A constraint satisfaction approach to tractable theory induction

John Ahlgren; Shiu Yin Yuen

doi:10.1007/978-3-642-44973-4_3

A constraint satisfaction approach to tractable theory induction

^*Corresponding author for this work

City University of Hong Kong

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

A novel framework for combining logical constraints with theory induction in Inductive Logic Programming is presented. The constraints are solved using a boolean satisfiability solver (SAT solver) to obtain a candidate solution. This speeds up induction by avoiding generation of unnecessary candidates with respect to the constraints. Moreover, using a complete SAT solver, search space exhaustion is always detectable, leading to faster small clause/base case induction. We run benchmarks using two constraints: input-output specification and search space pruning. The benchmarks suggest our constraint satisfaction approach can speed up theory induction by four orders of magnitude or more, making certain intractable problems tractable. © 2013 Springer-Verlag.

Original language	English
Title of host publication	Learning and Intelligent Optimization
Subtitle of host publication	7th International Conference, LION 7, Revised Selected Papers
Publisher	Springer Verlag
Pages	24-29
Volume	7997 LNCS
ISBN (Print)	9783642449727
DOIs	https://doi.org/10.1007/978-3-642-44973-4_3
Publication status	Published - 2013
Event	7th International Conference on Learning and Intelligent Optimization, LION 7 - Catania, Italy Duration: 7 Jan 2013 → 11 Jan 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7997 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Learning and Intelligent Optimization, LION 7
Place	Italy
City	Catania
Period	7/01/13 → 11/01/13

Research Keywords

Constraint satisfaction
Inductive Logic Programming
Theory induction

Access Output

10.1007/978-3-642-44973-4_3

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Ahlgren, J., & Yuen, S. Y. (2013). A constraint satisfaction approach to tractable theory induction. In Learning and Intelligent Optimization: 7th International Conference, LION 7, Revised Selected Papers (Vol. 7997 LNCS, pp. 24-29). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7997 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-44973-4_3

Ahlgren, John ; Yuen, Shiu Yin. / A constraint satisfaction approach to tractable theory induction. Learning and Intelligent Optimization: 7th International Conference, LION 7, Revised Selected Papers. Vol. 7997 LNCS Springer Verlag, 2013. pp. 24-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{653ade2ba95e4c75857d45be52295023,

title = "A constraint satisfaction approach to tractable theory induction",

abstract = "A novel framework for combining logical constraints with theory induction in Inductive Logic Programming is presented. The constraints are solved using a boolean satisfiability solver (SAT solver) to obtain a candidate solution. This speeds up induction by avoiding generation of unnecessary candidates with respect to the constraints. Moreover, using a complete SAT solver, search space exhaustion is always detectable, leading to faster small clause/base case induction. We run benchmarks using two constraints: input-output specification and search space pruning. The benchmarks suggest our constraint satisfaction approach can speed up theory induction by four orders of magnitude or more, making certain intractable problems tractable. {\textcopyright} 2013 Springer-Verlag.",

keywords = "Constraint satisfaction, Inductive Logic Programming, Theory induction",

author = "John Ahlgren and Yuen, {Shiu Yin}",

year = "2013",

doi = "10.1007/978-3-642-44973-4_3",

language = "English",

isbn = "9783642449727",

volume = "7997 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "24--29",

booktitle = "Learning and Intelligent Optimization",

address = "Germany",

note = "7th International Conference on Learning and Intelligent Optimization, LION 7 ; Conference date: 07-01-2013 Through 11-01-2013",

}

Ahlgren, J & Yuen, SY 2013, A constraint satisfaction approach to tractable theory induction. in Learning and Intelligent Optimization: 7th International Conference, LION 7, Revised Selected Papers. vol. 7997 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7997 LNCS, Springer Verlag, pp. 24-29, 7th International Conference on Learning and Intelligent Optimization, LION 7, Catania, Italy, 7/01/13. https://doi.org/10.1007/978-3-642-44973-4_3

A constraint satisfaction approach to tractable theory induction. / Ahlgren, John; Yuen, Shiu Yin.
Learning and Intelligent Optimization: 7th International Conference, LION 7, Revised Selected Papers. Vol. 7997 LNCS Springer Verlag, 2013. p. 24-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7997 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A constraint satisfaction approach to tractable theory induction

AU - Ahlgren, John

AU - Yuen, Shiu Yin

PY - 2013

Y1 - 2013

N2 - A novel framework for combining logical constraints with theory induction in Inductive Logic Programming is presented. The constraints are solved using a boolean satisfiability solver (SAT solver) to obtain a candidate solution. This speeds up induction by avoiding generation of unnecessary candidates with respect to the constraints. Moreover, using a complete SAT solver, search space exhaustion is always detectable, leading to faster small clause/base case induction. We run benchmarks using two constraints: input-output specification and search space pruning. The benchmarks suggest our constraint satisfaction approach can speed up theory induction by four orders of magnitude or more, making certain intractable problems tractable. © 2013 Springer-Verlag.

AB - A novel framework for combining logical constraints with theory induction in Inductive Logic Programming is presented. The constraints are solved using a boolean satisfiability solver (SAT solver) to obtain a candidate solution. This speeds up induction by avoiding generation of unnecessary candidates with respect to the constraints. Moreover, using a complete SAT solver, search space exhaustion is always detectable, leading to faster small clause/base case induction. We run benchmarks using two constraints: input-output specification and search space pruning. The benchmarks suggest our constraint satisfaction approach can speed up theory induction by four orders of magnitude or more, making certain intractable problems tractable. © 2013 Springer-Verlag.

KW - Constraint satisfaction

KW - Inductive Logic Programming

KW - Theory induction

UR - http://www.scopus.com/inward/record.url?scp=84890934501&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84890934501&origin=recordpage

U2 - 10.1007/978-3-642-44973-4_3

DO - 10.1007/978-3-642-44973-4_3

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783642449727

VL - 7997 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 24

EP - 29

BT - Learning and Intelligent Optimization

PB - Springer Verlag

T2 - 7th International Conference on Learning and Intelligent Optimization, LION 7

Y2 - 7 January 2013 through 11 January 2013

ER -

Ahlgren J, Yuen SY. A constraint satisfaction approach to tractable theory induction. In Learning and Intelligent Optimization: 7th International Conference, LION 7, Revised Selected Papers. Vol. 7997 LNCS. Springer Verlag. 2013. p. 24-29. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-44973-4_3

A constraint satisfaction approach to tractable theory induction

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this