GA and TN Decomposition

本周为了更好地理解论文的思路，我又重新回顾了学堂在线的数据挖掘课程，对一些重点知识进行了简单的记录。

The Introduction of Genetic Algorithm

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

从几十亿年前的单细胞生命体，经过漫长的自然进化，地球上最终有了像人类这样高度发达的生命体，所以说进化的威力是十分强大的。同时我们经常讨论的人工智能，其实还是基于固定的硬件和结构，它的能力会受到一定的限制。想象一下如果计算机的各类硬件能够自动的进化，那就很有可能在未来实现真正的强人工智能。

What can EAs do for us?

• Optimization
• Help people understand the envolution in nature.

What is Optimization?

• search the optimal solution from candidates based on certain performance criteria.
• Accomplish a predefined task to the highest standard

Global Optimization

Portfolio Optimization、Travelling Salesman Problem、Knapsack Problem、Bin Packing Problem、Feature Selection Problem, these questions are difficult to solve or caculate in polynomial time.

只用local search搜索最优值？容易陷入局部最优值

有parallel search，多个点同时开始进行搜索，避免陷入局部最优值

推荐一本书Blondie24：Playing at the edge of AI

Genetic Algorithm

GA算法基于生物学的背景，1975年由John Holland在论文《Adaptation in Natural and Artificial Systems》中提出，受到达尔文理论的启发，主要包含以下过程：染色体表达、杂交、变异、选择。其中涉及到的一些原则如下：

1. 将待解决的问题表示成染色体
2. 最开始的解决方案往往是随机生成的
3. 通过一代代的变异和选择，个体能够自然的进化

GA算法的主要过程如下图所示：

染色体表达

Individual（Chromosome）：表示问题的特定解决方案的一个向量，向量中的每一个值都是参数

Population：由多个个体组成，GA每次进化多个个体，通过并行搜索，进行全局最优化

Offspring：通过基因生成器生成的新的个体，希望能够有更优秀的结果

Encoding：二进制还是格雷码，如何编码TSP问题

格雷码的特点是它表示的每一个类别的编码之间只有一位的差别，而二进制0与7之间就距离很远，这不利于表达各个个体之间的并行关系。

选择

1. 轮盘法：主要是通过各个值的占比关系，来对基因进行选择，值大的被选中的机会就大，但无法处理负数
2. 等级法：将不同的取值分为不同的Rank，就像学生成绩从0-100变为ABCD一样，通过Rank的引入，能够极大的避免优质资源在一开始就过度的聚集。
3. 锦标赛选拔：每次从Individuals中选择两个或三个，对它们进行PK，PK胜利的留下继续进行遗传，失败的被淘汰。这里要注意一个问题就是每次选择的个数越多，就越容易淘汰掉有潜力的个体，当所有个体都被选择，问题就又变成了轮盘法
4. 精英选择：将后代中表现非常突出的基因保存到下一代，避免由于一两次偶尔的杂交或突变而直接丢掉。这一点就跟我们高考中的保送一样，有一部分同学成绩非常优秀，可能由于考试发挥的问题而被淘汰，因此如果有保送，那么好的基因也许能得以保留。

杂交

单点杂交：从某一处基因开始，其后A和B染色体的所有基因进行互换

两点杂交：指定两个基因，A和B染色体在两点之间的基因片段进行互换

统一性杂交（uniform crossover）：选择出要杂交的基因位置，将染色体对应位置的基因进行互换

变异

变异主要为了保证基因的多样性，如果仅仅是一些已有的基因不断杂交，可能整个群体的上限是被限定的，而通过变异这种方式引入随机性的突变，能够较好的脱离局部最优值，从而找到问题的更优解。

Evolutionary Topology Search for Tensor Network Decomposition

由于备选的solutions随着张量阶数增加指数增大，因此TN分解的最优拓扑结构是很难通过搜索解决的。但在这篇论文中，作者采用遗传算法解决这个问题。文中将复杂的拓扑结构编码为二进制字串，并且开发了遗产元算法在Hamming空间中寻找最优拓扑结构，并且通过实验结果验证了算法生成的拓扑结构相比于传统TT、TR的巨大优势。

这篇论文的张量分解方法可以应用到图片的降维处理中，HTN网络因为在张量网络层采用了TTN结构，产生了大量的参数，因此如果能够对图片进行预处理操作，从而提取一部分信息之后，再将二维的图片矩阵作为HTN的输入，那么相信模型的训练速度和效果会上升一个台阶。

Bayesian Tensor Network with Polynomial Complexity for Probabilistic Machine Learning

冉仕举老师的BTN网络，他自己定义了BTN的网络结构，类似于TTN，但是收缩过程不一样，他设计了两种结构BTN1和BTN2，并且这个BTN网络不是简单的用Adam或者SGD优化，这两种方式无法保证更新时的归一化，它自己定义了优化方式，然后跟Adam对比了一下，优点是复杂度和收敛效果。HTN参数过多就在于它采用TTN结构，进行不同层直接张量收缩时需要大量的辅助张量，来完成从2阶—>5阶—>新2阶的过渡

下面这张图是TTN网络的计算复杂度

下面这张图片是BTN的计算复杂度

可以看到两个算法的复杂度相差不大，对于HTN的优化可能没有很大的影响，但是论文给出了算法，可以借鉴参考，学习它的网络设计和自定义的反向传播算法。

目前的实验进展

本周开始上课，稍微有一些不适应，加上考试，Colab也一直断线，因此很多实验的思路和想法都被耽搁。于是就主要想再通过论文找找新的途径，主要在看那篇GA设计TN Decomposition的思路，想对数据进行个预处理，当然也可以简单的通过Tucker分解再训练，都是比较好的思路。

同时程序也写了好几版的代码，设计了一版Kfold多次交叉验证的训练方式，这样有利于处理这样的小规模样本数据。又设计了一版模型断点保存+直接多次fit的方式，来进行优化，目前的训练效果如下图所示

训练了100轮，准确率还是比较低，loss一直在降低，最小值为0.631103。但是准确率确没有大幅度上升，而是不断地波动，因此还需要继续分析原因。

Releated Links:

1. [算法]超详细的遗传算法（Genetic Algorithm）解析

2. [学堂在线80240372X]数据挖掘——进化计算（视频）

3. 详解贝叶斯张量网络（二）：概率性图像识别

4. ranshiju/BayesianTN算法代码