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

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