?reference?

#  $\text{KAR}^{\text{3}}\text{L}$: Knowledge-Aware Retrieval and
Representations aid Retention and Learning in Students

Matthew Shu1∗ Nishant Balepur2∗ Shi Feng3∗ Jordan Boyd-Graber2
1Yale University 2University of Maryland 3New York University
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Flashcard schedulers are tools that rely on 1) student models to predict the
flashcards a student knows; and 2) teaching policies to schedule cards based
on these predictions. Existing student models, however, only use flashcard-
level features, like the student’s past responses, ignoring the semantic ties
of flashcards. Deep Knowledge Tracing (DKT) models can capture semantic
relations with language models, but are inefficient, lack content-rich
datasets for evaluation, and require robust teaching policies. To address
these issues, we design $\text{KAR}^{\text{3}}\text{L}$, a DKT-inspired
student model that uses retrieval and BERT embeddings for efficient and
accurate student recall predictions. To test $\text{KAR}^{\text{3}}\text{L}$,
we collect a new dataset of diverse study history on trivia questions.
$\text{KAR}^{\text{3}}\text{L}$ bests existing student models in AUC and
calibration error. Finally, we propose a novel teaching policy that exploits
the predictive power of DKT models to deploy $\text{KAR}^{\text{3}}\text{L}$
online. Based on 27 learners and 32 6-day study trajectories,
$\text{KAR}^{\text{3}}\text{L}$ shows the ability to enhance medium-term
educational learning, proving its efficacy for scheduling.111Our data and code
are available at https://github.com/Pinafore/fact-repetition.

11footnotetext: Equal contribution. Figure 1:  Overview of
$\text{KAR}^{\text{3}}\text{L}$. Given a current flashcard and the student’s
study history as inputs, $\text{KAR}^{\text{3}}\text{L}$ first uses a BERT
retriever to obtain the most semantically similar cards from the study
history. Next, the BERT embeddings of these retrieved flashcards, the
embedding of the current flashcard, and flashcard-level features (e.g. time
since last review), are fed through a classifier (CLF) to predict if the
student knows the answer to the current flashcard.

##  1 Introduction

Flashcards help students learn a variety of subjects, such as vocabulary,
trivia, and law Wissman et al. (2012). In learning software, a flashcard
scheduler dictates when a student reviews old flashcards and when they learn
new ones Reddy et al. (2016). Many schedulers use student models to predict
the probability a student can recall a flashcard Mozer et al. (2019). A
teaching policy then chooses the flashcards to show next based on these recall
predictions Reddy et al. (2017). Teaching policies facilitate personalized
learning experiences by understanding a student’s learning needs. Therefore, a
scheduler’s student model must use informative features to adeptly capture a
student’s knowledge state Brusilovsky et al. (2015); Chrysafiadi et al. (2015)

For recall prediction, existing student models Settles and Meeder (2016);
Tabibian et al. (2019) rely on historical data from the student’s study
history, such as their past answers and time since last review. While these
features model student behavior, they neglect a key aspect of flashcards: the
textual content in the cards. Modeling this content and the semantic relations
between flashcard content could enhance recall prediction, especially on
unstudied cards. For instance, if a student knows that John Adams is the
_second_ American president, the student model should be able to infer that
the student can also answer “Who was the _first_ American president?”, even if
this question has not been studied. Current student models, relying only on
historical features, cannot make these semantic inferences or discriminatively
predict student recall on unseen cards. As a result, they cannot introduce new
cards to fill a student’s inferred knowledge gaps, indicating the need for
robust, content-aware techniques.

To solve this issue, we turn to Deep Knowledge Tracing (DKT) models Piech et
al. (2015), which embed student study histories Shin et al. (2021) to predict
study correctness. These embeddings can be enhanced with pretrained language
models Srivastava and Goodman (2021), providing a strong basis for capturing
semantic inferences. While DKT models have primarily been tested in offline
settings, we seek to design the _first_ online scheduler employing DKT to
improve student modeling. However, this novel integration of DKT for content-
aware scheduling introduces several challenges.

First, applying DKT for scheduling may degrade efficiency. While DKT models
provide rich representations by embedding a student’s full study history, this
is inefficient and can lower user experience Manhas (2013). Using the $k$-most
recent study items is a simple fix but fails when students shift topics, as
the past-$k$ data is no longer semantically related. Second, a content-aware
scheduler must be evaluated on a content-focused dataset. Current KT and
flashcard datasets Selent et al. (2016); Settles and Meeder (2016), however,
either do not release the content of flashcards or are limited to singular
vocab words; a diverse, content-rich dataset is critical to study how content-
aware schedulers capture semantic relations. Third, DKT-based student models
require robust teaching policies. Existing DKT-compatible policies select
flashcards with predicted recall near a threshold like 0.94 Eglington and
Pavlik Jr (2020), which may omit difficult (predicted recall of 0) but crucial
content for subject mastery. This simple type of policy does not fully exploit
DKT’s predictive power.

Pursuing a content-aware scheduler, we design $\text{KAR}^{\text{3}}\text{L}$,
a DKT-inspired student model that uses Knowledge-Aware Retrieval and
Representations to aid Retention and Learning (section 2).
$\text{KAR}^{\text{3}}\text{L}$ has two design choices to enhance efficiency
and flashcard representations (Figure 1). First,
$\text{KAR}^{\text{3}}\text{L}$ uses a BERT retriever Lee et al. (2019) to
obtain a subset of semantically similar cards in the student’s study history,
making $\text{KAR}^{\text{3}}\text{L}$ the first retrieval-augmented student
model. This approach greatly reduces the number of cards embedded by
$\text{KAR}^{\text{3}}\text{L}$, improving efficiency, and only uses the study
history that is semantically similar to the current flashcard, accounting for
topic shifts. Second, $\text{KAR}^{\text{3}}\text{L}$ represents the retrieved
study history and current flashcard with flashcard-level features and BERT
embeddings to predict student recall. This enables
$\text{KAR}^{\text{3}}\text{L}$ to accurately predict student recall even on
unseen flashcards, using both the individual properties of flashcards and
their semantic relations.

To evaluate $\text{KAR}^{\text{3}}\text{L}$, we create a flashcard app and
collect 123,143 study logs from 543 users (section 3). Our flashcards are
based on trivia facts, a content-rich domain spanning diverse topics such as
fine arts, history, and pop culture, allowing us to study the effect of
$\text{KAR}^{\text{3}}\text{L}$ capturing semantic relations. We compare
$\text{KAR}^{\text{3}}\text{L}$ with existing student models Wozniak (1990);
Settles and Meeder (2016); Srivastava and Goodman (2021); Ye et al. (2022).
Overall, $\text{KAR}^{\text{3}}\text{L}$ is the strongest student model,
having the most accurate and well-calibrated recall predictions, measured via
AUC and calibration error (section 4), revealing the benefits of content-aware
scheduling.

Finally, to assess $\text{KAR}^{\text{3}}\text{L}$ in a true learning setting,
we conduct an online comparison with FSRS, the current state-of-the-art
scheduler (section 5). To do so, we construct a novel delta-based teaching
policy, which selects flashcards $\text{KAR}^{\text{3}}\text{L}$ predicts will
maximize learning after a specified time delta. By leveraging DKT’s
predictions of future recall, we improve upon simple threshold-based policies
to ensure flashcards with currently low predicted recall probability can still
be scheduled for study.

We have 27 new learners study within our app to improve medium-term learning
over 6 days. Based on 32 study trajectories, $\text{KAR}^{\text{3}}\text{L}$
with the delta policy ($\text{KAR}^{\text{3}}\text{L}+\Delta$) performs
comparably to FSRS, a significant feat for the first attempt at using DKT for
online scheduling. Our results not only reveal
$\text{KAR}^{\text{3}}\text{L}$’s efficacy as an adaptive learning tool, but
also motivate future content-aware applications of DKT and language models in
educational settings.

Our contributions can be summarized as follows:
1) We develop $\text{KAR}^{\text{3}}\text{L}+\Delta$, the first content-aware
scheduler leveraging DKT and BERT to capture semantic ties and robustly
predict student recall.

2) We address practical DKT challenges by designing the first retrieval-
augmented student model and a novel delta teaching policy for our scheduler.

3) We collect and release a dataset of 123,143 study logs from 543 users on
diverse trivia flashcards.

4) Through offline and online evaluations, we showcase
$\text{KAR}^{\text{3}}\text{L}$’s efficacy for flashcard learning, motivating
future work in advancing DKT and language model applications for adaptive
education.

##  2 $\text{KAR}^{\text{3}}\text{L}$ Student Model Design

Our student model $\text{KAR}^{\text{3}}\text{L}$ is inspired by DKT
Abdelrahman et al. (2023) and uses as inputs: 1) the flashcard $f_{t}$ shown
to the student at time $t$; and 2) a sequence of all previous flashcards
studied by the student $\mathcal{F}=\\{f_{1},f_{2},...,f_{t-1}\\}$. We also
assume that each flashcard $z$ can be mapped to a set of flashcard-level
features $\mathcal{X}(z)$, such as the student’s number of correct and
incorrect responses to $z$ and the time since its last review. Using these
inputs, $\text{KAR}^{\text{3}}\text{L}$ predicts $a_{t}\in\\{0,1\\}$, a binary
variable indicating if the student will answer $f_{t}$ correctly.

As shown in Figure 1, $\text{KAR}^{\text{3}}\text{L}$ predicts $a_{t}$ via a
two-step process. First, $\text{KAR}^{\text{3}}\text{L}$ leverages a BERT-
based retriever $p(f_{t}|f_{i})$ to find the top-$k$ flashcards
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ most semantically relevant to
$f_{t}$. Next, $\text{KAR}^{\text{3}}\text{L}$ feeds $f_{t}$ and
$\mathcal{F}^{\prime}$ as inputs to a neural classifier
$p(a_{t}|f,\mathcal{F}^{\prime})$, which represents the current flashcard $f$
and each retrieved flashcard $f_{i}\in\mathcal{F}^{\prime}$ with BERT
embeddings and the flashcard features from $\mathcal{X}(z)$. We describe both
of these steps next.

###  2.1 Flashcard Retrieval

As a student learns, their study history $\mathcal{F}$ expands. Since DKT
models embed the entire study history, their inference time scales with the
length of $\mathcal{F}$ Pope et al. (2023), resulting in inefficiencies during
long-term deployment. A simple solution is to only consider the top-$k$ most
recent study items in $\mathcal{F}$, but this design choice overlooks
potential topic shifts in a student’s study. To illustrate, if a student has
just shifted from studying biology to literature, using the top-$k$ most
recent study items will fail, as their recent study history on biology will
not be useful for predicting their literary knowledge.

To overcome this issue, we draw from retrieval-augmented models, which
efficiently perform inference on large corpora by retrieving a subset of
relevant items Lewis et al. (2020); Balepur et al. (2023); Jiang et al.
(2023). Hence, we similarly retrieve the flashcards $\mathcal{F}^{\prime}$
from the student’s study history $\mathcal{F}$ that have the most similar
semantic representations to the current flashcard $f_{t}$. This retrieval-
augmented approach fixes the number of flashcards used by
$\text{KAR}^{\text{3}}\text{L}$, resulting in a constant inference time, and
ensures that $\text{KAR}^{\text{3}}\text{L}$ makes predictions using the study
history most semantically similar to $f_{t}$, accounting for topic shifts in a
student’s study.

We obtain the semantic similarity between each study history item
$f_{i}\in\mathcal{F}$ and the current flashcard $f_{t}$ via the dot product of
$f_{i}$ and $f_{t}$, represented by pretrained BERT Devlin et al. (2019)
embeddings:

$\displaystyle\textbf{d}(f_{i})$ $\displaystyle=\text{BERT}(f_{i}),$ (1)
$\displaystyle\textbf{q}(f_{t})$ $\displaystyle=\text{BERT}(f_{t}),$ (2)
$\displaystyle p(f_{t}|f_{i})$
$\displaystyle\sim\textbf{d}(f_{i})^{T}\textbf{q}(f_{t})$ (3)

We retrieve the $k$-highest values for $p(f_{t}|f_{i})$ through Maximum Inner-
Product Search Shrivastava and Li (2014), which become the top-$k$ most
semantically-relevant flashcards $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ to
$f_{t}$.

###  2.2 Feature Representation

After finding the semantically relevant flashcards $\mathcal{F}^{\prime}$, we
represent each flashcard in the study history $f_{i}\in\mathcal{F}^{\prime}$
and the current flashcard $f_{t}$ with informative features for predicting
student recall. Thus, along with the BERT representations computed in section
2.1, we also leverage flashcard-level heuristics used by prior student models
Settles and Meeder (2016); Tabibian et al. (2019). We define $\mathcal{X}(z)$
as a set of manually-crafted features to represent the flashcard $z$, such as
the distribution of the student’s past responses to $z$ and the time since its
last review. These flashcard-level features are essential for enabling
$\text{KAR}^{\text{3}}\text{L}$ to make accurate predictions, shown by our
ablation studies (section 4.4). In Appendix A.1 we show all of the features
computed by $\mathcal{X}(z)$.

Using the BERT embeddings and flashcard metrics as features, we train a
classifier $p(a_{t}|f_{t},\mathcal{F}^{\prime})$ that uses the current
flashcard $f_{t}$ and the retrieved history $\mathcal{F}^{\prime}$ to predict
correctness $a_{t}$, which is 1 if the student recalls $f_{t}$ correctly and 0
otherwise. We first feed the BERT embeddings and flashcard features
$\mathcal{X}(z)$ for each study history flashcard
$f_{i}\in\mathcal{F}^{\prime}$ and the current flashcard $f_{t}$ through a
linear layer to compute a hidden state $h\in\mathbb{R}^{768}$. Next, we feed
the hidden state $h$ through a final linear layer to predict $a_{t}$. We train
$p(a_{t}|f_{t},\mathcal{F}^{\prime})$ to minimize the cross-entropy loss
$\lambda$ of predicting $a_{t}$, conditioned on the representations of
flashcards $f$ and $\mathcal{F}^{\prime}$:

$\lambda=-\log p(a_{t}|f_{t},\mathcal{F}^{\prime})\cdot a_{t}.$ (4)

We minimize $\lambda$ using mini-batch gradient descent.

##  3 Training $\text{KAR}^{\text{3}}\text{L}$

In this section, we provide details for the training setup of
$\text{KAR}^{\text{3}}\text{L}$. We describe our motivation for making a data
collection platform (section 3.1), create flashcards (section 3.2), collect
student study data (section 3.3), and describe our model training procedure
(section 3.4).

###  3.1 Data Collection Platform

A content-aware model like $\text{KAR}^{\text{3}}\text{L}$ benefits most when
flashcards have detailed textual content. However, existing KT and flashcard
datasets refer to flashcards by ID or just a single vocab word, making them
unfit for our study. Further, these datasets are heavily domain-specific.
ASSISTments Selent et al. (2016), the most widely-used KT dataset Abdelrahman
et al. (2023), is restricted to arithmetic; EdNet Choi et al. (2020) and
Duolingo’s Spaced Repetition dataset Settles and Meeder (2016) are solely
dedicated to English language learning. Hence, to evaluate how
$\text{KAR}^{\text{3}}\text{L}$ captures semantic ties across diverse topics,
we opt to build our own data collection and experiment platform, based on a
web and mobile flashcard app (Figure 2).

Figure 2:  Screenshot from our web-based flashcard app after a user submits
their answer to a literature flashcard.

###  3.2 Flashcard Creation

With diversity in mind, we turn to trivia questions from the QANTA dataset
Rodriguez et al. (2019) to create our flashcards. These questions span 11
unique topics, including literature, history, science, fine arts, pop culture,
geography, and mythology.

Each question $q$ in QANTA consists of a list of clues
$q=\\{c_{1},...,c_{n}\\}$ describing a single answer $\mathcal{A}$. To convert
$q$ into a flashcard $f$, we first map each unique $\mathcal{A}$ to its
corresponding questions $\mathcal{Q}=\\{q_{1},...,q_{m}\\}$. Next, we take a
random sample of clues $\mathcal{C}=\\{c_{1},...,c_{p}\\}$ from $\mathcal{Q}$.
Using this data, we create $f$, where the clue $c\in\mathcal{C}$ is the front
of $f$ (i.e. the question shown to the user) and the answer $\mathcal{A}$ is
the back of $f$. Repeating this process for the entire dataset, we obtain
23,918 unique flashcards spanning 11 diverse subjects (e.g. history,
literature), examples of which are in Appendix A.2.

###  3.3 Study Data Collection

After creating flashcards, we recruit users to study with our app. We
advertise to users on English-speaking trivia forums. We give a total of $200
in compensation to 15 users who study the most cards. Each user is assigned to
one of three random schedulers. Two of the schedulers are Leitner Leitner
(1974) and SM-2 Wozniak (1990), the most popular heuristic-based flashcard
schedulers. As a pilot evaluation for $\text{KAR}^{\text{3}}\text{L}$, we also
train a cold start version of $\text{KAR}^{\text{3}}\text{L}$ on the Protobowl
dataset Rodriguez et al. (2019) following section 2.2. This version of
$\text{KAR}^{\text{3}}\text{L}$ is only used in this initial data collection,
and not in any other experiments. Over 4 months, 543 users created 123,143
study records. Each record contains the current flashcard $f_{t}$, the date
and time of $t$, the prior cards studied by the student
$\mathcal{F}=\\{f_{1},f_{2},...,f_{t-1}\\}$, and the binary variable $a$,
where $a$ is 1 if the student answered $f_{t}$ correctly. In our data, users
are only identifiable by user ID.

| Seen Cards | Unseen Cards
---|---|---
Model | AUC ($\uparrow$) | ECE ($\downarrow$) | Acc Correct ($\uparrow$) | Acc Incorrect ($\uparrow$) | AUC ($\uparrow$) | ECE ($\downarrow$) | Acc Correct ($\uparrow$) | Acc Incorrect ($\uparrow$)
HLR | 0.3696 | 0.3867 | 0.7380 | 0.1435 | - | - | - | -
Leitner | 0.7524 | 0.2340 | 0.8334 | 0.3799 | - | - | - | -
SM-2 | 0.6603 | 0.1997 | 0.8262 | 0.4193 | - | - | - | -
FSRS | 0.7519 | 0.1106 | 0.9208 | 0.5242 | - | - | - | -
LM-KT | 0.6582 | 0.2845 | 0.8053 | 0.3267 | 0.6838 | 0.2343 | 0.6665 | 0.5899
$\text{KAR}^{\text{3}}\text{L}$ | 0.7922 | 0.1006 | 0.9213 | 0.5419 | 0.7294 | 0.1206 | 0.6010 | 0.6103
Table 1: Student model ability to predict which flashcards students know
(Accuracy when Correct/Incorrect, AUC) and how well they know them (ECE).
$\uparrow$ (and $\downarrow$) denote if higher (or lower) scores are better.
Best scores are in bold.

###  3.4 Training Setup

We train $\text{KAR}^{\text{3}}\text{L}$ to minimize Equation 4 using our
dataset. We use the Adam optimizer Kingma and Ba (2015), a learning rate of
$0.00005$, a batch size of 64, and 10 training epochs. We retrieve $k=10$
items from the student’s study history for the experiment in section 4.3, and
$k=5$ for all other experiments, both via FAISS Johnson et al. (2019) for
efficiency. We sort study records chronologically and use the first 75% for
training and the last 25% for evaluation. Appendix A.4 contains more training
details.

##  4 Offline Evaluation

###  4.1 Baselines

We compare $\text{KAR}^{\text{3}}\text{L}$ with popular student models:
1) Half Life Regression (HLR) models $a_{t}$ with an exponential forgetting
curve Settles and Meeder (2016). This curve is fit using the student’s past
study responses and time since the last study of $f$.
2) Leitner moves a flashcard $f$ between slots based on student responses to
$f$ Leitner (1974). We use five slots and calculate $a_{t}$ as the current
slot position of $f$ divided by the total number of slots.
3) Super Memo (SM)-2 predicts $a_{t}$ by adjusting review intervals based on
the student’s proportion of successful recalls of $f$ Wozniak (1990).
4) FSRS schedules a flashcard $f$ with difficulty, stability, and
retrievability scores, based on the number of correct/incorrect responses to
$f$ Ye et al. (2022). We take the retrievability score, defined as the
probability of recall, as the prediction for $a_{t}$.
5) LM-KT is a representative DKT baseline using language models like
$\text{KAR}^{\text{3}}\text{L}$. It predicts $a_{t}$ with input sequences
$f_{t}$ and $\mathcal{F}$ and causal language modeling (CLM) Srivastava and
Goodman (2021). Following the paper, we use GPT-2 medium for CLM.

###  4.2 Evaluation Metrics

On the surface, a student model’s training objective is to give accurate
binary predictions for whether a student can recall a flashcard. However, a
student’s familiarity with flashcards is not binary but is instead on a
continuous spectrum. So for scheduling, we are more interested in if the
student model can discern cards that are familiar and unfamiliar to students
across a range of thresholds, rather than one binary prediction. We use two
metrics to capture this nuance and evaluate models: area under the ROC curve
(AUC) and expected calibration error (Naeini et al., 2015, ECE); the former
measures how well the model ranks cards based on the student’s familiarity
with them, and the latter measures if the recall estimates are well-
calibrated. We also show accuracy when the student actually answered correctly
($a_{t}=1$) and incorrectly ($a_{t}=0$), representing the model’s training
objective.

One key advantage of DKT models is that they embed the student’s study history
Shin et al. (2021); Abdelrahman et al. (2023) and do not solely rely on
flashcard-level features. Thus, these models can predict student recall on
cards with no interaction data. To assess this capability for
$\text{KAR}^{\text{3}}\text{L}$ and LM-KT, we compute our metrics segmented by
if the student has or has not seen the current flashcard $f_{t}$.

###  4.3 Quantitative Comparison

We study $\text{KAR}^{\text{3}}\text{L}$’s ability to model student recall
(Table 1). On seen cards, $\text{KAR}^{\text{3}}\text{L}$ surpasses models in
all metrics. On unseen cards, $\text{KAR}^{\text{3}}\text{L}$ bests LM-KT, the
only other model able to predict recall on unseen cards, in AUC, ECE, and Acc
Incorrect. Further, for $\text{KAR}^{\text{3}}\text{L}$, 3/4 metrics on unseen
cards are worse than on seen cards. Thus, student modeling on cards with no
study data is still an open challenge and may benefit from stronger methods to
capture semantics such as large language models.

LM-KT does surpass $\text{KAR}^{\text{3}}\text{L}$ in Acc Correct on unseen
cards, but we argue that AUC and ECE are better indicators of a student
model’s abilities. Accuracy relies on a fixed cutoff (0.5) to decide if a
student understands a flashcard, but research has shown that other values like
0.71 Pavlik Jr et al. (2020) and 0.94 Eglington and Pavlik Jr (2020) can also
be used as cutoffs. Thus, a robust student model should perform well across
varied thresholds, an ability better assessed by AUC and ECE. Overall, our
offline results suggest that $\text{KAR}^{\text{3}}\text{L}$ is the strongest
student model in content-rich settings, having the best ability to discern
which flashcards students know and how well they know them.

| Seen Cards | Unseen Cards
---|---|---
Model | AUC ($\uparrow$) | ECE ($\downarrow$) | AUC ($\uparrow$) | ECE ($\downarrow$)
$\text{KAR}^{\text{3}}\text{L}$ Full | 0.780 | 0.108 | 0.740 | 0.124
Top-$k$ Recent | 0.758 | 0.119 | 0.729 | 0.119
No BERT | 0.692 | 0.127 | 0.612 | 0.205
No $\mathcal{X}(z)$ | 0.680 | 0.135 | 0.620 | 0.191
Table 2: $\text{KAR}^{\text{3}}\text{L}$ vs ablations that use top-$k$ recent
flashcards, omit BERT embeddings, and omit features $\mathcal{X}(z)$.

###  4.4 Ablation Study

To test the benefits of the components of $\text{KAR}^{\text{3}}\text{L}$, we
conduct an ablation study (Table 2). Retrieving the $k$-most _relevant_ over
_recent_ flashcards, adding BERT embeddings, and using flashcard-level
features tend to improve the ECE and AUC of $\text{KAR}^{\text{3}}\text{L}$.
This suggests that considering topic shifts in a student’s study, capturing
semantic relationships, and using individual flashcards properties, all
benefit student modeling. Further, on unseen cards, where we expect semantic
relations to be most useful, the No BERT ablation has the worst AUC and ECE.
Thus, capturing semantic interplay is a viable strategy for student modeling
on unseen cards, motivating future research in content-aware scheduling.

Figure 3:  $\text{KAR}^{\text{3}}\text{L}$ forgetting curve for two
semantically related cards about U.S. presidents. After Card 1 is studied, the
predicted recall probability of the semantically related Card 2 increases,
despite not being studied.

###  4.5 Forgetting Curve Analysis

Forgetting curves are theoretical models representing memory decay over time
Ebbinghaus (2013); Murre and Dros (2015). While many student models explicitly
fit to exponential or power-law forgetting curves Upadhyay et al. (2020);
Settles and Meeder (2016), $\text{KAR}^{\text{3}}\text{L}$ does not in
exchange for more flexible memory representations. To simulate a forgetting
curve in $\text{KAR}^{\text{3}}\text{L}$, we query our model to predict the
recall of a flashcard while incrementing the feature for “time since last
review.”

To understand the role of BERT embeddings in $\text{KAR}^{\text{3}}\text{L}$,
we display simulated forgetting curves for two semantically related
flashcards. In Figure 3, Card 1 (James Garfield, the 20th U.S. president) is
studied once on day 0 and again on day 10. When Card 1 is recalled
successfully on day 10, the recall probability of the related Card 2 (Abraham
Lincoln, the 16th U.S. president) increases despite not being studied. This
example further underscores the benefit of modeling the semantic relationships
of flashcards: $\text{KAR}^{\text{3}}\text{L}$ intelligently adjust
predictions of student recall across semantically-related flashcards based on
the study of just one. In Appendix A.3, we simulate more
$\text{KAR}^{\text{3}}\text{L}$ forgetting curves.

###  4.6 $\text{KAR}^{\text{3}}\text{L}$ Semantic Retrieval Case Study

We further show the benefit of retrieval via a case study from our offline
dataset, where the user studies a new flashcard on Japanese authors (Figure
4). The top-3 flashcards retrieved by $\text{KAR}^{\text{3}}\text{L}$ are
topically related to the current card, like Japanese novels and Shinto, while
the last-3 cards seen by the user concern European history, indicating a topic
shift in the user’s study. Despite this shift, $\text{KAR}^{\text{3}}\text{L}$
can still accurately predict the student’s recall, since
$\text{KAR}^{\text{3}}\text{L}$ can exploit the student’s accuracy on the
retrieved flashcards (from $\mathcal{X}(z)$) to infer their knowledge of
Japanese literature. Since $\text{KAR}^{\text{3}}\text{L}$ groups semantically
similar flashcards during inference with retrieval,
$\text{KAR}^{\text{3}}\text{L}$ can also dynamically collect flashcards as
distinct knowledge concepts (KCs), i.e., the fine-grained KC of Japanese
culture in this case. Thus, through BERT embeddings,
$\text{KAR}^{\text{3}}\text{L}$ can recover KCs without requiring any KC
annotations that are typically used in KT datasets Abdelrahman et al. (2023),
further highlighting the potential of content-aware flashcard schedulers.

Figure 4:  Top-3 retrieved vs past-3 studied flashcards when the user studies
a new card on Japanese literature.

##  5 Online Evaluation

Extending the strong results of our offline evaluation (section 4.3), we now
assess $\text{KAR}^{\text{3}}\text{L}$ in a practical, online setting. Our
online evaluation studies the unexplored question: How much can a DKT-based
scheduler like $\text{KAR}^{\text{3}}\text{L}$ enhance learning compared to
the state-of-the-art non-DKT scheduler FSRS?

To answer this question, we first propose a novel teaching policy that fully
exploits the predictive power of DKT student models like
$\text{KAR}^{\text{3}}\text{L}$ (section 5.1). Next, we design a test mode
user study to serve as the first online comparison of DKT
($\text{KAR}^{\text{3}}\text{L}$) and non-DKT (FSRS) schedulers (section 5.2).
Finally, we evaluate the study trajectories of learners from our user study
(section 5.3), answering the open question surrounding the online
effectiveness of DKT models relative to state-of-the-art non-DKT schedulers.

###  5.1 A Delta-Based Teaching Policy for $\text{KAR}^{\text{3}}\text{L}$

After $\text{KAR}^{\text{3}}\text{L}$ predicts if the student can recall a
given flashcard, a teaching policy decides _when_ to schedule this card
Hunziker et al. (2019). As DKT models directly predict recall without learning
parameters like difficulty or memory strength, the only compatible existing
policy for DKT models like $\text{KAR}^{\text{3}}\text{L}$ is threshold-based,
which picks flashcards near specified retention levels like 0.9 Ye et al.
(2022) or 0.94 Eglington and Pavlik Jr (2020). A threshold-based policy for
$\text{KAR}^{\text{3}}\text{L}$ could run the classifier
$p(a_{t}|f_{t},\mathcal{F}^{\prime})$ on every flashcard and pick those with
predicted recall near a specified retention level. But without extra
heuristics, this method will not schedule cards that
$\text{KAR}^{\text{3}}\text{L}$ predicts a student cannot recall or has
forgotten (i.e. predicted recall of 0), even if studying these flashcards
would greatly improve retention and subject mastery.

To address this issue, we propose a delta-based teaching policy. For each
candidate flashcard $f$, we compute how studying $f$ at time $t$ would benefit
the student’s recall of $f$ at the future delta-based time
$t^{\prime}=t+\Delta$. When $\text{KAR}^{\text{3}}\text{L}$ (or any DKT model)
predicts that the student would recall $f$ correctly at time $t$ with
probability $p_{t}(f)$, we seek to compute by how much the future recall
probability $p_{t^{\prime}}(f)$ would increase if $f$ is studied at time $t$:

$p_{t^{\prime}}(f\mid\text{study }f\text{ at }t)-p_{t^{\prime}}(f\mid\text{no
study}).$ (5)

To get ${p_{t^{\prime}}(f\mid\text{study }f\text{ at }t)}$, the future recall
probability, we consider the two possible outcomes of studying the card $f$ at
time $t$: the student’s answer can be correct or incorrect. We weigh the two
outcomes by the model’s initial prediction $p_{t}(f)$:

$\displaystyle p_{t^{\prime}}(f\mid$ $\displaystyle\text{ study }f\text{ at
}t)\coloneqq$ (6) $\displaystyle p_{t^{\prime}}(f\mid\text{correct at }t)\cdot
p_{t}(f)$ $\displaystyle+$ $\displaystyle p_{t^{\prime}}(f\mid\text{incorrect
at }t)\cdot(1-p_{t}(f)).$

To compute the two $p_{t^{\prime}}$ values, we query the model as if we are at
time $t^{\prime}=t+\Delta$ and if the student answered correctly or
incorrectly at time $t$, with all features in $\mathcal{X}(f)$ updated
accordingly. We compute $p_{t^{\prime}}(f\mid\text{no study})$ similarly,
querying the model as if we are at time $t^{\prime}$ and if the student did
not study $f$ at $t$. In all, Eq. 5 gives the expected gain in recall on a
flashcard after time $\Delta$ if the student studies the flashcard at time
$t$, which we call the delta score.

The flashcards with the $n$-highest delta scores are scheduled as the next $n$
flashcards to study. With our delta-based teaching policy, we ensure that each
flashcard is studied for maximizing learning gains, preventing flashcards from
being neglected solely due to having low predicted recall and fully exploiting
the predictive power of DKT.

###  5.2 Test Mode Setup

For our user study, we deploy FSRS and $\text{KAR}^{\text{3}}\text{L}$ with
our delta teaching policy (i.e. $\text{KAR}^{\text{3}}\text{L}+\Delta$),
setting $\Delta$ equal to 1 day. Studying the impact of schedulers on learning
is challenging, as: (1) students want to study diverse subjects; (2) students
have varying background knowledge; and (3) learning, a multifaceted process,
is difficult to quantify.

To address (1), we create two test sets that are fixed across users, both
containing 20 manually-written cards from seven diverse Quizbowl bonus
questions Rodriguez et al. (2019). This ensures that each user will be
evaluated on the same flashcards, which will likely have at least some facts
of interest to the user. To mitigate (2), we follow best practices and use a
within-subject design Lindsey et al. (2014), where each user is randomly
assigned $\text{KAR}^{\text{3}}\text{L}$ for one of the test sets, and FSRS
for the other set. Thus, users can experience both schedulers, keeping
background knowledge consistent.

For (3), we decide to focus on medium-term learning, which we define as the
ability to retain and recall flashcards over several days. This goal reflects
the time span in which students report preparing for exams; Wissman et al.
(2012) find that students often study with flashcards for five days or less
and study no more than half their deck of flashcards at a time. Mirroring
this, our users review ten flashcards from the test set of 20, scheduled by
FSRS or $\text{KAR}^{\text{3}}\text{L}+\Delta$, once a day for five days. On
day six, the user completes a post-test and studies all 20 cards from the test
set. Following Alshammari (2019), we compute medium-term learning with the
average accuracy on the post-test set and when students first see each
flashcard (i.e. pre-test), We recruit users with the same procedure as section
3.3 and award all users who complete our study $50.

Scheduler | Pre-Test Accuracy | Post-Test Accuracy
---|---|---
FSRS | 0.44 | 0.91
$\text{KAR}^{\text{3}}\text{L}+\Delta$ | 0.45 | 0.90
Table 3: Average student pre-test and post-test accuracy when studying with
$\text{KAR}^{\text{3}}\text{L}+\Delta$ and FSRS.

###  5.3 User Study Results

Table 3 displays results on 32 completed study trajectories from 27 users with
FSRS and $\text{KAR}^{\text{3}}\text{L}+\Delta$. We find that both schedulers
help students achieve a similarly high mastery of the test mode cards, with a
notable doubling of pre-test to post-test accuracy ($0.45$ to $0.9$). This
suggests that $\text{KAR}^{\text{3}}\text{L}+\Delta$ improves medium-term
learning comparably to FSRS, further pointing to its efficacy for factual
learning.

Viewing these results along with the offline evaluation (section 4.3), we note
that $\text{KAR}^{\text{3}}\text{L}+\Delta$: 1) makes more accurate and
calibrated recall predictions than FSRS on seen flashcards; 2) can
discriminate between unseen flashcards, an ability not present in FSRS; and 3)
enhances medium-term learning comparably to FSRS. In all, these findings
suggest that $\text{KAR}^{\text{3}}\text{L}+\Delta$ not only equals but may
surpass FSRS as a scheduler. Since $\text{KAR}^{\text{3}}\text{L}+\Delta$ is
the first use of DKT and language models for content-aware scheduling and it
already at least matches the state-of-the-art, our results reveal a clear path
for adding DKT and language models into flashcard systems.

##  6 Related Work

###  6.1 Flashcard Scheduling

Flashcards excel at helping students recall facts, the bedrock for higher-
order learning Dunlosky and Rawson (2015). Their versatility makes them a
preferred tool for diverse subjects, from vocabulary Komachali and Khodareza
(2012); Sitompul (2013) to medicine Schmidmaier et al. (2011); Lu et al.
(2021). The order and spacing of flashcards strongly affect memory Kornell
(2009), motivating research into designing intelligent scheduling systems.

Earlier schedulers like Leitner Leitner (1974) and SuperMemo-2 Wozniak (1990)
opt for rule-based update heuristics to schedule review dates. Subsequent
schedulers are grounded in cognitive theory, deploying teaching policies with
student model predictions. Settles and Meeder (2016) propose half-life
regression (HLR) student models as trainable power-law and exponential
forgetting curves Ebbinghaus (1913), theoretical models of memory decay
derived from empirical research.

Later works extend HLR and build teaching policies to schedule flashcards
based on learned parameters and predictions from forgetting curve student
models. Reddy et al. (2017) optimize their teaching policy with reinforcement
learning, while MEMORIZE Tabibian et al. (2019) and SELECT Upadhyay et al.
(2020) minimize cost values to optimize review times. Recent models like FSRS
and DHP enhance these methods by optimizing spaced repetition via stochastic
shortest path algorithms and time series data Ye et al. (2022); Su et al.
(2023).

Notably, unlike DKT models, the student models in these schedulers cannot make
discriminative predictions on unseen flashcards. Thus, these schedulers use
arbitrary heuristics to introduce new cards, such as ordering by creation date
Elmes (2021). We address this issue with $\text{KAR}^{\text{3}}\text{L}$,
which makes predictions on unseen cards by drawing from DKT research and
leveraging semantic relationships.

###  6.2 Deep Knowledge Tracing

$\text{KAR}^{\text{3}}\text{L}$ draws from deep knowledge tracing (DKT)
Abdelrahman et al. (2023) which represents content in a neural embedding
space. The first DKT model used an RNN to capture the temporal dynamics of a
student’s study history Piech et al. (2015). Later works refine this model
with graph representations Yang et al. (2021); Song et al. (2022), forgetting
features Nagatani et al. (2019); Abdelrahman and Wang (2022), memory
structures Abdelrahman and Wang (2019); Gu et al. (2022), and metacognition
Carlon and Cross (2022). $\text{KAR}^{\text{3}}\text{L}$ is most similar to
SAINT+ Shin et al. (2021), a transformer DKT model, and LM-KT Srivastava and
Goodman (2021), a question generator using causal language modeling for
student modeling.

In this work, we address several practical challenges of DKT models by
designing: 1) the first retrieval-augmented student model to improve the
efficiency of embedding a student’s study history; 2) a new dataset of diverse
trivia questions to study the ability of DKT models to capture varied semantic
ties; and 3) a novel teaching policy to fully exploit the predictive
capabilities of DKT.

##  7 Conclusion

We develop $\text{KAR}^{\text{3}}\text{L}+\Delta$, the first content-aware
flashcard scheduler using DKT and language models for semantic inferences,
extending beyond traditional flashcard-level features. Our student model
produces accurate and well-calibrated recall predictions, and improves
efficiency through a BERT-based retriever. Our ablation study, forgetting
curve analysis, and retrieval case study further illustrate the advantages of
modeling semantic relations between cards, particularly on unseen cards. Along
with modeling, we contribute to future research by releasing a diverse,
content-rich dataset of student study history. Our dataset contrasts existing
domain-specific benchmarks, serving as a valuable tool to ensure models can
cater to students with varied learning interests. Finally, we design a delta-
based teaching policy to deploy $\text{KAR}^{\text{3}}\text{L}$ online. Our
policy enables $\text{KAR}^{\text{3}}\text{L}$ to enhance medium-term learning
comparably to the state-of-the-art scheduler, FSRS, and is compatible with any
model that predicts student recall. Overall, we highlight the advantages of
using DKT and language models to capture the semantic relations of flashcards,
which we hope will motivate future developments of content-aware adaptive
tutoring systems.

##  8 Limitations

One limitation of $\text{KAR}^{\text{3}}\text{L}$, which is manifested in some
form in all DKT models, is that our model uses BERT representations and a
neural classifier, resulting in a slower inference time compared to student
models which only use flashcard-level features. To minimize this limitation,
we consider two design choices. First, rather than embedding the entire
student history like existing DKT models, we perform top-$k$ retrieval,
enabling $\text{KAR}^{\text{3}}\text{L}$ to have a consistent inference time
that does not scale with the size of the student’s study history. Second, we
implement our retriever operations with FAISS Johnson et al. (2019), an
efficient vector database. This allows us to quickly look up the
representation of each flashcard derived from QANTA, eliminating the time
needed to tokenize and feed each flashcard through BERT, and efficiently
perform Maximum Inner-Product Search. During our test mode user study, we did
not receive complaints about the inference time of
$\text{KAR}^{\text{3}}\text{L}$.

Further, while $\text{KAR}^{\text{3}}\text{L}$ is an effective framework for
student modeling on our diverse dataset on trivia questions, we have not
analyzed the performance of $\text{KAR}^{\text{3}}\text{L}$ on domain-specific
DKT benchmarks that do not have easily accessible textual content, such as
EdNet Choi et al. (2020) or ASSISTments222To obtain the textual content of
ASSIStments, you must send an additional email for verification and agree to a
Terms of Use before your request can even be processed. In contrast, our
dataset will release the flashcard content for public use. Selent et al.
(2016). Since the primary goal of this work was to design a content-aware
scheduler, we require a diverse and content-focused dataset to evaluate our
model. In future works, if these datasets provide their textual content, it
would be interesting to study if the performance of
$\text{KAR}^{\text{3}}\text{L}$ is still strong, or how transfer learning
techniques Weiss et al. (2016) can help $\text{KAR}^{\text{3}}\text{L}$ adapt
to specific domains and datasets.

##  9 Ethical Considerations

The goal of adaptive student models like $\text{KAR}^{\text{3}}\text{L}$ is to
make personalized predictions about a student’s knowledge level. When making
such tailored predictions, it is crucial to ensure that these student models
are not exploiting private information about the user. To ensure that models
trained on our dataset do not succumb to this ethical risk, our dataset only
identifies users by a randomized ID. Further, our data collection and test
mode user study were both approved by an Institutional Review Board (IRB),
allowing us to fully address any potential risks of our study. All users were
compensated based on a raffle system, and could win either $10, $15, or $50
based on the study. In our advertisements, it was made clear to users before
signing up that they would be part of a research study.

## References

  * Abdelrahman and Wang (2019) Ghodai Abdelrahman and Qing Wang. 2019.  Knowledge tracing with sequential key-value memory networks.  In _Proceedings of the 42nd international ACM SIGIR conference on research and development in information retrieval_ , pages 175–184.
  * Abdelrahman and Wang (2022) Ghodai Abdelrahman and Qing Wang. 2022.  Deep graph memory networks for forgetting-robust knowledge tracing.  _IEEE Transactions on Knowledge and Data Engineering_.
  * Abdelrahman et al. (2023) Ghodai Abdelrahman, Qing Wang, and Bernardo Nunes. 2023.  Knowledge tracing: A survey.  _ACM Computing Surveys_ , 55(11).
  * Alhawiti (2014) Khaled M Alhawiti. 2014.  Natural language processing and its use in education.  _International Journal of Advanced Computer Science and Applications_ , 5(12).
  * Alshammari (2019) Mohammad T Alshammari. 2019.  Design and learning effectiveness evaluation of gamification in e-learning systems.  _International Journal of Advanced Computer Science and Applications_ , 10(9).
  * Anonthanasap et al. (2015) Orapin Anonthanasap, Monticha Ketna, and Teerapong Leelanupab. 2015.  Automated english mnemonic keyword suggestion for learning japanese vocabulary.  In _2015 7th International Conference on Information Technology and Electrical Engineering (ICITEE)_ , pages 638–643. IEEE.
  * Balepur et al. (2023) Nishant Balepur, Jie Huang, and Kevin Chang. 2023.  Expository text generation: Imitate, retrieve, paraphrase.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 11896–11919, Singapore. Association for Computational Linguistics.
  * Brusilovsky et al. (2015) Peter Brusilovsky, Sibel Somyürek, Julio Guerra, Roya Hosseini, Vladimir Zadorozhny, and Paula J Durlach. 2015.  Open social student modeling for personalized learning.  _IEEE Transactions on Emerging Topics in Computing_ , 4(3):450–461.
  * Burstein (2009) Jill Burstein. 2009.  Opportunities for natural language processing research in education.  In _Computational Linguistics and Intelligent Text Processing: 10th International Conference, CICLing 2009, Mexico City, Mexico, March 1-7, 2009. Proceedings 10_ , pages 6–27. Springer.
  * Carlon and Cross (2022) May Kristine Jonson Carlon and Jeffrey S Cross. 2022.  Knowledge tracing for adaptive learning in a metacognitive tutor.  _Open Education Studies_ , 4(1):206–224.
  * Choi et al. (2020) Youngduck Choi, Youngnam Lee, Dongmin Shin, Junghyun Cho, Seoyon Park, Seewoo Lee, Jineon Baek, Chan Bae, Byungsoo Kim, and Jaewe Heo. 2020.  Ednet: A large-scale hierarchical dataset in education.  In _Artificial Intelligence in Education: 21st International Conference, AIED 2020, Ifrane, Morocco, July 6–10, 2020, Proceedings, Part II 21_ , pages 69–73. Springer.
  * Chrysafiadi et al. (2015) Konstantina Chrysafiadi, Maria Virvou, Konstantina Chrysafiadi, and Maria Virvou. 2015.  Student modeling for personalized education: A review of the literature.  _Advances in personalized web-based education_ , pages 1–24.
  * Cui and Sachan (2023) Peng Cui and Mrinmaya Sachan. 2023.  Adaptive and personalized exercise generation for online language learning.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 10184–10198, Toronto, Canada. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dunlosky and Rawson (2015) John Dunlosky and Katherine A Rawson. 2015.  Practice tests, spaced practice, and successive relearning: Tips for classroom use and for guiding students’ learning.  _Scholarship of Teaching and Learning in Psychology_ , 1(1):72.
  * Ebbinghaus (1913) Hermann Ebbinghaus. 1913.  _Memory: A contribution to experimental psychology._ Teachers College Press, New York.
  * Ebbinghaus (2013) Hermann Ebbinghaus. 2013.  Memory: A contribution to experimental psychology.  _Annals of neurosciences_ , 20(4):155.
  * Eglington and Pavlik Jr (2020) Luke G. Eglington and Philip I. Pavlik Jr. 2020.  Optimizing practice scheduling requires quantitative tracking of individual item performance.  _npj Science of Learning_ , 5(1):1–10.
  * Elmes (2021) Damien Elmes. 2021.  Anki. powerful, intelligent flashcards.
  * Gu et al. (2022) Hengnian Gu, Xiaoxiao Dong, and Dongdai Zhou. 2022.  Dynamic key-value memory networks based on concept structure for knowledge tracing.  In _2022 4th International Conference on Computer Science and Technologies in Education (CSTE)_ , pages 290–294. IEEE.
  * Hunziker et al. (2019) Anette Hunziker, Yuxin Chen, Oisin Mac Aodha, Manuel Gomez Rodriguez, Andreas Krause, Pietro Perona, Yisong Yue, and Adish Singla. 2019.  Teaching Multiple Concepts to a Forgetful Learner.  _arXiv:1805.08322 [cs]_.
  * Jiang et al. (2023) Zhengbao Jiang, Frank F Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi-Yu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023.  Active retrieval augmented generation.  _arXiv preprint arXiv:2305.06983_.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019.  Billion-scale similarity search with GPUs.  _IEEE Transactions on Big Data_ , 7(3):535–547.
  * Kingma and Ba (2015) Diederik Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_ , San Diega, CA, USA.
  * Komachali and Khodareza (2012) Maryam Eslahcar Komachali and Mohammadreza Khodareza. 2012.  The effect of using vocabulary flash card on iranian pre-university students’ vocabulary knowledge.  _International Education Studies_ , 5(3):134–147.
  * Kornell (2009) Nate Kornell. 2009.  Optimising learning using flashcards: Spacing is more effective than cramming.  _Applied Cognitive Psychology: The Official Journal of the Society for Applied Research in Memory and Cognition_ , 23(9):1297–1317.
  * Lee and Lan (2023) Jaewook Lee and Andrew Lan. 2023.  Smartphone: Exploring keyword mnemonic with auto-generated verbal and visual cues.  In _International Conference on Artificial Intelligence in Education_ , pages 16–27. Springer.
  * Lee et al. (2019) Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. 2019.  Latent retrieval for weakly supervised open domain question answering.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6086–6096, Florence, Italy. Association for Computational Linguistics.
  * Leitner (1974) S Leitner. 1974.  So lernt man lernen (herder, freiburg, germany).
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _Advances in Neural Information Processing Systems_ , 33:9459–9474.
  * Liang et al. (2023) Kai-Hui Liang, Sam Davidson, Xun Yuan, Shehan Panditharatne, Chun-Yen Chen, Ryan Shea, Derek Pham, Yinghua Tan, Erik Voss, and Luke Fryer. 2023.  ChatBack: Investigating methods of providing grammatical error feedback in a GUI-based language learning chatbot.  In _Proceedings of the 18th Workshop on Innovative Use of NLP for Building Educational Applications (BEA 2023)_ , pages 83–99, Toronto, Canada. Association for Computational Linguistics.
  * Lindsey et al. (2014) Robert V Lindsey, Jeffery D Shroyer, Harold Pashler, and Michael C Mozer. 2014.  Improving students’ long-term knowledge retention through personalized review.  _Psychological science_ , 25(3):639–647.
  * Litman (2016) Diane Litman. 2016.  Natural language processing for enhancing teaching and learning.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 30.
  * Lu et al. (2021) Matthew Lu, John H Farhat, and Gary L Beck Dallaghan. 2021.  Enhanced learning and retention of medical knowledge using the mobile flash card application anki.  _Medical Science Educator_ , 31(6):1975–1981.
  * Manhas (2013) Jatinder Manhas. 2013.  A study of factors affecting websites page loading speed for efficient web performance.  _International Journal of Computer Sciences and Engineering_ , 1(3):32–35.
  * Mozer et al. (2019) Michael C Mozer, Melody Wiseheart, and Timothy P Novikoff. 2019.  Artificial intelligence to support human instruction.  _Proceedings of the National Academy of Sciences_ , 116(10):3953–3955.
  * Murre and Dros (2015) Jaap MJ Murre and Joeri Dros. 2015.  Replication and analysis of ebbinghaus’ forgetting curve.  _PloS one_ , 10(7):e0120644.
  * Naeini et al. (2015) Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. 2015.  Obtaining well calibrated probabilities using bayesian binning.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 29.
  * Nagatani et al. (2019) Koki Nagatani, Qian Zhang, Masahiro Sato, Yan-Ying Chen, Francine Chen, and Tomoko Ohkuma. 2019.  Augmenting knowledge tracing by considering forgetting behavior.  In _The world wide web conference_ , pages 3101–3107.
  * Palma Gomez et al. (2023) Frank Palma Gomez, Subhadarshi Panda, Michael Flor, and Alla Rozovskaya. 2023.  Using neural machine translation for generating diverse challenging exercises for language learner.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6115–6129, Toronto, Canada. Association for Computational Linguistics.
  * Pavlik Jr et al. (2020) Philip I Pavlik Jr, Andrew M Olney, Amanda Banker, Luke Eglington, and Jeffrey Yarbro. 2020.  The mobile fact and concept textbook system (mofacts).  _Grantee Submission_.
  * Piech et al. (2015) Chris Piech, Jonathan Bassen, Jonathan Huang, Surya Ganguli, Mehran Sahami, Leonidas J Guibas, and Jascha Sohl-Dickstein. 2015.  Deep knowledge tracing.  _Advances in neural information processing systems_ , 28.
  * Pope et al. (2023) Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. 2023.  Efficiently scaling transformer inference.  _Proceedings of Machine Learning and Systems_ , 5.
  * Reddy et al. (2016) 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_ , pages 1815–1824.
  * Reddy et al. (2017) Siddharth Reddy, Sergey Levine, and Anca Dragan. 2017.  Accelerating human learning with deep reinforcement learning.  In _NIPS workshop: teaching machines, robots, and humans_.
  * Rodriguez et al. (2019) Pedro Rodriguez, Shi Feng, Mohit Iyyer, He He, and Jordan L. Boyd-Graber. 2019.  Quizbowl: The case for incremental question answering.  _ArXiv_ , abs/1904.04792.
  * Savva et al. (2014) Manolis Savva, Angel X Chang, Christopher D Manning, and Pat Hanrahan. 2014.  Transphoner: Automated mnemonic keyword generation.  In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , pages 3725–3734.
  * Schmidmaier et al. (2011) Ralf Schmidmaier, Rene Ebersbach, Miriam Schiller, Inga Hege, Matthias Holzer, and Martin R Fischer. 2011.  Using electronic flashcards to promote learning in medical students: retesting versus restudying.  _Medical education_ , 45(11):1101–1110.
  * Selent et al. (2016) Douglas Selent, Thanaporn Patikorn, and Neil Heffernan. 2016.  Assistments dataset from multiple randomized controlled experiments.  In _Proceedings of the Third (2016) ACM Conference on Learning@ Scale_ , pages 181–184.
  * Settles and Meeder (2016) 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 (volume 1: long papers)_ , pages 1848–1858.
  * Shin et al. (2021) Dongmin Shin, Yugeun Shim, Hangyeol Yu, Seewoo Lee, Byungsoo Kim, and Youngduck Choi. 2021.  Saint+: Integrating temporal features for ednet correctness prediction.  In _LAK21: 11th International Learning Analytics and Knowledge Conference_ , pages 490–496.
  * Shrivastava and Li (2014) Anshumali Shrivastava and Ping Li. 2014.  Asymmetric lsh (alsh) for sublinear time maximum inner product search (mips).  _Advances in neural information processing systems_ , 27.
  * Sitompul (2013) Elsa Yusrika Sitompul. 2013.  Teaching vocabulary using flashcards and word list.  _Journal of English and Education_ , 1(1):52–58.
  * Song et al. (2022) Xiangyu Song, Jianxin Li, Qi Lei, Wei Zhao, Yunliang Chen, and Ajmal Mian. 2022.  Bi-clkt: Bi-graph contrastive learning based knowledge tracing.  _Knowledge-Based Systems_ , 241:108274.
  * Srivastava and Goodman (2021) Megha Srivastava and Noah Goodman. 2021.  Question generation for adaptive education.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 692–701, Online. Association for Computational Linguistics.
  * Su et al. (2023) Jingyong Su, Junyao Ye, Liqiang Nie, Yilong Cao, and Yongyong Chen. 2023.  Optimizing spaced repetition schedule by capturing the dynamics of memory.  _IEEE Transactions on Knowledge and Data Engineering_.
  * Tabibian et al. (2019) 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):3988–3993.
  * Tyen et al. (2022) Gladys Tyen, Mark Brenchley, Andrew Caines, and Paula Buttery. 2022.  Towards an open-domain chatbot for language practice.  In _Proceedings of the 17th Workshop on Innovative Use of NLP for Building Educational Applications (BEA 2022)_ , pages 234–249, Seattle, Washington. Association for Computational Linguistics.
  * Upadhyay et al. (2020) Utkarsh Upadhyay, Graham Lancashire, Christoph Moser, and Manuel Gomez-Rodriguez. 2020.  Large-scale randomized experiment reveals machine learning helps people learn and remember more effectively.  _arXiv:2010.04430 [cs, stat]_.  ArXiv: 2010.04430.
  * Weiss et al. (2016) Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. 2016.  A survey of transfer learning.  _Journal of Big data_ , 3(1):1–40.
  * Wissman et al. (2012) Kathryn T Wissman, Katherine A Rawson, and Mary A Pyc. 2012.  How and when do students use flashcards?  _Memory_ , 20(6):568–579.
  * Wozniak (1990) Piotr A Wozniak. 1990.  Optimization of learning.  _Unpublished master’s thesis, Poznan University of Technology. Poznan, Poland_.
  * Yang et al. (2021) Yang Yang, Jian Shen, Yanru Qu, Yunfei Liu, Kerong Wang, Yaoming Zhu, Weinan Zhang, and Yong Yu. 2021.  Gikt: a graph-based interaction model for knowledge tracing.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14–18, 2020, Proceedings, Part I_ , pages 299–315. Springer.
  * Ye et al. (2022) Junyao Ye, Jingyong Su, and Yilong Cao. 2022.  A stochastic shortest path algorithm for optimizing spaced repetition scheduling.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’22, page 4381–4390, New York, NY, USA. Association for Computing Machinery.

##  Appendix A Appendix

###  A.1 $\text{KAR}^{\text{3}}\text{L}$ Classifier Features

Table 4 lists all the hand-picked features used by
$\text{KAR}^{\text{3}}\text{L}$ in conjunction with BERT representations. All
features are normalized using mean value and standard deviation computed on
the training set. Features with IDs 16 through 20 are computed using the
Leitner Leitner (1974) and SM-2 Wozniak (1990) algorithms. All features that
go beyond the flashcard scope, such as the accuracy of the student in the
current session, are removed during the test mode study to ensure
$\text{KAR}^{\text{3}}\text{L}+\Delta$ does not have an unfair advantage
compared to FSRS.

###  A.2 Flashcard Examples

In Table 5, we provide examples of the flashcards created from the QANTA
dataset spanning 11 unique topics. The QANTA dataset is publicly available and
we used the dataset with its intended research use. These flashcards are
deployed into $\text{KAR}^{\text{3}}\text{L}$, where 543 participants produced
123,143 study records. In these records, 44.02 percent contain studies on new
flashcards and students correctly answer the flashcard shown 71.80 percent of
the time. On average, each user studied 226.78 flashcards during the data
collection period.

The data used to create our flashcards is well-established and was not
significantly altered in this work, so we did not check if the dataset
uniquely identifies individuals or contains offensive content. All of our
flashcards are written in English, containing facts primarily targeted toward
students in the American high school and college education systems. The only
additional data we collected beyond this that is released is the user’s ID,
the date and time of study, and which flashcards this user got correct and
incorrect, which pose no harms.

In Tables 6 and 7 we show the descriptions and summary statistics of the
qualitative and quantitative columns in our released dataset, respectively.

###  A.3 Forgetting Curves

In this section, we provide more examples of forgetting curves. Unlike
previous work which forces the student model to follow a specific forgetting
function, we consider student modeling as predicting the binary outcome of
each study. In Figure 5, we showcase the flexibility of our forgetting curves,
and display visualizations of how the forgetting curve of a flashcard changes
depending on its predicted recall probability.

###  A.4 Training Details

We train $\text{KAR}^{\text{3}}\text{L}$ for 12 hours using a single NVIDIA
RTX:A4000 GPU. Parameters were manually selected without search. We use the
default BERT configuration, and our classifier is implemented in
PyTorch333https://pytorch.org/ with the following layers: 1) BERT model; 2)
Dropout; 3) Linear Layer; 4) GELU Activation Layer; 5) Layer Normalization; 6)
Dropout; 7) Linear Layer. We minimize the binary cross entropy loss according
to Equation 4.

All of our baselines are implemented using the official code provided by the
authors of the respective papers, and all hyperparameters in the model
implementations were chosen according to the reported hyperparameters in the
paper. LM-KT was trained on a single NVIDIA RTX:A6000 GPU using 30 epochs and
all other training parameters were the default values in the provided code.
FSRS was trained using the Collaboratory notebook provided by the authors
using default parameters.

All metrics were reported from a single run. Accuracy, AUROC, and Expected
Calibration Error were all computed using scikit-learn.444https://scikit-
learn.org/

###  A.5 User Study Instructions

During our user studies, we ensure to provide clear instructions to our users.
First, on the home page of our app, the users are able to read the procedures
of our IRB (Figure 6). This serves as detailed instructions for our user
studies. Second, when it is time for the user to study test mode, a popup
appears giving brief instructions about the next test set they are about to
study (Figure 7). Users were also made aware of the confidentiality of their
data (Figure 8), which can be viewed by clicking on the IRB link on our home
page. The rest of the instructions are outlined in our advertisements. For
anonymity purposes, we are unable to share the advertisements but will do so
upon acceptance.

###  A.6 Additional Related Work: NLP for Education

Flashcard learning is just one educational application that benefits from NLP
Burstein (2009); Alhawiti (2014); Litman (2016). Recent advancements in this
field include generating education content Palma Gomez et al. (2023); Cui and
Sachan (2023), designing educational chatbots Tyen et al. (2022); Liang et al.
(2023), and creating mnemonic devices Savva et al. (2014); Anonthanasap et al.
(2015); Lee and Lan (2023). We hope that our findings, such as our discovered
benefit of retrieval, DKT, and language models for student modeling and
release of a diverse study history dataset, will enhance the next generation
of NLP-powered educational tools.

ID | Feature | ID | Feature
---|---|---|---
1 | # cards studied by student | 11 | Previous Delta
2 | # cards answered correctly by student | 12 | Previous study outcome
3 | # cards answered incorrectly by student | 13 | Delta in current session
4 | # cards studied in current session | 14 | Previous Delta in current session
5 | # cards answered correctly in session | 15 | Previous study outcome in session
6 | # cards answered incorrectly in session | 16 | Leitner box
7 | Average accuracy of student | 17 | SM2 e-factor
8 | Accuracy of student on this card | 18 | SM2 current interval
9 | Accuracy of student in session | 19 | Delta to Leitner scheduled date
10 | Delta - time passed since previous study | 20 | Delta to SM2 scheduled date
Table 4: Complete list of hand-picked features used in
$\text{KAR}^{\text{3}}\text{L}$.

Category | Example Front (Question) | Example Back (Answer) | Category Frequency
---|---|---|---
Philosophy |  | William James and, later, Richard Rorty continued
---
a strain of philosophy largely inaugurated by this philosopher
C.S. Peirce | 425
Trash (Pop Culture) |  | Recently-cancelled FOX show which starred Eliza Dushku
---
as Echo and which was directed by Joss Whedon
Dollhouse | 496
Mythology |  | To pay Thrym back for stealing Mjolnir, Thor wore bridal
---
clothes to disguise himself as this goddess
Freya | 1194
Science |  | Metal which is used in aerospace applications due to its
---
durability, with atomic number 22 and symbol Ti
Titanium | 2423
Current Events |  | A citizen of this nation crashed a plane into the
---
French Alps in March 2015
Federal Republic of Germany | 99
Fine Arts |  | Revived by Wanda Landowski, it helped bring success
---
to its 1955 performer, Glenn Gould
the Goldberg Variartions | 3158
Religion |  | This text was originally written in unknown characters
---
referred to as "Reformed Egyptian"
The Book of Mormon | 807
Literature |  | Chief harpooner of the Pequod, a cannibal companion of
---
Ishmael in Melville’s Moby Dick
Queequeg | 4822
Social Science |  | Luigi Pasinetti created a fifteen-equation mathematical
---
model of this economist’s views
David Ricardo | 966
Georgraphy |  | The Franz Joseph and Fox Glaciers can be found in this nation,
---
notable for existing at low altitudes
New Zealand | 1053
History |  | This figure ruled during the Interregnum and led the New Model Army
---
after the assassination of Charles I
Oliver Cromwell | 8476

Table 5: Examples of flashcards spanning 11 topics derived from the QANTA dataset. Figure 5: The average forgetting curve ten days before and after a study (which happens at day zero) for both when the user succeed and failed at the recall. Unlike exponential forgetting models, the convexity of our forgetting curve depends on both the current predicted recall and the outcome of the most recent study. Column | Description | Num Unique
---|---|---
user_id | Identifier for the user | 543
card_id | Identifier for the flashcard | 18663
card_text | Text on the flashcard | 17554
deck_id | Identifier for the deck (subject) being studied | 71
deck_name | Name of the deck (subject) being studied | 60
Table 6: Qualitative value columns in our released dataset, along with descriptions and number of unique values. Column | Description | Average | Min | Max
---|---|---|---|---
is_new_fact | Whether the user has (not) seen this card before | 0.44 | 0.00 | 1.00
user_n_study_positive | Number of total times the user has studied and answered correctly | 1951.53 | 0.00 | 14727.00
user_n_study_negative | Number of total times the user has studied and answered incorrectly | 471.14 | 0.00 | 3515.00
user_n_study_total | Number of total times the user has studied | 2422.68 | 0.00 | 16264.00
card_n_study_positive | Number of unique cards that the user has answered correctly | 6.78 | 0.00 | 82.00
card_n_study_negative | Number of unique cards that the user has answered incorrectly | 1.93 | 0.00 | 35.00
card_n_study_total | Number of unique cards that the user has answered in total | 8.72 | 0.00 | 92.00
acc_user | Accuracy of this user in all studies | 0.70 | 0.00 | 1.00
acc_card | Accuracy of all users on this card | 0.60 | 0.00 | 1.00
acc_usercard | Accuracky of the flashcard | 0.33 | 0.00 | 1.00
usercard_delta | Time (hours) since the previous study of this card by this user. | 194.85 | 0.00 | 6789.00
usercard_delta_previous | The previous delta. Zero if first or second study. | 2.92e+05 | 0.00 | 1.52e+07
usercard_previous_response | The result (correct/incorrect) of the previous study | 0.37 | 0.00 | 1.00
elapsed_milliseconds | Time user spent thinking about the answer before submitting | 10295.47 | 0.00 | 60000.00
correct_on_first_try | Whether the user answers the card correctly on the very first study. | 0.26 | 0.00 | 1.00
response | Correct / Incorrect | 0.71 | 0.00 | 1.00
Table 7: Quantitative value columns in our released dataset, along with
descriptions, min, max, and mean values.

Figure 6: Procedures and instructions shown to users.

Figure 7: Test Mode popup instructions shown to users just before completing a
test mode study.

Figure 8: Confidentiality details shown to users.


#  On the Density of Codes over Finite Chain Rings

Anna-Lena Horlemann  University of St.Gallen, Switzerland  Violetta Weger
Technical University of Munich, Germany  Nadja Willenborg  University of
St.Gallen, Switzerland

###### Abstract

We determine the asymptotic proportion of free modules over finite chain rings
with good distance properties and treat the asymptotics in the code length $n$
and the residue field size $q$ separately. We then specialize and apply our
technique to rank metric codes and to Hamming metric codes.

##  1 Introduction

The study of the asymptotic performance of error-correcting codes is a
classical topic in coding theory, going back to the work by Shannon, where
random codes are used to get arbitrarily close to the capacity of a given
discrete memoryless channel [11]. It is well known that Hamming-metric codes
over finite fields attaining the Singleton bound, namely Maximum Distance
Separable (MDS) codes, are dense if the field size tends to infinity and,
assuming the validity of the MDS conjecture, that they are sparse for the
length tending to infinity. For rank metric codes, we call codes that attain
the Singleton bound Maximum Rank Distance (MRD) codes. It makes a great
difference whether we have $\mathbb{F}_{q}$-linear codes, or
$\mathbb{F}_{q^{m}}$\- linear codes. For the former, we have that MRD codes
are neither dense nor sparse as $q$ tends to infinity, while for the latter
they are dense [7, 8, 6]. Recently, also the Lee metric was investigated in
[1, 10], and Maximum Lee Distance (MLD) codes are sparse, whether we let $n$
or $q$ grow to infinity. In this paper we consider such questions in the
context of linear codes over finite chain rings, i.e., rings whose ideals are
generated by one element and are linearly ordered by inclusion. Research on
codes over rings has been started a while ago, see e.g. [2, 9]. Recently,
there has been increasing interest in rank-metric codes over finite rings, see
for example the literature on nested-lattice based network coding [12, 13],
which shows that by using network coding over finite rings one may develop
more efficient physical layer network coding schemes.

##  2 Preliminaries

Throughout this paper we denote by $Q$ the set of prime powers, by
$\pazocal{R}$ a _finite chain ring_ and the generator of its maximal ideal
with nilpotency index $s$ is denoted by $\gamma$. Assume that for the residue
field we have $\pazocal{R}/\langle\gamma\rangle\cong\mathbb{F}_{q}$, i.e.,
$|\pazocal{R}|=q^{s}$, the projection
$\pazocal{R}\rightarrow\pazocal{R}/\langle\gamma\rangle$ is denoted by $\Psi$
and can be naturally extended to polynomials over $\pazocal{R}$.

Let $h\in\pazocal{R}[X]$ be a polynomial of degree $m$ such that the leading
coefficient of $h$ is a unit and $\Psi(h)$ is irreducible in $\mathbb{F}_{q}$,
then $S=\pazocal{R}[X]/\langle h\rangle$ is a _free local degree- $m$ Galois
extension_ of $\pazocal{R}$ with maximal ideal $\gamma S$ and
$S/\langle\gamma\rangle\cong\mathbb{F}_{q^{m}}$. Since $\pazocal{R}$ is a
finite chain ring, $S$ is also a finite chain ring. In particular, it is a
free $\pazocal{R}$-module of rank $m$ and hence letting $N=nm$, the $S$-module
$S^{n}$ is isomorphic to $\pazocal{R}^{N}$. For every divisor $\ell$ of $m$,
we have a unique subring $\bar{S}\subseteq S$ which is a free local Galois
extension of degree $\ell$ of $\pazocal{R}$. For more details, we refer to
[5].

We consider _codes_ as subsets of the metric space $(S^{n},D)$, where $D$ is a
_translation-invariant distance function_ $D:S^{n}\times
S^{n}\rightarrow\mathbb{R}_{\geq 0}$ which is non-increasing under scalar
multiplication. (This property is required for the technique that we use to
count the number of codes, and unfortunately excludes some metrics, such as
the Lee metric). The _minimum distance_ of a code $\mathscr{C}\subseteq S^{n}$
with respect to the distance $D$ is defined as

$\displaystyle D(\mathscr{C}):=\min\\{D(x,y):x,y\in\mathscr{C},\,x\neq y\\}.$

Similarly to finite fields, we can study codes that are linear w.r.t. the
subring $\bar{S}\subseteq S$. These codes are then finitely generated
$\bar{S}$-submodules of $S^{n}$. The smallest number of elements in
$\mathscr{C}$ which generate $\mathscr{C}$ as an $\bar{S}$-module is denoted
by $\mu_{\bar{S}}(\mathscr{C})$ and called the _rank_ of $\mathscr{C}$. If
$\mathscr{C}=\\{0\\}$, then we set $\mu_{\bar{S}}(\mathscr{C})=0$. If
$\mathscr{C}$ is a finitely generated free $\bar{S}$-module and
$\\{e_{1},\dots,e_{k}\\}$ is a free basis of $\mathscr{C}$, then
$\mu_{\bar{S}}(\mathscr{C})=k$ and any generating set of $\mathscr{C}$
consisting of $k$ elements is a free basis of $\mathscr{C}$ over $\bar{S}$.

From now on, we let $S$ be a free local Galois extension of $\pazocal{R}$ with
fixed degree $m$ such that $S^{n}\cong\pazocal{R}^{N}$ and we denote by
$\bar{S}$ its unique subring of extension degree $\ell$. Moreover a code
$\mathscr{C}$ is always considered to be a free $\bar{S}$-module of $S^{n}$.
We restrict ourselves to this case, due to the density results from [1] for
modules over finite chain rings, which state that the probability of picking
$k$ generators $e_{1},\dots,e_{k}\in S^{n}$, all having at least one unit
entry, approaches $1$. This property is independent of the underlying
linearity of the code, but only determines the freeness of the code and hence
we can apply it to our context. From [9, 1] it is known that the number of
free $\bar{S}$-modules of $S^{n}$ having rank $k$ is

$N_{N/\ell,q^{\ell}}^{k}:=q^{(N-k\ell)k(s-1)}\genfrac{[}{]}{0.0pt}{0}{N/\ell}{k}_{q^{\ell}},$
(2.1)

where $q,\ell,s,N=mn$ are as above. Note that (2.1) can define a sequence with
respect to any of its parameters. We will often use this, without explicitly
defining the sequence. We denote by

$\delta_{q}^{D}(N,k,\ell,d):=\frac{|\\{\mathscr{C}\subseteq\pazocal{R}^{N}:\mu_{\bar{S}}(\mathscr{C})=k,\,D(\mathscr{C})\geq
d\\}|}{N_{N/\ell,q^{\ell}}^{k}}$

the _density of $\bar{S}$-linear codes_ in $\pazocal{R}^{N}$ having rank $k$
over $\bar{S}$ and minimum distance at least $d$. In the following, $d$ will
always be a finite positive integer, not exceeding the maximal possible
distance with respect to $D$.

To give an upper and lower bound on the density $\delta_{q}^{D}(N,k,\ell,d)$
we use counting arguments on the number of isolated vertices in _bipartite
graphs_ that are regular with respect to certain maps defined on their left-
vertices. This approach was first proposed in [8] and applied to different
metrics and various types of linearity in [4].

We recall the concept of an _association_ on a finite non-empty set
$\mathscr{V}$ of magnitude $r\geq 0$ (see [8]) which is a function
$\alpha:\mathscr{V}\times\mathscr{V}\to\\{0,...,r\\}$ satisfying the
following:

  * (i)

$\alpha(V,V)=r$ for all $V\in\mathscr{V}$;

  * (ii)

$\alpha(V,V^{\prime})=\alpha(V^{\prime},V)$ for all
$V,V^{\prime}\in\mathscr{V}$.

Given a finite bipartite graph
$\mathscr{B}=(\mathscr{V},\mathscr{W},\mathscr{E})$ and an association
$\alpha$ on $\mathscr{V}$ of magnitude $r$, we call $\mathscr{B}$ _$\alpha$
-regular_ if for all $(V,V^{\prime})\in\mathscr{V}\times\mathscr{V}$ the
number of vertices $W\in\mathscr{W}$ with $(V,W)\in\mathscr{E}$ and
$(V^{\prime},W)\in\mathscr{E}$ only depends on $\alpha(V,V^{\prime})$. We then
denote this number by $\mathscr{W}_{\ell}(\alpha)$, where
$\ell=\alpha(V,V^{\prime})\in\\{0,\dots,r\\}$.

######  Proposition 2.1.

[8, Lemma 3.2 & Lemma 3.5]
Let $\mathscr{B}=(\mathscr{V},\mathscr{W},\mathscr{E})$ be a bipartite
$\alpha$-regular graph, where $\alpha$ is an association on $\mathscr{V}$ of
magnitude $r$. Let $\mathscr{F}\subseteq\mathscr{W}$ be the collection of non-
isolated vertices of $\mathscr{W}$. If $\mathscr{W}_{r}(\alpha)>0$, then

  1. (i)

$|\mathscr{F}|\leq|\mathscr{V}|\,\mathscr{W}_{r}(\alpha).$

  2. (ii)

$|\mathscr{F}|\geq\frac{\mathscr{W}_{r}(\alpha)^{2}\,|\mathscr{V}|^{2}}{\sum_{\ell=0}^{r}\mathscr{W}_{\ell}(\alpha)\,|\alpha^{-1}(\ell)|}.$

We often consider the set $S_{q(\gamma)}^{n}:=S^{n}\setminus(\gamma S)^{n}$,
where the lower index indicates the dependence given through
$S/\langle\gamma\rangle\cong\mathbb{F}_{q^{m}}$, equivalently
$\pazocal{R}/\langle\gamma\rangle\cong\mathbb{F}_{q}$. We denote the _open
ball_ in $S^{n}$ of radius $r$ centered at $0$ by

$\textbf{B}_{q}^{D}(S^{n},r):=\\{x\in S^{n}:D(x,0)<r\\}$

and the open ball of radius $r$ centered at $0$, containing only elements from
$S_{q(\gamma)}^{n}$ by

$\textbf{B}_{q}^{D}(S_{q(\gamma)}^{n},r):=\textbf{B}_{q}^{D}(S^{n},r)\setminus\textbf{B}_{q}^{D}((S/\langle\gamma^{s-1}\rangle)^{n},r),$

where $\textbf{B}_{q}^{D}((S/\langle\gamma^{s-1}\rangle)^{n},r)$ describes the
open ball of radius $r$ over the chain ring $S/\langle\gamma^{s-1}\rangle$,
centered at $0$. Note that $0\notin\textbf{B}_{q}^{D}(S_{q(\gamma)}^{n},r)$.
Since we consider translation-invariant distances the size of any ball in
$S^{n}$, or in any of its subrings, does not depend on its center. Hence, we
do not specify the centers and denote the corresponding _volumes_ of the balls
by
$\textbf{v}_{q}^{D}(S^{n},r),\textbf{v}_{q}^{D}(S/\langle\gamma^{s-1}\rangle^{n},r)$,
respectively $\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},r)$.

##  3 Bounding the Density

First we use Proposition 2.1 to give an upper and a lower bound on the number
of codes in the metric space $(S^{n},D)$ that have minimum distance bounded
from above by some positive integer $d$. In contrast to previous literature
[8], [4] we extend the bipartite graph model by considering free modules
instead of vector spaces as vertices of the graph. A free module of rank $1$
is generated by an element from the set $S_{q(\gamma)}^{n}$. These modules
will represent the left-sided vertices in our bipartite graph, which will
therefore fulfill some important regularity properties.

######  Theorem 3.1.

Let $1\leq k\leq N/\ell$, $1\leq d<\infty$ and let

$\displaystyle\mathscr{F}:=\\{\mathscr{C}\subseteq\pazocal{R}^{N}:D(\mathscr{C})\leq
d-1,\,\mu_{\bar{S}}(\mathscr{C})=k\\}.$

We have

$\displaystyle|\mathscr{F}|$
$\displaystyle\leq\frac{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)N_{N/\ell-1,q^{\ell}}^{k-1}}{q^{\ell(s-1)}(q^{\ell}-1)},$
$\displaystyle|\mathscr{F}|$
$\displaystyle\geq\tfrac{\left(\frac{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)}{q^{\ell(s-1)}(q^{\ell}-1)}\right)(N_{N/\ell-1,q^{\ell}}^{k-1})^{2}}{N_{N/\ell-1,q^{\ell}}^{k-1}+\left(\frac{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)}{q^{\ell(s-1)}(q^{\ell}-1)}-1\right)N_{N/\ell-2,q^{\ell}}^{k-2}}.$

###### Proof.

Consider the bipartite graph
$\mathscr{B}=(\mathscr{V},\mathscr{W},\mathscr{E}),$ where $\mathscr{V}$ is
the set of modules generated by one element from
$\textbf{B}_{q}^{D}(S_{q(\gamma)}^{n},d)$, $\mathscr{W}$ is the collection of
free codes in $\pazocal{R}^{N}$ with $\mu_{\bar{S}}(\mathscr{C})=k$ and
$(V,\mathscr{C})\in\mathscr{E}$ if and only if $V\subseteq\mathscr{C}$. Every
vertex contains exactly $q^{\ell(s-1)}(q^{\ell}-1)$ elements from
$\bar{S}_{\gamma}^{n}$. Hence we have

$\displaystyle|\mathscr{V}|=\frac{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)}{q^{\ell(s-1)}(q^{\ell}-1)},\quad|\mathscr{W}|=N_{N/\ell,q^{\ell}}^{k}.$

Due to the assumption, that $D$ is non-increasing under scalar multiplication,
every $x\in\textbf{B}_{q}^{D}(\pazocal{R}^{N},d)$ belongs to a vertex
$V\in\mathscr{V}$ and the set of non-isolated vertices in $\mathscr{W}$ is
exactly $\mathscr{F}$.

We define the association

$\alpha:\mathscr{V}\times\mathscr{V}\to\\{0,1\\},\quad(V,V^{\prime})\mapsto
2-\mu_{\bar{S}}(\langle V,V^{\prime}\rangle),$

which gives $|\alpha^{-1}(0)|=|\mathscr{V}|(|\mathscr{V}|-1)$ and
$|\alpha^{-1}(1)|=|\mathscr{V}|$. It is also easy to see that $\mathscr{B}$ is
$\alpha$-regular. Furthermore, we have

$\displaystyle\mathscr{W}_{0}(\alpha)=N_{N/\ell-2,q^{\ell}}^{k-2},\;\mathscr{W}_{1}(\alpha)=N_{N/\ell-1,q^{\ell}}^{k-1},$

which, combined with Proposition 2.1, directly implies the two bounds given in
the theorem. ∎

The above directly imply the following bounds on the density of
$\bar{S}$-linear codes with minimum distance bounded from below.

######  Corollary 3.2.

Let $1\leq k\leq N/\ell$ and $1\leq d<\infty$ be integers. We have

$\displaystyle\delta_{q}^{D}(N,k,\ell,d)$ $\displaystyle\geq
1-\frac{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)N_{N/\ell-1,q^{\ell}}^{k-1}}{(q^{\ell(s-1)}(q^{\ell}-1))N_{N/\ell,q^{\ell}}^{k}},$
(3.1) $\displaystyle\delta_{q}^{D}(N,k,\ell,d)$ $\displaystyle\leq
1-\frac{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)N_{N/\ell-1,q^{\ell}}^{k-1}}{\bar{\Theta}(q^{\ell(s-1)}(q^{\ell}-1))N_{N/\ell,q^{\ell}}^{k}},$
(3.2)

where

$\bar{\Theta}=1+(N_{N/\ell-1,q^{\ell}}^{k-1})^{-1}\left(\displaystyle\tfrac{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)}{q^{\ell(s-1)}(q^{\ell}-1)}-1\right)N_{N/\ell-2,q^{\ell}}^{k-2}.$

##  4 The asymptotics of $\pazocal{R}$-linear codes

In this section we present some general asymptotic results on the density
function of codes in $\pazocal{R}^{N}$ endowed with a translation-invariant
metric $D$.

The asymptotic estimates of the $q$-binomial coefficient from [4] extend to
the following equivalences.

######  Lemma 4.1.

Let $n\geq k\geq 0$ be integers. Then

  1. (i)

$N_{n,q}^{k}\sim q^{sk(n-k)}$ as $q\to\infty$,

  2. (ii)

$N_{n,q}^{k}\sim q^{sk(n-k)}\prod_{i=1}^{k}\frac{q^{i}}{q^{i}-1}$ as
$n\to\infty$.

######  Theorem 4.2.

Let $1\leq s,1\leq k\leq N/\ell$ and $2\leq d\leq n$ be integers. Further
consider the sequence $(S_{q}^{n})_{q\in Q}$, where
$S_{q}^{n}:=S_{q(\gamma)}^{n}$. Then

$\displaystyle\max\left\\{\liminf_{q\to\infty}\left(1-\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s(N-k\ell+\ell)}}\right),0\right\\}\leq\liminf_{q\to\infty}\delta_{q}^{D}(N,k,\ell,d).$

Moreover, if $\textbf{v}_{q}^{D}(S_{q}^{n},d)\in\Omega(q^{s(N-k\ell+\ell)})$
as $q\to\infty$, then

$\displaystyle\limsup_{q\to\infty}\delta_{q}^{D}(N,k,\ell,d)\leq\limsup_{q\to\infty}\left(\tfrac{1}{1+\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s(N-k\ell+\ell)}}}\right).$
(4.1)

In particular,

$\displaystyle\lim_{q\to\infty}\delta_{q}^{D}(N,k,\ell,d)=\begin{cases}1&\textnormal{if
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in o(q^{s(N-k\ell+\ell)})$,}\\\
0&\textnormal{if
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in\omega(q^{s(N-k\ell+\ell)})$.}\end{cases}$

###### Proof.

From Lemma (i) we obtain

$\frac{\textbf{v}_{q}^{D}(S_{q}^{n},d)N_{N/\ell-1,q^{\ell}}^{k-1}}{q^{\ell(s-1)}(q^{\ell}-1)N_{N/\ell,q^{\ell}}^{k}}\sim\frac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s(N-k\ell+\ell)}}\quad\textnormal{as}\quad
q\to\infty.$

Together with Equation (3.1) and the fact that $\delta_{q}^{D}(n,k,d)\geq 0$
the lower bound can be derived. Moreover, we have

$\bar{\Theta}\sim 1+\frac{(\textbf{v}_{q}^{D}(S_{q}^{n},d)-q^{\ell
s})}{q^{s(N-k\ell+\ell)}}\quad\textnormal{as}\quad q\to\infty,$

which, considering the upper bound (3.2), gives

$\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)N_{N/\ell-1,q^{\ell}}^{k-1}}{\bar{\Theta}(q^{\ell(s-1)}(q^{\ell}-1))N_{N/\ell,q^{\ell}}^{k}}\sim\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s(N-k\ell+\ell)}+\textbf{v}_{q}^{D}(S_{q}^{n},d)-q^{\ell
s}}$

as $q\to\infty$. Since
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in\Omega(q^{s(N-k\ell+\ell)})$ as
$q\to\infty$, taking the limit in the bound (3.2) yields the upper bound
(4.1). ∎

Following the same arguments as in the proof of Theorem 4.2 we obtain
analogous results for $n\to\infty$:

######  Theorem 4.3.

Let $q\in Q$ and $1\leq s,2\leq d\leq n$ be integers. Further consider the
sequence $(S_{q}^{n})_{n\geq 1}$, where $S_{q}^{n}:=S_{q(\gamma)}^{n}$ and let
$(k(n))_{n\geq 1}$ be a sequence of integers where $1\leq k(n)<n$ for all
$n\geq 1$. Then

$\displaystyle\max\left\\{\liminf_{n\to\infty}\left(1-\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s(N-k(n)\ell+\ell)}}\right),0\right\\}\leq\liminf_{n\to\infty}\delta_{q}^{D}(N,k(n),\ell,d).$

Moreover, if
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in\Omega(q^{s(N-k(n)\ell+\ell)})$ as
$n\to\infty$ then

$\displaystyle\limsup_{n\to\infty}\delta_{q}^{D}(N,k(n),\ell,d)\leq\limsup_{n\to\infty}\left(\tfrac{1}{1+\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s(N-k(n)\ell+\ell)}}}\right).$

In particular,

$\displaystyle\lim_{n\to\infty}\delta_{q}^{D}(N,k(n),\ell,d)=\begin{cases}1&\textnormal{if
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in o(q^{s(N-k(n)\ell+\ell)})$,}\\\
0&\textnormal{if
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in\omega(q^{s(N-k(n)\ell+\ell)})$.}\end{cases}$

In particular, we can fix a rate $R\in[0,1]$ such that $k(n)=RN/\ell$. Using
the same setup, we obtain:

######  Corollary 4.4.

Let $N=nm,R\in[0,1],S_{q}^{n}:=S_{q(\gamma)}^{n}$. Then

$\displaystyle\lim_{n\to\infty}\delta_{q}^{D}(n,RN/\ell,\ell,d)=$
$\displaystyle\begin{cases}1&\textnormal{if
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in o(q^{s((1-R)N+\ell)})$,}\\\
0&\textnormal{if
$\textbf{v}_{q}^{D}(S_{q}^{n},d)\in\omega(q^{s((1-R)N+\ell)})$.}\end{cases}$

The _sphere covering_ or _Gilbert-Varshamov (GV) bound_ states that there
exist codes with minimum distance $d$ of cardinality at least
$\frac{|S^{n}|}{\textbf{v}_{q}^{D}(S^{n},d)}$. Note that
$|S^{n}|\sim|S_{q(\gamma)}^{n}|$ both, as $n\to\infty$ and as $q\to\infty$.
Hence, if we have that

$\textbf{v}_{q}^{D}((S/\langle\gamma^{s-1}\rangle)^{n},d)\in
o(\textbf{v}_{q}^{D}(S^{n},d)),$

as $n\to\infty$ or as $q\to\infty$, we can asymptotically approximate this
bound by

$\displaystyle|\mathscr{C}|\geq\frac{|S^{n}|}{\textbf{v}_{q}^{D}(S^{n},d)}\sim\frac{|S_{q(\gamma)}^{n}|}{\textbf{v}_{q}^{D}(S_{q(\gamma)}^{n},d)},$
(4.2)

as either $q$ or $n$ tends to infinity, for some $\mathscr{C}\subseteq S^{n}$
of minimum distance $d$. For linear codes of rate $R$ we can reformulate (4.2)
to

$R\geq 1-\frac{1}{N}\log_{q^{s}}(\textbf{v}_{q}^{D}(S^{n},d))$
$\iff\log_{q^{s}}(\textbf{v}_{q}^{D}(S^{n},d))\geq N(1-R).$

In the following we study the asymptotic behaviour of codes achieving the
bound (4.2) with respect to $q$ or $n$.

######  Theorem 4.5.

Let $2\leq d\leq n$ be integers and $(S^{n},D)$ be a metric space, where $D$
is a translation-invariant metric on $S^{n}$, non-increasing under scalar
multiplication. Further, consider the sequence $(S_{q}^{n})_{q\in Q}$, where
$S_{q}^{n}:=S_{q(\gamma)}^{n}$. Let $\mathscr{C}\subseteq S^{n}$ be a
$\bar{S}$-module of rate
$R=1-\frac{1}{N}\log_{q^{s}}(\textbf{v}_{q}^{D}(S^{n},d))$, chosen uniformly
at random. If $\textbf{v}_{q}^{D}((S/\langle\gamma^{s-1}\rangle)^{n},d)\in
o(\textbf{v}_{q}^{D}(S^{n},d)),$ as $q\to\infty$, then the probability that
$\mathscr{C}$ has minimum distance at least $d$ approaches $1$, for
$q\rightarrow\infty$.

###### Proof.

The statement follows from Theorem 4.2 and

$\displaystyle\lim_{q\to\infty}\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s((1-R)N+\ell)}}$
$\displaystyle=\lim_{q\to\infty}q^{s(\log_{q^{s}}(\textbf{v}_{q}^{D}(S_{q}^{n},d))-\frac{s((1-R)N+\ell)}{s})}$
$\displaystyle=\lim_{q\to\infty}q^{s((1-R)N-(1-R)N-\ell)}=0.$

∎

If we consider $n$ going to infinity, then the probability that a
$\bar{S}$-module, chosen uniformly at random attains the GV bound is upper
bounded by $q^{s\ell}/(q^{s\ell}+1)$ and lower bounded by
$(q^{s\ell}-1)/q^{s\ell}.$ However, if we add an $\varepsilon$-environment, we
obtain:

######  Theorem 4.6.

In the setup of Theorem 4.5 let $\mathscr{C}\subseteq S^{n}$ be a
$\bar{S}$-module of rate
$R=1-\frac{1}{N}\log_{q^{s}}(\textbf{v}_{q}^{D}(S^{n},d))-\varepsilon$, chosen
uniformly at random. If
$\textbf{v}_{q}^{D}((S/\langle\gamma^{s-1}\rangle)^{n},d)\in
o(\textbf{v}_{q}^{D}(S^{n},d)),$ as $n\to\infty$, then the probability that
$\mathscr{C}$ has minimum distance at least $d$ approaches $1$, for
$n\rightarrow\infty$.

###### Proof.

The statement follows from Corollary 4.4 and

$\displaystyle\lim_{n\to\infty}\tfrac{\textbf{v}_{q}^{D}(S_{q}^{n},d)}{q^{s((1-R)N+\ell)}}=\lim_{n\to\infty}q^{s((1-R)N-(1-R)N-\varepsilon
N-\ell)}=0.$

∎

Note that the rank metric fulfills the requirement
$\textbf{v}_{q}^{D}((S/\langle\gamma^{s-1}\rangle)^{n},d)\in
o(\textbf{v}_{q}^{D}(S^{n},d))$ for $q,n\rightarrow\infty$, as does the
Hamming metric for $q\rightarrow\infty$. (For the definition of these metrics
see the following two sections.) Our results hence extend the one on the
asymptotic behaviour w.r.t. the GV bound from [1], where the analog was shown
for metrics stemming from additive weights (which do not include the rank
metric).

##  5 $\pazocal{R}$-linear Hamming metric codes

The _Hamming weight_ of $x\in S^{n}$ is given by
$\omega^{H}(x):=|\\{i\in[n]:x_{i}\neq 0\\}|$ and then the _Hamming distance_
for $x,y\in S^{n}$ is defined as $D^{H}(x,y):=\omega^{H}(x-y)$. Throughout
this section, we are working in the metric space $(S^{n},D^{H})$. Let
$\mathscr{C}$ be an $\bar{S}$-module of length $n$ and
$\mu_{\bar{S}}(\mathscr{C})=k$ then the following Singleton-like bound is
known for finite chain rings, see [2]:
$k\leq\frac{m}{\ell}(n-D^{H}(\mathscr{C})+1).$ Codes achieving this bound are
called _Maximum Distance with respect to Rank (MDR) codes_ , to differentiate
them from the usual MDS codes [2].

In order to study the asymptotic density of Hamming-metric codes, we need the
volume of the Hamming-metric ball in $S_{q(\gamma)}^{n}$ of radius $0\leq
r<\infty$ and its asymptotic estimates. Note that $|S|=q^{ms}$ and $S$ has
$q^{ms}-q^{m(s-1)}$ unit elements. Next we count the number of vectors up to
Hamming weight $r-1$ having at least one unit, as

$\textbf{v}_{q}^{H}(S_{q(\gamma)}^{n},r)=\sum_{i=0}^{r-1}\binom{n}{i}iq^{m(s-1)}(q^{m}-1)(q^{ms}-1)^{i-1}.$

The estimates

$\textbf{v}_{q}^{H}(S_{q}^{n},r)\sim\binom{n}{r-1}(r-1)q^{ms(r-1)}$

as $q\to\infty$ and

$\textbf{v}_{q}^{H}(S_{q}^{n},r)\sim\binom{n}{r-1}(r-1)(q^{ms}-1)(q^{ms}-q^{m(s-1)})^{r-2}$

as $n\to\infty$, easily follow. We can now derive asymptotic results for the
density of MDR codes.

######  Theorem 5.1.

Let $d\geq 2$ be an integer.

  * (i)

Let $n\geq 2$ be an integer. Then we have

$\lim_{q\to\infty}\delta_{q}^{H}(N,m/\ell(n-d+1),\ell,d)=1.$

  * (ii)

Let $q\in Q$, then

$\lim_{n\to\infty}\delta_{q}^{H}(N,m/\ell(n-d+1),\ell,d)=0.$

###### Proof.

One easily gets $\textbf{v}_{q}^{H}(S_{q}^{n},d)\in o(q^{sm(d-1)+s\ell})$ as
$q\to\infty$, which together with Theorem 4.2 gives the first statement of the
theorem. The second statement follows from
$\textbf{v}_{q}^{H}(S_{q}^{n},d)\in\omega(q^{sm(d-1)+s\ell})$ as $n\to\infty$
and Theorem 4.3. ∎

##  6 $\pazocal{R}$-linear rank metric codes

We adopt the vector representation of rank metric codes as introduced in [3].
A rank metric code is a subset of the $S$-module $S^{n}$ endowed with the
_rank distance_ , i.e., $D^{\textnormal{rk}}(x,y):=\textnormal{rk}(x-y),$
where $\textnormal{rk}(x):=\mu_{\pazocal{R}}(\langle
x_{1},\dots,x_{n}\rangle)$ denotes the _rank_ of $x=(x_{1},\dots,x_{n})\in
S^{n}$.

Let $\mathscr{C}\subseteq S^{n}$ be a code of minimum rank distance $d$, then
the following Singleton bound is given in [3]:

$|\mathscr{C}|\leq q^{s\cdot\max\\{m,n\\}(\min\\{m,n\\}-d+1)}.$ (6.1)

A rank metric code meeting the bound with equality is called an _MRDR (Maximum
Rank Distance with respect to Rank) code_.

Let $\mathscr{C}\subseteq S^{n}$ be a free $\bar{S}$-module such that
$\mu_{\bar{S}}(\mathscr{C})=k$ and $D^{\textnormal{rk}}(\mathscr{C})=d$, then
the Singleton bound (6.1) can be restated as

$\displaystyle\ell k\leq\max\\{m,n\\}(\min\\{m,n\\}-d+1).$ (6.2)

To analyze the asymptotic density of codes with largest possible rank over
$\bar{S}$, we first derive the volume of the ball in the rank metric and its
asymptotic estimates, similarly to [1, Proposition 15].

######  Proposition 6.1.

Let $0\leq r-1\leq\min\\{m,n\\}$, then

$\textbf{v}_{q}^{\textnormal{rk}}(S_{q(\gamma)}^{n},r):=\sum_{i=0}^{r-1}N_{n,q}^{i}q^{(s-1)mi}\prod_{j=0}^{i-1}(q^{m}-q^{j}).$

###### Proof.

For a fixed free module $U\subseteq\pazocal{R}^{n}$ with
$\mu_{\pazocal{R}}(U)=k$, the number of matrices $A\in\pazocal{R}^{n\times m}$
with $\textnormal{colsp}(A)=U$ equals the number of matrices
$B\in\pazocal{R}^{k\times m}$ of rank $k$, where by abuse of notation, a
matrix that generates a free module of rank $k$ is called a matrix of rank
$k$. The number of matrices of rank $k$ is given by

$q^{(s-1)mk}\prod_{j=0}^{k-1}(q^{m}-q^{j}),$

i.e., the number of ways to draw $k$ vectors from $\pazocal{R}_{\gamma}^{m}$,
such that they do not lie in the span of the previously picked vectors. The
number of free modules in $\pazocal{R}^{n}$ having rank $k$ is $N_{n,q}^{k}$.
∎

Using the estimates from Lemma 4.1 we obtain for $0\leq r-1\leq\min\\{m,n\\}$
the asymptotic estimate

$\textbf{v}_{q}^{\textnormal{rk}}(S_{q}^{n},r)\sim q^{s(r-1)(m+n-(r-1))},$

as $q\to\infty$ and for $0\leq r-1\leq m$ the estimate

$\displaystyle\textbf{v}_{q}^{\textnormal{rk}}(S_{q}^{n},r)\sim\genfrac{[}{]}{0.0pt}{0}{m}{r-1}_{q}q^{(r-1)((s-1)(m+n-(r-1))+n)},$
(6.3)

as $n\to\infty$.

If $n>m$, codes attaining the largest possible rank over $\bar{S}$, according
to (6.2) are not necessarily MRDR. For this reason we state the results for
$n>m$ separately. The proof is an application of 4.2, for details we refer to
[4, Theorem 5.7].

######  Theorem 6.2.

Let $m,\ell\geq 1,2\leq d\leq n$ be integers and let
$k=\lfloor\max\\{m,n\\}(\min\\{m,n\\}-d+1)/\ell\rfloor$. Define
$\theta:=(d-1)(\min\\{m,n\\}-d+1)$.

  * (i)

If $m\geq n$ then we have

$\displaystyle\lim_{q\to\infty}\delta_{q}^{\textnormal{rk}}(N,k,\ell,d)=\begin{cases}1&\textnormal{if
$\ell>\theta$,}\\\ 0&\textnormal{if $\ell<\theta$}\end{cases}$

and if $\ell=\theta$, then
$\lim_{q\to\infty}\delta_{q}^{\textnormal{rk}}(N,k,\ell,d)\leq 1/2.$

  * (ii)

If $n>m$ then we have

$\displaystyle\lim_{q\to\infty}\delta_{q}^{\textnormal{rk}}(N,k,\ell,d)=\begin{cases}1&\textnormal{if
$\theta-r<\ell$,}\\\ 0&\textnormal{if $\theta-r>\ell$,}\end{cases}$

where $r:=\ell(\lceil n(d-1)/\ell\rceil-n(d-1)/\ell)$. Moreover, if
$\ell=\theta-r$ then
$\lim_{q\to\infty}\delta_{q}^{\textnormal{rk}}(N,k,\ell,d)\leq 1/2$.

If we let the length $n$ go to infinity, we are again in the setting where
codes of the largest possible dimension are not necessarily MRDR.

######  Theorem 6.3.

Let $q\in Q$, fix $2\leq d\leq m$ and let $k(n):=\lfloor n(m-d+1)/\ell\rfloor$
for all $n\geq 2$. Then

$\displaystyle\limsup_{n\to\infty}\delta_{q}^{\textnormal{rk}}(N,k,\ell,d)\leq\frac{1}{1+\genfrac{[}{]}{0.0pt}{0}{m}{d-1}_{q}\frac{q^{(d-1)((s-1)(m-(d-1))}}{q^{2s\ell}}}.$

###### Proof.

Applying Theorem 4.3 and the estimate (6.3) as $n\to\infty$ we obtain

$\displaystyle\lim_{n\to\infty}\frac{\textbf{v}_{q}^{\textnormal{rk}}(S_{q}^{n},d)q^{sk(n)\ell}}{q^{s(N+\ell)}}$
$\displaystyle=\lim_{n\to\infty}\genfrac{[}{]}{0.0pt}{0}{m}{d-1}_{q}\frac{q^{(d-1)(s(m-(d-1))}}{q^{s\ell(1+(\lceil
n(d-1)/\ell\rceil-n(d-1)/\ell))}}$
$\displaystyle\sim\genfrac{[}{]}{0.0pt}{0}{m}{d-1}_{q}\frac{q^{(d-1)((s-1)(m-(d-1))}}{q^{2s\ell}},$

where we used that $k(n)=\lfloor n(m-d+1)/\ell\rfloor=N/\ell-\lceil
n(d-1)/\ell\rceil$ and $0\leq(\lceil n(d-1)/\ell\rceil-n(d-1)/\ell)\leq 1$. ∎

##  7 Concluding Remarks

We showed that linear codes over a finite chain ring endowed with the rank or
the Hamming metric exhibit a similar asymptotic behaviour as in the finite
field case, if we let $q$ or $n$ go to infinity. Under the assumption that
$\textbf{v}_{q}^{D}((S/\langle\gamma^{s-1}\rangle)^{n},d)\in
o(\textbf{v}_{q}^{D}(S^{n},d)),$ codes attaining (an $\varepsilon$-environment
of) the Gilbert-Varshamov bound are asymptotically dense as $q\to\infty$
(respectively as $n\to\infty$). Over finite fields this requirement is always
fulfilled, as then the zero-vector is the only element containing only non-
units. Furthermore, we showed in which cases optimal codes in the Hamming or
the rank metric are dense or sparse.

We remark that, using the Chinese Remainder Theorem, one can extend this
procedure to codes over general finite principal ideal rings, to determine
their asymptotic behaviour.

## References

  * [1] E. Byrne, A.L. Horlemann, K. Khathuria and V. Weger, ”Density of free modules over finite chain rings.” Linear Algebra and its Applications 651 (2022): 1-25.
  * [2] S.T. Dougherty and K. Shiromoto, “MDR codes over $\mathbb{Z}_{k}$,” IEEE Transactions on Information Theory, 46(1):265-269,2000
  * [3] H.T. Kamche and C. Mouaha, “Rank metric codes over finite principal ideal rings and applications,” IEEE Transactions on Information Theory, 65.12 (2019): 7718-7735.
  * [4] A. Gruica, A.L. Horlemann, A. Ravagnani and N. Willenborg, “Densities of Codes of Various Linearity Degrees in Translation-Invariant Metric Spaces,” arXiv preprint arXiv:2208.10573, August 2022.
  * [5] B.R. MacDonald, ”Finite rings with identity.” Marcel Dekker Incorporated, 1974, vol. 28.
  * [6] A. Neri, A.L. Horlemann-Trautmann, T. Randrianarisoa and J. Rosenthal, “On the genericity of maximum rank distance and Gabidulin codes,” Designs, Codes and Cryptography 86.2 (2018): 341-363.
  * [7] J. Antrobus and H. Gluesing-Luerssen, ”Maximal Ferrers diagram codes: constructions and genericity considerations.” IEEE Transactions on Information Theory 65.10 (2019): 6204-6223.
  * [8] A. Gruica, and A. Ravagnani, ”Common complements of linear subspaces and the sparseness of MRD codes.” SIAM Journal on Applied Algebra and Geometry 6.2 (2022): 79-110.
  * [9] T. Honold and I. Landjev, ”Linear codes over finite chain rings”, The electronic journal of combinatorics, 7 (2000).
  * [10] E. Byrne and V. Weger, ”Bounds in the Lee Metric and Optimal Codes.” Finite Fields and Their Applications, 2022.
  * [11] C.E. Shannon, ”A mathematical theory of communication.” The Bell system technical journal 27.3 (1948): 379-423.
  * [12] C. Feng, D. Silva and F.R. Kschischang: ”An algebraic approach to physical-layer network coding.” IEEE Trans. Inf. Theory 59(11), 7576–7596 (2013).
  * [13] M.P. Wilson, K. Narayanan, H.D. Pfister and A. Sprintson: ”Joint physical layer coding and network coding for bidirectional relaying.” IEEE Trans. Inf. Theory 56(11), 5641–5654 (2010)