提出可计算的局部组合复杂度，识别数据中是否隐藏人类可读信息。
Local Compositional Complexity: How to Detect a Human-readable Messsage
- 将数据最短描述分为结构与无结构部分，以结构部分大小衡量复杂度
- 实验验证可区分语音、图像、文本中的有意义信号与噪声或重复信号
- 适用于检测外星信号是否含消息，也可用于物理系统宏观态客观刻画
数据复杂度是自然科学及相关领域的重要概念，但缺乏严格且可计算的定义。本文聚焦一种特定复杂度：若数据具有可传达信息的结构，则复杂度高。人类语言、文字、图表和照片属高复杂度，而均匀或随机数据为低复杂度。本文提出一个通用框架，通过将数据最短描述划分为结构化与非结构化部分，以结构部分大小作为复杂度评分。该框架在统计力学中可实现对物理系统宏态和熵的更客观刻画。进一步，提出‘局部组合性’作为适合人类通信的特定结构，导出更精确、可计算的定义。实验表明，该方法可在听觉、视觉和文本领域有效区分有意义信号与噪声或重复信号，有望用于判断外星信号是否包含消息。
原文摘要 · Abstract (English)
Data complexity is an important concept in the natural sciences and related areas, but lacks a rigorous and computable definition. In this paper, we focus on a particular sense of complexity that is high if the data is structured in a way that could serve to communicate a message. In this sense, human speech, written language, drawings, diagrams and photographs are high complexity, whereas data that is close to uniform throughout or populated by random values is low complexity. We describe a general framework for measuring data complexity based on dividing the shortest description of the data into a structured and an unstructured portion, and taking the size of the former as the complexity score. We outline an application of this framework in statistical mechanics that may allow a more objective characterisation of the macrostate and entropy of a physical system. Then, we derive a more precise and computable definition geared towards human communication, by proposing local compositionality as an appropriate specific structure. We demonstrate experimentally that this method can distinguish meaningful signals from noise or repetitive signals in auditory, visual and text domains, and could potentially help determine whether an extra-terrestrial signal contained a message.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。