Principles and methods for personalizing newsfeeds via an analysis of information novelty and dynamics

• US 20050198056A1
• Filed: 04/20/2004
• Published: 09/08/2005
• Est. Priority Date: 03/02/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dumais, Susan T., Horvitz, Eric J., Gabrilovich, Evgeniy
• Granted Patent: US 7,293,019 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and methodology is provided for filtering temporal streams of information such as news stories by statistical measures of information novelty. Various techniques can be applied to custom tailor news feeds or other types of information based on information that a user has already reviewed. Methods for analyzing information novelty are provided along with a system that personalizes and filters information for users by identifying the novelty of stories in the context of stories they have already reviewed. The system employs novelty-analysis algorithms that represent articles as a bag of words and named entities. The algorithms analyze inter- and intra-document dynamics by considering how information evolves over time from article to article, as well as within individual articles.

Claims

1. A system for distributing personalized information, comprising:

a comparator that determines differences between two or more information items; and

an analyzer that automatically determines a subset of the information items as personalized information based in part on the differences and as data relating to the information items evolves over time.

2. The system of claim 1, further comprising a filter to discard previously observed information.

3. The system of claim 1, the information items relate to a news stream.

4. The system of claim 1, further comprising at least one server to collect the information items for further processing by the analyzer.

5. The system of claim 1, the comparator processes detailed statistics gathered on word occurrence across sets of documents in order to characterize differences and similarities among the sets.

6. The system of claim 1, further comprising a word model that employs named entities that denote people, organizations, or geographical locations.

7. The system of claim 1, further comprising a personalized news portal or news alerting service that seeks to minimize the time and disruptions to users.

8. The system of claim 1, further comprising a framework for determining differences in a variety of applications, including automatic profiling and comparison of text collections, automatic identification of different views, scopes and interests reflected in the texts, or automatic identification of novel information.

9. The system of claim 1, the comparator determines at least one of a difference in content, a difference in structural organization, and a difference in time.

10. The system of claim 9, further comprising a component for characterizing novelty in news stories and allowing ordering of news articles so that each article adds maximum information to a union of previously read articles.

11. The system of claim 9, for comprising a component for analyzing topic evolution over time to enable quantifying importance and relevance of news updates.

12. The system of claim 11, further comprising providing user controls for topic parameters in order provide a personalized news experience.

13. A computer readable medium having computer readable instructions stored thereon for implementing the components of claim 1.

14. A method for creating personalized information, comprising:

automatically analyzing documents from different information sources;

automatically determining novelty of the documents; and

creating a personalized feed of information based on the novelty of the documents.

15. The method of claim 14, further comprising inferring differences between document groups by building a model for each group, and then comparing the models using a similarity metric.

16. The method of claim 15, the models employ smoothed probability distributions over word features or as vectors of weights in the same feature space.

17. The method of claim 15, the similarity metric further comprising at least one of a KL divergence, a JS divergence, a cosine of vectors computation, a cosine of vectors of feature weights, and a measure of density of previously unseen named entities.

18. The method of claim 17, further comprising providing a novelty ranking algorithm that is applied iteratively to produce a small set of articles that a reader is potentially interested in.

19. The method of claim 18, further comprising at least one of providing a greedy incremental analysis and comparing substantially available updates to a seed story that a user has read, selecting the article least similar to the seed story.

20. The method of claim 19, further comprising the following algorithm:

Algorithm RANKNEWSBYNOVELTY (dist, seed, D, n)

R←

seed//initialization

for i=1 to min(n, |D|) do

d←

argmax_di ε

D {dist(d_i,R)}

R←

R∪

{d};

D←

D\{d}

where dist is a distance metric, seed—

is a seed story, D—

a set of relevant updates, n—

a desired number of updates to select, R—

list of articles ordered by novelty.

21. The method of claim 19, further comprising providing a general analysis of benefits versus the costs of alerting users to balance the informational value of particular articles or groups of articles with the cost of interrupting users, based on a consideration of the user'"'"'s context.

22. The method of claim 19, further comprising comparing articles received in one period with a union of articles received periodically.

23. The method of claim 22, further comprising determining distance metrics that consider previous articles relevant to a topic but decay the metrics weight with age.

24. The method of claim 19, further comprising the following algorithm:

Algorithm PICKDAILYUPDATE (dist, Bg, D, thresh)

d←

arg max_di ε

D{dist(d_i,Bg)}

if dist(d, Bg)>

thresh then display(d)

Bg←

D

where dist is a distance metric, Bg—

a background reference set including a union of relevant articles received on a preceding day, D—

a set of new articles received today, thresh—

user-defined sensitivity threshold.

25. The method of claim 19, further comprising determining a burst of novelty.

26. The method of claim 25, further comprising determining a median filter of width w that sorts w data points within a window centered on the current point.

27. The method of claim 26, further comprising the following algorithm:

$\mathrm{Algorithm}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{IDENTIFYBREAKINGNEWS}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{dist};<br><br>D;<br><br>l;<br><br>\mathrm{fw};<br><br>\mathrm{thresh}\right)$ $\mathrm{Window}\leftarrow <br><br>{\bigcup <br><br>}_{i=1}^l<br><br>d_i\in <br><br>D$ $\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>i=l+1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>D<br><br><br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{do}$ $\text{\hspace{1em}<br><br>}<br><br>{\mathrm{Scores}}_i\leftarrow <br><br>\mathrm{dist}<br><br>\left(d_i,\mathrm{Window}\right)$ $\text{\hspace{1em}<br><br>}<br><br>\mathrm{Window}\leftarrow <br><br>\left(\mathrm{Window}<br><br>\backslash <br><br>d_{i-l}\right)\bigcup <br><br>d_i$ ${\mathrm{Scores}}^{\mathrm{filt}}\leftarrow <br><br>\mathrm{MedianFilter}<br><br>\left(\mathrm{Scores},\mathrm{fw}\right)$ $\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>j=1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>{\mathrm{Scores}}^{\mathrm{filt}}<br><br><br><br>\mathrm{do}$ $\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{Scores}}_j^{\mathrm{filt}}><br><br>\mathrm{thresh}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{then}$ $\text{\hspace{1em}<br><br>}<br><br>\mathrm{display}<br><br>\left(d_{j+l}\right)$ $\text{\hspace{1em}<br><br>}<br><br>\mathrm{skip}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{beginning}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{next}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{burst}$

where dist is a distance metric, D—

a sequence of relevant articles, l—

sliding window length, fw—

median filter width, thresh—

user-defined sensitivity threshold.

28. The method of claim 19, further comprising determining at least one of recap articles, elaboration articles, offshoot articles, and irrelevant articles.

29. A method for performing a document analysis, comprising:

constructing a language model for each document in a set of documents;

determining a fixed distance metric to analyze the documents; and

sliding at least one window over words in the documents.

30. The method of claim 29, further comprising plotting distance scores of the window versus a seed story.

31. The method of claim 30, further comprising determining a sum of point-wise scores of each word vs. the seed story as stipulated by comparing the language model of a current document with that of the seed story using a selected metric.

32. The method of claim 31, further comprising employing a window length parameter of about 20.

33. The method of claim 29, further comprising assisting a design of ideal reading sequences or paths through currently unread news stories on a topic, within different time-horizons of recency from present time.

34. The method of claim 29, further comprising designing sequences for catching up on news, considering the most recent news as well as news bursts over time, to help people understand the evolution of news story and navigate the history of stories by major events or updates.

35. The method of claim 29, further comprising developing different types of display designs and metaphors.

36. The method of claim 35, the types include use of a time-line view or clusters in time.

37. The method of claim 29, further comprising providing ideal alerting in a desktop and or mobile setting of breaking news stories within a topic.

38. The method of claim 37, further comprising allowing users to specify topics, or key words and alerting the user when there is enough novelty given what the user has read.

39. The method of claim 37, further comprising alerting a user when a news story appears with keywords if the information novelty is above a predetermined threshold of novelty.

40. A system for creating personalized information, comprising:

means for analyzing a plurality of documents from different information sources;

means for determining a similarity of the documents; and

means for providing a personalized feed of information based on determined differences in similarity of the documents.