티스토리 뷰
이 내용은 "최신 정보 검색론, 저자 안동언" 책을 공부하면서 간단하게 정리한 내용입니다.
해당 책은 스탠포드의 "CS 276 / LING 286: Information Retrieval and Web Search"에서 사용되는 교재입니다.
관심있으신 분은 위 링크에서 강의 PPT를 제공하고 있으니 참고하시면 좋을것 같습니다.
추가적인 내용이나 잘못된 내용등 피드백 주시면 언제든 감사하겠습니다.
정보 검색?
대규모의 자료 중에서 원하는 자료를 찾는 행위
검색을 쉽게하기 위한 방법이 색인.
찾고자 하는 검색의 대상들, 검색 대상이 되는 문헌(document)의 대상을 컬렉션 혹은 말뭉치(corpus)라고 함.
Boolean검색 모델 :Boolean논리식의 형태로 모든 질의를 작성할 수 있는 정보 검색 모델.
정보 요구(information need)는 사용자가 더 알아보고자 하는 주제.
질의(query)는 사용자의 정보 요구를 컴퓨터에 전달하기 위해 사용자가 표현하는 것.
어떤 문헌이 사용자의 개인적인 정보 요구와 관련하여 가치있다고 판단되면 적합(relevant)하다고 함.
정보검색의 유효성을 평가하는 방법으로 전통적으로는
정확률(precision) : 반환된 결과중 정보 요구에 적합한 비율은 얼마인가?
재현율(recall) : 컬렉션에 포함된 적합 문헌 중 시스템에 의해 반환되 적합 문헌이 차지하는 비율은 얼마인가?
일반적인 색인으로는 정보의 크기가 크기 때문에 역색인 방식으로 색인을 한다.
기본적인 구조는 "단어 -> 포스팅 목록"
역색인 구축의 첫 단계는
1. 색인 대상 문헌을 수집
2. 문헌을 토큰 처리하여 토큰 목록으로 변환
3. 색인어가 될 토큰의 목록을 생성
4. 역색인을 생성하고, 어휘집과 포스팅으로 구성되는 역색인을 생성하여 각 용어가 출현하는 문헌을 색인
정렬 기반 색인 : 각 문헌은 색인 되면서 고유 연속 번호를 갖는다. 이때 색인의 목록을 정렬하여 알파벳 순으로 한다.
토큰화(tokenization)란 문자열을 토큰으로 쪼개는 과정, 언어학적 전처리는 색인 대상 용어들의 집합에 상당하는 토큰 묶음을 구축하는 과정.
불용어(stop word) : 너무 자주 출현하기 때문에 사용자 요구와 일치하는 문헌들을 선택하는데 도움이 되지 않는 단어. 어휘집에서 제거한다. 영어에서 a an he in for be by같은 단어들이 여기에 해당한다.
정규화(용어 동치류) : 겉으로 보기에는 혹은 문자열 그대로 보기에는 다른 단어이지만 실질적인 의미는 같은 단어들의 검색 결과를 같게 하기 위한 것. equvalence class를 생성하여 같은 결과가 나오도록 사상한다. 이를 위해서 발음기호, 대소문자의 통일과 같은 요소를 고려한다.
어근추출(stemming)과 표제어 복원(lemmatization) : 둘 다 한단어가 어미 변환되었고 때로는 파생된 형태로 되어 있는 단어들을 기본형으로 변환하는 것.
어간은 단어의 핵심 의미를 가지고 있는 핵심 부분이며, 접사는 단어에 추가적인 의미를 부여하는 부분입니다.
와일드 카드 질의 : *를 통한 검색을 하는 것, 이를 위해 n-gram방식을 사용하기도 한다.
질의가 들어왔을 떄 질의가 어휘집에 포함되어 있는지를 판단하고 있다면 포스팅에서 포인터를 확인한다.
이때, 어휘집에 조회 연산은 사전구조를 사용한다. 구현에는 크게 해쉬와 탐색 트리 구조를 사용한다.
해싱을 위해서는 해쉬 테이블의 적절한 설계가 필요하다. 해쉬 충돌에 대한 대비등이 필요함.
탐색트리는 주로 B트리를 사용합니다.
B트리는 노드의 데이터가 n개를 가질수 있으면 자식 노드는 n+1이며, 그 값은 정렬되어 있고 크기에 따라 노드에 할당됩니다. 또한 자식노드는 최소한 n/2개의 데이터를 가져야합니다.
편집거리(edit distance)는 두 단어가 주어졌을 때, s1에서 s2로 변환하는데 필요한 편집연산의 최소수입니다. 이와같은 편집거리 연산을 Levenshtein 거리(Levenshtein distance)라고도 합니다.
자카드 계수 : 두 집합 사이의 유사도를 측정하는 방법 중 하나
역색인을 구축하는 과정을 색인 구축, 색인이라고 부름.
정렬 기반 블록화 색인 알고리즘(BSBI, blocked sort based indexing algorithm)
1. 컬렉션을 동일한 크기로 나누다.
2. 기억장치 상에서 각 부분의 trem-doc id쌍을 정렬한다.
3. 정렬의 중간결과를 디스크에 저장한다.
4. 중간 정렬결과를 최종 색인으로 병합한다.
용어를 term ID로 사상시키는 자료 구조가 사전에 구비되어야 함.
단일 패스 메모리 색인(SPIMI, single pass in memory indexing) : term ID대신에 용어를 그대로 사용하며, 각 블록의 사전을 디스크에 기록한다.
분산색인
동적색인 : 컬렉션의 변화가 자주 있는 경우에 두가지 색인을 통해 처리함. 주색인과 보조색인
색인 압축, 캐싱의 사용이 증가되며 디스크에서 기억장치로 자료를 보다 빠르게 전송할 수 있음.
30규칙(Rule of 30) 30개의 가장 일반적인 용어들이 문헌 내 색인어의 30%를 차지한다는 것
손실 압축 : 약간의 정보 손실로 색인어를 줄이는 방법, 대소문자 통일, 어근 추출, 불용처 처리가 여기에 해당됨.
컬렉션에서 구별되는 용어 M의 수를 추정하는 방법
1. Heap 법칙 : 용어의 수 추정, M = k*T^b
2. zipf 법칙 : 용어 분포 모델링, i번째 일반적인 용어의 컬렉션 빈도 cf_i는 1/i에 비례한다.
사전을 압축하는 방법.
왜? 사전은 포스팅 파일에 비교해서 작지만, 응답시간을 결정하는데 있어서 주요한 요인 중 하나이기때문.
1. 스트링 구조의 사전 : 사전을 편찬순으로 어휘 정렬하고 고정길이의 배열로 저장하는 것
2. 블록 저장소 : 스트링 용어 들을 크기k 의 블록에 넣어 묶어주고 각블록의 첫 용어에 단 하나의 용어 포인터만을 배당해 사전을 압축
포스트파일의 압축 (이 내용 다시 공부하기)
1. 바이트 압축
2. 비트 압축
구역색인 : 사전은 그 구역의 문장에서 나오는 모든 어휘들의 어간으로 구성됨.
가중치 구역 점수 계산 : [0,1]사이에 있는 점수를 질의q와 문서 d (q, d)에 부여하는 것.
용어 빈도와 가중치 : 문서d내에서 용어 term이 얼마나 등장, 나타나는지에 따라 가중치를 주기 위한것 term frequency. tf
역문헌 빈도 : idf, log(N/df), df는 document frequency로서 용어 t를 포함하는 문헌들의 수
위 두가지 tf와 idf를 사용한 것이 "tf-idf"가중치이다.
- 적은 수의 문헌에 용어 t가 많이 있으면 높은 값을 가진다.
- 한 문헌이나 많은 문헌들에게 그 용어가 적게 있으면 적은 값을 가진다.
- 사실상 모든 문헌 안에 그 용어들이 있을 경우 낮은 값을 가진다.
벡터를 통한 점수 계산
두 문헌 d1과 d2를 벡터화 하여 코사인 유사도를 계산한다.
피봇 문헌 길이 정규화
7. 완전한 검색 시스템에서의 점수 계산
최상위 목록(champion list, fancy list, top docs) : 사전에 있는 각각의 용어 t에 대해 가장 높은 가중치를 가지는 r개 문헌들의 집합을 미리 계산하는 것
정적 품질 점수 :
문서 중심 점수 계산 : 포스팅 목록들을 병행 탐색하면서 각 문헌들의 점수를 계산하는 것.
용어 중심 점수 계산 : 용어 t의 포스팅 목록에서 tf의 내림차순으로 문헌 d를 정렬하는 것. 문헌들의 정렬은 포스팅 목록마다 서로 다를 것이고, 따라서 모든 질의 용어들에 대한 포스팅 목록들을 병행 탐색하여 점수들을 계산할수가 없다.
군집 가지치기 (cluster pruning) : 문헌 벡터들을 군집화 하는 동안 사전처리가 필요하다. 질의 시간에 코사인 점수들을 계산하기 위한 후보들로 군집에 있는 적은 수의 문헌들만을 고려한다.
정보 검색시스템의 구성 요소
- 중층색인 : 계층을 나누어서 tf값에 따라 1에서 먼저 찾고 그 다음 2에서 찾는 순서의 방법
- 질의용어 근접성 : w(윈도우 안의 단어수)가 더 작을수록 문서 d는 질의에 더욱 잘 부합한다.
- 파싱과 점수 계산 함수의 설계
- 구성 요소 결합
8.정보 검색 평가
적합성을 중심으로 검색 시스템의 성능을 평가함
실험을 위한 컬렉션
- Cranfield 컬렉션 : 1398개의 공기역학 저널 논문 초록과 225개의 질의 집합 및 적합성 을 판단하는 질의문헌쌍
- TREC : 미국 NIST 대규모 정보 검색 실험평가
- NTCIR (NII Test Collection For IR Systems) : 동아이사 언어 및 교차언어 검색
- CLEF
- 20 NewsGroups : 20개의 유즈넷 뉴스 그룹에 대한 1000개의 기사
순위 없는 검색 집합의 평가
- 정확률(precision) :
- 검색된 적합 문헌 / 검색 문헌
- tp / (tp + fp)
- 재현률(recall)
- 검색된 적합 문헌 / 적합 문헌
- tp / (tp + fn)
- 정밀도(accuracy) :
- (tp + tn ) / (tp + tn + fp + fn)
- F척도(F measure)
- F1 = 2PR / (P+R)
순위 검색 결과의 평가
- precision-recall curve
- interpolated precision
- MAP(mean average precision)
- k문서 정확률(precision at k)
- R 정확률 (R-precision)
- ROC
- CG
- 누적이득 cumulative gain
- DCG
- 할인 누적 discounted cumulative gain
- NDCG
척도에 관해 자세히 설명해둔 미디엄 글
False Positive (Type I error) : a non-relevant document is retrieved
False Negative (Type II error) : a relevant document is not retrieved