Criticality in Formal Languages and Statistical Physics
Henry W. Lin and Max Tegmark Dept. of Physics, Harvard University, Cambridge, MA 02138 Dept. of Physics、MIT Kavli Institute, Massachusetts Institute of Technology, Cambridge, MA 02139
Abstract
We show that the mutual information between two symbols, as a function of the number of symbols between the two, decays exponentially in any probabilistic regular grammar, but can decay like a power law for a context-free grammar. This result about formal languages is closely related to a well-known result in classical statistical mechanics that there are no phase transitions in dimensions fewer than two. It is also related to the emergence of power-law correlations in turbulence and cosmological inflation through recursive generative processes. We elucidate these physics connections and comment on potential applications of our results to machine learning tasks like training artificial recurrent neural networks. Along the way, we introduce a useful quantity which we dub the rational mutual information and discuss generalizations of our claims involving more complicated Bayesian networks.
中文速览
自然语言、人类基因组和巴赫音乐中，两个符号之间的互信息（mutual information）随距离以幂律（power law）缓慢衰减，而不是指数式快速消失——这一"长程关联"现象究竟从何而来？作者从形式语言理论出发，严格证明了任何马尔可夫（Markov）或隐马尔可夫模型生成的序列，其互信息只能指数衰减，永远无法产生幂律；而概率上下文无关文法（probabilistic context-free grammar, PCFG）通过递归嵌套的生成规则，则可以自然涌现出幂律长程关联。这一数学结论与统计物理中"一维系统不存在相变"的经典定理深度对应，也与湍流、宇宙暴胀中递归过程产生幂律的机制相通。结果对机器学习有直接启示：流行的长短期记忆网络（LSTM）之所以比普通循环网络更擅长语言建模，正是因为它能一定程度上模拟上下文无关文法的递归结构、复现幂律关联，但现有LSTM仍会低估超长距离的互信息，指出了进一步改进的方向。
原文 arXiv:1606.06737;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1606.06737v3