# IR

> [toc]

### Term Dependencies
1. Capturing term dependencies is a way beyond traditional IR models. Please list two methods to ==model term dependencies==. Any two methods are welcome.
Ans：同第四題， term correlation matrix or minterm
3. Term independence is a strong assumption in classic IR modeling. Please explain how generalized vector model relaxes the assumption
Ans：同第四題，將term的representation用minterm表示，讓term之間有關連性。
5. 
Ans：basic vector model 就是假設index term都是各自獨立的，generalized vector model是用minterm來解決，公式與說明同第四題。

7. 
Ans

### document representation, query representation, and a ranking function.
1. 
Ans
不是很確定probabilistic model中query和document的representation，因為只要計算ni和N就可以算Rank。

3. 
Ans
同第一題BM25是probabilistic model，不確定query和document的representation

5. An IR model is specified by document representation, query representation, and a ranking function. Please describe these three parts for BM25 model
Ans：同第二題

7. Representations of queries and documents and computation of their relationship degree are key components in an IR framework. Please compare counting-based IR model and prediction-based IR model from aspects of representations and similarity computation. You can select any one model to describe your answers

### latent semantic indexing model
1. Please explain how latent semantic indexing model maps terms and documents into the same vector space
Ans：
by using Singular Value Decomposition (SVD) Model
M=KSD ；where
* K is a term-term Matrix,
* S is a diagonal matrix of singular value,
* D is a document-document matrix.

3. In latent semantic indexing, we try to map both terms and documents into lower dimensional space, and perform the similarity computation on that space. Please show how to compute term vectors, document vectors, and vectors of input queries in the reduced space
4. 

6. 
Ans

### counting-based IR model and prediction-based IR model
1. Representations of queries and documents and computation of their relationship degree are key components in an IR framework. Please compare counting-based IR model and prediction-based IR model from aspects of representations and similarity computation. You can select any one model to describe your answers
2. Counting-based language model is based on Markov assumption with a restriction of history length k. Besides, the history is read from left to right. That is, the context is also restricted. Please propose a neural language model to relax these two restrictions.
3. 

### two sides ?
> [Looks like these are the same since "filtering = routing" according to q.3]
1. Information retrieval and information filtering are two sides of the same coin.Please describe how information retrieval concepts can be applied to information filtering.
2. Searching and routing are two sides of a same coin. In the class, you have learned lessons to evaluate the performance of a searching system. Please describe the concept of routing first, and discuss how to evaluate the performance of a routing system.
3. 

### tf-idf
1. 
Ans

### query likelihood, document likelihood and model comparsion
1. 
Ans

### Probabilistic Model
#### BM25
1. 
Ans

#### language model
1. 
Ans

---
* Filtering is often meant to imply the removal of data from an incoming stream, rather than finding data in that stream. In the first case, the users of the system see what is left after the data is removed; in the later case, they see the data that is extracted.

---

# Notes
* **Information retrieval** is about returning the information that is relevant for a specific query or field of interest of the user. While **information extraction** is more about extracting general knowledge (or relations) from a set of documents or information.

* Indx Term

* IR model
* 
* 
* 
* 

#### Classic IR Model
##### Boolean Model

##### Term Weight

* Term Weighting was introduced to measure the importance of an index term in a document or a query, respectively.
* For classic IR, the index term weights are assumed to be mutually independent (ex: Classic Vector Model), to take into account term-term correlations, we can compute a correlation matrix to get the correlation among terms.
* How to measure importance of an index term? -> TF-IDF
* tf: (occurences of term k / Document)
* idf: (number of documents / number of documents that include term k) -> term with higher idf is more important.
* (tf * idf) is a classic term weighting strategy
* 
* 
* 
* 
* Document length normalization
* 

##### Vector Model





##### Classic Probabilistic Model




經過一堆看不懂的推導得到





To do: initialization?

---

### Advanced Model: consider term dependencies

#### Set Theoretic IR Models
##### Set-based Model
用term set 替代 index term, when a document includes all index terms in a termset, the document includes this termset.

* term set is used to capture term dependencies.
* 

To reduce number of termset: only frequent term set is used.
* 
frequent: 組起來的termset 中的 index term 數量 >= threshold
* 
* $$ S_{abd} = \{d_1\}, N_i = 1, \text{not frequent}$$

* 

* 

* closed termsets: frequent term set還是太多了，想辦法再減少 -> keep the largest

##### Extended Boolean Model
透過把vector model 特性跟 boolean algebra 結合來解決傳統boolean model 沒有ranking, 缺乏partial matching and term weighting的問題




根據document中對index term x 跟 y的權重定義出d_j的向量, x, y權重計算方法：


如何計算document an query simularity? ：跟0,0越遠越好, 1,1越近越好

* 多維度的時候-> p-norm
p = 1 的時候等於是取平均值 -> vector like-> recall

p = infinity: fuzzy like

* 如此一來，operator的順序 matters

##### Fuzzy Set Model

A document without query term coule also be higly realative to a query! (ex: it has a term related to query term) -> to solve this issue -> Fuzzy!

The degree of membership is between 0 and 1, not distinct, but smoothly


* how to get fuzzy set? -> by term-term correlation matrix -> find intersection
* 
* d_j 相對於 k_i 會有一個 degree of membership -> c_il 是 index term i and l的相關程度，那d_j跟k_i的degree就是1 - 連乘(k_i 跟 index term k_l 的不相關程度), 想像如果有一個k_l跟k_i很有關係, c_il = 1, 那d_j跟k_i的degree就是1, 如此就可以透過fuzzy的概念來讓即使沒有含有k_i的d_j也能跟query有關係
* 

---
#### Algebraic IR Models
##### Generalized Vector Model
Use minterm to capture term dependency
整體與Vector Space Model相似, 但拿掉term vector間為independent的限制. 把term vector 用minterm展開, 而minterm vector間為independent
用minterm represents a document, 再透過具相同minterm的document計算c_ir，最後用c_ir and minterm represent index term vector. finally, k_i, k_j is not orthogonal. when we calcuate simularity, k_i * k_j != 0 anymore. -> term dependency !



k_i跟k_j同時出現在很多的文章出現的話，他們的關聯程度應該是很高的




##### Latent Semantic Indexing
generalized vector model is high dimentional and sparse whereas latent semantic is low dimentinal and dense.

不應該用intex term 處理，而需要mapping到某個空間去做計算

we need concept retrieval not index term retrieval.

A query is represented by a pseudo document.

Through SVD, we can get term matrix and document matrix. selecting S -> reduce concept space



---

#### Probabilistic Model
##### BM25
improvement in term weighting.

Classic probabilistic model covers only "idf", but not tf, and document length norm.

BM15: term frequency
BM11: document length norm
BM25: BM11 + BM15




##### Language Model

* The language modeling approach to IR directly models that idea: a document is a good match to a query if the document model is likely to generate the query, which will in turn happen if the document contains the query words often
* 一個distribution用來估算某個字串出現的機率跟下一個token是什麼
* 每個doc有一個model-> model產生該query的機率來當作query跟doc的相關程度
* 

unigram->independent
* 
取log，分為q在d跟不在d
* 
後半段(only not include)
有很多方法可以算ki在collection的機率
* 
* 
前半段(include / not include)
* 
還要一個smoothing 避免0的情形
* 
smoothing的方法有很多
* 

經過一堆吐血的推導，終於得到的ranking function
* 

##### Another Language Model based on bernoulli process
* 
一樣有很多方法可以算ki在collection的機率, 阿我們選下面那個
* 

based on above, the probability that term k_i will be produced by a random draw taken from d_j
* 

加上考慮k_i出現在document的frequency

* 
* 

終於得到的ranking function
* 

##### Query Model vs Document Model
* 前面用的是Document Model產生query (1, query likelihood)，也可以反過來用Query Model產生document (2, document likelihood), 還可以比較兩個model(3)
* 
* 
* 
* 
* mQ and mD generate 出 term t的 KL divergence

* How can one do relevance feedback using language modeling approach?
* 
* Expansion-based: 先算出query likelihood, 根據result 取rank前幾名的文章形成feedback docs, 再利用feedback doc來 expand query. -> 權重可能改變, query中的term 可能改變，but doc model是不變的
* Model-based: 先算出mQ跟mD的的KL divergence, 根據result 取排序前幾名的feedback docs, 利用feedback docs更新Query Model.
* Expansion-based 是更新query, Model-based是更新query model.
* How to update query model?
* 

* Translation Model
d 不是直接generate q, 是先經過一個translation process. 相關性就可以透過non-query term來處理

---
累了，這邊隨便整理orz
#### Neural IR

* Translation Model:

BM25, LM , Translaiton model都沒有考慮到term 跟term order相鄰的關係 ->
1. Dependency model
2. Relevance Model


#### Neural Approach to IR
* Neural Approach can be used in different points
* 
* 
* 

##### Term Representations
* 
* 
* 

* Observed
* Typical (seattle and sydney are cities) V.S Topical (seattle and seaharks are related to football)
* 
* 
* Latent
* LSA (svd)
* PLSA
* LDA
* word2vec: to encode the context around the word rather than the word itself. 一個詞的語意是被其他鄰近且一起出現的詞所定義. word2vec has IN and OUT embeddings.
* 
* Paragraph2vec
* 

##### Term Embeddings for IR
IR 需要做 quert-document matching, term embeddings 適合用在inexact matching
IR 也需要做feedback update, term embeddings可以用來做query expansion.
* 

* 

這一個建議query用in, doc 用out
* 

還有各式各樣inin outout inout mix的方法

Word Embeddings is a technique where individual words are represented as real-valued vectors in a lower-dimensional space and captures inter-word semantics.

### Relevance Feedback AND Query Expansion
1. feedback 有什麼可以用來expand query的？ 怎麼用？
2. explicit: directly from user, relevance or click
3. implicit: from system
* 

#### Explicit Relevance Feedback
* user 直接幫忙report哪些是相關的doc, 哪些是不相關
* 希望新的query找出更多相關的doc
* The Rocchio Method: 接近相關，遠離不相關
* 
* 
* A Probabilistic Method
* Evaluation：residual collection:
* 

#### Explicit Feedback Through Clicks
* eye tracking
* relevance judgements
* click as user preferences
* 
* 
* 
* 

#### Implicit Feedback Through Local Analysis
1. Local clustering
* 
* 

3. Local