主题：机器学习基础概念和统计机器学习基本算法
整理：侯宇轩
背景
- 机器学习（machine learning）形象的来说，就是使用机器（计算机）利用数据，自行对数据特征进行学习（与手工编写程序直接解决问题区分），来解决现实生活中的问题（如手写数字识别、实例分割等等）。
- 机器学习算法已经对人们对数据的利用方式造成了重大改变。例如医院开始将诊疗数据保存下来，包括病人的基本信息、医生的诊断结果、CT图像等等。使用学习型算法对这些数据进行分析，就可以得到一段时间内的病例发展趋势，或者尝试利用CT数据对病人的病灶进行自动检测等等。
分类
机器学习可以简单的认为是基于数据的学习。依据学习时是否有数据标签，分为监督学习、无监督学习和半监督学习
监督学习指不仅把训练数据丢给计算机，而且还把分类的结果（数据具有的标签）也一并丢给计算机分析。 计算机进行学习之后，再丢给它新的未知的数据，它也能计算出该数据导致各种结果的概率，给你一个最接近正确的结果。 由于计算机在学习的过程中不仅有训练数据，而且有训练结果（标签），因此训练的效果通常不错。监督学习的结果可分为两类：分类或回归。
非监督学习指的是只给计算机训练数据，不给结果（标签），因此计算机无法准确地知道哪些数据具有哪些标签，只能通过发现数据内部的一些相似特征，把数据划分为若干类。非监督学习一般表示为聚类算法。
对于半监督学习，其训练数据的一部分是有标签的，另一部分没有标签，而没标签数据的数量常常远远大于有标签数据数量（这也是符合现实情况的）。 隐藏在半监督学习下的基本规律在于：数据的分布必然不是完全随机的，通过一些有标签数据的局部特征，以及更多没标签数据的整体分布，就可以得到可以接受甚至是非常好的分类结果。
半监督学习分为很多种不同的情况。这里举一个例子：对下图，我们使用了先聚类再标注的手段。虽然有标签的数据很少，但是能够取得比较好的效果。
梯度下降算法
如何评判机器学习算法效果的好坏？一般会依据学习目标定义损失函数(loss function) J。例如，在分类问题中，损失函数定义为预测向量与标准向量之间的相似度。找到函数J的全局最优值，也就找到了机器学习算法最合适的参数。
梯度下降算法：在每一次训练的迭代中，计算损失函数的梯度，并且在参数空间中向梯度方向移动一定步长。
梯度下降算法的公式：
学习率与过拟合
学习率(Learning rate)作为机器学习中重要的超参，其决定着目标函数能否收敛到局部最小值以及何时收敛到最小值。合适的学习率能够使目标函数在合适的时间内收敛到局部最小值。梯度下降公式中α即为学习率，决定参数空间中的步长。
当学习率设置的过小时，收敛过程十分缓慢，且容易陷入局部极小值中。
- 当学习率设置的过大时，算法可能在参数空间的最小值附近来回震荡，无法收敛。
泛化能力（generalization ability）是指机器学习算法对新鲜样本的适应能力。学习的目的是学到隐含在数据对背后的规律，对具有同一规律的学习集以外的数据，经过训练的模型也能给出合适的输出，该能力称为泛化能力。
欠拟合：精度不足，泛化能力好。
过拟合：过于追求精度导致泛化能力不足。
如何防止过拟合？
最好的方法：增大训练样本。足够大的训练样本可以解决大多数问题。
正则化：在损失函数J中加入正则项，一般与参数的某个范数有关。
比如在最小二乘回归当中，函数的各个高阶（最高n阶）项之前的系数可以使用正则化进行限制。
统计机器学习基础方法：K近邻法
K近邻法(K-nearest-neighbors)主要用于分类问题。
对于新加入的点，寻找距离该点最近的k个已经进行分类的点。这k个点中数量最多的一类作为新点的类标签。
特点：分类器不需要使用训练集进行训练，训练时间复杂度为0。
重要的超参数：K。如下图，K=3与K=5会造成新点被分为不同的类。
改进算法：增加权重的knn。这个权重可以是距离权重（距离近的权重大），也可以是类别权重（更重视的一类权重大）
统计机器学习基础方法：支撑向量机SVM
支撑向量机（Support Vector Machine）主要用于分类问题。
它是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是间隔最大化，最终转化为一个凸二次规划问题来求解。根据数据的分布特点，SVM分为线性可分SVM、线性不可分SVM、非线性SVM三种，这里我们介绍第一种。
如果一个线性函数能够将样本分开，称这些数据样本是线性可分的。什么是线性函数呢？其实很简单，在二维空间中就是一条直线，在三维空间中就是一个平面，以此类推，如果不考虑空间维数，这样的线性函数统称为超平面。我们看一个简单的二维空间的例子，O代表正类，X代表负类，样本是线性可分的，但是很显然不只有这一条直线可以将样本分开，而是有无数条，我们所说的线性可分支持向量机就对应着能将数据正确划分并且间隔最大的直线。 我们所说的线性可分支持向量机就对应着能将数据正确划分并且间隔最大的直线。
为什么要间隔最大呢？一般来说，一个点距离分离超平面的远近可以表示分类预测的确信度，如图中的A B两个样本点，B点被预测为正类的确信度要大于A点，所以SVM的目标是寻找一个超平面，使得离超平面较近的异类点之间能有更大的间隔，即不必考虑所有样本点，只需让求得的超平面使得离它近的点间隔最大。
如何计算间隔？
在样本空间中，划分超平面可通过如下线性方程来描述：
其中w为法向量。假设超平面能将训练样本正确的分类，即对于训练样本(xi,yi )，满足
yi=+1代表正样本，yi=-1代表负样本（二分类）。这里的公式成为最大间隔假设。实际上，大于、小于号后面的+1、-1只是为了计算方便，理论上无论是多少，都可以通过变换w、b使其变为+1、-1。
将上式左右乘以yi，得到
实际上等于
训练中所有的样本都应满足上式。
如图，距离超平面最近的这几个点满足刚才的最大间隔假设，这几个点即称作支撑向量。虚线称为边界，虚线之间的距离称为间隔。
计算即可发现，间隔
补充证明： 设x+ 、x- 为两个异类支撑向量，那么间隔实际上即为两个异类支撑向量的差在W上的投影。
在得到间隔之后，要确定我们的计算目标：
此时，SVM的求解已经化为一个二次规划(QPLC)问题，可以使用各种求解器进行求解。有兴趣的读者可以了解一下对偶方法，可以将该问题进一步化为LPQC问题，此处不再赘述。
统计机器学习基础方法：决策树
决策树(decision tree）主要用于分类问题。
决策树由节点和（有向）边组成，将整个数据集划分为树状。内部节点表示一个特征或者属性，叶节点表示一个类，每个分叉处代表选择了一个特征。
测试时（建树完成后），将新节点依据决策树的分叉向下查找，直到到达叶节点确定最后分类。如下图是一棵简单的决策树，可以根据是否拥有房产、是否已婚、年收入是否大于等于80单位来将人分为能够偿还贷款和无法偿还贷款的两类。
目标：训练出一个与训练数据矛盾较小的决策树，同时需要保证泛化能力。
损失函数J：通常是正则化的极大似然函数。
通常算法：递归的选择最优特征。首先在根节点选择一个最优特征，使得各个子集在当前条件下有最好的分类。如果这些子集已经基本正确分类，那么停止分叉，构建叶节点；否则，需要对子集依照上面的原则重新分割。
以上方法可能会出现过拟合的现象。我们需要对生成的树进行剪枝，去掉过于细分的节点。可以看出，决策树学习算法包含特征选择、决策树生成、剪枝三部分。
特征选择原理：选取分类能力更强的特征。通常选取的准则是信息增益。
除了以上的后剪枝之外，使用的更多的方法是预剪枝。方法包括：
1.指定每一个结点所包含的最小样本数目，例如10，则该结点总样本数小于10时，则不再分；
2.指定树的高度或者深度，例如树的最大深度为4；
3.指定结点的熵若小于某个值则不再划分。
✉️ zjuvis@cad.zju.edu.cn