Latent Semantic Analysis(LSA)

1. 단어 매칭만으로는 뭔가 부족한 정보검색

예부터 들이 밀고 이야기를 시작해보겠다.

이 예에서, 키워드 검색이라면 주어진 쿼리에 문서1만 매칭에 성공한다. 그런데, 문서의 의미를 가만히 살펴 보면, 문서2 역시 쿼리에 적당한 문서이다. Latent Semantic Analysis(이하 LSA)는 예에서 보듯이 키워드 매칭으로 찾을 수 없는, 의미가 가까운 단어-문서, 단어-단어, 문서-문서를 찾을 수 있게 해준다. 

어떻게 '중국집 메뉴' 와 '짜장면 짬뽕'이 가깝다는 것을 찾아준다는 것일까? 이 때 이용하는 정보가 co-occurrence (공기, 共起)정보다. 문서1을 보면 '중국집 메뉴'와 '짜장면 짬뽕'은 같이 쓰였다. 바꿔 말해, co-occur한다.(共起한다.) 이 사실을 힌트 삼아 쿼리와 문서2 또한 가깝다고 유추할 수 있다. 

LSA는 개념적으로 co-occurrence 정보를 이용한다. co-occurrence 정보를 이용한다는 것은 단어의 '형태(morphology)가 아닌 의미(semantic)'를 이용한다는 뜻이다. 예를 들어 '배'라는 단어는 같은 문장에 co-occur 하는 동사가 '타다' 인지 '먹다' 인지에 따라 의미가 갈라지게 된다.  또한, '식당', '맛있게', '배부르게' 라는 단어와 같은 문장에 co-occur하는 처음 보는 단어는 아마 '음식'일 것이다. LSA는 이론적으로는 선형대수학의 SVD(Sigular Value Decomposition)을 이용한다. SVD를 계산하는 방법에 대해서는 얘기하지 않을 것이다. 시간은 없고, 라이브러리는 많다.

2. LSA는 SVD를 이용한다.

이제 부터가 진짜다. 다음과 같은 단어-by-문서 행렬 A가 있다.(Reference:이 예는 Foundations of Statistical Natural Language Processing에서 베꼈다.)

예제 : 단어-by-문서 원래 행렬

SVD는 원래의 단어-by-문서 행렬 A를 3개의 행렬로 분해(Decomposite, SVD의 D)한다.

A_t×d = T_t×nS_n×n(D_d×n)^T

여기서 아래첨자 txd는 t행 d열의 행렬이라는 뜻이고. 위첨자 T는 전치행렬(transposed matrix)인데, 원래 행렬의 행과 열을 뒤바꿔 놓은 행렬이다. t 는 단어 개수, d는 문서 개수 n은 min(t,d)이다. 행렬 A의 SVD를 (각자 구한 라이브러리를 이용하여)구하면 다음과 같이 3개의 행렬이 얻어진다.

원래 행렬 A 의 SVD

T는 단어에, D는 문서에 대응되는 행렬이다. 각 단어와 문서는 5차원 공간의 한 점으로 표현되고 있다. 대각행렬 S는 오른쪽 아래로 갈 수록 작은 값을 가지는데 5개의 값은 1~5번째 차원의 Scale로 생각할 수 있다. 더 뒤쪽 차원으로 갈 수록 그 Scale이 낮아진다는 뜻이다. 위에서 얘기했듯이 n의 값 5는 t와 d중 작은 값이다. 그런데, SVD는 여기서 n보다 훨씬 작은 k 값을 설정해서 그 이상의 차원은 날려버리는 방법으로 차원 축소를 해버린다.

3. LSA는 co-occurrence + 차원 축소

SVD에 대한 자세한 얘기는 대부분 생략했지만, 개념적인 이야기로 한번만 더 정리하고 넘어가겠다. 위 예 처럼 조그만 예가 아니라 실제 상황에서는 t(단어 개수), d(문서 개수)의 값은 수*만에 이를 것이다. min(t, d)인 n 역시 수*만에 이를 것이다. 만일 t = 100만, d= 500만 이었다면, 원래 행렬 A는 100만 차원 공간에 있는 500만개의 점을 표현하는 행렬이다. SVD를 구하는데 k = 100으로 정한다면, 행렬 A는 다음과 같은 3개의 행렬로 분해된다.

T : 100차원 공간에 100만개의 단어에 대응되는 점으로 표현
D : 100차원 공간에 500만개의 문서에 대응되는 점으로 표현
S : 1 ~ 100번째 차원의 중요도를 나타내는 대각행렬

위 표현에서 '대응되는 점'이라는 간접적인 표현을 쓴 것은 직접적으로 값을 사용하는 게 아니기 때문에 그렇게 쓴 것이다. 용도에 맞게 행렬을 사용하는 방법은 잠시 후에 얘기하겠다. 

일단, 여기서 D 행렬만 놓고 생각을 해보자. 원래의 공간에서는 500만개의 문서는 100만 차원 공간의 한 점으로 표현되었다. 그런데, 행렬 D에서는 500만개의 문서가 100차원으로 차원 축소된 공간의 한 점으로 '투영된다(projection)'. 축소된 공간으로 투영되는 와중에 비슷한 co-occurrence 패턴을 가지는 문서나 단어는 가까운 위치로 접근을 하게 된다. (무슨 마술 처럼 이야기를 하네-.-;;;) 그래서 LSA의 핵심 개념을 두 가지로 요약하면,

1. co-occurrence 정보 이용
2. 차원 축소

가 되겠다.

4. 활용 - 분해된 행렬의 사용방법

그럼, 잠시 미뤄 놓았던 3개의 행렬을 사용하는 방법을 말할 차례이다. 위의 예(5 x 6짜리 A행렬)에서 구했던 3개의 행렬을 k = 2로 차원 축소를 하면 3 ~ 5차원은 버려지고, 아래와 같은 차원 축소된 조합이 된다.

2차원으로 차원 축소한 SVD

3가지 시나리오에서의 이용방법은 다음과 같다.

1. 단어 - 단어간의 유사도 T X S 행렬의 row 간의 유사도로 계산한다.
2. 문서 - 문서 S X D^T 행렬의 colum 간의 유사도로 계산한다.
3. 단어 - 문서 TSD^T의 각 요소가 단어와 문서간의 유사도이다.

제일 만만한 2번 시나리오, 문서-문서간의 유사도를 어떻게 계산하는지만 예를 들어 보겠다. 위 그림에서 S X D^T 행렬을 구해보면 다음과 같다.

S X DT 행렬

결과적으로 D^T 행렬을 S행렬에 의해 re-scaling한 행렬이다. 암튼 문서1과 문서2의 유사도는 위 행렬의 1번째 컬럼과 2번째 컬럼의 cosine 유사도를 구하면 된다. 그렇다면, 모든 문서 쌍에 대해서 문서-by-문서간의 coine 유사도를 계산할 수 있다. 그 결과를 표로 그리면 다음과 같다.

문서-문서 간의 유사도

1.00은 자기 자신과 비교한 것이니까 빼고, 문서4-문서5가 가장 가까운 문서로, 문서3-문서6이 가장 먼 문서로 판명되었다. 맨위에 나온 행렬 A 그림에서 원래 문서를 찾아보면 이해가 될 것이다. 그런데, 여기서 문서2-문서3의 비교 결과가 흥미롭다. 원래 행렬 A에서 보면 두 문서는 공유하는 단어가 하나도 없다. 하지만 이 표에서는 유사도가 0.88로 매우 높게 나온다. 이게 다 co-occurrence와 차원 축소를 이용한 LSA의 결과이다. 

휴~ 여기까지. 누군가는 처음부터 끝까지 읽었으면 하는 마음에 내용을 줄이다 줄이다 보니 너무 많은 부분이 빠졌다. 특히, SVD에 의한 차원 축소에 대한 부분은 거의 한강을 건너 뛰는 수준이다. 이 부분에 대한 설명은 위 예제를 베껴온 Foundataions of Statistical Natural Language Processing 책에 정말 잘 나와있다. 아... 이런 말로 마무리를 하게 되다니. 아뭏든 여기까지 읽어준 분이 있다면, 감사합니다.