Kolmogorov complexity and its applications

柯尔莫哥洛夫复杂度及其应用

• 批准号: RGPIN-2016-03687
• 负责人: Li, Ming
• 金额: $ 4.59万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634829
• 关键词: Kolmogorov; complexity; its; applications

I am interested in developing a compelling theory of big data. Such a theory will depend on Kolmogorov complexity and information distance. Kolmogorov complexity is defined on one object. Information distance [C. Bennett, P. Gacs, M. Li, P. Vitanyi, W. Zurek, Information distance, IEEE Tran-IT, 44:4(1998)] is defined on two objects. This concept can be generalized to many objects. Using such a theory it is possible to optimally approximate the intuitive concept of "semantic distance" or closeness of two piece of data, in general. The key to this theory is to compress the data. Many ways of compressing data will be studied, including error encoding, clustering, and especially deep neural networks. Deep neural networks can be considered as ways of compressing data, especially big data. The following short-term goals are in tune with the above main theme of this research:

我对发展一个令人信服的大数据理论感兴趣。这样的理论将依赖于柯尔莫哥洛夫复杂度和信息距离。Kolmogorov复杂度定义在一个对象上。信息距离[C.班尼特，P. Li，P. Vitanyi，W. Zurek，Information distance，IEEE Tran-IT，44：4（1998）]定义在两个对象上。这个概念可以推广到许多对象。使用这样的理论，通常可以最佳地近似两个数据的“语义距离”或接近度的直观概念。 这个理论的关键是压缩数据。将研究许多压缩数据的方法，包括错误编码，聚类，特别是深度神经网络。深度神经网络可以被认为是压缩数据，特别是大数据的方法。以下短期目标与本研究的上述主题一致：