在监督学习中有一个有标签的训练集，目标是找到能够区分正样本和负样本的决策边界，通过一系列输入数据的特征和输入数据的标签，拟合一个假设函数。

2.1.1 线性回归算法

2.1.1.1 单变量线性回归

Linear regression with one variable，以房价模型为例：

单变量线性回归模型假设：$h_θ (x)=θ_0+θ_1 x$

$M$为训练集中实例的数量；$x$为特征/输入变量；$y$为目标变量/输出变量；$(x,y)$代表训练集中的某个实例；$((x^{(i)} ,y^{(i)})$为训练集中的第$i$个实例；$h$表示假设函数；$θ_0, θ_1 $为模型参数.

平方误差代价函数：

$J(θ_0,θ_1)=1/2m ∑_{i=1}^m(h_θ (x^{(i)})-y^{(i)})^2$

建模误差：模型所预测的值与训练集中实际值之间的差距。
实现建模目标：寻找可以使得建模误差的平方和能够最小的模型参数$θ0, θ_1$，获取平方误差代价函数的值最小$minimize{θ0,θ_1} J(θ_0,θ_1 )$，实现训练集与最优的直线相拟合，使训练集实例$(x,y)$的预测值$hθ (x)$接近实际值$y$.

梯度下降算法：

作用：用来计算函数最小值的一种算法。
基本思想：以求代价函数$minimize_{θ_0,θ_1} J(θ_0,θ_1 )$为例。首先随机选择一个参数的组合$θ_0, θ_1$，可以是一个全零的向量，计算代价函数的值；然后寻找下一组能让代价函数值下降的参数组合；如此往复，直到找到一个局部最小值。由于并没有尝试完所有的参数组合，所以不能确定得到的局部最小值是否是全局最小值，选择不同的初始参数组合，可能会找到不同的局部最小值。
梯度的几何意义：梯度是函数变化增加最快的地方，或者说沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向，梯度减少最快，更容易找到函数的最小值。
计算公式：
$repeat\ until\ convergence\ for(j=0 and j=1) :\{$ ${θ_j≔θ_j-α \frac {∂}{∂θ_j} J(θ_0,θ_1 ) }$ $\}$ 
α 是学习率，它决定了沿着能让代价函数下降程度最大的方向向下迈出的步子有多大。若α 太小一点点地挪动，去努力接近最低点，这样就需要很多步才能到达局部最低点；若α 太大，那么梯度下降法可能会越过最低点，可能造成无法收敛，甚至是发散。

运用梯度下降法解决单变量线性回归问题：
关键在于求出代价函数的偏导数

$h_θ (x)=θ_0+θ_1 x$ $J(θ_0,θ_1)=\frac {1}{2m} ∑_{i=1}^m(h_θ (x^{(i)})-y^{(i)})^2$

$repeat\ until\ convergence\ for(j=0 and j=1) :\{$

${θ_j≔θ_j-α \frac {∂}{∂θ_j} J(θ_0,θ_1 ) }$

$\}$

$\frac {∂}{∂θ_j} J(θ_0,θ_1)=\frac {∂}{∂θ_j} \frac {1}{2m} ∑_{i=1}^m(h_θ (x^{(i)})-y^{(i)})^2$

$repeat\ until\ convergence\ and\ update θ_0, θ_1\ simultaneously :\{$

$θ_0:=θ_0- \frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)})$ $θ_1:=θ_1- \frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x^{(i)}$

$\}$

单变量线性回归算法另类数学理解：$h_θ (x)=θ_0+θ_1 x$

$Slope:θ_1=(\overline{X} \overline{Y} -\overline{XY})/(\overline{X}^2 -\overline{X^2})$ $Interception:θ_0=\overline Y - θ_1 \overline{X}̅$ $Squrared error:SE=(Y-h_θ (X))^2$

2.1.1.2 多变量线性回归

Linear Regression with Multiple Variables，房价模型：

多维特征模型假设：$h_θ (x)=θ_0 x_0+θ_1 x_1+θ_2 x_2+⋯+θ_n x_n$

$(x1,x_2,…,x_n)$ 为模型特征；$n$ 代表特征的数量；$x^{(i)}$ 代表第 $i$ 个训练实例（一个向量）；$x_j^{(i)}$代第$i$个训练实例的第 $j$个特征；引入$x_0=1$。多维特征模型向量表示：$hθ (x)=θ^T X$

$X= \left[ \begin{matrix} 1 \\ x_1 \\ x_2 \\ ... \\ x_n \end{matrix} \right] θ = \left[ \begin{matrix} θ_0 \\ θ_1 \\ θ_2 \\ ... \\ θ_n \end{matrix} \right] h_θ (x)=θ^T X$

多变量梯度下降算法：

$Hypothesis: h_θ (x)=θ_0 x_0+θ_1 x_1+θ_2 x_2+⋯+θ_n x_n$ $Parameters: θ_0,θ_1,…,θ_n$ $Cost Function: J(θ_0,θ_1,…,θ_n )= \frac {1}{2m} ∑_{i=1}^m(h_θ (x^{(i)})-y^{(i)})^2$

$repeat\ until\ convergence\ update\ θ_0, θ_1,…,θ_n\ simultaneously :\{$
${θ_j≔θ_j-α \frac {∂}{∂θ_j} J(θ_0,θ_1,…,θ_n)
}$
$\}$
当代表特征的数量$n>1$时，梯度下降算法变为：首先随机选择一系列的参数值，计算所有的预测结果后，再给所有的参数一个新的值，如此循环直到收敛。
$repeat\ until\ convergence\ and\ update\ θ_0, θ_1,…,θ_n\ simultaneously:\{ $

$θ_0≔θ_0-\frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_0^{(i)}$ $θ_1≔θ_1-\frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_1^{(i)}$ $...$ $θ_n≔θ_n-\frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_n^{(i)}$

$\}$

提升多维特征梯度下降算法收敛速度：特征缩放

现象：假设使用两个特征，房屋的尺寸和房间的数量，尺寸的值为0-2000 平方英尺，而房间数量的值则是0-5，以两个参数分别为横纵坐标，绘制代价函数的等高线图能，看出图像会显得很扁，梯度下降算法需要非常多次的迭代才能收敛。
解决方法：保证这些特征都具有相近的尺度，尝试将所有特征的尺度都尽量缩放到-1到1 之间。
表达式：$x_n= \frac {x_n-μ_n}{s_n}$ 其中$μ_n$是平均值，$s_n$是标准差。

多维特征梯度下降算法学习率：

若学习率α 过小，则达到收敛所需的迭代次数会非常高；如果学习率α 过大，每次迭代可能不会减小代价函数，可能会越过局部最小值导致无法收敛。
通常可以考虑尝试的学习率：α=0.001， 0.003，0.01，0.03，0.1，0.3，1，3，10

高次多项式回归：

线性回归并不适用于所有数据，比如一个三次方模型： $h_θ (x)=θ_0+θ_1 x_1+θ_2 x_2^2+θ_3 x_3^3$
多项式回归处理方法：通常需要先观察数据然后再决定准备尝试怎样的模型
- 直接用曲线来拟合数据集，非线性回归算法（支持向量机）
- 将模型转化为线性回归模型：$x_2 = x_2^2;x_3 = x_3^3$
若采用多项式回归模型，在运行梯度下降算法前，特征缩放非常有必要。

最小二乘法（正规方程算法）：解决某些线性回归问题

基本思想：求代价函数的极值为零时的参数，即:$\frac {∂}{∂θ_j} J(θ_j )=0$
假设训练集特征矩阵为 X（包含了x_0=1）并且训练集的结果为向量 Y，利用正规方程解出向量：$θ={(X^T X)}^{-1} X^T Y$
适用范围：
- 对于不可逆的矩阵，正规方程方法是不能用的（通常是因为特征之间不独立，如同时包含英尺为单位的尺寸和米为单位的尺寸两个特征，也有可能是特征数量大于训练集的数量）。
- 如果特征数量 n 较大则运算代价大，因为矩阵逆的计算时间复杂度为 O(n3)，通常来说当 n 小于 10000 时还是可以接受的

2.1.2 逻辑回归算法

Logistic regression是用来解决分类问题，如邮件是垃圾邮件还是正常邮件、肿瘤是是良性的还是恶性的、线上交易是欺诈的还是正常的等等。

逻辑回归模型假设：

二元分类：输出变量$y∈\{0,1\}$，其中0 表示负向类，1 表示正向类。处理二元分类问题的算法的输出值永远在0 到1 之间，代表y为正向类的概率。 $\begin{cases} Classification: y=0\ or\ 1 \\ Logistic regression: 0≤h _θ (x)≤1 \end{cases}$
S型函数： $g(z)=\frac {1}{1+e^{-z}}$函数输出值永远在0 到1 之间。输入值从负无穷到正无穷，映射到0和1之间，将这样的输出值表达为“可能性”。
逻辑回归模型假设：
- 含义：对于给定的输入变量X，根据选择的参数θ计算输出变量等于1 的可能性。若对于给定的x，计算出$h_θ (x)=0.7$，则表示y有 70%的几率为正向类，有30%的几率为负向类$P(y=0 |x;θ)=1-P(y=1 |x;θ)$
- 判定边界：根据不同的数据呈现，可得到不同的决策边界：线性决策边界和非线性边界

逻辑回归代价函数：

误差平方和代价函数在逻辑回归模型中存在的问题：误差平方和代价函数将是一个非凸函数（Non-convex function）。
逻辑回归的代价函数为：
- 当实际的$ y=1 $且$hθ (x$)也为 1 时误差为$0$，当 $y=1$但$hθ (x)$不为1时误差随着hθ的变小而变大；
- 当实际的 $y=0$ 且$hθ (x)$也为$ 0 $时代价为$ 0$，当$y=0$ 但$hθ (x)$不为$ 0 $时误差随着$hθ$的变大而变大 $Cost(h_θ (x),y)=-y log(h_θ (x)) -(1-y)log(1-h_θ (x))$ $J(θ)=-\frac {1}{m} ∑_{i=1}^m [y^{(i)} logh_θ (x^{(i)} )+(1-y^{(i)} )log(1-h_θ (x^{(i)} ))]$

逻辑回归（对数回归）本质上是线性回归，只是在特征到结果的映射中加入了一层函数映射，即先把特征线性求和，然后使用函数 \$g(z)\$做为假设函数来预测，将连续值的特征值映射到0 和 1上。

应用梯度下降算法：

$repeat\ until\ convergence\ and\ update θ_0, θ_1,…,θ_n\ simultaneously:\{ $

$\}$

在运行梯度下降算法之前，进行特征缩放依旧是非常必要的。
高级优化算法：共轭梯度法、BFGS (变尺度法) 、L-BFGS (限制变尺度法)等。使用比梯度下降更复杂的算法来最小化代价函数，通常不需要手动选择学习率α。

多类别分类（一对多）：

假设数据集有三个类别，$三角形y=1、方框y=2、叉叉y=3$

分类思路：将其分成三个二元分类问题
- 先从用三角形代表的类别1 开始，实际上可以创建一个新的”伪”训练集，类型2 和类型3 定为负类，类型1 设定为正类，创建一个新的训练集，拟合出一个合适的分类器（这里的三角形是正样本，而圆形代表负样本），就得到一个正边界。
- 将多个类中的一个类标记为正向类$（ y=1）$，然后将其他所有类都标记为负向类，这个模型记作$hθ^{(1)} (x)$, 接着，类似地第我们选择另一个类标记为正向类$（ y=2）$，再将其它类都标记为负向类，将这个模型记作$hθ^{(2)} (x)$，依次类推最后得到一系列的模型简记为：$h_θ^{(i)} (x) = P(y=i| x;θ)\ \ \ \i=(1,2,3…k)$
- 最后，在需要做预测时，将所有的分类机都运行一遍，然后对每一个输入变量，都选择最高可能性的输出变量。
多类别分类问关键点：
- 挑选分类器：选择出哪一个分类器是可信度最高效果最好的，那么就可认为得到一个正确的分类，无论i值是多少，都有最高的概率值。
- 训练逻辑回归分类器：$hθ^{(i)} (x)$其中$i$对应每一个可能的 $y=i$，最后为了做出预测，给出输入一个新的$ x $值，用这个做预测，要做的就是在三个分类器里面输入 $x$，然后我们选择一个让$hθ^{(i)} (x)$最大的$i$，即：$maxi hθ^{(i)} (x)$。

逻辑回归算法实现与应用：

具体请参照：逻辑回归算法实现与应用

2.1.3 回归算法正则化

2.1.3.1 过度拟合问题

过度拟合也称为高方差，指的是如果有非常多的特征，通过学习得到的假设可能能够非常好地适应训练集（代价函数几乎为 0），但是可能会不能推广到新的数据，即不能做出相对准确的预测。以多项式理解， x 的次数越高，拟合的越好，但相应的预测的能力就可能变差。

问题描述：

线性回归过度拟合问题：第一个模型是一个线性模型，不能很好地适应训练集，欠拟合高偏差；第二个模型能比较好地适应训练集，在新输入变量进行预测时效果也比较好；第三个模型过于强调拟合原始数据，丢失了算法预测新数据的本质，过拟合高方差。

逻辑回归过度拟合问题：

解决方案：

降维：丢弃不能帮助做出正确预测的特征，手工选择保留哪些特征，或使用主成分分析算法。
正则化：保留所有的特征，但减小特征参数 $θ_j$ ，即减少某些特征对最终预测值的影响。

2.1.3.2 回归正则化

正则化模型推导：

正则化代价函数推导：
- 减少$θ_3$和$θ_4$的大小：正是那些高次项导致了过拟合的产生，所以若能让这些高次项的系数接近于0的话，就能很好的拟合，即可减少$θ_3$和$θ_4$的大小（设置一点惩罚）： $min_θ \frac {1}{2m} ∑_{i=1}^m(h_θ (x^{(i)})-y^{(i)})^2 +1000θ_3^2+10000θ_4^2$
- 减小所有$θ_j$的大小：若有非常多的特征，并不知道哪些特征需要惩罚，对所有的特征进行惩罚，并让代价函数最优化的软件来选择惩罚的程度，根据惯例一般不对$θ_0$进行惩罚，得到了一个较为简单的能防止过拟合问题的假设： $min_θ \frac {1}{2m} [∑_{i=1}^m(h_θ (x^{(i)})-y^{(i)})^2 +λ∑_{j=1}^n θ_j^2] \ \ \ \ (λ 又称为正则化参数 )$ 保证很好的拟合数据项： $ ∑{i=1}^m(hθ (x^{(i)})-y^{(i)})^2$
  保证更好的预测数据，防止过拟合项： $λ∑_{j=1}^nθ_j^2$
归一化参数λ特点：
λ过大会最小化所有的参数，导致模型变成 $h_θ (x)=θ_0$，欠拟合。λ过小会最大化所有的参数，导致模型过拟合。

正则化线性回归：

正则化梯度下降算法：
$repeat\ until\ convergence\ and\ update\ θ_0, θ_1,…,θ_n\ simultaneously:\{ $
$θ_0≔θ_0-\frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_0^{(i)}$ $θ_j≔θ_j-\frac {α}{m} ∑_{i=1}^m ((h_θ (x^{(i)})-y^{(i)}) x_n^{(i)}+\frac {λ}{m} θ_j)\ \ (j=1,2,…,n)$
$\}$
合并同类项有：
$repeat\ until\ convergence\ and\ update\ θ_0, θ_1,…,θ_n\ simultaneously:\{ $
$θ_0≔θ_0-\frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_0^{(i)}$ $θ_j≔θ_j (1-α \frac {λ}{m}) - \frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_n^{(i)}\ \ (j=1,2,…,n)$
$\}$
正则化正规方程算法：
$θ=(X^T X+λ \left[ \begin{matrix} 0&0&0&0&0&0 \\ 0&1&0&0&0&0 \\ 0&0&1&0&0&0 \\ .&.&.&.&.&.\\ 0&0&0&0&0&1 \\ \end{matrix} \right])^{-1}X^T Y$

正则化逻辑回归：

$J(θ)=-\frac {1}{m} ∑_{i=1}^m [y^{(i)} logh_θ (x^{(i)} )+(1-y^{(i)} )log(1-h_θ (x^{(i)} ))]+\frac {λ}{2m} ∑_{j=1}^nθ_j^2$

$repeat\ until\ convergence\ and\ update\ θ_0, θ_1,…,θ_n\ simultaneously:\{ $

$θ_0≔θ_0-\frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_0^{(i)}$ $θ_j≔θ_j (1-α \frac {λ}{m} - \frac {α}{m} ∑_{i=1}^m (h_θ (x^{(i)})-y^{(i)}) x_n^{(i)}\ \ (j=1,2,…,n)$

$\}$

看上去同线性回归一样，但是知道$h_θ(x)=g(θ^T X)$，所以与线性回归不同。虽然正则化的逻辑回归中的梯度下降和正则化的线性回归中的表达式看起来一样。