'Study/Information Retrieval'에 해당되는 글 21건

7.1 효율적인 점수 계산과 순위화

• 부정확한 최상위 K개 문헌 검색
• 정확한 최상위 K개 결과들의 적합성을 기대하는 사용자들의 요구를 많이 저버리지 않고, 근접한 K개 문헌을 검색하여 계산 비용을 매우 줄임
• 코사인 척도에 의한 최상위 K개 문헌들이 어떤 경우에는 질의에 대한 최상의 K개 문헌이 아닐 수도 있음
• 단지 사용자가 인식하는 적합성에 대한 한 가지 방법일 뿐
• 색인 제거 방법 -> 발견적 학습법
• 미리 설정된 임계값을 초과하는 idf를 가진 용어를 포함하는 문헌만을 고려함
• 낮은 idf 용어들의 포스팅 목록은 보통 길기 때문에 경쟁 목록에서 제외하면, 코사인을 계산하기 위한 문헌들의 수가 크게 줄어듬
• 많은 질의 용어들을 포함하는 문헌들만을 고려함
• 코사인 연산을 수행하기 전에 문헌에 많은 질의 용어가 포함되어야 하므로 K개의 후보 문헌보다 적은 문헌을 결과로 내놓을 위험성이 있음
• 최상위 목록(Champion list)
• 사전에 있는 각각의 용어 t에 대해 가장 높은 가중치를 가지는 r개 문헌들의 집합을 미리 계산하는 것 (r 값은 미리 선택되어져 있음)
• 최상위 목록은 tf-idf 가중치에서 용어 t에 대하여 가장 높은 값의 tf 값을 가지는 r개 문헌들임
• 정적 품질 점수(Static quality scores)
• 각 문헌 d에 대한 질의에 독립적인(정적인) 품질 척도 g(d)는 0과 1 사이의 값으로 나타내며, g(d) + tf-idf와 같이 이를 활용한 확장된 개념의 전체 최상위 목록(Global champion list)을 구성할 수 있음
• 이로써 High와 Low로 구분되는 포스팅 목록 구성이 가능함
• 영향 지수 정렬
• 포스팅 목록이 정적 점수와 질의 종속 점수의 부가적인 조합에 의해서 정렬된 정적 정렬을 구현하는 방법으로 정렬이 일관성을 다시 잃어 모든 문헌에 대해 정렬을 다시 수행하거나 특별한 점수 계산 함수에 의존하여 다른 정량에 의해 정렬될 수도 있음
• 문서 중심 점수 계산(Document-at-a-time scoring)
• 일반적인 점수 계산 방식으로 질의 용어에 대한 포스팅 목록들을 병행 탐색하면서 각 문헌들의 점수를 계산하는 방법
• 용어 중심 점수 계산(Term-at-a-time scoring)
• 일반적 정렬 방식에 의해 정렬되지 않아 병행 탐색이 불가능한 부정확한 최상위 K개 문헌 검색을 위한 점수 계산 방법
• 부정확한 최상위 K개 문헌 검색
• 용어 t의 포스팅 목록들에서 tf의 내림차순으로 문헌 d를 정렬하기 때문에 문헌들의 정렬은 포스팅 목록마다 서로 다름
• 따라서 모든 질의 용어들에 대한 포스팅 목록들을 병행 탐색하여 점수들을 계산할 수 없음
• 점수 계산이 요구되는 문헌의 수를 감소시키는 방법
• 질의 용어 t에 대한 포스팅 목록을 탐색할 때, 고정된 r개의 문헌을 보았거나, tf의 값이 임계값보다 적을 때까지의 포스팅 목록의 앞부분에 해당되는 문헌들을 고려함
• 점수를 누적할 때 질의 용어를 idf 내림차순으로 고려하므로, 최종 점수에 가장 기여하기 쉬운 질의 용어들을 먼저 고려함
• 질의 처리 시간이 적용될 수 있으며, 더 작은 idf를 가진 질의 용어가 있을때, 이전 질의 용어를 처리할 때 문헌 점수의 변화를 고려하여 계속 진행하거나 누적을 생략할 수 있음
• 군집 가지치기(Cluster pruning)
• 질의 시간에 코사인 점수들을 계산하기 위한 후보들로 군집에 있는 적은 수의 문헌들만을 고려하기 위해 사전 처리 단계가 필요함
• 선도자(Leader) 선정: 컬렉션에서 임의로 루트 N개의 문헌들을 고름
• 선도자들이 아닌 각 문헌들(Follower)에 대해 가장 가까운 선도자를 계산함
• 각 선도자를 따르는 추종자들의 기대 개수는 루트 N임
• 질의 처리 절차는 다음과 같음
• 질의 q가 주어지면 q에 가장 가까운 선도자 L을 찾으며, 이는 q에서 각 루트 N개의 선도자들까지의 코사인 유사도를 계산하는 것임
• 후보 집합 A는 추종자들이 같이 있는 L로 구성되며, 이 후보 집합에 있는 모든 문헌에 대해서 코사인 점수를 계산함
• 군집화를 위해 임의로 선택한 선도자를 사용하는 것은 처리 속도를 빠르게 하고 벡터 공간에서 문헌 벡터들의 분포를 반영하기 쉬움
• 문헌이 밀집한 벡터 공간 영역은 복수개의 선도자들이 있게 되고 좀 더 미세한 영역으로 나누어지게 됨

7.2 정보 검색 시스템의 구성 요소

• 중층 색인(Tiered index)
• 만약 K개 문헌보다 더 적은 수의 경쟁 문헌 집합 A가 생길 경우 중층 색인으로 최상위 목록을 일반화하며, 예를 들어 계층 1은 tf 임계값 20, 계층 2는 tf 임계값 10 등으로 계층 안에서 포스팅 표제어를 정렬함
• 질의 용어 근접성
• 질의 용어들 대부분 또는 모두가 서로 가깝게 나타나는 경우 문헌이 질의 의도에 맞는 문장을 가지고 있다는 증거이기 때문에 w라는 윈도우 폭(윈도우 내 단어 수)으로 근접성을 측정할 수 있음
• Boolean 검색(Boolean retrieval)
• 사용자가 용어들 사이의 상대적인 순서와 상관없이 키워드의 특정 조합의 유무를 통해 문헌 선택을 위한 수식을 명기할 것을 요구함
• 반면 백터 공간 질의는 기본적으로 문헌에 용어가 많으면 문헌의 점수를 더해 가는 증거 누적(Evidence accumulation) 형태임
• 와일드카드 질의
• 와일드카드와 벡터 공간 질의는 포스팅과 사전을 사용하여 구현할 수 있는 다른 색인이 필요함
• 이는 와일드카드가 벡터 공간에 복수의 용어를 생산하는 것으로 해석할 수 있으며, 이 용어들은 질의 백터에 포함
• 구절 질의
• 구절 질의 시 벡터로의 문헌 표현은 상당히 많은 손실을 초래함
• 구절에 대한 각 용어쌍을 하나의 용어로 다루어 벡터 공간에서 하나의 축으로 사상을 시켜도, 각 축(단어)에 대한 가중치는 독립적이지 않음
• 예를 들어 German shepherd 구절은 german shepherd 축으로 사상되지만 german 축과 shepherd 축에서 0이 아닌 가중치를 가지게 되어 손실을 초래함
• 따라서 구절에 대해 각 용어의 가중치가 높은 문헌을 찾기 위해 벡터 공간 검색을 사용할 수 있으며, 구절 검색은 단순히 문헌에 해당 구절이 존재하는 지를 알려줌
• 색인과 검색 알고리즘 관점에서 서로 다르게 구현되어야 할지라도 때때로 서로 유용하게 결합되어 질의 처리가 수행될 수 있음