कम्प्यूटेशनल लर्निंग थ्योरी

See also: स्टैटिस्टिकल लर्निंग थ्योरी

कंप्यूटर विज्ञान में, कम्प्यूटेशनल लर्निंग थ्योरी (या सिर्फ लर्निंग थ्योरी) मशीन लर्निंग एल्गोरिदम के डिजाइन और एनालिसिस का अध्ययन करने के लिए डिवोटेड आर्टिफीसियल इंटेलिजेंस का एक सबफ़ील्ड है।

समीक्षा

मशीन लर्निंग में थ्योरेटिकल रिजल्ट्स मुख्य रूप से एक प्रकार की इंडक्टिव लर्निंग से संबंधित होते हैं जिसे सुपरवाइज़ड लर्निंग कहा जाता है। सुपरवाइज़ड लर्निंग में, एक एल्गोरिदम में सैंपल दिए जाते हैं जिन्हें कुछ उपयोगी तरीके से लेबल किया जाता है। उदाहरण के लिए, सैंपल में मशरूम का विवरण हो सकता है, और लेबल यह हो सकता है कि मशरूम खाने योग्य हैं या नहीं। एल्गोरिदम इन पहले से लेबल किए गए सैंपल को लेता है और एक क्लासिफायरियर को इंड्यूस करने के लिए उनका उपयोग करता है। यह क्लासिफायरियर एक ऐसा फ़ंक्शन है जो सैंपल को लेबल प्रदान करता है, जिसमें ऐसे सैंपल भी सम्मिलित हैं जो पहले एल्गोरिदम द्वारा नहीं देखे गए हैं। सुपरवाइज़ड लर्निंग एल्गोरिदम का लक्ष्य प्रदर्शन के कुछ मापों को ऑप्टिमाइज़ करना है जैसे कि नए सैंपल पर की गई गलतियों की संख्या को कम करना।

परफॉरमेंस बाउंड के अतिरिक्त, कम्प्यूटेशनल लर्निंग थ्योरी लर्निंग की टाइम कॉम्पलेक्सिटी और फिजिबिलिटी का अध्ययन करता है। कम्प्यूटेशनल लर्निंग थ्योरी के अनुसार, एक कम्प्यूटेशन तभी फिजिबल मानी जाती है यदि इसे पोलीनोमिअल टाइम में किया जा सके। टाइम कॉम्पलेक्सिटी रिजल्ट्स दो प्रकार के होते हैं:

• पॉजिटिव रिजल्ट्स – दिखा रहा है कि कार्यों का एक निश्चित वर्ग बहुपद समय में लर्निंग योग्य है।
• निगेटिव रिजल्ट्स – दिखा रहा है कि कुछ कक्षाएं बहुपद समय में नहीं सीखी जा सकतीं।

निगेटिव रिजल्ट्स अक्सर आम तौर पर मानी जाने वाली, लेकिन फिर भी अप्रमाणित धारणाओं पर निर्भर होते हैं, जैसे कि:

• कम्प्यूटेशनल जटिलता - पी बनाम एनपी समस्या|पी ≠ एनपी (पी बनाम एनपी समस्या);
• क्रिप्टोग्राफी - एकतरफा कार्य मौजूद हैं।

कम्प्यूटेशनल लर्निंग थ्योरी के लिए कई अलग-अलग दृष्टिकोण हैं जो सीमित डेटा से सामान्यीकरण के लिए उपयोग किए जाने वाले अनुमान थ्योरीों के बारे में अलग-अलग धारणाएं बनाने पर आधारित हैं। इसमें संभाव्यता की विभिन्न परिभाषाएँ (आवृत्ति संभाव्यता, बायेसियन संभाव्यता देखें) और सैंपल की पीढ़ी पर विभिन्न धारणाएँ सम्मिलित हैं। विभिन्न दृष्टिकोणों में सम्मिलित हैं:

• सटीक शिक्षा, एंग्लुइन फंड द्वारा प्रस्तावित;
• संभवतः लगभग सही लर्निंग (पीएसी लर्निंग), लेस्ली वैलेंट द्वारा प्रस्तावित;
• वीसी थ्योरी, व्लादिमीर वापनिक और एलेक्सी हिरवोनेंकिस द्वारा प्रस्तावित;
• रे सोलोमनॉफ़ द्वारा विकसित सोलोमनॉफ़ का आगमनात्मक अनुमान का थ्योरी;
• एल्गोरिथम लर्निंग थ्योरी, ई. मार्क गोल्ड के कार्य से;
• निक लिटलस्टोन के काम से ऑनलाइन मशीन लर्निंग.

जबकि इसका प्राथमिक लक्ष्य लर्निंग को अमूर्त रूप से समझना है, कम्प्यूटेशनल लर्निंग थ्योरी ने व्यावहारिक एल्गोरिदम के विकास को जन्म दिया है। उदाहरण के लिए, पीएसी थ्योरी ने बूस्टिंग (मेटा-एल्गोरिदम) को प्रेरित किया, वीसी थ्योरी ने वेक्टर मशीनों का समर्थन किया, और बायेसियन अनुमान ने विश्वास नेटवर्क को प्रेरित किया।

यह भी देखें

• व्याकरण प्रेरण
• सूचना थ्योरी
• स्थिरता (लर्निंग का थ्योरी)
• त्रुटि सहनशीलता (पीएसी सीखना)

संदर्भ

सर्वेक्षण

• एंग्लुइन, डी. 1992. कम्प्यूटेशनल लर्निंग थ्योरी: सर्वेक्षण और चयनित ग्रंथ सूची। कंप्यूटिंग के थ्योरी पर चौबीसवें वार्षिक एसीएम संगोष्ठी की कार्यवाही में (मई 1992), पृष्ठ 351-369। http://portal.acm.org/cation.cfm?id=129712.129746
• डी. हौसलर। संभवतः लगभग सही सीख। आर्टिफिशियल इंटेलिजेंस पर आठवें राष्ट्रीय सम्मेलन की एएएआई-90 कार्यवाही में, बोस्टन, एमए, पृष्ठ 1101-1108। अमेरिकन एसोसिएशन फॉर आर्टिफिशियल इंटेलिजेंस, 1990। http://citeseer.ist.psu.edu/haussler90probable.html

वीसी आयाम

• वी. वापनिक और ए. चेर्वोनेंकिस। घटनाओं की सापेक्ष आवृत्तियों के उनकी संभावनाओं के समान अभिसरण पर। संभाव्यता का थ्योरी और उसके अनुप्रयोग, 16(2):264-280, 1971।

सुविधा चयन

• ए. धगट और एल. हेलरस्टीन, 'आईईईई सिम्प की कार्यवाही' में अप्रासंगिक विशेषताओं के साथ पीएसी सीखना। ऑन फ़ाउंडेशन ऑफ़ कंप्यूटर साइंस', 1994। http://citeseer.ist.psu.edu/dhagat94pac.html

प्रेरक अनुमान

• Gold, E. Mark (1967). "सीमा में भाषा की पहचान" (PDF). Information and Control. 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5.

इष्टतम ओ संकेतन सीखना

• ओडेड गोल्डरेइच, डाना रॉन। सार्वभौमिक लर्निंग एल्गोरिदम पर। http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224

निगेटिव रिजल्ट्स

• एम. किर्न्स और लेस्ली वैलेंट। 1989. बूलियन फ़ॉर्मूले और परिमित ऑटोमेटा लर्निंग पर क्रिप्टोग्राफ़िक सीमाएँ। कंप्यूटिंग के थ्योरी पर 21वीं वार्षिक एसीएम संगोष्ठी की कार्यवाही में, पृष्ठ 433-444, न्यूयॉर्क। एसीएम. http://citeseer.ist.psu.edu/kearns89cryptographic.html

बूस्टिंग (मशीन लर्निंग)

• रॉबर्ट ई. शापिरे। कमजोर लर्निंग की क्षमता की ताकत. मशीन लर्निंग, 5(2):197-227, 1990 http://citeseer.ist.psu.edu/schapire90strength.html

अधिगम सीखना

• ब्लूमर, ए.; एरेनफुच्ट, ए.; हौसलर, डी.; मैनफ्रेड के. वारमुथ|वार्मथ, एम.के. ओकाम का रेजर Inf.Proc.Lett। 24, 377-380, 1987.
• ब्लूमर, ए.; एरेनफुच्ट, ए.; हौसलर, डी.; वार्मथ, एम.के. लर्निंग की क्षमता और वापनिक-चेरवोनेंकिस आयाम। एसीएम का जर्नल, 36(4):929-865, 1989।

शायद लगभग सही सीख

• एल. बहादुर। लर्निंग योग्य एक थ्योरी। एसीएम के संचार, 27(11):1134-1142, 1984।

त्रुटि सहनशीलता

• माइकल किर्न्स और मिंग ली। दुर्भावनापूर्ण त्रुटियों की उपस्थिति में सीखना. कंप्यूटिंग पर सियाम जर्नल, 22(4):807-837, अगस्त 1993। http://citeseer.ist.psu.edu/kearns93learning.html
• किर्न्स, एम. (1993)। सांख्यिकीय प्रश्नों से कुशल शोर-सहिष्णु शिक्षा। कंप्यूटिंग के थ्योरी पर पच्चीसवीं वार्षिक एसीएम संगोष्ठी की कार्यवाही में, पृष्ठ 392-401। http://citeseer.ist.psu.edu/kearns93efficient.html

समतुल्यता

• डी.हौसलर, एम.केर्न्स, एन.लिटलस्टोन और मैनफ्रेड के. वार्मथ|एम. वार्मथ, बहुपद लर्निंग की क्षमता के लिए मॉडलों की समतुल्यता, प्रोक। कम्प्यूटेशनल लर्निंग थ्योरी पर पहली एसीएम कार्यशाला, (1988) 42-55।
• Pitt, L.; Warmuth, M. K. (1990). "भविष्यवाणी-संरक्षण न्यूनता". Journal of Computer and System Sciences. 41 (3): 430–467. doi:10.1016/0022-0000(90)90028-J.

इनमें से कुछ प्रकाशनों का विवरण कंप्यूटर विज्ञान#मशीन लर्निंग में महत्वपूर्ण प्रकाशनों की सूची में दिया गया है।

बाहरी संबंध

• Basics of Bayesian inference