Ranking Relevance in Yahoo Search, kdd2016

참고문서: Dawei Yin et al., Ranking Relevance in Yahoo Search, kdd2016 

  • 2016년 논문으로 오래된 논문이지만, 검색에 대해 잘 정리한 논문 
논문의 contribution
  • core ranking과 contextual reranking을 위한 learning to rank 알고리즘 
    • core ranking은 (질의, 문서)를 기반으로 적합성 판단 
    • contextual reranking은 (질의, 문서들)을 기반으로 적합성 판단. 즉, 하나 이상의 검색된 문서들을 함께 이용해서 문서의 적합성 판단 
  • click similarity, deep semantic matching, translated text matching과 같은 semantic matching features 
  • query rewriting 방법
  • recency sensitive ranking과 location sensitive ranking 

Background 

Overview of Architecture 

  • first step: 단어 매칭을 이용해서 문서 검색. 빠른 검색이 가능 
    • 논문에서는 'recall' 단계로 부름 
  • second step: first step에서 검색된 문서들을 대상으로, query dependent 자질을 이용해서 (질의, 문서) 쌍의 점수 계산 
    • 논문에서는 core ranking 이라고 부름 
  • second step을 위해서는 학습데이터가 필요함. 
    • 학습 데이터 구축에는 비용이 많이 드는데, 논문에서는 active learning 방법을 언급함 

Ranking Features (검색 자질. second step을 위한 자질들) 

  • Web graph 
    • 웹에서 문서간의 연결 정보를 이용해서, 문서의 quality 혹은 popularity 측정 
  • Document statistics 
    • 문서에 있는 단어 통계 정보 
  • Document classifier
    • spam, adult, language, main topic, quality, type of page (e.g., navigational destination vs informational) 등의 문서 분류 정보 
  • Query Features
    • number of terms, frequency of the query and of its terms, click-through rate of the query 등의 질의 정보 
  • Text match
    • (질의, 문서)간의 텍스트 매칭 정보. 문서의 어느 부분과 매칭되는지, 매칭시에 점수(bm25, 매칭텀 개수)를 어떻게 할 것인 지, 매칭된 단어들이 얼마나 인접해 있는지 등. 
  • Topical matching
    • 단어 단위의 유사도가 아닌 topic 단위의 유사도 
  • Click
    • probability of click, first click, last click, long dwell time click or only click 등의 정보 
  • Time 
    • For time-sensitive queries, the freshness of a page is important

Machine Learned Ranking 

  • 웹검색에는 다수의 비적합 문서들이 있음. gradient boosting tree (GBDT) 모델이 적합 / 비적합 문서 분류를 잘해서, 이 모델을 이용함 
  • 검색의 두번째 단계인 core-ranking 단계에서 비적합 문서들을 걸려냄 
  • 검색의 세번째 단계인 contextual-reranking 단계에서 적합 문서들의 순위를 정함 
    • contextual-reranking은 이 논문에서 제안한 거 같음.  

Core Ranking 

  • LogisticRank
    • core ranking을 위해서 논문에서 제안한 방법 
    • GDBT를 이용해서 적합/비적합을 분류하면서, 동시에 적합 문서에서 perfect 는 가장 큰 값이 나오도록 하고, excellent는 그 다음, good은 그 다음 값이 나오도록 모델 학습함  
      • 수식 1을 통해서 적합 / 비적합 분류를 함. log likelihood loss 이용 
      • 수식 3을 통해서 pseudo response 값을 계산함. 
      • 논문에서는 pseudo-response를 scale(label)을 곱하는 것으로 변경해서 사용함 ('pseudo_response(x)' 수식 참조)  
      • perfect는 3, excellent는 2, good은 1의 가중치(=수식에서 scale(label)임 ) 부여함 
      • 가중치를 통해서 pseudo response가 더 커지도록 만듬.  
      • pseudo response 값을 크게 함으로써, ranking 이 가능하도록 함. 즉, perfect는 더 큰 점수를 받도록 모델을 학습함  
    • 학습데이터: 약 2백만개의 질의-url 쌍. 
      • active learning과 수동 레이블링으로 구축 
  • 기존 방법인 GBRank, LambdaMart와 비교했을 때 더 좋은 결과를 보임 : 테이블 1  
    • 논문 저자들이 구축한 평가 데이터에서의 실험 결과: 

  • Learning to rank challenge로 공개된(?) 데이터셋에서는 logisticRank가 다른 모델보다 결과가 좋지 않음. 
    • 저자들의 의견
      • 이 공개된 데이터에는 bad인 비적합 문서가 27%로, real 환경에 비해서 적음 
        • real 환경에서는 bad인 비적합 문서가 99% 이상임 
      • 본인들이 구축한 평가데이터에는 비적합 문서가 훨씬 많다는 의미인듯. (real 환경과 유사한 분포로 데이터를 만들었을 듯) 
      • LogisticRank는 비적합 문서를 잘 분류할 수 있도록 되어 있는데, 비적합 문서가 적어서 이런 장점이 잘 나타나지 않은 것으로 언급함 

Contextual Reranking 

  • core ranker로 검색된 문서들 중에서 상위 30개의 문서를 대상으로 contextual reranking 수행 
  • contextual features 
    • rank : core ranker의 순위일 듯 
    • mean : 30개 문서들의 자질값의 평균 
    • variance : 30개 문서들의 자질값의 분산 
    • normalized feature : 30개 문서들의 자질값에 대해 평균과 표준편차로 정규화한 값 
    • topic model feature : 30개 문서들로 토픽 분포를 합쳐서 질의 토픽 모델 벡터를 만들고, 이를 이용해서 각 문서와의 유사도 계산 
  • 학습 데이터 관련. 
    • contextual reranking을 위해서 질의별 상위 30개 문서를 모두 레이블링 하는 듯. 
    • core ranking을 위해서는 질의별로 문서를 샘플링하는거 같음. 
    • 다음과 같은 문구가 있음.  
      • Beside contextual features, another advantage of reranking is that the training data for this phase is less prone to sample selection bias, since it is possible to label a complete set of candidate documents for a given query
  • contextual reranking에서 어떤 모델을 사용하는지 언급이 없음. GBDT일 듯. 

Semantic Matching Features 

Click Similarity (CS) 

  • click similarity: 
    • click log를 이용해서 질의 벡터와 문서 벡터를 생성하고, 
    • 이를 기반으로 질의와 문서간의 유사도 계산 
    • 실험 결과, 검색 품질 향상에 가장 기여도가 큰 자질임 
  • click graph를 이용해서 질의 벡터와 문서 벡터를 생성함 
    • click graph: 질의와 문서간의 bipartite graph. 질의로 검색 후에 클릭한 문서와 연결되어 있고, edge에는 클릭 빈도 정보가 있음. (그림 1) 
  • 질의 벡터와 문서 벡터 생성 단계  
    • 질의 벡터를 질의를 구성하는 텀이 질의에 나타난 빈도로 표기함 
    • 문서 벡터는 클릭에 사용된 질의 벡터들을 가져와서 생성함. 클릭 빈도를 가중치로 해서 질의 벡터들의 weighted sum 임. 크기가 1로 되도록 정규화함 (수식 4) 
    • 질의 벡터를 클릭한 문서 벡터들로 다시 생성함. 클릭 빈도를 가중치로 해서 문서 벡터들의 weighted sum 임. 크기로 1이 되도록 정규화함 (수식 5) 
    • 위 과정을 반복함. 적절히 수렴할 때까지. 
  • 질의 벡터, 문서 벡터 생성시에.. 
    • iteration 을 진행할수록 벡터내의 0 아닌 값이 많아지는데, 이 경우 처리 속도 이슈가 있음. 
    • 그래서 벡터내의 0 아닌 값을 상위 k개로 한정함. 
    • 저장 공간을 줄이기 위해서 quantization 후의 벡터를 저장함. 



Translated Text Matching (TTM) 

  • 기계 번역 모델을 이용해서, 질의를 문서 제목으로 변환한 후, 변환으로 얻은 텍스트와 문서 제목간의 유사도 계산 
  • 기계 번역 모델 
    • 학습 데이터: 질의와 클릭한 문서의 제목 쌍을 학습데이터 사용. 즉, 질의를 클릭한 문서 제목으로 번역되도록 하는 번역 모델을 만듬 
  • 질의당 k개의 번역 결과를 생성함. 
  • 질의와 문서간의 유사도 점수는 k개의 번역 결과와 문서간의 유사도 점수를 기반으로 함. 
    • 유사도 점수의 최대값, 평균, 중간값 등을 자질로 사용함 
  • 기여도가 높은 자질
    • EXT_Q_TLM : rewritten queries 와 문서 제목간의 maximum cosine similarity 
      • rewritten query는 질의를 문서 제목으로 변환하는 번역 모델로 생성함. (번역 모델을 여러개 만들어서 사용하는 듯) 
      • 질의와 문서 제목간의 cosine similarity를 어떻게 계산하는지는 설명이 없음. 
      • 자질중 7번째로 검색 기여도가 높은 자질
    • AGG_Q_TLM : rewritten queries 와 문서 제목의 rewritten titles 간의 cosine similarity 기반으로 만든 자질값. 
      • rewritten query는 질의를 문서 제목으로 변환하는 번역 모델로 생성함.
      • rewritten title은 문서 제목을 질의로 변환하는 번역 모델로 생성함. 
      • 하나 이상의 cosine similarity 가 나올텐데, 이를 어떻게 하나의 자질로 만들었는지, 혹은 모든 cosine similarity를 다 사용하는지에 대한 설명은 없음. 
      • 자질중 10번째로 검색 기여도가 높은 자질

Deep Semantic Matching (DSM)

  • DSSM 을 사용함 
    • 네트워크를 통해서 질의 임베딩과 문서 임베딩을 각각 생성하고, 질의 임베딩과 문서 임베딩간의 inner product로 유사도 계산 
  • 학습 데이터 
    • 10-slot window를 이용한다고 함. 
    • 10-slot window에서 1등을 positive로 사용하고, 나머지를 negative로 사용
    • (아마도) 야후 검색 결과를 1등에서부터 sliding 하면서 10개씩 가져오고, 10개 중 첫번째 문서는 positive로 사용하고, 나머지는 negative로 간주하는 듯. 
    • 30억건의 (질의, 10건의 문서) 데이터를 구축함 
  • 문서 제목과 문서 url의 domain name을 이용함
  • 자질중 8번째로 검색 기여도가 높은 자질 

CS, TTM, DSM 실험 결과 (테이블 3) 

  • base는 LogisticRank와 기본 자질을 사용한 것임 
    • contextual reranking은 사용하지 않음. 
  • torso, tail에서 CS의 기여도가 눈에 띄고 높음  
    • torso, tail 의 경우, 클릭 정보가 없을 텐데 CS가 기여를 많이함 (의외인듯) 
    • 저빈도 클릭 정보라도 이용하는 것이 좋은 것인지.  
  • TTM과 DSM은 비슷하게 기여하는 듯. 


Query Rewriting (QR) 

  • 검색의 첫번째 단계에서 적합 문서들을 더 검색하기 위한 용도 
  • term matching 시의 이슈 사항 예시: 첫번째 단계에서 해당 문서 검색이 안됨 
    • 질의: how much tesla 
    • 문서 표현: price tesla 
  • query rewriting 방법 : 질의를 문서 제목으로 변환하는 번역 모델을 만들어서 사용  
    • 학습 데이터: 질의와 클릭한 문서의 제목 쌍을 학습데이터 사용. 즉, 질의를 클릭한 문서 제목으로 번역되도록 하는 번역 모델을 만듬
  • ranking strategy 
    • QRW: 원질의와 qr 질의를 함께 이용 
      • 동일 문서가 원질의로도 검색되고 qr 질의로도 검색되면, 둘중 높은 점수를 이용함 
    • QRW-RE: 원질의는 사용하지 않고, qr 질의만 사용
  • 실험 결과: (테이블 4) 
    • QRW가 QRW-RE보다 더 좋음. 
    • query rewriting을 하면 대부분의 질의와 지표에서 결과가 좋아짐 
    • tail 질의에서 품질 향상이 큼. 

Comprehensive Experiments 

  • 평가 데이터
    • 1년치 야후 검색 로그에서 2천개 질의를 추출
    • 야후 검색 결과를 수동으로 레이블링해서 사용 
    • 질의당 몇개의 문서를 레이블링 했는지와, top / torso / tail 질의 개수는 언급되어 있지 않은 듯. 
  • 평가 모델 
    • base : logisticRank와 기본 자질을 이용하는 모델 
    • base+feat : base 모델에 3개의 semantic matching feature(CS, TTM, DSM)를 추가 이용 
    • base+all : base + feat 모델에 제안하는 랭킹 functions, query rewriting을 추가 이용 
      • 제안하는 ranking fuctions에 contextual reranking이 포함되려나? 
  • 평가 결과 


Location Sensitive Ranking 

  • location-sensitive query: 지역과 관련된 질의
  • explicit local queries : 질의에 명확하게 지역이 언급되어 있는 질의 (예: 보스톤에 있는  식당)
  • implicit local queries : 질의에 지역이 언급되지는 않았지만 지역 관련 질의 (예: 식당) 
  • 접근 방법 
    • 지역 기반 정보를 랭커 자질로 사용하지는 않음. 이렇게 하면 적합성 관련 더 주요한 자질들에 의해서 지역 관련 자질의 기여도가 낮을 수 있음. 
    • 대신, 지역 관련 정보를 별도로 처리함. (수식 7) 
      • f는 (질의, 문서) 적합성 정도를 나타냄 
      • d는 (질의, 문서)간의 거리 정보를 나타냄 
  • 질의와 문서간의 거리 정보를 계산하는 방법 : 수식 7에서 d hat 값을 계산하는 방법 
    • 질의의 지역 정보: 
      • explicit local query에서는 질의에 언급된 지역정보를 이용함  
      • implicit local query에서는 사용자의 위치 정보를 이용함 
    • 문서의 지역 정보
      • 문서를 클릭한 질의의 지역 정보를 이용함 
      • 하나 이상의 지역 정보가 있으면, 이들을 모두 이용함 


댓글

댓글 쓰기

이 블로그의 인기 게시물

utf-8과 utf8

utf-8과 utf8을 차이 없이 사용했다. utf8이 더 짧아서, 이걸 선호했는데.. 표준은 utf-8이라고 한다. ( UTF-8 vs. UTF8 참조) utf8을 지원하지 않는 경우가 있다.  utf8 때문에 고생한게.. ajax가 IE에서 동작하지 않아서이다. ajax에서는 prototype.js를 사용했다. 동일한 코드가 다른 서버에서는 IE로 잘 보이는데, 해당 서버에서는 IE로 실행이 안 되었다. 크롬, 불여우에는 서버 상관없이 잘 실행되었다.. 원인은 아파치 혹은 php 설정 차이일텐데.. 이걸 찾기 위해서 구글링과 두 장비간의 설정 파일 비교를 수행해서 간신히 찾았는데.. 그게 바로 utf8 문제였다. 아마도 크롬, 불여우에서는 utf-8과 utf8을 동일하게 취급하는 거 같고, IE에서는 utf8은 잘못된 것으로 판단하는 거 같다. ****************************** php.ini 파일에서 default_charset을 다음과 같이 설정해둔게 문제였다. default_charset = "utf8" 이를 다음과 같이 변경하니 문제가 해결되었다. default_charset = "utf-8"  ****************************** utf8을 사용하는 경우는 "-" 사용시에 문제가 되는 언어에서 사용한다고 한다. ( UTF8 or UTF-8? 참조) 비슷한 문제가 Ajax not working in IE at Apache server 에도 있었다. 여기에서는 iso-88 5 9-1을 iso-88 6 9-1로 잘못 기재해서 생긴 문제였다고 한다.
자세한 내용 보기