論文の概要: On Sinkhorn's Algorithm and Choice Modeling

• arxiv url: http://arxiv.org/abs/2310.00260v2
• Date: Mon, 07 Apr 2025 15:59:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:05:33.100356
• Title: On Sinkhorn's Algorithm and Choice Modeling
• Title（参考訳）: Sinkhornのアルゴリズムと選択モデルについて
• Authors: Zhaonan Qu, Alfred Galichon, Wenzhi Gao, Johan Ugander,
• Abstract要約: その結果, 最大推定問題は, 古典的行列バランス問題と, 対象列と列の和との等価性を示す。 この視点は、一見無関係な2つの研究領域の間の扉を開く。 我々は、Sinkhornの行列バランスのための有名なアルゴリズムの特別な例またはアナログとして、文献をモデル化する選択において、既存のアルゴリズムを統一する。
• 参考スコア（独自算出の注目度）: 7.590510456875604
• License:
• Abstract: For a broad class of models widely used in practice for choice and ranking data based on Luce's choice axiom, including the Bradley--Terry--Luce and Plackett--Luce models, we show that the associated maximum likelihood estimation problems are equivalent to a classic matrix balancing problem with target row and column sums. This perspective opens doors between two seemingly unrelated research areas, and allows us to unify existing algorithms in the choice modeling literature as special instances or analogs of Sinkhorn's celebrated algorithm for matrix balancing. We draw inspirations from these connections and resolve some open problems on the study of Sinkhorn's algorithm. We establish the global linear convergence of Sinkhorn's algorithm for non-negative matrices whenever finite scaling matrices exist, and characterize its linear convergence rate in terms of the algebraic connectivity of a weighted bipartite graph. We further derive the sharp asymptotic rate of linear convergence, which generalizes a classic result of Knight (2008). To our knowledge, these are the first quantitative linear convergence results for Sinkhorn's algorithm for general non-negative matrices and positive marginals. Our results highlight the importance of connectivity and orthogonality structures in matrix balancing and Sinkhorn's algorithm, which could be of independent interest. More broadly, the connections we establish in this paper between matrix balancing and choice modeling could also help motivate further transmission of ideas and lead to interesting results in both disciplines.
• Abstract（参考訳）: Bradley-Terry-Luce モデルや Plackett-Luce モデルなど,Luce の選択公理に基づくデータの選択とランク付けに広く用いられているモデルに対して,関連する最大推定問題は,目標列と列和との古典的行列バランス問題と等価であることを示す。 この視点は、一見無関係な2つの研究領域の間の扉を開き、Sinkhornの行列バランスのための有名なアルゴリズムの特別な例またはアナログとして、文献をモデル化する選択において、既存のアルゴリズムを統一することを可能にする。 これらの接続からインスピレーションを得て、シンクホーンのアルゴリズムの研究においていくつかのオープンな問題を解く。 有限スケーリング行列が存在するとき、Sinkhornのアルゴリズムの非負行列に対する大域的線形収束を確立し、重み付き二部グラフの代数的接続性の観点からその線形収束率を特徴づける。 さらに、Knight (2008) の古典的な結果を一般化する、急激な漸近的な線形収束率を導出する。 我々の知る限り、これらは一般的な非負行列と正の限界に対するシンクホーンのアルゴリズムのための最初の定量的線形収束結果である。 この結果から,行列バランスにおける接続性と直交構造の重要性と,独立性のあるシンクホーンのアルゴリズムが注目されている。 より広範に言えば、行列のバランスと選択モデリングの間の関係は、アイデアのさらなる伝達を動機付け、両方の分野において興味深い結果をもたらすのにも役立ちます。

関連論文リスト

• Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping [56.57574396804837]
  クラスタリングは機械学習とデータサイエンスにおける基本的なタスクであり、類似性グラフベースのクラスタリングはこの領域において重要なアプローチである。 マーカスマッピングと最適輸送の関係について検討する。 マーカス写像が特定の種類の最適輸送問題を解くことを証明し、マーカス写像によるこの問題の解法が最適輸送法を直接適用するよりも効率的であることを証明した。
  論文  参考訳（メタデータ） (2024-08-06T03:34:43Z)
• A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach [12.679411410749521]
  本稿では,ニューラルネットワークによる格子縮小問題に対するアルゴリズム空間のパラメータ化と,教師付きデータを持たないアルゴリズムの探索を行うことが可能であることを示す。 本研究では,一様行列の因子を出力する深層ニューラルネットワークを設計し,非直交格子基底をペナルライズして自己指導的に学習する。 提案手法は,一連のベンチマークにおいて,Lenstra-Lenstra-Lov'aszアルゴリズムに匹敵する複雑性と性能を持つアルゴリズムが得られることを示す。
  論文  参考訳（メタデータ） (2023-11-14T13:54:35Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。 私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。 ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
  論文  参考訳（メタデータ） (2021-07-16T19:34:10Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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