앞에서는 쇼프로와 K-1이라는, 그나마 그 성격이 확연히 다른 주제를 예로 들었는데,
만약 두 주제의 성격이 다소 비슷한 면이 있다 라고 한다면,
(예를 들면 \'리눅스\' 관련 문서들과 \'윈도우즈\' 관련 문서들)
아래 그림처럼 훨씬 더 골때리는 상황이 생길 수 있어.

(단어 2)
^
|                 o o o
|              o          o o
|           o *     x          o       x
|          o           x x            x 
|                            x   x  x 
|                               
|
-------------------------------> (단어 1)

o = 주제 1에 속하는 문서들
x = 주제 2에 속하는 문서들
* = 쿼리

사용자가 위의 별표와 같은 쿼리를 줬을 때, 올바른 결과라고 하려면
주제 1에 속하는 문서들(그 중에서도 쿼리와 가까이 있는 문서들)이 상위에 올라와야겠지.
그런데 위 그림을 보면, 주제 2에 속하는 문서들 중 몇몇 개가 주제 1의 문서들보다
쿼리에 더 가까이 있기 때문에, 걔들이 상위에 올라가게 된다는 문제가 생기지.

사실 이전 글에 나온 예의 경우, 올바른 분류에 방해가 되는 단어("최홍만")와 도움이 되는 단어("K-1")가 확실히 구분이 되었었고,
따라서 방해가 되는 단어들만 어떻게 잘 찾아낸 다음,
그 단어들의 빈도수는 무시하고 거리를 계산하면 올바른 결과를 얻을 수가 있었어.
하지만 지금 이 예제의 경우는 이런 식의 해결이 불가능하지.

그런데, 위 그림을 보다보면 한 가지 단서가 나와.
그림에서 쿼리 근처 영역만 잘라놓고 보자.

|                 o ←A
|       D→  o
|     C→ o *     x ←B  
|          o 
|                          

일단 그림에서 보듯이 A와 쿼리 사이의 직선 거리는 B와 쿼리 사이의 직선 거리보다 멀지.
그렇지만.. 직선 거리만 보면 그렇지만...
쿼리와 C, 쿼리와 D, C와 D, D와 A의 거리들은
쿼리와 B의 거리보다 가깝지.

이런 점에 착안을 해서 나온 아이디어가 Markov random walk 이라는 건데,
쿼리의 위치에서 시작을 해서 A 또는 B에 도착하게 될 때까지
매 턴마다 랜덤하게 임의의 포인트로 이동을 하는 거야.
단, 각 포인트로 이동하게 될 확률은, 현재 포인트와의 거리가 가까울 수록 큰 것이 핵심.

즉, 현재 위치가 쿼리라면, 다음 턴에 방문하게 될 포인트로는
C가 가장 확률이 높고 그 다음이 D, B, A 순이 되는 거지.
현재 위치가 D라면, 다음에 방문할 포인트로는 A/C/쿼리가 각각 비슷한 확률을 갖고 B는 그보다 좀 작겠지.

그림을 보면, 쿼리에서 시작해서 A까지 갈 수 있는 유망한(= 비교적 높은 확률을 가지는) path들이 몇 개 있지?
쿼리->C->D->A, (확률값은 P(쿼리->C)*P(C->D)*P(D->A))
쿼리->D->A, (확률값은 P(쿼리->D)*P(D->A))
그밖에 되돌아왔다 다시 방문하는 경우들.. (쿼리->C->쿼리->D->A 등등)

결국 쿼리에서 시작해서 이리 저리 포인트를 거쳐 최종적으로 A에 도착할 확률은,
위의 path들 각각의 확률을 모두 더한 것이 될 거야.

반면, 쿼리에서 시작해서 B로 갈 수 있는 유망한 path는 쿼리->B 하나 뿐이지.
쿼리를 제외한 나머지 포인트들과는 거리가 너무 멀어서,
다음 턴에 방문하게 될 확률이 낮으니까.
-> 잘 납득이 안 간다면 곱하기의 성질을 생각해봐.
n개의 값들을 곱한다고 했을 때, 이 중 단 한 개의 값이라도 작으면(예를 들면 0.01)
그 곱셈의 결과는 작아지지.
(반면 덧셈은, n개의 값을 더할 때 이 중 몇 개의 값이 작더라도 결과에 무진장 큰 영향은 안미치고.)
가령 쿼리->C->B 라는 path를 생각해 보면,
이 path를 타고 B까지 갈 확률은 P(쿼리->C)*P(C->B) 가 되겠지.
그런데 이때 P(C->B)가 너무 작기 때문에 이 path 전체의 확률까지 같이 작아져 버리는 거야.
쿼리->A->B, 쿼리->D->B 등등 모두 마찬가지지. 쿼리->B로 직접 가는 경우를 빼고...

즉... 이제 우리는 두 문서간의 유사성을 판단할 때 그들 사이의 직선 거리를 생각하는 대신,
"이 문서에서 Markov random walk을 했을 때 저 문서에 도착할 확률"을 생각하면 되는 거야.

여기서 이런 의문을 가지는 횽아들이 있을 거야.
"A에서 B로 가는 path만 센다고 하더라도 A->B, A->C->B, A->D->B, A->D->C->D->A->B 등등등
무수히 많은 path들이 존재하는데 얘네들 각각의 확률을 어떻게 일일히 다 구해서 더해주나?"

이에 대한 답을 겸해서, 알고리즘을 써 볼께.

1. 우선 각 문서들 사이의 거리를 가지고 기본 확률을 구해야겠지.
즉, d(A,B)가 있을 때 P(A->B)를 정하는데,
이건 보통, 초월함수 e를 이용해서 변환을 해.
P(A->B) = exp(-d(A,B)) / {모든 point들에 대해 exp(-d(A,x))의 합}
(모든 point들에 대한 합으로 나눠주는 이유는,
 A에서 임의의 포인트로 움직일 확률의 전체 합이 1이 되어야 하니까.)

2. n개의 문서가 있다고 하면, 얘들에게 임의의 순서로 차례(index)를 부여 해. 1, 2, ..., n 까지.
그런 다음, K라는 행렬을 정의하는데
K의 i번째 행, j번째 열에 들어갈 원소의 값을 앞에서 구한 P(i번째 포인트 -> j번째 포인트) 로 설정해.

3(핵심). I를 단위행렬(대각선 원소만 1이고 나머지는 다 0인 행렬)이라고 했을 때, 마지막으로
Q = inverse(I - 0.9*K)    (0.9는 예를 들면 그렇다는 거고, 0 초과 1 미만의 값이면 됨)
이렇게 계산을 하면, Q의 i번째 행, j번째 열의 원소값은
i번째 포인트에서 Markov random walk을 해서 j번째 포인트로 도착할 확률,
즉 우리가 구하고자 하는 유사성, 그 값이 나오게 돼.

Q가 왜 이런 값이 나오는지는 위의 역행렬 공식을 테일러 전개해 보면 알 수 있어.
inverse(I - 0.9*K) = I + 0.9*K + 0.9^2*K^2 + 0.9^3*K^3 + ....
이렇게 되거든.

이때 K^n의 i번째 행, j번째 열의 원소값은
i번째 포인트에서 Markov random walk을 했을 때 "정확히 n턴 이후에" j번째 point에 도착할 확률을 나타내.
(I는 K의 0제곱, 즉, 시작 지점에서 아직 전혀 이동을 안한 상태를 의미)
따라서 위 식을 말로 풀어 쓰면
Q = "0턴 이후에 도착할 확률 + 1턴 이후에 도착할 확률 + 2턴 이후에 도착할 확률 + ...."
이렇게 되는 거지.
따라서 모든 가능한 path들의 확률을 빠짐없이 다 더해주는 효과가 있지.
각각의 path를 일일히 세지 않아도 말이지...

요기까지가 본론이야.
이 알고리즘의 장점은, 검색할 데이터의 종류가 특정 응용 분야에 한정되어 있지 않다는 점이지.
문서, 그림, 비디오 등등, 벡터화 할 수 있는 모든 종류의 데이터들의 검색에 모두 쓰일 수 있고,
심지어 벡터화 할 수 없는 데이터라 하더라도(그런게 있나 모르겠지만;;)
임의의 두 아이템의 직선 거리(또는 유사성)만 정의할 수 있으면 이 알고리즘을 쓸 수 있어.

구글의 PageRank 알고리즘은 이 아이디어를 "웹 검색" 이라는 분야에 적용을 한 케이스인거지.
이에 대한 얘기는 다음 글에 쓸께. 이제 정말 마지막이야;