희소 숄레스키 분해를 이용한 베이즈 네트워크 추정 = Learning Bayesian Networks using Sparse Cholesky Decomposition

국문 초록 (Abstract)

본 논문에서는 초고차원 환경에서도 확장 가능한 베이즈 네트워크 추정 기법을 제안한다. 기존의 scale-Free bayesian network learning with RObust Selection Tuning and sparse choleskY (FROSTY) 알고리즘은 정밀도 행렬 추정을 위한 그래픽 라쏘와 방향성 추정을 위한 희소 순열 기반 숄레스키 분해 단계를 통해 대규모 데이터에서의 베이즈 네트워크 학습을 가능하게 한다. 그러나 수십만 개 이상의 변수를 포함하는 데이터에서는 메모리 및 계산 자원의 제약으로 인해 적용이 어려운 한계를 가진다. 본 연구에서는 이러한 문제를 해결하기 위해 FROSTY의 두 단계를 각각 개선한다. 먼저, 정밀도 행렬 추정을 위해 초고차원 환경에 적합한 High Performance computing implementation of Assymetric Convex CORrelation selection metho (HP-ACCORD) 방법론을 도입하고, 방향성 추정 단계에서는 다양한 발견적(heuristic) fill-in 최소화 알고리즘을 비교하여 우수한 기법을 제안한다. 뿐만 아니라, 본 연구에서는 사전 정보를 효과적으로 반영할 수 있는 순열 추정 알고리즘을 제안함으로써, 기존에 알려진 인과 구조를 기반으로 파생되는 미지의 인과 관계를 보다 정교하게 추정할 수 있는 가능성을 제시한다. 제안하는 방법은 합성 네트워크, 초고차원 다중 오믹스 데이터를 비롯한 실제 네트워크에 적용되어 정확도와 계산 효율성 측면에서 기존 기법 대비 우수한 성능을 보임을 확인하였다.

다국어 초록 (Multilingual Abstract)

This study proposes a scalable Bayesian network estimation method tailored for ultrahigh-dimensional settings. The existing FROSTY algorithm enables Bayesian network learning for large-scale data by estimating the precision matrix via graphical lasso and determining causal directions using a sparse permutation-based Cholesky decomposition. However, its applicability is limited when handling datasets with hundreds of thousands of variables due to memory and computational constraints. To address this, we improve both stages of the FROSTY algorithm. For precision matrix estimation, we adopt HP-ACCORD, an algorithm designed for ultrahigh-dimensional scalability. For causal structure estimation, we propose a novel permutation inference strategy that incorporates various heuristic fill-in minimization techniques as well as domain-specific prior knowledge. Furthermore, we introduce a prior-aware permutation estimation framework that enables more accurate inference of unknown causal relations based on established causal structures. The proposed method was applied to synthetic networks as well as real-world networks, including ultra-high-dimensional multi-omics datasets, and demonstrated superior performance in terms of both accuracy and computational efficiency compared to existing approaches.

목차 (Table of Contents)

• 국문초록 i
• 제 1 장 서론 5
• 제 2 장 배경 8
• 2.1 확률적 그래프 모델 8
• 2.2 가장 희소한 순열을 찾는 알고리즘 10
• 2.3 정규 비순환 유향그래프 모델에서의 SP 알고리즘 12
• 제 3 장 정밀도 행렬을 추정하는 방법 14
• 3.1 그래픽 라쏘 14
• 3.2 HP-ACCORD 15
• 제 4 장 가장 희소한 숄레스키 인자를 찾는 발견적 방법 17
• 4.1 최소 차수 알고리즘 17
• 4.1.1 근사적 최소 차수 알고리즘 21
• 4.1.2 열 기반 근사적 최소 차수 알고리즘 22
• 4.2 중첩된 분할 알고리즘 22
• 4.2.1 다중 단계 그래프 분할 알고리즘 22
• 4.3 사전 정보를 활용한 위상 깊이 기반의 알고리즘 24
• 제 5 장 실험 26
• 5.1 실제 네트워크와의 비교 26
• 5.1.1 순서 찾기 알고리즘에 따른 차이 27
• 5.1.2 베이즈 네트워크 추정 방법론에 따른 차이 33
• 5.2 확장성 39
• 5.2.1 변수의 개수에 따른 실행 시간 비교 39
• 5.2.2 스레드 개수에 따른 SP 알고리즘 소요 시간 비교 40
• 5.2.3 프로세스 개수에 따른 소요 시간 비교 41
• 5.2.4 단일 GPU 성능 42
• 5.3 간암 관련 다중 오믹스 데이터 분석 44
• 5.3.1 유전자 발현 조절인자 간의 관계 44
• 5.3.2 메틸화가 유전자 발현량으로 주는 영향 47
• 제 6 장 결론 48
• ABSTRACT 53
• 감사의 글 54