Old fashioned nlp algorithms

1. Boolean Retrieval

(1) Inverted Index

Term-document incidence matrix 는 Boolean 연산 기반으로 Information Retrieval 을 하기 위한 대표적인 방법으로 기본적으로 위의 테이블과 같은 가로축은 문서, 세로축은 단어 형태로 Matrix 를 구성하고, 각 문서 별로 단어가 존재하면 1, 그렇지 않으면 0 형태로 테이블을 구성하는 것을 시작으로 한다. 하지만 이러한 방법은 Matrix 사이즈가 매우 크고 데이터가 Sparse 하기 때문에 이러한 방법으로는 사전을 구성할 수가 없다.

그래서 위와 같은 Inverted Index 라는 형태로 구성을 하게 되는데, 단어별로 해당 단어를 포함하고 있는 문서의 Index 를 List 형태로 데이터를 구성한다. 이렇게 함으로써 데이터의 Spare 함은 해결이 된다고 볼 수 있다.

Inverted Index 를 만드는 과정은 대략적으로 위와 같다고 볼 수 있다. 첫 번째, 문장단위 분리(Sentence Splitting) 및 단어 단위 분리를 위한 (Space Tokenizing) 그리고 복수형 등을 제거하여 Normalize 하여주는 Stemming 등 전처리를 한 후에 각각의 단어에 해당 Document 의 Index 를 추가한다. 아래는 전처리의 대표적인 몇 가지 기법들이다.

단어순 + Doc ID 로 Sort 한 후에 List 형태로 데이터를 구성하여 위에서 설명한 Inverted Index 를 구성하게 된다.

(2) Processing Boolean queries

이렇게 구성한 Inverted Index 에 질의를 날려서, Boolean Retrieval 를 한다고 생각해보 전체적으로 아래와 같은 과정으로 검색이 이루어질 것이다.

쿼리 예시 : BRUTUS AND CALPURNIA

사전에서 BRUTUS 단어의 위치를 찾는다. (세로축에서 위치)
해당 단어가 언급된 Posting List 를 찾는다.
사전에서 CALPURNIA 의 위치를 찾는다(세로축에서 위치)
해당 단어가 언급된 Posting List 를 찾는다.
두 단어를 모두 가지고 있는 Document 를 찾는 작업을 수행한다(아래 설명)
Return intersection to user

두 단어가 모두 발생하는 Document 를 찾는 로직은 아래의 SUDO 코드와 같다. 대략적으로 설명을 해보면 우리가 찾고 싶은 것은 두개의 단어가 모두 등장하는 Doc ID 를 찾고 싶은 것이다. 첫 번째로 위에서 찾은 두개의 단어에 대한 Posting List를 처음 부터 조회해 간다고 생각해보자. 각 단어의 첫번째에 있는 DoC ID 와 두번째 단어에 있는 DoC ID 가 같다면 해당 Document 는 두가지 단어를 모두 포함하고 있는 것으로 Search Result 에 추가한다. 그렇지 않은 경우 DoC ID 가 더 작은 쪽의 ID 를 증가 시키고 첫 번째 Step 부터 반복한다.

(3) Query Optimization

이제 쿼리 최적화에 대해서 생각을 해보자, 아래와 같이 3개의 단어를 검색하는 문제가 있고, 각 단어의 Posting이 아래와 같다고 생각하자. 그렇다면 어떤 단어를 먼저 검색하는 것이 효과적일까? 당연히 가장 짧은 Posting 을 가지고 있는 단어인 Caesar 를 기준으로 하는 것이 좋을 것이다. 3개의 단어의 And 조건인데 Caesar 에 없다면, 모든 조건을 만족하는 Doc ID 는 없을 것일태니 말이다.

아래와 같은 SUDO 코드로 표현할 수 있는데, 결국 Posting 의 사이즈 순으로 Ordering 후 가장 짧은 단어를 기준으로 Intersect 를 수행하는 형태라고 볼 수 있겠다.

(4) Skip Pointers

조금 더 효율적으로 검색을 할 수 있는 방법은 없을까? 이번에는 Skip Pointers 라는 방법을 보도록 하겠다. 이 방법은 위와 같이 Pointer 에 대한 검색을 하나씩하는 하는 것이 아니라 한번에 여러개를 건너 뛰는 것이 핵심이다. 자세한 로직은 아래의 SUDO 코드로 설명하고자 한다.

두개의 Index 가 매치하는 경우 그결과를 리턴하는 로직은 동일하며, 그렇지 않은 경우 더 Index 가 작은 쪽을 증가시키면서 탐색을 하는 방법은 동일하지만, 여기에서 Skip 이라는 방법을 추가하여, Skip 을 하였음에도 비교하는 단어의 Posting 에 있는 Index 가 더 크다면 Skip을 하고 그렇지 않다면 한 포인트만 이동하는 형태로 검색을 수행한다.

그럼 Skip 은 크게 하는게 좋은가? 적게 하는게 좋은가? 크게 Skip 을 지정하면, Skip 을 하지 못하는 경우가 많아질 것이고, Skip 을 작게 하면 한번만 이동해도 되는 것을 여러번 이동해야 할 것이다. 각각 장단점이 있다. e*Root(len(Posting)) 같은 형태로 Skip 사이즈를 정할 수도 있음. 현재는 CPU 가 너무 빨라져서 그닥 속도에 도움을 주지는 못한다고 한다.

(5) Some Problems of Constructing Inverted Index (해결방안은 추후 설명)

여러가지 Document 의 파일 포맷 (PDF, 파워포인트 등) 이 다를 수 있다
유의미한 토큰을 찾는 문제 (문서의 모든 단어가 유의미하지는 않다)
토크나이징 문제(영어는 Space 토크나이징이 되는 것 같지만.. 그렇지 않은 언어는?)
엑센트에 따라 단어의 의미가 달라지는 경우나 사투리 같은 표현
대소문자의 차이에 따른 의미 변화
a, an, the 같은 의미 없는 Stop Words 의 제거(하지만 Stop Words 가 의미에 영향을 주는 경우는?)
Car == Automobile 처럼 철자는 다르지만 의미가 같은 경우
Lemmatization (car, cars, car’s, cars’ → car) 와 같은 표준화 문제
Stemming ( automate, automatic, automation all reduce to automat )

(6) Phrase Query (BiWords)

두개 이상의 단어를 연속적으로 구분으로 인지하고 검색을 해야할 경우에는 어떻게 해야 할까? 첫 번째 방법이 BiWords 이다. 예를들어 3개의 단어가 있다고 하면, Friends, Romans, Countrymen would generate two biwords:“friends romans” and “romans countrymen” 두개의 BiWords 를 구성할 수 있다. 이러한 BiWords 를 단어로 저장하는 방법으로 연속된 두개의 단어 문제는 해결 할 수 있다. 하지만, 구문이 더 길어진다면? 아래와 같이 Extended BiWords 형태를 생각해 볼 수 있겠다. 먼저 형태소 분석을 실행하고 형태소의 형태를 기준으로 BiWords 를 등록하는 형태로 조금더 확장성을 갖을 수 있다. 하지만 이러한 방븝은 False Positive (실제 일치하지 않는 내용을 전부 찾아버리는 문제) 및 너무 긴 구문에 의해서 Index 가 Blow Up 되버리는 문제 등으로 사용하지 않는다.

(7) Phrase Query (Positional indexes)

기존의 Posting 데이터가 단순히 Doc ID 만을 표시 했다면, Positional Indexes 는 Doc ID 와 함께, 해당 단어가 문서 내에서 어디에 표시되는지 순서를 같이 표시한다. 위의 예시를 보면, to be or not to be 를 검색하는데, TO 와 BE 가 동시에 나오는 문서는 1과 4두개 이지만, query 에서 to 다음에 be 가 나온다는 순서적인 정보를 고려하면 일치하는 Doc ID 는 4번임을 유추할 수 있다. 이러한 방법은 BiWords 에 비해서 많은 장점을 가지고 있으며, 구문 검색외에도 아래와 같은 Proximity Search(근접 탐색)에도 사용할 수가 있다.

ex) For example: employment /4 place ==> employment 와 place 가 4칸 내에 존재하는 문서를 찾아라 !

(8) Phrase Query (Positional indexes + BiWords )

굉장히 빈번하게 발생하는 단어 쌍에 대해서는 BiWords 로 단어로 등록하고 Positional Index를 사용하는 방법으로 그냥 Positional Index만 사용했을 때 보다 26% 이상의 검색 속도 향상을 얻어다고 다음과 같은 연구에서 밝히고 있다. (Williams et al. (2004) evaluate a more sophisticated mixed indexing scheme.)

2. Dictionary Data Structure

위와 같이 Inverted Index 를 구성하는데, Dictionary 는 어떤 형태로 저장하고 관리할 것인가? 크게 HashTable 과 Tree 방법이 있을 수가 있다. 먼저 HashTable 형태에 대해서 살펴보도록 하자.

Hash Table 은 빠르다. O(1) 의 복잡도로 원하는 값을 찾을 수 있다. 다만 단점이 있는데, 약간의 차이에 대해서 연관성을 찾을 수가 없다. 그냥 Index 에 등록된 정보만 있기 때문에 조금 차이 인지 많은 차이 인지 알수가 없다. 접두사로 무엇을 찾는다던지 행위를 할 수 없다. (당연히 단어의 알파뱃 구성을 데이터 구조에 반영하지 않기 때문에), 단어는 계속해서 추가되는데 추가 될때마다 Rehasing 하는건 굉장히 비싼 작업이다.

B-Trees 등을 사용하는 경우 Prefix 서치 같은 문제를 해결 할 수 있지만, HashTable 대비 속도가 느리다는 단점이 있다.

3. Tolerant Retrieval

우리가 검색을 할때는 항상 정확한 단어로 검색을 하는 것이 아니다. 가끔 오타가 발생하기도 하며, 특정 패턴을 만족하는 모든 단어를 검색하고 싶을 수도 있다. 여기서는 크게 Wild Card Search, Spelling Correction 그리고 Soudex 에 대해서 설명하고자 한다.

(1) Wild Card Search (with B-Tree)

Tree 구조에서 Wild Card 연산을 한다고 생각해보자, Wild Card 가 제일 뒤에 있는 경우 B-Tree 에서 쉽게 연산을 할 수가 있지만, Wild Card 가 앞에 오는 경우 해당 연산을 Tree 구조로는 처리하기가 어려워 진다. 제일 앞에 있다면, 역순의 Btree 를 또하나 만들어서 처리 할 수 있을 것이다.

그렇다면 만약에 Wild Card 가 단어 중간에 있다면? 많은 B-Tree 연산과 And 연산으로 나눠서 계산해야만 할 것이고 이는 매우 비싼 비용을 요구하게 될 것이다.

그래서 Permuterm Index 라는 개념을 제안하고 있는데, 아이디어 자체는 간단하다. $ 라는 문장의 끝을 나타내는 Special Char 를 정의하여, Wild Card 가 단어의 중간에 오더라도 WildCard 를 제일 위로 보내서 검색할 수 있도록 Trick 을 쓰는 것이다. 대신 하나의 단어에 대해서 모든 Wild Card 경우의 수를 만들고 이를 Index 에 등록해서 Tree 구조로 저장할 필요가 있겠다. 즉, 문제는 저장해야 하는 Index 의 사이즈가 너무 커지는 것이다.

(2) Wild Card Search (with K-Gram Index)

K-Gram, N-Gram 등의 원리는 간단하다. 2-Gram 이라고 한다면, 대상 단어를 Window Size 2의 Filter 로 슬라이딩하면서 슬라이싱 하여, 각 구성요소를 해당 단어의 Index 로 저장하고, Wilde Card 검색시에는 각 Piece 들의 조합으로 해당 단어를 검색하면 된다.

(3) Spell Correction

오타에 대한 보정은 검색에서 (Information Retrieval)에서 중요한 문제로 크게 두가지로 정의될 수 있다. 하나는 단독적으로 해당 단어만 보고 오타를 찾는 것과, 주변 문장의 맥락을 보고 그 의미를 파악하는 것이다. 여기서는 몇 가지 대표적인 방법들을 다뤄 보도록 하겠다.

(3) Spell Correction (Edit Distance)

원리는 매우 간단하다, 사용자가 검색한 단어와 사전에 가지고 있는 여러가지 단어 간의 Edit Distance (수정하기 위해서 필요한 비용)을 구하여 가장 비용이 적은 단어를 원래 의도했던 단어로 해석하는 형태이다. 수정 비용이란, 삽입, 삭제, 변경 등이 있는데 각 Weight 는 정의에 따라 달라질 수 있다.

(3) Spell Correction (Weighted Edit Distance)

위와 동일한 원리에 가중치를 두는 방안이 있는데, 예를들면 m과 n은 키보드 상에 붙어 있어, 오타가 발생할 확률이 높으니, 두 단어 간의 Replace 는 다른 단어 간의 교환 비용보다 더 작은 비용을 부여하는 등의 형태이다.

하지만, 이런 방법으로 우리가 가진 모든 사전에 있는 단어와 비용을 계산하기란 매우 느리고, 많은 비용이 드는 일일 것이다. 이러한 문제를 해결하기 위하여 N-Gram 방법을 제시한다.

(3) Spell Correction (N-Gram)

위와 같이 비교하고자 하는 단어를 N(1이 될수도, 2가 될수도..3이 될수도) 개의 캐릭터 단위로 쪼개고 각 단위별 일치 정보로 단어간의 유사도를 계산하는 방법이다. 대표적인 Metric 으로는 Jaccard Coefficient 가 있으며 방법은 아래와 같이, 비교하고자 하는 단어 포함 전체 토큰의 수 중에 일치하는 토큰의 수로 정의할 수 있다.

(3) Spell Correction (Context Sensitive Correction)

해당 단어 뿐만 아니라, 앞뒤 문맥을 보고 어떤 단어를 사용자가 최초에 의도 하였었는지를 판단하기 위한 방법으로, 대표적으로 베이지안 등이 있다.(추후 재 정리)

(4) Soundex

사람들이 주로 많이 하는 실수가 소리나는 그대로 타이핑해서 나는 문제라는 가정하에 비슷한 소리가 나는 알파뱃들을 동일한 코드로 치환하여 비교하는 방식으로, 대부분의 데이터 베이스에서 제공하는 기능이지만, 검색기능에서는 그다지 사용하지 있지 않다.

4. Language Model

(1) Definition of probabilistic Language Modeling

문장에 대한 확률이나, 단어의 순서에 대한 확률을 구하는 것을 그 목적으로 하며, 예를들면 앞에 1~n-1 까지 단어가 주어졌을때, n 에 올 단어의 확률을 구하는 그런 모델을 Language Model 이라고 정의한다.

(2) How to compute P(W) – Chain Rule

Chain Rule 을 사용하여, 위에서 정의한 P(W) 를 구할 수 있다. 그런데 과연 각각의 확률은 어떻게 구할 것인가? 아래와 같은 형태로 동시 발생 확률을 구해야 하는데, 과연 가능한가? 너무 많은 케이스가 존재하고, 모든 경우를 계산하기에 충분한 데이터를 확보하지 못하게 될 것이다.

(2) How to compute P(W) – Markov Assumption

모든 케이스를 계산할 수 없으니, 앞에 한개, 두개와 같이 일부 단어만 확률 계산시 사용하자는 아이디어가 Markov Assumption 이다. Bi-Gram 으로 확률을 구한다고 생각하면, 아래와 같은 간단한 표로 동시 발생 확률을 표현 할 수 있다.

그리고 데이터를 Normalized 해주면 다시 아래와 같은 표로 표현될 수 있을 것이다.

그러면 LM 모델을 각 단어의 이전 단어와 동시 발생 확률의 곱으로 표시할 수 있는데 위의 그림처럼 데이터가 0인 필드가 존재하여, 전체 확률이 0이 되는 문제가 발생할 수 있다. 이러한 Underflow 현상을 피하기 위하여 log 를 취하여 Log 의 합으로 LM 모델을 표시 할 수 있다.

하지만 이러한 모델도 Train 데이터에서 발생한, 케이스에 대해서만 잘동작하는 일반화가 되지 안흔 문제가 있다. 이러한 문제를 Zeros 라고 하며 아래와 같이 Train 데이터에서 발생하지 않은 케이스에 대해서는 아래와 같이 확률이 0이 되는 문제 발생.

(3) Add-one estimation (Laplace smoothing)

분자에 1을 더해 주고, 분모에는 Vocab 사이즈 이렇게 추가하여 주면, 즉 이렇게 Smoothing 을 하여 주면, 원래 0으로 표현되던 영역의 데이터들이 0 이상의 숫자로 표시되는 것을 볼 수가 있다.

그리고 약간의 응용으로 Add-K 라는 방법도 존재하며 수식은 아래와 같다.

(4) Spell Correction (Noisy Channel – 1Char Error Case)

오타 수정 문제에 대해서 이야기 해보자, 오타 수정에는 크게 두가지가 있는데, 하나는 사전에 없는 단어가 발생했을때, 사전에 있는 단어로 맵핑하는 Non-word 문제와 사전에는 있지만, 다른 의도로 타이핑 했을 수 있는 가능성에 대한 Real World Spelling error 문제가 있다. 전자의 경우 Edit Distance 를 사용하거나 Noisy Channel 을 사용할 수 있을 것이고, 후자의 경우 발음상 유사한 것이나 스펠링상 유사한 것을 찾는 행위들이 필요할 것이며, 구체적으로는 Noisy Channel 을 사용하거나 별도의 Classifier 를 사용하는 형태가 될 것이다.

Noisy Channel 이란 아래와 같은 형태로 정의할 수 있는데, 간단히 말하면 베지안 정리라고 보면 된다. 여기서 x 는 오타로 추정되는 단어이고, w 는 보정된 단어이다. 하지만 어떤 오타일때, 실제 의도가 어떤 단어였다라는 확률적인 분포는 우리가 가지고 있지 않기 때문에, 베이지안 정리를 이용하여, 특정 단어(사전에 있는)가 발생할 확률과 해당 단어가 오타날 확률의 곱으로 대체하여 사용할 수 있다.

한 단어가 틀렸다고 가정하면, 아래와 같은 Confusion Matrix 로 오타가 발생할 확률을 구할 수 있을 것이다. (아마도 키보드 구조에 따른 오타 가능성, 인접한 키보드 기리의 간섭)등을 반영한 확률이 될 것이다.

자 그러면 위의 베이지안에서 P(x|w) 는 위의 표를 통해서 구할 수 있게 된다. 그럼 실제 베이지안 정리를 이용하여, 오타를 보정하는 예제를 들어 보자. 예를들어서 acress 라는 오타가 있다고 해보자. 그러면 원래 의도된 단어는 무엇 이엇을까?

한단어 기준이니까 원래 단어가 across 였다면, P(x|w) 는 원래 ‘o’ 인 것을 ‘e’ 로 오타낼 확률이 될 것이고, P(w) 는 전체 코퍼스에서 ‘o’ 가 발생할 확률이 된다. 그리고 P(w|x)즉 오타 ‘e’ 가 실제 ‘o’일 확률은 P(x|w)*P(w) 이 될 것이다.

(4) Spell Correction (Noisy Channel-Word level)

순서의 조합의 확률이 가장 큰 경우를 선택하는 형태로 진행. 아래는 예시

5. Text Classification

(1) Naive Bayes

위에의 예에서 보면, 우리는 주어진 문서 (Document, Class) Set 으로 부터 긍정인 문서에서의 단어별 발생 빈도와 부정인 문서에서의 단어별 발생 빈도를 구할 수 있게 된다.

원래 우리가 알고 싶은건 P(C|X) = P(단어1| 클래스|)* P(단어2 | 클래스| ) …. * P(클래스) 즉, 클래스가 긍정인 문서들에서 어떤 단어가 나올 확률들의 곱 * 해당 클래스의 발생 확률로 해당 문서의 긍/부정을 확률적으로 판단할 수 있다.

예제를 하나 보자. 클래스 C 일 확률 = P(c) 는 전체 4개 데이터 중 3개로 3/4 이 된다.
그리고 클래스 J 일 확률 = P(j) 는 전체 4개 데이터 중 1개로 1/4이 된다. 그럼 이제 구해야 하는 것은 각 단어별 우도(동시 발생 확률)이다. 예를들어 ‘Chinese’ 가 C 라는 클래스에서 발생할 확률은 전체 단어 8개 중에 5개 이니까 5/8이지만 여기서는 라플라스 스무딩을 사용하여, (5+1)/(8+6)이 이 된다. V 는 고유 단어 수로 6개가 되겠다. 결국 TEST 인 5번 Doc 의 클래스는 c일 확률이 더 높다.

(4) Markov Chain

Markov Chain 은 기본적으로 Chain Rule 을 따르며, UniGram 방식으로 바로전 상태에서 현재 상태로 전이할 확률들의 합으로 다음 행동의 확률을 계산하는 방법이다.

두번째 Step 에서 해가뜰 확률을 구해보자, 처음 시작은 Sun 상태로 시작한다. 그럼 처음 상태에서 해가뜰 확률은 P(SUN) = 1.0, 비가올 확률은 P(RAIN) = 0.0이 된다. 그리고 해가 떴을때, 다시 해가뜰 확률은 0.9, 비가 온후에 해가뜰 확률은 0.3이 된다. 계산해보면 0.9*1.0 + 0.0*0.3 = 0.9이 된다. 반대로 비가올 확률은 0.1*1.0 + 0.0*0.7로 0.1이 된다. 그럼 두번째 Step 에서 상태는 0.9, 0.1이 된다. Step 3에서는 다시 해가뜰 확률은 0.9*0.9 + 0.1*0.3 = 0.81 + 0.03 = 0.84 , 비가올 확률은 0.9*0.1 + 0.1*0.7 = 0.09+0.07 = 0.16 이 된다. 이렇게 계속 확률을 계산하다보면 (무한대까지)

어떤 상태에서 시작해도 (위의 예는 Sunny 1.0)에서 시작했지만, 계속 수행하다 보면 같은 확률로 수렴한다. 구글에서는 이러한 원리를 이용하여, 특정한 시점에 사이트간 REF 정보를 수집하여 사이트의 중요도로 사용하고 있다.

5. Scoring, Term Weighting & Vector Space Model

(1) Ranked retrieval

Boolean 형태의 검색의 문제는 아주 정확하게 검색을 하지 않으면 원하는 검색 결과를 얻을 수 없고, 그것은 일부 전문가 시스템이 아닌 일반적인 검색엔진에서 고객들이 원하는 형태의 검색이 아니라는 문제가 있다. 이러한 문제에 대한 해결 방법으로, 질의에 대한 관련도 순으로 페이지를 정렬하여 제공하는 방법을 Ranked Retrieval 이라고 한다.

(2) Scoring documents

검색 결과를 Ordering 을 하기 위해서는 어뻐한 기준으로 Scoring 을 해야만 할 것이다. N-Gram 에서 Jacaard 스코어를 구했던 것을 생각해보자. 이 방법을 사용하여, 단어간의 형태적 유사성을 사용하여 스코어를 구하고 Ordering 을 할 수 있을 것이다. 하지만 이러한 방법은 단어의 발생 빈도등으 고려하지 않는 단점이 있으며, Length 에 대한 Normalization 을 고려할 필요가 있다.

(3) Term Frequency

Doc 에 발생하는 단어의 빈도를 가지고, 해당 문서를 표상하는 방법을 Bag of Words 라고 하며, 아래의 예시와 같이, 단어의 순서가 전혀 다른 두 문장도 동일하게 표상된다는 문제가 있다. 이러한 문제를 해결하는 Positional Information 의 삽입에 대해서는 나중에 이야기하도록 하고, TF-IDF 개념에 대해서 이야기 해보도록 하자.

(4) Collection statistics

위와 같은 테이블을 만들때 아래와 같은 TF-IDF 공식을 이용해 만들게 되면, 무의미하게 자주 나오는 전치사등의 가중치는 적어지고, 해당 문서에서만 고유하게 나오면서 빈도가 큰 단어들의 가중치가 커지게 된다. (여기서 N은 전체 Doc 수)

이제 Score 는 아래와 같이 조회한 단어를 기준으로 해당 단어에서의 가중치의 합으로 구할 수 있겠다.

(5) Vector space Scoring (Query as Vector)

질의도 Vector 로 바꿔서 질의와 문서 간의 유사도를 구할 수는 없을까? 아래와 같은 공식으로 두개의 Vector 간의 거리(각도?)를 구할 수가 있다.

Cosine Similarity (d1, d2) = Dot product(d1, d2) / ||d1|| * ||d2||

Score 를 구하는 SUDO 코드는 아래와 같다. 검색어를 q 라고 하고, q는 여러개의 term 으로 이루어 져있다고 할때, 각 term 에 대해서 Inverted Index 에서 해당 term 을 가지고 있는 Doc 을 찾아서 해당 Doc 의 Vector 와 검색어 Term 의 Vector 를 곱한 값을 각 Doc 별로 누적한다. 그 후에 Doc 에 누적된 값을 Doc 의 길이로 Normalize 한다. 그것이 최종적으로 각 Doc 단위의 Score 가 된다.

(6) NET Score

실제 검색 문제에 어떻게 지금까지 배운 것을 적용해 볼 것인지 고민해 보자. 우선 맨처음에 설명했던 Inverted Index 구조를 다시 생각해 보자. 가장 최근에 설명한 TF-IDF 기반으로 Doc 과 Query 의 유사도를 Scoring하는 것을 consigin(q,a) 라고 생각해보자. 그리고 우리가 알고 있는 어떤 문서의 중요도(많이 참조가 된다던지) 를 g(a) 라고 하자, 그러면 우리는 이 두개 Socre 의 선형적인 결합을 통해 Posting 을 정렬할 수 있다. (Default 는 그냥 Index 순서 따위.. )

그리고 빠른 검색을 위해 두 개의 Tier 로 Index를 High 와 Low로 나눠서 관리하는데, High 는 Score 상위k개에 대한 Index이고 Low 는 그 외에 대한 Index이다. 실제 검색시에는 High 에 대해서만, 위에서 배웠던 여러가지 기법들을 통해 빠른 속도로 중요하고, 키워드와 관련이 높은 문서를 찾아낼 수 있을 것이다.

6. Dimension Reduction

지금까지 문서 및 질의를 어떻게 Vector 공간에 표상하고, 어떤 Metric 으로 그 유사도를 측정하여 검색에 사용할 수 있는지 이야기 하였는데, 이러한 방법은 Vocab Size 에 따라 Vector Size 가 너무 커진다는 문제가 있다. 때문에 여러가지 방법으로 이 Dimension Size 를 줄이기 위한 연구들이 진행되었다.

(1) SVD (Singualr Value Decomposision)

(2) PCA(Principal Component Analysis)

(3) Word2Vec

7. 성능 평가

(1) Cohen’s kappa coefficient

(2) Pearson’s Correlation Coefficient

(3) Accuracy

(4) Precision, Recall and F1 Score

(5) Area under curve

8. Examples

1. Consider theses documents

Doc 1    breakthrough drug for schizophrenia
Doc 2    new schizophrenia drug
Doc 3    new approach for treatment of schizophrenia
Doc 4    new hopes for schizophrenia patients

A. What are the returned results for “new AND drug”
==> Doc2

B. What would be ranked highest for the same query keywords (in tf-idf ranking)
==> Doc2

C. Give an example query, that would return no result without lemmatization, but some
results with lemmatization.
==> patient AND drugs

D. Among the words used in these documents, which word would be evaluated first (when
used as a query keyword) in Boolean query processing?
==> Posting Size 가 1인 단어는 모두 동일하지만, 두번째 정렬 기준이 알파뱃이라면 approach 가 될 듯

E. Explain how the skip pointer reduces processing cost?
==> AND 연산이라고 할때, 두개 단어 중 적은 포인트를 가지고 있는 쪽에서 기존에는 1씩 증가하여 검색을 하는데,
이를 특정 단위로 Jump 하면 검색에 소요되는 시간이 절감 될 수 있음.

2. The inverted index below shows the position of terms in documents in the format of “term: doc1: <position1, position2, ..>; doc2:”. (3 points each)

(a) Find the most frequent 2-word phrase, and build its biterm inverted index in the above format.
==> RUSH IN : 2 : {2} ; 3 : {9} ; 7 : {4}

(b) For phrase queries ranked by proximity, what information should be added to enable early termination by TA algorithm?

(c) Explain why TA algorithm terminates early for a monotonic ranking function.Explain how a wild card query he*llo can be supported by permuterm index. (3pts)

==> 일반적인 B-Tree 로 he* 에 대한 연산 ( he<= words < hf )
Inverse Ordered B-Tree <뒤에서 앞으로> : oll* 연산 (oll <= words < olm )
두 개의 결과를 AND 연산하는 형태로 he* AND oll* 형태로 연산한다.
==> Permuterm 의 경우 llo$he* 형태로 변환하여 Wild Card 를 제일 뒤로 보내 연산 할 수 있을 것이다.

3.Give an example query supported by soundex, but not by permuterm index (3pts)

==> 검색어 : zuzoziza , 도큐먼트 : zazizozu
==> a,i,o,u 등 모음은 0으로 치환, 기타 유사 발음 단어 정해진 숫자로 치환 즉 위의 검색은 가능

4.Explain how the similarity between “permuterm” and “permutation” can be computed by Jaccard similarity on 3-grams (3 pts)

==> permuterm => $$p, $pe, per, erm, rmu, mut, ute, ter, erm, rm$, m$$
==> permutation => $$p, $pe, per, erm, rmu, mut, uta, tat, ati, tio ion, on$, n$$

==> 일치 6개, 전체 고유 토큰 수 19개
==> Jaccard Score = 6/19

5.Explain how language model can be used for spelling correction in search engine (3 pts)

==> 크게 단어가 사전에 존재하지 않는 경우와 , 원래 의도한 단어와 다른 단어를 입력한 경우 두 가지가 있겠다.
단어가 오타 하나라고 하면, 우리가 찾고 싶은 것은 P(원래단어|오타단어) 어떤 오타 단어가 실제 어떤 단어를 의미
했을지 확률인데, 이 확률은 구하기 어렵기 때문에 베이즈 정리에 의해서 P(원래단어|오타단어) = P(오타단어|원래
단어)*P(원래단어) 형태로 해당 오타가 발생할 확률은 구하여, 가장 확률이 높은 것을 고르는 형태가 되겠다.

만약에 실제 상황에서의 오타라고 하면, 앞뒤 문맥을 보고 판단을 할 필요가 있을 것인데, Bi-Gram LM 을 사용한다
고 생각해보면 I am boy 가 원래 의도 했던 문장이고, 가능한 조합이 I ji boy, I jo boy 여러가지 CASE 가 생길 수 있
다면, P(am|I) I가 나올때, am 이 나올 확률 (엄밀히는 (count(I + am) + 1) / (count(I) + V))형태로 확률을 구하고, 같
은 방법으로 P(am|I) * P(boy|am) = log(P(am|I)) + log(P( boy|am)) 형태로 표현될 것이고. 모든 경우 수에 대해서 확
률을 구해보면, 가장 높은 확률에 해당하는 조합이 원래 의도일 확률이 높다고 가정할 수 있을 것이다.

6.Explain what (a) map and (b) reduce function should do, for building an inverted index when documents are partitioned into 1000 computers. (3 points each)

==>

7.Explain how language model works to identify query keywords (hot,dog) are likely to be a phrase query (3 points)

==> BiGram 형태로 연속 발생 확률을 구하고, 그 확률이 어느정도 이상인 경우 Phrase 로 처리 할 수 있다

8.Write down how the topics discussed in the first half that can help your research (or, future topics that I can teach to help your research) (2pts)

==>