क्या कंप्यूटर के लिए उपयोगकर्ता द्वारा प्रदत्त उदाहरणों द्वारा नियमित अभिव्यक्ति को "सीखना" संभव है?

Question

क्या कंप्यूटर के लिए उपयोगकर्ता द्वारा प्रदत्त उदाहरणों द्वारा नियमित अभिव्यक्ति को "सीखना" संभव है?

स्पष्ट करने के लिए:

• मैं नहीं नियमित अभिव्यक्ति जानने के लिए चाहते हैं।
• मैं एक ऐसा प्रोग्राम बनाना चाहता हूं जो एक उदाहरण से एक नियमित अभिव्यक्ति "सीखता है" जो किसी उपयोगकर्ता द्वारा इंटरैक्टिव रूप से प्रदान किया जाता है, शायद किसी पाठ से भागों का चयन करके या स्टार्ट या एंड मार्कर चुनकर।

क्या यह संभव है? क्या एल्गोरिदम, कीवर्ड, आदि हैं जिनके लिए मैं Google कर सकता हूं?

संपादित: आप जवाब के लिए धन्यवाद, लेकिन मैं उपकरण जो यह सुविधा उपलब्ध कराने में कोई दिलचस्पी नहीं है। मैं सैद्धांतिक जानकारी की तलाश में हूं, जैसे कागजात, ट्यूटोरियल, स्रोत कोड, एल्गोरिदम के नाम, इसलिए मैं अपने लिए कुछ बना सकता हूं।

Answer 1

पुस्तक An Introduction to Computational Learning Theory में एक सीमित automaton सीखने के लिए एक एल्गोरिदम शामिल है। चूंकि प्रत्येक नियमित भाषा एक सीमित automaton के बराबर होती है, इसलिए प्रोग्राम द्वारा कुछ नियमित अभिव्यक्ति सीखना संभव है। Kearns and Valiant कुछ मामलों को दिखाएं जहां एक सीमित automaton सीखना संभव नहीं है। एक संबंधित समस्या learning hidden Markov Models है, जो संभाव्य ऑटोमाटा हैं जो वर्ण अनुक्रम का वर्णन कर सकती हैं। ध्यान दें कि प्रोग्रामिंग भाषाओं में उपयोग किए जाने वाले अधिकांश आधुनिक "नियमित अभिव्यक्ति" नियमित भाषाओं की तुलना में वास्तव में मजबूत होते हैं, और इसलिए कभी-कभी सीखना कठिन होता है।

Answer 2

आप इस साइट के साथ एक सा खेलने के लिए चाहते हो सकता है, यह काफी अच्छा है और लगता है कि यह क्या आप के बारे में बात कर रहे हैं करने के लिए कुछ ऐसा ही: मैं http://txt2re.com

Answer 3

मानना ​​है कि शब्द "प्रेरण" है। आप एक नियमित व्याकरण प्रेरित करना चाहते हैं।

मुझे नहीं लगता कि यह उदाहरणों (सकारात्मक या नकारात्मक) के सीमित सेट के साथ संभव है। लेकिन, अगर मैं सही ढंग से याद करता हूं, तो यह किया जा सकता है यदि ओरेकल है जिसे परामर्श दिया जा सकता है। (मूल रूप से आपको प्रोग्राम को उपयोगकर्ता द्वारा हाँ/कोई प्रश्न पूछने की आवश्यकता नहीं होगी।)

Answer 4

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

Answer 5

हां, यह निश्चित रूप से "संभव" है; यहाँ छद्म कोड है:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>) 
{ 
    if HasIntersection(<listOfPosExamples>, <listOfNegExamples>) 
    return <IntersectionError> 

    string regex = ""; 
    foreach(string example in <listOfPosExamples>) 
    { 
     if(regex != "") 
     { 
     regex += "|"; 
     } 
     regex += DoRegexEscaping(example); 
    } 
    regex = "^(" + regex + ")$"; 

    // Ignore <listOfNegExamples>; they're excluded by definition 

    return regex; 
} 

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

मुझे लगता है कि असली चुनौती उन सभी उदाहरणों से मेल खाने वाले सबसे छोटे रेगेक्स को ढूंढना होगा, लेकिन फिर भी, उपयोगकर्ता को यह सुनिश्चित करने के लिए बहुत अच्छा इनपुट देना होगा कि परिणामी अभिव्यक्ति "सही" थी।

Answer 6

@ युवाल सही है। आप कम्प्यूटेशनल लर्निंग थ्योरी, या "अपरिवर्तनीय अनुमान" देख रहे हैं।"

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

इस परिभाषा के अनुसार, मैं बहुत यकीन है कि नियमित रूप से भाषाओं learnable हैं हूँ। अन्य परिभाषाओं से, नहीं इतना ...

Answer 7

कोई कंप्यूटर कार्यक्रम एम वैध मैचों की सूची में आधारित पर आधारित एक सार्थक नियमित अभिव्यक्ति उत्पन्न करने में सक्षम होगा। मुझे आपको दिखाने दो क्यों।

मान लीजिए आप उदाहरण देते हैं 111111 और 999999, कंप्यूटर उत्पन्न करनी चाहिए:

1. एक रेगुलर एक्सप्रेशन मिलान का वास्तव में उन दो उदाहरण: (111111|999999)
2. 6 समान अंक (\d)\1{5}
3. एक regex मिलान 6 मिलान एक regex वाले और नाइन [19]{6}
4. किसी भी 6 अंक \d{6}
5. से मेल खाने वाला एक रेगेक्स शब्द सीमाओं के साथ तीन से ऊपर, उदा। \b\d{6}\b
6. पहले तीन में से कोई भी, अंक से पहले या उसके बाद नहीं, उदा। (?<!\d)\d{6}(?!\d)

आप देख सकते हैं, वहाँ कई तरीके है जिसमें उदाहरण के लिए रेगुलर एक्सप्रेशन में सामान्यीकृत किया जा सकता है। कंप्यूटर के अनुमानित नियमित अभिव्यक्ति का निर्माण करने का एकमात्र तरीका आपको सभी संभावित मैचों की सूची की आवश्यकता है। फिर यह एक खोज पैटर्न उत्पन्न कर सकता है जो वास्तव में उन मैचों से मेल खाता है।

यदि आप सभी संभावित मैचों को सूचीबद्ध नहीं करना चाहते हैं, तो आपको उच्च-स्तरीय विवरण की आवश्यकता है। यही वह है जो नियमित अभिव्यक्तियों को प्रदान करने के लिए डिज़ाइन किया गया है। 6 अंकों की संख्याओं की लंबी सूची प्रदान करने के बजाय, आप प्रोग्राम को "किसी भी छः अंकों" से मेल खाने के लिए कहते हैं। नियमित अभिव्यक्ति वाक्यविन्यास में, यह \ d {6} बन जाता है।

नियमित अभिव्यक्ति के रूप में लचीला होने वाला उच्च-स्तरीय विवरण प्रदान करने की कोई भी विधि नियमित अभिव्यक्तियों के रूप में जटिल होगी। RegexBuddy जैसे सभी टूल्स उच्च स्तर के विवरण को बनाने और परीक्षण करना आसान बना सकते हैं। सीधे terse नियमित अभिव्यक्ति वाक्यविन्यास का उपयोग करने के बजाय, RegexBuddy आपको सादे अंग्रेजी भवन ब्लॉक का उपयोग करने में सक्षम बनाता है। लेकिन यह आपके लिए उच्च स्तरीय विवरण नहीं बना सकता है, क्योंकि यह जादुई रूप से नहीं जान सकता है कि इसे आपके उदाहरणों को सामान्यीकृत करना चाहिए और जब यह नहीं होना चाहिए।

यह निश्चित रूप से एक उपकरण बनाना संभव है जो उपयोगकर्ता द्वारा नियमित अभिव्यक्ति उत्पन्न करने के लिए प्रदान किए गए दिशानिर्देशों के साथ नमूना पाठ का उपयोग करता है। इस तरह के एक उपकरण को डिजाइन करने में कठिन हिस्सा यह है कि उपयोगकर्ता को नियमित रूप से अभिव्यक्तियों से सीखने के लिए कठिन परिश्रम किए बिना, और सामान्य रेगेक्स नौकरियों या सरल नियमित अभिव्यक्तियों के लिए टूल को प्रतिबंधित किए बिना, मार्गदर्शिका की जानकारी के लिए उपयोगकर्ता से यह कैसे पूछता है।

Answer 8

प्रोलॉग के आधार पर इस तरह की समस्याओं के लिए समर्पित एक भाषा है। इसे progol कहा जाता है।

जैसा कि अन्य ने उल्लेख किया है, मूल विचार अनिवार्य शिक्षा है, जिसे अक्सर एआई सर्किल में आईएलपी (inductive logic programming) कहा जाता है।

दूसरा लिंक आईएलपी पर विकी आलेख है, जिसमें विषय के बारे में अधिक जानने में रुचि रखने पर बहुत उपयोगी स्रोत सामग्री शामिल है।

Answer 9

मैं गूगल और CiteSeer पर कुछ शोध किया और पाया है कि इन तकनीकों/कागजात:

• Language identification in the limit
• Probably approximately correct learning

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

ऐसा लगता है कि यह सैद्धांतिक स्तर पर भी एक मुश्किल समस्या है।

Answer 10

हां, यह संभव है, हम उदाहरणों (टेक्स्ट -> वांछित निष्कर्ष) से ​​रेगेक्स उत्पन्न कर सकते हैं। यह एक कामकाजी ऑनलाइन उपकरण है जो नौकरी करता है: http://regex.inginf.units.it/

रेगेक्स जनरेटर ++ ऑनलाइन उपकरण जीपी खोज एल्गोरिदम का उपयोग करके प्रदान किए गए उदाहरणों से एक रेगेक्स उत्पन्न करता है। जीपी एल्गोरिदम एक बहुविकल्पीय फिटनेस द्वारा संचालित होता है जो उच्च प्रदर्शन और सरल समाधान संरचना (ओकम के रेजर) की ओर जाता है। यह उपकरण मशीन लर्निंग लैब, ट्राएस्टे यूनिवर्सिस्टी (यूनिवर्सिटी डीग्गी स्टडी डी ट्राएस्टे) द्वारा एक डेमोस्ट्रेटिव एप्लिकेशन है। कृपया वीडियो ट्यूटोरियल here देखें।

यह एक शोध परियोजना है ताकि आप प्रयुक्त एल्गोरिदम here के बारे में पढ़ सकें।

देखें! यदि और केवल यदि दिए गए उदाहरणों में अच्छी तरह से समस्या का वर्णन :-)

उदाहरण से एक सार्थक regex/समाधान ढूँढना संभव है। इन उदाहरणों पर विचार करें जो निष्कर्षण कार्य का वर्णन करते हैं, हम विशेष आइटम कोड ढूंढ रहे हैं;

"The product code il 467-345A" -> "467-345A" 
"The item 789-345B is broken" -> "789-345B" 

एक (मानव) पुरुष, उदाहरण को देखते हुए, में अर्थात् कह सकते हैं: उदाहरण पाठ/निष्कर्षण जोड़े हैं "आइटम कोड \ घ ++ तरह बातें कर रहे हैं - 345 [ए बी]"

जब आइटम कोड अधिक अनुमोदित है लेकिन हमने अन्य उदाहरण प्रदान नहीं किए हैं, तो हमारे पास समस्या को अच्छी तरह से समझने के सबूत नहीं हैं। जब मानव उत्पन्न समाधान को लागू करने के \ घ ++ - 345 [ए बी] निम्न पाठ करने के लिए, यह विफल रहता है:

"On the back of the item there is a code: 966-347Z" 

आपको बेहतर वर्णन करने के लिए एक मैच है और क्या क्या में, अन्य उदाहरण देने की आवश्यकता नहीं है एक वांछित मैच: में अर्थात्:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z" 

फोन नंबर एक उत्पाद आईडी नहीं है, यह एक महत्वपूर्ण सबूत हो सकता है।