#  Flexible Logic from Neuronal Dynamics

Abraham Miliotis<EMAIL_ADDRESS>Sachin Talathi
<EMAIL_ADDRESS>William Ditto<EMAIL_ADDRESS>J Crayton
Pruitt Department of Biomedical Engineering, University of Florida,
Gainesville, FL 32611

(August 27, 2024)

###### Abstract

We present two novel methods for performing logic operations. Our methods are
based on using the time dimension for programming and data representation. The
first method is based on varying the sampling moment in time of a neuronal
action potential, and the second method is based on a neural delay system,
where the generation of the action potential is delayed by specific time
lengths, to be sampled at a fixed moment in time. Both methods are supported
by explicit examples.

###### pacs:

Valid PACS appear here

††preprint: APS/123-QED

The computational capabilities of chaotic and non-linear systems have been
widely reported sinha:2156 ; sinha:363 ; sinha:036216 ; sinha:036214 ;
murali:025201 ; murali:2005 ; murali:2669 ; murali:016205 ; munakata:1629 .
Most of these computational methods involve the threshold control of a chaotic
system murali:016210 ; ding:644  to perform computations, whether its simple
arithmetic calculations sinha:363 ; sinha:2156 , emulation of logic gates
sinha:036216  or solving more complex computational problems like the Deutsch-
Jozsa problem sinha:036214 . These nonlinear systems, with variable
thresholding schemes, provide an unique approach to emulate all logic gates
and have the flexibility of switching between different operational roles,
thus allowing for the design of a dynamic computer architecture. More recently
a different method for logic gate emulation based on the synchronization of a
driver and response nonlinear systems has been reported murali:025201 . In
this method though, the programming instruction and input data are separated
in different parts of the system. In this paper we present two novel methods
to perform computation using nonlinear systems which utilize time as
computational commands to represent both the programming instruction and the
input data stream into the logic gate, i.e. computation is performed by
varying a single parameter. The first method is based on variation of the
observation time (sampling instance) of a non-linear signal to obtain logic
gate emulation, while the second method for logic gate emulation is based on
time delays in the generation of a non-linear signal.

We will demonstrate these two general methods for logic gate emulation by
using the nonlinear properties of action potentials generated by neurons. We
model neuronal dynamics in the framework of conductance based Hodgkin-Huxley
(HH) neurons Talathi ; Talathi2 . The first method for logic emulation is
based on the idea of sampling the membrane voltage signal of a single neuron
at different moments in time. The second method utilizes two bi-directionally
coupled HH neurons, such that the two neuron system creates a time delay
circuit. This two neuron time delay circuit operates by generating an output
spike at time $t_{0}+\tau(R)$ in response to an input spike arriving into the
circuit at time $t_{0}$. The logic gates are emulated by varying the synaptic
strength $R$ that determines the time delay $\tau(R)$ and then observing the
output at a predetermined fixed time instant.

A system (a flexible logic gate) to be able to switch between the five
fundamental logic gates (AND, NAND, OR, NOR, XOR), needs to be able to
reproduce the truth table of each and every one of these gates murali:025201 ;
sinha:036216 . We can combine the truth tables into a single non-linear
function of the form: $F(u,t)>0,\text{for }t-\Delta t>t>t+\Delta\ t,\text{
else }F(u,t)=0$; which provides the required behavior for a system to be
utilized as a flexible logic gate. This function is very similar to an action
potential generated by a neuron; resting at a low voltage ($F(u,t)=0$), and
for a brief length of time rising very rapidly to a higher voltage
($F(u,t)>0$), and then dropping very rapidly back to its original level. It is
known that neurons have a method for performing computational operations Zhang
; we do not propose that the methods we present here are the method neurons
use, but it may well be a way by which neuronal networks in the brain
communicate information.

For any computational system to be able to perform flexible logic there are
three parameters that need to be given to the system. The first parameter that
needs to be introduced to the system is the programming instruction. This
programming instruction is the parameter of the system that defines which of
the five logic gates will be performed on a given set of inputs. The other two
parameters that need to be given to the system are the two logical inputs,
INPUT1 and INPUT2, see Figure 1.

Figure 1:  Required inputs and outputs of a flexible logic gate.

The first method of flexible logic implementation we will introduce is based
on utilizing fixed time intervals for representing the programming instruction
and the two inputs to the gate, as described above. These time intervals are
combined (as explained below) to determine the time at which the signal is to
be sampled to obtain an output from the gate. Consider a periodic nonlinear
signal of period T, which has a form close to that of a neuronal action
potential, see inset of Figure 2, i.e. for most of the time the signal is
“low” and for a brief length of time the signal is “high”. A programming
instruction is a time length, $t_{prog}<T$, at which the signal is sampled;
this time length is measured from a predetermined reference time point. Next,
the input data are also represented by a predetermined fixed time length.
Specifically a finite nonzero time length represents a logical 1,
$t_{input,i}$, where $i=\\{1,2\\}$, while zero time length representing a
logical 0. So we have:

$t_{input,i}=\\{\begin{array}[]{cc}t_{input,i}>0,&INPUTi=1\\\ \\\
t_{input,i}=0,&INPUTi=0\\\ \end{array}$

These three time intervals define the observation time at which the signal is
sampled for the output of the logic gate. This observation time is given by
$t_{prog}+t_{input,1}+t_{input,2}$.

It is important to note that the input data time length needs to be a constant
length irrespective of which of the two inputs, INPUT1 or INPUT2, is at
logical 1 and of double time length for the input (INPUT1, INPUT2) =(1,1).
This is a necessary condition so that the two input streams can be considered
degenerate, i.e. the cases (0,1) and (1,0) are represented by an equal time
length, while the case (1,1) corresponds to double this time length, which we
call as the input “unit” time. Careful choice of both the programming
instruction time and the input unit time can produce responses (threshold
crossing) at the sampled instance that are identical to the fundamental logic
gates. Note that since the time length representing a logical 0 is of zero
length, the programming instruction time is analogous to performing the
logical operation between two inputs of logical 0, i.e. (0,0).

As an example consider the action potential generated by a single neuron,
modeled as a type I HH neuron Talathi , see inset of Figure 2. For most of its
period the signal rests at -60mV, the resting membrane potential of the
neuron, but for a brief period of time the membrane voltage rises above the
resting potential when the neuron generates an action potential. If we
interpret a membrane voltage over -45mV as a logical 1 and below as logical 0,
then it is only a matter of $when$ we observe the signal to obtain a logical 0
or a logical 1 at the output, which represents a flexible logic opearation.
Take for example the case of the logical gate NOR, see Table 1, the truth
table of the NOR gate is: OUTPUT=1 for INPUTS=(0,0), OUTPUT=0 for INPUTS=(0,1)
/ (1,0) and OUTPUT=0 for INPUTS=(1,1). So we need 3 distinct times at which to
observe(sample) our signal that correspond to the OUTPUT values given by the
truth table. At the same time, the time difference between the 3 observation
times should be constant for the logical input of 1 to have a constant
representation, irrespective if it is INPUT1 or INPUT2. See Table 1.

Table 1:  NOR gate truth table, sampling time representation of programming and inputs, necessary conditions for representation of the NOR gate. INPUTS | NOR | Sampling time | Condition
---|---|---|---
(0,0) | 1 | $t_{prog}+0+0$ | $V_{sampled}>-45mV$
(0,1)/(1,0) | 0 | $t_{prog}+t_{input,1/2}+0$ | $V_{sampled}<-45mV$
(1,1) | 0 | $t_{prog}+t_{input,1}+t_{input,2}$ | $V_{sampled}<-45mV$
Figure 2:  Demonstration of operating a NOR gate using different sampling
times. Green dot represents a logical 1 at the OUTPUT, blue dot represents
logical 0 at the OUTPUT. The three dots indicate the distinct moments in time
that the signal would be sampled to generate the truth table of a NOR gate.
Inset: A typical action potential.

In Figure 2 we show the results of sampling our signal at the time instances
of 2555 for inputs (0,0), 2605 for inputs (0,1)/(1,0) and at 2655 for inputs
(1,1). Therefore in terms of programming and input time lengths, for the NOR
gate, $t_{prog}=2555$ time steps and $t_{input,i}=50,i=\\{1,2\\}$ time steps.
As is clear from the figure the appropriate OUTPUT values are obtained, i.e.
the voltage is over -45mV for the (0,0) case and below for the other two
cases. This observation can be interpreted as follows: to perform the logic
gate NOR we require to wait 2555 time steps as a programming time length and
then another 50 time steps for each occurrence of a single logical input of 1.
Using the same system, that is the HH neuron described above with the action
potential generated at the same rate, time instances for accomplishing the all
fundamental gates are given in Table 2. So in essence we have two time delays
on the observation instance, one for programming instruction, i.e. which gate
will be performed, and it is analogous to performing an operation on inputs
(0,0), and second time delay representing an input of logical 1, in this case
it is equal to 50 time steps.

Table 2:  Appropriate time sample instances to perform each fundamental logic gate, for each case of different inputs. In brackets the output of each gate is given. | NOR | NAND | AND | OR | XOR
---|---|---|---|---|---
(0,0) | 2555 (1) | 2505 (1) | 2405 (0) | 2455 (0) | 2485 (0)
(0,1)/(1,0) | 2605 (0) | 2555 (1) | 2455 (0) | 2505 (1) | 2535 (1)
(1,1) | 2655 (0) | 2605 (0) | 2505 (1) | 2555 (1) | 2585 (0)

The second method for flexible logic implementation is based on the idea that
one fixes the time instance of observation and varies the time of generation
of the action potential to perform the logic operations. This form of variable
delays can be implemented, in a neuronal system, by using a simple network of
two mutually coupled neurons as explained below.

In Talathi  the authors present a neuronal circuit that has the ability to
generate an action potential at a delayed time interval controlled by synaptic
coupling strength. In brief, the circuit is composed of two HH neurons
arranged as shown in Figure 3 inset; with neuron ($\alpha$), set at resting
state and the bistable neuron $\beta$ also set at resting fixed point state.
When an action potential arrives at time $t_{0}$, the neuron $\beta$ is pushed
into its bistable oscillating state. This neuron then sends an excitatory
input drive to neuron $\alpha$, which eventually triggers an action potential,
at a delayed time interval $t_{0}+\tau(R)$, that depends on the strength of
excitatory synaptic input the neuron receives at time $t_{0}$ through the
synapse $g_{S}=Rg_{S0}$, with $g_{S0}=1$. At that stage the action potential
generated by the neuron $\alpha$ will inhibit the bistable neuron sending it
back to its resting state. Thus both neurons will return to their resting
states, making the system receptive to a new operation. The time delay for the
generation of the action potential is governed by the parameter $R$, as can be
seen from Figure 3. By varying $R$ we can have the generated action potential
be produced at different times with respect to an initiating spike.

Figure 3:  Two neuron time delay circuitry. (Adapted from Talathi .)

Now in order to implement flexible logic gates with this two neuron time delay
circuitry, we set a specific observation time to observe the output of this
circuitry in response to an initiating spike; i.e. in the example below this
time is at 425msec after the initiating spike. Next we set a confirmation
voltage at -45mV; which we interpret as: logical 1 output if voltage at
observation time exceeds -45mV, else logical output 0. We also use the range
of $R$, $1.68<R<1.72$ where the curve of Figure 3 is linear, so that the
changes in $R$ are linearly proportional to the changes in $\tau(R)$ and so
changes for a logical 1 at the input are independent of whether it is at
INPUT1 or INPUT2.

Using this method of time delays, flexible logic can be implemented as
follows: the time delay circuitry is setup with a specific $R_{prog}$
representing which logical operation will be performed. Further, we shift the
total $R$ value of the system an extra amount depending on the inputs to the
system. In analogy to the previous method we have the total value of $R$
defined as: $R=R_{prog}+R_{input,1}+R_{input,2}$; representing the combination
of programming instruction, which decides the logic operation to be performed,
and the two input data streams, each represented by a shift in total $R$. In
our specific example a shift of $R_{input,i}=0.005,i=\\{1,2\\}$ represents a
single logical 1 at the inputs, for cases (0,1) and (1,0); and naturally for
inputs (1,1) $R_{input,1}+R_{input,2}=0.01$ and for (0,0)
$R_{input,i}=0,i=\\{1,2\\}$.

An initiating spike is given to the system every second, like a universal
clock. At 425msec after the initiating spike we observe the system, if there
is an action potential and the voltage is higher than -45mV we interpret a
logical 1 at the output otherwise a logical 0, see Figure 4 for an
illustrative example of a NOR gate implementation. In Figure 4 we see the
three distinct cases of the truth table of a NOR gate superimposed. Each case
is generated with a different $R$ value, representing the programming and the
inputs to the gate. As is expected for the NOR gate, only in the case of
INPUTS=(0,0) we have an action potential, at the observation time, over -45mV,
signified by the green dot. In the other two cases of the truth table the
action potentials generated at those $R$ values are lower than -45mV at the
observation time, signified by blue dots. Just like in the previous method, of
varying sampling time, we can with this method reproduce the five fundamental
logic gates with different delay parameter values, $R$, see Table 3.

Figure 4:  Demonstration of operating a NOR gate using different delay times. Green dot represents a logical 1 at the OUTPUT, blue dot represents logical 0 at the OUTPUT. The three action potentials each represents a distinct case of the truth table of NOR gate, in reality only one action potential will be generated for the specific case of inputs. Table 3:  R values for all gates. INPUTS | NOR | NAND | AND | OR | XOR
---|---|---|---|---|---
(0,0) | 1.705 | 1.700 | 1.690 | 1.695 | 1.697
(0,1)/(1,0) | 1.710 | 1.705 | 1.695 | 1.700 | 1.702
(1,1) | 1.715 | 1.710 | 1.700 | 1.705 | 1.707

We are using neuronal systems for our demonstrations as they are one of the
most natural generators for the function that covers all fundamental logic
gates. The neuronal action potential structure is exactly what is needed for
our methods to work. The novelty of the methods introduced is that we use time
for both the computational programming and the data representation. Based on
these methods our computational efficiency and capabilities are limited by how
finely time can be sliced, the sampling rate. The finer definition we have on
the slicing of time, higher sampling rate, the more distinct the different
cases can be and more robust to noise. In the implementation of our ideas
using neuronal models, the key parameter that defines the precision of each
operation is the width of the action potential in relation to the period of
the signal, the wider the action potential is the further apart in time each
case will be providing more resolution between the different logic cases and
more robustness to noise.

To concatenate such systems into more complex logic circuits, of two logic
gates and more, the output from one such system needs to be given as an input
to the next gate (system). This can be accomplished with the use of a lookup
table that relates the event of crossing the threshold, or not, with a time
length (for the first method) or with a shift in $R$ (for the second method),
see Figure 5 for a demonstration. A look up table is used because the nature
of the inputs to the system is different to that of the output, inputs are
time lengths (or changes in synaptic strength, $R$) whereas outputs are
events.

Figure 5:  Each flexible logic gate passes its output to a look up table that
translates the event of crossing the -45mV threshold to a change in the R
parameter of the next flexible logic gate.

Further research will focus to bring the inputs and outputs to the same units
so that concatenation can be performed without the use of a lookup table,
which adds computational overhead. In addition a method using time as
computational commands, to store and process (specifically: searching)
information will be reported in a future paper.

## References

  * [1] H.D.I. Abarbanel and S.S. Talathi.  Neural circuitry for recognizing interspike interval sequences.  Physics Review Letters, 96, 2006.
  * [2] Mingzhou Ding, E-Jiang Ding, William L. Ditto, Bruce Gluckman, Visarath In, Jian-Hua Peng, Mark L. Spano, and Weiming Yang.  Control and synchronization of chaos in high dimensional systems: Review of some recent results.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 7(4):644–652, 1997.
  * [3] Toshinori Munakata, Sudeshna Sinha, and William L. Ditto.  Chaos computing: Implementation of fundamental logical gates by chaotic elements.  IEEE Transactions in Circuits and Systems, 49(11):1629, 2002.
  * [4] K. Murali and Sudeshna Sinha.  Experimental realization of chaos control by thresholding.  Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 68(1):016210, 2003.
  * [5] K. Murali and Sudeshna Sinha.  Using synchronization to obtain dynamic logic gates.  Physical Review E (Rapid Communications), 75, 2007.
  * [6] K. Murali, Sudeshna Sinha, and William L. Ditto.  Implementation of nor gate by a chaotic chua’s circuit.  International Journal of Bifurcation and Chaos, 13(9):2669, 2002\.
  * [7] K. Murali, Sudeshna Sinha, and William L. Ditto.  Realization of the fundamental nor gate using a chaotic circuit.  Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 68(1):016205, 2003.
  * [8] K. Murali, Sudeshna Sinha, and I. Raja Mohamed.  Chaos computing: experimental realization of nor gate using a simple chaotic circuit.  Physics Letters A, 339:39–44, 2005.
  * [9] Sudeshna Sinha and William L. Ditto.  Dynamics based computation.  Physical Review Letters, 81(10):2156–2159, 1998.
  * [10] Sudeshna Sinha and William L. Ditto.  Computing with distributed chaos.  Physical Review E (Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics), 60(1):363–377, 1999.
  * [11] Sudeshna Sinha, Toshinori Munakata, and William L. Ditto.  Flexible parallel implementation of logic gates using chaotic elements.  Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 65(3):036216, 2002.
  * [12] Sudeshna Sinha, Toshinori Munakata, and William L. Ditto.  Parallel computing with extended dynamical systems.  Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 65(3):036214, 2002.
  * [13] SS Talathi, HDI Abarbanel, and WL Ditto.  Temporal spike pattern learning.  Physical Review E (Submitted), 2008.
  * [14] Chang Nian Zhang, Ming Zhao, and Meng Wang.  Logic operations based on single neuron rational model.  IEEE Transactions on neural networks, 11(3), 2000.


# Efficient Dialogue State Tracking by Masked Hierarchical Transformer

Min Mao, Jiasheng Liu, Jingyao Zhou, Haipang Wu

###### Abstract

This paper describes our approach to DSTC 9 Track 2: Cross-lingual Multi-
domain Dialog State Tracking, the task goal is to build a cross-lingual dialog
state tracker with a training set in rich resource language and a testing set
in low resource language. We formulate a method for joint learning of slot
operation classification task and state tracking task respectively.
Furthermore, we design a novel mask mechanism for fusing contextual
information about dialogue, the results show the proposed model achieves
excellent performance on DSTC Challenge II with a joint accuracy of 62.37% and
23.96% in MultiWOZ(en $\rightarrow$ zh) dataset and CrossWOZ(zh $\rightarrow$
en) dataset, respectively.

## Introduction

Task-oriented dialogue has a wide range of applications to handle everyday
tasks such as booking hotels, movie tickets and restaurants, etc. The system
for supporting these tasks mostly adopts a pipelined modular architecture,
which usually contains a natural language understanding (NLU) module for
recognizing users’ intent, a dialogue state tracking (DST) module for
extracting and tracking the dialogue states, a policy (POL) module for
deciding the system action and a natural language generation (NLG) module for
generating the response according to the system action. DST module is the core
component of a task-oriented dialogue system since the system response is
dependent on its result. An excellent DST can improve the user experience by
reducing the number of interactions. The challenge in DSTC 9 Track
2(Gunasekara et al. 2020) is to build a cross-lingual Multi-domain DST which
can track the dialogue state with resource-poor language whose original
dataset is resource-rich language. The dataset of this challenge is based on
MultiWOZ 2.1 (Eric et al. 2019) and CrossWOZ (Zhu et al. 2020). Competitors
should track the dialogue state in Chinese with MultiWOZ 2.1 dataset and in
English with CrossWOZ dataset, respectively.

To solve the above tasks, we propose a multi-task model to predict the
dialogue state and the state operation at each turn. The main contributions
are as follows:

>   * •
>
> To simplify the problem we use machine translation systems such as Google
> Translate, Baidu Translate to translate the training dataset from resource-
> rich language to resource-poor language, thereby the task can be considered
> as a traditional DST problem whose train and test dataset in the same
> language.
>
>   * •
>
> The dialogue state extracts from the dialogue history whose text usually has
> more than 512 tokens, but the encoder stack of Transformer usually has the
> length limit(512 tokens). We propose a general method to fusion the features
> from any length of historical turns by defining different masked self-
> attention structures in the transformer network. Furthermore, we use this
> feature fusion method to extract the global context information and local
> context information, respectively, merge those two representations to
> predict the dialogue state.
>
>   * •
>
> We adjust the model construction which is proposed in Shan et al. (2020) by
> adding a masked hierarchical transformer module, due to its local
> information module only contains the feature from a single turn. The added
> module can merge multi-turn features as the local representations so that
> the local representations can be used to predict multi-class classification
> such as state operation prediction. We use a three-class state operation
> prediction as to the auxiliary task. However, that is a bi-class
> classification task in Shan et al. (2020) due to the local representation
> module in their method only contain the information from the current turn.
>
>   * •
>
> Exploring data augmentation to improve the model performance.
>
>

|  User: I want to find a cheap restaurant in the north part of town. What is
the address and food ?
---
State: price range=cheap
|  Sys: There is Royal Spice which serves Indian food and Da Vinci Pizzeria
which serves Italian food. Would you like me to book you a table at either of
these restaurants ?
---
User: Royal Spice sounds good. Can you reserve a table for 8 at 15:45 on
Saturday ?
State: price range=cheap; restaurant-name=Royal Spice; food=Indian
|  Sys: Unfortunately , i was not able to book for that specific time and day
. Can i try a different day or time for you ?
---
User: How about at 14:45 ?
State: price range=cheap; restaurant-name=Royal Spice; food=Indian
|  Sys: Sorry, the booking was unsuccessful. would you like for me to find
another restaurant ?
---
User: Please tell me the address of Da Vinci Pizzeria.
State: price range=cheap; restaurant-name=Da Vinci Pizzeria; food=Italian

Table 1: An example dialogue. At the last turn(the $4$-th turn), the
underlined value of slot “food” is corrected by the information at the $2$-nd
turn.

## Related Work

Traditional DST methods can be divided into two major types: open-
vocabulary(Le, Socher, and Hoi 2020; Goel, Paul, and Hakkani-Tür 2019; Wu et
al. 2019) and predefined-ontology(Lee, Lee, and Kim 2019; Shan et al. 2020).
The former one generates slot value at each turn by a generative model such as
the decoder stack in RNN and Transformer, and the latter predefines the
dialogue ontology and simplifies the DST models into a classification problem.
The open-vocabulary methods can partly track unseen slot values but usually
has a lower performance than the predefined-ontology methods. Since the
ontology in the ninth DSTC Track 2 Cross-lingual Dialog State Tracking Task is
predefined, we here use the Predefined-ontology methods aims to achieve better
performance.

On the other hand, traditional DST models (Henderson, Thomson, and Young 2014;
Chao and Lane 2019) usually neglect the dialogue history and consider only
utterances at current turn. To avoid the problem of lacking historical
context, recent researchers employ autoregressive models to extract historical
information. Some of them use a low-level network such as RNN, GRU to
interactions between context and slots(Lee, Lee, and Kim 2019; Goel, Paul, and
Hakkani-Tür 2019), others use partial context only(Kim et al. 2019; Sharma,
Choubey, and Huang 2019). These methods cannot extract the relevant context in
an effective way.

Since the transformer network has been proposed in 2017(Vaswani et al. 2017),
the large-scale pre-trained model such as BERT(Devlin et al. 2018),
RoBERTa(Liu et al. 2019) demonstrate a strong effect on NLP tasks. However,
due to the maximum sequence length limit(eg, 512 for BERT-Base), these models
unable to tackle sequences that are composed of thousands of tokens. We here
use the feature fusion method on dialogue history, the method can fuse any
partial history information through a predefined mask in the transformer
network. Furthermore, we consider the historical dialogue information as
global information and utterance at the current turn and its adjacency
dialogue history as the local information which is in contrast to most
existing DST methods depending on either local or global information only.
Whilst the local feature aims to predict state operations (UPDATE, CARRYOVER,
DONTCARE ) and the global feature exploits relevant context from dialogue
history. To the end, we formulate a two-branch architecture, with one branch
for learning localized state operation and the other for learning slot value
extraction. The two branches are not independent but synergistically jointly
learned concurrently. We wish to discover and optimize jointly correlated
complementary feature selections in the local and global representations.

## Approach

### Problem definition

We assume a dialogue with $T$ turns
$D=\left\\{\left(A_{1},U_{1}\right),...,\left(A_{T},U_{T}\right)\right\\}$
where $A_{t}$ denotes Agent response, $U_{t}$ denotes user utterance at turn
$t$, the predefine ontology as $O=\left\\{\left(s,v_{s}\right),s\in
S,v_{s}\subset V\right\\}$ where $S$ is the set of slot names, here the slot
name is denoted as domain-slot, for example, “restaurant-name”. $V$ is the
total set of slot values and $v_{s}$ is the set of slot values belong to slot
$s$, i.e. $v_{s}\subseteq V$, we define
$B_{t}=\left\\{\left(s^{j}_{t},v^{j}_{s,t}\right),1\leqslant j\leqslant
J\right\\}$ as the belief state at each turn $t$, where $J$ is the total
number of slots. We add “none” to the no value slot at current turn.

Figure 1: The architecture of our model. We utilize the Masked Hierarchical
Transformer to encode the global and local information, respectively. We
combine the global and local information to predict slot values and use the
local information to predict state transition at turn $t$. Finally, we train
both tasks jointly.

### Joint Learning Multi Loss

Figure 1 shows the design of the proposed model architecture. The joint
learning model consists of two branches Transformer network: (1) The local
branch learning the state transition of each slot; (2) Another global branch
responsible for learning the slot value label of each slot at each turn. For
discovering correlated complementary information between local and global
feature selections, the joint learning scheme is considered with two
principles as follows:

>   * •
>
> Shared low-level features. We construct the two types of branches on a
> shared lower BERT model. The intuition is that, the low-level features such
> as word and phrase representations which are common to all patterns in the
> same sentences. The local and global feature learning branches are two
> related learning tasks, sharing the low-level BERT model reduces the model
> overfitting risks.
>
>   * •
>
> Multi-task independent learning. For learning the maximizing of
> complementary discriminative features from local and global representations,
> the remaining layers of two branches are learned independently which aims to
> preserve both local saliencies in state operation prediction and global
> robustness in dialogue history representation.
>
>

### Feature Fusion

We encoded the turn-level sentence by the BERT-base model due to its length is
usually less than 128. On the other hand, since the sentence length in
context-level is usually more than 512, we use the masked hierarchical
transformer to fuse the feature from each turn. In addition, we fuse total
historical context as a global representation that contains all dialogue
information up to now and $n$-history context as a local representation at the
current turn. The local representation is also used to predict state operation
at the current turn (eg. carryover, update, dontcare). Due to the state
operation cannot be decided by a single turn, we here use $n$-history context
as the local representation ($n\geq 1$). We also adjust the model construction
in Shan et al. (2020) by adding a masked hierarchical transformer module after
the BERT encoder.

### Network Construction

As shown in Figure 1, the slot names and slot values are encoded by the same
BERT with fixed weights. The dialogue is first encoded by a trainable BERT in
turn-level and then fuse the turn-level features for global and local
representations, respectively. Moreover, the global and the local
representations are merged by a gate mechanism. The vectors from this gate
mechanism are then used to compute the distance with slot value labels
(similar to Shan et al. (2020)). Furthermore, the local representations are
used for predicting state operations as an auxiliary task. To make the text
more aligned with Figure 1, we will describe each module in more detail.

#### Dialogue History Encode

As the belief state is dependent on the historical dialogue, Shan et al.
(2020) use a masked hierarchical transformer to encode the dialogue context.
We extend this method to encode the context as global and local
representations with two different mask metrics. An example of Masked Self-
Attention is shown in Figure 2.

The information of utterance at each turn is aggregated by a trainable BERT
and the utterance at turn $t$ is consisted of user utterance $U_{t}$ and agent
response $A_{t}$ (Lee, Lee, and Kim 2019). We denote the turn input as
$D_{t}=\left[CLS\right]\oplus A_{t}\oplus\left[SEP\right]\oplus
U_{t}\oplus\left[SEP\right]$ and the turn-level informations $h_{t}$ is
encoded by BERT as follows:

$h_{t}=\text{BERT}_{\text{uttr}}\left(D_{t}\right)$ (1)

The slot name $s$ and the slot value $v$ in Lee, Lee, and Kim (2019) are
encoded by a fixed weights BERT. The sequence of slot name and slot value are
denote as $q_{s}=\left[CLS\right]\oplus s\oplus\left[SEP\right]$ and
$q_{v}=\left[CLS\right]\oplus v\oplus\left[SEP\right]$ , the outputs of token
$\left[CLS\right]$ in both $q_{s}$ and $q_{v}$ are used to represent the
information of slot name and slot value, respectively.

$h_{s}=\text{BERT}_{\text{slot}}\left(q_{s}\right)$ (2)
$h_{v}=\text{BERT}_{\text{slot}}\left(q_{v}\right)$ (3)

For more general situations, the slot value at a single turn cannot be
discriminate only by current utterance, but is dependent on previous turns, as
shown in Table 1. Furthermore, the local feature with $n$-historical context
$c^{loc}_{s,t}$ at turn $t$ can be defined as a multi-head attention between
slot name and context of $n$-history, where $n$-history denotes $n$ turns of
dialogue history before current turn $t$, i.e.
$\left\\{uttr_{t-n},uttr_{t-n+1},...,uttr_{t}\right\\}$. Formally,
$c^{loc}_{s,t}$ can be denoted as follows:

$c^{loc}_{s,t}=\text{MultiHead}\left(h_{s},c_{s,t-n\leqslant i\leqslant
t},c_{s,t-n\leqslant i\leqslant t}\right)$ (4)

Where $c_{s,t-n\leqslant i\leqslant t}$ is the masked hierarcharical encoder
result. Figure 3 shows what $n$-history mask matrix looks like and
$c_{s,t-n\leqslant i\leqslant t}$ is denoted as follows:

$\displaystyle
m^{0}=\left[c^{word}_{s,1},c^{word}_{s,2},...,c^{word}_{s,t}\right]\ +\
\left[PE\left(1\right),PE\left(2\right),...,PE\left(t\right)\right],$
$\displaystyle m^{N}=\
\text{MaskedTransformer}\left(m^{N-1},m^{N-1},m^{N-1}\right),$ $\displaystyle
c_{s,t-n\leqslant i\leqslant t}=m^{N}$ (5)

Where $m^{N}$ is the output of $N$-layers MaskedTransformer.
$PE\left(\cdot\right)$ denotes positional encoding define in Devlin et al.
(2018), $c_{s,t}^{word}$ is the MultiHead Attention between slot name and
utterance tokens at turn $t$, which can be defined as follows:

$c_{s,t}^{word}=\text{MultiHead}(h_{s},h_{t},h_{t})$ (6)

We use $c_{s,0\leqslant i\leqslant t}$ and $c_{s,t-n\leqslant i\leqslant t}$
are the global and local contextual information, respectively. The feature
fusion method is shown in Figure 1, we expect this feature can better
represent the dialogue information through balancing the information from
global and local context.

Finally, we take the method of Shan et al. (2020) to compute the loss for
slot-value prediction, the probability distribution of slot value
$p\left(v_{t}\mid U_{t},A_{t},s\right)$ at turn $t$ and its loss are defined
as follows:

$\displaystyle p\left(v_{t}\mid U_{\leq t},A_{\leq t},s\right)\ =\
\frac{exp\left(-\|d_{s,t}-h_{v}\|\right)}{\sum_{{v^{\prime}}\in
V_{s}}exp\left(\|d_{s,t}-h_{v^{\prime}}\|\right)}$ $\displaystyle
L_{sv}=\sum_{s\in S}\sum^{T}_{t=1}-\text{log}\left(p\left(v_{t}\mid U_{\leq
t},A_{\leq t},s\right)\right)$ (7)

Where $d_{s,t}$ denotes the encoder result with slot name $s$, it will be used
to match each slot value representation $h_{v}$ belongs to $s$.

#### State Operation Decoder

We define O={CARRYOVER, DONTCARE, UPDATE} as the state operation category set.
An operation $r_{t}^{j}$ of slot $j$ is classified by state operation
predictor, the mean of each category as follows:

>   * CARRYOVER: slot value is unchanged.
>
>   * UPDATE: slot value is changed to a new value from previous one.
>
>   * DONTCARE: slot neither needs to be considered important nor be tracked
> in the dialogue.
>
>

#### Input Representation for State Operation

Figure 2: Masked Transformer. The position with -inf value in mask matrix will
be masked, since the softmax of -inf is zero.

As the conversation progresses, the state operation at each turn is determined
by the previous dialogue state and the current dialogue turn. The flow of
state can be modeled by autoregressive decoders. Therefore, we use RNN as our
decoder model, $c_{s,t}^{loc}$ and $h_{s,t-1}^{loc}$ as the model inputs:

$h^{loc}_{s,t}=\text{RNN}(c_{s,t}^{loc},h_{s,t-1}^{loc})$ (8)

Where $h_{s,t}^{loc}$ is the representation of state operation at turn $t$.

The probability distribution over state operations $p_{s,t}^{sop}$ and its
loss are defined as follows:

$\displaystyle p^{sop}_{s,t}=\text{softmax}\left(W_{sop}h^{loc}_{s,t}\right),$
$\displaystyle L_{sop}\ =\ \sum_{s\in
S}\sum^{T}_{t=1}-\left(Y_{s,t}^{sop}\right)^{T}\text{log}\left(p^{sop}_{s,t}\right)$
(9)

Where $W_{sop}$ is a linear project to obtain operation probability
distribution $p^{sop}_{s,t}$ and $Y^{sop}_{s,t}$ is the operation label of
slot $s$ at turn $t$ .

Therefore, we take the sum of losses metioned above as the final joint loss
$L_{joint}$ as following:

$L_{joint}=\ L_{sv}+L_{sop}$ (10)

Figure 3: $n$-history mask. The blocks with 0 score in the mask matrix means
the corresponding utterance is attendable.

## Experiment

### Baseline Models

We compare the performance of the proposed method with the following models:

>   * SUMBT: Using a trainable BERT to encode system and user utterances and a
> fixed weighted BERT to encode slot-type and slot-value information and
> predict the slot-value label based on a certain metric(Lee, Lee, and Kim
> 2019).
>
>   * CHAN: Employing a contextual hierarchical network to fusion contextual
> information and exploiting the same method in SUMBT to predict the slot-
> value label(Shan et al. 2020).
>
>   * NADST: Generate dialogue state at each turn by a non-autoregressive
> decoder model(Le, Socher, and Hoi 2020).
>
>   * TRADE: Using an Encoding Decoding model to generate slot-value label(Wu
> et al. 2019).
>
>

Model | Ontology | MultiWOZ(en $\rightarrow$ zh) | CrossWOZ(zh $\rightarrow$ en)
---|---|---|---
Joint(%) | Joint(%)
TRADE | $\times$ | 29.63 | 7.9
NADST | $\times$ | 31.21 | 8.3
SUMBT | $\checkmark$ | 49.4 | 10.6
CHAN | $\checkmark$ | 49.19 | 11.3
CHAN + 4-class STP(Ours) | $\checkmark$ | 50.16 | 11.87

Table 2:  Joint accuracy on human val sets of MultiWOZ(en $\rightarrow$ zh)
and CrossWOZ(zh $\rightarrow$ en), respectively. The ontology column indicates
if the model is based on predefined ontology or not.

Table 2 shows the joint accuracy of baseline models and our model on MultiWOZ
(en $\rightarrow$ zh) and CrossWOZ (zh $\rightarrow$ en) human val datasets.
Our model achieves 50.16% and 11.87% with 0.96% and 0.57% improvement
respectively.

### Data Augmentation

We found that the human evaluation dataset is generated through real-life
conversations, while the training data is generated by Google translator, so
it is not as natural as human language. In this work, we consider data
augmentation to improve model performance. We use translation services
provided by Tencent, Baidu, and our translation model to translate the source
language to the target language. We also found that MultiWOZ(en $\rightarrow$
zh) and CrossWOZ(zh $\rightarrow$ en) are provided by different organizers,
both of them have some annotation errors, so we here use different methods to
correct slot value labels.

For the MultiWOZ(en $\rightarrow$ zh) dataset we using the label in
MultiWOZ_2.2 as right labels to correct the older ones, and the changes of
each slot on MultiWOZ(en $\rightarrow$ zh) are shown in Table 3

Slot name | # of total slot values | # modified slot values | % of slot values modified
---|---|---|---
attraction-type | 10525 | 845 | 8
restaurant-food | 16095 | 502 | 3.1
attraction-name | 5843 | 465 | 7.9
restaurant-name | 7293 | 336 | 4.6
train-leave at | 7563 | 331 | 4.38
hotel-name | 8621 | 296 | 3.43
taxi-departure | 4037 | 254 | 6.29
taxi-destination | 4108 | 204 | 4.97
train-arrive by | 7488 | 167 | 2.23
restaurant-book-time | 8958 | 156 | 1.74

Table 3: The Top-10 number of slot values modified

For the CrossWOZ(zh $\rightarrow$ en) dataset we found that the belief states
at some turns are not inherited its previous turns. We consider these as the
labeling errors that need to be corrected, so we here use the concept of state
transition (carryover, update, dontcare, delete) to correct the belief state
at each turn.

We estimate the effectiveness of the back-translation data augmentation and
state transition prediction task. The joint accuracy reduces by $0.58\%$ with
removing the state operation prediction task and reduces by $8.4\%$ with no
data augmentation. Moreover, the performance decreases by $9.4\%$ with
removing both of them. Table 4 demonstrates that the data augmentation and
state transition prediction task are crucial for DST.

| MultiWOZ(en $\rightarrow$ zh) | CrossWOZ(zh $\rightarrow$ en)
---|---|---
Final Model | 58.56 | 16.81
remove state transition prediction | 57.98(-0.58) | 16.29(-0.52)
remove data argumentation | 50.16(-8.4) | 11.87(-4.94)
remove above two(only CHAN) | 49.19(-9.37) | 11.3(-5.51)

Table 4: The ablation study of the state transition prediction and the data
Augmentation on MultiWOZ(en $\rightarrow$ zh) and CrossWOZ(zh $\rightarrow$
en), respectively.

Team | Joint(%) | Slot(%) | Slot P/R/F1 | Joint(pub/pri) | Rank
---|---|---|---|---|---
1(ours) | 62.37 | 98.09 | 92.15/94.02/93.07 | 62.70/62.03 | 1
2 | 62.08 | 98.10 | 90.61/96.20/93.32 | 63.25/60.91 | 2
3 | 30.13 | 94.40 | 87.07/74.67/80.40 | 30.53/29.72 | 3
Baseline | 55.56 | 97.68 | 92.02/91.10/91.56 | 55.81/55.31 | N/A

Table 5: MultiWOZ Leaderboard (Best Submissions).

Team | Joint(%) | Slot(%) | Slot P/R/F1 | Joint(pub/pri) | Rank
---|---|---|---|---|---
3 | 16.86 | 89.11 | 68.26/62.85/65.45 | 16.82/16.89 | 1
1(ours) | 15.28 | 90.37 | 65.94/78.87/71.82 | 15.19/15.37 | 2
2 | 13.99 | 91.92 | 72.63/78.90/75.64 | 14.41/13.58 | 3
Baseline | 7.21 | 85.13 | 55.27/46.15/50.30 | 7.41/7.00 | N/A

Table 6: CrossWOZ Leaderboard (Best Submissions).

Team | Joint(%) | Slot(%) | Slot P/R/F1 | Joint(pub/pri) | Rank
---|---|---|---|---|---
2 | 32.30 | 94.35 | 81.39/82.25/81.82 | 32.70/31.89 | 1
1(ours) | 23.96 | 92.94 | 74.96/83.41/78.96 | 23.45/24.47 | 2
3 | 15.31 | 89.70 | 74.78/64.06/69.01 | 14.25/16.37 | 3
Baseline | 13.02 | 87.97 | 67.18/52.18/58.74 | 13.30/12.74 | N/A

Table 7: CrossWOZ Leaderboard (Updated Evaluation, Best Submissions).

### Overall Results

We train the model with different $n$-history as the local information and we
finally choice $1$-history as the best length for the joint learning.

By using above improvements, we achieve the result with joint accuracy of
62.37% and 23.96% on MultiWOZ(en $\rightarrow$ zh) and CrossWOZ(zh
$\rightarrow$ en) datasets, respectively.

With this end-to-end model, we achieve Top 1 in MultiWOZ(en $\rightarrow$ zh)
dataset, and Top 2 in CrossWOZ(zh $\rightarrow$ en) dataset. The results of
MultiWOZ(en $\rightarrow$ zh) and CrossWOZ(zh $\rightarrow$ en) tasks are
shown in Table 5 and 6 respectively. The Organizers found that the CrossWOZ(zh
$\rightarrow$ en) test data miss “name” labels when the user accepts the
attraction/hotel/restaurant recommended by the system(Gunasekara et al. 2020).
Table 7 shows the updated leaderboard for CrossWOZ. Moreover, although the
evaluation was updated in CrossWOZ(zh $\rightarrow$ en), our algorithm is
still ranked second in the updated CrossWOZ Leaderboard, which shows that our
method has better generalization ability.

## Conclusion

In this paper, we introduce a general feature fusion method as the solution in
DSTC 9 Track 2 competition, which can merge any parts of context feature from
dialogue history. We also construct a multi-task network to improve the
feature representation ability. Our proposed model is ranked first in MultiWOZ
(en $\rightarrow$ zh) and second in CrossWOZ (zh $\rightarrow$ en)
respectively. The proposed model is based on predefined ontology, and we will
investigate an open-vocabulary model in the future.

## References

  * Aujogue and Aussem (2019) Aujogue, J.-B.; and Aussem, A. 2019.  Hierarchical Recurrent Attention Networks for Context-Aware Education Chatbots.  In _2019 International Joint Conference on Neural Networks (IJCNN)_ , 1–8. IEEE.
  * Budzianowski et al. (2018) Budzianowski, P.; Wen, T.-H.; Tseng, B.-H.; Casanueva, I.; Ultes, S.; Ramadan, O.; and Gašić, M. 2018.  Multiwoz-a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling.  _arXiv preprint arXiv:1810.00278_.
  * Chao and Lane (2019) Chao, G.-L.; and Lane, I. 2019.  Bert-dst: Scalable end-to-end dialogue state tracking with bidirectional encoder representations from transformer.  _arXiv preprint arXiv:1907.03040_ .
  * Devlin et al. (2018) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ .
  * Eric et al. (2019) Eric, M.; Goel, R.; Paul, S.; Sethi, A.; Agarwal, S.; Gao, S.; and Hakkani-Tür, D. 2019.  Multiwoz 2.1: Multi-domain dialogue state corrections and state tracking baselines .
  * Gao et al. (2019) Gao, S.; Sethi, A.; Agarwal, S.; Chung, T.; and Hakkani-Tur, D. 2019.  Dialog state tracking: A neural reading comprehension approach.  _arXiv preprint arXiv:1908.01946_ .
  * Goel, Paul, and Hakkani-Tür (2019) Goel, R.; Paul, S.; and Hakkani-Tür, D. 2019.  Hyst: A hybrid approach for flexible and accurate dialogue state tracking.  _arXiv preprint arXiv:1907.00883_ .
  * Gunasekara et al. (2020) Gunasekara, C.; Kim, S.; D’Haro, L. F.; Rastogi, A.; Chen, Y.-N.; Eric, M.; Hedayatnia, B.; Gopalakrishnan, K.; Liu, Y.; Huang, C.-W.; Hakkani-Tür, D.; Li, J.; Zhu, Q.; Luo, L.; Liden, L.; Huang, K.; Shayandeh, S.; Liang, R.; Peng, B.; Zhang, Z.; Shukla, S.; Huang, M.; Gao, J.; Mehri, S.; Feng, Y.; Gordon, C.; Alavi, S. H.; Traum, D.; Eskenazi, M.; Beirami, A.; Eunjoon; Cho; Crook, P. A.; De, A.; Geramifard, A.; Kottur, S.; Moon, S.; Poddar, S.; and Subba, R. 2020.  Overview of the Ninth Dialog System Technology Challenge: DSTC9.
  * Henderson, Thomson, and Young (2014) Henderson, M.; Thomson, B.; and Young, S. 2014.  Word-based dialog state tracking with recurrent neural networks.  In _Proceedings of the 15th Annual Meeting of the Special Interest Group on Discourse and Dialogue (SIGDIAL)_ , 292–299.
  * Hochreiter and Schmidhuber (1997) Hochreiter, S.; and Schmidhuber, J. 1997.  Long short-term memory.  _Neural computation_ 9(8): 1735–1780.
  * Kim et al. (2019) Kim, S.; Yang, S.; Kim, G.; and Lee, S.-W. 2019.  Efficient dialogue state tracking by selectively overwriting memory.  _arXiv preprint arXiv:1911.03906_ .
  * Le, Socher, and Hoi (2020) Le, H.; Socher, R.; and Hoi, S. C. 2020.  Non-autoregressive dialog state tracking.  _arXiv preprint arXiv:2002.08024_ .
  * Lee, Lee, and Kim (2019) Lee, H.; Lee, J.; and Kim, T.-Y. 2019.  Sumbt: Slot-utterance matching for universal and scalable belief tracking.  _arXiv preprint arXiv:1907.07421_ .
  * Liu et al. (2019) Liu, Y.; Ott, M.; Goyal, N.; Du, J.; Joshi, M.; Chen, D.; Levy, O.; Lewis, M.; Zettlemoyer, L.; and Stoyanov, V. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ .
  * Ren et al. (2018) Ren, L.; Xie, K.; Chen, L.; and Yu, K. 2018.  Towards universal dialogue state tracking.  _arXiv preprint arXiv:1810.09587_ .
  * Shan et al. (2020) Shan, Y.; Li, Z.; Zhang, J.; Meng, F.; Feng, Y.; Niu, C.; and Zhou, J. 2020.  A Contextual Hierarchical Attention Network with Adaptive Objective for Dialogue State Tracking.  _arXiv preprint arXiv:2006.01554_ .
  * Sharma, Choubey, and Huang (2019) Sharma, S.; Choubey, P. K.; and Huang, R. 2019.  Improving dialogue state tracking by discerning the relevant context.  _arXiv preprint arXiv:1904.02800_ .
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , 5998–6008.
  * Wu et al. (2019) Wu, C.-S.; Madotto, A.; Hosseini-Asl, E.; Xiong, C.; Socher, R.; and Fung, P. 2019\.  Transferable multi-domain state generator for task-oriented dialogue systems.  _arXiv preprint arXiv:1905.08743_ .
  * Yang et al. (2019) Yang, Z.; Dai, Z.; Yang, Y.; Carbonell, J.; Salakhutdinov, R. R.; and Le, Q. V. 2019\.  Xlnet: Generalized autoregressive pretraining for language understanding.  In _Advances in neural information processing systems_ , 5753–5763.
  * Zhang et al. (2019) Zhang, J.-G.; Hashimoto, K.; Wu, C.-S.; Wan, Y.; Yu, P. S.; Socher, R.; and Xiong, C. 2019.  Find or classify? dual strategy for slot-value predictions on multi-domain dialog state tracking.  _arXiv preprint arXiv:1910.03544_ .
  * Zhu et al. (2020) Zhu, Q.; Huang, K.; Zhang, Z.; Zhu, X.; and Huang, M. 2020.  Crosswoz: A large-scale chinese cross-domain task-oriented dialogue dataset.  _arXiv preprint arXiv:2002.11893_ .