Permutation-valued features arise in a variety of applications, either in a direct way when preferences are elicited over a collection of items, or an indirect way in which numerical ratings are converted to a ranking. To date, there has been relatively limited study of regression, classification, and testing problems …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,181 papers · 148 categories
Trend · papers per month
48 results for “Mallows kernel”
New methods extend kernel estimators for partial rankings, improving performance in machine learning tasks.
problem Incomplete rankings data in real-world applications.
method Antithetic and Monte Carlo kernel estimators for partial rankings, variance reduction scheme.
result Improved antithetic kernel estimator with lower variance and better performance.
Paper tightens sample complexity for Mallows and Generalized Mallows Models.
problem Estimating parameters of Mallows and Generalized Mallows Models.
method Introduced Mallows Block Model to analyze and derive tight sample complexity bounds.
result Tight sample complexity bound for learning Mallows and Generalized Mallows Model.
Kernels of Mallows Models under the Hamming Distance for solving the Quadratic Assignment Problemstat.ML
A new algorithm improves solving QAP with better performance.
problem Solving the Quadratic Assignment Problem (QAP) efficiently.
method Estimation of Distribution Algorithms (EDAs) with a non-parametric distance-based Mallows model.
result The proposed algorithm outperforms existing methods for QAP.
Paper extends top-k Mallows model for better user preference analysis.
problem Capturing real-world user preferences focusing on a limited set of items.
method Generalized top-k Mallows model, novel sampling scheme, efficient algorithm, active learning.
result New tools for analysis and prediction in decision-making scenarios.
The paper tackles learning true rankings from noisy, incomplete data.
problem Learning true rankings from incomplete and noisy data.
method Introduces a selective Mallows model for noisy rankings and derives upper and lower bounds on sample complexity.
result Strong asymptotically tight bounds on sample complexity for learning complete rankings and top-k rankings.
Polynomial time algorithm for learning mixtures of Mallows models with any number of components.
problem Learning parameters of mixtures of Mallows models with any constant number of components.
method Determinantal identity of Zagier, polynomial identifiability, test functions, information-theoretic lower bounds, local queries, beyond worst-case analysis.
result First polynomial time algorithm for provably learning mixtures of Mallows models with any constant number of components.
This paper tackles the problem of selecting among several linear estimators in non-parametric regression; this includes model selection for linear regression, the choice of a regularization parameter in kernel ridge regression, spline smoothing or locally weighted regression, and the choice of a kernel in multiple kern…
The paper proposes methods to identify and sample from mixtures of Mallows models for top-k rankings.
problem Identifying and sampling from mixtures of Mallows models for top-k rankings in a heterogeneous population.
method Efficient sampling algorithms and identifiability proofs for both components of the mixture.
result The identifiability and learnability of the Mallows components' parameters in the mixture.
We propose a novel parameterized family of Mixed Membership Mallows Models (M4) to account for variability in pairwise comparisons generated by a heterogeneous population of noisy and inconsistent users. M4 models individual preferences as a user-specific probabilistic mixture of shared latent Mallows components. Our k…
Clustered Mallows Modelstat.ME
Extends Mallows model to handle item indifference in rankings.
problem Real data often contains item indifference, challenging strict preference assumptions.
method Proposes Clustered Mallows Model (CMM) to accommodate item indifference.
result CMM provides a flexible representation of rank collections with ordered clusters.
New algorithm learns permutations mixtures with optimal sample complexity.
problem Learning mixtures of permutations in high-dimensional settings.
method Combining groups of pairwise comparisons and combinatorial method of moments.
result Optimal sample complexity proportional to log(n) for high-dimensional data.
The paper addresses model averaging and ensembling, providing theoretical and practical insights.
problem Combining least squares estimators from multiple candidate models for improved predictive accuracy.
method Establishes oracle inequalities for Mallows' criterion, proposes a novel Mallows-type MA procedure.
result Demonstrates the effectiveness of the proposed Mallows-type MA estimator through numerical experiments.
Paper improves feature selection accuracy using transfer learning.
problem Improving feature selection accuracy in information criteria-based methods.
method Proposes TLCp, a transfer learning procedure based on Mallows' Cp.
result TLCp outperforms conventional Cp in accuracy and stability.
Paper proposes a new anomaly detection method using Random Forest with Mallows-like criterion.
problem Inherent uncertainty in model selection for anomaly detection.
method Integrates Mallows-like criterion into Random Forest algorithm for anomaly detection.
result Proposed method outperforms traditional methods in accuracy and robustness.
New voting rules protect against strategic voting by robust statistics.
problem Strategic voting can skew election outcomes.
method Revisit Mallows model, develop robust estimator.
result Efficient estimator achieves nearly optimal robustness.
Algorithm learns mixtures of rankings from noisy data.
problem Learning an unknown mixture of rankings from noisy samples.
method Algorithm for different noise models, including heat kernel and Mallows model.
result High accuracy learning of mixture to time.
We generalize Mallows model to learn distance metrics from data.
problem Learning optimal distance metrics from noisy ranking data.
method Propose distances and develop FPTAS for sampling and MLE.
result Strong consistency of estimators for various and .
Fundamental weight systems identified as quantum states.
problem Identifying which weight systems are quantum states.
method Analyzing the Cayley distance kernel on the symmetric group and its positivity.
result All fundamental gl(n)-weight systems are quantum states.
A Unified Statistical Learning Model for Rankings and Scores with Application to Grant Panel Reviewstat.ME
Unified model combines scores and rankings for grant panel review.
problem Combining scores and rankings for quality assessment in panel review.
method Mallows-Binomial model with tree-search algorithm for exact MLE.
result Model combines scores and rankings to quantify object quality and measure consensus.
Ranking Differential Privacystat.ML
This paper protects rankings from differential privacy breaches.
problem Leakage of personal information in rankings.
method Develops ε-ranking differential privacy and a multistage ranking algorithm.
result Establishes the connection between Mallows model and ε-ranking differential privacy.
We analyze the generalized Mallows model, a popular exponential model over rankings. Estimating the central (or consensus) ranking from data is NP-hard. We obtain the following new results: (1) We show that search methods can estimate both the central ranking pi0 and the model parameters theta exactly. The search is n!…
The study of isospectral surfaces in Euclidean and hyperbolic geometries.
problem Existence of non-isometric surfaces with identical chord length distributions.
method Construction of isospectral pairs of hyperbolic surfaces without common covers.
result Found isospectral pairs of hyperbolic surfaces with no common cover.
We introduce a new family of minmax rank aggregation problems under two distance measures, the Kendall τ and the Spearman footrule. As the problems are NP-hard, we proceed to describe a number of constant-approximation algorithms for solving them. We conclude with illustrative applications of the aggregation methods on…
New sampling methods improve Shapley value estimation for machine learning models.
problem Approximating Shapley values for non-trivial models is computationally challenging.
method Investigates new quadrature techniques and quasi-Monte Carlo methods for permutation sampling.
result Significant improvements in Shapley value estimates over existing methods.
Extends Fisher's Discriminant Analysis for interval-valued data.
problem Classifying entities represented by intervals and histograms.
method Adapts Fisher's Discriminant Analysis using Moore's interval arithmetic and Mallows' distance.
result Discriminant directions for interval-valued data are numerically maximized.
This paper presents a natural extension of stagewise ranking to the the case of infinitely many items. We introduce the infinite generalized Mallows model (IGM), describe its properties and give procedures to estimate it from data. For estimation of multimodal distributions we introduce the Exponential-Blurring-Mean-Sh…
The paper applies communication theory to improve language model reranking.
problem Ensuring safety and accuracy in language model outputs.
method Drawing parallels between communication theory and language model reranking, the authors propose a protocol to improve reliability.
result The proposed protocol can achieve asymptotically error-free performance in noisy communication scenarios.
Hierarchical Partial-Order Models for Ranking
problem Rank aggregation combining ordered lists
method Hierarchical partial-order models
result Bayesian inference for latent poset hierarchy
Novel algorithm optimizes decision trees for nonlinear metrics.
problem Optimizing decision trees for nonlinear metrics like F1-score.
method Bi-objective optimisation approach to find optimal trees on Pareto frontier.
result The optimal tree for nonlinear metrics lies on the Pareto frontier.
Choosing to Rankcs.LG
Flexible ranking models from choice data.
problem Difficulties in modeling, learning from, and predicting rankings.
method Choice-based ranking models using repeated selection.
result Choice-based ranking models outperform existing models in various ranking tasks.
Cross-validation estimates model performance on unseen data, not training data.
problem Understanding how cross-validation estimates prediction error and its limitations.
method Analyzing linear models and popular prediction error estimates, introducing nested cross-validation.
result Cross-validation estimates the average prediction error of models fit on other unseen training sets, not the model at hand.
New ranking models for time series data using GARCH-type approach.
problem Handling time series of ranking data.
method Developed ranking GARCH models based on Mallows distribution and maximum likelihood estimation.
result The proposed models capture temporal dynamics of rankings effectively.
We present a Dirichlet process mixture model over discrete incomplete rankings and study two Gibbs sampling inference techniques for estimating posterior clusterings. The first approach uses a slice sampling subcomponent for estimating cluster parameters. The second approach marginalizes out several cluster parameters …
New method speeds up model selection for complex scientific tasks.
problem Exhaustive model selection is computationally infeasible for large model spaces.
method Branch-and-bound algorithm with non-monotonic criteria.
result Guaranteed identification of optimal models with significant computational speedups.
Discriminative EBM predicts Alzheimer's disease progression timeline more accurately.
problem Estimating the sequence of biomarker abnormalities in Alzheimer's disease.
method Discriminative event-based modeling (EBM) with a generalized Mallows model for central ordering and relative distance between events.
result The proposed method outperformed existing state-of-the-art EBM methods in ADNI and synthetic data.
Efficient algorithm to select tuning parameters in sparse regression modeling with regularizationstat.ME
In sparse regression modeling via regularization such as the lasso, it is important to select appropriate values of tuning parameters including regularization parameters. The choice of tuning parameters can be viewed as a model selection and evaluation problem. Mallows' type criteria may be used as a tuning param…
Solve for the Hyperparameter, Skip the Search: Kolmogorov-Optimal Scaling Laws for Spline Regressioncs.LG
KOLMOGOROV-OPTIMAL RESOLUTION ESTIMATION (KORE) solves spline regression without exhaustive search
problem Hyperparameter tuning in spline regression
method Solving for optimal resolution analytically
result KORE matches exhaustive cross-validation and outperforms tuned models
We extend the recently introduced theory of Lovasz-Bregman (LB) divergences (Iyer & Bilmes 2012) in several ways. We show that they represent a distortion between a "score" and an "ordering", thus providing a new view of rank aggregation and order based clustering with interesting connections to web ranking. We show ho…
Survey on minimal penalty algorithms and slope heuristics.
problem Choosing optimal multiplicative constants from data.
method Minimal penalty and slope heuristics approach.
result Slope heuristics performs almost as well as residual-based estimators.
We extend the recently introduced theory of Lovasz-Bregman (LB) divergences (Iyer & Bilmes, 2012) in several ways. We show that they represent a distortion between a 'score' and an 'ordering', thus providing a new view of rank aggregation and order based clustering with interesting connections to web ranking. We show h…
MallowsPO enhances LLM fine-tuning with a dispersion index of human preferences.
problem Lack of diversity in human preferences in DPO.
method Developed a dispersion index based on Mallows' theory to characterize preference diversity.
result Demonstrated improved performance in various tasks using the dispersion index.
CRS model improves ranking data modeling with theoretical guarantees.
problem Lack of rich, multimodal models for ranking data.
method Contextual Repeated Selection (CRS) model for multimodal ranking data.
result CRS model significantly outperforms existing methods in various ranking contexts.
RCPO uses ranked choice modeling for better LLM alignment.
problem Pairwise preference optimization limits LLM alignment.
method Unified framework combining preference optimization and ranked choice modeling.
result RCPO outperforms competitive baselines in LLM alignment.
A new measure normalizes clustering accuracy to evaluate algorithms better.
problem Evaluation of clustering algorithms is challenging due to limitations of existing measures.
method Proposes a new, normalised clustering accuracy measure.
result The new measure identifies worst-case scenarios and is more interpretable.
This paper develops robust confidence intervals in high-dimensional and left-censored regression. Type-I censored regression models are extremely common in practice, where a competing event makes the variable of interest unobservable. However, techniques developed for entirely observed data do not directly apply to the…
Many unsupervised kernel methods rely on the estimation of the kernel covariance operator (kernel CO) or kernel cross-covariance operator (kernel CCO). Both kernel CO and kernel CCO are sensitive to contaminated data, even when bounded positive definite kernels are used. To the best of our knowledge, there are few well…
Survey of kernels, RKHS, and their applications in machine learning.
problem Understanding kernels and their applications in machine learning.
method Review of historical context, mathematical definitions, and practical applications of kernels.
result Comprehensive overview of kernels, RKHS, and their applications.