机器学习已经取得了巨大的成就,语音识别、自动驾驶、人机对弈等等,这些都说明了机器学习的强大之处。而自己研究生阶段的读研方向,已经基本确定,就是数据挖掘和机器学习,趁现在还有时间,可以先自己学一下(暑假总想看,结果每次都是看一会儿就打开电脑,然后就没有然后了。。。)

选这本书,是因为这本书适合入门,比较简单。而这个系列博客就是自己的笔记了,当个备忘录,或许还会有一些自己的想法在里面

OK,Go

学习问题的标准描述

学习的定义如下,这里的“学习”和我们日常生活中的“学习”意义并不完全相同

对于某类任务 T 和性能度量 P,如果一个计算机程序在 T 上以 P 衡量的性能随着经验 E 而自我完善,那么我们称这个计算机程序从经验 E 中学习

也就是说,为了很好的定义一个学习问题,必须明确三个特征:任务的种类 T衡量任务提高的标准 P经验的来源 E,书上给了一些例子,这里只写出关于西洋跳棋的例子

对于西洋跳棋问题

  • 任务T:下西洋跳棋
  • 性能标准P:比赛中击败对手的百分比
  • 训练经验E:和自己对弈

我们当然可以提出不同于以上的T、P、E,这些都没有问题,只要有足够的理由即可。

设计一个学习系统

用的就是西洋跳棋的例子,问题是这样的,我们需要设计一个下西洋跳棋的程序,让这个程序在世界锦标赛与人类选手进行比赛,用其获胜的百分比作为性能的衡量标准。

如前面所说,一个学习问题有三个特征,现在任务 T 已经确定了和性能标准 P 已经确定,还有一个经验 E 需要确定。对于经验E,有三个关键的属性:

  • 训练经验能否为系统的决策提供直接或者间接的反馈
    对于西洋跳棋,直接的样例如各种棋盘状态和相应的正确的走子,间接的样例如过去的对弈序列和最终的胜负。间接样例中,非终局的走子必须通过最终对弈的输赢来判断,这又涉及到信用分配问题,也就是每次走子对最终结果的贡献(这是一个非常困难的问题)
  • 学习器在多大的程度上控制训练序列 学习器依赖施教者选取棋盘状态和正确走子,或者提出自己认为模糊的棋盘状态并向施教者询问,或者完全自主控制训练。而完全自主训练,也可以分为每次训练一个全新的棋盘状态,或者从已知的最有效的走子路线稍作变化
  • 训练样例能多好的表示实例分布 训练样例和实例分布在绝大多数情况下书不同的,而系统最终的性能是通过实例分布来衡量的。目前多数的机器学习理论都依赖于训练样例与实例分布一致这一假设,但是在实践中需要清楚,这一假设经常不成立

在这个例子中,我们选择程序自己和自己对弈,因为,训练经验可以为系统提供间接的反馈(因为自己和自己对弈,对于对弈之中的棋盘状态,不能确定其最佳走子,而只能提供给系统一次对弈的走子路线以及结果),完全自主的训练(这个显然,自己和自己下棋,当然不需要外界的施教者),训练样例不能完全的表示实例分布(这个是当然的,甚至不能较好的表示实例分布,这取决于自我对弈的选择棋盘状态的策略)

现在,学习问题已经确定,不过,对于实现这个系统而言,这显然还不够,因为我们需要的操作上的定义,而不是理论的定义。因此现在需要选择:

  • 要学习的知识的确切类型
  • 对于这个目标知识的表示
  • 一种学习机制

选择目标函数

这一步是决定要学习的知识的确切类型以及执行程序如何使用这些知识。我们的目标其实是在西洋跳棋的合法走子中选择最佳的走子,这种任务代表了一类学习任务:已知一个巨大的搜索空间(合法的走子),但是最佳的搜索策略未知。很多最优化问题都可归于此。

我们学习的目标其实就是一个对于一个给定的棋盘状态,能够作出最佳走子选择的一个函数,这里称之为 ChooseMove,可以表示为。现在我们已经把我们的提高任务 T 的性能 P 的问题简化为了寻找 ChooseMove 这样的一个特定函数。但是这个 ChooseMove 函数的学习是非常困难的,因为提供给系统的是间接的经验,从一个棋盘状态选择一个最佳走子,就像之前所说,会涉及到信用分配问题。

而另外的一个选择是,对于每个棋盘状态,给出一个打分,最后我们就可以通过打分来决定一个棋盘状态的最佳走法。相比于ChooseMove,这应该是一个更简单的目标函数。这里称之为 V,表示为

现在任务就是确定这个函数 V,虽然任何一个能够对较好的棋盘状态打出较高分的函数都可以,我们还是应该确定一个特定的函数 V,我以为,这个函数应该越简单越好。

书中是如下定义,对于集合 B 中的任意一个棋盘状态 b

可以看出,这是一个递归性的定义,也正是因此,其运算效率不高。对于最后一种情况,决定 V(b) 需要向前搜索到达终局的所有路线,这显然不现实。因此这个定义是一个不可操作的定义。这种情况下,学习任务被简化为发现一个理想的目标函数 V 的可操作描述。通常完美的学习一个 V 的可操作定义是非常困难的,因此,事实上,我们一般仅仅希望我们的学习算法得到一个近似的目标函数,故而学习目标函数的过程通常称之为函数逼近。下面将会用表示学习到的函数。

选择目标函数的表示

的选择有很多,一般有两个方面要考虑:一是我们总希望选取一个非常有表征能力的描述,以尽最大可能的逼近理想函数 V;另一方面,表征能力越强的描述需要越多的训练数据。书中为了简化,选择了一种非常的简单的表示方法,即

其中,

  • :棋盘上黑子的数量
  • :棋盘上红子的数量
  • :棋盘上黑王的数量
  • :棋盘上红王的数量
  • :棋盘被红子威胁上黑子的数量
  • :棋盘上黑子威胁的红子的数量
  • :权,由学习算法来选择,学习的目标就是确定这些权

选择函数逼近算法

首先,每个训练样例都是一个有序偶,,表示棋盘状态以及对应的训练值。之后,需要估计训练值,对于非终局的棋盘状态,要确定其评分并不容易,最终的结果并不能确定一个中间状态的好坏,这很容易理解。虽然如此,确有一个比较简单的办法可以取得不错的效果,这个方法可以如下表示

虽然不容易理解,不过在数学上已经证明,这种方法可以近乎完美的收敛到 的估计值

接下来要做的就是调整权值,选择最适合权。什么叫做最适合呢?这是需要定义,也就是定义最佳拟合,一种常用的方法是把最佳的假设定义为是训练值和假设预测除的值之间的误差的平方和最小,即最小误差平方逼近,公式如下

现在需要一种算法,在新的训练样例来到的时候,能够更新权值,并且对估计的训练数据中的差错有较好的健壮性。LMS(least mean squares,最小均方法)就是一个这样的算法。对于每一个训练样例,LMS会将权值调整到减小误差的方向。其算真如下

对于每一个训练样例

  • 使用当前的权值计算
  • 对于每一个权值,进行如下更新 ,其中 是一个小的常数,如0.1,用来调整权值更新的幅度

在一定的条件下,LMS可以证明收敛到 的最小误差平方逼近

最终设计

最后的,我们的设计是一个循环的圈(书上有图,这里不画了,用语言描述以下),是这样的一个循环

新问题(初始棋局)—> [执行系统] — 解答路线(对弈历史)—> [鉴定器] —训练样例(有序偶序列)—> [泛化器] — 假设 —> [实验生成器] — 新问题

  • 执行系统:用学会的目标函数解决任务,生成解答
  • 鉴定器:以执行系统输出的解答作为输入,输出一系列的训练样例
  • 泛化器:根据鉴定器输出的训练样例学习新的目标函数,新的目标函数可以覆盖这些样例以及一些样例之外的情形
  • 实验生成器:以当前的假设作为输入,输出一个新的问题供执行系统取探索

许多机器学习系统都可以用这四个模块刻画。

对于西洋跳棋问题来说,如果目标函数真的可以表示为这些特定参数的线性组合,那么程序学习到这个目标函数的可能性很大,也就是说程序的正确性会很好,否则最多可以学到一个合理近似,毕竟一个程序无法学习这个程序根本无法表达的东西(比如目标函数是个二次函数,而这个函数只能表示一次函数,当然不能学习到这个二次的函数)。

机器学习的一些观点

在机器学习方面,一个有效的观点是机器学习问题经常可以归结于一个搜索问题,即对非常大的假设空间进行搜索,以确定最佳拟合观察到的数据和学习器已有知识的假设。意思就是在这个非常大的假设空间进行搜索,寻找到特定的假设,这个假设能够最佳的拟合观察到的数据与学习器已有的知识。。好吧,这句话比较绕口,是一个语法问题。。。

好了,第一次终于写完了,是到目前为止写的最长的一篇博客。。基本上照搬书上的东西,不过由于要写出来,相比于之前读本章,读得更加透彻了,毕竟写出来,不能通篇都是错的的东西。。

为了写数学公式,特意给博客加上了MathJax支持,还换了Markdown的解析器。。。不知道下一篇是什么时候呢。。。