=Paper=
{{Paper
|id=Vol-1440/paper2
|storemode=property
|title=Interactive Search with Contextual Navigation Recommendations
|pdfUrl=https://ceur-ws.org/Vol-1440/Paper2.pdf
|volume=Vol-1440
|dblpUrl=https://dblp.org/rec/conf/ijcai/KonikMM15
}}
==Interactive Search with Contextual Navigation Recommendations==
https://ceur-ws.org/Vol-1440/Paper2.pdf
Interactive Search with Contextual Navigation Recommendations
Tolga Könik Yoni Medoff Rajyashree Mukherjee
eBay Inc. eBay Inc. eBay Inc.
San Jose, CA 95125 San Jose, CA 95125 San Jose, CA 95125
tkonik@ebay.com ymedoff@ebay.com rmukherjee @ebay.com
Abstract contain products with high seller supply and buyer demand.
This also helps the user avoid (or backtrack from) low result
We present an interactive search assistance agent
scenarios.
that integrates search and recommendation-based
Our design observes several principles:
experiences into a novel unified presentation. The • Interactive: Shopping/search should be a conversational
agent guides the user toward more desirable inven-
interaction between the user and shopping assistant.
tory, while also satisfying the constraints that the
• Mixed-initiative [3]: System and user take the initiative in
user constructs with the help of the agent. We built turns and the UI provides a mechanism for the two
a prototype which supports this mechanism by
agents to share information and align their goals.
connecting to the search functionality on eBay. We
• Incremental: The UI enables the user to make incremental
have also created the popularity knowledge-base of changes (refinement, pivoting, and generalization) to
the agent by aggregating data from billions of user
the query, and receive immediate feedback on how
transactions. The accompanying video1 demon-
those changes affect the results. This helps the user
strates the resulting prototype in this context. build a mental model of the inventory while navigating
through each part of the process.
1 Introduction • Shared narrow focus: The UI enables the user to focus on
Many popular applications that provide services like shop- a narrow context at a time (e.g. changing part of the
ping, search, media, and social networking, rely on infor- query), while the system keeps track of that focus and
mation retrieval (IR) technologies that can be broadly cate- provide contextual recommendations at every step.
gorized into two groups: Query-based systems that primari- Researchers often discuss personalization of search and
ly aim to satisfy user input (i.e. keyword search, filtering, recommendations in two distinct contexts: customization
and browsing) [1] and Recommender systems [2] that take with respect to long term user models, and adaptation to
an active role in recommending content without the need for short-term user actions. The mechanisms that we propose
direct user input. The lines between these two IR systems here belong to the latter category. However, we believe that
can blur; a keyword search system might customize its re- this system would benefit from long-term user models as
sults based on recent user behavior and a recommendation well, and so we pose that potential integration as an open
system could narrow its results to be consistent with recent question for future work.
search queries. However, these components typically func- We implemented a prototype of Focus and demonstrate
tion independently, and user interfaces emphasize certain its feasibility in the e-commerce domain. The system pow-
functionality based on the expected utility for the user. ers its recommendations with data aggregated from billions
Here, we present Focus, and interactive assistant for a of transactions on eBay. Next, we go through a motivating
shopping website, which blurs the lines between user query- example, followed by an overview of the runtime architec-
based search and system-initiated recommendations. Our ture and offline processes that build the system’s
proposal involves an intelligent system that unifies keyword knowledge-base.
search, category browsing, attribute filtering, query comple-
tion, related query recommendation, and popularity-based 2 User-Interface Interaction
recommendations.
The paper is accompanied by a video demonstrating the
Focus behaves similar to a search engine in that it returns
user-interface interaction1. In preparing a demo system we
results satisfying user queries and selected filters, while were forced to make certain UI design choices, but the
simultaneously acting like a recommendation engine in in-
claims and architectural commitments we make in this paper
troducing popular inventory. It can assist users by suggest-
are more abstract in nature and they should not be evaluated
ing refinements for narrowing a query and proposing chang- limited to this particular interface.
es to particular parts of a query in order to move the search
towards alternative directions. The latter functionality al-
lows the user to discover popular parts of inventory that 1
http://youtu.be/RgoLvGf96Bg
The user starts the interaction by typing an initial query to brand=Coach, style=Shoulder Bag, and category=Clothing
a search box, or by selecting a group of filters from the land- Shoes and Accessories by applying a named entity extrac-
ing page of the experience. This landing page is currently tion mechanism, which resolves ambiguities by considering
hand-curated but a natural extension would be to construct it co-occurrence frequencies in historical transactions. Next,
by determining popular clusters of items, or by personaliz- the system updates the interface with these filters and shows
ing it based on past experience of the user. Subsequently,
relevant results from the inventory. Using this information,
the system will respond by showing relevant results for the
selected set of filters and recommends potential changes to the system also recommends new attribute filters such as
the query. After every user action, the system retrieves new color and shoe size since those are filters that work well
results and updates its query recommendations. These rec- with the selected filters (in terms of increasing the likeli-
ommendations are incremental, targeting only the specific hood of retrieving desirable inventory). At this point, the
user selected parts of the query. user can click on one of these attributes (e.g. color) and get
At the heart of the communication between the user and an ordered list of recommended values that work well with
the IR system is a user interface that represents the query, the previous set of filters (Figure 1). In this example, brown
along with changes recommended by the system. This acts is at the top of that list because it is a popular color for
as shared knowledge between the user and the system, and coach shoulder bags.
helps to align their goals. This assisted search approach is
similar to widely used autocomplete functionality in rec-
ommending changes to a query, but it differs in two key
ways. First, the query is partitioned into named entities. Ad-
ditionally, recommended changes are incremental and can
target any selected segment of the query. This provides the
user with multiple directions for changing the query in in-
cremental fashion, resulting in a more interactive experi-
ence, which allows the user to navigate through the invento-
ry efficiently.
The user interface (Figure 1) consists of three elements:
search context (top two rows), which characterizes the cur-
rent query for information retrieval, recommendations for
changing the query (dark bar), which list the recommenda- Figure 2. Focus interface - pivoting
tions to lead the user towards popular parts of the inventory,
and a result set consisting of items that best match the The user can also select one of the existing filters and get
search context. alternative recommendations that work best with the current
search context (Figure 2). For a given selected filter, the
values are recommendations that lead the user towards pop-
ular parts of the inventory. Those recommendations are de-
termined dynamically based on past popular user activity
statistics, which we will describe in the next section. For
example, clicking on brand filter might retrieve the value
Vera Bradley as another popular brand, which also corre-
lates with shoulder bags. Similarly, clicking on style would
trigger recommendations for popular item styles for Coach,
including totes and messengers.
Finally, the user can continue typing new keyword que-
ries. During this process, the system may suggest autocom-
pleting the keyword (e.g. the partial query “bl” could trigger
Figure 1. Focus interface - refinement the filter selection color=black). This autocomplete mecha-
nism also prefers entries that work best with the current
The search context includes a keyword query and a set of search context, among the ones that match the partial query.
selected filters consisting of attribute name-value pairs. The
search context is constructed by user’s initiative but the rec- 3 Architecture
ommender system helps by suggesting new refinements and
possible changes to the existing query. Whenever the user Focus architecture is partitioned into data storage, runtime
changes the search context (either by direct editing or by system, and offline data generation (Figure 3). Next, we
selecting a system recommendation), the system updates the review these components and explain how they support the
search results that match that new context. functionality described in the previous section.
For example when the user enters the query “coach
shoulder bag,” the system recognizes the attributes
3.1 Runtime Performance System Candidate Sorting
The runtime system includes a number of services that re- Our goal is to estimate the conditional probability P(y | x)
representing the likelihood of the user finding desired items
spond to user actions. The interface state consists of search
in the result set, when filtering by a name-value pair y, given
context, query change recommendations, and search results.
The user actions change the search context and the runtime the selected name-value filters x = x1, x2… xn. For example,
given the selected filter vector x=,
performance system responds by changing the result set and
candidates for y may include constraints like color=white or
recommendations.
The runtime performance system consists of three main size=10. In that case, the recommendation engine would
need to determine whether color=white or size=10 is a bet-
components. First, the item retrieval system returns a set of
ter refinement. The algorithm merely sorts candidate instan-
items from the inventory that best match the search context.
Second, the attribute extraction service extracts a number of tiations for y by maximizing P(y | x) for a given x. We
achieve this by Naïve Bayesian inference, where we have:
attribute-value pairs from a keyword query. Finally, the
P(y | x) ~ P(x 1| y) P(x 2| y)… P(x n| y) P(y)
third service recommends changes on the query given the
search context. In this work, we are focusing only on the assuming conditional independence:
P(x i x j| y) = P(x i| y) P(x j| y)
third component that generates the recommendations and
Under that assumption, the order of P(y | x) for a fixed x
therefore we will not describe the remaining components in
more detail. depends only on P(xi| y) and P(y) values.
The query recommendations component consists of a Retrieval
number of services, which all utilize the same backend data The three recommendation services use the backend engine
storage and inference engine. The structured autocomplete differently, depending on how they select candidate values
service inputs the search context along with a partial key- of y. For efficient retrieval, all values are stored in a table
word query, and returns filter values that match the partial which has one row for each y instance and has columns ob-
keyword query, preferring popular filters that co-occur with serving the following schema:
selected filters in the search context in past transactions. The
attribute name refinement service returns most popular at- This table has O(n) columns and rows, where n is the num-
tribute names to be used for further filtering given selected ber of attribute-value pairs and in our domain. Moreover, we
filters. Finally, the attribute value selection service return assume that the matrix is sparsely populated, which is an
best values for a chosen filter given the selected filters in the assumption that holds in our shopping domain.
search context. All of these services use the same backend The typical goal is to return y names and/or values (the first
engine that stores information about popularity of attributes two columns), given the probability values. For a set of se-
and their interaction. lected context filters x =, all services retrieve
only y rows such that:
3.2 Backend Reasoning Engine P(x1| y) ≠ 0, P(x2| y) ≠ 0,…, P(xn| y) ≠ 0
All query recommendation services rely on the backend Given a sparse matrix, this significantly reduces the num-
reasoning engine. Each service uses this engine to retrieve ber of candidates and their retrieval becomes very efficient
candidate values and order them based on a single populari- with usual indexing.
ty metric. We will first describe this popularity metric and On top of the shared retrieval constraints above, the sug-
then we will discuss the retrieval process specific to each gestion services use additional constraints. In structured
service. autocomplete with the partial keyword query q, the system
enforces the additional constraint contains(name(y), q), e.g.
The Data Store Real-time Performance System
Inventory
Item retrieval Recommended items
User
Interface
Clickstream Filter Suggestion
Data Query
Service recommendations
Offline
Model Refinement
Structured Data
Generation
Alternatives query, selected filters
Attribute Autocomplete
Relevance
Figure 2. Architecture Overview.
the query “re” retrieves only aspects like color=red, where plicit and agreed representation of the shared context, and
the query is contained in the aspect value. On the other resolving ambiguities and determining which part of past
hand, in attribute value refinement, the name N of the attrib- dialog is relevant for the current query remains to be a diffi-
ute is given as input, we use the additional constraint cult challenge. Facebook graph search [6] was employing
name(y) = N, e.g. when the filter color is selected, all re- structured autocomplete until recently, where named entities
trieved y rows satisfy name(y)=“color”. The attribute name were recommended to complete user queries, but no method
recommendations are handled with a slight extension where is provided for changing parts of a query to reduce low re-
y represents only the attribute name (without value). This call. Pinterest’s search interface [7] represents query words
fits in our database with minor changes. as tokens, which can be individually deleted and recom-
mends refinement words incrementally but the tokenization
3.3 Offline Architecture does not seem to happen in terms of name-value pairs, and
The mechanism we defined in the previous section defines a there is no mechanism to change part of a query to alterna-
conditional probability metric P(xi| y), which we defined as tive values. At the time of submission, Bing researchers
the probability of selection of y (filter name or name-value described a similar search experience, which also includes
pair) to be useful for the user, given a selected attribute filter pivoting [8]. We find it quite encouraging and validating
xi, and P(y) the unconditional probability of selection of the that other teams have independently built systems motivated
filter y to be useful. However, we have not described how by similar ideas.
we can obtain those values in a practical use case.
If we have a system running in production, those values CONCLUSION
can be obtained based on usage of filters and the engage-
We presented an information retrieval experience for a
ment with their results. However, it is not clear how we
shopping domain that merges search and recommendations
should initialize such a system. In the shopping domain, in a novel way. The system facilitates an incremental
there are several alternatives that can be used as proxies to
mixed-initiative interaction between the user and a recom-
these probabilities, each resulting in different runtime be-
mender agent, which leads the user towards popular parts of
havior. One can use data from engagement with an existing the inventory, while also satisfying user queries. We imple-
(but static) filter system, or use inventory-based metrics (i.e.
mented a functioning prototype that utilizes data mined
how many items in inventory satisfy brand=nike and cate-
from billions of transactions on eBay and the backend algo-
gory=basketball shoes at a given time). Instead, we decided rithm is efficient and scalable.
to optimize our system for popularity. Hence, we calculate
We are at early stages of this work and lack crucial eval-
the P values by listing item view actions and counting co-
uation demonstrating the utility of this system. However, we
occurrence of attribute-value pairs (e.g. number of viewed believe that our contribution is a novel step towards more
items with attributes brand=nike and color=white). Conse-
intelligent interactive information retrieval systems and can
quently, the resulting system is biased towards preferring
encourage future research in this area.
items with higher rates of user interaction.
4 Evaluation References
Our results are quite preliminary, and we have not yet con- 1. Manning, C. D. and Raghavan, P. Introduction to Infor-
ducted a systematic user experiment. We implemented a mation Retrieval, Cambridge Press, USA, 2008.
prototype user interface (demonstrated in the accompanying 2. Jannach, D. and Zanker, M. Recommender Systems: An
video) powered by real user activity data. While this kind of Introduction, 2010.
interface could be useful for different computing environ-
ments, its strength is highlighted in touch screen devices, 3. Walker, M., and Whittaker, S. Mixed initiative in dia-
where selecting from suggestions is easier than typing, and logue: An investigation into discourse segmentation. Pro-
there is limited space for suggestions. ceedings of the 28th Meeting of the ACL, 1990, 70-78.
The backend data is automatically generated using bil- 4. Apache Solr. http://lucene.apache.org/solr/
lions of items viewed at eBay and it covers a large portion 5. Lison, P. and Meena, R. Spoken dialogue systems: the
of items in the inventory that contain attribute data. Our new frontier in human-computer interaction XRDS: Cross-
item retrieval service and concept extractor utilizes existing roads, The ACM Magazine for Students - Natural Lan-
services at eBay. We built the query recommendation ser- guage 21 1 (2014), 46-51.
vices from scratch and they utilize a Solr [4] database for
storing and accessing attribute relevance data efficiently. 6. Facebook. http://facebook.com
7. Pinterest. http://pinterest.com
Related Work 8. Bing – Type less, search images faster.
A related approach that is recently gaining importance is http://blogs.bing.com/search/2015/04/16/type-less-search-
conversational search like "Google Now," "Apple Siri," and images-faster/
“Microsoft Cortana,” [5] where the IR system also actively
interacts with the user, but in these systems there is no ex-