UniformML Paper3-MLR《Learning Piece-wise Linear Models from Large Scale Data for Ad Click》

1 Introduction

線性模型在實際應用中雖然高效溉箕，但是實際很多特征空間的分界面未必都是線性的拒炎，為了適應這樣的場景裹纳，我們一般會通過兩種方法：
1择葡、復雜的特征工程（人工制造出非線性組合的特征）

To help LR model catch the nonlinearity, feature engineering technique is explored, which is both time and humanity consuming

2、通過模型組合（引入非線性模型）

Another direction, is to capture the nonlinearity with well-designed models. Facebook (He et al. 2014) uses a hybrid model which combines decision trees with logistic regression. Decision tree plays a nonlinear feature transformation role, whose output is fed to LR model. However, tree-based method is not suitable for very sparse and high dimensional data

除了樹模型+LR剃氧，還有factorization machine (FM)敏储，但是一般只能解決2階問題，沒辦法解決更高階的非線性組合朋鞍。

為了解決上述問題虹曙，本文提出了一個新的模型Large Scale Piece-wise Linear Model(LS-PLM)

In this paper, we present a piece-wise linear model and its training algorithm for large scale data.

這是一個分而治之的策略算法（divide-and-conquer strategy）：先對空間進行劃分出多個區(qū)域，然后對每個區(qū)域采用線性模型

first divides the feature space into several local regions, then fits a linear model in each region, resulting in the output with combinations of weighted linear predictions.

這里的非線性就看多個區(qū)域的劃分機制番舆，如果劃分越細酝碳，那非線性的表征能力就越強。

在學習曲線導數(shù)的時候恨狈，我們知道疏哗，在一個極短的線段里，可以近似為直線禾怠。

本文提出的模型具有以下優(yōu)點：

非線性
支持大規(guī)模并行訓練
稀疏性

model sparsity is a practical issue for online serving in industrial setting. We show LS-PLM with L1 and L2,1 regularizer can achieve good sparsity.

我們先看個例子返奉，本文提出的模型對非線性的擬合能力

Example

2 模型細節(jié)

2.1 模型結(jié)構(gòu)

前面已經(jīng)提到贝搁，我們?yōu)榱吮碚鞣蔷€性關(guān)系，會把空間進行劃分芽偏，用多個線性模型表征非線性模型雷逆。模型的公式如下：
$p(y=1|x)=g(\sum_{j=1}^m\sigma{(u_j^Tx)}\eta(w_j^Tx))$
這里g里用了兩個函數(shù)來分別表征分而治之(dividing and fitting)的概念。
這里模型的參數(shù)
$\theta={u_1, u_2, ...,u_m, w_1, w_2, ..., w_m}$ 污尉，其中{u1, u2, ..., um}參數(shù)是dividing function
$\sigma(.)$ 的膀哲；{w1, w2, ..., wm}參數(shù)是fitting function $\eta(.)$ 的。
當給定自變量x被碗，我們的預測模型包含兩部分：第一部分是dividing函數(shù)某宪，負責把特征空間劃分成m個區(qū)域；第二部分fitting函數(shù)是給出各個區(qū)域空間的概率預測锐朴。外層的g()保證我們的輸出結(jié)果滿足概率定義兴喂。
本文對上述三個函數(shù)的定義如下：

define of function

個人理解：感覺這里借鑒了non-parametric algorithm，然后和參數(shù)學習組合焚志，比如算法局部加權(quán)線性回歸算法衣迷，但是局部加權(quán)線性回歸算法的在線計算復雜度會隨著樣本數(shù)量增加而增加，這了用了m固定區(qū)域來限制酱酬，保證了在線計算復雜度壶谒，而且也在一段區(qū)域內(nèi)進行參數(shù)化
如果我們再對這個函數(shù)拆成兩步，第一步是先通過m個logistic regression計算岳悟，第二步是根據(jù)第一步的計算結(jié)果再進行一次softmax佃迄。這個過程是不是和一個標準的2層神經(jīng)網(wǎng)絡一樣？

本文還指出該模型和如下模型是如出一轍的形式贵少。

image

有了模型定義呵俏，下面我們來說下?lián)p失函數(shù)的定義：

image

這里loss同樣采用 經(jīng)驗誤差+結(jié)構(gòu)誤差的模式，經(jīng)驗誤差同LR采用的是交叉熵滔灶，模型結(jié)構(gòu)誤差采用的是L1和L2組合

$||\theta||_{2,1}=\sum_{i=1}^3at2yt1\sqrt{\sum_{j=1}^{2m}\theta_{i,j}^2}$
$||\theta||_1=\sum_{ij}|\theta_{i,j}|$

2.2 模型優(yōu)化求解方法

正是由于引入了模型結(jié)構(gòu)誤差普碎，導致模型非凸非平滑

However, both L1 norm and L2,1 norm are non-smooth functions. This causes the objective function of Eq.(4) to be non-convex and non-smooth, making it difficult to employ those traditional gradient-descent optimization methods

作者為了他解決這個問題，提出新的求解方法(根據(jù)梯度方向來更新)

2.3 trick

本文模型在訓練的時候采用了一個common feature trick录平，我們在廣告曝光的時候麻车，對于同一個用戶在同一個頁面展示不同的廣告，這里曝光的每條訓練數(shù)據(jù)集的user斗这、context的feature都是一致的动猬，只有item的feature不一致，所以在懸鏈的時候可以進行預計算公用特征表箭，然后在計算不一致特征即可赁咙，能夠高效提升計算效率。當然對訓練數(shù)據(jù)集分組的時候就有要求，盡可能把帶有公共特征的數(shù)據(jù)放在一臺機器上彼水。
如下崔拥，我們把feature空間分乘兩部分： xc表示common feature， xnc表示非公共特征

feature重寫

3 實驗

從試驗結(jié)果來看凤覆，模型超參數(shù)m如果越多能夠提升模型的效果链瓦，但是對訓練復雜度也會加大

image