論文の概要: Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation

• arxiv url: http://arxiv.org/abs/2507.08108v1
• Date: Thu, 10 Jul 2025 18:52:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-14 18:03:54.147391
• Title: Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation
• Title（参考訳）: 学習距離メトリックを用いたマロースモデル:サンプリングと最大類似度推定
• Authors: Yeganeh Alimohammadi, Kiana Asgari,
• Abstract要約: データから直接距離距離を学習するMallowsモデルの一般化を提案する。 具体的には、$L_alpha$ distances: $d_alpha(pi,sigma):=sum_i=1 |pi(i)-sigma(i)|alpha$である。 このサンプリングアルゴリズムを用いて、中央ランク、分散パラメータ、および最適距離距離を共同で推定する、効率的な最大類似度推定(MLE)アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.1534667887016089
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: \textit{Mallows model} is a widely-used probabilistic framework for learning from ranking data, with applications ranging from recommendation systems and voting to aligning language models with human preferences~\cite{chen2024mallows, kleinberg2021algorithmic, rafailov2024direct}. Under this model, observed rankings are noisy perturbations of a central ranking $\sigma$, with likelihood decaying exponentially in distance from $\sigma$, i.e, $P (\pi) \propto \exp\big(-\beta \cdot d(\pi, \sigma)\big),$ where $\beta > 0$ controls dispersion and $d$ is a distance function. Existing methods mainly focus on fixed distances (such as Kendall's $\tau$ distance), with no principled approach to learning the distance metric directly from data. In practice, however, rankings naturally vary by context; for instance, in some sports we regularly see long-range swaps (a low-rank team beating a high-rank one), while in others such events are rare. Motivated by this, we propose a generalization of Mallows model that learns the distance metric directly from data. Specifically, we focus on $L_\alpha$ distances: $d_\alpha(\pi,\sigma):=\sum_{i=1} |\pi(i)-\sigma(i)|^\alpha$. For any $\alpha\geq 1$ and $\beta>0$, we develop a Fully Polynomial-Time Approximation Scheme (FPTAS) to efficiently generate samples that are $\epsilon$- close (in total variation distance) to the true distribution. Even in the special cases of $L_1$ and $L_2$, this generalizes prior results that required vanishing dispersion ($\beta\to0$). Using this sampling algorithm, we propose an efficient Maximum Likelihood Estimation (MLE) algorithm that jointly estimates the central ranking, the dispersion parameter, and the optimal distance metric. We prove strong consistency results for our estimators (for any values of $\alpha$ and $\beta$), and we validate our approach empirically using datasets from sports rankings.
• Abstract（参考訳）: \textit{Mallows model}は、ランキングデータから学習するための広く使われている確率的フレームワークであり、推薦システムから投票まで、言語モデルと人間の嗜好を一致させる—\cite{chen2024mallows, kleinberg2021algorithmic, rafailov2024direct} このモデルの下では、観測されたランク付けは、中央ランクの$\sigma$のノイズの多い摂動であり、確率は$\sigma$、すなわち$P (\pi) \propto \exp\big(-\beta \cdot d(\pi, \sigma)\big)、$$$\beta > 0$は分散を制御し、$d$は距離関数である。 既存の手法は主に固定距離(Kendallの$\tau$ distanceなど)に焦点を当てており、データから直接距離メートル法を学ぶための原則的なアプローチは存在しない。 例えば、あるスポーツでは、定期的に長距離スワップ(ローランクのチームがハイランクのスワップを打つ)を見るが、他のスポーツではそのようなイベントは稀である。 そこで本研究では,データから直接距離距離を学習するMallowsモデルの一般化を提案する。 具体的には、$L_\alpha$ 距離にフォーカスする: $d_\alpha(\pi,\sigma):=\sum_{i=1} |\pi(i)-\sigma(i)|^\alpha$。 任意の$\alpha\geq 1$および$\beta>0$に対して、真分布に対して$\epsilon$-(全変動距離)のサンプルを効率的に生成するフルポリノミアル時間近似スキーム(FPTAS)を開発する。 L_1$ と $L_2$ の特別な場合であっても、これは消滅する分散(\beta\to0$)を必要とする事前の結果を一般化する。 このサンプリングアルゴリズムを用いて、中央ランク、分散パラメータ、および最適距離距離を共同で推定する、効率的な最大類似度推定(MLE)アルゴリズムを提案する。 評価値($\alpha$と$\beta$の任意の値)に対して強い一貫性を証明し、スポーツランキングのデータセットを用いて実証的にアプローチを検証する。

関連論文リスト

• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Multiple-policy Evaluation via Density Estimation [30.914344538340412]
  本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。 低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
  論文  参考訳（メタデータ） (2024-03-29T23:55:25Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
  一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。 我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
  論文  参考訳（メタデータ） (2022-02-16T16:24:31Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
  本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。 また、ディキンウォークの「ソフトパイ」バージョンも提示する。
  論文  参考訳（メタデータ） (2021-11-07T13:44:50Z)
• Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method [5.025654873456756]
  静的設定から動的設定への古典的BTL(Bradley-Terry-Luce)モデルの拡張について検討する。 我々は mathbbRn$ のアイテム $w_t* の潜在強度をいつでも回復することを目指している。 また、実データおよび合成データに関する実験で理論解析を補完する。
  論文  参考訳（メタデータ） (2021-09-28T14:01:40Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。