如何理解基于多任务优化的特征选择算法MTPSO？

yukamu

MTPSO是什么？
MTPSO这个算法的命名其实很有迷惑性。最初，我以为MTPSO是使用多任务优化方法同时处理多个数据集的特征选择任务。读了论文以后才发现，原来MTPSO是将一个大规模特征选择任务转换成多个子任务，并使用多任务优化方法同时解决多个子任务。
多任务优化处理大规模优化问题？
其实最近一段时间，将大规模问题转换成多个小规模子任务是多任务优化领域的热点。有点类似协同进化的感觉，不过近期的一些论文更强调是子任务可以独立构成完整解，不需要像协同进化一样进行解的拼接。
当然，究竟是协同进化更适合处理大规模问题，还是多任务优化更适合处理大规模问题，在未来几年内应该依然会是学术界争论的热点。不过，相比使用协同进化的特征选择算法VS-CCPSO，使用多任务优化的MTPSO从实验结果来看目前取得了更好的性能。因此，这里我就《Evolutionary Multitasking for Feature Selection in High-dimensional Classification via Particle Swarm Optimisation》这篇论文对基于多任务优化的特征选择算法做一下简单的解析吧。
多任务构造

首先，MTPSO的多个子任务都需要包含一部分的高质量特征和低质量特征。因此，作者使用Relief算法为每个特征分配重要性，特征  的重要性计算方式如下公式所示。具体来说，首先需要随机选择一个数据  ，随后Relief算法需要根据该数据  选择最邻近的 个同类元素作为  和不同类元素作为 。Relief算法的核心是 这个函数，该函数代表数据  和数据  在特征  上的差异。从下面公式可以看出，如果一个特征在内类元素上是高内聚的，而在不同类元素上是低耦合的，那么这个特征就具有高重要性。


根据特征重要性值，我们可以确定一个阈值，用于划分高质量和低质量特征。具体划分的阈值通过特征重要性和特征个数的Trade-Off Knee Point确定。如下图所示，拐点所对应的特征重要性值即为划分阈值。


在确定好高质量特征和低质量特征之后，我们假设 代表高质量特征平均重要性， 代表低质量特征平均重要性，那么新特征选择任务从高质量特征中采样的概率为  ，即如下公式所示。


最终，根据概率  ，我们就可以通过采样构建多个特征选择任务，如下图所示。从图中可以看出，最终每个任务都是原任务的一个子集，即包含了一部分高质量特征，也包含了一部分低质量特征。


最终，MTPSO算法同时优化这  个规模较小的子任务，最终就有希望在有限计算资源的情况下实现更好的特征选择性能。值得一提的是，上述转化方式会存在多个子任务和原始任务最优解不相同的情况，但是从后面的实验结果来看，MTPSO算法在众多数据集上具有良好的表现。
知识迁移

由于MTPSO采用的是Multi-Population的多任务优化范式，因此MTPSO将基于种群最优个体  进行知识迁移。由于  的知识迁移，在迁移之后，粒子群的速度也会相应发生改变，从而实现知识的最终迁移。
何时迁移
MTPSO的知识迁移时机通过 概率进行控制。这是目前多任务优化领域的常规操作，具体细节可以参考当前众多的多任务优化论文。
如何迁移
具体来说，  存在两种迁移方案，第一种是正常的两个任务的  作交叉操作，即如下所示。


第二种方案是如果  在 轮内都没有更新，那么代表可能陷入了局部最优。  则替换为所有任务  平均值。


上述流程整体来看如下图所示。在演化过程执行完成后，最终  个任务会输出  个结果，选择预测准确率最高的特征选择结果即可。


适应度评估

MTPSO的适应度评估函数直接选择将分类准确率 和选择特征数量通过权重 相加。在实际应用场景中，如果不好确定这个阈值的话，也可以考虑多目标优化。不过，多目标多任务优化就是一个另外的故事了。


实验结果

实验设置
MTPSO选择了连续PSO作为特征选择方案，由于特征选择结果需要为0或1，因此MTPSO选择0.6作为阈值，将连续PSO编码进行离散化。离散化过程如下图所示。


实验结果
从实验结果来看MTPSO在最终的预测准确率指标上相比其他算法有更好的效果，由此论文作者证明了MTPSO算法的有效性。

rustum

MTPSO是什么？
MTPSO这个算法的命名其实很有迷惑性。最初，我以为MTPSO是使用多任务优化方法同时处理多个数据集的特征选择任务。读了论文以后才发现，原来MTPSO是将一个大规模特征选择任务转换成多个子任务，并使用多任务优化方法同时解决多个子任务。
多任务优化处理大规模优化问题？
其实最近一段时间，将大规模问题转换成多个小规模子任务是多任务优化领域的热点。有点类似协同进化的感觉，不过近期的一些论文更强调是子任务可以独立构成完整解，不需要像协同进化一样进行解的拼接。
当然，究竟是协同进化更适合处理大规模问题，还是多任务优化更适合处理大规模问题，在未来几年内应该依然会是学术界争论的热点。不过，相比使用协同进化的特征选择算法VS-CCPSO，使用多任务优化的MTPSO从实验结果来看目前取得了更好的性能。因此，这里我就《Evolutionary Multitasking for Feature Selection in High-dimensional Classification via Particle Swarm Optimisation》这篇论文对基于多任务优化的特征选择算法做一下简单的解析吧。
多任务构造

首先，MTPSO的多个子任务都需要包含一部分的高质量特征和低质量特征。因此，作者使用Relief算法为每个特征分配重要性，特征  的重要性计算方式如下公式所示。具体来说，首先需要随机选择一个数据  ，随后Relief算法需要根据该数据  选择最邻近的 个同类元素作为  和不同类元素作为 。Relief算法的核心是 这个函数，该函数代表数据  和数据  在特征  上的差异。从下面公式可以看出，如果一个特征在内类元素上是高内聚的，而在不同类元素上是低耦合的，那么这个特征就具有高重要性。


根据特征重要性值，我们可以确定一个阈值，用于划分高质量和低质量特征。具体划分的阈值通过特征重要性和特征个数的Trade-Off Knee Point确定。如下图所示，拐点所对应的特征重要性值即为划分阈值。


在确定好高质量特征和低质量特征之后，我们假设 代表高质量特征平均重要性， 代表低质量特征平均重要性，那么新特征选择任务从高质量特征中采样的概率为  ，即如下公式所示。


最终，根据概率  ，我们就可以通过采样构建多个特征选择任务，如下图所示。从图中可以看出，最终每个任务都是原任务的一个子集，即包含了一部分高质量特征，也包含了一部分低质量特征。


最终，MTPSO算法同时优化这  个规模较小的子任务，最终就有希望在有限计算资源的情况下实现更好的特征选择性能。值得一提的是，上述转化方式会存在多个子任务和原始任务最优解不相同的情况，但是从后面的实验结果来看，MTPSO算法在众多数据集上具有良好的表现。
知识迁移

由于MTPSO采用的是Multi-Population的多任务优化范式，因此MTPSO将基于种群最优个体  进行知识迁移。由于  的知识迁移，在迁移之后，粒子群的速度也会相应发生改变，从而实现知识的最终迁移。
何时迁移
MTPSO的知识迁移时机通过 概率进行控制。这是目前多任务优化领域的常规操作，具体细节可以参考当前众多的多任务优化论文。
如何迁移
具体来说，  存在两种迁移方案，第一种是正常的两个任务的  作交叉操作，即如下所示。


第二种方案是如果  在 轮内都没有更新，那么代表可能陷入了局部最优。  则替换为所有任务  平均值。


上述流程整体来看如下图所示。在演化过程执行完成后，最终  个任务会输出  个结果，选择预测准确率最高的特征选择结果即可。


适应度评估

MTPSO的适应度评估函数直接选择将分类准确率 和选择特征数量通过权重 相加。在实际应用场景中，如果不好确定这个阈值的话，也可以考虑多目标优化。不过，多目标多任务优化就是一个另外的故事了。


实验结果

实验设置
MTPSO选择了连续PSO作为特征选择方案，由于特征选择结果需要为0或1，因此MTPSO选择0.6作为阈值，将连续PSO编码进行离散化。离散化过程如下图所示。


实验结果
从实验结果来看MTPSO在最终的预测准确率指标上相比其他算法有更好的效果，由此论文作者证明了MTPSO算法的有效性。