एक क्षेत्र को इलाकों में बांटना

एक बड़े प्रश्न को इलाकों में तोड़ना

जब कोई क्षेत्र सीधे खोजने के लिए बहुत बड़ा हो, तो आप उसे partition (खंडित) करते हैं: इसे गैर-ओवरलैपिंग (non-overlapping) इलाकों में बांटते हैं जो मिलकर पूरे क्षेत्र को कवर करते हैं। एक उप-प्रश्न का उत्तर देने का मतलब है एक इलाका चुनना और बाकी को नज़रअंदाज करना।

मान लीजिए प्रश्न यह है: "पिछले तिमाही में राजस्व (revenue) क्यों गिरा?" उत्तर-क्षेत्र बहुत विशाल है। इसे खंडित करें: (a) ग्राहकों की संख्या में कमी, (b) वही ग्राहक कम खर्च कर रहे हैं, (c) मूल्य निर्धारण या बिलिंग में बदलाव, (d) डेटा त्रुटि। ये चारों इलाके पूरे क्षेत्र को कवर करते हैं और एक-दूसरे के साथ ओवरलैप नहीं करते हैं। प्रत्येक एक छोटा प्रश्न है जिसे आप अलग से हल कर सकते हैं।

एक अच्छे विभाजन (partition) में ज्यामिति से सीखे गए दो गुण होते हैं: क्षेत्र पूरे स्थान को ढकते हैं (कुछ भी छूटता नहीं है) और वे अपरिवर्तनीय (disjoint) होते हैं (कुछ भी दो बार गिना नहीं जाता है)। यदि स्थान का कोई हिस्सा छूट जाता है, तो वास्तविक उत्तर उस खाली जगह में छुप सकता है। यदि क्षेत्र एक-दूसरे के ऊपर आते हैं, तो आप उसी जगह को दो बार खोजने में प्रयास बर्बाद करते हैं।

प्रत्येक उप-प्रश्न आपको एक क्षेत्र तक सीमित करता है। इसे हल करें, और आप उस क्षेत्र के बाहर की सभी चीज़ें हटा देते हैं: खोज का एक बड़ा, सस्ता (cheap) कमी।

एक साफ-सुथरा विभाजन

एक शहर पूछता है: "आपातकालीन प्रतिक्रिया समय (emergency response times) क्यों बढ़ रहे हैं?"

एक विश्लेषक इसे इस प्रकार विभाजित करने का प्रस्ताव रखता है: (a) दल तक पहुँचने में कॉल को अधिक समय लगता है, (b) एक बार भेजे जाने के बाद दल के पहुँचने में अधिक समय लगता है, और (c) दल को काम पूरा करने और खाली होने में अधिक समय लगता है।

हर आवश्यकता स्थान को काटती है

प्रतिबंध के रूप में आधा-तल (Half-Planes)

उत्तर-स्थान (answer space) को एक समतल तल (flat plane) की तरह देखें, जहाँ हर बिंदु एक संभावित उत्तर है। एक प्रतिबंध (constraint) एक आवश्यकता है, और हर आवश्यकता तल पर एक रेखा खींचती है और केवल एक पक्ष को ही रखती है। ज्यामिति में, वह रखा गया पक्ष एक आधा-तल (half-plane) कहलाता है।

"पंद्रह डॉलर से कम" एक रेखा है; सस्ती ओर को रखें। "चलने की दूरी के भीतर" दूसरी रेखा है; पास की ओर को रखें। "अभी खुला है" तीसरी है। जो भी आवश्यकता आप जोड़ते हैं, वह एक और कट (cut) है।

वह उत्तर जो हर आवश्यकता को पूरा करता है, सभी रखे गए पक्षों के प्रतिच्छेदन (intersection) में स्थित होता है। पर्याप्त आधे-तलों का प्रतिच्छेदन करने पर आपको एक छोटा सा सीमित क्षेत्र (bounded region) मिलता है: एक व्यवस्थित क्षेत्र जिसके अंदर एक सही उत्तर होता है।

दो विफलता मोड

अनुपयुक्त-प्रतिबंधित (कट बहुत कम): क्षेत्र असीमित रह जाता है। यह अनंतता की ओर बढ़ जाता है, इसलिए असीमित संख्या में अस्पष्ट उत्तर "फिट" हो जाते हैं। "मुझे एक अच्छा विचार दीजिए" असीमित है। आपको नॉइज़ मिलती है क्योंकि कुछ भी बाहर नहीं रखा गया था।

अति-प्रतिबंधित (बहुत अधिक, या विरोधाभासी, कट): क्षेत्र खाली हो जाता है। आधा-तल (half-planes) का कोई सामान्य बिंदु नहीं है, इसलिए कोई उत्तर बिल्कुल फिट नहीं होता। "एक संख्या जो सम और विषम दोनों हो" स्पेस को कुछ भी नहीं छोड़ता।

एक अच्छी तरह से निर्मित प्रश्न इन दोनों के बीच में होता है: क्षेत्र को सीमित करने के लिए पर्याप्त प्रतिबंध, इतने अधिक नहीं कि वे विरोधाभास पैदा करें और उसे खाली कर दें।

सीमित, असीमित, खाली

एक मैनेजर एक डिज़ाइनर से "एक लोगो" मांगता है। बाद में वे "एक लोगो" मांगते हैं जो एक अक्षर हो, एक रंग में हो, 16 पिक्सल पर काम करे, & साथ ही कम से कम चार रंगों का उपयोग करे।

सर्वोत्तम कटौती स्थान को आधा करती है

द्विद्वार खोज (Binary Search): हर हाँ/नहीं स्थान को आधा कर देती है

कुछ सवाल हाँ/नहीं के होते हैं। ज्यामितीय रूप से, एक हाँ/नहीं सवाल एक रेखा खींचता है & बताता है कि उत्तर किस ओर है: यह एक ही चाल में पूरा क्षेत्र हटा देता है।

सबसे अच्छा हाँ/नहीं प्रश्न वह है जो स्थान को दो बराबर भागों में बाँटता है, क्योंकि तब जो भी उत्तर आपको मिले, आपने ठीक आधी शेष संभावनाएँ हटा दी हैं। बार-बार "क्या यह ऊपरी आधा हिस्सा में है?" पूछने पर स्थान ज्यामितीय रूप से तेजी से सिकुड़ता है।

यह बाइनरी सर्च है। N उम्मीदवारों से शुरू करें। एक अच्छे प्रश्न के बाद, N/2 शेष रहते हैं। दो के बाद, N/4। k प्रश्नों के बाद, N / 2^k। तब आप समाप्त हो जाते हैं जब एक उम्मीदवार शेष रहता है, इसलिए आपको 2^k कम से कम N होने वाले सबसे छोटे k की आवश्यकता होती है।

वह सबसे छोटा k log2(N) का ceiling है। एक हज़ार उम्मीदवारों के लिए: 2^9 = 512 (पर्याप्त नहीं) & 2^10 = 1024 (पर्याप्त), इसलिए log2(1000) लगभग 9.97 है & आपको 10 प्रश्नों की आवश्यकता है। एक अरब उम्मीदवार? एक अरब का log2 लगभग 30 है। आधा करना इतना शक्तिशाली है कि एक हज़ार से एक अरब तक जाने में केवल लगभग बीस प्रश्नों का अंतर आता है।

प्रश्न पूछने का पाठ: एक तीखा हाँ/नहीं प्रश्न तब सबसे अधिक मूल्यवान होता है जब यह शेष स्थान को समान रूप से बाँटता है। एक असंतुलित प्रश्न जो केवल एक छोटी सी संभावना को हटाता है, वह मोड़ (turn) बर्बाद करता है।

खोज की गारंटी

आप एक अनुमान खेल खेल रहे हैं। कोई 1 से 1000 तक एक पूर्ण संख्या चुनता है। आप केवल हाँ/नहीं प्रश्न पूछ सकते हैं, & आप आदर्श रूप से खेलते हैं (हर प्रश्न शेष उम्मीदवारों को जितना संभव हो उतना समान रूप से बाँटता है)।

जब जवाब सस्ते हों, तो कटौतियाँ (Cuts) कीमती होती हैं

सवाल अब काम है

चारों टुकड़ों को एक साथ जोड़ें। एक सवाल एक स्थान खोलता है। विभाजन (Decomposition) उसे बाँटता है। प्रतिबंध (Constraints) उसे एक सीमित संभव क्षेत्र में काट देते हैं। अच्छे हाँ/नहीं सवाल उसे आधा कर देते हैं। इनमें से हर एक खोज को सिकोड़ने (shrinking the search) का एक कदम है, इससे पहले कि आप जवाब खोजें।

इतिहास के अधिकांश हिस्से में जवाब महंगा हिस्सा था। आपने एक विशेषज्ञ को भुगतान किया, प्रयोग किया, या अभिलेखागार (archive) में खोज की। इसलिए हम उन लोगों को महत्व देते थे जो जवाब दे सकें।

वह संतुलन उलट गया है। स्वचालित प्रणालियाँ अब लगभग निःशुल्क रूप से हज़ारों संभाव्य उत्तर उत्पन्न करती हैं। जब उत्तर सस्ते और प्रचुर हों, तो एक और उत्तर उत्पन्न करना कोई उपलब्धि नहीं है। जो दुर्लभ बनी है, वह यह जानना है कि कौन सा उत्तर पाने लायक है: और यह एक उत्तर-उत्पादन कौशल नहीं, बल्कि एक प्रश्न-पूछने का कौशल है।

ज्यामिति के संदर्भ में: एक मशीन खुशी-खुशी आपको स्थान (space) में कोई भी बिंदु दे देगी। आप जो मूल्य जोड़ते हैं, वह यह है कि आप वे प्रतिबंध (constraints) खींचते हैं जो स्थान को उस एक क्षेत्र तक सीमित कर देते हैं जहाँ एक अच्छा उत्तर अवश्य होना चाहिए। यदि आप कम प्रतिबंध लगाते हैं, तो आप संभाव्य शोर (plausible noise) में डूब जाएंगे (एक असीमित क्षेत्र)। यदि आप अधिक प्रतिबंध लगाते हैं, तो आपको कुछ नहीं मिलेगा (एक खाली क्षेत्र)। वे कटौतियाँ (cuts) लगाना जो क्षेत्र को ठीक उसी आकार तक सीमित करे, वह दुर्लभ, मानवीय कौशल है।

तो लाभ (leverage) "एक उत्तर प्राप्त करना" नहीं है। यह "वे प्रतिबंध लगाना" है जो उत्तर-स्थान को इतना छोटा कर दे कि उसमें कोई भी बिंदु पाने लायक हो।

मूल्य कहाँ खिसका

एक विश्लेषक अब लगभग शून्य लागत पर मिनटों में सौ ड्राफ्ट रणनीतियाँ उत्पन्न कर सकता है।

प्रश्नों की ज्यामिति: सारांश

आपने क्या सीखा

एक प्रश्न एकमात्र उत्तर की मांग नहीं है। यह संभावित उत्तरों का एक स्थान (space) है, और पूछने की कला उस स्थान को संकुचित करने की कला है:

- खोज स्थान (Search space): हर प्रश्न संभावित उत्तरों के एक समुच्चय को खोलता है। एक तीक्ष्ण प्रश्न एक छोटा समुच्चय खोलता है; एक अस्पष्ट प्रश्न एक विशाल समुच्चय खोलता है जिसमें आपको भटकना पड़ता है।

- विभाजन के रूप में विभाजित करना (Decomposition as partitioning): एक बड़े स्थान को ऐसे क्षेत्रों में बाँटें जो बिना किसी ओवरलैप के उसे पूरी तरह ढकें; प्रत्येक उप-प्रश्न आपको एक क्षेत्र तक सीमित करता है।

- सीमाओं के रूप में प्रतिबंध (Constraints as boundaries): हर आवश्यकता एक अर्ध-तल (half-plane) है; उत्तर उनके प्रतिच्छेदन (intersection) में निहित होता है। बहुत कम कटौतियाँ एक असीमित क्षेत्र छोड़ती हैं (अनंत अस्पष्ट उत्तर); विरोधाभासी कटौतियाँ एक खाली क्षेत्र छोड़ती हैं (कुछ भी फिट नहीं होता)।

- आधा करके सीमांकन: एक अच्छी तरह से चुनी गई हाँ/नहीं प्रश्न स्थान को दो भागों में बांट देती है। 1 से 1000 के बीच एक संख्या को पकड़ने के लिए ceil(log2(1000)) = 10 प्रश्न लगते हैं; एक अरब के लिए केवल लगभग 30।

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