论文部分内容阅读
基于范数定义的度量学习是机器学习、模式识别领域的基础性工作之一。最为常用的是基于L2范数的欧氏距离和马氏距离,因其易于求解(L2范数可微)且符合人类直觉,该范数被广泛应用于模式的相似性度量并据此设计算法,其中较为著名的大间隔学习机有:基于欧式度量的传统支持向量机(Support Vector Machine,SVM),广义特征值求解的近似支持向量机(Proximal Support Vector Machine via Generalized Eigenvalues)和由马氏距离度量的大间隔最近邻分类器(Large Margin Nearest Neighbor,LMNN),最大最小间隔学习机(Maximin Margin Machine,M~4),最大最小概率学习机(Minimax Probability Machine,MPM)等。然而,采用L2范数度量的学习机,存在两个主要问题:1)L2范数的不鲁棒性(为方便模型求解,人们多采用范数平方取代模型中的平方根项,这无疑会放大噪声样本的影响);2)高阶优化问题(也是因为平方操作,使得问题的求解规模至少是二次规划)。相对于L2范数,L1和L∞更为鲁棒且导出的问题多是线性规划;但由于众所周知的不可导性,无法通过如L2范数的梯度方法来获得点到平面的解析表达式,无法解析描述间隔,其应用不可避免地受到限制。本文针对以上不可导范数,从监督信息利用角度,进行了全监督、无监督和半监督的算法设计,主要工作如下:1.提出了无穷范数大间隔分类器Inf SVM。首先,注意到无穷范数不可导的事实,放弃经典的梯度和次梯度方法,从范数对偶角度导出了无穷范数的点到平面距离公式和投影公式。其次,基于点到平面公式导出无穷范数的间隔,恰可通过该范数的对偶来刻画。通过最大化间隔,并同时最小化经验误差,设计了Inf SVM,导出的问题可通过线性规划求解。它具有如下特点:(1)继承了SVM几何解释;(2)只需要求解一个线性规划,训练时间更短;(3)比SVM更为鲁棒;(4)在人工和UCI数据集上实验,验证了其分类精度达到甚至超过SVM。2.提出了无监督的L1k PC聚类算法。针对经典的L2范数k PC(k-Plane Clustering),提出了目标和约束同是L1范数的L1k PC算法。该方法的优势在于:1)相对于现有的拟k PC聚类算法(为利用簇间信息,用SVM的不等式约束取代k PC的L2范数约束)几何解释不清晰问题,L1k PC与k PC的一样,几何解释明确;2)提出了目标和约束均为L1范数的优化方法,即将非凸优化问题按L1凸壳划分为多个凸的子问题,每个子问题均可通过线性规划求解,避免了现有的高阶优化问题,如二次规划、特征方程、线性方程组等。据我们所知,该求解方法是首次提出;3)在人工数据集、UCI和人脸数据库上,实验验证了该方法在聚类能力、训练时间、鲁棒性方面的性能。3.提出了半监督聚类算法Semi-L1k PC。利用少量的有标样本和大量无标记样本且兼顾平面聚类的平面原型(Plane-Prototype)特点,在工作2的基础上,设计了半监督聚类算法Semi-L1k PC。从每类仅有一个已标样本出发,在人工数据集和UCI数据集上的实验表明:(1)在XOR(Exclusive OR)问题上,平面型的聚类方法的聚类准确率均显著高于k-means算法,因为k-means是以点为原型的聚类方法,其不适合平面分布型的数据集;(2)在少量监督信息引入后,半监督型聚类方法semi-k PC和semi-L1k PC比其他聚类方法的聚类准确率更高;(3)采用L1范数的semi-L1k PC比semi-k PC的鲁棒性更好.4.针对林火识别中的不平衡分类问题,提出了L1BSVM(L1 norm Biased SVM)算法。有别于其它分类方法,森林火灾早期预警系统中,期望能够在着火面积尽可能小的时候,就能够将图像中的火焰区域识别出来。此外,由于真实系统中的数据采集和数据传输均在野外,待处理数据不可避免存在噪声。针对这种含噪且极端不平衡的图像数据,利用多个颜色空间信息,在工作1的基础上,设计了Imbalanced Inf SVM算法。实验效果表明:(1)在大多数林火数据集上,Inf SVM的训练时间短且测试精度高;(2)在林火数据集的正负比例达到高度不平衡(如1:50以上)时,提出的L1BSVM算法能获得最高的林火识别率。