Dialog-based Interactive Image Retrieval

Introduction

The volume of searchable visual media has grown tremendously in recent years, and has intensified the need for retrieval systems that can more effectively identify relevant information, with applications in domains such as e-commerce , surveillance , and Internet search . Despite significant progress made with deep learning based methods , achieving high performance in such retrieval systems remains a challenge, due to the well-known semantic gap between feature representations and high-level semantic concepts, as well as the difficulty of fully understanding the user’s search intent.

A typical approach to improve search efficacy is to allow the user a constrained set of possible interactions with the system . In particular, the user provides iterative feedback about retrieved objects, so that the system can refine the results, allowing the user and system to engage in a “conversation” to resolve what the user wants to retrieve. For example, as shown in Figure 1, feedback about relevance allows users to indicate which images are “similar” or “dissimilar” to the desired image, and relative attribute feedback allows the comparison of the desired image with candidate images based on a fixed set of attributes. While these feedback paradigms are effective, the restrictions on the specific form of user interaction largely constrain the information that a user can convey to benefit the retrieval process.

In this work, we propose a new approach to interactive visual content retrieval by introducing a novel form of user feedback based on natural language. This enables users to directly express, in natural language, the most prominent conceptual differences between the preferred search object and the already retrieved content, which permits a more natural human-computer interaction. We formulate the task as a reinforcement learning (RL) problem, where the system directly optimizes the rank of the target object, which is a non-differentiable objective.

We apply this RL based interactive retrieval framework to the task of image retrieval, which we call dialog-based interactive image retrieval to emphasize its capability in aggregating history information compared to existing single turn approaches . In particular, a novel end-to-end dialog manager architecture is proposed, which takes natural language responses as user input, and delivers retrieved images as output. To mitigate the cumbersome and costly process of collecting and annotating human-machine dialogs as the system learns, we utilize a model-based RL approach by training a user simulator based on a corpus of human-written relative descriptions. Specifically, to emulate a single dialog turn, where the user provides feedback regarding a candidate image relative to what the user has in mind, the user simulator generates a relative caption describing the differences between the candidate image and the user’s desired image.In this work, the user simulator is trained on single-turn data and does not consider the dialog history. This reduces the sequence of responses to a “bag” of responses and implies that all sequences of a given set of actions (candidate images) are equivalent. Nevertheless, while the set of candidate images that maximize future reward (target image rank) are a set, selecting the image for the next turn naturally hinges on all previous feedback from the user. Therefore, the entire set of candidate images can be efficiently constructed sequentially. Whereas there is a lot of prior work in image captioning , we explore the problem of relative image captioning, a general approach to more expressive and natural communication of relative preferences to machines, and to use it as part of a user simulator to train a dialog system.

The efficacy of our approach is evaluated in a real-world application scenario of interactive footwear retrieval. Experimental results with both real and simulated users show that the proposed reinforcement learning framework achieves better retrieval performance than existing techniques. Particularly, we observe that feedback based on natural language is more effective than feedback based on pre-defined relative attributes by a large margin. Furthermore, the proposed RL training framework of directly optimizing the rank of the target image shows promising results and outperforms the supervised learning approach which is based on the triplet loss objective. The main contributions of this work are as follows:

A new vision/NLP task and machine learning problem setting for interactive visual content search, where the dialog agent learns to interact with a human user over the course of several dialog turns, and the user gives feedback in natural language.

A novel end-to-end deep dialog manager architecture, which addresses the above problem setting in the context of image retrieval. The network is trained based on an efficient policy optimization strategy, employing triplet loss and model-based policy improvement .

The introduction of a computer vision task, relative image captioning, where the generated captions describe the salient visual differences between two images, which is distinct from and complementary to context-aware discriminative image captioning, where the absolute attributes of one image that discriminate it from another are described .

The contribution of a new dataset, which supports further research on the task of relative image captioning. The project website is at: www.spacewu.com/posts/fashion-retrieval/

Related Work

Methods for improving image search results based on user interaction have been studied for more than 20 years . Relevance feedback is perhaps the most popular approach, with user input specified either as binary feedback (“relevant” or “irrelevant”) or based on multiple relevance levels . More recently, relative attributes (e.g., “more formal than these,” “shinier than these”) have been exploited as a richer form of feedback for interactive image retrieval . All these methods rely on a fixed, pre-defined set of attributes, whereas our method relies on feedback based on natural language, providing more flexible and more precise descriptions of the items to be searched. Further, our approach offers an end-to-end training mechanism which facilitates deployment of the system in other domains, without requiring the explicit effort of building a new vocabulary of attributes.

Significant progress has been recently made on methods that lie in the intersection of computer vision and natural language processing, such as image captioning , visual question-answering , visual-semantic embeddings , and grounding phrases in image regions . In particular, our work is related to image or video retrieval methods based on natural language queries . These methods, however, retrieve images and videos in a single turn, whereas our proposed approach aggregates history information from dialog-based feedback and iteratively provides more refined results.

Building conversational agents that can hold meaningful dialogs with humans has been a long-standing goal of Artificial Intelligence. Early systems were generally designed based on rule-based and slot-filling techniques , whereas modern approaches have focused on end-to-end training, leveraging the success of encoder-decoder architectures and sequence-to-sequence learning . Our work falls into the class of visually-grounded dialog systems . Das et al proposed the task of visual dialog, where the system has to answer questions about images based on a previous dialog history. De Vries et al. introduced the GuessWhat game, where a series of questions are asked to pinpoint a specific object in an image, with restricted answers consisting of yes/no/NA. The image guessing game demonstrated emergence of grounded language and communication among visual dialog agents with no human supervision, using RL to train the agents in a goal-driven dialog setting. However, these dialogs are purely text-based for both the questioner and answerer agents, whereas we address the interactive image retrieval problem, with an agent presenting images to the user to seek feedback in natural language.

Method

Given the feature representation of all images from the retrieval database, $\{x_{i}^{\textrm{im}}\}_{i=0}^{N}$, where $x_{i}^{\textrm{im}}=\textrm{ImgEnc}(I_{i})$, we can compute a sampling probability based on the distances between the history representation $s_{t}$ to each image feature, $x_{i}^{\textrm{im}}$. Specifically, the sampling probability is modeled using a softmax distribution over the top-$K$ nearest neighbors of $s_{t}$: $\mathbf{\pi}(j)=e^{-{d_{j}}}/\sum_{k=1}^{K}e^{-{d_{k}}},j=1,2,...,K$, where $d_{k}$ is the $L2$ distance of $s_{t}$ to its $k$-th nearest neighbor in $\{x_{i}^{\textrm{im}}\}_{i=0}^{N}$. Given the sampling distribution, two approaches can be taken to sample the candidate image, denoted as $a_{t+1}=I_{j^{\prime}}$: (1) stochastic approach (used at training time), where $j^{\prime}\sim\mathbf{\pi}$, and (2) greedy approach (used at inference time), where $j^{\prime}=\arg\max_{j}(\pi_{j})$. Combining the three components of the model architecture, the overall learnable parameters of the dialog manager model is $\theta=\{\theta_{r},\theta_{s}\}$. Next, we explain how the network is trained end-to-end.

2 Training the Dialog Manager

Training an RL model for this problem requires extensive exploration of the action space, which is only feasible if a large amount of training data is available. However, collecting and annotating human-machine dialog data for our task is expensive. This problem is exacerbated in the situation of natural language based user feedback, which incurs an even larger exploration space as compared to approaches based on a fixed set of attributes. In text-based dialog systems, it is common to circumvent this issue by relying on user simulators . We adopt a similar strategy, where a user simulator, trained on human-written relative descriptions, substitutes the role of a real user in training the dialog manager (illustrated in Figure 3a). Below we further describe our user simulator, as well as the reinforcement learning techniques that we used to optimize our dialog manager.

Here we propose the use of a relative captioner to simulate the user. It acts as a surrogate for real human users by automatically generating sentences that can describe the prominent visual differences between any pair of target and candidate images. We note that at each turn, our user simulator generates feedback independent of previous user feedback, and previously retrieved images. While more sophisticated models that consider the dialog history could potentially be beneficial, training such systems well may require orders of magnitude more annotated data. In addition, back-referencing in dialogs can inherently be ambiguous and complex to resolve, even for humans. Based on these considerations, we decided to first investigate the use of a single-turn simulator. While a few related tasks have been studied previously, such as context-aware image captioning and referring expression generation , to the best of our knowledge, there is no existing dataset directly supporting this task, so we introduce a new dataset as described in Section 4.

We experimented with several different ways of combining the visual features of the target and retrieved images. We include a comprehensive study of different models for the user simulator in Appendix C and show that the relative captioner based user model serves as a reasonable proxy for real users. Specifically, we used feature concatenation to fuse the image features of the target and the reference image pair and applied the model of Show, Attend, and Tell to generate the relative captions using a long short-term memory network (LSTM). For image feature extraction, we adopted the architecture of ResNet101 pre-trained on ImageNet; and to better capture the localized visual differences, we added a visual attention mechanism; the loss function of the relative captioner is the sum of the negative log likelihood of the correct words .

2.2 Policy Learning

When the network parameters are randomly initialized at the beginning, the history representations $s_{t}$ are nearly random. To facilitate efficient exploration during RL training, we first pre-train the policy using a supervised learning objective. While maximum likelihood-based pre-training is more common, here we pre-train using the more discriminative triplet loss objective:

where $x^{+}$ and $x^{-}$ are the image features of the target image and a random image sampled from the retrieval database respectively, m is a constant for the margin and $\|.\|_{2}$ denotes $L2$-norm. Intuitively, by ensuring the proximity of the target image and the images returned by the system, the rank of the target image can be improved without costly policy search from random initialization. However, entirely relying on this supervised learning objective deviates from our main learning objective, since the triplet loss objective does not jointly optimize the set of candidate images to maximize expected future reward. More explanation on the difference between the two objectives is provided in Appendix E.

Compared to traditional policy gradient methods, the model-based policy improvement gradients have lower variance, and converge faster. In Section 5, we further demonstrated the effectiveness of model-based policy improvement by comparing it with a recent policy gradient method. Figure 3b illustrates our policy learning method as described above.

Dataset: Relative Captioning

Our user simulator aims to capture the rich and flexible language describing visual differences of any given image pair. The relative captioning dataset thus needs this property. We situated the data collection procedure in a scenario of a shopping chatting session between a shopping assistant and a customer. The annotator was asked to take the role of the customer and provide a natural expression to inform the shopping assistant about the desired product item. To promote more regular, specific, and relative user feedback, we provided a sentence prefix for the annotator to complete when composing their response to a retrieved image. Otherwise the annotator response is completely free-form: no other constraints on the response were imposed. We used Amazon Mechanical Turk to crowdsource the relative expressions. After manually removing erroneous annotations, we collected in total $10,751$ captions, with one caption per pair of images.

Interestingly, we observed that when the target image and the reference image are sufficiently different, users often directly describe the visual appearance of the target image, rather than using relative expressions (c.f. fourth example in Figure 7(b), Appendix A). This behavior mirrors the discriminative captioning problem considered in , where a method must take in two images and produce a caption that refers only to one of them. Relative and discriminative captioning are complementary, and in practice, both strategies are used, and so we augmented our dataset by pairing 3600 captions that were discriminative with additional dissimilar images. Our captioner and dialog-based interactive retriever are thus trained on both discriminative and relative captions, so as to be respectively more representative of and responsive to real users. Additional details about the dataset collection procedure and the analysis on dataset statistics are included in Appendix A and Appendix B.

Experimental Results

In Section 5.1, we assess the contribution of each component of our pipeline for policy learning. To evaluate the value of using free-form dialog feedback, we show experiments considering both simulated user feedback (Section 5.2) and real-world user feedback (Section 5.3).

All experiments were performed on the Shoes dataset , with the same training and testing data split for all retrieval methods and for training the user simulator. $10,000$ database images were used during training, and $4,658$ images for testing. The retrieval models are tested by retrieving images on the testing set, starting from a randomly selected candidate image for the first dialog turn. Image retrieval performance is quantified by the average rank percentile of the image returned by the dialog manager on the test set. For details on architectural configurations, parameter settings, baseline implementation, please refer to Appendix D.

We use our proposed user simulator to generate data and provide extensive quantitative analysis on the contribution of each model component.

Figure 5 provides examples of simulator generated feedback and the collected user annotations. An interesting observation is that even though the user simulator only occasionally generates descriptions that exactly match the human annotations (the third example in Figure 5), it can still summarize the main visual differences between the images, since inherently there are many ways to describe differences between two images. Qualitative examination of the generated relative expressions showed that the user simulator can approximate feedback of real users at a very low annotation cost (more analysis is included in Appendix C).

To investigate how retrieval performance is affected by each component of the dialog manager, we compare our approach, denoted as Ours, against two variants: (1) SL: supervised learning where the agent is trained only with triplet loss; (2) RL-SCST: policy learning using Self-Critical Sequence Training (SCST) after pre-training the network using the triplet loss objective. As shown in Figure 4 (solid lines), the average ranking percentile of the target image in all methods increases monotonically as the number of dialog turns increases. Both RL-based retrieval algorithms outperform the supervised pre-training, SL, which is expected since the triplet loss function does not directly optimize the retrieval ranking objective. Finally, Ours achieves $98\%$ average ranking percentile with only two dialog turns and consistently outperforms RL-SCST across different dialog turns, which demonstrates the benefit of the model-based policy improvement component. We have observed similar results on the attribute-based baselines. Each of the SL based attribute model underperforms its RL version by $\sim 1\%$ in retrieval ranking percentile.

2 Effectiveness of Natural Language Feedback

In this section, we empirically evaluate the effect of natural language feedback, compared to pre-defined, relative attribute-based user feedback.

Generating Attribute Feedback. Each image in the dataset maps to a $10$-D attribute vector, as described in . We adopted a rule-based feedback generator which concatenates the respective attribute words with “more” or “less”, depending on the relative attribute values of a given image pair. For example, if the “shiny” value of the candidate image and the target image are $0.9$ and $1.0$ respectively, then the rule-based feedback is “more shiny.” Attributes are randomly sampled, similar to the relative attribute feedback generation in . To simulate the scenario when users provide feedbacks using multiple attributes, individual attribute phrases are combined. We adopted original attribute values in , which were predicted using hand-crafted image features, as well as attribute values predicted using deep neural networks in .

3 User Study of Dialog-based Image Retrieval

In this section, we demonstrate the practical use of our system with real users. We compare with an existing method, WhittleSearch , on the task of interactive footwear retrieval. WhittleSearch represents images as feature vectors in a pre-defined $10$-D attribute space, and iteratively refines retrieval by incorporating the user’s relative feedback on attributes to narrow down the search space of the target image. For each method, we collected $50$ five-turn dialogs; at each turn, one image is presented to the user to seek feedback. For WhittleSearch, the user can choose to use any amount of attributes to provide relative feedback on during each interaction. The resulting average ranking percentile of the dialog manager and WhittleSearch are $89.9\%$ and $70.3\%$ respectively. In addition to improved retrieval accuracy, users also reported that providing dialog-based feedback is more natural compared to selecting the most relevant attributes from a pre-defined list.

Figure 6 shows examples of retrieval dialogs from real users (please refer to Appendix E for more results and discussions). We note that users often start the dialog with a coarse description of the main visual features (color, category) of the target. As the dialog progresses, users give more specific feedback on fine-grained visual differences. The benefit of free-form dialog can be seen from the flexible usage of rich attribute words (“leopard print on straps”), as well as relative phrases (“thinner”, “higher heel”). Overall, these results show that the proposed framework for the dialog manager exhibits promising behavior on generalizing to real-world applications.

Conclusions

This paper introduced a novel and practical task residing at the intersection of computer vision and language understanding: dialog-based interactive image retrieval. Ultimately, techniques that are successful on such tasks will form the basis for the high fidelity, multi-modal, intelligent conversational systems of the future, and thus represent important milestones in this quest. We demonstrated the value of the proposed learning architecture on the application of interactive fashion footwear retrieval. Our approach, enabling users to provide natural language feedback, significantly outperforms traditional methods relying on a pre-defined vocabulary of relative attributes, while offering more natural communication. As future work, we plan to leverage side information, such as textual descriptions associated with images of product items, and to develop user models that are conditioned on dialog histories, enabling more realistic interactions. We are also optimistic that our approach for image retrieval can be extended to other media types such as audio, video, and e-books, given the performance of deep learning on tasks such as speech recognition, machine translation, and activity recognition.

Acknowledgement. We would like to give special thanks to Professor Kristen Grauman for helpful discussions.

References

Appendix A Data Collection

In the following, we explain the details on how we collected the relative captioning dataset for training the user simulator and provide insights on the dataset properties. Unlike existing datasets which aim to capture the visual differences purely using “more" or “less" relations on visual attributes , we want to collect data which captures comparative visual differences that are hard to describe merely using a pre-defined set of attributes. As shown in Figure 8, we designed the data collection interface in the context of fashion footwear retrieval, where a conversational shopping assistant interacts with a customer and whose goal is to efficiently retrieve and present the product that matches the user’s mental image of the desired item.

Collecting Relative Expressions. The desired annotation for relative captioning should be free-form and introduce minimum constraints on how a user might construct the feedback sentence. On the other hand, we want the collected feedback to be concise and relevant for retrieval and avoid casual and non-informative phrases (such as “thank you", “oh, well"). Bearing the two goals in mind, we designed a data collection interface as shown in Figure 8, which provided the beginning phrase of the user’s response (“Unlike the provided …”) and the annotators only needed to complete the sentence by giving an informative relative expression. This way, we can achieve a balance between sufficient lexical flexibility and avoiding irrelevant and casual phrases. After manual data cleaning, we are left with $10,751$ relative expressions with one annotation per image pair.

Augmenting Dataset with Single-Image Captions. During our data collection procedure for relative expressions, we observed that when the target image and the reference image are visually distinct (fourth example in Figure 7(b)), users often only implicitly use the reference image by directly describing the visual appearance of the target image. Inspired by this, we asked annotators to give direct descriptions on $3600$ images without the use of reference images. We then paired each image in this set with multiple visually distinct reference images (selected using deep feature similarity). This data augmentation procedure further boosted the size of our dataset at a relatively low annotation cost.

Appendix B Dataset analysis

Figure 7(a) shows the length distribution of the collected captions. Most captions are very concise (between 4 to 8 words), yet composing a large body of highly rich vocabularies as shown in Figure 9 A few high-frequency words are removed from this chart, including ”has/have”, ”is/are”, ”a”, ”with”. . Interestingly, although annotators have the freedom to give feedback in terms of comparison on a single visual attribute (such as “is darker", “is more formal"), most feedback expressions consist of compositions of multiple phrases that often include spatial or structural details (Table 1).

Examples of the collected relative expressions are shown in Figure 7(b). We observed that, in some cases, users apply a concise phrase to describe the key visual difference (first example); but most often, users adopt more complicated phrases (second and third examples). The benefit of using free-form feedback can be seen in the second example: when the two shoes are exactly the same on most attributes (white color, flat heeled, clog shoes), the user resorts to using composition of a fine-grained visual attribute (“holes") with spatial reference (“on the top"). Without free-form dialog based feedback, this intricate visual difference would be hard to convey.

Appendix C Human Evaluation of Relative Captioning Results

We tested a variety of relative captioning models based on different choices of feature fusion and the use of attention mechanism. Specifically, we tested one Show and Tell based model, RC-FC (using concatenated deep features as input), and three Show, Attend and Tell based models, including RC-FCA (feature concatenation), RC-LNA (feature fusion using a linear layer) and RC-CNA (feature fusion using a convolutional layer). For all methods, we adopted the architecture of ResNet101 pre-trained on ImageNet to extract deep feature representation.

We report several common quantitative metrics to compare the quality of generated captions in Table 2. Given the intrinsic flexibility in describing visual differences between two images, and the lack of comprehensive variations of human annotations for each pair of images, we found that common image captioning metrics does not provide reliable evaluation of the actual quality of the generated captions. Therefore, to better evaluate the caption quality, we directly conducted human evaluation, following the same rating scheme used in . We collected user ratings on relative captions generated by each model and those provided by humans on $1000$ image pairs. Both quantitative results and human evaluation (Figure 10) suggest that all relative captioning models produced similar performance with RC-CNA exhibiting marginally better performance. It is also noticeable that there is a gap between human provided descriptions and all automatically generated captions, and we observed some captions with incorrect attribute descriptions or are not entirely sensible to humans, as shown in Figure 11. This indicates the inherent complexity of task of relative image captioning and room for improvement of the user simulator, which will lead to more robust and generalizable dialog agents.

Appendix D Experimental Configurations

Since no official training and testing data split was reported on Shoes dataset, we randomly selected $10,000$ images as the training set, and the rest $4,658$ images as the held-out testing set. The user simulator adopts the same training and testing data split as our dialog manager: it was trained using image pairs sampled from the training set with no overlap with the testing images. Since the four models for relative image captioning produced similar qualitative results in the user study, we selected RC-FCA model as our user simulator since it leads to more efficient training time for the dialog manager than the RC-CNA model. The baseline method, RL-SCST, uses the same network architecture and the same supervised pre-training step as our dialog manager and also utilizes the user simulator for training. The idea of RL-SCST is to use test-time inference reward as the baseline for policy gradient learning by encouraging policies performing above the baseline while suppressing policies under-performing the baseline. Given the trained user simulator, we can easily compute the test-time rewards for RL-SCST by greedy decoding rather than stochastically sampling the image to return at each dialog turn.

For all methods, the embedding dimensionality of the feature space is set to $D=256$; the MLP layer of the image encoder is finetuned using the single image captions to better capture the domain-specific image features. For SL training, we used the ADAM optimizer with an initial learning rate of $0.001$ and the margin parameter $m$ is set to $0.1$. For all reinforcement learning based methods, we employed the RMSprop optimizer with an initial learning rate of $10^{-5}$, and the discount factor is set to $1$. For our dialog manager, we set the number of nearest neighbors as $3$ for the Candidate Generator.

Appendix E Discussions on the Dialog Manager

In this section, we provide more discussions on the proposed dialog manager framework and point out a few directions for improvement.

Figure 12 shows more examples of the dialog interactions on human users. In all examples, the target image reached a final ranking within the top $100$ images (about $97\%$ in ranking percentile) within five dialog turns. These examples indicate that, visible improvement of retrieval results often comes from a flexible combination of direct reference to distinctive visual attributes of the target image, and comparison to the candidate image based on relative attributes. Ideally, feedback based on a pre-defined attribute set can achieve similar performance if the attribute vocabulary is sufficiently comprehensive and descriptive (which often consists of hundreds of words as in our footwear retrieval application). But in practice, it is infeasible to ask the user to scroll through a list of hundreds of attribute words and select the optimal one to provide feedback on.

Further, we observe that the system tends to be less responsive to certain low-frequency words generated by the use simulator (such as “slouchy” in the third example). This is as expected, since the dialog manager is trained on the user simulator, which in itself has limitations (such as the fixed size of vocabulary after being trained, and the lack of memory for dialog history). We are interested in finetuning the dialog manager on real users, so that it can directly adapt to new vocabularies from the user. In summary, results on real users demonstrated that free-form dialog feedback is able to capture various types of visual differences with great lexical flexibility and can potentially result in valuable applications in real-world image retrieval systems.

Dialog Manager Learning Framework. One main advantage of the proposed RL based framework is to train the agent end-to-end with a non-differentiable objective function (the target image rank). While triplet loss based objective makes it efficient to pre-train the dialog manager, it still deviates from the ranking objective. As illustrated in Figure 13: two examples exhibit similar triplet loss objectives, but the target image ranks differ greatly.

We noticed that the dialog manager based on the current learning architecture sometimes forgets information from past turns. For example, in the second example of Figure 12, the second turn imposes a “yellow accents” requirement to the target image. While this feedback is reflected in the immediate next turn, it is missing from the later turns of the dialog. We think that model architectures which better incorporates the dialog history is able to alleviate this issue. We could in principle investigate more variations of the network design to further improve its performance. Overall, the proposed network architecture is effective in demonstrating the applicability of dialog-based interactive image retrieval.