A Hierarchical Bio-inspired Neural Network Based Multi-robot Cooperative Area Search Algorithm
-
摘要: 针对多机器人系统在战场、灾难现场等复杂未知环境下的区域搜索问题, 提出一种基于分层仿生神经网络的多机器人协同区域搜索算法. 首先将仿生神经网络(Bio-inspired neural network, BNN) 和不同分辨率下的区域栅格地图结合, 构建分层仿生神经网络信息模型, 其中包括区域搜索神经网络信息模型(Area search neural network information model, AS-BNN)和区域覆盖神经网络信息模型(Area coverage neural network information model, AC-BNN). 机器人在任务区域内实时探测到的环境信息将转换为AS-BNN和AC-BNN中神经元的动态活性值. 其次, 在分层仿生神经网络信息模型基础上引入分布式模型预测控制(Distributed model predictive control, DMPC)框架, 并设计多机器人分层协同决策机制. 当机器人处于正常搜索状态时, 基于AS-BNN进行搜索路径滚动优化决策; 当机器人陷入局部最优状态时, 则启用AC-BNN引导机器人快速找到新的未搜索区域. 最后, 在复杂未知环境下进行多机器人区域搜索仿真实验, 并与该领域内的3种算法进行比较. 仿真结果验证了所提算法能够在复杂未知环境下引导多机器人系统高效地完成区域搜索任务.Abstract: Aiming at the problem of multi-robot system area search in complex and unknown environments, such as battlefields and disaster scenes, a multi-robot cooperative area search algorithm based on a hierarchical bio-inspired neural network is proposed. Firstly, a hierarchical bio-inspired neural network (BNN) information model is constructed by combining the bio-inspired neural network with area grid maps at different resolutions, including the area search neural network information model (AS-BNN) and the area coverage neural network information model (AC-BNN). The real-time environmental information detected by the robots in the task area is converted into the dynamic activity values of neurons in both AS-BNN and AC-BNN. Secondly, a distributed model predictive control (DMPC) framework is introduced based on the hierarchical bio-inspired neural network information model, and a multi-robot hierarchical cooperative decision-making mechanism is designed. When the robot is in a normal search state, a rolling optimization decision for the search path is made based on the AS-BNN. If the robot falls into a local optimum state, the AC-BNN is activated to guide it in quickly finding a new unsearched area. Finally, a multi-robot area search simulation experiment is conducted in a complex and unknown environment, comparing the proposed algorithm with three other algorithms in this field. The simulation results verify that the proposed algorithm can guide the multi-robot system to efficiently complete the area search task in complex and unknown environments.
-
如今利用现代设备采集高维数据变得方便和容易, 但是获得的高维数据可能包含不相关和冗余的信息. 这不仅增加了学习模型的计算量和存储量, 而且可能导致学习模型的性能下降. 为了解决这些问题, 线性降维[1-4]通常用于从数据中提取重要和有用的信息. 线性降维的目的是通过优化一些准则函数对原始特征空间进行适当的线性变换. 主成分分析(Principal component analysis, PCA)和线性判别分析(Linear discriminant analysis, LDA)是两种流行的线性降维方法. 由于PCA和LDA的简单性和有效性, 它们已经被广泛应用于许多领域, 如人脸识别[5]、手写体字符识别[6]和缺陷诊断[7]等.
当样本的类别信息可用时, 通常情况下LDA在提取数据的鉴别特征方面比PCA更有效. 线性判别分析的目标是在变换空间中通过最大化类间距离和最小化类内距离来寻找投影矩阵. 从概率的观点来看, 假设每类样本服从高斯分布且具有不同的类中心以及相同的协方差, 则从Bayes最优准则可推导出LDA.
为了改善线性判别分析的特征提取性能, 各种LDA的改进算法[8-10]已经被提出. 使用最优向量替换各类中心[8]能提高LDA的类信息鉴别能力. 分数阶的LDA[11]通过在一系列分数阶中引入加权函数来改善LDA, 但这增加了获得投影向量的代价. 与Bayes错误率相关的近似成对精度准则[12]在原空间计算各类的权重, 从而改善LDA的性能. 几何平均[13], 调和平均[14]以及加权调和平均[15]被用来定义判别分析的准则函数. 最不利情况下的线性判别分析[16]考虑了最近的两个类中心和具有最大方差的类来寻找投影方向. 基于最大−最小距离的目标函数[17]探索了最近的数据对的性质来取得投影方向. Wasserstein判别分析[18]利用正则化Wasserstein距离获取类之间的全局和局部信息并优化目标函数取得最佳投影方向.
线性判别分析存在小样本的奇异性[19]以及非线性数据特征提取[20-21]等问题. 为了克服LDA的小样本奇异性问题, 典型的方法包括PCA+LDA, 正则化LDA, 伪逆LDA 以及张量判别分析[22]等. 为了有效地处理非线性数据, 各种线性判别分析已被拓宽到基于核函数的判别分析[7, 20-21]. 当训练集随着新数据的加入而变化时或处理的数据量大时, 各种增量学习[23-24]或在线学习方式被用来获得鉴别分析的投影方向. 文献[24]提出了两种形式的增量LDA : 序列增量LDA和块增量LDA, 它们能有效地获取大数据流的特征空间.
数据在采集或传输过程中可能受到污染, 这使得处理的数据包含噪声或离群点. 但经典线性判别分析对噪声数据具有敏感性, 即获得的投影方向偏离真正的投影方向. 为了降低LDA对噪声数据的敏感性, 许多工作致力于用鲁棒的目标函数替换LDA的原有目标函数[25-26]. 已有的诸多研究发现, 基于L1范数的目标函数比基于L2范数的目标函数在抑制异常点或噪声方面更有效[27-29]. 因此基于L1范数的判别分析方法近年来备受关注. L1范数的LDA[28]的类内距离和类间距离的定义依赖于L1范数, 这在某种程度上能抑制噪声. L1范数的核LDA不仅能抑制噪声, 而且能捕捉数据的非线性鉴别特征[28]. L1范数的两维LDA[30]拓宽了L1范数的LDA, 这种方法可直接处理图像数据, 而不需要把图像转化为向量形式. 通常L1范数的判别分析通过贪婪算法获取多个投影方向, 而非贪婪迭代算法[31]被用来直接获取L1范数的LDA的多个投影向量. 广义弹性网[32]通过Lp范数定义的目标函数来改善判别分析抑制噪声的能力, 而通过优化Bhattacharyya的L1范数误差界[33]可设计出新的鉴别分析模型. 最近提出的基于L21范数的LDA方法[34]通过同时优化类中心和投影方向从而在噪声数据方面表现出良好的性能.
在大多数判别分析中, 通常假定类内各个样本以相等的概率(均匀分布)取得的, 但是位于类中心附近的样本一般远远多于位于类边界附近的样本. 为了增加类内样本采样的多样性, 可令类内样本的采样概率在均匀分布的概率附近变化, 这种变化有利于区分类中心附近的样本或类边界附近的样本. 不确定优化中的不确定集能描述概率分布的变化范围. 因此本文借助KL散度定义的不确定集对类内样本信息进行概率建模. 此外, 为了更好描述各类中心的信息, 本文也利用KL散度定义的不确定集对其进行概率建模. 基于此, 本文提出了基于KL散度不确定集的线性判别分析方法, 从而进一步改善已有线性判别分析方法. 与以往的方法不同, 本文不仅考虑了一般范数的目标函数, 而且利用不确定集对训练样本信息进行了刻画. 本文采用的不确定集为围绕均匀分布的KL散度球且约束中的不确定集被转化为目标函数的正则化项. 本文的主要贡献表现为:
1) 提出了正则化对抗LDA和正则化乐观LDA. 正则化对抗LDA优先考虑了难以区分的样本, 而正则化乐观LDA优化考虑了易于区分的样本.
2) 采用了广义Dinkelbach算法求解正则化对抗LDA或正则化乐观LDA. 对正则化对抗LDA运用投影梯度法求解优化子问题, 而对正则化乐观LDA运用交替优化求解优化子问题.
3) 在数据集上表明了当数据没有被污染时, 两种判别分析模型取得可竞争的性能, 但在污染数据的情况下, 正则化乐观LDA取得更好的性能. 这也从另一方面说明了本文提供两种模型的目的, 即如果在某些验证数据集上正则化乐观LDA的最好性能明显优于正则化对抗LDA的最好性能, 那说明训练集包含离群点. 因此通过检查正则化对抗LDA和正则化乐观LDA的性能可判断训练集是否包含离群点.
1. 相关工作
假设维数为
$ d $ 的$ n $ 个数据点表示为$\{{\boldsymbol{x}}_1 ,\cdots, $ $ {\boldsymbol{x}}_n \}$ , 其中$ {\boldsymbol{x}}_i\in {\bf{R}}^d $ $ (i = 1,\cdots,n) $ . 数据集中每个数据点属于$ c $ 类中的一类, 第$ i $ 类的样本数为$ n_i $ , 这样$ n = \sum\nolimits_{i = 1}^c {n_i} $ 为总的样本数. 定义向量${\boldsymbol{a}} = (a_1,\cdots, $ $ a_n )^{\rm{T}}$ 的Ls范数为$\| {\boldsymbol{a}} \|_s = ( {\sum\nolimits_{i = 1}^n {| {a_i } |^s} } )^{\frac{1}{s}}$ , 其中$ s>0 $ . 当$ 0<s<1 $ 时,$ \| {\boldsymbol{a}} \|_s $ 并不是严格意义上的范数.线性判别分析的类间离差矩阵和类内离差矩阵分别被定义为:
$$ {\boldsymbol{S_b}} = \sum\limits_{i = 1}^c {\frac{n_i }{n}} ({\boldsymbol{m}}_i -\bar {{\boldsymbol{m}}})({\boldsymbol{m}}_i -\bar {{\boldsymbol{m}}})^{\rm{T}} $$ (1) $$ {\boldsymbol{S_w}} = \frac{1}{n}\sum\limits_{i = 1}^c {\sum\limits_{k = 1}^{n_i } {({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} } ({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )^{\rm{T}} $$ (2) 其中
$ \bar{{\boldsymbol{m}}} = \frac{1}{n}\sum\nolimits_{i = 1}^n {{\boldsymbol{x}}_i } $ 表示所有样本的均值,${\boldsymbol{m}}_i = $ $ \frac{1}{n_i}\sum\nolimits_{k = 1}^{n_i } {{\boldsymbol{x}}_k^i }$ 是第$ i $ 类样本的均值,$ {\boldsymbol{x}}_k^i $ 表示第$ i $ 类的第$ k $ 个样本. 线性判别分析在矩阵对$ ({\boldsymbol{S_b}}, {\boldsymbol{S_w}} ) $ 上执行广义特征值分解取得多个投影方向.1.1 最不利情况的线性判别分析
在文献[16]中, 类间离差矩阵(1)被改写成下面形式:
$$ {\boldsymbol{S_b}} = \sum\limits_{i = 1}^c \sum\limits_{j = i+1}^c \omega _{ij} ({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )^{\rm{T}} $$ (3) 其中
$ \omega _{ij} = \omega _i\omega _j $ ,$ i,j = 1,\cdots,c $ 以及$\omega _i = \dfrac{n_i}{n}$ 表示第$ i $ 类样本的先验概率. 在此基础上, 文献[16]定义了如下的线性判别分析:$$ \begin{split} &\max\limits_{{\boldsymbol{W}}} \frac{\min _{ij} \{\omega _{ij} \|{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )\|_2^2 \}}{\max _i \displaystyle\left\{\frac{1}{n_i }\sum\limits_{k = 1}^{n_i } {\|{\boldsymbol{W}}^{\rm{T}}} ({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )\|_2^2 \right\}}\\ &{\rm{s.t.}} \ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (4) 其中
$ {\boldsymbol{W}} $ 是一个$ d\times m $ 投影矩阵以及${\boldsymbol{I}}_m$ 表示单位矩阵. 在投影空间中, 模型(4)通过优化距离最近的两个类中心和具有最大类内距离的类取得最优投影矩阵. 这种方法实际上寻找不利区分样本的最优投影方向. 这种设计思想来源于分类器的设计. 在分类器设计中, 设计的分类器对难以分类的样本(边界样本)进行优先考虑, 即赋予较大的采样概率, 从而使设计的分类器具有更好的泛化性能. 模型(4)通过优先考虑难以区分的样本取得最优投影矩阵. Zhang和Yeung[16]提出了两种算法求解模型(4). 一种方法是将(4)转化为度量学习问题, 另一种方法是设计了一种基于约束的凹凸优化算法.1.2 基于L1范数的线性判别分析
在文献[28]中,下面优化模型被用来取得投影矩阵
$ {\boldsymbol{W}} $ :$$ \begin{split} &\max\limits_{{\boldsymbol{W}}} \frac{\displaystyle\sum\limits_{i = 1}^c {n_i } \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -\bar {{\boldsymbol{m}}})} \|_1 }{\displaystyle\sum\limits_{i = 1}^c {\sum\limits_{{\boldsymbol{x}}_j \in l_i } {\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_j -{\boldsymbol{m}}_i )} \|_1 } } }\\ &{\rm{s.t}}.\ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (5) 其中
$\|\cdot\|_1$ 表示向量的L1范数,$ l_i $ 表示第$ i $ 类样本的集合. 优化问题(5)的目标函数关于变量$ {\boldsymbol{W}} $ 是非平滑和非凸的. 文献[28]首先利用梯度上升法取得一个投影向量, 然后设计了一个贪婪方法来取得多个投影向量.1.3 基于L21范数的线性判别分析
为了改善线性判别分析模型在投影空间的鉴别能力, 文献[34]提出了下面的优化模型:
$$ \begin{split} &\min\limits_{{\boldsymbol{W}},{\boldsymbol{m}}_i } \frac{\sum\limits_{i = 1}^c {\displaystyle\sum\limits_{{\boldsymbol{x}}_j \in l_i } {\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_j -{\boldsymbol{m}}_i )} \|_2 } } }{\displaystyle\frac{1}{n}\sum\limits_{i = 1}^n {\| {{\boldsymbol{W}}^{\rm{T}}{\boldsymbol{x}}_i } \|_2 } }\\ &{\rm{s.t}}. \ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (6) 与以前的一些模型不同, 式(6)的类平均
${{{\boldsymbol m}_i}}\;(i = $ $ 1,\cdots,c)$ 是优化变量. 模型(6)的目标函数实际上对不同样本采用了L1范数, 而对每个样本的约简特征采用了L2范数, 这通常被称为L21范数的线性判别分析. 如果数据包含离群点, 基于算术平均取得的类中心可能偏离样本的真正类中心, 而优化的类中心接近真正的类中心. 模型(6)比模型(5)包含更多的优化变量. 文献[34]设计了一个有效的框架求解模型(6).2. 基于不确定集的正则化线性判别分析
2.1 正则化对抗LDA
为了度量两个具有公共支集的离散概率分布之间的差异, 文献[35]定义了KL散度. 假设给定两个离散概率分布
$ {\boldsymbol{p}} = (p_1,\cdots, p_n) $ 和$ {\boldsymbol{q}} = (q_1,\cdots, q_n) $ , 那么这两个概率分布之间的KL散度被定义为:$$ KL({\boldsymbol{p}}\vert {\boldsymbol{q}}) = \sum\limits_{i = 1}^n {p_i } \ln \frac{p_i }{q_i } $$ (7) 如果两个离散概率分布相同, 则KL散度的值为零. 由于KL散度不满足三角不等式, 它实际上不是一个真正的距离度量. 注意到KL散度是非对称的, 即
$ KL({\boldsymbol{p}}\vert {\boldsymbol{q}})\ne KL({\boldsymbol{q}}\vert {\boldsymbol{p}}) $ . KL散度是非负的, 即$ KL({\boldsymbol{p}}\vert {\boldsymbol{q}})\ge 0 $ . 在鲁棒优化中, 基于KL散度的不确定集被定义为[36-37]:$$ { K} = \{{\boldsymbol{p}}| {KL({\boldsymbol{p}}\vert {\boldsymbol{q}})} \le \varepsilon \} $$ (8) 式(8)的不确定集表明, 离散概率分布
$ {\boldsymbol{p}} $ 在给定的离散概率分布$ {\boldsymbol{q}} $ 附近变化, 其变化范围由一个非负参数$ \varepsilon $ 控制. 参数$ \varepsilon $ 越大, 不确定集的变化范围越大. 单个$ {\boldsymbol{p}} $ 是不确定集内的一个具体的概率分布.为了探索样本的类间信息, 模型(4)试图在低维投影空间中最大化最近的两个类中心, 而且它利用L2范数定义了类间距离. 在Ls范数的距离测度下, 与式(4)相似的类间信息的优化问题
$\max _{{\boldsymbol{W}}} \min _{i < j} \omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s$ 在${\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m$ 约束条件下被写成下面形式:$$ \begin{split} &\max\limits_{{\boldsymbol{W}}} \min\limits_{p_{ij} } \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} } } \omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s\\ &{\rm{s.t}}. \ \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} }, p_{ij} \ge 0, {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (9) 模型(9)不仅引入了优化变量
$ p_{ij} $ , 而且在投影后的类间距离使用了Ls范数. 如果$ s = 1 $ , 那么使用了L1范数定义了类间距离. 如果$ s = 2 $ , 那么使用了L2范数定义了类间距离. 模型(9)说明了优化变量$ p_{ij} $ 在概率单纯形内变化, 即在这个单纯形中寻找距离最近的类中心对, 并试图取得最优投影矩阵. 因此在提取鉴别特征时, 距离最近的两个类中心所起的作用最大. 显然, 它忽略了其他类中心的信息, 使得这种模型利用类中心的信息不完整. 为了解决这个问题, 本文首先将离散概率分布$ p_{ij} $ 看作类中心$ {\boldsymbol{m}}_i $ 和$ {\boldsymbol{m}}_j $ 之间的采样概率, 然后将离散概率分布$ p_{ij} $ 限制在一定的范围内, 使得模型变得更加灵活. 这里使用式(8)定义的不确定集, 这个不确定集是由离散概率分布定义的. 因此根据KL散度定义的不确定集和各类中心信息, 以下优化问题被提出:$$ \begin{split} &\max\limits_{{\boldsymbol{W}}} \min\limits_{p_{ij} } \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} } } \omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s\\ &{\rm{s.t}}.\ \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} },p_{ij} \ge 0\\ &\sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c} {p_{ij} } \ln \frac{p_{ij} }{q_{ij} }\le \varepsilon, {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (10) 模型(10)引入了满足条件
$ \sum\nolimits_{i<j}^c {q_{ij} } = 1 $ 的参数$ q_{ij} $ , 该参数$ q_{ij} $ 表示第$ i $ 类中心和第$ j $ 类中心所提供的先验知识. 如果事先没有提供先验知识, 可令$q_{ij} = \dfrac{2}{c(c-1)}$ , 即它服从均匀概率分布, 这是因为不同类中心构成的数据对的数目为$\dfrac{ c(c-1)}{2}$ . 参数$ q_{ij} $ 并不是优化变量. 模型(10)允许参数$ p_{ij} $ 在给定$ q_{ij} $ 的邻域内变化. 根据正则化理论, 通过引入一个非负参数$ \eta $ 可将(10)的不确定集转化为目标函数的正则化项. 因此模型(10)等价于下面的模型:$$ \begin{split} &\max\limits_{{\boldsymbol{W}}} \min\limits_{p_{ij} } F_1 (W,p_{ij} ): = \eta KL({\boldsymbol{p}}|{\boldsymbol{q}})+\\ &\qquad\sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} } } \omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )}\|_s^s\\ &{\rm{s.t}}. \ \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} },p_{ij} \ge 0,{\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (11) 在模型(11)中, KL散度作为正则化项使用了非负参数
$ \eta $ . 参数$ \eta $ 越大, 对应的不确定集越小. 参数$ \eta $ 越小, 对应的不确定集就越大. KL散度是非负的, 因此$ F_1 ({\boldsymbol{W}},p_{ij} ) $ 是非负的. 模型(11)仅仅考虑了类间样本的分布信息. 对于类内样本的分布信息, 遵循同样的思想, 这里考虑类边界附近的样本, 在投影矩阵的半正交约束下,$\min _{\boldsymbol{W}} \sum\nolimits_{i = 1}^c {\max _j } \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_j^i -{\boldsymbol{m}}_i )} \|_r^r$ 被改写成下面的形式:$$ \begin{split} &\min\limits_{{\boldsymbol{W}}} \max\limits_{u_{ik} } \sum\limits_{i = 1}^c {\sum\limits_{k = 1}^{n_i } {u_{ik} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )}\|_r^r } }\\ &{\rm{s.t}}. \ \sum\limits_{k = 1}^{n_i } {u_{ik} = 1} , u_{ik} \ge 0, {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (12) 模型(12)采用了Lr范数定义类内距离, 参数
$ r $ 是正的实数. 模型(4)中分式的分母考虑了低维空间中具有最大类内距离的类, 而模型(12)考虑了每一类中远离其类中心的那些样本, 那些样本可能位于类之间的交界处. 换言之, 它搜索一些样本, 使它们在类内信息中起主导作用. 这样$ u_{ik} $ 可看成第$ i $ 类的第$ k $ 个样本的采样概率. 通过将$ u_{ik} $ 限制在一个不确定集内, 使样本的采样概率发生变化. 根据(12)和不确定集可定义如下的优化问题:$$ \begin{split} &\min\limits_{{\boldsymbol{W}}} \max\limits_{u_{ik} } F_2 ({\boldsymbol{W}},u_{ik} ): = \\ &\qquad\sum\limits_{i = 1}^c{\sum\limits_{k = 1}^{n_i } {u_{ik} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} \|_r^r } } -\\ &\qquad\sum\limits_{i = 1}^c {\sum\limits_{k = 1}^{n_i } {\lambda _i } u_{ik} } \ln \frac{u_{ik} }{v_{ik} }\\ &{\rm{s.t}}.\ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m,\sum\limits_{k = 1}^{n_i } {u_{ik} = 1}, u_{ik} \ge 0 \end{split} $$ (13) 模型(13)为每类引入了非负参数
$\lambda _i\;(i = 1,\cdots, $ $ c)$ , 这些非负参数在类内信息和不确定集之间作出适当的折衷. 参数$ v_{ik} $ 表示不确定集的中心, 并满足$ \sum\nolimits_{k = 1}^{n_i } {v_{ik} = 1} $ ,$ v_{ik} \ge 0 $ . 通常每类的$ v_{ik} $ 为均匀分布, 即$v_{ik} = \dfrac{1}{n_i}, k = 1,\cdots, n_i$ . 模型(11)通过对各类中心进行概率建模探索了类间信息, 而模型(13)通过对类内样本的采样概率进行建模探索了类内信息. 为了同时利用类内信息和类间信息, 从式(11)和(13)可建立如下单目标优化模型:$$ \begin{split} &\min\limits_{{\boldsymbol{W}}} \frac{\max _{u_{ik} } F_2 ({\boldsymbol{W}},u_{ik} )}{\min _{p_{ij} } F_1 ({\boldsymbol{W}},p_{ij} )}\\ &{\rm{s.t.}} \ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m , \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} }\\ &p_{ij} \ge 0, u_{ik} \ge 0, \sum\limits_{k = 1}^{n_i } {u_{ik} = 1} \end{split} $$ (14) 式(14)的内层优化是关于变量
$ u_{ik} $ 和$ p_{ij} $ 的优化问题以及外层优化是关于变量$ {\boldsymbol{W}} $ 的优化问题. 模型的内层优化优先考虑了可分离性不好的样本(边界附近的样本有大的采样概率), 而外层优化使得它们在投影空间的可分离性变好. 从(12), (13)以及(14)知, 内层优化和外层优化的目标具有不一致(对抗)的性质. 本文将模型(14)称为正则化对抗LDA(Regularized adversarial LDA, RALDA). 式(14)的内层优化取得的概率分布被称为不确定集的对抗概率分布. 模型(14)是一个非凸优化问题. 模型(14)包含三组优化变量, 即$ {\boldsymbol{W}} $ ,$ u_{ik} $ 和$ p_{ij} $ . 如果同时考虑这三组优化变量, 这实际上是一个鞍点优化问题. 如果令$ u_{ik}^\ast({\boldsymbol{W}}) = \arg \max _{u_{ik} } F_2 ({\boldsymbol{W}},u_{ik} ) $ , 那么从$ u_{ik}^\ast(W) $ 可得到关于$ {\boldsymbol{W}} $ 的梯度信息[38], 这是因为$ F_2 ({\boldsymbol{W}},u_{ik}) $ 是变量$ u_{ik} $ 的严格凸函数. 同样地令$ p_{ij}^\ast (W) = \arg \max _{p_{ij} }F_1({\boldsymbol{W}},p_{ij} ) $ , 从$ p_{ij}^\ast ({\boldsymbol{W}}) $ 可得到关于$ {\boldsymbol{W}} $ 的梯度信息. 换句话说, 此情况下可计算$ u_{ik}^\ast ({\boldsymbol{W}}) $ 和$ p_{ij}^\ast(W) $ 关于$ {\boldsymbol{W}} $ 的(次)梯度. 注意非可微函数采用了次梯度. 通过下面两个优化问题可取得$ u_{ik}^\ast ({\boldsymbol{W}}) $ 和$ p_{ij}^\ast({\boldsymbol{W}}) $ :$$ \begin{split} &\max\limits_{u_{ik} } F_2 ({\boldsymbol{W}},u_{ik} )\\ &{\rm{s.t}}.\ \sum\limits_{k = 1}^{n_i } {u_{ik} = 1} , u_{ik} \ge 0 \end{split}$$ (15) $$ \begin{split} &\min\limits_{p_{ij} } F_1 ({\boldsymbol{W}},p_{ij} )\\ &{\rm{s.t}}.\ \sum\limits_{i<j}^c {p_{ij} = 1}, p_{ij} \ge 0 \end{split}$$ (16) 优化问题(15)对应模型(14)中分式的分子, 优化问题(16)对应模型(14)中分式的分母. 注意到函数
$ F_1({\boldsymbol{W}},p_{ij} ) $ 是变量$ p_{ij} $ 的强凸函数以及$ F_2 ({\boldsymbol{W}},u_{ik} ) $ 是变量$ u_{ik} $ 的强凹函数, 这说明优化问题(15)和(16)分别存在唯一解. 式(15)和(16)的唯一解分别表示为:$$ u_{ik}^\ast = \frac{v_{ik} \exp (\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} \|_r^r /\lambda _i )}{\sum\limits_{k = 1}^{n_i } {v_{ik} \exp (\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} \|_r^r /\lambda _i } )} $$ (17) $$ p_{ij}^\ast = \frac{q_{ij} \exp (-\omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s /\eta )}{\sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {q_{ij} } \exp (-\omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s /\eta } )} $$ (18) 把式(17)代入
$ \max _{u_{ik} } F_2 ({\boldsymbol{W}},u_{ik} ) $ 可取得:$$ \begin{split} &\tilde {F}_2 ({\boldsymbol{W}}) = \max\limits_{u_{ik} } F_2 ({\boldsymbol{W}},u_{ik} ) = \\ &\qquad\sum\limits_{i = 1}^c {\lambda _i } \ln \sum\limits_{k = 1}^{n_i } {v_{ik} \exp (\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} \|_r^r /\lambda _i } ) \end{split} $$ (19) 把式(18)代入
$ \min _{p_{ij} } F_1 ({\boldsymbol{W}},p_{ij} ) $ 可取得:$$ \begin{split} &\tilde {F}_1 ({\boldsymbol{W}}) = \min\limits_{p_{ij} } F_1 ({\boldsymbol{W}},p_{ij} ) = \\ &\quad-\eta \ln \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {q_{ij} } \exp (-\omega _{ij}\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s /\eta } ) \end{split} $$ (20) 式(19)和(20)实际上求解模型(14)的内层优化问题. 利用式(19)和(20), 优化模型(14)被改写成下面形式:
$$ \begin{split} &\min\limits_W F({\boldsymbol{W}}): = \frac{\tilde {F}_2 ({\boldsymbol{W}})}{\tilde {F}_1 ({\boldsymbol{W}})}\\ &{\rm{s.t}}. \ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split}$$ (21) 模型(21)仅包含优化变量
$ {\boldsymbol{W}} $ . 它是一个非常复杂的非线性优化问题. 从模型(21)的约束来看, 它属于Stiefel流形上的优化问题[41].2.2 求解优化模型(21)
式(21)是一个比率优化问题. 从
$ F_1({\boldsymbol{W}},p_{ij}) $ 的非负性和式(20)可得出$ \tilde {F}_1 ({\boldsymbol{W}}) $ 是非负的. 从(19)可推导出$ \tilde {F}_2 ({\boldsymbol{W}}) $ 是非负的. 这样式(21)中的函数$ F({\boldsymbol{W}}) $ 是非负的. 尽管存在求解模型(21)的诸多优化算法, 但本文采用了广义Dinkelbach算法[39]求解模型(21). 算法1描述了求解式(21)的主要步骤.算法1. 求解模型(21)的广义Dinkelbach算法
1) 令
$ {\boldsymbol{W}}^1 $ 是满足$({\boldsymbol{W}}^1)^{\rm{T}} {\boldsymbol{W}}^1 = {\boldsymbol{I}}_m$ 的初始可行解, 设定参数$ \lambda _i $ ,$ \eta $ ,$ q_{ij} = 2/(c(c-1)), u_{ik} = 1/n_i $ ,$ \gamma _1 = F({\boldsymbol{W}}^1) $ ,2) 对于
$ t = 1 $ to$ T $ 执行a) 求解
$\bar {F}(\gamma _t ) = \min _{{\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m\\ } \{\tilde {F}_2 ({\boldsymbol{W}})-\gamma _t \tilde {F}_1 ({\boldsymbol{W}})\}$ , 其解表示为$ {\boldsymbol{W}}^{t+1} $ ,b) 如果
$ \bar {F}(\gamma _t ) = 0 $ , 停止且$ {\boldsymbol{W}}^{t+1} $ 是最优解, 否则取得$ \gamma _{t+1} = F({\boldsymbol{W}}^{t+1}) $ ,3) 输出投影矩阵
$ {\boldsymbol{W}} $ .算法1把比率优化问题(21)归结为两个函数差的优化问题. 文献[27]已采用这种思想求解L1范数的LDA, 从而避免矩阵逆的计算, 这也克服小样本的奇异性问题. 文献[27]的方法实际上是广义Dinkelbach算法的一种形式. 这样本文的算法也不会出现矩阵逆计算问题. 如果KL散度的值不为0,
$ F_1 ({\boldsymbol{W}},p_{ij} ) $ 作为式(14)的分母也不为零. 这些因素促使了提出的算法克服了小样本的奇异性问题.算法1的停止条件是
$ \bar {F}(\gamma _t ) = 0 $ . 在实际应用中, 由于受浮点数计算精度的影响, 这通常是不可行的. 通常采用最大迭代次数或目标函数的相对变化小于一个数作为停止条件. 如文献[39]所述, 如果约束集是闭有界集且优化子问题取得精确解, 则算法1将在有限次迭代中结束, 或者它将产生一个无穷序列, 其极限点是式(21)的平稳点. 注意到投影矩阵$ W $ 位于一个闭有界集中, 并且模型(21)的目标函数是连续的. 因此式(21)的目标函数是有上下界的. 在实际求解中可能无法取得优化子问题的精确解. 如果采用闭映射的下降算法求解优化子问题, 那么算法1在这种情况下也收敛[39]. 因此本文利用梯度下降算法解决优化子问题以确保算法1的收敛性. 从算法1可看出, 其关键问题是如何求解优化子问题. 算法1中的子问题被表示如下:$$ \begin{array}{l}\bar {F}(\gamma _t ) = \min\limits_{{\boldsymbol{W}}^{\rm{T}} {\boldsymbol{W}} = {{{\boldsymbol I}_m}}} \{\tilde {F}_2 ({\boldsymbol{W}})-\gamma _t \tilde {F}_1 ({\boldsymbol{W}})\} \end{array} $$ (22) 从
$ F({\boldsymbol{W}}^1) $ 的非负性可知$ \gamma _t $ 是非负的. 如文献[39]所述, 函数$ \bar {F}(\gamma _t ) $ 是变量$ \gamma _t $ 的凹函数和递减函数, 并且$ \bar {F}(\gamma _t ) = 0 $ 有唯一解. 算法1的优点在于不需要取得优化子问题的精确解, 只要$ {\boldsymbol{W}} $ 满足$\{\tilde {F}_2 ({\boldsymbol{W}})- $ $ \gamma_t\tilde {F}_1({\boldsymbol{W}})\} < 0$ , 那么$ {\boldsymbol{W}} $ 比前一次的解更接近目标函数$ F({\boldsymbol{W}}) $ 的最优解. 这样可采用简单的梯度投影法求解优化问题(22). 本文采用了基于Armijo线搜索的投影次梯度法求解模型(22). 为了方便描述算法, 这里定义了梯度$\dfrac{\partial \tilde {F}({\boldsymbol{W}})}{\partial {\boldsymbol{W}}} = \dfrac{\partial \tilde {F}_2 ({\boldsymbol{W}})-\lambda _t \tilde {F}_1 ({\boldsymbol{W}})}{\partial {\boldsymbol{W}}}$ . 算法2描述了求解模型(22)的主要步骤.算法2. 求解模型(22)的投影次梯度法
1) 初始的
$ W $ , Armijo参数$ 0<\beta <1 $ ,2) 重复直到收敛
a) 计算(次)梯度
$\dfrac{\partial \tilde {F}({\boldsymbol{W}})}{\partial {\boldsymbol{W}}}$ 和$ g = 1 $ ,b) 计算
${{{\boldsymbol W}_{n}}} = P({\boldsymbol{W}}-\beta ^g\dfrac{\partial \tilde {F}({\boldsymbol{W}})}{\partial {\boldsymbol{W}}})$ ,c) 计算
$\tilde {F}({{{\boldsymbol W}_{n}}} )$ ; 如果$\tilde {F}({{{\boldsymbol W}_{n}}} ) < \tilde {F}({\boldsymbol{W}})$ , 那么${\boldsymbol{W}} = {{{\boldsymbol W}_{n}}}$ ; 否则$ g = g+1 $ , 转到b).算法2定义了保证投影矩阵半正交性的投影算子
$P({\boldsymbol{W}}) = {\boldsymbol{W}}({\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}})^{-\frac{1}{2}}$ , 即$(P({\boldsymbol{W}}))^{\rm{T}} P({\boldsymbol{W}}) = {{{\boldsymbol I}_m}}$ . 从算法1可知, 算法1涉及函数$ F({\boldsymbol{W}}) $ 的计算和算法2的运行. 计算$ F({\boldsymbol{W}}) $ 的复杂度为${\rm{O}}(c^2dm+ndm)$ 以及算法2的复杂度在于梯度的计算. 梯度计算的复杂度为${\rm{ O}}(c^2dm+ndm)$ . 这样算法1的计算复杂度为${\rm{O}}(T_1 ((c^2dm+ndm)+T_2 (c^2dm+ndm)))$ , 其中$ T_2 $ 为算法2的迭代次数以及$ T_1 $ 为算法1的迭代次数.2.3 正则化乐观判别分析
正则化对抗判别分析探索了不确定集中的对抗概率分布, 这实际上优化考虑了训练集中位于类边界附近的样本(远离类中心的样本). 然而当数据集包含离群点时, 这些离群点可能远离各类中心. 在这种情况下, 优先考虑类中心附近的样本是有益的, 即对接近类中心附近的样本分配大的采样概率. 不同于第2.1节中的模型, 本小节试图在不确定集中寻找另外一种概率分布, 这对应于优先考虑类中心附近的样本点. 因此借助不确定集以及类内和类间信息可定义以下优化问题:
$$ \begin{split} &\max\limits_{{\boldsymbol{W}}} \max\limits_{p_{ij} } H_1 ({\boldsymbol{W}},p_{ij} ): = -\eta KL({\boldsymbol{p}}| {\boldsymbol{q}})+\\ &\qquad\sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} } } \omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s \\ &{\rm{s. t.}} \ \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} } , p_{ij} \ge 0, {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (23) $$ \begin{split} &\min\limits_{{\boldsymbol{W}}, u_{ik}} H_2 ({\boldsymbol{W}},u_{ik} ): = \sum\limits_{i = 1}^c {\sum\limits_{k = 1}^{n_i } {\lambda _i } u_{ik} } \ln \frac{u_{ik} }{v_{ik} }+\\ &\qquad\sum\limits_{i = 1}^c {\sum\limits_{k = 1}^{n_i } {u_{ik} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} \|_r^r }} \\ &{\rm{s.t}}. \ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m , \sum\limits_{k = 1}^{n_i } {u_{ik} = 1}, u_{ik} \ge 0 \end{split} $$ (24) 模型(23)优先考虑了距离大的类中心对, 这实际上优先考虑区分性比较好的类. 因为
$ KL(p|q) $ 取非负值, 这不能从$ H_1({\boldsymbol{W}},p_{ij} ) $ 的定义得出其非负性. 对于模型(24), 它优先考虑区分性比较好的样本, 即对类中心附近的样本赋予大的采样概率和类边界附近的样本赋予小的采样概率. 当处理的数据包含异常点或噪声时, 它优先考虑了那些可能不是异常点的样本, 即对异常点赋予小的采样概率. 因为KL散度是非负的, 从式(24)知,$ H_2 ({\boldsymbol{W}},u_{ik} ) $ 不小于零. 根据(23)和(24)可建立以下单目标函数:$$ \begin{split} &\min\limits_{{\boldsymbol{W}}} H({\boldsymbol{W}}): = \frac{\min _{u_{ik} } H_2 ({\boldsymbol{W}},u_{ik} )}{\max _{p_{ij} } H_1 ({\boldsymbol{W}},p_{ij} )}\\ &{\rm{s.t}}. \ {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m, \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} } \\ &p_{ij} \ge 0, u_{ik} \ge 0, \sum\limits_{k = 1}^{n_i } {u_{ik} = 1} \end{split} $$ (25) 从(23), (24)和(25)知, 外层优化(优化
$ {\boldsymbol{W}} $ )和内层优化(优化$ u_{ik},p_{ij}) $ 的目标有一致的性质. 根据不确定规划中的乐观模型的概念, 本文将模型(25)称为正则化乐观LDA(Regularized optimistic LDA, ROLDA). 内层优化取得的概率分布被称为不确定集的乐观概率分布. 模型(25)利用不确定集优先考虑类中心附近的样本点. 对训练集而言, 模型(25)优先考虑了区分性好的类和样本. 如果数据集包含异常点或噪声, 那么这些异常点或噪声可能远离类中心且具有较低的采样概率. 因此模型(25)在某种程度上能抑制异常点或噪声. 模型(25)是非凸优化问题, 同样地也采用了广义Dinkelbach算法求解模型(25). 求解式(25)涉及下面优化子问题:$$ \begin{split} &\bar {H}(\gamma _t ) = \min\limits_{{\boldsymbol{W}}} \{\min\limits_{u_{ik} } H_2 ({\boldsymbol{W}},u_{ik} )-\\ &\qquad\gamma _t \max\limits_{p_{ij} } H_1 ({\boldsymbol{W}},p_{ij} )\}\\ &{\rm{s.t}}.\ \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} } ,\sum\limits_{k = 1}^{n_i } {u_{ik} = 1}\\ &p_{ij} \ge 0, u_{ik} \ge 0, {\boldsymbol{W}}^{\rm{T}} {\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (26) 其中
$ \gamma_t $ 是来源于$ H({\boldsymbol{W}}) $ 的值. 函数$ H_1({\boldsymbol{W}},p_{ij}) $ 关于变量$ p_{ij} $ 是强凹函数, 函数$ H_2({\boldsymbol{W}},u_{ik}) $ 关于变量$ u_{ik} $ 是强凸函数. 这样$ p_{ij} $ 和$ u_{ik} $ 存在唯一解, 分别表示为:$$ p_{ij} = \frac{q_{ij} \exp (\omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s /\eta )}{\sum\limits_{i<j} {q_{ij} \exp (\omega _{ij} \| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{m}}_i -{\boldsymbol{m}}_j )} \|_s^s /\eta } )} $$ (27) $$ u_{ik} = \frac{v_{ik} \exp (-\left\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} \right\|_r^r /\lambda _i )}{\sum\limits_{k = 1}^{n_i } {v_{ik} \exp (-\| {{\boldsymbol{W}}^{\rm{T}}({\boldsymbol{x}}_k^i -{\boldsymbol{m}}_i )} \|_r^r /\lambda _i } )} $$ (28) 因为简化
$ H_1({\boldsymbol{W}},p_{ij} ) $ 和$ H_2({\boldsymbol{W}},u_{ik} ) $ 会导致模型是复杂的非线性问题, 所以没有借助式(27)和(28)简化$ H_1({\boldsymbol{W}},p_{ij} ) $ 和$ H_2({\boldsymbol{W}},u_{ik}) $ . 注意到如果把式(27)代入$ H_1 ({\boldsymbol{W}},p_{ij} ) $ , 那么可得出$ \max _{p_{ij} } H_1 ({\boldsymbol{W}},p_{ij} ) $ 是非负的. 如果把式(28)代入$ H_2 ({\boldsymbol{W}},u_{ik}) $ , 那么可得出$ min _{u_{ik} }H_2({\boldsymbol{W}},u_{ik}) $ 是非负的. 因此$ \gamma_t $ 是非负的. 考虑到$ \gamma _t $ 的非负性, 模型(26)可转化为下面的优化问题:$$ \begin{split} &\min\limits_{{\boldsymbol{W}}} \min\limits_{u_{ik}, p_{ij} } \{H_2 ({\boldsymbol{W}},u_{ik} )-\gamma _t H_1 ({\boldsymbol{W}},p_{ij} )\}\\ &{\rm{s.t}}. \ \sum\limits_{i = 1}^c {\sum\limits_{j = i+1}^c {p_{ij} = 1} } , \sum\limits_{k = 1}^{n_i }{u_{ik} = 1}\\ &p_{ij} \ge 0, u_{ik}\ge 0, {\boldsymbol{W}}^{\rm{T}}{\boldsymbol{W}} = {\boldsymbol{I}}_m \end{split} $$ (29) 模型(29)属于约束的最小化问题. 因为约束集是闭有界集且目标函数是连续的, 模型(29)存在解. 注意到优化变量
$ u_{ik} $ ,$ p_{ij} $ 以及$ {\boldsymbol{W}} $ 的约束是独立的, 这样交替优化算法能有效地求解模型(29). 模型(22)仅涉及优化变量$ {\boldsymbol{W}} $ 且目标函数是复杂的非线性优化问题, 但模型(29)涉及三组优化变量, 每一组优化变量对应一个优化子问题. 算法3概括了求解模型(29)的过程.算法3. 求解式(29)的交替优化算法
1) 给定初始
$ p_{ij} $ 和$ u_{ik} $ ,2) 重复直到收敛
a) 固定
$ p_{ij}\; $ 和$ u_{ik} $ , 更新$ {\boldsymbol{W}} $ ,b) 固定
$ u_{ik} $ 和$ {\boldsymbol{W}} $ , 通过(27)更新$ p_{ij} $ ,c) 固定
$ p_{ij} $ 和$ {\boldsymbol{W}} $ , 通过(28)更新$ u_{ik} $ .如果
$ s = r = 2 $ , 算法1中的步骤a)可通过特征值分解取得投影矩阵$ {\boldsymbol{W}} $ . 在其他情况下, 可通过在Stiefel流形上的梯度下降法取得投影矩阵$ {\boldsymbol{W}} $ . 不同于正则化对抗LDA的求解, 如果采用Stiefel流形上的梯度下降法取得$ {\boldsymbol{W}} $ [41], 此时函数的梯度并不包含指数函数, 这实际上把指数函数放在了$ p_{ij} $ 和$ u_{ik} $ 的更新上. 在$ s = r = 2 $ 情况下, 取得$ W $ 的计算复杂度为${\rm{O}}(d^3)$ . 当样本的维数较大时, 执行特征值分解可能比较耗时, 那么可采用流形上的梯度下降法取得$ {\boldsymbol{W}} $ . 采用Stiefel流形上的梯度下降法取得$ {\boldsymbol{W}} $ 的复杂度为${\rm{O}}(T_g(c^2dm+ndm))$ , 其中$ T_g $ 为梯度下降法的迭代次数. 更新$ p_{ij} $ 和$ u_{ik} $ 的计算复杂度分别为${\rm{ O}}(c^2dm)$ 和${\rm{O}}(ndm)$ . 这样如果$ s = r = 2 $ 且采用特征值分解取得投影矩阵$ {\boldsymbol{W}} $ , 那么算法的计算复杂度为${\rm{O}}(T_3 (c^2dm+ndm+d^3))$ , 其中$ T_3 $ 为算法3的迭代次数. 如果采用Stiefel流形上的梯度下降法取得投影矩阵$ {{\boldsymbol{W}}} $ , 那么算法3的计算复杂度为${\rm{O}}(T_3 (c^2dm+ndm+T_g (c^2dm+ndm)))$ .2.4 与其他线性判别分析的关系
从式(17)和(18)可得到如下推论.
推论 1. 假定
$ p_{ij}^\ast $ 和$ u_{ik}^\ast $ 如式(17)和(18)那样定义, 那么可得出$$ \mathop {\lim }\limits_{\eta \to \infty } p_{ij}^\ast = q_{ij} , \quad \mathop {\lim }\limits_{\lambda _i \to \infty } u_{ik}^\ast = v_{ik} $$ 推论1说明了当参数
$ \eta $ 和$ \; \lambda _i $ 趋向正无穷大时,$ p_{ij} $ 和事先定义的$ q_{ij} $ 一致, 以及$ u_{ik} $ 和事先定义的$ v_{ik} $ 一致. 在这种情况下, 根据$ q_{ij} $ 和$ v_{ik} $ 定义可得出$ p_{ij} = 2/(c(c-1)) $ 和$ u_{ik} = 1/n_i $ . 此时正则化对抗LDA退化为不同范数的LDA. 即当$ s = r = 2 $ 时, 模型(14)成为L2范数的LDA; 当$ s = r = 1 $ 时, 模型(14)成为L1范数的LDA. 当参数$ \eta $ 和$ \lambda _i $ 趋向0时, 模型(14)变成了最强对抗概率分布下的线性判别分析. 这样参数$ \eta $ 和$ \lambda_i $ 的变化为模型(14)和各种范数的LDA建立了联系. 因此RALDA推广了以前的模型.从式(27)和(28)可知: 当参数
$ \eta $ 和$ \lambda_i $ 趋向正无穷大时,$ p_{ij} = 2/(c(c-1)) $ 和$ u_{ik} = 1/n_i $ . 此时正则化乐观LDA退化为不同范数的LDA. 即$ s = r = 2 $ 时, 模型(25)成为L2范数的LDA; 当$ s = r = 1 $ 时, 模型(25)成为L1范数的LDA. 当参数$ \eta $ 和$ \lambda _i $ 趋向0时, 模型(25)变成了最乐观概率分布下的线性判别分析. 从式(17)和(18), 以及式(27)和(28)可知, RALDA和ROLDA中的$ p_{ij} $ 和$ u_{ik} $ 是不同的. 从(17)可知类边界附近的样本具有大的采样概率; 从(28)可知类中心附近的样本具有大的采样概率. 这样模型(14)优先考虑那些不利区分的样本, 而模型(25)优先考虑了那些有利区分的样本. 尽管这两种模型的机制是不同的, 但是当参数趋向无穷时, 它们是等价的.3. 实验结果
本节通过在数据集上的一系列实验来评估所提出模型的有效性. 当涉及到分类问题时, 本文采用了最近邻分类器且度量准则采用了欧氏范数. 为了进行比较, 本文编程实现了几种鲁棒的特征提取方法, 包括L1-LDA[6]、最不利LDA (Worst-case LDA, WLDA[16])、LDA-L1[28]和L21-LDA[34]. L1-LDA 和LDA-L1的参数设置与文献[34]中的相同. 注意到提出的模型涉及多个参数. 为了简单起见, 令参数
$ \lambda = \lambda _1 = \cdots = \lambda _c $ , 即所有的类都被赋予了相同的参数$ \lambda $ , 这样模型的参数被约简为两个参数$ \lambda $ 和$ \eta $ , 两个参数取自集合$ {\{}10^{-3},10^{-2},10^{-1},1,10,10^2,10^3{\}} $ . 对于参数$ r $ 和$ s $ , 本文只考虑参数取特殊值的情况, 即把$ s = r = 1 $ 和$ s = r = 2 $ 的RALDA分别简记为L1RALDA和L2RALDA,以及把$ s = r = 1 $ 和$ s = r = 2 $ 的ROLDA分别简记为L1ROLDA和L2ROLDA. 迭代方法的初始解采用了LDA的正交化投影矩阵. 实验环境是一台内存为8 GB的奔腾1.6 GHz计算机和Matlab (7.0.0)编程语言.3.1 人脸和物体数据集的实验
本小节在四个人脸数据库(Yale、ORL、UMIST和AR)上和一个物体数据库(COIL)上测试了提出的模型. ORL人脸数据库包含40个人, 每个人都有10幅不同的图像, 所有的图像都是在一个均匀背景下拍摄的. UMIST人脸数据库包含20个人的564幅人脸图像, 每个人都有不同的种族、性别和外貌, 例如不同的表情、照明、戴眼镜/不戴眼镜、留胡须/不留胡须、不同的发型. 耶鲁大学的人脸数据库包含15个人的165幅灰度图像, 其人脸图像涉及光照条件和面部表情的变化. AR人脸数据库包含4000多幅彩色人脸图像, 每个人有不同的面部表情、光照条件和遮挡. AR人脸图像在两个不同的时间段拍摄且时间间隔是两周, 每阶段获取每个人的13幅图像. COIL数据库包含1440幅灰度图像和20个物体的黑色背景, 每个物体有72幅不同的图像. 为了提高计算效率, 将所有图像归一化为
$ 32\times32 $ 大小的灰度图像.考虑到提出的算法是一种迭代算法, 第一组实验测试了算法的收敛性. 实验数据来自Yale数据集. 我们随机选取每个人的四幅图像组成训练集, 其它图像用于测试. 假设约简维数为14. 训练集中有一半的样本被矩形噪声污染. 矩形噪声包含等概率的白点和黑点, 它们在图像中的位置是随机的且块的大小是
$ 32\times32 $ 像素. 在实施算法2时, 令$ \beta = 0.5 $ . 图1列出了L2RALDA, L1RALDA, L2ROLDA和L1ROLDA四种方法的收敛性. 为了简单性, 在这组实验中令$ \lambda = \eta $ .
图 1 L2RALDA, L1RALDA, L2ROLDA和L1ROLDA的收敛性分析Fig. 1 Convergence analysis of L2RALDA, L1RALDA, L2ROLDA and L1ROLDA从图1可知, 四种算法的目标函数值随着迭代次数的增加而递减. 当迭代次数超过某一数值时, 目标函数值几乎保持稳定. 文献[27]指出: 当出现小样本的奇异性问题时, 采用梯度上升法求解L1范数的判别分析(目标函数为最大化问题)可能使得目标函数值发生振荡现象. 在这组实验中, 图像的维数远远大于训练样本的个数, 这存在奇异性问题, 但图1显示了提出的算法的目标函数值并没有出现振荡的情况, 这意味着提出的算法在某种程度上避免了小样本的奇异性问题. 从图1可观察到基于L1范数的模型比基于L2范数的模型一般需要更多的迭代次数, 这是因为基于L1范数的模型有不可微的目标函数. 注意到不同的参数也影响算法的收敛速度. 因此在后面的实验中, 本文设定算法的停止条件为最大迭代次数为50或目标函数值的相对改变不超过
$ 10^{-4} $ .在约简的参数下提出的模型有两个重要参数
$ \lambda $ 和$ \eta $ . 这组实验探索了参数$ \lambda $ 和$ \eta $ 对识别性能的影响. 对于图像识别问题, 为了降低计算代价, 采用主成分分析降维但保持图像的百分之九十九的能量. 对于耶鲁数据集, 随机选取每个人的四幅图像组成训练集, 其他样本用于测试. 假设约简维数为14, 固定$ r = s = 1 $ 或$ r = s = 2 $ , 参数$ \lambda $ 和$ \eta $ 从集合${\{}10^{-3}, $ $ 10^{-2},10^{-1},1,10,10^2,10^3{\}}$ 中取值. 因此每个参数取七个值. 实验结果来自十次的平均实验. 图2显示了每种算法随参数变化的错误率. 在图2的每个子图中, 其中$ x $ 轴表示对数尺度的参数$ \lambda $ ,$ y $ 轴表示对数尺度的参数$ \eta $ , 以及$ z $ 轴表示算法的错误率.
图 2 L2RALDA, L1RALDA, L2ROLDA和L1ROLDA的错误率与参数的关系Fig. 2 Error rates of L2RALDA, L1RALDA, L2ROLDA and L1ROLDA versus the parameters从图2可看出, 模型的错误率随着参数的变化而变化. 当参数
$ \lambda $ 和$ \eta $ 取较小值时, L1ROLDA的错误率较低. 对于L2ROLDA, 如果参数$ \eta $ 取较大值且参数$ \lambda $ 取较小值, 则分类性能较好. 对于L1RALDA, 如果参数$ \eta $ 取较小值且参数$ \lambda $ 取较大值, 则在很大范围内获得较低的错误率. 对于L2RALDA, 其参数也影响算法的性能. 这组实验表明了L1ROLDA和L1RALDA的作用机理是不同的. 因此在实际应用中需要选择合适的参数才能获得最佳的分类性能, 这可通过交叉验证等方法来获得最佳参数.为了比较各种模型的特征提取性能, 在Yale、ORL、UMIST和COIL数据集上随机选取每个人的4幅图像构成训练集, 其余图像用作测试目的. 为了评价算法的鲁棒性, 在Yale、ORL、UMIST和COIL数据集上人工模拟了遮挡图像, 那就是训练集中有一半的样本被矩形噪声污染. 矩形噪声包含等概率的白点和黑点, 它们在图像中的位置是随机的, 块的大小是
$ 20 \times 20 $ 像素. 由于AR数据集包含实际遮挡的情况, 本文考虑了120个人的两种遮挡情况: 其一是太阳镜遮挡, 其二是围巾遮挡. 在AR数据集上, 对于太阳镜遮挡, 从第一时间段的7幅无遮挡图像中随机选择3幅图像, 然后将这些图像与随机选择的3幅太阳镜遮挡的图像构成训练集. 第二时间段得到的7幅无遮挡的图像被用做测试集. 因此每个人的训练样本数为6. 对于围巾遮挡, 从第一时间段的7幅无遮挡图像中随机选择3幅图像, 然后将这些图像与随机选择的3幅围巾遮挡图像构成训练集, 第二时间段得到的7幅无遮挡的图像被用做测试集.图3显示了在Yale数据库上几种算法的错误率随约简特征变化的情况. 表1列出了各种方法的最好性能. 另外表1中给出了各个人脸数据集上和COIL数据集上的最好性能. 每种方法的参数在额外的五次运行上得到. 表1的实验结果来自20次随机运行的平均, 其中C- 表示污染的数据集.
图 3 数据集上不同方法随维数变化的错误率Fig. 3 Error rates of various methods with varying dimensions on the Yale database表 1 各种方法在原始数据集和污染数据集上的平均错误率(%)和标准偏差Table 1 Average error rates (%) of various methods and their standard deviations on the original and contaminated data setsData sets L1-LDA LDA-L1 L21-LDA WLDA L2RALDA L1RALDA L2ROLDA L1ROLDA Yale 8.48 (3.42) 9.52 (3.47) 7.81 (4.21) 10.19 (3.24) 8.48 (4.25) 9.19 (3.96) 8.76 (3.84) 7.46 (3.10) C-Yale 24.95 (4.76) 25.05 (5.05) 24.86 (4.98) 27.81 (4.87) 27.24 (4.92) 24.57 (4.58) 23.24 (4.49) 22.76 (4.12) ORL 9.89 (2.13) 0.21 (2.06) 8.86 (2.45) 10.33 (2.02) 8.98 (2.15) 8.34 (2.12) 9.66 (2.18) 9.19 (1.92) C-ORL 14.62 (2.41) 15.27 (2.32) 13.98 (2.73) 15.92 (2.85) 15.82 (2.67) 13.13 (2.63) 13.45 (2.49) 12.58 (2.52) UMIST 8.99 (2.09) 9.23 (2.07) 8.87 (2.75) 10.15 (2.02) 9.42 (2.15) 8.83 (2.12) 9.07 (2.18) 8.98 (1.99) C-UMIST 24.52 (3.89) 26.33 (3.93) 22.98 (3.85) 29.23 (3.84) 23.39 (4.04) 23.52 (3.92) 23.22 (3.88) 21.90 (3.72) COIL 18.45 (2.02) 19.46 (1.64) 18.21 (1.65) 19.97 (1.79) 19.05 (1.64) 17.98 (1.46) 18.31 (2.12) 17.42 (2.14) C-COIL 28.34 (3.41) 29.66 (3.49) 27.35 (3.55) 29.01 (3.15) 28.46 (3.43) 27.65 (2.43) 28.32 (3.01) 26.22 (3.32) AR-sunglasses 9.26 (1.73) 9.38 (1.46) 8.05 (1.57) 10.02 (1.70) 9.21 (1.53) 9.01 (1.25) 8.25 (1.23) 7.33 (1.79) AR-scarf 21.29 (1.10) 20.81 (1.25) 19.03 (1.28) 28.02 (0.92) 26.35 (0.89) 20.34 (1.34) 19.38 (1.24) 17.24 (1.34) 从图3可知, 随着约简维数的增加各种方法的错误率下降, 但过多的特征反而使得错误率上升. 这表明特征的维数是一个重要的参数. 从表1可看出, 对于原图像集, L1RALDA在ORL和UMIST数据集上可获得很好的分类效果, 这表明在适当的条件下, 优先考虑边界点的判别分析算法是合理的. 当部分图像被污染后, L1ROLDA在大多数情况下优于其他方法. 在实际遮挡的AR数据上, 围巾遮挡比太阳镜遮挡导致更大的错误率.
同其他方法比较, L1ROLDA不仅采用了L1范数的损失函数, 而且考虑了样本的采样概率, 其采样概率在不确定集中自适应地变化, 从而得到较好的效果. 从表1可知, 当部分图像被污染后, 各种方法错误率的标准偏差一般大于原始图像上各种方法错误率的标准偏差. 这表明污染的数据使得各种方法的性能具有更大的不确定性.
这组实验比较了各种算法在五个图像数据集上的时间消耗. 提出算法的停止条件如前面所述. 在ORL, UMIST, Yale和COIL数据集上假定约简维数为40. 由于AR数据集包含更多的类数, 其约简维数设定为80. 图4显示了各种算法在五个数据集上的运行时间(单位: 秒).
从图4可看出, WLDA的运行时间远远高于其它算法的运行时间, 这是因为这种方法采用了二阶锥规划. L1-LDA和LDA-L1都采用了贪婪算法取得多个投影向量, 它们的运行时间相差不大. 在Yale和ORL数据集上, L21LDA的运行时间是最少的, 但在UMIST和COIL数据集上, L2ROLDA需要的时间最少. 由于在AR数据集上的约简维数为80且类数较多, 每种方法的训练时间明显大于在其他数据集上的训练时间. 一般来说, L1RALDA和L1ROLDA训练时间分别大于L2RALDA和L2ROLDA的训练时间, 这是因为L1RALDA和L1ROLDA采用了L1范数导致其目标函数是不可微的, 而L2RALDA和L2ROLDA的目标函数是可微函数.
3.2 UCI数据集上的实验
这组实验使用的数据集来自UCI机器学习库. 这些数据集已被广泛用于评估一些学习算法的性能. 本文在8个数据集上测试了提出的模型. 这8个数据集分别是Australia (690样本/14特征/2类), Diabetes (768/8/2), German (1000/24/2), Heart (270/13/2), Liver(345/6/2), Sonar (208/60/2), WPBC (198/33/2)和Waveform (5000/21/3). 不同于图像数据集, 对于这些数据集, 训练样本的维数远远小于训练样本的个数, 即小样本的奇异性问题不会出现. 每个数据集样本的属性被转化为[−1, 1]区间. 对于每个数据集, 随机选取70% 的样本构成训练集, 剩下的样本作为测试集. 除了原始数据集, 我们也模拟了训练集中样本的某些特征被污染的情况. 具体来说, 训练集中一半样本的50% 特征被替换为由−1和1组成的随机噪声.
每种方法的参数在训练集上通过五叠交叉验证方法学习得到. 实验性能取自十次随机实验的平均结果. 为了比较两种算法在同一个数据集上的性能, 在显著性水平0.05的情况下计算L1ROLDA和其他算法的配对
$ t $ 检验的$ p $ -值. 如果$ p $ - 值大于0.05时, 这表明L1ROLDA和其他算法没有显著的差别. 当$ p $ -值小于0.05时, 这表明L1ROLDA和其他算法存在显著差别. 表2和表3列出在原始数据集和污染数据集上的实验结果, 其实验结果包括平均正确率(Average correct rates, ACR)和标准偏差(standard deviations,SD)以及L1ROLDA和其他方法的配对$ t $ 检验的$ p $ -值.表 2 各种方法在原始数据集上的平均正确率(ACR(%)), 标准偏差(SD)和$ p $ -值Table 2 Average correct rates (ACR(%)), standard deviations (SD), and$ p $ -values of various methods on the original data setsData sets L1-LDA LDA-L1 L21-LDA WLDA L2RALDA L1RALDA L2ROLDA L1ROLDA ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) $ p $-值 $ p $-值 $ p $-值 $ p $-值 $ p $-值 $ p $-值 $ p $-值 $ p $- 值 Australian 82.22 (3.44) 80.15 (3.36) 83.44 (3.57) 80.12 (3.29) 79.15 (3.61) 82.99 (3.46) 79.77 (3.27) 84.12 (3.63) 7.98$ \times 10^{-3} $ 3.13$ \times 10^{-5} $ 0.43 3.00$ \times 10^{-5} $ 1.45$ \times 10^{-5} $ 0.028 1.78$ \times 10^{-5} $ — Diabetes 72.55 (4.51) 71.68 (4.62) 73.28 (4.33) 70.19 (4.40) 71.18 (4.71) 72.87 (4.26) 71.99 (4.27) 72.68 (4.39) 0.22 0.15 0.84 0.0084 0.10 0.46 0.19 — German 74.45 (3.66) 72.02 (3.69) 74.68 (3.88) 69.34 (3.77) 72.06 (3.54) 74.99 (3.49) 72.67 (3.66) 73.74 (3.48) 0.03 1.30$ \times 10^{-3} $ 0.04 6.39$ \times 10^{-4} $ 7.84$ \times 10^{-3} $ 0.04 0.01 — Heart 75.89 (5.11) 74.36 (5.13) 77.32 (5.16) 73.53 (5.17) 74.22 (5.22) 77.52 (5.34) 75.67 (5.54) 78.98 (5.19) 8.94$ \times 10^{-4} $ 5.99$ \times 10^{-5} $ 0.012 3.72$ \times 10^{-6} $ 4.81$ \times 10^{-5} $ 0.043 1.14$ \times 10^{-4} $ — Liver 65.25 (4.33) 63.27 (4.78) 64.34 (4.99) 62.87 (4.60) 62.99 (4.71) 64.12 (4.37) 63.01 (4.48) 64.54 (4.29) 0.52 0.89 0.28 0.074 0.08 0.68 0.51 — Sonar 72.11 (4.98) 70.99 (4.96) 73.16 (5.52) 70.21 (5.43) 70.68 (5.06) 72.45 (5.21) 70.99 (5.29) 73.22 (5.16) 0.06 6.07$ \times 10^{-4} $ 0.72 3.80$ \times 10^{-4} $ 4.45$ \times 10^{-4} $ 0.074 6.69$ \times 10^{-4} $ — Waveform 83.27 (1.99) 82.18 (2.12) 85.12 (1.88) 81.23 (1.94) 81.53 (2.15) 83.69 (2.22) 81.49 (2.10) 86.28 (1.98) 1.93$ \times 10^{-5} $ 8.97$ \times 10^{-6} $ 0.08 1.42$ \times 10^{-6} $ 1.83$ \times 10^{-6} $ 7.10$ \times 10^{-5} $ 1.57$ \times 10^{-6} $ — WPBC 77.89 (5.19) 75.32 (5.23) 78.23 (5.44) 72.12 (5.37) 73.14 (5.21) 79.33 (5.36) 72.99 (5.28) 77.89 (5.29) 0.47 1.67$ \times 10^{-4} $ 0.17 1.19$ \times 10^{-5} $ 1.58$ \times 10^{-5} $ 4.76$ \times 10^{-3} $ 6.08$ \times 10^{-6} $ — 表 3 各种方法在污染数据集上的平均正确率(ACR(%)), 标准偏差(SD)和$ p $ -值Table 3 Average correct rates (ACR(%)), standard deviations (SD), and$ p $ -values of various methods on the contaminated data setsData sets L1-LDA LDA-L1 L21-LDA WLDA L2RALDA L1RALDA L2ROLDA L1ROLDA ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) ACR (SD) $ p $-值 $ p $-值 $ p $-值 $ p $- 值 $ p $-值 $ p $-值 $ p $-值 Australian 80.45 (3.56) 78.34 (3.77) 81.65 (3.46) 75.22 (3.89) 77.26 (3.45) 81.78 (3.66) 79.62 (3.78) 82.51 (3.52) 1.99$ \times 10^{-4} $ 7.89$ \times 10^{-6} $ 0.025 6.02$ \times 10^{-7} $ 5.17$ \times 10^{-6} $ 0.04 2.10$ \times 10^{-5} $ — Diabetes 70.63 (4.22) 69.44 (4.29) 70.32 (4.35) 65.26 (4.65) 69.37 (4.60) 70.65 (4.05) 70.38 (4.30) 70.37 (4.41) 0.41 0.055 0.29 7.55$ \times 10^{-5} $ 0.037 0.49 0.39 — German 71.34 (3.48) 70.08 (3.55) 71.76 (3.22) 64.45 (3.79) 70.05 (3.86) 71.09 (3.94) 71.39 (3.68) 72.36 (3.77) 5.08$ \times 10^{-3} $ 0.92$ \times 10^{-3} $ 1.41$ \times 10^{-2} $ 1.30$ \times 10^{-7} $ 1.80$ \times 10^{-3} $ 0.027 0.099 — Heart 72.05 (5.26) 72.24 (5.45) 72.44 (5.13) 66.53 (4.98) 70.22 (5.26) 70.35 (5.39) 71.51 (4.99) 74.88 (5.10) 3.06$ \times 10^{-3} $ 1.58$ \times 10^{-3} $ 8.12$ \times 10^{-3} $ 2.03$ \times 10^{-6} $ 0.35$ \times 10^{-4} $ 1.06$ \times 10^{-4} $ 0.67$ \times 10^{-3} $ — Liver 62.67 (4.33) 60.67 (4.59) 62.53 (4.25) 59.36 (4.78) 60.08 (4.32) 62.04 (4.64) 61.01 (4.13) 63.98 (4.31) 0.047 9.79$ \times 10^{-4} $ 0.039 1.51$ \times 10^{-4} $ 2.75$ \times 10^{-4} $ 0.032 7.22$ \times 10^{-3} $ — Sonar 70.56 (5.71) 68.89 (5.96) 71.37 (5.34) 66.19 (5.39) 68.34 (5.30) 70.32 (5.41) 69.82 (5.27) 71.02 (5.19) 0.17 9.16$ \times 10^{-4} $ 0.55 6.18$ \times 10^{-5} $ 2.34$ \times 10^{-4} $ 0.12 6.99$ \times 10^{-2} $ — Waveform 80.46 (1.89) 79.04 (2.03) 81.08 (1.96) 79.28 (1.89) 80.56 (1.95) 81.75 (2.02) 80.73 (2.11) 82.28 (2.03) 4.47$ \times 10^{-3} $ 1.54$ \times 10^{-5} $ 0.03 4.69$ \times 10^{-5} $ 5.27$ \times 10^{-3} $ 0.18 6.33$ \times 10^{-3} $ — WPBC 73.44 (5.10) 71.35 (5.15) 73.31 (5.27) 70.25 (5.29) 70.21 (5.33) 72.21 (5.39) 70.82 (5.42) 74.76 (5.22) 0.49 2.30$ \times 10^{-2} $ 0.34 3.17$ \times 10^{-3} $ 2.96$ \times 10^{-3} $ 3.59$ \times 10^{-2} $ 8.34$ \times 10^{-3} $ — 从表2可知, L21-LDA在Diabetes数据集上取得最好的性能, L1RALDA在German和WPBC数据集上取得最好的性能, L1ROLDA在Australian, Heart和Waveform数据集上取得最好的性能, L1-LDA在Liver数据集上取得最好的性能, 这表明了没有一种方法在这些数据集上取得一致好的性能. 从表3可知, 当特征被污染后, 每种方法的性能都会存在某种程度的下降. 一般来说基于L2范数方法不比基于L1范数方法好. 从表2和表3的
$ p $ -值可知, L1ROLDA和其它方法是否存在明显的差别. 例如: 从$ p $ -值可知在特征没有被污染的情况下, L1ROLDA和L21LDA在German和Heart数据集上存在统计意义上的差别, 但当特征被污染后, L1ROLDA和L21LDA在Australian, German, Heart, Liver和Waveform数据集上存在统计意义上的差别.当特征被污染后, L1ROLDA方法在多数情况下优于其他方法, 这是因为在不确定集下, 优先考虑了那些有利区分的样本, 这些样本可能不是污染的数据点, 而对离群点赋予较低的采样概率. 因此当数据被污染后, 应当优先选择L1ROLDA方法. 实际上, 当测试RALDA和ROLDA时, 如果在验证数据集上ROLDA的性能远远好于RALDA的性能, 那么说明训练集包含离群点. 在这种情况下, 我们可采用一些去离群点的方法去除训练集中的离群点, 然后再执行特征提取算法.
尽管配对
$ t $ 检验能比较两种算法在同一个数据集上的性能差别, 但是它不能取得多种算法在多个数据集上的性能排序问题. 由于在多个数据集上测试了多种方法, 本文采用Friedman检验[40]评估多种算法的性能. 在Friedman检验中, 如果零假设成立, 即假设所有的算法在性能上是相等的, Friedman统计量可用概率分布来计算. 本文使用关键差别(Critical difference, CD)图[40]比较不同算法的性能. 图5表示了在原始数据和污染数据上的性能分析的CD图. CD图的平均秩提供了算法的性能的排序. 平均秩越小, 算法的性能越好. 从图5(a)可知, L1ROLDA给出了最小的平均秩, 但是L21-LDA的平均秩和L1ROLDA的平均秩相差不大. WLDA有最大的平均秩. 从图5(b)可知, 当数据被污染后, L1ROLDA仍然取得了最小的平均秩, 但L21-LDA的平均秩明显大于L1ROLDA的平均秩. 总的来说, 由于采用了L1范数和优先考虑了类中心附近的样本, 当数据被污染后, 正则化乐观线性判别分析取得最好的性能.4. 结论
本文提出了基于不确定集和混合范数的线性判别分析方法. 不同于以前的方法, 本文借助Kullback-Leibler不确定集描述样本的变化信息, 这样可探索不确定集中的概率分布. 由于样本或类中心的采样概率在不确定集中灵活变化, 从而使得模型适应数据的内在特性. 模型是比率优化和非凸优化问题. 广义Dinkelbach算法被用来求解优化模型. 本文利用投影梯度法或交替优化技术求解算法的优化子问题. 这样算法的收敛性直接来自广义Dinkelbach算法的收敛性. 在图像数据集和UCI数据集上做了一系列实验. 实验结果表明: 在没有污染的数据集上, 由于RALDA考虑了类边界附近的样本, RALDA应当被优先考虑, 但在污染数据集上, ROLDA应当被优先考虑. 由于本文简化了模型中一些参数, 这些参数对模型的性能会产生一定的影响. 今后我们将重点研究如何自动学习多个参数, 并将本文的基本思想推广到其它基于核函数的非线性判别分析和张量判别分析.
-
图 2 区域搜索地图与区域覆盖地图映射示例$(s_f=2)$
Fig. 2 The example of mapping the area search map with the area cover map$(s_f=2)$
图 6 六个机器人在区域搜索过程中不同时刻下的搜索轨迹
Fig. 6 The search trajectories of six robots at different moments during the area search process
图 7 分层仿生神经网络信息模型在区域搜索过程中不同时刻下的活性值
Fig. 7 The activity values of the hierarchical bio-inspired neural network information model at different moments during the area search process
图 8 六个机器人在不同算法驱动下的区域搜索轨迹
Fig. 8 Six robots search trajectories in a region driven by different algorithms
表 1 主要符号说明
Table 1 Description of main symbols
主要符号 具体含义 $ N_r $ 机器人的数量 ${ S}_{{\rm cov}}^{k}$ 第$ k $个机器人搜索的面积大小 ${ S}_{{\rm cov}}^{\rm rep}$ $ N_r $个机器人重复搜索的面积大小 $ { S}(G(x,\;y)) $ 栅格$ G(x,\;y) $的状态 ${ S}(A(\hat{x},\;\hat{y}))$ 子区域$A(\hat{x},\;\hat{y})$的状态 $ K_{\rm u} $ 未搜索栅格状态标记 $ K_{\rm o} $ 障碍物栅格状态标记 $ K_{\rm c} $ 自由栅格状态标记 $ A $ 神经元活性值衰减速率 $ B $ 神经元活性值上限 $ -D $ 神经元活性值下限 $M_r$ 第$i$个神经元的相邻神经元个数 $\psi_{i}$ AS-BNN第$i$个神经元的活性值 $\psi_{i}'$ AC-BNN第$i$个神经元的活性值 $w_{ij} $ 神经元之间连接权重系数 $I_{i}$ AS-BNN神经元外部输入信号 $I_{i}'$ AC-BNN神经元外部输入信号 $L$ DMPC框架下机器人决策预测步长 $h_{s}(k)$ 机器人在栅格地图下位置状态 $h_{s}'(k)$ 机器人在覆盖地图下位置状态 $A(\hat{x}_g,\;\hat{y}_g)$ 机器人局部最优状态下预测的目标子区域 ${x}_s(k),\;{y}_s(k)$ $k$ 时刻机器人在栅格地图所处位置 $\hat{x}_{s}(k),\;\hat{y}_{s}(k)$ $k$ 时刻机器人在覆盖地图所处位置 $J$ 用于机器人正常搜索状态下搜索路径预测的搜索收益函数 $J_E$ 用于机器人局部最优搜索状态下子区域引导路径预测过程的搜索收益函数 $J_H$ 用于机器人局部最优搜索状态下目标子区域搜索路径预测过程的搜索收益函数 $ J^{(L)} $ 机器人$L$步累积搜索收益函数 $J_c$ 神经元活性值增益函数(搜索路径预测) $J_c'$ 神经元活性值增益函数(子区域引导路径预测) $J_t$ 转弯代价函数 $J_g$ 目标子区域引导函数 $\lambda_1$ 函数$J_c$对应的权重系数 $\lambda_2$ 函数$J_t$对应的权重系数 $\lambda_3$ 函数$J_g$对应的权重系数 
下载: 导出CSV
下载: 导出CSV
表 3 不同机器人数量下4种算法区域搜索性能对比
Table 3 Comparison of area search performance of four algorithms under different number of robots
机器人
数量运动
步数BNN算法[26] A-RPSO算法[12] DCRS算法[6] 本文所提算法 AVE-C STD-C MAX-C MIN-C AVE-C STD-C MAX-C MIN-C AVE-C STD-C MAX-C MIN-C AVE-C STD-C MAX-C MIN-C 2 252 84.047% 0.1375 93.556% 72.111% 82.764% 0.0893 94.000% 64.333% 97.164% 0.0330 100.000% 83.556% 99.564% 0.0062 100.000% 98.778% 4 126 84.592% 0.0737 96.556% 76.333% 85.500% 0.0631 96.111% 65.000% 96.836% 0.0232 99.667% 91.111% 99.656% 0.0039 100.000% 99.111% 6 84 86.290% 0.0843 95.667% 75.556% 88.587% 0.0391 93.778% 82.889% 97.438% 0.0162 99.889% 92.778% 99.596% 0.0070 100.000% 98.778% 8 56 82.489% 0.0712 92.444% 71.333% 88.438% 0.0309 93.333% 80.111% 96.106% 0.0231 99.111% 87.444% 99.428% 0.0057 100.000% 98.889%
下载: 导出CSV
-
[1] Cao X, Li M Y, Tao Y T, Lu P. HMA-SAR: Multi-agent search and rescue for unknown located dynamic targets in completely unknown environments. IEEE Robotics and Automation Letters, 2024, 9(6): 5567−5574 doi: 10.1109/LRA.2024.3396097 [2] Peng B, Zhang X R, Shang M S. A novel competition-based coordination model with dynamic feedback for multi-robot systems. IEEE/CAA Journal of Automatica Sinica, 2023, 10(10): 2029−2031 [3] Li K, Zhao K, Song Y D. Adaptive consensus of uncertain multi-agent systems with unified prescribed performance. IEEE/CAA Journal of Automatica Sinica, 2024, 11(5): 1310−1312 doi: 10.1109/JAS.2023.123723 [4] Huang J H, Zeng J, Chi X M, Sreenath K, Liu Z T, Su H Y. Velocity obstacle for polytopic collision avoidance for distributed multi-robot systems. IEEE Robotics and Automation Letters, 2023, 8(6): 3502−3509 doi: 10.1109/LRA.2023.3269295 [5] 张方方, 陈波, 班旋旋, 霍本岩, 彭金柱. 基于生物启发神经网络和DMPC的多机器人协同搜索算法. 控制与决策, 2021, 36(11): 2699−2706Zhang Fang-Fang, Chen Bo, Ban Xuan-Xuan, Huo Ben-Yan, Peng Jin-Zhu. Multi-robot cooperative search algorithm based on bio-inspired neural network and DMPC. Control and Decision, 2021, 36(11): 2699−2706 [6] Chen B, Zhang H, Zhang F F, Liu Y H, Tan C, Yu H N, et al. A multirobot distributed collaborative region coverage search algorithm based on Glasius bio-inspired neural network. IEEE Transactions on Cognitive and Developmental Systems, 2023, 15(3): 1449−1462 doi: 10.1109/TCDS.2022.3218718 [7] Chen B, Zhang H, Zhang F F, Jiang Y M, Miao Z Q, Yu H N, et al. DIBNN: A dual-improved-BNN based algorithm for multi-robot cooperative area search in complex obstacle environments. IEEE Transactions on Automation Science and Engineering, DOI: 10.1109/TASE.2024.3379166 [8] Zheng X M, Jain S, Koenig S, Kempe D. Multi-robot forest coverage. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Edmonton, Canada: IEEE, 2005. 3852−3857 [9] Pehlivanoglu Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV. Aerospace Science and Technology, 2012, 16(1): 47−55 doi: 10.1016/j.ast.2011.02.006 [10] Dong W, Liu S S, Ding Y, Sheng X J, Zhu X Y. An artificially weighted spanning tree coverage algorithm for decentralized flying robots. IEEE Transactions on Automation Science and Engineering, 2020, 17(4): 1689−1698 [11] Nair V G, Guruprasad K R. MR-SimExCoverage: Multi-robot simultaneous exploration and coverage. Computers & Electrical Engineering, 2020, 85: Article No. 106680 [12] Dadgar M, Jafari S, Hamzeh A. A PSO-based multi-robot cooperation method for target searching in unknown environments. Neurocomputing, 2016, 177: 62−74 doi: 10.1016/j.neucom.2015.11.007 [13] Zhang J Q, Lin Y X, Zhou M C. Virtual-source and virtual-swarm-based particle swarm optimizer for large-scale multi-source location via robot swarm. IEEE Transactions on Evolutionary Computation, DOI: 10.1109/TEVC.2024.3391622 [14] Tang, H W, Sun W, Yu H S, Lin A P, Xue M. A multirobot target searching method based on bat algorithm in unknown environments. Expert Systems With Applications, 2020, 141: Article No. 112945 doi: 10.1016/j.eswa.2019.112945 [15] Zhou Z W, Luo D L, Shao J, Xu Y, You Y C. Immune genetic algorithm based multi-UAV cooperative target search with event-triggered mechanism. Physical Communication, 2020, 41: Article No. 101103 doi: 10.1016/j.phycom.2020.101103 [16] Yang B, Ding Y S, Jin Y C, Hao K R. Self-organized swarm robot for target search and trapping inspired by bacterial chemotaxis. Robotics and Autonomous Systems, 2015, 72: 83−92 doi: 10.1016/j.robot.2015.05.001 [17] Garg V. E2RGWO: Exploration enhanced robotic GWO for cooperative multiple target search for robotic swarms. Arabian Journal for Science and Engineering, 2023, 48(8): 9887−9903 doi: 10.1007/s13369-022-07438-5 [18] Hou K, Yang Y J, Yang X R, Lai J Z. Distributed cooperative search algorithm with task assignment and receding horizon predictive control for multiple unmanned aerial vehicles. IEEE Access, 2021, 9: 6122−6136 doi: 10.1109/ACCESS.2020.3048974 [19] Dai W, Lu H M, Xiao J H, Zeng Z W, Zheng Z Q. Multi-robot dynamic task allocation for exploration and destruction. Journal of Intelligent & Robotic Systems, 2020, 98: 455−479 [20] Li J, Tan Y. A two-stage imitation learning framework for the multi-target search problem in swarm robotics. Neurocomputing, 2019, 334: 249−264 doi: 10.1016/j.neucom.2019.01.035 [21] Liu B, Wang X P, Zhou W. Multi-UAV collaborative search and strike based on reinforcement learning. Journal of Physics: Conference Series, 2020, 1651 : Article No. 012115 [22] Wang X Y, Fang X. A multi-agent reinforcement learning algorithm with the action preference selection strategy for massive target cooperative search mission planning. Expert Systems With Applications, 2023, 231: Article No. 120643 doi: 10.1016/j.eswa.2023.120643 [23] Hodgkin A L, Huxley A F. A quantitative description of membrane current and its application to conduction and excitation in nerve. The Journal of physiology, 1952, 117(4): 500−544 doi: 10.1113/jphysiol.1952.sp004764 [24] Grossberg S. Contour enhancement, short term memory, and constancies in reverberating neural networks. Studies of Mind and Brain: Neural Principles of Learning, Perception, Development, Cognition, and Motor Control, 1982: 332−378 [25] Luo C M, Yang S X, Stacey D A. Real-time path planning with deadlock avoidance of multiple cleaning robots. In: Proceedings of the IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422). Taiwan, China: IEEE, 2003. 4080−4085 [26] Luo C M, Yang S X, Li X D, Meng M Q H. Neural-dynamics-driven complete area coverage navigation through cooperation of multiple mobile robots. IEEE Transactions on Industrial Electronics, 2017, 64(1): 750−760 doi: 10.1109/TIE.2016.2609838 [27] Sun B, Zhu D Q, Tian C, Luo C M. Complete coverage autonomous underwater vehicles path planning based on Glasius bio-inspired neural network algorithm for discrete and centralized programming. IEEE Transactions on Cognitive and Developmental Systems, 2019, 11(1): 73−84 [28] Muthugala M A V J, Samarakoon S M B P, Elara M R. Toward energy-efficient online complete coverage path planning of a ship hull maintenance robot based on Glasius bio-inspired neural network. Expert Systems With Applications, 2022, 187: Article No. 115940 doi: 10.1016/j.eswa.2021.115940 [29] Zhao L, Li R, Han J D, Zhang J L. A distributed model predictive control-based method for multidifferent-target search in unknown environments. IEEE Transactions on Evolutionary Computation, 2023, 27(1): 111−125 doi: 10.1109/TEVC.2022.3161942 [30] Conte C, Jones C N, Morari M, Zeilinger M N. Distributed synthesis and stability of cooperative distributed model predictive control for linear systems. Automatica, 2016, 69: 117−125 doi: 10.1016/j.automatica.2016.02.009 [31] Qiao K J, Liang J, Yu K J, Yue C T, Lin H Y, Zhang D Z, et al. Evolutionary constrained multiobjective optimization: Scalable high-dimensional constraint benchmarks and algorithm. IEEE Transactions on Evolutionary Computation, 2024, 28(4): 965−979 [32] Grossberg S. Nonlinear neural networks: Principles, mechanisms, and architectures. Neural Networks, 1988, 1(1): 17−61 [33] Ni J J, Yang S X. Bioinspired neural network for real-time cooperative hunting by multirobots in unknown environments. IEEE Transactions on Neural Networks, 2011, 22(12): 2062−2077 doi: 10.1109/TNN.2011.2169808 期刊类型引用(4)
1. 杨静，王晓，王雨桐，刘忠民，李小双，王飞跃. 平行智能与CPSS:三十年发展的回顾与展望. 自动化学报. 2023(03): 614-634 . 
本站查看2. 赵奎，闫玉芳，曹吉龙，高延军. 融合规范化判断的双向循环神经网络诊疗预测模型. 小型微型计算机系统. 2022(06): 1278-1284 . 百度学术3. 赵奎，杜昕娉，高延军，马慧敏. 融合文字与标签的电子病历命名实体识别. 计算机系统应用. 2022(10): 375-381 . 百度学术4. 高华睿，郝龙，王明明，包绍伦，康乐. 基于Att-Bi-LSTM的高速公路短时交通流预测研究. 武汉理工大学学报. 2020(09): 59-64 . 百度学术其他类型引用(5)
-
下载:
计量
- 文章访问数: 367
- HTML全文浏览量: 154
- 被引次数: 9
