2009/08/05 19:20
if (IR or NLP)
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에서 베꼈다.)
SVD는 원래의 단어-by-문서 행렬 A를 3개의 행렬로 분해(Decomposite, SVD의 D)한다.
예제 : 단어-by-문서 원래 행렬
At×d = Tt×nSn×n(Dd×n)T
여기서 아래첨자 txd는 t행 d열의 행렬이라는 뜻이고. 위첨자 T는 전치행렬(transposed matrix)인데, 원래 행렬의 행과 열을 뒤바꿔 놓은 행렬이다. t 는 단어 개수, d는 문서 개수 n은 min(t,d)이다. 행렬 A의 SVD를 (각자 구한 라이브러리를 이용하여)구하면 다음과 같이 3개의 행렬이 얻어진다.
T는 단어에, D는 문서에 대응되는 행렬이다. 각 단어와 문서는 5차원 공간의 한 점으로 표현되고 있다. 대각행렬 S는 오른쪽 아래로 갈 수록 작은 값을 가지는데 5개의 값은 1~5번째 차원의 Scale로 생각할 수 있다. 더 뒤쪽 차원으로 갈 수록 그 Scale이 낮아진다는 뜻이다. 위에서 얘기했듯이 n의 값 5는 t와 d중 작은 값이다. 그런데, SVD는 여기서 n보다 훨씬 작은 k 값을 설정해서 그 이상의 차원은 날려버리는 방법으로 차원 축소를 해버린다.
원래 행렬 A 의 SVD
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 : 100차원 공간에 500만개의 문서에 대응되는 점으로 표현
S : 1 ~ 100번째 차원의 중요도를 나타내는 대각행렬
일단, 여기서 D 행렬만 놓고 생각을 해보자. 원래의 공간에서는 500만개의 문서는 100만 차원 공간의 한 점으로 표현되었다. 그런데, 행렬 D에서는 500만개의 문서가 100차원으로 차원 축소된 공간의 한 점으로 '투영된다(projection)'. 축소된 공간으로 투영되는 와중에 비슷한 co-occurrence 패턴을 가지는 문서나 단어는 가까운 위치로 접근을 하게 된다. (무슨 마술 처럼 이야기를 하네-.-;;;) 그래서 LSA의 핵심 개념을 두 가지로 요약하면,
1. co-occurrence 정보 이용
2. 차원 축소
가 되겠다. 2. 차원 축소
4. 활용 - 분해된 행렬의 사용방법
그럼, 잠시 미뤄 놓았던 3개의 행렬을 사용하는 방법을 말할 차례이다. 위의 예(5 x 6짜리 A행렬)에서 구했던 3개의 행렬을 k = 2로 차원 축소를 하면 3 ~ 5차원은 버려지고, 아래와 같은 차원 축소된 조합이 된다.
3가지 시나리오에서의 이용방법은 다음과 같다.
결과적으로 DT 행렬을 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의 결과이다.
2차원으로 차원 축소한 SVD
3가지 시나리오에서의 이용방법은 다음과 같다.
1. 단어 - 단어간의 유사도 T X S 행렬의 row 간의 유사도로 계산한다.
2. 문서 - 문서 S X DT 행렬의 colum 간의 유사도로 계산한다.
3. 단어 - 문서 TSDT의 각 요소가 단어와 문서간의 유사도이다.
제일 만만한 2번 시나리오, 문서-문서간의 유사도를 어떻게 계산하는지만 예를 들어 보겠다. 위 그림에서 S X DT 행렬을 구해보면 다음과 같다. 2. 문서 - 문서 S X DT 행렬의 colum 간의 유사도로 계산한다.
3. 단어 - 문서 TSDT의 각 요소가 단어와 문서간의 유사도이다.
S X DT 행렬
문서-문서 간의 유사도
휴~ 여기까지. 누군가는 처음부터 끝까지 읽었으면 하는 마음에 내용을 줄이다 줄이다 보니 너무 많은 부분이 빠졌다. 특히, SVD에 의한 차원 축소에 대한 부분은 거의 한강을 건너 뛰는 수준이다. 이 부분에 대한 설명은 위 예제를 베껴온 Foundataions of Statistical Natural Language Processing 책에 정말 잘 나와있다. 아... 이런 말로 마무리를 하게 되다니. 아뭏든 여기까지 읽어준 분이 있다면, 감사합니다.
Trackback | http://blog.sragent.pe.kr/trackback/28
-
http://blog.sragent.pe.kr/entry/Latent-Semantic-AnalysisLSA http://en.wikipedia.org/wiki/Singular_value_decomposition http://stat.ethz.ch/R-manual/R-patched/library/base/html/svd.html 문서들을 N개의 차원(단어)로 이루어진 M개의 문서 ..
댓글을 달아 주세요
진짜 정리를 잘하셨군요.
진짜?
너무 잘 봤습니다. 프린트해서 삼공펀치로 찍어서 철 해놨습니다.^^
질문하나 해도 될까요?
3가지 시나리오 이용방법 중에,
문서-문서 유사도 검색을 S X DT 행렬의 colum 간의 유사도로 계산하는 근거는 뭔가요?
(위의 질문에 이어서..)
정확한 이해를 위해서는
eigenvector나 eignevalue가 의미하는 것을 알아야 할 듯 싶은데..저는 단지 계산하는 방법 정도만 알고 있는듯 싶어서요.
잘 보셨다니 감사드립니다.
부끄럽게도 저도 SVD를 수학적으로 이해한게 아니라서 시원한 답을 못드리겠습니다.
SVD의 결과를 놓고 개념적을 파악한 수준입니다.
본문의 밑에서 두번째 그림에서 보듯이 S X DT행렬의 각 컬럼들은 원래의 문서 vector를 2차원 vector로 차원 축소한 것들입니다. 따라서 문서간의 유사도를 컬럼 벡터간의 유사로 계산을 합니다.
오랫만이네 잘 배우고 감 ^^;
근데 적절한 차원값 k는 어떻게 정하면 좋은것이야... 연락처는 mingk24 골뱅이 지메일 ~~
반갑다 ^^
Foundations ... 책에서는
"Values of k that are frequently chosen are 100 and 150." 이라고만 나와 있는데, 자세한 내용은 더 찾아봐야 알겠다.
아...정말 필요한 정보였는데...감사합니다.
나름 된 포스팅이군요.^^
근데 문서2하고 문서3 공유하는 단어가 없는데 유사도 높게 나온건 어찌 받아들여야 하나요?ㅋ
아까 첫번째 예에서 짬뽕-메뉴 이런 식으로 co-occurrence의 결과로 봐야하겠지만.....
맞나요?ㅋ
암튼 좋은 포스팅 감사합니다.
문서2와 문서3은 모두 문서1과 공유하는 단어가 있는 탓에 유사한 문서로 나왔습니다.
좋은 자료 잘 읽고 갑니다.^^
올려주신 자료는 정말 유용하게 잘 봤습니다. svd로 주신 예제로 다 돌려봤는데요 마지막에 코사인 유사도는 어떻게 구하나요? 제가 매틀랩 초보라서.... 어떻게 계산해야하는지 알려주실수 있나요? 부탁드립니다~
LSA에 대해 공부하고 있는데 다른 자료들 보고 잘 이해가 안됬는데,
이글을 보고 완전 이해하고 갑니다. 정리 완전잘하셨어요 필요한 부분만
재미있게 읽고 갑니다. "SVD + 대각행렬 차원축소"가 핵심이네요. 그리고 3가지나(?) 응용할 수 있으니 정말 멋지네요~ 감사합니다.