2. 沈阳航空航天大学 人机智能研究中心, 辽宁 沈阳 110136
2. Human Computer Intelligence Research Center, Shenyang Aerospace University, Shenyang 110136, China
基于核函数的机器学习方法,简称核方法,是机器学习领域的一类重要方法,被广泛地应用于分类、聚类、回归和特征选择等方面[1].最具有代表性的方法有:支持向量机、谱聚类、岭回归、核主成分分析等.文献[2]在121个数据集上比较研究了179种分类器的性能,发现基于核函数的支持向量机与极限学习机是5种最优的分类器之一,其效果明显好于其他分类器.然而,核函数的选择与参数优化一直是影响核方法效果的核心问题[3],从而推动了核度量标准,特别是普适性核度量标准(universal kernel evaluation measure)[4]的研究.
普适性核度量标准不直接估计泛化误差界,仅依据给定的问题和样本对核函数质量做出量化评价,与留一法[5]和Span-Bound法[6]等泛化误差界的直接估计法相比具有较高的计算效率,计算代价仅为O(n2)(n为样本容量),与结构风险(structural risk)[7, 8]、负对数后验(negative log-posterior)[9]和超核(hyperkernels)[10]等方法相比具有算法无关性,不依赖于具体核学习算法与核函数,具有较好的推广能力.其中,KTA(kernel target alignment)[11]是最早被提出的普适性核度量标准,因此也是应用较为广泛的标准之一.文献[4]综述了KTA的基本思想、理论特性、在多核学习、特征选择与核函数参数优化等方面的应用情况以及与其他普适性度量标准间的关系.
在KTA之后提出的其他普适性度量标准力争沿袭KTA的优点,并对KTA存在的问题进行了改进,其中, EKTA(extension of kernel target alignment)[12]与CKTA(centered kernel target alignment)[13]同样基于KTA的Alignment的基本思想.EKTA采用了每类样本数量对目标矩阵进行了调整,目的是解决KTA的类别分布敏感性问题.CKTA首先将核函数进行了中心化,然后计算与目标矩阵的相似程度.中心化可以消除由于样本远离原点而产生的病态核矩阵的问题[14].
FSM(feature space based kernel matrix evaluation measures)[15]首次指出KTA存在线性变换敏感性问题,并针对该问题进行了改进.FSM与KTA的Alignment基本思想不同,直接度量样本在特征空间中的可分离性,为特征空间中正负类中心的距离与特征空间中同类样本在正负类中心所确定的方向上总偏差的比值.FSM的基本思想与KCSM(kernel class separablity measures)最接近,KCSM是Fisher线性判别准则[16, 17]在核函数度量上的应用,为样本在特征空间中类间散布程度和类内散布程度的比值.KCSM被应用于特征选择[18, 19]、核函数参数优化[20]等方面.
由此可见,KTA,EKTA,CKTA,FSM与KCSM彼此之间存在一定的相关性,除KCSM外,其他标准都是针对KTA所存在的问题进行的改进,并且EKTA,CKTA与KTA属同族标准,KCSM与FSM属同族标准.因此,对上述5种算法进行比较分析,可进一步揭示其内在相关性以及发现类别分布敏感性与线性变换敏感性等问题的产生原因,为解决上述问题提出新的度量标准提供依据.
对KTA,EKTA,CKTA,FSM与KCSM进行比较研究:首先,发现了上述5种普适性度量标准具有较为相近的形式,可在统一的框架下进行研究与比较,并且发现其度量内容为特征空间中线性假设的平均间隔,与支持向量机最大化最小间隔的优化目标存在偏差;然后,使用模拟数据研究了类别分布敏感性、线性平移敏感性、异方差数据敏感性,指出5种度量标准产生上述问题的原因,并指出该5种普适性度量标准都是核度量的充分非必要条件,好的核函数可能获得较低的度量值;最后,通过在9个UCI数据集和20Newsgroups数据集上的核函数选择实验比较了5种度量标准的度量效果,由于CKTA解决了KTA的线性变换敏感性问题并且受异方差数据影响较弱,是该5种度量标准中度量效果最好的普适性核度量标准.
1 对5种度量标准的分析考虑二分类问题,X⊂$\mathbb{R}$n为样本空间,Y={-1,+1}为标记集.D代表在X×Y上确定但未知的概率分布,样本集{(x1,y1),…,(xl,yl)}依据分布D独立同分布抽取.并且有l+个样本属于“+1”类,有l-个样本属于“-1”类,l=l++l-.每个样本xi通过核函数映射到特征空间H中的φ(xi):
$ k\left( {{x}_{i}},{{x}_{j}} \right)=\left\langle \phi \left( {{x}_{i}} \right),\phi \left( {{x}_{j}} \right) \right\rangle ,\phi :X\to H. $
核函数k的核矩阵为
${{\left[ K \right]}_{i}}_{,j}=k\left( {{x}_{i}},{{x}_{j}} \right). $
1.1 KTAKTA由Cristianini等人[11]提出,是最早被提出的核度量标准.对于二分类问题,KTA计算核矩阵与理想目标矩阵的对齐程度.定义理想目标矩阵为
$ {{[Y]}_{i,j}}={{y}_{i}}\cdot {{y}_{j}}=\left\{ \begin{array}{*{35}{l}} +1,\text{ }{{y}_{i}}={{y}_{j}} \\ -1,\text{ }{{y}_{i}}\ne {{y}_{j}} \\ \end{array} \right.. $
定义KTA为
$KTA(K,Y)=\frac{{{\langle K,Y\rangle }_{F}}}{\sqrt{{{\langle K,K\rangle }_{F}}}\sqrt{{{\langle Y,Y\rangle }_{F}}}}, $
其中,${{\left\langle .,. \right\rangle }_{F}} $ 为Frobenius内积.因此,KTA为归一化后的核矩阵与理想目标矩阵间的Frobenius内积.KTA取值区间为[-1,+1],值越高,表明核矩阵与理想目标矩阵对齐程度越高,核函数越好.
由Y的定义可知 ${{\left\langle Y,Y \right\rangle }_{F}}={{l}^{2}} $ ,KTA可转化为如下形式:
$ KTA(K,Y)=\frac{1}{\sqrt{\frac{1}{{{l}^{2}}}{{\langle K,K\rangle }_{F}}}}{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y), $
其中, ${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y)=\frac{1}{{{l}^{2}}}{{\langle K,Y\rangle }_{F}}\text{.}$ 本文将在第2.1节讨论 ${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y) $ 与特征空间中线性假设平均间隔间的关系.
1.2 CKTACorinna等人[13]提出了CKTA,并将其用于多核学习.文献[21]将其用于基于连续基核的多核学习任务.文献[22]>将其应用于多核聚类任务.CKTA使用了中心化核函数代替了KTA中的核函数,中心化核函数定义如下:
$\begin{align} & {{k}_{C}}({{x}_{1}},{{x}_{2}})=\langle \phi ({{x}_{1}})-\bar{\phi },\phi ({{x}_{2}})-\bar{\phi }\rangle \\ & =\left\langle \phi ({{x}_{1}})-\frac{1}{n}\sum\limits_{i=1}^{l}{\phi ({{x}_{i}})},\phi ({{x}_{2}})-\frac{1}{n}\sum\limits_{i=1}^{l}{\phi ({{x}_{i}})} \right\rangle \\ & =k({{x}_{1}},{{x}_{2}})-\frac{1}{n}\sum\limits_{i=1}^{n}{k({{x}_{i}},{{x}_{2}})}-\frac{1}{n}\sum\limits_{j=1}^{n}{k({{x}_{1}},{{x}_{j}})}+\frac{1}{{{n}^{2}}}\sum\limits_{i,j=1}^{n}{k({{x}_{i}},{{x}_{j}})}. \end{align} $
$\bar{\phi }$为特征空间中总体样本的中心向量.中心化的核矩阵KC计算方法如下:
${{K}_{C}}=K-\frac{1}{l}1{{1}^{T}}K-\frac{1}{l}K1{{1}^{T}}+\frac{1}{{{l}^{2}}}({{1}^{T}}K1)1{{1}^{T}}=\left[ I-\frac{1{{1}^{T}}}{l} \right]K\left[ I-\frac{1{{1}^{T}}}{l} \right], $
其中,1∈$\mathbb{R}$l×1表示元素全为1的向量,I为单位矩阵.不难得出, $\left[ I-\frac{1{{1}^{T}}}{l} \right]\left[ I-\frac{1{{1}^{T}}}{l} \right]=\left[ I-\frac{1{{1}^{T}}}{l} \right]. $ CKTA的形式如下:
$CKTA({{K}_{C}},Y)=\frac{{{\langle {{K}_{C}},Y\rangle }_{F}}}{\sqrt{{{\langle {{K}_{C}},{{K}_{C}}\rangle }_{F}}}\sqrt{{{\langle Y,Y\rangle }_{F}}}}. $
与KTA类似,CKTA可转换为如下形式:
$CKTA(K,Y)=\frac{1}{\sqrt{\frac{1}{{{l}^{2}}}{{\langle {{K}_{C}},{{K}_{C}}\rangle }_{F}}}}{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}({{K}_{C}},Y). $
1.3 EKTAKandola[12]提出了EKTA,使用了样本容量对样本类别标记做如下调整:
$ {{y}_{i}}=\left\{ \begin{array}{*{35}{l}} \frac{1}{{{l}_{+}}},\text{ }{{y}_{i}}=1 \\ -\frac{1}{{{l}_{-}}},\text{ }{{y}_{i}}=-1 \\ \end{array} \right., $
则目标矩阵YE为
$ {{[{{Y}_{E}}]}_{i,j}}={{y}_{i}}\cdot {{y}_{j}}=\left\{ \begin{array}{*{35}{l}} \frac{1}{l_{+}^{2}},\text{ }{{y}_{i}}={{y}_{j}}=1 \\ \frac{1}{l_{-}^{2}},\text{ }{{y}_{i}}={{y}_{j}}=-1 \\ -\frac{1}{{{l}_{+}}{{l}_{-}}},\text{ }{{y}_{i}}\ne {{y}_{j}} \\ \end{array} \right.. $
引理1. 对于任意对称半正定核矩阵K∈$\mathbb{R}$l×l与目标矩阵Y:
${{\langle K,{{Y}_{E}}\rangle }_{F}}={{\langle {{K}_{C}},Y\rangle }_{F}}\cdot {{\left( \frac{l}{2{{l}_{+}}{{l}_{-}}} \right)}^{2}}. $
证明:由矩阵中心化的定义,中心化目标矩阵YC与YE具有如下关系:
$\frac{{{Y}_{E}}}{\sqrt{{{\langle {{Y}_{E}},{{Y}_{E}}\rangle }_{F}}}}=\frac{{{Y}_{C}}}{\sqrt{{{\langle {{Y}_{C}},{{Y}_{C}}\rangle }_{F}}}}. $
因此, $ \frac{{{\langle K,{{Y}_{E}}\rangle }_{F}}}{\sqrt{{{\langle {{Y}_{E}},{{Y}_{E}}\rangle }_{F}}}}=\frac{{{\langle K,{{Y}_{C}}\rangle }_{F}}}{\sqrt{{{\langle {{Y}_{C}},{{Y}_{C}}\rangle }_{F}}}}. $
由于 $\sqrt{{{\langle {{Y}_{C}},{{Y}_{C}}\rangle }_{F}}}=4\cdot \frac{{{l}_{+}}{{l}_{-}}}{l},\sqrt{{{\langle {{Y}_{E}},{{Y}_{E}}\rangle }_{F}}}=\frac{1}{{{l}_{+}}{{l}_{-}}}, $ 可得出:
${{\langle K,{{Y}_{E}}\rangle }_{F}}={{\langle K,{{Y}_{C}}\rangle }_{F}}\cdot {{\left( \frac{l}{2{{l}_{+}}{{l}_{-}}} \right)}^{2}}. $
由 $\left[ I-\frac{1{{1}^{T}}}{l} \right]\left[ I-\frac{1{{1}^{T}}}{l} \right]=\left[ I-\frac{1{{1}^{T}}}{l} \right] $ ,可得${{\left\langle K,{{Y}_{C}} \right\rangle }_{F}}={{\left\langle K,{{Y}_{C}} \right\rangle }_{F}}$,于是有:
$ {{\langle K,{{Y}_{E}}\rangle }_{F}}={{\langle {{K}_{C}},Y\rangle }_{F}}\cdot {{\left( \frac{l}{2{{l}_{+}}{{l}_{-}}} \right)}^{2}}. $
依据引理1可将EKTA转化为
$ EKTA(K,{{Y}_{E}})=\frac{{{\langle K,{{Y}_{E}}\rangle }_{F}}}{\sqrt{{{\langle K,K\rangle }_{F}}}\sqrt{{{\langle {{Y}_{E}},{{Y}_{E}}\rangle }_{F}}}}=\frac{{{\langle {{K}_{C}},Y\rangle }_{F}}{{\left( \frac{l}{2{{l}_{+}}{{l}_{-}}} \right)}^{2}}}{\sqrt{{{\langle K,K\rangle }_{F}}}\sqrt{{{\langle {{Y}_{E}},{{Y}_{E}}\rangle }_{F}}}}=\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}\frac{1}{\sqrt{\frac{1}{{{l}^{2}}}{{\langle K,K\rangle }_{F}}}}{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}({{K}_{C}},Y). $
1.4 FSMFSM为特征空间中正负类中心的距离与特征空间中同类样本在正负类中心所确定的方向上总偏差的比值:
$\begin{matrix} FSM(k)=\frac{std}{||{{\phi }_{+}}-{{\phi }_{-}}||}\text{,} \\ std=st{{d}_{+}}+st{{d}_{-}}=\sqrt{\frac{\sum\limits_{i=1}^{{{n}_{+}}}{{{\langle \phi ({{x}_{i}})-{{\phi }_{+}},e\rangle }^{2}}}}{{{l}_{+}}-1}}+\sqrt{\frac{\sum\limits_{i=1}^{{{n}_{-}}}{{{\langle \phi ({{x}_{i}})-{{\phi }_{-}},e\rangle }^{2}}}}{{{l}_{-}}-1}},其中,e=\frac{{{\phi }_{+}}-{{\phi }_{-}}}{||{{\phi }_{+}}-{{\phi }_{-}}||}. \\ \end{matrix}$
φ+为正类样本在特征空间的中心,φ-为负类样本在特征空间的中心,||φ+-φ-||为两类中心的距离,std+与std-分别为特征空间中正类与负类样本在两类中心所确定的方向上的偏差.FSM值越小,则表明核函数越好.由φ+,φ-与核距离的定义可得:
$ \begin{align} & ||{{\phi }_{+}}-{{\phi }_{-}}|{{|}^{2}}=\langle {{\phi }_{+}},{{\phi }_{+}}\rangle +\langle {{\phi }_{-}},{{\phi }_{-}}\rangle -2\langle {{\phi }_{+}},{{\phi }_{-}}\rangle \\ & \text{ }=\left\langle \frac{1}{{{l}_{+}}}\sum\limits_{i=1}^{{{l}_{+}}}{{{\phi }_{i}}},\frac{1}{{{l}_{+}}}\sum\limits_{i=1}^{{{l}_{+}}}{{{\phi }_{i}}} \right\rangle +\left\langle \frac{1}{{{l}_{-}}}\sum\limits_{i=1}^{{{l}_{-}}}{{{\phi }_{i}}},\frac{1}{{{l}_{-}}}\sum\limits_{i=1}^{{{l}_{-}}}{{{\phi }_{i}}} \right\rangle -2\left\langle \frac{1}{{{l}_{+}}}\sum\limits_{i=1}^{{{l}_{+}}}{{{\phi }_{i}}},\frac{1}{{{l}_{-}}}\sum\limits_{i=1}^{{{l}_{-}}}{{{\phi }_{i}}} \right\rangle \\ & \text{ }=\frac{1}{l_{+}^{2}}\sum\limits_{i=1,j=1}^{{{l}_{+}},{{l}_{+}}}{\langle {{\phi }_{i}},{{\phi }_{j}}\rangle }+\frac{1}{l_{-}^{2}}\sum\limits_{i=1,j=1}^{{{l}_{-}},{{l}_{-}}}{\langle {{\phi }_{i}},{{\phi }_{j}}\rangle }-2\frac{1}{{{l}_{+}}{{l}_{-}}}\sum\limits_{i=1,j=1}^{{{l}_{+}},{{l}_{-}}}{\langle {{\phi }_{i}},{{\phi }_{j}}\rangle } \\ & \text{ }=\frac{1}{l_{+}^{2}}\sum\limits_{i=1,j=1}^{{{l}_{+}},{{l}_{+}}}{k({{x}_{i}},{{x}_{j}})}+\frac{1}{l_{-}^{2}}\sum\limits_{i=1,j=1}^{{{l}_{-}},{{l}_{-}}}{k({{x}_{i}},{{x}_{j}})}-2\frac{1}{{{l}_{+}}{{l}_{-}}}\sum\limits_{i=1,j=1}^{{{l}_{+}},{{l}_{-}}}{k({{x}_{i}},{{x}_{j}})} \\ & \text{ }={{\langle K,{{Y}_{E}}\rangle }_{F}}. \\ \end{align} $
再由引理1, $||{{\phi }_{+}}-{{\phi }_{-}}|{{|}^{2}}={{\langle K,{{Y}_{E}}\rangle }_{F}}={{\langle {{K}_{C}},Y\rangle }_{F}}\cdot {{\left( \frac{l}{2{{l}_{+}}{{l}_{-}}} \right)}^{2}}\text{.} $ 定义stdu与eu为
$st{{d}_{u}}=\sqrt{\frac{\sum\limits_{i=1}^{{{n}_{+}}}{{{\langle \phi ({{x}_{i}})-{{\phi }_{+}},{{e}_{u}}\rangle }^{2}}}}{{{l}_{+}}-1}}+\sqrt{\frac{\sum\limits_{i=1}^{{{n}_{-}}}{{{\langle \phi ({{x}_{i}})-{{\phi }_{-}},{{e}_{u}}\rangle }^{2}}}}{{{l}_{-}}-1}},\text{ }{{e}_{u}}={{\phi }_{+}}-{{\phi }_{-}},$
则FSM可转化为
$ \frac{1}{FSM(k)}=\frac{||{{\phi }_{+}}-{{\phi }_{-}}|{{|}^{2}}}{st{{d}_{u}}}=\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}\cdot \frac{{{l}^{2}}}{{{l}_{+}}{{l}_{-}}\cdot \left( \sqrt{\frac{1}{{{l}_{+}}-1}\sum\limits_{i=1}^{{{n}_{+}}}{{{\langle \phi ({{x}_{i}})-{{\phi }_{+}},{{\phi }_{+}}-{{\phi }_{-}}\rangle }^{2}}}}+\sqrt{\frac{1}{{{l}_{-}}-1}\sum\limits_{i=1}^{{{n}_{-}}}{{{\langle \phi ({{x}_{i}})-{{\phi }_{-}},{{\phi }_{+}}-{{\phi }_{-}}\rangle }^{2}}}} \right)}{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}({{K}_{C}},Y). $
1.5 KCSMKCSM的形式如下,其与Fisher线性判别分析的形式一致:
$ KCSM(k)=\frac{Tr({{S}_{B}})}{Tr({{S}_{W}})}. $
SB和SW分别表示类间散布矩阵和类内散布矩阵;Tr代表矩阵的迹,对于二分类问题:
$ \begin{align} & Tr({{S}_{B}})={{l}_{+}}||{{\phi }_{+}}-\bar{\phi }|{{|}^{2}}+{{l}_{-}}||{{\phi }_{-}}-\bar{\phi }|{{|}^{2}}, \\ & Tr({{S}_{W}})=\sum\limits_{i=1}^{{{l}_{+}}}{||\phi ({{x}_{i}})-{{\phi }_{+}}|{{|}^{2}}}+\sum\limits_{i=1}^{{{l}_{-}}}{||\phi ({{x}_{i}})-{{\phi }_{-}}|{{|}^{2}}.} \\ \end{align} $
$||{{\phi }_{+}}-\bar{\phi }|| $ 与 $||{{\phi }_{-}}-\bar{\phi }|| $ 为类中心到样本中心的距离, $||\phi \left( {{x}_{i}} \right)-{{\phi }_{+}}|| $ 为样本到类中心的距离.
$ \begin{align} & ||{{\phi }_{+}}-\bar{\phi }|{{|}^{2}}=\langle {{\phi }_{+}},{{\phi }_{+}}\rangle +\langle \bar{\phi },\bar{\phi }\rangle -2\langle {{\phi }_{+}},\bar{\phi }\rangle =\frac{1}{l_{+}^{2}}\sum\limits_{i,j=1}^{{{l}_{+}}}{k({{x}_{i}},{{x}_{j}})}+\frac{1}{{{l}^{2}}}\sum\limits_{i,j=1}^{l}{k({{x}_{i}},{{x}_{j}})}-2\frac{1}{{{l}_{+}}}\frac{1}{l}\sum\limits_{i=1}^{{{l}_{+}}}{\sum\limits_{j=1}^{l}{k({{x}_{i}},{{x}_{j}})}}, \\ & ||{{\phi }_{-}}-\bar{\phi }|{{|}^{2}}=\langle {{\phi }_{-}},{{\phi }_{-}}\rangle +\langle \bar{\phi },\bar{\phi }\rangle -2\langle {{\phi }_{-}},\bar{\phi }\rangle =\frac{1}{l_{-}^{2}}\sum\limits_{i,j=1}^{{{l}_{-}}}{k({{x}_{i}},{{x}_{j}})}+\frac{1}{{{l}^{2}}}\sum\limits_{i,j=1}^{l}{k({{x}_{i}},{{x}_{j}})}-2\frac{1}{{{l}_{-}}}\frac{1}{l}\sum\limits_{i=1}^{{{l}_{-}}}{\sum\limits_{j=1}^{l}{k({{x}_{i}},{{x}_{j}})}}. \\ \end{align} $将 $||{{\phi }_{+}}-\bar{\phi }|{{|}^{2}} $ 与 $||{{\phi }_{-}}-\bar{\phi }|{{|}^{2}} $ 带入Tr(SB):
$ Tr({{S}_{B}})={{\langle {{K}_{C}},Y\rangle }_{F}}\cdot \frac{l}{4{{l}_{+}}{{l}_{-}}}. $
由此可得:
$KCSM(k)=\frac{\frac{{{l}^{3}}}{4{{l}_{+}}{{l}_{-}}}\cdot \frac{1}{{{l}^{2}}}{{\langle {{K}_{C}},Y\rangle }_{F}}}{\sum\limits_{i=1}^{{{l}_{+}}}{||\phi ({{x}_{i}})-{{\phi }_{+}}|{{|}^{2}}}+\sum\limits_{i=1}^{{{l}_{-}}}{||\phi ({{x}_{i}})-{{\phi }_{-}}|{{|}^{2}}}}=\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}\frac{1}{\frac{1}{l}\sum\limits_{i=1}^{{{l}_{+}}}{||\phi ({{x}_{i}})-{{\phi }_{+}}|{{|}^{2}}}+\frac{1}{l}\sum\limits_{i=1}^{{{l}_{-}}}{||\phi ({{x}_{i}})-{{\phi }_{-}}|{{|}^{2}}}}{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}{{\langle {{K}_{C}},Y\rangle }_{F}}. $
2 讨 论本节首先讨论上述5种普适性核度量标准与特征空间中线性假设平均间隔的关系,指出上述5种度量标准都是对特征空间中线性假设平均间隔的度量;然后,分别讨论类别分布敏感性、线性平移敏感性和异方差数据敏感性,分析上述问题的产生原因.
2.1 特征空间中线性假设的期望间隔首先定义特征空间中对偶形式的线性假设,并给出该线性假设的期望间隔.
定义1(特征空间中线性假设). k为定义在X×X上的对称半正定核,并且有(x',y')∈X×Y.对于任意x∈X,定义特征空间中线性假设h*(x)为
$ {{h}^{*}}\left( x \right)={{E}_{\mathbf{x}'}}[a'y'k(x,x')],a'\in \mathbb{R},a'\ge 0. $
对于容量为l的样本,基于该样本的特征空间中经验线性假设为
${{h}^{*}}(x)=\frac{1}{l}\sum\limits_{i=1}^{l}{{{\alpha }_{i}}{{y}_{i}}k(x,{{x}_{i}})},\text{ }{{\alpha }_{i}}\in \mathbb{R},\text{ }{{\alpha }_{i}}\ge 0.$
定义2(线性假设的期望间隔). 给定任意的(x,y)∈X×Y,h(x)的函数间隔为yh*(x),那么基于分布D的期望间隔为
$ {{E}_{\mathbf{x}}}\left[ y{{h}^{*}}\left( x \right) \right]={{E}_{\mathbf{x}}}[y{{E}_{\mathbf{x}}}'[a'y'k(x,x')]]={{E}_{\mathbf{x}}}_{,x'}[a'yy'k(x,x')],a'\in \mathbb{R},a'\ge 0. $
对于容量为l的样本,在该样本上的平均间隔为
$ {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}}_{{{x}_{i}}}}[y{{h}^{*}}(x)]=\frac{1}{l}\sum\limits_{i=1}^{l}{{{y}_{i}}\left[ \frac{1}{l}\sum\limits_{j=1}^{l}{{{\alpha }_{j}}{{y}_{j}}k({{x}_{i}},{{x}_{j}})} \right]=\frac{1}{{{l}^{2}}}\sum\limits_{i=1,j=1}^{l,l}{{{\alpha }_{j}}{{y}_{i}}{{y}_{j}}k({{x}_{i}},{{x}_{j}})}},\text{ }{{\alpha }_{j}}\in \mathbb{R},\text{ }{{\alpha }_{j}}\ge 0. $
定理1给出了期望间隔与h*(x)泛化误差间的关系.
定理1(线性假设的泛化误差上界). 令R(h)为h*(x)的泛化误差.对于任意对称半正定核函数k,supx,x'∈Xk(x, x')≤B,supx∈Xα≤A,有:$R({{h}^{*}})\le 1-\frac{{{E}_{x}}[y{{h}^{*}}(x)]}{AB}.$
证明:依据Cauchy-Schwarz不等式:
$ |{{E}_{x}}[y{{h}^{*}}(x)]|=|{{E}_{x,{x}'}}[{\alpha }'y{y}'k(x,{x}')]|\le \sqrt{{{E}_{x,{x}'}}[{{({\alpha }'y{y}')}^{2}}]{{E}_{x,{x}'}}[{{k}^{2}}(x,{x}')]}=\sqrt{{{E}_{x,{x}'}}[{{({\alpha }')}^{2}}]{{E}_{x,{x}'}}[{{k}^{2}}(x,{x}')]}\le AB. $基于上式:
$1-R({{h}^{*}})=\Pr [y{{h}^{*}}(x)\ge 0]=E[{{1}_{\{y{{h}^{*}}(x)\ge 0\}}}]\ge E\left[ \frac{y{{h}^{*}}(x)}{AB}{{1}_{\{y{{h}^{*}}(x)\ge 0\}}} \right]\ge \frac{E[y{{h}^{*}}(x)]}{AB},$
其中,1e为事件e的指示函数,当e发生时,1e的值为1.
由定理1可见,h(x)的泛化误差上界与期望间隔成反比例关系.即,增大期望间隔可降低泛化误差上界.下述定理保证最大化 ${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y) $ 与最大化平均间隔是等价的.
定理2. 假设α'与y'k(x,x')相互独立,对于容量为l的样本,最大化 ${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y) $ 与最大化平均间隔 ${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}}_{{{x}_{i}}}}[y{{h}^{*}}(x)] $ 是等价的.
证明:由于α'与y'k(x,x')相互独立:
$ {{E}_{x}}[y{{h}^{*}}(x)]={{E}_{x}}[{{E}_{{{x}'}}}[{\alpha }'y{y}'k(x,{x}')]]={{E}_{x}}[{{E}_{{{x}'}}}[{\alpha }']{{E}_{{{x}'}}}[y{y}'k(x,{x}')]]=E[{\alpha }']E[y{y}'k(x,{x}')]. $
对于容量为l的样本:
$ {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}}_{{{x}_{i}}}}[y{{h}^{*}}(x)]=\frac{1}{l}\sum\limits_{j=1}^{l}{{{\alpha }_{j}}}\frac{1}{{{l}^{2}}}\sum\limits_{i=1,j=1}^{l,l}{{{y}_{i}}{{y}_{j}}k({{x}_{i}},{{x}_{j}})}. $
由 $ {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y) $ 的定义以及αj≥0可得:
$ {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}}_{{{x}_{i}}}}[y{{h}^{*}}(x)]=\frac{1}{l}\sum\limits_{j=1}^{l}{{{\alpha }_{j}}}\cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y)=\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}})\cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y)\propto {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y), $
其中, $ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}})=\frac{1}{l}\sum\limits_{j=1}^{l}{{{\alpha }_{j}}}. $
依据定理2,将KTA,EKTA,CKTA,FSM与KCSM的 $ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}}) $ 项与 ${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y) $ 项列于表 1中.可见,5种度量标准的差异主要体现在了 $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}}) $ 项上,并可得出如下结论:KTA,EKTA,CKTA,FSM与KCSM是在核函数所构造的特
征空间中对线性假设的平均间隔的度量.若某核函数具有较高度量值,那么在由其构造的特征空间中,线性假设将具有较高的平均间隔.需要特别指出的是,这与支持向量机最大化最小间隔的优化标准存在偏差.通常情况下,平均间隔与最小间隔具有较大差异,因此,对于支持向量机更适于直接度量最小间隔而不是平均间隔.然而,平均间隔与最小间隔相比具有较好的统计稳定性,因此需要在统计稳定性与度量偏差间进行折中,可使用k间隔[23]或使用靠近边界样本的平均间隔近似最小间隔.
类别分布敏感性是指普适性核度量标准的度量值随着两类样本分布变化,即使样本在某核函数构造的特征空间中线性可分,该核函数也可能获得较低的度量值.采用二维空间非平衡数据(X⊂$\mathbb{R}$2)模拟样本经核函数映射后在特征空间中的分布情况,以此展示各普适性度量标准对类别分布的敏感性,如图 1.核函数为k(xi,xj)= $\left\langle {{x}_{i}},{{x}_{j}} \right\rangle $,类别分布由α∈[0, 1]确定,有比例为α的样本在(-1,1)处具有类别标记“1”,其余1-α的样本在(1,1)处具有类别标记“-1”.显然,对于任意α,样本集都线性可分,各普适性核度量标准的度量值应为其最优值.各普适性度量标准的度量值见表 2.
由表 2可见:FSM与KCSM达到其最优值;而KTA,EKTA和CKTA没有达到最优度量值,并且度量值随着类别分布比例α变化.因此,仅有FSM与KCSM不具有类别分布敏感性.通过表 1比较5种度量标准可发现:FSM与KCSM都具有因子 $\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}},\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}\text{,}$ 反映了类别的分布比例.乘上 $\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}\text{,}$ 可消除普适性度量标准的类别分布敏感性.通过乘上$\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}\text{,}$CKTA可获得其最优度量值1.0.$\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}$仅与数据相关.由于通常假设样本依据分布D独立同分布抽取,即,对于不同样本可假定类别分布具有较小波动,当样本给定,$\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}$为独立于核函数的常数,因此,是否具有$\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}$项不影响核函数度量结果的相对关系.EKTA具有$\frac{{{l}^{2}}}{4{{l}_{+}}{{l}_{-}}}$但其仍然具有类别分布敏感性,其主要原因是:EKTA与KTA具有线性平移敏感性,其度量值与样本的绝对位置相关.
2.3 线性平移敏感性SVM等核方法对旋转、平移、尺度变换等线性变换具有不变性,这就要求普适性核度量标准应同样具有该性质[15].半正定核函数k(xi,xj)= $ \left\langle \phi \left( {{x}_{i}} \right),\phi \left( {{x}_{j}} \right) \right\rangle $ 具有旋转不变性,因此,普适性核度量标准也具有旋转不变性.5种普适性核度量标准都具有规范化项( $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}})$ 项),所以都具有尺度变换不变性.因此,重点讨论线性平移敏感性.线性平移敏感性是指在特征空间中进行平移变换φ(x)→φ(x)+δ,度量值将是δ的函数.因为平移变换不改变数据的可分性,所以度量值应为恒定值.采用二维空间数据(X⊂$\mathbb{R}$2)模拟样本经核函数映射后在特征空间中的分布情况,展示各普适性度量标准的线性平移敏感性,如图 2所示.
核函数为k(xi,xj)=$\left\langle {{x}_{i}},{{x}_{j}} \right\rangle $,在(-1,1)处的样本具有类别标记“1”,在(-1+2cos(θ),1+2sin(θ))处的样本具有类别标记“-1”,两类样本具有相同容量.对于任意θ,该实例皆线性可分,因此,普适性核度量标准应为各自的最优值.各度量标准的度量值列入表 3中.通过表 3可见:CKTA,FSM与KCSM的度量值为各自的最优值;KTA与EKTA具有相同的度量值,并且度量值随着θ而变化.由此可见,KTA与EKTA具有线性平移敏感性,而CKTA,FSM, KCSM不具有.
由表 1,对比KTA,EKTA,CKTA,FSM与KCSM可发现:除KTA外,其他度量标准使用${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}({{K}_{C}},Y)$替代${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}(K,Y)$,由于${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}_{u}}({{K}_{C}},Y)$使用中心化核函数,因此不具有线性平移敏感性.比较CKTA与EKTA,CKTA使用${{\left\langle {{K}_{C}},{{K}_{C}} \right\rangle }_{F}}$替代了${{\left\langle K,K \right\rangle }_{F}},{{\left\langle {{K}_{C}},{{K}_{C}} \right\rangle }_{F}}$不具有线性平移敏感性.FSM与KCSM在计算类内散度时使用的是样本点间的核距离[24],核距离不具有线性平移敏感性,从而使得FSM与KCSM不具有线性平移敏感性.
2.4 异方差数据敏感性FSM被指出具有异方差数据敏感性[25],然而,本文研究发现,5种度量标准都具有异方差数据敏感性.异方差数据敏感性是指在特征空间中两类样本分布的方差对度量值的影响,即使在线性可分的情况下,也可能获得较低的度量值.各度量标准中$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}})$描述了数据的散布程度,其形式与方差相似.KTA,EKTA,CKTA使用核函数平方的均值($\frac{1}{{{l}^{2}}}{{\langle K,K\rangle }_{F}}$)或中心化核函数平方的均值($\frac{1}{{{l}^{2}}}{{\langle {{K}_{C}},{{K}_{C}}\rangle }_{F}}$)度量数据的散布程度.FSM与KCSM使用数据点到类中心的距离度量数据的散布程度.5种度量标准具有异方差数据敏感性,是由于 $ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}}) $ 度量数据散布程度具有异方差数据敏感性.
本文采用二维空间数据(X⊂$\mathbb{R}$2)模拟样本经核函数映射后在特征空间中的分布情况,验证普适性核度量标准的异方差数据敏感性是由 $ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}}) $ 产生的.使用两个二元正态分布生成数据,如图 3所示:类别“1”的中心在(0.4, 0),协方差矩阵为 $\left[ \begin{matrix} 0.01 & 0 \\ 0 & 1 \\ \end{matrix} \right]\text{;}$ 类别“-1”的中心在(-0.4,0),协方差矩阵为 $\left[ \begin{matrix} 0.01 & 0 \\ 0 & var \\ \end{matrix} \right]\text{.}$ 其中,var以0.1为步长从0.1递增到10,每类500个样本.对于每个var,重复进行100次上述过程,其结果取平均值.图 4展示了 $ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}}) $ 随var变化的曲线,图中还展示了两类中心距离(DBC)随var变化的曲线,以反映$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}}) $的变化是由于异方差数据敏感性产生而不是由于随机数据波动产生的.可见,$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{E}({{\alpha }_{j}}) $随var的变化而大幅度变化,其中,FSM变化最为剧烈,并且在每个var的100组数据上的方差最大.FSM更容易受到异方差数据的影响.
本文使用来自UCI的9个数据集和20Newsgroups数据集进行核函数选择实验.UCI数据集中的多分类问题使用“one-vs-one”策略转化为多个二分类问题,各数据集信息列于表 4中,包括特征数量、样本容量.在UCI数据集上采用10折交叉验证的方法估计错误率.采用文献[26]所提供的20Newsgroups数据集(http://www.cad. zju.edu.cn/home/dengcai/Data/TextData.html),包含样本18 846,特征26 214.该数据集已经划分训练集和测试集,训练集包含样本11 314(60%),测试集包含样本7 532(40%).在训练集上采用核函数度量标准选择核函数,在测试集上验证所选择核函数的分类错误率.核方法使用SVM,训练工具采用LIBSVM.参数γ为0.1,1,2,4,8,16,32的RBF核与参数d为1,2,3,4的多项式核作为被度量的核函数.SVM的惩罚因子C使用10折交叉验证,从0.01,0.1, 1,10,100中选择.
KTA,EKTA,CKTA,FSM与KCSM在每个数据集上选出的核函数及10折交叉验证错误率(20Newgroups为在测试集上的分类错误率)列入表 5中,括号内为错误率方差.其中,BEST为通过10折交叉验证获得的最小错误率(20Newgroups为在测试集上的最小分类错误率),P代表多项式核,R代表RBF核,后续数值为核函数的参数,如:P3代表参数d为3的多项式核.表中黑体数据表示通过置信度为95%的T检验,与BEST无显著差异.标有下划线的数据表示通过置信度95%的T检验,与BEST存在显著差异(差于BEST),但显著优于其他普适性度量标准.Win 1行代表在19组分类问题上与BEST无显著性差异的数量,Win 2行代表在19组分类数问题上显著好于其他普适性度量标准的数量.
由表 5可见,普适性核度量标准选择出的核函数达到或接近交叉验证方法选择的最优核函数的分类效果,表明了普适性核度量标准在核函数选择问题上的有效性.但是这5种普适性度量标准都没有完全与BEST一致或无显著性差异,最多仅在10个数据集上与BEST无显著差异,可见,普适性度量标准还需进一步研究.KTA, EKTA,CKTA基于Alignment思想的度量标准好于FSM与KCSM的基于可分性度量的标准.在本文的实验中,对KTA进行改进的EKTA与FSM并没有显著好于KTA的效果.CKTA为效果最好的普适性度量标准,在10个二分类问题上与BEST无显著性差异,在17个二分类问题上显著好于其他度量标准.通过比较KTA,EKTA与CKTA,可验证CKTA所解决的线性平移敏感性问题在真实问题集上的有效性.FSM为效果最差的普适性度量标准,并且较倾向于选择具有较小γ值的RBF核(R0.1),文献[27]也同样发现了该现象.FSM更容易受到异方差数据的影响,是导致其效果较差的原因之一.虽然FSM同样解决了KTA的线性平移敏感性问题,但引入了较为严重的异方差数据敏感性问题,使得其效果较差.KCSM效果好于FSM,但由于其基于Fisher判别分析,假设数据符合正态分布,因此也限制了其效果[20].
4 结束语本文对KTA,EKTA,CKTA,FSM和KCSM这5种普适性度量标准进行了比较研究,发现上述5种普适性度量标准具有较为相近的形式;并且发现其度量内容为特征空间中某一线性假设的平均间隔,与支持向量机最大化最小间隔的优化标准存在偏差.使用模拟数据分析了上述标准的类别分布敏感性、线性平移敏感性、异方差数据敏感性,指出了各度量标准的数据敏感性问题的产生原因.最后,在9个UCI数据集和20Newsgroups数据集上比较了上述标准的度量效果,由于CKTA解决了KTA的线性变换敏感性问题,并且受异方差数据影响较弱,是度量效果相对最好的普适性核度量标准.
[1] | Schölkopf B, Smola A. Learning with Kernels. Cambridge: MIT Press, 2002. 1-45. |
[2] | Fernández-Delgado M, Cernadas E, Barro S, Amorim D. Do we need hundreds of classifier to solve real world classification problems? Journal of Machine Learning Research, 2014,15(10):3133-3181.. |
[3] | Ramachandram D, Mandava R, Ehsan AM. A survey of the state of the art in learning the kernels. Knowledge and Information Systems, 2012,31(2):193-221 . |
[4] | Wang TH, Zhao DY, Tian SF. An overview of kernel alignment and its application. Artificial Intelligence Review, 2012,43(2): 179-192 . |
[5] | Elisseeff A, Pontil M. Leave-One-Out error and stability of learning algorithms with applications. In: Proc. of the Advances in Learning Theory: Methods, Models and Applications. 1994. 1-15. |
[6] | Chapelle O, Vapnik V. Model selection for support vector machines. In: Solla SA, Leen TK, Müller K, eds. Proc. of the Advances in Neural Information Processing Systems 12. Cambridge: MIT Press, 1999. 230-236. |
[7] | Lanckriet GR, Cristianini N, Bartlett P, Ghaoui LE, Jordan MI. Learning the kernel matrix with semi-definite programming. Journal of Machine Learning Research, 2004,5(1):27-72. |
[8] | Wang CQ, Chen JM, Hu CH, Sun YX. Kernel matrix learning with a general regularized risk functional criterion. Journal of Systems Engineering and Electronics, 2010,21(1):72-80 . |
[9] | Girolami M, Rogers S. Hierarchic Bayesian models for kernel learning. In: Raedt LD, Wrobel S, eds. Proc. of the 22nd Int’l Conf. on Machine Learning. Bonn, 2005. 241-248 . |
[10] | Ong CS, Smola AJ, Williamson RC. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 2005,6(7): 1043-1071 . |
[11] | Cristianini N, Shawe-Taylor J, Elisseeff A, Kandola J. On kernel-target alignment. In: Dietterich TG, Becker S, Ghahramani Z, eds. Proc. of the Advances in Neural Information Processing Systems 14. Cambridge: MIT Press, 2001. 367-373. |
[12] | Kandola J, Shawe-Taylor J, Cristianini N. On the extensions of kernel alignment. In: Proc. of the Neural Networks and Computational Learning Theory. 2002. |
[13] | Cortes C, Mohri M, Rostamizadeh A. Algorithms for learning kernels based on centered alignment.Journal of Machine Learning Research, 2012,13(2):795-828. |
[14] | Meilǎ M. Data centering in feature space. In: Bishop CM, Frey BJ, eds. Proc. of the 9th Int’l Workshop on Artificial Intelligence and Statistics. 2003. |
[15] | Nguyen CH, Ho TB. An efficient kernel matrix evaluation measure. Pattern Recognition, 2008,41(11):3366-3372 . |
[16] | Wang L, Chan KL. Learning kernel parameters by using class separability measure. In: Cristianini N, Jaakkola T, Jordan M, Lanckriet G, eds. Proc. of the 6th Kernel Machines Workshop, in Conjunction with Neural Information Processing Systems. 2002. |
[17] | Loog M, Heab-Umbach R. Multi-Class linear dimension reduction by generalized fisher criteria. In: Proc. of the 6th Int’l Conf. on Spoken Language Processing. 2000. |
[18] | Nazarpour A, Adibi P. Two-Stage multiple kernel learning for supervised dimensionality reduction. Pattern Recognition, 2015,48(5): 1854-1862 . |
[19] | Ge MM, Fan LY. Learning optimal kernel for pattern classification. WSEAS Trans. on Mathematics, 2013,5(12):491-500. |
[20] | Wu XY, Mao X, Chen LJ, Xue YL, Rovetta A. Kernel optimization using nonparametric fisher criterion in the subspace. Pattern Recognition Letters, 2015,54:43-49 . |
[21] | Afkanpour A, Szepesvári C, Bowling M. Alignment based kernel learning with a continuous set of base kernels. Machine Learning, 2013,91(3):305-324 . |
[22] | Lu YT, Wang LT, Lu JF, Yang JY, Shen CH. Multiple kernel clustering based on centered kernel alignment. Pattern Recognition, 2014,47(11):3656-3664 . |
[23] | Gao W, Zhou ZH. On the doubt about margin explanation of boosting. Artificial Intelligence, 2013,203:1-18 . |
[24] | Schölkopf B. The kernel trick for distance. In: Leen TK, Dietterich TG, Tresp V, eds. Proc. of the Advances in Neural Information Processing Systems 13. Cambridge: MIT Press, 2000. 301-307. |
[25] | Chudzian P. Evaluation measures for kernel optimization. Pattern Recognition Letters, 2012,33(9):1108-1116 . |
[26] | Cai D, Wang XH, He XF. Probabilistic dyadic data analysis with local and global consistency. In: Danyluk AP, Bottou L, Littman ML eds. Proc. of the 26th Annual Int’l Conf. on Machine Learning. ACM Press, 2010. 105-112 . |
[27] | Wang PY, Cai DF. Kernel-Distance target alignment. In: Li ST, Liu CL, Wang YN, eds. Proc. of the Pattern Recognition: Communications in Computer and Information Science. Berlin: Springer-Verlag, 2014.101-110 . |