검색엔진 : Vector space Model

이 문서는 수정될 수 있습니다. 최신문서는 Joinc Wiki에서 확인하세요.

term vector model이라고도 불리우는 Vector space model은 정보필터링, 문서내에서의 정보검색, 색인과 유사도를 계산하기 위한 수학모델로, 다차원 선형공간에서의 Vector 정보를 이용해서 자연어를 포함한 문서의 중요도를 분석하기 위한 방법을 제시한다. 이 모델은 SMART Information Retrieval System에서 가장 먼저 언급되었다.

문서는 색인단
어의 vector로 나타낼 수 있을 것이고, 문서의 유사도는 Vector에 위치하 단어들간의 거리로 계산해낼 수 있을 것이다
라는게 이 모델의 대전제다. vector에 위치한 단어들의 유사도는 다음과 같은 간단한 삼각공식으로 나타낼 수 있다.

TF - IDF 모델

Vector Space Model을 사용하기 위해서는 문서의 Vector 공간에 있는 Term의 가중치(weights)를 계산하고 있어야 한다. 이를 위해서 term frequency - inverse document frequency 모델이 사용되고 있다.

• TF : 문서 Vector에 존재하는 Term의 갯수
• IDF : Term을 Vector에 포함하고 있는 모든 문서들
• Weight = TF * IDF

문서 d가 있다면, Vector d는

에서

IDF에서 |D|는 문서의 총갯수이고 는 Term을 포함한 문서의 갯수다.

예를 들자면 리눅스(:12)라는 쿼리어가 주어졌을 때 유사한 문서는 리눅스를 많이 포함한 문서일 거라고 예상할 수 있다. 이것이 TF다.

일반적인 단어는 여러문서에 걸쳐서 나올 것이고, 이러한 단어를 포함한 문서는 낮은 유사성을 가지게 될것이다. 이것이 IDF다. 예를 들어서 리눅스 유저로 문서를 찾는다고 하면, 리눅스는 전문용어이므로 더 적은 문서에서 발견 될것이고, 리눅스를 포함한 문서는 더 높은 유사도를 부여할 수 있을 것이다.

예제 : 문서의 유사도

이렇게 각 문서에 대해서 Term Vector를 만들었다고 가정을 해보자.

이제 주어진 Term에 대해서 두 문서간의 거리를 구할 수 있게된다. 이 거리가 가까우면 더 유사한문서라고 할 수 있다.

이렇게 Vector화 하는 이유는 눈으로 읽은 문서가 "야구기사"에 관련된 문서인지 "연예기사"에 관련된 문서인지 분리해낼 수 있는 인간과는 달리 컴퓨터는 이를 구분할 수 없기 때문이다.

여기 A, B, C 세개의 문서가 있다고 가정해 보자. 그리고 백터에 위치하는 원소의 값을 다음과 같이 정의 하자.

1. 번째 원소는 "상상플러스"라는 단어의 빈도수
2. 번째 원소는 "김제동"
3. 번째 원소는 "무한도전" 이다.

(A,B)는 상상플러스에 관한 문서이고, (C)는 야구에 관한 문서다. A에서 첫번째 원소인 "상상플러스"의 발생빈도는
10, "김제동"의 발생 빈도수는 5이다. B는 8,9이고, C는 0이라고 하면 다음과 같이 각 문서의 유사도를 계산해낼 수
있다.

1. d(A,B) = 2^2 + 4^2 = 20
2. d(A,C) = 10^2 + 5^2 = 125
3. d(B,C) = 8^2 + 9^2 = 145

비슷한 주제의 문서들끼리 대체로 가까운 거리를 가지고, 다른 주제를 가지는 문서들이 거리가 멀이지는 것을 확인할 수 있을 것이다.

예제 : Term에 대한 문서의 유사도

"리눅스 개발자" 라는 단어를 포함한 문서들이 있다고 가정해 보자. 색인파일이 만들어져 있다면, 이들 문서를 포함한 문서를 찾는
것은 그리 어렵지 않을 것이다. 문제는 "리눅스 개발자"와 더욱더 많은 관련성을 가진 문서를 어떻게 가려내느냐에 있다.

일반적으로 생각해서 문서 d 의 term vector가 만들어져 있다면, 각 term사이의 거리를 구한다음에 모두 더해주면 될 것이다.

1. 리눅스는 매우 좋은 운영체제이다. 어쩌고 저쩌고.. 한참후에 개발자입장에서 한번 써볼한 하다.
2. 리눅스는 개발자에게 매우 좋은 운영체제이다. 왜냐하면 어쩌고 저쩌고

컴퓨터는 간단한 거리계산을 이용해서 2번 문서가 주어진 Term에 더 유사한 문서라는 걸 찾아낼 수 있다.

장점

1. 동음이의어와 다의어 처리가 가능하다.
2. 결과의 정확도 - relevance scoring - 를 구할 수 있다.
3. 결과 피드백이 용이하다.

단점

Vector Space Model은 다음과 같은 단점을 가진다.

1. Term의 갯수가 많아질수록 해당 문서는 더 낮은 similarity 값을 가지게 된다. 이는 큰 문서일 저 평가될 수 있음을 의미한다.
2. 찾고자 하는 키워드가 정확히 매치되어야 한다. - 이 문제는 좋은 형태소 분석기를 가짐으로써 어느정도 해결할 수 있다. -
3. 워낙에 광범위한 주제를 다루는 문서가 많고 문서에 포함된 Term의 양도 많기 때문에, 비슷한 주제를 다루는 문서라고 하더라도 전혀다른 Term으로 구성되는 경우가 발생한다.
4. 느리다.

3번의 경우가 특히 문제가 될 수 있는데, 예를 들어서 설명해보도록 하겠다.

최홍만은 k-1에서 활약하는 격투선수이면서 특유의 쇼맨쉽으로 이런 저런 프로에 게스트 혹은 고정출현을 하고 있다. 그러므로 연예계 문서중 몇개에서는 '최홍만이 어느정도의 빈도수를 가지게 될 것이다. k-1 으로 눈을 돌려서 생각해보면, 최홍만이 출전한 경기와 관련된 문서의 경우 빈도수가 높지만, 그렇지 않은 경기와 관련된 문서인 경우 낮은 빈도수를 가지게 될 것이다.

이것을 가정해서 최홍만의 빈도수를 y축으로 k-1의 빈도수를 x축으로하고 연예방송과 k-1 두종류의 문서를 그래프로 그려보면 아래와 같이 각각의 주제가y축으로 길게 늘어선 형태를 가지게 된다.

o = 연예계 문서 (k-1에 대한 단어가 전혀 나타나지 않음)
x = k-1 관련 문서들 
최홍만
|o       x
|o      x
|o       x
|o      x
|o       x
|o      x
+-------------->  (K-1)

여기에서 다음의 결론을 얻을 수 있다.

1. 같은 주제라고 하더라도 y축의 이쪽끝과 저쪽끝의 문서는 거리가 멀어진다.
2. 다른 주제라고 하더라도 y축상에 있는 문서끼리는 거리가 가깝다.
3. 결론 : 검색이 제대로 안된다 주제간의 차이를 반영하지 못하기 때문이다.

Markov random walk

두 주제의 성격이 비슷한 경우를 생각해보자. 예를 들자면 리눅스관련 문서와 윈도우즈관련 문서쯤이 되겠다. 다음과 같은 그래프가 만들어진 경우를 생각해 보자.

(단어 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의 문서들보다 쿼리에 더 가까이 있기 때문에, 이들이
상위에 올라오는 문제가 발생한다. 이 경우 주제 2에 속하는 문서를 어떻게 제거할 것인가가 중요한 이슈가 될 것이다.

문제의 해결을 위해서 쿼리 근처 영역만을 잘라놓고 보도록 하자.

|                o <-A
|       D->  o
|     C-> o *    x <-B  
|          o 
|                          

직선거리상으로만 보자면 A와 쿼리의 직선 거리가 B와 쿼리의 직선거리보다 멀다. 그렇지만 쿼리와 C, 쿼리와 D, C와 D,
D와 A 각각의 거리는 B의 거리보다 가깝다. 명확하지는 않지만 문제가 풀릴 수도 있다는 생각이 들 것이다. 각각의 포인트로 이동하게 될확률을 곱하는 것이다.

여기에서 확률은 거리에 따라 달라진다. 거리가 가까우면 움직일 확률이 높아지고, 멀면 그만큼 확률이 낮아진다. 이러한 문제를 처리하기 위해서 나온 아이디어가 Markov random walk로, 쿼리의 위치에서 시작을 해서 A 혹은 B로 도착할 때까지 매 턴마다 랜덤하게 임의의 포인트로 이동을 하는 방식이다.

예를들어 query에서 A로 갈수 있는 유망한 경로와 이에 따른 확률값은 다음과 같을 것이다.

• 쿼리 -> C -> D -> A : 확률값은 P(쿼리->C) * P(C->D) * P(D->A)
• 쿼리 -> D -> A : 확률값은 P(쿼리->D) * P(D->A)
• 기타 : 쿼리 -> C -> 쿼리 -> D -> A 등등등

해서 쿼리에서 A까지 도달할 확률은 위의 path들의 확률을 모두 더한게 될 것이다.

반면 쿼리에서 시작해서 B로 갈 수 있는 유망한 경로는 쿼리->B 하나 뿐이다. 쿼리에서 A 혹은 B로 이동하는 확률값은 각 포인트로 이동할 수 있는 확률의 곱이다. 이는 특정포인트로의 확률이 낮은게 있다면, 전체확률을 크게 낮추게 된다. 위의 그래프에서 C, D, A에서 B로의 거리는 너무 멀기 때문에 확률자체가 낮아지게 되고, 결국 다른 경로를 통한 확률은 쿼리->B보다 낮아질 수 밖에 없게 된다.

즉 두 문서간의 유사성을 판단할때 문서간의 직선거리를 생각하는 대신에 문서에 도착할 확률로 보는 것이다.

Markov Random walk 와 PageRank

PageRank는 문서의 중요도를 위해서 제시한 구글의 알고리즘이다. 예를 들자면 A, B, C, D 4개의 웹문서가 있고, 이중 B와 D가 A를 link 하고 있을 때, A의 Page Rank는

Q(A) = Q(B)/N(B) + Q(D)/N(D)

가 된다. N은 해당 페이지가 가지고 있는 link의 갯수를 의미한다. 이 계산을 모든 웹페이지에 대해서 반복해서 수행하면 된다.

여기에서 Markov Random walk 와 Page Rank와의 관계를 알아보자. 일단 Page Rank는 웹페이지 혹은
링크와 같은 것들을 따로 Vector화 하지 않는다. 그러므로 Markov Random walk를 사용할 수가 없다. 그렇다면,
여러개의 링크중 어떤 링크로 이동할 확률이 가장 큰가를 어떻게 계산할 수 있을까 ?

구글은 random click이라는 아이디어를 생각해 냈다. 예를 들어 A라는 웹페이에 N개의 링크가 있다고 가정 했을 때, random click란 그 중 하나를 무작위로 click할 확률을 의미한다. 이 확률의 계산은 무지 단순하다 1/N 하면 된다. 즉 위의 공식은 아래와 같이 좀더 자세하게 나타낼 수 있을 것이다.

Q(A) = Q(B)*(1/N(B)) + Q(C)*0 + Q(D)*(1/N(D)