論文の概要: Optimal Clustering from Noisy Binary Feedback

• arxiv url: http://arxiv.org/abs/1910.06002v4
• Date: Mon, 5 Feb 2024 05:07:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-07 21:51:13.464496
• Title: Optimal Clustering from Noisy Binary Feedback
• Title（参考訳）: 雑音二元フィードバックからの最適クラスタリング
• Authors: Kaito Ariu, Jungseul Ok, Alexandre Proutiere, Se-Young Yun
• Abstract要約: 本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 75.17453757892152
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of clustering a set of items from binary user feedback. Such a problem arises in crowdsourcing platforms solving large-scale labeling tasks with minimal effort put on the users. For example, in some of the recent reCAPTCHA systems, users clicks (binary answers) can be used to efficiently label images. In our inference problem, items are grouped into initially unknown non-overlapping clusters. To recover these clusters, the learner sequentially presents to users a finite list of items together with a question with a binary answer selected from a fixed finite set. For each of these items, the user provides a noisy answer whose expectation is determined by the item cluster and the question and by an item-specific parameter characterizing the {\it hardness} of classifying the item. The objective is to devise an algorithm with a minimal cluster recovery error rate. We derive problem-specific information-theoretical lower bounds on the error rate satisfied by any algorithm, for both uniform and adaptive (list, question) selection strategies. For uniform selection, we present a simple algorithm built upon the K-means algorithm and whose performance almost matches the fundamental limits. For adaptive selection, we develop an adaptive algorithm that is inspired by the derivation of the information-theoretical error lower bounds, and in turn allocates the budget in an efficient way. The algorithm learns to select items hard to cluster and relevant questions more often. We compare the performance of our algorithms with or without the adaptive selection strategy numerically and illustrate the gain achieved by being adaptive.
• Abstract（参考訳）: 本研究では,アイテム群をバイナリユーザフィードバックからクラスタリングする問題について検討する。 このような問題はクラウドソーシングプラットフォームにおいて、ユーザに対して最小限の労力で大規模ラベリングタスクを解決するために発生する。 例えば、最近のreCAPTCHAシステムでは、画像を効率的にラベル付けするためにユーザーがクリック(バイナリ回答)することができる。 我々の推論問題では、アイテムは最初未知の非重複クラスタにグループ化される。 これらのクラスタを回復するために、学習者は、一定有限集合から選択された二項解の質問とともに、有限個の項目のリストをユーザに順次提示する。 これら各項目について、ユーザは、アイテムクラスタと質問によって予測が決定され、アイテムを分類する「it hardness」を特徴付けるアイテム固有のパラメータによってノイズの多い回答を提供する。 目的は、最小のクラスタリカバリエラーレートでアルゴリズムを考案することである。 我々は,任意のアルゴリズムが満たす誤り率に関する問題固有情報理論の下限を,一様および適応的(リスト,質問)選択戦略として導出する。 均一な選択のために、K平均アルゴリズム上に構築された単純なアルゴリズムを示し、その性能は基本的限界にほぼ一致する。 適応的選択のために,情報理論的誤差の下限の導出にインスパイアされた適応アルゴリズムを開発し,その結果,予算を効率的に配分する。 アルゴリズムは、クラスタ化が難しい項目と関連する質問をより頻繁に選択することを学ぶ。 我々は,アルゴリズムの性能を適応的選択戦略の有無を数値的に比較し,適応性によって得られる利益を例示する。

関連論文リスト

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
  インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。 既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。 本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
  論文  参考訳（メタデータ） (2024-06-06T04:05:54Z)
• From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection [12.993073967843292]
  我々は,未知の地下構造クラスタリングを用いて,半教師付き環境で問題を研究する。 本稿では,クラスタリングアルゴリズムの精度向上のためのサイズ一般化の概念を提案する。 データセット全体においてどのアルゴリズムが最適かを特定するために、データの5%をサブサンプルとして使用しています。
  論文  参考訳（メタデータ） (2024-02-22T06:53:35Z)
• Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms [17.57585822765145]
  本稿では,小データセットに適した正確なアルゴリズムと,大データセットにスケールする任意の$varepsilon in (0, 1)$に対して$frac1-varepsilon integer 5$-approximationアルゴリズムを提案する。 実世界のデータセットに対する実験は、提案アルゴリズムが既存のデータセットよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-05T13:02:35Z)
• Ensemble Method for Cluster Number Determination and Algorithm Selection in Unsupervised Learning [0.0]
  教師なしの学習は、現場で使われる専門知識の必要性に悩まされる。 最小限の入力で活用できるアンサンブルクラスタリングフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-23T04:59:10Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Certifiably Polynomial Algorithm for Best Group Subset Selection [0.9667631210393929]
  ベストグループサブセットの選択は、応答変数の最良の解釈可能性を達成するために重複しないグループの小さな部分を選択することを目的としている。 有効群を反復的に検出し,無力群を除外するグループスプライシングアルゴリズムを提案する。 提案手法の効率と精度を,合成データセットと実世界のデータセットを比較して検証する。
  論文  参考訳（メタデータ） (2021-04-23T03:05:11Z)
• Clustering with Penalty for Joint Occurrence of Objects: Computational Aspects [0.0]
  Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。 この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。 本稿では,本手法の計算的側面について考察する。
  論文  参考訳（メタデータ） (2021-02-02T10:39:27Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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