#  Machine Learning-based Low Overhead Congestion Control Algorithm for
Industrial NoCs

Shruti Yadav Narayana1, Sumit K. Mandal2, Raid Ayoub3, Michael Kishinevsky3,
Umit Y. Ogras1
1Dept. of ECE, University of Wisconsin-Madison; 2Dept. of CSA, Indian
Institute of Science, Bangalore, India;
3Intel Corporation, Hillsboro, OR

###### Abstract

Network-on-Chip (NoC) congestion builds up during heavy traffic load and
cripples the system performance by stalling the cores. Moreover, congestion
leads to wasted link bandwidth due to blocked buffers and bouncing packets.
Existing approaches throttle the cores after congestion is detected, reducing
efficiency and wasting line bandwidth unnecessarily. In contrast, we propose a
lightweight machine learning-based technique that helps predict congestion in
the network. Specifically, our proposed technique collects the features
related to traffic at each destination. Then, it labels the features using a
novel time reversal approach. The labeled data is used to design a low
overhead and an explainable decision tree model used at runtime congestion
control. Experimental evaluations with synthetic and real traffic on
industrial 6$\times$6 NoC show that the proposed approach increases fairness
and memory read bandwidth by up to 114% with respect to existing congestion
control technique while incurring less than 0.01% of overhead.

##  I Introduction

Systems-on-chip (SoCs) with multi-core processors use networks-on-chip (NoCs)
for fast and energy-efficient communication between the processing elements.
NoCs consist of three main components: 1) routers, 2) links, and 3) queues for
storing the packets. Buffered NoCs, such as those with wormhole routing, store
the flits that make up the packets in intermediate routers [1]. In contrast,
bufferless NoCs, commonly used in industrial processors, store the packets
only at the endpoints, i.e., in the egress queues of the traffic sources and
ingress queues of the destinations. Under heavy traffic, i.e., when the rate
of incoming packets is high, finite size queues fill up and apply
backpressure. NoCs implement backpressure mechanisms to prevent packet losses.
For example, when the ingress queues at the destination are full, the buffered
NoCs stall the packet and propagate the backpressure upstream. In contrast,
bufferless industrial NoCs deflect the packets to one of the available output
ports. Hence, the deflected packets use NoC resources until they return to the
deflection point [2]. In either case, the backpressure eventually propagates
all the way back to the traffic sources (i.e., the cores) and prevents them
from injecting new packets into the NoC. As a result, the throughput (the
number of packets processed per unit time) decreases, and the overall
performance of the SoC deteriorates.

To address the congestion problem, researchers have proposed congestion
control mechanisms for industrial NoCs [3]. This technique monitors the queue
occupancy at the sinks. If the queue occupancy exceeds a predetermined
threshold, a distress on signal is sent to the sources. The source then stops
sending packets until it receives a distress off signal, which is triggered
after queue occupancy drops below a certain threshold.

Figure 1: Percentage of miss packets with state-of-the-art congestion control
technique. The traffic is generated with 50% LLC miss rate (shown in red
dashed line). However, the percentage of miss packets decreases to 7% at the
highest injection rate which is extremely unfair to miss traffic.

This mechanism reduces the NoC congestion and limits the packet latency in the
NoC. However, the resulting throughput is lower under a heavier workload.
Moreover, the mechanism is not fair towards the requests that experience a
miss in the shared last level cache (LLC). For example, Figure 1 shows the
percentage of traffic with LLC miss as a function of the traffic injection
rate. The percentage of requests with LLC miss denotes the proportion of the
requests fetched from the memory controller. In this experiment, we generate
synthetic traffic that will result in 50% (the dotted line on the figure) LLC
miss rate. At low traffic loads, the observed percentage of LLC miss rate is
50%, as expected. However, the percentage of completed transactions with LLC
misses drops as the traffic intensity increases and becomes as low as 7% when
the network becomes heavily congested. Similar unfairness happens also at
other LLC miss rates. In addition, static techniques depend on the
predetermined threshold that does not change with the workload, while reactive
techniques act after congestion happens [4, 5]. Hence, they do not maintain
the throughput of the NoC under heavy traffic.

The goal of this work is twofold. First, it aims to maximize and sustain the
memory read/write bandwidth provided to the processing cores. Achieving this
goal ensures that the cores use the NoC bandwidth effectively and that their
performance does not degrade with NoC congestion. Second, it aims to maximize
the fairness between the LLC hit and miss traffic. Without this goal, the
requests with an LLC miss experience starvation (as demonstrated in Figure 1)
since they have much longer delays than those with LLC hit. We propose a
proactive congestion control (a.k.a., source throttling) technique to achieve
these goals. The first step of the proposed approach is a supervised learning
framework enabled by a novel design of experiments and time reversal
techniques. The second step designs a lightweight decision tree using the data
from these experiments. This decision tree determines whether any given sink
node will likely experience congestion or not (before the queue is blocked).
Finally, the decision tree is used at runtime to control the traffic sources,
i.e., the cores. If a sink is likely congested, the cores stop sending new
requests to that sink until the congestion signal is cleared. Experimental
evaluations with synthetic and realistic traces show that the proposed
technique increases memory read bandwidth by up to 114% and the percentage of
missed traffic by up to 3.1$\times$ compared to a state-of-the-art congestion
control technique.

The major contributions of the work are as follows:

  * •

A novel time reversal approach and supervised learning to construct a decision
tree for NoC congestion control,

  * •

End-to-end congestion control algorithm for industrial NoCs,

  * •

Thorough experimental evaluations showing up to 114% higher memory read
bandwidth than a state-of-the-art technique with less than 0.01% of overhead.

The rest of this paper is organized as follows. Prior work related to
congestion control in NoC are discussed in Section II. We review the
background of the work in Section III. The proposed technique is described in
detail in Section IV. The experimental results are presented in Section V.
Finally, Section VI concludes the paper.

##  II Related Work

Existing NoC congestion control techniques can be broadly classified as 1)
Global and 2) Local. The global congestion control techniques assess the
congestion status of the whole network. Depending on the congestion status,
the packet injection rates of all the sources are regulated [6, 7, 1]. In
contrast, local congestion control techniques monitor the congestion at each
node [3, 8, 5, 4]. State-of-the-art industrial NoCs monitor the ingress queue
sizes of each node [3, 8]. If the size exceeds a certain threshold, then the
injection of packets from all the sources is stopped. The packet injection
resumes when the occupancies of all the queues drop below another
predetermined threshold. With this technique, congestion at any of the ingress
queues leads to throttling at all sources, leading to conservative behavior.
Authors in [5] propose a fine-grained source throttling method for NoCs with
mesh topology. In this work, the routers which are most affected by congestion
are identified. Then, these routers are used to estimate the NoC congestion
status. A heterogeneous congestion criterion for 2D mesh-NoC is proposed in
[4]. When NoC congestion occurs in a node, the packets whose trajectory is
through the congested node are stalled in the source. However, all the
congestion control techniques described above are reactive i.e., the
congestion criteria kicks in only after the congestion physically occurs in
the NoC.

Proactive congestion control techniques for NoCs are proposed in [9, 10]. The
technique proposed in [9] estimates the availability of the neighboring router
through analytical expression. When a traffic source observes that the input
port connected to it does not have availability then it does not send the
packets. Authors in [10] propose an artificial neural network (ANN)-based
global admission controller for NoC. In this work, the admission controller
slows down the injection rate from the sources by factor determined by the
ANN. The aforementioned techniques are applicable to an NoC where the packets
can wait at each router on its path. However, industrial NoCs are priority
aware and incorporates deflection routing where the packets already injected
in the NoC can never stop. Therefore, existing proactive congestion controls
techniques are not applicable to industrial NoCs.

In contrast, we propose a proactive congestion control technique to increase
memory read/write bandwidth and to improve the fairness between LLC hit and
miss traffic for industrial NoCs with deflection routing. To the best of our
knowledge, this is the first proactive congestion control technique proposed
for industrial NoCs with deflection routing.

##  III System Architecture and Background

Figure 2: A representative 4$\times$4 mesh-NoC with deflection routing.

###  III-A NoCs with Deflection Routing

This work targets NoCs used in high-end servers and state-of-the-art many core
architectures [8]. Figure 2 shows a 4$\times$4 mesh NoC architecture, each
column of which is also used in client systems, such as Intel i7 processors
[11]. Hence, the proposed congestion control technique is applicable to a wide
range of priority-aware industrial NoCs, where the packets already in the
network have higher priority than the packets waiting in the egress queues of
the sources. Assume that Node 11 in Figure 2 sends a packet to Node 1
following Y-X routing (highlighted by thick blue arrows). Deflection in
priority-aware NoCs happens when the queue at the turning point (Node 3) or
final destination (Node 1) becomes full. This can happen if the receiving
node, such as a cache controller, cannot process the packets fast enough. The
probability of observing a full queue increases with smaller queues (needed to
save area) and heavy traffic load from the cores. If the packet is deflected
at the destination node, it circulates within the same row (the red thin
arrows), as shown in Figure 2. Consequently, a combination of regular and
deflected traffic can load the corresponding row and pressure the queue at the
turning point (Node 3). This, in turn, can lead to deflection on the column
which propagates the congestion towards the source wasting useful NoC
bandwidth.

###  III-B Background on Cache Coherency Flow

This work assumes a local L1/L2 cache at each node, a distributed LLC, and
non-inclusive MESI-like cache-coherency flow [12]. If a request from a core is
not present in L1 or L2 cache, the request is sent to LLC. If the request is
present in the LLC, then the corresponding data is returned from LLC to the
requesting core. If the request is not present in the LLC then the request is
forwarded to the memory controller. The corresponding data is fetched from the
memory controller and returned to the core. The proposed congestion control
technique is independent of the number of cores, LLC banks and on-chip memory
controllers.

##  IV ML-Based Proactive Source Throttling

###  IV-A Overview of the Approach

When packets in the NoC are deflected at the sink, they continue to use the
NoC bandwidth and aggravate congestion. Hence, the proposed runtime technique
works as follows:

  1. 1.

It monitors the congestion indicators, i.e., the features of our machine
learning (ML) model, at each sink queue and determines whether they are likely
to be blocked,

  2. 2.

If a given queue is likely to be blocked, it sets a congestion signal at that
sink. Otherwise, it clears the congestion signal.

  3. 3.

The sources check the congestion signal at the destination before sending a
new request. If the congestion signal is set, they throttle the corresponding
request and move on to the next request. The requests to the sinks with
congestion signal are delayed until the congestion signal is cleared.

We note that checking the congestion signal at the destination does not incur
any additional overhead compared to existing techniques [3, 2], since they
also incorporate similar mechanism. They also have a small ($\sim$ 10 cycles
in our case) deterministic delay when the distress information is carried by a
simple dedicated time-division-multiplexed channel.

The fundamental question is to determine when to throttle a source. Since the
network traffic dynamics are fast, time-dependent, and nonlinear, we need to
consider not only the current queue occupancies but also first and second
order factors that can lead to congestion. For example, consider an ingress
queue with depth 32. An occupancy of 16 packets may be safe if the current
input traffic rate is lower than the service rate and the level of burstiness
is low. Since the average occupancy is likely to be decreasing as time
progresses, the sources do not need to be throttled. In contrast, an occupancy
of 16 packets may be dangerous if the average occupancy is increasing.
Therefore, a holistic approach must consider all relevant features summarized
in Section IV-B. Moreover, determining the optimal criteria is non-trivial
even when all the features are available. Hence, the second component of the
proposed approach is to design a decision tree using an innovative data
collection and labelling technique presented in Section IV-C. Finally, the
last step is implementing the lightweight controller that uses the congestion
signals and local criteria to throttle the source (Section IV-D).

###  IV-B Features used for Supervised Learning

To construct the machine learning-based model, we first collect the dataset
required for training. The dataset consists of features ($\mathcal{F}$) listed
in Table I with corresponding labels ($\mathcal{L}$). Here
$\mathcal{F}=(f^{1},f^{2},...,f^{N})$, where $N$ is the number of features,
$f^{j}\in\mathbb{R}$, $1\leq j\leq N$ and $\mathcal{L}\in\\{0,1\\}$. The
features ($\mathcal{F}$) are sampled every time a packet arrives at the
ingress queue at the sink. If the queue is not full, the packet is written to
the queue. Otherwise, the packet bounces. Sampling the features in both
conditions (sink or bounce) enables us to monitor congestion accurately at
sink node.

To capture the features accurately, we compute exponentially weighted moving
average (EWMA) of each feature as:

$\bar{f}_{i}^{j}=\alpha f_{i}^{j}+(1-\alpha)\bar{f}_{i-1}^{j},~{}i>0,~{}1\leq
j\leq N$ (1)

In this equation, $\bar{f}_{i}^{j}$ denotes EWMA of the feature $f^{j}$ for
$i^{\mathrm{th}}$ packet, $f_{i}^{j}$ denotes the original value of the
feature $f^{j}$ (e.g. injection rate) and $\alpha$ is the degree of mixing
parameter ($0\leq\alpha\leq 1$). The value of $\alpha$ is tuned to track the
average accurate without a significant delay. The feature values are
smoothened over time by computing EWMA. We implemented EWMA computation in a
cycle-accurate industrial simulator. A five point derivative is computed for
the features involving gradient. We track all the features in Table I, which
are potentially useful for congestion control. Since data collection is an
offline process, the EWMA computation overheads are inconsequential. After
deploying the machine learning model, EWMA of only the selected features are
tracked at runtime.

TABLE I: List of features collected at each sink. Injection rate to the sink queue | Total injection rate (sunk + deflected)
---|---
| Co-eff. of variation of
---
the total traffic (sunk + deflected)
| Co-eff. of variation of inter-arrival
---
time of the traffic to the sink queue
Rate of deflected packets | Mean service time of the sink queue
| Co-eff. of variation of
---
deflected packet inter-arrival time
| Co-eff. of variation of
---
sink queue inter-departure time
Occupancy | Probability that the sink queue is full
Gradient of injection rate | Gradient of queue occupancy
| Gradient of total
---
(sunk + deflected) injection rate
Gradient of probability of sink being full

###  IV-C Training Data Collection and Decision Tree

Labeling the features: The collected features indicate the ingress queue and
NoC congestion state at sampling time. For example, the features will capture
if a sink queue is full and deflects a packet. However, one must throttle the
source before the queue becomes full, i.e., before the onset of congestion.
The main challenge is to know that a packet will bounce before it is even
injected into the network. Having this knowledge at runtime is impossible, but
we mitigate this challenge using a novel time reversal approach described
next. The generation time stamps of all the deflected packets are recorded
while sampling the features. If a packet is deflected at the sink, we know
that the source must have been throttled at the generation time of this
packet. This sense of time in our comprehensive simulation data enables us to
go back to the generation time of the deflected packet and label the collected
features around that time accordingly.

Figure 3 shows an illustrative example of our proposed time reversal approach
for labelling the features. Figure 3(a) shows the features sampled for six
packets arriving at the ingress queue. Along with the features, the timestamps
when the packets attempted to sink are also sampled (last column of the
table). Apart from sampling the features of the packets arriving at the
ingress queue, we also sample the generation timestamps of the deflected
packets. As shown in the Figure 3(b), there are two deflected packets –
$P_{4}$ and $P_{5}$. The generation timestamps ($d_{j}$ in Equation 2) when
they were injected from the source are 10 and 11 respectively. Next, we
compute a set of timestamps for each deflected packets (two in this case)
which are within 2 cycles of the injection timestamps. From $P_{4}$, we get
$\mathcal{S}_{4}=\\{8,9,10,11,12\\}$ and from $P_{5}$, we get
$\mathcal{S}_{5}=\\{9,10,11,12,13\\}$. If $t_{i}$ is the timestamp of the
packet $P_{i}$, where $1\leq i\leq 5$, then we label $P_{i}$ as 1 if
$t_{i}\in\mathcal{S}_{4}\cup\mathcal{S}_{5}$. If $d_{j}$ is the generation
timestamp of when the $j^{\mathrm{th}}$ deflected packet and $t_{i}$ is the
timestamp of the $i^{\mathrm{th}}$ packet arriving at the sink, in general we
label ($l_{i}$) the features of the $i^{\mathrm{th}}$ packet arriving at the
sink as:

$l_{i}=\begin{cases}1,&\text{if $(d_{j}-\Delta)\leq t_{i}\leq(d_{j}+\Delta)$
}\\\ 0,&\text{Otherwise}\end{cases}$ (2)

where $\Delta=2$ in this example. A label of 0 denotes that if the source
sends packet to that particular sink, then it will not result in congestion. A
label of 1 denotes that if the source sends packet to that particular sink,
then it will result in congestion. Therefore, all the features with timestamp
within the range of $\Delta$ ($\Delta>0$) of $d_{i}$ are labelled as 1. In
other words, features within a range of $\Delta$ timestamps from the same
timestamp as the generation timestamp of the deflected packets are labelled as
1. The features of the packets with label of 1 are highlighted in Figure 3(c).

Figure 3: An illustrative example of our proposed time reversal approach to
label the features.

Supervised Learning: We can employ any supervised learning algorithm to create
a model which can take congestion control decision. In this work, we choose
binary decision tree since decision tree incurs low hardware overhead
(detailed in Section V-F). The output of the decision tree is either 0 or 1.
An output of 0 denotes that cores can send packet without congesting the NoC.
An output of 1 denotes that there is a possibility of congestion in the near
future and cores should stop injecting packets in the NoC. We observe that the
decision tree obtained through supervised learning supports our idea of
proactive congestion control. For an example, the decision tree returns an
output of 1 if both the occupancy of the sink is high and the gradient of
injection rate to the sink is positive.

###  IV-D Local Source Control

Each source (e.g., the CPU cores) has controller in the NoC interface. The
controller checks the congestion signal from the decision tree at each sink.
Due to deflection routing, the sources which are located at the boundary of
floorplan (e.g., Node-1, 5, 9, 13 in Figure 2) have highest priority.
Therefore, packets sent from these sources do not compete with the packets
waiting at other sources with lower priority. Hence, the sources with highest
priority can inject freely and cause congestion. In addition to the sink
nodes, a local condition at sources with highest priority can also proactively
hint future congestion. Therefore, we also implement a local condition for the
sources with the highest priority. Let $N$ be the current occupancy of the
destination sink, and $N_{T}$ be the target occupancy. According to Little’s
law, $\lambda\times t_{avg}$ more packet can be written to the queue, where
$\lambda$ is the injection rate to the ingress and $t_{avg}$ is the average
time between two source throttling decisions [13]. Hence, the traffic source
is throttled if $N+\lambda t_{avg}>N_{T}$, i.e., the queue can become full.

1 Input: Absolute value of the features, mixing parameter ($\alpha$), size of
the sink queue ($N$), target occupancy ($N_{T}$)

2 Output: To throttle (1) or not to throttle the source (0)

3

4$L=LC(N_{T},N,\lambda)$

5 if  _L == 1_ then

6 return 1

7

8 end if

9else

10 $\bar{\mathcal{F}}\leftarrow$ EWMA of the features using Equation 1

11 $D=DT(\mathcal{\bar{\mathcal{F}}})$

12 return $D$

13

14 end if

Algorithm 1 End-to-end congestion control algorithm

Algorithm 1 shows the end-to-end algorithm for congestion control which
combines the decision from decision tree model and the local condition. The
input to the algorithm is the absolute value of the features, mixing parameter
($\alpha$), occupancy of the sink queue ($N$), and target occupancy ($N_{T}$).
First, the controller checks the local condition ($LC$). $LC$ always returns
false for the sources with lower priority. If the local condition’s output
($L$) is true, then the algorithm returns true. Otherwise, EWMA of the
features ($\bar{\mathcal{F}}$) are computed following Equation 1. Then, the
algorithm returns the output of the decision tree ($D$).

##  V Experimental Evaluations

###  V-A Experimental Setup

We use a cycle-accurate industrial NoC simulator to evaluate our proposed
approach on a 6$\times$6 mesh NoC with two memory controllers. The NoC
architecture is similar to the one used in recent industrial SoCs [3, 2]. Due
to classified nature of the simulator and architecture, we present normalized
values. Each simulation is run for 600k cycles (with a warm-up period of 100k)
to reach steady-state values. The experiments consider a non-inclusive MESI-
like cache-coherency protocol [12] with varying traffic and last-level cache
(LLC) hit rates.

###  V-B Accuracy of Decision Tree

We perform simulations for LLC hit rate of 0.5 with different injection rates.
The smoothing parameter ($\alpha$ in Equation 1) is set as $\frac{1}{16}$ and
$\Delta$ (in Equation 2) is 5. The entire dataset is divided into 70% training
data and 30% validation. Table II shows the accuracy of predicting label-0 and
label-1 for the validation data with decision trees having different depths.
As a reminder, label-0 denotes that if the sources inject packets, it will not
lead to congestion and vice-versa. Therefore, if the labeled feature is 0 and
the predicted label is 1, the decision tree will unnecessarily stop the cores
from injecting packets. This scenario might be okay since it will not lead to
congestion. However, if the labeled feature is 1 and the predicted label is 0,
the core will still inject packets when it should have stopped. This
misprediction will lead to congestion in NoC. Therefore, the accuracy of
predicting label-1 is more important than the accuracy of predicting label-0.
We observe that the decision tree with depth 4 has the highest accuracy in
predicting label-1. The decision tree with a depth lower than 4 has lower
prediction accuracy for label-0 and label-1, while a deeper decision tree has
a lower accuracy for label-1 due to overfitting. Therefore, we choose the
decision tree with depth 4 for evaluation. We note that, the decision tree for
each sink is trained offline (once) and the same decision tree is used for
congestion control with any incoming workload.

TABLE II: Accuracy(%) of decision trees with different depths. Decision tree of depth 4 is chosen based on the accuracy. | Decision tree depth
---|---
2 | 3 | 4 | 5 | 6 | 7 | 8
Label-0 | 93.3 | 93.2 | 93.7 | 94.9 | 96.1 | 96.2 | 96.5
Label-1 | 95.9 | 97.4 | 97.6 | 97.5 | 96.3 | 95.6 | 94.8

###  V-C Comparison of Average Transaction Latency

The primary goal of our congestion control technique is to reduce the number
of deflected packets so that there is no wastage of NoC bandwidth. We observe
that when no congestion control is enabled, the rate of deflected packets
increases with increasing injection rate. For example, with an injection rate
of 0.27 and LLC hit rate of 0.2, the average rate of deflected packets is
0.08. In this scenario, our proposed congestion control technique sees no
deflected packets. A reduced number of deflected packets reduces NoC
congestion, so packets experience lower wait time and average latency.

Figure 4 shows the comparison of average transaction latency for varying
injection rates with LLC hit rate of 70%. The comparison is between the
congestion control technique used in state-of-the-art industrial NoC [3] and
our proposed approach. The average transaction latency denotes the round trip
latency from the generation of a read/write request to its completion. In the
state-of-the-art congestion control technique, if the occupancy of the sink
exceeds a predetermined value, the sources are throttled. The sources restart
injecting packets in the NoC if the sink occupancy becomes lower than another
predetermined value. Therefore, the state-of-the-art control technique is
reactive. In contrast, our proposed congestion control technique predicts
congestion and provides a proactive decision to throttle the sources. As a
result, compared to the reactive state-of-the-art, our proposed proactive
congestion control technique throttles at the onset of congestion in NoC,
without wasting memory read bandwidth. From figure 4 it is observed that the
proposed congestion control technique reduces the average transaction latency
by up to 30% compared to the state-of-the-art approach. We also observe a
similar improvement in average transaction latency for other LLC hit rates.
For example, the proposed technique improves the average transaction latency
by 7% for an LLC hit rate of 0.2 on average.

Figure 4: Comparison of average transaction latency for 70% hit rate. Lower
transaction latency indicates less congestion.

###  V-D Comparison of Percentage of LLC Miss

This section compares the percentage of requests with LLC miss between the
state-of-the-art congestion control technique and our proposed technique. The
percentage of requests with LLC miss denotes the proportion of the requests
fetched from the memory controller. Since our proposed technique reduces NoC
congestion, more requests with LLC miss are allowed to be fetched from the
memory controller. Therefore, our proposed technique consistently results in a
higher percentage of requests with LLC miss, as shown in Figure 5 compared to
the state-of-the-art congestion control technique. In this case, the synthetic
traffic is generated with a 70% hit rate, i.e., ideally, 30% of the traffic
should be miss traffic. We observe that at a lower injection rate, both
techniques result in 30% of requests with LLC miss since there is no
congestion in the NoC. With the increasing injection rate, the percentage of
requests with LLC miss reduces. However, our proposed congestion control
technique shows up to 3.1$\times$ improvement in the percentage of requests
with LLC miss at the higher injection rate. We also observe similar LLC miss
percentage improvement for other LLC hit rates. For example, the proposed
technique improves the LLC miss percentage by 1.2$\times$ for LLC hit rate of
0.2. Therefore, the proposed technique is fairer towards the requests with LLC
miss than the state-of-the-art technique.

Figure 5: Comparison of percentage of LLC miss for 70% LLC hit rate (30% LLC
miss). Higher percentage of LLC miss indicates that the congestion control
technique is more fair towards the miss traffic. Figure 6: Comparison of
memory read bandwidth for 20% LLC hit rate. Higher memory read bandwidth
indicates less NoC congestion. Figure 7: Comparison of average bytes received
per core for 70% LLC hit rate.

###  V-E Comparison of Memory Read Bandwidth

This section compares the memory read bandwidth achieved by the state-of-the-
art approach and our technique. Memory read bandwidth measures the average
number of requests fetched from the memory controller in case of a cache miss.
The percentage of missed packets with our proposed congestion control
technique also significantly increases the memory read bandwidth. Figure 5
shows the 70% LLC hit rate comparison between state-of-the-art and proposed
techniques. Both techniques result in equal memory read bandwidth at lower
injection rates. However, with increasing injection rate, the memory read
bandwidth decreases significantly with a state-of-the-art congestion control
technique. Our proposed congestion control technique keeps the memory read
bandwidth at a certain level, even at a higher injection rate. The highest
improvement seen in memory read bandwidth is 190%. On average, the proposed
technique achieves a 64% improvement in memory read bandwidth compared to
state-of-the-art methods.

Transactions with an LLC miss take significantly longer than those with an LLC
hit due to off-chip memory access. Therefore, the requests with LLC miss stay
longer in the queue, reducing the total volume of data received per core
(Bytes/core). However, our technique reduces congestion in the NoC and hence
total volume of data received per core does not decrease drastically despite
substantial increase in memory read bandwidth. Figure 7 shows that our
proposed approach results in slight (4% on average) reduction in average bytes
received per core although it completes 3.1$\times$ more transactions with LLC
miss.

Figure 8: Memory read bandwidth comparison with realistic workloads.

Results with varying injection rates: So far, we have shown the results when
the cores inject with a fixed injection rate for the entire duration. However,
real applications may have different phases, and in each phase, cores may
inject at different injection rates. Therefore, we also perform experiments
with synthetic workloads having different injection rates. Specifically, in
each workload, we consider four different injection rates. Figure 8 shows the
comparison of memory read bandwidth for ten such workloads executing with 70%
hit rate. Our proposed congestion control technique achieves up to 114%
improvement in memory read bandwidth compared to the state-of-the-art method.
On average, the proposed congestion control technique shows a 106% improvement
in memory read bandwidth for these realistic workloads.

###  V-F Hardware Overhead Analysis

We implemented the RTL for the local condition at all sources and the feature
computation as well as the decision tree at all ingress of the NoC. Then, we
synthesized the RTL using Synopsys Design Compiler with 45 nm technology from
TSMC. To have a fair comparison, we scaled the area and power values to 14 nm
technology (using the technique described in [14]) since the state-of-the-art
SkyLake SoC is fabricated with 14nm [3]. We observe that our proposed
congestion control technique consumes only 0.01 mm2 of area and 2.2 mW of
power. The total area of SkyLake SoC is 694 mm2 and it consumes power in the
order of 10W [3, 15]. Hence, our proposed technique incurs negligible overhead
(less than 0.01%) both in area and power. Therefore, the technique results in
significant reduction of NoC congestion with negligible hardware overhead.

##  VI Conclusion and Future Work

State-of-the-art NoC congestion control techniques are reactive, i.e., can
detect NoC congestion only after it occurs. This paper proposes a supervised
learning framework along with a time reversal technique to construct a
lightweight decision tree. This decision tree proactively determines whether
any given sink node will likely experience congestion or not (before the queue
is blocked). Experimental evaluation shows that the proposed congestion
control technique achieves up to 114% improvement in memory read bandwidth for
realistic workloads while incurring less than 0.01% of overhead.

## References

  * [1] Radu Marculescu, Umit Y Ogras, Li-Shiuan Peh, Natalie Enright Jerger, and Yatin Hoskote.  Outstanding research problems in noc design: system, microarchitecture, and circuit perspectives.  IEEE Trans. on Computer-Aided Design of Integrated Circ. and Syst., 28(1):3–21, 2008.
  * [2] Jack Doweck et al.  Inside 6th-generation Intel Core: New Microarchitecture Code-named Skylake.  IEEE Micro, (2):52–62, 2017.
  * [3] Simon M Tam et al.  SkyLake-SP: A 14nm 28-Core Xeon® Processor.  In 2018 IEEE ISSCC, pages 34–36, 2018.
  * [4] Reza Akbar and Farshad Safaei.  A Novel Heterogeneous Congestion Criterion for Mesh-based Networks-on-Chip.  Microprocessors and Microsystems, 84, 2021.
  * [5] Hongzhi Zhao, Nader Bagherzadeh, Qiang Wang, and Yongchang Wang.  A Fine-Grained Source-Throttling Method for Mesh Architectures.  IEEE Access, 8:33101–33112, 2020.
  * [6] Raj Jain, K Ramakrishnan, and Dah-Ming Chiu.  Congestion Avoidance in Computer Networks with a Connectionless Network Layer.  arXiv preprint, 1998.
  * [7] A-H Smai and L-E Thorelli.  Global Reactive Congestion Control in Multicomputer Networks.  In Proc. Fifth International Conf. on High Perform. Comput. (Cat. No. 98EX238), pages 179–186. IEEE, 1998.
  * [8] James Jeffers, James Reinders, and Avinash Sodani.  Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition.  Morgan Kaufmann, 2016.
  * [9] Umit Y Ogras and Radu Marculescu.  Prediction-based Flow Control for Network-on-Chip Traffic.  In Proceedings of the 43rd annual design automation conference, pages 839–844, 2006.
  * [10] Boqian Wang, Zhonghai Lu, and Shenggang Chen.  ANN Based Admission Control for on-chip Networks.  In 2019 56th ACM/IEEE Design Automation Conference (DAC), pages 1–6, 2019.
  * [11] Efraim Rotem.  Intel Architecture, Code Name Skylake Deep Dive: A New Architecture to Manage Power Performance and Energy Efficiency.  In Intel Developer Forum, 2015.
  * [12] Mark S Papamarcos and Janak H Patel.  A Low-overhead Coherence Solution for Multiprocessors with Private Cache Memories.  In Proceedings of the 11th annual international symposium on Computer architecture, pages 348–354, 1984.
  * [13] John DC Little.  A Proof for the Queuing Formula: L= $\lambda$ W.  Operations research, 9(3):383–387, 1961.
  * [14] Satyabrata Sarangi and Bevan Baas.  DeepScaleTool: A Tool for the Accurate Estimation of Technology Scaling in the Deep-submicron Era.  In 2021 IEEE ISCAS, pages 1–5, 2021.
  * [15] WikiChip LLC.  Skylake (server) - microarchitectures - intel.  https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(server), accessed 22 Sept 2022.


# Analysis of Knowledge Tracing performance on synthesised student data

Panagiotis Pagonis Corresponding Author. Email<EMAIL_ADDRESS>Kai
Hartung  Di Wu  Munir Georges  Sören Gröttrup  Technische Hochschule
Ingolstadt, Germany  Intel Labs, Germany

###### Abstract

Knowledge Tracing (KT) aims to predict the future performance of students by
tracking the development of their knowledge states. Despite all the recent
progress made in this field, the application of KT models in education systems
is still restricted from the data perspectives: 1) limited access to real life
data due to data protection concerns, 2) lack of diversity in public datasets,
3) noises in benchmark datasets such as duplicate records. To resolve these
problems, we simulated student data with three statistical strategies based on
public datasets and tested their performance on two KT baselines. While we
observe only minor performance improvement with additional synthetic data, our
work shows that using only synthetic data for training can lead to similar
performance as real data.

##  1 Introduction

In recent years, the education has experienced the transformation from
traditional classrooms into digital teaching [11]. Especially the COVID-19
pandemic remarkably accelerated the adaption of remote learning and encouraged
the development of AI-enhanced educational technology. Intelligent tutoring
systems (ITS) are widely applied in providing personalized instruction and
tutoring for students with computer-assisted learning environments, which
offer intelligent services that assist the knowledge acquisition process and
increase motivation. However, online education still faces the challenges of
improving learner engagement and adapting educational contents to different
users. As a sequence modeling technique, Knowledge Tracing (KT) models
dynamically keep track of students’ knowledge states and predict their future
performance on following exercises. This has been proven to be valuable in
supporting instructors with better teaching strategy design and creating
personalised study plans in accordance with learner’s diverse learning styles
[16].

As a student modeling technique, the KT task aims to observe and capture the
changes in students’ knowledge states during learning. Given series of
questions, the learning process is represented through the results,
corresponding skills and interaction data, like response time, attempts, or
skills, of each question answering activity between the ITS and the learners.
A large amount of efforts has been made to study this problem. Bayesian
Knowledge Tracing (BKT) [4] is the most classic approach, which applies Hidden
Markov Models (HMM) to predict probabilities of the binary variable of each
step. In its earlier versions, this method assumes that studied knowledge will
never be forgotten and ignores the individual differences of students’
prerequisite knowledge, and therefore has led to the emergence of multiple
varieties, see [12, 25]. With the rise of neural networks, Deep Knowledge
Tracing (DKT) [22] introduced recurrent neural networks as a stronger
sequential feature extractor, which outperformed previous approaches. New DKT
models began to be proposed to capture different aspects of the cognitive
development process, see, for example, [10, 15, 19].

Though, a lot of efforts have been made to improve the prediction accuracy on
student grades, with most KT models focusing on binary grade prediction and
only care if a student passed or failed an exercise, see [1, 5, 14, 17, 20,
22]. Additionally, most common public datasets like Assistments [9, 21], Junyi
[2] or EdNet [3] also provide data with only binary grades of exercises. In
practical application, however, exercises with grades on some kind of scale
beyond just 0 and 1 are quite common. So, the lack of more diverse data
sources is significant in this area. Furthermore, currently available public
KT datasets are collected from diversed learning scenarios, which present
distinctively different features and scales, resulting in a difficulty of
practical adaption. On one hand, the benchmark datasets often contain noise
(e.g. wrong timestamps or null values), formatting issues (e.g. gaps between
experiment setups, datasets, and versions), and incorrect descriptions.
Furthermore, strict data protection regulations often challenge the
researchers during the data collection. Despite of the trending of digital
learning, the use of learning analytic tools are strictly limited and many
developers, like in the European Union, do not have access to anonymized
student data [8]. It is worth noting that the majority work focuses on
modeling the learning process instead of solving the mentioned problems from a
data perspective. As a result, conducting knowledge tracing in real education
could be very expensive.

Seeking solutions for the lack of variety and expensive data in KT, we focus
our efforts in synthesizing data on continuous or ordinal scales and test
their performance on two baselines (see Section 4) by adding synthesized data
of different ratio to the original datasets. We accordingly chose two public
datasets for our experiments which do record grades on such scales, the Open
University Learning Analytics dataset (OULAD) [13], and the SLP dataset [24].

| OULAD | SLP
---|---|---
students | 32,593 | 4,830
exercises | 37,443 | 7,502
total interactions | 10,655,280 | 460,688
Table 1: Size statistics of the OULAD [13] and SLP [24] datasets

Both datasets contain interaction data from online learning environments. The
size description can be found in Table 1. OULAD gives grades ranging from 0 to
100 for each exercise and SLP gives ordinal grades with the range depending on
each exercise. To be able to treat the datasets equally, we normalize all
grades in terms of percentage to a range from 0 to 100.

In the following section, we describe our approaches to generate synthetic
data. In Section 3 and 4, we describe the KT baselines and the experiments
using the corresponding models on the synthetic data. Section 5 and 6 are
dedicated to the discussion and conclusion of our findings.

##  2 Synthetic Data Generator

The most crucial parameter in the educational datasets is the students’
grades. We designed three different methods to generate grades, which are
introduced in this section: Generator1 is based on the distribution of grades,
Generator2 performs resampling in each step of the student learning path, the
sequence of grades from one student, and Generator3 reuses the existing
students. When examining the datasets for the generator creation, we exclude
grades 0 and 100 to avoid a dominant influence from those two values.

###  2.1 Generator1

Synthetic Data Generator1 generates new grades by sampling from one
distribution of all grades in the dataset. So, we first identify the best
fitting distribution to the grades in the real data. We did so using the
’distfit’ package in python [23], which comprises nearly all common univariate
distributions.

Specifically, in the OULAD dataset the best fitting distribution to the grades
is a log-gamma distribution with parameters: $c=0.50,$ $scale=8.20,$
$location=89.02$, see Figure 1.

By drawing grades from this distribution, we create the single interaction
instances for the synthetic dataset.

Figure 1: Fitted log-gamma distribution of grades (curve) compared to
distribution of all grades (histogram) for the OULAD dataset.

The real and the simulated grades datasets have a similar distributions, as
visualized in Figure 3. Additionally, both datasets have a similar average
(real: $73.02$, simulated: $73.14$) and median (real: $77$, simulated:
$76.98$) grade, as well as standard deviation (real: $17.49$, simulated:
$17.67$).

In the SLP dataset, the distribution that explains the grades best is a beta
distribution with parameters: $a=2.46,$ $b=2.89,$ $scale=92.62,$
$location=4.38$. As shown in Figure 2, the selected distribution is not
optimal. It should be mentioned that there is not always a perfect fit of
distributions.

Figure 2: Fitted beta distribution of grades (curve) compared to the
distribution of all grades (histogram) for the SLP dataset.

The average (real: $53.16$, simulated: $73.17$) and the median (real: $50.00$,
simulated: $77.03$) are different, but the standard deviation (real: $18.48$,
simulated: $17.17$) is still similar, which is shown in Figure 3.

Figure 3: Boxplot of real and synthetic grade distribution using Generator1
for OULAD and SLP dataset.

Apart from the basic descriptive statistics one more parameter that should be
taken into account, is the possible dependency on the previous grade. In
Generator1 this dependency is not taken into account. The development of a
function that takes into account the current attempt of a student and the
distribution of grades at that point should give very reliable results.
However, this needs a lot of data which radically increases the complexity.
Generator1 can be considered as the baseline for our next attempts to provide
a powerful and reliable method for synthetic datasets.

###  2.2 Generator2

Another approach to generate synthetic educational data is to perform a
resampling from the actual dataset. This idea is inspired by bootstrap
resampling for estimating parameters of a dataset [6, 7]. Usually,
bootstrapping is used to estimate the variance or, in general, the
distribution of a statistic of a population such as the mean or variance.
However, directly applying this concept would not produce realistic grades.
Thus, we don’t do any actual parameter estimation, but only use the approach
to collect samples.

First, we randomly collect the whole learning path of a user, which is the
sequence of grades this student got during its study. Then, for each step in
this learning path, we randomly pick a value out of the grades over all
students at the same step from the real data. Thus, this method does not cover
progressive dependencies between the subsequent time steps. Afterwards we add
some Gaussian noise, with parameters $\mu=0,\sigma=3$, to create the new
grade. This process is repeated until all grades in every step of the learning
path are filled. This new synthetic dataset has similar properties and a
similar grade distribution to the real one. The advantage of this method is
the construction of the dataset based on real data and considering each step.
Using as input for the Generator2 the OULAD dataset, the results are
encouraging. A comparison to the descriptive statistics of real and generated
data proves that efficiency. More specifically, the average (real: $73.02$,
simulated: $74.43$), the median (real: $77.00$, simulated: $77.74$) and the
standard deviation (real: $17.49$, simulated: $16.81$) do not differ much.
These comparisons is visualized in Figure 4.

Moreover, in the SLP dataset the similarities in the main metrics average
(real: $53.16$, simulated: $55.11$), median (real: $50.00$, simulated:
$54.79$) and standard deviation (real: $18.48$, simulated: $18.05$) remain,
but the first quartile (real: $33.33$, simulated: $42.61$) differs slightly.
Those results can be found in Figure 4.

Figure 4: Boxplot of real and synthetic grade distribution using Generator2
for OULAD and SLP dataset.

There are no limits in the dataset size, thus any source with numeric grades
may work without issues. A possible drawback of this method is the time of
generation, which can be high depending on the requested amount of data.

###  2.3 Generator3

The third version of the Synthetic Data Generator or Generator3 utilises a
simpler and the more lightweight approach. This method chooses a random user
from the real dataset and collects their whole learning path. Then, Gaussian
noise is added to the grades, here with parameters $\mu=0,\sigma=3$. The
procedure continues until the requested amount of data is fulfilled. The
method offers a quick generation of any amount of data which preserves the
properties of the real data, as well as the possible time dependency between
grades and correlations. Those are not the only advantages of the Generator3,
but also it could be easily modified and used for any dataset. Even if the
data are reused, it offers anonymity and generated users could be considered
as completely new entries.

For the evaluation of the algorithm the same two datasets are used. A
comparison between real and simulated data follows for both datasets as well
as some basic statistics. In the OULAD dataset the descriptive statistics of
real and generated datasets are almost identical. The difference for the
average (real: $73.01$, simulated: $73.03$), the median (real: $77.00$,
simulated: $77.68$) and the standard deviation (real: $17.48$, simulated:
$17.70$) are almost equal to 0 as can be seen in Figure 5. The method has
similar results on the SPL dataset, which are also shown in Figure 5. Here,
the average (real: $76.89$, simulated: $73.03$), the median (real: $50.00$,
simulated: $51.96$) and the standard deviation (real: $18.47$, simulated:
$18.70$) are once again very similar. In particular, the OULAD generated
dataset follows a beta distribution with parameters $a=25.70$, $b=2.37$,
$scale=343.82$, $location=-241.75$, which is very close to the log-gamma
observed for the original dataset, but more smoothed out. The SLP follows a
beta distribution with parameters $a=3.37$, $b=2.98$, $scale=100.73$,
$location=-0.68$.

Figure 5: Boxplot of real and synthetic grade distribution using Generator3
for OULAD and SLP dataset.

In addition, one more proof for the efficiency of that method is that the
distributions of the generated data follow similar but smoother distributions
as the real data (see Figure 6).

Figure 6: Comparison of the distributions of grades of real data and data
generated from Generator3.

##  3 Knowledge Tracing

We compare two approaches to Knowledge Tracing. The original Deep Knowledge
Tracing (DKT) [22] uses an recurrent neural network architecture, which takes
a sequence of binary grades of one student as input and gives a prediction on
whether the next exercise will be passed or failed as output. We adapt this
architecture to the non-binary grades of our datasets. Instead of cross-
entropy loss we apply mean-squared-error as loss, comparing the networks
logits scaled by a sigmoid function with the grades normalized to the range
$[0,1]$.

Bayesian Knowledge Tracing (BKT), as implemented by Badrinath et al. in [1],
uses hidden Markov models optimized via expectation maximization. We are
running the default BKT model as offered by the library with the additon of
the forget parameter.

##  4 Experiments

For both datasets, we compare the influence of adding synthetic data to real
training data as augmentation, as well as the performance of the Knowledge
Tracing model on real data when trained on synthetic data only. The test data
is the same 20% split of the full real data for all experiments on one
dataset.

Of the 80% training data split, we compare KT performance when training on 0%,
50%, and 100% of that split respectively. For each of these variants we
further compare performance when adding synthesized data of a size equal to
0%, 25%, 50%, 75%, 100%, 200% and 300% of the original training split. Thus we
get a grid of real and synthetic data ratios on which to train the KT models
and for which to compare the result. This results in two variations for each
dataset without synthetic data, and 18 more variations for each dataset and
generator version.

###  4.1 Evaluation

We evaluate the KT models on three metrics, Accuracy (ACC), Matthews-
Correlation-Coefficient[18] (MCC) and Mean Absolute Error (MAE). MAE serves to
asses the Model Performance with respect to the continuous nature of the
scores in the datasets we chose to focus on. ACC evaluates the classic binary
prediction of passed or failed and MCC should give an impression on how
balanced the model predictions are. For both classification scores, we treat a
normalized score above 0.5 as class 1 (passed) and a score below as class 0
(failed). We don’t use the ordinal grades of the SLP dataset as categories as
they do not provide consistent classes across the dataset.

###  4.2 Results

Generator1 mainly worsens the model performance of DKT on the OULAD dataset to
a small degree when added to real training data. When using only synthetic
data, the MAE is worse than when training on any amount of real data, however
only by 3-4 points, see left graph in Figure 7. On the other hand, when
looking at the MCC in Table 3, the synthetic data stays well below the real
data. On the SLP dataset adding synthetic data from Generator1 has less of a
negative effect, but when using synthetic data only the MAE is further away
from the baseline of real data than on OULAD, see Figure 8 and Table 5.

Figure 7: OULAD Dataset: Influence of synthetic data on Deep Knowledge Tracing performance in MAE. Lower values are better. Figure 8: SLP Dataset: Influence of synthetic data on Deep Knowledge Tracing performance in MAE. Lower values are better. Figure 9: SLP Dataset: Influence of synthetic data on Bayesian Knowledge Tracing performance in MAE. Lower values are better. | 0 | 0.25 | 0.5 | 0.75 | 1 | 2 | 3
---|---|---|---|---|---|---|---
Generator1
0.0 |  | 0.906 | 0.91 | 0.91 | 0.91 | 0.911 | 0.911
0.5 | 0.92 | 0.918 | 0.919 | 0.918 | 0.917 | 0.917 | 0.918
1.0 | 0.919 | 0.921 | 0.919 | 0.919 | 0.917 | 0.918 | 0.91
Generator2
0.0 |  | 0.898 | 0.909 | 0.892 | 0.911 | 0.896 | 0.911
0.5 | 0.92 | 0.92 | 0.919 | 0.918 | 0.918 | 0.918 | 0.918
1.0 | 0.919 | 0.921 | 0.921 | 0.92 | 0.919 | 0.92 | 0.919
Generator3
0.0 |  | 0.912 | 0.915 | 0.91 | 0.915 | 0.913 | 0.909
0.5 | 0.92 | 0.919 | 0.914 | 0.911 | 0.915 | 0.908 | 0.907
1.0 | 0.919 | 0.92 | 0.914 | 0.914 | 0.915 | 0.911 | 0.909
Table 2: DKT ACC per data combination on the OULAD dataset. Rows stand for real data ratio, columns for synthetic data ratio. Best values per real data ratio are highlighted. | 0 | 0.25 | 0.5 | 0.75 | 1 | 2 | 3
---|---|---|---|---|---|---|---
Generator1
0.0 |  | -0.003 | 0.0 | 0.0 | 0.0003 | 0.0 | 0.0
0.5 | 0.356 | 0.339 | 0.336 | 0.307 | 0.326 | 0.265 | 0.36
1.0 | 0.385 | 0.36 | 0.329 | 0.342 | 0.335 | 0.3 | 0.328
Generator2
0.0 |  | 0.004 | -0.004 | -0.019 | 0.0 | -0.007 | 0.0
0.5 | 0.356 | 0.349 | 0.359 | 0.354 | 0.323 | 0.324 | 0.313
1.0 | 0.385 | 0.381 | 0.376 | 0.376 | 0.338 | 0.33 | 0.333
Generator3
0.0 |  | 0.344 | 0.347 | 0.344 | 0.359 | 0.361 | 0.335
0.5 | 0.356 | 0.374 | 0.367 | 0.35 | 0.367 | 0.329 | 0.337
1.0 | 0.385 | 0.39 | 0.371 | 0.359 | 0.368 | 0.354 | 0.34
Table 3: DKT MCC per data combination on the OULAD dataset. Rows stand for real data ratio, columns for synthetic data ratio. Best values per real data ratio are highlighted. | 0 | 0.25 | 0.5 | 0.75 | 1 | 2 | 3
---|---|---|---|---|---|---|---
Generator1
0.0 |  | 0.489 | 0.468 | 0.493 | 0.468 | 0.467 | 0.467
0.5 | 0.706 | 0.69 | 0.695 | 0.693 | 0.689 | 0.692 | 0.692
1.0 | 0.7 | 0.703 | 0.699 | 0.702 | 0.702 | 0.702 | 0.703
Generator2
0.0 |  | 0.503 | 0.499 | 0.502 | 0.504 | 0.506 | 0.691
0.5 | 0.706 | 0.682 | 0.665 | 0.669 | 0.698 | 0.674 | 0.675
1.0 | 0.7 | 0.78 | 0.692 | 0.713 | 0.7 | 0.707 | 0.705
Generator3
0.0 |  | 0.662 | 0.692 | 0.692 | 0.698 | 0.696 | 0.69
0.5 | 0.706 | 0.702 | 0.698 | 0.697 | 0.706 | 0.695 | 0.695
1.0 | 0.7 | 0.709 | 0.707 | 0.707 | 0.704 | 0.705 | 0.704
Table 4: DKT ACC per data combination on the SLP dataset. Rows stand for real data ratio, columns for synthetic data ratio. Best values per real data ratio are highlighted. | 0 | 0.25 | 0.5 | 0.75 | 1 | 2 | 3
---|---|---|---|---|---|---|---
Generator1
0.0 |  | -0.04 | 0.04 | -0.05 | 0.017 | 0.004 | 0.001
0.5 | 0.412 | 0.381 | 0.389 | 0.384 | 0.383 | 0.385 | 0.385
1.0 | 0.397 | 0.409 | 0.403 | 0.404 | 0.403 | 0.408 | 0.409
Generator2
0.0 |  | 0.011 | 0.002 | 0.005 | 0.01 | 0.012 | 0.38
0.5 | 0.412 | 0.369 | 0.329 | 0.395 | 0.393 | 0.348 | 0.351
1.0 | 0.397 | 0.559 | 0.385 | 0.431 | 0.401 | 0.412 | 0.409
Generator3
0.0 |  | 0.324 | 0.38 | 0.381 | 0.395 | 0.39 | 0.38
0.5 | 0.412 | 0.402 | 0.396 | 0.394 | 0.412 | 0.391 | 0.389
1.0 | 0.397 | 0.417 | 0.415 | 0.413 | 0.407 | 0.409 | 0.407
Table 5: DKT MCC per data combination on the SLP dataset. Rows stand for real
data ratio, columns for synthetic data ratio. Best values per real data ratio
are highlighted.

Generator2 shows mostly similar results for both datasets as Generator1, with
the one exception. Here, we can observe that using a synthetic data ratio of 3
without real data achieves results comparable to using real data only, see
Figure 7 and 8. This observation is also confirmed for ACC and MCC in Table 4
and 5.

For Generator3, it can be seen that adding a smaller amount of synthetic data
to the real data tends to slightly improve the MAE on OULAD and on SLP, see
Figure 7 and 8, as well as MCC and ACC as can be seen in tables 2-5. But,
adding more than 25-50% of the real training set size worsens the model on the
OULAD data set. Using the synthetic data only shows to cause a test
performance on par with using a lower amount of real data for both datasets.

| MAE | MCC | ACC
---|---|---|---
>0.1 | 0.09 | 0 | 0.91
0.1 | 0.09 | 0 | 0.91
0.01 | 0.159 | -0.006 | 0.841
Table 6: BKT results on the OULAD dataset. Rows stand for real data ratio. Synthetic data ratio is 0 for all entries in the column. | 0 | 0.25 | 0.5 | 0.75 | 1 | 2 | 3
---|---|---|---|---|---|---|---
Generator1
0.0 |  | 0.103 | 0.103 | 0.103 | 0.103 | 0.103 | 0.103
0.5 | 0.896 | 0.889 | 0.862 | 0.805 | 0.739 | 0.24 | 0.106
1.0 | 0.897 | 0.895 | 0.89 | 0.881 | 0.863 | 0.733 | 0.51
Generator2
0.0 |  | 0.897 | 0.897 | 0.897 | 0.897 | 0.897 | 0.897
0.5 | 0.896 | 0.896 | 0.896 | 0.897 | 0.897 | 0.897 | 0.897
1.0 | 0.897 | 0.987 | 0.897 | 0.897 | 0.897 | 0.897 | 0.897
Generator3
0.0 |  | 0.896 | 0.896 | 0.896 | 0.896 | 0.897 | 0.897
0.5 | 0.896 | 0.896 | 0.896 | 0.896 | 0.896 | 0.897 | 0.897
1.0 | 0.897 | 0.897 | 0.897 | 0.897 | 0.897 | 0.897 | 0.897
Table 7: BKT ACC per data combination on the SLP dataset. Rows stand for real data ratio, columns for synthetic data ratio. Best values per real data ratio are highlighted. | 0 | 0.25 | 0.5 | 0.75 | 1 | 2 | 3
---|---|---|---|---|---|---|---
Generator1
0.0 |  | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
0.5 | -0.001 | -0.001 | 0.009 | 0.005 | 0.005 | -0.002 | -0.001
1.0 | -0.002 | -0.005 | 0.003 | 0.005 | 0.008 | 0.006 | 0.01
Generator2
0.0 |  | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
0.5 | -0.002 | 0.0 | 0.0 | -0.001 | -0.001 | -0.003 | 0.0
1.0 | -0.002 | -0.002 | -0.002 | -0.002 | -0.001 | 0.0 | 0.0
Generator3
0.0 |  | 0.0 | 0.002 | 0.0 | -0.002 | -0.002 | 0.0
0.5 | -0.002 | 0.0 | 0.0 | 0.0 | -0.003 | -0.002 | 0.001
1.0 | -0.002 | -0.002 | -0.002 | -0.003 | -0.003 | -0.002 | -0.003
Table 8: BKT MCC per data combination on the SLP dataset. Rows stand for real
data ratio, columns for synthetic data ratio. Best values per real data ratio
are highlighted.

The BKT on the OULAD dataset appears completely uninfluenced by the addition
or substraction of data on the above scales. Here each variation including the
baseline achieves an MAE of 0.09, an ACC of 0.91, and an MCC of 0. To test, if
smaller fractions of real data make a difference, we also include a run on 10%
and 1% of the real dataset and the results in Table 6 show that only a small
ratio of 1% causes a change in the results.

On the SLP dataset, an effect can be seen using Generator1, see Figure 9, as
well as Table 7 and 8. These show that the performance on synthetic data does
not come close to that on real data and adding the synthetic data to the real
one consistently worsens. For the other Generators however, the results look
much more like for the OULAD dataset, as different data ratios show
essentially no effect.

##  5 Discussion

Regarding the general grade distribution, all three Generators come close to
the real data, as can be seen in figures 3 \- 6. However, using the generated
data for training KT models has little to no positive effect on the
performance. For Generator1 this likely lies in the fact that the synthetic
grades are sampled independently of each other and of any other context,
therefore not being able to represent a student actually going through a
number of exercises in sequence. Generator2 does include a dependence on the
time step, at which each exercise is taken. However, it still does not account
for the dependence of grades in a sequence on each other. Generator3
eventually samples full sequences and adapting those, leaving some degree of
dependency of the sampled grades intact. This is reflected in the fact, that
the performance of the DKT model trained on synthetic data only, is on par
with the baseline performance. Generator3 is also the only one for which we
can observe a slight improvement when adding synthetic data to the real one.

Another reason that the performance does not improve with the generated data
might lie in the skew of the datasets. Especially the OULAD dataset shows a
bias towards good grades, as can be seen in for example in Figure 3. And while
this is not the case for the SLP dataset, the same figure does also show that
the chosen distribution for this dataset does also result in a skew towards
positive grades. So adding this kind of data may cause the KT models to be
more biased towards positive grades, not being able to predict negative grades
in a more balanced test set.

The BKT does not appear to profit from the synthetic data at all. Here, even
the baselines for both datasets already show an MCC close to 0, so the model
seems already more biased towards the majority class. That may be a reason why
adding synthetic data to the model does not change anything in the OULAD
dataset.

##  6 Conclusion

Our Synthetic Data Generators have been shown to produce data with overall
distributions close to the real data. However just drawing from distributions
does not provide enough additional information for the KT models to be able to
improve performance using this data. But we could produce synthetic data close
enough to the real data to achieve KT performances close to the real data.

This gives hope that we can build on this work to achieve better synthetic
datasets in future work. Next steps could include adapting the sampling
approach from Generator3 to not be too close to sampling real data sequences.
Another step to build on this study might be to utilize the synthetic data
from more directed sampling to explicitly balance out biased datasets similar
to an oversampling approach.

This work is part of the project THISuccessAI under project number
FBM2020-EA-1690-07540 and has been funded by the Stiftung Innovation in der
Hochschullehre.

## References

  * [1] Anirudhan Badrinath, Frederic Wang, and Zachary Pardos, ‘pybkt: An accessible python library of bayesian knowledge tracing models’, in Proceedings of the 14th International Conference on Educational Data Mining, pp. 468–474, (2021).
  * [2] Haw-Shiuan Chang, Hwai-Jung Hsu, and Kuan-Ta Chen, ‘Modeling exercise relationships in e-learning: A unified approach’, in International Conference on Educational Data Mining (EDM), (2015).
  * [3] Youngduck Choi, Youngnam Lee, Dongmin Shin, Junghyun Cho, Seoyon Park, Seewoo Lee, Jineon Baek, Chan Bae, Byungsoo Kim, and Jaewe Heo.  Ednet: A large-scale hierarchical dataset in education, 2020.
  * [4] Albert T Corbett and John R Anderson, ‘Knowledge tracing: Modeling the acquisition of procedural knowledge’, User modeling and user-adapted interaction, 4, 253–278, (1994).
  * [5] Miao Dai, Jui-Long Hung, Xu Du, Hengtao Tang, and Hao Li, ‘Knowledge tracing: A review of available techniques.’, Journal of Educational Technology Development & Exchange, 14(2), (2021).
  * [6] Bradley Efron, ‘Estimating the error rate of a prediction rule: improvement on cross-validation’, Journal of the American statistical association, 78(382), 316–331, (1983).
  * [7] Bradley Efron and Robert Tibshirani, ‘Improvements on cross-validation: the 632+ bootstrap method’, Journal of the American Statistical Association, 92(438), 548–560, (1997).
  * [8] European Parliament and Council of the European Union.  Regulation (EU) 2016/679 of the European Parliament and of the Council.
  * [9] Mingyu Feng, Neil Heffernan, and Kenneth Koedinger, ‘Addressing the assessment challenge with an online system that tutors as it assesses’, User Modeling and User-Adapted Interaction, 19(3), 243–266, (August 2009).
  * [10] Aritra Ghosh, Neil Heffernan, and Andrew S Lan, ‘Context-aware attentive knowledge tracing’, in Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2330–2339, (2020).
  * [11] Jianhua Han, Wei Zhao, Qiang Jiang, Mohamed Oubibi, and Xiangen Hu, ‘Intelligent tutoring system trends 2006-2018: A literature review’, in 2019 Eighth International Conference on Educational Innovation through Technology (EITT), pp. 153–159, (2019).
  * [12] Tanja Käser, Severin Klingler, Alexander G Schwing, and Markus Gross, ‘Dynamic bayesian networks for student modeling’, IEEE Transactions on Learning Technologies, 10(4), 450–462, (2017).
  * [13] Jakub Kuzilek, Martin Hlosta, and Zdenek Zdrahal, ‘Open University Learning Analytics dataset’, Scientific Data, 4(1), 170171, (November 2017).
  * [14] Youngnam Lee, Youngduck Choi, Junghyun Cho, Alexander R. Fabbri, Hyunbin Loh, Chanyou Hwang, Yongku Lee, Sang-Wook Kim, and Dragomir Radev.  Creating A Neural Pedagogical Agent by Jointly Learning to Review and Assess, 2019.
  * [15] Qi Liu, Zhenya Huang, Yu Yin, Enhong Chen, Hui Xiong, Yu Su, and Guoping Hu, ‘Ekt: Exercise-aware knowledge tracing for student performance prediction’, IEEE Transactions on Knowledge and Data Engineering, 33(1), 100–115, (2019).
  * [16] Qi Liu, Shuanghong Shen, Zhenya Huang, Enhong Chen, and Yonghe Zheng, ‘A survey of knowledge tracing’, arXiv preprint arXiv:2105.15106, (2021).
  * [17] Yunfei Liu, Yang Yang, Xianyu Chen, Jian Shen, Haifeng Zhang, and Yong Yu.  Improving Knowledge Tracing via Pre-training Question Embeddings, 2020.
  * [18] B.W. Matthews, ‘Comparison of the predicted and observed secondary structure of t4 phage lysozyme’, Biochimica et Biophysica Acta (BBA) - Protein Structure, 405(2), 442–451, (1975).
  * [19] Hiromi Nakagawa, Yusuke Iwasawa, and Yutaka Matsuo, ‘Graph-based knowledge tracing: modeling student proficiency using graph neural network’, in IEEE/WIC/ACM International Conference on Web Intelligence, pp. 156–163, (2019).
  * [20] Shalini Pandey and George Karypis.  A Self-Attentive model for Knowledge Tracing, 2019.
  * [21] Zach A Pardos, Ryan S.J.D Baker, Maria San Pedro, Sujith M Gowda, and Supreeth M Gowda, ‘Affective States and State Tests: Investigating How Affect and Engagement during the School Year Predict End-of-Year Learning Outcomes’, Journal of Learning Analytics, 1(1), 107–128, (May 2014).
  * [22] Chris Piech, Jonathan Bassen, Jonathan Huang, Surya Ganguli, Mehran Sahami, Leonidas J Guibas, and Jascha Sohl-Dickstein, ‘Deep Knowledge Tracing’, in Advances in Neural Information Processing Systems, eds., C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, volume 28. Curran Associates, Inc., (2015).
  * [23] Erdogan Taskesen.  distfit is a python library for probability density fitting., March 2023.  If you use this software, please cite it using these metadata.
  * [24] Ziding Shen Penghe Chen Xiaoqing Li Shengquan Yu Yu Lu, Yang Pian, ‘SLP: A Multi-Dimensional and Consecutive Dataset from K-12 Education’, in 29th International Conference on Computers in Education (ICCE), (2021).
  * [25] Michael V Yudelson, Kenneth R Koedinger, and Geoffrey J Gordon, ‘Individualized bayesian knowledge tracing models’, in Artificial Intelligence in Education: 16th International Conference, AIED 2013, Memphis, TN, USA, July 9-13, 2013. Proceedings 16, pp. 171–180. Springer, (2013).