Underspecified Query Refinement via Natural Language Question Generation

Proceedings of COLING 2012: Technical Papers, pages 2341–2356, COLING 2012, Mumbai, December 2012. Underspecified Query Refinement via Natural Language Question Generation Hassan Sa j jad1 Patrick Pantel2 Michael Gamon2 (1) Qatar Computing Research Institute, Qatar Foundation, Doha, Qatar ∗ (2) Microsoft Research, Redmond, WA, USA ❤s❛❥❥❛❞❅q❢✳♦r❣✳q❛✱ ♣♣❛♥t❡❧❅♠✐❝r♦s♦❢t✳❝♦♠✱ ♠❣❛♠♦♥❅♠✐❝r♦s♦❢t✳❝♦♠ ABSTRACT Underspecified queries are common in vertical search engines, leading to large result sets that are difficult for users to navigate. In this paper, we show that we can automatically guide users to their target results by engaging them in a dialog consisting of well-formed binary questions mined from unstructured data. We propose a system that extracts candidate attribute-value question terms from unstructured descriptions of records in a database. These terms are then filtered using a Maximum Entropy classifier to identify those that are suitable for question formation given a user query. We then select question terms via a novel ranking function that aims to minimize the number of question turns necessary for a user to find her target result. We evaluate the quality of system-generated questions for grammaticality and refinement effectiveness. Our final system shows best results in effectiveness, percentage of well-formed questions, and percentage of answerable questions over three baseline systems. KEYWORDS: Query refinement, question generation, search as a dialog. ∗This work was conducted at Microsoft Research. 2341 1 Introduction Vertical search engines, i.e., domain-specific search engines, retrieve ranked entities from an underlying database, often via unstructured keyword queries. Popular engines, such as Yelp, Bing Travel, IMDB, and Amazon share a common aspect with niche engines, such as BlueWine and OpticsPlanet: user queries are often underspecified. Whether because of the seemingly infinite inventory in the larger engines, or because of the esoteric collections in niche engines, or simply because users seek to browse a collection of results, underspecification is pervasive. When the set of specified entities exceeds the common limit of ten blue links, finding the desired entity can be a long and frustrating process. For example, consider the query “blue polo with purple stripes" issued to the Bing Shopping engine. Pages of results are returned with correctly matching products. Browsing through these, especially in a mobile or handsfree scenario, can be prohibitively difficult. In most result sets, however, entities can form natural clusters based on important attributes. In our example, clusters can be formed based on price, designer, shirt patterns, etc. Some vertical search engines leverage such editorially defined clusters by forming a faceted search experience, where users can refine search results by selecting attribute values. Such experiences are expensive to build, require a heavily curated ontology to define the important attributes, and consequently are only feasible for large sites with significant revenue streams. In this paper, we explore methods to automatically discover important attributes from unstructured data associated with entities in a database. Further, in a runtime scenario, we propose algorithms for selecting the best candidate attribute to ask about, based on various criteria, and we construct a binary natural language question for the user to answer. The …

Content truncated to 500 words