The Symbolic Interior Point Method
The Symbolic Interior Point Method
复制标题
符号内点法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
K. Kersting
中科院分区：
文献类型：
--
作者：
Martin Mladenov;Vaishak Belle;K. Kersting
数值优化可以说是机器学习和人工智能中最突出的计算框架。它可以被视为一种汇编语言，用于解决复杂组合问题，从学习中的分类和回归，到决策理论中的最优策略和均衡计算，再到信息科学中的熵最小化。不幸的是，在涉及关系、对象和其他逻辑依赖的复杂领域中指定此类问题充其量也是繁琐的，需要大量的专业知识，而解算器需要煞费苦心地将模型简化为标准形式。为了克服这一点，我们为优化问题引入了一个丰富的建模框架，允许对符号结构进行方便的编码。我们不是将这种符号结构简化为稀疏或密集的矩阵，而是直接使用代数决策图(ADDS)来表示和利用它。将高效的基于加法的矩阵向量代数和无矩阵内点方法相结合，开发了一个能够充分利用符号表示的结构来求解凸线性和二次优化问题的引擎。我们演示了生成的符号-数字优化器在具有数百万个非零条目的决策和压缩传感任务中的灵活性。
Numerical optimization is arguably the most prominent computational framework in machine learning and AI. It can be seen as an assembly language for hard combinatorial problems ranging from classification and regression in learning, to computing optimal policies and equilibria in decision theory, to entropy minimization in information sciences. Unfortunately, specifying such problems in complex domains involving relations, objects and other logical dependencies is cumbersome at best, requiring considerable expert knowledge, and solvers require models to be painstakingly reduced to standard forms. To overcome this, we introduce a rich modeling framework for optimization problems that allows convenient codification of symbolic structure. Rather than reducing this symbolic structure to a sparse or dense matrix, we represent and exploit it directly using algebraic decision diagrams (ADDs). Combining efficient ADD-based matrix-vector algebra with a matrix-free interior-point method, we develop an engine that can fully leverage the structure of symbolic representations to solve convex linear and quadratic optimization problems. We demonstrate the flexibility of the resulting symbolic-numeric optimizer on decision making and compressed sensing tasks with millions of non-zero entries.