שירות מוניות טוב צריך להיות בטוח, אמין ומהיר. המשתמש לא יכנס לפרטים: חשוב לו שילחץ על כפתור ה"הזמנה" ויקבל רכב במהירות האפשרית שתיקח אותו מנקודה א' לנקודה ב'. אם אין רכבים בקרבת מקום, השירות צריך מיד להודיע על כך כדי ללקוח לא היו ציפיות שווא. אבל אם השלט "אין מכוניות" מופיע לעתים קרובות מדי, אז זה הגיוני שאדם פשוט יפסיק להשתמש בשירות זה וילך למתחרה.
במאמר זה אני רוצה לדבר על איך, באמצעות למידת מכונה, פתרנו את הבעיה של חיפוש מכוניות באזורים בצפיפות נמוכה (במילים אחרות, שם, במבט ראשון, אין מכוניות). ומה יצא מזה.
פרהיסטוריה
כדי להתקשר למונית המשתמש מבצע כמה שלבים פשוטים, אבל מה קורה בתוך השירות?
| משתמש | שלב | Backend Yandex.Taxi |
|---|---|---|
| בוחר את נקודת ההתחלה | סיכה | אנו משיקים חיפוש פשוט אחר מועמדים - חיפוש סיכות. בהתבסס על הדרייברים שנמצאו, זמן ההגעה חזוי - ETA בפין. מחושב מקדם הגדלת בנקודה נתונה. |
| בוחר יעד, תעריף, דרישות | הַצָעָה | אנו בונים מסלול ומחשבים מחירים לכל התעריפים תוך התחשבות במקדם הגובר. |
| לוחץ על כפתור "התקשר למונית". | סיכום | אנו פותחים בחיפוש מלא אחר המכונית. אנו בוחרים את הנהג המתאים ביותר ומציעים לו הזמנה. |
על , и כבר כתבנו. וזה סיפור על מציאת נהגים. כאשר נוצרת הזמנה, החיפוש מתרחש פעמיים: על הסיכה ועל ההזמנה. חיפוש ההזמנה מתבצע בשני שלבים: גיוס מועמדים ודירוג. ראשית, נמצאו נהגים מועמדים זמינים הקרובים ביותר לאורך גרף הדרך. לאחר מכן מופעלים בונוסים וסינון. שאר המועמדים מדורגים והזוכה מקבל הצעת הזמנה. אם הוא מסכים, הוא משויך להזמנה וניגש לנקודת המסירה. אם הוא מסרב, אז ההצעה מגיעה להצעה הבאה. אם אין עוד מועמדים, החיפוש מתחיל שוב. זה נמשך לא יותר משלוש דקות, ולאחר מכן ההזמנה מבוטלת ונשרפת.
חיפוש על סיכה דומה לחיפוש על הזמנה, רק שההזמנה לא נוצרת והחיפוש עצמו מתבצע פעם אחת בלבד. נעשה שימוש גם בהגדרות פשוטות של מספר המועמדים ורדיוס החיפוש. פשטות כאלה נחוצות כי יש בסדר גודל יותר סיכות מאשר פקודות, וחיפוש הוא פעולה די קשה. נקודת המפתח לסיפור שלנו: אם במהלך החיפוש המקדים לא נמצאו מועמדים מתאימים בפין, אז אנחנו לא מאפשרים לכם לבצע הזמנה. לפחות ככה זה היה פעם.
זה מה שהמשתמש ראה באפליקציה:
חפש מכוניות ללא מכוניות
יום אחד הגענו להשערה: אולי במקרים מסוימים עדיין ניתן להשלים את ההזמנה, גם אם לא היו מכוניות על הסיכה. הרי עובר זמן מה בין הסיכה להזמנה, והחיפוש אחר ההזמנה שלם יותר ולעיתים חוזר על עצמו מספר פעמים: בזמן זה עלולים להופיע דרייברים זמינים. ידענו גם ההיפך: אם יימצאו נהגים על הסיכה, לא עובדה שימצאו אותם בעת ההזמנה. לפעמים הם נעלמים או שכולם מסרבים לפקודה.
כדי לבחון את ההשערה הזו, השקנו ניסוי: הפסקנו לבדוק את נוכחות המכוניות במהלך חיפוש בפין עבור קבוצת בדיקה של משתמשים, כלומר, הייתה להם הזדמנות לבצע "הזמנה ללא מכוניות". התוצאה הייתה די בלתי צפויה: אם המכונית לא הייתה על הסיכה, אז ב-29% מהמקרים היא נמצאה מאוחר יותר - בעת חיפוש לפי ההזמנה! יתרה מכך, הזמנות ללא מכוניות לא היו שונות משמעותית מהזמנות רגילות מבחינת שיעורי ביטולים, דירוגים ומדדי איכות נוספים. הזמנות ללא רכב היוו 5% מכלל ההזמנות, אך קצת יותר מ-1% מכלל הנסיעות המוצלחות.
כדי להבין מהיכן מגיעים המוציאים לפועל של פקודות אלה, בואו נסתכל על הסטטוסים שלהם במהלך חיפוש על סיכה:
- זמין: היה זמין, אבל משום מה לא נכלל במועמדים, למשל, הוא היה רחוק מדי;
- בהזמנה: היה עסוק, אבל הצליח להשתחרר או להתפנות ;
- עסוק: היכולת לקבל הזמנות הושבתה, אבל אז הנהג חזר לקו;
- לא זמין: הנהג לא היה מקוון, אבל הוא הופיע.
בואו נוסיף אמינות
הזמנות נוספות הן נהדרות, אבל 29% מהחיפושים המוצלחים אומר ש-71% מהמקרים המשתמש חיכה זמן רב ובסופו של דבר לא הלך לשום מקום. למרות שזה לא דבר רע מנקודת מבט של יעילות המערכת, זה בעצם נותן למשתמש תקוות שווא ומבזבז זמן, שלאחר מכן הוא מתעצבן ו(אולי) מפסיק להשתמש בשירות. כדי לפתור בעיה זו, למדנו לחזות את הסבירות שתימצא מכונית בהזמנה.
התוכנית היא כדלקמן:
- המשתמש שם סיכה.
- חיפוש מתבצע על הסיכה.
- אם אין מכוניות, אנו צופים: אולי הן יופיעו.
- ובהתאם להסתברות, אנו מאפשרים או לא מאפשרים לבצע הזמנה, אך אנו מזהירים כי צפיפות המכוניות באזור זה בזמן זה נמוכה.
באפליקציה זה נראה כך:
השימוש במודל מאפשר ליצור הזמנות חדשות בצורה מדויקת יותר ולא להרגיע אנשים לשווא. כלומר, לווסת את יחס האמינות ומספר ההזמנות ללא מכונות באמצעות מודל הדיוק-ריקול. אמינות השירות משפיעה על הרצון להמשיך ולהשתמש במוצר, כלומר בסופו של דבר הכל מסתכם במספר הנסיעות.
קצת על דיוק-ריקולאחת המשימות הבסיסיות בלמידת מכונה היא משימת הסיווג: הקצאת אובייקט לאחת משתי מחלקות. במקרה זה, התוצאה של אלגוריתם למידת מכונה הופכת לעתים קרובות להערכה מספרית של חברות באחת השיעורים, למשל, הערכת הסתברות. עם זאת, הפעולות שמתבצעות הן בדרך כלל בינאריות: אם המכונית זמינה, אז ניתן לך להזמין אותה, ואם לא, אז לא נעשה. אם להיות ספציפיים, בואו נקרא לאלגוריתם שמייצר אומדן מספרי מודל, ולסווג כלל שמשייך אותו לאחת משתי מחלקות (1 או -1). כדי ליצור מיון המבוסס על הערכת המודל, עליך לבחור סף הערכה. איך בדיוק תלוי מאוד במשימה.
נניח שאנו עושים בדיקה (מסווג) לאיזו מחלה נדירה ומסוכנת. בהתבסס על תוצאות הבדיקה, אנו שולחים את המטופל לבדיקה מפורטת יותר, או אומרים: "יופי, לך הביתה". עבורנו, שליחת חולה הביתה היא הרבה יותר גרועה מבדיקה מיותרת של אדם בריא. כלומר, אנחנו רוצים שהבדיקה תעבוד עבור כמה שיותר אנשים חולים באמת. ערך זה נקרא recall =. למסווג אידיאלי יש ריקול של 100%. מצב מנוון הוא לשלוח את כולם לבדיקה, אז גם הריקול יהיה 100%.
זה קורה גם הפוך. לדוגמה, אנחנו מייצרים מערכת בדיקות לסטודנטים, ויש לה גלאי רמאות. אם פתאום הצ'ק לא עובד בחלק מהמקרים של רמאות, אז זה לא נעים, אבל לא קריטי. מצד שני, זה רע מאוד להאשים תלמידים שלא בצדק במשהו שהם לא עשו. כלומר, חשוב לנו שבין התשובות החיוביות של המסווג יהיו כמה שיותר נכונות, אולי לרעת מספרן. זה אומר שאתה צריך למקסם את הדיוק = . אם ההפעלה מתרחשת בכל האובייקטים, אזי הדיוק יהיה שווה לתדירות המחלקה המוגדרת במדגם.
אם האלגוריתם מייצר ערך הסתברות מספרי, אז על ידי בחירת ספים שונים, אתה יכול להשיג ערכי דיוק-זכירה שונים.
בבעיה שלנו המצב הוא כדלקמן. ריקול הוא מספר ההזמנות שאנו יכולים להציע, דיוק הוא האמינות של הזמנות אלו. כך נראית עקומת הזכירה הדיוק של הדגם שלנו:
יש שני מקרי קיצון: לא לאפשר לאף אחד להזמין ולאפשר לכולם להזמין. אם אתה לא מאפשר לאף אחד, הריקול יהיה 0: אנחנו לא יוצרים פקודות, אבל אף אחת מהן לא תיכשל. אם נאפשר לכולם, הריקול יהיה 100% (נקבל את כל ההזמנות האפשריות), והדיוק יהיה 29%, כלומר 71% מההזמנות יהיו גרועות.
השתמשנו בפרמטרים שונים של נקודת ההתחלה כסימנים:
- זמן/מקום.
- מצב מערכת (מספר המכונות התפוסות של כל התעריפים והסיכות בסביבה).
- פרמטרי חיפוש (רדיוס, מספר מועמדים, הגבלות).
עוד על השלטים
מבחינה קונספטואלית, אנו רוצים להבחין בין שני מצבים:
- "יער עמוק" - אין כאן מכוניות בשלב זה.
- "חוסר מזל" - יש מכוניות, אבל בחיפוש לא היו מתאימות.
דוגמה אחת ל"חוסר מזל" היא אם יש ביקוש רב במרכז ביום שישי בערב. יש הרבה הזמנות, הרבה אנשים מוכנים, ואין מספיק נהגים לכולם. זה עשוי להתברר כך: אין דרייברים מתאימים בסיכה. אבל ממש תוך שניות הם מופיעים, כי בזמן הזה יש הרבה נהגים במקום הזה והסטטוס שלהם משתנה כל הזמן.
לכן, אינדיקטורים שונים של מערכת בסביבת נקודה A התבררו כמאפיינים טובים:
- מספר כולל של מכוניות.
- מספר מכוניות בהזמנה.
- מספר המכוניות שאינן זמינות להזמנה בסטטוס "עסוק".
- מספר משתמשים.
אחרי הכל, ככל שיש יותר מכוניות, כך גדל הסיכוי שאחת מהן תהיה זמינה.
למעשה, חשוב לנו שלא רק מכוניות יאותרו, אלא שיבוצעו גם טיולים מוצלחים. לכן, ניתן היה לחזות את ההסתברות לטיול מוצלח. אבל החלטנו לא לעשות זאת, כי הערך הזה תלוי מאוד במשתמש ובנהג.
אלגוריתם אימון המודל היה . נתונים שהתקבלו מהניסוי שימשו לאימון. לאחר היישום, היה צורך לאסוף נתוני הדרכה, ולעיתים מאפשרים למספר קטן של משתמשים להזמין כנגד החלטת המודל.
תוצאות של
תוצאות הניסוי היו כצפוי: השימוש במודל מאפשר להגדיל משמעותית את מספר הנסיעות המוצלחות עקב הזמנות ללא מכוניות, אך ללא פגיעה באמינות.
נכון לעכשיו המנגנון הושק בכל הערים והמדינות ובעזרתו מתרחשים כ-1% מהטיולים המוצלחים. יתרה מכך, בערים מסוימות עם צפיפות מכוניות נמוכה, חלקן של נסיעות כאלה מגיע ל-15%.
פוסטים נוספים על טכנולוגיית מוניות
מקור: www.habr.com