Abstract
We consider a novel concept-learning and merging task, motivated by two use-cases. The first is about merging and compressing music playlists, and the second about federated learning with data privacy constraints. Both settings involve multiple learned concepts that must be merged and compressed into a single interpretable and accurate concept description. Our concept descriptions are logical formulae in CNF, for which merging, i.e. disjoining, multiple CNFs may lead to very large concept descriptions. To make the concepts interpretable, we compress them relative to a dataset. We propose a new method named CoWC (Compression Of Weighted Cnf) that approximates a CNF by exploiting techniques of itemset mining and inverse resolution. CoWC compresses the CNF size while also considering the F1-score w.r.t. the dataset. Our empirical evaluation shows that CoWC outperforms alternative compression approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
- 2.
References
Bharati, S., Mondal, M.R.H., Podder, P., Prasath, V.B.S.: Federated learning: applications, challenges and future directions. Int. J. Hybrid Intell. Syst. 18(1–2), 19–35 (2022)
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press (2009)
Bocklandt, S., Derkinderen, V., Vanderstraeten, K., Pijpops, W., Jaspers, K., Meert, W.: Pruning-based extraction of descriptions from probabilistic circuits (2024)
Darwiche, A.: A logical approach to factoring belief networks. In: KR, pp. 409–420. Morgan Kaufmann (2002)
Defferrard, M., Benzi, K., Vandergheynst, P., Bresson, X.: FMA: a dataset for music analysis. In: ISMIR, pp. 316–323 (2017)
Derkinderen, V., Manhaeve, R., Dos Martires, P.Z., De Raedt, L.: Semirings for probabilistic and neuro-symbolic logic programming. Int. J. Approximate Reasoning 109130 (2024)
Dua, D., Graff, C.: UCI machine learning repository (2017). http://archive.ics.uci.edu/ml
Eén, N., Biere, A.: Effective preprocessing in SAT through variable and clause elimination. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 61–75. Springer, Heidelberg (2005). https://doi.org/10.1007/11499107_5
Goyal, K., et al.: Automatic generation of product concepts from positive examples, with an application to music streaming. In: BNAIC/BENELEARN. Communications in Computer and Information Science, vol. 1805, pp. 47–64. Springer (2022)
Jabbour, S., Sais, L., Salhi, Y.: Mining to compact CNF propositional formulae. CoRR abs/1304.4415 (2013)
Jain, A., Gautrais, C., Kimmig, A., Raedt, L.D.: Learning CNF theories using MDL and predicate invention. In: IJCAI, pp. 2599–2605. ijcai.org (2021)
Korhonen, T., Järvisalo, M.: SharpSAT-TD in model counting competitions 2021-2023. CoRR abs/2308.15819 (2023)
Lagniez, J., Lonca, E., Marquis, P.: Definability for model counting. Artif. Intell. 281, 103229 (2020)
Lagniez, J., Marquis, P.: Preprocessing for propositional model counting. In: AAAI, pp. 2688–2694. AAAI Press (2014)
Lucchese, C., Orlando, S., Perego, R.: DCI closed: a fast and memory efficient algorithm to mine frequent closed itemsets. In: FIMI. CEUR Workshop Proceedings, vol. 126. CEUR-WS.org (2004)
Manthey, N.: Coprocessor - a standalone SAT preprocessor. CoRR abs/1108.6208 (2011)
Masud, C.L.H.A.S.M.: Multiple Objective Decision Making, Methods and Applications: A State-of-the-Art Survey. Springer (1979)
Michalski, R.S.: A theory and methodology of inductive learning. Artif. Intell. 20(2), 111–161 (1983)
Muggleton, S.H.: Duce, an oracle-based approach to constructive induction. In: IJCAI, pp. 287–292. Morgan Kaufmann (1987)
Rauniyar, A., et al.: Federated learning for medical applications: a taxonomy, current trends, challenges, and future research directions. IEEE Internet Things J. 11(5), 7374–7398 (2024)
Sammut, C., Webb, G.I. (eds.): Inverse Resolution, p. 558. Springer, Boston (2010)
Tseitin, G.S.: On the complexity of derivation in propositional calculus, pp. 466–483. Springer, Heidelberg (1983)
Uno, T., Kiyomi, M., Arimura, H.: LCM ver. 2: efficient mining algorithms for frequent/closed/maximal itemsets. In: FIMI. CEUR Workshop Proceedings, vol. 126. CEUR-WS.org (2004)
Vreeken, J., van Leeuwen, M., Siebes, A.: Krimp: mining itemsets that compress. Data Min. Knowl. Discov. 23(1), 169–214 (2011)
Acknowledgements
We thank the music streaming company Tunify (https://www.tunify.com/en-gb/) for discussing the use case. VD was supported by the EU H2020 ICT48 project “TAILOR” under contract #952215. This research received funding from the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme. LDR is also supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The authors have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bocklandt, S., Derkinderen, V., Kimmig, A., De Raedt, L. (2025). Approximate Compression of CNF Concepts. In: Pedreschi, D., Monreale, A., Guidotti, R., Pellungrini, R., Naretto, F. (eds) Discovery Science. DS 2024. Lecture Notes in Computer Science(), vol 15244. Springer, Cham. https://doi.org/10.1007/978-3-031-78980-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-78980-9_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-78979-3
Online ISBN: 978-3-031-78980-9
eBook Packages: Computer ScienceComputer Science (R0)