# Context-Aware Attentive Knowledge Tracing

Aritra Ghosh  University of Massachusetts AmherstAmherstMA
<EMAIL_ADDRESS>,  Neil Heffernan  Worcester Polytechnic
InstituteWorcesterMA<EMAIL_ADDRESS>and  Andrew S. Lan  University of
Massachusetts AmherstAmherstMA<EMAIL_ADDRESS>
(2020)

###### Abstract.

Knowledge tracing (KT) refers to the problem of predicting future learner
performance given their past performance in educational applications. Recent
developments in KT using flexible deep neural network-based models excel at
this task. However, these models often offer limited interpretability, thus
making them insufficient for personalized learning, which requires using
interpretable feedback and actionable recommendations to help learners achieve
better learning outcomes. In this paper, we propose attentive knowledge
tracing (AKT), which couples flexible attention-based neural network models
with a series of novel, interpretable model components inspired by cognitive
and psychometric models. AKT uses a novel monotonic attention mechanism that
relates a learner’s future responses to assessment questions to their past
responses; attention weights are computed using exponential decay and a
context-aware relative distance measure, in addition to the similarity between
questions. Moreover, we use the Rasch model to regularize the concept and
question embeddings; these embeddings are able to capture individual
differences among questions on the same concept without using an excessive
number of parameters. We conduct experiments on several real-world benchmark
datasets and show that AKT outperforms existing KT methods (by up to $6\%$ in
AUC in some cases) on predicting future learner responses. We also conduct
several case studies and show that AKT exhibits excellent interpretability and
thus has potential for automated feedback and personalization in real-world
educational settings.

††journalyear: 2020††copyright: acmcopyright††conference: Proceedings of the
26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining USB Stick;
August 23–27, 2020; Virtual Event, USA††booktitle: Proceedings of the 26th ACM
SIGKDD Conference on Knowledge Discovery and Data Mining USB Stick (KDD ’20),
August 23–27, 2020, Virtual Event, USA††price: 15.00††doi:
10.1145/3394486.3403282††isbn: 978-1-4503-7998-4/20/08

##  1\. Introduction

Recent advances in data analytics and intelligent tutoring systems (Woolf,
2010) have enabled the collection and analysis of large-scale learner data;
these advances hint at the potential of _personalized_ learning at large
scale, by automatically providing personalized feedback (Piech et al., 2015b)
and learning activity recommendations (Lan and Baraniuk, 2016) to each learner
by analyzing data from their learning history.

A key problem in learner data analysis is to predict future learner
performance (their responses to assessment questions), given their past
performance, which is referred to as the knowledge tracing (KT) problem
(Corbett and Anderson, 1994). Over the last 30 years, numerous methods for
solving the KT problem were developed based on two common assumptions: i) a
learner’s past performance can be summarized by a set of variables
representing their current latent _knowledge level_ on a set of
concepts/skills/knowledge components, and ii) a learner’s future performance
can be predicted using their current latent concept knowledge levels.
Concretely, let $t$ denote a set of discrete time indices, we have the
following generic model for a learner’s knowledge and performance

$\displaystyle r_{t}\sim f(h_{t}),\quad h_{t}\sim g(h_{t-1}),$

where $r_{t}\in\\{0,1\\}$ denotes the learner’s graded response to an
assessment question at time step $t$, which is usually binary-valued ($1$
corresponds to a correct response and $0$ corresponds to an incorrect one) and
is observed. The latent variable $h_{t}$ denotes the learner’s current
knowledge level and is not observed. $f(\cdot)$ and $g(\cdot)$ are functions
that characterize how learner knowledge dictate their responses and how it
evolves; they are sometimes referred to as the response model and the
knowledge evolution model, respectively.

Earlier developments in KT methods before 2010 can be divided into two
classes. The first class centered around the Bayesian knowledge tracing (BKT)
method (Pardos and Heffernan, 2010; Yudelson et al., 2013) where knowledge
($h_{t}$) is a binary-valued scalar that characterizes whether or not a
learner masters the (single) concept covered by a question. Since the response
($r_{t}$) is also binary-valued, the response and knowledge evolution models
are simply noisy binary channels, parameterized by the guessing, slipping,
learning, and forgetting probabilities. The second class centered around item
response theory (IRT) models (Lord, 1980) and use these models (especially
sigmoidal link functions) as the response model $f(\cdot)$; learner knowledge
level is then modeled as real-valued vectors ($\mathbf{h}_{t}$) for questions
that cover multiple concepts. Among these methods, the SPARFA-Trace method
(Lan et al., 2014) used a simple affine transformation model as the explicit
knowledge evolution model $g(\cdot)$. Other methods, e.g., additive factor
models (Cen et al., 2006), performance factor analysis (Pavlik Jr et al.,
2009), the difficulty, ability, and student history (DASH) model (Lindsey et
al., 2014), and a few recent methods including knowledge factorization
machines (Vie and Kashima, 2019) and an extension to the DASH model, the DAS3H
model (Choffin et al., 2019), used _hand-crafted features_ such as the number
of previous attempts, successes, and failures on each concept in their
knowledge evolution model. Methods in both classes rely on expert labels to
associate questions to concepts, resulting in excellent interpretability since
they can effectively estimate the knowledge level of each learner on expert-
defined concepts.

Recent developments in KT centered around using more sophisticated and
flexible models to fully exploit the information contained in large-scale
learner response datasets. The deep knowledge tracing (DKT) method (Piech et
al., 2015a) was the first method to explore the use of (possibly deep) neural
networks for KT by using long short-term memory (LSTM) networks (Hochreiter
and Schmidhuber, 1997) as the knowledge evolution model $g(\cdot)$. Since LSTM
units are nonlinear, complex functions, they are more flexible than affine
transformations and more capable of capturing nuances in real data.

The dynamic key-value memory networks (DKVMN) method extended DKT by using an
external memory matrix ($\mathbf{H}_{t}$) to characterize learner knowledge
(Zhang et al., 2017). The matrix is separated into two parts: a static, “key”
matrix that contains the fixed representation of each concept, and a dynamic,
“value” matrix that contains the evolving knowledge levels of each learner on
each concept. DKVMN also uses separate “read” and “write” processes on this
external matrix for the response and knowledge evolution models; these
processes make it even more flexible than DKT. DKT and KVMN reported state-of-
the-art performance in predicting future learner performance (Khajah et al.,
2016) and have been the benchmark for new KT methods.

The self-attentive knowledge tracing (SAKT) method (Pandey and Karypis, 2019)
is the first method to use attention mechanisms in the context of KT.
Attention mechanisms are more flexible than recurrent and memory-based neural
networks and have demonstrated superior performance in natural language
processing tasks. The basic setup of SAKT has many similarities to the
Transformer model (Vaswani et al., 2017), an effective model for many
sequence-to-sequence prediction tasks. However, we observe that SAKT does not
outperform DKT and DKVMN in our experiments; see Section 4 for details.
Possible reasons for this include i) unlike in language tasks where strong
long-distance dependencies between words are more common, the dependence of
future learner performance on the past is likely restricted to a much shorter
window, and ii) the sizes of learner response datasets are several magnitudes
lower than natural language datasets and are less likely to benefit from
highly flexible and large-scale attention models.

More importantly, no existing KT method truly excels at both future
performance prediction and interpretability. Early KT methods exhibit
excellent interpretability but do not provide state-of-the-art performance on
future learner performance prediction. Recent KT methods based on deep
learning excel at that but offer limited interpretability. Therefore, these KT
methods do not fully meet the needs of personalized learning, which requires
not only accurate performance prediction but also the ability to provide
automated, interpretable feedback and actionable recommendations to help
learners achieve better learning outcomes.

###  1.1. Contributions

For the task of predicting the learner’s response to the current question, we
propose the attentive knowledge tracing (AKT) method, which uses a series of
attention networks to draw connections between this question and every
question the learner has responded to in the past. We summarize our key
innovations below:

  1. (1)

Contrary to existing attention methods that use raw question and response
embeddings, we put raw embeddings into context and use _context-aware
representations_ of past questions and responses by taking a learner’s entire
practice history into account.

  2. (2)

Inspired by cognitive science findings on the mechanisms of forgetting, we
propose a novel _monotonic attention mechanism_ that uses an exponential decay
curve to down weight the importance of questions in the distant past. We also
develop a context-aware measure to characterize the time distance between
questions a learner has responded to in the past.

  3. (3)

Leveraging the Rasch model, a simple and interpretable IRT model, we use a
series of _Rasch model-based embeddings_ to capture individual differences
among questions without introducing an excessive amount of model parameters.

We conduct a series of experiments on several benchmark real-world educational
datasets comparing AKT to state-of-the-art KT methods. Our results show that
AKT (sometimes significantly) outperforms other KT methods in predicting
future learner performance. Further, we perform ablation studies on each of
the key AKT model components to demonstrate their value. We also perform
several case studies to show that AKT exhibits excellent interpretability and
has the potential for automated feedback and practice question recommendation,
both key requirements of personalized learning111Source code and datasets will
be available at https://github.com/arghosh/AKT.

##  2\. Knowledge Tracing Problem Setup

Each learner’s performance record consists of a sequence of questions and
responses at each discrete time step. For learner $i$ at time step $t$, we
denote the combination of the question that they answered, the concept this
question covers, and their graded response as a tuple,
$(q_{t}^{i},c_{t}^{i},r_{t}^{i})$, where $q_{t}^{i}\in\mathbb{N}^{+}$ is the
question index, $c_{t}^{i}\in\mathbb{N}^{+}$ is the concept index, and
$r_{t}^{i}\in\\{0,1\\}$ is the response. Under this notation,
$(q_{t}^{i},c_{t}^{i},1)$ means learner $i$ responded to question $q_{t}^{i}$
on concept $c_{t}^{i}$ correctly at time $t$. We note that this setup is
different from some prior works on deep knowledge tracing that often ignore
the question index and summarize learner performance as
$(c_{t}^{i},r_{t}^{i})$. This choice was made to avoid overparameterization;
see Section 3.3 for a detailed analysis. In the following discussions, we omit
the superscript $i$ as we discuss how to predict future performance for a
single learner. Given their past history up to time $t-1$ as
$\\{(q_{1},c_{1},r_{1}),\ldots,(q_{t-1},c_{t-1},r_{t-1})\\}$, our goal is to
predict their response $r_{t}$ to question $q_{t}$ on concept $c_{t}$ at the
current time step, $t$.

###  2.1. Question and Response Embeddings

Following previous work (Zhang et al., 2017), we use real-valued embedding
vectors $\mathbf{x}_{t}\in\mathbb{R}^{D}$ and
$\mathbf{y}_{t}\in\mathbb{R}^{D}$ to represent each question and each
question-response pair ($q_{t},r_{t}$), respectively. $\mathbf{x}_{t}$
characterizes information about questions, and $\mathbf{y}_{t}$ characterizes
the knowledge learners acquire by responding to questions, with two separate
embeddings for correct and incorrect responses, respectively. $D$ denotes the
dimension of these embeddings. Therefore, let $Q$ denote the number of
questions, there are a total of $Q$ question embedding vectors and $2Q$
question-response embedding vectors. In most real-world educational settings,
the question bank is considerably larger than the set of concepts and many
questions are assigned to very few learners. Therefore, the majority of
existing KT methods use concepts to index questions to avoid
overparameterization; all questions covering the same concept are treated as a
single question. In this case, $q_{t}=c_{t}$ and $Q=C$.

##  3\. The AKT Method

The AKT method consists of four components: two self-attentive encoders, one
for questions and one for knowledge acquisition, a single attention-based
knowledge retriever, and a feed-forward response prediction model; Figure 1
visualizes the AKT method and its connected components.

We use the two self-attentive encoders to learn context-aware representations
of the questions and responses. We refer to the first encoder as the _question
encoder_ , which produces modified, contextualized representations of each
question, given the sequence of questions the learner has previously practiced
on. Similarly, we refer to the second encoder as the _knowledge encoder_ ,
which produces modified, contextualized representations of the knowledge the
learner acquired while responding to past questions. Alternatively, we could
use raw embeddings of questions and responses similar to prior work. We found
that the context-aware representation performs better in most datasets. We
refer to the knowledge evolution model as the _knowledge retriever_ , which
retrieves knowledge acquired in the past that is relevant to the current
question using an attention mechanism. Finally, the response prediction model
predicts the learner’s response to the current question using the retrieved
knowledge. The AKT method is motivated by three intuitions rooted in cognitive
science and psychometrics; we will detail these intuitions in what follows.

Figure 1. Overview of the AKT method. We use the Rasch model-based embeddings
as raw embeddings for questions and responses. The question and knowledge
encoders compute the context-aware representations of questions and responses
pairs. The knowledge retriever uses these representations as input and
computes the knowledge state of the learner. For simplicity, we do not show
the monotonic attention mechanism in the encoders. We do not show sublayers
either.

###  3.1. Context-aware Representations and The Knowledge Retriever

As introduced above, we use two encoders in our model. The question encoder
takes raw question embeddings $\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{t}\\}$ as
input and outputs a sequence of context-aware question embeddings
$\\{\hat{\mathbf{x}}_{1},\ldots$, $\hat{\mathbf{x}}_{t}\\}$ using a monotonic
attention mechanism (detailed in the next subsection). The context-aware
embedding of each question depends on both itself and the past questions,
i.e., $\hat{\mathbf{x}}_{t}=f_{\mbox{enc}_{1}}$
$(\mathbf{x}_{1},\ldots,\mathbf{x}_{t})$. Similarly, the knowledge encoder
takes raw question-response embeddings
$\\{\mathbf{y}_{1},\ldots,\mathbf{y}_{t-1}\\}$ as input and outputs a sequence
of actual knowledge acquired
$\\{\hat{\mathbf{y}}_{1},\ldots,\hat{\mathbf{y}}_{t-1}\\}$ using the same
monotonic attention mechanism. The context-aware embedding of acquired
knowledge depend on the learner’s response to both the current question and
past questions, i.e.,
$\hat{\mathbf{y}}_{t-1}=f_{\mbox{enc}_{2}}(\mathbf{y}_{1},\ldots,\mathbf{y}_{t-1})$.

The choice of using context-aware embeddings rather than raw embeddings
reflects our first intuition: _the way a learner comprehends and learns while
responding to a question depends on the learner_. These modified
representations reflect each learner’s actual comprehension of the question
and the knowledge they actually acquire, given their personal response
history. This model choice is motivated by the intuition that for two learners
with different past response sequences, the way they understand the same
question and the knowledge they acquire from practicing on it can differ.

The knowledge retriever takes the context-aware question and question-response
pair embeddings $\hat{\mathbf{x}}_{1:t}$ and $\hat{\mathbf{y}}_{1:t-1}$ as
input and outputs a retrieved knowledge state $\mathbf{h}_{t}$ for the current
question. We note that in AKT, the learner’s current knowledge state is also
context-aware since it depends on the current question they are responding to;
this model choice is different from that in most existing methods, including
DKT. We also note that the knowledge retriever can only use information on the
past questions, the learner’s responses to them, and the representation of the
current question, but not the learner’s response to the current question,
i.e.,
$\mathbf{h}_{t}=f_{\mbox{kr}}(\hat{\mathbf{x}}_{1},\ldots,\hat{\mathbf{x}}_{t},\hat{\mathbf{y}}_{1},\ldots,\hat{\mathbf{y}}_{t-1})$.
The response prediction model uses the retrieved knowledge to predict the
current response.

###  3.2. The Monotonic Attention Mechanism

We use a modified, monotonic version of the scaled dot-product attention
mechanism for the encoders and the knowledge retriever. We start by briefly
summarizing the original scaled dot-product attention mechanism. Under this
framework, each encoder and the knowledge retriever has a key, query, and
value embedding layer that maps the input into output queries, keys, and
values of dimension $D_{q}=D_{k}$, $D_{k}$, and $D_{v}$, respectively. Let
$\mathbf{q}_{t}\in\mathbb{R}^{D_{k}\times 1}$ denote the query corresponding
to the question the learner responds to at time $t$, the scaled dot-product
attention values $\alpha_{t,\tau}$ are computed using the softmax function
(Goodfellow et al., 2016) as

$\displaystyle\alpha_{t,\tau}=\mbox{Softmax}(\frac{\mathbf{q}_{t}^{\intercal}\mathbf{k}_{\tau}}{\sqrt{D_{k}}})=\frac{\exp(\frac{\mathbf{q}_{t}^{\intercal}\mathbf{k}_{\tau}}{\sqrt{D_{k}}})}{\sum_{\tau^{\prime}}\exp(\frac{\mathbf{q}_{t}^{\intercal}\mathbf{k}_{\tau}}{\sqrt{D_{k}}})}\in[0,1].$

The output of the scaled dot-product attention mechanism is then given by
$\textstyle\sum_{\tau}\alpha_{t,\tau}\mathbf{v}_{\tau}\in\mathbb{R}^{D_{v}\times
1}$. $\mathbf{k}_{\tau}\in\mathbb{R}^{D_{k}\times 1}$ and
$\mathbf{v}_{\tau}\in\mathbb{R}^{D_{v}\times 1}$ denote the key and value for
the question at time step $\tau$, respectively. Depending on the specific
component, the output depends either on both the past and the current
($\tau\leq t$ for the question and knowledge encoders) or only the past
($\tau<t$ for the knowledge retriever).

Both encoders employ the self-attention mechanism, i.e., $\mathbf{q}_{t}$,
$\mathbf{k}_{t}$, and $\mathbf{v}_{t}$ are computed using the same input; the
question encoder uses $\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{t}\\}$ while the
knowledge encoder uses $\\{\mathbf{y}_{1},\ldots,\mathbf{y}_{t-1}\\}$. The
knowledge retriever, on the other hand, does not use self-attention. As shown
in Fig. 1, at time step $t$, it uses $\hat{\mathbf{x}}_{t}$ (the modified
embedding of the current question),
$\\{\hat{\mathbf{x}}_{1},\ldots,\hat{\mathbf{x}}_{t-1}\\}$ (the context-aware
embeddings of past questions), and
$\\{\hat{\mathbf{y}}_{1},\ldots,\hat{\mathbf{y}}_{t-1}\\}$ (the context-aware
embeddings of past question-response pairs) as input to generate the query,
keys, and values, respectively. We note that SAKT uses question embeddings for
mapping queries whereas response embeddings for key and value mapping. In our
experiments, we have found that using question embeddings for mapping both
queries and keys is much more effective.

However, this basic scaled dot-product attention mechanism is not likely going
to be sufficient for KT. The reason is that learning is temporal and memories
decay (Pashler et al., 2009); a learner’s performance in the distant past is
not as informative as recent performance when we are predicting their response
to the current question. Therefore, we develop a new monotonic attention
mechanism that reflects our second intuition: _when a learner faces a new
question, past experiences i) on unrelated concepts and ii) that are from too
long ago are not likely to be highly relevant._ Specifically, we add a
multiplicative exponential decay term to the attention scores as:

$\displaystyle\alpha_{t,\tau}=\frac{\exp{(s_{t,\tau})}}{\sum_{\tau^{\prime}}\exp{(s_{t,\tau^{\prime}})}},$

with

(1) $\displaystyle s_{t,\tau}$ $\displaystyle=\frac{\exp\left(-\theta\cdot
d(t,\tau)\right)\cdot\mathbf{q}_{t}^{\intercal}\mathbf{k}_{\tau}}{\sqrt{D_{k}}},$

where $\theta>0$ is a learnable decay rate parameter and $d(t,\tau)$ is
temporal distance measure between time steps $t$ and $\tau$. In other words,
the attention weights for the current question on a past question depends not
only on the similarity between the corresponding query and key, but also on
the relative number of time steps between them. In summary, our monotonic
attention mechanism takes the basic form of an exponential decay curve over
time with possible spikes at time steps when the past question is highly
similar to the current question. We note that we apply exponential decay to
the attention weights rather than latent knowledge, which is the common
approach in existing learner models (see e.g., (Reddy et al., 2016; Mozer et
al., 2017)).

We note that there are many other possible ways to characterize the temporal
dynamics of attention. First, in language tasks that attention networks excel
at, the temporal dynamics can be modeled using additive positional embeddings
or learnable embeddings (Vaswani et al., 2017). Second, in our monotonic
attention mechanism, we can also parameterize the exponential decay as
$s_{t,\tau}=\frac{\mathbf{q}_{t}^{\intercal}\mathbf{k}_{\tau}}{\sqrt{D_{k}}}-\theta\cdot
d(t,\tau)$. However, neither of these changes lead to comparable performance
to our chosen model setup; we will compare AKT against its variants using
positional encoding rather than monotonic attention in our experiments.

A context-aware distance measure. The exponential decay function decides the
rate at which the attention weights decay as the distance between the current
time index and the previous time indices increase. A straightforward way to
define the distance between two time indices is their absolute value
difference, i.e., $d(t,\tau)={|t-\tau|}$. However, this distance is not
context-aware and ignores the practice history of each learner. For example,
consider the two following sequences of concepts a learner practiced on:

$\displaystyle{\mbox{Venn Diagram
(VD)}}_{1},{\mbox{VD}}_{2},\cdots,{\mbox{VD}}_{8},{\mbox{Prime Numbers
(PN)}}_{9},{\mbox{PN}}_{10}$

and

$\displaystyle{\mbox{PN}}_{1},{\mbox{VD}}_{2},{\mbox{VD}}_{3},\cdots,{\mbox{VD}}_{9},{\mbox{PN}}_{10},$

where the notation “$VD_{2}$” means that the learner practiced the concept of
Venn Diagram at time step $2$. In this example, the learner answers a question
on Prime Numbers at $t=10$, i.e., the current time index, in both of these
sequences, but the most recent past practice on Prime Numbers comes at
different time indices. Since the concepts of Venn Diagram and Prime Numbers
are not closely related, the learner’s previous practices on Prime Numbers is
more relevant to us when predicting their answer to the current practice
question than recent practices on Venn Diagram. In this case, with the
straightforward absolute value difference, an exponential decay curve will
significantly reduce the attention weight assigned to the practice on Prime
Numbers at $t=1$.

Therefore, we propose the following context-aware distance measure between
time steps $d(t,\tau)$ with $\tau\leq t$ for the exponential decay mechanism
(in the encoders):

$\displaystyle d(t,\tau)$
$\displaystyle=|t-\tau|\cdot\sum_{t^{\prime}=\tau+1}^{t}\gamma_{t,t^{\prime}},$
$\displaystyle\gamma_{t,t^{\prime}}$
$\displaystyle=\frac{\exp{(\frac{\mathbf{q}_{t}^{\intercal}\mathbf{k}_{t^{\prime}}}{\sqrt{D_{k}}})}}{\sum_{1\leq\tau^{\prime}\leq
t}\exp{(\frac{\mathbf{q}_{t}^{\intercal}\mathbf{k}_{\tau^{\prime}}}{\sqrt{D_{k}}})}},\,\forall
t^{\prime}\leq t.$

For the knowledge retriever, we replace $\tau^{\prime}\leq t$ with $\tau<t$
and $t^{\prime}\leq t$ with $t^{\prime}<t$ correspondingly. In other words,
this context-aware distance measure uses another softmax function to adjust
the distance between consecutive time indices according to how the concept
practiced in the past is related to the current concept. In practice, in each
iteration during model training, we use the current AKT model parameters to
compute the modified distance measure and fix it; we do not pass gradients
through the distance measure.

Multi-head attention and sub-layers. We also incorporate multi-head attention
which is effective in attending to past positions at multiple time scales
(Vaswani et al., 2017). Therefore, we use $H$ independent attention heads
where every head has its own decay rate $\theta$, concatenate the final output
into a $(D_{v}\cdot H)\times 1$ vector and pass it to the next layer. This
model design enables AKT to summarize past learner performance at multiple
time scales, which bears some similarities to the multiple time windows in the
multiscale context, DASH, and DAS3H models (Pashler et al., 2009; Lindsey et
al., 2014; Choffin et al., 2019). We also use several sub-layers, including
one for layer normalization (Lei Ba et al., 2016), one for dropout (Srivastava
et al., 2014), a fully-connected feedforward layer, and a residual connection
layer (He et al., 2016) in each encoder and the knowledge retriever.

###  3.3. Response Prediction

The last component of the AKT method predicts the learner’s response to the
current question. The input to the prediction model is a vector that
concatenates both the retrieved knowledge (the knowledge retriever output
$\mathbf{h}_{t}$) and the current question embedding ${\mathbf{x}}_{t}$; this
input goes through another fully-connected network before finally going
through the sigmoid function (Goodfellow et al., 2016) to generate the
predicted probability $\hat{r}_{t}\in[0,1]$ that the learner answers the
current question correctly. All learnable parameters in the entire AKT method
are trained in end-to-end fashion by minimizing the binary cross-entropy loss
of all learner responses, i.e.,

$\ell=\textstyle\sum_{i}\textstyle\sum_{t}-(r_{t}^{i}\log\hat{r}_{t}^{i}+(1-r_{t}^{i})\log(1-\hat{r}_{t}^{i})).$

###  3.4. Rasch Model-Based Embeddings

As we discussed above, existing KT methods use concepts to index questions,
i.e., setting $q_{t}=c_{t}$. This setup is necessary due to data sparsity. Let
$Q$ denote the total number of questions and $L$ denote the number of
learners. In most real-world learner response datasets, the number of learner
responses is comparable to $CL$ and much less than $QL$ since many questions
are assigned to few learners. Therefore, using concepts to index questions is
effective in avoiding overparameterization and overfitting. However, this
basic setup ignores the individual differences among questions covering the
same concept, thus limiting the flexibility of KT methods and their potential
for personalization.

We use a classic yet powerful model in psychometrics, the Rasch model (which
is also known as the 1PL IRT model) (Lord, 1980; Rasch, 1993), to construct
raw question and knowledge embeddings. The Rasch model characterizes the
probability that a learner answers a question correctly using two scalars: the
question’s difficulty, and the learner’s ability. Despite its simplicity, it
has shown to achieve comparable performance to more sophisticated models on
learner performance prediction in formal assessments when knowledge is static
(Lan et al., 2016; Wilson et al., 2016). Specifically, we construct the
embedding of the question $q_{t}$ from concept $c_{t}$ at time step $t$ as

$\displaystyle\mathbf{x}_{t}=\mathbf{c}_{c_{t}}+\mu_{q_{t}}\cdot\mathbf{d}_{c_{t}},$

where $\mathbf{c}_{c_{t}}\in\mathbb{R}^{D}$ is the embedding of the concept
this question covers, and $\mathbf{d}_{c_{t}}\in\mathbb{R}^{D}$ is a vector
that summarizes the variation in questions covering this concept, and
$\mu_{q_{t}}\in\mathbb{R}$ is a scalar _difficulty_ parameter that controls
how far this question deviates from the concept it covers. The question-
response pairs $(q_{t},r_{t})$ from concept $c_{t}$ are extended similarly
using the scalar difficulty parameter for each pair:

$\displaystyle\mathbf{y}_{t}=\mathbf{e}_{(c_{t},r_{t})}+\mu_{q_{t}}\cdot\mathbf{f}_{(c_{t},r_{t})},$

where $\mathbf{e}_{(c_{t},r_{t})}\in\mathbb{R}^{D}$ and
$\mathbf{f}_{(c_{t},r_{t})}\in\mathbb{R}^{D}$ are concept-response embedding
and variation vectors. This model choice reflects our third intuition:
_questions labeled as covering the same concept are closely related but have
important individual differences that should not be ignored._ This model
choice is partly inspired by another work in fusing KT and IRT models (Khajah
et al., 2014).

These Rasch model-based embeddings strike the right balance between modeling
individual question differences and avoiding overparameterization. For the
question embeddings, the total number of embedding parameters in this model is
$2CD+Q$, which is slightly more than that in a model that uses concepts to
index questions ($CD$), but much less than that in a model where each question
is parameterized individually ($QD$), since $C\ll Q$ and $D\gg 1$. We further
define the concept-response embeddings as
$\mathbf{e}_{(c_{t},r_{t})}=\mathbf{c}_{c_{t}}+\mathbf{g}_{r_{t}}$, where
$\mathbf{g}_{1}$ and $\mathbf{g}_{0}$ denote the embeddings for correct and
incorrect responses (regardless of the concept), respectively. Therefore, we
only introduce a total of $(C+2)D+Q$ new embedding parameters instead of
$2CD+Q$ new parameters for the concept-response embeddings. We note that our
question and question-response embeddings share a group of parameters
($\mathbf{c}_{c_{t}}$); this setting is different from existing neural
network-based KT methods where the two are independent of each other. These
compact embedding representations significantly reduce the number of
parameters in not only AKT but also some other KT methods, leading to improved
performance on future learner performance prediction; see Table 5 for details.

##  4\. Experimental Results

In this section, we detail a series of experiments we conducted to test on
several real-world datasets. We evaluate AKT both quantitatively through
predicting future learner responses and qualitatively through a series of
visualizations and case studies.

Dataset | Learners | Concepts | Questions | Responses
---|---|---|---|---
Statics2011 | $333$ | $1,223$ | - | $189,297$
ASSISTments2009 | $4,151$ | $110$ | $16,891$ | $325,637$
ASSISTments2015 | $19,840$ | $100$ | - | $683,801$
ASSISTments2017 | $1,709$ | $102$ | $3,162$ | $942,816$

Table 1. Dataset statistics.

Dataset | BKT+ | DKT | DKT+ | DKVMN | SAKT | AKT-NR | AKT-R
---|---|---|---|---|---|---|---
Statics2011 | $\sim 0.75$ | $0.8233\pm 0.0039$ | ${\bf 0.8301\pm 0.0039}$ | $0.8195\pm 0.0041$ | $0.8029\pm 0.0032$ | ${\it 0.8265\pm 0.0049}$ |
ASSISTments2009 | $\sim 0.69$ | ${\it 0.817\pm 0.0043}$ | $0.8024\pm 0.0045$ | $0.8093\pm 0.0044$ | $0.752\pm 0.004$ | $0.8169\pm 0.0045$ | ${\bf 0.8346\pm 0.0036}$
ASSISTments2015 |  | $0.731\pm 0.0018$ | ${\it 0.7313\pm 0.0018}$ | $0.7276\pm 0.0017$ | $0.7212\pm 0.002$ | ${\bf 0.7828\pm 0.0019}$ |
ASSISTments2017 |  | $0.7263\pm 0.0054$ | $0.7124\pm 0.0041$ | $0.7073\pm 0.0044$ | $0.6569\pm 0.0027$ | ${\it 0.7282\pm 0.0037}$ | ${\bf 0.7702\pm 0.0026}$

Table 2. Performance of all KT methods on all datasets in predicting future
learner responses. AKT (sometimes significantly) outperforms all baseline
methods on all datasets. Best models are bold, second best models are italic.

###  4.1. Experimental Setup

Datasets. We evaluate the performance of AKT and several baselines on
predicting future learner responses using four benchmark datasets:
ASSISTments2009, ASSISTments2015, ASSISTments2017222The ASSISTments datasets
are retrieved from
https://sites.google.com/site/assistmentsdata/home and
https://sites.google.com/view/assistmentsdatamining/., and Statics2011.333The
Statics2011 dataset is retrieved from
https://pslcdatashop.web.cmu.edu/DatasetInfo?datasetId=507. The ASSISTments
datasets were collected from an online tutoring platform; in particular, the
ASSISTments2009 dataset has been the standard benchmark for KT methods over
the last decade. The Statics2011 dataset was collected from a college-level
engineering course on statics. On all these datasets, we follow a series of
standard pre-processing steps in the literature. For the ASSISTments2009
dataset, we remove all interactions that are not associated to a named
concept. For the ASSISTments2015 dataset, we remove all interactions where the
“isCorrect” field is not 0 or 1. We list the numbers of learners, concepts,
questions, and question-response pairs in Table 1. Out of these datasets, only
the ASSISTments2009 and ASSISTments2017 datasets contain question IDs;
therefore, the Rasch model-based embeddings are only applicable to these two
datasets.

Baseline methods and evaluation metric. We compare AKT against several
baseline KT methods, including BKT+ (Yudelson et al., 2013), DKT, DKT+ (which
is an improved version of DKT with regularization on prediction consistency
(Yeung and Yeung, 2018)), DKVMN (Zhang et al., 2017), and the recently
proposed self-attentive KT (SAKT) method (Pandey and Karypis, 2019), which
uses an attention mechanism that can be viewed as a special case of AKT
without context-aware representations of questions and responses and the
monotonic attention mechanism. We use the area under the receiver operating
characteristics curve (AUC) as the metric to evaluate the performance of all
KT methods on predicting binary-valued future learner responses to questions.

Training and testing. For evaluation purposes, we perform standard k-fold
cross-validation (with $k=5$) for all models and all datasets. Thus, for each
fold, $20\%$ learners are used as the test set, $20\%$ are used as the
validation set, and $60\%$ are used as the training set. For each fold, we use
the validation set to perform early stopping and tune the parameters for every
KT method.

We truncate learner response sequences that are longer than $200$, following
(Piech et al., 2015a; Zhang et al., 2017), for computational efficiency
reasons. If a learner has more than $200$ responses, we break up their entire
sequence into multiple shorter sequences. We use the Adam optimizer to train
all models (Kingma and Ba, 2015) with a batch size of $24$ learners to ensure
that an entire batch can fit into the memory of our machine (equipped with one
NVIDIA Titan X GPU). We implement all versions of AKT in PyTorch; We also re-
implement DKT, DKT+, and SAKT, since including question IDs requires new
dataset partitions and leads to new experimental results. We use the Xavier
parameter initialization method (Glorot and Bengio, 2010) for AKT, DKT, DKT+,
and SAKT; for DKVMN, we follow their work and use samples from normal
distributions to initialize the parameters (Zhang et al., 2017). We do not re-
implement BKT+; its performance on various datasets is taken from (Zhang et
al., 2017). For most datasets and most algorithms, one training epoch takes
less than 10 seconds. We set the maximum number of epochs to $300$.

Dataset |  $\mbox{AKT}^{\mbox{raw}}$-NR | AKT-NR |  $\mbox{AKT}^{\mbox{raw}}$-R | AKT-R
---|---|---|---|---
Statics2011 | $0.8253$ | ${\bf 0.8265}$ |  |
ASSISTments2009 | $0.8082$ | ${\bf 0.8169}$ | $0.8267$ | ${\bf 0.8346}$
ASSISTments2015 | $0.7332$ | ${\bf 0.7828}$ |  |
ASSISTments2017 | $0.7066$ | ${\bf 0.7282}$ | $0.7552$ | ${\bf 0.7702}$

Table 3. AKT outperforms its variants that do not use contextual-aware
question and response representations.

Dataset | SAKT | $\mbox{AKT-NR}^{\mbox{pos}}$ | $\mbox{AKT-NR}^{\mbox{fixed}}$ | AKT-NR
---|---|---|---|---
Statics2011 | $0.8029$ | $0.8196$ | $0.8196$ | ${\bf 0.8265}$
ASSISTments2009 | $0.752$ | $0.7706$ | $0.7708$ | ${\bf 0.8169}$
ASSISTments2015 | $0.7212$ | $0.7271$ | $0.7272$ | ${\bf 0.7828}$
ASSISTments2017 | $0.6569$ | $0.672$ | $0.6722$ | ${\bf 0.7282}$

Table 4. AKT significantly outperforms its variants that do not use monotonic
attention.

Dataset | DKT | DKT-R | DKT+ | DKT+-R | DKVMN | DKVMN-R | SAKT | SAKT-R | AKT-NR | AKT-R
---|---|---|---|---|---|---|---|---|---|---
ASSISTments2009 | $0.817$ | $0.8179$ | $0.8024$ | $0.8033$ | $0.8093$ | $0.8235$ | $0.752$ | $0.7784$ | $0.8169$ | ${\bf 0.8346}$
ASSISTments2017 | $0.7263$ | $0.7543$ | $0.7124$ | $0.7382$ | $0.7073$ | $0.7628$ | $0.6569$ | $0.7137$ | $0.7282$ | ${\bf 0.7702}$

Table 5. The Rasch model-based embeddings (sometimes significantly) improve
the performance of KT methods.

###  4.2. Results and Discussion

Table 2 lists the performance of all KT methods across all datasets on
predicting future learner responses; we report the averages as well as the
standard deviations across five test folds. AKT-R and AKT-NR represent
variants of the AKT model with and without the Rasch model-based embeddings,
respectively. We see that AKT (sometimes significantly) outperforms other KT
methods on the ASSISTments datasets while DKT+ marginally outperforms AKT on
the smallest Statics2011 dataset. In general, AKT performs better on larger
datasets; this result suggests that attention mechanisms are more flexible
than recurrent neural networks and are thus more capable of capturing the rich
information contained in large-scale real-world learner response datasets. On
the ASSISTments2015 and ASSISTments2017 datasets, AKT-NR improves the AUC by
$6\%$ and $1\%$ over the closest baseline. It performs on-par with the best-
performing baseline on the Statics2011 and ASSISTments2009 datasets. More
importantly, on the ASSISTments2009 and 2017 datasets with question IDs, AKT-R
significantly outperforms other KT methods, by $2\%$ and $6\%$ over the
closest baseline, respectively. We note that DKT outperforms the more advanced
DKVMN method in our implementation. While we are able to replicate the
performance of DKVMN using the same experimental setting (Zhang et al., 2017),
we found that DKT performs much better than previously reported in that work.
DKT+ performs on-par with DKT, with minor improvements on the Statics2011
dataset. We also observe that the RNN-based model, DKT, outperforms SAKT on
all datasets.

Ablation study. In order to justify the three key innovations in the AKT
method, context-aware representations of questions and responses, the
monotonic attention mechanism, and the Rasch model-based embeddings, we
perform three additional ablation experiments comparing several variants of
the AKT method. The first experiment compares AKT-NR and AKT-R using context-
aware question and response representations (with the question and knowledge
encoders) with two variants $\mbox{AKT}^{\mbox{raw}}$-NR and
$\mbox{AKT}^{\mbox{raw}}$-R; In these variants, we use raw question and
response embeddings as their representations instead of the context-aware
representations (i.e., without passing them through the encoders). The second
experiment compares AKT-NR against several variants without the monotonic
attention mechanism. These variants include $\mbox{AKT-NR}^{\mbox{pos}}$,
which uses (learnable) positional encoding to capture temporal dependencies in
learner response data and $\mbox{AKT-NR}^{\mbox{fixed}}$, which uses (fixed)
positional encoding using different frequencies of sine and cosine functions
(Vaswani et al., 2017). The third experiment compares AKT-R with AKT-NR, DKT,
DKT-R, DKT+, DKT+-R, DKVMN, DKVMN-R, SAKT, and SAKT-R on the ASSISTments2009
and 2017 datasets where question IDs are available; DKT-R, DKT+-R, DKVMN-R,
and SAKT-R refer to the DKT, DKT+, DKVMN, and SAKT methods augmented with the
Rasch model-based embeddings as input, respectively.

Table 3 shows the results (only averages and not standard deviations across
test folds, due to spatial constraints) of the first ablation experiment for
the context-aware representations (i.e., the question and knowledge encoders).
On all datasets AKT-R and AKT-NR outperform their counterparts,
$\mbox{AKT}^{\mbox{raw}}$-NR and $\mbox{AKT}^{\mbox{raw}}$-R, which use only a
single self-attention mechanism with exponential decay (i.e., the knowledge
retriever). These results suggest that our context-aware representations of
questions and responses are effective at summarizing each learner’s practice
history.

Table 4 shows the results of the second ablation experiment for the monotonic
attention mechanism. We see that AKT-NR significantly outperforms other
attention mechanisms using positional embeddings, including SAKT, by about
$1\%$ to $6\%$ on all datasets. We postulate that the reason for this result
is that unlike in language tasks where strong long-distance dependencies
between words are more common, the dependence of future learner performance on
the past is restricted to a much shorter time window. Therefore, using multi-
head attention with different exponential decay rates in the attention weights
can effectively capture short-term dependencies on the past at different time
scales.

Table 5 shows the results of the third ablation experiment for the Rasch
model-based embeddings on the two ASSISTments datasets where question IDs are
available. All baseline KT methods with the added Rasch model-based embeddings
outperform their regular versions, especially on the ASSISTments2017 dataset.
These results confirm our intuition that treating all questions covering the
same concept as a single question is problematic; individual differences among
these questions should not be ignored as long as overparameterization can be
avoided.

Remark. Our standard experimental setting follows that used in (Zhang et al.,
2017; Piech et al., 2015a). In this setting, for questions tagged with
multiple concepts (in the ASSISTments2009 dataset), a single learner response
is repeated multiple times, one for each concept. Other works used different
experimental settings for these questions; In (Wilson et al., 2016), the
authors removed such questions and as a result, DKT’s performance dropped to
0.71. In (Xiong et al., 2016), the authors built new concepts for each
combination of co-occurring single concepts and as a result, DKT’s performance
dropped to 0.73. Therefore, we also use an alternative experimental setting on
the ASSISTments2009 dataset. For a question tagged with multiple concepts, we
average the corresponding concept embeddings and use them as both input
embeddings and for response prediction. Table 6 lists the performance of all
KT methods on the ASSISTments2009 dataset under this setting. DKT’s
performance dropped to 0.76 using average embeddings, faring better than
settings under (Xiong et al., 2016; Wilson et al., 2016). We observe similar
performance drops compared to our standard experimental setting for all KT
methods, while AKT-R still comfortably outperforms all baselines.

DKT | DKT+ | DKVMN | SAKT | AKT-NR | AKT-R
---|---|---|---|---|---
$0.7616$ | $0.7552$ | $0.7556$ | $0.7432$ | ${\it 0.7627}$ | ${\bf 0.7866}$

Table 6. AKT still outperforms other KT methods on the ASSISTments2009 dataset
under an alternative experimental setting for questions tagged with multiple
concepts.

###  4.3. Visualizing Learned AKT Parameters

Figure 2. Visualizations of 2 attention weights in the decoder of AKT for
three attention heads and 2 attention weights for three consecutive practice
questions for a learner. Concept similarity and recency are key factor that
control the attention weights.

Monotonic attention. Figure 2 shows the interpretability offered by AKT’s
monotonic attention mechanism using the ASSISTments2009 dataset. Figure 2
visualizes the attention weights in the knowledge retriever for one learner as
an example; we plot the attention weights used to predict their performance on
20 consecutive practice questions across three attention heads. We see that
each attention head operates on its own time scale: they all have attention
windows of different widths. For example, the second head is capable of
attending to the entire past, up to 20 time steps (in this example); on the
contrary, the third head can only attend to the immediate past and focuses
primarily on the last 3-5 time steps. This observation suggests that some
questions and responses in the past contain information that is highly
predictive of the learner’s response to the current question; this information
can be effectively captured by multiple attention heads with different decay
rates.

Figure 2 visualizes the normalized attention weights in the knowledge
retriever for a single learner for three consecutive time steps. In the top
row, the learner is responding to a question on Concept 30 at time $T$ after
practicing this concept from $T-10$ to $T-5$, then taking a break to practice
on Concept 42, before coming back to Concept 30 at time $T-1$. We see that AKT
predicts their response to the current question by focusing more on previous
practices on this concept (both in the immediate past and further back) than
practices on another concept also in the immediate past. In the middle row,
the learner switches to practicing on Concept 42 again. Again, AKT learns to
focus on past practices on the same concept rather than the immediate past on
a different concept at times $T-2$ and $T-1$. In the bottom row, the learner
practices on Concept 42 for the second consecutive time, and AKT shows a
similar focus pattern to that in the top row, with the roles of Concepts 30
and 42 swapped. These observations suggest that AKT’s monotonic attention
mechanism has the potential to provide feedback to teachers by linking a
learner’s current response to their responses in the past; this information
may enable teachers to select certain questions that they have practiced for
them to re-practice and clear misconceptions before moving on. We also note
that AKT, using a data-driven approach, learns these attention patterns that
match hand-crafted features in existing KT methods (e.g., the number of total
attempts and correct attempts on this concept) (Pavlik Jr et al., 2009;
Lindsey et al., 2014).

Rasch model-based embeddings. Figure 3 visualizes the learned Rasch model-
based question embeddings for several concepts using t-SNE (Van Der Maaten,
2014) using the ASSISTments2009 dataset, together with their empirical
difficulties for selected questions (portions of correct responses across
learners). We also highlight the hardest and easiest question for each concept
based on their empirical difficulties. We see that questions on the same
concept form a curve and are ordered by their difficulty levels: for the
majority of concepts, questions on one end of the line segment are easy while
questions on the other end are hard. This result confirms our intuition that
questions from the same concept are not identical but closely related to each
other; this relationship can be well-captured by the Rasch model using its
difficulty parameter.

Figure 3. Visualization of learned question embeddings with fraction of
correct responses among learners for selected concepts.

Concept |  Question |  $\mu_{q}$
---|---|---
|  From the list of numbers below, which number is the largest? 6.7, 6.4, 3.4, 5.1 |  -0.0397
Ordering Positive Decimals |  Which of following decimals is the smallest? 0.107, 0.1889, 0.12, 0.11582 |  0.0090
|  Arrange these numbers from least to greatest. -1/4, 12.1, -1.4, -4/4 |  0.0279
|  Steve has a marble jar, that he likes to randomly select marbles from it to play with. The jar has 5 orange marbles and 5 purple marbles. What is the probability that Steve gets an orange marble from the jar? |  $-0.0515$
Probability of a Single Event |  A bag contains 8 red, 5 green, and 7 blue popsicles. John is going to draw out a popsicle without looking in the bag. What is the probability that he will draw either a green or a blue popsicle? |  $0.0088$
|  A card is selected at random from a standard deck of 52 cards. Find the probability of choosing a club or an ace card. Enter your answer as a fraction. |  $0.0548$
|  Convert 7/7 into a percent. |  -0.0540
Conversion of Fractions |  Convert 8/4 into a percent. |  0.0038
|  Convert 9/8 into a percent. |  0.0529

Table 7. Question text and learned difficulty parameters ($\mu_{q}$) for
selected questions on three concepts. Learned difficulty levels match our
intuition on the difficulty of these questions.

Table 7 lists sample questions each for three different concepts, “Ordering
Positive Decimals”, “Probability of a Single Event”, and “Conversion of
Fractions to Percents”, and their learned difficulty parameters. We show three
questions for each concept: an easy one, an average one, and a hard one. Using
the “Probability of a Single Event” concept as an example, the learned
difficulty parameter values ($\mu_{q}$) are $-0.0515$ for the easy one,
$0.0088$ for the average one, and $0.0548$ for the hard one. These learned
difficulty levels match our understanding about the difficulty levels of these
questions.

These results suggest that AKT has the potential to be applied in real-world
educational settings. Using the estimated difficulty parameters, a
computerized learning platform can either i) automatically select questions
with appropriate difficulty levels for each learner given their past
responses, or ii) support teachers to adjust course plans by providing them
feedback on question difficulty levels learned from real data. Therefore, AKT
improves over existing KT methods by not only providing state-of-the-art
predictive performance but also exhibiting interpretability and potential for
personalized learning.

##  5\. Conclusions and Future Work

In this paper, we have proposed attentive knowledge tracing, a new method for
knowledge tracing that relies fully on attention networks. Our method improves
upon existing knowledge tracing methods by building context-aware
representations of questions and responses, using a monotonic attention
mechanism to summarize past learner performance in the right time scale, and
by using the Rasch model to capture individual differences among questions
covering the same concept. Experimental results on a series of benchmark real-
world learner response datasets show that our method outperforms state-of-the-
art KT methods and exhibit excellent interpretability. Avenues of future work
include i) incorporating question text to further enhance the interpretability
of question and concept embeddings and ii) testing whether our method can
improve prediction performance on language learning datasets where memory
decay occurs (Reddy et al., 2016).

## References

  * (1)
  * Cen et al. (2006) Hao Cen, Kenneth Koedinger, and Brian Junker. 2006\.  Learning factors analysis–A general method for cognitive model evaluation and improvement. In _Proc. International Conference on Intelligent Tutoring Systems_. 164–175.
  * Choffin et al. (2019) Benoît Choffin, Fabrice Popineau, Yolaine Bourda, and Jill-Jênn Vie. 2019.  DAS3H: Modeling student learning and forgetting for pptimally scheduling distributed practice of skills. In _Proc. International Conference on Educational Data Mining_. 29–38.
  * Corbett and Anderson (1994) Albert Corbett and John Anderson. 1994.  Knowledge tracing: Modeling the acquisition of procedural knowledge.  _User Modeling and User-adapted Interaction_ 4, 4 (Dec. 1994), 253–278.
  * Glorot and Bengio (2010) Xavier Glorot and Yoshua Bengio. 2010.  Understanding the difficulty of training deep feedforward neural networks. In _Proc. International Conference on Artificial Intelligence and Statistics_. 249–256.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016\.  _Deep Learning_.  MIT Press.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proc. IEEE Conference on Computer Vision and Pattern Recognition_. 770–778.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural Computation_ 9, 8 (Nov. 1997), 1735–1780.
  * Khajah et al. (2014) MM Khajah, Y Huang, JP González-Brenes, MC Mozer, and P Brusilovsky. 2014.  Integrating knowledge tracing and item response theory: A tale of two frameworks. In _Proc. International Workshop on Personalization Approaches in Learning Environments_ , Vol. 1181. 7–15.
  * Khajah et al. (2016) Mohammad Khajah, Robert Lindsey, and Michael Mozer. 2016\.  How deep is knowledge tracing?. In _Proc. International Conference on Educational Data Mining_. 94–101.
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization. In _Proc. International Conference on Learning Representations_.
  * Lan and Baraniuk (2016) Andrew Lan and Richard Baraniuk. 2016.  A Contextual Bandits Framework for Personalized Learning Action Selection. In _Proc. International Conference on Educational Data Mining_. 424–429.
  * Lan et al. (2016) Andrew Lan, Tom Goldstein, Richard Baraniuk, and Christoph Studer. 2016.  Dealbreaker: A nonlinear latent variable model for educational data. In _Proc. International Conference on Machine Learning_. 266–275.
  * Lan et al. (2014) Andrew Lan, Christoph Studer, and Richard Baraniuk. 2014\.  Time-varying learning and content analytics via sparse factor analysis. In _Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 452–461.
  * Lei Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. 2016\.  Layer normalization.  _arXiv preprint arXiv:1607.06450_ (July 2016).
  * Lindsey et al. (2014) Robert Lindsey, Jeffery Shroyer, Harold Pashler, and Michael Mozer. 2014.  Improving students’ long-term knowledge retention through personalized review.  _Psychological Science_ 25, 3 (Jan. 2014), 639–647.
  * Lord (1980) Frederick Lord. 1980\.  _Applications of Item Response Theory to Practical Testing Problems_.  Erlbaum Associates.
  * Mozer et al. (2017) Michael Mozer, Denis Kazakov, and Robert Lindsey. 2017\.  Discrete-event continuous-time recurrent nets.  _arXiv preprint arXiv:1710.04110_ (Oct. 2017).
  * Pandey and Karypis (2019) Shalini Pandey and George Karypis. 2019.  A self attentive model for knowledge tracing. In _Proc. International Conference on Educational Data Mining_. 384–389.
  * Pardos and Heffernan (2010) Zachary Pardos and Neil Heffernan. 2010.  Modeling individualization in a Bayesian networks implementation of knowledge tracing. In _Proc. International Conference on User Modeling, Adaptation, and Personalization_. 255–266.
  * Pascanu et al. (2013) Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. 2013\.  On the difficulty of training recurrent neural networks. In _Proc. International Conference on Machine Learning_. 1310–1318.
  * Pashler et al. (2009) Harold Pashler, Nicholas Cepeda, Robert Lindsey, Ed Vul, and Michael Mozer. 2009.  Predicting the optimal spacing of study: A multiscale context model of memory. In _Proc. Conference on Advances in Neural Information Processing Systems_. 1321–1329.
  * Pavlik Jr et al. (2009) Philip Pavlik Jr, Hao Cen, and Kenneth Koedinger. 2009\.  Performance factors analysis–A new alternative to knowledge tracing. In _Proc. International Conference on Artificial Intelligence in Education_. 531–538.
  * Piech et al. (2015a) Chris Piech, Jonathan Bassen, Jonathan Huang, Surya Ganguli, Mehran Sahami, Leonidas J Guibas, and Jascha Sohl-Dickstein. 2015a.  Deep knowledge tracing. In _Proc. Conference on Advances in Neural Information Processing Systems_. 505–513.
  * Piech et al. (2015b) Chris Piech, Jonathan Huang, Andy Nguyen, Mike Phulsuksombati, Mehran Sahami, and Leonidas Guibas. 2015b.  Learning Program Embeddings to Propagate Feedback on Student Code. In _Proc. International Conference on Machine Learning_. 1093–1102.
  * Rasch (1993) Georg Rasch. 1993\.  _Probabilistic Models for Some Intelligence and Attainment Tests_.  MESA Press.
  * Reddy et al. (2016) Siddharth Reddy, Igor Labutov, Siddhartha Banerjee, and Thorsten Joachims. 2016.  Unbounded human learning: Optimal scheduling for spaced repetition. In _Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 1815–1824.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: A simple way to prevent neural networks from overfitting.  _The Journal of Machine Learning Research_ 15, 1 (June 2014), 1929–1958.
  * Van Der Maaten (2014) Laurens Van Der Maaten. 2014\.  Accelerating t-SNE using tree-based algorithms.  _The Journal of Machine Learning Research_ 15, 1 (2014), 3221–3245.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need. In _Proc. Conference on Advances in Neural Information Processing Systems_. 5998–6008.
  * Vie and Kashima (2019) Jill-Jênn Vie and Hisashi Kashima. 2019.  Knowledge tracing machines: Factorization machines for knowledge tracing. In _Proc. AAAI Conference on Artificial Intelligence_ , Vol. 33. 750–757.
  * Wilson et al. (2016) Kevin Wilson, Yan Karklin, Bojian Han, and Chaitanya Ekanadham. 2016.  Back to the basics: Bayesian extensions of IRT outperform neural networks for proficiency estimation. In _Proc. International Conference on Educational Data Mining_. 539–544.
  * Woolf (2010) Beverly Park Woolf. 2010\.  _Building Intelligent Interactive Tutors: Student-centered Strategies for Revolutionizing E-learning_.  Morgan Kaufmann.
  * Xiong et al. (2016) Xiaolu Xiong, Siyuan Zhao, Eric G Van Inwegen, and Joseph E Beck. 2016.  Going deeper with deep knowledge tracing.  _International Educational Data Mining Society_ (2016).
  * Yeung and Yeung (2018) Chun-Kit Yeung and Dit-Yan Yeung. 2018.  Addressing two problems in deep knowledge tracing via prediction-consistent regularization. In _Proc. ACM Conference on Learning at Scale_. ACM, 5.
  * Yudelson et al. (2013) Michael Yudelson, Kenneth Koedinger, and Geoffrey Gordon. 2013\.  Individualized Bayesian knowledge tracing models. In _Proc. International Conference on Artificial Intelligence in Education_. 171–180.
  * Zhang et al. (2017) Jiani Zhang, Xingjian Shi, Irwin King, and Dit-Yan Yeung. 2017\.  Dynamic key-value memory networks for knowledge tracing. In _Proc. International Conference on World Wide Web_. 765–774.

Supplementary Material

Parameter tuning. For all methods, we use a two-layer, fully-connected network
for the response prediction model, with $512$ and $256$ hidden units in the
first and second layers, respectively. For AKT, we fix the number of attention
heads to $H=8$ and use the same dimension for the queries, keys, and values
for each head in the encoders and the knowledge retriever, i.e.,
$D_{k}=D_{v}=D/8$ where $D$ is the input embedding dimension. For AKT, we
share the query and key embedding layer in the attention mechanism. We do not
perform grid search over the values of these parameters since the performance
of KT methods is insensitive to these parameters. For all methods, we use
$\\{256,512\\}$, $\\{256,512\\}$, and $\\{0,0.05,0.1,0.15,0.2,0.25\\}$ as
values of the input embedding dimension, the hidden state dimension, and the
dropout rate for the feedforward network, respectively. We also use
$\\{1,10,\infty\\}$ as values of the maximum gradient norm for clipping
(Pascanu et al., 2013) where $\infty$ means no gradient norm clipping. For
AKT, SAKT, and their variants, we use $\\{5\times 10^{-6},10^{-5},10^{-4}\\}$
as values of the learning rate in the Adam optimizer. For DKT, DKT+, and
DKVMN, we use $\\{10^{-4},10^{-3}\\}$ as values of the learning rate.
Additionally, for DKVMN, we use $\\{20,50\\}$ as values of the memory size
parameter, following (Zhang et al., 2017). For DKT+, we use $\\{0.1,0.2\\}$,
$\\{0.3,1\\}$, and $\\{3,30\\}$ as values of the reconstruction
regularization, the $\ell_{1}$-norm penalty, and the $\ell_{2}$-norm penalty
parameters, respectively, following (Yeung and Yeung, 2018).


# End-to-End Stable Imitation Learning via Autonomous Neural Dynamic Policies

Dionis Totsila1†∗, Konstantinos Chatzilygeroudis2†∗, Denis Hadjivelichkov3,
Valerio Modugno3,
Ioannis Hatzilygeroudis1, and Dimitrios Kanoulas3 ∗Corresponding authors:
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>† Equal Contribution1Computer Engineering and
Informatics Department (CEID), University of Patras, Greece2CILab, Department
of Mathematics, University of Patras, Greece3RPL Lab, University College
London, United Kingdom

###### Abstract

State-of-the-art sensorimotor learning algorithms offer policies that can
often produce unstable behaviors, damaging the robot and/or the environment.
Traditional robot learning, on the contrary, relies on dynamical system-based
policies that can be analyzed for stability/safety. Such policies, however,
are neither flexible nor generic and usually work only with proprioceptive
sensor states. In this work, we bridge the gap between generic neural network
policies and dynamical system-based policies, and we introduce Autonomous
Neural Dynamic Policies (ANDPs) that: (a) are based on autonomous dynamical
systems, (b) always produce asymptotically stable behaviors, and (c) are more
flexible than traditional stable dynamical system-based policies. ANDPs are
fully differentiable, flexible generic-policies that can be used in imitation
learning setups while ensuring asymptotic stability. In this paper, we explore
the flexibility and capacity of ANDPs in several imitation learning tasks
including experiments with image observations. The results show that ANDPs
combine the benefits of both neural network-based and dynamical system-based
methods.

###### Index Terms:

Robot Learning, Imitation Learning, Dynamical System-Based Policies, Lyapunov
Stability, Data-Efficient Learning

##  I Introduction

Choosing the appropriate policy structure is crucial for effective and
practical robot learning [1, 2, 3]. Currently, either in the context of
Reinforcement Learning (RL) [4] or Imitation Learning (IL) [5], the standard
choice is to use Neural Networks (NNs). NNs possess the flexibility needed to
learn complicated behaviors as well as the generalizability required to be
able to run the same algorithms in any robot or scenario. However, NN-based
policies are black-box and cannot ensure well-behaved trajectories, meaning
that their behavior cannot be predicted in unforeseen situations. As a result,
RL algorithms often make harmful decisions for the robot and/or the
environment, especially during initial learning stages.

This comes in contrast with traditional robot learning literature [6], where
usually in the context of IL/Learning from Demonstrations (LfD) the policy
behavior is shaped according to some well-defined criteria. For example,
producing behaviors that are guaranteed to asymptotically converge to an
attractor is an important concept of traditional robot learning [6, 7]. The
main building tool for this is a Dynamical System (DS), and the main idea is
to represent the policy to be learned as a DS. This gives us the ability to
reason about the policy in terms familiar to control theory and make proofs
about properties that we care about (e.g., for asymptotic stability) [7]. This
concept has been explored in robotic scenarios with two main different
approaches: (a) time-dependent DSs that mostly fall under the framework of
Dynamic Movement Primitives (DMPs) [8, 9, 10], and (b) autonomous DSs where
the input is only dependent on the current state [11, 7]. Both approaches are
able to provide asymptotic stability guarantees, while autonomous DSs’
reactiveness does not depend on time. Traditionally, both approaches have been
utilized mainly in Imitation Learning (IL)/Learning from Demonstrations (LfD)
scenarios [12, 13, 14, 15, 7, 16], but recently there was an attempt to use
DMPs with RL [17, 18].

Figure 1: Autonomous Neural Dynamic Policy Outline.

In this work, we aim at developing a novel policy representation that:

  1. 1.

Produces behaviors that are guaranteed to asymptotically converge to an
attractor;

  2. 2.

Is universal, meaning that any robot/embodied agent can use it;

  3. 3.

Can accept any observation space (e.g. RGB images), and the input is not
limited only to the feedback of robot states.

The first feature guarantees that the policy does not produce unpredictable
behaviors outside the trained data, but will try to go toward the attractor,
which is a critical aspect for robotic applications. Even if this feature
cannot guarantee that the robot will never try anything harmful (e.g., very
big velocity command), it is a good stepping stone towards having safe robot
behaviors. The second characteristic is important as it will make the policy
usable by any robotic mechanism and any scenario. The last characteristic is
important for practical robotic applications since traditionally policies that
provide stability guarantees are not straightforward to utilize with states
that are not limited to proprioceptive sensor states.

Inspired by the LfD literature and the usage of DSs, we attempt to integrate
them with the representation capabilities of NNs, with the intention of
creating a policy with the aforementioned properties. To achieve this goal:

  * •

We assume that the state of the system can be divided into a part that is
directly controlled (e.g., joint positions), and a part that can only be
observed and/or indirectly controlled (e.g., a box);

  * •

We represent the policy as a non-linear combination of linear systems; this
gives us the ability to reason about the stability of the produced behavior,
while also being able to exploit the representation abilities of NNs to
combine the elementary DSs effectively.

We call this new type of policies Autonomous Neural Dynamic Policies (ANDPs)
because they: (a) are based on dynamical systems, (b) are generic policies,
(c) are based on neural networks, and (d) do not depend on the time (thus,
autonomous). The main novelty of ANDPs lies in their ability to accept any
input space (even images), while still producing asymptotically stable
behaviors of the controllable state. This is achieved by imposing constraints
on the elementary linear DSs, while making the policy expressive by using NNs
to combine them. Finally, we perform some reparameterizations to “eliminate”
the constraints and to be able to optimize ANDPs using gradient-based
unconstrained optimization.

##  II Related Work

The choice of the policy structure plays an important role for the
effectiveness of learning in practical robot applications. When designing the
policy structure, there is always a tradeoff between having a representation
that is expressive, and one that provides a space that is efficiently
searchable [2].

The most obvious way to make the policy easy to be searched (or optimized) is
to hand-design it. In [19], for example, the authors design by hand a policy
for a ball acquisition task, which has only four parameters. This low-
dimensional policy can be easily optimized, but with only four parameters it
might not possess big expressiveness. Moreover, if we are faced with a
different robot/task, we need to re-design the policy from scratch. On the
other hand, using a function approximator (e.g. a neural network) to describe
the policy, enables us to easily increase the expressiveness and generality of
the policy, but can make the policy difficult to optimize for.

There are numerous works that describe best practices and policy structures
that ease the learning process. In [3] the authors thoroughly evaluate
different action spaces (with the corresponding low-level controllers, and
thus policy structures) in a wide range of scenarios. They conclude that
operating in end-effector space combined with low-level controllers make the
learning process faster, more robust, and provide easier transfer from
simulation to the physical world and between robots. The authors in [1] reach
to similar conclusions in a related study that performs a comparison between
different action spaces for manipulation tasks. Overall, it is clear from the
literature that in order to learn effectively in practical robotic
applications, we need a structured policy representation.

Dynamic Movement Primitives (DMPs) [8, 9, 10] provide a framework for
structured policy types that are basically a dynamical system. As such, we can
insert desired properties that can make our system behave in specific ways.
DMPs are split into two systems: (a) the canonical system (which is usually a
springer-damper system), and (b) the transformation system. The canonical
system represents the movement _phase_ $s$, which starts at 1 and converges to
0 over time. The transformation systems combine a spring-damper system with a
function approximator (e.g., NNs) which, when integrated, generates
accelerations. Multi-dimensional DMPs are achieved by coupling multiple
transformation systems with one canonical system. DMPs can be used in the end-
effector and the joint angle space. There are numerous successful
implementations of DMPs mainly in IL/LfD scenarios covering a wide range of
tasks [10, 14, 13] and even multi-task cases [12, 20].

DMPs, however, are time-dependent and thus they may produce undesirable
behaviors; for example, a policy that cannot adapt to perturbations after some
time. Stable Estimator of Dynamical Systems (SEDS) [7] explores how to use
dynamical systems in order to define autonomous (i.e., time-independent)
controllers (or policies) that are asymptotically stable. The main idea of the
algorithm is to use a finite mixture of Gaussian functions (Gaussian Mixture
Models - GMMs) as the policy,
$\dot{\boldsymbol{\xi}}=\pi_{\text{seds}}(\boldsymbol{\xi})$, with specific
properties that satisfy some stability guarantees. SEDS, however, requires
demonstrated data in order to optimize the policy (i.e., data gathered from
experts), although similar ideas have been used within the RL framework [21].
SEDS and its variants [15, 22] have provided effective solutions to difficult
tasks ranging from point-to-point motions [7] to humanoid navigation [23] and
following force profiles [16]. One of the main limitations of SEDS is the
_accuracy vs. stability dilemma_ , i.e., it performs poorly in highly non-
linear motions that contain high curvatures or that are non-monotonic. This is
mainly because of the constraints SEDS imposes on the structure of the GMMs.
Recent variants of SEDS, and in particular LPV-DS [15, 22], attempt to relax
the constraints by disconnecting the learning of the weighting function from
the elementary DSs; LPV-DS still uses GMMs for learning the functions.

Recently, Bahl et al. [17] proposed a method to combine neural networks with
DMPs. The main idea is to create a high-level controller with NNs that takes
as input an unstructured state and _selects_ parameters of a DMP that acts as
the low-level controller. Their method, called Neural Dynamic Policies (NDPs),
was able to learn multiple LfD and RL scenarios effectively. In a recent
extension [18], the authors provide a hierarchical formulation of their method
that can be used to solve more complex tasks. To the best of our knowledge,
this work proposes one of the first methods that effectively combine NNs with
DSs and provide the first general-purpose policy (i.e., it can be used with
almost any input and any robot) that is based on DSs. However, since their
policy changes the dynamical system every $X$ steps there are still no
theoretical guarantees for stability, but mostly rely on the data-driven
capabilities of the NNs to capture this type of behaviors.

In this paper, we take inspiration from LPV-DS and NDPs and provide a policy
structure, called Autonomous Neural Dynamic Policies (ANDPs), that (a) always
produces asymptotically stable behaviors for the controllable part of the
state, and that (b) is a general purpose policy that can work with any action
space and can accept arbitrary inputs (e.g., images).

##  III Problem formulation

We assume discrete-time dynamical systems that can be described by transition
dynamics of the form:

$\displaystyle\boldsymbol{x}^{t+1}=f(\boldsymbol{x}^{t},\boldsymbol{u}^{t})+\boldsymbol{w}$
(1)

where the system is at state $\boldsymbol{x}^{t}\in\mathbb{R}^{E}$ at time
$t$, takes control input $\boldsymbol{u}^{t}\in\mathbb{R}^{U}$ and ends up at
state $\boldsymbol{x}^{t+1}$ at time $t+1$, $\boldsymbol{w}$ is i.i.d.
Gaussian system noise, and $f$ is a function that describes the unknown
transition dynamics.

We assume that the system is controlled through a parameterized policy
$\boldsymbol{u}=\pi(\boldsymbol{x}|\boldsymbol{\theta})$ that is followed for
$M$ steps ($\boldsymbol{\theta}$ are the parameters of the policy). When
following a particular policy for $M$ time-steps from an initial state
distribution $p(\boldsymbol{x}^{0})$, the system’s states and actions jointly
form trajectories
$\boldsymbol{\tau}=(\boldsymbol{x}^{0},\boldsymbol{u}^{0},\boldsymbol{x}^{1},\boldsymbol{u}^{1},\dots,\boldsymbol{x}^{M-1})$,
which are often also called rollouts or paths.

In this work, we define a novel policy structure and learning procedure
(called ANDPs) with stability guarantees. In an imitation learning scenario,
we assume access to a few demonstrated trajectories
$\\{\boldsymbol{\tau}_{i}\\}_{i=1,\dots,K}$, and we want to find the policy
parameterization $\boldsymbol{\theta}$ that “mimics” the demonstrated
trajectories as well as possible. In this work, we assume having access only
to the states of the system, $\boldsymbol{x}^{t}$, and not of the control
signals, $\boldsymbol{u}^{t}$. In other words, we have trajectories
$\\{\boldsymbol{s}_{i}\\}_{i=1,\dots,K}$ of the form
$\boldsymbol{s}=(\boldsymbol{x}^{0},\boldsymbol{x}^{1},\dots,\boldsymbol{x}^{M-1})$.
This makes the problem slightly more difficult and usually enforces the use of
a low-level controller [24].

##  IV Proposed Policy Structure

We make the assumption that the state of the system can be split into two
parts: (a) a part that can be directly controlled (e.g., positions and
velocities of the end-effector), and (b) a part that can only be observed
and/or indirectly controlled (e.g., obstacles/objects). In particular (we omit
the time notation, $t$, for clarity):

$\displaystyle\boldsymbol{x}=\begin{bmatrix}\boldsymbol{x}_{c}\\\
\boldsymbol{x}_{nc}\end{bmatrix}\in\mathbb{R}^{d_{c}+d_{nc}},$ (2)

where $\boldsymbol{x}_{c}$ is the part of the state that can be directly
controlled and $\boldsymbol{x}_{nc}$ is the part of the state that can only be
observed. $d_{c}$ and $d_{nc}$ are the state-space dimensions for the
controllable and non-controllable parts, respectively ($d_{c}+d_{nc}=E$).

We define the control policy as a dynamical system with a fixed attractor
$\boldsymbol{x}_{c}^{*}$ (formulated as a weighted sum of elementary linear
dynamical systems):

$\dot{\boldsymbol{x}}_{c}=\pi(\boldsymbol{x})=\sum_{i=1}^{N}w_{i}(\boldsymbol{x})\boldsymbol{A}_{i}\Big{(}\boldsymbol{x}_{c}^{*}-\boldsymbol{x}_{c}\Big{)}$
(3)

where $N$ is the number of elementary dynamical systems,
$w_{i}(\boldsymbol{x})\in\mathbb{R}$ are state-dependent weighting functions,
and $\boldsymbol{A}_{i}\in\mathbb{R}^{d_{c}\times d_{c}}$,
$\boldsymbol{x}_{c}^{*}\in\mathbb{R}^{d_{c}}$.

The control policy, $\pi(\boldsymbol{x})$ (Fig. 1), defines the desired
velocity profile that the controllable state $\boldsymbol{x}_{c}$ should
follow. Depending on the state representation one can directly use the output
for commanding the robot, use a PD controller, or use some inverse
dynamics/kinematics model. Note, that the controllable state
$\boldsymbol{x}_{c}$ can also contain velocities (e.g.,
$\boldsymbol{x}_{c}=\\{\boldsymbol{\xi},\dot{\boldsymbol{\xi}}\\}$, where
$\boldsymbol{\xi}$ is the end-effector translation) and in that case the
system is a second order DS. Although in this work we explore first-order DSs,
our formulation allows for second-order DS systems.

######  Theorem 1.

Assume that the controllable part of a state trajectory follows the policy as
defined in Eq. 3. Then, the function described by Eq. 3 is asymptotically
stable to $\boldsymbol{x}_{c}^{*}$ if

$\begin{cases}\boldsymbol{A}_{i}+\boldsymbol{A}_{i}^{T}\succ 0&\text{the
symmetric part of }A\text{ is psd}\\\
w_{i}(\boldsymbol{x})>0,&i=1,..,N,\forall\boldsymbol{x}\in\mathbb{R}^{E}\end{cases}$
(4)

###### Proof.

The proof follows classical Lyapunov analysis similar to [22].∎

The results of the above theorem can be described as _“The controllable part
of the system will always converge to the fixed attractor
$\boldsymbol{x}_{c}^{*}$”_. Although this does not guarantee that the whole
system state will converge to a desired state, this is an important property
for a policy to have, as it will always generate commands that will eventually
drive the controllable part of the system to a stable point. It is important
to note that this property holds if the controllable system can follow the
commanded velocities perfectly, and does not take into account the properties
of a possible low-level controller (e.g., a controller based on the
pseudoinverse of the Jacobian for end-effector control) or the rest of the
environment. This is, however, common in the LfD literature since designing a
policy that can guarantee the stability of the whole system and take into
account the properties of the low-level controller is a challenging task and
would require bulk approximations to be made [2, 24]. Nevertheless, in all of
our experiments, we never observed diverging motions and we did not have to
tune the low-level controllers to avoid such situations. Overall, these
limitations do not seem to have a big impact on the resulting behaviors and we
were able to learn a wide range of motions using different low-level
controllers (in joint- and task-space).

###  IV-A ANDPs via Neural Networks

The main intuition of ANDPs is to combine the power of neural networks to
learn from data while keeping the stability guarantees of the traditional DS-
based policies. In order to be able to represent the ANDPs (Eq. 3) with a
neural network, we have to: (a) find the “learnable” parameters, (b) make sure
that the policy is fully differentiable, and (c) handle the constraints of Eq.
4 properly.

In order to define the learnable parameters, we need to identify parameters of
Eq. 3. First, the matrices $\boldsymbol{A}_{i}$ do not depend on the state,
and thus we can directly optimize for their parameters. Second, in order to
define each $w_{i}(\boldsymbol{x})$, we use one neural network for all of
them. More concretely, we define a neural network $\Psi$ which takes input a
full system state $\boldsymbol{x}$ and predicts a vector
$\boldsymbol{W}\in\mathbb{R}^{N}$. In other words,
$\boldsymbol{W}=\Psi(\boldsymbol{x}|\boldsymbol{\psi})$, where
$\boldsymbol{\psi}$ are the parameters of the neural network. The
$i\text{-th}$ element of the $\boldsymbol{W}$ vector represents
$w_{i}(\boldsymbol{x})$. So, the total learnable parameters of the policy are
$\boldsymbol{\theta}=\\{\boldsymbol{A}_{1},\dots,\boldsymbol{A}_{N},\boldsymbol{\psi}\\}$.
It is easy to see that since each $\boldsymbol{A}_{i}$ is a simple matrix, and
$\boldsymbol{\psi}$ parameters of a neural network, the whole policy is fully
differentiable.

One can also add the attractor point, $\boldsymbol{x}^{*}_{c}$, to the
optimization variables. The policy would still be differentiable
($\boldsymbol{x}^{*}_{c}$ is a free parameter). In our experiments, we
observed that in IL/LfD scenarios, that would require a complicated loss
function, and thus we left this exploration for future work. In this paper, we
assume a fixed attractor that is equal to the average of the last points of
all the demonstrated trajectories.

The last element is to be able to optimize the parameters
$\boldsymbol{\theta}$ given some objective function, while respecting the
constraints defined in Eq. 4. In the general case, this would require a
constrained optimization problem to be performed, but this can be challenging
to do for high-dimensional parameter spaces, such as the ones generated by
neural networks. In order to bypass this issue but still respect the
constraints, we perform the following steps:

  * •

First, each $w_{i}$ should be positive. We can easily generate positive
numbers by adding an $exp$ layer after the last layer of $\Psi$. In this work,
we always use a _softmax_ layer as the last layer of $\Psi$ that generates
positive values that sum to one; it also makes more sense as we want to
combine the elementary DSs that $\boldsymbol{A}_{i}$ define.

  * •

We, now, need to satisfy the constraint
$\boldsymbol{A}_{i}+\boldsymbol{A}_{i}^{T}\succ 0$. If we assume real matrices
and define
$\boldsymbol{A}_{i}=\boldsymbol{B}_{i}+\boldsymbol{C}_{i}-\boldsymbol{C}_{i}^{T}$,
where $\boldsymbol{B}_{i}$ is a symmetric positive definite matrix (no
restrictions for $\boldsymbol{C}_{i}$), we can see that
$\boldsymbol{A}_{i}+\boldsymbol{A}_{i}^{T}=\boldsymbol{B}_{i}+\boldsymbol{C}_{i}-\boldsymbol{C}_{i}^{T}+\boldsymbol{B}_{i}+\boldsymbol{C}_{i}^{T}-\boldsymbol{C}_{i}=2\boldsymbol{B}_{i}\succ
0$. $\boldsymbol{B}_{i}$ is symmetric, thus
$\boldsymbol{B}_{i}=\boldsymbol{B}_{i}^{T}$, and
$\boldsymbol{C}_{i}-\boldsymbol{C}_{i}^{T}$ defines a skew symmetric matrix.
This gives us the ability to freely optimize for the parameters of
$\boldsymbol{C}_{i}$. So, we are left with handling the case of optimizing for
a symmetric positive definite matrix, $\boldsymbol{B}_{i}$.

  * •

If we assume real matrices, a symmetric positive definite matrix
$\boldsymbol{B}_{i}$ can be factorized as
$\boldsymbol{B}_{i}=\boldsymbol{L}_{i}\boldsymbol{L}_{i}^{T}$ (Cholesky
decomposition), where $\boldsymbol{L}_{i}$ is a lower triangular matrix with
real and positive diagonal entries. It is easy to see that we can optimize for
the parameters of $\boldsymbol{L}_{i}$ and reconstruct $\boldsymbol{B}_{i}$
that we need.

Using the above steps we can now perform unconstrained optimization while
still ensuring that the constraints in Eq. 4 are fulfilled. This is important
as we are more confident that the optimization will converge to good
solutions.

##  V Experiments

Figure 2: Multi-task scenario with image inputs. All tasks are learned with a
single model that can distinguish between tasks given an image input.

In this paper, we focus on IL/LfD scenarios. Through the conducted
experiments, we attempt to answer the following questions:

  1. 1.

Do ANDPs produce stable behaviors? How well can they reproduce the initial
demonstrations?

  2. 2.

Can ANDPs learn complex movements for a realistic robotic task? Are they
robust?

  3. 3.

Can ANDPs accept arbitrary inputs like 3D orientations? Can they accept even
raw images?

  4. 4.

Can ANDPs work on a physical robot?

In order to answer the first three questions, we devise a multi-task scenario
where the goal is for ANDPs to learn multiple tasks into one policy; we use
the DART open-source simulator [25]. The idea is to use the non-controllable
part of the state $\boldsymbol{x}_{nc}$ to ”define” which task we want the
robot to perform. So for each task, $\boldsymbol{x}_{nc}$ is an image captured
with a camera that is mounted to the robot’s end-effector and points directly
to a sign that displays the picture that corresponds to the particular
movement. We also test the reactiveness of ANDPs by changing the image in the
middle of the evaluation pipeline, and the robustness of the learned policies
by inserting force perturbations.

In order to answer the fourth question, we devise the following experiment:
_We use a physical Franka Panda robot to collect three demonstrations with
kinesthetic guidance for a pouring task and learn a policy with data collected
from a physical setup._ In this task the robot needs to pour liquid from one
cup into a bowl and we control the robot in end-effector space with changing
orientation.

###  V-A Multi-Task Learning

In this section, we want to determine whether ANDPs have the capability of
learning intricate 3D motions, demonstrate the flexibility of ANDPs compared
to traditional LfD methods, and exhibit the reactive and resilient nature of
the learned policy against perturbations. We collect one demonstration for
each of the following movements: a sinusoidal motion, a linear motion, and a
curvilinear motion, so that we can devise a multi-task scenario where the goal
is for ANDPS to learn multiple tasks into one policy. In essence, we use the
non-controllable part of the state to ”define” which task we want the robot to
perform. In order to create the labels, we simulate a sign with the image
corresponding to every motion across the robot, we then attach a camera to the
end-effector of the arm facing towards the sign and we shoot a grayscale image
for every sample. We take all 3 demonstrations and we have a state of the
form:
$\boldsymbol{x}=\\{\boldsymbol{x}_{nc},\boldsymbol{x}_{c}\\}=\\{\mathcal{I},x,y\\}$,
where $\mathcal{I}\in\mathbb{R}^{64\times 64}$ is a grayscale image. We use a
Convolutional Neural Network (CNN) to model the weight function $\Psi$; in
particular, we use a LeNet [26] variation. We learn one model for all three
tasks. In Fig. 2, we see that ANDPs are able to learn to distinguish the three
tasks while always ensuring convergence to the fixed attractor. Moreover, the
learned policy is reactive and robust to perturbations. To showcase the
broader concept of reactiveness we start an evaluation run with the image
corresponding to the linear movement displayed, at $t=1s$ we switch the
displayed image to the one representing the sinusoidal movement. We observe
that the robot changed its motion to follow the shape of the corresponding
movement (Fig. 3).

Figure 3: Reactiveness of ANDPs on changes in the non-controllable part of the
state, we switch from the line image to the sine image at t=$1s$.

To show that ANDPs are robust and reactive to force perturbations we apply an
external force to the robot twice during the execution: once at the beginning
of the behavior, and once at $t=5\,s$. We observe that the robot is able to
converge to the attractor and follow the overall shape of the behavior (Fig.
4).

Figure 4: Reactiveness of ANDPs on external force perturbations we apply an
external force twice, one at $t=0s$ and $t=5s$.

###  V-B Physical Robot Experiment

In this section, we want to identify whether ANDPs: (a) work with realistic
demonstrations, and (b) can learn a task that requires precision and end-
effector orientation control. For those reasons, we collect three
demonstrations with kinesthetic guidance on the physical robot performing a
pouring task: the robot holds a cup filled with liquid and needs to pour it
inside a bowl (Fig. 5). For safety, we “emulate” the liquid with small plastic
objects. We then learn a policy with ANDPs using the collected demonstrations
with a state of the form
$\boldsymbol{x}\equiv\boldsymbol{x}_{c}=\\{x,y,z,r_{x},r_{y},r_{z}\\}$, where
$\\{x,y,z\\}$ is the end-effector translation and $\\{r_{x},r_{y},r_{z}\\}$ is
the end-effector orientation expressed in Euler XYZ angles.

Figure 5:  Collecting pouring task demonstrations via kinesthetic guidance on
the Franka Emika Panda robot.

The results showcase that ANDPs work reliably in this setting and the robot
successfully pours the liquid from the cup to the bowl (Fig. 7). In order to
validate more thoroughly the effectiveness of the learned policy, we perform
_10 replicates with different initial configurations_ of the robot and measure
_the percentage of the plastic objects that end up inside the bowl_ (Fig. 6
(a)). We get a median percentage of $100\%$ with $67.5\%$ and $100\%$ for the
25-th and 75-th percentiles respectively (Fig. 6 (b)).

Figure 6: Percentage of objects that ended up inside the bowl on the 10
replications of the pouring task.

Figure 7: From left to right, screenshots of a successful trial of the pouring
task in the physical setting.

##  VI Results and Conclusions

ANDPs are one of the first policy structures for robot learning that are
general purpose while ensuring asymptotic stability of the produced behaviors
(at least for the controllable part, i.e., the robot). Using ANDPs we were
able to learn many different tasks with different action space
parameterizations and different input types. Although we performed experiments
only in IL/LfD scenarios, ANDPs are fully differentiable and generic policies
and thus can also be used in pure RL settings. We will explore this property
of ANDPs in future work.

Another important feature of ANDPs is their inherit explainability. Since the
underlying policy is a sum of elementary linear DSs, one can examine the ANDPs
via more classical tools for understanding the reasoning of the policy behind
its decisions. We aim at investigating this in detail in future work.

The main limitation of ANDPs’ current formulation is the need for having a
fixed attractor (even if the attractor is “learned”, it is still a fixed
attractor, that is, it does not move throughout the episode/experience). This
has two important consequences: (a) it might be difficult for the policy to
learn long-horizon complicated tasks, and (b) we need to find a more
complicated optimization scheme in order to relax the constraints for the
elementary DSs and allow non-monotonic motions (i.e., motions that “go away”
from the attractor). In future work, we aim at exploring the possibility of
having a moving attractor while keeping the stability properties.

Finally, although we provided interesting results with image inputs, we aim at
performing extensive experiments with different tasks to further validate the
effectiveness of ANDPs in these settings.

## Acknowledgments

Konstantinos Chatzilygeroudis was supported by the Hellenic Foundation for
Research and Innovation (H.F.R.I.) under the “3rd Call for H.F.R.I. Research
Projects to support Post-Doctoral Researchers” (Project Acronym: NOSALRO,
Project Number: 7541). Dimitrios Kanoulas and Valerio Modugno were supported
by the UKRI Future Leaders Fellowship [MR/V025333/1] (RoboHike).

## References

  * [1] P. Varin, L. Grossman, and S. Kuindersma, “A comparison of action spaces for learning manipulation tasks,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 6015–6021.
  * [2] K. Chatzilygeroudis, V. Vassiliades, F. Stulp, S. Calinon, and J.-B. Mouret, “A survey on policy search algorithms for learning robot controllers in a handful of trials,” _IEEE Transactions on Robotics_ , 2019.
  * [3] R. Martín-Martín, M. A. Lee, R. Gardner, S. Savarese, J. Bohg, and A. Garg, “Variable impedance control in end-effector space: An action space for reinforcement learning in contact-rich tasks,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 1010–1017.
  * [4] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press Cambridge, 1998\.
  * [5] A. Rajeswaran, V. Kumar, A. Gupta, G. Vezzani, J. Schulman, E. Todorov, and S. Levine, “Learning Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrations,” in _Proceedings of Robotics: Science and Systems (RSS)_ , 2018.
  * [6] A. Billard, S. Calinon, R. Dillmann, and S. Schaal, “Robot programming by demonstration,” in _Springer handbook of robotics_. Springer, 2008, pp. 1371–1394.
  * [7] S. M. Khansari-Zadeh and A. Billard, “Learning stable nonlinear dynamical systems with gaussian mixture models,” _IEEE Transactions on Robotics_ , vol. 27, no. 5, pp. 943–957, 2011.
  * [8] F. Stulp and O. Sigaud, “Robot skill learning: From reinforcement learning to evolution strategies,” _Paladyn, Journal of Behavioral Robotics_ , vol. 4, no. 1, pp. 49–61, 2013.
  * [9] S. Schaal, “Dynamic movement primitives-a framework for motor control in humans and humanoid robotics,” in _Adaptive motion of animals and machines_. Springer, 2006, pp. 261–280.
  * [10] A. J. Ijspeert, J. Nakanishi, H. Hoffmann, P. Pastor, and S. Schaal, “Dynamical movement primitives: learning attractor models for motor behaviors,” _Neural computation_ , vol. 25, no. 2, pp. 328–373, 2013.
  * [11] F. Khadivar, I. Lauzana, and A. Billard, “Learning dynamical systems with bifurcations,” _Robotics and Autonomous Systems_ , vol. 136, p. 103700, 2021\.
  * [12] A. Ude, A. Gams, T. Asfour, and J. Morimoto, “Task-specific generalization of discrete and periodic dynamic movement primitives,” _IEEE Transactions on Robotics_ , vol. 26, no. 5, pp. 800–815, 2010.
  * [13] A. Ude, B. Nemec, J. Morimoto _et al._ , “Trajectory representation by nonlinear scaling of dynamic movement primitives,” in _IROS_ , 2016.
  * [14] A. J. Ijspeert, J. Nakanishi, and S. Schaal, “Learning attractor landscapes for learning motor primitives,” in _NIPS_ , 2003.
  * [15] N. Figueroa and A. Billard, “A physically-consistent bayesian non-parametric mixture model for dynamical system learning.” in _CoRL_ , 2018, pp. 927–946.
  * [16] W. Amanhoud, M. Khoramshahi, and A. Billard, “A dynamical system approach to motion and force generation in contact tasks.” Robotics: Science and Systems (RSS), 2019.
  * [17] S. Bahl, M. Mukadam, A. Gupta, and D. Pathak, “Neural dynamic policies for end-to-end sensorimotor learning,” in _NeurIPS_ , 2020.
  * [18] S. Bahl, A. Gupta, and D. Pathak, “Hierarchical neural dynamic policies,” in _RSS_ , 2021.
  * [19] P. Fidelman and P. Stone, “Learning ball acquisition on a physical robot,” in _2004 International Symposium on Robotics and Automation (ISRA)_ , 2004, p. 6.
  * [20] F. Stulp, G. Raiola _et al._ , “Learning Compact Parameterized Skills with a Single Regression,” in _Humanoids_ , 2013.
  * [21] F. Guenter, M. Hersch, S. Calinon, and A. Billard, “Reinforcement learning for imitating constrained reaching movements,” _Advanced Robotics_ , vol. 21, pp. 1521–1544, 2007.
  * [22] Y. Shavit, N. Figueroa, S. S. M. Salehian, and A. Billard, “Learning augmented joint-space task-oriented dynamical systems: a linear parameter varying and synergetic control approach,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 2718–2725, 2018.
  * [23] N. Figueroa, S. Faraji, M. Koptev, and A. Billard, “A dynamical system approach for adaptive grasping, navigation and co-manipulation with humanoid robots,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 7676–7682.
  * [24] T. Osa, J. Pajarinen, G. Neumann, J. A. Bagnell, P. Abbeel, J. Peters _et al._ , “An algorithmic perspective on imitation learning,” _Foundations and Trends® in Robotics_ , vol. 7, no. 1-2, pp. 1–179, 2018.
  * [25] J. Lee, M. X. Grey, S. Ha, T. Kunz, S. Jain, Y. Ye, S. S. Srinivasa, M. Stilman, and C. K. Liu, “Dart: Dynamic animation and robotics toolkit,” _Journal of Open Source Software_ , vol. 3, no. 22, p. 500, 2018.
  * [26] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel, “Backpropagation applied to handwritten zip code recognition,” _Neural computation_ , vol. 1, no. 4, pp. 541–551, 1989.