目录
Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。
| 论文概况 | 详细 |
|---|---|
| 标题 | 《Multitree Genetic Programming With New Operators for Transfer Learning in Symbolic Regression With Incomplete Data》 |
| 作者 | Baligh Al-Helali, Qi Chen, Member, Bing Xue, Mengjie Zhang |
| 发表期刊 | IEEE Transactions on Evolutionary Computation |
| 发表年份 | 2021 |
| 期刊等级 | 中科院 SCI 期刊分区(2022年12月最新升级版）1 区，CCF-B |
| 论文代码 | 未公开 |
作者单位：
Evolutionary Computation Research Group, School of Engineering and Computer Science, Victoria University of Wellington, Wellington 6140, New Zealand
研究动机
数据集中存在缺失值是一个非常严重的问题，它会影响机器学习任务的性能。符号回归(SR)是一种回归算法，它同时搜索模型结构和参数，不需要对模型的结构进行任何预设。同时 SR 是一种白盒模型，有着更好的可解释性。由于 SR 的学习过程是数据驱动的，需要着重考虑数据缺失问题。对于不完整数据的处理主要有三种方法，分别是删除缺失值、直接使用缺失值、插值，这些方法都需要足够的数据来提供可靠的模型。所以在实例数量较少的情况下，更适合使用基于迁移学习的方法。
文章贡献
针对数据集存在缺失值的问题，本文提出了一种基于多树 GP(MTGP) 的迁移学习方法 pMTGPDA，用于将知识从完整的源域转移到不完整的目标域中。首先在源域的数据集上训练多个 SR 模型，通过模型中的训练细节计算源域的特征和实例的权重作为先验知识。然后将提取的权重知识用于基于 MTGP 的转换，构造源特征空间到目标特征空间的非对称映射，实现估算目标域中缺失的值的作用。产生变换后的特征和实例以及权重后，对输入的目标数据进行正常的 SR，得到输出的结果。对于 MTGP 的交叉、变异操作，本文开发了新的遗传算子进行优化，而且设置的适应度函数能同时度量域之间的不匹配度和 SR 的学习性能。
本文方法
本文涉及到的符号及其含义如下表所示：
从源域中提取知识
源域的学习过程是对完整数据运行 SR 得到一组模型，用于根据源域学习过程中特征和实例的影响来估计源空间特征和实例的权重。源领域中越重要的特征、实例就越有可能使目标领域受益，因此在转换构建过程中获得的权重就越大。而噪声和离群实例往往有更大的预测偏差，所以它们可能对减轻目标域中的数据缺失问题没有太大的帮助。
这个步骤的流程如下伪代码所示，主要是在循环 r 次种每次训练一个 SR 模型，然后得到源域的特征、实例的知识。
源域特征的权重用如下的公式计算，主要是取某个特征的频率与所有源域特征的总频率之比，然后通过除以 r 计算这些比率的平均值。
源域实例的权重用如下的公式计算，也就是利用学习到的模型在每个实例上的预测误差来计算它们的权重。
基于 MTGP 的迁移学习
变换域通过 GP 和源域特征通过特征构造实现，转换域的特征空间的目标是减少两个域之间分布的不匹配。该方法为一种 wrapper 方法，其流程如下伪代码所示。
算法的步骤可以被简单概括为如下：
- 以完整的源域数据、不完整的目标域训练集、提取到的特征和实例的权重作为输入，生成初始种群进行初始化；
- 利用种群中的每个个体得到转换域，计算转换域的特征、实例的权重；
- 对得到的权重归一化，通过转换域的数据和权重补全目标域的缺失值；
- 估算种群中的个体适应度，通过交叉变异生成下一代。
构造域转换特征的原理如下图所示，用源域的特征作为 MTGP 个体中每棵树的输入，构造出的新特征将一一与目标域的特征对应。
转换域的特征、实例权值
通过 MTGP 将源域 Ds 的特征和实例转换为构造域 Dc，然后使用源域得到的权重为 Dc 的特征和实例计算权重。Dc 的特征权重计算公式如下，其中 M 为构造变换的 MTGP 模型，Mj 为 M 中第 j 棵树的终端集，Xcj 表示构造的第 j 个特征。
Dc 的实例计算公式如下，由于实例可以来源于转换域和目标域，所以这两类实例的权重计算方法不同。属于目标域的实例的权重直接设置为 1，构造域的实例的权重则根据源域的权重计算。
数据插值
通过变换域可以得到一组归一化的特征权值和实例权值，接着通过改进的加权 k 近邻(WKNN)插值对目标数据进行插值。WKNN 除了可以根据源实例对预测误差的影响计算它们的权重，还可以根据它们对目标域中缺失值的输入的贡献进行加权。
插值的步骤如下伪代码所示，将 KNN 检索到的实例组合成通过加权平均求和来估算缺失值，该步骤仅使用实例中具有非缺失值的特征来计算距离。
WKNN 的距离使用改进的加权欧几里得距离，设 Ia 为待输入的不完全实例，j 为 Ia 中具有非缺失值的特征索引集，Ii 为另一个实例且在第 j 个特征的值不缺失。则 Ia 与 Ii 之间的距离计算公式如下：
进一步得到实例 Ia 与实例 Ii 之间的加权距离 ω(Ia,Ii) 的计算公式如下：
对加权距离归一化得到 Nω(Ia, I1)，如果 Ia 与另一个实例之间的距离为零，则它们的加权距离设为 1，而其他实例的权重设置为 0。然后将实例 Ia 缺失的估计值设置为检索到的邻居实例的加权平均值，使用如下公式表示：
MTGP 适应度函数
MTGP 的目标是使变换后的域 Dc 尽可能接近目标域 Dt，接近的程度基于学习损失和分布的不匹配度两个指标来衡量。学习损失 L 指是变换域在插值后对目标任务有利的程度，分布不匹配度 Ω 是转换域的分布与目标域的分布的相似性的度量。
适应度函数的公式表示如下，其中 λ 是设为 0.3 正则化因子，使的训练损失的影响大于域之间分布的影响。
对输入的目标域数据补全缺失值后，运行 SR 并使用相对平方误差 RSE 进行评估，RSE 的公式如下：
目标域的学习损失使用 RSE 计算得到，计算公式如下：
分布不匹配度用于量化 Dt 和 Dc 之间的分布不匹配，此处使用了 KS 度量，它可用于量化两个一维样本 S1 和 S2 之间的概率分布差异。KS 的公式如下，其中 FS1 和 FS2 为 S1 和 S2 的经验分布函数，sup 为上确界函数。
本文将一维数据上的 KS 扩展到多个特征域之间的分布距离，通过简单地平均两个域中对称特征之间的 KS 距离实现，公式如下：
遗传算子
单树 GP 中的遗传算子是在子树级别实现的，由于 MTGP 个体由多棵树组成，本文的遗传算子基于其中的子树的质量实现。树的质量通过构造的特征与个目标特征的分布不匹配度来衡量，整个个体的适应度函数使用如下公式表示：
突变算子将选择需要突变的树的索引，本文提出了一种使概率最差索引变异算子(PWIM)。PWIM 算子鼓励考虑最差的树进行突变，其他树有较小的概率发生突变。突变概率使用如下公式计算，其中 M 为 MTGP 个体，Mk 为 M 中的第 k 棵树，mt 为树的数量，idx 为待选树的索引。
交叉操作只允许在构造相同目标特征的树之间进行，本文提出了一种概率最高同索引交叉算子(PBIC)。PBIC 算子倾向于使用质量更高的树交叉，但并不完全排除较差的树。交叉概率使用如下公式计算，其中 M 为 MTGP 个体，Mk 为 M 中的第 k 棵树，mt 为树的数量，idx 为待选树的索引。
实验结果
数据集
在现有迁移学习回归研究中有 6 个常用的数据集，其中的 Auto-mpg、Imports 数据集包含缺失值，其他数据集是完整的。为了模拟迁移学习的场景，将数据按照一定的连续特征进行排序，然后选择数据的前三分之二作为源域，其余实例作为目标域数据。接着利用不同的正态分布对两个域中的特征进行随机数扰动，保证两个域中分布的差异性。
处理后的数据集信息如下表所示，其中 m 为数据集中的特征数量，ns(nt)为数据分割后源(目标)域中的实例数量。
对于异构情况，需要令源域和目标域具有不同的特征空间，这个通过特征分割如下公式进行特征分割实现。特征空间被分成 Half1 和 Half2 两部分，前半部分用于源域而所有特征用于目标域的设置称为“Half1-All”，此外还有另外两种设置方式：All-Half2 和 Half1-Half2。
为了模拟数据有缺失值的情况，对每个数据集使用 MAR 缺失概率生成不完整数据集。该过程使用 40% 的特征随机重复 30 次，共使用 10%、30%、50% 三种缺失率，每个目标数据集生成 90 个不完整数据集(3×30)。
实验设置
本文提出的方法被称为 pMTGPDA，实验中将与以下几种方法进行了比较。SR 使用 RSE 作为评估指标，每个实验重复运行 30 次。在目标域中数据集按照 3:7 划分为训练集和测试集，来强调目标域中可用学习数据的缺乏。为了评估结果之间的差异，使用显著性水平为 0.05 的 Wilcoxon 非参数统计检验。
| 对比算法 | 简述 |
|---|---|
| WKNNIM | 该方法只考虑目标域，先使用 WKNNIM 方法对目标域的不完整数据进行输入，然后将完整数据用于 SR 学习 |
| WKNNIMDC | 该方法是将目标训练数据和源数据结合在一起得到的训练数据应用 WKNNIM 后进行学习，不进行域间的自适应 |
| 随机森林插值(RFIM) | 从缺失值最少的特征开始，使用随机森林回归补全缺失值，不断重复上述步骤直到完成插值 |
| MTGPTL | 建立一个基于 MTGP 的变换域，只考虑目标域的回归误差 |
| MTGPDA | 除了最小化 MTGPTL 中的误差，还最小化了源域和目标域的分布不匹配，遗传算子都是随机选择树进行操作 |
算法的参数根据验证集选择，实验设置如下表所示。
同构情况下的 SR
在同构的迁移学习中源域的特征空间和目标域的特征空间相似，但对应的边缘分布不同。该部分的实验结果如下图所示，从结果可见所有基于 MTGP 的方法在大多数情况下都能有正迁移能力，pMTGPDA 方法具有最佳的 SR 性能。
异构情况下的 SR
在同构的迁移学习中源域的特征空间与目标域的特征空间不同，根据前面的设置有三种情况：Half1-All、All-Half2、Half1-Half2。Half1-All 中源域的特征空间只包含原始数据的前半部分，目标域包含所有可用的特征。这说明目标域中的 SR 仍将使用类似于同构场景中使用的特性集，但源域中用于构造从源域到目标域的 MTGP 转换的特征较少。Half1-All 的结果如下图所示，从结果可以看出基于 MTGP 的方法在大多数情况下都能提高 SR 性能，pMTGPDA 方法具有最佳的 SR 性能。
All-Half2 中源域的特征空间包含所有可用的原始特征，目标域只有后一半的特征。此时可以使用完整的特征集来构造从源域到目标域的 MTGP 转换，但是目标域用于构建 SR 模型的特性数量有限。All-Half2 的结果如下图所示，从结果可以看出各种方法的 SR 性能普遍较差，pMTGPDA 仍然提高了目标域的 SR 性能。
Half1-Half2 中的两个域具有完全不同的特性集，是一种最为极端的情况。Half1-Half2 的结果如下图所示，从结果可以看出该场景的学习表现比其他场景更差，所提出的 pMTGPDA 方法仍然在目标 SR 性能方面取得了较大的改进。
存在缺失值的真实数据集的 SR
真实数据集 Auto-mpg 和 Imports 本身就存在缺失值，可以使用它们来检查所提出的方法在实际情况下的有效性。该部分将不完整的实例作为测试集，剩余的完整数据作为训练集。使用同质情况下得到的所有可能的模型来预测不完全实例，并计算其平均值和标准差。得到的实验结果如下表所示，“-”(“+”)表示该方法明显劣于(优于) pMTGPDA 方法，“=”表示差异不显著，结果表明 pMTGPDA 在两种数据集上均显著优于其他方法。
训练时间
将 pMTGPDA 与 MTGPTL 和 MTGPDA 比较模型的训练时间，平均训练时间(单位是 10 秒)以及特征的数量如下表所示。可见 MTGPDA 比 MTGPTL 耗时更长，pMTGPDA 的训练时间最长。这是因为 MTGPDA 具有最小化分布不匹配的额外步骤，pMTGPDA 在此基础上具有特征/实例加权步骤。
学习到的转换表达式
下表中展示了几个在 Yacht 数据集上学习到的表达式，可以看到这些构造特征的复杂性是不同的。第三个特征具有最复杂的表达式，第四个特征的表示最为简单。然而在计算分布不匹配度时，结构树复杂度较低的特征 xc4 的失配性能优于复杂度较高的特征。这样的现象可能表明在映射到新域时，复杂的转换可能不代表有较高的泛化能力。
遗传算子比较
本文尝试了多种不同的遗传算子，该部分对这些算子也进行比较。用于比较的突变算子如下表所示：
| 算子 | 缩写 | 简述 |
|---|---|---|
| 随机索引突变 | RIM | 随机选择树进行突变 |
| 所有索引突变 | AIM | 对所选个体的每个树进行突变 |
| 最佳索引突变 | Best Index Mutation, BIM | 选取最小不匹配度值的子树进行突变，该算子鼓励使用较好的特征 |
| 最差索引突变 | WIM | 选择适应度值最差的树进行突变，该算子鼓励较差的树进行变化 |
用于比较的突变算子如下表所示：
| 算子 | 缩写 | 简述 |
|---|---|---|
| 随机相同索引树交叉 | RSIC | 从一个个体中随机选择一棵树，然后与另一个个体中具有相同索引的树交叉 |
| 全索引交叉 | AIC | 在两个个体中具有相同索引的每对树之间进行交叉来扩展 RSIC 算子 |
| 最佳指数交叉 | BIC | 选择不匹配平均最小的一对树标准交叉，该算子鼓励交换较好的树的信息 |
| 最差指数交叉 | WIC | 选择分布相似度平均值最差的一对树进行交叉，该算子鼓励交换较差的树的信息 |
| 概率最差同指数交叉 | PWIC | 类似于 WIC，但该算子不排除较好的树的选择概率 |
对这些算子进行排列组合后，在 540 个场景下(6个数据集× 重复30次× 3个缺失率)进行比较，每对使用的算子起到正迁移的次数统计如下表所示。可见虽然所有的算子组合方式都倾向于提供正迁移，但通过 PBIC 交叉和 PWIM 突变获得的结果最好。从每个操作符相关的总数的差异来看，改变交叉操作符的影响大于突变的影响，可能是因为本文设置的交叉率较大。
消融实验
本文提出的 pMTGPDA 增加了三个主要组成部分：特征加权、实例加权、新的遗传算子。通过比较不同组件相对于 baseline 获得显著改进的数量来衡量组件的重要性，在 30% 缺失概率的情况下对每种情况重复 30 次比较，实验结果如下表所示。结果表明特征加权的改善效果最显著，实例加权组件效果最差，在大多数情况下将它们组合在一起会产生最佳性能。
优点和创新点
个人认为，本文有如下一些优点和创新点可供参考学习：
- 将迁移学习和进化计算结合，利用 MTGP 得到转换域的特征表示，适应度函数能同时考虑 SR 的性能和域之间的失配程度；
- 新型的遗传算子分别能着重关注较好和较差的 MTGP 个体树，同时又不会直接忽视其他树；
- 利用 SR 进行回归所见即所得，具有良好的可解释性；