CA2747153A1 - Natural language processing dialog system for obtaining goods, services or information - Google Patents

Abstract

The subject invention provides a unique system and method that uses natural language input to determine which services or products that a retailer provides best match a user's query. In particular, the system encompasses an entire dialog system that can be easily integrated into a website or other software application that has distinct entities with associated meta-data. User input can be typed, or spoken whereby speech recognition can be utilized to convert speech to text. The system will display entities that best match the user's input, and ask clarifying questions if the user is unsatisfied with the results.

Description

DESCRIPTION [0003] In particular goods and services are TITLE Natural Language Processing Dialog offered on the Internet which are accessed by System for Obtaining Goods, Services or shoppers who either use search engines to find Information. what goods and services are available, in which case shoppers type in the name or words associated with the goods or services TECHNICAL FIELD
they seek; select goods and services from a [0001] The invention relates to computer user menu available from particular sites offering interfaces. Specifically it relates goods or services; or enter words into fields of computational natural language processing forms and databases associated with websites within the domain of natural user interaction. which offer goods and services.
In particular it relates to seeking or shopping for goods, services, or information on the [0004] Existing software approaches the internet or other databases. problem of natural language computer interface, either written or oral, by attempting BACKGROUND to solve the full complexity of natural

[0002] At present computer users have the language and by trying to enable the user to options of interfacing with computers and access any software available on the computational devices such as mobile phones computer. Either that or existing software and tablets with a keyboard, mouse, touchpad often designs systems which can be tailored to and so forth. Hardware also exists to allow one very specific domain (such as phone users to interact with computers and functionality) but cannot be easily adapted to computational devices via their voice.
other domains.
However the complexity of natural spoken language is an unsolved problem in [0005] Maluuba, the language of shoppers, computing and few users use their voice as an recognizes that it is a much simpler problem interface with their computer or to provide users with natural language computational device. Furthermore users processing that relates to websites on the generally cannot use natural language with internet that offer goods or services.
existing computer software or programmes to [0006] The present invention deals with a shop for goods or services that they want or to dialog system empowered by natural language obtain information.
processing that assists a user with finding products, services, or information. More specifically, the present patent relates to a part of a specific entity.
Features are defined system for providing integrated dialog to an as individual measurable heuristic properties application. of the natural language input.

[0007] A dialog system is a computer system [0008] Existing systems are often very brittle intended to converse with a human. Natural or require someone skilled in the art to adapt language processing involves the processing to new areas. As an example, some prior art of a natural language input. A natural utilizes a rule-based approach to NER.
These language input is language used by a person approaches use manually constructed finite (as opposed to a computer language or other state patterns, which attempt to match a artificial language), including all of the sequence of words in a similar manner to a idioms, assumptions, and implications of an general regular expression matcher. These utterance in a natural language input. Natural systems are mainly rule-based.
Rule-based language processing by a computer is systems can reach high levels of accuracy, typically an attempt to understand the however they are very brittle. While they meaning of a natural input and act may be able to handle one domain of intelligently in response. The present patent categories, they'll quickly fall apart when handles natural language processing via a applied to a new domain (i.e. a flight unique approach to Named Entity Recognition oriented rule-based system will not be able (NER). Named Entity Recognition is a type of to handle book entities). The other often used information extraction that seeks to locate and paradigm in NER is statistically based classify atomic elements in text into approaches such as a Hidden-Markov-Model, predefined categories. It is necessary to abbreviated to HMM below. With the extract these atomic structures in order to majority of these approaches, every time that perform an intelligent task for a user which a new domain is chosen (i.e.
trying to build an requires specific information. For example, in NER system for extracting names and dates) a order to purchase a plane ticket for a user, it is skilled practitioner of the art needs to necessary to extract destination, departure determine which evidences or features to use location, departure time, arrival time, etcetera. for the new domain. A
rigorous defmition of Most named entity recognition algorithms use what constitutes a feature is defined in evidences or features within the natural paragraph 21.
language input to determine which words are [0009] The present invention is a scalable user says "Calgary" we could determine their system which can quickly learn how to destination city is Calgary.
identify specific required information and can be very easily adapted to new domains. It uses BRIEF DESCRIPTION OF THE
the genetic algorithm combined with other DRAWINGS
parts of the system to do feature selection and forgoes the need for a skilled practitioner of the art to adapt it to new domains. [0012] FIG. 1 is a simplified diagram illustrating one over-all embodiment of the [0010] Another problem in state of the art of present invention.
NLP is that often user input requires information outside of the immediate input to [0013] FIG. 2 is a flow diagram illustrating a understand the user. As an example, if a user potential end-to-end run-through of one said "I'd like a ticket to New York. Actually potential embodiment of the present patent's change that to Seattle." identifying that the dialog manager. The numbers 1 to 10 indicate the flow of input from one component to second sentence refers to a ticket is something that cannot be determined by looking at that another.

sentence alone in the state of the art of NLP. [0014] FIG. 3 is a diagram illustrating a The present invention remembers an entire potential embodiment of the present patent's conversation and thus can run certain NLP system.
algorithms that allow it to identify entities using past user input. DETAILED DESCRIPTION OF THE
[0011 ] Existing NER systems also have INVENTION
trouble distinguishing between very similar [0015] Reference will now be made in detail entities. As an example, disambiguating to the embodiments of the present invention, between if an entity is a destination city or examples of which are illustrated in the departure city is very difficult. The present accompanying drawings.

invention uses a system to generate questions, [0016] In FIG. 1 a flow chart is shown of the and uses the question asked as a feature to overall flow of input from a user and output disambiguate similar entities. As an example, from the system. A user provides input either the present invention may ask the user by typing directly, or else they speak to "Where would you like to leave to?" if the another speech to text engine which passes

3 along the text to the present invention. This along with other conversational context input is passed along to the dialog manage information is then passed back to the 100 which extracts as much meta-data as it delegate 201. The user input along with the can, and retrieves past information about the information taken from the dialog memory is conversation that has been occurring with the then passed along to the NLP
Engine 205. The user. This information is then passed along to NLP engine then extracts out all of the entities the Natural Language Engine 101. The natural it can determine from the information passed language engine then extracts out entities to it. An entity is essentially an atomic (defined later in the text) which is used by the element that fits into a predefined category.
dialog manager. The dialog manager then An example of an entity is a place.
These sends the final set of output to the user. entities are then passed back to the delegate.
The delegate then passes along the extracted [0017] In FIG. 2 a flow chart is shown of the entities to the entity memory 202. The entity central dialog manager 201. The dialog memory stores the most recently determined manager is responsible for storing all past entities. If a current entity being passed along conversational information 204, invoking the to the entity memory is the same as a past NLP engine 205 and outputting results. The entity, the past entity is over-ridden by the system begins when natural language input is most recent entity. The entity memory then passed to the main delegate. First the delegate returns any entities that have been extracted asks the dialog memory 204 what the last from past user input to the delegate. At this question asked was, and to provide it with any point the delegate passes along all of the filled conversational information it considers entities to the question generator 203. The relevant. The dialog memory stores the input question generator has a list of entities that it just passed to it, along with all input passed to wants filled and associated priorities. As an it in the past. It also remembers the question example, in the scenario of trying to book a that was asked in the past. The dialog memory hotel, the question generator may want check can be configured to use various algorithms to in day, check out day, and desired price.
extract useful features from the past user Check in day could be assigned a priority input. As an example, Hobbs's algorithm higher than price. If the question generator could be used to extract past entities that was then passed a check out day entity, it relate to a pronoun in the current natural would then return a question to the delegate language user input. The last question asked, that asks the user for a check in day. This

4 question generation can be done in a variety that uses a tree-like graph or model of of ways. The simplest is to simply do a linear decisions and their possible consequences, mapping between all possible filled or unfilled including chance event outcomes, resource entity states and predefined questions. This costs, and utility.
question is then returned to the delegate. The [0019] Once the query type has been delegate then passes along all of the entities to determined, the user input, last question id, the product selector 200. The product selector and context information is passed along to the uses this information to get product results.
feature extractor 301. The feature extractor There are multiple ways to get product results.
extracts out all features it considers relevant.
One of the simplest is that it could pass along The mechanism for determining what features the entities to an API of a major website, and are relevant is explained in a later section.
then parse the XML that is returned. These These features are then passed along to a results are then returned to the delegate. The conditional random field 302.
delegate then returns the product results along with the question to the user. [0020] Our solution employs a conditional random field (CRF) based approach to entity [0018] FIG 3 relates to the core natural recognition. A conditional random field is an language processing engine that is at the algorithm that is given a set of undetermined center of the system. The first step of this elements and associated features and from the system is the query classifier 300 which features determines what entity each element determines what type of query the user is is. An entity is essentially an atomic element asking. As an example, it could be that the that fits into a predefined category. An system was set up to handle a travel example of an entity is a place.
application. In this case there could be three different types of queries, one related to [0021] A feature is essentially a property that flights, one related to hotels, and one related a word or entity has or doesn't have. An to car services. The query classifier example of a feature is "Is this entity a determines which one of these particular noun?".
queries the user wants. There are a variety of A CRF decides upon the correct entity methods that could be employed for query according to the following formula classification but one example is a decision tree. A decision tree is a decision support tool P(Entity (E)IFeature (F)) = (1 C

where Alpha is the normalization constant [0025] Once you have a set of training data and W is the weight vector for the specific that has been labelled with the correct entity entity. Each weight will be associated with a for each element, training simply becomes a feature. matter of maximum likelihood learning [0022] A Conditional Random Field for P(Ei I Fi;W).

for a specific domain requires specific entities [0026] Finally, the invention can identify to be identified. As an example, we can look entities in any new sentence provided to us, at the scenario of buying a flight ticket. The by first extracting out features, and then entities that could be used are: location, date, feeding that sentence and the feature set time, luxury class, cost, carrier, stopovers, through our CRF.
number of tickets, price, specific group, and [0027] A CRF is used for a few reasons.
hotel. It is worth noting that within Maluuba's Hidden Markov Models are generally the engine, these entities are passed along to a most powerful of the MI techniques. An template tagger which further breaks the HMM require the model to treat the evidences entities down into more complex entities as if they are independent of each other (departure location, arrival location etc.).
(evidence in our case being the feature set).
[0023] Examples of some features that could This assumption is false, which results in potentially be used are: previous 2 Part-of- inaccuracy.
Speech (POS) tags, next 2 POS tags, previous [0028] However modelling dependencies in 2 chunk values, next 2 chunk values, begins the evidence with this many entities and with capital letter, and was preceded by: "to", features is a considerable amount of work or "from", "at", or "on". We also used the entity may in fact be impossible. A Conditional value of the previous element.
Random Field allows us to avoid assuming [0024] Once a set of features has been evidences are independent but doesn't require decided, it is necessary to acquire training us to model each of these dependencies. In data, and then manually label the data with the other words, a CRF is potentially more correct entities. This labelled data 306 is capable at capturing the locality of passed along to both the genetic algorithm and phenomena but requires less effort in both conditional random fields (302 and 303). adapting to any given new domain.

[0029] Feature selection, and hence accuracy measure for named entity optimized conditional random fields are recognition and the log(n) term is added so done via 305. Any combination of features that the system favours smaller models.

can be used to perform the task of NER using [0033] One of the biggest reasons that a CRF
a CRF. However the use of a particular solution was chosen was because it is very feature set can have a dramatic effect on the easy to scale to other domains.
General cross results. The present invention uses the genetic domain features can be picked. Examples of algorithm to determine the optimal feature set. such features include;
alphanumeric values [0030] The problem of finding the optimal included, is an entity the first word, is the feature set can be thought of searching the word all caps, does the word contain nouns, entire space of feature sets for the optimal are there numbers in the word, is the word answer. semantically similar to other words (i.e. what specific [0031] In order to apply the genetic algorithm, using a word net), does it include a speci the following mapping from the feature set suffix (i.e $) etc. Other features can be taken directly from the data set. As an example, the space to a binary vector space is applied.
entire dictionary of words that exist in a given data set can be used as features. As several Let F be the set of all features examples, one might determine if an entity is Let V be a binary vector space a word in the dictionary, or else, is it proceeded by or followed by a specific word Let f be a particular feature set in the dictionary.
Let S be a mapping F-> V
[0034] The system could begin with hundreds v = S(f) st of thousands of features. Subsets of this v[i] = 1 if f contains F[i] feature set could be applicable to many v[i] = 0 if f does not contain F[i] different dramatically different domains.
When it is decided to adapt the system to a new domain, all that is required is that a set of [0032] An example of a potential fitness users essentially enter natural sentences and function is made up of the f-measure + log(n) label entities in that sentence (as an example a where n is the number of features in the user may enter the sentence "I'd like a ticket feature set. The f-measure is a common to New York leaving tomorrow" and label "New York" as the destination city and services they desire that are available on the "tomorrow" as the departure date). The internet or a database.
genetic algorithm [305] then determines what 2. A system subsequent to 1 which can be the optimal set of features is, and the CRF
easily adapted to new domains, requiring very uses these features and data to extract entities little effort from computer professionals.
from future sentences. Labelling entities is a very simple task that only requires a basic 3. A system that provides a dialog knowledge of the written language. Hence, functionality, which can have d basic adapting the system to new domains requires conversation with the user.
almost no effort from a computer professional 4. A system which in essence takes the very and can, from a programmer's perspective, be complicated task of NLP, and breaks it down done almost instantly. Increasing accuracy is into the very simple task of labelling which merely a process of adding more data.
can be done by just about anyone who can [0035] Finally, two conditional random fields read written language.
are employed, although more or fewer could

5. A practical method for using natural be used depending on the domain. The first language to shop for goods and services that is Conditional Random Field is used to available on the internet or databases.
determine general entities (such as place).
These entities are used as a feature in the second CRF 303 which then determines more specific entities (such as destination city).
Once these entities are extracted, they are passed along to the dialog manager (FIG. 1).
The mechanisms for the dialog manager are explained in an earlier section.

Claims

Claims:

1. A system that can syntactically parse human speech into entities that can be easily used to provide the user with products and