什么是机器学习（Machine Learing）

首先我们应该弄清楚什么是学习。

learning: acquiring skill with experience accumulated from observations

machine learning: acquiring skill with experience accumulated/computed from data

相较于学习而言机器学习是通过观察数据从而获得技能。

具体来说：skill便是在某些性能指标（improving some performance measure）。所以说机器学习的定义可以具体为：

machine learning：improving some performance measure with experience computed from data

但是同时由于机器学习又经常用于为复杂问题构建解决方案，即可以用于复杂系统的构建，所以机器学习的另一种定义为：

machine learning：an alternative route to build complicated systems

当然如此工具，有三个关键点（Key Essence of Machine Learning）：

1. exists some ‘underlying pattern’ to be learned
   —so ‘performance measure’ can be improved
2. but no programmable (easy) definition
   —so ‘ML’ is needed
3. somehow there is data about the pattern
   —so ML has some ‘inputs’ to learn from

其中第一点和第三点是进行机器学习的前提条件，第二点是为防止机器学习滥用，即简单&可人为处理的问题不需要机器学习。

英语单词学习：
navigate 使通过，oriented 标定方向的，scale 规模衡量，poisoning 中毒，properly 适当非常，likeliness 可能

本课总结：Machine-Learing is everywhere ❗

学习问题的基本形式 （Formalize the Learning Problem）

基本符号（Basic Notations）

属性（attribute）或特征（feature）：反映事件或对象在某方面的表现或性质的事项。属性张成的空间又叫样本空间（sample space）或属性空间（attribute space）: \(\mathcal{X}\)。

示例（instance）或样本（sample）或输入（input）： \(\boldsymbol{x}_{i}=\left(x_{i 1}x_{i 2} ; \ldots ; x_{i d} \right)\)，是 \(d\) 维样本空间 \(\mathcal{X}\) 中的一个向量（特征向量），其中\(x_{ij}\)是\(x_i\)在第\(j\)个属性上的取值， \(d\) 称为样本 \(x_{i}\)的维数(dimensionality)。

标记（label）或输出（output）：\(y_i\)，关于示例\(x_i\)结果的信息。标记张成的空间又叫标记空间（label space) : \(\mathcal{Y}\)。

样例（example）：\(\left(x_{i}, y_{i}\right)\)，拥有标记的示例。

目标函数（target function）：未知的需要学习的模式（unknown pattern to be learned)，前面提及到的skill的终极模式，即属性和标记之间的真实映射关系：\(f(x) = y\)。

数据集（data set）：一组关于某事件或对象的记录（样例）的集合，数学表示为\(D=\left\{\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots, \boldsymbol{x}_{m}\right\}\)，分为训练集(training set)和测试集(test set)。

模型（model）或假设（hypothesis）：学得模型对应了关于数据的某种潜在的规律，通过对数据观察学习到的属性和标记之间的近似映射关系：\(h:\mathcal{X} \rightarrow \mathcal{Y}\)；这种潜在规律自身，则称为“真相”或“真实”（ground-truth），学习过程就是为了找出或逼近真相。有时将模型称为“学习器”（learner），可看作学习算法在给定数据和参数空间上的实例化。所有的\(h\)组成了假设函数集\(H\)，其中伪最优的假设函数（‘best’ hypothesis)将被叫做 \(g\)。

学习（learning）或训练（training）：从数据中学得模型的过程，这个过程通过执行某个学习算法（learning algorithm）\(\mathcal{A}\)来完成。

测试（testing）：学得模型后，使用其进行预测的过程，被预测的样本称为测试样本（testing sample）。

学习流程（Learning Flow）

上图便是机器学习的基本流程图。其中learning algorithm \(\mathcal{A}\)便是在所有的假设函数函数选取出 \(g\)（‘best’ hypothesis) (\(\mathcal{A}\) takes \(\mathcal{D}\) and \(\mathcal{H}\) to get \(\mathcal{g}\))。所以该流程图又可画为：

从该流程图出发可以获得机器学习的最终定义为：从数据出发计算出接近于目标函数 \(f\) 的伪最优假设函数 \(g\) (use data to approximate target)，即\(g \approx f\)。

机器学习与数据挖掘/人工智能/统计学

数据挖掘/人工智能/统计学的定义如下

Data Mining ：use (huge) data to find property that is interesting.

Artificial Intelligence ：compute something that shows intelligent behavior

Statistics ：use data to make inference about an unknown process

简单来说数据挖掘虽然有时跟机器学习很相似，但是在实际中分析却很不同，当然数据挖掘有时对机器学习很有帮助，机器学习是实现人工智能的一种方法，而统计学有许多工具用于实现机器学习的方法。

如何实现二分类（Binary Classification）

感知机（Perceptron)

以是否发放信用卡为例，在生活中最简单的方式便是根据一个人的属性：年龄，参加工作的时间，薪资和当前的信誉度对一个人进行评判。而感知机则是利用全部属性的线性组合进行计算是否发卡的分数，而每个属性的系数则是每个属性的所占比重。

property	value
age	23 years
annual salary	NTD 1,000,000
year in job	0.5 year
current debt	200,000

这里属性就是前面所提到的特征features of customer构成这个人的特征向量→ \(\mathbf{x}=\left(x_{1}, x_{2}, \cdots, x_{d}\right)\) ，而每个属性或特征所占的比重weight构成这个人的比重向量 → \(\mathbf{w}=\left(w_{1}, w_{2}, \cdots, w_{d}\right)\)。这样便可以根据两者计算分数，进而使用阈值判断决定是否进行发卡。

\[\text { score } = \sum_{i=1}^{d} w_{i} x_{i}\\ \begin{array}{l}\text{approve credit if} \quad & \text { score } > \text{threshold}\\ \text{deny credit if} \quad & \text { score } < \text{threshold}\end{array} \]

那么可以将上述问题总结为一个线性假设函数（linear formula） \(h \in \mathcal{H}\)：

\[h(\mathbf{x})=\operatorname{sign}\left(\left(\sum_{i=1}^{d} w_{i} x_{i}\right)-\text { threshold }\right) \]

这里的sign(x)表示的是取变量符号的函数，当x小于零取-1，当x大于零取1。

 那么假设函数的输出空间即标记空间可以表示为$\mathcal{Y}:\{+1(\text { good }),-1(\text { bad })\}, 0 \text{ ignored}$ 。而这便是感知机的基本数学形式，而感知机名字的由来是由于历史原因。

为了简化公式这里令\(w_0 = 1 , x_0 = \text{threshold}\)，那么可以将上述的两个特征向量和比重向量改写为 \(\mathbf{x}=\left(x_{0},x_{1}, x_{2}, \cdots, x_{d}\right)\) ， \(\mathbf{w}=\left(w_{0},w_{1}, w_{2}, \cdots, w_{d}\right)\)。那么该假设函数可以改写为：

\[h(\mathbf{x})=\operatorname{sign}\left(\mathbf{w}^{T}\mathbf{x}\right) \]

那么感知机在二维空间 \(\mathbb{R}^{2}\) 可写为：

\[h(\mathbf{x})=\operatorname{sign}\left(w_{0}+w_{1} x_{1}+w_{2} x_{2}\right) \]

其表现如下图所示，其中标签y的表现形式为：o (+1), × (-1)，而上述假设函数的表现形式便是lines (or hyperplanes in \(\mathbb{R}^{2}\) ，二维空间的超平面)，而理想状态下正负样本则分别在其两侧（positive on one side of a line, negative on the other side）。

可见感知机便是简单的线性二分类器。

感知机学习算法（PLA）

理论分析

感知机模型已经建立，那么根据机器学习流程图，便需要一个学习算法（Learning Algorithm) \(\mathcal{A}\) 选取假设函数使得 \(g \approx f \text{ on } \mathcal{D}\) ，理想状态下是\(g(\mathbf{x}_n)=f(\mathbf{x}_n)=y_n\)。但是问题是假设函数集\(\mathcal{H}\)是无穷大（infinite size）的。

一个思路是从一个初始假设函数 \(g_0\) （或\(\mathbf{w}_0\)，因为由于感知机本身的特点，\(\mathbf{w}_i\)便可以代表\(\mathbf{g}_i\)）开始迭代，并且纠正（correct）该假设函数在 \(\mathcal{D}\) 上犯得分类错误，而感知机学习算法（Perceptron Learning Algorithm）便是如此实现的。

PLA实现步骤如下：

For \(t=0,1, \ldots\)

• find a mistake of \(\mathbf{w}_{t}\) called \(\left(\mathbf{x}_{n(t)}, y_{n(t)}\right)\)

\[\operatorname{sign}\left(\mathbf{w}_{t}^{T} \mathbf{x}_{n(t)}\right) \neq y_{n(t)} \]

• (try to) correct the mistake by

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

until no more mistakes return last \(\mathbf{w}\) (called \(\mathbf{w}_{\mathrm{PLA}}\) ) as \(g\).

将向量相加操作在二维平面可表示为：

知识回顾：

• 向量的叉积：\(a \times b = |a| |b| \sin (a,b)\)
• 向量的点积：\(a \cdot b = |a| |b| \sin (a,b) = a^{T}b\)

所以当\(y_n > 0, \mathbf{w}_n^{T}\mathbf{x}_n < 0\)时想使\(\mathbf{w}_n^{T}\mathbf{x}_n\)向\(y_n\)逼近，那么\(\mathbf{w}_n\) 和 \(\mathbf{x}_n\) 的夹角应该由钝角转为锐角，即旋转\(\mathbf{w}_n\) 向 \(\mathbf{x}_n\) 靠近，那么使用第二步公式便可以实现，反之同理可证。

引用名言：

知错能改，善莫大焉。

A fault confessed is half redressed.