User intention modeling for web navigation

US 6,993,586 B2
Filed: 05/09/2002
Issued: 01/31/2006
Est. Priority Date: 05/09/2002
Status: Active Grant

First Claim

Patent Images

1. A method for modeling a user intention during network navigation, the method comprising:

predicting, based on a statistical multi-step n-gram probability model, an optimal information goal of the user, the optimal information goal being based on a sequence of previously visited network content pieces and a globally optimized navigation path through the sequence, the optimal information goal being predicted as follows;

recording a history of user action, the history comprising information corresponding to user navigation to a plurality of networked content pieces, the information indicating at least the sequence of previously visited network content pieces;

for at least a portion of the sequence data, calculating respective probabilities that a user would visit a particular content piece n in the sequence from a content piece n−

1 in the sequence, a prediction of the optimal information goal being based on the respective probabilities, the calculating comprising;

$\begin{matrix} \Pr (w_{i} \langle w_{1}, ⩓, w_{i - 1}) \approx \Pr (w_{i} | w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) \\ \begin{matrix} = \frac{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i}) / C_{n}}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) / C_{n - 1}} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} * C; \end{matrix} \end{matrix}$ wherein Pr represents the probability;

wherein user navigation to the plurality of networked content pieces is represented as w₁, w₂, Λ

, w_i, Λ

, w_L, where w_iis the ith visited content piece in the sequence; and

wherein C(w_i−

n+1, . . . , w_i−

2, w_i−

1w_i) denotes the count of an n-Gram (w_i−

n+1, . . . , w_i−

2, w_i−

1, w_i) appearing in training data, C_nis a total number of the n-grams, C_n−

1is a total number of the (n−

1)-grams, C equals to C_n/C_n−

1, C_n, C_n−, and C are constants.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

The disclosed subject matter models or predicts a user'"'"'s intention during network or WWW navigation. Specifically, a statistical multi-step n-gram probability model is used to predict a user'"'"'s optimal information goal. The optimal information goal is based on a sequence of previously visited network content pieces and a globally optimized navigation path through the sequence.

73 Citations

View as Search Results

36 Claims

1. A method for modeling a user intention during network navigation, the method comprising:
- predicting, based on a statistical multi-step n-gram probability model, an optimal information goal of the user, the optimal information goal being based on a sequence of previously visited network content pieces and a globally optimized navigation path through the sequence, the optimal information goal being predicted as follows;
  
  recording a history of user action, the history comprising information corresponding to user navigation to a plurality of networked content pieces, the information indicating at least the sequence of previously visited network content pieces;
  
  for at least a portion of the sequence data, calculating respective probabilities that a user would visit a particular content piece n in the sequence from a content piece n−
  
  1 in the sequence, a prediction of the optimal information goal being based on the respective probabilities, the calculating comprising;
  
  $\begin{matrix} \Pr (w_{i} \langle w_{1}, ⩓, w_{i - 1}) \approx \Pr (w_{i} | w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) \\ \begin{matrix} = \frac{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i}) / C_{n}}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) / C_{n - 1}} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} * C; \end{matrix} \end{matrix}$ wherein Pr represents the probability;
  
  wherein user navigation to the plurality of networked content pieces is represented as w₁, w₂, Λ
  
  , w_i, Λ
  
  , w_L, where w_iis the ith visited content piece in the sequence; and
  
  wherein C(w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1w_i) denotes the count of an n-Gram (w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1, w_i) appearing in training data, C_nis a total number of the n-grams, C_n−
  
  1is a total number of the (n−
  
  1)-grams, C equals to C_n/C_n−
  
  1, C_n, C_n−, and C are constants.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
- - 2. The method of claim 1, wherein a content piece of the sequence comprises a Web page.
  - 3. The method of claim 1, wherein predicting the globally optimized navigation path is dynamically performed responsive to user Web navigation.
  - 4. The method of claim 1, wherein the portion comprises a session of user access to particular ones of the networked content pieces.
  - 5. The method of claim 1, wherein the history further comprises a URL, a hyperlink, a user name, a start time, text corresponding to a URL, a query, elapsed time, or an object name.
  - 6. The method of claim 1, wherein the globally optimized navigation path is based on the following:
    - $\underset{w_{i}}{argmax} \prod_{i = k + 1}^{\infty} \Pr (w_{i} | w_{i - 2} w_{i - 1}); and,$ wherein k represents a number of networked content pieces that the user has already visited.
  - 7. The method of claim 1, wherein the globally optimized navigation path is based on the following:
    - $\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log (\Pr (w_{i} | w_{i - 2} w_{i - 1}));$ wherein k represents a number of networked content pieces that the user has already visited; and
      
      wherein t indicates how many steps are predicted.
  - 8. The method of claim 7 further comprising dynamically determining how many steps to the optimal information goal are to be predicted by employing a perplexity that reflects the entropy of the globally optimized navigation path.
  - 9. The method of claim 7, wherein the optimal information goal is determined according to the following:
    - $\underset{t}{argmax} (\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log \Pr (w_{i} | w_{i - 2} w_{i - 1})) .$

10. A computer-readable medium for modeling a user intention during network navigation, the computer-readable medium comprising computer-executable instructions for:
- predicting, based on a statistical multi-step n-gram probability model, an optimal information goal of the user, the optimal information goal being based on a sequence of previously visited network content pieces and a globally optimized navigation path through the sequence, the optimal information goal being predicted as follows;
  
  recording a history of user action, the history comprising information corresponding to user navigation to a plurality of networked content pieces, the information indicating at least the sequence of previously visited network content pieces;
  
  for at least a portion of the sequence data, calculating respective probabilities that a user would visit a particular content piece n in the sequence from a content piece n−
  
  1 in the sequence, a prediction of the optimal information goal being based on the respective probabilities, the calculating comprising;
  
  $\begin{matrix} \Pr (w_{i} \langle w_{1}, ⩓, w_{i - 1}) \approx \Pr (w_{i} | w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) \\ = \frac{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i}) / C_{n}}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) / C_{n - 1}} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} * C; \end{matrix}$ wherein Pr represents the probability;
  
  wherein user navigation to the plurality of networked content pieces is represented as w₁, w₂, Λ
  
  , w_i, Λ
  
  , w_L, where w_iis the ith visited content piece in the sequence; and
  
  wherein C(w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1w_i) denotes the count of an n-Gram (w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1, w_i) appearing in training data, C_nis a total number of the n-grams, C_n−
  
  1is a total number of the (n−
  
  1)-grams, C equals to C_n/C_n−
  
  1, C_n, C_n−, and C are constants.
- View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
- - 11. The computer-readable medium of claim 10, wherein a content piece of the sequence comprises a Web page.
  - 12. The computer-readable medium of claim 10, wherein predicting the globally optimized navigation path is dynamically performed responsive to user Web navigation.
  - 13. The computer-readable medium of claim 10, wherein the portion comprises a session of user access to particular ones of the networked content pieces.
  - 14. The computer-readable medium of claim 10, wherein the history further comprises a, URL, a hyperlink, a user name, a start time, text corresponding to a URL, a query, elapsed time, or an object name.
  - 15. The computer-readable medium of claim 10, wherein the globally optimized navigation path is based on the following:
    - $\underset{w_{i}}{argmax} \prod_{i = k + 1}^{\infty} \Pr (w_{i} | w_{i - 2} w_{i - 1}); and,$ wherein k represents a number of networked content pieces that the user has already visited.
  - 16. The computer-readable medium of claim 10, wherein the globally optimized navigation path is based on the following:
    - $\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log (\Pr (w_{i} | w_{i - 2} w_{i - 1}));$ wherein k represents a number of networked content pieces that the user has already visited; and
      
      wherein t indicates how many steps are predicted.
  - 17. The computer-readable medium of claim 16 further comprising instructions for dynamically determining how many steps to the optimal information goal are to be predicted by employing a perplexity that reflects the entropy of the globally optimized navigation path.
  - 18. The computer-readable medium of claim 16, wherein the optimal information goal is determined according to the following:
    - $\underset{t}{argmax} (\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log (\Pr (w_{i} | w_{i} - 2 w_{i - 1})) .$

19. A computing device for modeling a user intention during network navigation, the computing device comprising:
- a processor; and
  
  a memory coupled to the processor, the memory comprising computer-executable instructions that are fetched and executed by the processor for;
  
  predicting, based on a statistical multi-step n-gram probability model, an optimal information goal of the user, the optimal information goal being based on a sequence of previously visited network content pieces and a globally optimized navigation path trough the sequence, the optimal information goal being predicted as follows;
  
  recording a history of user action, the history comprising information corresponding to user navigation to a plurality of networked content pieces, the information indicating at least the sequence of previously visited network content pieces;
  
  for at least a portion of the sequence data, calculating respective probabilities that a user would visit a particular content piece n in the sequence from a content piece n−
  
  1 in the sequence, a prediction of the optimal information goal being based on the respective probabilities, the calculating comprising;
  
  $\begin{matrix} \Pr (w_{i} \langle w_{1}, ⩓, w_{i - 1}) \approx \Pr (w_{i} | w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) \\ \begin{matrix} = \frac{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i}) / C_{n}}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) / C_{n - 1}} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} * C; \end{matrix} \end{matrix}$ wherein Pr represents the probability;
  
  wherein user navigation to the plurality of networked content pieces is represented as w₁, w₂, Λ
  
  , w_i, Λ
  
  , w_L, where w_iis the ith visited content piece in the sequence; and
  
  wherein C(w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1, w_i) denotes the count of an n-Gram (w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1, w_i) appearing in training data, C_nis a total number of the n-grams, C_n−
  
  1is a total number of the (n−
  
  1)-grams, C equals to C_n/C_n−
  
  1, C_n, C_n−, and C are constants.
- View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
- - 20. The computing device of claim 19, wherein a content piece of the sequence comprises a Web page.
  - 21. The computing device of claim 19, wherein predicting the globally optimized navigation path is dynamically performed responsive to user Web navigation.
  - 22. The computing device of claim 19, wherein the portion comprises a session of user access to particular ones of the networked content pieces.
  - 23. The computing device of claim 19, wherein the history further comprises a URL, a hyperlink, a user name, a start time, text corresponding to a URL, a query, elapsed time, or an object name.
  - 24. The computing device of claim 19, wherein the globally optimized navigation path is based on the following:
    - $\underset{w_{i}}{argmax} \prod_{i = k + 1}^{\infty} \Pr (w_{i} | w_{i - 2} w_{i - 1}); and,$ wherein k represents a number of networked content pieces that the user has already visited.
  - 25. The computing device of claim 19, wherein the globally optimized navigation path is based on the following:
    - $\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log (\Pr (w_{i} | w_{i} - 2 w_{i - 1}));$ wherein k represents a number of networked content pieces that the user has already visited; and
      
      wherein t indicates how many steps are predicted.
  - 26. computing device of claim 25, further comprising instructions for dynamically determining how many steps to the optimal information goal are to be predicted by employing a perplexity that reflects the entropy of the globally optimized navigation path.
  - 27. computing device of claim 25, wherein the optimal information goal is determined according to the following:
    - $\underset{t}{argmax} (\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log (\Pr (w_{i} | w_{i} - 2 w_{i - 1})) .$

28. A computer device for modeling a user intention during network navigation, the computing device comprising processing means for:
- predicting, based on a statistical multi-step n-gram probability model, an optimal information goal of the user, the optimal information goal being based on a sequence of previously visited network content pieces and a globally optimized navigation path through the sequence, the optimal information goal being predicted as follows;
  
  recording a history of user action, the history comprising information corresponding to user navigation to a plurality of networked content pieces, the information indicating at least the sequence of previously visited network content pieces;
  
  for at least a portion of the sequence data, calculating respective probabilities that a user would visit a particular content piece n in the sequence from a content piece n−
  
  1 in the sequence, a prediction of the optimal information goal being based on the respective probabilities, the calculating comprising;
  
  $\begin{matrix} \Pr (w_{i} \langle w_{1}, ⩓, w_{i - 1}) \approx \Pr (w_{i} | w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) \\ \begin{matrix} = \frac{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{\Pr (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i}) / C_{n}}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}) / C_{n - 1}} \\ = \frac{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1}, w_{i})}{C (w_{i - n + 1}, \dots, w_{i - 2}, w_{i - 1})} * C; \end{matrix} \end{matrix}$ wherein Pr represents the probability;
  
  wherein user navigation to the plurality of networked content pieces is represented as w₁, w₂, Λ
  
  , w_i, Λ
  
  , w_L, where w_iis the ith visited content piece in the sequence; and
  
  wherein C(w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1, w_i) denotes the count of an n-Gram (w_i−
  
  n+1, . . . , w_i−
  
  2, w_i−
  
  1, w_i) appearing in training data, C_nis a total number of the n-grams, C_n−
  
  1is a total number of the (n−
  
  1)-grams, C equals to C_n/C_n−
  
  1, C_n, C_n−, and C are constants.
- View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36)
- - 29. The computing device of claim 28, wherein a content piece of the sequence comprises a Web page.
  - 30. The computing device of claim 28, wherein predicting the globally optimized navigation path is dynamically performed responsive to user Web navigation.
  - 31. The computing device of claim 28, wherein the portion comprises a session of user access to particular ones of the networked content pieces.
  - 32. The computing device of claim 28, wherein the history further comprises a URL, a hyperlink, a user name, a start time, text corresponding to a URL, a query, elapsed time, or an object name.
  - 33. The computing device of claim 28, wherein the globally optimized navigation path is based on the following:
    - $\underset{w_{i}}{argmax} \prod_{i = k + 1}^{\infty} \Pr (w_{i} | w_{i - 2} w_{i - 1}); and,$ wherein k represents a number of networked content pieces that the user has already visited.
  - 34. The computing device of claim 28, wherein the globally optimized navigation path is based on the following:
    - $\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log (\Pr (w_{i} | w_{i} - 2 w_{i - 1}));$ wherein k represents a number of networked content pieces that the user has already visited; and
      
      wherein t indicates how many steps are predicted.
  - 35. The computing device of claim 34 further comprising means for dynamically determining how many steps to the optimal information goal are to be predicted by employing a perplexity that reflects the entropy of the globally optimized navigation path.
  - 36. The computing device of claim 34, wherein the optimal information goal is determined according to the following:
    - $\underset{t}{\arg \max} (\frac{1}{t} \sum_{i = k + 1}^{i = k + t} \log \Pr (w_{i} | w_{i - 2} w_{i - 1})) .$

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Microsoft Technology Licensing LLC (Microsoft Corporation)
Original Assignee
Microsoft Corporation
Inventors
Chen, Zheng, Sun, Xiaoming, Wenyin, Liu
Primary Examiner(s)
Cardone, Jason D

Application Number

US10/142,625
Publication Number

US 20030212760A1
Time in Patent Office

1,363 Days
Field of Search

709/201, 709/203, 709/218, 709/228, 709/238, 711/137
US Class Current

709/228
CPC Class Codes

G06F 16/954   Navigation, e.g. using cate...

G06F 17/18   for evaluating statistical ...

H04L 67/564   Enhancement of application ...

H04L 67/568   Storing data temporarily at...

H04L 67/62   Establishing a time schedul...

H04L 67/63   Routing a service request d...

H04L 69/329   in the application layer [O...

H04L 9/40   Network security protocols

User intention modeling for web navigation

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

73 Citations

36 Claims

Specification

Solutions

Use Cases

Quick Links

User intention modeling for web navigation

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

73 Citations

36 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links