Spaced Repetition SM2

Este é o código-fonte em javascript do algoritmo spaced repetition. Segundo o Wikipédia. Futuramente irei refatorá-lo para as linguagens JAVA e C++.

Cite

Repetição espaçada é uma técnica de aprendizado baseada em evidências usualmente utilizada com flashcards (cartões de memorização). Flashcards recém-introduzidos e mais difíceis são mostrados com maior frequência, enquanto os mais antigos e menos difíceis são mostrados com menor frequência para explorar o efeito de espaçamento. Foi comprovado que o uso de repetição espaçada aumenta a taxa de aprendizado
Fonte: https://pt.wikipedia.org/wiki/Repetição_espaçada

Este código foi obtido a partir de um plugin do obsidian no github e serve de ponto de partida para compreender o funcionamento deste algoritmo. Veja mais a frente os casos de teste.

Fonte: https://www.stephenmwangi.com/obsidian-spaced-repetition/flashcards/#single-line-basic-remnote-style
Algoritmo: https://www.stephenmwangi.com/obsidian-spaced-repetition/algorithms/

Note

(It's the same as that used for flashcards - apart from the PageRanks)

The algorithm is a variant of Anki's algorithm which is based on the SM-2 algorithm.
It supports ternary reviews i.e. a concept is either hard, good, or easy at the time of review.
initial ease is weighted (using max_link_factor) depending on the average ease of linked notes, note importance, and the base ease.
- if link_count > 0: initial_ease = (1 - link_contribution) * base_ease + link_contribution * average_ease
  - link_contribution = max_link_factor * min(1.0, log(link_count + 0.5) / log(64)) (cater for uncertainty)
- The importance of the different concepts/notes is determined using the PageRank algorithm (not all notes are created equal xD)
  - On most occasions, the most fundamental concepts/notes have higher importance
If the user reviews a concept/note as:
- easy, the ease increases by 20 and the interval changes to old_interval * new_ease / 100 * 1.3 (the 1.3 is the easy bonus)
- good, the ease remains unchanged and the interval changes to old_interval * old_ease / 100
- hard, the ease decreases by 20 and the interval changes to old_interval * 0.5
  - The 0.5 can be modified in settings
  - minimum ease = 130
- For 8 or more days:
  - interval += random_choice({-fuzz, 0, +fuzz})
    - where fuzz = ceil(0.05 * interval)
    - Anki docs: > "[...] Anki also applies a small amount of random “fuzz” to prevent cards that were introduced at the same time and given the same ratings from sticking together and always coming up for review on the same day."
The scheduling information is stored in the YAML front matter

export enum ReviewResponse {
    Easy,
    Good,
    Hard,
    Reset,
}

export interface SRSettings {
    // algorithm
	baseEase: number;
	lapsesIntervalChange: number;
	easyBonus: number;
	maximumInterval: number;
	maxLinkFactor: number;
}

export const DEFAULT_SETTINGS: SRSettings = {
    // algorithm
    baseEase: 250,
    lapsesIntervalChange: 0.5,
    easyBonus: 1.3,
    maximumInterval: 36525,
    maxLinkFactor: 1.0,
};

export function schedule(
    response: ReviewResponse,
    interval: number,
    ease: number,
    delayBeforeReview: number,
    settingsObj: SRSettings,
    dueDates?: Record<number, number>,
): Record<string, number> {

    delayBeforeReview = Math.max(0, Math.floor(delayBeforeReview / (24 * 3600 * 1000)));  // 1 dia

  
    if (response === ReviewResponse.Easy) {
        ease += 20;
        interval = ((interval + delayBeforeReview) * ease) / 100;
        interval *= settingsObj.easyBonus;
    } else if (response === ReviewResponse.Good) {
        interval = ((interval + delayBeforeReview / 2) * ease) / 100;
    } else if (response === ReviewResponse.Hard) {
        ease = Math.max(130, ease - 20);
        interval = Math.max(
            1,
*          (interval + delayBeforeReview / 4) * settingsObj.lapsesIntervalChange,
        );
    }

    // replaces random fuzz with load balancing over the fuzz interval

    if (dueDates !== undefined) {
        interval = Math.round(interval);
        if (!Object.prototype.hasOwnProperty.call(dueDates, interval)) {
            dueDates[interval] = 0;
        } else {
            // disable fuzzing for small intervals
            if (interval > 4) {
                let fuzz = 0;
                if (interval < 7) fuzz = 1;
                else if (interval < 30) fuzz = Math.max(2, Math.floor(interval * 0.15));

                else fuzz = Math.max(4, Math.floor(interval * 0.05));
                const originalInterval = interval;
                outer: for (let i = 1; i <= fuzz; i++) {

                    for (const ivl of [originalInterval - i, originalInterval + i]) {

                        if (!Object.prototype.hasOwnProperty.call(dueDates, ivl)) {
                            dueDates[ivl] = 0;
                            interval = ivl;
                            break outer;
                        }
                        if (dueDates[ivl] < dueDates[interval]) interval = ivl;
                    }
                }
            }
        }
        dueDates[interval]++;
    }

    interval = Math.min(interval, settingsObj.maximumInterval);
    return { interval: Math.round(interval * 10) / 10, ease };

}

Quando nos deparamos com um código que pouco entendemos, o melhor lugar para iniciar a análise são os casos de testes unitário. Veja abaixo alguns deles.


test("Test reviewing with default settings", () => {
    expect(
        schedule(ReviewResponse.Easy, 1, DEFAULT_SETTINGS.baseEase, 0, DEFAULT_SETTINGS, {}),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase + 20,
        interval: 4,
    });

    expect(
        schedule(ReviewResponse.Good, 1, DEFAULT_SETTINGS.baseEase, 0, DEFAULT_SETTINGS, {}),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase,
        interval: 3,
    });

    expect(
        schedule(ReviewResponse.Hard, 1, DEFAULT_SETTINGS.baseEase, 0, DEFAULT_SETTINGS, {}),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase - 20,
        interval: 1,
    });
});

test("Test reviewing with default settings & delay", () => {
    const delay = 2 * 24 * 3600 * 1000; // two day delay
    expect(
        schedule(ReviewResponse.Easy, 10, DEFAULT_SETTINGS.baseEase, delay, DEFAULT_SETTINGS, {}),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase + 20,
        interval: 42,
    });

    expect(
        schedule(ReviewResponse.Good, 10, DEFAULT_SETTINGS.baseEase, delay, DEFAULT_SETTINGS, {}),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase,
        interval: 28,
    });

    expect(
        schedule(ReviewResponse.Hard, 10, DEFAULT_SETTINGS.baseEase, delay, DEFAULT_SETTINGS, {}),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase - 20,
        interval: 5,
    });
});

test("Test load balancing, small interval (load balancing disabled)", () => {
    const dueDates = {
        0: 1,
        1: 1,
        2: 1,
        3: 4,
    };
    expect(
        schedule(ReviewResponse.Good, 1, DEFAULT_SETTINGS.baseEase, 0, DEFAULT_SETTINGS, dueDates),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase,
        interval: 3,
    });
    expect(dueDates).toEqual({
        0: 1,
        1: 1,
        2: 1,
        3: 5,
    });
});

test("Test load balancing", () => {
    // interval < 7
    let dueDates: Record<number, number> = {
        5: 2,
    };
    expect(
        schedule(ReviewResponse.Good, 2, DEFAULT_SETTINGS.baseEase, 0, DEFAULT_SETTINGS, dueDates),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase,
        interval: 4,
    });
    expect(dueDates).toEqual({
        4: 1,
        5: 2,
    });

    // 7 <= interval < 30
    dueDates = {
        25: 2,
    };


    expect(
        schedule(ReviewResponse.Good, 10, DEFAULT_SETTINGS.baseEase, 0, DEFAULT_SETTINGS, dueDates),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase,
        interval: 24,
    });
    expect(dueDates).toEqual({
        24: 1,
        25: 2,
    });

    // interval >= 30
    dueDates = {
        2: 5,
        59: 8,
        60: 9,
        61: 3,
        62: 5,
        63: 4,
        64: 4,
        65: 8,
        66: 2,
        67: 10,
    };
    expect(
        schedule(ReviewResponse.Good, 25, DEFAULT_SETTINGS.baseEase, 0, DEFAULT_SETTINGS, dueDates),
    ).toEqual({
        ease: DEFAULT_SETTINGS.baseEase,
        interval: 66,
    });
    expect(dueDates).toEqual({
        2: 5,
        59: 8,
        60: 9,
        61: 3,
        62: 5,
        63: 4,
        64: 4,
        65: 8,
        66: 3,
        67: 10,
    });
});

test("Test textInterval - desktop", () => {
    expect(textInterval(1, false)).toEqual("1 day(s)");
    expect(textInterval(41, false)).toEqual("1.3 month(s)");
    expect(textInterval(366, false)).toEqual("1 year(s)");
    expect(textInterval(1000, false)).toEqual("2.7 year(s)");
});

test("Test textInterval - mobile", () => {
    expect(textInterval(1, true)).toEqual("1d");
    expect(textInterval(41, true)).toEqual("1.3m");
    expect(textInterval(366, true)).toEqual("1y");
    expect(textInterval(1000, true)).toEqual("2.7y");
});

test("Test new cards", () => {
    expect(textInterval(undefined, false)).toEqual("New");
});