- John O. R. Aoga ORCID:orcid.org/0000-0002-7213-146X10,
- Siegfried Nijssen ORCID:orcid.org/0000-0003-2678-126610 &
- Pierre Schaus ORCID:orcid.org/0000-0002-3153-894110
Part of the book series:Lecture Notes in Computer Science ((LNPSE,volume 11802))
Included in the following conference series:
1479Accesses
Abstract
Researchers in machine learning and data mining are increasingly getting used to modeling machine learning and data mining problems as parameter learning problems over network structures. However, this is not yet the case for several pattern set mining problems, such as concept learning, rule list learning, conceptual clustering, and Boolean matrix factorization. In this paper, we propose a new modeling language that allows modeling these problems. The key idea in this modeling language is that pattern set mining problems are modeled as discrete parameter learning problems overBoolean circuits. To solve the resulting optimisation problems, we show that standard optimization techniques from the constraint programming literature can be used, including mixed integer programming solvers and a local search algorithm. Our experiments on various standard machine learning datasets demonstrate that this approach, despite its genericity, permits learning high quality models.
The first author is supported by the FRIA-FNRS (Fonds pour la Formation à la Recherche dans l’Industrie et dans l’Agriculture, Belgium).
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angluin, D.: Queries and concept learning. Mach. Learn.2(4), 319–342 (1987)
Aoga, J.O.R., Guns, T., Nijssen, S., Schaus, P.: Finding probabilistic rule lists using the minimum description length principle. In: Soldatova, L., Vanschoren, J., Papadopoulos, G., Ceci, M. (eds.) DS 2018. LNCS (LNAI), vol. 11198, pp. 66–82. Springer, Cham (2018).https://doi.org/10.1007/978-3-030-01771-2_5
Aoga, J.O.R., Guns, T., Schaus, P.: Mining time-constrained sequential patterns with constraint programming. Constraints22(4), 548–570 (2017)
Bertsimas, D., Dunn, J.: Optimal classification trees. Mach. Learn.106(7), 1039–1082 (2017)
Clark, P., Niblett, T.: The CN2 induction algorithm. Mach. Learn.3, 261–283 (1989)
Coquery, E., Jabbour, S., Saïs, L., Salhi, Y.: A SAT-based approach for discovering frequent, closed and maximal patterns in a sequence. In: ECAI (2012)
Darwiche, A.: Compiling knowledge into decomposable negation normal form. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 1999, pp. 284–289. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1999)
De Raedt, L., Zimmermann, A.: Constraint-based pattern set mining. In: Proceedings of the Seventh SIAM International Conference on Data Mining, Minneapolis, Minnesota, USA, 26–28 April 2007, pp. 237–248 (2007)
Fisher, D.H., Langley, P.: Approaches to conceptual clustering. In: Joshi, A.K. (ed.) Proceedings of the 9th International Joint Conference on Artificial Intelligence, Los Angeles, CA, USA, August 1985, pp. 691–697. Morgan Kaufmann (1985)
Gay, D., Selmaoui, N., Boulicaut, J.: Pattern-based decision tree construction. In: Second IEEE International Conference on Digital Information Management (ICDIM), Lyon, France, Proceedings, 11–13 December 2007, pp. 291–296. IEEE (2007)
Guns, T., Dries, A., Tack, G., Nijssen, S., De Raedt, L.: MiningZinc: a modeling language for constraint-based mining. In: Twenty-Third International Joint Conference on Artificial Intelligence (2013)
Guns, T., Nijssen, S., De Raedt, L.: Evaluating pattern set mining strategies in a constraint programming framework. In: Huang, J.Z., Cao, L., Srivastava, J. (eds.) PAKDD 2011. LNCS (LNAI), vol. 6635, pp. 382–394. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-20847-8_32
Guns, T., Nijssen, S., De Raedt, L.: Itemset mining: a constraint programming perspective. Artif. Intell.175(12–13), 1951–1983 (2011)
Guns, T., Nijssen, S., De Raedt, L.: k-Pattern set mining under constraints. IEEE Trans. Knowl. Data Eng.25(2), 402–418 (2013)
Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., Bengio, Y.: Binarized neural networks. In: Lee, D.D., Sugiyama, M., Luxburg, U.V., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems 29, pp. 4107–4115. Curran Associates Inc., New York (2016).http://papers.nips.cc/paper/6573-binarized-neural-networks.pdf
Kemmar, A., Lebbah, Y., Loudni, S., Boizumault, P., Charnois, T.: Prefix-projection global constraint and top-k approach for sequential pattern mining. Constraints22(2), 265–306 (2017)
Lam, H.T., Pei, W., Prado, A., Jeudy, B., Fromont, É.: Mining top-k largest tiles in a data stream. In: Calders, T., Esposito, F., Hüllermeier, E., Meo, R. (eds.) ECML PKDD 2014. LNCS (LNAI), vol. 8725, pp. 82–97. Springer, Heidelberg (2014).https://doi.org/10.1007/978-3-662-44851-9_6
Lazaar, N., et al.: A global constraint for closed frequent pattern mining. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 333–349. Springer, Cham (2016).https://doi.org/10.1007/978-3-319-44953-1_22
Meo, R., Psaila, G., Ceri, S.: A new SQL-like operator for mining association rules. In: Vijayaraman, T.M., Buchmann, A.P., Mohan, C., Sarda, N.L. (eds.) VLDB 1996, Proceedings of 22th International Conference on Very Large Data Bases, Mumbai (Bombay), India, 3–6 September 1996, pp. 122–133. Morgan Kaufmann (1996)
Michalski, R.S.: On the quasi-minimal solution of the general covering problem (1969)
Negrevergne, B., Guns, T.: Constraint-based sequence mining using constraint programming. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 288–305. Springer, Cham (2015).https://doi.org/10.1007/978-3-319-18008-3_20
Ouali, A., Loudni, S., Lebbah, Y., Boizumault, P., Zimmermann, A., Loukil, L.: Efficiently finding conceptual clustering models with integer linear programming. In: Kambhampati, S. (ed.) Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9–15 July 2016, pp. 647–654. IJCAI/AAAI Press (2016)
Ouali, A., et al.: Integer linear programming for pattern set mining; with an application to tiling. In: Kim, J., Shim, K., Cao, L., Lee, J.-G., Lin, X., Moon, Y.-S. (eds.) PAKDD 2017. LNCS (LNAI), vol. 10235, pp. 286–299. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-57529-2_23
Rudin, C., Ertekin, Ş.: Learning customized and optimized lists of rules with mathematical programming. Math. Program. Comput.10(4), 659–702 (2018)
Schaus, P., Aoga, J.O.R., Guns, T.: CoverSize: a global constraint for frequency-based itemset mining. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 529–546. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-66158-2_34
Sejnowski, T.J.: The Deep Learning Revolution. MIT Press, Cambridge (2018)
Verwer, S., Zhang, Y.: Learning optimal classification trees using a binary linear program formulation. In: 33rd AAAI Conference on Artificial Intelligence (2019)
Author information
Authors and Affiliations
ICTEAM/INGI, UCLouvain, Ottignies-Louvain-la-Neuve, Belgium
John O. R. Aoga, Siegfried Nijssen & Pierre Schaus
- John O. R. Aoga
You can also search for this author inPubMed Google Scholar
- Siegfried Nijssen
You can also search for this author inPubMed Google Scholar
- Pierre Schaus
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toJohn O. R. Aoga.
Editor information
Editors and Affiliations
INRA, Castanet Tolosan, France
Thomas Schiex
INRA, Castanet Tolosan, France
Simon de Givry
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Aoga, J.O.R., Nijssen, S., Schaus, P. (2019). Modeling Pattern Set Mining Using Boolean Circuits. In: Schiex, T., de Givry, S. (eds) Principles and Practice of Constraint Programming. CP 2019. Lecture Notes in Computer Science(), vol 11802. Springer, Cham. https://doi.org/10.1007/978-3-030-30048-7_36
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-30047-0
Online ISBN:978-3-030-30048-7
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative