机器学习基石笔记1

阅读量：5272 次

发布时间：2019-06-14

本文共 6369 字，大约阅读时间需要 21 分钟。

机器学习基石笔记1

lecture 1: The Learning Problem

1. 机器学习是什么

通过对数据的经验计算(experience computed)，提升性能度量

3个关键性质

a) 存在一种可以学习的潜在的模式(underlying pattern)

b) 没有明确的可编程的定义

c) 存在和模式相关的数据

2. 机器学习的应用

教育

推荐系统

etc.

3. 机器学习的元素

compenents1

4. 机器学习和其他领域的关系

领域	描述
机器学习	使用数据计算假设g，以此估计目标函数f
数据挖掘	使用大数据，发现有趣的特性
人工智能	计算得到一个具有智能行为的结果
统计学	使用数据从一个未知的分布得出推论

lecture 2: Learning to Answer Yes/No

1. 感知机假设集(hypothesis set)

定义

对于特征 $\textbf{x}=(x_1, x_2, ..., x_d)$，计算每一个特征的权重值，当

$\sum_{i=1}^dw_ix_i > threshold$，$y=1$

$\sum_{i=1}^dw_ix_i < threshold$，$y=-1$

可以将感知机理解为线性(二元)分类器

线性形式公式

$h(\textbf{x}) = sign\Big(\big(\sum_{i=1}^d w_i x_i\big) - threshold\Big) $

向量形式公式

2. 感知机学习 (PLA)

目标：需要一个g，用来估计目标函数f ($g \approx f$)

必要条件：$g \approx f\ on\ D$，理想情况是$g(x_n) = f(x_n) = y_n$

难点：$H$无穷大

思路：从某个 $g_0$ 开始，然后通过数据集 $D$ 纠正它的错误

tips: 之后会用权重向量 $\textbf{W}_0$ 代替 $g_o$

感知机算法

For t = 0, 1...

1) 找到下一个（Next） $\textbf{w}_t$的错误，标记为$(\textbf{x}_{n(t)}, y_{n(t)})$

\[sign\big( \textbf{w}_t^T \textbf{x}_{n(t)} \big) \neq y_{n(t)}\]

2) 尝试通过更新$\textbf{w}_t$的值来更正分类错误：

\[ \textbf{w}_{t+1} \leftarrow \textbf{w}_t + y_{n(t)} \textbf{x}_{n(t)} \]

直到不再有错误出现，返回最后的$\textbf{w}$ (称之为 $\textbf{w}_{PLA} $ )作为函数g

PLA的实现

1) 找到一个$\textbf{w}_t$的错误，标记为$(\textbf{x}_{n(t)}, y_{n(t)})$

\[sign\big( \textbf{w}_t^T \textbf{x}_{n(t)} \big) \neq y_{n(t)}\]

2) 通过更新$\textbf{w}_t$的值来更正分类错误：

\[ \textbf{w}_{t+1} \leftarrow \textbf{w}_t + y_{n(t)} \textbf{x}_{n(t)} \]

直到遍历数据集时不再有分类错误，则返回最后的$\textbf{w}$ (称之为 $\textbf{w}_{PLA} $ )作为函数g

tips: 取下一个样本的操作可以用常规遍历（naive cycle(1, 2, ..., N)），或者预先计算好的随机排序

3. Guarantee of PLA

线性可分

如果PLA终止了且不再有分类错误，那么存在w能够线性划分数据集D而没有分类错误，那么这样的数据集D是线性可分的

PLA Fact

$\textbf{w}_t$在更新后与$\textbf{w}_f$更加接近（aligned with）

$\textbf{w}_t$不会增长得过快

从$\textbf{w}_o = 0$开始，经过了T次的更新以后：

\[ \frac{\textbf{w}_f^T}{\lVert \textbf{w}_f \lVert} \frac{\textbf{w}_t}{\lVert \textbf{w}_t \lVert} \ge \sqrt{T} · constant\]

$constant = \displaystyle\frac{\rho}{R}$，其中$\rho = min \ y_n\frac{\textbf{w}_f^T}{\lVert \textbf{w}_f \lVert} \textbf{x}_n$，$R = max \lVert \textbf{x}_n \lVert^2$

向量标准化后，其乘积会小于等于1，且在更新了T次后，有下界存在。

4. 更多关于PLA的知识

PLA

只要数据集线性可分，并且通过分类错误更新w，那么

$\textbf{w}_f$和$\textbf{w}_t$的内积会增长很快，而$\textbf{w}_t$的长度则增长缓慢

PLA的分类边界（PLA "lines"）越来越接近$\textbf{w}_f$，并最终停止更新（halt）

优点

易于实现，速度快，能在任意的维度下工作

缺点

预设数据集是线性可分的，但该特性是事先不知道的（如果知道了，就不需要 PLA了=。=）

不能完全确定迭代步数（$\rho$取决于$\textbf{w}_f$）
- 尽管实际上会很快

非线性可分

调整PLA方法，以得到一个足够好的g

Pocket算法

初始化pocket 权重为$\hat{\textbf{w}}$

1) 找到一个（随机的）$\textbf{w}_t$的错误，标记为$(\textbf{x}_{n(t)}, y_{n(t)})$

\[sign\big( \textbf{w}_t^T \textbf{x}_{n(t)} \big) \neq y_{n(t)}\]

2) 尝试通过更新$\textbf{w}_t$的值来更正分类错误：

\[ \textbf{w}_{t+1} \leftarrow \textbf{w}_t + y_{n(t)} \textbf{x}_{n(t)} \]

3) 如果$\textbf{w}_{t+1}$的分类错误比$\hat{\textbf{w}}$少，则将$\hat{\textbf{w}}$更新为$\textbf{w}_{t+1}$，直到足够的迭代次数，返回最后的$\hat{\textbf{w}}$ (称之为 $\textbf{w}_{pocket} $ )作为函数g