課程｜資訊檢索

# 資訊檢索 ## 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)