सचिव समस्या: Difference between revisions

From Vigyanwiki
No edit summary
 
(12 intermediate revisions by 3 users not shown)
Line 90: Line 90:
| 0.406
| 0.406
|}
|}
शास्त्रीय सचिव समस्या में सर्वश्रेष्ठ आवेदक के चयन की संभावना की ओर अभिसरण होता है <math>1/e\approx 0.368</math>.
शास्त्रीय सचिव समस्या में सर्वश्रेष्ठ आवेदक के चयन की संभावना की ओर अभिसरण होता है। <math>1/e\approx 0.368</math>.


== वैकल्पिक समाधान ==
== वैकल्पिक समाधान ==
इस समस्या और कई संशोधनों को ऑड्स एल्गोरिथम द्वारा सीधे तरीके से (इष्टतमता के प्रमाण सहित) हल किया जा सकता है, जिसमें अन्य अनुप्रयोग भी हैं। इस एल्गोरिथम द्वारा हल की जा सकने वाली सेक्रेटरी समस्या के लिए संशोधनों में आवेदकों की यादृच्छिक उपलब्धता, आवेदकों के लिए अधिक सामान्य परिकल्पनाएं शामिल हैं जो निर्णयकर्ता के लिए रुचिकर हों, आवेदकों के लिए समूह साक्षात्कार, साथ ही आवेदकों की यादृच्छिक संख्या के लिए कुछ मॉडल।{{Citation needed|date=May 2022}}
इस समस्या और कई संशोधनों को कठिनाई प्रारूप द्वारा सीधे तरीके से इष्टतमता के प्रमाण सहित हल किया जा सकता है जिसमें अन्य अनुप्रयोग भी हैं इस प्रारूप द्वारा हल की जा सकने वाली सचिव समस्या के लिए संशोधनों में आवेदकों की यादृच्छिक उपलब्धता आवेदकों के लिए अधिक सामाशा परिकल्पनाएं सम्मिलित हैं जो निर्णयकर्ता के लिए रुचिकर हों आवेदकों के लिए समूह साक्षात्कार साथ ही आवेदकों की यादृच्छिक संख्या के लिए कुछ प्रयुक्त आवेदक हैं।{{Citation needed|date=May 2022}}


== सीमाएं ==
== सीमाएं ==
सचिव समस्या का समाधान केवल तभी सार्थक है जब यह मानना ​​उचित हो कि आवेदकों को नियोजित निर्णय रणनीति का कोई ज्ञान नहीं है, क्योंकि शुरुआती आवेदकों के पास कोई मौका नहीं है और अन्यथा दिखाई नहीं दे सकता है।
सचिव समस्या का समाधान केवल तभी सार्थक है जब आवेदकों को नियोजित निर्णय रणनीति का कोई ज्ञान न हो क्योंकि शुरुआती आवेदकों के पास कोई मौका नहीं है और यह दिखाई भी नहीं दे सकता है।


शास्त्रीय सचिव समस्या के समाधान के अनुप्रयोगों के लिए एक महत्वपूर्ण दोष आवेदकों की संख्या है <math> n </math> पहले से पता होना चाहिए, जो शायद ही कभी होता है। इस समस्या को दूर करने का एक तरीका यह मान लेना है कि आवेदकों की संख्या एक यादृच्छिक चर है <math>N </math> के ज्ञात वितरण के साथ  <math>P(N=k)_{k=1,2,\cdots} </math> (प्रेसमैन और सोनिन, 1972)। हालांकि, इस मॉडल के लिए, इष्टतम समाधान सामान्य रूप से अधिक कठिन है। इसके अलावा, इष्टतम सफलता की संभावना अब 1/e के आसपास नहीं है, लेकिन आमतौर पर कम है। इसे आवेदकों की संख्या न जानने की कीमत चुकाने के संदर्भ में समझा जा सकता है। हालांकि, इस मॉडल में कीमत ज्यादा है। के वितरण की पसंद पर निर्भर करता है <math>N</math>इष्टतम जीत संभावना शून्य तक पहुंच सकती है। इस नई समस्या से निपटने के तरीकों की तलाश में एक नए मॉडल का नेतृत्व किया गया जो तथाकथित 1/ई-कानून को सर्वोत्तम विकल्प प्रदान करता है।
शास्त्रीय सचिव समस्या के समाधान के अनुप्रयोगों के लिए एक महत्वपूर्ण दोष आवेदकों की संख्या <math> n </math> है जो इस समस्या को दूर करने का तरीका यह मान लेता है कि आवेदकों की संख्या एक यादृच्छिक चर है <math>N </math> के ज्ञात वितरण के साथ  <math>P(N=k)_{k=1,2,\cdots} </math> प्रेसमैन और सोनिन 1972 में इस प्रारूप के लिए इष्टतम समाधान सामान्य रूप से अधिक कठिन है इसके सफलता की संभावना अब 1/e के आसपास नहीं है लेकिन आमतौर पर कम है इसे आवेदकों की संख्या न जानने की कीमत चुकाने के संदर्भ में समझा जा सकता है जबकि इस प्रारूप में कीमत ज्यादा है यह इसके वितरण की पसंद पर निर्भर करता है <math>N</math>इष्टतम जीत संभावना शून्य तक पहुंच सकती है इस नई समस्या से निपटने के तरीकों की तलाश में एक नए प्रारूप का नेतृत्व किया गया जो तथाकथित 1/ई-कानून को सर्वोत्तम विकल्प प्रदान करता है।


==1/सर्वश्रेष्ठ विकल्प का ई-कानून==
==1/सर्वश्रेष्ठ विकल्प का ई-कानून==
मॉडल का सार इस विचार पर आधारित है कि जीवन अनुक्रमिक है और वास्तविक दुनिया की समस्याएं वास्तविक समय में उत्पन्न होती हैं। इसके अलावा, ऐसे समय का अनुमान लगाना आसान होता है जिसमें विशिष्ट घटनाओं (आवेदकों के आगमन) को अधिक बार होना चाहिए (यदि वे करते हैं) तो होने वाली विशिष्ट घटनाओं की संख्या के वितरण का अनुमान लगाने के बजाय। इस विचार ने निम्नलिखित दृष्टिकोण को जन्म दिया, तथाकथित एकीकृत दृष्टिकोण (1984):
प्रारूप का सार इस विचार पर आधारित है कि जीवन अनुक्रमिक है और वास्तविक दुनिया की समस्याएं वास्तविक समय में उत्पन्न होती हैं इसके अलावा ऐसे समय का अनुमान लगाना आसान होता है जिसमें विशिष्ट घटनाओं आवेदकों के आगमन को अधिक बार होना चाहिए यदि वे ऐसा करते हैं तो होने वाली विशिष्ट घटनाओं की संख्या के वितरण का अनुमान लगाने के जगह इस विचार ने निम्नलिखित दृष्टिकोण को जन्म दिया तथाकथित एकीकृत दृष्टिकोण 1984 में लागू हुआ।


मॉडल को इस प्रकार परिभाषित किया गया है: एक आवेदक को कुछ समय अंतराल पर चुना जाना चाहिए <math>[0,T]</math> किसी अनजान नंबर से <math> N</math> रैंक करने योग्य आवेदकों की। लक्ष्य इस परिकल्पना के तहत केवल सर्वश्रेष्ठ का चयन करने की संभावना को अधिकतम करना है कि विभिन्न रैंकों के सभी आगमन ऑर्डर समान रूप से होने की संभावना है। मान लीजिए कि सभी आवेदकों का आगमन समय घनत्व समान है, लेकिन एक-दूसरे से स्वतंत्र है <math>f</math> पर <math>[0,T]</math> और जाने  <math>F</math> इसी आगमन समय वितरण फ़ंक्शन को निरूपित करें, अर्थात
प्रारूप को इस प्रकार परिभाषित किया गया है कि एक आवेदक को कुछ समय अंतराल पर चुना जाना चाहिए <math>[0,T]</math> किसी अनजान नंबर से <math> N</math> पद करने योग्य आवेदकों का लक्ष्य इस परिकल्पना के तहत केवल सर्वश्रेष्ठ का चयन करने की संभावना को अधिकतम करना है किसी विभिन्न पदों के सभी आगमन आदेशित समान रूप से होने की संभावना है मान लीजिए कि सभी आवेदकों का आगमन समय घनत्व समान है लेकिन एक-दूसरे से स्वतंत्र है <math>f</math> पर <math>[0,T]</math> और जाने  <math>F</math> इसी आगमन समय वितरण कार्यक्रम को निरूपित करें अर्थात्


: <math>F(t) = \int_{0}^{t} f(s)ds </math>, <math>\, 0\le t\le T</math>.
: <math>F(t) = \int_{0}^{t} f(s)ds </math>, <math>\, 0\le t\le T</math>.


होने देना <math>\tau</math> ऐसा हो कि <math> F(\tau)=1/e.</math> सभी आवेदकों को समय-समय पर प्रतीक्षा करने और निरीक्षण करने की रणनीति पर विचार करें <math>\tau </math> और यदि संभव हो तो समय के बाद पहले उम्मीदवार का चयन करना <math>\tau </math> जो पिछले सभी से बेहतर है। फिर इस रणनीति, जिसे 1/ई-रणनीति कहा जाता है, में निम्नलिखित गुण हैं:
<math>\tau</math> ऐसा हो कि <math> F(\tau)=1/e.</math> सभी आवेदक समय-समय पर प्रतीक्षा करने और निरीक्षण करने की रणनीति पर विचार करें <math>\tau </math> यदि संभव हो तो समय के बाद पहले उम्मीदवार का चयन करना <math>\tau </math> जो पिछले सभी से बेहतर है फिर इस रणनीति को जिसे 1/ई-रणनीति कहा जाता है इसमें निम्नलिखित गुण हैं


1/ई-रणनीति
1/ई-रणनीति


:(i) सभी के लिए पैदावार <math>N</math> कम से कम 1/e की सफलता की संभावना,
:(i) सभी के लिए पैदावार <math>N</math> कम से कम 1/e की सफलता की संभावना।


: (ii) चयनकर्ता के लिए एक न्यूनतम-इष्टतम रणनीति है जो नहीं जानता है <math>N</math>,
: (ii) चयनकर्ता के लिए एक न्यूनतम-इष्टतम रणनीति है जो <math>N</math>को नहीं जानता है।


:(iii) चयन करता है, यदि कम से कम एक आवेदक है, बिल्कुल 1/e संभावना के साथ कोई नहीं।
:(iii) चयन करता है यदि कम से कम एक आवेदक हो जो 1/e संभावना के साथ कोई न हो।


एफ. थॉमस ब्रस द्वारा 1984 में सिद्ध किया गया पहला/ई-कानून एक आश्चर्य के रूप में सामने आया। कारण यह था कि अज्ञात के लिए एक मॉडल में पहुंच से बाहर होने से पहले लगभग 1/e के मान पर विचार किया गया था <math> N </math>, जबकि यह मान 1/e अब सफलता की संभावना के लिए एक निचली सीमा के रूप में प्राप्त किया गया था, और यह यकीनन बहुत कमजोर परिकल्पनाओं वाले मॉडल में है (उदाहरण के लिए गणित देखें। समीक्षाएं 85:m)।
एफ. थॉमस ब्रस द्वारा 1984 में सिद्ध किया गया पहला/ई-कानून एक आश्चर्य के रूप में सामने आया कारण यह था कि अज्ञात के लिए एक प्रारूप में पहुंच से बाहर होने से पहले लगभग 1/e के मान पर विचार किया गया था <math> N </math> जबकि यह मान 1/e अब सफलता की संभावना के लिए एक निचली सीमा के रूप में प्राप्त किया गया था और यह यकीनन बहुत कमजोर परिकल्पनाओं वाले प्रारूप में है उदाहरण के लिए समीक्षाएं 85: मिनट


हालाँकि, कई अन्य रणनीतियाँ हैं जो (i) और (ii) प्राप्त करती हैं और, इसके अलावा, 1/ई-रणनीति की तुलना में सख्ती से बेहतर प्रदर्शन करती हैं।
जबकि कई अन्य रणनीतियाँ हैं जो (i) और (ii) प्राप्त करती हैं और इसके अलावा 1/ई-रणनीति की तुलना में सख्ती से बेहतर प्रदर्शन करती हैं एक साथ सभी के लिए <math>N</math>> 2। एक सरल उदाहरण वह रणनीति है जो समय के बाद या पहले अपेक्षाकृत सर्वश्रेष्ठ उम्मीद का चयन करती है यदि संभव हो जबकि <math>\tau </math> कम से कम एक आवेदक इस समय से पहले पहुंचे और समय के बाद दूसरे अपेक्षाकृत सर्वश्रेष्ठ उम्मीदवार का चयन करें {{sfn|Gnedin|2021}}
एक साथ सभी के लिए <math>N</math>> 2। एक सरल उदाहरण वह रणनीति है जो समय के बाद पहले अपेक्षाकृत सर्वश्रेष्ठ उम्मीदवार का चयन करती है (यदि संभव हो)। <math>\tau </math> बशर्ते कि कम से कम एक आवेदक इस समय से पहले पहुंचे, और अन्यथा समय के बाद दूसरे अपेक्षाकृत सर्वश्रेष्ठ उम्मीदवार का चयन करें (यदि संभव हो)। <math>\tau </math>.{{sfn|Gnedin|2021}}
   
   
संख्या 1/ई की समान भूमिका के कारण 1/ई-कानून कभी-कभी ऊपर वर्णित शास्त्रीय सचिव समस्या के समाधान के साथ भ्रमित हो जाता है। हालांकि, 1/ई-कानून में, यह भूमिका अधिक सामान्य है। परिणाम भी मजबूत है, क्योंकि यह अज्ञात संख्या में आवेदकों के लिए है और चूंकि आगमन समय वितरण एफ पर आधारित मॉडल अनुप्रयोगों के लिए अधिक ट्रैक्टेबल है।
संख्या 1/ई की समान भूमिका के कारण 1/ई-कानून कभी-कभी ऊपर वर्णित शास्त्रीय सचिव समस्या के समाधान के साथ भ्रमित हो जाता है जबकि 1/ई-कानून में यह भूमिका अधिक सामान्य है परिणाम भी मजबूत है क्योंकि यह अज्ञात संख्या में आवेदकों के लिए है और चूंकि आगमन समय वितरण एफ पर आधारित प्रारूप अनुप्रयोगों के लिए अधिक हैं।


== गोगोल का खेल ==
== गोगोल का खेल ==
थॉमस एस. फर्ग्यूसन के अनुसार, सेक्रेटरी प्रॉब्लम पहली बार प्रिंट में दिखाई दी, जब इसे [[मार्टिन गार्डनर]] ने अपने फरवरी 1960 में [[ अमेरिकी वैज्ञानिक ]] में [[गणितीय खेल स्तंभ]] में चित्रित किया।{{r|TomFer89}} यहां बताया गया है कि गार्डनर ने इसे कैसे तैयार किया: किसी को कागज की जितनी चाहें उतनी पर्चियां लेने के लिए कहें, और प्रत्येक पर्ची पर एक अलग सकारात्मक संख्या लिखें। संख्याएँ 1 के छोटे अंशों से लेकर एक गोगोल के आकार की संख्या (1 के बाद सौ शून्य) या इससे भी बड़ी हो सकती हैं। इन पर्चियों को उल्टा कर दिया जाता है और एक मेज के ऊपर से फेर दिया जाता है। एक समय में आप स्लिप्स को उल्टा कर देते हैं। लक्ष्य यह है कि जब आप उस संख्या तक पहुंचें जिसे आप श्रृंखला में सबसे बड़ा मानते हैं तो मुड़ना बंद कर दें। आप वापस नहीं जा सकते हैं और पहले से मुड़ी हुई पर्ची नहीं उठा सकते हैं। यदि आप सभी पर्चियों को पलट देते हैं, तो निश्चित रूप से आपको अंतिम मुड़ी हुई पर्चियों को चुनना चाहिए।{{sfn|Gardner|1966}}
थॉमस एस. फर्ग्यूसन के अनुसार सचिव समस्या पहली बार छपाई में दिखाई दी जब इसे [[मार्टिन गार्डनर]] ने अपने फरवरी 1960 में [[ अमेरिकी वैज्ञानिक ]]में [[गणितीय खेल स्तंभ]] में चित्रित किया {{r|TomFer89}} यहां बताया गया है कि गार्डनर ने इसे कैसे तैयार किया किसी को कागज की जितनी चाहें उतनी पर्चियां लेने के लिए कहें और प्रत्येक पर्ची पर एक अलग सकारात्मक संख्या लिखें संख्याएँ 1 के छोटे अंशों से लेकर एक गोगोल के आकार की संख्या 1 के बाद सौ शून्य या इससे भी बड़ी हो सकती हैं इन पर्चियों को उल्टा कर दिया जाता है और एक मेज के ऊपर से फेर दिया जाता है एक समय में आप फिसलकर उल्टा कर देते हैं लक्ष्य यह है कि जब आप उस संख्या तक पहुंचें जिसे आप श्रृंखला में सबसे बड़ा मानते हैं तो मुड़ना बंद कर दें आप वापस नहीं जा सकते हैं और पहले से मुड़ी हुई पर्ची नहीं उठा सकते हैं यदि आप सभी पर्चियों को पलट देते हैं तो निश्चित रूप से आपको अंतिम मुड़ी हुई पर्चियों को चुनना चाहिए।{{sfn|Gardner|1966}}


लेख में सचिव समस्या का समाधान किसने किया? फर्ग्यूसन ने बताया कि सेक्रेटरी की समस्या अनसुलझी रही, जैसा कि एम. गार्डनर ने कहा था, जो दो विरोधी खिलाड़ियों के साथ दो-व्यक्ति शून्य-राशि के खेल के रूप में है।{{r|TomFer89}} इस खेल में ऐलिस, सूचित खिलाड़ी, गुप्त रूप से अलग-अलग नंबर लिखता है <math>n</math> पत्ते। बॉब, रोकने वाला खिलाड़ी, वास्तविक मूल्यों को देखता है और जब भी वह चाहता है तो कार्ड को बदलना बंद कर सकता है, अगर आखिरी कार्ड बदल गया तो जीतना कुल अधिकतम संख्या है। बुनियादी सचिव की समस्या से अंतर यह है कि बॉब कार्डों पर लिखे वास्तविक मूल्यों का अवलोकन करता है, जिसका उपयोग वह अपनी निर्णय प्रक्रियाओं में कर सकता है। सचिव समस्या के कुछ संस्करणों में कार्ड पर संख्या आवेदकों के संख्यात्मक गुणों के अनुरूप होती है। संख्याओं का [[संयुक्त संभाव्यता वितरण]] ऐलिस के नियंत्रण में है।
लेख में सचिव समस्या का समाधान किसने किया फर्ग्यूसन ने बताया कि सचिव की समस्या अनसुलझी रही जैसा कि एम. गार्डनर ने कहा था जो दो विरोधी खिलाड़ियों के साथ दो-व्यक्ति शून्य-राशि के खेल के रूप में है {{r|TomFer89}} इस खेल में ऐलिस, सूचित खिलाड़ी, गुप्त रूप से अलग-अलग नंबर लिखता है <math>n</math> पत्ते बॉब, रोकने वाला खिलाड़ी, वास्तविक मूल्यों को देखता है और जब भी वह चाहता है तो कार्ड को बदलना बंद कर सकता है अगर आखिरी कार्ड बदल गया तो जीतना कुल अधिकतम संख्या है बुनियादी सचिव की समस्या से अंतर यह है कि बॉब कार्डों पर लिखे वास्तविक मूल्यों का अवलोकन करता है जिसका उपयोग वह अपनी निर्णय प्रक्रियाओं में कर सकता है सचिव समस्या के कुछ संस्करणों में कार्ड पर संख्या आवेदकों के संख्यात्मक गुणों के अनुरूप होती है संख्याओं का [[संयुक्त संभाव्यता वितरण]] ऐलिस के नियंत्रण में है।


बॉब उच्चतम संभव संभावना के साथ अधिकतम संख्या का अनुमान लगाना चाहता है, जबकि ऐलिस का लक्ष्य इस संभावना को यथासंभव कम रखना है। ऐलिस के लिए कुछ निश्चित वितरण से स्वतंत्र रूप से संख्याओं का नमूना लेना इष्टतम नहीं है, और वह कुछ आश्रित तरीके से यादृच्छिक संख्याओं को चुनकर बेहतर खेल सकती है। के लिए <math>n=2</math> ऐलिस की कोई न्यूनतम रणनीति नहीं है, जो थॉमस एम. कवर|टी के विरोधाभास से निकटता से संबंधित है। ढकना। लेकिन के लिए <math>n>2</math> खेल में एक समाधान है: ऐलिस यादृच्छिक संख्या (जो आश्रित यादृच्छिक चर हैं) को इस तरह से चुन सकता है कि बॉब सापेक्ष रैंकों के आधार पर शास्त्रीय रोक रणनीति का उपयोग करने से बेहतर नहीं खेल सकता।{{sfn|Gnedin|1994}}
बॉब उच्चतम संभव संभावना के साथ अधिकतम संख्या का अनुमान लगाना चाहता है जबकि ऐलिस का लक्ष्य इस संभावना को यथासंभव कम रखना है ऐलिस के लिए कुछ निश्चित वितरण से स्वतंत्र रूप से संख्याओं का नमूना लेना इष्टतम नहीं है और वह कुछ आश्रित तरीके से यादृच्छिक संख्याओं को चुनकर बेहतर खेल सकती है के लिए <math>n=2</math> ऐलिस की कोई न्यूनतम रणनीति नहीं है जो थॉमस एम. कवर टी के विरोधाभास से निकटता से संबंधित है  <math>n>2</math> खेल में एक समाधान है ऐलिस यादृच्छिक संख्या जो आश्रित यादृच्छिक चर हैं यह इस तरह से चुन सकता है कि बॉब सापेक्ष पदों के आधार पर शास्त्रीय रोक रणनीति का उपयोग करने से बेहतर नहीं खेल सकता।{{sfn|Gnedin|1994}}


== अनुमानित प्रदर्शन ==
== अनुमानित प्रदर्शन ==
Line 136: Line 135:
[[Image:SecretaryProblemHeuristicPlot.png|thumb|300px|right|तीन अनुमानों के लिए अपेक्षित सफलता की संभावनाएं।]]
[[Image:SecretaryProblemHeuristicPlot.png|thumb|300px|right|तीन अनुमानों के लिए अपेक्षित सफलता की संभावनाएं।]]


{{harvnb|Stein|Seale|Rapoport|2003}} ने कई मनोवैज्ञानिक रूप से प्रशंसनीय अनुमानों के लिए अपेक्षित सफलता की संभावनाएँ प्राप्त कीं जिन्हें सचिव समस्या में नियोजित किया जा सकता है। उन्होंने जिन ह्यूरिस्टिक्स की जांच की वे थे:
{{harvnb|Stein|Seale|Rapoport|2003}} ने कई मनोवैज्ञानिक रूप से प्रशंसनीय अनुमानों के लिए अपेक्षित सफलता की संभावनाएँ प्राप्त कीं जिन्हें सचिव समस्या में नियोजित किया जा सकता है उन्होंने ह्यूरिस्टिक्स की जांच की थी
* कटऑफ नियम (CR): पहले y आवेदकों में से किसी को भी स्वीकार न करें; इसके बाद, पहले सामना करने वाले उम्मीदवार (यानी, सापेक्ष रैंक 1 वाला आवेदक) का चयन करें। इस नियम में एक विशेष मामले के रूप में शास्त्रीय सचिव समस्या के लिए इष्टतम नीति है जिसके लिए y = r।
* कटऑफ नियम पहले y आवेदकों में से किसी को भी स्वीकार न करें इसके बाद पहले सामना करने वाले उम्मीदवार यानी सापेक्ष पद 1 वाला आवेदक का चयन करें इस नियम में एक विशेष स्थान के रूप में शास्त्रीय सचिव समस्या के लिए इष्टतम नीति है जिसके लिए y = r
*उम्मीदवार गणना नियम (सीसीआर): वाई-वें सामना करने वाले उम्मीदवार का चयन करें। ध्यान दें कि यह नियम आवश्यक रूप से किसी भी आवेदक को छोड़ नहीं देता है; यह केवल इस बात पर विचार करता है कि कितने उम्मीदवारों का अवलोकन किया गया है, यह नहीं कि आवेदक अनुक्रम में निर्णय निर्माता कितना गहरा है।
*उम्मीदवार गणना नियम सीसीआर वाई-वें सामना करने वाले उम्मीदवार का चयन करें ध्यान दें कि यह नियम आवश्यक रूप से किसी भी आवेदक को छोड़ नहीं देता है यह केवल इस बात पर विचार करता है कि कितने उम्मीदवारों का अवलोकन किया गया है यह नहीं कि आवेदक अनुक्रम में निर्णय निर्माता कितना गहरा है।
* लगातार गैर-उम्मीदवार नियम (एसएनसीआर): वाई गैर-उम्मीदवारों (यानी, संबंधित रैंक वाले आवेदक > 1) का अवलोकन करने के बाद सबसे पहले सामना करने वाले उम्मीदवार का चयन करें।
* लगातार गैर-उम्मीदवार नियम एसएनसीआर वाई गैर-उम्मीदवारों यानी संबंधित पद वाले आवेदक > 1 का अवलोकन करने के बाद सबसे पहले सामना करने वाले उम्मीदवार का चयन करें ।


प्रत्येक अनुमानी का एक एकल पैरामीटर y होता है। आंकड़ा (दाईं ओर दिखाया गया है) n = 80 के साथ समस्याओं के लिए y के एक समारोह के रूप में प्रत्येक अनुमानी के लिए अपेक्षित सफलता की संभावनाएं प्रदर्शित करता है।
अनुमानी का एक एकल पैरामीटर y होता है आंकड़ा दाईं ओर दिखाया गया है n = 80 के साथ समस्याओं के लिए y के एक समारोह के रूप में प्रत्येक अनुमानी के लिए अपेक्षित सफलता की संभावनाएं प्रदर्शित करता है।


== कार्डिनल पेऑफ वेरिएंट ==
== कार्डिनल पेऑफ वेरिएंट ==
एकल सर्वश्रेष्ठ आवेदक ढूँढना एक सख्त उद्देश्य की तरह लग सकता है। कोई कल्पना कर सकता है कि साक्षात्कारकर्ता एक कम-मूल्यवान आवेदक की तुलना में एक उच्च-मूल्यवान आवेदक को नियुक्त करेगा, और न केवल सर्वश्रेष्ठ प्राप्त करने के लिए चिंतित होगा। अर्थात्, साक्षात्कारकर्ता एक आवेदक का चयन करने से कुछ मूल्य प्राप्त करेगा जो आवश्यक रूप से सर्वोत्तम नहीं है, और व्युत्पन्न मूल्य चयनित के मूल्य के साथ बढ़ता है।
एकल सर्वश्रेष्ठ आवेदक ढूँढना एक सख्त उद्देश्य की तरह लग सकता है कोई कल्पना कर सकता है कि साक्षात्कारकर्ता एक कम-मूल्यवान आवेदक की तुलना में एक उच्च-मूल्यवान आवेदक को नियुक्त करेगा और न केवल सर्वश्रेष्ठ प्राप्त करने के लिए चिंतित होगा अर्थात् साक्षात्कारकर्ता एक आवेदक का चयन करने से कुछ मूल्य प्राप्त करेगा जो आवश्यक रूप से सर्वोत्तम नहीं है और व्युत्पन्न मूल्य चयनित के मूल्य के साथ बढ़ता है।


इस समस्या को मॉडल करने के लिए, मान लीजिए कि <math>n</math> आवेदकों के पास वास्तविक मूल्य हैं जो यादृच्छिक चर एक्स तैयार i.i.d हैं। [0, 1] पर एक [[समान वितरण (निरंतर)]] से। ऊपर वर्णित शास्त्रीय समस्या के समान, साक्षात्कारकर्ता केवल यह देखता है कि क्या प्रत्येक आवेदक अब तक का सबसे अच्छा है (एक उम्मीदवार), प्रत्येक को मौके पर ही स्वीकार या अस्वीकार कर देना चाहिए, और यदि वह पहुंच जाता है तो अंतिम को स्वीकार करना चाहिए। (स्पष्ट होने के लिए, साक्षात्कारकर्ता प्रत्येक आवेदक की वास्तविक सापेक्ष रैंक नहीं सीखता है। वह केवल यह सीखता है कि आवेदक की सापेक्ष रैंक 1 है या नहीं।) हालांकि, इस संस्करण में भुगतान चयनित आवेदक के सही मूल्य द्वारा दिया गया है। उदाहरण के लिए, यदि वह एक आवेदक का चयन करता है जिसका सही मूल्य 0.8 है, तो वह 0.8 कमाएगा। साक्षात्कारकर्ता का उद्देश्य चयनित आवेदक के [[अपेक्षित मूल्य]] को अधिकतम करना है।
इस समस्या का प्रारूप बनाने के लिए मान लीजिए कि <math>n</math> आवेदकों के पास वास्तविक मूल्य हैं जो यादृच्छिक चर एक्स तैयार हैं 0, 1 पर एक [[समान वितरण (निरंतर)|समान वितरण निरंतर]] ऊपर वर्णित शास्त्रीय समस्या के समान साक्षात्कारकर्ता केवल यह देखता है कि क्या प्रत्येक आवेदक अब तक का सबसे अच्छा है एक उम्मीदवार प्रत्येक को मौके पर ही स्वीकार या अस्वीकार कर देना चाहिए और यदि वह पहुंच जाता है तो अंतिम को स्वीकार करना चाहिए साक्षात्कारकर्ता प्रत्येक आवेदक की वास्तविक सापेक्ष पद नहीं सीखता है वह केवल यह सीखता है कि आवेदक की सापेक्ष पद 1 है या नहीं जबकि इस संस्करण में भुगतान चयनित आवेदक के सही मूल्य द्वारा दिया गया है उदाहरण के लिए यदि वह एक आवेदक का चयन करता है जिसका सही मूल्य 0.8 है, तो वह 0.8 कमाएगा साक्षात्कारकर्ता का उद्देश्य चयनित आवेदक के [[अपेक्षित मूल्य]] को अधिकतम करना है।


चूंकि आवेदक के मान i.i.d. [0, 1] पर एक समान वितरण से प्राप्त करता है, दिए गए tवें आवेदक का अपेक्षित मूल्य <math>x_{t}=\max\left\{x_1, x_2, \ldots, x_t\right\}</math> द्वारा दिया गया है
चूंकि आवेदक के मान 0, 1 पर एक समान वितरण से प्राप्त करता है दिए गए tवें आवेदक का अपेक्षित मूल्य <math>x_{t}=\max\left\{x_1, x_2, \ldots, x_t\right\}</math> द्वारा दिया गया है


:<math>
:<math>
E_{t}=E\left(X_{t}|I_{t}=1\right)=\frac{t}{t+1}.
E_{t}=E\left(X_{t}|I_{t}=1\right)=\frac{t}{t+1}.
</math>
</math>
शास्त्रीय समस्या के रूप में, इष्टतम नीति एक दहलीज द्वारा दी गई है, जिसे इस समस्या के लिए हम निरूपित करेंगे <math>c</math>, जिस पर साक्षात्कारकर्ता को उम्मीदवारों को स्वीकार करना शुरू कर देना चाहिए। बेयरडेन ने दिखाया कि सी या तो है <math>\lfloor \sqrt n \rfloor</math> या <math>\lceil \sqrt n \rceil</math>.{{sfn|Bearden|2006}} (वास्तव में, जो भी सबसे करीब है <math> \sqrt n </math>।) यह इस तथ्य से अनुसरण करता है कि एक समस्या दी गई है <math>n</math> आवेदकों, कुछ मनमाने ढंग से सीमा के लिए अपेक्षित अदायगी <math>1 \le c \le n</math> है
शास्त्रीय समस्या के रूप में इष्टतम नीति एक दहलीज द्वारा दी गई है जिसे इस समस्या के लिए हम निरूपित करेंगे <math>c</math>, जिस पर साक्षात्कारकर्ता को उम्मीदवारों को स्वीकार करना शुरू कर देना चाहिए बेयरडेन ने दिखाया कि सी या तो है <math>\lfloor \sqrt n \rfloor</math> या <math>\lceil \sqrt n \rceil</math>.{{sfn|Bearden|2006}} वास्तव में जो भी सबसे करीब है <math> \sqrt n </math>। यह इस तथ्य से अनुसरण करता है कि एक समस्या दी गई है <math>n</math> आवेदकों को कुछ मनमाने ढंग से सीमा के लिए अपेक्षित अदायगी <math>1 \le c \le n</math> प्ादानन करता है


:<math>
:<math>
Line 159: Line 158:
+\left[\prod_{s=c}^{n-1}\left(\frac{s-1}{s}\right)\right]\frac{1}{2}={\frac {2cn-{c}^{2}+c-n}{2cn}}.
+\left[\prod_{s=c}^{n-1}\left(\frac{s-1}{s}\right)\right]\frac{1}{2}={\frac {2cn-{c}^{2}+c-n}{2cn}}.
</math>
</math>
फर्क <math> V_{n}(c)</math> सी के संबंध में, एक प्राप्त करता है
<math> V_{n}(c)</math> सी के संबंध में एक प्राप्त कर्ता है


: <math>\frac{\partial V}{\partial c} = \frac{ -{c}^{\,2}+n }{ 2{c}^{\,2}n }.</math>
: <math>\frac{\partial V}{\partial c} = \frac{ -{c}^{\,2}+n }{ 2{c}^{\,2}n }.</math>
फ़ाइल: RelativeRankLearning2.pdf|thumb|आंशिक-सूचना अनुक्रमिक खोज प्रतिमान में सीखना। संख्या खोज में विभिन्न बिंदुओं पर उनके सापेक्ष रैंक (अब तक देखे गए कुल आवेदकों में से) के आधार पर आवेदकों के अपेक्षित मूल्यों को प्रदर्शित करती है। उम्मीदों की गणना मामले के आधार पर की जाती है जब उनके मान समान रूप से 0 और 1 के बीच वितरित किए जाते हैं। सापेक्ष रैंक की जानकारी साक्षात्कारकर्ता को आवेदकों का अधिक बारीकी से मूल्यांकन करने की अनुमति देती है क्योंकि वे उनकी तुलना करने के लिए अधिक डेटा बिंदु जमा करते हैं।
आंशिक-सूचना अनुक्रमिक खोज प्रतिमान में सीखना संख्या खोज में विभिन्न बिंदुओं पर उनके सापेक्ष पद अब तक देखे गए कुल आवेदकों में से आवेदकों के अपेक्षित मूल्यों को प्रदर्शित करती है उम्मीदों की गणना जगहों के आधार पर की जाती है जब उनके मान समान रूप से 0 और 1 के बीच वितरित किए जाते हैं सापेक्ष पद की जानकारी साक्षात्कारकर्ता को आवेदकों का अधिक बारीकी से मूल्यांकन करने की अनुमति देती है क्योंकि वे उनकी तुलना करने के लिए अधिक डेटा बिंदु जमा करते हैं तब से <math>\partial^{\,2}V / \partial c^{\,2}<0</math> के सभी अनुमेय मूल्यों के लिए <math>c</math> तथा <math>V</math> का अधिकतम होता है <math>c=\sqrt n</math>. चूँकि V उत्तल है <math>c</math> इष्टतम पूर्णांक-मान होना चाहिए <math>\lfloor \sqrt n \rfloor</math> या <math>\lceil \sqrt n \rceil</math>. इस प्रकार के अधिकांश मूल्यों के लिए <math>n</math> साक्षात्कारकर्ता शास्त्रीय संस्करण की तुलना में प्रमुख प्रतिदान संस्करण में जल्द ही आवेदकों को स्वीकार करना शुरू कर देगा जहां उद्देश्य एकल सर्वश्रेष्ठ आवेदक का चयन करना है ध्यान दें कि यह एक स्पर्शोन्मुख परिणाम नहीं है यह सभी के लिए है <math>n</math>. जबकि ज्ञात वितरण से अपेक्षित मूल्य को अधिकतम करने के लिए यह इष्टतम नीति नहीं है ज्ञात वितरण के स्थान में गतिशील कार्यक्रम के माध्यम से इष्टतम खेल की गणना की जा सकती है।
तब से <math>\partial^{\,2}V / \partial c^{\,2}<0</math> के सभी अनुमेय मूल्यों के लिए <math>c</math>, हम पाते हैं <math>V</math> पर अधिकतम होता है <math>c=\sqrt n</math>. चूँकि V उत्तल है <math>c</math>, इष्टतम पूर्णांक-मान थ्रेशोल्ड या तो होना चाहिए <math>\lfloor \sqrt n \rfloor</math> या <math>\lceil \sqrt n \rceil</math>. इस प्रकार, के अधिकांश मूल्यों के लिए <math>n</math> साक्षात्कारकर्ता शास्त्रीय संस्करण की तुलना में कार्डिनल पेऑफ संस्करण में जल्द ही आवेदकों को स्वीकार करना शुरू कर देगा, जहां उद्देश्य एकल सर्वश्रेष्ठ आवेदक का चयन करना है। ध्यान दें कि यह एक स्पर्शोन्मुख परिणाम नहीं है: यह सभी के लिए है <math>n</math>. हालांकि, ज्ञात वितरण से अपेक्षित मूल्य को अधिकतम करने के लिए यह इष्टतम नीति नहीं है। ज्ञात वितरण के मामले में, गतिशील प्रोग्रामिंग के माध्यम से इष्टतम खेल की गणना की जा सकती है।


इस समस्या का एक अधिक सामान्य रूप पाले और क्रेमर (2014) द्वारा पेश किया गया<ref>{{Cite journal|last1=Palley|first1=Asa B.|last2=Kremer|first2=Mirko|date=2014-07-08|title=Sequential Search and Learning from Rank Feedback: Theory and Experimental Evidence|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2014.1902|journal=Management Science|volume=60|issue=10|pages=2525–2542|doi=10.1287/mnsc.2014.1902|issn=0025-1909}}</ref> मानता है कि प्रत्येक नए आवेदक के आने पर, साक्षात्कारकर्ता उन सभी आवेदकों के सापेक्ष उनकी रैंक देखता है जो पहले देखे जा चुके हैं। यह मॉडल एक साक्षात्कारकर्ता सीखने की धारणा के अनुरूप है क्योंकि वे पिछले डेटा बिंदुओं के एक सेट को जमा करके खोज प्रक्रिया जारी रखते हैं जिसका उपयोग वे नए उम्मीदवारों के आने पर उनका मूल्यांकन करने के लिए कर सकते हैं। इस तथाकथित आंशिक-सूचना मॉडल का एक लाभ यह है कि यदि साक्षात्कारकर्ता को प्रत्येक आवेदक के मूल्य के बारे में पूरी जानकारी दी गई थी, तो सापेक्ष रैंक की जानकारी के साथ प्राप्त किए गए निर्णयों और परिणामों की सीधे संबंधित इष्टतम निर्णयों और परिणामों से तुलना की जा सकती है। यह पूर्ण-सूचना समस्या, जिसमें आवेदकों को एक ज्ञात वितरण से स्वतंत्र रूप से लिया जाता है और साक्षात्कारकर्ता चयनित आवेदक के अपेक्षित मूल्य को अधिकतम करना चाहता है, मूल रूप से मोजर (1956) द्वारा हल किया गया था,<ref>{{Cite journal|last=Moser|first=Leo|date=1956|title=केली की समस्या पर|journal=Scripta Math|volume=22|pages=289–292}}</ref> सकागुची (1961),<ref>{{Cite journal|date=1961-06-01|title=कुछ अनुक्रमिक नमूनाकरण डिजाइन की गतिशील प्रोग्रामिंग|journal=Journal of Mathematical Analysis and Applications|language=en|volume=2|issue=3|pages=446–466|doi=10.1016/0022-247X(61)90023-3|issn=0022-247X|last1=Sakaguchi|first1=Minoru|doi-access=free}}</ref> और कार्लिन (1962)।
इस समस्या का एक अधिक सामान्य रूप पाले और क्रेमर (2014) द्वारा पेश किया गया<ref>{{Cite journal|last1=Palley|first1=Asa B.|last2=Kremer|first2=Mirko|date=2014-07-08|title=Sequential Search and Learning from Rank Feedback: Theory and Experimental Evidence|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2014.1902|journal=Management Science|volume=60|issue=10|pages=2525–2542|doi=10.1287/mnsc.2014.1902|issn=0025-1909}}</ref> मानना है कि प्रत्येक नए आवेदक के आने पर साक्षात्कारकर्ता उन सभी आवेदकों के सापेक्ष उनका पद देखता है जो पहले देखे जा चुके हैं यह प्रतिरूप एक साक्षात्कारकर्ता सीखने की धारणा के अनुरूप है क्योंकि वे पिछले डेटा बिंदुओं के एक समूह को जमा करके खोज प्रक्रिया जारी रखते हैं जिसका उपयोग वे नए उम्मीदवारों के आने पर उनका मूल्यांकन करने के लिए कर सकते हैं इस तथाकथित आंशिक-सूचना प्रतिरूप का एक लाभ यह है कि यदि साक्षात्कारकर्ता को प्रत्येक आवेदक के मूल्य के बारे में पूरी जानकारी दी गई थी तो सापेक्ष पद की जानकारी के साथ प्राप्त किए गए निर्णयों और परिणामों की सीधे संबंधित इष्टतम निर्णयों और परिणामों से तुलना की जा सकती है यह पूर्ण-सूचना समस्या जिसमें आवेदकों को एक ज्ञात वितरण से स्वतंत्र रूप से लिया जाता है और साक्षात्कारकर्ता चयनित आवेदक के अपेक्षित मूल्य को अधिकतम करना चाहता है यह मूल रूप से मोजर द्वारा 1956 में सकागुची 1961 में और कॉर्लिन 1962 में हल किया गया था। <ref>{{Cite journal|last=Moser|first=Leo|date=1956|title=केली की समस्या पर|journal=Scripta Math|volume=22|pages=289–292}}</ref>


== अन्य संशोधन ==
== अन्य संशोधन ==
सचिव समस्या के कई रूप हैं जिनका सरल और सुरुचिपूर्ण समाधान भी है।
सचिव समस्या के कई रूप हैं जिनका सरल और सुरुचिपूर्ण समाधान भी है।