第1章 引言
1.1 机器学习理论
机器学习（machine learning ）是当前人工智能主要的研究发展方向之一。机器学习与认知科学、心理学、计算机科学等许多学科都有着密切的联系，涉及领域比较广，已经成功地运用于许多实际问题，并取得了不错的学习效果，如自动驾驶汽车、疾病预测、下棋和语音识别等[1]。在解决这些实际问题的过程中，机器学习技术被深入地进行分析和研究，得到了迅速发展，并产生了很多优秀的学习算法，如常用的八大机器学习算法：决策树算法[2]、随机森林算法[3]、人工神经网络算法[4]、支持向量机算法[5]、Boosting 与Bagging 算法[6， 7]、关联规则算法[8， 9]、贝叶斯学习算法[10， 11]以及EM 算法[12]。
近年来随着计算机及采样技术的发展，人们可以越来越容易地获取海量的高维数据，如何从这些数据中找出合理有效的信息并进行探索，已成为机器学习、数据挖掘等领域研究的热点问题。高维数据对传统的机器学习与统计分析提出了严峻的挑战，如导致所谓的“维数灾难”(curse of dimensionality)[13]，也就是说为保证学习仍能获得良好的性能，样本集的大小需随着问题维数(变量或特征数目)的增加呈指数增长。与之相关的另一个挑战问题为空空间现象[14](empty space phenomenon)，即高维空间本质上是稀疏空间，如标准正态分布N(0，1)在只有一维变量时，[1， 1]区间内包含接近70%的数据点。然而当变量维数增加到十维时，以原点为球心的单位超球内只包含0.02% 的数据。另外，当样本数目远小于维数时，将导致典型的小样本(small sample size)问题，从而*终影响学习算法的推广能力[15]。
大量认知科学的实验验证了很多高维数据确实存在较低的本征维数，且分布于高维空间中的一个低维子流形上。例如，在不同角度、不同光照情况下，同一个人的图像集就是一个以姿态、尺度、光照等为参数的低维子流形。这也更加表明对高维数据进行维数约简具有必要性。人眼能在瞬间认出多年未曾谋面的老同学，然而计算机识别却很难做到。神经生物学研究发现视感知系统具有某种特性的不变性，且整个神经细胞群的触发率可由少量维度的变量来描述，这也进一步表明视神经元的群体活动由内在的低维结构所控制[16]。
1.1.1 维数约简
给定的数据是由n个m维的数据向量xi组成，且该数据集的本征维数为(一般情况下)，其中本征维数为嵌入在D维高维空间的数据集X分布或接近于低维子空间或流形的维数d。维数约简的基本思想是通过线性或非线性变换把高维的数据集X映射到一个低维空间，从而获得d(一般d≥d)维的数据表示，同时尽可能地保持原高维数据的信息。
如此一来，维数约简技术不仅囊括了经典的主成分分析(principal component analysis， PCA)[17]和线性判别分析(linear discriminant analysis， LDA)[18]等方法，而且诸如压缩感知中的随机投影[19]、图像下采样等策略也自然地归属于上述维数约简定义的范畴。维数约简通常分为特征提取(如PCA 和LDA)与特征选择(如图像下采样)两类方法。
维数约简可在很大程度上避免维数灾难，使得学习任务（如分类或聚类等）更加稳定、高效，并产生更优的推广性能。实际中，对于成千或上万甚至更高维的数据而言，如何通过维数约简技术获得数据的有效表示已变得越来越重要，也更具挑战性，且要满足两个基本特性[20]：数据的维数得到一定程度的约简，可有效地识别出数据的重要成分、内在结构特征及隐变量等；另外，通过将数据降维至二维或三维进行可视化，人们可准确直观地感知与发现隐藏在数据中的内在结构与规律。
1.1.2 稀疏与低秩
压缩感知(compressed sensing， CS)与稀疏表示(sparse representation，SR)是由Candès等提出的一种新的理论框架[21]，*早被用于从低维观测信号中恢复出高维原始信号，其优化问题如下所述：
(1.1)
式中，表示范数，即向量中非零元素的个数；A∈ Rd×m为观测矩阵。该框架现已被广泛应用于信号与图像处理领域，如图像去噪、恢复(recovery)及超分辨率(supper-resolution)重建等，并取得了巨大成功。该理论框架表明：当感兴趣的信号是可稀疏表示的或具有可压缩性时，可以通过极少的采样或观测精确地重构该信号，也就是说，很多现实信号都拥有较多的冗余，类似的说法还有奥卡姆剃刀(Ockham’s razor)原理或*小描述长度(minimal description length)。稀疏表示已成为*近几年信号处理、机器学习、模式识别及计算机视觉等领域的一个研究热点。其实稀疏表示的概念早在1996 年Nature中就有涉及，将稀疏性正则引入到*小二乘问题中，计算得到具有方向特性的图像块，这样能很好地解释初级视皮层(V1)的工作原理[22]。另外，在同一年，著名的Lasso 算法[23]也被提出用于求解带有稀疏约束的*小二乘问题。
*近几年，衍生于压缩感知技术的低秩矩阵重建已成为机器学习、计算机视觉、信号处理、优化等领域*热的研究方向之一，并在图像与视频处理、计算机视觉、文本分析、多任务学习、推荐系统等方面得到了成功的应用[24]。矩阵恢复或填充可看成压缩感知理论由一维信号到二维矩阵的推广[25]。矩阵的稀疏性主要表现在两个方面：第一是矩阵元素的稀疏性，即矩阵非0元素的个数相对较少，也就是矩阵的范数；第二是矩阵奇异值(若为对称矩阵，则为特征值)的稀疏性，即矩阵奇异值中的非0元素的个数相对较少，也就是秩函数值较小。先看矩阵奇异值的稀疏性，即通常假定待恢复或填充的矩阵为低秩的，可通过矩阵的某些线性运算的结果由如下的优化问题精确地重构该矩阵：
(1.2)
式中，rank(.)为矩阵的秩函数；A(.)为一个线性算子。具体的低秩矩阵填充问题可表述为如下的形式：
(1.3)
式中，Ω为已知元素下标的集合。PΩ()Z 定义为如下的形式：
若同时考虑矩阵元素与矩阵奇异值的稀疏性，可得到两类*近几年非常流行的问题模型：鲁棒主成分分析(robust principal component analysis， RPCA)或稀疏加低秩矩阵分解(sparse and low-rank matrix decomposition)模型和低秩表示(low-rank representation， LRR)模型。鲁棒主成分分析模型可由如下的优化问题描述：
式中，λ>0 为正则参数；为一种特定的正则策略，如用于对高斯噪声建模的Frobenius 范数[26， 27]，即，处理少量较大幅值噪声的l0范数[26， 28]，及可有效处理列噪声或奇异点的l2，0范数[29， 30]等。上述三类不同的噪声分别如图1.1所示。
然而上述的式(1.4)隐式地假设观测数据的潜在结构为单独一个低秩线性子空间[29， 31， 32]。很多实际数据都分布于多个线性子空间的并集中，且任何数据点属于某个子空间的关系也是未知的。*近，有一种低秩加稀疏矩阵分解的拓展模型被提出，并被称为低秩表示模型[29， 30]，即结合子空间分割与噪声识别于一个框架中用于处理多子空间问题。该低秩表示模型有如下所述的形式：
(1.5)
图1.1 三类不同的噪声类型[29]
式中，Z∈Rm×n被文献[30]称为给定数据X的*低秩表示；D∈Rm×m为一个线性张成数据空间的字典，m为字典中原子或基的数目。
从本质上来讲，具有稀疏或低秩结构的数据可由很少的采样来完成该信号或数据的重建或鲁棒性恢复。因为稀疏性与低秩性假设同样适用于高维数据的分布特点，所以压缩感知技术非常适合于处理高维数据问题，可有效地避免传统机器学习与统计分析理论的不足。
1.1.3 半监督学习
传统的机器学习方法主要分为两大类：监督学习(supervised learning)和无监督学习(unsupervised learning)[33]。其中前者假设已有一些数据输入及其相应的输出，其目的为学习一个映射函数，使得该函数可预测新数据样本的输出，典型的问题有分类与回归；而无监督学习假设仅有一些数据输入而没有任何监督信息的指导，其目的是发现隐藏在数据中的某些性质，典型的问题包括聚类、概率密度估计及数据维数约简。有时标签数据不足以用于监督学习的训练，而采用无监督学习又会浪费标签数据中包含的信息。针对该问题，人们提出了半监督学习(semi-supervised learning， SSL)[33]，它能同时利用少量标签数据的信息和大量未标记数据中的隐含信息，达到比仅使用一种数据信息更好的学习效果，在理论和实践中已经引起了广泛的兴趣。文献[34]的研究表明半监督学习也非常符合人类的学习方式。
SSL又称为从标签和无标记数据中学习，是机器学习、数据挖掘与计算机视觉等领域中的一个研究热点[33]。传统的监督学习仅使用标签数据来进行训练，然而获取大量的标签数据通常很难，代价很高且需要耗费一定的人力和物力，还需要有经验的专家来标注。虽然主动学习(active learning)可有效地减少标注数据的代价，但是与传统的监督学习一样，它也不能利用无标签数据的信息。然而随着数据采集技术和计算机硬件技术的发展，收集大量的无标签样本已非常容易，SSL可同时利用少量标签数据和大量无标签数据来进行学习，以半监督分类为例，通过无标签样本和有标签样本一起构建性能更好的分类器[34]。另外，相对于标注数据，获得辅助信息(side information)，如成对约束(pairwise constraint)相对更加容易。成对约束表明相应的目标样本是属于同类或异类的，一般称之为Must-link(ML)或Cannot-link (CL)[35-37]。与半监督学习类似的一种方法是直推式学习(transductive learning)，它假定未标注样本为测试数据，其学习的目的是在那些无标签样本上取得*佳的推广能力。换句话说，SSL是一个开放的系统，即对任何未知的样本都能进行预测；而直推式学习则是一个封闭的系统，在学习时就已经知道了需要预测的测试数据[38]。
目前，SSL主要基于两种基本的假设，即聚类假设(cluster assumption)和流形假设(manifold assumption)。其中，聚类假设的内容为处在相同类簇中的样本有较大的可能性拥有相同的标签。由此假设可知，决策边界应该尽量通过数据分布较为稀疏的地方，从而避免把同一稠密类簇中的数据点分到决策边界两侧，即可表述为低密度分离(low density separation)：决策分界线应该在低密度分布区域。典型的方法主要有直推式SVMs(TSVMs)[39， 40]及其凸放松算法[41， 42]。流形假设的内容是所有数据位于或近似位于高维空间中的一个潜在低维子流形上。与聚类假设着眼于整体特性不同，流形假设主要考虑模型的局部特性，有很多种SSL 方法利用图拉普拉斯去刻画数据固有的几何分布结构，典型的方法有高斯随机场[43](Gaussian random fields， GRF)、局部与全局一致[44](local and global consistency，LGC)和流形正则[45， 46](manifold regularization)等。*近，Li 等[47]利用成对约束假设和聚类假设共同应用于分类问题，其中成对约束假设的内容为ML 约束的未标注数据点应为同类，而CL 约束的未标注实例应分到不同的类中。
1.2 压缩感知理论
1.2.1 压缩感知的研究意义
展开
