在线学习[1-3]作为一种增量式的机器学习技术，能够对模型进行实时增量更新，学习过程中随时都可以使用当前学到的模型对未知样本进行预测，一旦对样本处理完毕，不需要对其进行存储和再访问.在线学习非常适用于处理大规模流数据，不仅可以处理流数据带来的样本无限量和实时分析的挑战，还不依赖于样本独立同分布的假设[4-5].正因为如此，此研究领域得到快速发展，涌现出丰富的算法.

在线梯度下降(online gradient descent, OGD)[6]是最简单也是最流行的一阶在线学习方法，在学习的每一轮总是沿着瞬时损失函数的负梯度方向修正模型，然后再将修正后的模型投影到可行域内.被动-主动算法(passive-aggressive learning, PA)[7]采用了OGD中根据瞬时损失函数的负梯度方向更新模型，同时，在学习过程中考虑了预测的置信水平，即样本到当前决策边界的间距，更新模型时每个样本上的学习步长与该样本被分类的置信水平相关.作为PA的一种拓展算法，置信度加权学习(confidence-weighted, CW)[8-9]是一个二阶在线学习方法，不仅使用了瞬时损失函数的函数值和次梯度信息，还使用了瞬时损失函数的二阶导数信息，即Hessian矩阵信息.自适应权重正则化方法(adaptive regularization of weights, AROW)[10]将CW算法中的约束放松，转换为正则化项加到KL散度函数中，从而算法在每次学习中只需求解一个无约束的优化问题，从而提高了对噪声的鲁棒性.

然而，已有的在线学习往往假设每个流数据拥有相同且固定不变的特征空间.在实际应用中，流数据的特征空间往往是随时间变化的，具有动态性和未知性.因此，梯形特征空间的在线学习、演化特征空间的在线学习和任意特征空间的在线学习被相继提出和研究.

梯形特征空间(trapezoidal feature space)[11]是随着数据的到来特征空间呈递增状态，同时满足新到来的样本中至少拥有前一个样本的特征空间.例如，在文本分类和聚类中的无限词汇主题模型[12]，文档和文本词汇的数量都随着时间的推移而增加，从而需要更新模型以便捕获新增加术语的重要性.稀疏梯形流数据学习(sparse trapezoidal streaming data， STSD)[11,13]，将特征空间分为2部分：已有特征(existing features)和新特征(new features)，根据PA的原则，如果预测错误则更新分类器，使得损失最小化，并且接近当前的分类器；如果在学习过程中出现了新的特征，也根据结构风险最小化原则更新新特征对应的分类器权值.

在现实应用中，原有的特征空间(又称旧特征集)消失，新的特征空间出现，这种现象称为特征演化，即演化特征空间(evolvable feature space)[14].例如，已有传感器因为电池寿命、硬件损坏等原因被新的传感器取代，传感器收集的数据特征将发生变化.假设传感器电池用完的时间是可以预先知道的，则通常会在旧传感器用完之前放置一组新的传感器，因此就会有重叠时间段：旧特征集和新特征集共同存在.那么如何利用重叠周期挖掘新旧特征之间的关系，并且在只有新特征可用的情况下如何利用旧特征学习的模型？特征演化流学习(feature evolvable streaming learning, FESL)[14-15]运用OGD作为模型更新策略，通过重叠时期的样本来学习新特征到旧特征的映射，即从新特征中重建出旧特征，从而继续利用旧特征学习的模型，进而针对新旧模型提出了组合预测和当前最优预测2种集成方法.一遍增量和递减学习(one-pass incremental and decremental learning， OPID)[16]将演化特征空间分为2个阶段：压缩阶段(C-阶段)和扩展阶段(E-阶段)，并在C-阶段提出了一遍压缩学习方法，在E-阶段提出了一种新的学习方法来继承C-阶段的分类结果.在线演化度量学习(online evolving metric learning, EML)[17]在度量学习领域来研究演化特征空间.值得说明的是，文献[16-17]处理的是没有重叠时期但有重叠特征的情况.对于有重叠时期的特征演化空间，特征演化可能是不可预测的，这意味着特征可能会消失或任意出现，从而导致重叠时期参差不齐.为了解决这个问题，具有不可预测特征演化的预测学习(prediction with unpredictable feature evolution, PUFE)[18]通过矩阵补全的方法来修补重叠时期的特征.同时，在演化特征空间中，数据分布有可能发生变化，针对这个问题，特征和分布演化流学习(feature and distribution evolving stream learning， FDESL)[19]提出了一种针对特征空间和数据分布均发生变化的数据差异度量方法——演化差异(evolving discrepancy)，并给出了良好的理论保证，特别是对泛化性能的理论保证.已有的演化特征学习中往往假设每个样本预测后都会揭示其真实的类别标签，而在实际应用中这个假设大都不满足，因为大多数样本是没有类别标签的，同时人工标注类别标签是非常耗时且昂贵.为了解决这一问题，适宜存储的演化特征学习(storage-fit feature-evolvable streaming learning， SF2EL)[20]运用流形正则化技术，利用以往相似的数据，协助改进在线模型.

现有的在线学习方法假设的固定特征空间、梯形特征空间和演化特征空间都遵循着明确的规律而变化，这都限制了在动态环境中的适用性，因为在动态环境中流数据的特征空间是反复无常、任意变化的，即任意特征空间(capricious feature space)[21].基于任意特征流的在线学习(online learning from capricious data streams， OCDS)[21-22]在全局性的特征空间上提出了一个生成图模型(generative graphical model)来建立已有特征和新特征的关系，使在已有特征空间上学习的模型可以应用到新特征空间.与此同时，基于多样化特征空间的在线学习(online learning from varying feature spaces， OLVF)[23]对样本和特征空间分别进行分类，其中，为了对样本进行分类，动态地将样本分类器和训练集投影到它们的共享特征子空间上，特征空间分类器预测给定特征空间的投影置信度，最后，样本分类器根据投影置信度对约束强度进行缩放，进而根据经验风险最小化原则进行分类器更新.

无论是固定特征空间、梯形特征空间、演化特征空间，还是任意特征空间，在现实应用中均有对应的应用场景.因此，基于这4种类型的在线学习方法研究均具有很大的应用意义.

在本文中，我们将重点放在演化特征空间的在线学习方法研究上.文献[14-15]提出的特征演化流学习(FESL)算法运用了最简单的OGD作为模型更新策略，同时，在新旧特征重叠阶段只研究了重建旧特征.本文提出了一种基于被动-主动更新策略的特征演化学习算法(passive-aggressive learning with feature evolvable streams, PAFE).该算法采用了PA作为模型更新策略，其中，PA在学习过程中不仅采用了OGD中根据瞬时损失函数的负梯度方向更新模型，同时考虑了与样本相关的置信水平.在新旧特征重叠阶段，本文不仅从新特征重建了旧特征，同时从旧特征表示了新特征，为新特征的模型学习提供了合理的模型初始化.继而该算法从新特征空间和被恢复的旧特征空间中学习了2个基模型，并研究了2种集成算法：组合预测和当前最优预测.最后，在合成数据集和真实数据集上的实验结果验证了所提算法的有效性.

1 相关背景

本文主要研究演化特征空间下的在线二分类任务.在每一轮的学习中，分类器会接收到一个样本并给出预测结果，一旦给出预测结果，则揭示该样本的真实标签，进而得到分类器的瞬时损失，该损失反映了预测标签与真实标签之间的差异，根据该损失信息，算法可以改进其分类器模型，以便在下一轮中做出更好的预测.

在本文中，采用大写粗体表示矩阵，小写粗体表示向量.其中，对于任意的矩阵M∈d×n，矩阵的转置表示为MT.对于任意的方阵A∈n×n，可逆矩阵表示为A-1.表示向量v∈d的2-范数，向量v的转置表示vT.

用(xt,yt)表示每轮接收到的数据实例，其中xt∈d是具有d维特征空间的样本，yt∈{-1,+1}是其对应的真实标签.PA算法[7]将预测模型约束为线性模型wt∈d，通过预测当前样本的标签，表示为与样本相关的置信度，并采用hinge损失作为损失函数，即(wTx,y)=max(0,1-ywTx).PA算法的目标函数具体为

(1)

其中，ξ≥0是松弛变量，(ft,yt)≤ξ，且C≥0是平衡松弛项对目标函数的影响.式(1)拥有闭式解：

wt+1=wt+τtytxt，

(2)

其中，

演化特征空间表现为原有的特征空间消失，新的特征空间出现，也就是说每一个周期过程中仅包含2个特征空间，因此，我们只需要关注一个周期，就很容易拓展到很多周期的情况.图1展现了文献[15]中给出的一个周期内的演化流数据产生过程，可以总结如下：

1) 对于t=1,2,…,T1-B，分类器从特征空间S1接收一个样本d1，其中d1是特征空间S1的特征维数，T1是拥有特征空间S1的样本数.

2) 对于t=T1-B+1,T1-B+2,…,T1，分类器分别从已有特征空间S1和现有特征空间S2接收到2个样本d1和d2，其中d2是特征空间S2的特征维数.

3) 对于t=T1+1,T1+2,…,T1+T2，分类器从特征空间S2接收一个样本d2，其中T2是拥有特征空间S2的样本数.值得说明的是，新旧特征重叠的时段B相对于T1和T2来说非常小，且对于在特征空间S2的模型训练影响极小，因此，我们忽略了特征空间S2中的T1-B+1,T1-B+2,…,T1样本.

将PA算法应用到演化特征空间中，则有：

(3)

其中，对于特征空间S1有t=1,2,…,T1，特征空间S2有t=T1,T2,…,T1+T2.

2 基于PA的特征演化流学习算法

在本节中，我们首先介绍所提基于PA更新策略的特征演化学习算法PAFE的基本思想，然后引入到2个集成方法中.

基于演化特征空间的在线学习主要局限性[14-15]是在新特征空间S2的情况下，无法再接收具有特征空间S1的数据，从而会忽略S1中已经学习得到的模型，同时，忽略了已学到的模型对S2中模型的初始化.为了解决这个问题，假设新旧特征空间存在2种映射关系φ:d2→d1,ψ:d1→d2，即其中，来恢复S1中的数据，d2用S1来模拟S2中的数据，M1,M2是线性映射的系数矩阵.我们继续沿用文献[14-15]中提出的线性映射来近似这2种关系.则在新旧特征重叠时刻T1-B+1,T1-B+2,…,T1有：

(4)

(5)

式(4)和(5)的最优解为

(6)

(7)

因此，当只能从特征空间S2中接收数据d2时，我们就可以通过d1来恢复S1中的数据，进而继续更新S1中已学到的模型w1,T1.同时，对于特征空间S2的模型学习，往往是随机初始化，可以通过d2用S1来模拟S2中的数据，继而用已学到的模型w1,T1来初始化特征空间S2中的模型.

学习模型w1,T1和2个线性映射的最优系数矩阵过程如算法1所示.

算法1. 学习特征空间S1下的模型w1,T1，最优系数矩阵

① 初始化：随机初始化w1,1∈d1,A1=A2=B1=B2=0;

② for t=1:T1

③ 接收样本：d1；

④ 计算：

⑤ 揭示样本真实标签：yt∈{-1,+1}；

⑥ 瞬时损失：(f1,t,yt)；

⑦ if (f1,t,yt)>0

⑧ 用式(3)更新模型；

⑨ end if

⑩ if t>T1-B

end if

end for

输出：

在t=T1+1,T1+2,…,T1+T2时，我们可以在2个基模型w1,t,w2,t上得到2个预测值：和其中，w1,t的初始值为w1,T1，w2,t的初始值为基于这2个基模型，为了得到更好的预测结果，我们引用文献[14-15]中提出的2个集成方法：组合预测和当前最优预测.

组合预测即在第t轮的预测是基模型预测的加权平均值，如式(8)所示：

pt=a1,tf1,t+a2,tf2,t，

(8)

其中，ai,t是第i个基模型预测的权重.权重的更新如式(9)所示：

ai,t+1=vi,t/(v1,t+v2,t),i=1,2,

(9)

其中，vi,t=ai,te-η (fi,t,yt)，且具体来说，当时，定理1[14-15]给出了组合预测的损失界限，继而说明在旧特征空间的帮助下性能将得到改善.首先，我们给出在T1+1,T1+2,…,T1+T2阶段中的3种累积损失LS1,LS2,LS12，其中是2个基模型下的累积损失，是组合预测模型下的累积损失.

定理1[14-15]. 对于T2>1，在t=T1+1,T1+2,…,T1+T2时刻下，给定则组合预测模型下的累积损失LS12满足如下性质：

关于基模型的组合预测具体过程如算法2所示.

算法2. 组合预测(PAFE-c).

① 初始化：a1,T1=a2,T1=1/2,η=(8(ln 2)/T2)1/2;

② 调用算法1得到

③

④ w1,T1+1=w1,T1；

⑤

⑥ for t=T1+1:T1+T2

⑦ 接收样本：d2；

⑧ 计算：

⑨ 用式(8)计算pt；

⑩ 揭示样本真实标签：yt∈{-1,+1}；

瞬时损失：(f1,t,yt),(f2,t,yt),(pt,yt)；

用式(9)更新权重a1,t+1,a2,t+1；

if (f1,t,yt)>0

用式(3)更新模型w1,t；

end if

if (f2,t,yt)>0

用式(3)更新模型w2,t；

end if

end for

通常情况下，组合预测比只选择一个基模型的效果好[24]，但要求每个基模型的性能不能太差[25].而在PAFE问题中w1,t在特征空间S2下可能会变得越来越差.因此，本文引用另一个集成方法：当前最优预测[14-15]，它以较高的概率选择权重较大的基模型.我们通过权重的分布来选择当前最优的基模型，具体表示为

ui,t+1=ai,t/(a1,t+a2,t),i=1,2.

(10)

权重的更新如式(11)所示：

ai,t+1=δΔt/2+(1-δ)vi,t,i=1,2,

(11)

其中，H(x)=-x ln x-(1-x)ln(1-x)是在x∈(0,1)下的熵函数，η=(8/T2(2ln 2+(T2-1)H(1/(T2-1))))1/2，vi,t=ai,te-η (fi,t,yt),i=1,2,Δt=v1,t+v2,t,δ=1/(T2-1).为了从理论上保证所提算法当前最优预测的性能，定理2[14-15]给出了其累积损失的上界.

定理2[14-15]. 对于T2>1，在t=T1+1,T1+2,…,T1+T2下，当η=(8/T2(2ln 2+(T2-1)H(1/(T2-1))))1/2,δ=1/(T2-1),则当前最优预测模型下的累积损失LS12满足如下性质：

其中，

选择当前最优预测的过程具体如算法3所示.

算法3. 当前最优预测(PAFE-s).

① 初始化：a1,T1=a2,T1=1/2,η=(8/T2(2ln 2+(T2-1)H(1/(T2-1))))1/2;

② 调用算法1得到

③

④ w1,T1+1=w1,T1；

⑤

⑥ for t=T1+1:T1+T2

⑦ 接收样本：d2；

⑧ 计算：

⑨ 用式(10)选择当前最优模型wi,t；

⑩ 计算：pt=fi,t；

揭示样本真实标签：yt∈{-1,+1}；

瞬时损失：(f1,t,yt),(f2,t,yt),(pt,yt)；

用式(11)更新权重；

if (f1,t,yt)>0

用式(3)更新模型w1,t；

end if

if (f2,t,yt)>0

用式(3)更新模型w2,t；

end if

end for

3 实验与结果分析

本节我们首先介绍对比算法，其次给出实验数据集并分析其结果.

3.1 对比算法

我们将本文所提算法PAFE-c,PAFE-s和过程中产生的4个算法进行对比，同时与文献[15]中所提算法FESL-c,FESL-s进行对比，并和其过程中涉及的3个算法进行对比.值得说明的是，对比的时间段为在旧特征空间已经消失，新特征空间出现到消失，即被最新特征空间出现之前.

① NOGD[15].只考虑新特征空间的模型通过OGD进行更新；

② ROGD-u[15].通过线性映射，得到旧特征空间，进而继续用OGD更新原有旧特征空间学习到的模型；

③ ROGD-f[15].尽管通过新特征空间恢复得到旧特征空间，但用已经学习到的旧模型，且不再更新；

④ FESL-c[15].2个基模型NOGD和ROGD-u的组合预测；

⑤ FESL-s[15].2个基模型NOGD和ROGD-u的选择当前最优预测；

⑥ NPA-r.只考虑新特征空间的模型通过PA进行更新，模型的初始化为随机数值；

⑦ NPA-d.尽管只考虑新特征空间的模型通过PA进行更新，但模型的初始化是通过重叠时刻旧特征到新特征的映射得到的；

⑧ RPA-u.通过恢复得到旧特征空间，继续用PA更新原有旧特征空间已学习到的模型；

⑨ RPA-f.旧特征空间已学到的模型不再更新，直接应用至恢复的旧特征空间；

⑩ PAFE-c.2个基模型NPA-d和RPA-u的组合预测；

PAFE-s.2个基模型NPA-d和RPA-u的选择当前最优预测.

3.2 实验设置及结果分析

实验选用了和文献[15]中相同的24个二分类数据集，包含8个合成数据集和16个来自Reuters的数据集(1) http://www.lamda.nju.edu.cn/code_FESL.ashx，其中，合成数据集是通过随机高斯矩阵将原始数据集人为地映射到另一个特征空间，然后获得来自特征空间S1和S2的数据；Reuters的每个数据集都有2个视图，分别代表2种不同的语言，将2个视图视为2个特征空间.24个数据集的详细信息如表1所示，其中，前4行的数据集是合成数据集，剩余8行的数据集是来自Reuters的数据集.

我们将本文所提算法与文献[15]中所提算法进行对比，其中文献[15]所提算法的结果是直接使用文献中的结果.因此，为了算法对比的公平性，本文中设置的和文献[15]中的设置是一样的：对于合成数据集，所有算法的分类精度是通过10次独立运行的平均结果得出的，重叠时刻B的大小设置为5或者10，新旧特征空间的交替时刻T1和T2均设置为样本个数的二分之一.本文所提算法PAFE-c,PAFE-s中的超参C设置如下：

① Australian,Credit-g,German:C=0.02；

② Credit-a,Svmguide3:C=0.05；

③ Diabetes:C=0.09；

④ Kr-vs-kp,Splice:C=0.005.

表2给出了在合成数据集上所有对比算法的分类精度，其中，表2用“·”标记每个网格中较好的结果，用粗体标注最好的结果.

从表2可以看出，所提算法PAFE-c和PAFE-s均在5个数据集上优于其他对比算法，尤其是在Kr-vs-kp数据集上，分类精度比FESL-c和FESL-s高出0.102，而在数据集Credit-g和Splice上，FESL-c和FESL-s仅比本文所提算法高出0.008以内.NPA-d是用了旧特征空间已学到的模型进行初始化，所以分类精度比NPA-r的高，甚至高出0.105.同时，用恢复的旧特征空间继续更新的模型RPA-u的分类精度比RPA-f的高.然而，NOGD在6个数据集上的效果优于NPA-d，而RPA-u/RPA-f在6个数据集上的效果优于ROGD-u/ROGD-f，这个现象说明了PA更新策略更适合于数量较多的流数据.

对于数据规模较大的Reuters数据集，所有算法的分类精度是通过3次独立运行的平均结果得出的，重叠时刻B的大小均设置为50，新旧特征空间的交替时刻T1和T2也设置为样本个数的二分之一.本文所提算法PAFE-c，PAFE-s中的超参C设置如下：

① r.EN-FR,r.EN-GR,r.EN-IT,r.EN-SP,r.FR-IT,r.FR-SP,r.IT-FR,r.IT-SP:C=10-3；

② 剩余的8个Reuters数据集:C=10-4.

表3给出了在Reuters数据集上所有对比算法的分类精度，其中，表3用“·”标记每个网格中较好的结果，用粗体标注最好的结果.从表3可以看出，所提算法PAFE-s在15个数据集上优于其他对比算法，PAFE-c的分类精度均不高于PAFE-s，但在14个数据上优于其他对比算法.基本与表2的结果一致，RPA-u的分类精度比RPA-f的高，而NPA-d在大部分Reuters数据集上的分类精度比NPA-r仅高出0.005以内，这说明随着流数据的增多，模型的初始值对基于PA策略的模型更新影响越小.与表2表现不同的是，NPA-d在15个数据集上的效果优于NOGD，而ROGD-u在11个数据集上的效果优于RPA-u，这个现象再次验证了PA更新策略更适合演化特征空间中的模型学习.表3给出了在Reuters数据集上所有对比算法的分类精度.从表3可以看出，所提算法PAFE-s在15个数据集上优于其他对比算法，PAFE-c的分类精度均不高于PAFE-s，但在14个数据上优于其他对比算法.基本与表2的结果一致，RPA-u的分类精度比RPA-f的高，而NPA-d在大部分Reuters数据集上的分类精度比NPA-r仅高出0.005以内，这说明随着流数据的增多，模型的初始值对基于PA策略的模型更新影响越小.与表2表现不同的是，NPA-d在15个数据集上的效果优于NOGD，而ROGD-u在11个数据集上的效果优于RPA-u，这个现象再次验证了PA更新策略更适合演化特征空间中的模型学习.

为了验证分析的合理性，我们给出了本文所提算法在部分数据集上的平均累计损失趋势，同时也验证了所提算法的收敛性，如图2所示.在每个时刻表示为每个对比算法在1,2,…,t上的平均累积损失，即

图2中(a)～(d)和(e)～(i)分别是所提算法在合成数据集和Reuters数据集上的平均累积损失趋势，且平均累积损失越小越好.从图2可以看出，随着到来样本数量的增加，平均累积损失收敛到一个相对稳定的数值.同时，从图2中的结果中可以再次验证如下结论：1)在合成数据集上NPA-d的趋势是迅速下降，而在数据规模较大的Reuters数据集上，NPA-r的下降趋势比NPA-d更快，说明在较大的数据集上通过重叠阶段的映射用已学的旧特征模型为新特征模型初始化是非常有意义的.2)基于PA更新策略的演化特征空间学习，在数据规模较小时，组合预测PAFE-c比当前最优预测的下降趋势更为明显，相对于规模较大的数据集Reuters，当前最优预测PAFE-S的下降趋势则更为明显.

4 总 结

本文提出了一种基于PA更新策略的特征演化学习算法(PAFE).PA在学习过程中不仅采用了OGD中根据瞬时损失函数的负梯度方向更新模型，同时考虑了与样本相关的置信水平.尤其，在新旧特征重叠阶段，本文不仅重建了旧特征，同时通过已获得的旧特征模型来初始化新特征的模型，进而获得更高的算法性能.继而从新特征空间和被恢复的旧特征空间中学习了2个基模型，并研究了2种集成算法：组合预测和当前最优预测.实验表明，本文所提算法可以得到更好的分类效果.而无论本文还是文献[15]都是用一阶在线学习方法更新的模型，接下来可以从二阶信息的角度研究演化特征空间下的学习，也许可以获得更高的分类性能或者加速平均累积损失的下降速度.

参考文献

[1]Shalev-Shwartz S. Online learning and online convex optimization[J]. Foundations and Trends in Machine Learning, 2011, 4(2): 107-194

[2]Zhu Zhenfeng, Zhai Yanxiang, Ye Yangdong. A linear method for online AUC maximization[J]. Journal of Computer Research and Development, 2018, 55(12): 2725-2733 (in Chinese)(朱真峰, 翟艳祥, 叶阳东. 一种线性的在线AUC优化方法[J]. 计算机研究与发展, 2018, 55(12): 2725-2733)

[3]Li Zhijie, Li Yuanxiang, Wang Feng, et al. Big data stream oriented multi-task accelerated online learning algorithm[J]. Journal of Computer Research and Development, 2015, 52(11): 2545-2554 (in Chinese)(李志杰, 李元香, 王峰, 等. 面向大数据流的多任务加速在线学习算法[J]. 计算机研究与发展, 2015, 52(11): 2545-2554)

[4]Zhai Tingting, Gao Yang, Zhu Junwu. Survey of online learning algorithms for streaming data classification[J]. Journal of Software, 2020, 31(4): 912-931 (in Chinese)(翟婷婷, 高阳, 朱俊武. 面向流数据分类的在线学习综述[J]. 软件学报, 2020, 31(4): 912-931)

[5]Li Zhijie, Li Yuanxiang, Wang Feng, et al. Online learning algorithms for big data analytics: A survey[J]. Journal of Computer Research and Development, 2015, 52(8): 1707-1721 (in Chinese)(李志杰, 李元香, 王峰, 等. 面向大数据分析的在线学习算法综述[J]. 计算机研究与发展, 2015, 52(8): 1707-1721)

[6]Zinkevich M. Online convex programming and generalized infinitesimal gradient ascent[C] //Proc of the 20th Int Conf on Machine Learning. Menlo Park: AAAI, 2003: 928-936

[7]Crammer K, Dekel O, Keshet J, et al. Online passive-aggressive algorithms[J]. Journal of Machine Learning Research, 2006, 7(3): 551-585

[8]Dredze M, Crammer K, Pereira F. Confidence-weighted linear classification[C] //Proc of the 25th Int Conf on Machine Learning. New York: ACM, 2008: 264-271

[9]Crammer K, Dredze M, Pereira F. Exact convex confidence-weighted learning[C] //Proc of the 22nd Annual Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2009: 345-352

[10]Crammer K, Kulesza A, Dredze M. Adaptive regularization of weight vectors[C] //Proc of the 22nd Annual Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2009: 414-422

[11]Zhang Qin, Zhang Peng, Long Guodong, et al. Towards mining trapezoidal data streams[C] //Proc of 2015 IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2015: 1111-1116

[12]Zhai Ke, Boyd-Graber J. Online latent Dirichlet allocation with infinite vocabulary[C] //Proc of the 30th Int Conf on Machine Learning. Cambridge, MA: JMLR, 2013: 561-569

[13]Zhang Qin, Zhang Peng, Long Guodong, et al. Online learning from trapezoidal data streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(10): 2709-2723

[14]Hou Bojian, Zhang Lijun, Zhou Zhihua. Learning with feature evolvable streams[C] //Proc of the Annual Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2017: 1417-1427

[15]Hou Bojian, Zhang Lijun, Zhou Zhihua. Learning with feature evolvable streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(6): 2602-2615

[16]Hou Chenping, Zhou Zhihua. One-pass learning with incremental and decremental features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(11): 2776-2792

[17]Dong Jiahua, Cong Yang, Sun Gan, et al. Evolving metric learning for incremental and decremental features[J]. arXiv preprint, arXiv:2006.15334, 2020

[18]Hou Bojian, Zhang Lijun, Zhou Zhihua. Prediction with unpredictable feature evolution[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021. DOI:10.1109/TNNLS.2021.3071311

[19]Zhang Zhenyu, Zhao Peng, Jiang Yuan, et al. Learning with feature and distribution evolvable streams[C] //Proc of the 37th Int Conf on Machine Learning. Cambridge, MA: JMLR, 2020: 11317-11327

[20]Hou Bojian, Yan Yuhu, Zhao Peng, et al. Storage fit learning with feature evolvable streams[J]. arXiv preprint, arXiv:2007.11280, 2020

[21]He Yi, Wu Baijun, Wu Di, et al. Online learning from capricious data streams: A generative approach[C] //Proc of the 28th Int Joint Conf on Artificial Intelligence. Brookline, MA: Microtome Publishing, 2019: 2491-2497

[22]He Yi, Wu Baijun, Wu Di, et al. Toward mining capricious data streams: A generative approach[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 32(3): 1228-1240

[23]Beyazit E, Alagurajah J, Wu Xindong. Online learning from data streams with varying feature spaces[C] //Proc of the 33rd AAAI Conf on Artificial Intelligence. Menlo Park: AAAI, 2019, 33: 3232-3239

[24]Zhou Zhihua. Ensemble Methods: Foundations and Algorithms[M]. Boca Raton: CRC Press, 2012

[25]Freund Y, Schapire R E. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences, 1997, 55(1): 119-139

Passive-Aggressive Learning with Feature Evolvable Streams

Liu Yanfang1,2, Li Wenbin1, and Gao Yang1

1(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023) 2(College of Mathematics and Information Engineering, Longyan University, Longyan, Fujian 364012)

Abstract In many real-world applications, data are collected in the form of a feature evolvable stream. For instance, old features of data gathered by limited-lifespan sensors disappear and new features emerge at the same time along with the sensors exchanging simultaneously. Online passive-aggressive algorithms have proven to be effective in learning linear classifiers from datasets with both a fixed feature space and a trapezoidal feature space. Therefore, in this paper we propose a new feature evolvable learning based on passive-aggressive update strategy (PAFE), which utilizes the margin to modify the current classifier. The proposed algorithm learns two models through passive-aggressive update strategy from the current features and recovered features of the vanished features. Specifically, we both recover the vanished features and mine the initialization of the current model from the overlapping periods in which both old and new features are available. Furthermore, we use two ensemble methods to improve performance: combining the predictions from the two models, and dynamically selecting the best single prediction. Experiments on both synthetic and real data validate the effectiveness of our proposed algorithm.

Key words online learning; passive-aggressive strategy; supervised learning; ensemble learning; evolvable features

收稿日期：2021-04-01；

修回日期：2021-05-26

基金项目：国家重点研发计划项目(2018AAA0100905)；福建省中青年教师教育科研项目(科技类)(JAT190743)；龙岩市科技计划项目(2019LYF13002,2019LYF12010)

This work was supported by the National Key Research and Development Program of China (2018AAA0100905), the Education Scientific Research Project of Young Teachers of Fujian Province (JAT190743), and the Science and Technology Project of Longyan City (2019LYF13002, 2019LYF12010).

通信作者：高阳(gaoy@nju.edu.cn)

中图法分类号 TP391

(liuyanfang003@163.com)

Liu Yanfang, born in 1987. PhD candidate and lecturer. Member of CCF. Her main research interests include machine learning, data mining and online learning.

刘艳芳，1987年生.博士研究生，讲师,CCF会员.主要研究方向为机器学习、数据挖掘和在线学习.

Li Wenbin, born in 1991. PhD, assistant researcher. Member of CCF. His main research interests include machine learning, metric learning, few-shot learning and computer vision. (liwenbin@nju.edu.cn)

李文斌，1991年生.博士，助理研究员,CCF会员.主要研究方向为机器学习、度量学习、小样本学习和计算机视觉.

Gao Yang, born in 1972. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include reinforcement learning, multi-agent systems, computer vision and big data analysis.

高 阳，1972年生.博士，教授，博士生导师.CCF高级会员.主要研究方向为强化学习、多智能体系统、计算机视觉和大数据分析.