Information Retrieval and Web Search

Information Retrieval and Web Search

Web Search은 편리함과 풍부한 정보의 양 때문에, 정보검색(Information Retrieval) 분야에서 많이 사용되어 왔고, Web Search는 사용자가 필요한 정보를 많은 문서(large collection of text documents)에서 찾는 것을 도와주는 IR(Information Retrieval)에 기반한다.
전통적인 IR에서는 기본적인 정보 단위를 문서(document)라하고, 많은 문서의 집합들은 text database 형태를 취할 수 있다고 생각하였다. 이는 Web에서는 Web Pages이다.

정보를 검색한다는 것은 간단하게 사용자 query와 관련성이 있는 문서들을 찾는것을 의미하고, 찾아진 문서의 ranking은 사용자 query와의 관련성 점수를 의미한다. 가장 일반적으로 사용되는 query의 형태는 단어(term)들을 나열한 query이다. Text에 있는 정보들은 구조화 되어있지 않는(unstructured)것과 다르게, Database에 있는 데이터들은 구조화 되어있고, relational table에 저장되어 있기 때문에, IR은 SQL을 이용해 데이터를 검색하는 것과는 다르다. Text 검색에서는 query language인 SQL이 존재하지 않는다.

Search Engine은 간단한 기존의 IR 모델의 application이 아니다. Search Engine이 IR의 결과들을 이용하긴 하지만, Search Engine만의 고유한 기술들이 필요하고, IR에 대한 많은 문제점들이 존재한다.

1. Web Search에서는 효율성이 가장 중요하다.
   예전 IR 시스템에선 많은 문서들이 존재하지 않아 중요하지 않게 생각했던 효율성이 현재에는 가장 중요한 issue이다.(2000년 기준, Google은 100억개 이상의 문서를 관리한다)

2. 웹 문서들은 기존 IR 시스템에서 사용되던 문서들과 상당히 다른 차이점이 존재한다.

   • Hyperlink와 Anchor Text가 존재한다.
     Hyperlink는 문서를 검색하고, 그 값을 rank하는 알고리즘에서 아주 중요한 역할을 한다. Anchor Text는 hyperlink와 마찬가지로, 종종 hyperlink가 가리키고 있는 웹 문서보다 더 정확한 설명을 갖고 있다.

   • 웹 문서는 Semi-Structured이다.
     웹 문서들은 기존 전통적인 문서들마냥 간단한 몇개의 절로 구성되어 있지 않다. 대신 웹 문서들은 Title, Metadata, body 등과 같은 몇몇 다른 필드들을 갖고 있고, 이 필드 안에 있는 정보들은 다른 것들보다 더 중요한 의미를 갖는다.

3. Spamming이라는 중요한 issue가 있다.
   기존 IR 시스템에선 이러한 issue가 존재하지 않았지만, Rank라는 것이 중요한 Search Engine에서는 spamming에 대해 아주 중요하게 다뤄야 한다. 만약 검색한 query와 연관성 있는 문서가 존재하지만 정말 낮은 곳에 ranking되어 있다면, 사용자들은 그 문서를 보기가 힘들 것이다.

오늘날에는 Google 검색 결과에 상위 노출 되기 위해서 많은 기법들이 있다

Basic Concepts of Information Retrieval

Information Retrieval(IR)은 사용자들이 필요로 하는 문서를 찾는 것을 돕는 연구이다. 기술적으로는 Acquisition, Organization, Storage, Retrieval, Distribution of Information에 대해서 연구한다.

아래 그림은 IR 시스템의 기본 아키텍처에 대한 그림이다.

위의 그림에 대해 설명하자면,
1. User Query를 query operations모델을 이용해 retrieval system에 요청한다.
2. retrieval module은 document index를 이용해 query에 포함된 term들과 연관된 문서들을 검색한다.
3. 검색된 문서들과 query의 연관성을 계산해 rank하여 사용자에게 보여준다.

Document collection은 text database라고도 불리며, 효율적인 검색을 위해 indexer에 의해 색인된다.

User Query는 사용자가 필요한 정보를 의미하는데, 이는 몇가지 형태를 취한다.

1. Keyword Queries
2. Boolean Queries
3. Phrase Queries
4. Proximity Queries
5. Full Document Queries
6. Natural Language Questions

Information Retrieval Models

IR 모델은 document와 query가 어떻게 나타나고, document와 사용자 query의 관계를 어떻게 정의하는지에 대해 다룬다. IR에는,

• Boolean Model
• Vector Space Model
• Language Model
• Probablistic Model

의 4 개의 모델이 존재한다. 그리고 IR System과 Web에서 일반적으로 사용되는 모델은 처음 세 개(Boolean, Vector Space, Language Model)의 모델이다.

비록 세 개의 모델이 document와 query들을 다르게 표현할지라도, 똑같은 프레임워크를 사용한다. 세 개의 모델은 각 document 혹은 query들을 word(단어) 혹은 term(용어)의 "bag"로 다룬다. 이 때, term과 document의 순서는 무시한다. 즉 document는 구분되는 term들의 나열로 표현될 수 있다. 이 글에서 나오는 term은 사전에 나오는 자연어 단어가 아니라는 점을 유의해야한다.

각각의 term은 가중치(weight)와 연관되어있다. 문서 \(D\)의 집합(collection)이 주어졌을 때, \(V = \{t_1, t_2, ..., t_{\mid V \mid}\}\)를 집합에서의 유일한 term들의 나열이라 한다면, 집합 V는 집합의 vocabulary(어휘)라고 불리고 \(\mid V \mid\)는 집합의 크기라고 할 수 있다. 예를 들어, \(V\)에서 term의 개수,

Boolean Model

Boolean Model은 가장 먼저 연구되었고, 가장 쉬운 Information Retrieval(정보검색) 모델이다. 이 모델은 사용자 query에 맞는 document를 찾는 개념을 이용했고, query와 retrieval(검색) 둘다 Boolean 수식에 기반했다.

Document Representation

Boolean 모델에서 documents와 queries는 단어들의 집합들로 나타난다. 즉, 각 단어의 존재 유무만 고려하면 된다. 위의 document vector 표현을 사용했을때, term \(t_i\)가 document \(d_j\)에 나타나면, document \(d_j\)에서 term \(t_i\)의 가중치 \(w_{ij}(\sqsubseteq{0,1})\)는 1이고 아니면 0의 값을 갖는다.

\[
W_{ij} = \left\{\array{
1\mbox{ if } t_1 \mbox{ appears in } d_j \\
0\mbox{ otherwise.} \\
} \right.
\]

Boolean Queries

query term들은 AND, OR, NOT과 같은 논리연산들을 이용해 만들어져있어 Boolean query는 정확한 논리적 의미를 갖게 된다. 예를 들어, query ((\(x\) AND \(y\)) AND (NOT \(z\)))는 term \(x\)와 \(y\)는 무조건 포함하고, \(z\)는 무조건 제외된 검색 결과를 의미한다. 다른 예로, query (\(x\) OR \(y\))는 \(x\)와 \(y\) 중 적어도 하나는 포함하는 검색 결과를 의미한다.

Document Retrieval

Boolean query가 들어오면, 시스템은 모든 문서에서 논리적으로 일치하는 결과를 보여준다. 그러므로 이 모델의 검색은 decision criterion에 기반한다고 할 수 있다. 그리고 이 모델의 특성상 문서 검색에서 부분 일치 혹은 랭킹이라는 개념이 존재하지 않는 치명적인 단점으로 문서 검색 시에 나쁜 결과를 출력한다.

이러한 문제점으로 Boolean Model은 단독으로 사용되는 경우는 거의 존재하지 않고, 대부분의 검색 엔진들은 inclusion, exclusion 연산자를 사용하는 제한된 Boolean Model을 지원한다.

Vector Space Model

이 모델은 가장 잘 알려지고 IR 모델에서 넓게 사용되는 모델이다.

Document Presentation

Vector Spacee Model에서의 document는 weight vector(가중치 벡터) 나타나고, 각 요소들의 가중치는 TF 혹은 TF-IDF scheme의 변화에 따라 계산된다. Boolean Model에서와 달리 document \(d_j\)에서 term \(t_i\)의 가중치 \(W_{ij}\)의 값은 더이상 {0, 1} 사이의 값이 아닌 어떠한 값도 가질 수 있다.

Term Frequency(TF) Scheme

이 모델에서 term \(t_i\)의 weight는 문서 \(d_j\)에 나타나는 \(t_i\)의 개수를 의미한다. 하지만 TF Scheme은 대부분의 문서에서 특정 term이 나오는 상황을 고려하지 않는다는 단점이 존재한다.

TF-IDF Scheme

이 것은 가장 잘 알려진 weighting scheme이다. 여기서 TF는 위에 나온대로 term frequency를 의미하고, IDF는 inverse document frequency를 의미한다.

Inverse document frequency는 특정 단어가 나오는 문서의 개수의 역수 값을 의미

\(N\)을 시스템에서 문서의 총 개수라하고, \(df_i\)를 term \(t_i\)가 한 개 이상 나오는 문서의 개수라 한다. 그리고 \(f_{ij}\)를 문서 \(d_j\)에서 term \(t_i\)의 빈도라 할 때, \(d_j\)에서 \(t_i\)의 nomalized term frequency(\(tf_{ij}\))는 아래 식으로 계산할 수 있다

\[
tf_{ij} = \frac{f_{ij}}{max\{f_{1j}, f_{2j}, ..., f_{\mid V \mid j}\}}
\]

만약, term \(t_i\)가 \(d_j\)안에 나타나지 않을 경우 \(tf_{ij}=0\)이다.

term \(t_i\)에 대한 inverse document frequency(\(idf_i\))는 아래 수식에 의해 계산된다.

\[
idf_i = \log \frac{N}{df_i}
\]

이 IDF는 전체 문서에서 특정 단어가 얼마나 나오는지 나타내는 값이고, 이 값이 높으면 그 단어는 중요도가 떨어진다는 의미이다.

결론은 TF-IDF를 이용한 가중치 계산은 아래의 수식으로 할 수 있다.

\[
W_{ij} = tf_{ij} \times idf_i
\]

Queries

query q는 document와 정확히 같은 방식으로 다뤄진다. 설명하자면, q에서 term weight \(w_{iq}\)는 일반적으로 document와 유사한 방식으로 계산되고 그 식은 아래와 같다.

\[
W_{iq} = \big(0.5 + \frac{0.5f_{iq}}{max \{f_{1q}, f_{2q},...,f_{\mid V\mid q}\}} \big)\times log{\frac{N}{df_i}}
\]

Document Retrieval and Relevance Ranking

document가 입력한 query와 연관이 있는지 결정하는 것은 어려운 일이다. 하지만 Boolean Model과 달리 Vector Space Model은 이러한 결정을 할 필요가 없다. 이런 결정을 하는 대신, 검색된 결과를 갖고 degrees of relevance(연관 정도)를 갖고 ranking을 한다. degree of relevance를 계산하는 한가지 방법은 문서 집합 \(D\)에서 각 문서 \(d_j\)와 query q와의 유사성을 계산하는 방법이다. 유사성을 계산 하는 방법은 여러가지가 존재하지만 가장 유명한 것은 consine similarity이다. cosine similarity는 document vector \(d_j\)와 query vector q의 consine 값을 계산하는 방법이다.

\[
cosine(d_j, q) = \frac{d_j\bullet q}{\|d_j\|\times\|q\|} = \frac{\sum_{i=1}^{\mid V\mid}W_{ij} \times W_{iq}}{\sqrt{\sum_{i=1}^{\mid V \mid}W_{ij}^2} \times \sqrt{\sum_{i=1}^{\mid V\mid}W_{iq}^2}}
\]

또 다른 유사성 계산 방법은 2 개의 vector를 곱해 계산 하는 방법이다.

\[
sim(d_j, q) = \langle d_j \bullet q\rangle
\]

Document Rank는 위의 유사성 계산으로 구한 값을 이용해 할 수 있다. 여기서 계산되어 가장 높은곳에 랭크된 문서는 input으로 입력한 query와 가장 유사하다고 판단한다.

또다른 degree of relevance 계산 방법 = Okapi 추후 추가.

Statistical Language Model

Statistical language model은 확률, 통계학에 기반하여 만들어졌다. 기본 개념은 간단한데, 각 문서에 대해 language model을 추정한다. 그리고 주어진 language model의 query 확률로 rank한다. 이와 유사한 개념으로는 NLP(Natural Language Process)와 음성인식(Speech Recognition)에서 사용돼 왔다.

이제 실제 수식으로 살펴보자면,

query \(q\)를 단어(term)들의 나열이라고 하자, \(q = q_1q_2...q_m\)이고 문서들의 집합을 \(D\)라 하면, \(D=\{d_1, d_2, ..., d_N\}\)이다. 이러한 language model 접근법에서, 문서 \(d_j\)의 확률 모델에 기반하여 생성되는 query \(q\)의 확률을 고려해야 한다.(ex: \(Pr(q \mid d_j)\))

위의 과정 이후, 검색된 문서의 ranking을 구하기 위해선 Bayes rule을 이용해 \(Pr(d_j \mid q)\)에서의 확률을 계산해야한다.

\[
Pr(d_j\mid q) = \frac{Pr(q\mid d_j)Pr(d_j)}{Pr(q)}
\]

Ranking에서 모든 문서에 대해 \(Pr(q)\)가 같을 필요는 없지만, \(Pr(d_j)\)는 대부분 동일한 값이고 ranking에 영향을 주지 않는다. 그러므로 \(Pr(q\mid d_j)\)만을 계산하면 된다.

기본적으로 language model은 unigram에서 작동한다. 즉 language model은 각각의 단어들이 독립적으로 생성된다고 가정한다. 이 의미는 단어에 대해 다항분포(multinomial distribution)을 따른다는 것이다.
multinomial distribution과 unigram 모델에서, 아래의 수식을 이용해 계산할 수 있다.

\[
Pr(q=q_1q_2...q_m\mid d_j) = \prod_{i=1}^{m}Pr(q_i\mid d_j) = \prod_{i=1}^{\mid V \mid}Pr(t_i\mid d_j)^{f_{iq}}
\]

여기서 \(f_{iq}\)는 \(q\)에서 term \(t_i\)가 발생하는 횟수를 의미하고, \(\sum_{i=1}^{\mid V \mid}Pr(t_i\mid d_j)=1\)이다. 이제 검색 문제는 \(Pr(t_j\mid d_j)\)를 추정하는 것으로 바꼈고, 이는 상대빈도로 나타낼 수 있다.

\[
Pr(t_i\mid d_j) = \frac{f_{ij}}{\mid d_j \mid}
\]

\(f_{ij}\)가 문서 \(d_j\)에서 단어 \(t_i\)가 발생하는 횟수인걸 생각해보면, \(\mid d_j \mid\)는 문서 \(d_j\)에 있는 모든 단어의 수를 의미한다.

하지만, 이러한 방법에도 문서 \(d_j\)상에 존재하지 않지만 실제로 유효한 단어가 0의 확률을 가지게 되고, 이를 과소평가하게되는 문제점이 존재한다. 이러한 상황은 naïve Bayesian model을 사용하는 classification과 유사한데, 확률이 0이 되는 경우 0이 다른 수치들로 각각의 문서상에 존재하지 않는 단어들을 보정해야한다. 이러한 것을 'Smoothing'이라 한다. 이 때 Smoothing으로 확률 정확성을 높이기 위해 확률 추정을 조절한다. 이 Smoothing이라는 이름은 이 기술이 낮은 확률 값(0 값 등)은 올리고, 높은 확률 값은 내리는 방식으로 분산을 줄이는 형태로 수행하여 붙은 이름이다. 이는 확률 상에서 0 값이 나오는 것을 막을 뿐만 아니라, 전체적인 정확도를 높이는데 사용된다. Smoothing 중 하나인 additive smoothing은 아래의 수식으로 계산할 수 있다.

\[
Pr_{add}(t_i \mid d_j) = \frac{\lambda + f_{ij}}{\lambda\mid V\mid + \mid d_j\mid}
\]

\(\lambda=1\)일 때 Laplace Smoothing이라 부르고, \(0\lt\lambda\lt1\)일 때 Lidstone Smoothing이라 한다.

Relevance Feedback

Text and Web Page Pre-Processing

문서를 검색하기 전에 시스템 내부에선 몇가지 사전작업이 수행되어야 한다. HTML Tag들이 없던 예전 문서에서는, stopword removal, stemming, handling of digits, hyphens, punctuations, cases of letters과 같은 사전작업을 수행했다. Web Page에서는, 이 같은 작업 외에도 추가로 HTML tag removal과 identification of main content blocks과 같은 작업이 추가로 필요하다.

1. Stopword Removal
   Stopwords라는 것은 언어에서 자주 발생하고 중요하지 않지만, 문장을 구성하기 위해서 사용되는 단어들을 의미한다. 예를 들어 아래와 같은 것들이 존재한다.
   

   
   a, about, an, are, as, at, be, by, for, form, how, in, is, of, on, etc.
   그, 그것, 저것, 이것, 나는, -의 등
   

   
   이러한 단어들은 문서들이 색인되고 저장되기 전에 지워야 함은 물론 검색 query에서도 지워야 한다.

2. Stemming
   많은 언어에서, 어느 하나의 단어는 문맥에 따라 여러 형태로 존재한다. 예를 들어, 영어에서 명사는 여러 형태가 존재하고, 동사는 동명사(go, going, etc.)형태, 과거와 현재 시제에 따라 또 형태가 달라진다. 이러한 단어의 다양성은 검색을 했을 때 연관문서가 query에 있는 정확한 단어가 아니라 다양한 형태를 갖고 있을 수 있음을 의미한다. 이러한 문제점을 해결하고자 하는 것이 stemming이다.
   
   Stem이라는 것은 단어에서 접두사, 접미사를 제외한 부분을 의미한다. 영어에서 단어의 다양성은 대부분 접사로 인해 발생하고, stemming은 접미사 제거(suffix removal) 혹은 stripping을 의미한다. 예를 들어 "computer", "computing", "compute"는 "comput"로 "walks", "walking", "walker"는 "walk"로 될 수 있다.
   
   몇 년간 많은 연구자들이 stemming을 했을 때의 장점과 단점에 대해서 연구해왔다. 일단 stemming은 재현율(recall)을 향상시키고, indexing structure의 크기를 감소 시킨다. 하지만, 연관 없는 문서들이 연관 되어있다고 잘못 검색되는 문제 때문에 정확도가 떨어진다. 예를 들어, "cop"과 "cope"라는 단어는 "cop"으로 stemming 될 수 있다. 그러나 만약 경찰과 관련 있는 문서를 찾는다면, "cope" 단어만 포함한 문서는 관련이 없다고 나올 것이다.

3. Other Pre-Processing Tasks for Text

   • Digits
     기존 IR 시스템에선 날짜, 시간과 같이 규칙적인 숫자들을 제외하고는 문서에 포함된 숫자들은 전부 제외시켰었다. 그러나 Search Engine에서는 이러한 숫자들도 전부 색인하여 검색할 수 있게 한다.

   • Hyphens

   • Punctuation Marks

   • Case of Letters
     모든 알파벳은 대문자 혹은 소문자 단 하나의 형태로 전부 변경한다.

4. Web Page Pre-Processing
   Web Page는 기존의 문서와 다르게 추가적인 사전 작업 과정이 필요하다.

   • Identifying different text fields
     HTML에서는 일반 Text와는 다르게 Title, Metadata, Body 영역이 존재한다. 이 영역들을 확인함으로써 검색 시스템이 단어들을 서로 다른 영역에서 검색할 수 있도록 한다.

   • Identifying anchor text
     Hyperlink와도 연관되어 있는 anchor text는 종종 link가 가리키는 것보다 더 정확한 정보를 갖고 있을때가 있어 Search Engine에서 중요하게 다뤄진다.

   • Removing HTML tags

   • Identifying main content blocks

5. Duplicate Detection
   기존 IR 시스템에선 중복되는 문서나 페이지는 중요한 문제가 아니었지만, Web 환경에서는 매우 중요한 issue이다. Web에서는 페이지와 내용들 중복에는 몇 가지 다른 형태가 존재한다.
   
   페이지를 복사 하는 것은 중복 혹은 반복이라고 하며, 웹 사이트 전체를 복사 하는 것은 Mirroring이라 한다. Duplicate pages와 mirror sites는 제한된 bandwidth의 네트워크 환경에서 파일 다운로드나 검색 속도를 향상시키기 위해 종종 사용되기도 한다. 하지만 이렇게 중복된 페이지나 웹 사이트를 찾는 것은 index 크기를 줄일 수 있어, 검색 결과를 향상 시킬 수 있다.
   
   이러한 중복 검사를 위해 몇가지 방법들이 있다. 그 중 가장 간단한 방법은 모든 문서에 대해 hash 값을 부여하는 것이다. 그러나 이러한 방법은 정확히 hash 값이 일치하여 중복되는 문서를 찾는것에서만 유용하고, 웹에서는 이러한 경우가 좀처럼 존재하지 않는다. 예를 들어 mirroring 한 사이트지만, URL이나 Web master, contact 정보, 광고 정보 등이 다르다. 그렇기 때문에 hash 값으로는 중복을 찾기가 쉽지가 않다.
   
   hash 방법 외에 \(n\)-grams를 기반으로 한 효과적인 중복탐지 기술이 있다. \(n\)-gram이라는 것은 특정 길이 \(n\)으로 고정된 연속적인 단어들을 의미한다. 예를 들어, "John went to school with his brother" 이라는 문장은 "John went to", "went to school", "to school with", "school with his", "with his brother"라는 5개의 3-gram으로 나타낼 수 있다.
   
   \(S_n(d)\)를 문서 \(d\)에 포함된 구별되는 \(n\)-gram의 집합이라 한다면, 각각의 \(n\)-gram은 특정 숫자나 MD5 hash 값으로 인코딩 될 수 있다.
   
   만약 문서 \(d_1\), \(d_2\)에 2개의 \(n\)-gram 집합 \(S_n(d_1)\), \(S_n(d_2)\)가 있으면, Jaccard coefficient를 이용해 두 문서의 유사도를 계산할 수 있다.
   \[
   \mbox{Jaccard coefficient} \\\\
   sim(d_1, d_2) = \frac{\mid S_n(d_1) \cap S_n(d_2) \mid}{\mid S_n(d_1) \cup S_n(d_2)\mid}
   \]
   Jaccard coefficient - 두 집합 사이의 겹치는 정도를 수치로 나타낸 것
   
   
   threshold는 문서 \(d_1\)과 \(d_2\) 겹치는지 아닌지 판단하는데 사용된다.