An Optimal Agnostic PAC Algorithm

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

इसका उत्तर देने के लिए, वैज्ञानिक VC डायमेंशन (वैपनिक और चेरवनिकिस के नाम पर) नामक एक अवधारणा का उपयोग करते हैं। VC डायमेंशन को रोबोट के मस्तिष्क के "भ्रमित करने वाले" या "जटिल" होने के माप के रूप में समझें। एक सरल मस्तिष्क जो केवल कान के आकार को देखता है उसका VC डायमेंशन कम होता है; एक सुपर-जटिल मस्तिष्क जो हर एक पिक्सेल को देखता है उसका उच्च VC डायमेंशन होता है। लक्ष्य एक "स्वीट स्पॉट" खोजना है जहाँ रोबोट उपयोगी होने के लिए पर्याप्त तेज़ी से सीखता है, लेकिन इतना जटिल भी नहीं है कि वह नियमों को सीखने के बजाय प्रशिक्षण तस्वीरों को याद कर ले। दशकों से, गणितज्ञों ने एक सटीक फॉर्मूला खोजने की कोशिश की है जो हमें ठीक से बता सके कि एक निश्चित संख्या में उदाहरणों और जटिलता के एक निश्चित स्तर को देखते हुए, एक रोबोट द्वारा की जाने वाली "अतिरिक्त" त्रुटि कितनी होगी।

लंबे समय तक, हमारे ज्ञान में एक अंतराल था। हम जानते थे कि जब डेटा आदर्श होता है (लेबल में कोई गलती नहीं होती) तो सीखने की सर्वोत्तम गति क्या होती है, और हम जानते थे कि जब डेटा बहुत अव्यवस्थित होता है तो क्या होता है। लेकिन बीच की स्थिति क्या है? यदि डेटा थोड़ा शोर वाला (noisy) है? पिछले प्रयास एक भारी बैकपैक के साथ दौड़ लगाने की तरह थे; वे करीब तो थे, लेकिन वे उस अतिरिक्त "लॉगारिदमिक" वजन को ढो रहे थे जिसने उन्हें ज़रूरत से ज़्यादा धीमा कर दिया था। बड़ा सवाल यह था: क्या हम एक ऐसा लर्नर बना सकते हैं जो डेटा में कितना भी शोर हो, बिना वह अतिरिक्त वजन ढोए, बिल्कुल सबसे तेज़ गति से चल सके?

यह शोध पत्र, जिसका शीर्षक "An Optimal Agnostic PAC Algorithm" है, इस प्रश्न का उत्तर एक जोरदार "हाँ" के साथ देता है। लेखकों, मार्कस एंजेलुंड मैथियासेन, जियान क्वान और निकिता झिवोटोव्स्की ने एक विशिष्ट लर्निंग एल्गोरिदम का निर्माण किया है जो सांख्यिकीय रूप से इष्टतम जोखिम सीमा (statistically optimal risk bound) प्राप्त करता है। सरल शब्दों में, इसका अर्थ है कि उन्होंने एक ऐसा क्लासिफायर प्रशिक्षित करने का तरीका खोजा है जो न्यूनतम गलतियाँ करता है, और गणितीय रूप से यह सिद्ध किया है कि शोर के किसी भी स्तर के लिए कोई अन्य विधि (कुछ सार्वभौमिक स्थिरांकों तक) उन्हें मात नहीं दे सकती। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने इसे सिद्ध किया।

उन्होंने इसे कैसे किया, यहाँ एक बहुत ही व्यवस्थित पुस्तकालय और "वन-इनक्लूजन" के चतुर खेल की कहानी का उपयोग करके बताया गया है।

समस्या: शोर वाली लाइब्रेरी

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

"सबसे अच्छा संभव" सिस्टम (मान लीजिए कि ओरेकल) ब्रह्मांड के वास्तविक नियमों को जानता है। ओरेकल भी कुछ गलतियाँ करेगा क्योंकि लाइब्रेरियन के लेबल कभी-कभी गलत होते हैं। इस न्यूनतम त्रुटि दर को $L^*$ कहा जाता है। आपका लक्ष्य एक ऐसी प्रणाली बनाना है जो ओरेकल के प्रदर्शन के जितना संभव हो सके करीब पहुँच सके, लाइब्रेरी से सीमित किताबें ($n$) उपयोग करके।

शोध पत्र सिद्ध करता है कि उनकी नई प्रणाली (मान लीजिए कि द ऑप्टिमाइज़र) की त्रुटि दर ($L(\hat{h})$) इस प्रकार होगी:
$$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$$
गणित से डरें नहीं। मुख्य भाग वर्गमूल (square root) वाला पद है। यह सूत्र कहता है कि आपके द्वारा की जाने वाली अतिरिक्त गलतियाँ ( "excess risk") जैसे-जैसे आपको अधिक किताबें ($n$) मिलती हैं, वैसे-वैसे कम होती जाती हैं, और यह संभाव्यता के नियमों द्वारा अनुमति दी गई सबसे तेज़ गति से कम होती हैं। पिछले तरीकों में अतिरिक्त कारक (जैसे $\log(n)$) थे जिन्होंने उन्हें धीमा कर दिया था, लेकिन द ऑप्टिमाइज़र उन सबको हटा देता है।

गुप्त नुस्खा: क्यूब और ओरिएंटेशन

उन्होंने यह कैसे किया? उन्होंने दो विचारों के शानदार संयोजन का उपयोग किया: वन-इनक्लूजन ग्राफ (The One-Inclusion Graph) और सफिक्स एवरेजिंग (Suffix Averaging)।

1. वन-इनक्लूजन ग्राफ (द क्यूब गेम)
कल्पना करें कि आपके सैंपल में मौजूद सभी संभावित तरीके कैसे हो सकते हैं जिनमें किताबों को लेबल किया जा सकता है। यदि आपके पास $n$ किताबें हैं, तो $2^n$ संभावित लेबल संयोजन हैं। आप इन संयोजनों को एक विशाल, बहु-आयामी घन (एक "बूलियन क्यूब") के कोनों के रूप में देख सकते हैं।

• दो कोने एक किनारे (edge) से जुड़े होते हैं यदि वे एक किताब के लेबल में अंतर रखते हैं।
• "ओरेकल" (सबसे अच्छा नियम) इस घन में कहीं रहता है।
• लक्ष्य यह पता लगाना है कि जब आप एक कोने पर होते हैं, तो आपको किस दिशा में इशारा करना चाहिए, ताकि आप ओरेकल के करीब पहुँच सकें।

लेखक ओरिएंटेशन नामक तकनीक का उपयोग करते हैं। कल्पना करें कि आप इस घन के एक कोने पर खड़े हैं। आपको तय करना होगा कि किस दिशा में जाना है। शोध पत्र एक नया गणितीय उपकरण पेश करता है जिसे लेम्मा 2.1 (Lemma 2.1) कहा जाता है, जो एक "क्लास-डिपेंडेंट एज आइसोपेरिमेट्रिक इनइक्वेलिटी" है। हमारी लाइब्रेरी एनालॉजी में, यह एक नियम की तरह है जो कहता है: "सही दिशा खोजने के लिए आपको कितने पथों की जाँच करने की आवश्यकता है, यह इस पर निर्भर करता है कि आप ओरेकल से कितनी दूर हैं और लाइब्रेरी कितनी जटिल है।"

वे सिद्ध करते हैं कि आप इस विशाल घन में प्रत्येक किनारे को एक दिशा दे सकते हैं ताकि, आप चाहे कहीं से भी शुरू करें, आपको सबसे अच्छे उत्तर के करीब पहुँचने के लिए एक विशिष्ट संख्या से अधिक कदम उठाने की आवश्यकता नहीं होगी। यह चरण महत्वपूर्ण है क्योंकि यह एक अस्त-व्यस्त अनुमान लगाने वाले खेल को एक नियतात्मक पथ (deterministic path) में बदल देता है।

2. सफिक्स एवरेजिंग (द कमेटी वोट)
एक बार जब आपके पास यह पूर्ण ओरिएंटेशन हो जाता है, तो उन्हें इसे एक वास्तविक दुनिया के प्रेडिक्टर में बदलने की आवश्यकता होती है। वे सफिक्स एवरेजिंग नामक एक ट्रिक का उपयोग करते हैं।
कल्पना कीजिए कि आप विशेषज्ञों की एक टीम बना रहे हैं। आप केवल एक विशेषज्ञ की राय नहीं लेते। इसके बजाय, आप विशेषज्ञों की एक श्रृंखला से पूछते हैं जिन्होंने डेटा की थोड़ी अलग मात्रा देखी है।

• विशेषज्ञ 1 ने पहले $k$ किताबें देखी हैं।
• विशेषज्ञ 2 ने पहली $k+1$ किताबें देखी हैं।
• ...
• विशेषज्ञ $m$ ने पहली $2k-1$ किताबें देखी हैं।

अंतिम भविष्यवाणी इन सभी विशेषज्ञों की राय का औसत (average) है। यह शक्तिशाली है क्योंकि यह यादृच्छिकता (randomness) को सुचारू बनाता है। यदि एक विशेषज्ञ को शोर वाले बुक के साथ दुर्भाग्यपूर्ण अनुभव होता है, तो अन्य विशेषज्ञ उसे संतुलित कर देते हैं। शोध पत्र सिद्ध करता है कि यह औसत प्रक्रिया, उनके पूर्ण क्यूब ओरिएंटेशन के साथ मिलकर, त्रुटि दर को कम रखती है, भले ही डेटा शोर वाला क्यों न हो।

3. द फाइनल पॉलिश: थ्रेशोल्डिंग (Thresholding)
औसत परिणाम -1 और 1 के बीच का एक नंबर (एक "स्कोर") है। "बिल्ली" या "कुत्ता" का अंतिम उत्तर प्राप्त करने के लिए, वे एक थ्रेशोल्ड का उपयोग करते हैं। वे सबसे अच्छे कट-ऑफ पॉइंट को चुनने के लिए सत्यापन पुस्तकों (validation books) के एक अलग सेट पर कई अलग-अलग कट-ऑफ पॉइंट का परीक्षण करते हैं। यह चरण सुनिश्चित करता है कि अंतिम परिणाम एक सरल, नियतात्मक नियम (एक बाइनरी क्लासिफायर) है, न कि एक धुंधली संभावना।

यह क्यों मायने रखता है

इस शोध पत्र से पहले, यदि आप सबसे तेज़ सीखने की दर चाहते थे, तो आपको आदर्श डेटा के लिए काम करने वाले तरीकों और शोर वाले डेटा के लिए काम करने वाले तरीकों के बीच चयन करना पड़ता था। आप बिना किसी दंड के दोनों दुनियाओं का सर्वश्रेष्ठ प्राप्त नहीं कर सकते थे।

यह शोध पत्र दिखाता है कि आप दोनों दुनियाओं का सर्वश्रेष्ठ प्राप्त कर सकते हैं। उन्होंने एक ऐसा लर्नर बनाया जो:

1. इसे शोर के स्तर को जानने की आवश्यकता नहीं है: यह बिना यह जाने काम करता है कि डेटा कितना अव्यवस्थित है ($L^*$) या आप कितने आश्वस्त होना चाहते हैं ($\delta$)।
2. यह इष्टतम (optimal) है: यह डेवरोय, ग्योर्फी और लुगोसी जैसे पिछले शोधकर्ताओं द्वारा स्थापित सैद्धांतिक निचली सीमा (speed limit) से मेल खाता है।
3. यह नियतात्मक (deterministic) है: यह भाग्य पर निर्भर नहीं करता है; यह उसी डेटा पर चलाने पर हर बार समान उत्तर देता है।

लेखक स्पष्ट रूप से इस विचार को खारिज करते हैं कि इष्टतम परिणाम प्राप्त करने के लिए हमें "पॉलीलॉगारिदमिक" कारकों (उन अतिरिक्त धीमी गति वाले कारकों) की आवश्यकता है। वे सिद्ध करते हैं कि वे कारक अनावश्यक हैं। वे यह भी दिखाते हैं कि जबकि कुछ पिछली विधियाँ (जैसे साधारण बहुमत वोट) आदर्श डेटा के लिए अच्छी तरह से काम करती हैं, वे शोर पेश होने पर इष्टतम गति बनाए रखने में विफल रहती हैं।

संक्षेप में, यह शोध पत्र मशीन लर्निंग सिद्धांत के इतिहास में एक लंबे समय से चले आ रहे अध्याय को समाप्त करता है। यह बाइनरी क्लासिफिकेशन के लिए एक "परफेक्ट" एल्गोरिदम प्रदान करता है, जहाँ डेटा कभी भी आदर्श नहीं होता है। यह एक ऐसे मानचित्र को खोजने जैसा है जो गारंटी देता है कि आप खजाना पा सकते हैं, चाहे सड़क पर कितने भी गड्ढे हों। लेखकों ने केवल यह सुझाव नहीं दिया कि यह संभव है; उन्होंने मानचित्र बनाया और सिद्ध किया कि यह काम करता है।