\section{Introduction}
Interactive spoken content retrieval (SCR) system enhances a retrieval system by incorporating user-system interaction~\cite{robins2000interactive,ruthven2008interactive} into the spoken content retrieval process. 
The primary task of SCR is to retrieve the spoken content~\cite{garofolo2000trec} or multimedia~\cite{patton2002interactive,cho2004emotional} desired by the user. 
The necessity of user-system interaction in an SCR system is shown in many aspects.
In SCR, the spoken content is usually transcribed into one-best transcriptions or lattices~\cite{saraclar2004lattice,hakkani2006beyond,7114229,can2011lattice,parlak2008spoken}.
As ASR errors are inevitable, the retrieved results often contain ambiguities. 
Additionally, it is difficult to display the retrieved multimedia or spoken information items to users~\cite{Zhang:2015:IRC:2766462.2767761}. 

In previous work, the Markov decision process (MDP) has been used to model spoken-content interactive information retrieval (IIR)~\cite{6018284,wen2012interactive,wen2013interactive}. 
Wu et al.~\cite{wu2016interactive} propose using deep reinforcement learning (RL) in interactive SCR.
Approaches to learning interaction policy include training a system to learn against a user simulator~\cite{schatzmann2006survey,asri2016sequence,li2016user}. 
In spoken-content IIR, the agent learns through interaction; however, it is not feasible to learn this using real users in user-system interaction. Thus a user simulator is used to train spoken-content IIR.
The construction of the user simulator is often the key to a satisfactory system.
	Policies learned with a poor user simulator can be worse than heuristic hand-crafted policies~\cite{thomson2010bayesian}. 
In previous approaches, simulated users choose actions based on hand-crafted rules without randomness~\cite{6018284,wen2012interactive,wen2013interactive,wu2016interactive}. 
These hand-crafted rules are not sufficient to simulate the behavior of real users. 
Moreover, simulated users are unrealistic in that they always generate the same responses given the same situations.

To create a reliable user simulator, we propose a new framework for interactive SCR. 
We design a trainable user simulator for use in joint learning with the dialogue manager, making hand-crafted simulated users unnecessary.
Joint optimization of the dialog agent and the user simulator with deep RL using simulated dialog between the two agents has been proposed for task-oriented dialogue~\cite{liu2017iterative}, and leads to promising improvements after pre-training by supervised learning. 
Learning two agents jointly has also been considered in object detection dialogue~\cite{de2017guesswhat} and negotiation dialogue~\cite{lewis2017deal}.
In this paper, we consider interactive SCR, which is quite different from previous work.
Here both the user simulator and the IIR system are learned jointly by  deep Q-network (DQN)~\cite{mnih2013playing} from scratch without any labeled data for pre-training.
We use advanced DQN algorithms~\cite{hessel2017rainbow} to improve the performance of both the interactive SCR system and the user simulator.
The learned simulator displays more sophisticated behavior and acts more like a real user.


\begin{figure*}[t]
  \centering
  \includegraphics[width=0.97\textwidth]{figure1_v5.pdf}
  \caption{Block diagram of jointly learned user simulator and interactive spoken content retrieval system}
  \label{fig:Proposed ISCR}
\end{figure*}

\section{Proposed Approach}

Figure~\ref{fig:Proposed ISCR} illustrates the framework of the proposed interactive SCR, in which the interactive SCR system and the user simulator are jointly learned.
In the proposed framework, the user simulator is given a set of queries and their corresponding relevant spoken documents.
Although the system developers must provide data to the user simulator, they do not need to recruit real users to interact with the system, which greatly facilitates system development.
During training, the user simulator enters a query (e.g., ``US president'') into the SCR system. 
The system retrieves the search results, and to improve the results, it requests more information from the user (e.g., ``Please provide more information.'').
Then the user simulator responds (e.g., ``Trump''). 
The response is determined based on the current search results and the relevant documents.
Given the response, the SCR system updates the search results and poses another question. 
This interaction between the SCR system and the user simulator continues until the simulator decides to terminate (the user is satisfied with the results, or gives up).

During this interaction, the retrieval system does not know which documents are relevant.
It must learn to ask the most efficient question given the situation to obtain the information with least interaction.
For the user simulator, though, although it knows which documents are relevant, it cannot directly access the database.
It can only update the search results by providing useful responses to the SCR system.
The DQN parameters in the dialogue manager and the user simulator are jointly learned so the SCR finds the relevant documents in the most efficient way.
During interaction, real users also do their best to help the SCR system.
Thus we believe that a user simulator learned in this fashion is better than one based on hand-crafted rules.
 
The interactive SCR system is described in Section 2.1, and the user simulator is described in Section 2.2.  
The DQN is used to determine the actions of both the interactive SCR system and the user simulator.
The relevant DQN algorithms are described in Section 2.3. 

\subsection{Interactive SCR System}
The interactive SCR system comprises the retrieval module, the feature extraction module, and the dialogue manager module~\cite{wu2016interactive}.
The user first enters a query \emph{q} into the system. With this user query, and potentially with other extra feedback information from the user during further user-system interaction~\cite{lee2012improved,zhai2001model,tao2006regularized}, the retrieval module generates a list of retrieval results.
The retrieved results returned from the retrieval module are fed into the feature extraction module, after which they are represented as a feature vector~\cite{wu2016interactive,wen2013interactive}. 
The dialogue manager determines the action based on the extracted features.
There are four possible actions: return documents\footnote{The system says ``Please view the list and select one item relevant to your need''.}, return key term\footnote{The system says ``Is it related to $t^*$?'', where $t^*$ is a key term.}, return request\footnote{The system says ``Please provide more information''.}, and return topic\footnote{The system shows a list of topics and says ``Which topic is related?''.}.
By taking an action and showing the retrieved results based on the current information, the user's response provides the system with more information, enabling the system to update the retrieved results. 
Given the updated results, the dialogue manager 
goes on to the next dialogue round until the user decides to end the interaction.


For the system reward, we use a tailored negative reward for each action because no matter what action is taken by the dialogue manager, all feedback actions represent an additional burden to the user. 
To evaluate the retrieval result, we utilize the mean average precision (MAP) as an indicator:
the better the MAP, the higher reward obtained by the system.
The return (total reward) $R$ of a dialogue is defined as
\begin{equation}
  R =  \sum_{k=1}^T c_k + \lambda r_k, \label{eq1}
\end{equation}
where $c_k$ is the negative reward from the action taken at the $k$-th turn, and $r_k$ is the MAP improvement after the interaction. 
$\lambda$ is a constant set by the system developer.



\subsection{User Simulator}

Given the action of the SCR system, the user simulator offers a response.
In the user simulator, for each action the corresponding decision maker decides on the suitable response. 
The input of the decision maker is a $K$-dimensional feature vector.
The feature vector is the relevance of the top-$K$ documents in the retrieved list from the SCR system, which represents the retrieval quality of the  retrieval results at the current stage.
If the document ranked at the $k$-th position is relevant, the $k$-th dimension is 1; otherwise, the value is zero (the relevance of the returned documents is known only by the user simulator, not the SCR system).

Because the SCR system has four possible actions, there are four decision makers in the user simulator.
The four decision makers are described as follows: 
\begin{itemize}
\item\textit{Return Documents}:  
Given a retrieved list, we rank the relevant documents based on their relevance scores from the retrieval system. 
The response is the relevant documents ranked at a specific position.
The decision maker determines the reply by document rankings. 
\item\textit{Return Key Term}: If the key term appears in more than 50\% of the relevant documents, the simulated user replies ``YES'' with probabilities of 100\%, 95\%, 90\%, or 85\%. The probability is decided by the decision maker.
\item\textit{Return Request}: Each term $t$ has a score $S(t)=\sum_{d \in \mathcal{R_T}}{N(t,d) ln(1+idf(t))}$, where $N(t,d)$ is the term frequency of term $t$ in the manual transcription of document $d$, $idf(t)$ the inverse document frequency of term $t$ computed from the manual transcriptions of the document collection, and $\mathcal{R_T}$ the real relevant document set provided by the annotators.
All the terms are ranked according to $S(t)$.
Again, the decision maker determines the reply by term rankings. 
\item\textit{Return Topic}: 
Given a query, a set of topics is ranked according to their relevance to the query (the relevance is provided by the annotators).
The decision maker determines the reply by topic rankings. 
\end{itemize}

If the MAP of the retrieved result is higher than a threshold (thus meeting the user's information need) or the interaction turns exceeds a maximum number (the user gives up), the interaction stops.
If the interaction ends because the MAP is higher than a threshold, the dialogue is deemed a success and the user simulator receives a positive reward; otherwise, the dialogue fails, and a negative reward is given as punishment\footnote{In contrast to the dialogue manager, the user simulator does not receive a negative reward for each action.}.
In this study the threshold is set to 0.6, and the maximum number of turns is 4.

\subsection{Reinforcement Learning} \label{subsec:rl} 

The dialogue manager in the interactive SCR system as well as all the decision makers in the user simulator are deep Q-networks (DQNs)~\cite{mnih2013playing}.
The input of each DQN is a feature representation $s$, 
known also as a \textit{state} per reinforcement learning.
The definitions of this feature representation differ between the dialogue manager and decision maker. 
The DQN output dimension equals the number of possible actions $a$ in the action set.
The output corresponding to each action is the state-action value $Q(s, a)$. 
As the possible actions for the DQN in the dialogue manager are \textit{Return Documents}, \textit{Return Key Term}, \textit{Return Request}, and \textit{Return Topic}, the output dimension for the DQN in  dialogue manager is four.
For the user simulator decision makers, the DQN for the Return Key Term decision maker has four outputs (corresponding to 100\%, 95\%, 90\%, and 85\%).
For the remaining three decision makers, each DQN output dimension corresponds to a ranking position (1st, 2nd, 3rd, etc).
All the DQNs (one in the SCR system and four in the user simulator) are trained to maximize the expected return of the system they belong to via the interaction between the interactive SCR system and the user simulator.
To ameliorate the risk of instability when jointly learning the user simulator and retrieval system~\cite{liu2017iterative}, we update the DQNs in the two systems iteratively.
That is, we first fix the DQNs in the user simulator, and update the DQN in the SCR system $C$ times.
Then we switch the training agent:
We update the DQNs in the user simulator another $C$ times, while fixing the SCR system.
The above procedure is conducted iteratively.

In addition to the standard DQN algorithm, we use the extended versions.
As the standard DQN algorithm has been observed to overestimate the Q-values~\cite{van2016deep,hasselt2010double}, double DQN is also used in the following experiment, which decouples the selection from the evaluation~\cite{van2016deep,hasselt2010double}.
Dueling DQN~\cite{wang2015dueling} is further applied here. Compared to typical DQN, dueling DQN uses an altered network structure, splitting it into two streams: one learns to provide an estimate of the state value $V(s)$ for every state, and the other calculates the potential advantages 
of each action at a given state.  



\begin{comment}
\subsubsection{Typical DQN Training Algorithm}

Via the interaction between the interactive SCR system and user simulator, each DQN will collect a set of experiences, $T = \{e_1, e_2, ..., e_t, ...e_T \}$, is collected for training.  
Each $e_t = (s_t, a_t, r_t, s_{t+1})$ means taking action $a_t$ at state st obtaining reward $r_t$ and reaching state $s_{t+1}$ at the next time step). 
$T$ is a data set collected over many retrieval episodes.

The DQN\cite{hinton2006reducing,bengio2009learning} is trained by iteratively updating the parameters $\theta$. 
With parameters obtained at the $i$-th iteration,denoted as $\theta^i$, $\theta^i$ can be learned by minimizing the following loss function $L_i(\theta^i)$  in (\ref{eq2}) by gradient descent.
\begin{equation}
  L_i( \theta ^i)= E_{s,a,r,s^ \prime \sim U(T)}[(\hat{y}_i- Q(s,a; \theta ^i))^2 ]
\label{eq2}
\end{equation}
The expression $s, a, r, s^\prime \sim U(T)$ in (\ref{eq2}) indicates that the
network is trained by sampling mini-batches of experiences
from $T$ uniformly at random. This method is raised for experience replay\cite{mnih2015human,lin1993reinforcement}. In this way, the training data is
used more efficiently via re-use of the experience samples in
multiple updates. 
$\hat{y}^i$ in (\ref{eq2}) is defined as below:
\begin{equation}
\hat{y}_i = r +  \gamma  \cdot \max_{\hat{a}^ \prime  \in A} Q (s^\prime,a^\prime; \theta^-  )
\label{eq3}
\end{equation}
Where $\theta^−$ is taken as the parameters obtained several iterations before. Freezing the parameters of the target network $Q(s^\prime,a^\prime; \theta^-)$ while updating the online network $Q(s, a; \theta^i)$improves the stability of the algorithm\cite{mnih2015human,lin1993reinforcement}.

\subsubsection{Double DQN}

The standard DQN algorithm above is noted to overestimate the Q-values \cite{van2016deep,hasselt2010double}. 
Double DQN is proposed, which decouples the selection from the evaluation\cite{van2016deep,hasselt2010double}.
In the algorithm of double DQN, two DQN networks, $\theta$ and $\theta^\prime$, are learned. For each update, one of the DQN network is used to determine the policy, and the other determines its value. Equation (\ref{eq3}) is modified as follow.
\begin{equation}
\hat{y}_i = r +  \gamma  \cdot Q(s^\prime, arg \max_{\hat{a}^ \prime  \in A} (s ^\prime,a^\prime;\theta^i); \theta^\prime  )
\label{eq4}
\end{equation}
In (\ref{eq4}), the selection of the action $a$ using the argmax operation is based on $\theta^i$. However, we use the second DQN, $\theta^\prime$, to fairly evaluate the value of this state-action pair.
To obtain two DQN networks, one alternative is to assign each experience randomly to update one of the two networks, but in this paper, we use $\theta^-$ in (\ref{eq3}) as $\theta^\prime$, or $\theta^\prime = \theta^-$.

\subsubsection{Dueling DQN}
Dueling DQN \cite{wang2015dueling} is further applied here. Comparing to typical DQN, dueling DQN presents a change in the network structure. It splits the network structure into two streams: one learns to provide an estimate of the state value $V(s)$ for every state $s$, and the other calculates potential advantages of each action $s$ at $a$ give state $s$, $A(s, a)$. The Q-value is the integration of the state value and advantage value, or $Q(s, a) = V (s)+A(s, a)$.
The network structure of dueling DQN significantly improves the learning speed on account of adding additional information about the composition of action-values during estimation. 
With dueling architecture, we start to learn the state values $V(s)$ once an action has been taken at state $s$, which makes the learning faster. 
\end{comment}

\begin{table*}[]
\centering
\caption{MAP and Return for different approaches evaluated on both one-best transcription and lattices}
\label{my-label}
\begin{tabular}{|c|c|c|l|l|l|l|}
\hline
\multicolumn{3}{|c|}{Approaches} & \multicolumn{2}{c|}{One-best} & \multicolumn{2}{c|}{Lattices} \\ \hline
User simulator & Dialogue manager & \multicolumn{1}{l|}{Input feature} & \multicolumn{1}{c|}{MAP} & \multicolumn{1}{c|}{Return} & \multicolumn{1}{c|}{MAP} & \multicolumn{1}{c|}{Return}  \\ \hline\hline
\multirow{6}{*}{(a) Rule-based} 
 & \multirow{2}{*}{(a-1) DQN } & Raw & 0.5641 & 99.31 & 0.5847 & 112.24 \\ \cline{3-7}  
 &  & Human+Raw & 0.5655 & 107.02 & 0.5790 & 101.99  \\ \cline{2-7} 
 & \multirow{2}{*}{(a-2) Double DQN} & Raw & \textbf{0.5744} & \textbf{107.08} & 0.5911 & 112.14  \\ \cline{3-7} 
 &  & Human+Raw & \textbf{0.5846} & \textbf{115.70} & \textbf{0.5959} & \textbf{102.52}\\ \cline{2-7} 
 & \multirow{2}{*}{(a-3) Dueling DQN} & Raw & 0.5562 & 96.27 & \textbf{0.5860} & \textbf{113.70}  \\ \cline{3-7} 
 &  & Human+Raw & 0.5665 & 105.35 & 0.5784& 96.37 \\ \cline{2-7} 
\hline\hline
\multirow{2}{*}{(b-1) DQN} & \multirow{2}{*}{DQN} & Raw & 0.5758 & 113.02 & 0.6041 & 162.85   \\ \cline{3-7} 
 &  & Human+Raw & 0.5820 & 130.83 & 0.6027 &  162.93  \\ \hline

\multirow{2}{*}{(b-2) Double DQN} & \multirow{2}{*}{Double DQN} & Raw & \textbf{0.6063} & \textbf{190.39} & \textbf{0.6414} & \textbf{224.42} \\ \cline{3-7} 
 &  & Human+Raw & \textbf{0.6066} & \textbf{199.17} & \textbf{0.6375} &  \textbf{222.66}  \\ \hline

\multirow{2}{*}{(b-3) Dueling DQN} & \multirow{2}{*}{Dueling DQN} & Raw & 0.5780 & 108.72 & 0.5864 &  157.92 \\ \cline{3-7} 
 &  & Human+Raw & 0.5757 & 127.49 & 0.5723 &   158.23 \\ 

\hline\hline

\multirow{2}{*}{(c-1) Double DQN} & \multirow{2}{*}{Dueling DQN} & Raw & 0.5733 & 134.20 & 0.5678 & 143.83  \\ \cline{3-7} 
 &  &Human+Raw &0.5573 & 111.84 & 0.5905 &  146.83\\ \hline
 
\multirow{2}{*}{(c-2) Dueling DQN} & \multirow{2}{*}{Double DQN} & Raw & \textbf{0.5899} & \textbf{164.00} & \textbf{0.6494} &  \textbf{238.91}   \\ \cline{3-7} 
 &  & Human+Raw & \textbf{0.6139} & \textbf{208.25} & \textbf{0.6420} & \textbf{225.72} \\ \hline
\end{tabular}%
\end{table*}


\section{Experiments}

\subsection{Data Set}

In the experiments, we used a Mandarin Chinese broadcast news corpus as the spoken document collection from which to retrieve news. The news stories were recorded from radio or TV stations in Taipei from 2001 to 2003, and comprised a total of 5047 news documents covering a total length of 198 hours. For speech recognition, both one-best transcriptions and lattices were generated for spoken content retrieval. Twenty-two graduate students were recruited as the annotators, providing 163 text queries and their relevant spoken documents (not necessarily including the query terms). 

\subsection{Experiment Settings}
Our retrieval module is based on language modeling~\cite{lafferty2001document,chia2010statistical}. After receiving the user feedback in the dialogue, we use the query-regularized mixture model~\cite{lee2012improved,zhai2001model,tao2006regularized}  to generate the new query $q^\prime$. 
The input dimension $K$ of the decision makers was set to 49.
The output dimensions for the four DQNs in the user simulator were all set to four.

All the DQNs had the same hyper-parameters. We used networks with two hidden layers of 1024 nodes. We used relu as the activation function and set the batch size to 256. The initial learning rate was set to 8e-4. MAP was selected as our retrieval evaluation metric. Ten-fold cross validation was performed in all experiments; that is, for each trial, 8 out of 10 query folds were used for training, 1 for parameter tuning (validation set), and the remaining fold for testing.

\begin{figure}[t]
  \centering
  \includegraphics[width=\linewidth]{iteration_v3.png}
  \caption{Learning curve of different methods}
  \label{fig:iteration}
\end{figure}

\subsection{Results and Discussion}

In this subsection, the user simulator is used to both train and test the SCR system. 
Figure~\ref{fig:iteration} shows the learning curves of different methods on the training set. 
The rule-based system is identical to previous work~\cite{wu2016interactive}.
The proposed approach is based on a typical DQN 
with the $C$ iterative steps from Section~\ref{subsec:rl}. 
We find that training with the rule-based system is more stable than the proposed approach, and results in better performance in the first few epochs.
This is reasonable because it is more difficult to train two systems together.
However, with more epochs, the proposed approach eventually outperforms the previous rule-based method.
$C$ was set to 500 in the following experiments.

Table 1 shows the MAP and Return results for the SCR system based on one-best transcription and lattices.
For each  approach, the dialogue manager DQN utilizes two kinds of input features, which were also used in previous work~\cite{wu2016interactive}. 
\textit{Raw} represents the relevance scores of the top-N documents in the retrieved results, and \textit{Human} indicates the use of hand-crafted features based on human knowledge such as clarity score~\cite{he2006query}, ambiguity score~\cite{cronen2002predicting}, and weighted information gain (WIG)~\cite{zhou2007query}. 
The table is divided into three blocks.
In part (a), the rule-based user simulator was used, which is identical to Wu et al.~\cite{wu2016interactive}.
The results of the learnable user simulator are in parts (b) and (c). 
In part (b), we used the same DQN algorithm for the user simulator and dialogue manager, while in part (c), we used different algorithms.

In part (a), we compare the different DQN algorithms with the rule-based user.
The results show that in some cases, both double and dueling DQN outperform the typical DQN.
Using the same DQN algorithm, the trainable user simulator always outperforms the rule-based user simulator (rows (b-1) v.s. (a-1), rows (b-2) v.s. (a-2), rows (b-3) v.s. (a-3)).
For example, compare (b-1) with the baseline (a-1): the trainable user simulator yields improvements of 35.2\% in terms of Return.
We further achieve our best performance on (c-2), by utilizing dueling DQN for the user simulator and double DQN for the dialogue manager. Why this combination yields the best performance is still under investigation.
It shows significant improvement, outperforming the rule-based baseline ((c-2) v.s. (a-1)) by 88.4\% and joint learning using the same DQN algorithm ((b-2) v.s. (a-1)) by 99.0\%.
However, it is not enough to simply show that the trainable user simulator results in higher returns for the SCR system: it is possible that the user simulator is learning a very unnatural way to provide information to the SCR system.
We address this in the next subsection.



\subsection{Human evaluation}

\begin{table}[]
\centering
\caption{KL-divergence between rule-based simulator, learnable simulator and human results, as well as each system's entropy}
\label{KL_entropy}
\begin{tabular}{cccc}
\multirow{2}{*}{KL-divergence} & Rule/human & Ours/human      & Rule/ours \\ \cline{2-4} 
                               & 5.9899     & \textbf{2.1503} & 6.1859    \\
\multirow{2}{*}{Entropy}       & Rule & Ours            & Human     \\ \cline{2-4} 
                               & 0    & \textbf{0.6006} & 0.8886   
\end{tabular}
\end{table}

To verify the correlation and similarity between the proposed user simulator and real users, we performed a subjective human evaluation with 21 subjects, all of whom were graduate students. Given a sampled query, the subject was asked to identify the most relevant document in the top-4 retrieved relevant documents\footnote{Because the output dimension of the decision maker for \textit{Return Document} is 4, it returns only relevant documents ranked in the top four.}. 
Due to space limitations, we show only the results of \textit{Return Document}; the results for the other actions are similar.
The choices of human, rule-based user, and decision maker are considered random variables (with 1st, 2nd, 3rd, and 4th as the outcomes).
We calculated the KL-divergence between the rule-based user simulator, our proposed trainable user simulator, and the human evaluation result.
In Table 2, which lists the average results, the abbreviations are Rule, Ours, and Human respectively. 
The proposed user simulator and human have the smallest KL divergence (Ours/Human).
This shows that the proposed joint training of the user simulator was more closely correlated to the distribution of human evaluations than the rule-based approach. 
We further calculated the entropy of each distribution.
The entropy of the rule-based system was zero because given the same input, it always produces the same response.
The result shows that the decisions made by the proposed user simulator were more diverse and also closer to human evaluation than the rule-based simulator. 

\section{Conclusions}
User-system interaction is highly desired for SCR. 
Interactive SCR is usually learned using simulated users, but designing simulated users using hand-crafted rules is difficult.
In this paper, we propose a new framework in which the user simulator and the interactive SCR system are jointly learned. 
The experimental results show that the proposed method leads to promising improvements on return. 
Human evaluation further shows that a trainable user simulator much more closely reflects human behavior.


\bibliographystyle{IEEEtran}

