?

1.?前言

互聯(lián)網(wǎng)技術(shù)和大數(shù)據(jù)技術(shù)的迅猛發(fā)展正在時刻改變我們的生活，視頻網(wǎng)站、資訊app、電商網(wǎng)站等每天都有大量的活躍用戶在不斷的產(chǎn)生海量的用戶行為，同時，每天又都產(chǎn)生大量的新增PGC或者UGC內(nèi)容（如小說、資訊文章、短視頻等）。

從推薦系統(tǒng)的角度來看，系統(tǒng)每時每刻都面臨大量的新舊用戶、新舊物品和大量的用戶行為數(shù)據(jù)，對于用戶，我們需要對要用戶進行建模，去刻畫用戶的肖像和興趣，然而我們常常面對的情況是用戶的行為是稀疏的，而且可能存在比例不一的新用戶，如何給新用戶推薦，是推薦系統(tǒng)中的一個著名問題，即冷啟動問題，給新用戶展示哪些item決定了用戶的第一感和體驗；同時在推薦過程中，需要考慮給新item展示的機會，比如給一個喜歡科幻電影的user推薦一些非科幻類型的電影，提高推薦的多樣性，這就是推薦系統(tǒng)中另外一個問題，即探索和利用的問題。

2.?冷啟動和EE問題

推薦系統(tǒng)需要根據(jù)歷史的用戶行為和興趣偏好預測用戶未來的行為和興趣，因此歷史用戶行為某種程度上成為推薦推薦的重要先決條件。實際過程中，我們面對大量的新用戶，這些用戶我們并不知道他們的profile，對于這些用戶，常用的冷啟動的算法包括根據(jù)已有的個人靜態(tài)信息（年齡、性別、地理位置、移動設(shè)備型號等）為用戶進行推薦。然而實際情況下，很難在系統(tǒng)中直接獲取這些用戶信息。給新用戶推薦的item，由于成本較高（用戶不感興趣就再也不來了），我們需要保證item要足夠熱門，要保證足夠的多樣性，同時盡量保證可區(qū)分。

與用戶的冷啟動相對應的，則是item的冷啟動，當一個新物品加入站內(nèi)，如何快速的展現(xiàn)的用戶。特別是在某些場景下，推薦列表是給用戶展示的唯一列表，那么顯而易見，只能在推薦列表中嘗試給用戶推薦新物品。對于CF算法來說，無論是基于領(lǐng)域還是基于模型，如果想要這個新物品被推薦出來，顯然我們需要獲得用戶對這個物品的行為數(shù)據(jù)。一個最簡單的做法就是在推薦列表中隨機給用戶展示新物品，但是這樣顯然不太個性化。一個較好的做法是將新物品推薦給曾經(jīng)喜歡過與新物品相似物品的用戶。由于新item沒有用戶行為，因此物品相似度只能從item自身出發(fā)，包括根據(jù)item的內(nèi)容信息挖掘出item的向量表示，通過向量相似度來刻畫物品相似度，還可以利用topic model挖掘出item的主題分布等等。

推薦系統(tǒng)需要考慮對用戶興趣的不斷探索和細化，同時也需要盡可能的擴大展示物品的多樣性和寬度。比如極端情況下給用戶展示物品的場景只有推薦列表，同時我們需要盡可能優(yōu)化的ctr，那么給冷啟動用戶我們該如何選擇物品，如何快速的探測出用戶的興趣？

舉例來說，對于一個熱愛足球的足球迷我們該如何選擇給他推薦的物品？比較簡單的方式我們可以可以根據(jù)ctr排序，給冷啟動用戶推薦最熱門、點擊率最高的物品，給他推薦點擊率最高的足球相關(guān)物品，顯然這樣做會保證我們推薦結(jié)果的ctr會比較高，但是這樣做會減少我們推薦結(jié)果的覆蓋率，降低推薦結(jié)果的多樣性，以致于推薦物品候選集也會收斂，出現(xiàn)反復推薦。比如對于資訊來說，用戶看到的資訊都是點擊率較高的搞笑類，但是顯然“搞笑”并不能刻畫的興趣。我們達觀數(shù)據(jù)在實踐中一直在不斷探索用戶興趣，擴大推薦結(jié)果多樣性，原因正在于此。（達觀數(shù)據(jù) 文輝）

簡單來看這其實是一個選擇問題，即探索（exploration）和利用（exploitation）問題。接下來本文接下來將詳述EE問題和某些已有算法。

3.?多臂老虎機模型和UCB算法

當你走進一家賭場，面對20個一模一樣的老虎機，你并不知道它們吐錢的概率。假設(shè)你的成本是1000元，每搖一次的成本是2元，那么你在總共500次搖臂的機會下，該如何最大化你的收益呢？ 這就是多臂老虎機問題(Multi-armed bandit problem, K-armed bandit problem, MAB)。

一個簡單的做法就是每臺老虎機我們都搖10次，余下的300次都選擇成功率最高的那臺。但是顯然我們耗費了200次機會來探索，而且我們?nèi)匀粺o法保證實驗成功率最高的那臺老虎機就是真實成功率最高的。大家也可以猜到，如果我們有足夠多的探索機會，那么我們幾乎可以選擇出成功率最高的老虎機。很遺憾，我們沒有足夠的探索機會，對應到我們的推薦問題中就是任何的用戶展示pv都是珍貴的，況且實際情況的“老虎機”遠遠不止20臺，而且還存在不斷新加入的情況，這就導致獲取每個item收益率的成本太大。

我們達觀數(shù)據(jù)使用累計遺憾（collect regret）來衡量策略的優(yōu)劣：

t表示當前輪數(shù)，表示平均最大收益，表示?第t輪的實際收益。累計遺憾公式表明了實際累計收益和理想最佳收益的差值。為了簡單起見，我們假設(shè)每臺機器的收益為伯努利收益，即收益要么是0，要么是1。對應到推薦系統(tǒng)中，老虎機即對應我們的物品（item），每次搖臂即認為是該物品的一次展示，我們可以用是否點擊來表示收益，點擊(win)的收益就是1，沒有點擊(lose)的收益就是0。

解決bandit問題的算法眾多，一般分為基于semi-uniform的策略、probability matching 策略、pricing策略等。這里只列舉若干個策略，具體大家可以參考(https://en.wikipedia.org/wiki/Multi-armed_bandit)。

Epsilon-greedy策略：每次試驗都以的概率選擇前面試驗中平均收益最佳的item，以的概率等概率隨機選擇其他item，該策略簡單，而且可以通過

Epsilon-first策略：該策略探索和利用交叉選擇，總試驗次數(shù)為N，探索次數(shù)為，探索階段也是等概率隨機選擇所有item，利用階段也是選擇平均收益最好的機器。

Epsilon-decreasing策略：與Epsilon-greedy策略近似，不同地方在于隨著試驗的進行會不斷減少。（達觀數(shù)據(jù) 文輝）

UCB（Upper Confidence Bound）算法

在推薦系統(tǒng)中，通常量化一個物品的收益率（或者說點擊率）是使用，例如點擊為10，展示數(shù)為8，則估計的點擊率為80%，在展示數(shù)達到10000后，其表現(xiàn)ctr是否還能達到80%呢？ 顯然是不可能的。而這就是統(tǒng)計學中的置信度問題，計算點擊率的置信區(qū)間的方法也有很多，比如威爾遜置信空間（https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval#Wilson_score_interval）。UCB算法步驟包括：首先對所有item的嘗試一下，然后每次選擇以下值最大的那個item:

，其中是物品到目前的收益均值，本質(zhì)上是均值的標準差。t是目前的試驗次數(shù)，是這個item被試的次數(shù)。

這個公式表明隨著每個物品試驗次數(shù)的增加，其置信區(qū)間就越窄，收益概率就越能確定。如果收益均值越大，則被選中的機會就越大（exploit），如果收益均值越小，其被選中的概率也就越少，同時哪些被選次數(shù)較少的item也會得到試驗機會，起到了explore的作用。

Probability-matching策略表明一臺機器的選擇次數(shù)應當與它是最佳收益item的概率相同。其中Thompson采樣就是一種Probability-matching策略算法，該算法也是一個的在線學習算法，即通過不斷的觀察數(shù)據(jù)來更新模型參數(shù)。

Thompson采樣

Thompson采樣假設(shè)每個item的收益率為p，那么如何來估計一個item的收益概率p呢？直接用試驗結(jié)果的收益概率p是否合理呢？ 比如一個item給用戶展示了20次，用戶點擊了16次，那么我們可以認為這個item的收益率是80%嗎？而這顯然是不合理的，因為我們首先需要考慮的就是這個收益率的置信度，20次試驗得出的結(jié)果置信度小于試驗了10000次試驗的置信度，其次可能我們的經(jīng)驗表明所有item的平均收益率只有10%。

Thompson采樣使用Beta分布來描述收益率的分布（分布的布：?https://en.wikipedia.org/wiki/Beta_distribution），我們通過不斷的試驗來估計一個置信度較高的基于概率p的概率分布。假設(shè)概率p的概率分布符合Beta(wins, lose)，beta分布有兩個參數(shù)wins和lose，每個item都維護了beta分布的參數(shù)，每次試驗都選擇一個item，有點擊則wins增加1，否則lose增加1。每次選擇item的方式則是：用每個item的beta分布產(chǎn)生一個隨機數(shù)，選擇所有item產(chǎn)生的隨機數(shù)中的最大的那個item。Beta分布概率密度函數(shù)如下：

舉例來說，推薦系統(tǒng)需要試探新用戶的興趣，假設(shè)我們用內(nèi)容類別來表示每個用戶的興趣，通過幾次展示和反饋來獲取用戶的興趣。針對一個新用戶，使用Thompson算法為每一個類別采樣一個隨機數(shù)，排序后，輸出采樣值top N 的推薦item。獲取用戶的反饋，比如點擊。沒有反饋則更新對應類別的lose值，點擊了則更新對應類別的wins值。

4.?LinUCB算法?

回到推薦列表的場景，推薦系統(tǒng)為用戶推薦物品。user和item都可以用一系列特征表示。用戶特征包括用戶的統(tǒng)計歷史行為、人口學屬性信息；物品特征包括描述信息、類別信息等等。在這種場景下，探索和利用也必須是個體用戶級別上實施，因為不同用戶看到相同的物品的反饋差異較大。

LinUCB算法是一種基于上下文特征（用戶特征、物品特征）的UCB算法，基于特征進行探索和利用。該算法結(jié)合上下文特征，選擇給用戶的推薦物品，同時利用用戶反饋及時修正選擇策略，以達到最大化收益（提升點擊率）的目標。

使用互斥線性模型的LinUCB

LinUCB算法假設(shè)推薦item的每次展現(xiàn)收益（是否點擊）是和上下文特征成線性關(guān)系的，即：

其中表示用戶特征和物品特征的合集，表示第t次嘗試的收益，a表示item，表示物品a的位置系數(shù)向量?？梢钥闯龈鱾€item的模型參數(shù)是相互獨立的（互斥）。

設(shè)（d*m）表示為m個訓練上下文，表示每個上下文的實際收益，對訓練數(shù)據(jù)使用嶺回歸訓練出的物品a的參數(shù)為：

其中表示d*d的單位矩陣。其中在置信度下，模型收益與期望收益滿足：

其中，。

上述等式給出了物品a期望收益的一個UCB，因此也就引申出了UCB的選擇策略，對于第t次試驗，選擇以下式中最大值的物品，

其中。上述模型中預期收益的方差為，即為標準差。

以上為互斥線性模型LinUCB的基本算法流程，其中結(jié)合上述內(nèi)容，第一行參數(shù)控制了explore的程度，即越大，置信區(qū)間上限也就越大，也就加大了explore的程度；4-7行對于新物品，使用單位陣和0l向量進行參數(shù)初始化；8-9行計算item a的置信區(qū)間上限；11行選擇最優(yōu)item；12-13行更新選擇item的模型參數(shù)。

思想上LinUCB算法類似于對召回結(jié)果重排序的方法，也是考慮用戶和item的特征，來計算出收益最大的item，不同的是LinUCB借鑒了UCB的置信區(qū)間的方法來平衡exploit和explore問題，同時從LinUCB算法是一個在線的學習算法，與一般離線算法需要離線訓練不同，LinUCB隨著每次展示和反饋會不斷優(yōu)化模型參數(shù)和收益。（達觀數(shù)據(jù) 文輝）

關(guān)于LinUCB算法的介紹請參考論文http://rob.schapire.net/papers/www10.pdf?。

5.?CLUB算法

CLUB(online clustering bandits)算法假設(shè)將全部用戶劃分成若干個用戶群，每個用戶群對相同推薦內(nèi)容的反饋是一致的，同時自適應的調(diào)整用戶群。與liner bandit一樣，CLUB算法也是根據(jù)特征計算收益，不同的是CLUB算法中相同群體用戶共享相同的參數(shù)向量，即第i個用戶對item a的收益為：

其中表示第i個user，表示第i個user所屬的用戶群編號，表示每個用戶群的參數(shù)向量，x表示上文下特征，表示噪聲項。

該算法在時刻t，對于用戶i，維護一個向量的估計值。與liner bandit算法相似，根據(jù)收益反饋不斷更新。與LinUCB算法類似的，可以根據(jù)協(xié)方差矩陣（d*d維，初始化為單位陣）的逆和向量（d維向量，初始化為0向量）計算得出。除此之外，算法需要維護一個無向圖，每個節(jié)點表示一個user。算法首先從完全圖開始，根據(jù)的演化逐步移除節(jié)點之間的邊。定義第t時刻的用戶群個數(shù)為，，……表示時刻t的用戶劃分群。顯然初始狀態(tài)下=1，(全部用戶)。

在每個時刻t（1，2，……），用戶，相關(guān)上下文特征向量集合為，用戶所屬的群為。CLUB算法根據(jù)收益選擇item的式如下：

其中是通過同用戶群內(nèi)各個節(jié)點通過最小方差逼近擬合計算得出的聚合權(quán)重向量，CB為向量的置信區(qū)間上限。

CLUB算法觀察到item的收益后，更新協(xié)方差矩陣，更新；雖然不會更新其他節(jié)點的M和b，但是會隱式的影響下一輪的聚合權(quán)重向量；接下來判斷節(jié)點與相鄰節(jié)點的參數(shù)向量（）距離，如果足夠大，則將該邊移除。

CLUB算法的完整流程如下：

其中控制探索的程度，是用戶關(guān)系是否刪除的控制參數(shù)。上述算法流程包含了刪除關(guān)系邊的條件，其中是t時刻前歷史上i用戶被選中的次數(shù)。

CLUB算法首先提出了基于協(xié)同概念的bandit算法，即每次用戶預測對item收益是由這個所屬的群體的聚合權(quán)重向量參數(shù)所決定的，同時根據(jù)個人反饋更新個人參數(shù)，個人參數(shù)又隱式的影響群體參數(shù)和用戶群體的劃分。據(jù)CLUB算法論文介紹，在一些公共數(shù)據(jù)集中，取得了比LinUCB更好的效果，關(guān)于CLUB算法的更多細節(jié)請參考https://arxiv.org/abs/1401.8257。

6.?結(jié)束語

本文簡單介紹了推薦系統(tǒng)中一直存在的兩大問題：冷啟動和EE問題，并簡單闡述了業(yè)界解決這兩大問題的一些常見解決方法和算法。正如前文所說，EE問題某種程度中一直以矛盾共同體存在，在實際場景中，需要平衡兩者。

達觀數(shù)據(jù)長期致力于推薦系統(tǒng)的深度探索和研究，達觀個性化推薦引擎可以快速捕捉用戶新額興趣點，實時更新用戶模型，大幅提高推薦效果，同時利用大量的NLP技術(shù)和深度學習技術(shù)擴大推薦多樣性，避免內(nèi)容越推越窄，更多請參考http://35285.cn/recommend.html。本文時間有限，難免有偏頗之處，歡迎大家共同探討。