Precomputation of context-sensitive policies for automated inquiry and action under uncertainty

• US 7,428,521 B2
• Filed: 06/29/2005
• Issued: 09/23/2008
• Est. Priority Date: 06/29/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Sarin, Raman K., Koch, Paul B.
• Primary Examiner(s): Holmes; Michael B.
• Application Number:
  US11/172,016
• Publication Number:
  US 20070022075A1
• Time in Patent Office: 1,182 Days
• Field of Search: 706/52
• US Class Current: 706/52
• CPC Class Codes: G06F 8/35 model driven
• CPC Class Codes: G06F 8/36 Software reuse
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Learning, inference, and decision making with probabilistic user models, including considerations of preferences about outcomes under uncertainty, may be infeasible on portable devices. The subject invention provides systems and methods for pre-computing and storing policies based on offline preference assessment, learning, and reasoning about ideal actions and interactions, given a consideration of uncertainties, preferences, and/or future states of the world. Actions include ideal real-time inquiries about a state, using pre-computed value-of-information analyses. In one specific example, such pre-computation can be applied to automatically generate and distribute call-handling policies for cell phones. The methods can employ learning of Bayesian network user models for predicting whether users will attend meetings on their calendar and the cost of being interrupted by incoming calls should a meeting be attended.

Claims

1. A distributed model processing system, comprising:

a policy component that includes decision-making instructions that are derived from logical rules and/or probabilistic user models developed in an offline computing environment, the probabilistic user models are associated with a model of interruptibility or a model of attendance; and

a mobile device that caches the decision-making instructions to facilitate functional operations on the device.

2. The system of claim 1, where value-of-information computations are used to compute and cache policies that describe if and when to make real-time inquiries to users or if and when to access information from sensors to resolve uncertainties.

3. The system of claim 1, where policies are used in a mobile phone to make decisions about call handling, including one or more of, whether to send a call silently to a voicemail system, ring or vibrate with a particular chime and intensity, display information visually, play a particular outgoing message, let a caller know when a user will next be available, allow the caller to indicate a desire to ring through to the user after hearing an outgoing message describing aspects of the user'"'"'s current context, or allow the caller to reschedule the call to another available time.

4. The system of claim 1, the probabilistic user models are associated with at least one user interface to train the models.

5. The system of claim 1, further comprising policies that allow for sensing of local state or state changes with one or more of a microphone, photocell, camera, accelerometer, thermometer, barometer, GPS device, or wireless radio signals, where the wireless signals include GSM strengths, which are embedded in a device or connected to a device via wire or wireless connection.

6. The system of claim 1, the probabilistic user models are trained from explicit or implicit user input.

7. The system of claim 1, the probabilistic user models are associated with at least one Bayesian network model or graphical model.

8. The system of claim 1, the probabilistic user models are associated with a cost/benefit analysis, where policies are created in accordance with a goal of maximizing expected value or minimizing expected cost based upon a consideration of a likelihood of different future situations.

9. The system of claim 1, the probabilistic user models are associated with an expected cost of interruption (ECI) computation.

10. The system of claim 9, the ECI computation includes the following equation:

$\mathrm{ECI}=p<br><br>\left(A<br><br>\text{❘<br><br>}<br><br>E\right)<br><br>\underset{i}{\sum <br><br>}<br><br>p<br><br>\left(c_i<br><br>\text{❘<br><br>}<br><br>E\right)<br><br>c_i+\left(1-p<br><br>\left(A<br><br>\text{❘<br><br>}<br><br>E\right)\right)<br><br>c^b<br><br>\left(S\right);<br><br>$

where p(A|E) is a likelihood that users will attend a meeting, given evidential properties E associated with the meeting obtained via calendar appointment properties, p(c_i |E) is a probability that users assign a cost c_i to the meeting, where i indexes the meeting as being low, medium, or high cost, and c^b(S) is a background cost of being interrupted in a context S, representing where a user does not attend a meeting, as captured by a time of day and day of week.

11. A computer readable medium having computer readable instructions stored thereon for implementing the policy component of claim 1.

12. A method for distributing model policies system, comprising:

automatically compiling decision model outputs into a file that includes one or more policies;

extending the policies to include pre-computed dialog queries to resolve decision-making uncertainties;

loading the policies on a remote device to extend functional capabilities of the remote device; and

employing the remote device to automatically schedule user activities.

13. The method of claim 12, further comprising analyzing a call log to determine the decision model.

14. The method of claim 12, further comprising generating an interface to train the user model.

15. The method of claim 12, further comprising employing a client component on the remote device to interact with a desktop computing application.

16. The method of claim 12, further comprising determining at least one of an expected cost of communications (ECC) and an expected value of information (EVI) to determine the dialog queries.

17. The method of claim 16, further comprising determining the following equation where the ECC for a meeting of duration τ

based on a consideration of current evidence E with respect to properties of an upcoming meeting is,

$\mathrm{ECC}<br><br>\left(E,t\right)=\left(\underset{i}{\sum <br><br>}<br><br>f_i<br><br>c_i^{\mathrm{defer}}+\underset{j}{\sum <br><br>}<br><br>f_j<br><br>c_j^{\mathrm{ring}}\right)<br><br>t$

and where f_i is a frequency of calls in each caller group i that has a cost of deferral lower than a cost of interruption, f_j is a frequency of calls in each caller group j that has a cost of deferral higher than the cost of interruption, and c^defer and c^ring are the costs of deferral and cost of interruption of respective caller classes.

18. A system to facilitate mobile device operations, comprising:

means for learning user models in an offline computing environment;

means for encoding output from the user model according to one or more control policies; and

means for executing the control policies in at least a second computing environment apart from the offline computing environment.