机器学习笔记Part2

一、分类问题简介

在所有的二分类问题中，期待输出的yyy都有两个值：0或者1

但是也有多分类问题的存在：y∈{1,2,3}y\in\{1,2,3\}y∈{1,2,3}。

Example：肿瘤预测

假设使用线性函数进行拟合，设置阈值为0.5，超过0.5认为肿瘤为阳性，低于0.5认为肿瘤为阴性。当数据呈现下面的分布时，得到的函数分类结果将会是糟糕的：

把线性回归直接应用于分类问题通常不是一个好主意。

对于二分类问题来说，分类的结果y=0y=0y=0或者111，但是如果采用线性回归的话，那么hθ(x)h_\theta(x)hθ​(x)可能是大于1或者小于0。接下来将开发一个名为logistics的回归算法，算法的输出值将一直处于0到1之间，并且不会超过1。

二、logistics回归算法

假设函数

希望0≤hθ(x)≤10\leq h_\theta(x)\leq 10≤hθ​(x)≤1，假设：
hθ(x)=g(θTx)g(z)=11+e−zh_\theta(x)=g(\theta^Tx)\\ g(z)=\frac{1}{1+e^{-z}} hθ​(x)=g(θTx)g(z)=1+e−z1​
我们将g(z)g(z)g(z)称为sigmod function，与logistics function同意。这两个术语是可以互换的，都指的是函数g(z)g(z)g(z)。将上述两个函数结合在一起，那么可以得到新的假设函数：
hθ(x)=11+e−θTxh_\theta(x)=\frac{1}{1+e^{-{\theta^T}x}} hθ​(x)=1+e−θTx1​

因为g(z)g(z)g(z)在0到1之间，所以新的假设函数的值也在0到1之间。下面要做的就是给θ\thetaθ选定一个值，假设会帮助我们做出预测。

模型的解释

输入x：输出为y=1的概率

在病人的特征为x的情况下，肿瘤是阳性的概率为70%。

同时，我们也可以得到y=0的概率，因为二者概率和为1.

决策边界

决策边界的概念帮助我们理解假设函数到底在计算什么。

在下图中，假设我们已经确定好了参数θ0\theta_0θ0​，θ1\theta_1θ1​和θ2\theta_2θ2​。此处，假设θ0=−3,θ1=1,θ2=1\theta_0=-3,\theta_1=1,\theta_2=1θ0​=−3,θ1​=1,θ2​=1。一旦三个参数得到了确定，决策边界（decision boundary）就得到了确定。

随着多项式变得复杂，特征变多，决策边界也会变得复杂，不再是直接使用一条线就能够分割，如下例子：

训练集是帮助我们来拟合参数θ\thetaθ的，并不是来确定决策边界的。但是一旦有了参数θ\thetaθ，决策边界就是确定的。

logistics回归的实现

代价函数的确定

假如我们的代价函数和之前线性回归一样，定义为：J(θ)=1m∑i=1m12(hθ(x(i))−y(i))2J(\theta)=\frac{1}{m}\sum_{i=1}^{m}\frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2J(θ)=m1​∑i=1m​21​(hθ​(x(i))−y(i))2，我们令cost(hθ(x(i))−y(i))=12(hθ(x(i))−y(i))2cost(h_\theta(x^{(i)})-y^{(i)})=\frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2cost(hθ​(x(i))−y(i))=21​(hθ​(x(i))−y(i))2。由于假设函数为hθ(x)=11+e−θTxh_\theta(x)=\frac{1}{1+e^{-{\theta^T}x}}hθ​(x)=1+e−θTx1​，最后代价函数会是“非凸函数”（non-convex），如果对于这样的函数使用梯度下降，将不能保证它收敛到全局最优解。

假如我们使用一个不是平方的函数定义这个代价函数，可能就能避免结果是非凸函数。下面我们就要寻找一个代价函数，使其为凸函数，能保证梯度下降最终收敛到最优解。

简化代价函数

logistics回归代价函数：
J(θ)=1m∑i=1mCost(hθ(x(i)),y(i))Cost(hθ(x(i)),y(i))={−log(hθ(x))ify=1−log(1−hθ(x))ify=0Note:y=1 or 0 alwaysJ(\theta)=\frac{1}{m}\sum_{i=1}^mCost(h_{\theta}(x^{(i)}),y^{(i)})\\ Cost(h_{\theta}(x^{(i)}),y^{(i)})=\begin{cases}-log(h_\theta(x))\quad if\ y=1\\ -log(1-h_{\theta}(x))\quad if\ y=0\end{cases}\\ \text{Note:y=1 or 0 always} J(θ)=m1​i=1∑m​Cost(hθ​(x(i)),y(i))Cost(hθ​(x(i)),y(i))={−log(hθ​(x))if y=1−log(1−hθ​(x))if y=0​Note:y=1 or 0 always
由于y总是不等于0就等于1，那么我们可以把上面的函数的形式进行改写，写成一个式子的形式：
Cost (hθ(x),y)=−ylog⁡(hθ(x))−(1−y)log⁡(1−hθ(x))\text { Cost }\left(h_\theta(x), y\right)=-y \log \left(h_\theta(x)\right)-(1-y) \log \left(1-h_\theta(x)\right)  Cost (hθ​(x),y)=−ylog(hθ​(x))−(1−y)log(1−hθ​(x))
综上，我们可以整理得到logistics回归的代价函数：
J(θ)=1m∑i=1mCost(hθ(x(i)),y(i))=−1m[∑i=1my(i)log⁡hθ(x(i))+(1−y(i))log⁡(1−hθ(1−hθ(x(i))))]J(\theta)=\frac{1}{m}\sum_{i=1}^mCost(h_{\theta}(x^{(i)}),y^{(i)})\\ =-\frac{1}{m}[\sum_{i=1}^my^{(i)}\log h_{\theta}(x^{(i)})+(1-y^{(i)})\log (1-h_\theta (1-h_\theta(x^{(i)})))] J(θ)=m1​i=1∑m​Cost(hθ​(x(i)),y(i))=−m1​[i=1∑m​y(i)loghθ​(x(i))+(1−y(i))log(1−hθ​(1−hθ​(x(i))))]
该代价函数是从极大似然法中得出的，该代价函数有个很好的属性就是该函数为convex function。

logistics回归的参数确定

logistics回归梯度下降公式：

公式的形式和线性回归相同，但是假设函数的形式被修改了。

• Debugging

  对于梯度下降是否正确的检测，我们仍可以采用绘制J(θ)J(\theta)J(θ)与迭代次数的图像来进行debugging。

• 特征缩放feature scaling

  线性回归找那个的特征缩放仍然适用于logistics回归

高级优化算法

使用这些高级优化算法，能够加快logistics回归的速度，并且更加适合解决大型机器学习问题。比如有大量的特征的模型。

对于梯度下降来说，我们只需要编写出代价函数J(θ)J(\theta)J(θ)和相应的偏导数∂∂θjJ(θ)\frac{\partial}{\partial \theta_j}J(\theta)∂θj​∂​J(θ)就可以得到梯度下降的算法。但是梯度下降并不是可以使用的唯一算法。

其他的优化算法

其他的优化方法：

• Gradient descent
• Conjugate gradient
• BFGS
• L-BFGS

优点：

• 不需要去选择学习率α\alphaα
• 通常比梯度下降收敛更快

缺点：

• 更加复杂

其他算法的应用例子

应用在logistics回归中：

下面是自行编写的python梯度下降、BFGS和L-BFGS的程序：

• 梯度下降

• BFGS

• L-BFGS

logistics在多分类中的应用

多分类问题的例子：

利用一对多的分类思想，我们可以将其应用在多分类问题上。

一对多分类原理

一对多分类原理有时也称作“一对余”方法。以下面的图为例子，我们将其转换为三个独立的二元分类问题：分别进行logistics回归，拟合出对应的分类器。

综上，我们通过logistics回归拟合得到了3个分类器：$h_\theta^{(1)}(x), h_\theta^{(2)}(x), h_\theta^{(3)}(x) $:
hθ(i)(x)=P(y=i∣x;θ)(i=1,2,3)h_\theta^{(i)}(x)=P(y=i|x;\theta)\tag{i=1,2,3} hθ(i)​(x)=P(y=i∣x;θ)(i=1,2,3)
最后我们给出一个新的输入值xxx，期望得到预测结果。我们需要做的就是将输入三个分类器中分别运行，最后从三个分类器中选择输出最大的那个，作为最后的预测结果，即：
max⁡ihθ(i)(x)\max_ih_\theta^{(i)}(x) imax​hθ(i)​(x)

三、过拟合与正则化

过拟合现象

过拟合：曲线可能过所有的样本点，但是面临函数变量太多，太过于庞大的问题。同时代价函数的代价值可能很低，但是也导致了它无法泛化到新的样本中，无法预测新的样本。这里的“泛化”指的是一个假设模型应用到新的样本的能力。

• 欠拟合，高偏差

• 过拟合，高方差

  

过拟合在logistics回归中的例子：

过拟合和欠拟合的识别

过拟合的处理

解决过拟合的处理方式：

• 尝试减少变量的数量
  • 人工检查变量
  • Model Selection Algorithm（later）
• 正则化 regularization
  • 保持所有的特征，但是减少梯度/θj\theta_jθj​的值
  • 当我们有很多变量时，每个变量都可能对最终的y值有些影响，此时正则化的方式就会变得很有效

正则化

正则化的思想

Intution：

将原来的代价函数中加入惩罚项：1000θ32+1000θ421000\theta_3^2+1000\theta_4^21000θ32​+1000θ42​，其中1000只是一个随机举例的比较大的数，加上惩罚项后，为满足代价函数最小化，最终求得的θ3\theta_3θ3​和θ4\theta_4θ4​都会约等于0，相当于拟合的函数为θ0+θ1x+θ2x2\theta_0+\theta_1x+\theta_2x^2θ0​+θ1​x+θ2​x2，实际上是一个二次函数。这是一种更好的假设模型。

通过这个例子，我们知道了加入惩罚项带来的效果。从某种意义上来说，这就是正则化背后的思想：较小的参数值，意味着得到一个更简单的假设模型，更不容易出现过拟合的问题。

Example：房价预测

特征：x1,x2,x3,...,x100x_1,x_2,x_3,...,x_{100}x1​,x2​,x3​,...,x100​

参数：θ0,θ1,...,θ100\theta_0,\theta_1,...,\theta_{100}θ0​,θ1​,...,θ100​
J(θ)=12m[∑i=1m(hθ(x(i))−y(i))+λ∑j=1mθj2]J(\theta)=\frac{1}{2m}[\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})+\lambda \sum_{j=1}^m\theta_j^2] J(θ)=2m1​[i=1∑m​(hθ​(x(i))−y(i))+λj=1∑m​θj2​]

其中λ∑j=1mθj2\lambda\sum_{j=1}^m\theta_j^2λ∑j=1m​θj2​是正则项，λ\lambdaλ是正则化参数。

λ\lambdaλ控制两个不同的目标之间的取舍。第一个目标，即前一项与训练的目标有关：最小化代价；第二个目标，即后一项则是使所有的参数尽可能的小，避免过拟合。

对于正则化参数λ\lambdaλ来说，如果：

• 设置得太大：对θi\theta_iθi​这些参数的惩罚力度太大，所有的参数都会接近于0，相当于把假设函数的所有参数都忽略了，最后假设模型只剩下一个θ0\theta_0θ0​，相当于用一条平行于x轴的直线去拟合。

  

  这样的模型偏差太大，是欠拟合的。

• 设置得太小：惩罚不够，可能会造成过拟合（overfitting）

线性回归中的正则化

线性回归中提到了两种方法：
线性回归{基于梯度下降基于正规方程线性回归\begin{cases}基于梯度下降\\ 基于正规方程\end{cases} 线性回归{基于梯度下降基于正规方程​
本节将这两种方法推广到正则化线性回归中

梯度下降的正则化

线性回归代价函数：
J(θ)=12m[∑i=1m(hθ(x(i))−y(i))+λ∑j=1nθj2]min⁡J(θ)J(\theta)=\frac{1}{2m}[\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})+\lambda\sum_{j=1}^n\theta_j^2]\\ \min J(\theta) J(θ)=2m1​[i=1∑m​(hθ​(x(i))−y(i))+λj=1∑n​θj2​]minJ(θ)
梯度下降：
repeat:{θj:=θj−α1m∑i=1m(hθ(x(i)−y(i))xj(i)(j=0,1,2,3,...,n)}repeat:\{ \theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)-y^{(i)}})x_j^{(i)}\qquad (j=0,1,2,3,...,n)\} repeat:{θj​:=θj​−αm1​i=1∑m​(hθ​(x(i)−y(i))xj(i)​(j=0,1,2,3,...,n)}
现将梯度下降写成下面所示形式（形式修改，内涵没变）：

考虑到加入正则化后，正则项未对θ0\theta_0θ0​进行处理，所以加入正则化后的梯度下降可以表示为下面的算法形式：
Gradient descent Repeat {θ0:=θ0−α1m∑i=1m(hθ(x(i))−y(i))x0(i)]θj:=θj−α[1m∑i=1m(hθ(x(i))−y(i))xj(i)+λmθj]}\begin{aligned} &\text {Gradient descent } \\ &\text {Repeat }\{ \\ &\left.\theta_0:=\theta_0-\alpha \frac{1}{m} \sum_{i=1}^m\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right) x_0^{(i)}\right] \\ & \theta_j:=\theta_j-\alpha\left[\frac{1}{m} \sum_{i=1}^m\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right) x_j^{(i)}+\frac{\lambda}{m} \theta_j\right] \\\}\end{aligned} }​Gradient descent Repeat {θ0​:=θ0​−αm1​i=1∑m​(hθ​(x(i))−y(i))x0(i)​]θj​:=θj​−α[m1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​+mλ​θj​]​
整理关于θj\theta_jθj​的项，得到下面的结果：
θj:=θj(1−αλm)−α1m∑i=1m(hθ(x(i))−y(i))xj(i)\theta_j:=\theta_j(1-\alpha\frac{\lambda}{m})-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} θj​:=θj​(1−αmλ​)−αm1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​
其中(1−αλm)(1-\alpha\frac{\lambda}{m})(1−αmλ​)是一个比1略小的项，所以梯度下降的结果在原来梯度下降的基础上使θj\theta_jθj​又变小了一点。

正规方程的正则化

矩阵不可逆：

假设m≤nm\leq nm≤n，θ=(XTX)−1XTy\theta=(X^TX)^{-1}X^Tyθ=(XTX)−1XTy —— 矩阵XTXX^TXXTX不可逆，如果使用pinv()函数，那么最后得到的解不会是最优的假设模型。但是在正则化中考虑到了这个问题：

如果 λ>0\lambda >0λ>0
θ=(XTX+λ[011⋱1])−1XTy\theta=\left(X^T X+\lambda\left[\begin{array}{lllll} 0 & & & & \\ & 1 & & & \\ & & 1 & & \\ & & & \ddots & \\ & & & & 1 \end{array}\right]\right)^{-1} X^T y θ=⎝⎛​XTX+λ⎣⎡​0​1​1​⋱​1​⎦⎤​⎠⎞​−1XTy
那么矩阵：(XTX+λ[011⋱1])\left(X^T X+\lambda\left[\begin{array}{lllll} 0 & & & & \\ & 1 & & & \\ & & 1 & & \\ & & & \ddots & \\ & & & & 1 \end{array}\right]\right)⎝⎛​XTX+λ⎣⎡​0​1​1​⋱​1​⎦⎤​⎠⎞​一定是可逆的，不是奇异矩阵。故，使用正则化也会解决一些出现不可逆的问题。

上述则是使用正则化解决线性回归的过程。

logistics回归中的正则化

梯度下降的正则化

将梯度下降进行修改后可以得到：（注意，假设函数与线性回归相比发生了改变）

高级优化算法的正则化

• 定义costFunction()：参数是向量θ\thetaθ
• 将costFunction()作为参数，传入fminunc()中