論文の概要: Exact Paired-Permutation Testing for Structured Test Statistics
- arxiv url: http://arxiv.org/abs/2205.01416v1
- Date: Tue, 3 May 2022 11:00:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-04 20:09:03.204246
- Title: Exact Paired-Permutation Testing for Structured Test Statistics
- Title（参考訳）: 構造的テスト統計のための完全対置換テスト
- Authors: Ran Zmigrod, Tim Vieira, Ryan Cotterell
- Abstract要約: 構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
- 参考スコア（独自算出の注目度）: 67.71280539312536
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Significance testing -- especially the paired-permutation test -- has played
a vital role in developing NLP systems to provide confidence that the
difference in performance between two systems (i.e., the test statistic) is not
due to luck. However, practitioners rely on Monte Carlo approximation to
perform this test due to a lack of a suitable exact algorithm. In this paper,
we provide an efficient exact algorithm for the paired-permutation test for a
family of structured test statistics. Our algorithm runs in $\mathcal{O}(GN
(\log GN )(\log N ))$ time where $N$ is the dataset size and $G$ is the range
of the test statistic. We found that our exact algorithm was $10$x faster than
the Monte Carlo approximation with $20000$ samples on a common dataset.
- Abstract（参考訳）: 重要なテスト(特にペア置換テスト)は、NLPシステムの開発において重要な役割を担い、2つのシステムのパフォーマンスの違い(すなわち、テスト統計)が運のせいではないことを確信する。
しかし、実践者は適切な厳密なアルゴリズムが欠如しているため、このテストを実行するためにモンテカルロ近似に頼る。
本稿では,構造化テスト統計の族に対して,ペア置換テストのための効率的な厳密アルゴリズムを提案する。
我々のアルゴリズムは$\mathcal{O}(GN)(\log GN )(\log N ))$timeで実行され、$N$はデータセットのサイズ、$G$はテスト統計の範囲である。
われわれの正確なアルゴリズムはモンテカルロ近似より10ドル高速で、共通のデータセット上に20000ドルのサンプルがあることがわかった。
関連論文リスト
- The Limits of Assumption-free Tests for Algorithm Performance [6.7171902258864655]
与えられたモデリングタスクにおいてアルゴリズムはどの程度うまく機能し、どのアルゴリズムが最善を尽くすか?
一方、特定のトレーニングデータセットに対して$A$を実行して生成された特定の適合モデルが$n$であるのか?
論文 参考訳（メタデータ） (2024-02-12T03:19:30Z) - Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。
グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。
提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文 参考訳（メタデータ） (2024-02-08T14:43:56Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Adjusted chi-square test for degree-corrected block models [13.122543280692641]
次数補正ブロックモデル(DCSBM)の適合性テストを提案する。
単純な調整により、$d_i$ の調和平均が無限に成長する限り、統計は null の下で分布に収束する。
我々の分布結果は漸近的ではなく、明示的な定数を持ち、目標分布へのコルモゴロフ-スミルノフ距離の有限サンプル境界を与える。
論文 参考訳（メタデータ） (2020-12-30T05:20:59Z) - 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 Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Downsampling for Testing and Learning in Product Distributions [24.48103093661132]
未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。
ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。
本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
論文 参考訳（メタデータ） (2020-07-15T02:46:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。