論文の概要: On Sinkhorn's Algorithm and Choice Modeling
- arxiv url: http://arxiv.org/abs/2310.00260v1
- Date: Sat, 30 Sep 2023 05:20:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-05 05:32:19.637912
- Title: On Sinkhorn's Algorithm and Choice Modeling
- Title（参考訳）: Sinkhornのアルゴリズムと選択モデルについて
- Authors: Zhaonan Qu, Alfred Galichon, Johan Ugander
- Abstract要約: その結果, 最大推定問題は, 古典的行列バランス問題と, 対象列と列の和との等価性を示す。
この視点は、一見無関係な2つの研究領域の間の扉を開く。
これらの接続からインスピレーションを得て、シンクホーンのアルゴリズムの研究において重要なオープンな問題を解く。
- 参考スコア（独自算出の注目度）: 6.43826005042477
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For a broad class of choice and ranking models 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 important open problems
on the study of Sinkhorn's algorithm. We first prove the global linear
convergence of Sinkhorn's algorithm for non-negative matrices whenever finite
solutions to the matrix balancing problem exist. We characterize this global
rate of convergence in terms of the algebraic connectivity of the bipartite
graph constructed from data. Next, we also derive the sharp asymptotic rate of
linear convergence, which generalizes a classic result of Knight (2008), but
with a more explicit analysis that exploits an intrinsic orthogonality
structure. To our knowledge, these are the first quantitative linear
convergence results for Sinkhorn's algorithm for general non-negative matrices
and positive marginals. The connections we establish in this paper between
matrix balancing and choice modeling could help motivate further transmission
of ideas and interesting results in both directions.
- Abstract（参考訳）: Bradley-Terry-Luce モデルや Plackett--Luce モデルを含む、Luce の選択公理に基づく幅広い選択とランク付けモデルに対して、関連する最大推定問題は、ターゲット行と列和との古典的行列バランス問題と等価であることを示す。
この視点は、一見無関係な2つの研究領域の間の扉を開き、Sinkhornの行列バランスのための有名なアルゴリズムの特別な例またはアナログとして、文献をモデル化する選択において既存のアルゴリズムを統合することを可能にする。
これらの関係から着想を得て,sinkhornのアルゴリズムの研究において重要なオープン問題を解決した。
まず,非負行列に対するシンクホーンアルゴリズムの大域的線形収束を,行列バランス問題に対する有限解が存在する場合に証明する。
データから構築された二部グラフの代数的接続性の観点から,この収束率を特徴付ける。
次に、我々は線形収束の鋭い漸近的速度(2008年のナイトの古典的な結果を一般化する)を導出するが、本質的な直交構造を利用するより明示的な分析を行う。
我々の知る限りでは、これらは一般の非負行列と正の辺数に対するシンクホーンのアルゴリズムに対する最初の定量的線形収束結果である。
行列のバランスと選択モデルの間の関係は、アイデアのさらなる伝達と両方の方向における興味深い結果の動機付けに役立つだろう。
関連論文リスト
- Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping [56.57574396804837]
クラスタリングは機械学習とデータサイエンスにおける基本的なタスクであり、類似性グラフベースのクラスタリングはこの領域において重要なアプローチである。
マーカスマッピングと最適輸送の関係について検討する。
マーカス写像が特定の種類の最適輸送問題を解くことを証明し、マーカス写像によるこの問題の解法が最適輸送法を直接適用するよりも効率的であることを証明した。
論文 参考訳（メタデータ） (2024-08-06T03:34:43Z) - An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。
提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
論文 参考訳（メタデータ） (2024-03-17T21:43:19Z) - Data Assimilation for Sign-indefinite Priors: A generalization of
Sinkhorn's algorithm [0.0]
更新された値が指定された限界値と一致するように,符号の不確定な多次元配列を再検討する。
我々のアプローチはシュル「オーディンガー問題」の理性に従っており、限界分布に一致するように「適切な」確率測度を更新することを目的としている。
論文 参考訳（メタデータ） (2023-08-22T21:13:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。