How machine learning will help, when every minute counts

 3r33333. 3r3-31. Imagine that you need to call a taxi. You open the application, see that the car will arrive in seven minutes, click "Order" - and the car is 15 minutes away from you, if it is found at all. Agree, unpleasant? 3r33354.  3r33333. 3r33354.  3r33333. Under the cut, let's talk about how machine learning methods help Yandex.Taxi to better predict ETA (Estimated Time of Arrival). 3r33354.  3r33333. 3r33354.  3r33333. How machine learning will help, when every minute counts 3r33170. 3r33354.  3r33333. 3r33354.  3r33333. To begin, we recall that the user sees in the application before ordering:
 3r33333. 3r33354.  3r33333. 3r33354.  3r33333. 3r33354.  3r33333. The blue points on the map are the best points for boarding a taxi. Red pin - the point to which the user calls a taxi. The pin shows how long the car will arrive. In an ideal world. But in the real world, other people nearby also call themselves a car through the Yandex.Taxi application. And we do not know which car will go to whom, because they are distributed only after the order. If the machine is already assigned, for the forecast, we will use the Yandex.Map routing and the time when moving along the optimal path. This time (perhaps with a small margin) we will show the user immediately after ordering. The question remains: how to predict ETA before ordering? 3r33354.  3r33333. 3r33354.  3r33333. And here comes machine learning. We make a sample with the objects and the correct answers and train the algorithm to guess the answer according to the features of the object. In our case, the objects are user sessions, the answers are the time after which the car actually arrived. Signs of the object can be numerical parameters known before ordering: the number of drivers and users of the application next to the pin, the distance to the nearest service vehicles and other potentially useful values. 3r33354.  3r33333. 3r33354.  3r33333. 3r33333. Why it matters
3r33354.  3r33333. 3r33354.  3r33333. In an ideal world, people do everything in advance and always plan their time accurately. But we live in the real world. If a person is late for work or, even worse, at the airport, it is important for him to understand whether he will have time to leave and get to his destination. 3r33354.  3r33333. When deciding what to order, the future passenger is guided, including waiting time. It can be very different in different applications for calling a taxi, and in different rates of one application. So that the user does not regret the choice, it is very important to show the exact ETA. 3r33354.  3r33333. 3r33354.  3r33333. It seems simple. Come up with more signs, train a model, for example CatBoost, predict the time before the car arrives - and you can finish on this. But experience shows that it is better not to hurry and think carefully, and then do it. 3r33354.  3r33333. 3r33354.  3r33333. At first, we had no doubt that it was necessary to predict the time after which the driver would actually arrive at the user. Yes, before ordering, we do not know for sure which machine will be assigned. But we can predict ETA using data not about a specific driver, but about drivers in the vicinity of the order. Of course, the forecast must be fair enough that the user can plan time. 3r33354.  3r33333. 3r33354.  3r33333. But what does “honest” mean? After all, any prediction algorithm is good or good only statistically. There are also successful, and frankly bad results, but it is necessary “on average” not to deviate much from the correct answers. Here we must understand that "on average" is different. For example, the average is at least three concepts from statistics: expectation, median, and fashion. The picture from Darella Huff's great book “How to lie with the help of statistics” perfectly shows the difference: 3r33354.  3r33333. 3r33354.  3r33333. 3r362. 3r33354.  3r33333. 3r33354.  3r33333. We want the model to be on average a little mistaken. Depending on the value “on average”, there are two options for assessing the quality of forecasts. The first option is to show the user the expected time before the arrival of a taxi. As a result, a model that minimizes the average square of the forecast error (Mean Squared Error, MSE) will be trained:
 3r33333. 3r33354.  3r33333.
3r399.
3r33354.  3r33333. 3r33354.  3r33333. Here is

- correct answers, 3r399. 3r3386.
- model predictions. 3r33354.  3r33333. 3r33354.  3r33333. Another option is not to be mistaken with the ETA forecast mainly in one direction, up or down. In this case, we will show the user the median time distribution before the arrival of a taxi. As a result, a model that optimizes the average module of the forecast error (Mean Absolute Error, MAE) will be trained:
 3r33333. 3r33354.  3r33333.
3r399. 3r3-300.
3r33354.  3r33333. 3r33354.  3r33333. But we realized that we are a little ahead. 3r33354.  3r33333. 3r33354.  3r33333. 3r33333. Rethinking Problem Setting
3r33354.  3r33333. 3r33354.  3r33333. After the appointment, we know what kind of car goes to the user, which means we can estimate its travel time on Yandex.Maps. This time is shown in the pin after the order. On the one hand, we now have more information and the forecast will be more accurate, but, on the other hand, this is also an estimate with an error. 3r33354.  3r33333. 3r33354.  3r33333. That was the catch in the ETA pin problem. Until the driver is appointed, it is necessary to predict exactly the time that Yandex.Map routing will show later, and not the actual time before the filing machine. 3r33354.  3r33333. 3r33354.  3r33333. It would seem that nonsense: instead of the exact value, take as a target a different forecast? But it makes sense, and here's why. On the way to you, the designated machine may linger. The driver got into a dangerous situation on the road, in a traffic jam due to an accident or went out to buy water. Such delays are difficult to predict. They create additional noise in the target variable, due to which the already difficult task of predicting ETA in pin becomes even more difficult. 3r33354.  3r33333. 3r33354.  3r33333. How to get rid of noise? Predict the smoothed target variable — the time that is displayed after the machine is assigned based on the route to the user. 3r33354.  3r33333. 3r33354.  3r33333. This is also the logic from the business point of view: you can’t throw out the travel time on the optimal way from ETA anyway, but additional delays can be reduced by working with drivers. 3r33354.  3r33333. 3r33354.  3r33333. 3r33333. Quality metrics, data, model and training
3r33354.  3r33333. 3r33354.  3r33333. We found out that for ETA in Pina it is necessary to predict not the actual time, but the time that will be obtained after the machine is assigned along the route. Of the two quality metrics, MAE and MSE, we chose MAE. Perhaps from the point of view of the intuitiveness of the forecast, it is more logical to evaluate the expectation (MSE), rather than the median (MAE). But MAE has a nice feature: the model is more resistant to emissions (outliers) among training examples. 3r33354.  3r33333. 3r33354.  3r33333. Signs are divided into groups:
 3r33333. - built on the current time; 3r33354.  3r33333. - geo (coordinates, distance to the city center and significant objects on the map); 3r33354.  3r33333. - pin (how many and what machines are nearby, their density is calculated differently); 3r33354.  3r33333. - statistics on the zone (as usual, we are mistaken, how many are predicted); 3r33354.  3r33333. - data on the nearest drivers (in what time they arrive, how much closer is the first closer than the second, etc.). 3r33354.  3r33333. 3r33354.  3r33333. On these signs, CatBoost was trained, of course. The decisive argument was that the gradient boost implemented in CatBoost over balanced trees has long established itself as a very powerful method of machine learning, and the method of encoding categorical features in CatBoost regularly justifies itself in our tasks. Another nice feature of the library is fast GPU training. 3r33354.  3r33333. 3r33354.  3r33333. Now a few words about which models were compared. The original ETA (until machine learning was specified) was calculated on the basis of the time for which the machine closest to the user can arrive. The current model (used in the application now) is what happened with the help of machine learning and 3r3-3755. what this article is about. 3r3176. In addition, the production will soon roll out a new model. It uses an order of magnitude more significant for solving the problem of signs. The table below shows the measurements of the quality of these models on historical data. By the way, we still have a lot of plans - 3r3169. come help
. 3r33354.  3r33333. 3r33354.  3r33333. 3r33175. ETA forecast quality for validation * 3r3176. 3r33354.  3r33333. 3r33354.  3r33333. 3r3181.  3r33333.
 3r33333.
3r33354.  3r33333.
 3r33333.
Mean Absolute Error
 3r33333.
 3r33333.
Error more than 1 minute
 3r33333.
 3r33333.
Error more than 2 minutes
 3r33333.
 3r33333.
Error more than 5 minutes
 3r33333.
 3r33333.
 3r33333.
 3r33333.
Original ETA 3r3-3322. 3r33354.  3r33333.
 3r33333.
???r3322. 3r33354.  3r33333.
 3r33333.
???r3322. 3r33354.  3r33333.
 3r33333.
??? r3r3322. 3r33354.  3r33333.
 3r33333.
???r3r3322. 3r33354.  3r33333.
 3r33333.
 3r33333.
 3r33333.
The current model is
3r33354.  3r33333.
 3r33333.
??? (–3.4)
3r33354.  3r33333.
 3r33333.
??? (–2.1)
3r33354.  3r33333.
 3r33333.
??? (–6.3)
3r33354.  3r33333.
 3r33333.
3 (–19.2)
3r33354.  3r33333.
 3r33333.
 3r33333.
 3r33333.
New model 3r3322. 3r33354.  3r33333.
 3r33333.
??? (–4.5)
3r33354.  3r33333.
 3r33333.
??? (–3.4)
3r33354.  3r33333.
 3r33333.
??? (–8.2)
3r33354.  3r33333.
 3r33333.
2.8 (–23.2)
3r33354.  3r33333.
 3r33333.
 3r33333.
3r33354.  3r33333. 3r33354.  3r33333. * Percentage (change in parentheses compared to baseline ETA). 3r33354.  3r33333. 3r33354.  3r33333. Machine learning allowed to win about two seconds, or 3.4% of the average deviation of the forecast. And in the new model - almost a second, a total of 4.5% already. But it is difficult to understand from these numbers that the ETA has improved significantly. To feel the benefits of machine learning, you should pay attention to the last column. Slips with a forecast of more than 5 minutes was 19.2%, and in the new model - even 23.2% less! By the way, such errors occur only in 3 and 2.8% of cases in models using machine learning. 3r33354.  3r33333. 3r33354.  3r33333. 3r33333. Results
3r33354.  3r33333. 3r33354.  3r33333. We refined the ETA in Pina mainly in order to provide users with a reliable forecast. But, of course, in any application of machine learning in business, it is imperative to evaluate the economic effect. And to understand whether it is comparable with the cost of building and implementing models. After the A /B test online, it turned out that we, using machine learning, received a statistically significant increase in conversion from order to trip (after all, the order can be canceled) and the increase in conversion from user session to order. 3r33354.  3r33333. 3r33354.  3r33333. In both cases, this is an effect of the order of 0.1 percentage points. This, by the way, does not contradict statistical significance: on our data volumes, even such a difference is reliably detected in 2–4 weeks. And with the importance for the business, in fact, everything is also quite good: it turned out that the cost of specifying the ETA is bounced off with a conversion increase in just a few months. 3r33354.  3r33333. 3r33354.  3r33333. As a result, we received a useful and illustrative case. The specification of the ETA in the pin has become an instructive story about the careful selection of the target variable. On the product side, this is a very motivating example: we improved the application and saw that users appreciated this. We hope, the updated ETA will help our passengers to keep up with meetings, trains and airplanes more often. 3r33333. 3r33333. 3r33333. 3r33333.
! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d,! 1): e.attachEvent ("onload", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r33333. 3r33333. 3r33333. 3r33333. 3r33333. 3r33333. 3r33333.
+ 0 -

Add comment