【机器学习】回归算法和分类算法中各种公式的详细推导

「爱情、让人受尽委屈。」 2023-07-11 15:26 22阅读 0赞

## 1、什么是回归算法 ##

回归算法是一种比较常用的机器学习算法，用来建立“解释”变量和观测值之间的关系；从机器学习的角度来讲，用于构建一个算法模型（函数）来做属性与标签之间的映射关系，在算法的学习过程中，试图寻找一个函数h：Rd -> R，使得参数之间的关系拟合性最好。  
回归算法中算法（函数）的最终结果是一个连续的数据值，输入值（属性值）是一个d维度的属性/数值向量。

## 2、线性回归算法 ##

（1）线性回归公式  
一元线性回归： y = a x + b y=ax+b y=ax\+b，是一条线。  
二元线性回归： h ( x ) = θ 0 + θ 1 x 1 + θ 2 x 2 h(x)=\\theta\_0+\\theta\_1x\_1+\\theta\_2x\_2 h(x)=θ0\+θ1x1\+θ2x2，是一个平面。  
多元线性回归：  
 h θ ( x ) = θ 0 + θ 1 x 1 + . . . + θ n x n = θ 0 1 + θ 1 x 1 + . . . + θ n x n = θ 0 x 0 + θ 1 x 1 + . . . + θ n x n = ∑ i = 0 n θ i x i = θ T X \\begin\{aligned\} h\_\\theta(x) &= \\theta\_0+\\theta\_1x\_1+...+\\theta\_nx\_n \\\\ &= \\theta\_01+\\theta\_1x\_1+...+\\theta\_nx\_n \\\\ &=\\theta\_0x\_0+\\theta\_1x\_1+...+\\theta\_nx\_n \\\\ &=\\sum\_\{i=0\}^n\\theta\_ix\_i \\\\ &=\\theta^TX \\end\{aligned\} hθ(x)=θ0\+θ1x1\+...\+θnxn=θ01\+θ1x1\+...\+θnxn=θ0x0\+θ1x1\+...\+θnxn=i=0∑nθixi=θTX  
最终要求是计算出 的值，并选择最优的 值构成算法公式。  
（2）误差的最大似然估计  
 y ( i ) = θ T x ( i ) + ε ( i ) y^\{(i)\}=\\theta^Tx^\{(i)\}+\\varepsilon^\{(i)\} y(i)=θTx(i)\+ε(i)  
依据中心极限定理，误差 ε ( i ) \\varepsilon^\{(i)\} ε(i)(1 ≤ \\leq ≤i ≤ \\leq ≤n)是独立同分布的，服从均值为0，方差为某定值 σ 2 \\sigma^2 σ2的高斯分布。根据 θ \\theta θ的极大似然估计求出损失函数，进而求得 θ \\theta θ。  
 p ( ε ( i ) ) = 1 σ 2 π e ( − ( ε ( i ) ) 2 2 σ 2 ) p ( y ( i ) ∣ x ( i ) ; θ ) = 1 σ 2 π exp ⁡ ( − ( y ( i ) − θ T x ( i ) ) 2 2 σ 2 ) L ( θ ) = ∏ i = 1 m p ( y ( i ) ∣ x ( i ) ; θ ) = ∏ i = 1 m 1 σ 2 π exp ⁡ ( − ( y ( i ) − θ T x ( i ) ) 2 2 σ 2 ) l ( θ ) = log ⁡ L ( θ ) = log ⁡ ∏ i = 1 m 1 σ 2 π exp ⁡ ( − ( y ( i ) − θ T x ( i ) ) 2 2 σ 2 ) = ∑ i = 1 m log ⁡ 1 σ 2 π exp ⁡ ( − ( y ( i ) − θ T x ( i ) ) 2 2 σ 2 ) = m log ⁡ 1 σ 2 π − 1 σ 2 ⋅ 1 2 ∑ i = 1 m ( y ( i ) − θ T x ( i ) ) 2 l o s s ( y j , y j ^ ) = J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 = 1 2 ( X θ − Y ) T ( X θ − Y ) → min ⁡ θ J ( θ ) ∇ θ J ( θ ) = ∇ θ ( 1 2 ( X θ − Y ) T ( X θ − Y ) ) = ∇ θ ( 1 2 ( θ T X T − Y T ) ( X θ − Y ) ) = ∇ θ ( 1 2 ( θ T X T X θ − θ T X T Y − Y T X θ + Y T Y ) ) = 1 2 ( 2 X T X θ − X T Y − ( Y T X ) T ) = X T X θ − X T Y θ = ( X T X ) − 1 X T Y \\begin\{aligned\} p(\\varepsilon^\{(i)\})&=\\frac\{1\}\{\\sigma\\sqrt\{2\\pi\}\}e^\{(-\\frac\{(\\varepsilon^\{(i)\})^2\}\{2\\sigma^2\})\} \\\\ p(y^\{(i)\}|x^\{(i)\};\\theta)&=\\frac\{1\}\{\\sigma\\sqrt\{2\\pi\}\}\\exp(-\\frac\{(y^\{(i)\}-\\theta^Tx^\{(i)\})^2\}\{2\\sigma^2\}) \\\\ L(\\theta)&=\\prod\_\{i=1\}^mp(y^\{(i)\}|x^\{(i)\};\\theta) \\\\ &=\\prod\_\{i=1\}^m\\frac\{1\}\{\\sigma\\sqrt\{2\\pi\}\}\\exp(-\\frac\{(y^\{(i)\}-\\theta^Tx^\{(i)\})^2\}\{2\\sigma^2\}) \\\\ l(\\theta)&=\\log L(\\theta) \\\\ &=\\log\\prod\_\{i=1\}^m\\frac\{1\}\{\\sigma\\sqrt\{2\\pi\}\}\\exp(-\\frac\{(y^\{(i)\}-\\theta^Tx^\{(i)\})^2\}\{2\\sigma^2\}) \\\\ &=\\sum\_\{i=1\}^m\\log\\frac\{1\}\{\\sigma\\sqrt\{2\\pi\}\}\\exp(-\\frac\{(y^\{(i)\}-\\theta^Tx^\{(i)\})^2\}\{2\\sigma^2\}) \\\\ &=m\\log\\frac\{1\}\{\\sigma\\sqrt\{2\\pi\}\}-\\frac\{1\}\{\\sigma^2\}\\cdot\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(y^(i)-\\theta^Tx^\{(i)\})^2 \\\\ loss(y\_j, \\hat\{y\_j\})&=J(\\theta)=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2 \\\\ &=\\frac\{1\}\{2\}(X\\theta-Y)^T(X\\theta-Y) \\rightarrow\\min\_\{\\theta\}J(\\theta) \\\\ \\nabla\_\{\\theta\}J(\\theta)&=\\nabla\_\{\\theta\}(\\frac\{1\}\{2\}(X\\theta-Y)^T(X\\theta-Y)) \\\\ &=\\nabla\_\{\\theta\}(\\frac\{1\}\{2\}(\\theta^TX^T-Y^T)(X\\theta-Y)) \\\\ &=\\nabla\_\{\\theta\}(\\frac\{1\}\{2\}(\\theta^TX^TX\\theta-\\theta^TX^TY-Y^TX\\theta+Y^TY)) \\\\ &=\\frac\{1\}\{2\}(2X^TX\\theta-X^TY-(Y^TX)^T) \\\\ &=X^TX\\theta-X^TY \\\\ \\theta&=(X^TX)^\{-1\}X^TY \\end\{aligned\} p(ε(i))p(y(i)∣x(i);θ)L(θ)l(θ)loss(yj,yj^)∇θJ(θ)θ=σ2π1e(−2σ2(ε(i))2)=σ2π1exp(−2σ2(y(i)−θTx(i))2)=i=1∏mp(y(i)∣x(i);θ)=i=1∏mσ2π1exp(−2σ2(y(i)−θTx(i))2)=logL(θ)=logi=1∏mσ2π1exp(−2σ2(y(i)−θTx(i))2)=i=1∑mlogσ2π1exp(−2σ2(y(i)−θTx(i))2)=mlogσ2π1−σ21⋅21i=1∑m(y(i)−θTx(i))2=J(θ)=21i=1∑m(hθ(x(i))−y(i))2=21(Xθ−Y)T(Xθ−Y)→θminJ(θ)=∇θ(21(Xθ−Y)T(Xθ−Y))=∇θ(21(θTXT−YT)(Xθ−Y))=∇θ(21(θTXTXθ−θTXTY−YTXθ\+YTY))=21(2XTXθ−XTY−(YTX)T)=XTXθ−XTY=(XTX)−1XTY  
（3）最小二乘法求参数 θ \\theta θ的最优解  
参数解析式： θ = ( X T X ) − 1 X T Y \\theta=(X^TX)^\{-1\}X^TY θ=(XTX)−1XTY  
最小二乘法的使用要求矩阵 X T X X^TX XTX是可逆的；为了防止不可逆或者过拟合的问题存在，可以增加额外数据影响，导致最终的矩阵是可逆的：  
 θ = ( X T X + λ I ) − 1 X T Y \\theta=(X^TX+\\lambda I)^\{-1\}X^TY θ=(XTX\+λI)−1XTY  
最小二乘法直接求解的难点：矩阵逆的求解并不容易，矩阵的维数很可能很大。  
（4）目标函数/损失函数/代价函数（loss/cost function）  
1）0-1损失函数：  
 J ( θ ) = \{ 1 , Y ≠ f ( X ) 0 , Y = f ( X ) J(\\theta)=\\begin\{cases\}1, & Y\\ne f(X) \\\\ 0, & Y=f(X)\\end\{cases\} J(θ)=\{ 1,0,Y=f(X)Y=f(X)  
2）感知损失函数：  
 J ( θ ) = \{ 1 , ∣ Y − f ( X ) ∣ > t 0 , ∣ Y − f ( X ) ∣ ≤ t J(\\theta)=\\begin\{cases\}1, & |Y-f(X)|\\gt t \\\\ 0, & |Y-f(X)|\\le t\\end\{cases\} J(θ)=\{ 1,0,∣Y−f(X)∣>t∣Y−f(X)∣≤t  
3）平方和损失函数：  
 J ( θ ) = ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 J(\\theta)=\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2 J(θ)=i=1∑m(hθ(x(i))−y(i))2  
4）绝对值损失函数：  
 J ( θ ) = ∑ i = 1 m ∣ h θ ( x ( i ) ) − y ( i ) ∣ J(\\theta)=\\sum\_\{i=1\}^m|h\_\\theta(x^\{(i)\})-y^\{(i)\}| J(θ)=i=1∑m∣hθ(x(i))−y(i)∣  
5）对数损失函数：  
 J ( θ ) = ∑ i = 1 m ( y ( i ) log ⁡ h θ ( x ( i ) ) ) J(\\theta)=\\sum\_\{i=1\}^m(y^\{(i)\}\\log h\_\\theta(x^\{(i)\})) J(θ)=i=1∑m(y(i)loghθ(x(i)))  
（5）正则化惩罚项  
目标函数： J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 J(\\theta)=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2 J(θ)=21∑i=1m(hθ(x(i))−y(i))2  
为了防止数据过拟合，也就是 θ \\theta θ的值在样本空间中不能过大/过小，可以在目标函数之上增加一个平方和损失：  
 J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 + λ ∑ i = 1 n θ j 2 J(\\theta)=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2+\\lambda\\sum\_\{i=1\}^n\\theta\_j^2 J(θ)=21i=1∑m(hθ(x(i))−y(i))2\+λi=1∑nθj2  
这个 λ ∑ i = 1 n θ j 2 \\lambda\\sum\_\{i=1\}^n\\theta\_j^2 λ∑i=1nθj2叫做L2正则项。  
使用L2正则的线性回归模型称为Ridge回归（岭回归）。加L2正则项的损失函数如下。  
 J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 + λ ∑ i = 1 n θ j 2 ( λ > 0 ) J(\\theta)=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2+\\lambda\\sum\_\{i=1\}^n\\theta\_j^2 \\\\ (\\lambda\\gt0) J(θ)=21i=1∑m(hθ(x(i))−y(i))2\+λi=1∑nθj2(λ>0)  
使用L1正则的线性回归模型称为LASSO回归（Least Absolute Shrinkage and  
Selection Operator）。加L1正则项的损失函数如下。  
 J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 + λ ∑ i = 1 n ∣ θ j ∣ ( λ > 0 ) J(\\theta)=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2+\\lambda\\sum\_\{i=1\}^n|\\theta\_j| \\\\ (\\lambda\\gt0) J(θ)=21i=1∑m(hθ(x(i))−y(i))2\+λi=1∑n∣θj∣(λ>0)  
Ridge回归（L1-norm）和LASSO回归（L2-norm）的比较：  
L2-norm中，由于对于各个维度的参数缩放是在一个圆内缩放的，不可能导致有维度参数变为0的情况，那么也就不会产生稀疏解；实际应用中，数据的维度中是存在噪音和冗余的，稀疏的解可以找到有用的维度并且减少冗余，提高回归预测的准确性和鲁棒性（减少过拟合）L2-norm可以达到最终解的稀疏性的要求。  
Ridge模型具有较高的准确性、鲁棒性以及稳定性。LASSO模型具有较高的求解  
速度。  
同时使用L1正则和L2正则的线性回归模型就称为弹性网络算法（Elasitc Net算法）。  
 J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 + λ ( p ∑ j = 1 n ∣ θ j ∣ + ( 1 − p ) ∑ j = 1 n θ j 2 ) \{ λ > 0 p ∈ \[ 0 , 1 \] J(\\theta)=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2+\\lambda(p\\sum\_\{j=1\}^n|\\theta\_j|+(1-p)\\sum\_\{j=1\}^n\\theta\_j^2) \\\\ \\begin\{cases\} \\lambda\\gt0 \\\\ p\\in\[0, 1\] \\end\{cases\} J(θ)=21i=1∑m(hθ(x(i))−y(i))2\+λ(pj=1∑n∣θj∣\+(1−p)j=1∑nθj2)\{ λ>0p∈\[0,1\]  
（6）模型效果判断  
1）MSE：误差平方和，越趋近于0表示模型越拟合训练数据。  
 M S E = 1 m ∑ i = 1 m ( y i − y i ^ ) 2 MSE=\\frac\{1\}\{m\}\\sum\_\{i=1\}^m(y\_i-\\hat\{y\_i\})^2 MSE=m1i=1∑m(yi−yi^)2  
2）RMSE：MSE的平方根，作用同MSE。  
 R M S E = M S E = 1 m ∑ i = 1 m ( y i − y i ^ ) 2 RMSE=\\sqrt\{MSE\}=\\sqrt\{\\frac\{1\}\{m\}\\sum\_\{i=1\}^m(y\_i-\\hat\{y\_i\})^2\} RMSE=MSE=m1i=1∑m(yi−yi^)2  
3） R 2 R^2 R2：取值范围(负无穷,1\]，值越大表示模型越拟合训练数据；最优解是1；当模型预测为随机值的时候，有可能为负；若预测值恒为样本期望， R 2 R^2 R2为0。  
TSS：总平方和TSS（Total Sum of Squares），表示样本之间的差异情况，是伪方差的m倍。  
RSS：残差平方和RSS（Residual Sum of Squares），表示预测值和样本值之  
间的差异情况，是MSE的m倍。  
 R 2 = 1 − R S S T S S = 1 − ∑ i = 1 m ( y i − y i ^ ) 2 ∑ i = 1 m ( y i − y ˉ ) y ˉ = 1 m ∑ i = 1 m y i \\begin\{aligned\} R^2&=1-\\frac\{RSS\}\{TSS\}=1-\\frac\{\\sum\_\{i=1\}^m(y\_i-\\hat\{y\_i\})^2\}\{\\sum\_\{i=1\}^m(y\_i-\\bar\{y\})\} \\\\ \\bar\{y\}&=\\frac\{1\}\{m\}\\sum\_\{i=1\}^my\_i \\end\{aligned\} R2yˉ=1−TSSRSS=1−∑i=1m(yi−yˉ)∑i=1m(yi−yi^)2=m1i=1∑myi  
（7）机器学习调参  
在实际工作中，对于各种算法模型（线性回归）来讲，我们需要获取θ、λ、p的值；θ的求解其实就是算法模型的求解，一般不需要开发人员参与（算法已经实现），主要需要求解的是λ和p的值，这个过程就叫做调参（超参）。  
交叉验证：将训练数据分为多份，其中一份进行数据验证并获取最优的超参：λ  
和p；比如：十折交叉验证、五折交叉验证（scikit-learn中默认）等。  
（8）线性回归的扩展  
线性回归的θ是一次的，而对于样本本身而言，样本可以是非线性的，也就是说最终得到的函数f: x->y，函数f(x)可以是非线性的，比如：曲线等。  
![20200306221151179.png][]  
（9）局部加权回归损失函数  
普通线性回归损失函数：  
 J ( θ ) = ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 J(\\theta)=\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2 J(θ)=i=1∑m(hθ(x(i))−y(i))2  
局部加权回归损失函数：  
 J ( θ ) = ∑ i = 1 m w ( i ) ( h θ ( x ( i ) ) − y ( i ) ) 2 J(\\theta)=\\sum\_\{i=1\}^mw^\{(i)\}(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2 J(θ)=i=1∑mw(i)(hθ(x(i))−y(i))2  
 w ( i ) w^\{(i)\} w(i)是权重，它根据要预测的点与数据集中的点的距离来为数据集中的点赋权值。当某点离要预测的点越远，其权重越小，否则越大。常用值选择公式为：  
 w ( i ) = exp ⁡ ( − ( x ( i ) − x ) 2 2 k 2 ) w^\{(i)\}=\\exp(-\\frac\{(x^\{(i)\}-x)^2\}\{2k^2\}) w(i)=exp(−2k2(x(i)−x)2)  
该函数称为指数衰减函数，其中k为波长参数，它控制了权值随距离下降的速率。使用该方式主要应用到样本之间的相似性考虑，类似于SVM中的核函数。

## 3、梯度下降算法 ##

（1）梯度下降算法的公式推导  
目标函数θ求解： J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 J(\\theta)=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2 J(θ)=21∑i=1m(hθ(x(i))−y(i))2  
初始化θ（随机初始化，可以初始为0）。  
沿着负梯度方向迭代，更新后的θ使J(θ)更小。公式如下。  
 θ = θ − α ⋅ ∂ J ( θ ) ∂ θ \\theta=\\theta-\\alpha\\cdot\\frac\{\\partial J(\\theta)\}\{\\partial\\theta\} θ=θ−α⋅∂θ∂J(θ)  
α是学习率、步长。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70][]  
 J ( θ ) = 1 2 ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 ∂ J ( θ ) ∂ θ j = ∂ 1 2 ( h θ ( x ) − y ) 2 ∂ θ j = 2 ⋅ 1 2 ( h θ ( x ) − y ) ⋅ ∂ ( h θ ( x ) − y ) ∂ θ j = ( h θ ( x ) − y ) ∂ ( ∑ i = 1 n θ i x j − y ) ∂ θ j = ( h θ ( x ) − y ) x j \\begin\{aligned\} J(\\theta)&=\\frac\{1\}\{2\}\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})^2 \\\\ \\frac\{\\partial J(\\theta)\}\{\\partial\\theta\_j\}&=\\frac\{\\partial\\frac\{1\}\{2\}(h\_\\theta(x)-y)^2\}\{\\partial\\theta\_j\} \\\\ &=2\\cdot\\frac\{1\}\{2\}(h\_\\theta(x)-y)\\cdot\\frac\{\\partial(h\_\\theta(x)-y)\}\{\\partial\\theta\_j\} \\\\ &=(h\_\\theta(x)-y)\\frac\{\\partial(\\sum\_\{i=1\}^n\\theta\_ix\_j-y)\}\{\\partial\\theta\_j\} \\\\ &=(h\_\\theta(x)-y)x\_j \\end\{aligned\} J(θ)∂θj∂J(θ)=21i=1∑m(hθ(x(i))−y(i))2=∂θj∂21(hθ(x)−y)2=2⋅21(hθ(x)−y)⋅∂θj∂(hθ(x)−y)=(hθ(x)−y)∂θj∂(∑i=1nθixj−y)=(hθ(x)−y)xj  
（2）批量梯度下降算法（BGD）  
 ∂ J ( θ ) ∂ θ j = ( h θ ( x ) − y ) x j ∂ J ( θ ) ∂ θ j = ∑ i = 1 m ∂ J ( θ i ) ∂ θ j = ∑ i = 1 m ( x j ( h θ ( x ( i ) ) − y ( i ) ) ) = ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) θ j = θ j + α ∑ i = 1 m ( y ( i ) − h θ ( x ( i ) ) ) x j ( i ) \\begin\{aligned\} \\frac\{\\partial J(\\theta)\}\{\\partial\\theta\_j\}&=(h\_\\theta(x)-y)x\_j \\\\ \\frac\{\\partial J(\\theta)\}\{\\partial\\theta\_j\}&=\\sum\_\{i=1\}^m\\frac\{\\partial J(\\theta\_i)\}\{\\partial\\theta\_j\} \\\\ &=\\sum\_\{i=1\}^m(x\_j(h\_\\theta(x^\{(i)\})-y^\{(i)\})) \\\\ &=\\sum\_\{i=1\}^m(h\_\\theta(x^\{(i)\})-y^\{(i)\})x\_j^\{(i)\} \\\\ \\theta\_j&=\\theta\_j+\\alpha\\sum\_\{i=1\}^m(y^\{(i)\}-h\_\\theta(x^\{(i)\}))x\_j^\{(i)\} \\end\{aligned\} ∂θj∂J(θ)∂θj∂J(θ)θj=(hθ(x)−y)xj=i=1∑m∂θj∂J(θi)=i=1∑m(xj(hθ(x(i))−y(i)))=i=1∑m(hθ(x(i))−y(i))xj(i)=θj\+αi=1∑m(y(i)−hθ(x(i)))xj(i)  
（3）随机梯度下降算法（SGD）  
 ∂ J ( θ ) ∂ θ j = ( h θ ( x ) − y ) x j \\frac\{\\partial J(\\theta)\}\{\\partial\\theta\_j\}=(h\_\\theta(x)-y)x\_j ∂θj∂J(θ)=(hθ(x)−y)xj

for i=1 to m {

θ j = θ j + α ( y ( i ) − h θ ( x ( i ) ) ) x j ( i ) \\theta\_j=\\theta\_j+\\alpha(y^\{(i)\}-h\_\\theta(x^\{(i)\}))x\_j^\{(i)\} θj=θj\+α(y(i)−hθ(x(i)))xj(i)

}

（4）BGD和SGD算法比较  
SGD速度比BGD快，迭代次数少。  
SGD在某些情况下（全局存在多个相对最优解/J(θ)不是二次函数），SGD有可能跳出某些小的局部最优解，所以不会比BGD坏。  
BGD一定能够得到一个局部最优解（在线性回归模型中一定是得到一个全局最优解），SGD由于随机性的存在可能导致最终结果比BGD的差。  
注意：优先选择SGD。  
（5）小批量梯度下降法（MBGD）  
如果既需要保证算法的训练过程比较快，又需要保证最终参数训练的准确率，而这正是小批量梯度下降法（Mini-batch Gradient Descent，简称MBGD）的初衷。MBGD中不是每拿一个样本就更新一次梯度，而且拿b个样本（b一般为10）的平均梯度作为更新方向。

for i= 1 to m/10 {

θ j = θ j + α ∑ k = i i + 10 ( y ( k ) − h θ ( x ( k ) ) ) x j ( k ) \\theta\_j=\\theta\_j+\\alpha\\sum\_\{k=i\}^\{i+10\}(y^\{(k)\}-h\_\\theta(x^\{(k)\}))x\_j^\{(k)\} θj=θj\+αk=i∑i\+10(y(k)−hθ(x(k)))xj(k)

}

## 4、Logistic分类算法 ##

（1）Logistic/Sigmoid函数  
 p = h θ ( x ) = g ( θ T x ) = 1 1 + e − θ T x g ( z ) = 1 1 + e − z g ′ ( z ) = ( 1 1 + e − z ) ′ = e − z ( 1 + e − z ) 2 = 1 1 + e − z ⋅ e − z 1 + e − z = 1 1 + e − z ⋅ ( 1 − 1 1 + e − z ) = g ( z ) ⋅ ( 1 − g ( z ) ) \\begin\{aligned\} p&=h\_\\theta(x)=g(\\theta^Tx)=\\frac\{1\}\{1+e^\{-\\theta^Tx\}\} \\\\ g(z)&=\\frac\{1\}\{1+e^\{-z\}\} \\\\ g'(z)&=(\\frac\{1\}\{1+e^\{-z\}\})' \\\\ &=\\frac\{e^\{-z\}\}\{(1+e^\{-z\})^2\} \\\\ &=\\frac\{1\}\{1+e^\{-z\}\}\\cdot\\frac\{e^\{-z\}\}\{1+e^\{-z\}\} \\\\ &=\\frac\{1\}\{1+e^\{-z\}\}\\cdot(1-\\frac\{1\}\{1+e^\{-z\}\}) \\\\ &=g(z)\\cdot(1-g(z)) \\end\{aligned\} pg(z)g′(z)=hθ(x)=g(θTx)=1\+e−θTx1=1\+e−z1=(1\+e−z1)′=(1\+e−z)2e−z=1\+e−z1⋅1\+e−ze−z=1\+e−z1⋅(1−1\+e−z1)=g(z)⋅(1−g(z))  
（2）Logistic回归的极大似然函数  
假设：  
 P ( y = 1 ∣ x ; θ ) = h θ ( x ) P ( y = 0 ∣ x ; θ ) = 1 − h θ ( x ) P ( y ∣ x ; θ ) = ( h θ ( x ) ) y ( 1 − h θ ( x ) ) ( 1 − y ) \\begin\{aligned\} P(y=1|x;\\theta)&=h\_\\theta(x) \\\\ P(y=0|x;\\theta)&=1-h\_\\theta(x) \\\\ P(y|x;\\theta)&=(h\_\\theta(x))^y(1-h\_\\theta(x))^\{(1-y)\} \\end\{aligned\} P(y=1∣x;θ)P(y=0∣x;θ)P(y∣x;θ)=hθ(x)=1−hθ(x)=(hθ(x))y(1−hθ(x))(1−y)  
似然函数：  
 L ( θ ) = p ( y ⃗ ∣ X ; θ ) = ∏ i = 1 m p ( y ( i ) ∣ x ( i ) ; θ ) = ∏ i = 1 m ( h θ ( x ( i ) ) ) y ( i ) ( 1 − h θ ( x ( i ) ) ) ( 1 − y ( i ) ) \\begin\{aligned\} L(\\theta)&=p(\\vec\{y\}|X;\\theta) \\\\ &=\\prod\_\{i=1\}^\{m\}p(y^\{(i)\}|x^\{(i)\};\\theta) \\\\ &=\\prod\_\{i=1\}^\{m\}(h\_\\theta(x^\{(i)\}))^\{y^\{(i)\}\}(1-h\_\\theta(x^\{(i)\}))^\{(1-y^\{(i)\})\} \\end\{aligned\} L(θ)=p(y∣X;θ)=i=1∏mp(y(i)∣x(i);θ)=i=1∏m(hθ(x(i)))y(i)(1−hθ(x(i)))(1−y(i))  
对数似然函数：  
 l ( θ ) = log ⁡ L ( θ ) = ∑ i = 1 m ( y ( i ) log ⁡ h θ ( x ( i ) ) + ( 1 − y ( i ) ) log ⁡ ( 1 − h θ ( x ( i ) ) ) ) ∂ l ( θ ) ∂ θ j = ∑ i = 1 m ( y ( i ) h θ ( x ( i ) ) − 1 − y ( i ) 1 − h θ ( x ( i ) ) ) ⋅ ∂ h θ ( x ( i ) ) ∂ θ j = ∑ i = 1 m ( y ( i ) g ( θ T x ( i ) ) − 1 − y ( i ) 1 − g ( θ T x ( i ) ) ) ⋅ ∂ g ( θ T x ( i ) ) ∂ θ j = ∑ i = 1 m ( y ( i ) g ( θ T x ( i ) ) − 1 − y ( i ) 1 − g ( θ T x ( i ) ) ) ⋅ g ( θ T x ( i ) ) ( 1 − g ( θ T x ( i ) ) ) ⋅ ∂ θ T x ( i ) ∂ θ j = ∑ i = 1 m ( y ( i ) ( 1 − g ( θ T x ( i ) ) ) − ( 1 − y ( i ) ) g ( θ T x ( i ) ) ) ⋅ x j ( i ) = ∑ i = 1 m ( y ( i ) − g ( θ T x ( i ) ) ) ⋅ x j ( i ) \\begin\{aligned\} l(\\theta)&=\\log L(\\theta) \\\\ &=\\sum\_\{i=1\}^m(y^\{(i)\}\\log h\_\\theta(x^\{(i)\})+(1-y^\{(i)\})\\log(1-h\_\\theta(x^\{(i)\}))) \\\\ \\frac\{\\partial l(\\theta)\}\{\\partial\\theta\_j\}&=\\sum\_\{i=1\}^m(\\frac\{y^\{(i)\}\}\{h\_\\theta(x^\{(i)\})\}-\\frac\{1-y^\{(i)\}\}\{1-h\_\\theta(x^\{(i)\})\})\\cdot\\frac\{\\partial h\_\\theta(x^\{(i)\})\}\{\\partial\\theta\_j\} \\\\ &=\\sum\_\{i=1\}^m(\\frac\{y^\{(i)\}\}\{g(\\theta^Tx^\{(i)\})\}-\\frac\{1-y^\{(i)\}\}\{1-g(\\theta^Tx^\{(i)\})\})\\cdot\\frac\{\\partial g(\\theta^Tx^\{(i)\})\}\{\\partial\\theta\_j\} \\\\ &=\\sum\_\{i=1\}^m(\\frac\{y^\{(i)\}\}\{g(\\theta^Tx^\{(i)\})\}-\\frac\{1-y^\{(i)\}\}\{1-g(\\theta^Tx^\{(i)\})\})\\cdot g(\\theta^Tx^\{(i)\})(1-g(\\theta^Tx^\{(i)\}))\\cdot\\frac\{\\partial\\theta^Tx^\{(i)\}\}\{\\partial\\theta\_j\} \\\\ &=\\sum\_\{i=1\}^m(y^\{(i)\}(1-g(\\theta^Tx^\{(i)\}))-(1-y^\{(i)\})g(\\theta^Tx^\{(i)\}))\\cdot x\_j^\{(i)\} \\\\ &=\\sum\_\{i=1\}^m(y^\{(i)\}-g(\\theta^Tx^\{(i)\}))\\cdot x\_j^\{(i)\} \\end\{aligned\} l(θ)∂θj∂l(θ)=logL(θ)=i=1∑m(y(i)loghθ(x(i))\+(1−y(i))log(1−hθ(x(i))))=i=1∑m(hθ(x(i))y(i)−1−hθ(x(i))1−y(i))⋅∂θj∂hθ(x(i))=i=1∑m(g(θTx(i))y(i)−1−g(θTx(i))1−y(i))⋅∂θj∂g(θTx(i))=i=1∑m(g(θTx(i))y(i)−1−g(θTx(i))1−y(i))⋅g(θTx(i))(1−g(θTx(i)))⋅∂θj∂θTx(i)=i=1∑m(y(i)(1−g(θTx(i)))−(1−y(i))g(θTx(i)))⋅xj(i)=i=1∑m(y(i)−g(θTx(i)))⋅xj(i)  
Logistic回归θ参数的求解过程为（类似梯度下降方法，往正梯度方向迭代）。  
批量梯度下降算法（BGD）：  
 θ j = θ j + α ∑ i = 1 m ( y ( i ) − h θ ( x ( i ) ) ) x j ( i ) \\theta\_j=\\theta\_j+\\alpha\\sum\_\{i=1\}^m(y^\{(i)\}-h\_\\theta(x^\{(i)\}))x\_j^\{(i)\} θj=θj\+αi=1∑m(y(i)−hθ(x(i)))xj(i)  
随机梯度下降算法（SGD）：  
 θ j = θ j + α ( y ( i ) − h θ ( x ( i ) ) ) x j ( i ) \\theta\_j=\\theta\_j+\\alpha(y^\{(i)\}-h\_\\theta(x^\{(i)\}))x\_j^\{(i)\} θj=θj\+α(y(i)−hθ(x(i)))xj(i)  
（3）Logistic回归的损失函数  
 p i = h θ ( x ( i ) ) = 1 1 + e − θ T x ( i ) = 1 1 + e − f i L ( θ ) = ∏ i = 1 m p ( y ( i ) ∣ x ( i ) ; θ ) = ∏ i = 1 m p i y ( i ) ( 1 − p i ) 1 − y ( i ) l ( θ ) = ln ⁡ L ( θ ) = ∑ i = 1 m ln ⁡ \[ p i y ( i ) ( 1 − p i ) 1 − y ( i ) \] = ∑ i = 1 m ln ⁡ \[ ( 1 1 + e − f i ) y ( i ) ( 1 1 + e f i ) 1 − y ( i ) \] l o s s ( y ( i ) , y ( i ) ^ ) = − l ( θ ) = ∑ i = 1 m \[ y ( i ) ln ⁡ ( 1 + e − f i ) + ( 1 − y ( i ) ) ln ⁡ ( 1 + e f i ) \] = \{ ∑ i = 1 m ln ⁡ ( 1 + e − f i ) , y ( i ) = 1 ∑ i = 1 m ln ⁡ ( 1 + e f i ) , y ( i ) = 0 ⇒ l o s s ( y ( i ) , y ( i ) ^ ) = ∑ i = 1 m ln ⁡ ( 1 + e ( 1 − 2 y ( i ) ) θ T x ( i ) ) , y ( i ) = \{ 1 0 \\begin\{aligned\} p\_i&=h\_\\theta(x^\{(i)\}) \\\\ &=\\frac\{1\}\{1+e^\{-\\theta^Tx^\{(i)\}\}\} \\\\ &=\\frac\{1\}\{1+e^\{-f\_i\}\} \\\\ L(\\theta)&=\\prod\_\{i=1\}^mp(y^\{(i)\}|x^\{(i)\};\\theta) \\\\ &=\\prod\_\{i=1\}^mp\_i^\{y^\{(i)\}\}(1-p\_i)^\{1-y^\{(i)\}\} \\\\ l(\\theta)&=\\ln L(\\theta) \\\\ &=\\sum\_\{i=1\}^m\\ln\[p\_i^\{y^\{(i)\}\}(1-p\_i)^\{1-y^\{(i)\}\}\] \\\\ &=\\sum\_\{i=1\}^m\\ln\[(\\frac\{1\}\{1+e^\{-f\_i\}\})^\{y^\{(i)\}\}(\\frac\{1\}\{1+e^\{f\_i\}\})^\{1-y^\{(i)\}\}\] \\\\ loss(y^\{(i)\},\\hat\{y^\{(i)\}\})&=-l(\\theta) \\\\ &=\\sum\_\{i=1\}^m\[y^\{(i)\}\\ln(1+e^\{-f\_i\})+(1-y^\{(i)\})\\ln(1+e^\{f\_i\})\] \\\\ &=\\begin\{cases\}\\sum\_\{i=1\}^m\\ln(1+e^\{-f\_i\}), &y^\{(i)\}=1 \\\\ \\sum\_\{i=1\}^m\\ln(1+e^\{f\_i\}), &y^\{(i)\}=0\\end\{cases\} \\\\ \\Rightarrow loss(y^\{(i)\},\\hat\{y^\{(i)\}\})&=\\sum\_\{i=1\}^m\\ln(1+e^\{(1-2y^\{(i)\})\\theta^Tx^\{(i)\}\}), y^\{(i)\}=\\begin\{cases\}1 \\\\ 0\\end\{cases\} \\end\{aligned\} piL(θ)l(θ)loss(y(i),y(i)^)⇒loss(y(i),y(i)^)=hθ(x(i))=1\+e−θTx(i)1=1\+e−fi1=i=1∏mp(y(i)∣x(i);θ)=i=1∏mpiy(i)(1−pi)1−y(i)=lnL(θ)=i=1∑mln\[piy(i)(1−pi)1−y(i)\]=i=1∑mln\[(1\+e−fi1)y(i)(1\+efi1)1−y(i)\]=−l(θ)=i=1∑m\[y(i)ln(1\+e−fi)\+(1−y(i))ln(1\+efi)\]=\{ ∑i=1mln(1\+e−fi),∑i=1mln(1\+efi),y(i)=1y(i)=0=i=1∑mln(1\+e(1−2y(i))θTx(i)),y(i)=\{ 10

## 5、Softmax分类算法 ##

（1）Softmax回归的概率函数  
Softmax回归是Logistic回归的一般化，适用于K分类的问题，第k类的参数为向量 θ k \\theta\_k θk，组成的二维矩阵为 θ k ∗ n \\theta\_\{k\*n\} θk∗n。Softmax函数的本质就是将一个K维的任意实数向量压缩（映射）成另一个K维的实数向量，其中向量中的每个元素取值都介于（0，1）之间。  
Softmax回归的概率函数为：  
 p ( y = k ∣ x ; θ ) = e θ k T x ∑ l = 1 K e θ l T x , k = 1 , 2 , . . . , K p(y=k|x;\\theta)=\\frac\{e^\{\\theta\_k^Tx\}\}\{\\sum\_\{l=1\}^Ke^\{\\theta\_l^\{T\}x\}\}, k=1,2,...,K p(y=k∣x;θ)=∑l=1KeθlTxeθkTx,k=1,2,...,K  
（2）Softmax回归的似然估计  
似然函数：  
 L ( θ ) = ∏ i = 1 m ∏ k = 1 K p ( y = k ∣ x ( i ) ; θ ) y k ( i ) = ∏ i = 1 m ∏ k = 1 K ( e θ k T x ∑ l = 1 K e θ l T x ) y k ( i ) \\begin\{aligned\} L(\\theta)&=\\prod\_\{i=1\}^m\\prod\_\{k=1\}^Kp(y=k|x^\{(i)\};\\theta)^\{y\_k^\{(i)\}\} \\\\ &=\\prod\_\{i=1\}^m\\prod\_\{k=1\}^K(\\frac\{e^\{\\theta\_k^Tx\}\}\{\\sum\_\{l=1\}^Ke^\{\\theta\_l^Tx\}\})^\{y\_k^\{(i)\}\} \\end\{aligned\} L(θ)=i=1∏mk=1∏Kp(y=k∣x(i);θ)yk(i)=i=1∏mk=1∏K(∑l=1KeθlTxeθkTx)yk(i)  
对数似然函数：  
 l ( θ ) = ln ⁡ L ( θ ) = ∑ i = 1 m ∑ k = 1 K y k ( i ) ( θ k T x ( i ) − ln ⁡ ∑ l = 1 K e θ l T x ( i ) ) l ( θ ) = ∑ k = 1 K y k ( θ k T x − ln ⁡ ∑ l = 1 K e θ l T x ) \\begin\{aligned\} l(\\theta)&=\\ln L(\\theta) \\\\ &=\\sum\_\{i=1\}^m\\sum\_\{k=1\}^Ky\_k^\{(i)\}(\\theta\_k^Tx^\{(i)\}-\\ln\\sum\_\{l=1\}^Ke^\{\\theta\_l^Tx^\{(i)\}\}) \\\\ l(\\theta)&=\\sum\_\{k=1\}^Ky\_k(\\theta\_k^Tx-\\ln\\sum\_\{l=1\}^Ke^\{\\theta\_l^Tx\}) \\end\{aligned\} l(θ)l(θ)=lnL(θ)=i=1∑mk=1∑Kyk(i)(θkTx(i)−lnl=1∑KeθlTx(i))=k=1∑Kyk(θkTx−lnl=1∑KeθlTx)  
（3）Softmax回归的随机梯度  
 ∂ l ( θ ) ∂ θ k = y k x − e θ k T x ∑ l = 1 K e θ l T x x = ( y k − e θ k T x ∑ l = 1 K e θ l T x ) ⋅ x = ( y k − p ( y = k ∣ x ; θ ) ) ⋅ x \\begin\{aligned\} \\frac\{\\partial l(\\theta)\}\{\\partial\\theta\_k\}&=y\_kx-\\frac\{e^\{\\theta\_k^Tx\}\}\{\\sum\_\{l=1\}^Ke^\{\\theta\_l^Tx\}\}x \\\\ &=(y\_k-\\frac\{e^\{\\theta\_k^Tx\}\}\{\\sum\_\{l=1\}^Ke^\{\\theta\_l^Tx\}\})\\cdot x \\\\ &=(y\_k-p(y=k|x;\\theta))\\cdot x \\end\{aligned\} ∂θk∂l(θ)=ykx−∑l=1KeθlTxeθkTxx=(yk−∑l=1KeθlTxeθkTx)⋅x=(yk−p(y=k∣x;θ))⋅x

## 6、总结 ##

线性模型一般用于回归问题，Logistic和Softmax模型一般用于分类问题。  
求θ的主要方式是梯度下降算法，梯度下降算法是参数优化的重要手段，主要是SGD，适用于在线学习以及跳出局部极小值。  
Logistic/Softmax分类算法是实践中解决分类问题的最重要的方法。  
广义线性模型对样本要求不必要服从正态分布、只需要服从指数分布簇(二项分布、泊松分布、伯努利分布、指数分布等)即可；广义线性模型的自变量可以是连续的也可以是离散的。

[20200306221151179.png]: https://img-blog.csdnimg.cn/20200306221151179.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306205450104.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU=,size_16,color_FFFFFF,t_70