Method and apparatus for generating an inference about a destination of a trip using a combination of open-world modeling and closed world modeling

• US 7,991,718 B2
• Filed: 06/28/2007
• Issued: 08/02/2011
• Est. Priority Date: 06/28/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Subramani, Murugesan S., Horvitz, Eric J., Krumm, John C.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US11/770,541
• Publication Number:
  US 20090006297A1
• Time in Patent Office: 1,496 Days
• Field of Search: 706/20, 706/12, 706/21, 706 45- 48, 706/62, 4554561-457, 342/147, 342/450, 342/451, 340988-989, 340/995.19, 340/995.25, 701 23- 37, 701200-226
• US Class Current: 706/21
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

The claimed subject matter provides systems and/or methods that facilitate generating an inference about events that may not have yet been observed. Open-world modeling can be used to take a history of observation so as to understand trends over time in the revelation of previously unseen events, and to make inferences with subsets of data that new unseen events will be seen. Thus, inaccuracies associated with predictions generated from incomplete data sets can be mitigated. To yield such predictions, open-world submodels and closed-world submodels that do not allow for previously unseen events can be combined via a model mixture methodology, which fuses inferences from the open- and close-world models.

Claims

1. A system that facilitates generating an inference about a destination of a current trip, comprising:

a component that makes a log of information about trips, the log comprising previously observed locations that were destinations of the trips; and

a modeling component, comprising at least one processor, that generates predictions of a destination of the current trip based at least in part upon a combination, the combination being a combination of outputs of;

an open-world submodeling component that provides probabilities, based on the log of locations, that locations that are not in the log are the destination of the current trip; and

a closed-world submodeling component that provides probabilities that locations in the log are the destination of the current trip, the closed-world submodeling component inferring the probabilities based on information in the log that indicates probabilities that previously observed locations will recur as a destination of a trip,

wherein the modeling component generates a prediction of the destination of the current trip by combining, for each of a plurality of locations, a probability provided by the open-world submodeling component and a probability provided by the closed-world submodeling component.

2. The system of claim 1, the open-world submodeling component reasons about a likelihood of seeing previously unobserved states given a specific observational context.

3. The system of claim 1, the modeling component effectuates open-world decomposition by using the open-world model and the closed-world model to generate the predictions.

4. The system of claim 1, wherein:

the open-world submodeling component generates probabilities that locations that are not in the log are the destination of a trip based on demographics or driving dynamics of a user.

5. The system of claim 1, wherein the open-world submodeling component models the probabilities related to the locations that are not in the log based upon a spatial distribution.

6. The system of claim 5, the open-world submodeling component models the spatial distribution as a probability distribution over a distance from previously observed destination of a trip.

7. The system of claim 1, wherein the modeling component further comprising a weighting component that combines the probability provided by the open-world submodeling component and the probability provided by the closed-world submodeling component.

8. The system of claim 7, the weighting component fuses a weighted combination of probabilities provided by the open-world submodeling component and the closed-world submodeling component as a function of duration of data collection.

9. The system of claim 8, the weighting component employs curve fitting to model a change in the likelihood that a user will visit a new location over time.

10. The system of claim 7, further comprising a profile component that generates a weight utilized by the weighting component based upon a consideration of user related characteristics.

11. The system of claim 1, further comprising a content component that provides relevant information associated with the generated predictions.

20. The system of claim 1, wherein the predicted events comprise predicted destinations of trips and the events that have been previously observed are trips for which the destination has been observed.

12. A method that facilitates handling incompleteness of data sets to enable generating a prediction, comprising:

with at least one processor;

receiving observed data relating to operation of a vehicle;

computing, based on the observed data, probabilities of previously observed events recurring; and

extrapolating the observed data to yield probabilities related to non-observed events; and

generating a prediction of an event based at least in part upon a combination, the combination being a combination of the probabilities related to the non-observed events and the previously observed events,

wherein;

the probabilities are weighted in forming the combination by a dynamic factor to place greater emphasis on probabilities related to the previously observed events when the amount of received data increases; and

the previously observed events constitute previously taken trips that have been logged.

13. The method of claim 12, extrapolating the observed data further comprises performing trend analysis to characterize how observational data changes given ongoing data collection.

14. The method of claim 12, the method further comprises:

generating a closed-world submodel based upon the observed data, the closed-world submodel being used to generate the probabilities of previously observed events recurring;

generating an open-world submodel by evaluating a likelihood of observing the non-observed data over a future period of time, the open-world submodel being used to generate the probabilities of previously non-observed events occurring; and

combining outputs of the closed-world submodel and the open-world submodel based upon a weight to yield the prediction.

15. The method of claim 14, the weight varies dynamically with a length of observation.

16. The method of claim 14, combining the closed-world submodel and the open-world submodel further comprising:

determining characteristics of a user;

identifying a subgroup to which the user belongs based upon the characteristics;

forecasting a trajectory of a submodel weight that varies as a function of observation time based upon the identified subgroup; and

combining the closed-world submodel and the open-world submodel by utilizing the forecasted submodel weight.

17. The method of claim 14, generating the open-world submodel further comprising distributing probabilities associated with non-observed data based upon an analysis of spatial trends.

18. The method of claim 12, further comprising presenting relevant content based upon the prediction.

19. A system that facilitates generating a prediction, comprising:

at least one processor programmed to provide;

means for generating a closed-world inference based upon observed data, the closed world inference indicating a probability of recurrence of at least one event that has previously been observed, wherein the observed data relates to operation of a vehicle and the event that has previously been observed is a previous trip that has been logged;

means, comprising at least one processor, for generating an open-world inference by evaluating a probability of observing previously non-observed data over a future period of time; and

means for combining the closed-world inference and the open-world inference based upon a weight to yield the prediction, the weight being based on an amount of observed data.