{'fraction_non_alphanumeric': 0.04446660705688149, 'fraction_numerical': 0.01585391017263911, 'mean_word_length': 4.432280963945451, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning partially ranked data based on graph regularization

Ranked data appear in many different applications, including voting and consumer surveys. There often exhibits a situation in which data are partially ranked. Partially ranked data is thought of as missing data. This paper addresses parameter estimation for partially ranked data under a (possibly) non-ignorable missing mechanism. We propose estimators for both complete rankings and missing mechanisms together with a simple estimation procedure. Our estimation procedure leverages a graph regularization in conjunction with the Expectation-Maximization algorithm. Our estimation procedure is theoretically guaranteed to have the convergence properties. We reduce a modeling bias by allowing a non-ignorable missing mechanism. In addition, we avoid the inherent complexity within a non-ignorable missing mechanism by introducing a graph regularization. The experimental results demonstrate that the proposed estimators work well under non-ignorable missing mechanisms.


Introduction
Data commonly come in the form of ranking in preference survey such as voting and consumer surveys. Asking people to rearrange items according to their preference, we obtain the collection of rankings. Several methods for ranked data have been proposed. Mallows (1957) proposed a parametric model, now called the Mallows model; Diaconis (1989) developed a spectral analysis for ranked data; Recently, the analysis of ranked data has gathered much attention in machine learning community (see Liu (2011); Fürnkranz and Hüllermeier (2011)). See Section 1.2 for more details.
Partially ranked data is often observed in real data analysis. This is because one does not necessarily express his or her preference completely; for example, according to the election records of the American Psychological Association collected in 1980, one-third of ballots provided full preferences for five candidates, and the rest provided only top-t preferences with t = 1, 2, 3 (see Section 2A in Diaconis (1989)); Data are commonly of partially ranked in movie ratings because respondents usually know only a few movie titles among a vast number of movies. Therefore, analyzing partially ranked data efficiently extends the range of application of statistical methods for ranked data.
Partially ranked data is thought of as missing data. We can naturally consider that there exists a latent complete ranking behind a partial ranking as discussed in Lebanon and Mao (2008). The existing studies for partially ranked data make the Missing-At-Random (MAR) assumption, that is, an assumption that the missing mechanism generating partially ranked data is ignorable; Under the MAR assumption, Busse et al. (2007) and Meilȃ and Chen (2010) leverage an extended distance for partially ranked data; Lu and Boutilier (2011) introduces a probability model for partially ranked data. However, an improper application of the MAR assumption may lead to a relatively large estimation error as argued in the literature on missing data analysis (Little and Rubin (2014)). In the statistical sense, if the missing mechanism is non-ignorable, using the MAR assumption is equivalent to using a misspecified likelihood function, which causes significantly biased parameter estimation and prediction. In fact, Marlin and Zemel (2009) points out that there occurs a violation of the MAR assumption in music rankings. This paper addresses learning the distribution of complete and partial rankings based on partially ranked data under a (possibly) non-ignorable missing mechanism. Our approach includes estimating a missing mechanism. However, estimating a missing mechanism has an intrinsic difficulty. Consider a top-t ranking of r items. Length t characterizes the missing pattern generating a top-t ranking from a complete ranking with r items. It requires r!(r − 2) parameters to fully parameterize the missing mechanism since r! multinomial distributions with r − 1 categories models the missing mechanism. Note that the number of complete rankings is r!. A large number of parameters cause over-fitting especially when the sample size is small. To avoid over-fitting, we introduce an estimation method leveraging the recent graph regularization technique (Hallac et al. (2015)) together with the Expectation-Maximization (EM) algorithm. The numerical experiments using simulation data as well as applications to real data indicate that our proposed estimation method works well especially under non-ignorable missing mechanisms.
1.1. Contribution. In this paper, we propose estimators for the distribution of a latent complete ranking and for a missing mechanism. To this end, we employ both a latent variable model and a recently developed graph regularization. Our proposal has two merits: First, we allow a missing mechanism to be non-ignorable by fully parameterizing it. Second, we reduce over-fitting due to the complexity of missing mechanisms by exploiting a graph regularization method. Figure 1. A latent structure behind partially ranked data when the number of items is four: A ranking is expressed as a list of ranked items. The number located at the i-th position of a list represents the label of the i-th preference. The top layer shows latent complete rankings with a graph structure. A vertex in the top layer corresponds to a latent complete ranking. A edge in the top layer is endowed by a distance between complete rankings. The bottom three layers show partial rankings generated according to missing mechanisms. An arrow from the top layer to the bottom three layers corresponds to a missing pattern. A probability on arrows from a complete ranking to the resulting partial rankings corresponds to a missing mechanism.
Our ideas for the construction of the estimators are two-fold: First, we work with a latent structure behind partially ranked data (see Figure 1). This structure consists of the graph representing complete rankings (in the top layer) and arrows representing missing patterns. In this structure, a vertex in the top layer represents a latent complete ranking; An edge is endowed by a distance between complete rankings; An arrow from the top layer to the bottom layers represents a missing pattern; A multinomial distribution on arrows from a complete ranking corresponds to a missing mechanism. Second, we assume that two missing mechanisms become more similar as the associated complete rankings get closer to each other on the graph (in the top layer). Together with both the restriction to the probability simplex and the EM algorithm, these ideas are implemented by the graph regularization method (Hallac et al. (2015)) under the probability restriction. In addition, we discuss the convergence properties of the proposed method.
The simulation studies as well as applications to real data demonstrate that the proposed method improves on the existing methods under non-ignorable missing mechanisms, and the performance of the proposed method is comparable to those of the existing methods under the MAR assumption.
1.2. Literature review. Relatively scarce is the literature on the inference for ranking-related data with (non-ignorable) missing data. Marlin et al. (2007) points out that the MAR assumption does not hold in the context of the collaborative filtering. Marlin et al. (2007) and Marlin and Zemel (2009) propose two estimators based on missing mechanisms. These estimators show the higher performance both in prediction of rating and in the suggestion of top-t ranked items to users than estimators ignoring a missing mechanism. Using the Plackett-Luce and the Mallows models, Fahandar et al. (2017) introduces a rank-dependent coarsening model for pairwise ranking data. This study is different from these studies in types of ranking-related data: Marlin and Zemel (2009) and Marlin et al. (2007) discuss rating data; Fahandar et al. (2017) discusses pairwise ranking data; this study discusses partially ranked data.
Several methods have been proposed for estimating distributions of partially ranked data (Beckett (1993); Busse et al. (2007); Meilȃ and Chen (2010); Lebanon and Mao (2008); Jacques and Biernacki (2014); Caron et al. (2014)). These methods regard partially ranked data as missing data. Beckett (1993) discusses imputing items on missing positions of a partial ranking by employing the EM algorithm. Busse et al. (2007) and Meilȃ and Chen (2010) discuss the clustering of top-t rankings by the existing ranking distances for top-t rankings. Lebanon and Mao (2008) proposes a nonparametric model together with a computationally efficient estimation method for partially ranked data. For the proposal, Lebanon and Mao (2008) exploits the algebraic structure of partial rankings and utilizes the Mallows distribution as a smoothing kernel. Jacques and Biernacki (2014) proposes a clustering algorithm for multivariate partially ranked data. Caron et al. (2014) discusses Bayesian non-parametric inferences of top-t rankings on the basis of the Plackett-Luce model. Caron et al. (2014) does not explicitly rely on the framework that regards partially ranked data as the result of missing data; However, the model discussed in Caron et al. (2014) is equivalent to that under the MAR assumption. Overall, all previous studies rely on the MAR assumption, whereas our study is the first attempt to estimate the distribution of partially ranked data with a (possibly) non-ignorable missing mechanism.
We work with the graph regularization framework called Network Lasso (Hallac et al. (2015)). Network Lasso employs the alternating direction method of multipliers (ADMM; see Boyd et al. (2011)) to solve a wide range of regularization-related optimization problems of a graph signal that cannot be solved efficiently by generic optimization solvers. In addition, Network Lasso has a desirable convergence property, cooperates with distributed processing systems, and has been applied to various optimization problems on a graph. We present an application of Network Lasso to missing data analysis. In the application, we coordinate Network Lasso with the probability simplex constraint and the EM algorithm.
1.3. Organization. The rest of this paper is organized as follows. Section 2 formulates a probabilistic model of partially ranked data based on a missing mechanism, and introduces a distancebased graph structure for a complete ranking. Section 3 proposes the regularized estimator for both a latent complete ranking and a missing mechanism. We also discuss the convergence properties of the proposed estimation procedure. Section 4 demonstrates the result of simulation studies and real data analysis. Section 5 concludes the paper. The concrete algorithm of the proposed estimation procedure and The proof of the convergence property are provided in Appendices A and B, respectively.

Preliminaries
2.1. Notation. We begin with introducing notations for analyzing partially ranked data. In this paper, we identify a complete ranking of r items {1, . . . , r} with a permutation that maps each item i ∈ {1, . . . , r} uniquely to a corresponding rank {1, . . . , r}. A top-t ranking is a list of t items out of r items. We identify a top-t ranking with a permutation that maps an item in a subset of items uniquely to a corresponding rank in {1, . . . , t}.
We denote by S r the collection of all complete rankings of r items. We denote by S r the collection of all top-t rankings with t running through t = 1, . . . , r − 1. We denote by t(τ ) the length of a partial ranking τ ∈ S r . A tuple of a complete ranking π and length t uniquely determines a top-t ranking τ : π −1 (i) = τ −1 (i) for i = 1, . . . , t, where π −1 and τ −1 denote the inverses of π and τ , respectively. We define the collection of complete rankings compatible with a given ranking τ ∈ S r as [τ ] = {π ∈ S r | π −1 (i) = τ −1 (i) (i = 1, . . . , t(τ ))}.
2.2. Partial rankings and a missing mechanism. Next we introduce notations and terminologies for a probabilistic model with a missing mechanism. A probabilistic model for top-t ranked data with a general missing mechanism consists of a probabilistic model of generating complete rankings and that of a missing mechanism. The joint probability of a complete ranking and a missing mechanism is decomposed as where P (π) determines how a complete ranking is filled, and P (t | π) specifies a missing pattern conditioned on the latent complete ranking π. Then, the probability of a top-t ranking τ ∈ S r is obtained by marginalizing a latent complete ranking out: Now distributions P (t | π) and P (π) are parameterized by φ and θ, respectively; hence P (τ ; θ, φ) = π∈[τ ] P (t | π; φ)P (π; θ). We call {P (π; θ) : θ ∈ Θ} with a parameter space Θ a complete ranking model and {P (t | π; φ) : φ ∈ Φ} with a parameter space Φ a missing model. We call θ a complete ranking parameter, and call φ a missing parameter, respectively. Given the i.i.d. observations τ (n) = {τ 1 , . . . , τ n ∈ S r }, we denote the negative log-likelihood function by 2.3. Distances, graph structures, and distributions on complete rankings. We end this section with introducing distances, graph structures, and distributions on complete rankings.
We endow the class S r of complete rankings with a distance structure as follows. Since we identify the class S r as a the class of permutations, we endow S r with the symmetric group structure and its group law •. Using this identification, we leverage distances on symmetric groups for distances on S r . There exist a large number of distances on S r such as the Kendall distance, the Spearman rank correlation metric, and the Hamming distance. Among these, the Kendall distance (Kendall (1938)) has been often used in statistics and machine learning. The Kendall distance between two complete rankings π 1 and π 2 , d(π 1 , π 2 ), is defined as where A is the whole class of adjacent transpositions. This distance is suitable for describing similarity between preferences because the transform of a complete ranking by a single adjacent transposition is just the exchange of the i-th and (i + 1)-th preferences. In this paper, we focus on the Kendall distance d as a distance on S r .
There exists a one-to-one correspondence between the distance structure with the Kendall distance and a graph structure. Set the vertex set V = S r and set the edge set E = {{π, π } : there exists b ∈ A such that π = b • π }. Then the distance structure (S r , d) corresponds one-toone to the graph G = (V, E), since the Kendall distance d(π, π ) is its minimum path length between the vertices corresponding to π,π . Remark that E is rewritten as E = {{π, π } : d(π, π ) = 1}.
We introduce a well-known probabilistic model for complete rankings. The Mallows model (Mallows (1957)) is one of the most popular probabilistic models for complete rankings. The Mallows model associated with the Kendall distance is defined as where σ is a location parameter indicating a representative ranking, c is a concentration parameter indicating a decay rate, and Z(c) = π∈Sr exp{−cd(π, σ)} is a normalizing constant that depends only on c. The mixture model of K ∈ N Mallows distributions is defined as represent the parameters of each mixture component. The Mallows mixture model has been used for estimation and clustering analysis of ranked data (Murphy and Martin (2003); Busse et al. (2007)).

Proposed Method
In this section, we propose estimators for both complete ranking and missing models together with a simple estimation procedure. Here we assume that the parameterization of the complete ranking and missing models is separable, that is, θ and φ are distinct. We use the following missing model {P (t | π; φ) : φ ∈ Φ} to allow a non-ignorable missing mechanism: We make no assumptions on a complete ranking model {P (π; θ) : θ ∈ Θ}.
We conduct minimization in the definition ofθ,φ using the following EM algorithm: At the (m + 1)-th step, set where for i ∈ {1, . . . , n}, Consider minimizations (3) and (4). Minimization (3) depends on the form of a complete ranking model P (π; θ); For example, consider the Mallows model with θ = (σ, c) (see Section 2.3). In this case, we write down the minimization of θ at the (m + 1)-th step as follows: See Busse et al. (2007) for more details. Minimization (4) in the (m + 1)-th step is conducted using the following iteration: At the (l + 1)-th step, set Here, ϕ ∈ R r!(r−1) 2 is the copy variable of φ, u ∈ R r!(r−1) 2 is the dual variable, and L ρ is an augmented Lagrangian function with a penalty constant ρ defined as where q m+1 π,t := for all π ∈ S r and t = 1, . . . , r − 1. Note that q m+1 π,t = 0 when {i : t(τ i ) = t} is an empty set. The detailed algorithm is provided in Appendix A.
Remark 3.1 (Meaning of the penalty term). We make the assumption that two complete rankings close to each other in the Kendall distance have smoothly related missing probabilities. This assumption leads to adding a ridge penalty π,π ∈Sr d(π,π )=1 to the negative log-likelihood function. This assumption is reasonable because the Kendall distance measures the similarity of preferences expressed by two rankings.
Remark 3.2 (The proposed method under the MAR assumption). For top-t ranked data, the MAR assumption is expressed as Then under the MAR assumption, the negative log-likelihood function L(θ, φ; τ (n) ) is decomposed as which indicates that the parameter estimation for φ is unnecessary for estimating θ.
The proof is provided in Appendix B. The basis of the proof is reformulating the optimization problem (4) as an instance of the alternating direction method of multipliers (ADMM; Boyd et al. (2011): We rewrite the problem (4) as follows: where V is the vertex set of the graph defined in Section 2.3 and q π,t = i:t(τ i )=t K k=1 q i,k,π . Introducing a copy variable ϕ on the edge set, we recast the optimization problem (14) into an equivalent form: Note that this reformulation follows the idea of Hallac et al. (2015). We employ ADMM to solve the optimization of the sum of objective functions of splitted variables under linear constraints.

Numerical experiments
In this section, we apply our methods to both simulation studies and real data analysis. In simulation studies, we use the Mallows mixture models (2) with two types of missing models. In the real data analysis, we use the election records of the American Psychological Association collected in 1980.

Performance measures.
We evaluate the performance of several estimators for θ and φ in estimating distributions of a latent complete ranking and of a partial ranking. We measure the performance using the following total variation losses: When the true values of a complete ranking and missing parameters are θ and φ, respectively, the losses of estimatorsθ andφ are given as Losses L par and L comp measure the estimation losses for partial and complete ranking distributions, respectively.

Method comparison.
We compare our estimators with the estimator based on the maximum entropy approach proposed by Busse et al. (2007) and a non-regularized estimator, abbreviated by ME and NR, respectively. In addition, we use the proposed estimator with the regularization parameter selected using two-fold cross-validation based on L par .
We denote the proposed method introduced in section 3 with the value of regularization parameter λ as Rλ and that with the regularization parameter selected using cross-validation as RCV.
The maximum entropy approach (ME) uses an extended distance between top-t rankings to introduce an exponential family distribution of a top-t ranking. From the viewpoint of missing data analysis, ME implicitly assumes the MAR assumption. For this reason, in the maximum entropy approach, we estimate the missing model parameter φ by assuming homogeneous missing probabilities P (t | π) = φ t (∀π ∈ S r ) and using the maximum likelihood in the evaluation of the loss L par (θ, φ).
The non-regularized estimator (NR) is the minimizer of the non-regularized likelihood function L(θ, φ; τ (n) ). The estimation based on the non-regularized likelihood function can be implemented straightforwardly.

Stopping criteria.
In simulation studies, we use the following stopping criteria and hyperparameters. We terminate the iteration of the EM algorithm when the change of the likelihood of the observable distribution gets lower than = 1. We terminate the iteration of ADMM when both the primal and dual residuals got less than p = d = 1 or when the number of iterations exceeded 100. In addition, to prevent being trapped in local minima due to the EM algorithm, we use the following devices. First, we use 10 different initial location parameters in the EM algorithm. Second, we make the value of the location parameter transit from the current to a different one in the first five iterations of the EM algorithm.

Simulation studies.
We conducted two simulation studies. The data-generating models are as follows: For complete ranking models, we use the Mallows and Mallows mixture models. For missing models, we use a binary missing mechanism in which the possible missing patterns are only that no items are missing or that all but the first items are missing. We parameterize missing models in such a way that there is a discrepancy between the distribution of a complete ranking generated by the latent Mallows model and the marginal distribution of a partial ranking restricted to S (r−1) r := {τ : t(τ ) = r − 1, τ ∈ S r }. Note that S (r−1) r is identical to S r as a set. In each simulation, we generate 100 datasets with sample size of n = 1000. We set the number of items to r = 5. 4.4.1. Tilting the concentration parameter. In the first simulation study, we use the Mallows model and the missing model that tilts the concentration parameter c: The missing model is parameterized by c * > 0 and R ∈ [0, 1] as φ π = (φ π,0 , . . . , φ π,(r−1) ) = (1 − C π (c * , R), 0, . . . , 0, C π (c * , R)), π ∈ S r where C π (c * , R) = min 1, In this parameterization, the parameter c * specifies the degree of concentration of the marginal distribution P (τ ; θ, φ) of a partial ranking restricted to S c)d(π, σ 0 )} ≤ 1, P (τ ; θ, φ) has the form of the Mallows distribution with the concentration parameter c * : where π(i) = τ (i), i = 1, . . . , r − 1. The parameter 0 ≤ R ≤ 1 specifies the proportion of partial rankings in S (r−1) r . We set c = 1, R = 0.7, and c * ∈ {0.8, 1, 1.2}. Figures 2 and 3 show the results. When c * = 1, the proposed methods outperform ME both in L par and L comp . When c * = 1, the proposed methods underperform compared to ME. These results reflect that the setting with c * = 1 satisfies the MAR assumption, whereas the settings with c * = 1 do not satisfy the MAR assumption. For L par , the proposed methods outperform NR regardless of the values of c * . However, there are subtle distinctions in the values of L comp of these methods.
The performance of the proposed method with the cross-validated regularization parameter (RCV) is comparable with that of the proposed method with the optimal regularization parameter both for L par and L comp , indicating the utility of cross-validation.
In this simulation study, we additionally use the classification error as the performance measure.  (c) w * 1 = 0.7 Figure 6. Boxplots of the classification errors for the dataset tilting the mixture coefficient: The compared methods are the maximum entropy approach (ME), the non-regularized estimator (NR), the proposed methods (R1; R10; R100) and its version with the cross-validation (RCV). The results with different values of the concentration parameter w * are shown in (A)-(C). Figures 4-6 show the results. The proposed methods outperform ME when w * 1 = 0.5 in comparing L par ; when w * 1 is 0.7 in comparing L comp ; when w * 1 = 0.5 in comparing the classification error. The proposed methods outperform NR both in comparing L par and L comp except when w * 1 is 0.7 for L comp . As w * deviates from 0.5, the classification error of ME increases. On the other hand, the classification errors of the other methods decrease.
4.5. Application to real data. We apply the proposed method to real data. We use the election records for five candidates collected by the American Psychological Association. Among the 15549 vote casts, only 5141 filled all candidates (t = 5, 4); 2108 filled t = 3; 2462 filled t = 2; and the rest filled only t = 1. For comparison, we chose several pairs of train and test datasets randomly to measure L par since we do not have the true values of the model parameters nor the form of the model. To see the dependence of the estimation performance on the sample size, we used different sizes (n = 100, 500, 1000, 5000, 10000) of the train datasets, whereas we fixed the size of the test datasets to n = 3000. We sampled test datasets independently 30 times and sampled train datasets from the remaining data independently 30 times for each size. In calculating L par , we used the empirical distribution of the employed test dataset as the true distribution. For a complete ranking model, we made the use of the likelihood of the Mallows mixture model with the number of clusters set to 3 as in Busse et al. (2007). Since R1 performs poorly in terms of L par according to the simulation study, we eliminate R1 from the candidate of two-fold cross-validation. Figures 7 and 8 show the result. When the sample size is small (n = 100, 500), the proposed method is comparable to ME, and NR works poorly. When the sample size is moderate (n = 1000), the proposed method outperforms both ME and NR. When the sample size is large (n = 5000, 10000), the proposed method outperforms ME, and it is comparable to NR. These results indicate that considering non-ignorable missing mechanisms contributes to the improvement of the performance when the sample size is sufficient, while the graph regularization reduces over-fitting when the sample size is insufficient.

Conclusion
We proposed a regularization method for partially ranked data to prevent modeling bias due to the MAR assumption and avoid over-fitting due to the complexity of missing models. Our simulation experiments showed that the proposed method improves on the maximum entropy approach (Busse et al. (2007)) under non-ignorable missing mechanisms. They also showed that the proposed method improves on the non-regularized estimator especially in estimating distribution of a partial ranking. Our real data analysis suggested that moderate or large sample sizes attribute the improvement by the proposed method and the proposed method is effective in reducing over-fitting.
We propose two main tasks for future work. The first task is to improve the computational efficiency of our method since it was not a priority in this study. Leveraging partial completion of items (instead of full completion) might be effective for reducing the computational cost. For this purpose, the distance of top-t ranking described in Busse et al. (2007) might be beneficial for the construction of the graph. The second task is to develop cross-validation or an information criterion for inferring the distribution of a latent complete ranking. In this study, we employed cross-validation based on the distribution of a partial ranking. When the distribution of a latent complete ranking is of interest, cross-validation based on the distribution of a latent complete ranking would be more suitable. However, the construction of such cross-validation would be difficult because the empirical distribution of a latent complete ranking cannot be obtained directly, which rises ubiquitously where one uses the EM algorithm for the estimation of latent variables. There have been several derivations of information criteria comprising the distribution of latent variables (Shimodaira (1994); Cavanaugh and Shumway (1998)). We conjecture that these derivations would be useful for inferring partially ranked data.
• Residual convergence: the primal residualr l ∈ R r!(r−1) 2 defined byr l π,π ,t := φ l π,t − ϕ l π,π ,t converges to 0 with respect to l: lim l→∞r l = 0; • Objective convergence: the convergence Objective convergence together with residual convergence implies convergence of the objective function L λ (φ; τ (n) , q m+1 (n) ), because we have where it follows from residual convergence and the continuity of g that |g(φ l ) − g(ϕ l )| → 0. The following is a sufficient condition for objective and residual convergence based on ADMM (see Section 3.2 of Boyd et al. (2011)): (I) The functions f and g are closed, proper, and convex; (II) Unaugmented Lagrangian L 0 has a saddle point.
Here unaugmented Lagrangian L 0 is defined as In what follows, we show that conditions (I) and (II) hold.
Hence, L − is coercive since we have L − (y n ) ≥ − L 0 (φ n , ϕ n , y n ) ≥ −2r!(r−1)+ y n 2 → ∞ (n → ∞) for any sequence {y n } ∞ n=1 satisfying y n 2 → ∞, and thus all level sets of L − are bounded. From the above, conditions (iv) and (v) are satisfied and thus we complete the proof.