「周末AI课堂」非参模型初步（理论篇）机器学习你会遇到的“坑”
非参数模型的来源
曾经有人说机器学习的分为三步，分别是表示，评估和优化。表示指的是我们要将样本空间映射到一个合适的特征空间，一般的，我们更青睐于这样的表示是低维度的，是更加稀疏交互的，同时也希望是相互独立的。而评估指的是模型在数据上表现的量化形式，我们选取合适的函数来表示什么样子的模型是好的，性能度量就是我们的评估。在前两步都完成了以后，我们最后要做的就是优化，就是对我们的评估函数进行求解，找出最合适的解，来确定最终的模型。所以我们先来总结下我们在前面提到过的模型（而非方法），并用简明的话语做一个总结：
- 简单线性回归：数学形式最简单的模型，数学形式为
- ，也可理解为似然函数选取高斯分布的MLE
- 多项式回归：简单线性回归的推广，本质意义是利用泰勒展开逼近未知函数
- 岭回归：添加
- 正则化的线性回归，也可理解为，对参数分布添加均值为零高斯先验的MAP
- LASSO：添加
- 正则化的线性回归，也可理解为，对参数分布添加均值为零拉普拉斯先验的MAP
- 贝叶斯岭回归：利用贝叶斯定理的增量学习，选取高斯分布这样一种自共轭先验，可以简单的计算后验概率
- Logistic回归：利用sigmoid函数的性质，将线性回归的方法拓展为分类算法，同时因为对概率意义的直接赋予，它仍然是一个概率对特征的线性算法。
- 支持向量机：采用最大硬间隔思路在特征空间中确定决策边界，在此模型中被大量使用的kernel function可以将线性的边界拓展为非线性边界
- 朴素贝叶斯：利用贝叶斯定理对类别的后验概率进行推断，若属性值连续，则需要假设特征的分布，若属性值离散，则是基于大数定理的频率计数
我们可以看到，我们以往碰到的模型大都是携带参数，我们对模型的训练过程就是对模型参数的估计问题，比如，我们利用线性回归去适应数据的时候，我们的Loss Function就是
,我们将数据代入，利用优化算法或者直接方程求解，我们就会得到参数的最佳值，参数值一旦确定，整个模型就随之确定。
但在机器学习中，有些模型本身并没有携带参数，我们将其叫做非参数模型（non-parametric model）。我们将模型分为参数和非参数模型的背后，其实隐含着我们要不要对数据的分布做出假设，而我们所说的参数，其实就对应着分布的参数。在非参数模型中，我们不需要对样本的分布做出任何假设，直接利用样本来进行分析。我们可以很容易的发现，我们在上一节《朴素贝叶斯》中提到的，属性值离散的分类问题，也属于非参数模型，因为我们将其转化为了一个计数问题。
常见的非参数模型
K近邻（k-neighbors）
数学准备：
- 相似度：对于高维空间的样本，距离是相似度的指标，距离越近的样本，相似度就越高。（不要混淆距离和内积）
K近邻可能是机器学习最容易理解的算法（没有之一），事实上，它根本就没有进行学习，因为它的原理就是通过某种距离度量来判定样本的相似度，距离越近相似度也就越高，我们在面对分类或者回归任务的时候，只需要将新的样本放入到训练集中，通过与其最邻近的k个样本的target来判断新样本的target。
如图，考虑一个简单的二分类问题，如果我们选取k=3的情况，里面会包含两个类别2的样本，和一个类别一的样本，我们就可以根据简单的投票法，即少数服从多数原则，将新样本判定为类别2。但我们要注意到，虽然k=3时，包含了三个样本，但三个样本与我们的新样本的距离并不一致，而距离越近的样本相似度会更高，所以我们还可以对不同距离的样本赋予不同的权重，比如我们可以取距离的倒数作为权重，来使得距离越近的样本对我们的判断贡献越大。
对于回归问题，target就会变得连续，但我们仍然可以选取最近的k个样本的平均值作为我们的预测值，同样也可以根据距离的远近来赋予不同的权重。
在实际问题中，我们可以选择不同的K,不同的距离度量来作为我们的超参数，通过调节他们使得性能更好。
决策树（DecisionTree）（初步）
数学准备：
- 自信息（self-information）：
- ，是从概率角度出发对信息量的刻画。对概率取对数，是为了满足联合概率的信息的可加性，即两个事件均发生的概率要相乘，但反映在信息量上要相加；再取负值，是因为，小概率的事件信息量更大，大概率事件的信息量更小。
- 信息熵（Information Entropy）：
- ,是自信息的期望值，即，来自于一个概率分布的自信息的加权平均。
决策树是一类听起来很吓人，乍一看却又很简单，深入学习之后才知其精妙的算法。简单的来说，它模拟了人的决策过程：
如图，我们面临一个三分类问题，即go to restaurant、buy a hamburger、go to sleep的问题，每个分类都有着两个属性：自己饿不饿，有没有钱。我们的决策过程就是一颗决策树。
决策树最初步的问题，并不是树的形状，而是我们要挑选特征用于生成分支，才会使得我们沿着树的路径一直回答问题，直到得出正确的结果。进一步的来说，我们会为每个属性添加if-then的条件语句，每个节点都会做一次判断，我们希望在每次节点判断的时候，本来就属于同一类的样本都尽可能的往同一个方向走，而不希望它们分开，而不同类的样本要尽可能的分开，不要在一个分支节点上。
同时，数学上的信息熵有两点重要的性质：
- 类的样本集合越是均匀（即不同类样本等概率），信息熵就越大。反之，信息熵越小，说明某一样本的比例可能越大。从概率的意义来说，一个系统的不确定性越大，信息熵就越大。
- 样本都是均匀的两个系统，包含更多类样本的系统，信息熵也会更大
我们可以用信息熵的第一个性质来挑选特征，我们的样本集合为D,第k类样本出现的概率为
,L是总的类别数，我们的信息熵则是：
如果我们选取的特征下的某个取值会使得样本集合D变成d，d就是同一属性的相同取值下样本的集合，设定
是新的集合中包含的类别数，
是在新的样本集合中每一类所占的比例我们就可以计算出此时数据集d的信息熵：
根据信息熵的第一个性质，我们希望节点包含的样本集合的信息熵越小越好，因为这样意味着根据特征划分之后的分布就不再均匀。同时，因为相同特征的不同取值下的样本集合并不相同，假设属性有i个取值，那么所以我们要对每个取值下的信息熵进行加权平均，来获得这一属性总的信息熵：
我们可以直接对属性的信息熵（分支节点的信息熵）比较大小，将最小的信息熵所对应的属性作为我们判断的节点。但更普遍的做法是，用总体的信息熵减去属性的信息熵，就会获得所谓的信息增益（Gain），其实就是根据某个特征划分后的信息熵的变化：
其中:
表示的是，在确定的某个属性下的取值为i,类别为v的样本个数。我们对每个特征都进行这样的计算，然后挑出信息增益最大的属性。但随之而来的一个问题是，取值多的特征，就会造成信息增益较大的情形。为理解这层关系，我们只需要考虑一个极端的情况，取值数太多，造成每个取值下的样本数只有一类，
，这样按照某个特征划分后的信息熵为零，信息增益最大。从过拟合的角度来说，取值数过多的特征划分的非常精确，但这样的精确会削弱模型的泛化能力。
根据信息熵的第二个性质，为了避免信息增益偏好于取值多的特征，我们必须要添加取值多的特征要付出的代价，我们在此基础上，定义该特征下的取值个数（而非属性值本身）的信息熵：
其中，
是确定属性下取值为i的样本数。根据信息熵的第二个性质可以看出，取值个数的信息熵会随着属性值的增多，而变得越来越大。对每一个属性进行这样的计算，并且用信息增益除以它，就得到了所谓的信息增益率（Gain Ratio)：
我们就可以在属性取值的信息熵和属性取值个数的信息熵之间，取得了一种微妙的平衡。但要注意，如果属性的取值只有一个，属性个数的信息熵会变为零，我们需要引入一些修正项，强行使得分母不为零。
但如果我们只利用信息增益率来判断，可能又会导致节点的划分偏好于取值少的特征，我们可以根据实际情况对分母加上不同的权重来抵消这种偏好，但更普遍的做法是，我们会用所有属性的信息增益来进行初步筛选，然后对得分较高的几个属性进行信息增益率的筛选。
我们通过上述的手段就可以解决决策树最基本的问题，但还会有以下三个问题：
- 目前只能对离散的属性值进行计算，属性值一旦变得连续，特征取值数就会变得非常大，这时候计算信息增益和信息增益率都会失去它原本的意义。
- 对于回归问题，target也会变的连续，属性取值的信息熵和属性取值数的信息熵都会变的无法定义。
- 即便上面两个问题可以忽略，我们利用属性值的信息增益和信息增益率可以不断的延展我们的决策树，直至每一个样本都被划分正确，这样的精细做法必然会带来过拟合，我们该如何在决策树种避免它呢？
这些问题会在我们的下一篇《非参数模型（进阶）》中得到解答。
读芯君开扒
课堂TIPS
• K近邻算法涉及到样本距离的计算，除了我们常见的欧几里得距离，我们可以根据任务的不同，采用不同的距离度量，比如黎曼距离，曼哈顿距离，海明距离。我们使用的距离也可以不进行事先先指定，而是通过度量学习的方法去寻找一个距离，但这样的距离还必须内嵌入相应的学习器中。
• K近邻算法对异常值敏感，对样本的密度要求高，也并没有什么解释性。决策树恰好相反，它对异常值非常鲁棒，并不要求一定做预处理，而且具有很强的解释性，它还可以根据信息增益和信息增益率的准则对特征的重要程度进行排序，构造一颗泛化能力良好的决策树可以帮助我们清楚问题中的关键因素。
• K近邻虽然简单无脑，但可以证明，它的泛化误差不会超过贝叶斯最优分类器的两倍，而决策树在面对特征之间复杂的线性、非线性组合的时候往往无能为力，甚至当分类的问题中类别过多的时候，准确性也会迅速下降。
作者：唐僧不用海飞丝
如需转载，请后台留言，遵守转载规范