Recursive Program Synthesis from Sketches and Mixed-Quantifier Properties
यह शोध पत्र कैटालिस्ट (Cataclyst) प्रस्तुत करता है, जो एक नवीन काउंटर-एग्जांपल-गाइडेड एन्यूमरेटिव सिंथेसिस टूल है जो मिक्सड-क्वांटिफायर फर्स्ट-ऑर्डर लॉजिक प्रॉपर्टीज से रिकर्सिव प्रोग्राम्स को सफलतापूर्वक सिंथेसाइज करने के लिए स्केचिंग, सिंटैक्टिक कंस्ट्रेंट लर्निंग और प्रोफाइलैक्टिक प्रूनिंग का लाभ उठाता है, जो 60 में से 59 बेंचमार्क को हल करता है और मौजूदा दृष्टिकोणों से काफी बेहतर प्रदर्शन करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
एक ऐसी दुनिया की कल्पना करें जहाँ आप बिल्कुल वैसा ही वर्णन कर सकें जैसा आप चाहते हैं कि एक कंप्यूटर प्रोग्राम करे—जैसे "इस फ़ंक्शन को बिना किसी नंबर को हटाए एक लिस्ट को सॉर्ट करना चाहिए"—और एक मशीन तुरंत आपके लिए सटीक कोड लिख दे। इस सपने को प्रोग्राम सिंथेसिस (program synthesis) कहा जाता है, और यह कंप्यूटर विज्ञान और तर्कशास्त्र (logic) के मिलन बिंदु पर स्थित है। यह कैसे काम करता है, इसे समझने के लिए, इसे "मैड लिब्स" (Mad Libs) के एक बहुत ही सख्त खेल की तरह समझें। केवल खाली स्थानों में यादृच्छिक (random) शब्द भरने के बजाय, आपको एक आंशिक कहानी (जिसे स्केच/sketch कहा जाता है) दी जाती है जिसमें खाली स्थान होते हैं, और नियमों का एक सेट (जिसे गुणधर्म/properties कहा जाता है) होता है जिसका अंतिम कहानी को पालन करना चाहिए। कंप्यूटर का काम यह पता लगाना है कि उन खाली स्थानों में कौन से शब्द भरे जाएं ताकि कहानी समझ में आए और नियमों का पालन करे। पेचीदा हिस्सा यह है कि उन रिक्त स्थानों को भरने के संभावित तरीकों की संख्या अनंत है, जैसे कि समुद्र तट पर एक विशिष्ट रेत के कण को खोजने की कोशिश करना जो हर बार देखने पर मुड़ते ही बढ़ता जा रहा है। यदि कंप्यूटर एक-एक करके हर संभावना को आज़माने की कोशिश करता है, तो इसमें अनंत समय लग जाएगा। यही कारण है कि शोधकर्ता हमेशा खोज को कम करने (prune) के स्मार्ट तरीके खोजने की कोशिश करते हैं, जिससे कंप्यूटर को बुरे विचारों को आज़माने से पहले ही उन्हें छोड़ने में मदद मिले।
यह शोध पत्र इस पहेली को हल करने का एक नया, चतुर तरीका पेश करता है, विशेष रूप से उन प्रोग्रामों के लिए जो स्वयं को कॉल करते हैं (रिकर्सिव प्रोग्राम) और जिनमें "सभी के लिए" (for all) और "अस्तित्व है" (there exists) वाले जटिल नियम शामिल हैं। लेखकों, डेरेक एगॉल्फ और स्टावरोस ट्रिपकिस ने CATACLYST नामक एक टूल बनाया है जो एक बहुत ही स्मार्ट जासूस की तरह कार्य करता है। कोड के हर संभावित संयोजन का अंधाधुंध अनुमान लगाने के बजाय, CATACLYST काउंटरएग्जांपल-गाइडेड सिंथेसिस (counterexample-guided synthesis) नामक रणनीति का उपयोग करता है। यहाँ बताया गया है कि यह कैसे काम करता है: टूल एक संभावित प्रोग्राम चुनता है और जाँचता है कि क्या वह काम करता है। यदि प्रोग्राम विफल हो जाता है, तो टूल केवल यह नहीं कहता कि "गलत" और आगे बढ़ जाता; बल्कि, वह पूछता है, "यह क्यों विफल हुआ?" और फिर उस गलती से एक सबक सीखता है। वह एक नियम बनाता है जो कहता है, "दोबारा कभी भी यह विशिष्ट गलती न करें," जो प्रभावी रूप से खोज वृक्ष (search tree) की विशाल शाखाओं को काट देता है ताकि कंप्यूटर उन पर समय बर्बाद न करे।
शोध पत्र इस सीखने की प्रक्रिया को अत्यधिक कुशल बनाने के लिए दो मुख्य तरकीबें प्रस्तुत करता है। पहली है काउंटरएग्जेंडरलाइजेशन (counterexample generalization)। कल्पना कीजिए कि आप ब्लॉकों का एक टावर बनाने की कोशिश कर रहे हैं, लेकिन वह गिर जाता है क्योंकि आपने एक भारी ब्लॉक को एक डगमगाते हुए ब्लॉक पर रखा है। एक साधारण लर्नर केवल कह सकता है, "वहाँ वह भारी ब्लॉक मत रखो।" लेकिन एक स्मार्ट लर्नर कहता है, "इस विशिष्ट पैटर्न में किसी भी डगमगाते स्थान पर कोई भी भारी ब्लॉक न रखें।" टूल ऐसा इसलिए करता है क्योंकि वह विश्लेषण करता है कि एक प्रोग्राम क्यों विफल हुआ (जैसे कि एक कॉन्ट्रैक्ट उल्लंघन जहाँ एक फ़ंक्शन को गलत इनपुट दिया गया था, या एक प्रॉपर्टी उल्लंघन जहाँ आउटपुट गलत था) और समान विफलताओं को रोकने के लिए एक व्यापक नियम तैयार करता है। दूसरी तरकीब है प्रोफाइलैक्टिक प्रूनिंग (prophylactic pruning)। यह घर से बाहर निकलने से पहले अपना पहनावा चेक करने जैसा है। पूरा पहनावा पहनने, बाहर जाने और फिर यह महसूस करने के बजाय कि आपने गलत मोज़े पहने हैं, आप मोज़े पहनते समय ही उन्हें चेक करते हैं। टूल स्केच के छेदों को भरते समय ही नियमों की जाँच करता है, और यदि कोई आंशिक समाधान पहले से ही विफल होने वाला है, तो पूरे प्रोग्राम के बनने का इंतज़ार किए बिना तुरंत रुक जाता है।
इस दृष्टिकोण के परिणाम काफी प्रभावशाली हैं। लेखकों ने CATACLYST का परीक्षण 60 बेंचमार्क (परीक्षण समस्याओं का एक सेट) पर किया। जनरलाइजेशन और प्रोफाइलैक्टिक प्रूनिंग दोनों तरकीबों को चालू रखने के साथ, टूल ने 60 में से 59 बेंचमार्क को सफलतापूर्वक हल किया, और प्रत्येक को हल करने में 2 मिनट से अधिक का समय नहीं लगा। जब उन्होंने जनरलाइजेशन ट्रिक को बंद कर दिया, तो टूल ने कम समस्याएं हल कीं, और जब उन्होंने प्रोफाइलैक्टिक प्रूनिंग को बंद किया, तो उसने और भी कम समस्याएं हल कीं। यह सुझाव देता है कि दोनों तकनीकें टूल की सफलता के लिए महत्वपूर्ण हैं। शोध पत्र यह भी नोट करता है कि जबकि एक अन्य टूल मौजूद है जो समान जटिल नियमों को संभाल सकता है, वह यहाँ उपयोग की जाने वाली "स्केचिंग" पद्धति का समर्थन नहीं करता है, इसलिए सीधा मुकाबला संभव नहीं था, लेकिन नया टूल उन बेंचमार्क पर उस अन्य टूल से बेहतर प्रदर्शन करता है जिन्हें वह चला सकता था। अंततः, यह शोध पत्र दिखाता है कि गलतियों से सीखकर और त्रुटियों को जल्दी पहचानकर, हम कंप्यूटर को पहले की तुलना में बहुत तेज़ी से जटिल, आत्म-सुधार करने वाला कोड लिखना सिखा सकते हैं।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।