Introduction: Autonavi’s vision is to connect the real world and make travel better. In order to realize the vision, we need to handle the smart link between LBS big data and users. Information retrieval is the key technology, and search suggestion is an indispensable part of retrieval service.

This paper will mainly introduce the specific application of machine learning in Autonavi search suggestions, especially some attempts in model optimization. These explorations and practices have been verified and achieved good results, and laid a foundation for the application of personalization, deep learning and vector index in the following years.

Reconstruct the search sort module

Search suggestions refer to: When users enter query in the input box, query or POI (Point of Interest, geographical information system can be shops, residential areas, bus stations, etc.) will be automatically completed for users, and all candidates after completion will be listed and intelligentially sorted.



We hope to reduce the input cost of users through suggest service: intelligent prompt. It is characterized by fast response and no complex query retrieval, so it can be regarded as a simplified VERSION of LBS domain information retrieval service.

Like the general IR system, suggest is divided into two stages: recall and sort of DOC (DOC in LBS is POI). In the sorting stage, the text correlation of Query and DOC is mainly used, as well as the characteristics of DOC itself (weight and click), to carry out weighted score sorting.

However, with the continuous development of business and the increasing scale of features, manual parameter tuning becomes increasingly difficult, and it is difficult to obtain satisfactory results by rule-based sorting. In this case, various patches will have to be made to solve the business problem, making the code difficult to maintain.



Therefore, we decided to reconstruct the ordering module, and Learning to Rank is undoubtedly a good choice.

Challenges: sample construction, model tuning

Learning to Rank (LTR) is a machine Learning method to solve the sorting problem in retrieval system. Gbrank is the most commonly used model in the industry, and Pair WISE is the most commonly used loss solution, which is also consistent here. When LTR is used to solve practical problems, one of the most important problems is how to obtain samples.

First of all, amap has a huge number of page views every day, and the number of candidate POI hidden behind this is astronomical. It is obviously unrealistic to obtain samples through manual annotation.

Second, if you want to use some method of automatic sample construction, such as building sample pairs based on user clicks on POI, you will also encounter the following problems:

• Easy to click on the fit, click on what, what results will be given later. • Sometimes clicking behavior is not a measure of true satisfaction. •suggest the front end only shows the top10 results, more results have no chance to show to the user, naturally no click. • Some users are used to entering a complete query for search, but do not use the completion results of the search suggestions, so the needs of these users cannot be counted.

These problems can be summed up as: modeling without clickable data is confusing. But even a click on a POI doesn’t mean the user is actually satisfied.

Finally, in model learning, we also face the challenge of feature sparsity. The goal of statistical learning is to minimize the global error. Sparse features are often ignored by models due to the small number of samples they affect. But in practice, the solution of some middle-long tail cases often depends on these features. Therefore, how to tune the model learning process is very important.

Detailed explanation of system modeling process

In the previous section, we described two modeling challenges, one is how samples are constructed and the other is how models learn to tune. Let’s first look at how to solve the sample construction problem. Our solution is:

• Consider the user’s behavior session in the travel scene, not only based on a click behavior of suggest, but more importantly, investigate the user’s behavior sequence in the travel scene. For example, suggest what word to search for after giving a search suggestion, go where to go, etc.

• Rather than counting clicks on a single query, consider the session as a whole, and the user’s click behavior at the end of the session is generalized to all queries in the session.

Detailed scheme

As shown below:



Finally, more than one million random queries of online click logs are extracted, and the first N candidate POIS are recalled for each query. By using the above sample construction scheme, at most tens of millions of effective samples can be used as training samples of GBRANK.

In terms of features, four modeling requirements are mainly considered, each of which has a corresponding feature design scheme:

• There are multiple recall links, including: different cities, pinyin recall. Therefore, a feature design is needed to solve the comparability between different recall links. • The target POI is not static but dynamic as the user continues to input. You need a feature that can represent dynamic requirements under different Queries. • Low-frequency long-tail Query, no click and other posterior features, need to supplement the prior features. •LBS service, with strong regional personalized demand. The needs of users vary greatly from region to region. In order to realize regional personalization and achieve a thousand domains and dimensions, the geohash algorithm is first used to fragment the geographic space, and each fragment gets a string of unique identifiers. This makes it possible to count characteristics separately on this identifier (shard).



Detailed feature design is shown in the following table:



After feature design is completed, necessary feature engineering is carried out, including scale scaling, feature smoothing, position bias removal, normalization and so on, in order to give better play to the role of features. I won’t explain too much here.

In the first version of the model, all the rules were dropped, and the MRR improved by about 5 points in the test set. However, there were also some problems in the model learning, such as the uneven learning of GBRANk features. When the tree nodes split, only a few features are selected, and the other features do not come into play.

This brings us to the second modeling challenge mentioned earlier: the problem of tuning model learning. Specifically, how to solve the problem of uneven selection of GBRANK features. Now, let’s explain it in detail.

Let’s look at the feature importance of the model. As shown below:



After analysis, the main reasons for the imbalance of feature learning are as follows:

• The cross feature query-click has a high degree of absence, with the eigenvalue 0 in 60% of the samples. The tree node splitting benefit of this feature is small and the feature cannot be selected. In fact, however, in the case of sufficient clicks, the query-click click is closer to the user’s actual intention than city-click. • For text similar features, although not missing, but its forward and reverse order is low, so the node splitting benefit is also lower than city-click, also cannot be selected.

To sum up, due to various reasons, the same feature (city-click) is repeatedly selected as the tree node during feature selection in the process of tree model learning, making other features fail to play their due roles. There are two solutions to this problem:

• Method 1: Over-sample the sparse feature samples and the low-frequency Query samples to increase the splitting benefit. The advantage is that the implementation is simple, but the disadvantage is also obvious: the real distribution of samples is changed, and the over-sampling is effective for all features, so the adjustment goal cannot be flexibly realized. We chose method two. • Method 2: Adjust loss Function. According to the characteristic difference of the two samples, the negative gradient (residual) is modified, so as to modify the next splitting benefit of this feature. For example, for the samples with non-missing Query-click feature, loss will be generated when learning mistakes. Adjusting Loss is to add penalty item LOss_DIff to this loss. With the increase of loss, the splitting benefit of the next tree increases, and then the probability of the Query-click feature being selected as the splitting node increases.

The specific calculation formula is as follows:



The above formula is the negative gradient of the cross entropy loss function, loss_diff is equivalent to a translation of the SIGmod function.



The larger the difference, the greater the LOSS_DIff, the greater the penalty, and the greater the splitting benefit of this feature in the corresponding next iteration.

After loss adjustment, the model was retrained, and the MRR of the test set was improved by 2 points on the basis of the initial model. At the same time, the settlement ratio of historical sorting cases has been increased from 40% to 70%, which is obviously effective.

Write in the last

At present, we have completed the modeling of crowd personalization and individual personalization, and are actively promoting the application of deep learning, vector index and user behavior sequence prediction in Autoravi search suggestions.


Author: Autonavi Technology

The original link

This article is the original content of the cloud habitat community, shall not be reproduced without permission.