論文の概要: 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の新規変種の方がユーザ数でよいことを示す。

関連論文リスト

• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  階層モデルに基づく選好文の一貫性問題の解法として,アルゴリズム的手法を構築し,比較する。 インスタンスが一貫すると、評価関数に階層的モデルが存在し、代替関数の順序関係を誘導する。 この問題を解決するための3つのアプローチを開発する。
  論文  参考訳（メタデータ） (2024-10-31T13:48:46Z)
• Improved theoretical guarantee for rank aggregation via spectral method [1.0152838128195467]
  複数の項目間のペアワイズ比較を与えられた場合、ランキングが観測値と一致するようにランク付けする方法? ランクアグリゲーションとして知られるこの問題は、スポーツ、レコメンデーションシステム、その他のウェブアプリケーションに多くの応用を見出している。 ここで、各ペア比較は真のスコア差の破損したコピーである。
  論文  参考訳（メタデータ） (2023-09-07T16:01:47Z)
• Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing [10.508187462682308]
  我々は,クラウドソーシングの課題を,基礎的真理だけでなく,最も紛らわしい回答と混乱確率の回復を目標として検討している。 本稿では,各タスクの上位2つの答えが,他の選択肢と区別されるモデルを提案する。 このモデルでは、上位2つの答えと混乱確率の両方を推測する2段階の推論アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-12-29T09:46:39Z)
• 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)
• 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)

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

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