Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise

당신이 탐정이 되어 미스터리를 풀고 있다고 상상해 보세요. 대신 지문 대신 수천 개의 흩어진 단서들, 즉 지도 위의 점들, 사진 속의 픽셀들, 혹은 책 속의 단어들을 가지고 있습니다. 당신의 임령은 이 단서들을 얼마나 비슷하게 생겼는지에 따라 의미 있는 더미로 묶는 것입니다. 이것이 바로 **클러스터링(clustering)**의 핵심입니다. 이는 컴퓨터가 무엇을 찾아야 할지 알려주는 스승 없이도 무질서한 데이터 속에서 숨겨진 패턴을 찾도록 돕는 머신러닝 세계의 초능력입니다.

이 작업을 수행하는 가장 오래되고 유명한 방법 중 하나는 **K-평균(K-means)**이라고 불립니다. 이것을 약간의 변형이 가미된 '의자 뺏기 게임'이라고 생각하세요. 당신은 몇 명의 "캡틴"(중심점)을 뽑고, 모든 데이터 포인트는 자신이 가장 가깝다고 느끼는 캡틴에게 달려갑니다. 그러고 나서 캡틴들은 자신의 새로운 팀의 평균 위치로 이동하고, 사람들은 다시 달려갑니다. 모두가 움직임을 멈출 때까지 이 과정을 반복합니다. 이것은 탐욕적이고 단계적인 과정으로 보통 매우 잘 작동하지만, 수십 년 동안 수학자들은 이 방법이 최적의 해답을 정확히 얼마나 빨리 찾아내는지, 그리고 왜 때때로 루프에 빠져 갇히게 되는지에 대해 머리를 싸매 왔습니다.

여기 프랭크-울프(Frank-Wolfe) 알고리즘이 있습니다. 이는 수학자들이 벽에 부딪히는 기술(이를 "투영"이라 부릅니다)을 사용하지 않고 복잡한 문제를 해결하기 위해 사용하는 또 다른 종류의 최적화 도구입니다. 이것은 마치 언덕 아래로 향하는 가장 가파른 경로를 선택하여, 거대한 발걸음을 내디디며 바닥에 도달할 때까지 내려가는 등산가와 같습니다. 오랫동안 이 두 방법, 즉 K-means와 Frank-Wolfe는 서로 다른 동네에 사는 것처럼 보였습니다. 하지만 한 새로운 논문은 이들이 사실 서로 다른 모자를 쓰고 있는 같은 사람이라고 제안합니다.

---

위대한 폭로: K-means는 변장한 Frank-Wolfe이다

이 논문에서 저자인 마이클 포코조비(Michael Pokojovy), J. 마커스 조브(J. Marcus Jobe), 사이먼 라코스테-줄리앙(Simon Lacoste-Julien)은 로이드의 K-means 알고리즘(모두가 사용하는 표준 버전)이 사실은 프랭크-울프 알고리즘의 특별하고 은밀한 버전임을 보여주며 커튼을 걷어 올립니다.

이 마법을 이해하기 위해, 당신이 거대한 파티를 조직하려고 한다고 상상해 보세요. 당신은 사람들이 같은 음악을 좋아하면 함께 앉을 수 있도록 손님들을 그룹화하고 싶습니다.

• 기존 방식 (K-means): 몇 개의 테이블(중심점)을 정하고, 모두에게 가장 가까운 테이블에 앉으라고 요청한 다음, 그 테이블들을 앉아 있는 사람들의 중심으로 이동시킵니다. 테이블이 더 이상 움직이지 않을 때까지 이를 반복합니다.
• 새로운 통찰: 저자들은 K-means가 테이블을 손님들의 중심으로 이동시킬 때, 수학적으로 프랭크-울프 알고리즘이 언덕 아래로 거대한 발걸음을 내딛는 것과 정확히 똑같은 일을 하고 있다는 것을 깨달았습니다.

이것이 왜 중요할까요? 왜냐하면 프랭크-울프 알고리즘은 수학적으로 "깔끔한" 도구이며 알려진 속도 제한을 가지고 있기 때문입니다. K-means가 파티 모자를 쓴 프랭크-울프라는 것을 깨달음으로써, 저자들은 K-means가 작업을 완료하는 데 정확히 얼마나 걸릴지 증명하기 위해 프랭크-울프의 깔끔한 수학을 사용할 수 있게 되었습니다.

"빈 의자" 문제

K-means 게임에는 한 가지 까다로운 부분이 있습니다. 때때로 테이블에 아무도 앉지 않게 되는 경우가 발생합니다. 파티 비유에서, 모든 사람이 다른 테이블로 달려갔기 때문에 캡틴이 혼자 서 있게 될 수도 있습니다. 수학적 용어로, 이는 프랭크-울프가 보통 굴러 내려가는 매끄러운 언덕에 "틈"이나 거친 부분을 만듭니다.

저자들은 이 문제를 무시하지 않았습니다. 대신 정면으로 맞섰습니다. 그들은 이러한 "빈 의자" 순간(그들은 이를 세미스무스(semismooth) 목적 함수라고 부릅니다)을 처리할 수 있는 더 유연한 새로운 버전의 프랭크-울프 알고리즘을 개발했습니다. 그들은 클러스터가 비어 있을 때조차 알고리즘이 혼란에 빠지거나 느려지지 않는다는 것을 증명했습니다. 알고리즘은 이전처럼 효율적으로 계속 언덕을 내려갑니다.

얼마나 빠른 것이 빠른 것인가?

가장 흥ende로운 발견은 속도입니다. 저자들은 K-means 알고리즘이 **O(1/t)**의 속도로 좋은 해답으로 수렴한다는 것을 증명했습니다.

이를 간단한 비유로 풀어보겠습니다. 당신이 보물 상 chests를 향해 걷고 있다고 상상해 보세요.

• 만약 당신이 **O(1/√t)**의 속도로 걷는다면, 처음에는 큰 발걸음을 내딛겠지만, 마치 진흙탕 속을 헤치고 나가는 것처럼 발걸음이 매우 빠르게 작아질 것입니다.
• 하지만 K-means는 실제로 프랭크-울프이기 때문에 **O(1/t)**의 속도로 걷습니다. 이는 당신의 발걸음이 작아지기는 하겠지만, 훨씬 더 예측 가능하게 보물에 가까워질 것임을 보장한다는 의미입니다.

결정적으로, 저자들은 이 속도가 최적의 해답으로부터 얼마나 멀리 떨어져 있는지에만 의존한다는 것을 보여주었습니다. 데이터 포인트가 백만 개(거대한 파티)이든 단 몇 개이든 상관없습니다. 속도 보장은 그대로 유지됩니다. 이는 이전의 이론들이 데이터 포인트의 수가 늘어날 때 매우 복잡하고 난해해졌던 것과 대조되는 큰 성과입니다.

이론 검증

이것이 단순히 예쁜 수학적 기교가 아님을 확인하기 위해, 팀은 대규모 시뮬레이션을 실행했습니다.

• 그들은 점들이 "덩어리"(색색의 종이 꽃가루 구름 같은) 형태를 띠는 가짜 데이터를 만들고 K-means 알고리즘을 수천 번 실행했습니다.
• 또한, 하늘, 잔디, 건물을 분리하기 위해 사진의 픽셀을 그룹화하는 것을 목표로 하는 **이미지 분할(image segmentation)**의 실제 데이터셋에서도 테스트했습니다.

모든 테스트에서 알고리즘이 위치한 곳과 도달하고자 하는 곳 사이의 "간격"은 수학이 예측한 대로 정확히 줄어들었습니다. 결과를 그래프에 그렸을 때, 선은 -1.0의 기울기로 내려갔는데, 이는 O(1/t) 속도의 수학적 서명입니다. 데이터가 무질서하거나 클러스터의 모양이 이상하더라도 알고리즘은 침착함을 유지했습니다.

알고리즘을 멈추는 새로운 방법

가장 실용적인 시사점 중 하나는 파티를 언제 멈출지 아는 방법입니다. 보통 컴퓨터는 중심점이 거의 움직이지 않을 때 K-means를 멈춥니다. 하지만 저자들은 더 나은 방법을 제안합니다. "프랭크-울프 간극"(현재의 배치와 다음 가능한 배치 사이의 점수 차이)이 충분히 작아질 때 멈추는 것입니다.

이 새로운 중단 규칙은 남은 "작업량"이 정확히 얼마인지 알려주는 연료 게이지를 갖는 것과 같습니다. 이는 추측하는 것보다 더 신뢰할 수 있으며, 알고리즘이 수행해야 할 단계의 상한선을 명확히 제시합니다.

결론

이 논문은 새로운 K-means 방식을 발명한 것이 아닙니다. 대신 우리가 수십 년 동안 사용해 온 신뢰할 수 있는 기존 방식이 강력하고 현대적인 수학적 도구의 변장한 모습임을 밝혀낸 것입니다. 이 두 세계를 연결함으로써, 저자들은 K-means에 대한 명확하고 증명된 속도 제한을 제공하고 작업이 완료되었음을 알리는 더 나은 방법을 제시했습니다. 이는 때때로 과학계에서 가장 친숙한 도구들이 우리가 생각했던 것과는 다른 의상을 입고 있다는 사실을 일깨워줍니다.