प्रथम-अनुक्रम प्रेरक शिक्षार्थी

यंत्र अधिगम में, फर्स्ट-ऑर्डर इंडक्टिव लर्नर (FOIL) एक नियम-आधारित लर्निंग एल्गोरिदम है।

पृष्ठभूमि

1990 में रॉस क्विनलान द्वारा विकसित, FOIL फ़ंक्शन-मुक्त हॉर्न उपवाक्य ़ सीखता है, जो प्रथम-क्रम विधेय कैलकुलस का एक उपसमूह है। कुछ अवधारणाओं के सकारात्मक और नकारात्मक उदाहरणों और पृष्ठभूमि-ज्ञान विधेय (गणितीय तर्क) के एक सेट को देखते हुए, FOIL अवधारणा के लिए एक तार्किक अवधारणा परिभाषा या नियम उत्पन्न करता है। प्रेरित नियम में कोई भी स्थिरांक शामिल नहीं होना चाहिए (रंग (एक्स, लाल) रंग (एक्स, वाई), लाल (वाई) बन जाता है) या फ़ंक्शन प्रतीक, लेकिन नकारात्मक विधेय की अनुमति दे सकता है; पुनरावर्ती अवधारणाएँ भी सीखने योग्य हैं।

ID3 एल्गोरिदम की तरह, FOIL डेटा को कवर करने वाले नियम का निर्माण करने के लिए सूचना सिद्धांत पर आधारित मीट्रिक का उपयोग करके पहाड़ी पर चढ़ता है। हालाँकि, ID3 के विपरीत, FOIL फूट डालो और जीतो एल्गोरिदम के बजाय एक अलग-और-जीत विधि का उपयोग करता है, एक समय में एक नियम बनाने और एल्गोरिदम के अगले पुनरावृत्ति के लिए उजागर उदाहरण एकत्र करने पर ध्यान केंद्रित करता है।

एल्गोरिदम

FOIL एल्गोरिथ्म इस प्रकार है:

इनपुट उदाहरणों की सूची

आउटपुट प्रथम-क्रम विधेय तर्क में नियम

FOIL(उदाहरण)

पॉज़ को सकारात्मक उदाहरण बनने दें

प्रेड को सीखने के लिए विधेय बनने दें

जब तक पॉज़ खाली न हो जाए:

नेग को नकारात्मक उदाहरण मानें

बॉडी को खाली पर सेट करें

LearnClauseBody को कॉल करें

नियम में प्रीड ← बॉडी जोड़ें

पॉज़ से उन सभी उदाहरणों को हटा दें जो बॉडी को संतुष्ट करते हैं

प्रक्रिया लर्नक्लॉजबॉडी

जब तक नेग खाली न हो जाए:

एक शाब्दिक एल चुनें

एल को बॉडी से जोड़ें

नकारात्मक उदाहरणों से हटाएं जो एल को संतुष्ट नहीं करते हैं

उदाहरण

मान लीजिए कि FOIL का कार्य पिता (X, Y) और माता-पिता (X, Y) के संबंधों को देखते हुए दादा (X, Y) की अवधारणा को सीखना है। इसके अलावा, मान लीजिए कि हमारे वर्तमान शरीर में दादा (एक्स, वाई) ← माता-पिता (एक्स, जेड) शामिल हैं। इसे बॉडी को किसी भी शाब्दिक पिता (एक्स, एक्स), पिता (वाई, जेड), माता-पिता (यू, वाई), या कई अन्य के साथ जोड़कर बढ़ाया जा सकता है - इस शाब्दिक को बनाने के लिए, एल्गोरिदम को एक विधेय नाम दोनों का चयन करना होगा और विधेय के लिए चर का एक सेट (जिनमें से कम से कम एक को खंड के अस्वीकृत शाब्दिक में पहले से मौजूद होना आवश्यक है)। यदि FOIL शाब्दिक माता-पिता (X,Z) को जोड़कर एक खंड दादा (X,Y) ← true का विस्तार करता है, तो यह नए चर Z का परिचय दे रहा है। सकारात्मक उदाहरणों में अब वे मान शामिल हैं <X,Y,Z> जैसे कि दादा( X,Y) सत्य है और मूल(X,Z) सत्य है; नकारात्मक उदाहरण वे हैं जहां दादा (एक्स, वाई) सत्य है लेकिन माता-पिता (एक्स, जेड) गलत है।

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

एक्सटेंशन

FOCL एल्गोरिथ्म (फर्स्ट ऑर्डर कंबाइंड लर्नर) एफओआईएल को विभिन्न तरीकों से विस्तारित करता है, जो प्रभावित करता है कि एफओसीएल निर्माणाधीन खंड का विस्तार करते समय परीक्षण के लिए शाब्दिक चयन कैसे करता है। खोज स्थान पर बाधाओं की अनुमति है, जैसे कि विधेय हैं जो उदाहरणों के एक सेट के बजाय एक नियम पर परिभाषित होते हैं (जिन्हें इंटेंसियल विधेय कहा जाता है); सबसे महत्वपूर्ण बात यह है कि एक संभावित गलत परिकल्पना को सीखे जाने वाले विधेय के प्रारंभिक अनुमान के रूप में अनुमति दी जाती है। FOCL का मुख्य लक्ष्य FOIL के अनुभवजन्य तरीकों में स्पष्टीकरण-आधारित शिक्षा (EBL) के तरीकों को शामिल करना है।

यहां तक ​​कि जब एफओआईएल पर एफओसीएल को कोई अतिरिक्त ज्ञान प्रदान नहीं किया जाता है, तब भी, यह पुनरावृत्त गहनता गहराई-पहली खोज के समान एक पुनरावृत्तीय चौड़ीकरण खोज रणनीति का उपयोग करता है|गहराई-पहली खोज: पहला एफओसीएल कोई मुक्त चर पेश करके एक खंड को सीखने का प्रयास करता है। यदि यह विफल हो जाता है (कोई सकारात्मक लाभ नहीं), तो प्रति विफलता एक अतिरिक्त मुक्त चर की अनुमति दी जाती है जब तक कि मुक्त चर की संख्या किसी भी विधेय के लिए उपयोग की गई अधिकतम से अधिक न हो जाए।

बाधाएँ

FOIL के विपरीत, जो अपने वेरिएबल्स पर टाइपिंग की बाधा नहीं डालता है, FOCL पृष्ठभूमि ज्ञान के एक सरल रूप को शामिल करने के एक सस्ते तरीके के रूप में टाइपिंग का उपयोग करता है। उदाहरण के लिए, एक विधेय जीवनएट(एक्स,वाई) में जीवनएट(व्यक्ति, स्थान) प्रकार हो सकते हैं। हालाँकि, अतिरिक्त विधेय पेश करने की आवश्यकता हो सकती है - बिना प्रकार के, नेक्स्टडोर (एक्स, वाई) यह निर्धारित कर सकता है कि क्या व्यक्ति एक्स और व्यक्ति वाई एक-दूसरे के बगल में रहते हैं, या क्या दो स्थान एक-दूसरे के बगल में हैं। प्रकारों के साथ, इस कार्यक्षमता को बनाए रखने के लिए दो अलग-अलग विधेय नेक्स्टडोर (व्यक्ति, व्यक्ति) और नेक्स्ट डोर (स्थान, स्थान) की आवश्यकता होगी। हालाँकि, यह टाइपिंग तंत्र isPerson(X) या isLocation(Y) जैसे विधेय की आवश्यकता को समाप्त कर देता है, और जब A और B को व्यक्ति चर के रूप में परिभाषित किया जाता है, तो खोज स्थान को कम करते हुए, lifeAt(A,B) पर विचार करने की आवश्यकता नहीं होती है। इसके अतिरिक्त, टाइपिंग जीवनएट(ए,बी) जैसे असंभव शाब्दिकों को हटाकर परिणामी नियम की सटीकता में सुधार कर सकती है, जो फिर भी उच्च सूचना लाभ के लिए प्रतीत हो सकता है।

बराबर (एक्स, एक्स) या बीच (एक्स, एक्स, वाई) जैसे तुच्छ विधेय को लागू करने के बजाय, एफओसीएल चर पर अंतर्निहित बाधाओं का परिचय देता है, जिससे खोज स्थान और कम हो जाता है। कुछ विधेय में सभी चर अद्वितीय होने चाहिए, अन्य में क्रमविनिमेयता होनी चाहिए (आसन्न (एक्स, वाई) आसन्न (वाई, एक्स) के बराबर है), फिर भी दूसरों को वर्तमान खंड में एक विशेष चर मौजूद होने की आवश्यकता हो सकती है, और कई अन्य संभावित बाधाएं .

परिचालन नियम

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

'इनपुट्स' शाब्दिक रूप से क्रियान्वित किया जाना है, सकारात्मक उदाहरणों की सूची, नकारात्मक उदाहरणों की सूची

'आउटपुट' क्रियात्मक रूप में शाब्दिक

परिचालन (शाब्दिक, सकारात्मक उदाहरण, नकारात्मक उदाहरण)

यदि 'लिटरल' क्रियाशील है

वापसी 'शाब्दिक'

खाली सेट पर 'ऑपरेशनल लिटरल्स' प्रारंभ करें

'शाब्दिक' की परिभाषा में प्रत्येक खंड के लिए

सकारात्मक उदाहरणों और नकारात्मक उदाहरणों पर खंड की जानकारी लाभ की गणना करें

अधिकतम लाभ वाले खंड के लिए

वाक्य में प्रत्येक शाब्दिक 'एल' के लिए

'ऑपरेशनल लिटरल्स' में ऑपरेशनलाइज़ ('एल', सकारात्मक उदाहरण, नकारात्मक उदाहरण) जोड़ें

एक परिचालन नियम शाब्दिक रूप से कम (X,Y) हो सकता है; एक गैर-परिचालन नियम (X,Y,Z) ← से कम(X,Y), कम से कम(Y,Z) के बीच हो सकता है।

प्रारंभिक नियम

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

संदर्भ

• http://www.csc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/foil.html