关于作者

 一个毕业于北京大学数学力学系,在中国科学院计算所、计算中心和网络中心工作过,在澳大利亚科工组织DMS、香港浸会学院数学系和中国21世纪议程管理中心等处工作过,多次获国家和中科院科技奖并享受政府特殊津贴的退休老头。现在在【中国科普博览】网“科学新语林”栏目里开设一个《数学与计算机》的个人专栏,愿和爱好数学与计算机的各界网友和青少年朋友,谈谈对数学与计算机的看法、想法。

《常用算法之智能计算(三)》:机器学习计算

张建中
2018年11月08日
机器学习(Machine Learning),人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域,主要使用归纳、综合而不是演绎的方法研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。机器学习是一门多领域的交叉学科,涉及到概率论、统计学、逼近论、凸分析、算法复杂度理论和计算机科学等诸多学科。

机器学习(摘自互联网)

机器学习计算(Machine Learning Computing)主要设计和分析一些让计算机可以自动“学习”的算法,是一类从数据中自动分析获得规律、利用规律,对未来数据进行分类、聚类和预测等的一类算法。因为机器学习计算中涉及了大量的统计学理论,机器学习与统计推断的联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习计算关注可以实现的、行之有效的学习算法,很多推论问题具有无程序可循的难度,所以部分的机器学习研究是开发简单、处理容易的近似算法。
机器学习已经得到了十分广泛的应用,如数据挖掘、计算机视觉、自然语言处理、生物特征识别、搜索引擎、医学诊断、检测信用卡、证券市场分析、DNA序列测序、语音和手写识别、战略游戏和机器人运用等。
从更广泛的意义上来看,机器学习是人工智能的一个子集。人工智能旨在使计算机更加智能化,而机器学习已经证明如何做到这一点。简而言之,机器学习是人工智能的应用,通过应用从数据中反复学习得到算法,可以改进计算机的功能,而无需进行明确的编程。
在给出机器学习计算各种算法之前,最好是先研究一下什么是机器学习和如何对机器学习进行分类,才能更好的理解和掌握一些具体的机器学习算法并将其用于实际问题的计算和处理。
学习是人类具有的一种重要智能行为,但究竟什么是学习,长期以来却众说纷纭。社会学家、逻辑学家和心理学家都各有自己不同的看法和说法。比如,有人定义机器学习是一门人工智能的科学,该领域的主要研究对象是人工智能,特别是如何从经验学习中改善具体算法的性能,也有人认为机器学习是对能通过经验自动改进计算机算法的研究,还有人认为机器学习是用数据或以往的经验,以此优化计算机程序的性能标准等等。尽管如此,为了便于进行讨论和推进机器学习学科的进展,有必要对机器学习给出定义,即使这种定义是不完全、不完整和不充分的并存在诸多争议的。
顾名思义,机器学习是研究如何使用机器来模拟人类学习活动的一门学科。稍为严格的提法是:机器学习是一门研究机器获取新知识、新技能并识别现有知识的学问。这里所说的“机器”,当然指的是计算机;现在是电子计算机,将来还可能是中子计算机、光子计算机或神经网络计算机。
计算机能否象人类一样能具有学习的能力,特别是机器的学习能力是否能超过人类,确有许多不同的想法和看法,争议颇多。持否定意见人的一个主要论据是:机器是人造的,其性能和动作完全是由设计者规定的,因此无论如何其能力也不会超过设计者本人。这种意见对不具备学习能力的计算机来说的确是对的,可是对具备了学习能力的计算机就值得考虑了,因为这种计算机的能力通过学习和实际应用会不断提高和增强,过了一段时间之后,设计者本人也不知它的能力达到了什么水平、是否超过了自己。
对机器学习可按照不同的标准和方法进行分类,下面简单介绍两种常见的分类方法。
(1)基于学习策略的分类 ?学习策略是指学习过程中系统所采用的推理策略。一个学习系统总是由学习和环境两部分组成。由环境(如书本或教师)提供信息,学习部分则实现信息转换,用能够理解的形式记忆下来,并从中获取有用的信息。学习策略的分类标准就是根据学生实现信息转换所需的推理多少和难易程度来分类的,依照从简到繁、从少到多的次序分为以下六种基本类型:
1)机械学习????学习者无需任何推理或其它的知识转换,直接吸取环境所提供的信息,主要考虑如何索引存贮知识并加以利用。系统的学习方法是直接通过事先编好、构造好的程序来学习,学习者不作任何工作,或者是通过直接接收既定的事实和数据进行学习,对输入信息不作任何的推理。
2)示教学习????学生从环境中获取信息,把知识转换成内部可使用的表示形式,并将新的知识和原有知识有机地结合为一体。所以要求学生有一定程度的推理能力,但环境仍要做大量的工作。教师以某种形式提出和组织知识,以使学生拥有的知识可以不断的增加。这种学习方法和人类社会的学校教学方式有点相似,学习的任务就是建立一个系统,使它能接受教导和建议,并有效地存贮和应用学到的知识。目前,不少专家系统在建立知识库时就使用这种方法以实现知识获取。
3)演绎学习????学生所用的推理形式为演绎推理,从公理出发,经过逻辑变换推导出结论。这种推理是"保真"变换和特化的过程,使学生在推理过程中可以获取有用的知识。这种学习方法包含宏操作学习、知识编辑和组块技术。
4)类比学习????利用源域和目标域二个不同领域中的知识相似性,通过类比从源域的知识推导出目标域的相应知识,从而实现学习。类比学习系统可以使一个已有的计算机应用系统转变为适应于新的领域,来完成原先没有设计出来的类似功能。类比学习需要比上述三种学习方式更多的推理,一般要求先从知识源中检索出可用的知识,再将其转换成新的形式,用到新的状态中去。
5)解释学习????学生根据教师提供的目标概念、该概念的一个例子、领域理论及可操作准则,首先构造一个解释来说明为什么该例子满足目标概念,然后将解释推广为目标概念的一个满足可操作准则的充分条件。
6)归纳学习????归纳学习是由教师或环境提供某些概念的一些实例或反例,让学生通过归纳推理得出该概念的一般描述。这种学习的推理工作量远多于示教学习和演绎学习,因为环境并不提供一般性概念描述。归纳学习是最基本的、发展较为成熟的一类学习方法,在人工智能领域中已经得到广泛的研究和应用。
(2)基于学习方式的分类 ??机器学习算法按照学习方式的不同可以分为五种类型:有监督学习、无监督学习、半监督学习、强化学习和深度学习。
1)有监督学习????输入的数据为训练数据,并且每一个数据都会带有标签或类别。通过训练过程建模,模型需要作出预测,如果预测出错会被修正,直到模型输出准确的训练结果,训练过程会一直持续。常用于解决的问题有分类和回归,常用的算法包括分类、逻辑回归和BP神经网络。
2)无监督学习????输入数据没有标签或类别,输出没有标准答案,就是一系列的样本。无监督学习通过推断输入数据中的结构建模,可能是提取一般规律,可以是通过数学处理系统以减少冗杂,或者根据相似性组织数据。常用于解决的问题有聚类,降维和关联规则的学习。常用的算法包括了Apriori算法和K均值算法等。
3)半监督学习????半监督学习可以看做无监督学习的延伸,介于有监督学习和无监督学习二者之间,其输入数据包含标签和不带标签的样本。常用于解决的问题是分类和回归,常用的算法是对所有的无标签的数据建模进行的预测算法。
4)强化学习 ???强化学习是一个连续决策的过程,每次预测都有一定形式的反馈,但是没有精确的标签或者错误信息。
5) 深度学习????深度学习并不是一种独立的学习方法,其本身也会用到有监督和无监督的学习,由于近几年该领域发展迅猛,一些特有的学习手段和算法相继提出,因此将其看作一种单独的学习方法。
深度学习是机器学习研究中的一个新的领域,目的在于建立、模拟人脑进行分析学习的神经网络,模仿人脑的机制来解释数据,如图像、声音和文本等多媒体数据。深度学习是无监督学习的一种,其概念源于人工神经网络的研究,含有多隐层的多层感知器就是一种深度学习结构。深度学习通过组合低层特征形成更加抽象的高层表示其属性类别或特征,以发现数据的分布式特征。基于深信度网络提出非监督逐层训练算法,为解决深层结构相关的优化难题带来了希望,随后提出多层自动编码器深层结构。此外提出的卷积神经网络是第一个真正多层结构学习算法,它利用空间相对关系减少参数数目以提高训练性能。
目前,机器学习领域的研究工作主要围绕在以下三个方面:
1)任务研析???对一组预定任务的学习系统进行研究,改进执行性能并提高其有效性;
2)模型研发 ??研究人类学习过程并进行计算机模拟和分析,改进现有模型,提出新的更加有效的模型;
3)理论分析???从理论上探索各种可能的机器学习方法,给出独立于应用领域的高效算法。
机器学习算法的功能可粗略的分为四大类,即分类、聚类、预测和降维,可用的机器学习算法不下数百种,包括回归分析、判别分析、聚类分析、因子分析和主成分分析、贝叶斯分类、决策树、支持向量机、EM、Adaboost、人工神经网络及它们之间的一些集成算法等。其中的回归分析、判别分析、聚类分析等已在统计计算里进行了介绍,神经网络计算也在上一篇文章中进行了较多的讨论,下面仅对机器学习中最常用的一些特有算法,如决策树算法、支持向量机算法、朴素贝叶斯算法、最大期望算法、KNN算法和K均值算法等,进行一些思考性、原理性的简单介绍。
1)决策树(Decision Trees)算法
决策树是一个预测模型,代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若想有多个输出,可以建立独立的决策树以处理不同输出。
一个决策树包含三种类型的节点,即决策节点,机会节点和终结点。这里,每个决策树都表述了一种树型结构,由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时,递归过程完成。
决策树算法根据数据的属性采用树状结构建立决策模型,常常用来解决分类和预测问题。常见的算法有分类及回归树,ID3,C4.5,随机森林,多元样条回归等实际可用的一些算法。
2)支持向量机(Support Vector Machine,SVM)算法
SVM是一种監督式學習算法,广泛用于统计分类以及预测分析计算中。
SVM属于一般化线性分类器。这类分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区,因此支持向量机也被称为最大边缘区分类器。
SVM的主要思想可以概括为两点:① 针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能;② 基于结构风险最小化理论,在特征空间中建构最优分割超平面,使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定的上界。
3)朴素贝叶斯分类(Na?ve Bayesian classification)算法
朴素贝叶斯是一种基于贝叶斯定理与特征条件独立假设的概率分类算法,通过对象的先验概率,利用贝叶斯公式
其中P(A|B)是后验概率,P(B|A)是似然概率,P(A)是先验概率,P(B)是预测先验概率。
根据上述公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类别作为该对象所属的类别。朴素贝叶斯算法简单,快速,具有较小的出错率,对结果解释容易理解。
4)最大期望(Expectation–Maximization,EM)算法
在统计计算中,最大期望算法是在概率模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量,经常用在机器学习和计算机视觉的数据集聚领域。最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值;第二步是最大化(M),也就是最大化在E步上找到的最大似然的期望值从而计算参数的最大似然估计。M步上找到的参数然后用于另外一个E步计算,这个过程不断交替进行,进行改进,以寻求渐近最优结果。
5)K最近邻(k-Nearest Neighbor,KNN)分类算法
KNN分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别,则该样本也属于这个类别。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN方法虽然从原理上依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。
K-近邻算法的思想如下:首先,计算新样本与训练样本之间的距离,找到距离最近的K个邻居;然后,根据这些邻居所属的类别来判定新样本的类别,如果它们都属于同一个类别,那么新样本也属于这个类;否则,对每个后选类别进行评分,按照某种规则确定新样本的类别。
6)K-均值(K-means)算法
K-均值算法是输入聚类个数k,以及包含 n个数据对象的数据库,输出满足方差最小标准?k(k 数据对象划分为 k个 聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高,而不同聚类中的对象相似度较小。
k-means 算法的工作过程说明如下:首先从n个 数据对象任意选择 k 个对象作为初始聚类中心,而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的聚类,然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的 均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个 聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
从算法的表现上来说,它并不保证一定得到全局最优解,最终解的质量很大程度上取决于初始化的分组。由于该算法的速度快,因此常用的一种方法是多次运行k平均算法,选择最优解。
机器学习是继神经网络系统之后人工智能应用的又一重要研究领域,也是人工智能和神经网络计算的核心研究课题。对机器学习的研究及其进展,必将促使人工智能和整个科学技术的进一步发展。