论文标题
图形未成年人满足机器学习：障碍的力量
Graph Minors Meet Machine Learning: the Power of Obstructions
论文作者
论文摘要
数十年来，计算上的棘手性促进了大量主要旨在优质折衷的方法的发展。机器学习技术的使用最终成为获得$ {\ cal np} $的近似解决方案的可能工具之一 - 硬组合优化问题。在最近的文章中，Dai等人。引入了一种用于计算顶点覆盖问题实例的近似解决方案的方法。在本文中，我们考虑通过考虑称为“障碍物”的特殊问题实例选择适当的培训策略的有效性，我们认为我们本身具有某些内在特性。利用Dai等人的最新工作。关于顶点覆盖问题，并使用相同的案例研究以及其他19个问题实例，我们显示了使用障碍物训练神经网络的实用性。实验表明，障碍物的训练会导致收敛所需的迭代次数大大减少，从而大大减少了训练模型所需的时间。
Computational intractability has for decades motivated the development of a plethora of methodologies that mainly aimed at a quality-time trade-off. The use of Machine Learning techniques has finally emerged as one of the possible tools to obtain approximate solutions to ${\cal NP}$-hard combinatorial optimization problems. In a recent article, Dai et al. introduced a method for computing such approximate solutions for instances of the Vertex Cover problem. In this paper we consider the effectiveness of selecting a proper training strategy by considering special problem instances called "obstructions" that we believe carry some intrinsic properties of the problem itself. Capitalizing on the recent work of Dai et al. on the Vertex Cover problem, and using the same case study as well as 19 other problem instances, we show the utility of using obstructions for training neural networks. Experiments show that training with obstructions results in a huge reduction in number of iterations needed for convergence, thus gaining a substantial reduction in the time needed for training the model.
