제5장 검색 모델링

2013. 09. 08

가천대학교 IT대학 컴퓨터미디어융합학과

Information Retrieval

제5장 검색 모델링

5.1 소개

5.2 불리언 모델 5.3 벡터 공간 모델

5.4 확률 모델

익힘 문제

3

Why Retrieval Model?

Retrieval Model is a power of IRS for accuracy .

검색의 성공은 모델의 힘이다.

용어 정의

Collection: 문서의 집합 문서

자연어 문장의 나열 색인어 집합

색인어:

의미를 가지는 키워드 문서 내용의 요약

5

5.1 정보검색 모델링 개요

모델, 모델링

1) 특정한 목적을 위하여 대상을 가상적(추상적)으로 만든 객 체.

2) 대상을 경제적이며 부분적으로 추상화하여 만든 객체.

3) 이론이나 시스템의 속성을 설명하는 기법.

4) 대상의 특정 부분들을 집중적으로 조명하기 위한 추상화 기술.

5) 특정한 목적을 위하여 대상을 추상적(가상적)으로 만드는 객체(수단).

6) 대상의 모양이나 기능을 가상적으로 구현한 객체(수단).

모델의 목적과 기능

순서 목 적 기 능

1 설계 설계 목적을 정확하게 반영하고 확인 2 의사소통 관련자들 사이의 의사소통 수단

3 시험 예상 시험 자료를 준비하여 미리 시험

4 교육 훈련 제품 개발 이후를 대비한 사용자 교육

7

5.1 정보검색 모델링 개요

검색 모델과 시스템

질 의

결 과

가상 질의

가상 결과 시험 DB

문서집합

정보검색 시스템

검색 모델

검색 알고리즘 mapping

검색 모델의 정의

-용어를 매개로 질의와 문서의 관련성을 결정하는 도구.

-용어를 통하여 질의와 문서를 연결하는 알고리즘.

검색 모델에 필요한 기능

* 용어 공간으로 표현된 문서와 질의가 어떻게 관련되는가?

* 어떻게, 얼마나 관련된다고 결정할 것인가?

9

5.1 정보검색 모델링 개요

정보검색 모델의 구성

인터페이스 인터페이스

검색 알고리즘 정보 표현

Database 문서 집합

사용자

검색 언어

질의 용어

색 인

결과 결과

결과

검색 논리

^검색

논리 종 류 내 역

용어 부합

완전 부합 질의와 완전히 일치하는 용어 검색

부분 부합 질의와 부분적으로 일치하는 용어 검색 위치 부합 검색하는 용어들의 위치 관계에 따라 검색 범위 부합 질의에서 허용하는 범위의 내용을 검색 유사

도 부 합

간접 검색

질의와 문서의 유사한 정도에 따라 검색.

간접적인 요인들을 계산하여 유사도를 기준으로

검색

11

5.1 개요 검색 모델 분류

검색

축적 ad hoc: 변함없는 문서 파일에 질의는 지속적으로 갱신

ex. 도서관

여과 filter: 변함없는 질의에 문서 파일은 지속적으로 갱신.

user profile: 사용자 기호도 관리.

ex. 신문, 증권

브라우즈

전체 문서 읽기.

ex. 보고서

검색 모델

검색 축적 여과

퍼지

공간 벡터

추론망 대수론

확률론

집합론 확장 불리언

신경망

신념망 불리언 모델

벡터 모델

확률 모델

축적 ad hoc:

여과 filter

브라우즈 browse:

13

5.1 개요

검색 모델 구성 요소

|D, Q, F, R(q_i,d_j)|

D: 문서의 집합 Q: 질의

F: 문서/질의 표현

R(q_i, d_j): 질의 i와 문서 j를 연관시켜주는 순위 결정 알고리즘

검색 모델의 기능 세부 규정

- 문서 표현 - 질의 표현 - 검색 함수

관련성의 근거를 결정.

관련성의 근거

- binary: yes or no

15

5.1 개요

검색 모델의 분류 Boolean models :

- 확장 불리안

Vector space model

- Latent Semantic Indexing

Probabilistic model

- Bayesian network

- Inference network model - Belief network model

표현

문서는 단어들의 집합으로 표현.

질의

질의는 AND, OR, NOT으로 연결된 키워드의 불리언 식.

범위를 지시하는 괄호 포함.

((data OR sign) AND boy ) OR hotel AND not Hilton

출력:

문서들은 관련이 있거나 없다.

부분 정합partial match이나 순위는 없다.

17

5.2 불리언 모델

((data OR sign) AND boy ) OR hotel AND not Hilton

A B A B

a b

(a) a AND b (b) a OR b (c) a AND NOT b

OR boy

AND

data sign

hotel

OR

AND

Hilton

NOT

인기 있는 검색 모델

- 단순한 질의로 이해가 쉽다.

- 명확한 형식

순위를 부여할 수 있는 모델로 확장 가능

합리적으로 효율적인 구현 가능

19

5.2 불리언 모델

질의:

- 불 수식으로 사용자 요구를 명확하게 표현 가능 - 연산자: AND, OR, NOT

용어: 역파일

curve: (12, 25, 36, 77, 125, 334) time: (11, 12, 34, 56, 76, 125) Query

(curve and time) = 12, 125 (curve or time) = 11, … ,334

(curve and not time) = 25, 36, 77, 334

불리언 모델의 검색 실례

DID 문서

11 time …… curve 12 curve ….. Time….

25 Curve…..

34 …. time

36 curve

용어 문서 번호(DID)

curve 12, 25, 36, 77, 125, 334 time 11, 12, 34, 56, 76, 125

(b) 색인

(curve AND time) = 12, 125

(curve OR time) = 11, 12, 25, 34, …, 334 (curve AND NOT time) = 25, 36, 77, 334

76 time

77 curve

125 curve time

56 time

21

5.2 불리언 모델

장점:

집합론과 불 대수 기반 모델  단순성, 간결성 질의가 명확하고, 직관적이고, 이해하기 쉽다.

단점:

경직성: 결과가 너무 많거나, 너무 적거나 복잡한 사용자 요구를 질의로 표현 곤란 검색 문서의 수를 제어하기 곤란

순위화 적용 곤란

부분 정합 partial match 곤란: 사용자 요구의 중요도 표현 곤 란

관련 환류의 수행 곤란

- 통계 기반의 모델

- 문서: 전형적으로 단어들의 백bag으로 표현.

단어들의 백(빈도수를 가진 비 정렬된 단어들) bag: 동일 요소들의 중복을 허용하는 집합

- 사용: 가중치를 지정한 용어들의 집합을 규정

Q = (database 0.5; text 0.8; sign:0.3) Unweighted query terms:

Q = (database; text; sign)

23

5.3 벡터 공간 모델 VSM

- 질의와 문서 사이의 유사도를 근거로 검색

- 출력 문서들은 질의에 대한 유사도에 따라 순위화

- 유사도: 질의와 문서에서 키워드의 빈도수를 기반으로 함 - 자동적인 관련성 환류를 지원

- 관련 문서들은 질의에 추가

- 비 관련 문서들은 질의에서 제외

VSM: 색인어 공간에서 문서와 질의의 용어들을 벡터로 표 현하고 두 벡터 간의 유사도를 기준으로 관련 문서를 검색 하는 방식

- 문서에서 중요한 단어들을 어떻게 결정하는가?

- 한 문서 안에서 그리고 전체 문서 집합에서 한 용어의 중요 성을 어떻게 결정하는가?

- 질의와 문서의 유사도를 어떻게 결정하는가?

- 웹에서 문서 집합은 무엇이고 연결의 효과가 무엇이고 형식

25

5.3 벡터 공간 모델 VSM

- t 를 전처리 후에 얻어지는 용어로 가정:

이들을 색인어 또는 어휘라고 부름

- 이들 “직교” 용어들이 벡터 공간을 형성

- 문서 d

와 질의 q에서 용어 i는 가중치 w

로 표현.

- 문서 d

와 질의 q는 가중치를 이용하여 t-차원 벡터로 표현

d_j = (w_1j, w_2j, …, w_tj) q = (w_1q, w_2q,… w_tq)

질의 q 문서

d^j

θ

문서와 질의의 벡터 공간

용어 t

질의 Q

문서 D

θ1

θ2

용어 t

27

5.3 벡터 공간 모델

실례

T₁: retrieval T₂: information T₃: system

D₁ = 2T₁ + 3T₂ + 5T₃ D₂ = 3T₁ + 7T₂ + T₃ Q = T₁ + 0T₂ + 2T₃

D₁과 D₂ 중에서 어느 것이 Query에 근접한가?

t₃

q = t₁ + 0t₂ + 2t₃ 5

2 3

7 1

3

d₁ = 2t₁ + 3t₂ + 5t₃

d₂ = 3t₁ + 7t₂ + t₃ 1

2

t₁

t₂

질의 벡터

q = t₁ + 0t₂ + 2t₃ = [1, 0, 2]

d₁ = 2t₁ + 3t₂ + 5t₃ = [2, 3, 5]

d₂ = 3t₁ + 7t₂ + t₃ = [3, 7, 1]

S(d₁, q) = [2, 3, 5] * [1, 0, 2] = 2 + 0 + 10 = 12 S(d₂, q) = [3, 7, 1] * [1, 0, 2] = 3 + 0 + 2 = 5

∑

=

i

q t q

d

S ( , ) *

29

5.3 벡터 공간 모델

- n 문서의 집합체는 용어-문서 행렬식으로 벡터 공간 모델로 표현.

T

T

T

T

D

= [t

, t

, …, t

, …, t

]

D

= [t

, t

, …, t

, …, t

]

... … …

... … …

D

= [t

, t

, …, t

, …, t

]

- 용어 빈도수가 다음과 같은 문서가 있다.

A(4), B(2), C(1)

- 집합체는 10,000개의 문서가 있고 이들 용어들의 문서 빈도 는 다음과 같다.

A(50), B(1,300), C(250)

- tf-idf 계산 tf: f_i,j/max_l idf : Weight = log(N/dfi) A: tf_A = 4/4; idf_A = log(10000/50) = 5.3; tf-idf = 5.3

B: tf_B = 2/4; idf_B = log(10000/1300) = 2.0 tf-idf = 1

31

5.3 벡터 공간 모델

유사도 측정

두 벡터 사이의 유사도를 계산하는 함수

유사도 측정 용도

- 검색 문서들의 순위 부여 가능

- 문턱 값을 조정하면 검색 문서의 수를 통제 가능

문서 D_i와 Q_j의 유사도: Cosine 계산식 S(D_i, Q_j) = Σ _k=1,N T_ik · Q_jk

D₁ = [0.2, 0.1, 0.4, 0.5]

D₂ = [0.5, 0.6, 0.3, 0] Q = [0.5, 0.5, 0, 0]

D₃ = [0.4, 0.5, 0.8, 0.3]

D₄ = [0.1, 0, 0.7, 0.8]

S(D₁,Q) = 0.1 + 0.05 + 0 + 0 = 0.15 S(D₂,Q) = 0.25 + 0.3 + 0 + 0 = 0.55 S(D₃,Q) = 0.2 + 0.25 + 0 + 0 = 0.45

33

5.3 벡터 공간 모델 5.3.2 신경망 모델

신경망 : 두뇌의 뉴런을 모방하여 만든 정보처리 체계

뉴런들의 연결 특성을 컴퓨터 모의실험으로 표현하는 수학 모델

은닉층: y = {-x, if Output >1.5} 최종출력: z = {1, if Output > 0.5}

{+x, if Output <= 1.5} z = {0, if Output <= 0.5}

W1 W₂

출력:

y

입력: X1 입력: X2

은닉층

가중치 가중치

A

C .5

+1 0

+ 1

H 1.5

+1 0

+ 1

(c) 다층 퍼셉트론

A B

C

+1 +1

+0.7 -0.3 +0.4

입력 출력

(a) 단순 신경망 (b) 퍼셉트론

B A

C

B 문턱값

신경망의 실례

1 0 0 1 0 0 1 1 1 1 0 1 1

0 1 2 3 4 5 6 7 8

. .

back propagation

35

5.3 벡터 공간 모델 5.3.2 신경망 모델

자료 표현

- 국부 표현(local representation) 입력층: 색인어 당 하나의 노드 출력층: 문서 당 하나의 노드

학습

모든 가중치가 학습 알고리즘에 의해 결정 학습 자료: term vector

실행

입력: 질의 벡터, 출력: 질의 벡터에 대한 출력층의 각 노드 에 활성화된 값에 따라서 문서의 순위가 결정된다.

동기

정보검색 시스템

- 문서 벡터와 질의 벡터의 유사도를 계산하여 순위화한다.

- 문서와 질의에 포함된 색인은 정합되어야 하고 적절한 가 중치를 가지고 있어야 순위화 한다.

신경망 모델

- 3층으로 구성

질의 용어, 문서 용어, 문서

37

5.3.2 신경망 모델 _예제

D1:

Cats and dogs eat.

D2:

The dog has a mouse.

D3:

Mice eat anything.

D4:

Cats play with mice and rats.

D5:

Cats play with rats.

Query: Do cats play with mice?

Ka

Kb

Kc

Kl

K_a

Kb

K_c K1

d_N d1

d_j

dj+1

. .

.

. .

. . .

질의 용어 문서 용어 문서

입력층 은닉층 출력층

Cat

Play

Cat

Rat Dog

d₁

d₂

d₃ .

.

dk

Eat 질의

용어 문서 색인 문서 집합

..

..

Mouse

Mouse

39

5.3 벡터 공간 모델 장단점 장점

- 용어 가중치 : 검색 성능 향상 - 부분 정합 가능

- 검색 결과 우선순위화 가능

단점

- 색인 용어들 간의 연관성을 고려하지 않음

용어 근접도(proximity), 용어 사이의 의존성 무시 - 연관 피드백 없이 성능 개선 곤란

- Missing semantic information (e.g. word sense).

- Missing syntactic information (e.g. phrase structure, word order, proximity information).

- Assumption of term independence (e.g. ignores synonomy).

- Lacks the control of a Boolean model (e.g., requiring a term to appear in a document).

: Given a two-term query “A B”, may prefer a document

containing A frequently but B, over a document that contains

41

5.3 벡터 공간 모델

Summary

- Simple, mathmatically based approach.

- Considers both local (tf) and global (idf) word occurance frequencies.

- Provides partial matching and ranked results.

- Tends to work quite well in practice despite obvious weaknesses.

- Allows efficient implementation for large document collections.

(scalable)

42

IR 문제를 확률적으로 해석.

1976 Robertson과 sparck Jones가 제안

가정(확률 원칙)

연관 확율은 문헌과 질의 표현에만 종속된다.

질의 q, 문서 D, 관련 문서인 해답 집합 R이 존재하고, 해답 집합 R을 서술할 수 있으면 검색 가능.

집합 R의 문서는 질의 q에 연관되고 다른 문헌은 연관되지 않 는다.

질의 과정: 해답 집합의 특성을 규정하는 작업.

문제: 특성은 모르고, 특성 규정에 사용된 의미를 가진 용어만 존재.

43

5.4 확률 모델

확률 모델의 진행 과정

1. 확률 표현을 추정하여 생성하고 검색한다.

2. 사용자는 검색된 문서 중에서 어떤 것이 관련되고 안 되 는지를 제시한다.

3. 시스템은 이 정보를 이용하여 이상적인 해답 집합 표현으 로 수정한다.

다시 2, 3번을 반복하여 수행한다.

표현은 점점 이상적인 해답 집합 표현에 가까워진다.

적합한 문서의 서술과 질의.

어부가 고기를 잡기 위해

초기 추정

확률 표현 생성

검색

만족

확률 표현 y 개선

N

종 료 시 작

부적합한 문서 ¬R

적합한 문서

R

질의 q

문서 D

서술 yes 가능?

no END

45

5.4 확률 모델

대책

초기에 특성을 알 수 없으므로 추정.

초기 추정

 검색에 사용될 예비 확률 표현 생성  검색

 결과의 관련성을 검토하여 확률 표현 개선  점차 이상적 결과로 개선.

질의 q, 컬렉션의 문서 D_j 가 주어지면, D_j 에 관련될 확률 추 정.

해답 집합을 R, R에 속하지 않으면 비연관 집합 R.

정의

용어 가중치 변수는 모두 2진값, w_i,j ε {0,1}, d_i,q ε {0,1}.

질의 q는 색인어의 부분 집합.

R : 연관집합, ¬R: 비연관집합

P(R|d_j) : 문헌 d_j가 질의 q에 연관될 확률

P(¬ R|d_j) : 문헌 d_j가 질의 q에 비연관될 확률 문헌 d_i와 질의 q의 유사도:

sim(d_j,q) = P( R|d_j)/P(¬ R|d_j)

47

5.4 확률 모델

문제점

사용자가 찾는 문서 d_j 를 찾을 확률을 어떻게 구하나?

장점

이론상 문헌들이 연관 확률 값에 따라 순위화

단점

- 초기에 연관/비연관으로 문헌들을 추정 분리해야,,, - 문헌 내 색인 빈도수를 고려하지 않음

- 용어에 대한 독립을 가정

사건 B 발생 후 n개의 서로 배반인 사건 A₁, A₂, …,A_n 중 A_i가 일어날 확률:

P(A|B)는 사건 B가 일어났다는 조건하에 사건 A가 일어날 조건부 확률:

실험결과  새로운 정보  확률 개선 사전확률  새로운 정보 

∑

=

1

)

| ( ) (

)

| ( ) ) (

| (

k

k k

i i

i P A P B A

A B P A B P

A P

49

5.4 확률 모델 5.4.1 베이즈 정리

>>> 예제 5.1:

남녀공학인 어떤 중학교에 학생들이 1, 2, 3학년별로 각각 40%, 30%, 30%가 분포되어 있으며 각 학년별로 여학생 들이 각각 40%, 45%, 50%가 분포되어 있다. 한 여학생 이 1학년일 경우는 얼마일까?

∑

= ₃

1

1 1

1

)

| ( ) (

)

| ( ) ) (

| (

k

k

k P B A

A P

A B P A B P

A P

0.4 0.3 0.3

0.4 0.45 0.5

1학년 2학년 3학년

여학생 남학생 여학생 남학생 여학생 남학생

“확률 이론과 그래픽 이론의 결합으로 이루어진 그래픽 모델

”

방향성 비순환 그래프

Node: parent/child

random 변수 X(i): 측정값, 인수, 숨겨진 변수, 가설 등 = Bayesian.

확률분포 p(X(i) | parents(X(i)))의 곱. i=1,…,n parent가 있으면 조건부 확률, 없으면 무조건

Arc: 노드들 사이의 인과관계

Cloudy

Sprinkler Rain

WetGrass P(C=F) P(C=T) ---

0.5 0.5

C | P(R=F) P(R=T) --- F | 0.8 0.2 T | 0.2 0.8

P(W=F) P(W=T) --- 1.0 0.0 0.1 0.9 0.1 0.9 0.01 0.99 S R |

--- F F | T F | F T | T T | C | P(S=F) P(S=T)

--- F | 0.5 0.5 T | 0.9 0.1

51

5.4 확률 모델

“잔디가 젖을 때 스프링클러가 동작하거나 비가 오는 경우”

날씨가 흐릴 때, 비가 올 확률:

P(R=T|C=T) = 0.8

결합 확률 분포

P(x1,x2,x3,x4,x5)

= P(x1)P(x2|x1)P(x3|x1)P(x4|x2,x3)P(x5|x3)

P(x1) : 망의 사전 확률

베이즈 망 구성

- 시스템 표현을 위한 노드 구성 - 노드 연결

- 확률 테이블 구성 ^X5

X2 X3

X4

X1

53

5.4 확률 모델 5.4.2 추론망 모델

결합 확률 분포

정보검색 : 인간이 원하는 정보를 검색하려는 신념으로 해석.

일반인도 통계에 대한 정의가 없어도 확률을 언급한다.

추론망 모델은 색인어, 문서, 질의에 대하여 확률 변수를 계산 .

문서 d_j에 연계된 확률 변수는 그 문서를 관측 사건으로 간 주하며, 이 문서 관측이 색인어와 연계된 확률 변수에 대 한 신념을 나타낸다.

문서 d_j는 용어 t₂, t_i, t_k를 가지며,

요구 R은 질의 노드 q와 q₁으로 연결.

R = q ∨ q₁ = q ∨ (q₂ ∨ t_i ) = t₁ ∨ t₂ ∨ t_i ∨ ((t₁ ∧ t₂ )∨ t_i))

d_j

t₁ t₂ t_k

q

t_i

q₂ q₁

...

...

문서 노드

용어 노드

질의 노드

... ...

and or

55

5.4 확률 모델 5.4.1 베이지안 모델

세 모델의 비교

모델

기능 불리언 모델 벡터 모델 확률 모델 불리언 논리 yes

가중치 yes yes

우선순위 yes yes

검색 기준 용어 존재 벡터 거리 용어 빈도

고유 특징 적합성 환류

모델

대상을 특정한 목적을 위하여 추상화시킨 객체(수단).

모델의 목적

설계, 소통, 시험, 교육.

검색 모델

용어를 매개로 질의와 문서집합의 관련성을 결정하는 수단.

정보검색 모델의 구성

DB, 색인, 검색 알고리즘, 검색 언어, 정보 표현, 인터페이스 검색 논리

용어 부합(완전, 부분, 위치, 범위), 유사도 부합(간접 검색)

57

5.5 요점 정리

검색 모델의 분류

검색(축적, 여과), 부라우즈

검색(불리언, 벡터모델, 확률 모델) 불리언 모델

문서(단어 집합), and,or,not, no 부분정합, no 우선순위.

단순, 명확, 이해 용이.

벡터 모델

문서: 단어들의 bag.

적용: 가중치를 허용하는 용어들의 집합 벡터공간 모델

질의와 문서를 용어들의 벡터로 표현하고 두 벡터의 유사도 를 이용하여 관련성을 판단하는 검색 기법.

58

벡터 공간 모델

질의와 문서의 용어로 구성된 벡터 공간에서 유사도 계산 기술.

신경망 모델

뉴런들의 연결 특성을 컴퓨터 모의실험으로 표현하는 수학 모델

정보검색 신경망 모델

문서와 질의에 포함된 색인은 정합되어야 하고 적절한 가중치 를 가지고 있어야 순위화 한다.

확률 모델

확률 표현을 이용하여 질의와 문서의 유사도를 추정하는 모델.

베이즈 모델

사건 B가 발생한 후에 서로 배반인 An개의 사건 중에서 한 사

59

5.6 익힘 문제

두 문제를 선택하여 해답을 제출하시오.

) ㄱ |

(

)

| ) (

, (

j j

j P R d

d R q P

d

sim

=

∑=

= ₃

1

1 1

1

)

| ( ) (

)

| ( ) ) (

| (

k

k

k P B A

A P

A B P A B P

A P

% 599 . 3 03599 .

4 0 . 0

* 4 . ) 0

|

( ¹ = =

+

= + B A P

∑

= ^{ik k}

i q t q

d

S( , ) *