目前,半监督机器学习方法不但在理论方面得到了深入地研究,而且在实践中已获得了广泛地应用。半监督学习的基本出发点是同时利用已标号和未标号样本进行学习,主要目的是借助隐含于未标号样本中的结构信息来提高学习性能。由于数据的结构信息通常可以用一个图来表达,所以以图表达为中心的半监督学习方法成为了当前的研究主流之一。图上的传播学习正是基于图表达的一类典型半监督学习方法,其主要思想是:图结点上的标号信息可以通过图路径从已标记(样本)结点传播到未标记(样本)结点,而连接两结点的图路径数量和路径长度可作为它们之间的一种相似度测量。最近,图上的传播学习方法已经成功渗透到分类、聚类、排序和降维等诸多研究领域。然而,无论是在理论方面还是应用方面,图传播方法仍存在一些关键问题有待于解决。例如,(1)当需要传播的对象是样本间的成对约束而不是样本的类别标号时,该如何进行约束传播?(2)当没有任何监督信息可以利用时,该如何来发掘和改造图传播方法?(3)图传播方法是否能作为一种数据预处理手段而不仅仅是作为一种特定的分类方法?(4)当传播图很大时,是否能在部分图而不是全局图上进行传播?针对以上这些问题,本文对图传播方法进行了深入的研究,并得到了如下四个方面的研究成果:1.把约束传播问题归结为一个核矩阵学习问题,并由此提出了核传播的概念。现有的标号传播算法不能对样本间的成对约束进行传播,为此,我们把该问题转化成一个核矩阵传播问题。核矩阵传播的主要思路是,首先通过求解一个小规模半定规划问题把用户提供的成对约束信息编码到一个小尺寸的“种子核”矩阵内,然后利用核传播公式把该种子核矩阵传播成为整个样本集上的全核矩阵。特别地,在某种意义下,标号传播方法能被解释为核传播方法的一个特例。相比于现有的同类型方法,我们的核传播方法在实验中表现出了更好的综合性能。2.提出了基于流形收缩的无监督数据预处理方法。传统的标号传播方法在无监督情形下将失效,为此我们提出了一种名为流形收缩的无监督数据预处理方法。一方面,流形收缩方法能够被直观地解释成为样本点在图上的一个随机行走(Random Walks)过程;另一方面,流形收缩方法相当于对原样本集进行了一个收缩映射,而且可以把此映射作为一种数据预处理手段。此外,作为一种新的无监督数据预处理技术,流形收缩方法不但能方便且自然地与核技巧、降维方法等相互结合,而且能从理论上保证更好的分类泛化能力。3.提出了基于模式移动的半监督数据预处理方法。在部分样本类别标号已知的情况下,传统的标号传播方法通常被作为一种特定的分类器来使用,这限制了在传播中进一步使用其它分类器的能力。为了能够把图传播方法的优势方便地结合到普通的监督型分类器中,我们提出了半监督模式移动的概念,同时把它作为一种新的半监督数据预处理手段。此外,我们还进一步提出了一种利用采样技术进行算法加速的方案,并由此自然地解决了模式移动算法中的外样本(Out-of-Sample)推广问题。实验结果表明,相比于一些半监督降维方法,我们提出的半监督模式移动方法具有一定的优势。4.提出了一种基于子图正则化的半监督图像检索方法。基于反馈的图像检索问题虽然可以作为一个普通的在线分类问题来对待,但它自身还具有小样本性、类不平衡性和实时性要求等特点。Lu等人[1]提出的基于全图正则化的支持向量机分类算法在应用到图像检索方面时没有考虑到类不平衡性和实时性等问题,为此,我们提出了一种基于查询子图(而非全图)正则化的半监督图像检索算法,称为偏拉普拉斯支持向量机(BLapSVM, Biased Laplacian Support Vector Machine)。实验结果表明,BLapSVM能较好地解决反馈图像检索中存在的小样本性、类不平衡性和实时性等问题。