論文の概要: Adjusted chi-square test for degree-corrected block models
- arxiv url: http://arxiv.org/abs/2012.15047v1
- Date: Wed, 30 Dec 2020 05:20:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 05:55:57.490893
- Title: Adjusted chi-square test for degree-corrected block models
- Title（参考訳）: 次数補正ブロックモデルに対する調整型チ二乗試験
- Authors: Linfan Zhang and Arash A. Amini
- Abstract要約: 次数補正ブロックモデル(DCSBM)の適合性テストを提案する。
単純な調整により、$d_i$ の調和平均が無限に成長する限り、統計は null の下で分布に収束する。
我々の分布結果は漸近的ではなく、明示的な定数を持ち、目標分布へのコルモゴロフ-スミルノフ距離の有限サンプル境界を与える。
- 参考スコア（独自算出の注目度）: 13.122543280692641
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a goodness-of-fit test for degree-corrected stochastic block
models (DCSBM). The test is based on an adjusted chi-square statistic for
measuring equality of means among groups of $n$ multinomial distributions with
$d_1,\dots,d_n$ observations. In the context of network models, the number of
multinomials, $n$, grows much faster than the number of observations, $d_i$,
hence the setting deviates from classical asymptotics. We show that a simple
adjustment allows the statistic to converge in distribution, under null, as
long as the harmonic mean of $\{d_i\}$ grows to infinity. This result applies
to large sparse networks where the role of $d_i$ is played by the degree of
node $i$. Our distributional results are nonasymptotic, with explicit
constants, providing finite-sample bounds on the Kolmogorov-Smirnov distance to
the target distribution. When applied sequentially, the test can also be used
to determine the number of communities. The test operates on a (row) compressed
version of the adjacency matrix, conditional on the degrees, and as a result is
highly scalable to large sparse networks. We incorporate a novel idea of
compressing the columns based on a $(K+1)$-community assignment when testing
for $K$ communities. This approach increases the power in sequential
applications without sacrificing computational efficiency, and we prove its
consistency in recovering the number of communities. Since the test statistic
does not rely on a specific alternative, its utility goes beyond sequential
testing and can be used to simultaneously test against a wide range of
alternatives outside the DCSBM family. We show the effectiveness of the
approach by extensive numerical experiments with simulated and real data. In
particular, applying the test to the Facebook-100 dataset, we find that a DCSBM
with a small number of communities is far from a good fit in almost all cases.
- Abstract（参考訳）: 次数補正確率ブロックモデル(DCSBM)の適合性試験を提案する。
このテストは、d_1,\dots,d_n$観測値を持つ多項分布群間の平均値の等式を測定する調整されたチ二乗統計に基づく。
ネットワークモデルの文脈では、$n$という多重項の数は、観測値の$d_i$よりもはるかに速く成長するので、設定は古典的な漸近から逸脱する。
単純な調整は、$\{d_i\}$の調和平均が無限大に大きくなる限り、統計学が分布に収束することを示す。
この結果は、$d_i$の役割をノード$i$の度合いで果たすような大きなスパースネットワークに適用できる。
我々の分布結果は漸近的ではなく、明示的な定数を持ち、目標分布へのコルモゴロフ-スミルノフ距離の有限サンプル境界を与える。
順次適用した場合、テストはコミュニティの数を決定するためにも使用できる。
テストはadjacency matrixの(row)圧縮バージョンで動作し、次数で条件付けされ、その結果、大きなスパースネットワークに対して高度にスケーラブルである。
我々は、$K$コミュニティのテスト時に$(K+1)$-communityの割り当てに基づいて列を圧縮するという新しいアイデアを取り入れた。
この手法は, 計算効率を犠牲にすることなく, 逐次的応用のパワーを増大させ, コミュニティ数回復における一貫性を実証する。
テスト統計は特定の代替品に依存しないため、そのユーティリティはシーケンシャルなテストを超えて、dcsbmファミリー以外の幅広い代替品に対して同時にテストすることができる。
シミュレーションおよび実データを用いた大規模数値実験によるアプローチの有効性を示す。
特に、Facebook-100データセットにテストを適用すると、少数のコミュニティを持つDCSBMは、ほぼすべてのケースに適していないことが分かりました。
関連論文リスト
- Doubly Robust Conditional Independence Testing with Generative Neural Networks [8.323172773256449]
本稿では、第3の確率ベクトル$Z$を与えられた2つのジェネリックランダムベクトル$X$と$Y$の条件独立性をテストする問題に対処する。
条件分布を明示的に推定しない新しい非パラメトリック試験法を提案する。
論文 参考訳（メタデータ） (2024-07-25T01:28:59Z) - 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) - A Permutation-free Kernel Two-Sample Test [36.50719125230106]
サンプル分割と学生化に基づく2次時間MDDテスト統計法を提案する。
大きなサンプルサイズの場合、我々の新しいクロスMMDはMDDよりも大幅にスピードアップし、わずかに電力を消費するだけである。
論文 参考訳（メタデータ） (2022-11-27T18:15:52Z) - The Projected Covariance Measure for assumption-lean variable significance testing [3.8936058127056357]
単純だが一般的なアプローチは、線形モデルを指定し、次に$X$の回帰係数が 0 でないかどうかをテストすることである。
条件付き平均独立性のモデルフリーなnullをテストする問題、すなわち条件付き平均の$Y$$$X$と$Z$は$X$に依存しない。
本稿では,加法モデルやランダムフォレストなど,柔軟な非パラメトリックあるいは機械学習手法を活用可能な,シンプルで汎用的なフレームワークを提案する。
論文 参考訳（メタデータ） (2022-11-03T17:55:50Z) - Efficient Aggregated Kernel Tests using Incomplete $U$-statistics [22.251118308736327]
提案した3つのテストは、複数のカーネル帯域に集約され、さまざまなスケールでnullからの離脱を検出する。
提案した線形時間集約テストは,現在最先端の線形時間カーネルテストよりも高い出力が得られることを示す。
論文 参考訳（メタデータ） (2022-06-18T12:30:06Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Dimension-agnostic inference using cross U-statistics [33.17951971728784]
本稿では,サンプル分割と自己正規化とともに,既存のテスト統計の変分表現を用いた手法を提案する。
結果の統計学は、縮退したU統計を慎重に修正し、対角ブロックを落とし、対角ブロックを外したままにすると見なすことができる。
論文 参考訳（メタデータ） (2020-11-10T12:21:34Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Noisy Adaptive Group Testing using Bayesian Sequential Experimental
Design [63.48989885374238]
病気の感染頻度が低い場合、Dorfman氏は80年前に、人のテストグループは個人でテストするよりも効率が良いことを示した。
本研究の目的は,ノイズの多い環境で動作可能な新しいグループテストアルゴリズムを提案することである。
論文 参考訳（メタデータ） (2020-04-26T23:41:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。