可扩展机器学习——线性回归（linear Regression）
可扩展机器学习——线性回归（linear Regression）
注：这是一份学习笔记，记录的是参考文献中的可扩展机器学习的一些内容，英文的PPT可见参考文献的链接。这个只是自己的学习笔记，对原来教程中的内容进行了梳理，有些图也是引用的原来的教程，若内容上有任何错误，希望与我联系，若内容有侵权，同样也希望告知，我会尽快删除。这部分本应该加上实验的部分，实验的部分在后期有时间再补上。
可扩展机器学习系列主要包括以下几个部分：
概述 - Spark分布式处理 - 线性回归(linear Regression) - 梯度下降(Gradient Descent) - 分类——点击率预测(Click-through Rate Prediction) - 神经科学
三、线性回归(linear Regression)
1、线性回归概述
回归(Regression)问题的目标是从观测样本中学习到一个到连续的标签值的映射，这是一个监督学习的问题。回归问题有：
- Height, Gender, Weight → Shoe Size
- Audio features → Song year
- Processes, memory → Power consumption
- Historical financials → Future stock price
- 等等
2、线性最小二乘回归
2.1、回归的基本概念
对于每一个观测样本，我们有特征向量x\mathbf{x}，样本标签y\mathbf{y}：
xT=[x1x2x3]
\mathbf{x}^T=\left [ x_1\; x_2\; x_3 \right ]
假设在特征与标签之间存在一个线性映射：
y=w0+w1x1+w2x2+w3x3
y=w_0+w_1x_1+w_2x_2+w_3x_3
在第一项称为偏置项(bias)，通过在特征中合并偏置项，得到下面的特征向量：
xT=[1x1x2x3]
\mathbf{x}^T=\left [1\; x_1\; x_2\; x_3 \right ]
此时，可以将上述的线性映射表示成向量的乘积：
y≈y^=∑i=03wixi=wTx
y\approx \hat{y}=\sum_{i=0}^{3}w_ix_i=\mathbf{w}^T\mathbf{x}
2.2、线性回归的优点
上述便是线性回归的基本形式，对于线性回归，有以下的一些优点：
- 简单
- 在实际中通常表现很好
- 通过对特征的提取，可以引进复杂的模型
2.3、线性回归的目标
线性回归的目标是找到一条直线或者称为超平面能够最好的拟合样本，如下面的1?D1-D的情况：
其中，xx轴表示的特征，yy轴表示的是标签。此时的线性映射为：
y≈y^=w0+w1x
y\approx \hat{y}=w_0+w_1x
2.4、线性回归的评价
线性回归的评价是指如何度量预测值(Prediction)与标签(label)之间的的接近程序，通常有一下的两种损失函数：
- 绝对损失(Absolute Loss)：
l=|y?y^|
l=\left | y-\hat{y} \right |
- 平方损失(Squared Loss)：
l=(y?y^)2
l=\left ( y-\hat{y} \right )^2
其中，平方损失有很好的数学特性：如处处可导。
2.5、线性模型的学习
假设有nn个训练样本，其中，x(i)\mathbf{x}^{\left ( i \right )}表示的是第ii个训练样本。假设使用的是线性模型：
y^=wTx
\hat{y}=\mathbf{w}^T\mathbf{x}
损失函数为均方损失函数，即：
(y?y^)2
\left ( y-\hat{y} \right )^2
则训练模型的目标是使得在所有的训练集上，找到特定的w\mathbf{w}，使得均方误差最小，即：
minw∑i=1n(wTx(i)?y(i))2
\underset{\mathbf{w}}{min}\sum_{i=1}^{n}\left ( \mathbf{w}^T\mathbf{x}^{\left ( i \right )}-y^{\left ( i \right )} \right )^2
2.6、线性回归模型的求解
假设有训练样本的个数为nn，特征的维数为dd，则对于样本中的数据，有如下的定义：
- X∈Rn×d\mathbf{X}\in \mathbb{R}^{n\times d}：矩阵存储样本及其特征
- y∈Rny\in \mathbb{R}^n：向量存储标签，每个值为实数
- y^∈Rn\hat {y}\in \mathbb{R}^n：预测的标签，y^=Xw\hat {y}=\mathbf{X}\mathbf{w}
- w∈Rd\mathbf{w}\in \mathbb{R}^d：模型的参数
最小均方回归(Least Squares Regression)：学习一个从特征到标签的映射(w\mathbf{w})，以使得残差的平方和最小，即 minw∥Xw?y∥22 \underset{\mathbf{w}}{min}\left \| \mathbf{X}\mathbf{w}-y \right \|^2_2
上述的残差的平方和最小等价于下述的形式：
minw∑i=1n(wTx(i)?y(i))2
\underset{\mathbf{w}}{min}\sum_{i=1}^{n}\left ( \mathbf{w}^T\mathbf{x}^{\left ( i \right )}-y^{\left ( i \right )} \right )^2
求上述问题的最小值，可以等价于求函数f(w)f\left ( w \right )的最小值，其中，函数f(w)f\left ( w \right )为：
f(w)=∥wx?y∥22=∑i=1n(wx(i)?y(i))2
f\left ( w \right )=\left \| w\mathbf{x}-y \right \|^2_2=\sum_{i=1}^{n}\left ( wx^{\left ( i \right )}-y^{(i)} \right )^2
对于上述的优化函数，可以使用让其导数为00的情况求其最优解，即：
dfdw(w)=2∑i=1nx(i)(wx(i)?y(i))=0?wxTx?xTy=0?w=(xTx)?1xTy
\begin{matrix} \frac{df}{dw}\left ( w \right )=2\sum_{i=1}^{n}x^{(i)}\left ( wx^{(i)}-y^{(i)} \right )=0\\ \Leftrightarrow w\mathbf{x}^T\mathbf{x}-\mathbf{x}^Ty=0\\ \Leftrightarrow w=\left ( \mathbf{x}^T\mathbf{x} \right )^{-1}\mathbf{x}^Ty \end{matrix}
这样，便求出了模型的最优解，存在这样的解的前提是矩阵的逆存在：
w=(XTX)?1XTy
\mathbf{w}=\left ( \mathbf{X}^T\mathbf{X} \right )^{-1}\mathbf{X}^Ty
2.7、过拟合和泛化能力
求解模型的目的是要使用模型，即在新的数据集上使用模型，若其能在新的数据集上表现的很好，说明求解出的模型具有很好的泛化能力(Generalization ability)。最小均方回归容易导致过拟合，因为其对训练数据过分拟合。过拟合的情况如下图所示：
简单的模型通常更具有泛化能力(Occam剃刀)。
为了使得模型具有更好的泛化能力，我们需要降低模型的复杂度，直观上来讲，具有更小的权重的模型更简单。
岭回归(Ridge Regression)：学习一个映射(w\mathbf{w})能够使得残差的均方和与正则项之和达到最小，即 minw∥Xw?y∥22+λ∥w∥22 \underset{\mathbf{w}}{min}\left \| \mathbf{X}\mathbf{w}-y \right \|^2_2+\lambda \left \| \mathbf{w} \right \|^2_2
其中，前一项∥Xw?y∥22\left \| \mathbf{X}\mathbf{w}-y \right \|^2_2表示的是训练误差，第二项∥w∥22\left \| \mathbf{w} \right \|^2_2表示的是模型的复杂度，λ\lambda 是平衡训练误差和模型复杂度的参数。
与上述的求解过程一致，可以得到下面的最有模型：
w=(XTX+λId)?1XTy
\mathbf{w}=\left ( \mathbf{X}^T\mathbf{X}+\lambda \mathbf{I}_d \right )^{-1}\mathbf{X}^Ty
3、回归问题实例
3.1、监督学习的流程
对于监督学习的流程的具体过程见下图：
3.2、音乐发行年代的预测
对于具体的监督学习任务，可以拆分成下面的过程：
下面是每一步具体的操作。
3.2.1、获取数据
实验的目标是要根据音乐中声音特征预测音乐所属的年代，原始数据可以从UCI的ML库中找到Millionsong Dataset，地址为YearPredictionMSD Data Set。原始数据中是1980到2014年间的西方的商业唱片，特征为平均12音色，标签为发行年代。
3.2.2、分割数据集
将数据集分成训练集和测试集，训练集用于训练，而测试集用于评价模型的优劣。测试误差显示出我们的模型是否具有很好的泛化能力。
3.2.3、特征提取
这里使用的是平方特征(Quadratic features)，平方特征生成方法为：通过属性之间的组合形成新的特征。平方特征可以通过原始数据学习到一个非线性的模型。
假设有两个22维数据，其平方特征为：
x=[x1x2]T?Φ(x)=[x21x1x2x2x1x22]T
\mathbf{x}=\left [ x_1\; \; x_2 \right ]^T\Rightarrow \Phi \left ( \mathbf{x} \right )=\left [ x_1^2\; \; x_1x_2\; \; x_2x_1\; \; x_2^2 \right ]^T
z=[z1z2]T?Φ(z)=[z21z1z2z2z1z22]T
\mathbf{z}=\left [ z_1\; \; z_2 \right ]^T\Rightarrow \Phi \left ( \mathbf{z} \right )=\left [ z_1^2\; \; z_1z_2\; \; z_2z_1\; \; z_2^2 \right ]^T
更简洁的可以表示为：
Φ′(x)=[x212√x1x2x22]T
{\Phi }'\left ( \mathbf{x} \right )=\left [ x_1^2\; \; \sqrt{2}x_1x_2\; \; x_2^2 \right ]^T
Φ′(z)=[z212√z1z2z22]T
{\Phi }'\left ( \mathbf{z} \right )=\left [ z_1^2\; \; \sqrt{2}z_1z_2\; \; z_2^2 \right ]^T
此时有：
Φ(x)TΦ(z)=∑x21z21+2x1x2z1z2+x22z22=Φ′(x)Φ′(z)
\Phi \left ( \mathbf{x} \right )^T\Phi \left ( \mathbf{z} \right )=\sum x_1^2z_1^2+2x_1x_2z_1z_2+x_2^2z_2^2={\Phi}' \left ( \mathbf{x} \right ){\Phi}' \left ( \mathbf{z} \right )
3.2.4、监督学习
在学习阶段，使用的是岭回归(Ridge Regression)，学习从声音特征到歌曲年代的映射。岭回归的学习目标是学习到一个映射(w\mathbf{w})，可以使得残差和的平方加上正则项达到最小，即：
minw∥Xw?y∥22+λ∥w∥22
\underset{\mathbf{w}}{min}\left \| \mathbf{X}\mathbf{w}-\mathbf{y} \right \|^2_2+\lambda \left \| \mathbf{w} \right \|^2_2
其中，前一项是训练的误差，后一项是模型的复杂度，自由参数λ\lambda 是用于平衡训练误差和模型的复杂度的。对于自由参数的选择，通常的做法是对多个参数可能值进行评估，选择评估最好的作为自由参数的值，这样的方法很明显的结果是可能对训练数据效果很好，但是对预测数据效果不好，即所谓的过拟合。另一种方法是留出一部分的训练数据用于搜索自由参数，即构建验证数据集(Validation Set)，如下图所示：
此时，数据集中就包括了训练集，验证集和测试集，其中，训练集用于训练模型，验证集用于评估不同的模型，测试集则是评估最终的模型的准确性。
对于模型中的一些自由参数，或称为超参数(hyperparameter)，可以采用网格搜索(Grid Search)的方法获取，网格搜索是指定义好区间，在区间上取固定的长度来取得不同的值，如下图所示：
3.2.5、评估
在最小二乘优化中使用的是均方误差(Mean Squared Error, MSE)的评价指标，通常在使用中使用的是均方根误差(Root Mean Squared Error, RMSE)，MSE的形式如下：
MSE=1n∑i=1n(y^(i)?y(i))2
MSE=\frac{1}{n}\sum_{i=1}^{n}\left ( \hat{y}^{(i)}-y^{(i)} \right )^2
而RMSE为：
RMSE=MSE?????√
RMSE = \sqrt{MSE}
3.2.6、预测
预测是指对新的观测数据，利用训练好的模型对其进行预测，得到相应的年代。
4、分布式实现
对于大数据集，传统的基于单机环境已经不能胜任这样的工作，对于下述的解：
w=(XTX)?1XTy
\mathbf{w}=\left ( \mathbf{X}^T\mathbf{X} \right )^{-1}\mathbf{X}^T\mathbf{y}
其计算复杂度为：O(nd2+d3)O\left ( nd^2+d^3 \right )，其中，矩阵乘法XTX\mathbf{X}^T\mathbf{X}的计算复杂度为O(nd2)O\left ( nd^2 \right )，矩阵求逆的计算复杂度为O(d3)O\left ( d^3 \right )。需要的空间复杂度为：O(nd+d2)O\left ( nd+d^2 \right )，其中，矩阵乘法XTX\mathbf{X}^T\mathbf{X}的空间复杂度为O(d2)O\left ( d^2 \right )。计算的瓶颈在矩阵的乘法XTX\mathbf{X}^T\mathbf{X}，而存储的瓶颈则主要在X\mathbf{X}。
矩阵的乘法是通过向量的内积实现的。
如：
矩阵的乘法也可以通过矩阵对应的列和行的外积的和实现。
如：
在分布式实现的时候，可以采用如下的方法实现矩阵的计算：
若需要PDF版本，请关注我的新浪博客@赵_志_勇，私信你的邮箱地址给我。