Education of a Model Student

This is another theoretical paper. Its authors are from Cornell University and include Jon Kleinberg and Steven Strogatz. The subject of the paper is the study of mathematical models for scheduling of educational material. Many asymptotic analysis of the relationship between learning rate and spacing constraints are given for different families of constraints and educational goals.

The authors consider a simplified educational model that is based on a set of educational units u_1, u_2, ... u_n which have spacing constraints defined by sequences {a_k} and {b_k}. A pair (a_i,b_i) tells us that the (i+1)-th ideal time to the student see a given unit is between a_k and b_k time steps after seeing it for the i-th time. In general, the spacing constraints are the same for all units and can be defined by functions. Moreover, the paper studies two educational goals: the infinite perfect learning and the finite sequence (cramming). Infinite perfect learning consists of never forgetting what have been learned so far. Cramming is a method of learning that has a specific temporal target (e.g., a test) and does not assure that the learned material will be remembered after this target.

From now, I will summarize some of the most important results presented in the paper. Proofs will be discussed without much detail.

The Recap Method: Based on the idea of infinite perfect learning and a quick learning rate (i.e., rate at which new content is introduced). The learning rate t_n (i.e., the time stamp when the content n is introduced) grows as theta(n log n) and a_k = 2^k and b_k=2^(k-1)(k+1). An algorithm for generating this schedule can be defined in terms of a depth-first post-order traversal of a binary tree. An example for 4 units is: u_1,u_2,u_1,u_2,u_3,u_4,u_3,u_4,u_1,u_2,u_3,u_4,...

The Superlinearity of the Introduction Time Function: For schedules that exhibit infinite perfect learning, the introduction time function t_n must be superlinear. This is my favorite result of the paper and it makes me think a lot about my own lousy educational strategy. They prove it by contradiction. A linear learning rate means that there is a c such that t_n <= c.n for all n. Let n_0 be an integer such that n_0 > Sum_{j=1}^k b_j. At least c.n_0 units has been introduced at n_0. Moreover, at least n_0  units will have occurred c+1 times by time step c.n_0+Sum_{j=1}^k b_j. So, c.n_0+Sum_{j=1}^k b_j >= (c_1).n_0 and Sum_{j=1}^k b_j >= n_0, which is a contradiction.

The Slow Flashcard Schedule: This schedule is based on a deck of flashcards, where the kth card corresponds to the unit u_k. A card is taken from the top and inserted into the k+1 position, where k is the number of times the card has already been taken. This generates a schedule such as: u_1,u_2,u_1,u_2,u_3,u_1,u_3,u_2,u_4,u_3... It is shown that this schedule exhibits infinite perfect learning with spacing constraints (a_k,b_k) = (k,k^2). Simulation results suggest that this schedule may even exhibit infinite perfect learning with spacing constraints (k,2k).

Flexible Students: For flexible students a_k = 1 for all k. In this scenario, the authors propose a sequencing for which b_1>=2 , b_k => inf and in which the constraints are met and new material is quickly introduced. The idea is increasing the level of the sequences as follows:

Level 1: u_1,u_2,u_1,u_2,...

Level 2: u_3,u_1,u_3,u_2,u_3...

Level 3: u_4,u_1,u_4,u_2,u_4,u_3...

...

This schedule exhibits infinite perfect learning and b_k can grow arbitrarily slowly, depending on the value of b_k.

The Finicky Slow Student: For this family of constraints, where a_k = b_k = k it is not possible to achieve infinite perfect learning. It is proved by contradiction by showing for two or more units, it is not possible to meet the constraints without conflicts. Unit u_1 will occur at times t_1,t_2, ... where t_i = Sum_{k=1}^i a_k. Lets state that u_2 starts at s_0 and also occurs at s_1,s_2, ... where s_i=s_0+Sum_{k=1}^i a_k. We know that s_i - t_i = s_0 and s_{i+1}-s_i = t_{i+1}-t_i=a_{i+1}. Choose k large enough so that t_{k+1}-t_k>s_0, then t_{k+1}>t_{k}+s_0=s_k and t_{k+1}>s_k. Let m be the smallest number such that t_m+1>s_m. The authors show that t_{m}=s_{m-1}.

Cramming: The authors show that for every positive integer n and every set of spacing constraints with b_k approaching to infinite, there exists a sequence that achieves bounded learning of order n. In other words, if you have a given content to study for a test, it is possible to organize a schedule for this test for any valid spacing constraints with enough time. They prove it by induction, using the idea of inserting a new unit into a sequence S_n. They also present limits on the amount of content that can be crammed in a limited amount of time. I confess that I did not understand this part very well, I believe an example would help.

This paper is very interesting. Based on a real complex problem, the authors propose a very simple model and apply asymptotic analysis to study it from several perspectives. During the reading, I discovered that asymptotic analysis was borrowed/stolen by computer scientists, having many (maybe more) applications outside it. I should study this subject more in the future, specially from a broader perspective (e.g., a book about asymptotic analysis in general).

Link: http://www.pnas.org/content/early/2012/01/13/1109863109.full.pdf+html