مقاله Construction and learnability of canonical Horn formulas : تی پی بین

خلاصه مقاله

We describe an alternative construction of an existing canonical representation for definite Horn theories, the Guigues-Duquenne basis (or GD basis), which minimizes a natural notion of implicational size. We extend the canonical representation to general Horn, by providing a reduction from definite to general Horn CNF. Using these tools, we provide a new, simpler validation of the classic Horn query learning algorithm of Angluin, Frazier, and Pitt, and we prove that this algorithm always outputs the GD basis regardless of the counterexamples it receives.

نویسندگان

Marta Arias [ LARCA Research Group, Departament LSI, Universitat Politècnica de Catalunya, Barcelona, Spain ]

José L. Balcázar [ Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, Santander, Spain ]

کلمات کلیدی

Query learning Horn formulas Canonical representation

آدرس این مقاله

آدرس مستقیم دسترسی به این مقاله

مشخصات کنفرانس

مشاهده مقالات

Machine Learning 2013

Machine Learning is an international forum for research on computational approaches to learning. The journal publishes articles reporting substantive results on a wide range of learning methods applied to a variety of learning problems. The journal features papers that describe research on problems and methods, applications research, and issues of research methodology. Papers making claims about learning problems or methods provide solid support via empirical studies, theoretical analysis, or comparison to psychological phenomena. Applications papers show how to apply learning methods to solve important applications problems. Research methodology papers improve how machine learning research is conducted. All papers describe the supporting evidence in ways that can be verified or replicated by other researchers. The papers also detail the learning component clearly and discuss assumptions regarding knowledge representation and the performance task.

حوزه های تحت پوشش : Artificial Intelligence, Control, Robotics, Mechatronics, Computing Methodologies,Simulation and Modeling