美文网首页
【林轩田机器学习基石学习笔记】When machine can

【林轩田机器学习基石学习笔记】When machine can

作者: 砥砺前行的人 | 来源:发表于2021-12-11 16:13 被阅读0次

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

前言

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

什么时候机器可以学习

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


机器学习

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

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

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

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

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

形式化机器学习问题

机器学习的形式化表示
  • 输入: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 即为 -thresholdX_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 上逐步纠正优化。针对感知机学习算法,有如下过程:

  1. 初始化 w_0 为 0,找出此时分错的数据集中的一个,表示为(x_{n(t)}, y_{n(t)}),其中 t 表示第几轮迭代优化:
    sign(w^T_tx_{n(t)}) \neq y_{n(t)}
  2. 尝试纠正错误
    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。而原先罐子中的橘色与绿色的比例可能为 \mu1 - \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]

代入 霍夫丁不等式:


代入霍夫丁不等式

the statement E_{in}(h) = E_{out}(h) is probably approximately correct (PAC)

E_{in}(h) \approx E_{out}(h) 并且E_{in}(h) 很小时,可以推论出 E_{out}(h) 也很小,此时 h \approx f,因为 E可以看做出错的概率

所以,如果在 H 中选择出的 h 使得E_{in}(h) 很小时,那么 g = f PAC。

learning

如果假设空间 H 有M(有限)个假设,N足够大,通过算法 A 无论任何g,E_{in}(h) \approx E_{out}(h)。如果 A 找到的 E_{in}(g) \approx 0,则 E_{out}(g) \approx 0 APC

相关文章

网友评论

      本文标题:【林轩田机器学习基石学习笔记】When machine can

      本文链接:https://www.haomeiwen.com/subject/bcnhfrtx.html