论文标题
线性添加剂Markov过程的熵率
The entropy rate of Linear Additive Markov Processes
论文作者
论文摘要
这项工作为线性添加剂Markov过程（LAMP）的熵提供了一个理论值，这是一种能够使用给定自相关结构生成序列的表达模型。虽然一阶马尔可夫链模型通过在当前状态下进行条件来生成新值，但灯模型根据某些不必界限的分布将过渡状态从序列的历史记录中。灯模型捕获了与高阶马尔可夫过程相似的数据中的复杂关系和远程依赖性。虽然高阶马尔可夫过程具有多项式参数空间，但灯模型仅以概率分布和下层一阶马尔可夫链的过渡矩阵为特征。我们证明，灯的理论熵速率等同于基础一阶马尔可夫链的理论熵率。这一令人惊讶的结果是通过选择灯过渡状态的随机过程引入的随机性来解释的，并为数据中的复杂依赖性建模，同时保留有用的理论结果。我们使用灯模型来估计LastFM，Brightkite，WikisPeedia和Reuters-21578数据集的熵率。我们比较使用频率概率估计，一阶马尔可夫模型和灯模型计算得出的估计值，并考虑了确保过渡矩阵不可还原的两种方法。在大多数情况下，灯熵速率低于替代方案的速度，这表明灯模型更好地适应过程中的结构依赖性。
This work derives a theoretical value for the entropy of a Linear Additive Markov Process (LAMP), an expressive model able to generate sequences with a given autocorrelation structure. While a first-order Markov Chain model generates new values by conditioning on the current state, the LAMP model takes the transition state from the sequence's history according to some distribution which does not have to be bounded. The LAMP model captures complex relationships and long-range dependencies in data with similar expressibility to a higher-order Markov process. While a higher-order Markov process has a polynomial parameter space, a LAMP model is characterised only by a probability distribution and the transition matrix of an underlying first-order Markov Chain. We prove that the theoretical entropy rate of a LAMP is equivalent to the theoretical entropy rate of the underlying first-order Markov Chain. This surprising result is explained by the randomness introduced by the random process which selects the LAMP transitioning state, and provides a tool to model complex dependencies in data while retaining useful theoretical results. We use the LAMP model to estimate the entropy rate of the LastFM, BrightKite, Wikispeedia and Reuters-21578 datasets. We compare estimates calculated using frequency probability estimates, a first-order Markov model and the LAMP model, and consider two approaches to ensuring the transition matrix is irreducible. In most cases the LAMP entropy rates are lower than those of the alternatives, suggesting that LAMP model is better at accommodating structural dependencies in the processes.
