# Human-in-the-loop Handling of Knowledge Drift

Andrea Bontempelli1111Contact Author Fausto Giunchiglia1,2 Andrea Passerini1
Stefano Teso1
1University of Trento, Italy, 2Jilin University, Changchun, China
<EMAIL_ADDRESS>
###### Abstract

We introduce and study knowledge drift (KD), a complex form of drift that
occurs in hierarchical classification. Under KD the vocabulary of concepts,
their individual distributions, and the _is-a_ relations between them can all
change over time. The main challenge is that, since the ground-truth concept
hierarchy is unobserved, it is hard to tell apart different forms of KD. For
instance, introducing a new _is-a_ relation between two concepts might be
confused with individual changes to those concepts, but it is far from
equivalent. Failure to identify the right kind of KD compromises the concept
hierarchy used by the classifier, leading to systematic prediction errors. Our
key observation is that in many human-in-the-loop applications (like smart
personal assistants) the user knows whether and what kind of drift occurred
recently. Motivated by this, we introduce trckd, a novel approach that
combines _automated_ drift detection and adaptation with an _interactive_
stage in which the user is asked to disambiguate between different kinds of
KD. In addition, trckd implements a simple but effective knowledge-aware
adaptation strategy. Our simulations show that often a handful of queries to
the user are enough to substantially improve prediction performance on both
synthetic and realistic data.

##  1 Introduction

We are concerned with human-in-the-loop applications of hierarchical
classification under drift. In such applications, the concept hierarchy
embedded into the predictor might become obsolete over time [28]. Smart
personal assistants (PAs), for instance, often need to infer the location or
social context of their user from sensor data (e.g., GPS coordinates, nearby
Bluetooth devices), but the hierarchy of relevant places and people changes as
the user’s life changes [9]. Another example is protein function prediction,
in which annotations are structured according to the Gene Ontology, a resource
that is regularly updated to incorporate the latest discoveries [11]. We refer
to this as _knowledge drift_ (KD).

Classifiers that fail to adapt to KD may output wrong, ambiguous, or
irrelevant predictions. Standard approaches for learning under concept drift,
however, are insufficient for handling KD [8]. Indeed, KD subsumes but is
substantially more complex than concept drift, as it can affect the concept
hierarchy itself: both concepts and _is-a_ relations between them may appear,
disappear, and change.

The main challenge is how to reliably distinguish between different kinds of
KD. For instance, introducing an _is-a_ relation between two concepts leaves a
similar footprint on the data stream as changing their individual
distributions. However, confusing one for the other entails acquiring spurious
_is-a_ relations and hence systematically mis-predicting future instances.

Our key observation is that, in our human-in-the-loop setting, the user can
identify with little effort what kind of drift occurred, if any. Several
examples are given below. Motivated by this observation, we design trckd
(TRaCking Knowledge Drift), an approach that tackles KD by combining
_automated_ drift detection and adaptation with _interactive_ drift
disambiguation. At a high level, trckd detects possible KD by checking whether
the distribution of current and past examples have diverged using the maximum
mean discrepancy [10], and whenever it finds any drift it asks the user to
identify what changed. In order to facilitate this step, trckd supplies the
user with an initial guess and optionally with concrete examples in support of
the guess. Moreover, trckd implements a simple but effective knowledge-aware
adaptation strategy that we ground on top of $k$NN-based multi-label
classifiers [26]. Our experiments show that interactive drift disambiguation
and knowledge-aware adaptation are key for good performance under KD, and that
asking a handful of queries to the user is often enough to achieve substantial
performance improvements.

Figure 1:  Left: Decision surface and concept hierarchy of a classifier for
Ann’s social context that knows about five concepts: “ _P_ erson”, “ _B_ oss”,
“ _S_ ubordinate”, “ _D_ ave”, and “ _E_ arl”. Middle: Concept Drift: Dave
moves to a different office. As new examples are received, the decision
surface changes but the hierarchy remains the same. Right: Knowledge Drift:
Ann is promoted and “Dave” is now her subordinate. If the classifier knows
that the hierarchy changed, it can transfer examples from “Dave” to
“Subordinate”, quickly improving its performance.

#### Contributions:

Summarizing, we:

  1. 1.

Introduce knowledge drift and the related issue of drift disambiguation.

  2. 2.

Design trckd, an approach to KD in human-in-the-loop applications that
combines _automated_ detection and adaptation with _interactive_
disambiguation, and instantiate it on top of $k$NN-based approaches to concept
drift.

  3. 3.

Show experimentally that, thanks to knowledge-aware adaptation guided by few
user queries, trckd often outperforms its competitors on three data sets.

##  2 Preliminaries

We begin by introducing hierarchical classification under drift. Instances
$\bm{\mathrm{x}}$ belong to one or more concepts (_aka_ classes) organized in
a ground-truth hierarchy, a DAG in which nodes are concepts and edges encode
_is-a_ relations. Labels $\bm{\mathrm{y}}$ are indicator vectors: the $i$th
element of $\bm{\mathrm{y}}$, denoted $y^{i}$, is $1$ if $\bm{\mathrm{x}}$
belongs to the $i$th concept and $0$ otherwise.

######  Example.

Given observations $\bm{\mathrm{x}}$ (e.g., GPS coordinates and list of nearby
devices), Ann’s PA predicts that Ann is studying at the library with Bob.
Here, “Studying”, “Library”, and “Bob” are concepts, and the concept hierarchy
states, among other things, that “Bob” is a “Friend” and a “Person”.

The machine observes a stream of examples
$\bm{\mathrm{z}}_{t}=(\bm{\mathrm{x}}_{t},\bm{\mathrm{y}}_{t})$ drawn from a
ground-truth data distribution $P_{t}(\bm{\mathrm{X}},\bm{\mathrm{Y}})$. The
latter is always consistent with the ground-truth hierarchy: if the $j$th
concept _is-a_ specialization of the $i$th concept, then $y^{j}=1$ implies
$y^{i}=1$ (and conversely $y^{i}=0$ implies $y^{j}=0$). The machine’s goal is
to _learn a classifier that performs well on future instances_.222We assume
$\bm{\mathrm{y}}$ to be given for ease of exposition. In practical
applications, often $\bm{\mathrm{y}}$ has to be acquired using an active
learning step.

###  2.1 Knowledge Drift

What makes this setting challenging is that the ground-truth concept hierarchy
and the data distribution can both change over time $t$ and that neither of
them can be observed directly. This gives rise to a very general form of drift
that we denote _knowledge drift_ (KD).

In standard (i.e., non-hierarchical, closed world) settings, the only possible
forms of drift are _distribution shift_ , in which the prior distribution over
instances $P_{t}(\bm{\mathrm{X}})$ changes, and _individual concept drift_ ,
in which the conditional distribution of a single concept
$P_{t}(Y_{i}\,|\,\bm{\mathrm{X}})$ changes [8]. The term _concept drift_
captures both processes.

######  Example.

During the semester, Ann spends most of her time studying at the library. Once
the finals are over, Ann stops going to the library as often and while there
she is less likely to be studying. This affects the distribution of GPS
coordinates and that of activities conditioned on GPS coordinates.

Knowledge drift subsumes, but is more complex than, concept drift, as it can
affect the concept hierarchy itself. Four atomic types of drift to the
hierarchy can be defined: _concept addition_ , _concept removal_ , _relation
addition_ , and _relation removal_. Concept addition refers to the appearance
of new concepts and concept removal to the phasing out of obsolete concepts.
Relation addition and relation removal, on the other hand, refer to changes in
the structure of the hierarchy itself.

######  Example.

Concepts like “Friend” and “Library” are essentially immutable, but the
specific friends and libraries that matter to Ann (which are also concepts)
can change over time, e.g., when Ann graduates or moves abroad. In particular:
i) If Ann buys a vacation home, an unanticipated concept “Ann’s vacation home”
appears in the ground-truth hierarchy (concept addition). Conversely, if Ann’s
vacation home is sold, the corresponding concept is no longer meaningful and
disappears (concept removal). ii) If Ann receives a promotion and her old boss
Dave becomes her subordinate, then “Dave” moves from being a child of “Boss”
(relation removal) to being a child of “Subordinate” (relation addition).

###  2.2 Handling Knowledge Drift

Roughly speaking, handling concept drift involves two steps: _detecting_ drift
and _adapting_ the model accordingly [8]. Timely detection and adaptation are
a prerequisite for avoiding prediction mistakes, even more so in the
hierarchical case, where a single misaligned concept can compromise the
predictions of all related concepts.

Dealing with KD, however, requires the machine to maintain a copy of the
(unobserved) ground-truth concept hierarchy and to update it based on the
identified KD. Doing so involves one extra step: _drift disambiguation_. By
this we mean identifying what concepts and relations were affected by drift
and how. This step is critical, because different types of KD require
different types of adaptation and failure to disambiguate KD can induce a
mismatch between the ground-truth and the classifier’s hierarchies, leading to
systematic, cascading prediction errors [16].

Solving disambiguation is far from trivial. To see this, consider relation
addition. Like all other forms of KD, relation addition can only be identified
by its effects on the data distribution. Specifically, adding a relation
introduces a _correlation_ between the concepts appearing in the relation.
Naturally, the converse does not necessarily hold:

######  Example.

Ann is on a work trip and sleeps in her hotel room by herself. Hence, the
concepts “Sleeping” and “Alone” are highly correlated. Once Ann gets back
home, she no longer sleeps alone and the correlation drops dramatically.

This shows that logically independent concepts can be highly correlated. Now,
the machine has no sure way of telling apart relation addition from concept
drift, and might react by adding a spurious relation to its concept hierarchy.
It might take plenty of examples for the machine to correct its mistake, and
reliable examples are usually scarce in non-stationary settings like ours.
Relation removal works similarly.

Dealing with concept removal is also non-trivial: removing the $i$th concept
implies not only that it cannot occur (and should not be predicted) ever
again, but also that its child concepts are not longer attached to it.
Treating concept removal as concept drift makes it hard to force the
conditional distribution $P_{t}(Y_{i}\,|\bm{\mathrm{X}})$ to exactly zero and,
depending on the classifier being used, even doing so may not guarantee that
the deleted concept is not predicted when one of its children is.333The only
“easy” case is concept addition, which is straightforward in our fully labeled
setting and will not be considered further.

##  3 Handling Knowledge Drift with TRCKD

Our approach stems from the simple observation that in many human-in-the-loop
scenarios _the user can naturally disambiguate between different types of KD_.
Consider our running example: Ann is perfectly aware that the finals are not
yet over (so no drift occurred in this regard) and that her vacation home has
been recently sold (and hence that “vacation home” is no longer a valid
concept). It is therefore sensible to partially offload drift disambiguation
to the user.

To this end, we introduce trckd, a $k$NN-based approach for human-in-the-loop
hierarchical classification under KD that combines _automated_ detection and
adaptation with _interactive_ disambiguation. trckd detects drift using a
time-tested sliding-window approach [14] upgraded to hierarchical
classification. Most importantly, trckd introduces an new interactive drift
disambiguation step and a simple but effective knowledge-aware adaptation
strategy. Following the literature, we focus on multi-window $k$NN-based
classifiers [26], however the overall algorithm of can be adapted to more
complex models.

The pseudo-code of trckd is listed in Algorithm 1. The algorithm takes a data
set $S_{1}$ and a concept hierarchy compatible with it and uses them to train
an initial classifier. Then, in each iteration $t=1,2,\ldots$ the machine
receives a new example
$\bm{\mathrm{z}}_{t}=(\bm{\mathrm{x}}_{t},\bm{\mathrm{y}}_{t})$ and performs
three steps: 1) It detects whether KD occurred, 2) It cooperates with the user
to determine what concepts and relations were affected by KD, and 3) It adapts
the classifier and the machine’s concept hierarchy accordingly. We discuss
these three steps in turn.

#### Step 1: Detection.

trckd builds on the multi-label two-window detector of Spyromitros-Xioufis et
al. [26]. For every concept $i$ in the machine’s hierarchy, trckd maintains
two windows of examples:444In hierarchical classification, most examples do
not belong to most concepts. As in [26], trckd accounts for this by allocating
$2/3$ of each window for negatives. $W_{\text{cur}}^{i}$ holds the $w$ most
recent examples and is updated in each iteration, while $W_{\text{old}}^{i}$
holds $w$ reference (past) examples and is only updated when the $i$th concept
drifts. Whenever this happens, the contents of $W_{\text{old}}^{i}$ are
replaced with those of $W_{\text{cur}}^{i}$ and the latter is emptied.
Predictions are made using a standard $k$NN rule using only the examples in
the recent window. KD is detected whenever the measured difference between the
distributions of the recent and past windows of at least one concept is larger
than some threshold $\tau$.

trckd measures this difference using the _maximum mean discrepancy_ (MMD), a
well-known discrepancy employed in hypothesis testing [10] and domain
adaptation [30]. Letting $P$ and $Q$ be distributions over some space
$\mathcal{X}$ and $k$ a user-defined kernel over $\mathcal{X}$, the MMD
between $P$ and $Q$ relative to $k$ is:

$\text{MMD}(P,Q)^{2}=\mathbb{E}[k(\bm{\mathrm{a}},\bm{\mathrm{a}}^{\prime})]-2\mathbb{E}[k(\bm{\mathrm{a}},\bm{\mathrm{b}})]+\mathbb{E}[k(\bm{\mathrm{b}},\bm{\mathrm{b}}^{\prime})]$

where $\bm{\mathrm{a}}$, $\bm{\mathrm{a}}^{\prime}$ are drawn i.i.d. from $P$
and $\bm{\mathrm{b}}$, $\bm{\mathrm{b}}^{\prime}$ from $Q$. Estimating the MMD
between $W_{\text{old}}^{i}$ and $W_{\text{cur}}^{i}$ requires to define a
kernel between examples $\bm{\mathrm{z}}$. trckd achieves this by defining two
separate kernels over instances and labels $k_{X}$ and $k_{Y}$ and then taking
their tensor product [27]:
$k(\bm{\mathrm{z}},\bm{\mathrm{z}}^{\prime})=k((\bm{\mathrm{x}},y),(\bm{\mathrm{x}}^{\prime},y^{\prime}))=k_{X}(\bm{\mathrm{x}},\bm{\mathrm{x}}^{\prime})\cdot
k_{Y}(y,y^{\prime})$. The choice of base kernels is application-specific. In
our experiments, we employ a Gaussian kernel $k_{X}$ for the instances and a
delta kernel $k_{Y}(y,y^{\prime})=\mathbbm{1}\\!\left\\{y=y^{\prime}\right\\}$
for the labels.

The MMD has several advantages. First of all, if $P\equiv Q$ then necessarily
$\text{MMD}(P,Q)=0$.555If $k$ is characteristic, the converse also holds [29].
Unlike other theoretically well-behaved discrepancies (like total variation
distance and $\mathcal{A}$-distance [14]), the MMD can be estimated
efficiently (in linear or quadratic time, depending on the estimator) even for
higher-dimensional data [19, 21, 10]. Just as importantly, in our experiments
the MMD achieved better false detection rate than ME [13], a state-of-the-art
discrepancy with better discrimination power on paper.

Algorithm 1 The trckd algorithm. Inputs: $S_{1}$ is the initial data set,
$s:=|S_{1}|$, $w$ the window size, $\tau$ a threshold.
$\widehat{\mathrm{MMD}}$ is an empirical estimator of the MMD and
$\bm{\mathrm{z}}_{t}^{i}:=(\bm{\mathrm{x}}_{t},y_{t}^{i})$.

1:Fit initial classifier on $S_{1}$

2:for every concept $i$ in the machine’s hierarchy do

3:
$W_{\text{old}}^{i}\leftarrow\\{\bm{\mathrm{z}}_{s}^{i},\ldots,\bm{\mathrm{z}}_{s-w}^{i}\\}$

4:for $t=1,2,\ldots$ do

5: Receive new example $\bm{\mathrm{z}}_{t}$

6: for every concept $i$ in the machine’s hierarchy do

7:
$W_{\text{cur}}^{i}\leftarrow\\{\bm{\mathrm{z}}_{s+t}^{i},\bm{\mathrm{z}}_{s+t-1}^{i},\ldots,\bm{\mathrm{z}}_{s+t-w}^{i}\\}$

8: if $\exists
i\,:\,\widehat{\mathrm{MMD}}(W_{\text{cur}}^{i},W_{\text{old}}^{i})\geq\tau$
then

9: Illustrate detected KD to the user

10: Adapt based on user’s KD description

#### Step 2: Disambiguation.

Upon detecting drift, trckd initiates interaction with the user. Interaction
can be carried out through a simple UI akin to those used for designing
ontologies [12, 1]. The interface shows (part of) the machine’s concept
hierarchy and highlights the concepts that were identified by MMD. Notice that
this visual description of the detected drift is unstructured, in that it does
not disambiguate between different forms of atomic KD. In our running example,
the PA might highlight the concepts “Dave”, “Boss”, and “Subordinate”, thus
enabling Ann to focus her recent promotion and identify related changes. Of
course, the machine’s description of drift might be inaccurate or incomplete.
For this reason, trckd asks the user to correct it using the graphical
interface. Extra context can be supplied to the user by including a handful of
examples that summarize how the concepts affected by KD have changed. Such
examples can be selected from the past and current windows of those concepts
using MMD witness functions [17].

If the machine’s drift description is accurate enough (which should typically
be if the drift detector is tuned well) then the user’s jobs is simply to tell
the machine whether the relations between the highlighted concepts have
undergone drift and how. To this end, the user can deselect highlighted
concepts and add or remove arrows in the DAG. This is not particularly
cognitively demanding. If the machine’s description is not accurate, the user
can still easily deselect wrongly highlighted concepts. This is already an
improvement over no interaction. A sufficiently motivated and knowledgeable
user has also the option of editing any drifting concepts or relations not
detected by the machine. All of this extra information is useful for guiding
knowledge-aware adaptation.

#### Step 3: Adaptation.

Once it receives the user’s drift description, trckd adapts the machine’s
hierarchy and the windows accordingly. In particular: i) For every instance of
individual concept drift in the description, it empties the current window of
the affected concept and transfers its contents to the past window. ii) For
concept removal, the past and current windows of the affected are deleted and
any _is-a_ relations between the removed concept are deleted and its children
are attached to the parent. iii) For relation addition, the positive examples
belonging to the child concept are copied to the parent’s window and the
latter is doubled in size to cope. iv) For relation removal, the positive
examples belonging to the child concept are removed from the parent’s window
and the latter is shrank accordingly. The child concept is also linked
directly to its grand-parent. This strategy applies immediately to $k$NN-based
approaches and to other classifiers that support forgetting (i.e., removal of
training examples). Our experiments show that this simple form of knowledge-
aware adaptation strategies outperforms strategies based on adaptively
forgetting obsolete examples [26, 23].

|  |
---|---|---
|  |
Figure 2: Knowledge-aware versus other adaptation strategies. Left to right:
Results for HSTAGGER, EMNIST, and 20NG. Top row: relation addition. Bottom
row: relation removal. Plots for the other forms of KD can be found in the
Supplementary Material.

Figure 3: Interactive versus fully automated drift disambiguation. Left to right: concept removal, relation addition, and relation removal. Top: HSTAGGER. Bottom: EMNIST. The results for 20NG can be found in the Supplementary Material due to space constraints. |  |
---|---|---
Figure 4: trckd versus competitors on sequential KD. Left to right: HSTAGGER,
EMNIST, and 20NG.

##  4 Experiments

We empirically address the following research questions:

Q1

Is knowledge-aware adaptation useful?

Q2

Does interacting with the user help adaptation?

Q3

Does trckd work in realistic, multi-drift settings?

The code for all experiments is at: https://gitlab.com/abonte/handling-
knowledge-drift.

#### Competitors.

We compared trckd against several alternatives: MW-kNN: the multi-window $k$NN
approach of [26] designed specifically for multi-label problems. PAW-kNN:
punitive adaptive window $k$NN, a state-of-the-art multi-label approach that
employs a single window for all concepts and adapts by discarding examples
responsible for prediction mistakes [23]. $\textsc{trckd}_{LLR}$: a fully-
automated version of trckd that follows up MMD detection by performing drift
disambiguation with a likelihood ratio test. This test detects a relation
$y^{j}$ _is-a_ $y^{i}$ iff $P(y^{j}|y^{i})/P(y^{j}|\neg y^{i})\geq\beta$
with666This is the best possible value for $\beta$ as the ground-truth data is
assumed to be always consistent with the ground-truth hierarchy.
$\beta=\infty$. If the test detects relation addition/removal,
$\textsc{trckd}_{LLR}$ applies the corresponding knowledge-aware adaptation
strategy, otherwise it defaults to emptying the current window of the detected
concept(s). $k$NN 1-window: $k$NN with a single window for all concepts that
forgets old examples). $k$NN: regular $k$NN with no adaptation.

#### Data sets.

We ran experiments on three data sets. HSTAGGER: a hierarchical version of
STAGGER, a widely used synthetic data set of two-dimensional objects with
three categorical attributes (shape, color, size) and labeled by drifting
random formulas like “small and (green or red)” [24]. HSTAGGER has $3$
attributes with $4$ values each and labels instances using $5$ different
drifting random formulas chosen to have a reasonable pos./neg. ratio. The
hierarchy is created by selecting two concepts as part of a third one that
acts as parent concept. EMNIST: a data set of $28\times 28$ handwritten digits
and (uppercase, lowercase) letters [5]. We simulate hierarchical data by
running multiple streams of EMNIST examples in parallel. The digits and
letters are grouped in $5$ concepts and structured as in HSTAGGER. Instances
were embedded using a variational autoencoder [15]. 20NG: a data set of
newsgroup posts categorized in twenty topics.777From
archive.ics.uci.edu/ml/datasets/Twenty+Newsgroups The data set was converted
to hierarchical classification by grouping different classes into super-topics
(e.g., alt.atheism, soc.religion.christian and talk.religion.misc were grouped
into a “religion” super-topic). The documents were embedded using a pre-
trained Sentence-BERT model [22] and compressed to $100$ features using PCA.
The data sets are converted into streams by sequentially sampling random
examples.

#### Experimental details

All experiments were run on a machine with eight 2.8 GHz CPUs and 32 GiB RAM.
Each experiment was run ten times by changing the random seed: 2 for selecting
hyperparameters and 8 for evaluating performance. Our evaluation focuses on
concept deletion, relation addition, and relation removal; plain concept drift
is reported in the Supplementary Material. In the three cases, KD is injected
into the stream by removing a random concept from the available ones, adding a
random relation, and removing a random relation, respectively. KD starts after
the competitors approximately reach their peak performance, namely after $100$
iterations for HSTAGGER and EMNIST, and $170$ for 20NG. Performance was
measured in terms of micro $F_{1}$ score on a hold-out test set (of size $64$
for HSTAGGER and $200$ for EMNIST and 20NG) randomly selected before each run.
All methods observed the same sequence of examples and drifts. The plots
report standard error information. User replies were simulated by an oracle
that always answers correctly to disambiguation queries.

#### Hyperparameters

For trckd, the window size $w$ was fixed to 200 so to make it perform as well
as standard $k$NN when no drift is present. MW-$k$NN and all variants of trckd
use the same window size. To speed up detection, the MMD is computed on the 70
most recent examples only. Prior to each experiment, the threshold $\tau$ was
selected from $\\{0.4,0.5\\}$ to optimize $F_{1}$ on two independent runs. The
ranges of $k$ differ between methods, the detailed values are reported in the
Supplementary Material. For PAW-$k$NN, the penalty ratio was set to $p=1$ as
suggested by Roseberry et al. [23] and the minimum and maximum window sizes to
$50$ and $200$ for consistency with trckd.

#### Q1: Is knowledge-aware adaptation useful?

To evaluate the impact of our adaptation strategy, we remove unrelated effects
due to spurious/delayed detection by telling all approaches exactly when KD
occurs. We compare $\textsc{trckd}_{oracle}$ (i.e., trckd that knows exactly
when drift occurs) to MW-$k$NN, PAW-$k$NN, $k$NN 1-window, regular $k$NN and
$\textsc{trckd}_{forget}$ (trckd that adapts to all types of KD by forgetting
old examples).

The results can be viewed in Figure 2. The plots show that
$\textsc{trckd}_{oracle}$ is by far the best performing method on all data
sets and for all forms of KD. In most cases the runner up is
$\textsc{trckd}_{forget}$: while it performs similarly to
$\textsc{trckd}_{oracle}$ for concept drift and removal (see the Supplementary
Material; this is because our adaptation strategy boils down to forgetting in
this simple setup), it does lag behind for relation addition and removal,
showing a sizeable advantage for knowledge-aware adaptation. MW-$k$NN works
reasonably well but suffers from relying on passive adaptation and does not
always performs better than the two $k$NN baselines. PAW-$k$NN tends to
underperform on EMNIST and 20NG, especially when KD affects the relations.
These results validate knowledge-aware adaptation on all data sets and allows
us to answer Q1 in the affirmative. For this reason, we will focus on
knowledge aware adaptation in the following experiments.

#### Q2: Is interaction useful?

To measure the impact of interaction, we compare four variants of trckd that
differ in what information they elicit from the supervisor, namely: trckd,
$\textsc{trckd}_{LLR}$, $\textsc{trckd}_{oracle}$ and $\textsc{trckd}_{ni}$
(like trckd except that instead of interacting with the user it assumes that
all concepts detected as drifting by MMD have undergone individual concept
drift and adapts by purging their current window). The results in Figure 3 are
quite intuitive: $\textsc{trckd}_{oracle}$ substantially outperforms all
alternatives in all cases except for relation removal in 20NG. This shows
that, if drift is detected correctly and timely, interactive disambiguation is
extremely useful for guiding knowledge-aware adaptation and quickly aligning
the model to the ground-truth. trckd tends to perform substantially better
than the no-interaction baselines $\textsc{trckd}_{LLR}$ and
$\textsc{trckd}_{ni}$ and if MMD detection works well it quickly reaches the
performance of the oracle. This allows us to answer Q2 in the affirmative. If
MMD underperforms (as in EMNIST), trckd does not get a chance to quickly
interact with the user and shows no improvement. This could be fixed by better
optimizing the choice of kernel and threshold used by MMD, perhaps by turning
them into per-concept parameters. This is left to future work. Importantly,
trckd interacts with the user $1.54\pm 0.78$ times per run on average, showing
that few interaction rounds are often enough to achieve a noticeable
performance boost.

#### Q3: Does trckd work in multi-drift settings?

We consider a realistic scenario with four sequential KD events, namely
concept drift, relation addition, relation removal, and concept removal. The
results in Figure 4 show that trckd tends to outperform all competitors except
the oracle. The advantage is quite marked whenever the KD affects the concept
hierarchy itself, up to $+10\%$ $F_{1}$ for HSTAGGER and $+5\%$ for EMNIST.
The plots mirror the advantages shown by trckd in the previous experiments and
highlight that the benefits knowledge-aware adaptation and interaction carry
over to more realistic settings. This allows us to answer Q3 in the
affirmative. The lack of reactive adaptation penalizes MW-$k$NN and PAW-$k$NN,
the latter especially on EMNIST.

##  5 Related Work

trckd is the first approach that considers KD in hierarchical classification
and that explicitly tackles drift disambiguation. Indeed, existing work on
concept drift focuses on the single-label [8] and multi-label [32] cases,
while work on drift understanding is unconcerned with hierarchical
classification [18]. trckd is also the first approach to tackle drift
disambiguation by interacting with a human supervisor. Sliding windows were
first employed for drift detection in [14]. This setup offers distribution-
free guarantees on detection accuracy under mild assumptions. The idea of
using examples in the windows for explanatory purposes was also discussed in
[14]. The MMD, which trckd uses to compare present and past data, was
leveraged in domain adaptation [30]. More recent two-sample tests, like ME
[13], underperformed in our experiments.

Open world recognition is a streaming classification setting in which
unanticipated classes appear over time [4, 2]. Open world recognition only
deals with concept addition, and it is unconcerned with more general KD. Other
recent work on interactive classification under concept addition [3] focuses
on handling noisy labels rather than on adapting to drift.

Finally, in continual learning the machine must learn new concepts (or tasks)
over time. The key difference is that our goal is to smartly forget obsolete
information, whereas in continual learning the main issue is how to prevent
the machine from forgetting previously acquired knowledge [20]. More
generally, continual learning neglects other forms of KD altogether.

##  6 Conclusion

We introduced the problem of knowledge drift in hierarchical classification
and proposed to partially offload drift disambiguation to a user. We
introduced trckd, an approach for learning under KD that combines _automated_
drift detection and adaptation, upgraded to hierarchical classifiers, with
_interactive_ drift disambiguation. Our results indicate that trckd
outperforms fully automated approaches by asking just a few questions, even
when detection performance is not ideal.

In future work, we plan to improve the interpretability of our interaction
protocol by integrating ideas from explainable AI [6, 25], generalize trckd to
active learning settings in which the labels must be explicitly queried and
develop KD adaptation strategies for neural nets in continual learning.

##  7 Acknowledgments

The research of FG and AP has received funding from the European Union’s
Horizon 2020 FET Proactive project “WeNet – The Internet of us”, grant
agreement No 823783. The research of AB and ST has received funding from the
“DELPhi - DiscovEring Life Patterns” project funded by the MIUR Progetti di
Ricerca di Rilevante Interesse Nazionale (PRIN) 2017 – DD n. 1062 del
31.05.2019.

## References

  * Angeli et al. [2015] Gabor Angeli, Melvin Jose Johnson Premkumar, and Christopher D Manning.  Leveraging linguistic structure for open domain information extraction.  In _IJCNLP_ , 2015.
  * Bendale and Boult [2015] Abhijit Bendale and Terrance Boult.  Towards open world recognition.  In _CVPR_ , 2015.
  * Bontempelli et al. [2020] Andrea Bontempelli, Stefano Teso, Fausto Giunchiglia, and Andrea Passerini.  Learning in the wild with incremental skeptical gaussian processes.  In _IJCAI_ , 2020.
  * Boult et al. [2019] TE Boult, S Cruz, AR Dhamija, M Gunther, J Henrydoss, and WJ Scheirer.  Learning and the unknown: Surveying steps toward open world recognition.  In _AAAI_ , 2019.
  * Cohen et al. [2017] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik.  Emnist: Extending mnist to handwritten letters.  In _IJCNN_ , 2017.
  * Demšar and Bosnić [2018] Jaka Demšar and Zoran Bosnić.  Detecting concept drift in data streams using model explanation.  _Expert Systems with Applications_ , 2018.
  * Friedman et al. [2008] Jerome Friedman, Trevor Hastie, and Robert Tibshirani.  Sparse inverse covariance estimation with the graphical lasso.  _Biostatistics_ , 2008.
  * Gama et al. [2014] João Gama, Indrė Žliobaitė, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia.  A survey on concept drift adaptation.  _ACM Comput Surv_ , 2014.
  * Giunchiglia et al. [2017] Fausto Giunchiglia, Enrico Bignotti, and Mattia Zeni.  Personal context modelling and annotation.  In _PerCom_ , 2017.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alex Smola.  A kernel two-sample test.  _JMLR_ , 2012.
  * Jacobson et al. [2018] Matthew Jacobson, Adriana Estela Sedeño-Cortés, and Paul Pavlidis.  Monitoring changes in the gene ontology and their impact on genomic data analysis.  _GigaScience_ , 2018.
  * Jiménez-Ruiz et al. [2012] Ernesto Jiménez-Ruiz, Bernardo Cuenca Grau, Yujiao Zhou, and Ian Horrocks.  Large-scale interactive ontology matching: Algorithms and implementation.  In _ECAI_ , 2012.
  * Jitkrittum et al. [2016] Wittawat Jitkrittum, Zoltán Szabó, Kacper P Chwialkowski, and Arthur Gretton.  Interpretable distribution features with maximum testing power.  In _NeurIPS_ , 2016.
  * Kifer et al. [2004] Daniel Kifer, Shai Ben-David, and Johannes Gehrke.  Detecting change in data streams.  In _VLDB_ , 2004.
  * Kingma and Welling [2014] Diederik P Kingma and Max Welling.  Auto-encoding Variational Bayes.  In _ICLR’14_ , 2014.
  * Koller and Friedman [2009] Daphne Koller and Nir Friedman.  _Probabilistic graphical models: principles and techniques_.  2009\.
  * Lloyd and Ghahramani [2015] James R Lloyd and Zoubin Ghahramani.  Statistical model criticism using kernel two sample tests.  _Advances in Neural Information Processing Systems_ , 2015.
  * Lu et al. [2018] Jie Lu, Anjin Liu, Fan Dong, Feng Gu, Joao Gama, and Guangquan Zhang.  Learning under concept drift: A review.  _IEEE Transactions on Knowledge and Data Engineering_ , 2018.
  * Paninski [2003] Liam Paninski.  Estimation of entropy and mutual information.  _Neural computation_ , 2003.
  * Parisi et al. [2019] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter.  Continual lifelong learning with neural networks: A review.  _Neural Networks_ , 2019.
  * Pérez-Cruz [2009] Fernando Pérez-Cruz.  Estimation of information theoretic measures for continuous random variables.  In _NeurIPS_ , 2009.
  * Reimers and Gurevych [2019] Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _EMNLP-IJCNLP_ , 2019.
  * Roseberry et al. [2019] Martha Roseberry, Bartosz Krawczyk, and Alberto Cano.  Multi-label punitive knn with self-adjusting memory for drifting data streams.  _TKDD_ , 2019.
  * Schlimmer and Granger [1986] Jeffrey C Schlimmer and Richard H Granger.  Incremental learning from noisy data.  _Machine learning_ , 1986.
  * Schramowski et al. [2020] Patrick Schramowski et al.  Making deep neural networks right for the right scientific reasons by interacting with their explanations.  _Nat Mach Intell_ , 2020.
  * Spyromitros-Xioufis et al. [2011] Eleftherios Spyromitros-Xioufis, Myra Spiliopoulou, Grigorios Tsoumakas, and Ioannis Vlahavas.  Dealing with concept drift and class imbalance in multi-label stream classification.  In _IJCAI_ , 2011.
  * Srinivas et al. [2010] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger.  Gaussian process optimization in the bandit setting: no regret and experimental design.  In _ICML_ , 2010.
  * Stojanovic et al. [2002] Ljiljana Stojanovic, Alexander Maedche, Boris Motik, and Nenad Stojanovic.  User-driven ontology evolution management.  In _ECAW_ , 2002.
  * Szabó and Sriperumbudur [2017] Zoltán Szabó and Bharath K Sriperumbudur.  Characteristic and universal tensor product kernels.  _JMLR_ , 2017.
  * Zhang et al. [2013] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang.  Domain adaptation under target and conditional shift.  In _ICML_ , 2013.
  * Zhang and Zhang [2010] Min-Ling Zhang and Kun Zhang.  Multi-label learning by exploiting label dependency.  In _Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2010.
  * Zheng et al. [2019] Xiulin Zheng, Peipei Li, Zhe Chu, and Xuegang Hu.  A survey on multi-label data stream classification.  _IEEE Access_ , 2019.

### Additional Details

#### Hyperparameters.

Table 1 reports the values used in each experiment.

RQ | Drift | $\tau$ |  TRCKD $k$ |  PAW-$k$NN $k$
---|---|---|---|---
HSTAGGER
Q1 - Q2 | CD | 0.04 | 3 | 3
CR | 0.04 | 11 | 3
RA | 0.04 | 11 | 3
RR | 0.04 | 11 | 3
Q3 | All | 0.04 | 11 | 3
EMNIST
Q1 - Q2 | CD | 0.04 | 5 | 3
CR | 0.05 | 3 | 3
RA | 0.05 | 3 | 3
RR | 0.04 | 3 | 3
Q3 | All | 0.05 | 3 | 3
20NG
Q1 - Q2 | CD | 0.05 | 3 | 3
CR | 0.05 | 3 | 3
RA | 0.04 | 3 | 3
RR | 0.04 | 3 | 3
Q3 | All | 0.05 | 3 | 3
Table 1:  Hyperparameter values.

The hyperparameters are: MMD threshold $\tau$ used by trckd; number of
neighbors $k$ used by trckd and all competitors except PAW-$k$NN; and number
of neighbors $k$ used by PAW-$k$NN. Abbreviations: CD is concept drift, CR
concept removal, RA relation addition, and RR relation removal. Before each
experiment, the value of $\tau$ and $k$ are selected in two independent runs
by optimizing $F_{1}$. The value of $\tau$ is selected from $\\{0.4,0.5\\}$;
these values were frequently observed to indicate drift in our experiments.
The value of $k$ from $\\{3,5,11\\}$ and it was chosen independently for trckd
and its variants, including MW-$k$NN, and for PAW-$k$NN.

All other hyperparameters remain fixed across experiments. The window size of
trckd was set to 200. The penalty ratio of PAW-$k$NN was set to $p=1$ as in
[23], while the minimum and maximum window sizes were set to $m_{min}=50$ for
HSTAGGER and EMNIST and 80 for 20NG data set and $m_{max}=200$ repsectively.
To speed up detection, the MMD is only computed on the 70 most recent
examples. This choice does not sacrifice reliability of detection.

The inference and training time is similar for all methods since they are all
based on $k$NN. One method requires 2 seconds for training on the new example
and evaluating on test set at each iteration.

#### Data sets.

Table 2 reports, for each of our three data sets, the number of examples
sampled to generate the stream $|S|$, the number of attributes $d$ and their
type, the number of concepts $c$, as well as the following three measures of
annotation density: the (average) number of positive labels per example $LC$,
the empirical probability that a label is positive $LD$, and how many distinct
combinations of positive categories (out of $2^{c}$) are annotated in the data
$DL$. These metrics are taken from [31]. All instances in the data set belong
to the root concept.

Data set | $|S|$ | $d$ | Type | $c$ | $LC$ | $LD$ | $DL$
---|---|---|---|---|---|---|---
HSTAGGER | 570 | 3 | cat. | 6 | 4.42 $\pm$ 0.16 | 0.63 $\pm$ 0.02 | 34.63 $\pm$ 11.89
EMNIST | 570 | 10 | cont. | 9 | 3.5 $\pm$ 0.04 | 0.44 $\pm$ 0.00 | 55.38 $\pm$ 5.57
20NG | 570 | 100 | cont. | 6 | 2.19 $\pm$ 0.00 | 0.31 $\pm$ 0.00 | 8.5 $\pm$ 0.5
Table 2: Data sets statistics (mean $\pm$ std.). $|S|$: number of instances,
$d$: number of attributes, type of features (categorical or continuous), $c$:
number of labels, $LC$: label cardinality, $LD$: label density, $DL$: distinct
label set. The metrics are averaged on 8 runs and refer to the experiment for
Q3.

#### Metrics.

The plots in the paper focus on the micro $F_{1}$ score, which consider the
sparsity of the classes of our scenario. Letting
$\\{(\bm{\mathrm{x}}_{i},\bm{\mathrm{y}}_{i}):i=1,\ldots,n\\}$ be the examples
in the _test set_ , $\hat{\bm{\mathrm{y}}}_{i}$ their predictions and
$y_{i}^{j}$ the $j$th element of $y_{i}$, which is 1 if $\bm{\mathrm{x}}_{i}$
belong to the $j$th concept and 0 otherwise, the micro $F_{1}$ is defined as
follows:

$\displaystyle F_{\text{$1$-micro}}$
$\displaystyle=\frac{2\sum_{j=0}^{c}\sum_{i=1}^{n}y_{i}^{j}\hat{y}_{i}^{j}}{\sum_{j=0}^{c}\sum_{i=1}^{n}y_{i}^{j}+\sum_{j=0}^{c}\sum_{i=1}^{n}\hat{y}_{i}^{j}}$

The results showed in the following figures are averaged on 8 runs and for
each of them the standard error is reported.

### MMD Versus Mean Embeddings

In order to evaluate whether MMD is fit for dealing with KD, we implemented
Mean Embeddings (ME), an state-of-the-art kernel-based discrepancy between
distributions [13]. Importantly, the discrimination power of ME can be
maximized on an independent training set with gradient ascent. In our
experiment, we carried out this optimization on the pre-drift examples (i.e.,
on the first 100 examples in the stream for HSTAGGER and EMNIST and on the
first 170 for 20NG). We also used the very same tensor product kernel for both
MMD and ME and for ME we tuned the width of the Gaussian kernel $k_{X}$ over
instances along with the discrimination power of ME.

Despite being more powerful than MMD on paper, the ME did not perform as well
in practice. In particular, ME turned out to be overly sensitive and had
severe false detection issues. The changepoints detected by trckd +ME are
illustrated as vertical dashed bars in Figure 5 for the case of HSTAGGER with
sequential KD. In short, ME tends to detect three or four times as many drifts
as MMD. This makes it inadequate for interacting with the user: indeed,
querying the user too frequently is likely to rapidly make her lose interest
in the interaction in practice.

Figure 5: Results for multiple drifts scenario for HSTAGGER. trckd implements
the ME test for drift detection. The ME hyperparameters are $J=5$ and
$\alpha=0.01$.

### Comparison to Graphical Lasso

Given the similarity between drift disambiguation and structure learning for
probabilistic graphical models [16], we evaluated a variant of trckd that uses
graphical lasso to reconstruct the structure of the hierarchy from the most
recent examples [7]. In particular, in each iteration a data set is built by
combining the 70 most recent examples (analogously to what is done for MMD)
for all concepts in the machine’s hierarchy. This data set set is fed to
graphical lasso, which spits out an (sparse) undirected graph based on the
empirical correlation between all the concepts. The directions of individual
edges are set so to maximize the likelihood of the child implying the parent
and edges are treated as _is-a_ relations. The resulting directed graph
replaces the machine’s concept hierarchy. The difference between the previous
and current concept hierarchy is used to perform knowledge-aware adaptation.

A comparison between trckd +lasso and a baseline MW-$k$NN is reported in
Figure 6. It turns out that for relation addition and removal, graphical lasso
often fails to estimate the ground-truth concept hierarchy, leading to
systematic prediction errors. Furthermore, it is quite unstable and often
detects spurious changes to the hierarchy. The main issue is that – like other
fully automated approaches for structure learning – graphical lasso does
require substantial amounts of data to perform reliably, and this is simply
not the case in our non-stationary setting. This makes structured learning-
based approaches unsuitable for this setup.

Figure 6: HSTAGGER, automatic drift type identification with Graphical Lasso
and MMD for detection. Top: relation addition. Bottom: relation removal.

### Full Plots for Q1

Figures 7 report the $F_{1}$ score for all competitors on all data sets. The
results are the same as in the main text: $\textsc{trckd}_{oracle}$ is by far
the best performing method and the runner up is $\textsc{trckd}_{forget}$,
which lags behind when dealing with relation addition and removal. The
MW-$k$NN baseline performs well but suffers from relying on passive
adaptation. PAW-$k$NN tends to perform well for concept drift on HSTAGGER and
EMNIST, but falls behind on 20NG and for all other forms of drift.

|  |  |
---|---|---|---
|  |  |
|  |  |
Figure 7: Comparison in terms of micro F1 between trckd and standard
forgetting strategies for $k$NN-based methods. Top to bottom: results for
HSTAGGER, EMNIST, and 20NG. Left to right: concept drift, concept removal,
relation addition, and relation removal.

### Full Plots for Q2

To measure the impact of interaction, we compare four variants of trckd that
differ in what information they elicit from the supervisor:
$\textsc{trckd}_{oracle}$ which knows exactly when and what kind of knowledge
drift occurred; trckd, our proposed approach that combines MMD for detection
and interactive identification; $\textsc{trckd}_{ni}$ (no interaction) that
trusts MMD for both detection and disambiguation, and uses forgetting for
adaptation since MMD cannot distinguish between concept drift and relation
addition/removal; $\textsc{trckd}_{LLR}$: a fully-automated version of trckd
that follows up MMD detection by performing drift disambiguation with a
likelihood ratio test.

The results in terms of micro $F_{1}$ score are reported in Figure 8. The
ideal baseline outperforms all alternatives in all cases. trckd performs as
well or better than the less interactive variants in all cases. The concept
drift case for 20NG (first column, last plot), the momentary decrease in the
performance around iteration 240 is due to the fact that in most of the runs
MMD detects the drift and trckd performs the adaptation around the same
iteration.

---
Figure 8: Comparison in terms of micro F1 between trckd and less interactive
variants. Top to bottom: results for HSTAGGER, EMNIST and 20NG. Left to right:
concept drift, concept removal, relation addition, and relation removal.