Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization

이 논문은 **유한 에르고드 다변량 마르코프 체인 (Multivariate Markov Chains)**의 전이 행렬을 저차원 상태 공간으로 최적 투영하거나, 좌표의 최적 분할 (partition) 을 찾아 원래 체인에 비해 정보 손실이 최소화되도록 하는 문제를 연구합니다. 저자들은 이러한 문제를 **서브모듈러 최적화 (Submodular Optimization)**의 관점에서 접근하여, 다양한 정보 이론적 기준 (엔트로피율, 분해 가능성 거리, 독립성, 정상성 등) 하에서 최적의 부분집합 또는 분할을 선택하는 효율적인 알고리즘을 제안합니다.

주요 내용은 다음과 같습니다.

1. 연구 문제 (Problem Statement)

다변량 마르코프 체인의 $d$개 좌표 중 일부 좌표 집합 $S$를 선택하거나, 좌표를 $k$개의 그룹으로 분할할 때, 다음과 같은 정보 이론적 목적 함수를 최적화하는 문제를 다룹니다.

• 엔트로피율 (Entropy Rate) 최대화: 투영된 전이 행렬 $P(S)$의 엔트로피율을 최대화하여 가장 "무작위성"이 높은 좌표 집합을 찾습니다.
• 분해 가능성 거리 (Distance to Factorizability) 최적화: 원래 전이 행렬 $P$를 좌표 분할에 따라 분해된 모델로 근사할 때 발생하는 정보 손실 (KL 발산) 을 최소화하거나, 반대로 분해된 모델과 원래 모델의 거리를 최대화하는 분할을 찾습니다.
• 독립성 거리 (Distance to Independence) 최소화: 투영된 체인이 독립적인 마르코프 체인에 얼마나 가까운지 (또는 먼지) 를 측정하여, 독립성에 가까운 부분집합을 찾습니다.
• 정상성 거리 (Distance to Stationarity) 최적화: 투영된 체인이 정상 분포에 얼마나 빠르게 수렴하는지 (또는 멀어지는지) 를 측정하여, 평형 상태와 가장 먼 (또는 가장 가까운) 좌표 집합을 식별합니다.

이러한 선택 문제는 조합 최적화 문제로, 좌표의 개수 (cardinality) 에 대한 제약 조건 하에서 수행됩니다.

2. 방법론 (Methodology)

저자들은 위 목적 함수들이 서브모듈러 (Submodular) 또는 슈퍼모듈러 (Supermodular) 구조를 가진다는 것을 증명하고, 이를 활용하여 효율적인 탐욕 알고리즘 (Greedy Algorithms) 을 설계합니다.

• 서브모듈러성 및 k-서브모듈러성 분석:
  • 엔트로피율, 분해 가능성 거리 등은 서브모듈러 함수임을 보였습니다.
  • 독립성 거리, 정상성 거리 등은 슈퍼모듈러 함수임을 보였으며, 이는 부호를 반전시키거나 여집합을 취함으로써 서브모듈러 문제로 변환 가능함을 증명했습니다.
  • 좌표 분할 (Partition) 문제는 k-서브모듈러 (k-submodular) 최적화 문제로 확장하여 다루었습니다.
• 왜곡된 탐욕 알고리즘 (Distorted Greedy Algorithm) 의 일반화:
  • 기존 탐욕 알고리즘은 목적 함수가 단조 증가 (monotonically non-decreasing) 일 때만 이론적 보장이 있습니다. 그러나 본 문제의 많은 목적 함수는 단조 증가하지 않습니다.
  • 이를 해결하기 위해, 비단조 서브모듈러 함수를 단조 서브모듈러 함수와 모듈러 함수의 차이로 변환하는 기법을 도입했습니다.
  • 이를 바탕으로 **k-서브모듈러 최적화를 위한 일반화된 왜곡된 탐욕 알고리즘 (Generalized Distorted Greedy Algorithm)**을 제안했습니다. 이 알고리즘은 선택된 부분집합의 크기에 대한 제약 조건 하에서 $(1 - e^{-1})$ 근사 비율을 가진 이론적 하한을 보장합니다.

3. 주요 기여 (Key Contributions)

1. 마르코프 체인 이론에서의 새로운 서브모듈러 함수 식별: 엔트로피율, 분해 가능성, 독립성, 정상성과 관련된 다양한 함수들이 서브모듈러 또는 슈퍼모듈러 구조를 가진다는 것을 rigorously 증명했습니다.
2. 마르코프 체인을 위한 서브모듈러 최적화 기반 선택 알고리즘: 기존에 연구되지 않았던 마르코프 체인의 좌표 부분집합/분할 선택 문제를 서브모듈러 최적화 프레임워크로 체계화하고, 이론적 보장이 있는 탐욕 알고리즘을 적용했습니다.
3. 일반화된 왜곡된 탐욕 알고리즘 개발: k-서브모듈러 최적화 문제 (좌표 분할 문제) 에 대해, 모듈러 함수와의 차이를 최대화하는 새로운 알고리즘을 제안하고 이론적 근사 비율을 증명했습니다. 이는 마르코프 체인 응용을 넘어 k-서브모듈러 최적화 분야 자체에도 기여합니다.
4. 수치적 검증: 베르누이 - 라플라스 (Bernoulli-Laplace) 모델과 큐리 - 바이스 (Curie-Weiss) 모델을 사용하여 제안된 알고리즘의 성능을 검증했습니다.

4. 실험 결과 (Results)

• 모델: 베르누이 - 라플라스 모델 (입자 이동 모델) 과 큐리 - 바이스 모델 (자기 모델) 을 사용하여 10 차원 이상의 다변량 마르코프 체인을 생성했습니다.
• 성능 비교: 제안된 왜곡된 탐욕 알고리즘과 일반화된 왜곡된 탐욕 알고리즘이 기존의 단순 탐욕 알고리즘 (Heuristic Greedy) 보다 종종 더 좋은 목적 함수 값을 달성하거나, 동등한 성능을 보임을 확인했습니다.
  • 특히 엔트로피율 최대화 및 독립성 거리 최소화 문제에서 제안된 알고리즘이 일관되게 우수한 결과를 보였습니다.
• MCMC 샘플링 개선 사례: 큐리 - 바이스 모델에서 정상성에 가장 먼 좌표를 식별하여, 해당 좌표를 분리하고 나머지 좌표는 빠르게 수렴하는 투영된 체인으로 처리하는 **분해형 샘플러 (Factorized Sampler)**를 제안했습니다. 이 방법은 기존 단일 체인보다 더 빠른 수렴 속도와 더 낮은 총변동 거리 (Total Variation Distance) 를 보여주어 MCMC 효율성을 개선할 수 있음을 입증했습니다.

5. 의의 및 중요성 (Significance)

• 계산적 효율성: 스펙트럼 이론 (고유값/고유벡터 계산) 에 의존하는 기존 모델 축소 방법과 달리, 전이 행렬의 구조만 알면 계산 가능한 조합 최적화 접근법을 제시하여 고차원 문제에서도 적용 가능성을 높였습니다.
• 이론적 엄밀성: 정보 이론적 기준을 최적화하는 문제에 대해 근사 비율이 보장된 알고리즘을 제공함으로써, 마르코프 체인 분석에 대한 수학적 기반을 강화했습니다.
• 실용적 응용: MCMC 샘플러 가속화, 모델 축소, 특징 선택 (Feature Selection) 등 다양한 분야에서 다변량 마르코프 체인의 구조를 이해하고 효율적으로 처리하는 데 직접적으로 활용될 수 있습니다.

요약하자면, 이 논문은 다변량 마르코프 체인의 복잡한 구조를 정보 이론적 관점에서 분석하고, 서브모듈러 최적화 기법을 통해 계산적으로 효율적이고 이론적으로 보장된 최적 부분집합/분할 선택 알고리즘을 개발했다는 점에서 중요한 의의를 가집니다.