CS 898: Kolmogorov complexity and its applications Winter 2023 Home cs.uwaterloo.ca/~mli/

   

Instructor:
Ming Li	Contact me by email	mli@uwaterloo.ca
Course time and location:	The official course time is Fridays 9:00-11:50am. We will hold the first class during this time on Jan. 13, 9am EST, on zoom. Our zoom meeting id will always be: 863 4846 7016. (There is no passcode) All the lectures have been recorded. The students will view the recorded lectures online at their convenience before the lecture time. Then at the the class time, I will go thru the ppt, and explain the key points and answer questions.
Office hours:	Any time by email, and we can hold separate zoom sessions.
Textbook:	Ming Li and Paul Vitanyi, An introduction to Kolmogorov complexity and its applications. 4th edition, Springer, 2019 (Other editions are ok too)

The course material will be mainly from the textbook, research papers, the ppt lecture notes and recorded zoom session presentations. The students will do three homeworks and a research project at the end of the term, and present it via zoom.

Kolmogorov complexity is a modern theory of information and randomness. The goal of this course is to teach the students the basic concepts of Kolmogorov complexity and how to use this tool in their own research. This term we will focus on how Kolmogorov complexity can be used in deep learning and help to resolve problems such as few shot learning.

Topics include: plain Kolmogorov complexity, randomness, prefix Kolmogorov complexity, incompressibility method, information distance, applications in various fields ranging from average-case analysis of algorithms, Lovasz Local Lemma, to few shot learning. It is impossible to cover the complete textbook, rather we will focus more on recent developments but we will focus on the applications, especially I wish to discuss in depth on Kolmogorov complexity applications to few shot learning.

Marking Scheme: Each student is expected to do three homeworks (20% each) and a final project and presentation in class (via zoom recording) which can be either theoretical or programming (40%).

Course announcements and lecture notes will appear on this page. You are responsible for reading it regularly.

Assignments:

• The assignment 1 (Due Jan. 27) contains the following problems from the textbook (4th edition): Exercises 2.1.1[a], 2.1.2, 2.1.3, 2.1.5 (page 113) and 2.2.5, 2.2.6 (page 122).
• Assignment 2 (Due Feb. 24)). Do Exercises 2.4.2 (page 141), 2.5.1, 2.5.2, 2.5.3 (page 160),from the textbook (4th edition) and prove the following statement: If a binary sequence x of length n has exactly n/2 0's, then x is not c-incompressible, for large enough n.
• Assignment 3 (Due March 17). Problem 1: Use Kolmorogov complexity to directly prove that a 1 head 2-way DFA cannot accept L={w#w | w in {0,1}*}. Note, please do not use other theorems, do a direct Kolmogorov complexity proof. Problem 2: Using Kolmogorov complexity, obtain the average case lower bound for binary search. Problem 3: Using Kolmogorov complexity (directly, without using theorems from Chapter 6), prove that {0^n 1^m | m>n} is not regular. Problem 4: Do Excercise 6.8.5 (page 504 in the textbook, 4th edition). Problem 5: ShakerSort sorts a list of numbers by comparing each adjacent pair of items in a list in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning. It stops when a pass does no swaps. Using incompressibility argument, prove a tight average case lower bound for ShakerSort. Problem 6. Do Exercise 6.3.1 (Page 465 of the textbook, 4th edition), using Kolmogorov complexity. Problem 7. Do Exercise 6.3.3 (Page 465, 4th edition), using Kolmogorov complexity.

Project topics:

This term, I wish to focus on Kolmogorov complexity application to few shot learning and consciousness. The main ideas are in this paper. Project topics include:
• Tradeoff between compression during training stage and compression at the inference stage;
• Few shot learning applications.
• Predictive coding. (See Predictive coding in the visual cortex: a functional interpretation of some extra-classical receptive-field effects by R. Tao, D. Ballard, Nature Neuroscience, 1999)
• Representation learning with contrastive predictive coding, by A. Oord, Y. Li, O. Vinyals)
• Improve Omniglot character recognition (1 shot 20 way dataset).
• Few shot learning for low resource languages: trade-off of training data amount and the need for recognition stage compression.
• Extend few shot learning in NLP to other types of queries.
• Understand relationship among consciousness, compression, and learning.

Other possible project topics:

• Review and extend the recent work of Bill Gasarch: Gasarch recent manuscript on context-free grammar size using Kolmogrov complexity.
• Simplicity of Deep learning models. Take a look at this paper.
• Replace mutual information argument in this and next paper by Kolmogorov complexity? This paper extends the usage of mutual information to NLP
• Do average analysis of an algorithm, using Kolmogorov complexity.
• Interesting applications of Kolmogorov complexity to LLL type of problems.
• Simplify and improve average-case analysis of Quicksort using Kolmogorov complexity (I will provide the papers).
• Improve the Shellsort average-case lower bound (Open). This is very difficult.
• Close the gap of logn upper bound and (1/2)logn lower bound for the following problem: given a sequence of k stacks linearly connected from left to right. The input is a permutation of n integers to the leftmost stack. The integers move in order (not passing each other unless they go into stacks) from left to right and any of them can go into any stack when they arrive at that stack and popped out at some subsequent steps. The output is from the rightmost stack and should be sorted in increasing order. How many stacks do we need? Or demonstrate why Kolmogorov complexity cannot be used for further improvement. Note: Luke Schaeffer has improved (1/2)logn to 0.53logn.
• Please do not hesitate to discuss with me on both finding and solving your project problems. Please let me know what you wish to work on. I generally prefer people working on the different projects. A project can be 1) Original theoretical research; 2) An application of Kolmogorov complexity (proving a theorem, analyzing an algorithm, or implement a program); 3) In depth analysis of one potential application of Kolmogorov complexity, when you failed 1) or 2); 4) In depth survey / review of one area.

Lectures:

• Lecture 1. History, definition of Kolmogorov complexity, basics (Chapters 1 and 2). 1 week. Lecture 1 ppt. || Lecture 1 video, 2023 Lecture 1 video || Lecture 1 video, Part 1 || Lecture 1 video, Part 2
• Lecture 2: Randomness. Definitions and Martin-Lof tests (Sections 2.4, 2.5). 2 weeks. Lecture 2, Part 1 ppt || Part 2 ppt. || Lecture 2 video, Part 1 || Lecture 2 video, Part 2. Lecture 2 video, More explanation on randomness -- finite case Feb 3 Lecture video, More explanation on randomness -- infinite case and assignment 2
• Lecture 3: Symmetry of Information (Section 2.8). 1 week. Lecture 3 ppt || Lecture 3 video
• Lecture 4 (Feb. 17 week): Few shot learning, and how to specialize ChatGPT. New lecture notes: . We will use this pptx, please attend the class, and not to depended on the previous recorded videos. Lecture on few shot learning video, 2023 Feb. 17 (Sections 8.2, 8.3, 8.4, 8.6 this paper, this paper, and this paper). 2 weeks. Lecture 4 ppt || Lecture 4 video
• Lecture 5: The incompressibility method and its applications in average case analysis and lower bounds (Chapter 6) HeapSort+LLL video || Lecture 5 ppt || Lecture 5 video, part 1|| Lecture 5 video, part 2|| Lecture 5 video, part 3|| Lecture 5 video, part 4|| Some nice additional notes by Tao Jiang 2 weeks.
• Lecture 6: Prefix Kolmogorov complexity (Chapter 3) Lecture 6 ppt || Lecture 6 video
• Lecture 7: Inductive Inference (Chapter 5) Lecture 7 ppt || Lecture 7 video
• Lecture 8: Kolmogorov complexity and the nature (Chapter 8) Lecture 8 ppt || Lecture 8 video
• Lecture 9: Resource bounded Kolmogorov complexity (Chapter 7). Lecture 9 ppt || Lecture 9 video || For those who are interested in reading more, you can look at this Lance Fortnow notes).

Student Presentations (Starting April 10, 9am):

• 9:00am Wen Cui. Crash Report Analysis and Classification
• 9:20am Minghan Li Planning for empowerment in visual environments
• 9:40am Futian Zhang. Use one-shot learning for mouse gesture recognition with siamese neural network
• 10:00am Albert Ding Few-shot saliency
• 10:20am Sheng-Chieh (Jack) Lin. Contextualized query embeddings for conversational search
• 10:40am Cynthia Hongfeng Huang Few-shot text classification using large language model-based range coding
• 11:00am Yue Lyu Designing mobile neuraofeedback training games for children with autism spectrum disorder
• 11:20am Xueguang Ma Precise document retrieval by minimizing Kolmogorov distance with document generation
• 11:40am Zeping Mao and Yandong Zhu Overcome PTM problem in de novo peptide sequencing with few-short learning

Announcements: