본문 바로가기

검색 엔진

[박혜웅] 랭킹 모델(ranking model)

  • ranking (순위부여)의 필요성

    • natural language query에 의한 결과를 평가하기 위하여, ranking이 필요하다.

      • 일반사용자는 boolean query 보다 natural language query를 선호한다.

        • boolean system 은 훈련이 없는 일반 사용자에 복잡한 boolean query를 요구한다.
        • natural language query는 데이타에 없는 용어나 잘못된 철자에도 임의의 결과를 얻을 수 있다.

          • 검색어의 일부분만 일치하여도 일부의 문서는 검색할 수 있으므로

 

  • 순위부여 모델의 특징

    • 근접(인접)연산, 필드제한이 필요없다.

      • 추가적인 위치정보(필드위치, 단어위치)를 저장할 필요가 없다.
    • 불용어목록을 줄일 수 있다.

      • 컴퓨터분야에 대한 문헌에서 "컴퓨터"를 불용어로 지정할 필요가 없다.

 

  • 순위부여 기본 개념

    • term vector

      • 전체 문서집합안에 n개의 색인어(term)가 존재할 때, (t1, t2, ..... tn)처럼 vector로 표현할 수 있다.
      • 각 색인어가 문서 또는 질의에 존재 여부에 따라 이 vector에서 1,0 으로 표시할 수 있다.
      • query vector : query에 대한 term vector
      • document vector: document에 대한 term vector
    • ranking

      • rankinig은 query vector * document vector 의 값을 내림차순으로 정렬하는 것.
      • 단, query vector, document vector 에 아래 요소를 이용하여, 가중치를 부여할 수 있다. 

        • TF, IDF가 높을 수록 가중치가 높다.
        • xx.png 
        • TF= term frequency (문헌내 빈도수)

          • TF의 예: 
          • 많이 출현한 용어일 수록 TF가 높다.
          • TF는 그 문헌에서 가장많이 출현한 용어의 출현 빈도수가 작을수록 높다. (정규화를 위한 옵션)
          • TF는 용어 KIi의 빈도수가 높을수록 높다.
        • IDF= inverted document frequency (역 문헌 빈도수)

          • IDF의 예:
          • 흔하지 않은 용어일 수록 IDF가 높다.

            • IDF는 전체문헌의 수가 많을 수록 높다. (정규화를 위한 옵션)
            • IDF는 용어의 출현 빈도수가 작을 수록 높다.
        • user-specified term weight

          • 사용자가 임의로 정한 가중치
    • ranking 의 예

 

 

  • 순위부여 모델

    • 순위부여에서 유사도에 평가의 필요성에 대해 주장한 Luhn, 1957

      •  "두 개 이상의 정보표현(문헌과 질의)이 주어진 원소(색인어)와 분포(색인어의 분포)면에서 서로 일치한다면,  그것들은(문헌과 질의) 유사한 정보를 표현할 확률이 더욱 높다."

    • 벡터와 가중치를 이용한 유사도계산 방법

      1.  

      2. 모델에 따라 가중치 계산을 다르게 함.
    • 순위부여 모델의 종류

      • 각 문헌에 대한 질의에 순위 부여

      • 관련있는 문헌 집합 전체에 대한 질의에 순위부여

        • 클러스터링 모델
        • 퍼지 모델
      • 직접 비교

        • Spark Jones: 수작업으로 색인어 추출
        • McGill: 제어색인(수작업), 비제어색인(자동)을 모두 이용
        • Harman: "잡음" 측정법이용하여 용어집중도 파악

          • 잡음: 검색에 사용할 만한 용어가 아닌 중요하지 않은 단어
      • 문헌구조에 따라 순위부여

        • Bernstein: 용어가 있는 구조적 위치에 따라 가중치 부여
      • 문헌내부구조에 따라 순위부여

        • 잠재 의미색인(semantic indexing) 이용
        • 성능은 우수하지만, 속도의 문제가 있음

 

  • 순위부여 기법 선정 가이드

    • IDF, 잡음, 엔트로피를 이용하면 성능이 향상된다.

      • 즉, 장서내의 용어 분포를 바탕으로 하는 용어 가중치를 이용하면, 성능이 향상된다.

    • TF를 이용하여도 항상 성능이 향상되는 것은 아니다.

      • TF 에 대한 정규화 필요성 (TF 이용시 위험성)

        • 높은 문헌내 빈도수의 영향 완화

          • 같은 문헌에서 20번 나타나는 용어가 1번 나타나는 용어보다 20배 중요한 것은 아니다.
        • 문헌 길이에 대한 효과 고려

          • 매우 짧은 문헌에게 불리한 환경
        • 장서의 종류에 따른 특성 고려

          • 문헌내 빈도수의 효과가 작은 장서도 있다.
    • TF와 IDF를 조합하여 여러가지 방법을 사용할 수 있다.

      • 정규화의 2가지 방식

        • 코사인(cosine) 정규화: 출현빈도를 정규화하는데 사용
        • 최대(max) 정규화: 다중 주제에 대한 검색시 유용
    • 문헌구조에 따라 추가적인 가중치를 부여하는 것은 유용하다.

      • 제목, 요약문에 나오는 용어에 높은 가중치를 부여한다.
    • 초기 검색 이후에 연관 가중치를 사용하는 것은 효과적이다.

 

  • 순위부여 모델의 역파일

    •  사전(렉시콘)에 가중치 정보를 저장하는 경우

      • 용어가중치 계산을 탐색루틴에서 해야하므로 오버헤드 발생 (???)
      • 가중치 관련정보 = 역문헌 빈도수
      •  

    • 포스팅 파일에 가중치 정보를 저장하는 경우 (저장하는 정보에 따른 분류)

      •  
      • 저장하지 않음

        • 모든 처리를 탐색 루틴에서 한다.
      • 원빈도수 저장

        • 탐색은 느리다.
        • 가장 유연한다.

          • 색인을 바꾸지 않고 용어 가중치 알고리즘을 변경할 수 있다.
      • 정규화된 빈도수 저장

        • 갱신시 포스팅파일을 바꿀 필요가 없다.
        • 원빈도수 저장보다 탐색이 빠르다.
      • 완전한 용어가중치 저장

        • 갱신할 때마다 포스팅파일을 바꿔야 한다.

          • 역문헌빈도수가 레코드가 추가될 때마다 바뀌기 때문이다.
        • 탐색시간이 가장 빠르다.
        • 연관피드백에서 이용하기 어렵다.

          • 탐색시 각 가중치를 더하기만 한다.

 

  • 순위부여 모델의 탐색 방법

    • 불리언 시스템의 역파일 탐색 과정과 비슷하나, 포스팅에서 가중치 획득하는 부분이 추가된다.
    • 문헌 식별번호를 키로 하여 레코드 가중치를 값으로 하는 해싱테이블 이용

      • 해싱테이블은 저장장치의 한 블록을 사용
    • 스템과 비스템 질의용어 조작

      • 스템,비스템을 하나의 사전에 정렬하여 저장한다.

        • 저장장치를 절약하므로, 대용량 데이타 집합에 유리
      • 스템,비스템을 2개의 사전에 정렬하여 저장한다.

        • 소용량 데이타 집합에 유리

 

  • 가지치기(전지,pruning)

    • 검색 성능에 큰 영향을 미치지 않는 선에서, 적합성(가중치)이 낮은 문서를 순위부여과정에서 제외시키는 것
    • 가지치기 방법

      • 불용어를 제거
      • 역문헌빈도수가 낮은 용어와 관련된 문서 제거

        • 가중치를 합산하는 과정에서, 역문헌빈도수가 작고 가중치가 0인 누산기에는 가중치를 추가하지 않는다.

 

  • 순위부여 관련 주제

    • 연관(적합성) 피드백

      • 연관피드백을 이용하여 검색성능 향상 가능
    • 클러스터링

      • 같은 문헌을 클러스터링하여, 순위 부여하는 회수를 줄임
    • 불리언 모델(시스템)

      • 불리언 모델과 순위부여 모델의 통합 시도
    • 요약파일

      • 역파일 대신 요약파일을 사용하여 처리속도 향상
    • 제약에 대한 처리

      • 특정 문구 포함, 불리언 연산자, 인접 연산자
      • 2단계로 처리됨 (제약을 처리하는 단계가 추가됨)