Guessing State Tracking for Visual Dialogue

The Guesser plays an important role in GuessWhat?! like visual dialogues. It locates the target object in an image supposed by an oracle oneself over a question-answer based dialogue between a Questioner and the Oracle. Most existing guessers make one and only one guess after receiving all question-answer pairs in a dialogue with predefined number of rounds. This paper proposes the guessing state for the guesser, and regards guess as a process with change of guessing state through a dialogue. A guessing state tracking based guess model is therefore proposed. The guessing state is defined as a distribution on candidate objects in the image. A state update algorithm including three modules is given. UoVR updates the representation of the image according to current guessing state, QAEncoder encodes the question-answer pairs, and UoGS updates the guessing state by combining both information from the image and dialogue history. With the guessing state in hand, two loss functions are defined as supervisions for model training. Early supervision brings supervision to guesser at early rounds, and incremental supervision brings monotonicity to the guessing state. Experimental results on GuessWhat?! dataset show that our model significantly outperforms previous models, achieves new state-of-the-art, especially, the success rate of guessing 83.3% is approaching human-level performance 84.4%.


Introduction
Visual dialogue has received increasing attention in recent years. It involves both vision and language processing and interactions between them in a continuous conversation, and brings some new challenging problems. Some different tasks of Visual Dialogue have been proposed, such as Visual Dialog [7], GuessWhat?! [9], GuessWhich [5], Image-Grounded Conversation [17] and Multimodal dialogs [20]. Among them, GuessWhat?! is a typical object guessing game played between a Questioner and an Oracle. Given an image including several objects, the goal of the Ques- tioner is to locate a target object supposed by the oracle oneself at the beginning of a game by asking a series of yes/no questions. The Questioner therefore has two subtasks: one is Question Generator (QGen) that asks questions, the other is Guesser that identifies the target object in the image. The Oracle answers questions with yes or no. The left part of Fig.1 shows a game played by the QGen, Oracle and Guesser. The Guesser, which makes the final decision, is the focus of this paper.
Compared with QGen, relatively less work has been done on Guesser. De Vries et al. [9,24] proposed the first Guesser model that outputs probabilities over objects in the image, where the full dialogue history is encoded by a Long Short-Term Memory (LSTM) [12], an object is represented by its category and spatial position, a dot product and a softmax are used to match between the dialogue history and any object. The object with maximum probability is selected as the answer. If the right object is picked, the game is successful. Some other Guesser models [34,2,22,21] were proposed, which are similar to the model in [9,24] except for encoding of dialogue history and images. Zhao et al. [34,2] introduced memory [25] and attention [6] to the model [9,24], the question-answer (QA) pairs are encoded using two-hops attention. Shekhar et al. [22,21] used a shared encoder in conjunction with the QGen task to process the dialogue history.
Most of existing Guesser models make a guess after fixed rounds of QA, such as [9,24,19] or [34,2,21,22]. It is obvious that different game might need different rounds of question-answer. Some work has therefore been done on choosing when to guess, i.e. make a guess after different rounds of question-answer for different game.
No matter the number of question-answer rounds is fixed or changed in different dialogues, existing Guesser models make one and only one guess after final round of questionanswer, i.e. Guesser is not activated until it reaches the final round of dialogue.
This paper models the Guesser in a different way. We think the Guesser is active through a dialogue. It keeps on updating a guess distribution after each question-answer pair from the beginning, and does not make a final guess until the dialogue reaches a predefined round or it can make a confident guess. For example, as show in Figure 1, a guess distribution is initiated as uniform distribution, i.e. each object has same probability as target object at beginning of the game. After receiving the first pair of question-answer, the guesser updates the guess distribution and continues to update the distribution in following rounds of dialogue. It makes a final guess after predefined 5 rounds of dialogue.
We think that modeling the Guesser as a process instead of a decision in single point provides more chances to not only make much more detailed use of dialogue history but also combine more information for making better guesses. One such information is monotonicity, i.e. a good enough guesser will never reduce the guess probability on the target object by making proper use of each question-answer pair. A good guess either raises the probability of target object in guess distribution when the pair contains new information about target object, or does not change the probability when the pair contains no new information.
This paper proposes a guessing state tracking (GST) based Guesser model to implement the above idea. Guessing state (GS) is at first time introduced into the game. A GS is defined as a distribution on candidate objects. A GST mechanism, which includes three sub-modules, is proposed to updating GS after each question-answer pair from the beginning. The update of GS brings a series of GS.
Two loss functions are designed on making better use of the GS, or the introduce of GS into visual dialogue makes the two new loss functions possible. One is called early supervision loss that tries to lead GS to the target object as early as possible, where ground-truth is used to guide the guesses after each round of question-answer, even the guess after first round where a successful guess is impossible at that time. The other is called incremental supervision loss that try to bring monotonicity mentioned above to the probability of target object in the series of GS.
Experimental results show that the proposed model achieves new state-of-the-art performances in all different settings on GuessWhat?!. To summarize, our contributions are mainly three-fold: • We introduce guessing state into visual dialogue for the first time, and propose a Guessing State Tracking (GST) based Guesser model, a novel mechanism that models the process of guessing state updating over question-answer pairs.
• We introduce two guessing states based supervision losses, early supervision loss and incremental supervision loss, which are effective to model training.
• Our model performs significant better than all previous models, and achieves new state-of-the-art in all different settings on GuessWhat?!. The accuracy of 83.3% approaches the humans level of 84.4%.

Related Work
Guesser models play a very important role in many visual dialogue tasks such as GuessWhat?!. Some different models have been proposed on modeling Guess. The first guesser model was proposed in [9,24]. The model makes a guess after a dialogue between the QGen and the oracle. Each dialogue includes given number of question-answer pairs. All question-answer pairs in a dialogue are encoded sequently by an LSTM into a vector as the representation of the linguistic dialogue. Each candidate object is embedded into a vector by concatenating theirs 512-dimensional category embedding and 8-dimensional spatial embedding. A dot product is then used to calculate similarity between the representation of the dialogue and each candidate object. A softmax classifier over the similarities is used to output final guess.
The second different guesser architecture was employed in [34,2]. Memory [25] and Attention [6] modules are integrated into the first guesser model. It is a two-hops of attention [26] module. They encode each QA-pair into a vector as a fact, which form a memory base of facts. The summary of all object embeddings is used as a key, where the encode of object like [9,24]. They perform two-hops attention and obtain a final linguistic representation. Similarly, a dot product and a softmax are used to output probabilities between the dialogue history and each candidate object.
The recent different guesser model was introduced in [22]. Differs from the first guesser model, they use a shared dialogue history encoder with the QGen. The encode of dialogue history and image are similar to [9,24]. Finally, a dot product and a softmax are used to output object probabilities between dialogue history and each object in the image.
As we can see, all existing guesser models make one and only one guess after a given number of question-answer rounds. They treat guess as a single time decision at the end of a dialogue. Different from them, Guesser model proposed in the paper treats guess as a process, and keeps a guessing state through the process. The guessing state is defined as a distribution over objects. The guessing state will be updated after each round of the dialogue. Furthermore, two new loss functions are proposed for making full use of the guessing state.
Moreover, there are some attention-based methods proposed in similar tasks such as VisDial [7,11,18,14,35,30], which are also suitable for solving guesser task. Deng et al. [10] proposed an accumulated attention (ATT) mechanism for guesser and VisDial task. They view guesser task and VisDial are similar and cast guesser task as a visual grounding task [16,32]. Specially, they compute three kinds of attentions respectively, i.e. query attention, image attention and objects attention, combine them together, refine them circularly and obtain a joint representation. Finally, they output probability between the representation and any object by a softmax function. To better consider the impact of imperfect dialogue history, Yang et al. [31] proposed history-aware co-attention network (HACAN) to encode the QA-pairs, a dot product is used to calculate similarities between history and object, the one with highest similarity is selected as the guess.
There are some methods on model learning. De Vries et al. [9] trained the guesser network by supervised learning. Zhao et al. [34] first considered guesser task as a deep reinforcement learning task [27,4,8], a guess is viewed as an action. Shekhar et al. [22] formulated Guesser and QGen as a multi-task learning problem [3] and trained by cooperative learning (CL) [4].

Model: Guessing State Tracking
The framework of our guessing state tracking (GST) model is illustrated in Fig.2. Three modules are implemented in each round of guessing. There are Update of Visual Representation (UoVR), Question-Answer Encoder (QAEncoder) and Update of Guessing State (UoGS). Where, UoVR updates representation of an image for guesser according to the previous round of guessing state, new visual representation is then combined into QAEncoder for synthesizing information from both visual and linguistic sides up to current round of dialogue for guesser. Finally, UoGS is applied to update the guessing state of guesser. We give details of each module in following sub-sections.

Update of Visual Representation (UoVR)
Following previous work [9,24], candidate objects in an image are represented by their category and spatial features as in Eq.1: where i , it is concatenation of a 512-dimensional category embedding o cate and an 8-dimensional vector o spat of the location in the image. To map the dimension of object embedding to the same as the word embedding, the concatenation passed through an MLP to obtain a d-dimensional vector.
Let π (j) ∈ R m be an accumulative probability distribution over m objects after jth round of dialogue. It is defined as the guessing state and will be updated with the guessing process. At the beginning of a game, π (0) is a uniform distribution.
With the progress of guessing, the visual representation for guesser would update accordingly. Two steps are designed for the update.
The first step is update of representations of objects. Pang and Wang [19] proposed an effective way of representation update for QGen model. We borrow it for our guesser model as shown in Eq.2: where O (j) ∈ R m×d . Second, the element-wise summary of all object repre- where v (j) ∈ R d denotes the updated visual representation especially for guesser after jth round of dialogue.

Question-Answer Encoder (QAEncoder)
For encoding linguistic information in current question with visual representation in hand, each word w (j) i in jth question is concatenated with the new visual representation and fed to a LSTM encoder as shown in Eq.4, The last hidden state of the LSTM is used as question representation h (j) , h (j−1) is used as initial input of the LSTM as shown in Fig.2. h (j) is then concatenated to a (j) which the embedding of the answer for jth question, and passes through an MLP as shown in Eq.5, where h (j) qa ∈ R d synthesizes information from both question and answer up to jth round dialogue for the guesser. It will be used to update guessing state in next module.

Update of Guessing State (UoGS)
Three steps are designed for Guessing State update.
where O (j) qa ∈ R m×d is a set of fused representation which combines information from current question-answer pair and visual objects.
Second, a softmax is used to measure how many changes this round of question-answer brings to the guess as shown in Eq.7,π Where, three vectors, including the fused representation and visual object representation as well as representation of question-answer h (j) qa are concatenated together. We find that this type of symmetric concatenation is an effective operation. d is the dimension of word embedding that used for controlling variance.
Finally, the previous rounds of guessing state π (j−1) is updated according toπ (j) as in Eq.8, where π (j) ∈ R m is the new guessing state after jth round of question-answer, norm is normalization keeping π (j) be a probability distribution.

Stop Questioning
When to stop questioning is also a problem in Guess-What?! like visual dialogue. Most of previous work choose a simple policy, i.e, a QGen model stops questioning after a predefined number of dialogue rounds, and the guess model select an object as the guess.
Our model can implement this policy by making use of π (j) , the guessing state after jth round dialogue. If K is the predefined number, the guesser model will keep on updating π (j) till j = K. The object with the highest probability in π (K) will be then selected as the guess.
A same number of questions are asked for any game under this policy, no matter how different the different games are. The problem of the policy is obvious. On the one hand, the guesser model does not select any object even if it is confident enough about a guess, and make a QGen model keep on asking till K questions are asked. On the other hand, the QGen model cannot ask more questions when K questions are asked even if the guesser model is not confident about any guess at that time. The guesser model must give a guess.
Our model provides a chance to adopt some other policies for stopping questioning. A simple way is to predefine a threshold of confidence. Once the biggest probability in a guessing state is equal to or bigger than the threshold, question answering is stopped, and the guesser model output the object with the biggest probability as the guess. Another way involves the gain of guessing state. Once the information gain from jth state to j+1th state is less than a threshold, the guesser model outputs the object with the biggest probability as the guess.

Early and Incremental Supervision
Besides on stopping questioning, the introduce of guessing states provides another useful information for model training.
Because the guessing states are tracked from the beginning of a dialogue, supervision of correct guess can be employed from early stage, which is called early supervision. Because the guessing states are tracked at each round of a dialogue, the change of guessing state can be also supervised to ensure that the guessing is alone a right way. We call this kind of supervision incremental supervision. Two supervision functions are introduced as follows.
Early Supervision Early supervision tries to maximize the probability of the right object from the beginning of a dialogue, and keep on used up to the penultimate round of the dialogue. It is defined as the summary of a series of cross-entropy between the guessing state after each round of dialogue and the ground-truth object as shown in Eq.9, CrossEntropy(π (j) , y GT ), (9) where y GT is a one-hot vector with 1 in the position of the ground-truth object, J max is the maximum number of rounds.
The cross-entropy at the final round, i.e. CrossEntropy(π (Jmax) , y GT ), we refer to as plain supervision loss (L P S in briefly).
Incremental Supervision Incremental supervision tries to keep the probability of the target object in guessing state increasing or nondecreasing as shown in Eq.10, where π (j) target denotes probability value of the target object in guessing state at jth round of dialogue, c is a parameter controlling input value of log function is valid.

Training
Our model is trained in two stages including supervised and reinforcement learning.
For supervised learning, the guesser network is trained by minimizing the following objective as shown in Eq.11, where α is a balancing parameter. For reinforcement learning, the guesser network is refined by minimizing the negative expected reward in Eq.12, (12) where π θ denotes a policy parameterized by θ which associates a guessing state over actions, e.g., an action corresponds to select an object over m candidate objects. We have three notes on Eq.12.
First, it use the REINFORCE [28,29] without baseline. Second, a reward is 1 if the right object is found at the final guess, and 0 otherwise.
Finally, it is trained only on the self-play successful dialogues, the unsuccessful ones are filtered. The reward 1 is spread uniformly over the guessing action at each round.

Experimental Setup
Dataset GuessWhat?! dataset containing 66k images, about 800k question-answer pairs in 150K games. It is split at random by 70%, 15%, 15% of the games into the training, validation and test set [9,24]. The number of object candidates in each image is between 3 and 20, the average number is around 8.
Baseline models A GuessWhat?! game involves Oracle, QGen and Guesser. Almost all existing work use a same Oracle model [9,24] which will be used in all our experiments. Two different QGen models are used for validating our guesser model. One is the often used model in previous work [24], the other is a new QGen model which achieves new state-of-the-art [19]. Several different existing Guess models are compared with our model. They are guesser [9,24], guesser(MN) [34], GDSE [22], ATT [10] and HA-CAN [31]. The models are first trained in supervised way on the training set, and then, one Guesser and one QGen model are jointly refined by reinforcement learning from self-play with the Oracle model fixed. Specifically, selfgenerated successful games are used to tune the Guesser model, while all self-play games are used to optimize the QGen.
Implementation Details The maximum round J max is set to 5 or 8. The balancing parameter in Eq.11 is set to 0.7, the parameter c in Eq.10 is set to 1.1 (We will discuss the influence of these parameters in ablation study). The size of word embedding is 512, LSTM hidden unit number in all three models are 512. Early stopping is used on the validation set. More details, including the source codes and other materials, will be published in the near future.
We use success rate of guessing for evaluation. Following previous work [9,24], both success rates on NewObject and on NewGame are reported. Results by three inference methods described in [2], including Sampling (S), Greedy (G) and Beam-search (BS, beam size is set to 20) are used on both NewObject and NewGame.
Supervised Learning (SL) We separately train the Guesser and Oracle model for 20 epochs, the QGen for 50 epochs using Adam optimizer [13] with a learning rate of 3e-4 and a batch size of 64.
Cooperative Learning (CL) In [22], the QGen and Guesser are first trained with SL. Guesser is further trained using the self-generated dialogues, then QGen is re-trained on the human dialogues with SL. The two models iteratively trained in this cooperative way.
Reinforcement Learning (RL) We use momentum stochastic gradient descent with a batch size of 64 and learning rate annealing. The base learning rate is 1e-3 and decayed every 25 epochs with exponential rate 0.99. The momentum parameter is set to 0.9. Table 1 reports the success rates of guessing with different combination of QGen and Guesser models with the same Oracle model [9,24] for the game GuessWhat?!. In the first part of table 1, all models are trained in SL way. We can see that no matter which QGen models are used, qgen [24] or VDST [19], our guesser model GST significantly outperforms other guesser models in both 5 and 8 rounds dialogue at all different settings. Specifically, GST achieves a new state-of-the-art of 54.10% and 50.97% on NewObject and NewGame in Greedy way by SL.

Comparison with the state-of-the-art
In the second part of table 1, two combinations trained in CL way are given. Our model is not trained in this way. So we do not have comparison in CL case with the performance of these models are lower than those in RL part.
In the third part of table 1, all QGen and Guesser models are trained by RL. We can see that our GST Guess model combined with VSDT QGen model achieves best perfor-mance in both 5 and 8 rounds dialogue at all different settings. It significantly outperforms other models. For example, it outperforms the best previous model at Sampling (S) setting on NewObject (i.e. guesser(MN) [34] + ISM [1] with 72.1%) by nearly 9 percent, outperforms the best previous model at Greedy (G) setting on NewObject (i.e. guesser(MN) [34] + TPG [34] with 74.3%) by more than 9 percent, outperforms the best previous model in NewObject at Beam-search (BS) setting on NewObject (i.e. guesser [24] + VDST [19] with 71.03%) by more than 12 percent. The same thing happens on NewGame case. That is to say, our model consistently outperforms previous models in all different setting on both NewObject and NewGame. Especially, GST achieves 83.32% success rate on NewObject in Greedy way, which is approaching human performance 84.4%. Specifically, with same QGen, no matter which QGen models are used, qgen [24] or VDST [19], our guesser model GST significantly outperforms other guesser models in both 5 and 8 rounds dialogue at all different settings. Table 2. Classification errors (%) for the guesser models (lower is better).

Model
Train err Val err Test err Max Q's Random [9] 82.9 82.9 82.9 -LSTM [9] 27.9 37.9 38.7 -HRED [9] 32 A previous work [10,31] evaluate Guess model only on training data by measuring the error rate of model. For compare, we also follow the error rate of classification for evaluation. Table 2 reports the results. We can see that our method trained in SL is comparable to the best model. After reinforcement learning, our GST based guesser achieves a new state-of-the-arts of 16.7%, 16.9%, 18.4% and outperforms the compared methods by a large margin. Effect of Individual Supervision In this section, we conduct ablation studies to separate the contributions of su-pervisions: Plain Supervision (PS), Early Supervision (ES) and Incremental Supervision (IS). Table 3 reports the success rate of guessing after supervised learning. Removing ES&PS from the full model, the game success rate significantly drops 11.52 (from 54.10% to 42.58%) and 11.49 (from 50.97% to 39.48%) points on NewObject and NewGame on Greedy case. Removing IS, the success rate drops 0.61 (from 54.10% to 53.49%) and 0.64 (from 50.97% to 50.33%), respectively. It shows that early supervision pair with ES&PS contributes more than incremental supervision.

Ablation Study
We then analyze the impact of individual supervision loss to guessing state after reinforcement learning. We train three GST networks using three different loss, i.e. PS, PS&ES and PS&ES&IS, respectively, and then count the average probability of the ground-truth object in guessing state on all successful games at each round for these cases. Fig.3(a) show the curves of average probability changing with rounds of dialogue for three cases.
In Fig.3(a), as is observed, we have three notes. First, the guess probability is progressively increasing in all three different loss. It demonstrates the effectiveness of the proposed guessing state tracking mechanism, i.e. modeling guess as a process helps to improve guess gradually.
Second, the average probability in the blue line is higher than that in the gray line, it demonstrates the effectiveness of early supervision loss.
Third, the average probability in the red line is better than that in the blue line, it demonstrates that incremental supervision gives further improvement to guess model.
Overall, these results demonstrate the effectiveness of early supervision and incremental supervision. It is the combination of these supervisions that train GST based model efficiently.  Figure 3. a, the average guessing state on the ground-truth object change with an increase in the number of dialogue rounds. b, the error rate at different α settings.
Effect of balancing parameter α in Eq.11 Fig.3(b) shows the error rate of classification changes smoothly with increasing of α in Eq.11 from 0.0 to 1.0. After 0.1, it makes no big difference to the error rate of classification.
Effect of Symmetric Concatenation Table 4 shows the effectiveness of the symmetric concatenation used in Eq.7.  Effect of c in Eq.10 Table 5 shows the error rate on three different c settings. As is observed, c is insensitive to error rate. In our experiment, we set c to 1.1, since it obtains lower error rate in Val err and Test err.

Qualitative Evaluation
In Fig.4, we show four successful dialogues to visualize the guess process. We only plot 4 candidate objects for simplicity in each example. The colorful barcodes represent an initial guessing state π (0) on candidate objects, the detailed numbers represent the subsequent rounds of guessing state.
Taking Fig.4(a) as an example. For an image with several candidate objects (including a target object), Guesser has an initial uniform guess on all candidates, i.e. initial guessing state π (0) . QGen starts a dialogue by asking the first question is it a cow?, Oracle responses with yes. The guesser then updates its initial guessing state π (0) to π (1) , e.g., the probability on the ostrich and tree approaches to zero, while the cow on both sides increases to 0.45 and 0.51 respectively. The guessing state updates in this way as shown in Fig.4(s). As we can see, the probability of the cow on the right side keeps to raise with the process of the dialogue.

Conclusion
The paper proposes a novel guessing state tracking (GST) based model for guesser, which models guess as a process with change of guessing state, instead of making one and only one guess over the dialogue history in all the previous work. To make full use of the guessing state, two losses, i.e. early supervision loss and incremental supervision loss, are introduced. Experiments shows that our GST based guesser significantly outperforms all of the existing methods, and achieves a new strong state-of-the-art performance that is close to humans, the success rate of guessing 83.3% is approaching human-level performance 84.4%.