WhittleSearch: Interactive Image Search with Relative Attribute Feedback

1 Introduction

• Users describe how an exemplar’s high-level properties should change toward their envisioned target, communicating what is missing rather than only labeling images relevant or irrelevant.Examples include asking for shoes to be more formal or a scene to be brighter or more urban.Source: §1 · p. 2
• Offline, WhittleSearch learns ranking functions for nameable attributes; at query time, it applies users’ comparative constraints to update relevance rankings and present new exemplars.The cycle continues until the top-ranked images are acceptably close to the target.Source: §1 · p. 2
• The user-initiated variant lets users choose which attributes to comment on among top-ranked reference images, while the active variant selects feedback intended to reduce relevance uncertainty.The first leaves the choice of feedback to the user; the second selects a specific exemplar and attribute.Source: §1 · p. 2
• Active WhittleSearch builds a binary search tree for each attribute, estimates the information gain of pivot comparisons, and updates relevance predictions after each response.An “equally” response ends exploration of that attribute tree.Source: §1 · p. 3
• Attribute search trees limit active selection to one image per attribute per iteration, reducing machine-side scanning and supporting a small number of well-chosen user interactions.The authors contrast this with prior information-gain methods that scan all database images at each iteration.Source: §1 · p. 3
• Across shoes, people, and scenes, WhittleSearch refines search more effectively than traditional binary feedback, often with less total user interaction.The authors also report that active reference-image selection compares favorably with conventional active methods and a simpler binary-search-tree baseline.Source: §1 · p. 3

2.1 Interactive feedback in image search

• Interactive image search adapts rankings from user feedback, but binary labels do not tell the system what makes one image more relevant; relative attributes specify that distinction.The authors argue that ordinal comparisons also permit sequential exemplar selection, with each comparison predicted to reduce the relevance of half the unexplored images.Source: §2.1 · pp. 3–4

2.2 Active testing and “20 questions” labeling

• Unlike active testing, which selects questions to classify one novel image, Active WhittleSearch selects visual comparisons to reduce relevance uncertainty across a database of images.Related active-testing work includes human responses to intermediate labels and similarity comparisons (Branson et al, 2010; Wah et al, 2014).Source: §2.2 · p. 4

2.3 Attributes for image search

• Prior work uses semantic attributes for retrieval, but this paper uses relative attributes as a feedback channel and extends relative-attribute learning to human-generated exemplar comparisons.The manuscript brings together the authors’ earlier work, compares user- and system-initiated feedback, and adds experimental comparisons and qualitative results.Source: §2.3 · pp. 4–5

2.4 Attributes for recognition

• Although attributes also support recognition tasks such as zero-shot learning and object description, this work selects exemplars for image search rather than classifiers or attribute labels for recognition.The authors distinguish active exemplar selection and visual comparisons from prior requests for attribute labels.Source: §2.4 · p. 5

3.1 Learning to Predict Relative Attributes

• For each given attribute vocabulary, WhittleSearch trains one-time image-level rankers from consensus pairwise judgments, capturing within-category variation that category comparisons misrepresent (23% smiling-relationship violations).The rankers predict attribute strength in novel images; image-level supervision matters because a person can exhibit an attribute to different degrees across photos.Source: §3.1 · pp. 5–6

3.2 Relative Attribute Feedback

• Relative statements about whether a target has more, less, or equally of an attribute than a reference image carve away irrelevant regions and update probabilistic relevance rankings.The system ranks database images by their probability of relevance given image content and accumulated feedback, accounting for imperfect predicted attribute strengths; relative feedback can refine descriptions across result rounds and convey attribute-specific information beyond binary labels.Source: §3.2 · p. 7

3.3 Hybrid Feedback Approach

• The hybrid approach learns a large-margin ranking function that places relevant images above irrelevant ones and images satisfying more relative constraints above those satisfying fewer.It weights binary-feedback pairs inversely to their fraction of the combined pair set to balance the more numerous relative-attribute pairs.Source: §3.3 · p. 8

3.4 Active WhittleSearch with Attribute Pivots

• Active WhittleSearch asks whether the target has more, less, or equally of an attribute than an exemplar, selecting comparisons for expected maximal information gain.It uses a small set of attribute-tree pivot exemplars rather than exhaustively considering every database image, and outputs images sorted by predicted relevance.Source: §3.4 · p. 9

3.4.1 Attribute Binary Search Trees

• For each attribute, an offline binary search tree recursively partitions database images into balanced sets using median-valued images as pivots.The pivots restrict candidate comparisons, while probabilistic constraint satisfaction avoids error-prone hard pruning when predicted strengths differ from users’ perceptions and accounts for varying information gain.Source: §3.4.1 · p. 9

3.4.2 Actively Selecting an Informative Comparison

• At each round, active selection chooses the current attribute pivot expected to minimize total relevance entropy after the user’s possible response.The ALL RELEVANT response-likelihood strategy uses currently relevant database images as a proxy for which responses the user is likely to give.Source: §3.4.2 · pp. 9–10
• SIMILAR QUESTION reuses the answer to the most similar prior question, based on pivot-image descriptor distance and Kendall’s τ correlation between attribute rankings.MOST RELEVANT instead uses the current best-guess target image as its proxy; the paper evaluates all three likelihood strategies.Source: §3.4.2 · p. 10
• At each iteration, Active WhittleSearch requests a comparison for the selected pivot, updates feedback constraints, and moves that attribute’s tree pointer or stops its exploration after an “equally” response.The process ends when the user is satisfied with the top results or all attribute trees have bottomed out.Source: §3.4.2 · p. 10, Figure 5 · p. 10
• Active selection costs O(MN) per feedback round, compared with O(MN^2) for traditional information gain, because binary search trees exploit ordinal relative-attribute values.Here M is the attribute vocabulary size and N is the database size, with M ≪ N.Source: §3.4.2 · pp. 10–11

3.5 Discussion

• Active WhittleSearch selects feedback according to the system’s knowledge, but its reference images may be disjoint from top-ranked results, requiring users to examine both sets.Source: §3.5 · p. 11
• WhittleSearch lets users choose reference images and attributes, but its performance depends on their choices and response accuracy, and each feedback statement takes longer to complete.The qualitative comparisons illustrate user-chosen feedback that misses distinctive target features and feedback that is particularly valuable.Source: §3.5 · p. 11
• Active WhittleSearch may suit users who want to avoid choosing feedback or have a specific target, while WhittleSearch may suit careful users or those browsing with vague preferences.A mismatch between human and system attribute perceptions can make Active WhittleSearch’s entropy estimates inaccurate; small screens may also favor eliminating user choice.Source: §3.5 · p. 11
• Active WhittleSearch is expected to have its strongest advantage in the first few iterations, when entropy-based selection is most crucial.Source: §3.5 · p. 11

4.1 Experimental Design

• The evaluation used random target images, target percentile rank, and NDCG@50 against human-judgment-based relevance rankings, with binary SVM feedback as the key baseline.The ground-truth ranking was learned from 750 image triplets per dataset judged by seven Mechanical Turk subjects; the datasets cover Shoes, Faces, and Scenes.Source: §4.1 · pp. 12–13

4.2 WhittleSearch Results

• Relative-attribute feedback outperformed binary feedback on all three datasets and often reached a top target rank faster.The advantage was slight on Faces but stronger on Shoes and Scenes; searches tended to stabilize after 2–10 feedback rounds, with similar runtimes for both methods.Source: Figure 8 · p. 14, §4.2 · p. 14
• More feedback improved both methods, but attribute feedback yielded higher accuracy per constraint and performed well with near or near-plus-far reference images.The reference-image comparison used 100 queries and automatically generated feedback; the prose reports that both methods generally did well with near-plus-far references and attribute feedback also did fairly well with near references.Source: Figure 9 · p. 14, §4.2 · pp. 14–15, Table 1 · p. 14
• Human-generated attribute feedback largely outperformed binary feedback, retaining an advantage after keyword initialization with fewer feedback statements.The human-feedback comparison used 16 queries per dataset and eight statements; the keyword-initialized Shoes comparison used 16 queries and four statements per method.Source: Figure 10 · p. 15, §4.2 · p. 15
• Relative feedback can bound acceptable attribute strengths precisely, while hybrid feedback combines attribute and binary input when either alone may miss the search goal.In one example, attribute-guided results matched the user's descriptions but missed the correct person; binary feedback succeeded at that goal, motivating the complementary hybrid approach.Source: §4.2 · pp. 15–16
• Instance-level relative-attribute supervision outperformed class-level supervision on Shoes and Scenes, where categories are more fluid.Inter-subject disagreement was 6% for instance-level responses versus 13% for category-level responses.Source: Table 2 · p. 16, §4.2 · p. 16

4.3 Active WhittleSearch Results

• Active WhittleSearch was set up for comparison with attribute-selection and binary-feedback alternatives, including exhaustive entropy-based selection, top-result selection, and random passive selection.The active binary baseline selected an image whose SVM decision value was closest to zero; passive binary feedback selected images randomly.Source: §4.3 · p. 18
• MOST RELEVANT performed consistently well across datasets and beat the other likelihood models except on Scenes, so the authors use it in the remaining experiments.SIMILAR QUESTION performed best for some iterations on Scenes but poorly on Faces; the authors attribute this to the difficulty of estimating attribute similarity for distinct facial attributes.Source: Figure 15 · p. 19, §4.3 · p. 19
• Active WhittleSearch improves average percentile rank over ATTRIBUTE PIVOTS by 7.6% after 3 iterations and reaches the top 40 in 12, 10, and 4 iterations for Shoes, Scenes, and Faces, versus TOP’s 21, 21, and 9.The authors report that this saves users up to 70 seconds per query.Source: Figure 16 · p. 19, §4.3 · pp. 19–20
• Relative attribute methods quickly surpass binary feedback after its initial advantage, with similar feedback times of 6.4 seconds versus 5.5 seconds; relative feedback also outperforms TOP.PASSIVE BINARY FEEDBACK performs better than its active counterpart in these experiments.Source: Figure 16 · p. 19, §4.3 · p. 19
• The tree-based active method is orders of magnitude faster than ACTIVE ATTRIBUTE EXHAUSTIVE, while hard pruning incorrectly eliminates the true target for about 93% of queries.The authors describe the binary trees as regularization that focuses questions on informative comparisons and reduces the risk of selecting uninformative outliers.Source: Table 3 · p. 19, §4.3 · p. 19
• In live user tests, Active WhittleSearch typically ranked targets better than the baselines and found a very similar Shoes-1k image in 1.9 iterations, versus 2.4 for ATTRIBUTE PIVOTS and 3.15 for TOP.The authors note that the live experiment required real-time decisions, which the exhaustive active method could not provide.Source: Figure 18 · p. 20, §4.3 · p. 20

4.4 Comparing WhittleSearch and Active WhittleSearch

• Active WhittleSearch reduced system entropy faster than WhittleSearch after two iterations, but WhittleSearch achieved better ranks and became preferable when result-page examination time dominated feedback time.Active WhittleSearch was cheaper in user feedback time, while WhittleSearch’s greater freedom to choose feedback options required more time.Source: Figure 20 · p. 22, §4.4 · p. 22
• Users reported greater confidence in WhittleSearch responses, while Active WhittleSearch did better in the query where all five workers agreed on every response.The authors suggest incorporating a user-confidence model so active feedback can select informative questions that users are likely to answer confidently.Source: Figure 20 · p. 22, §4.4 · pp. 22–23

• Compared with existing active and passive methods, the pivot-based formulation is more efficient by orders of magnitude and more accurate in practice.Source: §5 · p. 23
• Experiments on three diverse datasets show promise for relative-attribute feedback, with well-chosen comparative queries rapidly pinpointing the visual target.Source: §5 · p. 23
• Future work includes modeling uncertainty, encouraging diverse and manageable questions, transferring control between user and system, and learning new attributes during search.The authors also plan to explore greater search diversity and different weights for feedback on different attributes.Source: §5 · p. 23

• Table 4 scores Shoes dataset classes from 1 (least) to 10 (most) for each attribute.Source: Table 4 · p. 26