論文の概要: HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property

• arxiv url: http://arxiv.org/abs/2401.00013v1
• Date: Thu, 21 Dec 2023 18:47:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-15 12:25:59.599438
• Title: HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property
• Title（参考訳）: hitsndiffs: 真理の発見から連続する性質を持つ行列の復元による能力発見へ
• Authors: Zixuan Chen, Subhodeep Mitra, R Ravi, Wolfgang Gatterbauer
• Abstract要約: 本研究では,あるユーザが質問(項目)をし,他のユーザが回答(ラベル)を返却するクラウドソース環境での一般的な問題を解析する。 我々はこの問題を「能力発見」と呼び、「真理発見」というよりよく研究された問題とのつながりと双対性を強調する。 実験の結果,我々の新しいHITSは,最先端の真理発見手法と比較して,精度の高いユーザランキングを生成することがわかった。
• 参考スコア（独自算出の注目度）: 11.332742187228524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze a general problem in a crowd-sourced setting where one user asks a question (also called item) and other users return answers (also called labels) for this question. Different from existing crowd sourcing work which focuses on finding the most appropriate label for the question (the "truth"), our problem is to determine a ranking of the users based on their ability to answer questions. We call this problem "ability discovery" to emphasize the connection to and duality with the more well-studied problem of "truth discovery". To model items and their labels in a principled way, we draw upon Item Response Theory (IRT) which is the widely accepted theory behind standardized tests such as SAT and GRE. We start from an idealized setting where the relative performance of users is consistent across items and better users choose better fitting labels for each item. We posit that a principled algorithmic solution to our more general problem should solve this ideal setting correctly and observe that the response matrices in this setting obey the Consecutive Ones Property (C1P). While C1P is well understood algorithmically with various discrete algorithms, we devise a novel variant of the HITS algorithm which we call "HITSNDIFFS" (or HND), and prove that it can recover the ideal C1P-permutation in case it exists. Unlike fast combinatorial algorithms for finding the consecutive ones permutation (if it exists), HND also returns an ordering when such a permutation does not exist. Thus it provides a principled heuristic for our problem that is guaranteed to return the correct answer in the ideal setting. Our experiments show that HND produces user rankings with robustly high accuracy compared to state-of-the-art truth discovery methods. We also show that our novel variant of HITS scales better in the number of users than ABH, the only prior spectral C1P reconstruction algorithm.
• Abstract（参考訳）: 本研究では,あるユーザが質問(項目)をし,他のユーザが回答(ラベル)を返却するクラウドソース環境での一般的な問題を解析する。 質問に対して最も適切なラベル("真実")を見つけることに焦点を当てた既存のクラウドソーシング作業とは違って、私たちの問題は、質問に答える能力に基づいてユーザのランキングを決定することです。 我々はこの問題を「能力発見」と呼び、よりよく研究された「真実発見」の問題と結びつきと双対性を強調する。 品目とそのラベルを原則的にモデル化するために,SAT や GRE といった標準化テストの背後にある広く受け入れられている理論である Item Response Theory (IRT) を導いた。 私たちはまず、ユーザの相対的なパフォーマンスがアイテム間で一貫性を持ち、より優れたユーザが各項目のラベルを適当に選択できるような、理想的な設定から始めます。 より一般的な問題のアルゴリズム的解法は、この理想的な設定を正しく解き、この設定の応答行列がC1P(Consecutive Ones Property)に従うことを観察するべきである。 C1Pはアルゴリズム的に様々な離散アルゴリズムでよく理解されているが、「HITSNDIFFS(HND)」と呼ばれるHITSアルゴリズムの新たな変種を考案し、もし存在する場合の理想的なC1P置換を復元できることを示す。 連続する順列を見つける高速組合せアルゴリズム(もし存在するなら)とは異なり、hndはそのような順列が存在しない場合も順序を返す。 したがって、理想的な設定で正しい答えを返すことが保証される我々の問題に対して原則的ヒューリスティックを提供する。 実験の結果,HNDは最先端の真理発見手法と比較して,高精度にユーザランキングを生成することがわかった。 また,従来のスペクトルC1P再構成アルゴリズムであるABHよりも,HITSの新規変種の方がユーザ数でよいことを示す。

関連論文リスト

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Dual-Directed Algorithm Design for Efficient Pure Exploration [9.728332815218181]
  有限組の代替品を用いた逐次適応実験の文脈における純粋探索問題を考える。 固定予算, 固定信頼度, 後収束率設定に対する最大最適化問題として問題複雑性尺度を定式化する。 我々のアルゴリズムは、$varepsilon$-best-armの識別(または、良好な選択保証の確率でランク付けと選択)としきい値の帯域幅で最適性を得る。
  論文  参考訳（メタデータ） (2023-10-30T07:29:17Z)
• Improved theoretical guarantee for rank aggregation via spectral method [1.0152838128195467]
  複数の項目間のペアワイズ比較を与えられた場合、ランキングが観測値と一致するようにランク付けする方法? ランクアグリゲーションとして知られるこの問題は、スポーツ、レコメンデーションシステム、その他のウェブアプリケーションに多くの応用を見出している。 ここで、各ペア比較は真のスコア差の破損したコピーである。
  論文  参考訳（メタデータ） (2023-09-07T16:01:47Z)
• Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach [10.293894471295205]
  本研究では、動的アソートによる選択に基づくフィードバックから学習する際のランク付けと選択の問題について検討する。 両学習目標に対して,新しい,シンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-13T05:05:30Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
  二次代入問題 (QAP) はNPハード問題に属する最適化問題である。 ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。 本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
  論文  参考訳（メタデータ） (2020-07-29T15:02:07Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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