論文の概要: Ranking Items from Discrete Ratings: The Cost of Unknown User Thresholds

• arxiv url: http://arxiv.org/abs/2510.01871v1
• Date: Thu, 02 Oct 2025 10:23:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:21.08955
• Title: Ranking Items from Discrete Ratings: The Cost of Unknown User Thresholds
• Title（参考訳）: 離散的評価から項目をランク付けする - 未知のユーザ閾値のコスト
• Authors: Oscar Villemaud, Suryanarayana Sankagiri, Matthias Grossglauser,
• Abstract要約: 粗い離散スケールのレーティングから、きめ細かい項目のランキングを復元できるかどうかを問う。 ほぼ完璧なランキングを達成するには、$Theta(n2)$ユーザと$Omega(n2)$クエリが必要です。 しきい値の多様性は、多くのユーザの粗いレーティングをきめ細かなランキングにマージするために必要ですが、しきい値が未知であれば、この多様性はコストがかかります。
• 参考スコア（独自算出の注目度）: 5.361620932483819
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ranking items is a central task in many information retrieval and recommender systems. User input for the ranking task often comes in the form of ratings on a coarse discrete scale. We ask whether it is possible to recover a fine-grained item ranking from such coarse-grained ratings. We model items as having scores and users as having thresholds; a user rates an item positively if the item's score exceeds the user's threshold. Although all users agree on the total item order, estimating that order is challenging when both the scores and the thresholds are latent. Under our model, any ranking method naturally partitions the $n$ items into bins; the bins are ordered, but the items inside each bin are still unordered. Users arrive sequentially, and every new user can be queried to refine the current ranking. We prove that achieving a near-perfect ranking, measured by Spearman distance, requires $\Theta(n^2)$ users (and therefore $\Omega(n^2)$ queries). This is significantly worse than the $O(n\log n)$ queries needed to rank from comparisons; the gap reflects the additional queries needed to identify the users who have the appropriate thresholds. Our bound also quantifies the impact of a mismatch between score and threshold distributions via a quadratic divergence factor. To show the tightness of our results, we provide a ranking algorithm whose query complexity matches our bound up to a logarithmic factor. Our work reveals a tension in online ranking: diversity in thresholds is necessary to merge coarse ratings from many users into a fine-grained ranking, but this diversity has a cost if the thresholds are a priori unknown.
• Abstract（参考訳）: ランキング項目は多くの情報検索およびレコメンデーションシステムにおいて中心的なタスクである。 ランキングタスクのユーザ入力は、粗い離散的なスケールで評価されることが多い。 このような粗い評価から、きめ細かい項目を復元できるかどうかを問う。 ユーザは、その項目のスコアがユーザのしきい値を超えた場合、その項目を肯定的に評価する。 すべてのユーザがアイテムの順序に同意するが、スコアとしきい値の両方が遅れている場合、その順序を推定することは困難である。 私たちのモデルでは、ランク付けメソッドは自然に$n$のアイテムをビンに分割します。 ユーザーは順次到着し、新しいユーザー全員に問い合わせて現在のランキングを改善できる。 スピアマン距離によって測定されたほぼ完全なランキングを達成するには、$\Theta(n^2)$ユーザが必要である(従って$\Omega(n^2)$クエリ)。 これは比較からランク付けするために必要な$O(n\log n)$クエリよりもはるかに悪い。 また,2次発散係数を用いて,スコア分布としきい値分布のミスマッチの影響を定量化する。 結果の厳密さを示すために,クエリの複雑さが対数係数に一致したランキングアルゴリズムを提案する。 しきい値の多様性は、多くのユーザの粗いレーティングをきめ細かなランキングにマージするために必要ですが、しきい値が未知であれば、この多様性はコストがかかります。

関連論文リスト

• Adaptively Learning to Select-Rank in Online Platforms [34.258659206323664]
  本研究は、異種ユーザの候補プールからアイテムを適応的にランク付けすることの課題に対処する。 本研究では,多様なユーザの好みや項目位置の影響を考慮に入れたユーザ応答モデルを構築した。 シミュレーションと実世界の両方のデータセットで実施された実験は、アルゴリズムがベースラインを上回っていることを示している。
  論文  参考訳（メタデータ） (2024-06-07T15:33:48Z)
• Found in the Middle: Permutation Self-Consistency Improves Listwise Ranking in Large Language Models [63.714662435555674]
  大規模言語モデル(LLM)は、文脈の使い方に位置バイアスを示す。 我々は,ブラックボックスLLMのランキングリスト出力に対して,自己整合性(permutation self-consistency)を提案する。 LLaMA v2 (70B) では GPT-3.5 では 7-18% , LLaMA v2 (70B) では 8-16% である。
  論文  参考訳（メタデータ） (2023-10-11T17:59:02Z)
• Replace Scoring with Arrangement: A Contextual Set-to-Arrangement Framework for Learning-to-Rank [40.81502990315285]
  ラーニング・トゥ・ランク(Learning-to-rank)は、トップNレコメンデーションタスクの中核的なテクニックであり、理想的なランク付けはアイテムからアレンジへのマッピングである。 既存のソリューションのほとんどは確率的ランキング原理(PRP)のパラダイムに該当する。すなわち、まず候補セットで各項目をスコアし、次にソート操作を行い、トップランキングリストを生成する。 本稿では,個別のスコアリングやソートを必要とせずに,候補項目の順列を直接生成する新しいフレームワークであるSet-To-Arrangement Ranking (STARank)を提案する。
  論文  参考訳（メタデータ） (2023-08-05T12:22:26Z)
• Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
  本稿では,二部類ランキングにおける公平性を実現するためのモデルに依存しない後処理フレームワークxOrderを提案する。 xOrderは、教師なしおよび教師なしの公正度メトリックを含む、さまざまな分類モデルとランキングフェアネスメトリクスと互換性がある。 提案アルゴリズムを,4つのベンチマークデータセットと2つの実世界の患者電子健康記録リポジトリ上で評価した。
  論文  参考訳（メタデータ） (2023-07-27T07:42:44Z)
• Online Learning of Optimally Diverse Rankings [63.62764375279861]
  ユーザのフィードバックのみに基づいて最適なリストを効率よく学習するアルゴリズムを提案する。 我々は、$T$クエリの後に、LDRの後悔は$O((N-L)log(T))$としてスケールする。
  論文  参考訳（メタデータ） (2021-09-13T12:13:20Z)
• User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets [28.537935838669423]
  ユーザフェアネス、アイテムフェアネス、多様性は根本的に異なる概念であることを示す。 3つのデシラタを明示的に強制する最初のランク付けアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-04T02:53:09Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  提案手法は,提案システムにおける暗黙的フィードバックの特性に対応するために,協調的ランキング(SeetRank)のためのセッティングワイドベイズ的手法を提案する。 具体的には、SetRankは、新しい設定された選好比較の後方確率を最大化することを目的としている。 また、SetRankの理論解析により、余剰リスクの境界が$sqrtM/N$に比例できることを示す。
  論文  参考訳（メタデータ） (2020-02-23T06:40:48Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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