Please pay attention to the wechat public account “AI Front”, (ID: AI-front)
The traditional method of search sorting is to score items by various methods, and finally sort by the score of each item. Thus, traditional search ranking methods do not take into account the interaction between displayed items. Similarly, traditional methods of estimating CTR and CVR for a single item are based on the assumption that the CTR and CVR of the item will not be affected by other items being displayed at the same time (we call the display context). In fact, the display context of a commodity can affect users’ clicking or purchasing decisions: if the commodities around a commodity are similar to it but cheaper than it, the probability of users buying it will not be high; On the contrary, if the surrounding goods are more expensive than it, then the probability of users to buy it will increase.
How do you sort if you break the traditional ordering model and show the assumption that context doesn’t matter? For this reason, we first propose a global ranking method considering the interaction of goods. We describe e-commerce sequencing as a global optimization problem that targets Gross Merchandise Volume (GMV), a measure of customer satisfaction. To be precise, the optimization goal of global sorting is to maximize the mathematical expectation of GMV. To calculate the mathematical expectation of GMV, it is necessary to know the transaction probability of goods, and the transaction probability of goods affects each other. Therefore, we propose a transaction probability estimation model considering the interaction of goods.
First of all, we propose a global feature extension approach, in which the influences of other commodities are added into the probability estimation model in the form of global features when estimating the transaction probability of a commodity, so that the influences of other commodities are taken into account in the estimation. Then, we further propose an RNN model to accurately consider the effect of the order of goods on the probability of transaction. By using the RNN model, we turn e-commerce sorting into a sequence generation problem and use the Beam Search algorithm to find a better sort. We conducted a large number of experiments on the Taobao wireless main search platform, and achieved a GMV improvement of 5% compared with the taobao wireless main search algorithm at that time.
The input of the global sorting stage is N items to be sorted, and the output is the sorting result of N items.
We use S = (1… , N) represents the top N commodity sequence output by basic sorting; O stands for the full permutation set of S, O = (o1… , oN) ∈ O represents a permutation of S; In addition, di represents the position of commodity I in order O, that is, ODI = I; C (o, I) represents the presentation of commodity I in the contex global sequence T in the sequence O, and the specific definition will be discussed in different cases later.
V of I is the value of good I.
We define the target as GMV generated by this search, so in the case of given C (o, I), there can be:
The ultimate goal of global sorting is to find a sort with the highest expected payoff:
Finding this optimal sort requires solving two problems:
-
Q.1 p (I | c (o, I)) how to accurately estimate the probability.
-
Problem 2. Finding O ∗ is a combinatorial optimization problem, and the time complexity of violent search is N! Need to find a reasonable and efficient approximation algorithm.
Problem 1 is the key to improve the effect. The more accurate the estimation is, the more obvious the combinatorial optimization effect will be; otherwise, the combinatorial optimization in the second step will be meaningless. Theoretically, c(o, I) = (o1… , oN) is the complete presentation context of I, but if the presentation context is considered completely, the combinatorial optimization of problem 2 is complicated
It’s hard to go down. In order to solve problem 2 more efficiently, c(o, I) needs to be simplified appropriately. According to the degree of simplification of C (o, I), we divide the global sorting model into two classes, which are respectively introduced below.
E-commerce search global sorting method
The first type of model only uses information about the set of goods that present the context, without delving into the actual order of presenting the context, that is, C (o, I) = S ∖ {I}. The intuitive reason
Solution. The first type of model assumes that when a user decides whether to buy commodity I, he only remembers that he has seen all commodity set S, but does not care about the sequence of commodities in S.
In this case, the user knows his pick collection and compares and selects the items he wants to buy most. We change the feature of commodity I itself into local feature FI, L. Can put the goods partial features of the fi I at this moment, l comparing with the local characteristics of other commodity, get the goods characteristic and the candidate set other goods as a result, and the comparison of the results as a global information contains features added to the p (I (o, I) | c) forecast.
Taking the price feature as an example, we will sort S according to the price latitude, and uniformly normalize the price rank of commodity I into a value between [0 and 1] (the most expensive price becomes 1, and the cheapest price becomes 0), so that the price feature of I expands the global price feature of I.
In the above way, each dimension of FI and L can be extended according to its rank to obtain the corresponding global feature FI and G. Finally, we splicing the local and global features together as the feature fi = (fi, L, FI, G) of the commodity I displaying the context. Then show the context through the characteristics of extension and added to the model to help model predict clinch a deal the probability p (I | c (o, I)).
Under the assumption of the first type of model, combinatorial optimization of problem 2 becomes simple. The commodity set is static, so the transaction probability of each commodity can be calculated independently.
But within DNN calculate p (I (o, I) | c) without considering the goods I sort them accordingly, should according to the position bias of p (I (o, I) | c) to make a correction, namely, p (I | c (o, I)) bias (di). For solving the question 2, we don’t need to know specific bias (di) values, only need to know the bias, as the once upon a time, in turn, lower back position is ok, because at this time as long as according to v (I) p (I | c (o, I)) from high to low to sorting of goods, we will be able to get maximal profit.
The second type of model takes into account not only the information about the set of goods in the context, but also the precise order of goods before I. Similar to the first type of model, the commodity set information showing context is added to the feature of each commodity by extending the global feature, that is, FI = (Fi, L, FI, G). But, unlike the first model, calculation of p (I | c (o, I)), the second model also takes into consideration the real order of row in front of the I, namely, p (I | c (o, I)) = p (I | o1, o2,…., odi – 1), such question 1 probability estimation problem into a sequence, The most straightforward method is to use RNN to calculate p (I | c (o, I)).
Different from the model of the first type, since we consider the order of the goods before I, the change of the order of the goods before I will affect the transaction probability of the goods I. In this case, the returns of each good cannot be calculated separately, because the returns of good I are affected by the goods ahead of it; Until the final order is determined, there is no way to know what the order is before commodity I, and our goal is to determine such an optimal order. At the same time, just because we only consider the order of the goods before I, we can sort step by step from front to back, and select the goods in the current position in each step.
To understand this, let’s look at a simple case: sorting by quantile.
The so-called fractional sorting refers to the sorting of the largest income of a commodity to the first, and then conditions on the first commodity, recalculate the income of the rest of the commodity, and select the largest income of the commodity to the second, and so on. Obviously quantile sort is a greedy algorithm. Beam search algorithm can be understood as an extension of greedy algorithm. In each step of search, beam search will retain the k sequences with the largest benefits until the last step, and then return the best sequence.
The original RNN model did not solve the problem of long distance dependence: when we calculated the probability of a transaction for the 20th position, the first four positions had almost no effect. However, the goods in front of the user are the first to see, generally have a deep impression, the impact on the following goods should not be ignored. In order to make the model capable of taking into account the long distance and the dependence on sorting position, we designed a new attention mechanism to be added to the network of RNN.
By embedding attention and location embedding in this way, the model can automatically learn how to adjust attention at different locations according to the data to get better prediction results. Intuitively, the structure diagram of the model is as follows:
Where DNN only uses FI and L as the baseline of features. ReDNN is a DNN global ordering model using the global feature Fi = (Fi, L, Fi, G), miRNN is an RNN global ordering model, and miRNN+attention is an RNN model adding our attention mechanism.
When miRNN and miRNN + attention models were used for sorting, the algorithm times were θ (kN 2) and θ (kN 3), where N was the number of items to be sorted and K was the beam size parameter of beam Search algorithm. For taobao search such a large-scale search platform, such complexity is obviously too high.
However, based on the baseline ranking, we can only rank the top N goods, as long as N is not large, the calculation is affordable. At the same time, because the items at the top of the list have the most impact, the benefits of reordering those items are also greater.
We compare the GMV growth (response model effect) and latency growth curves of various global sorting methods proposed in this paper under different N and K:
Baseline DNN growth: GMV, search engine Latency
For the first time, we put forward a global ranking method for e-commerce considering the mutual influence of goods, and achieved obvious results in taobao main search. At present, the biggest problem is that although RNN method has better effect, it brings too much calculation burden, so how to reduce the calculation amount will be an important research direction.