[ML&DL]基于图的目标函数分解策略
这个课题的想法是：将高维目标函数分解，通过在子目标函数之间建立通信来解决子目标函数的变量冲突，从而达到全局最优(次优)。这是我在知乎上的提问，还没有得到有价值的回答。
问题的关键在于如何计算(有效解决冲突)?但是这里总结一下我做的工作，目标函数分解的工作。关于如何计算，老板说了不让我做，因为那是师兄师姐的博士课题(PSO)。不过我可以做其他的优化算法，但是是否收敛？收敛后的gap的bound怎样？都是没有研究的问题。
首先如何用图表示? 将原目标函数展开成sum求和形式，每一个term用一个node来表示，两个node之间的边用term的共享变量来表示。
为什么以及如何分割? 通过分割可以将高维优化问题转化为低维优化，个人认为如何分割和如何计算有着密切联系。可能想到的一种方式是优化每个子目标函数，然后同步变量来解决冲突，直至全局最优，那么同步变量就要涉及子目标的通信开销。
如何最小化通信开销? 用边上共享变量的个数当做边的权值，这个问题可以转化为图聚类的问题。减少通信也就意味着子目标函数之间的依赖关系越少越好，但是同时要满足负载均衡，负载均衡是多机环境下提高资源利用率的重要方法。
假设不考虑负载均衡，有两种目标函数可选(为了保证严格定义，直接来源metis的官方文档)：
1.最小化割集
Consider a graph G = (V, E), and let P be a vector of size |V | such that
P [i] stores the number of the partition that vertex i belongs to. The
edgecut of this partitioning is defined as the number of edges that
straddle partitions. That is, the number of edges (v, u) for which P [v]
!= P [u]. If the graph has weights associated with the edges, then the
edgecut is defined as the sum of the weight of these straddling edges.
2.最小化通信代价
Consider a graph G = (V, E), and let P be a vector of size |V | such that
P [i] stores the number of the partition that vertex i belongs to. Let Vb
belongs to V be the subset of interface (or boarder) vertices. That is,
each vertex v belongs to Vb is connected to at least one vertex that
belongs to a different partition. For each vertex v belongs to Vb let Nadj[
v] be the number of domains other than P[v] that the vertices adjacent to
v belong to.The totalv of this partitioning is defined as:
totalv = Sum{Nadj[v]| v belongs to Vb}.
不严格的说，edgecut以edge为研究对象，意味着砍掉多少条边可以将原目标函数分开，communication volume意味着在不同子目标函数之间进行通信需要多少通信量。communication volume以node为研究对象，可能存在edgecut的重复计算。
关于图分割有很多研究成果，在metis中有两种分割方式，不过二者是类似的想法。
应用Bisection，可以得到K-way的分割方式，如下：
从上图可以看出，分为三个阶段(metis的实现中，每个阶段都有相应的多种算法)：
1.coarsening: 直观上的表达是提取图的骨骼，方式是用一个node表示多个node。典型地如下：
2.initial partitioning: 本阶段，原问题被转换为一个小图的谱聚类问题。
3.uncoarsening: 还原，注意在还原的过程中要纠正在小图中的分割结果，原因是小图还原为大图的过程中，大图的度明显增多，可能找到更优的解，也就是上图中我们看到的refined partition。
至此，结束。
总结: 个人还是比较期待基于这种目标函数的分解方式在计算上的表现的，但是首先要解决的问题是收敛性的分析。针对分解的工作本文回答了intuition，what，why，how的问题，在具体实现上，自己写了目标函数符号计算的模块，也就是建立目标函数的图表示，然后将分割交给了metis来完成，做了300维和1000维的Rosenbrock目标函数分解的工作，1000维下耗时300s(符号分解+画图+分解+python)，故在计算时间上还是比较快。
参考:
1.Four graph partitioning algorithms
比较详细的总结了目前主流的图分割算法。
简单介绍了各种图划分的方法同时给出了主流的图划分库。
3.图分割软件集合
（This wrapper uses a few environment variables!!!）
Wrapper for the METIS library for partitioning graphs (and other stuff). This library is unrelated to PyMetis, except that they wrap the same library. PyMetis is a Boost Python extension, while this library is pure python and will run under PyPy and interpreters with similarly compatible ctypes libraries.
详细的讨论了PowerGraph的话题，包含两个方面GAS Decomposition和Vertex Partitioning.
主要用于符号计算，目标函数的展开。
对多目标优化建立一个直观的认识。
谱聚类在三种目标函数下的处理，令人感动的数学。