---
# System prepended metadata

title: 課程｜資訊檢索
tags: [課程]

---

# 資訊檢索

## Indexing
- **IR 問題定義：**
    - 給定 $corpus=\{d_1,d_2,...,d_n\}$，其中每一個 document $d=[w_1~~~w_2~~~...~~~w_k]$
    - 給定 $query=[q_1~~~q_2~~~...~~~q_m]$
    - 請問 $corpus$ 中，和 query 相關的文件有哪些？？
- **挑出適當的 index term。**
    - 原則一：忽略高頻字(stop word)
    - 原則二：將有形態變化的字轉為原型
- **給定 index term，表示 document 和 query。**
    - $\text{index term}=\{k_1,k_2,...,k_t\}$，根據有無出現，可表示成 $t$ 維的 binary 向量。
        - document：$c(d_j)=(w_1,w_2...,w_t)$
        - query：$c(q)=(w_1,w_2...,w_t)$
    - Term-Document Matrix
        - 每個 document 出現了哪些 term。
        - 每個 term 出現在哪些 document。
    - Term-term Matrix
        - 兩個 term 之間的關聯性。
## **Vector Space Model**
- 符號說明：
    - $f_{i,j}$ 表示 $k_i$ 在 $d_j$ 的 term frequency
    - $F_{i}=\sum{f_{i,j}}$ 表示 $k_i$ 的 total occurences in corpus
    - $n_i$ 表示 $k_i$ 的 document frequency。
- 把每一個 document、query，表示成一個向量
    - $d_j=(w_{1j},w_{2j},...,w_{tj})$
    - $w_{i,j}=\begin{equation} \left\{ \begin{array} ~(1+logf_{i,j})~log\frac{N}{n_i} & \text{, if } f_{i,j}>0 \\ 0  & \text{, otherwise} \end{array} \right. \end{equation}$
    - 視需求加入 document length normalization。
    - $sim(d_j,q)=\frac{d_j\cdot q}{|d_j||q|}$
- **Zipf’s Law**：Corpus 中，頻率 f 和 排名 r 的關係，滿足：
    - 一般形式：$f=C*r^{-\alpha}$
    - 簡易形式：$fr=const.$
- **Generalized Vector Model**
    - 目標：把 terms $k_1,k_2,k_3,k_4$ 再仔細找出關聯，用另一個觀點的向量表示。
        - $d_1=(1,0,2,0)$
        - $d_2=(0,0,0,1)$
        - 但兩文件仍可能有相關。
        - 有 $2^4=16$ 個 minterm $m_r$，每個 $m_r$ 表示『各個 term $k_i$ 有無出現』。
    - 步驟：
        - 找出每篇 document 對應到哪些 minterm。
        - 每個 minterm 計算 $k_i$ 在所有對應的 document 中出現幾次。
            - $c_{i,r}=\sum\limits_{c(d_j)=m_r}w_{i,j}$
        - 根據 $m_r$ 和 $k_i$ 的對應關係，把 $k_i$ 用 $m_r$ 表示。
            - $k_i=\frac{\sum on(i,m_r)c_{i,r}m_r}{\sqrt{\sum on(i,m_r)c_{i,r}^2}}$
        - document 由 $k_i$ 表示 $\rightarrow$ document 由 $m_r$ 表示。
- **Latent Semantic Indexing**
    - 透過矩陣的SVD分解，人工的刪除矩陣中的某些欄位
        - 刪太多：無法代表原來的資料。
        - 刪太少：無法 filter 掉 non-relevant details。
    - ![](https://i.imgur.com/inqyZoO.png)
## **Probabilistic Model**
- $d_j=(x_1,x_2,...,x_t)$
- $q=(q_1,q_2,...,q_t)$
- $sim(d_j,q)=\frac{P(R|d_j,q)}{P(NR|d_j,q)}=\frac{P(R|q)}{P(NR|q)}\frac{P(d_j|R,q)}{P(d_j|NR,q)}\\~~~~~~~~~~~~~~~~~=O(R|q)\prod\limits_{i=1}^t\frac{P(x_i|R,q)}{P(x_i|NR,q)}\\~~~~~~~~~~~~~~~~~=O(R|q)\prod\limits_{x_i=1}\frac{p_i}{u_i}\prod\limits_{x_i=0}\frac{1-p_i}{1-u_i}\\~~~~~~~~~~~~~~~~~=O(R|q)\prod\limits_{x_i=q_i=1}\frac{p_i(1-u_i)}{u_i(1-p_i)}\prod\limits_{q_i=1}\frac{1-p_i}{1-u_i}$
- **Retrieval Status Value Estimation：**
    - 對固定query，假設已知 R 以及 NR
    - 對每個 term $x_i$
        - $p_i=P(x_i=1|R,q)=\frac{r_i}{R}$
        - $u_i=P(x_i=1|NR,q)=\frac{n_i-r_i}{N-R}$
            -|relevant|nonrelevant|total
            -|-|-|-
            $x_i$ 出現|$r_i$  |$n_i-r_i$    |$n_i$
            $x_i$ 消失|$R-r_i$|$N+r_i-R-n_i$|$N-n_i$
            $ALL$ 　　|$R$    |$N-R$        |$N$
    - $RSV(d_j,q)=\sum\limits_{q_i=x_i=1}log\frac{p_i(1-u_i)}{u_i(1-p_i)}\\~~~~~~~~~~~~~~~~~~=\sum\limits_{q_i=x_i=1}log\frac{r_i+0.5}{R-r_i+0.5}\frac{N+r_i-R-n_i+0.5}{n_i-r_i+0.5}$
- 一些性質
    - **IDF like**：
        - $R=0$時 ， $RSV(d_j,q)=\sum\limits_{q_i=x_i=1}log\frac{N-n_i+0.5}{n_i+0.5}$
    - **Negative weight**：$n_i>\frac{N}{2}\rightarrow RSV<0$
        - 有時候會把公式改成：$RSV(d_j,q)=\sum\limits_{q_i=x_i=1}log\frac{N+0.5}{n_i+0.5}$
- **Relevance Feedback**
    - 對於 $q$ ，我們一開始沒有 $R$。
    - 只要我們有 $R$，我們就可以對所有 $d_j$ 排序。
    - 排序完就可以找出最相關的幾個 document，做為新的 $R$。
    - **Recursively：** 因此我們可以初始化假設一個 $R$，重複『ranking + 重新設定 $R$』，直到收斂為止。
## **BM25**
- Based on 機率模型，without 相關文件 R。
- 以大量現實資料，找出表現最好的參數及公式。
- 結果經常被用來當作 simple baseline。
- 實驗結果：
    - BM1：$sim(d_j,q)=\sum\limits_{q_i=x_i=1}log\frac{N-n_i+0.5}{n_i+0.5}$
    - BM15：$sim(d_j,q)=\sum\limits_{q_i=x_i=1}\frac{(K_1+1)f_{i,j}}{K_1+f_{i,j}}\times log\frac{N-n_i+0.5}{n_i+0.5}$
    - BM11：$sim(d_j,q)=\sum\limits_{q_i=x_i=1}\frac{(K_1+1)f_{i,j}}{\frac{K_1~len(d_j)}{avg\_len}+f_{i,j}}\times log\frac{N-n_i+0.5}{n_i+0.5}$
    - BM25：$sim(d_j,q)=\sum\limits_{q_i=x_i=1}\frac{(K_1+1)f_{i,j}}{K_1\times[~(1-b)+b\frac{~len(d_j)}{avg\_len}~]+f_{i,j}}\times log\frac{N-n_i+0.5}{n_i+0.5}$
    - 建議設定 $K_1=1$， $b$ 接近 $1$。
## **Language Model**
- Learning From Data
    - 核心觀念：
        - 給定 data，不能直接算出對應 model 的機率。
        - 給定 model，能輕易算出產生特定 data 的機率。
        - $P(\theta|X)\rightarrow P(X|\theta)P(\theta)$
        - **以下的推導，目標就是找到使 $P(X|\theta)P(\theta)$ 最大最好的 $\theta$。**
    - Priori Probabiliry：$P(\theta)$
    - Posteriori Probability：$P(\theta|X)$
    - Maximum Likelihood Estimation 的應用
        - 假設 $d=(3,5,2)$ 是由 multinomial unigram language model M 所產生：
        - $max~P(d|M)=\frac{10!}{2!3!5!}~p^3q^5r^2$ 滿足 $p+q+r=1$
            - 可以推得 → $p=0.3, q=0.5, r=0.2$
- 以下由 **Query Likelyhood** 出發，討論 **multinomial unigram language model**
    - 每個 $d_j$ 背後都有對應的 $M_j$，現在考慮：$d_j=[a,b,b,b,d],$$\\C=[\#a=100,\#b=200,\#c=400,\#d=800]$
    - 不考慮 smooothing ：
        - $log~P(q|M_j)=log~\prod\limits_{k_i\in q}P(k_i|M_j)=\sum\limits_{k_i\in q}log~P(k_i|M_j)$
    - 考慮 smooothing ：
        - 機率重新分配：$P(k_i|M_j)=\begin{equation} \left\{ \begin{array} ~P_{\in}(k_i|M_j)~~~k_i\text{ appear in  }d_j\\\alpha_jP(k_i|C)~~~\text{otherwise} \end{array} \right. \end{equation}$
        - 演算法：
            - 1.**決定** $P_{\in}(k_i|M_j)$
                - Jelinek-Mercer Method：$P_{\in}(k_i|M_j)=(1-\lambda)\frac{f_{i,j}}{\sum_if_{i,j}}+\lambda\frac{F_i}{\sum_iF_i}$
                - Dirichlet smoothing：$P_{\in}(k_i|M_j)=\frac{f_{i,j}+\lambda\frac{F_i}{\sum_iF_i}}{\sum_if_{i,j}+\lambda}$
            - 2.**決定** $P(k_i|C)$
                - Hiemstra：$P(k_i|C)=\frac{n_i}{\sum_in_i}$
                - Miller, Leek, and Schwartz：$P(k_i|C)=\frac{F_i}{\sum_iF_i}$
            - 3.根據公式算出 $\alpha_j$
                - $\alpha_j=\frac{1-\sum\limits_{k_i\in d_j}P_{\in}(k_i|M_j)}{1-\sum\limits_{k_i\in d_j}P(k_i|C)}$
            - 4.根據公式算出 $log~P(q|M_j)$
                - $log~P(q|M_j)=\sum\limits_{k_i\in q\land d_j}log~P_{\in}(k_i|M_j)+\sum\limits_{k_i\in q\land \bar{d_j}}log~P_{\notin}(k_i|M_j)\\~~~~~~~~~~~~~~~~~~~~~=\sum\limits_{k_i\in q\land d_j}log~(\frac{P_{\in}(k_i|M_j)}{P_{\notin}(k_i|M_j)})+\sum\limits_{k_i\in q}log~P_{\notin}(k_i|M_j)\\~~~~~~~~~~~~~~~~~~~~~=\sum\limits_{k_i\in q\land d_j}log~(\frac{P_{\in}(k_i|M_j)}{\alpha_jP(k_i|C)})+\sum\limits_{k_i\in q}log~\alpha_jP(k_i|C)\\~~~~~~~~~~~~~~~~~~~~~\sim\sum\limits_{k_i\in q\land d_j}log~(\frac{P_{\in}(k_i|M_j)}{\alpha_jP(k_i|C)})+n_qlog~\alpha_j$
- 三種 Measure Relevance 的方法：
    - Query Likelyhood
        - $sim(d,q)=\frac{P(R|d,q)}{P(NR|d,q)}=\frac{P(q|d,R)}{P(q|d,NR)}\frac{P(d|R)}{P(d|NR)}\frac{P(R)}{P(NR)}\sim P(q|d,R)=P(q|\theta_d)$
    - Document Likelyhood
        - $sim(q,d)=\frac{P(R|q,d)}{P(NR|q,d)}=\frac{P(d|q,R)}{P(d|q,NR)}\frac{P(q|R)}{P(q|NR)}\frac{P(R)}{P(NR)}\sim P(d|q,R)=P(d|\theta_q)$
    - Negative KL divergence
        - $sim(q,d)=-D(\theta_q||\theta_d)$
- Relevance Feedback
    - ![](https://i.imgur.com/yBfUYkG.png)
    - 算出目前相關的文件之後，**用找到的 relevance document**，來更新 query 或是 query model。
## **Neural Language Model**

## Other Models
- **Boolean Model**
    - 直接由 Term-Document Matrix 得到。
    - 可以處理由不同 index term 透過 and, or, not 組合的 Query。
- **Set Based Model**
    - 考慮到 index term 之間可能有 dependency，$term\rightarrow termset$
        - 給定 query，找出我們需要的 **termsets**
            - EX：q=[a b d] $\rightarrow$ 我們有 7 個 termsets ： $S_a,S_b,S_d,S_{ab},S_{bd},S_{ad},S_{abd}$
            - 每個 termsets ，若出現在太少 document 中，則可以不考慮它。
        - 如果覺得 termsets 種類太多，甚至可以只考慮 **closed termsets**
            - 某些 termsets 對應的文章完全相同，則只保留最大的 termsets。
    - 每篇 document ，表示成一個 termsets 向量
        - $d_j=(W_{1j},W_{2j},...,W_{2^tj})$
        - $W_{i,j}=\begin{equation} \left\{ \begin{array} ~(1+logf_{i,j})log\frac{n}{n_i} & \text{, if } f_{i,j}>0 \\ 0  & \text{, otherwise} \end{array} \right. \end{equation}$
    - $sim(d_j,q)=\frac{d_j\cdot q}{|d_j||q|}$
- **Extended Boolean Model**
    - 每篇 document ，表示成一個 normalized 向量
        - $d_j=(w_{1j},w_{2j},...,w_{tj})$
        - $w_{i,j}=\frac{tf_{i,j}}{max\_tf}\frac{idf_{i,j}}{max\_idf}$
    - $sim(d_j,q_{and})=1-\sqrt{\frac{(1-x)^2+(1-y)^2}{2}}$
    - $sim(d_j,q_{or})=\sqrt{\frac{x^2+y^2}{2}}$
    - 例子： $q=(k_1\land k_2)\lor k_3~~~~$ with $~~~~d=(x_1,x_2,x_3,...,x_t)$
        - $y=1-(\frac{(1-x_1)^p+(1-x_2)^p}{2})^{\frac{1}{p}}$
        - $sim(d,q)=(\frac{y^p+x_3^p}{2})^{\frac{1}{p}}$
- **Fuzzy Set Model**
    - 模糊集合理論 fuzzy set theory，有興趣再補充。
## Evaluation

## Mixture Model
## Topic Model
## Link Analysis
## Text Classification
## Text Clustering


## 參考
[資訊探勘](https://hackmd.io/vyP7SXwSQgWo7bilqUsPNQ)
[Andrew Moore](https://www.autonlab.org/tutorials)
[EM Algorithm](https://pdfs.semanticscholar.org/8c3e/7708aa78ba89ce85df96f17de3125def7d4c.pdf)
[cs124](https://web.stanford.edu/class/cs124/)
[cs276](https://web.stanford.edu/class/cs276/course_schedule.html)
[Advanced Methods in NLP](http://www.cs.tau.ac.il/~joberant/teaching/advanced_nlp_spring_2017/)
[Youtube Victor Lavrenko](https://www.youtube.com/user/victorlavrenko/featured)

