逻辑回归算法
引入
假设我们要解决一个分类问题，其中标签\(y\)取值为0或1.
如果我们用线性回归算法，那么函数\(h_\theta(x)\)的输出值可能远大于1，或远小于0. 因此，这里介绍一种新的算法：逻辑回归算法，它的性质是：它的输出值永远在0到1之间。注意，该算法虽然名字中包含“回归”两字，但是实际是一种分类算法。
模型表示
逻辑回归模型的假设函数是：
\[h_\theta(x) = g(\theta^TX)\]
其中\(g\)为逻辑函数/对数几率函数(logistic function)，是一种常用的S形函数(Sigmoid function)：
\[g(z) = \frac{1}{1+e^{-z}}\]
对模型的理解
在逻辑回归模型中，\(h_\theta(x)\)表示对于输入\(x\)，其输出值为1的概率，即
\[h_\theta(x) = P(y=1|x;\theta)\]
决策边界
在逻辑回归中，我们进行如下预测： - 当\(h_\theta(x)\geq0.5\)时，预测\(y=1\) - 当\(h_\theta(x)<0.5\)时，预测\(y=0\)
再利用S形函数的性质，我们可以进一步得出： - 当\(\theta^TX\geq0\)时，预测\(y=1\) - 当\(\theta^TX<0\)时，预测\(y=0\)
举个栗子，假设我们有一个模型：\(h_\theta(x) = g(\theta_0 + \theta_1x_1 + \theta_2x_2)\)，其中三个参数分别为-3，1，1.则对于满足\(-3+x_1+x_2\geq0\)的样本，我们预测\(y=1\)（图中为红叉），反之预测\(y=0\)（图中为蓝圈）.
于是我们可以绘制一条直线\(x_1+x_2=3\)，将样本按结果划分为两部分，这条直线就是模型的决策边界。
需要注意的是，决策边界是假设函数、参数向量\(\theta\)的属性，与数据集无关。
当然，决策边界并不一定是直线，也可能是曲线、甚至是个圆。比如说，当数据集呈现出如下的情况的时候：
此时我们会拟合出非线性的\(h_\theta(x)\)，也就会求出非线性的决策边界。
代价函数
在线性回归模型中，我们的代价函数是所有数据误差的平方和，也就是：
\[J(\theta) = \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})^2\]
但如果我们在逻辑回归中也用同样的代价函数时，它将会是一个非凸函数(non-convex function)：
这会导致我们的代价函数会有多个局部最小值，梯度下降法也就无法找到全局最小值。
注意，对于函数的凹凸性，国内外的定义不同，我们考虑Wiki上的定义，它和这里的定义以及西瓜书上的定义（P54注释）相同。即：
\(f\) is called convex if:
\(\forall x_1,x_2 \in X,\forall t \in [0,1]: f(tx_1+(1-t)x_2) \le tf(x_1)+(1-t)f(x_2)\)
\(f\) is called strictly convex if:
\(\forall x_1 \ne x_2 \in X,\forall t \in (0,1): f(tx_1+(1-t)x_2) < tf(x_1)+(1-t)f(x_2)\)
A function \(f\) is said to be (strictly) concave(凸) if \(-f\) is (strictly) convex.
于是，我们把线性函数的代价函数中\(\frac{1}{2m}\)的\(\frac12\)放到后面的每一项中，并把\(\sum\)的第\(i\)项记为\(Cost(h_\theta(x^{(i)}), y^{(i)})\)。我们把改写后的代价函数 \[ J(\theta) = \frac1mCost(h_\theta(x^{(i)}), y^{(i)}) \] 作为逻辑回归的代价函数，其中 \[ Cost(h_\theta(x), y)= \begin{cases} -log(h_\theta(x)) & ,\text{if $y = 1$} \\ -log(1-h_\theta(x)) & ,\text{if $y = 0$} \end{cases} \] 代入后，代价函数可以写成 \[ J(\theta) = -\frac1m[\sum_{i=1}^m(y^{(i)}logh_\theta(x^{(i)}) + (1-y^{(i)})log(1-h_\theta(x^{(i)})))] \] 该式子来自于统计学中的极大似然法，且是一个凸函数，所以能够作为逻辑回归的代价函数。
梯度下降
逻辑回归中的梯度下降和线性回归中完全相同： \[ \begin{align} \theta_j & := \theta_j - \alpha\frac{\partial}{\partial\theta_j}J(\theta) \\ & :=\theta_j - \alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \end{align} \] 所以在两种不同的回归中，它们的区别在于对\(\theta_i(x)\)定义的不同。而在线性回归中的梯度下降以及特征缩放，在逻辑回归中同样适用。
更优的算法
在参数拟合时，我们的最终目标就是最小化代价函数，并确定那时的参数\(\theta\)。更具体地说，我们需要对于某个指定的\(\theta\)，求出对应\(J(\theta)\)和\(\frac{\partial}{\partial\theta_j}J(\theta)\)，再求出下一个\(\theta\)。
在这个过程中，梯度下降法还需要我们手动确定学习速率\(\alpha\)，且通常效率很低。而其实还有一些其他的算法（如共轭梯度法、BFGS(变尺度法)、L-BFGS(限制变尺度法)），它们更高级、更复杂，却有以下优点：
- 不需要手动选择学习速率\(\alpha\)。
- 通常有更高的效率。
因此在遇到大型的机器学习问题时，我们常常通过调用库来使用这些更高级的算法，而不是梯度下降法。
多类别分类：one-vs-all算法
在分类问题中，常常不仅有两种分类，那么对于多类别分类，应该如何找出一个学习算法来进行分类呢？
假设有这样一个数据集
其中有三种不同的类别，我们要做的是把这个三元分类问题拆分成三个不同的二元分类问题：是绿三角和不是绿三角、是红叉和不是红叉、是蓝方块和不是蓝方块。
求解这三个子问题后，我们拟合出了三个不同的分类器\(h_\theta^{(i)}(x)= P(y=i|x;\theta)\)，分别用来预测\(y\)属于第\(i\)种类型的概率。综合起来看，对于给定输入\(x\)，它的所属分类应该是使得\(h_\theta^{(i)}(x)\)最大的那个\(i\)值，即\(\max_ih_\theta^{(i)}(x)\)。
正则化
过拟合(overfitting)与欠拟合(underfitting)
对于同样的一组数据集，我们可能学习出不同的模型。其中有的模型学的“太简单”，不能很好的拟合数据集，通常也不会有很好的预测效果；而另外一些模型又可能学的“太好”，把训练数据的一些特点（而不是模型中应该学到的规律）也学了，这样也不能够很好地进行预测。
学的“太简单”的现象就称为欠拟合(underfitting)，与之伴随的通常是较高的偏差；而学的“太好”的现象则称为过拟合(overfitting)，通常伴随着较大的方差，有较差的泛化能力。这两者是两个极端，都不是好的模型，我们希望得到适中的模型。
减少过拟合
当我们的模型有较多的特征，而只有较少的训练数据的时候，过拟合的问题就会发生。要减少过拟合的问题，我们有以下解决方法：
- 减少特征（手动选择或使用算法），这种方式会删除那些其实对预测有一些影响的特征。
- 正则化，这种方式会把各个特征对预测的影响都考虑进来。
正则化与代价函数
在正则化中，我们不减少特征数量，而是以减小参数\(\theta_i\)的值的方法来减小对应特征\(x_i\)对模型的影响。
比如我们的模型假设是 \[ h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_3+\theta_4x_4 \] 而我们的优化目标是最小化代价函数，以线性回归模型为例，该目标可以写为： \[ \min_\theta\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})^2 \] 我们想要减小特征\(x_3\)和\(x_4\)的影响，要做的就是给\(\theta_3\)和\(\theta_4\)设置一点惩罚，使它们接近于0，也就能使\(x_3\)和\(x_4\)对预测的影响变小很多。比如，我们可以把优化目标改为： \[ \min_\theta\frac{1}{2m}[\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})^2 + 1000\theta_3^2 + 10000\theta_4^2] \] 如果我们不知道应该惩罚哪些特征，就对所有的特征都进行惩罚（按照惯例，不对\(\theta_0\)进行惩罚）。这样，我们能把新的代价函数概括为： \[ J(\theta)=\frac{1}{2m}[\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})^2 + \lambda\sum_{j=1}^n\theta_j^2] \] 其中\(\lambda\)称为正则化参数，它的大小代表了正则化的程度，控制了在两个不同目标之间的tradeoff。第一个目标（由第一个求和式控制）希望我们的模型假设能够更好学习、适应训练集；而第二个目标（第二个求和式）希望保持参数值较小，减少各参数对预测结果的影响，也就是希望不要学的“太好”。
为了更好的理解，这里考虑两种极端情况。如果\(\lambda\)为0，则相当于没有进行正则化，只考虑了第一个目标，会导致overfitting；而如果\(\lambda\)非常大，则会导致所有参数（除\(\theta_0\)）都趋近于0，导致最后的模型假设变成\(h_\theta(x)=\theta_0\)，这就相当于几乎没有学习，导致了underfitting。
正则化的线性回归
在原来的线性回归中，梯度下降法的更新规则为： \[ \theta_j := \theta_j - \alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \] 在正则化后，我们对\(j=1,2,\cdots,n\)的更新规则进行修改，得出新的更新规则为： \[ \theta_j = \begin{cases} \theta_j - \alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} & \text{if $ j = 0$} \\ \theta_j(1-\alpha\frac\lambda m) - \alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} & \text{others} \end{cases} \] 其中\(1-\alpha\frac\lambda m\)常常是一个微微小于1的数，因此在每次更新中会把\(\theta_j\)逐渐压缩。
同样，正规方程也能用于求解正则化线性回归模型。原来的方程为： \[ \theta = (X^TX)^{-1}X^Ty \] 对于正则化的线性回归模型，新的方程修改为： \[ \theta = (X^TX + \lambda \begin{bmatrix} 0 \\ & 1 \\ && 1 \\ &&& \ddots \\ &&&& 1 \end{bmatrix} )^{-1}X^Ty \] 还记得在前面所学的正规方程中提到，可能会出现矩阵不可逆的问题。即当有冗余特征或训练数据少于特征数时，\(X^TX\)将是奇异的、不可逆的。而正则化同样为我们解决了这个问题。在上述式子中，只要有\(\lambda>0\)，就能确保括号内的项是可逆的。
正则化的逻辑回归
在逻辑回归中，正则化的操作会把代价函数改为 \[ J(\theta) = -\frac1m[\sum_{i=1}^m(y^{(i)}logh_\theta(x^{(i)}) + (1-y^{(i)})log(1-h_\theta(x^{(i)})))] + \frac{\lambda}{2m}\sum_{j=1}^m\theta_j^2 \] 代价函数的改变会导致各种学习时会用到的算法的对应变化。比如说，在不考虑正则化时，梯度下降法在逻辑回归中也适用，且两种回归中的更新规则也相同。那么同样，在正则化后，线性回归中的梯度下降法更新规则仍然可以用于逻辑回归中： \[ \theta_j = \begin{cases} \theta_j - \alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} & \text{if $ j = 0$} \\ \theta_j(1-\alpha\frac\lambda m) - \alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} & \text{others} \end{cases} \]
同样，由于代价函数的改变，导致在使用逻辑回归中的高级算法中，代码也需要进行一些修改，但这里就不做详细阐述。