在无线传感器网络(WSN,wireless sensor network)的众多应用中，对监测信息进行分类是最基础也是最重要的一项任务^[1-2]. 核学习机(或核方法)作为解决分类问题的主流方法，在WSN中得到了日益广泛的应用^[3]. 然而，在WSN中训练数据都分散在各节点上，通过多跳路由将所有训练数据传输到数据中心进行集中式训练，将会消耗大量的节点能量、占用大量的带宽，这与WSN上能源替换代价非常高甚至不可替换、带宽资源非常有限相冲突，同时也容易使数据中心周围节点成为整个系统的瓶颈. 因此，通过相邻节点间的协作，利用节点本身的处理能力，在网内分布式协同学习核分类器的方法引起了众多学者的关注和研究^[4-6]. 但是，已有的WSN下核学习机分布式训练方法仍存在构建或维护特定链路代价高、基于共享数据普适性不强和支持向量机(SVM,support vector machine)增量训练通信代价大等问题. 为此，笔者以核最小平方误差(KMSE,kernel minimum squared error)方法和具有稀疏特性的L1正则化相结合，研究了仅依靠相邻节点间的协作，在网内分布式协同训练L1正则化KMSE学习机的方法，提出了基于并行投影方法的L1正则化KMSE学习机分布式(L1-DKMSE-PP，L1-regularized distributed kernel minimum squared error based on parallel projections)训练算法.

1 预备知识

考虑二分类问题，给定一组独立同分布的训练样本集S={(x_i,y_i),x_i∈R^d,y_i∈{－1,1},i=1,2,…,m}. 基于“损失函数+正则项”框架的KMSE分类问题可以归结为求解优化问题：

$\mathop {min}\limits_{f \in {H_K}} {1 \over m}\sum\limits_{i = 1}^m {{{({y_i} - f({x_i}))}^2} + \Omega ({{\left\| f \right\|}_{{H_K}}})} $

(1)

其中：f∈H_K为再生希尔伯特空间中的函数；f(x_i)为对样本x_i的期望输出；Ω(‖f‖_HK)为正则项，用于避免模型过拟合. 表示定理给出了式(1)中最优函数f^*(·)的表示形式^[3]为

${f^*}\left( \cdot \right) = \sum\limits_{i = 1}^m {{\alpha _i}k({x_i},\cdot)} $

(2)

其中：k(x_i,·)为已知样本x_i与未知样本的向量内积，用于描述两个样本间的相似程度或距离大小；α_i∈R(i=1,2,…,m)为k(x_i,·)的系数. 由式(2)可以看出，核学习机f^*(·)依赖训练样本数据.

为了说明WSN中各节点之间的相邻关系，使用无向图G(J,E)对WSN进行描述，J为节点集合，E为节点间直接通信的链路集合，每个节点j∈J及其单跳邻居节点用集合B_j⊆J来表示. 假定网络是连通的，即网络中任意两点间至少存在一条路径. 每个节点j上的训练数据集用S_j:={(x_jn,y_jn),n={1,2,…,N_j}}表示，其中x_jn∈R^d为训练数据jn的特征向量，d为特征向量维数，y_jn∈{1,－1}为训练数据jn对应的类别标签，N_j为训练数据数量. 另外，模型训练之前，相邻节点间没有相同的训练数据.

为方便描述，给出以下两个定义：

定义1(关键样本) 模型系数解向量中非零项对应的训练样本，称为关键样本.

定义2(模型稀疏率) 模型中关键样本数与参与模型训练的总样本数的比值，称为模型稀疏率.

2 L1 KMSE学习机分布式训练方法

为减少f^*(·)依赖的训练样本数量，利用L1正则化构建KMSE学习机优化问题：

$\mathop {min}\limits_{f \in {H_K}} {1 \over m}\sum\limits_{i = 1}^m {{{({y_i} - f({x_i}))}^2} + \lambda ({{\left\| f \right\|}_1})} $

(3)

其中：λ‖f‖₁为正则项，λ>0为正则项系数.

2.1 L1 KMSE学习机训练问题的推导

为减少L1正则化KMSE学习机分布式训练过程中的数据传输量，借鉴文献^[7]中基于一次全局平均一致性线性SVM分布式训练算法1-AC-DSVM的思想，构建基于节点本地模型与局部最优模型对本地训练样本预测值一致的优化问题：

$\eqalign{ & \mathop {min}\limits_{{f_j} \in {H_K}} {1 \over {{N_j}}}\sum\limits_{n = 1}^{{N_j}} {{{({y_{jn}} - {f_j}({x_{jn}}))}^2} + \lambda {{\left\| {{f_j}} \right\|}_1}} \cr & s.t.{f_j}({x_{jn}}) = \bar f_{{B_j}}^*({x_{jn}}),\forall j \in J,n = 1,2, \ldots ,{N_j} \cr} $

(4)

其中：N_j为节点j∈J上参与训练的样本数量，f_Bj^**(x_jn)为节点j及其邻居节点间的局部最优模型对本地训练样本的预测值. 为求解式(4)的优化问题，每个节点j∈J利用并行投影方法对其等式约束构建优化问题，如式(5)所示，相应的求解迭代形式如式(6)和式(7)^[8]所示.

$\eqalign{ & min{1 \over {{N_j}}}\sum\limits_{n = 1}^{{N_j}} {{{({y_{jn}} - {f_j}({x_{jn}}))}^2} + \lambda {{\left\| {{f_j}} \right\|}_1}} + \cr & {1 \over 2}\left\| {{f_j}} \right.({x_{jn}}) - \bar f_{{B_j}}^*\left. {({x_{jn}})} \right\|_2^2,\forall j \in J,n = 1,2, \ldots ,{N_j} \cr} $

(5)

$\bar f_{{B_j}}^{{*^{k + 1}}}({x_{jn}}) = {{\sum\limits_{i = 1}^{{B_j}} {f_i^{k + 1}({x_{jn}})} } \over {\left| {{B_j}} \right|}},\forall j \in J,n = 1,2, \ldots ,{N_j}$

(6)

$\eqalign{ & \sum\limits_{i = 1}^{{B_j}} {f_i^{k + 1}({x_{jn}})} = \cr & \arg \min \left\{ {{1 \over {{N_j}}}} \right.\sum\limits_{n = 1}^{{N_j}} {{{({y_{jn}} - {f_j}({x_{jn}}))}^2} + \lambda {{\left\| {{f_j}} \right\|}_1}} + \cr & {1 \over 2}\left\| {{f_j}} \right.({x_{jn}}) - \bar f_{{B_j}}^*\left. {({x_{jn}})} \right\|\left. {_2^2} \right\},\forall j \in J,n = 1,2, \ldots ,{N_j} \cr} $

(7)

式(6)中：|B_j|为B_j中元素个数，即节点j及其邻居节点数量；f_Bj^**^k+1(x_jn)为节点j的局部最优模型对其本地样本的预测值，是包括j在内的所有邻居节点的模型对节点j本地训练样本预测值的平均. 式(7)是一个无约束优化问题，求解该优化问题，利用交替方向乘子方法将其变换成等价的含有等式约束的优化问题^[8]，如式(8)所示.

$\eqalign{ & \min {1 \over {{N_j}}}{({Y_j} - {K_j}{\alpha _j})^T}({Y_j} - {K_j}{\alpha _j}) + \cr & {1 \over 2}\left\| {{K_j}{\alpha _j}} \right. - \bar f_{{B_j}}^*\left. {({x_{jn}})} \right\|_2^2 + \lambda {\left\| {{z_j}} \right\|_1} \cr & s.t.{\alpha _j} - {z_j} = 0 \cr} $

(8)

其中：Y_j为训练样本类别标签向量，K_j为由本地训练样本通过核函数k(x_i·x_j)得到的增广核矩阵，α_j为要求解的系数向量. 利用交替方向乘子方法对式(8)进行推导求解，得到各变量的迭代形式，如式(9)～式(11)所示.

$\eqalign{ & \alpha _j^{k + 1} = {\left[ {\left( {{2 \over {{N_j}}} + 1} \right)K_j^T{K_j} + \rho I} \right]^{ - 1}} \cr & \left[ {K_j^T\left( {{2 \over {{N_j}}}{Y_j} + \bar f{{_{{B_j}}^*}^k}({x_j})} \right) + \rho (z_j^k + u_j^k)} \right] \cr} $

(9)

$z_j^{k + 1}: = {\Psi _{\lambda /\rho }}(\alpha _j^{k + 1} + u_j^k)$

(10)

$u_j^{k + 1}: = u_j^k + \alpha _j^{k + 1} - z_j^{k + 1}$

(11)

式(9)中：ρ为大于0的常数，u_j为对偶变量. 式(10)中的Ψ为软阈值操作符，其定义为

${\Psi _k}\left( a \right) = \left\{ {\matrix{ {a - k} & {a > k} \cr 0 & {\left| a \right| \le k} \cr {a + k} & {a < - k} \cr } } \right.$

(12)

各节点利用式(9)~式(11)可以求得系数向量α_j，进而求出本地最优稀疏模型，如式(13)所示，其中l为系数向量α_j中非零项的个数.

$f_j^{k + 1}\left( \cdot \right) = \sum\limits_{i = 1}^l {\alpha _i^{k + 1}k({x_i},\cdot),\forall j \in J} $

(13)

至此，各节点按照式(9)～式(11)、式(13)、式(6)的顺序迭代求解节点本地最优稀疏模型.

2.2 邻居节点间的协作

式(9)中，f_Bj^*(x_j)是节点j及其邻居节点模型对其本地训练样本预测得到的平均预测值.为了得到该平均预测值，节点j需要得到所有邻居节点的稀疏模型，即邻居节点间需要以传输稀疏模型的方式进行协作. 为充分发挥稀疏模型在节点模型求解过程中的作用，各节点接收到邻居节点发送过来的稀疏模型后，先将稀疏模型中的关键样本加入到本地训练样本集，然后利用接收到的模型对本地训练样本计算平均预测值. 为减少数据传输量，各节点对已经发送过的训练样本设置发送标志，限制其重复发送. 当各节点以此协作方式收敛到本地最优稀疏模型后，邻居节点间仍依靠传输稀疏模型的方式，利用平均一致性算法实现各节点模型的全局一致.

2.3 L1正则化KMSE学习机分布式训练算法

基于上述迭代形式和邻居节点间的协作方式，提出了L1-DKMSE-PP训练算法，其步骤如下.

算法：L1-DKMSE-PP

输入：初始化节点j∈J上的训练样本集S_j:={(x_jn,y_jn),n={1,2,…,N_j}}、核参数σ、正则系数λ、k=0、f_Bj^*k(x_jn)=y_jn；

输出：稀疏模型f^*(·)；

重复：

步骤1 k=k+1，节点j利用式(9)～式(11)、式(13)求出局部稀疏模型f_j^k(·)，并发送给邻居节点.

步骤2 节点j接收邻居节点的稀疏模型f_i^k(·),i∈B_j，并将其中的关键样本加入到本地训练样本集；然后利用接收到的所有模型对本地训练样本进行预测，利用式(6)求出f_Bj^*k(x_j).

步骤3 当k≥2时，节点j判断局部模型是否满足收敛条件，若不满足，重复步骤1～3；若满足，结束，转步骤4.

步骤4 利用平均一致性算法对节点收敛到的局部最优模型进行全局平均，得到最优模型f^*(·).

3 仿真实验与结果分析

为了验证算法L1-DKMSE-PP的有效性，以一个由30个节点构成的WSN为例，使用模拟数据集和(UCI,UC irvine machine learning repository)基准数据集进行实验，并与L1正则化KMSE学习机的集中式(L1-CKMSE,centralized KMSE based on L1 regularized)训练算法、SVM的集中式(CSVM,centralized support vector machine)训练算法、文献^[4]中的分布式训练算法(AP-DKMSE,distributed KMSE based on alternative projection)和文献^[6]中的分布式训练算法(DPSVM,distributed parallel support vector machine)从模型预测正确率、模型稀疏率和数据传输量3个方面进行对比.

3.1 实验设置

本实验中模拟数据集由两类非线性可分的数据组成，一类服从均值为mu₁=[0,0]^T、协方差矩阵为Σ=[0.6,0;0,0.4]^T的二维高斯分布，另一类服从混合参数分别为π₁=0.3和π₂=0.7、均值分别为mu₂=[－2,－2]^T和mu₃=[2,2]^T、协方差矩阵均为Σ的二维混合高斯分布；UCI基准数据集是wave-form和wave-form-noise. 3个数据集的基本信息如表 1所示.

实验中核函数选用高斯核函数k(x_i,x_j)=exp(－‖x_i－x_j‖²/2σ²)，*算法CSVM、L1-CKMSE、L1-DKMSE-PP、AP-DKMSE和DPSVM使用的核参数σ、正则系数λ以及惩罚因子C的参数值，使用搜索方法寻优得到. 各算法在3个数据集上使用的参数值如表 2所示. 基于上述实验设置，在每个数据集上进行30次独立实验.

3.2 实验结果分析

1) 模型预测正确率

如图 1所示，算法L1-DKMSE-PP在synthetic dataset、wave-form和wave-form-noise数据集上的模型预测正确率与集中式算法L1-CKMSE表现基本一致，与其他对比算法CSVM、AP-DKMSE和DPSVM相比也都没有明显差别.

2) 模型稀疏率

如图 2所示，在synthetic dataset、wave-form和wave-form-noise上，算法L1-DKMSE-PP在模型稀疏率上均明显高出了集中式算法L1-CKMSE，但都显著低于集中式算法CSVM、分布式算法AP-DKMSE和DPSVM. 这表明，算法L1-DKMSE-PP在3个数据集上的模型稀疏效果显著优于对比算法CSVM、AP-DKMSE和DPSVM，但也明显略劣于集中式算法L1-CKMSE.

3) 数据传输量

如图 3所示，在synthetic dataset上，算法L1-DKMSE-PP的数据传输量与集中式算法CSVM和L1-CKMSE相比，分别少37.94%和32.38%；与分布式算法AP-DKMSE相差更明显，少了69.41%，但与分布式算法DPSVM相比，多了12.57%. 在wave-form和wave-form-noise上，算法L1-DKMSE-PP的数据传输量均显著低于其他4个对比算法. 在synthetic dataset和UCI的2个基准数据集上，算法L1-DKMSE-PP和DPSVM在数据传输量上对比结论不一致，其原因是算法DPSVM在不同数据集上表现出极其不同的稀疏特性，在synthetic dataset上，算法DPSVM的模型稀疏程度很大，而在UCI的2个基准数据集上表现很差，所以，算法DPSVM的模型稀疏率和数据传输量受训练样本集影响很大. 而算法L1-DKMSE-PP在模型稀疏率和数据传输量上受不同数据集影响不明显，并且在3个数据集上的数据传输量均显著低于对比算法L1-CKMSE、CSVM和AP-DKMSE.

4 结束语

针对WSN中集中式训练核学习机时存在的数据传输代价大的问题，研究了仅依靠相邻节点间的协作在网内分布式协同训练方法，提出了仅依靠相邻节点间传输稀疏模型的协作方式，在网内分布式协同训练L1正则化KMSE学习机的算法L1-DKMSE-PP. 仿真实验结果表明，在模型预测正确率上，算法L1-DKMSE-PP取得了与集中式算法L1-CKMSE和其他对比算法相当的预测效果；在模型稀疏率上，算法L1-DKMSE-PP仅次于其对应的集中式算法L1-CKMSE，但明显优于实验中其他对比算法；在数据传输量上，算法L1-DKMSE-PP较实验中的对比算法L1-CKMSE、CSVM和AP-DKMSE都表现出绝对优势. 算法L1-DKMSE-PP因其在数据传输量上的显著优势，为WSN下进行核学习机的训练提供了一种可行的方法.