정보검색론 제 15장. 확장 불리안 모델

숭실대학교 정보검색연구실 - 정보검색론(2003) 이준호 교수님 교제를 메모하기 위한 글입니다.

제 15장. 확장 불리안 모델 

퍼지 집합, Waller-Kraft, Paice, P-Norm, Infinite-One 과 같은 확장 불리안 모델은 기존의 불리안 검색 시스템에 순위 결정 기능을 부여하기 위하여 개발되어 왔다.

이들은 문서 내에서 색인어의 중요성을 반영하는 색인어 가중치를 이용하는 공통된 특성을 지니고 있다.

확장 불리안 모델을 기반으로 하는 정보 검색 시스템은 다음 <T, Q, D, F> 에 의해 정의 된다.

• T : 질의와 문서를 표현하기 위해 사용되는 색인어들의 집합

• Q : 시스템이 인식할 수 있는 질의들의 집합. Q에 속하는 각각의 질의 q는 색인어들과 논리 연산자 AND, OR, NOT 으로 구성된 불리안 수식

• D : 문서들의 집합. D에 속하는 각각의 문서 d 는 wi 가 색인어 ti의 가중치 일때 {(t1, w1), ..., (tn, wn)}와 같이 표현된다. 색인어 가중치 wi는 0~1 사이의 값을 갖는다.

• F : 문서값을 계산하는 순위 결정 함수. F:D X Q -> [0,1]로 정의

함수 F는 각 쌍의 (d, q)에 0~1 사이의 값을 부여. 이 값은 문서 d 와 질의 q 사이의 유사도이며, 질의 q에 대한 문서 d의 문서값이라고 일컬는다.

AND와 OR에 대한 연산자 계산식은 순위 결정 함수의 성능을 결정하는 가장 중요한 요소.

퍼지 집합 모델 : 연산자 계산식은 2개의 피연산자를 갖는 이항 연산자

Waller-Kraft, Paice, P-Norm, Infinite-One : 2개 이상의 연산자를 갖는 다항 연산자

퍼지 집합은 결합법칙을 만족하나 나머지는 불만족. 결합법칙이 만족하려면 질의 (t1 AND t2) AND t3 와 t1 AND (t2 AND t3)에 대해 서로 같아야 함.

15.1 긍정적 보상 연산자 

피지 집합 모델은 문서들의 순위를 결정하는 문서값을 계산함으로써 불리안 검색 시스템의 단점을 극복하였다. 하지만 AND와 OR 연산을 위하여 사용하는 MIN 과 MAX 연산자가 검색효과를 저하시키는 특성을 지니고 있다.

또한 확장 불리안 모델에서 AND 와 OR 연산을 위해 퍼지 연산자들이 사용 될 때 단일 피연산자 의존 문제와 부정적 보상 문제가 있다.

단일 피연산자 의존 문제

d1 = {(Information, 0), (Retrieval, 0)}

d2 = {(Information, 1), (Retrieval, 0)}

q1 = Information AND Retrieval

곱하기 연산자 AND 연산을 위해 사용되면 d1, d2는 모두 값이 0이 되므로 적절한 검색 결과가 아니게 된다.

부정적 보상 문제

d3 = {(Information, 0.70), (Retrieval, 0.70)}

q2 = Information AND Retrieval

q3 = Information

질의 q2 문서 값 0.49, 질의 q3의 문서 값 0.70. 즉 유사도가 더 낮아지는 문제가 발생한다.

 

퍼지 연산자들이 검색 효과에 미치는 영향을 분석함으로써, 높은 검색 효과를 제공할 수 있는 긍정적 보상 연산자라 불리는 이항 연산자 집합이 정의 되었다.

p: [0, 1] × [0, 1] → [0, 1]

임의의 긍정적 보상 연산자 p는 다음과 같은 특석을 갖는다.

특성 p1 : p(x, x) = x ; 즉, p는 idempotent(멱등:연산을 여러 번 적용하더라도 결과가 달라지지 않는 것)이다.

특성 p2 : MIN(x, y) < p(x, y) < MAX(x,y), x≠y

긍정적 보상 연산자에 대한 위의 정의로부터 긍정적 보상 연산자는 단일 피연산자 의존 특성과 부정적 보상 특성 모두를 지니고 있지 않다. 

15.2 이항 유연한 불리안 연산자

<그림 15.2>는 Waller-kraft, Paice, P-Norm, Infinite-One 모델로부터 유도된 이항 연산자를 보여준다. 이들은 다음과 같은 형태의 함수이다.

b: [0, 1] × [0, 1] → [0 , 1]

이항 연산자 b는 다음과 같은 특성을 갖는다.

글쓴이 주석 - 잘 정리된 특성 b1~4, 정리, 증명이 있으나 이 곳에 요약을 하지 않습니다.

결론적으로 Waller-Kfaft, Paice, P-Norm, Infinite-One 모델의 이항 연산자들은 높은 검색 효과를 제공하는 긍정적 보상 연산자입니다.

15.3 다항 연산자의 필요성

15.4 다항 유연한 불리안 연산자

글쓴이 주석 - 

계속해서 문서를 요약 정리하려 하였으나 수식과 증명, 정의들을 요약하는 것은 왜곡될 수 있으므로 원 글을 그대로 옮겨 와야 하는데, 그대로 옮겨오는 것은 이 글의 취지인 요약과 상반되며 이번 장은 다음 장에 있는 확률 모델로 발전해 가는 과정이므로 간략하게만 요약합니다. .

Waller-Kraft, Paice, P-Norm, Inifiite-One 모델은 다항 연산을 가능하게 함으로써 결합법칙을 만족하지 못하는 문제를 회피하였으나 어떤 경우에 잘못된 문서의 순위를 결정합니다. 이 모델들은 질의에 주어진 모든 색인어들이 문서값의 계산에 있어서 동등하게 고려되어야 한다는 일반적 가정을 위반한 것이며, 그래서 불균등 중요성 문제(Unequal Importance Problem)를 발생시킵니다.

불균등 중요성 문제로 인하여 불리안 모델은 적절한 순위 결정 기능이 아닙니다.