論文の概要: Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm

• arxiv url: http://arxiv.org/abs/2001.11775v2
• Date: Fri, 30 Apr 2021 05:39:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-05 06:21:37.246436
• Title: Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm
• Title（参考訳）: XORクエリによるバイナリ分類:基本限界と効率的なアルゴリズム
• Authors: Daesung Kim and Hye Won Chung
• Abstract要約: 未知ラベルのバイナリ分類のための問合せに基づくデータ取得問題を考える。 我々は、選択したオブジェクトのサブセットの「グループ属性」を問う効果的なクエリタイプを考える。 雑音パラメータが未知であっても,この制限を実現する効率的な推論アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 15.127728811011245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a query-based data acquisition problem for binary classification of unknown labels, which has diverse applications in communications, crowdsourcing, recommender systems and active learning. To ensure reliable recovery of unknown labels with as few number of queries as possible, we consider an effective query type that asks "group attribute" of a chosen subset of objects. In particular, we consider the problem of classifying $m$ binary labels with XOR queries that ask whether the number of objects having a given attribute in the chosen subset of size $d$ is even or odd. The subset size $d$, which we call query degree, can be varying over queries. We consider a general noise model where the accuracy of answers on queries changes depending both on the worker (the data provider) and query degree $d$. For this general model, we characterize the information-theoretic limit on the optimal number of queries to reliably recover $m$ labels in terms of a given combination of degree-$d$ queries and noise parameters. Further, we propose an efficient inference algorithm that achieves this limit even when the noise parameters are unknown.
• Abstract（参考訳）: 情報通信,クラウドソーシング,レコメンダシステム,アクティブラーニングに多様な応用がある未知ラベルのバイナリ分類のためのクエリベースのデータ取得問題を考える。 クエリ数が極力少ない未知のラベルの信頼できるリカバリを確保するため、選択したオブジェクトのサブセットの"グループ属性"を求める効果的なクエリタイプを検討します。 特に、$m$バイナリラベルをxorクエリで分類する問題は、$d$が選択されたサブセット内の特定の属性を持つオブジェクトの数が偶数か奇数かを問うものである。 クエリの程度と呼ぶ$d$のサブセットサイズは、クエリによって異なります。 一般的なノイズモデルでは、クエリに対する答えの精度は、ワーカー(データプロバイダ)とクエリ度$d$の両方によって変化する。 この一般的なモデルでは、最適クエリ数に対する情報理論の限界を特徴付け、次数-d$クエリとノイズパラメータの組み合わせによって$m$ラベルを確実に復元する。 さらに,ノイズパラメータが未知であっても,この制限を実現する効率的な推論アルゴリズムを提案する。

関連論文リスト

• Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
  我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。 限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
  論文  参考訳（メタデータ） (2024-02-16T22:17:01Z)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  本稿では,知識グラフにエッジを欠いた複雑な論理的クエリに応答するクエリ埋め込み手法を提案する。 回答エンティティは、エンティティの埋め込みとクエリの埋め込みの類似性に応じて選択される。 埋め込み空間上の様々な領域から多様な回答を検索するために,複雑なKGクエリ応答方法Q2Pを提案する。
  論文  参考訳（メタデータ） (2022-04-27T11:16:08Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。 提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
  論文  参考訳（メタデータ） (2022-02-22T01:34:35Z)
• Active clustering for labeling training data [0.8029049649310211]
  本稿では,人間専門家がペアワイズクエリに応答する比較的安価なタスクを実行するための,データ収集のトレーニング環境を提案する。 我々は、アイテムをクラスタリングし、その複雑さを分析するのに必要なクエリの平均数を最小化するアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2021-10-27T15:35:58Z)
• How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
  機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。 本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。 さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
  論文  参考訳（メタデータ） (2021-10-05T20:15:35Z)
• Online Learning of Optimally Diverse Rankings [63.62764375279861]
  ユーザのフィードバックのみに基づいて最適なリストを効率よく学習するアルゴリズムを提案する。 我々は、$T$クエリの後に、LDRの後悔は$O((N-L)log(T))$としてスケールする。
  論文  参考訳（メタデータ） (2021-09-13T12:13:20Z)
• Active Covering [37.525977525895605]
  我々は,学習者がラベルのないデータセットを与えられ,クエリの事例を逐次ラベル付けできる,アクティブカバーの問題を分析する。 目的は,最少数のラベルクエリにおいて,肯定的な例をすべてラベル付けすることである。
  論文  参考訳（メタデータ） (2021-06-04T15:32:39Z)
• Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings [84.0206612938464]
  query2boxは、不完全な知識グラフ上の任意のクエリを推論するための埋め込みベースのフレームワークである。 query2boxは、スケーラブルな方法で$wedge$, $vee$, $exists$で任意の論理クエリを処理可能であることを示す。 本稿では,3つの大規模KGに対するQuery2boxの有効性を示すとともに,クエリ2boxが技術状況に対して最大25%の相対的な改善を達成可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-14T11:20:10Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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