Learning to Filter with Predictive
State Inference Machines
Wen SunJoint work with Arun Venkatraman, Byron Boots, and Drew Bagnell

Recursive Bayesian FilteringLatent State Space Modele.g., Hidden Markov Model (HMM)
Linear Dynamical Systems (LDS)

xt+1 ⇠ P (X|xt )

yt+1 ⇠ P (Y |xt+1 )

xt

yt 1

yt

xt+1

Latent State Space Modele.g., Hidden Markov Model (HMM)
Linear Dynamical Systems (LDS)

xt+1 ⇠ P (X|xt )

yt+1 ⇠ P (Y |xt+1 )P (xt |y1 , ..., yt 1 )

xt

yt 1

yt

xt+1

Latent State Space Modele.g., Hidden Markov Model (HMM)
Linear Dynamical Systems (LDS)

xt+1 ⇠ P (X|xt )

yt+1 ⇠ P (Y |xt+1 )P (xt |y1 , ..., yt 1 )xt

yt 1ytP (xt+1 |y1 , ..., yt )xt+1

Latent State Space Modele.g., Hidden Markov Model (HMM)
Linear Dynamical Systems (LDS)

xt+1 ⇠ P (X|xt )

yt+1 ⇠ P (Y |xt+1 )P (xt |y1 , ..., yt 1 )xt

yt 1ytP (xt+1 |y1 , ..., yt )xt+1

Classic Approach

Classic Approach

Sequencesof observation

Classic Approach

Sequencesof observation

Hypothesize a model(e.g., LDS)Classic Approach

Sequencesof observation

Hypothesize a model(e.g., LDS)

Learning(e.g., EM)Classic Approach

Sequencesof observation

Hypothesize a model(e.g., LDS)

Learning(e.g., EM)ˆ✓

Learned parameters(e.g., MLE)

k✓ˆ

⇤✓ k=
6 0

e.g., local optimal (EM),finite data (Spectral methods)

5

k✓ˆ

⇤

✓ k=
6 0

e.g., local optimal (EM),finite data (Spectral methods)

5Model Mismatch

k✓ˆ

⇤

✓ k=
6 0e.g., local optimal (EM),finite data (Spectral methods)

Model Mismatch

System identification generally does not guarantee
filtering or prediction performance5

Goal:
Directly learn the filter procedure to predict from history tofuture observations.
•Similar to Recurrent Neural Networks•Performance guarantees on prediction errors•Good practical performance

Predictive State Representationx1

y1x2x3tx...

yt 1yt...

x[Singh et al., 2004, Hefty et al. 2015] 7

Predictive State Representationx1

y1x2x3tx...

yt 1yt...

xht 1 = [y1 , . . . , yt 1 ][Singh et al., 2004, Hefty et al. 2015] 7

Predictive State Representationx1y1x2x3tx...

yt 1yt...

ht 1 = [y1 , . . . , yt 1 ]x

ft = [yt , yt+1 , . . . , yt+k 1 ][Singh et al., 2004, Hefty et al. 2015] 7

Predictive State Representationx1y1x2x3tx...

yt 1yt...

ht 1 = [y1 , . . . , yt 1 ]x

ft = [yt , yt+1 , . . . , yt+k 1 ]P (xt |ht 1 ) , P (ft |ht 1 ) K-observability[Kalman 1963, Hsu et al. 2012][Singh et al., 2004, Hefty et al. 2015] 7

Predictive State Representationx1

y1x2x3tx...

yt 1yt...

ht 1 = [y1 , . . . , yt 1 ]x

ft = [yt , yt+1 , . . . , yt+k 1 ]P (xt |ht 1 ) , P (ft |ht 1 ) K-observability[Kalman 1963, Hsu et al. 2012]

P (ft |ht 1 ) , E[ (ft )|ht 1 ][Singh et al., 2004, Hefty et al. 2015] 7

Predictive State Representationx1y1x2x3tx...

yt 1yt...

ht 1 = [y1 , . . . , yt 1 ]x

ft = [yt , yt+1 , . . . , yt+k 1 ]P (xt |ht 1 ) , P (ft |ht 1 ) K-observability[Kalman 1963, Hsu et al. 2012]

P (ft |ht 1 ) , E[ (ft )|ht 1 ]Sufficient Features[Singh et al., 2004, Hefty et al. 2015] 7

Predictive State Representationx1

y1x2x3tx...

yt 1yt...

ht 1 = [y1 , . . . , yt 1 ]x

ft = [yt , yt+1 , . . . , yt+k 1 ]P (xt |ht 1 ) , P (ft |ht 1 ) K-observability[Kalman 1963, Hsu et al. 2012]

P (ft |ht 1 ) , E[ (ft )|ht 1 ]Sufficient Features[Singh et al., 2004, Hefty et al. 2015] 7

...
y0...
yt

yt+1

...
yt+k 1yt+k

E[ (ft )|ht 1 ]

...
y0...
yt

yt+1...
yt+k 1yt+k

E[ (ft )|ht 1 ]

...
y0...
yt

yt+1

Predictive State
Filter...
yt+k 1yt+k

E[ (ft )|ht 1 ]

...
y0...
yt

yt+1

...
yt+k 1

E[ (ft+1 )|ht ]Predictive State
Filteryt+kE[ (ft )|ht 1 ]

...
y0...
ytyt+1...
yt+k 1

E[ (ft+1 )|ht ]Predictive State
Filteryt+kE[ (ft )|ht 1 ]

...
y0...
yt

yt+1...
yt+k 1

E[ (ft+1 )|ht ]Predictive State
Filteryt+kE[ (ft )|ht 1 ]

...
y0...
yt

yt+1...
yt+k 1yt+k

E[ (ft+1 )|ht ]Predictive State
FilterkE[ (ft )|ht 1 ](f˜t )k2

E[ (ft )|ht 1 ]

...
y0...
yt

yt+1...
yt+k 1yt+k

E[ (ft+1 )|ht ]Predictive State
FilterkE[ (ft )|ht 1 ]Moment Matching(f˜t )k2

E[ (ft )|ht 1 ]

...
y0...
yt

yt+1...
yt+k 1yt+k

E[ (ft+1 )|ht ]Predictive State
FilterTX
t=1

kE[ (ft )|ht 1 ]Moment Matching(f˜t )k2

E[ (ft )|ht 1 ]

...
y0...
yt

yt+1...
yt+k 1yt+k

E[ (ft+1 )|ht ]Predictive State
FilterTX
t=1

kE[ (ft )|ht 1 ]Moment Matching(f˜t )k2

Learning Non-stationary Filters
mt = E[ (ft )|ht 1 ]

m1y1

g1

m2

y2

g2

m3
y3

g3

. . . gT

Learning Non-stationary Filters
mt = E[ (ft )|ht 1 ]

m1
y1

g1

m2

y2

g2

m3

g3

. . . gT

y3
Supervision f2 for m2

Learning Non-stationary Filters
mt = E[ (ft )|ht 1 ]

m1

g1

m2

g2

y2

y1

m3

g3

. . . gT

y3
Supervision f2 for m2

min

g1 ,g2 ,...,gT

E⌧

T
X
t=1kgt (mt , yt )s.t. mt+1 = gt (mt , yt ), 8t(ft+1 )k2Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1

y2y3

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1y2f2y3

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1y2y3

f2

g1 = arg min
g2GX⌧kg(m1 , y1 )(f2 )k2

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1

m2

g1

y1

y2y3

f2

g1 = arg min
g2G

X⌧kg(m1 , y1 )(f2 )k2

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1

g1

m2y2y3

g1 = arg min
g2GX⌧kg(m1 , y1 )(f2 )k2

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1

g1

m2y2y3f3

g1 = arg min
g2G

X
⌧

kg(m1 , y1 )(f2 )k2

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1

g1

m2y2y3f3

g1 = arg min
g2G

g2 = arg min
g2G

X
⌧

X
⌧

kg(m1 , y1 )kg(m2 , y2 )(f2 )k2(f3 )k2

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1

g1

m2

g2

m3y2y3f3

g1 = arg min
g2G

g2 = arg min
g2GX
⌧

X
⌧

kg(m1 , y1 )kg(m2 , y2 )(f2 )k2(f3 )k2

Learning Non-stationary Filters
Forward Training [Ross & Bagnell 2010]

m1y1

g1

m2

g2

m3y2

g3y3
f3

g1 = arg min
g2G

g2 = arg min
g2GX
⌧

X
⌧

kg(m1 , y1 )kg(m2 , y2 )(f2 )k2(f3 )k2

Learning Non-stationary Filters
Performance Guarantee

Learning Non-stationary Filters
Performance GuaranteeE⌧ ⇠D⌧

T
h1 X

T t=1

 E⌧ ⇠D⌧kgt (m̂⌧t , x⌧t )

TX
⇥1

T t=1

kgt⇤ (m̂⌧t , x⌧t )+ 4⌫ R̄(G)rT ln(T / )+22M⌧(ft+1)k2i⌧(ft+1)k2⇤

Learning Non-stationary Filters
Performance GuaranteeE⌧ ⇠D⌧

T
h1 X

T t=1

 E⌧ ⇠D⌧kgt (m̂⌧t , x⌧t )

TX
⇥1

T t=1

kgt⇤ (m̂⌧t , x⌧t )+ 4⌫ R̄(G)r
T ln(T / )+22M⌧(ft+1)k2i⌧(ft+1)k2

Prediction error⇤

Learning Non-stationary Filters
Performance GuaranteeE⌧ ⇠D⌧

T
h1 X

T t=1

 E⌧ ⇠D⌧kgt (m̂⌧t , x⌧t )TX⇥1T t=1

kgt⇤ (m̂⌧t , x⌧t )+ 4⌫ R̄(G)r
T ln(T / )+22M⌧(ft+1)k2i⌧(ft+1)k2

Prediction error⇤Prediction error from thebest Hypothesis

Learning Non-stationary Filters
Performance GuaranteeE⌧ ⇠D⌧T
h1 X

T t=1

 E⌧ ⇠D⌧kgt (m̂⌧t , x⌧t )

TX
⇥1

T t=1

kgt⇤ (m̂⌧t , x⌧t )+ 4⌫ R̄(G)r
T ln(T / )+22M⌧(ft+1)k2i⌧(ft+1)k2

Prediction error⇤Prediction error from thebest Hypothesis

Rademacher number

Learning Non-stationary Filters
Performance GuaranteeE⌧ ⇠D⌧

T
h1 X

T t=1

 E⌧ ⇠D⌧kgt (m̂⌧t , x⌧t )TX⇥1T t=1kgt⇤ (m̂⌧t , x⌧t )+ 4⌫ R̄(G)rT ln(T / )+22M⌧(ft+1)k2i⌧(ft+1)k2

Prediction error⇤

Prediction error from thebest Hypothesis

Rademacher number
Excess Error

Learning Stationary Filters
mt = E[ (ft )|ht 1 ]

m1g

m2g

m3y2

y1min E⌧g

TX
t=1...

gy3

kg(mt , yt )s.t. mt+1 = g(mt , yt ), 8t2(ft+1 )kLearning Stationary Filters
mt = E[ (ft )|ht 1 ]

m1g

m2g

m3y2y1...

gy3
Supervision f2 for m2

min E⌧
gT
X
t=1kg(mt , yt )s.t. mt+1 = g(mt , yt ), 8t2(ft+1 )kLearning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]
Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

13

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]
Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learnerg

13

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]
Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

gm1y1y2y313

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]
Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

g

m1y1g

m2y2y313

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]
Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

gm1y1gm2y2g

m3y313

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]
Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

g

m1y1g

m2y2g

m3

mTy313

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]kg(m2 , y2 )Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

g

m1

y1g

m2y2g

m32(f3 )kmT

y313

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]kg(m2 , y2 )Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

g

m1

m2g

y1
Construct Loss: `t (g) =y2XX⌧tg

2(f3 )kmT

m3
y3kg(mt , yt )2(ft+1 )k13

Learning Stationary Filter
Data Aggregation (DAgger) [Ross & Bagnell 2011]kg(m2 , y2 )Follow the (regularized) Leader,
Online Gradient Descent [Zinkevich,2003]

No-Regret
Online Learner

g

m1

m2

g

y1
Construct Loss: `t (g) =y2XX⌧tg

2(f3 )kmT

m3y3kg(mt , yt )2(ft+1 )k13

Experiments
xt+1 = Axt + ✏x , ✏x ⇠ N (0, Q)
yt = Cxt + ✏y , ✏y ⇠ N (0, R)

Learn linear models:• PSIM with Forward Training (length 2 predictive state)• PSIM with DAgger (length 2 predictive state)• 5 Autoregressive models (history lengths = 5,10, 20, 30, 35)• N4SID

Compare ratio of error of learned predictor to true Kalman Filter Errorwith diﬀerent amounts of training datalog (error of learned predictor / true Kalman Filter Error)

log (error of learned predictor / true Kalman Filter Error)

Data Aggregation

log (error of learned predictor / true Kalman Filter Error)

Autoregressive Model

Data Aggregation

Experiments on Real Dynamical Systems

Filtering Goal: predict multi-step future observations, conditioned onhistory

Experiments on Real Dynamical Systems

Filtering Goal: predict multi-step future observations, conditioned onhistory

Multi-Step Error: PSIM VS Spectral Methods
Robot Drill Assembly

9654321412108641200

Pred. Step 1

RFF + Linear
LinearIVR
N4SID

16Avg. Filtering Error

7RFF + Linear
LinearIVR
N4SID

Pred. Step 2

Pred. Step 3

Pred. Step 4300
250

Pred. Step 1

Pred. Step 2

Beach Video Texture

350

Avg. Filtering Error

Avg. Filtering Error

8Motion Capture

18

RFF + Linear
Linear
IVR
N4SID

200
150
100500Pred. Step 1

Pred. Step 2

Pred. Step 3

Pred. Step 3

Pred. Step 4

Multi-Step Error: PSIM VS Spectral Methods
Robot Drill Assembly976

RFF + Linear
Linear
IVR
N4SID

54321412108641200

Pred. Step 1

RFF + Linear
LinearIVR
N4SID

16Avg. Filtering Error

Avg. Filtering Error

8Motion Capture

18Pred. Step 2

Pred. Step 3

Pred. Step 4

Avg. Filtering Error

300250Pred. Step 2

Beach Video Texture

350

Kernel Regression

Pred. Step 1

RFF + Linear
Linear
IVR
N4SID

200
150
100500Pred. Step 1

Pred. Step 2

Pred. Step 3

Pred. Step 3

Pred. Step 4

Multi-Step Error: PSIM VS Spectral Methods
Robot Drill Assembly976

RFF + Linear
Linear
IVR
N4SID

54321412108641200

Pred. Step 1

Pred. Step 2

Pred. Step 3

Pred. Step 4

Avg. Filtering Error

300
250

Pred. Step 1

Pred. Step 2

Beach Video Texture

350

Kernel Regression
Linear Regression

RFF + Linear
Linear
IVR
N4SID

16

Avg. Filtering Error

Avg. Filtering Error

8Motion Capture

18

RFF + Linear
Linear
IVR
N4SID

200
150
100
500

Pred. Step 1

Pred. Step 2

Pred. Step 3

Pred. Step 3

Pred. Step 4

Comparison to Recurrent Neural Network
The Way of Encoding of History…

Prediction Error

Comparison to Recurrent Neural Network
The Way of Encoding of History…
RNN: Hidden Units (e.g., Memory Cell in LSTM)
PSIM: Predictive State

Prediction Error

Comparison to Recurrent Neural Network
The Way of Encoding of History…
RNN: Hidden Units (e.g., Memory Cell in LSTM)
PSIM: Predictive State

Prediction Error

Conclusion•Predictive State Inference Machines (PSIM): data-driven
approach that directly learns inference procedures for latent state
space models.
•Can use powerful, non-linear learner to directly represent theinference procedure•Similar to RNN, but theoretical Guarantees on inference
performance

Predictive State Inference Machines
ThanksContact: wensun@cs.cmu.edu