A dilemma faced by teachers, and increasingly by designers of educational software, is the trade-off between teaching new material and reviewing what has already been taught. Complicating matters, review is useful only if it is neither too soon nor too late. Moreover, different students need to review at different rates. We present a mathematical model that captures these issues in idealized form. The student's needs are modeled as constraints on the schedule according to which educational material and review are spaced over time. Our results include algorithms to construct schedules that adhere to various spacing constraints, and bounds on the rate at which new material can be introduced under these schedules. asymptotic analysis | scheduling I n his 2009 speech to the National Academy of Sciences, President Barack Obama exhorted the audience to imagine some of the things that could be made possible by a commitment to scientific research, including the invention of "learning software as effective as a private tutor" (1). This paper is a modest step in that direction. An important challenge for the design of educational software is to incorporate the results of empirical research on how people learn. Such research endeavors to provide principles for how to choose what is taught, how to present it, and how to sequence the material. Ultimately, educational software will require mechanisms for managing the constraints that arise when these principles are applied in different settings. Here we develop and analyze an idealized mathematical model for incorporating a fundamental class of such constraints into educational software-constraints arising from the importance of timing and review in the presentation of new material. For example, software for building vocabulary must determine when to introduce new words that the student has not yet learned, and when to review words whose definitions the student has successfully recalled in the past. The issue is similar to that faced by a high school math teacher deciding how often to schedule lessons that involve trigonometry, or by a piano teacher who needs to decide how much time a student should devote to practicing scales while also learning to play new pieces. The study of the importance of timing with respect to review dates to at least 1885 (2). The notion that it is better to spread studying over time instead of doing it all at once is called the spacing effect. In 1988, Dempster noted that "the spacing effect is one of the most studied phenomena in the 100-year history of learning research" (3). As Balota et al. point out in their review (4), "spacing effects occur across domains (e.g., learning perceptual motor tasks vs. learning lists of words), across species (e.g., rats, pigeons, and humans), across age groups and individuals with different memory impairments, and across retention intervals of seconds to months." See refs. 5 and 6 for reviews. For further results and background, see refs. 7-9. For work on exploiting the spacing effect to build vocabulary (in humans), see refs. 10-13. Review is an important part of the learning process, but the extent to which review is needed varies by student. Some students need to review early and often, whereas others can learn a lot without any review at all. Personalized educational software of the future could fit a model to the user and then schedule review in a way that is tailored to the model. With such educational software in mind, we envision a system in which the software designer can specify a schedule for the introduction of new material, together with a schedule by which the review of existing material is spaced over time. What we find, however, is that the resulting scheduling problems are mathematically subtle: Existing techniques do not handle scheduling problems with spacing constraints of this type. Our main contribution is to develop an approach for reasoning about the feasibility of schedules under spacing constraints. We begin by introducing a stylized mathematical model for the constraints that arise from the spacing effect, and then consider the design of schedules that incorporate these constraints. Roughly speaking, we model the introduction and review of material as a sequence of abstract educational units, and we model the needs of the student using two sequences, fa k g and fb k g: After an educational unit has been introduced, the "ideal" time for the student to see it for the ðk þ 1Þ st time is between a k and b k time steps after seeing it for the kth time. We also model various educational outcomes that the designer of educational software may seek to achieve. The details are given below. The Educational Process. We imagine the underlying educational software as implementing a process that presents a sequence of abstract educational units which could represent facts such as the definitions of vocabulary words, concepts such as trigonometric identities, or skills such as playing a scale on the piano. For example, the sequence u 1 , u 2 , u 3 , u 1 , u 4 ;…, indicates that educational unit u 1 was introduced at the first time step and reviewed at the fourth time step. This sequence defines the schedule according to which the units will be presented. We also allow our schedules to contain blanks, or time steps in which no educational unit is presented; thus, an arbitrary schedule will have each entry equal to either an educational unit or a blank. This model is highly idealized. It ignores possible relationships between units, such as the etymological (and potentially pedagogically useful) connection between the vocabulary words "neophyte" and "neologism," for example, or the dependence of trigonometry on more basic concepts in geometry. It also treats all units as equal. Thus it does not capture, for example, that an experienced pianist may benefit more from practicing a scale than practicing Twinkle Twinkle Little Star. The real-life educational process is nuanced, complex, and context dependent. Future work in building models for educational software may introduce more complexity to this model, or simply reduce scope and model more specific situations. Here, Author contributions: T.P.N., J.M.K., and S.H.S. designed research, performed research, analyzed data, and wrote the paper. Conflict of interest statement: T.P.N. is the owner of a small, wholly owned company, Flash of Genius, LLC, that sells educational software. This article is a PNAS Direct Submission. in the interest of generality as well as mathematical tractability, we use this very simple model of the general educational process in order to create a formalism that captures spacing constraints and their role in reviewing material after it has been introduced. Spacing Constraints. A large body of empirical work in learning research has studied the expanding nature of optimal review. For example, when students first learn a new vocabulary word, they must review it soon or else they likely lose the ability to correctly recall the definition. If they do review it before forgetting it, they will then generally be able to go longer than before without needing review. By repeatedly reviewing, the student "builds up" the ability to go longer and longer without seeing the word while maintaining the ability to recall its definition. However, reviewing a word too soon after studying it can reduce the benefit of the review. These are the principles of the well-established theory of expanded retrieval; see ref. 4 for a review specifically on expanded retrieval. More generally, see refs. 3-13. We want a simple formalism that captures the need to review an educational unit on a schedule that "expands" the spacing between successive viewings. We wish to leave the exact rate of expansion under the control of the software designer, motivated by the goal of creating different schedules for different students. We thus imagine that the designer of the software specifies a set of spacing constraints, consisting of an infinite sequence of ordered pairs ða 1 ;b 1 Þ, ða 2 ;b 2 Þ;…;ða k ;b k Þ;…, where a k ≤ b k are positive integers for all k. Intuitively, the idea is that, for each educational unit u i in the schedule, the designer wants the gap in the schedule between the kth and ðk þ 1Þ st occurrences of u i to have length in the closed interval ½a k ;b k . The fact that a student can go longer between occurrences as they gain familiarity with the educational unit is represented by the assumption that the numbers a k and b k are weakly increasing: We impose the requirement that a k ≤ a kþ1 and b k ≤ b kþ1 for all k. Thus, our key definition is that a schedule satisfies a set of spacing constraints if, for each u i in the schedule, the ðk þ 1Þ st occurrence of u i in the schedule comes between a k and b k positions (inclusive) after the kth occurrence. Roughly speaking, the numbers b k model how long the student can retain learned material. The numbers a k model how long a student should wait before review is beneficial, capturing the notion that there is an ideal time to review. If review is done too early, it is less beneficial. If it is done too late, the student will forget the material in the interim. This model is, by design, a simplification of spacing constraints and their role in learning. A more nuanced model might allow for "blurry" boundaries for the intervals ½a k ;b k , in which there is a numerical penalty for missing the interval by a small amount. Another refinement would be to allow the model to discriminate between educational units to reflect that some things are easier to learn than others. However, our simple model captures the essence of the phenomenon we are investigating, and will allow for mathematical analysis that elucidates the mechanics of scheduling review in an optimal way. Educational Goals. We consider two natural goals for the designer of the educational software. The mission of the software could be to teach students in such a way that they grow their knowledge without bound, never forgetting anything along the way; a sort of "lifelong learning" approach to education. Alternatively, the mission could simply be to get students familiar with a certain set of educational units by a particular point in time, regardless of whether they are destined to forget what they learned quickly thereafter; something like the studying technique known as "cramming." We address both goals in this paper. We model the first goal by saying that a schedule exhibits infinite perfect learning with respect to some spacing constraints if (i) it satisfies the spacing constraints, and (ii) it contains infinitely many educational units, each of which occurs infinitely often. Thus if the constraints represented the needs of a student, then with such a schedule the student would, over the course of the infinite sequence, learn an infinite set of educational units without ever forgetting anything. For the second goal we consider a finite sequence, representing the presentation of material up to a test or performance. For a positive integer n, we say that the sequence is a cramming sequence, and exhibits bounded learning of order n, if (i) it satisfies the spacing constraints, and (ii) it contains at least n distinct educational units such that, if a unit occurs a total of k times in the sequence, then its last occurrence is within b k positions of the end of the sequence. Condition (ii) captures the requirement that the student should still be able to recall all of the n educational units at the end of the sequence, which was the whole point of cramming. Note that, although the spacing constraints have been respected up to the end of the finite sequence, there is no guarantee that the sequence could be extended while continuing to satisfy the spacing constraints. With respect to infinite perfect learning, we will be interested in the rate at which the student would learn if taught according to the schedule. To this end, we define the introduction time function: For a given schedule of educational units, let t n denote the position in the schedule of the first occurrence of the nth distinct educational unit. Thus the slower the growth of t n , the faster new educational units are being introduced. We will be considering questions of the following nature. Given spacing constraints fða k ;b k Þg, does there exist a schedule that exhibits infinite perfect learning, or bounded learning, with respect to the constraints? If so, how can we construct such schedules? And when such a schedule exists, what rate of learning (as measured by the sequence t 1 ;t 2 ;…) is achievable? These are fundamental problems that would be faced by an educational software designer seeking to incorporate spacing constraints in the design of the underlying algorithms. As we will see, despite the simply stated formulation of these questions, the combinatorial challenges that they lead to quickly become quite intricate. The spacing constraints are described by two infinite sequences of parameters, fa k g and fb k g. In this section, we describe how choices for these parameters affect the rate at which new educational units can be introduced into the schedule and how schedules can be tailored to particular parameter regimes and educational goals. Overview of Results. We begin by examining the first main issue of this paper: the trade-off between (i) the rate at which b k grows as a function of k and (ii) the rate at which t n grows as a function of n. Informally, if b k grows relatively slowly, then a lot of time must be spent on review rather than on introducing new units, and hence t n must grow more quickly, corresponding to slower learning. It is clear that t n ≥ n for any schedule, because even without review we can only introduce one educational unit per time step. With these considerations in mind, we investigate the following pair of questions that explore the two sides of the trade-off. First, is there a set of spacing constraints for which t n is close to this trivial bound, growing nearly linearly in n? Second, as we require b k to grow slower as a function of k, it becomes more difficult to achieve infinite perfect learning. Is there a set of spacing constraints for which infinite perfect learning is possible, and for which b k grows as a polynomial function of k? We answer both of these questions in the affirmative. In The Recap Method, we describe a set of spacing constraints for which a schedule can be constructed that exhibits infinite perfect learning, and where the rate of learning is relatively quick. In the schedule we construct, t n grows as Θðn log nÞ, and in fact t n ≤ n · ð⌊ log 2 n⌋ þ 1Þ. Recalling that we must have t n ≥ n for all 2 of 6 | www.pnas.org/cgi/doi/10.1073/pnas.1109863109 Novikoff et al. n for any schedule, we see that the recap schedule achieves infinite perfect learning with only a modest increase on this bound-that is, with a relatively small amount of review. In the SI Text, we show how to construct a schedule where t n grows at a rate that, in some sense, can be as close to linear as desired. In Superlinearity of the Introduction Time Function, we show that there can be no schedule whatsoever such that t n grows as OðnÞ. In The Slow Flashcard Schedule, we show a set of spacing constraints for which a k and b k grow polynomially in k and for which infinite perfect learning is possible. With these spacing constraints based on much smaller a k and b k , the schedule we construct has a slower rate of learning; t n is bounded below by Ωðn 2 Þ and bounded above by Oðn 3 Þ, in contrast to the schedule from The Recap Method for which the introduction time function grows as Θðn log nÞ. The gap between the quadratic lower bound and the cubic upper bound is an interesting open question; we give numerical evidence that in fact the lower bound may be tight, and that t n grows as Oðn 2 Þ. Much of this analysis is done in the SI Text. Following these results, we turn to the second main issue in this paper, which is to identify general possibility and impossibility results for satisfying classes of spacing constraints. We first show, in Flexible Students, that the difficulty in achieving infinite perfect learning stems, in a sense, from the fact that the numbers a k are growing: Specifically, we show that for any spacing constraints in which a k ¼ 1 and b k → ∞, it is possible to construct a schedule that exhibits infinite perfect learning. The construction introduced here demonstrates a general method that can be adapted to many sets of spacing constraints with a k > 1 as well. Thus far, we have only considered spacing constraints that allow for the construction of schedules that exhibit infinite perfect learning. In The Finicky Slow Student, we show that there exist spacing constraints for which no schedule can exhibit infinite perfect learning. In particular, we build this impossibility result from an extreme case, where a k ¼ b k ¼ f ðkÞ and f ðkÞ is a function that grows slowly in k. These constraints represent a setting in which the student insists on reviewing material on an extremely precise and plodding schedule, with no room for error. The difficulty in constructing a schedule for such a set of constraints is that as the knowledge base-the number of educational units introduced-grows, so does the need to review, and so the potential for scheduling conflicts increases. The slower the student [the slower the growth of f ðkÞ], the fewer educational units can be put on the back burner, so to speak, while the student focuses on new units. The more finicky the student (the smaller the windows b k − a k ), the less wiggle room there is in scheduling review. All of these points match with intuition. Students who don't need to review much and aren't too picky about when the review needs to happen can be taught a lot, and fast. But students who need a lot of review and who only derive benefit from very welltimed review will be more difficult to teach. The educational mantra is "every child can learn," but designers of personalized educational software may find that scheduling the educational process for some students is, at the least, more difficult for some than for others. In Cramming, we show that every student can cram. More precisely, we show that, for any set of spacing constraints and any n, it is possible to construct a finite sequence that exhibits bounded learning of order n. Consistent with the discussion that accompanied the definition of bounded learning earlier, the construction assures nothing about whether the sequence can be extended beyond this moment of "expertise" at its end. Finally, also in Cramming, we explore the question of how much can be crammed in a given amount of time. Given a set of spacing constraints and a finite number T, we derive a nontrivial upper bound on those n for which bounded learning of order n is possible using only T time steps. The Recap Method. Here we explore spacing constraints that allow for infinite perfect learning with a rapid learning rate-that is, where the introduction time function, t n , grows slowly. Consider the spacing constraints a k ¼ 2 k and b k ¼ 2 k−1 ðk þ 1Þ. A schedule that allows for infinite perfect learning with respect to these spacing constraints can be described as follows. To find the first ðk þ 1Þ · 2 k entries of the schedule, consider a depth-first postorder traversal of a full binary tree of depth k with 2 k leaves labeled u 1 , u 2 ;…;u 2 k from left to right. (A depth-first postorder traversal of a tree is a particular order for visiting the nodes of a tree, defined as follows. Starting at the root v of the tree, the depth-first postorder traversal is first applied recursively to each subtree below v one at a time; after all these traversals are done, then the root v is declared to be visited.) Begin with an empty sequence. Every time a leaf is visited, append the sequence with the corresponding educational unit. Every time a nonleaf node is visited, append the sequence with the units corresponding to all of the descendant leaves, in left-to-right order. The resulting sequence gives the first ðk þ 1Þ · 2 k entries in the schedule. Thus, using k ¼ 2 we have that the first 12 entries of the schedule are u 1 ;u 2 ;u 1 ;u 2 ;u 3 ;u 4 ;u 3 ;u 4 ;u 1 ;u 2 ;u 3 ;u 4 . We call this schedule "the recap schedule" because it incorporates periodic review of everything that has been learned so far, like a teacher saying "okay, let's recap." In this schedule, the number of time steps between the kth and ðk þ 1Þ st occurrence of any particular unit is always between 2 k and 2 k−1 ðk þ 1Þ, with both bounds actually achieved for each k. This fact-along with the fact that infinitely many units occur infinitely often due to properties of depth-first traversals-establishes that the recap schedule allows for infinite perfect learning with respect to the given spacing constraints. Calculations which establish these facts are shown in the SI Text. Further calculations, also shown in the SI Text, establish that t n grows as Θðn log nÞ in this schedule. More precisely, 1 2 · n · ð⌊ log 2 n⌋ þ 1Þ ≤ t n ≤ n · ð⌊ log 2 n⌋ þ 1Þ: By generalizing the construction of the schedule, using a more general class of trees, we can show that, for a large class of functions rðnÞ, schedules can be constructed that exhibit infinite perfect learning for which t n grows as Θðn · r −1 ðnÞÞ. The class includes functions rðnÞ that grow arbitrarily fast, and so in that sense we can create schedules for which t n grows at a rate that is as close to linear as desired. The downside of these schedules is that they require increasingly lax spacing constraints as the growth rate of t n approaches linearity: The schedules that we construct for which t n grows as Θðn · r −1 ðnÞÞ require b k , as well as b k − a k , to grow as Θðk · rðkÞÞ. Calculations which establish these facts, too, are shown in the SI Text. Superlinearity of the Introduction Time Function. Although our constructions are able to achieve introduction times t n that grow arbitrarily close to linearly in n, we can also show that an actual linear rate of growth is not achievable: For schedules that exhibit infinite perfect learning, the introduction time function t n must be superlinear. More precisely, we show that, for any schedule that exhibits infinite perfect learning with respect to any spacing constraints fða k ;b k Þg, there cannot be a constant c such that t n ≤ cn for all n. To prove this statement, we consider an arbitrary set of spacing constraints fða k ;b k Þg and an arbitrary schedule that exhibits infinite perfect learning with respect to these constraints, and assume for the sake of contradiction that there is a constant c such that t n ≤ cn for all n. Letb k ¼ ∑ k j¼1 b j and let n 0 be any integer such that n 0 >b cþ1 . By our assumption, at least n 0 educational units have been introduced by the time step cn 0 . In general, for any Novikoff et al. PNAS Early Edition | 3 of 6 schedule that exhibits infinite perfect learning, any unit that has been introduced by time step t will have occurred k times by time step t þb k , by the definition ofb k . Thus at least n 0 units will have occurred c þ 1 times by time step cn 0 þb cþ1 . So cn 0 þb cþ1 ≥ ðc þ 1Þn 0 because each time step corresponds to at most one educational unit. Subtracting cn 0 from both sides, we have that b cþ1 ≥ n 0 , which contradicts our choice of n 0 . Thus, there cannot be a constant c such that t n ≤ cn for all n. The Slow Flashcard Schedule. One can describe the construction of the recap schedule without using depth-first traversals or full binary trees, but rather using a deck of flashcards. Doing so will shed some light on the recap schedule, and will also serve as a useful jumping-off point for discussing the very different schedule which is the focus of this section. So we begin our discussion here by revisiting the recap schedule. Imagine a deck of flashcards, with the kth card corresponding to an educational unit u k . Thus the top card corresponds to u 1 , the next card corresponds to u 2 , etc. Then we construct a schedule as follows. At every step, we present to the student the educational unit corresponding to the top card, and then reinsert the card into position 2 k , where k is the number of times we have presented the educational unit corresponding to that card, up to and including this latest time step. Thus first we present u 1 , then we remove it from the deck and reinsert it into position 2 in the deck. Then we present u 2 , then remove it and reinsert it into position 2 in the deck. Then u 1 is again on top and so we present it for a second time and then remove it and reinsert it into position 2 2 ¼ 4. This process produces the recap schedule. In this section, we consider a schedule that is much more difficult to describe explicitly than the recap schedule, but whose construction can similarly be described in terms of a deck of flashcards. Instead of reinserting into position 2 k as above, though, we reinsert into position k þ 1. Carefully applying this rule shows the first few entries of the schedule to be u 1 ;u 2 ;u 1 ;u 2 ;u 3 ;u 1 ;u 3 ;u 2 ; u 4 ;u 3 . Of all schedules that can be constructed with a similar flashcard-reinsertion scheme using some strictly increasing reinsertion function rðkÞ with rð1Þ > 1, it is this schedule, constructed using rðkÞ ¼ k þ 1, which progresses through the deck the slowest. For this reason, we call this schedule "the slow flashcard schedule." In the SI Text, we show that the slow flashcard schedule exhibits infinite perfect learning with respect to the spacing constraints with ða k ;b k Þ ¼ ðk;k 2 Þ. Thus the slow flashcard schedule provides a dramatic alternative to the recap schedule. Whereas b k and b k − a k both grew exponentially in k in the recap schedule, here they grow quadratically and yet still allow for infinite perfect learning. Numerical simulations shown in the SI Text suggest that this schedule in fact exhibits infinite perfect learning even with respect to the much tighter spacing constraints with ða k ;b k Þ ¼ ðk;2kÞ. If that is the case, the contrast with the recap schedule would be even more stark. The trade-off for this slow growth in b k is the speed at which the knowledge base grows. Whereas t n , the time needed for the knowledge base to achieve size n, grew as Θðn log nÞ in the recap schedule, here it is bounded below by Ωðn 2 Þ. A proof of this fact can be found in the SI Text, along with numerical evidence that it in fact grows as Θðn 2 Þ. The spacing constraints in The Recap Method and The Slow Flashcard Schedule are tailored to allow for existence proofs that certain bounds on t n , b k , and b k − a k can be achieved in the context of infinite perfect learning. The methods used to describe the schedules, though, suggest general principles for how to construct schedules with desirable properties. Moreover, we note that the schedules constructed are relevant to any set of spacing constraints that are more relaxed than the given ones: If a schedule exhibits infinite perfect learning with respect to spacing constraints fða k ;b k Þg, then it also exhibits infinite perfect learning with respect to fða 0 k ;b 0 k Þg when a 0 k ≤ a k and b 0 k ≥ b k for all k. In the next section, Flexible Students, we begin with a general class of students and build schedules tailored to each individual student in the class. Flexible Students. What if the student did not need to wait at all in order to derive benefit from studying? In other words, what if a k ¼ 1 for all k? In this case, we can use a technique for constructing schedules that we call "hold-build": sequencing the educational units that are known to the student in a "holding pattern" so that they meet the spacing constraints, while showing new educational units in quick repetition (thereby "building" them up). The only assumptions that are needed for the construction, besides a k ≡ 1, are that b 1 ≥ 2 and that b k → ∞. (Note that b k is already required to be weakly increasing.) We define the sequence HB m to be the infinite sequence that starts with u m , contains u m in every other entry, and cycles through units u 1 ;…;u m−1 in the remaining entries. So, for example, HB 2 ¼ u 2 ;u 1 ;u 2 ;u 1 ;u 2 ;u 1 ;… HB 3 ¼ u 3 ;u 1 ;u 3 ;u 2 ;u 3 ;u 1 ;u 3 ;u 2 ;u 3 ;u 1 ;… HB 4 ¼ u 4 ;u 1 ;u 4 ;u 2 ;u 4 ;u 3 ;u 4 ;u 1 ;u 4 ;u 2 ;u 4 ;… Now, consider an arbitrary set of spacing constraints such that a k ≡ 1, b 1 ≥ 2, and b k → ∞. For ease of discussion, we say that an educational unit is at level k when it has been shown exactly k times. We construct the schedule that assures infinite perfect learning as follows. First, present unit u 1 . Then present units according to HB 2 . So far so good; so long as units are presented according to HB 2 , we know the spacing constraints will be met, because b k ≥ 2 for all k. Meanwhile, the levels for u 1 and u 2 can be built up without bound. Continue HB 2 as long as necessary until it is feasible to move on to HB 3 . In other words, show enough of HB 2 so that if the schedule up to that point were followed by an indefinite run of HB 3 , then the spacing constraints would be met. This condition is guaranteed to be true after a finite number of time steps because b k → ∞ and HB 2 is periodic. Thus, once enough of HB 2 has been shown, we show as much of HB 3 as necessary until we can afford to move on to HB 4 . Then we show as much of HB 4 as necessary until we can afford to move on to HB 5 , and we continue building the schedule like this indefinitely. The schedule formed by concatenating hold-build patterns in this way assures infinite perfect learning, and it applies to any set of spacing constraints with a k ≡ 1, b 1 ≥ 2, and b k → ∞. Thus we actually have a class of spacing constraints where infinite perfect learning is possible and yet b k can grow arbitrarily slowly. The trade-off for an exceedingly slow-growing b k will again be a fast-growing t n , corresponding to a slow rate of learning. The exact rate will depend on the exact rate of growth of b k . To give a concrete example of this hold-build construction and an accompanying calculation of t n , we can consider the simple case where b k ¼ k þ 1. (Note that, because we only require that b k be weakly increasing, there are much slower-growing choices for b k than this one.) Then, by carrying out the construction above, we have that the sequence is u 1 ;u 2 ;u 1 ;u 2 ;u 1 ;u 2 |fflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflffl} HB 2 ;u 3 ;u 1 ;u 3 ;u 2 ;u 3 ;u 1 ;u 3 ;u 2 ;u 3 |fflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl ffl{zfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl ffl} with 4k − 3 time steps spent in HB k for every k. Thus, because u i will be introduced one time step after finishing the HB i−1 part of the schedule, we have that The idea behind the hold-build construction, namely the method of putting some units in a holding pattern while others are being "built up," could readily be used to construct schedules assuring infinite perfect learning for many sets of spacing constraints with a k > 1 as well (or spacing constraints with b 1 ¼ 1, for that matter). It is a tool that can be used to tailor educational processes to model students in general. The Finicky Slow Student. We now give a set of spacing constraints fða k ;b k Þg for which no schedule can exhibit infinite perfect learning. They are simply the constraints defined by a k ¼ b k ¼ k. We call this set of constraints "the finicky slow student" because b k − a k is so small, and because b k grows so slowly as a function of k. We show that no schedule can exhibit infinite perfect learning with respect to the finicky slow student. Suppose, for the sake of contradiction, that there were a schedule that exhibited infinite perfect learning with respect to the finicky slow student. We say that a schedule incorporates educational unit u i if the unit occurs infinitely many times, and if the sequence of occurrences satisfies the spacing constraints. Thus, given the particulars of the finicky slow student, if a unit u i is incorporated, and if it first occurs at step τ, then it must also occur at steps τ þ 1, τ þ 3, τ þ 6, τ þ 10;…. By assumption, the schedule incorporates infinitely many educational units. We can assume, without loss of generality, that educational unit u 1 is incorporated and that its first occurrence is at time step τ 0 ¼ 0. (Letting time start at zero here allows for cleaner calculations.) Then we know that u 1 also occurs at precisely the steps τ 1 , τ 2 , τ 3 ;…, where τ i ¼ ∑ i k¼1 a k . It will be sufficient to show that no other unit can be incorporated without creating a scheduling conflict-in other words, without needing to eventually be scheduled at a step of the form τ i . Suppose another unit, call it u 2 , were incorporated, with its first occurrence at step s 0 . Then we know that u 2 must also occur at precisely the steps s 1 , s 2 , s 3 ;…, where s i ¼ s 0 þ ∑ i k¼1 a k . We show that there must be some step common to both sequences fs i g and fτ i g. Thus we will have a contradiction because, at most, one educational unit can appear in each entry of the schedule. We begin by noting that s i − τ i ¼ s 0 for all i, and that Thus for sufficiently large k, we have that τ kþ1 > s k . Now let m be the smallest number such that τ mþ1 > s m . We know m ≥ 1, because τ 0 ¼ 0 and τ 1 ¼ 1 by construction. We claim that τ m ¼ s m−1 . If τ m > s m−1 , then m would not be the smallest number such that τ mþ1 > s m (because then m − 1 would also qualify), so τ m ≯s m−1 . If τ m < s m−1 , then we have that τ m < s m−1 < s m < τ mþ1 , which implies that s m − s m−1 ≤ τ mþ1 − τ m − 2, because all s i and τ i are integer valued. Thus a m ≤ a mþ1 − 2, so a mþ1 − a m ≥ 2, which is not possible because a kþ1 − a k ¼ 1 for all k. So τ m ≮s m−1 . Thus we have that τ m ¼ s m−1 , which is a contradiction, of course, because only one educational unit can be scheduled for any given time step. Thus no schedule can exhibit infinite perfect learning with respect to the finicky slow student; in fact, the finicky slow student does not even allow for the incorporation of more than one educational unit. This proof holds not only for the spacing constraints , where f ðkÞ is an integer sequence such that f ð1Þ ¼ 1, f ðk þ 1Þ − f ðkÞ ∈ f0;1g, and f ðkÞ → ∞. The exact choice doesn't matter; the finickiness (a k ¼ b k ) and the slowness [f ð1Þ ¼ 1 and f ðk þ 1Þ − f ðkÞ ∈ f0;1g] are sufficient to carry out the proof as written, but with the final argument using a kþ1 − a k ≤ 1 instead of a kþ1 − a k ¼ 1. Cramming. The focus up until now has been on infinite perfect learning, but there could be less ambitious goals for a student. We turn our attention now to cramming. At the end of this section, we address the question of how much cramming can be done in a given amount of time. We begin here with a positive result, showing that for every positive integer n and every set of spacing constraints with b k → ∞, there exists a sequence that achieves bounded learning of order n. We consider an arbitrary set of spacing constraints with b k → ∞ and proceed by induction on n. It is clear that bounded learning is possible for n ¼ 1; the sequence consisting simply of u 1 satisfies the definition. Now, let S n be a sequence of length T n that achieves bounded learning of order n. To complete the induction, we construct a new sequence, S nþ1 of length T nþ1 , that achieves bounded learning of order n þ 1. Recall from Flexible Students that the level of an educational unit at time t in a sequence is the number of times it has appeared prior to time t. The basic idea behind the construction of S nþ1 is to start by building up the level of u 1 until it is at a level m such that b m > T n . Then we use the next T n steps to present units u 2 , u 3 ;…;u nþ1 according to the sequence S n . When that is done, the time limit of b m has still not been reached for u 1 , and hence the sequence satisfies the definition of bounded learning of order n þ 1. Formally, let m be the smallest integer such that b m > T n . Then present unit u 1 at time t ¼ 0 and at times t ¼ ∑ j i¼1 a i for j ¼ 1;2;…;m − 1. Present a blank in the sequence at every other time step in between. Then, starting at time t ¼ 1 þ ∑ m−1 i¼1 a i , present units u 2 ;u 3 ;…;u nþ1 according to the T n elements of the sequence S n . This sequence, through time T nþ1 ¼ T n þ ∑ m−1 i¼1 a i , is our new sequence S nþ1 . By construction it satisfies the conditions of bounded learning of order n þ 1. By induction, then, bounded learning of order n is possible for all positive integers n for any set of spacing constraints with b k → ∞. In the construction above, it is entirely possible that one or more units would begin to violate the spacing constraints even one time step later. Little is assured other than the educational units having met the scheduling constraints up to a certain time step. We call this sort of construction cramming because it presents the material with a particular target time in view and without regard to the scheduling of material after this target time, like a student cramming for a final exam who doesn't worry about how much will be retained after the test. Condition (ii) of our definition of bounded learning models the notion of studying up to a point in time and then being able to remember everything that was studied for at least one more time step, as if there were a quiz lasting one time step which would occur in the time step immediately following the cramming sequence. We could similarly model the notion of a quiz that lasts d time steps by requiring that if a unit's last occurrence is s time steps from the end of the sequence, and the unit occurs a total of k times in the sequence, then s þ d must be less than or equal to b k . We note that our results regarding cramming sequences could be adapted to such an alternative model. We turn now to the issue of how much can be crammed in a given amount of time. Given a set of spacing constraints fða k ;b k Þg, and a positive integer T, we can put an upper bound on the numbers n for which bounded learning of order n is possible in T time steps. If we let mðiÞ denote the smallest integer k such that b k ≥ i, then it can be shown that n must satisfy Novikoff et al. PNAS Early Edition | 5 of 6 ∑ n i¼1 mðiÞ ≤ T and ∑ mðnÞ−1 j¼1 a j þ n ≤ T. Each inequality implicitly bounds n from above. These bounds reflect the constraints imposed by the limited number of time steps available, and the notions that fa k g and fb k g represent limitations on how fast the level of an educational unit can be built up and how long educational units can be remembered. Details can be found in the SI Text. Despite the negative connotations associated with cramming, the basic idea can actually be useful in a number of settings in real life. A traveler may only care to learn a language enough to travel in a foreign country just once, for example, or a performer may only need to have a certain skill set on the day of a performance and not necessarily after that. Perhaps educational software of the future will have tunable parameters that allow the student (or teacher or parent) to set the goal of the educational process. This way the software may not only adapt to the natural abilities of the students, but also to their personal goals. The possibilities for future work seem limitless. A more complete theory of infinite perfect learning could be one goal. Such a theory would include more techniques for constructing educational processes tailored to students, and a more complete theory relating a k and b k to the maximum rate at which the model student can accrue knowledge. A major goal should be a truly adaptive educational process: one that adapts to the student in real time. For example, in this paper we model the educational process as a sequence designed to satisfy a set of constraints fixed in advance, but an alternate approach would be to test the student's knowledge throughout the process, and for the schedule to be controlled by an online algorithm that chooses the next unit based on the answers the student has given. Such a system would model the process of a teacher observing student progress before deciding what to teach next. Modeling this situation would be an exciting challenge. The interaction between the two online algorithms, one modeling the student and the other modeling the teacher, promises to be complex and fascinating, and hopefully enlightening and useful to future designers and engineers of educational software. There is much opportunity here for mathematical modeling, theoretical calculations, and numerical simulations that shed light on what makes an effective teacher and how educational software can adapt in real time to user behavior. Another area for future work is the design and analysis of models that are tailored to specific subjects. Perhaps a model involving a network of educational units could be used to investigate the phenomenon that it is often easier to learn a set of facts that somehow "reinforce" each other than a set of unrelated facts. Introducing relationships between educational units calls for new models of the student's reception of the units, which in turn call for different educational processes. Yet another avenue of research is empirical work. The techniques and intuitions gained from theoretical work should be put to use to create actual educational software. Then data from real students can be collected and the process of using the data to validate and refine the models can begin. Finally, the mathematics of managing spacing constraints in sequences could find additional applications beyond those considered above, for example, to task management in parallel processing or the study of multitasking in humans. The models presented in this paper are simple and theoretical. Designers of educational software will likely need to implement models and algorithms that are more complex and tailored to the educational content being delivered. It is our hope that work on simple theoretical models will provide the foundations of intuition for designers of educational software, in much the same way that algorithmic game theory does for engineers who work in online ad auctions and other related fields. With the current boom in educational software-not to mention the humanoid robot teacher industry (14)-it is clear that the time has come to develop a theory of algorithmic education.
One notable work in this regard is that of Novikoff et al. REF , who propose a theoretical framework for spaced repetition based on a set of deterministic operations on an infinite string of content pieces.
Education of a model student
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Computer Science Medicine