[Advanced ML & DL Week1] Indexing By Latent Semantic Analysis

작성자: 15기 조우영

 

Introduction

 

• 목적: 기존(해당 논문 이전)의 검색 기법들에 만연한 문제인 query에 존재하는 단어들과 document에 존재하는 단어들을 match하려는 문제를 해결하기 위한 새로운 접근, 방법을 소개하기 위함
  • 문제는 사용자들은 의미에 기반하여 검색을 하지만 문서에 존재하는 각 단어는 문서의 개념적 주제나 의미와 매치하지 않거나 무관하기 때문에 발생
  • Synonymy: 똑같은 개념을 표현할 수 있는 다양한 단어들이 존재하기 때문에 user가 제공한 query에 존재하는 단어가 document에는 존재하지 않는 현상
  • Polysemy: 한 단어에 다양한 의미가 존재하기 때문에 user가 제공한 query에 존재하는 단어가 실제로 document에 존재해 match가 되기는 하나, user의 의도와는 다른 의미를 가지는 현상
• 해결법: 검색을 위해 선택되는 단어의 무작위성에 의해 가려진 잠재적인 의미 구조(Latent Semantic Structure)가 data에 존재한다고 가정하고, 통계 기법을 이용하여 이 잠재 구조를 추정하고 모호한 노이즈를 제거함. 그리고 해당 구조를 indexing과 검색에 이용한다. Latent Semantic Structure를 찾기 위해서 SVD(Singular Value Decomposition, 특이값 분해)를 이용함. 

 

 

Deficiencies of Current Automatic Indexing and Retrieval Methods

 

근본적인 문제: 특정 정보를 찾기 위해 사용자가 검색하는 단어와, 해당 정보를 indexing한 단어가 일치하지 않음

1. Synonymy(유의어): 동일한 대상을 표현하는 여러가지 방법이 존재한다. 검색의 Recall(재현율)을 떨어뜨린다. 
2. Polysemy(다의어): 동일한 단어에도 여러가지 의미가 존재한다. 검색의 Precision(정밀도)를 떨어뜨린다.

 

*  Precision과 Recall이란??

 

	Relevant Document (관련 있는 문헌)	Irrelevant Document (관련 없는 문헌)
Retrieved Document (검색된 문헌)	A	B	A + B
Unretrieved Document (검색되지 않은 문헌)	C	D	C + D
	A + C	B + D	A + B + C + D

 

 

Recall = $\frac{A}{A + C}$ = $\frac{\sharp(Relevant Doc \,  \cap \, Retrieved Doc)}{Relevant Doc}$ = P(Retrieved Doc|Relevant Doc)

 

Precision = $\frac{A}{A + B}$ = $\frac{\sharp(Relevant Doc \,  \cap \, Retrieved Doc)}{Retrieved Doc}$ = P(Relevant Doc|Retrieved Doc)

 

 

위의 언급된 문제를 극복하는데에 실패한 이유에는 3가지 큰 요인이 존재하는데, 이는, 

 

1. 문서를 통해 만들어진 index term 불완전성, 
   • User가 사용할 모든 단어를 index term이 포함하고 있지 않거나, term selection procedure에서 문서에 존재하는 많은 단어들이 drop 되기 때문
   • 유의어 문제를 위한 해결방안: Term Expansion, Thesaurus(유의어사전) 만들기
     
     • 크기가 작은 데이터에는 Precision의 손실 없이 Recall Rate을 높이는 유의미한 효과를 보였지만, 큰 데이터에 대해서는 Polysemy 문제를 야기함(Precision의 손실 발생) 
2. 다의어를 처리하기 위한 자동화 된 기법의 부재,
   
   • 다의어 문제를 위한 해결방안: 특정 단어만 사용하도록 통제하거나, 사람을 번역기처럼 사용하는 방법
     • 사람을 직접 사용하기 때문에 비용이 크고, 사람의 능력에 직접적인 영향을 받음
     • 적절한 controlled vocab을 찾았음에도 document나 indexing에 사용되지 않은 단어일 수도 있음
3.  기존의 indexing과 retrieval 작동 기법의 한계
   • 각 단어들이 서로 독립적으로 발생한다고 가정하는 현재의 작동 방식으로 인해 복합 용어를 사용하는 쿼리 사용이 제한됨
   • 중복성을 전혀 고려하지 못해 위의 언급된 문제를 더욱 심하게 하는 요인이 되기도 함

이다. 

 

 

Rationale of the Latent Semantic Indexing(LSI) Method

 

Illustration of Retrieval Problems

 

기존의 term based 검색 방법의 문제점을 아래의 가상의 Document-Term Matrix(DTM)을 사용하여 살펴보자

 

* Query: "IDF in computer-based infomation look-up"

 

 

• REL열의 R: 사용자가 Query와 관련있다고 판단한 문서(실제로 관련있는 문서)
• MATCH열의 M: 기존의 방식에 의해 Query와 매치되어 사용자에게 return된 문서(Query에 등장한 단어가 문서에도 등장하면 MATCH로, 문서와 Query 모두에 등장한 단어에는 *이 붙어있다)

 

문서 1은 실제로는 query와 관련이 있는 문서임에도 불구하고 query와 일치되는 단어가 문서에 존재하지 않기 때문에 매치되지 않아 return되지 않는다. 반면 문서 2는, query와 관련이 없음에도 query와 일치하는 단어가 있어 매치되어 return 된다. 

 

 

유의어 문제(문서 1에서 발생)

 

• 사용자의 관점에 의하면 문서 1에는 'look-up'이라는 단어가 들어가있어야 하고 반대로 시스템의 관점에서는 query에 access 혹은 retrieval이라는 단어가 들어있었어야 한다.
• 이는 문서가 특정 주제의 일부만을 포함하고 있기 때문에, 추출되는 index term 또한 이런 특성을 가지고 있기 때문에 발생한다. 
• 이는 query에 대해서도 마찬가지로, query의 내용이 문서에 포함된 내용에 일부에 불과하기 때문에 발생한다. 
• 해결방법: query가 실제로 암시하고 있는 단어를 예측하는 방법을 찾거나, 문서에서 사용되고 있는 단어들이 무엇인지를 기반으로 query를 문서에 적용하는 방법을 찾아야함
  • 예를 들어, 'access'와 'retrieval'이 각각 100개의 문서에서 등장했을 때, 그 중 95개의 문서에 두 단어가 동시에 등장했다면, retrieval이 등장하지 않고 access만 등장한 5개의 문서에 대해서 뭔가 잘못됐다고 판단해, retrieval만 등장하는 query가 입력됐을 때에도 해당하는 5개의 문서도 매치시킬 수 있는 어떠한 구조를 찾아내야 한다.

 

 

다의어 문제(문서 2에서 발생)

 

• 문서 2에 등장하는 단어 'information'은 사실은 query에 등장하는 단어 'information'과는 다른 의미로 쓰인 단어라고 한다. 
• 해결방법: Correlational Structure Analysis를 통해 다의어의 가중치를 줄이는 방법을 사용할 수 있다.

 

Incomplete하고, unreliable한 set of terms로 구성된 표현을 더 reliable한 표현들로 대체해는 것이 목표!

이를 위해 term과 document 사이의 숨겨진 구조(Latent Structure)를 사용하려고 한다.

 

 

The Choice of Method for Uncovering Latent Semantic Structure

 

• Latent 모델의 parameter를 찾기 위해서 문서 내에 단어의 등장에 대한 행렬을 사용할 것이다.
• 문서와 단어 사이의 의미적 유사성이 문서 내의 단어 사용 패턴을 모델링 하는데 핵심적이기 때문에 proximity model을 사용한다.
  • Proximity model이란 어떤 공간이나 구조 안에서 서로 유사한 것끼리 가까이에 두려고 하는 모델이다.
• 이런 숨겨진 Proximity Sturucture를 찾아 검색을 위해 사용하려는 선행 연구 2개에 대한 간단한 소개
  • Hierarchical Classification
    • 문서와 단어의 클러스터링을 위해 사용된다.
    • 문서 간에 공통된 단어가 얼마나 존재하는지에 따라 유사도가 정해짐(많을수록 거리가 가까운 것)
    • 문서-문서 간의 거리 행렬은 hierarchical classfication을 찾기 위한 cluster analysis를 위해 사용된다. 검색 시에는 이 structure의 neighborhoods를 탐색하게 된다.
    • Hierarchical Clustering은 계층이 너무 제한적이기 때문에 문서들에 존재하는 풍부한 의미를 담지 못한다. Cross classification이 불가능하다는 점, 일반적으로 parameter의 수가 굉장히 적다(n개 object에 대해서는 n개 parameterr가 최대)는 점이 그 예시 중 일부이다. 
    • Hierarchical Classification은 검색을 위한 계산의 효율성은 증가시켰으나, 검색의 성능을 개선시켰는가에 대해서는 확실하지 않다.
  • Factor Analysis
    • 문서들 간의 유사도로 구성된 square symmetric matrix를 구성하고 linear algebra를 이용하여 비슷한 문서들끼리 가까이에 위치하는 low dimensional spatial model을 생성한다.
    • Factor Analysis는 이전에 소개된 clustering 방법에 비해 문서들에 존재하는 풍부한 의미를 담아낼 잠재성이 존재한다.(n개 points에 대한 k차원 모델은 nk개의 parameter를 지닌다.)
    • 하지만, 계산비용이 매우 크고, 이전 시도들이 15~20년 전에 있었던 것을 고려했을 때, 여러가지 processing constraints가 존재하였다. 
    • 기존의 factor analysis에는 굉장히 제한된 factor analytic model들이 사용되었다.
    • 심지어 일부 기존의 시도들은 인간이 직접 수천 수만 건의 유사성을 판단하는 작업이 요구되었다.
  • 검색 문제에서는 term과 document 모두가 고려되어야 하는데 앞서 소개한 hierarchical classification과 factor analysis 모두 term만을 혹은 document만을 다룰 수 있다는 공통적인 문제도 존재하였다.

 

 

해당 논문에서 제시하는 방법의 차별점

 

 

1. 합리적인 size의 문제를 분석하였다. 
2. term-document relation을 포착하기 위한 약 100차원의 rich, high-dimensional representation
3. 동일한 공간에서 term과 document를 모두 represent 할 수 있는 수학적 기법
4. query terms를 통해 직접 문서를 검색(기존 factor analysis 방법처럼 기본 축을 회전시키거나 해석하려 하지 않고, 기존 hierarchical classification과 같은 clustering 방법처럼 intermediate document cluster를 사용하지 않고)

 

모델 선정에 적용한 3가지 기준

 

 

1. Adjustable Representational Richness(표현의 풍부함의 정도를 조절 가능하게끔) 
   • 차원의 수 k를 조정할 수 있는 multidimensional scaling이나 factor analysis와 같은 방법
2. Explicit Representation of both terms and documents 
   • 검색은 query에 해당하는 새로운 object가 들어왔을 때 semantic structure에 적절히 배치를 하고 가까이에 위치한 문서들을 찾는 방식으로 이루어짐
   • 이를 달성하기 위해서는 terms 또한 documents와 마찬가지로 semantic structure 내에 위치할 수 있어야 한다. 이를 위해서는 rectangular matrix로 시작해 row object와 column object에 대해 모두 적절한 표현방법을 구성하는 two-mode proximity methods를 사용한다. 이런 방법의 예시로는,  
     1. Multidimensional Unfolding
        • term과 document 모두 동일한 space 상에 point로 표현됨
        • 유사도는 point들 간의 euclidean distance를 통해 측정됨
     2. Two-mode Factor Analysis
        • 마찬가지로 term과 document 모두 동일한 space 상에 point로 표현됨
        • 유사도는 point들 간의 inner product를 통해 측정됨
     3. Unfolding in trees
        • term과 document 모두 tree 상의 leaves로 표현됨
        • 유사도는 tree path의 길이로 측정됨
3. Computational Tractability for Large Datasets: 기존의 모델들은 $N^4$, $N^5$ (N = # terms + # doucments) 정도 복잡도를 가지는 계산이 요구됐기 때문에 보다 효율적인 능력을 가지는 모델을 찾고자 하였다.

 

위 3가지 기준을 모두 만족한 모델은 two-mode factor analysis였다. 

 

• tree unfolding model은 표현에 있어서 제약도 존재하며 계산 비용이 높음.
• mutidimensional unfolding 또한 계산 비용이 높음
• two mode factor analysis는 SVD를 기반으로 하는 familiar factor analytic model의 일반화된 버전이다.
• SVD를 사용하면 terms, documents를 선택 가능한 차원의 공간에 나타내고 dot product나 cosine 값을 통해 유사도를 측정할 수 있다.
• 또한 시간복잡도 또한 $N^2$×$k^3$로 더 빠르다.

 

SVD or Two-Mode Factor Analysis

 

LSA(Latent Semantic Analysis)는 terms by documents matrix를 사용한다. Terms by documents matrix에서 latent semantic structure model을 찾기 위해 SVD(Singular value decomposition)가 사용된다. 이를 factor analysis의 관점에서 살펴보면, 

 

 

1. one-mode factor analysis

 

• 동일한 유형의 object의 가능한 모든 쌍의 관계를 나타내는 square symmetric matrix (document by document matrix) - 사람이 판단한 유사도, 혹은 겹치는 단어의 개수를 나타내는 행렬일 수 있음
• 이 matrix를 eigen analysis를 통해 eigenvectors와 eigenvalues라는 특수한 두 matrix간의 곱으로 표현
• Original document는 기존의 차원보다 더 낮은 차원을 가지는 factor를 통해 근사된다.

 

2. two-mode factor analysis

 

• one-mode factor analysis에서와 달리 행과 열에 각각 다른 유형의 object의 가능한 모든 쌍의 관계를 나타내는 rectangular matrix(term by document matrix)
• singular value decomposition이라는 방법을 통해 이 rectangular matrix는 특수한 세 matrix의 곱으로 표현됨
• one-mode에서와 마찬가지로 이 특수한 matrices는 더 낮은 차원을 가지는 factor를 통해 근사된다. 
• 유사도는 vector간의 dot product나 cosine을 통해 측정된다. 
• SVD를 통해 각 단어들을 orthogonal factor value들로 변환하는 것은 최초에 설명한 3가지의 모델 선정 기준에 부합한다.

 

대략적으로 말하면 factor들은 서로 다른 단어와 문서에서 추출된 공통되는 의미 요소들이라고 할 수 있다. 각각의 단어와 문서는 이러한 의미 요소들과의 연관성의 강도를 나타내는 가중치를 가지는 vector로 표현된다.  즉, 어떠한 term, query, document는 k개의 factor를 통해 표현될 수 있다. (원래 N개인 index terms가 가장 근사한 k < N인 factor들을 통해 표현된다.) 이 때, 우리의 목표는 factor를 통해 단순히 terms, documents, queries들을 표현하게 되는 것이 목적이므로 일반적인 factor analysis에서처럼 축을 회전시키거나 factor의 의미 자체를 해석하려는 시도는 하지 않는다. 역시 같은 이유로 2개 혹은 3개의 factor만을 사용하여 매우 저차원으로 차원을 축소하려는 시도도 하지 않는다. 하지만 여전히 계산의 효율성을 높이는 차원에서 너무 낮지도 높지도 않은 차원을 사용하고자 한다. 

 

query가 주어지면 query에 주어진 단어들의 weighted sum을 통해 query를 재표현한다. 이를 pseudo-documents라 한다. 그리고 이 pseudo-documents와 모든 documents들 간의 cosine 유사도를 측정해 유사한(높은 cosine값을 가지는) 문서들을 return한다.

 

 

예시

 

 

 

• Terms에 등장한 index terms는 한 개 이상의 문서의 제목에 등장한 단어들이다. 
• c1~c5는 human-computer interaction과 관련된 문서들이고, m1~m4는 graph theory와 관련된 문서들이다.
• 각 cells는 각 문서의 제목에서 해당 단어가 등장한 횟수이다. 

 

• 위의 설명된 matrix에 singular vector decomposition을 적용한 결과이다. 
• 각각의 terms는 검은 동그라미로, documents는 하얀 사각형으로 표현되고 있다.
• human computer interaction이라는 query와 관련있는 문서를 찾아보자.
• 단순히 일치하는 단어를 통해 찾으면 human interaction이라는 단어가 제목에 포함된 c1, c2, c4가 return 되지만, 실제로 관련있지만 human interaction이라는 단어가 제목에 포함되어있지 않은 c3와 c5는 return되지 않는다.
• latent semantic structure method는 구성된 factor space에서 'human computer interaction'이라는 query와 유사한 문서를 찾아낸다.
• query에 등장하는 'human'과 'computer'라는 2개의 term이  factor space에 존재하기 때문에 그 사이에 query에서 생성된pseudo-document q가 위치하게 된다.
• q와 유사한 문서들(cosine 유사도 0.9 정도 = 점선으로 표시되어있음)은 점선 내부에 존재한다. 이전과 달리 실제로 유사한 내용을 갖는 문서인 c1~c5가 모두 return된다. 
• SVD를 사용한 결과가 term-based 방법(단순히 일치하는 단어의 수를 보는 방법)보다 우수한 검색 성능을 가지는 것을 확인할 수 있었다.

 

 

Technical Details

 

The Singular Value Decomposition(SVD) Model

 

모든 rectangular matrix(t x d matrix, t for terms, d for documents)는 다음과 같은 3 matrices의 곱의 형태로 표현될 수 있는데 이를 X의 singular value decomposition이라 부른다.

 

$X = T_{0}S_{0}D_{0}'$

 

Original SVD Model

 

• $T_{0}$와 $D_{0}$는 orthonomal(column vector들의 inner product가 0, 모든 벡터의 크기가 1)한 column들을 가지고 $S_0$은 diagonal matrix이다.
• $T_{0}$와 $D_{0}$는 각각 left singular vectors, right singular vectos로 구성된 행렬이고, $S_{0}$는 singular values로 구성된 diagonal matrix이다.
• SVD의 결과는 row, column, sign permutation까지 모두 unique하다. 통상적으로, $S_{0}$의 원소는 모두 양수이고, 크기에 따른 내림차순으로 배열될 수 있게끔 구성한다.
• 일반적으로, $T_{0}, S_{0}, D_{0}$ 모두 full rank이다. 

 

Reduced SVD Model

 

• SVD의 강력한 이점은 더욱 작은 행렬을 이용하여 최적의 근사를 하는 방법이 간단하다는 것이다. $S_{0}$의 singular values 중 k largest singular values는 유지하고, 나머지는 0으로 만든다. 이렇게 새로이 만든 $S_0$와 $T_{0}, D_{0}$의 product로 표현되는 새로운 행렬 $\hat{X}$는 rank k를 갖는 X의 근사행렬이 된다. 

 

* 이 때 k는 가장 좋은 검색 성능을 보이는 k를 사용한다.

 

• 위의 과정에서 $S_0$의 밑부분에 zeros를 남겨놓았기 때문에 $S_{0}$는 diagonal matrix가 아니다. 이 zero rows를 delete하고 일부 columns를 delete함으로 $S_0$에서 새로운 diagonal matrix S를 만들 수 있다. $T_0$와 $D_0$의 대응하는 columns를 delete해 새로운 matrix T와 D를 만들어내면 다음과 같은 reduced model을 얻을 수 있다.

 

$X$ $\approx$ $\hat{X}$ = $TSD'$

 

 

Comparing Fundamental Comparison Quantities from the SVD Model

 

- Comparing two terms (단어 i와 단어 j가 얼마나 유사한가?)

 

두 단어 간의 유사도는 $\hat{X}$의 row vectors 간의 dot product를 통해 표현된다. $\hat{X}\hat{X}'$는 모든 term-to-term dot products를 cell로 갖는 square symmetric matrix이다. S가 diagonal matrix이고, D가 orthonomal하기 때문에 

 

$\hat{X}\hat{X}' = (TSD') \times (TSD')' = TSD'DST' = TSIST' = TS^{2}T'$

 

와 같이 표현된다.

 

따라서 $\hat{X}\hat{X}'$의 (i, j) cell은 matrix TS의 i번째 row와 j번째 rows의 dot product를 취하는 방식으로도 얻을 수 있다. 때문에 TS의 row를 term의 좌표라고 생각하면 이러한 점 사이의 dot product를 통해 term들 간의 비교가 가능하다. S가 diagonal matrix이기 때문에 T를 좌표로 삼을 때와 TS를 좌표로 삼을 때의 관계는 간단하다. S가 diagonal matrix이기 때문에 TS는 T의 각각의 column에 S의 diagonals만큼 scalar곱을 해준 것과 동일하다. 즉, 기존의 축을 S의 diagonals를 통해 축소시키거나 늘린 것이다.

 

 

- Comparing two documents (문서 i와 문서 j는 얼마나 유사한가?)

 

두 문서 간의 유사도를 구하는 방법도 비슷하지만, 이때는 $\hat{X}$의 row vectors간의 dot product가 아닌 column vectors간의 dot product를 사용한다는데에서 차이를 가진다. 따라서 $\hat{X}'\hat{X}$가 모든 document-to-document dot products를 cell로 갖는 square symmetric matrix이다.

 

위에 설명한 이유와 동일한 이유로 

 

$\hat{X}'\hat{X} = DS^{2}D'$

 

로 표현된다. 

 

DS의 rows를 document의 좌표라고 생각하면 이러한 점 사이의 dot product를 통해 document들 간의 비교가 가능하다. 마찬가지로 D를 좌표로 삼을 때와 DS를 좌표로 삼을 때는 S가 diagonal matrix이기 때문에 DS는 D의 각각의 column에 S의 diagonals만큼 scalar곱을 해준 것과 동일하다는 관계를 갖는다.

 

 

- Comparing term and document (단어 i와 문서 j는 얼마나 연관되어있는가?)

 

term과 document간의 비교는 앞선 두 개의 비교에서처럼 $\hat{X}$의 행이나 열을 사용하는 것이 아닌 cell을 기준으로 이루어진다. 

$\hat{X} = TSD'$로 표현되기 때문에 $\hat{X}$의 (i, j) cell은 $TS^{\frac{1}{2}}$의 i번째 row와 $DS^{\frac{1}{2}}$의 j번째 column의 dot product를 취해 얻을 수 있다. 

 

 

Finding Representations for Pseudo-Documents

 

query 혹은 pseudo-document와 문서들을 비교하기 위해서는 query에 존재하는 term에 대한 vector $X_{q}$를 통해 마치 행렬 D의 row처럼 사용 가능한 $D_{q}$를 얻고자 한다. X = $\hat{X}$라 가정하면 실제 문서 $X_{i}$를 넣었을 때 $D_{i}$를 다음과 같이 얻을 수 있다.

 

$D_{i} = X_{i}'TS^{-1}$

 

따라서  X = $\hat{X}$라는 가정 하에서 $D_{q}$를 다음과 같이 정의한다.

 

$D_{q} = X_{q}'TS^{-1}$

 

이를 통해 query와 문서 간의 비교가 가능해진다.

 

 

 

 

 

 

https://wikidocs.net/24949

1) 잠재 의미 분석(Latent Semantic Analysis, LSA)