First adaptable spaced repetition algorithm: Algorithm SM-4
This text is part of: "History of spaced repetition" by Piotr Wozniak (June 2018)
Introducing flexible interval function
SuperMemo 2 was great. Its simple algorithm has survived in various mutations to this day in popular apps such as Anki or Mnemosyne. However, the algorithm was dumb in the sense that there was no way of modifying the function of optimum intervals. The findings of 1985 were set in stone. Memory complexity and stability increase were expressed with the same single number: E-factor. It is a bit like using a single lever in a bike for two functions: (1) to change gears, and (2) to change the direction of driving.
Individual items could adapt the spacing of review by changes to their estimated difficulty. Those changes could compensate for errors in the function of optimum intervals. Even if the algorithm was slow to converge on the optimum, in theory, it was convergent. The main flaw was that, in Algorithm SM-2, new items would not benefit from the experience of old items.
Algorithm SM-4 was the first attempt to arm SuperMemo with universal adaptability. It was completed in February 1989. In the end, adaptability was too slow to show up, but inspiration gathered with Algorithm SM-4 was essential for further progress, esp. in understanding the problem of stability-vs-accuracy in spaced repetition. In short, Algorithm SM-4 was too stable to be accurate. This was quickly remedied in Algorithm SM-5 just 7 months later. Here is an excerpt from my Master's Thesis to explain the details:
The main fault of Algorithm SM-2 seems to have been the arbitrary shape of the function of optimal intervals. Although very effective in practice and confirmed by years of experimental repetitions, this function could not claim scientifically proved validity, nor could it detect the overall impact of few day variations of optimal intervals on the learning process. Bearing these flaws in mind I decided to employ routine SuperMemo repetitions in the validation of the function of optimal intervals!
Using optimization procedures like those applied in finding E-Factors I wanted the program to correct the initially proposed function whenever corrections appeared justified.
To achieve this goal, I tabulated the function of optimal intervals.
Figure: Matrix of optimal intervals showed up in SuperMemo 4 in 1989, and survived to this day in SuperMemo 17 with few changes. In SuperMemo 4, it was the source of information for optimum spacing. In SuperMemo 17, it is derived from the OF matrix generated by Algorithm SM-15 that is used concurrently with Algorithm SM-17. The picture presents a matrix from SuperMemo 5, and shows a significant departure from the original values of the matrix. In SuperMemo 4, adaptations proceeded at much slower pace
Particular entries of the matrix of optimal intervals (later called the OI matrix) were initially taken from the formulas used in Algorithm SM-2.
SuperMemo 4 (February 1989), in which the new solution was implemented, used the OI matrix to determine values of inter-repetition intervals:
I(n):=OI(n,EF)
where:
- I(n) - the n-th inter-repetition interval of a given item (in days),
- EF - E-Factor of the item,
- OI(n,EF) - the entry of the OI matrix corresponding to the n-th repetition and the E-Factor EF.
However, the OI matrix was not fixed once for all. In the course of repetitions, particular entries of the matrix were increased or decreased depending on the grades. For example, if the entry indicated the optimal interval to be X and the used interval was X+Y while the grade after this interval was not lower than four, then the new value of the entry would fall between X and X+Y.
Thus the values of the OI entries in the equilibrium state should settle at the point where the stream of poor-retention items balances the stream of good-retention items in its influence on the matrix.
As a consequence, SuperMemo 4 was intended to yield an ultimate definition of the function of optimal intervals.Rigid SuperMemo 4
It did not take me long to realize that the verification-correction cycle in the new algorithm was too long. It was not much different than running the 1985 eperiment on the computer. To determine decade-long intervals, I needed a decade to pass to test the outcomes of the review. This led to Algorithm SM-5 seven months later. Here is the problem with Algorithm SM-4 as described in my Master's Thesis:
Algorithm SM-4 was implemented in SuperMemo 4 and was used between March 9, 1989 and October 17, 1989. Although the main concept of modifying the function of optimal intervals seemed to be a major step forward, the implementation of the algorithm was a failure. The basic insufficiency of the algorithm appeared to result from formulas applied in modification of the OI matrix.
There were two the most striking flaws:
- modifications were too subtle to rearrange the OI matrix visibly in a reasonably short time,
- for longer inter-repetition intervals, the effect of modification had to wait very long before being steadily fixed, i.e. it took quite a lot of time before the result of a modification of a few-month-long interval could be seen and corrected if necessary
After seven months of using Algorithm SM-4, the OI matrices of particular databases did not look much different from their initial states. One could explain this fact by the correctness of my earlier predictions concerning the real values of the optimal inter-repetition intervals, however, as it was later proved by means of Algorithm SM-5, the actual reason of the stability of the matrices was the flaws in the optimization formulae.
As far as acquisition rate and retention are concerned, there is no reliable evidence that Algorithm SM-4 brought any progress. Slight improvement could as well be related to general betterment of the software and improvement in item formulation principlesRemnants of SuperMemo 4 in new SuperMemos
Interestingly, you can still see the matrix of optimum intervals in newer versions of SuperMemo. The matrix is not used by the algorithm, however, it is displayed in SuperMemo statistics as it informs the user about the impact of complexity on the length of intervals in the future.
If you compare a matrix produced by SuperMemo 5 in 8 months of use, you will notice a significant similarity to the matrix produced in two decades of using Algorithm SM-8:
Figure: Matrix of optimum intervals is no longer used in Algorithm SM-17. However, it can still be generated with procedures of Algorithm SM-15. The columns correspond with easiness of the material expressed as A-Factor. The rows correspond with memory stability expressed as repetition category
Algorithm SM-4
Here is the outline of Algorithm SM-4 as described in my Master's Thesis:
Algorithm SM-4 used in SuperMemo 4.0:
- Split the knowledge into smallest possible items
- With all items associate an E-Factor equal to 2.5
- Tabulate the OI matrix for various repetition numbers and E-Factor categories
- Use the following repetition spacing to obtain the initial OI matrix:
- OI(1,EF):=1
- OI(2,EF):=6
- for n>2 OI(n,EF):=OI(n-1,EF)*EF
- where:
- OI(n,EF) - optimal inter-repetition interval after the n-th repetition (in days) for items with E-Factor equal EF,
- Use the OI matrix to determine inter-repetition intervals:
- I(n,EF):=OI(n,EF)
- where:
- I(n,EF) - the n-th inter-repetition interval for an item whose E-Factor equals EF (in days),
- OI(n,EF) - the entry of the OI matrix corresponding to the n-th repetition and the E-Factor EF
- After each repetition estimate the quality of the repetition response in the 0-5 grade scale (see Algorithm SM-2).
- After each repetition modify the E-Factor of the recently repeated item according to the formula:
- EF':=EF+(0.1-(5-q)*(0.08+(5-q)*0.02))
- where:
- EF' - new value of the E-Factor,
- EF - old value of the E-Factor,
- q - quality of the response in the 0-5 grade scale.
- If EF is less than 1.3 then let EF be 1.3.
- After each repetition modify the relevant entry of the OI matrix.
- An exemplary formula could look as follows (the actual formula used in SuperMemo 4 was more intricate):
- OI':=interval+interval*(1-1/EF)/2*(0.25*q-1)
- OI:=(1-fraction)*OI+fraction*OI'
- where:
- OI - new value of the OI entry,
- OI' - auxiliary value of the OI entry used in calculations,
- OI - old value of the OI entry,
- interval - interval used before the considered repetition (i.e. the last used interval for the given item),
- fraction - any number between 0 and 1 (the greater it is the faster the changes of the OI matrix),
- EF - E-Factor of the repeated item,
- q - quality of the response in the 0-5 grade scale.
- Note that for q=4 the OI does not change and that for q=5 the OI increases 4 times less than it decreases for q=0.
- Note also that the maximum change of the OI equals (I(n)-I(n-1))/2 in terms of the repetition spacing used in Algorithm SM-2 (i.e. (OI-OI/EF)/2).
- If the quality response was lower than 3 then start repetitions for the item from the beginning without changing the E-Factor.
- After each repetition session of a given day repeat again all the items that scored below four in the quality assessment. Continue the repetitions until all of these items score at least four
Problems with interval matrix
In addition to slow convergence, Algorithm SM-4 showed that the use of matrix of intervals leads to several problems that could easily be solved by replacing intervals with O-factors. Those additional flaws led to a fast implementation of Algorithm SM-5 yet in 1989. Here is a short analysis that explained the flaws in the use of the matrix of optimum intervals:
- In the course of repetition it may happen that one of the intervals will be calculated as shorter than the preceding one. This is certainly inconsistent with general assumptions leading to the SuperMemo method. Moreover, validity of such an outcome was refuted by the results of application of the Algorithm SM-5. This flaw could be prevented by disallowing intervals to increase or drop beyond certain values, but such an approach would tremendously slow down the optimization process interlinking optimal intervals by superfluous dependencies. The discussed case was indeed observed in one of the databases. The discrepancy was not eliminated by the end of the period in which the Algorithm SM-4 was used despite the fact that the intervals in question were only two weeks long
- E-Factors of particular items are constantly modified thus in the OI matrix an item can pass from one difficulty category to another. If the repetition number for that item is large enough, this will result in serious disturbances of the repetitory process of that item. Note that the higher the repetition number, the greater the difference between optimal intervals in neighboring E-Factor category columns. Thus if the E-Factor increases the optimal interval used for the item can be artificially long, while in the opposite situation the interval can be much too short