Notebooks for Machine Learning Foundations by @hsuantien

• 机器学习基石上 (Machine Learning Foundations)-Mathematical Foundations
• 机器学习基石下 (Machine Learning Foundations)-Algorithmic Foundations

by Hsuan-Tien Lin

《机器学习基石》是国立**大学资讯工程系的 林轩田 老师开设的课程（中文授课）。

该课程旨在从基础的角度介绍机器学习，包括机器学习的哲学、关键理论和核心技术。

从基础角度出发，既能保证学生能够了解机器学习的基本概念，同时对学生基础的要求最少，也能够保证课程不会太枯燥。

（如果从理论角度出发，需要深入掌握各种机器学习理论，花费大量时间，但却不实用； 而如果从技术角度出发，快速介绍多种机器学习方法，但无法清晰理解，难以选择和应用。）

人：

• 观察 -> 学习 -> 技巧
• Observation -> Learning -> Skill

机器：

• 数据 -> 机器学习 -> 技巧
• Data -> Machine Learning -> Skill

• 改进一些表现
• Improve some performance measure

因为用传统的编程方式定义、解决某些问题非常难；但使用机器学习的方法可以让这个问题变得很简单。

• 构建复杂的系统

例子：

• 识别什么是树

其他的例子：

• 控制火星探测车（不了解火星的情况）
• 语音识别（难以定义这个问题的解决方法）
• 高频股市交易（人类无法实现）

1. 存在潜在的模式（exists some underlying patten）

• 这样才存在改进的空间（反例：预测下一个随机数）

2. 无法用简单的编程实现

• 否则没有必要使用机器学习（反例：识别图中是否存在环路）

3. 必须有能够反映这个问题的数据

• 否则无法学习（反例：预测核能是否会毁灭人类）

如果有以上三点，那么用机器学习 有可能 可以解决这个问题；

略

数据输入（Input）：

结果输出（Output）：

目标函数（Target function）：

数据集（Data）：

机器学习算法（Learning algorithm)：

函数集合（Hypothesis set）：

假设函数（Hypothesis <=> Skill）：

机器学习的过程，就是：

• 在符合目标函数的数据上；
• 运用用机器学习算法；
• 从函数集合中；
• 得到假设函数的过程。

机器学习模型是由机器学习算法和函数集合组成。

1. 机器学习 v.s. 数据挖掘（Data Mining）

• 机器学习和数据挖掘可以互相帮助
• 机器学习有时包含在数据挖掘中，数据挖掘的范围更加广泛

2. 机器学习 v.s. 人工智能（Artificial Intelligence）

• 机器学习是实现人工智能的一种方法
• 机器学习也是一种人工智能，人工智能的范围更加广泛

3. 机器学习 v.s. 统计学（Statistics）

• 统计学是实现机器学习的一种方法
• 机器学习更重视计算结构，而统计学更加重视数学的严谨性（当然也损失了很多）

考虑一个简单的分类问题，是否给一个顾客办理信用卡。

假设每个顾客有一系列的特征（Feature），比如年薪、花费、债务等：

计算特征的加权求和作为分数：

如果客户的得分高于某个分数（threshold），则办理信用卡；若低于某个分数，则不办理信用卡。 因此有：

这就是感知机。

简化一下这个公式：

每一种权重向量（ ）就是一个假设函数 （Hypothesis）。

在二维空间中（ ），每一种 可以用一条直线表示，在这个直线上的值为0，直线将平面分为 +1 和 -1 两个部分。因此，感知机也叫线性分类器（linear/binary classifiers）

—— A fault confessed is half redressed.

那么，如何选出最好的目标函数呢？

我们希望得到的假设函数近似等于目标函数：

我们并不知道目标函数，但我们有符合目标函数的数据，因此，至少在这些数据中，这两个函数应该是近似的：

不过，因为目标函数所属的函数集合 可以是无限大的，从中找到我们想要的目标函数非常难。

因此，可以先从函数集合中随意拿出一个函数 （可以用权重的向量 表示）， 然后，在数据中优化这个函数的表现，这就是PLA (Cyclic PLA) 的思路：

在一个循环 t = 0,1,2,3,... 中：

• 找到当前函数判断错误的数据：

• 使用这个数据修正函数（向量求和）：

• 直到每个数据都不出现错误时，循环停止，得到权重向量：

但是，这个算法还有一些问题：

• 算法中的循环不一定会停止
• 算法能够保证在已有的数据中是正确的，但未必在未知数据中也是正确的

• 那么，什么情况下PLA的循环会停止？

数据是线性可分的（Linear Separable）

• 当数据是线性可分的时候，PLA的循环就一定会停止吗？

当数据线性可分时，存在一条线（ ）可以完美区分这个数据集，每一个数据都可以被这条线区分在正确的部分，因此有：

（任意一个数据点的向量表示与分割线法向量的夹角小于90度，向量内积等于向量的长度与夹角cos值的乘积）

我们使用向量内积的方式来查看这个完美的分割线和我们 T 循环中分割线的相似程度。

如果两个向量越相似，他们的向量内积越大。 此外，还需要考虑两个向量的模/长度，如果向量变长，內积也会变大，因此使用单位向量进行内积。 所以，以下公式可以衡量这两个向量的相似程度：

对于分子部分，有：

迭代后有：

对于分母部分，有：

因为只有在某个数据出现错误时，才会使用这个数据更新向量，所以有：

所以，上面的公式可以简化为：

迭代后有：

综上，

其中，

可见两个单位向量的內积会随着 T 的增加而增加，这说明随着PLA的不断循环、更新，两个向量是越来越接近的；

同时，因为两个单位向量內积的最大值为 1，所以 T 不可能无限增加，因此，在数据线性可分时，PLA的循环最终会停下来，找到一个很好的分割线。

不过，PLA仍然有一些问题：

• 需要数据是线性可分的，但是我们并不知道数据是否线性可分

• 数据是线性可分的假设过于强了，很多时候数据不是线性可分的（比如数据有噪声）

• 尽管当线性是可分的时候，PLA会停下来，但是我们并不知道需要多少个循环才能停下（参数中含有未知的 ）

为了解决这些问题，我们首先应该假设噪声应该很小，多数的数据都是线性可分的；

因此我们可以找到一条线，在这个数据集中出现的错误最少：

但是这是一个 NP-hard 问题。

因此，我们修改了一下PLA的算法，这个新算法的思路是用PLA的循环每次找到一个新的分类器（线）时，检查这个分类器在数据中的表现，如果这个新的分类器比（口袋里）以前的分类器表现好，那么就留下这个新的分类器。这个算法叫做 口袋算法（Pocket Algorithm）。