在数据挖掘和机器学习领域,为非独立且同分布(independent and identically distributed,简称IID)数据构建学习模型是近年来出现的热门研究主题^[1].为了有效地解决非IID数据学习问题,研究者提出了领域适应学习(domain adaptation learning,简称DAL)^[2]方法.该方法利用某些不同但相关的源(或辅助)领域数据的有监督学习来实现目标领域数据分类.DAL在许多实际应用中有较广泛的需求,并逐渐得到研究者的大量关注^[2-9].目前已提出大量学习方法以解决视频概念检测^[4]、文本分类^[3]、人脸识别和图像标注^[7]等领域适应问题,其中大多数方法侧重于统计分类器的适应,即所谓归纳学习,而对于演绎适应学习,鲜有相关研究工作开展.直观上来说,演绎DAL方法在具体实践中可取得更优的效能.另外,现有DAL方法同样需要来自源领域充足的标签训练数据以实现知识迁移,换句话说,若标签训练数据不足或有限,DAL性能在具体应用中则会在一定程度上有所下降.

在过去的几年里,基于图的半监督学习(semi-supervised learning,简称SSL)方法因其优雅的数学形式和独特的效能,已发展成为机器学习领域热门研究主题之一^[10].这些SSL方法一般都假设训练数据和测试数据抽取自某个相同的特征分布或特征空间,而当数据分布发生变化时,这些利用先验信息习得的模型需要再次采用新的训练数据进行重构.在DAL中,如果忽略领域差异,将源领域数据作为带标签的训练样本和目标领域无标签数据作为测试样本,DAL则降级为SSL问题.直观上来说,SSL算法可被直接用于领域适应问题,其间的细微差别在于:(1) 在SSL中带标签的训练数据量相对于DAL中的较小;(2) SSL中训练数据和测试数据均取自某个相同但未知的数据分布,而DAL则来自不同但相关的数据分布.已有几项研究工作将SSL扩展为DAL方法:Dai等人^[11]提出一种基于期望最大的DAL算法,除了利用领域间Kullback-Leibler散度^[6]最小化来估计标签样本和无标签样本间平衡参数外,该方法等价于半监督期望最大算法^[12];文献^[13]中,Xing等人采取在最近邻图上传播标签的方法,提出一种桥接精炼DAL算法,其相似于基于图的SSL算法.但是研究结果得知,基于图的SSL算法性能在一定程度上依赖于图边的权值,其通常采用k-最近邻(k-nearest neighbor,简称k-NN)或Gaussian核相似性(Gaussian kernel similarity,简称GKS)^[14,15]等方法计算取得,而且,传统SSL方法通常对噪声(或桥接点)^[14]和缺失数据(如人脸数据中的遮罩)^[16]较敏感,会导致将标签错误地传播到不同类.为此,Wang等人^[14]提出一种线性邻居传播算法(linear neighbor propagation,简称LNP),该方法虽然能通过修正数据点与其k-NN间的权值来改善传统k-NN方法的性能,但是其仍然依赖传统的欧式距离来预定义数据点的k-NN,换句话说,LNP依然未能彻底解决传统SSL方法中如何有效确定数据点的邻居数这个根本问题.

近年来,稀疏表示(sparse representation,简称SR)^[16]技术在机器学习和模式识别(特别是在人脸识别^[16-19]和图像分类^[20])等领域得到有效应用,并展现出其独特的鲁棒性能.针对上述传统图构建存在的问题,Fan等人^[18]提出一种稀疏正则化半监督分类算法;文献^[17]提出采用稀疏表示来度量样本间的相似性,以实现样本间的标签传播;与文献^[17]思想相似,文献^[21]提出一种基于稀疏表示的SSL方法,通过新构建的稀疏图实现标签的有效传播;Cheng等人^[22]明确提出一种鲁棒的稀疏(或l₁-范最小)驱动的有向图(或l₁-图),并将该图分别应用于普聚类、子空间学习和SSL,取得了良好的效果.

本文基于图SSL模型,利用核稀疏表示技术,提出了一种稀疏标签传播DAL算法(sparse label propagation domain adaptation learning,简称SLPDAL):首先,基于领域间数据分布均值差最小化准则寻求一个优化的核空间,并将领域数据嵌入到该核空间;然后,在该嵌入核空间,基于l₁-范最小化准则计算各领域数据的核稀疏重构系数;最后,通过保留领域数据间核稀疏重构系数约束,实现源领域数据标签向目标领域传播.从上述分析来看,在数据图的构建上,虽然本文方法与文献[17,18,21-23]具有相似之处,但明显不同的是:现有方法都是针对IID数据在原始输入空间(如文献^{[17,18,21,22]})或某个核空间(如文献^[23])构建一个用以标签传播的稀疏图;而本文方法是针对非IID数据学习问题,在一个基于分布差最小优化的再生核Hilbert空间(reproduced kernel hilbert space,简称RKHS)构建该稀疏图.特别地,与传统方法相比,SLPDAL方法所具有的优势在于:

(1) 在继承和发展传统的基于图的SSL方法优点的基础上,利用核稀疏表示技术和领域数据分布差最小化准则,提出一种鲁棒有效的全局和局部一致正则化DAL方法SLPDAL,实现源领域数据标签向目标领域传播,并将该方法拓展为多核学习模型MKSLP.

(2) 由于稀疏表示能保留自然的判别信息,使得SLPDAL方法在解决DAL问题时只需要相对更少的带标签数据,并且通过使用稀疏集中索引(sparsity concentration index,简称SCI)^[16],SLPDAL方法能够自动消除噪声数据和恢复缺失数据.

(3) 在SLPDAL方法中,标签传播图模型的构建准则为领域数据的核稀疏表示,而该准则一般优于传统SSL方法中采用的最近邻准则,尤其是对于高维小样本数据集的学习.与传统SSL方法中数据近邻和图边权值的计算分开完成不同,本文方法中邻居大小和图边权值通过l₁-范优化过程来一步确定,使得领域中不同样本具有不同的近邻数,能够增强本文方法对复杂数据分布学习的自适应性.

(4) 由于所提出的方法框架模型所具有的一般性,在一定的条件变换下,许多现有的SSL方法和DAL方法能被该模型所恢复.如在忽略领域差条件下,该方法模型能够简单地应用于基于图的SSL问题.

由于基于图Laplacian正则化SSL^[3]和本文方法的紧密关系,下节将首先讨论基于图的SSL模型.

1 图Laplacian正则化SSL

一般来说,存在两种SSL任务:1) 演绎学习(或直推学习(transductive learning)),其仅旨在预测无标签顶点的分类标签^[14];2) 归纳学习,其试图归纳出一个在整个样本空间具有最低误差率的决策函数^[15].显然,归纳学习困难且复杂^[14],因此,本文重点关注半监督演绎学习模型.研究结果表明,SSL问题的关键是先验一致性^[15],也称聚类假设或流形假设,其假设相邻数据点可能具有相同标签或具有相同结构(如聚类或子流形^[24])的数据具有相同标签,前者为局部假设,而后者为全局假设.近年来,在SSL方面取得的一个杰出成就就是基于图的SSL模型,其将整个数据集建模为一个图结构G=(V,E),其中,V为顶点集,E为边集.每个边e_ijÎE被赋予一个非负权值w_ij≥0,以反映数据点对i和j间的相似性.图G可以为有向(即w_ij¹w_ji)或无向(即w_ij=w_ji),本文仅关注无向图的情况.

给定数据集X={x₁,x₂,…,x_l,x_l+1,…,x_n}Ρ^d和标签集L={1,2,…,c},其中,前l个点x_i(1≤i≤l)标签为y_iÎL,余下的n-l个数据点x_u(l+1≤u≤n)无标签,每个数据点x_i均采样自某个固定但未知的分布,则基于图的SSL旨在基于由数据集X构成的图G寻求c个优化的分类函数f^j(1≤j≤c),且满足:1) 优化函数的输出应接近图中带标签顶点的标签值;2) 优化函数的输出应在整个图上平滑.从而,基于图的SSL一般框架旨在最小化:

$J(f) = \lambda \sum\limits_{j = 1}^c {\sum\limits_{i = 1}^l {\delta ({f^j}({x_i}),{y_i})} } + \beta \sum\limits_{j = 1}^c {R({f^j})} $

(1)

其中,d(×,×)表示损失函数(如hinge损失函数或平方损失函数),以度量标签数据的预测值和期望值间的不一致性; R(f^j)为惩罚正则项,以约束函数f^j在本质数据流形上的平滑性;l和b为两个正则化参数,以分别控制损失和平滑项间的平衡.惩罚正则项可采用如下一般形式:

R(F)=tr(F^TQF) (2)

其中,F=(F¹,F²,…,F^c)Ρ^nxc为类指示矩阵,F^j=[f^j(x₁),f^j(x₂),…,f^j(x_n)]^T,Q为一个nxn平滑矩阵.

定义1(图Laplacian正则化). 如果Q=L且Qe=0,则R(f)称为一阶图Laplacian正则化,其中L=D-WΡ^nxn为图Laplacian,W=[w_ij]_nxn为图边权值矩阵,D=diag(d₁,d₂,…,d_n)为一对角度矩阵,其中,${d_i} = \sum\nolimits_j {{w_{ij}}} {\rm{,}}$e为一n-维全1

向量;如果Q=(I-W)^T(I-W),且Qe=0,则称R(f)为二阶图Laplacian正则化.

如果选d(×,×)为平方损失函数,R(f)为基于Laplacian算子的图Laplacian正则化,则公式(1)可描述为

min ltr((F-Y)^TC(F-Y))+btr(F^TQF) (3)

其中,YΡ^nxc为类标签矩阵,且若x_i被标识为y_i=j,则Y_ij=1;否则,Y_ij=0.QΡ^nxn称为图Laplacian,CΡ^nxn为对角矩

阵,其前l个对角元素C_ii=C_l>0(1≤i≤l),余下对角元素C_ii=C_u≥0(l+1≤i≤n),C_l和C_u为两个参数.可以很容易地推导出公式(3)的解析解为

F=l(lC+bQ)^-1CY (4)

从而x_i(l+1≤i≤n)的预测标签由下式确定:

${y_i} = \arg \mathop {\max }\limits_{1 \le j \le c} {F_{ij}},{\rm{ }}l + 1 \le i \le n$

(5)

图Laplacian Q和(或)对角矩阵C在不同设置条件下,现有大多数基于图的SSL方法能够被统一到公式(3)框架,例如在文献^[25]中,Q设置为一个组合一阶图Laplacian且C_l=¥,C_u=0;在文献^[26]中,Q被设置为规范化一阶图Laplacian且C_l=C_u=1.以上两种图Laplacian均基于聚类假设,而在文献^[27]中,Q被设置为基于局部学习假设的二阶图Laplacian且C_l=1,C_u=0;在文献^[14]中,Q被设置为基于局部线性嵌入思想的二阶图Laplacian且C_l=C_u=1;在文献^[28]中,Q被设置为混合图Laplacian.

2 稀疏标签传播DAL 2.1 问题描述

对于DAL问题,本文将训练领域定义为源领域,其中有充足的带标签训练数据;将测试领域定义为目标领域,其中带标签的数据不存在或非常有限.对于一个模式分类问题,一个领域D由某个潜在的真实数据分布P(x,

y)给出,其中,xÎX为样本集,yÎY为相应的类标签集.对于DAL,无标签的测试数据集${X^t} = \{ (x_j^t)\} _{j = 1}^m,x_j^t \in X{\rm{,}}$抽取自目标领域D^t,带标签的训练数据集${X^s} = \{ (x_i^s,y_i^s)\} _{i = 1}^n,x_i^s \in X,y_i^s \in Y$抽取自某个与D^t不同但相关的源领域D^s.

令源领域数据分布P^s(x,y)=P^s(y|x)×P^s(x)和目标领域数据分布P^t(x,y)=P^t(y|x)×P^t(x)是两个潜在的真实数据分布,且P^s(x,y)¹P^t(x,y).事实上,绝大多数DAL方法均假设存在两个不同但高度相关的领域^[3,5].DAL的关键思想是,通过某种分布变换技术来减小P^t(x,y)和P^s(x,y)间的差异^[2,3,6].在DAL研究中,常用的分布距离度量方法包括基于熵概念的Kullback-Leibler散度^[5]和基于统计概念的最大均值差(maximum mean discrepancy,简称MMD)^[29]等.现有研究结果显示,MMD度量准则能够更有效地估计在某个再生核Hilbert空间两个分布间的距离.

通过某个非线性映射f:¡^d®H,可将原始空间问题变换为再生核Hilbert空间(RKHS) H中的问题^[30].对于某个恰当选择的映射f,在空间H中,内积á×,×ñ算子定义为áf(x₁),f(x₂)ñ_H=K(x₁,x₂),其中,x₁,x₂ÎX,且K(×,×):XxX®¡为一

半正定核函数.在RKHS中,度量两个分布间距离的MMD可定义如下:

定义2(MMD)^[29]. 设p和q为定义于领域D上的分布,令F为某个函数类,且f(ÎF):X®¡.

给定观测集${X^s} = \{ (x_i^s,y_i^s)\} _{i = 1}^n$和${X^t} = \{ (x_j^t)\} _{j = 1}^m{\rm{,}}$MMD及其经验估计定义为

$\left. \begin{array}{l} MMD[F,p,q] = \mathop {\sup }\limits_{f \in F} ({E_{{X^s} \in p}}[f({x^s})] - {E_{{X^t} \in q}}[f({x^t})])\\ MMD[F,{X^s},{X^t}] = \mathop {\sup }\limits_K \left( {\frac{1}{n}\sum\limits_{i = 1}^n {\phi (x_i^s) - } \frac{1}{m}\sum\limits_{j = 1}^m {\phi (x_j^t)} } \right) \end{array} \right\}$

(6)

基于MMD准则和稀疏保留假设^[19],本文提出SLPDAL算法,其将传统的基于图的SSL算法有效扩展到DAL领域.

2.2SLPDAL算法

本节将形式化地提出SLPDAL算法.令${X^s} = \{ x_1^s,x_2^s,...,x_n^s\} $和${X^t} = \{ x_1^t,x_2^t,...,x_m^t\}$为分别来自源领域和目标领域的两个数据点集.设$X = \{ \{ x_i^s\} _{i = 1}^n,\{ (x_j^t\} _{j = 1}^m\}$代表¡^d空间n+m个数据点,$\bar L = \{ + 1,- 1\} $ (1≤i≤n)标记为${L_i} \in \bar L{\rm{,}}$其余数据点x_jÎX(n+1≤j≤n+m)无标签.SLPDAL的目标是,试图预测数据点x_j的标签

值.实现该任务需要3个步骤:(1) 领域分布核均值匹配;(2) 数据的核稀疏表示;(3) 稀疏标签传播以实现源领域标签向目标领域迁移.

2.2.1 领域分布核均值匹配

当样本数据映射到高维甚至无限维空间时,定义2中的MMD能够捕捉到数据的高阶统计特征^[4].基于此,Gretton等人^[29]提出核函数f的选取原则,即,f为RKHS中的单位球.这样,两个领域分布距离度量可以简单地表示为RKHS中数据分布的均值差,即,源领域和目标领域间最小分布距离为

$\mathop {\min }\limits_K dist({X^s},{X^t}) = \left\| {\frac{1}{n}\sum\limits_{i = 1}^n {\phi (x_i^s)} - \frac{1}{m}\sum\limits_{i = 1}^m {\phi (x_i^t)} } \right\|_H^2$

(7)

进一步简化为

$\mathop {\min }\limits_K dist({X^s},{X^t}) = tr({X^\phi }{\Pi _{st}}{({X^\phi })^T}) = tr({\Pi _{st}}{K_{XX}})$

(8)

其中,${X^\phi } = [\phi (x_1^s),\phi (x_2^s),...,\phi (x_n^s),\phi (x_1^t),\phi (x_2^t),...,\phi (x_m^t)],{K_{XX}} = {({X^\phi })^T}{X^\phi },{\Pi _{st}} \in {{\rm{R}}^{(n + m) \times (n + m)}}$定义为

${\Pi _{st}}(i,j) = \left\{ {\begin{array}{*{20}{l}} {\frac{1}{{{n^2}}},{\rm{ if }}{x_i},{x_j} \in {X^s}}\\ {\frac{1}{{{m^2}}},{\rm{ if }}{x_i},{x_j} \in {X^t}}\\ { - \frac{1}{{nm}},{\rm{ otherwise}}} \end{array}} \right.$

(9)

现有研究指出:高斯核映射能够提供一个有效的RKHS嵌入,使得领域间分布距离的一致性度量得以实现^[30].为此,本文采用高斯核函数${k_\sigma }(x,z) = \exp \left( { - \frac{1}{{2{\sigma ^2}}}||x - z|{|^2}} \right)$作为Hilbert空间映射的再生核函数,其中,x,zÎX,

s指核带宽.

定理1^[31]. 假设A为一个对称矩阵且A=PSP^T,其中,P包含矩阵A的正交特征向量列,S=diag(s₁,s₂,…,s_n)为相应特征值构成的对角矩阵,b为一个正常数,则公式(10)中半定规划问题和公式(11)中线性规划问题具有相同的优化解,即,K=PGP^T,其中,G=diag(g₁,g₂,…,g_n).

$\left\{ \begin{array}{l} \mathop {\min }\limits_K tr(AK)\\ {\rm{s}}{\rm{.t}}{\rm{. }}0\underline \prec K\underline \prec I,tr(K) = b \end{array} \right.$

(10)

$\left\{ \begin{array}{l} \mathop {\min }\limits_{{\gamma _i}} \sum\limits_{i = 1}^n {{\gamma _i}{\sigma _i}} \\ {\rm{s}}{\rm{.t}}{\rm{. }}0 \le {\gamma _i} \le 1,\sum\limits_{i = 1}^n {{\gamma _i}} = b,1 \le i \le n \end{array} \right.$

(11)

证明:关键步骤是证明矩阵A和K能被联合对角化,详细过程可参见文献^[31].

令A=P_st和K=K_XX,我们可以通过求解公式(11)中线性规划问题得到公式(8)的优化解K^*,这可以利用现存的半定规划软件包来高效地实现.

2.2.2 数据的核稀疏表示

本阶段关注如何通过数据的稀疏表示来构建一个加权图G={X,S},其中,X为数据集构成的顶点集,S为边权值,每条边s_ijÎS代表数据点对x_i和x_j间的稀疏关系.如下两条理由能够说明为何数据的稀疏表示适于图的构建:

1) 在典型的k-邻居图构建中,稀疏性具有重要地位:一方面,稀疏性刻画了数据分布的全局性;另一方面,稀疏性能够有效节省计算成本和存储空间.但是,传统的基于k-NN和高斯函数构建的k-邻居图的稀疏性依赖于人工设定的邻居数和高斯核参数s.文献^[14]研究指出:在只有少量标签数据的情况下,难以可靠地选取模型参数,即,难以确定优化的参数s.为此,需要寻求一种更可靠、更稳定的方法来构建图模型G.

2) 最稀疏的表示自然地具有判别性.因为我们的最终目标是对目标领域数据实现分类,所以我们期望图数据包含尽可能多的判别信息,即,来自相同类的两个数据点通过边连接起来.对于典型的k-NN图,上述所期望的属性严重依赖近邻准则在原始空间实施效果的好坏^[14],然而,对于原始高维数据(如人脸图像数据),最近邻准则通常不能取得较好的性能.相比之下,近年来研究^[16]显示:稀疏表示具有自然的判别力并能在高维数据环境下取得较好的性能,而且该判别力仅与类数紧密相关,而与样本数无关.因此,基于SR构建的图模型在无需源领域大量标签数据的情况下能够包含更多的判别信息.

基于以上原因,本文试图避开传统的基于图的SSL方法中所采用的点对间关系度量方法,而采用SR来重构各数据点x_iÎX.为此,我们首先在RKHS中通过求解如下修改的l₁-范最小化问题来为各数据点x_i寻求一个稀疏重构权值向量s_i:

$\mathop {\min }\limits_{{s_i}} C||{s_i}|{|_1} + ||\phi ({x_i}) - {X^\phi }{s_i}||_2^2 = \mathop {\min }\limits_{{s_i}} C||{s_i}|{|_1} + L({s_i},K)$

(12)

其中,

· 核K为公式(8)中寻求的优化解;

· C为正则化参数,以控制重构稀疏性和重构补偿间的平衡;

· $L({s_i},K) = 1 + {s_i}{K_{XX}}{s_i} - 2s_i^T{K_X}({x_i}){\rm{,}}$其中,K_XX为一个(n+m)x(n+m)矩阵,其中元素{K_XX}_ij=K(x_i,x_j);K_X(x_i) 是一个(n+m)x1向量,其中元素{K_X(x_i)}_j=K(x_j,x_i);s_i=[s_i1,s_i2,…,s_i(i-1),0,s_i(i+1),…,s_i(n+m)]^T是一个(n+m)-维列向量,其中,第i个元素等于0表示x_i从X中移除,s_ij(j¹i)表示样本x_j对x_i的重构贡献度.本文进一步约束$\sum\nolimits_{j \ne i} {{s_{ij}}} = 1$且s_ij≥0.

可以通过KOMP算法^[32]来求解公式(12)中核稀疏表示问题.在求得所有数据点的重构稀疏向量${\hat s_i}$(1≤i≤n+m)后,即可构建稀疏权值矩阵$S = [{\hat s_1},{\hat s_2},...,{\hat s_{n + m}}]{\rm{,}}$进而可构建一个稀疏图模型G={X,S},其中,X为训练样本集,S为边权值矩阵.值得说明的是,S中元素s_ij并非数据点对x_i和x_j间简单的相似性度量,矩阵S本质上有别于传统的图正则化算法(如LPP(locality preserving projection)^[33])中的权值矩阵.对于基于图的DAL问题,采用稀疏矩阵S作为图权值矩阵具有如下的有效属性:(1) 在稀疏矩阵S中,各权值向量s_i均遵从重要的对称性,即旋转不变性(满足公式(12)约束)和转换不变性(满足约束$1_{n + m}^T{s_i} = 1{\rm{,}}$其中,1_n+m代表(n+m)x1维列向量),使得权值矩阵S能够在一定程度上反映数据的本质几何属性;(2) 即使在无类标签的情况下,权值矩阵S中也能自然地保留数据的判别信息.

2.2.3 从标签数据到无标签数据的稀疏标签传播

本节,我们将利用公式(12)构建的核稀疏图和一个迭代过程来有效地解决源领域数据x_iÎX^s的标签向目标领域数据x_uÎX^t传播的问题.设F表示定义于样本集X上的分类函数集,且"fÎF,则可赋予每个数据点x_i一个实值f,无标签数据x_u的标签由f_u=f(x_u)的符号确定.在每次迭代中,使每个数据从其稀疏重构对象中“吸收”部分标签信息,且保留其初始状态的部分标签信息.这样,在第t+1次迭代时,x_i的标签为

$f_i^{t + 1} = \alpha \sum\nolimits_{j \ne i} {{M_{ij}}f_j^t} + (1 - \alpha ){y_i}$

(13)

其中,0<a<1控制x_i从其重构对象“吸收”标签信息部分,M_ij=(S+S^T-S^TS)_ij.令y=(y₁,y₂,…,y_n+m)^T且y_i=L_i(1≤i≤n),

y_u=0(n+1≤u≤n+m).${f^t} = {(f_1^t,f_2^t,...,f_{n + m}^t)^T}$为在第t次迭代的预测标签向量,f⁰=y.公式(13)迭代方程重写为

f ^t+1=aMf ^t+(1-a)y (14)

本文将采用公式(14)来更新各数据对象的标签直至收敛,即,数据的预测标签在经过几次迭代后不再发生变化.

定理2. 公式(14)中计算的序列{f^t}收敛于下式:

f ^*=(1-a)(I-aM)^-1y (15)

证明:由公式(13)和初始条件f⁰=y可得:

${f^t} = {(\alpha M)^{t - 1}}y + (1 - \alpha )\sum\limits_{i = 0}^{t - 1} {{{(\alpha M)}^i}} y$

(16)

显然,矩阵M的谱半径满足r(M)≤1,同时,0<a<1,从而可得$\mathop {\lim }\limits_{t \to \infty } {(\alpha M)^{t - 1}} = 0$,进而,

$\mathop {\lim }\limits_{t \to \infty } \sum\limits_{i = 0}^{t - 1} {{{(\alpha M)}^i}} = {(I - \alpha M)^{ - 1}}{\rm{,}}$

其中,I为n阶指示矩阵(identity matrix).显然,序列{f^t}收敛于

${f^*} = \mathop {\lim }\limits_{t \to \infty } {f^t} = (1 - \alpha ){(I - \alpha M)^{ - 1}}y$

(17)

由于在分类中我们仅用f_i的符号去确定数据点x_i的标签,因此,衡量1-a>0不影响f^*=(I-aM)^-1y的符号变化,从而定理2得证.

根据定理2,以f^*作为分类函数使得SLPDAL成为“一站式”算法,即,只需一步就能预测所有数据标签.

下面,将SLPDAL算法拓展为多分类问题:设有c个分类,标签集为$\bar L = \{ 1,2,...,c\}$,令P为(n+m)xc矩阵集,其中,矩阵元素为非负的实数值.任意矩阵$F = [F_1^T,F_2^T,...,F_{n + m}^T] \in P$对应X上的一个特定的分类,即,数据x_i分类为y_i=argmax_j≤cF_ij.因此,F也可看成一个标签函数.初始地,设F₀=Y,其中:如果x_i标记为j,则Y_ij=1;否则Y_ij=0,对于无标签数据点x_u,Y_uj=0(1≤j≤c).同样地,对于多分类情况,只要将公式(17)中的y简单地替换为Y,即可得到如下的多分类预测函数:

F^*=(1-a)(I-aS)^-1Y  (18)

则每个数据对象的标签可由${y_i} = \arg {\max _{j \le c}}F_{ij}^*$确定.

2.3 算法步骤及其复杂度分析

SLPDAL算法的主要步骤描述见算法1.

算法1. SLPDAL.

输入: 标签样本x_iÎX^s,无标签样本x_uÎX^t,参数g,a以及初始化标签向量y.

输出: 目标领域无标签数据的预测标签.

Step 1: 通过公式(8)寻求优化核函数K.

Step 2: 通过求解公式(12)中l₁-范最小化问题,构建稀疏图G={X,S}.构建传播矩阵M=S+S^T-S^TS.

Step 3: 重复F^t+1=aMF^t+(1-a)y直到收敛.

Step 4: 令F^*为序列F^t的极限,输出各数据点x_i的标签${y_i} = \arg {\max _{j \le c}}F_{ij}^*.$

令N=n+m,其中,n和m分别代表源领域和目标领域数据集大小,k表示算法迭代次数.SLPDAL方法整体计算复杂度包括3个部分:优化核矩阵和MMD矩阵计算复杂度O(N²);采用KOMP算法^[32],样本的核稀疏表示计算复杂度O(N²);基于稀疏图的标签传播需要复杂度近似为O(kN)^[34],则该算法的总体计算复杂度为O(2N²+kN).因此,大样本数据集将会明显增大算法的复杂度,所幸的是,由于稀疏表示所具有自然判别能力,使得上述算法在解决实际DAL问题时只需要相对较少的源领域数据,即可取得可比较的效率和精度(如下文实验结果显示).另外,在实际应用中,为了进一步改善本文方法在大规模目标数据集上的处理效率,在SLPDAL算法第1步结束后,可利用传统的支持向量机^[4]对目标领域数据进行初始划分,然后采用我们在文献^[35]中的相似做法(文献^[35]第1.6节),选取目标领域数据集的一个有效子集(设大小为t<<m),再继续进行SLPDAL算法的第2步~第4步的学习.该做法使得SLPDAL算法所需处理的数据大小变为N¢(=n+t)<<N,从而有望提升算法执行效能.

3SLPDAL正则化框架 3.1 稀疏保留正则化

首先,基于上述稀疏重构图G={X,S}提出一个稀疏保留正则项.根据以上描述,稀疏权值矩阵S能够在一定程度上反映数据的本质几何特征且包含了数据的自然判别信息,另外,根据聚类假设,即,如果数据点对x_i和x_j相近,则其对应标签值f_i和f_j也应该彼此接近,我们因此可期望通过稀疏表示来保留类标签空间与核特征空间相似的几何特性.但是,对于新建立的稀疏图G,其边权值${\hat s_{i,j}}$不是一个严格的相似性度量,我们不能按照基于图的框架来构建稀疏保留正则项.注意到,数据点对x_i和x_j间关系刻画为${x_i} = \sum\limits_{j = 1}^{n + m} {{{\hat s}_{i,j}}{x_j}} ,$其并非简单的亲近性,因此,我们期望该数据点对对应的类标签f_i和f_j也尽量保留这种关系,即,分别按照LLE(locally linear embedding)^[24]和LPP^[34]算法思想,刻画为$\min \sum\nolimits_i {\left\| {{f_i} - \sum\limits_{j = 1}^{n + m} {{{\hat s}_{i,j}}{f_j}} } \right\|_2^2} $或$\min \sum\limits_{i,j = 1}^{n + m} {{{\hat s}_{i,j}}({f_i} - {f_j})} {\rm{.}}$因此,可通过最小化如下目标函数来构建稀疏保留正则项,其最好地保留了优化权值向量${\hat s_i}$,从而有效地实现稀疏标签从源领域到目标领域的平滑传播.

${J_1}(F) = \mathop {\min }\limits_F \sum\limits_{i,j = 1}^{m + n} {{{\hat s}_{i,j}}||{f_i} - {f_j}|{|^2}} $

(19)

${J_2}(F) = \mathop {\min }\limits_F \sum\nolimits_i {\left\| {{f_i} - \sum\limits_{j = 1}^{m + n} {{{\hat s}_{i,j}}{f_j}} } \right\|} _2^2$

(20)

其中,F=(f₁,f₂,…,f_c)Ρ^(n+m)xc为类指示矩阵,f_j=[f_j(x₁),f_j(x₂),…,f_j(x_n+m)]^T.J₁(F)和J₂(F)之间的差别在于“加法”算子的顺序.虽然公式(19)和公式(20)中的正则项能够潜在地集成到许多SSL框架,但本文仅关注DAL框架的构建.

定理3. J₁(F)和J₂(F)分别为一阶和二阶图Laplacian正则化.

证明:利用简单的代数计算可得:

J₁(F)=tr(FL₁F^T),J₂(F)=tr(FL₂F^T),

其中,L₁=D-S,L₂=(I-S)^T(I-S),S=[s_ij]_(n+m)x(n+m),D=diag(d₁,d₂,…,d_n+m)为对角矩阵,${d_i} = \sum\nolimits_j {{s_{ij}}} {\rm{.}}$

另外,根据$\sum\nolimits_j {{s_{ij}}} = 1,\forall i{\rm{,}}$则可得:

$\begin{array}{l} {L_2}e = \sum\limits_j {{{[{{(I - S)}^T}(I - S)]}_{ij}}} = \sum\limits_j {{{(I - S - {S^T} + {S^T}S)}_{ij}}} = \\ 1 - \sum\limits_j {{s_{ij}}} - \sum\limits_j {{s_{ji}}} + \sum\limits_j {\sum\limits_k {{s_{ki}}{s_{kj}}} } = 1 - 1 - \sum\limits_j {{s_{ji}}} + \sum\limits_k {{s_{ki}}} = 0, \end{array}$

其中,e为一(n+m)-维全1向量.

按照以上同样推导,可得L₁e=0.根据定义1,J₁(F)和J₂(F)可分别称为一阶和二阶图Laplacian 正则化,且L₁和L₂分别为一阶和二阶图Laplacian.

根据定理3,J₁(F)和J₂(F)能够被进一步统一为

J(F)=tr(FLF^T) (21)

其中,L=L₁或L=L₂.

定理4. SLPDAL通过公式(15)计算的预测结果可通过如下正则化框架导出:

$Q(F) = \mathop {\min }\limits_F tr(FL{F^T}) + \frac{\mu }{2}tr({(F - Y)^T}(F - Y))$

(22)

其中,YΡ^(n+m)xc为原始标签矩阵,如果x_i标记为y_i=j,则Y_i,j=1;否则,Y_i,j=0.

证明:针对变量F对Q(F)求导数可得:

$\frac{{\partial Q(F)}}{{\partial F}} = LF + \mu (F - Y)$

(23)

令L=I-M,对于一阶图Laplacian M=S,对于二阶图Laplacian M=S+S^T-S^TS.令公式(23)等于0,可得最小化Q(F)的近似解,即

(I-M)F+m(F-Y)=0.

进一步整理为

$F - \frac{1}{{1 + \mu }}MF - \frac{\mu }{{1 + \mu }}Y = 0.$

引入两个新变量$\alpha = \frac{1}{{1 + \mu }}$和$\beta = \frac{\mu }{{1 + \mu }}{\rm{,}}$注意到a+b=1,则(I-aM)F=bY,因为(I-aM)可逆,故可得:

F=b(I-aM)^-1Y (24)

很容易看到,公式(24)和公式(15)相等.换句话说,SLPDAL能够从正则化框架公式(22)导出,因此,目标领域数据点x_uÎX(n+1≤u≤n+m)的预测标签可由下式确定:

${f_u} = \arg \mathop {\max }\limits_{1 \le j \le c} {F_{u,j}},n + 1 \le u \le n + m$

(25)

证毕.

公式(22)中,Q(F)的第1项称为平滑项,其描述了相对于稀疏重构结构的数据标签的总体变化;第2项称为拟合项,其度量预测标签和原始标签的拟合性能.

3.2 全局和局部一致正则化

以全局的方式选择一个好的函数,可能不是一个好的策略,因为函数集可能没包含一个适于全局数据集的学习函数^[27].然而从函数集中,可更容易地选出一些适于输入空间局部区域的好的预测函数,因此,可将整个输入空间分割成多个局部区域,然后针对各个局部区域实现更有效的最小化局部成本函数.但是,采用纯粹的局部学习算法也可能存在问题,因为在各局部区域可能不具备用以训练局部学习函数的数据^[28],因此在局部学习正则化的基础上,还应该应用一个全局平滑项,以根据本质数据分布来平滑预测数据标签,使得预测标签更合理、更精确.

从第3.1节的讨论可知:公式(24)中,稀疏保留正则化虽然能比传统的基于图的SSL方法更好地捕捉数据的全局判别信息,但是它却不能捕捉局部数据的判别信息.因此,为了捕捉局部判别信息,本文采用局部核岭回归函数对每个数据模式实施一次回归运算.令矩阵$X = [x_1^s,x_2^s,...,x_n^s,x_1^t,x_2^t,...,x_m^t] \in {{\rm{R}}^{d \times (n + m)}}$代表包含源领域和目标领域的数据集,为简单起见,假定X1_n+m=0,其中,1_n+m表示(n+m)x1向量,定义总体散度矩阵S_t、类间散度矩阵S_b和类内散度矩阵S_w分别为S_t=XX^T,S_b=XGG^TX^T,S_w=XX^T-XGG^TX^T,其中,$G = Y{({Y^T}Y)^{ - \frac{1}{2}}}$为一个加权类指示矩阵,且G^TG=I_c,则有如下定理:

定理5^[36]. 如果rank(S_b)=c-1和rank(S_t)=rank(S_w)+(S_b),则真实的类指示矩阵能被某个数据低维线性投影所表示,即,存在WΡ^dxc,使得Y=X^TW.

定理5中的条件在实际应用中,通常对于高维、小样本问题是满足的(如人脸识别应用)^[36].

令${X_i} = \{ {x_j}\} _{j = 1}^k \in {{\rm{R}}^{d \times k}} \subset X$代表数据x_i的核稀疏重构对象集,其中,k代表数据点x_i的稀疏重构对象数(根据

经验,为了获得最好的有判别的k个重构模式,本文设置s_ij≥e,eÎ(0,1)为某个用户定义的相对较小的阈值).由定理5,可以定义如下局部正则项:

$\mathop {\min }\limits_{F \in {{\rm{R}}^{(n + m) \times c}}} \sum\limits_{l = 1}^c {||{f^l} - {o^l}|{|^2}} $

(26)

其中,c为待分的类数,F=[f¹,f²,…,f^c]为类指示矩阵且${f^l} = {[f_1^l,f_2^l,...,f_{n + m}^l]^T} \in {{\rm{R}}^{(n + m)}},{o^l} = \{ o_i^l({x_i})\} _{i = 1}^{n + m} \in {{\rm{R}}^{n + m}}$代表在数据x_i的低维线性投影上的局部输出,即,$o_i^l({x_i}) = X_i^T{W_i}.$为了获得公式(26)中$o_i^l({x_i})$的分析解,本文采用核岭回

归算法^[27],在某个具有核映射f的RKHS中,公式(26)可重写为

$\mathop {\min }\limits_{{f_i},{W_i}} \sum\limits_{l = 1}^c {\sum\limits_{i = 1}^{n + m} {(||{{(X_i^\phi )}^T}{W_i} - {f_i}|{|^2} + \eta ||{W_i}|{|^2})} } $

(27)

其中,$X_i^\phi = \{ \phi ({x_j})\} _{j = 1}^k \subset {X^\phi },{X^\phi } = [\phi (x_1^s),\phi (x_2^s),...,\phi (x_n^s),\phi (x_1^t),\phi (x_2^t),...,\phi (x_m^t)],\eta > 0$为一个正则参数.

根据Representer Theorem^[15],可得${W_i} = \sum\limits_{j = 1}^k {\nu _{ij}^l\phi ({x_j})} {\rm{.}}$对于任意重构对象x_jÎX_i,其系数向量$v_i^l \in {{\rm{R}}^{k \times 1}}$中元素为$v_{ij}^l$.从而,$o_i^l({x_i}) = {K_i}v_i^l$,K_iΡ^kxk为核矩阵,包含元素K(x_u,x_v),x_u,x_vÎX_i.替换公式(27)中的W_i可得:

$\mathop {\min }\limits_{v_i^l \in {\Re ^k}} \sum\limits_{l = 1}^c {\sum\limits_{i = 1}^{n + m} {(||{K_i}v_i^l - f_i^l|{|^2} + \eta {{(v_i^l)}^T}{K_i}v_i^l)} } $

(28)

求解公式(28)后,可得$v_i^l = {({K_i} + \eta I)^{ - 1}}f_i^l,$则$o_i^l({x_i})$的分析解可表示为

$o_i^l({x_i}) = k_i^T{({K_i} + \eta I)^{ - 1}}f_i^l = \Omega _i^Tf_i^l$

(29)

其中,k_iΡ^k表示包含元素K(x_i,x_j)的向量,其中,x_jÎX_i,${\Omega _i} = k_i^T{({K_i} + \eta I)^{ - 1}}$.公式(26)可被重写为如下紧凑形式:

$\mathop {\min }\limits_{F \in {\Re ^{(n + m) \times c}}} \sum\limits_{l = 1}^c {||{f^l} - A{f^l}|{|^2}} = \sum\limits_{l = 1}^c {{{({f^l})}^T}{L_o}{f^l}} = tr({F^T}{L_o}F)$

(30)

其中,L_o=(I-A)^T(I-A),且I为一(n+m)-维单位矩阵,矩阵A=[a_ij]Ρ^(n+m)x(n+m)的构造方法是:对于"x_i和x_j(1≤i,j≤n+m),如果x_jÎX_i,则a_ij=W_ij;否则,a_ij=0.在公式(21)中,用(1-l)L+lL_o替换L,其中,lÎ^[0,1]为一平衡参数,从而得到一个基于全局和局部一致视角的混合图Laplacian正则化^[26]形式:

J_mix(F)=tr{F[(1-l)L+lL_o]F^T} (31)

最后,可导出基于混合图Laplacian正则化的SLPDAL框架形式:

${Q_{mix}}(F) = \mathop {\min }\limits_F {J_{mix}}(F) + \frac{\mu }{2}tr({(F - Y)^T}(F - Y))$

(32)

根据公式(31),当l=1时,J_mix(F)降级为基于局部正则化的DAL形式.

4 算法性质和扩展 4.1 对样本外(out-of-sample)数据的推理

第3节论述了SLPDAL算法的主要演绎学习过程,本节介绍如何将SLPDAL算法推广到样本外数据学习.按照文献^[14]的做法,为了将SLPDAL泛化到样本外数据学习需要做两件事情:(1) 对于新的样本外测试数据点x_u,使用和公式(23)相同的平滑准则类型;(2) 确保样本外数据x_u的加入不会影响训练数据集的原始Q(F)值.

对于新的测试数据点x_u,平滑准则定义为

$Q(f({x_u})) = \sum\limits_{j:{x_j} \in X} {{s_{uj}}{{(f({x_u}) - {f_j})}^2}} {\rm{/}}Q(f({x_u})) = {\left( {f({x_u}) - \sum\limits_{j:{x_j} \in X} {{s_{uj}}{f_j}} } \right)^2}$

(33)

因为Q(f(x_u))关于f(x_u)为凸函数,故在公式(34)条件下,其能被最小化:

$f({x_u}) = \sum\limits_{j:{x_j} \in X} {{s_{uj}}{f_j}}$

(34)

有趣的是,公式(34)正好是当数据点x_u的标签能够被训练数据集内重构数据对象的标签优化重构时的公式,即为公式(35)的优化解:

$f({x_u}) = \mathop {\min }\limits_{f({x_u})} ||f({x_u}) - \sum\nolimits_j {{s_{uj}}{f_j}} ||_2^2$

(35)

4.2SLPDAL的鲁棒性

当数据集中有无效测试数据时,SLPDAL算法存在潜在问题,因此在实施标签传播前,须先确定无标签样本是否有效.在实际应用场景中,检测并排斥无效测试样本(或离群点),是模式分类方法的关键能力.

对于每个类i(1≤i≤c),令Y_i:¡^n+m®¡^n+m为选取与第i类相关的稀疏重构系数的特征函数.对于一个稀疏重构系数向量sΡ^n+m,Y_i(s)Ρ^n+m为一个新的向量,其非零元素为s中与第i个类相关的元素.

定义3(稀疏集中索引(sparsity concentration index,简称SCI)^[16]). 稀疏重构系数向量sΡ^n+m的SCI定义为

根据定义3,对于由公式(12)取得的优化解${\hat s_i}:$如果$SCI({\hat s_i}) = 1,$则表示测试样本x_i仅由同一类的对象表示;如果$SCI({\hat s_i}) = 0,$则表示稀疏重构系数均分于所有类.

从而,可以选择一个适当的阈值tÎ(0,1),使得当$SCI({\hat s_i}) \ge \tau $时,则认为测试样本x_i为有效.因此,在稀疏图构造之前,我们可实施一个预处理过程,即,通过SCI测试方法来排除数据集中某些噪声或离群点,从而增强SLPDAL算法的鲁棒性能.

4.3 多核学习扩展

本文所提出的核方法在一定程度上严重依赖核函数的选择,然而,对于某个特定领域的适应学习任务,最合适的核函数事先往往是无法预知的.而且,在某个用户事先定义的核函数池中进行优化函数的穷尽搜索也将是非常耗时的,因此,为了增强该方法的鲁棒性,关键在于如何有效学习一个适当的核函数.目前,已有一些多核学习(multiple kernel learning,简称MKL)方法^[37,38]被提出来,然而,这些方法均假设训练数据和测试数据来自相同领域,导致其不能基于来自不同领域的样本数据学习一个优化的核函数,从而使得这些MKL方法在源领域的学习性能不能有效地迁移到目标领域.但是,在某些约束条件(如领域间分布距离最小化)下^[4],上述MKL方法能够明显改善DAL性能.由于核函数在本文方法中的中心地位,选取一个好的核函数是必须的,因此,本节将重点讨论在SLPDAL算法的领域分布核均值匹配阶段,如何利用多核学习技术来学习一个有效的集成核函数,从而将上述SLPDAL方法推广到多核学习框架.图 1显示了SLPDAL的多核学习模型.

根据MKL技术,即,将M个核k₁,k₂,…,k_M及其核诱导特征映射f₁,f₂,…,f_M构成一个凸组合^[37,38],基于领域数

据的多核K_M是M个核$\{ {k_h}\} _{h = 1}^M$的凸组合,其中,k_h与公式(8)中定义的K相同.

采用文献^[37,38]中的MKL形式,可得:

${K_M} = \sum\limits_{h = 1}^M {{\mu _h}{k_h}} ,{\rm{ }}{\mu _h} \ge 0,{\rm{ }}\sum\limits_{h = 1}^M {{\mu _h}} = 1.$

从而,公式(8)中的单核函数被推广为多核函数K_M.

公式(8)可直接利用现有的MKL软件包(如SimpleMKL^[37])求解,更多细节可参见文献^[37].为有所区别,下文将基于MKL的SLPDAL算法称为多核稀疏标签传播(multiple kernel sparse label propagation,简称MKSLP).

4.4 领域间分布一致控制

定理6^[39]. 给定一个高斯核函数类其中,s₀>0.对于任意k_s,k_tÎK_g且0<t<s<¥,则有${\gamma _{{k_\sigma }}}(P,Q) \ge {\gamma _{{k_\tau }}}(P,Q){\rm{.}}$

定理6说明:核带宽越大,RKHS嵌入领域的分布距离将越大,从而导致SLPDAL(或MKSLP)算法收敛速度降低.为了实验研究核带宽对SLPDAL(或MKSLP)的性能影响,本文特将高斯核带宽参数化,即,高斯核函数泛化为

${k_{\sigma /\gamma }}(x,{x_i}) = \exp \left( { - \frac{{||x - {x_i}|{|^2}}}{{2{{(\sigma /\gamma )}^2}}}} \right),$

其中,g为一个可调参数.根据下文实验结果:随着g值的增加,领域内样本分布呈现强的内聚性,从而导致领域内不同类样本出现交叠,这将会严重影响学习性能;另一方面,随着g值的减小,将会导致SLPDAL(或MKSLP)算法收敛率下降.因此,本文约束参数gÎ[1,g₀],其中,g₀为一用户指定的阈值.实验结果显示:通过协调参数g,能够进一步增强所提出算法的领域适应性能.

5 实验结论

为了评价SLPDAL方法在DAL问题上的有效性,本文在一系列人造数据集和几个实际领域适应数据集上将该方法与几个代表性的算法进行比较,其中,实际领域适应应用包括:跨领域人脸识别、跨领域图像标注、可视化视频概念检测、跨领域文本分类.

对于所有数据集,源领域数据和部分目标领域数据真实标签已知,来自源领域和目标领域的标签数据用于训练数据集,目标领域无标签数据用于测试数据集.

与所提出的方法进行比较的学习算法包括基线方法LLGC^[26]、基于稀疏重构技巧的S-RLSC^[18]以及基于线性邻居传播模型的LNP^[14].这些方法都是经典的SSL算法,它们在许多不同的SSL任务中表现出良好的鲁棒性,但是,它们不能直接有效应用于DAL任务.为此,本文还重点比较了几种代表性的DAL方法,如LMPROJ^[6],CD-SVM^[9],KMM^[40]和DTSVM^[4].

在所有实验中,对于几个相关的核学习方法CD-SVM,KMM和LMPROJ,本文采用标准的高斯核函数:

k_q(x,z)=exp(-q||x-z||²),

其中,q设置为1/d(d为数据维数).对于多核学习方法DTSVM,按照文献^[4]的设置,令核参数为1.2^dq,其中,d分别设置为{0,0.5,1,1.5,2,2.5,3,3.5},从而为DTSVM构造8个基核.对于SLPDAL方法,采用参数化高斯核函数:

${k_{\sigma /\gamma }}(x,{x_i}) = \exp \left( { - \frac{{||x - {x_i}|{|^2}}}{{2{{(\sigma /\gamma )}^2}}}} \right),$

其中,核参数s按照文献^[29]的做法,通过最小化MMD准则获得.根据经验,对于二元分类问题,本文首先选取核参数s为训练数据平均范数的平方根;对于多类划分,则选取核参数为$\sigma \sqrt c $(c为分类数).

对于多核方法MKSLP,为了公平起见,本文也按照文献^[4]的设置,选取核参数为1.2^ds,其中,d的设置与DTSVM相同.在该方法利用SCI测试的预处理阶段,本文按照经验选取阈值t,以过滤2%的潜在噪声点.

目前,在核学习方法中如何有效地选择模型参数,仍然属于一个具有挑战性的公开问题.本文采用五重交叉验证法来选择各算法参数,实验结果的平均值用于算法性能评价,所有算法代码实现均在Matlab2010a上完成.

5.1 人造数据集实验 5.1.1 标签传播效果

本节将采用一个二维人造数据集来显示所提出方法的学习性能,以更好地理解该方法在特定的领域适应问题上的标签传播过程.首先,人工生成一个包含300个样本的刻画两个信息类别的“双月形”二维数据集作为源领域(source domain,简称SD)数据,其中,每个类包含150个样本对象;然后,将该数据集逆时针旋转30°作为目标领域(target domain,简称TD)数据,并在其中标识2个标签数据点(分别以实心*和表示),如图 2(a)所示(即,当迭代次数t=0时仅有2个标签样本).上述旋转操作,使得两个领域数据呈现不同分布.从图 2(b)(即,当迭代次数t=15时,目标领域所有样本被标识)可以清楚地看出本文所提出的方法在DAL上的标签传播有效性.

为了进一步显示所提出的方法对样本外数据的学习效能,继续采用图 2(a)中的数据集,利用SLPDAL预测目标领域无标签样本,通过公式(35)来推理目标领域在区域{(x,y)|xÎ[-10,7],yÎ[-10,5]}内样本的标签,图 2(c)显示了所有样本标签的推理结果,图中z轴显示数据的预测标签值.从图 2(c)结果可直观地看出,推理结果的边界和样本内数据的预测边界的本质结构几乎相同.

5.1.2 对噪声数据的鲁棒性

在某些情况下,由于数据标注的疏忽,使得标签样本中可能包含某些噪声,其将直接导致标签传播算法有效性的明显下降.而检测这些噪声标签需要大量人力和时间,因此在实际应用中,有必要设计一个鲁棒的分类器.图 3展现了本文所提方法对噪声标签的鲁棒性能,在图 3(a)中,一个包含两类的“双月形”数据集直观上应被划分为2个聚类,其中包含2个划分异常的数据点,或可称为噪声标签(即,目标领域每个类包含1个噪声点).图 3(b)~图 3(d)分别显示1-近邻LNP算法、无SCI预处理的SLPDAL和具有SCI预处理的SLPDAL算法,经比较可以看出,只有经过SCI预处理的SLPDAL算法正确地划分了所有数据点.

5.1.3 对桥接数据的鲁棒性

在SLPDAL算法中存在的另一个潜在问题是,数据集中存在的桥接数据(即,在某些复杂的类相互交连的数据集中那些连接不同类数据的样本点)也将导致标签传播性能下降.如图 4(a)所示的“双月形”数据集,该数据集的上半月和下半月距离较近,导致上半月右端点和下半月的左端点出现一定程度的交织,从而产生了某些桥节点.图 4(b)~图 4(d)分别显示5-近邻LNP算法、S-SRLC算法以及基于SCI预处理的SLPDAL算法分类结果.从这些结果可以看出:针对具有桥接点的数据集,SLPDAL方法经过SCI预处理后,取得了优于LNP和S-SLRC方法的学习性能.由于LNP算法无法有效判别类间交叠数据点,使得其明显对桥节点较敏感^[36].另外,值得注意的是,与LNP算法相比,S-SRLC算法取得了较好的鲁棒性.可能的解释是,SR具有自然的判别能力,因而即使在桥架点存在的情况下,基于SR的S-SRLC算法依然运行良好.

5.2 领域适应人脸识别 5.2.1 数据集描述

为了评价所提出的方法在跨领域人脸识别应用上的有效性,本文采用两个具有代表性的人脸数据库,即,ORL和YALE(两个数据集均可从网站http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html下载).

ORL数据库包含40个不同对象的400幅人脸图像,根据时间、灯照条件、面部表情、面部细节等不同特征,分别有10幅图像刻画每个对象,实验中,将每幅原始图像的大小缩减为40x40像素;YALE数据库包含15个不同对象的165幅人脸图像,根据不同的面部表情和面部配置,分别有11幅图像刻画每个对象,并将原始图像缩减为32x32像素大小.

5.2.2 实验设置

为了评价所提出的方法在人脸识别应用上的鲁棒性,本文从YALE和ORL数据库中分别对每个对象随机选取8幅图像作为源领域数据集(如图 5(a)所示).目标领域数据集通过将源领域数据逆时针旋转30°来获得,该旋转操作使得源领域和目标领域数据具有不同的分布.实验中,为了测试所提出方法的鲁棒性,在样本数据中加入了随机噪声和遮罩信息.第1次,在目标领域图像样本中逐渐增加高斯白噪声百分比,以逐渐减小信噪比(signal-to- noise ratio,简称SNR),如图 5(b)所示.第2次,不同大小的黑色方块随机覆盖在目标领域样本图像上,从而产生遮罩(或缺失数据)现象,如图 5(c)所示.对于大小为32x32像素的YALE图像,黑色方块大小分别为6x6,10x10,18x 18和22x22像素;对于大小为40x40像素的ORL图像,黑色方块大小分别为8x8,14x14,22x22和26x26像素.

5.2.3 实验结果

上述数据集的实验结果记录于表 1和表 2,表中分别详细记录了每种算法在各数据集上10次最好分类精度率(ACC%)的平均值和标准差,其中,黑体数据表示经t-测试证实相应算法明显优于其他算法.由表 1和表 2可看出:在样本数据完好(无缺损数据和噪声信息)或接近完好的情况下,SLPDAL(或MKSLP)和DTSVM算法均取得了优于其他算法的分类性能,这说明SR和MKL技术可用于改善DAL泛化性能.同时,几种SSL算法取得了最差的分类性能,这也证实了SSL算法不适于DAL任务.但值得指出的是,本文方法SLPDAL和MKSLP在绝大多数情况下均取得了最好或可比较的识别性能,这说明基于稀疏重构和MMD思想的SLPDAL和MKSLP算法是有效的.另外,随着噪声或遮罩信息的增加,所有算法的识别性能均表现出了不同程度的下降趋势,而本文所提出的方法SLPDAL(或MKSLP)和S-SRLC性能下降相对缓慢.同时看到,基于多核技术的MKSLP方法几乎总是稍好于SLPDAL方法,这也进一步说明了基于稀疏重构技术或(和)MKL技术的图像识别方法对于噪声或缺失数据具有更强的鲁棒性.

5.3 跨领域Web图像标注 5.3.1 数据集及其设置

本部分将在一个实际Web图像标注数据库NUS-WIDE^[41]上进行实验,以验证所提出的方法在图像标注问题上的领域适应学习性能.NUS-WIDE数据库包含来自81个不同概念的269 648幅带标签的Web图像,样本特征为500维.为了模拟DAL环境,实验选取12个动物概念,包括熊猫、猴子、猫、斑马、老虎、鸟、狗、蛙、马、蝴蝶、蛇、长颈鹿,如图 6所示,从中随机选取6个带标签的概念作为源领域数据集,采用所提出的算法将稀疏标签传播到其他6个概念.

5.3.2 实验结果

实验中对12个概念进行了6次随机划分,每次划分的图像概念标注性能如图 7所示.

从图 7可以看出:本实验取得了与人脸识别相似的结论,唯一例外的是CD-SVM方法在本数据集上取得了相对较好的性能,但由于其未能明确考虑有效控制领域间分布的一致性,使得CD-SVM方法依然达不到满意的效果.值得指出的是:本文基于MKL的方法MKSLP在所有划分上的图像概念标注性能均优于其他方法,甚至比人脸识别中优势更明显.对此可能的解释是:由于不同概念图像的差异性较大,导致领域间分布距离较大,在此条件下,MKSL与其他方法相比,能够迁移更多的判别信息至目标领域.而且,本实验结果也再次显示出:MKSLP算法通过领域间分布一致正则化来学习一个多核空间,对于跨领域图像标注任务是有效的.

5.4 视频概念检测

本节将进一步验证MKSLP方法在大规模视频数据集TRECVID上的有效性和效率.

5.4.1 数据集描述

TRECVID视频数据库(http://www-nlpir.nist.gov/projects/trecvid)是目前供研究所用的最大的带标注视频数据集之一,其中,TRECVID 2005数据集包含61 901个关键帧,分别抽取自6个广播频道108小时的视频节目; TRECVID 2007数据集包含21 532个关键帧,分别抽取自60小时的新闻杂志、科学新闻、纪录片以及教育节目等视频数据^[4,9].如文献^[4]所展示,由于TRECVID 2007数据集和TRECVID 2005数据集在节目结构和制作规格等方面存在较大的差异,使得在TRECVID数据集上进行领域适应学习是一项艰难挑战.实验从LSCOM-lite词库^[4]中挑选36个语言概念,以覆盖在广播新闻视频出现的36个主要的可视概念,这36个概念已被予以手工标注,以描述在TRECVID 2005和TRECVID 2007数据集中关键帧的可视内容.抽取3个低级全局特征(即,网格颜色矩(225-维)、Gabor纹理(48-维)和边缘方向直方图(73-维))以表示关键帧的不同内容,然后,将这3类特征连接起来,使得每个关键帧均成为一个346-维的特征向量.

5.4.2 实验设置

本实验将系统地比较所提出的方法MKSLP和基线方法S-SRLC以及几种跨领域学习方法(包括CD-SVM,DTSVM以及KMM)在视频概念识别应用上的性能.MKSLP和S-SRLC使用源领域D^s或源领域加上目标领域D^sÈD^t带标签数据作为训练样本集,这里,$D_l^t$代表目标领域带标签数据,为了有所区别,将在这两种情况下训练的MKSLP和S-SRLC方法分别称为MKSLP_A,MKSLP_AT,S-SRLC_A和S-SRLC_AT.几种跨领域学习方法CD-SVM,DASVM,KMM和DTSVM也同时采用两个领域标签数据集${D^s} \cup D_l^t$作为训练数据集.对于CD-SVM,KMM,DTSVM和MKSLP方法,从目标领域随机选出4 000个无标签样本作为无标签目标领域数据集${D^s} \cup D_l^t$按照文献^[4]的设置,根据在TRECVID 2007数据集中正标注样本的频率,实验中将36个概念分成3个组:第1组由12个具有高频率(正标注样本频率超过0.05)的概念组成;第2组由11个具有中等频率(0.01≤正标注样本频 率≤0.05);第3组由剩下的13个低频率概念组成(正标注样本频率小于0.01).实验采用非差值平均精度(non- interpolated average precision,简称AP)^[4]作为性能评价标准,并记录每种算法最好的实验结果.

5.4.3 实验结论

表 3记录了所有参与比较的算法分别在3个概念组和总体概念上的平均AP率.

由表 4可以得出如下几个有意义的结论:

(1) 在所有概念组上,S_SRLC_A方法均逊色于其他方法.这表明仅利用源领域训练数据的S_SRLC分类器不能在目标领域取得较好性能,这也说明了在不同年代收集的TRECVID数据集的数据分布间差异较大.

(2) S-SRLC_A和S-SRLC_AT方法在Group-1中的AP值一定程度上高于在Group-3中的AP值.这说明在Group-1中,概念具有大量来自两个领域的正样本数据.直观上来说,当两个领域中存在足够的正样本时,样本将在特征空间中分布紧密.在此情况下,领域样本分布可能出现交叠^[4],从而使得来自源领域的训练数据有助于目标领域视频概念检测;相反地,在Group-3中,来自两个领域的中样本在特征空间的分布较稀疏,导致两个领域数据分布间交叠较少,因此对于Group-3中的概念识别,来自源领域的训练数据将在一定程度上降低目标领域视频概念检测性能.

(3) 在所有概念组上,方法S-SRLC_AT,CD-SVM和KMM均优于方法S-SRLC_A.这表明在S-SRLC_AT,CD-SVM和KMM等方法中,利用目标领域信息能够有效改善目标领域学习性能.从Group-ALL中的结果可知,KMM和CD-SVM方法比S-SRLC_AT方法稍差.可能的解释是:CD-SVM方法采用来自目标领域k-NN来定义源领域数据权重,而当目标领域正标注训练样本数非常有限时(如本实验中,每个概念10个正标注样本),上述学习得到权值是不可靠的;相似地,KMM方法采用无监督的方式学习源领域数据集权重,可能使得其识别性能在一定程度上弱于其他跨领域识别方法.

(4) 在所有概念组上,DTSVM和MKSLP方法明显好于S-SRLC_AT和两种DAL方法CD-SVM和KMM.这说明,DTSVM和MKSLP方法通过有效组合多基核函数,能够成功地减小两个领域间的分布差距.而且,本文带有稀疏保留特性的MKSLP_A和MKSLP_AT方法在Group-ALL概念组上的识别性能优于DTSVM方法,由此可知,MKSLP方法在所有概念组上的识别性能优于所有其他方法.

(5) 值得注意的是,在所有概念组上,MKSLP_AT方法均稍好于MKSLP_A方法,这进一步证实了目标领域先验信息能够有效增强MKSLP方法的领域适应能力.

在定理2中,我们已系统地证明了SLPDAL方法的收敛性.下面,我们将采用分别来自上述3个不同概念组中的3个概念,即Person,Office和Charts的数据作为实验样本,以实验证实MKSLP算法的收敛性能.如图 8所示,MKSLP的目标值(迭代变化值)在少于10次内即可收敛,相似结果在TRECVID数据集中的其他概念上也能观测得出.

5.5 跨领域文本分类

本节将采用两个实际文本数据集20 Newsgroups和垃圾邮件过滤^[3,6]来深入展现所提方法在跨领域文本分类任务上的普遍有效性.

5.5.1 数据集描述

上述两个文本数据集的简单描述汇总于表 4,表中数据集序号标识了各个实验任务,如序号3表示20 Newsgroup文本集中“Rec.”(源领域)和“Sci.”(目标领域)数据作为实验样本集,其中,源领域(Rec.)中分别包含1 984个正的训练样本和1 977个负训练样本;而目标领域(Sci.)分别包含1 993个正的训练样本和1 972个负训练样本.

5.5.2 实验设置

20 Newsgroups和垃圾邮件过滤是两个公开的跨领域文本分类任务,现有的许多DAL方法^[3,6]通常采用它们来评价算法性能.20 Newsgroups数据集包含20个新闻组类别,每个组大约包含1 000份文档.对于该文本分类任务,其主要目标是利用各顶层类别下的子类文档分别作为训练文档和测试文档来正确区分顶层类别下的新闻文档(如区分”Sci.”文档和”talk”文档),其中,各子类文档集代表一个不同的领域.

在垃圾邮件过滤数据集中^[3]有3个邮件子集,分别表示为User 1,User 2和User 3,分别代表 3个不同用户.在该DAL问题中,主要任务是识别出正常邮件和垃圾邮件.由于在各子集中正常和垃圾邮件由不同用户标识,使得各子集的数据分布相关但不同.各子集包含2 500邮件,其中一半为正常邮件(标签为1),另一半为垃圾邮件(标签为-1).按照文献^[6]的设置,本实验考虑3种情况:1) User 1(源领域) & User 2(目标领域);2) User 2(源领域) & User 3(目标领域);3) User 3(源领域) & User 1(目标领域).

在各实验中,训练数据集包含所有来自源领域的标签样本和随机采自目标领域的2l个标签样本(每类l个标签样本),目标领域中剩余样本用于测试数据,其中,对于20 Newsgroups数据集,设置l=3;对于垃圾邮件数据集,设置l=5.

5.5.3 实验结论

对于各数据集,每种算法均运行5次并记录最好的结果,并将最终的平均值和标准差记录于表 5.

从表6中的结果能够得出如下几个有意义的结论:

1) 跨领域学习算法LMPROJ和KMM经常取得与几种SSL算法LLGC,S-SRLC和LNP相似的学习性能,可能的解释为:由于两个领域的数据分布非常相关或相近时,现有的DAL方法难以进一步提升在目标领域的学习性能.KMM方法在两个数据集上的分类性能普遍差于LMPROJ方法,其原因可能是:基于转导学习(transductive learning)框架的LMPROJ方法比KMM方法更适于这些文本数据集分类.另外,在绝大多数情况下,采用MKL策略的DTSVM方法均优于其他方法(SLPDAL方法除外),从而可以推断,MKL技术在某些特定环境下确实能够有效地改进DAL性能.

2) 本文所提出的方法SLPDAL在两个数据集上的分类性能一般均优于其他方法,这是因为SLPDAL方法明确而综合性地考虑了3个方面的特征:(1) 领域数据分布的差异匹配;(2) 数据分布的整体与局部本质几何特征的一致性;(3) 同时利用源领域和目标领域先验信息.

为了进一步评价目标领域标签数据个数变化对所提出的方法鲁棒性的影响,令l值在区域lÎ{0,1,3,5,7,10}内变化,并在20 Newsgroups数据集中的任务5和任务1上进行重新实验,实验结果如图 9(a)、图 9(b)所示.从图 9中可看出:目标领域标签样本数的增加,能够明显增强所有方法(尤其是DAL方法)的学习能力.这说明充分利用目标领域先验信息,可明显改善DAL方法的学习性能.

5.6 参数敏感性分析

本实验从表 5中选取几个DAL任务(包括任务3、任务6和任务7),以明确阐述模型参数对所提出方法的分类性能影响.根据定理6,实验设置g₀=10,图 10(a)~图 10(d)分别显示,模型参数m,l,g和h对所提方法的分类性能影响,图中的参数变化曲线是在固定其他3个最优参数的情况下绘制的.

图 10(a)~图 10(c)显示了所提出的方法在任务6和任务7上的参数敏感性,图 10(d)显示了所提出的方法在任务3上的参数敏感性.从这些图示曲线的变化可以得出如下结论:

(1) 图 10(a)显示了控制参数a的正则参数m对所提方法的敏感性.根据定理4的证明可知,参数m起到平衡预测损失和平滑性的作用.图中结果显示,该参数虽然从某种意义上来说对所提出的方法的分类精度起到一定的影响,但通过对y轴的观测发现,该影响效果非常有限.

(2) 图 10(b)显示,当l=0时,即,忽略领域间局部一致性时,所提出的方法不能取得最优学习性能.在一定的参数值区域内,随着l的增加,所提出方法的性能逐渐缓慢提升,直到收敛于某个最大性能值;当l=1,即,忽略领域间全局一致性(由稀疏保留正则项控制)时,所提出的方法在一定程度上呈现下降趋势.从以上分析可知,基于转导框架模型的DAL方法仅考虑领域数据分布的全局或局部特征是不完全的,应综合考虑领域数据的全局和局部本质分布特征的一致性,才可能获得最优的领域适应分类性能.

(3) 图 10(c)显示,一方面,参数g的值越小(如gÎ[1,3)),即高斯核带宽越大,使得领域内数据分布散度就越大,从而导致领域间分布差最小化的收敛速率减小;另一方面,参数g的值越大(如gÎ[6,+¥)),即高斯核带宽越小,导致领域内类间数据分布出现交叠.上述两种情况均可能导致所提出的方法分类性能的明显下降,而只有在一个适度的参数值域范围内(e.g. gÎ[3,6)),所提出的方法才可能获得最优的性能.

(4) 从图 10(d)可观察到:当参数值h<4时,SLPDAL不能取得优化性能;但是,随着参数h值的增加,SLPDAL分类精度能够得到稳步提升.

6 结束语

本文提出一种领域适应学习方法,即,稀疏标签传播领域适应学习(SLPDAL).基于领域间数据分布的最小化MMD准则,寻求一个RKHS H,在H中,采用核稀疏表示技术来重构领域数据并构造一个稀疏图,并据此完成SLPDAL方法的标签传播过程,从而实现最终的跨领域学习任务.理论分析结果显示:基于领域数据分布的全局和局部一致正则化,SLPDAL所预测的数据标签具有充分平滑性.在人造和实际DAL任务上的实验结果验证了所提出方法的鲁棒性和有效性.对于基于领域间数据分布最小化MMD准则的DAL方法,源领域数据集选择的有效性是决定其成败的一个非常重要的因素.现有研究成果表明:多源领域的集成有利于避免单一源领域可能导致的所谓“负迁移”现象^[42],但是多个源领域的集成势必造成学习算法的计算复杂度增加.因此,基于多源领域有效集成的SLPDAL模型的构建,是本文值得进一步研究的一个方向.

致谢 在此,我们向对本文的工作给予支持和建议的同行,尤其是本文的各位审稿专家表示衷心的感谢.