slide 下载地址：https://www.csie.ntu.edu.tw/~htlin/course/mlfound17fall/
bilibili 视频地址：https://www.bilibili.com/video/BV1Cx411i7op

前言

机器学习是一门理论与应用相结合的技术。这门课从基础（基石）开始切入，逐步建立起对于机器学习的宏观认知。

什么时候机器可以学习

生活中的学习是从观察出发（听觉，视觉等），通过一个学习的过程获得某一方面的技巧，而机器学习下是电脑通过数据获得某一方面的技巧，技巧就是增进某一方面的性能表现（例如预测准确率等）。

机器学习

机器学习是构建复杂系统的另一种途径。

下面是一些机器学习的使用场景：

火星上的导航
语音和视觉辨识
股票高频交易
个性化服务

如果问题拥有以下三个场景，也许可以使用机器学习：

有某些性能目标可以被提升
通常用显式编程无法解决
拥有数据作为学习输入

形式化机器学习问题

机器学习的形式化表示

输入： $x \in X$
输出： $y \in Y$
需要学习的模式（目标函数）： $f: X \xrightarrow{} Y$
数据（训练样本）： $D = {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$
假设空间： $g: X \xrightarrow{} Y$

目标 f 通常是不可知的，但是我们希望 g 可以尽可能的和 f 相似

引入假设空间

$g \in H = {h_k}$ ，对于银行判断是否向某个用户派发信用卡，可以有以下一些模型：

$h_1$ ：收入大于1w
$h_2$ ：每月使用信用卡超过2w
$h_3$ ：工龄大于2年

$H$ 可以包含好的和坏的假设，通过机器学习算法选择最好的一个 g。机器学习就是一个选择算法 $A$ 和从 $H$ 中选择 $g$ 的过程。

感知机(线性分类器)

信用卡租赁

左边栏目为客户的特征，而右栏目为特征的具体数值，这里是一条数据。对于 $x = (X_1, X_2,...,X_d)$ 客户特征，通过对于每一个特征的加权求和，如果 $\sum_{i=1}^{d} W_iX_i > threshold$ ，则派发信用卡，如果 $\sum_{i=1}^{d} W_iX_i < threshold$ ，则不派发信用卡。对于 $Y: \{+1(\text {good}),-1(\text {bad})\}$ ，有以下 $h \in H$

$h(X) = sign((\sum_{i=1}^{d} W_iX_i ) - threshold)$
$= sign((\sum_{i=1}^{d} W_iX_i ) + (-threshold)(+1))$
$= sign(\sum_{i=0}^{d} W_iX_i )$
$= sign(W^TX )$

上述的 $W_0$ 即为 $-threshold$ ， $X_0$ 为 $+1$

二维感知器举例

x1, x2 分别代表数据的不同特征，圈圈和叉叉表示label的+1和-1，假设空间中的 h 表示一条直线，将不同特征的数据分开。

选择合适的 g

如下是我们目前的期望：

想要 $g \approx f$ ，但是 f 通常是未知的。
希望在数据集D上， $g(X_n) \approx f(X_n) = y_n$
难点： $H$ 有无穷多个， $g \in H$

一种可行的方法：从 $g_0$ 开始，在数据集 D 上逐步纠正优化。针对感知机学习算法，有如下过程：

初始化 $w_0$ 为 0，找出此时分错的数据集中的一个，表示为 $(x_{n(t)}, y_{n(t)})$ ，其中 t 表示第几轮迭代优化：
$sign(w^T_tx_{n(t)}) \neq y_{n(t)}$
尝试纠正错误
$w_{t+1} = w_t + y_{n(t)}x_{n(t)}$
直到不再出现错误，将此时的 w 作为 g

线性可分

线性可分性

设 $R=max||x_i||，\gamma = min(y_i(w_{f} x_{i}+b_{f}))$ ，则回归次数 k 满足以下公示：
$k \leq \frac {R^2}{\gamma^2}$

但往往在拿到数据集的时候无法判断是否线性可分，有可能是因为存在细小的 Noise，所以我们需要寻找一个犯错误最小的 g：

但这个公式是一个 NP-hard 问题，是无法求解的。

口袋算法（Pocket Algorithm）

基本算法如下：

找到一个随机的错误样本
修正错误 $w_{t+1} = w_t + y_{n(t)}x_{n(t)}$
在自觉足够的时候停止

输出空间 y

二元分类： $y = \{-1,+1\}$ ，是非题，例如感知器算法

垃圾邮件分类
是否派发信用卡
是否确诊癌症
回答是否正确

多元分类： $y = \{1，2，3，...，k\}$ ，二元分类是 k 为 2的多元分类特殊情况。

回归分析： $y \in R$ 或者 $y \in [lower, upper]$
结构化学习：输出具有结构化

核心是二元分类和回归分析

监督学习，非监督学习，半监督学习：

分类

常见非监督学习：

分群
密度估计
离群分析

常见半监督学习（有标记的很少）：

人脸识别
药物数据

利用未标记的数据来避免“昂贵”的标记成本

增强学习：通过奖励和惩罚诱导学习系统做出预期的行为

总结来说：

监督式学习: 所有 $y_n$
非监督学习: 没有 $y_n$
半监督学习: 一部分 $y_n$
增强学习:奖励和惩罚

不同的 $f \xrightarrow{} (x_n, y_n)$

Batch：批量学习。一次性喂给所有数据，学习得到一个固定的模型。
Online：线上学习。通过顺序接收数据实例 improve。
Active：主动学习。机器能够主动问问题，适用于标记极其昂贵。

不同的 X

Concrete 特征：人对数据集的分析。
Raw 特征：数据本身，例如图片的每一个像素值向量，语音的原始信号。
Abstract 特征：没有实际意义，例如用户ID，视频ID，对机器学习没有直接帮助

学习的可行性

先进行一个小游戏

找规律

无论你说 $\{+1,-1 \}$ 中的任何一个，出题人都可以用另一对立的规则说你的答案是错的。

再看看下一个例子：

在数据集中，g 完全可以和 f 表现一直，但在数据集之外，一定有出错的可能，仿佛无法学到 f。

没有免费的午餐定理

机器学习最核心的问题，在于利用数据集，得出模型，在数据集以外也能预测正确。

推论未知事物

假设需要从一个拥有橘色和绿色的罐子中计算各自的比例：

我们可以打乱后随即取出10个，计算橘色的可能性记为 $\nu$ ，则绿色的可能性为 $1 - \nu$ 。而原先罐子中的橘色与绿色的比例可能为 $\mu$ 和 $1 - \mu$ 。

有可能出现一次抽出的都是橘色，或者都是绿色，但这个概率很小。

霍夫丁不等式

Hoeffding 不等式的简介表示如下：
$P[|\nu -\mu| > \epsilon] \leq 2 exp(-2 \epsilon^2 N)$

当 N 很大，也就是采样更多， $\nu$ 可能接近 $\mu$ ，在 $\epsilon$ 的可容忍误差范围内。

the statement $\nu = \mu$ is probably approximately correct (PAC)

如果用 learing 对比从罐子中取出球的过程：

learning VS bin

如果 N很大并且 $x_n$ 符合 i.i.d ，可以通过 $P[h(x_n) \neq y_n]$ 来推断 $P[h(x) \neq f(x)]$

增加从全集中取样形成数据集

对于任何固定的 h，大概可以推断：
$\text {unknown } E_{out}(h) = \varepsilon_{x \sim P} [h(x) \neq f(x)]$
$\text {by known } E_{in}(h) = \frac {1} {N} \sum^{N}_{n=1} [h(x_n) \neq y_n]$