关键词:
机器学习
图论模型
流形排序矩阵
图k均值
脉冲神经网络
摘要:
机器学习是人工智能的一个分支,其研究的目标是构建一个能够从数据中自主学习出一定的规律(或模式)并将此规律应用于后续数据处理的系统。作为一个基础性的学科分支,机器学习在许多领域有着重要的应用,例如生物信息学、人工智能、航空航天、现代医学等。图论作为一个数学分支,其在机器学习中的研究与应用近年来得到了快速的发展。基于图论的机器学习算法就是把机器学习的问题归结为图论的问题,然后利用图论理论进行分析和求解的一类学习算法。相比较于其他算法模型,基于图论的机器学习算法有着以下优势:一、图论作为一个数学分支,有着深厚的数学理论背景,这为对机器学习算法从理论上分析做了必要的准备。二、图论具有模型简单、概括力强的特点,这使得很多问题可以利用图论模型进行描述和求解。三、图论模型可以利用矩阵描述并利用线性代数和矩阵理论知识进行分析和求解,因此表达形式简洁但富有概括力,同时便于进行深入理论分析。四、基于图论谱分析的机器学习算法很多具有闭合的解析解表达式,或者可以利用凸优化理论进行求解,这样可以求得全局最优解,避免局部最优解。已有的基于图论的机器算法研究主要集中在两个方面:一个是基于图论的半监督学习算法,包括半监督分类算法、半监督降维等;二是基于图论的无监督学习算法,包括谱聚类算法、无监督降维算法等。虽然已有算法在很多应用中取得了成功,但仍有许多不足,概况说来有以下几点:一、图论的半监督学习算法已被成功应用于许多领域,其主要特点是能够利用极少量标记样本对大量未标记样本进行分类,这就减少了很多用于标记样本时所消耗的人力和财力等资源。但半监督学习多为直推式学习且/或预测新样本时运算量较大。监督学习的优势是能够在输入样本空间中构建一个监督模型,从而对已见样本和未见样本都能高效地进行直接分类;其缺陷是要构建一个具有很好泛化能力的模型往往需要大量标记样本进行训练。能否将二者的优势结合,利用极少标记样本在输入空间中构建出一个具有良好泛化能力的高效监督模型是一个很值得探讨的问题,具有很大的实用价值。本文在这方面进行了尝试。二、现有的聚类算法,如谱聚类,虽然能够在很多情况下取得较好的结果,但在应对高维非线性流形分布的数据时仍然有不足,具体表现为:对于不同流形分布出现交叠或有类间有大量歧义点时聚类结果往往不满意或者需要进行复杂的非光滑优化问题求解,从而需要很大的计算量和内存开销;更进一步,聚类算法对于每个类别,无法在给出类别标记信息的同时给出此类中最具代表性的样本点,而这一点在如视频或者文本自动摘要上有着重要应用。三、在处理时空分布数据(spatio-temporaldata)时,由于时空分布数据具有一定的空间分布特性,同时这种分布特性在时间上可能存在不断演化,而且此类数据的数据量一般较大。传统的机器学习算法(如svm)适合于处理静态的向量数据,其很难学习和描述此类时空数据中蕴含的这种复杂的、动态的时空交互演化关系。针对以上问题,本文主要工作和创新点可归结为以下几个方面:一、本文对基于图论的半监督学习算法localandglobalconsistency(lgc)进行了改进,使其具备“各向异性”的传播特性,即在高样本密度区域具有较快的标记信息传播,在低样本密度区具有较慢的标记信息传播,从而抑制类间区域的不正确标记信息传播。在此基础上本文提出了一种两步学习的新型监督学习框架,能够在极少的标记样本数量情况下在输入空间中构建并学习一个具有良好泛化能力的监督模型。二、受到lgc算法和流形排序算法的启发,本文把传统欧氏空间中点云中心概念拓展到黎曼几何中流形中心概念,提出了一种基于图论的k均值算法用于非线性流形聚类。该算法不仅对传统高斯分布类型数据(适合于经典k均值算法)具有很好的效果,而且对于(低维)流形分布的高维数据同样能够给出很好的聚类结果,同时给每一类选出一个最具代表性的样本点,这些代表点在数据集压缩及自动摘要上有着重要的应用。三、进一步,本文针对以上算法中(也是许多其他图论算法中)的关键排序矩阵的计算量大的特点,提出了一种时间和空间均为线性复杂度的快速算法,对于大样本集具有很好的可扩展性,并把该算法引入到神经网络系统结构的分析中,使得网络模型具有多种可视化效果,有助于更好地理解模型和数据。同时在已有工作的基础上本文拓展了一种新型时空数据(spatio-temporaldata)学习架构,NeuCube架构,使原有架构能更好地对任何时空数据进行处理,使早期事件预警以及时空模式识别性能具有较大改善。四、除此之外,本文还对图论机器学习算法中的一些其他问题进行了研究。例如,不同类间往往存在歧义点(也称“桥接点”),这会对很多流形聚类算法的性能造成严重影响。针对这种情况,本文给出了一种有效去除类间歧义点的算法。还有,非线性多变量向量值函数的拟合,常用的方法是多层神经网络或者单个分量