Introduction
* 검색 기법의 근본적 문제 : 유저들은 conceptual content에 기초해 검색 but concept를 표현하는 단어가 많고 단어의 다의성 때문에 쿼리가 제대로 작동하지 않음
ex) conceptual content = naver일 때 naver를 검색하기 위해 'it회사', '초록창', '검색엔진' 등
을 사용할 수 있음. 여기서 '초록창'은 naver를 지칭하는 은어이지만, 실제로 초록색 창문을 의미
할 수도 있음.
* 문제의 해결법 : data에 latent sematic structure가 잠재되어 있다고 가정하고 해당 structure를 찾아 indexing과 검색에 이용. latent semantic structure를 찾기 위해서 SVD(Singular Value Decomposition)를 사용.
Deficiencies of current automatic indexing and retrieval methods
기존 정보 검색 방법의 문제
* 근본적 결함 - 단어를 통해 특정 정보를 찾기 위해 검색할 때, 정보를 색인화 한 단어와 검색을 위해 사용한 단어가 동일하지 않음.
* 유의어(synonymy)의 존재 때문에 동일한 대상을 표현할 때 사람별로 다른 단어를 사용하게 된다. 이는 검색의 재현율(recall performance) 를 떨어트린다.
* 다의어(polysemy)의 존재 때문에 동일한 단어를 듣고도 여러가지 대상을 떠올린다. 이는 검색의 정밀도(precision)를 떨어트린다.
* 참고로 여기서 말하는 recall, precision은 위 표를 참고하면 이해하기 편하다.
$recall = {a \over a+c}$
$precision == {a \over a+b}$
synonymy, polysemy 문제를 해결에 실패한 원인
* 기존 automatic indexing 기법에서 위에서 언급한 문제들을 해결하기 위해 노력했지만 실패했다. 원인은 다음과 같다.
1) 문서에 맞게 identified된 index term이 불완전함
- synonymy 존재로 인해 index term은 사용자가 검색에 사용하는 모든 term들을 반영하지 못함.
- 전문가들은 유의어 문제를 해결하기 위해 automatic term을 확장하거나 thesaurus를 생성하는 방법을 사용했다.
- 하지만 이 과정에서 추가된 term들은 또 다른 문제인 polysemy 문제를 야기함(precision 하락).
2) polysemy를 처리하는 기법의 부재
- 사람이 직접 개입하지 않으면 처리하기 힘듦.
3) 작동방식의 한계
- 각 단어들은 서로 독립적으로 발생한다고 가정하기 때문에 동시발생 횟수에 따른 가중치 고려가 전혀 없음.
Rationale of the Latent Semantic Indexing(LSI) method
Illustration of retrieval problems
* 기존의 term based 검색 방법의 문제점을 살펴보자.
* 테이블 하단에 있는 것은 가상의 query이다.
* REL column의 R 값은 해당 document가 query와 관련이 있다는 것을 의미한다. 관련성에 대한 평가는 사용자에 의해 직접 수행되었다.
* query와 document에서 모두 등장한 단어는 asterisk를 붙였다.
* MATCH column의 M 값은 해당 document가 query와 매치되기 때문에 사용자에게 return될 수 있다는 것을 뜻한다. query에 들어있는 단어가 문서에도 등장하면 query와 문서는 매치된다고 판단한다.
* 문서 1과 2는 기존의 용어 중복 검색 체계의 문제점을 나태나고 있다. 문서 1은 query와 관련성이 있지만, match되지 않기 때문에 사용자에게 return되지 않고, 문서 2는 query와 관련성이 없지만, match되기 때문에 사용자에게 return된다.
유의어 문제
* 위 그림에서 사용자의 관점에 의하면 Doc1에 look-up이라는 단어가 들어있었어야 하고, 검색 시스템의 관점에 의하면 사용자의 query에는 access(혹은 document, retrieval 등)가 들어있어야 한다.
* 이는 문서가 문서가 다루는 주제에 대한 complete discourse 중 일부분만을 담고 있기 때문이기도 하고(특정 주제의 일부분만을 문서가 담고 있음), 검색 시스템을 위해 추출한 index term 또한 마찬가지로 일부만을 담고 있기 때문이다.
* 물론 쿼리도 마찬가지이다.
문제 해결을 위해
* 어떤 term들이 query에의해 암시되는지 정확히 예측해야 함.
* 어떤 term들이 문서에 적용되는지를 찾아내야함.
* 이를 위해 term과 term의 발생 패턴에 대해 분석해야 함.
* Doc 2의 'information'은 잘못된 정보를 우리에게 주고 있다(information의 다의성으로 인해). correlational structure analysis(상관구조분석)를 통해 다의어의 가중치를 줄이는 방법을 사용할 수 있다.
* incomplete하고, unreliable한 set of terms로 구성된 표현을 더 reliable한 entity들로 대체해야 한다. 이를 위해 term과 document의 연관 속에서 고차적인(또는 잠재적인) 구조를 찾아내야 할 것이다.
The choice of method for uncovering latent semantic structure
* latent model을 찾아내기 위해 문서 내의 단어 등장에 대한 matrix를 생성할 것이다.
* latent similarity을 찾기 위해 문서들에서 사용된 term 들의 사용 패턴을 모델링 해야 한다.
* 앞선 문헌들에서는 정보검색을 위한 latent proximity structure를 찾기 위해 아래 2가지 방법을 사용했었다.
기존의 latent proximity structure 찾는 기법
1) hierachical classification analysis
- 단어들과 문서들의 클러스터링을 위해 사용되었음.
- 문서 클러스터링에서 문서간의 거리(유사성)는 어느정도 동일한 단어들을 포함하고 있는지를 통해 정해진다. 그리고 이 문서간 거리를 통해 생성된 행렬은 문서들의 계층 분류를 위한 클러스터링 분석에 사용된다. 검색시 이 structure의 neighborhoods를 탐색하게 된다.
- 시소러스(thesaurus)는 이러한 기법을 활용해 생성되었다.
- 클러스터링의 단점으로는 계층이 너무 제한적이기 때문에 문서들 세트의 풍부한 의미를 담을 수 없다는 점이다. 또한 교차 분류가 불가능하다. 자유변수가 매우 적기 때문에 보통 n개의 objectd에 n개의 파라미터들 밖에 존재하지 않는다.
- 결과적으로 클러스터링은 검색에 대한 계산 효율은 증가시켰지만, retrieval success를 개선했는지는 불명확하다.
2) factor analysis
- 자동 문서 색인화, 검색을 위해 사용
- 이전의 factor analysis는 유사도를 표현한 정방 대칭 행렬을 구성하고, 선형대수를 통해 low dimensional spatial model(비슷한 문서들이 모여있는)을 구성하는 방법을 사용하였음.
- factor analytic model은 clustering model보다 더 풍부한 잠재력을 가지고 있음(n points에 대한 k차원 모델은 nk개의 파라미터를 가지고 있음).
- 그럼에도 단점은 존재하는데, 시간과 비용이 많이 소요되고, 과거에 시도됐던 모델들이 모두 제한된 버전이었고, 인간이 직접 유사성에 대해 판단해야 된다는 점이다.
* 위 2가지와 같은 기존의 접근법은 몇 가지 어려움을 겪었었다. 검색 문제에서는 term, 문서 두 가지가 모두 고려되어야 하는데, 지금까지의 representation들은 하나씩만 다뤘다(term-document를 모두 고려한 clustering이 아닌 term clustering 혹은 document clustering).
논문에서 제시할 새로운 방법
1) reasonable size의 문제를 분석(1000~2000 개의 문서, 5000~7000개의 index terms)
2) term-document relations를 포착하기 위한 rich, high-dimensional(about 100 dimension) representation
3) term과 문서를 동일한 공간에서 represent하는 수학적 기법
4) query term을 통해 문서를 직접 검색(기본 축을 회전하거나 해석하지 않고, intermediate document cluster를 사용하지 않고)
제시될 Model에 사용된 3가지 기준
1) Adjustable representational richness
- multidimensional scaling, factor analysis와 같은 차원수 k를 통해 representational power를 조절 가능한 모델 사용
2) Explicit representation of both terms and documents
- 검색 과정은 새로운 object가 들어왔을 때 적절하게 sematic structure에 배치하고 가까운 문서를 찾는 방식으로 진행됨.
- 이를 위해 rectangular matrix로 시작해 행 및 열 object의 explicit representation을 구성하는 two-mode proximity methods를 사용함. 이를 위해서는 3가지 방법을 사용할 수 있음.
2-1) Multidimensional unfolding
- term,document들은 동일한 공간의 점들로 표현되고 유사성은 점들간의 유클리디안 거리를 통해 측정됨.
2-2) Two mode factor analysis
- term, document들은 동일한 공간의 점들로 표현되고 유사도는 점들간의 inner product로 측정됨.
2-3) Unfolding in trees
- term, document들은 나무의 잎사귀와 같이 표현되고 유사도는 경로의 길이로 측정됨
3) Computational tractability for large datasets
- 기존의 모델의 복잡도는 $N^4, N^5$ 정도이기 때문에 효과적인 fitting techniques를 가진 모델을 사용함.
3가지 기준을 모두 만족하는 모델은?
* 3가지 기준을 모두 만족하는 모델은 two-mode factor analysis이다.
* tree unfolding model은 계산 비용이 높음.
* two mode factor analysis는 SVD를 기반으로 하는 familiar factor analytic model이다.
* SVD를 사용하면 terms, documents를 차원을 선택할 수 있는 공간에 나타내고 dot product나 cosine 값을 통해 유사도를 측정할 수 있다. 또한 시간복잡도 또한 $N^2 \times k^3$ 로 더 빠르다.
SVD or Two-mode factor Analysis Overview
Traditional Factor Analysis
* LSA는 terms by documents matrix를 사용한다. 그리고 matrix에 SVD를 적용해 latent semantic structure model을 찾아낸다.
* 이를 위해 factor analysis의 관점에서 접근해보자.
One-mode Factor analysis
* 한 개의 object로 이뤄진 matrix 사용. ex) document by document matrix
* 유사도 등을 기준으로
* 이 matrix는 eigen-analysis에 의해 두 matrix(eigenvectors, eigenvalues)의 곱으로 분해된다.
* 이를 통해 원본 문서의 similarity behavior는 더 작은 수의 factor들(더 낮은 차원의)의 값으로 근사된다.
Two- mode Factor analysis
* 두 개의 object로 이뤄진 matrix 사용 ex) terms by documents matrix
* matrix는 one-mode에서와 같이 분해되는데, one-mode가 2개의 matrix로 분해되었던 것 과는 다르게 3개로 분해되고, 이 분해 과정을 SVD라고 한다. SVD에는 singular vector들과 singular value들이 포함된다.
* 원본 matrix는 SVD를 통해 더 낮은 차원의 행렬들로 분해된다.
* 유사도는 inner product 혹은 cosine 값을 통해 측정된다.
* SVD를 통해 각 단어들을 orthogonal factor value들로 변환하는 것은 우리가 최초에 제기했던 3가지의 근본적인 문제를 해결해준다.
SVD
* SVD를 통해 우리는 문서 및 단어들을 찾아낸 factor별로 분류할 수 있다. 각 문서 및 단어들의 벡터는 factor에 대한 가중치로 해석한다. 이 때 term, query 혹은 document는 k 개의 factor value들로 표현되거나 k차원의 space에 있는 vector들로 정의 될 수 있다. 이 때 N개의 original index term들은 N보다 작은 k개의 surrogates로 대체되기 때문에 경제적(계산 측면에서)이다.
* 우리는 벡터를 회전시키거나 해석하는 과정은 추가적으로 하지 않고 그저 문서, 단어, 쿼리들을 representation으로 나타내는 것만 목표로 한다.
* factor analysis에서 사용되는 PCA등에서 매우 낮은 차원으로 근사하는 것과 달리 우리는 매우 낮지도 매우 높지도 않은 차원의 벡터들로 original vector들을 근사할 것이다. 즉, original matrix에서 variance를 재생산하는 것 보다 검색시 효율적인 차원으로 근사하는 것에 집중한다.
Query processing
* query가 주어지면 query에 주어진 단어들의 weighted sum을 통해 pseudo-documents를 생성한다. 그리고 이 pseudo-documents와 documents들 간의 cosine 유사도를 측정해 유사한 문서들을 return한다.
SVD Example
* 'Terms' 에 있는 인덱싱된 term들은 1개 이상의 title에서 발생한 단어들이다.
* c1~c5는 human-computer interaction에 관한 documents이고, m1~m4는 graph theroy에 대한 documents이다.
* 위 matrix에 SVD를 적용한 결과이다. SVD 계산에 관한 자세한 내용은 곧 확인할 것이다. 일단 결과만 보자.
* documents는 빈 정사각형으로 표시되며 document 내에 포함하는 단어의 index가 표기되어 있다.
* 단어들은 검정색 원으로 표시되었다.
* latent semantic indexing에 의해 새로 구성된 factor space에서 'human computer interaction'이라는 query를 통해 유사한 문서를 찾아보자.
* 'human'과 'computer'가 factor space에 존재하기 때문에 두 벡터 human, computer 사이에 query를 뜻하는 q가 pseudo-document로서 scaling되어 위치하게 된다.
* pseudo document q와 유사한 단어들(cosine 유사도 0.9 이하)은 점선으로 표시된 범위 안에 존재한다. 유사한 문서로는 c1~c5가 존재한다. 실제로도 c1~c5 모두 같은 토픽인 'human computer interaction'을 공유하며 q역시 동일한 토픽에 포함된다.
* 만약 term-based 검색 시스템이었다면 q와 발생 단어가 겹치는 c1, c2, c4를 return했을 것이다.
* 결과적으로 SVD를 사용했을 때 term-based 방법보다 양질의 검색 결과를 제공하는 것을 확인할 수 있다.
Technical Details
SVD
* term과 document로 이뤄진 t x d matrix X는 다음과 같이 세 개의 marix들로 분해될 수 있다.
$X = T_0 S_0 D_0 '$
* $T_0$와 $D_0$는 orthonormal column들로 이뤄져 있는 orthogonal matrix이다, $S_0$는 diagonal matrix이다.
* $T_0, D_0$ 는 left singular vector, right singular vector이고, S_0는 singular values로 이뤄진 matrix이다.
* $S_0$는 $XX^T, X^TX$를 고유값분해 해서 나오는 고유값들의 square root를 대각원소로 하는 m x n 직사각 대각행렬이다.
* SVD의 결과는 unique하기 때문에 row, column, sign permutation까지 모두 unique하다. $S_0$의 원소는 모두 양수이고, 크기에 따른 내림차순과 같이 배열되어 있다.
* 보통 $T_0$, $D_0$, $S_0$은 모두 full rank이다.
* 만약 $S_0$의 singular values들이 사이즈에 따라 정렬되었다면, k largest까지는 유지되고 나머지들은 0으로 설정될 수 있을 것이다.
* SVD를 통해 분해된 matrix들의 곱을 $Xhihat$이라고 할 때 $Xhihat$은 X에 근사되고 rank값은 k가 된다.
* $S_0$ diagnoal marix이지만 정방행렬이 아니므로 밑 부분에 원소가 모두 0인 row들이 존재한다. 해당 row들을 제거한다. 또한 원하는 크기의 열벡터를 제거하면 행렬 S를 얻을 수 있다.
* 마찬가지로 T와 D에서도 동일한 작업을 해준다. 그러면 위와 같이 reduced model을 얻을 수 있다.
* matrix S의 차원 수 k를 적절히 선택해서 latent structure를 잘 구현하면서 불필요한 디테일을 잘 구현하도록 해야 한다.
Computing fundamental comparison quantities from the SVD model
* 우리는 다음 3가지 비교에 관심이 있다.
1) term i와 j가 얼마나 유사한가?
2) document i와 j가 얼마나 유사한가?
3) term i와 document j가 얼마나 연관되어 있는가?
* 위 3가지 비교를 위해 표준 정보 검색법(기존의 방법)에서는 term-document matrix에서 1)을 위해 두 행을 비교하거나, 2)를 위해서 두 열을 비교하거나, 3)을 위해서 각 cell들을 비교하는 방법을 사용한다.
* 우리는 비슷한 비교 방법을 사용하지만, matrix에 내재되어 있는 중요하고 신뢰성 있는 패턴을 표현하는 $Xhihat$ 을 사용할 것이다. $xhihat$을 사용하면 더 작은 연산이 소요된다는 장점도 있다.
Comparing two terms
* TD matrix에서 두 row vector들의 dot product는 두 term들 간의 유사도를 나타낸다.
* 그리고 matrix $Xhihat Xhihat'$는 모든 term-to-term dot product를 포함하고 있다. 때문에 $Xhihat Xhihat'$를 통해 두 term들 간의 유사도를 확인할 수 있다.
* orthogonal matrix D와 전치행렬 D' 의 곱은 단위행렬이다. 또한 diagonal matrix S와 전치행렬 S'의 곱은 $S^2$ 이다. 때문에 $Xhihat Xhihat'$ 는 아래와 같다.
$XhihatXhihat' = TSD' * (TSD')' = TSD' * DS'T' = (TS)(S'T') = TS^2T'$
* $XhihatXhihat'$은 결국 TS 행렬과 TS행렬의 전치행렬의 곱과 같으므로, $XhihatXhihat'$의 i, j cell은 matrix TS의 row i, row j의 곱을 의미하게 된다. 때문에 TS의 row를 term의 좌표(벡터)라고 생각하면 이러한 점 사이의 dot product를 통해 term들의 비교가 가능하다. T를 좌표로 삼거나 TS를 좌표로 삼거나 동일하다(S가 diagonal이기 때문에 TS는 T의 원소에 diagonal의 대각 성분만큼 scalar곱을 한 것과 같음).
Comparing two documents
* TD matrix에서 두 column vector 들의 dot product는 두 document 사이의 유사도(얼마나 비슷한 term들을 가지고 있는지)를 나타낸다.
* 이번에는 column들간의 비교(document간의 비교)를 위해 $Xhihat'Xhihat$ 를 시행할 것이다.
$Xhihat'Xhihat = DS^2D'$
* 나머지는 term 비교와 동일하다.
Comparing term and documents
* term과 document간의 비교는 cell을 기준으로 이뤄진다.
* $Xhihat$의 (i, j) cell은 $TS^{1 \over 2}$의 i 번째 row, $DS^{1 \over 2}$의 j번째 row의 곱으로 이뤄진다.
Finding Representations for pseudo-documents
* query혹은 pseudo document를 뜻하는 q 와 다른 document를 비교하기 위해서는 term vector $X_{qi}$ 를 구하고 term vector들로 이뤄진 pseudo-document $D_q$를 구성하여 비교해야 한다.
$D_q = X_q ' T S^{-1}$
https://cheris8.tistory.com/11
[정보검색] 검색 성능 척도 :: 재현율 (Recall) & 정확률 (Precision) & F척도 (F-measure)
정보검색시스템의 평가는 검색 성능(retrieval performance)이 가장 중요한 평가 기준이다. 검색 성능에는 검색의 효율성과 검색의 효과성이 존재한다. 검색의 효율성(effiency)이란 검색 속도 혹은 응답
cheris8.tistory.com
머신러닝 - 9. 차원 축소와 PCA (Principal Components Analysis)
차원 축소와 PCA 차원 축소는 많은 feature로 구성된 다차원 데이터 세트의 차원을 축소해 새로운 차원의 데이터 세트를 생성하는 것입니다. 일반적으로 차원이 증가할수록, 즉 feature가 많아질수록
bkshin.tistory.com
https://angeloyeo.github.io/2019/08/01/SVD.html
특이값 분해(SVD) - 공돌이의 수학정리노트
angeloyeo.github.io
