这篇文章是我的“程序员的机器学习笔记”系列的第一篇，之所以要写这个笔记一是希望自己能有所提高，毕竟总结的过程也是二次学习的过程；二呢，是希望给有意愿转到机器学习方向的程序员提供一个学习的资料吧，希望大家共同进步。

        在这第一篇里主要讲述机器学习中的一些基本概念，学习的类型以及我对某些概念的形成其背后的思想的理解，这部分理解不一定是那些大家们先驱们的思想的正确理解，所以仅供参考和辅助理解概念。

一、什么是机器学习？

        对于什么是机器学习目前并没有一个统一的共识，在《统计学习方法》中提到Herbet A. Simon曾对学习下的定义：“如果一个系统能够通过执行某个过程改进它的性能，这就是学习。”

        在经典著作AIMA（《人工智能 一种现代的方法》）中作者说：“一个Agent是善于学习的，若基于其对世界的观察，能够改进执行未来任务时的性能。”

        在Andrew NG的《Machine Learning》里提到了一个更加形式化的定义：

Tom Mitchell 给出了一个更加现代的定义：“A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.”

        挺绕口的，翻译出来大概意思就是：如果一个计算机程序，它处理由性能度量P所度量的任务T的性能能够随着（对应于T和P的）经验E的提升而提升，那么我们就说这个计算机程序能够从关于这些类型的任务T和其性能度量P的经验E中学习。

        还是挺绕的，不过我们从上面三个描述中能感性的了解到“任务T”、“经验E”和“性能P”应该是一个程序是否能学习的很重要的因素。具有学习能力的程序应该能做到从任务T中获得经验E并根据经验E提升自己的性能P。

        类比人是如何学习的，比如小孩子学走路，刚开始的时候小孩子不会走路总是摔倒，但是通过不断的尝试获得越来越多的经验，孩子走得越来越稳。

                    T ＝ 走路

                    E ＝ 不断尝试获得的经验（大概是如何迈腿如何保持平衡之类的）

                    P ＝ 走路更稳

下面是Andrew NG举的例子：

                    下西洋棋的程序的例子：

                    E = 玩很多局西洋棋的经验

                    T = 下西洋棋

                    P = 程序赢得下一场棋局的概率

二、为什么需要机器学习？

        简单来说，就是现实世界中有很多问题是无法通过直接编程解决的，要么是解空间太大无法穷举，要么是我们对于直接求解没有思路。还有就是规则在发生变化固化的程序无法自适应改变，其实这往往是因为我们没有无法找到数据背后真正的产生规则，而机器学习程序可以不断的自我更新和搜寻近似的规则来逼近数据背后隐含的信息。

        可以举很多用传统的方法无法解决的问题。比如数据挖掘，我们要挖掘数据中隐含的信息；比如我们很难写确定的一个程序让计算机学习如何驾驶直升机，如何进行手写字体识别，如何进行NLP，如何识别图像（计算机视觉），而这些任务最合适的方式是让计算机自己学习如何去做。还有像下棋这样的任务，如果通过传统的编程方式去做那么如果要写出一个好的下棋程序那么编程者自身需要是一个高手才能保证它的程序有很高的胜率，但是通过机器学习手段，编程者即便是个菜鸟，计算机可以通过自己学习而达到很高的水平。

        另外，还有像电子商务网站的推荐功能等，针对这些网站的海量用户去编写千万个不同的程序显然是不可能的。唯一有效的解决方案就是开发出能够自我学习定制出符合你的喜好的并据此进行推荐的软件。所以，机器学习可以给我们的程序带来新的能力。

        AIMA的作者在书中提问了这样两个问题并给出了解答：

为什么我们希望Agent能够学习？如果Agent的设计能够被改进，为什么设计者不以此改进为基点进行编程？

    他的回答是：

有三个主要理由。首先，设计者不能预测Agent可能驻留的所有情境，例如走迷宫的机器人必须学习它所遇到的新迷宫的布局。其二，设计者不能预期随时间推移可能出现的所有变化，如预测明天股票市场价格的程序必须学习，以便涨跌条件发生变化时能够自我适应。其三，有时候人类程序员本身对程序求解没有思路。例如，人类大多善于识别家庭成员的面相，但即使是最好的程序员也不能编写出完成此任务的计算机程序，除非使用学习算法。

三、机器学习的种类

从总体上来说，任何的机器学习问题都能够被划分到两个宽泛的类型：监督学习和非监督学习。进一步细分，机器学习还可以分为监督学习、非监督学习、半监督学习、强化学习和推荐系统等。

监督学习：

        监督学习是一类应用广泛的学习问题，监督学习的任务是从一组“输入－输出”对样本组成的数据集（下面称为训练集或训练数据集）中学习能够预测新输入相对应的输出的函数。“输入－输出”对样本组成的训练集形式化如下：

                    T={(x1, y1), (x2, y2), ..., (xn, yn)}，其中，每个yi是对应于输入xi的输出。

        那么，我们有一个很纯朴的想法，在数据背后一定存在一种映射，它能将某个xi映射到一个yi，我们不妨认为这个映射是某个未知函数f(x)，即每个yi都是由未知函数y=f(x)生成。只从数据本身我们无法轻易知道这个未知函数f(x)具体是什么，但是我们可以提出一个假设函数h(x)，使得它能足够好的逼近这个未知的f(x)，即h(x) —> f(x)，学过数值分析的应该知道这个过程就是函数拟合。

        面对这个训练数据集我们可以提出很多的假设函数，怎么确定应该是哪一个呢？所谓的“监督”又是什么含义呢？这就要回到训练数据集本身来说。训练数据集是由一组“输入－输出”对组成的，其实这个“输出”就是给出了一个由输入应该得到什么输出的正确答案，训练数据集中每一个xi都对应了一个正确答案yi。我们正愁怎么确定这个h(x)呢，既然训练集已经给了部分输入的正确答案，那么我们在生成我们的假设函数h(x)的时候就可以充分使用这些标准答案作为参考，其实也是使用这些标准答案作为h(x)的约束或监督，即，h(x)在训练数据集上应该能最大程度地与这些标准答案靠近，越接近标准答案的假设函数就越能从所有的假设中胜出。这就是监督学习的思想。

        另外，监督学习问题可以分为两大类：回归和分类，具体在后面的笔记中会讲到。

        另外提一句，我们无法知道真正的产生数据的f(x)，而只能根据已有的数据去最大可能的拟合它，所以期待我们的拟合函数能百分百符合真正的规律是不现实的，也就是说期望我们的系统能百分百精确地预测未来是不现实的。人工智能的观点是“设计能最佳表现的系统”而不是设计一个完美的系统。在实现时，我们也是不断的训练和更新模型以达到不断优化模型去最小化误差的目的，而不是一开始就奔着100%正确去。

AIMA中提到：

先驱的人工智能研究者赫伯特.西蒙（Herbert Simon，1916—2001）因其早期的工作在1978年获得经济学诺贝尔奖，其工作指出基于满意度的模型——做出“足够好”的决策，而不是费力地计算最优决策——给出了真实人类行为的一个更好的描述（Simon，1947）。

虽然他说的是人工智能中的决策问题，但是这个思想我们在机器学习模型及算法中也是随处可见的。

无监督学习：

        了解了监督学习，无监督学习就容易理解了。在监督学习的训练集中每一个xi都对应了一个标准答案yi，但是在无监督学习中训练集中只有xi没有标准答案yi，我们对于输出应该是什么样了解的很少或者完全不了解，这也意味着无监督学习需要以另外的思路来寻找数据背后的隐含信息。无监督学习可以基于数据中各变量之间的关系，比如某种距离的度量，来聚类数据，从而让我们得到数据中蕴含的某种结构而不需要了解数据中各变量的作用。

        另外，在监督学习中，学习到的最佳假设函数在测试数据集（测试数据集具有和训练数据集相同的(xi, yi)结构，即测试数据集也带有标准答案）上做预测的时候可以得到的预测结果的反馈，而无监督学习中没有基于预测结果的反馈，因为没有标准答案。

        无监督学习常用在聚类问题上，例如给定一个具有1000000个不同基因的集合，找出一个方法来自动的对这些基因进行分组，每个组内的基因在某些因素上是相似的或者有关联的， 比如lifespan, location, roles等。

        无监督学习也可以用于一些非聚类的问题，例如鸡尾酒算法可以让你找到混乱环境中的结构信息，比如从酒会里嘈杂的声音中分辨出每个人的声音。

半监督学习：

        监督学习的训练集是带有正确答案的（一般称为带有标记的），无监督学习的训练集是不带标记，而半监督学习介于二者之间，它的训练集是部分带有标记部分不带标记的，而且往往带有标记的样本点很少，大部分是不带标记的。半监督学习的任务是：在不需要与外界交互（不需要寻求外界的帮助将未标记的样本点加上标记）的情况下，如何利用未标记的样本来提升学习性能。

        半监督学习解决的问题是一个很现实的问题。在现实中我们通常无法获取大量带有标记的样本，大多数的样本都是不带标记的，要给这些不带标记的样本通过人力重新加上标记费时费力，比如电信公司要做电话盗打的检测（Fraud Detection），想要从历史的话单记录中找到盗打的规律，以便用来实时检测盗打事件，可想而知在历史记录中已被确认的盗打或非盗打记录相较于未被确认的记录来说是很少的，如果仅使用占比很少的带标记的样本用监督学习的方式来建模，由于训练样本不足，学得的模型的预测性能往往不太好，如何有效的利用大量的不带标记的样本就是一个现实的问题了。

强化学习：

        强化学习是一种非常有意思的学习方式。强化学习的内容非常丰富，可以认为它囊括了人工智能的全部，在Alpha Go大胜李世石后，强化学习也开始越来越被人们关注。

        强化学习通常用来解决需要做连续决策的问题，给出一个能取得长期累积价值最大化的策略。这样的问题不是做一步预测就结束的，它是由一连串的决策构成的决策过程，即，在某个状态下强化学习得到的策略需要根据此状态给出一个动作，作出这个动作后系统（由程序和外部环境构成）转入新的状态，模型又需要作出新的动作，如此循环，而且要求每个状态下作出的动作都是在考虑后续可能状态转换的情况下能获得最大价值的动作。比如下围棋。

        强化学习任务一般可以用马尔可夫决策过程（Markov Decision Process，简称MDP）来描述：Agent（机器或程序）处于环境E中，所有状态组成的状态空间为X，其中每个状态x∈X是Agent感知到的环境的描述，Agent能采取的动作构成了动作空间A，若某个a∈A作用在当前状态上，则潜在的状态转移函数P将使得环境从当前状态按某种概率专一到另一个状态，在状态转移的同时，环境会根据潜在的奖励函数R反馈给Agent一个奖励。综合起来，强化学习任务对应了四元组E = <X, A, P, R>。

四、机器学习基本术语

        每个行业都有一些术语或行话，机器学习中也有一些基本的术语，为了便于后面的讨论，在这里需要就一些经常出现的术语做一些介绍。

数据集

        数据集是我们可以用来进行机器学习模型训练的一组数据的集合，其中每一条数据也称一个样本，是关于一个事件或对象的描述。一条数据可能会由多个数据项组成，每个数据项反映事件或对象在某方面的表现或性质，所以数据项也称为“属性”或“特征”，属性的取值称为“属性值”。比如电话的Fraud Detection，我们可能有这么一个数据集，样本容量为10000：

样本1: {20170110141005；60；02166668888；8613888888888；31.230432； 121.473791}

样本2: {20170608201500；180；02166556688；8613866666666；31.334455； 121.567890}

样本3: {20170610212010；76；02166676543；8613966667777；31.678090； 122.2233441}

.

样本10000: {20180113161002；600；02166778899；13332345678；32.567890；125.303958}

其中每个样本是对一个电话呼叫的描述，它包含6个属性，它的每个属性描述的是：

{属性1: 呼叫时间；属性2:呼叫时长；属性3:主叫号码；属性4:被叫号码；属性5:交换机经度；属性6:交换机纬度}

数据集中的一条数据即是一个样本，所有样本组成的空间称为样本空间，而数据集只是样本空间中的一部分，是样本空间的子集。例如上例中的电话呼叫记录的数据集，我们只是从历史所有的呼叫记录中抽样出了10000条记录。

一般地，数据集可以形式化地表示为：

D ＝ {X1, X2,X3, ...,Xm}，表示包含m个样本的数据集，每个样本由d个属性描述，则每个样本Xi = {xi1; xi2; ...; xid}是d维样本空间X中的一个向量，Xi∈X，其中xij是Xi在第j个属性上的取值，d称为样本Xi的维数。

    通常情况下，我们会把数据集划分为两个部分，一部分用于机器学习模型的学习（或称为训练），另一部分用于测试模型的性能。用于训练的那部分子集称为“训练集”，用于测试的子集称为“测试集”。

输入空间，特征空间，输出空间

        在监督学习中，将输入与输出所有可能取值的集合分别称为输入空间和输出空间。每个具体的输入通常由特征向量来表示，所有特征向量存在的空间成为特征空间。特征空间的每一维对应于一个特征。有时候输入空间与特征空间是相同的，有时候需要从输入中提取特征，将输入空间映射到特征空间。模型都是定义在特征空间上的。

假设空间

        我们在前面提到，在监督学习中，学习的目的是为了学习一个由输入到输出的映射，而为了得到这个映射我们会提出关于这个映射的一个假设，而这个假设的所有可能性就组成了一个假设空间，学习过程就是从假设空间中搜索出与训练集最匹配的假设。

五、统计学习三要素

        最后介绍下《统计学习方法》中说的统计学习三要素，之所以觉得有必要说下这部分内容，一是因为笔记中涉及的大部分内容都是统计学习的内容；二是，我觉得这三要素其实是体现了统计学习的思路，类似于一种方法论了，思路往往比具体的某个算法或模型更重要。

    统计学习方法都是由模型、策略加算法构成：

    方法 ＝ 模型 ＋ 策略 ＋ 算法

    统计学习方法之间的不同主要来自其模型、策略、算法的不同，确定了这三要素，统计学习的方法也就确定了。

模型

        统计学习首先要考虑的问题是学习什么样的模型，模型确定了，模型的假设空间自然就确定了，后面要做的就是从假设空间子搜索最优的假设。例如，在监督学习中，如果我们假定从输入到输出的映射是一个线性模型，那么我们要找的这个最优的假设函数就是输入变量的线性函数。这个线性模型的假设空间就是所有线性函数（一般有无穷多个）构成的函数集合。

策略

        有了模型后，就有了假设空间，接下来就是考虑按照什么样的准则选择最优的假设，这也是统计学习的目标。

        我们判断假设空间中一个假设比另一个好的准则有两个：1. 经验风险最小，2. 结构风险最小。

        在监督学习中，经验风险中的“经验”就是训练集中的“输入－输出”对，最主要的是“输出”（标记或正确答案）。我们的假设函数h(x)在训练集上根据输入给出的输出y'与训练集上的正确答案y可能一致也可能不一致，这两者之间的差距称为损失。由于损失来自于假设函数那，么自然也就有损失函数，一般记作 L(Y, h(X)) 。

        可以定义多种损失函数，其中平方损失函数最为常用：L(Y, h(X)) ＝ (Y - h(X))^2

        既然说的是经验，那么当然不能只考虑某一个样本的损失了，而应该考虑整个训练集上的平均损失，练的多了才有经验嘛。

        所以，经验风险最小化就是指我们的假设关于训练数据集平均损失最小化，即：

        另一方面，相对于整个样本空间，我们的训练集是很小的，而且训练集中的数据又不可避免的会有噪声干扰，所以基于训练集去拟合真实函数，即便在训练集上的经验风险已经最小了，但是在测试集上做预测的误差也可能会很大，这就是所谓的“过拟合”（由于训练数据中有噪声，太强调与训练数据的正确答案一致，就会拟合过头了，拟合出一个结构佷复杂的函数，导致在训练数据集上的经验风险很小，但是模型在测试数据集上却不理想）。

        结构风险最小化就是为了解决这个过拟合问题的。具体的在后面的笔记中会说明，这里只简单介绍。结构风险是指假设函数的结构的复杂度，假设函数结构越复杂结构风险越大。结构风险小需要经验风险和模型复杂度同时小，结构风险小的模型往往对训练数据集和测试数据都有较好的预测。如何把这个结构风险最小的想法带入的模型中呢？答案是通过在经验风险的基础上引入一个正则化项（或称惩罚项）来限制假设函数的结构，结构越复杂惩罚就越大。

        后面𝝀J(h)就是正则化项，𝝀>=0,  h是学习到的假设函数，f越复杂J(h)的值越大。

        效果差不多的手段，越简单的手段越好。这种规律真是处处可见啊。

算法

        算法是指学习模型的具体计算法方法。统计学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最后需要考虑用什么样的计算方法求解最优模型。比如，对于前面的那个结构风险最小化的表达式，它是一个最优化问题，那么怎么去求解这个最优化问题呢？这里说的算法就是求解最优化问题的算法。如果最优化问题有解析解，求解析解还是比较简单的（比如先求导再令导数为0得到驻点再在驻点中找出全局最优点）；但是大多数情况是解析解不存在，这就需要用数值计算的方法求得数值解了，比如梯度下降，拟牛顿法等，使用类似的迭代方法时，如何保证找到全局最优解并使求解的过程非常高效是一个重要的问题，算法如果迭代的特别慢或者压根就收敛不了那就不能用了。

        在这篇笔记中，从总体上介绍了机器学习的一些基本的概念，学习的类型和一些机器学习的思想，其实还有一些概念也很重要，这些概念在具体的某个机器学习模型和算法中并不体现，但是这些概念确实是为机器学习服务的，比如与性能度量，模型评估等相关的概念，它们用来衡量一个经过训练得到的模型是不是一个好的模型，所以这些概念也是很重要的有必要提及的，但是我不想使第一篇笔记的篇幅过大，所以我将放到下一篇笔记中介绍。

参考资料：

Andrew NG 《Machine Learning》课程

李航《统计学习方法》

周志华《机器学习》

Stuart J. Russelll《人工智能 一种现代的方法》