Transcript DynaMMo: Mining and Summarization of Coevolving Sequences

DYNAMMO: MINING AND
SUMMARIZATION OF COEVOLVING
SEQUENCES WITH MISSING VALUES
Lei Li
joint work with Christos Faloutsos, James
McCann, Nancy Pollard
June 9, 2009
Microsoft Research
CHALLENGE

Multidimensional coevolving time series:



Motion Capture sequence
Temperature/humidity monitoring
Daily Chlorine level measurement in drinking water system
Big challenge:


Missing observations
Mining with missing values
Find hidden patterns
 Use of hidden patterns

2
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values

MISSING VALUES IN MOCAP
Left Hand
position
Right Hand
position
3
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Marker/Sensor
Time
BLANK-OUTS IN MOCAP
Left Hand
position
Right Hand
position
4
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Marker/Sensor
Time
GOAL
•
1.
2.
3.
4.
Effective: low reconstruction error, agreeing with human
intuition (e.g. natural reconstructed motion for mocap)
Scalable: to time-duration T of the sequences.
Black-outs: It should be able to handle “black-outs”, when
all markers dissappear (eg., a person running behind a
wall, for a moment).
Automatic: The method should require no parameters to
be set by the user.
5
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
We want recovering, mining and summarization
algorithms to be:
OUTLINE

Scenario and Motivation

Proposed Methods – DynaMMo



Recovering missing
values
Compression and
summarization
Forecasting
Segmentation
Experimental Results
 Conclusion

6
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values

SCENARIO: MOTION CAPTURE

Motion Capture:
Markers on human actors
 Cameras used to track the 3D
positions
 Duration: 100-500
 93 dimensional body-local
coordinates after preprocessing (31bones)

Challenge:


Occlusions
Other general scenario:
Missing value in Sensor data: Out of
battery, transmission error, etc
 Unable to observe, e.g.
historical/future observation

From mocap.cs.cmu.edu
7
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values

OBSERVATION AND MOTIVATION
Dynamics:
temporal
moving pattern
 Correlation
among multiple
markers

Right Hand
Left Foot
Right Foot
8
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Use both
dynamics and
correlation to
solve occlusion.
Left Hand
THE UNDERLYING TIME SERIES MODEL
LINEAR DYNAMICAL SYSTEMS
N(z0, Γ)
N(G∙z1, Σ)
Z2
N(F∙z2, Λ)
N(G∙z2, Σ)
Z3
N(G∙z3, Σ)
N(F∙z3, Λ)
Z4
N(F∙z4, Γ)
N(G∙z4, Σ)
…
z
X1
X2
Model parameters:
θ={z0,
Γ, F, Λ, G, Σ}
X3
X4
z1 = z0+ω0
zn+1 = F∙zn+ωn
xn = G∙zn+εn
9
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Z1
N(F∙z1, Λ)
DYNAMMO RECOVERING ALGORITHM
Expectation Maximization
 Intuition:
Finding the best model parameters (θ) and missing
values for X to minimize the expected loglikelihood:

10
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
See details in paper
DYNAMMO INTUITION:
correlation
dynamics
Right Hand
missing
11
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Left Hand
DYNAMMO COMPRESSION: INTUITION
observations w/ missing values
keep only a (best) portion of them
12
Same idea could be used in segmentation and forecasting
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
get hidden variables and model parameters
EXPERIMENT
•
Dataset:
Chlorine: Chlorine level in drinking water system
•
•
–
Mocap: full body human motion capture dataset
–
–
•
•
Duration 4310 time ticks
166 sequences
58 motions
each with duration 100-500, 93 dimensions
Occlusion: random mask out
Baseline:
–
–
linear interpolation and spline
MSVD:
•
•
Missing value SVD algorithm
EM flavored version of SVD.
13
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
–
RESULTS
•
•
•
•
14
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
•
Reconstruction Error for random mask out
Scalability: computation time to duration
Forecasting case study
Compression: error versus space
Segmentation for synthetic and real data
DYNAMMO RECONSTRUCTION RESULT
(AVERAGE OVER 10 REPEATS)
Mocap dataset
worse
Reconstruction error
Reconstruction error
better
average consecutive occlusion length
15
easy
difficult
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Chlorine dataset
SCATTER COMPARISON: DYNAMMO VS MSVD
16
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
error of DynaMMo
error of MSVD
DYNAMMO SCALABILITY
17
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Computation time
sequence length (chlorine data)
DYNAMMO FORECASTING
Predicted signal
using learned
model
18
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Actual Data
DYNAMMO COMPRESSION
error
DynaMMo
optimal
compression
better
Compression ratio
more space
19
less space
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
worse
DYNAMMO SEGMENTATION
segmentation
using
reconstruction
error
20
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
original data
MOCAP SEGMENTATION
RUNNING TRANSITION MOTION (MOCAP#16.8)
left femur
segmentation
using
reconstruction
error
21
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
left hip
CONTRIBUTION
We propose algorithms DynaMMo for



•
Recovering missing
values
Compression and
summarization
Forecasting
Segmentation
DynaMMo meets all goals:
1.
2.
3.
4.
Effective: low reconstruction error, agreeing with human
intuition (e.g. natural reconstructed motion for mocap)
Scalable: computation time linear to length/duration T of
the sequences.
Black-outs: able to handle “black-outs”, when all markers
dissappear.
Automatic: The methods should require few parameter to
be set by the user.
22
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
•

QUESTION
Thanks!
 Contact: [email protected]

Lei Li
Christos
Faloutsos
Jim McCann
23
Li et al. DynaMMo: Mining and Summarization of Coevolving Sequences with Missing Values
Nancy
Pollard