优化间隔重复调度的随机最短路径算法

下载原文：ElMRdGODmozAGHxkUVDc2iXCnCe

2022_A Stochastic Shortest Path Algorithm for Optimizing Spaced Repetition Scheduling_Ye et al.pdf

摘要

间隔重复是一种记忆技术，通过遵循复习计划可以有效地形成长期记忆。为了提高记忆效率，间隔重复的调度器需要对学生的长期记忆进行建模，并优化复习的成本。我们收集了 2.2 亿个具有时间序列特征的学生记忆行为日志，并建立了具有马尔可夫属性的记忆模型。基于该模型，我们设计了一个间隔重复调度器，通过随机的最短路径算法保证复习成本最小。实验结果表明，与最先进的方法相比，性能提高了 12.6％。该调度器已成功部署在在线语言学习应用程序墨墨背单词（MaiMemo）中，以帮助数百万学生。

关键词

• 间隔重复、最优控制、语言学习

1 介绍

为了形成长期记忆，学生应该反复复习所学材料。根据艾宾浩斯的初级记忆实验，复习过程中的重复次数、重复间隔和其他因素会影响一个人的记忆。这些因素在大量的心理学实验中得到了研究，并被总结为一些效应，如间隔效应和滞后效应。间隔重复是一种采用这些效应来提高记忆效率的记忆技术。通过对每一次复习的间隔，它可以有效地提高长期记忆。间隔重复对第二语言的学习有明显的效果，许多研究表明，间隔重复在医学、统计学、历史等领域也能发挥作用。

在大多数间隔重复的实践中，材料是以抽认卡的形式呈现的，如图 1 所示，用简单的时间表确定每张抽认卡的复习时间。设计一个更有效的间隔性复习安排算法的问题有着丰富的历史。从 Leitner 盒到第一个间隔重复软件 SuperMemo，他们都是以设计者的经验和个人实验为基础，使用简单的规则启发式算法。许多间隔重复软件（Anki, Mnemosyne 等）仍然使用这些算法。由于硬编码的参数和缺乏理论证明，这些算法不能适应不同的学习者和材料。同时，它们的性能也不能得到保证。

随着电子学习平台的普及，可以收集大量关于学生复习的数据。它使研究人员能够设计出可训练的、自适应的、有保障的算法。在墨墨背单词这个支持学习者记忆词汇的语言学习应用中，一个高效的间隔重复调度算法可以节省数百万用户的时间，并帮助他们记住更多的单词。最近，一些作品采用机器学习来确定最佳复习时间。然而，由于以下三个原因，这些方法并不适合我们的条件。

• 缺少时间序列信息：一些作品，如 HLR（半衰期回归）模型和 EFC（指数遗忘曲线）模型，使用遗忘曲线将回忆的概率与上次复习后的时间联系起来。但他们忽略了时间间隔对记忆强度的影响。在他们的模型中，记忆强度是一个重复次数的函数。根据间隔效应和我们收集的数据，复习的间隔对长期记忆的形成有很大影响。
• 缺少用户感知的优化目标：HLR 和基于它的改进的 C-HLR 模型，旨在准确预测记忆的回忆概率。减少复习的压力，最大限度地提高记忆力，以及其他与用户有关的指标都没有考虑。
• 缺少可解释性。一些基于深度强化学习的算法对设计者来说是一个黑盒子，缺乏可解释性。在学生的模型调度复习过程中提供解释，对教育研究有帮助。

在本文中，我们根据收集到的数以百万计的记忆数据，建立了用于模拟用户长期记忆的 DHP（Difficulty-Halflife-P(recall)）模型。我们设定了一个具有实际意义的明确的优化目标：使用户形成长期记忆的记忆成本最小化。为了实现这一目标，我们提出了一种新颖的间隔重复调度算法，即 SSP-MMC（Stochastic-Shortest-Path-Minimize-Memorization-Cost）。

我们的工作为间隔重复调度器提供了一个更接近自然环境的长期记忆模型，并通过现实世界的数据进行了测试。我们找到了一个可能的间隔重复调度的优化问题和相应的最优方法。我们公开了数据和软件工具，以方便复制和后续研究（见数据与代码一节）。综上所述，本文的主要贡献是：

• 建立并公开发布我们的间隔重复日志数据集，这是第一个包含时间序列信息的数据集。
• 据我们所知，这是第一个采用时间序列特征来模拟长期记忆的工作。
• 实证结果表明，在最小化记忆成本方面，SSP-MMC 优于最先进的基线。

2 相关工作

在优化间隔重复方面已经有大量的文献，从建模和预测学习者的长期记忆到基于相关记忆模型设计优化调度算法。

间隔重复和记忆模型。适应性思维特征-理性模型（ACT-R）是一种认知体系结构，其包含了陈述性记忆模块，假设每次练习会尝试一条幂函数遗忘曲线，多个幂函数近似了间隔重复后的遗忘曲线。而多尺度语境模型（MCM），假设每次练习都会产生一条指数函数遗忘曲线，使用多个指数函数叠加来近似遗忘曲线。半衰期回归模型（HLR）是一个可训练的间隔重复模型。为了预测学习者对特定材料的记忆半衰期，在线语言学习平台 Duolingo 的研究者使用他们的用户日志数据进行训练。Ahmed Zaidi 等人在该模型上进行了改进，将神经网络引入了该模型，并考虑了更多心理学、语言学相关的特征。但这些模型没有考虑学习者对单词记忆的反馈顺序和反馈之间的间隔，缺失了时序信息。

用间隔重复模型进行优化调度。为了平衡新材料的学习和已学材料的复习，Reddy 等人提出了莱特纳系统的排队网络模型，并设计了一种启发式算法来安排复习。然而，该算法是基于 EFC 模型，将记忆强度作为复习次数和莱特纳箱位置的函数，而不是重复之间的间隔。Tabibian 等人引入了标记的时间点过程来表示间隔的重复，并将调度视为一个最佳控制问题。他们想出了召回概率和评论数量之间的权衡。由于数据集的限制，他们模型中的遗忘率只受召回结果的影响。在 Hunziker 等人的工作中，优化间隔重复的调度归结为随机序列优化问题。他们设计了一种贪婪的算法来实现学习者保持率最大化的高性能。但该算法实现高效用的充分条件很严格，可能在大多数情况下不适用。最近，强化学习也被应用于优化间隔重复的安排。一些论文通过设计奖励和在模拟环境中的训练，使用RL来最大化学习者的记忆期望。然而，他们的算法所基于的环境过于简化，使得它不能很好地适用于现实世界。除此之外，这些算法缺乏可解释性，在不同的模拟环境中，它们的表现也不尽相同，并不总是优于启发式算法。

3 长期记忆模型

为了设计一种高效的、有保证的、可解释的间隔重复调度算法，我们收集了学习者的记忆行为数据，然后用这些数据来验证几种心理效应。利用这些效应，我们对记忆进行建模，以了解间隔重复的调度是如何影响学习者的记忆状态的。

3.1 建立数据集

我们收集了墨墨背单词一个月的日志，包含 2.2 亿条记忆行为数据，以建立一个模型来模拟学习者的记忆。由于以下原因，我们没有使用 Duolingo 的开源数据集：

• 它缺乏时间序列方面的内容，如反馈和间隔的序列，而我们对数据的分析表明，历史特征对记忆状态有很大的影响。
• 它的回忆概率定义是有问题的。Duolingo 将回忆概率定义为一个单词在特定会话中被正确回忆的次数比例，这意味着同一单词在特定会话中的多次记忆行为是独立的。然而，第一次回忆会影响学习者的记忆状态和全天的后续记忆。

从墨墨背单词收集的记忆数据记录了学习者对单词记忆的历史信息。对于任意一个记忆行为，我们用一个四元组来表示：

$e :=(u, l, t, r)$

它的含义是一个学习者$u$在时间$t$回忆单词$l$的反馈（回忆成功$r=1$；回忆失败$r=0$）。

为了便于研究记忆行为序列，我们将历史特征加入其中：

$e_{i} :=(u, l, \boldsymbol{\Delta t_{1:i-1}}, \boldsymbol r_{1:i-1} , \Delta t_i , r_i)$

其中 $e_i$ 表示学习者 $u$ 对单词 $l$的第$i$次回忆，$\Delta t$ 表示两次回忆之间的时间间隔。 $\boldsymbol \Delta t_{1:i-1}$ 和 $\boldsymbol r_{1:i-1}$分别表示第$1$到第 $i-1$ 回忆的间隔历史和反馈历史。

我们过滤掉其中第一个反馈为 $r=1$ 的日志，以排除学习者在使用间隔重复之前形成的记忆的影响。学习者的记忆行为事件的样本日志见表 1

由此我们得到了包含任意学习者对任意单词的完整记忆行为历史数据。接下来，我们将基于该数据验证两个在间隔重复中发挥重要作用的心理学现象。

3.2 遗忘曲线与间隔效应

遗忘曲线是说，学习者停止复习后，记忆会随着时间的推移而衰退。在上面的记忆行为事件中，回忆是二元的(即，用户要么完全回忆起一个单词，要么忘记一个单词)。为了捕捉记忆的衰退，我们需要得到二元回忆背后潜在的概率。为了得到回忆概率，我们忽略学习者本身的影响，用学习该单词的学习者中的回忆比例 $\cfrac{n_{r=1}}{N}$ 作为回忆概率 $p$，从而聚合得到:

$e_{i} :=(l, \boldsymbol{\Delta t}_{1:i-1}, \boldsymbol r_{1:i-1}, \Delta t_i , p_i)$

通过控制 $w$、$\boldsymbol{\Delta t}_{1:i-1}$ 和 $\boldsymbol r_{1:i-1}$，我们可以绘制每个$\Delta t$的$p$，从而得到遗忘曲线。当 $N$ 足够大时，比率 $n_{r=1}/N$ 接近召回概率。然而，墨墨背单词中几乎有 10 万个词，在不同的时间序列中为每个词收集的行为事件是稀疏的。我们需要对单词进行分组，以便在区分不同的单词和缓解数据稀疏性之间做出权衡。鉴于我们对遗忘曲线感兴趣，材料的难度会明显影响遗忘速度。因此，我们尝试用第一次学习它们后第二天的回忆率作为划分单词难度的标准。图 2a 描绘了回忆率的分布。

我们可以从数据分布中看到，回忆率大多在 0.45 和 0.85 之间。为了使分组数据的平衡和密度，将单词分为十个难度组。分组的结果显示在图 2 和表 2 中。符号 $d$ 表示难度，数字越大，难度就越大。

因此，分组记忆行为事件可以表示为：

$e_{i} :=(d, \boldsymbol{\Delta t}_{1:i-1}, \boldsymbol r_{1:i-1}, \Delta t_i , p_i)$

使用聚合后的数据，我们便可以绘制有足够数据支持的遗忘曲线.我们使用指数遗忘曲线模型 $p_i = 2^{-\frac{\Delta t_i}{h_i}}$ 对其进行拟合，并由此得到记忆半衰期。

通过此方法，我们将 $\Delta t_i , p_i$ 特征降维得到 $h_i$：

$e_{i} :=(d, \boldsymbol{\Delta t}_{1:i-1}, \boldsymbol r_{1:i-1}, h_i)$

间隔效应是说，随着复习之间的间隔增长，复习后对记忆的巩固效果也会提升。在我们的数据集中，我们认为可以用一次复习前后的半衰期之比来表示记忆的巩固效果。

图 3 中的散点反映了每个区间所对应的召回比例，而曲线是用指数函数拟合这些点的结果。各种颜色表示不同的控制情况。从各种记忆行为事件中，我们可以观察到，成功的回忆会延长记忆的半衰期。记忆巩固的效果随着复习间隔的延长而上升。

基于上述效应，我们提出了 Difficulty-Halflife-P(recall) Model，用于解释现有数据。

3.3 难度-半衰期-回忆概率模型

目前处理时间序列数据的先进方法是基于 LSTM 和 GRU 等递归神经网络，它们可以利用时间序列特征预测半衰期。然而，引入神经网络将使我们的算法无法解释。相反，我们开发了一个具有马尔科夫特性的时间序列模型，以实现可解释性和简单性。在这个模型中，我们将时间序列的维度减少为状态变量和状态转换方程。我们考虑以下四个变量：

• 半衰期。它衡量记忆的存储强度。
• 回忆概率。它衡量记忆的检索强度。根据间隔效应，每次复习的间隔时间会影响半衰期。当 $h$ 固定时，$\Delta t$ 和 $p$ 是一对一映射的，为了规范化，我们用 $p=2^{-\Delta t/h}$ 代替它作为状态变量。
• 回忆结果。回忆成功后半衰期提高，回忆失败后半衰期下降。
• 难度。直觉上难度越高，记忆越难巩固。

将时间序列被投影到三维空间，最后的半衰期、召回概率和半衰期为 XYZ 轴，难度由颜色表示，如图 4 所示。

通过观察数据的分布，我们观察到了两个现象：在 $r_1 = 1$ 时 $h_{i+1}>h_i$，在 $r_1 = 0$ 时 $h_{i+1}>0$

我们将这两个约束条件考虑到状态转移方程中，得到：

$h_{i+1} =[h_i \cdot (\exp( \boldsymbol \theta_1 \cdot \boldsymbol x_i)+1),\exp(\boldsymbol \theta_2 \cdot \boldsymbol x_i)] \cdot [r_i, 1-r_i]^T$

其中

• $\boldsymbol x_i = [\log d_i, \log h_i,\log(1-p_i)]$ 是特征向量
• $\boldsymbol\theta$ 是参数向量，由线性回归得出

在该转移方程的基础上，我们观察到，当学习者反馈遗忘后的记忆行为中，在当前半衰期和回忆概率相同的情况下，下一个半衰期变小。我们认为这是由于对学习者来说更难的材料，更可能被反馈遗忘，所以学习者反馈遗忘后的材料，其难度会比记住的材料更高。

因此，我们新增了一个状态转移方程：

难度转移方程： $d_{i + 1} = [d_i, d_i + \theta_3]\cdot[r_i, 1-r_i]^T$

为了防止难度无限增长，我们增加了一个上限。

最终，我们的记忆状态转移方程组为：

$\left[\begin{array}{c} h_{i+1} \\ d_{i+1} \end{array}\right] = \left[\begin{array}{c} h_i \cdot (\exp( \boldsymbol \theta_1 \cdot \boldsymbol x_i)+1)&\exp(\boldsymbol \theta_2 \cdot \boldsymbol x_i)\\ d_i& d_i + \theta_3 \end{array}\right]\times\left[\begin{array}{c} r_i \\ 1-r_i \end{array}\right]$

$\boldsymbol x_i = [\log d_i, \log h_i,\log(1-p_i)]$

$r_i \sim Bernoulli(p_i)$

$p_i=2^{-\frac{\Delta t_i}{h_i}}$

根据上述转移方程组，和数据中统计出的半衰期初始值 $h_0$ 、难度初始值 $d_0$ ，即可预测任意记忆行为序列下的半衰期$h_i$。计算过程如图 5 所示。

4 最优调度

有了描述学习者长期记忆的模型，我们便可以使用该模型来预测不同间隔重复调度算法的表现。在设计优化调度之前，我们需要设置一个目标。

4.1 问题设置

间隔重复方法的目的在于帮助学习者高效地形成长期记忆。而记忆半衰期反映了长期记忆的存储强度，复习次数、每次复习所花费的时间则反映了记忆的成本。所以，间隔重复调度优化的目标可以表述为：在给定记忆成本约束内，尽可能让更多的材料达到目标半衰期，或以最小的记忆成本让一定量的记忆材料达到目标半衰期。其中，后者的问题可以简化为如何以最小的记忆成本让一条记忆材料达到目标半衰期，即最小化记忆成本（Minimize Memorization Cost, MMC）。

我们在第 3.3 节所构建的长期记忆模型满足马尔可夫性，每次记忆的状态只取决于上一次的半衰期、难度和当前的复习间隔和回忆结果。其中回忆结果服从一个与复习间隔有关的随机分布。由于半衰期状态转移存在随机性，一条记忆材料达到目标半衰期所需的复习次数是不确定的。因此，间隔重复调度问题可以视作一个无限时间的随机动态规划问题。考虑到优化目标是让记忆半衰期达到目标水平，所以本问题存在终止状态，所以可以转化为一个随机最短路径问题（Stochastic Shortest Path, SSP）。结合优化目标，我们将算法命名为 SSP-MMC。

4.2 随机最短路径算法

如上图所示，在不考虑难度状态的情况下，圆圈是半衰期状态，方块是复查间隔，虚线箭头表示给定复查间隔的半衰期状态转换，黑边表示给定记忆状态下可用的复查间隔与相应的复查成本。间隔重复中的随机最短路径问题是调度员如何建议最佳复查间隔，以最小化达到目标半衰期的预期复查成本。

符号约定：

• $h_0$ - 初始半衰期
• $h_{N}$- 目标半衰期
• $h_{k+1}, d_{k+1} = f(h_k,d_k,\Delta t_k, r_k)$ - 记忆状态转移方程
• $g(h_k,d_k,\Delta t_k, r_k)$ - 复习成本
  • 出于简化的目的，我们只考虑 $r_k$ 的影响：$g(r_k) = a \cdot r_k + b \cdot (1-r_k)$
    • a 为回忆成功的成本
    • b 为回忆失败的成本
    • 通常回忆失败后需要更多的练习，所以 b > a
• $\Delta T(h_k,d_k)$- 当前记忆状态下可选的复习间隔集合
• $J_\pi(h_0,d_0)$- 总复习成本

让我们列出 SSP-MMC 的 Bellman's equation：

$J(h_k,d_k) = \min\limits_{\Delta t_k \in \Delta T(h_k, d_k)} E[g(r_k) + J(f(h_k,d_k,\Delta t_k, r_k))]$

基于该方程，可以使用动态规划迭代求解，得到每个 $h_k,d_k$ 对应的最优复习间隔 $\Delta t_k$。

考虑到 $h$ 是一个连续值，不利于记录状态，可以将其离散化：

$h_{index} = \lfloor\log(h) / \log(\rm{base})\rfloor$

• base 用于控制 h 分箱大小
• 取对数是因为状态转移方程中，h是近似于指数增长的

由于存在难度上限 $d_N$ 和终止半衰期 $h_N$，我们可以建立一个成本矩阵 $J[d_N][h_N]$，并初始化为 $\inf$。设置 $J[d_i][h_N] = 0$，然后开始遍历每个 $(d_k,h_k)$，从 $\Delta T(h_k, d_k)$ 中遍历每个 $\Delta t_k$，计算 $p_k,h_{r_k=1},h_{r_k=0},d_{r_k=1},d_{r_k=0}$，然后使用以下公式：

$cost[h_k][d_k] = \min\limits_{p_k} [p_k \cdot (g(1) + cost[h_{r_k=1}][d_{r_k=1}]) + (1-p_k) \cdot (g(0) + cost[h_{r_k=0}][d_{r_k=0}])]$

来迭代更新每个记忆状态对应的最优成本。用一个策略矩阵记录每个状态下最优的复习间隔。最优策略会在一遍遍迭代中收敛。

5 实验

我们的实验是为了回答以下问题。

• DHP 模型模拟长期记忆的效果如何？
• DHP 模型的权重参数的实际意义是什么？
• SSP-MMC 算法给出的最佳复习间隔的模式是什么？
• 与基线相比，SSP-MMC 算法在不同指标上有什么改进？

在这一节中，我们首先根据第 3.3 节中收集的数据集训练了 DHP 模型，并将其与 HLR 模型进行比较。还对 DHP 模型的参数进行了可视化，以获得对记忆的直观解释。然后，我们使用 DHP 模型作为 SSP-MMC 算法的训练环境，以获得最佳策略并将其可视化。最后，我们在由 DHP 模型组成的模拟环境中比较了 SSP-MMC 与不同基线的性能。

5.1 DHP 模型权重分析

为了更好地了解DHP模型，我们将其与 HLR 模型在预测半衰期方面进行比较，并分析模型的权重。

拟合的结果显示在图 7 中。从比较中，我们可以发现，在预测半衰期时，HLR 是欠拟合的，而 DHP 模型的预测误差（如表所示）明显小于 HLR 模型，特别是在回忆失败后的结果。这很可能是由于 HLR 丢失了时间序列信息，使得它无法区分 $r_{1:2}=1,0$ 和 $r_{1:2}=0,1$ 这样的记忆行为。

根据拟合得到的参数和模型的方程，我们得到成功回忆后的半衰期：

$h_{i+1} = h_i \cdot( \exp(3.81) \cdot d_i^{-0.534} \cdot h_i^{-0.127} \cdot (1 - p_i)^{0.970} + 1)$

图 8a 说明，成功回忆后的半衰期随着 $p_i$ 的减少而增加，这验证了间隔效应的存在。图 8b 显示，随着最后半衰期的增加，半衰期的增加倍数减少，这可能意味着我们的记忆巩固会随着记忆强度的增加而减少，即存在边际效应。

类似地，回忆失败后的半衰期：

$h_{i+1} = \exp(-0.041) \cdot d_i^{-0.041} \cdot h_i^{0.377} \cdot (1 - p_i)^{-0.227}$

图 8c 中，记忆的半衰期越长，回忆失败后的半衰期也越长，这可能是因为记忆在遗忘中没有完全丢失。而随着回忆概率的降低，回忆失败后的半衰期也随之降低，这可能是因为随着时间的推移，记忆被遗忘得更彻底。

5.2 SSP-MMC 最优策略分析

通过在 DHP 模型的环境中训练算法 SSP-MMC，我们得到了每个记忆状态的预期复习成本和最佳复习间隔时间。

如图 9a 所示，复习成本随着半衰期的增加而减少，随着难度的增加而增加。具有高半衰期的记忆以较低的预期成本达到目标半衰期。此外，难度较高的记忆具有较高的预期成本，因为它们的半衰期增长较低，如图 8b 所示，需要更多的复习才能达到目标半衰期。

如图 9b 所示，在相同的记忆半衰期水平下，间隔时间随着难度的增加而增加。这可能是因为遗忘提高了简单记忆的难度，降低了它们的半衰期，导致了更高的复习成本。调度算法倾向于给简单记忆更短的间隔时间，减少它们被遗忘的概率，即使它牺牲了一点半衰期的提升。间隔时间在半衰期的中段达到峰值。为了解释这个峰值，有必要与图 9c 进行比较。

如图 9c 所示，对应于最佳间隔的召回概率随着半衰期的延长而增加，随着难度的增加而减少。这意味着在记忆的早期阶段，调度器会指示学习者以较低的检索强度进行复习，这可能是「合意的困难」的反映。当半衰期增加到目标值时，召回概率就会接近 100％。根据公式 $\Delta t = - h \cdot \log_2 p$ 和 p 对 h 的趋势，$\Delta t$ 在出现峰值的地方先是增加，然后减少。

5.3 离线模拟

我们研究了 5 个基线策略：random、anki、half-life、threshold、memorize 和 3 个指标：目标半衰期达成量、累计学习量、回忆期望。

环境

我们的模拟环境有以下参数。目标半衰期$h_N$，召回成功/失败成本，每日成本限制和模拟持续时间。

基线

我们将 SSP-MMC 与几个基线调度算法进行对比：

• random 策略，每次从 $[1,h_N]$ 中随机选择一个间隔进行安排复习
• Anki，sm-2 的一种变体，参考其开源的代码。由于 anki 的算法中，用户的回忆结果是以 1-4 分输入。我们将回忆失败映射到 1 分，回忆成功映射到 3 分。
• 半衰期，即直接以半衰期作为本次安排的复习间隔。
• 固定阈值，即当 p 小于等于某一水平（我们使用 80%）时进行复习。
• Memorize，一种基于最优控制的算法，代码来自于他们开源的仓库。

指标

我们的评价指标包括：

• 达到目标半衰期的记忆数量，当一条 item 的半衰期超过目标半衰期，该指标 +1
• 累计记忆期望，即学习者所有记忆的 item 的回忆概率之和。
• 累计新增的记忆数量，当一条item被加入到学习者的间隔重复调度中，该指标 +1

实现细节

我们设定 360 天（接近一年）的召回半衰期为目标半衰期，当 item 的半衰期超过这个值时，它将不会被安排复习。然后，考虑到实际场景中学习者每天的学习时间大致恒定，我们设定 600s（10 分钟）为每天学习成本的上限。当每次学习和复习过程中的累计成本超过这个上限时，无论是否完成，复习任务都会被推迟到第二天，以确保每种算法在相同的记忆成本下进行比较。我们使用学习者的平均时间，即成功回忆的时间为 3s，失败回忆的时间为 9s。然后，语言学习是一个长期的过程，我们设定模拟时间为 1000 天。

分析

上图中的仿真结果显示，

在 THR 上， SSP-MMC 的表现比所有基线都好，这并不令人惊讶。THR 与 SSP-MMC 的优化目标一致，而且 SSP-MMC 可以达到这个指标的上限。

为了量化每种算法性能之间的相对差异，我们比较了 THR = 6000 的天数（图中标记为🌟）： SSP-MMC 为 466 天，ANKI 为 569 天，THRESHOLD 为 533 天，而 MEMORIZE 为 793 天。与THRESHOLD 相比，SSP-MMC 节省了 12.6％ 的复习时间。

SRP 上的结果与 THR 上的结果相似。这意味着学习者按照 SSP-MMC 的时间表学习会记得最多。

在 WTL 上，RANDOM 在早期阶段击败了所有的算法，因为只要调度算法不安排复习，学习者就可以继续学习新的单词，但这是以忘记已经学过的单词为代价的。此外，SSP-MMC 胜过其他基线，因为它将记忆的成本降到最低，给学习者更多的时间来学习新词。

6 结论

我们的工作建立了第一个包含完整时序信息的记忆数据集，设计了基于时序信息的长期记忆模型，能够良好拟合现有的数据，并为优化间隔重复调度提供了坚实的基础。我们将最小化学习者的记忆成本作为间隔重复软件的目标，根据随机最优控制理论，我们推导出了一个有数学保证的最小化记忆成本的调度算法 SSP-MMC。SSP-MMC 将心理学上被多次验证的遗忘曲线、间隔效应等理论与现代机器学习技术相结合，降低了学习者形成长期记忆的记忆成本。相较于 HLR 模型，考虑时序信息的模型在拟合用户长期记忆上的精度有显著提升。并且，基于随机动态规划的间隔重复调度算法，在各项指标上都超过了之前的算法。该算法被部署在 MaiMemo 中以提高用户的长期记忆效率。我们在附录中提供了设计和部署的技术细节。

主要的后续工作是改进 DHP 模型，考虑用户特征对记忆状态转移的影响，并在语言学习以外的间隔重复软件中使用我们的算法来建议模型的通用性。此外，学习者使用间隔重复方法的场景十分多样化，设计匹配学习者目标的优化指标也是一个值得研究的问题。

7 数据与代码

为了促进该领域的研究，我们开源了本文使用的数据集和代码：

https://github.com/maimemo/SSP-MMC

致谢

感谢我们在 MaiMemo 的合作者，尤其是黄俊和张征，他们帮助我们从系统的各个部分收集数据。

参考文献

[1] John R. Anderson, Daniel Bothell, Michael D. Byrne, Scott Douglass, Christian Lebiere, and Yulin Qin. 2004. An Integrated Theory of the Mind. Psychological Review 111, 4 (2004), 1036–1060.

[2] Robert A. Bjork, Elizabeth L. Bjork, et al. 1992. A New Theory of Disuse and an Old Theory of Stimulus Fluctuation. From learning processes to cognitive processes: Essays in honor of William K. Estes 2 (1992), 35–67.

[3] Shana K. Carpenter, Harold Pashler, and Nicholas J. Cepeda. 2009. Using Tests to Enhance 8th Grade Students’ Retention of U.S. History Facts. Applied Cognitive Psychology 23, 6 (2009), 760–771.

[4] Nicholas J. Cepeda, Harold Pashler, Edward Vul, John T. Wixted, and Doug Rohrer. 2006. Distributed Practice in Verbal Recall Tasks: A Review and Quantitative Synthesis. Psychological Bulletin 132, 3 (2006), 354–380.

[5] Nicholas J. Cepeda, Edward Vul, Doug Rohrer, John T. Wixted, and Harold Pashler. 2008. Spacing Effects in Learning: A Temporal Ridgeline of Optimal Retention. Psychological Science 19, 11 (2008), 1095–1102.

[6] Hermann Ebbinghaus. 1913. Memory: A Contribution to Experimental Psychology. Teachers College Press, New York.

[7] Anette Hunziker, Yuxin Chen, et al. 2019. Teaching Multiple Concepts to a Forgetful Learner. In Advances in Neural Information Processing Systems. 4050– 4060.

[8] Sebastian Leitner. 1974. So lernt man leben. Droemer-Knaur, München, Zürich.

[9] Jaclyn K. Maass, Philip I. Pavlik, and Henry Hua. 2015. How Spacing and Vari- able Retrieval Practice Affect the Learning of Statistics Concepts. In Artificial Intelligence in Education. Springer, 247–256.

[10] Arthur W. Melton. 1970. The Situation with Respect to the Spacing of Repetitions and Memory. Journal of Verbal Learning and Verbal Behavior 9, 5 (1970), 596–606.

[11] Harold Pashler, Nicholas Cepeda, Robert V Lindsey, Ed Vul, and Michael C Mozer. 2009. Predicting the Optimal Spacing of Study: A Multiscale Context Model of Memory. In Advances in Neural Information Processing Systems. 1321–1329.

[12] Siddharth Reddy, Igor Labutov, Siddhartha Banerjee, and Thorsten Joachims. 2016. Unbounded Human Learning: Optimal Scheduling for Spaced Repetition. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1815–1824.

[13] Siddharth Reddy, Sergey Levine, and Anca Dragan. 2017. Accelerating Human Learning with Deep Reinforcement Learning. University of California, Berkeley (2017), 9.

[14] Burr Settles and Brendan Meeder. 2016. A Trainable Spaced Repetition Model for Language Learning. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. ACL, 1848–1858.

[15] Sugandh Sinha. 2019. Using Deep Reinforcement Learning for Personalizing Review Sessions on E-Learning Platforms with Spaced Repetition. Ph. D. Dissertation. KTH Royal Institute of Technology.

[16] Paul Smolen, Yili Zhang, and John H. Byrne. 2016. The Right Time to Learn: Mechanisms and Optimization of Spaced Learning. Nature reviews. Neuroscience 17, 2 (2016), 77–88.

[17] Behzad Tabibian, Utkarsh Upadhyay, Abir De, Ali Zarezade, Bernhard Schölkopf, and Manuel Gomez-Rodriguez. 2019. Enhancing Human Learning via Spaced Repetition Optimization. Proceedings of the National Academy of Sciences 116, 10 (2019), 3988–3993.

[18] Shaw TJ, Pernar LIM, et al. 2012. Impact of Online Education on Intern Behaviour around Joint Commission National Patient Safety Goals: A Randomised Trial. BMJ quality & safety 21, 10 (2012), 819–825.

[19] Utkarsh Upadhyay, Abir De, and Manuel Gomez-Rodrizuez. 2018. Deep Rein- forcement Learning of Marked Temporal Point Processes. In Advances in Neural Information Processing Systems. 3172–3182.

[20] Piotr A. Wozniak. 1990. Optimization of Learning. http://super- memory.com/english/ol.htm.

[21] Zhengyu Yang, Jian Shen, Yunfei Liu, Yang Yang, Weinan Zhang, and Yong Yu. 2020. TADS: Learning Time-Aware Scheduling Policy with Dyna-Style Planning for Spaced Repetition. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 1917–1920.

[22] Ahmed Zaidi, Andrew Caines, Russell Moore, Paula Buttery, and AndrewRice. 2020. Adaptive Forgetting Curves for Spaced Repetition Language Learning. In Artificial Intelligence in Education. Springer, 358–363.

A 部署设计

在这个附录中，我们描述了如何将 SSP-MMC 算法部署到墨墨背单词中，以优化学习者的间隔重复计划。

A.1 架构

上图显示了间隔重复调度器的框架，它分为两个主要部分：绿色为本地，红色为远程。

每次用户复习单词时，带有时间序列信息的记忆行为事件将被记录在本地，我们称之为 User Review Logs。在学习者完成当天的所有复习后，这些日志会被上传到远程。

完整的复习日志必须处理大量的写入，需要永久保留，而且一旦写入就不会更新，所以我们使用流式数据服务将日志写入数据仓库。在预处理 ETL 中，我们定期计算所有单词的难度，并汇总 DHP 记忆模型所需的训练数据，为 SSP-MMC 调度算法 提供训练环境。

在计算出模型参数和最优策略后，远程将相关配置推送到本地。然后本地预测器和调度器将加载新的配置来预测记忆状态，并为用户学习的每个单词安排复习日期。

A.2 冷启动

在冷启动阶段，它可以使用一个简单的调度算法，比如说 SM-2。然后将收集到的 User Review Logs 到远程的 Full Review Logs，并进行预处理以计算难度和半衰期。这些数据被用来拟合 DHP 模型以获得模型参数，并作为 SSP-MMC 的环境来推导出最佳策略。远程的模型参数和最优策略将被发送到本地预测器和调度器，以取代原来的简单调度算法，并获得更多的 User Review Logs，从而迭代改进 DHP Memory Model 和 SSP-MMC 调度算法生成的最优策略。