\section{Introduction}

In the past decade, goal-oriented spoken dialogue systems (SDS), such as the virtual personal assistants Microsoft's Cortana and Apple's Siri, are being incorporated in various devices and allow users to speak to systems freely in order to finish tasks more efficiently.
A key component of these conversational systems is the natural language understanding (NLU) module—-it refers to the targeted understanding of human speech directed at machines~\cite{tur2011spoken}.
The goal of such ``targeted'' understanding is to convert the recognized user speech into a task-specific semantic representation of the user's intention, at each turn, that aligns with the back-end knowledge and action sources for task completion.
The dialogue manager then interprets the semantics of the user's request and associated back-end results, and decides the most appropriate system action, by exploiting semantic context and user specific meta-information, such as geo-location and personal preferences~\cite{mctear2004spoken,rudnicky1999agenda}.

A typical pipeline of NLU includes:
domain classification, intent determination, and slot filling~\cite{tur2011spoken}.
NLU first decides the domain of user's request given the input utterance, and based on the domain, predicts the intent and fills associated slots corresponding to a domain-specific semantic template.
For example, Figure~\ref{fig:iob} shows a user utterance, ``\textit{show me the flights from seattle to san francisco}'' and its semantic frame, \textsf{find\_flight(origin=``seattle'', dest=``san francisco'')}.
It is easy to see the relationship between the origin city and the destination city in this example, although these do not appear next to each other. 
Traditionally, domain detection and intent prediction are framed as utterance classification problems, where several classifiers such as support vector machines and maximum entropy have been employed~\cite{haffner2003optimizing,chelba2003speech,chen2014deriving}.
Then slot filling is framed as a word sequence tagging task, where the IOB (in-out-begin) format is applied for representing slot tags as illustrated in Figure~\ref{fig:iob}, and hidden Markov models (HMM) or conditional random fields (CRF) have been employed for slot tagging~\cite{pieraccini1992speech,wang2005spoken}.

\begin{figure}[t]
	\centering
    \includegraphics[width=0.9\linewidth]{iob.pdf}
    \vspace{-2mm}
    \caption{An example utterance annotated with its semantic slots in the IOB format (S).}
\vspace{-4mm}
    \label{fig:iob}
\end{figure}

With the advances on deep learning, deep belief networks (DBNs) with deep neural networks (DNNs) have been applied to domain and intent classification tasks~\cite{sarikaya2011deep,tur2012towards,sarikaya2014application}.
Recently, \newcite{ravuri2015recurrent} proposed an RNN architecture for intent determination.
For slot filling, deep learning has been viewed as a feature generator and the neural architecture can be merged with CRFs~\cite{xu2013convolutional}.
\newcite{yao2013recurrent} and \newcite{mesnil2015using} later employed RNNs for sequence labeling in order to perform slot filling.
However, the above studies benefit from large training data without leveraging any existing knowledge.
When tagging sequences RNNs consider them as flat structures, with their underlying linear chain structures, potentially ignoring the structured information typical of natural language sequences.

Hierarchical structures and semantic relationships contain linguistic characteristics of input word sequences forming sentences, and such information may help interpret their meaning.
Furthermore, prior knowledge would help in the tagging of sequences, especially when dealing with previously unseen sequences~\cite{tur2010left,deoras2013deep}.
Prior work exploited external web-scale knowledge graphs such as Freebase and Wikipedia for improving NLU~\cite{heck2013leveraging,ma2015knowledge,chen2014deriving}
\newcite{liu2013query} and \newcite{chen2015matrix} proposed approaches that leverage linguistic knowledge encoded in parse trees for language understanding, where the extracted syntactic structural features and semantic dependency features enhance inference model learning, and the model achieves better language understanding performance in various domains.

Even with the emerging paradigm of integrating deep learning and linguistic knowledge for different NLP tasks~\cite{socher2014grounded}, most of the previous work utilized such linguistic knowledge and knowledge bases as additional features as input to neural networks, and then learned the models for tagging sequences.
These feature enrichment based approaches have some possible limitations:
1) poor generalization and 2) error propagation.
Poor generalization comes from the mismatch between knowledge bases and the input data, and then the incorrectly extracted features due to errors in previous processing propagate errors to the neural models.
In order to address the issues and better learn the sequence tagging models, this paper proposes knowledge-guided structural attention networks, K-SAN, a generalization of RNNs that automatically learn the attention guided by external or prior knowledge and generate sentence-based representations specifically for modeling sequence tagging.
The main difference between K-SAN and previous approaches is that knowledge plays the role of a teacher to guide networks where and how much to focus attention considering the whole linguistic structure simultaneously.
Our main contributions are three-fold:
\begin{itemize}
\vspace{-1.5mm}
\item End-to-end learning\\
To our knowledge, this is the first neural network approach that utilizes general knowledge as guidance in an end-to-end fashion, where the model automatically learns important substructures with an attention mechanism.
\vspace{-1.5mm}
\item Generalization for different knowledge\\
There is no required schema of knowledge, and different types of parsing results, such as dependency relations, knowledge graph-specific relations, and parsing output of hand-crafted grammars, can serve as the knowledge guidance in this model.
\vspace{-1.5mm}
\item Efficiency and parallelizability\\
Because the substructures from the input utterance are modeled separately, modeling time may not increase linearly with respect to the number of words in the input sentence.
\vspace{-1.5mm}
\end{itemize}
In the following sections, we empirically show the benefit of K-SAN on the targeted NLU task.

\section{Related Work}
\label{sec:related}

\paragraph{Knowledge-Based Representations}

There is an emerging trend of learning representations at different levels, such as word embeddings~\cite{mikolov2013distributed}, character embeddings~\cite{ling2015finding}, and sentence embeddings~\cite{le2014distributed,huang2013learning}.
In addition to fully unsupervised embedding learning,
knowledge bases have been widely utilized to learn entity embeddings with specific functions or relations~\cite{celikyilmaz2015unsupervised,yang2014embedding}.
Different from prior work, this paper focuses on learning composable substructure embeddings that are informative for understanding.

Recently linguistic structures are taken into account in the deep learning framework.
\newcite{ma2015dependency} and \newcite{tai2015improved} both proposed dependency-based approaches to combine deep learning and linguistic structures, where the model used tree-based n-grams instead of surface ones to capture knowledge-guided relations for sentence modeling and classification.
\newcite{roth2016neural} utilized lexicalized dependency paths to learn embedding representations for semantic role labeling.
However, the performance of these approaches highly depends on the quality of ``whole'' sentence parsing, and there is no control of degree of attentions on different substructures.
Learning robust representations incorporating whole structures still remains unsolved.
In this paper, we address the limitation by proposing K-SAN to learn robust representations of whole sentences, where the whole representation is composed of the salient substructures in order to avoid error propagation.

\paragraph{Neural Attention and Memory Model}

One of the earliest work with a memory component applied to language processing is memory networks~\cite{weston2015memory,sukhbaatar2015end}, which encode facts into vectors and store them in the memory for question answering (QA).
Following their success, \newcite{xiong2016dynamic} proposed dynamic memory networks (DMN) to additionally capture position and temporality of transitive reasoning steps for different QA tasks.
The idea is to encode important knowledge and store it into memory for future usage with attention mechanisms.
Attention mechanisms allow neural network models to selectively pay attention to specific parts.
There are also various tasks showing the effectiveness of attention mechanisms.

However, most previous work focused on the classification or prediction tasks (predicting a single word given a question), and there are few studies for NLU tasks (slot tagging).
Based on the fact that the linguistic or knowledge-based substructures can be treated as prior knowledge to benefit language understanding, this work borrows the idea from memory models to improve NLU.
Unlike the prior NLU work that utilized representations learned from knowledge bases to enrich features of the current sentence, this paper directly learns a sentence representation incorporating memorized substructures with an automatically decided attention mechanism in an end-to-end manner.


\section{Knowledge-Guided Structural Attention Networks (K-SAN)}
\label{sec:model}

For the NLU task, given an utterance with a sequence of words/tokens $\vec{s} = w_1, ..., w_T$, our model is to predict corresponding semantic tags $\vec{y} = y_1, ..., y_T$ for each word/token by incorporating knowledge-guided structures.
The proposed model is illustrated in Figure~\ref{fig:model}.
The knowledge encoding module first leverages external knowledge to generate a linguistic structure for the utterance, where a discrete set of knowledge-guided substructures $\{x_i\}$ is encoded into a set of vector representations (\ref{ssec:kg_encoding}).
The model learns the representation for the whole sentence by paying different attention on the substructures (\ref{ssec:arch}).
Then the learned vector encoding the knowledge-guided structure is used for improving the semantic tagger (\ref{sec:tagger}).

\begin{figure*}[t]
\centering
\vspace{-2mm}
\includegraphics[width=\linewidth]{model.pdf}
\vspace{-5mm}
\caption{The illustration of knowledge-guided structural attention networks (K-SAN) for NLU.}
\label{fig:model}
\vspace{-2mm}
\end{figure*}

\subsection{Knowledge Encoding Module}
\label{ssec:kg_encoding}

\begin{figure}[t]
\centering
\vspace{-2mm}
\includegraphics[width=\linewidth]{dep_tree.pdf}
\vspace{-4mm}
\caption{The knowledge-guided substructures of dependency parsing, $x_i$, on an example sentence $s$.}
\vspace{-2mm}
\label{fig:tree}
\end{figure}

The prior knowledge obtained from external resources, such as dependency relations, knowledge bases, etc., provides richer information to help decide the semantic tags given an input utterance.
This paper takes dependency relations as an example for knowledge encoding, and other structured relations can be applied in the same way.
The input utterance is parsed by a dependency parser, and the substructures are built according to the paths from the root to all leaves~\cite{chen2014fast}.
For example, the dependency parsing of the utterance ``{\it show me the flights from seattle to san francisco}'' is shown in Figure~\ref{fig:tree}, where the associated substructures are obtained from the parsing tree for knowledge encoding.
Here we do not utilize the dependency relation labels in the experiments for better generalization, because the labels may not be always available for different knowledge resources.
Note that the number of substructures may be less than the number of words in the utterance, because non-leaf nodes do not have corresponding substructure in order to reduce the duplicated information in the model.
The top-left component of Figure~\ref{fig:model} illustrates the module for modeling knowledge-guided substructures.





\subsection{Model Architecture}
\label{ssec:arch}
The model embeds all knowledge-guided substructures into a continuous space and stores embeddings of all $x$'s in the knowledge memory.
The representation of the input utterance is then compared with encoded knowledge representations to integrate the carried structure guided by knowledge via an attention mechanism.
Then the knowledge-guided representation of the sentence is taken together with the word sequence for estimating the semantic tags.
Four main procedures are described below.

\paragraph{Encoded Knowledge Representation}
To store the knowledge-guided structure, we convert each substructure (e.g. path starting from the root to the leaf in the dependency tree), $x_i$, into a structure vector $m_i$ with dimension $d$ by embedding the substructure in a continuous space through the knowledge encoding model $M_\text{kg}$.
The input utterance $s$ is also embedded to a vector $u$ with the same dimension through the model $M_\text{in}$.
\begin{eqnarray}
m_i &=& M_\text{kg}(x_i),\\
u &=& M_\text{in}(s).
\end{eqnarray}
We apply the three types for knowledge encoding models, $M_\text{kg}$ and $M_\text{in}$, in order to model multiple words from a substructure $x_i$ or an input sentence $s$ into a vector representation:
1) fully-connected neural networks (NN) with linear activation, 
2) recurrent neural networks (RNN),
and 3) convolutional neural networks (CNN) with a window size 3 and a max-pooling operation.
For example, one of substructures shown in Figure~\ref{fig:tree}, ``{\it show flights seattle from}'', is encoded into a vector embedding.
In the experiments, the weights of $M_\text{kg}$ and $M_\text{in}$ are tied together based on their consistent ability of sequence encoding.

\paragraph{Knowledge Attention Distribution}
In the embedding space, we compute the match between the current utterance vector $u$ and its substructure vector $m_i$ by taking their inner product followed by a softmax.
\begin{equation}
p_i = \text{softmax}(u^T m_i),
\end{equation}
where $\text{softmax}(z_i) = e^{z_i} / \sum_j e^{z_j}$ and $p_i$ can be viewed as attention distribution for modeling important substructures from external knowledge in order to understand the current utterance.

\paragraph{Sentence Representation}
In order to encode the knowledge-guided structure, 
a vector $h$ is a sum over the encoded knowledge embeddings weighted by the attention distribution.
\begin{equation}
h = \sum_i p_i m_i,
\end{equation}
which indicates that the sentence pays different attention to different substructures guided from external knowledge.
Because the function from input to output is smooth, we can easily compute gradients and back propagate through it.
Then the sum of the substructure vector $h$ and the current input embedding $u$ are then passed through a neural network model $M_\text{out}$ to generate an output knowledge-guided representation $o$.
\begin{equation}
\label{eq:encoding}
o = M_\text{out}(h + u),
\end{equation}
where we employ a fully-connected dense network for $M_\text{out}$.

\paragraph{Sequence Tagging}
To estimate the tag sequence $\vec{y}$ corresponding to an input word sequence $\vec{s}$, we use an RNN module for training a slot tagger, where the knowledge-guided representation $o$ is fed into the input of the model in order to incorporate the structure information.
\begin{equation}
\vec{y} = \text{RNN}(o, \vec{s})
\end{equation}

\section{Recurrent Neural Network Tagger}
\label{sec:tagger}
\subsection{Chain-Based RNN Tagger}

Given $\vec{s} = w_1, ..., w_T$, the model is to predict $\vec{y} = y_1, ..., y_T$ where the tag $y_i$ is aligned with the word $w_i$.
We use the Elman RNN architecture, consisting of an input layer, a hidden layer, and an output layer~\cite{elman1990finding}.
The input, hidden and output layers consist of a set of neurons representing the input, hidden, and output at each time step $t$, $w_t$, $h_t$, and $y_t$, respectively.
\begin{eqnarray}
\label{eq:hidden}
h_t &=& \phi(W w_t + U h_{t-1}),\\
\label{eq:y}
\hat{y_t} &=& \text{softmax}(V h_t),
\end{eqnarray}
where $\phi$ is a smooth bounded function such as tanh, and $\hat{y_t}$ is the probability distribution over of semantic tags given the current hidden state $h_t$.
The sequence probability can be formulated as
\begin{equation}
\label{eq:obj}
p(\vec{y}\mid \vec{s}) = p(\vec{y}\mid w_1, ..., w_T) = \prod_i p(y_i\mid w_1, ..., w_i).
\end{equation}
The model can be trained using backpropagation to maximize the conditional likelihood of the training set labels.

To overcome the frequent vanishing gradients issue when modeling long-term dependencies, gated RNN was designed to use a more sophisticated activation function than a usual activation function, consisting of affine transformation followed by a simple element-wise nonlinearity by using gating units~\cite{chung2014empirical}, such as long short-term memory (LSTM) and gated recurrent unit (GRU)~\cite{hochreiter1997long,cho2014properties}.
RNNs employing either of these recurrent units have been shown to perform well in tasks that require capturing long-term dependencies~\cite{mesnil2015using,yao2014spoken,graves2013speech,sutskever2014sequence}.
In this paper, we use RNN with GRU cells to allow each recurrent unit to adaptively capture dependencies of different time scales~\cite{cho2014properties,chung2014empirical},
because RNN-GRU can yield comparable performance as RNN-LSTM with need of fewer parameters and less data for generalization~\cite{chung2014empirical}

A GRU has two gates, a \emph{reset gate} $r$, and an \emph{update gate} $z$~\cite{cho2014properties,chung2014empirical}.
The reset gate determines the combination between the new input and the previous memory, and the update gate decides how much the unit updates its activation, or content.
\begin{eqnarray}
\label{eq:reset}
r &=& \sigma( W^r w_t + U^r h_{t-1}),\\
\label{eq:update}
z &=& \sigma( W^z w_t + U^z h_{t-1}),
\end{eqnarray}
where $\sigma$ is a logistic sigmoid function.

Then the final activation of the GRU at time $t$, $h_t$, is a linear interpolation between the previous activation $h_{t-1}$ and the candidate activation $\tilde{h_t}$:
\begin{eqnarray}
\label{eq:candidate_h}
h_t &=& (1 - z) \odot \tilde{h_t} + z \odot h_{t-1}, \\
\tilde{h_t} &=& \phi( W^h w_t + U^h (h_{t-1}\odot r) )),
\end{eqnarray}
where $\odot$ is an element-wise multiplication.
When the reset gate is off,
it effectively makes the unit act as if it is reading the first symbol of an input sequence,
allowing it to forget the previously computed state.
Then $\hat{y_t}$ can be computed by (\ref{eq:y}).

\subsection{Knowledge-Guided RNN Tagger}
In order to model the encoded knowledge from previous turns, for each time step $t$, the knowledge-guided sentence representation $o$ in (\ref{eq:encoding}) is fed into the RNN model together with the word $w_t$.
For the plain RNN, the hidden layer can be formulated as
\begin{equation}
h_t = \phi(M o + W w_t + U h_{t-1})
\end{equation}
to replace (\ref{eq:hidden}) as illustrated in the right block of Figure~\ref{fig:model}.
RNN-GRU can incorporate the encoded knowledge in the similar way, where $M o$ can be added into gating mechanisms for modeling contextual knowledge similarly.

\begin{figure}[t]
\vspace{-2mm}
\centering
\includegraphics[width=\linewidth]{joint_tagger.pdf}
\vspace{-5mm}
\caption{The joint tagging model that incorporates a chain-based RNN tagger (upper block) and a knowledge-guided RNN tagger (lower block).}
\vspace{-3mm}
\label{fig:joint_tagger}
\end{figure}

\subsection{Joint RNN Tagger}
Because the chain-based tagger and the knowledge-guided tagger carry different information, the joint RNN tagger is proposed to balance the information between two model architectures.
Figure~\ref{fig:joint_tagger} presents the architecture of the joint RNN tagger.
\begin{eqnarray}
h_t^1 &=& \phi(W^1 w_t + U^1 h_{t-1}),\\
h_t^2 &=& \phi(M o + W^2 w_t + U^2 h_{t-1}),\\
\hat{y}_t &=& \text{softmax}(V(\alpha h_t^1 + (1 - \alpha) h_t^2)),
\end{eqnarray}
where $\alpha$ is the weight for balancing chain-based and knowledge-guided information.
By jointly considering chain-based information ($h_t^1$) and knowledge-guided information ($h_t^2$), the joint RNN tagger is expected to achieve better generalization, and the performance may be less sensitive to poor structures from external knowledge. In the experiments, $\alpha$ is set to $0.5$ for balancing two sides.
The objective of the proposed model is to maximize the sequence probability $p(\vec{y}\mid \vec{s})$ in (\ref{eq:obj}), and the model can be trained in an end-to-end manner, where the error would be back-propagated through the whole architecture.



\section{Experiments}
\label{sec:exp}

\begin{table*}[t]
    \centering
  \begin{tabular}{llclccc}
\hline
\multirow{2}{*}{} & \multicolumn{3}{c}{Model} & \multicolumn{3}{c}{Dataset} \\
\cline{2-7}
& Encoder ($M_\text{kg}$/$M_\text{in}$) & Knowledge & Tagger & Small & Medium & Large\\
\hline\hline
Baseline & - & \xmark & CRF & 58.94 & 78.74 & 89.73 \\
 & - & \xmark & RNN & 68.58 & 84.55 & 92.97 \\
& CNN & \xmark & RNN & 73.57 & 85.52 & 93.88\\
\hline
Structural & - & \cmark & CRF & 59.55 & 78.71 & 90.13\\
& DCNN & \cmark & RNN & 70.24 & 83.80 & 93.25\\
& Tree-RNN & \cmark & RNN & 73.50  & 83.92 & 92.28 \\
\hline
Proposed & K-SAN (NN) & \cmark & RNN & 74.11$^\dag$ & 85.97 & 93.98$^\dag$ \\
& K-SAN (RNN) & \cmark & RNN & 73.13 & 86.85$^\dag$ & \bf 94.97$^\dag$ \\
& K-SAN (CNN) & \cmark & RNN & \bf 74.60$^\dag$ & \bf 87.99$^\dag$ & 94.86$^\dag$ \\
\hline
  \end{tabular}
  \caption{The F1 scores of predicted slots on the different size of ATIS training examples, where K-SAN utilizes the dependency relations parsed from the Stanford parser. Small: 1/40 set; Medium: 1/10 set; Large: original set. ($\dag$ indicates that the performance is significantly better than all baseline models with $p<0.05$ in the t-test.)}
  \label{tab:result}
\vspace{-3mm}
\end{table*}

\subsection{Experimental Setup}
The dataset for experiments is the benchmark ATIS corpus, which is extensively used by the NLU community~\cite{mesnil2015using}.
There are 4978 training utterances selected from Class A (context independent) in the ATIS-2 and ATIS-3, while there are 893 utterances selected from the ATIS-3 Nov93 and Dec94.
In the experiments, we only use lexical features.
In order to show the robustness to data scarcity, we conduct the experiments with 3 different sizes of training data (Small, Medium, and Large), where Small is 1/40 of the original set, Medium is 1/10 of the original set, and Large is the full set.
The evaluation metrics for NLU is F-measure on the predicted slots\footnote{The used evaluation script is \texttt{conlleval}.}.

For experiments with K-SAN, we parse all data with the Stanford dependency parser~\cite{chen2014fast} and represent words as their embeddings trained on the in-domain data, where the parser is pre-trained on PTB.
The loss function is cross-entropy, and the optimizer we use is adam with the default setting~\cite{kingma2014adam}, where the learning rate $\lambda=0.001$, $\beta_1=0.9$, $\beta_2=0.999$, and $\epsilon=1e^{-08}$.
The maximum iteration for training our K-SAN models is set as 300.
The dimensionality of input word embeddings is 100, and the hidden layer sizes are in $\{50, 100, 150\}$.
The dropout rates are set as $\{0.25, 0.50\}$.
All reported results are from the joint RNN tagger, and the hyperparameters are tuned in the dev set for all experiments.





\subsection{Baseline}

To validate the effectiveness of the proposed model, we compare the performance with the following baselines.
\begin{itemize}
\vspace{-1mm}
\item Baseline:
\begin{itemize}
\vspace{-1mm}
\item CRF Tagger~\cite{tur2010left}: predicts a semantic slot for each word with a context window (size = 5).
\vspace{-1mm}
\item RNN Tagger~\cite{mesnil2015using}: predicts a semantic slot for each word.
\vspace{-1mm}
\item CNN Encoder-Tagger~\cite{kim2014convolutional}: tag semantic slots with consideration of sentence embeddings learned by a convolutional model.
\vspace{-1mm}
\end{itemize}
\vspace{-1mm}
\item Structural: The NLU models utilize linguistic information when tagging slots, where DCNN and Tree-RNN are the state-of-the-art approaches for embedding sentences with linguistic structures.
\begin{itemize}
\vspace{-1mm}
\item CRF Tagger~\cite{tur2010left}: predicts slots based on the lexical (5-word window) and syntactic (dependent head in the parsing tree) features.
\vspace{-1mm}
\item DCNN~\cite{ma2015dependency}: predicts slots by incorporating sentence embeddings learned by a convolutional model with consideration of dependency tree structures.
\vspace{-1mm}
\item Tree-RNN~\cite{tai2015improved}: predicts slots with sentence embeddings learned by an RNN model based on the tree structures of sentences.
\vspace{-1mm}
\end{itemize}
\vspace{-1mm}
\end{itemize}


\begin{figure*}[t]
\vspace{-1mm}
\centering
\includegraphics[width=0.92\linewidth]{attention_comparison.pdf}
\vspace{-3mm}
\caption{The visualization of the decoded knowledge-guided structural attention for both {\bf relations} and {\bf words} learned from different size of training data. Relations and words with darker color indicate higher attention weights generated by the proposed K-SAN with CNN. The slot tags are shown in the figure for reference.
Note that the dependency relations are incorrectly parsed by the Stanford parser in this example, but our model is still able to benefit from the structural information.}
\vspace{-2mm}
\label{fig:attention}
\end{figure*}

\subsection{Slot Filling Results}
Table~\ref{tab:result} shows the performance of slot filling on different size of training data, where there are three datasets (Small, Medium, and Large use 1/40, 1/10, and whole training data).
For baselines (models without knowledge features), CNN Encoder-Tagger achieves the best performance on all datasets.

Among structural models (models with knowledge encoding), Tree-RNN Encoder-Tagger performs better for Small data but slightly worse than the DCNN Encoder-Tagger.

CNN~\cite{kim2014convolutional} performs better compared to DCNN~\cite{ma2015dependency} and Tree-RNN~\cite{tai2015improved}, even though CNN does not leverage external knowledge when encoding sentences.
When comparing the NLU performance between baselines and other state-of-the-art structural models, there is no significant difference.
This suggests that encoding sentence information without distinguishing substructure may not capture salient semantics in order to improve understanding performance.

Among the proposed K-SAN models, CNN for encoding performs best on Small (75\% on F1) and Medium (88\% on F1), and RNN for encoding performs best on the Large set (95\% on F1).
Also, most of the proposed models outperform all baselines, where the improvement for the small dataset is more significant.
This suggests that the proposed models carry better generalization and are less sensitive to unseen data.
For example, given an utterance ``{\it which flights leave on monday from montreal and arrive in chicago in the morning}'', ``{\it morning}'' can be correctly tagged with a semantic tag \textsf{B-arrive\_time.period\_of\_day} by K-SAN, but it is incorrectly tagged with \textsf{B-depart\_time.period\_of\_day} by baselines, because knowledge guides the model to pay correct attention to salient substructures.
The proposed model presents the state-of-the-art performance on the large dataset (RNN-BLSTM in baselines), showing the effectiveness of leveraging knowledge-guided structures for learning embeddings that can be used for specific tasks and the robustness to data scarcity and mismatch.

\subsection{Attention Analysis}

In order to show the effectiveness of boosting performance by learning correct attention from much smaller training data through the proposed model,
we present the visualization of the attention for both words and relations decoded by K-SAN with CNN in the Figure~\ref{fig:attention}.
The darker color of blocks and lines indicates the higher attention for words and relations respectively.
From the figure, the words and the relations with higher attention are the most crucial parts for predicting correct slots, e.g. origin, destination, and time.
Furthermore, the difference of attention distribution between three datasets is not significant; this suggests that our proposed model is able to pay correct attention to important substructures guided by the external knowledge even the training data is scarce.

\begin{figure*}[htb]
\begin{minipage}[b]{.47\linewidth}
  \centering
  \centerline{\includegraphics[width=\linewidth]{dep}}
  \centerline{(a) Syntax: the dependency tree}\medskip
\end{minipage}
\hfill
\begin{minipage}[b]{0.47\linewidth}
  \centering
  \centerline{\includegraphics[width=\linewidth]{amr}}
  \centerline{(b) Semantics: the AMR graph}\medskip
\end{minipage}
\vspace{-4mm}
\caption{The constructing procedure of knowledge-guided substructures, $x_i$, on an example sentence $s$.}
\label{fig:substructure}
\end{figure*}

\begin{table*}[t]
    \centering
  \begin{tabular}{cllrccc}
\hline
Approach & \multicolumn{3}{c}{Knowledge (Max \#Substructure)} & Small & Medium & Large\\
\hline\hline
\multirow{4}{*}{CRF} & \multirow{2}{*}{Dependency Tree} & Stanford & - & 59.55 & 78.71 & 90.13\\
 & & SyntaxNet & - & 61.09 & 78.87 & 90.92\\
 \cline{2-7}
 & \multirow{2}{*}{AMR Graph} & Rule-Based & - & 59.55 & 79.15 & 89.97\\
 & & JAMR & - & 61.12 & 78.64 & 90.25\\
\hline
\multirow{4}{*}{K-SAN (CNN)} & \multirow{2}{*}{Dependency Tree} & Stanford & 53 & \bf 74.60 & 87.99 & 94.86 \\
& & SyntaxNet & 25 & 74.35 & \bf 88.40 & \bf 95.00\\
 \cline{2-7}
& \multirow{2}{*}{AMR Graph} & Rule-Based & 19 & 74.32 & 88.14 & 94.85\\
& & JAMR & 8 & 74.27 & 88.27 & 94.89\\
\hline
  \end{tabular}
  \vspace{-1.5mm}
  \caption{The F1 scores of predicted slots with knowledge from different resources.}
  \label{tab:parser}
\vspace{-2mm}
\end{table*}

\subsection{Knowledge Generalization}
In order to show the capacity of generalization to different knowledge resources, we perform the K-SAN model for different knowledge bases.
Below we compare two types of knowledge formats: dependency tree and Abstract Meaning Representation (AMR).
AMR is a semantic formalism in which the meaning of a sentence is encoded as a rooted, directed, acyclic graph~\cite{banarescu2013amr}, where nodes represent concepts, and labeled directed edges represent the relations between two concepts.
The formalism is based on propositional logic and neo-Davidsonian event representations~\cite{parsons1990events,davidson1967logical}.
The semantic concepts in AMR were leveraged to benefit multiple NLP tasks~\cite{liu2015toward}.
Unlike syntactic information from dependency trees, the AMR graph contains semantic information, which may offer more specific conceptual relations.
Figure~\ref{fig:substructure} shows the comparison of a dependency tree and an AMR graph associated with the same example utterance and how the knowledge-guided substructures are constructed.

Table~\ref{tab:parser} presents the performance of CRF and K-SAN with CNN taggers that utilize dependency relations and AMR edges as knowledge guidance on the same datasets, where CRF takes the head words from either dependency trees or AMR graphs as additional features and K-SAN incorporates knowledge-guided substructures as illustrated in Figure~\ref{fig:substructure}.
The dependency trees are obtained from the Stanford dependency parser or the SyntaxNet parser\footnote{\url{https://github.com/tensorflow/models/tree/master/syntaxnet}}, and AMR graphs are generated by a rule-based AMR parser or JAMR\footnote{\url{https://github.com/jflanigan/jamr}}.

Among four knowledge resources (different types and obtained from different parsers), all results show the similar performance for three sizes of datasets.
The maximum number of substructures for the dependency tree is larger than the number in the AMR graph (53 and 25 v.s. 19 and 8), because syntax is more general and may provide richer cues for guiding more attention while semantics is more specific and may offer stronger guidance.
In sum, the models applying four different resources achieve similar performance, and all significantly outperform the state-of-the-art NLU tagger, showing the effectiveness, generalization, and robustness of the proposed K-SAN model.

\section{Conclusion}
\label{sec:con}
This paper proposes a novel model, knowledge-guided structural attention networks (K-SAN), that leverages prior knowledge as guidance to incorporate non-flat topologies and learn suitable attention for different substructures that are salient for specific tasks.
The structured information can be captured from small training data, so the model has better generalization and robustness.
The experiments show benefits and effectiveness of the proposed model on the language understanding task, where all knowledge-guided substructures captured by different resources help tagging performance, and the state-of-the-art performance is achieved on the ATIS benchmark dataset.

\newpage
