Probably approximately correct learning of Horn envelopes from queries
| Autor: | Sergei Obiedkov, Daniel Borchmann, Tom Hanika |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Computer Science - Logic in Computer Science Computer Science - Artificial Intelligence 0211 other engineering and technologies Probably approximately correct learning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Oracle Machine Learning (cs.LG) Formal concept analysis Discrete Mathematics and Combinatorics F.4.1 I.2.6 Equivalence (formal languages) Mathematics Applied Mathematics 021107 urban & regional planning Logic in Computer Science (cs.LO) Exponential function Artificial Intelligence (cs.AI) TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics Ask price 03G10 68T27 Algorithm |
| Zdroj: | Discrete Applied Mathematics. 273:30-42 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.02.036 |
| Popis: | We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain. 21 pages, 1 figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect