LIPIcs.STACS.2023.38.pdf
- Filesize: 0.79 MB
- 18 pages
Document
Relating Description Complexity to Entropy
Authors
Reijo Jaakkola 
,
Antti Kuusisto ,
Miikka Vilander
-
Part of:
Volume:
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-03-03
File
Document Identifiers
Author Details
Cite AsGet BibTex
Reijo Jaakkola, Antti Kuusisto, and Miikka Vilander. Relating Description Complexity to Entropy. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.38
https://doi.org/10.4230/LIPIcs.STACS.2023.38
Abstract
We demonstrate some novel links between entropy and description complexity, a notion referring to the minimal formula length for specifying given properties. Let MLU be the logic obtained by extending propositional logic with the universal modality, and let GMLU be the corresponding extension with the ability to count. In the finite, MLU is expressively complete for specifying sets of variable assignments, while GMLU is expressively complete for multisets. We show that for MLU, the model classes with maximal Boltzmann entropy are the ones with maximal description complexity. Concerning GMLU, we show that expected Boltzmann entropy is asymptotically equivalent to expected description complexity multiplied by the number of proposition symbols considered. To contrast these results, we prove that this link breaks when we move to considering first-order logic FO over vocabularies with higher-arity relations. To establish the aforementioned result, we show that almost all finite models require relatively large FO-formulas to define them. Our results relate to links between Kolmogorov complexity and entropy, demonstrating a way to conceive such results in the logic-based scenario where relational structures are classified by formulas of different sizes.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discrete mathematics
- Theory of computation → Finite Model Theory
Keywords
- finite model theory
- entropy
- formula size
- randomness
- formula size game
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Micah Adler and Neil Immerman. An n! lower bound on formula size. ACM Trans. Comput. Log., 4(3):296-314, 2003. URL: https://doi.org/10.1145/772062.772064.
- Pablo Barceló, Mikaël Monet, Jorge Pérez, and Bernardo Subercaseaux. Model interpretability through the lens of computational complexity. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/b1adda14824f50ef24ff1c05bb66faf3-Abstract.html.
- Stephen J. Blundell and Katherine M. Blundell. Concepts in Thermal Physics. Oxford University Press, October 2009. URL: https://doi.org/10.1093/acprof:oso/9780199562091.001.0001.
- Ronald Fagin. The number of finite relational structures. Discret. Math., 19(1):17-21, 1977. URL: https://doi.org/10.1016/0012-365X(77)90116-9.
-
William Feller. An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley & Sons Inc., 1968.
- Peter Grünwald and Paul M. B. Vitányi. Shannon information and Kolmogorov complexity. CoRR, cs.IT/0410002, 2004. URL: https://doi.org/10.48550/arXiv.cs/0410002.
- Lauri Hella and Miikka Vilander. Formula size games for modal logic and μ-calculus. J. Log. Comput., 29(8):1311-1344, 2019. URL: https://doi.org/10.1093/logcom/exz025.
-
Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto, Masood Feyzbakhsh Rankooh, and Miikka Vilander. Explainability via short formulas: the case of propositional logic with implementation. In Joint Proceedings of (HYDRA 2022) and the RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, volume 3281 of CEUR Workshop Proceedings, pages 64-77, 2022.
- Sik K. Leung-Yan-Cheong and Thomas M. Cover. Some equivalences between Shannon entropy and Kolmogorov complexity. IEEE Trans. Inf. Theory, 24(3):331-338, 1978. URL: https://doi.org/10.1109/TIT.1978.1055891.
-
Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition. Texts in Computer Science. Springer, 2019.
-
Michel Loève. Probability Theory. Graduate texts in mathematics. Springer, 1963.
-
Oleg Pikhurko and Oleg Verbitsky. Logical complexity of graphs: A survey. In Martin Grohe and Johann A. Makowsky, editors, Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, Washington, DC, USA, January 5-8, 2009, volume 558 of Contemporary Mathematics, pages 129-180. American Mathematical Society, 2009.
- Alexander A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Comb., 10(1):81-93, 1990. URL: https://doi.org/10.1007/BF02122698.
- Andreia Teixeira, Armando Matos, Andre Souto, and Luis Filipe Coelho Antunes. Entropy measures vs. Kolmogorov complexity. Entropy, 13(3):595-611, 2011. URL: https://doi.org/10.3390/e13030595.
- Pasko Zupanovic and Domagoj Kuic. Relation between Boltzmann and Gibbs entropy and example with multinomial distribution. Journal of Physics Communications, 2:045002, 2018. URL: https://doi.org/10.1088/2399-6528/aab7e1.