##################################### 重点总结 ##################################### 机器学习 #################################### 技术概念 ================================= 按照用途和要解决的问题，机器学习算法可以分为有监督学习，无监督学习，强化学习3种类型。 其中，有监督学习又进一步细分为分类问题与回归问题，无监督学习算法分为聚类问题和数据降维问题。 概括起来，各类算法要解决的核心问题是： 分类算法 是什么 回归算法 是多少 聚类算法 怎么分 数据降维 怎么压 强化学习 怎么做 训练集数据量大小的要求 -------------------------------------- 一个粗略的启发是，训练数据量不应小于模型可调参数数量若干倍(5或者10). 出自 PRML 第一章。 有监督学习与无监督学习 -------------------------------------- 根据样本数据是否带有标签值，可以将机器学习算法分成有监督学习和无监督学习两类。 有监督学习的样本数据带有标签值，它从训练样本中学习得到一个模型，然后用这个模型对新的样本进行预测推断。有监督学习的典型代表是分类问题和回归问题。 无监督学习对没有标签的样本进行分析，发现样本集的结构或者分布规律。无监督学习的典型代表是聚类，表示学习，和数据降维，它们处理的样本都不带有标签值。 分类问题与回归问题 -------------------------------------- 在有监督学习中，如果样本的标签是整数，则预测函数是一个向量到整数的映射，这称为分类问题。如果标签值是连续实数，则称为回归问题，此时预测函数是向量到实数的映射。 生成模型与判别模型 -------------------------------------- 分类算法可以分成判别模型和生成模型。给定特征向量x与标签值y，生成模型对联合概率p(x,y)建模，判别模型对条件概率p(y|x)进行建模。 另外，不使用概率模型的分类器也被归类为判别模型，它直接得到预测函数而不关心样本的概率分布： .. math:: y=f(x) 判别模型直接得到预测函数f(x)，或者直接计算概率值p(y|x)，比如SVM和logistic回归，softmax回归，判别模型只关心决策面，而不管样本的概率分布的密度。 生成模型计算p(x, y)或者p(x|y) ，通俗来说，生成模型假设每个类的样本服从某种概率分布，对这个概率分布进行建模。 机器学习中常见的生成模型有贝叶斯分类器，高斯混合模型，隐马尔可夫模型，受限玻尔兹曼机，生成对抗网络等。典型的判别模型有决策树，kNN算法，人工神经网络，支持向量机，logistic回归，AdaBoost算法等。 `理解生成模型与判别模型`_ 交叉验证 -------------------------------------- 交叉验证（cross validation）是一种统计准确率的技术。 k折交叉验证将样本随机、均匀的分成k份，轮流用其中的k-1份训练模型，1份用于测试模型的准确率，用k个准确率的均值作为最终的准确率。 过拟合与欠拟合 -------------------------------------- 欠拟合也称为欠学习，直观表现是训练得到的模型在训练集上表现差，没有学到数据的规律。引起欠拟合的原因有模型本身过于简单，例如数据本身是非线性的但使用了线性模型；特征数太少无法正确的建立映射关系。 过拟合也称为过学习，直观表现是在训练集上表现好，但在测试集上表现不好，推广泛化性能差。过拟合产生的根本原因是训练数据包含抽样误差，在训练时模型将抽样误差也进行了拟合。所谓抽样误差，是指抽样得到的样本集和整体数据集之间的偏差。引起过拟合的可能原因有： 模型本身过于复杂，拟合了训练样本集中的噪声。此时需要选用更简单的模型，或者对模型进行裁剪。训练样本太少或者缺乏代表性。此时需要增加样本数，或者增加样本的多样性。训练样本噪声的干扰，导致模型拟合了这些噪声，这时需要剔除噪声数据或者改用对噪声不敏感的模型。 偏差与方差分解 -------------------------------------- 模型的泛化误差可以分解成偏差和方差。偏差是模型本身导致的误差，即错误的模型假设所导致的误差，它是模型的预测值的数学期望和真实值之间的差距. 方差是由于对训练样本集的小波动敏感而导致的误差。它可以理解为模型预测值的变化范围，即模型预测值的波动程度。 模型的总体误差可以分解为偏差的平方与方差之和： .. math:: E \left( (y-f(x))^2 \right ) = Bias^2 \left ( f(x) \right ) + Var \left ( f(x) \right ) + \sigma^2 如果模型过于简单，一般会有大的偏差和小的方差；反之如果模型复杂则会有大的方差但偏差很小。 其他阅读 `偏差与方差 `_ 正则化 -------------------------------------- 为了防止过拟合，可以为损失函数加上一个惩罚项，对复杂的模型进行惩罚，强制让模型的参数值尽可能小以使得模型更简单，加入惩罚项之后损失函数为： .. math:: L(\theta) = \frac{1}{2l} \sum^{l}_{l=1} (f_{\theta} (x_i) -y_i)^2 + \frac{\lambda}{2} r(\theta) 正则化被广泛应用于各种机器学习算法，如岭回归，LASSO回归，logistic回归，神经网络等。除了直接加上正则化项之外，还有其他强制让模型变简单的方法，如决策树的剪枝算法，神经网络训练中的dropout技术，提前终止技术等。 维数灾难 -------------------------------------- 为了提高算法的精度，会使用越来越多的特征。当特征向量维数不高时，增加特征确实可以带来精度上的提升； 但是当特征向量的维数增加到一定值之后，继续增加特征反而会导致精度的下降，这一问题称为维数灾难。 目标函数 -------------------------------------- 最优化 -------------------------------------- `机器学习中的最优化算法总结 `_ 数学 ################################################ 概率论 ============================================ 基础概念 ------------------------------------------- :边缘概率: PRML 1.2节 P17 ------------------------------------------- ------------------------------------------- 优化算法 ============================================ 好的文章 .. [] 理解凸优化 列举常用的最优化方法 ------------------------------------------- - 梯度下降法 - 牛顿法， - 拟牛顿法 - 坐标下降法 - 梯度下降法的改进型如AdaDelta，AdaGrad，Adam，NAG等。 梯度下降法的关键点 ------------------------------------------- 梯度下降法沿着梯度的反方向进行搜索，利用了函数的一阶导数信息。梯度下降法的迭代公式为： .. math:: \theta_{t+1} = \theta_{t} - \gamma \nabla f(\theta_{t}) 根据函数的一阶泰勒展开，在负梯度方向，函数值是下降的。只要学习率设置的足够小，并且没有到达梯度为0的点处， 每次迭代时函数值一定会下降。需要设置学习率为一个非常小的正数的原因是要保证迭代之后的 :math:`\theta_{t+1}` 位于迭代之前的值 :math:`\theta_{t}` 的邻域内， 从而可以忽略泰勒展开中的高次项，保证迭代时函数值下降。 梯度下降法只能保证找到梯度为0的点，不能保证找到极小值点。迭代终止的判定依据是梯度值充分接近于0，或者达到最大指定迭代次数。 梯度下降法在机器学习中应用广泛，尤其是在深度学习中。 AdaDelta，AdaGrad，Adam，NAG等改进的梯度下降法都是用梯度构造更新项，区别在于更新项的构造方式不同。 对梯度下降法更全面的介绍可以阅读SIGAI之前的公众号文章 `“理解梯度下降法” `_ 。 牛顿法的关键点 ------------------------------------------- 牛顿法利用了函数的一阶和二阶导数信息，直接寻找梯度为0的点。牛顿法的迭代公式为： .. math:: X_{k+1} = X_k - \gamma H^{-1}_{k} g_{k} 其中H为Hessian矩阵，g为梯度向量。 牛顿法不能保证每次迭代时函数值下降，也不能保证收敛到极小值点。 在实现时，也需要设置学习率，原因和梯度下降法相同，是为了能够忽略泰勒展开中的高阶项。学习率的设置通常采用直线搜索（line search）技术。 在实现时，一般不直接求Hessian矩阵的逆矩阵，而是求解下面的线性方程组： .. math:: H_k d = - g_k 其解d称为牛顿方向。迭代终止的判定依据是梯度值充分接近于0，或者达到最大指定迭代次数。 牛顿法比梯度下降法有更快的收敛速度，但每次迭代时需要计算Hessian矩阵，并求解一个线性方程组，运算量大。 另外，如果Hessian矩阵不可逆，则这种方法失效。对牛顿法更全面的介绍可以阅读SIGAI之前的公众号文章 `“理解牛顿法” `_ 。 拉格朗日乘数法 ------------------------------------------- 拉格朗日乘数法是一个理论结果，用于求解带有等式约束的函数极值。对于如下问题： .. math:: min\ f(x) h_i(x) = 0,i=1,...,p 构造拉格朗日乘子函数： .. math:: L(x,\lambda) = f(x) + \sum^{p}_{i=1} \lambda_i h_i(x) 在最优点处对x和乘子变量的导数都必须为0： .. math:: \nabla_x f + \sum_{i=1}^{p} \lambda_i \nabla_x h_i = 0 h_i(x)=0 解这个方程即可得到最优解。对拉格朗日乘数法更详细的讲解可以阅读任何一本高等数学教材。机器学习中用到拉格朗日乘数法的地方有： - 主成分分析 - 线性判别分析 - 流形学习中的拉普拉斯特征映射 - 隐马尔科夫模型 凸优化 ------------------------------------------- 数值优化算法面临两个方面的问题：局部极值，鞍点。前者是梯度为0的点，也是极值点，但不是全局极小值； 后者连局部极值都不是，在鞍点处Hessian矩阵不定，即既非正定，也非负定。 凸优化通过对目标函数，优化变量的可行域进行限定，可以保证不会遇到上面两个问题。凸优化是一类特殊的优化问题，它要求： 1. 优化变量的可行域是一个凸集 2. 目标函数是一个凸函数 凸优化最好的一个性质是：所有局部最优解一定是全局最优解。 对于凸优化更详细的讲解可以阅读SIGAI之前的公众号文章 `“理解凸优化” `_ 。 机器学习中典型的凸优化问题有： - 线性回归 - 岭回归 - LASSO回归 - Logistic回归 - 支持向量机 - Softamx回归 拉格朗日对偶 ------------------------------------------- 对偶是最优化方法里的一种方法，它将一个最优化问题转换成另外一个问题，二者是等价的。拉格朗日对偶是其中的典型例子。对于如下带等式约束和不等式约束的优化问题： .. math:: min\ f(x) g_i (x) \le 0 \ i=1,...,m h_i(x) = 0 \ i=1,...,p 与拉格朗日乘数法类似，构造广义拉格朗日函数： .. math:: L(x,\lambda,v) = f(x) + \sum^{m}_{i=1} \lambda_i g_i(x) + \sum^{p}_{i=1} v_i h_i(x) :math:`\lambda_{i}` 必须满足 :math:`\lambda_{i}\geq 0` 的约束。原问题为： .. math:: min_x\ max_{\lambda,v,\lambda_i \ge 0} L(x,\lambda,v) 即先固定住x，调整拉格朗日乘子变量，让函数L取极大值；然后控制变量x，让目标函数取极小值。原问题与我们要优化的原始问题是等价的。 对偶问题为： .. math:: max_{\lambda,v,\lambda_i \ge 0}\ min_x L(x,\lambda,v) 和原问题相反，这里是先控制变量x，让函数L取极小值；然后控制拉格朗日乘子变量，让函数取极大值。 一般情况下，原问题的最优解大于等于对偶问题的最优解，这称为弱对偶。在某些情况下，原问题的最优解和对偶问题的最优解相等，这称为强对偶。 强对偶成立的一种条件是Slater条件： 一个凸优化问题如果存在一个候选x使得所有不等式约束都是严格满足的，即对于所有的i都有 :math:`g_{i}(x)< 0` ， 不等式不取等号，则强对偶成立，原问题与对偶问题等价。注意，Slater条件是强对偶成立的充分条件而非必要条件。 拉格朗日对偶在机器学习中的典型应用是支持向量机。 KKT条件 ------------------------------------------- KKT条件是拉格朗日乘数法的推广，用于求解既带有等式约束，又带有不等式约束的函数极值。对于如下优化问题： .. math:: min\ f(x) g_i(x)\le 0 \ i=1,...,q h_i(x) = 0 \ i=1,...,p 和拉格朗日对偶的做法类似，KKT条件构如下乘子函数： .. math:: L(x,\lambda,\mu) = f(x) + \sum^p_{j=1} \lambda_j h_j(x) + \sum^q_{k=1} \mu_k g_k(x) :math:`\lambda` 和 :math:`\mu` 称为KKT乘子。在最优解处 :math:`x^{*}` 应该满足如下条件： .. math:: \nabla_x L(x^*) = 0 \mu_k \ge 0 \mu_k g_k(x^*) = 0 h_j(x^*)=0 g_k(x^*) \le 0 等式约束 :math:`h_{j}（x^{*}）= 0` 和不等式约束 :math:`g_{k}(x^{*})\leq0` 是本身应该满足的约束， :math:`\nabla_{x}L(x^{*})=0` 和之前的拉格朗日乘数法一样。唯一多了关于 :math:`g_{i}（x）` 的条件： .. math:: \mu_k g_k(x^*) = 0 KKT条件只是取得极值的必要条件而不是充分条件。 特征值与特征向量 ------------------------------------------- 对于一个n阶矩阵A，如果存在一个数 :math:`\lambda` 和一个非0向量X，满足： .. math:: A X=\lambda X 则称\lambda为矩阵A的特征值，X为该特征值对应的特征向量。根据上面的定义有下面线性方程组成立： .. math:: (A - \lambda I)X=0 根据线性方程组的理论，要让齐次方程有非0解，系数矩阵的行列式必须为0，即： .. math:: |A-\lambda I| = 0 上式左边的多项式称为矩阵的特征多项式。矩阵的迹定义为主对角线元素之和： .. math:: tr(A) = \sum^n_{i=1} a_{ii} 根据韦达定理，矩阵所有特征值的和为矩阵的迹： .. math:: \sum_{i=1}^n \lambda_i = tr(A) 同样可以证明，矩阵所有特征值的积为矩阵的行列式： .. math:: \prod^n_{i=1} \lambda_i = |A| 利用特征值和特征向量，可以将矩阵对角化，即用正交变换将矩阵化为对角阵。实对称矩阵一定可以对角化，半正定矩阵的特征值都大于等于0，在机器学习中，很多矩阵都满足这些条件。特征值和特征向量在机器学习中的应用包括：正态贝叶斯分类器、主成分分析，流形学习，线性判别分析，谱聚类等。 奇异值分解 ------------------------------------------- 矩阵对角化只适用于方阵，如果不是方阵也可以进行类似的分解，这就是奇异值分解，简称SVD。假设A是一个m x n的矩阵，则存在如下分解： .. math:: A=U \Sigma V^T 其中U为m x m的正交矩阵，其列称为矩阵A的左奇异向量； :math:`\Sigma` 为m x n的对角矩阵， 除了主对角线 :math:`\sigma_{ii}` 以外，其他元素都是0；V 为n x n的正交矩阵，其行称为矩阵A的右奇异向量。 U的列为 :math:`AA^T`的特征向量，V的列为 :math:`A^T A` 的特征向量。 目标函数 =========================================== 最小平方法、均方误差、最小二乘 ------------------------------------------ .. important:: 最小平方解，对于离群点缺少鲁棒性，容易受到离群点的影响，会是得决策平面(或者回归中的拟合曲线)严重偏向离群点的方向 最小平方法在分类问题中存在很大缺陷，参照 PRML P134，结论，最小平方法不适合分类问题。 最大似然估计 ------------------------------------------- 有些应用中已知样本服从的概率分布，但是要估计分布函数的参数 :math:`\theta` ，确定这些参数常用的一种方法是最大似然估计。 最大似然估计构造一个似然函数，通过让似然函数最大化，求解出 :math:`\theta` 。 最大似然估计的直观解释是，寻求一组参数，使得给定的样本集出现的概率最大。 假设样本服从的概率密度函数为 :math:`p(x，\theta)` ，其中X为随机变量，:math:`\theta` 为要估计的参数。 给定一组样本 :math:`x_{i} ,i =1,...,l` ，它们都服从这种分布，并且相互独立。最大似然估计构造如下似然函数： .. math:: L(\theta) = \prod_{i=1}^l p(x_i;\theta) 其中 :math:`x_{i}` 是已知量，这是一个关于 :math:`\theta` 的函数，我们要让该函数的值最大化，这样做的依据是这组样本发生了， 因此应该最大化它们发生的概率，即似然函数。这就是求解如下最优化问题： .. math:: max\ \prod_{i=1}^l p(x_i;\theta) 乘积求导不易处理，因此我们对该函数取对数，得到对数似然函数： .. math:: ln\ L(\theta) = ln\ \prod_{i=1}^l p(x_i;\theta) = \sum_{i=1}^l ln\ p(x_i;\theta) 最后要求解的问题为： .. math:: arg\ max \sum_{i=1}^l ln\ p(x_i;\theta) 最大似然估计在机器学习中的典型应用包括logistic回归，贝叶斯分类器，隐马尔科夫模型等。 .. tip:: 过拟合是最大似然的一个通用属性，通过贝叶斯方法，可以避免过拟合问题。 贝叶斯方法加入的先验，相当于惩罚项。 最大似然的缺陷 bias 偏移问题 最大似然和贝叶斯估计的区别 ------------------------------------------- PRML 1.2.3节 P23 最大后验估计（MAP）仍然是点估计，就是最大化 似然*先验，也就是相当于 正则化+似然估计。 真正的贝叶斯思想，应该是求出后验概率分布，然后通过后验概率分布加权期望（积分）进行预测。 模型 #################################### 贝叶斯分类器 ======================================== 贝叶斯分类器将样本判定为后验概率最大的类，它直接用贝叶斯公式解决分类问题。假设样本的特征向量为x，类别标签为y，根据贝叶斯公式，样本属于每个类的条件概率（后验概率）为： 分母p(x)对所有类都是相同的，分类的规则是将样本归到后验概率最大的那个类，不需要计算准确的概率值，只需要知道属于哪个类的概率最大即可，这样可以忽略掉分母。分类器的判别函数为： 在实现贝叶斯分类器时，需要知道每个类的条件概率分布p(x|y)即先验概率。一般假设样本服从正态分布。训练时确定先验概率分布的参数，一般用最大似然估计，即最大化对数似然函数。 如果假设特征向量的各个分量之间相互独立，则称为朴素贝叶斯分类器，此时的分类判别函数为： 实现时可以分为特征分量是离散变量和连续变量两种情况。贝叶斯分分类器是一种生成模型，可以处理多分类问题，是一种非线性模型。 EM算法 #################################### 以上是简单的推导过程，EM算法的步骤是 - 首先，第一轮迭代t=0时，随机初始化待求参数 :math:`\pmb{\omega}^{(t)}` - E步，求解隐藏变量 :math:`\pmb{\theta}` 的后验概率分布 :math:`g(\pmb{\theta} | \mathbf{Y},\pmb{\omega}^{(t)} )` - :math:`\pmb{\theta}` 本身是连续值，这时 :math:`g(\pmb{\theta} | \mathbf{Y},\pmb{\omega}^{(t)} )` 就是概率密度函数，计算积分比较复杂。 - 所以可以把 :math:`\pmb{\theta}` 离散化，这样 :math:`g(\pmb{\theta} | \mathbf{Y},\pmb{\omega}^{(t)} )` 就是概率质量函数，只需要求出其概率分布，然后利用求和的方式计算全概率。 - M步，极大化Q函数 :math:`Q(\pmb{\omega}^{(t+1)}|\pmb{\omega}^{(t)})` 得到新的 :math:`\pmb{\omega}^{(t+1)}` .. math:: \pmb{\omega}^{(t+1)} = \mathop{\arg\max}_{\pmb{\omega} \in \pmb{\Omega}} \sum_{\pmb{\theta} \in \pmb{\Theta}} g(\pmb{\theta}|\mathbf{Y},\pmb{\omega}^{(t)}) ln L(\mathbf{Y},\pmb{\theta}|\pmb{\omega}) - 重复E步和M步直到满足收敛条件 - :math:`\pmb{\omega}` 不再变化 :math:`|\pmb{\omega}^{(t+1)} - \pmb{\omega}^{(t)}|<\epsilon` - 对数似然函数不再变化 :math:`|lnL(\mathbf{Y}|\pmb{\omega}^{(t+1)}) - lnL(\mathbf{Y}|\pmb{\omega}^{(t)})|<\epsilon` 隐马尔科夫模型(Hidden Markov Model,HMM) ################################################### HMM的参数估计算法就是EM的一个特例，前后向算法其实就是贝叶斯网络中的传播算法，求后验概率分布的。 .. _`理解梯度下降法`: https://mp.weixin.qq.com/s?__biz=MzU4MjQ3MDkwNA==&mid=2247484111&idx=1&sn=4ed4480e849298a0aff828611e18f1a8&chksm=fdb69f58cac1164e844726bd429862eb7b38d22509eb4d1826eb851036460cb7ca5a8de7b9bb&scene=21#wechat_redirect .. _`理解凸优化`: https://mp.weixin.qq.com/s?__biz=MzU4MjQ3MDkwNA==&mid=2247484439&idx=1&sn=4fa8c71ae9cb777d6e97ebd0dd8672e7&chksm=fdb69980cac110960e08c63061e0719a8dc7945606eeef460404dc2eb21b4f5bdb434fb56f92&token=1065243837&lang=zh_CN#rd .. _`理解梯度提升算法1-梯度提升算法`: https://zhuanlan.zhihu.com/p/53064510 .. _`理解XGBoost`: https://zhuanlan.zhihu.com/p/55217712 .. _`理解EM算法`: https://zhuanlan.zhihu.com/p/54899055 .. _`集成学习综述-从决策树到XGBoost`: https://zhuanlan.zhihu.com/p/50947110 .. _`理解概率密度函数`: https://zhuanlan.zhihu.com/p/48140593 .. _`机器学习与深度学习常见面试题（下）`: https://zhuanlan.zhihu.com/p/47559203 .. _`机器学习与深度学习常见面试题（上）`: https://zhuanlan.zhihu.com/p/45091568 .. _`理解生成模型与判别模型`: https://zhuanlan.zhihu.com/p/46422895 .. _`机器学习中的目标函数总结`: https://zhuanlan.zhihu.com/p/44722270 .. _`理解 logistic 回归`: https://zhuanlan.zhihu.com/p/44583106 .. _`深入浅出聚类算法`: https://zhuanlan.zhihu.com/p/43651469 .. _`理解过拟合`: https://zhuanlan.zhihu.com/p/38224147 .. _`机器学习中的最优化算法总结`: https://zhuanlan.zhihu.com/p/42689565 .. _`理解AdaBoost算法`: https://zhuanlan.zhihu.com/p/43443518 .. _`浓缩就是精华-SIGAI机器学习蓝宝书`: https://zhuanlan.zhihu.com/p/42862322 .. _`用一句话总结常用的机器学习算法`: https://zhuanlan.zhihu.com/p/38067616 .. _``: