Grant: Discovery Grants Program - Individual
University of Waterloo
$63,000.00
Kolmogorov complexity and its applications
FY 2016-17
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-03687
Name nom
Li, Ming
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheri
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
63000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
800
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information and communication services
Area of application fr
Services d'information et de télécommunications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Kolmogorov complexity and its applications
Keyword
NSERC
Application summary
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.