Patent Publication Number: US-8126891-B2

Title: Future data event prediction using a generative model

Description:
BACKGROUND 
     Predicting occurrences of events in sequential data is an issue in temporal data mining. Large amounts of sequential data are gathered in various domains such as biology, manufacturing, network usage, finance, etc. As such, the reliable prediction of future occurrences of events in sequential data may have applications in such domains. For example, predicting major breakdowns from a sequence of faults logged in a manufacturing plant may help to avoid future breakdowns, and therefore improve plant throughput. 
     One approach to predicting occurrences of future events in categorical sequences uses rule-based methods. For example, rule-based methods have been used for predicting rare events in event sequences with application to detecting system failures in computer networks. In such an approach, “positive” and “negative” data sets are created using windows that precede a target event and windows that do not, respectively. Frequent patterns of unordered events are discovered separately in both data sets and confidence-ranked collections of positive-class and negative-class patterns are used to generate classification rules. 
     Another rule-based method, called a genetic algorithm-based approach, is used to predict rare events, and begins by defining “predictive patterns” as sequences of events with some temporal constraints between connected events. A genetic algorithm is then used to identify a diverse set of predictive patterns, where a disjunction of such patterns constitutes the classification rules. Yet another rule-based method learns multiple sequence generation rules to infer properties, in the form of rules, about future events in the sequence. 
     SUMMARY 
     Various embodiments related to the prediction of future data events using a generative model are disclosed herein. For example, one disclosed embodiment comprises a method of predicting a search engine switch. First, a sequence of events are tracked in a user search. Next, a search engine switch is predicted based upon the sequence of events tracked. Then, in response to predicting a search engine switch and prior to the user requesting a search engine switch, an action is taken toward changing a user experience. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are 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. Furthermore, the claimed subject matter is not limited to implementations that solve any or all disadvantages noted in any part of this disclosure. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows an embodiment of a network search engine environment. 
         FIG. 2  shows a process flow depicting an embodiment of a method of building a generative model for predicting a future occurrence of a target event. 
         FIG. 3  shows an example embodiment of an Episode Generating Hidden Markov Model (EGH) corresponding to an example episode. 
         FIG. 4  shows a process flow depicting an embodiment of a method of predicting a user requesting a change from a first network search engine to a second network search engine. 
         FIG. 5  shows a graph depicting search engine switch prediction performance for difference lengths, W, of preceding sequences. 
         FIG. 6  shows a graph depicting search engine switch prediction performance for test sequences that are W=16 events long. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  illustrates a system  100  comprising user computing device  102  interacting with first network search engine server  104  and second network search engine server  114  via network  106 . User computing device  102  further comprises memory  108  and logic subsystem  110 , which comprises one or more processors and other logic components. Memory  108  comprises instructions executable by the logic subsystem  110  to receive user input during a search engine session, and to communicate with first network search engine server  104  and/or second network search engine server  114  during a user session. First network search engine server  104  also comprises memory  116  and logic subsystem  118 , which comprises one or more processors and other logic components. Memory  116  comprises instructions executable by the logic subsystem  118  to operate a search engine, to communicate with user computing device  102  during a user session, and to perform the various methods of predicting a search engine switch that are described herein. It will be understood that the second network search engine server also includes such components, which are omitted from  FIG. 1  for clarity. 
     As a user of computing device  102  engages in a search engine use session with first network search engine server  104 , a stream of events  112  is created. Within stream of events  112  there exists a sequence of events, representing a search session. Within a search session there exists one or more episodes, each episode comprising an ordered sequence of events. As shown in  FIG. 1 , PSRQ is an example of an episode preceding a target event Y. Each event may be associated with a value from a finite set of events, each value corresponding to an action received from computing device  102  or to a feature of a page visited by a user of computing device  102  during the search engine use session. Such features, which may be referred to herein as “page features”, may include one or more of a display time of a page, a type or item of content on a page, or any other suitable feature that is connected to a page being viewed. 
     Search engine companies derive revenue based at least in part on a number of users of the services offered by the search engine company. Therefore, such a company may be interested in retaining as many users as well as in attracting as many new users as possible. Thus, a provider of the first network search engine server  104  may wish to predict when a user of the first network search engine server  104  will request to change to the second network search engine server  114  (i.e. ending the search session with the first network search engine server  104  and initiating a search session with the second network search engine server  114 ). Thus, various embodiments are described herein that allow a search engine provider to predict a search engine switch by tracking a sequence of events in a user search and predicting a search engine switch based upon the sequence of events tracked. The user search may include one or more of a user search session. Further, in response to such a prediction, the search engine provider may send a message to the user to initiate contact with the user and thereby to attempt to retain the user prior to the user requesting a switch. In other embodiments, the second network search engine server  114  may anticipate a switch from the first network search engine server  104  to the second network search engine server  114 , and act in response to this anticipation. Such a response action may include pre-fetching search results. For example, such embodiments may include the second network search engine server  114  running a browser-toolbar plug-in to monitor search behavior on the first network search engine server. The embodiments disclosed herein may also be applicable to other episode-based predictions, including but not limited to predicting occurrences of events in sequential data gathered in various other domains such as biology, manufacturing, network usage and finance. 
     The disclosed embodiments utilize a type of Hidden Markov Model (HMM) that may be referred to as an Episode-Generating HMM (EGH). This model also may be referred to herein as a “generative model” in that the model generates a prediction based upon a stream of events. Before utilizing such a generative model, the generative model is built for a desired target event, such as a user-requested switch of search engines.  FIG. 2  illustrates an embodiment of a method  200  of building a generative model for predicting a future occurrence of a target event type, Y, based upon a plurality of preceding events E i . It will be understood that the model may be built and used on a single computing device or system (e.g. first network search engine server  104  and/or second network search engine server  114 ), or may be built on a different computing device than on which it is used. 
     Method  200  comprises, at  202 , building a training set of data from an initial set of data. Given the initial set of data, s H = E 1 , . . . , E n , . . .  , comprising a plurality of sequences of events, a selected number of events preceding each occurrence of an event of a target event type from the initial set of data are extracted, as described in detail below. In the specific example of a search engine use case, a single sequence of events may correspond to a single user search session, and a target event type may be a request to switch search engines. For n being the current time instant, each event, E i , takes values from a finite set E, of possible event types. YεE denotes the target event type whose occurrences are to be predicted in the streams. Therefore, it is desired to predict, at each time instant n, whether or not the next event E n+1 , in the stream s H , will be of the target event type Y. In other embodiments, there may be more than one target event type to predict in the problem. 
     Thus, for YεE denoting a set of target event types, it may be of interest to predict, based on events observed in the stream up to time instant n, whether or not E n+1 =Y. To build a prediction model for a target event type Y, an event window preceding occurrences of Y in the stream s H  is examined. K denotes a number of occurrences of the target event type Y, in the data stream s H . 
     Continuing with  FIG. 2 , building a training set of data at  202  comprises extracting events from s H  to form a training set of data D Y . The training set of data may be built in any suitable manner. One suitable manner is shown at  204  and  206 . First, as indicated at  204 , D Y  is initialized by setting D Y =φ. Then, at  206 , a selected number W of events preceding each event of target event type Y are extracted from the initial set of data. In various embodiments, W may be a fixed (i.e. hard-coded) value, or may be a user-defined parameter. Thus, for each t such that E t =Y, &lt;E t−W , . . . , E t−1 &gt; may be added to D Y . This yields D Y ={X 1 , X 2 , . . . X K } where each X i , i=1, . . . , K is the W-length slice, or event window, from s H , that immediately preceded the i th  occurrence of Y in s H . The X i &#39;s are referred to as the preceding sequences of Y in s H . 
     Next, statistics of the W-length sequences preceding Y may be determined for future use in predicting future occurrences of Y in the data. This may be done by learning a generative model, Λ Y , in the form of a mixture of specialized HMMs for Y, using the D Y  that was constructed at  202 . In one embodiment, constructing such a model may be done in two stages. In the first stage, a frequent episode technique may be used, where such technique has been adapted to mine multiple sequences rather than a single long event stream, to discover the frequent episodes in D Y . 
     Method  200  at  208  comprises extracting frequent episodes from the training set of data D Y , where each episode comprises an ordered sequence of events in the training set of data D Y , wherein determining each frequent episode for extracting comprises detecting non-overlapping occurrences of the episode in the training set of data. 
     For example, consider the set of K event sequences introduced above, D Y ={X 1 , X 2 , . . . , X K }, where each X i  is an event sequence constructed over the finite set, E, of possible event types. The size of the set is given by |E|=M. The patterns in the framework are episodes, where an episode is an ordered tuple of event types. For example, (A→B→C), is an episode of size 3. An episode is said to occur in an event sequence if there exist events in the sequence appearing in the same relative ordering as in the episode. 
     Any suitable definition of episode frequency may be used to define frequent episodes for extraction. For example, in one embodiment, the frequency of an episode may be defined as a non-overlapped occurrences-based frequency, adapted to the case of multiple event sequences. Two occurrences of an episode, α, are said to be non-overlapped if no events associated with one occurrence appear in the other occurrence. A collection of occurrences of α is said to be non-overlapped if every pair of occurrences in it is non-overlapped. The frequency of α in an event sequence may be defined as the cardinality of the largest set of non-overlapped occurrences of α in the sequence. With these definitions, the frequency of episode, α, in a data set, D Y , of event sequences, may be defined as the sum of sequence-wise frequencies of α in the event sequences that constitute D Y . 
     Method  200  next comprises, at  210 , filtering the plurality of frequent episodes to determine a plurality of significant frequent episodes. In one embodiment, process  210  may comprise, at  212 , applying a significance test based on a frequency of the frequent episode, a length of the training set and a size of the finite set of events. Details of such a significance test are as follows. 
     Consider an N-node episode, α, whose frequency in the data, D Y , is f α . The significance test for α scores the alternate hypothesis, [H 1 :D Y  is drawn from the EGH, Λ α ], against the null hypothesis, [H 0 :D Y  is drawn from an independent, identically distributed source]. An upper bound, ε for the Type I error probability, (i.e. the probability of wrong rejection of H 0 ) is chosen. Taking T to be the total number of events in all the sequences of D Y  put together, and M to be the size of the set E, the significance test rejects H 0  (i.e. it declares α as significant) if 
                 f   α     &gt;     Γ   N       ,         
where Γ is determined as follows:
 
     
       
         
           
             Γ 
             = 
             
               
                 T 
                 M 
               
               + 
               
                 
                   
                     
                       ( 
                       
                         T 
                         M 
                       
                       ) 
                     
                     ⁢ 
                     
                       ( 
                       
                         1 
                         - 
                         
                           1 
                           M 
                         
                       
                       ) 
                     
                   
                 
                 ⁢ 
                 
                   
                     
                       Φ 
                       
                         - 
                         1 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         1 
                         - 
                         ɛ 
                       
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     Here Φ −1  (•) denotes the inverse cumulative distribution function of the standard normal random variable. For ε=0.5, Γ=(T/M) may be obtained, and the threshold increases for smaller values of ε. For typical values of T and M, T/M may be the dominant term in the expression for Γ, and hence, 
             T   NM         
may be used as the frequency threshold to obtain significant N-node episodes.
 
     One feature of this significance test is that there is no need to explicitly estimate any HMMs to apply the test. The theoretical connections between episodes and EGHs allows for a test of significance that is based only on frequency of the episode, length of the data sequence and size of the set. 
     Continuing with  FIG. 2 , at  212 , upon applying such a frequency test, a set of J significant frequent episodes may be obtained, F s ={α i , . . . , α J }, for episode sizes, 1, . . . , W. Method  200  next comprises, at  214 , associating each significant frequent episode with a HMM in which a frequency ordering among the significant frequent episodes is preserved as a likelihood ordering among a corresponding mixture of HMMs. This may be performed in any suitable manner. For example, in one embodiment, process  214  further comprises, at  216 , associating each significant frequent episode α j  with an EGH. The EGH, Λ αj , is based on the episode&#39;s frequency in the data. Associating each significant frequent episode with a HMM comprises constructing a tuple comprising a state space vector of dimension twice the length of the episode, a symbols vector of symbols emitted from a plurality of corresponding episode states, and a noise parameter, as described below. 
     Considering an N-node episode, α=(A 1 → . . . →A N ), associated with an EGH, Λ α , the EGH Λ α has 2N states, where the states 1 through N constitute the episode states, and states (N+1) to 2N, the noise states. The symbol probability distribution in episode state, i, 1≦i≦N, is the delta function, δ Ai (•). All transition probabilities are fully characterized through what is known as the EGH noise parameter, ηε(0, 1), where transitions into noise states have probability η, while transitions into episode states have probability (1−η). The initial state for the EGH is state 1 with probability (1−η), and state 2N with probability η. An example of a 3-node episode is described below for the case of N=3 as shown in  FIG. 3 . 
       FIG. 3  illustrates an example EGH corresponding to an example episode (A→B→C). Such an episode has 2N=6 states, where states 1-3 are episode states and states 4-6 are noise states. The dotted circle, along with its outgoing arcs, represents the initial state probability distribution. The symbol probabilities are shown alongside corresponding nodes. For example, δ A (•) denotes a probability density function of 1 for symbol A and 0 for all others. Likewise for δ B (•) and δ C (•). Transitions into noise states have probability η, while transitions into episode states have probability (1−η). The uniform probability density function over the symbol set is denoted by u(•). This example EGH may only emit an “A” in state 1, a “B” in state 2 and a “C” in state 3. If η is small, the output sequence generated by this example EGH would be an event sequence with many occurrences of the episode (A→B→C). 
     Continuing with  FIG. 2 , associating each significant frequent episode with an EGH further comprises the following. For an N-node episode α=(A 1 → . . . →A N ) which occurs in the data, D Y ={X 1 , X 2 , . . . , X K }, with frequency, f α , the EGH associated with α is denoted by the tuple, Λ α =(S, A α , η α ). Here, S={1, . . . , 2N}, denotes the state space, A α =(A 1 , . . . , A N ), denotes the symbols that are emitted from the corresponding episode states, and η, the noise parameter, is set equal to 
               T   -     Nf   α       T         
if it is less than
 
             M     M   +   1           
and to 1 otherwise.
 
     Next method  200 , at  218 , comprises building the generative model by forming a weighted mixture of the HMMs for the target event type. Process  218  further comprises at  220 , forming a weighted mixture of the HMMs by using an Expectation Maximization (EM) algorithm to estimate a plurality of mixture coefficients. A more detailed discussion of the structure of the weighted mixture of HMMs follows. 
     For a set of significant episodes F s ={α 1 , . . . , α J }, and EGH Λ αj  associated with each α j  for j=1, . . . , J, each sequence X i εD Y  is now assumed to be generated by a mixture of the EGHs, Λ αj , j=1, . . . , J. Denoting the mixture of EGHs by Λ Y , and assuming that the K sequences in D Y  are independent, the likelihood of D Y  under the mixture model may be written as follows: 
     
       
         
           
             
               
                 
                   
                     P 
                     ⁡ 
                     
                       [ 
                       
                         
                           D 
                           Y 
                         
                         | 
                         
                           Λ 
                           Y 
                         
                       
                       ] 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         1 
                       
                       K 
                     
                     ⁢ 
                     
                       P 
                       ⁡ 
                       
                         [ 
                         
                           
                             X 
                             i 
                           
                           | 
                           
                             Λ 
                             Y 
                           
                         
                         ] 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         1 
                       
                       K 
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               1 
                             
                             J 
                           
                           ⁢ 
                           
                             
                               θ 
                               j 
                             
                             ⁢ 
                             
                               P 
                               ⁡ 
                               
                                 [ 
                                 
                                   
                                     X 
                                     i 
                                   
                                   | 
                                   
                                     Λ 
                                     
                                       α 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       j 
                                     
                                   
                                 
                                 ] 
                               
                             
                           
                         
                         ) 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
     Here, each EGH, Λ αj , may be fully characterized by the significant episode, α j , and its corresponding noise parameter, η j . Consequently, the only unknowns in the expression for likelihood under the mixture model are the mixture coefficients, θ j , j=1, . . . , J. An Expectation Maximization (EM) algorithm is used to estimate the mixture coefficients of Λ Y  from the data set D Y , and is described in more detail as follows. 
     Let θ g ={θ 1   g , . . . , θ J   g } denote the current guess for the mixture coefficients being estimated. At the start of the EM procedure θ g  is initialized uniformly, i.e. θ j   g  is set to be 
               θ   j   g     =     1   J           
for all j. By regarding θ j   g  as the prior probability corresponding to the j th  mixture component Λ αj , the posterior probability for the l th  mixture component, with respect to the i th  sequence X i εD Y , can be written using Bayes&#39; Rule:
 
     
       
         
           
             
               P 
               ⁡ 
               
                 [ 
                 
                   
                     l 
                     | 
                     
                       X 
                       i 
                     
                   
                   , 
                   
                     Θ 
                     g 
                   
                 
                 ] 
               
             
             = 
             
               
                 
                   
                     θ 
                     l 
                     g 
                   
                   ⁢ 
                   
                     P 
                     ⁡ 
                     
                       [ 
                       
                         
                           X 
                           i 
                         
                         | 
                         
                           Λ 
                           
                             α 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             l 
                           
                         
                       
                       ] 
                     
                   
                 
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       1 
                     
                     J 
                   
                   ⁢ 
                   
                     
                       θ 
                       j 
                       g 
                     
                     ⁢ 
                     
                       P 
                       ⁡ 
                       
                         [ 
                         
                           
                             X 
                             i 
                           
                           | 
                           
                             Λ 
                             
                               α 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               j 
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               . 
             
           
         
       
     
     After computing P[l|X i , Θ g ] for l=1, . . . , J and i=1, . . . , K, using the current guess Θ g , a revised estimate may be obtained, Θ new ={Θ 1   new , . . . , Θ J   new }, for the mixture coefficients using the following update rule: 
     
       
         
           
             
               
                 for 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 l 
               
               = 
               1 
             
             , 
             … 
             ⁢ 
             
                 
             
             , 
             J 
             , 
             
               
                 compute 
                 ⁢ 
                 
                   : 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   θ 
                   l 
                   new 
                 
               
               = 
               
                 
                   1 
                   K 
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     K 
                   
                   ⁢ 
                   
                     
                       P 
                       ⁡ 
                       
                         [ 
                         
                           l 
                           | 
                           
                             
                               X 
                               
                                 i 
                                 , 
                               
                             
                             ⁢ 
                             
                               Θ 
                               g 
                             
                           
                         
                         ] 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
     The revised estimate Θ new , is used as the “current guess” Θ g , in the next iteration, and the procedure, namely the computation of the prior two equations, is repeated until convergence. Note that computation of the likelihood, P└X i |Λ αj ┘, j=1, . . . , J needed in the Bayes&#39; Rule equation, is done efficiently by approximating each likelihood along the corresponding most likely state sequence, 
     
       
         
           
             
               
                 P 
                 ⁡ 
                 
                   [ 
                   
                     
                       X 
                       i 
                     
                     | 
                     
                       Λ 
                       
                         α 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         l 
                       
                     
                   
                   ] 
                 
               
               = 
               
                 
                   
                     ( 
                     
                       
                         η 
                         α 
                       
                       M 
                     
                     ) 
                   
                   T 
                 
                 ⁢ 
                 
                   
                     ( 
                     
                       
                         1 
                         - 
                         
                           η 
                           α 
                         
                       
                       
                         
                           η 
                           α 
                         
                         / 
                         M 
                       
                     
                     ) 
                   
                   
                     
                       Nf 
                       α 
                     
                     ⁡ 
                     
                       ( 
                       
                         X 
                         i 
                       
                       ) 
                     
                   
                 
               
             
             , 
           
         
       
     
     where f α (X i ) refers to frequency of episode α in sequence X i . This way, the likelihood is a simple by-product of the non-overlapped occurrences-based frequency counting algorithm. Even during the prediction phase, to be discussed later, this approximation may be used when computing the likelihood of the current window, X, of events, under the mixture model, Λ Y . 
     One property of the EGH association is given by the following theorem. Let D Y ={X 1 , X 2 , . . . , X K } be the given data set of event sequences over the set E (of size |E|=M). Let α and β be two N-node episodes occurring in D Y  with frequencies f α  and f β  respectively. Let Λ α  and Λ β  be the EGHs associated with α and β. Let q α * and q β * be the most likely state sequences for D Y  under Λ α  and Λ β  respectively. If η α  and η β  are both less than 
             M     M   +   1           
then,
 
     (i) f α &gt;f β  implies P(D Y ,q α *|Λ α )&gt;P(D Y ,q β *|Λ β ) and 
     (ii) P(D Y , q α *|Λ α )&gt;P(D Y ,q β *|Λ β ) implies f α ≧f β . 
     Stated informally, the result shows that, among sufficiently frequent episodes, the more frequent episodes may be associated with EGHs with higher data likelihoods. Therefore, for any episode, α, with 
                 η   α     &lt;     M     M   +   1         ,         
the joint probability of the data D Y , and the most likely state sequence q α *, is given by
 
     
       
         
           
             
               P 
               ⁡ 
               
                 [ 
                 
                   
                     D 
                     Y 
                   
                   , 
                   
                     
                       q 
                       α 
                       * 
                     
                     | 
                     
                       Λ 
                       α 
                     
                   
                 
                 ] 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       η 
                       α 
                     
                     M 
                   
                   ) 
                 
                 T 
               
               ⁢ 
               
                 
                   
                     ( 
                     
                       
                         1 
                         - 
                         
                           η 
                           α 
                         
                       
                       
                         
                           η 
                           α 
                         
                         / 
                         M 
                       
                     
                     ) 
                   
                   
                     Nf 
                     α 
                   
                 
                 . 
               
             
           
         
       
     
     Continuing with  FIG. 2 , method  200 , at  222 , lastly comprises outputting the generative model. In the context of the specific embodiments described above, process  222  may comprises, at  224 , outputting the generative model Λ Y . 
     After production of the generative model, the model may be used to predict future occurrences of events of a target event type. For example,  FIG. 4  depicts an embodiment of a method  400  of predicting whether a user of a first network search engine will request a change to a second network search engine. Method  400  at  402  comprises monitoring, via a generative model comprising a weighted mixture of HMMs, a stream of events in a search engine use session between the user and the first network search engine for an occurrence of one or more significant frequent episodes corresponding to a likelihood of a search engine change. In some embodiments, the weighted mixture of HMMs may comprise a weighted mixture of EGHs. Further, such a request to change to the second network search engine may be represented in the generative model by a target event type within the stream of events. Therefore, requesting a change to a second network search engine comprises detecting a significant frequent episode preceding the target event type as recognized by the generative model. 
     In one embodiment, as illustrated at  404 , monitoring the stream of events comprises monitoring a fixed-length event window. In alignment with the framework introduced in the discussion of  FIG. 2 , consider the event stream s=&lt;E 1 , . . . , E n , . . . &gt; in which a future occurrence of target event type Y is to be predicted. For n denoting the current time instant, a W-length window of events up to and including the n th  event in s is constructed, X=[E n−w+1 , . . . , E n ]. A condition the algorithm uses to predict E n+1 =Y is based on the likelihood of the window, X, of events under the mixture model, Λ Y . Thus,  402  further comprises at  404 , given a generative model, Λ Y ={(α j , θ j ):j=1, . . . , J}, for all n≧W, setting X=&lt;E n−W+1 , . . . , E n &gt; and setting t Y =0. 
     Next, method  400  at  406  comprises determining via the generative model a prediction that the user of the first network search engine will request a change to the second network search engine. As illustrated at  408 , in some embodiments, process  406  may further comprise determining this prediction by calculating a likelihood P[X|Λ Y ] of the event window X under the generative model Λ Y . Further, as illustrated at  410 , in some embodiments, process  406  may further comprise predicting that the user of the first network search engine will request a change to the second network search engine if the likelihood exceeds a threshold value γ. The threshold value γ may be selected during the training phase for a chosen level of recall, or may be selected in any other suitable manner. 
     However, in some embodiments, this threshold condition may be considered insufficient by itself to predict an occurrence of event type Y, for the following reason. The likelihood P[X|Λ Y ] will be high whenever X contains one or more occurrences of significant episodes (from F s ). These occurrences, however, may correspond to a previous occurrence of Y within X, and hence may not be predictive of any future occurrence(s) of Y. To address this possibility, a simple heuristic may be used that first identifies the last of occurrence of Y (if any) within the window X and remembers the corresponding location in t Y . The algorithm predicts E n+1 =Y only if, in addition to P[X|Λ Y ]&gt;γ, there exists at least one occurrence of a significant episode after the last occurrence of Y in X. This heuristic may be easily implemented using the frequency counting algorithm of frequent episode discovery. Thus, if P[X|Λ Y ]&gt;γ then if YεX then set t Y  to the largest t such that E t =Y and n−W+1≦t≦n if there exists an αεF s  that occurs in X after t Y  then predict E n+1 =Y. Otherwise, predict E n+1 ≠Y. 
     Continuing with  FIG. 4 , method  400  comprises, at  412 , outputting the prediction that the user of the first network search engine will request a change to the second network search engine, and, at  414 , taking an action toward changing a user experience in response to the prediction. 
     Taking an action toward changing a user experience at  414  may include one or more of sending a message to the user, offering the user search assistance, adapting the user experience on the user&#39;s behalf, and recommending an action for the user to take. For example the origin, or pre-switch, engine may offer users a new interface affordance (e.g., sort search results based on different meta-data), or search paradigm (e.g., engage in an instant messaging conversation with a domain expert) to encourage them to stay. In contrast, the destination, or post-switch, engine could pre-fetch search results in anticipation of the incoming query. Furthermore, such a message may be sent to the user in any suitable manner, such as by sending one or more of an instant message, an email message, an internet telephone message, or a live chat request message. 
       FIG. 5  illustrates a graph depicting search engine switch prediction performance for difference lengths, W, of preceding sequences. Experiments were conducted using EGHs to predict whether a user will switch search engines, given the user&#39;s recent interaction history with the search engine. Three months of interaction logs were analyzed, where the interaction logs were obtained during November 2006, December 2006, and May 2007 from hundreds of thousands of consenting users through an installed browser tool-bar. All personally identifiable information was removed from the logs prior to this analysis. In each month&#39;s data, the first half of the data was used for algorithm training and the second half of the data was used for algorithm testing. 
     From these logs, search sessions were extracted. Every session began with a query to one of four internet search engines, and contained either search engine result pages, visits to search engine homepages, or pages connected by a hyperlink trail to a search engine result page. A session ended if the user was idle for more than 30 minutes. Users with less than five search sessions were removed to reduce potential bias from low numbers of observed interaction sequences or erroneous log entries. A search engine switch was defined as one of three behaviors within a session: (i) issuing a query to a different search engine, (ii) navigating to the homepage of a different search engine, or (iii) querying for a different search engine name. Around 8% of search sessions extracted from the logs contained a search engine switch. 
     Each search session was represented as a character sequence to allow for easy manipulation and analysis, and to remove any identifying information. This allows privacy to be protected while preserving the salient aspects of search behavior to perform the predictive analyses. To represent the search sessions, an set was formed with the goal of maximum simplicity. Since page dwell times may be useful information, page dwell times were encoded as well. In this analysis, dwell times were bucketed into ‘short’, ‘medium’, and ‘long’ based on a tripartite division of the dwell times across all users and all pages viewed. 
     Many millions of such sequences were extracted from the interaction logs to use in the training and testing of the prediction algorithm. Further, these sequences were encoded using one symbol for every action-page pair. An action is a user interaction event such as a hyperlink click. A page in this case is a Web page, although could be any information object, with interaction attributes such as display time. The set used had 62 symbols total, which reduced to 55 symbols by considering all pairs with a Y as a single symbol, where Y is the target event type. For example, if a user issued a query, viewed the search result page for a short period of time, clicked on a result link, viewed the page for a short time, and then decided to switch search engines, the session would be represented as ‘QRSPY,’ where Q=Issue Query, R=Visit first search engine result page (SERP) (short display time), S=Click result hyperlink, P=Visit non-SERP page (short display time), and then Y=Switch search engine. 
     One challenge in predicting a change of search engines derives from the very low number of switches compared to non-switches. For example, in one data set, the most common string preceding a switch occurred about 2.6 million times, but led to a switch only 14,187 times. A string-matching algorithm used as a control described above obtained high precision (&gt;85%) at low recall (5%). However, precision reduced rapidly as recall increased (i.e., to a precision of less than 20% at a recall of 20%). The results did not improve for different window lengths. This trend was also observed in the second and third data sets. 
     In contrast, the results obtained for search engine switch prediction using the EGH mixture model described herein demonstrate high precision even at higher recall. First,  FIG. 5  illustrates a graph depicting search engine switch prediction performance for difference lengths, W, of preceding sequences, for results obtained using the approach described herein for one of the three test data sets, with the first half of the data used for training and the second half of the data used for testing. A range of values for W between 2 and 16 was examined. For W=16, the algorithm achieves a precision greater than 95% at recalls between 75% and 80%. 
     Next,  FIG. 6  illustrates a graph depicting search engine switch prediction performance for test sequences that are W=16 events long. In this test, one full data set of the three data sets was used to produce the generative model, and the resulting generative model was used to test prediction performance all three sets of data. Again, the approach described herein achieved precision greater than 95% at recalls between 75% and 80%. Similar results were obtained when the algorithm was trained using the data from each of the other two sets of data and used to predict search engine switches on the test sets from all three months. 
     While described in the context of predicting a switch of search engines, it will be understood that the embodiments described herein may be applicable to other use environments as well, including but not limited to applications in biology, manufacturing, network usage, finance, etc. such as predicting major breakdowns from a sequence of faults logged in a manufacturing plant to avoid future breakdowns, and/or detecting system failures in computer networks. It will further be appreciated that the computing devices described herein may be any suitable computing device configured to execute the programs described herein. For example, the computing devices may be a mainframe computer, personal computer, laptop computer, portable data assistant (PDA), computer-enabled wireless telephone, networked computing device, or other suitable computing device, and may be connected to each other via computer networks, such as the Internet. These computing devices typically include a processor and associated volatile and non-volatile memory, and are configured to execute programs stored in non-volatile memory using portions of volatile memory and the processor. As used herein, the term “program” refers to software or firmware components that may be executed by, or utilized by, one or more computing devices described herein, and is meant to encompass individual or groups of executable files, data files, libraries, drivers, scripts, database records, etc. It will be appreciated that computer-readable media may be provided having program instructions stored thereon, which upon execution by a computing device, cause the computing device to execute the methods described above and cause operation of the systems described above. 
     It will further be understood that the embodiments described herein are exemplary in nature, and that these specific embodiments or examples are not to be considered in a limiting sense, because numerous variations are contemplated. Accordingly, the present disclosure includes all novel and non-obvious combinations and sub-combinations of the various embodiments disclosed herein, as well as any and all equivalents thereof.