論文の概要: Optimal level set estimation for non-parametric tournament and crowdsourcing problems
- arxiv url: http://arxiv.org/abs/2408.15356v1
- Date: Tue, 27 Aug 2024 18:28:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-29 18:02:17.277615
- Title: Optimal level set estimation for non-parametric tournament and crowdsourcing problems
- Title（参考訳）: 非パラメトリックトーナメントとクラウドソーシング問題の最適レベルセット推定
- Authors: Maximilian Graf, Alexandra Carpentier, Nicolas Verzelen,
- Abstract要約: クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
- 参考スコア（独自算出の注目度）: 49.75262185577198
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that both the experts and the questions can be ordered, namely that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. When $n=d$, this also encompasses the strongly stochastic transitive (SST) model from the tournament literature. Here, we focus on the relevant problem of deciphering small entries of $M$ from large entries of $M$, which is key in crowdsourcing for efficient allocation of workers to questions. More precisely, we aim at recovering a (or several) level set $p$ of the matrix up to a precision $h$, namely recovering resp. the sets of positions $(i,j)$ in $M$ such that $M_{ij}>p+h$ and $M_{i,j}<p-h$. We consider, as a loss measure, the number of misclassified entries. As our main result, we construct an efficient polynomial-time algorithm that turns out to be minimax optimal for this classification problem. This heavily contrasts with existing literature in the SST model where, for the stronger reconstruction loss, statistical-computational gaps have been conjectured. More generally, this shades light on the nature of statistical-computational gaps for permutations models.
- Abstract（参考訳）: クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家と質問の両方を順序付けできる、すなわち、専門家$i$が質問に対して正しく答える確率を含む行列$M$が、行と列の置換までのバイソトニックであると仮定する。
n=d$の場合、トーナメント文献からの強確率推移(SST)モデルも含む。
ここでは、質問に対する労働者の効率的な配分のためのクラウドソーシングにおいて重要な、M$の大規模なエントリからM$の小さなエントリを解読する、関連する問題に焦点を当てる。
より正確には、行列の(あるいは複数の)レベルセット$p$を精度$h$まで回復すること、すなわちrespを回復することを目指している。
M_{ij}>p+h$ と $M_{i,j}<p-h$ の位置の集合。
損失指標として、誤分類されたエントリの数を考慮する。
本研究の主目的として,この分類問題に対して最小限の多項式時間アルゴリズムを構築した。
これは、SSTモデルにおける既存の文献と大きく対照的であり、より強い再構成損失のため、統計計算のギャップが推測されている。
より一般に、これは置換モデルに対する統計計算的ギャップの性質に光を当てる。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
論文 参考訳（メタデータ） (2023-05-08T17:46:01Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。
幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。
我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
論文 参考訳（メタデータ） (2022-02-07T14:43:35Z) - Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。
シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
論文 参考訳（メタデータ） (2021-10-15T09:27:50Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳（メタデータ） (2021-06-08T23:38:29Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Optimal estimation of sparse topic models [3.308743964406688]
本稿では、要素的にスパースである可能性のある$A$の推定について検討し、$K$のトピックの数は不明である。
我々は、そのような$A$を推定するための新しいミニマックスローバウンドを導出し、そのリカバリのための新しい計算効率の良いアルゴリズムを提案する。
我々の推定値は、未知の$A$に適応し、我々の分析は、任意の有限$n$、$p$、$K$および文書長に対して有効である。
論文 参考訳（メタデータ） (2020-01-22T03:19:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。