LOCALIZED ANOMALY DETECTION USING CONTEXTUAL SIGNALS

• US 20170076217A1
• Filed: 09/16/2015
• Published: 03/16/2017
• Est. Priority Date: 09/16/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wolk, Jessica Kristan, Krumm, John Charles, Horvitz, Eric Joel
• Granted Patent: US 10,614,364 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

An expected value of a measurement in a first context may be inferred based at least partly on a contextual signal. The contextual signal may comprise an actual value that is: (i) of a same type as the expected value, and (ii) associated with a second context that is different from the first context (e.g., the contexts can comprise geographical areas), or the contextual signal may comprise an actual value that is: (i) of a different type than a type of the expected value, and (ii) associated with the first context, or a second context that is different from the first context. If a difference between the expected value and an actual value of the first context is greater than a threshold difference, this condition is considered an anomaly. A detected anomaly may be used to determine an event that may be significant or otherwise of interest to a user community.

Claims

1. A computer-implemented method comprising:

inferring an expected value for a first context based at least in part on a first actual value that is;

(i) of a same type as the expected value, and (ii) associated with a second context that is different from the first context;

determining a prediction error by comparing the expected value to a second actual value that is;

(i) of the same type as the expected value, and (ii) associated with the first context; and

determining that an anomaly has occurred in the first context based at least in part on the prediction error.

2. The computer-implemented method of claim 1, further comprising training a machine-learned inference function to infer the expected value for the first context as a function of at least the first actual value, wherein inferring the expected value comprises utilizing the machine-learned inference function.

3. The computer-implemented method of claim 1, further comprising:

determining a standard deviation of the prediction error;

normalizing the prediction error by dividing the prediction error by the standard deviation to obtain a normalized prediction error; and

comparing the normalized prediction error to a predetermined threshold,

wherein determining that the anomaly has occurred in the first context comprises determining that the normalized prediction error exceeds the predetermined threshold.

4. The computer-implemented method of claim 1, wherein the first context comprises a first geographical area and the second context comprises a second geographical area that is within a predetermined distance from the first geographical area, the method further comprising determining an event in the first geographical area based at least in part on the anomaly.

5. The computer-implemented method of claim 4, further comprising:

designating the event as a candidate event; and

determining that the candidate event is a real event using a machine-learned binary classifier.

6. The computer-implemented method of claim 5, further comprising:

accessing a standing query associated with a user;

determining that attributes of the real event satisfy the standing query; and

transmitting a notification of the real event to a client device associated with the user.

7. The computer-implemented method of claim 5, further comprising:

creating a text summary of the real event; and

causing presentation of the text summary on a public display situated in a public space within the first geographical area.

8. The computer-implemented method of claim 1, wherein the first context comprises a first geographical area and the second context comprises a second geographical area, the method further comprising:

discretizing an initial geographical area into a plurality of geographical areas, the plurality of geographical areas including the first geographical area and the second geographical area;

for each geographical area of the plurality of geographical areas constructing a time series comprising a plurality of data points plotted over time, each data point representing an actual value of a measurement taken during a time interval; and

for the first geographical area, inferring a plurality of expected values, including the expected value, for each data point in the time series.

9. The computer-implemented method of claim 8, wherein the initial geographical area is discretized into a triangular tessellation such that each geographical area of the plurality of geographical areas is triangular, and the plurality of geographical areas are substantially uniform in size.

10. The computer-implemented method of claim 9, wherein discretizing the initial geographical area comprises creating a hierarchical triangular mesh (HTM) comprising multiple triangular tessellations at different levels of resolution, the method further comprising:

discretizing time by creating a hierarchy of time intervals at different durations, the hierarchy of time intervals including the time interval;

combining each time interval of the hierarchy of time intervals with each level of the different levels of resolution to create a plurality of spatio-temporal resolutions;

selecting the first geographical area at a spatio-temporal resolution of the plurality of spatio-temporal resolutions; and

for the first geographical area;

constructing a time series;

training a machine-learned inference function for detecting anomalies; and

determining that a qualifying condition is met by analyzing the time series to determine that actual values of the time series meet or exceed a threshold.

11. A computer-implemented method comprising:

inferring an expected value for a first context based at least in part on a first actual value that is;

(i) of a different type than a type of the expected value, and (ii) associated with the first context, or a second context that is different from the first context;

determining a prediction error by comparing the expected value to a second actual value that is;

(i) of a same type as the expected value, and (ii) associated with the first context; and

determining that an anomaly has occurred in the first context based at least in part on the prediction error.

12. The computer-implemented method of claim 11, further comprising training a machine-learned inference function to infer the expected value for the first context as a function of at least the first actual value, wherein inferring the expected value comprises utilizing the machine-learned inference function.

13. The computer-implemented method of claim 11, further comprising comparing the prediction error to a predetermined threshold,

wherein determining that the anomaly has occurred in the first context comprises determining that the prediction error exceeds the predetermined threshold.

14. The computer-implemented method of claim 11, wherein the first context comprises a first geographical area and the second context comprises a second geographical area that is adjacent to the first geographical area, the method further comprising determining an event in the first geographical area based at least in part on the anomaly.

15. The computer-implemented method of claim 14, further comprising:

designating the event as a candidate event; and

determining that the candidate event is a real event using a machine-learned binary classifier.

16. A system comprising:

memory;

one or more processors;

one or more modules stored in the memory and executable by the one or more processors to perform operations comprising;

inferring a time series of expected values for a first geographical area based at least in part on a first time series of actual values for a second geographical area;

determining a time series of prediction errors by comparing the time series of expected values to a second time series of actual values for the first geographical area; and

determining that an anomaly has occurred in the first geographical area based at least in part on the time series of prediction errors.

17. The system of claim 16, the operations further comprising, prior to inferring the time series of expected values:

segmenting an initial geographical area into a plurality of geographical areas, wherein the plurality of geographical areas includes the first geographical area and the second geographical area;

constructing the first time series of actual values for the second geographical area;

constructing the second time series of actual values for the first geographical area; and

selecting the first geographical area to analyze for the anomaly.

18. The system of claim 16, the operations further comprising training a machine-learned inference function to infer the time series of expected values for the first geographical area as a function of:

a time of day, a day of week, and at least the first time series of actual values, wherein inferring the time series of expected values comprises utilizing the machine-learned inference function.

19. The system of claim 16, the operations further comprising determining an event in the first geographical area based at least in part on the anomaly.

20. The system of claim 19, the operations further comprising:

designating the event as a candidate event; and

determining that the candidate event is a real event using a machine-learned binary classifier.