खोज hh.ru के लिए नई संकेत सेवा

खोज संकेत महान हैं। एड्रेस बार में हम कितनी बार पूरी साइट का पता टाइप करते हैं? और ऑनलाइन स्टोर में उत्पाद का नाम? ऐसे लघु प्रश्नों के लिए, कुछ वर्ण टाइप करना आमतौर पर पर्याप्त होता है यदि खोज संकेत अच्छे हों। और अगर आपके पास बीस उंगलियां या अविश्वसनीय टाइपिंग गति नहीं है, तो आप निश्चित रूप से उनका उपयोग करेंगे।
इस लेख में, हम अपनी नई hh.ru खोज संकेत सेवा के बारे में बात करेंगे, जो हमने स्कूल ऑफ प्रोग्रामर्स के पिछले अंक में की थी।

पुरानी सेवा में कई समस्याएं थीं:

• उन्होंने हाथ से चुने गए लोकप्रिय उपयोगकर्ता प्रश्नों पर काम किया;
• उपयोगकर्ता की वरीयताओं को बदलने के लिए अनुकूल नहीं हो सकता;
• उन प्रश्नों को रैंक नहीं कर सकता है जो शीर्ष में शामिल नहीं हैं;
• टाइपो ठीक नहीं किया।

नई सेवा में, हमने इन कमियों (नए लोगों को जोड़ते समय) को ठीक किया।

लोकप्रिय प्रश्नों का शब्दकोश

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

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

भाषा मॉडल

एक अन्य दृष्टिकोण प्रश्नों की संभावनाओं का मूल्यांकन करना और उपयोगकर्ता क्वेरी के लिए सबसे संभावित निरंतरता उत्पन्न करना सीखना है। ऐसा करने के लिए, भाषा मॉडल का उपयोग करें - शब्द अनुक्रम के एक सेट पर एक संभावना वितरण।



चूंकि उपयोगकर्ता अनुरोध ज्यादातर कम होते हैं, इसलिए हमने तंत्रिका नेटवर्क भाषा मॉडल की कोशिश भी नहीं की, लेकिन खुद को एन-ग्राम तक सीमित कर लिया:

$$

$$P (w_1 \ dots w_m) = \ prod_ {i = 1} ^ mP (w_i | w_1 \ dots w_ {i-1}) \ लगभग \ prod_ {i = 1} ^ mP (w_i। W_ {i-) n-1)} \ dots w_ {i-1})$$

सबसे सरल मॉडल के रूप में, हम संभावना की सांख्यिकीय परिभाषा ले सकते हैं

$$

$$P (w_i | w_1 \ dots w_ {i-1}) = \ frac {गिनती (w_1 \ dots w_i)} {गिनती (w_1 \ dots w_ {i-1})}$$

हालांकि, ऐसा मॉडल उन प्रश्नों के मूल्यांकन के लिए उपयुक्त नहीं है जो हमारे नमूने में नहीं थे: यदि हमने 'जूनियर डेवलपर जावा' का अवलोकन नहीं किया है, तो यह पता चला है कि

$$

$$P (\ text {जूनियर डेवलपर java}) = \ frac {गिनती (\ text {जूनियर डेवलपर java})}} {गिनती (\ text {जूनियर डेवलपर})} = 0$$

इस समस्या को हल करने के लिए, आप विभिन्न मॉडलों को चौरसाई और प्रक्षेप का उपयोग कर सकते हैं। हमने बैकऑफ़ का उपयोग किया:

$$

$$P_ {bo} (w_n | w_1 \ dots w_ {n-1}) = \ _ {मामले} {P} (w_n | w_1 \ dots w_ {n-1}), गिनें (w_1 / dots w_ {n-) 1})> 0 \\ \ अल्फा {P_ {bo}} (w_n | w_2 \ dots w_ {n-1}), गिनती (w_1 \ dots w_ {n-1}) = 0 \ end {मामले:$$

$$

$$\ Alpha = \ frac {P (w_1 \ dots w_ {n-1})} {1 - \ sum_wP_ {bo} (w | w_2 \ dots w_ {n-1})}$$

जहां P स्मूथी प्रायिकता है $$$w_1 ... w_ {n-1}$ (हम लाप्लास स्मूथिंग का इस्तेमाल करते हैं):

$$

$$P (w_n | w_1 \ dots w_ {n-1}) = \ frac {गिनती (w_n) + \ delta} {गिनती (w_1 \ dots w_ {n-1}) + \ delta। V |}$$

जहां वी हमारा शब्दकोश है।

विकल्प पीढ़ी

इसलिए, हम किसी विशेष अनुरोध की संभावना का आकलन करने में सक्षम हैं, लेकिन इन समान अनुरोधों को कैसे उत्पन्न करें? निम्न कार्य करना बुद्धिमानी है: उपयोगकर्ता को एक क्वेरी दर्ज करने दें $$$w_1 ... w_n$ , तब जो प्रश्न हमारे लिए उपयुक्त हैं, उन्हें शर्त से पाया जा सकता है

$$

$$w_1 \ dots w_m = \ underset {w_ {n + 1} \ dots w_m \ _ in V} {argmax} P (w_1 \ dots w_n w_ {n + 1} \ dots w_m)$$

बेशक, के माध्यम से छँटाई $$$| वी | ^ {m-n}, m = 1 \ dots M$ प्रत्येक आने वाले अनुरोध के लिए सर्वोत्तम विकल्पों का चयन करना संभव नहीं है, इसलिए हम बीम खोज का उपयोग करेंगे । हमारे n- ग्राम भाषा मॉडल के लिए, यह निम्न एल्गोरिथ्म में आता है:

def beam(initial, vocabulary): variants = [initial] for i in range(P): candidates = [] for variant in variants: candidates.extends(generate_candidates(variant, vocabulary)) variants = sorted(candidates)[:N] return candidates def generate_candidates(variant, vocabulary): top_terms = [] #         1, 2, ... n  for n0 in range(n): top_n = sorted(vocabulary, key=lambda c: P(|variant[-n0:]) top_terms.extends(top_n) candidates = [variant + [term] for term in top_terms] #       candidates = sorted(candidates, key=lambda v: P(variant))[:N] return candidates 

यहां हरे रंग में हाइलाइट किए गए नोड्स अंतिम चयनित विकल्प हैं, नोड के सामने की संख्या $$$w_n$ - संभावना $$$P (w_n | w_ {n-1})$ , नोड के बाद - $$$P (w1 ... w_n)$ ।

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

संभावनाओं के लिए बोरान

वाक्यांश की निरंतरता के सशर्त प्रायिकता वेरिएंट में एन सर्वश्रेष्ठ प्राप्त करने के लिए, हमने शब्दों में बोरॉन का उपयोग किया। नोड में $$$w_1 \ _ to w_2$ संग्रहीत गुणांक $$$\ अल्फा$ , मूल्य $$$P (w_2 | w_1)$ और सशर्त संभावना द्वारा छांटे गए $$$P (\ बुलेट | w_1 w_2)$ शर्तों की सूची $$$w_3$ साथ में $$$P (w_3 | w_1 w_2)$ । विशेष शब्द eos एक वाक्यांश के अंत को चिह्नित करता है।

लेकिन एक अति सूक्ष्म अंतर है

ऊपर वर्णित एल्गोरिथ्म में, हम मानते हैं कि क्वेरी में सभी शब्द पूरे हो गए थे। हालांकि, यह अंतिम शब्द के लिए सही नहीं है कि उपयोगकर्ता इसे अभी दर्ज करता है। वर्तमान शब्द को दर्ज करने के लिए हमें फिर से पूरे शब्दकोश में जाना होगा। इस समस्या को हल करने के लिए, हम एक प्रतीकात्मक बोरान का उपयोग करते हैं, जिसके नोड्स में हम एम की शर्तों को असमान संभावना द्वारा सॉर्ट करते हैं। उदाहरण के लिए, यह M = 3 के साथ जावा, जूनियर, ज्यूपिटर, जावास्क्रिप्ट के लिए हमारे बोर की तरह दिखेगा:



फिर, बीम खोज की शुरुआत करने से पहले, हम वर्तमान शब्द को जारी रखने के लिए M सर्वोत्तम उम्मीदवारों की खोज करते हैं $$$w_n$ और के लिए एन सर्वश्रेष्ठ उम्मीदवारों का चयन करें $$$P (w_1 \ dots w_n)$ ।

शुद्धिपत्र

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

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

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

यदि आप एक संभाव्य बिंदु से टाइपो को ठीक करने के कार्य से संपर्क करते हैं, तो शोर चैनल के मॉडल में आना काफी स्वाभाविक है:

1. वर्णमाला सेट $$$\ सिग्मा$ ;
2. सभी अनुगामी लाइनों का सेट $$$\ सिग्मा ^ *$ उसके ऊपर;
3. कई लाइनें जो सही शब्द हैं $$$D \ subseteq \ सिग्मा ^ *$ ;
4. वितरण दिया गया $$$P (s | w)$ जहाँ $$$s \ in \ सिग्मा ^ *, w \ _ D $ मे$ ।

तब सुधार कार्य इनपुट एस के लिए सही शब्द w खोजने के रूप में सेट किया गया है। त्रुटि के स्रोत के आधार पर, माप करें $$$पी$ इसे विभिन्न तरीकों से बनाया जा सकता है, हमारे मामले में टाइपो की संभावना का अनुमान लगाने का प्रयास करना बुद्धिमानी है (चलो उन्हें तत्व प्रतिस्थापन कहते हैं) $$$P_e (t | r)$ , जहाँ t, r प्रतीकात्मक n- ग्राम हैं, और फिर मूल्यांकन करते हैं $$$P (s | w)$ सबसे संभावित प्राथमिक प्रतिस्थापन द्वारा डब्ल्यू से प्राप्त करने की संभावना के रूप में।

चलो $$$Part_n (x)$ - स्ट्रिंग को एन सब्सट्रिंग्स (संभवतः शून्य) में विभाजित करना। ब्रिल-मूर मॉडल में संभाव्यता की गणना शामिल है $$$P (s | w)$ निम्नानुसार है:

$$

$$P (s। W) \ लगभग \ max_ {R \ in Part_n (s)} T_ में Part_n (s)} \ prod_ {i = 1} ^ {n} P_e (T_i | R_i)$$

लेकिन हमें खोजने की जरूरत है $$$P (w | s)$ :

$$

$$P (w | s) = \ frac {P (s | w) P (w)} {P (s)} = const \ cdot P (s | w) \ cdot P (w)$$

P (w | s) का मूल्यांकन करने के लिए सीखने के द्वारा, हम उसी दमरेउ-लेवेंसाइटिन दूरी के साथ रैंकिंग विकल्पों की समस्या को भी हल करेंगे और टाइपो को ठीक करने पर संदर्भ लेने में सक्षम होंगे।

गणना $$$P_e (T_i | R_i)$

प्राथमिक प्रतिस्थापन की संभावनाओं की गणना करने के लिए, उपयोगकर्ता प्रश्न हमें फिर से मदद करेंगे: हम शब्दों के जोड़े की रचना करेंगे (s, w)

1. दमरेउ-लेवेंश्टीन में करीब;
2. एक शब्द अन्य एन बार की तुलना में अधिक सामान्य है।

ऐसी जोड़ियों के लिए, हम लेवेंसहाइट के अनुसार इष्टतम संरेखण पर विचार करते हैं:


हम s और w के सभी संभावित विभाजन की रचना करते हैं (हमने खुद को लंबाई n = 2, 3 तक सीमित कर लिया है): n → n, pr → rn, pro → rn, ro → po, m → ``, mm → m, आदि। प्रत्येक एन-ग्राम के लिए, हम पाते हैं

$$

$$P_e (t | r) = \ frac {गिनती (r \ to t)} {गिनती (r)}$$

गणना $$$P (s | w)$

गणना $$$P (s | w)$ सीधे लेता है $$$O (2 ^ {| w | + | s |})$ : हम एस के सभी संभव विभाजन के साथ डब्ल्यू के सभी संभव विभाजन के माध्यम से सॉर्ट करने की आवश्यकता है। हालाँकि, उपसर्ग पर गतिकी एक उत्तर दे सकती है $$$O (| w | * | s | * n ^ 2)$ जहां n प्राथमिक प्रतिस्थापन की अधिकतम लंबाई है:

$$

$$d [i, j] = \ start {case} d [0, j] = 0 & j> = k \\ d [i, 0] = 0 & i> = k \\ d [0, j] = P (s [0: j] \ space। \ Space w [0]) और j <k \\ d [i, 0] = P (s [0] \ space | \ space w [0: i] & | i <k \\ d [i, j] = \ underset {k, l \ le n, k \ lt i, l \ lt j} {max} (p [s jl: j] \ space | \ space w [ik: i]) \ cdot d [ik-१, jl-१]) \ end {मामले}$$

यहां पी k-gram मॉडल में संबंधित पंक्ति की संभावना है। यदि आप बारीकी से देखते हैं, तो यह वैकोनर-फिशर एल्गोरिथ्म के साथ उककोन कतरन के समान है। हर कदम पर हमें मिलता है $$$P (w [0: i] | s [0: j])$ सभी सुधारों की गणना करके $$$w [i-k: i]$ में $$$s [j-l: j]$ के अधीन है $$$k, l \ le n$ और सबसे संभावित एक का चुनाव।

पर वापस $$$P (w | s)$

तो, हम गणना कर सकते हैं $$$P (s | w)$ । अब हमें कई विकल्पों को चुनने की आवश्यकता है $$$P (w | s)$ । अधिक सटीक, मूल अनुरोध के लिए $$$s_1s_2 \ dots s_n$ आपको चुनना होगा $$$w_1 \ dots w_n$ जहाँ $$$P (w_1 \ dots w_n | s_1 \ dots s_n)$ अधिकतम। दुर्भाग्य से, विकल्पों की एक ईमानदार पसंद हमारी प्रतिक्रिया समय की आवश्यकताओं में फिट नहीं हुई (और परियोजना की समय सीमा करीब आ रही थी), इसलिए हमने निम्नलिखित दृष्टिकोण पर ध्यान केंद्रित करने का निर्णय लिया:

1. मूल क्वेरी से k को अंतिम शब्द बदलकर हमें कई विकल्प मिलते हैं:
   
   1. हम कीबोर्ड लेआउट को सही करते हैं यदि परिणामी शब्द में मूल एक से कई गुना अधिक संभावना हो;
   2. हमें ऐसे शब्द मिलते हैं जिनकी डमरू-लेवेंसाइटिन दूरी d से अधिक नहीं है;
   3. उनके लिए टॉप-एन विकल्पों में से चुनें $$$P (s | w)$ ;
2. मूल अनुरोध के साथ इनपुट के लिए BeamSearch भेजें;
3. परिणामों की रैंकिंग करते समय हम प्राप्त विकल्पों पर छूट देते हैं $$$\ prod_ {i = 0} ^ {k-1} P (s_ {n-i} | w_ {n-i})$ ।

क्लॉज 1.2 के लिए, हमने एफबी-ट्राइ एल्गोरिथ्म (आगे और पीछे का ट्राइ) का उपयोग किया, जो आगे और पीछे उपसर्ग वाले पेड़ों में फजी खोज पर आधारित है। यह पूरे शब्दकोश में P (s | w) के मूल्यांकन से अधिक तेज़ निकला।

क्वेरी सांख्यिकी

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

लेकिन डेटा अभी भी बहुत शोर है: xss इंजेक्शन के प्रयास, गलत लेआउट, क्लिपबोर्ड से यादृच्छिक पाठ, "प्रोग्रामर सी 1 सी नहीं" अनुरोधों के साथ अनुभवी उपयोगकर्ता , कीबोर्ड से गुजरे बिल्ली से अनुरोध ।


इसलिए, स्रोत डेटा को साफ़ करने के लिए, हमने बाहर रखा:

• कम आवृत्ति की शर्तें;
• युक्त क्वेरी भाषा ऑपरेटर
• अश्लील शब्दावली।

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

ठेस में

परियोजना सुरक्षा से ठीक पहले, उन्होंने आंतरिक परीक्षण के लिए उत्पादन में एक सेवा शुरू की, और कुछ दिनों के बाद - 20% उपयोगकर्ताओं के लिए। Hh.ru में, उपयोगकर्ताओं के लिए महत्वपूर्ण सभी परिवर्तन एबी परीक्षणों की एक प्रणाली से गुजरते हैं, जो हमें न केवल परिवर्तनों के महत्व और गुणवत्ता के बारे में सुनिश्चित करने की अनुमति देता है, बल्कि त्रुटियों को खोजने के लिए भी।



आवेदकों के लिए sujest से औसत खोजों की मीट्रिक तेज हो गई है (0.959 से बढ़कर 1.1355 तक), और सभी खोज क्वेरी के सबसे अच्छे से खोजों की हिस्सेदारी 12.78% से बढ़कर 15% हो गई है। दुर्भाग्य से, मुख्य उत्पाद मैट्रिक्स नहीं बढ़ा, लेकिन उपयोगकर्ताओं ने निश्चित रूप से अधिक युक्तियों का उपयोग करना शुरू कर दिया।

अंत में

स्कूल की प्रक्रियाओं, अन्य परीक्षण किए गए मॉडलों के बारे में एक कहानी के लिए कोई जगह नहीं थी, उपकरण जो हमने मॉडल तुलनाओं के लिए लिखे थे, और बैठकें जहां हमने तय किया कि मध्यवर्ती डेमो को पकड़ने के लिए कौन सी विशेषताओं को विकसित करना है। पिछले स्कूल के रिकॉर्ड को देखें , https://school.hh.ru पर एक अनुरोध छोड़ें, दिलचस्प कार्यों को पूरा करें और अध्ययन के लिए आएं। वैसे, कार्यों की जांच के लिए सेवा पिछले सेट के स्नातकों द्वारा भी की गई थी।

क्या पढ़ना है?

1. भाषा मॉडल का परिचय
2. ब्रिल-मूर मॉडल
3. अमेरिकन प्लान-Trie
4. आपकी खोज क्वेरी से क्या होता है