Learning Implicitly with Noisy Data in Linear Arithmetic
| Autor: | Vaishak Belle, Ionela G. Mocanu, Brendan Juba, Alexander Philipp Rader |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science Theoretical computer science Linear programming Computer Science - Artificial Intelligence Computer science Constraints and SAT Constraints and Data Mining Implicit learning Task (project management) Logic in Computer Science (cs.LO) Artificial Intelligence (cs.AI) Robustness (computer science) Benchmark (computing) Linear arithmetic Constraints and Machine Learning Heuristics Noisy data |
| Zdroj: | IJCAI Rader, A P, Mocanu, I G, Belle, V & Juba, B 2021, Learning Implicitly with Noisy Data in Linear Arithmetic . in Proceedings of 30th International Joint Conference on Artificial Intelligence (IJCAI-21) . pp. 1410-1417, 30th International Joint Conference on Artificial Intelligence, Montreal, Quebec, Canada, 19/08/21 . https://doi.org/10.24963/ijcai.2021/195 |
| DOI: | 10.48550/arxiv.2010.12619 |
| Popis: | 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. Comment: This is an extended version of our IJCAI21 paper of the same name |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|