기술 요약: k-차수 충실성 가정을 통한 고차 마르코프 블랭킷 발견

문제 정의

마르코프 블랭킷(Markov Blanket, MB) 발견 문제는 결합 분포 $P$로부터 샘플링된 데이터셋을 통해 타겟 변수 $Y$의 그래픽 MB를 추론하는 문제를 포함한다. 이 과업은 베이지안 네트워크(BN) 및 마르코프 랜덤 필드(MRF)의 구조 학습, 인과 발견, 그리고 피처 선택에서 매우 중요하다.

기존의 대부분의 제약 기반 MB 발견 방법들은 **충실성 가정(faithfulness assumption)**에 의존한다: 즉, 분포 $P$에서의 모든 조건부 독립(CI)은 그래프 구조 $G$에서의 분리와 대응된다는 전제이다(그 반대도 마찬가지이다). 그러나 이 가정은 다음과 같은 두 가지 방식으로 빈번하게 위배된다:

1. 실제 위배(True Violations): 노이즈가 섞인 XOR 또는 고차 패리티 함수와 같은 특정 함수적 관계는 그래프 구조에 대해 "불충실한(unfaithful)" 의존성을 생성한다. 예를 들어, $k+2$개의 변수가 포함된 노이즈 섞인 패리티 함수의 경우, 변수들이 그래프상에서 연결되어 있음에도 불구하고 쌍방향(pairwise) 및 저차 조건부 독립이 존재할 수 있다.
2. 경험적 위배(Empirical Violations): 실제 분포가 충실하더라도, 유한한 샘플 크기로 인해 통계적 오류가 발생하여 경험적 CI가 실제 분포와 일치하지 않을 수 있다. 극단적인 경우, 샘플 수가 적을 때 알고리즘은 실제 MB를 복구하지 못하거나 가짜 의존성을 발견할 수 있다.

3개의 변수를 포함하는 XOR 유형의 관계를 다루는 **2-인접성 충실성(2-adjacency faithfulness)**과 같은 이전의 완화 방식들은 3개 이상의 변수를 포함하는 고차 패리티 관계를 포착하는 데 실패한다.

방법론

$k$-차수 충실성 완화

저자들은 앞선 (2-adjacency faithfulness와 같은) 완화 방식을 $k+2$개 변수 간의 패리티 유형 의존성을 포착할 수 있도록 일반화한 **$k$-차수 충실성($k$-order faithfulness)**을 제안한다.

• $k$-차수 의존성: 두 변수 $Y$와 $X$는 분리 집합 $S$의 임의의 부분 집합이 조건부 집합에 추가되더라도(단, $|Z|=k$일 때) 여전히 조건부 의존 상태를 유지한다면, $Z$에 대해 $|Z|$-차수 의존적이라고 정의된다.
• 가정: 그래프 $G$가 $P$에 대해 $k$-차수 충실하다는 것은, 임의의 변수 $Y, X$와 집합 $S$에 대하여, 만약 어떤 $Z$(크기 $\le k$)와 $S' \subseteq S$가 주어졌을 때 $Y$와 $X$가 $Z \cup S'$에 대해 조건부 독립이라면, $Y$와 $X$는 $S$에 의해 그래픽적으로 분리된다는 것을 의미한다.
• 대우(Contrapositive): 만약 $Y$와 $X$가 그래프에서 분리되지 않는다면, $Y$와 $X$는 $S$에 대하여 $Z$($|Z| \le k$)를 통해 연관(dependent)되어 있어야 한다.

계산 가능성을 확보하기 위해, 저자들은 **$l$-유계 분리 가정($l$-bounded separator assumption)**을 도입한다. 이는 만약 $Y$와 $X$가 큰 집합에 대해 조건부 독립이라면, 해당 집합의 부분 집합 중 크기가 $\le l$인 집합이 존재하여 이들을 독립으로 만든다는 가정이다. 이 가정은 CI 테스트 중 조건부 집합을 탐색하는 범위를 제한한다.

kOMB 알고리즘

본 논문은 이러한 새로운 가정 하에서 작동하도록 Grow and Shrink (GS) 알고리즘을 수정한 개념 증명 알고리즘인 kOMB($k$-order Markov blanket)를 소개한다.

1. Grow 단계: 개별 변수를 테스트하는 대신, kOMB는 현재의 후보 MB와 함께 조건화되었을 때 $Y$와 다른 변수들 사이의 의존성을 드러내는 변수들의 부분 집합(크기 최대 $k$)을 반복적으로 탐색한다. 이는 "상호 연관된(inter-associated)" 집합을 식별하기 위해 재귀적 탐색(find_inter_dep)을 활용한다.
2. Shrink 단계: 후보 MB의 남은 변수들의 부분 집합(크기 $l$로 제한됨)에 의해 $Y$로부터 분리될 수 있는 변수를 MB에서 제거한다.
3. 이론적 보장: 저자들은 전역 마르코프 성질(Global Markov Property), $k$-차수 충실성, 그리고 $l$-유계 분리 가정 하에서 kOMB가 변수의 그래픽 MB를 정확하게 복구함을 증명한다.

주요 기여

1. 이론적 프레임워크: $k+2$개 변수가 포함된 고차 패리티 관계를 처리하기 위해 기존의 완화 방식(예: 2-adjacency faithfulness)을 일반화한 $k$-차수 충실성의 정의를 제시하였다.
2. 알고리즘 구현: 고차 의존성이 존재하는 상황에서 MB 발견을 수행하기 위해 $k$-차수 충실성을 활용하는 제약 기반 알고리즘인 kOMB를 개발하였다.
3. 경험적 검증: kOMB가 실제 위배(예: 패리티 함수) 및 경험적 위배(유한 샘플 효과)로 인해 기존 방법들이 실패하는 시나리오에서 MB를 성공적으로 복구함을 입증하였다.

실험 결과

합성 데이터

저자들은 4개의 변수로 구성된 합성 베이지안 네트워크에서 $Y$가 다섯 가지 서로 다른 불리언 함수(XOR, 패리티, "exactly-1" 포함)를 통해 생성된 경우에 대해 kOMB를 테스트하였다.

• 성능: kOMB는 GS 알고리즘 및 기타 기존 방법들(IAMB, HITON 등)보다 일관되게 우수한 성능을 보였다.
• 고차 복구: 3-변수 XOR 확장형인 패리티 함수의 경우, 표준 방법들은 MB를 복구하는 데 실패했다. 반면 $k=2$를 적용한 kOMB는 완벽한 복구(F1 스코어 1.0)를 달성하여, 3개의 조건부 변수를 필요로 하는 의존성을 탐지할 수 있음을 확인하였다.
• 샘플 크기 민감도: 낮은 샘플 regime에서, 더 높은 $k$ 값을 가진 kOMB는 낮은 차수의 방법들에 비해 경험적 충실성 위배에 대해 더 뛰어난 강건성을 보여주었다.

벤치마크 데이터셋

Alarm1, Barley, Insurance, Mildew의 네 가지 표준 데이터셋에 대해 실험을 수행하였다.

• 성능: kOMB는 일반적으로 BAMB, HITON, MMMB와 같은 최신 기법들과 비교하여 경쟁력 있거나 우월한 F1 스코어를 달성하였다.
• 차수 민감도: $k$ 값의 이점은 데이터셋에 따라 달랐다. 저차 카디널리티 네트워크(Alarm1, Insurance)에서는 $k=2$가 성능을 향상시켰다. 고카디널리티 네트워크(Barley, Mildew)에서는 주어진 샘플 크기(5000개)에서 큰 조건부 집합이 CI 테스트의 검정력을 약화시키기 때문에 $k=1$이 종종 더 나은 성능을 보였다.
• 실행 시간: 예상대로 $k$와 네트워크 카디널리티가 증가함에 따라 실행 시간도 크게 증가하였다. 고카디널리티 네트워크의 경우, $k=2$ 설정은 $k=1$이나 베이스라인 방법들에 비해 현저히 느렸다.

의의 및 주장

본 논문은 kOMB를 고차 의존성을 활용함으로써 충실성 위배가 존재하는 상황에서도 MB 발견을 개선할 수 있음을 보여주는 **개념 증명(proof-of-concept)**으로 자리매김한다.

• 완곡한 주장: 저자들은 kOMB가 효율성에 최적화된 것이 아니라, $k$-차수 충실성의 이론적 유용성을 검증하는 것이 주 목적임을 명시적으로 밝히고 있다.
• 실무적 함의: 결과는 패리티 형태의 관계가 포함된 문제나 샘플 크기가 제한적인 상황에서, 충실성 가정을 고차로 완화하는 것이 유익하다는 점을 시사한다.
• 향후 방향: 본 논문은 최악의 경우 계산 비용을 줄이기 위한 근사 알고리즘, 전문가 지식 없이 $k$와 $l$을 선택하는 원칙적인 방법, 그리고 실험에 사용된 G-test 및 SCI 테스트를 넘어선 최신 조건부 독립 테스트의 통합 필요성을 제시한다.

이 연구는 전통적인 충실성 가정이 대개 충분하지만, 특정 구조적 관계(예: 패리티)나 유한 샘플의 현실을 고려할 때 더 유연한 고차 접근 방식이 필요함을 확립한다.