Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering

당신이 데이터의 긴, 연속적인 흐름, 마치 센서를 지나 흘러가는 강물을 보고 있다고 상상해 보십시오. 때때로 물의 성질이 변합니다. 물이 따뜻해지거나, 강바닥의 바위가 움직이거나, 속도가 변할 수도 있습니다. 데이터 과학의 세계에서 이러한 순간들을 **변화점(change points)**이라고 부릅니다. 변화점을 찾는 것은 강물이 완만한 시냇물에서 거친 급류로 변하는 정확한 지점을 포착하는 것과 같습니다.

오랫동안 과학자들은 이러한 변화를 찾기 위한 훌륭한 도구 상자를 가지고 있었지만, 그 도구들은 데이터의 낙차가 서로 독립적일 때, 즉 마치 무작위로 떨어지는 빗방울처럼 서로 영향을 주지 않을 때만 완벽하게 작동했습니다. 하지만 현실 세계의 데이터는 종종 **의존적(dependent)**입니다, 마치 마르코프 체인(Markov chain)처럼 말이죠. 마르코프 체인을 '전화기 게임(telephone game)'에 비로요 비유해 본다면, 다음 메시지는 방금 들은 메시지에 전적으로 달려 있습니다. 강물이 요동치고 있다면, 다음 물보라는 이전의 물보라에 의존하게 됩니다. 기존의 도구들은 여기서 어려움을 겪었으며, 종종 잘못된 추측을 하거나 탐색을 시작하기 전에 변화가 몇 번이나 일어날지 미리 알아야만 했습니다.

이 논문은 이러한 의존적인 데이터에서 정답을 미리 알 필요 없이 변화를 찾아내는 새롭고 영리한 방법을 소개합니다. 이들이 어떻게 해냈는지, 이야기를 나누듯 쉽게 풀어보겠습니다.

기존 도구들의 문제점

저자들은 기존의 많은 방법이 마치 용의자가 정확히 몇 명인지 알려주기 전까지는 사건을 해결하기를 거부하는 탐정과 같다고 지적합니다. 또한 그들은 데이터가 독립적이라고 가정하는 경우가 많은데, 이는 기후 패턴이나 네트워크 트래픽처럼 오늘의 데이터가 어제의 데이터에 크게 영향을 받는 현상을 설명하기에는 큰 무리가 있습니다.

PELT(Pruned Exact Linear Time)라고 불리는 한 가지 인기 있는 방법은 매우 빠르지만, 저자들은 이 방법의 결함을 발견했습니다. PELT는 '유령'을 보는 경향이 있다는 것입니다. 실험 결과, 실제 강물에는 3번의 변화가 있었음에도 불구하고, PELT는 데이터 스트림의 길이에 따라 7, 8, 9, 심지어 26번의 변화를 찾아냈습니다. 이는 과잉 분할(over-segmentation)을 일으켜, 강물을 불필요하게 잘게 쪼개버리는 결과를 초래합니다.

새로운 해결책: 적응형 클러스터링(Adaptive Clustering)

저자들은 스마트하고 적응력이 뛰어난 분류기처럼 작동하는 방법을 제안합니다. 당신이 일렬로 흐르는 거대한 색깔 구슬 더미(당신의 데이터 포인트들)를 가지고 있다고 상상해 보십시오. 당신은 색깔이 몇 종류인지, 혹은 색이 어디서 변하는지도 모릅니다.

그들의 방법은 구슬들을 '클러스터'(세그먼트)로 그룹화하려고 시도하며, 이때 각 그룹 내부의 구슬들이 최대한 서로 유사하도록 만듭니다. 그들은 '유사성'을 **클러스터링 분산(clustering variance)**이라는 개념을 사용하여 측정합니다. 분산을 '혼돈(chaos)의 척도'라고 생각해 보십시오. 빨간 구슬과 파란 구슬을 한 양동이에 섞으면 혼란스럽습니다. 하지만 빨간 구슬만 들어있는 양동이는 평온합니다. 목표는 혼돈이 최소화되는 방식으로 강물을 양동이(구간)로 나누는 것입니다.

의존적인 데이터(전화기 게임)에 대해 이 방법이 작동하게 만들기 위해, 그들은 새로운 수학적 안전망을 발명해야 했습니다. 그들은 마르코프 체인을 위해 특별히 설계된 드보레츠키-키어퍼-울프위츠(DKW) 부등식을 증명했습니다. 쉬운 말로 풀이하자면, 이것은 "데이터 포인트들이 서로 대화를 나누고 있을지라도, 우리가 충분히 기다리기만 한다면 우리의 추정치는 진실에 매우 가까울 것이다"라는 보증을 의미합니다.

증명: 그들이 실제로 찾아낸 것

이 논문은 단순히 추측하는 것이 아니라, 수학적으로 증명하고 시뮬레이션을 통해 테스트했습니다.

1. 수학적 원리: 그들은 '혼돈'(분산)을 최소화하면서 동시에 너무 많은 양동이를 만드는 것에 대해 작은 페널티를 부여하면, 결국 정확한 변화의 횟수와 그 정확한 위치를 찾게 된다는 것을 보여주었습니다. 그들은 변화의 횟수가 데이터가 길어짐에 따라 늘어나더라도 이 방법이 작동한다는 것을 증명했습니다.
2. 시뮬레이션: 그들은 250개의 시점(time points)을 가진 가상의 강물을 만들었습니다 (각 구간의 길이는 25, 75, 150, 25 포인트).
   • 결과: 그들의 새로운 방법은 변화가 일어난 지점인 25, 75, 150을 정확히 찾아냈습니다. 완벽했습니다.
   • 경쟁 모델: PELT 방법은 변화를 25, 37, 46, 72, 151, 161, 176, 204에서 찾아냈습니다. 실제 변화는 3번인데, PELT는 8번의 변화를 찾아냈습니다.
3. 속도 대 정확도: 저자들은 또한 이 문제를 해결하기 위한 컴퓨터 프로그램("혼합 정수 이진 정식화", mixed-integer binary formulation)을 구축했습니다. 그들은 계산을 훨씬 빠르게 만드는 수학적 기법인 "이선형 재정식화(bilinear reformulation)"를 찾아냈습니다.
   • 250개의 데이터 포인트에 대해, 그들의 빠른 방법은 9.43초가 걸렸습니다.
   • PELT 방법은 단 0.35초밖에 걸리지 않았습니다 (가장 빠릅니다). 하지만 틀렸습니다.
   • 그들의 느린 원래 방법은 30.42초가 걸렸지만, 역시 완벽했습니다.

이 논문이 주장하지 않는 것

이 논문이 무엇을 말하지 않는지 아는 것도 중요합니다.

• 이 방법이 모든 가능한 유형의 데이터에 작동한다고 주장하는 것이 아닙니다. 그들은 특히 '재생 마르코프 체인(regenerating Markov chain)'(가끔 스스로 초기화되는 특정 유형의 의존적 데이터)처럼 행동하는 데이터에 집중하고 있습니다.
• 이 방법이 다변량(multivariate) 데이터(여러 변수가 동시에 존재하는 데이터) 문제를 해결했다고 주장하는 것도 아닙니다. 그들은 이를 다차원으로 확장하는 것이 여전히 "열린 문제(open question)"라고 명시했습니다.
• 이 방법이 세상에서 가장 빠르다고 주장하는 것도 아닙니다. 그들은 PELT가 더 빠르다는 점을 인정하지만, 가짜 변화를 찾아내고 있다면 속도는 중요하지 않다고 주장합니다.

핵심 요약

저자들은 정답을 미리 알 필요 없이 의존적인 데이터 스트림에서 여러 번의 변화를 찾아낼 수 있는 엄격한 비매개변수적(nonparametric) 도구를 구축했습니다. 그들은 수학적으로 이 방법이 작동함을 증명했고, 시뮬레이션을 통해 기존의 인기 있는 방법들이 너무 많은 변화를 찾아내어 실패하는 지점에서 이 방법이 어떻게 진정한 변화를 찾아내는지 보여주었습니다.

비록 그 배후의 수학에는 "라데마허 복잡도(Rademacher complexities)"나 "오를릭 노름(Orlicz norms)" 같은 복잡한 개념들이 포함되어 있지만, 결과는 단순합니다. 만약 과거가 미래에 영향을 주는 데이터 스트림을 가지고 있다면, 이 새로운 방법은 그것을 올바르게 나누어 줄 수 있습니다. 반면 기존의 빠른 방법들은 데이터를 종이 꽃가루처럼 잘게 쪼개버릴 수도 있습니다. 저자들은 향에 "포아송 집중(Poissonian concentration)"에 관한 특정 수학적 퍼즐을 풀 수 있다면, 데이터의 "꼬리(tails)" 부분의 변화를 포착하는 능력을 더욱 개선할 수 있을 것이라고 제안합니다. 하지만 현재로서는, 이것은 견고하고 입증된 진전입니다.