第二回データ同化の研究会＠山梨大学
20150330
グラフィカルラッソによる
プローブ未観測リンクの交通状態推定
東北大学
原 祐輔
(共同研究者: 花岡洋平，片岡駿，桑原雅夫)
1. 研究の背景
• 途上国におけるプローブカーによる交通モニタリング
2013/9/31 13:00-13:05
バンコク中心部の交通状態
・観測道路数が最も多い
時間帯で約53%の道路が
未観測
– エリア全体の交通状態を把握することは困難
– 固定観測(感知器)をネットワーク全体に広げることは非効率
– 時間帯・道路リンクごとに取得にばらつきのある データを補間推定することが望まれる
本日の流れ
1. 研究の背景と目的
2. 多次元正規分布による補間アプローチ
3. パラメータ推定のための2つの戦略
4. バンコク中心部におけるケーススタディ
5. 精度検証
6. 推定されたパラメータの解釈
7. 本研究のまとめと今後の課題
本研究の目的
• 本研究の目的
– プローブカーのみから得られる観測データを 用いてエリア全体の交通状態を正確に把握する
• 課題とアプローチ
1. ある単位時間には未観測リンクが多く存在
• 過去データから統計モデルを構築し，補間
2. 過去データにも未観測リンクが多く存在
• 部分観測データから統計モデルを学習できるよう 拡張
3. 予測精度の高い統計モデルの構築方法
• 分析者が強い仮定を置かない柔軟なモデリング
2.本研究における統計モデルの仮定
• ネットワーク上の各方向別道路リンクは交通状態をもつ
– 本研究では具体的には5分単位の平均リンク速度とする
– 本研究では各リンク間の空間的相関のみを対象
– 各時刻別に独立に交通状態が観測されると仮定
• (=大変強い仮定: 時系列相関は今後の課題)
x2
正規分布で良いのか？
• 交通状態の表現に1つの多次元正規分布でいいのか？
– もちろんベストではない(別の分布とか，混合分布とか)
– しかし，多次元正規分布は扱いやすい
– また，補間という観点では柔軟性がある
e.g. x1, x2がリンク1, 2のリンク平均速度とする
x4
P(x2)
x3
x1
周辺化分布
x2
x5
• ネットワーク上の各道路リンク単位の交通状態は ただ一つの多次元正規分布によって生成されていると仮定
– 多次元正規分布の平均ベクトルµと 分散共分散行列 Σ(精度行列Σ-1=Θ) によって ネットワーク交通状況の相関構造を表現
x2
x1
観測されたx1が
傾向をもつ場合の
条件付き分布
P(x2)
P(x1)
x2
x2
未観測リンクの補間手法
3.多次元正規分布のパラメータ推定
(Gaussian Markov Random Field)
• 補間手法は以降，共通のため最初に説明
• 多次元正規分布(=モデル)のパラメータµ, Θは既知#
• ネットワーク全体の交通状態をx = (x1,…,xL)とし， 観測された道路リンクをxo, 未観測リンクをxuで表す!
• このとき，未観測リンクの周辺事後分布は
p(x u | x o , µ, Θ) =
∫
N(x | µ, Θ )∏ δ (yi − xi ) dx o
−1
xo
i∈O
−1
= N(x u | µu − Θ−1
uuΘuo (x o − µ o ), Θuu )
平均ベクトル
=条件付き分布
(1)
分散共分散行列
−1
x̂ u = arg max N(x u | µu − Θ−1
uuΘuo (x o − µ o ), Θuu )
xu
! µ $
" Θ
Θou %
' µ = # u & δ (⋅)
ここで Θ = $ uu ， ， はディラックのデルタ関数
#" µo &%
$# Θuo Θoo '&
1. 標本平均，標本分散共分散行列を計算(=ナイーブ)
– パラメータ数に対してデータ数が十分に得られていない場合， 推定パラメータが学習データに過剰に適合(過学習)
– 精度行列が正則という保障なし
☹
2. 分析者が構造化したGaussian Graphical Model (GGM)
(花岡ら, 2014; Kataoka et al., 2014)!
– モデル構造の設計の段階でパラメータ数を削減
– 精度行列は正則になるよう設計
– 構造化がうまく交通現象を説明できているかは不明
3. 実データから精度行列の構造を推定
(Graphical Lasso; GL)!
– 正則化により1.の問題を解決
– 構造をデータから学習することで2.の問題を解決
☹
zd i ∈ U
z = {xu , y}
d
j∈O
ln p(z d |θ)
y
d
(i, j)
Ω
i, j ∈ O
#2
ηϵ ! dd 2 η ! "1 d
1 T −1 j ∈|V|
d
i∈U
Odln η + const
ln p(z |θ) = β z −
z
−
z
−
z
−
β
Θ
β
−
i
j
d
i, j ∈ Ud2
2 Ω
2 (i, j)∈E i
2η
2
i∈V
2つのアプローチの違い
Ω
Ωd1
(i, j)
(i, j)
Ωd2
d
3
• 2.構造化GGMによるアプローチ
zd
–
xd
i, j ∈ Od
i, j ∈ Ud
p(xdu |y d , θ) exp
$!
i∈Ud
βi (xu )i −
2
i∈Ud
(4.26)
Θ=
(xdu )i −
Dempster et al.12)
(i, j)∈Ω1
z
:"0
12)
EM
&
GGM(4.24)|Ud |
p(xdu |y d , θ) =
η
EM
θ̂
p(xu |y, θ)
xu
#T
"
##
det Θud z " η " d
d
ln
p(z|θ)
exp
−
x
−
µ
Θ
d
d xu − µud
u
U
u
d
Θ = |U |
2
xu
(2π)
ln p(z|θ)
z
Mstep
– Graphical Lasso
(Friedman et al., !
2007)によって推定
θ̂
Mstep
θ new
mdi :=β
ydj
i+ J
Mstep
j∈∂(i),Ωd1
θ0
Estep
Mstep
Mstep
θ new
1 −1 d
old
µud := Θud m
Q(θ,
θ
)
η
θ0
Estep Mstep
Estep
Estep
Estep
2
η
(4.28)
i
θ old
27
|V|
zxidu y−d y d
zi − z j − β Θ β −
ln η + const
d
2(4.26)
2 (i, j)∈E (4.28)
2η Q(θ|θ old2)
i∈V
Estep
d d dd
p(xp(x
|y |y
, θ), θ)
(4.26)
– Mstep
E-step
Q(θ|θ )
4.3.2
Q(θ|θ# old
$!
% )%
$!
28
d !
!!
!!
d !
"
"
!
!
2 #2
"
#
η
ϵ
η
η
η
ϵ
η
η
2
ηϵd d d 2 η d d d d
1d dT) )d2−1−2 |V| (xd ) −
d dd d
d
T d β (x
d (yd(y
p(x
,|θ)
θ), exp
)i −
(x )i −
) j du ) j
θ)
exp
−
)i(x
−du(x
(4.25)
j u ) j )β−
i uconst
lnp(x
p(z
=Estep
β
z −i βui (x
−
z
−
β
Θ
−
ln
η
+
u |yu |y
u(x
u(x
i −i (x
u )i z−
u )iz−
i2 − y u(x
i
j
2 2 d d 2η
2 22 d d
2 2
i∈Udi∈U
(i,j)∈Ω
(i,j)∈Ω
θ i∈Udi∈Ud 2 i∈V
(i,j)∈Ω
(i,j)∈Ω
(i,dj)∈E
xd
1
p(xdu |y d , θ)
3
1
i
u
u i
old
2 y
i∈Ud & &
i∈Ud
– Q関数のパラメータ偏微分
|U |
θu
i
2
i
(i, j)∈Ωd1
u j
2
du i
(i, j)∈Ωd3
4.4.1
u j
28
ln p(Θ, µ) =
∂η
(i,j)∈E
D
d
2η
2
i∈V
D
d
2η2
⎧
µ
(4.1)
Σ
! 1
T
"
D
1# d
log det Θ −
(x − µ)T Θ(xd − µ) + const
2
2
(4.1)
Σ
(4.2)
d
Θ
d
(5)
Θ∗xd==arg
log
(4.31)
d
(xd1 , xmax
, ..., xd|V|
) det Θ − tr(SΘ) − ρ||Θ||1
2Θ
D
|V| |V|
D
1# d
ln ∑
p(Θ,
µ) = log det Θ −
(x − µ)T Θ(x
2
µ,
µ d − µ) + const
=∑
ΘΘ
– ここで はL1ノルム項
DΘ!
2
! j |Θiji j | # 2
||Θ||11 " |V|×|V|
µ
d
i
i, j=1
L(β, η) :=
ln p xd |β, η
L1正則化イメージ
15
D
d=1xd
D d
(4.7)
Θ
ΘD2 D
D 目的関数の等高線
D
) "
* ηϵ ") "
* η ") "
*
1
1
1
T
d xd = (xd , xd , ..., xd ) d 2
d
d 2
=β
x
−
(x
)
−
(x
−
x
)
2
i
j
(4.31) 2 1
L1
D
D |V| i
2
D
d=1
2
i∈V
(i, j)∈E
d=1
制約なし時の最適解
d=1
µ, Θ
1
N4.3.2
− β T Θ−1 β − ln det η + const
L1ノルム正則化時の最適解
2η
2
15
d dold
d
old
p(x
|y |y
,uθ)
=
p(x
, θ)
d
d
j∈∂(i),Ω
j∈∂(i),Ω
1
1
29
• に対して，正則化項を加えた最適化問題を解く
GGM
x
D
D d
•
(4.29a)
−1
1
Θ
d
d|
" η" " η "
#T #T " "
## ##
det
ΘuΘ
d
η|U
det
d
p(xd |y d , θ)η !
d d%
$ !
%
oldu exp
!
" exp
# du x−$duµ−
(4.28)
d xdu x
−udµuN
(4.28)
d UΘ
d
η|β
, ηold
)−−12−x
∂Q(β, η|β u, ηu ) =∂Q(β,
(4.27)
uΘ
U −uµ
1udµ!
1!
1
1 Θi j = 0
d|
1 (2π)
|U
|Ud |
2
(2π)
Ed [zi z (4.29a)
−
−
(ϵ%+ |∂(i)|
Ed [zi 2 ] + 2 β T Θ−1 β
$! ∝
Ed [zi ] − Θ ∝!
β
j ]!
はclosed
formで導出可能
d !
"2η 2
#2
i
D
D
2η
η
η
D η ϵ ∂η d
∂βi
d
(i,j)∈E
d
p(xdu |y d , θ) exp
βi (xdu )i − d
(xu )i −
(ydi − (xddu ) j )2 −
(xdu )i − (xi∈V
u) j
2
2
2
d
d
d
d
i∈U
i∈U
(i, j)∈Ω1
(i, j)∈Ω3
&
d
(4.29b)
" η!
" !
#T
"
##
η|U | det Θ
$
%
$
%
ud
old old
d d
d!
d
!
!
!
Fridman et
d
d
∂Q(β, η|β , η )
x
−
µyudd Θ2Ud xu −1µud T −1 (4.27)
(4.28)
dexp −
1 p(xu |y , θ) = N 1|Ud | mi m:=β
1
u
+
J
y
:=β
+
J
i
i 2
j E
j [z ] +
∝
Ed [zi z j ] − (2π)
−
(ϵi + |∂(i)|
β Θ β
d i
xd
2
p(x|µ, Θ) :=
exp − (x − µ) Θ(x − µ)
• 多次元正規分布 の
Z(Θ)
2
尤度関数
(4.2)
4.3.2
3
old
i1
! 1
"
exp − (x − µ)T Θ(x − µ)
Z(Θ)
2
1
Q(θ, θ old )
"
#
(4.27)
(4.26)
)
• E-step
M step Q(θ|θ
∂Q(β, η|β , η )
1 ! (4.27)
$!
% −1 β
∝
E [z ] − Θ
d !
!
!
old
η ϵ max
η
η D " d d i d #2
i
∂β
d d
d θ̂ = arg
d
d
d
2
i
Q(θ|θ
)
– Q関数を最大化する
d (x ) −
p(x |y , θ) exp
β (x ) −
(y − (x ) ) −
(x ) − (x )
old
Θ = Σ−1
µ := Θ β
3.2
3.2 Graphical
η Lassoの概要
Q(θ, θ old )
(4.25)
ln p(z d |θ)
z
(4.25)
u u
Estep
Mstep
dold
観測リンクydが与えられたもとでの未観測リンクx
の事後確率
2
GGM
µ
p(x|µ, Θ) :=
4.4
27 27
d "
d #d
d
=ηϵ ! Estep
ln p(z
|θ)p(x
|y2 , θ old
Mstep
η !
1 )dx
d2
d ud
T u −1
(4.25)
xd xd
⎧
⎪
Kataoka et al.
∂(i)
D
D
⎪
⎪ϵ +d |∂(i)|
i ∈ Ud "d d d "
ln
|θ)
⎪
ln p(z
|θ) |Θ)
Q(θ|θ old⎪
)⎪ =z z d
...
lnp(z
p(z
p(xdu |y d , θ old )dx1u dx2u . . . dxD
データ欠損のためEMアルゴリズムを利用
⎪
u
⎪
xu1 xu2
xuD
27
⎪
d=1
d=1
⎨ !!!
!
!
" " D d #2 #2 1 1 D
!
!
!
d
ηϵ
η
ηϵ
η
Θ
:=
|V|
d
2
|V|
⎪
2
u T z dT −⎪
d d
d"
d −1# d d (i, j) ∈
d d or
i)T"
∈T−1Θ
Ωβ−13−β − ln ηln+ηconst
E step
ln p(z
|θ) |θ)
=β
zi z−
z3j zddj−d(d−j, β
Θ
ln p(z
= β z⎪
−
−
zΩ
β
+ const
i
dzi −
d d 2d
i −
old (4)
1
2
D
⎪
2η
2 i∈V . . ln
2 (i,j)∈E
⎪
p(z
|θ)p(x
, θ2ηold )dx
(4.25)
Q(θ|θ old ) =
.2 (i,j)∈E
ln
p(z
p(x
u |y |Θ)
u u |y ,2θ )dxu dxu . . . dxu
⎪2= i∈V
⎪
– Q関数
d
D
⎪
du1d xu2xu
d
x
x
u
⎪
d=1p(z |θ)
d=1
z
ln
⎪
⎪0# !
(4.26)
(4.26)
otherwise
⎩
– 完全データの対数尤度関数
ln p(z d |θ) = β T z d −
j
i= j
⎪
GGMGGM
⎪
– 道路ネットワークは他のリンクとたかだか数本しか (4.19)
x
⎪
⎪
⎨
接続していないので非常にスパースな行列を仮定している
Θ = (i,
Σ−1j) ∈2 E or ( j, i) ∈ E
Θµij = ⎪
−1
⎪
⎪
⎪
⎪
– モデルのパラメータ数はたかだかV+2
(オリジナルはV + V2/2)!
⎪
4.1
⎪
⎪
⎪
⎪
⎪
otherwise
⎩0
3.2
{β, η}
θ old
⎧
構造化GGMのパラメータ推定
Estep
Q(θ, θ )
⎪
⎪
!
⎪ ! !
i
4.1
(4.19)
と変形できるのでこの式は多次元正規分布である
GGM(4.11)
Θ
4.2
GGM
α
old
•
•
!
#
ηϵ "
η "
3.1exp構造化GGMの概要
βx −
x −
(x − x )
⎪
⎪
2
⎪
• 4.1精度行列の0成分
⎪
ϵ + |∂(i)|
⎪
⎪
p(xu |y, θ)
0"Estep
Estep
µ
4
(4.27)
y
• 3.実データから精度行列の構造を推定するアプローチ
GGM(4.24)
Dempster et al.
EM
– 全ての要素について推定し，推定の過程で0を増加
Θ
2
(i, j)∈Ω3
EM
(4.15)
GGM
i
2" #i∈V
∞
GGM
!1
! 21 (i, j)∈E
"
T −1
Z(β, γ, α) = exp β
Θ
β
exp
− (x
− µ)T Θ(x
(4.16)
• 交通状態xを表現する確率モデル
" − µ)# dx
!
#
η"
2!
2
−∞
2 "
"
! −
#
= exp βx
ϵ
+
|∂(i)|
x
+
η
x
x
(4.20)
i
j
ηϵ
ηi
T 2
2
p(x|β, η) ∝ exp β(3.2)(3
x −i∈V
x2i −
(xj)∈E
(4.19)
(2)
i − x j)
(i,
(2))
2 i∈V
2 (i, j)∈E
! η
η T −1 #
%4
!
"
T
%
ε + ∂(i)
(x 1−βµ)
−(2π)
µ) +
β Θ
i=γ,
=exp
j!α) =−exp
T Θ(x
−1
N det(Θ
−1 ) β
'
Z(β,
Θ
β
(4.17)
2
2
1
β ' −1
η
µ2 ≡ Θ−1β ∂(i) はリンクiと接続するリンク集合
(i, j) E!
Θij ≡ &
η
'
0
otherwise!
(4.16)
(4.17)
'
ϵ
(
とすると
4.1
$
!
" #
N
!
1 det C
1η
η
T T
4.2(4.19)
GGM
p(x|β, γ,
α)(4.11)
= η)%=
exp
−− (x(x−−µ)µ)
Θ(x
− µ)
(4.18)
ηϵ
p(x|β,
exp
Θ(x
−
µ)
(3) γi
N
22
(2π)−1 )
(2π)N det(Θ
G(V, E)
%
#2
η ! d
η ! " d
d
2
d
(yi − (xu ) j ) − y
(xu )i − (xu ) j
2
2
d
d
ln p(z)
ηd ϵ !
d
∞
4–2
(4.19)
z
y Ωd
(i, j)
隣接する道路同士のみ値をもつ精度行列を定義
3
ln p(z)
p(xdu |y d , θ)
z
23
! 1 $
"
1$ 2 $
Z(β, γ, α) =
exp − (
βi xi −
γi xi +
αij xi x j dx
2
2
−∞
i∈V
i∈V
(i,j)∈E
T d
d
#
xi
Θ1
al.
Graphical Lasso
(4.2)
µ
(4.21)
Θ−1 − S − ρ Γ = 0 L1
(4.31)
Σ = Θ−1
4.3.2
W
Θ,W
Σ = Θ Lassoの概要
W
3.2 Graphical
!
−1
"
!
"
30
30
30
(4.33)
!
4.4.2
Θ,W
30
GL
(4.21)
"
W11 w12
S11 s12
11 θ12
• Θ
L1正則化は重要でないパラメータを0に追いや
Θ= T
,W
Ssign(Θ
= i jT) Θi j = 0
Γ = Θi j !T0
Γi, j, =
Γi j ∈ [−1,(4.34)
1]
θ22"
s12
l.
Lasso
! θることができ，スパースな解が得られる
!w12 w22 "
! s22 "
12Graphical
(4.32)
Θ11– モデラーが仮定せず，データからスパースな解を得る
θ12
W11 w(4.31)
S11 s12
12
Θ= T
,W =
,S = T
(4.34)
T
θ12 , w12 , s12 θ – しかし，L1ノルムは微分不可能なので扱いづらい
θ
w
w
s
s
22
22
22
12
12
12
, w22 , s22
Θ−1 − S − ρ Γ = 0
θ12 , w12 , s12 θ22
• 共分散構造問題に対して，データのノイズに対
して安定した解が得られるアルゴリズムとして
Σ = Θ−1
W
Θ,W
(4.33)
GL
θ22 , wFriedman
et al. (2007)がGraphical Lassoを提案!
22 , s22
S
(4.33)
β
w12 β ∈ R
|V|−1
(4.33)
S
SS S
(4.34)
# $ Θ = θ12T
∂
1
1/2
• 本研究でも観測された道路リンク交通状態から
W β − b + ρ||β||1 = 0
(4.35)
s12
∂β θ122, w12,11
リンク間の共分散構造の推定にGLを利用
#GL$
%2
&
θ22 , w22 , s22
∂
1
1/2
L1
β =(4.35)
W β − b + ρ||β|| = 0
∂β 2
b=
(4.33)
11
GL
w12(4.35)
− s12 − ρ(4.31)
γ12 = 0 Θ
(4.34)
(4.36)
(4.33)
T
12
i,j
(4.31)
(4.31)
(4.31)
ij
Θi j i j= 0
ij
Γi jij∈ [−1, 1]
(4.31)
Θ
ij
(4.32)
(4.32)
(4.32)
∂
(6)
Γ=0
ln p(Θ) = Θ−1 − S − ρρ Γ
∂Θ
−1−1 −1
ΘΘ
−
S
−
ρ
Γ
=
0
==
00
Θ− S
−−
S ρ− Γ
ρΓ
• ここでSは標本分散共分散行列，Γは以下の行列
−1
Σ
=
Θ
W
%' sign(Θ )
if Θij ≠ 0# −1−1 −1
ij
ΣΣ=Σ
W
Γ ij = &
=Θ=
ΘΘ
WW
(' ∈ [−1,1]
(4.32)
if Θij = 0#
W11
w T12
GL
GLGL
GL
31
31
w22
Graphical
Lassoの導出
L1 L1
−1
θ12 = −θ22 W11
w12 = −θ22 β
β β
ββ
L1L1
−1
β = W11
w12
(4.36)
−1/2
β ≡ W11−1w12 ," b ≡ W11−1/2 s12
−1−1 −1 • 新たな変数を定義
|V|−1
|V|−1
(4.36)
−1/2−1/2
|V|−1
W
w
β
∈
R
b
=
W
s
W
ww12
β
∈
R
b
=
W
s
12
12
12
−1/2
−1
W
β
∈
R
b
=
W
s
11
11
−1
|V|−1
11
11
12 β ∈ R
β = W bw=
(4.36)
11
12 W 11 s 12
W w
12
(4.34)
(4.34)
(4.34)
(4.34)
12
# $ θ = −θ%2 %W
& & −θ β
−1
∂# #∂$1 #$ 1 $ 1/2
% 2 11 w&12& =
12
22
%
2 222+ ρ||β||
∂
1
1/2
W
β
−
b
1/2
∂ 1 W
1 1 ==00
W
β b− b + ρ||β||
+ ρ||β||
1/2
11
β
−
=
0
11
1
2
∂β
W
β
−
b
+
ρ||β||
=
0
∂β 2 11
1
∂β∂β2 2 11 θ12 = −θ22 W11−1 w12 = −θ22 β
11
(4.33)
(4.33)
(4.33)
(4.33)
Θ,W
Θ,W
Θ,W
Θ,W
!
"-1*をWとし，以下のように分割
!
"
!
"
• 上式の最適解Θ
Θ11 θ12
W11 w12
S11 s12
31
31
(4.38)
(4.38)
(4.35)
(4.35)
(4.35)
(4.35)
(4.38)
(4.38)
31
βββ===
β=
β=W w
(4.36)
• βを用いて式(7),
(8)を以下のように変形
(4.35)
(4.34)
(4.33)
W11 β − s12
−
ρ γ12 = 0
(4.35)
(4.34)
(4.33)
(4.35)
(4.34)
(4.33)
11
−1
11
(4.35)
12
11
12
W11 β − s12 −
• 式(6)の右上ブロックから式(7)が成り立つ
W11
ij
θ12 = −θ22 W11−1 w12 = −θ22 β
−1/2
W11
s12
Graphical Lassoの導出
Γi, j i,=
sign(Θi j )i j
j
Γij ∈ [−1, 1]
Γ Γ= sign(Θ
Γ Γ ∈ ∈[−1,
Γ Θ Θ! 0! 0
= sign(Θ) ) Θ Θ= =0 0
[−1,1]1]
(4.31)
(4.32)
L1
正則化付き対数尤度とGL
ΓΓ
(4.33)
(4.33)
(4.33)
(4.33)
30
L1
β=
# $
%2
&
∂ 1
1/2
(4.35)
(4.34)
(4.33)
W
β
−
b
+
ρ||β||
=
0
(4.35)
1
Γ
Θij ! 0
Γi, j = sign(Θ
Θij = 0
Γij ∈ [−1, 1]
11
ij )
∂β 2
−1/2
|V|−1
β∈R
b = W11 s12
β
L1
β=
• 正則化項付き対数尤度関数の最適化が (4.31)
(4.32)
β
=
W11−1 w12
.21)
L1
−1/2
−1
|V|−1
W
w
β
∈
R
b
=
W
s
L1正則化付き回帰問題に帰着できることを示す
12
12
11
11
(4.35)
(4.34)
(4.33)
Θi j !
0
ij
Θij = 0
" " ,"S =
!! !
"" "
" =! ! !
Θ =!Θ!ΘT!Θθ θ" θ" , W
T 11
w
ST11ss1212
WW
ww
SS11s11
12 12
11
11W
1212
θ111211 1112
θ22
w
w
ss2212
22,12
12
12
,
W
=
,
S
=
Θ=
,
W
=
,
S
=
ΘΘ
==
,
W
=
S
=
Tθ T θ T θ θ
T Tw T w w
s22s22
θ12
ww
w
ssT12T12sT12s22
1222 22 22
12 θ
1212 12 2222 22
θ12 , w12 , s12
w
w
,12s1212, s12
θ12θ,12w,θ12
– 12,12,s上記の分割は各行列から1列のみ取り出している
θ22 , w22 , s22
, sw,22s2222, s22
, 22
w
22,22
θ22θ,22wθ
w
"
!
"
!
"
θ12
W11 w12
S11 s12
,
W
=
,
S
=
%θ2 22
&12T w22
w
sT12 s22
1
Γi, j = sign(Θij )
• 正則化項付き対数尤度関数をΘで微分
– 最適化問題をL1正則化項付き回帰問題に帰着!
!
GL
Θ11
Θij ! 0
Γ
W11 β − s12(4.34)
ρ Wγ
=s120−−ρ ργ12γ12= =0(9)0
11
12β −
(4.33)(4.39)
(4.39)
(4.39)
(4.39)
Θ−1
θ22 > 0
sign(θ12 )
∂
θ12 = −θ22 W
(4.38)
Θ w12 = −θ22 β θ22 > (10)
0
sign(θ
(6
)
12 ) =
Γ=0
(4.33)
W Θln=p(Θ)
I = Θ−1 − S − ρρ Γ
(4.32)
Θ 11
θ22 > 0
sign(θ12 ) =
∂Θ
w12 − s12 − ρ γ12 = 0
(4.36)
−1 −1
w12 s− s−
−ρ γ =0
(4.36)
w1212) )==−sign(β)
(4.36)
(4.36)
−sign(W
−sign(β)
(4.39)(4.39)
11 11−1w
(7) "
12 −
γ12 = 0
(4.36)
Θ−sign(W
θ221212−12−ρ>ρργγ120γ1212=12==000
sign(θ(4.36)
) =
"!
" ! w12 − s12 − ρ
!
"
12
−sign(W
w12 ) = −sign(β)
(4.39)
ww
12 − s12
11
•
元の最適化問題の見方を変えると
T
w12 Θ11 θ12
W11 Θ11 + w12 θ12 W
θ
+
θ
w12
I
0
11 12
22
!
"
"
"
W Θ =Σ
I = Θ−1
=
(4.37)
W = 0T Θ,W
TT
W
Θγ=
I ∂∂∂ ! 111ββ
T
T
T
T
T + ρ||β||
T T s12
−
ρ
=
W
β−β−β−
β
−1
1
w22 θ12
θ• 22WΘ=Iより以下が成り立つ
θ12
W + θw
w12
θ + w22 θ22
1 "
W11W
β1111−ββs−W
−
ρ=
W
Θ
=
I1212=
W
−W
s12
−
ργγ
=
βT W
β11
sβ
12
1111
12 +sρ||β||
12s
12
12 + 1ρ||β||
1
Θ
I
w12 ) = −sign(β)
(4.39)
2
∂β
!
"!
" 12!
" ! −sign(W
∂β 2
WΘ = I
w12
w22
W Θ = I W11
"!
T
w12
w12
w22
T
Θ11 θ12
W11 Θ11 + w12 θ12
W11 θ12 + θ22 w12
I 0
=
= T
T
T
T
T
θ12 θ22
θ12 W + θw12
w12
θ + w22 θ22
0 1
11
(4.37)β =
"!
" ∂β! ! 2##
" !
" " "
−1
T $2 $2 $2
W11
w12 ! ! !W11 "w
"!!12 Θ(4.36)
" !! ∂∂ !W
" 1!−1! 2−1
! 11# Θ1/21/2
+ wW
Wβ11TβθsT12s++β+θTβ
I "0+" ρ||β||
1/2
Tw12
1/2
11 " "θ12! =
11ββ
12
22
TTθ
∂ 11Θ
1W
! W
"
!
" 1−"W
=W
W+
s1/2
s−12
s1212
s12
1/2
w
Θ
θ
w−−Wθ
W
θ 12+12θT w12
Is s+102"ρ||β||
12 − −
T !W
−11 2 1
" !
" !
"
T
Θ11 θ
W"11 Θ11 +! w12 θ12
W
I W011 β − s12 − ρ
! 12 – 右上ブロックから
" 11 θ12 !+ θ22 w12"
(4.37)
Θ =θ T
W11T w12 T
S11 s12 = T
T
θΘ
θ 11 12 θ,12
W
w
θ= + w
0 1 (4.34)
W
=+ θwT22
,S
22 θ22
(8)
W
0
12 = 22T
12wW
12
11 θ12 + θ
12 11=
T
=0
θ12 θ22
w12 w22θ12 + θ22w12 s
s22
12
θ12 , w12 , s12
=
"
11
120
=
=1112 −
(4.37)
12
11 Tθ12
12
112Θ
12
11
12
22
1111
11
W1111w
w
W
+w
w
W
θ
+
θ
I
Tθ"
12
11
11
12−
11
2212w12
=
W
β
W
s
−
β
s
+
β
s
s
+
ρ||β||
2
∂β
2
2
∂β
T 1212 ΘΘ11
T11
T11W
T12
T0 W
!
12
1
12
W
θ
W
Θ
+
θ
θ
+
θ
w12
I
=
=
(4.37)
12
11+
11 11 T
11 T w 12 w2211 T θ 12 θ22
11 T 2
12 θw
12 θ +22w22 θ22
θ11
= T0 2 1 11(4.37)
(4.37)
T12
12θ == ∂β
12+ w θ
#W
$2$12
"w
#12 W
2
T
T
T"θ
wT∂ 121
w22 θ
θ!!T1211W
+
θw
w
22
Tθ∂∂Tθ
Tθ12 θ
T 12
T2 12
+
θw
w
θ
+
w22θ2222θ2222 = 00T0T11 1(4.40)
1/2
22− β=
1/2
212
!
#
$
"
θ
W
+
θw
w
θ
+
w
12
12
12
2
W
β
−
b
+
ρ||β||
=
0
γ12 w
=w12T 1212 ww2222β TθW
β
s
+
ρ||β||
22
22
=
W
β
−
b
+
ρ||β||
=
0
(4.40)
(11)
1
11
12
1
12
12
12 1
∂β
1/212 = 0
W11 β −
s∂1212221− W
ρ1111γ
(4.39) (4.40)
∂β 2
= ∂β
β − b + ρ||β||21 = 0
11
∂β
2
! #
$
"
2
(4.35)
βに対するL1正則化付き回帰問題
(4.35)1/2
∂ 1
1
1/2
=
W11 β −(4.35)
W11 s12ΣW11 θ−12β+TθWs2212w12+=β0T s12 − Ww11−1 s212 β+ ρ||β||1
Θ
θ
>
0
sign(θ
) =
12
W11
+ θ22 w
0
22
12β
2
∂β 2
Σθ
W12 =
w12
θ12
θw
12
22 w
WW
θ12
+ +θ22
==
00
1111
12 12
! #
$2
"
L1
β
Σ 2 (4.35)
w12
β
1
−1
L1
(4.35)W
1/2
−sign(W11
w12 )== ∂
−sign(β)
(4.39)β
W
β
−
b
+
ρ||β||
=
0
(4.40)
−1
1
11 w12
β=W
w12
wii = sii + ρ
Graphical Lassoの導出
• 以上より，L1正則化回帰問題を順次解く
step. 1 初期値をW = S + ρIとする
step. 2 Wを分割し，式(11)をβについて解く．
w12 = W11β̂ を用いる
最適解 β̂ が得られたら，
ŵ
ことにより 12 を得る
step. 3 step.2を各列について繰り返し，
Wが収束したら終了
本研究による拡張
4.4
• 実際に得られるデータは未観測リンクを含む
– Graphical Lassoをそのまま適用することはできない
4.4.1
• EMアルゴリズムを適用
– Estep：対数尤度関数の期待値を計算
(4.2)
Q(Θ | Θold ) =
w12
W11
∫
xu
ln p(x u , y | Θ)p(x u | y, Θold )dx u
– Mstep：GLの枠組みでL1制約付き対数尤度最大化
w22
Θ∗ = arg max log det Θ − tr(SΘ) − ρ||Θ||1
w T12
(
Θ
• GLがWを正則に保ちつつ更新していくことは
Mizumder and Hastie (2012)に示されている
!|V|×|V| Θ ← Θold
– 収束していなければ としてEstepへ
||Θ||1
i, j=1
|Θi j |
(4.7)
4. バンコク中心部でのケーススタディ
• バンコク中心部を対象としてネットワーク作成
– 道路リンク数：1183個
– 平均リンク長：64m
– MVNのパラメータ数: 2*1183 + 1183*1182/2
• データセット
70万!
Θ
バンコク中心部の日常(4.31)
Θi j = 0
L1
4.3.2
Fridman et al.
Graphical Lasso
– 2013/9/1-7, 10/14-11/5
の30日間のプローブデータ
14)
– 6:00∼20:00を抽出
– マップマッチングし，
道路リンクごとに 5分間平均リンク速度を算出
– データ数は5040
– 各データの平均欠損率71％
(=未観測リンク数/1183)
GL
GL
5.1.3
5
41
バンコク中心部のリンク欠損率
道路種別ごとの平均速度の傾向
3
43
(
(
5–5)
幹線道路の例
700
(
600
1000
700
500
700
300
600
200
500
100
400
400
300
200
200
0
1
10 2 20 3 30 4 40 5 50 6 60 7 70 8 80 9 9010 10011
100
speed (km/h)
100
0
0
1
10
– 5–5
2
20
3
30
4
40
5
50
6
0
60 7 70 8 80 9 90 10 10011
0
1
10 2 20 3 30 4 40 5 50 6 60 7 70 8 80 9 9010 10011
speed (km/h)
140 – 5–4
speed (km/h)
細街路の例
– 5–5
120
100
freqency
43
600
400
800
freqency
freqency
900
3000
バンコク中心部は
同一リンクであっても
100
分散が大きい傾向
140
80
5–7
60
120
freqency
40
20
高速道路・幹線道路はプローブ観測率高い
高速道路の例
5–6)
500
freqency
0-5%
5-10%
10-50%
50-100%
5–4)
0
0
1
10 2 20 3 30 4 40 5 50 6 60 7 70 8 80 9 9010 10011
speed (km/h)
– 5–2
– 5–6
80
60
40
20
0
0
1
10 2 20 3 30 4 40 5 50 6 60 7 70 8 80 9 9010 10011
speed (km/h)
400
350
5. 精度検証方法
– 5–6
予測前(実観測データ)
• 8-fold クロスバリデーション
–
–
–
80 km/h over
60-80 km/h
40-60 km/h
20-40 km/h
0-20 km/h
300
5040個のデータを学習用(4410)＋検証用(630)に分割
リ 250
学習用データ：交通状態予測モデルのパラメータ推定に使用
ン
検証用データ：モデルによる速度の予測精度評価に使用
ク 200
数 150
• 検証方法
– 学習・検証用データに真値がわからない道路リンクが存在
100
– 検証用データを未観測リンク率が8割になるようランダムに欠損
50
– 欠損部を予測し，欠損させた道路の真値とその予測値を比較
0
• 精度検証イメージ
0 1 10 2 20 3
検証用データ
観測リンク
30
4
40
5
50
6
60
7
70
8
80
9
90
10100 11
欠損率(%)
未観測リンク
ランダムに
– 5–3 欠損割合を8割に
推定された
モデルで補間
欠損させた部分は
真値がわかっている
ので，予測値と比較
9月1日 13:55-14:00 データの欠損率を8割としたデータ
予測精度検証結果
予測後(実観測＋予測データ)
80 km/h over
60-80 km/h
40-60 km/h
20-40 km/h
0-20 km/h
• 真値と予測値の比較
9月1日 13:55-14:00 予測結果
• 予測精度
GGMと本手法の比較
6. GGMが仮定する共分散構造
上位10%
上位20%
上位30%
対象リンク
46
• 計算時間
計算時間(hour)
30
GGM: 25時間42分
25
20
15
10
5
0
0.1
0.05
0.01
正則化パラメータρ
0.005
0.001
→ GGMと比較して学習時間が短縮し，高精度な予測が可能に
– 5–9
同心円状に共分散が小さくなる構造
Graphical Lassoが学習した共分散構造
上位10%
上位20%
上位30%
負
対象リンク
GLが推定した共分散構造の解釈に向けて
• クラスター順に分散共分散行列を並べ替え
1. 高速道路クラスター
2
分散共分散行列をk-means法により3つのクラスターに分類
1:高速道路クラスター
2:幹線道路クラスター
3:細街路クラスター
平均速度を用いていないにもかかわらず，
3つの道路種別をそれぞれ多く含むクラスターに分類された
空間的に離れた道路の相関もデータから推定
1
GLが推定した共分散構造の解釈に向けて
3
ODや経路選択行動を反映した学習
• クラスター分けされたネットワークの一部を抜粋
2. 幹線道路クラスター
3. 細街路クラスター
0.1 over
0.1 ~ 0.05
-0.01 ~ -0.02
-0.02 under
– 各道路種別間での関連性の強さは，種別ごとに異なる
– 並行路線を似た共分散構造を持った道路リンクとして学習
– ODや経路選択行動の交通特性をデータから学習
7. 本研究の成果と今後の課題
• 本研究の成果!
1. プローブ未観測リンクの補間手法の提案!
2. ネットワーク構造を仮定するGGMによるアプローチ
とデータから共分散構造を学習するGraphical Lassoの
アプローチから予測モデルの構築を行った!
3. 部分観測データに対してEMアルゴリズムを適用し， GGM, GLのEM拡張を行った!
4. 分析者が強い仮定を置かないデータオリエンテッド
なモデリングの方がより高精度な予測が可能である
ことが示された!
5. GLが推定した分散共分散行列の解釈可能性
• 今後の課題
– 時系列相関の考慮
– 多次元正規分布→潜在変数による混合分布
参考文献
1. Kataoka, S., Yasuda, M., Furtlehner, C., and Tanaka, K., : Traffic
data reconstruction based on Markov random field modeling,
Inverse Problems, 30025003, 2014.!
2. Freedman, J., Hastie, T. and Tibshirani, R., :Sparse inverse
covariance estimation with the graphical lasso, Biostatistics, 9, 3,
pp. 432-441, 2008.!
3. Mazumder, R., and Hastie, T. : The graphical lasso: New insights
and alternatives. Electronic journal of statistics, 6, pp. 2125-2149,
2012. !
4. Dempster, A. P., Laird, N. M., and Rubin, D. B., :Maximum
Likelihood from Incomplete Data via the EM Algorithm, Journal
of the Royal Statistical Society. Series B (Methodological), 39, 1,
pp.1-38, 1977.!
5. 花岡洋平, 原祐輔, 片岡駿, 桑原雅夫: バンコクにおける長期
間プローブデータを用いた交通状態推定とその検証, 第12回
ITSシンポジウム2014 Peer-Review Proceedings, CD-ROM,
2014.
© Copyright 2024 ExpyDoc
