論文の概要: Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion

• arxiv url: http://arxiv.org/abs/2010.12181v1
• Date: Fri, 23 Oct 2020 06:23:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-03 23:37:01.905871
• Title: Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
• Title（参考訳）: ロバストなランク1行列完全化による逆クラウドソーシング
• Authors: Qianqian Ma and Alex Olshevsky
• Abstract要約: 明らかな記載が損なわれているかは分かっていない。 提案アルゴリズムは,ErdHos-R'enyiランダムグラフを用いて,抽出されたエントリの集合が与えられたときに最適であることを示す。 特に, 提案アルゴリズムは, ErdHos-R'enyiランダムグラフを用いて, 与えられたエントリの集合が与えられたときに最適であることを示す。
• 参考スコア（独自算出の注目度）: 17.615174152419133
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of reconstructing a rank-one matrix from a revealed subset of its entries when some of the revealed entries are corrupted with perturbations that are unknown and can be arbitrarily large. It is not known which revealed entries are corrupted. We propose a new algorithm combining alternating minimization with extreme-value filtering and provide sufficient and necessary conditions to recover the original rank-one matrix. In particular, we show that our proposed algorithm is optimal when the set of revealed entries is given by an Erd\H{o}s-R\'enyi random graph. These results are then applied to the problem of classification from crowdsourced data under the assumption that while the majority of the workers are governed by the standard single-coin David-Skene model (i.e., they output the correct answer with a certain probability), some of the workers can deviate arbitrarily from this model. In particular, the "adversarial" workers could even make decisions designed to make the algorithm output an incorrect answer. Extensive experimental results show our algorithm for this problem, based on rank-one matrix completion with perturbations, outperforms all other state-of-the-art methods in such an adversarial scenario.
• Abstract（参考訳）: 明らかにされたエントリのサブセットからランク 1 のマトリックスを再構築する問題は、明らかにされたエントリのいくつかが、未知で任意に大きい摂動で腐敗しているときに問題となる。 明らかな記載が損なわれるかは不明である。 本稿では,交互最小化と極値フィルタリングを組み合わせた新しいアルゴリズムを提案する。 特に,提案アルゴリズムは,Erd\H{o}s-R\'enyiランダムグラフの集合が与えられたときに最適であることを示す。 これらの結果は、労働者の大多数が標準のシングルコインDavid-Skeneモデル(すなわち、ある確率で正しい回答を出力する)によって支配されているが、一部の労働者はこのモデルから任意に逸脱できるという仮定の下で、クラウドソースデータから分類する問題に適用される。 特に「敵対的」な労働者は、アルゴリズムが誤った答えを出力するように設計された決定を下すこともできる。 広汎な実験結果から, 摂動を伴うランクワン行列の完備化に基づくこの問題に対するアルゴリズムは, 対角的シナリオにおいて, その他の最先端手法よりも優れていた。

関連論文リスト

• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions [6.537257913467247]
  低ランク行列の完備化は、与えられた観測セットをできるだけ正確に回復する最小の複雑さの行列からなる。 新たな凸緩和は、既存の方法に比べて最大値を大幅に下げる。
  論文  参考訳（メタデータ） (2023-05-20T22:04:34Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。 まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。 次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
  論文  参考訳（メタデータ） (2022-10-03T00:28:44Z)
• Partial Matrix Completion [29.68420094716923]
  この研究は、部分行列完備化の新しい枠組みを確立する。 目標は、高い信頼性で完成できるエントリの大規模なサブセットを特定することである。 本稿では,以下の証明可能な保証付き効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-25T12:47:20Z)
• Matrix Completion with Sparse Noisy Rows [3.42658286826597]
  非退化雑音モデル下での高精度な低ランク化について検討する。 本稿では,各行が列の代わりにランダムノイズを受けることができると仮定する。
  論文  参考訳（メタデータ） (2022-04-01T05:45:43Z)
• Causal Matrix Completion [15.599296461516984]
  マトリックス完備化(Matrix completion)は、ノイズ観測のスパース部分集合から基礎となる行列を復元する研究である。 伝統的に、行列の成分は「ランダムに完全に欠落している」と仮定される。
  論文  参考訳（メタデータ） (2021-09-30T14:17:56Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion [2.0257616108612373]
  部分的な問題としてラッソを含む行列圧縮センシングと行列補完を扱う。 本稿では,ハマー損失関数と核ノルムのペナル化を組み合わせた単純な統一手法を提案する。
  論文  参考訳（メタデータ） (2020-10-25T02:32:07Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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