Conversational understanding

Exemplary embodiments relate to methods, mediums, and systems for managing a conversation. In an embodiment, a computer-implemented input interface is provided to receive an input comprising information in natural language. A dialog manager is configured to determine an intent of the input, determine information to fulfill the intent, and identify one or both of information available to the dialog manager or information that is unavailable to the dialog manager. A conversational understanding document documents the intent and the identified information. An output interface forwards the conversational understanding document towards a task completion handler separate and distinct from the dialog manager. Other embodiments are described and claimed.

BACKGROUND

Systems for supporting human-computer interaction are increasingly becoming more sophisticated. Whereas humans have traditionally been restricted to interacting with computers in highly structured ways, advances in conversational understanding are allowing computers to process input that is provided in a natural language. Processing natural language inputs, particularly when the input requests the computer to perform a task, may be complex. Among other constraints, the computer may need to determine the nature of the requested task, identify information needed to perform the task, and solicit any unknown needed information from the user (or elsewhere).

Problematically, when these capabilities are combined together in a single component, it can become difficult or time-consuming to update the component to adapt to new types of tasks, to naturally converse with users in different manners, to provide third-party developers access to conversational understanding capabilities, and to identify potentially irrelevant information that may not need to be gathered.

SUMMARY

Exemplary embodiments relate to methods, mediums, and systems for managing a conversation and performing task completion. In an embodiment, a computer-implemented input interface is provided to receive an input comprising information in natural language. A dialog manager is configured to determine an intent of the input, determine target information to fulfill the intent, and identify one or both of information among the information that is available to the dialog manager or information that is not available to the dialog manager. A structured conversational understanding document documents the intent and the identified information. An output interface forwards the intent document towards a task completion handler separate and distinct from the dialog manager. Other embodiments are described and claimed.

DETAILED DESCRIPTION

In general, exemplary embodiments relate to methods, mediums, and systems for supporting conversational experiences, and to augment those experiences by providing additional relevant information or performing a requested task.

In particular, exemplary embodiments relate to techniques for supporting conversational experiences so as to complete a task, possibly in the presence of incomplete information. An input is provided to a natural language understanding (NLU) unit, which identifies the intent of the input. The intent is provided to a dialog manager, which determines, if possible, what additional information is needed to fulfill the input and maintains the conversation state. An entity resolution component callable by the NLU unit and/or the dialog manager may map part of the text input to entities, such as social networking graph entities. A task completion (TC) handler guides a conversation to obtain any necessary missing information. Further conversational information is provided to the dialog manager, but the separate TC handler is responsible for determining what missing information to seek, and in what order. Because the TC handler is a separate entity, third-parties can provide different TC handler plugins that allow for new intents to be handled, allow for different vendors to guide conversations in different ways, and delay decisions about the user experience for as long as possible.

According to exemplary embodiments, a NLU component identifies the intent of an input. The intent of the input represents a classification or categorization of the input based on the type of question asked or the type of task that the input requests. For example, one intent may be to request movie times, while another intent may be to check a weather forecast.

The intent is provided to a dialog manager, which determines what additional information is needed to fulfill the input and maintains a conversation state. In exemplary embodiments described herein, the operation of guiding the conversation is carried out by a TC handler separate and distinct from the dialog manager. The TC handler determines what information to seek, and at what time. Updated information prompted by the TC handler is provided to the dialog manager.

Because the handler is provided as a separate entity from the dialog manager, the functionality of managing the conversation state and resolving information to entities is separated from the functionality of deciding how the conversation should move forward. This separation makes it easier to provide new or updated handlers as third-party plugins (it may be appreciated, however, that the handlers may be implemented by the same entity as the one that implements the dialog manager). As a result, new functionality may be quickly deployed without the need to rebuild the task handling service as a whole, and the task handler may use different plugins to handle the same task in different ways.

There are a number of advantages of such a system. For example, new intents can be handled by specifying new intent types, without the need to rebuild the system. Furthermore, different vendors may provide different handler plugins that guide conversations in different ways. Moreover, decisions about the user experience are delayed for as long as possible in the process flow, which potentially allows for some missing information to be inferred without directly querying the user.

FIG. 1shows an overview of an exemplary task completion service12. An input10including, for example, text in a natural language is provided to the task completion service12. The input10may include a question, a request to perform a task, and/or information used to answer the question or perform the task. For example, the input10may include a query such as “when does the new Superman movie play?” or a request such as “purchase tickets for the new Superman movie?”

In the above examples, some information has been provided for answering the question or performing the task (e.g., that the movie is new and involves Superman), but the provided information may be insufficient to fully answer the question or perform the task. For instance, the task completion service12may need to know where the user wishes to see the movie, and at about what time. Accordingly, the task completion service12may guide a conversation to retrieve supplemental information, preferably in a natural conversational style.

An output14may be provided in a natural language (e.g., a language that has developed naturally in use, as contrasted with structured computer language). The output14may include an answer to the question (e.g., “Superman plays at 7:00 at the cinema down the street from you”), confirmation that the task has been performed (e.g., “I bought you tickets. Here's your receipt!”) or a next iteration in the conversation (e.g., “Where would you like to see the movie?”).

In order to generate the output14, the input10may be provided to a natural language understanding component28, which classifies the input10based on an intent of the input10. In the above example, the natural language understanding component28might classify the input10as a request for movie times or a request to perform the task of purchasing movie tickets.

The natural language understanding component28may generate a conversational understanding (CU) document18, which represents structured data that can be processed by a task completion handler22that services the input10. The CU document18may include an identification of the intent of the input10, any information that is known about the input10, missing information that may be useful to address the input10, etc.

Optionally, the CU document18may be provided to a broker20. In cases where more than one task completion handler22exists for servicing the input10, the broker may select one of the possible task completion handlers22to generate the output14. For example, multiple movie service plugins may exist, and the broker20may select one of the movie service plugins to answer the question or purchase the tickets.

The task completion handler22identifies any missing information from the CU document18, and guides a conversation in a natural language to obtain the missing information. When sufficient information has been collected to service the request or answer the question, the task completion handler22may provide an answer or fulfill the request.

Classification of the intent of the input and identification of present and missing information may be handled by the dialog manager72. The dialog manager72may also maintain a conversational state of a conversation managed by the task completion handler22(for example, the dialog manager72may store any already-captured information about the input10, and may update the CU document18with all available information). Meanwhile, selection of which missing information to pursue, the order to pursue the missing information, guidance of the conversation, and final servicing of the request may be handled by the task completion handler22. Thus, separation is maintained between the capabilities of the dialog manager72and the task completion handler22.

As a result, different plugins may be employed as part of the task completion handler22, including third-party plugins. Moreover, the dialog manager72may be extended using third-party intent resolution handlers. This allows new intents to be serviced without rebuilding the entire task completion service12and allows different vendors to handle the same input10in different ways (e.g., using different conversational styles or different services).

Furthermore, this exemplary setup allows decisions about which information to pursue to be delayed to as late as possible in the processing flow (e.g., being handled by the task completion handler22instead of the dialog manager72), which means that the task completion handler22may be able to infer some information or determine that some information identified by the dialog manager72is not relevant in the present context. For instance, in the above example, the task completion handler22may include a plugin provided by a movie application that only services theaters in a limited geographic area. If the movie Superman is only playing at one theater serviced by the plugin, then it may not be necessary for the task completion handler22to ask where the user would like to see the movie, and the handler22may refrain from asking the user questions related to location. This may not be possible in a system in which the decision as to which information to pursue is handled by a general-purpose dialog manager72.

These and other features and advantages are described in the detailed block diagrams and flowcharts below. Before these exemplary embodiments are addressed, a general note on data privacy is provided.

Data Privacy

Some embodiments described herein make use of data that may include information voluntarily provided by one or more users. In such embodiments, data privacy may be protected in a number of ways.

For example, the user may be required to opt in to any data collection before user data is collected or used. The user may also be provided with the opportunity to opt out of any data collection. Before opting in to data collection, the user may be provided with a description of the ways in which the data will be used, how long the data will be retained, and the safeguards that are in place to protect the data from disclosure.

Any information identifying the user from which the data was collected may be purged or disassociated from the data. In the event that any identifying information needs to be retained (e.g., to meet regulatory requirements), the user may be informed of the collection of the identifying information, the uses that will be made of the identifying information, and the amount of time that the identifying information will be retained. Information specifically identifying the user may be removed and may be replaced with, for example, a generic identification number or other non-specific form of identification.

Once collected, the data may be stored in a secure data storage location that includes safeguards to prevent unauthorized access to the data. The data may be stored in an encrypted format. Identifying information and/or non-identifying information may be purged from the data storage after a predetermined period of time.

Although particular privacy protection techniques are described herein for purposes of illustration, one of ordinary skill in the art will recognize that privacy protected in other manners as well. Further details regarding data privacy are discussed below in the section describing network embodiments.

Next, a detailed description of the components of the conversational understanding system is provided.

Natural Language Understanding Component, Dialog Manager, and Entity Resolution

FIG. 2Aillustrates an exemplary illustration of a natural language understanding (NLU) component28, which works with the exemplary dialog manager72depicted inFIG. 4todetermine the intent of the input10, maintain a conversational state, and generate a CU document18to be provided to the broker20and/or the task completion handler22. The NLU component28and dialog manager72may consult one or more entity resolution components29, as shown inFIG. 3, to resolve any entities in the input10.

The goal of the NLU28and dialog manager72is to analyze the input10and fill in as many informational gaps as possible, given the information available to the respective components.

Initially, the NLU component28generates a CU document18with a unique identifier. The document contains all the information for the incoming request known to the NLU component28. For example, the CU document18may include a partner ID identifying where the input10originated (e.g., an application or service), a viewer context, natural language text that was provided as part of the input10, an ID for the language of the natural language text, etc. The CU document18is passed through the natural language understanding (NLU) component28and to the dialog manager72.

FIG. 2Aillustrates an exemplary NLU component28hosting custom rules32, language processors34, and trained models36which are composed into flows to meet the requirements of various partners. The NLU component28produces intent candidates (e.g., possible categories or classifications of tasks/questions) and/or a structured representation of the input natural language text which will be further processed by the intent service16.

Next, a dialog manager72processes the output of the language processing steps performed by the natural language understanding component28and decides on next steps, such as further target information that is needed or useful to service the request or answer the question in the input10. A description of suggested next steps, such as information to be requested, may be recorded in the CU document18that may be returned to the original caller or provided to a task completion handler22. This information may be used to guide a back-and-forth conversation in which further information is solicited from a user.

The dialog manager72may have access to instances of the CU document26from previous interactions. For example, in an embodiment implemented in a social networking context, each such CU document26may be stored in a user's social networking graph. This way, the dialog manager72might use that earlier information to reconstruct a conversation and aggregate available information about a request or question.

Alternatively, or in addition, other ways of establishing a conversational context may also be used (e.g. retrieving a conversation history in a messaging program or other applications or interfaces for conducting a conversation).

The natural language understanding component28is now described in more detail.

Natural Language Understanding Service

FIG. 2Bdepicts the natural language understanding (NLU) component28in more detail. The NLU component28is responsible for processing some input text (considering some context). It produces intent candidates and/or structured representation of the input text which will be further processed by the intent service16.

As previously noted, the NLU component28may include custom rules32for one or more domains, which may be created through a custom rules engine (CRE) service38. Given a specified partner ID, as discussed above, the CRE service38may evaluate the input against a custom rules set for that particular partner.

The NLU component28may also host machine-language-trained models34for language processing. The models34may be trained by one or more model trainers40. The CRE service38and the models34may be composed together to form language processors34that implement partner-specific language processing flows.

The initial input10may be received by a service handler42, which generates a CU document18and hands the CU document18off to an NLU Engine44. Based on consultation with the language processors34, a partner manager46, and a model manager48, the engine44creates an updated context document18(which may include the original input document10).

Using the Partner Manager (PM) component46, a Language Processor (LP)34is chosen to address the request. The Partner Manager46maintains a map between third-party partners and their specific implementation of a Language Processor34interface. Furthermore, a Model Manager (MM)48is passed, if necessary, to the partner-specific LP34so that information about all the deployed models36is available. The partner-specific LP34can utilize other processors34that are available in order to implement the processing on the context (e.g. SVM, CRF, Travel-specific SVM). The response of each Language Processor34may be added to the CU document18to generate a response50, which is then converted into an updated CU document18by the NLU engine44.

The language processors34may include a CRE language processor52and/or model-specific language processors54, that are trained by the model trainer40. There may also be a Language Processor34that acts as a bridge between the NLU service28and a predictor service for Deep Neural Network (DNN)-trained models.

Upon startup of the service, the Model Manager48indexes all the metadata about the models36that are available. Similarly, the Partner Manager46loads all the partner-specific Language Processors34, which in turn instantiate all the Language Processors34they are using so that the models36are loaded in memory.

A new partner on-boarding may require the implementation of a new partner-specific LP34and a new deployment of the service12. To avoid this coupling, a declarative mechanism may be provided for defining partner-specific compositions of our Language Processors34. Such compositions may be loaded dynamically, without requiring a new deployment of the service12.

As noted above, the language processors34may make use of custom rulesets32, which may be accessed through a custom rules service38. The custom rules service38may include a custom rules interpreter58for accepting an input from the language processors34and applying the custom rulesets32. A custom rules management component60may provide an interface to allow new custom rulesets32to be easily defined and/or updated.

Alternatively, or in addition, in the absence of an appropriate ML-trained model36, custom rules32may be used to process the input text and generate an intent. The custom rules32may also generate a candidate response for the response document50.

Entity Resolution

The NLU component28may consult with one or more entity resolution components29in order to resolve entities in the input10. An exemplary entity resolution component29is depicted inFIG. 3.

The entity resolution component29maps elements of the input10to specific entities or data structures. For example, if the input10includes the keyword “tomorrow,” an entity resolution component29may map the keyword to a particular computational “date” object representing the following day. Similarly, if the input10includes the key phrase “tomorrow morning,” an entity resolution component29may further map the phrase to a “time” object representing a default morning time (e.g., a date/time object representing the following day at 9:00 AM). Other examples are also possible: named people may be mapped to users of a social network, particular movies may be mapped to a data object representing the movie in a database, etc.

FIG. 3depicts several examples of entity resolution components29, including a date/time component29a, a movie component29b, a social network entity component29c, a person component29d, etc. Other examples might include, for instance, a location resolution component (e.g., mapping the term “Seattle” to a data object representing a Seattle, Wash.), among other possibilities. To facilitate entity resolution, the entity resolution components29may connect to external entities, such as a social networking graph228(described in more detail in connection withFIG. 11). The social networking graph228may be used to resolve social network entities29csuch as users, businesses, interest pages, etc., but may also be used to resolve other types of entities as well (e.g., the movie component29bmay resolve movies to a particular node of the social networking graph228brepresenting a movie, or to a social networking page for the movie).

Dialog Manager

FIG. 4illustrates an exemplary dialog manager72. As shown inFIG. 4, the CU document18produced by the NLU component28may be provided to the dialog manager72. The dialog manager72analyzes the CU document18, potentially using local or third-party intent resolution handlers, in order to determine next steps that may be taken in the conversation.

The dialog manager72may be configured to provide application-specific user experiences, and may call a particular application programming interface (API) function as specified in the intent resolution handlers for a given intent. The intent resolution handlers may identify target information for a particular intent, and different intent resolution handlers may handle different intents. The target information identified by the dialog manager72may be bundled into the CU document18and provided to a task completion handler that guides a conversation to obtain the missing information and/or service the request.

The intent resolution handlers may include different handlers for servicing different intents and identifying any information needed or useful for fulfilling the intents (“target information”).

New intents may be serviced by providing new intent resolution handers. A new intent resolution handler may be constructed, for example, by specifying a language model34to use for an intent associated with the intent resolution handler, by specifying any dialog requirements for the intent resolution handler (e.g., information that is used to fulfill the requests), and optionally an application programming interface (API) endpoint to call when dialog involving the intent is required. This and other information may be supplied for each of the intent resolution handlers, and the dialog manager72may consult this information when a particular intent is identified in the CU document18.

The dialog manager72may also interact with external services88in order to fill in any gaps that the language processors did not cover. Alternatively, or in addition, if there are multiple candidate interpretations from the language processors34, the dialog manager72might decide to reach out to external services88to see which of those interpretation has a higher chance of returning a result.

The dialog manager72may employ one or more custom rules and may therefore consult the custom rules service38. Furthermore, the dialog manager72may make use of one or more models, and may therefore consult a model trainer62(similar to the model trainer40as depicted in connection with the NLU component28ofFIG. 2B; however, the dialog manager72may make use of different types of models than the models36of the NLU component28).

The output of the dialog manager72may be a CU document18, which may be forwarded towards a task completion handler22. As noted above, at each step in a conversation, previous messages in the conversation remain available to the components of the service12, including the dialog manager72. As a result, the dialog manager72may access previous messages and/or locally store any relevant information about the conversation, in order to maintain a full state of the conversation. The dialog manager72may update the CU document18to include all relevant information that has been gathered during the course of the conversation as the conversation progresses. Thus, the task completion handler22may be a stateless entity and can always be provided with the most up-to-date information by the dialog manager72.

Task Completion Handlers

FIG. 5illustrates exemplary task completion handlers22. The task completion handlers22support user experiences by providing an output14(e.g. some language, the result of an operation, etc.) that is performed as a result of the identified intent. The partner ID given at the beginning of the processing pipeline may define the behavior of the task completion handlers22.

When an input CU document18is received specifying a particular intent, a task completion handler22responsible for the identified intent will be dispatched to generate the appropriate response. The handler22may initially consult the CU document18in case a candidate response is already there (e.g., if a candidate response was inserted by one of the rules in the ruleset32). Exemplary task completion handlers22depicted inFIG. 5include a search handler22a, a weather handler22b, a joke handler22c, a casual conversation handler22d, a social networking handler22e, and a dialog follow-up handler wwf (although other possibilities exist as well). The task completion handlers22may also interact with external services88to resolve ambiguous information or to acquire information not specified in the input10without the need to interact with a user.

A task completion handler22may be provided by the same entity that provides the dialog manager72, or may be provided by a third party. In such an event, the dialog manager72and the task completion handler22may be hosted in separate locations and may communicate with each other over a network, such as the Internet.

The task completion handlers22are responsible for evaluating the information in the CU document18in order to identify which potentially relevant information still needs to be collected before the intent can be serviced. A given task completion handler22decides which information to pursue, and in what order. The task completion handler22also decides the particular language to employ in conducting the conversation, so that different task completion handlers22may possess different conversational styles.

Data Structures

FIGS. 6-8depict exemplary data structures suitable for use in exemplary embodiments.

FIG. 6depicts an exemplary input10. The input10may include natural language text90, such as a query or instruction from a user written in a natural, conversational style.

The input10may also include a partner ID92that identifies a partner that originated the request or that is associated with the request. For example, if the user accesses the service12through a movie application, the partner ID92may be an identifier of the movie service associated with the movie application. The partner ID92and/or the natural language may be analyzed to identify the intent of the input10.

The input10may also specify a language ID94, which identifies the language of the natural language text90. The language ID94may be used to identify which language models to apply to the natural language text90.

FIG. 7depicts an exemplary CU document18, which is a structured document (e.g., not written in a natural language) intended for internal consumption by the service12.

The CU document18may include an intent ID96, which identifies the intent of the input10. The intent ID96may be determined based on one or both of the natural language text90or the partner ID92.

The CU document18may further includes fields or slots98for information. The slots98may include one slot each for information deemed to be relevant to processing the input10(e.g., as determined by the intent resolution handlers62). For example, if the identified intent is a request for movie times, then the intent document18may include information slots98for the name of the movie, the time and/or date for which show times are requested, and a location at which the user would like to see the movie. To this end, the information slots98may each include a field for the type of information (e.g., “location”) and a field102for holding the value of the information (e.g., “Seattle, Wash.”). The information value field102may be left blank if the information is not yet known. Thus, if the task completion handler receives an intent document18having blank value fields102, then the task completion handler may be aware that some information useful or necessary for processing the request has not yet been provided. The task completion handler can then decide whether to request the information and, if so, in what order missing information should be acquired.

In some cases, the intent of the input10may be ambiguous, such that more than one intent may be possible. For example, if a user provides an input of “I want to watch Superman,” the user might want to go to a movie theater to see the movie, or might want to watch the movie at home on a cable channel. This could therefore result in a first intent of “movie search” and a second intent of “TV search.” Each of these may be treated as a separate hypothesis, and the CU document18may include data structures95a,95b, . . . corresponding to different hypotheses. Each data structure95a,95b, . . . may include a hypothesis score97, which represents a likelihood or probability for the hypothesis. The hypothesis score97may be assigned, for example, by the dialog manager72. The dialog manager72or the broker20may select the hypothesis with the highest score97and forward the CU document18to the appropriate handler22for that hypothesis. Alternatively or in addition, the dialog manager72or the broker20may use a decision making algorithm to resolve the ambiguity based on the identified hypotheses. For example, the dialog manager72or the broker20may submit a query to the user asking which of the hypotheses is correct (e.g., “do you want to see a movie on your device or go to the theater?”).

FIG. 8illustrates an exemplary output14. The output14includes the intent ID96that identifies the intent of the input10. Furthermore, any entities104identified by the entity resolution component29may be specified in the output14.

The output14may also include fields representing an overall understanding of the conversation106(e.g., the information from the information slots98). This information may be used at the client side or by the dialog manager72to quickly regenerate the state of the conversation. It is noted that although the task resolution handler22may package the information form the information slots98(as received in the CU document18) into the output14, the handler22may refrain from maintaining the state of the conversation itself. This allows the handler22to be stateless and frees the handler22from the need to identify which information has or has not yet been provided, thereby facilitating interoperation between the dialog manager72and third-party handlers22.

The output14also includes a user-consumable response110(e.g., natural language text intended for human consumption) as generated by the task completion handler22. In some embodiments, the response110may be paired with the task results108to provide a full response to the user.

Exemplary Method

FIG. 9depicts an exemplary method suitable for use with exemplary embodiments. The method may be implemented as conversational understanding logic112in the form of instructions stored on a non-transitory computer readable medium.

At block114, an input may be provided to the task completion service. The input may be in the form of natural language text that presents a request for information, a request to perform a task, and/or information that may be used to fulfill a request. The input may also include a partner ID specifying a partner from which the input originated or otherwise associated with the input. The input may also include a language ID that specifies a language of the natural language text.

At block116, the input may be processed at a dialog manager of the task completion service. Block1116may involve multiple sub-operations. For example, processing the input may involve determining an intent of the input at block118. The intent may be determined based on a partner ID provided with the input and/or by processing the natural language text of the input to identify the intent of the text (e.g., in view of one or more keywords and/or one or more rules). Processing the input may further include determining any target information that is necessary or useful for servicing the intent at block120. For example, the dialog manager may consult one or more intent resolution handlers that describe the information necessary or useful for processing the intent. The dialog manager may also identify any information contained in the natural language text of the input, in order to update the conversational state.

Any target information that is deemed useful or necessary, as identified in block120, may be analyzed in view of existing information accessible to the dialog manager (in the present input and any previous inputs in the conversation). For example, because the dialog manager maintains the conversational state including previous communications in the conversation, the dialog manager may identify any information that was identified as useful or necessary in block120, but which is already present in the conversational history. Based on this determination, the dialog manager may identify any necessary or useful information that has not already been gathered, and identify this as missing information in block120.

As a result of processing the input at block116, the dialog manager may produce an intent document. Optionally, the dialog manager may pass the intent document to a broker at block124. The broker may, at block126, determine whether multiple handlers exist for servicing the intent, and may select one of the handlers to process the intent document. For example, the broker may consult one or more user preferences to determine if the user has a preferred handler for servicing requests of this type. Alternatively or in addition, the natural language text of the input may specify a preferred handler. Still further, different handlers for the same intent may have different informational requirements, and the broker may select the handler for which the minimum amount of additional information needs to be specified. One of ordinary skill in the art will understand that other techniques for selecting a preferred handler may also be employed.

At block128, the intent may be forwarded to the selected handler. If the handler is integrated into the task completion system, then the intent document may be provided directly to the selected handler. If the handler is provided by a third party plugin, then the dialog manager or broker may connect to the plugin (e.g., via a network). In either case, the dialog manager or broker may provide the intent document to the handler by calling an API method for the handler, as specified in the intent resolution handler for the specified intent.

Processing may then proceed to block130, where the handler may determine whether it has sufficient information to complete the original task or answer the original question. For example, the handler may determine whether any necessary or useful information is missing from the intent document. It is noted that it may not be necessary to provide all information specified in the intent document (e.g., some information may be determined by the handler to be irrelevant in the present context). If sufficient information is available to complete the task or answer the query, then at step132the task handler may generate a response, and processing may end at step134.

If the handler is not ready to complete the task at block130, then at block136the handler may select a piece of missing information to request from the user. Each handler may include its own internal logic for determining which piece of information to request, in what order, and how to request the information. Processing may then proceed to block138, when the handler generates a response that requests the missing information. Processing may then return to step block, where a new input (e.g., in response to the request for missing information) is received.

Network Embodiments

FIG. 10illustrates an exemplary network environment in which some or all of the embodiments may be implemented.

A user may interact with a client210, which may be (for example) a personal computer, tablet, mobile phone, special-purpose translation device, etc. In some embodiments, the client210does not require interaction from a user.

The client210may include one or more input devices212and one or more output devices214. The input devices212may include, for example, microphones, keyboards, cameras, electronic pens, touch screens, and other devices for receiving an input. The output devices214may include a speaker, a display device such as a monitor or touch screen, and other devices for presenting an output.

In some embodiments, the input from the input devices212may be in the form of an input10that is being sent to a task completion service12for processing.

The client210may include a memory216, which may be a non-transitory computer readable storage medium, such as one or a combination of a hard drive, solid state drive, flash storage, read only memory, or random access memory. The memory216may a representation of an input10and/or a representation of an output14, as well as one or more applications. For example, the memory216may store a social networking client218that allows a user to interact with a social networking service.

The input10may be textual, such as in the case where the input device212is a keyboard. Alternatively, the input10may be an audio recording, such as in the case where the input device212is a microphone. Accordingly, the input10may be subjected to automatic speech recognition (ASR) logic140in order to transform the audio recording to text that is processable by the task completion service12. As shown inFIG. 10, the ASR logic140may be located at the client device210(so that the audio recording is processed locally by the client210and corresponding text is transmitted to the conversational understanding server224), or may be located remotely at the conversational understanding server224(in which case, the audio recording may be transmitted to the conversational understanding server224and the conversational understanding server224may process the audio into text). Other combinations are also possible—for example, if the input device212is a touch pad or electronic pen, the input10may be in the form of handwriting, which may be subjected to handwriting or optical character recognition analysis logic in order to transform the input10into processable text.

Similarly, a resulting output14from a task completion system12may be in the form of text. In some embodiments, the desirable end form of the output may be something other than text, such as an audio representation of the translation. Accordingly, the output14may be subjected to text-to-speech (TTS) logic142in order to transform the text into an audio recording that is presentable by the output devices214. As shown inFIG. 10, the TTS logic142may be located at the client device210(so that the output text is processed locally by the client210and corresponding audio is sent to the output devices214), or may be located remotely at the conversational understanding server224(in which case, text may be processed at the conversational understanding server224and the resulting audio recording may be transmitted to the client210). Other combinations of processing logic are also possible, depending on the desired final form for the output14.

The client210may be provided with a network interface220for communicating with a network222, such as the Internet. The network interface220may transmit the input16in a format and/or using a protocol compatible with the network222and may receive a corresponding output28from the network222.

The network interface220may communicate through the network222to a conversational understanding server224. The conversational understanding server224may host the above-described task completion service12.

The network interface220of the client210may also be used to communicate through the network222with a social networking server226. The social networking server226may include or may interact with a social networking graph228that defines connections in a social network. Furthermore, the conversational understanding server224may connect to the social networking server226for various purposes, such as retrieving training data from the social network. The client210may provide the input36to, and may receive the output18from, the social network (e.g., as a translated post, article, etc.).

A user of the client210may be an individual (human user), an entity (e.g., an enterprise, business, or third-party application), or a group (e.g., of individuals or entities) that interacts or communicates with or over the social-networking server226. The social-networking server226may be a network-addressable computing system hosting an online social network. The social-networking server226may generate, store, receive, and send social-networking data, such as, for example, user-profile data, concept-profile data, social-graph information, or other suitable data related to the online social network. The social-networking server226may be accessed by the other components of the network environment either directly or via the network222.

The social-networking server226may include an authorization server (or other suitable component(s)) that allows users to opt in to or opt out of having their actions logged by social-networking server226or shared with other systems (e.g., third-party systems, such as the translation server224), for example, by setting appropriate privacy settings. A privacy setting of a user may determine what information associated with the user may be logged, how information associated with the user may be logged, when information associated with the user may be logged, who may log information associated with the user, whom information associated with the user may be shared with, and for what purposes information associated with the user may be logged or shared. Authorization servers may be used to enforce one or more privacy settings of the users of social-networking server226through blocking, data hashing, anonymization, or other suitable techniques as appropriate.

In response to a request from a user (or other entity) for a particular object stored in a data store, the social-networking system226may send a request to the data store for the object. The request may identify the user associated with the request. The requested data object may only be sent to the user (or a client system210of the user) if the authorization server determines that the user is authorized to access the object based on the privacy settings associated with the object. If the requesting user is not authorized to access the object, the authorization server may prevent the requested object from being retrieved from the data store, or may prevent the requested object from be sent to the user. In the search query context, an object may only be generated as a search result if the querying user is authorized to access the object. In other words, the object must have a visibility that is visible to the querying user. If the object has a visibility that is not visible to the user, the object may be excluded from the search results.

In some embodiments, targeting criteria may be used to identify users of the social network that may benefit from the above-described classifier and/or translation system. Targeting criteria used to identify and target users may include explicit, stated user interests on social-networking server226or explicit connections of a user to a node, object, entity, brand, or page on social-networking server226. In addition, or as an alternative, such targeting criteria may include implicit or inferred user interests or connections (which may include analyzing a user's history, demographic, social or other activities, friends' social or other activities, subscriptions, or any of the preceding of other users similar to the user (based, e.g., on shared interests, connections, or events)). Particular embodiments may utilize platform targeting, which may involve platform and “like” impression data; contextual signals (e.g., “Who is viewing now or has viewed recently the page for COCA-COLA?”); light-weight connections (e.g., “check-ins”); connection lookalikes; fans; extracted keywords; EMU advertising; inferential advertising; coefficients, affinities, or other social-graph information; friends-of-friends connections; pinning or boosting; deals; polls; household income, social clusters or groups; products detected in images or other media; social- or open-graph edge types; geo-prediction; views of profile or pages; status updates or other user posts (analysis of which may involve natural-language processing or keyword extraction); events information; or collaborative filtering. Identifying and targeting users may also implicate privacy settings (such as user opt-outs), data hashing, or data anonymization, as appropriate.

FIG. 11illustrates an example of a social graph228. In exemplary embodiments, a social-networking service may store one or more social graphs228in one or more data stores as a social graph data structure via the social networking service.

The social graph228may include multiple nodes, such as user nodes230and concept nodes232. The social graph228may furthermore include edges234connecting the nodes. The nodes and edges of social graph228may be stored as data objects, for example, in a data store (such as a social-graph database). Such a data store may include one or more searchable or queryable indexes of nodes or edges of social graph228.

The social graph228may be accessed by a social-networking server226, client system210, third-party system (e.g., the translation server224), or any other approved system or device for suitable applications.

A user node230may correspond to a user of the social-networking system. A user may be an individual (human user), an entity (e.g., an enterprise, business, or third-party application), or a group (e.g., of individuals or entities) that interacts or communicates with or over the social-networking system. In exemplary embodiments, when a user registers for an account with the social-networking system, the social-networking system may create a user node230corresponding to the user, and store the user node30in one or more data stores. Users and user nodes230described herein may, where appropriate, refer to registered users and user nodes230associated with registered users. In addition, or as an alternative, users and user nodes230described herein may, where appropriate, refer to users that have not registered with the social-networking system. In particular embodiments, a user node230may be associated with information provided by a user or information gathered by various systems, including the social-networking system. As an example and not by way of limitation, a user may provide their name, profile picture, contact information, birth date, sex, marital status, family status, employment, education background, preferences, interests, or other demographic information. In particular embodiments, a user node230may be associated with one or more data objects corresponding to information associated with a user. In particular embodiments, a user node230may correspond to one or more webpages. A user node230may be associated with a unique user identifier for the user in the social-networking system.

In particular embodiments, a concept node232may represent a third-party webpage or resource hosted by a third-party system. The third-party webpage or resource may include, among other elements, content, a selectable or other icon, or other inter-actable object (which may be implemented, for example, in JavaScript, AJAX, or PHP codes) representing an action or activity. As an example and not by way of limitation, a third-party webpage may include a selectable icon such as “like,” “check in,” “eat,” “recommend,” or another suitable action or activity. A user viewing the third-party webpage may perform an action by selecting one of the icons (e.g., “eat”), causing a client system to send to the social-networking system140a message indicating the user's action. In response to the message, the social-networking system140may create an edge (e.g., an “eat” edge) between a user node230corresponding to the user and a concept node232corresponding to the third-party webpage or resource and store edge234in one or more data stores.

In particular embodiments, a pair of nodes in social graph228may be connected to each other by one or more edges234. An edge234connecting a pair of nodes may represent a relationship between the pair of nodes. In particular embodiments, an edge234may include or represent one or more data objects or attributes corresponding to the relationship between a pair of nodes. As an example and not by way of limitation, a first user may indicate that a second user is a “friend” of the first user. In response to this indication, the social-networking system140may send a “friend request” to the second user. If the second user confirms the “friend request,” the social-networking system may create an edge234connecting the first user's user node230to the second user's user node230in social graph228and store edge234as social-graph information in one or more data stores. In the example ofFIG. 11, social graph228includes an edge234indicating a friend relation between user nodes230of user “Amanda” and user “Dorothy.” Although this disclosure describes or illustrates particular edges234with particular attributes connecting particular user nodes230, this disclosure contemplates any suitable edges234with any suitable attributes connecting user nodes230. As an example and not by way of limitation, an edge234may represent a friendship, family relationship, business or employment relationship, fan relationship, follower relationship, visitor relationship, subscriber relationship, superior/subordinate relationship, reciprocal relationship, non-reciprocal relationship, another suitable type of relationship, or two or more such relationships. Moreover, although this disclosure generally describes nodes as being connected, this disclosure also describes users or concepts as being connected. Herein, references to users or concepts being connected may, where appropriate, refer to the nodes corresponding to those users or concepts being connected in social graph228by one or more edges234.

In particular embodiments, an edge234between a user node230and a concept node232may represent a particular action or activity performed by a user associated with user node230toward a concept associated with a concept node232. As an example and not by way of limitation, as illustrated inFIG. 11, a user may “like,” “attended,” “played,” “listened,” “cooked,” “worked at,” or “watched” a concept, each of which may correspond to a edge type or subtype. A concept-profile page corresponding to a concept node232may include, for example, a selectable “check in” icon (such as, for example, a clickable “check in” icon) or a selectable “add to favorites” icon. Similarly, after a user clicks these icons, the social-networking system140may create a “favorite” edge or a “check in” edge in response to a user's action corresponding to a respective action. As another example and not by way of limitation, a user (user “Carla”) may listen to a particular song (“Across the Sea”) using a particular application (SPOTIFY, which is an online music application). In this case, the social-networking system140may create a “listened” edge234and a “used” edge (as illustrated inFIG. 2) between user nodes230corresponding to the user and concept nodes232corresponding to the song and application to indicate that the user listened to the song and used the application. Moreover, the social-networking system140may create a “played” edge234(as illustrated inFIG. 11) between concept nodes232corresponding to the song and the application to indicate that the particular song was played by the particular application. In this case, “played” edge234corresponds to an action performed by an external application (SPOTIFY) on an external audio file (the song “Across the Sea”). Although this disclosure describes particular edges234with particular attributes connecting user nodes230and concept nodes232, this disclosure contemplates any suitable edges234with any suitable attributes connecting user nodes230and concept nodes232. Moreover, although this disclosure describes edges between a user node230and a concept node232representing a single relationship, this disclosure contemplates edges between a user node230and a concept node232representing one or more relationships. As an example and not by way of limitation, an edge234may represent both that a user likes and has used at a particular concept. Alternatively, another edge234may represent each type of relationship (or multiples of a single relationship) between a user node230and a concept node232(as illustrated inFIG. 11between user node230for user “Edwin” and concept node232for “SPOTIFY”).

In particular embodiments, the social-networking system140may create an edge234between a user node230and a concept node232in social graph228. As an example and not by way of limitation, a user viewing a concept-profile page (such as, for example, by using a web browser or a special-purpose application hosted by the user's client system) may indicate that he or she likes the concept represented by the concept node232by clicking or selecting a “Like” icon, which may cause the user's client system to send to the social-networking system a message indicating the user's liking of the concept associated with the concept-profile page. In response to the message, the social-networking system may create an edge234between user node230associated with the user and concept node232, as illustrated by “like” edge234between the user and concept node232. In particular embodiments, the social-networking system140may store an edge234in one or more data stores. In particular embodiments, an edge234may be automatically formed by the social-networking system in response to a particular user action. As an example and not by way of limitation, if a first user uploads a picture, watches a movie, or listens to a song, an edge234may be formed between user node230corresponding to the first user and concept nodes232corresponding to those concepts. Although this disclosure describes forming particular edges234in particular manners, this disclosure contemplates forming any suitable edges234in any suitable manner.

The social graph228may further comprise a plurality of product nodes. Product nodes may represent particular products that may be associated with a particular business. A business may provide a product catalog to a consumer-to-business service and the consumer-to-business service may therefore represent each of the products within the product in the social graph228with each product being in a distinct product node. A product node may comprise information relating to the product, such as pricing information, descriptive information, manufacturer information, availability information, and other relevant information. For example, each of the items on a menu for a restaurant may be represented within the social graph228with a product node describing each of the items. A product node may be linked by an edge to the business providing the product. Where multiple businesses provide a product, each business may have a distinct product node associated with its providing of the product or may each link to the same product node. A product node may be linked by an edge to each user that has purchased, rated, owns, recommended, or viewed the product, with the edge describing the nature of the relationship (e.g., purchased, rated, owns, recommended, viewed, or other relationship). Each of the product nodes may be associated with a graph id and an associated merchant id by virtue of the linked merchant business. Products available from a business may therefore be communicated to a user by retrieving the available product nodes linked to the user node for the business within the social graph228. The information for a product node may be manipulated by the social-networking system as a product object that encapsulates information regarding the referenced product.

As such, the social graph228may be used to infer shared interests, shared experiences, or other shared or common attributes of two or more users of a social-networking system. For instance, two or more users each having an edge to a common business, product, media item, institution, or other entity represented in the social graph228may indicate a shared relationship with that entity, which may be used to suggest customization of a use of a social-networking system, including a messaging system, for one or more users.

FIG. 12illustrates an embodiment of an exemplary computing architecture236suitable for implementing various embodiments as previously described. The above-described methods, for example, may be embodied as instructions on a computer readable medium or as part of the computing architecture236. In one embodiment, the computing architecture236may comprise or be implemented as part of an electronic device. Examples of an electronic device may include those described with reference toFIG. 12, among others. The embodiments are not limited in this context.

As shown inFIG. 12, the computing architecture236comprises a processing unit240, a system memory242and a system bus244. The processing unit240can be any of various commercially available processors, including without limitation an AMD® Athlon®, Duron® and Opteron® processors; ARM® application, embedded and secure processors; IBM® and Motorola® DragonBall® and PowerPC® processors; IBM and Sony® Cell processors; Intel® Celeron®, Core (2) Duo®, Itanium®, Pentium®, Xeon®, and XScale® processors; and similar processors. Dual microprocessors, multi-core processors, and other multi-processor architectures may also be employed as the processing unit240.

The computer238may include various types of computer-readable storage media in the form of one or more lower speed memory units, including an internal (or external) hard disk drive (HDD)250, a magnetic floppy disk drive (FDD)252to read from or write to a removable magnetic disk254, and an optical disk drive256to read from or write to a removable optical disk258(e.g., a CD-ROM or DVD). The HDD250, FDD252and optical disk drive256can be connected to the system bus244by a HDD interface260, an FDD interface262and an optical drive interface264, respectively. The HDD interface260for external drive implementations can include at least one or both of Universal Serial Bus (USB) and IEEE 694 interface technologies.

The drives and associated computer-readable media provide volatile and/or nonvolatile storage of data, data structures, computer-executable instructions, and so forth. For example, a number of program modules can be stored in the drives and memory units246,248, including an operating system266, one or more application programs268, other program modules270, and program data272. In one embodiment, the one or more application programs268, other program modules270, and program data272can include, for example, the various applications and/or components of the system30.

A user can enter commands and information into the computer238through one or more wire/wireless input devices, for example, a keyboard274and a pointing device, such as a mouse276. Other input devices may include microphones, infra-red (IR) remote controls, radio-frequency (RF) remote controls, game pads, stylus pens, card readers, dongles, finger print readers, gloves, graphics tablets, joysticks, keyboards, retina readers, touch screens (e.g., capacitive, resistive, etc.), trackballs, trackpads, sensors, styluses, and the like. These and other input devices are often connected to the processing unit504through an input device interface278that is coupled to the system bus244, but can be connected by other interfaces such as a parallel port, IEEE 694 serial port, a game port, a USB port, an IR interface, and so forth.

A monitor280or other type of display device is also connected to the system bus244via an interface, such as a video adaptor282. The monitor280may be internal or external to the computer238. In addition to the monitor280, a computer typically includes other peripheral output devices, such as speakers, printers, and so forth.

The computer238may operate in a networked environment using logical connections via wire and/or wireless communications to one or more remote computers, such as a remote computer284. The remote computer284can be a workstation, a server computer, a router, a personal computer, portable computer, microprocessor-based entertainment appliance, a peer device or other common network node, and typically includes many or all of the elements described relative to the computer238, although, for purposes of brevity, only a memory/storage device286is illustrated. The logical connections depicted include wire/wireless connectivity to a local area network (LAN)288and/or larger networks, for example, a wide area network (WAN)290. Such LAN and WAN networking environments are commonplace in offices and companies, and facilitate enterprise-wide computer networks, such as intranets, all of which may connect to a global communications network, for example, the Internet.

When used in a LAN networking environment, the computer238is connected to the LAN288through a wire and/or wireless communication network interface or adaptor292. The adaptor292can facilitate wire and/or wireless communications to the LAN288, which may also include a wireless access point disposed thereon for communicating with the wireless functionality of the adaptor292.

When used in a WAN networking environment, the computer238can include a modem294, or is connected to a communications server on the WAN290, or has other means for establishing communications over the WAN290, such as by way of the Internet. The modem294, which can be internal or external and a wire and/or wireless device, connects to the system bus244via the input device interface278. In a networked environment, program modules depicted relative to the computer238, or portions thereof, can be stored in the remote memory/storage device286. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers can be used.

Terminology