# Generalized Zero-shot Intent Detection via Commonsense Knowledge

A.B. Siddique, Fuad Jamour, Luxun Xu, Vagelis Hristidis
University of California, Riverside
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Identifying user intents from natural language utterances is a crucial step in
conversational systems that has been extensively studied as a supervised
classification problem. However, in practice, new intents emerge after
deploying an intent detection model. Thus, these models should seamlessly
adapt and classify utterances with both seen and unseen intents – unseen
intents emerge after deployment and they do not have training data. The few
existing models that target this setting rely heavily on the scarcely
available training data and overfit to seen intents data, resulting in a bias
to misclassify utterances with unseen intents into seen ones. We propose
$\mathsf{RIDE}$: an intent detection model that leverages commonsense
knowledge in an unsupervised fashion to overcome the issue of training data
scarcity. $\mathsf{RIDE}$ computes robust and generalizable _relationship
meta-features_ that capture deep semantic relationships between utterances and
intent labels; these features are computed by considering how the concepts in
an utterance are linked to those in an intent label via commonsense knowledge.
Our extensive experimental analysis on three widely-used intent detection
benchmarks show that relationship meta-features significantly increase the
accuracy of detecting both seen and unseen intents and that $\mathsf{RIDE}$
outperforms the state-of-the-art model for unseen intents.

##  1 Introduction

Virtual assistants such as Amazon Alexa and Google Assistant allow users to
perform a variety of tasks (referred to as ‘skills’ in Alexa) through an
intuitive natural language interface. For example, a user can set an alarm by
simply issuing the utterance _“Wake me up tomorrow at 10 AM”_ to a virtual
assistant, and the assistant is expected to understand that the user’s intent
(i.e., “AddAlarm”) is to invoke the alarm module, then set the requested alarm
accordingly. Detecting the intent implied in a natural language utterance
(i.e., _intent detection_) is typically the first step towards performing any
task in conversational systems.

Intent detection (or classification) is a challenging task due to the vast
diversity in user utterances. The challenge is further exacerbated in the more
practically relevant setting where the full list of possible intents (or
classes) is not available before deploying the conversational system, or
intents are added over time. This setting is an instance of the _generalized
zero-shot classification problem_ Felix et al. (2018): labeled training
utterances are available for seen intents but are unavailable for unseen ones,
and at inference time, models do not have prior knowledge on whether the
utterances they receive imply seen or unseen intents; i.e., unseen intents
emerge after deploying the model. This setting is the focus of this paper.

Little research has been conducted on building generalized zero-shot (GZS)
models for intent detection, with little success. The authors in Liu et al.
(2019) proposed a dimensional attention mechanism into a capsule neural
network Sabour et al. (2017) and computing transformation matrices for unseen
intents to accommodate the GZS setting. This model overfits to seen classes
and exhibits a strong bias towards classifying utterances into seen intents,
resulting in poor performance. Most recently, the authors in Yan et al. (2020)
extended the previous model by utilizing the density-based outlier detection
algorithm LOF Breunig et al. (2000), which allows distinguishing utterances
with seen intents from those with unseen ones, which partially mitigates the
overfitting issue. Unfortunately, the performance of this model is sensitive
to that of LOF, which fails in cases where intent labels are semantically
close.

We propose $\mathsf{RIDE}$111$\mathsf{RIDE}$: Relationship Meta-features
Assisted Intent DEtection222Currently under review. GitHub Code Repository
will be shared upon acceptance, a model for GZS intent detection that utilizes
commonsense knowledge to compute robust and generalizable unsupervised
_relationship meta-features_. These meta-features capture deep semantic
associations between an utterance and an intent, resulting in two advantages:
(_i_) they significantly decrease the bias towards seen intents as they are
similarly computed for both seen and unseen intents and (_ii_) they infuse
commonsense knowledge into our model, which significantly reduces its reliance
on training data without jeopardizing its ability to distinguish semantically
close intent labels. Relationship meta-features are computed by analyzing how
the phrases in an utterance are linked to an intent label via commonsense
knowledge.

Figure 1 shows how the words (or phrases) in an example utterance are linked
to the words in an example intent label through the nodes (i.e., concepts) of
a commonsense knowledge graph. In this example, the link
${\langle}\texttt{look for},$ $Synonym,$ $\texttt{find}{\rangle}$ indicates
that look for and find are synonyms, and the links ${\langle}\texttt{feeling
hungry},$ $CausesDesire,$ $\texttt{eat}{\rangle}$ and
${\langle}\texttt{restaurant},$ $UsedFor,$ $\texttt{eat}{\rangle}$ can be used
to infer the existence of the link ${\langle}\texttt{feeling hungry},$
$IsRelated,$ $\texttt{restaurant}{\rangle}$, which indicates that feeling
hungry and restaurant are related. These two links, the direct and the
inferred ones, carry a significant amount of semantic relatedness, which
indicates that the given utterance-intent pair is compatible. Note that this
insight holds regardless of whether the intent is seen or not. $\mathsf{RIDE}$
utilizes this insight to build relationship meta-feature vectors that quantify
the relatedness between an utterance and an intent in an unsupervised fashion.

$\mathsf{RIDE}$ combines relationship meta-features with contextual word
embeddings Peters et al. (2018), and feeds the combined feature vectors into a
trainable prediction function to finally detect intents in utterances. Thanks
to our relationship meta-features, $\mathsf{RIDE}$ is able to accurately
detect both seen and unseen intents in utterances. Our extensive experimental
analysis using the three widely used benchmarks, SNIPS Coucke et al. (2018),
SGD Rastogi et al. (2019), and MultiWOZ Zang et al. (2020) show that our model
outperforms the state-of-the-art model in detecting unseen intents in the GZS
setting by at least 30.36%.

A secondary contribution of this paper is that we managed to further increase
the accuracy of GZS intent detection by employing Positive-Unlabeled (PU)
learning Elkan and Noto (2008) to predict if a new utterance belongs to a seen
or unseen intent. PU learning assists intent detection models by mitigating
their bias towards classifying most utterances into seen intents. A PU
classifier is able to perform binary classification after being trained using
only positive and unlabeled examples. We found that the use of a PU classifier
also improves the accuracy of existing GZS intent detection works, but our
model is again outperforming these works.

Figure 1: Example utterance, intent, and small commonsense knowledge graph.
The presence of direct links such as ${\langle}\texttt{look for},$ $Synonym,$
$\texttt{find}{\rangle}$ and inferred ones such as ${\langle}\texttt{feeling
hungry},$ $IsRelated,$ $\texttt{restaurant}{\rangle}$ between phrases in the
utterance and those in the intent label indicate utterance-intent
compatibility.

##  2 Preliminaries

Figure 2: Overview of $\mathsf{RIDE}$.

###  2.1 Intent Detection

Let $\mathcal{S}=\\{\mathcal{I}{1},\cdots,\mathcal{I}{k}\\}$ be a set of seen
intents and $\mathcal{U}=\\{\mathcal{I}_{k+1},\cdots,\mathcal{I}_{n}\\}$ be a
set of unseen intents where $\mathcal{S}\cap\mathcal{U}=\varnothing$. Let
$\mathcal{X}=\\{\mathcal{X}{1},\mathcal{X}{2},...,\mathcal{X}{m}\\}$ be a set
of labeled training utterances where each training utterance
$\mathcal{X}_{i}\in\mathcal{X}$ is described with a tuple
$(\mathcal{X}{i},\mathcal{I}{j})$ such that $\mathcal{I}{j}\in\mathcal{S}$. An
intent $\mathcal{I}{j}$ is comprised of an _Action_ and an _Object_ and takes
the form “ActionObject”333If intents are described using a complex textual
description, Actions and Objects can be extracted using existing NLP tools
such as dependency parsers. (e.g., “FindRestaurant”); an Action describes a
user’s request or activity and an Object describes the entity pointed to by an
Action Chen et al. (2013); Wang et al. (2015); Vedula et al. (2020). In both
the zero-shot (ZS) and the GZS settings, the training examples have intent
labels from set $\mathcal{S}$ only, however, the two settings differ as
follows.

ZS Intent Detection. Given a test utterance $\mathcal{X}^{\prime}_{i}$ whose
true label $\mathcal{I}_{j}$ is known to be in $\mathcal{U}$ a priori, predict
a label $\mathcal{I}^{\prime}{j}\in\mathcal{U}$.

GZS Intent Detection. Given a test utterance $\mathcal{X}^{\prime}_{i}$,
predict a label $\mathcal{I}^{\prime}{j}\in\mathcal{S}\cup~{}\mathcal{U}$.
Note that unlike in the ZS setting, it is not known whether the true label of
$\mathcal{X}^{\prime}_{i}$ belongs to $\mathcal{S}$ or $\mathcal{U}$, which
exacerbates the challenge in this setting; we focus on this setting in this
paper.

###  2.2 Knowledge Graphs

Knowledge graphs (KG) are structures that capture relationships between
entities, and are typically used to capture knowledge in a semi-structured
format; i.e., they are used as knowledge bases. Knowledge graphs can be viewed
as collections of triples, each representing a fact of the form
${\langle}\texttt{head},$ $relation,$ $\texttt{tail}{\rangle}$ where head and
tail describe entities and $relation$ describes the relationship between the
respective entities. In this work, we use ConceptNet Speer et al. (2016),
which is a rich and widely-used commonsense knowledge graph. Interested
readers can check Appendix A.1 for more details on ConceptNet.

###  2.3 Link Prediction

While large knowledge graphs may capture a large subset of knowledge, they are
incomplete: some relationships (or links) are missing. Link prediction Kazemi
and Poole (2018) augments knowledge graphs by predicting missing relations
using existing ones. In the context of this work, we pre-train a state-of-the-
art link prediction model (LP) on the ConceptNet KG to score novel facts that
are not necessarily present in the knowledge graph. Given a triple (i.e.,
fact) in the form ${\langle}\texttt{head},$ $relation,$
$\texttt{tail}{\rangle}$, a link prediction model scores the triple with a
value between 0 and 1, which quantifies the level of validity of the given
triple. The details of training our link predictor are available in Appendix
A.2.

###  2.4 Positive-Unlabeled Learning

Positive-Unlabeled (PU) classifiers learn a standard binary classifier in the
unconventional setting where labeled negative training examples are
unavailable. The state-of-the-art PU classifier Elkan and Noto (2008), which
we integrate into our model, learns a decision boundary based on the positive
and unlabeled examples, and thus can classify novel test examples into
positive or negative. The aim of the PU classifier is to learn a probabilistic
function $f(\mathcal{X}{i})$ that estimates
$P(\mathcal{I}{j}\in\mathcal{S}\mid\mathcal{X}{i})$ as closely as possible. In
this work, we train a PU classifier using our training set (utterances with
only seen intents labeled as positive) and validation set (utterances with
both seen and unseen intents as unlabeled). We use 512-dimensions sentence
embedding as features when using the PU classifier, generated using a pre-
trained universal sentence encoder Cer et al. (2018).

##  3 Our Approach

Figure 2 shows an overview of our model: given an input utterance
$\mathcal{X}_{i}$, we first invoke the PU classifier (if it is available) to
predict whether $\mathcal{X}_{i}$ implies a seen or an unseen intent; i.e.,
whether $\mathcal{X}_{i}$’s intent belongs to set $\mathcal{S}$ or
$\mathcal{U}$. Then, an instance of our core model (the red box in Figure 2)
is invoked for each intent in $\mathcal{S}$ or $\mathcal{U}$ based on the PU’s
prediction. Our core model predicts the level of compatibility between the
given utterance $\mathcal{X}_{i}$ and intent $\mathcal{I}_{j}$, i.e., the
probability that the given utterance implies the given intent
$P(\mathcal{I}_{j}|\mathcal{X}_{i})\in[0,1]$. Finally, our model outputs the
intent with the highest compatibility probability, i.e.,
$\operatorname*{argmax}_{\mathcal{I}_{j}}P(\mathcal{I}_{j}|\mathcal{X}_{i})$.

Our core model concatenates relationship meta-features, utterance embedding,
and intent embedding and feeds them into a trainable prediction function. The
Relationship Meta-features Generator (RMG) is at the heart of our model, and
it is the most influential component. Given an utterance and an intent, RMG
generates meta-features that capture deep semantic associations between the
given utterance and intent in the form of a meta-feature vector.

###  3.1 Relationship Meta-feature Generation

RMG extracts relationship meta-features by utilizing the “ActionObject”
structure of intent labels and commonsense knowledge graphs. Relationship
meta-features are not only generalizable, but also discriminative: while the
example utterance “Look for something nearby. I am feeling hungry.” may be
related to the intent “ReserveRestaurant”, the Action part of this intent is
not related to any phrase in the utterance; thus, “ReserveRestaurant” is less
related to the utterance than “FindRestaurant”.

RMG takes the following inputs: a set of relations in a knowledge graph (35 in
the case of ConceptNet)
$\mathcal{R}=\\{\mathpzc{r}{1},\mathpzc{r}{2},..,\mathpzc{r}{t}\\}$; the set
of n-grams $\mathcal{G}{i}=\\{g{1},g{2},..,g{q}\\}$ that correspond to the
input utterance $\mathcal{X}{i}$, where $|\mathcal{G}|=\mathpzc{q}$; and an
intent label $\mathcal{I}{j}=\\{\mathcal{A},\mathcal{O}\\}$, where
$\mathcal{A}$ and $\mathcal{O}$ are the Action and Object components of the
intent, respectively. RMG computes a relationship meta-features vector in four
steps, where each step results in a vector of size $|\mathcal{R}|$. The
smaller vectors are:
$\textbf{e}^{\overrightarrow{\mathcal{A}}}_{\mathcal{X}{i}}$,
$\textbf{e}^{\overrightarrow{\mathcal{O}}}_{\mathcal{X}{i}}$,
$\textbf{e}^{\overleftarrow{\mathcal{A}}}_{\mathcal{X}{i}}$, and
$\textbf{e}^{\overleftarrow{\mathcal{O}}}_{\mathcal{X}{i}}$, where
$\textbf{e}^{\overrightarrow{\mathcal{A}}}_{\mathcal{X}{i}}$ captures the
Action to utterance semantic relationships and
$\textbf{e}^{\overrightarrow{\mathcal{O}}}_{\mathcal{X}{i}}$ captures the
Object to utterance relationships. The remaining two vectors capture
relationships in the other direction; i.e., utterance to Action/Object,
respectively. Capturing bi-directional relationships is important because a
relationship in one direction does not necessarily imply one in the other
direction – for example, ${\langle}\texttt{table},$ $AtLocation,$
$\texttt{restaurant}{\rangle}$ does not imply ${\langle}\texttt{restaurant},$
$AtLocation,$ $\texttt{table}{\rangle}$. The final output of RMG is the
relationship meta-features vector $\textbf{e}_{\mathpzc{relationship}}$, which
is the concatenation of the four aforementioned vectors. We explain next how
the smaller vectors is computed.

Input: $\mathcal{R}=\\{\mathpzc{r}{1},\cdots,\mathpzc{r}{t}\\}$: relations in
KG

$\mathcal{G}_{i}=\\{g{1},\cdots,g{q}\\}$: utterance n-grams

$\mathcal{I}_{j}=\\{\mathcal{A},\mathcal{O}\\}$: intent’s Action and Object

Output: $\textbf{e}_{\mathpzc{relationship}}$:
$\mathcal{X}_{i}$-$\mathcal{I}_{j}$ relationship meta-features

Let $\textbf{e}^{\overrightarrow{\mathcal{A}}}_{\mathcal{X}{i}}$ = RM
($\mathcal{A}$, $\mathcal{G}{i}$, $\rightarrow$) // Action to utterance

Let $\textbf{e}^{\overrightarrow{\mathcal{O}}}_{\mathcal{X}{i}}$ = RM
($\mathcal{O}$, $\mathcal{G}{i}$, $\rightarrow$) // Object to utterance

Let $\textbf{e}^{\overleftarrow{\mathcal{A}}}_{\mathcal{X}{i}}$ = RM
($\mathcal{A}$, $\mathcal{G}{i}$, $\leftarrow$) // utterance to Action

Let $\textbf{e}^{\overleftarrow{\mathcal{O}}}_{\mathcal{X}{i}}$ = RM
($\mathcal{O}$, $\mathcal{G}{i}$, $\leftarrow$) // utterance to Object

Let $\textbf{e}_{\mathpzc{relationship}}$ =
[$\textbf{e}^{\overrightarrow{\mathcal{A}}}_{\mathcal{X}{i}}$,
$\textbf{e}^{\overrightarrow{\mathcal{O}}}_{\mathcal{X}{i}}$,
$\textbf{e}^{\overleftarrow{\mathcal{A}}}_{\mathcal{X}{i}}$,
$\textbf{e}^{\overleftarrow{\mathcal{O}}}_{\mathcal{X}{i}}$]

return $\textbf{e}_{\mathpzc{relationship}}$

Function  _RM(_$concept$ , $phrases$, $direction$_)_:

Let e = []

foreach  _$r\in\mathcal{R}$_ do

if  _$direction$ = $\rightarrow$_ then

Let $p$ = Max $(LP(concept,r,g))$ for $g\in phrases$

if  _$direction$ = $\leftarrow$_ then

Let $p$ = Max $(LP(g,r,concept))$ for $g\in phrases$

e.append(p)

return e

Algorithm 1 RMG

RMG computes $\textbf{e}^{\overrightarrow{\mathcal{A}}}_{\mathcal{X}{i}}$ by
considering the strength of each relation in $\mathcal{R}$ between
$\mathcal{A}$ and each n-gram in $\mathcal{G}{i}$. That is,
$\textbf{e}^{\overrightarrow{\mathcal{A}}}_{\mathcal{X}{i}}$ has
$|\mathcal{R}|$ cells, where each cell corresponds to a relation
$r\in\mathcal{R}$. Each cell is computed by taking $max(LP(\mathcal{A},r,g))$
over all $g\in\mathcal{G}{i}$. $LP$(head, $relation$, tail) outputs the
probability that the fact represented by the triple ${\langle}\texttt{head},$
$relation,$ $\texttt{tail}{\rangle}$ exists. The vector
$\textbf{e}^{\overrightarrow{\mathcal{O}}}_{\mathcal{X}{i}}$ is computed
similarly, but with passing $\mathcal{O}$ instead of $\mathcal{A}$ when
invoking the link predictor; i.e., taking $max(LP(\mathcal{O},r,g))$ over all
$g\in\mathcal{G}{i}$ to compute each cell. The vectors
$\textbf{e}^{\overleftarrow{\mathcal{A}}}_{\mathcal{X}{i}}$ and
$\textbf{e}^{\overleftarrow{\mathcal{O}}}_{\mathcal{X}{i}}$ are computed
similarly, but with swapping the head and tail when invoking the link
predictor; i.e., utterance phrases are passed as head and Action/Object parts
are passed as tail. Algorithm 1 outlines the previous process. Finally, the
generated meta-features are passed through a linear layer with sigmoid
activation before concatenation with the utterance and intent embeddings.

###  3.2 Utterance and Intent Encoders

Given an utterance
$\mathcal{X}{i}=\\{\mathpzc{w}{1},\mathpzc{w}{2},\cdots,\mathpzc{w}_{\mathpzc{u}}\\}$
with $\mathpzc{u}$ words, first we compute an embedding
$\mathpzc{emb}(\mathpzc{w}{j})\in\mathbb{R}^{\mathpzc{dim}}$ for each word
$\mathpzc{w}_{\mathpzc{j}}$ in the utterance, where
$\mathpzc{emb}(\mathpzc{w}{j})$ is the concatenation of a contextual embedding
obtained from a pre-trained ELMo model and parts of speech (POS) tag
embedding. Then, we use bi-directional LSTM to produce a
$\mathpzc{d}$-dimensional representation as follows:

$\overrightarrow{\mathpzc{\textbf{h}}}{j}=\text{LSTM}{fw}(\overrightarrow{\mathpzc{\textbf{h}}}_{\mathpzc{j}-\mathpzc{1}},\mathpzc{emb}(\mathpzc{w}{j})).$
$\overleftarrow{\mathpzc{\textbf{h}}}{j}=\text{LSTM}{bw}(\overleftarrow{\mathpzc{\textbf{h}}}_{\mathpzc{j}-\mathpzc{1}},\mathpzc{emb}(\mathpzc{w}{j})).$

Finally, we concatenate the output of the last hidden states as utterance
embedding
$\textbf{e}_{\mathpzc{utterance}}=[\overrightarrow{\mathpzc{\textbf{h}}}{u};\overleftarrow{\mathpzc{\textbf{h}}}{u}]\in\mathbb{R}^{\mathpzc{d}}$.
We encode intent labels similarly to produce an intent embedding
$\textbf{e}_{\mathpzc{intent}}\in\mathbb{R}^{\mathpzc{d}}$.

###  3.3 Training the Model

Our model has two trainable components: the LSTM units in the utterance and
intent encoders and the compatibility probability prediction function. We
jointly train these components using training data prepared as follows. The
training examples are of the form
$((\mathcal{X}{i},\mathcal{I}{j}),\mathcal{Y})$, where $\mathcal{Y}$ is a
binary label representing whether the utterance-intent pair
$(\mathcal{X}{i},\mathcal{I}{j})$ are compatible: $1$ means they are
compatible, and $0$ means they are not. For example, the utterance-intent pair
(“I want to play this song”, “PlaySong”) gets a label of $1$, and the same
utterance paired with another intent such as “BookHotel” gets a label of $0$.
We prepare our training data by assigning a label of $1$ to the available
utterance-intent pairs (where intents are seen ones); these constitute
positive training examples. We create a negative training example for each
positive one by corrupting the example’s intent. We corrupt intents by
modifying their Action, Object, or both; for example, the utterance-intent
pair (“Look for something nearby. I am hungry.”, “FindRestaurant”) may result
in the negative examples (…, “ReserveRestaurant”), (…, “FindHotel”), or
(…,“RentMovies”). We train our core model by minimizing the cross-entropy loss
over all the training examples.

##  4 Experimental Setup

In this section, we describe the datasets, evaluation settings and metrics,
competing methods, and implementation details of our proposed method.

###  4.1 Datasets

Table 1 presents important statistics on the datasets we used in our
experiments.

SNIPS Coucke et al. (2018). A crowd-sourced single-turn NLU benchmark with $7$
intents across different domains.

SGD Rastogi et al. (2019). A recently published dataset for the eighth Dialog
System Technology Challenge, Schema Guided Dialogue (SGD) track. It contains
dialogues from $16$ domains with a total of $46$ intents. It is one of the
most comprehensive and challenging publicly available datasets. The dialogues
contain user intents as part of dialogue states. We only kept utterances where
users express an intent by comparing two consecutive dialogue states to check
for the expression of a new intent.

MultiWOZ Zang et al. (2020). Multi-Domain Wizard-of-Oz (MultiWOZ) is a well-
known and publicly available dataset. We used the most recent version $2.2$ of
MultiWOZ in our experiments, which contains utterances spanning $11$ intents.
Similarly to the pre-processing of SGD dataset, we only kept utterances that
express an intent to maintain consistency with the previous work.

Dataset | SNIPS | SGD | MultiWOZ
---|---|---|---
Dataset Size |  $14.2$K |  $57.2$K |  $30.0$K
Vocab. Size |  $10.8$K |  $8.8$K |  $9.7$K
Avg. Length | $9.05$ | $10.62$ | $11.07$
# of Intents | $7$ | $46$ | $11$
Table 1: Dataset statistics.

###  4.2 Evaluation Methodology

We use standard classification evaluation measures: accuracy and F1 score. The
values for all the metrics are per class averages weighted by their respective
support. We present evaluation results for the following intent detection
settings:

ZS intent Detection. In this setting, a model is trained on all the utterances
with seen intents – i.e., all samples $(\mathcal{X}{i},\mathcal{I}{j})$ where
$\mathcal{I}{j}\in\mathcal{S}$. Whereas at inference time, the utterances are
only drawn from those with unseen intents; the model has to classify a given
utterance into one of the unseen intents. Note that this setting is less
challenging than the GZS setting because models know that utterances received
at inference time imply intents that belong to the set of unseen intents only,
thus naturally reducing their bias towards classifying utterances into seen
intents. For each dataset, we randomly place $\approx 25\%$, $\approx 50\%$,
and $\approx 75\%$ of the intents in the seen set for training and the rest
into the unseen set for testing, and report the average results over $10$
runs. It is important to highlight that selecting seen/unseen sets in this
fashion is more challenging to models because all the intents get an equal
chance to appear in the unseen set, which exposes models that are capable of
detecting certain unseen intents only.

GZS intent Detection. In this setting, models are trained on a subset of
utterances implying seen intents. At inference time, test utterances are drawn
from a set that contains utterances implying a mix of seen and unseen intents
(disjoint set from training set) and the model is expected to select the
correct intent from all seen and unseen intents for a given test utterance.
This is the most realistic and challenging problem setting, and it is the main
focus of this work. For the GZS setting, we decided the train/test splits for
each dataset as follows: For SNIPS, we first randomly selected 5 out of 7
intents and designated them as seen intents – the remaining 2 intents were
designated as unseen intents. We then selected $70\%$ of the utterances that
imply any of the 5 seen intents for training. The test set consists of the
remaining $30\%$ utterances in addition to all utterances that imply one of
the 2 unseen intents. Previous work Liu et al. (2019) used the same number of
seen/unseen intents, but selected the seen/unseen intents manually. Whereas we
picked unseen intents randomly, and we report results over $10$ runs resulting
in a more challenging and thorough evaluation. That is, each intent gets an
equal chance to appear as an unseen intent in our experiments, which allows
testing each model more comprehensively. For SGD, we used the standard splits
proposed by the dataset authors. Specifically, the test set includes
utterances that imply $8$ unseen intents and $26$ seen intents; we report
average results over $10$ runs. For MultiWOZ, we used $70\%$ of the utterance
that imply $8$ (out of $11$) randomly selected intents for training and the
rest of the utterances (i.e., the remaining $30\%$ of seen intents’ utterances
and all utterances implying unseen intents) for testing.

(a) SNIPS dataset

(b) SGD dataset

(c) MultiWOZ dataset

Figure 3: F1 scores for competing models in the ZS setting with varying
percentages of seen intents. In the ZS setting, utterances with only unseen
intents are encountered at inference time, and models are aware of this. Our
model $\mathsf{RIDE}$ consistently outperforms all other models for any given
percentage of seen intents.

###  4.3 Competing Methods

We compare our model $\mathsf{RIDE}$ against the following state-of-the-art
(SOTA) models and several strong baselines:

SEG Yan et al. (2020). A semantic-enhanced Gaussian mixture model that uses
large margin loss to learn class-concentrated embeddings coupled with a
density-based outlier detection algorithm LOF to detect unseen intents.

ReCapsNet-ZS Liu et al. (2019). A model that employs capsule neural network
and a dimensional attention module to learn generalizable transformational
metrices from seen intents.

IntentCapsNet Xia et al. (2018). A model that utilizes capsule neural networks
to learn low-level features and routing-by-agreement to adapt to unseen
intents. This model was originally proposed for detecting intents in the
standard ZS setting. We extended it to support the GZS setting with the help
of its authors.

Other Baseline Models. (_i_) Zero-shot DDN Kumar et al. (2017): A model for ZS
intent detection that achieves zero-shot capabilities by projecting utterances
and intent labels into the same high dimensional embedding space. (_ii_) CDSSM
Chen et al. (2016): A model for ZS intent detection that utilizes a
convolutional deep structured semantic model to generate embeddings for unseen
intents. (_iii_) CMT Socher et al. (2013): A model for ZS intent detection
that employs non-linearity in the compatibility function between utterances
and intents to find the most compatible unseen intents. (_iv_) DeViSE Frome et
al. (2013): A model that was originally proposed for zero-shot image
classification that learns a linear compatibility function. Note that baseline
ZS models have been extended to support GZS setting.

###  4.4 Implementation Details

We lemmatize ConeptNet KG, that has $1$ million nodes (English only after
lemmatization), $2.7$ million edges, and $35$ relation types. The link
predictor is trained on the lemmatized version of ConceptNet KG. The link
predictor has two $200$-dimensional embedding layers and a negative sampling
ratio of $10$; it is trained for $1,000$ epochs using Adam optimizer with a
learning rate of $0.05$, L2 regularization value of $0.1$, and batch size of
$4800$. Our relationship meta-features generator takes in an utterance’s
n-grams with n $\leq 4$ and an intent label, and uses the pre-trained link
predictor to produce relationship meta-features with $140$ dimensions. Our
utterance and intent encoders use pre-trained ELMo contextual word embeddings
with $1024$ dimension and POS tags embeddings with $300$ dimension, and a two-
layer RNN with $300$-dimensional bidirectional LSTM as recurrent units. Our
prediction function has two dense layers with relu and softmax activation. Our
core model is trained for up to $200$ epochs with early stopping using Adam
optimizer and a cross entropy loss with initial learning rate of $0.001$ and
ReduceLROnPlateau scheduler PyTorch (2020) with $20$ patience epochs. It uses
dropout rate of $0.3$ and batch size of $32$. A negative sampling ratio of up
to $6$ is used. We use the same embeddings generation and training mechanism
for all competing models.

Method | SNIPS | SGD | MultiWOZ
---|---|---|---
Unseen | Seen | Unseen | Seen | Unseen | Seen
Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1
DeViSE | 0.0311 | 0.0439 | 0.9487 | 0.6521 | 0.0197 | 0.0177 | 0.8390 | 0.5451 | 0.0119 | 0.0270 | 0.8980 | 0.5770
CMT | 0.0427 | 0.0910 | 0.9751 | 0.6639 | 0.0254 | 0.0621 | 0.9014 | 0.5803 | 0.0253 | 0.0679 | 0.9025 | 0.6216
CDSSM | 0.0521 | 0.0484 | 0.9542 | 0.7028 | 0.0367 | 0.0284 | 0.8890 | 0.6379 | 0.0373 | 0.0244 | 0.8861 | 0.6515
Zero-shot DNN | 0.0912 | 0.1273 | 0.9437 | 0.6687 | 0.0662 | 0.1168 | 0.8825 | 0.6098 | 0.0802 | 0.1149 | 0.8940 | 0.6012
IntentCapsNet | 0.0000 | 0.0000 | 0.9749 | 0.6532 | 0.0000 | 0.0000 | 0.8982 | 0.5508 | 0.0000 | 0.0000 | 0.9249 | 0.6038
ReCapsNet | 0.1249 | 0.1601 | 0.9513 | 0.6783 | 0.1062 | 0.1331 | 0.8762 | 0.5751 | 0.1081 | 0.1467 | 0.8715 | 0.6170
SEG | 0.6943 | 0.6991 | 0.8643 | 0.8651 | 0.3723 | 0.4032 | 0.6134 | 0.6356 | 0.3712 | 0.4143 | 0.6523 | 0.6456
$\mathsf{RIDE}$ ${~{}\mathpzc{w/o}~{}\textsc{PU}}$ | 0.8728 | 0.9103 | 0.8906 | 0.8799 | 0.3865 | 0.4634 | 0.8126 | 0.8295 | 0.3704 | 0.4645 | 0.8558 | 0.8816
$\mathsf{RIDE}$ ${~{}\mathpzc{/w}~{}\textsc{PU}}$ | 0.9051 | 0.9254 | 0.9179 | 0.9080 | 0.5901 | 0.5734 | 0.8315 | 0.8298 | 0.5686 | 0.5206 | 0.8844 | 0.8847
Table 2: Main results: accuracy and F1 scores for competing models in the GZS
setting (i.e., models receive both seen and unseen intents at inference time,
which makes the setting more challenging than the ZS setting). We present
results for two variants of our model: $\mathsf{RIDE}$
${~{}\mathpzc{w/o}~{}\textsc{PU}}$ which does not use a PU classifier, and
$\mathsf{RIDE}$ ${~{}\mathpzc{/w}~{}\textsc{PU}}$ which uses one. Our model
consistently achieves the best F1 score for both seen and unseen intents
across all datasets, regardless of whether the PU classifier is integrated or
not.

(a) SNIPS dataset

(b) SGD dataset

(c) MultiWOZ dataset

Figure 4: F1 scores for unseen intents for the competing models in the GZS
setting after integrating a PU classifier.

##  5 Results

Standard ZS Intent Detection. Figure 3 presents the F1 scores averaged over
$10$ runs for all competing models with varying percentages of seen intents in
the ZS setting. The performance of all models improves as the percentage of
seen intents increases, which is expected because increasing the percentage of
seen intent gives models access to more training data and intents. Our model
$\mathsf{RIDE}$ consistently outperforms the SOTA model SEG Yan et al. (2020)
and all other models in the ZS setting with a large margin across all the
datasets. Specifically, it is at least $12.65\%$ more accurate on F1 score
than the second best model for any percentage of seen intents on all the
datasets. Note that all models perform worse on SGD and MultiWOZ compared to
SNIPS because these two datasets are more challenging: they contain closely
related intent labels such as “FindRestaurant” and “FindHotel”.

GZS Intent Detection. Table 2 shows accuracy and F1 scores averaged over $10$
runs for all competing models in the GZS setting. For unseen intents, our
model $\mathsf{RIDE}$ outperforms all other competing models on accuracy with
a large margin. Specifically, $\mathsf{RIDE}$ is $30.36\%$, $58.50\%$, and
$53.18\%$ more accurate than the SOTA model SEG on SNIPS, SGD, and MultiWOZ
for unseen intents, respectively. Moreover, our model consistently achieves
the highest F1 score on seen as well as unseen intents, which confirms its
generalizability. CMT and IntentCapsNet achieve the highest accuracy for
utterances with seen intents on all datasets, but their F1 score is among the
worst due to their biased-ness towards misclassifying utterances with unseen
intents into seen ones. $\mathsf{RIDE}$ outperforms the SOTA model SEG
regardless of whether a PU classifier is incorporated or not. For SNIPS, the
role of the PU classifier is negligible as it causes a slight improvement in
accuracy and F1 score. For SGD and MultiWOZ, which are more challenging
datasets, the PU classifier is responsible for significant improvements in
accuracy. Specifically, it provides $20.36$ and $19.82$ percentage points
improvement for SGD and MultiWOZ, respectively, on unseen intents.

Effect of PU Classifier on Other Models. We observed that one of the main
sources of error for most models in the GZS setting is their tendency to
misclassify utterances with unseen intents into seen ones due to overfitting
to seen intents. We investigated whether existing models can be adapted to
accurately classify utterances with unseen intents by partially eliminating
their bias towards seen intents. Figure 4 presents F1 scores of all the models
with and without PU classifier. A PU classifier significantly improves the
results of all the competing models. For instance, the IntentCapsNet model
with a PU classifier achieves an F1 score of 74% for unseen intents on SNIPS
dataset in the GZS setting compared to an F1 score of less than 0.01% without
the PU classifier. Note that the PU classifier has an accuracy (i.e.,
correctly predicting whether the utterance implies a seen or an unseen intent)
of $93.69$ and an F1 score of $93.75$ for SNIPS dataset; $86.13$ accuracy and
$83.54$ F1 score for SGD dataset; and $87.32$ accuracy and $88.51$ F1 score
for MultiWOZ dataset. Interestingly, our model $\mathsf{RIDE}$ (without PU
classifier) outperforms all the competing models even when a PU classifier is
incorporated into them, which highlights that the PU classifier is not the
main source of the performance of our model. We did not incorporate the PU
classifier into SEG model because it already incorporates an equivalent
mechanism to distinguish seen intents from unseen ones (i.e., outlier
detection).

Configuration | SNIPS | SGD | MultiWOZ
---|---|---|---
UI-Embed ${~{}\mathpzc{w/o}~{}\textsc{PU}}$ | 0.2367 | 0.1578 | 0.1723
Rel-M ${~{}\mathpzc{w/o}~{}\textsc{PU}}$ | 0.7103 | 0.3593 | 0.3321
RIDE ${~{}\mathpzc{w/o}~{}\textsc{PU}}$ | 0.9103 | 0.4634 | 0.4645
UI-Embed ${~{}\mathpzc{/w}~{}\textsc{PU}}$ | 0.7245 | 0.4202 | 0.4124
Rel-M ${~{}\mathpzc{/w}~{}\textsc{PU}}$ | 0.8463 | 0.5167 | 0.4781
RIDE ${~{}\mathpzc{/w}~{}\textsc{PU}}$ | 0.9254 | 0.5734 | 0.5206
Table 3: Ablation study: F1 scores for unseen intents in GZS setting; the key
reason behind our model’s astonishing accuracy is our relationship meta-
features.

Ablation Study. To quantify the effectiveness of each component in our model,
we present the results of our ablation study in Table 3 (in the GZS setting).
Utilizing utterance and intent embeddings only (i.e., UI-Embed) results in
very low F1 score, i.e., 23.67% on SNIPS dataset. Employing relationship meta-
features only (i.e., Rel-M) results in significantly better results: an F1
score of 71.03% on SNIPS dataset. When utterance and intent embeddings are
used in conjunction with relationship meta-features (i.e., $\mathsf{RIDE}$
${~{}\mathpzc{w/o}~{}\textsc{PU}}$), it achieves better F1 score compared to
the Rel-M or UI-Embed configurations. A similar trend can be observed for the
other datasets as well. Finally, when our entire model is deployed (i.e.,
including utterance and intent embeddings, relationship meta-features, and the
PU classifier, i.e., $\mathsf{RIDE}$ ${~{}\mathpzc{/w}~{}\textsc{PU}}$), it
achieves the best results on all the datasets.

##  6 Related Work

The deep neural networks have proved highly effective for many critical NLP
tasks Siddique et al. (2020); Farooq et al. (2020); Zhang et al. (2018);
Williams (2019); Ma et al. (2019); Siddique et al. (2021); Liu and Lane
(2016); Gupta et al. (2019). We organize the related work on intent detection
into three categories: (_i_) supervised intent detection, (_ii_) standard
zero-shot intent detection, and (_iii_) generalized zero-shot intent
detection.

Supervised Intent Detection. Recurrent neural networks Ravuri and Stolcke
(2015) and semantic lexicon-enriched word embeddings Kim et al. (2016) have
been employed for supervised intent detection. Recently, researchers have
proposed solving the related problems of intent detection and slot-filling
jointly Liu and Lane (2016); Zhang et al. (2018); Xu and Sarikaya (2013).
Supervised intent classification works assume the availability of a large
amount of labeled training data for all intents to learn discriminative
features, whereas we focus on the more challenging and more practically
relevant setting where intents are evolving and training data is not available
for all intents.

Standard Zero-shot Intent Detection. The authors in Yazdani and Henderson
(2015) proposed using label ontologies Ferreira et al. (2015) (i.e., manually
annotated intent attributes) to facilitate generalizing a model to support
unseen intents. The authors in Dauphin et al. (2013); Kumar et al. (2017);
Williams (2019) map utterances and intents to the same semantic vector space,
and then classify utterances based on their proximity to intent labels in that
space. Similarly, the authors in Gangal et al. (2019) employ the outlier
detection algorithm LOF Breunig et al. (2000) and likelihood ratios for
identifying out-of-domain test examples. While these works showed promising
results for intent detection when training data is unavailable for some
intents, they assume that all utterances faced at inference time imply unseen
intents only. Extending such works to remove the aforementioned assumption is
nontrivial. Our model does not assume knowledge of whether an utterance
implies a seen or an unseen intent at inference time.

Generalized Zero-shot Intent Detection. To the best of our knowledge, the
authors in Liu et al. (2019) proposed the first work that specifically targets
the GZS intent detection setting. They attempt to make their model
generalizable to unseen intents by adding a dimensional attention module to a
capsule network and learning generalizable transformation matrices from seen
intents. Recently, the authors in Yan et al. (2020) proposed using a density-
based outlier detection algorithm LOF Breunig et al. (2000) and semantic-
enhanced Gaussian mixture model with large margin loss to learn class-
concentrated embeddings to detect unseen intents. In contrast, we leverage
rich commonsense knowledge graph to capture deep semantic and discriminative
relationships between utterances and intents, which significantly reduces the
bias towards classifying unseen intents into seen ones. In a related, but
orthogonal, line of research, the authors in Ma et al. (2019); Li et al.
(2020); Gulyaev et al. (2020) addressed the problem of intent detection in the
context of dialog state tracking where dialog state and conversation history
are available in addition to an input utterance. In contrast, this work and
the SOTA models we compare against in our experiments only consider an
utterance without having access to any dialog state elements.

##  7 Conclusion

We have presented an accurate generalized zero-shot intent detection model.
Our extensive experimental analysis on three intent detection benchmarks shows
that our model is 30.36% to 58.50% more accurate than the SOTA model for
unseen intents. The main novelty of our model is its utilization of
relationship meta-features to accurately identify matching utterance-intent
pairs with very limited reliance on training data, and without making any
assumption on whether utterances imply seen or unseen intents at inference
time. Furthermore, our idea of integrating Positive-Unlabeled learning in GZS
intent detection models further improves our models’ performance, and
significantly improves the accuracy of existing models as well.

## References

  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Advances in neural information processing systems_ , pages 2787–2795.
  * Breunig et al. (2000) Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. 2000.  Lof: identifying density-based local outliers.  In _Proceedings of the 2000 ACM SIGMOD international conference on Management of data_ , pages 93–104.
  * Cer et al. (2018) Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Guajardo-Cespedes, Steve Yuan, Chris Tar, et al. 2018\.  Universal sentence encoder.  _arXiv preprint arXiv:1803.11175_.
  * Chen et al. (2016) Yun-Nung Chen, Dilek Hakkani-Tür, and Xiaodong He. 2016.  Zero-shot learning of intent embeddings for expansion by convolutional deep structured semantic models.  In _2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 6045–6049. IEEE.
  * Chen et al. (2013) Zhiyuan Chen, Bing Liu, Meichun Hsu, Malu Castellanos, and Riddhiman Ghosh. 2013\.  Identifying intention posts in discussion forums.  In _Proceedings of the 2013 conference of the North American chapter of the association for computational linguistics: human language technologies_ , pages 1041–1050.
  * Coucke et al. (2018) Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, et al. 2018.  Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces.  _arXiv preprint arXiv:1805.10190_.
  * Dauphin et al. (2013) Yann N Dauphin, Gokhan Tur, Dilek Hakkani-Tur, and Larry Heck. 2013.  Zero-shot learning for semantic utterance classification.  _arXiv preprint arXiv:1401.0509_.
  * Elkan and Noto (2008) Charles Elkan and Keith Noto. 2008.  Learning classifiers from only positive and unlabeled data.  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 213–220.
  * Farooq et al. (2020) Umar Farooq, A. B. Siddique, Fuad Jamour, Zhijia Zhao, and Vagelis Hristidis. 2020\.  App-aware response synthesis for user reviews.  In _2020 IEEE International Conference on Big Data (Big Data)_ , pages 699–708.
  * Felix et al. (2018) Rafael Felix, Vijay BG Kumar, Ian Reid, and Gustavo Carneiro. 2018.  Multi-modal cycle-consistent generalized zero-shot learning.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 21–37.
  * Ferreira et al. (2015) Emmanuel Ferreira, Bassam Jabaian, and Fabrice Lefevre. 2015.  Online adaptative zero-shot learning spoken language understanding using word-embedding.  In _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 5321–5325. IEEE.
  * Frome et al. (2013) Andrea Frome, Greg S Corrado, Jon Shlens, Samy Bengio, Jeff Dean, Marc’Aurelio Ranzato, and Tomas Mikolov. 2013.  Devise: A deep visual-semantic embedding model.  In _Advances in neural information processing systems_ , pages 2121–2129.
  * Gangal et al. (2019) Varun Gangal, Abhinav Arora, Arash Einolghozati, and Sonal Gupta. 2019.  Likelihood ratios and generative classifiers for unsupervised out-of-domain detection in task oriented dialog.  _arXiv preprint arXiv:1912.12800_.
  * Gulyaev et al. (2020) Pavel Gulyaev, Eugenia Elistratova, Vasily Konovalov, Yuri Kuratov, Leonid Pugachev, and Mikhail Burtsev. 2020.  Goal-oriented multi-task bert-based dialogue state tracker.  _arXiv preprint arXiv:2002.02450_.
  * Gupta et al. (2019) Arshit Gupta, John Hewitt, and Katrin Kirchhoff. 2019.  Simple, fast, accurate intent classification and slot labeling for goal-oriented dialogue systems.  In _Proceedings of the 20th Annual SIGdial Meeting on Discourse and Dialogue_ , pages 46–55.
  * Kazemi and Poole (2018) Seyed Mehran Kazemi and David Poole. 2018.  Simple embedding for link prediction in knowledge graphs.  In _Advances in neural information processing systems_ , pages 4284–4295.
  * Kim et al. (2016) Joo-Kyung Kim, Gokhan Tur, Asli Celikyilmaz, Bin Cao, and Ye-Yi Wang. 2016.  Intent detection using semantically enriched word embeddings.  In _2016 IEEE Spoken Language Technology Workshop (SLT)_ , pages 414–419. IEEE.
  * Kumar et al. (2017) Anjishnu Kumar, Pavankumar Reddy Muddireddy, Markus Dreyer, and Björn Hoffmeister. 2017.  Zero-shot learning across heterogeneous overlapping domains.  In _INTERSPEECH_ , pages 2914–2918.
  * Li et al. (2020) Miao Li, Haoqi Xiong, and Yunbo Cao. 2020.  The sppd system for schema guided dialogue state tracking challenge.  _arXiv preprint arXiv:2006.09035_.
  * Liu and Lane (2016) Bing Liu and Ian Lane. 2016.  Attention-based recurrent neural network models for joint intent detection and slot filling.  _arXiv preprint arXiv:1609.01454_.
  * Liu et al. (2019) Han Liu, Xiaotong Zhang, Lu Fan, Xuandi Fu, Qimai Li, Xiao-Ming Wu, and Albert YS Lam. 2019.  Reconstructing capsule networks for zero-shot intent classification.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4801–4811.
  * Ma et al. (2019) Yue Ma, Zengfeng Zeng, Dawei Zhu, Xuan Li, Yiying Yang, Xiaoyuan Yao, Kaijie Zhou, and Jianping Shen. 2019.  An end-to-end dialogue state tracking system with machine reading comprehension and wide & deep classification.  _arXiv preprint arXiv:1912.09297_.
  * Peters et al. (2018) Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _Proc. of NAACL_.
  * PyTorch (2020) PyTorch. 2020.  torch.optim — pytorch 1.3.0 documentation.  https://pytorch.org/docs/stable/optim.html#torch.optim.lr_scheduler.ReduceLROnPlateau.  (Accessed on 11/12/2020).
  * Rastogi et al. (2019) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2019.  Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset.  _arXiv preprint arXiv:1909.05855_.
  * Ravuri and Stolcke (2015) Suman Ravuri and Andreas Stolcke. 2015.  Recurrent neural network and lstm models for lexical utterance classification.  In _Sixteenth Annual Conference of the International Speech Communication Association_.
  * Sabour et al. (2017) Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. 2017.  Dynamic routing between capsules.  In _Advances in neural information processing systems_ , pages 3856–3866.
  * Siddique et al. (2020) A. B. Siddique, Samet Oymak, and Vagelis Hristidis. 2020.  Unsupervised paraphrasing via deep reinforcement learning.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’20, page 1800–1809, New York, NY, USA. Association for Computing Machinery.
  * Siddique et al. (2021) A.B. Siddique, Fuad Jamour, and Vagelis Hristidis. 2021.  Linguistically-enriched and context-aware zero-shot slot filling.  In _Proceedings of the Web Conference 2021_ , New York, NY, USA. Association for Computing Machinery.
  * Socher et al. (2013) Richard Socher, Milind Ganjoo, Christopher D Manning, and Andrew Ng. 2013.  Zero-shot learning through cross-modal transfer.  In _Advances in neural information processing systems_ , pages 935–943.
  * Speer et al. (2016) Robyn Speer, Joshua Chin, and Catherine Havasi. 2016.  Conceptnet 5.5: An open multilingual graph of general knowledge.  _arXiv preprint arXiv:1612.03975_.
  * Speer et al. (2017) Robyn Speer, Joshua Chin, and Catherine Havasi. 2017.  Conceptnet 5.5: An open multilingual graph of general knowledge.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction.  International Conference on Machine Learning (ICML).
  * Vedula et al. (2020) Nikhita Vedula, Nedim Lipka, Pranav Maneriker, and Srinivasan Parthasarathy. 2020\.  Open intent extraction from natural language interactions.  In _Proceedings of The Web Conference 2020_ , pages 2009–2020.
  * Wang et al. (2015) Jinpeng Wang, Gao Cong, Wayne Xin Zhao, and Xiaoming Li. 2015.  Mining user intents in twitter: A semi-supervised approach to inferring intent categories for tweets.  In _Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence_ , AAAI’15, page 318–324. AAAI Press.
  * Williams (2019) Kyle Williams. 2019.  Zero shot intent classification using long-short term memory networks.  _Proc. Interspeech 2019_ , pages 844–848.
  * Xia et al. (2018) Congying Xia, Chenwei Zhang, Xiaohui Yan, Yi Chang, and Philip S Yu. 2018.  Zero-shot user intent detection via capsule neural networks.  _arXiv preprint arXiv:1809.00385_.
  * Xu and Sarikaya (2013) Puyang Xu and Ruhi Sarikaya. 2013.  Convolutional neural network based triangular crf for joint intent detection and slot filling.  In _2013 ieee workshop on automatic speech recognition and understanding_ , pages 78–83. IEEE.
  * Yan et al. (2020) Guangfeng Yan, Lu Fan, Qimai Li, Han Liu, Xiaotong Zhang, Xiao-Ming Wu, and Albert YS Lam. 2020.  Unknown intent detection using gaussian mixture model with an application to zero-shot intent classification.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1050–1060.
  * Yazdani and Henderson (2015) Majid Yazdani and James Henderson. 2015.  A model of zero-shot learning of spoken language understanding.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 244–249.
  * Zang et al. (2020) Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen. 2020.  MultiWOZ 2.2 : A dialogue dataset with additional annotation corrections and state tracking baselines.  In _Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI_ , pages 109–117, Online. Association for Computational Linguistics.
  * Zhang et al. (2018) Chenwei Zhang, Yaliang Li, Nan Du, Wei Fan, and Philip S Yu. 2018.  Joint slot filling and intent detection via capsule neural networks.  _arXiv preprint arXiv:1812.09471_.

##  Appendix A Appendices

This section provides supplementary details on various aspects of this paper.
First, we provide more details on the commonsense knowledge graph we have used
as a source of knowledge on semantic relatedness of concepts. Then, we
describe the specifics of the datasets we used in our evaluation and our
preprocessing procedures. Finally, we provide the details on handling a
special case when utterances do not imply intents.

###  A.1 Knowledge Graph Details

Although creating and maintaining knowledge graphs is laborious and time
consuming, the immense utility of such graphs has led many researchers and
institutions to make the effort of building and maintaining knowledge graphs
in many domains, which lifts the burden off of other researchers and
developers who utilize these graphs. For tasks that involve commonsense
reasoning such as _generalized zero-shot_ intent detection, the ConceptNet
Speer et al. (2016) commonsense knowledge graph stands out as one of the most
popular and freely available resources. ConceptNet originated from the
crowdsourcing project Open Mind Common Sense, and includes knowledge not only
from crowdsourced resources but also expert-curated resources. It is available
in $10$ core languages, and $68$ more common languages. It was employed to
show state-of-the-art results at SemEval 2017 Speer et al. (2017). In this
work, we considered $35$ relation types to generate our relationship meta-
features. The relation types are: $RelatedTo$, $FormOf$, $IsA$, $PartOf$,
$HasA$, $UsedFor$, $CapableOf$, $AtLocation$, $Causes$, $HasSubevent$,
$HasFirstSubevent$, $HasLastSubevent$, $HasPrerequisite$, $HasProperty$,
$MotivatedByGoal$, $ObstructedBy$, $Desires$, $CreatedBy$, $Synonym$,
$Antonym$, $DistinctFrom$, $DerivedFrom$, $SymbolOf$, $DefinedAs$, $MannerOf$,
$LocatedNear$, $HasContext$, $SimilarTo$, $EtymologicallyRelatedTo$,
$EtymologicallyDerivedFrom$, $CausesDesire$, $MadeOf$, $ReceivesAction$,
$ExternalURL$, and $Self$.

The relationship meta-feature generator produces $35\times 4=140$ dimension
vector for each utterance-intent pair. Specifically, we generate
relationships: (_i_) from utterance to Object (i.e., Object part in intent
label); (_ii_) utterance to Action (i.e., Action part in intent label); and
(_iii_) Object to utterance; (_iv_) Action to utterance.

A knowledge graph may not have redundant, but necessary information. For
example, a knowledge graph may have the entry ${\langle}\texttt{movie},$
$IsA,$ $\texttt{film}{\rangle}$ but not ${\langle}\texttt{film},$ $IsA,$
$\texttt{movie}{\rangle}$ or vice-versa, because one triple can be inferred
from the other based on background knowledge (i.e., symmetric nature of the
$IsA$ relation). Similarly, the triple ${\langle}\texttt{movie},$ $HasA,$
$\texttt{subtitles}{\rangle}$ can be used to infer the triple
${\langle}\texttt{subtitles},$ $PartOf,$ $\texttt{movie}{\rangle}$ based on
the background knowledge (i.e., inverse relation between $HasA$ and $PartOf$).
So, if this kind of redundant information (i.e., complementing entries for all
such triples) is not available in the knowledge graph itself, there is no way
for the model to learn these relationships automatically. To overcome this
issue, we incorporate the background knowledge that each of the relation types
$IsA$, $RelatedTo$, $Synonym$, $Antonym$, $DistinctFrom$, $LocatedNear$,
$SimilarTo$, and $EtymologicallyRelatedTo$ is symmetric; and that the relation
types $PartOf$ and $HasA$ are inversely related in our link prediction model
as described in Kazemi and Poole (2018).

###  A.2 Training the Link Predictor

The training data for a link prediction model is prepared as follows. First,
the triples in the input knowledge graph are assigned a label of $1$. Then,
negative examples are generated by corrupting true triples (i.e., modifying
the head or tail of existing triples) and assigning them a label of $-1$
Bordes et al. (2013). Finally, we train our LP using the generated training
data by minimizing the L$2$ regularized negative log-likelihood loss of
training triples Trouillon et al. (2016).

###  A.3 Datasets Preprocessing

SNIPS Natural Language Understanding benchmark (SNIPS) Coucke et al. (2018) is
a commonly used dataset for intent detection, whereas Dialogue System
Technology Challenge 8, Schema Guided Dialogue dataset (SGD) Rastogi et al.
(2019) and Multi-Domain Wizard-of-Oz (MultiWOZ) Zang et al. (2020) were
originally proposed for the task of dialogue state tracking. For SGD and
MultiWOZ, we perform a few trivial preprocessing steps to extract utterances
that contain intents, along with their labels, and use them for the task of
generalized zero-shot intent detection. First, we provide the details on the
preprocessing steps specific to the SGD and MultiWOZ dataset and then describe
the preprocessing steps that are common for all datasets.

Steps for SGD and MultiWOZ. To maintain consistency with the previous work on
intent detection, we extract only the utterances where user/system expresses
an intent, and discard the rest from the original SGD and MultiWOZ datasets.
The dialogue state contains a property “active_intent” that keeps track of the
user’s current intent. After each user utterance, we compare dialogue states
to check for the expression of a new user intent, i.e., whether the value of
the “active_intent” is modified. Whenever the user expresses a new intent, the
value of the “active_intent” is updated. Moreover, sometimes, the bot (i.e.,
system) also offers new intents to the user (e.g., offering reserving a table
to the user, who has successfully searched for a restaurant), which is tracked
in the system actions property “act = OFFER_INTENT”, and “values =
$<$new_intent$>$”. We also keep such system utterances.

Common Steps. We perform some standard preprocessing steps on all the
datasets. We use spaCy to tokenize the sentences. Since intent labels are
given in the “ActionObject” format, we tokenize them into “Action Object”
phrases before feeding them into our model. For example, the intent labels
“FindHotel” and “RateBook”, are transformed into “Find Hotel” and “Rate Book”,
respectively. Note that some Objects parts of intent labels are compound.
Consider the intent label “SearchOneWayFlight” whose Action is “Search” and
Object is “OneWayFlight”. In such cases, our relationship meta-features
generator computes meta-features for each part of the compound object then
averages them to produce the Object meta-features vector. In the previous
example, “OneWayFlight” meta-features vector is computed as the average of the
meta-features of “OneWay” and “Flight”.

###  A.4 Intent Existence Prediction

In real human-to-human or human-to-machine conversations, utterances do not
necessarily imply intents. Most existing intent detection models formulate the
problem as a classification problem where utterances are assumed to imply an
intent, which limits utility of such models in practice. In what follows, we
describe a simple method for extending intent detection models (including
ours) to accommodate the case when utterances do not necessarily imply
intents. We propose to do binary classification as a first step in intent
detection, where a binary classifier is used to identify utterances that do
not imply an intent. To validate the viability of this proposal, we
experimented with several binary classifiers. To train the classifiers, we
created datasets of positive and negative examples from seen intents data;
positive examples are utterances that imply intents, and negative examples are
utterances that do not have intents (See Section A.3 for details on
identifying utterances that imply intents). For the SGD dataset, we used the
standard train/test splits, and for the MultiWOZ dataset, we used the same
splits described in the GZS setting. We report in Table 4 the average F1 score
over 5 runs of several binary classifiers for the SGD and the MultiWOZ
datasets. All classifiers use ELMo Peters et al. (2018) and POS tag
embeddings. These results show that intent existence classification can be
done accurately using the available training data; consequently, intent
detection models can be easily and reliably extended to support the case when
some input utterances do not imply intents.

Method | SGD | MultiWOZ
---|---|---
CNN | 0.9497 | 0.9512
GRU | 0.9528 | 0.9619
LSTM | 0.9512 | 0.9607
Bi-LSTM | 0.9525 | 0.9621
Table 4: F1 score for intent existence binary classifiers.


*[1]#1

# An FPGA Architecture for Online Learning
using the Tsetlin Machine

Samuel Prescott1, Adrian Wheeldon2, Rishad Shafik3, Tousif Rahman3,
Alex Yakovlev3 & Ole-Christoffer Granmo4

1 University College London, UK 2 The University of Edinburgh, UK
3Newcastle University, UK 4 The University of Agder, Norway

###### Abstract

There is a need for [ ([)]ML models to evolve in unsupervised circumstances.
New classifications may be introduced, unexpected faults may occur, or the
initial dataset may be small compared to the data-points presented to the
system during normal operation. Implementing such a system using neural
networks involves significant mathematical complexity, which is a major issue
in power-critical edge applications. This paper proposes a novel []FPGA
infrastructure for online learning, implementing a low-complexity []ML
algorithm called the []TM. This infrastructure features a custom-designed
architecture for run-time learning management, providing on-chip offline and
online learning. Using this architecture, training can be carried out on-
demand on the []FPGA with pre-classified data before inference takes place.
Additionally, our architecture provisions online learning, where training can
be interleaved with inference during operation. []TM training naturally
descends to an optimum, with training also linked to a threshold hyper-
parameter which is used to reduce the probability of issuing feedback as the
[]TM becomes trained further. The proposed architecture is modular, allowing
the data input source to be easily changed, whilst inbuilt cross-validation
infrastructure allows for reliable and representative results during system
testing. We present use cases for online learning using the proposed
infrastructure and demonstrate the energy/performance/accuracy trade-offs.

##  1 Introduction

Traditional []ML models are trained before use with an initial set of pre-
classified data, so called _batch learning_. A recent concept has been to
develop []ML models more akin to human learning, where the model learns over
time and adapts to changes [8]. This concept is called _continual or online
learning_ [4]. It involves training using data as it arrives at the system. In
batch learning systems this data would only be used for inference, but online
learning evolves the training process under various real-world circumstances
[14]. These may include introducing new classes after deployment of the system
[19], mitigating faults during runtime [11], and learning new information from
datapoints that were not available at design time [2].

However, enabling online learning is challenging for the following two major
reasons. Firstly, the learning system requires architectural provisions for
managing (i.e. storing and retrieving) a large volume of data at real-time
[14, 9]. Secondly, the online training process aimed at high learning accuracy
is typically characterized by iterative arithmetic routines, such as those in
neural networks, together with the associated hyperparameter optimisations
[16]. When implemented in software, these can dramatically increase the
performance and energy costs – which can render online learning infeasible
[14]. As such, there is growing demand of accelerated hardware architectures,
implemented in []ASIC or []FPGA.

The []TM is a new []ML algorithm based around propositional logic and
reinforcement learning [5]. With parallel logic based structures and low-
complexity learning controls by only 2 hyperparameters, the []TM algorithm has
recently shown competitive classification accuracy and energy consumption
across a wide range of applications when compared with neural networks [17, 1,
13, 7, 18] (see Section 2 for more details on the []TM). In this paper, we aim
to leverage these properties for a low-energy online learning infrastructure.
Specifically, we present FPGA []FPGA architecture that forms part of the []TM
ecosystem to address the following three goals: i) acceleration of []TM
inference with the capability of training online; ii) acceleration of online
hyper-parameter search for faster prototyping and cross-validation of
datasets; and iii) as RTL []RTL prototyping platform for []ASIC-oriented
designs based on the []TM.

### Contributions:

This paper presents a novel, online learning accelerator architecture
implemented using []TM. Our aim is to achieve at-speed learning capability,
while also maintaining low energy costs. _The main contributions of the paper
are:_

  * •

an []FPGA tailored architectural design for an online learning system,
featuring both data and learning management subsystems;

  * •

a detailed analysis of supervised online training in the []TM; and

  * •

experimental validations and demonstrations of the architecture using a number
of use cases: i) introduction of new training data including operation in
supervised mode; ii) introduction of a new class during runtime; and iii)
mitigation of faults in []TA and clause outputs.

The remainder of this paper is organized as follows. Section II briefly
introduces []TM. Section III and IV detail the proposed online learning
architecture and integrated system operation. Section V discusses experimental
results, presenting 3 different use cases. Section VI highlights some key
performance tradeoffs, while Section VII concludes the paper.

##  2 The Tsetlin Machine

The []TM is ML []ML algorithm which learns patterns from data features in
Boolean form rather than binary numbers. This allows for the algorithm to
process data through propositional logic. The main inference component of the
[]TM is the _clause_ which composes an * gateand expression of the input
Boolean features and their complements. The []TM comprises many clauses, each
producing a vote. The composition of each clause is controlled by a vector of
_include_ bits (see Figure 1). These bits are parameters that are learnt by
teams of []TA.

Clauses Automaton Teams TATAMajority VotingArgmaxClause ResultsincludeClass
ConfidenceFeedbackClassificationInput FeaturesRandomizerLearningFaultInjection
Figure 1: Overview of the Tsetlin machine (TM) architecture, with []TA fault
injection highlighted later discussed in Section 3.1.2.

Each clause can produce a vote for its class. Half of the clauses can vote
positively, while the other half of the clauses can vote negatively. The
inclusion of inhibition in the voting system enables non-linearity in the
inference process. A majority vote gives an indication of class confidence,
which is used to classify the input data and influence future decisions of the
automata through the feedback mechanism [5].

The []TA is a class of finite reinforcement automaton [12]. It produces an
_exclude_ output for states below the midpoint, and _include_ for states above
the midpoint. The []TA receives a penalty or reward from the feedback
mechanism based on the current state of the []TM. Continued rewards in the end
states cause the []TA to saturate. A penalty in one of the midstates ($n$ or
$n+1$) causes the []TA to transition across the decision boundary — between
exclude and include.

The []TM controls []TA feedback through the hyperparameters $T$ and $s$. $T$
can be thought of as a target for the number of clauses to activate.
Hyperparameter $s$ introduces an element of stochasticity, and therefore
exploration, into the []TA’s behaviour. More details on []TM can be found in
[5].

##  3 FPGA Accelerator Architecture

We present a modular []TM architecture targeted at []FPGA (Figure 2). The
architecture as implemented is capable of both offline and online training to
satisfy our need for low energy and at-speed learning as discussed in Section
1. Below we describe the building blocks of the architecture in details.

Figure 2: Overview of the proposed online learning architecture.

###  3.1 Tsetlin Machine

The []TM forms the core of the architecture. The []TM hyperparameters such as
number of classes, number of clauses and number of []TA states are
parameterized at design time to allow arbitrarily-sized machines to be
synthesized. The sensitivity and threshold hyperparameters, $s$ and $T$, are
controllable during runtime via []IO ports. We added two additional features
to the []TM to improve development.

####  3.1.1 Over-Provisioning Resources

To reduce the need for re-synthesis and to allow adaptation on-the-fly,
resources can be over-provisioned. Classes are controlled by a pre-synthesis
parameter and can be over-provisioned by not introducing the []TM to
additional classifications during training, which can be utilised to introduce
new classifications during online operation. Clauses are controlled by a
maximum clause number pre-synthesis parameter and a clause number port. They
can be over-provisioned by using a number of clauses below the maximum at the
clause number port, which can be increased to the maximum during runtime if
required. The extent of over-provisioning is application specific.

####  3.1.2 Fault Injection

Faults present a major issue in systems, therefore we created a way to allow
faults to be injected into the system to aid development of fault-tolerant
systems [10]. In order to simulate faults in our system we add extra logic to
the []TM which forces the []TA outputs. Each []TA’s output action is a $1$ or
$0$. In order to simulate stuck-at faults we introduce * gateand/or gates to
the output. If the ANDed signal is $0$, the output is always $0$ and if the
ORed signal is $1$, the []TA output is always $1$. For fault-free []TA
operation, the ANDed signal should be $1$ and the ORed signal $0$.

A fault controller module provides two mappings for these signals individual
to each []TA. These mappings are initially set to $1$ for AND and $0$ for OR,
and can then be updated as required. Each []TA is addressable and connected to
the microcontroller interface IP, providing access to these mappings from the
microcontroller code. This allows various fault configurations to be injected
without re-synthesis of the []FPGA logic.

###  3.2 Tsetlin Machine Management

The operation of the system is controlled by two main state machines, one for
high-level system operations and one for low-level, per data-point, state
machine. The high-level manager controls operation of the system as a whole,
whereas the low-level manager controls the I/O and operation of the []TM
itself.

###  3.3 Accuracy Analysis

The accuracy analysis block records the number of errors and total epochs per
accuracy analysis cycle. An additional block records the history of these
values during simulation in []RAM, whereas these values can be immediately
offloaded to the microcontroller when implemented on an []FPGA to reduce []RAM
usage.

###  3.4 Offline Data Input

####  3.4.1 Class Filtering

In Section 5.2 we investigate the advantages of online training when
introducing a new class. Therefore, a filtering subsystem was created,
controlled by an external enable signal, to remove a certain class if desired.

####  3.4.2 Memory Management

The []TM management subsystem can request data from different sources with
data request signals, with the details of these sources abstracted to
different modules. Therefore, we created a memory management subsystem to
retrieve and parse the required offline data from onboard memory and present
it to the []TM management when required, abstracting the memory interface
itself away from the management subsystem.

###  3.5 Online Data Input

The online data source of a system is application dependent as it may come
from a microcontroller or other IP and sensors. Therefore the online data
input subsystem was abstracted into multiple layers. This also included the
filter IP discussed for the Offline Data Input subsystem.

####  3.5.1 Online Data Manager

The []TM management subsystem requests each row of online data when it
requires it. The online data manager provides this data from the online data
source via a cyclic buffer.

####  3.5.2 Online Input Data Buffer

To allow the []TM management to be able to periodically check model accuracy,
we implemented a cyclic buffer to temporarily store online data in []RAM to
prevent datapoints being ignored by the system during accuracy analysis
processes.

####  3.5.3 Online Input Parser

For experimentation, online data was stored in on-chip ROM, accessed via a
cross-correlation interface. We created specific IP to retrieve and parse each
row of data, providing it to the system’s aforementioned buffer system. Due to
this abstraction, this IP can be replaced depending on the online input source
without the need to modify the other subsystems.

###  3.6 Memory

####  3.6.1 Block Memory Manager - Cross-Validation

The pattern recognition and inference capabilities of a machine learning model
are important. A common way of testing this is to use cross-correlation, where
the full dataset is split into subsets for training and validation. These
subsets will be referred to as the three data _sets_.

To accommodate both offline and online training, in this system sets are
required for offline training, validation and online training. For example,
the iris dataset used to acquire our results has 150 unique datapoints. These
sets were allocated 30, 60, 60 respectively.

When training []ML models, data biases can have a significant effect on
training [6]. For example, a specific row of data may result in the []TM
incorrectly classifying a future row of data that would have been classified
correctly if the former row had not been used. Additionally, there may be
uneven distributions of classes and patterns across these three sets.

Therefore, we took action to mitigate these effects to produce results
actually representative of how the system may behave in different scenarios.

We split the full dataset into small subsets. These will be referred to as
_blocks_. The length of each block needed to be a factor of each set size, for
the iris example the highest common factor, $30$, was chosen. This resulted in
$150/30=5$ blocks which could be combined as required to form the larger sets.

The experimentation was re-run for various orderings of these blocks, with the
results averaged. The maximum number of possible orderings in this example
$5!=120$, so we created a subsystem that could be provided with a set of
starting orderings which could then be easily manipulated to produce the full
number of orderings.

####  3.6.2 Onboard ROM

Each block was stored in a separate block ROM, mapped to via the cross-
validation IP. Each block ROM was dual port to allow the Online Training set
to be used in online training as well as accuracy analysis.

###  3.7 System/Microcontroller Interface

We created a general piece of IP to provide the on-board microcontrolelr with
access so a set of 32-bit I/O registers via an AXI bus. These registers were
connected via signals to more specific IP to separate and combine signals into
these registers and connect them to the required ports within the system.

Additionally, we implemented a handshaking itnerface between the
microcontroller and this more spcific IP. The IP sends a signal to the
microcontroller informing it that certain registers are ready to be read from,
then pauses the system whilst waiting for the microcontroller to respond. The
microcontroller can then read the registers and assert a different signal to
convey that the registers have been read successfully. The system detects this
signal and resumes operation. This allows the system to operate at high speed
without worrying about the microcontroller’s speed of operation and race
conditions.

###  3.8 Microcontroller

To reduce development times by reducing the need for re-synthesis and
implementation, we made various system parameters controllable and adjustable
via a connected microcontroller. Additionally, this allows dynamic control of
the system, for example the ability to reconfigure over-provisioned resources.
The microcontroller also provides a medium to retrieve accuracy information by
communicating with a host PC via a connected UART interface and provides an
established starting point for acquiring online data via the microcontroller
interface. This could provide access to data from sources connected via UART
or Ethernet, for example.

##  4 System Operation

Figure 3: System execution flow.

The high-level []TM manager controls execution flow. After initial training
using the offline training set, the accuracy is analyzed in terms of the
training data and, optionally: a validation set (for inference validation on
unseen data) and the online training set. Online learning is then executed for
a set number of datapoints before accuracy analysis is re-run, as shown in
Figure 3. This information can be used to determine the effectiveness of
online learning over time and with different configurations, as well as to
detect possible faults that have occurred. In offline training and accuracy
accuracy analysis for all sets, data is taken from the Offline Input
subsystem. During online training, data is taken from the Online Input
subsystem.

##  5 Experimental Results and Use Cases

The effectiveness of the system was investigated and demonstrated through
three possible use cases. For all experimentation, the _iris_ dataset was used
($16$ booleanised inputs, $3$ classifications, $150$ unique datapoints) with
the same system parameters: $16$ clauses, $s$ hyper-parameter $1.375$ for
offline and $1$ for online, $T$ hyper-parameter $15$, $10$ offline training
iterations and 120 cross-correlated orderings with the results averaged. These
values were carefully chosen from offline experiments as they demonstrated
good learning efficacy for the particular dataset. An additional promising
application of this system, with its cross-validation infrastructure, is rapid
hyper-parameter search. The fast execution time allows entire datasets to be
analyzed in a matter of seconds, allowing the optimum hyper-parameters for a
given dataset to be discovered within a short period of time.

###  5.1 Limited Initial Training Data

In many applications, the number of initial data points may be limited. Online
learning provides further training during operation.

We investigated the effect of online learning using labelled data. Often it
may be possible to acquire some labelled data at runtime, for example from
user feedback or to an []IoT edge node from a central system. Alternatively,
it may be possible to use a confident estimated classification as the class
for a set of inputs.

An offline training set of length $20$ was initially used to train the []TM
over $10$ iterations. The accuracy was then analyzed for this offline training
set, a validation set and an online training set. Online training with $60$
labelled datapoints was carried out for a single iteration of the set, with a
small $s$ hyper-parameter value of $1$. A lower $s$ value increases the
likelihood of inaction, so overall there will be a bias away from issuing
feedback when a low $s$ value is used, resulting in reduced power consumption.
The accuracy was re-analyzed and the process repeated for 16 iterations of the
online training set. Figure 4 shows the resulting effect on accuracy due to
this online training. It shows the accuracy of the validation and online
training sets increased similarly by approximately $12\%$, unlike the offline
training set accuracy which increased less significantly by only approximately
$5\%$.

Figure 4: The effect of online learning with labelled data on accuracy.
Starting accuracies: offline training set $83\%$, validation set $79.5\%$ and
online training set $79.5\%$.

The accuracy of the online training set increased the most as the training was
being performed using this set, so the feedback applied to the []TAs was
targeted at these particular datapoints. The patterns contained within the
full dataset were spread across the three sets. Therefore, training on the
online training set resulted in an increase in accuracy for the validation set
due to these shared patterns being exposed to the []TM during online training.
As the offline training set was used for initial offline training, the []TAs
were initially configured for the offline training set datapoints meaning the
offline training set had the largest initial accuracy. When training with the
online training set, the []TA states changed to also fit the online training
set. The accuracy for the offline training set ultimately increased, again due
to patterns being shared across the three sets, but not as significantly as
the other two. This was primarily due to the higher initial accuracy, but also
links to catastrophic forgetting where the model may lose its fit for old data
as new data is learned [3]. It could be advantageous to use a replay method,
continuing training with occasional datapoints from the offline training set
during online operation [3].

###  5.2 Unseen Class Introduction

It is possible for additional classes to be introduced during online
operation. Traditionally this support would not be possible as the system
would require full retraining, but with online learning the system can adapt
dynamically.

For testing, we created the class filter IP, in Section 3.4.1, to remove a
desired class during offline training and initial online operation, to
experiment using online learning in this scenario by introducing a previously
unseen classification midway through online operation.

We again used labelled data in the online training set, but further
experimentation could involve analyzing class confidence to determine the
likelihood a datapoint belongs to an unseen classification and provide
appropriate feedback.

Initially, the accuracy over $16$ online learning iterations was analyzed, but
with one classification filtered out. $30$ datapoints were available in the
offline training set, but only $20$ were used in previous experimentation.
Therefore, the size of the set after filtering one of three classes out was
still approximately $20$. The validation and online training sets had no such
redundancy, so were each reduced to approximately $40$ in size when one of
three datasets was filtered out. The results of this are demonstrated in
Figure 5, showing an increase in accuracy over online training. Oscillations
were present, due to the small nature of the dataset and relatively small
number of online iterations, but this provided a suitable baseline. As
expected, the validation set increased in accuracy less than the online
training set, but the accuracy of the offline training set increased the most
significantly. As the initial accuracy was lower for it in this experiment, it
allowed the accuracy to increase further during online operation.

Figure 5: Accuracy results with the _iris_ dataset’s $0$ class filtered from
the three sets for the entire operation. Starting accuracies: offline training
set $75.75\%$, validation set $79.66\%$ and online training set $79.66\%$.

We repeated this to produce a second baseline with online learning disabled
and a new classification introduced after $5$ online iterations, with a
decrease in accuracy observed in Figure 6 for all sets when the unseen class
was introduced. The decrease was the same for the validation and online
training sets, but was different for the offline training set with the offline
training set being a third the size of the other two contributing to this
discrepancy.

Figure 6: Effect on accuracy of introducing new classification at runtime
(after $5$ online iterations) with online training disabled. Starting
accuracies: offline training set $75.75\%$, validation set $79.66\%$ and
online training set $79.66\%$.

Finally, we combined these two experiments to observe the effect of labelled
online learning on []TM accuracy with the introduction of a class at runtime,
the results being observed in Figure 7. The accuracy initially increased
inline with the baseline in Figure 5 before the new class was introduced. When
the new class was introduced after $5$ online iterations, the accuracy briefly
decreased (after the new class was introduced, one iteration of online
training was executed before the accuracy was re-analyzed) whilst the []TM
began being trained with the online training set containing the new class. The
accuracy soon recovered, showing a significantly positive outcome compared to
without online training. The relative accuracy increase for these sets were
comparable after the point where the new class was introduced.

Figure 7: Effect of online training on new classification introduction.
Starting accuracies: offline training set $75.75\%$, validation set $79.66\%$
and online training set $79.66\%$.

###  5.3 Fault Mitigation

Faults can be major issues, especially in unsupervised edge nodes. An example
of a fault causing an issue within a []TM is a []TA getting stuck outputting
$0$ or $1$, regardless of the literal input to the []TA. A []TM relies on
stochasticity and majority voting, therefore there is more than one training
solution. So, if such a fault exists before training, the system can train
itself in a way that this []TA has little effect on the output. Therefore when
online learning is used, training continues after initial training, having the
potential to re-train “around" faulty []TAs. Faults can be injected into the
[]TM and the effects observed with and without online learning enabled.
Usually the number of faults is small, but for demonstration purposes a large
number of faults were injected at the same time.

####  5.3.1 Runtime fault mitigation using labelled online learning

A Python script was created and used to create an equal spread of fault
mappings across the []TAs. The []TM is effective at fault mitigation when
training [15], so to observe the effects of faults on a fully-trained system
the faults were injected after $5$ online iterations.

The faults injected consisted of forcing the output of $20\%$ of the []TAs to
$0$. The effect with online training disabled was observed in Figure 8, where
the accuracy decreased as expected. The difference in accuracy change between
the offline training set and the validation/online training sets was due to
the difference in set size.

Figure 8: Faults introduced after 5 online iterations, with online learning
disabled. 20% stuck at 0 faults evenly distributed across []TAs. Starting
accuracies: offline training set $83\%$, validation set $79.5\%$ and online
training set $79.5\%$.

This was repeated, but with online learning enabled. Figure 9 demonstrated
that the accuracy briefly fell (after the faults were injected, one iteration
of online training was executed before the accuracy was re-analyzed) before
starting to recover with further online iterations, with the final accuracy
increases after $16$ iterations being on par with the fault-free system
demonstrated in Figure 4. After faults were injected, the relative changes in
accuracy across the three sets were comparable. This was significantly better
than the offline learning demonstration in Figure 8, due to the stochasticity
and majority voting properties of the []TM: feedback is applied individually
for each []TA, so issues with other []TAs may result in feedback being applied
differently to non-faulty []TAs that it would have been otherwise, leading to
clause characteristics changing. For example, a clause voting against a
classification may change to cancel out a clause containing faults causing it
to always vote for a classification.

Figure 9: Faults introduced after 5 online iterations, with online learning
enabled. 20% stuck at 0 faults evenly distributed across []TAs. Starting
accuracies: offline training set $83\%$, validation set $79.5\%$ and online
training set $79.5\%$.

####  5.3.2 Further Mitigation Strategies

After every set number of online learning epochs, the []TM accuracy is
analyzed using the initial training data as well as unseen validation data.
This accuracy analysis can be used to enable/disable online learning, control
online learning sensitivity and to choose to fully retrain the []TM on-chip if
the accuracy has fallen below a certain threshold (i.e. significant faults
have occurred). Additionally, with over-provisioning of clauses, additional
clauses can be enabled for this retraining to further mitigate the effect of
faulty []TAs [15].

##  6 Performance and Power Consumption

The parallel nature of a hardware-implemented []TM is unrivalled by software
implementations due to the high degree of concurrency. Where a software
implementation cannot calculate all clause outputs at the same time, our
hardware []TM implementation takes just two clock cycles to complete inference
and feedback for all clauses and []TAs. The throughput of the []TM is one
datapoint per clock, requiring an additional clock cycle to buffer the I/O.
This decreases execution times from minutes, or longer, on a computer using a
software implementation down to a matter of seconds [17]. Whilst the system
can interface with a microcontroller, it contains handshake logic for this
interaction to allow the speed of microcontroller operation to be independent
from the speed of the hardware []TM. The only possible slowdown is stalling
during this handshaking process.

When inference or learning is not occurring, the []TM is clock-gated,
providing significant power consumption improvements. Additionally, clock
gating is used for the over-provisioned clauses and []TAs to reduce the power
consumption overhead when they remain unused. The estimated power consumption
for the experimental implementation on a Xilinx Zybo Z7-20 was 1.725W, of
which 1.4W was associated with the onboard microcontroller (using default tool
activity).

##  7 Conclusions

We demonstrated a new []TM based online learning hardware architecture,
implemented on []FPGAs, leveraging their flexibility to allow rapid
development. The architecture provides a fast and reliable way of utilizing
on-chip learning in both offline and online circumstances. Online learning was
demonstrated with labelled data, demonstrating its positive effects on
accuracy in three use cases. Three different use cases were presented in order
to validate the effectiveness and flexibility of the proposed architecture. We
showed that the architecture is capable of at-speed and low-power online
learning using a flower type detection dataset.

Additional research directions will involve experimentation with the []TM’s
classification confidence to apply feedback when using unlabelled online data,
as well as using the class confidences from each class to determine if
unlabelled data may belong to an unseen classification. Additionally, it may
be investigated how continuous accuracy analysis (every $N$ cycles test the
accuracy with a single piece of offline training data, maintaining a
cumulative average) can be used to detect faults and trigger system
retraining/resource re-provisioning and the impact of injecting faults at the
clause output level.

## References

  * [1] B. Bhattarai, O.-C. Granmo, and L. Jiao.  Measuring the Novelty of Natural Language Text Using the Conjunctive Clauses of a Tsetlin Machine Text Classifier.  arXiv:2011.08755 [cs], Nov. 2020.
  * [2] D. Biswas, V. Balagopal, R. Shafik, B. M. Al-Hashimi, and G. V. Merrett.  Machine learning for run-time energy optimisation in many-core systems.  In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017, pages 1588–1592. IEEE, 2017.
  * [3] M. Delange, R. Aljundi, M. Masana, S. Parisot, X. Jia, A. Leonardis, G. Slabaugh, and T. Tuytelaars.  A continual learning survey: Defying forgetting in classification tasks.  IEEE Trans. Pattern Anal. Mach. Intell., pages 1–1, 2021.
  * [4] Ó. Fontenla-Romero, B. Guijarro-Berdiñas, D. Martinez-Rego, B. Pérez-Sánchez, and D. Peteiro-Barral.  Online machine learning.  In Efficiency and Scalability Methods for Computational Intellect, pages 27–54. IGI Global, 2013.
  * [5] O.-C. Granmo.  The Tsetlin Machine – A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic.  arXiv:1804.01508 [cs], Apr. 2018.
  * [6] J. Gu and D. Oelke.  Understanding bias in machine learning.  arXiv preprint arXiv:1909.01866, 2019.
  * [7] J. Lei, A. Wheeldon, R. Shafik, A. Yakovlev, and O.-C. Granmo.  From arithmetic to logic based AI: A comparative analysis of neural networks and tsetlin machine.  In 2020 27th IEEE Int. Conf. Electron. Circuits Syst., 2020.
  * [8] M. London and J. W. Smither.  Empowered self-development and continuous learning.  Human Resource Management: Published in Cooperation with the School of Business Administration, The University of Michigan and in alliance with the Society of Human Resources Management, 38(1):3–15, 1999.
  * [9] S. Maheshwari, T. Rahman, A. Yakovlev, A. Rafiev, L. Jiao, O.-C. Granmo, et al.  Redress: Generating compressed models for edge inference using tsetlin machines.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023\.
  * [10] J. Mathew, R. Shafik, and D. Pradhan.  Energy-efficient fault-tolerant systems.  Springer USA, 2014.
  * [11] M. R. Napolitano, G. Molinaro, M. Innocenti, B. Seanor, and D. Martinelli.  A complete hardware package for a fault tolerant flight control system using online learning neural networks.  In Proceedings of the 1999 American Control Conference (Cat. No. 99CH36251), volume 4, pages 2615–2619. IEEE, 1999.
  * [12] K. S. Narendra and M. A. L. Thathachar.  Learning Automata: An Introduction.  Prentice-Hall, Inc., USA, 1989.
  * [13] R. Saha, O.-C. Granmo, V. I. Zadorozhny, and M. Goodwin.  A Relational Tsetlin Machine with Applications to Natural Language Understanding.  arXiv:2102.10952 [cs], Feb. 2021.
  * [14] D. Sahoo, Q. Pham, J. Lu, and S. C. Hoi.  Online deep learning: Learning deep neural networks on the fly.  arXiv preprint arXiv:1711.03705, 2017.
  * [15] R. Shafik, A. Wheeldon, and A. Yakovlev.  Explainability and dependability analysis of learning automata based AI hardware.  In 2020 IEEE 26th Int. Symp. On-Line Test. Robust Syst. Des., pages 1–4. IEEE, July 2020.
  * [16] E. Wang, J. J. Davis, D. Moro, P. Zielinski, C. Coelho, S. Chatterjee, P. Y. K. Cheung, and G. A. Constantinides.  Enabling binary neural network training on the edge, 2021.
  * [17] A. Wheeldon, R. Shafik, T. Rahman, J. Lei, A. Yakovlev, and O. C. Granmo.  Learning automata based energy-efficient AI hardware design for IoT applications.  Philos Trans R Soc Math Phys Eng Sci, 378(2182), Oct. 2020.
  * [18] A. Wheeldon, A. Yakovlev, R. Shafik, and J. Morris.  Low-Latency Asynchronous Logic Design for Inference at the Edge.  In To Appear in Proc DATE’21, Dec. 2020.
  * [19] H. Yu, H. Xie, X. Yang, H. Zou, and S. Gao.  Online sequential extreme learning machine with the increased classes.  Computers & Electrical Engineering, 90:107008, 2021.

AI

    artificial intelligence
ASIC

    application-specific integrated circuit
BD

    bounded delay
BNN

    binarized neural network
CAD

    computer-aided design
CD

    completion detection
CMOS

    complementary metal-oxide-semiconductor
CNN

    convolutional neural network
CSC

    complete state coding
CTM

    convolutional Tsetlin machine
CPOG

    conditional partial order graph
DFT

    design for test
DI

    delay insensitive
DR

    dual-rail
DRAM

    dynamic RAM
DSP

    digital signal processing
DVFS

    dynamic voltage and frequency scaling
EDA

    electronic design automation
FPGA

    field-programmable gate array
FSM

    finite state machine
HDC

    hyperdimensional computing
HDL

    hardware description language
INWE

    inverse-narrow-width effect
ISA

    instruction set architecture
I/O

    input/ouput
IoT

    internet of things
LA

    learning automaton
LEC

    logical equivalence checking
LFSR

    linear feedback shift register
LCG

    linear congruential generator
LSB

    least significant bit
LU

    learning unit
MAC

    multiply-accumulate
MEP

    minimum energy point
ML

    machine learning
MLP

    multi-layer perceptron
MPP

    maximum power point
MPPT

    maximum power point tracking
MSB

    most significant bit
NCL

    null convention logic
NN

    neural network
OCV

    on-chip variation
PC

    personal computer
PCA

    principal component analysis
PCG

    permuted congruential generator
PDF

    probability density function
PI

    primary input
PO

    primary output
PRBG

    pseudorandom bit generator
PRNG

    pseudorandom number generator
PVT

    process, variation and temperature
QDI

    quasi delay insensitive
RAM

    random-access memory
RBG

    random bit generator
RCA

    ripple-carry adder
RCD

    reduced CD
RCDR

    reduced CD dual-rail
RDF

    random dopant fluctuation
RNG

    random number generator
RO

    ring oscillator
RTL

    register transfer level
RTM

    recurrent Tsetlin machine
SCM

    standard cell memory
SDF

    standard delay format
SI

    speed independent
SoP

    sum-of-products
SPICE

    simulation program with integrated circuit emphasis
SR

    single-rail
SRAM

    static RAM
STG

    signal transition graph
STA

    static timing analysis
SVM

    support vector machine
TA

    Tsetlin automaton
TAT

    Tsetlin automaton team
TM

    Tsetlin machine
TRNG

    true random number generator
ULV

    ultra-low voltage
USB

    universal serial bus
VLSI

    very-large-scale integration
WSN

    wide sensor network
  *[[]:
  *[TA]: Tsetlin automaton
  *[TM]: Tsetlin machine
  *[CD]: completion detection