2018年9月版本

Week 3

分类 Classification

• 二元分类，对于结果y，只有$y\in{\{0,1\}}$y∈{0,1}，0代表负类（某事物不存在），1代表正类（某事物存在），这种分类往往并不精确，但是对于客体来讲无关紧要
• 多元分类即y的结果有若干个
• 对于线性回归，应用二元分类往往不是很好，因为y只取0和1，但是很可能预测结果会远大于1或者远小于0
• 可以使用逻辑回归，其预测结果一定会在0到1之间
• 结论：回归和分类不能使用同一种模式去解题

逻辑回归 Logistic Regression

• 模型基本要求：输出值在0到1之间

• $h_{\theta}(x)=g(\theta^Tx),\;g(z)=\frac{1}{1+e^{-z}}$hθ​(x)=g(θTx),g(z)=1+e−z1​

• 上述g成为sigmoid函数，或者逻辑函数

• $h_{\theta}(x)$hθ​(x)的输出，认为是对于输入x，估计y=1的概率，即$h_{\theta}(x)=P(y=1|x;\theta)$hθ​(x)=P(y=1∣x;θ)
• 由上，$P(y=0|x;\theta)=1-P(y=1|x;\theta)$P(y=0∣x;θ)=1−P(y=1∣x;θ)

决定边界 Decision Boundary

• 假设函数的一种属性
• 用来划定分类结果所在的区域
• 对于一个逻辑回归$h_{\theta}(x)=g(z)$hθ​(x)=g(z)，如果我们认为分类的界限在$z=0$z=0，那么可以到处一个界限$z=0$z=0，这个界限就是决定边界，大于0为正，小于0为负

代价函数 Cost Function

• 在逻辑回归中，差的平方和这一函数会变成非凸函数，导致有过多的局部最优解，梯度下降无法保证代价函数找到全局最小值

• 代价函数的基本目标：对代价函数$J(\theta)=\frac{1}{m}\sum\limits_{i=1}^{m}Cost(h_{\theta}(x),y)$J(θ)=m1​i=1∑m​Cost(hθ​(x),y)，应当寻找一个函数Cost，能够使得J可以通过梯度下降得到最优解

• 逻辑回归中的Cost：$Cost(h_{\theta}(x),y)= \left\{ \begin{array}{lr} -\log (h_{\theta}(x)) \; if \; y=1 & \\ -\log (1-h_{\theta}(x)) \; if \; y=0 & \end{array} \right.$Cost(hθ​(x),y)={−log(hθ​(x))ify=1−log(1−hθ​(x))ify=0​​

  • y=1时，如果预测结果为1，那么代价为0（认为绝对正确），此时，结果越趋近于0，代价就越大，甚至趋近于无穷大（认为绝对错误）

  • 

  • y=0时，如果预测结果为0，那么代价为0，此时，结果越趋近于1，代价就越大，甚至趋近于无穷大

  • 需要注意的是，除了预测结果恰等于y时，代价为0，其余情况下，代价均为正值

  • 

简化代价函数与梯度下降

• 上述Cost函数的简写形式：$Cost(h_{\theta},y)=-y\log(h_{theta}(x))-(1-y)\log(1-h_{\theta}(x))$Cost(hθ​,y)=−ylog(htheta​(x))−(1−y)log(1−hθ​(x))
• 代价函数：$J(\theta)=-\frac{1}{m}[\sum\limits_{i=1}^{m}y^{(i)}\log(h_{\theta}(x^{(i)}))+(1-y^{(i)})\log(1-h_{\theta}(x^{(i)}))]$J(θ)=−m1​[i=1∑m​y(i)log(hθ​(x(i)))+(1−y(i))log(1−hθ​(x(i)))]
• 这个代价函数定义，可以利用极大似然估计的规则进行求导，同时是一个凸函数，可以很好的拟合逻辑回归模型
• 梯度下降过程的公式：$\theta_j:=\theta_j-\alpha\sum\limits_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_j^{(i)}$θj​:=θj​−αi=1∑m​(hθ​(x(i))−y(i))xj(i)​
• 上述优化式和线性回归的内容形式一致，但是假设函数本身不同

高级优化方法

• 共轭梯度法 Conjugate Gradient

• 变尺度法 BFGS

• 限制变尺度法 L-BFGS

• 优点：

  • 不需要手动选择学习率
  • 比梯度下降更快地收敛

• 缺点：

  • 更加复杂

多元分类 Multiclass Classification

• 结果值超过两个类别的分类问题

一对多的分类（一对余） One-vs-all (one-vs-rest)

• 以三个类别为例，可以将三个类别的分类问题，处理成三组二元分类问题
• 对应的公式：$h_{\theta}^{(i)}(x)=P(y=i|x;\theta)$hθ(i)​(x)=P(y=i∣x;θ)
• 基本目标：针对每一个类i训练一个逻辑回归分类器$h_{\theta}^{(i)}(x)$hθ(i)​(x)，以对每一个y=i的可能性进行预测
• 对每一个新的输入x，对每一个$h_{\theta}^{(i)}(x)$hθ(i)​(x)进行预测，取最大的结果作为最终的分类结果

过拟合 Overfitting

• 欠拟合（underfitting），又称高偏差（High Bias），即没有很好地拟合训练数据，效果较差

• 过拟合（overfitting），又称高方差（High Variance），即能够拟合几乎所有所有的训练数据，可能出现函数过于庞大的问题，以至于无法泛化到新的数据上

• 解决过拟合的方法：

  • 减少特征数量（人工筛选或者使用选择算法）（丢弃特征意味着可能丢失信息）
  • 正规化（保留所有的特征，但是减小参数的数量级或者数值大小）

正规化 Regularization

• 基本思路：如果我们将参数变得比较小，就意味着
  • 假设函数更加简单
  • 更不容易过拟合
• 通过修改代价函数来减小所有参数的数值（因为无法先验挑选，只能全部减小）
• 修改后的式子（线性回归）：$J(\theta)=\frac{1}{2m}[\sum\limits_{i=1}^{m}(h_{\theta}(x^{(i)}-y^{(i)}))^2+\lambda\sum\limits_{j=1}^{n}\theta_j^2]$J(θ)=2m1​[i=1∑m​(hθ​(x(i)−y(i)))2+λj=1∑n​θj2​]
• 式子后面新加的部分称为正规化项，其中的正规化参数λ用于控制两个目标的相互平衡：
  • 训练假设函数能够更好的拟合数据
  • 保持参数数值较小
• 正规化系数不能过大，否则会造成所有的参数（不包括$\theta_0$θ0​）都非常小，造成严重的欠拟合

正规化线性回归 Regularized Linear Regression

• 对正规化的代价函数，有新的梯度下降公式：$
  \begin{equation}
  \left{
  \begin{array}{lr}
  \theta_0:=\theta_0-\alpha\frac{1}{m}\sum\limits_{i=1}^{{m}(h_{\theta}(x}{(i)})-y^{(i)})x_0{(i)} & \
  \theta_j:=\theta_j-\alpha[\frac{1}{m}\sum\limits_{i=1}^{{m}(h_{\theta}(x}{(i)})-y^{(i)})x_j{(i)}+\frac{\lambda}{m}\theta_j] &
  \end{array}
  \right.
  \end{equation}$
• 后一项合并后得到$\theta_j:=\theta_j(1-\alpha\frac{\lambda}{m})-\alpha\frac{1}{m}\sum\limits_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_0^{(i)}$θj​:=θj​(1−αmλ​)−αm1​i=1∑m​(hθ​(x(i))−y(i))x0(i)​
• 对于系数$(1-\alpha\frac{\lambda}{m})$(1−αmλ​)，实际情况下，分数项会是一个非常小的正值，因此每一次更新，参数都会被缩小一点点
• 对正规化的代价函数，有新的正规方程：$\bold{\theta}=(X^TX+ \lambda \begin{bmatrix} 0&&&&\\&1&&&\\&&1&&\\&&&\ddots&\\&&&&1\end{bmatrix})^{-1}X^Ty$θ=(XTX+λ⎣⎢⎢⎢⎢⎡​0​1​1​⋱​1​⎦⎥⎥⎥⎥⎤​)−1XTy
• 上述正规方程不可逆的情况，有m不大于n的情况，但只要λ大于0，上式可以证明可逆

正规化逻辑回归 Regularized logistic Regression

• 正规化的代价函数：$J(\theta)=-[\frac{1}{m}\sum\limits_{i=1}^{m}y^{(i)}\log(h_{theta}(x^{(i)}))+(1-y^{(i)})\log(1-h_{\theta}(x^{(i)}))]+\frac{\lambda}{2m}\sum\limits_{j=1}^{n}\theta_j^2$J(θ)=−[m1​i=1∑m​y(i)log(htheta​(x(i)))+(1−y(i))log(1−hθ​(x(i)))]+2mλ​j=1∑n​θj2​
• 新的梯度下降公式：$\left\{ \begin{array}{lr} \theta_0:=\theta_0-\alpha\frac{1}{m}\sum\limits_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_0^{(i)} & \\ \theta_j:=\theta_j-\alpha[\frac{1}{m}\sum\limits_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda}{m}\theta_j] & \end{array} \right.$⎩⎪⎨⎪⎧​θ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​]​​