planeheart的头脑风暴
注册日期:
2013-09-16 15:53:09
上次登录:
2016-05-11 02:38:27
邮件地址:
saintpal@163.com
兴趣领域:
数学,物理,人工生命,系统科学,计算机科学
  
用逻辑深度表征和分类数字图像
2015-04-08 03:43:59  图像分类  逻辑深度  复杂度 

 

A computable universe的编者Hector Zenil及其合作者发表的文献Image Characterization and Classification by Physical Complexity 中,证明了虽然“物理的复杂度”不可计算,但稳定的近似依然具有在图像处理上的应用价值。在这里,所谓“物理的复杂度”指的乃是C.H.Bennett早在1987年定义的逻辑深度,名称来源于逻辑深度的研究动机为量化物理系统的复杂性(见Logical depth and physical complexity

 逻辑深度(下简称深度)与Kolmogorov复杂度(下简称复杂度)密切相关。指定一台适当的通用机作为参考机,二元数据的复杂度定义为在参考机上运行并输出该数据的最短程序长度,而深度则定义为该最短程序生成原数据所需的步数【1】。研究揭示复杂度极高的数据应具有随机噪声的特征,而深度极高的数据则具有高度复杂的结构性特征。因此,复杂度往往衡量的实际上是“随机”,而深度衡量的才更接近我们直觉中的“复杂”概念。

 由于恼人的不可计算性,逻辑深度的研究常常被局限于纯理论方面。但同样不可计算的Kolmogorov复杂度早已通过近似方法被应用于基因谱系和语言谱系的分析,音乐风格的机器识别数据挖掘复杂网络的表征交通流和蠕虫病毒的研究改进支持向量机的训练算法等方面,对于数据规模较大的情况,常用的近似办法是用各种性能优良的压缩算法(gzip,bzip2,PPMZ,Deflate,Lempel-Ziv,Context tree weighting等)对数据进行压缩,将最小压缩包的大小作为Kolmogorov复杂度的近似【2】,相应地,最小压缩包的解压时间则可以作为逻辑深度的近似(排除干扰因素还需要一些技术细节,此处略去)。

 既然理论部分已经介绍完了,现在就来看看计算机实验成效如何。依据逻辑深度从高到低可以将图像文件分组排列如下:

 

从以上的结果可以看出,逻辑深度将“认为”分形结构,人脸,手写笔迹等比随机图案或纯色更加复杂,假如逻辑深度的快速近似算法足够有效,则它的应用价值或在于与图像分块法结合,从大面积的图像中迅速识别出包含有效信息的区域。

目前笔者感到好奇的是逻辑深度是否也能够用于音乐的处理。上文已经提到Kolmogorov复杂度在这方面有所应用,逻辑深度与Kolmogorov复杂度一样,在理论上是普适的度量而不依赖于具体的领域,所以深度也可以被寄予同等的期望。基于1/f噪声理论的研究已经显示不少经典乐曲在功率谱上具有强烈的共通性。类似地,如果音乐的美感与逻辑深度之间有着足够强的相关性的话,这会是非常有启示性的结论。

 

 

 

 

 

 

 

 

【1】      这个定义虽然符合原本的精神,但研究发现仅考虑最短程序会导致逻辑深度的不稳定。如果存在多个比最短程序稍长,但运行较快的等价程序的话,简单地改变参考机的选取就有可能造成逻辑深度的剧变。而且这种情况也会导致逻辑深度对随机性太过敏感。为了克服这个缺陷,Bennett最终将串s的逻辑深度定义为所有比最短程序不长出d比特的“准最短”程序中生成s所需的最低步数,其中d是需要根据实际情况确定的显著性参数。适当的d将会引入足够多的程序的用时竞争,使深度更加符合描述的要求。

 

【2】       为了使近似结果符合实际,利用数据本身的特征来优选和改进已有的压缩算法是有必要的。不过往往无法用数学严格证明某一种压缩算法一定可以将复杂度近似到给定的精度以内。所以我们只能说:从结果的成功上看,所用的近似算法应该是足够接近实际情况的。

2015-04-08 05:05:18
   这个介绍很有意思,推荐~
2015-04-08 05:16:38
   直观看来,复杂度可定义二维世界的空间,逻辑深度则可定义其时间。
2015-04-14 15:57:25
   谢谢分享,我从未听过逻辑深度,这篇介绍很有启发性。
登录后才可以评论,马上登录