（讀論文）推薦系統之ctr預估-LR與GBDT+LR模型解析

本人才疏學淺，不足之處歡迎大家指出和交流。

本系列接下來要分享的文章是關于線性模型的，在15年後深度模型在ctr預估領域百花齊放之時，仍覺得傳統的LR模型有着基石的作用，于是有了今天的分享。話不多說，今天會介紹的是經典的LR模型及Facebook在2014年提出的GBDT+LR（重點）。當時深度學習幾乎還沒有應用到到計算廣告/推薦系統領域，Facebook提出利用GBDT的葉節點編号作為非線性特征的表示，或者說是組合特征的一種方式，可以自動實作特征工程，下面我們一起來看看吧。

兩篇原文：

1. Predicting Clicks: Estimating the Click-Through Rate for New Ads
2. Practical Lessons from Predicting Clicks on Ads at Facebook

1、背景

這裡是微軟研究院在當時提出LR模型時的商業背景：搜尋引擎主要靠商業廣告收入，在廣告位上面打廣告，使用者點選，之後廣告商付費。在通用搜尋引擎，通常廣告位置是在搜尋結果之前，或者在搜尋結果右邊，由此為查詢選擇正确的廣告及其展示順序會極大地影響使用者看到并點選每個廣告的機率。此排名對搜尋引擎從廣告中獲得的收入産生了很大影響。此外，向使用者展示他們喜歡點選的廣告也會提高使用者滿意度。出于這些原因，能夠準确估計系統中廣告的點選率非常重要(樸素的想法即是放使用者可能點選的廣告，并且放每次點選廣告商付費多的廣告)。

于是就歸結到點選率預估的模型選擇和特征工程問題。

2、LR Model

2.1 LR的數學基礎

為何在2012年之前LR模型占據了計算廣告領域的極大部分市場呢，我們可以從數學角度稍作分析：

邏輯回歸（logistics regression）作為廣義線性模型的一種，它的假設是因變量y服從伯努利分布。那麼在點選率預估這個問題上，“點選”這個事件是否發生就是模型的因變量y。而使用者是否點選廣告這個問題是一個經典的擲偏心硬币（二分類）問題，是以CTR模型的因變量顯然應該服從伯努利分布。是以采用LR作為CTR模型是符合“點選”這一事件的實體意義的。

在了解這一基礎假設的情況下，再來看LR的數學形式就極具解釋性了：

其中x是輸入向量，θ 是我們要學習的參數向量。結合CTR模型的問題來說，x就是輸入的特征向量，h(x)就是我們最終希望得到的點選率。

2.2、樸素的直覺和可解釋性

直覺來講，LR模型目标函數的形式就是各特征的權重和，最後再加以sigmoid函數。忽略其數學基礎，僅靠我們的直覺認知也可以一定程度上得出使用LR作為CTR模型的合理性：

使用各特征的權重和是為了綜合不同特征對CTR的影響，而由于不同特征的重要程度不一樣，是以為不同特征指定不同的權重來代表不同特征的重要程度。最後要加上sigmoid函數，是希望其值能夠映射到0-1之間，使其符合CTR的機率意義。

對LR的這一直覺（或是主觀）認識的另一好處就是模型具有極強的可解釋性，算法工程師們可以輕易的解釋哪些特征比較重要，在CTR模型的預測有偏差的時候，也可以輕易找到哪些因素影響了最後的結果。

2.3、工程化的需要

在工業界每天動辄TB級别的資料面前，模型的訓練開銷就異常重要了。在GPU尚未流行開來的2012年之前，LR模型也憑借其易于并行化、模型簡單、訓練開銷小等特點占據着工程領域的主流。囿于工程團隊的限制，即使其他複雜模型的效果有所提升，在沒有明顯beat LR之前，公司也不會貿然加大計算資源的投入更新CTR模型，這是LR持續流行的另一重要原因。

3、GBDT+LR Model

這篇文章（原文2）主要介紹了CTR預估模型LR(Logistic Regression)+GBDT。當時深度學習還沒有應用到計算廣告領域，而在此之前為探索特征交叉而提出的FM（見本系列第一篇）和FFM（本系列忘寫了...）雖然能夠較好地解決資料稀疏性的問題，但他們仍停留在二階交叉的情況。如果要繼續提高特征交叉的次元，不可避免的會發生組合爆炸和計算複雜度過高等問題。在此基礎上，2014年Facebook提出了基于GBDT+LR組合模型的解決方案。簡而言之，Facebook提出了一種利用GBDT（Gradient Boosting Decision Tree）自動進行特征篩選群組合，進而生成新的離散特征向量，再把該特征向量當作LR模型輸入，預估CTR的模型結構。随後Kaggle競賽也有實踐此思路，GBDT與LR融合開始引起了業界關注。

LR+GBDT相比于單純的LR或者GBDT帶來了較大的性能提升，論文中給出資料為3%，這在CTR預估領域确實非常不錯。除此之外，Facebook還在線上學習、Data freshness、學習速率、樹模型參數、特征重要度等方面進行了探索（本文不做讨論，有興趣可參閱原文）。Online Learning是本文的一個重點，接下來我們會提到。

3.1、GBDT

GBDT 由多棵 CART 樹組成，本質是多顆回歸樹組成的森林。每一個節點按貪心分裂，最終生成的樹包含多層，這就相當于一個特征組合的過程。根據規則，樣本一定會落在一個葉子節點上，将這個葉子節點記為1，其他節點設為0，得到一個向量。論文中如下圖所示：有兩棵樹，第一棵樹有三個葉子節點，第二棵樹有兩個葉子節點。如果一個樣本落在第一棵樹的第二個葉子，将它編碼成 [0, 1, 0]。在第二棵樹落到第一個葉子，編碼成 [1, 0]。是以，輸入到 LR 模型中的向量就是 [0, 1, 0, 1, 0]。

需要注意的一點是：利用 GBDT 模型進行自動特征組合和篩選是一個獨立（獨立于LR訓練）的過程，于是乎這種方法的優點在于兩個模型在訓練過程中是獨立進行的，不需要進行聯合訓練，自然也就不存在如何将LR的梯度回傳到GBDT這類複雜的問題。

然而，還有兩個重要問題是為什麼建樹采用GBDT以及為什麼要使用內建的決策樹模型，而不是單棵的決策樹模型呢？

對于第二個問題，我們可以認為一棵樹的表達能力很弱，不足以表達多個有區分性的特征組合，多棵樹的表達能力更強一些，可以更好的發現有效的特征和特征組合。

對于第一個問題，牽涉到GBDT原理問題，這裡不做過多讨論，請參考兩篇網上寫的較好的文章：

1. GBDT詳解。
2. 機器學習算法GBDT。

3.2、GBDT+LR總結

由于決策樹的結構特點，事實上，決策樹的深度就決定了特征交叉的次元。如果決策樹的深度為4，通過三次節點分裂，最終的葉節點實際上是進行了3階特征組合後的結果，如此強的特征組合能力顯然是FM系的模型不具備的。但由于GBDT容易産生過拟合，以及GBDT這種特征轉換方式實際上丢失了大量特征的數值資訊，是以我們不能簡單說GBDT由于特征交叉的能力更強，效果就比FM或FFM好（事實上FFM是2015年提出的）。在模型的選擇和調試上，永遠都是多種因素綜合作用的結果。

GBDT+LR比FM重要的意義在于，它大大推進了特征工程模型化這一重要趨勢，某種意義上來說，之後深度學習的各類網絡結構，以及embedding技術的應用，都是這一趨勢的延續。

4、Online Learning

論文中的線上模型可以做到：

GBDT可以一天或者幾天來訓練一次

LR可以實作線上學習online learning，幾乎是實作實時的訓練

接下來我們就詳細介紹一下其使用的online data joiner系統：這個名字主要是來自于，這裡最關鍵的步驟就是把labels(click/no-click)和訓練輸入(ad impressions)以一種線上的方式連起(join)起來。是以系統被稱為online data joiner。

4.1 label标注

首先設定一個足夠長的門檻值。一個廣告展示給使用者之後，如果使用者在門檻值的時間内沒有點選廣告就标記為no-click，點選了的話就标記為click。這個等待的時間視窗需要非常小心的調整。

如果太長了，會增加緩存impression的記憶體消耗，而且影響實時資料的産生；如果太短了則會導緻丢失一部分的點選樣本，會影響click converage。

click converage 點選覆寫表示有多少個點選行為被記錄了下來生成了樣本。online data joiner必須保證盡可能高的點選覆寫，也就是盡可能多的來記錄下來所有的點選行為。但是如果等待太久就會增加緩存開銷等影響。是以online data joiner必須在click converage和資源消耗之間做出平衡，又一個trade-off。

如果點選覆寫比較低，意味着很多使用者的點選不但沒有記錄下來，而是變成了沒有點選。造成資料分布發生偏差，結果就是：模型學習到的CTR值要比真實值低很多。不過實際情況中，問題比較好解決：增大等待時間視窗，隻要記憶體消耗還可以接受就行。

4.2 模型架構

online data joiner系統結構如下：

廣告展示生成特征，使用者給出回報：點選或者未點選。Online Joiner捕獲回報生成新的訓練樣本，訓練樣本經過Trainer的學習得到新的模型。模型反過來影響Ranker系統對展示的廣告進行選擇排序，使用者又看到了新的廣告，決定是否要點選。一直這樣下去，形成一個閉環系統。

4.3 挑戰

系統異常是線上學習系統的一大挑戰。這裡的異常就是指系統異常，比如系統出現問題導緻stream data是老資料。可能分類器就會學習到錯的資料，針對所有的點選率都給出一個非常低甚至是0的機率。這顯然不是我們想看到的。可以依靠一些保護機制來解決，比如：當發現實時的訓練資料分布發生比較大變化的時候，就把onliner trainer和online joiner自動斷開，防止Trainer學習到壞的資料分布。

5、總結（具體的對比實驗和實作細節等請參閱原論文）

本次簡要介紹了傳統的LR模型，其優點和缺點都非常突出，但不可否認的是其基石般的作用和地位。同時我們也介紹了GBDT+LR的改進方案以解決特征組合的問題，但GBDT也存在很容易過拟合的問題，接下來這段話摘自于知乎：

這裡是引用阿裡的蓋坤大神的回答，他認為GBDT隻是對曆史的一個記憶罷了，沒有推廣性，或者說泛化能力。

番外：蓋坤大神的團隊在2017年提出了兩個重要的用于CTR預估的模型，MLR（實際開始應用于2012年）和DIN，後面的線性模型和深度模型也會更新這兩篇，下篇再見吧~

實作GBDT+LR的一個Demo，感興趣的童鞋可以看下我的[github](https://link.zhihu.com/?target=https%3A//github.com/Jesse-csj/TensorFlow_Practice。

巨人的肩膀：https://blog.csdn.net/shenziheng1/article/details/89737467