[Two sample test][Graph] Collaborative non-parametric two-sample testing(by Alejandro de la Concha, Nicolas Vayatis, Argyris Kalogeratos)

https://arxiv.org/abs/2402.05715

Collaborative non-parametric two-sample testing

Abstract 

Graph 구조에서의 multiple two sample test에 관해서 다룬다. 

두 표본 검정(Two-Sample Test, TST): In statistical hypothesis testing, a two-sample test is a test performed on the data of two random samples, each independently obtained from a different given population. The purpose of the test is to determine whether the difference between these two populations is statistically significant(출처: wiki)
즉 독립된 A, B 집단에서 추출한 데이터 a,b 들이 서로 통계적으로 유의미한 차이를 보이는지 검정. 사전에 이미 구분된 집단 A,B가 존재

Multiple Two-Sample Tests:
 conducting several two-sample tests simultaneously(동시에) to compare more than two groups or to make
 multiple comparisons
 within a dataset. When you have more than two groups to compare, or when you want to perform multiple comparisons (e.g., comparing each group to a control group or comparing all pairs of groups), you need methods that adjust for the increased risk of Type I errors(H0가 참인데도 기각하는 시나리어) due to multiple testing. 

 

이는 Spatial Statistics(공간 통계) 및 신경과학에서 흔히 사용하는 시나리오로, 고정된 그래프의 각 노드 v에 관해 노드별 pdf, pv와 qv간의 Two sample Test(TST)를 처리한다. 이는 연결된 노드가 유사한 테스트 결과(statistical test, 즉 비슷한 통계적 특성을 지님)를 가질 것이라는 가정하에 귀무가설 pv = qv를 기각하는 노드를 구별하는 것이다. 

노드 하나당 하나의 값이 아니라, 각 노드에 데이터 세트가 연결되어 있다고 생각하시면 이해하기 쉬움.
노드와 데이터: 이 논문에서 각 노드 는 단순히 하나의 값을 나타내는 것이 아니라, 특정 위치나 개체에서 수집된 데이터 세트를 나타냄

 

 논문에서는 그래프 구조를 효율적으로 활용하고 pv와 qv에 대한 가정을 최소화하는 non-parametric collaborative two-sample testing (CTST)을 제안한다. ϕ-divergence estimation, Kernel Methods, and Multitask Learning을 통합한 방법론이다. 이후 논문에서는 합성 데이터에 관한 실험과 지진 활동을 감지하는 실제 센서 네트워크를 사용하여 CTST가 각 노드에서 독립적으로 적용되고 그래프의 기하학적  무시하는 기존 비모수 통계 테스트보다 우수하다는 것을 보인다. 

기존의 통계적 방법들은 각 노드를 독립적으로 취급하여, 노드 간의 연결성이나 공간적 관계를 고려하지 않았음

 

Introduction 

두개의 확률밀도함수(pdf) p와 q에 관하여 Two-sample Test(TST)는 H0: p=q가 참인지 아닌지에 대한 significant evidence가 있는지 확인한다. TST는 Machine learning 분야에서 상세히 연구되어 여러 방법들이 제안되었다(Sugiyama et al., 2011b; Gretton et al., 2012; Har-chaoui et al., 2013; Lopez-Paz & Oquab, 2017; Bargiotas et al., 2021)). 대부분의 통계문제들과 같이, 전형적인 univariate 설정에서 다변량으로 확장하는 것은 쉽지 않은 문제이다. 이는 여러 두 샘플 테스트를 수행하는 것이 귀무가설을 잘 못 기각할 확률(False postive, Type 1 error)이 테스트 횟수에 따라 증가하게 되는 Multiple Comparison Problem (MCP)에 직면하기 때문이다.  

MCP에 관한 기존의 처리 방법들으 테스트 되는 가설 수 N에 따라  p-value(π-value) 값을 조정하는 본페로니 보정(Dunn, 1961)이나 Maximum Statistic 및 순열 검정을 사용하는 비모수 resampling 테스트(Westfall & Young, 1992) 등이 있.

.Maximum Statistic: Maximum statistic은 여러 개의 통계량 중에서 가장 큰 값을 선택한 것입니다. 예를 들어, 여러 그룹 간의 평균 차이를 비교할 때, 각 그룹 간의 t-통계량을 계산하고 이 중에서 가장 큰 값을 maximum statistic으로 사용할 수 있습니다

Permutation Test (순열 검정): 관측된 데이터를 재배열하여 실제 관찰된 효과가 무작위 분포에 비해 얼마나 차이나는지 확인하는 방법 자세한 내용은 https://angeloyeo.github.io/2021/10/28/permutation_test.html 확인

 

다중 두 샘플 테스트(MTST) 문제는 공간 통계학, 신경과학, 복잡계 등의 분야에서 나타나며,  이러한 맥락에서 각 테스트는 서로 다른 "위치"에서 샘플링된 데이터와 연관되어 있으며, 귀무 가설의 유효성은 종종 이러한 위치 간의 "근접성"에 따라 달라진다. 예를 들어, 함께 발화하는 뉴런들이 함께 연결된다는 헤비안 관점은 신경과학에서 일반적인 기준이며, "모든 것은 서로 관련이 있지만, 가까운 것은 먼 것보다 더 많이 관련되어 있다"는 토플러의 첫 번째 지리 법칙은 공간 통계학에서 중요한 이론이다. 

 

Multiple two-sample testing on graph

위에서 언급한 응용분야에서의 여러 필요성에 힘입어, 본 논문은 주어진 고정된 그래프 G의  각 노드 v ∈ V = {1, ..., N }에 관한 TST를 연구한다. 즉, 각 노드는 도드별로 pdf p와 q를 비교한다. 그런 다음 모든 N 개의 가설들이 동시에 확인된다. 

이를 통해

 

를 찾아낸다. 이는 주어진 신뢰수준 1-π에 따라 귀무가설이 기각된 노드들의 집합임으로 실제로  pv != qv인 노드들의 집합인 I에 해당 집합, R이 최대한 유사하게 만드는 것이다. 

본 논문에서는 pdf의 p와 구분하기 위해 π를 p-value라고 함

 

Multiple Hypothesis Testing(MT) 접근법을 따라, 이 경우에도 R을 결정하기 위해서는 아래의 3가지 요소가 필요하다. 

1. H0에 대한 테스트 통계량 Sv는 노드 v의 데이터를 사용하여 p와 q의 유사도를 정량화한다. 

2. π, p-value 추정 프레임워큰 어떤 H0를 기각해야하는지를 식별한다. 

3. MCP 문제를 제어하기 위한 Type 1 error의 보정이 필요하다. 

 

그래프 구조의 MTST에서 기존의 방법들은 주로 plug-in 방법을 사용한다. 즉, 

• 각 노드에 대해 독립적으로 검정 통계량(test statistic)을 계산하고 π-value 추정 및 기각
•  사후적으로 제1종 오류를 보정하기 위하여 aggregation mechanism 적용, 즉 다중 통계 Sv에서 단일 테스트 통계를 정의하여 이용

하는 방법을 택했다. 

하지만 이러한 방법들은 각 쌍의 확률 밀도 함수pv와 qv간의 차이를 적절히 정량화하지 못하는 개별 테스트 통계량이 부정확한 결론을 초래할 수 있다는 것이다. 

 

주목할 만한 그래프 구조의 다중 테스트(MT) 기법에는 Permutation Cluster Test (PCT) (Maris & Oostenveld, 2007),
Threshold-free Cluster Enhancement (TFCE) (Smith & Nichols, 2009), and the Structure-Adaptive Benjamini
Hochberg Algorithm (SAHBA) (Li & Barber, 2018)가 있으며, 이들은 기각해야할 귀무가설이 연결되어있는 노드들의 집합과 연관되어있다고 가정한다. . PCT 및 TFCE 절차의 π-값은 최대 테스트 통계에 대한 permutaion test를 통해 추정된다. 반면에 SAHBA는 노드 수준의 π-값의 reweighting mechanism을 사용하며, 연결된 노드들이 유사한 π-값을 보일 것이라는 가정에 의존한다. 

 

본 논문은 CTST를 제안하여 non-parametric methods 와 graph smoothness 개념을 이용한다.

Graph smoothness:  그래프의 노드 간의 함수가 자연스럽게 변화하는 성질을 의미한다. 즉, 연결된 노드들이 비슷한 값을 가진다는 가정

 

Fig1은 이러한 방법을 설명한다. 기존방법들과 다르게 CTST는 모든 노드 수준의 테스트 통계량을 공동으로 추정하고 연관적인 방식으로 식별하여 통합된 추정과 기각을 함께 제공한다는 것이다. ϕ-divergence estimation, Kernel Methods, Multitasking, 특히 GRULSIF framework (de la Concha et al., 2024)를 이용하여 p와 q의 차이를 정교하게 정량화한다. 또한 graph smoohtness 가정을 통해 collaborative estimation은 연결된 노드 u와 v에 대한 테스트 통계량의 유사성을 강화한다. 노드 수준의 테스트 통계량에서 유도된 규칙은성은 효율적으로 k-Family-Wise Error Rate(FWER)을 제어하는 permutation test에 의해 활용되며, 노드를 식별한다 (이를 통해 개별 추정의 에러를 줄임)

 

k-FWER: k개 이상의 1종 오류가 발생할 확률을 의미, FWER은 1종오류를 의미

Figure 1: Collaborative multiple two-sample testing (CTST) based on collaborative LRE over a graph

Fig1: 왼쪽 그림은 각 그래프 노드 v에서 두가지 확률 밀도 함수인 파란색 p와 분홍 q에서 얻은 관측값을 바탕으로 
GRULSIF는 연관된 Liklihood ratio, r를 collaborative 방식으로 추정합니다. 이 예에서, 주어진 x가 실질적으로 그래프 신호 r에 매핑되는 방식을 쉽게 볼 수 있습니다. 오른쪽 그림은 CTST 테스트의 시각적 요약입니다. GRULSIF에 의해 계산된 가능도 비율은 노드 수준의 p-값을 추정하는 데 사용되며, 이를 통해 p와 q가 다른 노드를 궁극적으로 식별할 수 있습니다.

 

2. Preliminaries and problem statement

2.1 Preliminaries

2.1.1 General notations: 

 

추가적으로 Graph smootheness의 관한 정의는 다음과 같다. 

그래프 G = (V, E, W)는 다음을 따른다. V는 vertex. E는 edge, W는 가중치 행렬을 의미하며(N*N matrix), 양수이고 symmetric이며 Wuu = 0(self loop 없음). 

 

Smoothness는 다음과 같이 정의된다. 

그래프 함수  ϑ:V→R(즉 실수값을 할당)에 관하여 다음을 따를 때 smoothness가 정의됨

즉, 서로 연결된 노드들의 차이가 적고(괄호 안에 term). 연결 가중치가 클 수록 더 매끄럽다고 할 수 있다. 

 

 

2.1.2 ϕ-divergences and likelihood-ratio

ϕ-발산은 두 확률 측정 간의 비유사성을 측정하는 비음수 함수이다. 르벡 측도에 대해 두 확률 측도 p와 q를 비교하는 ϕ-divergence는 다음과 같이 정의된다. 

ϕ : R → R는 ϕ(1) = 0인 볼록하고 반연속인 실수 함수이다 (Csiszár, 1967).

이 값은 두 p와 q가 동일 할 때만 0이며, Eq2의 적분이 p에 의해서 이루어짐으로, 값은 p가 더 큰 값을 가지는 점들에 대해 민감하기에 비대칭 함수라는 특성을 가진다. 

 

아래 r은 liklihood ratio로, 모든 ϕ-divergence 계산의 중심이 된다. 3.1절에서 보겠지만 우리는 p와 q 사이의  카이 제곱편차의 근사를 likelihood-ratio estimation(LRE) 문제로 변환 가능하다.

하지만 실제로 r은 수렴하지 못할 수도 있기에 비모수 방법을 수행시 문제가 될 수 있다. 이러한 이유로 p를 아래와 같이 변형하여 얻을 수 있는

 α-relative likelihood-ratio function (Yamada et al., 2011)를 사용한다. 

 

2.2 Problem statement

Undirected & Postive weight를 가지는 그래프 G=(V,E,W)에 관하여, 각 노드 v는 두개의 알려지지 않은 pdf p와 q로부터 유래된 n + n'의 iid 관측치를 가지고 있다고 가정하자. 관측값은 다음과 같다. 

 

제안된 CTST는 수식 1에서 제시된 그래프 구조의 다중 두 샘플 테스트 문제를 해결하는 것을 목표로 하며 세 단계로 구성된다:

1. Collaborative estimation: 가용 데이터(Eq3)를 사용하여 노드 수준의 상대 우도 비

를 공동으로 추정한다. 벡터 값 함수 r은 각 노드 v에 대해 chi square divergence을 근사하는 데 사용된다.

카이 제곱 발산

2. Node-level test statistics: ϕ-divergences(2.1절 참조)은 이들을 노드 수준 테스트 통계량에 대한 좋은 후보로 만든다. 비대칭성을 다루기 위해 각 노드에서 노드 수준의 테스트 통계량 쌍 S와 S'이 사용되며, 이는 각각 χ2(p|q)와 χ2(q|p)에 해당한다. 

3. π-value 추정: 두 세트의 노드 수준 π-value, π와 π' 집합을 추정하는 데 사용되는 순열검정은 R(기각할 귀무가설 집합) 식별하는데 사용한다. 순열검정은 FWER에 대한 약한 제어를 보장한다.

3. The proposed collaborative non-parametric two-sample test (CTST)

CTST 방법의 기반은 그래프 구조에서의 collaborative likelihood-ratio estimation (LRE)이다. 용이하게도 이 문제는 de la Concha et al., 2024에서 설명되었으며, Graph based Relative Unconstrained Least Squares Importance Fitting (GRULSIF) 또한 제안되었고, 이를 본 논문의 방법에서도 사용한다. 그 전에 비모수 추정에 관한 기본적인 개념을 아래에 언급한다. 

Reproducing Kernel Hilbert Spaces

주로 머신러닝에서 비선형 함수를 다루기 위해 사용되는 도구로 이는 다음과 같이 정의된다. 

입력 공간  X  ⊂  R^d가 주어졌을 때, RKHS, H에 대하여 r(x)를 추정하는 것을 목표로 한다.  H는  함수  f : X → R 를 요소로 하는 공간이며, 공간  H 로, 내적 ⟨·, ·⟩H 를 가지며, Mercer Kernel K(·, ·)에 의해 재생됩니다. Mercer Kernel는 양의 준정부호(positive semi-definite) 조건을 만족하는 대칭 함수를 말한다. 그러면 H는 RKHS 재생 속성을 가진다. 

 

또한 H는 H = span({K(x, ·) : ∀x ∈ X })을 만족하며, 앞서본 smoothness의 개념은 RKHS에서 다음과 같이 일반화 가능하다. 

 

3.1. Step 1: Collaborative likelihood-ratio estimation

Graph-based framework for LRE (de la Concha et al.,2024)를 Step1에 적용하였다. 이는  χ2-divergence에 초점을 맞추고 있다. 

와 같이 Eq2를 설정하면 ϕ-divergences 수식을 Pearson χ2-편차(chi-squared divergence), PE(p||q)와 동일하게 만들 수 있다. 

즉,ϕ-divergences가 더 넓은 개념이라고 생각할 수 있다 

 

 

여기서 F는 함수 공간이며, 부등식 4b는 카이제곱 발산의 variational representation이며 이는 Lemma 1 in (Nguyen et al., 2008)에서 유도된다.  

 variational representation: 
어떤 함수의 값을 다른 함수들의 최적화 문제로 표현하는 것을 말ㄹ함. 이를 통해 원래 함수의 성질을 분석하거나 계산을 용이하게 함, 예를 들어 아래의 예시 등이 가능

카이제곱 발산의 경우, 부등식 4b에 나타나는 함수 f는 우도 비율 r을 근사한다. Sector 2.1에서 논의한 봐와 같이, r을 추정하는 대신 ra를 이용하는 방법이 추천되며,

 

를 추정한다. 마지막으로 식 4b를 관측값들을 이용한 기대값으로 다음과 같이 표현한다. 

 

함수 공간 F를 고르는 것은 실제로 구현될 수 있는 학습 알고리즘을 정의하는 데 핵심적이며, 동시에 안정성 및 일관성과 같은 원하는 이론적 특성을 고려해야한다. 우리의 접근 방식에서는 graph smoothness을 향상시킬 수 있는 기하학적 특성을 가진 RKHS를 선택한다. 이는 두함수 fu, fv ∈ H가 RKHS에서 가까울 경우, 동일한 점 x ∈ X에서 평가될 때 유사성을 나타낸다는 (6)에서 유래된다. 

 

여기서 C는 0보다 큰 상수이며, K()의 상한은 C보다 작거나 같다.  첫 번째 부등식은  H의 재생 속성으로 인한 것이고, 두 번째는 코시-슈바르츠 부등식의 결과이다. 따라서 그래프의 smoothness를 유지하여 인접 노드 y와 v에 에 대해  ||fu − fv||를 작게 하는 것이 유사한  χ2-divergence 추정치를 도출할 것으로 예상된다.

 

3.1.2  Optimization problem ???

이 최적화 문제의 목표는  r = (r1 , ..., rN,), 즉 각 노드에 관한 relative Likelihood-ratio 학습하는 것이다. 이를 위해 3.1에서 밝힌것과 같이 부등식 4b에 나타나는 함수 f는 우도 비율 r을 근사하기에 f에 관한 최적화 수식을 풀며 이는 아래와 같다.

 

첫번째항은 각 노드에서 카이제곱 발산의 음의 variational representtation의 해당(식 5의 비상수항)한다. 

두 번째 항은 추정치의 그래프 매끄러움을 평가합니다. 마지막 항은 과적합의 위험을 줄이는 패널티 항입니다 (Sheldon, 2008). 유한 차원 공간 F = span({φ(x) : x ∈ DˆL}) 이  H를 근사하는  D^기반 함수 집합이 주어졌을 때, feature map φ(x)를 공간 F로의 직교 투영으로 대체하기 위해 Nyström 근사를 사용하는 것이 제안되었다. H에서 이른바 앵커 포인트 세트를 결정하고, 관련된 커널 매트릭스

에서 새로운 feature map은 다음과 같이 유도된다. 

 

식 7, 최적화 문제를 Empirical expectaion으로 표현하고,  Nyström 근사를 취하면 f^은 다음과 같은 형태로 취해진다.

여기서

로 모든 노드 매개변수를 벡터화하면서 최적화 문제는 다음과 같은 형태의 2차 문제로 다시 작성된다. 

 

3.1.3  Implementation

de la Concha et al., 2024)의 구현을 따르며, 문제 10을 Cyclic Block Coordinate Descent (CBCD) 방법으로 해결하는 것을 제안합니다 (Beck & Tetruashvili, 2013; Li et al., 2018). n=n' 일 때, 최종 계산 비용은 다음과 같습니다:

 

여기서 L << Nn 임으로 실제 그래프에 확장 가능하다. 

Cyclic Block Coordinate Descent알고리즘은 전체 변수를 여러 개의 블록으로 나누고, 각 반복 단계에서 하나의 블록에 속한 변수들을 동시에 업데이트. 이 과정은 모든 블록이 업데이트될 때까지 반복

GRULSIF의 다른 중요한 구현 요소로는 앵커 포인트 선택 및 하이퍼파라미터 선택이다; 후자는 커널 함수의 매개변수 및 정규화 상수 λ, γ에 해당합니다. 정규화 매개변수 α의 경우 특별한 주의가 필요하므로, 우리는 연구된 CTST 작업에 대해 몇 가지 유익한 실험을 Appendix B.3.2에서 남겨둔다. 

3.2. Step 2: Node-level test statistic

 Θ, 매개변수 벡터가 추정된 후 우리는 χ2-divergence를 다음과 같이 근사할 수 있다.

 

발산의 비대칭성 문제를 해결하기 위해(Eq2), 다음 PE(p||q)와 PE(q||p)를 고려한 통계량을 통해 R을 식별한다. 

 

PE^(Xv ||X′v )는 PE(pv||qv )의 asymptotic unbaised estimator이며, 이는  graph smoothness hypothesis와 collaborative LRE가 추정문제가 더 여려워 질수록 관련성이 높아진다(de la Concha et al., 2024), 예를 들어 각 노드에 관한 가능한 관측치가 더 적어지는 경우가 이에 해당한다. 모든 v에 관하여  pv = qv이면 graph smooth가 성립하니, 모든 연결된 노드에 관해

 

가 성립한다. 

 

본 연구에서는 이러한 특성을 활용하여 FWER을 제거하기 위해 모든 노드에 대해 pv = qv를 H0 로 가지는 순열검정을 제안하며, 동시에 측정의 변화를 경함하는 노드를 식별할만큼의 민감도를 유지한다. 

 

3.3. Step 3: π-value estimation

본 논문의 다중검정 전략은 각 추정된 노드별 π-값에 대해 임계값 η∗을 적용하여 기각된 노드들의 집합 R을 생성한다. 

TP, True positive는  #{v | v ∈ I0 ∩R}로  False postive #{v | v ∈ R \ I0}로 정의한다. 

 

k-Family-Wise Error Rate (FWER for k = 1)를 제어하여 multiple two sample test를 다룬다. 

k-Family-Wise Error Rate는 개별 노드 수준에서 최소 한개가 잘못 기각될 확률( H0가 참, 즉 p=q인데도 기각하는 시나리오, 다시말해 동일분포에서 나왔음에도 다른 분포에서 나왔다고 판단할 확률)을 말하며 수식으로는 아래와 같다. 

여기서 π*은 0.01 혹은 0.05로 사용자가 정의한다. 

I0: 해당 논문에서 I0는 귀무 가설이 실제로 참인 노드들의 집합. 즉, 두 샘플 간에 실제로 차이가 없는 노드들의 모음.

 

우리는 아래의 귀무가설을 고려한다. 

 

강한 FWER 통제가 모든 부분집합 I0 ⊂ V 에 대해 적용되는 것과 달리 약한 통제는 I0 = V인 경우에 대해서만 다룬다.

• Strong FWER control: 강한 전체 오류율 제어는 귀무 가설이 참인 모든 부분 집합에 대해 오류율을 제어하는 것을 의미합니다. 즉, 어떤 경우에도 제1종 오류를 범할 확률을 낮게 유지합니다.
• Weak FWER control: 약한 전체 오류율 제어는 모든 귀무 가설이 참인 경우, 즉 $I_0 = V$인 경우에만 전체 오류율을 제어합니다. 여기서 I0는 참인 귀무 가설의 집합을 나타내고, V는 전체 노드 집합을 의미합니다. 즉, 모든 노드에서 귀무 가설이 동시에 참일 때 제1종 오류를 범할 확률을 제어합니다. 

 Weak FWER control은 두 가지 서로 다른 실험 조건 하에서 complex 시스템의 행동을 연구할 때 특히 관련있다. 두 조건 간에 통계적으로 유의미한 차이가 없을 때, 모든 노드가 귀무가설(eq 15)을 만족하는 것이 예상된다.

신경과학은 이런 상황을 잘 설명하는 예시들을 제공한다: MTST는 센서들이 뇌의 활동을 모니터링하며 주어진 자극에 대한 발화 뉴런 클러스터를 탐지하는 것을 목표로 한다. PCT (Maris & Oostenveld, 2007)와 TFCE (Smith & Nichols, 2009)와 같은 고전적인 방법들은 뇌 기능의 고유한 그래프 구조를 고려하고 약한 FWER 통제를 수행한. 이를 통해 두 실험 조건 간의 잘못된 차이를 주장하는 위험을 완화하면서도 신경 활동 패턴을 감지하는 데 필요한 민감도를 유지한다. 

 

Step 1에서 Collaborative ϕ-divergence 추정이 도입한 그래프 정규화는 노드 수준 테스트 통계에 대한 아웃라이어에 대해 강건한 추정을 제공한다. 이는 귀무가설 하에서 특히 관련이 있으며 우리는 거짓 양성(FP)을 피하고자 하므로 이러한 특성을 사용하고 약한 FWER control을 통해  π-값d을 추정하는 것이 자연스럽다. 

비모수 LRE의 유연성은 pdf p, q에 대해 일정 수준의 이질성(heterogeneity)을 허용합니다. 이는 인접한 노드의 쌍 ((pv, qv) 및 (pu, qu) 간의  relative likelihood-ratio가 공유하는 RKHS에서 근접한 함수로 근사될 수 있는 한에서 가능하다. 이 기능은 H0 하에서 테스트 통계의 분포를 복잡하게 만들며, 결과적으로 FWER 통제를 위한 명시적 공식을 도출하기 어렵게 만든다. 더욱이, 의도된 응용을 위해서는 Node-level test statistic 간의 상관관계를 고려하는 것이 중요하다.

 

우리는 프레임워크를 제한하지 않으면서 위의 문제를 해결하기 위한 비모수적(non-parametric) 전략으로서 순열 검정(permutation test)의 사용을 제안한다 (Westfall & Young, 1992).

 

설계된 순열 검정은 벡터 X:,j=(x1,j,...,xN,j)T  (또는 X:,j′=(x1,j′,...,xN,j′)위에서 수행되며, 각각은 모든 노드에 대해 주어진 샘플 인덱스 j를 가지는 관측값들을 포함한다.

순열 검정은 최대 검정 통계량

의 분포를 추론하고, 이를 이용하여 R를 결정함으로써 약한 FWER(Family-Wise Error Rate) 제어를 π∗ 수준에서 달성한다.

 

CTST 알고리즘은 알고리즘 1(Alg. 1)에 제공되어 있다.Theorem 3.1은 CTST가 사용자 정의 비율 π∗을 제공하는 약한 FWER 제어를 갖는 MT(multiple testing) 절차임을 검증한다. 증명의 기술적 세부 사항은 부록에 제공된다.

 

3.4. A CTST variant ignoring the graph structure(그래프 구조 무시하는 변형)

우리는 POOL을 기반으로 하는 축소된 CTST 변형(reduced CTST variant)을 도출할 수 있으며, POOL은 동일한 추정 프레임워크를 사용하지만 그래프 구성 요소를 무력화하는 GRULSIF 변형이다(즉, 식 (10)에서 W=0N×N으로 설정함) (de la Concha et al., 2024).

이 POOL-CTST 변형은 MT(Multiple Testing) 문제에 그래프가 존재하지 않는 경우에 유용할 수 있다.

POOL은 RULSIF(Yamada et al., 2011; 2013)의 변형으로 볼 수 있지만, 다음과 같은 차이가 있다.

i) RULSIF가 각 노드에 대해 독립적으로 하이퍼파라미터를 선택하는 것과 달리, POOL은 모든 노드에 대해 평균 점수

 

기반으로 공동 하이퍼파라미터 선택을 수행한다.

 

ii) POOL은 전체 데이터 관측값을 대상으로 한 Nyström 차원 축소 기법을 사용하지만, RULSIF는 각 노드 또는 전체 데이터에서 단순한 균일 무작위 샘플링을 사용한다 (Sugiyama et al., 2012).

 

 

4. Experiment 

본 장에서는 제안한 방법론인 CTST를 그래프 구조를 가진 Multiple testing 문제, 합성(synthetic) 및 실제(real) 시나리오에서 적용한다. 이를 통해 노드 수준 테스트 통계량을 비모수적(non-parametric) 그래프 기반 협업 추정 방식으로 결합하는 것과, 최대 통계를 이용한 순열 검정을 통해 약한 FWER(Family-Wise Error Rate) 제어를 달성하는 것의 이점을 확인하는 것이다 

 

CTST는 SAHBA, PCT, TFCE와 같은 방법들의 직접적인 비교대상이 아니며, 이러한 방법들은 오히려 CTST의 출력을 후처리(post-processing)하는 보완적인 접근 방식으로 볼 수 있다. 

CTST는 그래프 구조를 가진 데이터에서 두 샘플 간의 차이를 검정하는 데 주력한다. 즉, 각 노드에서 두 확률 분포가 동일한지 여부를 판단하는 데 목적이 존재. , 연결된 노드들이 유사한 테스트 결과를 가질 것이라는 가정하에 귀무 가설을 검정. 반면, SAHBA, PCT, TFCE는 주로 뇌파(EEG)나 뇌 자기장(MEG) 데이터 분석에서 클러스터 기반의 통계적 유의성을 평가하는 데 사용한다, 

 

공정한 비교를 수행하고 비모수적 방법의 유연성을 유지하기 위해, 우리는 커널 방법(Kernel Methods)을 기반으로 구축된 추정 접근법에 초점을 맞춘다. 비교 대상은 LRE 기반 비모수적 알고리즘(테스트 통계량이 ϕdivergence 추정량에 해당하는 경우)과, 비모수적 통계 검정의 최신 기술(state-of-the-art)로 간주되는 MMD(Maximum Mean Discrepancy)를 기반으로 한 커널 방법(Gretton et al., 2012)이다. 표 1(Tab. 1)은 비교된 모든 방법을 보여주며, CTST만이 그래프 구조를 통합하고 있음을 알 수 있다.

 

각 비모수적 방법에서는 정규화 상수와 커널 함수의 하이퍼파라미터를 설정해야 하며, 우리는 폭 파라미터 σ를 가진 가우시안(Gaussian) 커널에 집중한다. LRE 기반 방법들은 교차 검증(cross-validation)을 통해 하이퍼파라미터를 결정하며, MMD의 경우 관련 연구를 참고하여 원래의 MMD-MEDIAN 버전(Gretton et al., 2012)과, 두 샘플 검정의 검정력과 연관된 점수를 목표로 하는 MMD-MAX 방법(Sutherland et al., 2017)을 비교 대상으로 선정하였다. 하이퍼파라미터 선택에 대한 자세한 내용은 부록 B(Appendix B)에 제공된다.

 

다른 방법들의 경우, 전통적인 MT 접근법을 따른다. 즉, 먼저 각 노드에 대해 독립적으로 노드 수준 테스트 통계량을 추정한 후, 최대 통계를 이용한 비모수적 재표본 검정(non-parametric resampling test)으로 MCP(Multiple Comparison Problem)를 제어한다(Westfall & Young, 1992). 노드 수준 테스트 통계량 {Sv}는 각 방법이 측정하는 불일치(dissimilarity)의 개념(즉, ϕ divergence 또는 MMD)과 일치하며, H0 하에서의 SG=max⁡Sv분포는 순열 검정을 통해 추정된다(알고리즘 1(Alg. 1) 참조).

 

ϕ-divergence 기반 방법들의 비대칭성(non-symmetricity) 문제는 섹션 3.2에서 CTST에 대해 사용한 방식과 동일하게 해결하며, p,q 및 q,p 를 비교한다. 그런 다음, 사용자가 제공한 임계 비율 π∗에 따라, 기각된 가설 집합을 다음과 같이 정의한다.

 

설계된 네 가지 완전 합성(fully synthetic) 시나리오의 각 인스턴스는 무작위 그래프를 생성한 후, 특정 노드 하위 집합에서 발생하는 변화의 패턴을 정의하는 방식으로 생성된다.

• Synth.Ia & Synth.Ib: 4개의 클러스터(cluster)로 구성된 확률적 블록 모델(Stochastic Block Model, SBM)을 사용하며, 각 클러스터는 25개의 노드를 포함한다(클러스터 내(edge intra-cluster) 연결 확률: 0.5, 클러스터 간(edge inter-cluster) 연결 확률: 0.01). 이후, 클러스터 기반 체계를 통해 각 클러스터(C1,...,C4)의 모든 노드에 대해 동일한 변화(측정값 변화 유무)를 설정한다.
• Synth.IIa & Synth.IIb: 100개의 노드로 구성된 격자 그래프(Grid graph, GRID)를 사용하며, 10×10 정규 타일링(regular tiling) 형태를 갖는다. 이 경우, 에고 네트워크(ego-network) 기반 체계를 적용하며, 먼저 노드 u를 무작위로 선택하는데, 선택 확률은 노드의 차수(degree)에 비례한다. 이후, u의 2-hop 에고 네트워크(단순히 C(u)로 표기되는 노드 집합) 내의 노드들만이 측정값 변화를 경험하도록 설정한다.

4.1. Synthetic experiments

합성 시나리오는 설계상 I0=V∖I0​ 집합을 제공하는데, 이는 pv≠qv가 성립하는 노드 인덱스 v를 의미한다. 이를 통해 다양한 MT(Multiple Testing) 프레임워크의 검정력(power)을 비교할 수 있다.

표 2(Tab. 2)에 자세히 설명된 시나리오들은 그래프 부드러움 가설(graph smoothness hypothesis, 즉 연결된 노드는 유사한 행동을 보인다는 가설)을 만족하도록 (de la Concha et al., 2024)의 연구와 유사하게 설계되었으며, GRULSIF가 해결해야 하는 LRE(Local Regularization Estimation) 관련 여러 도전 과제를 포함하고 있다. 이러한 각 시나리오를 기반으로, 우리는 p와 q​를 비교하는 이표본 검정(two-sample test) 을 수행한다. 두 확률 밀도 함수(pdf)는 평균(mean), 형태(shape), 공분산(covariance) 등의 차이를 가질 수 있다(표 2의 노드 수준 가설 참조). 또한, 동일한 시나리오에서 여러 유형의 변화가 발생할 수도 있다.

MT 절차의 성능은 다음 두 가지 기준을 중심으로 측정된다.

1. FWER 제어의 효율성 – 즉, 식 (15)의 귀무 가설(H0) 하에서 하나 이상의 거짓 양성(false positive)이 발생할 확률.
2. 추정된 노드 수준 π값의 정보성 – 낮은 π값이 실제로 I0​에 속하는 노드들과 얼마나 잘 연관되는가.

실제 응용 관점에서 보면, 두 개의 시간 스탬프(time-stamp) 또는 실험 조건을 비교할 때, 거짓 양성을 최소화하여 존재하지 않는 통계적으로 유의미한 차이를 주장하지 않는 방법이 선호된다. 또한, MT 절차가 관측된 편차를 유발한 노드들을 얼마나 정확하게 식별하는가도 중요한 요소이다. 이 품질 평가는 대안 자유 반응 수신기 조작 특성(Alternative Free-response Receiver-Operating Characteristic, AFROC) 곡선(Chakraborty & Winter, 1990)으로 요약된다. AFROC 곡선을 추정하는 자세한 방법은 부록 B(Appendix B)에 제공된다.

 

AFROC 곡선의 AUC(Area Under Curve)는 표 3(Tab. 3)에 보고되며, AUC 값이 높을수록 성능이 우수함을 의미한다. 즉, 해당 방법이 FWER 수준 π∗=0.05를 유지하면서도 I0내의 노드들을 잘 식별할 수 있음을 의미한다.

우리가 설계한 AFROC 곡선은 거짓 양성(false positive) 노드들, 즉 {v∣v∈R∖I0}를 무시한다. 따라서, 우리는 ROC 곡선의 AUC도 함께 보고하지만, 해석할 때는 AFROC-AUC가 가장 중요한 기준이며, ROC-AUC는 유사한 AFROC-AUC 값을 가진 방법들을 구별하는 보조적인 기준으로 사용해야 한다.

4.1.1 Synthetic experiments Finding

표 3(Tab. 3)의 결과를 보면, CTST는 문제의 기하학적 구조(geometry)를 고려하지 않는 다른 방법들에 비해 명확히 더 효율적인 검정 방법임을 확인할 수 있다. 그래프의 역할은 관측값이 적을수록, 그리고 pv와 qv사이의 차이가 미묘할수록 더욱 중요해진다.

이러한 효과는 특히 CTST와 그래프를 사용하지 않는 변형 모델인 POOL(섹션 3.4) 을 비교할 때 더욱 두드러진다. 또한, CTST는 POOL에 비해 정규화 파라미터 α의 변화에 대해 더욱 강건하고 일관된 성능을 보인다(부록 B 참조).

4.2. Two-sample testing on real seismic data

CTST의 공간 통계 분석(spatial statistical analysis)에서의 잠재력을 보여주기 위한 실용적인 예시로 지진 데이터(seismic data) 를 사용한다. 다만, 본 연구가 해당 분야의 최신(state-of-the-art) 방법들을 능가하려는 시도로 해석되어서는 안 된다는 점을 강조한다.

 

지질학적 재해 모니터링 시스템(geological hazard monitoring systems)은 여러 개의 관측소(stations) 로 구성되며, 이는 특정 지역에 전략적으로 배치되어 지표면 소음 및 흔들림(ground noise and shaking) 을 다양한 센서를 통해 감지한다.

지진이 발생하면 지각을 통해 전파되며, 이 과정이 모니터링 센서에 의해 포착된다. 일반적으로 진앙(epicenter)에 가까운 관측소일수록 반응이 더 빠르며, 지진 발생 전후 데이터에서 더 뚜렷한 차이를 보이는 경향이 있다.

이러한 맥락에서, 그래프 기반의 다중 이표본 검정(multiple two-sample test) 을 활용하면,

1. 지진의 유의미성을 평가하고,
2. 각 관측소가 언제, 그리고 어떤 시간 구간 동안 활성화되었는지를 식별할 수 있다.

4.2.1 Data Preprocessing

우리는 뉴질랜드(New Zealand)에서 발생한 두 개의 지진(seismic events) 을 분석한다.

• 지진 A (Seism A): 규모 5.5(Magnitude 5.5, 리히터 규모), 2021년 5월 31일 발생
• 지진 B (Seism B): 규모 2.6(Magnitude 2.6, 더 약한 지진), 2023년 10월 2일 발생

각 관측소에는 강진 가속도계(strong-motion accelerometers) 가 장착되어 있으며, 이들은 세 개의 수직 방향(perpendicular directions) 에 따른 3차원 신호(3D signals) 를 제공한다.

지진 발생 이전 50초부터 이후 50초까지의 파형(waveforms) 을 분석하며, 샘플링 주파수는 100Hz 이다.

 

각 지진 사건을 10개의 5초짜리 time-window로 분할하고,

• 이전 시점 데이터 Xv​ (pre-event)
• 이후 시점 데이터 Xv′​ (post-event)

라고 한다. 이제 각 노드 마다 time-winow들간의 유의미한 변화가 있는지 two-sample test를 거친다. 

 

 

데이터 전처리에서는 CTST의 수학적 가정을 만족하도록 값을 변환해야한다. 

1. r이 동일한 RKHS에서 근사되어야한다, 즉 모든 노드에서 동일한 공간에서 학습 가능하도록 보장해야한다. 

2. 각 노드에서의 샘플이 독립적이고 동일한 샘플 크기를 유지해야한다: 각 창에서 동일 개수 100개의 관측값을 이용 

3. graph smoothing을 만족해야한다

 

전처리 과정은 각 관측소와 각 방향(3개의 변화)에 대해 독립적으로 수행된다.

선형 추세를 제거하고 2-16 bandpass filter 를 적용한다.

주파수 범위가 2Hz에서 16Hz 사이인 신호만을 통과시키고, 이 범위를 벗어나는 주파수 성분은 감쇠시키는 필터입니다. 이러한 필터는 밴드패스 필터의 일종으로, 특정 주파수 대역만을 선택적으로 통과시키는 역할을 합니다.​
밴드패스 필터는 다음과 같은 기능을 수행합니다:
1. 특정 주파수 대역 통과: 설정된 주파수 범위 내의 신호만을 통과시키고, 그 외의 주파수는 억제합니다.​
2. 잡음 및 불필요한 신호 제거: 관심 있는 주파수 대역 외의 잡음이나 간섭 신호를 제거하여 신호의 품질을 향상시킵니다.

제곱 평균 제곱근(RMS) 진폭를 계산한 후  Amplitude Envelope를 계산하여 이용한다.

진폭의 변화 패턴을 명확하게 볼 수 있음 원래 신호는 고주파 성분이 많아서 지진이 시작되는 지점을 찾기 어려울 수 있음. RMS Amplitude Envelope을 계산하면, 시간에 따른 전체적인 에너지 변화를 볼 수 있어 지진파의 도착 시점이나 주요 변화를 쉽게 감지 가능.

잡음을 줄이고 더 중요한 특징만 남길 수 있음 원래 신호에는 **배경 잡음(Noise)**이 포함될 수 있음. RMS Amplitude Envelope을 사용하면 불필요한 고빈도 변동을 제거하고, 신호의 전체적인 변화를 부드럽게 나타낼 수 있음.

이표본 검정(Two-Sample Test, TST)의 신뢰도를 높임 원래 신호는 **극단적인 피크 값(peak value)**이 많아, 단순한 검정 방법을 적용하면 오탐(False Positive)이 많을 수 있음. RMS Amplitude Envelope을 사용하면 전체적인 신호 패턴을 비교할 수 있어, 진짜 지진파 변화만 감지할 수 있음.

 

이후 시간적 의존성을 줄이기 위해, AR(1)을 적합시키고, 해당 모델에서 나온 잔차를 이용한다. 
출력값은 평균이 0이고 분산이 1이 되도록 표준화된 다음, 관측소 간 데이터를 비교 가능하게 만들기 위해 출력값을 해당 최대값으로 나눈다. 

 

4.2.2 Graph Structure

우리는 지진 관측소와 그 신호 간의 공간적 및 시간적 유사성을 모두 반영하는 그래프 표현을 두 단계에 걸쳐 구축한다.

 

1단계: 공간 그래프 (G_S​) 구축

먼저, 공간 그래프 G_S=(V,E,W) 를 생성한다.

• 노드(V): 분석 대상 시간 동안 모든 가속도계(accelerometers)의 데이터가 사용 가능한 관측소(stations) 를 노드로 간주한다.
• 엣지(E): 각 관측소를 지리적으로 가장 가까운 3개의 이웃(nearest neighbors)과 연결하여 무가중(unweighted) 그래프를 구성한다, 이를 3NN graph라고 한다. 

2단계: 시공간 다중 그래프 (G_S×T) 구축

이제, 시간 차원을 통합하여 다중 그래프(multiplex graph) G_S×T를 구축한다.

• 신호를 지진 발생 전후로 나누어 10개의 시간 창(time-windows) 으로 세분화하며, 각 창은 동일한 개수의 관측값을 포함한다.
• G_S×T의 노드는 원래 공간 그래프 G_S의 노드에 시간 차원을 추가한 V×T로 정의되며, 여기서 T={1,...,10}이다.
• 두 노드 (u,t)와 (v,t′) 는 다음 조건 중 하나를 만족할 때 연결된다.
  1. t=t′, (u,v)∈E(u, v)인 경우 → 같은 시간 창에서 공간 그래프 GSG_SGS​ 내에서 연결된 두 노드는 여전히 연결됨.
  2. u=v, |t′−t| =1 인 경우 → 각 노드는 시간적으로 연속된 두 개의 인접 시간 창에서의 자신과 연결됨.

각 데이터 관측값은 해당하는 노드와 시간 창에 의해 인덱싱된다. 이를 기반으로, 우리는 확률 밀도 함수(pdf) 집합을 정의한다.

 

전처리 이후, 각 노드-시간 창 쌍 (v,t) 에 대해 두 개의 샘플을 얻는다.

 

​

우리는 t=0 을 샘플링 시작점(즉, 지진 발생 50초 전) 으로 설정한다.

• X(v,1)​ → 지진 발생 이전 첫 5초간의 관측값
• X'(v,1)→ 지진 발생 이후 첫 5초간의 관측값

이러한 구성 하에서, 이표본 검정(two-sample test) 을 통해 p(v,t)≠q(v,t) 인 노드-시간 창 쌍 (v, t) 을 식별하는 것이 목표이다.

 

결과 시각화 및 클러스터 분석는 다음과 같이 이루어진다. 

• 각 방법에 대해 계산된 π값의 지도(map of computed π-value) 를 생성한다.
• π값이 0.05보다 작은 노드-시간 창 쌍 (v,t) 은 강조(highlight)되어 표시됨.
• G_S×T​에서 이러한 노드들을 포함하는 가장 큰 클러스터 C_S×T 만 보고하며, 즉, 가장 큰 규모의 유의미한 변화가 발생한 영역을 분석한다.

4.2.3 Findings

그림 2(Fig. 2) 는 지진 A(Seism A) 에 대한 CTST 결과를 시각적으로 보여주며, 나머지 실험 결과의 시각화는 부록 B.2.3(Appendix B.2.3) 에 제공된다.

모든 실험된 방법들은 지진 발생을 정확하게 탐지하고, 진앙(epicenter)에 가까운 관측소들이 가장 민감하게 반응하는 노드임을 식별할 수 있었다.

그러나, 그래프 구조를 고려하지 않는 방법들 (즉, 관측소 간의 공간적 및 시간적 유사성을 반영하지 않는 방법들) 은 정보성이 떨어지는 탐지 결과를 초래하였다.

• 예를 들어, 관련 π값을 보면, 지진의 영향이 실제 신호에서 사라진 후에도 오랫동안 지속되는 것처럼 보이는 비현실적인 결과가 도출되었다.
• 반면, CTST는 진앙에 가까운 대부분의 노드를 올바르게 복원하며, 지진 이벤트의 진행 과정을 더 정확하게 추적하였다.

이러한 결과는 합성 실험(synthetic experiments)의 결과와도 일치한다.

• 진앙(AFROC-AUC 및 ROC-AUC) 지표에서 CTST는 거짓 경보(false alarms)에 대해 더 강건(robust) 하며,
• 그래프 부드러움 가정(graph smoothness assumption)이 성립할 때, 관심 노드(nodes of interest)를 더 높은 신뢰도로 복원한다.

음영이 있는 부분은

CTST가 단순히 신호의 진폭이 커졌다고 판단하는 것이 아니라, 신호의 확률 분포가 귀무가설(변화 없음)을 기각할 만큼 유의미하게 변화했다고 함, 즉 time window 내의 두 확률분포가 통계적으로 다르다고 판단하면 파란음영으로 표시 

5. Conclusions and further work

 

본 논문에서는 그래프의 노드에 대해 여러 두 표본 테스트를 위해 설계된 새로운 그래프 구조 비모수 테스트를 보였다. 이 접근 방식은 collaborative log ratio estimation 의 발전을 통합하여, 그래프 부드러움 가정 하에 노드 수준의 테스트 통계치를 공동으로 계산하고 기각해야 할 귀무가설을 식별하는 장점을 가진다. 이 방법은 유연하며, 각 노드에서의 데이터가 다변량일 수 있는 복잡한 시나리오를 처리할 수 있는 능력을 가지고 있으며, 비교하는 pdf 간의 차이의 성격은 알려지지 않고 노드의 테스트 간에 일정량의 이질성이 허용한다.

합성 및 실제 실험 결과는 우리의 방법이 테스트 간의 유사성을 고려하지 않는 최신 비모수 접근 방식에 비해 유리하게 작용한다는 것을 보여준다. 향후 연구로는 이 접근 방식을 더 많은 응용 프로그램에 확장하고, 보다 엄격한 제1종 오류 제어를 위한 전략을 설계하는 것이 흥미로울 것이다.