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

• US 7,613,670 B2
• Filed: 01/03/2008
• Issued: 11/03/2009
• 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/969,053
• Publication Number:
  US 20080162394A1
• Time in Patent Office: 670 Days
• Field of Search: 706/46
• US Class Current: 706/46
• 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 method to facilitate mobile device operations, comprising:

employing a processor to execute computer executable instructions stored on a computer readable storage medium to implement the following acts;

utilizing each of a training input and a user input to develop logical rules or probabilistic user models in an offline computing environment, the probabilistic user models are associated with a model of interruptibilitv or a model of attendance;

generating a policy component that includes decision-making instructions derived from at least one of the logical rules or probabilistic user models developed in the offline computing environment; and

transmitting the policy component to a mobile device.

2. The method of claim 1, further comprising providing policies associated with the policy component to facilitate making 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.

3. The method of claim 1, further comprising providing 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.

4. The method of claim 1, further comprising using at least one user interface to train the associated probabilistic user models.

5. The method of claim 1, further comprising communicating via a client component on the device to interact with a desktop computing application.

6. A computer implemented method for developing model policies system, comprising:

employing a processor to execute computer executable instructions stored on a computer readable storage medium to implement the following acts;

recording a set of appointment properties associated with a user'"'"'s electronic calendar;

utilizing the set of appointment properties associated with the user'"'"'s electronic calendar to develop logical rules or probabilistic user models in an offline computing environment;

developing a policy component that includes decision-making instructions that are derived from the logical rules or probabilistic user models; and

encoding the policy component for implementation onto a mobile device.

7. The method of claim 6, further comprising recording a set of appointment properties by crawling a user'"'"'s online calendar.

8. The method of claim 6, further comprising recording for each appointment, one or more of:

time of day of the appointment, day of week of the appointment, appointment duration, subject of the appointment, location of the appointment, organizer of the appointment, the response status of the user, whether the appointment is recurrent or not, whether the time is marked as busy or free on the user'"'"'s calendar, whether the user was required or optional, the number of invitees, the organizational relationships of the invitees to the user, and the role of the user.

9. The method of claim 6, wherein the probabilistic user models are associated with a model of interruptibility or a model of attendance.

10. The method of claim 6, further comprising using at least one user interface to train the models associated with the probabilistic user models.

11. The method of claim 6, further comprising training the probabilistic user models from explicit or implicit user input.

12. The method of claim 6, further comprising implementing at least one Bayesian network model or graphical model with the probabilistic user models.

13. The method of claim 6, further comprising executing a cost/benefit analysis associated with the probabilistic user models, where policies are created in accordance with a goal of maximizing expected value or minimizing an expected cost based upon a consideration of a likelihood of different future situations.

14. The method of claim 6, further comprising determining an expected cost of interruption (ECI) computation associated with the probabilistic user models.

15. The method of claim 14, further comprising determining the ECI computation using the following equation:

$\mathrm{ECI}=p<br><br>\left(A❘<br><br>E\right)<br><br>\underset{i}{\sum <br><br>}<br><br><br><br>p<br><br>\left(c_i❘<br><br>E\right)<br><br>c_i+\left(1-p<br><br>\left(A❘<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.

16. The method of claim 14, further comprising determining a default ECI value when a user is not attending an appointment.

17. The method of claim 6, further comprising determining an expected cost of deferral associated with the probabilistic user models based, at least in part on, organizational relationships and activities.

18. The method of claim 6, further comprising determining at least one of an expected cost of communications (ECC) and an expected value of information (EVI) to determine at least one dialog query.

19. The method of claim 18, further comprising executing the following equation where the ECC for a meeting of duration t based on a consideration of current evidence E with respect to properties of an upcoming meeting is,

$\mathrm{ECC}$

( E , t ) = ( ∑

i ⁢

⁢

f i ⁢

c i defer + ∑

j ⁢

⁢

f j ⁢

c j ring ) ⁢

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.

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

a processor;

a memory communicatively coupled to the processor and storing computer readable instructions for implementing the following components;

a learning component for learning user models in an offline computing environment, the user models learned by utilizing each of a training input and a user input in the offline computing environment, the user models are associated with a model of interruptibility or a model of attendance;

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

a transmission component for transmitting the control policies to a remote device, the control policies executable in an online computing environment at the remote device apart from the offline computing environment.