Probabilistic approaches

A variable A represents an event (a subset of the space of possible outcomes). Equivalently, we can represent the subset via a random variable , which is a function from outcomes to real numbers; the subset is the domain over which the random variable A has a particular value. Often we will not know with certainty whether an event is true in the world. We can ask the probability of the event  0 ≤P(A)≤1. For two events A and B, the joint event of both events occurring is described by the joint probability P(A,B). The conditional probability P(A|B) expresses the probability of event A given that event B occurred. The fundamental relationship between joint and conditional probabilities is given by the chain rule :

P(A,B) = P(A∩B) = P(A|B)P(B) = P(B|A)P(A)

<point> The Binary Independence Model (BIM)

is the model that has traditionally been used with the PRP(Probability Ranking Principle: “If a reference retrieval system's response to each request is a ranking of the documents in the collection in order of decreasing probability of relevance to the user who submitted the request, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data.”).

It introduces some simple assumptions, which make estimating the probability function P(R|d,q) practical. Here, ``binary'' is equivalent to Boolean: documents and queries are both represented as binary term incidence vectors. That is, a document d is represented by the vector   where xt = 1 if term t is present in document d and xt = 0 if t is not present in d. With this representation, many possible documents have the same vector representation. Similarly, we represent q by the incidence vector (the distinction between q and  is less central since commonly q is in the form of a set of words).

“Independence” means that terms are modeled as occurring in documents independently. The model recognizes no association between terms. This assumption is far from correct, but it nevertheless often gives satisfactory results in practice; it is the ``naive'' assumption of Naive Bayes models, discussed further in Section 13.4 . Indeed, the Binary Independence Model is exactly the same as the multivariate Bernoulli Naive Bayes model presented in Section 13.3 . In a sense this assumption is equivalent to an assumption of the vector space model, where each term is a dimension that is orthogonal to all other terms.

We will first present a model which assumes that the user has a single step information need. As discussed in Chapter 9 , seeing a range of results might let the user refine their information need. Fortunately, as mentioned there, it is straightforward to extend the Binary Independence Model so as to provide a framework for relevance feedback, and we present this model in Section 11.3.4 .

To make a probabilistic retrieval strategy precise, we need to estimate how terms in documents contribute to relevance, specifically, we wish to know how term frequency, document frequency, document length, and other statistics that we can compute influence judgments about document relevance, and how they can be reasonably combined to estimate the probability of document relevance. We then order documents by decreasing estimated probability of relevance.

We assume here that the relevance of each document is independent of the relevance of other documents. As we noted, this is incorrect: the assumption is especially harmful in practice if it allows a system to return duplicate or near duplicate documents. Under the BIM, we model the probability that a document is relevant via the probability in terms of term incidence vectors  . Then, using Bayes rule, we have:

=

=

Here, and  are the probability that if a relevant or nonrelevant, respectively, document is retrieved, then that document's representation is . You should think of this quantity as defined with respect to a space of possible documents in a domain. How do we compute all these probabilities? We never know the exact probabilities, and so we have to use estimates: Statistics about the actual document collection are used to estimate these probabilities.   and  indicate the prior probability of retrieving a relevant or nonrelevant document respectively for a query . Again, if we knew the percentage of relevant documents in the collection, then we could use this number to estimate   and . Since a document is either relevant or nonrelevant to a query, we must have that:

1) probabilistic indexing model

2) probabilistic retrieval model

3) 2-Poisson model

포아송 확률이란 단위 시간(또는 공간) 안에서 어떤 사건이 무작위로 몇 번 발생할 것인지를 표현하는 이산 확률 분포이다.

만일 X가 주어진 시간에서 발생한 사건의 숫자라면, 그리고 주어진 시간당 사건의 평균수가  λ(람다)라면, 주어진 시간에 사건 x를 관찰할 확률은 다음과 같이 구한다:

P(X = x) = [eqn: e ^{- lambda } {lambda ^{chi }} over {chi !}]

x = 0, 1, 2, 3, 4, . . .

<Note>

e는 수학적 자연상수인, e ≈ 2.718282 이다. e의 파워를 계산하기 위하여 계산기에 있는 [eqn: e ^{chi }] 버튼을 눌러야 한다.

만일 X의 확률이 이러한 방식으로 분산되어 진다면, 우리는 X∼Po(λ) 라고 쓴다. 이때, λ 는 분산의 파라미터이다. 그리고 우리는 X가 파라미터 λ와 함께 포아송 분산에 따른다고 말한다.

<예제>

어떤 도서관에서 신간의 대출이 시간당 평균 1.8권씩 무작위로 이루어지고 있다고 가정해 보자. 그럼 이 도서관에서 주어진 시간에 4권의 신간이 대출될 확률은 무엇이냐?

X는 특정한 시간에 대출되는 신간의 수 이다.

(i)  대출은 무작위로 발생 한다

(ii) 평균비율은 1.8권이다.

따라서 X ∼ Po(1.8)라고 쓴다.

이제 주어진 시간에 정확하게 4권의 신간이 대출될 확률을 다음과 같은 공식을 사용하여 계산할 수 있다:

P(X = 4) = [eqn: e ^{-1.8} {1.8 ^{4}} over {4!}]= 0.0723

또 하나, 이 도서관에서 주어진 시간에 2권 이상의 신간이 대출될 확률은 무엇이냐?

P(X ≥ 2) = P(X = 2) + P(X = 3) + . . .

i.e. 계산할 확률은 무한 수이다.

다음과 같이 구한다:

P(X ≥ 2) = P(X = 2) + P(X = 3) + . . .

= 1 − P(X < 2)

= 1 − (P(X = 0) + P(X = 1))

= 1 − [eqn: (e ^{-1.8} {1.8 ^{0}} over {0!} +e ^{-1.8} {1.8!} over {1!} )]

= 1 − (0.16529 + 0.29753)

= 0.537

<point> Okapi BM25 (BM stands for Best Matching)>

정보검색에서, Okapi BM25 (BM stands for Best Matching)은 특정한 탐색쿼리에 적합성을 근거로 문서를 매칭시켜서 서열화시키는 탐색엔진에서 사용하는 ranking function 이다. 이것은 Stephen E. Robertson, Karen Spärck Jones 등에 의해 1970년대와 80년대에 개발된 확률적 검색 프레임워크에 근거하고 있다.

BM25와 이것의 새로운 변종인 BM25F는 웹 탐색과 같은 문서검색에서 최신의 TF-IDF-like retrieval functions을 사용하고 있다.

BM25는 문서에 있는 쿼리어들 간의 상호 연관성(상대적 근접성)과 관계없이, 각 문서에 나타나는 쿼리를 근거로 문서의 세트를 서열화하는 a bag-of-words retrieval 함수(function) 이다.  이것은 단일 함수가 아니라, 비록 서로 다른 요소와 파라미터를 사용하더라도 실재로 scoring functions의 한 가족이다. 가장 잘 알려진 사례들 중의 하나는 다음과 같다:

keywords q1, ..., qn,를 포함하고 있는 쿼리 Q에서, 문서 D의 BM25 score는 다음과 같이 계산한다:

score(D,Q) = [eqn: sum _{i=1} ^{n} IDF(q _{i} ). {f(q _{i,} D).(k _{1} +`1)} over {f(q _{i,} D)+k _{1} .(1-b+b. {|D|} over {avgdl} )}]

▪f(qi, D)은 문서 D에 있는 qi's term frequency이다;

▪|D|는 단어로 된 문서 D의 길이 이다;

▪avgdl은 문서에서 발췌한 텍스트 집단에 있는 평균문서길이 이다.

▪k1 and b는 free parameters이며, k1 ∈ [1.2,2.0] 그리고 b = 0.75처럼, 대체적으로

advanced optimization이 없을 때 선택된다.

▪IDF(qi)는 쿼리용어 qi 의IDF (inverse document frequency) weight 이다. 이것은 대

체로 다음과 같이 계산한다:

IDF(qi) =log[eqn: {N-n(q _{1} )+0.5} over {n(q _{1} )+0.5}]

▪N은 집단에 있는 문서의 총 수이다.

▪n(qi)은  qi.을 포함하고 있는 문서의 수이다.

4) Bayesian network models

Bayes 정리: 베이즈 확률계산(영어: Bayes’ theorem)는 두 확률 변수의 사전 확률과 사후 확률 사이의 관계를 나타내는 정리다

[eqn: Pr(A|B)=` {Pr(B|A)Pr(A)} over {Pr(B)}]

▪Pr(A|B-도서관): B의 값이 주어진 경우에 대한 A의 사후 확률.

▪Pr(B|A): A가 주어졌을 때 B의 조건부 확률.

▪Pr(A): A의 사전확률으로, 아직 사건 B에 관한 어떠한 정보도 알지 못한다는 것을

의미한다.

▪Pr(B): B의 사전확률이며, 정규화 상수의 역할을 한다.

(예) 눈앞의 사람에 대한 사전확률이 주어졌을 경우에, 철수의 사후확률을 구하는 공식

<point>

P(눈앞의사람)도 사실 계산이 가능한 상수값인데, 만일 가능한 사람이 철수, 영희, 순희 3사람이라고 한다면,

P(눈앞의사람) = P(눈앞의사람|철수)P(철수) + P(눈앞의사람|영희)P(영희) + P(눈앞의사람|순희)P(순희) = [eqn: ( {1} over {3} TIMES {1} over {3} )] + [eqn: ( {1} over {3} TIMES {1} over {3} )] + [eqn: ( {1} over {3} TIMES {1} over {3} )] = [eqn: {3} over {9} `=` {1} over {3}]

로 계산된다.

5) language models

>개념

언어 모델링(Language Modeling)은 자연어 안에서 문법, 구문, 단어 등에 대한 어떤 규칙성을 찾아내고 그 규칙성을 이용하기 위한 노력이다. 이런 방법을 통해 얻어진 언어모델(LM: Language Model)은 오랫동안 음성 인식이나 기계 번역, 문자 인식, 철자 교정 등 다양한 응용분야에서 시스템의 정확도를 높이고 수행 시간을 줄이는 데 유용한 방법으로 각광을 받아왔다.

언어모델은 크게 지식 기반 모델(Knowledge-based Model)과 통계적 모델(Statistical Model)로 나눌 수 있다. 지식 기반 모델은 정규 문법(RG: Regular Grammar)나 문맥 자유 문법(CFG: Context-Free Grammar)을 만들고, 이러한 문법 구조에 어긋난 구조를 탐색 공간에서 제거함으로써 탐색 범위를 줄이고 인식률을 높이는 방식이다. 그러나 지식 기반 모델은 문법 구조를 만들기가 까다롭고 대용량의 어휘를 수용하기 어려울 뿐만 아니라 언어의 비문법성에 의해 규칙정의가 어렵기 때문에 범용 언어 모델이나 새로운 영역에 대한 언어 모델을 구성할 때 많은 시간과 노력을 요구하게 된다. 따라서 이 모델링 방법은 주로 특정적이고 협소한 분야의 자연언어처리 분야에서 일부 사용되고 있을 뿐 대규모의 데이터를 처리해야 하는 분야에서는 적용되기 어려운 접근법이다.

이에 반해 통계적 모델은 대량의 말뭉치(Corpus)에서 언어 규칙을 확률로 나타내고 확률값을 통해서 탐색 영역을 제한하는 방법이다. 그래서 통계적 언어모델은 음성인식에서 정확성뿐만 아니라 탐색 공간을 급격히 줄이는 효과를 보여준다. 통계적 언어모델의 목적은 주어진 인식영역에 맞는 단어열 s의 확률을 예측하는 것으로 단어열 s는 w1, w2, ..., wi로 이루어진 단어열이라고 가정하면 단어열 s의 확률 P(s)는 다음과 같다:

[eqn: p(w _{1} ,`w _{2} ,`...,`w _{i} )`=`p(w _{1} )p(w _{2} `|`w _{1} )p(w _{3} `|`w _{1} w _{2)`} `...`p(w _{i`} `|`w _{1`...`} w _{i-1} )]

그러나 일반적인 통계적 언어모델링은 어떤 단어열에서 i번째 단어 wi가 나타날 확률을 구하기 위해 w1□에서 w1-i□까지 i-1개의 단어열이 나타날 확률을 구해야 하는 번거로움이 있다. 그래서 단어의 확률은 이전 단어에 의존적이라는 Markov 가정에 의해 i번째 단어가 나타날 확률을 구하기 위해 이전의 N-1개의 단어의 확률만을 적용하는 N-Gram 모델이 일반적이다. 특정한 문장 s에 대한 N-gram 모델의 식은 다음과 같다:

□ □     P(s) ≅ P(w1, w2, ... , wn) = [eqn: ``` prod _{i=1} ^{n} p(w _{i} |w _{i-m+1,} `...,`w _{i-1} )]

wi는 문장에서 i 번째 단어이고 m은 연관되어 사용된 단어 수를 정의한다. bigram 모델(m=2)은 앞의 단어에 이어 뒤의 단어가 나타날 확률을 사용해서 측정한다. 반면 unigram 모델(m=1)은 오직 개별 단어의 확률로 측정한다. 음성인식과 기계번역과 같은 응용분야에서는 단어순서가 중요하기 때문에 일반적으로 대용량의 학습데이터가 가능하다면 trigram(m=3)□모델이, 소량의 학습데이터가 가능하다면 bigram이 사용되어 왔다. 정보검색에서 단어순서의 역할은 덜 명백하다고 생각되었고 이에 따라 가장 친숙하고 기본적인 언어모델인 unigram 모델이 광범위하게 사용되고 있다.

통계적 언어모델이 모두 그렇듯이 N-Gram 통계언어 모델링은 모든 가능한 문장의 확률적 분포를 추정하기 위해 언어 모델을 사용하기 때문에, 우선적으로 전체 컬렉션을 대표할 만한 샘플 데이터를 선정하고 그 데이터를 학습함으로써 언어모델을 측정하는 것이 선행되어야 한다. 따라서 통계적 언어모델의 좋은 성능을 위해서는 대용량의 학습 데이터가 필요하고, 만약 빈약한 학습데이터에 의해 빈도수가 ‘0'인 단어가 질의어에 포함될 경우 전체 질의어의 확률분포 값이 ‘0’이 되는 심각한 오류가 발생하게 된다. 즉 미등록어(OOV: Out-Of-Vocabulary) 발생시에는 그 대처가 불가능하다는 것이 통계적 언어모델링의 가장 큰 단점이다. 하지만 지난 30여 년 동안 언어모델링의 다양한 확장 기법에 대한 연구들을 통해 미등록어 발생의 단점들을 보완함으로써 음성인식, 기계 번역, 자동 교정 등과 같은 대부분의 언어모델링 응용분야에서 성공적인 결과를 보이고 있다. 이중에 통계적 언어모델인 N-gram이 가장 성공적이고 간편한 언어모델링 방법으로 알려져 있다. 이제 언어모델이 정보검색 분야에서는 어떻게 적용되는지에 대하여 간략하게 살펴보고자 한다.

>언어모델과 정보검색

1998년의 Ponte와 Croft의 연구 이후, 언어모델링 연구 분야에서 정보검색은 음성인식, 기계번역과 같은 주요한 응용분야의 하나가 되었고 정보검색 연구 분야에서 언어모델은 주목해야할 검색모델의 하나로 자리 잡고 있다. 언어모델 적용은 여러 가지 이유에서 이점을 지닌다. 예를 들면, 언어모델을 사용하여 정보검색시스템을 구축하는 것은 시스템 설계와 실험 성과에 대한 이유를 확률적인 방법을 사용하여 명확한 수치 데이터로 제시해 줄 수 있다는 것이다. 또 다른 큰 이점은 지난 30여 년 동안 자연언어처리 분야에서 실험되어 축적되어온 다양한 언어모델과 완화기법의 결합에 대한 연구결과물들을 응용할 수 있다는 것이다.

정보검색에서 언어모델 적용의 기본적인 가정은 이용자가 생각하고 있는 하나의 ‘이상적인’ 문헌이 존재하고, 이용자는 그 문헌을 요구하기 위해 질의어 텍스트로 표현한다는 것이다. 이와 같은 이용자의 질의생성과정을 모델링 하는 것이 전통적인 LMIR의 기본 개념이 된다. 즉, 문헌으로부터 질의를 생성한다는 것이다. 다시 말해 LMIR은 컬렉션 내의 각각의 문헌 □를 위한 언어모델 Md□를 구축한다는 것이고, 그리고 어떻게 이런 각각의 문헌 모델로부터 질의 □Q가 생성될 수 있는가에 따라 문헌들을 순위화하는 것이다. 이것은 P(Q|Md)로 표현된다.

정보검색을 위한 언어모델들은 □P(Q|Md)□을 어떻게 정의하고 계산하느냐에 따라 그 접근방법이 달라진다.

Ponte와 Croft는 질의을 단일어로 취급하고 P(Q|Md)□의 근사치를 구하기 위해 질의어를 생성해낼 확률과 질의어에 포함되지 않은 단어를 생성하지 않을 확률의 곱으로 계산했다. 질의에서 같은 단어의 중복 출현은 고려되지 않았고 이를 위해 제시된 식은 다음과 같다.

[eqn: P(Q|M _{d} )`=` prod _{w` IN Q} ^{} P(w|M _{d} )` prod _{w NOTIN Q} ^{} (1.0`-`P(w|M _{d} )]

여기에서 P(w|Md)는 비모수적 방법에 의해 계산된 것으로, w와 위험요인을 포함한 문헌에서 w의 평균 확률을 사용하였고, 전혀 출현하지 않은 단어를 위해서는 컬렉션에서 w의 전체 확률을 대신 사용하였다. Ponte와 Croft의 모델은 정보검색분야에 적용된 초기 언어모델로 최근의 많은 연구들에서 기본적인 또는 전통적인 언어모델로 간주되고 있다.

전통적인 LMIR은 확률적인 계산방법에 의한 전형적인 수학모델을 따르기 때문에 비교적 단순하고 이해하기 쉬운 체제이다. 또한 LMIR은 각 문헌의 모델링 과정이 곧 색인작성 과정이 되며 이렇게 측정된 문헌모델에서 질의 생성확률을 추정하는 것으로 색인작성과 검색모델이 통합된 접근법이라는 장점을 가진다. 하지만 LMIR이 대량의 훈련 데이터(Training Data)가 필요하다는 점, 적합성 피드백(Relevance Feedback)이나 질의 확장(Query Expansion)을 직접적으로 적용하기 어렵다는 점, 또한 불리언 연산자나 구, 구조적인 질의 처리가 어렵다는 단점을 지니고 있다.

<point> Finite automata and language models

http://nlp.stanford.edu/IR-book/html/htmledition/finite-automata-and-language-models-1.html

쿼리를 생산하는 문서모델이란 무엇일까? 공식적인 언어모델의 일종인 전통적인 언어생산 모델은 문자열(string)을 인식하거나 생산하는데 사용할 수 있다. 예를 들어, 도 12.1의 finite automaton에서는 샘플을 포함하고 있는 문자열을 생산할 수 있다. 생산가능한 문자열의 풀-세트를 automation의 language라 부른다.

만일 각 노드가 다른 용어를 생산하는 것과 관련해서 확률분포를 가지고 있다면, 우리는language model을 갖고 있다. language model의 개념은 본질적으로 확률적이다. language model은 어휘(vocabulary)에서 발췌한 문자열의 확률 척도를 구하는 함수이다.

is a function that puts a probability measure over strings drawn from some vocabulary. 예를 들어, alphabet ∑에 대한 language model의 공식은 다음과 같다:

한 가지 가장 간단한 언어모델은 probabilistic finite automaton과 대등하다. probabilistic finite automaton은 도 12.2에서처럼, 다른 용어를 생산과 관련해서 단일 확률분포를 갖는 단일 노드를 가지며, 그 공식은  이다.

각 단어가 생산된 다음에, 우리는 다른 단어를 생산하기 위하여 거기서 멈출 것인지 또는 looping할 것인지를 결정한다. 또한 이 모델에서는 최종 상태에서 멈출 확률을 필요로 한다.  이 같은 모델은 단어의 순서 별로 확률분포를 설정한다. 또한 이것은 그것의 분포에 따라 텍스트를 생산하는 모델을 제공하기도 한다.

>example

probability of a word sequence를 찾기 위하여, 각 단어를 생산한 다음에 멈출 확률이나 순환한 확률과 함께, 우리는 단지 이 모델에서 순차적으로 각 단어에 매긴 확률을 곱하면 된다.

=

보다시피, 특별한 문자열/문서의 확률은 대체로 매우 작은 수이다! 여기서 우리는 두 번째 frog 단어를 생산한 다음에 멈추었다. 첫 번째 줄의 숫자는 term emission probabilities이고, 두 번째 줄은 각 단어를 생산한 다음에 계속하거나 멈출 확률들이다. 분명한 stop 확률은 finite automation이 잘 구성된 언어모델이 되기 위하여 필요하다.

그럼에도 불구하고, 대부분의 경우에, 우리는 STOP 그리고 (1-STOP) 확률을 포함시키는 것을 생략할 것이다. 데이터 세트인 두 모델을 비교하기 위하여, 우리는 그것들의 likelihood ratio를 계산할 것이다. likelihood ratio는 한 모델에서 이루어진 데이터의 확률을 다른 모델에서 이루어진 데이터의 확률로 단지 나눈 결과이다. 왜냐하면 stop 확률이 고정되어 있다면,

문자열을 생산하는 두 개의 언어 모델들의 likehood를 비교하여 얻는 결과인 likelihood ration는 변하지 않을 것이기 때문이다. 따라서 문서의 순위도 변하지 않을 것이다. 그럼에도 불구하고 공식적으로 그 숫자들은 더 이상은 참된 확률이 아니고 단지 확률에 비례하는 것이다.

>example.

Figure 12.3: Partial specification of two unigram language models.

도 12.3처럼, 우리가 두 개의 언어모델 M1 과 M2를 가지고 있다고 가정해 보자. 각각은 m1 probability에서 보여주고 있는 것처럼, 용어들의 순서에 따라 확률 값(estimate)을 제공하고 있다. the sequence of terms에 더 높은 확률을 제공하고 있는 언어모델은 더 쉽게 term sequence를 생산할 수 있다. 이제 우리는 우리의 계산에서 STOP 확률을 생략할 것이다

For the sequence shown, we get:

이제 우리는 라는 것을 알게 된다. 우리는 확률의 생산과 관련해서 공식을 제시하고 있다. 그러나 이것은 확률적 어플리케이션에서는 일반적이더라도, 실재로는 sums of log probabilities을 가지고 작업하는 것이 아마도 최상일 것이다.