分类问题(Classification)
首先什么是分类问题?分类问题就是预测的值是离散的,比如是否是垃圾邮件(是/不是),肿瘤是否是良性(是/不是)等等,我们该用什么方法去解决分类问题呢?使用线性回归是否合适?
在week1/2的课程中主要探讨了"回归问题,预测连续值",我们使用线性回归可以很好的来预测结果,但是很遗憾线性回归不能用于解决分类问题,比如:
使用线性回归解分类问题有几点很奇怪的地方:
1.线性回归函数是条尽量拟合所有样本的直线,上图中可以观察到对于某些样本可能会存在或者这种情况, 但是对于这个分类问题,结果只能是[0,1]
2.上图中采用了阈值分类,即这种情况被认为是恶性肿瘤,被认为是良性,在现有的样本中工作的很棒,但是如果新增一个tumor size非常大的样本,会导致线性回归函数斜率更低(紫色->蓝色),那么此时阈值=0.5就会得出和之前训练结果完全不同的值,这也是不合理的.(就我自己的理解是因为分类问题中预测结果的性质有很大的不同,预测结果为0和1完全是两码事,所以这里用预测连续值的线性回归不合适,如果是预测连续值比如房价那种,你加入新的样本,即使这个样本很离群,也一定程度上改变了线性回归函数,但是无所谓,因为本质上都是预测房价,100w和80w也没啥差别,但是肿瘤良性恶性就差别大了,属于性质完全不同的结果).
Logistic Regression
虽然是叫做Logistic Regression但是它是一个解决分类问题的算法,Logistic Regression的如下:
其中g(z)被称为Sigmoid Function或者叫Logistic Function.
由上图可知,Logistic Function可以把任意值映射到[0,1]的范围,完美契合了分类问题的情况,但是还是有一点比较尴尬,就是怎么理解的这些值,比如说,我们可以理解为该样本预测结果为1的概率是70%(则该样本预测结果为0的概率是30%),我们记作:
总结:在Logistic Regression中,的值是样本x预测结果为1的概率.
比较:在Linear Regression中,的值是样本x的预测值.
Decision Boundary
接上面,但是毕竟分类问题是要解决给定样本究竟是那种类型的问题,你不能说这个样本有70%的概率是1这样子,于是我们有如下规定:
--> y=1
--> y=0
那么则有:
--> y=1
--> y=0
所谓Decision Boundary就是分割开y=1和y=0区域的线,接下来看两个例子:
1.
则有,--> y=1,即when then y = 1, else y = 0;
图形如下,图中的直线即是的Decision Boundary
2.如下图所示
Cost Function
Logistic Regression的代价函数和Linear Regression是不一样的,如果使用之前的代价函数:
我们将带入其中会发现得到的代价函数是non-convex的,这意味着无法使用梯度下降算法得到global的最优解.
所以,对于Logistic Regression的代价函数我们定义如下:
if y=1
if y=0
从直觉上来理解这个代价函数应该是:如果y=1,但是趋近于0(回忆之前提到了Logistic Regression的假设函数是y=1的概率),这种情况等于是说根据得出y=1的概率无限小,所以需要代价函数付出无限大的代价才能让y=1;y=0的情况亦然.
Simplified Cost Function and Gradient Descent
简化后的如下:
将其带入代价函数中可得:
梯度下降算法
可以注意到Logistic Regression的梯度下降算法和Linear Regression的一致,但是的取值实际上是不同的,此外Logistic Regression的梯度下降算法也可以用Feature Scaling来加快其收敛速度.
Advanced Optimization
除了梯度下降算法之外还有"Conjugate gradient", "BFGS", and "L-BFGS"算法都可以来求合适的使得最小,他们有共同的优点:
1.不需要设置
2.通常情况下比梯度下降更快
缺点:
1.实现非常复杂
一般情况下我们不会亲自去实现这些算法,使用一些包装好的api会是更好的选择,比如使用octave的fminunc函数.
fminunc
使用fminunc函数的方法如下:
step1.定义costFunction
function [jVal, gradient] = costFunction(theta)
jVal = [...code to compute J(theta)...];
gradient = [...code to compute derivative of J(theta)...];
end
step2.初始化参数并且调用fminunc
options = optimset('GradObj', 'on', 'MaxIter', 100);
initialTheta = zeros(2,1); % 根据实际情况
[optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);
optTheta即优化后的
Multiclass Classification: One-vs-all
之前讨论的分类问题都是都是简单的非此即彼的问题,即y={0,1},现实生活中的分类问题更加复杂,比如邮件分类(来自陌生人/好友/家人/同事,y={0,1,2,3})之类的,对于这种Muticlass classification的问题我们采用One-vs-all(One-vs-rest)的策略,即选定y=0的样本,将其他y!=0的样本都归为另一类,这样我们可以得到,so on so forth,最后所对应的i即是分类的结果,如下图:
The Problem of Overfitting
- 左边这张图没有很好的拟合训练样本,我们称之为"under fitting"或者"high bias",一般是由于太简单或者说使用的特征太少导致的.这种情况没办法很好的拟合训练样本所以你也不指望它能很好的作出预测.
- 右边这张图过度的拟合训练样本,我们称之为"over fitting"或者"high variance",一般是由于太复杂以至于出现了太多没有必要的曲线和角度.这种情况非常精确的拟合了训练样本但是丧失了一般性,对于新样本的预测不靠谱.
Regularization
Cost Function
假设我们有
如上图,对于如上图的训练样本,其实就能拟合的很好了,但是我们为了不改变原有的形式,只能削弱对与的影响,具体方法就是在原来的Cost Function后面加上,这样为了使得Cost Function最小,那么也要小,即->0,那么的图形就会和非常的类似.
那么一般来说,如果样本特征种类非常多,非常复杂,我们也不知道究竟是哪些\theta使得 overfitting,所以干脆将所有\theta都追加到Cost Function中,即:
注意此处没有包涵,其中被称为Regularization Parameter,当无限大的时候,->0,此时,这种情况就是underfitting,当
无限小的时候,几乎不会有变化,此时也不会起到很好修正overfitting的作用.
Regularized Linear Regression
Gradient Descent
将Regularization应用与Linear Regression的梯度下降算法中,如下:
对稍微做下转换可得:
Normal Equation
将Regularization应用与Linear Regression的Normal Equation算法中,如下:
其中L是一个(n+1)*(n+1)的矩阵(和Identity很类似除了对角线第一个值是0),为什么对角线第一个是0而不是1,从直觉上来说是因为我们实际上并没有.再有,之前我们探讨过当m<n时,一定不可逆,m=n时有几率不可逆,但是无论在哪种情况下一定可逆.