Information Retrieval (Chapter 5: 질의연산) 서정연교수 Office: 공학관 816 Tel: 705-8488 Email: seojy@sogang.ac.kr
소개 문제: 해결책: 검색된 연관문서의 수가 적다. 사용자 요구를 정확하게 질의로 표현할 수 없다. 사용자 질의에 대해 검색된 문서가 거의 없을 수 있거나, 관련된 문서는 거의 없을 수 있다. 사용자 요구를 정확하게 질의로 표현할 수 없다. 대부분의 사용자는 만족한 결과를 얻기 위해서 질의 작성에 많은 시간을 소비한다. 해결책: 초기 질의를 사용해서 연관 정보를 검색한다. 검색된 문서를 사용해서 질의를 재작성한다. 질의 확장(term expansion): 새로운 용어를 원래 질의에 추가한다. 용어 가중치 재부여 (term reweighting): 확장된 질의의 용어에 대해서 가중치를 재부여한다.
소개 (계속) 질의 확장 질의 용어 가중치 재부여 질의에 포함된 용어를 변경한다(추가, 변경, 삭제). 검색되지 않은 연관문서를 검색하는데 도움이 된다. 예) D1 : unretrieved relevant document D2 : retrieved relevant document D1 = (information, retrieval, system) D2 = (Database, retrieval, manager) 초기: q1 = Database 확장 질의: q1’ = Database or retrieval 질의 용어 가중치 재부여 가중치를 조정하며, 순위화와 밀접하게 관련되어 있다. 연관문서에 출현되는 질의용어의 가중치를 증가시킨다. 검색되지 않은 연관문서를 추가 검색하는 것에는 도움이 되지 않는다.
사용자 연관 피드백 연관 피드백에서 사용자 역할 검색된 문서의 리스트를 보여주고, 연관된 문서를 선택한다. 연관 피드백의 기본 개념 중요한 용어나 표현을 선택: 사용자에 의해서 연관문서로 확인되면 그 문서에 포함된 용어는 중요한 용어이다. 새로운 질의 작성에서 선택된 용어의 중요도를 증가한다. 새로운 질의는 항상 연관문서의 순위는 좋아지고 비연관 문서의 순위는 나빠진다. 연관 피드백을 사용하면 정확률은 항상 좋아진다.
소개 (계속) 연관 정보: 사용자 질의에 적합한지 아닌지에 관한 정보: 연관 문서 집합과 비연관 문서 집합 정보검색 시스템 유사도 계산 질의 문서 DB 검색 결과 연관 피드백 사용자 연관 정보 연관 정보: 사용자 질의에 적합한지 아닌지에 관한 정보: 연관 문서 집합과 비연관 문서 집합
질의 재작성을 위한 세 가지 방법 사용자 연관 피드백 지역 피드백(Local feedback) 사용자로부터 오는 피드백 정보에 기반한다. 지역 피드백(Local feedback) 초기 검색된 문서 집합으로부터 생성된 정보에 기반한다. 전역 피드백(Global feedback) 문서 컬렉션으로부터 생성된 정보에 기반한다.
사용자 연관 피드백 연관 피드백 검색된 문서를 보여준다. 검색된 문서의 연관 여부를 조사한다. 연관된 문서를 표시한다. 중요한 용어를 선택한다. 중요한 용어의 중요도(가중치)를 증가한다. 두 가지 기술 질의 확장: 연관문서로부터 추출된 용어를 추가한다. 용어가중치 재부여 : 연관판정에 의해서 용어 가중치를 조정한다. 장점 질의 재작성 과정의 세부적인 내용이 사용자에게 숨겨진다. 전체 검색 과정을 작은 단계로 나누어 처리된다. 연관용어는 강조하고 비연관 용어는 강조하지 않는다. 사용자가 손으로 시스템이 자동으로
벡터 모델에서 연관 피드백 기본 개념 연관 문서의 용어 가중치 벡터에 가깝도록 질의를 재작성한다. 표기법 Dr : 사용자가 확인한 검색된 연관 문서 집합 Dn : 검색된 비연관 문서 집합 Cr : 컬렉션 Dall에서 연관 문서 집합 | x | : 문서 수, 예) |Dn| : Dn의 문서 수 최적 질의 재작성
벡터 모델에서 연관 피드백(계속) 문제: Cr을 미리 알 수 없다. 질의 재작성을 위한 세 가지 방법 : : 비연관 문서 중에서 가장 높은 순위의 문서 예전에는 Ide_Dec_Hi가 다른 두가지보다 약간 성능이 좋은 것으로 알려져 왔으나, 최근에는 셋 다 비슷한 결과를 내는 것으로 평가됨 Dr에서 정보는 Dn의 정보보다 더 중요하다. 그래서 대개, < 이다. 만일 아예 = 0 으로 간주하면 긍정적 피드백(positive feedback) 장점: 간단하고 좋은 결과를 가져온다. 단점: 최적 기준이 없다.
확률모델에서의 용어가중치 재부여 확률 연관 모델 P(ki|R) / P(ki|R)의 계산 방법 초기 추정 P(ki|R) : 연관문서 R에서 ki를 관찰할 확률 P(ki|R) / P(ki|R)의 계산 방법 초기 추정 초기 추정을 통한 개선 방법: Dr: the set of relevant retrieved docs, Dr,i: Dr에서 ki를 포함하는 문서 집합 위의 식을 확률연관모델 식에 대입하면 질의 재작성 모델은 다음과 같다 , where ni is the # of doc with ki for all ki
확률모델에서의 용어가중치 재부여(계속) 다른 질의 재작성 모델 장점 : - 피드백 과정이 가중치 조절과 밀접하게 관련되어 있다. - 용어들이 서로 독립이라는 가정과 이진 문서 색인 (wi,q {0, 1} and wi,j {0, 1}) 하에서는 용어 가중치 재부여는 최적이다. 단점: - 피드백 과정에서, 문서의 용어 가중치는 고려되지 않는다. - 이전 질의작성에 사용된 용어 가중치는 무시된다. - 질의 확장을 사용하지 않는다. - 일반적으로, 벡터 모델에서 연관 피드백 만큼 좋은 성능을 보이지 않는다.
연관 피드백의 평가 단순한 방법(Simplistic manner) 연관 피드백을 사용하지 않을 경우의 성능과 비교한다. 성능(재현율/정확률)이 크게 개선된다. 문제점: 비현실적인 방법 연관피드백의 기본 가정은 연관 문서는 이미 사용자에게 보여진 것이다. 잔여 컬렉션 방법(Residual collection method) (de facto standard) 초기 검색을 수행한다. 연관 피드백을 위해서 검색된 문서 중에서 상위의 x개만 사용자에게 보여준다. 보여지지 않았던 컬렉션(잔여 컬렉션)에 대해서만 평가한다. 이 방법은 편향되지 않으며 현실적인 평가 방법이다. 문제점: 재현율과 정확률이 낮을 수 있기 때문에 다른 방법과 직접 비교해서는 안된다.
연관 피드백의 평가(계속) 시험과 제어(Test and control) 순위 고정(Rank freezing) 임의로 문서 콜렉션을 반으로 나눈다. 그 중 반을 이용해서 검색하고 피드백 정보를 구한다. 다른 반을 이용해서 새 질의를 이용해서 평가한다. 두 번째의 평가 결과만을 비교한다. 순위 고정(Rank freezing) 검색을 수행한다. 연관된 문서의 순위는 고정하거나(partial freezing) 모든 검색된 문서의 순위를 고정시키고(full freezing) 평가한다. 새로 검색된 문서가 고정되지 않은 순위에 얼마나 차지했는지를 평가한다.
자동 지역 분석 질의 용어에 관계된 용어를 찾는다. 사람의 개입 없이 질의를 확장한다. 전역적 방법 지역적 방법 이미 알려진 연관문서에 포함된 용어는 아직 알려지진 않은 연관문서를 찾는데 사용된다. 자동으로 연관 용어를 찾는 방법 질의 용어에 관계된 용어를 찾는다. 동의어, 접사의 변형, 문서에서 질의 용어와 밀접한 용어 사람의 개입 없이 질의를 확장한다. 접근 방법 전역적 방법 컬렉션 내 전체 문서를 사용 용어 연관성을 나타내는 전역적 유사 시소러스 구조를 작성 사용자는 자신에게 제시된 이 구조를 이용하여 질의 확장을 위한 용어를 선택 지역적 방법 질의 q에 의해 검색된 문서들을 이용 질의 시간에 질의 확장을 위한 용어를 선택 사용자의 도움이 필요 없음 지역 클러스터링, 지역 문맥 분석 방법
지역 클러스터링을 이용한 질의 확장 질의 확장 = 클러스터링 클러스터의 종류 연관 클러스터(association clusters) 메트릭 클러스터(metric clusters) 스칼라 클러스터(scalar clusters) 표기법 V(s) : 형태소 s에 대한 문법적 변형 집합, 예) V(love) = {love, loves, ...} Di : 지역 문서(검색된 문서) 집합 Vi : 지역 단어(Di에 있는 구별된 모든 단어) Si : Vi에서 생성된 모든 스템(어근) 웹 환경에는 비현실적: 키워드 확장에 드는 오버헤드가 너무 큼 인트라넷, 특정 분야의 문서 컬렉션 검색에 유용 Relevance feedback은 검색속도보다는 정확성을 위한 방법
연관 클러스터 (Association Cluster) 문서에 속한 스템의 공기(co-occurrence)에 기반한다. 문서 내에서 자주 공기하는 스템은 동의관계를 가진다. 연관도(correlation) 연관 행렬(association matrix) [su,v] : Unnormalized: su,v = cu,v Normalized 지역 연관 클러스터(local association cluster)를 구하는 방법 스템 su에 대해서 함수 Su(n)를 사용해서 가장 큰 값을 가지는 n개의 su,v를 선택한다. Su(n) : u번째 줄에서 n개의 가장 큰 값을 가지는 n개의 su,v를 구한다. : 문서 dj에서 스템 si의 빈도
메트릭 클러스터 두 용어 간의 거리에 기반한다. 같은 문장에서 출현하는 두 용어는 문서 내에 멀리 떨어져 나오는 출현하는 다른 용어에 비해서 관련성이 크다. 연관도(correlation) 연관 행렬(association matrix) [su,v] : Unnormalized : su,v = cu,v normalized 지역 연관 클러스터를 구하는 방법 스템 su에 대해서 함수 Su(n)를 사용해서 가장 큰 값을 가지는 n개의 su,v를 선택한다. : 같은 문서에서 ki과 kj 사이의 단어 수
스칼라 클러스터 Su(n)과 Sv(n)을 비교해서 구한다. 비슷한 이웃을 가지는 두 스템이 동의어 관계를 가진다. 연관 행렬 [su,v] : 지역 연관 클러스터를 구하는 방법 스템 su에 대해서 함수 Su(n)를 사용해서 가장 큰 값을 가지는 n개의 su,v를 선택한다. : (Su,1, Su,2, . . ., Su,n) and : (Sv,1, Sv,2, . . ., Sv,n)
Interactive Search Formulation 이웃 관계 어떤 스템 와 연관된 클러스터에 속하는 스템 을 의 이웃이라 한다. 또는 탐색동의어(searchonym) 의미상 동의어라기보다 현재 질의 문맥에서 서로 연관된 키워드 누락된 동의어를 보충하고 탐색 질의 확장해준다. x
Interactive Search Formulation(계속) 이웃 스템을 이용한 질의 확장 각 스템 에 대해 클러스터 에서 m개의 이웃 스템 선택 이웃 스템을 질의에 추가 정규화된 클러스터와 비정규화된 클러스터의 결합 비정규화된 클러스터는 고빈도 스템들을 서로 묶는 경향 정규화된 클러스터는 저빈도 스템을 묶는 경향 두 클러스터의 결합은 연관 관계를 더 잘 표현할 수 있다. 검색 개선을 위한 연관 스템 정보 사용 만약 연관 계수 가 정의된 임계값보다 크다면 스템 의 이웃 스템은 스템 의 이웃 스템으로 해석될 수 있고 역도 성립한다. 불리언 질의를 처리 할 때, 매우 큰 유연성 제공 and : a neighbor stem of
Interactive Search Formulation(계속) 보고된 실험 결과 지역 클러스터링 방법의 유용성을 보여줌 메트릭 클러스터가 순수 연관 클러스터보다 더 나은 성능을 보인다. 두 용어의 연관 관계가 두 용어의 거리와 밀접한 관련이 있다. 클러스터가 지역적인 경우만 해당한다. 전역적 문맥에서는 클러스터가 컬렉션 내의 전체 문서로 유도되고 성능은 지역 클러스터와 다르다.
지역 문맥 분석을 통한 질의 확장 지역 클러스터링 VS. 전역 분석 지역 문맥 분석 지역 클러스터링 전역 분석 질의에 의해 검색된 상위 문서들 속에 있는 용어 공기 정보에 기반 각 질의와 가장 가까운 이웃 용어들이 원래 질의의 확장에 사용 전역 분석 용어 상관관계를 전체 문서 컬렉션에서 찾음 전체 컬렉션에서 용어 관계를 명시하는 시소러스 구축과 관련되어있음. 용어는 개념으로 다뤄짐 시소러스는 개념 관계 구조로 볼 수 있음 시소러스 구축에 있어 작은 문맥과 구 구조를 이용 지역 문맥 분석 전역 분석의 아이디어를 지역 문서에 적용 전역 분석과 지역분석을 결합
지역 문맥 분석을 통한 질의 확장(계속) 지역 문맥 분석 절차 상위의 n개의 단락(고정 길이의 텍스트)을 검색한다 상위 순위 단락에 나타나는 각 개념 c에 대해 해당 개념과 전체 질의와의 유사도 sim(q, c)를 계산한다. tf-idf 방법의 변형 이용 상위 m개의 개념을 원래 질의 q에 첨가한다. 첨가된 개념에 가중치를 (1 - 0.9 i / m)로 할당한다. i : 마지막 개념 순위에서 해당 개념의 순위 원래 질의 q의 개념에는 가중치를 2로 할당한다.
지역 문맥 분석을 통한 질의 확장(계속) 유사도 : frequency of term in the j-th passage : frequency of the concept c in the j-th passage N: the number of passages in the collection : the number of passages containing the term : the number of passages containing the concept c : constant parameter which avoids a value equal to zero for sim(q,c) 저빈도 질의 용어를 강조하기 위해 TREC 데이터에 잘 동작하도록 고안, 다른 데이터에 적용하기 위해서는 튜닝 필요
자동 전역 분석 컬렉션 전체 문서로부터 추출된 정보를 이용하여 질의를 확장 컬렉션 전체 문서를 이용하여 작성된 유사 시소러스 구조를 사용 종류 유사도 시소러스에 기반한 질의 확장 통계 시소러스에 기반한 질의 확장 시소러스를 작성하는 방법과 질의 확장을 위한 용어 선택 방법은 매우 상이함
시소러스 시소러스는 용어들 사이의 관계를 지니는 용어의 계층 구조이다. 용어는 단어 혹은 구가 될 수 있다. 시소러스는 주제별로 설계되며 영역에 의존한다. computer-aided instruction see also education UF teaching machines BT educational computing TT computer application RT education teaching CC C7810C FC c7810cf 1979 INSPEC 시소러스 see also: cross reference NT: more specific term BT: more general term TT: root node RT: related term UF: alternative CC,FC: INSPEC classification scheme 구성? 개념 노드 관계 링크 : 넓은 용어(Broader-Term), 좁은 용어(Narrower Term), 동의관계(Synonym) 등 ...
시소러스(계속) 시소러스의 목적 큰 컬렉션으로부터 연관된 문서를 효과적으로 검색하기 위해서 색인: 검색: 문서를 표현(색인)하기 위해 가장 적절한 시소러스 용어를 선택하여 사용할 수 있다. 검색: 질의 재작성 과정에서 가장 적절한 용어를 선택할 수 있다. 충분한 문서가 검색되지 않았다면, 시소러스의 관계링크를 따라서 질의를 확장한다. 너무 많은 문서가 검색되면, 시소러스에서 더 구체적인 용어를 선택해서 질의를 확장한다.
시소러스(계속) 시소러스를 어떻게 구축하는가? 수동으로 자동으로 아주 개념적인 작업이고 많은 지식이 필요하다. 많은 노력이 필요하다. 자동으로 be challenging
검색에서 시소러스의 역할 시소러스 시소러스 시소러스 일반 색인 용어 질의 재작성 - 넓게(일반적 의미로) 검색된 문서 순위화된 문서 불리안 질의 불리안 IR 시스템 순위화 시스템 시소러스 문서 DB 시소러스 색인어를 시소러스 용어로 변경 시소러스 일반 색인 용어 질의 재작성 - 넓게(일반적 의미로) - 좁게(구체적 의미로) 문서 컬렉션
유사도 시소러스 구축 Term vector N: the number of documents in the collection t: the number of terms in the collection : frequency of occurrence of the term in the document : the number of distinct index terms in the document : the inverse term frequency : the maximum of all factors for the i-th term
유사도 시소러스 구축(계속) 과 의 유사도 스칼라 연관 행렬을 위한 연관 계수의 변형식 과 의 유사도 스칼라 연관 행렬을 위한 연관 계수의 변형식 문서를 용어 공기 관계 추출을 위해 사용하는 것이 아니라 용어를 색인하기 위한 색인 요소로 사용 전역 유사도 시소러스는 컬렉션에 나타나는 모든 색인어 쌍에 대해 연관 계수를 구함으로 구축 계산 비용 높으나 시소러스가 한번만 계산되면 되고, 점진적인 업데이트 가능
유사도 시소러스 기반 질의 확장 전역 유사도 시소러스에 주어지면 1. 개념 공간에서 질의를 표현한다. 2. 질의 q와 질의 용어에 관련된 용어 kv 사이의 유사도 sim(q, kv)를 계산한다. : weight associated to the index-query pair
유사도 시소러스 기반 질의 확장(계속) [그림 5.2] 질의 중심 Qc로부터 주어진 용어 Kv까지의 거리는 각각의 질의 용어로부터 Kv까지의 거리와 매우 다를 수 있다 3. sim(q, kv)에 따라 상위 r개의 용어를 사용해서 질의 q를 q’으로 확장한다. 질의 q’에서 kv의 가중치
유사도 시소러스 기반 질의 확장(계속) 세개의 다른 컬렉션에서 성능 향상(20%내외) 문서와 질의 사이의 용어-개념 공간에서의 유사도 일반화된 벡터 모델과 비슷 일반화된 벡터 모델과의 차이점 가중치 계산 방법의 차이 용어-개념 모델에서는 상위 r개의 용어만이 질의 확장을 위해 사용
통계 시소러스에 기반한 질의 확장 전역 시소러스 1. 전체 컬렉션에서 관련된 용어의 무리로 클래스를 구성한다. 2. 질의 확장을 위해 1에서 구성된 연관 용어를 사용한다. 3. 확장을 위해 선택된 용어는 높은 용어 변별값(term discrimination value)를 가져야 한다. 주로 저빈도 용어 저빈도 용어는 용어에 대한 정보 부족으로 클러스터링하기 어렵다. 문서를 클래스로 컬러스터링하여 동일 문서 클래스에 출현하는 저빈도 용어를 한 시소러스 클래스로 묶음
통계 시소러스에 기반한 질의 확장(계속) 문서 클러스터링을 위해 완전 연결 알고리즘(complete link algorithm)을 사용한다. 1. 각 문서를 하나의 클러스터로 지정한다.(bottom-up 방법) 2. 모든 클러스터 사이의 유사도를 계산하다. 3. 클러스터 간 유사도가 가장 높은 두 클러스터 [Cu, Cv] 를 결정한다. 4. 두 클러스터 Cu와 Cv를 하나의 클러스터로 결합한다. 5. 정지 기준을 만족하지 못하면 단계 2로 간다. 6. 클러스터의 계층을 결정한다.
Single-link Clustering The similarity of two clusters is the similarity between the two most similar items, each of which is taken from a different cluster. Given clusters X and Y , similarity (X, Y ) = max (similarity (x, y)) where x X; y Y Generates a ``chaining'' effect Generates a small number of large, poorly coupled clusters. max
Single-link Clustering -- An Example Taken from Salton89 page 330 Process in the order of similarity value: AF-AE-BF-BE-AD-AC.. A F 0.9 AF A F 0.9 0.8 E AE
Single-link Clustering -- An Example (2) F 0.9 E 0.8 B BF A F 0.9 E 0.8 B 0.6 0.5 D C AD A F 0.9 E 0.8 B 0.6 D AC
Single-link Clustering with Threshold A F 0.9 E 0.8 C D B 0.7 Threshold = 0.7 3 clusters A F 0.9 E 0.8 B 0.6 0.5 D C A F 0.9 E 0.8 C D B 0.7 0.6 0.5 Threshold = 0.5 1 cluster
Complete-link Clustering The similarity of two clusters is the similarity between the two least similar items, each of which is taken from a different cluster. Given clusters X and Y , similarity (X, Y ) = min (similarity (x, y)) where x X; y Y Generates a large number of small, but tightly coupled clusters.
Complete-link Clustering-An Example Can any node be added to AF? (only B and E are high enough to be consider) Sort the similarity values in descending order: 0.9 A F Sim(A,E) = 0.8 Sim(F,E) = 0,3 Sim(AF, E) = 0.3 Sim(B,F) = 0.8 Sim(B,A) = 0,3 => Sim(AF, B) = 0.3 AF = 0.9 AE = 0.8 BF = 0.8 BE = 0.7 AD = 0.6 AC = 0.6 BD = 0.5 CE = 0.5 BC = 0.4 DE =0.4 AB = 0.3 CD = 0.3 EF = 0.3 CF = 0.2 DF = 0.1 Can any node be added to BE? 0.7 B E Sim(B,D) = 0.5 Sim(E,D) = 0.4 Sim(BE, D) = 0.4 Sim(E,C) = 0.5 Sim(B,C) = 0.4 Sim(BE, C) = 0.4 0.7 B E C 0.4 Can any node be added to BCE? Sim(E,D) = 0.4 Sim(B,D) = 0.5 Sim(C,D) = 0.3 Sim(BCE, D) = 0.3
Complete-link Clustering-An Example 0.7 B E C 0.4 D 0.3 AF = 0.9 AE = 0.8 BF = 0.8 BE = 0.7 AD = 0.6 AC = 0.6 BD = 0.5 CE = 0.5 BC = 0.4 DE =0.4 AB = 0.3 CD = 0.3 EF = 0.3 CF = 0.2 DF = 0.1 0.7 B E C 0.4 D 0.3 0.9 A F 0.1
Complete-link Clustering with Threshold 0.7 B E C D 0.9 A F Threshold 0.7 0.7 B E C D 0.9 A F Threshold 0.5 0.7 B E C 0.4 D 0.3 0.9 A F 0.1 0.7 B E C D 0.9 A F 0.5 0.4 Threshold 0.3 0.7 B E C D 0.9 A F 0.5 0.4 Threshold 0.4
통계 시소러스에 기반한 질의 확장(계속) 완전 링크 알고리즘을 이용해 작성된 세 클러스터 계층 (클러스터간 유사도는 타원 내 숫자로 표시)
통계 시소러스에 기반한 질의 확장(계속) 전역 시소러스의 클래스를 구성하는 용어 선택 사용자로부터 3개의 매개변수를 구한다. Threshold class(TC) Number of documents in a class(NDC) Maximum inverse document frequency(MIDF) 시소러스 클래스를 생성하기 위한 클러스터 Cv와 Cu을 선택한다. sim(Cu, Cv) > TC NDC를 사용하여 대상 클러스터의 크기(문서수)를 제한 |Cu+v| < NDC라면 NDC에 의해 더 작은 클러스터 Cu+v를 선택한다. 이렇게 선택된 문서 클러스터 중 MIDF를 이용, 저빈도 용어만이 시소러스 클래스에 참여하도록 한다. 너무 일반적인 용어는 좋은 동의어가 아니다.
통계 시소러스에 기반한 질의 확장(계속) 시소러스 클래스를 사용한 질의 확장 시소러스 클래스 C에 대한 평균 용어 가중치 wtC이다. 시소러스 클래스 가중치 Wc 4개의 컬렉션을 이용한 실험에서 이러한 가중치 계산이 좋은 결과(검색 성능향상)를 나타내었음
연관 피드백 분야의 연구 동향 및 쟁점 현대 정보 검색시스템의 그래픽 인터페이스에 바로 적용해서 연관피드백을 적용할 수 있음 그러나 상호작용성이 중요하므로 피드백 정보를 얻는 새로운 기술이 요구됨 전역 분석 기술은 질의에 제공된 지역 문맥을 활용함 중요한 연구 과제 지역 분석, 전역 분석, 시각 표시 장치와 대화적 인터페이스를 조합하는 문제 중요한 쟁점 사용자로 하여금 문서 공간을 시각적으로 항해하는 문제 질의 작성을 돕는 단서를 제공하는 문제