week 3

1.logistic regression(classification)
 采用之前的肿瘤问题如下图所示：
 ![](https://leanote.com/api/file/getImage?fileId=5979352bab64414c1600032d)
 此时若采用线性回归，以线性的hypothesis拟合，当最右边的training sample加入的时候曲线会明显的右偏，导致拟合效果变差，而且在本问题中y的取值只有0和1，采用线性的曲线明显超过了0和1的界限。
 
 
 2.hypothesis representation
 为了解决1中提出的问题，在这里我们采用logistic regression model来描述边界曲线，在原有的$h_\theta(x)$的hypothesis变为$g(\theta^TX)$,其中X代表特征向量，g代表logic function，在这里我们采用$g(z)=\frac 1 {1+e^{-z}}$,该函数的图像为：
 ![](https://leanote.com/api/file/getImage?fileId=5979352bab64414c1600032e)
 所以最终的hypothesis变为:$h_\theta(x)=\frac 1 {1+e^{-\theta^TX}}$
 h的作用就是对于给定的变量x，根据选择的参数$\theta$确定输出变量y=1的可能性，即：$h_\theta(x)=P(y=1|x;\theta)$
 
 
 3.decision boundary
 现有：![](https://leanote.com/api/file/getImage?fileId=5979352bab64414c1600032f)
 对于本模型，提出一个拟合模型：$h_\theta(x)=g(\theta_0+\theta_1x_1+\theta_2x_2)$,并且令$\theta_0,\theta_1,\theta_2$分别为-3，1，1，也就是说参数向量$\theta$为$$
 \begin {bmatrix}
 -3\\1\\1
 \end {bmatrix}
 $$
 在此情况下显然x1+x2=3,通过绘制这条直线可以清楚地拟合decision boundary。
 
 
 4.cost function
 对于上节提到的肿瘤问题，现条件如下图：
 ![](https://leanote.com/api/file/getImage?fileId=59795d6fab644149e0000a06)
在linear regression中我们采用的是modeling error 的平方和的形式，但是由于本例中的hypothesis带入到cost function中后出现的可能是non-convex function，如下图所示，
![](https://leanote.com/api/file/getImage?fileId=59795d6fab644149e0000a07)
存在多个局部最优解，所以我们重新定义logistic regression的cost function为：
$J(\theta)=\frac 1 m \sum \limits ^m _{i=1}Cost(h_\theta(x^{(i)}),y^{(i)})$
其中$Cost(h_\theta(x^{(i)}),y^{(i)})$定义为：
![](https://leanote.com/api/file/getImage?fileId=59795d6fab644149e0000a08)
$h(\theta)与Cost(h_\theta(x^{(i)}),y^{(i)})$的关系如下图所示：
![](https://leanote.com/api/file/getImage?fileId=59795d6fab644149e0000a09)
这样构建的特点是：当实际的y为1且$h_\theta$也为1时误差为0，当y为1且$h_\theta$不为1时，误差随着$h_\theta$变小而变大；当实际的y为0且$h_\theta$也为0时代价为0，当y为0且$h_\theta$不为0时，误差随着$h_\theta$变大而变大。
为了简化上述表达式，将2个方程通过极大似然估计的方法整理到一个方程中，整理后的结果如下：
$Cost(h_\theta(x),y)=-ylog(h_\theta(x^{(i)}))-(1-y)log(1-h_\theta(x^{(i)}))$
带入cost function中得到：
$J(\theta)=-\frac 1 m[\sum \limits ^m_{i=1}y^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))]$
得到这个代价方程后我们可以用梯度下降的方式来计算代价最小的$\theta$了，算法为：
repeat:
{
    $\theta _j:=\theta _j-\alpha\mathrm{\frac d {d\theta_j}}J(\theta)$
}
求导后得到：
{
    $\theta _j:=\theta _j-\alpha \frac 1 m \sum \limits ^m _{i=1}(h_ \theta (x^{(i)})-y^{(i)})x^{(i)} _j$
    }
虽然得到的算法与线性回归中的梯度下降是一样的，但是由于这里的$h_\theta(x)=g(\theta^TX)$与线性回归不同，所以这两者实际上是不一样的。

5.simple cost function and gradient decent
在这里我们采用一种简单的方式来写cost function，并且利用梯度下降来拟合出合适的$\theta$。
这是我们之前求出的cost function：
$J(\theta)=-\frac 1 m[\sum \limits ^m_{i=1}y^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))]$
将此式应用于递归下降中，得到：
repeat
{
    $\theta_j:=\theta_j-\alpha \sum \limits ^m_{i=1} (h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}
    $
}
如果有n个特征，也就是说$$\theta=\begin{bmatrix}
\theta_1\\ \theta_2\\\theta_3\\...\\\theta_n
\end{bmatrix}
$$
那必须同时更新所有的$\theta$值，为了实现这一目标，可以采用for循环或者将其向量化。

6.advanced optimization
本节的目的是通过一些高级的优化算法来在运算上代替梯度下降算法，进而加快逻辑回归的执行速度。
首先换个角度来看梯度下降，在有了代价方程$J(\theta)$后，我们要将其最小化，也就是分别求出$J9\theta)对于\theta_0,\theta_1...\theta_n$的偏导数$\frac {\mathrm{d}} {\mathrm{d\theta_\theta}}$,在求得了这些之后，我们要做的就是逐步等待这些参数完成迭代，为了加速这一过程，我们可以采用共轭梯度、BFGS（变尺度法）和L-BFGS（限制变尺度法）。使用这几种算法的好处在于无需手动配置学习速率，他们会自动选择一个合适的$\alpha$。
以一个例子来在octave中实现这些：
假设cost function的参数有2个，$\theta_1和\theta_2$,代价方程和对应的偏导如下图：
![](https://leanote.com/api/file/getImage?fileId=597aa87aab64410fae000822)
为了得到$J(\theta)$，我们在octave中采用如下封装好的函数来执行梯度下降算法，如下图所示：
![](https://leanote.com/api/file/getImage?fileId=597aa87aab64410fae000823)
执行结果会返回两个值，其中返回的第二个值为梯度值，应该是一个2*1的列向量，在得到了代价方程后，就可以调用更高级的优化函数fminunc了，调用方法如下：
![](https://leanote.com/api/file/getImage?fileId=597aa87aab64410fae000820)
参数中的'on'为打开梯度计算，需要设置一个梯度以及最大迭代次数。'@'为指针符号，指向刚才得到的代价方程，经过执行后会返回合适的参数值以及代价等信息。

7.multiclass classification-one versus all
假设存在如下图所示的分类情况：
![](https://leanote.com/api/file/getImage?fileId=597aa87aab64410fae000824)
现存在一个训练集，有3个类别，如上图，分别用y=1，y=2，y=3来表示3中符号，从y=1开始，我们可以构建一个伪训练集，如下图：
![](https://leanote.com/api/file/getImage?fileId=597aa87aab64410fae000821)
也就是将class 1当做一类，将剩下的部分当做另一类，把这个模型记作$h_\theta^{(1)}(x)$,并以此类推，得到$h_\theta^{(2)}(x)$和$h_\theta^{(3)}(x)$，最后将这一系列模型简记为：
$h_\theta^{(i)}(x)=p(y=i|x;\theta)$
最后要做的就是在3个分类器中同时输入训练集，选择一个最大的$h_\theta ^{(i)}(x)$。

8.regularzation
首先我们来讨论一下过拟合(over-fitting)问题，以下图一个回归问题为例：
![](https://leanote.com/api/file/getImage?fileId=597d9167ab64410be00012d5)

从图中可以看出来，第一个模型为线性回归，欠拟合，无法比较精确地描述training set；而第三个模型为四次方程，虽然它很好地拟合了training set，但是过于强调拟合数据，而失去了算法的本质。
在分类问题中也存在同样的问题，如下图所示：
![](https://leanote.com/api/file/getImage?fileId=597d9167ab64410be00012d4)
可以看出来，x的指数越高，拟合的效果越好，但是对之后的预测能力可能也就会变得越差。
所以遇到了过拟合的问题时，我们通常采用以下方法进行处理：
① 丢弃一些不能帮助我们正确预测的特征，可以手动选择保留的特征，或者采用某些特定的算法来帮忙，比如PCA。
② regularzation，保留所有的特征，但是减少参数的magnitude。

9.cost function
上述回归问题我们的模型是：
$h_\theta(x)=\theta_0+\theta_1x+\theta_2x^2+\theta_3x^3+\theta_4x^4$
之前我们分析出了正是由于高次项导致了拟合的不完美，所以如果能使高次项系数接近0的话就可以比较成功的拟合了，由此我们可以将高次项的$\theta_3和\theta_4$赋以较高的系数，分别都赋予1000和1000，修改后的cost function如下：
![](https://leanote.com/api/file/getImage?fileId=597ee39cab64416674001a4a)
这样修改后的cost function选择出的$\theta_3和\theta_4$对方程的影响就比以前小了很多，但是假如我们有非常多的特征，我们并不知道选择哪个参数进行penalty，所以在后方附上一项$\lambda \sum \limits ^n _{j=1}\theta_j ^2$,这样的就得到了一个较为简单的防止过拟合的hypothesis：

![](https://leanote.com/api/file/getImage?fileId=597ee39cab64416674001a4b)
其中$\lambda$被称作正则化参数(regularization parameter)，按照惯例，我们不对$\theta_0$进行惩罚，处理后的模型对比如下图所示：
![](https://leanote.com/api/file/getImage?fileId=597ee39cab64416674001a49)
如果$\lambda$过大就会导致所有的参数都最小化了，导致模型变为$h_\theta(x)=\theta_0$，造成欠拟合。

10.regularized linear regression
对于线性回归的问题，我们现在有两种解决方法，一种是梯度下降，另一种是基于正规方程，正则化线性回归的代价方程为：
$J(\theta)=\frac 1 {2m}[\sum \limits ^m _{i=1}(h_\theta(x^{(i)})-y^{(i)})^2+\lambda \sum \limits^n _{j=1}\theta _j ^2)]$
如果我们要使用梯度下降的方法来最小化代价函数，由于我们未对$\theta_0$进行正则化，所以梯度下降算法分为以下两种情况：
repeat until convergence

{
    $$
    \theta_0:=\alpha \frac 1 m \sum \limits ^m _{i=1}((h_\theta(x^{(i)}-y^{(i)}).x_0 ^{(i)})
    $$
    $$
    \theta_j:=\theta_j-\alpha \frac 1 m \sum \limits ^m _{i=1}((h_\theta(x^{(i)}-y^{(i)}).x_j^{(i)}+\frac \lambda m\theta_j)
    $$
}
将第二个式子进行调整可得：
$$
\theta_j:=(1-\alpha\frac \lambda m)-\alpha \frac 1 m \sum \limits ^m _{i=1}(h_\theta(x^{(i)}-y^{(i)}).x_j^{(i)}
$$
可以看出来梯度下降算法的变化在于额外减少的$\alpha\frac \lambda m$，在每次下降算法更新数据后令$\theta$在基础上减少了一个额外的值。
我们也可以使用正规方程来处理正则化线性回归模型，方法如下图：
![](https://leanote.com/api/file/getImage?fileId=5981360eab64413b6d00052d)
可以看出来本公式是在原来的基础上增加了一项![](https://leanote.com/api/file/getImage?fileId=5981360eab64413b6d00052a)
,增加这一项的目的是保证括号内的矩阵存在逆阵。

11.regularized logistic regression
针对逻辑回归问题，我们在之前已经知道有两种优化算法：第一种是使用gradient decent来优化cost function，或者在接下来使用更高级的算法来进行优化，这些高级算法需要你自己设计cost function；第二种将cost function进行regularization，得到如下所示的代价函数：
![](https://leanote.com/api/file/getImage?fileId=5981360eab64413b6d00052b)
通过求偏导来最小化代价函数，算法如下：
![](https://leanote.com/api/file/getImage?fileId=5981360eab64413b6d00052c)
虽然看起来和线性回归很像，但是$h_\theta(x)=g(\theta^TX)$，所以存在区别，另外$\theta_0$在两者中不参与正则化。