Page 71 - 《软件学报》2020年第12期

张鑫 等:自然进化策略的特征选择算法研究 3737

For generation g=1,2,…,τ do
(g)
Sample λ independent points from distribution p(x|θ )→x 1 ,…,x λ
Evaluate the sample (x 1 ,…,x λ ) on f(⋅)
Calculate log-derivatives ∇ θ logπ(x|θ)
End for
1 λ
( )∇
∇ θ J () θ λ g = 1 f x g θ log (xπ ← g | ) θ ∑
1 λ
F ← ∇ ∑ log (x θ π | )∇ log (x θ π | ) T
λ g = 1 θ g θ θ
-1
θ←θ+ηF ∇ θ J(θ)
Until termination criterion met
NES 将普通随机梯度替换为自然梯度,自然梯度首先被 Amari 引入机器学习领域,并且已被证明自然梯度
比普通梯度更有优势 [39,40] .自然梯度能够加速梯度在平原地区的收敛速率,并减缓梯度在高原地区的收敛速率.

2 MCC-NES

ES 能够有效地进行评价学习,并且具有良好的全局搜索能力和并行化能力.进一步地,NES 可以通过使用
样本梯度信息来更新参数.由于 NES 需要处理梯度,我们使用 GPU-Tensorflow 作为 NES 运行框架,同时引入一
些优化策略,提出了一种新的特征选择算法(MCC-NES).之后,通过实验验证 MCC-NES 算法在特征选择问题中
的性能.实验结果表明:MCC-NES 算法能够有效地完成特征选择问题,而且在处理高维数据时有着出色的表现.
2.1 MCC-NES算法建模及特征编码

结合前文分析,本文的工作采用了基于协方差矩阵建模的自然进化策略.分布模型中的参数包括分布均值
向量 m 和分布协方差矩阵 C,其中,|m|=rank(C)表示数据集中特征的个数.当特征个数较小时,对完全协方差矩阵
建模是非常有益的.但是面对高维数据时,使用完全协方差矩阵复杂度就会很高.因为协方差矩阵的大小和数据
2
特征维数相关,对于 n 维数据来说,完全协方差矩阵中元素的个数就会有 n 个.当 n 取值增大时,其计算复杂度就
会呈指数级增长.因此,为了有效处理高维数据,我们选择保留矩阵主要信息,只关心每个特征的发散性而不去
考虑特征之间的相关性,使用对角协方差矩阵代替完全协方差矩阵进行建模,从而降低算法时间复杂度.
在算法的初始化阶段,通过在超参数α上重复添加高斯扰动(扰动强度σ=0.01)来初始化分布均值向量 m,对
于分布协方差矩阵 C,选择使用单位矩阵进行初始化,使得算法模型中每个特征对应于分布均值向量 m 中的一
个元素和分布协方差矩阵 C 中的一个对角元素.在算法迭代时,将向量 m 中的每个元素与矩阵 C 中对应的对角
元素作为正态分布的参数做高斯采样,生成关于每个特征的分布取值,然后,将得到的数值结果通过使用一种新
的编码方式映射到布尔型的特征选择上,具体的特征编码方式如下:
⎧ 1, 1 > 0.5
⎪
x g = ⎨ 1e − g ∗ i y 2 (9)
+
i
⎪
⎩ 0, otherwise
ES 算法一般用于解决连续型优化问题,为了处理特征选择问题,文中使用公式(9)将特征高斯采样的结果映
g
射到{0,1}序列中,其中, y 表示在第 g 次迭代中第 i 个特征的高斯采样结果.使用公式(9)进行特征映射,如图 1
i
所示.若映射后的结果大于 0.5,就选取该特征(用二进制 1 表示选取该特征);否则的话,就不进行选择(用二进制 0
来表示不选取该特征).
通过这种编码方式,我们希望在迭代过程中对于那些已经确定的特征尽量使其保持稳定(在图 1 中表现为
两端较为平缓的部分),而对于不确定的特征提供更多的探索(在图 1 中表现为中间部分的曲线,有较高的斜率,
对于梯度信息更为敏感).