『IR 信息檢索入門必看』#9 網(wǎng)頁排序（簡明）

訪問博客查看 本文 最新內(nèi)容，排版更美觀ヾ(?ω?`)o 如有錯誤歡迎指出~

IR 信息檢索系列筆記：

當(dāng)我們在一個小的文檔庫中查詢時，即使 query 很模糊，我們只要返回所有相關(guān)文檔即可，甚至不需要猜測用戶的查詢需求。

但如果在一個大的文檔集中查詢時（比如谷歌），往往可以返回大量的相關(guān)文檔。如果基于相關(guān)度的 ranking，往往無法區(qū)分哪些文檔該呈現(xiàn)在最前面，甚至可能時一些低質(zhì)量的網(wǎng)頁對于某些詞的詞頻很高，從而排在了前面。

此時我們就不能只聚焦與「相關(guān)度」，PageRank 算法通過計算一個頁面的「重要度」，從而判別網(wǎng)頁質(zhì)量，得到排序。

基本思想

如何衡量「重要度」？用點擊率、權(quán)威性？然而，這些數(shù)據(jù)都是爬蟲無法爬取到的，同時也難以正確衡量。

科學(xué)家們從 Bibliometrics (文獻(xiàn)計量學(xué)) 中借鑒了如下觀點：

  • Bibliographic coupling (引文耦合)：兩篇文章具有相近的引用。
  • Co-citation (協(xié)同引用)：兩篇文章被大量其他文章同時引用。
  • Impact factor (影響因子)：一個期刊中的文章的年平均被引次數(shù)，衡量了一個期刊的「重要度」。

例如，最權(quán)威的 SCI 往往只收錄其認(rèn)為重要的期刊，也只記錄其中的期刊相互引用的次數(shù)。當(dāng)一篇文章被 SCI 收錄的文章引用時，通常也可以說明其有一定的影響力——即重要度的「傳遞」。

對于文獻(xiàn)引用的可視化，我們通常稱為 Citation Graph，通常是一個 Directed Acyclic Graph (有向無環(huán)圖，DAG)，因為較早的文章無法修改而引用后來的文章。

在網(wǎng)頁中，我們可以 Hyperlinks (超鏈接) 來類比引用，從而形成一個 Hyperlink Graph，區(qū)別是這類圖中可以有環(huán)路。

從而引出網(wǎng)頁排序的基本假設(shè)：

  • The rank of a web page is higher if many pages link to it.
  • Links from highly ranked pages are given greater weight than links from less highly ranked pages.

PageRank Algorithm

基于上述假設(shè)，我們很容易可以得到當(dāng)前頁面的鏈入、鏈出數(shù)。但是，要怎么知道鏈入當(dāng)前頁面的前序頁面，其重要度是多少呢？

隨機游走模型 | Random Walk Model

在一個封閉的 Hyperlink Graph 中，隨機選取一個頁面作為訪問起點，隨機選取其鏈出的頁面進行訪問，再對下一個頁面重復(fù)上述操作。

大量重復(fù)后，統(tǒng)計每個結(jié)點被訪問的頻率，用頻率近似概率后，我們可以發(fā)現(xiàn)訪問概率較大者通常有著較多的鏈入，或者其鏈入頁面也有著較大的訪問概率。用公式表示就是：
\mathrm{Pr}\left( P_i \right) =\mathrm{Pr}\left( P_i\mid P_1 \right) \mathrm{Pr}\left( P_1 \right) +\mathrm{Pr}\left( P_i\mid P_2 \right) \mathrm{Pr}\left( P_2 \right) +\cdots +\mathrm{Pr}\left( P_i\mid P_N \right) \mathrm{Pr}\left( P_N \right)
其中 \mathrm{Pr}\left( P_i\mid P_1 \right) 表示從編號為 1 的網(wǎng)頁跳轉(zhuǎn)到編號為 i 的網(wǎng)頁的概率，其計算方式為：
\mathrm{Pr}\left( P_i\mid P_1 \right) =\begin{cases} 0\text{，如果}P_1\text{到}P_i\text{沒有鏈入}\\ \frac{1}{m}\text{，}m\text{為}P_1\text{的鏈出數(shù)}\\ \end{cases}

矩陣表示 | Matrix Representation

令 w_i=\mathrm{Pr}\left( P_i \right)，則 \boldsymbol{w}=\left[ \mathrm{Pr}\left( P_1 \right) ,\mathrm{Pr}\left( P_2 \right) ,\cdots ,\mathrm{Pr}\left( P_N \right) \right] ^T，再令 \boldsymbol{B}_i=\left[ \mathrm{Pr}\left( P_i\mid P_1 \right) ,\mathrm{Pr}\left( P_i\mid P_2 \right) ,\cdots ,\mathrm{Pr}\left( P_i\mid P_N \right) \right]，則有：

w_{i}=B_i\cdot \boldsymbol{w}

特別地，當(dāng) i 取遍 1 到 N 的所有值后， 得到矩陣形式：
\boldsymbol{w}=B\cdot \boldsymbol{w}
其中 B 稱作標(biāo)準(zhǔn)化鏈接矩陣，矩陣中的每個元素代表列號對應(yīng)的 Page 鏈入行號對應(yīng)的 Page 的概率，每列之和為 1。當(dāng)一個頁面沒有鏈出時，這一列全為 0。

于是我們可以用迭代方法求解這個方程的穩(wěn)定解 \boldsymbol{w}_k——即我們想求的訪問概率向量，也就是重要度向量。只需要將 \boldsymbol{w}_0 設(shè)為全 1 向量（因為一開始隨機訪問到每個頁面的概率都相同），不斷代入即可。

阻尼迭代 | PageRank with Damping

然而，現(xiàn)在存在的問題是，上面的所有推導(dǎo)都是建立在理想狀態(tài)下的，即假設(shè)所有網(wǎng)頁組成的這個有向圖是強連通的。

當(dāng) Hyperlink Graph 存在 link loops (循環(huán)陷阱)，即存在一個小的子圖，只有鏈入沒有鏈出，所有隨機游走的用戶到了這幾個網(wǎng)頁后，就如同進了黑洞一般，一直在里面“打轉(zhuǎn)”，出不來了。

這樣就使得當(dāng)游走次數(shù)趨于無窮時，最終陷阱中結(jié)點的訪問次數(shù)遠(yuǎn)大于其他結(jié)點。這樣會使得計算出的 \boldsymbol{w} 向量中，陷阱外的結(jié)點訪問概率都為 0。

PageRank 算法最終采用了阻尼因子（damping factor）的修正，使得進入陷阱后仍有機會跳出循環(huán)。
\boldsymbol{w}_k=d\boldsymbol{w}_0+\left( 1-d \right) B\cdot \boldsymbol{w}_{k-1}
其中 \boldsymbol{w}_0 為全 1 向量，d 是實驗確定的常數(shù)，通常取 0.15。

結(jié)合相關(guān)度 | Combined Method

有了重要度向量后，當(dāng)有查詢時，我們只需要先確定命中文檔（至少有一個 term 與 query 相同的文檔），再將其用重要度排序即可。

然而，這樣做的缺點是，沒有考慮到查詢和文檔的相關(guān)性——即，有可能一篇文檔雖然有相同的 term，但主題卻相去甚遠(yuǎn)。

于是，有人提出了結(jié)合 Term Weighting 和 PageRank 的方法，在確定命中文檔后，利用傳統(tǒng)的權(quán)重計算方法，計算出 query 和每個 doc 的相似度 s_j。再和重要度 p_j 線性加權(quán)算出排序指標(biāo)：
c_j=\lambda s_j+\left( 1-\lambda \right) p_j
其中 \lambda 為實驗確定的常數(shù)。

PageRank 算法缺點

  1. 忽略了查詢，則忽略了 query 和 doc 主題相關(guān)性，導(dǎo)致結(jié)果的相關(guān)性降低。

  2. 沒有過濾廣告鏈接和功能鏈接（例如常見的分享鏈接）。這些鏈接通常沒有什么實際價值，前者鏈接到廣告頁面，后者常常鏈接到某個社交網(wǎng)站首頁。

  3. 對新網(wǎng)頁不友好。因為即使是非常好的新頁面也不會有很多鏈入，要成為一個高重要度的頁面仍需要很長時間的推廣。

主題敏感 PR | Topic-Sensitive PageRank

在實際的網(wǎng)絡(luò)中，PageRank 算法還存在「主題漂移」問題，特別對于大量隨意交互外鏈的站點，會導(dǎo)致搜索引擎返回主題無關(guān)結(jié)果。

同時，前面的討論提到，PageRank 忽略了 query 的主題相關(guān)性，也導(dǎo)致了結(jié)果的相關(guān)性降低。同一查詢詞在不同語境下，語義上指向的可能是不同的主題，但 PageRank 無論如何都是返回「重要度」最高的頁面。

理想情況下，應(yīng)為每個用戶的偏好維護一套專用的「主題重要度」向量，但面對海量用戶這種方法顯然不可行。所以搜索引擎一般會選擇一種稱為主題敏感的折中方案。

基本思想 | Basic Idea

基本假設(shè)：在 PageRank 的隨機游走模型中，用戶傾向于選擇具有同一個主題的鏈出網(wǎng)頁。

基于這個假設(shè)，可以預(yù)定義幾個話題類別，例如體育、娛樂、科技等等，對于某個網(wǎng)頁來說，對應(yīng)某個主題類型都有相應(yīng)的 PageRank 分值，然后想辦法關(guān)聯(lián)用戶的話題傾向，根據(jù)用戶的話題傾向排序結(jié)果。

矩陣形式 | Matrix Form

與原始的 PageRank 不同，新的算法對出度為 0 的網(wǎng)站加以處理以保證收斂性。引入了向量 \boldsymbolu0z1t8os 來指示某一個網(wǎng)頁是否出度為 0，若為 0 則對應(yīng)項為 1。
d_{i}= \begin{cases}1 & \text { if } \operatorname{deg}(j)=0 \\ 0 & \text { otherwise }\end{cases}

向量 \boldsymbol{p} 來表示訪問各個網(wǎng)頁的概率均等，代替 \boldsymbol{w}_0 的寫法：

\boldsymbol{p}=\left[\frac{1}{n}\right]_{n \times 1}

兩個矩陣的乘積所得的矩陣 D 表示出度為 0 的網(wǎng)頁將以均等概率訪問其他網(wǎng)頁。與前述提到的矩陣 B 具有互補的特性，補充了在隨機游走模型中，一個網(wǎng)頁出度為 0 時的訪問頁面的情況。這樣做使得最終矩陣的每一列之和都為 1。
D=\boldsymbol{p} \times \boldsymbolu0z1t8os^{T}
則最終排名的計算方法為：
\boldsymbol{Rank} =d \boldsymbol{p} + (1-d)(B+D) \cdot \boldsymbol{Rank}

偏置向量 | ODP-Biasing

主題的預(yù)定義參考了 ODP (Open Directory Project) 網(wǎng)站，利用 ODP 中 16 個頂級分類下的 URLs 生成了 16 組偏置 PageRank 向量 (biased PageRank vectors)。

為了實現(xiàn)這一點，算法中采用了新的向量 \boldsymbol{v_j}=\boldsymbol{p}，針對每個主題有：
v_{j i}=\left\{\begin{array}{cl} \frac{1}{\left|T_{j}\right|} & i \in T_{j} \\ 0 & i \notin T_{j} \end{array}\right.
其中 T_{j} 表示在契合第 j 個主題的網(wǎng)頁集合。包含在這些網(wǎng)頁中的頁面被賦予較大的跳轉(zhuǎn)概率值，而其他網(wǎng)站則相對減少。

查詢打分 | Query-Time Importance Score

此外，還需要在給定一個查詢 q 的時候，估算出該查詢落在某個主題 c_j 的概率。文章使用了樸素貝葉斯分類器（naive-Bayes classifier），將查詢 q 中的每個 term 分詞記作 q_i，利用貝葉斯公式：
P\left(c_{j} \mid q\right)=\frac{p\left(c_{j}\right) \cdot P\left(q \mid c_{j}\right)}{P\left(q\right)} \propto P\left(c_{j}\right) \cdot \prod_{i} P\left(q_{i} \mid c_{j}\right)
而 P\left(q_{i} \mid c_{j}\right) 則容易用統(tǒng)計的方法估計出來，對于 P\left(c_{j}\right) 則采用先驗概率的方法，根據(jù)用戶的查詢歷史（上下文）進行動態(tài)調(diào)整。

計算出了查詢落在各個主題的概率后，再用這個概率對各個主題下的 Rank 向量進行線性加權(quán)，即可得到最終排序用的評分：
s_{q d}=\sum_{j} P\left(c_{j} \mid q^{\prime}\right) \cdot r_{j d}

HITS: Hyperlink-Induced Topic Search

這里再介紹一種基礎(chǔ)的網(wǎng)頁排序算法——基于超鏈接追敏的主題排序，對于一個查詢，不再返回單一的網(wǎng)頁排名，而是同時返回兩個列表：

  • 包含鏈接的 Hub 網(wǎng)頁，收錄了主題相關(guān)的權(quán)威網(wǎng)頁鏈接。
  • 包含內(nèi)容的 Authority 網(wǎng)頁，有著與主題相關(guān)的高質(zhì)量內(nèi)容。

那么，如何排序這兩個列表呢？

基本假設(shè)：

  • 一個好的 Hub 網(wǎng)頁指向該主題的許多 Authority 網(wǎng)頁。
  • 一個好的 Authority 網(wǎng)頁被許多好的 Hub 網(wǎng)頁指向。

基于這兩個假設(shè)，我們可以提出兩個指標(biāo)來衡量每個頁面：樞紐值（Hub Scores）和權(quán)威值（Authority Scores），這兩種值是互相依存、互相影響的。

  • 樞紐值，指的是頁面上所有出鏈指向頁面的權(quán)威值之和。
  • 權(quán)威值，指的是頁面的所有入鏈所在的原頁面的樞紐值之和。

算法步驟 | HITS Algorithm

  1. 找出 root set：根據(jù)用戶 query 中的 term，在文檔集中找出包含至少一個 term 的的文檔，使他們構(gòu)成 root set。

  2. 找出 base set：在 root set 的基礎(chǔ)上，找出集合中網(wǎng)頁鏈入或鏈出并且不在 root set 中的網(wǎng)頁，并把他們加入到集合中，從而構(gòu)成 base set。

  3. 計算每一個網(wǎng)頁的樞紐值 h(x) 和權(quán)威值 a(x)，初始時，所有 h 值和 a 值均為 1。

  4. 迭代更新兩個值直至收斂。為了防止兩個值太大，可以在每次迭代后歸一化。歸一化的指標(biāo)不重要，因為我們只關(guān)注相對排名。

  5. 返回兩個值分別排序的列表。

HITS 算法缺點

  1. 盡管限制了計算對象在 base set 中，但在線計算效率還是太低，不如 PR 快。
  2. 主題漂移現(xiàn)象仍未解決。如果在集合里包含與查詢主題無關(guān)的頁面，且含有大量相互鏈接，可能會排到前列。這種現(xiàn)象被稱為緊密鏈接社區(qū)現(xiàn)象。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容