हो–कश्यप एल्गोरिथ्म मशीन लर्निंग में रैखिक वर्गीकरणकर्ताओं को प्रशिक्षित करने के लिए एक पुनरावृत्तीय प्रक्रिया है। यह 1965 में यू-ची हो और रंगासामी एल. कश्यप द्वारा विकसित किया गया था, और यह विभेदक-आधारित शिक्षण विधियों के परिवार से संबंधित है जो एक विशेषता स्थान में वर्गों को अलग करने के लिए एक हाइपरप्लेन ढूंढते हैं। पहले के परसेप्ट्रॉन-शैली नियमों के विपरीत जो केवल भार वेक्टर को समायोजित करते हैं, हो–कश्यप एल्गोरिथ्म एक मार्जिन वेक्टर को भी समायोजित करता है, जिससे यह अभिसरण कर सकता है, भले ही प्रशिक्षण डेटा सख्ती से रैखिक रूप से वियोज्य न हो, बशर्ते कि एक शिथिल अर्थ में समाधान मौजूद हो।
एल्गोरिथ्म एक वर्ग-त्रुटि मानदंड फलन को न्यूनतम करता है। प्रशिक्षण नमूनों के एक समूह को देखते हुए, जिनमें से प्रत्येक को एक विशेषता वेक्टर द्वारा दर्शाया गया है, लक्ष्य एक भार वेक्टर और एक मार्जिन वेक्टर खोजना है, जैसे कि विशेषता मैट्रिक्स और भार वेक्टर का गुणनफल एक धनात्मक मार्जिन वेक्टर के बराबर हो। प्रक्रिया मार्जिन वेक्टर को ग्रेडिएंट डिसेंट चरण का उपयोग करके अद्यतन करने और भार वेक्टर को न्यूनतम-वर्ग समाधान के माध्यम से अद्यतन करने के बीच वैकल्पिक रूप से चलती है। यह दोहरा अद्यतन एल्गोरिथ्म को प्रत्येक पुनरावृत्ति पर एक बंद-रूप भार अद्यतन देता है, जिससे यह कम्प्यूटेशनल रूप से कुशल हो जाता है और मानदंड की एकदिष्ट कमी सुनिश्चित करता है।
गणितीय सूत्रीकरण
मान लीजिए कि प्रशिक्षण डेटा में \(n\) नमूने हैं, प्रत्येक में \(d\) विशेषताएँ हैं, जो एक \(n \times d\) मैट्रिक्स \(X\) में व्यवस्थित हैं। प्रत्येक नमूने को दो वर्गों में से एक से संबंधित के रूप में लेबल किया गया है, और लेबल +1 या -1 के रूप में एन्कोड किए गए हैं। एल्गोरिथ्म एक भार वेक्टर \(w\) और एक मार्जिन वेक्टर \(b\) (सभी घटक धनात्मक) खोजता है, जैसे कि \(Xw = b\)। न्यूनतम करने का मानदंड \(J(w, b) = \|Xw - b\|^2\) है।
अद्यतन नियम हैं:
- \(b_{k+1} = b_k + \rho (Xw_k - b_k)\), जहाँ \(\rho\) एक सीखने की दर है, और \(b\) के ऋणात्मक घटकों को धनात्मकता बनाए रखने के लिए शून्य पर सेट किया जाता है।
- \(w_{k+1} = (X^T X)^{-1} X^T b_{k+1}\), जो वर्तमान मार्जिन वेक्टर के लिए न्यूनतम-वर्ग समाधान है।
यह दो-चरणीय प्रक्रिया तब तक दोहराई जाती है जब तक कि मानदंड एक सीमा से नीचे न गिर जाए या पुनरावृत्तियों की अधिकतम संख्या तक न पहुँच जाए। यदि डेटा रैखिक रूप से वियोज्य है तो एल्गोरिथ्म समाधान में अभिसरण करने की गारंटी है; यदि नहीं, तो यह दोलन कर सकता है, और एक सामान्य प्रथा यह है कि गैर-वियोज्य मामलों में अभिसरण को मजबूर करने के लिए मार्जिन वेक्टर में एक छोटा धनात्मक स्थिरांक जोड़ा जाए।
ऐतिहासिक संदर्भ
एल्गोरिथ्म 1960 के दशक के मध्य में पेश किया गया था, जो पैटर्न पहचान और तंत्रिका नेटवर्क में तीव्र विकास की अवधि थी। यू-ची हो और रंगासामी एल. कश्यप ने अपना काम 1965 में IEEE ट्रांज़ैक्शन्स ऑन इलेक्ट्रॉनिक कंप्यूटर्स में प्रकाशित किया। उस समय, रैखिक वर्गीकरणकर्ता वर्ण पहचान और सिग्नल वर्गीकरण जैसे कार्यों के लिए एक प्राथमिक उपकरण थे। हो–कश्यप एल्गोरिथ्म ने परसेप्ट्रॉन सीखने के नियम पर एक सुधार की पेशकश की, जो डेटा पूरी तरह से वियोज्य न होने पर अभिसरण करने में विफल हो सकता था। मार्जिन वेक्टर को पेश करके, एल्गोरिथ्म ने एक अधिक मजबूत दृष्टिकोण प्रदान किया जो शोर या अतिव्यापी डेटा को संभाल सकता था।
यह विधि न्यूनतम-माध्य-वर्ग (LMS) एल्गोरिथ्म और विड्रो-हॉफ नियम से निकटता से संबंधित है, जो उसी अवधि के आसपास बर्नार्ड विड्रो और उनके सहयोगियों द्वारा विकसित किए गए थे। हालाँकि, हो–कश्यप एल्गोरिथ्म स्पष्ट रूप से मार्जिन को मॉडल करता है, जिससे यह आधुनिक सपोर्ट वेक्टर मशीनों (SVMs) का अग्रदूत बन जाता है जो बेहतर सामान्यीकरण के लिए मार्जिन पर भी जोर देते हैं।
अनुप्रयोग और विस्तार
अपने मूल रूप में, हो–कश्यप एल्गोरिथ्म पैटर्न पहचान में समस्याओं पर लागू किया गया था, जैसे कि हस्तलिखित अंकों को वर्गीकृत करना और शोर में सिग्नल का पता लगाना। दशकों में, इसे कई तरीकों से विस्तारित किया गया है:
- गैर-रैखिक विस्तार: इनपुट को कर्नेल फलन के माध्यम से मैप करके, एल्गोरिथ्म को गैर-रैखिक रूप से वियोज्य डेटा पर लागू किया जा सकता है, जैसा कि कर्नेलाइज़्ड SVMs में होता है।
- नियमितीकरण: मानदंड में एक दंड पद जोड़ना, जैसे \(\lambda \|w\|^2\), सामान्यीकरण में सुधार करता है और खराब-स्थिति वाले मैट्रिक्स को संभालता है।
- बहु-वर्ग समस्याएँ: द्विआधारी सूत्रीकरण को एक-बनाम-सभी या एक-बनाम-एक रणनीतियों का उपयोग करके कई वर्गों तक बढ़ाया जा सकता है।
- ऑनलाइन सीखना: स्ट्रीमिंग डेटा के लिए विविधताएँ विकसित की गई हैं जहाँ नमूने क्रमिक रूप से आते हैं।
इन विस्तारों ने एल्गोरिथ्म को आधुनिक मशीन लर्निंग पाठ्यक्रमों में प्रासंगिक बनाए रखा है, जिसे अक्सर रैखिक विभेदक विश्लेषण में पुनरावृत्तीय अनुकूलन के उदाहरण के रूप में पढ़ाया जाता है।
अन्य विधियों से संबंध
हो–कश्यप एल्गोरिथ्म कई अन्य सीखने की तकनीकों के साथ वैचारिक समानताएँ साझा करता है। परसेप्ट्रॉन एल्गोरिथ्म, जिसे फ्रैंक रोसेनब्लैट ने 1958 में पेश किया था, एक अलग करने वाला हाइपरप्लेन भी ढूंढता है, लेकिन गैर-वियोज्य डेटा के लिए अभिसरण की गारंटी नहीं देता है। हो–कश्यप एल्गोरिथ्म का न्यूनतम-वर्ग अद्यतन का उपयोग एडम ऑप्टिमाइज़र के समान है, क्योंकि दोनों में अनुकूली समायोजन शामिल हैं, हालाँकि एडम गहन शिक्षण के लिए स्टोकेस्टिक ग्रेडिएंट के साथ डिज़ाइन किया गया है। इसके विपरीत, हो–कश्यप एल्गोरिथ्म नियतात्मक और बैच-आधारित है।
एक और संबंधित विधि विश्रांति विधि है, जो मार्जिन को भी समायोजित करती है लेकिन विभिन्न अद्यतन नियमों का उपयोग करती है। हो–कश्यप एल्गोरिथ्म की तुलना अक्सर न्यूनतम-वर्ग वर्गीकरणकर्ता से की जाती है, जो धनात्मक मार्जिन लागू किए बिना वर्ग त्रुटि को न्यूनतम करता है; मार्जिन बाधा ही हो–कश्यप एल्गोरिथ्म को उसके अभिसरण गुण प्रदान करती है।
व्यावहारिक विचार
हो–कश्यप एल्गोरिथ्म को लागू करते समय, कई व्यावहारिक मुद्दे उत्पन्न होते हैं। \((X^T X)^{-1}\) की गणना बड़े \(d\) के लिए महंगी हो सकती है, और यदि विशेषताएँ अनावश्यक हैं तो मैट्रिक्स एकवचन हो सकता है। ऐसे मामलों में, छद्म-व्युत्क्रम या नियमितीकरण तकनीकों का उपयोग किया जाता है। सीखने की दर \(\rho\) को सावधानी से चुना जाना चाहिए; बहुत बड़ा मान दोलन का कारण बन सकता है, जबकि बहुत छोटा अभिसरण को धीमा कर देता है। एक सामान्य विकल्प \(\rho = 1\) है, जो अक्सर व्यवहार में अच्छी तरह से काम करता है।
एल्गोरिथ्म विशेषताओं के पैमाने के प्रति संवेदनशील है। बड़े-परिमाण वाली विशेषताओं द्वारा प्रभुत्व से बचने के लिए विशेषताओं को शून्य माध्य और इकाई विचरण में मानकीकृत करने की सिफारिश की जाती है। उच्च-आयामी डेटा के लिए, जैसे कि पाठ वर्गीकरण में, एल्गोरिथ्म अतिअनुकूलन कर सकता है, और नियमितीकरण आवश्यक हो जाता है।
दशकों पुराना होने के बावजूद, हो–कश्यप एल्गोरिथ्म एक मूल्यवान शैक्षणिक उपकरण बना हुआ है। यह अनुकूलन और सीखने के बीच की अंतःक्रिया को दर्शाता है, और इसका अभिसरण प्रमाण पैटर्न पहचान सिद्धांत में एक क्लासिक परिणाम है। मशीन लर्निंग पर आधुनिक पाठ्यपुस्तकें अक्सर इसे सरल परसेप्ट्रॉन और अधिक उन्नत मार्जिन-आधारित वर्गीकरणकर्ताओं के बीच एक पुल के रूप में शामिल करती हैं।