Systems and methods for guiding allocation of computational resources in automated perceptual systems

• US 7,873,724 B2
• Filed: 12/05/2003
• Issued: 01/18/2011
• Est. Priority Date: 12/05/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Oliver, Nuria M., Horvitz, Eric J.
• Primary Examiner(s): BATES, KEVIN T
• Application Number:
  US10/729,464
• Publication Number:
  US 20050132378A1
• Time in Patent Office: 2,601 Days
• Field of Search: 709226-228, 700/90, 700/241, 701/1, 704/249, 705/1, 707 1- 10, 707100-101, 713/100, 713/300, 715/738, 370/252, 370/352, 370/392, 379/219, 382/232, 398/30, 424/641, 435/6, 463/42, 706/14, 706/15
• US Class Current: 709/224
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

The present invention leverages analysis methods, such as expected value of information techniques, rate-based techniques, and random selection technique, to provide a fusion of low-level streams of input data (e.g., raw data) from multiple sources to facilitate in inferring human-centric notions of context while reducing computational resource burdens. In one instance of the present invention, the method utilizes real-time computations of expected value of information in a greedy, one-step look ahead approach to compute a next best set of observations to make at each step, producing “EVI based-perception.” By utilizing dynamically determined input data, the present invention provides utility-directed information gathering to enable a significant reduction in system resources. Thus, of the possible input combinations, the EVI-based system can automatically determine which sources are required for real-time computation relating to a particular context.

Claims

1. An analysis system, comprising:

a plurality of sensors configured to collect perception evidence;

a computer system comprising a perception system that, when executed, consumes computing resources of the computing system, the perception system comprising;

a control component that selectively gathers from the plurality of sensors the perception evidence, the perception evidence being gathered at times selected to limit utilization of the computing resources of the computer system by the perception system; and

an analysis component that utilizes an analysis policy to analyze the perception evidence to determine a context of a user of the computer system,

wherein;

the control component uses information from the analysis component regarding at least one feature about which to collect data to select the times at which to gather perception evidence from one or more of the plurality of sensors;

the analysis component generates the information based on a value of the at least one feature for determining the context;

the analysis policy comprises at least one selected from the group consisting of;

a random selection perception policy that randomly selects which features to utilize on a frame by frame basis, a rate-based perception policy that defines observational frequencies and duty cycles for at least one feature or an EVI-based perception policy that determines an expected value of information via a cost-benefit analysis means utilizing at least expected values and cost of analysis values for at least one feature, the cost of analysis values comprising at least one value proportional to an impact to the computing resources employed by the perception system.

2. The system of claim 1, the analysis component employing, at least in part, learned inferences relating to persistence versus volatility of observational states to account for unobserved data.

3. The system of claim 2, the learned inferences based, at least in part, on a probability distribution over future states based on at least one previously observed value that is captured by at least one function of time.

4. The system of claim 3, the probability distribution comprising a Gaussian distribution:

5. The system of claim 1, the control component employing a criticality level of at least one user task to limit utilization of computing resources by the perception system.

6. The system of claim 1, the control component limiting utilization of computing resources based upon context.

7. The system of claim 1, the control component limiting utilization of computing resources by controlling what analysis policy is employed.

8. The system of claim 7, the selection of the analysis policy based on context information.

9. The system of claim 1, further comprising at least one perception sensor to provide the perception evidence for the perception system.

10. The system of claim 9, the control component limiting utilization of computing resources by facilitating control of at least one selected from the group consisting of an analysis process for at least one perception sensor and a focus of attention of at least one perception sensor.

11. The system of claim 9, the control component limiting utilization of computing resources by controlling what perception sensors are employed.

12. The system of claim 9, the perception sensor comprising at least one selected from the group consisting of a video camera, an audio microphone, a keyboard keystroke sensor, a mouse utilization sensor, and a motion detector.

13. The system of claim 9, the perception sensor comprising a detector for at least one state of at least one selected from the group consisting of at least one data structure within a computing system and at least one application activity within a computing system.

14. The system of claim 1, further comprising a user interface component that interfaces with at least one user to relay information relating to user perception preferences to the perception system.

15. The system of claim 14, the control component employing at least one user perception preference to limit utilization of computing resources by the perception system.

16. The system of claim 14, the user perception preferences comprising values of cost for utilizing computing resources.

17. The system of claim 1, the perception evidence analysis operations comprising analysis policy selection control operations between the control component and the analysis component.

18. The system of claim 1, the perception evidence analysis operations comprising perception evidence related information exchanges between the control component and the analysis component.

19. The analysis system of claim 1 utilized to design an analysis policy of at least one perception system and its perception sensors.

20. The analysis system of claim 1 utilized to determine at least one value of adding at least one sensor to at least one perception system.

21. The analysis system of claim 1 utilized to provide information relating to volatility of data due to influences of a flow of time.

22. The analysis system of claim 1 utilized to determine at least one time-based economic value of a business given its environmental context.

23. The system of claim 1, the analysis policy comprising a context-based analysis policy.

24. The system of claim 1, the analysis policy comprising a random selection perception policy that randomly selects which features to utilize on a frame by frame basis.

25. The system of claim 1, the analysis policy comprising a rate-based perception policy that defines observational frequencies and duty cycles for at least one feature.

26. The system of claim 25, the rate-based perception policy utilizing off-time that is determined by cross-validation means on a real-time data validation set to determine time for computations.

27. The system of claim 1, the analysis policy comprising an EVI-based perception policy that determines an expected value of information via a cost-benefit analysis means utilizing at least expected values and cost of analysis values for at least one feature.

28. The system of claim 27, the cost of analysis values comprising at least one value proportional to an impact to the computing resources employed by the perception system.

29. The system of claim 27, the EVI-based perception policy employing a context-based cost model to determine the cost of analysis values.

30. The system of claim 27, the EVI-based perception policy employing real-time computations of expected value of information.

31. The system of claim 30, the real-time computations processed utilizing a myopic, single step approach for computing a next best set of observations.

32. The system of claim 27, the cost of analysis values comprising at least one selected from the group consisting of dollar values, percentage of CPU utilization values, latency values, and user selected preference values.

33. The system of claim 27, the cost-benefit analysis means utilizing substantially similar value types for a cost value and a benefit value to calculate the expected value of information.

34. The system of claim 27, the cost-benefit analysis means further comprising at least one utility model that facilitates in analyzing a benefit of determining a value of at least one feature.

35. The system of claim 34, the utility model comprising a conditional utility model that alters functionality dependent upon context.

36. The system of claim 27, the EVI-based perception policy further comprising a probabilistic model.

37. The system of claim 36, the probabilistic model comprising a Hidden Markov Model (HMM) model.

38. The system of claim 37, the expected value of information determined, at least in part, via Equation (4):

39. The system of claim 37, the expected value of information determined, at least in part, via discretized Equation (5):

40. The system of claim 36, the probabilistic model comprising a Layered Hidden Markov Model (LHMM) model.

41. The system of claim 40, the Layered Hidden Markov Model (LHMM) utilized to substantially reduce re-training of higher level layers when an operating environment change occurs.

42. A non-transitory computer readable medium having stored thereon computer executable components of the system of claim 1.

80. A device employing the system of claim 1 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.

43. An analysis system comprising at least one processor, the analysis system comprising

a control component that selectively gathers perception evidence to limit utilization of computing resources by a perception system;

and

an analysis component that utilizes an analysis policy to analyze, with the at least one processor, the perception evidence obtained for employment in the perception system;

wherein

the analysis component is interactive with the control component for perception evidence analysis operations,

the analysis policy comprises an EVI-based perception policy that determines an expected value of information via a cost-benefit analysis means utilizing at least expected values and cost of analysis values for at least one feature,

the cost-benefit analysis means comprise at least one utility model that facilitates in analyzing a benefit of determining a value of the at least one feature,

the utility model comprises a conditional utility model that alters functionality dependent upon context, and

the expected value of information is determined, at least in part, via utilization of Equation (2);

44. A method of analyzing data, comprising:

with the at least one processor;

obtaining perception evidence for a perception system from a plurality of sensors;

determining a context from the perception evidence;

analyzing the perception evidence utilizing an analysis policy to determine a perceived system value indicating a value of utilization of computing resources of a computer system by the perception system; and

employing the perceived system value to limit utilization of the computing resources by determining at least one sensor from the plurality of sensors to obtain the perception evidence and a time at which to obtain the perception evidence by the at least one sensor, wherein the time is selected based on an intensity of interaction of a user with the computer system.

45. The method of claim 44, wherein analyzing the perception evidence further comprises:

employing, at least in part, learned inferences relating to persistence versus volatility of observational states to provide unobserved perception evidence in lieu of observed perception evidence.

46. The method of claim 45, wherein the learned inferences are based, at least in part, on a probability distribution model for future states based on at least one previously observed value that is captured by at least one function of time.

47. The method of claim 46, wherein the probability distribution model comprises, at least in part, a Gaussian distribution:

48. The method of claim 44, further comprising:

accepting user input to obtain user preferences to establish criteria for limiting utilization of the computing resources by the perception system.

49. The method of claim 48, wherein the criteria comprises at least one critical task that supersedes analysis of the perception evidence for the at least one feature in the context.

50. The method of claim 44, further comprising:

extracting the perception evidence pertaining to at least one feature from the at least one sensor.

51. The method of claim 50, further comprising:

selecting when the at least one sensor is employed to obtain the perception evidence to further optimize the limiting of the computing resources employed by the perception system.

52. The method of claim 50, wherein the at least one sensor obtains perception evidence for at least one feature.

53. The method of claim 44, further comprising:

selecting the analysis policy based on optimization of limiting the computing resources for the context.

54. The method of claim 44, further comprising:

selecting the analysis policy based on optimization of limiting the computing resources for obtaining a desired feature.

55. The method of claim 44, wherein employing the perceived system value comprises utilizing the computing resources when the perceived system value is above a threshold.

56. The method of claim 55, the threshold is a predetermined threshold.

57. The method of claim 56, the predetermined threshold is set via a user preference.

58. The method of claim 56, the predetermined threshold is set via the perception system based on context.

59. The method of claim 44, wherein employing the perceived system value comprises utilizing the computing resources for a feature combination that yields a maximal perceived system value.

60. The method of claim 44, the analysis policy comprising a rate-based perception policy.

61. The method of claim 60, further comprising:

defining observational frequencies and duty cycles via a cross-validation means on a real-time data validation set for perception sensors employed by the perception system; and

determining which perception sensors are providing sensed data and utilizing the sensed data to compute features facilitated by the sensed data.

62. The method of claim 61, further comprising:

adapting the observational frequencies and duty cycles for at least one sensor dynamically.

63. The method of claim 44, the analysis policy comprising a random selection-based perception policy.

64. The method of claim 63, further comprising:

determining features available based on available perception sensors employed by the perception system;

randomly selecting which features to analyze; and

processing at least one analyzed feature to determine output perception data.

65. The method of claim 44, the analysis policy comprising an EVI-based perception policy.

66. The method of claim 65, further comprising:

calculating a benefit value for determining a feature;

calculating a cost value for determining the feature; and

utilizing the EVI-based perception policy to derive a cost-benefit analysis value of the feature;

the cost benefit analysis utilizing a benefit value and a cost value.

67. The method of claim 66, the benefit value and the cost value calculated employing a substantially similar value type.

68. The method of claim 67, the value type comprising at least one selected from the group consisting of a dollar value, a percentage of CPU utilization value, a latency value, and a user-selected value.

69. The method of claim 65, the EVI-based perception policy further comprising at least one selected from the group consisting of a utility model and a probabilistic model.

70. The method of claim 69, further comprising:

evaluating an expected value of information (EVI) utilizing, at least in part, employment of Equation (2);

71. The method of claim 69, the probabilistic model comprising a Hidden Markov Model (HMM).

72. The method of claim 71, further comprising:

evaluating an expected value of information (EVI) utilizing, at least in part, employment of Equation (4);

73. The method of claim 71, further comprising:

evaluating an expected value of information (EVI) utilizing, at least in part, employment of discretized Equation (5);

74. The method of claim 69, the probabilistic model comprising a Layered Hidden Markov Model (LHMM).

75. The method of claim 74, further comprising:

employing lower level layers of the LHMM to mask higher level layers from needing to be re-trained when the perception system is changed to a new environment.

76. A perception evaluation system utilizing the method of claim 44 to determine benefits of additional perception sensors to a perception system.

77. A perception design system utilizing the method of claim 44 to design a perception system to optimally limit utilization of computing resources.

78. A perception response system employing the method of claim 44 to provide information utilizing knowledge of volatility of data due to influences of a flow of time to re-determine perceptions at appropriate intervals.

79. A device employing the method of claim 44 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.

81. A data analysis system, comprising:

a plurality of sensors to collect a plurality of features as perception evidence;

control means to limit utilization of computing resources of a computer system by a perception system by controlling the plurality of sensors to selectively gather the perception evidence obtained via the perception system; and

analyzing means to;

analyze the perception evidence utilizing an analysis policy to determine context of use of the computer system by one or more users in which the perception system is operating, and

guide the control means to limit the utilization of the computing resources by determining which features from the plurality of features to collect as the perception evidence depending on a value of the features for limiting the utilization of the computing resources by the perception system, based on the determined context;

wherein

the control means selects at least one sensor from the plurality of sensors to collect the features.

82. A data analysis system, comprising:

a first component of a perception system that receives a data query relating to data to determine a context in which the perception system is operating so that to limit utilization of computing resources of a computer system by the perception system, wherein the data comprises perception evidence pertaining to at least one feature collected by a plurality of sensors; and

a second component that;

analyzes, with the at least one processor, volatility versus persistence of observations of at least one state of the data over time to establish reasonableness in timing of at least one reply to the query, and

selects at least one sensor from the plurality of sensors to collect the perception evidence pertaining to the at least one feature to limit the utilization of the computing resources based on a value of the at least one feature in the context, wherein

selection of the at least one feature depends on an intensity of interaction of a user with the computer system.