Information Retrieval (정보 검색)

Outline

• Relevance Ranking Using Terms
• Relevance Using Hyperlinks
• Synonyms., Homonyms, and Ontologies
• Indexing of Documents

Information Retrieval (IR)

database system보다 단순한 data model을 사용

• 문서들의 모음으로 구성된 정보
• 문서는 구조화되지 않았으며 schema가 없음

IR은 키워드 또는 예제 문서와 같은 사용자 입력을 기반으로 관련 문서를 찾습니다

이미지처럼 텍스트가 아닌 데이터와 함께 제공되는 텍스트 설명에서도 사용할 수 있습니다
웹 검색 엔진은 IR 시스템의 가장 친숙한 예

 

Database system과의 차이점

• IR system은 transactional update, concurrency control, recovery를 하지 않음 
• DB는 structured data와 data organization에 의해 정의된 schema를 다룬다
• IR system은 일반적으로 데이터베이스 시스템에 의해 처리되지 않는 쿼리 문제를 처리
  • 키워드별 근사 검색
  • 관련 정도를 기준으로 검색된 답변의 순위 

---

Keyword Search

전체 텍스트(full text) 검색에서 각 문서의 모든 단어는 keyword로 간주됩니다.
(문서에 있는 단어들을 지칭할 때 그 단어를 사용)

 

IR system은 일반적으로 keyword와 논리적 연결을 사용하여 형성된 쿼리 식을 허용하거나 그렇지 않을 수 있습니다.
(Ands는 적지 않아도 알아서 인식됨)

 

질의에 대한 추정된 관련성에 기초하여 문서의 순위를 매기는 것이 중요

관련성 순위(Relevance Ranking)는 다음과 같은 요인을 기반으로 한다.

• Term Frequency : 문서에서 query keyword 발생 빈도
• Inverse document frequency: query keryword가 발생한 문서 수 - 적을 수록 해당 keyword의 중요도가 높아짐
• Hyperlinks to documents : 문서에 대한 링크가 많을 수록 그 문서는 중요해짐

Relevance Ranking Using Terms

TF-IDF ranking

Term frequency/Inverse Document frequency

https://wikidocs.net/31698

단어의 빈도와 역 문서 빈도(문서의 빈도에 특정 식을 취함)를 사용하여

문서 내의 각 단어들마다 중요한 정도를 가중치로 주는 방법

 

n(d) = document d 속 terms의 수

n(d,t) = document d 속 temr t의 출현 횟수

 

relevance of a document d to a term t는

log를 씌워서 빈번한 용어의 과도한 weight을 피함

 

query Q에 대한 document의 relevance는

 

대부분의 시스템이 위의 모델에 추가됨

• 제목, 작성자 목록, 섹션 제목 등에 나타나는 단어가 더 중요해집니다.
• 문서에서 처음 나타나는 단어가 늦게 나타나는 경우 중요도가 낮아집니다.
• stop words : "a", "an", "the", "it" 등과 같은 매우 일반적인 단어들은 제거된다.
• Proximity :  쿼리의 키워드가 문서에서 서로 가깝게 나타나는 경우, 문서의 중요도는 멀리 떨어져 있는 경우보다 높습니다.

문서가 관련 점수의 내림차순으로 반환됩니다.
(일반적으로 모든 문서는 반환되지 않고 상위 몇 개의 문서만 반환됩니다.)

 

 

Similarity Based Retrieval

유사성 기반 검색 - 주어진 문서와 유사한 문서를 검색합니다.

유사성은 공통어(common words)를 기초로 정의될 수 있다.

ex) TF (d, t ) / n (t )가 가장 높은 A에서 k개의 용어를 찾아 다른 문서의 관련성을 찾는 데 사용합니다.

 

Relevance Feedback: 유사성을 사용하여 답변 집합을 keyword query로 세분화할 수 있습니다
• 사용자는 keyword query로 검색된 문서에서 몇 개의 관련 문서를 선택하고, 시스템은 이와 유사한 다른 문서를 찾습니다

 

Vector space model: n차원 공간을 정의합니다

여기서 n은 document set 내 단어 수입니다
• 문서 d에 대한 벡터는 원점에서 i번째 좌표가 TF (d,t ) / n (t )인 점까지 이동한다
• 두 문서의 벡터 사이의 각도의 cosine은 유사성의 척도로 사용된다

 

 

Relevance Using Hyperlinks

용어 빈도만 고려할 경우 쿼리와 관련된 문서 수가 엄청날 수 있습니다.

 

용어 빈도를 사용하면 "spamming"이 쉬워집니다.

 ex) 여행사는 "여행"이라는 단어를 웹페이지에 많이 추가하여 순위를 높일 수 있다

 

<유명한 사이트의 페이지를 찾기>

아이디어: 웹 사이트의 인기(예: 방문하는 사용자 수)를 사용하여 주어진 키워드와 일치하는 사이트 페이지의 순위를 매깁니다

문제점: 사이트의 실제 인기를 찾기 어렵습니다
솔루션: 사이트의 인기 또는 명성을 측정하기 위해 사이트에 대한 하이퍼링크 수를 사용

• 각 사이트에서 하이퍼링크를 하나만 카운트합니다
• popularity measure는 개별 페이지가 아닌 사이트 단위로 합니다
  • 그러나 대부분의 하이퍼링크는 site의 root입니다
  • 또한 cs.yale.edu과 같은 URL 접두사에는 다양한 인기의 관련 없는 페이지가 많이 포함되어 있기 때문에
  • (사실 "사이트"의 개념은 정의하기 어렵습니다)

개선사항

사이트에 대한 링크에 기반하여 prestigence를 계산할 때,

자신이 더 높은 prestigence를 가진 사이트의 링크에 더 비중을 둡니다

• prestige definition는 순환(circular)입니다
• 동시 선형 방정식의 시스템 (system of simultaneous linear equation) 설정 및 해결

위의 아이디어는 Google PageRank 순위 매커니즘의 기초입니다

 

 

<사람들의 명성에 순위를 매기는 소셜 네트워킹 이론과의 연결>

• 예를 들어, 미국 대통령은 아는 사람이 많아서 위신이 높다
• 이들은 다른 사람들도 알고 있을 정도로 prestigence도 높다

<Hub 및 authority 기반 순위>

• Hub : 주제에 대한 여러 페이지에 대한 연결을 저장하는 페이지
• authority : 주제에 대한 실제 정보를 포함하는 페이지
• 각 페이지는 그것이 가리키는 authorities의 prestige에 근거하여 hub prestige을 얻는다.
• 각 페이지는 그것이 가리키는 hub prestige을 바탕으로 authority prestige를 얻는다.
• 다시 말하지만, prestige definition는 cyclic이고, linear equation을 풀어서 얻을 수 있다.
• 쿼리에 대한 답변 순위를 매길 때 authority prestige 사용

https://ltvw.tistory.com/entry/%ED%97%88%EB%B8%8C-%EC%98%A4%EC%8F%98%EB%A6%AC%ED%8B%B0Hubs-and-Authorities-%EB%AA%A8%EB%8D%B8%EA%B3%BC-HITS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EB%93%AC

허브-오쏘리티(Hubs and Authorities) 모델과 HITS 알고리듬

---

Synonyms and Homonyms

Synonyms (동의어)

ex)  문서: "모터사이클 수리", 쿼리: "모터사이클 유지보수"
- "유지 보수"와 "수리"는 동의어임을 인식해야 함

- 시스템에서 쿼리를 "모터사이클 및 (수리 또는 유지 관리)"로 확장할 수 있습니다

 

Homonyms (동음이의어)

ex) "목적어"는 명사/동사로서 다른 의미를 갖는다
문맥에서 의미를 어느 정도 명확히 할 수 있다

 

'동음이의어'는 '소리는 같으나 뜻이 다른 단어'를 의미하고

'동의어'는 '뜻이 같은 말'을 의미합니다

 

synonyms를 사용하여 쿼리를 자동으로 확장하는 것은 문제가 될 수 있다

• 동의어를 추론하기 위해 의도된 의미를 이해할 필요가 있다
• 또는 사용자에게 동의어에 대해 확인할 필요가 있다
• 동의어는 다른 의미도 가질 수 있다

 

Concept-Based Querying

접근법

• 각 단어에 대해 문맥에서 나타내는 concept을 결정합니다
• 하나 이상의 ontologies 사용:
  • 개념 간의 관계를 보여주는 계층 구조
  • ex) E-R 모델에서 본 ISA 관계

이 접근법은 특정 분야의 용어를 표준화하는 데 사용될 수 있다

• ontologies는 여러 언어를 연결할 수 있습니다
• Semantic Web의 기초(여기에서는 다루지 않음)

 

Indexing of Documents

각 키워드 Ki를, 키워드를 포함하는 문서 집합 Si로

inverted index로 매핑합니다.
(document는 식별자로 식별된다)

Inverted index는 기록될 수 있습니다.
• 근접성 기반 순위(proximity based ranking)를 허용하기 위해 문서 내에 keyword를 위치시킴
• TF를 계산용 keyword의 발생 횟수

and 연산자: K1, K2 ..., Kn이 모두 포함된 문서를 찾습니다.

or 연산자 : K1, K2 , …, Kn 중 하나 이상을 포함하는 문서

각 Si는 병합을 통해 효율적인 교차/합집합이 가능하도록 정렬됩니다.
• 정렬된 목록을 병합하여 "not"을 효율적으로 구현할 수도 있습니다.

 

// 결정 커버리지는 만족했는데 조건(condition) 커버리지는 만족하지못함 케이스 32분

// mcdc는 맨 마지막 1부터 출발