論文[Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction](arxiv.org/pdf/1704.0519)

==*定期更新,獲取更多,歡迎[star](AlexanLee/ads-papers)。另外歡迎關注[計算廣告實驗](AlexanLee/ads-ailab),我會總結一些實現。*==

#### 一、論文基本描述。

CTR預估由於是針對大規模非線性數據的機器學習存在很多的困難。

1. 本論文提出了一個新型的模型（LS-PLM）。

2. 利用`$L_1$`和`$L_{2,1}$`正則來解決學習問題，將會導致非凸和非光滑的優化問題。因此，為解決這個問題提出了一種基於方嚮導數和擬牛頓法的有效方法

3. 另外，設計了工業級的數百臺機器的模型訓練系統。

LS-PLM可以捕捉非線性的特徵數據，從而減少特徵工程的工作。從2012年這個模型就開始大規模應用到阿里巴巴的展示廣告預估上。

#### 二、解決方法、思想

點擊率預估是在線廣告的核心問題。傳統的方法是LR模型，LR模型利用`$L_1$`正則能生成稀疏解。實際上CTR預估是一個非線性的問題，用戶點擊涉及到流量質量，用戶興趣，上下文特徵，以及它們的交叉特徵。為瞭解決LR的非線性問題，需要做大量的特徵工程。另一方面，可以設計一些非線性模型，Facebook 利用決策樹?LR的方式。**但是樹形模型不適合非常稀疏的高緯特徵數據。FM能夠有效的解決特徵交叉的問題，但是，不能解決所有的數據非線性問題。**

本論文提出了一種基於大規模數據的分片線性回歸模型（LS_PLM）,**它是基於分治法的思想。首先將特徵空間分解為若干本地區域，然後針對每一個區域訓練一個線性模型，把最後所有線性模型預測的權重作為輸出結果**。有如下三個特點：

1. 非線性性。

2. 大規模性。巨大的樣本量，高緯特徵。

3. 稀疏性。利用`$L_1$`和`$L_{2,1}$`正則可以很好的獲得稀疏性。

模型公式:

預測`$p(y|x)$`需要考慮兩部分，第一部分`$sigma(mu_{j}^{T})$`將特徵空間分成m（超參數）個區域，第二部分`$eta(w_j^Tx)$`對每個區域進行預測。`$g(.)$`確保我們的模型滿足定義的概率函數。

特例,利用softmax作為分割函數，sigmoid作為預測函數，因此得到一個明確的表達式：

這裡的混合模型可以看作是一個FOE模型：

LS_PLM的目標函數：

這裡`$L_1$`和`$L_{2,1}$`都是非光滑函數，這造成目標函數是非凸、非光滑的，因此很難用傳統的梯度下降法和EM演算法。

##### 優化

引理1 當目標函數`$f( heta)$`是由非光滑的正則函數組成的時候，例如上邊提到的損失函數，那麼對任何的`$ heta$`和`$d$`那麼方嚮導數存在。

命題2 給定一個光滑損失函數和一個目標函數，有：

其中

***

優化演算法：

***

演算法：

類似於LBFGS,修改為：

1. 使用最小化非凸目標導數方向`$d(k)$`代替負梯度。

2. 更新方向取決於所選的方向`$d(k)$` 定義的。當`$H(k)$`不是正定時，切換到`$d(k)$`.

3. 在線性搜索時，每個搜索點都投影到前一點的orthant上。

##### 實現

並行計算：

兩個角色：工作節點，每個節點有部分的訓練數據和本地模型。第二個為服務節點，每個節點存放全部的參數，

通用的特徵技巧：

將特徵劃分為通用特徵和非通用特徵，

有三個方面：

1. 分組訓練通用特徵，確保這些樣本存儲在相同的工作節點上。

2. 對於多個樣本通用特徵只存儲一次。

3. 對於通用特徵更行損失函數和梯度只一次。

#### 三、評價指標

AUC。

#### 四、實驗

通常來說，較大的m需要較多的參數有較大模型容量，但是會導致訓練的成本增加。列舉了不同的分片，得到的不同的AUC值。最後得到12為最好的參數。

`$lambda$`和`$eta$`都取1.

目前實際測試實驗，採用FTRL優化的MLR模型比LR模型，可以穩定提升離線AUC2%左右。實際證明瞭其效果。

可參看[計算廣告實驗](AlexanLee/ads-ailab).

還有[Angel](Angel-ML/angel)的實現。

#### 五、使用&借鑒

典型的應用場景：

**基於 MLR 的定向廣告 CTR 預估演算法**

基於 MLR 演算法的非線性學習能力，阿里媽媽的定向廣告 CTR 預估採用了大規模原始ID 特徵 + MLR 演算法的架構。具體為刻畫一次廣告展現為特徵向量，它由三部分獨立構成：

1. 用戶部分特徵（包括 userid、profile 信息、用戶在淘寶平臺上的歷史行為特徵（瀏覽/購買過的寶貝/店鋪/類目上的 id 和頻次等）

2. 廣告部分特徵（包括 adid、campainid、廣告對應的賣家店鋪 id、類目 id 等）

3. 場景部分特徵（包括時間、位置、資源位等）

這些特徵之間無傳統的交叉組合，維度在 2 億左右。然後，他們將數據直接餵給 MLR 演算法，並且應用了結構化先驗、pretrain+ 增量訓練、線性偏置等高級技巧，讓模型從數據中自動去總結和擬合規律。相比於傳統的 LR+ 特徵工程思路，這種解法更為高效和優雅，模型精度更高，在實際生產中的可迭代更強。

**基於 MLR 的定向廣告 Learning to Match 演算法**

Match 演算法是定向廣告中的一個重要環節，它的核心使命是基於用戶的人口屬性、歷史行為等信息來猜測用戶可能感興趣的廣告集合。傳統的 Match 演算法更多採用的是規則匹配、協同過濾等方法，方法的擴展性不強。

在阿里媽媽定向廣告系統中，工程師研發了基於 MLR 的 learning to match 演算法框架。簡單來說，用模型的方法基於用戶的行為歷史來學慣用戶個性化的興趣，從而召回高相關性的候選廣告集。

同樣地，基於MLR演算法的非線性能力，可以很容易地將不同的特徵源、標籤體系融合到框架中，不需要過多地關注和設計特徵的交叉組合，使得框架的靈活性大大增強。

#### 六、參考&推薦

1. [Practical Lessons from Predicting Clicks on Ads at Facebook](quinonero.net/Publicati)

2. [mixed-effects logistic regression](idiom.ucsd.edu/~rlevy/l)


推薦閱讀：
相關文章