×

zbMATH — the first resource for mathematics

Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3. (English) Zbl 1379.68279
Summary: This paper provides a gentle introduction to problem-solving with the IDP3 system. The core of IDP3 is a finite model generator that supports first-order logic enriched with types, inductive definitions, aggregates and partial functions. It offers its users a modeling language that is a slight extension of predicate logic and allows them to solve a wide range of search problems. Apart from a small introductory example, applications are selected from problems that arose within machine learning and data mining research. These research areas have recently shown a strong interest in declarative modeling and constraint-solving as opposed to algorithmic approaches. The paper illustrates that the IDP3 system can be a valuable tool for researchers with such an interest. The first problem is in the domain of stemmatology, a domain of philology concerned with the relationship between surviving variant versions of text. The second problem is about a somewhat related problem within biology where phylogenetic trees are used to represent the evolution of species. The third and final problem concerns the classical problem of learning a minimal automaton consistent with a given set of strings. For this last problem, we show that the performance of our solution comes very close to that of the state-of-the art solution. For each of these applications, we analyze the problem, illustrate the development of a logic-based model and explore how alternatives can affect the performance.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N17 Logic programming
68T05 Learning and adaptive systems in artificial intelligence
68T27 Logic in artificial intelligence
68T30 Knowledge representation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, T.; Blockeel, H.; Bogaerts, B.; Bruynooghe, M.; Denecker, M.; De Pooter, S.; Macé, C.; Ramon, J., (2012)
[2] Andrews, T.; Macé, C., Beyond the tree of texts: Building an empirical model of scribal variation through graph analysis of texts and stemmata, Literary and Linguistic Computing, 28, 4, 504-521, (2013)
[3] Baret, P.; Macé, C.; Robinson, P.; Peersman, C.; Mazza, R.; Noret, J.; Wattel, E.; Van Mulken, M.; Robinson, P.; Lantin, A-C.; Canettieri, P.; Loreto, V.; Windram, H.; Spencer, M.; Howe, C.; Albu, M.; Dress, A., The Evolution of Texts: Confronting Stemmatological and Genetical Methods, Proceedings of the International Workshop, Louvain-la-Neuve, Testing methods on an artificially created textual tradition, 255-283, (2006), Istituti editoriali e poligrafici internazionali: Istituti editoriali e poligrafici internazionali, Pisa, Italy
[4] Biermann, A. W.; Feldman, J. A., On the synthesis of finite-state machines from samples of their behavior, IEEE Transactions on Computers, 21, 6, 592-597, (1972) · Zbl 0243.94039
[5] Blockeel, H.; Bogaerts, B.; Bruynooghe, M.; De Cat, B.; De Pooter, S.; Denecker, M.; Labarre, A.; Ramon, J.; Verwer, S.; Dovier, A.; Costa, V. S., Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012), Modeling machine learning and data mining problems with FO(⋅), 14-25, (2012), Budapest, Hungary
[6] Brewka, G.; Eiter, T.; Truszczyński, M., Answer set programming at a glance, Communications of the ACM, 54, 12, 92-103, (2011)
[7] Calimeri, F.; Ianni, G.; Ricca, F.; Alviano, M.; Bria, A.; Catalano, G.; Cozza, S.; Faber, W.; Febbraro, O.; Leone, N.; Manna, M.; Martello, A.; Panetta, C.; Perri, S.; Reale, K.; Santoro, M. C.; Sirianni, M.; Terracina, G.; Veltri, P., Proceedings of the International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), The third answer set programming system competition: Preliminary report of the system competition track, 388-403, (2011), Springer: Springer, Berlin, Germany
[8] Costa Florêncio, C.; Verwer, S.; Bshouty, N.; Stoltz, G.; Vayatis, N.; Zeugmann, T., Algorithmic Learning Theory, Regular inference as vertex coloring, 81-95, (2012), Springer: Springer, Berlin, Germany · Zbl 1248.68028
[9] Coste, F.; Nicolas, J., ICML Workshop on Grammatical Inference, Automata Induction, and Language Acquisition, Regular inference as a graph coloring problem, (1997), Nashville, Tennessee
[10] De Cat, B.; Bogaerts, B.; Bruynooghe, M.; Denecker, M., (2014)
[11] De Cat, B.; Bogaerts, B.; Denecker, M.; Devriendt, J., 25th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2013), Model expansion in the presence of function symbols using constraint programming, 1068-1075, (2013), Washinton, WA
[12] De Cat, B.; Bruynooghe, M., Detection and exploitation of functional dependencies for model generation, Theory and Practice of Logic Programming, 13, 4-5, 471-485, (2013) · Zbl 1286.68042
[13] De Cat, B.; Denecker, M.; Stuckey, P.; Dovier, A.; Costa, V. S., Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012), Lazy model expansion by incremental grounding, 201-211, (2012), Wadern, Germany
[14] De Cat, B.; Denecker, M.; Stuckey, P. J.; Bruynooghe, M., (2014)
[15] De La Higuera, C., A bibliographical study of grammatical inference, Pattern Recognition, 38, 9, 1332-1348, (2005)
[16] Denecker, M.; Lierler, Y.; Truszczynski, M.; Vennekens, J.; Dovier, A.; Costa, V. S., Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012), A Tarskian informal semantics for Answer Set Programming, 277-289, (2012), Wadern, Germany
[17] Denecker, M.; Ternovska, E., A logic of nonmonotone inductive definitions, ACM Transactions on Computational Logic (TOCL), 9, 2, 1-52, (2008) · Zbl 1367.68278
[18] Denecker, M.; Vennekens, J., 14th International Conference on Principles of Knowledge Representation and Reasoning, The well-founded semantics is the principle of inductive definition, revisited, AAAI press · Zbl 0928.03033
[19] Denecker, M.; Vennekens, J.; Bond, S.; Gebser, M.; Truszczyński, M.; Erdem, E.; Lin, F.; Schaub, T., 10th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR), The second Answer Set Programming competition, 637-654, (2009), Springer: Springer, Berlin, Germany · Zbl 1175.68008
[20] Wittocx, J.; Denecker, M., International Conference on Applications of Declarative Programming and Knowledge Management, A prototype of a knowledge-based programming environment, 279-286, (2011), Springer: Springer, Berlin, Germany
[21] Devriendt, J.; Bogaerts, B.; Mears, C.; Cat, B. D.; Denecker, M., Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’12), Symmetry propagation: Improved dynamic symmetry breaking in SAT, 49-56, (2012), Athens, Greece: IEEE Press, Athens, Greece
[22] Dovier, A.; Costa, V. S., Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012), (2012), Wadern, Germany · Zbl 1253.68010
[23] Eén, N.; Sörensson, N.; Giunchiglia, E.; Tacchella, A., International Conference, SAT, An extensible SAT-solver, 502-518, (2003), Springer: Springer, Berlin, Germany · Zbl 1204.68191
[24] Erdem, E., Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning - Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday, Applications of answer set programming in phylogenetic systematics, 415-431, (2011), Springer
[25] Felsenstein, J., Inferring Phylogenies, (2004), Sinauer: Sinauer, Sunderland, MA
[26] Frisch, A. M.; Harvey, W.; Jefferson, C.; Hernández, B. M.; Miguel, I., Essence: A constraint language for specifying combinatorial problems, Constraints, 13, 3, 268-306, (2008) · Zbl 1147.68424
[27] Gambette, P., (2010)
[28] Gebser, M.; Kaufmann, B.; Neumann, A.; Schaub, T., LPNMR, clasp: A conflict-driven answer set solver, 260-265, (2007), Springer: Springer, Berlin, Germany
[29] Gelfond, M.; Lifschitz, V.; Kowalski, R. A.; Bowen, K. A., ICLP/SLP, The stable model semantics for logic programming, 1070-1080, (1988), MIT Press: MIT Press, Cambridge, MA
[30] Gold, E. M., Complexity of automaton identification from given data, Information and Control, 37, 3, 302-320, (1978) · Zbl 0376.68041
[31] Grinchtein, O.; Leucker, M.; Piterman, N.; Furbach, U.; Shankar, N., Automated Reasoning, Inferring network invariants automatically, 483-497, (2006), Springer: Springer, Berlin, Germany · Zbl 1120.68005
[32] Guns, T.; Nijssen, S.; Raedt, L. D., Itemset mining: A constraint programming perspective, Artificial Intelligence, 175, 12-13, 1951-1983, (2011) · Zbl 1353.68233
[33] Heule, M.; Verwer, S., (2010)
[34] Heule, M. J. H.; Verwer, S., Software model synthesis using satisfiability solvers, Empirical Software Engineering, (2012)
[35] Huson, D. H.; Rupp, R.; Scornavacca, C., Phylogenetic Networks: Concepts, Algorithms and Applications, (2010), Cambridge University Press: Cambridge University Press, Cambridge, UK
[36] Ierusalimschy, R.; De Figueiredo, L. H.; Celes, W., Lua - an extensible extension language, Software: Practice and Experience, 26, 6, 635-652, (1996)
[37] Jansen, J.; Jorissen, A.; Janssens, G., Compiling input* FO(⋅) inductive definitions into tabled Prolog rules for IDP3, Theory and Practice of Logic Programming, 13, 4-5, 691-704, (2013) · Zbl 1286.68047
[38] Kowalski, R. A.; Rosenfeld, J. L., IFIP Congress, Predicate logic as programming language, 569-574, (1974), North-Holland
[39] Labarre, A.; Verwer, S.
[40] Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The DLV system for knowledge representation and reasoning, ACM Transactions on Computational Logic, 7, 499-562, (2002) · Zbl 1367.68308
[41] Mariën, M.; Wittocx, J.; Denecker, M.; Bruynooghe, M.; Büning, H. Kleine; Zhao, X., SAT, SAT(ID): Satisfiability of propositional logic extended with inductive definitions, 211-224, (2008), Springer: Springer, Berlin, Germany · Zbl 1138.68547
[42] Marriott, K.; Nethercote, N.; Rafeh, R.; Stuckey, P. J.; Garcia De La Banda, M.; Wallace, M., The design of the Zinc modelling language, Constraints, 13, 3, 229-267, (2008) · Zbl 1146.68352
[43] Milner, R., A theory of type polymorphism in programming, Journal of Computer and System Sciences, 17, 3, 348-375, (1978) · Zbl 0388.68003
[44] Mitchell, D. G.; Ternovska, E.; Veloso, M. M.; Kambhampati, S., Twentieth AAAI National Conference on Artificial Intelligence (AAAI-05), A framework for representing and solving NP search problems, 430-435, (2005), MIT Press: MIT Press, Cambridge, MA
[45] Nieuwenhuis, R.; Oliveras, A.; Tinelli, C., Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T), Journal of the ACM, 53, 6, 937-977, (2006) · Zbl 1326.68164
[46] Pelov, N.; Denecker, M.; Bruynooghe, M., Well-founded and stable semantics of logic programs with aggregates, Theory and Practice of Logic Programming (TPLP), 7, 3, 301-353, (2007) · Zbl 1111.68070
[47] Roos, T.; Heikkilä, T., Evaluating methods for computer-assisted stemmatology using artificial benchmark data sets, Literary and Linguistic Computing, 24, 4, 417-433, (2009)
[48] Schulte, C.; Stuckey, P. J., Efficient constraint propagation engines, ACM Transactions on Programming Languages and Systems, 31, (2008)
[49] (2010)
[50] Swift, T.; Warren, D. S., XSB: Extending Prolog with tabled logic programming, Theory and Practice of Logic Programming, 12, 157-187, (2012) · Zbl 1244.68021
[51] Syrjänen, T.; Niemelä, I.; Eiter, T.; Faber, W.; Truszczyński, M., LPNMR, The smodels system, 434-438, (2001), Springer: Springer, Berlin, Germany · Zbl 1010.68797
[52] Timpanaro, S.; Most, G. W., The Genesis of Lachmann’s Method, (2005), University of Chicago Press: University of Chicago Press, Chicago, IL
[53] Van Gelder, A.; Ross, K. A.; Schlipf, J. S., The well-founded semantics for general logic programs, Journal of the ACM, 38, 3, 620-650, (1991) · Zbl 0799.68045
[54] Wittocx, J.; Denecker, M.; Bruynooghe, M., Constraint propagation for first-order logic and inductive definitions, ACM Transactions on Computational Logic, 14, 3, (2013) · Zbl 1353.68260
[55] Wittocx, J.; Mariën, M.; Denecker, M.; Denecker, M., The 2nd International Workshop on Logic and Search (LaSh 2008), The IDP system: A model expansion system for an extension of classical logic, 153-165, (2008), Leuven, Belgium
[56] Wittocx, J.; Mariën, M.; Denecker, M., Grounding FO and FO(ID) with bounds, Journal of Artificial Intelligence Research, 38, 223-269, (2010) · Zbl 1210.68107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.