In a learning-to-rank problem, there is a set of agents (users) X = {x 1 , . . . x n } and a set of alternatives (items) Y = {y 1 , . . . y m }. Each agent reveals her preferences over a subset of alternatives. The goal is to infer agents' preferences over all alternatives, including those that are not rated or ranked. This fundamental machine learning problem has many practical applications. For example, recommender systems use an agent' revealed preferences to discover other alternatives she might be interested in; product designers learn from consumers' past choices to estimate the demand curve of a new product; defenders can predict terrorists' preferences based on their past behavior; and political parties can evaluate campaign options based on voters' preferences. See (Liu and others 2009) for a recent survey. Rating vs. ranking. Agents' preferences can be represented by either a rating for each alternative (e.g., an integer rating in Netflix), or a ranking over the alternatives (i.e., complete ordering). Rating-based approaches have many known drawbacks (Liu and Yang 2008;Katz-Samuels and Scott Copyright c 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 2018), including (i) agents often have different scales for ratings; and (ii) numeric values are often less robust than ranking-based approaches. In fact, rating data can always be converted to ranking data (e.g., y 1 is ranked higher than y 2 if y 1 has a higher rating) and thus ranking-based models and algorithms are more general. We focus on ranking data.
A common approach to infer an agent's preference is to first identify near neighbors of the agent in terms of the Kendall-Tau (KT) distance, then aggregate their rankings to produce a prediction. The KT distance is a metric that counts the number of pairwise disagreements between two ranking lists. This approach was proposed by Liu and Yang (2008), and their algorithm will be referred to as KT-kNN in this paper. Many subsequent work are based on the following assumption (Hwang and Lee 2009;Wang et al. 2012;Fan and Lin 2013;Wang et al. 2014;Park et al. 2015).
Assumption 1. KT distance is a good measure of similarity between agents.
No theoretical justification for this assumption was known until recently. Katz-Samuels and Scott (2018) proposed a latent utility model to justify the assumption. In their model, each agent or alternative is associated with a latent feature. Alternative j's utility to agent i is controlled by a deterministic function of the similarity in their latent features. Under this model, consistency result is established for the KT-kNN algorithms.
However, this model assumes that agents' preferences are deterministic, which is unrealistic in many settings. For example, an agent can exhibit irrational behavior, or provide only a noisy version of her preferences. In fact, human preferences are often highly non-deterministic. Various statistical models have been built to model such randomness, pioneered by the Nobel Laureate McFadden (McFadden 2000) among many other researchers. Therefore, the following question remains open.
This question can be answered by designing algorithms for two closely-related problems: (i) preference completion (PC): given each agent's preferences over a subset of alternatives, the goal is to estimate its preference over all the alternatives. (ii) near neighbors (NN): given an agent x i , the goal is to find agents x i ′ close to x i in the latent space.
Standard techniques exist to use algorithms for the NN problem to solve a PC problem ( (Katz-Samuels and Scott 2018;Liu and Yang 2008); see also Appendix D). Therefore, we focus on the NN problem in this paper.
Our Contributions. Our main conceptual contribution is the combination of a distance-based latent model and random preferences for learning to rank. To the best of our knowledge, while there is a large literature in each component, we are the first to consider both. See related work for more discussions.
Our model is called distance-based random preference model. Let the latent feature of agent i (alternative j) be x i (y j ). Agent i's preferences are determined by a utility function u(x i , y j ) = θ(x i , y j ) + ǫ i,j , where θ(x i , y j ) is a deterministic monotonically decreasing distance-based function and ǫ i,j is a zero mean independent random variable. Our model captures two pervasive characteristics of ranking datasets: Ch1. Economically meaningful θ(•, •) function. u(x i , y j ) is high in expectation when x i and y j are close. An agent is more likely to prefer alternatives with similar latent features to itself. Ch2. Random preference model. The function u(x i , y j ) contains a noise term ǫ i,j to capture uncertainties in agents' behaviors.
Our technical contributions are two-fold. First, we prove that Assumption 1 does not hold anymore in our distancebased random preference model. More precisely, we prove that the agents found by the KT-kNN algorithm (Liu and Yang 2008) is far away from the given agents with high probability, even when n, m → ∞.
Second, we design an "anchor-based" algorithm for finding an agent's near neighbors under random preferences. The algorithm is based on the following natural idea: if two agents i 1 and i 2 are close, then their KT distance to any other agent j (an anchor) should also be close. The algorithm proceeds by using the KT distance to other agents as an agent's feature, and measures the closeness between two agents by the L 1 distance of their features. We prove that asymptotically our algorithm identifies an agent's near neighbors with high probability when the latent space is 1dimensional. Many techniques we developed can be generalized to high-dim settings.
Experiments on synthetic data verify our theoretical findings, and demonstrate that our algorithm is robust in highdim spaces. Experiments on Netflix data shows that our anchor-based algorithm is superior to the KT-kNN algorithm and a standard collaborative filter (using the cosinesimilarities to determine neighbors). Related Work and Discussions. While using random utility models in learning-to-rank problems is not new (Lu and Negahban 2015; Park et al. 2015;Oh, Thekumparampil, and Xu 2015;Zhao, Piech, and Xia 2016;Zhao, Villamil, and Xia 2018;Liu et al. 2019; Katz-Samuels and Scott 2018), we are not aware of any that simultaneously achieves both Ch1 and Ch2.
Random utility-based ranking algorithms (Lu and Negahban 2015; Park et al. 2015;Oh, Thekumparampil, and Xu 2015) address Ch2, but the function θ(x i , y j ) often does not have an explicit economics interpretation. For example, let Θ ∈ R n×m be a matrix such that Θ i,j = θ(x i , y j ). (Park et al. 2015;Oh, Thekumparampil, and Xu 2015) assume that Θ is low rank. But the low rank assumption does not have explicit economically interpretation.
While recent non-parametric models (e.g., (Katz-Samuels and Scott 2018)) allow one to use economically interpretable functions θ (addressing Ch1), they operate only under deterministic utility models.
Parametric preference learning has been extensively studied in machine learning, especially learning to rank (Azari Soufiani et al. 2013;Azari Soufiani, Parkes, and Xia 2013;2014;Cheng, Hüllermeier, and Dembczynski 2010; Hughes, Hwang, andXia 2015; Khetan andOh 2016; Maystre andGrossglauser 2015). These works are different with ours as it is often assumed that agents' preferences are generated from a parametric model.
Distance-Based Random Preference Model. Let X = {x 1 , . . . , x n } ⊂ R d denote the set of agents and let Y = {y 1 , . . . , y m } ⊂ R d denote the set of alternatives. We slightly abuse the notation and use x i to refer to both agent i and her latent features. Each agent x i has a ranking (preference list)
Utility functions and the random utility model. Agent i's expected utility on alternative j is determined by a function θ(x i , y j ). Throughout this paper, we use θ(x i , y j ) = exp(-x i -y j 2 ), where . 2 is the ℓ 2 -norm. Agent i's ranking R i is determined by the widely-used Plackett-Luce model (Plackett 1975;Luce 1977). The realized utility of alternative y j for agent i is generated by u(x i , y j ) ≡ θ(x i , y j ) + ǫ i,j , where ǫ i,j is a zero mean independent random variable that follows the Gumbel distribution. Then, agent i ranks the alternatives in decreasing order of their realized utilities. The density function of the Plackett-Luce model has a closed-form formula. Let y j1 ≻ i y j2 represent that y j1 is ahead of y j2 in R i and let j 1 , j 2 , . . . j m be a permutation of [m]. We have
.
(1)
The marginal distribution between alternatives j 1 and j 2 is
θ(xi,yj 1 )+θ(xi,yj 2 ) . Distributions of X and Y. x i and y j are i.i.d. generated from distributions D X and D Y . The supports of D X and
where c is a constant. We adopt the standard "near uniform" assumption for D X and D Y (Abraham et al. 2015;Hoff, Raftery, and Handcock 2002;Kleinberg 2000;Sarkar, Chakrabarti, and Moore 2011).
. Observation model. We observe only agent i's ranking over a subset O i ⊆ [m] of alternatives. Each alternative j is in O i independently with probability p. The O i 's are also independently generated across different agents. Let R Oi be the ordered list over O i ⊆ Y that is consistent with R (i.e., R Oi is the partial ranking of R over O i ). For each agent i, we observe R Oi i . The near neighbor problem. Here, an algorithm needs to find near neighbors of an input agent. An algorithm is a k(n, m)-NN solver with parameter τ (n) if • for any input agent i, the algorithm outputs k agents i 1 , i 2 , . . . i k , and
We often write k-NN or kNN instead of k(n, m)-NN when k's dependencies on m and n are not critical. Additional notations and examples. For an arbitrary ordered list R, we use it calligraphic form R to extract the rank of an alternative. For example, suppose y j is the top-ranked alternative in R, then R(y j ) = 1. Let I(v) be an indicator that sets to 1 if the argument v is true; if false, it sets to 0.
Let |R| be the length of the list R. Let R 1 and R 2 be two ordered lists over the same set of alternatives. The normalized Kendall-Tau distance between R 1 and R 2 is
When R 1 and R 2 do not have the same support, the normalized KT distance is defined as
To facilitate analysis, sometimes we need to introduce new agents outside X . For a new agent with latent features x, let R x denote its ranking over Y and let R Ox x denote the observed ranking. Conditional probability and expectations. There are multiple levels of randomness for producing the rankings R i 's: (i) x i and y j are random and (ii) u(x i , y j ) consists of a random component (i.e., randomness from the Plackett-Luce model). Care must be taken when operating the conditional random variables defined in our process. For example,
In this section, we will prove the inefficacy of KT-kNN algorithm by Liu and Yang (2008) (Algorithm 1) in our distanced-based random preference model. This implies that Assumption 1 does not hold in our model.
Recall that KT-kNN uses KT distances to find an agent's neighbors based on the intuition that when x i and x j are close, their "opinion" on alternatives' utilities should be similar. The next theorem show that this intuition does not hold Algorithm 1: KT-kNN (it produces incorrect results)
, k, and an agent x i . 2 Output: k neighbors near agent i in the latent space.
jn-1 ) 4 Return X KT-kNN ← {j 1 , . . . j k } in our model, by proving that KT-kNN does not return any near neighbors for a large fraction of x i . Theorem 1. Consider Algorithm KT-kNN under distancebased random preference model in which d = 1 and p = 1. Let D Y and D X be uniform distributions on [-1, 1]. For any constant ǫ, any x i ∈ [-1 + ǫ, -0.5] ∪ [0.5, 1 -ǫ], and any k ≤ n/ ln 5 n, we have
with high probability. The probability comes from random X /{x i }, random Y, and random preferences.
Remarks. Theorem 1 states that KT-kNN fails to work even for the simple case where d = 1 and 3) is a strong result because trivial algorithms exist to find an agent x j whose distance to x i is Θ(1) (just picking up an arbitrary x j ). In addition, this result continues to hold for large populations (e.g., when n, m → ∞ and p = 1), suggesting that the limitation of the KT-based approach roots at the structural properties of the NK function. In addition, if we use KT-kNN to solve PC problem by applying standard techniques, it will also produce poor results (see Appendix D and Lemma 8 there).
Comparison to (Katz-Samuels and Scott 2018). Katz-Samuels and Scott (2008) proved that KT-kNN is effective under the deterministic utility model. This suggests that with the presence of uncertainties in the utility function (a more realistic assumption), the algorithmic structure of the NN problem is significantly altered. Intuitions behind Theorem 1. The following example highlights the salient structures of KT-distances. Example 1 (Near-neighbors in expectation). Let x 1 = 0, y 1 = -0.5, and y
, where would we place an agent that minimizes its KT distance to x 1 ?). One would hope that when x * and x 1 are close, R x * and R 1 is close, but here x * = -0.5. Specifically, let a be the probability x 1 prefers y 1 to y 2 (i.e., a ≡ θ(x1,y1) θ(x1,y1)+θ(x1,y2) ) and let b(x) be the probability x prefers y 1 to y 2 . Recall that agents' support is [-1, 1]. We need to solve
Here, we aim to minimize the weighted sum of a ∈ [0, 1] and (1 -a) via controlling b(x). The optimal solution has a simple structure: when a > (1 -a) (equivalently, a > 0.5), we need to set the weight associated with a as small as possible, which means setting b(x) to the largest possible value. When a < (1 -a), b(x) needs to be minimized. Thus, the optimal solution uses the following threshold rules (assume a = 0.5 for simplicity).
x * ∈ (-1, y 1 ) if a > 0.5 (y 2 , 1) if a < 0.5 .
This minimizer is far from x 1 .
See also Example 3 in Appendix B.5 for another small and concrete example, in which KT-kNN produces poor output.
We use intuitions from Example 1 to prove the theorem. Specifically, define
First, note that NK(R i , R x ) concentrates at G i (x) when m is sufficiently large. This comes from the concentration behavior of the NK function:
See Appendix B.1 for the proof. The terms in NK are not independent terms so we cannot directly apply Chernoff bounds. Our proof uses the combinatorial structure of the NK function to decouple the dependencies among terms. The technique we develop can be of independent interests.
Let x * = arg min x G i (x). Below is our main lemma:
Lemma 2. Let D Y be uniform distribution on [-1, 1]. Let x i be any agent in [-1, -0.5]. We have
Similarly, when x i ∈ [0.5, 1], arg min x G i (x) = 1.
For any x i ∈ [-1, -0.5]∪[0.5, 1], Lemma 1 and Lemma 2 give us:
, where the first approximation comes from the concentration bound of NK and the second approximation comes from the fact that there must exist one agent close to -1 when the number of agent is large. Therefore, all the neighbors produced by KT-kNN are far from x i (see Appendix B.4 for a rigorous analysis).
Proof of Lemma 2. By linearity of expectation, we have
The last equality holds because y j 's are i.i.d. samples from D Y . Define
When the context is clear, we shall refer to p i (y 1 , y 2 ) and p x (y 1 , y 2 ) as p i and p x , respectively. We have
One can see that G i (x) is a smooth function (the first derivative exists). Our proof consists of three parts. Part
The proof for part 3 is similar to part 1. Proving part 2 is also simpler. Therefore, we focus only on the proof for part 1. Proof for part 2 and 3 is deferred to Appendix B.2.
We now show that when x ∈ (-1, x i ], ∂G i (x)/∂x > 0. We have (see Fact 2 in Appendix B.2):
where
• sign(y 1 -x)-sign(y 2 -x)
Here,
1,2 ) measures whether x i (x) is closer to y 2 or y 1 . Similar to Example 1, they serve as important quantities determining the structure of ∂G i (x)/∂x (and therefore the optimal solution).
One can check that Φ(y 1 , y 2 , x, x i ) = Φ(y 2 , y 1 , x, x i ). Therefore,
Central to our analysis is carefully partitioning the event y 1 ≤ y 2 into four disjoint (sub)-events. Under each event, the conditional expectation of Φ can be computed in a straightforward manner. Specifically, define
. Figure 3(a) in Appendix A visualizes the events to complement the analysis. We now interpret the meaning of these events. Event E 1 . Event E 1 represents the case in which y 1 and y 2 are on the same side of x. In this case, any movement Algorithm 2: Anchor-kNN
, k, and agent x i . 2 Output: k neighbors near agent i.
with high probability. The probability comes from random X /{x i }, random Y, and random preferences.
Remark. τ (n) cannot be too small because our function D(x i , x j ) cannot measure the distance of two agents well if they are too close. m needs to grow when p (fewer samples) or τ (n) decreases (higher quality requirement), which is intuitive. k measures the number of numbers an algorithm can find so that their distance is within τ (n); larger k means the algorithm is more powerful.
Let
In the remainder of this section, we analyze the behavior of of D. The function D concentrates at D and can be shown by using simple Chernoff bounds (see Appendix C.2 for a complete analysis). Lemma 3. For any near-uniform D X , D Y on [-c, c] and any two agents x i , x j , we have
where c 3 is a constant that depends only on c.
Upper bound proof for Lemma 3. The upper bound requires only a straightforward calculation. Recall that p
The last inequality is shown in Fact 6 in Appendix C.1. Lower bound bound proof for Lemma 3. Here we analyze only the case |x i -x j | ≤ 2c -2 ln n. When |x i -x j | > 2c -2 ln n (e.g., x i and x j are around the boundaries -c and c, respectively), the result is trivial. Wlog, assume that x i < x j . We partition [-c, c] into three intervals and consider anchor agents in each of these intervals. Specifically, define (see also Figure 1
The agents in I 2 are "less effective anchors" (C2). We use trivial bound for terms in I 2 (|F i,t -F j,t | ≥ 0). Focusing on I 1 and I 3 , we have
x j is at least in the order of |x i -x j | 2 . The analysis for the other term is similar. Below is the lemma we need (related to C2):
∂x dx , we aim to give a bound for ∂Gt(x) ∂x . Specifically,
when x ≥ 2x t + c (or equivalently, x t ≤ x-c 2 ). Re-cycle the definition of Φ, ∆ (i) 1,2 , and ∆ (x) 1,2 used in the analysis of Theorem 1 (see also Appendix A for the notation summary) so that ∂G(x) ∂x = E y1<y2 [Φ(y 1 , y 2 , x, x t ) | x, x t ] We partition the positions of {y 1 , y 2 } into events (see also Fig. 1c for a visualization):
• E 1 : when x ≤ y 1 ≤ y 2 or y 1 ≤ y 2 ≤ x.
• E 2 : when y 1 ∈ [ x-7c 8 , 3x-5c 8 ] and y 2 ≥ x+c 2 . We have
• E 3 : when (y 1 , y 2 ) / ∈ E 1 ∪ E 2 . As explained below, we do not need to explicitly calculate Pr[E 3 | y 1 ≤ y 2 ].
We now explain the intuition associated with these events.
Event E 1 . Because y 1 and y 2 are on the same side of x, we have E[Φ | E 1 , x, x t ] = 0 (see also Lemma 2). Event E 2 and event E 3 . When (y 1 , y 2 ) ∈ E 2 ∪ E 3 , we have |y 1 -x t | ≤ |y 2 -x t | (x t is closer to y 1 than to y 2 ). This is because (i) |y 2 -x t | ≥ x -x t when y 2 ≥ x and x ∈ I 1 , and (ii) |y 1 -x t | ≤ max{x t -c, x -x t } ≤ x -x t since y 1 ≤ x and x ≥ 2x t + c. This conclusion is trivial when the positions of the points are visualized (Figure 1(c)).
In these events, an increment in x will result in an increment in G t (x). Therefore E[Φ | E 2 ∪ E 3 , x, x t ] ≥ 0. Event E 2 . Knowing Φ can be arbitrarily close to 0 when E 2 ∪ E 3 happens. Here, we need also identify an event so that Φ is at least a positive constant. Event E 2 serves for this based kNN algorithm failed to find similar agents (users), challenging the assumptions made in many prior preference completion algorithms. To fix the problem, we introduced a new anchor-based algorithm Anchor-kNN that uses all the agents' ranking data to determine the closeness of two agents. Our approach is in sharp contrast to most existing feature engineering methods. We provided a rigorous analysis for Anchor-kNN for 1-dim latent space, and performed experiments on both synthetic and real datasets. Our experiments showed that Anchor-kNN works in high dim space and promises to outperform other widely used techniques.