PATENT DOCUMENT

Publication Number: US-9633004-B2
Application Number: US-201414500703-A
Country: US
Kind Code: B2

Title: Better resolution when referencing to concepts

Abstract:
Systems and processes for operating a virtual assistant programmed to refer to shared domain concepts using concept nodes are provided. In some examples, to process a textual representation of user speech using an active ontology having these concept nodes, a primary user intent can be determined from the textual representation of user speech. Concepts referred to by the primary user intent can be identified, and substrings of the textual representation of user speech corresponding to the concepts can be identified. Secondary user intents for the substrings can be determined and a task flow based on the primary user intent and the secondary user intents can be generated and performed.

Claims:
What is claimed is: 
     
       1. A method for operating a virtual assistant on an electronic device, the method comprising:
 receiving an audio input comprising user speech; 
 converting the user speech of the audio input into a textual representation of the user speech; 
 determining a primary user intent for the textual representation; 
 identifying a first type of concept referred to by the primary user intent; 
 identifying a first substring from the textual representation corresponding to the first type of concept; 
 determining a secondary user intent for the first substring; and 
 performing a task flow comprising one or more tasks based at least in part on the primary user intent for the textual representation and the secondary user intent for the first substring. 
 
     
     
       2. The method of  claim 1 , wherein determining the primary user intent for the textual representation comprises:
 determining a confidence score for a plurality of interpretations of the textual representation; and 
 determining the primary user intent for the textual representation based on an interpretation of the plurality of interpretations of the textual representation having the highest confidence score. 
 
     
     
       3. The method of  claim 1 , wherein the first type of concept comprises a place, a time, an event, or a person. 
     
     
       4. The method of  claim 1 , wherein identifying the first substring from the textual representation comprises:
 identifying one or more predetermined words corresponding to the first type of concept in the textual representation; and 
 identifying the first substring based on the one or more predetermined words corresponding to the first type of concept. 
 
     
     
       5. The method of  claim 1 , wherein determining the secondary user intent for the first substring comprises:
 determining a confidence score for a plurality of interpretations of the first substring; and 
 determining the secondary user intent for the first substring based on an interpretation of the plurality of interpretations of the first substring having the highest confidence score. 
 
     
     
       6. The method of  claim 5 , wherein the plurality of interpretations of the first substring exclude interpretations from domains that do not output the first type of concept. 
     
     
       7. The method of  claim 1 , further comprising:
 identifying a second type of concept referred to by the primary user intent; identifying a second substring from the textual representation corresponding to the second type of concept; and 
 determining a secondary user intent for the second substring, wherein performing the task flow is further based on the secondary user intent for the second substring. 
 
     
     
       8. The method of  claim 7 , wherein the second type of concept comprises a place, a time, an event, or a person. 
     
     
       9. The method of  claim 7 , wherein identifying the second substring from the textual representation comprises:
 identifying one or more predetermined words corresponding to the second type of concept in the textual representation; and 
 identifying the second substring based on the one or more predetermined words corresponding to the second type of concept. 
 
     
     
       10. The method of  claim 7 , wherein determining the secondary user intent for the second substring comprises:
 determining a confidence score for a plurality of interpretations of the second substring; and 
 determining the secondary user intent for the second substring based on an interpretation of the plurality of interpretations of the second substring having the highest confidence score. 
 
     
     
       11. The method of  claim 10 , wherein the plurality of interpretations of the second substring exclude interpretations from domains that do not output the second type of concept. 
     
     
       12. The method of a  claim 7 , further comprising:
 identifying a third type of concept referred to by the secondary user intent for the first substring; 
 identifying a third substring from the first substring corresponding to the third type of concept; and 
 determining a tertiary user intent for the third substring, wherein performing the task flow is further based on the tertiary user intent for the third substring. 
 
     
     
       13. The method of  claim 12 , wherein the third type of concept comprises a place, a time, an event, or a person. 
     
     
       14. The method of  claim 12 , wherein identifying the third substring from the first substring comprises:
 identifying one or more predetermined words corresponding to the third type of concept in the first substring; and 
 identifying the third substring based on the one or more predetermined words corresponding to the third type of concept. 
 
     
     
       15. The method of  claim 12 , wherein determining the tertiary user intent for the third substring comprises:
 determining a confidence score for a plurality of interpretations of the third substring; and 
 determining the tertiary user intent for the third substring based on an interpretation of the plurality of interpretations of the third substring having the highest confidence score. 
 
     
     
       16. The method of  claim 15 , wherein the plurality of interpretations of the third substring exclude interpretations from domains that do not output the third type of concept. 
     
     
       17. The method of  claim 1 , wherein performing the task flow comprises:
 identifying a primary task flow to accomplish the primary user intent; 
 identifying one or more constraints associated with the primary task flow; 
 identifying one or more queries, programs, methods, services, or APIs that satisfy the one or more constraints associated with the primary task flow; and 
 generating the task flow from the primary task flow and the identified one or more queries, programs, methods, services, or APIs. 
 
     
     
       18. The method of  claim 17 , wherein the one or more constraints comprises a type of input required by the primary task flow, and wherein the identified one or more queries, programs, methods, services, or APIs are capable of providing the type of input required by the primary task flow. 
     
     
       19. The method of  claim 1 , further comprising:
 parsing the textual representation, wherein determining the primary user intent for the textual representation comprises determining the primary user intent for the parsed textual representation; and 
 parsing the first substring, wherein determining the secondary user intent for the first substring comprises determining the secondary user intent for the parsed first substring. 
 
     
     
       20. The method of  claim 1 , wherein identifying the first type of concept referred to by the primary user intent is performed after determining the primary user intent. 
     
     
       21. An electronic device, comprising:
 one or more processors; 
 memory; and 
 one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for:
 receiving an audio input comprising user speech; 
 converting the user speech of the audio input into a textual representation of the user speech; 
 determining a primary user intent for the textual representation; 
 identifying a first type of concept referred to by the primary user intent; 
 identifying a first substring from the textual representation corresponding to the first type of concept; 
 determining a secondary user intent for the first substring; and 
 performing a task flow comprising one or more tasks based at least in part on the primary user intent for the textual representation and the secondary user intent for the first substring. 
 
 
     
     
       22. The device of  claim 21 , wherein determining the primary user intent for the textual representation comprises:
 determining a confidence score for a plurality of interpretations of the textual representation; and 
 determining the primary user intent for the textual representation based on an interpretation of the plurality of interpretations of the textual representation having the highest confidence score. 
 
     
     
       23. The device of  claim 21 , wherein the first type of concept comprises a place, a time, an event, or a person. 
     
     
       24. The device of  claim 21 , wherein identifying the first substring from the textual representation comprises:
 identifying one or more predetermined words corresponding to the first type of concept in the textual representation; and 
 identifying the first substring based on the one or more predetermined words corresponding to the first type of concept. 
 
     
     
       25. The device of  claim 21 , wherein determining the secondary user intent for the first substring comprises:
 determining a confidence score for a plurality of interpretations of the first substring; and 
 determining the secondary user intent for the first substring based on an interpretation of the plurality of interpretations of the first substring having the highest confidence score. 
 
     
     
       26. The device of  claim 25 , wherein the plurality of interpretations of the first substring exclude interpretations from domains that do not output the first type of concept. 
     
     
       27. The device of  claim 21 , wherein the one or more programs further include instructions for:
 identifying a second type of concept referred to by the primary user intent; 
 identifying a second substring from the textual representation corresponding to the second type of concept; and 
 determining a secondary user intent for the second substring, wherein performing the task flow is further based on the secondary user intent for the second substring. 
 
     
     
       28. The device of  claim 27 , wherein the second type of concept comprises a place, a time, an event, or a person. 
     
     
       29. The device of  claim 27 , wherein identifying the second substring from the textual representation comprises:
 identifying one or more predetermined words corresponding to the second type of concept in the textual representation; and 
 identifying the second substring based on the one or more predetermined words corresponding to the second type of concept. 
 
     
     
       30. The device of  claim 27 , wherein determining the secondary user intent for the second substring comprises:
 determining a confidence score for a plurality of interpretations of the second substring; and 
 determining the secondary user intent for the second substring based on an interpretation of the plurality of interpretations of the second substring having the highest confidence score. 
 
     
     
       31. The device of  claim 30 , wherein the plurality of interpretations of the second substring exclude interpretations from domains that do not output the second type of concept. 
     
     
       32. The device of a  claim 27 , wherein the one or more programs further include instructions for:
 identifying a third type of concept referred to by the secondary user intent for the first substring; 
 identifying a third substring from the first substring corresponding to the third type of concept; and 
 determining a tertiary user intent for the third substring, wherein performing the task flow is further based on the tertiary user intent for the third substring. 
 
     
     
       33. The device of  claim 32 , wherein the third type of concept comprises a place, a time, an event, or a person. 
     
     
       34. The device of  claim 32 , wherein identifying the third substring from the first substring comprises:
 identifying one or more predetermined words corresponding to the third type of concept in the first substring; and 
 identifying the third substring based on the one or more predetermined words corresponding to the third type of concept. 
 
     
     
       35. The device of  claim 32 , wherein determining the tertiary user intent for the third substring comprises:
 determining a confidence score for a plurality of interpretations of the third substring; and 
 determining the tertiary user intent for the third substring based on an interpretation of the plurality of interpretations of the third substring having the highest confidence score. 
 
     
     
       36. The device of  claim 35 , wherein the plurality of interpretations of the third substring exclude interpretations from domains that do not output the third type of concept. 
     
     
       37. The device of  claim 21 , wherein performing the task flow comprises:
 identifying a primary task flow to accomplish the primary user intent; 
 identifying one or more constraints associated with the primary task flow; 
 identifying one or more queries, programs, methods, services, or APIs that satisfy the one or more constraints associated with the primary task flow; and 
 generating the task flow from the primary task flow and the identified one or more queries, programs, methods, services, or APIs. 
 
     
     
       38. The device of  claim 37 , wherein the one or more constraints comprises a type of input required by the primary task flow, and wherein the identified one or more queries, programs, methods, services, or APIs are capable of providing the type of input required by the primary task flow. 
     
     
       39. A non-transitory computer-readable storage medium comprising computer-executable instructions for:
 receiving an audio input comprising user speech; 
 converting the user speech of the audio input into a textual representation of the user speech; 
 determining a primary user intent for the textual representation; 
 identifying a first type of concept referred to by the primary user intent; 
 identifying a first substring from the textual representation corresponding to the first type of concept; 
 determining a secondary user intent for the first substring; and 
 performing a task flow comprising one or more tasks based at least in part on the primary user intent for the textual representation and the secondary user intent for the first substring. 
 
     
     
       40. The computer-readable storage medium of  claim 39 , wherein determining the primary user intent for the textual representation comprises:
 determining a confidence score for a plurality of interpretations of the textual representation; and 
 determining the primary user intent for the textual representation based on an interpretation of the plurality of interpretations of the textual representation having the highest confidence score. 
 
     
     
       41. The computer-readable storage medium of  claim 39 , wherein the first type of concept comprises a place, a time, an event, or a person. 
     
     
       42. The computer-readable storage medium of  claim 39 , wherein identifying the first substring from the textual representation comprises:
 identifying one or more predetermined words corresponding to the first type of concept in the textual representation; and 
 identifying the first substring based on the one or more predetermined words corresponding to the first type of concept. 
 
     
     
       43. The computer-readable storage medium of  claim 39 , wherein determining the secondary user intent for the first substring comprises:
 determining a confidence score for a plurality of interpretations of the first substring; and 
 determining the secondary user intent for the first substring based on an interpretation of the plurality of interpretations of the first substring having the highest confidence score. 
 
     
     
       44. The computer-readable storage medium of  claim 43 , wherein the plurality of interpretations of the first substring exclude interpretations from domains that do not output the first type of concept. 
     
     
       45. The computer-readable storage medium of  claim 39 , further comprising instructions for:
 identifying a second type of concept referred to by the primary user intent; 
 identifying a second substring from the textual representation corresponding to the second type of concept; and 
 determining a secondary user intent for the second substring, wherein performing the task flow is further based on the secondary user intent for the second substring. 
 
     
     
       46. The computer-readable storage medium of  claim 45 , wherein the second type of concept comprises a place, a time, an event, or a person. 
     
     
       47. The computer-readable storage medium of  claim 45 , wherein identifying the second substring from the textual representation comprises:
 identifying one or more predetermined words corresponding to the second type of concept in the textual representation; and 
 identifying the second substring based on the one or more predetermined words corresponding to the second type of concept. 
 
     
     
       48. The computer-readable storage medium of  claim 45 , wherein determining the secondary user intent for the second substring comprises:
 determining a confidence score for a plurality of interpretations of the second substring; and 
 determining the secondary user intent for the second substring based on an interpretation of the plurality of interpretations of the second substring having the highest confidence score. 
 
     
     
       49. The computer-readable storage medium of  claim 48 , wherein the plurality of interpretations of the second substring exclude interpretations from domains that do not output the second type of concept. 
     
     
       50. The computer-readable storage medium of a  claim 45 , further comprising instructions for:
 identifying a third type of concept referred to by the secondary user intent for the first substring; 
 identifying a third substring from the first substring corresponding to the third type of concept; and 
 determining a tertiary user intent for the third substring, wherein performing the task flow is further based on the tertiary user intent for the third substring. 
 
     
     
       51. The computer-readable storage medium of  claim 50 , wherein the third type of concept comprises a place, a time, an event, or a person. 
     
     
       52. The computer-readable storage medium of  claim 50 , wherein identifying the third substring from the first substring comprises:
 identifying one or more predetermined words corresponding to the third type of concept in the first substring; and 
 identifying the third substring based on the one or more predetermined words corresponding to the third type of concept. 
 
     
     
       53. The computer-readable storage medium of  claim 50 , wherein determining the tertiary user intent for the third substring comprises:
 determining a confidence score for a plurality of interpretations of the third substring; and 
 determining the tertiary user intent for the third substring based on an interpretation of the plurality of interpretations of the third substring having the highest confidence score. 
 
     
     
       54. The computer-readable storage medium of  claim 53 , wherein the plurality of interpretations of the third substring exclude interpretations from domains that do not output the third type of concept. 
     
     
       55. The computer-readable storage medium of  claim 39 , wherein performing the task flow comprises:
 identifying a primary task flow to accomplish the primary user intent; 
 identifying one or more constraints associated with the primary task flow; 
 identifying one or more queries, programs, computer-readable storage mediums, services, or APIs that satisfy the one or more constraints associated with the primary task flow; and 
 generating the task flow from the primary task flow and the identified one or more queries, programs, methods, services, or APIs. 
 
     
     
       56. The computer-readable storage medium of  claim 55 , wherein the one or more constraints comprises a type of input required by the primary task flow, and wherein the identified one or more queries, programs, methods, services, or APIs are capable of providing the type of input required by the primary task flow.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims priority from U.S. Provisional Ser. No. 62/006,036, filed on May 30, 2014, entitled BETTER RESOLUTION WHEN REFERENCING TO CONCEPTS, which is hereby incorporated by reference in its entirety for all purposes. 
    
    
     FIELD 
     This relates generally to natural language processing and, more specifically, to modeling domains to refer to cross-domain concepts. 
     BACKGROUND 
     Intelligent automated assistants (or virtual assistants) provide an intuitive interface between users and electronic devices. These assistants can allow users to interact with devices or systems using natural language in spoken and/or text forms. For example, a user can access the services of an electronic device by providing a spoken user input in natural language form to a virtual assistant associated with the electronic device. The virtual assistant can perform natural language processing on the spoken user input to infer the user&#39;s intent and operationalize the user&#39;s intent into tasks. The tasks can then be performed by executing one or more functions of the electronic device, and a relevant output can be returned to the user in natural language form. 
     Some virtual assistants can be implemented using active ontologies to simplify the software engineering and data maintenance of the virtual assistant systems. Active ontologies can represent an integration of data modeling and execution environments for assistants and can provide a framework to tie together the various sources of models and data (e.g., domain concepts, task flows, vocabulary, language pattern recognizers, dialog context, user personal information, mappings from domain and task requests to external services, and the like). Implementing a virtual assistant in this way allows the virtual assistant to quickly and accurately respond to a user input in natural language form. However, current active ontology architectures can make it difficult to add new knowledge domains representing a subject, genre, area of interest, group of similar requests, or the like, to the active ontology. 
     SUMMARY 
     Systems and processes for operating a virtual assistant are provided. One example process can include receiving a textual representation of user speech and determining a primary user intent for the textual representation of user speech. The process can further include identifying a first type of concept referred to by the primary user intent, identifying a first substring from the textual representation of user speech corresponding to the first type of concept, and determining a secondary user intent for the first substring. The process can further include performing a task flow comprising one or more tasks based at least in part on the primary user intent for the textual representation of user speech and the secondary user intent for the first substring. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an exemplary environment in which a virtual assistant can operate according to various examples. 
         FIG. 2  illustrates an exemplary user device according to various examples. 
         FIG. 3  illustrates a block diagram of an exemplary virtual assistant according to various examples. 
         FIG. 4  illustrates a portion of an exemplary active ontology according to various examples. 
         FIG. 5  illustrates a portion of another exemplary active ontology according to various examples. 
         FIG. 6  illustrates an exemplary process for operating a virtual assistant according to various examples. 
         FIG. 7  illustrates a functional block diagram of an electronic device configured to operate a virtual assistant according to various examples. 
     
    
    
     DETAILED DESCRIPTION 
     In the following description of examples, reference is made to the accompanying drawings in which it is shown by way of illustration specific examples that can be practiced. It is to be understood that other examples can be used and structural changes can be made without departing from the scope of the various examples. 
     This relates to systems and processes for operating a virtual assistant programmed to refer to shared domain concepts using concept nodes. A concept node can represent a particular type of concept, such as a person, place, time, event, or the like, and can be used within a domain of an active ontology to refer to a concept without having to identify all possible sources for that concept, and without associated logic to select the appropriate knowledge representation of user intent from the various domains for a given user input. In some examples, to process a textual representation of user speech using an active ontology having these concept nodes, a primary user intent can be determined from the textual representation of user speech. Concepts referred to by the primary user intent can be identified, and substrings of the textual representation of user speech corresponding to the concepts can be identified. Secondary user intents for the substrings can be determined and a task flow based on the primary user intent and the secondary user intents can be generated and performed. 
     System Overview 
       FIG. 1  illustrates exemplary system  100  for implementing a virtual assistant according to various examples. The terms “virtual assistant,” “digital assistant,” “intelligent automated assistant,” or “automatic digital assistant” can refer to any information processing system that interprets natural language input in spoken and/or textual form to infer user intent, and performs actions based on the inferred user intent. For example, to act on an inferred user intent, the system can perform one or more of the following: identifying a task flow with steps and parameters designed to accomplish the inferred user intent; inputting specific requirements from the inferred user intent into the task flow; executing the task flow by invoking programs, methods, services, APIs, or the like; and generating output responses to the user in an audible (e.g., speech) and/or visual form. 
     A virtual assistant can be capable of accepting a user request at least partially in the form of a natural language command, request, statement, narrative, and/or inquiry. Typically, the user request seeks either an informational answer or performance of a task by the virtual assistant. A satisfactory response to the user request can include provision of the requested informational answer, performance of the requested task, or a combination of the two. For example, a user can ask the virtual assistant a question, such as “Where am I right now?” Based on the user&#39;s current location, the virtual assistant can answer, “You are in Central Park.” The user can also request the performance of a task, for example, “Please remind me to call Mom at 4 p.m. today.” In response, the virtual assistant can acknowledge the request and then create an appropriate reminder item in the user&#39;s electronic schedule. During the performance of a requested task, the virtual assistant can sometimes interact with the user in a continuous dialogue involving multiple exchanges of information over an extended period of time. There are numerous other ways of interacting with a virtual assistant to request information or performance of various tasks. In addition to providing verbal responses and taking programmed actions, the virtual assistant can also provide responses in other visual or audio forms (e.g., as text, alerts, music, videos, animations, etc.). 
     An example of a virtual assistant is described in Applicants&#39; U.S. Utility application Ser. No. 12/987,982 for “Intelligent Automated Assistant,” filed Jan. 10, 2011, the entire disclosure of which is incorporated herein by reference. 
     As shown in  FIG. 1 , in some examples, a virtual assistant can be implemented according to a client-server model. The virtual assistant can include a client-side portion executed on a user device  102 , and a server-side portion executed on a server system  110 . User device  102  can include any electronic device, such as a mobile phone, tablet computer, portable media player, desktop computer, laptop computer, PDA, television, television set-top box, wearable electronic device, or the like, and can communicate with server system  110  through one or more networks  108 , which can include the Internet, an intranet, or any other wired or wireless public or private network. The client-side portion executed on user device  102  can provide client-side functionalities, such as user-facing input and output processing and communications with server system  110 . Server system  110  can provide server-side functionalities for any number of clients residing on a respective user device  102 . 
     Server system  110  can include one or more virtual assistant servers  114  that can include a client-facing I/O interface  122 , one or more processing modules  118 , data and model storage  120 , and an I/O interface to external services  116 . The client-facing I/O interface  122  can facilitate the client-facing input and output processing for virtual assistant server  114 . The one or more processing modules  118  can utilize data and model storage  120  to determine the user&#39;s intent based on natural language input, and perform task execution based on inferred user intent. In some examples, virtual assistant server  114  can communicate with external services  124 , such as telephony services, calendar services, information services, messaging services, navigation services, and the like, through network(s)  108  for task completion or information acquisition. The I/O interface to external services  116  can facilitate such communications. 
     Server system  110  can be implemented on one or more standalone data processing devices or a distributed network of computers. In some examples, server system  110  can employ various virtual devices and/or services of third party service providers (e.g., third-party cloud service providers) to provide the underlying computing resources and/or infrastructure resources of server system  110 . 
     Although the functionality of the virtual assistant is shown in  FIG. 1  as including both a client-side portion and a server-side portion, in some examples, the functions of the assistant can be implemented as a standalone application installed on a user device. In addition, the division of functionalities between the client and server portions of the virtual assistant can vary in different examples. For instance, in some examples, the client executed on user device  102  can be a thin-client that provides only user-facing input and output processing functions, and delegates all other functionalities of the virtual assistant to a backend server. 
     User Device 
       FIG. 2  is a block diagram of a user-device  102  according to various examples. As shown, user device  102  can include a memory interface  202 , one or more processors  204 , and a peripherals interface  206 . The various components in user device  102  can be coupled together by one or more communication buses or signal lines. User device  102  can further include various sensors, subsystems, and peripheral devices that are coupled to the peripherals interface  206 . The sensors, subsystems, and peripheral devices gather information and/or facilitate various functionalities of user device  102 . 
     For example, user device  102  can include a motion sensor  210 , a light sensor  212 , and a proximity sensor  214  coupled to peripherals interface  206  to facilitate orientation, light, and proximity sensing functions. One or more other sensors  216 , such as a positioning system (e.g., a GPS receiver), a temperature sensor, a biometric sensor, a gyroscope, a compass, an accelerometer, and the like, are also connected to peripherals interface  206 , to facilitate related functionalities. 
     In some examples, a camera subsystem  220  and an optical sensor  222  can be utilized to facilitate camera functions, such as taking photographs and recording video clips. Communication functions can be facilitated through one or more wired and/or wireless communication subsystems  224 , which can include various communication ports, radio frequency receivers and transmitters, and/or optical (e.g., infrared) receivers and transmitters. An audio subsystem  226  can be coupled to speakers  228  and a microphone  230  to facilitate voice-enabled functions, such as voice recognition, voice replication, digital recording, and telephony functions. 
     In some examples, user device  102  can further include an I/O subsystem  240  coupled to peripherals interface  206 . I/O subsystem  240  can include a touch screen controller  242  and/or other input controller(s)  244 . Touch-screen controller  242  can be coupled to a touch screen  246 . Touch screen  246  and the touch screen controller  242  can, for example, detect contact and movement or break thereof using any of a plurality of touch sensitivity technologies, such as capacitive, resistive, infrared, and surface acoustic wave technologies, proximity sensor arrays, and the like. Other input controller(s)  244  can be coupled to other input/control devices  248 , such as one or more buttons, rocker switches, a thumb-wheel, an infrared port, a USB port, and/or a pointer device such as a stylus. 
     In some examples, user device  102  can further include a memory interface  202  coupled to memory  250 . Memory  250  can include any electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, a portable computer diskette (magnetic), a random access memory (RAM) (magnetic), a read-only memory (ROM) (magnetic), an erasable programmable read-only memory (EPROM) (magnetic), a portable optical disc such as CD, CD-R, CD-RW, DVD, DVD-R, or DVD-RW, or flash memory such as compact flash cards, secured digital cards, USB memory devices, memory sticks, and the like. In some examples, a non-transitory computer-readable storage medium of memory  250  can be used to store instructions (e.g., for performing some or all of process  600 , described below) for use by or in connection with an instruction execution system, apparatus, or device, such as a computer-based system, processor-containing system, or other system that can fetch the instructions from the instruction execution system, apparatus, or device, and execute the instructions. In other examples, the instructions (e.g., for performing process  600 , described below) can be stored on a non-transitory computer-readable storage medium of server system  110 , or can be divided between the non-transitory computer-readable storage medium of memory  250  and the non-transitory computer-readable storage medium of server system  110 . In the context of this document, a “non-transitory computer readable storage medium” can be any medium that can contain or store the program for use by or in connection with the instruction execution system, apparatus, or device. 
     In some examples, the memory  250  can store an operating system  252 , a communication module  254 , a graphical user interface module  256 , a sensor processing module  258 , a phone module  260 , and applications  262 . Operating system  252  can include instructions for handling basic system services and for performing hardware dependent tasks. Communication module  254  can facilitate communicating with one or more additional devices, one or more computers, and/or one or more servers. Graphical user interface module  256  can facilitate graphic user interface processing. Sensor processing module  258  can facilitate sensor related processing and functions. Phone module  260  can facilitate phone-related processes and functions. Application module  262  can facilitate various functionalities of user applications, such as electronic-messaging, web browsing, media processing, navigation, imaging, and/or other processes and functions. 
     As described herein, memory  250  can also store client-side virtual assistant instructions (e.g., in a virtual assistant client module  264 ) and various user data  266  (e.g., user-specific vocabulary data, preference data, and/or other data, such as the user&#39;s electronic address book, to-do lists, shopping lists, etc.) to provide the client-side functionalities of the virtual assistant. 
     In various examples, virtual assistant client module  264  can be capable of accepting voice input (e.g., speech input), text input, touch input, and/or gestural input through various user interfaces (e.g., I/O subsystem  240 , audio subsystem  226 , or the like) of user device  102 . Virtual assistant client module  264  can also be capable of providing output in audio (e.g., speech output), visual, and/or tactile forms. For example, output can be provided as voice, sound, alerts, text messages, menus, graphics, videos, animations, vibrations, and/or combinations of two or more of the above. During operation, virtual assistant client module  264  can communicate with the virtual assistant server using communication subsystem  224 . 
     In some examples, virtual assistant client module  264  can utilize the various sensors, subsystems, and peripheral devices to gather additional information from the surrounding environment of user device  102  to establish a context associated with a user, the current user interaction, and/or the current user input. In some examples, virtual assistant client module  264  can provide the contextual information or a subset thereof with the user input to the virtual assistant server to help infer the user&#39;s intent. The virtual assistant can also use the contextual information to determine how to prepare and deliver outputs to the user. 
     In some examples, the contextual information that accompanies the user input can include sensor information, such as lighting, ambient noise, ambient temperature, images or videos of the surrounding environment, distance to another object, and the like. The contextual information can further include information associated with the physical state of user device  102  (e.g., device orientation, device location, device temperature, power level, speed, acceleration, motion patterns, cellular signal strength, etc.) or the software state of user device  102  (e.g., running processes, installed programs, past and present network activities, background services, error logs, resources usage, etc.). Any of these types of contextual information can be provided to the virtual assistant server  114  as contextual information associated with a user input. 
     In some examples, virtual assistant client module  264  can selectively provide information (e.g., user data  266 ) stored on user device  102  in response to requests from the virtual assistant server  114 . Virtual assistant client module  264  can also elicit additional input from the user via a natural language dialogue or other user interfaces upon request by virtual assistant server  114 . Virtual assistant client module  264  can pass the additional input to virtual assistant server  114  to help virtual assistant server  114  in intent inference and/or fulfillment of the user&#39;s intent expressed in the user request. 
     In various examples, memory  250  can include additional instructions or fewer instructions. Furthermore, various functions of user device  102  can be implemented in hardware and/or in firmware, including in one or more signal processing and/or application specific integrated circuits. 
     Conceptual Architecture 
       FIG. 3  illustrates a simplified block diagram of an example virtual assistant  300  that can be implemented using system  100 . Virtual assistant  300  can receive user input  304  in the form of an audio or textual representation of the user&#39;s natural language input and, optionally, contextual information  306  to generate an output response  308  to the user in audio or text form, as well as other actions  310  (e.g., sending an email, setting an alarm, etc.) performed in response to the user input. Virtual assistant  300  can include multiple different types of components, devices, modules, processes, systems, and the like, which, for example, may be implemented and/or instantiated via the use of hardware and/or combinations of hardware and software. For example, as shown in  FIG. 3 , virtual assistant  300  can include one or more of the following types of systems, components, devices, processes, and the like (or combinations thereof): one or more active ontologies  350 ; active input elicitation component(s)  394 ; short term personal memory component(s)  352 ; long-term personal memory component(s)  354 ; domain models component(s)  356 ; vocabulary component(s)  358 ; language pattern recognizer(s) component(s)  360 ; language interpreter component(s)  370 ; domain entity database(s)  372 ; dialog flow processor component(s)  380 ; services orchestration component(s)  382 ; services component(s)  384 ; task flow models component(s)  386 ; dialog flow models component(s)  387 ; service models component(s)  388 ; and output processor component(s)  390 . A detailed description of these components can be found in Applicants&#39; U.S. Utility application Ser. No. 12/987,982 for “Intelligent Automated Assistant,” filed Jan. 10, 2011. 
     Active Ontology 
     As mentioned above, active ontology  350  can represent an integration of data modeling and execution environments for assistants and can provide a framework to tie together the various sources of models and data (e.g., domain concepts, task flows, vocabulary, language pattern recognizers, dialog context, user personal information, mappings from domain and task requests to external services, and the like).  FIG. 4  illustrates a portion of a typical active ontology  400  that can be used as active ontology  350  in virtual assistant  300 . In particular, the displayed portion of active ontology  400  illustrates the way that concepts from different domains can be tied together in a typical active ontology. 
     As shown in  FIG. 4 , active ontology  400  includes a weather domain  402  having a weather node  404 . Weather node  404  is connected to time node  406  and place node  414 , indicating that weather has a concept of both time and place (e.g., weather near the hockey game Friday night). In typical active ontologies like that shown in  FIG. 4 , domains that refer to a concept, such as place, time, person, event, or the like, can be programmed to specifically refer to every other domain within the active ontology that can produce that concept. These domains can also be programmed to include logic for calling the referenced domains, receiving the knowledge representations of user intent generated by those domains, identifying the knowledge representations of user intent that is most likely to provide the appropriate concept, and extracting the relevant concept from that knowledge representation of user intent. 
     To illustrate, time node  406  is shown as being connected to logic  408 , which is connected to sports domain  418 , reminder domain  420 , business domain  422 , and email domain  424 . This configuration indicates that the time concept of weather node  404  can be produced by sports domain  418 , reminder domain  420 , business domain  422 , or email domain  424 . For example, the time concept of weather node  404  can be referenced with respect to information contained in sports domain  418  (e.g., weather during a sporting event), information contained in reminder domain  420  (e.g., weather at a time of a reminder set by the user), information contained in business domain  422  (e.g., weather when a particular business is set to open), or information contained in email domain  424  (e.g., weather when an email was received). Logic  408  can be used to identify the knowledge representation of user intent produced by sports domain  418 , reminder domain  420 , business domain  422 , or email domain  424  that is most likely to provide the appropriate time concept and to extract the time concept from that knowledge representation of user intent. 
     Similarly, place node  414  is shown as being connected to logic  416 , which is connected to sports domain  418 , reminder domain  420 , and business domain  422 . This configuration indicates that the place concept of weather node  404  can be produced by sports domain  418 , reminder domain  420 , or business domain  422 . For example, the place concept of weather node  404  can be referenced with respect to information contained in sports domain  418  (e.g., weather at a sports stadium), information contained in reminder domain  420  (e.g., weather at a location associated with a reminder set by the user), or information contained in business domain  422  (e.g., weather at the headquarters of a business). Logic  416  can be used to identify the knowledge representation of user intent produced by sports domain  418 , reminder domain  420 , or business domain  422  that is most likely to provide the appropriate place concept and to extract the place concept from that knowledge representation of user intent. 
     A domain that is configured in a manner similar to that of weather domain  402 , shown in  FIG. 4 , can be used to process user inputs that reference concepts with respect to information contained in the specific domains that the domain is programmed to reference. However, it can be problematic to add new domains to this type of active ontology because any concepts referred to by the new domain must be programmed to refer to every other existing domain within the active ontology that can produce those concepts. Additionally, the existing domains within the active ontology would need to be modified to refer to any concepts produced by the new domain. For example, to add a restaurant domain that both refers to and produces a time and place concept, the restaurant domain would have to be programmed to specifically refer to weather domain  402 , sports domain  418 , reminder domain  420 , business domain  422 , and email domain  424  for the time concept, and to refer to weather domain  402 , sports domain  418 , reminder domain  420 , and business domain  422  for the place concept. The restaurant domain would also need to be programmed with logic for calling the referenced domains, receiving the knowledge representations of user intent generated by those domains, identifying the knowledge representations of user intent that are most likely to provide the appropriate concepts, and extracting the relevant concepts from those knowledge representations of user intent. The logic of the existing weather domain  402 , sports domain  418 , reminder domain  420 , business domain  422 , and email domain  424  would have to similarly be modified. Thus, referencing concepts between domains in this way may be overly burdensome for active ontologies having numerous domains. 
     While not shown, it should be appreciated that weather domain  402  can further include other types of weather-related information, such as vocabulary, entities, other concepts, properties, task flows that can be performed, dialog flows that can be performed, services that can be invoked, relationships between any of the forgoing, or the like. The other domains of active ontology  400  can similarly include any type of information related to their respective subjects, genres, areas of interest, groups of similar requests, or the like. 
     Concept Node 
       FIG. 5  illustrates a portion of an active ontology  500  that is similar to active ontology  400 , but that includes “concept nodes” (e.g., time concept node  502  and place concept node  506 ) for referring to concepts within its various domains. A concept node can represent a particular type of concept, such as a person, place, time, event, or the like, and can be used within a domain of an active ontology to refer to a concept without having to identify all possible sources for that concept, and without associated logic to select the appropriate knowledge representation of user intent from the various domains for a given user input. 
     A concept node can include a non-terminal node having a single terminal node and a semantic tag that defines the type of concept that the concept node supports (e.g., person, place, time, event, or the like). The terminal node can be configured to identify portions or substrings of a user input that likely refer to the concept type of concept node. In some examples, the terminal node can identify substrings of a user input that likely refer to a concept type by performing a variable match process using one or more seed words that are likely associated with the type of concept. For example, a terminal node for a place concept node can include the seed word “near,” indicating that the portion of an utterance following the word “near” likely refers to a place concept. Similarly, a terminal node for a time concept node can include the seed word “during,” indicating that the portion of an utterance following the word “during” likely refers to a time concept. When used to process the user input “what&#39;s the weather like near my brother&#39;s house during the Super Bowl?”, the terminal node for the place concept node can be used to identify “my brother&#39;s house” as a substring of the user input that likely refers to a place concept, and the terminal node for the time concept node can be used to identify “the Super Bowl” as a substring of the user input that likely refers to a time concept. It should be appreciated that identifying a substring of a user input that likely refers to a concept type can include identifying multiple potential substrings of the user input that could refer to the concept and selecting the potential substring having the highest confidence score as the substring of the user input that likely refers to the concept type. 
     While specific algorithms and seed words are provided above for the terminal nodes of a time concept node and a place concept node, it should be appreciated that terminal nodes having other algorithms and/or seed words for identifying substrings of a user input that correspond to a particular concept type can be used. Additionally, other types of concept nodes can be created and used in the domains of an active ontology by creating appropriate semantic tags for the concept nodes and defining their terminal nodes in such a way so as to identify substrings of an utterance that likely correspond to their respective concept types. 
     To illustrate the use of a concept node in an active ontology,  FIG. 5  shows active ontology  500  that, similar to active ontology  400 , includes sports domain  418 , reminder domain  420 , business domain  422 , email domain  424 , and weather domain  402  having weather node  404 . However, in contrast to active ontology  400 , weather node  404  in  FIG. 5  can instead be connected to time concept node  502  and place concept node  506  rather than time node  406  and place node  414 . Additionally, unlike time node  406  and place node  414  in  FIG. 4 , time concept node  502  and place concept node  506  need not refer to every other domain within active ontology  500  that can produce those concepts and do not require logic for selecting the appropriate knowledge representation of user intent from the various domains for a given user input. Instead, time concept node  502  and place concept node  506  can include terminal node  504  and terminal node  508 , respectively, which can be used to identify substrings of a user input that likely refer to the time and place concepts, respectively. 
     While only two concept nodes are shown, it should be appreciated that the domains of active ontology  500  can include any number and type of concept nodes, and any elements or nodes within those domains that refer to a concept can be connected to the appropriate concept node. Configuring active ontology  500  in this way simplifies the process of adding new domains to the active ontology. For example, to add a restaurant domain that both refers to and produces a time and place concept, the restaurant domain can simply be programmed to include a time concept node similar or identical to time concept node  502  and a place concept node similar or identical to place concept node  506 . Unlike adding the restaurant domain to active ontology  400 , the newly created restaurant domain does not need to be programmed to refer to weather domain  402 , sports domain  418 , reminder domain  420 , business domain  422 , and email domain  424  for the time concept, and does not need to be programmed to refer to weather domain  402 , sports domain  418 , reminder domain  420 , and business domain  422  for the place concept. Additionally, the existing weather domain  402 , sports domain  418 , reminder domain  420 , business domain  422 , and email domain  424  in active ontology  500  do not need to be modified to refer to the newly added restaurant domain. 
     Process for Operating a Virtual Assistant 
       FIG. 6  illustrates an exemplary process  600  for operating a virtual assistant programmed to refer to concepts using concept nodes according to various examples. In some examples, process  600  can be performed using a system similar or identical to system  100  and that utilizes an active ontology having concept nodes similar or identical to those shown in  FIG. 5 . 
     At block  602 , an audio input including user speech can be received at a user device. In some examples, a user device (e.g., user device  102 ) can receive audio input that includes a user&#39;s speech via a microphone (e.g., microphone  230 ). The microphone can convert the audio input into an analog or digital representation, and provide the audio data to one or more processors (e.g., processor(s)  204 ). 
     At block  604 , the user speech of the audio input can be converted into a textual representation of the user speech. The user speech can be converted using any known speech-to-text conversion process. In some examples, the user speech can be converted into the textual representation locally on the user device. In other examples, the user device can transmit data corresponding to the audio input to a remote server (e.g., server system  110 ) capable of performing the speech-to-text conversion process. 
     A multi-pass natural language process represented by blocks  606 ,  608 ,  610 , and  612  can be performed on the textual representation of user speech. Specifically, at block  606 , the textual representation of user speech can be received or accessed, and a first pass of the multi-pass natural language process can be performed to determine a primary user intent from the textual representation of user speech. As discussed in greater detail in Applicants&#39; U.S. Utility application Ser. No. 12/987,982 for “Intelligent Automated Assistant,” filed Jan. 10, 2011, determining user intent can include analyzing, by processing modules  118  using the various components of virtual assistant  300  shown in  FIG. 3 , the textual representation of user speech to identify possible parse results or interpretations for the textual representation of user speech. Generally, the parse results can include associations of data in the user input with concepts, relationships, properties, instances, and/or other nodes and/or data structures in models, databases, and/or other representations of user intent and context. The parse results can include syntactic parse results that associate data in the user input with structures that represent syntactic parts of speech, clauses, and phrases including multiword names, sentence structure, and/or other grammatical graph structures. The parse results can also include semantic parse results that associate data in the user input with structures that represent concepts, relationships, properties, entities, quantities, propositions, and/or other representations of meaning and user intent. Determining user intent can further include determining a confidence score for each of the alternative parse results (e.g., syntactic or semantic parse results) representing the likelihood that a particular parse result is the correct parse result to apply to the textual representation of user speech. The primary user intent can be determined based on the knowledge representation of user intent associated with the parse result having the highest confidence score. For example, the primary user intent can be determined to include the nodes associated with vocabulary, entities, concepts, properties, task flows that can be performed, dialog flows that can be performed, services that can be invoked, relationships between any of the forgoing, or the like, of the knowledge representation of user intent associated with the parse result having the highest confidence score. 
     At block  608 , a first type of concept referred to by the primary user intent determined at block  606  can be identified. In some examples, identifying the first type of concept referred to by the primary user intent can include searching the primary user intent structure for concept nodes similar or identical to those described above with respect to  FIG. 5 . For example, the primary user intent structure can be searched for a time concept node, place concept node, person concept node, event concept node, or the like. If a concept node is found within the primary user intent structure, the semantic tag that defines the type of concept associated with the concept node can be read to identify and store the first type of concept referred to by the primary user intent. 
     It should be appreciated that the primary user intent determined at block  606  can include any number and type of concept nodes. In these examples, block  608  can further include identifying those other types of concept nodes, reading their associated semantic tags, and recording the concept types indicated by the semantic tags. 
     At block  610 , a first substring from the textual representation of user speech that corresponds to the first type of concept identified at block  608  can be identified. In some examples, identifying the first substring can include performing a variable match using a terminal node of the concept node identified at block  608 . The terminal node can define how to match certain parts of a user input to a particular concept. In some examples, the terminal node can define one or more seed words that are likely associated with a particular type of concept. For example, a terminal node for a place concept node can include the seed word “near,” indicating that the portion of an utterance following the word “near” likely refers to a place concept. Similarly, a terminal node for a time concept node can include the seed word “during,” indicating that the portion of an utterance following the word “during” likely refers to a time concept. When used to process the user input “what&#39;s the weather like near my brother&#39;s house during the Super Bowl?”, the terminal node for the place concept node can be used to identify “my brother&#39;s house” as a substring of the user input that likely refers to a place concept, and the terminal node for the time concept node can be used to identify “the Super Bowl” as a substring of the user input that likely refers to a time concept. It should be appreciated that identifying a substring of a user input that likely refers to a concept type can include identifying multiple potential substrings of the user input that could refer to the concept and selecting the potential substring having the highest confidence score as the substring of the user input that likely refers to the concept type. 
     In some examples, more than one type of concept can be identified at block  608 . In these examples, block  610  can further include identifying substrings from the textual representation of user speech that correspond to those types of concepts. The terminal nodes of the concept nodes associated with those types of concepts can be used to identify the substrings by performing, for example, a variable match process using seed words. 
     At block  612 , a second pass of the multi-pass natural language process can be performed to determine a secondary user intent for the first substring identified at block  610 . In some examples, the secondary user intent for the unparsed first substring can be determined in a manner similar or identical to that used to determine the primary user intent for the textual representation of user speech at block  606 . For example, the first substring can be treated as an input to the virtual assistant, and the virtual assistant can analyze, using processing modules  118  and the various components of virtual assistant  300  shown in  FIG. 3 , the first substring to identify possible parse results for the textual representation of user speech in a manner similar or identical to that described above with respect to block  606 . Determining the secondary user intent can further include determining a confidence score for each of the alternative parse results representing the likelihood that a particular parse result is the correct parse result to apply to the first substring. The secondary user intent can be determined based on the parse result having the highest confidence score. For example, the secondary user intent can be determined to include the nodes associated with vocabulary, entities, concepts, properties, task flows that can be performed, dialog flows that can be performed, services that can be invoked, relationships between any of the forgoing, or the like, of the knowledge representation of user intent associated with the parse result having the highest confidence score. 
     In some examples, to reduce the amount of processing required, determining the secondary user intent at block  610  can include considering only possible parse results from domains that can potentially output that type of concept. For example, if determining the secondary user intent for a first substring that corresponds to a place concept, possible parse results or interpretations from the email domain can be excluded from consideration since the email domain may not output a place concept. 
     In some examples, more than one type of concept can be identified at block  608  and more than one substring can be identified from the textual representation of user speech at block  610  that correspond to these concepts. In these examples, block  612  can further include determining a secondary user intent for the additional substrings. For example, the additional substrings can be input into the virtual assistant and analyzed, using processing modules  118  and the various components of virtual assistant  300  shown in  FIG. 3 , to identify possible parse results for the substrings in a manner similar or identical to that of the first substring. Determining the secondary user intent can further include determining a confidence score for each of the alternative parse results representing the likelihood that a particular parse result is the correct parse result to apply to the additional substrings. The secondary user intent for the additional substrings can be determined based on the respective parse result having the highest confidence score. 
     In some examples, a concept identified at block  608  can include a sub-concept. In these examples, blocks  608 ,  610 , and  612  can be recursively performed to identify the sub-concept from the secondary user intent, identify a substring of the substring corresponding to the concept, and determine a tertiary user intent for the substring of the substring corresponding to the concept. This recursive performance of blocks  608 ,  610 , and  612  can be performed any number of times to perform additional passes of the multi-pass natural language process to process the concepts and sub-concepts of the user speech. The user intent determined for a lower level recursive pass can be provided to the user intent of a higher level recursive pass. 
     Once all passes of the multi-pass natural language process is complete, a task flow planning and execution process represented by block  614  can then be performed. At block  614 , a task flow generated based on the primary user intent determined at block  606  and the secondary user intent  612  can be performed (and any subsequent passes of the multi-pass natural language process). In some examples, performing the task flow can include receiving the knowledge representation of user intent produced by the multi-pass natural language process and identifying a primary task flow to accomplish the primary user intent. The primary task flow can include a task flow identified by the primary user intent structure. For example, the primary task flow for a primary user intent structure representing a user intent to search for weather at a particular place and time can include performing a search query in an external weather service for the weather at the particular place and time. 
     Performing the task flow can further include identifying one or more constraints associated with the primary task flow. The one or more constraints can include any type of constraint imposed by the task flow, such as a type of input required by the task flow or a service required by the task flow. 
     Performing the task flow can further include identifying one or more queries, programs, methods, services, or APIs that can be performed to satisfy the one or more constraints. For example, the one or more queries, programs, methods, services, or APIs can be identified based on their ability to provide the type of input required by the primary task flow. 
     The tasks and order of the tasks to be performed in the task flow can be generated based on the primary task flow, the one or more constraints of the primary task flow, the identified one or more queries, programs, methods, services, or APIs, and the knowledge representation of user intent produced by the multi-pass natural language process. For example, based on the knowledge representation of user intent produced by the multi-pass natural language process, the domains that are to be used to generate parse results, the service methods required, and constraints of those services can be known. Given this information, an appropriate ordering of tasks can be generated to obtain the inputs required by tasks associated with the lowest level user intent structure (e.g., the tertiary user intent) to generate the required inputs for tasks associated with the higher level user intent structures (e.g., the secondary and primary user intents). 
     To illustrate the operation of process  600 , one example audio input that can be received at block  602  can include the user speech “What is the weather like near the hockey game tonight?”. At block  604 , the user speech can be converted into a textual representation of user speech. At block  606 , the textual representation of user speech can be analyzed using, for example, the various components of virtual assistant  300  shown in  FIG. 3  having active ontology  500  shown in  FIG. 5 , to identify possible parse results for the textual representation of user speech. In this example, each of weather domain  402 , sports domain  418 , reminder domain  420 , business domain  422 , and email domain  424  can generate possible parse results. A confidence score can be generated for the possible parse results and it can be determined that a parse result from weather domain  402  has the highest confidence score. This parse result can be used to determine that the likely user intent of the textual representation is that the user desires weather information. 
     At block  608 , the user intent structure associated with the identified parse result can be searched for concept nodes to identify concepts referred to by the user intent. As shown in  FIG. 5 , the weather user intent structure can include time concept node  502  and place concept node  506 . Thus, the semantic tags of these concept nodes can be read to identify and store the time concept and place concept represented by these concept nodes. At block  610 , a substring corresponding to each of the types of concepts identified at block  608  can be identified. For example, terminal node  508  can be used to perform a variable match process on the textual representation “What is the weather like near the hockey game tonight?” using the seed word “near” to identify the substring “the hockey game tonight” as likely referring to the place concept. Terminal node  504  can be used to perform a variable match process on the textual representation “What is the weather like near the hockey game tonight?” using the seed word “during” to identify a substring that likely refers to the time concept. Since the textual representation of user speech does not include the seed word “during,” other rules associated with terminal node  504  can optionally be used to determine that “tonight” or “the hockey game tonight” may refer to the time concept, but may do so with a lower confidence. 
     At block  612 , a secondary user intent can be determined for the substring identified at block  610 . This can include analyzing using, for example, the various components of virtual assistant  300  shown in  FIG. 3  having active ontology  500  shown in  FIG. 5 , to identify possible parse results for the substring. For example, the substring “the hockey game tonight” generated by terminal node  508  of place concept node  506  may have been the most confident weather result at block  610 . Thus, each of weather domain  402 , sports domain  418 , reminder domain  420 , business domain  422 , and email domain  424  can generate possible parse results. However, in some examples, parse results from email domain  424  can be excluded since that domain does not output the place type concept. A confidence score can be generated for the possible parse results and it can be determined that a parse result of a sporting event from sports domain  418  has the highest confidence score. Since a sporting event has both a concept of a time and a place, the determined user intent satisfies both the place concept requirement of place concept node  506  and time concept node  502  of weather domain  402 . Thus, the user intent of the sporting event can be returned to the weather domain user intent for the textual representation “What is the weather like near the hockey game tonight?” for both time concept node  502  and place concept node  506 . 
     At block  614 , task flow planning and execution can be performed. In some examples, this can include receiving the output of the multi-pass natural language process, performing service pipelining to unravel the multi-pass natural language output to take an output of one service and feed it into the input of another, and perform constraint validation and resolution. 
     For example, continuing with the example the textual representation “What is the weather like near the hockey game tonight?”, block  614  can include performing a query for the hockey game within the sports domain based on the output from the multi-pass natural language process and receiving the results. Since the multi-pass natural language process also indicates that the sports domain  418  output feeds into the input of the weather domain  402 , constraints for weather domain  402  can be inspected. In this example, it can be determined that the constraints for weather domain  402  include the concepts of place and time, as well as a constraint that a latitude and longitude must be defined for the place. 
     Next, the output from the sports domain  418  can be evaluated to determine if it is a valid input for weather domain  402 . For example, if multiple sporting events are output by weather domain  402 , block  614  can include disambiguating the events to identify a most likely sporting event. In another example, if no sporting events are output by sports domain  418 , a response should be presented to the user. In yet another example, if a sporting event is output by sports domain  418 , then block  614  can include extracting the concept. In this example, the place concept can be extracted from the event. If the output of sports domain  418  is not valid, block  614  can include an attempt to resolve the error. In the event that there is no time concept, then block  614  can include extracting the time concept from the event or using a default value. In the event that there is a missing latitude or longitude value, block  614  can include identifying a service that has specified that it can resolve latitude and longitude for any place concept. The constraint and validation process can be applied to the additional identified services. For example, when passing the place to be resolved into latitude and longitude, the service can be validated and the cycle of validation and resolution can continue until a final result is generated. 
     Once the service parameters are fully resolved, the final service can be invoked. For example, once the parameters for the weather service are resolved, the service can be invoked using those parameters to produce a final result for the user. However, if that service feeds into another service, the planning and execution process described above can be repeated. 
     Using process  600 , domains within an active ontology of a virtual assistant can advantageously refer to concepts shared between domains without having to specifically refer to every other domain within the active ontology that can produce that concept. Additionally, the domains do not require logic for calling the referenced domains, receiving the knowledge representations of user intent generated by those domains, identifying the knowledge representations of user intent that is most likely to provide the appropriate concept, and extracting the relevant concept from that knowledge representation of user intent. This reduces the time and effort required to add or modify domains within the active ontology. 
     While process  600  is described above for processing a spoken user input, it should be appreciated that it can similarly be used to process a text user input. For example, to process a text user input, blocks  602  and  604  may not be performed. Instead, the text user input can be received or accessed and blocks  606 ,  608 ,  610 ,  612 , and  614  can be performed, as described above, on the text user input. 
     Additionally, it should be appreciated that the blocks of process  600  can be performed on user device  102 , server system  110 , or a combination of user device  102  and server system  110 . For instance, in some examples, all blocks of process  600  can be performed on user device  102 . In other examples, all blocks of process  600  can be performed at server system  110 . In yet other examples, some blocks of process  600  can be performed at user device  102 , while other blocks of process  600  can be performed at server system  110 . 
     Electronic Device 
     In accordance with some examples,  FIG. 7  shows a functional block diagram of an electronic device  700  configured in accordance with the principles of the various described examples. The functional blocks of the device can be implemented by hardware, software, or a combination of hardware and software to carry out the principles of the various described examples. It is understood by persons of skill in the art that the functional blocks described in  FIG. 7  can be combined or separated into sub-blocks to implement the principles of the various described examples. Therefore, the description herein optionally supports any possible combination or separation or further definition of the functional blocks described herein. 
     As shown in  FIG. 7 , electronic device  700  can include a touch screen display unit  702  configured to display a user interface and to receive touch input, and a sound receiving unit  704  configured to receive sound input. In some examples, electronic device  700  can include a speaker unit  706  configured to generate sound. Electronic device  700  can further include a processing unit  708  coupled to touch screen display unit  702  and sound receiving unit  704  (and, optionally, coupled to speaker unit  706 ). In some examples, processing unit  708  can include a text receiving unit  710 , a primary user intent determining unit  712 , a concept identifying unit  714 , a first substring identifying unit  716 , a secondary user intent determining unit  718 , a task flow performing unit  720 , a second substring identifying unit  722 , a third substring identifying unit  724 , and a tertiary user intent determining unit  726 . 
     Processing unit  708  can be configured to receive an audio input (e.g., from audio receiving unit  704 ) containing user speech. Processing unit  708  can be configured to perform speech-to-text conversion on the audio input to generate a textual representation of user speech. The textual representation of user speech can be received by text receiving unit  710 . A primary user intent can be determined from the textual representation of user speech (e.g., using primary user intent determining unit  712 ). A first type of concept referred to by the primary user intent can be identified (e.g., using concept identifying unit  714 ). A first substring corresponding to the first type of concept can be identified from the textual representation of user speech (e.g., using first substring identifying unit  716 ). A secondary user intent for the first substring can be determined (e.g., using secondary user intent determining unit  718 ). A task flow comprising one or more tasks based at least in part on the primary user intent for the textual representation of user speech and the secondary user intent for the first substring can be performed (e.g., using task flow performing unit  720 ). 
     In some examples, processing unit  708  can be configured to determine the primary user intent for the textual representation of user speech (e.g., using primary user intent determining unit  712 ) by determining a confidence score for a plurality of interpretations of the textual representation of user speech and determining the primary user intent for the textual representation of user speech based on an interpretation of the plurality of interpretations of the textual representation of user speech having the highest confidence score. In some examples, the first type of concept comprises a place, a time, an event, or a person. 
     In some examples, processing unit  708  can be configured to identify the first substring from the textual representation of user speech (e.g., using first substring identifying unit  716 ) by identifying one or more predetermined words corresponding to the first type of concept in the textual representation of user speech and identifying the first substring based on the one or more predetermined words corresponding to the first type of concept. 
     In some examples, processing unit  708  can be configured to determine the secondary user intent for the first substring (e.g., using secondary user intent determining unit  718 ) by determining a confidence score for a plurality of interpretations of the first substring and determining the secondary user intent for the first substring based on an interpretation of the plurality of interpretations of the first substring having the highest confidence score. In some examples, the plurality of interpretations of the first substring can exclude interpretations from domains that do not output the first type of concept. 
     In some examples, processing unit  708  can be configured to identify a second type of concept referred to by the primary user intent (e.g., using concept identifying unit  714 ), identify a second substring from the textual representation of user speech corresponding to the second type of concept (e.g., using second substring identifying unit  722 ), and determine a secondary user intent for the second substring (e.g., using secondary user intent determining unit  718 ), wherein performing the task flow is further based on the secondary user intent for the second substring. In some examples, the second type of concept comprises a place, a time, an event, or a person. 
     In some examples, processing unit  708  can be configured to identify the second substring from the textual representation of user speech (e.g., using second substring identifying unit  722 ) by identifying one or more predetermined words corresponding to the second type of concept in the textual representation of user speech and identifying the second substring based on the one or more predetermined words corresponding to the second type of concept. 
     In some examples, processing unit  708  can be configured to determine the secondary user intent for the second substring (e.g., using secondary user intent determining unit  718 ) by determining a confidence score for a plurality of interpretations of the second substring and determining the secondary user intent for the second substring based on an interpretation of the plurality of interpretations of the second substring having the highest confidence score. In some examples, the plurality of interpretations of the second substring can exclude interpretations from domains that do not output the second type of concept. 
     In some examples, processing unit  708  can be configured to identify a third type of concept referred to by the secondary user intent for the first substring (e.g., using concept identifying unit  714 ), identify a third substring from the first substring corresponding to the third type of concept (e.g., using third substring identifying unit  724 ), and determine a tertiary user intent for the third substring (e.g., using tertiary user intent determining unit  726 ), wherein performing the task flow is further based on the tertiary user intent for the third substring. In some examples, the third type of concept comprises a place, a time, an event, or a person. 
     In some examples, processing unit  708  can be configured to identify the third substring from the first substring (e.g., using third substring identifying unit  724 ) by identifying one or more predetermined words corresponding to the third type of concept in the first substring and identifying the third substring based on the one or more predetermined words corresponding to the third type of concept. 
     In some examples, processing unit  708  can be configured to determine the tertiary user intent for the third substring (e.g., using tertiary user intent determining unit  726 ) by determining a confidence score for a plurality of interpretations of the third substring and determining the tertiary user intent for the third substring based on an interpretation of the plurality of interpretations of the third substring having the highest confidence score. In some examples, the plurality of interpretations of the third substring can exclude interpretations from domains that do not output the third type of concept. 
     In some examples, processing unit  708  can be configured to perform the task flow (e.g., using task flow performing unit  720 ) by identifying a primary task flow to accomplish the primary user intent, identify one or more constraints associated with the primary task flow, identify one or more queries, programs, methods, services, or APIs that satisfy the one or more constraints associated with the primary task flow, and generate the task flow from the primary task flow and the identified one or more queries, programs, methods, services, or APIs. In some examples, the one or more constraints can include a type of input required by the primary task flow, and the identified one or more queries, programs, methods, services, or APIs can be capable of providing the type of input required by the primary task flow. 
     As described above, one aspect of the present technology is the gathering and use of data available from various sources to improve the delivery to users of invitational content or any other content that may be of interest to them. The present disclosure contemplates that in some instances, this gathered data can include personal information data that uniquely identifies or can be used to contact or locate a specific person. Such personal information data can include demographic data, location-based data, telephone numbers, email addresses, home addresses, or any other identifying information. 
     The present disclosure recognizes that the use of such personal information data, in the present technology, can be used to the benefit of users. For example, the personal information data can be used to deliver targeted content that is of greater interest to the user. Accordingly, use of such personal information data enables calculated control of the delivered content. Further, other uses for personal information data that benefit the user are also contemplated by the present disclosure. 
     The present disclosure further contemplates that the entities responsible for the collection, analysis, disclosure, transfer, storage, or other use of such personal information data will comply with well-established privacy policies and/or privacy practices. In particular, such entities should implement and consistently use privacy policies and practices that are generally recognized as meeting or exceeding industry or governmental requirements for maintaining personal information data private and secure. For example, personal information from users should be collected for legitimate and reasonable uses of the entity and not shared or sold outside of those legitimate uses. Further, such collection should occur only after receiving the informed consent of the users. Additionally, such entities would take any needed steps for safeguarding and securing access to such personal information data and ensuring that others with access to the personal information data adhere to their privacy policies and procedures. Further, such entities can subject themselves to evaluation by third parties to certify their adherence to widely accepted privacy policies and practices. 
     Despite the foregoing, the present disclosure also contemplates examples in which users selectively block the use of, or access to, personal information data. That is, the present disclosure contemplates that hardware and/or software elements can be provided to prevent or block access to such personal information data. For example, in the case of advertisement delivery services, the present technology can be configured to allow users to select to “opt in” or “opt out” of participation in the collection of personal information data during registration for services. In another example, users can select not to provide location information for targeted content delivery services. In yet another example, users can select to not provide precise location information, but permit the transfer of location zone information. 
     Therefore, although the present disclosure broadly covers use of personal information data to implement one or more various disclosed examples, the present disclosure also contemplates that the various examples can also be implemented without the need for accessing such personal information data. That is, the various examples of the present technology are not rendered inoperable due to the lack of all or a portion of such personal information data. For example, content can be selected and delivered to users by inferring preferences based on non-personal information data or a bare minimum amount of personal information, such as the content being requested by the device associated with a user, other non-personal information available to the content delivery services, or publicly available information. 
     Although examples have been fully described with reference to the accompanying drawings, it is to be noted that various changes and modifications will become apparent to those skilled in the art. Such changes and modifications are to be understood as being included within the scope of the various examples as defined by the appended claims.

Metadata:
Filing Date: 20140929
Publication Date: 20170425
Grant Date: 20170425
Priority Date: 20140530
Inventors: GIULI RICHARD D.
TREADGOLD NICHOLAS K.
Assignee: APPLE INC
CPC Classifications: [{"code": "G10L15/1822", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F40/30", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F3/167", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F16/3329", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F16/3329", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F40/30", "inventive": true, "first": false, "tree": "[]"}, {"code": "G10L15/22", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06F3/167", "inventive": true, "first": false, "tree": "[]"}, {"code": "G10L2015/223", "inventive": false, "first": false, "tree": "[]"}, {"code": "G10L15/1815", "inventive": true, "first": false, "tree": "[]"}, {"code": "G10L15/1822", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06F17/2785", "inventive": true, "first": true, "tree": "[]"}, {"code": "G10L15/1822", "inventive": false, "first": false, "tree": "[]"}, {"code": "G06F17/30654", "inventive": true, "first": false, "tree": "[]"}]
Family ID: 54702534