論文の概要: Learning-to-Rank with Partitioned Preference: Fast Estimation for the
Plackett-Luce Model
- arxiv url: http://arxiv.org/abs/2006.05067v3
- Date: Fri, 26 Feb 2021 00:58:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-23 13:43:04.752484
- Title: Learning-to-Rank with Partitioned Preference: Fast Estimation for the
Plackett-Luce Model
- Title(参考訳): 分割選好による学習と学習:プラケット・ルーシモデルの高速推定
- Authors: Jiaqi Ma, Xinyang Yi, Weijing Tang, Zhe Zhao, Lichan Hong, Ed H. Chi,
Qiaozhu Mei
- Abstract要約: M$パーティションを持つ$N$アイテムが与えられた場合、PLモデルの下でパーティショニングされた好みを持つデータの確率を計算すると、時間複雑性は$O(N+S!)$である。
時間複雑性$O(N+S3)$で確率とその勾配を計算するための効率的な数値積分法を提案する。
- 参考スコア(独自算出の注目度): 24.923231199480433
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the Plackett-Luce (PL) model based listwise learning-to-rank
(LTR) on data with partitioned preference, where a set of items are sliced into
ordered and disjoint partitions, but the ranking of items within a partition is
unknown. Given $N$ items with $M$ partitions, calculating the likelihood of
data with partitioned preference under the PL model has a time complexity of
$O(N+S!)$, where $S$ is the maximum size of the top $M-1$ partitions. This
computational challenge restrains most existing PL-based listwise LTR methods
to a special case of partitioned preference, top-$K$ ranking, where the exact
order of the top $K$ items is known. In this paper, we exploit a random utility
model formulation of the PL model, and propose an efficient numerical
integration approach for calculating the likelihood and its gradients with a
time complexity $O(N+S^3)$. We demonstrate that the proposed method outperforms
well-known LTR baselines and remains scalable through both simulation
experiments and applications to real-world eXtreme Multi-Label classification
tasks.
- Abstract(参考訳): 分割された選好を持つデータについて,placett-luce (pl)モデルに基づくlistwise learning-to-rank (ltr) について検討する。
m$パーティションを持つ$n$アイテムが与えられると、plモデルの下で分割されたプライバシを持つデータの可能性を計算すると、$o(n+s!)$という時間の複雑さがあり、$s$は最上位の$m-1$パーティションの最大サイズである。
この計算課題は、PLベースのリストワイズ LTR メソッドの大半を分割された選好の特別な場合、トップ$K$ランキング、トップ$K$アイテムの正確な順序が知られている場合に制限する。
本稿ではPLモデルのランダムなユーティリティモデル定式化を活用し、時間複雑性$O(N+S^3)$で確率とその勾配を計算するための効率的な数値積分手法を提案する。
提案手法はよく知られたLTRベースラインよりも優れており,実世界のeXtreme Multi-Label分類タスクへのシミュレーション実験と応用の両方を通して,スケーラブルであることを示す。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Ranking Inferences Based on the Top Choice of Multiway Comparisons [2.468314282946207]
本稿では、各試行においてランダムに選択された項目のうち、上位選択の観測データに基づいて、$n$アイテムのランキングを考察する。
これは、M$-wayランキングに対するプラケット=リュックモデルの有用な修正であり、最高選択のみを観測し、M=2$に対応する祝賀されたブラッドリー=テリー=リュックモデルの延長である。
論文 参考訳(メタデータ) (2022-11-22T02:34:52Z) - You can't pick your neighbors, or can you? When and how to rely on
retrieval in the $k$NN-LM [65.74934004876914]
Retrieval-enhanced Language Model (LM) は、大規模な外部データストアから取得したテキストにそれらの予測を条件付ける。
そのようなアプローチの1つ、$k$NN-LMは、既存のLMの予測を$k$-nearest近くのモデルの出力と補間する。
本研究では,2つの英語モデルデータセットに対するアプローチの有効性を実証的に測定する。
論文 参考訳(メタデータ) (2022-10-28T02:57:40Z) - Efficient and Accurate Top-$K$ Recovery from Choice Data [1.14219428942199]
レコメンデーションシステムのようないくつかのアプリケーションでは、統計学者は主に大量のアイテムから上位のアイテムの集合を回収することに興味がある。
そこで本稿では,K$-recoveryの高速かつ高精度なランキングアルゴリズムとして,選択に基づくボルダカウントアルゴリズムを提案する。
選択に基づくボルダカウントアルゴリズムは,多種多様なランダム効用モデルの下で,上位$Kの回収に最適なサンプル複雑性を有することを示す。
論文 参考訳(メタデータ) (2022-06-23T22:05:08Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳(メタデータ) (2022-06-14T08:14:14Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳(メタデータ) (2021-04-06T20:25:57Z) - Sampling from a $k$-DPP without looking at all items [58.30573872035083]
カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。
既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。
そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2020-06-30T16:40:44Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳(メタデータ) (2020-02-22T01:03:33Z) - Best-item Learning in Random Utility Models with Subset Choices [40.17224226373741]
我々は、$k$アイテムのサブセットの逐次的かつ適応的に選択されたプレイを用いて、$n$アイテムのプールから最も価値のあるアイテムをPACで学習する問題を考察する。
そのようなRUMの新たな性質を最小限の利点と呼び、アイテムのペアを分離する複雑さを特徴づけるのに役立つ。
一般RUMの学習アルゴリズムとして,アイテムの相対的な数と階層的除去と,新しいPACサンプルの複雑性保証を併用した学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-19T03:57:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。