Regime Shifts in Streams:
Real-time Forecasting ofCo-evolving Time Sequences
Yasuko Matsubara, Yasushi Sakurai(Kumamoto University)

KDD 2016

Y. Matsubara & Y. Sakurai

1

Big time-series data streams• Given:Co-evolving event streams• Goal:Real-time forecastingX?
Forecast

KDD 2016

Y. Matsubara & Y. Sakurai

2Requirements
What is “Real-time forecasting”?
(a) ls-steps-ahead forecasting
Long-termXls-steps?

Continuous(b) Adaptive non-linear modeling
Non-linearAdaptiveKDD 2016

Y. Matsubara & Y. Sakurai

6

(a) ls-steps-ahead forecasting
Long-term: Predict ls-steps ahead events

Continuous : Capture dynamic patterns
ArrivedeventsX

KDD 2016

Futureevents?
Y. Matsubara & Y. Sakurai

ls-steps
aheadeventsls7

(b) Adaptive non-linear modeling
Non-linear: Non-linear dynamical systems

Adaptive: Regime shifts (ecosystems)
Shift

NLDSs
Image courtesy of dan at FreeDigitalPhotos.net.

KDD 2016

Woodlands

Y. Matsubara & Y. Sakurai

Grasslands8Latent non-linear dynamics

P1

Various patterns (“regimes”) in streams

Originaldata
OriginalOrigi(left)
stretching
stretching(right)
walkingwalking (left) stretching(left)(left)(both)(both)(both)

Value

2 20 0−2 −21000

1000
1000
2000

1500
1500 2000
2000
2500
3000
Time

Forecastedvariables
Forecastedvariables
Forecasted variables

2 20 0−2 −2

Value

500
500
1500

KDD 2016

Y. Matsubara & Y. Sakurai

2500
2500
3500
Time
T

9

Regime shifts in streams

P2

Various patterns (“regimes”) in streams

stretching (left) (both) Origina

walking20−2500

1000

1500

2000

Forecasted variables
20−2

KDD 2016

Y. Matsubara & Y. Sakurai

2500
Tim

10

Regime shifts in streams

P2

Various patterns (“regimes”) in streams

stretching (left) (both) Origina

walking20−2500

20−2Regime #1“Walk”KDD 2016

1000

1500

2000

Forecasted variables

Y. Matsubara & Y. Sakurai

2500
Tim

11

Regime shifts in streams

P2

Various patterns (“regimes”) in streams

stretching (left) (both) Origina

walking20−2500

20−2

Regime #1“Walk”KDD 2016

1000

Shift1500

2000

Forecasted variables

2500
TimRegime #2“Stretch”

Y. Matsubara & Y. Sakurai

12Regime shifts in natural systems
P2

Abrupt changes in the structure of complex systems

Example:• Woodland vs. grassland• Coral vs. macro algae• Desert vs. vegetation

Woodlands

Grasslands

Ecological system
Image courtesy of dan at FreeDigitalPhotos.net.

KDD 2016

Y. Matsubara & Y. Sakurai

13

Regime shifts in event streams
P2

Abrupt changes in the structure of complex systems
32Value20

10−1−2−2300 400 500 600 700 6500 6600 6700 6800 6900

Woodlands

Grasslands

Ecological system
Image courtesy of dan at FreeDigitalPhotos.net.

KDD 2016

Walking

WipingMotion sensors

Y. Matsubara & Y. Sakurai

14

Nested structure

P3

Nested, multi-scale dynamics
Chicken
dance

2
Xorg
0−2200400600

800

1000 1200

200400600800

1000 1200

200
KDD 2016

400600800 1000 1200
Y. Matsubara & Y. Sakurai

2X(1)0−22(2)

X 0−2

Original events(1) : Long-term
X+(2)
X : Short-term
15

Nested structure

P3

Nested, multi-scale dynamics
Chicken
dance

2
Xorg
0−22X

(1)

200

400

600

800

Xorg = X + X

1000 1200

(2)

(1)
0

Tail feathers =−2

bending knees, once2(2)200400600

X 0−2200
KDD 2016

800+1000 1200moving arms, quickly
400

600

800 1000 1200
Y. Matsubara & Y. Sakurai

16

Problem definition• RegimeSnap
Current window XC

Forecast window VF

Value

2Event stream X
Estimated events VE

0−20200

tm

400
Time

Tim
e Arrived events
KDD 2016

tc600 ts te 800
Future (unknown) events
Y. Matsubara & Y. Sakurai

17

Problem definition• RegimeSnap
Current window XC

XC

Value

20−20200

tm

400
Time

Tim
e Arrived events
KDD 2016

Forecast window VF

Given:
Event stream X

tc600 ts teCurrentwindow
EstimatedeventsXVCE(originalevents)
800

Future (unknown) events
Y. Matsubara & Y. Sakurai

18

Problem definition• RegimeSnap

Find:

Estimated events VE
Current window XC
VForecastwindow
Forecast window FVFVEValue

20−20200tm

400
Time

Time Arrived events
KDD 2016

Event stream X
Estimated events VE

tc600 ts te 800VF

Future (unknown) events
Y. Matsubara & Y. Sakurai

19

Streaming algorithm• Proposed algorithms
A1X?

lsRegimeCast
Report ls-steps-ahead future events

A2 RegimeReader
Identify current regime dynamics

A3 RegimeEstimatorEstimates regime parameter set θ
KDD 2016

Y. Matsubara & Y. Sakurai

20RegimeCast
Event stream X

TimeXCΘθ1(1)θ 2(1)

θKDD 2016

θ(2)2Report VF(1)ModelDB

RegimeReader

Θ(2 )
(2)
1

tc

RegimeEstimator... ≈+VE(1)Y. Matsubara & Y. Sakurai

Forecast
window

VE

VE(2)
21

RegimeCast
Event stream X

TimeXCΘθ1(1)

θ 2(1)

tc
Report VF(1)ModelRegime
DB Step1:

Forecast
window

ReaderCurrent
X...
≈CRegime window+

Θ(2 )
(2)
1

θ

KDD 2016

θ(2)
2

EstimatorVE(1)Y. Matsubara & Y. Sakurai

VE

VE(2)
22

RegimeCast
Step2:
Eventstream X

Time

Find optimal
regime/model
Θ(1)
1

θθ(1)
2

θKDD 2016

θ(2)2Report VF(1)ModelDB

Θ(2 )
(2)
1

XC

tc

RegimeEstimator

RegimeReader... ≈+VE(1)Y. Matsubara & Y. Sakurai

Forecast
window

VE

VE(2)
23

RegimeCast
Event stream X

TimeXCΘ(1)1θModelVE
DB(2 )(2)
1

θKDD 2016

θ(2)2Report VF(1)

Step3:
θ
Estimate
future Θevents
(1)
2

tc

RegimeEstimatorRegimeReader... ≈+VE(1)Y. Matsubara & Y. Sakurai

Forecast
window

VE

VE(2)
24

RegimeCast
Event stream X

XC+
Step4:
Estimate
new tcTime
XC
regime (optional)
ReportΘ(1)θ1(1)θ 2(1)Model
DB

RegimeReader

Θ(2 )
(2)
1

θ

KDD 2016

θ(2)2RegimeEstimator V... ≈+(1)E

Y. Matsubara & Y. Sakurai

VF

Forecast
window

VE

VE(2)
25

RegimeCast
Event stream X

tcTime
Step5:V
XC
F
Repor
Reportt V
futureeventsF(1)Θθ1(1)

θ 2(1)

Forecast
Regime window

ModelDB

ReaderΘ(2 )(2)1θ

KDD 2016

θ(2)
2

RegimeEstimator... ≈+VE(1)Y. Matsubara & Y. Sakurai

VEVE(2)26

RegimeCast
Event stream X

TimeXCΘθ1(1)θ 2(1)

θKDD 2016

θ

(2)
2

Report VF(1)ModelDB

RegimeReader

Θ(2 )
(2)
1

tc

RegimeEstimator... ≈+VE(1)Y. Matsubara & Y. Sakurai

Forecastwindow

VE

VE(2)
27

Forecasting power of RegimeCast
Real-time forecasting over data streams
Original
Forecast(100-steps-ahead)
Snap-Shot(Currentwindow)
KDD 2016

Y. Matsubara & Y. Sakurai

28

Forecasting power of RegimeCast
Real-time forecasting over data streams
Original
Forecast

Arrivedevents

Futureevents(100-steps-ahead)
Snap-Shot(Currentwindow)
KDD 2016?
Y. Matsubara & Y. Sakurai

29

Forecasting power of RegimeCast
Real-time forecasting over data streams
Original
Forecast(100-steps-ahead)
Snap-Shot(Currentwindow)
KDD 2016

Y. Matsubara & Y. Sakurai

30

Q1. Effective – MoCap #1

KDD 2016

Y. Matsubara & Y. Sakurai(100-120)steps ahead

31

Q1. Effective – MoCap #2

KDD 2016

Y. Matsubara & Y. Sakurai(100-120)steps ahead

32

Q1. Effective – MoCap #3

KDD 2016

Y. Matsubara & Y. Sakurai(30-35)steps ahead

33

Q1. Effective – Google Trend

3-monthsahead
KDD 2016

Y. Matsubara & Y. Sakurai

34

Q1. Effective – Google Trend

3-monthsahead
KDD 2016

Y. Matsubara & Y. Sakurai

35

Q1. Effective – others
Atmospheric pressure & temperature

3-monthsahead

3-monthsahead
KDD 2016

Y. Matsubara & Y. Sakurai

36

Q1. Effective – others
Yen vs. dollar & AU vs. PT

6-weeksahead
KDD 2016

3-monthsahead
Y. Matsubara & Y. Sakurai

37

Q2. Accuracy
Regime
Cast

ARIMA
TBATS
KDD 2016

Y. Matsubara & Y. Sakurai

38

Q3. Scalability
Regime
Cast

ARIMA
TBATS
KDD 2016

Y. Matsubara & Y. Sakurai

39

Discussion
lsls-steps-ahead
forecastingXls-steps vs. error

ls-steps vs. speed

KDD 2016

Y. Matsubara & Y. Sakurai?

40Regime Shifts in Streams:
Real-time Forecasting of
Co-evolving Time Sequences
Yasuko Matsubara, Yasushi Sakurai(Kumamoto University)

KDD 2016

Y. Matsubara & Y. Sakurai

41