[Coursera] Text Retrieval and Search Engines (MODULE 6)

수업에서 제시하는 Guiding Questions에 따라 이번 수업 내용을 설명하고자 한다.

 

Guiding Questions

Develop your answers to the following guiding questions while completing the readings and working on assignments throughout the week.

• What is relevance feedback? What is pseudo-relevance feedback? What is implicit feedback?
• How does Rocchio work? Why do we need to ensure that the original query terms have sufficiently large weights in feedback?
• What is the KL-divergence retrieval function? How is it related to the query likelihood retrieval function?
• What is the basic idea of the two-component mixture model for feedback?
• What are some of the general challenges in building a web search engine?
• What is a crawler? How can we implement a simple crawler?
• What is focused crawling? What is incremental crawling?
• What kind of pages should have a higher priority for recrawling in incremental crawling?
• What can we do if the inverted index doesn’t fit in any single machine?
• What’s the basic idea of the Google File System (GFS)?
• How does MapReduce work? What are the two key functions that a programmer needs to implement when programming with a MapReduce framework?
• How can we use MapReduce to build an inverted index in parallel?
• What is anchor text? Why is it useful for improving search accuracy?
• What is a hub page? What is an authority page?
• What kind of web pages tend to receive high scores from PageRank?
• How can we interpret PageRank from the perspective of a random surfer “walking” on the Web?
• How exactly do you compute PageRank scores?
• How does the HITS algorithm work?

 

Answers

1. What is relevance feedback? What is pseudo-relevance feedback? What is implicit feedback?
   • relevance feedback: 검색 엔진에 쿼리를 입력했을 때 나온 각 문서를 사용자가 관련성이 있는 문서인지 개별 판단
   • pseudo-relevance feedback: 검색 엔진에 쿼리를 입력했을 때 나온 top-k개의 문서를 관련성 있는 문서라고 가정
   • implicit feedback: 사용자가 검색 엔진을 사용하면서 클릭한 문서를 관련성 있는 문서라고 가정
     
     
2. How does Rocchio work? Why do we need to ensure that the original query terms have sufficiently large weights in feedback?
   • new query = (original query * alpha) + (rel docs * beta) - (non-rel docs * gamma)
   • 즉, 쿼리의 벡터 공간을 관련 문서와 가깝게 관련되지 않은 문서와 멀게 배치한다.
   • 이때, 특정 피드백 문서에 과적합 되는 것을 막기 위해 original query에 충분한 가중치(alpha)를 두어야 한다.
     
     
3. What is the KL-divergence retrieval function? How is it related to the query likelihood retrieval function?
   • Rocchio 피드백이 벡터 공간 모델에 적합하다면 KL-divergence retrieval function은 언어 모델에 적합하다.
   • KL-divergence retrieval function은 query likelihood retrieval function의 일반화된 모델이다.
   • KL-divergence retrieval function을 활용한 피드백은 Rocchio feedback과 유사하다.
     
     • 쿼리 확률 분포와 문서 확률 분포 간의 KL-divergence를 계산한다.
     • KL-divergence 결과를 통해 관련 문서를 추출한다.
     • new query distribution = ((1 - alpha) * query distribution) + (alpha * rel docs)
       
       
4. What is the basic idea of the two-component mixture model for feedback?
   • 관련 문서에는 당연하게도 "the"와 같은 common words가 들어가 있다.
   • 우리는 언어 모델이 common words에 높은 가중치를 주는 것을 원하지 않는다.
   • 따라서 Background words와 Topic words로 구성된 Mixture Model을 구성한다.
   • Mixture Model = $\lambda P(w|C) + (1-\lambda) P(w|\theta)$
   • 람다가 충분히 크다면 해당 모델은 Background words model에 등장하기 힘든 희귀한 단어에 큰 가중치를 주게 된다.
     
     
5. What are some of the general challenges in building a web search engine?
   • 확장성(Scalability): 웹 규모는 방대하다. 
   • 웹의 역학(Dynamics of the Web): 새로운 페이지가 계속해서 생기고 기존 페이지도 수시로 업데이트된다.
   • 낮은 질의 정보(Low Quality Information): 스팸과 같이 정보가가 없는 웹 사이트도 있다.
     
     
6. What is a crawler? How can we implement a simple crawler?
   • 크롤러(crawler)란 자동으로 웹을 탐색하며 정보를 수집하는 로봇을 의미한다.
   • 간단한 크롤러는 다음과 같이 구성할 수 있다.
     • 시드 페이지를 우선순위 큐에 넣는다.
     • 우선순위 큐에서 페이지를 꺼낸 후 해당 페이지 정보를 탐색한다.
     • 해당 페이지 내 하이퍼링크를 우선순위 큐에 넣는다.
       
       
7. What is focused crawling? What is incremental crawling?
   • focused crawling: 특정 주제에 관한 페이지만 크롤링한다. 
   • incremental crawling: 한 번 인덱스를 구축한 뒤에는 모든 웹 페이지를 크롤링하지 않고 주기적으로 일부 페이지만 크롤링하여 정보를 업데이트한다.
     
     
8. What kind of pages should have a higher priority for recrawling in incremental crawling?
   • 자주 업데이트되는 페이지나 사람들이 자주 접속하는 페이지 위주로 크롤링한다.
     
     
9. What can we do if the inverted index doesn’t fit in any single machine?
   
   • 확장성(Salability)과 효율성(Efficiency) 부분을 개선할 필요가 있다.
   • 확장성과 효율성을 개선하기 위해 Google File System(GFS)과 MapReduce를 활용할 수 있다.
     
     
10. What’s the basic idea of the Google File System (GFS)?
    • GFS는 Master Node, Chunk Servers, Clients로 구성되어 있다.
      • Master Node: 메타데이터를 관리하고 전체적인 시스템을 조종한다.
      • Chunk Servers: 데이터가 고정된 크기(64MB)로 나뉘어 여러 청크 서버에 저장된다. 
      • Clients: Master와 상호작용 하여 메타데이터를 획득하며 청크 서버에 저장된 데이터를 읽거나 청크 서버에 데이터를 저장한다.
        
        
11. How does MapReduce work? What are the two key functions that a programmer needs to implement when programming with a MapReduce framework?
    • Mapping은 들어온 입력값을 Key와 Value 형태로 묶는 과정이다.
    • Reducing은 동일한 Key 값을 가진 데이터를 처리하는 과정이다 (예: `(word, total_counts)`)
      
      
12. How can we use MapReduce to build an inverted index in parallel?
    
    • 각 단어에 (document_number, total_counts)를 할당한다.
    • 각 단어(Key)로 정렬한다.
    • 각 단어(Key)에 할당된 (document_number, total_counts)를 합친다.
    • 최종적으로 {'coffee' : {(D1, 1), (D2, 2)}}와 같은 Inverted Index가 구축된다.
      
      
13. What is anchor text? Why is it useful for improving search accuracy?
    • anchor text는 클릭이 가능한 하이퍼링크를 뜻한다.
    • 다수의 페이지가 가리키는 특정 페이지는 중요한 문서일 확률이 높다.
      
      
14. What is a hub page? What is an authority page?
    • hub page: 다른 유용한 페이지들을 모아놓은 정보의 창구이다.
    • authority page: 믿을 만한 중요한 정보를 담고 있는 페이지이다.
      
      
15. What kind of web pages tend to receive high scores from PageRank?
    • 다른 페이지로부터 인용된 횟수가 높을 수록 높은 점수를 얻는다.
    • 인용된 횟수가 높은 페이지로부터 인용된다면 높은 점수를 얻는다.
      
      
16. How can we interpret PageRank from the perspective of a random surfer “walking” on the Web?
    • PageRank가 다른 페이지를 방문하는 확률분포는 아래와 같다.
    • 다음 페이지 = (모든 페이지) / (모든 페이지 수) + (페이지 내 하이퍼링크) / (페이지 내 하이퍼링크 수)
    • 따라서 PageRank는 어떤 페이지든 방문할 수 있으며 "random surfer"라고 볼 수 있다.
      
      
17. How exactly do you compute PageRank scores?
    • 아래 수식을 이용해 PageRank 점수를 계산한다.

 

18. How does the HITS algorithm work?

• 인접행렬의 반복 연산을 통해 HITS 점수를 계산한다.
• Authorities와 Hubs를 모두 고려한 점수라는 점이 특징이다.