[정보검색] 제8장 검색 성능 향상 전략 - 제3절 질의확장

이 글은 정영미 교수님의 정보검색연구를 바탕으로 연세대학교 문성빈 교수님의 수업을 공부한 기록입니다.

1. 질의확장

• 질의확장의 목적
  • 이용자가 입력한 초기 질의(initial query)를 수정하여 검색 성능을 높이는 것
• 질의확장은 질의확장과 질의수정을 모두 포함
  • 질의확장은 실제로 새로운 질의어/검색어를 추가하는 것
  • 질의수정은 새로운 질의는 추가하지 않고 초기 질의어의 가중치만 다시 산출하는 것

질의확장 방법

• 초기 질의에 새로운 질의어를 추가한다.
  • 용어들 간 유사도 행렬이나 시소러스, 또는 용어 클러스터링 등을 이용하여 초기 질의어와 유사한 용어들을 새로운 질의어로 추가
  • 질의어에 가중치를 부여하지 않은 시스템에서 흔히 사용
  • 불리언 검색
• 초기 질의에 새로운 질의어를 추가하면서 초기 질의어의 가중치를 다시 산출한다.
  • 초기 질의어의 가중치는 그대로 두고 추가 질의어에만 초기 질의어와의 유사도 정도에 따라 적절한 가중치를 부여하는 것
  • 초기 질의어의 가중치도 다시 산출하는 것
  • 질의어에 가중치를 부여하는 시스템에서 적용
  • 벡터공간 검색
• 초기 질의에 새로운 질의는 추가하지 않고 초기 질의어의 가중치만 다시 산출한다.
  • 확률 검색에서 일차적으로 검색된 문헌들에 대한 적합성 판정 결과 초기 질의어의 적합성 가중치를 다시 부여하는 경우에 해당

전역적 질의확장 vs. 지역적 질의확장

• 추가 질의어를 확보하는 방법에 따라 전역적 질의확장과 지역적 질의확장으로 구분
• 전역적(global) 질의확장
  • 검색 이전에 질의를 확장하는 방법
  • 데이터베이스 내 전체 용어들로부터 초기 질의어와 유사한 용어들을 모두 선정하여 새로운 질의어로 추가하는 방법
• 지역적(local) 질의확장
  • 일차 검색된 문헌들에 출현한 용어들을 이용하여 추가 질의어를 선정하거나 초기 질의어의 가중치를 수정하는 방법
  • 적합성 피드백에 의한 질의확장에 해당

2. 전역적 질의확장

• 이용자가 입력한 원래의 질의어와 유사한 용어를 새로운 질의어로 추가하여 검색을 수행하는 것
• 자동 질의확장
  • 시스템에 의해 자동으로 질의어 추가
• 상호작용적(interactive) 질의확장
  • 시스템이 제시한 유사어나 연관어 중에서 이용자가 새로운 질의어를 선택함으로써 질의어 추가
• 유사도 시소러스에 의한 질의확장
  • 데이터베이스 내 용어들 간의 공기빈도를 이용하여 생성한 유사도 행렬 즉 유사도 시소러스를 사용하여 유사도가 높은 용어를 선택하는 경우
• 전통적 시소러스에 의한 질의확장
  • 전통적인 의미의 시소러스를 사용하여 질의어와 개념적으로 관련된 용어를 선택하는 경우

유사도 시소러스에 의한 질의확장

• 유사도 시소러스를 이용하여 초기 질의어와의 유사도가 높은 용어를 찾아 새로운 질의어로 추가한 다음 검색 진행
• 유사도 시소러스 (Similarity Thesaurus)
  • 용어들 간 유사도 행렬 또는 유사도 행렬로부터 생성한 용어 클러스터
  • 용어 출현 정보에 기반한 문헌-용어 행렬로부터 작성
• 용어-용어 유사도 행렬을 이용하여 추가 질의어를 선정하는 방법
  • 각 질의어와의 유사도가 임계치를 넘는 용어들을 새로운 질의어로 추가
  • 일정한 수의 용어들을 새로운 질의어로 추가

개념 기반 질의확장

• 전역적 질의확장에서 문제가 되는 것: 추가 질의어를 어떻게 확보할 것인가
  • 각각의 질의어와 유사한 용어들을 찾아내어 추가하기 때문에 새로 추가되는 질의어들이 질의 전체의 개념과는 별로 연관성이 없는 경우 O
• 각 질의어가 아니라 질의 전체 개념과 유사한 용어들을 선정하여 질의어로 추가하는 것
• 하나의 질의어와의 유사도가 높은 용어보다는 질의 전체 개념과의 유사도가 높은 용어를 선정
• 질의 개념과 유사한 추가 질의어의 선정 과정
  1. 각 질의어 $q_{t_i}$와 추가 대상 용어 $t$와의 유사도 $SIM(q_{t_i}, \ t)$를 산출한다.
  2. 질의 $Q$와 용어 $t$의 유사도 $SIM(Q, \ t)$를 산출한다.
     • $\sum_{q_{t_i} \in Q} q_i \times SIM(q_{t_i}, \ t)$
  3. 질의 $Q$와의 유사도가 큰 상위 $r$개의 용어를 질의어로 추가한다.

전통적 시소러스에 의한 질의확장

• 대부분의 온라인 데이터베이스 서비스는 이용자가 검색 시 활용할 수 있는 전문적인 온라인 시소러스를 제공
  • 이용자는 키워드만을 질의어로 사용하지 않고 정보요구를 보다 잘 표현하는 용어를 시소러스로부터 선택하여 질의어로 사용할 수 O
  • 시소러스 용어의 사용은 검색의 정확성을 높일 뿐만 아니라 정보요구에 관련된 문헌들을 더 많이 검색할 수 있도록 O
• Greenberg
  • 원 질의어와 어떠한 의미관계를 갖는 용어가 질의확장에 더 유용한가를 실험
  • 자동 질의확장: 동의어(SYN)와 하위어(NT)가 좋은 질의어 후보
  • 상호작용적 질의확장: 연관어(RT)가 좋은 질의어 후보
• Mandala
  • 수작업 시소러스 1종과 자동으로 구축한 유사도 시소러스 2종을 동시에 사용한 질의확장을 수행
  • 이종의 여러 시소러스를 적절한 가중치를 적용하여 질의확장에 사용한 경우가 단일 유형의 시소러스를 사용한 경우보다 더 좋은 성능 O

3. 지역적 질의확장

• 일차 검색된 문헌들을 대상으로 실행
  • 적합성 피드백에 의한 질의확장
• 적합성 피드백에 의한 질의확장의 원칙
  • 적합문헌에 출현한 용어는 질의어로 추가 (질의어에 가중치 부여 X인 경우)
  • 부적합문헌에 출현한 용어는 질의어에서 제외 (질의어에 가중치 부여 X인 경우)
  • 적합문헌에 출현한 질의어의 가중치는 up (질의어에 가중치 부여 O인 경우)
  • 부적합문헌에 출현한 질의어의 가중치는 down (질의어에 가중치 부여 O인 경우
• 질의확장 결과 적합하다고 판정된 문헌들의 내용과 유사한 질의가 작성
• 벡터공간 검색, 확률 검색, p-norm 검색 등에서 사용

적합성 피드백(Relevance Feedback)에 의한 질의확장

• 지역적 질의확장에서 적합성 피드백은 적합성 판정을 누가 하는가에 따라 이용자 피드백과 시스템 피드백으로 구분
• 이용자 피드백 (User Feedback)
  • 초기 질의에 의한 검색 결과 이용자가 검색된 n개의 문헌에 대해 직접 적합문헌과 부적합문헌을 판정하는 것
  • 시스템은 입력된 적합성 정보를 이용하여 질의확장을 한 다음 이차 검색을 수행
• 시스템 피드백 (System Feedback = Blind Feedback = Pseudo Relevance Feedback)
  • 검색 시스템이 검색 결과 상위 n개의 문헌을 모두 적합문헌으로 판정하는 것
  • 시스템은 이용자의 개입 없이 질의확장을 할 수 O

적합성 피드백에 의한 질의확장에서 고려해야 할 중요한 문제

• 적합성 판정에 사용할 문헌의 수를 몇개로 할 것인가. (Learning Sample Size)
  • 이용자 피드백: 이용자가 감내할 수 있는 수준에서 적합성 판정 대상 문헌의 수를 결정하는 것이 바람직
  • 시스템 피드백: 상위 n개의 문헌이 모두 적합문헌으로 판정되는 것이기 때문에 대체로 5개 이내의 소수의 문헌을 사용하는 것이 효과적
• 적합문헌에 출현한 용어 가운데 얼마를 추가 질의어로 사용할 것인가.
  • 적합문헌에 부여된 모든 색인어를 추가 질의어로 선택
  • 중요도에 따라 상위 n개를 선정

적합성 피드백에 의한 질의확장 공식

• 적합성 피드백에 의한 질의확장은 벡터공간 검색에서 가장 많이 논의
• 표준 로치오(standard Rocchio) 공식
• $Q’ = \alpha \times Q + \beta \times \frac{1}{n_1} \sum_{i=1}^{n_1} R_i - \gamma \times \frac{1}{n_2} \sum_{i=1}^{n_2} S_i$
  • $Q$: 초기 질의 벡터
  • $Q’$ : 수정 질의 벡터
  • $n_1$ : 검색된 적합문헌 수
  • $n_2$ : 검색된 부적합문헌 수
  • $R_i$ : 적합문헌 벡터
  • $S_i$ : 부적합문헌 벡터
  • $\alpha, \beta, \gamma$ : 각 항의 비중을 나타내는 파라미터 : 로치오 가중치
  • $Q’$은 원래의 질의벡터 $Q$에 적합문헌들의 평균 벡터와 부적합문헌들의 평균벡터의 차이를 더해준 값
• Ide_Regular 공식
  • $Q’ = Q + \sum_{i=1}^{n_1} Ri - \sum_{i=1}^{n_2} S_i$
  • $\alpha = \beta = \gamma = 1$로 고정
• Ide_Dec_Hi 공식
  • $Q’ = Q + \sum_{i=1}^{n_1} R_i - S1$
  • 가장 상위에 오는 부적합문헌 한개만을 질의수정에 반영하는 것

예제) 로치오 공식, Ide_Regular 공식, Ide_Dec_HI 공식을 이용하여 질의수정 (단 α = 1, β = 1/2, γ = 1/4)

$Q = (5, 0, 3, 0, 1)$
$D1 = (3, 1, 2, 1, 2)$ : R
$D2 = (2, 2, 2, 1, 1)$ : NR
$D3 = (2, 0, 1, 2, 1)$ : R
$D4 = (2, ,0, 0, 2, 1)$ : NR

Rocchio
$Q’ = 1 \times (5,0,3,0,1) + \frac{1}{2} \times \frac{(3,1,2,1,2) + (2,0,1,2,1)}{2} - \frac{1}{4} \times \frac{(2,2,2,1,1) + (2,,0,0,2,1)}{2}$

Ide_Regular
$Q’ = (5, 0, 3, 0, 1) + { (3, 1, 2, 1, 2) + (2, 0, 1, 2, 1) } - { (2, 2, 2, 1, 1) + (2, ,0, 0, 2, 1) }$

Ide_Dec_Hi_
$Q’ = (5, 0, 3, 0, 1) + \{ (3, 1, 2, 1, 2) + (2, 0, 1, 2, 1) \} - (2, 2, 2, 1, 1)$

전역적 분석을 도입한 지역적 질의확장

• 지역적 유사도 시소러스 (Local Similarity Thesarus) 기법
  • 지역적 유사도 시소러스는 초기 질의에 의해 검색된 문헌들의 집합이나 또는 상위 n개의 문헌에 출현한 용어들 간의 유사도를 측정하여 생성 (전역적 시소러스와의 차이점)
  • 지역적 유사도 시소러스를 이용하여 질의어와 유사도가 높은 용어들을 찾아내어 새로운 질의어로 추가 (전역적 질의확장과의 공통점)
• 지역적 문맥 분석 (Local Context Analysis) 기법
  • 일차 검색에서 상위 n개의 단락들을 검색한 다음 이 단락들에 포함된 개념(명사구)을 질의어와의 유사도 순으로 순위화하여 상위 n개의 개념을 추가 질의어로 선정
  • 질의어와 유사한 용어로 키워드 형태가 아닌 명사구를 선정하여 추가 질의어로 사용한다는 점에서 차이 O
  • 문헌 전체가 아니라 일정한 크기의 단락에서의 공기빈도를 기반으로 유사도를 산출한다는 점에서 차이 O