机器学习算法深度总结(3)-最小二乘

1. 最小二乘学习法

最小二乘学习法(后续简称二乘法)是对模型输出和训练集输出的残差的平方和最小时的参数 $\theta$ 进行学习:
$J_{LS}(\theta) = \frac{1}{2}\sum_{i=1}^n(f_\theta(x_i)-y_i)^2$
优化目标:
$\hat{\theta}_{LS} = \underset{\theta}{argmin}J_{LS}(\theta)$
二乘法也称L2损失最小化学习法.

线性模型 $f_\theta(x) = \sum_{j=1}^b\theta_j\phi_j(x) = \theta^T\phi(x)$ 训练样本的残差平方 $J_{LS}$ 表示如下:
$J_{LS}(\theta)= \frac{1}{2}\|\Phi\theta-y\|^2$
其中, $y=(y_1,\cdots,y_n)^T$ 是训练输出的n维行向量, $\Phi$ 是基函数的nxb设计矩阵:
$\Phi= \begin{pmatrix} \phi_1(x_1) & \cdots & \phi_b(x_1) \\ \vdots & \ddots & \vdots \\ \phi_1(x_n) & \cdots & \phi_b(x_1n \end{pmatrix} = (\phi(x1), \cdots, \phi(x_n))$
也是输入数据的基函数向量向量组成的列向量矩阵.
求平方差 $J_{LS}(\theta)$ 的参数向量 $\theta$ 的偏微分:
$\nabla_{\theta}J_{LS} = (\frac{\partial J_{LS}}{\partial \theta_1}, \cdots, \frac{\partial J_{LS}}{\partial \theta_b})= \Phi^T\Phi\theta-\Phi^T\mathbf y$
上式推导:

常用的矩阵求导公式:

改写为向量积
$2J_{LS}(\theta)= \|\Phi\theta-y\|^2 = (\Phi\theta-y)^T(\Phi\theta-y)$

2.展开多项式
$2J_{LS}(\theta)= y^Ty - 2\theta^T\Phi^Ty + \theta^T\Phi^T\Phi\theta$

对第二项求关于 $\theta$ 的导数:
根据矩阵求导公式:
$\nabla_{x}(x^TA) = A$
故
$\nabla_{\theta}(2\theta^T\Phi^Ty) = 2\Phi^Ty$

对第三项求 $\theta$ 的导数:
根据矩阵求导公式:
$\nabla_{x}(x^TAx) = Ax+A^Tx$
故
$\nabla_{\theta}(\theta^T\Phi^T\Phi\theta) = (\Phi^T\Phi)\theta+(\Phi^T\Phi)^T\theta = 2\Phi^T\Phi\theta \; \;\cdots(\Phi^T\Phi是对称矩阵, 有\Phi^T=\Phi)$
第一项求 $\theta$ 的导数为0, 故:
$J_{LS}(\theta)=\Phi^T\Phi\theta-\Phi^Ty$
得证.

$\nabla \theta_{LS}=0$ 时 $J_{LS}(\theta)$ 取得最小值, 此时最小二乘解满足 $\Phi^T\Phi \theta=\Phi^T\mathbf y$
解得:
$\hat \theta_{LS} = (\Phi^T\Phi)^{-1}\Phi^Ty$
广义逆矩阵: 是对逆矩阵的推广, 只有方阵, 非奇异矩阵才有逆矩阵, 单矩形矩阵或奇异矩阵都可以定义广义逆矩阵.
令广义逆矩阵为:
$\Phi^+ = (\Phi^T\Phi)^{-1}\Phi^T$
, 则 $\hat \theta_{LS}$ 可写为:
$\hat \theta_{LS} = \Phi ^+y$

2. 最小二乘解的性质

补充知识: 奇异值分解

矩阵A( $m\times n$ )的SVD定义为:
$A = U \Sigma V^T \;(此处A不要求是方阵)$
奇异值在 $\Sigma$ 主对角线上. U和V均为酋矩阵, 满足 $U^TU = I$ , $V^TV=I$
SVD分解步骤:
①对 $A^TA$ ( $n\times n$ )方阵(做特征分解: $(A^TA)v_i = \lambda_iv_i$ , 所有特征向量组成V矩阵, V中的每个特征向量 $v_i$ 为右奇异向量
②对 $AA^T$ ( $m\times m$ )方阵做特征分解: $(AA^T)u_i = \lambda_iu_i$ , 所有特征向量组成U矩阵, U中的每个特征向量 $U_i$ 为右奇异向量
③奇异值矩阵 $\Sigma$ 为对角矩阵, 每个奇异值 $\sigma_i=\sqrt{\lambda_i}$ , $\lambda_i$ 为左奇异矩阵 $A^TA$ 中奇异向量对应的特征值

设计矩阵 $\Phi$ (线性模型的基函数矩阵)的奇异值分解:
$\phi = \sum_{k=1}^{min(n,b)}\kappa_k\psi_{k} \varphi_k^T$
$\kappa_k, \psi_{k}, \varphi_k$ 分别称为奇异值, 左奇异向量, 右奇异向量.

奇异值非负
奇异向量满足正交性

$\Phi$ 的广义逆矩阵:
$\Phi^+ =\sum_{k=1}^{min(n,b)}\kappa_k^+\psi_{k} \varphi_k^T$
$\kappa _k^+$ 是标量 $\kappa$ 的广义逆矩阵, $\kappa^+ = \frac{1}{\kappa} (\kappa \neq 0时)$
最小二乘解表示为:
$\hat \theta_{LS}= \sum_{k=1}^{min(n,b)}\kappa_k^+(\psi_{k}^Ty) \varphi_k$
模型输出向量变换为列向量:
$(f_{\hat \theta_{LS}}(x_1), \cdots, f_{\hat \theta_{LS}}(x_n))^T = \Phi\hat \theta_{LS} = \Phi\Phi^+\mathbf{y}$
因此, $\Phi\Phi^+$ 是 $\Phi$ 的正交投影矩阵, 最小二乘法输出向量 $\mathbf y$ 是值域 $R(\Phi)$ 的正交投影得到的.

带入真实函数中的参数 $\theta^*$ :
$(f(x_1), \cdots, f(x_n))^T = \Phi \theta^*$
可知, 真的输出值向量就存在于 $R(\Phi)$ 中
结论: 用最小二乘法的向量若是由 $R(\Phi)$ 的正投影得到的, 则可以有效去除y中的噪音.
噪声期望E为0是, $\hat \theta_{LS}$ 就是真是参数 $\theta^*$ 的无偏估计:
$E[\hat \theta_{LS}] = \theta^*$
渐近无偏性:
增加训练样本n, 上式 $E[\hat \theta_{LS}]$ 会向着模型中最优参数方向收敛的性质

补充知识: 投影矩阵

投影到向量

向量b在向量a上的投影 $(b)_a=\hat{x}a$ , 其中 $\hat{x}=\frac{a\cdot b}{a^\top a}$ (a,b均为向量)
$\hat{x}$ 求解:
设b在a直线上的投影为 $p=\hat{x}a$ , 作直线a的垂线直线e, 则e为向量b到向量p的最短距离, 且 $e=b-p$ .
$e\cdot a = a^T (b-p) = a^T\cdot b - \hat{x}a^T \cdot a = 0 \Rightarrow \hat{x} = \frac{a^T\cdot b}{a^T \cdot a}$

投影到子空间
若投影p, 向量b, 矩阵P满足 $p=Pb$ , 则称P为投影矩阵. 将 $p=\hat{x}a$ 改写一下, $p=\frac{a^T\cdot b}{a^T \cdot a} a = (\frac{a^T\cdot a}{a^T \cdot a}) b$ , 可将投影向量看做秩为1的投影矩阵P.

投影矩阵的两个典型的性质
① P是一个对称矩阵
②它的平方等于它自身：P2=P

3. 带约束的最小二乘

L2约束也称L2正则化, 回归问题里也叫岭回归(Ridge Regression),也叫权重衰减(weight decay), 可改善模型的过拟合.
L1约束也叫"稀疏规则算子"(Lasso regularization), 模型参数太多时, 模型求解耗时太多, 稀疏学习可将大部分参数置为0, 从而快速求解.

L1和L2约束二乘的参数空间:

1. L2约束二乘

约束条件如下:
$\underset{\theta}{\min}J_{LS}(\theta)\quad 约束条件\|\theta\|^2 \leq R$
L2参数空间, 是一个参数空间原点为圆心,R为半径内的圆(一般为超球):

引入拉格朗日对偶问题:

利用拉格朗日对偶问题, 求解:
$\underset{\lambda}{\max}\min[J_{LS}(\theta) + \frac{\lambda}{2}(\|\theta\|^2-R)]\;s.t. \lambda \ge 0$
的最优解问题, 可得到最优化问题 $\underset{\theta}{\min}J_{LS}(\theta)$ 的解, 上式中拉格朗日待定因子 $\lambda$ 的解由圆半径R决定

简化版(不由R决定 $\lambda$ ):
$\hat \theta = \underset{\theta}{argmin}[J_{LS}(\theta)+\frac{\lambda}{2}\|\theta\|^2] \; s.t. \lambda \ge 0$
上式 $J_{LS}(\theta)$ 表示对样本拟合程度, 与 $\frac{\lambda}{2}\|\theta\|^2$ 组合得到最小值, 防止过拟合

L2约束的LS关于 $\theta$ 的微分可通过下式求解:

$\hat J_{LS}(\theta)= J_{LS}(\theta) + \frac{\lambda}{2}\|\theta\|^2 = \frac{1}{2}(\Phi\theta-y)^T(\Phi\theta-y) + \frac{\lambda}{2}\theta^T\theta \quad (1)$

$\nabla_\theta J_{LS}$ 上文已经求过:

$\nabla_\theta J_{LS} = \Phi^T\Phi\theta-\Phi^Ty \quad (2)$

$\nabla_\theta \theta^T\theta$ 根据矩阵求导公式:

$\nabla_\theta \theta^T\theta = 2\theta \quad(3)$
综合(2)(3)求(1)中关于 $\theta$ 的微分:
$\nabla_\theta \hat J_{LS}(\theta)=\Phi^T\Phi\theta-\Phi^Ty + 2 \lambda \theta = (\Phi^T\Phi +\lambda I)\lambda -\Phi^Ty$

令关于 $\theta$ 的导数为0, L2约束的LS的解 $\theta$ 为:
$\hat \theta = (\Phi^T\Phi+\lambda I)^{-1}\Phi^T\mathbf y$

上式结论:

将矩阵 $\Phi^T\Phi和\lambda I$ 相加提高其正则性, 进而更稳定地进行逆矩阵求解.
L2约束的LS也称为L2正则化的LS, 式(1)中的 $\|\theta\|^2$ 称为正则项, $\lambda$ 为正则化参数
L2正则化有时也称岭回归

将设计矩阵 $\Phi$ 做奇异值分解:
$\Phi = \sum_{k=1}^{\min(n,b)}\kappa_k\psi_k\varphi_k^T$

带入上上式, 则L2约束的LS解 $\hat \theta$ 表示为:
$\hat \theta = \sum_{k=1}^{\min(n,b)} \frac{\kappa_k}{\kappa_k^2+\lambda}\psi_k^Ty\varphi_k$
上式结论:

$\lambda=0$ 时, L2约束的LS蜕化为一般的LS
设计矩阵 $\Phi$ 计算条件恶劣,包含极小的奇异值 $K_k$ 时, $K_k/K_k^2=1/K_k$ 变得极大, 训练输出y的噪声会增加
分母 $\kappa_k^2$ 中加入正的常数 $\lambda$ , 避免 $\kappa_k/(\kappa_k^2+\lambda)$ 过大, 进而可防止过拟合

拓展: 更一般L2约束的LS

更一般的L2约束LS使用 $b \times b$ 正则化矩阵G, 可得到更一般的表示:

问题表示:
$\underset{\theta}{\min}J_{LS}(\theta)\ s.t. \ \theta^TG\theta \le R$
$\hat \theta$ 求解:
更一般的L2约束的LS解 $\theta$ 求解过程, 和标准L2约束的LS大体相同:
$\hat \theta = (\Phi^T\Phi + \lambda G)^{-1}\Phi^Ty$

参数空间:
矩阵G对称正定时, $\theta^TG\theta \leq R$ 将数据限制在椭圆区域内. 下图为更一般的L2约束的LS参数空间:

模型选择

部分空间约束或L2约束的LS, 都过分依赖正交投影矩阵P和 正则化参数λ的选择
选择合适的P和λ至关重要
采用不同的输入样本, 决定算法中各个参数值的过程称为模型选择

2. L1约束二乘

L1约束二乘的参数空间:

稀疏学习中常用L1进行条件约束:

$\underset{\theta}{\min}J_{LS}(\theta)\quad 约束条件\|\theta\|_1 \leq R$
其中, $\|\theta\|_1=\sum_{j=1}^{b}|\theta_j|$
再回顾L1和L2约束二乘的参数空间:

以含参线性模型为例对上图做分析:

$f_{\theta} = \sum_{j=1}^b\theta_j\phi_j(x) =\theta^T\phi(x)$

训练误差 $J_{LS}$ 是关于 $\theta$ 的向下的二次凸函数, 因此 $J_{LS}$ 在参数空间内有椭圆状等高线, 底部是最小二乘解 $\hat \theta_{LS}$
$\hat \theta_{L_2CLS}$ :椭圆等高线和圆周交点是L2约束LS的解 $\hat \theta_{LS}$ , 即 $L_2$ -Constrained Least Squares
$\hat \theta_{L_1CLS}$ :椭圆等高线和菱形的角的焦点是L1约束LS的解 $\hat \theta$ , L1约束LS的解一定位于参数的轴上

L1约束二乘求解

L1范数包含原点处不可微分的绝对值, 故不能像L2约束那样简单求解:

下面通过利用拉格朗日对偶问题求解, 考虑L1正则化的最优化问题:
$\underset{\theta}{\min}J(\theta), J(\theta) = J_{LS}(\theta) + \lambda\|\theta\|_1$

L1范数原点不能微分, 用微分的二次函数控制:
$|\theta_j| <= \frac{\theta_j^2}{2c_j}+\frac{c_j}{2}, \forall c_j > 0$

函数如图:

L2正则化LS一般表达式:
$\hat \theta = \underset{\theta}{argmin}\tilde{J}(\theta), \tilde J(\theta) = J_{LS}(\theta)+\frac{\lambda}{2}\theta^T\tilde{\Theta}^+\theta + C$

线性模型 $f_{\theta}(x)=\theta^T\phi(x)$ 的解 $\hat \theta$ :
$\hat \theta =(\Phi^T\Phi+\lambda\Theta^+)^{-1}\Phi^Ty$
现在的解 $\Theta=\tilde\Theta$ 的情况下，绝对值函数也是与二次函数的上界相外切的，因此， $J(\tilde \theta)=\tilde J(\tilde \theta)$ 是成立的。另外， $\hat \theta$ 是 $\tilde J$ 为最小的时候取到的， $\tilde J(\hat \theta) \ge \tilde J(\hat \theta)$ 也是成立的。由于 $\tilde J(\theta)$ 是J的上界, 因此 $\tilde J(\hat \theta) \ge J(\hat \theta)$ 也是成立的，综上可得:
$J(\tilde\theta) = \tilde J(\tilde \theta) \ge \tilde J(\hat \theta) \ge J(\hat \theta)$
可见, 更新后的解 $\hat \theta)$ 比现在的解 $\tilde \theta)$ 更收敛, 具体如下图所示：

给定适当的初始值反复更新这个解, l1约束二乘的解就可使用l2约束二乘法来求得.

3.Lp约束二乘

$L_p$ 范数:
$\|\theta\|_p = (\sum_{j=1}^b|\theta_j|^P)^{\frac{1}{p}} \le R$
$p=\infty$ 时称最大值范数: $\|\theta\|_{\infty} = \max\{|\theta_1|,\cdots,|\theta_b|\}$
p=0时L_0范数表示非零向量元素个数:
$\|\theta\|_0 = \sum_{j=1}^b\delta(\theta_j \ne 0), \delta(\theta_j \ne 0) = \begin{cases} 1& (\theta_j \ne 0) \\ 0&(\theta_j = 0) \end{cases}$

$L_p$ 范数的单位球(R=1):

分析:

$p \leq 1$ 时,坐标轴上呈现有峰值的尖形
$p \geq 1$ 时,单位球呈现凸形

稀疏解存在的特殊条件:
1.约束空间为凸形(非凸优化困难)
2.坐标轴上呈现有峰值的尖形

就像上图展示的那样，在坐标轴上呈有峰值的尖形是存在稀疏解的秘诀。另一方面，满足约束条件的空间如果不是凸型的话，可能存在局部最优解，但是最优化工作就会变得异常艰难。因此，当p=1时是稀疏解存在的唯一的凸型，由此可知，L1约束的最小二乘学习法是非常特殊的一种学习方法。

满足Lp范数的约束条件的空间性质:

4. 弹性网络(L1+L2)

L1约束的限制:

参数b比训练样本n多时, 线性模型可选择的最大特征数被局限为n
线性模型中形成集群构造(有多个基函数相似的集合)时, $L_1$ LS选择一个忽略其它, 核模型输入样本是簇构造是更易形成集群构造
参数b比样本n少时, $L_1$ 的通用性比 $L_2$ 更差

$\tau=0.5$ 时, L1+L2范数的单位球如下图所示(黑实线)：

由图可见, $\tau=0.5$ 时L1+L2范数的单位球和 $L_{1.4}$ 范数的单位球形状完全相同, 然而, 如果用放大镜放大角的部分, 会发现 $L_{1.4}$ 范数的单位球像L2那样平滑, 但是L1+L2范数的单位球则像L1范数那样呈尖形.
因此L1+L2范数约束也会想L1范数约束那样容易求得稀疏解.

此外, 另外，即使参数b比训练样本数n还要多，L1+L2约束的最小二乘学习法也可以拥有n个以上的非零参数。另外，当基函数为集合构造的时候，经常会以集合为单位对基函数进行选择，实验证明：L1+L2约束的最小二乘学习法比L1约束的最小二乘学习法具有更高的精度。然而，除了加入正则化参数λ之外，为了调整L1范数和L2范数的平衡，还需要引入参数T，这也是L1+L2约束最小二乘学习法在实际中所面临的问题。

最后编辑于：2018.10.08 13:02:38

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,293评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,604评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,958评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,729评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,719评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,630评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,000评论 3赞 397
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,665评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,909评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,646评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,726评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,400评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,986评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,959评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,197评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,996评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,481评论 2赞 342