Classification and Representation
Classification
此小节主要讲了哪些情况下需要使用分类模型，以及为什么线性回归模型不能很好的解决分类问题。
Andrew举了一个例子来说明为什么线性回归模型不能很好地解决分类问题。如下图：
由上图可知，如果我们要对tumor进行分类(malignant or benign?)那么就需要设定一个阈值(threshold), 比如此例设定为0.5，当y>=0.5时，我们认为就是1，即malignant，同理y<0.5时，就认为是0，即benign。貌似也可以去做预测啊，我们接着看下幅图：
当我们的样本数据有了新的数据后，我们的线性回归模型曲线会调整角度，但此时，如果仍然以0.5为阈值的话，显然有一部分数据就会预测错误。
直观上，从图形上看也能看出来，线性模型的曲线（直线）很难很好的拟合样本。
因此，在这节课开始，将引入logistic regression。
另外有几个概念，要知晓。
两分类的问题我们也叫做binary classification problem。而如果是更多分类类型，则叫做multi-class classification problem。
而在binary classification问题中，通常分为0和1， 0代表negative class， 1代表positive class。
Hypothesis Representation
sigmoid function
我们期望我们的模型输出为0到1之间的数值，从而可以分类为0或1.因此我们的模型需要满足如下条件：
0<=h(θ)<=1
数学中有一个函数恰好可以实现这种操作，即给定一个参数，会输出0~1之间的数值，这就是sigmoid function 或者叫做logistic function，这个function的定义如下：
下面我们可以把我们之前的线性模型的输出结果作为参数传递给该sigmoid函数，这样其输出就可以变为0~1之间的数值。因此，将h(θ)代入z就有如下公式:
最终其函数曲线如下：
hypothesis interpretation
我们sigmoid化后的假设其输出是一个0~1的数值，而这个数值显示的其实是一个概率。这个概率就是预测y=1的概率。那么，相应的y=0的概率就是1-h(x)。我们也可以如下表示：
统计概率的表示法，
P(y =1 | x; θ)表示当取值为x，且this probability is parameterized by θ，其输出y为1的概率。
Decision Boundary
此小节主要讲了什么是decision boundary，以及它是怎么产生的，并从直觉上理解这个东西。
从上一小节，我们已经知道sigmoid函数的样子，从图形中可以看到当横轴坐标大于等于0时，其值大于等于0.5，也就是说输出为1的概率大于等于0.5，因此我们就可以分类为1；同样道理，当其横坐标小于0时，我们就可以分类为0。而上一节我们知道这个横坐标实际是我们的h(x)函数的输出。所以可以得出如下结论：
当如下公式成立时，就认为概率>=0.5，也就归类为1：
当如下公式成立时，就认为概率<0.5，也就归类为0：
接着，Andrew举了一个例子，来让我们理解什么是decision boundary。
这里实际假设我们已经训练好了这个模型，其theta值为[-3; 1; 1]的vector，这是我们要根据上边的公式就会得出如下结论：
当 -3+x1+x2 >= 0 ，我们就会认为y=1；
同样当-3 +x1 + x2 < 0时， 我们就会认为y=0.
这里根据 x1 + x2 = 3来画一条线，这条线其实就是所谓的decision boundary，如上图所示，在线上的我们就认为是1，此直线以下的就认为是0。直观上也可以非常好的理解。
当然，在实际工程应用时，可能不会如此简单，边界可能不会如此规则的通过一条直线来划分。它也有可能如下图所示非直线边界：
正如我们之前的课程讲到的，可以使用特征的不同choice，比如可以使用高阶多项式的方式(higher order polynomial regression)。这里实际就是使用了二次多项式函数，theta取值为[-1; 0; 0; 1; 1]时，我们可以得出其边界方程，实际如上图所示的圆圈。
更进一步的，可能是不规则的图形，如下图所示：
总之，从这些例子可以看出，只要我们找到了θ，并且选择对应的feature和feature choice，我们就可以画出一个边界来区分0， 1值，从而实现了分类。所以关键点就在于找到这个θ和feature choice，得出这个边界公式，也就是我们通常所说的算法。
Cost Function
此小节主要讲了针对logistic regression模型，我们应该使用什么样的cost function。
首先，Andrew讲了如果要使用原先线性回归模型的cost function，就会导致该cost function为非凸函数(non-convex)，这样我们找到的就是局部最优值，而非全局最优值，如下图左边的图所示，而我们的目标是找到一个凸函数作为cost function，如下图右边的图所示：
所以，针对logistic regression模型，我们采用如下cost function：
当y=1时，其cost function的函数图如下：
当y=1时，实际就是说我们的样本的输出值y均为1的时候，我们通过这个cost function来训练我们的模型，这时候，如果我们的cost function趋近于0，那么相应的模型输出值趋近于1，也就越接近我们的实际情况，相反，h(x)输出如果趋近于0，那么cost function就会趋于无穷大，也就惩罚了该算法。
当y=0时，其函数图如下：
同样，当h(x)输出越接近1，其cost function就越趋近于无穷大，这就会惩罚该算法。
Simplified Cost Function and Gradient Decent
本小节主要讲述了简化后的cost function，以及如何针对这个cost function做梯度下降。
cost function
在上一小节，我们已经知道Cost function分为两种情况，一种是y=1，一种是y=0。但也正因为只有两种情况，所以我们可以通过一个数学小技巧来将两个公式合并成一个公式，如下：
课上Andrew已经详细讲解了验证y等于0和1的过程，不再详述。
接下来我们将Cost function代入J(θ), 再看下最终的J(θ)的样子,如下所示：
我们还可以将这个公式vectorized：
首先，对于线性回归的hypothesis，我们针对每个样本的variables可以通过如下公式计算其输出值h，其中x(i)为单个样本的向量：
由此，我们可以得出整体输出的向量h，其公式如下：
注意，这里的X是大写，表示所有样本的矩阵，大家可以推导下。
之后，由于我们需要sigmoid该函数，从而形成新的假设，如下：
h=g(Xθ)
最终J(θ) vectorized之后如下图：
Gradient Decent
我们最终的目的依然是寻找J(θ)的最小值，同样的，我们仍然可以用梯度下降的方法来寻找这个最小值。前面，我们已经证明过了通过使用这个cost function我们可以得到凸函数，所以是可以找到全局最小值的。
函数的梯度下降过程其实是类似的，都是通过迭代的方式不断计算新的θ值，以使得J(θ)不断减小。在此过程中，同样需要通过求J(θ)的导数，原理跟线性回归类似。求导之后，最终迭代过程如下图所示：
可以看出，这个梯度下降的过程和线性回归模型非常类似，但是这里的hθ(x)是sigmoid function，而不是原先的θ'X。
另外，该梯度下降公式也可以vectorized化，从而不需要每次都需要一个加总的循环去计算，如下：
需要注意的是当我们在后续使用fminunc时，gradient只需要计算𝜕/𝜕θ*J(θ), 这个求导展开后是如下公式：
即没有learning rate，但是需要除以m
最后，Feature Scaling同样适用于logistic regression模型。
Advanced Optimization
此小节主要讲了一些除梯度下降以外的高级优化方法，而这些优化的算法都已经在函数库中实现，我们只需要知道如何调用即可。
优化的目标
首先要明确我们的优化目标是选择J(θ)的最小值。
先来看下原先梯度下降的过程:
其中，而如果我们有了J(θ)和J(θ)的导数，我们可以利用如下方法来快速找到最优值。
- conjugate gradient
- BFGS
-
L-BFGS
Octave以及其它一些语言的库中一般都有提供这些高级算法的实现，所以一般的我们只需要直接调用。例子如下：
fminunc
总体来说，就是需要我们自己写一个cost function，并返回J(θ)值即jVal，以及gradient vector。然后通过调用fminunc函数我们就可以自己选取这些高级的算法并自动计算出收敛后的θ值，以及J(θ)值，和是否收敛的标志位，如下图所示：
octave execute fminunc
注意optimset是用于设置函数的参数，这里使用参数'GradObj' 为 ‘On'表明我们的cost function会提供decent object， MaxIter 为100表明我们最多只迭代100次。
传递函数的时候通过@funcname来传递。
需要注意的是initialTheta的维数必须>=2
Multiclass Classification
此小节主要讲述了什么是multiclass classification，并且着重讲了通过one-vs-all方法来获取不同类别的概率的方法。实际上就是给定Feature x，计算其为某个特定分类i的概率，即P(y =i | x; θ)
当有多个分类时，我们会计算所有分类的概率，然后选取最大值，即可能性最大的分类作为输出。
Solving the problem of Overfitting
The Problem of Overfitting
此小节主要讲了过拟合问题(Overfitting)
首先Andrew讲了在机器学习训练过程中存在的三种情况：
underfitting(high bias)， just right， overfitting(high variance)
过拟合overfitting实际就是过于精确地去匹配了样本，导致无法更一般化地去预测。
解决过拟合主要有两种方式：
- 减少Feature的数量：同样有两种方式一种是手工选取features；另外是通过算法自动选取
-
Regularization正则化，等待后续课程再看。
address overfitting.png
Cost Function
此小节主要讲了如何去regularization，为什么这样是有效果的。
直觉上理解下，线性回归模型中，当feature很多，甚至还有很多高阶多项式的时候，就可能产生过拟合现象，而要减少这些features的影响就要尽量减少它们的权重，即让θ变小，可以设想极端情况下，某些θ减小到0，这时就可能退化成二次线性方程，曲线也就更加平滑。所以，此时就避免了过拟合现象。而为了让θ变小，我们可以在cost function中使用正则化技巧，课堂老师举了个例子，让J(θ)加一个1000*θ，这样cost function为了最小，那么对应的θ也就会变得很小。如下图所示：
通常情况下，我们不知道应该选取哪个θ来加到J(θ)当中，因此我们会为所有的θ值统一乘一个数，再加到J(θ)当中，也就得到了如下公式：
其中λ(lambda)叫做regularization parameter，显然，这个λ越大，那么梯度下降后，θ值就会越小，相对应的项和feature影响的权重也就越小，但是要避免走向另外一个极端，即如果λ非常大，想象一下那些多项式几乎都为0，那么就成了underfitting了。
这里有一个问题就是λ如何选择呢？
Regularized Linear Regression
此小节主要讲了如何针对LR进行正则化。
Gradient Decent Regularization
首先，看下梯度下降正则化之后是什么样：
需要注意的是：
- θ0是不需要正则化的，所以单独拿了出来
- 1- 𝑎λ/m是必须要>0, 因为θ如果<=0就不对了。通常 𝑎λ/m是一个接近于1的数，比如0.99
-
如果使用微积分的话，我们可以证明最终求导后的公式如下：
gradient decent with regularization
变换一下，如下：
gradient decent with regularization
Normal Equation with Regularization
作为对比，首先看下之前我们的Normal Equation公式
通过正则化后的J(θ)重新求导并set为0，就会得到如下公式：
- L是一个接近于单元矩阵的n+1维的方阵，只是最左上角设为0
- 针对没有正则化的normal equation，我们之前讲过有些矩阵是没有逆矩阵的，因此如果使用inv函数求逆矩阵的时候可能就行不通，但是通过正则化之后，可以证明其肯定会有逆矩阵，因此对于无法求解逆矩阵的情况，也会通过正则化的方式来解决。
Regularized Logistic Regression
通过正则化，我们同样可以解决Logistic Regression的过拟合问题，如下图所示：
先看下原先的J(θ)公式：
正则化之后如下：
针对这个新的J(θ)， 我们可以通过如下方式进行梯度下降，可以看出跟LR是非常相似的，但是那个h(x)已经不是原先的θ'x， 而是sigmoid化之后的函数。
另外，我们同样可以使用之前课程所说的高级优化方法(通过调用fminunc)，同样我们需要提供一个计算cost function的函数，如下图所示：
-
注意：上边的公式有误，gradient(j)的公式应当如下(是+λ/m*θj)：
regularized gradient 注意在计算jVal的时候需要加正则化的term
计算gradient的时候我们不需要learning rate，只需要计算J(θ)的导数
对于gradient(1)， 我们需要单独计算，不需要正则化
