Information Retrieval Part 1 sigma α 2015.11.01. sigma α
Information Retrieval (IR): Outline Issues Information Retrieval Boolean Retrieval The term vocabulary and posting lists Dictionaries and tolerant retrieval Scoring, term weighting The vector space model Evaluation in IR Relevance Feedback Probabilistic information retrieval Language models for IR sigma α 2
sigma α Issues
Issues 페이스북, 드론으로인터넷공급하겠다 https://www.facebook.com/makeyourfutures/videos/59805074 7002870/ http://www.bloter.net/archives/234650 sigma α 4 http://techneedle.com/archives/20576
Issues http://contest.welldone.to/contest/read/105839 sigma α 5
Issues http://www.slideshare.net/perone/deep-learning-convolutional-neuralnetworks?utm_content=buffer54c8c&utm_medium=social&utm_source=plus.google.com&utm_campaign=buffer sigma α 6
Issues http://www.slideshare.net/perone/deep-learning-convolutional-neuralnetworks?utm_content=buffer54c8c&utm_medium=social&utm_source=plus.google.com&utm_campaign=buffer sigma α 7
sigma α Information Retrieval
Information Retrieval Natural Language (NL) 개인의생각을공유할때자연어 ( 즉, 한국어, 영어등 ) 를사용 자연어는말, 글등으로표현및보관 Information Retrieval (IR) 정보검색은구조화되지않은임의의대용량정보에서사용자가원하는정보를검색하고찾아주는것 sigma α 9
sigma α Boolean Retrieval
Boolean Retrieval Boolean model은정보검색시스템에서가장간단한모델질의 (query) 들을이진표현으로적용 예를들어, Antony and Cleopatra 이진표현을만족하는모든문서들을찾음 Term-document incidence matrix ( 텀 - 문서발생빈도메트릭트 ) 해당메트릭스는문서내에질의의 term 이존재하면 1, 그렇지않으면 0 으로표현 sigma α 11
Term-document incidence matrix Incidence vectors ( 발생빈도벡터 ) 질의 BRUTUS 와 CAESAR 가같이출현, CALPURNIA 는출현하지않는문서를검색 에대한계산 BRUTUS AND CAESAR AND NOT CALPURNIA 에대한검색 110100 AND 110111 AND 101111 = 100100 sigma α 12 NOT 010000
0/1 vector for BRUTUS BRUTUS 가 Anthony and Cleopatra, Hamlet 문서에등장한것을알수있음 sigma α 13
Bigger collections Term-document incidence matrix 방법으로벡터를표현하면의미없는데이터 0 이많아짐 희소행렬 N = 10 6 documents, each with 1000 tokens total of 10 9 tokens If 6 bytes per token, size of document collection is about 6 10 9 = 6GB If there are 500,000 terms 500,000 10 6 매트릭스에는 1 보다 0 이훨씬더많음 더좋은표현방법 : 필요없는데이터 0 은버리고, 1 에대해서만표현 Inverted index sigma α 14
Inverted index 역색인 : 단어가포함된문서만인덱싱하는방법 Documents Dictionary Postings sigma α 15
Inverted index construction sigma α 16
First: Tokenizing & preprocessing sigma α 17
Second, third: Generate Sorting posting sigma α 18
Forth: Creating posting lists sigma α 19
Query processing in posting lists 사용자가다음질의를검색 (Intersect): BRUTUS AND CALPURNIA This is linear in the length of the posting lists This only works if posting lists are sorted sigma α 20
Query processing in posting lists Algorithm sigma α 21
sigma α The term vocabulary and posting lists
Term definitions Word 문자열을 character 단위로나눈것들 Term 형태소나음절등으로정규화시킨단어 Token 문서내에서발생하는단어나 term Term과는다르게문서내에서등장한단어그대로를사용 Type 같은문자시퀀스를유지하는모든 token 들의클래스 sigma α 23
Tokenization 입력된질의를토큰별로나누는것 Input: Friends, Romans, countrymen. So let it be with Caesar Output: [friend], [roman], [countryman], [so], [let], [it], [be], [with], [caesar], 각토큰은 posting list 의후보단어들이됨 이 tokenization 도일관성이중요 ( 다음을고려해야함 ) 띄어쓰기구분 복합명사 : 한국전자통신연구원, 한국전자통신연구원 하이픈 : state-of-the-art, co-education 불용어 정규화 숫자표현 : [3/20/91 == Mar 20, 1991], [(800) 234-2333 == 800.234.2333] 등 sigma α 24
Tokenization Normalization ( 정규화 ) 문서내에서등장한단어들중에약어나, 별칭등으로여러형태로표현하는경우가있음 일관성저하 질의에대하여더좋은결과를얻기위해하나의형태로맞춰야함 정규화사용 예를들어, U.S.A == USA, Windows == windows, 박천음 == 그, 같은발음기호의단어들등 Stop word ( 불용어 ) 정보검색에서의미가없는단어들, 즉검색에큰도움이되지않는단어들을말함 예를들어, a, an, and, are, as, by,, in, the etc., 감탄사등 이런불용어를포함하면메모리낭비, 오더증가, 성능하락등의패널티가포함됨 따라서 posting list 를구성하는 term 에서제외함 보통 term 단위에서적용, phrase 단위에서는예외 sigma α 25
Tokenization Case folding 대문자를소문자화시켜서일관성유지 Lemmatization 형태소분석을이용하여단어표현의원형을찾음 예를들어, 감다 [ 가 + ㅁ + 다 ], [ 감 + 다 ], is, are [be], car, cars, car s, cars [car] Stemming Lemmatization 과유사하지만 stemming 은단어의어근을추출하는방법 Crude heuristic process that chops off the ends of words Grep 과같이패턴에의해처리되기때문에언어에종속적 예를들어, automate, automatic, automation [automat] Stemming algorithm: Porter algorithm sigma α 26
Dictionaries and tolerant retrieval sigma α
Inverted index Inverted index Posting list에대한포인터 문서빈도측정가능 Dictionaries Term vocabulary를저장하기위한데이터구조 Term vocabulary: the data sigma α 28
Hash Dictionary 를해시 (hash) 로사용 해시를이용할경우속도가매우빠름 Lookup time is constant 그러나다음과같은문제점존재 Minor variants problem: resume vs. résumé 이런경우찾을때문제발생 ( 제대로못찾음 ) No prefix search (all terms starting with automat ): 즉 automat* 과같은 wild-card 연산이불가능 이런문제점을해소할수있는방법 : 트리 (tree) sigma α 29
Tree 해시의단점 ( 즉, minor variants problem, prefix problem) 을해결 Simplest tree: binary tree Search order is O logm, M is the size of the vocabulary 그러나속도문제존재 Binary tree가균형있게구성됐다면, 빠른속도로찾을수있음 그러나편향된 tree인경우에는 vocabulary size인 O(M) 따라서 B-tree 이용 sigma α 30
Tree: Binary tree sigma α 31
Tree: B-tree sigma α 32
sigma α Scoring, Term Weighting
Problem of Boolean model Boolean model 간단한모델 : 단순히문서와질의간의일치또는불일치로검색 전문가들이사용하기에좋음 특허심사관, 특허개발자등 그러나일반유저들에게똑똑한검색을제공하지못함 Cons of Boolean model 특정정보에중점을두지않고해당하는문서를모두검색 즉, 해당질의와일치또는불일치 (1 or 0) 정보로만검색 간단한질의에는많은문서가검색됨 질의어가자세하게입력되면찾기힘듦 따라서뭐가더중요하고사용자가원하는결과인지판별하지못함 이런문제를해결하기위해 Ranking 적용 Ranked retrieval sigma α 34
Ranked retrieval 질의에대한검색시, 스코어 (score) 를적용하고우선순위에따라검색된문서를보임 Just show the top 10 results 관련된문서는가중치를높이고, 관련없는문서는가중치를낮춤 어떻게스코어를적용하는가? 질의 - 문서쌍 (query-doc pair) 을기준으로 0~1 값 scoring 질의와문서의연관성에따라 scoring 질의 - 문서유사도 Simple scoring 평소자주하는질의 scoring 문서에포함된질의 scoring We use frequency method Term frequency Document frequency sigma α 35
Term frequency 질의또는문서내에포함된같은단어들의개수 Binary incidence matrix 해당단어가문서에포함되면 1 아니면 0 sigma α 36
Term frequency 질의또는문서내에포함된같은단어들의개수 Binary incidence matrix: containing term frequency 해당단어가문서에서몇번나오는지카운트 sigma α 37
Term frequency 질의또는문서내에포함된같은단어들의개수 Using bag of words Bag of words model 여러문자열들은다양한길이와단어순서로표현됨 따라서검색에사용되는모든문자열들을하나의일관성있는모델로표현하는것이좋음 모든데이터셋에일관성있는표현을제공하기위해하나의리스트로정의 bag of words The positional index was able to distinguish these two documents. We will look at recovering positional information later in this course. sigma α 38
Term frequency tf 질의또는문서내에포함된같은단어들의개수 tf t,d : 질의와문서의 term frequency (= tf) t: term, d: document Tf는질의-문서 (query-document) 매치스코어로사용그러나 카운트가능사는아니다!! Tf=10인문서와 tf=1인문서는직관적으로같은문서 즉, tf의차이가 10배라고두문서의연관성이적은게아님 이런부분을보완하기위하여 tf에 log 적용 sigma α 39
Log frequency weighting The log frequency weight of term t in d is defined as follows w t,d = 1 + log 10 tf t,d if tf t,d > 0 0 otherwise tf t,d w t,d 0 0, 1 1, 2 1.3,, 10 2, 1000 4, etc. Score for a document-query pair Sum over terms t in both q and d tf-matching-score q, d = t q d (1 + log 10 tf t,d ) sigma α 40
Rare term vs. frequent term 단어중에는단어의횟수와상관없이중요한경우가있음 즉, 한번등장한단어이지만중요한키워드인경우 Rare term 개체명, 고유명사등은문서내단어빈도가낮음 예를들어, 한국전자통신연구원, 네이버, 강원대학교 등은문서내에서처음한번등장하고, 그이후에는대용어로표현 e.g., ARACHNOCENTRIC Frequent term 조사, 관사, 형용사등은문서내단어빈도가높음 예를들어, 아름다운, 좋은, 그, 이등, a, an, the so on. 위와같은경우, tf 때문에가중치를원하는방향대로적용하지못함 we want high weight for rare terms 따라서 해당단어가나타난문서의수 를고려 df (document frequency) Tf의희소성극복을위함 sigma α 41
Document frequency Df: 입력된질의의단어가나타난문서의수 몇개의문서가해당단어를포함하고있는지가중치계산가능 ANTHONY 의 df=3 여기서 rare term 을포함한문서의 df 는낮게나타남 Frequent term 을포함한문서의 df 는높게나타남 마찬가지로 df 희소성발생 We want Rare term: high weight, Frequent term: low weight sigma α 42
Inverse document frequency Rare term: low tf, low df Frequent term: high tf, high df 좋은성능의검색 : high weight for rare terms 따라서 df 의값을역수취함 : inverse doc-freq (idf) Df 를역수로취하면 low df high score, high df low score 가능 즉, rare term 의희소성극복가능 idf t = log 10 N df t [log 10 N/d f ] instead of [N/d f ] to dampen the effect of idf sigma α 43
Examples for idf Compute idf t using the formula: idf t = log 10 N df t Term df t idf t 박천음 1 6 사람 100 4 금요일 1,000 3 노래방 10,000 2 술 100,000 1 이 1,000,000 0 위와같이 idf 는 rare term 에대한가중치를증가시키고 frequent term 에대한가중치를감소시킬수있음 sigma α 44
Tf-idf weighting Term 에대한 tf-idf 는해당 term 의 tf 와 idf 의곱으로구함 w t,d = (1 + log tf t,d ) log 10 N df t tf, idf weight는모두 log를취함정보검색에서가장잘알려진방법 The tf-idf matching-score q, d = t q d (w t,d ) The tf-idf weight Term frequency: 문서내에서등장한가중치 Inverse doc-freq: 문서셋에서 rarity of the term에대한가중치 sigma α 45
References http://nlp.stanford.edu/ir-book/ http://cs.kangwon.ac.kr/~leeck/ir/ sigma α 46
QA 감사합니다. 박천음, 박찬민, 최재혁, 홍다솔 sigma α, 강원대학교 Email: parkce@kangwon.ac.kr sigma α 47