Assignment 1
For the code, I have created a Google Colab Link that can be accessed online to run the Assignment 1 code I wrote.
Simulated Annealing
Intro
download. sa.drawio.png
41 总体统计结果： 成本 - 平均值: 25331.90, 标准差: 3555.19 适应度 - 平均值: 47998.57, 标准差: 18157.56 违反度 - 平均值: 1.13, 标准差: 0.88
30次运行中的最优解： 来自第 3 次运行 最优解: [7, 9, 27, 83, 109, 141, 177] 适应度: 21048.00 成本: 21048 违反度: 0
42 总体统计结果： 成本 - 平均值: 15943.73, 标准差: 2846.79 适应度 - 平均值: 79943.73, 标准差: 24185.33 违反度 - 平均值: 3.20, 标准差: 1.14
30次运行中的最优解： 来自第 6 次运行 最优解: [2, 10, 59, 110, 220, 256, 665, 1031] 适应度: 35658.00 成本: 15658 违反度: 1
43 总体统计结果： 成本 - 平均值: 16967.00, 标准差: 2358.72 适应度 - 平均值: 58967.00, 标准差: 19305.39 违反度 - 平均值: 2.10, 标准差: 0.98
30次运行中的最优解： 来自第 15 次运行 最优解: [1, 25, 93, 262, 511, 807, 887, 1034] 适应度: 17054.00 成本: 17054 违反度: 0
BGA
41 总体统计结果： 成本 - 平均值: 19645.40, 标准差: 2932.75 适应度 - 平均值: 19645.40, 标准差: 2932.75 违反度 - 平均值: 0.00, 标准差: 0.00
30次运行中的最优解： 来自第 2 次运行 最优解: [2, 12, 61, 77, 129, 140] 适应度: 14085.00 成本: 14085 违反度: 0
42 总体统计结果： 成本 - 平均值: 13397.87, 标准差: 1753.58 适应度 - 平均值: 22731.20, 标准差: 11766.78 违反度 - 平均值: 0.47, 标准差: 0.62
30次运行中的最优解： 来自第 11 次运行 最优解: [2, 10, 58, 125, 445, 630, 1063] 适应度: 11758.00 成本: 11758 违反度: 0
43 总体统计结果： 成本 - 平均值: 13696.07, 标准差: 1459.55 适应度 - 平均值: 13696.07, 标准差: 1459.55 违反度 - 平均值: 0.00, 标准差: 0.00
30次运行中的最优解： 来自第 27 次运行 最优解: [1, 80, 156, 247, 276, 800, 868, 978] 适应度: 11454.00 成本: 11454 违反度: 0
BGA Tour
41 总体统计结果： 成本 - 平均值: 24226.60, 标准差: 3539.30 适应度 - 平均值: 24893.27, 标准差: 5741.90 违反度 - 平均值: 0.03, 标准差: 0.18
30次运行中的最优解： 来自第 7 次运行 最优解: [6, 19, 30, 63, 77, 109, 135, 188, 196] 适应度: 18429.00 成本: 18429 违反度: 0
42 总体统计结果： 成本 - 平均值: 15219.53, 标准差: 2421.34 适应度 - 平均值: 55886.20, 标准差: 18963.77 违反度 - 平均值: 2.03, 标准差: 0.91
30次运行中的最优解： 来自第 22 次运行 最优解: [2, 10, 59, 62, 255, 701, 908] 适应度: 16812.00 成本: 16812 违反度: 0
43 总体统计结果： 成本 - 平均值: 16960.13, 标准差: 2312.79 适应度 - 平均值: 35626.80, 标准差: 15520.77 违反度 - 平均值: 0.93, 标准差: 0.77
30次运行中的最优解： 来自第 3 次运行 最优解: [1, 78, 157, 159, 661, 754, 896, 1017] 适应度: 14660.00 成本: 14660 违反度: 0
IBGA
总体统计结果： 成本 - 平均值: 11307.00, 标准差: 0.00 适应度 - 平均值: 11307.00, 标准差: 0.00 违反度 - 平均值: 0.00, 标准差: 0.00
30次运行中的最优解： 来自第 1 次运行 最优解: [1, 11, 61, 77, 140] 适应度: 11307.00 成本: 11307 违反度: 0
相似性和差异
相似性：
- 原动力：都是为了兼顾可行解和质量，为了防止定义的fitness出现过惩罚和欠惩罚的情况，从而太早收敛于local minimum或者偏离可行区域。
- 处理方法：都考虑了代价函数以及惩罚函数两个指标，保留了一定的不可行解，从而避免过早失去有潜力但不可行的解。
不同性：
- 是否为随机算法。Ranking Replacement是一种将已有解划分为四个子组，通过子组是否存在以及规定次序从而确定性地决定放弃哪个解的方法，而Stochastic Ranking是一种基于概率p比较cost function，基于概率1-p比较惩罚函数的随机算法，需要给出超参数p
- 作用的场合不同。Stochastic Ranking给出一个排名，至于选择哪些个体作为下一代并没有规定，而Ranking Replacement是一个规定了如何选择，放弃下一代的算法。
由于在Air Crew Scheduling Problems这一问题为寻找最小值问题，且我使用了二进制编码来表示解决方法，所以这将成为以下描述的上下文。首先，对于模拟退火，我们需要定义两个算子，一个是生成初始解，另一个是寻找邻居解。对于初始解，我先将每一位设置为0，并以概率P来将其flip为1. 对于生成另据解，我选择随机flip当前解的一bit。 在得到初始解后，如果没有到达设定的最高迭代次数，那么就生成一个邻居解，接下来比较二者的fitness。在模拟退火中，我将fitness函数设置为： f(x) = cost(x) + 20000 \mul panalty(x) 我们以概率Pf来接受新解，Pf定义为 Pf = exp(f(current) - f(neighbor) / T)， 这代表着如果新解的fitness小于现有解，那么新解会立刻被接受。如果新解的fitness大于现有解，那么也有一定概率被接受，只不过随着温度降低，概率变低。这在搜索前期增加了搜索范围，在搜索后期不会跳出较优范围。这个循环不断进行，直到达到设定的最高迭代次数，算法结束。
Standard binary genetic algorithm表示使用二进制编码作为gynotype的进化算法。由于未指定选择的算子，所以我实现了truncate selection和tournament selection两个变种。BGA的流程图在Figure 2，我将通过流程图来讲解本算法。
首先，我们通过运行population size次initialization生成算法来获得初始种群。这个initialization算法和模拟退火中用到的方法一样。接下来，进入循环，我们通过种群中fiteness的计算结果来选出parents，再通过施加交叉互换和突变算子产生子代，接下来再次计算种群以及子代的fitness进行排序，选择前population size的个体生成新种群，然后继续循环，直到迭代次数达到或其他条件达到退出循环，最后种群中fitness第一的就是搜索结果。
对于truncate selection，就是对种群中个体fitness排序后选择前population_size作为父代。对于tournament selection，就是每次从种群中采样k个个体，选出fitness最佳的个体作为父代。
Improved BGA是指采用pseudo-random initialisation method进行初始种群生成，使用stochastic ranking method进行排序并使用heuristic improvement operator对生成的子代进行repair的BGA算法。由于算法框架大致与BGA相同，所以我将着重介绍这三个算子。
首先是pseudo-random initialisation method。这个算法的一个精髓就是建立了矩阵alpha_i来建立能覆盖行i的列j的检索。其思想是，每次随机选择一个未被覆盖的行i，也就是未被已有机组cover的地点，来选择一个既能覆盖行i，又不和当前已选择列j冲突的新列，不断重复，直到找不到这样的列。另外在选择i和j的时候都有随机性，所以这也是一个随机算法。
接下来是stochastic ranking method。这个算法就像是一个改良版的冒泡排序。其思想是，为了防止过惩罚和欠惩罚，于是在对个体排序的时候，同时考虑cost funciton以及惩罚函数。具体来说，若二者都不违反约束，就直接比较cost function，否则，其基于概率p比较cost function，基于概率1-p比较惩罚函数，从而排序。p是超参数，对于循环次数，也是一个超参数。
最后是heuristic improvement operator。这个算子用来修复因突变和交叉互换产生的子代违反太多约束导致质量差，欠覆盖或过覆盖的问题。其思想是，通过DROP和ADD过程来防止过覆盖和欠覆盖。对于产生的子代，随机选择其覆盖的列，如果对于这一列，存在其覆盖的行过覆盖了，那就删除这个列。这就是DROP过程。DROP之后可能会产生更多的欠覆盖，所以进行ADD。对于所有未被覆盖的行，从所有列中试图找出满足它覆盖的行都还没被覆盖的列集合，并使用贪心策略（cost / 覆盖行数）来选择列加入解中。这样，产生的解要么是所有行只覆盖一遍，要么是欠覆盖，不会出现过覆盖的现象。
可以看到，对比三个算法，收敛速度 IBGA > BGA > SA，最后的结果，Cost IBGA > BGA > SA，Violation IBGA > BGA > SA，运行速度 SA > BGA > IBGA。
SA与BGA使用同种初始化方法，也使用了同种fitness函数，但BGA的收敛快于SA，证明了在规模较大，较复杂的问题上，进化算法相比模拟退火的优势。然而，
在本节，我们将对三种算法的结果进行对比与讨论。首先，Table 1-4展示了三种算法在3个benchmark上30次独立运行结果的平均值与标准差。其次，我们绘制了三种算法的收敛曲线，如Figure 1-4。
对于解的质量，IBGA > BGA > SA。具体来说，IBGA可以做到0 violation，且Cost最低。注意到IBGA在三个数据上一开始就做到了0 violation，这体现了伪随机初始化提供了优秀的起点。而更低的Cost也体现了启发式修补结果以及随机排序的贡献。而BGA在小规模（sppnw41）的数据上可以做到0 violation，但是在较大的数据上（42 43）就难以做到，其Cost处于中间，优于模拟退火但劣与IBGA。而虽然和BGA使用同样的fitness函数以及初始解生成方法，但效果最差，Cost较高，Violation也比较高。
对于收敛速度，IBGA > BGA > SA。实际上，由于使用了伪随机初始化，IBGA的起点明显优于其他两种方法。另外，我发现IBGA总是收敛到同一个结果上。对于BGA，收敛快于SA，这也体现了以种群为单位搜索的优势。而SA的收敛速度最慢，震荡也很严重。
对于时间，进行一次搜索，速度SA > BGA > IBGA。进化算法由于需要维持一个种群，所以慢于SA很正常。IBGA慢于BGA是因为，其中间要对解进行修补，并且随机排序可能需要多轮，所以更慢。但从整体上看，收敛到最小值的速度，IBGA>BGA>SA，这也进一步说明了IBGA每次搜索质量更高。
解的质量：IBGA > BGA > SA
从实验结果来看，IBGA 在所有测试数据上都表现出最优的解质量，能够保证所有约束被满足，同时 Cost 也最低。相比之下，BGA 的解质量次之，在小规模数据集（如 sppnw41）上能够达到 Violation = 0，但在较大规模问题（如 sppnw 42, 43）上难以保证所有行都被覆盖，导致 Violation 偏高，Cost 也高于 IBGA。而 SA 由于其单点搜索策略，解的质量最差，既无法有效降低 Violation，也无法找到较低的 Cost。IBGA 之所以在解的质量上占据明显优势，主要得益于三个关键点：首先，伪随机初始化提供了一个质量较高的初始种群，使得 IBGA 在优化过程中能从更优的起点开始搜索；其次，启发式修补算子在进化过程中能够主动修正违反约束的解，使得 IBGA 更容易找到可行解，并在 Cost 和覆盖性之间取得平衡；最后，随机排序的引入打破了固定的选择顺序，使得搜索空间更加多样，避免了早熟收敛，提高了解的全局质量。这些改进使得 IBGA 在所有实验数据上都找到了 Cost 最低、Violation = 0 的最优解，远超 BGA 和 SA。
收敛速度：IBGA > BGA > SA
从收敛趋势来看，IBGA 的优化过程最快，能够在更少的迭代次数内找到最优解，而 BGA 次之，SA 则收敛最慢且震荡较大。IBGA 之所以收敛速度快，关键在于伪随机初始化带来的优质起点，使得它从第一代开始便具备较强的解质量，而不需要过多的迭代来修正 Violation。有趣的是，伪随机初始化带来的起点质量，甚至比SA搜索结果质量更高。同时，启发式修补算子能够快速消除不满足约束的解，使得 IBGA 在较少的世代内便能将 Violation 降为 0，并通过贪心策略找到更优的 Cost。而 BGA 由于没有使用伪随机初始化，初始解质量较低，需要更多代数来优化 Violation，因此收敛速度较 IBGA 慢，但仍然明显快于 SA。SA 由于仅依赖邻域搜索，没有群体进化的优势，因此收敛速度最慢，并且由于概率接受机制的存在，解的质量在前期会出现较大的波动。即使在收敛阶段，SA 仍然可能因较大的搜索步长而出现震荡，导致它不仅收敛慢，而且稳定性较差。相比之下，IBGA 在所有测试数据上始终收敛到同一个最优解，表现出极高的稳定性，而 BGA 可能会在不同的运行中收敛到不同的局部最优解，而 SA 由于其高温阶段的随机扰动，每次运行得到的解都可能有较大差异。
计算时间：SA > BGA > IBGA
如果单纯从单次搜索的计算开销来看，SA 的计算时间最短，BGA 居中，而 IBGA 最长。然而，若考虑到最终收敛到最优解所需的时间，IBGA 反而是最快的。SA 由于只维护一个解，每次迭代只进行简单的邻域搜索，因此计算时间最低，但由于它收敛极慢，整体优化时间较长。BGA 由于种群进化的特点，每一代都需要进行交叉、变异、选择等操作，因此计算时间高于 SA，但由于它比 SA 具有更快的收敛速度，最终在整体优化时间上要比 SA 更具优势。而 IBGA 在 BGA 的基础上增加了启发式修补和随机排序，这两个过程都会增加计算时间，使得单次搜索成本更高，但由于 IBGA 本身的收敛速度快，可以在较少的迭代次数内找到最优解，因此总收敛时间仍然优于 BGA 和 SA。综合来看，SA 在单次搜索时间上最有优势，但由于收敛缓慢，在大规模问题上并不适用；BGA 计算开销适中，但收敛速度受限于初始种群的质量；IBGA 虽然单次计算时间最高，但能在最少的代数内找到最优解，使得它在总收敛时间上最具优势。因此，若追求计算效率并允许一定的计算开销，IBGA 是最优选择；若希望在计算时间较短的情况下找到次优解，BGA 仍然是一个合理的选择；而 SA 由于收敛慢、解质量差，仅适用于计算资源极度受限且无需高质量解的情况。】
recurrent名字 解释一下 修改了文章内容避免误解 补上rnn tx不是核心思想，只是拿来用 TDModule、递归结已经被蕴含 模型预测结果是一个离散点的分布，点建模成轨迹。 加法 加上去 没开源 不知道怎么初始化的 没有公开代码 实验设定不一样 顶级会议 自己跑的 开源的 训练 硬件 训练时间 对于视屏的工作 最新就是21 为了弥补gap 我甚至给static家了rnn 时间差分不新？做gaze时序的工作 这是一个新的工作 传统的方法把不同帧之间扔到rnn里，本文关注了针尖特征的差异，循环网络结构捕获运动信息，输出结果的对齐 其他领域被用 但是gaze没有用过 时间差分只是一种提取振间差异的方法 改进 说明怎么融合 循环名字改一下 Transformer 的超参数对模型性能的影响页数限制 Transformer-based gaze estimation DTW, Wasserstein Loss 尽力搜索多媒体会议以及CV会议 光流
问题
R5
%% 1. 消融实验不够：实际上TDMoudle与递归结构的消融结果即为FaceNet，所以已经蕴含在了实验结果对比中。对于Transformer的消融结果，我们进行了实验，但由于篇幅限制没放下。结果如下，我们将对论文进行修改。 %% %% 1. 我们理解审稿人对 PDA Loss 命名的疑问。我们的 PDA Loss 本质上是对预测 gaze 轨迹点的对齐，而非传统的概率分布对齐。 由于 gaze 轨迹点是离散的，并非概率密度分布，因此“分布对齐”指的是将这些点建模为轨迹，在这一层面对齐，而非 Wasserstein Loss 计算的概率分布距离。 %%
- 加法操作只有一个输入：我们感谢审稿人的细致观察。图中展示的是 TDModule 提取的运动特征加回到原始图像特征，从特征的花纹是可以看出的。我们将优化图示，使其更清晰。
- 对于其认为[26]结果错，我认为它对于我们的工作有一些误解，这是由于我们的的模型在对齐点分布时需要用到人头与屏幕坐标，而所以只在Eyediap以屏幕为目标的数据上进行了测试。我们复现并测试了所有的对比模型，而在我们的测试环境下，[26]的结果的确为5.22。
- 对于其认为有一篇paper在eyediap结果更好而我们没法引用，由于Eyediap并未提供标准的dataloader，这篇文章的作者与我们采用了不同的pre-processing方法，所以无法直接比较，而作者并未开源其代码，导致我们无法复现。所以其结果无法直接进行比较。
R6
- %% 模型的训练时间 %%、所需硬件，计算复杂性，算一下。 %% 2. 代码实现的可访问性：将会开源代码。 %% %% 2. 文献旧：我们已经尽力寻找了近年多媒体和CV领域处理gaze的paper。尽管以静态图片作为输入的新paper有很多，以动态视频为输入的paper很少。我们已经尽力选择一些视频gaze方法，以及一些静态方法。我们还为静态方法添加了bi-LSTM和Transformer来增加与我们方法的对比性。 %%
R7
- 认为TDMoudle不够新：一方面，在video gaze领域，传统方法通常 直接将图像特征输入 RNN 进行处理，而而我们的 TDModule 通过 时间差分提取帧间运动特征，再结合递归结构进行特征融合，这是 gaze estimation 领域较新的做法。此外，我们不仅仅是简单使用时间差分，而是将其与层级特征融合，并在输出端进行轨迹对齐，这与以往方法不同。
- The use of recurrent structures, such as LSTMs and GRUs, to process sequential data in video-based tasks is a common practice. 这位审稿人可能误解了我们recurrent名字的用意。我们通过循环设计，在不同层次将运动特征融入到图像特征中，这与传统意义上的RNN中的recurrent并无联系。
- %% 参数数量、 FLOPs （浮点运算）或内存需求：分析。 %% %% 5. 没对Transformer和TDModule消融？鉴于计算资源的限制以及研究的重点，我们的研究重点不在于研究参数量对于模型的影响，分析的架构选择更为重要。然而，这样的实验是十分易于进行的，我们同意增加实验。 %%
R8
- %% 近期sota：已经说过了 %% %% 10. PDA Loss 没有与其他轨迹对齐损失，如提到的Wasserstein Loss，实际上，这种Loss是用于计算两个概率分布而非点分布的距离的，与本文的Point Distribution概念不同，无法比较。我们认为给出的对于 PDA Loss的消融实验已经足以证明其有效性 %%
- %% 推理时间和内存消耗 %%：推理时间可以实时运行，内存消费显卡，如4060已经可以带动
- EFE表现不如FaceNet-GRU 2020，这是因为，FaceNet-GRU由于有GRU利用视频时序信息，而EFE只利用单帧图像信息，FaceNet-GRU优于EFE很正常。我们没有为EFE添加时序处理模块是因为其并未公开代码，无法复现，论文里已经指出了。
- 对于Transformer与各种RNN变体的对比：我们认为这不是我们工作的重点，其实已经做了研究。
- %% 可重复性：我们会开源的 %%
FLOPs: 174071.85M Params: 14.89M
消融
R5: 1. 消融实验不够：实际上TDMoudle与递归结构的消融结果即为FaceNet，所以已经蕴含在了实验结果对比中。对于Transformer的消融结果，我们进行了实验，但由于篇幅限制没放下。结果如下，我们将对论文进行修改。 R7 5. 没对Transformer和TDModule消融？对于Transformer的消融实验已补充，对于TDModule我们也与ResNet进行了消融对比。对于TDModule内部，我们的研究重点不在于研究参数量对于模型的影响，分析的架构选择更为重要。然而，这样的实验是十分易于进行的，我们同意增加实验。
实际上TDMoudle与循环结构的消融结果即为FaceNet，已经蕴含在了实验结果对比中。而对于Transformer的消融我们也已经补充。对于TDModule的参数调整以及Transoformer的参数调整，我们认为我们的研究重点不在于研究参数量对于模型的影响，分析整体的架构选择更为重要。
开源
R6: 2. 代码实现的可访问性：将会开源代码。 R8: 6. 可重复性：我们会开源的
PDA Loss
R5: 1. 我们理解审稿人对 PDA Loss 命名的疑问。我们的 PDA Loss 本质上是对预测 gaze 轨迹点的对齐，而非传统的概率分布对齐。 由于 gaze 轨迹点是离散的，并非概率密度分布，因此“分布对齐”指的是将这些点建模为轨迹，在这一层面对齐，而非 Wasserstein Loss 计算的概率分布距离。 R8: 10. PDA Loss 没有与其他轨迹对齐损失，如提到的Wasserstein Loss，实际上，这种Loss是用于计算两个概率分布而非点分布的距离的，与本文的Point Distribution概念不同，无法比较。我们认为给出的对于 PDA Loss的消融实验已经足以证明其有效性
参数
R6 4. 模型的训练时间、所需硬件，计算复杂性，算一下。 R7 参数数量、 FLOPs （浮点运算）或内存需求：分析。 R8 7. 推理时间和内存消耗：推理时间可以实时运行，内存消费显卡，如4060已经可以带动
文献旧
R6: 2. 文献旧：我们已经尽力寻找了近年多媒体和CV领域处理gaze的paper。尽管以静态图片作为输入的新paper有很多，以动态视频为输入的paper很少。我们已经尽力选择一些视频gaze方法，以及一些静态方法。我们还为静态方法添加了bi-LSTM和Transformer来增加与我们方法的对比性。 R8 近期sota：已经说过了
We appreciate the reviewer’s perspective. In the video gaze estimation domain, traditional methods typically directly input image features into an RNNs for processing. In contrast, our TDModule explicitly extracts inter-frame motion features using temporal differencing, which is then integrated with a recurrent structure at different levels for feature fusion. This is a relatively novel approach in video gaze estimation. Moreover, our method goes beyond simple temporal differencing by integrating hierarchical feature fusion and aligning outputs at the trajectory level, setting it apart from prior work.
Larry Shi