基本知识

样本（sample）：每条记录对一个事务的描述
数据集（data set）：这组记录的集合
属性（attribute）：反映时间或对象在某个地方的表现或性质的事项
属性空间（attribute space）：属性组成的空间
特征向量（feature vector）：由于空间中的每一个点都对应一个坐标向量，所以也可以叫做特征向量
学习/训练（learning/train）：从数据中学得的模型的这一过程
训练样本（testing sample）：在训练过程中使用的数据
训练集：训练样本组成的集合

学习的过程就是为了找到或者逼近真相

分类（classification）：预测的数值是离散值
回归（regression）：预测的数据是连续值
测试（testing）：在有了模型后，进行预测的过程；测试样本：被预测的样本
聚类（clustering）：将训练集中的样本分组；簇：每一个组都成为一簇
按照训练数据是否有标记，学习任务可以分为监督学习（supervised）和非监督学习（unsupervised）
泛化能力(generalization):学习模型适用于新样本的能力

机器学习算法在学习的过程中对某种类型的假设偏好，叫做归纳偏好；没有免费的午餐定理：无论学习算法有多聪明啊，他们的期望都是一样的；但是对于某一个具体的问题时，算法是有更好的

人们把已有的知识教给计算机时十分困难的，所以有了让计算机去学习的思想

深度学习模型的复杂程度非常高，把参数调节好，性能往往就好，深度学习虽缺乏严格的理论技术，但它显著降低了机器学习应用者的门槛

模型评估与选择

经验误差

错误率：分类错误的样本占总样本数量的比例
E=a/m
精度：1-错误率
训练误差（training error）/经验误差（empirical error）:学习器在训练集上的误差
泛化误差（generalization）：在新样本上的误差
过拟合：对于已有的数据集过渡依赖，以为所有的数据都应该又这些特质，导致泛化能力下降，相对于出现的次数较多。克服机器学习中过拟合现象是当前的主要问题。
欠拟合：对于训练集的特征抓取能力太弱

机器学习目前面临的通常是np问题，或者np-hard问题
P问题：一个问题可以在多项式（O(n^k)） 的时间复杂度内解决，例如：n个数的排序（不超过O(n^2)）
NP问题：一个问题的解可以在多项式的时间内被证实或证伪，例如：典型的子集求和问题,给定一个整数集合求是否存在一个非空子集它的和为零。如给定集合s={-1,3,2,-5,6}，很明显子集{3,2,-5}能满足问题，并且验证该解只需要线性时间复杂度就能被证实。

评估方法

我们需要建立一个测试集来评判所训练模型的好坏，测试集在建立的应该和训练集是互斥的，即他们的交为空集。下面简述集中方法：

1.留出法

直接将数据集D分成两个互斥的集合，一个做训练集另一个做测试集。在划分的时候要尽量保持数据分布的一致性，让各个样本的占比尽量不变。测试集合至少包含30个样本。

2.交叉验证法

将数据集D分为k个大小一致的，相似的互斥数据集，也要保持数据的一致性。每次都用k-1个数据集作为训练集，余下的作为测试集。交叉验证法的评估结果的稳定性和保真性在很大程度是取决于k的大小，所以他也叫k折验证法，最常用的10折验证法。

3.自助法(有放回采样）

上面两种方法的训练集都是小于D的，因为要留一点做测试，自助法减小了对D的占用。建立一个D’每次都从D中抽取一个元素放到D中，然后再复制到D中，抽取m次后，我们得到了一个元素个数<=m的集合D’。

得到D中大约有37%的样本不会出现在D’中
自助法在数据集较小的情况，难以有效的划分时候较好。由于产生的数据集不能保证其一致性，改变的初试数据集的分布，可能会引入估计偏差。

调参和算法的选择没什么本质联系

性能评价

均方误差：

(函数h为逻辑判断函数）

查全率：正确的样本是否被检测出了很多

查准率：是不是一查一个准，而不是瞎猜

假正例(FP:坏的西瓜,但是模型认为是好的西瓜)
假反例(FN:好的西瓜,但是模型认为是坏的西瓜)
真反例(TN:坏的西瓜,并且模型也认为是坏的西瓜)

拟合误差

是一种结合了偏差和误差的统计量

方差偏差困境

1 偏差（Variance）指的是建立的预测模型与真实模型之间差值的期望

偏差

2 方差（Bias）指的是建立的预测模型预测值本身的波动大小，描述的是离散程度

当模型简单时,或欠拟合,模型的偏差大,方差小.
当模型复杂时,或过拟合,模型的偏差小,方差大

方差

学完数理统计再接着补充

线性模型

1.知识点补充

1）先验概率——根据若干年的统计（经验）或者气候（常识），某地方下雨的概率；说的就是根据个人经验套用一个已有的统计学概率

2）后验概率——下雨（果）的时候有乌云（因/证据/观察的数据）的概率，即已经有了果，对证据发生的可能性描述；

3）似然概率——根据天上有乌云（原因或者证据/观察数据），下雨（结果）的概率；

4）条件概率：

发生了b的情况下，a发生的概率

贝叶斯

6)全概率公式

全概率公式的意义在于，当某一事件的概率难以求得时，可转化为在一系列条件下发生概率的和。

套入条件概率公式

2.基本形式

通过属性的线性组合来预测分类结果，线性模型有很好的可解释性

w权重、p偏置量

线性回归

在上一节的基础上，再来讨论如何得到符合模型的w和b，我们选用均方根作为损失函数（最小二乘法）

就是二阶范式

将上上个公式代入上个公式得到了船新的误差函数，这个函数既有估测值还有两个参数方便收敛

这种求解w和b的值来使得误差最小化的收敛过程，叫做线性回归模型的最小二乘参数估计
对w和b求导的：

MES是一个凹函数，因为他是个抛物线，所以求关于w、b一阶导为0的点即极值点（驻点）就是误差最小的时候，但是多元问题下，不好求精确解，可以使用梯度下降来的近似解。

多元线性回归

在一般线性回归的基础上，输入的属性值是一组属性的时候就是多元的了

对数线性回归

我们想把对象和属性之间的关系放到指数尺度上，就有了新的逼近函数

3.线性判别分析(LDA）

思想；设法将给定的训练集样例投影到一条直线上，并且使得同类样例的投影点尽量接近，不同的尽量远。可以转化为投影后类内方差最小，类间方差最大

高纬度下就用方差的推广--散度

由于分子分母都有w二次项，所以最优解一定与w的长度无关，只和他的方向有关

支持向量机

定义

是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，将训练样本划分的超平面有很多，分割的原则是间隔最大化，最终转化为一个凸二次规划问题。SVM算法还包括核函数，核函数可以使它成为非线性分类器。还可以用软间隔来做很难完全划分。

image.png

间隔：

点到超平面的距离叫做间隔

超平面：

在二维空间中就是一条直线，在三维空间中就是一个平面，以此类推，如果不考虑空间维数，这样的线性函数统称为超平面。

支持向量：

离这个超平面最近的点就是”支持向量”

二次规划

黑塞阵

1.线性可分支持向量机

很显然不只有这一条直线可以将样本分开，而是有无数条，我们所说的线性可分支持向量机就对应着能将数据正确划分并且间隔最大的直线。

距离

分类

两个异类支持向量到超平面距离的和：间隔

w为法向量，决定了超平面的方向，b为位移项

我们要让间隔最大，就是让w最小

2.对偶问题

多求解二次规划问题的算法，如拉格朗日方法、Lemke方法、内点法、有效集法、椭球算法。
下面的式子加号左侧是要求解的式子，右侧是支持向量要满足的限制条件即y=1.
拉格朗日,解决的是等式约束
KKT,解决的是不等式约束，加入了一个松弛变量，让不等式约束变成了等式约束，之后拉格朗日系数和约束条件会有一个关系，再求解。

拉格朗日

kkt限制条件：满足正则和边缘条件

当=0时，即其不会出现在13中；反之α =1时，其一定是支持向量，一定在边界上。

这里显示出了支持向量机的重要特征：当训练完成后，大部分样本都不需要保留，最终模型只与支持向量有关。

如何求解：SMO

SMO算法的特点：不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止。
SMO算法则采用了一种启发式的方法，即在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计

3.核函数

当需要划分的训练集是线性不可分的，就需要一个非线性模型来分类。但是分线性问题是难解问题，所以希望能用解线性分类问题的方法求解，因此可以采用非线性变换，将非线性问题变换成线性问题。

令ϕ(x)表示将 x 映射后的特征向量，于是在特征空间中，划分超平面所对应的的模型可表示为

于是有最小化函数：

其对偶问题为：

直接求解可能由于特征维度太高了，无法计算ϕ(x)^T*ϕ(x)，于是定义一个内积函数--核函数

求解后得

常见的的核函数

4.支持向量机的多分类方案

a.一对多法（one-versus-rest,简称1-v-r SVMs）。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

b.一对一法（one-versus-one,简称1-v-1 SVMs）。其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，最后得 票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。

c.层次支持向量机（H-SVMs）。层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。

5.软间隔

有的训练集可能会很难区分，很难判断是否其过拟合，所以引入了软间隔，与之对应的硬间隔是所有样本都必须要正确的划分。

软间隔方法引入了一个损失函数来允许一些不满足的样本得到正确的分类。即引入松弛变量的间隔问题成为软间隔

三种常见的代替损失函数

正则化角度看svm

二范数也算是正则化，

L1正则化的优点是优化后的参数向量往往比较稀疏；L2正则化的优点是其正则化项处处可导。

正则化

其中Ω（f）就可以看作是正则化项，在贝叶斯概率中被看作是先验概率，c是正则化常数，累加可以看作是约束、容错。

另一个角度看svm

依旧是用正则化公式，现在的正则化项可以看作是结构风险，用来描述模型某些性质，依旧是先验概率是在有样本之前就知道的，累加看作是经验风险是后验概率，用来描述模型与训练数据的契合程度，c是用来做微调的是两者的折中。

基础知识：

损失函数：针对单个具体样本，表示模型预测值与真实样本值之间的差距。损失函数越小，说明模型对于该样本预测越准确。常见损失函数有0-1损失函数、平方损失函数、绝对损失函数、对数损失函数（对数似然损失函数）。

image

经验风险：对所有训练样本都求一次损失函数，再累加求平均。即模型f(x)对训练样本中所有样本的预测能力。

image

所谓经验风险最小化即对训练集中的所有样本点损失函数的平均最小化。经验风险越小说明模型f(x)对训练集的拟合程度越好。

期望风险：对所有样本（包含未知样本和已知的训练样本）的预测能力，是全局概念。（经验风险则是局部概念，仅仅表示决策函数对训练数据集里的样本的预测能力。）

我们知道未知的样本数据（<X,Y>）的数量是不容易确定的，所以就没有办法用所有样本损失函数的平均值的最小化这个方法，那么怎么来衡量这个模型对所有的样本（包含未知的样本和已知的训练样本）预测能力呢？熟悉概率论的很容易就想到了用期望。即假设X和Y服从联合分布P(X,Y).那么期望风险就可以表示为：

image

理想的模型（决策）函数应该是让所有的样本的损失函数最小（即期望风险最小化）。但是期望风险函数往往不可得，所以用局部最优代替全局最优。这就是经验风险最小化的理论基础。

总结经验风险和期望风险之间的关系：

经验风险是局部的，基于训练集所有样本点损失函数最小化。经验风险是局部最优，是现实的可求的。

期望风险是全局的，基于所有样本点损失函数最小化。期望风险是全局最优，是理想化的不可求的。

缺点：只考虑经验风险的话，会出现过拟合现象，即模型f(x)对训练集中所有的样本点都有最好的预测能力，但是对于非训练集中的样本数据，模型的预测能力非常不好。怎么办？这就需要结构风险。

结构风险：对经验风险和期望风险的折中，在经验风险函数后面加一个正则化项（惩罚项），是一个大于0的系数lamada。J(f)表示的是模型的复杂度。

经验风险越小，模型决策函数越复杂，其包含的参数越多，当经验风险函数小到一定程度就出现了过拟合现象。也可以理解为模型决策函数的复杂程度是过拟合的必要条件，那么我们要想防止过拟合现象的方式，就要破坏这个必要条件，即降低决策函数的复杂度。也即，让惩罚项J(f)最小化，现在出现两个需要最小化的函数了。我们需要同时保证经验风险函数和模型决策函数的复杂度都达到最小化，一个简单的办法把两个式子融合成一个式子得到结构风险函数然后对这个结构风险函数进行最小化。

近邻法

一般用灰度图，也需要模板来做匹配.数据太多了，可以把数据聚类
和线性回归一样用二范数

1.k近邻（k-nearest neighbor,k-NN）

k一般选择的是奇数

2.最近邻

缺点：第一个是需要存储全部的训练样本，第二个是计算量较大

分组快速搜索近邻法。

其基本思想是：将样本集按用聚类分析分解成一个个组，给出每组质心的位置，以质心作为代表点，和未知样本计算距离，选出距离最近的一个或若干个组，再在组的范围内应用一般的KNN算法。由于并不是将未知样本与所有样本计算距离，故该改进算法可以减少计算量，但并不能减少存储量。

用两步规则来筛掉绝大部分的点，剩下的点就要逐个计算距离了。
质心Mp的位置不会改变，D（Mp-Xi)是已经计算并储存好的，所以二式，中要使用D（Mp-Xi)。