# Patent

## Title
Modeling actions for entity-centric search

## Abstract

In one embodiment, a web service engine server 104 may predict a successive action by a user based on an entity reference 302. The web service engine server 104 identifies an entity reference 302 in a data transmission caused by a user. The web service engine server 104 determines from the data transmission a user intention towards the entity reference 302 using an intention model based on a transmission log. The web service engine server 104 predicts a related successive web action option 522 for the entity reference 302 based on the user intention.

## Background
BACKGROUND
A search engine is a program executed on a server that looks for data on the internet. The search engine may provide a list of one or more website links in response to a search query from a user. The search engine may compare the search query to an index. The search engine may compile the index based on metadata retrieved by a web crawler. The search engine may compare the words of the search query to the metadata to determine the best match. Other factors may also be taken into account, such as the number of links to the website on other websites and other data.
SUMMARY
This Summary is provided to introduce a selection of concepts in a simplified form that is further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.
Embodiments discussed below relate to predicting a successive action by a user based on an entity reference. The web service engine server may identify an entity reference in a data transmission caused by a user. The web service engine server may determine from the data transmission a user intention towards the entity reference using an intention model based on a transmission log. The web service engine server may predict a related successive web action option for the entity reference based on the user intention.



DRAWINGS
In order to describe the manner in which the above-recited and other advantages and features can be obtained, a more particular description is set forth and will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments and are not therefore to be considered to be limiting of its scope, implementations will be described and explained with additional specificity and detail through the use of the accompanying drawings.
FIG. 1 illustrates, in a block diagram, one embodiment of a data network.
FIG. 2 illustrates, in a block diagram, one embodiment of a computing device.
FIGS. 3a-c illustrate, in block diagrams, different embodiments of data transmissions providing an entity reference.
FIGS. 4a-c illustrate, in plate diagrams, embodiments of intention models.
FIGS. 5a-b illustrate, in block diagrams, embodiments of a presentation user interface.
FIG. 6 illustrates, in a flowchart, one embodiment of a method creating a search intention model.
FIG. 7 illustrates, in a flowchart, one embodiment of a method of using the search intention model on an entity reference.



DETAILED DESCRIPTION
Embodiments are discussed in detail below. While specific implementations are discussed, it should be understood that this is done for illustration purposes only. A person skilled in the relevant art will recognize that other components and configurations may be used without parting from the spirit and scope of the subject matter of this disclosure. The implementations may be a machine-implemented method, a tangible machine-readable medium having a set of instructions detailing a method stored thereon for at least one processor, or a web service engine server.
Many search queries contain named entities. Depending on the entity reference and the context, the user may frequently choose from a limited number of actions to perform on the entity, such as “view biography of”, “see sports statistics for”, “read reviews of” and others. These actions, in turn, may typically be performed at certain websites or using certain applications, including online enabled applications.
A search engine may create a query log of the search queries sent in by a sufficiently large set of users, as well as the sites that those users subsequently visited. A search engine may create a statistical intention model based on that query log to predict subsequent actions taken by a single user. A statistical intention model identifies the subsequent action that a user seeks to enable by the submitted query. For example, a user submitting the query “Star Wars reviews” may want to watch the movie Star Wars®, but wishes to read reviews beforehand to determine if the movie is worth seeing. By identifying an entity in a search query, the context words surrounding that query, and other information available in web usage logs, such as a query click history, the search engine may use the intention model to determine the intent of the user. Thus, a search engine may predict any subsequent actions that a user wants to perform, and may preemptively provide the user with a website link to an online service to perform those actions. Alternately, the search engine may preemptively provide the user with an application programming interface (API) that connects the user to a website or application capable of performing those actions. The application programming interface may be provided by the online service or by the search engine user interface. The search engine may interact with either a graphical user interface or a voice recognition program to provide these options to the user.
Further, these action predictions may be created and used by other web services, such as an e-mail service, a social network, or even a shopping service. A web service engine may use an entity reference in a data transmission, such as an e-mail or a social network posting, to provide targeted advertising to the user. The web service engine may develop an intention model based on a transmission log of user transmissions sent by a sufficiently large set of users.
Thus, in one embodiment, a web service engine server may predict a successive action by a user based on an entity reference. The web service engine server may identify an entity reference in a data transmission caused by a user. The web service engine server may determine from the data transmission a user intention towards the entity reference using an intention model based on a transmission log. The web service engine server may predict a related successive web action option for the entity reference based on the user intention.
FIG. 1 illustrates, in a block diagram, one embodiment of a data network 100 that may use an entity centric web service. A user device 102 may submit a direct data transmission, such as a search query, to a web service engine server 104, such as a search engine server, over a data network connection 106. The web service engine server 104 may identify sites on the internet 108 that respond to the search query.
Alternatively, the web service engine server 104, such as an e-mail server or a social network server, may intercept an indirect data transmission from the user device, such as an e-mail or a posting on a public forum or a social network. The web service engine server 104 may use an entity reference in the data transmission to determine a user intention indicated by the data transmission. An entity reference is a reference to an event, a location, a virtual entity, or a tangible entity. The web service engine server 104 may develop an intention model based on a transmission log to model a user intention. The web service engine server 104 may use the intention model and the entity reference to determine the user intention.
The web service engine server 104 may then predict one or more related successive web action options based on the user intention. A related successive web action option is a possible action the user may take on the internet after the search query in furtherance of the user intention. Each related successive web action option may be associated with one or more website links that may lead to a website where the user may perform the related successive web action option. Alternately, a successive web action option may be associated with an application programming interface connecting the user to a website or application to perform the related successive web action option, such as a banking application or other applications. The related successive web action option set, the associated website links, and the application programming interfaces may be ranked in order of usability, as determined by the probabilities suggested by the intention model.
FIG. 2 illustrates a block diagram of an exemplary computing device 200 which may act as a user device 102 or a web service engine server 104. The computing device 200 may combine one or more of hardware, software, firmware, and system-on-a-chip technology to implement the entity-centric web service. The computing device 200 may include a bus 210, a processor 220, a memory 230, a read only memory (ROM) 240, a storage device 250, an input device 260, an output device 270, and a communication interface 280. The bus 210 may permit communication among the components of the computing device 200.
The processor 220 may include at least one conventional processor or microprocessor that interprets and executes a set of instructions. The memory 230 may be a random access memory (RAM) or another type of dynamic storage device that stores information and instructions for execution by the processor 220. The memory 230 may also store temporary variables or other intermediate information used during execution of instructions by the processor 220. The ROM 240 may include a conventional ROM device or another type of static storage device that stores static information and instructions for the processor 220. The storage device 250 may include any type of tangible machine-readable medium, such as, for example, magnetic or optical recording media and its corresponding drive. A tangible machine-readable medium is a physical medium storing machine-readable code or instructions, as opposed to a transitory medium or signal. The storage device 250 may store a set of instructions detailing a method that when executed by one or more processors cause the one or more processors to perform the method. The storage device 250 may also be a database or a database interface for storing website links, intention models, and action phrasings.
The input device 260 may include one or more conventional mechanisms that permit a user to input information to the computing device 200, such as a keyboard, a mouse, a voice recognition device, a microphone, a headset, etc. The output device 270 may include one or more conventional mechanisms that output information to the user, including a display, a printer, one or more speakers, a headset, or a medium, such as a memory, or a magnetic or optical disk and a corresponding disk drive. The communication interface 280 may include any transceiver-like mechanism that enables computing device 200 to communicate with other devices or networks. The communication interface 280 may include a network interface or a transceiver interface. The communication interface 280 may be a wireless, wired, or optical interface.
The computing device 200 may perform such functions in response to processor 220 executing sequences of instructions contained in a computer-readable medium, such as, for example, the memory 230, a magnetic disk, or an optical disk. Such instructions may be read into the memory 230 from another computer-readable medium, such as the storage device 250, or from a separate device via the communication interface 280.
The web service engine server 104 may identify an entity reference in a data transmission, such as a search query, an e-mail, or a social network post. FIG. 3a illustrates, in a block diagram, one embodiment of a search query 300. The search query 300 is a query entered directly into a search engine. The search query 300 may have an entity reference 302. The entity reference 302 describes the tangible entity, virtual entity, location or event that the user intends to act upon. For example, the entity reference 302 may be “restaurant”, “Black Keys”®, “Star Wars”®, or “Hope Solo”. The search query 300 may have one or more context words 304 on either side of the entity reference 302. A context word 304 describes the context in which the user intends to use the entity reference 302. For example, the context word 304 may be “reservations”, “tickets”, or “stats”. The intent may be inferred even when the context word 304 is empty.
If the web service engine server 104 is attached to a mail server, the web service engine server 104 may passively read the e-mail of a user. FIG. 3b illustrates, in a block diagram, one embodiment of an e-mail 320. The e-mail 320 may have an address 322 indicating the destination of the e-mail. The e-mail 320 may have a message body 324 presenting the message being sent to the address 322. An entity reference 302 and one or more context words 304 may be embedded in the message body 324 of the e-mail 320. For example, the body of the e-mail may read: “I am taking my wife to the French Laundry for dinner tomorrow.” The entity reference 302 may be “French Laundry,” while the context words 304 may be “dinner” and “tomorrow”. Thus, the web service engine server 104 may determine that the user intends to go to dinner tomorrow at the French Laundry, predict that the next action of the user may be to make reservations, and provide an application programming interface to make reservations at the French Laundry.
The web service engine server 104 may crawl a social network page associated with the user. FIG. 3c illustrates, in a block diagram, one embodiment of a social network page 340. The social network page 340 may have a social network post 342 attributable to a user. The social network post 342 may have an entity reference 302 and one or more context words 304 embedded in the post body 324. For example, the social network post 342 may read: “I am looking forward to attending the Niners' game tomorrow.” The entity reference 302 may be “Niners' game” and the context words may be “attending”. The web service engine server 104 may determine that the user intends to attend a San Francisco Forty-Niners' ® game, and that a successive action may be to order a Forty-Niners' jersey to wear to the game. The web service engine server 104 may recommend a website link to a paraphernalia store.
The web service engine server 104 may use a transmission log to develop an intention model. A transmission log is a collection of user transmissions, such as a search query, an e-mail, or a social network post. The transmission log may collect user transmissions from multiple users or may focus on user transmissions from a single user. An intention model may be used to predict the probability of a specific user intention resulting in a specific user action.
The web service engine server 104 may use the intention model to automatically learn the underlying actions intended in a user transmission, as well as to recommend actions given a new user transmission. The intention model may probabilistically describe a generation process for a user transmission containing an entity and underlying action intent. The intention model may assume that a user transmission is governed by latent actions and entity types, which influence the choice of query terms and clicks. The intention model may use inference procedures to infer actions after learning these models by maximizing the probability through observing a large collection of real-world user transmissions and the resulting clicked hosts.
A web service engine may use multiple types of intention models. For example, FIG. 4a illustrates, in a block diagram, one embodiment of a simplified intention model 400. A simplified intention model 400 may use one or more context words (n) 304 to create an action prediction 402 to be taken by the user. The viability of the action prediction (a) 402 may be measured by comparing a host website clicked by the user in a continuation of the user transmission, referred to as the click through host (c) 404. The click through host 404 may be a website link presented in response to a search query and selected by a user, or a website selection by a user after sending an e-mail or posting a social network post. The context words 304 and click through host 404 may be directly observable by the web service engine. The simplified intention model 400 may have a context multinomial set of parameters (Φ) 406 describing the distribution of the context words 304, a host multinomial set of parameters (Ω) 408 describing the distribution of the click through host 404, and an action multinomial set of parameters (Θ) 410 describing the distribution of the action prediction 404.
For a user transmission of “Star Wars review,” the intention model may generate the action “read reviews.” Based on this action, the intention model may choose a null context word 304 and a context word 304 of “review.” The intention model may generate a click on a site such as “rottentomatoes.com.”
The joint probability of the intention model may be the product of the conditional distributions, as given by:

P(a,q=n1,n2,c|Θ,Φ,Ω)=P(a|Θ)P(n1|a,Φ)P(n2|a,Φ)P(c|a,Ω)

Next, the intention model 400 may define each of the terms in the joint distribution. The intention model 400 may define K as the number of latent actions 412 that govern the transmission log, where K 412 is fixed in advance. Then, the probability of action prediction a 402 may be defined as a multinomial distribution with probability vector Φ 410, such that the probability of a particular action may be given by:




  
    
      P
      ⁡
      
        (
        
          a
          =
          
            a
            ^
          
        
        )
      
    
    =
    
      
        ∏
        
          k
          =
          1
        
        K
      
      ⁢
      
        
      
      ⁢
      
        Θ
        k
        
          I
          ⁡
          
            [
            
              k
              =
              
                a
                ^
              
            
            ]
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      s
      .
      t
      .
      
        
      
      ⁢
      
        
          ∑
          k
        
        ⁢
        
          Θ
          k
        
      
    
    =
    1
  




where I is an indicator function set to 1 if the condition holds, and 0 otherwise.

The intention model 400 may define V as the shared vocabulary size of all context words n1 and n2 304. Given an action prediction a 402, the probability of generating a context word n 304 may be given by a multinomial distribution with probability vector Φa 406 such that Φ=[Φ1, . . . , ΦK] represents parameters across actions:




  
    
      P
      ⁡
      
        (
        
          n
          =
          
            
              
                n
                ^
              
              |
              a
            
            =
            
              a
              ^
            
          
        
        )
      
    
    =
    
      
        ∏
        
          v
          =
          1
        
        V
      
      ⁢
      
        
      
      ⁢
      
        Φ
        
          
            a
            ^
          
          ,
          v
        
        
          I
          ⁡
          
            [
            
              v
              =
              
                n
                ^
              
            
            ]
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      s
      .
      t
      .
      
        
      
      ⁢
      
        ∀
        
          a
          ⁢
          
            
              
                ∑
                
                  v
                  =
                  1
                
              
              V
            
            ⁢
            
              Φ
              
                a
                ,
                v
              
            
          
        
      
    
    =
    1
  




Finally, the intention model 400 may assume H possible click values, corresponding to H click through hosts 404. A click on a host may be determined by an action. Given an action prediction a 402, the intention model 400 may assume the probability of generating a click through host c 404 is a multinomial with a probability vector ωa 408 such that Ω=[ω1, . . . , ωK] captures the matrix of parameters across all K actions 412. In particular:




  
    
      P
      ⁡
      
        (
        
          c
          =
          
            
              
                c
                ^
              
              |
              a
            
            =
            
              a
              ^
            
          
        
        )
      
    
    =
    
      
        ∏
        
          h
          =
          1
        
        H
      
      ⁢
      
        
      
      ⁢
      
        Φ
        
          
            a
            ^
          
          ,
          h
        
        
          I
          ⁡
          
            [
            
              h
              =
              
                c
                ^
              
            
            ]
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      s
      .
      t
      .
      
        
      
      ⁢
      
        ∀
        
          a
          ⁢
          
            
              
                ∑
                
                  h
                  =
                  1
                
              
              H
            
            ⁢
            
              Φ
              
                a
                ,
                h
              
            
          
        
      
    
    =
    1
  




Given a query, the intention model 400 may apply Bayes' rule to find the posterior distribution over the actions. In particular, the posterior distribution, P(a|q,c), may be directly proportional to the joint distribution. The intention model may compute this distribution by evaluating the joint for every value of a and the observed configuration of q and c.
Given a transmission log Q 414 having N independently and identically distributed transmissions (each qj={n1j, n2j}) and the corresponding clicked through hosts 404, the intention model 400 may estimate the parameters Θ 410,Φ 406, and Ω 408 that maximize the (log) probability of observing Q 414. The log P(Q) may be written as:




  
    log
    ⁢
    
      
    
    ⁢
    
      P
      ⁡
      
        (
        Q
        )
      
    
  
  =
  
    
      ∑
      
        j
        =
        1
      
      N
    
    ⁢
    
      
        ∑
        a
      
      ⁢
      
        
          
            P
            j
          
          ⁡
          
            (
            
              
                a
                |
                q
              
              ,
              c
            
            )
          
        
        ⁢
        log
        ⁢
        
          
        
        ⁢
        
          
            P
            j
          
          ⁡
          
            (
            
              q
              ,
              c
              ,
              a
            
            )
          
        
      
    
  




In the above equation, Pj(a|q, c) may represent the posterior distribution over actions for the jth query. The intention model 400 may use an expectation maximization process to set the parameters. Starting with a random initialization of the parameters, the intention model 400 may iterate between the expectation step, in which Pj(a|q, c) may be computed for each user transmission, and the maximization step, in which the parameters may be updated by fixing Pj(a|q, c) to the values computed in the expectation step.
The intention model 400 may obtain parameter updates by computing the derivative of log P(Q) with respect to each parameter, and setting the resultant to 0. The update for Θ 410 may be given by the average of the posterior distributions over the actions:




  
    θ
    
      a
      ^
    
  
  =
  
    
      
        ∑
        
          j
          =
          1
        
        N
      
      ⁢
      
        
          P
          j
        
        ⁡
        
          (
          
            
              a
              =
              
                
                  a
                  ^
                
                |
                q
              
            
            ,
            c
          
          )
        
      
    
    
      
        ∑
        
          j
          =
          1
        
        N
      
      ⁢
      
        
          ∑
          a
        
        ⁢
        
          
            P
            j
          
          ⁡
          
            (
            
              
                a
                |
                q
              
              ,
              c
            
            )
          
        
      
    
  




For a fixed a, the intention model 400 may give the update for Φa 406 by the weighted average of the context words 304, where the weights are the posterior distributions over the action predictions 402, for each user transmission. In particular:




  
    Φ
    
      
        a
        ^
      
      ,
      
        n
        ^
      
    
  
  =
  
    
      
        ∑
        
          j
          =
          1
        
        N
      
      ⁢
      
        
          
            P
            j
          
          ⁡
          
            (
            
              
                a
                =
                
                  
                    a
                    ^
                  
                  |
                  q
                
              
              ,
              c
            
            )
          
        
        ⁡
        
          [
          
            
              I
              ⁡
              
                [
                
                  
                    n
                    1
                    j
                  
                  =
                  
                    n
                    ^
                  
                
                ]
              
            
            +
            
              I
              ⁡
              
                [
                
                  
                    n
                    2
                    j
                  
                  =
                  
                    n
                    ^
                  
                
                ]
              
            
          
          ]
        
      
    
    
      2
      ⁢
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            P
            j
          
          ⁡
          
            (
            
              
                a
                =
                
                  
                    a
                    ^
                  
                  |
                  q
                
              
              ,
              c
            
            )
          
        
      
    
  




Similarly, the intention model 400 may update Ω 408, the parameters 408 that govern the distribution over clicked through hosts 404 for each action prediction 402. For a fixed action prediction a 402, the intention model 400 may be updated by taking the weighted average of the clicked through hosts 404, with weights provided by the posterior distribution over the actions:




  
    Ω
    
      
        a
        ^
      
      ,
      
        n
        ^
      
    
  
  =
  
    
      
        ∑
        
          j
          =
          1
        
        N
      
      ⁢
      
        
          
            P
            j
          
          ⁡
          
            (
            
              
                a
                =
                
                  
                    a
                    ^
                  
                  |
                  q
                
              
              ,
              c
            
            )
          
        
        ⁢
        
          I
          ⁡
          
            [
            
              
                c
                j
              
              =
              
                c
                ^
              
            
            ]
          
        
      
    
    
      
        ∑
        
          j
          =
          1
        
        N
      
      ⁢
      
        
          P
          j
        
        ⁡
        
          (
          
            
              a
              =
              
                
                  a
                  ^
                
                |
                q
              
            
            ,
            c
          
          )
        
      
    
  




FIG. 4b illustrates, in a block diagram, one embodiment of a more complex intention model 420. The intention model 420 may consider the entity reference 302 when determining the action prediction 402. The entity reference 302, the context words 304, and the click through host 404 may be directly observable when creating the simplified intention model 400. A more complex intention model 420 may include an entity type 422. An entity type 422 is a categorization of an entity. For example, the entity reference 302 “Star Wars”® may have an entity type 422 of “Movie”. Inclusion of the entity type 422 tends to have such an impact on an action prediction 402 that the entity type 422 may be excluded from initial construction of the intention model 420. The intention model 420 may have an entity multinomial set of parameters (Ψ) 424 describing the distribution of the entity 302 and a type multinomial set of parameters (τ) 426 describing the distribution of the entity type 422.
The joint probability over the model variables may be:

P(t,a,q={n1,e,n2,}c|Θ,Φ,Ω,τ,Ψ)=P(t|τ)P(a|t,Θ)P(e|t,Ψ) P(c|a,Ω)P(n1|a,Φ)P(n2|a,Φ)

Next, the intention model 420 may describe each term in the joint probability. Let The number 428 of entity types 422. The probability of generating an entity type t 422 may be governed by a multinomial with a probability vector τ 426. In particular:




  
    
      P
      ⁡
      
        (
        
          t
          =
          
            t
            ^
          
        
        )
      
    
    =
    
      
        ∏
        
          i
          =
          1
        
        T
      
      ⁢
      
        
      
      ⁢
      
        τ
        i
        
          I
          ⁡
          
            [
            
              i
              =
              
                t
                ^
              
            
            ]
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      s
      .
      t
      .
      
        
      
      ⁢
      
        
          ∑
          
            i
            =
            1
          
          T
        
        ⁢
        
          τ
          i
        
      
    
    =
    1
  




The intention model 420 may set E as the number of known entities. The probability of generating an entity θ 302 given entity type t 422 may be a multinomial with a probability vector Ψt 424 such that Ψ=[Ψ1, . . . , ΨT] captures the matrix of parameters across all T 428 types 422. In particular:




  
    
      P
      ⁡
      
        (
        
          e
          =
          
            
              
                e
                ^
              
              |
              t
            
            =
            
              t
              ^
            
          
        
        )
      
    
    =
    
      
        ∏
        
          i
          =
          1
        
        E
      
      ⁢
      
        
      
      ⁢
      
        Ψ
        
          
            t
            ^
          
          ,
          i
        
        
          I
          ⁡
          
            [
            
              i
              =
              
                e
                ^
              
            
            ]
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      s
      .
      t
      .
      
        
      
      ⁢
      
        ∀
        
          t
          ⁢
          
            
              ∑
              
                i
                =
                1
              
              E
            
            ⁢
            
              Ψ
              
                t
                ,
                i
              
            
          
        
      
    
    =
    1
  




Since actions may be conditioned on types for every value of type, the entity type 422 may be represented by a multinomial distribution with probability vector Θ 410, such that Θ=[Θ1, . . . , ΘT] represents parameters across types:




  
    
      P
      ⁡
      
        (
        
          a
          =
          
            
              
                a
                ^
              
              |
              t
            
            =
            
              t
              ^
            
          
        
        )
      
    
    =
    
      
        ∏
        
          k
          =
          1
        
        K
      
      ⁢
      
        
      
      ⁢
      
        Θ
        
          
            t
            ^
          
          ,
          k
        
        
          I
          ⁡
          
            [
            
              k
              =
              
                a
                ^
              
            
            ]
          
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      s
      .
      t
      .
      
        
      
      ⁢
      
        ∀
        
          t
          ⁢
          
            
              ∑
              
                k
                =
                1
              
              K
            
            ⁢
            
              Θ
              
                t
                ,
                k
              
            
          
        
      
    
    =
    1
  




Prior distributions over the context words 304 and click through host 404 may remain unchanged as the simplified intention model 400.
Given a query, the complex intention model 420 may apply Bayes' rule to find the posterior distribution, P(a, t|q, c), over the actions, as proportional to P(a,t,q,c). The complex intention model 420 may compute this quantity by evaluating the joint for each combination of action prediction a 402 and entity type t 422, and the observed values of q and c.
During inference, the complex intention model 420 may enforce that an entity may have certain admissible types. As an example, if the entity is Star Wars®, valid types include film and book. The complex intention model 420 may set the posterior probability of invalid types to zero. The complex intention model 420 may obtain the set of admissible types for every entity using an external knowledge base.
As with the simplified intention model 400, the complex intention model 420 may perform maximum likelihood estimation of the parameters using the expectation maximization process. The maximization may further include these equations for the following complex parameters:



  
    
      τ
      
        t
        ^
      
    
    =
    
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            ∑
            a
          
          ⁢
          
            
              P
              j
            
            ⁡
            
              (
              
                a
                ,
                
                  t
                  =
                  
                    
                      t
                      ^
                    
                    |
                    q
                  
                
                ,
                c
              
              )
            
          
        
      
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            ∑
            
              a
              ,
              t
            
          
          ⁢
          
            
              P
              j
            
            ⁡
            
              (
              
                a
                ,
                
                  t
                  |
                  q
                
                ,
                c
              
              )
            
          
        
      
    
  




  
    
      Ψ
      
        
          t
          ^
        
        ,
        
          e
          ^
        
      
    
    =
    
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            ∑
            a
          
          ⁢
          
            
              
                P
                j
              
              ⁡
              
                (
                
                  a
                  ,
                  
                    t
                    =
                    
                      
                        t
                        ^
                      
                      |
                      q
                    
                  
                  ,
                  c
                
                )
              
            
            ⁢
            
              I
              ⁡
              
                [
                
                  
                    e
                    j
                  
                  =
                  
                    e
                    ^
                  
                
                ]
              
            
          
        
      
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            ∑
            a
          
          ⁢
          
            
              P
              j
            
            ⁡
            
              (
              
                
                  a
                  =
                  
                    
                      a
                      ^
                    
                    |
                    q
                  
                
                ,
                c
              
              )
            
          
        
      
    
  



In a search query, a context word 304 may be left empty. For example, a user may query for “Star Wars” instead of adding refiners such as “Star Wars reviews” or “Star Wars tickets.” FIG. 4c illustrates, in a block diagram, one embodiment of an empty context intention model 440. In order to compensate, the empty context intention model 440 may explicitly represent an empty context word 304 using a switch variable 442 that determines whether a context word 304 may be empty. The empty context intention model 440 may have an entity multinomial set of parameters (σ) 444 describing the distribution of the switch variable 442.
The empty context intention model 440 may be:

P(t,a,q={n1,e,n2}c,s={s1,s2}|Θ,Φ,Ω,τ,Ψ,σ)=P(t|τ)P(a|t,Θ)P(e|t,Ψ)P(c|a,Ω)Πi=12P(ni|a,Φ)I[s i=1]P(n2|a,Φ)

The probability of generating an empty or non-empty context word s 304 given an action prediction a 402 may be given by a Bernoulli distribution with switch parameter σa 444:

P(s|a=â)=σâI[i={circumflex over (t)}](1−σâ)I[s=0]

The maximization function for the switch parameter σ 444:




  
    σ
    
      a
      ^
    
  
  =
  
    
      
        ∑
        
          j
          =
          1
        
        N
      
      ⁢
      
        
          ∑
          t
        
        ⁢
        
          
            
              P
              j
            
            ⁡
            
              (
              
                
                  a
                  =
                  
                    a
                    ^
                  
                
                ,
                
                  t
                  |
                  q
                
                ,
                c
                ,
                s
              
              )
            
          
          ⁢
          
            I
            ⁡
            
              [
              
                
                  I
                  ⁡
                  
                    [
                    
                      
                        s
                        1
                      
                      =
                      1
                    
                    ]
                  
                
                +
                
                  I
                  ⁡
                  
                    [
                    
                      
                        s
                        2
                      
                      =
                      1
                    
                    ]
                  
                
              
              ]
            
          
        
      
    
    
      2
      ⁢
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            ∑
            t
          
          ⁢
          
            
              P
              j
            
            ⁡
            
              (
              
                
                  a
                  =
                  
                    a
                    ^
                  
                
                ,
                
                  t
                  |
                  q
                
                ,
                c
                ,
                s
              
              )
            
          
        
      
    
  




A web service engine may take a Bayesian approach and treat these parameters as variables, possibly with Dirichlet and Beta prior distributions, and perform Bayesian inference.
In using the intention model, the user may submit a search query 300 to the web service engine server 104 of “Star Wars review”. The user may then click on the website rottentomatoes.com. The web service engine server 104 may model the search query 300 by labeling “Star Wars” as the entity reference 302. The web service engine server 104 may label the word “review” as a context word 304. The web service engine server 104 may label www.rottentomatoes.com as the click through host 404. The web service engine server 104 may determine that the entity type 422 is “Film”. Thus, the web service engine server 104 may determine that a predicted action 402 is “read a review”.
The web service engine server 104 may use the intention model on a data transmission to predict a future action by the user. The action predictions 402 may be in response to a direct data transmission, such as a search query 300, or gleaned from an indirect data transmission, such as an e-mail 320 or a social network post 340. FIG. 5a illustrates, in a block diagram, one embodiment of a search engine page 500 that may present the resulting action predictions 402 to the user. While a graphical user interface is shown, other user interfaces, such as a natural user interface using voice recognition, may also be used. The search engine page 500 may present the search query 300 to the user. The search engine page may present a standard search result set 510, listing a set of direct search results 512. For example, a search query 300 of “Girl with the Dragon Tattoo movie” may result in a direct search result 512 of the website set up by the production company. The search engine page 500 may provide a related successive web action option set 520 for the search query 300. The related successive web action option set 520 may have one or more related successive web action options 522, each with an associated website link 524 or application programming interface 526. Per the previous example, the related successive web action option 522 may be “read a review” with a link to Rotten Tomatoes®, “buy a ticket” with a Fandango® application, or “download a digital copy” with a link to Amazon®. Each related successive web action option 522 may have a rank 528, allowing the related successive web action options 522 to be arranged from most likely to least likely, as determined by the intention model.
Alternately, the action predictions 402 may be gleaned from an indirect data transmission, such as an e-mail 320 or a social network post 340. Thus, the action predictions 402 may be incorporated into a web page, such as an e-mail account, a blog, or a social network post. FIG. 5b illustrates, in a block diagram, one embodiment of a web page 550 that may present the resulting action predictions 402 to the user. While a graphical user interface is shown, other user interfaces, such as a natural user interface using voice recognition, may also be used. The web page 550 may provide a related successive web action option set 520 in a web page advertisement 560. The web page advertisement 560 may be in a banner advertisement over a web page body 570.
FIG. 6 illustrates, in a flowchart, one embodiment of a method 600 creating a search intention model. The web service engine server 104 may receive or compile a transmission log of user transmissions over a large set of users, such as search queries, e-mails, or social network posts (Block 602). The web service engine server 104 may develop a simplified intention model 400 based on the transmission log to model the user intention (Block 604). The web service engine server 104 may factor at least one of an entity reference 302, a click through host 404, and a context word 304 into the intention model 400 (Block 606). The web service engine server 104 may determine an entity type 422 for each entity reference 302 in the transmission log(Block 608). The web service engine server 104 may factor the entity type 422 into later construction of a complex intention model 420 (Block 610). The web service engine server 104 may exclude the entity type 422 from initial construction of the intention model 400 to prevent the entity type 422 from overwhelming the other factors. The web service engine server 104 may tailor the intention model to an individual user (Block 612). The web service engine server 104 may consider demographic information about the user or prior search and click history.
The web service engine server 104 may generate the action phrasing by clustering phrases found in a large corpus of phrases, such as the 108. The web service engine server 104 may filter the clustered phrases to remove adverbs and noise, pairing the words down to action verbs. The web service engine server 104 may further filter the action verbs to remove any actions that may not be performed online. The web service engine server 104 may then pair those action verbs with a location or object. The web service engine server 104 may label an action cluster of the intention model (Block 614). The web service engine server 104 may generate automatically an action phrasing for a related successive web action option using the labeled action cluster (Block 616). Alternatively, the action phrasing may be generated, supplemented, or edited by a human administrator.
FIG. 7 illustrates, in a flowchart, one embodiment of a method 700 of using the search intention model on an entity reference. The web service engine server 104 may receive a data transmission caused by an individual user (Block 702). The data transmission may be a search query 300, an e-mail 320, or a social network post 340. The web service engine server 104 may identify an entity reference 302 in the data transmission caused by the user (Block 704). The web service engine server 104 may identify the entity reference in at least one of a search query, an e-mail, or a social network post. The web service engine server 104 may determine from the data transmission a user intention towards the entity reference using an intention model based on a transmission log (Block 706). The web service engine server 104 may predict a related successive web action option set 520 for the entity reference based on the user intention towards the entity reference according to the intention model (Block 708).
The web service engine server 104 may identify a website link 524 or an application programming interface 526 for performing a related successive web action option 522 (Block 710). A website administrator may indicate that the website performs a related successive web action by placing the action phrasing for that related successive web action option 522, as provided by the web service engine server 104, in a metadata tag for that website. Thus, the web service engine server 104 may identify at least one of a website link 524 or application programming interface 526 having the related successive web action option 522 in a metadata tag. The web service engine server 104 may associate at least one of the website link 524 or the application programming interface 526 with the related successive web action option 522 (Block 712).
If two related successive web action options 522 in the related successive web action option set 520 have an equal probability of being chosen (Block 714), the web service engine server 104 may incorporate a monetization factor into ranking the related successive web action option set 520 or in selecting a website link 524 or application programming interface 526 (Block 716). A monetization factor may be an advertisement fee, a paid action placement, a lead generation, an on-site commercial transaction, or other payment processes. The web service engine server 104 may rank the related successive web action options 522 in the related successive web action option set 520 (Block 718).
The web service engine server 104 may send the related successive web action option set 520 to a user device 102 for presentation to the user (Block 720). The related successive web action option set 520 may be just a portion of available related successive web action options. The user device 102 may present the related successive web action option set 540 to the user through any kind of user interface, such as a graphical user interface or a natural user interface. The web service engine server 104 may receive a user selection of a website link 524 associated with a related successive web action option 522 (Block 722). The web service engine server 104 may adjust the intention model based on the user selection (Block 724).
Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms for implementing the claims.
Embodiments within the scope of the present invention may also include non-transitory computer-readable storage media for carrying or having computer-executable instructions or data structures stored thereon. Such non-transitory computer-readable storage media may be any available media that can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such non-transitory computer-readable storage media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store desired program code means in the form of computer-executable instructions or data structures. Combinations of the above should also be included within the scope of the non-transitory computer-readable storage media.
Embodiments may also be practiced in distributed computing environments where tasks are performed by local and remote processing devices that are linked (either by hardwired links, wireless links, or by a combination thereof) through a communications network.
Computer-executable instructions include, for example, instructions and data which cause a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. Computer-executable instructions also include program modules that are executed by computers in stand-alone or network environments. Generally, program modules include routines, programs, objects, components, and data structures, etc. that perform particular tasks or implement particular abstract data types. Computer-executable instructions, associated data structures, and program modules represent examples of the program code means for executing steps of the methods disclosed herein. The particular sequence of such executable instructions or associated data structures represents examples of corresponding acts for implementing the functions described in such steps.
Although the above description may contain specific details, they should not be construed as limiting the claims in any way. Other configurations of the described embodiments are part of the scope of the disclosure. For example, the principles of the disclosure may be applied to each individual user where each user may individually deploy such a system. This enables each user to utilize the benefits of the disclosure even if any one of a large number of possible applications do not use the functionality described herein. Multiple instances of electronic devices each may process the content in various possible ways. Implementations are not necessarily in one system used by all end users. Accordingly, the appended claims and their legal equivalents should only define the invention, rather than any specific examples given.

## Claims

1. A machine-implemented method, comprising:
observing, by a computer system, directly in a transmission log, a context word distribution and a click through host distribution, in a network;
identifying, by the computer system, an entity reference in a data transmission transmitted by a user via the network;
determining, by the computer system, from the data transmission a user intention towards the entity reference using an intention model having a context multinomial set of parameters describing the context word distribution, an action multinomial parameter set describing an action prediction distribution related to the context multinomial set of parameters and a host multinomial parameter set describing the click through the host distribution from the transmission log;
predicting, by the computer system, a probability of at least one related successive web action option for the entity reference taken after the data transmission in furtherance of the user intention towards the entity reference according to the intention model for determining presentation to the user;
selecting, by the computer system, a related successive web action option set based on the probability;
generating automatically, by the computer system, an action phrasing set for the related successive web action option set;
sending the related successive web action option set to a user device for presentation to the user on a graphical user interface of the user device; and
adjusting, by the computer system, the intention model based on the action phrasing set and a user selection of a related successive web action option from the related successive web action option set presented to user on the user device.

2. The method of claim 1, further comprising: identifying the entity reference in at least one of a search query, an e-mail, and a social network post.

3. The method of claim 1, further comprising: compiling the transmission log of user transmissions for multiple users; and developing the intention model using the transmission log.

4. The method of claim 1, further comprising: ranking the related successive web action option in a related successive web action option set.

5. The method of claim 4, further comprising: incorporating a monetization factor into ranking the related successive web action option set.

6. The method of claim 1, further comprising: associating at least one of a website link and an application programming interface with the related successive web action option.

7. The method of claim 1, further comprising: identifying at least one of a website link and an application programming interface having the related successive web action option in a metadata tag.

8. The method of claim 1, further comprising: determining the entity type for the entity reference.

9. The method of claim 1, further comprising: factoring an entity type into the intention model.

10. The method of claim 1, further comprising: tailoring the intention model to the user.

11. A tangible machine-readable medium having a set of instructions detailing a method stored thereon that when executed by one or more processors cause the one or more processors to perform the method, the method comprising:
observing, by the processor, directly in a transmission log, a context word distribution and a click through host distribution, in a network;
developing, by the processor, an intention model to model a user intention, the intention model having a context multinomial set of parameters describing a context word distribution, an action multinomial parameter set describing an action prediction distribution related to the context multinomial set of parameters and a host multinomial parameter set describing the click through the host distribution from the transmission log;
identifying, by the processor, an entity reference in a data transmission transmitted by a user via the network;
determining, by the processor, from the data transmission a user intention towards the entity reference using the intention model;
predicting, by the processor, a probability of at least one related successive web action option for the entity reference taken after the data transmission in furtherance of a user intention towards the entity reference according to the intention model for determining presentation to the user;
selecting, by the processor, a related successive web action option set based on the probability;
generating automatically, by the processor, an action phrasing set for the related successive web action option set;
sending the related successive web action option set to a user device for presentation to the user; and
adjusting, by the processor, the intention model based on the action phrasing set and a user selection of a related successive web action option from the related successive web action option set presented to the user on the user device.

12. The tangible machine-readable medium of claim 11, wherein the method further comprises: factoring an entity type into the intention model.

13. The tangible machine-readable medium of claim 11, wherein the method further comprises: incorporating a monetization factor into ranking the related successive web action option set.

14. The tangible machine-readable medium of claim 11, wherein the method further comprises: ranking the related successive web action option in a related successive web action option set.

15. The tangible machine-readable medium of claim 11, wherein the method further comprises: associating at least one of a website link and an application programming interface with the related successive web action option.

16. The tangible machine-readable medium of claim 11, wherein the method further comprises: tailoring the intention model to the user.

17. A search engine server, comprising:
a communication interface configured to receive a search query from a user via a network;
a processor configured to:
observe, directly in a transmission log, a context word distribution and a click through host distribution, in the network;
develop an intention model to model a user intention, the intention model having a context multinomial set of parameters describing a context word distribution, an action multinomial parameter set describing an action prediction distribution related to the context multinomial set of parameters and a host multinomial parameter set describing the click through the host distribution from the transmission log;
identify an entity reference in the search query;
determine a user intention towards the entity reference from the search query using the intention model;
predict a probability of at least one related successive web action option set for the entity reference taken after the search query in furtherance of the user intention towards the entity reference according to the intention model for determining presentation to the user;
select a related successive web action option set based on the probability;
generate automatically an action phrasing set for the related successive web action option set;
send the related successive web action option set to a user device for presentation to the user; and
adjust the intention model based on the action phrasing set and a user selection of a related successive web action option from the related successive web action option set presented to the user on the user device; and
a memory configured to store the intention model.

18. The search engine server of claim 17, wherein the processor is configured to rank the related successive web action option set.

19. The search engine server of claim 17, wherein the processor is configured to label an action cluster of the intention model for generation of the action phrasing set.

20. The search engine server of claim 17, wherein the processor is configured to associate at least one of a website link and an application programing interface with the related successive web action option.