本文主要向大家介绍了机器学习入门之《机器学习基石》——学习笔记，通过具体的内容向大家展现，希望对大家学习机器学习入门有所帮助。

一，什么是机器学习？

使用Machine Learning 方法的关键：

1， 存在有待学习的“隐含模式”

2， 该模式不容易准确定义（直接通过程序实现）

3， 存在关于该模式的足够数据

image.png

这里的f 表示理想的方案，g 表示我们求解的用来预测的假设。H 是假设空间。

通过算法A， 在假设空间中选择最好的假设作为g。

选择标准是 g 近似于 f。

image.png

上图增加了"unknown target function f: x->y“， 表示我们认为训练数据D 潜在地是由理想方案f 生成的。

机器学习就是通过DATA 来求解近似于f 的假设g。

二， 机器学习与数据挖掘、人工智能、统计学的关系

1， Machine Learning vs. Data Mining

数据挖掘是利用（大量的）数据来发现有趣的性质。

1.1 如果这里的”有趣的性质“刚好和我们要求解的假设相同，那么ML=DM。

1.2 如果”有趣的性质“和我们要求的假设相关，那么数据挖掘能够帮助机器学习的任务，反过来，机器学习也有可能帮助挖掘（不一定）。

1.3 传统的数据挖掘关注如果在大规模数据（数据库）上的运算效率。

目前来看，机器学习和数据挖掘重叠越来越多，通常难以分开。

2， Machine Learning vs. Artificial Intelligence(AI)

人工智能是解决（运算）一些展现人的智能行为的任务。

2.1 机器学习通常能帮助实现AI。

2.2 AI 不一定通过ML 实现。

例如电脑下棋，可以通过传统的game tree 实现AI 程序；也可以通过机器学习方法（从大量历史下棋数据中学习）来实现。

3，Machine Learning vs. Statistics

统计学：利用数据来做一些位置过程的推断（推理）。

3.1 统计学可以帮助实现ML。

3.2 传统统计学更多关注数学假设的证明，不那么关心运算。

统计学为ML 提供很多方法/工具（tools）。

第二讲： Perceptron-感知机 (台湾国立大学机器学习基石）

Learning to Answer Yes/No （二值分类）

一, Perceptron

x = (x1, x2, ..., xd) ---- features

w = (w1, w2, ..., wd) ---- 未知（待求解）的权重

对于银行是否发送信用卡问题：

image

perceptron 假设：

image

sign 是取符号函数， sign(x) = 1 if x>0, -1 otherwise

向量表示：

image

感知机（perceptron）是一个线性分类器(linear classifiers）。

线性分类器的几何表示：直线、平面、超平面。

二， Perceptron Learning Algorithm (PLA)

感知机求解（假设空间为无穷多个感知机；注意区分下面的普通乘法和向量内积，内积是省略了向量转置的表示，因为豆瓣不支持公式。。。）

初始w = 0 （零向量）。

第一步：找一个分错的数据（xi, yi）， sign(w*xi) != yi；

第二步：调整w 的偏差，w = w + yi*xi；

循环第一、二步，直到没有任何分类错误， 返回最后得到的w。

实际操作时，寻找下一个错误数据可以按照简单的循环顺序进行（x1, x2, ..., xn）；如果遍历了所有数据没有找到任何一个错误，则算法终止。注：也可以预先计算（如随机）一个数据序列作为循环顺序。

以上为最简单的PLA 算法。没有解决的一个基本问题是：该算法不一定能停止！

三， PLA 算法是否能正常终止

分两种情况讨论：数据线性可分；数据线性不可分。

image

注意PLA 停止的条件是，对任何数据分类都正确，显然数据线性不可分时PLA 无法停止，这个稍后研究。

1， 我们先讨论线性可分的情况。

数据线性可分时，一定存在完美的w(记为wf)， 使得所有的(xi, yi), yi = sign(wf*xi).

可知：

image

下面证明在数据线性可分时，简单的感知机算法会收敛。

image

而且量向量夹角余弦值不会大于1，可知T 的值有限。由此，我们证明了简单的PLA 算法可以收敛。

四，数据线性不可分：Pocket Algorithm

当数据线性不可分时（存在噪音），简单的PLA 算法显然无法收敛。我们要讨论的是如何得到近似的结果。

我们希望尽可能将所有结果做对，即：

image

寻找wg 是一个NP-hard 问题！

只能找到近似解。

Pocket Algorithm

image

与简单PLA 的区别：迭代有限次数（提前设定）；随机地寻找分错的数据（而不是循环遍历）；只有当新得到的w 比之前得到的最好的wg 还要好时，才更新wg（这里的好指的是分出来的错误更少）。

由于计算w 后要和之前的wg 比较错误率来决定是否更新wg， 所以pocket algorithm 比简单的PLA 方法要低效。

最后我们可以得到还不错的结果：wg。

第三讲： 机器学习的分类学 (台湾国立大学机器学习基石）

机器学习方法的分类学，通过不同的分类标准来讨论。

一，根据输出空间来分类。

1， 分类(classification)

1.1 二值分类 (binary classification)：输出为 {+1， -1}。

1.2 多值分类 (multiclass classification)：输出为有限个类别，{1, 2, 3, ... , K}

2， 回归(regression)

输出空间：实数集 R ， 或 区间 [lower, upper]

3， 结构学习（structured learning）：典型的有序列化标注问题

输出是一个结构（如句子中每个单词的词性）， 可以成为 hyperclass， 通常难以显示地定义该类。

需要重点研究的是二值分类和回归。

二， 根据数据标签(label) 情况来分类。

1， 有监督学习(supervised learning)：训练数据中每个xi 对应一个标签yi。

应用：分类

2， 无监督学习(unsupervised learning)：没有指明每个xi 对应的是什么，即对x没有label。

应用：聚类，密度估计(density estimation)， 异常检测。

3， 半监督学习(semi-supervised learning)：只有少量标注数据，利用未标注数据。

应用：人脸识别；医药效果检测。

4， 增强学习(reinforcement learning)：通过隐含信息学习，通常无法直接表示什么是正确的，但是可以通过”惩罚“不好的结果，”奖励“好的结果来优化学习效果。

应用：广告系统，扑克、棋类游戏。

总结：有监督学习有所有的yi；无监督学习没有yi；半监督学习有少量的yi；增强学习有隐式的yi。

三， 根据不同的协议来分类。

1， 批量学习 - Batch learning

利用所有已知训练数据来学习。

2， 在线学习 - online learning

通过序列化地接收数据来学习，逐渐提高性能。

应用：垃圾邮件， 增强学习。

3， 主动学习 - active learning

learning by asking：开始只有少量label, 通过有策略地”问问题“ 来提高性能。

比如遇到xi, 不确定输出是否正确，则主动去确认yi 是什么，依次来提高性能。

四， 通过输入空间来分类。

1， 离散特征 - concrete features

特征中通常包含了人类的智慧。例如对硬币分类需要的特征是（大小，重量）；对信用分级需要的特征是客户的基本信息。这些特征中已经蕴含了人的思考。

2， 原始特征 - raw features

这些特征对于学习算法来说更加困难，通常需要人或机器（深度学习，deep learning）将这些特征转化为离散(concrete)特征。

例如，数字识别中，原始特征是图片的像素矩阵；声音识别中的声波信号；机器翻译中的每个单词。

3， 抽象特征 - abstract features

抽象特征通常没有任何真实意义，更需要认为地进行特征转化、抽取和再组织。

例如，预测某用户对电影的评分，原始数据是(userid, itemid, rating)， rating 是训练数据的标签，相当于y。这里的(userid, itemid)本身对学习任务是没有任何帮助的，我们必须对数据所进一步处理、提炼、再组织。

总结：离散特征具有丰富的自然含义；原始特征有简单的自然含义；抽象特征没有自然含义。

原始特征、抽象特征都需要再处理，此过程成为特征工程(feature engineering)，是机器学习、数据挖掘中及其重要的一步。离散特征一般只需要简单选取就够了。

image

第四讲：学习的可行性分析 (台湾国立大学机器学习基石）

机器学习的可行性分析。

一， 第一条准则： 没有免费的午餐！(no free lunch !)

给一堆数据D， 如果任何未知的f （即建立在数据D上的规则）都是有可能的，那么从这里做出有意义的推理是不可能的！！ doomed !!

如下面这个问题无解（或者勉强说没有唯一解）：

image

下面这题也是如此：

image

再来看个”大神“的例子：

已知 (5, 3, 2) => 151022, 求 (7, 2, 5) => ？

鬼才知道！！ 即使给你更多已知数据也白搭！因为有多种自造的规则可以解释已知数据。

瞬间感觉小学中学做过的好多题（尤其是奥赛类的）都是扯淡的有木有！！不同的理解就会有不同的答案。

如何解决上述存在的问题？ 答：做出合理的假设。

二， 关于罐子里选小球的推论（概论&统计）

这里主要去看原课件吧。

比较重要的一个霍夫丁不等式(Hoeffding’s Inequality) 。

霍夫丁不等式

这里v 是样本概率；u 是总体概率。

三，罐子理论与学习问题的联系

image

对于一个固定的假设h， 我们需要验证它的错误率；然后根据验证的结果选择最好的h。

image

四，Real Learning

面对多个h 做选择时，容易出现问题。比如，某个不好的h 刚好最初的”准确“ 的假象。

随着h 的增加，出现这种假象的概率会增加。

发生这种现象的原因是训练数据质量太差。

image

对于某个假设h， 当训练数据对于h 是BAD sample 时， 就可能出现问题。

因此，我们希望对于我们面对的假设空间，训练数据对于其中的任何假设h 都不是BAD sample。

image

所以，当假设空间有限时（大小为M）时， 当N 足够大，发生BAD sample 的概率非常小。

此时学习是有效的。

当假设空间无穷大时（例如感知机空间），我们下一次继续讨论。（提示：不同假设遇到BAD sample 的情况会有重叠）

第五讲： 学习的可行性分析（一些概念和思想） (台湾国立大学机器学习基石）

Training versus Testing

1，回顾：学习的可行性？

最重要的是公式：

image

（1） 假设空间H有限（M），且训练数据足够大，则可以保证测试错误率Eout 约等于训练错误率Ein；

（2）如果能得到Ein 接近于零，根据（1），Eout 趋向于零。

以上两条保证的学习的可能性。

可知，假设空间H 的大小M 至关重要，我们接下来会力求找一个H 大小的上界。

M存在重要的trade-off 思想：

（1）当M 很小，那么坏数据出现的概率非常小（见第四讲分析），学习是有效的；但是由于假设空间过小，我们不一定能找到一个方案，可以使训练误差接近零；

（2）反之，若M 很大，坏数据出现的概率会变大。

若假设空间无限大（比如感知机），学习一定是无效的吗？这门在下面力图回答这个问题。

2， 假设空间H 大小：M

根据上面的公式，当M 无限大时是无法有效学习的；主要是我们在计算M 是通过UNION BOUND 的方式，这样得到的上界太宽松了；实际上，由于不同假设下发生坏事情是有很多重叠的，其实我们可以得到比M小得多的上界。

我们希望将这么多的假设进行分组，根据组数来考虑假设空间大小。

接下来的讨论需要脑子转个弯儿，去看台大林轩田的视频和讲义应该更清楚些，我这里解释的看不懂没关系~

后面的讨论都是针对批量的二值分类问题。

这个思想的关键是，我们从有限个输入数据的角度来看待假设的种类。

（1）最简单的情形，只有一个输入数据时，我们最多只有两种假设：h1(x) = +1 or h2(x) = -1 。

（2）输入数据增加到两个，最多可以有四种假设：

h1(x1)=1, h1(x2)=1;

h2(x1)=-1, h2(x2)=1;

h3(x1)=1, h3(x2)=-1;

h4(x1)=-1, h4(x2)=-1.

依次类推， 对于k 个输入数据，最多有2^k 种假设。

上面阐述的是理想、极端情况，实际上，在实际学习中我们得不到如此之多的假设。例如，对于2维感知机（输入为平面上的点），输入数据为3个时，下面这种假设是不存在的：

image

（圆圈和叉代表两种不同分类，这种情形也就是线性不可分）。

我们尝试猜测，当k 很大时，有效假设的数量远小于 2^k ?

定义"dichotomy": hypothesis 'limited' to the eyes if x1, x2, ..., xn

也就是相当于我们前面描述的，从输入数据的角度看，有效假设的种类。

输入规模为N时，dichotomies 的一个宽的上界是 2^N.

后面这部分内容，如果想理解清楚，还是建议看林轩田的讲解。:-)

定义关于数据规模N 的生长函数(growth function)：数据规模为N 时，可能的dichotomy 的数量，记为m(N)。

下面列举几种生长函数：

（1）X=R（一维实数空间），h(x) = sign(x-a)， a 是参数。

它的生长函数： m(N) = N + 1 ； 当N > 1时，m(N) < 2^N

（2）X=R， h(x) = 1 iff x>=a or x<b, -1 otherwise. 有两个参数 a, b.

它的生长函数：m(N) = 0.5N^2 + 0.5N + 1； 当 N>2 时， m(N) < 2^N

（3）X=R^2（二维实数空间），h是一个任意凸多边形，多边形内部的为1，外部的为-1。

它的生长函数：m(N) = 2^N

我们引入一个重要概念：突破点(break point)：对于某种假设空间H，如果m(k)<2^k， 则k 是它的突破点。

对于上面提到的三个例子，（1）的突破点是2,3,4... （2）的图破点是3,4,... （3）没有突破点。

注意：如果k 是突破点，那么k+1, k+2, ... 都是突破点。

对于感知机，我们不知道它的生长函数，但是我们知道它的第一个突破点是4， m(4)=14 < 16

对于后面的证明，突破点是一个很重要的概念。

第六讲： 归纳理论(台大机器学习）

上一讲重点是一些分析机器学习可行性的重要思想和概念，尤其是生长函数(growth function) 和突破点(break point) 的理解。

这一讲开篇再介绍一个界函数（bounding function）的概念：是指当（最小）突破点为k 时，生长函数m(N) 可能的最大值，记为B(N, k)。

显然，当k=1时，B(N, 1) = 1; 当k > N 时，B(N,k) = 2^N; 当k = N 时，B(N,k)=2^N - 1.

于是很容易得到Bounding function table:

image

需要重点考虑 k < N 的情况。

林轩田在课程中是通过图示的方法来猜想可能的递推不等式，没有严谨证明。

我这里根据林老师的图示进一步理解下，希望能给出一个相对更严谨的解释。

我们考虑B(4, 3)，对应的数据量是4 (x1, x2, x3, x4)，从这四个数据的角度看应该有B(4,3)个有效的dichotomies。

如果我们遮住其中一个 数据（比如x4），余下的dichotomies去重后，不超过B(3,3) 个。（否则就违背了突破点在3）。显然， B(4,3) <= 2 * B(3,3)。

也就是说，当扩展为(x1,x2,x3,x4)时，(x1,x2,x3)上的dichotomies 只有部分被重复复制了（最多一次）。

于是可以设 被复制的dichotomies 数量为a，未被复制的数量为b。（0 <= a,b <= B(3,3) )

可以知道，B(3,3) = a+b; B(4,3) = 2*a + b.

我们假设a > B(3,2)，这样，当扩展到(x1,x2,x3,x4) 时，有大于B(3,2) 的(x1,x2,x3) 上的dichotomies 被复制。此时在(x1,x2,x3) 中一定能够找到两个点被打散(shatter)而且被复制了，由于被复制，对月这些dichotomies，x4可以取两个不同类别的值，因此在(x1,x2,x3,x4) 中一定能找到3个点被打散了。这与"3"是突破点相违背。假设不成立，所以a <= B(3,2)。

所以，我们得到：B(4,3) = 2*a + b <= B(3,3) + B(3,2).

对于任意N > k, 利用上述思路，可以证明 B(N,k) <= B(N-1, k) + B(N-1,k-1).

有了递推不等式，通过数学归纳法，我们证明下面的Bounding Function (N > k) :

image

这个式子显然是多项式的，最高次幂是 k-1。

所以我们得到结论：如果突破点存在（有限的正整数），生长函数m(N) 是多项式的。

既然得到了m(N) 的多项式上界，我们希望对之前的不等式（如下图）中M 进行替换。

image

然而直接替换是存在问题的，具体解释和替换方法这里不多说了，可以去看林老师的课程。主要问题就是Eout(h)，out 的空间是无穷大的，通过将Eout 替换为验证集(verification set) 的Ein' 来解决这个问题。最后我们得到下面的VC bound:

image

VC 界是机器学习中很重要的理论基础，我们在后面还会对VC 维有详细解释。

到了这里，我们可以说，2维感知机的学习是可行的！

这一阶段大功告成！ :-)

第七讲： VC维理论 (台大机器学习）

上一讲的最后得到了VC bound，这一讲对VC维理论进行理解，这是机器学习（最）重要的理论基础。

我们先对前面得到的生长函数和VC bound 做一点小的修改。

image

image

1，VC 维的定义

VC Demension: 对于假设空间H，满足生长函数m(N) = 2^N 的最大的N， 记为dvc(H).

可知，dvc(H) 比H 的最小突破点k 小1，即 dvc(H) = k-1.

2维感知机的VC维是3.

2，感知机的VC维

我们已经知道，2维感知机的VC维是3.

对于d 维感知机，我们猜测它的VC 维是 d+1 ?

对此，我们只要证明 dvc >= d+1 && dvc <= d+1.

(1) 证明 dvc >= d+1

对于d 维空间的任意输入数据x1, 都增加一个分量x10, 取值恒为1.

即 x1 = (1, x11, x12, ... , x1d)。 （x1 是一个向量）

取组特殊的输入数据：

image

对于上面的d+1 个输入数据，我们可以求得向量w :

image

也就是说，这样的d+1 个输入数据可以被d 维感知机打散(shattered), 所以有 dvc >= d+1.

(2) 证明 dvc <= d+1

对于d 维空间的输入数据：

image

也就是说，不可能存在d+2 个线性独立的输入数据。其中，线性组合中的系数可能为正、负或零，但是不全为零。

等式两边都乘以 w 向量：

image

假设这d+2 个数据都可以被打散。那么我们可以对 wx 随意取值（-1 或 +1），上式都应该能够满足。然而，对于这样的情况：当系数a 为正数时，wx 取+1，反之w*x 取-1，式子右边一定大于0；此时式子左边就无法取-1，与假设矛盾。

所以d 维感知机无法打散 d+2 个点，也就是说VC 维最大只能是 d+1.

综合（1）（2），证得 dvc = d+1.

3，VC 维的物理意义

VC维可以反映假设H 的强大程度(powerfulness)，VC 维越大，H也越强，因为它可以打散更多的点。

通过对常见几种假设的VC 维的分析，我们可以得到规律：VC 维与假设参数w 的自由变量数目大约相等。

例如，对于2维感知机，w = (w0, w1, w2)，有三个自由变量，dvc = 3.

4，VC 维的解释

VC 维反映了假设H 的强大程度，然而VC 维并不是越大越好。

通过一些列数学推导，我们得到：

image

上面的”模型复杂度“ 的惩罚(penalty)，基本表达了模型越复杂（VC维大），Eout 可能距离Ein 越远。

下面的曲线可以更直观地表示这一点：

image

模型较复杂时(dvc 较大)，需要更多的训练数据。 理论上，数据规模N 约等于 10000dvc（称为采样复杂性，sample complexity）；然而，实际经验是，只需要 N = 10dvc.

造成理论值与实际值之差如此之大的最大原因是，VC Bound 过于宽松了，我们得到的是一个比实际大得多的上界。

即便如此，VC Dimension & VC bound 依然是分析机器学习模型的最重要的理论工具。

第八讲： 噪音和错误 (台大机器学习）

当我们面对的问题不是完美的（无噪音）二值分类问题，VC 理论还有效吗？

1，噪音和非确定性目标

几种错误：(1) noise in y: mislabeled data; (2) noise in y: different labels for same x; (3) noise in x: error x.

将包含噪音的y 看作是概率分布的，y ~ P(y|x)。

学习的目标变为预测最有可能出现的y，max {P(y|x)}。

2， 错误的测量 (error measure)

对错误不同的测量方法将对学习过程有不同的指导。

如下面的0/1 error 和 squared error.

image

我们在学习之前，需要告诉模型我们所关心的指标或衡量错误的方法。

3，衡量方法的选择

image

图中的false accept 和 false reject 就是我们在分类中常说的 false positive 和 false negative，只是台湾和大陆的叫法不同而已。

采用0/1 error 时，对于每种错误，都会有相同程度的惩罚(panalize)。

然而，在实际应用中，两种错误带来的影响可能很不一样。

例如（讲义中的例子），一个商场对顾客进行分类，老顾客可以拿到折扣，新顾客没有折扣；这时，如果发生false reject（将老顾客错分为新顾客）而不给其打折，那么会严重影响用户体验，对商家口碑造成损失，影响较坏；而如果发生false accept （将新顾客错分为老顾客)而给其打折，也没什么大不了的。

另一个例子，CIA 的安全系统身份验证，如果发生false accept（将入侵者错分为合法雇员），后果非常严重。

通过上述两个例子，我们知道，对于不同application，两类错误的影响是完全不同的，因此在学习时应该通过赋予不同的权重来区分二者。比如对于第二个例子，当发生false accept : f(x)=-1, g(x)=+1, 对Ein 加一个很大的值。

Just remember: error is application/user-dependent.

4，带权重的分类

依然是借助CIA 身份验证的例子来说明什么是weighted classification：

通过感知机模型解决CIA 分类问题。如果数据时线性可分的，那么带权重与否对结果没有影响，我们总能得到理想结果。

如果输入数据有噪音（线性不可分），像前面学习感知机时一样，采用Pocket 方法，然而计算错误时对待两种错误(false reject/false accept) 不再一视同仁，false acceot 比false reject 严重1000倍。通过下面方法解决

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标人工智能机器学习频道！