Systems and methods for detecting and coordinating changes in lexical items

• US 9,324,007 B2
• Filed: 08/30/2012
• Issued: 04/26/2016
• Est. Priority Date: 11/29/2008
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Wright, Jeremy, Abella, Allcia, Grothendieck, John
• Primary Examiner(s): Rifkin, Ben
• Application Number:
  US13/598,662
• Publication Number:
  US 20120323836A1
• Time in Patent Office: 1,335 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

Systems and methods for efficiently detecting and coordinating step changes, trends, cycles, and bursts affecting lexical items within data streams are provided. Data streams can be sourced from documents that can optionally be labeled with metadata. Changes can be grouped across lexical and/or metavalue vocabularies to summarize the changes that are synchronous in time. The methods described herein can be applied either retrospectively to a corpus of data or in a streaming mode.

Claims

1. A method for detecting and coordinating change events in a data stream comprising:

monitoring, by a processor, over time, a probability of occurrence of lexical items in a data stream comprising a plurality of lexical items and a metavalue associated therewith, according to a lexical occurrence model, to detect a plurality of change events in the data stream;

applying, by the processor, a significance test to the change events to determine if the change events are statistically significant;

applying, by the processor, an interestingness test to the change events to determine a measure of interest (I) indicating whether the change events are likely to be of interest to a user, the interestingness test defined using conditional mutual information between the lexical items (W) and the lexical occurrence model (M) given a time span (T) as provided by a relationship;

I(W;

M|T)=H(W|T)−

H(W|M,T)

where H represents conditional entropy; and

grouping the change events across the lexical items and the metavalue to summarize the change events that are synchronous in time, the grouping forming a set of grouped change events.

2. The method of claim 1, wherein the data stream comprises a text stream.

3. The method of claim 1, wherein the lexical items in the data stream comprise at least one of a single word, a symbol, a number, a date, a place, a named-entity, a URL, textual data, multimedia data, and a token.

4. The method of claim 1, wherein the metavalue associated with the lexical items includes at least one of external metadata and internal metadata.

5. The method of claim 1;

wherein the probability of occurrence of the lexical items in the data stream is monitored over time according to the lexical occurrence model to detect at least one of a step change, a trend, a cycle, and a burst in the data stream.

6. The method of claim 1, wherein the lexical occurrence model includes at least one of a piecewise-constant lexical occurrence model and a piecewise-linear lexical occurrence model.

7. The method of claim 1;

wherein the lexical occurrence model includes a periodic component to detect cyclic change events and a piecewise-linear component to detect acyclic change events.

8. A non-transitory computer readable storage medium comprising computer readable instructions that;

when executed by a processor, cause the processor to perform operations comprising;

monitoring, over time, a probability of occurrence of lexical items in a data stream comprising a plurality of lexical items and a metavalue associated therewith, according to a lexical occurrence model, to detect a plurality of change events in the data stream;

applying a significance test to the change events to determine if the change events are statistically significant;

applying an interestingness test to the change events to determine a measure of interest (I) indicating whether the change events are likely to be of interest to a user;

the interestingness test defined using conditional mutual information between the lexical items (W) and the lexical occurrence model (M) given a time span (T) as provided by a relationship;

I(W;

M|T)=H(W|T)−

H(W|M,T)

where H represents conditional entropy; and

grouping the change events across the lexical items and the metavalue to summarize the change events that are synchronous in time, the grouping forming a set of grouped change events.

9. The non-transitory computer readable storage medium of claim 8, wherein the data stream comprises a text stream.

10. The non-transitory computer readable storage medium of claim 8, wherein the lexical items in the data stream comprise at least one of a single word, a symbol, a number, a date, a place, a named-entities, a URL, textual data, multimedia data, and a token, and the metavalue associated therewith.

11. The non-transitory computer readable storage medium of claim 8, wherein the metavalue associated with the lexical items includes at least one of external metadata and internal metadata.

12. The non-transitory computer readable storage medium of claim 8, wherein the computer readable instructions for monitoring the probability of occurrence of the lexical items in the data stream over time cause the processor to detect at least one of a step change, a trend, a cycle, and a burst in the data stream.

13. The non-transitory computer readable storage medium of claim 8, wherein the lexical occurrence model includes at least one a piecewise-constant lexical occurrence model and a piecewise-linear lexical occurrence model.

14. The non-transitory computer readable storage medium of claim 8, wherein the lexical occurrence model includes a periodic component to detect cyclic change events and a piecewise-linear component to detect acyclic change events.

15. A system for detecting and coordinating change events in a data stream, comprising:

a processor;

a memory in communication with the processor, the memory having stored thereon instructions, executable by the processor to cause the processor to perform operations comprising;

monitoring, over time, a probability of occurrence of lexical items in a data stream comprising a plurality of lexical items and a metavalue associated therewith, according to a lexical occurrence model, to detect a plurality of change events in the data stream;

applying a significance test to the change events to determine if the change events are statistically significant;

applying an interestingness test to the change events to determine a measure of interest (I) indicating whether the change events are likely to be of interest to a user, the interestingness test defined using conditional mutual information between the lexical items (W) and the lexical occurrence model (M) given a time span (T) as provided by a relationship;

I(W;

M|T)=H(W|T)−

H(W|M,T)

where H represents conditional entropy; and

grouping the change events across the lexical items and the metavalue to summarize the change events that are synchronous in time, the grouping forming a set of grouped change events.

16. The system of claim 15, wherein the data stream comprises a text stream, and the lexical items comprise at least one of a single word, a symbol, a number, a date, a place, a named-entities, a URL, textual data, multimedia data, and a token.

17. The system of claim 15, wherein the metavalue comprises at least one of external metadata and internal metadata.

18. The system of claim 15, wherein the instructions for monitoring the probability of occurrence of the lexical items in the data stream over time cause the processor to detect at least one of a step change, a trend, a cycle, and a burst in the data stream.

19. The system of claim 15, wherein the lexical occurrence model includes at least one of a piecewise-constant lexical occurrence model and a piecewise-linear lexical occurrence model.

20. The system of claim 15, wherein the lexical occurrence model includes a periodic component to detect cyclic change events and a piecewise-linear component to detect acyclic change events.