US 11,106,690 B1Granted

Neural query auto-correction and completion

AssigneeA9.com, Inc.

InventorsInderjit Dhillon, Vijai Mohan, Po-Wei Wang

Life of this patent

Estimating the term…

Loading patent…

Abstract

Various embodiments of systems and methods allow unsupervised, deep learning, character-level language models to complete and correct search engine queries, given arbitrary search prefixes. Embodiments use a multi-layer, character-level, recurrent neural network trained on query logs to generate query suggestions for the user. Integrated is an error correction framework. More particularly, approaches disclosed herein for query error correction and completion combine the character-level language models with an edit-distance-based potential function calibrated to generate spelling corrections, linking the two using a tree-based beam search algorithm that can exploit the potential functions and efficiently rank the suggestions. Optimizations are made to the predictive system, and efficient processor-based computations complete the queries, with error correction, in real-time. The embodiments substantially increase hit rate over standard approaches and are capable of handling tail queries.

Claims17

Dependent claims

A computer-implemented method, comprising:

receiving, by a search engine, a query string including at least a portion of a search query to be executed by the search engine;
generating one or more potential spelling corrections for the query string by applying an edit-distance potential function, the edit-distance potential function calculating errors in the query by measuring a minimum number of changes to transform a character string in the query into another string having corrected spelling;
training a multi-layer recurrent neural network on a data set to develop a character-level language model, the data set including at least one of query logs, product or service information, or customer reviews;
applying the multi-layer recurrent neural network to the query string and the spelling corrections to generate, based at least in part on the character-level language model, a plurality of suggestions for completing the portion of the search query, the character-level language model recursively operating on at least one character in a prefix in the query string;
generating the suggestions through a prefix tree;
selecting and ranking the suggestions by a heuristic beam search algorithm;
and
providing for display, as the query string is entered into the search engine, at least a subset of the suggestions as ranked.

5 more elements

A computing system, comprising:

at least one processor;
and
memory including instructions that, when executed by the at least one processor, cause the computing system to:
receive at least a portion of a query;
process one or more characters of the query using a dissimilarity analysis function to determine potential spelling corrections, the dissimilarity analysis including application of at least one edit-distance function calculating errors in the query by measuring a minimum number of changes to transform a character string in the query into another string having corrected spelling;
train a neural network on a data set to develop a character-level language model, the data set including at least one of query logs, product or service information, or customer reviews:
apply the neural network to the query and the spelling corrections to generate, based at least in part on the character-level language model, a plurality of suggestions for completing the query, the character-level language model recursively operating on at least one character in a prefix in the query;
rank the suggestions through a beam search algorithm;
and
provide for display, as the query is entered into the search engine, at least a subset of the suggestions as ranked.

7 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/900,003Filed 20 Feb 2018
Granted: 31 Aug 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

G06F 16/2468
Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries: fuzzy queries
G06F 16/2425
Query formulation: iterative querying; Query formulation based on the results of a preceding query
G06N 3/044
Architecture, e.g. interconnection topology: recurrent networks, e.g. Hopfield networks
G06N 3/0442
Recurrent networks, e.g. Hopfield networks: characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU]