Layered models for context awareness

• US 7,203,635 B2
• Filed: 06/27/2002
• Issued: 04/10/2007
• Est. Priority Date: 06/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Oliver, Nuria M., Garg, Ashutosh, Horvitz, Eric J.
• Primary Examiner(s): Shah; Kamini
• Assistant Examiner(s): Gebresilassie; Kibrom K.
• Application Number:
  US10/183,774
• Publication Number:
  US 20040002838A1
• Time in Patent Office: 1,748 Days
• Field of Search: 703/2, 703/22, 716/16, 716/20, 715/708, 715/713, 715/861, 706/20, 706/21, 706/22, 345/156, 345/158
• US Class Current: 703/22
• CPC Class Codes: G06F 18/256 of results relating to different input data, e.g. multimodal recognition
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing
• CPC Class Codes: G10L 25/00 Speech or voice analysis techniques not restricted to a single one of groups G10L15/00 - G10L21/00 muting semiconductor-based amplifiers when some special characteristics of a signal are sensed by a speech detector, e.g. sensing when no signal is present, H03G3/34

Abstract

The present invention relates to a system and methodology providing layered probabilistic representations for sensing, learning, and inference from multiple sensory streams at multiple levels of temporal granularity and abstraction. The methods facilitate robustness to subtle changes in environment and enable model adaptation with minimal retraining. An architecture of Layered Hidden Markov Models (LHMMs) can be employed having parameters learned from stream data and at different periods of time, wherein inferences can be determined relating to context and activity from perceptual signals.

Claims

1. A learning system for signal processing comprising a computer processor and memory for executing the following components, the system is recorded on a computer-readable medium and capable of execution by a computer, comprising the:

N classification layers, each of the N classification layers associated with M_N probabilistic models per layer, N and M being integers, respectively;

at least one parameter defined per a respective classification layer, the parameters trained independently at different classification layers;

at least one input stream that is analyzed by the N classification layers, at least one of the input streams sampled according to varying levels of temporal granularity at the respective classification layers;

a plurality of time inputs that are applied as sample inputs to the respective layers, the plurality of time inputs are arranged in a descending order of temporal granularity, the descending order refers to lower levels of the N classification layers being sampled at finer time granularities than higher levels of the N classification layers;

wherein the N classification layers analyze multiple input streams to determine at least one state associated with a human characteristic, the multiple input streams include at least one of audio data, video data, computer activity data, and other contextual activity data, and wherein at least one of the determined states is stored to enable a computer event; and

at least one computer event that is enabled from at least one of the state, and at least one of the computer events is at least one of anticipated, altered, tuned, and adjusted in accordance with a determined state.

2. The system of claim 1, the computer activity data relates to at least one of mouse movements, applications activity, and keyboard strokes.

3. The system of claim 1, the at least one state includes a context state, the context state defines at least one of what is a user doing, how busy the user is, how focused the user is, and where attentional resources of the user are being applied.

4. The system of claim 1, the at least one state includes at least one of a user activity and a user pattern, the user activity includes at least one of a phone conversation, a face-face conversation, a presentation, a distant conversation, no person in the office, user present, other activity engaged.

5. The system of claim 1, the at least one state includes a behavior, the at least one behavior includes at least one of happy, upset died, relaxed, and excited.

6. The system of claim 5, further comprising at least one of inferences about possible states and implied states.

7. The system of claim 1, the at least one computer event further comprising at least one of invoking an application, adjusting the application, altering timing of the application, providing feedback from the application, adjusting one or more controls, providing information utilities to the user based on the determined state, and executing a subsequent algorithm based upon the determined state.

8. The system of claim 1, further comprising at least one feature vector that is generated by a respective classification layer, the feature vector being passed to a subsequent stage for probabilistic processing.

9. The system of claim 1, the N classification layers are at least one of concurrently processed and serially processed.

10. The system of claim 1, the N classification layers provide a hierarchical configuration to support learning human activities from sensed data.

11. The system of claim 10, the hierarchical configuration employs at least one of Directed Acyclic Graphs (DAG) and Dynamic Graphical Models, the Directed Acyclic Graphs (DAG) and Dynamic Graphical Models include Dynamic Bayesian Networks, a Hidden Markov Model (HMM), and a hierarchically arranged layered Hidden Markov Model (LHMM).

12. The system of claim 11, the DAG includes a set of random variables represented as nodes and one or more directed edges between the nodes.

13. The system of claim 12, the DAG defines a mathematical form of conditional Probability Distribution Function (PDF) between the random variables.

14. The system of claim 11, the HMM performs a quantization of a system configuration space into a small number of discrete states having probabilities for transitions between the states.

15. The system of claim 14, further comprising a finite discrete variable to index a current state of the system.

16. The system of claim 1, the M_n probabilistic models further comprise at least one of Support Vector Machines (SVM), Naive Bayes, Bayesian Network, Dynamic Graphical Models, Decision Trees, Similarity-based, and Vector-based Models.

17. A computer-implemented method to facilitate learning in a sampled data system, comprising the following computer-executed acts:

determining a plurality of parameters for a layered classification system, each layer of the layered classification system includes M associated probabilistic models, M being an integer greater than 1;

connecting at least two layers of the layered classification system, via an inferential result from a lower classification layer to a higher classification layer;

training the plurality of parameters that are configured on different layers of the layered classification system independently;

applying a plurality of time inputs as sample inputs to the layers, the plurality of time inputs are arranged in a descending order of temporal granularity, the descending order refers to lower levels of the N classification layers being sampled at finer time granularities than higher levels of the N classification layers;

determining at least one model state from the layered classification system;

storing at least one of the determined model states for adjusting a computer event; and

adjusting at least one computer event based upon at least one of the determined model states, the computer event comprises at least one of adjusting computer applications, adjusting timing, providing feedback, and changing at least one control.

18. The method of claim 17, further comprising learning the plurality of parameters by solving a forward-backward algorithm.

19. The method of claim 18, the forward-backward algorithm provides expressions for an α

_t (i) and β

_r (i) variables forming a normalized product leads to γ

_t (i)=P (q_t=S_i |O(1;

t)), wherein a conditional likelihood of a particular state S_i at time t, is given as O(1;

t), representing observations up to time t, the α

_t (i) variable is expressed as;

${\mathrm{\alpha <br><br>}}_{t+1}<br><br>\left(j\right)=\left[\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_t<br><br>\left(i\right)<br><br>P_{j|i}\right]<br><br>p_j<br><br>\left(o_t\right),$

the β

_t (i) variable is expressed as;

${\mathrm{\beta <br><br>}}_t<br><br>\left(i\right)=\left[\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\beta <br><br>}}_{t+1}<br><br>\left(j\right)<br><br>P_{i|j}<br><br>p_j<br><br>\left(o_{t+1}\right)\right],$

wherein N is the number of hidden states, P_ij is the probability of state i given state j and p_i (o_t) is the probability for state i of observing o_t.

20. The method of claim 17 the at least one model state is determined via a Viterbi algorithm that yields a most likely sequence of states Ŝ

within the model given an observation sequence O={O_l. . . ,O_n}.

21. The method of claim 20, the most likely sequence of states Ŝ

determined by Ŝ

=argmax_sP(S|O).

22. The method of claim 21, further comprising a posterior state sequence probability P(S|O) that is expressed as:

$P<br><br>\left(S|O\right)=\frac{P_{\mathrm{s1}}<br><br>p_{\mathrm{s1}}<br><br>\left(o_1\right)<br><br>\underset{t=2}{\overset{T}{\prod <br><br>}}<br><br>p_{s_t}<br><br>\left(o_t\right)<br><br>P_{s_t|s_{t-1}}}{P<br><br>\left(O\right)}$

wherein S={a₁, . . . ,a_N};

is a set of discrete states, s_t∈

S corresponds to a state at time t, and P_i|j=P<sub>st=ai |s t−

1=α

j</sub> is a stats-to-state transition probability.

23. The method of claim 22, further comprising determining prior probabilities for an initial state as P_i=P_sj=ai=P_{s l} and determining p_i(o_t)=p_st=ai(o_t=p_st(o_t)) to represent output probabilities for respective states.

24. A computer-implemented method to facilitate signal processing in an intelligent system, comprising the following computer-executed acts:

applying a plurality of sensor signals at a base layer of a probabilistic hierarchy;

determining at least one feature vector for an intermediary layer of the probabilistic hierarchy;

employing a tertiary layer of the probabilistic hierarchy to discriminate data;

applying a plurality of time inputs as sample inputs to the base, intermediary and tertiary layers, the plurality of time inputs are arranged in a descending order of temporal granularity, the descending order refers to lower levels of the N classification layers being sampled at finer time granularities than higher levels of the N classification layers;

associating longer temporal concepts with subsequent layers of the probabilistic hierarchy, the base layer, the intermediary layer, the tertiary layer and subsequent layers of the probabilistic hierarchy comprise a plurality of probabilistic models;

determining at least one model state from the base, intermediary and tertiary layers;

storing at least one of the determined model states for adjusting a computer event; and

adjusting at least one computer event based upon at least one of the determined model state, the computer event comprises at least one of adjusting computer applications, adjusting timing, providing feedback and changing at least one control.

25. The method of claim 24, further comprising applying the probabilistic hierarchy within an awareness application in order to at least one of learn and detect activities associated with the application.

26. The method of claim 25, the activities are associated with at least one of an office, a location, a home, a public place, and an automobile.

27. The method of claim 24, further comprising discriminating data by training at least one HMM to recognize a sensor input.

28. The method of claim 24, further comprising classifying audio signals with at least one HMM in order to implement a sound classifier.

29. The method of claim 24, further comprising a sound that is localized utilizing a Time Delay of Arrival technique.

30. The method of claim 24, further comprising classifying video signals with at least one HMM in order to implement a person detector.

31. A computer-implemented method to facilitate real time signal processing, comprising the following computer-executed acts:

defining a multi-layer classification system;

defining one or more probabilistic models per a respective layer of the multi-layer classification system;

defining different sample rates per the respective layer;

applying a plurality of time inputs as sample inputs to the respective layers, the plurality of time inputs are arranged in a descending order of temporal granularity, the descending order refers to lower levels of the N classification layers being sampled at finer time granularities than higher levels of the N classification layers;

feeding inferential outputs from previous layers to subsequent layers of the multi-layer classification system;

inferring multiple states from analytical results derived from previous layers;

storing the inferred model states for adjusting a computer event; and

adjusting at least one computer event based upon the inferred multiple states, the computer event comprises at least one of adjusting computer applications, adjusting timing, providing feedback, and changing at least one control.

32. An analysis system comprising a computer processor and memory for executing the following software components, the system is recorded on a computer-readable medium and capable of execution by a computer, comprising:

at least one processing component at a lowest layer of a classification system to analyze multiple signal input streams;

at least one feature vector indicating results from a portion of the lowest layer; and

at least one behavioral model executable on a highest layer of the classification system to infer human behavior based at least in part on the feature vector, the lowest layer, the higher layer and intermediary layers of the classification system comprise a plurality of probabilistic models

a plurality of time inputs that are applied as sample inputs to the lowest and highest layers, the plurality of time inputs are arranged in a descending order of temporal granularity, the descending order refers to lower levels of the N classification layers being sampled at finer time granularities than higher levels of the N classification layers, and wherein the inferred human behavior is stared to enable a computer event; and

at least one computer event that is enabled from the inferred human behavior, at least one of the computer events is at least one of anticipated, altered, tuned, and adjusted in accordance with the inferred human behavior.

33. The system of claim 32, the human behavior includes at least one of phone conversation, face-to-face conversation, conversation, presentation, distant conversation, nobody at location, user present, and engaged in some other activity.

34. The system of claim 32, further comprising at least one of binaural microphones to provide audio inputs, and a Universal Serial Bus (USB) camera to provide video signals.

35. The system of claim 32, the processing component determines Linear Predictive Coding (LPC) coefficients and applies a feature selection on the coefficients by a process of principal component analysis (PCA).

36. The system of claim 32, the processing component extracts higher-level features from the input streams including at least one of an energy computation, a mean and variance of a fundamental frequency over a time window computation, and a zero crossing rate determination.

37. The system of claim 36, the zero crossing rate determination is expressed as:

$\mathrm{Zero}<br><br>\left(m\right)=\frac{1}{N}<br><br>\underset{n=m-N+1}{\overset{m}{\sum <br><br>}}<br><br>\frac{<br><br>\mathrm{sign}<br><br>\left(s<br><br>\left(n\right)\right)-\mathrm{sign}<br><br>\left(s<br><br>\left(n-1\right)\right)<br><br>}{2}·<br><br>w<br><br>\left(m-n\right)$

wherein m is a frame number, N is a frame length, w is a window function, s(n) is a digitized speech signal at an index indicator n, and sign(s(n))={+1, s(n)>

=0;

−

1, s(n)<

0}.

38. The system of claim 32, further comprising a component to determine a feature, the feature including at least one of a density of skin color in an image, a density of motion in the image, a density of foreground pixels in the image and a density of face pixels in the image.

39. The system of claim 32, further comprising a localization component to localize sound, the localization component employing a Time Delay of Arrival (TDOA) process.

40. The system of claim 39, the TDOA determines time delays between signals originating from different sensors, the TDOA includes at least one of a time delay estimation (TDE) and a sound source localization (SSL).

41. A system to facilitate computer signal processing comprising a computer processor and memory for executing the following software components, the system is recorded on a computer-readable medium and capable of execution by a computer, comprising:

means for configuring a multi-layer classification system;

means for training one or more probabilistic models per a respective layer of the multi-layer classification system;

means for providing various time sample rates per the respective layer;

means for applying a plurality of time inputs as sample inputs to the respective layers, the plurality of time inputs are arranged in a descending order of temporal granularity, the descending order refers to lower levels of the N classification layers being sampled at finer time granularities than higher levels of the N classification layers;

means for feeding inferential outputs from previous layers to subsequent layers of the multi-layer classification system;

means for inferring multiple human states from analytical results derived from previous layers;

means for storing the inferred multiple human states for adjusting a computer event; and

means for adjusting at least one computer event based upon the inferred multiple human states, the computer event comprises at least one of adjusting computer applications, adjusting timing, providing feedback, and changing at least one control.

42. A signal to communicate sensor data between at least two nodes system for signal processing, comprising a computer processor and memory for executing the following components, the signal is recorded on a computer-readable medium and capable of execution by a computer, comprising:

a first data packet comprising;

an N layered classification component employed to communicate probabilistic results between at least two layers of N layered classification system; and

at least one parameter defined per a respective classification layer, the parameters trained independently at different classification layers; and

at least one input stream that is analyzed by the N classification layers, at least one of the input streams is sampled according to varying levels of temporal granularity at the respective classification layers, the N layered classification component and the different classification layers comprise M probabilistic models, M and N being integers greater than 1;

a plurality of time inputs that are applied as sample inputs to the respective layers, the plurality of time inputs are arranged in a descending order of temporal granularity, the descending order refers to lower levels of the N classification layers being sampled at finer time granularities than higher levels of the N classification layers;

wherein the N classification layers analyze multiple input streams to determine at least one state associated with a human characteristic, the multiple input streams include at least one of audio data, video data, computer activity data, and other contextual activity data, and wherein at least one of the states is stored to enable a computer event; and

at least one computer event that is enabled from at least one of the states, and at least one of the computer events is at least one of anticipated, altered, tuned, and adjusted in accordance with a determined state.