论文标题
用线性算术中的嘈杂数据隐式学习
Learning Implicitly with Noisy Data in Linear Arithmetic
论文作者
论文摘要
使用现实世界数据的表达语言进行鲁棒性学习仍然是一项具有挑战性的任务。许多常规方法吸引了启发式方法，而没有任何鲁棒性的保证。虽然大概是正确的（PAC）语义提供了强大的保证，但即使在命题逻辑中，学习明确表示也不是可行的。然而，关于所谓的“隐式”学习的最新工作在获得一阶逻辑片段的多项式时间结果方面表现出了巨大的希望。在这项工作中，我们扩展了PAC-音乐中的隐式学习，以线性算术语言的间隔和阈值不确定性的形式处理嘈杂的数据。我们证明，我们的扩展框架可以保证现有的多项式时间复杂性。此外，我们对迄今纯粹的理论框架进行了首次实证研究。使用基准问题，我们表明，我们学习最佳线性编程目标约束的隐式方法极大地超过了实践中明确的方法。
Robust learning in expressive languages with real-world data continues to be a challenging task. Numerous conventional methods appeal to heuristics without any assurances of robustness. While probably approximately correct (PAC) Semantics offers strong guarantees, learning explicit representations is not tractable, even in propositional logic. However, recent work on so-called "implicit" learning has shown tremendous promise in terms of obtaining polynomial-time results for fragments of first-order logic. In this work, we extend implicit learning in PAC-Semantics to handle noisy data in the form of intervals and threshold uncertainty in the language of linear arithmetic. We prove that our extended framework keeps the existing polynomial-time complexity guarantees. Furthermore, we provide the first empirical investigation of this hitherto purely theoretical framework. Using benchmark problems, we show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.
