Yandex.Taxi कैसे कारों की खोज करती है जबकि वहाँ कोई कार नहीं है

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

इस लेख में मैं इस बारे में बात करना चाहता हूं कि मशीन लर्निंग का उपयोग करके, हमने कम घनत्व वाले क्षेत्रों में कारों की खोज की समस्या को कैसे हल किया (दूसरे शब्दों में, जहां, पहली नज़र में, कोई कार नहीं है)। और इससे क्या हुआ.

पृष्ठभूमि

टैक्सी बुलाने के लिए, उपयोगकर्ता कुछ सरल कदम उठाता है, लेकिन सेवा के अंदर क्या होता है?

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

पर पिन में ईटीए, मूल्य गणना и सबसे उपयुक्त ड्राइवर चुनना हम पहले ही लिख चुके हैं. और यह ड्राइवरों को ढूंढने के बारे में एक कहानी है। जब कोई ऑर्डर बनाया जाता है, तो खोज दो बार होती है: पिन पर और ऑर्डर पर। किसी ऑर्डर की खोज दो चरणों में होती है: उम्मीदवारों की भर्ती और रैंकिंग। सबसे पहले, उपलब्ध उम्मीदवार ड्राइवर ढूंढे जाते हैं जो सड़क ग्राफ़ के सबसे करीब हों। फिर बोनस और फ़िल्टरिंग लागू की जाती है। शेष उम्मीदवारों को रैंक दी जाती है और विजेता को ऑर्डर ऑफर प्राप्त होता है। यदि वह सहमत होता है, तो उसे ऑर्डर सौंपा जाता है और डिलीवरी बिंदु पर चला जाता है। अगर वह मना कर दे तो ऑफर अगले के पास आ जाता है. यदि कोई और उम्मीदवार नहीं हैं, तो खोज फिर से शुरू होती है। यह तीन मिनट से अधिक नहीं चलता है, जिसके बाद ऑर्डर रद्द कर दिया जाता है और जला दिया जाता है।

पिन पर खोजना किसी ऑर्डर पर खोज करने के समान है, केवल ऑर्डर नहीं बनाया जाता है और खोज केवल एक बार ही की जाती है। उम्मीदवारों की संख्या और खोज त्रिज्या के लिए सरलीकृत सेटिंग्स का भी उपयोग किया जाता है। इस तरह के सरलीकरण आवश्यक हैं क्योंकि ऑर्डर की तुलना में परिमाण के क्रम में अधिक पिन होते हैं, और खोज करना एक कठिन कार्य है। हमारी कहानी का मुख्य बिंदु: यदि प्रारंभिक खोज के दौरान पिन पर कोई उपयुक्त उम्मीदवार नहीं मिला, तो हम आपको ऑर्डर देने की अनुमति नहीं देते हैं। कम से कम पहले तो ऐसा ही होता था.

उपयोगकर्ता ने एप्लिकेशन में यही देखा:

बिना कारों वाली कारों की खोज करें

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

इस परिकल्पना का परीक्षण करने के लिए, हमने एक प्रयोग शुरू किया: हमने उपयोगकर्ताओं के एक परीक्षण समूह के लिए पिन पर खोज के दौरान कारों की उपस्थिति की जांच करना बंद कर दिया, यानी, उनके पास "कारों के बिना ऑर्डर" करने का अवसर था। परिणाम काफी अप्रत्याशित था: यदि कार पिन पर नहीं थी, तो 29% मामलों में यह बाद में पाई गई - ऑर्डर पर खोज करने पर! इसके अलावा, रद्दीकरण दर, रेटिंग और अन्य गुणवत्ता संकेतकों के मामले में कारों के बिना ऑर्डर नियमित ऑर्डर से काफी भिन्न नहीं थे। कारों के बिना बुकिंग सभी बुकिंग का 5% थी, लेकिन सभी सफल यात्राओं में केवल 1% से अधिक थी।

यह समझने के लिए कि इन आदेशों के निष्पादक कहां से आते हैं, आइए एक पिन पर खोज के दौरान उनकी स्थिति देखें:

• उपलब्ध: उपलब्ध था, लेकिन किसी कारण से उम्मीदवारों में शामिल नहीं किया गया था, उदाहरण के लिए, वह बहुत दूर था;
• आदेश पर: व्यस्त था, लेकिन खुद को मुक्त करने या उपलब्ध होने में कामयाब रहा श्रृंखला क्रम;
• व्यस्त: आदेश स्वीकार करने की क्षमता अक्षम कर दी गई, लेकिन फिर ड्राइवर लाइन पर लौट आया;
• उपलब्ध नहीं है: ड्राइवर ऑनलाइन नहीं था, लेकिन वह उपस्थित हुआ।

आइए विश्वसनीयता जोड़ें

अतिरिक्त ऑर्डर बढ़िया हैं, लेकिन 29% सफल खोजों का मतलब है कि 71% मामलों में उपयोगकर्ता ने लंबे समय तक इंतजार किया और अंततः कहीं नहीं गया। हालाँकि सिस्टम दक्षता के दृष्टिकोण से यह कोई बुरी बात नहीं है, यह वास्तव में उपयोगकर्ता को झूठी आशा देता है और समय बर्बाद करता है, जिसके बाद वे परेशान हो जाते हैं और (संभवतः) सेवा का उपयोग करना बंद कर देते हैं। इस समस्या को हल करने के लिए, हमने इस संभावना का अनुमान लगाना सीखा कि ऑर्डर पर कार मिल जाएगी।

योजना इस प्रकार है:

• उपयोगकर्ता एक पिन डालता है.
• पिन पर सर्च किया जाता है.
• यदि कोई कारें नहीं हैं, तो हम भविष्यवाणी करते हैं: शायद वे दिखाई देंगी।
• और संभावना के आधार पर, हम आपको ऑर्डर देने की अनुमति देते हैं या नहीं देते हैं, लेकिन हम आपको चेतावनी देते हैं कि इस समय इस क्षेत्र में कारों का घनत्व कम है।

एप्लिकेशन में यह इस तरह दिखता था:

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

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

मान लीजिए हम किसी दुर्लभ और खतरनाक बीमारी के लिए परीक्षण (क्लासिफायरियर) कर रहे हैं। परीक्षण के परिणामों के आधार पर, हम या तो रोगी को अधिक विस्तृत जांच के लिए भेजते हैं, या कहते हैं: "अच्छा, घर जाओ।" हमारे लिए, किसी बीमार व्यक्ति को घर भेजना किसी स्वस्थ व्यक्ति की अनावश्यक जांच करने से कहीं अधिक बुरा है। यानी, हम चाहते हैं कि परीक्षण यथासंभव अधिक से अधिक बीमार लोगों पर काम करे। इस मान को रिकॉल = कहा जाता है. एक आदर्श क्लासिफायरियर की रिकॉल 100% होती है। एक ख़राब स्थिति यह है कि सभी को जांच के लिए भेजें, फिर रिकॉल भी 100% होगा।

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

यदि एल्गोरिदम एक संख्यात्मक संभाव्यता मान उत्पन्न करता है, तो विभिन्न थ्रेसहोल्ड का चयन करके, आप विभिन्न सटीक-रिकॉल मान प्राप्त कर सकते हैं।

हमारी समस्या में स्थिति इस प्रकार है. रिकॉल उन ऑर्डरों की संख्या है जो हम पेश कर सकते हैं, सटीकता इन ऑर्डरों की विश्वसनीयता है। हमारे मॉडल का सटीक-रिकॉल वक्र इस प्रकार दिखता है:

दो चरम मामले हैं: किसी को भी ऑर्डर करने की अनुमति न दें और सभी को ऑर्डर करने की अनुमति दें। यदि आप किसी को अनुमति नहीं देते हैं, तो रिकॉल 0 होगा: हम ऑर्डर नहीं बनाते हैं, लेकिन उनमें से कोई भी विफल नहीं होगा। यदि हम सभी को अनुमति देते हैं, तो रिकॉल 100% होगा (हमें सभी संभावित ऑर्डर प्राप्त होंगे), और सटीकता 29% होगी, यानी 71% ऑर्डर खराब होंगे।

हमने शुरुआती बिंदु के विभिन्न मापदंडों को संकेतों के रूप में इस्तेमाल किया:

• समय/स्थान.
• सिस्टम स्थिति (आस-पास के सभी टैरिफ और पिन की कब्जे वाली मशीनों की संख्या)।
• खोज पैरामीटर (त्रिज्या, उम्मीदवारों की संख्या, प्रतिबंध)।

संकेतों के बारे में अधिक जानकारी

वैचारिक रूप से, हम दो स्थितियों के बीच अंतर करना चाहते हैं:

• "गहरा जंगल" - इस समय यहाँ कोई कार नहीं है।
• "अशुभ" - कारें तो हैं, लेकिन खोजने पर कोई उपयुक्त कारें नहीं मिलीं।

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

इसलिए, बिंदु A के आसपास के विभिन्न सिस्टम संकेतक अच्छी विशेषताएं साबित हुए:

• कारों की कुल संख्या.
• ऑर्डर पर कारों की संख्या.
• "व्यस्त" स्थिति में ऑर्डर करने के लिए अनुपलब्ध कारों की संख्या।
• उपयोगकर्ता की संख्या।

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

मॉडल प्रशिक्षण एल्गोरिथ्म था कैटबॉस्ट. प्रयोग से प्राप्त डेटा का उपयोग प्रशिक्षण के लिए किया गया। कार्यान्वयन के बाद, प्रशिक्षण डेटा एकत्र करना पड़ता था, कभी-कभी कम संख्या में उपयोगकर्ताओं को मॉडल के निर्णय के विरुद्ध आदेश देने की अनुमति मिलती थी।

परिणाम

प्रयोग के नतीजे उम्मीद के मुताबिक थे: मॉडल का उपयोग करने से आप कारों के बिना ऑर्डर के कारण सफल यात्राओं की संख्या में उल्लेखनीय वृद्धि कर सकते हैं, लेकिन विश्वसनीयता से समझौता किए बिना।

फिलहाल, यह तंत्र सभी शहरों और देशों में लॉन्च किया गया है और इसकी मदद से लगभग 1% सफल यात्राएं होती हैं। इसके अलावा, कारों के कम घनत्व वाले कुछ शहरों में, ऐसी यात्राओं का हिस्सा 15% तक पहुँच जाता है।

टैक्सी तकनीक के बारे में अन्य पोस्ट

• हम Yandex.Taxi में ड्राइवरों के बीच ऑर्डर कैसे वितरित करते हैं
• गतिशील मूल्य निर्धारण, या कैसे Yandex.Taxi उच्च मांग की भविष्यवाणी करता है
• कार की स्थिति का आकलन करने के लिए कंप्यूटर विज़न का उपयोग कैसे करें। यांडेक्स.टैक्सी अनुभव
• Yandex.Taxi मशीन लर्निंग का उपयोग करके कार पिक-अप समय की भविष्यवाणी कैसे करती है

स्रोत: www.habr.com