من الاستدلال إلى التعلم الآلي: اقتراحات البحث في Citymobil

مرحبا! اسمي ميخائيل دياتشكوف ، وفي Citymobil أقوم بالتعلم الآلي. سأخبرك اليوم عن الخوارزمية الجديدة الخاصة بنا لإنشاء اقتراحات بحث للوجهات النهائية. سوف تتعلم كيف تحولت مهمة تبدو بسيطة إلى سيناريو مثير للاهتمام ، حيث نأمل أن نجعل حياة المستخدمين أسهل قليلاً. نواصل مراقبة عمل الخوارزمية الجديدة عن كثب وسنقوم بعد ذلك بتعديلها للحفاظ على جودة الترتيب على مستوى عالٍ. بالنسبة لجميع المستخدمين ، سنطلق الخوارزمية في الأسابيع القليلة المقبلة ، لكننا مستعدون بالفعل لإخبارك بالرحلة الطويلة التي وصلنا إليها من الاستدلال إلى خوارزمية التعلم الآلي وإدخالها حيز التنفيذ.



أعتقد أن الأمر يستحق أن نبدأ بوصف العالم المثالي لسيناريو طلب سيارة أجرة من منظور واجهة المستخدم. أود أن يفهم تطبيقنا أين / أين / متى / بأي سيارة يريد المستخدم المغادرة. في هذه المقالة ، سنلقي نظرة على الحل الذي نقدمه للإجابة على سؤال "أين".



أحد العناصر المركزية على الشاشة الأولى (الذي يراه المستخدم بعد تسجيل الدخول) هو اقتراحات البحث. في فريق البحث الجغرافي ، نطلق عليهم اسم "sajest" (من الاقتراح الإنجليزي). أنها توفر للمستخدم عناوين المسار النهائية (النقاط "ب") من سجل السفر الخاص به بناءً على الموقع الحالي للدبوس (أي نقطة الإسقاط) والوقت من اليوم دون إدخال استعلام بحث. نحاول مساعدة المستخدم على تكوين أمر "بنقرة واحدة" بمساعدة sagests. في الإصدار الحالي من تطبيق عميل iOS ، تبدو sajests كما يلي:







يمكن أن يؤثر البحث الجغرافي ، بسبب خوارزميات إنشاء نتائج البحث ، على بعض أهم مقاييس المنتج لتطبيق العميل ، مثل الوقت الذي يقضيه في طلب سيارة أجرة ( وقت الطلب ، أو T2O ) ، وكذلك عدد الإجراءات التي اتخذها العميل لتشكيل أمر ( إجراءات للطلب ، أو A2O). لذلك ، قررنا تطوير خوارزمية تتنبأ بنقاط النهاية الأكثر احتمالية للمسار (النقاط "ب") لموقع ووقت معينين من اليوم.

ارشادي

أحد مطوري الواجهة الخلفية لفريق البحث الجغرافي (فاسيليسك، مرحبًا!) بإرشاد بسيط إلى حد ما لتوليد sajests التي تعمل لكل من نقطة البداية "A" ونقطة النهاية "B". وتجدر الإشارة على الفور إلى أن الاستدلال لم ينجح في سجل سفر المستخدم ، ولكن على سجل النقرات على نتائج البحث ، مما أدى إلى بعض المشاكل. هذه الأشياء نسميها "القمم" (من الإنجليزية. الانتقاء ). بدا الاستدلال هكذا:

1. بالنسبة للمستخدم الحالي ، نأخذ جميع قممه التاريخية.
2. نحن نصفيهم ، ونترك لهم نفس الهدف (من / أين).
3. , , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
4. , , , , , .
5. , , 3:00 14:00, , .
6. - (), , - .
7. .

عملت هذه الخوارزمية لفترة من الوقت ، وكانت جيدة بشكل عام لأخصائيي القيمة المضافة (سنتحدث عن المقاييس بعد ذلك بقليل) ، ولكن كان لها عدد من العيوب. بالإضافة إلى منطق العمل البدائي ، لم يكن يعتمد على الرحلات ، ولكن على اختيارات المستخدم. لهذا السبب ، يحصل المستخدمون أحيانًا على نتائج بحث غير واضحة. وأيضًا ، نظرًا للطريقة "المحددة" لتخزين تاريخ القمم ، كان من الصعب إجراء تحليلات سريعة. بناءً على ذلك ، قررنا تجربة تطبيق التعلم الآلي. بعد ذلك ، سننظر في صياغة مشاكل الترتيب ونختصر مشكلتنا إلى تصنيف ثنائي.

بيان ترتيب المشكلة

قبل الحديث عن الميزات والمقاييس والنموذج ، نحتاج إلى معرفة نوع المشكلة التي نحاول حلها. دعنا نذهب بشكل متكرر ونحاول أولاً صياغة صياغة عامة لمشكلة الترتيب. تبدو هكذا:



$$$X$ - الكثير من الأشياء.



$$$X^l = \{x_1, \dots, x_l \}$ - عينة تدريب. 



$$$i \prec j$ - الترتيب الصحيح في أزواج $$$(i, j)$



الهدف: بناء وظيفة الترتيب $$$a: X \rightarrow ℝ$، مع ماذا 

$$

$$i \prec j ⇒  a(x_i) < a(x_j)$$

لنقم الآن بصياغة مهمة ترتيب نتائج البحث حسب الاستعلام. إنها تختلف عن مشكلة التصنيف العامة في أنه بدلاً من المجموعة العامة للكائنات التي نحتاج إلى تصنيفها ، تظهر مجموعتان$$$D$ و $$$Q$ - العديد من المستندات والاستفسارات.



$$$D$ - جمع الوثائق (الإجابات).



$$$Q$ - الكثير من الطلبات.



$$$D_q \subseteq D$ - مجموعة المستندات التي تم العثور عليها بواسطة الاستعلام q.



$$$X = Q \times D$ - الكائنات عبارة عن أزواج "طلب ، مستند": $$$x \equiv (q, d), q \in Q, d \in D_q$



$$$Y$ - مجموعة مرتبة من التصنيفات (التصنيفات).



$$$y(q, d): X \rightarrow Y$- درجات الصلة.



كلما زادت النتيجة$$$y(q, d)$، كلما زادت صلة الوثيقة $$$d$ طلب $$$q$...



يتم تحديد الترتيب الصحيح فقط بين تلك المستندات التي تم العثور عليها بواسطة نفس الاستعلام$$$q$: 

$$

$$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$$

في مهمتنا المتمثلة في التوصية بنقاط نهاية المسار ، تكون مجموعة التصنيفات ثنائية. بالنسبة للمستخدم ، قد يكون العنوان المقترح ذا صلة أو غير ذي صلة (باستثناء الحالات ذات المسار المعقد مع نقاط نهاية متعددة). إذا اعتبرنا المهمة في سياق المستخدم ، إذن$$$q$- طلب إلى الخدمة ، والذي يحتوي على هوية العميل والموقع الجغرافي والتاريخ والوقت ؛$$$D_q$- العديد من نقاط النهاية التاريخية "ب" لرحلات المستخدم (نحن نقدم اقتراحات فقط بناءً على عناوين الرحلات السابقة). وكل إجابة صحيحة$$$d \in D_q$ تحت الطلب $$$q$ يمكن أن تكون ذات صلة بالمستخدم (من النقطة الحالية وفي الوقت الحالي ، يحتاج المستخدم للذهاب هنا بالضبط) أو غير ذي صلة.



من أجل الاكتمال ، يبقى فقط وصف عملية تكوين عينة من أزواج الطلب والاستجابة مع الهدف. ضع في اعتبارك ، من أجل التبسيط ، عميلاً واحدًا لديه 5 رحلات. لنرتب هذه الرحلات من الأول إلى الأخير. بالنسبة للرحلة الأولى ، لا نعرف أي شيء عن رحلات المستخدم ، لذلك لا يمكننا أن نقدم له أرقى باستخدام خوارزمية التعلم الآلي الموصوفة (يعمل هنا الاسترشاد بالمستخدمين الجدد). بالنسبة للرحلة الثانية ، نعرف الوجهة النهائية من الرحلة الأولى ويمكننا تقديم هذا العنوان للمستخدم إذا نجح في اجتياز إجراء المعالجة اللاحقة (يقع على بعد أكثر من كيلومتر واحد من الموقع الحالي ، في نفس المنطقة ، وما إلى ذلك). للرحلة الثالثة ، قد يكون لدينا بالفعل من واحد إلى اثنين من الأشياء المحتمَلة ،إذا كان عنوان نهاية الرحلة الثانية هو نفس عنوان نهاية الرحلة الأولى وإذا كانت عناوين النهاية مختلفة ، على التوالي. إذا تزامن sajest مع نقطة النهاية "B" (أي ، سقطت في نفس سداسي عشري بحجم ثابت) ، فسنحدد 1 كهدف ، وإلا - 0. وفقًا لهذه الخوارزمية ، نشكل جميع أنواع أزواج النموذج "طلب - (ممكن) استجابة "لكل عميل.



وبالتالي ، قمنا بتقليص مشكلة الترتيب إلى مشكلة تصنيف ثنائي. الآن يمكننا التحدث عن مقاييس تقييم الجودة.

المقاييس

في مسائل الترتيب ، مقياس يوضح نسبة الإجابات الصحيحة من المستندات $$$D_q$ إلى الأعلى $$$n$ قائمة الترتيب عند الطلب $$$q$تسمى Precision @ n . نحن مهتمون بـ Precision @ 1/2/3 ، نظرًا لأن إجمالي معدل النقر على المراكز الثلاثة الأولى يبلغ حوالي 95٪. في الوقت نفسه ، لا يوجد سوى عنوان نهائي واحد صحيح (بطبيعة الحال ، إذا أراد المستخدم المغادرة للحصول على عنوان من سجله) ، لذلك ، فإن هذا المقياس سيعرض فقط نسبة الحالات عندما تقع النقطة النهائية الصحيحة "ب" في أعلى 1/2/3 العناوين التي اقترح خوارزمية لدينا.



أذكر ذلك في مشكلتنا$$$Y = \{0, 1\},\; y(q, d)$ - ملاءمة، $$$a(q, d)$هي وظيفة الترتيب المطلوبة. ثم يمكن كتابة Precision @ n على النحو التالي:

$$

$$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$$

علامات ونموذج

يمكن تقسيم ميزات النموذج في مشكلتنا إلى عدة كتل:

• للمستند فقط $$$d \in D_q$ (العنوان النهائي ، النقطة "ب").
• للطلب فقط $$$q$ (عنوان البداية ، النقطة "أ").
• مشترك في الطلب والتوثيق $$$(q, d)$ (المسار من "أ" إلى "ب").
• عام للمستخدم.

فيما يلي بعض الأمثلة لكل منهم.



أمثلة على علامات الوثيقة فقط (النقطة "ب"):

1. عدد الرحلات إلى النقطة "B" في آخر K يوم.
2. عدد الرحلات إلى النقطة "ب" حسب اليوم من الأسبوع والوقت من اليوم.
3. متى كانت الرحلة السابقة للنقطة "ب".
4. علم أن الرحلة السابقة تمت للنقطة "ب".
5. هي النقطة "ب" العنوان المختار / المنزل / العمل.

أمثلة على الخصائص للطلب فقط $$$q$ ( «» + /):

1. , .
2. «».
3. «» K .
4. «» .
5. «» //.
6. / $$$q$.
7. «».

, $$$(q, d)$ ( «» “”):

1. , .
2. .
3. .

:

1. K .
2. .
3. إحصائيات الرحلة التاريخية (المتوسط ​​، الكميات ، متوسط ​​مسافة الرحلة ، إلخ).

نتيجة لذلك ، حصلنا على أكثر من 100 ميزة تصف زوجًا من كائنات "مستند الطلب". نظرًا لأننا نريد تعظيم الدقة @ 1/2/3 ، فمن المنطقي أننا بحاجة إلى التنبؤ باحتمالية رحلة المستخدم إلى وجهة معينة وترتيب المرشحين المحتملين وفقًا للاحتمال الذي تم الحصول عليه. لقد جربنا خوارزميات مختلفة ووظائف خسارة مختلفة ، واستقرنا على تعزيز التدرج على الأشجار وخسارة اللوغوس . النتائج التي تم الحصول عليها في وقت استخدام الكشف عن مجريات الأمور:

إنتاج

بطبيعة الحال ، قبل التوصل إلى بعض الخوارزميات والميزات ونماذج التدريب المعقدة ، تحتاج إلى التفكير في كيفية عمل كل هذا في القتال تحت الحمل ، مع عدم نسيان التوسع. بعد أن اجتمعنا مع فريق تطوير الواجهة الخلفية ، قمنا برسم مخطط تقريبي لكيفية ظهور خدمتنا. قررنا تغليف نموذج التعلم الآلي المُدرَّب في إطار عمل الويب غير المتزامن بانتظار Sanic، والتي سترسل خدمة البحث الطلبات إليها. بالإضافة إلى التحجيم الرأسي ، قمنا بتنفيذ القدرة على النشر إلى أجهزة متعددة. سيتم إرسال الطلبات إلى الخدمة إلى عنوان URL لموازن التحميل ، ثم يتم إنشاء وكيل لهذا الجهاز أو ذاك باستخدام خوارزمية Round-robin. بعد تنفيذ النموذج الأولي الأول للخدمة ، أدركنا أنه يمكننا تقليل حجم الاستعلامات بشكل كبير في MySQL. نظرًا لأن أي تغيير في الدبوس مع اختيار نقطة التغذية هو طلب بحث جديد ، وبالتالي لخدمتنا ، فقد اعتقدنا أنه يمكننا تخزين ذاكرة تخزين مؤقت مع سجل سفر المستخدم لمدة N دقيقة من لحظة الطلب إلى Redis. بفضل هذا ، قمنا بتقليل الحمل على القاعدة ثلاث مرات. نتيجة لذلك ، يمكن تمثيل مخطط الخدمة على النحو التالي:







نقوم بتخزين الطلبات على الخدمة وردودها في ElasticSearch ، كما نقوم بنقل ومراقبة المقاييس المسؤولة عن استقرار العمل في NewRelic.



سير العمل العام لخدمتنا:

1. ترسل خدمة البحث طلبًا إلى خدمة تلميحات البحث.
2. يقوم الموازن بتحديد إحدى الآلات وإرسال هذا الطلب إليها.
3. داخل الجهاز ، يتم إرسال الطلب إلى أحد العمال المفتوحين أو يدخل في قائمة الانتظار.
4. داخل العامل:
   1. نحن نتحقق من صحة الطلب الوارد.
   2. نحن نقدم طلبًا في Redis ، إذا لم يكن هناك سجل طلبات للمستخدم ، فسنذهب إلى MySQL ونكتب البيانات المستلمة إلى Redis.
   3. نقوم بمعالجة البيانات الأساسية وجمع الميزات للنموذج.
   4. نقوم بذلك predict_proba()وفقًا لكل الأحزان المتولدة ونفرزها وفقًا لـ "الاحتمال".
   5. نقوم بمعالجة إضافية للبيانات ونشكل الرد.
   6. نعود الجواب لخدمة البحث.

ماذا بعد؟

نحن الآن نختبر نموذجنا بنشاط باستخدام اختبار التبديل من أجل استخلاص النتائج لاحقًا وتنفيذ إضافات إضافية للخوارزمية لتحسين جودة الترتيب. في المستقبل ، سنحاول إضافة ميزات إضافية إلى النموذج ، وكذلك ، مع مصممي المنتج ، نعد حلاً جديدًا لـ "عرض" sagests. بالطبع ، سيكون من الرائع أن يفهم تطبيقنا نفسه أين / متى / أين / بأي سيارة يريد المستخدم المغادرة. نحن نعمل في جميع الاتجاهات بحيث يتم إجراء طلب سيارة أجرة بالفعل بنقرة واحدة.