論文の概要: Approximating a RUM from Distributions on k-Slates

• arxiv url: http://arxiv.org/abs/2305.13283v1
• Date: Mon, 22 May 2023 17:43:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-23 13:50:27.978923
• Title: Approximating a RUM from Distributions on k-Slates
• Title（参考訳）: k-スレート上の分布からラムを近似する
• Authors: Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Andrew Tomkins
• Abstract要約: 与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
• 参考スコア（独自算出の注目度）: 88.32814292632675
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we consider the problem of fitting Random Utility Models (RUMs) to user choices. Given the winner distributions of the subsets of size $k$ of a universe, we obtain a polynomial-time algorithm that finds the RUM that best approximates the given distribution on average. Our algorithm is based on a linear program that we solve using the ellipsoid method. Given that its corresponding separation oracle problem is NP-hard, we devise an approximate separation oracle that can be viewed as a generalization of the weighted feedback arc set problem to hypergraphs. Our theoretical result can also be made practical: we obtain a heuristic that is effective and scales to real-world datasets.
• Abstract（参考訳）: 本研究では,ランダムユーティリティモデル(rum)をユーザ選択に適合させる問題を考える。 宇宙のサイズ$k$のサブセットの勝者分布を考えると、多項式時間アルゴリズムは、与えられた分布を平均で最もよく近似する RUM を求める。 本アルゴリズムは,楕円型手法を用いて解く線形プログラムに基づいている。 対応する分離オラクル問題はNPハードであるため、重み付けされたフィードバック弧集合問題のハイパーグラフへの一般化とみなすことができる近似分離オラクルを考案する。 我々の理論結果は、実世界のデータセットに効果的でスケール可能なヒューリスティックな結果を得ることができる。

関連論文リスト

• Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
  一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。 ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-10-24T19:57:56Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Gaussian Amplitude Amplification for Quantum Pathfinding [0.0]
  逐次連結な二部グラフの幾何学に焦点をあて、ガウス分布によって記述可能な解空間を自然に生み出す。 本稿では,これらの分布を符号化したオラクルを用いて振幅増幅による最適経路を解く方法を示す。
  論文  参考訳（メタデータ） (2021-12-15T14:41:14Z)
• Clustering a Mixture of Gaussians with Unknown Covariance [4.821312633849745]
  最大極大推定に基づくMax-Cut整数プログラムを導出する。 最適な速度を得るが、2次サンプルサイズを必要とする効率的なスペクトルアルゴリズムを開発する。 我々は Max-Cut プログラムを$k$-means プログラムに一般化する。
  論文  参考訳（メタデータ） (2021-10-04T17:59:20Z)
• Local versions of sum-of-norms clustering [77.34726150561087]
  本手法はボールモデルにおいて任意に閉じた球を分離できることを示す。 我々は、不連結連結集合のクラスタリングで発生する誤差に定量的な有界性を証明した。
  論文  参考訳（メタデータ） (2021-09-20T14:45:29Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Efficient Discretizations of Optimal Transport [16.996068297291057]
  境界分布に対して与えられた点数で離散化を計算するアルゴリズムを提案する。 我々は近似の限界を証明し、幅広い問題について性能を実証する。
  論文  参考訳（メタデータ） (2021-02-16T04:31:52Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

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

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