Kolmogorov complexity and its applications

我对开发一个令人信服的大数据理论很感兴趣。这样的理论将取决于科尔莫戈罗夫的复杂性和信息距离。柯尔莫戈罗夫复杂性是在一个对象上定义的。在两个对象上定义了信息距离[C.Bennett，P.Gacs，M.Li，P.Vitanyi，W.Zurek，Information Distance，IEEE Tran-IT，44：4(1998)]。这个概念可以推广到许多对象。使用这样的理论，通常可以最佳地近似两段数据的“语义距离”或接近这一直观概念。这一理论的关键是对数据进行压缩。将研究许多压缩数据的方法，包括错误编码、聚类，特别是深度神经网络。深度神经网络可以被认为是压缩数据，特别是大数据的方法。以下短期目标与上述研究主题一致：*1)自然语言处理(NLP)的深度学习。我的团队已经训练了卷积神经网络(CNN)来将自然语言问题映射到具有有限数量关系的数据库结构化查询。这项工作将继续下去。我的团队还训练了一个用于对话或聊天的递归神经网络(RNN)。这项工作将扩展到上下文敏感聊天。这项工作将有两个长期目标：a)神经网络将被作为一种近似语义距离的方法进行研究；b)只有来自互联网的大数据，这种方法才是实用的。*2)生物信息学。美国有线电视新闻网还接受了蛋白质鉴定以及在质谱学蛋白质定量中挑峰的培训。这些研究和方法将扩展到蛋白质定量。这项工作再次依赖于我从行业获得的大量培训数据。*不会孤立地研究这些深度学习方法。他们将与我用信息距离近似语义距离的理论一起进行研究，试验在没有明确的压缩规则的情况下，使用深度神经网络作为压缩方法来处理大数据的效率。我还将花8个月的时间与Paul Vitanyi一起修改他的研究书籍《科尔莫戈罗夫复杂性及其应用导论》，其中将包括这些新的结果。*生物信息学中的其他几个短期主题将被研究。一种是抗体排序算法。我计划设计一种使用线性规划的新算法来解决抗体测序的生物信息学工业问题。另一个问题是将生物信息学中的想法应用到其他领域：我的团队发明了最佳间距种子来进行同源搜索。这被认为是过去15年来生物信息学中最有影响力的创新之一。我的想法是使用最优间隔种子的想法来开发一种观察理论来检测时间序列中的趋势。初步实验取得成功。**

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: ***1) Deep learning in natural language processing (NLP). My group has trained a Convolutional Neural Network (CNN) to map natural language questions to a database structured query with a limited number of relations. This work will continue. My group also has trained a Recurrent Neural Network (RNN) for conversation or chatting. This work will be extended to context sensitive chatting. This work will have two implications with the long term goal: a) Neural network will be studied as one way to approximate semantic distance; and b) Only with big data from the internet, this approach is practically useful.***2) Bioinformatics. A CNN has also been trained for protein identification as well as for peak-picking in mass spectrometry protein quantitation. These studies and methodologies will be extended to protein quantitation. This work again depends on huge amount of training data I have obtained from industry. ***These deep learning approaches will not be studied in isolation. They will be studied together with my theory of approximating semantic distance by information distance, experimenting with the efficiency of using deep neural networks as compression methods to deal with big data when there are no clear rules of compressing. I will also spend 8 months full time to revise his research book with Paul Vitanyi "An introduction to Kolmogorov complexity and its applications", that will include these new results. ***Several other short-term topics in bioinformatics will be studied. One is an antibody sequencing algorithm. I plan to design a new algorithm using linear programming to solve a bioinformatics industrial problem of antibody sequencing. Another problem is to apply the ideas in bioinformatics to other fields: optimal spaced seeds were invented by my group to do homology search. This has been considered one of the most influential innovations in bioinformatics during the last 15 years. I have the idea of using the optimal spaced seed idea to develop an observation theory to detect the trends in time series. Initial experiments were performed successfully.**