machine_learning – 深萌图谱

that_is_the_way_understanding_the_data

# 序

Tom Mitchell于1998年给机器学习下了个定义——计算机程序从经验E中学习，解决某任务T，进行某一性能度量P，通过P测定在T上的表现因经验E而提高。最主要的两类机器学习算法为监督学习(Supervised Learning)和非监督学习(Unsupervised Learning)。监督学习就是人去教会机器做某件事。非监督学习就是让计算机自己学习。当然还有其它类别的机器学习，如强化学习和推荐系统。

监督学习：给算法一个包含正确答案的数据集，从其中学到或建立一个模式（函数），并以此模式来推测（预测）新的实例。训练资料是由输入物件（通常是向量）和预期输出所组成。函数的输出可以是一个连续的值（称为回归分析），或是预测一个分类标签（称作分类）。

非监督学习：给定的数据并不会被特别标识，学习模型是为了推断出数据的一些内在结构。如聚类等。

# 模型描述

在监督学习中，给一个数据集，这个数据集被称作训练集（Training Set），我们的工作就是从这个训练集中学习如何进行预测。

用m表示训练样本，和统计学用n表示样本不一样。如果用x表示输入变量，用y表示输出变量，则（x, y）表示一个训练样本。那么（x⁽ⁱ⁾, y⁽ⁱ⁾）则表示第i个训练样本。

监督学习算法的工作：向学习算法提供训练集，学习算法的任务是输出一个函数h(hypothesis)，函数h的作用是将输入变量x输入，然后输出预测的y。

那么设计一个学习算法，下一个需要做的就是，决定怎么表示这个假设函数h。

在回归中，最初选择的假设函数，就是单变量线性回归（Univariate Linear Regression）。这种线性的情况是学习的基础，之后将在此基础上构建更复杂的模型以及更复杂的学习算法。

损失函数（cost function）：是将随机事件或其有关随机变量的取值映射为非负实数以表示该随机事件的“风险”或“损失”的函数。在应用中，损失函数通常作为学习准则与优化问题相联系，即通过最小化损失函数求解和评估模型。例如在统计学和机器学习中被用于模型的参数估计。

$$\begin{align}& \large \textbf{Hypothesis: }\\& \large \quad h_\theta(x)=\theta_1x+\theta_0\\& \large \textbf{Parameters: }\\& \large \quad \theta_1,\;\theta_1\\& \large \textbf{Cost Function: }\\& \large \quad J(\theta_0,\theta_1)=\frac{1}{2m}\displaystyle\sum_{i=1}^{m}\left(h_\theta \left(x^{(i)}\right)-y^{(i)}\right)^2\\& \large \textbf{Goal: }\underset{\theta_0,\theta_1}{\text{minimize}}J(\theta_0,\theta_1)\end{align}$$

在线性回归中，平方误差代价函数是解决回归问题最常用的手段。我们希望找到一条与数据拟合的直线，所以构造了假设函数，包括两个参数θ。随着参数选择不同会得到不同直线，于是代价函数也不同，优化目标就是使得代价最小。

学习算法的优化目标就是通过选择θ的取值，获得最小的代价函数，线性回归的目标函数是minimizeJ(θ)。

如在(1,1)，(2,2)，(3,3)的线性回归中，不同的θ取值，代价函数也不同，如下图所示。

当考虑两个变化的参数时，代价函数就需要用等高线法来描绘。当θ₁和θ₀取不同的值时，它离椭圆圆心（J的最小值）的距离都不同。

# 梯度下降

梯度下降（Gradient Descent）：是一种可以将代价函数J最小化的算法。梯度下降算法不仅用于线性回归中，还广泛用于机器学习的众多领域。

将代价函数的图像看作是两座山，一个人正站在山上某一点上想尽快下山，如果他要在某个方向上走一小步，他应该朝哪个方向迈步。上面两个图表示，如果这个人站在不同点，则梯度下降法会将这个人带到不同的局部最低处（梯度下降算法的一个特点）。

梯度下降的数学原理由下图表示。 := 表示赋值。每一次梯度下降都会同时给θ₀和θ₁赋值。式中α是被称作学习率的数字，用来控制在梯度下降时，迈出多大的步子。

$$\begin{align}& \large \textbf{Gradient descent algorithm}\\& \large \text{repeat until convergence \{}\\& \large \quad \theta_j:=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta_0,\theta_1)\quad (\text{for} \;j=0\;\text{and}\;j=1)\\& \text{\}}\\\\& \hline\\& \text{Correct: Simultaneous update}\\& \;\;\large \text{temp0}:=\theta_0=\alpha\frac{\partial}{\partial\theta_0}J(\theta_0,\theta_1)\\& \;\;\large \text{temp1}:=\theta_1=\alpha\frac{\partial}{\partial\theta_1}J(\theta_0,\theta_1)\\& \large \;\;\theta_0:=\text{temp0}\\& \large \;\;\theta_1:=\text{temp1}\end{align}$$

θ₀和θ₁是同时更新的

结合下图理解梯度下降的原理，上图和下图都是不考虑θ₀的情况。上文已经讲到过，α为学习率，α右侧的偏导数在途中则表示为代价函数的斜率。

当某一点在最低代价的右侧时，如下图所示，则梯度下降更新函数中偏导数为正数，θ₁将会变得更小，然后再次更新。当某一点在最低代价左侧时，如下图所示，则梯度下降更新函数中偏导数则为负数，减一个负数则为加一个整数，θ₁实则变大。

更新函数中的学习率：如果α太小，则梯度下降会下降地很慢。但如果α太大，它会导致无法收敛甚至发散。

实际上，在梯度下降中，当我们接近局部最低点时，梯度下降法会自动采取更小的幅度，因为越接近局部最低点，偏导数的值越小，梯度下降法将自动采取较小的幅度。所以也不用另外减小α。

接下来将梯度下降和代价函数结合，得到线性回归的算法

$$\begin{align}& \large \textbf{Linear Regression Model}\\& \large \;\; h_\theta(x)=\theta_1x+\theta_0\\& \large \;\;J(\theta)=\frac{1}{2m}\displaystyle\sum_{i=1}^{m}\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right)^2\end{align}$$

将右侧的J(θ)代入到左侧的梯度下降中去，并将θ0和θ1同时更新，就得到了线性回归算法。如下图所示。

不同于之前展示的两个山脉一样的代价函数，线性回归的代价函数是一个凸函数（弓形函数）。这个函数没有局部最优解，只有全局最优解。所以计算这种代价函数的梯度下降时，它总会收敛到全局最优解。

以上的算法，有时被称作Batch梯度下降。Batch意味着，每一步下降，我们都遍历了整个训练集的样本。

# 矩阵

矩阵：矩阵维度的描述是行×列，如R^4×2则是四行二列的矩阵。A_ij表示第i行第j列的元素。向量是一个特殊的矩阵，向量是只有一列的矩阵。

矩阵向量乘法运算：

矩阵向量乘法的一个小例子，如下图所示，使用假设函数一次性进行四次预测。这样可以用一行代码完成整个过程。这不仅简化了代码量，还提高了计算效率。

矩阵矩阵乘法运算

矩阵矩阵乘法的一个例子。如要预测四间房子的价格，但有三个假设函数，如果想将这三个假设函数都用于者四间房子，就可以用矩阵×矩阵。用线性代数函数库的方法还可以利用处理器多个线程进行并行计算。高效简洁。

矩阵乘法具有一些特性：

不满足交换律，除非是和单位矩阵相乘
满足结合律
I_n×n为单位矩阵，对角线上都是1，其它都为0

逆矩阵（Matrix Inverse）

如果一个m×m的矩阵A有逆矩阵，则它的逆矩阵为A^-1。AA^-1=A^-1A=I_m×m。可以看到矩阵A是m×m的矩阵，这种行列数相等的矩阵称为方阵，实际上，只有方阵才有逆矩阵。但也不是所有矩阵都有逆矩阵，如全是0的矩阵就没有逆矩阵。

没有逆矩阵的矩阵成为奇异矩阵（singular）或退化矩阵（degenerate）。可以把它们想成非常近似于0。

转置矩阵（Matrix Transpose）

假设A是一个m×n的矩阵，设矩阵B等于A的转置，那么B就是一个n×m的矩阵，维度和A相反。

看18，用Python实现一下逆运算和转置运算。

多元线性回归

还是用房价的例子。用于预测房价的信息不仅有房子的面积，还有卧室的数量、楼层数、房龄等，这就需要使用多元线性回归，而不是一元线性回归。如下图（左）所示，x⁽ⁱ⁾表示第i个训练样本的输入特征值，可以看作是一个4维向量。

将之前一元线性回归的假设函数改写成如下右图所示形式。为简化这个等式的表达方式，将x₀⁽ⁱ⁾的值设为1，x₀原本是不存在的，但设为1的化可以刚好使截距为它本身。那么特征向量X变成从0开始标记的n+1维向量。同时把所有的参数θ看作一个向量，也是一个从0开始的n+1维向量。

经过以上变换，假设函数就可以写成θ^Tx的形式。

多元梯度下降

上面探讨了多元线性回归的假设形式，这里讲如何设定该假设的参数，如何使用梯度下降法来处理多元线性回归。上面的图片已经给出了多元线性回归的假设形式 h_θ(x)=θ^Tx ，此模型的参数包括θ₀到θ_n，可以看作一个θ的n+1维向量。

下右图左侧表示一元线性回归的梯度下降，右侧表示多元线性回归的梯度下降。

# 梯度下降实用技巧

特征缩放

如果有一个含有多个特征的机器学习问题，你能确保这些特征（的取值）都处在一个相近的范围，这样梯度下降就能更快地收敛。

从代价函数的等值线图来理解，如果特征的取值差别特别大，那么等值线将会呈现出一种特别歪斜并且椭圆的形状。那么梯度下降将会花很长一段时间并且可能来回波动，很长时间之后才会收敛到全局最小值。解决这个问题的有效办法就是特征缩放，比如变换单位（每100，每1000）等。

如下右图就是将原始的特征值缩放到0到1之间，以更快的执行梯度下降。这就是特征缩放。

一般来说当我们执行特征缩放时，我们通常的目的是将特征的取值约束到 [-1, 1] 。别太大，也别太小。太大太小都背离特征缩放的初衷。

均值归一化（Mean Normalization）是特征缩放的一种方法，均值归一化如下公式所示。

μ₁表示训练集中特征x₁的平均值，s₁表示训练集中特征x₁的标准差或极差。

学习率α

通过minJ(θ)与迭代次数的曲线可以观察出梯度下降是否正常工作，如下左图所示，如果正常工作的话，每一次迭代，J(θ)都应该下降。

还可以通过曲线看出梯度下降算法是否已经收敛，如曲线末端已经很平缓了，感觉就已经收敛了。当然也有下右图所示的自动收敛测试，原理是如果代价函数下一步迭代后的下降小于一个很小的值，则认为梯度下降已经收敛。但这个阈值不好确定，所以看曲线更方便。

如果J(θ)随着迭代次数而不断上升的话（曲线是向上的），则说明梯度下降没有正常工作，这通常意味着应该减小学习率α。还有一种情况曲线是U字形，这也意味着学习率α过大，梯度下降算法不断冲过最小值，导致J(θ)上升。还有一种情况是曲线呈ww形，这也是学习率过大的结果，用小一点的学习率就行。

数学家已经证明只要学习率α足够小，那么每次迭代后代价函数J(θ)都会下降。当然学习率也不能太小，否则梯度下降会收敛得很慢。

每选一个学习率，绘一个J(θ)与迭代次数的图像，学习率可以从0.001,0.003,0.01,0.03,0.1,0.3,1这样选。

# 特征和多项式回归

根据已有的特征来创造新的特征，如知道矩形房屋的长宽特征，可以创造面积特征，及面积的平方、面积的立方或平方根特征。由称为未知数的变量和称为系数的常数通过有限次加减法、乘法以及自然数幂次的乘方运算得到的代数表达式，进行线性回归，就是多项式回归。由于可能涉及到幂的运算，特征缩放就尤为重要。

为了得到比较好的拟合效果，就需要熟悉不同多项式的函数曲线，同时还需要选择合适的特征。如在上右图中，房价和面积的关系可以通过加一个面积（房子长宽特征的乘积）的平方根多项式来拟合。

那么在做回归的时候，可以设计不同特征，并且选用不同的复杂的函数来拟合，而不仅仅是一条直线来拟合。

当然有些算法能自动选择使用哪些特征，以及如何使用这些特征。

# 正规方程（Normal Equation）

正规方程对于某些线性回归问题会给更好的办法来求得参数θ的最优值。与梯度下降法不同，正规方程不需要迭代以求得θ的最优值，它仅需一次计算就可以求解θ的最优值。

在微积分中，如果θ是一个实数，最小化一个二次函数，需对它求导并令等式等于0，然后求出θ的值就是最优解。但在感兴趣的问题中，θ不再是一个实数，而是一个n+1维的向量。一般来说，这也是求每个θ的偏导数然后令等式为0，最后解出每一个θ。但这过于复杂。

那么正规矩阵就提出一个快速的解法，用一下例子举例，θ求出来等于(X^TX)^-1X^Ty

使用正规方程，就不需要进行特征缩放。

以下是梯度下降法和正规方程法的优缺点。当特征变量小于10000时，做线性回归可以用正规方程，但当特征变量特别多时，那就用梯度下降。

梯度下降有优点有1）当特征变量很多时，依然很好的运行。2）在分类算法中也可以使用。缺点有1）需要选择学习率。2）要进行很多次迭代。

正规方程优点有1）不用选择学习率。2）不用迭代。但缺点是在特征变量很多时，就会运行地非常慢。

不可逆性

在上面的θ求解公式中，需要求X^TX的逆矩阵，但如果X^TX是不可逆的呢？如果使用Octave的 pinv() 函数，那么即使没有逆也可以求出θ，因为该函数会生成伪逆。

上图指出，XTX没有逆可能由两种原因导致。一是学习问题包括多余的特征，如某地块的平方米和平方英尺特征。二是特征数大于等于训练样本量。

# 矢量

向量化：将特征向量化将提高线性回归算法的效率。如下图所示，左侧是在非向量化的情况下计算假设函数h(x)，右侧是向量化的情况下计算假设函数。不仅代码少了，效率还提高了。

如线性回归梯度下降算法的更新规则，要将θ们同时进行更新，用向量化的代码将大大提高效率。那么通常情况下要实现这三个θ的同步更新需要写三行代码，但使用向量化就只需要一行代码实现。

实际上，将θ看作一个n+1维的向量，里面就是θ₀到θ_n，然后令θ=θ-αδ，δ也是一个n+1维的向量，绿色框框里的那部分。x₁、x₂分别表示第一个、第二个特征的向量。x₁⁽ⁱ⁾则表示第一个特征的第i个值。那么就完成了矢量化的线性回归。

# 分类

若预测变量y是一个离散值，那么这就是一个分类问题。Logistic回归是一个分类算法，虽然他叫回归，这是历史问题，但它是一个分类算法。如果预测变量分了多个类，就是多分类问题了。

以下是分类问题的假设函数，Sigmoid和Logistic是同义词，代表 g(x) 函数。这样的话，h_θ(x)就在[0, 1]之间了。θ^Tx实际上是线性回归的假设函数。

接下来看一看解释。h_θ(x)=0.7的意思是，x特征下得到正向结果（y=1）的概率为0.7。其实可以将h_θ(x)看作是得到正向结果的概率。

决策边界：在特征空间内，根据不同特征对样本进行分类，不同类型间的分界就是针对该训练集的决策边界。

为了拟合Logistic回归模型中的θ，要定义用来拟合参数的代价函数。如果沿用之前线性回归那个J(θ)，那么会得到一个非凸函数。但为了使得在运用梯度下降法得到全局最优解时，我们更想看到代价函数是一个凸函数（convex），所以需要进行下面的操作。

下面左图给出了单训练样本Logistic回归的代价函数（当y=1时），实际上就是粉红色函数那一截。

可以看到如果因变量的种类为1，h_θ(x)=1的情况下，代价函数则为0。也就是说，如果假设函数预测的类型为1，而y刚好等于我预测的类型，那么代价则为0。相反的，若y为1，但我预测的值为0，那么代价将会变得无穷大，也就是说用非常非常大的代价值来惩罚这个学习算法。

当y=0时，单训练样本代价函数如下图所示。当y=0时，我们的假设函数hθ(x)却非常肯定的给出了1这个预测，那么代价将会相当大（趋近于无穷）。如果y=0，h_θ(x)也预测的0，那么代价为0。

虽然凸性分析超出这节课的范围，但这也显示我们所选的代价函数会给我们一个凸优化问题，让整体的代价函数J(θ)成为一个凸函数，并没有局部最优解。

简化Logistic回归的代价函数与梯度下降

上面部分将单训练样本Logistic回归的代价函数分成了两种方法来写，但简化成更紧凑的一个等式。

这样一来，无论当y=0或1，另一种情况都会乘以0被消去。这样一来，写Logistic回归的代价函数就更方便了。如下左图所示便是Logistic回归的代价函数了。接下来，如下右图所示，要找这个J(θ )在最小值时的θ。

用梯度下降法时写出更新函数，发现这个函数和线性回归的更新函数是一模一样的。但，它们的h_θ(x)是不一样的，如红字所示。接下来可以使用循环来同步更新，也可以使用向量化的方式来同步更新，后者效率更高。

高级优化

梯度下降法不是我们唯一能用的算法来计算代价函数和偏导项，还有一些其他更高级更复杂的算法，如果能用这些方法来计算代价函数和偏导项的话，那么这些算法就是为我们优化代价函数的不同方法。如共轭梯度法、BFGS、L-BFGS。这些算法有很多优点，如不用手动选择学习率，比梯度下降更快等。

这些算法有一个更智能的内循环，叫线搜索算法，它可以自动尝试不同的学习率并自动选择一个好的学习，甚至可以为每一次迭代选择不同的学习率。

下图中的 jVal 就为代价函数， gradient(1) 为偏导项。

多类别分类问题

下图直观解释什么是多类别分类。下左图所示为二分类问题。

下右图为多类别分类问题，需要构建三个新的伪训练集，在伪训练集内将某一类别设为正类，另外两个设为负类，这样就把多类别分类转为二分类问题了，之后再拟合一个分类器（classifier），称为h_θ⁽¹⁾(x)，这就是一个标准的Logistic回归分类器了，再训练这个分类器，得到那个粉色的判定边界。

对于i=1,2,3，拟合分类器 h_θ⁽¹⁾(x) ，来尝试估计出，给定x和θ时y=i的概率。

最后，我们已经训练好了Logistic回归分类器h_θ⁽ⁱ⁾(x)来预测i类别y=i的概率，为了做出预测，我们给出一个新的输入值x，那么在三个分类器中都输入x，取使得h最大的那个类别i，也就是可信度最高效果最好的那个分类器。

# 过拟合问题

下面左右图分别回归的过拟合和分类的过拟合的两个案例（均为最右边那个图）。下面只解释左图。

如左图所示，用线性回归来用面积预测房子的价格，很明显看到拟合出来应该是一条平滑的曲线。

（左图）第一张图尝试用一次线性回归拟合，但很明显这个算法没有很好的拟合数据集，称之为欠拟合（underfit），或说这个算法具有高偏差（high bias），这两种说法都意味着算法没有很好地拟合训练数据。偏差意思是，罔顾数据的不符，先入为主地拟合一条直线，最终导致拟合效果很差，就好像这个算法有很大的偏见，认为是线性相关。

（左图）第二张就是刚好合适的函数。

（左图）第三张的算法通过了每一个数据点，但是不断上下波段，非常扭曲，并不是一个预测房价的好模型。这种情况就是过拟合（overfit），也称这个算法有高方差。只要使用足够多的多项式，就能使得算法拟合所有的数据，但是假设函数就会太庞大，变量太多，以至于没有足够的数据来约束它，来获得一个好的假设函数。这就是过度拟合。

Overfitting：过拟合问题将在变量过多的时候出现，这时训练出的假设函数能很好拟合训练集，代价函数可能很接近（或等于）零，但它千方百计拟合训练集，导致它无法泛化（generalize）到新的样本中，不能进行预测。

有两个办法解决过拟合问题——

减少特征的个数。具体而言可以手动选择一些变量，或者使用“模型选择算法”，自动选择保留哪些特征。
正则化（regularization）。保留所有特征，但减少参数θ的大小。如果每个特征都有用，不想丢弃的话，就可以用这个方法。

正则化

以面积预测房价的例子来说，用二次函数的那个函数可以很好的拟合数据，但用一个阶数过高的多项式来拟合，就出现了过拟合的问题，泛化地不好。

那我们不妨在代价函数中加入惩罚项，来使得θ₃和θ₄都非常小。如下图所示。这就相当于去掉了原来算法的后面两项，使得其相当于左边那个二次函数（但实际不是）。

以上就是正则化背后的思想，就是，如果参数θ的值较小，就意味着一个更简单的假设函数，也就更不容易出现过拟合问题。

不过在实际问题中，我们不知道哪一项或哪几项是高阶项，不知道挑选出哪些参数来缩小它们的值，所以在正则化中，我们要做的是修改代价函数，来缩小所有的参数θ（除了θ₀，约定俗成，加不加θ₀的惩罚项都一样）。如下图红框所示，加上了一个求和项（正则化项）。

红框中的λ是正则化参数（regularization parameter），其作用是控制两个不同目标之间的取舍，控制这两个目标之间的平衡：

第一个目标则是绿色下划线部分（目标函数第一项），就是更好地拟合训练集。
第二个目标则是保持参数θ尽量的小（目标函数第二项），从而保持假设模型相对简单，避免出现过拟合。

但如果对θ的惩罚程度过大，就会导致这些参数都接近于0，相当于把假设函数所有项都忽略了，就留了一个θ₀。也就是一条直线来拟合数据，这很明显是一个欠拟合的情况。所以说，为了让正则化起到应有的效果，应该注意去选择一个更合适的正则化参数λ。后面会讲很多方法自动选择正则化参数。

线性回归的正则化

到目前为止（指该帖），共有两种方法来求解线性回归，一个是梯度下降，另一个则是正规方程。

先讲一讲把梯度下降求解线性回归推广到正则化线性回归。如下左图所示是一个正则化线性回归的代价函数，要用梯度下降法来求这个代价函数的最小值的参数θ。J(θ)第一项则是线性回归的一般目标，第二项则是额外的正则化项。再看右图，在梯度下降时除了θ0，都再右侧加了一个额外的项，这就是为了对正则化线性回归使用梯度下降法做出的修改。再化简得第三个的式子。直观地来讲，（第三个式子）第一项就是把θ_j向0的方向缩小了一点点，第二项与在添加正则化项之前的梯度下降更新是一样的。

用正规方程法来求解正则化线性回归，解决过拟合问题，即使在一个很小的训练集里拥有大量特征。让我们能更好的用线性回归解决很多问题。设正则化线性回归的代价函数的偏导数等于0时，求出的θ，使得代价函数为全局最小值。实际上它与之前的正规方程求解线性回归不同的地方就是加了个蓝色的项（λ×一个很怪的矩阵）。但恰恰是这个东西，解决了在样本量小于特征数时(X^TX)不可逆的问题。这也就使得，即使在一个很小的训练集拥有大量特征，线性回归也不会出现过拟合，效果也还好。

Logistic回归的正则化

该帖上面讲过拟合问题的时候没有提到正则化Logistic回归代价函数的公式，下图给出这个公式。图中蓝色的决策边界非常扭曲，从右侧的假设函数也可以看出有很多特征何高阶多项式，没有泛化的潜力。粉色的决策边界就更合理，是正则化Logistic回归。因此，使用正则化的话，即使有很多帖子，正则化都可以帮我们避免过拟合。

接下来给出梯度下降求解正则化Logistic回归的公式。感觉和梯度下降法求线性回归很像，但它们的假设函数h(x)不同。

高级优化函数的正则化

上面讲过，建立一个costFunction函数，然后将它赋给 fminunc() 函数（高级优化函数，意思是函数在无约束条件下的最小值）。然后costFunction会返回jVal（代价函数）和gradient（梯度），下面就要写代码计算这两个东西。但将其推广到正则化Logistic回归，就有了代码所示的部分，只不过代码从gradient(2)开始就加了一个正则化项的偏导。因为是从θ₁开始的嘛。

# 非线性假设

对于复杂的非线性假设，如果用线性回归或者Logistic回归，那就意味着几何级增长的特征数量（高阶多项式）。只是包括平方项和立方项特征的简单Logistic回归算法并不是一个在n很大的时候学习复杂的非线性假设的好办法，因为特征太多。神经网络在学习复杂的非线性假设上被证明是一种好得多的算法。

神经网络由来已久，最初的目的是制造模拟大脑的机器。大脑很神奇，我们通过大脑不断学习新的事物，但不会像运行上千个程序那样感到负担，或许有一个算法，使得我们可以不断的学习新的东西。

神经网络

将神经元模拟成一个逻辑单元，下面用一个很简单的模型来模拟神经元工作。将神经元模拟成一个逻辑单元。黄色的为神经元细胞体，通过输入通道（树突）传递给神经元一些信息，然后用神经元做一些计算，然后通过它的输出通道（轴突）输出假设函数计算的结果。X₀是偏置单元，加它与否取决于具体例子表现起来是否方便。于是这个简单模型就是带有Sigmoid(或Logistic)激活函数的人工神经元，这个Sigmoid激活函数指代的是非线性函数 g(z) 。在这里模型的参数θ，有关神经网络的文献里也称模型的权重。

上图是单个人工神经元，神经网络就是一组神经元连接在一起的集合。输入层输入特征X₁X₂X₃，输出层输出假设的最终计算结果。第二层a₁上面的⁽²⁾指的是第二层。a₁⁽²⁾实际上是第二层第1个神经元的激活项。激活项是指由一个具体神经元计算并输出的值。

下图展示上面这个神经网络的具体计算步骤，刚才已经说过，这个 a_i^(j) 是第j层第i个神经元的激活项，激活项是指有一个具体神经元计算输出的值。此外，神经网络被这些矩阵参数化。 θ^(j) 就是这个权重矩阵，它控制从某一层到下一层的映射。下图中的a₁⁽²⁾等于 sigmoid() 激活函数作用在输入的θ₁₀⁽¹⁾x₀…θ₁₃⁽¹⁾x₃的线性组合上的结果。那么θ⁽¹⁾是控制从三个输入单元到三个隐藏单元的映射的参数矩阵，是一个3×4的矩阵。

Generally，如果一个网络在第j层有S_j个单元，在j+1层有S_j+1个单元，那么控制第j层到j+1层映射的矩阵θ(j)的维度是S_j+1×(S_j+1)。

第三层的那个神经元，计算假设函数的最终结果。可以看到式子中是θ₍₂₎而不是θ₍₁₎，因为控制的是从第二层到第三层（输出单元）的映射。

那么上图的神经网络，定义了函数h从输入x到输出y的映射。这些假设被参数θ参数化，这样一来，改变θ就能得到不同假设。

以向量化的方法高效实现神经网络的计算

下图，从输入单元的激活项开始传播给隐藏层，计算隐藏层的激活函数，再计算输出层的激活项，这个过程叫向前传播（forward propagation）。接下来结合下图讲一讲这个过程的向量化实现方法。将a₁⁽²⁾里的 g() 函数里面的θ₁₀⁽¹⁾x₀…θ₁₃⁽¹⁾x₃赋给z₁⁽²⁾，这个z值是特定神经元的输入值x₀x₁x₂x₃的加权线性组合。

将x看成x₀-x₃组成的向量，z⁽²⁾看作z值们组成的向量。那么用向量化的形式写出，z⁽²⁾=θ⁽¹⁾x，a⁽²⁾=g(z⁽²⁾)。图中定义了a⁽¹⁾=x，所以z⁽²⁾=θ⁽¹⁾a⁽¹⁾。最后计算假设函数的结果那个神经元激活函数里的值可以写作z⁽³⁾，z⁽³⁾=θ⁽²⁾a⁽²⁾，最后假设函数可以写作h_θ(x)=a⁽³⁾=g(z⁽³⁾)。那么绿色框框内的公式来计算h(x)，那就会非常有效，这就是向量化的实现方式。

如下左图所示，把左边部分蒙起来，右侧就像一个Logistic回归，只是输入这个回归的特征，是隐藏层计算出来的数值。也就是说，它们是学习得到的函数输入值，也就是说第一层映射到第二层的函数是由其它参数θ⁽¹⁾决定的。也就是说根据θ选择的不同参数，有时可以学到有趣和复杂的特征，就可以得到更好的假设函数，比用原始的x0-x3输入时得到的假设好得多。甚至可以用x1x2等多项式作为输入项，这个算法可以灵活地尝试快速学习任意的特征项。

在神经网络中，神经元的连接方式叫做架构（Architecture），如下图所示。第一层还是输入层，第二三层是隐藏层，可以计算出更复杂的特征，第四层是输出层，这样以来得到非常有趣的非线性假设函数。

接下来是一个详细的例子来说明神经网络是怎么计算复杂非线性函数的输入的，这个例子能够帮助理解为什么神经网络可以用来学习复杂的非线性假设模型。

下图例子中有两个输入特征x₁和x₂，它们都只能取0或1。左边的部分可以看作右边复杂机器学习问题的简化版。我们的想做的是学习一个非线性的判断边界，把红叉和蓝圈分开。要学习这个问题，需要用到 XOR 计算，异或计算，相同为0，不同为1。 XNOR 等价于 NOT(x₁XORx₂) 。

拟合AND运算

为了构造这个计算AND运算的只含有单个神经元的神经网络，可以加一个偏置单元，然后调整神经网络中的权重，配合 Sigmoid 函数来拟合AND运算。 Sigmoid 函数的图像如右上角所示，当z为4.6时， g(z) 为0.99，且该函数关于y轴对称。下面可以看作三个θ组成的一个向量，分别为-30、20、20。

拟合OR运算

单个神经元的神经网络拟合OR运算只需改一下参数。

拟合NOT运算

拟合XNOR运算

把下图中上部分的三个单独的部分组合到一个网络当中，就可以拟合XNOR运算了。在图中下部分建立了一个神经网络来实现这个XNOR运算。

x1-x3是输入层，隐藏层中有两个神经元，三个原始特征映射到隐藏层不同神经元的权重不同，就完成了不同的稍微复杂的功能，从隐藏层到输出层再添加一个偏置单元，赋予权重，实现一个更复杂的运算，最后输出假设函数的结果。下半部分的图，左右侧要结合来看，更直观地理解神经网络是如何实现的。

那么这个函数就有一个输入层、一个隐藏层、一个输出层，最后得到了一个非线性的决策边界，用以计算XNOR函数。

神经网络多类别分类

在多分类问题中，y(i)就不是{1,2,3,4}了，而是一个向量，如在一个四分类问题中，就是[1,0,0,0]^T,[0,1,0,0]^T…[0,0,0,1]^T。一个训练样本由(x⁽ⁱ⁾, y⁽ⁱ⁾)组成，x⁽ⁱ⁾就是四种物体种的一个，如四张图中的一张图像，y(i)就是[1,0,0,0]^T…[0,0,0,1]^T中的一个。

那么我们希望找到一个办法使神经网络输出一些数值， h_θ(x⁽ⁱ⁾)≈y⁽ⁱ⁾ ，在四张图片分类的例子中，式中的 h_θ(x⁽¹⁾) 和 y⁽ⁱ⁾ 都是四维向量，分别代表四种不同的类别。

神经网络在分类问题中的应用

假设有一个如下图所示的神经网络，然后有一个右上角的m组训练集， L 表示神经网络中的层数（这里等于4）， s_l 表示l层的单元数，不包括偏置单元。

分类问题可以分为两种，一种是二元分类问题（如图中左部分所示），这种情况下会有一个输出单元，来计算h_θ(x)，h_θ(x)∈ℝ（属于一个实数）。那么 s_l 在这里就等于1，为了简化记法可以写成k=1。另一种是多类别分类问题（如图中右部分所示），也就是会有k个不同的类。如果有四类的话，那么hθ(x)∈ℝ^k（K维向量），这里K≥3（因为是四分类）。

神经网络的代价函数

神经网络中用到的代价函数是Logistic回归中用到的代价函数的一般形式，对于Logistic回归而言要使得代价函数最小化，可以看到Logistic回归的y⁽ⁱ⁾，表示它只有一个输出单元，也可以看到后面的正则项j从1开始，说明没有把偏差项θ₀正则化。

神经网络有k个y⁽ⁱ⁾（y_k⁽ⁱ⁾），也就是有k个Logistic输出单元。神经网络输出属于ℝ^k的向量， (h_θ(x))_i 表示第i个输出。与Logistic回归的代价函数不同的是，求和项把k个输出单元的所有输出项全加起来了，如果有四个输出单元，那么就是每一次Logistic回归的代价函数按四次输出的顺序依次把这些代价函数加起来。那个求和符号应用于y_k和h_k，因为我们主要将第K个输出单元的值和y_k值的大小作比较。后面那个额外的正则化项，就是对所有除了偏置单元的θ参数求和。

神经网络反向传播算法

上面讲了神经网络的代价函数，接下来讲让代价函数最小化的算法——反向传播算法。

上面已经交代了神经网络的代价函数，接下来需要使用梯度下降或更高级的算法来计算使得 J(θ) 最小时的θ。也就是说这里关注的是那个偏导项的计算。

下面是在只给定一个训练样本的情况下神经网络向前传播的计算过程。

接下来，为了计算那个偏导数，将用一个叫反向传播的算法。

反向传播算法直观上来说需要计算每个结点的 error ，所谓误差就是单元的激活值与训练样本的真实值的差距， δ_j^(l)=a_j^(l)-y_j ，这个激活值实际上就是那个神经元的输出值。这里如果把δ、a、y都看作向量，就可以得出一个向量化的表达式 δ⁽⁴⁾=a⁽⁴⁾-y 。

先把输出层的δ计算出来，再一层一层往前计算δ，直到计算到第二层。第一层是输入层，就不做这个操作了。下图是仅有一个训练样本的情况，如果忽略正则项，就可以得到最下面的结果。在图中也可以看到 g'(z⁽²⁾)=a⁽²⁾·×(1-a⁽²⁾) ，通过微积分算出来的。

反向传播算法的完整过程

接下来讲有大量训练样本的情况下（假设有m个）。首先要设一个Δ_ij^(l)=0，可以理解为在编程中求一个累加之前的变量声明，用来计算代价函数的偏导项的。然后遍历每一个训练样本，都有设a⁽¹⁾=x⁽ⁱ⁾（x⁽¹⁾是第i个样本），进行一个向前传播来计算后面每一层的a^(l)（l=2,3,4..L），只有向前传播计算了激活值之后，才能计算出用于反向传播的 δ ，然后求得Δ_ij^(l)（累加每一个偏导数项，上图给出的计算方法，结合下图看），偏导项等于最后的D_ij^(l)。

理解反向传播

为了更好理解反向传播，先进一步研究一下前向传播的过程。算上偏置单元有三个箭头指向a₁⁽³⁾，设三个箭头上面的权重依次是{θ₁₀⁽²⁾,θ₁₁⁽²⁾,θ₁₂⁽²⁾}，那么z₁⁽³⁾就如图中下面公式所示，这就是前向传播在做的事。反向传播和前向传播非常相似，只是两个算法的计算方向不同。

举一个只有一个输出单元且只考虑一个训练样本的神经网络的例子，如左图所示。因只有一个输出单元，是所以这一个训练样本的 y⁽ⁱ⁾ 是一个实数。如果忽略正则化项（λ=0），那么对应这个训练样本的代价函数就是图中蓝色框中的东西，可以看作是神经网络输出值与真实值的差的平方（方差），所以这个 cost(i) 表示了神经网络预测样本值的准确程度，也就是神经网络输出值与实际观测值y⁽ⁱ⁾的接近程度。

下面右图就在进行一个反向传播。对反向传播算法的直观理解就是计算一个 δ_j^(l) ，也就是第l层中第j个单元中得到的激活项的“误差”，也是代价函数 cost(i) 关于 z_j^(l) 的偏导数。如果在神经网络内部稍微把 z_j^(l) 改一下就最终会影响到代价函数的值。δ衡量的是，为了影响这些z_j^(l)所改变神经网络中权重的程度，进而影响整个神经网络的输出。

接下来是最直观的公式环节，通过前向传播已经计算出了输出单元的激活值，那么 δ₁⁽⁴⁾=y⁽ⁱ⁾-a₁⁽⁴⁾ ，然后计算出前面每个节点的δ。如 δ2(2)=θ₁₂⁽²⁾δ₁⁽³⁾+θ₂₂⁽²⁾δ₂⁽³⁾ 。这些δ都只关于隐藏单元并不包括偏置单元。

把参数从矩阵展开成向量

该步骤是为了方便高级优化。如 fminunc() 这个高级优化方法假定θ为向量。但在神经网络中，θ不再是向量，而是矩阵，且梯度也以矩阵形式出现。所以在使用高级优化函数的时候，就需要从矩阵中取出向量来。

当参数存储为矩阵时，在进行正向传播和反向传播时会更方便；向量表达式的优点是，高级优化函数通常要求输入参数为长向量。

梯度检测

反向传播算法含有许多细节，实现起来比较困难，还很容易产生bug，当它与梯度下降或其它算法一同运行时，看起来反向传播算法正常运行， J(θ) 也在每次迭代中减小，但最后得到的值比没有bug情况下的值大一个量级，更糟糕的是把存在bug的结果当作最后的结果。

为了避免这种情况，有一种思想叫做梯度检测。如下图所示是一个代价函数 J(θ) ，并且有一个θ（实数），那么该点的导数就是图像在该点上的切线的斜率。现在要从数值上逼近这个导数，找到 θ-ε 和 θ+ε 两个点，连接这两个点，该线的斜率就约等于θ点的斜率（ε足够小）。一般来说取ε=10^-4，太小的话会出问题。

蓝线右侧被红叉划掉的是单侧差分，左侧红色的是双侧差分，双侧差分的结果更准确。

上述部分还只是θ是一个实数的情况，下面要考虑一个更普遍的情况，就是当θ是一个向量的情况。如下左图所示，来估计所有的偏导数项。用右图所示的循环求得 gradApprox ，检查该值是否约等于 DVec （从反向传播得到的导数）。如果这两者非常接近（只有几位小数的差距），那么我们就可以确信反向传播的实现是正确的，把这个 DVec 用到梯度下降或更高级的优化函数中时得到的结果是正确的。

总结一下，实现数值上的梯度检验的过程如下。第一步通过反向传播计算 DVec ，第二部计算出 gradApprox ，第三步对比它们是否非常相近，如果非常相近则关闭梯度检验，然后再进行训练。

随机初始化

当执行梯度下降或高级优化算法时，需要为变量Θ选取初始值。在Logistic回归中将Θ设置为 zeros 是可以的，但在神经网络中这样不起任何作用。

假设将Θ设置为 zeros ，那么激活值将会相等，δ将会相等，偏导数也会相等。两个蓝色的参数在进行梯度下降后，它们俩也会相等（虽然改变了）。如下图中，蓝色的权重依然相等，绿色的权重依然相等，红色的权重依然相等etc。这意味着，即使进行梯度下降，隐藏单元依然以相同的函数作为输入来计算，也就是说所有的隐藏单元都在计算相同的特征，都以相同的函数作为输入。这阻止了神经网络学习任何有趣的东西。

为了解决这个问题，在神经网络对参数进行初始化时，要使用随机初始化的思想。具体来说，上面的问题有时也被称为对称权重问题，也就是所有的权重都是一样的。随机初始化就是解决这种对称问题的方法。

具体来说就是，把每一个θ^(l)_ij随机初始化为一个在 [-ε,ε] 之间的某个实数。

所以，为了训练神经网络，应先将权重随机初始化为一个接近0的范围在-ε到ε之间的数，然后进行反向传播，再进行梯度检验，通过检验后关闭检验代码，再进行梯度下降（或其它高级优化函数）来最小化代价函数。第一步是打破对称性的流程。后面进行梯度下降或其它高级优化算法来计算出使得代价函数最小的θ的最优解。

神经网络总结

在训练一个神经网络时要做的第一件事就是选择一个一种网络架构（Architecture）。输入单元的数量等于特征x⁽ⁱ⁾的维度。输出单元的数量等于区分的类别数，如果多于两类，还要把 y 写出向量的形式。至于隐藏单元个数和隐藏层数，一个合理的默认选项是只使用一个隐藏层，如果不止一个隐藏层的话，同样也有一个合理的默认选项，就是每个隐藏层都具有相同个数的单元。

通常情况下，隐藏单元越多越好，当然计算量也越大。隐藏单元数需要和输入单元数匹配，可以与输入单元数相同或是它的几倍。

训练神经网络有六个步骤

第一步，构建神经网络，随机初始化权重（初始化为很小的值接近零的值）。第二步，执行向前传播算法，对任意输入的 x⁽ⁱ⁾ 计算出 h_θ(x⁽ⁱ⁾) ，也就是输出值y的向量。第三步，计算出代价函数J(θ)。第四步，执行反向传播算法，来计算代价函数J(θ)关于参数θ的偏导数。具体来说使用反向传播算法，需要对所有训练样本使用一个循环进行遍历，对每一个训练样本进行迭代，从(x⁽¹⁾,y⁽¹⁾)开始，对第一个样本进行前向传播和反向传播运算，然后在第二次循环中对第二个样本执行前向传播和反向传播运算，以此类推直到最后一个样本。具体来说是把x(i)喂到输入层，然后执行前向传播和反向传播，这样就可以得到神经网络每一层中每一个单元的激活值（激励值）和δ项。在这个循环中计算出Δ(l)，再在循环之外计算出偏导项。

第五步，运用梯度检验来对比这些已经得到的偏导数项。也就是把用反向传播算法得到的偏导数值与用数值方法得到的估计值相比较，比较是否相近，以确保反向传播得到的结果是正确的。然后停用梯度检验。

第六步，将梯度下降或其它高级优化方法和反向传播算法相结合，来最小化关于θ的代价函数J(θ)。神经网络的代价函数是非凸函数，因此梯度下降法理论上可能收敛于局部最小值。尽管不是全局最小值，但也非常不错了，在实际应用中。

下图中红色的高点就是，对于大部分训练样本，输出值h_θ(x⁽ⁱ⁾)远离观测值y⁽ⁱ⁾的情况，在最低点就是对于大部分训练样本，假设函数输出值≈真实值的时候，也就是神经网络对训练集拟合得比较好的情况。梯度下降的原理是从某个随机的初始点开始不断往下降，反向传播算法的目的就是算出梯度下降的方向。梯度下降与反向传播算法相结合试图找到最优参数使得神经网络的输出值与训练集中观测到的y⁽ⁱ⁾实际值尽可能接近。

反向传播算法能够让更复杂的强大的非线性函数模型更好的拟合你的数据。

P57讲的是神经网络的反向传播实现自动驾驶。

# 学习模型的选择

假设在开发一个机器学习系统时，怎么来选择学习道路？这是本节将要解释的内容。

用预测房价的学习例子，假设已经完成了正则化线性回归得到了学习参数，将假设函数放到新的房屋样本进行测试，在预测房价时产生了巨大的误差，那么下一步应该怎么做才能改进这个算法？

第一种方法是使用更多的训练样本。但有时候获得更多的训练样本实际上并没有作用。在后面会解释原因，也将知道怎样避免把过多的时间浪费在收集更多的训练数据上。因为更多的训练样本在有些情况下也是于事无补的。

第二种方法是尝试选用更少的特征，少选一点特征防止过拟合。

第三种方法是用更多的特征，可能目前的特征集还不够。需要去调研更多的数据以扩充特征集，但这会花费大量时间，所以我们希望在完成这些调研工作之前就知道这样做是否有效。

第四种方法是增加多项式特征，如x₁^2,x₂^2,x₁x₂等。

第五种方法是增大或者减少正则化参数 λ 的值。

这五种方法都需要时间来实行，所以不能随便选。有一系列简单的方法可以快速排除掉上面的一半的不太有效的措施（针对具体问题），从而节约大量时间。首先应该评估机器学习算法的性能，然后通过机器学习诊断法来进行测试，通过执行测试能够了解算法在哪里出了问题，通常也能得出要想改进一种算法的效果，什么样的尝试才是有意义的。

评价学习算法

接下来讲怎样评价算法学习得到的假设，基于这些知识，再学习如何防止过拟合和欠拟合的问题。当我们确定学习算法的参数时，我们要选择使得训练误差（代价函数）最小的那些参数。但得到一个很小的训练误差不一定是一件好事，仅仅凭一个很小的训练误差并不能说明这是一个很好的假设，比如过拟合问题，过拟合得到的训练误差就很小，但这种情况下训练出来的学习算法推广到新的训练样本上就不灵了（无法推广）。

那么怎么判断一个假设是否过拟合呢？我们可以画出假设函数的图进行观察，但特征数较大，画出假设函数进行观察就变得很难甚至不可能了。因此需要另一种评价假设函数的方法。那就是取 70% 的训练样本作为训练集（Training Set），剩下 30% 的训练样本作为测试集（Test Set）。如果这些训练样本有某种规律或顺序，那么随机抽取是最好的；如果训练样本已经随机分布了，则取前70%为训练样本后30%为测试样本就行了。如果数据不是随机排列的，那么最好还是打乱顺序。

训练和测试线性回归算法

首先需要对训练集进行学习得到参数θ，具体而言就是基于那70%的训练集来最小化训练误差J(θ)，然后通过那30%的测试集来算出测试误差，具体而言就是求测试集平方误差的平均值。

训练和测试Logistic回归

步骤与训练和测试线性回归算法一样，只是计算测试集误差的公式不同。

除了图中的 J_test(θ) 计算方法，还有一个叫 0/1分类错误（错误分类）的方法来计算测试集的误差。

具体而言就是定义一个 err(h_θ(x),y) 函数，当hθ(x)≥0.5但y=0时或hθ(x)<0.5但y=1时，返回1（这两种情况都代表假设对样本进行了误判）；当假设对样本进行正确的分类时，返回0。再计算出错误分类误差来定义测试误差，也就是把错误分类误差 err(h_θ(x),y) 进行求和并平均到每一个测试样本上。

模型选择

对于确定一个数据集最合适的多项式次数、选择正确的特征构造学习算法或选择学习算法中正则化参数λ，都是模型选择的问题。上面所说的把训练样本分为训练集和测试集，在没有模型选择（选择多项式次数、选择特征、选择正则化参数等）的情况下可以检查过拟合问题，但加上模型选择的步骤，（再只分训练集和测试集的情况下）用测试集计算出的误差比实际的泛化误差会小。

因此我们需要把训练样本按照6：2：2的比例分为Training Set、Validation Set、Test Set。训练集用来算出参数θ，验证集用来模型选择，测试集用来验证算法的泛化能力。

选择多项式次数

假设要选择能最好拟合数据的多项式次数但训练数据只分成了训练集和测试集，那么要用训练集计算出不同次数多项式使得代价函数最小的参数θ，用测试集计算不同多项式次数的最小测试误差以选择模型，那么只能用测试集误差来代表泛化误差，这可能存在很大偏差，比实际的泛化误差小。

因此在模型选择问题中，为了避免上述的误差，就要将训练样本按照6:2:2的比例分为Training Set、Cross Validation Set（or Validation Set）、Test Set。基于这些数据集，来计算训练误差、交叉验证误差和测试误差。

有了训练集、验证集和测试集之后，在多项式次数选择时这样做：首先用训练集计算每个多项式假设的参数θ。然后用验证集来计算每个多项式假设的交叉验证误差，选择验证误差最小的那个多项式假设作为模型。最后用测试集计算这个模型的泛化误差。

诊断偏差与方差

当运行一个学习算法，这个算法的表现不理想时，多半是两种情况，要么是偏差比较大（欠拟合）要么是方差比较大（过拟合）。找到具体的问题是改进算法的有效途径，这对改进实际的学习算法的效果非常重要。下图中左中右分别代表欠拟合（高偏差）、恰好、过拟合（高方差）的情况。

具体来说，沿用训练误差和验证误差的定义——分别是用训练集计算的和用交叉验证集计算的均方误差。画出一个横轴为多项式次数与均方误差的图。如下图所示，训练误差肯定会随着多项式次数的增加而减小（粉色的线）。交叉验证的误差在多项式次数低或高时都可能会偏大（红色的线）。

那么假设运行了一个学习算法，算法的效果不好，那么怎么判断此时的学习算法出现的是高偏差问题还是高方差问题？

从下图中可以看出，高偏差情况下（欠拟合），训练误差和验证误差均较大，且两者的值相似。

高方差情况下（过拟合），训练误差的值很小（代表对训练集的拟合非常好），但验证误差较大（泛化能力较差），这种情况下验证误差远大于训练误差。

正则化与偏差和方差

这里讨论一下正则化算法与方差和偏差的关系，以及正则化是如何影响偏差和方差的。

如下图所示，假设要对图中的高阶多项式进行拟合，为防止过拟合，在代价函数后面加了个正则化项来使参数θ尽可能小。

图中最左边的小图，正则化参数λ取值特别大，那么参数θ的惩罚将会很重，导致参数θ≈0且h(x)≈0，那么这个假设处于高偏差的状态，且对数据集严重欠拟合。

图中最右边的小图，正则化参数λ取值特别小，那么正则化程度很小或几乎没有，最后通常得到高方差过拟合的结果。

那么如何自动选择一个合适的λ呢？如下左图所示，第一个式子为假设，第二个式子为学习算法的目标（带正则化项的情况），第三、四、五分别为训练误差、验证误差和测试误差，这些式子都没有带正则化项。 Jtrain(θ) 等下面三项，都是不使用正则化项时的训练集、验证集和测试集平均误差平方的一半。

如上右图所示，选取一系列想要尝试的λ的值，比如从0（不带正则化项）开始，步长设置为两倍，如图中所示，得到了12个备选模型。然后使用每一个模型，去最小化代价函数得到参数θ。然后用验证集去评价它们得到验证误差。选择验证集误差最小的那个模型作为最终选择。最后用测试集来计算出最终选择模型的测试误差，以估计它对新样本的泛化能力。这就是模型选择在选择正则化参数λ时的应用。

下图展示的是当改变正则化参数λ时，验证误差和训练误差将怎样变化。当λ很小的时，就相当于没有正则化项，那么很大可能处于高方差过拟合状态；当λ很大时，把参数θ都惩罚成0了，就很可能处于高偏差欠拟合状态。训练误差 Jtrain(θ) 随λ变化的图像由蓝色曲线所示。验证误差 Jcv(θ) 随λ变化的图像由粉色曲线所示，总会有个中间值λ使得训练误差和验证误差都很小。

对于真实的数据，得到的曲线可能更凌乱点，但通过观察总有这个趋势，可以手动或者自动得出这个刚刚好的点（所对应的λ的值）。

学习曲线

如果想要检查算法运行是否正常，或改进它的表现，那么学习曲线就是一个非常有用的工具。

为画出学习曲线，通常要在同一个坐标系上画出 J_train(θ) 和 J_cv(θ) 随训练样本大小变化的曲线。

如下图所示，用一个二次函数来拟合m个训练样本（m从小到大变化）。当m=1时，用二次函数拟合的效果会非常好（只有一个样本，训练误差为0，曲线必过该点），当m越来越大，用二次函数来拟合m个训练样本的效果会越来越一般（训练误差会越来越大），这是 J_train(θ) 的图像。那么 J_cv(θ) 的图像如粉色的曲线所示，m越来越大，验证误差会越来越小。这就是一个学习曲线图。

高偏差情况

在高偏差情况， Jcv(θ) 会随着m变大将很快变为水平而不再变化（在达到一定样本数量之后），这也是为什么高偏差情况下增加样本量对改进算法是没用的。 Jtrain(θ) 在高偏差情况下会随着m增大而逐渐增大，最后接近 Jcv(θ) ，且它们二者都会较大。

高方差情况

随着m增大，高次多项式会越来越难将训练样本拟合得很好，但训练误差还是较小（因为这是过拟合的情况）。高方差情况下，验证误差将会很大，随着m增加，验证误差和训练误差之间会有一个较大的距离。但获得更多的训练样本，两个曲线很可能会更靠近。也就是说，在高方差情况下，使用更多的训练集对改进算法是有帮助的。

Debug a learning algorithm

修正高偏差问题：1）增加额外的特征。2）增加多项式（x^2, x1x2, etc）。3）减小正则化参数λ。

修正高方差问题：1）增加样本量。2）减少特征数量。3）增大正则化参数λ。

神经网络过拟合

在进行神经网络拟合的时候，可以选择相对简单的、隐藏层数和隐藏单元较少的神经网络，比如下图中左侧神经网络所示。像这种简单的神经网络，参数较少，容易出现欠拟合问题。唯一的优点是计算量较小。

另一种情况是选择较大型的神经网络结构，神经网络架构中隐藏层数或隐藏单元比较多，这种复杂的神经网络参数较多，容易出现过拟合。过拟合是大型神经网络的主要问题，但实际上复杂神经网络的性能往往较好，如果发生过拟合问题，可以使用正则化的方法来修正，这样的效果也往往比小型神经网络好。在这种复杂神经网络中，默认情况是选择一个隐藏层，如果想要选择一个最合适的隐藏层数，可以将数据分为训练集、验证集和测试集，用训练集计算出不同隐藏层数神经网络的参数θ，用验证集计算出交叉验证误差，以选择最合适的隐藏层数。

# 机器学习系统设计

本节以邮件垃圾分类为例子，讲述机器学习系统中可能遇到的问题以及优先处理事项。

在构建一个垃圾邮件分类器时，首先应该思考如何表示邮件的特征向量X。比如构建一个包含100个单词的列表来区分垃圾邮件或非垃圾邮件。举个例子，一个邮件包含deal它更可能是垃圾邮件，包含discount更可能是垃圾邮件，包含真名更可能是非垃圾邮件等。

具体做法是，构建一个100个单词的列表，然后挨个检查这些单词是否在邮件中出现了。定义一个特征向量X，如果邮件中包含了那个单词，则写1，没出现则填0。那么这个特征向量是100维的。当然实际上，是选择最常出现的10000到50000个单词来作为特征向量，而不是手动选择100个。

然后思考如何在最短的时间内让垃圾邮件分类器具有高精度和低错误率。第一种做法是收集大量数据。第二种做法是用更复杂的特征。第三种做法是开发更精密的算法来检测错误拼写。

误差分析

有很多思想和方法能够改进学习算法，误差分析能够帮助你在众多的方法种做出选择。

通常来说，实现一个机器学习的应用，可以先通过一个简单的算法来实现它，而不是构建一个有复杂特征的系统。即使这个速成的算法不完美，但可以通过交叉验证来测试数据。然后绘制出学习曲线，来看是否存在高偏差或高方差问题，以选择对应的解决方案。下一步进行误差分析，关注一下交叉验证集的情况，看一看被算法错误分类的样本有没有什么共同的特征或规律。

误差分析具体来说，假如做一个垃圾邮件分类器，交叉验证集有500个样本，垃圾邮件分类器错误分类了100份邮件，错误率很高。那么接下来要看这100份邮件的类型，然后思考怎么样改进特诊来更好的分类。比如故意拼错单词的有5份，来自不正常的服务器的有16份，奇怪标点符号的有32份。奇怪标点符号的邮件占比很大，说明值得花时间构造复杂的特征针对这一类错误。

数值评估

另一个改进算法的技巧是保证自己对学习算法有一种数值估计的方法，也就是说当改进算法的时候，算法能够返回一个数值评价指标来估计算法执行的效果，将会有很大的帮助。因为改进算法的时候可能会让算法效果更好，也可能更差，需要用这个数值指标（通过交叉验证集）来评价。错误分析只能找到改进算法的思路，但是否真的有改进效果还得看数值评估。

每选择一个新的改进方法，都去用验证集评估一下效果（误差率），做一个对比。再选取是否采用这个方法。

查准率（Precision）和召回率（Recall）

上一部分讲到数值评估的误差率，误差率可能对算法的改进有用，但也可能没用。比如在偏斜类问题下（正样本和负样本之间的严重不平衡）。比如在一个二值分类中，10000份样本只有一个50个样本被分为一类（假设为1），学习算法在验证集上得到的错误率为1%，把学习算法设置为y=0，得到的错误率会更低。这种例子可能发生在正例和负例的比例极端的情况下。

因此，在偏斜类问题下，错误率并不能很好的衡量算法。但查准率和召回率，在偏斜类问题下就能更好地衡量学习算法。

在一个二元分类的问题下，画一个2X2的实际分类与预测分类的表格。当预测分类为1且实际分类也为1时，称之为真阳性；当预测分类为1但实际分类为0时，称之为假阳性；当预测分类为0且实际分类也为0时，称之为真阴性；当预测分类为0但真实分类为1时，称之为[/loliCode]假阴性[/loliCode]。

查准率=真阳性/所有预测阳性，反应的是，对于那些“预测为1的人”，有多大概率真的为1。也可以写成查准率=真阳性/(真阳性+假阳性) 。高查准率说明，假阳性少，分类准确度高。

召回率=真阳性/所有实际阳性，反映的是，对于那些“实际上为1的人”，有多大的比例学习算法能够正确预测。也可以写成召回率=真阳性/(真阳性+假阴性) 。高召回率说明，假阴性少，分类准确度高。

通过查准率和召回率，可以更清楚的知道分类算法到底好不好。比如在偏斜类问题下，设y=0的话，召回率会等于0。一般来说，会把出现得比较少的类别设置为y=1。高查准率和高召回率意味着算法效果比较好，这种评价指标在偏斜类问题下比误差分类好。

保证查准率和召回率的相对平衡

上面讲了查准率和召回率是评估算法的一个有效的指标，但在不同应用中，为 h_θ(x) 设置不同阈值会得到不同的查准率和召回率。

假设要在非常确信的情况下才预测某个情况会发送，那就要将阈值调高，比如当 h_θ(x)≥0.7 时才预测 y=1 ，也就是说当 y=1 的概率大于等于0.7的时候我们才说y=1。这样会使得算法有较高的查准率和较低的召回率。

假设要避免假阴性，那就要把阈值调低，比如当 h_θ(x)≥0.3 时就预测 y=1 （为了避免任何漏网之鱼），那么这会使得算法有较低的查准率和较高的召回率。

针对不同的应用会设置不同的阈值，在不同的阈值下查准率和召回率会随之改变。

也就是说，不同的应用有不同的阈值，不同的阈值又会得到不同的查准率和召回率，那么怎么比较哪个阈值情况下算法的效果更好？在这里提出了评估度量值 F₁ Score 。

F Score = 2*PR / (P + R) ，当查准率或召回率有一个等于0时，F值就会等于0。对于不同的阈值，F值越高，算法的效果越好。在对阈值的选择上，可以用训练集来计算出不同阈值下的参数，然后用验证集来检验它们的F值。然后选一个最高的，作为最好的阈值。

机器学习数据

上面讲了数值评估指标，接下来讲讲数据。之前讲过在算法需要改进时不要盲目地去增加更多数据，因为增加训练样本只在一些情况下起作用。但在某些条件下，得到大量数据在某种算法下训练可以得到一个具有良好性能的学习算法。

比如01年Banko和Brill使用四个算法做同样的监督分类问题，发现较为“劣质”的算法在大量数据的情况下，算法的效果优于“优质”算法。

之前也说过，这是有条件的。第一，特征需要有大量能准确预测y的信息（一个人类专家能够通过这些特征准确得预测y吗）。第二，算法有大量参数（如有很多隐藏的神经单元），有大量参数容易过拟合（高偏差），但有非常庞大的数据集就会使得算法不太可能发生过拟合。这样训练误差会与测试误差相近，且都比较小。如果能做到这两者，增加数据集可以得到一个较好的学习算法。

# 支持向量机

SVM在工业界和学术界用得都比较多，可以从Logistic回归做一点改动来得到一个SVM。

设 z=θ^Tx ，结合Sigmoid函数的图像，可以知道，如果y=1，那么就要h_θ(x)接近1，意味着z就要远大于0。如果y=0，想要正确分类就要h_θ(x)接近0，意味着z就要远小于0。

对于每一个训练样本对总的代价函数做的贡献，把它设为-(ylogh_θ(x)+(1-y)log(1-h_θ(x)))，这是每个样本对总代价的贡献。把hθ(x)替换成 1/(1+e^-z)，这样无论y为1或0，都会将其中一项消掉，剩下另外一项，画出图像。

接下来，对代价函数进行修改（可以从图中看出），当y=1时，z≥1的部分，y输出0，z<1的部分y是一条和Sigmoid函数相似的直线，称为 cost₁(z) ；当y=0时，z≤-1的部分，y输出0，z>-1的部分y是一条和Sigmoid函数相似的直线，称为 cost₀(z) 。 cost() 的下标只是指在代价函数中y=1或0。这样的改造使得SVM的计算比Logistic回归简单。

接下来构建SVM，写出SVM的代价函数。写出Logistic回归的代价函数，再把上面的改动替换到公式里。再把1/m去掉（SVM的惯例）。在Logistic回归中，代价函数看作是 A+λB ，设定不同的正则化参数λ，来权衡多大程度上去适应训练集，也就是说这里的λ控制了这个式子不同部分的相对权重。但在SVM里，不再用λ控制权重，而是写成 CA+B 。

SVM并不像Logistic回归输出概率，而是直接预测y=0或1。

大间距分类器

有时人们把SVM叫做大间距分类器。如下图所示是SVM的代价函数，图中左侧的 cost₁(z) 用于正样本，右侧的 cost₀(z) 用于负样本。

安全因子

在y=1时，本来我们可以让 θ^Tx≥0 时让 cost₁(z)=0 的，也就是说让图中左侧图像的线让左移一个单位。但SVM对此有更高的要求，不是恰好能正确分类就行了， θ^Tx 不是略大于0就行，而是要≥1。在y=0时， θ^Tx 也不是略小于0就行，而是要≤-1。这就像构建了一个安全因子（安全间距）。

SVM决策边界

当 CA+B 中的C非常大时，比如设置个10万，那么代价函数中的 A 将非常想等于0，才能使代价函数尽量小。优化问题可以看作是，如何通过选择参数θ，来使得 A 等于0。优化问题可以改写成红框所示的部分。

SVM决策边界：线性可分的例子

在线性可分的例子中使用SVM来分类正负样本，SVM通常会得到一个更稳健的决策边界（图中黑色的线所示），它的间距会较大（相比于图中粉色和绿色的决策边界），这使得SVM具有鲁棒性。在分离数据时会尽量用大的间距去分离，因此SVM也叫大间距分类器。这也是上图中优化问题得到的结果。

大间距分类器展示异常值

上图中的大间距分类器是在C很大的情况下得出的，在C很大时，SVM会比较敏感，可能因为一个异常值而改变决策边界（如图中从黑色变为粉色）。但如果C没有那么大，在复杂情况下，SVM依旧可以得到黑色的决策边界。

当C不是非常大时，SVM可以忽略异常点，甚至当数据是线性不可分的时候，SVM也能得到比较好的结果。

SVM的数学原理

下图中u和v是两向量，那么u·v=(u^T)*v，也就是两向量的内积（点积）。 ||u|| 称为向量u的范数（norm）或长度，等于(u₁²+u₂²)^1/2。

粉色的向量v投影在蓝色的向量u上的长度设为p，那么向量u和向量v的内积u·v=(u^T)*v=p·||u||。这里的p和||u||都是实数，且带有符号。

做一个简化：假设只有两个特征，且设截距θ₀为0。将 CA+B 的B项拎出来，它就变成了1/2*(θ₁²+θ₂²)，再转成1/2*((θ₁²+θ₂²)^1/2)²，根据上面的范数的定义，B就变成了1/2||θ||²。那么SVM就是在最小化参数向量θ的范数（长度）的平方。

当y⁽ⁱ⁾=1时，我们希望θ^Tx⁽ⁱ⁾≥1，根据上面讲的内积，θ^Tx⁽ⁱ⁾实际上可以看作是，第i个样本x(i)在参数向量上的长度与参数向量的范数的积。也就是说，θ^Tx⁽ⁱ⁾=p⁽ⁱ⁾·||θ||。

还是延续最开始的简化，设截距为0，决策边界过坐标原点。参数向量θ与决策边界垂直，也过坐标原点。下左图中绿色的决策边界间距很小，下面讲SVM为什么不选它。如果间距很小，把参数向量（蓝色）画出来之后，发现 p⁽ⁱ⁾ 都很小，为了实现优化目标，||θ||就会很大，才能使得两个数的乘积足够大或足够小。但优化目标函数要做的是使得 ||θ|| 足够小，那么这个小间距决策边界就不是个好方向。

下右图比左图的决策边界就好很多，p⁽ⁱ⁾变大了，||θ||就可以变小了。SVM就会倾向于选择右侧的决策边界，而不是左边的。SVM试图最大化这些p⁽ⁱ⁾，这也是它被称作大间距分类器的原因。

使用SVM构造复杂的非线性分类器（思想）

上面简单介绍了SVM的数学原理以及为什么SVM被称为大间距分类器。接下来讲SVM是如何构造复杂的非线性分类器的。

SVM构造复杂非线性分类器需要两个东西——核（Kernel）、标记（landmark），来构造新的特征，从而训练复杂的非线性边界。

假如要构造图中蓝色曲线所示的决策边界，就可以写出右侧的复杂多项式，设这f₁=x₁，f₂=x₂，f₃=x₁x₂…这些 f 就是新特征。问题是，有很多不同的特征可以选择，但并不知道这些特征是不是我们想要的。

这里介绍构造新特征f₁f₂f₃的方法。手动选取一些点 l⁽ⁱ⁾ ，称这些点为标记，定义 f 为训练样本与标记的相似度的度量，设f_i=similarity(x,l⁽ⁱ⁾)= exp(-||x-l(i)||²/2σ²) 。分子部分是训练样本x与标记的欧氏距离的平方。这里的相似度的度量，用术语来说就是核函数（Kernel Function），这里用的是高斯核函数， k(x,l⁽ⁱ⁾) 。

将注意力转到第一个标记 l⁽¹⁾ ，f₁=similarity(x,l⁽¹⁾)=k(x,l⁽¹⁾)=exp(-||x-l⁽¹⁾||²/2σ²)。

根据公式可得，如果训练样本离标记1很近，那么 f₁ ≈1，如果x离标记1很远，那么 f₁ ≈0。如上图所示，我们给了三个标记，因此x与这三个标记构造了三个新特征f₁f₂f₃。

假设第一个标记在(3,5)，根据核函数公式画一个图像。当 σ²=1 时如下左图所示， σ²=0.5 时如下中图所示， σ²=3 时如下右图所示。当x刚好等于(3,5)时 f=1 ，如果x朝四周移动那么f值会越接近0。

从图中可以看出， σ² 越大，x朝四周移动f降到0的速度越慢。

上面是f₁f₂f₃的定义，接下来看如何使用它们来构造一个复杂非线性分类器。假设在下图右侧的学习算法中，已经得到了参数θ（θ₀=-0.5，θ₁=1，θ₂=1，θ₃=0）。如果一个训练样本刚好在粉色的点，预测函数为(-0.5+1+0+0+0)=0.5≥0，Y输出1。如果另一个训练样本在蓝色的点，预测函数为(-0.5+0+0+0+0)=-0.5≤0，Y输出0。

通过大量的这样的点来进行相应处理，会得到一个红色曲线所示的决策边界。

如何构造SVM（实践）

上一小节讲的是SVM构造复杂非线性分类器的思想，介绍了核函数和标记。这里介绍标记是如何选取的以及偏差方差分析，上一节只是随便选了3个标记，在真正复杂的研究中肯定不止三个标记。

在实际应用中，将每一个样本，直接用作标记。加入有m个训练样本，那么就会有l⁽¹⁾l⁽²⁾…l^(m)个标记，且每个标记与样本点的位置对应。这样以来，新构造的特征就是在度量每一个样本与样本集中其它样本的距离。

这个过程具体来说就是，给定m个训练样本，那么就会有m个与之对应的标记，然后就会有m+1个新特征(f₀f₁..f_m)，f₀=1为截距项。针对样本(x⁽ⁱ⁾, y⁽ⁱ⁾)来说，新的特征就为[f₁⁽¹⁾…f_m⁽ⁱ⁾]，且之中有一项f_i⁽ⁱ⁾刚好度量的是它与它自身的相似度，等于1。

那么给定一个样本，计算特征 f∈ℝ^m+1 ，如果 θ^Tf≥0 则预测y=1。那么θ也是m+1维的。那么特征也构造了下一步就是计算参数θ了，肯定是通过最小化代价函数的方式计算参数θ。

之前就提过SVM的代价函数，但是这里要用新的带有核函数的特征f⁽ⁱ⁾替换里面的x⁽ⁱ⁾，后面的正则化项要从1到m求和（n=m），因为忽略了θ₀。同时，正则化项里的θ²可以写成θ^Tθ，但大多数支持向量机实现的时候都写成了θ^TMθ，这个矩阵M取决于采用的核函数。 θ^TMθ 相似于||θ||²但又不是它，此举使得SVM计算效率更高。

CA+B 中的C

C与Logistic回归中的(1/λ)的作用类似，较大的C意味着较小的λ，代表正则化几乎没有，会造成低偏差高方差，倾向于过拟合。相反，较小的C意味着较大的λ，会导致高偏差低方差，倾向于欠拟合。

σ²

除了C，高斯核函数的σ²也是我们要选择的参数。较大的σ²意味着f_i（相似度函数）会变化得非常平缓，意味着高偏差和低方差。较小的σ2意味着f_i会变化得非常剧烈，意味着低偏差和高方差。

运行SVM时需要注意的事项

尽管不需要自己写SVM，但需要注意 C 的大小以及核函数的选择。至于后者可以有很多选择，如 No Kernel ，也称作线性核函数； Gaussian Kernel ，也称作高斯核函数； String Kernel ，也称作字符串核函数；

No Kernel ：如果有大量特征，训练样本量很小。且只想拟合一个线性边界而不是复杂的非线性边界（因为没有足够的数据，容易过拟合）。那么使用不带内核的SVM是很合理的。

Gaussian Kernel ：使用该核函数还需要选择一个 σ² ，该参数的选择是偏差和方差权衡的结果。如果有较小的特征数，样本量较大时，使用带有高斯核函数的SVM拟合一个复杂的非线性决策边界是一个不错的选择。

如果选择了 Gaussian Kernel ，在实现它的时候可能得自己去定义一下这个函数（不过可能在22年不需要了吧）。更重要的一点是，在使用高斯核函数之前一定要进行特征缩放。因为在||x-l||2的计算中，如果其中某一项特别大，那么间距主要是由那一项贡献，另一项会被忽略。

当然不是所有的核函数都有效。在使用核函数之前，这些核函数需要满足一个叫 Mercer’s theorem 的条件。这个定理所作的就是确保所有SVM包都能用大类的优化方法从而迅速求得所有θ。除了线性核函数和高斯核函数，还有多项式核函数等也满足该定理。

多项式核函数：k(x,l)=(X^Tl)²，或(X^Tl)³，或(X^Tl+1)³，或(X^Tl+5)⁴。那么一般形式就是(X^Tl+constant)^degree。与高斯核函数相比用得少，且效果也一般。通常是在x和l都是严格的非负数时（保证内积永远不是负数）才会用。人们通常用得不多。

SVM的多分类问题

很多SVM包都内置了多分类函数，调就完事了。除此之外，可以和之前Logistic回归多分类一样，使用one-vs-all方法，训练K个SVM，每个SVM将每个类别和不同类别区分开然后获得K个θ。然后用最大的 (θ⁽ⁱ⁾)^Tx 来预测类别i。

Logistic regression vs. SVM

接下来讨论一下什么时候选Logistic回归什么时候选SVM或其它方法。

当特征数比训练样本量多时，如特征数有1万个但样本量只有10~1000个，这种情况因为没有足够的数据来拟合复杂的非线性决策边界，所以选择Logistic回归或者带线性核函数的SVM。

当特征数较小，训练样本量适中，如特征数有1~1000个，相对的有10~10000个训练样本。使用带高斯核函数的SVM会比较好。

当特征数较小，训练样本量很大时，如特征数有1~1000个，相对的有5万10万多个训练样本。这种情况下可以尝试增加一些特征，然后使用Logistic回归或带线性核函数的SVM。

Logistic回归和带线性核函数的SVM 是相似的算法，它们两个算法都做相似的事得到相似的结果。

但针对上面的不同情况， Neural Network 都会非常有效，但有一个缺点就是运行得慢。以及，局部最优是 Neural Network 一个不大不小的问题，但 SVM 具有的优化问题是一种凸优化问题，所以不需要担心局部最优的问题。

最后，算法不是最最最重要的，更重要的是有多少数据，误差分析的熟练程度，分析排除学习算法问题的能力，设计新特征的能力。

# 无监督学习

在此节之上分类算法的部分为监督学习。监督学习（如下左图所示）会给一个带标签的训练集，目标是找到一个能区分正负样本的决策边界。而在非监督学习中，数据不带有任何标签，学习算法讲找到隐含在数据中的结构。图中（下右图）将训练样本分为两簇的算法被称作聚类算法。

K-Means

K-Means 算法能将一系列没有标签的数据分为有紧密关系的子集或簇。

K-Means算法步骤：①随机生成K个聚类中心（就是K个点，假如想分为K簇）。②簇分类：遍历每一个样本，将它们分给最近的聚类中心。③移动聚类中心：将这K个点分别移动到这K类样本的均值点。④重复第二步和第三步直到算法收敛。

具体而言， K-Means 算法要输入两个东西，一个是参数K（分K类），另一个是一系列无标签的数据集。同时在 K-Means 算法中，我们约定x⁽ⁱ⁾是一个n维实数向量（不要x₀=1）。该算法也是一个迭代算法：初始化聚类中心，并重复簇分类和移动聚类中心直到算法收敛。

假如存在一个没有点的聚类中心，最直接的做法是移除那个聚类中心，最后得到K-1个簇。如果非要想得到K个簇，那么可以重新初始化。

K-Means 算法还可以用来解决分离不佳的簇的问题，如下图右侧的部分所示。这可以被用作市场分类等问题。

K-Means的优化目标

设 c⁽ⁱ⁾ 为样本x⁽ⁱ⁾所属的簇的索引（如123…K）。设 μ_k 为第k类聚类中心的位置。设 μ_c(i) 为样本x⁽ⁱ⁾所属簇的聚类中心位置。那么 K-Means 算法的代价函数如下图所示。 K-Means 算法的代价函数也称作失真代价函数（Distortion Cost Function），该失真代价函数由(c⁽¹⁾,…c^(m),μ₁,…μ_k)决定。

具体而言，第一步，(μ₁,…μ_k)不变，改变(c⁽¹⁾,…c^(m))以使得失真代价函数最小。第二步，(c⁽¹⁾,…c^(m))不变，改变(μ₁,…μ_k)使得失真代价函数最小。 K-Means 算法就是把(c⁽¹⁾,…c^(m),μ₁,…μ_k)分成两半，然后重复那两步。

随机初始化

随机初始化的目的是避免局部最优。有一种随机初始化的方法较好，就是随机选K个样本点作为聚类中心（μ₁,…μ_k）。由于不同的聚类中心初始化， K-Means 最终可能会收敛到不同的结果。

具体而言， K-Means 算法可能收敛到局部最优。如图中左下角和右下角的结果就是畸变函数收敛到了局部最优。如果担心算法结果落到局部最优，可以尝试多次随机初始化。

写一个循环，将次数设置为50~1000，计算每一次算法的代价，然后挑最小代价对应的c⁽¹⁾,…c^(m)及μ₁,…μ_k。

如果聚类数在2~10之间，那么多次随机初始化通常能够找到较好的局部最优解。如果K比10大很多，如成百上千，那么多次随机初始化不会有太大改善，更有可能第一次随机初始化就会给出一个相当好的结果。

聚类数的选择

应根据后续目的进行选择，看哪个聚类数量更适合后面的目的，如市场分割、T恤尺寸的选择。如在T恤尺寸选择这件事上，可以选3种尺寸或5种，但实际上选择尺寸的种数是为了更好地卖衣服，如果市场更喜爱5种尺寸，那就选5种。

当然还有一种方法，但是用的不多，就是计算每种选择对应的畸变函数，然后连成线，看是否存在拐点。如下图左侧小图当K=3时有明显拐点，但右图就没有。这种方法没有上面的方法好，但是可以试试。

# 降维

降维（Dimensionality Reduction）可以达到数据压缩的目的。数据压缩不仅节省了存储空间，还加速了学习算法。降维就是将高维降低到低维，如将两个特征降低到一个特征。

如下图左图所示，通过投影绿色线上所有的原始样本，来近似原始的数据集。那么之前通过两个位置才能指定的样本点，现在只需要一个位置就能指定了。这是对原始数据集的一种近似。

下图右图所示，是把数据从三维降到二维。那么每个样本就可以用一个二维向量来表示了。

降维的第一个目的是数据压缩，第二个目的是可视化数据。如，有50个特征，把它降到2个，就可以将它们可视化出来。把50个特征降到2个，这2个特征的物理意义通常不是所期望的那样。这样的可视化能够帮助你最便捷得捕捉到样本在两个维度间的变化。

主成分分析（PCA，最强大的无监督算法之一）

对于降维问题，用的最多的是主成分分析法。下图是将二维数据降到一维，每个样本点到投影点的距离都很小。那么PCA实际做的是找到一个低维平面，然后将数据投影在上面，使这些蓝色小线段（投影误差）的长度平方最小。

在运用PCA之前，常规的做法是对每一个特征进行均值归一化和特征缩放（选做，如果特征呈现不同范围的值），使得特征的均值为0且其数值在可比较的范围之内。

正式地来说，PCA做的就是试着找一个向量μ⁽ⁱ⁾，使得投影误差的平方最小，这是下图左图的情况。

更普遍的是，有N维数据，想将其降到K维，那么我们不再想只找一个向量，而是找K个向量来对数据进行投影，来最小化投影误差的平方。也就是说找μ⁽¹⁾μ⁽²⁾…μ^(k)共K个向量，将数据投影到这K个向量展开的线性子空间上

下图右图是3D降到2D的情况，找了两个向量μ⁽¹⁾和μ⁽²⁾，这两个向量构建了一个二维平面，然后将数据投影在上面。

PCA不是线性回归，尽管看起来比较相似。下图左图是线性回归，用所有的x来预测一个y，然而在PCA中，没有区别对待这些特征，也就是说没有所谓的y。

使用PCA进行降维

在使用PCA之前，需要对每一个特征进行均值归一化，取决于数据可能还要进行特征缩放。

如下是求解过程，假如把n维的数据降到k维，首先计算的是协方差Σ：

使用 [U, S, V]=svd(Sigma) 可以计算出协方差矩阵Σ的特征向量。 svd() 代表奇异值分解。且协方差矩阵Σ是一个 n×n 矩阵。U也是一个 n×n 的矩阵。如果想把数据从n维减少到k维，我们需要做的是提取前k个向量（u⁽¹⁾…u^(k)），这给了K个方向即我们想投影数据的方向。

剩下的过程就是，通过 svd() 的数值线性过程获得矩阵U，然后获取前k列的向量。将这前k列组成的矩阵单独提出来，命名为U_reduce，代表被降维的矩阵U。那么向量z就是 z=U_reduce^Tx ，这里的x是数据样本。

最后，如果数据集写成一个矩阵X，则协方差矩阵Σ就可以很好的向量化实现，如下图所示。用 svd() 方法得到的矩阵U是要降维的矩阵，获得该矩阵的前K列。然后将n维的特征向量x降维到k维的向量z。

最后，类似于K-Means算法，如果用PCA，则x₀不能为1。

压缩重现

前面几节一直将PCA作为压缩算法来讨论，这里讲如何让压缩后的数据回到高维数据的近似值。

通过 X_approx=U_reduce·z 得到高维数据的近似值。

主成分数量的选择

在选择主成分数量之前，先计算出均方投影误差和数据的方差，选取最小的值，使得前者与后者的比小于等于0.05（学术界0.05，也可以0.01），使得均方投影误占数据方差的比例小于0.05。也就是说，投影误差尽可能小，投影值尽量近似真实值了，95%的数据的变化被保留了。

具体算法是，从K=1开始进行遍历，直到遍历到某个数值使得上面的比值小于0.05，就取这个K。如下图左侧所示。

但还有更简单的方法，如 svd() 函数，返回的 U, S, V 中的矩阵S，是一个对角矩阵。该矩阵使得上图的计算简便很多。具体看图。

PCA加速监督学习算法

假如有一个监督学习问题，这个问题有输入x和标签y，像这样(x⁽¹⁾,y⁽¹⁾),(x⁽²⁾,y⁽²⁾),…,(x^(m),y^(m))。x⁽ⁱ⁾是有非常高的维度，假设有10000维的特征向量（在CV中，一个100×100的图片就有这个维度了），那么学习算法会运行得非常慢。

那么PCA减少数据维度的功能就能帮助此类算法提升速度。面对这种问题，首先检查被标记的训练集并只抽取输入特征x，把标签y临时放一边。这样就得到了一个无标签的训练集，然后对这个无标签的训练集使用PCA，把10000维的特征降低到1000维，得到一个新的低维的训练集。将低维的训练集输入学习算法，学习一个假设函数h_θ(z)，而不是h_θ(x)。

PCA所做的就是，定义一个从x到z的映射，这个从x到z的映射只能通过训练集上运行PCA来定义。U_reduce就是PCA学习得到的参数。需要注意的是，PCA仅能在训练集上运行。在训练集运行后得到参数后，才能运用在验证集和测试集。

上面讲的是将数据维度从10000降低到1000的例子，实际上这是比较可能的，尤其是在分类算法中，这样做几乎不影响算法的性能。

PCA运用的注意事项

上述部分讲了PCA能够进行数据压缩和可视化。

数据压缩能够减少存储数据所需要的内存或硬盘，还能够加速学习算法。在这些应用中，会选择主成分数量K，因此要计算方差保留的百分比（通常保留99%的方差）。

对于可视化应用，由于我们只能可视化二维图和三维图，所以会选择K等于2或3。

上面回顾了一下PCA的应用。下面讲一下PCA的误用，不要这样使用。第一是用PCA来防止过拟合。第二是滥用PCA。

不要用PCA来防止过拟合，这不是PCA的正确使用方式。虽然用PCA把高维数据降到了低维数据，确实更不容易发生过拟合，但这很糟糕，完全不如正则化来防止过拟合。

理由如下，首先PCA在运用时没有考虑到 y ，PCA减少数据的信息或维度且不关心y值是什么，它丢掉的信息很可能是非常有价值的信息。但正则化项是知道y值的，所以不会丢失有用信息。

不要在不应该使用PCA的情况下使用PCA。PCA是为了数据压缩、加速算法和可视化。如果不使用PCA也能实现这些目的，那就不要用PCA了，毕竟PCA还是要丢掉一部分信息的。

如果用原始数据实在是做不下去（算法太慢、存储不够），再去用PCA。

# 异常检测

异常检测是机器学习的常见应用，主要运用在非监督学习问题，但和监督学习问题很相似。

异常检测，就是通过一些特征，来检测异常问题。比如生产飞机引擎时，通过引擎运行时产生的热量（x₁）和引擎的振动（x₂）等特征，然后把非异常的数据成图（这里只展示了两个特征，都是没有标签的特征，是非监督学习），然后把待检测的数据再放上去检测。下面讲更正式的讲定义。

异常检测定义

假设有m个正常数据，我们需要一个算法来告诉我们一个新的样本数据x_test是否异常（毕竟用眼睛看图说话太不定量了）。那么需要给无标签的训练集建模。即 p(x) ，也就是说对X（特征变量）的分布概率建模。如果 P(xtest)<ε ，那么将标记这个测试样本为异常样本，如果 P(xtest)≥ε ，那么标记这个测试样本是正常的。

将正常的训练集成图，可以大概看出，可能在数据集中的地方，中心处，正常的概率相当大，离中心区越远，正常的概率越小。这是一个密度估计。

异常检测的应用

Fraud Detection

假设系统的用户在从事不同活动，那么构建一些特征，建立一个模型来表示用户表现出各种行为的可能性（用户行为对应的特征向量出现的概率）。

构建一些特征向量，如x1是用户登陆的频率，x2是访问某页面的次数，x3是发帖次数等等，然后根据这些特征和数据，建立一个模型 p(x) 。然后用这个模型来检测出哪些用户很奇怪。

工业领域

如上文提到的飞机引擎生产的例子，找到异常的引擎。

数据中心的计算机监控

构建一些特征，来找到计算机集群里异常的计算机。

高斯分布

高斯分布也称正态分布，一般写作这种形式 x~N(μ, σ²) ，μ是特征x的均值，控制钟形曲线的中心位置；σ是特征x的标准差，控制钟形曲线的宽度。

下图这个钟形曲线决定了x取不同值时的概率，公式写作 p(x;μ, σ²) ，也是高斯分布概率密度函数。

参数估计

假设样本x⁽ⁱ⁾服从高斯分布，现在有一些样本，实际上是可以估计 μ和σ的。下图中写了公式，实际上这是对参数μ和σ的极大似然估计。

在统计学中，σ²的计算公式可能是 m-1 而不是 m ，但在ML中大家喜欢用后者。实际上只要数据集够大，它们的区别就几乎没有了。

异常检测的算法

这一节将使用高斯分布来构建异常检测的算法。假设共有m个样本的无标签训练集，每个样本有n个特征。用这样的数据集建立一个模型p(x)，试图解决哪些特征量出现的概率高，哪些比较低。

假设每一个特征都服从高斯分布，那么x₁的均值和标准差分别是μ₁和σ₁，x₂的均值和标准差分别是μ₂和σ₂…。那么这个模型可以写成：

在统计学中每个特征应满足独立性假设，但在ML中不满足独立性假设算法也能跑，效果也还好。

这个分布项 p(x) 的估计问题也称作密度估计问题。

算法如下：①选择特征，通过一些特征来指出异常的样本。一般来说还是选择能够描述数据的一般特性的特征。②拟合出参数μ和σ，用m个无标记的样本来拟合。③给出新案例，如果计算出的p小于某个阈值，则判断为异常值。

为什么是小于这个阈值ε就判定为异常呢？在统计学的假设检验中，零假设通常是不想要的假设，备择假设才是想得到的假设。这个P值是在现有样本下，得到零假设所假设的情况的概率。在异常检验中，异常才是我们想要的结果，正常的样本不是我们想要的结果。所以零假设是新样本是正常值，备择假设是新样本是异常。

举个例子，如下图所示，可以从笛卡尔坐标系的横轴纵轴分别画两条钟形曲线，当然特征数多了就没办法可视化了，这只是思想。右图分别是x1和x2的钟形曲线，合在一块就是下面的曲面图。曲面图的z值就是p(x)值（probability）。将新样本的z值与ε相对比，来确定是否是异常样本。

开发异常检测应用的全过程

之前已经讲过实数评估的重要性，这里讲另一种评估异常检测算法的方法。异常检测被看作一种非监督学习问题，因为用的是无标签的数据，但如果有一些带有标签的数据来指明哪些是异常样本、正常样本，这就是能评估异常检测算法的标准方法。

这个评估方法需要有标签的样本来驱动，把数据以 6:2:2 的比例分为训练集、验证集和测试集。训练集里几乎全是正常样本，验证集和训练集把剩余的正常样本和异常样本对半分，但不能重复利用任何一个样本。

得到训练集、验证集和测试集之后，用高斯函数来拟合m个无标签的训练样本，虽然说是无标签，但放的都是正常样本。然后在验证集和测试集上，对新样本进行预测。

由于正常样本比异常样本多得多，因此这是一个偏斜类问题。在这类问题的学习算法评估中需要用到查准率、召回率和F Score（主要是通过F Score来判断算法的好坏）。

最后是 ε 选择的问题，该值是判断异常样本的阈值，可以用验证集来选择该值的大小。也就是说尝试不同的值，使得 F Score 最大。

实际上在特征选择、阈值的选择等，验证集返回的结果都能使我们更定量地来决定是否这样选择特征或阈值。最好选好特征和阈值后，用测试集来评估整个算法。整个过程中，训练集仅用来拟合均值和标准差。

异常检测与监督学习

异常检测和监督学习问题有点像，尤其是在假设数据标签的时候，但它们却不一样。此处介绍什么时候用异常检测算法更佳，什么时候用监督学习算法更好。

在异常检测中，在估计 p(x) 的值时，需要的是负样本而不是正样本。所以异常（正样本）少也可以。但监督分类很难从少量正样本中学习异常是什么（尤其是异常种类繁多的时候），且不可能针对每一个异常（正样本）都建一次模，这种情况下往往是对负样本（正常样本）建模。

但如果正样本非常大，或者有一个已经识别了正样本的算法，那么使用一个监督分类算法更合理，它能观察大量正负样本来学习相应的特征，并尝试区分它们。

虽然垃圾邮件种类繁多，但被当作监督学习问题，因为垃圾邮件的样本量很大。

总结一下，如果正样本的样本量太小，那么就用异常检测。如果正样本的样本量特别大且种类繁多或已经针对所有类型的正样本有了正确的学习算法，那么可以用监督学习。如欺诈检测（正样本量太小）用异常检测，垃圾邮件（和欺诈一个性质但样本量很大）则用监督学习。

看93

异常检测之前的数据处理与特征选择

异常检测是基于高斯分布函数对负样本建模的学习算法，所以负样本若服从正态分布的话，那是极好的。但如果不服从正态分布，那就得进行数据预处理，将其处理成服从正态分布。有以下方法可以预处理数据：

x <- log(x)
x <- log(x+c)
x <- x^(1/2)
x <- x^(1/3)
x <- x^c
…

总而言之，如果画出来的 histogram 和高斯分布相差甚远，那就可以做以上变换，来让数据更接近高斯分布，但不这么做算法还是能跑。

在异常检测中，选择的特征往往决定算法的准确度。为了选择合适的特征，误差分析往往是必要的。误差分析在上文中讲过，就是先训练出一个算法，然后在验证集上运行算法，然后找出预测出错的样本，观察它们的特征来构建一个新的特征。如下图所示。

为算法选择特征时应针对学习的问题，且应选择在异常中会特别大或特别小的特征。如在IDC中为找到异常的计算机，可以构建 CPU负载/网络流量这个特征，如果这个特征特别大的话说明该计算机可能陷入死循环了（CPU升高但网络流量一般）。

多元高斯分布

当特征之间存在一定的关联时，多元高斯分布可能会很有用。如下图中绿色的样本，很明显就有问题，但它在两个特征的单变量高斯分布函数上的值又不小，就不能从单变量高斯函数的值发现该异常样本。

使用单变量高斯分布的异常检测算法只能得出粉色圈圈的范围，而不是蓝色圈圈。因此需要一个改良版的异常检测（就是考虑了特征之间的相关关系）。

这个改良版的异常检测需要用到多元高斯分布，也就是本节要讲的内容。多元高斯分布不再为每一个特征单独建模，而是建立一个整体的模型 p(x) ，该模型的参数是向量 μ （就是很多均值）和协方差矩阵 Σ 。

下图中的 |Σ| 是协方差Σ的行列式，在 Octave 里用 det(Σ) 函数计算。

下面是一些多元高斯分布 p(x;μ,Σ) 的例子，注意观察 Σ 的变化对应的图的变化。

下图中 Σ 代表着特征之间的关系。

下面是改变向量 μ 。

多元高斯分布最重要的优势是描述多个特征变量之间的正相关或负相关情况。

基于多元高斯分布的异常检测

多元高斯分布函数如下图所示，参数μ和Σ的拟合方法展示在下侧。

过程

1.用上图中的两个公式和手里的训练集拟合出 p(x)
2.给定一个新样本x，计算出p(x)，如果小于某个阈值，则标记为异常样本。

多元高斯分布函数与单变量高斯分布函数

实际上，原始的单变量高斯分布是多元高斯分布的一个特殊情况，就是所有特征完全独立的情况。也就是说，协方差矩阵非主对角线上元素全为0的情况。

原始模型用的更频繁，多元高斯分布函数用的少一些，但各有优缺点。如果能手动创建特征来捕捉异常值，原始模型会运行得很好。多元高斯分布能自动捕捉不同特征之间的关系，不想手动创建特征来捕获异常就可以用多元高斯分布函数。

但原始模型最大的优势是，计算量更小，因为多元高斯分布函数要求解矩阵Σ的逆，该计算成本会非常高。

且即使样本量较小，原始模型也能正常运行。多元高斯分布函数要求样本量大于特征数，否则矩阵Σ不可逆，是个奇异矩阵。但实践中，需要样本量大于特征数的10倍才比较好。

在实践中通常是手动创建一个捕获异常的特征，所以原始模型用得较多。但当样本量远大于特征数的时候，用多元高斯分布函数会节省手动创建特征的时间，且效果也很好。

如果在实践中，发现这个矩阵是奇异矩阵，那么通常两种情况。①不满足样本量大于特征数。②存在冗余特征，如x₁=x₂, x₃=x₄+x₅。

# 推荐系统

像流媒体平台、购物平台等，收集用户信息以更好地推荐内容给用户（促使用户消费），这种推荐算法就是互联网公司一直在研究的机器学习的一个应用。且从这里可以接触到，机器学习的一些伟大的想法——特征学习（自动得学习一系列合适的特征）。这不比自己手动设计特征得劲？

例子

当用户j对电影i评分后，设 r(i,j)=1 ，且把评的分数赋给 y^(i,j) 。因此推荐系统的问题是，给出了 r(i,j)=1 和 y^(i,j) 的数据，去查找那些没有被评分的电影，并试图预测这些电影的评分。也就是说我们的学习算法要填补很多缺失值，这样就可以把合适的电影推荐给用户了。

基于内容的推荐算法

如有一些电影，每个用户都评价了一些电影。基于内容的推荐算法做的是观察这些用户并预测他们会如何评价没评价过的电影。

该算法假设每一部电影都有一个对应的特征集， x₁ 衡量爱情片程度， x₂ 衡量动作片程度。那么每个电影就可以用一个特征向量来表示。为做出预测，把每个用户的评价预测值看作是一个线性回归问题。需要学习一个θ^(j)∈R³（算上了截距项），用(θ^(j))^Tx⁽ⁱ⁾表示用户j对电影i的预测评分。

用Alice举个例子，Alice对应一个θ⁽¹⁾，这是要求解的参数向量。总共有5部电影，Alice给四部打了分，要预测第3部电影。假设第3部电影的特征向量为 x⁽³⁾=[1, 0.99, 0]’ ，在这里假设已经求解得到了 θ⁽¹⁾=[0, 5, 5]’ ，那么根据(θ^(j))^Tx⁽ⁱ⁾，Alice对第3部电影的评分将是4.95。也就是说该算法为每一个用户应用了一个不同的线性回归。

公式化

先介绍下标记：

设 r(i,j)=1 ，如果用户j评价了电影i，否则设为0。那么 y^(i,j) 则为评的分，如果有的话。 θ^(j) 是用户j的参数向量。 x⁽ⁱ⁾ 是电影i的特征向量。用(θ^(j))^Tx⁽ⁱ⁾来预测用户j对某个未评分电影的评价分数。 m^(j) 为用户j评价的电影数量。现在要求的是 θ^(j) 。

为了求解 θ^(j) ，那么就是要获得一个 θ^(j) 使得预测值离真实值的误差最小。这个代价函数和多元线性回归的代价函数一模一样，不过在这里把常数 m^(j) 给去除了，不影响最后的参数计算。

上图只是针对单个用户求解 θ^(j) ，接下来一次性计算所有用户的 θ^(j) ，并使用梯度下降求解参数。值得注意的是，当k=0时代价函数不带正则化项，当k≠0时代价函数带正则化项，所以梯度下降分了两个情况。

那么这就是基于内容的推荐算法，需要假设变量是已有的（电影的爱情程度特征x₁和动作程度特征x₂），但实际情况是，我们并没有这样的特征量，或者很难获取所有电影的这些特征量。下面讲的推荐系统算法不是基于内容的，会自动学习特征。

协同过滤（Collaborative Filtering）

这是第二种内容推荐系统的算法，该算法能够自行学习所要使用的特征。在上一种方法中，给每一部电影了一个特征集（浪漫程度x₁和动作程度x₂），但实际上得到每一部电影的浪漫程度和动作程度是不现实的。

上一个方法是去拟合出用户的参数θ，该方法假设已经知道了用户的参数θ，去求电影的特征。假设我们知道了用户喜爱浪漫电影的程度和动作电影的程度，那么就得到了如图中所示的四个用户参数 θ 。知道了这些就可以推测出每部电影的特征值。

举个例子，第一部电影前两个用户给了5分，后两个用户给了0分。已知前两个用户非常喜欢浪漫电影，后两个用户讨厌浪漫电影。那么可以推断这部电影是浪漫电影。实际上求的是，该电影的特征x1应该是什么，才能使得 (θ⁽¹⁾)^Tx⁽¹⁾≈5 ， (θ⁽²⁾)^Tx⁽¹⁾≈5 ， (θ⁽³⁾)^Tx⁽¹⁾≈0 ， (θ⁽⁴⁾)^Tx⁽¹⁾≈0 。那么在这个例子中， x⁽¹⁾=[1, 1.0, 0.0]^T 会是一个好的解。

优化目标

假设用户告诉了我们偏好，也就是说用户提供了 θ⁽¹⁾,θ⁽²⁾,θ⁽³⁾,…,θ^(n_u) ，通过这些用户参数θ来求电影i的特征 x⁽ⁱ⁾ 。下图中的第一个公式，就是针对电影i的求解特征的优化算法，对每一个对电影i有过评分的用户j，将预测得分与他们实际得分的平方距离求和并最小化，就是该算法的优化目标。后面跟了一个正则化项，防止特征值变得太大。

但我们不只求电影i的特征x⁽ⁱ⁾，而是求所有电影的特征 x⁽¹⁾,x⁽²⁾,…,x^(n_m) 。那么就需要对所有的电影进行求和。得到下面的公式。

在上面一节讲的是基于内容的推荐算法，这一节讲的是基于协同过滤的推荐算法。前者是给定电影的特征集x，求用户的参数θ；后者是给定用户的参数θ，求电影的特征集x。那么可以随机猜一些θ值，初始化θ后用来学习电影的特征，再根据特征学习θ，如此往复。最后算法收敛，得到一组合理的电影特征和用户参数。这不是最后的算法，还可以进行优化。

最后讲讲如何理解协同过滤，当执行协同过滤时，要观察大量用户的实际行为来协同得到更佳的每个人对电影的评分值。因为如果每个用户都对一部分电影做出评价，那么每个用户都在帮助算法学习出更合适的特征。然后根据这些学习到的特征，更好地预测用户的评分。也就是说每个用户都在帮助算法更好地学习特征。

协同过滤算法

上面一小节讲到了协同过滤算法的思想，接下来讲到的算法不用循环计算用户参数θ和电影特征x，而是一步到位同时解出用户参数θ和电影特征x。这个算法把上面讲到的两个公式结合到一起，形成一个新的公式。

下图中，第一个公式的求和，是针对每一个用户，求算法给出的每一个预测值与用户j每一部评过分的电影的真实值的平方距离的和。第二个公式求的和，是针对每一部电影，求算法给出的每一个预测值与每一个用户给出的真实值（如果有）的平方距离的和。第三个公式把前两个公式整合到一起，该公式的特性是，如果假设电影特征x是常数，那么该公式会变为第一个公式；如果假设用户参数θ是常数，那么该公司变为第二个公式。

那么协同过滤算法的优化目标就变为最下面红框框里的目标了，该算法唯一的不同是不用像之前的算法那样反复计算。

在以前我们以这样的方法学习特征量时，遵循的一个惯例是设 x₀=1 （对应一个截距项），但在协同过滤算法中不再遵循这个管理，特征量将是一个n维实数（以前特征量是n+1维的）。同样的参数θ也是n维的，因为不用计算x₀的参数。放弃这个惯例的原因是，现在在学习所有特征，没必要硬核地给一个特征值编码为1，如果特征值真的是1，算法会给出来1这个答案。

再说一下整个流程。1.给特征x和参数θ随机初始化，都赋予一个小的随机值。2.使用梯度下降求解特征x和参数θ。3.给一个用户，这个用户带有一些参数θ，再给一部电影，带有已知的特征x。如果用户尚未对这部电影评分，就可以使用θ^Tx来预测用户对该电影的评分。

协调过滤算法的向量化实现

为了以向量化的方式实现协同过滤算法，需要用到低秩矩阵分解。

首先把数据集写入矩阵Y（包括未知值），不同的列代表不同的用户，不同的行代表不同的电影。

为将每一个预测评分 (θ^(j))^T(x⁽ⁱ⁾) 写入矩阵，需要写一个矩阵X，该矩阵包含了所有电影的特征值，且每一行代表一个电影（图中写的是x^T，因为x是一个列向量）；同理，再写一个矩阵Θ，包含所有的用户参数，且每一行代表一个用户。那么这个预测评分的矩阵就可以写成 XΘ^T 。

寻找相关产品

对于每一个产品i，通过协同过滤算法学习出了它的许多特征，虽然这些特征很难理解，但能够提高预测准确度就行。

相关产品可能产品的特征是相似的，所以如果一个用户喜欢产品i，那么找到能使得 ||x(i)-x(j)|| 较小的产品j推荐给用户就可以了。

也就是说，两个产品的特征向量的距离小，则可以认为两产品相似，可以用来推荐。

Mean Normalization

如果有一个用户没有给任何一个电影评分，那么矩阵Y会有一列全是问号。如下图的优化后的协同过滤算法所示，第一个求和项将会是0，因为没有满足 r(i,j)=1 的情况，所以能影响优化目标的只有最后一个求和项（对Θ的求和）。要是最后一个求和项最小，那么只能使得所有参数都为0，这就是学习结果。用参数0来预测电影评分，结果也是0，没有意义。

所以提出了均值归一化，来解决这个问题。

1.求出每部电影的评分均值（评分总分/评分个数）。2.将每一部电影的评分减去对应的均分，最后的?依旧是?，得到一个新的评分矩阵。3.用新的评分矩阵来运行协同过滤算法，但预测值应该写成 (θ^(j))^Tx⁽ⁱ⁾+μ_i ，因为新的评分矩阵减去了每部电影对应的均值。4.虽然对于那个从未打过分的用户，学习到的参数还是0，但是预测的分数却变成了每部电影的均值。

# 大尺度机器学习

现在的机器学习算法比二十年前的算法运行的好的原因之一是现在又极其庞大的数据来训练算法。下面几节讲处理海量数据的算法。

为什么要用海量数据？
为获取高性能的机器学习系统，需要采用低偏差的算法并用庞大数据进行训练。

但对于批量梯度下降（上面的梯度下降全是批量梯度下降）来说，有了大数据，计算就很成问题。因为每一次同步更新计算导数时，都需要完整遍历一次数据集。

选取一小部分随机样本来看增加样本是否有用

在提到随机梯度下降之前，可以先试试用随机的一千份样本来绘制学习曲线。如果学习曲线如下图左图所示，那么增加训练样本将有助于提升效果。如果学习曲线如下图右图所示，那么很明显是一个高偏差问题，增加样本量效果不大，就不用去费精力获得更大数据了。

随机梯度下降（Stochastic Gradient Descent）

随机梯度下降法是对批量梯度下降法的改进，为了适用于大数据。对于随机梯度下降，提出新的代价函数 cost(θ, (x⁽ⁱ⁾, y⁽ⁱ⁾)) ，是预测值与真实值距离平方的一半，它衡量的是假设函数在某一个样本上的表现。随机梯度下降过程：

随机打乱所有数据
遍历所有的训练样本，针对每一个样本进行梯度下降。也就是说，先关注第一个样本，把参数改一下，使算法对第一个样本拟合得更好。然后再更改参数使得算法对第二个样本拟合得更好，以此类推，直到完成所有的训练集。

随机梯度下降的循环会遍历整个训练集，从这个遍历的角度分析随机梯度下降，随机打乱数据将会使得随机梯度下降收敛得更快。随机梯度下降对于批量梯度下降最大的优点是每一次计算导数时不用遍历所有数据集，而是每一次只针对一个样本，遍历数据集后使算法收敛。

在针对每一个样本使得代价函数最小时，算法在一点点修改参数，使得参数朝着全局最小值的方向修改。再看一遍随机梯度下降的过程以及收敛的曲线。红色的曲线是批量梯度下降，粉色的折线是随机梯度下降。总的来看参数是朝着全局最小值的方向移动的，不过偶尔有例外，整个过程是随机迂回的，朝全局最小值前进。

最后，外层循环决定整个过程中循环的次数，训练集的大小决定外层循环的次数。训练集特别大，通常来说一次就够了。如果不是特别大，一般1-10次。

学习率和收敛

在正确的 Batch梯度下降中，每一次迭代代价函数都是下降的。但对于随机梯度下降来说，代价函数可能不是每一次都是下降的。那么怎么确定随机梯度下降正确执行了呢？对于这个问题，依旧是画出代价函数的折线图。但该代价值不是针对全体训练样本的代价，而是迭代b次后，用更新后的参数，计算这b个样本的代价函数的平均值，作为代价。通过这个图看出随机梯度下降是否在收敛。

因为是每b个样本的代价值均值，所以有很多噪声总的来看歪歪扭扭。随机梯度下降不会收敛到全局最小值，而是在某个范围内来回振荡，最后接近全局最小值。如果 α 更小，那么这种振荡会更小，可以得到更好的参数。

如果得到下图左上角的结果，那么这是个很不错的下降过程，可以看出代价函数的值在下降。在某个值后图像变得平缓，说明已经收敛了。如果用更小的 α ，那么图像将变成红色的线所示的图像，可能收敛到更好的结果。

如右上角的图所示，将每1000次改为每5000次计算一次代价值，会得到红色的更平缓的曲线。确实能反映算法收敛了，但不能及时反应算法运行的情况，因为每5000次才有个数据点。

如左下角的图所示，看起来代价函数的值没有减小，算法没有在学习。但增加成每5000次计算一个数据点并绘图，会发现算法是在收敛的，只是蓝线求均值的样本太少了，包含了太多噪声，导致看不出。但也可能即使增加了样本的数量，粉色的曲线还是很平坦，那就说明算法确实没收敛，那么就得调整 α 或者调整特征。

如右下角的情况，发现代价函数曲线是上升的，那么算法发散了，需要调小 α 。

运行随机梯度下降算法，代价函数的值会曲折地到达最小值，且不会收敛到全局最小值，而是在最小值附近一直徘徊。因此得到的参数值是全局最小值的近似值。如果想算法更好地收敛到全局最小值的近似值，可以让 α 随迭代次数减小，振荡会越来越小，代价函数的值会非常靠近全局最小值。但该方法需要去确定两个额外的参数。

Mini-Batch Gradient Descent

Mini-Batch梯度下降就是每次迭代用 b 个训练样本，与每次迭代用所有训练样本的batch梯度下降和每次迭代只用1个训练样本的随机梯度下降不同。选取 b 为2到100为常用的取值范围，通常可以取10。

假设取 b 为10，共有1000个训练样本，完整算法如下图所示。Mini-Batch梯度下降比随机梯度下降更快，因为可以对多个样本进行并行梯度下降。但选择参数 b 可能会费点时间。

在线学习

当网站或服务有连续不断的用户流时，学习算法对于每个用户只用一次。该方法可以适应变化的用户偏好，如随经济环境变化用户可能会对价格敏感。

如一个快递服务，每个用户就是一个 (x, y) ，x包括一系列社会经济属性及快递的价格，y表示用户是否购买服务。学习的是 p(y=1|x; θ) （用户在给定特征和价格下购买服务的概率）。学习好算法后，可以利用这些信息，在新用户来的时候选择合适的价格。

该方法用一个用户（行为）就丢一个用户（行为），因为有连续不断的用户流。所以 (x, y) 没有索引。

我感觉不是不重复利用用户，而是不重复利用用户的某个行为。因为有大量的用户每时每刻进行大量的操作，所以数据很多。

该算法的思想和随机梯度下降很像，唯一不同是之前讲的随机梯度下降用的是固定的训练集。

MapReduce

很多机器学习问题过于庞大以至于不能在一台电脑上运行，可能数据太多不能在一台电脑上把数据全跑一遍，因此可以对大规模机器学习上使用 MapReduce 的方法。

用Batch梯度下降举例，因为每一次迭代都会遍历全部样本，如果数据量大的话会很费时间，所以把数据集分为n个部分，n台计算机分别领一部分进行遍历，这样每台计算机的工作量都会小一点，计算完成后把结果发给中心服务器来整合这些结果。

具体如下图所示，把400份样本的训练集分为4份，每份100个样本。然后四台机器分别对每份样本进行遍历，得到计算结果temp_j⁽¹⁾-temp_j⁽⁴⁾。最后将计算结果汇总。也就是说把求和项分为4份，4台计算机每台计算1份求和，然后把每份求和项加起来，组成最后想要的完整样本的求和项。

MapReduce使用限制

把 MapReduce 运用在某种算法之前，需要考虑一个关键问题，该算法是否可以表示成对某种训练集的求和。事实上很多算法可以，而在大数据集上运行这些算法所消耗的计算量就在于需要对非常大的训练集进行求和。

# 应用实例：Photo Optical Character Recognition

Photo OCR有三个步骤——1.识别文字区域。2.字符分离。3.字符识别。（4.单词拼写修正）

像这样的系统被称为机器学习流水线（Pipeline）。在很多复杂的机器学习系统中这种流水线形式非常普遍，流水线中会有多个不同模块。设计一个机器学习系统，要作出最重要的决定之一就是怎样设计流水线的各个模块，这样便于分配人员和工作。

滑动窗口分类器

图像OCR流水线第一步是文字识别，就是下图中不同长宽比的矩形框，长宽比不同的例子有点难，先从简单一点的行人检测例子讲起。

在行人检测例子中，要识别的东西具有相似的长宽比，那么用一个固定长宽比的矩形就可以了。但对于一串文字来说，这个长宽比例是不同的。虽然行人距离摄像头位置不同，大小会改变，但比例依旧不变。

行人检测系统流水线

流水线如下：

确定比例的标准为82*36（或相似的值）。
从数据集中收集一些正样本和负样本（1000个到10000个）。
应用监督学习算法构建一个分类器，来判断是否为行人。
在测试集中运行一个滑动窗口，判断每个窗口内是否有行人。

所谓滑动窗口是下图中绿色的固定比例矩形框，它出现在了一张图片的左上角，系统判断该框内是否有行人，判断结束后，窗口向右滑动一个步长再判断框内是否有行人，一直滑动完整个图片。然后用该比例更大或更小的窗口重复执行上述操作。分类器若返回1的值，则说明区域内存在行人。

照片OCR的文字识别

那么以上是行人检测的滑动窗口，接下来返回到文本检测的例子。与行人检测例子类似：

拿出一系列包含正样本和负样本的训练集。其中正样本代表对应区域有文字出现，负样本代表框内没有文字。
使用监督学习算法学习一个分类器，来判断区域内是否有文字。
用一个固定比例大小的矩形在新图上滑动。如下图所示，分类器认为出现文字的部分用白色表示，可能出现文字的部分用灰色表示，黑色就是分类器不认为有文字。
如下图所示，运行一个放大算子，把每个白色方块扩大成右侧的样子。原理就是判断白色像素周围5到10个像素内，是否也有白色像素，如果有的话就把整个范围内的像素都变白色。
用算法将高瘦的矩形框丢掉。