广义线性模型的流式学习

ゞ浴缸里的玫瑰 2022-08-10 17:53 223阅读 0赞

# 广义线性模型的流式学习 #

--------------------

# 1. 广义线性模型的组成 #

在这篇博客中，我们将介绍机器学习中最常用的一大类模型：**广义线性模型**。广义线性模型包含线性模型、逻辑斯特回归、岭回归、Lasso等。这几种模型在spark中均有实现，然而，还未有基于spark streaming的流式算法。

# 2. 本文符号 #

假设我们有n个数据，分别为![chart_cht_tx_chl_24d_1_2Cd_2_2C...d_n_24][]，每个数据的维度为k，在广义线性模型中，我们将这n个数据集中到一个矩阵![chart_cht_tx_chl_24A_20_5Cin_20R_5E_7Bn_20_5Ctimes_20k_7D_24][]中，其中A的每一行为一个数据。每个数据对应的标签为![chart_cht_tx_chl_24y_1_2Cy_2_2C..._2Cy_n_24][]，注意每个标签是一个(0,1)的数，我们把这n个数集合到一个向量![chart_cht_tx_chl_24y_20_5Cin_20R_5E_7Bn_7D_24][]中。另外，我们假设广义线性模型中需要学习的参数为x，由于是线性模型，因此x的维度也是n。

# 3. 线性模型 #

在线性模型中，我们假设![chart_cht_tx_chl_24y_3DAx_20_2B_20_5Cepsilon_24][]，其中![chart_cht_tx_chl_24_5Cepsilon_24][]是一个服从高斯分布的误差项。根据最大似然概率准则，我们需要通过优化以下问题来得到x

![chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5C_7CAx-y_5C_7C_2_5E2_24_24][]

这也是一个线性最小二乘问题。由于这是一个L2的优化问题，因此可以通过梯度下降来求解。上述目标优化问题关于参数$x$的梯度为

![chart_cht_tx_chl_24_24_5Cnabla_20f_28x_29_3DA_5ET_20_28Ax-y_29_24_24][]

梯度下降的更新步骤为

![chart_cht_tx_chl_24_24x_5Et_20_3D_20x_5E_7Bt-1_7D-step_5Cnabla_20f_28x_29_24_24][]

# 4. 逻辑斯特回归 #

逻辑斯特回归我们已经在之前的博客上详细介绍，[请戳][Link 1]。

# 5. 岭回归 #

岭回归也是一种线性模型，它的模型为

![chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5Cfrac_7B1_7D_7Bn_7D_5C_7CAx_20-_20y_5C_7C_2_5E2_2B_5Clambda_20_5C_7CLx_5C_7C_2_5E2_24_24][]

其中n是数据的个数，![chart_cht_tx_chl_24_5Clambda_24][]是正则项的权重，L是一个矩阵，通常取为单位阵I。之所以在第一项前面乘以1/n，是为了保证![chart_cht_tx_chl_24_5Clambda_24][]不需要随着数据量而改变。岭回归对x加入了一个正则项，要求其能量尽量小。对岭回归的目标优化函数求梯度，就可以使用梯度下降法来求解。其梯度为

![chart_cht_tx_chl_24_24_5Cnabla_20f_28x_29_20_3D_20_5Cfrac_7B1_7D_7Bn_7DA_5ET_28Ax-y_29_2B_5Clambda_20L_5ETLx_24_24][]

# 6. Lasso模型 #

Lasso是一个L1正则化的问题，相对于一般的L2正则化问题，Lasso可以得到稀疏的解，在机器学习中能得到比L2正则化更好的结果。Lasso问题的形式是：

![chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5C_7Cy_20-_20Ax_5C_7C_2_5E2_20_2B_20_5Clambda_20_5C_7Cx_5C_7C_1_24_24][]

在机器学习中，$x$是我们要学习的模型参数，前一项是对训练数据的拟合，后一项是对模型参数的正则化（regularization）。

Lasso问题是一个凸问题，可以求得全局最优解。但是![chart_cht_tx_chl_24_7C_7Cx_7C_7C_1_24][]在x=0时是不可导的，所以它没有梯度，只有次梯度，因此不能直接使用梯度下降法来最优化。

## Huber Function ##

为了解决上述问题，我们可以使用Huber Function对![chart_cht_tx_chl_24_7C_7Cx_7C_7C_1_24][]在x=0处进行平滑，也就是用如下的Huber Function来代替![chart_cht_tx_chl_24_7C_7Cx_7C_7C_1_24][].

![img2.gif][]

画出Huber Function 可以看到

![Huber Function][]

可以看到其在![chart_cht_tx_chl_24_5B-_5Cepsilon_2C_5Cepsilon_5D_24][]处是平滑的,并且它可以看做是![chart_cht_tx_chl_24_7C_7Cx_7C_7C_1_24][]函数的近似。

现在Lasso问题可以近似为：

![chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5C_7Cy_20-_20Ax_5C_7C_2_5E2_20_2B_20_5Clambda_20H_7B_5Cepsilon_7D_28x_29_24_24][]

要用梯度下降法解决上述问题，需要对![chart_cht_tx_chl_24H_7B_5Cepsilon_7D_28x_29_24][]求导，Huber Function是一个分段函数，它的导数为

![Center][]

其中sign(x)函数是对x取符号运算。现在我们可以得到近似后的Lasso问题的目标优化函数的梯度为

![chart_cht_tx_chl_24_24_5Cnabla_20f_20_3D_20_20-_20_7BA_5ET_7D_5Cleft_28_20_7By_20-_20Ax_7D_20_5Cright_29_20_2B_20_5Clambda_20_7BH_5Cvarepsilon_20_7D_5Cleft_28_20x_20_5Cright_29_24_24][]

将上述的广义线性模型使用我们在之前的[博客][Link 1]中提到的方法进行流式学习，即可得到这些广义线性模型基于spark streaming的流行机器学习。

[chart_cht_tx_chl_24d_1_2Cd_2_2C...d_n_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24d_1%2Cd_2%2C...d_n%24
[chart_cht_tx_chl_24A_20_5Cin_20R_5E_7Bn_20_5Ctimes_20k_7D_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24A%20%5Cin%20R%5E%7Bn%20%5Ctimes%20k%7D%24
[chart_cht_tx_chl_24y_1_2Cy_2_2C..._2Cy_n_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24y_1%2Cy_2%2C...%2Cy_n%24
[chart_cht_tx_chl_24y_20_5Cin_20R_5E_7Bn_7D_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24y%20%5Cin%20R%5E%7Bn%7D%24
[chart_cht_tx_chl_24y_3DAx_20_2B_20_5Cepsilon_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24y%3DAx%20%2B%20%5Cepsilon%24
[chart_cht_tx_chl_24_5Cepsilon_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%5Cepsilon%24
[chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5C_7CAx-y_5C_7C_2_5E2_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24%5Carg%5Cmin_x%20%5C%7CAx-y%5C%7C_2%5E2%24%24
[chart_cht_tx_chl_24_24_5Cnabla_20f_28x_29_3DA_5ET_20_28Ax-y_29_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24%5Cnabla%20f%28x%29%3DA%5ET%20%28Ax-y%29%24%24
[chart_cht_tx_chl_24_24x_5Et_20_3D_20x_5E_7Bt-1_7D-step_5Cnabla_20f_28x_29_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24x%5Et%20%3D%20x%5E%7Bt-1%7D-step*%5Cnabla%20f%28x%29%24%24
[Link 1]: http://blog.csdn.net/zhangyuming010/article/details/38032629
[chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5Cfrac_7B1_7D_7Bn_7D_5C_7CAx_20-_20y_5C_7C_2_5E2_2B_5Clambda_20_5C_7CLx_5C_7C_2_5E2_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24%5Carg%5Cmin_x%20%5Cfrac%7B1%7D%7Bn%7D%5C%7CAx%20-%20y%5C%7C_2%5E2%2B%5Clambda%20%5C%7CLx%5C%7C_2%5E2%24%24
[chart_cht_tx_chl_24_5Clambda_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%5Clambda%24
[chart_cht_tx_chl_24_24_5Cnabla_20f_28x_29_20_3D_20_5Cfrac_7B1_7D_7Bn_7DA_5ET_28Ax-y_29_2B_5Clambda_20L_5ETLx_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24%5Cnabla%20f%28x%29%20%3D%20%5Cfrac%7B1%7D%7Bn%7DA%5ET%28Ax-y%29%2B%5Clambda%20L%5ETLx%24%24
[chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5C_7Cy_20-_20Ax_5C_7C_2_5E2_20_2B_20_5Clambda_20_5C_7Cx_5C_7C_1_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24%5Carg%5Cmin_x%20%5C%7Cy%20-%20Ax%5C%7C_2%5E2%20%2B%20%5Clambda%20%5C%7Cx%5C%7C_1%24%24
[chart_cht_tx_chl_24_7C_7Cx_7C_7C_1_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%7C%7Cx%7C%7C_1%24
[img2.gif]: /images/20220810/5f63e0fb31304adb87cf70704ce53e5a.png
[Huber Function]: /images/20220810/bf60b71a1f2149808bc33fa9f9cbb2c9.png
[chart_cht_tx_chl_24_5B-_5Cepsilon_2C_5Cepsilon_5D_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%5B-%5Cepsilon%2C%5Cepsilon%5D%24
[chart_cht_tx_chl_24_24_5Carg_5Cmin_x_20_5C_7Cy_20-_20Ax_5C_7C_2_5E2_20_2B_20_5Clambda_20H_7B_5Cepsilon_7D_28x_29_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24%5Carg%5Cmin_x%20%5C%7Cy%20-%20Ax%5C%7C_2%5E2%20%2B%20%5Clambda%20H_%7B%5Cepsilon%7D%28x%29%24%24
[chart_cht_tx_chl_24H_7B_5Cepsilon_7D_28x_29_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24H_%7B%5Cepsilon%7D%28x%29%24
[Center]: /images/20220810/73c44e9d805b4e56833daedce4112735.png
[chart_cht_tx_chl_24_24_5Cnabla_20f_20_3D_20_20-_20_7BA_5ET_7D_5Cleft_28_20_7By_20-_20Ax_7D_20_5Cright_29_20_2B_20_5Clambda_20_7BH_5Cvarepsilon_20_7D_5Cleft_28_20x_20_5Cright_29_24_24]: http://chart.googleapis.com/chart?cht=tx&chl=%24%24%5Cnabla%20f%20%3D%20%20-%20%7BA%5ET%7D%5Cleft%28%20%7By%20-%20Ax%7D%20%5Cright%29%20%2B%20%5Clambda%20%7BH'_%5Cvarepsilon%20%7D%5Cleft%28%20x%20%5Cright%29%24%24