机器学习笔记--线性回归和逻辑回归

介绍机器学习

定义

机器学习的定义：一个程序被认为能从经验E中学习，解决任务T,达到性能度量值P，当且仅当，有了经验E后，经过P评判，程序在处理T时的性能有所提升。（Tom Mitchell ，卡内基梅隆大学）

分类

监督学习：通过已有的一部分输入数据与输出数据之间的对应关系，生成一个函数，将输入映射到合适的输出，例如回归和分类
非监督学习：直接对输入数据集进行建模，例如聚类
半监督学习：综合利用类标的数据和没有类标的数据，来生成合适的分类函数。

线性回归

代价函数（cost Function)

房价预测问题：
$m$ 代表训练集中实例的数量
$x$ 代表特征/输入变量
$y$ 代表目标变量/输出变量
$\left( x,y \right)$ 代表训练集中的实例
$(x^{(i)}, y^{(i)})$ 代表第$i$ 个观察实例
$h$ 代表学习算法的解决方案或函数也称为假设（hypothesis）

一种可能的表达式：$h_{\theta }\left ( x \right ) = \theta _{0} + \theta _{1}x$
模型所预测的误差值与训练集中实际值之间的差距就是建模误差（modeling error）

我们的目标便是选择出可以使得建模误差的平方和能够最小的模型参数。 即使得代价函数 $J \left( \theta_0, \theta_1 \right) = \frac{1}{2m}\sum\limits_{i=1}^m \left( h_{\theta}(x^{(i)})-y^{(i)} \right)^{2}$最小。

代价函数也称为平方误差函数，或平方误差代价函数。

梯度下降法

梯度下降是一个用来求函数最小值的算法，我们将使用梯度下降算法来求出代价函数$J(\theta_{0}, \theta_{1})$ 的最小值。

梯度下降背后的思想是：开始时我们随机选择一个参数的组合$\left( \theta_{0},\theta_{1},......,\theta_{n} \right)$，计算代价函数，然后我们寻找下一个能让代价函数值下降最多的参数组合。我们持续这么做直到找到一个局部最小值（local minimum），因为我们并没有尝试完所有的参数组合，所以不能确定我们得到的局部最小值是否便是全局最小值（global minimum），选择不同的初始参数组合，可能会找到不同的局部最小值。

批量梯度下降（batch gradient descent）算法的公式为：
repeat until convergence {
$\theta_{j} :=\theta_{j}-\alpha \frac{\partial}{\partial \theta_{j}} J\left(\theta_{0}, \theta_{1}\right)$(for $j=0$ and $j=1$)
}

线性回归算法

对线性回归的算法运用梯度下降法，关键是对代价函数求导，即：

$\frac{\partial }{\partial \theta _{j} }J\left ( \theta _{0}, \theta _{1}\right ) = \frac{\partial }{\partial \theta _{j} }\frac{1}{2m} \sum_{i=1}^{m}(h_{\theta }(x^{(i)})-y^{(i)})^2$

$j=0$ 时：$\frac{\partial}{\partial \theta_{0}} J\left(\theta_{0}, \theta_{1}\right)=\frac{1}{m} \sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right)$

$j=1$ 时：$\frac{\partial}{\partial \theta}_{1} J\left(\theta_{0}, \theta_{1}\right)=\frac{1}{m} \sum_{i=1}^{m}\left(\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right) \cdot x^{(i)}\right)$

则算法改写成：

Repeat {
$\theta_{0} :=\theta_{0}-a \frac{1}{m} \sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right)$
$\theta_{1} :=\theta_{1}-a \frac{1}{m} \sum_{i=1}^{m}\left(\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right) \cdot x^{(i)}\right)$

}

批量梯度下降算法：每一步中都用到了所有的训练样本数据。

多维变量线性回归

多维变量线性回归（Linear Regression with Multiple Variables)
增添更多特征后，我们引入一系列新的注释：
$n$ 代表特征的数量
${x^{\left( i \right)} }$代表第 $i$ 个训练实例，是特征矩阵中的第$i$行，是一个向量（vector）。
比方说，上图的
${x}^{(2)}\text{=}\begin{bmatrix} 1416\\\ 3\\\ 2\\\ 40 \end{bmatrix}$
${x}_{j}^{\left( i \right)}$代表特征矩阵中第 $i$ 行的第 $j$ 个特征，也就是第 $i$ 个训练实例的第 $j$ 个特征。
如上图的$x_{2}^{\left( 2 \right)}=3,x_{3}^{\left( 2 \right)}=2$，
支持多变量的假设 $h$ 表示为：$h_{\theta}\left( x \right)={\theta_{0} }+{\theta_{1} }{x_{1} }+{\theta_{2} }{x_{2} }+...+{\theta_{n} }{x_{n} }$，
这个公式中有$n+1$个参数和$n$个变量，为了使得公式能够简化一些，引入$x_{0}=1$，则公式转化为：$h_{\theta} \left( x \right)={\theta_{0} }{x_{0} }+{\theta_{1} }{x_{1} }+{\theta_{2} }{x_{2} }+...+{\theta_{n} }{x_{n} }$
此时模型中的参数是一个$n+1$维的向量，任何一个训练实例也都是$n+1$维的向量，特征矩阵$X$的维度是 $m*(n+1)$。 因此公式可以简化为：$h_{\theta} \left( x \right)={\theta^{T} }X$，其中上标$T$代表矩阵转置。

多变量梯度下降

与单变量的一样，代价函数是所有建模误差的平方和，即：$J\left( \theta_{0},\theta_{1}...\theta_{n} \right)=\frac{1}{2m}\sum\limits_{i=1}^{m}\left( h_{\theta} \left(x^{\left( i \right)} \right)-y^{\left( i \right)} \right)^{2}$ ，其中：$h_{\theta}\left( x \right)=\theta^{T}X={\theta_{0} }+{\theta_{1} }{x_{1} }+{\theta_{2} }{x_{2} }+...+{\theta_{n} }{x_{n} }$ ，我们的目标和单变量线性回归问题中一样，是要找出使得代价函数最小的一系列参数。

特征缩放

在我们面对多维特征问题的时候，我们要保证这些特征都具有相近的尺度，这将帮助梯度下降算法更快地收敛。
以房价问题为例，假设我们使用两个特征，房屋的尺寸和房间的数量，尺寸的值为 0-2000平方英尺，而房间数量的值则是0-5，以两个参数分别为横纵坐标，绘制代价函数的等高线图能，看出图像会显得很扁，梯度下降算法需要非常多次的迭代才能收敛。解决的方法是尝试将所有特征的尺度都尽量缩放到-1到1之间。
最简单的方法是令：$x_{n}=\frac{x_{n}-\mu_{n} }{s_{n} }$，其中 ${\mu_{n} }$是平均值，${s_{n} }$是标准差。

学习率

梯度下降算法的每次迭代受到学习率的影响，如果学习率$a$过小，则达到收敛所需的迭代次数会非常高；如果学习率$a$过大，每次迭代可能不会减小代价函数，可能会越过局部最小值导致无法收敛。
通常可以考虑尝试些学习率：
$\alpha=0.01,0.03,0.1,0.3,1,3,10$

特征和多项式回归

有时我们需要曲线来适应我们的数据，比如一个二次方模型：$h_{\theta}\left( x \right)={\theta_{0} }+{\theta_{1} }{x_{1} }+{\theta_{2} }{x_{2}^2}$
或者三次方模型： $h_{\theta}\left( x \right)={\theta_{0} }+{\theta_{1} }{x_{1} }+{\theta_{2} }{x_{2}^2}+{\theta_{3} }{x_{3}^3}$ 。采用多项式回归模型，在运行梯度下降算法时，特征缩放很重要。

正规方程

正规方程是通过求解下面的方程来找出使得代价函数最小的参数的：$\frac{\partial}{\partial{\theta_{j} } }J\left( {\theta_{j} } \right)=0$ 。
假设我们的训练集特征矩阵为 $X$（包含了 ${ {x}_{0} }=1$）并且我们的训练集结果为向量 $y$，则利用正规方程解出向量 $\theta ={ {\left( {X^T}X \right)}^{-1} }{X^{T} }y$ 。

上标T代表矩阵转置，上标-1 代表矩阵的逆。设矩阵$A={X^{T} }X$，则：${ {\left( {X^T}X \right)}^{-1} }={A^{-1} }$

对于那些不可逆的矩阵（通常是因为特征之间不独立，如同时包含英尺为单位的尺寸和米为单位的尺寸两个特征，也有可能是特征数量大于训练集的数量），正规方程方法是不能用的。

梯度下降与正规方程的比较：

梯度下降	正规方程
需要选择学习率$\alpha$	不需要
需要多次迭代	一次运算得出
当特征数量$n$大时也能较好适用	需要计算${ {\left( { {X}^{T} }X \right)}^{-1} }$ 如果特征数量n较大则运算代价大，因为矩阵逆的计算时间复杂度为$O\left( { {n}^{3} } \right)$，通常来说当$n$小于10000 时还是可以接受的
适用于各种类型的模型	只适用于线性模型，不适合逻辑回归模型等其他模型

总结一下，只要特征变量的数目并不大，标准方程是一个很好的计算参数$\theta $的替代方法。具体地说，只要特征变量数量小于一万，我通常使用标准方程法，而不使用梯度下降法。

逻辑回归

在分类问题中，要预测的 $y$ 是离散的值，此时采用逻辑回归（Logistic Regression）的学习算法。

以二元分类问题为例，将因变量（dependent variable)可能属于的两个类成为负向类（negative class)和正向类（positive class），则因变量 $y\epsilon 0,1$ 其中 0 表示负向类，1 表示正向类。

逻辑回归算法的实质是：它的输出值永远在 0 和 1 之间，是一种分类算法。

假设函数

假设函数的表示

逻辑回归的假设是：$h_{\theta }=g(\theta ^{T}X)$ 其中: $X$ 代表特征向量；$g$ 代表逻辑函数（logistic function），常用的逻辑函数为 S型函数，公式为 $g(z)=\frac{1}{1+e^{-z} }$。

python 代码实现：

import numpy as np
def sigmod(z):
	return 1 / (1 + np.exp(-z))

$h_\theta \left( x \right)$的作用是，对于给定的输入变量，根据选择的参数计算输出变量=1的可能性（estimated probablity）即$h_\theta \left( x \right)=P\left( y=1|x;\theta \right)$

判定边界

决策边界(decision boundary)

S函数的图像：

在逻辑回归中，我们预测：

当${h_\theta}\left( x \right)>=0.5$时，预测 $y=1$。

当${h_\theta}\left( x \right)<0.5$时，预测 $y=0$ 。

根据上面绘制出的 S 形函数图像，我们知道当

$z=0$ 时 $g(z)=0.5$

$z>0$ 时 $g(z)>0.5$

$z<0$ 时 $g(z)<0.5$

又 $z={\theta^{T} }x$ ，即：
${\theta^{T} }x>=0$ 时，预测 $y=1$
${\theta^{T} }x<0$ 时，预测 $y=0$

代价函数

推导代价函数

线性回归模型，我们定义的代价函数是所有模型误差的平方和。理论上来说，我们也可以对逻辑回归模型沿用这个定义，但是问题在于，当我们将${h_\theta}\left( x \right)=\frac{1}{1+{e^{-\theta^{T}x} } }$带入到这样定义了的代价函数中时，我们得到的代价函数将是一个非凸函数（non-convexfunction）。

这意味着我们的代价函数有许多局部最小值，这将影响梯度下降算法寻找全局最小值。

重新定义逻辑回归的代价函数为：$J\left( \theta \right)=\frac{1}{m}\sum\limits_{i=1}^{m}{ {Cost}\left( {h_\theta}\left( {x}^{\left( i \right)} \right),{y}^{\left( i \right)} \right)}$，其中

$Cost(h_{\theta }(x),y) = \left\{\begin{matrix} -log(h_{\theta }(x)) & if y = 1\\ -log(1 - h_{\theta }(x)) & if y = 0 \end{matrix}\right.$

${h_\theta}\left( x \right)$与 $Cost\left( {h_\theta}\left( x \right),y \right)$之间的关系如下图所示：

这样构建的$Cost\left( {h_\theta}\left( x \right),y \right)$函数的特点是：当实际的 $y=1$ 且${h_\theta}\left( x \right)$也为 1 时误差为 0，当 $y=1$ 但${h_\theta}\left( x \right)$不为1时误差随着${h_\theta}\left( x \right)$变小而变大；当实际的 $y=0$ 且${h_\theta}\left( x \right)$也为 0 时代价为 0，当$y=0$ 但${h_\theta}\left( x \right)$不为 0时误差随着 ${h_\theta}\left( x \right)$的变大而变大。
将构建的 $Cost\left( {h_\theta}\left( x \right),y \right)$简化如下：

$\operatorname{cost}\left(h_{\theta}(x), y\right)=-y \times \log \left(h_{\theta}(x)\right)-(1-y) \times \log \left(1-h_{\theta}(x)\right)$

带入代价函数得到：

$J(\theta)=\frac{1}{m} \sum_{i=1}^{m}\left[-y^{(i)} \log \left(h_{\theta}\left(x^{(i)}\right)\right)-\left(1-y^{(i)}\right) \log \left(1-h_{\theta}\left(x^{(i)}\right)\right)\right]$

即：$J(\theta)=-\frac{1}{m} \sum_{i=1}^{m}\left[y^{(i)} \log \left(h_{\theta}\left(x^{(i)}\right)\right)+\left(1-y^{(i)}\right) \log \left(1-h_{\theta}\left(x^{(i)}\right)\right)\right]$

python代码实现：

import numpy as np
    
def cost(theta, X, y):
  theta = np.matrix(theta)
  X = np.matrix(X)
  y = np.matrix(y)
  first = np.multiply(-y, np.log(sigmoid(X* theta.T)))
  second = np.multiply((1 - y), np.log(1 - sigmoid(X* theta.T)))
  return np.sum(first - second) / (len(X))

可以用梯度下降算法来求得能使代价函数最小的参数了。算法为：

Repeat {
$\theta_j := \theta_j - \alpha \frac{\partial}{\partial\theta_j} J(\theta)$
(simultaneously update all )
}

求导后得到：

Repeat {
$\theta_{j} :=\theta_{j}-\alpha \frac{\partial}{\partial \theta_{j}} J(\theta)$
(simultaneously update all )
}

推导过程：

$J\left( \theta \right)=-\frac{1}{m}\sum\limits_{i=1}^{m}{[{ {y}^{(i)} }\log \left( {h_\theta}\left( { {x}^{(i)} } \right) \right)+\left( 1-{ {y}^{(i)} } \right)\log \left( 1-{h_\theta}\left( { {x}^{(i)} } \right) \right)]}$
考虑：
${h_\theta}\left( { {x}^{(i)} } \right)=\frac{1}{1+{ {e}^{-{\theta^T}{ {x}^{(i)} } } } }$
则：
${ {y}^{(i)} }\log \left( {h_\theta}\left( { {x}^{(i)} } \right) \right)+\left( 1-{ {y}^{(i)} } \right)\log \left( 1-{h_\theta}\left( { {x}^{(i)} } \right) \right)$
$={ {y}^{(i)} }\log \left( \frac{1}{1+{ {e}^{-{\theta^T}{ {x}^{(i)} } } } } \right)+\left( 1-{ {y}^{(i)} } \right)\log \left( 1-\frac{1}{1+{ {e}^{-{\theta^T}{ {x}^{(i)} } } } } \right)$
$=-{ {y}^{(i)} }\log \left( 1+{ {e}^{-{\theta^T}{ {x}^{(i)} } } } \right)-\left( 1-{ {y}^{(i)} } \right)\log \left( 1+{ {e}^{ {\theta^T}{ {x}^{(i)} } } } \right)$

所以：
$\frac{\partial }{\partial {\theta_{j} } }J\left( \theta \right)=\frac{\partial }{\partial {\theta_{j} } }[-\frac{1}{m}\sum\limits_{i=1}^{m}{[-{ {y}^{(i)} }\log \left( 1+{ {e}^{-{\theta^{T} }{ {x}^{(i)} } } } \right)-\left( 1-{ {y}^{(i)} } \right)\log \left( 1+{ {e}^{ {\theta^{T} }{ {x}^{(i)} } } } \right)]}]$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{[-{ {y}^{(i)} }\frac{-x_{j}^{(i)}{ {e}^{-{\theta^{T} }{ {x}^{(i)} } } } }{1+{ {e}^{-{\theta^{T} }{ {x}^{(i)} } } } }-\left( 1-{ {y}^{(i)} } \right)\frac{x_j^{(i)}{ {e}^{ {\theta^T}{ {x}^{(i)} } } } }{1+{ {e}^{ {\theta^T}{ {x}^{(i)} } } } } }]$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{ {y}^{(i)} }\frac{x_j^{(i)} }{1+{ {e}^{ {\theta^T}{ {x}^{(i)} } } } }-\left( 1-{ {y}^{(i)} } \right)\frac{x_j^{(i)}{ {e}^{ {\theta^T}{ {x}^{(i)} } } } }{1+{ {e}^{ {\theta^T}{ {x}^{(i)} } } } }]$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{\frac{ { {y}^{(i)} }x_j^{(i)}-x_j^{(i)}{ {e}^{ {\theta^T}{ {x}^{(i)} } } }+{ {y}^{(i)} }x_j^{(i)}{ {e}^{ {\theta^T}{ {x}^{(i)} } } } }{1+{ {e}^{ {\theta^T}{ {x}^{(i)} } } } } }$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{\frac{ { {y}^{(i)} }\left( 1\text{+}{ {e}^{ {\theta^T}{ {x}^{(i)} } } } \right)-{ {e}^{ {\theta^T}{ {x}^{(i)} } } } }{1+{ {e}^{ {\theta^T}{ {x}^{(i)} } } } }x_j^{(i)} }$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{({ {y}^{(i)} }-\frac{ { {e}^{ {\theta^T}{ {x}^{(i)} } } } }{1+{ {e}^{ {\theta^T}{ {x}^{(i)} } } } })x_j^{(i)} }$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{({ {y}^{(i)} }-\frac{1}{1+{ {e}^{-{\theta^T}{ {x}^{(i)} } } } })x_j^{(i)} }$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{[{ {y}^{(i)} }-{h_\theta}\left( { {x}^{(i)} } \right)]x_j^{(i)} }$
$=\frac{1}{m}\sum\limits_{i=1}^{m}{[{h_\theta}\left( { {x}^{(i)} } \right)-{ {y}^{(i)} }]x_j^{(i)} }$

梯度下降算法以外，还有一些常被用来令代价函数最小的算法，这些算法更加复杂和优越，而且通常不需要人工选择学习率，通常比梯度下降算法要更加快速。这些算法有：共轭梯度（Conjugate Gradient），局部优化法(Broyden fletcher goldfarb shann,BFGS)和有限内存局部优化法(LBFGS) 。

简化的代价函数和梯度下降

由上面的推导可以得到代价函数$Cost\left( {h_\theta}\left( x \right),y \right)=-y\times log\left( {h_\theta}\left( x \right) \right)-(1-y)\times log\left( 1-{h_\theta}\left( x \right) \right)$
即，逻辑回归的代价函数：
$Cost\left( {h_\theta}\left( x \right),y \right)=-y\times log\left( {h_\theta}\left( x \right) \right)-(1-y)\times log\left( 1-{h_\theta}\left( x \right) \right)$
$=-\frac{1}{m}\sum\limits_{i=1}^{m}{[{ {y}^{(i)} }\log \left( {h_\theta}\left( { {x}^{(i)} } \right) \right)+\left( 1-{ {y}^{(i)} } \right)\log \left( 1-{h_\theta}\left( { {x}^{(i)} } \right) \right)]}$
试图找尽量让$J\left( \theta \right)$ 取得最小值的参数$\theta $，即 $\underset{\theta}{\min }J\left( \theta \right)$

最小化代价函数的方法，是使用梯度下降法(gradient descent)。这是我们的代价函数：
$J\left( \theta \right)=-\frac{1}{m}\sum\limits_{i=1}^{m}{[{ {y}^{(i)} }\log \left( {h_\theta}\left( { {x}^{(i)} } \right) \right)+\left( 1-{ {y}^{(i)} } \right)\log \left( 1-{h_\theta}\left( { {x}^{(i)} } \right) \right)]}$

根据梯度下降算法可以得到 $\theta$ 的更新公式：

${\theta_j}:={\theta_j}-\alpha \frac{1}{m}\sum\limits_{i=1}^{m}{({h_\theta}({ {x}^{(i)} })-{ {y}^{(i)} }){x_{j} }^{(i)} }$

若有$n$ 个特征，则需要同步更新所有的 $\theta_{j}, j=0..n$ 。

可以发现，逻辑回归算法和线性回归算法的 $\theta$ 的更新规则是一样的，但是两者的假设函数是不同的。

线性回归的假设函数为 ${h_\theta}\left( x \right)={\theta^T}X={\theta_{0} }{x_{0} }+{\theta_{1} }{x_{1} }+{\theta_{2} }{x_{2} }+...+{\theta_{n} }{x_{n} }$

逻辑回归的假设函数为 ${h_\theta}\left( x \right)=\frac{1}{1+{ {e}^{-{\theta^T}X} } }$

可以向量化的方式来同时更新所有的 $\theta$ 。

若特征范围差距很大的话，采用特征缩放的方式可以提高梯度下降的收敛速度。

高级优化

梯度下降并不是我们可以使用的唯一算法，还有其他一些算法，更高级、更复杂。如果我们能用这些方法来计算代价函数$J\left( \theta \right)$和偏导数项$\frac{\partial }{\partial {\theta_j} }J\left( \theta \right)$两个项的话，那么这些算法就是为我们优化代价函数的不同方法，共轭梯度法 BFGS (变尺度法) 和L-BFGS (限制变尺度法) 就是其中一些更高级的优化算法，它们需要有一种方法来计算 $J\left( \theta \right)$，以及需要一种方法计算导数项，然后使用比梯度下降更复杂的算法来最小化代价函数。

这三种算法有许多优点，其中一个就是不需要手动选择学习率 $\alpha$，所以对于这些算法的一种思路是，给出计算导数项和代价函数的方法，可以认为算法有一个智能的内部循环，称为线性搜索(line search)算法，它可以自动尝试不同的学习速率 $\alpha$，并自动选择一个好的学习速率 $a$，因此它甚至可以为每次迭代选择不同的学习速率，那么就不需要自己选择。这些算法实际上在做更复杂的事情，不仅仅是选择一个好的学习速率，所以它们往往最终比梯度下降收敛得快多了。

多类别分类：一对多

逻辑回归 (logistic regression)可以用来来解决多类别分类问题，“一对多” (one-vs-all) 的分类算法。如何进行一对多的分类工作，有时这个方法也被称为"一对余"方法。

我们先从用三角形代表的类别1开始，实际上我们可以创建一个，新的"伪"训练集，类型2和类型3定为负类，类型1设定为正类，我们创建一个新的训练集，如下图所示的那样，我们要拟合出一个合适的分类器。

将多个类中的一个类标记为正向类（$y=1$），然后将其他所有类都标记为负向类，这个模型记作$h_\theta^{\left( 1 \right)}\left( x \right)$。接着，类似地第我们选择另一个类标记为正向类（$y=2$），再将其它类都标记为负向类，将这个模型记作 $h_\theta^{\left( 2 \right)}\left( x \right)$,依此类推。最后得到一系列的模型简记为： $h_\theta^{\left( i \right)}\left( x \right)=p\left( y=i|x;\theta \right)$其中：$i=\left( 1,2,3....k \right)$

要做预测时，我们将所有的分类机都运行一遍，然后对每一个输入变量，都选择最高可能性的输出变量。训练这个逻辑回归分类器：$h_\theta^{\left( i \right)}\left( x \right)$， 其中 $i$ 对应每一个可能的 $y=i$，在三个分类器里面输入 $x$，选择一个让 $h_\theta^{\left( i \right)}\left( x \right)$ 最大的$ i$，即$\max {i} h{\theta}^{(i)}(x)$。

正则化（Regualrization）

过拟合问题

问题提出

在实际使用线性回归和逻辑回归应用到特定的问题中会出现过拟合（over-fitting）。下面以回归问题作为例子：

第一个模型是线性模型，欠拟合，不能很好的适应训练集；第三个模型是四次方的模型，过于强调拟合原始数据而忽略了预测新数据的功能；中间的模型最合适。

如何解决过拟合的问题？

• 丢弃一些不能帮助我们正确预测的特征，可以手工选择，可以使用模型选择算法（PCA）

• 正则化，保留所有的特征，但是减少参数的大小

代价函数

上面的回归问题中的假设为${h_\theta}\left( x \right)={\theta_{0} }+{\theta_{1} }{x_{1} }+{\theta_{2} }{x_{2}^2}+{\theta_{3} }{x_{3}^3}+{\theta_{4} }{x_{4}^4}$，可以看出正是高次项导致了过拟合的产生，如果高次项的参数 $\theta$ 接近0，则可以很好的拟合。

正则化的基本方法是在一定程度上减少参数 $\theta$ 的值。要减少 ${\theta_{3} }$ 和 ${\theta_{4} }$ 的大小，需要修改代价函数，在其中${\theta_{3} }$和${\theta_{4} }$ 设置一点惩罚。在最小化代价时也需要将这个惩罚纳入考虑中，最终导致选择较小一些的${\theta_{3} }$和${\theta_{4} }$。修改后的代价函数如下：$\underset{\theta }{\mathop{\min } }\,\frac{1}{2m}[\sum\limits_{i=1}^{m}{ { {\left( { {h}_{\theta } }\left( { {x}^{(i)} } \right)-{ {y}^{(i)} } \right)}^{2} }+1000\theta _{3}^{2}+10000\theta _{4}^{2}]}$。

带有正则化的代价函数为：$J(\theta)=\frac{1}{2 m}\left[\sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right)^{2}+\lambda \sum_{j=1}^{n} \theta_{j}^{2}\right]$，其中$\lambda $又称为正则化参数（**Regularization Parameter**）。 注：根据惯例，我们不对${\theta_{0}}$进行惩罚。

经过正则化后的对比：

令 $\lambda$ 的值很大的话，为了使Cost Function 尽可能的小，所有的 $\theta $ 的值（不包括${\theta_{0} }$）都会在一定程度上减小。若$\lambda$ 的值太大了，那么$\theta $（不包括${\theta_{0} }$）都会趋近于0，模型变成 ${h_\theta}\left( x \right)={\theta_{0} }$。对于正则化，我们要取一个合理的 $\lambda$ 的值，这样才能更好的应用正则化。

正则化线性回归

对于线性回归问题的求解，有两种学习算法：基于梯度下降，基于正归方程。

正则化线性回归的代价函数为：$J\left( \theta \right)=\frac{1}{2m}\sum\limits_{i=1}^{m}{[({ {({h_\theta}({ {x}^{(i)} })-{ {y}^{(i)} })}^{2} }+\lambda \sum\limits_{j=1}^{n}{\theta _{j}^{2} })]}$。

因未对 $\theta_{0}$ 进行正则化，所以梯度下降法分两种情况：

$Repeat$ $until$ $convergence${

${\theta_0}:={\theta_0}-a\frac{1}{m}\sum\limits_{i=1}^{m}{(({h_\theta}({ {x}^{(i)} })-{ {y}^{(i)} })x_{0}^{(i)} })$

${\theta_j}:={\theta_j}-a[\frac{1}{m}\sum\limits_{i=1}^{m}{(({h_\theta}({ {x}^{(i)} })-{ {y}^{(i)} })x_{j}^{\left( i \right)} }+\frac{\lambda }{m}{\theta_j}]$ $for$ $j=1,2,...n$

}

上面算法中$ j=1,2,…,n$ 时的更新式子进行调整可得：

${\theta_j}:={\theta_j}(1-a\frac{\lambda }{m})-a\frac{1}{m}\sum\limits_{i=1}^{m}{({h_\theta}({ {x}^{(i)} })-{ {y}^{(i)} })x_{j}^{\left( i \right)} }$

同样，可以利用正规方程求解正则化线性回归，

$\theta =\left ( X^{T}X + \lambda \begin{bmatrix} 0 & & & & \\ &1 & & & \\ & & 1 & & \\ & & &\ddots & \\ & & & 1& \end{bmatrix} \right )^{^{-1} }X^{T}y$

公式中矩阵的维度为$(n+1) * (n+1)$。

正则化逻辑回归

对于逻辑回归问题，有两种优化算法：一种使用梯度下降法来优化代价函数$J\left( \theta \right)$，另一种使用更高级的优化算法，需要自己设计代价函数$J\left( \theta \right)$。

增加了正则化的代价函数为：

$J\left( \theta \right)=\frac{1}{m}\sum\limits_{i=1}^{m}{[-{ {y}^{(i)} }\log \left( {h_\theta}\left( { {x}^{(i)} } \right) \right)-\left( 1-{ {y}^{(i)} } \right)\log \left( 1-{h_\theta}\left( { {x}^{(i)} } \right) \right)]}+\frac{\lambda }{2m}\sum\limits_{j=1}^{n}{\theta _{j}^{2} }$

Python代码：

import numpy as np

def costReg(theta, X, y, learningRate):
    theta = np.matrix(theta)
    X = np.matrix(X)
    y = np.matrix(y)
    first = np.multiply(-y, np.log(sigmoid(X*theta.T)))
    second = np.multiply((1 - y), np.log(1 - sigmoid(X*theta.T)))
    reg = (learningRate / (2 * len(X))* np.sum(np.power(theta[:,1:theta.shape[1]],2))
    return np.sum(first - second) / (len(X)) + reg

最小化该代价函数，通过求导得到梯度下降算法：

$Repeat$ $until$ $convergence${

${\theta_0}:={\theta_0}-a\frac{1}{m}\sum\limits_{i=1}^{m}{(({h_\theta}({ {x}^{(i)} })-{ {y}^{(i)} })x_{0}^{(i)} })$
${\theta_j}:={\theta_j}-a[\frac{1}{m}\sum\limits_{i=1}^{m}{({h_\theta}({ {x}^{(i)} })-{ {y}^{(i)} })x_{j}^{\left( i \right)} }+\frac{\lambda }{m}{\theta_j}]$ $for$ $j=1,2,...n$

}

线性回归的作业用 python 实现，见Github中代码：ex1