探尋微博背后的大數(shù)據(jù)原理：微博推薦算法簡述

“We are leaving the age of information and entering the age of recommendation” — Chris Anderson in The Long Tail。

我們正在遠離信息，而進入推薦時代?！死锼埂ぐ驳律?/span>

在介紹微博推薦算法之前，我們先聊一聊推薦系統(tǒng)和推薦算法。有這樣一些問題：推薦系統(tǒng)適用哪些場景？用來解決什么問題、具有怎樣的價值？效果如何衡量？

推薦系統(tǒng)誕生很早，但真正被大家所重視，緣起于以”facebook”為代表的社會化網(wǎng)絡(luò)的興起和以“淘寶“為代表的電商的繁榮，”選擇“的時代已經(jīng)來臨，信息和物品的極大豐富，讓用戶如浩瀚宇宙中的小點，無所適從。推薦系統(tǒng)迎來爆發(fā)的機會，變得離用戶更近：

• 快速更新的信息，使用戶需要借助群體的智慧，了解當(dāng)前熱點。
• 信息極度膨脹，帶來了高昂的個性化信息獲取成本，過濾獲取有用信息的效率低下。
• 很多情況下，用戶的個性化需求很難明確表達，比如“今天晚上需要在附近找一個性價比高、又符合我口味的餐館“。

推薦系統(tǒng)的適用場景還有很多，不再一一列舉；其主要解決的問題是為用戶找到合適的item（連接和排序），并找到一個合理的理由來解釋推薦結(jié)果。而問題的解決，就是系統(tǒng)的價值，即建立關(guān)聯(lián)、促進流動和傳播、加速優(yōu)勝劣汰。

推薦算法是實現(xiàn)推薦系統(tǒng)目標(biāo)的方法和手段。算法與產(chǎn)品相結(jié)合，搭載在高效穩(wěn)定的架構(gòu)上，才能發(fā)揮它的最大功效。

接下來我們說一下微博推薦，微博本身的產(chǎn)品設(shè)計，使得即使沒有推薦系統(tǒng)，仍然會形成一個大的用戶關(guān)系網(wǎng)絡(luò)，實現(xiàn)信息快速傳播；而衡量一個事物的價值，一個簡單的方法是對比看看保留它和去掉它時的差別。微博需要健康的用戶關(guān)系網(wǎng)絡(luò)，保障用戶feed流的質(zhì)量，且需要優(yōu)質(zhì)信息快速流動，通過傳播淘汰低質(zhì)信息。微博推薦的作用在于加速這一過程，并在特定的情況下控制信息的流向，所以微博推薦的角色是一個加速器和控制器。

最后回到微博推薦算法中來，上面扯了那么多，只是為了讓大家能對微博推薦算法有更好的理解。我們的工作，是將微博推薦的目標(biāo)和需要解決的問題，抽樣為一系列的數(shù)學(xué)問題，然后運用多種數(shù)據(jù)工具進行求解。

接下來首先用一個圖梳理下我們用到的方法和技術(shù)，然后再逐一介紹。

基礎(chǔ)及關(guān)聯(lián)算法

這一層算法的主要作用是為微博推薦挖掘必要的基礎(chǔ)資源、解決推薦時的通用技術(shù)問題、完成必要的數(shù)據(jù)分析為推薦業(yè)務(wù)提供指導(dǎo)。

這一部分中常用的算法和技術(shù)如下：

分詞技術(shù)與核心詞提取

是微博內(nèi)容推薦的基礎(chǔ)，用于將微博內(nèi)容轉(zhuǎn)化為結(jié)構(gòu)化向量，包括詞語切分、詞語信息標(biāo)注、內(nèi)容核心詞/實體詞提取、語義依存分析等。

分類與anti-spam

用于微博內(nèi)容推薦候選的分析，包含微博內(nèi)容分類和營銷廣告/色情類微博識別；

內(nèi)容分類采用決策樹分類模型實現(xiàn)，共3級分類體系，148個類別；營銷廣告/色情類微博的識別，采用貝葉斯與最大熵的混合模型。

聚類技術(shù)

主要用于熱點話題挖掘，以及為內(nèi)容相關(guān)推薦提供關(guān)聯(lián)資源。屬于微博自主研發(fā)的聚類技術(shù)WVT算法（word vector topic），依據(jù)微博內(nèi)容特點和傳播規(guī)律設(shè)計。

傳播模型與用戶影響力分析

開展微博傳播模型研究和用戶網(wǎng)絡(luò)影響力分析（包含深度影響力、廣度影響力和領(lǐng)域內(nèi)影響力）。

主要推薦算法

1. Graph-based 推薦算法

微博具有這樣的特點：用戶貢獻內(nèi)容，社會化途徑傳播，帶來信息的爆炸式傳播。之所以稱作graph-based 推薦算法，而不是業(yè)界通用的memory-based 算法，主要原因在于：

• 我們的推薦算法設(shè)計是建立在社交網(wǎng)絡(luò)之上，核心點在于從社交網(wǎng)絡(luò)出發(fā)，融入信息傳播模型，綜合利用各類數(shù)據(jù)，為用戶提供最佳的推薦結(jié)果；比如很多時候，我們只是信息傳播的關(guān)鍵環(huán)節(jié)，加入必要的推薦調(diào)控，改變信息傳播通路，后續(xù)的傳播沿著原來的網(wǎng)絡(luò)自然的傳播。
• Feed流推薦（我們稱作趨勢），是我們最重要的產(chǎn)品，而結(jié)果必須包含用戶關(guān)系。

從graph的宏觀角度看，我們的目標(biāo)是建立一個具有更高價值的用戶關(guān)系網(wǎng)絡(luò)，促進優(yōu)質(zhì)信息的快速傳播，提升feed流質(zhì)量；其中的重要工作是關(guān)鍵節(jié)點挖掘、面向關(guān)鍵節(jié)點的內(nèi)容推薦、用戶推薦。

對這部分的算法做相應(yīng)的梳理，如下面的表格：

這里的困難點在于graph的“邊”怎樣量化與取舍，依據(jù)多個“邊”與“節(jié)點”的綜合評分計算，以及與網(wǎng)絡(luò)挖掘分析結(jié)果的融合。

這部分的算法研發(fā)中，產(chǎn)出了如下的數(shù)據(jù)附產(chǎn)品：

2. Content-based 推薦算法

Content-based 是微博推薦中最常用也是最基礎(chǔ)的推薦算法，它的主要技術(shù)環(huán)節(jié)在于候選集的內(nèi)容結(jié)構(gòu)化分析和相關(guān)性運算。

正文頁相關(guān)推薦是content-based 應(yīng)用最廣的地方，以它為例，簡要的說一下

內(nèi)容分析的很多點已在前面描述過了，這里重點說2個地方：

• 內(nèi)容質(zhì)量分析，主要采用微博曝光收益+內(nèi)容信息量/可讀性的方法來綜合計算。微博曝光收益是借助用戶群體行為，衡量內(nèi)容優(yōu)劣；內(nèi)容信息量計算比較簡單，即是微博關(guān)鍵詞的idf信息迭代；對于內(nèi)容可讀性的衡量，我們做了一個小的分類模型，分別以可讀性較好的新聞?wù)Z料和可讀性較差的口語化語料為訓(xùn)練樣本，通過提取里面的各類詞搭配信息，計算新微博具有良好可讀性的概率。
• 詞擴展，content-based的效果取決于內(nèi)容分析的深度。微博的內(nèi)容比較短，可提取的關(guān)鍵信息比較少，做相關(guān)運算時容易因為數(shù)據(jù)稀疏而導(dǎo)致推薦召回率和準(zhǔn)確率的難以權(quán)衡；我們引入word2vec技術(shù)，優(yōu)化了詞擴展效果，后面又以此為基礎(chǔ)開展詞聚類的工作，實現(xiàn)了推薦召回率和準(zhǔn)確率的同步提升。

相關(guān)計算的技術(shù)點在于向量的量化和距離度量，我們通常使用“tf*idf權(quán)重量化 + 余弦距離”或者“topic 概率 + KLD距離“的兩種方法。

3. Model-based 推薦算法

微博作為中國最大的社會化媒體產(chǎn)品，具有海量的用戶和信息資源；這就給推薦帶來了2個挑戰(zhàn)：

來源融合與排序

候選的極大豐富，意味著我們有更多的選擇，于是我們推薦結(jié)果的產(chǎn)生包含兩層：多種推薦算法的初選與來源融合排序的精選，為了得到更客觀準(zhǔn)確的排序結(jié)果，我們需要引入機器學(xué)習(xí)模型，來學(xué)習(xí)隱藏在用戶群體行為背后的規(guī)律。

內(nèi)容動態(tài)分類和語義相關(guān)

微博UGC的內(nèi)容生產(chǎn)模式，以及信息快速傳播和更新的特點，意味著之前人工標(biāo)注樣本，訓(xùn)練靜態(tài)分類模型的方法已經(jīng)過時了，我們需要很好的聚類模型把近期的全量信息聚合成類，然后建立語義相關(guān)，完成推薦。

Model-based 算法就是為了解決上述的問題，下面是我們兩塊最重要的機器學(xué)習(xí)工作：

3.1 CTR/RPM（每千次推薦關(guān)系達成率）預(yù)估模型，采用的基本算法為Logistic regression，下面是我們CTR預(yù)估模型整體的架構(gòu)圖：

這部分工作包含樣本選擇、數(shù)據(jù)清洗、特征提取與選擇、模型訓(xùn)練、在線預(yù)估和排序。值得一提的是，模型訓(xùn)練前的數(shù)據(jù)清洗和噪音剔除非常重要，數(shù)據(jù)質(zhì)量是算法效果的上界，我們之前就在這個地方吃過虧。

Logisitic regression是一個2分類概率模型

優(yōu)化的目標(biāo)在于最大化“樣本正確分類概率的連乘值“；我們借助yahoo 研發(fā)的vowpal_wabbit機器學(xué)習(xí)平臺來完成模型特征值求解的最優(yōu)化過程。

3.2 LFM（Latent Factor Model）：LDA、矩陣分解（SVD++、SVD Feature）

LDA是2014年初重點開展的項目，現(xiàn)在已經(jīng)有了較好的產(chǎn)出，也在推薦線上產(chǎn)品中得到了應(yīng)用；LDA本身是一個非常漂亮和嚴謹?shù)臄?shù)學(xué)模型，下面是我們一個LDA topic的例子，僅供參考。

至于矩陣分解，2013年的時候做過相應(yīng)的嘗試，效果不是特別理想，沒有繼續(xù)投入。

隱語義模型是推薦精度最高的單一模型，其困難在于數(shù)據(jù)規(guī)模大時，計算效率會成為瓶頸；我們在這個地方開展了一些工作，后續(xù)會有同學(xué)專門介紹這一塊。

混合技術(shù)

三個臭皮匠頂個諸葛亮，每一種方法都有其局限性，將不同的算法取長補短，各自發(fā)揮價值，是極為有效的方式。微博推薦算法主要采用了下面的混合技術(shù)：

時序混合：

即在推薦過程的不同時間段，采用不同的推薦算法；以正文頁相關(guān)推薦為例，在正文頁曝光的前期階段，采用content-based + ctr預(yù)估的方法生成推薦結(jié)果，待產(chǎn)生的足量可信的用戶點擊行為后，再采用user-based 協(xié)同過濾的方法得到推薦結(jié)果，如下圖所示：

這樣利用content-based很好的解決了冷啟動的問題，又充分發(fā)揮了user-based CF的作用，實現(xiàn)1+1>2的效果。

分層模型混合：

很多情況下，一個模型無法很好的得到想要的效果，而分層組合往往會取得比較好的效果，分層模型混合即“將上一層模型的輸出作為下層模型的特征值，來綜合訓(xùn)練模型，完成推薦任務(wù)“。比如我們在做微博首頁右側(cè)的ctr預(yù)估排序時，采用分層邏輯回歸模型，解決了不同產(chǎn)品間特征天然缺失與樣本量差異、曝光位置帶來的效果偏差等問題。

瀑布型混合：

這類混合技術(shù)思路非常簡單，即在推薦候選非常豐富的情況下，采用逐層過濾的方法的得到推薦結(jié)果，通常將運算快、區(qū)分度低的算法放在前面，完成大量候選集的篩選；將運算慢、區(qū)分度高的算法放在后面，精細計算剩下的小規(guī)模集合。這類混合在微博推薦中大量使用，我們采用各種輕量算法完成候選集粗選，然后采用ctr預(yù)估做精細化排序。

交叉混合：

各類推薦算法中子技術(shù)，可以在另外的推薦算法中綜合使用，比如content-based在相關(guān)性計算中積累的距離計算方法，可以很好的應(yīng)用在協(xié)同過濾的量化計算中。實際的例子，我們將研究LDA時積累的向量計算方法成功的應(yīng)用到用戶推薦中。

Online 與 offline

微博數(shù)據(jù)的特點（海量、多樣、靜態(tài)與動態(tài)數(shù)據(jù)混在一起），決定了大部分推薦產(chǎn)品的結(jié)果需要同時借助online和offline的計算來完成。從系統(tǒng)和算法設(shè)計的角度，這是一個“重”與“輕”的問題，計算分解和組合是關(guān)鍵，我們需要將對時間不敏感的重型計算放在offline端，而將時間敏感性強的輕型快速計算放在online端。幾種我們常用的方式如下圖：

Online需要簡單可靠的算法，快速得到結(jié)果；簡要說明下上面的圖，如下

半成品有以下的3中形式

1）計算過程拆解的離線部分，如user-based CF中的用戶相似度，online通過數(shù)據(jù)庫讀取后在線計算完成user-based 推薦。

2）離線挖掘的優(yōu)質(zhì)候選集，如正文頁相關(guān)推薦的內(nèi)容候選集，online通過索引獲取到數(shù)據(jù)后，再通過相關(guān)性和ctr預(yù)估排序生成推薦結(jié)果。

3）具有較高相似度的推薦結(jié)果集，如offline計算好粉絲相似高的用戶，在線對用戶行為做出實時反饋，實時補充推薦與其剛關(guān)注用戶相似的用戶。

• 靜態(tài)推薦結(jié)果，是指那些與時間關(guān)聯(lián)小的推薦item，如我們的用戶推薦95%的結(jié)果來自離線計算。
• 機器學(xué)習(xí)模型，這是一個計算過程時序性上的拆解；offline完成模型的訓(xùn)練，在線調(diào)用model完成item排序，當(dāng)然也可以通過online-learning或?qū)崟r特征值完成模型的實時更新。同時，model在線計算時，需要注意缺失特征值的補全，保證offline與online環(huán)境的一致性。

此外，我們也有直接online計算完成的推薦結(jié)果，如首頁右側(cè)話題推薦，由于用戶對話題需求的差異非常小，它基本上是一個排行榜的需求，但熱門微博也可以有精巧的設(shè)計，我們采用了一個曝光動態(tài)收益模型，通過上一段時段的（點擊收益-曝光成本）來控制下一時段的item曝光幾率，取得了非常好的效果，ctr和導(dǎo)流量有3倍以上的提升。

不同類型的推薦結(jié)果，要輔以不同的推薦理由，這一點需要前端的多種展示嘗試和offline的日志分析。

效果評測

算法效果的度量方式?jīng)Q定了大家努力的方向，而對于不同類型的推薦，最好根據(jù)產(chǎn)品的定位和目標(biāo)，采用不同的標(biāo)準(zhǔn)體系去衡量工作結(jié)果。實際效果的評測分為3個層次：用戶滿意度、產(chǎn)品層指標(biāo)（如ctr）、算法層指標(biāo)，我們的效果評測也會分為人工評測、線上A/B測試、離線算法效果評測3種。

產(chǎn)品指標(biāo)的制定，應(yīng)該從產(chǎn)品期望達成的目標(biāo)出發(fā)，體現(xiàn)用戶滿意度。

對算法離線評測而言，關(guān)鍵的是找到一套合理的算法評測指標(biāo)去擬合產(chǎn)品層指標(biāo)，因為算法離線評測總是在上線前進行，這個對應(yīng)做的越好，算法的優(yōu)化成果才能更好的轉(zhuǎn)化為線上的產(chǎn)品指標(biāo)。

下圖為我們的算法離線效果評測的架構(gòu)圖

常用的離線評測指標(biāo)有：RMSE、召回率、AUC、用戶內(nèi)多樣性、用戶間多樣性、新穎性等。對于不同的產(chǎn)品有不同的組合指標(biāo)去衡量，比如用戶推薦中“用戶間多樣性”非常重要，而熱點話題卻可以允許用戶間有較大的結(jié)果重合度。