--- title: "Learning Mixtures of Random Utility Models with Features from Incomplete Preferences" authors: - "Zhibing Zhao" - "Ao Liu" - "Lirong Xia" doi: "10.24963/ijcai.2022/525" url: "https://ijcai.org/proceedings/2022/525" pdf: "https://ijcai.org/proceedings/2022/0525.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "3780-3786" track: "Main Track" keywords: - "Machine Learning: Learning Preferences or Rankings" --- # Learning Mixtures of Random Utility Models with Features from Incomplete Preferences Zhibing Zhao, Ao Liu, Lirong Xia *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 3780-3786. DOI: [10.24963/ijcai.2022/525](https://doi.org/10.24963/ijcai.2022/525) ## Abstract Random Utility Models (RUMs), which subsume Plackett-Luce model (PL) as a special case, are among the most popular models for preference learning. In this paper, we consider RUMs with features and their mixtures, where each alternative has a vector of features, possibly different across agents. Such models significantly generalize the standard PL and RUMs, but are not as well investigated in the literature. We extend mixtures of RUMs with features to models that generate incomplete preferences and characterize their identifiability. For PL, we prove that when PL with features is identifiable, its MLE is consistent with a strictly concave objective function under mild assumptions, by characterizing a bound on root-mean-square-error (RMSE), which naturally leads to a sample complexity bound. We also characterize identifiability of more general RUMs with features and propose a generalized RBCML to learn them. Our experiments on synthetic data demonstrate the effectiveness of MLE on PL with features with tradeoffs between statistical efficiency and computational efficiency. Our experiments on real-world data show the prediction power of PL with features and its mixtures. ## Full text ## 1 Introduction Preference learning is a fundamental machine learning problem in a wide range of applications such as discrete choice analysis [McFadden, 1973], marketing [Berry et al., 1995], meta-search engines [Dwork et al., 2001], information retrieval [Liu, 2009], recommender systems [Baltrunas et al., 2010], crowdsourcing [Chen et al., 2013; Mao et al., 2013], social choice [Azari Soufiani et al., 2012], among many others. Plackett-Luce model (PL) [Plackett, 1975; Luce, 1959] is one of the most popular statistical models for preference learning due to its interpretability and computational tractability. In the standard PL, each alternative is parameterized by a real number θ such that eθ represents the alternative's "quality". The higher the quality is, the more likely the alternative is ranked higher by an agent. ∗Work done while at Rensselaer Polytechnic Institute. Extensions of the standard PL has been proposed and studied mostly in three dimensions. The first dimension is PL with features, where features of the agents and/or the alternatives are given, and the model is parameterized by the relationship (often linear, see Definition 2) between the features and the quality of the alternatives. Examples include the conditional logit model [McFadden, 1973], the BLP model [Berry et al., 1995], and bilinear models [Azari Soufiani et al., 2013; Sch¨afer and H¨ullermeier, 2018; Zhao et al., 2018a]. The second dimension is PL for partial preferences, where the data consist of partial preferences, often represented by partial orders over the alternatives. Due to the hardness of tackling general partial orders [Liu et al., 2019], most previous work focused on natural sub-cases, including choice data [Train, 2009], top-ranked orders (top-l) [Mollica and Tardella, 2017], and pairwise preferences [H¨ullermeier et al., 2008]. In particular, in a top-l order, the agent reports a linear order over her most-preferred l alternatives. Top-l orders generalize standard PL (l = m- 1, where m is the number of alternatives) and choice data (l = 1). The third dimension is PL mixture models, where k ≥ 1 PL models are combined via a mixing coefficients ⃗α = (α1, . . . , αk) and each αi represents the probability that the data is generated from the i-th PL. Mixtures of PLs provide better fitness to data [Tkachenko and Lauw, 2016] and are a popular method for clustering [Gormley and Murphy, 2008], but they are generally hard to compute and are prone to criticisms on interpretability and trustworthiness due to their (non)identifiability [Zhao et al., 2016]. While there is a large literature on standard PL and its extensions in each of the three dimensions, little is known about the generalization of PL in all three dimensions simultaneously, i.e. mixtures of PL models with features for partial preferences. The literature on general RUMs and their extensions is far more limited. The problem is already highly challenging for top-l orders-to the best of our knowledge, only one previous work studied mixtures of PL models with features for top-l orders [Tkachenko and Lauw, 2016], where an EM algorithm was proposed yet no theoretical guarantees on the model or the algorithm were given. Motivated by the lack of theoretical understandings of the general PL extensions and learning algorithms, we ask the following question. When and how can preference learning be done for (mixtures of) RUMs with features for incomplete preferences? Table 1: The model, identifiability, and consistency of this work compared with previous work. | | features | top-l | mixtures | identifiability | consistency | |-----------------------------------------------------------------|------------|---------------|------------|--------------------------|---------------| | This work | ✓ | ✓ | ✓ | ✓(Thm. 1, 2, Coro. 1, 2) | ✓(Thm. 4) | | [Tkachenko and Lauw, 2016] | ✓ | ✓ | ✓ | | | | [Yıldız et al., 2020] | ✓ | ✓ | | | | | [McFadden, 1973], [Berry et al., 1995] | ✓ | top-1 | | ✓ | ✓ | | [Gr¨un and Leisch, 2008] | ✓ | top-1 | | ✓ | | | [Sch¨afer and H¨ullermeier, 2018] | ✓ | linear orders | | ✓ | | | [Zhao et al., 2016], [Zhao et al., 2018b], [Zhao and Xia, 2019] | | linear orders | ✓ | ✓ | ✓ | | [Chierichetti et al., 2018] | | ✓ | ✓ | ✓ | | The question is highly challenging and the answer is not fully known even for many well-studied sub-cases, such as (non-mixture) PL with features for top-l orders and mixtures of standard PL (without features) for linear orders. In this paper, we provide the first answers to the question for PL with features for top-l orders by characterizing their identifiability, consistency, and sample complexity of their MLEs. We also provide the first generic identifiability result for its mixture models as well as more general RUMs with features. Identifiability is a fundamental property of statistical models that is important to explainability and trustworthiness of decisions, which are particularly relevant in preference learning scenarios [Gormley and Murphy, 2008]. Identifiability requires that different parameters of the model lead to different distributions over data. If a model is non-identifiable, then sometimes the explanations of the learned parameters and corresponding decisions can be provably wrong, because there may exist another parameter that fits the data equally well, yet whose explanation and corresponding decisions are completely different. See Example 1 for an illustrative example. Additionally, the identifiability of a model is necessary for any algorithm to be consistent or have finite sample complexity. Our Contributions. In this paper, we provide the first theoretical characterizations of identifiability for mixtures of k ≥ 1 PLs with features for top-l orders, denoted by k-PLX-TO, where X is the feature matrix. We note that in k-PLX-TO, each agent submits a top-l order for possibly different l. Identifiability. We provide necessary and sufficient conditions for PLX -TO and its special case called the bilinear model, denoted by PLY,Z-TO, to be identifiable in Theorem 1 and Corollary 1, respectively. Even though k-PLX -TO is not identifiable for any k ≥ 2, we provide a sufficient condition in Theorem 2 for a parameter k-PLX -TO to be identifiable, which leads to the generically identifiability of 2-PLX -TO in Corollary 2. It suggests that identifiability may not be a practical concern if the condition is satisfied. We also characterize identifiability of RUMs with features in the appendix. Strict concavity and sample complexity of MLE. We provide a necessary and sufficient condition for the MLE of PLX -TO to be strictly concave in Theorem 3 and bound on the RMSE of MLE of PLX -TO in Theorem 4, which implies the consistency of MLE and a sample complexity bound. Our experiments on synthetic data demonstrate the performance of MLE and the tradeoffs between statistical efficiency and computational efficiency when learning from different top-l preferences for PLX-TO. For k-PLX-TO, we propose an EM algorithm and show the prediction power of different configurations of k-PLX -TO. Related Work and Discussions. Table 1 summarizes related works on PL and its extensions that are close to ours. As discussed above, there is a large literature on PL and its extensions in each of the three dimensions, yet no theoretical result is known even for the special non-mixture case PLX-TO for top-l orders in general. [Tkachenko and Lauw, 2016] is the only previous work we are aware of that tackles kPLX -TO, which does not provide theoretical guarantees. Even for PLX -TO, we are only aware of another recent paper [Yıldız et al., 2020], which proposed an ADMM-based algorithm for computing the MLE, but it is unclear whether their algorithm converges to the ground truth because the consistency of MLE was unknown, which is a direct corollary of Theorem 4. To the best of our knowledge, our identifiability results (Theorems 1, 2, Corollaries 1, 2) and the RMSE bound (Theorem 4) are the first for (k-)PLX -TO even for linear orders (l = m- 1). Mixtures of PLs with features for choice data (top-1) are well studied and can be dated back to the classical conditional logit model [McFadden, 1973] and the BLP model [Berry et al., 1995]. PL with bilinear features, which is a special case of PLX -TO, has been studied in the literature [Azari Soufiani et al., 2013; Sch¨afer and H¨ullermeier, 2018; Zhao et al., 2018a]. There is a large literature on standard PL (without features) and its mixture models [Hunter, 2004; Soufiani et al., 2013; Negahban et al., 2017; Maystre and Grossglauser, 2015; Khetan and Oh, 2016; Zhao and Xia, 2018; Gormley and Murphy, 2008; Oh and Shah, 2014; Zhao et al., 2016; Chierichetti et al., 2018; Zhao and Xia, 2019; Liu et al., 2019]. Our setting is more general. Recently, Sch¨afer and H¨ullermeier (2018, Proposition 1) provided a sufficient condition for PL with bilinear features to be identifiable. However, their result is flawed due to the missing conditions on the ranks of feature matrices. See Example 3 for more details. Our Corollary 1 provides a necessary and sufficient condition for the identifiability of more general models. Zhao et al. (2016) characterized the conditions on k (the number of components in the mixture model) and m (the number of alternatives) for mixtures of standard PLs to be (non-)identifiable. Zhao and Xia (2019) characterized (non-)identifiability of mixtures of PLs (without features) for structured partial orders. Gr¨un and Leisch (2008) characterized conditions for mixtures of multinomial logit models to be identifiable. These results do not subsume our results because the model studied in this paper is more general. Consistency of MLE was proven for the conditional logit model [McFadden, 1973] assuming that each agent provides multiple choice data. Or equivalently, agents with the same features are repeatedly observed. This assumption may not hold in the big data era, where the feature space can be extremely large and it is unlikely that agents would have identical features. Our proof of the RMSE bound on MLE, which implies consistency, tackles exactly this case and is inspired by the proof of [Khetan and Oh, 2016, Theorem 8] for standard (non-mixture) PL. Unlike the standard PL where the Hessian matrix is negative semidefinite with at least one zero eigenvalue [Khetan and Oh, 2016], the Hessian matrix of the model studied in this paper does not have zero eigenvalues. Due to this difference, the techniques in proving the sample complexity bound in [Khetan and Oh, 2016] cannot be directly extended to our setting. Due to the space constraint, we focus on Plackett-Luce model in the main paper and defer results on RUMs to the appendix. ## 2 Preliminaries Let A = {a1, . . . , am} denote the set of m alternatives. Let {1, . . . , n} denote the set of n agents. Given an agent j, each alternative is characterized by a column vector of d ≥ 1 features ⃗xji ∈ Rd . For any r = 1, . . . , d, let xji,r denote the rth feature of ⃗xji. A linear order, which is a transitive, antisymmetric, and total binary relation, is denoted by R = ai1 ≻ . . . ≻ aim , where ai1 ≻ ai2 means that the agent prefers ai1 over ai2 . Let L(A) denote the set of all linear orders. A ranked top-l (top-l for short) order has the form O = ai1 ≻ ai2 . . . ≻ ail ≻ others. It is easy to see that a linear order is a special top-l order with l =m-1. Let T (A) denote the set of all top-l orders for all l ∈ {1, 2, . . . ,m- 1}. An l-way order has the form O = ai1 ≻ ai2 . . . ≻ ail . Let I(A) denote the set of all l-way orders for all l ∈ {2, . . . ,m}. Definition 1 (Plackett-Luce model (PL)). The parameter space is Θ = Rm. The sample space is L(A)n . Given a parameter ⃗ θ ∈ Θ, the probability of any linear order R = ai1 ≻ ai2 ≻ . . . ≻ aim is PrPL(R|⃗ θ) = ∏m-1 p=1 exp(θip ) ∑mq=p exp(θiq ) . It follows that the marginal probability for any top-l order R = ai1 ≻ ai2 . . . ≻ ail ≻ others is PrPL(R|⃗ θ) = ∏lp=1 exp(θip ) ∑mq=p exp(θiq ) . In the literature, a normalization constraint on ⃗ θ, e.g. ∑i θi = 0, is often required to make the model identifiable. In this paper we do put such a constraint since it is more convenient to extend the current definition to PL with features. Let Xj = [⃗xj1, . . . , ⃗xjm] ∈ Rd×m denote the feature matrix for agent j, and let X = [X1, . . . ,Xn] ∈ Rd×mn denote the feature matrix that concatenates the features for all agents. Definition 2 (Plackett-Luce model with features (PLX)). Let X ∈ Rd×mn denote a feature matrix. The parameter space is Θ = Rd . The sample space is L(A)n . For any parameter ⃗ β ∈ Θ, the probability of any linear order Rj = ai1 ≻ ai2 ≻ . . . ≻ aim given by agent j is PrPLX (Rj |⃗ β) = ∏m-1 p=1 exp(⃗ β·⃗xjip ) β·⃗xjiq ) . We note that all feature matrices are assumed given, i.e., not part of the parameter of any model in this paper. PL with bilinear features [Azari Soufiani et al., 2013] is a special case of PLX , where each agent j ∈ {1, . . . , n} is characterized by a column feature vector ⃗yj ∈ RL and each alternative ai ∈ A is characterized by a column feature vector ⃗zi ∈ RK . We note that for any i ∈ {1, . . . ,m}, ⃗zi is the same across all agents. Let Y = [⃗y1, . . . , ⃗yn] ∈ RL×n denote the agent feature matrix and Z = [⃗z1, . . . , ⃗zm] ∈ RK×m denote the alternative feature matrix. Definition 3 (Plackett-Luce model with bilinear features PLY,Z). Let Y ∈ RL×n denote an agent feature matrix and let Z ∈ RK×m denote an alternative feature matrix. The parameter space consists of matrices Θ = RK×L. The sample space is L(A)n . Given a parameter B ∈ Θ, the probability of any linear order Rj = ai1 ≻ ai2 ≻ . . . ≻ aim given by agent exp(⃗z⊤ PLY,Z can be viewed as a special case of PLX by letting X = Y ⊗ Z and vectorizing B accordingly. Definition 4 (k-PL). For any k ≥ 1, the mixture of k PlackettLuce models is defined as follows. The sample space is L(A)n . The parameter space has two parts. The first part is the mixing coefficients ⃗α = (α1, · · · , αk) with ⃗α ≥ 0 and ⃗α · ⃗1 = 1. The second part is (⃗ θ(1) , · · · , ⃗ θ(k)), where ⃗ θ(r) ∈ Θ is the parameter of the r-th PL component. The probability of any linear order R is Prk-PL(R|⃗ θ) = ∑kr=1 αr PrPL(R|⃗ θ(r) ). Definition 5 (Mixtures of k Plackett-Luce models with features (k-PLX)). Let X ∈ Rd×mn denote the feature matrix. The parameter space Θ has two parts. The first part is the vector of mixing coefficients ⃗α = (α1, α2, . . . , αk) and the second part is (⃗ β(1) , ⃗ β(2) , . . . , ⃗ β(k) ), where for r = 1, . . . , k, ⃗ β(r) = {β(r) i |1 ≤ i ≤ d}}. The sample space is L(A)n . Given a parameter ⃗ θ ∈ Θ, the probability of any linear order Rj = [ai1 ≻ ai2 ≻ . . . ≻ aim ] given by agent j is Prk-PL(X )(Rj |⃗ θ) = ∑kr=1 αr PrPLX (Rj |⃗ β(r) ). PLX can be viewed as a special case of k-PLX where k = 1. Definition 6 (Identifiability). Let M = {Pr(·|⃗ θ) : ⃗ θ ∈ Θ} be a statistical model, where Θ is the parameter space and Pr(·|⃗ θ) is the distribution over the sample space associated with ⃗ θ ∈ Θ. We say that a parameter ⃗ θ ∈ Θ is identifiable in M, if for any ⃗γ ∈ Θ with ⃗γ ̸= ⃗ θ, we have Pr(·|⃗ θ) ̸= Pr(·|⃗γ). Mis identifiable if all its parameters are identifiable. The following example shows that non-identifiability of a model can lead to unavoidable untrustworthy interpretations and decisions. Example 1. Suppose an automobile manufacturer is using PLY,Z to learn consumers' preferences over car models. For simplicity suppose there are two agents {1, 2} and two alternatives (car models) {a1, a2}. Y = [y1, y2] = [0.5, 1], where each agent is represented by her normalized income (0.5 for the first agent and 1 for the second agent). Z = [⃗z1, ⃗z2] = [0.6 1 0.2 0.5], where each car is represented by its normalized price (0.6 for the first car and 1 for the second car) and its normalized miles per gallon (0.2 for the first car and 0.5 for the second car). Let B = [-1, 8/3]⊤ and B′ = [1, 0]⊤. We show that B and B′ correspond to exactly the same distribution over the two agents' preferences. In fact, it is not hard to verify that ⃗z⊤ 1 By1 - ⃗z⊤ 2 By1 = z⊤ 1 B′ y1 - ⃗z⊤ 2 B′ y1 = -0.2 and ⃗z⊤ 1 By2 - ⃗z⊤ 2 By2 = ⃗z⊤ 1 B′ y2 - ⃗z⊤ 2 B′ y2 = -0.4. Therefore, PrPLY,Z (R1 = a1 ≻ a2|B) = 1 1+exp(⃗z⊤ 2 By1-⃗z⊤ 1 By1) = 1 1+exp(⃗z⊤ 2 B′ y1-⃗z⊤ 1 B′ y1) = PrPLY,Z (R1 = a1 ≻ a2|B′ ). Other probabilities can be calculated similarly. Therefore, it is impossible for any statistical method to distinguish B from B′ . This may not be a big concern if the company uses the learned model to predict the preferences of new customers, as both B and B′ would give the same prediction. However, the first components of B and B′ have opposite interpretations. The first component of B being positive is often interpreted as the existence of a negative correlation between an agent's income and the car's price, i.e. richer people prefer cheaper cars. The interpretation of the first component of B′ is on the opposite. This makes the interpretation and any decision based on it untrustworthy. □ Figure 1: Illustration of model M-TO with the parameter ⃗ϕ, where M is a model that generates linear orders. M-TO allows users to report top-l orders of different l's. ![Image](https://ijcai.org/proceedings/2022/fulltext/525/image_000000_0adbaec6fee4c5072cc82ca318de985d48ac393f27844b2788900c7f6157f1c8.png) ## 3 Models and Their Identifiability for Top-l Orders Modeling and learning from different partial orders is desirable in the scenarios where users provide different structures of partial orders [Zhao and Xia, 2019]. Following Zhao and Xia (2019), we extend PLX to a model that generates top-l partial orders by introducing a new parameter ⃗ϕ = (ϕ1, . . . , ϕm-1), where ∑m-1 i=1 ϕi = 1. ⃗ϕ can be viewed as a distribution over {1, 2, . . . ,m- 1} that represents the probability for the agent to report a top-l order, where 1 ≤ l ≤ m- 1. Any model defined in the previous section can be extended to a model that generates a top-l order R with probability PrM-TO(R|⃗ θ, ⃗ϕ) = ϕl PrM(R|⃗ θ), as is illustrated in Figure 1. For example, PLX can be extended to PLX -TO, formally defined as follows. Figure 2: Relations between models in this paper in Venn diagram. kPLX -TO is the most general model, subsuming all the other models. The two largest submodels of k-PLX -TO are PLX -TO and k-PLX , whose intersection is PLX . PL is the smallest model in this diagram, lying at the intersection of PLX -TO and k-PL. ![Image](https://ijcai.org/proceedings/2022/fulltext/525/image_000001_7b359fb5c78005d064c4c21d8f96643645637e672157d06728869cda68ffcde2.png) Definition 7 (PLX-TO). Let X ∈ Rd×mn denote the feature matrix. The parameter space is Θ = Rd × {⃗ϕ ∈ Rm-1 ≥0 : ⃗ϕ · ⃗1 = 1}. The sample space is T (A)n . Given a parameter (⃗ β, ⃗ϕ), the probability of any top-l order Oj = ai1 ≻ ai2 ≻ . . . ≻ ail ≻ others given by agent j is PrPLX -TO(Oj |⃗ β, ⃗ϕ) = ϕl PrPLX (Oj|⃗ β), where PrPLX (Oj|⃗ β) is the marginal probability of Oj under PLX given ⃗ β. Again, X is assumed given and not part of the parameter of PLX -TO. PLX is a submodel of PLX -TO (where ϕm-1 = 1). PLY,Z-TO and k-PLX-TO can be defined similarly, see Appendix A for their formal definitions. The relations between different models mentioned in this paper are shown in the Venn diagram in Figure 2 (PLY,Z and PLY,Z-TO are omitted for simplicity). As was illustrated in Example 1, identifiability is important if one wants to interpret the learned parameter. For the rest of this section, we focus on identifiability of PLX-TO and k-PLX -TO. To characterize the identifiability of PL extensions with features, for each j ≤ n, we first define agent j's normalized feature matrix, denoted by norm(Xj). We then define Norm(X). In words, X is normalized by using the feature vector of a1 as the baseline. Our results still hold if another alternative is used as the baseline. We now present our first identifiability theorem. Theorem 1. For any X, PLX -TO is identifiable if and only if Norm(X) has full row rank. The full proof can be found in Appendix G.2. Example 2. Consider a PLX (a special case of PLX-TO), whose feature matrix X has three rows ⃗r1, ⃗r2, and ⃗r3, where ⃗r1 + ⃗r2 = ⃗r3. Therefore, Norm(X) does not have full row rank. Let ⃗ β = [β1, β2, β3]⊤ be the ground truth parameter. We construct ⃗ β′ = [β1 + β3, β2 + β3, 0]⊤. Then it is easy to see ⃗ β⊤ · X = ⃗ β′⊤ · X , which further means for any order R, we have PrPLX (R|⃗ β) = PrPLX (R|⃗ β′ ) by Definition 2. This means this PLX is not identifiable. Theorem 1 can be applied to characterize the identifiability for PL with bilinear features as in the following corollary. Corollary 1. For any model PLY,Z-TO, where Y ∈ RL×n and Z ∈ RK×m, PLY,Z-TO is identifiable if and only if both Y and norm(Z) have full row rank. The formal proof can be found in Appendix G.3. The full row rank condition in Theorem 1 and Corollary 1 is mild as long as n is not too small, which is the case in many real-world applications. For example, the full row rank condition holds on the sushi dataset used in our real-world experiment. In Appendix F.4, we show that the probability of violating the full row rank condition becomes very small when sampling n = 10 agents from the sushi dataset, and this probability decays exponentially as n increases. In the next example, we show that the sufficient conditions for PLY,Z-TO to be identifiable by Sch¨afer and H¨ullermeier (2018, Proposition 1) is unfortunately flawed. Example 3. Continuing Example 1, it is not hard to verify that no agent feature or alternative feature is a constant, which implies that PLY,Z is identifiable according to [Sch¨afer and H¨ullermeier, 2018, Proposition 1]. However, as we showed in Example 1, PLY,Z is not identifiable. It's easy to see that norm(Z) has two rows but only one column, which does not have full row rank. Identifiability of mixtures of PLs with features is at least as challenging as the identifiability of mixtures of standard PLs, which is still an open problem for any k ≥ 3. In the following theorem, we provide a sufficient condition for a parameter in k-PLX -TO to be identifiable. Theorem 2. If k-PL is identifiable, then for any X such that Norm(X) has full row rank, any parameter (⃗α, ⃗ β, ⃗ϕ) with ϕm-1 > 0 is identifiable in k-PLX -TO. The proof is done by contradiction. The full proof is provided in Appendix G.4. Corollary 2. For any X such that Norm(X) has full row rank, 2-PLX -TO over four or more alternatives is identifiable modulo label switching. ## 4 MLE of PLX-TO and Its Consistency Let P = (O1, . . . , On) denote the input data, where for each j ≤ n, Oj is a top-lj order. Let X ∈ Rd×mn denote the feature matrix. MLE of PLX -TO computes the parameter that maximize the following log likelihood function: Note that ⃗ϕ and ⃗ β parameter are separated in the log likelihood function, we can compute them separately as follows. ⃗ϕ can be easily computed by counting the frequencies of each top-l order. The main challenge is to accurately estimate the ⃗ β part, which is the main focus of the rest of this section. The following theorem provides a necessary and sufficient condition for the objective function in (4) to be strictly concave, which turns out to be the same condition for the identifiability of PLX-TO. Strict concavity is desirable because, combined with boundedness, it guarantees the convergence of MLE. Theorem 3. For any PLX-TO and any data P = (O1, . . . ,On), the log likelihood function in (4) is strictly concave if and only if Norm(X) has full row rank. The full proof can be found in Appendix G.5. We now introduce an assumption to guarantee the boundedness of MLE for given data P . Boundedness is important for consistency because a strictly concave function may not converge if it is unbounded. For any j ≤ n, i1 ≤ m, and i2 ≤ m, we define ξj,i1i2 as follows. Assumption 1. Let X ∈ Rd×mn denote a feature matrix and let P denote the data. For any r ≤ d, there exist j1, j2 ∈ {1, . . . , n} with j1 ̸= j2 and i1, i2 ∈ {1, . . . ,m} with i1 ̸= i2 such that ξj1,i1i2 ξj2,i1i2 (xj1i1,r-xj1i2,r)(xj2i1,r-xj2i2,r) < 0. At a high level, Assumption 1 is a mild condition that requires sufficient diversity in agents' preferences, which mirrors Hunter's assumption for PL [Hunter, 2004, Assumption 1]. The following lemma shows that Assumption 1 is sufficient for MLE to be bounded. Lemma 1. For any PLX-TO and data P, if Assumption 1 holds then the MLE in (4) is bounded. The proof is provided in Appendix G.6. Finally, the following theorem provides a bound on the RMSE of MLE for PLX -TO given that Norm(X) has full row rank. Figure 3: MSE (left) and Runtime (right) with 95% confidence intervals for MLE on PLX -TO given top-1 only, top-3 only, top-5 only, and top-9 (full rankings) over 2000 trials. Results for Top-7 are very close to those for top-9, and therefore omitted. ![Image](https://ijcai.org/proceedings/2022/fulltext/525/image_000002_a15069ad358f503a6bb5559a8259159e15d8fbb0c5ea0e6967ce4c8a39babe32.png) Theorem 4. Given any PLX-TO over m alternatives and n agents with the feature matrix X ∈ Rd×mn . Define L(⃗ β) = 1n ∑nj=1 ln PrPLX (Oj |⃗ β), which is 1n of the objective function in (4). Let H(⃗ β) denote the Hessian matrix of L(⃗ β) and λ1(⃗ β) be the smallest eigenvalue of -H(⃗ β). Let ⃗ β0 denote the ground truth parameter and ⃗ β∗ denote the estimated parameter that is computed using (4). Define λmin = min0≤σ≤1 λ1(σ⃗ β∗ + (1 - σ)⃗ β0 ). If Norm(X) has full row rank and Assumption 1 holds, then for any 0 < δ < 1, with probability 1 - δ, where c is the difference between the largest and the smallest entries of X . The full proof is in Appendix G.7. The RMSE (root-mean-square-error) bound given by Theorem 4 is not tight since we make no assumptions on the distribution of features. While Theorem 4 does provide insights on convergence of MLE: 1. Consistency: as n increases, RMSE ||⃗ β0 - ⃗ β∗ ||2 decreases at the rate of 1 √n . When n approaches infinity, RMSE approaches 0. 3. Approximation of λmin: in practice, when the size of data is not too small, λmin can be approximated by λ1(⃗ β∗ ) because ⃗ β∗ approaches ⃗ β0 as n increases. This gives a practical way of computing the RMSE bound when the ground truth is unknown. ## 5 Experiments We show experiments on synthetic data in this section and provide additional experiments on mixture models and on real-world data in the appendix. Setup. Fix m = 10 and d = 10. For each agent and each alternative, the feature vector is generated in [-1, 1] uniformly at random. Each component in ⃗ β is generated uniformly at random in [-2, 2]. MLE for PLX-TO was implemented in MATLAB with the built-in fminunc function and tested on a Ubuntu Linux server with Intel Xeon E5 v3 CPUs each clocked at 3.50 GHz. We use mean squared error (MSE) and runtime to measure the statistical efficiency and computational efficiency of algorithms, respectively. Results are shown in Figure 3. All values are averaged over 2000 trials. Observations. Figure 3 shows the performance of MLE for PLX -TO. We observe that MSE decreases as the number of agents increases, which demonstrates consistency of MLE for PLX -TO. Moreover, learning from top-l preferences with different l values provides tradeoffs between statistical efficiency and computational efficiency. ## 6 Summary and FutureWork We provide the first set of theoretical results on the identifiability of mixtures of PL with features for top-l preferences. We also identify conditions for the MLE of PLX-TO to be consistent, and propose an EM algorithm to handle general k-PLX-TO. In the full version of this paper [Zhao et al., 2022], we provide a generalized Rank-Breaking then Composite Marginal Likelihood algorithm for learning RUMs beyond PL from incomplete preferences and show its performance on synthetic data. [Zhao et al., 2022] also includes additional experiments on mixture models as well as missing proofs. Generic identifiability and efficient algorithms for k-PLX -TO are natural questions for future work. ## Acknowledgements We thank anonymous reviewers for helpful comments. Lirong Xia is supported by NSF #1453542 and a gift fund from Google. Ao Liu is supported by RPI-IBM AIHN scholarship. ## References 1. [Azari Soufiani et al., 2012] Hossein Azari Soufiani, David C. Parkes, and Lirong Xia. Random utility theory for social choice. In Proceedings of Advances in Neural Information Processing Systems, pages 126-134, 2012. 2. [Azari Soufiani et al., 2013] Hossein Azari Soufiani, David C. Parkes, and Lirong Xia. Preference Elicitation For General Ran- dom Utility Models. In Proceedings of Uncertainty in Artificial Intelligence, 2013. 3. [Baltrunas et al., 2010] Linas Baltrunas, Tadas Makcinskas, and Francesco Ricci. Group recommendations with rank aggrega- tion and collaborative filtering. In Proceedings of the fourth ACM conference on Recommender systems, pages 119-126, 2010. 4. [Berry et al., 1995] Steven Berry, James Levinsohn, and Ariel Pakes. Automobile prices in market equilibrium. Econometrica, pages 841-890, 1995. 5. [Chen et al., 2013] Xi Chen, Paul N Bennett, Kevyn Collins- Thompson, and Eric Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the sixth ACM interna- tional conference on Web search and data mining, pages 193-202, 2013. 6. [Chierichetti et al., 2018] Flavio Chierichetti, Ravi Kumar, and An- drew Tomkins. Learning a mixture of two multinomial logits. In International Conference on Machine Learning, pages 961-969, 2018. 7. [Dwork et al., 2001] Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web, pages 613-622, 2001. 8. [Gormley and Murphy, 2008] Isobel Claire Gormley and Thomas Brendan Murphy. Exploring voting blocs within the irish electorate: A mixture modeling approach. Journal of the American Statistical Association, 103(483):1014-1027, 2008. 9. [Grün and Leisch, 2008] Bettina Grün and Friedrich Leisch. Identifi- ability of finite mixtures of multinomial logit models with varying and fixed effects. Journal of classification, 25(2):225-247, 2008. 10. [Hüllermeier et al., 2008] Eyke Hüllermeier, Johannes Fürnkranz, Weiwei Cheng, and Klaus Brinker. Label ranking by learning pairwise preferences. Artificial Intelligence, 172(16-17):1897- 1916, 2008. 11. [Hunter, 2004] David R Hunter. Mm algorithms for generalized bradley-terry models. The annals of statistics, 32(1):384-406, 2004. 12. [Khetan and Oh, 2016] Ashish Khetan and Sewoong Oh. Data- driven rank breaking for efficient rank aggregation. The Journal of Machine Learning Research, 17(1):6668-6721, 2016. 13. [Liu et al., 2019] Ao Liu, Zhibing Zhao, Chao Liao, Pinyan Lu, and Lirong Xia. Learning plackett-luce mixtures from partial preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4328-4335, 2019. 14. [Liu, 2009] Tie-Yan Liu. Learning to rank for information retrieval. Information Retrieval, 3(3):225-331, 2009. 15. [Luce, 1959] Duncan R. Luce. Individual choice behavior. John Wiley, 1959. 16. [Mao et al., 2013] Andrew Mao, Ariel D Procaccia, and Yiling Chen. Better human computation through principled voting. In Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013. 17. [Maystre and Grossglauser, 2015] Lucas Maystre and Matthias Grossglauser. Fast and accurate inference of plackett-luce mod- els. In Advances in neural information processing systems, pages 172-180, 2015. 18. [McFadden, 1973] Daniel McFadden. Conditional logit analysis of qualitative choice behavior. In Frontiers of Econometrics, pages 105-142, New York, NY, 1973. Academic Press. 19. [Mollica and Tardella, 2017] Cristina Mollica and Luca Tardella. Bayesian plackett-luce mixture models for partially ranked data. Psychometrika, 82(2):442-458, 2017. 20. [Negahban et al., 2017] Sahand Negahban, Sewoong Oh, and De- vavrat Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1):266-287, 2017. 21. [Oh and Shah, 2014] Sewoong Oh and Devavrat Shah. Learning mixed multinomial logit model from ordinal data. In Advances in Neural Information Processing Systems, pages 595-603, 2014. 22. [Plackett, 1975] Robin L. Plackett. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statis- tics), 24(2):193-202, 1975. 23. [Schäfer and Hüllermeier, 2018] Dirk Schäfer and Eyke Hüllermeier. Dyad ranking using plackett-luce models based on joint feature representations. Machine Learning, 107(5):903-941, 2018. 24. [Soufiani et al., 2013] Hossein Azari Soufiani, William Chen, David C Parkes, and Lirong Xia. Generalized method-of-moments for rank aggregation. In Advances in Neural Information Process- ing Systems, pages 2706-2714, 2013. 25. [Tkachenko and Lauw, 2016] Maksim Tkachenko and Hady W Lauw. Plackett-luce regression mixture model for heterogeneous rankings. In Proceedings of the 25th ACM International on Confer- ence on Information and Knowledge Management, pages 237-246, 2016. 26. [Train, 2009] Kenneth E. Train. Discrete Choice Methods with Sim- ulation. Cambridge University Press, 2nd edition, 2009. 27. [Yıldız et al., 2020] İlkay Yıldız, Jennifer Dy, Deniz Erdogmus ¸, Jayashree Kalpathy-Cramer, Susan Ostmo, J Peter Campbell, Michael F Chiang, and Stratis Ioannidis. Fast and accurate ranking regression. In International Conference on Artificial Intelligence and Statistics, 2020. 28. [Zhao and Xia, 2018] Zhibing Zhao and Lirong Xia. Composite marginal likelihood methods for random utility models. In In- ternational Conference on Machine Learning, pages 5922-5931, 2018. 29. [Zhao and Xia, 2019] Zhibing Zhao and Lirong Xia. Learning mix- tures of plackett-luce models from structured partial orders. In Advances in Neural Information Processing Systems, pages 10143- 10153, 2019. 30. [Zhao et al., 2016] Zhibing Zhao, Peter Piech, and Lirong Xia. Learning mixtures of plackett-luce models. In International Con- ference on Machine Learning, pages 2906-2914, 2016. 31. [Zhao et al., 2018a] Zhibing Zhao, Haoming Li, Junming Wang, Jef- frey Kephart, Nicholas Mattei, Hui Su, and Lirong Xia. A Cost- Effective Framework for Preference Elicitation and Aggregation. In Proceedings of Uncertainty in Artificial Intelligence, 2018. 32. [Zhao et al., 2018b] Zhibing Zhao, Tristan Villamil, and Lirong Xia. Learning mixtures of random utility models. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018. 33. [Zhao et al., 2022] Zhibing Zhao, Ao Liu, and Lirong Xia. Learning mixtures of random utility models with features from incomplete preferences. arXiv preprint arXiv:2006.03869, 2022.