Sun Xianfang, Rosin Paul L, Martin Ralph R
School of Computer Science and Informatics, Cardiff University, Cardiff, UK.
IEEE Trans Syst Man Cybern B Cybern. 2011 Jun;41(3):749-60. doi: 10.1109/TSMCB.2010.2091271. Epub 2010 Dec 3.
Cellular automata (CA) with given evolution rules have been widely investigated, but the inverse problem of extracting CA rules from observed data is less studied. Current CA rule extraction approaches are both time consuming and inefficient when selecting neighborhoods. We give a novel approach to identifying CA rules from observed data and selecting CA neighborhoods based on the identified CA model. Our identification algorithm uses a model linear in its parameters and gives a unified framework for representing the identification problem for both deterministic and probabilistic CA. Parameters are estimated based on a minimum variance criterion. An incremental procedure is applied during CA identification to select an initial coarse neighborhood. Redundant cells in the neighborhood are then removed based on parameter estimates, and the neighborhood size is determined using the Bayesian information criterion. Experimental results show the effectiveness of our algorithm and that it outperforms other leading CA identification algorithms.
具有给定演化规则的细胞自动机（CA）已得到广泛研究，但从观测数据中提取CA规则的逆问题研究较少。当前的CA规则提取方法在选择邻域时既耗时又低效。我们提出了一种从观测数据中识别CA规则并基于所识别的CA模型选择CA邻域的新方法。我们的识别算法使用参数线性模型，并为确定性和概率性CA的识别问题提供了一个统一的框架。基于最小方差准则估计参数。在CA识别过程中应用增量程序来选择初始粗邻域。然后根据参数估计去除邻域中的冗余细胞，并使用贝叶斯信息准则确定邻域大小。实验结果表明了我们算法的有效性，并且它优于其他领先的CA识别算法。
