HMM2, 도둑 위치 추적

 

 

히든 마코프에 들어가기 전에 언론에 나온 “인공지능으로 범인을 추적할 수 있다” 기사에 대해 조금 알아 보죠.

 

진짜 천재들 빼고는 어려운 분야는 저도 마찬가지지만 일반 사람들은 현실에서 실제 어떻게 응용되는지에 대한 구체적인 예가 없으면 이해하기 힘듭니다. 그래서 HMM에서 나온 범인추적의 예를 간단하게 설명하겠습니다. 앞에서도 이야기해지만 이런 것은 아직 교과서적인 예입니다. 비현실적인 가정들이 많이 있다는 것이죠.

 

 

상황은 이렇습니다.

 

집주인에 밤에 2층에서 잠을 자고 있는데 아래층에 도둑이 들어왔습니다. 집주인을 관찰하는 변수 V(visual)는 아래층의 도둑이 움직일 때 아래층에서 삐끗하는 소리와 다른 물체와 부딪치는 소리 2개입니다. 즉 V=(V1, V2) 두 개의 변수로 되어 있고, 집 주인은 일정 간격으로 10번 측정합니다.

 

 

 

 

 

 

 

여기서 노란색은 소리를 못들은 것이고 갈색은 소리를 들은 것이라 생각하면 됩니다. 반대로 생각해도 되고요. 상관없죠. 어차피 실제 데이터가 아니고 가공데이타이니까요. 그래서 처음 집주인이 들은 (비끗, 쿵)=(0, 1), 두 번째 들은 소리는 (비끗, 쿵)=(1, 0)이 됩니다. 0은 소리를 못들은 것이고, 1은 소리를 들은 것이라 하죠.

 

 

관심은 이 2개의 소리를 듣고 범인이 어떤 위치에 있는가 하는가입니다. 그래서 보이지 않은 변수 H(hidden)은 범인의 위치입니다. 1층 바닥은 5*5의 격자모양(grid)로 나눕니다. 그래서 H도 두 개의 변수가 됩니다. H=(H1, H2) 여기서 H1은 앞뒤방향, H2는 위아래 방향으로 설정이 되고 H1이나 H2가 취할 수 있는 값은 1부터 5가 되겠죠.

 

여기서 한 가지 제한 조건은 도둑이 앞이나 뒤나 또는 위로, 아래로 한 단계식만 움직인다는 것이죠. 즉, 4개의 방향으로 한 단계식만 움직인다는 것을 가정합니다. 점프는 안되고요. 현실적인 전제라고 볼 수 있지만 45도로 움직이는 것은 금지하는데 이건 좀 비현실적인 가정이라 볼 수 있습니다.

 

이와 같이 움직이는 것은 전형적인 마코프 체인이라 할 수 있습니다. 현재 도둑의 위치는 이전 상태에만 영향을 받기 때문입니다. Barber 책에서는 여기서 풀어야 할 문제를 3개 제시했습니다. 아래 그림에서 흰색이 도둑의 위치입니다.

 

 

 

 

 

위의 fitering, smoothing, Viterbi가 우리가 풀어야 할 문제이고 맨 마지막은 진짜 도둑이 진행한 위치입니다. 그래서 위의 세 개의 해답이 아래 진짜 도둑의 위치와 비슷하면 이 HMM 모형이 잘 적용되었다고 할 수 있죠.

 

 

 

그럼 위의 세가지 문제가 어떻게 다른지 이해를 좀 해야 합니다. fitering은 집주인의 입장에서 추측입니다. 즉 현재 5시점까지 삐끗과 쿵 소리를 들었을 때 도둑이 현재 5시점에서 바닥 어디에 있는가 하는 문제입니다.

 

 

이런 문제는 인공지능에서 온라인(online)이라고 합니다. 새로운 데이터 정보가 실시간에 하나씩 들어올 때 마다 판단을 한다는 것이죠. 이와 반대되는 개념은 배치(batch)라고 합니다. 이건 데이터를 다 본 후 전체 데이터를 가지고 처리하는 것입니다. 기존의 통계 분석은 batch 형식입니다.

 

 

예를 들어 이런 문제입니다. 국제회의에서 동시통역을 한다고 하죠. 이건 거의 실시간으로 통역을 해야 합니다. 또 중요한 기상 예보도 실시간에 들어오는 새로운 정보에 따라 바로 판단을 해야 합니다. 또 무인자동차도 실시간 정보를 가지고 즉각적으로 판단을 해야 합니다.

 

그러나 팟캐스터에서 사람들이 이야기한 것을 문자로 번역하는 것은 실시간으로 할 필요가 없지요. 다 녹음 한 후 문자로 전환해서 기사에 올리면 됩니다. 그 만큼 긴박한 상황이 아니죠. 또 국회에서 발언 기록 같은 것도 구태여 실시간에 기록할 필요가 없습니다. 말한 것 전부 다 녹음 떠서 이걸 문자로 번역해 주면 됩니다.

 

다음의 2번과 3번 문제는 배치(batch) 문제입니다.

 

 

두 번째 smoothing은 집주인도 될 수 있고, 수사관의 입장도 될 수 있습니다. 신고를 받고 수사관이 와서 집주인에게 마지막인 10시점까지 (삐긋, 쿵)에 관한 정보를 다 듣습니다. 그리고 1시점부터 10시점까지 특정 시점에서 도둑이 있을 가능성을 판단하는 것입니다.

 

 

이 두 번째 문제가 세 번째 문제 Viterbi 문제와 조금 헷갈리수가 있습니다. 세 번째도 상황은 비슷합니다. 수사관이 10시점까지 모든 정보를 집주인에게 듣습니다. 그리고 전체적으로 도둑이 1시점부터 10시점까지 움직일 가능성이 제일 높은 경로를 판단하는 문제입니다.

 

두 번째 문제는 local 한 문제입니다. 세 번째 문제는 global한 문제입니다. 두 번째 답을 모은 것이 세 번째 답이 될 수가 없습니다. 예를 들어 두 번째 문제에서 1시점에서 도둑이 (1,4)의 위치에 있을 가능성이 제일 높다고 나왔다고 하고, 2 시점에서 도둑이 (3,4)의 위치에 있을 가능성이 제일 높다고 하죠. 그러나 (1,4)==>(3,4)로 가는 것은 불가능하죠. 전제로 한 단위만 움직인다고 했으니까요.

 

 

이렇게도 생각할 수 있습니다. A와 B 두 소비자가 X, Y라는 물건을 샀을 때 효용을 생각해보죠.

소비자	X	Y	전체
A 소비자	3	1	4
B 소비자	2	4	6

 

X 물건에서 가장 높은 효용은 3이고 Y에서 가장 높은 효용은 4입니다. 그러나 전체적으로 보면 B 소비자의 효용이 A보다 훨씬 높습니다. B 소비자는 로칼하게 X에서 최고의 효용이 아니지만 전체적인 (X, Y)로 보면 B 소비자가 A보다 효용이 훨씬 높게 나온다는 것이죠.

 

대부분 우리의 관심은 Viterbi 문제를 해결하는 것입니다. 그런데 이 Viterbi 문제를 통계학에서 많이 나오는 EM 알고리즘을 쓴다고 하네요. 그래서 다시 한번 EM 알고리즘에 대해, 이번에는 좀 자세히 쓰려고 합니다.

 

그런데 이런 삐끗과 쿵하는 소리만 듣고 어떻게 저걸 푼다는 것이죠. 이미 사전에 바닥 5*5의 격자에서 각 위치에서 비끗할 확률, 쿵할 확률를 알고 있다고 전제를 하기 때문입니다. 이것도 좀 비현실적이죠.

 

 

이와 비슷한 문제를 생각해 볼 수 있습니다. 살인 사건이 났습니다. 해당 지역을 위처럼 격자로 나누고, 이 지역에 있는 CCTV에서 범인이 찍혔는지, 안찍혔는지 확인을 한다는 것이죠. 이게 관찰 변수 H가 되는 것이고요. 이 관찰 변수를 보고 범인의 이동 행로를 추정한다는 것이죠.

 

또 EPL 축구보면 경기에서 축구 선수가 움직이는 동선을 파악한 그림들이 나옵니다. 뛴 거리도 통계로 나오고요. 이것도 게임 동영상을 보고 한 50개의 이미지를 채취합니다. 그래서 이 50개의 이미지를 가지고 각 선수가 움직인 경로를 판단한다는 것이죠. 이게 되는지 잘 모르겠습니다. 전에는 선수 축구화 바닥에 전자칩을 다는 것이 아닐까 생각했는데요. 요새는 그런 것을 많이 하니까요.