Zenil Hector, Kiani Narsis A, Tegnér Jesper
Information Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, SciLifeLab, Karolinska Institute, Stockholm 171 76, Sweden; Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom; and Algorithmic Nature Group, LABoRES, Paris 75006, France.
Information Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, SciLifeLab, Karolinska Institute, Stockholm 171 76, Sweden and Algorithmic Nature Group, LABoRES, Paris 75006, France.
Phys Rev E. 2017 Jul;96(1-1):012308. doi: 10.1103/PhysRevE.96.012308. Epub 2017 Jul 7.
In estimating the complexity of objects, in particular, of graphs, it is common practice to rely on graph- and information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which an object, such as a graph, can be described or observed. From observations that can reconstruct the same graph and are therefore essentially translations of the same description, we see that when applying a computable measure such as the Shannon entropy, not only is it necessary to preselect a feature of interest where there is one, and to make an arbitrary selection where there is not, but also more general properties, such as the causal likelihood of a graph as a measure (opposed to randomness), can be largely misrepresented by computable measures such as the entropy and entropy rate. We introduce recursive and nonrecursive (uncomputable) graphs and graph constructions based on these integer sequences, whose different lossless descriptions have disparate entropy values, thereby enabling the study and exploration of a measure's range of applications and demonstrating the weaknesses of computable measures of complexity.
在估计对象（特别是图）的复杂性时，通常的做法是依赖于图论和信息论的度量。在此，我们使用具有诸如博雷尔正态性等性质的整数序列，来解释这些度量如何并非独立于对象（如图）的描述或观察方式。从能够重构同一图的观察结果（因此本质上是同一描述的不同形式）可以看出，当应用诸如香农熵这样的可计算度量时，不仅有必要在存在感兴趣特征时预先选择该特征，而在不存在时进行任意选择，而且诸如将图的因果似然性作为一种度量（与随机性相对）这样更一般的性质，可能会被诸如熵和熵率这样的可计算度量极大地误表示。我们基于这些整数序列引入递归和非递归（不可计算）图以及图构造，其不同的无损描述具有不同的熵值，从而能够研究和探索一种度量的应用范围，并展示可计算复杂性度量的弱点。
