\section{Introduction}

\begin{figure*}[t]
\center
\includegraphics[width=7in]{differencewithMDNet}
\caption{The definition of tracking by natural language specification (left sub-figure) and loss functions we used for the optimization of our tracker (right sub-figure). }
\label{differencewithMDNet}
\end{figure*}

As a classical and challenge task in computer vision, visual tracking has been widely used in various applications, such as intelligent surveillance and automatic driving. Although appealing results have been achieved, visual tracking is still challenging partly due to the existences of the extreme factors including heavy occlusion, abruptly changing, large deformation and out of view.

Most successful visual trackers follow the tracking-by-detection framework, in which a set of positive and negative samples are used to train the parameters of classifiers and deep representations. However, existing tracking models mostly treat different training samples independently while ignores the relationship information among them, which is crucial to the robustness of feature representation and classifier learning. For instance, when we attempt to estimate the response score of one sample, existing approaches only consider the relationship between positive and negative samples. Other relations among different sample pairs are ignored. As a result, some hard positive or negative samples are difficult to obtain proper response score since only limited relationship information among samples is utilized for the overall estimation.

Recently, natural language is introduced in visual tracking, which achieves improved tracking performance~\cite{Li2017Tracking}. For example, Li \emph{et al.}~\cite{Li2017Tracking} propose three models including natural language only, visual target specification based on language, and leveraging their joint capacity, to help visual trackers against model drift. However, they use the Recurrent Neural Network (RNN) model to encode the input sentences to generate a dynamic filter, in which the RNN module would increase heavy computational burden on the tracking speed. Moreover, how to use natural language to guide the learning of graph-based structural feature representations remains not studied yet.

To handle above problems, we propose a novel structure-aware deep neural network that is end-to-end trained for visual tracking.  On the one hand, we utilize the graph convolutional network (GCN) to model the relations among training samples. Specifically, we first take them as graph nodes and use the standard convolutional network to extract their features. To fully utilize the spatial and temporal relations among samples (\emph{i.e.}, graph nodes), the deeply learned messages are then propagated among nodes via GCN to update and refine the pairwise relation feature for each node. After that, we form the final feature representation for each proposal by concatenating the enhanced and the original feature. On the other hand, we treat natural language embedding as high-level semantic information to guide the structural feature learning in the training phrase with triplet loss function, as shown in Figure \ref{differencewithMDNet} (b).

In the visual tracking task, the targets are easily lost when heavy occlusion occurs and they are out of view. It is difficult to re-track the targets when they are back to view as online update scheme adopted in most tracking methods will contaminate tracking models and the used local search strategy is also limited to recover the targets. Although some trackers employ the strategy of target re-detection~\cite{liu2018robust}, how to judge whether tracking failures occur or not is a challenging problem, and the re-detection models are too weak to recover the targets effectively when they reappear. To handle this problem, we elaborately design a novel subnetwork to learn the target-driven visual attentions from the guidance of both visual and natural language cues. Specifically, we use convolutional network to encode all the input data, i.e., the whole video frame, target object patch and natural language specification, for more efficient computation. The features are concatenated and input to an upsample module to generate the target-driven attention maps. The global proposals can be extracted from the attention regions and then input to the classifier together with local proposals. Therefore, in addition to providing complementary proposals to local ones, the global proposals could cover the targets well when they are back to view from heavy occlusion and out of view.

Generally speaking, our proposed algorithm is more intelligent by mining more structure information and exploring high-quality global proposal generation via target-driven visual attention. The contributions of this paper can be summarized as the following three aspects:
	\begin{itemize}
	\item We propose an effective approach to handle the challenges of significant appearance changes, heavy occlusion and out of view in visual tracking. Extensive experiments on five tracking benchmarks against some recent and state-of-the-art trackers demonstrate that our proposed tracker is more robust to aforementioned challenging factors.
	\item We propose a novel structure-aware deep neural network to make best use of the structures between training sample pairs and thus enhance the discriminative ability of feature representations. To make feature representations more discriminative, we introduce the natural language of target objects to assist visual feature learning via a triplet loss function.
	\item We elaborately design a novel global proposal generation network to the target-driven visual attentions from the guidance of both visual and natural language cues. Benefit from the global proposals, our tracker is able to re-track the target objects that are lost caused by the challenges of heavy occlusion and out of view.
	\end{itemize}

\begin{figure*}[t]
\center
\includegraphics[width=6in]{pipeline-overallframework}
\caption{The pipeline of our proposed tracking algorithm. }
\label{pipelineAll}
\end{figure*}

\section{Related Works}
We give a brief review about tracking algorithms related to this paper as follows.

\textbf{Structure based Trackers.} The algorithm to track non-rigid object has attracted great attention in recent years. Regular trackers can nearly handle the extreme deformations, therefore, some researchers begin to study this task and attempt to exploit part information and achieve promising performance. Son \emph{et al.} \cite{son2015tracking} utilize the online gradient boosting decision tree operation on individual patches to achieve robust visual tracking. Yeo \emph{et al.} in \cite{yeo2017superpixel} attempt to use Markov Chain on superpixel graph, however, the information propagation through a graph could be slow based on the structure. Ting and Yang \emph{et al.} propose the patch-based trackers based on correlation filter and combine the patches within a particle filter framework in \cite{li2015reliable} and \cite{liu2015real}, respectively. The major issue existed in these trackers is that they are all separately learn the correlation filter for each part and record the relative positions between each part and target center. Besides, these part-based trackers divide the target object into fixed number of fragments in a violent way. Hence, their model contains few discriminative local structure information due to such rough patch dividing, and little semantic information maintained in the feature of such patches. It is also very hard to design a reasonable updating strategy for these trackers and will be rather sensitive to model drift when drastic deformation occurred. Zhang \emph{et al.} \cite{Zhang_2018_ECCV} propose a structure constrained part-based model for visual tracking using DNNs and does not explicitly divide the target into parts. Their tracker can suppress the influence of aforementioned issues to some extent, however, they may still not be able to handle the drastic deformation or heavy occlusion well due to the lack of considering global information. Our model takes the target object and its language description as condition and estimate target-driven attention maps for global proposal generation which can handle this issue well.

\textbf{Multi-domain based Trackers.}
The idea of use multi-domain layers for the training of CNN is first proposed by Nam \emph{et al.} in \cite{Nam2015Learning}. They pretrain a CNN using a large set of videos with tracking groundtruths to obtain a generic target representation. Their network is composed of shared layers and multiple branches of domain-specific layers, where domains correspond to individual training sequences and each branch is responsible for binary classification to identify target in each domain. Their final tracking performance is indeed great and many trackers are developed based on this idea, such as BranchOut \cite{han2017branchout}, Meta-tracker \cite{Park_2018_ECCV}, Real-time MDNet \cite{Jung_2018_ECCV}. Although these trackers are all attempt to improve MDNet from different views, however, none of them consider the structure information when pretrain their models. In addition, these trackers still adopt the local search strategy which may make them sensitive to challenging factors as mentioned above. Our tracker utilizes the GCN and natural language to take the structure information into consideration and also joint use the global and local proposals for classification which make the baseline tracker more robust to challenging factors.

\textbf{Visual Attention based Trackers.}
To handle the influence of video noises and/or tracker noises in the extremely challenging conditions, there are several attempts to combine attention maps with visual tracking. Choi \emph{et al.} \cite{Choi2016Visual} presented an attention-modulated visual tracking algorithm that decomposes an object into multiple cognitive units and trains multiple elementary trackers to modulate the distribution of attention based on various features and kernel types. Han \emph{et al.} \cite{Hong2015Online} proposed an online visual tracking algorithm by learning discriminative saliency map using CNN. They also directly searched the target object from attention locations. The spatial weights, which are widely used by DCF trackers to suppress the boundary effect, can also be interpreted as one type of visual attention. For example, the cosine window map \cite{bolme2010visual} and the Gaussian window map \cite{Danelljan2016Beyond} \cite{danelljan2015learning}. Recently, a number of efforts \cite{choi2017attentional} \cite{chu2017online} \cite{Yang_2018_ECCV} have been made to exploit visual attention within deep models. These approaches emphasize attentive features and resort to additional attention modules to generate feature weights. However, the feature weights learned in single frames are unlikely to enable classifiers to concentrate on robust features over a long temporal span. Moreover, slight inaccuracy of feature weights will exacerbate the misclassification problem. This requires an in-depth investigation on how to best exploit the visual attention of deep classifiers so that they can attend to target objects over time. Similar views can also be found in \cite{pu2018deep}. Instead, our proposed target-driven attention network takes video frames, initial target object and natural language as inputs. The generated attention maps are video-specific and can provide high-quality global proposals for visual tracking.

\textbf{Tracking by Natural Language.}
Integrating natural language into the computer vision community has becoming a new trend and many new tasks has been proposed, such as image caption, visual question answer, segmentation with natural language. The bridge used to connect the natural language and computer vision is the embedding technique which has achieved great progress in recent years, such as word2vector \cite{mikolov2013efficient}, GloVe \cite{Pennington2014Glove}. Usually, they utilize the memory network (RNN, LSTM, GRU or SRU) or CNNs to further learning the feature representations based on embedded vectors. They also integrate attention mechanism into their deep models to further improve the final performance. Improving tracking performance with natural language has been studied in \cite{Li2017Tracking}, they propose three kinds of models to fully illusturate possible combinations of visual tracking and natural language specifications. Different from their work, we embedding the natural language with CNN and use the embedding features to guide the global target-driven attention map generation. In addition, we also utilize the language embedding as high-level semantic information for shared feature learning.

\section{The Proposed Method}
The motivation of our method lies in two main aspects: i). How to learn a more robust deep feature representation by considering the correlations between extracted proposals? ii). How to obtain high-quality global proposals for visual tracking? In this paper, we propose an unified deep visual tracking algorithm guided by natural language specification, as shown in Figure \ref{pipelineAll}. We will give a detailed introduction to our tracker in following sections, including network architecture, loss functions, online tracking procedure and implementation details.

\subsection{Network Architecture.}
Our tracker contains two sub-networks, \emph{i.e.} structure-aware local search sub-network (SALNet) and global proposal generation sub-network (GPGNet).

\subsubsection{SALNet}
The SALNet is actually a binary classification based visual tracker which follows the regular tracking-by-detection framework. Following MDNet, we use a deep convolutional network architecture as shown in Figure \ref{pipelineAll}. It takes a $107 \times 107$ RGB image patch as input, and contain five hidden layers including three convolutional layers and two fully connected layers. The convolutional layers are identical to the corresponding parts of VGG-M network \cite{chatfield2014return} \footnote{{https://github.com/HyeonseobNam/py-MDNet}} except that the feature map sizes are adjusted by our input size. The next two fully connected layers contain 4608 and 512 output units and are combined with ReLUs and dropouts. We adopt the feature from the second fc layer which is 512-D to denote corresponding image patch.

The major difference between our SALNet with existing binary classification based trackers is that we take the correlations between training samples into consideration. Specifically, we formulate the deep feature learning problem for visual tracking as a \emph{node-focused} graph application. Given the features of extracted training samples, we can construct an undirected complete graph $G(V, E)$, where $V = \{v_1, v_2, ... , v_N\}$ denotes the set of nodes. Each node represents a feature vector of extracted image patch. We also establish edges $E$ on the graph $G$ to represent the set of relationships between different nodes. In this graph, we connect pairs of semantically related nodes together. More specifically, we will assign the weight based on the Euclidean distance between each paired proposal. We use $W_{ij}$ to denote the relation importance between node $i$ and node $j$, which can be represented as  following:
\begin{equation}
\label{affinityFunction}
W_{ij}  =
\left\{
\begin{aligned}
\ &	 \frac{exp(S(g_i, g_j))}{\sum_{j} exp(S(g_i, g_j))},    ~~~ if ~~~ i \neq j \\
 &	0,						~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ else \\
\end{aligned}
\right.
\end{equation}
where $g_i$ and $g_j$ are the $i$-th and $j$-th node. $S()$ is a pairwise similarity estimation function, that estimates the similarity score between $g_i$ and $g_j$.

After the affinity matrix is computed according to Eq. \ref{affinityFunction}, we perform normalization on each row of the matrix so that the sum of all the edge values connected to one proposal $i$ will be 1. Following \cite{vaswani2017attention}, we adopt the softmax function for the normalization:
\begin{equation}
\label{softmaxFunction}
G_{ij} = \frac{exp(W_{ij})}{\sum_{j=1}^{N}exp(W_{ij})}
\end{equation}
The normalized $G$ is taken as the adjacency matrix representing the similarity graph.

Different from standard convolution that operate on local region in an image, the convolutional operations on graphs is then defined by computing the response at a node based on the neighboring nodes defined by the adjacency graph. Mathematically, the convolutional operations for each layer in the network is represented as:
\begin{equation}
\label{graphConvolution}
Z = \hat{A} X' W
\end{equation}
where $\hat{A}$ is a normalized version of the binary adjacency matrix $A$ of the graph, with $n \times n$ dimensions. $X'$ is the input $n \times k$ feature matrix from previous layer. $W$ is the weight matrix of the layer with dimension $k \times c$, where $c$ is the output channel number. Therefore, the input to a convolutional layer is $n \times k$, and the output is a $n \times c$ matrix $Z$. The convolution operations can  be stacked one after another. A non-linear operation (ReLU) can be applied after each convolutional layer. For the final convolutional layer, the number of output channels is the number of label classes ($c = C$) in the supervised learning. In this paper, we only want to obtain its output feature, therefore, we do not integrate this layer into our network. More detailed introductions can be found in \cite{2016Semigcn} \cite{battaglia2018relational}.

After we obtain the enhanced feature via GCN, we concatenate it with original input as the final feature representation of each proposal. Following MDNet, we also introduce the domain-specific layers to model the correlations between different video sequences in the training dataset. We prefer readers to check the MDNet to have a deeper understand of this algorithm.

In the shared feature learning phase (\emph{i.e.} the SALNet), the loss function used for binary classification (\emph{i.e.} BCE loss) can be formulated as:
\begin{equation}
\label{crossEntropyLoss}
L_c = - \sum_{i=1}^{T} y_i log p_i  + (1-y_i) log (1-p_i)
\end{equation}
where $T$ is the mini-batch size, $y_i$ the ground truth label of the $i$-th sample, $p_i$ is the prediction of corresponding sample from deep neural network.

In addition to BCE, the triplet loss function is also adopted to ensure that all positive samples $\textbf{V}^p$ (\emph{positive}) are closer to the high-level semantic vectors $\textbf{V}$ (\emph{anchor}) and all negative samples $\textbf{V}^n$ (negative) are at a distance from the anchor vector, as illustrated in Figure \ref{differencewithMDNet} (b). Formally, we have:
\begin{equation}
\label{tripletLossfunction}
||V - V^p||_2^2 + \alpha \leq ||V - V^n||_2^2, ~~ \forall (V, V^p, V^n) \in \mathcal{T}
\end{equation}
where $\alpha$ is a margin that is enforced between positive and negative pairs, we set it as 1.0 in our implementation. $\mathcal{T}$ is the set of all possible triplets in the training set and the mini-batch can be setted as N. Hence, the loss function for the mini-batch can be formulated as:
\begin{equation}
\label{tripletLossfunction}
L_t = \sum_{i=1}^{T} [ ||V - V^p||_2^2 -  ||V - V^n||_2^2 + \alpha ]_+
\end{equation}

Therefore, the final loss function for the optimization of the SALNet can be formulated as:
\begin{equation}
\label{totalLossfunction}
Loss = L_c + \lambda * L_t
\end{equation}
where $\lambda$ is a tradeoff parameter, we experimentally set it as 0.1 in our experiments.

\subsubsection{GPGNet}
Although the proposed SALNet already achieve good performance on some video sequences, however, it still cannot get rid of the issues caused by local search strategy under the tracking-by-detection framework. In this paper, we propose the global proposal generation network (GPGNet) to complement with local proposals for robust visual tracking.

\begin{figure}[t]
\center
\includegraphics[width=3.3in]{CNN-for-language}
\caption{The illustration of convolutional network for natural language embedding. }
\label{cnnLanEmbedding}
\end{figure}

As shown in Figure \ref{pipelineAll}, the inputs of this module are target object patch, video frame and natural language specification. For all the input data, we only use convolutional networks to obtain its features due to the efficiency of CNN. Specifically, for each video frame and the target object patch, we resize them into $192 \times 256 \times 3$ and obtain their feature map whose dimension is $12 \times 16 \times 512$ via VGG-Net. For the natural language, we first embedding each word into a 512-D feature vector. Different from regular operation which use RNN model to embedding the language \cite{Li2017Tracking} \cite{Margffoy_Tuay_2018_ECCV} \cite{Chen_2018_ECCV}, we adopt CNN to encode them with more efficient parallel convolution which has widely used in many tasks \cite{gehring2017convolutional} \cite{Aneja_2018_CVPR}. The detailed configuration of the convolutional network can be found in Figure \ref{cnnLanEmbedding}. The visual features of video frame and target object are concatenated along the channel, hence, we obtained a feature map whose dimension is $12 \times 16 \times 1024$. The maximum length of given sentence is 16 in this paper, therefore, we can obtain the sentence embedding  $16 \times 512$. Then, we expand this embedding into $12 \times 16 \times 512$ and obtain a feature map $12 \times 16 \times 1536$ after concatenate with visual features. The features we obtained in the encoding phase are concatenated together and input into the upsample network (which is a reversed VGG-Net).

Following \cite{Margffoy_Tuay_2018_ECCV}, we adopt the binary cross-entropy loss for the optimization of GPGNet.

\subsection{Online Tracking}
When tracking the target object in a new sequence with the guide of target-driven attention maps, the shared layers in pre-trained CNN and a new binary classification layer are combined together to construct a new network. And also the GCN module  is only used for shared feature learning in the training phrase to achieve more efficient tracking. Online tracking is performed by evaluating the candidate windows randomly sampled around the previous target state and proposals extracted from attention regions. In this paper, to estimate the target state in each frame, $N$ target candidates $\textbf{x}^1, \textbf{x}^2, ... , \textbf{x}^N$  sampled around the previous target state and current attention regions are evaluated using the network. We obtain their positive scores $F^+(\textbf{x}^i)$ and negative scores $F^-(\textbf{x}^i)$ from the network. During the sampling phase, our target-driven attention maps could provide proposals with more accurate location and scale information, which could make the searching process more efficient and effective. Hence, the optimal target state $\textbf{x}^*$ is given by finding the example with the maximum positive score as:
\begin{equation}
\label{MDNETMaximum}
\textbf{x}^* = \arg \max_{\textbf{x}^i} F^+(\textbf{x}^i)
\end{equation}

We adopt the same strategy with MDNet, \emph{i.e.}, long-term and short-term updates, to update our model. Long-term updates are performed in regular intervals using the positive samples collected for a long period while short-term updates are conducted whenever potential tracking failures are detected (when the positive score of the estimated target is less than 0.5) using the positive samples in a short-term period.

\subsection{Implementation Details}
The global proposals generated from attention maps can be concluded as the following three steps: 1) Obtain attention regions and center location of each region, given the attention map; 2) Obtain BBox, which attempts to cover each attention region; 3) Employ Gaussian sampling strategy on these bounding boxes to generate proposals.

The GPGNet is used to generate the target-driven attention maps for global proposal extractation. We use binary mask for the training of this network which can be obtained directly from BBox annotations. As shown in Figure \ref{GPGtrainSamples}, we first generate a black mask which has the same resolution as the video frame, then, we white the target object regions according to annotated BBox in the training dataset. The binary mask is used as the ground truth attention maps to optimize the GPGNet. Following the regular semantic segmentation,  we adopt the binary cross-entropy loss to measure the difference between the generated attention maps and the ground truth.
\begin{figure}[htb]
\center
\includegraphics[width=3.3in]{GPGtrainSamples}
\caption{The pipeline of pre-processing training samples for GPGNet.}
\label{GPGtrainSamples}
\end{figure}

The training details of SALNet: initial learning rate is 0.0001; batch size is set as 8, and Adam is utilized for optimization. For the GPGNet, the initial learning rate is 5e-5, batch size is 20, Adagrad is used for the optimization. Three convolutional layers are used to encode the natural language and the maximum sentence length is 16. We train this network for 50 epochs. All the experiments are implemented based on PyTorch on a desktop computer with Ubuntu 16.04, I7-6700k, NVIDIA TITAN Xp with 12G VRAM and 32G RAM.

\section{Experiments}

We will first introduce the dataset and evaluation criteria used in this paper. After that, we will compare our tracking results with other state-of-the-art visual trackers on several public benchmarks. Then, we conduct ablation studies to validate the effectiveness of each component. Finally, we will discuss the difference with existing trackers.

\subsection{Datasets and Evaluation Criterion}
The training datasets used in this paper for SALNet and GPGNet are \textbf{TLP50} \cite{moudgil2017long}, \textbf{DTB70} \cite{li2017visualDLP70} and \textbf{LaSOT} \cite{fan2018lasot} \footnote{{https://cis.temple.edu/lasot/}} dataset which totally contain 120 (50 + 70) and 1400 video sequences, respectively \footnote{The baseline method pyMDNet used in this paper is implemented based on PyTorch and pre-trained on two long-term dataset \textbf{TLP} \cite{moudgil2017long} and \textbf{DTB70} dataset \cite{li2017visualDLP70} for all our experiments.}.  The LaSOT provide both the BBox and natural language annotations of target object, which is suitable for our natural language guided tracking task. Specifically, we generate binary mask for each video frame by setting the target object pixels as zero and background pixels as 255. We use those masks as goundtruth attention maps to optimize the GPGNet. It is also worthy to note that, we only select 44660 images from the LaSOT dataset (it totally contains 3.52 million frames) for the training of GPGNet to quickly validate our proposed method.  The testing is conducted on five benchmark datasets, including \textbf{OTB-2013} \cite{WuLimYang13}, \textbf{OTB-100} \cite{wu2015object}, \textbf{VOT-2014} \cite{Kristan2014a},  \textbf{VOT-2016} \cite{VOT_TPAMI} and \textbf{TC128} \cite{Liang2015Encoding} dataset. The natural language specification of OTB100 is borrowed from lang-tracker \footnote{{https://github.com/QUVA-Lab/lang-tracker}}, and other datasets used for testing is annotated by one person to maintain its consistency.

Two widely used evaluation protocols are utilized in this paper: \textbf{{success rate}} and \textbf{{precision rate}}. These two criteria are all aiming at measure the percentage of successfully tracked frames. For the success rate, a frame is declared to be successfully tracked if the estimated bounding box and the ground truth box have an interaction-over-union overlap larger than a certain threshold. For precision rate, tracking on a frame is considered successful if the distance between the center of the predicted box and the ground truth box is under some threshold.

\begin{figure*}[t]
\center
\includegraphics[width=7in]{attentionShown}
\caption{The attention maps generated by our GPGNet.}
\label{attentionShown}
\end{figure*}

\begin{figure*}[t]
\center
\includegraphics[width=7in]{attentionShown-v-t-joint}
\caption{The difference between target object only, natural language only and joint based global attention estimation.}
\label{attentionShown-v-t-joint}
\end{figure*}

\begin{table*}[htp!]
\center
\scriptsize
\caption{The tracking results on OTB-2013 and OTB-100 Benchmark (The top three results are highlighted in \textbf{{\color{red} red}}, \textbf{{\color{green} green}} and \textbf{{\color{blue} blue}}, respectively).} \label{OTBbenchmarkresults}
\begin{tabular}{l|c|c|c|c|c|c|c|c|c}
\hline
\hline
\textbf{Algorithm}				&\textbf{SINT++}      &\textbf{StructSiam} 		&\textbf{CREST}   		&\textbf{CCOT} 		  &\textbf{RFL  } 			&\textbf{RASNet}	 	 &\textbf{SRDCFD}	 	&\textbf{CSR-DCF} &\textbf{ AFCN}  \\
\hline
\textbf{OTB-2013}  &0.839/0.624	&0.880/0.638 &\textbf{{\color{green} 0.908}}/\textbf{{\color{green} 0.673}}		&0.899/ \textbf{{\color{blue} 0.672}}   &0.786/0.583    &0.892/0.670  &0.870/0.653  	&-/- 			  & 0.860/0.607	 \\
\hline
\textbf{OTB-100} 	&0.768/0.574 &0.851/0.621 &0.838/0.623 	&\textbf{{\color{red} 0.898}}/\textbf{{\color{red} 0.671}}  &0.778/0.581    &-/0.641 			&0.825/0.627  		&0.733/0.587  	  &0.799/0.573  	\\
\hline
\hline
\textbf{Algorithm}				&\textbf{ADNet} 		&\textbf{Meta-Tracker}		&\textbf{MemTrack}  &\textbf{Staple}  &\textbf{CFNet} &\textbf{Lang-Tracker}&\textbf{SiamFC}&\textbf{pyMDNet}&\textbf{Our}\\
\hline
\textbf{OTB-2013}	&\textbf{{\color{blue} 0.903}}/0.659	 	&-/-			&0.849/0.642 		&0.793/0.600	 	&0.785/0.589			&-/0.578   		&0.809/0.607	 	&0.880/0.655			&\textbf{{\color{red} 0.925}}/ \textbf{{\color{red} 0.676}}      \\
\hline
\textbf{OTB-100}	&\textbf{{\color{blue} 0.880}}/\textbf{{\color{green} 0.646}}	 	&0.856/0.637	 &0.820/0.626  		&0.784/0.581	 	&0.777/0.586			&-/-   		&0.771/0.582	 	&0.866/\textbf{{\color{blue} 0.643}}			&\textbf{{\color{green} 0.889}}/\textbf{{\color{green} 0.646}}         \\
\hline
\end{tabular}
\end{table*}

\begin{figure*}[t]
\center
\includegraphics[width=6.5in]{results_on_VOT_benchmarks}
\caption{The tracking results on VOT-2014 (left two sub-figures) and VOT-2016 dataset (right two sub-figures). }
\label{resultsVOT}
\end{figure*}

\begin{figure}[t]
\center
\includegraphics[width=3.3in]{tc128_results}
\caption{The tracking results on TC128 dataset. }
\label{tcresults}
\end{figure}

\subsection{Comparison with State-of-the-art Trackers}
To fully demonstrate the effectiveness of our proposed algorithm, we compare with many recent and popular trackers, including: \textbf{MDNet} \cite{Nam2015Learning}, \textbf{CCOT} \cite{Danelljan2016Beyond}, \textbf{ECO} \cite{Danelljan2017ECO}, \textbf{RASNet} \cite{Wang_2018_CVPR}, \textbf{SINT} \cite{Tao2016Siamese}, \textbf{SINT++} \cite{Wang_2018_CVPR}, \textbf{CSR-DCF} \cite{Lukezic2016Discriminative}, \textbf{ADNet} \cite{Yun2017Action}, \textbf{Meta-Tracker} \cite{Park_2018_ECCV}, \textbf{MemTrack} \cite{Yang_2018_ECCV}, \textbf{Staple} \cite{bertinetto2016staple}, \textbf{CFNet} \cite{valmadre2017end}, \textbf{Lang-Tracker}  \cite{Li2017Tracking}, \textbf{SiamFC} \cite{bertinetto2016fully}, \textbf{ReGLe} \cite{li2017regle}, \textbf{StructSiam} \cite{Zhang_2018_ECCV} and \textbf{AFCN} \cite{choi2017attentional}.

As shown in Table \ref{OTBbenchmarkresults}, it is obvious to find that our proposed visual tracker achieve good and even better performance than some recent trackers on OTB-2013 and OTB-100 benchmark datasets. Compared with the baseline method pyMDNet, our method improves significantly on both OTB-2013 and OTB-100 dataset. Specifically, our algorithm improves the tracking accuracy (precision plot/success plot) from 0.880/0.655 to 0.925/0.676 on OTB-2013 dataset; from 0.866/0.643 to 0.889/0.646 on OTB-2015 dataset, respectively. Our method also achieves good tracking results on the public benchmarks compared with other visual trackers. Our tracker does not perform as well as the top performing tracker CCOT on OTB100 dataset. It is because: i).  CCOT crops the sample in a continuous space for scale estimation, while our tracker only randomly draws a sparse set of samples. ii). CCOT also use multiple features (e.g., color names, HOG and deep features), while we only use deep features. We will consider to explore these ideas as our future works.

We also show the tracking results on VOT-2016 which are evaluated with its own default metrics, as shown in Table \ref{VOTOriResults}. We can find that our tracker can achieve comparable or even better performance when compared with other trackers. The illustration about the tracking results and target-driven attention maps can be found from Figure \ref{attentionShown}, \ref{attentionShown-v-t-joint} and \ref{trackingResultsFigure}.

\begin{table*}[htp!]
\small
\center
\caption{ Comparison with other trackers on VOT-2016 dataset with default metrics.} \label{VOTOriResults}
\begin{tabular}{c|ccccccccc}
\hline
\hline
{Algorithm}	 &{CCOT }   &{EBT }		 &{Staple }		&{SRDCF }	&{HCF } &{SiamRN }	&{DSST}   	 &{MDNet}  &{Ours}\\
\hline
{EAO}  &0.3310   &0.2913     &0.2952   &0.2471   &0.2203   &0.2766   &0.1814     &0.2572   &0.3045   \\
\hline
{FPS}  &82.18   &2.87   &14.43  &503.18   &328.73      &7.05   &13.90    &2.66   &2.27   \\
\hline
\end{tabular}
\end{table*}

\begin{table}[htp!]
\center
\scriptsize
\caption{ Tracking performance without or with global proposals on OTB100 dataset. The tracking results on precision plot and success plot are listed as follows.} \label{GPResults}
\begin{tabular}{l|c|c|c|c}
\hline
\hline
\textbf{Algorithm}	 &\textbf{Our-SALNet}   &\textbf{Our-TO}	 &\textbf{Our-NL}	 &\textbf{Our-JTNL}\\
\hline
\textbf{OTB100}  &0.876/0.644  &0.886/0.647  &0.884/0.643  &0.889/0.646\\
\hline
\end{tabular}
\end{table}

\subsection{Ablation Studies}

\textbf{The Effect of GCN.}
To demonstrate the effectiveness of structured information from other proposals, we conduct experiment on this component (\emph{i.e.} pyMDNet+GCN) on OTB-2013 dataset. As shown in Table  \ref{CAResults}, pyMDNet+GCN improved the tracking result from 0.880/0.655 to 0.905/0.671 on precision and success plot, respectively, compared with baseline method pyMDNet. This result fully validated the effectiveness of the structured information from other nodes, that is to say, the GCN can help to learn more discriminative deep features for visual tracking.

\textbf{The Effect of Triplet Loss.}
To validate the effectiveness of natural language guided feature learning, we test the model which only with triplet module, \emph{i.e.} pyMDNet+Language, as we can see from Table  \ref{CAResults}, the prior knowledge also improved the feature learning. This experiment fully demonstrates the effectiveness of the introduced natural language specification to guide the shared feature learning.

\begin{table}[htp!]
\center
\scriptsize
\caption{ Component Analysis on OTB-2013 dataset. The tracking results on precision plot and success plot are listed as follows.} \label{CAResults}
\begin{tabular}{l|c|c|c}
\hline
\hline
{Algorithm}	 &\textbf{pyMDNet}   &\textbf{+ GCN}	 &\textbf{+ Language}	 \\
\hline
{OTB-2013}  &0.880/0.655  &0.905/0.671  &0.913/0.668  \\
\hline
\end{tabular}
\end{table}

\textbf{The Effect of Global Search Strategy.}
As shown in Table \ref{GPResults},  we conduct object tracking without global proposals (Our-SALNet), and also joint use local and global search strategy for robust visual tracking. Specifically, we estimate the attention maps with following three versions: target object patch based (Our-TO), natural language based (Our-NL) and joint target and language (Our-JTNL) based. It is easy to find that the utilization of global search strategy can significantly improve the tracking results compared with baseline method Our-SALNet. We also visualize some of these global attention maps in Figure \ref{attentionShown}.

\textbf{The Generic of Target-driven Attention Maps.}
We show our target-driven attention maps can also be integrated with other trackers, such as CSRDCF \cite{Lukezic_IJCV2018}. We take the attention maps generated by our GPGNet as a kind of feature representation, and integrated with CSRDCF for robust visual tracking. For example, CSR-DCF uses [gray, color name and hog feature] as original features. After integrated with our attention maps, its feature tuple becomes [gray, color name, hog, attention map].  As shown in Figure \ref{resultsVOT} (a), the tracking results of CSRDCF can be improved with our attention maps on VOT dataset.

\textbf{Influence of Tradeoff Parameter $\lambda$.}
As shown in Eq. \ref{totalLossfunction}, our loss function contains a hyperparameter $\lambda$ which is introduced to tradeoff the classification loss and triplet loss. In this section, we conduct some experiments on this parameter (we set the $\lambda$ equal to 0, 0.1, 0.2, 0.3, 0.5, 0.8 and 1) to show its influence on the final tracking results. The curve to shown variation of tracking performance can be found in Figure \ref{resultsAblationStudyNodeParameter}.  We can find that our proposed deep model is not sensitive to the hyperparameter $\lambda$.

\begin{figure}[t]
\center
\includegraphics[width=3.3in]{accuracy_nodeNum_params}
\caption{The analysis of tradeoff parameter (left sub-figure) $\lambda$ and node numbers (right sub-figure). The {{\color{red} red}} line denotes the variation of precision plots, and the {{\color{blue} blue}} line denotes the success plots. }
\label{resultsAblationStudyNodeParameter}
\end{figure}

\textbf{Influence of Node Numbers for GCN.}
To test the influence of different numbers of training samples, we extract different amount of samples (\emph{i.e.} 0,  20,   28,   32,   43,   50, 70 ) and conduct experiment to check the final result. As shown in Figure \ref{resultsAblationStudyNodeParameter}, the tracking results can be enhanced significantly when integrating GCN, since the result of other proposals are all better than zero's (i.e. the baseline method pyMDNet). We can also find that the results are better than others when the node number belong to the range of (30, 50).

\textbf{Influence on Different Layers of GCN.}
To check the influence of different graph convolutional layers, we conduct ablation studies on this question. We set the number of GCN layers as 2, 3, 5 and 8 layers to pretrain the model and test on the OTB2013 dataset. As shown in Table \ref{differGCNResults}, the tracking results can be enhanced when increasing the number of GCN layers. However, it also increased the training time when more layers are added. Hence, we choose 3 GCN layers to achieve better tradeoff between accuracy and training time in our experiments.

\begin{table}[htp!]
\center
\small
\caption{ Tracking results with different layers of GCN on OTB2013 dataset.} \label{differGCNResults}
\begin{tabular}{l|ccccccc}
\hline
\hline
{Layers}	 &{2}	 &{3}	 &{5} &{8}\\
\hline
{SR}  &0.654  &0.663	&0.671 &0.670	\\
\hline
\end{tabular}
\end{table}

\textbf{Tracking results on similar appearance videos.}
To validate the performance on videos with similar target objects, we also test our tracker on 46 video sequences \footnote{The selected video list: {Basketball, Bird1, Girl2, BlurCar1, BlurCar2, BlurCar4, Bolt, Bolt2, Walking, Walking2, BlurCar3, Freeman3, Car1, Car2, Car24, Car4, CarDark, Couple, Coupon, Crossing, Crowds, Deer, Football, Football1, Human3, Human4, Human5, Human6, Human7, Human8, Human9, Ironman, Jogging-1, Jogging-2, Jumping, KiteSurf, Liquor, Shaking, Singer1, Singer2, Skating1, Skating2-1, Skating2-2, Soccer, Subway, Suv.}} selected from OTB100 dataset. These videos contain at least one or more similar objects with target object. We want to validate the robustness of our target-driven attention maps via this experiments. As shown in Figure \ref{similarAppearanceResults}, our tracker can still achieve good performance on these challenging videos. Specifically, we can achieve 91.8/65.2 on this sub-dataset evaluated with PR and SR evaluation criterion. It is easy to find that our results are better than baseline method pyMDNet (86.5/64.2) and some other recent visual trackers, such as SINT++ \cite{Wang_2018_CVPR}, ReGLe \cite{li2017regle}.

\begin{figure}[t]
\center
\includegraphics[width=3.3in]{results_similar_Appearance_videos}
\caption{The tracking results on 46 videos selected from OTB100 dataset (these videos all contain similar appearance objects with the target object).}
\label{similarAppearanceResults}
\end{figure}

\begin{figure*}[t]
\center
\includegraphics[width=7in]{trackingResultsFigure}
\caption{The tracking results of our method and other trackers.}
\label{trackingResultsFigure}
\end{figure*}

\subsection{Discussion}

\textbf{Difference Between Regular Saliency Estimation and Our Attention Maps.} Saliency maps usually focus on the target we humans attend, however, it maybe not the target we want to track in practical videos. Therefore, it can not be directly utilized in practical tracking algorithms. Meanwhile, our attention maps are generated based on initial target object and natural language specifications. It only focuses on the target object we want to track in each video, in another word, our attention maps are \emph{video-specific}.

\textbf{Difference with Existing Trackers.}
	The most relevant works with ours are Lang-Tracker \cite{Li2017Tracking} and MDNet. \textbf{For the Lang-Tracker}: lang-tracker use language to detect target object in the first frame and tracking target object according to image patch and language descriptions for subsequent frames; we use the natural languge for shared feature learning and global attention estimation, which also improve the final tracking results significantly. \textbf{For the MDNet}: i). MDNet did not consider the structure information between training samples or language; we model this information with GCN and triplet loss function when design our network. ii). MDNet only adopt the local search strategy by following tracking-by-detection framework which make their tracker rather sensitive to challenging factors; Our tracker jointly use local and global search strategy for robust visual tracking. Extensive experiments on five tracking benchmarks validated the effectiveness of our proposed algorithm.

\section{Conclusion}
In this paper, we propose a novel visual tracker, named DAT, to track the target object based on the provided BBox and its natural language specification. Our tracker can be devided into two main subnetworks: SALNet and GPGNet. The SALNet is a novel structure-aware deep neural network by take both the correlations between video sequences and training samples in each video into consideration. We adopt the softmax and triplet loss functions to train this sub-network. We also propose the GPGNet, which is a novel target-driven global attention estimation network to ensure the locations we should focus on. These proposals extracted from the attention regions are feed into binary classifier together with proposals extracted from local search window. The proposal with maximum response score will be chosen as the tracking result of current frame. Extensive experiments on several public tracking benchmarks validated the effectiveness of our proposed method.

{
\bibliographystyle{ieee}


\section{Introduction}
Dialog based interaction between a customer and a bot may become tedious and irrelevant if the system’s beliefs are not consistent with the set of beliefs of the customer. Beliefs are cognitive representational states that represent the presumed context of the conversation perceived by each agent. A key limitation in today's conversational interfaces is their lack of robustness when understanding the latent beliefs. The inherent difficulties of conversational systems (chatbots) are further increased by the conditions under which these systems typically operate: increasingly larger vocabularies, large and diverse user populations, spontaneous input, etc. Unless mediated by better belief identification and robust reasoning mechanisms, these errors propagate to subsequent stages of processing in a dialog system and exert a considerable negative impact on the quality and ultimately the success of the interaction.

Identifying latent beliefs is a challenging task since it depends on various factors like identifying and analyzing context. Other challenges that exist in identifying latent beliefs is the reference to multiple concepts and the need to extract a large amount of facts, commonsense knowledge, anaphora resolution, and logical reasoning. Consider the example, \textit{``I am looking for a heavy course"}, it is difficult to identify the latent belief if the student is looking for a course which is heavy in terms of the workload; class size and/or the nature/quality of assignments.

We propose a novel approach for identifying more accurate beliefs over concept values in conversational systems by integrating information across multiple turns in the conversation. Traditional machine learning approaches train a system with extremely large dialog corpus that covers a variety of scenarios. Another approach is to build a system with a complex set of hand-crafted rules that may address some specific instances. Both approaches may be impractical in many real-world domains. Our framework is based on a combination of machine-learning mechanism and logical reasoning to understand the latent beliefs. Our model then evaluates the beliefs to tailor the dialog and make it consistent with the set of beliefs of the user. This process then helps drive the conversation in a meaningful way.

\section{Related Work}

Deep learning based dialog systems~\cite{miller2016key} use memory networks to learn the underlying dialog structure and carry out goal-oriented dialog.
However, they do not factor in beliefs or trigger epistemic rules in modifying the conversation given the evolving context.
In~\cite{williams2016dialog} Williams et.al, describe the dialog state tracking challenge and mention ``how the task of correctly inferring the state of the conversation - such as the user's goal - given all of the dialog history up to that turn'' is important. It is in this overall context, we propose that it is important to evaluate the probable beliefs held by the human and tailor the dialog system suitably to be consistent with the beliefs in order to hold a relevant conversation.

Although a number of attempts have been made to build dialog systems~\cite{henderson2014word}, ~\cite{Weston16}, ~\cite{williams2016dialog}, the use of epistemic rules in driving the dialog in a consistent way with the beliefs has not yet been tackled. Various approaches to dialog management have been proposed and these can be broadly classified into finite-state methods, probabilistic methods and deep learned methods.

There are recent motivating examples of works that make use of machine-learning to build intelligent dialog systems.
Traditional dialog systems are specialized for a domain and rely on slot-filling driven by a knowledge base and a finite-state model~\cite{lemon2006hierarchical}. The finite-state model represents the dialog structure in the form of a state transition network in which the nodes represent the system's interactions and the transitions between the nodes determine all the possible paths through the network.

Uckelman~\cite{sara2010obligationes} describes how in a formal dialog system, dynamic epistemic logic can be used in an \textit{Obligatio}, where two agents, an \textit{Opponent} and a \textit{Respondent}, engage in an alternating-move dialog to establish the consistency of a proposition.
Sadek et al.~\cite{Sadek:1997:AND:1622270.1622305} proposes a reasoning engine to build effective and generic communicating  agents.
Motivated by the above works, we propose to identify the beliefs, use these beliefs to trigger epistemic rules, and use the assertions of the rules to drive the conversation by tailoring the states in a finite-state machine dialog system.

Opinion mining methods have been in use for over long time.  Recently, these methods have been applied to dialog systems. Roy et al.~\cite{aaai_Roy_16} propose a novel approach to consider customer satisfaction to tailor the dialog. While general sentiment analysis methods are useful to understand a customer's mental situation, they may need to be complemented with more domain specific information leading to richer fine grained classes of sentiments.
For this reason, it is necessary to develop methods which take into account domain specific sentiments information.

\section{Supervised Approach for Automatically Learning Latent Beliefs}

A key issue in dialogue management is the design of the dialogue policy incorporating latent beliefs. While it is possible to design this by hand, such an approach has several shortcomings. Development is manually intensive and expensive, the systems are difficult to maintain and performance is often sub-optimal. In our previous work, we highlighted some of the issues in hand crafting belief rules~\cite{DBLP:conf/aaai/SangroyaASR18}.

An alternative to hand-crafting belief rules is to automatically learn them given a large annotated corpus of utterances and corresponding labeled beliefs. However, it is challenging to design a machine learning model as the performance of the model would be degraded if it is based on simple linguistic features such as \textit{bag-of-words} (See Figure~\ref{word_cloud}). Sometimes, the available training data consist of large number of closely related classes that makes the problem of belief identification more difficult.

\begin{figure}
\centering
      \includegraphics[scale=0.2]{images/word_cloud.png}
    \caption{Word Cloud of Dialog Utterances of a \textit{Curious} Student}
    \label{word_cloud}
\end{figure}

It is challenging task to build an automatic system that can understand the latent beliefs of humans (more specifically students). For example, there may be a student who is confused and directionless, might come up with something like \textit{``I have no inkling of where I want my life to go and am unable to determine what classes to take. I'm interested in machine learning. Can you help me decide what to do?”} . There may be another student who has done his homework on what he wants but needs only little direction from the advisor. These two different categories of students needs different conversational flow and a different set of dialog policy needs to be tailored for each case.

We take the initial input from the student to advisory bot and categorize it into one of the tree categories based on there emotional belief. We consider 3 categories ``\textbf{curious}",  ``\textbf{neutral}", ``\textbf{confused}" and manually annotate them to student's utterances for each dialog. Most of the conversations seem to be similar in nature. Therefore, it becomes a challenging task to annotate the data correctly and pass it to machine learning model.

Figure~\ref{fig:senti_methodology} illustrates the proposed methodology for identifying and updating the latent beliefs. Its inputs include the utterances and a domain ontology.

\begin{figure}
\centering
      \includegraphics[scale=0.25]{images/arch.png}
    \caption{Domain Specific Latent Belief Extraction Process}
    \label{fig:senti_methodology}
\end{figure}

\subsection{Step 1: Classifying Latent Beliefs}

If an utterance belongs to more critical categories such as \textit{confused}, it is assigned a higher weight as compared to category such as \textit{curious}. This is intuitive that student with a more confused state of mind would need more attention and a specific dialog plan. The latent belief classification is done with the help of machine learning in an automatic fashion.

\subsection{Step 2: Enriching Beliefs using Domain Ontology}

We make use of knowledge mining derived using the domain ontology to update the latent beliefs. Our ontology consists of a large knowledge graph expressing the information about a domain. For example, this includes the course information, their easiness ratings, workload ratings and class size (See Figure~\ref{fig:meta_info}). This information is available in a structured RDF graph. Use of ontology assists in enriching the beliefs further. It also helps to map the utterance which can be in any natural language form to a structured information that can be used to tailor the FSM based dialog manager.

\begin{figure}
\centering
      \includegraphics[scale=0.3]{images/meta_info.png}
    \caption{Domain Knowledge for Belief Enrichment}
    \label{fig:meta_info}
\end{figure}

\subsection{Epistemic Reasoning over Latent Beliefs and Domain Knowledge}

The extracted latent beliefs and the domain knowledge trigger the epistemic rules. For example ``\texttt{Belief (Student is confused) and Course\_Load(High) => Knows-Agent (student is not confident), Knows-Agent (should advise light courses)}'' asserts facts about the current epistemic state of the agent. We use \texttt{Prolog} to define epistemic rules and carry out the reasoning against facts and domain knowledge.

\subsection{Step 3: Learning the Model for Latent Belief Extraction}

We now train a LSTM (Long Short Term Memory) network to build a model that can automatically categorize the beliefs based upon the information described in previous section (See Algorithm~\ref{alg1}). Like many other studies of LSTM on text, words are first converted to low-dimensional dense word vectors via a word embedding layer. The first layer is therefore the embedding layer that uses 32 length vectors to represent each word. The next layer is the LSTM layer with 100 units. Finally, we use a dense output layer with 5 neurons (5 classes/labels) and a softmax activation function to make the predictions. We used \textit{Categorical\_Cross\_Entropy} as the loss function (in \textit{Keras}) alongwith ADAM optimizer. For regularization, we employ dropout to prevent co-adaptation. We run the experiment for 20 epochs with a batch size of 64.

\begin{algorithm}
\caption{Algorithm for Updating Dialog States using Latent Belief Extraction}
\label{alg1}
\begin{algorithmic}

   \REQUIRE FSM for dialog
   \REQUIRE User Input as Dialog Utterance $T$
   \ENSURE Fine Grain Set of Latent Beliefs
   \ENSURE Meaningful dialog states
   \FOR{all Utterances $r$ in $T$ }
   \FOR{all states ${s_i}$ of FSM}
   \STATE Remove Stopwords and Punctuations
   \STATE Convert to Lowercase
   \STATE Tokenize
   \STATE Mark special name-entities

   \FOR{all sentence $m$ in $r$ }
   \STATE Extract Latent Beliefs {$Curious$, $Confused$ etc.}
   \STATE Using Domain Ontology {$courses$, $workload$, $size$ etc., update latent beliefs $b$}
   \STATE Using Information Extraction, update $b$
   \STATE Using facts ${F_i}$ and EPISTEMIC\_rulebase, fill slots of Dialog manager Frames
   \STATE update weight ${w_i}$ of state ${s_i}$ using Latent Beleifs and Epistemic Reasoning
   \STATE Using threshold and weights, build meaningful states of FSM (ask\_states, skip\_states)
    \ENDFOR
    \ENDFOR
    \ENDFOR

\end{algorithmic}
\end{algorithm}

In our experiments we consider dialog dataset student advisor conversations from \url{https://www.ibm.com/blogs/research/2018/07/sentence-selection-dstc7}. We manually annotate latent beliefs across three categories such as \emph{Curious, Confused and Neutral}. Total number of utterances after data processing were 3500 (Figure~\ref{fig:belief_classes}). The clean-up process involves converting text to lower case; tokenizing the sentences; and removal of punctuations and stopwords. Each input utterance as input is converted into a vector form. We identify the top 300 unique words and every word in this vocabulary is given a index. If the word is not present in vocabulary we consider it as 0. For Example: \textit{I am very disappointed today}. The vector representation of this sentence is [10, 100, 23, 467, 0]. Next, we need to truncate and pad the input sequences so that they are all the same length. We take the max length of utterance to be 50.  We divide the data into training set (75\%)  and test set (25\%). We ensure that we do not have data sparsity issue i.e. We keep approximate equal proportion of data for each class.

\subsection{Experimental Results}

\begin{figure}
\centering
     \includegraphics[scale=0.45]{images/belief_classes_v2.png}
    \caption{Number of Utterances in Training Data for each Category (Latent Beliefs)}
    \label{fig:belief_classes}
\end{figure}

We evaluate the proposed method on the seventh Dialog State Tracking Challenge (DSTC-7) dataset (``Flex Data: Student – Advisor dialogue"~\cite{Flex}). We used 3500 conversations including list of paraphrases for each utterance as training data for belief classification. It becomes a little challenging to tag them to correct categories because of lexical similarity between these three classes. We got 84\% classification accuracy for latent belief extraction. We also tried bag-of-words and naive bayes models that performed badly for this experiment. As we discussed earlier, this is possible due to lot of common words between three classes.

\subsection{Example: Tailoring the Chatbot}
\label{chatbot}

We parse a dialog through Dependency parsers (such as Stanford-CoreNLP, GATE, MITIE etc.) and
extract triples from the description by focusing on the dependencies identified among nouns and verbs. For example, for a description \textit{''I prefer morning classes as I sleep early at night"}, triples such as (\textit{I, prefer, morning classes}) are extracted. Once the triples are extracted, we use a hand-crafted fact-assertion rulebase to assert facts implied by the triples. This is done by evaluating the triples in the context of a student-advisor ontology, synonym-and-slang dictionary, information-extraction patterns that are relevant for the category of the belief, and by triggering the fact-assertion rules. The latent belief identification process helps to understand the student's emotional beliefs and tailor the conversations accordingly.

We assume that we have a hand-crafted dialog-management finite-state-machine (FSM) to carry out the dialog with the student. The FSM operates on slots that are filled by extracting information from the input dialog and subsequent interaction. The probable beliefs of the student that were asserted as facts are then evaluated by the epistemic rules encoded in a knowledge base for the domain. The rules make assertions about the states in the FSM that need to be skipped and the states that need to be evaluated in order to be consistent with the beliefs of the student. The subsequent dialog is carried out and the next set of beliefs are then asserted. The cycle then continues. As shown in Table~\ref{Sample_Output}, we can observe that chatbot is able to skip some FSM states as a result of latent beliefs. The beliefs and epistemic rules helped tailor the dialog to the user's expectations. In this work, we demonstrate the overall architecture where we use the output of RNN based belief identification model as an input to the epistemic rule engine. Our approach is generic and can be applied easily in any other domains.

  \rowcolors{2}{gray!25}{white}

\begin{table}
\footnotesize
\begin{center}
\caption{Sample Output of Dialog System}
\label{Sample_Output}
\begin{tabular}{|p{3.2cm}|p{4.1cm}|}
    \rowcolor{gray!50}

\hline
Advisor & Hi! I am your advisor. You can ask any doubts in selection of your courses for next semester.
\\
\hline

\hline
Student & I am a junior year student with interest in statistics and data analysis
\\
\textcolor{blue}{Output ($ML$-$Model$)} & \texttt{\textcolor{blue}{Latent Belief: Student(Curious)}}\\

\hline
Advisor \textcolor{red}{(skipstate(ask\_interest), skipstate(ask\_semester))} & Do you have any specific requirement \textit{about the workload} of the course
\\

\hline
Student & I would prefer a \textit{class with lighter workload} and higher helpfulness rating
\\

\hline
Advisor & Do you have any timing preferences?
\\

\hline
Student & I \textit{prefer morning classes} as I sleep early at night.\\

\hline
Advisor \textcolor{red}{(SkipState(ask\_extra\_details))} & I would advise you STATS250 ``Statistics and Data Analysis" which is an easy course.\\

\hline

\end{tabular}
\end{center}
\end{table}

\section{Conclusion}
This paper presents a supervised approach to identify latent beliefs from dialog utterances and tailor the dialog. In future, we would like to investigate reinforcement learning based approaches for belief identification.

\bibliographystyle{aaai}