【机器学习1】

记录的集合：数据集

由于空间中的每个点对应一个坐标向量，我们也把一个示例称为一个“特征向量”。

非显著式编程的做法

收益函数

1998 Tom MitShell

第一本成熟的教科书：MACHINE LEARNING

典型的最优化问题

为数据打标签（独特行业）

监督学习
强化学习（与环境互动）

非监督学习

需要假设：同一类的训练数据在空间中距离更近->样本的空间信息->设计算法将其分成两类

非监督学习算法包括：

聚类
EM算法（Expectation-Maximization algorithm）
主成分分析

半监督学习

少量的标注数据大量未标注数据

监督学习（界限模糊）

分类（离散）
回归（连续）

主要是解决分类问题

1.提取特征

2.特征选择

特征空间

只要画出了区分的曲线，就算完成了机器学习

维度

标准

没有免费午餐定理

1995 D.H.Wolpert

在设计机器学习算法的时候有一个假设：

在特征空间上距离接近的样本，他们属于同一个类别的概率会更高。

机器学习的本质：

通过有限的已知数据，能在复杂的高维特征空间中预测未知的样本

没有放之四海而皆准的算法

支持向量机（线性可分定义）

Vladimir Vapnik

SVM的主要思想可以概括为两点:

它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。

它基于结构风险最小化理论之上在特征空间中构建最优超平面，使得学习器得到全局最优化，并且在整个样本空间的期望以某个概率满足一定上界。

用数学严格定义线性可分

用向量形式定义

二维特征空间结果

基于最优化理论

寻找最优分类直线

该直线分开了两类
该直线最大化间隔（margin）
该直线处于间隔的中间，到所有支持向量距离相等

证明：在线性可分条件下，有且只有唯一一条直线，满足上面三个条件

quickhull

最优分类超平面

该超平面分开了两类
该超平面有最大化间隔
该超平面处于间隔的中间，到所有支持向量距离相等

凸优化问题

算法的超参数：人为事先设定的参数

不断变化C的值

松弛变量

对于线性不可分情况，需适当放松限制条件

线性模型的表现力是不够的

所以要扩大可选函数范围。

非线性 -> 线性

低维 ->高维

用线性超平面进行分类

算法模型的自由度

数据向量维度一旦变得很高，我们怎么办？

答案是检查凸包（convex hull）是否相交。

Q:什么是凸包呢？

A:简单说凸包就是一个凸的闭合曲线（曲面），而且它刚好包住了所有的数据。

如何高效的找到一组数据的凸包？

如何高效的判断两个凸包是否重合？

网友Darren Engwirda 给出了很好的建议：

There are efficient algorithms that can be used both to find the convex hull (theqhull algorithm is based on anO(nlog(n)) quickhull approach I think), and to perform line-line intersection tests for a set of segments (sweepline atO(nlog(n))), so overall it seems that an efficient O(nlog(n)) algorithm should be possible.

This type of approach should also generalise to general k-way separation tests (where you havek groups of objects) by forming the convex hull and performing the intersection tests for each group.

It should also work in higher dimensions, although the intersection tests would start to become more challenging...

简单说，他的建议就是用quickhull算法来找到数据的凸包，sweepline算法判断凸包边缘是否有相交，两个步骤的复杂度都是O(nlogn)。

其中quickhull已经在软件包qhull(http://www.qhull.org/)实现了。

Vladimir Naumovich Vapnik

不用知道具体形式

核函数

kernel其实就是帮我们省去在高维空间里进行繁琐计算的“简便运算法”。甚至，它能解决无限维空间无法计算的问题！因为有时f(·)会把n维空间映射到无限维空间去。

预测 $x$ 的值，那就在训练集 $X$ 中寻找与 $x$ 相似的样本，再把这些样本的值加权作为预测值。

这里有两个问题：

如何度量样本之间的相似性？
如何加权？

一般来说，相似性越高，权重越大。下面先看三个例子：

k近邻。一般用欧式距离寻找离 $x$ 最近的 $k$ 个点，然后把对应的 $y$ 等权重加权作为预测值。距离越近，相似度越高。顺带说一句，k近邻是一个hard threshold的思想，这和主成分回归的思想差不多。
Nadaraya-Watson估计。在非参数估计中经常看到，距离越近的点，权重越大。