값이 내려가기만 한다면 EM은 어딘가에 도착한다. 그런데 무엇이 도착하는가? 값인가, 파라미터인가? 그리고 그 도착점은 가장 좋은 답인가?
수렴하는 것과 수렴하지 않는 것
단조감소하는 수열이 아래로 유계이면(어떤 값 밑으로는 내려가지 않으면) 수렴한다. x가 이산이면 𝓛 = KL ≥ 0이 하한이므로, 목적함수의 "값"은 수렴한다. 아래 그림은 같은 이야기를 로그우도 ℓ(𝓛에 −를 붙이고 상수를 더한 것)로 그린 것이다. EM 절 파이썬의 데이터(평균 −2와 3인 두 봉우리에서 뽑은 100개)에 두 성분 혼합을 처음 값 두 가지로 맞췄다. 처음 평균을 (0, 1)로 두면 −1.904에서 멈춘다. 두 성분을 똑같이 (0.5, 0.5)에 두면 두 성분이 끝까지 똑같이 움직여, 봉우리 하나짜리 답 −2.367에서 멈춘다. 두 줄 모두 한 번도 내려가지 않았고, 둘 다 "수렴"했다.
파이썬 절의 데이터에 두 성분 혼합을 맞출 때 사이클마다의 평균 로그우도. 처음 평균 (0, 1)에서 시작하면 −1.904 에, 두 성분을 똑같이 (0.5, 0.5)에 두고 시작하면 −2.367 에 멈춘다
여기서 조심할 것이 세 가지다.
첫째, 수렴하는 것은 값이지 파라미터가 아니어서, 값이 멈췄다고 파라미터가 한 점으로 모인다는 보장은 없다. 파라미터의 수렴은 추가 조건 아래에서 따로 증명해야 한다(제프 우, 1983).
둘째, 도착하는 곳은 전역해(가능한 모든 파라미터 가운데 가장 좋은 답)가 아니라 그래디언트가 0인 점(정류점)이다. 대개는 국소 최댓값이지만, 위 그림의 점선처럼 안장점(말안장처럼 어떤 방향으로는 오르막이고 어떤 방향으로는 내리막인, 그래디언트가 0인 점)에 멈출 수도 있다. 초기값에 따라 다른 곳에 도착한다는 것은 아래 위젯에서 리셋을 눌러 보면 바로 보인다.
셋째, 위의 하한 KL ≥ 0은 x가 이산일 때의 이야기라서, 하한이 늘 있는지는 따로 따져야 한다. 키나 몸무게처럼 x가 연속인 데이터에서도 같은 말을 할 수 있는지는 아래 문제 9에서 들여다본다.
속도에 대해서도 한마디. EM이 해 근처에서 얼마나 빨리 다가가는지는 "빠진 정보의 비율"이 정한다(뎀프스터·레어드·루빈, 1977). 완전데이터가 가졌을 피셔 정보(파라미터를 조금 움직일 때 분포가 얼마나 달라지는지 재는 양) 가운데 z를 못 봐서 잃은 피셔 정보의 비율이다. 봉우리들이 많이 겹쳐 z를 추측하기 어려울수록 이 비율이 1에 가까워지고, EM은 느려진다.
직접 움직여 보기
불러오는 중…
한 사이클 안의 풍경
EM의 한 사이클 안에 이 교재의 많은 것이 들어 있다.
분포가 점이고, 결합분포의 공간이 무대다.
목적함수가 KL이다.
두 측지선(m-측지선과 e-측지선)이 두 면의 평탄함이 된다.
F(θ)의 볼록성 덕에 M-스텝의 답이 하나다.
완전데이터 모델이 지수족이면 M-스텝은 모멘트 일치다.
데이터 면과 모델 면이 마주 선다.
수렴 속도는 빠진 피셔 정보의 비율이 정한다.
열어 두기(E)와 확정하기(M)가 번갈아 온다.
EM의 두 스텝은 e-사영과 m-사영이다.
피타고라스가 매 스텝의 감소량을 잰다.
M-스텝의 답이 하나인 것과 EM 전체의 답이 하나인 것은 다르다. 한 스텝 안의 문제는 볼록하지만, 두 변수를 함께 보면 볼록하지 않아서 국소해가 생긴다.
한 알고리즘의 한 스텝을 정직하게 이해하려면 이만큼의 풍경이 필요했다.
이 절의 결론
“EM에서 수렴하는 것은 값이지 파라미터가 아니고, 도착하는 곳은 초기값이 정하는 정류점이다. 값의 수렴도 목적함수가 아래로 유계일 때만 보장된다.”
문제 7. 놀이터의 더 좋은 나눔
1 m, 3 m, 6 m, 11 m 자리의 아이 넷을 선생님 둘이 맡는다. 아이들을 두 모둠으로 나누고 선생님이 모둠의 한가운데에 서면, 아이와 자기 선생님 사이 거리의 제곱을 모두 더한 "거리 제곱합"이 정해진다. (가) 아이 넷을 두 모둠으로 나누는 방법을 모두 따져, 거리 제곱합이 가장 작은 나눔을 찾아라. (나) 선생님 둘이 0 m와 4 m에서 시작해 "가까운 선생님의 모둠에 들기 → 모둠 한가운데로 옮기기"를 번갈아 하면 거리 제곱합 14.50에서 멈춘다. (가)의 답과 같은가? (다) 처음 자리를 5 m와 11 m로 바꾸면 어디서 멈추는가?
1, 3, 6, 11 m 자리의 아이 넷과 두 가지 시작 자리. (나)는 선생님이 0 m와 4 m, (다)는 5 m와 11 m에서 시작한다
함께 풀기
김민준
번갈아 하기는 내려가기만 하니까, 멈춘 14.50이 가장 작은 값이겠죠. {1, 3}과 {6, 11}로 나뉘었어요.
선생님
나누는 방법이 몇 가지나 돼요? 다 세어 볼 수 있겠어요?
이서연
한쪽이 비지 않게 나누면 일곱 가지예요. 다 해 보기 전에… 11 m 아이가 혼자 멀리 있는 게 마음에 걸려요. 11 m만 따로 떼어 볼게요.
어, 그럼 14.50에서는 왜 안 움직였죠? 6 m 아이가 3.33 m 쪽으로 가면 더 좋아지는데요.
선생님
14.50에서 멈췄을 때 선생님은 2 m와 8.5 m에 있었어요. 두 선생님 가운데 6 m 아이에게 더 가까운 선생님은 누구예요?
이서연
8.5 m 선생님이요. 2.5 m 대 4 m.
선생님
그러면 ①에서 6 m 아이는 어디로 가요? ②에서는요?
이서연
①에서는 안 옮겨 가고, 모둠이 그대로니 ②에서도 선생님이 안 움직여요. 두 일 모두 "이 이상 한 번에 나아질 수 없다"고 말하는 자리라 멈춘 거예요. 가장 좋은 자리라서가 아니라요.
김민준
(다)는 5 m와 11 m에서 시작하면 {1, 3, 6}이 5 m 쪽, {11}이 11 m 쪽이 돼서 선생님이 3.33 m와 11 m로 가요. 12.67에서 멈춰요. 시작 자리만 바꿨는데 가장 좋은 나눔에 닿았어요.
이서연
내려가기만 한다는 건 "어딘가에 멈춘다"까지만 말해 주는 거네요. 어디에 멈추는지는 출발점이 정하고요.
문제 8. 초기값이 도착지를 정한다
위 위젯과 같은 데이터를 쓴다. 평균 −3, 0.5, 3.5, 표준편차 0.8, 1.0, 0.6, 혼합 비중 0.35, 0.40, 0.25인 세 봉우리에서 뽑은 200개다. 여기에 세 성분 가우시안 혼합을 EM으로 맞춘다. 초기 평균은 데이터에서 무작위로 세 점을 뽑고, σ = 1, 혼합 비중은 1/3로 둔다. 무작위로 뽑는 방법을 초기값 번호 0~199로 정해 200가지 초기값을 만들고, 각각 EM을 수렴할 때까지(한 사이클에 ℓ이 10⁻⁷보다 적게 오를 때까지) 돌린다. (가) 초기값 7번은 어디에 도착하는가? (나) 200개의 최종 평균 로그우도는 어떻게 나뉘는가? (다) 가장 높은 값에 도착하는 파라미터는 하나뿐인가? 위젯에 초기값 번호를 넣으면 같은 초기값으로 돌려 볼 수 있다.
위젯과 같은 데이터 200개의 히스토그램과, 초기값 7번이 데이터에서 뽑은 처음 평균 셋(−4.83, −2.49, 1.46)
둘이 −3 근처에 몰렸고 하나가 1.3에 있어요. 0.5랑 3.5를 하나가 같이 덮고 있네요. 문제 7(놀이터)에서 선생님 둘이 {1, 3}, {6, 11}로 나뉜 채 멈춘 거랑 같은 모양이에요.
이서연
초기값 탓 아니야? 가우시안 혼합의 로그우도는 로그 안에 정규분포가 있으니까 오목할 것 같아요. 오목하면 극댓값이 곧 최댓값이고 하나뿐이잖아요. 초기값을 바꿔도 같은 데로 가야 해요.
선생님
서연 학생, 성분 1과 성분 2의 이름표를 바꿔 달면 로그우도가 달라져요?
이서연
안 달라져요. 합이니까 순서가 상관없어요.
선생님
그러면 최댓값을 주는 파라미터가 몇 개예요?
이서연
이름표 바꾸기만으로 3! = 6개요.
선생님
아까 말한 대로 엄격하게 오목하다면 최댓값을 주는 점은 몇 개여야 해요?
이서연
하나요. 그런데 여섯 개니까… 오목할 수가 없어요. 로그 안에 합이 있어서 log-sum이 오목성을 깨요.
김민준
그럼 봉우리 사이에 골짜기도 있겠네. 7번 같은 데서 멈출 자리도 생기고.
김민준
200개를 다 돌려 봤어요. 158번은 ℓ = −2.199, 평균 (−3.08, 0.44, 3.42)에 닿았어요. 18번은 −2.197로 조금 더 높은데, 평균 (−3.17, 0.64, 3.51)에 혼합 비중이 많이 달라요. 나머지 24번은 −2.230에서 −2.238 사이이고, 7번처럼 두 성분이 한 곳에 몰렸어요.
선생님
가장 높은 쪽이 200번 중 18번이네요. 그래도 EM 입장에서는 24번도 모두 "수렴"이에요. 값이 더는 안 오르니까요.
김민준
조별 과제에서 첫 회의 때 역할을 잘못 나누면, 매주 조금씩 나아져도 끝까지 그 구조로 가는 거랑 비슷해요. 중간에 판을 다시 짜지는 않으니까.
이서연
수학 수업에서 "미분이 0인 점은 후보일 뿐"이라고 했던 게 이거네요. EM의 단조성은 후보에 도착한다는 것까지만 말해 줘요.
선생님
그럼 실전에서는 어떻게 하면 좋을까요?
김민준
초기값을 여러 개로 돌려서 ℓ이 가장 높은 걸 고르면 되겠네요. 방금 200개 돌린 것처럼요.
이서연
처음부터 좋은 데서 시작하는 방법도 있겠어요. 문제 4의 놀이터 선생님들처럼 점을 가까운 중심으로 나누고 중심을 옮기는 일(k-means라고 부르는 방법)을 먼저 해서, 그 중심을 초기 평균으로 쓰는 거요.
선생님
둘 다 실제로 쓰는 방법이에요.
풀어 본 뒤 위젯에서 확인 → 위 EM 위젯의 「초기값 번호」 칸에 7을 넣고 「불러오기」 단추
문제 9. 무한대로 가는 우도 (킬러)
EM 절 파이썬의 데이터 100개(평균 −2와 3인 두 봉우리에서 뽑은 것)에 두 성분 가우시안 혼합을 맞춘다. 성분 1의 평균을 데이터 한 점 x₁ 위에 놓고 σ₁ → 0으로 보낸다(w₁ = 0.01, 성분 2는 전체 데이터의 평균과 표준편차). (가) 평균 로그우도 ℓ은 어떻게 되는가? (나) 이것은 "EM에서 KL은 단조감소하고 KL ≥ 0이므로 수렴한다"는 본문의 논리와 모순인가? (다) 성분 1을 x₁ 위에 σ₁ = 0.01, w₁ = 0.01로 놓고 EM을 돌리면 어디로 가는가?
파이썬 절의 데이터 100개, 성분 2(혼합 비중 0.99, 전체 평균 0.07과 표준편차 2.58), 데이터 한 점 x₁ = −1.87 위에 세운 성분 1(혼합 비중 0.01). σ₁을 0.04, 0.02, 0.01로 줄여 그렸다
