Su, C.J., and Judd, K.L.: Constrained optimization approaches to

Su, C.J., and Judd, K.L.: Constrained optimization
approaches to estimation of structural models,
Econometrica, Vol. 80, pp. 2213-2230, 2012.
集中理論談話会 #15
2014/6/28(土)
D2 浦田淳司
論文目次・概要
構造推定にあたって，NFXP法(Rust(1987))は，不動点の繰り返し計算を
行うために計算負荷が高い．そこで，均衡制約条件付き数理計画問題(MPEC)
を用いて等価な定式化を行い，計算負荷を低減させた手法を提案する．
1. Introduction
2. MPEC Approach to Estimation
3. Single-Agent Dynamic Discrete-Choice Models
3.1 Single-Agent Dynamic Discrete-Choice Models
3.2 Maximum-Likelihood Estimation
4. Monte Carlo Experiments
5. Conclusion
+ NPLとの比較
++ TRcの式(論文とは関係なし)
2
背景：NFXP法(構造推定アプローチ)
Rust, J.(1988) Statistical Models of Discrete Choice Processes, Transportation Research Part B, Vol. 22(2), pp. 125-158.
の不動点を求める
EV
θ
の導入
⇒MPEC
1. Introduction
Outer
構造推定パラメータをθ求める
期待価値関数
ごθとの繰り返し計算が負荷
Inner
3
均衡条件，尤度の最大化
提案手法（MPEC)を用いた推定法を説明（2章）
観測可能な状態
選択結果 d
意思決定者i (1
)
構造パラメータ：コスト，利益などを示す
内生変数 σ：意思決定者の政策関数．構造パラメータの関数となる．
σは均衡条件を通じて，に拠る．
を所与としたときの，∑
,σ
0 (1)
を(1)式を満たすσの集合と定義する
≔ σ:
,σ
0
は∑ の要素であり，期待価値関数とし，一意に定まる．
また，∑ はと1対1対応する．
L , ; を観測データXの対数尤度とし，尤度最大化パラメータは次と定義
(3)
2. MPEC approach to estimate
4
MPECによる定式化
NFXPアルゴリズムでは，次を繰り返す．
outer loop: 尤度関数を最大化する構造パラメータを求める
inner loop: パラメータを所与とし，すべての ∈ ∑ の中から不動点解を求める
やりたいことは，
構造パラメータを推定する際に，内生変数σがから算出されたものであればよい
⇒均衡制約条件(1)を用いた制約付き最適化問題として定義する
1
max L(θ , σ ; X ) subject to h(θ , σ ) = 0
(θ ,σ ) M
定理1：(3)式と(4)式の等価性を示す
は尤度最大化の(3)式で定義され，(4)式の解は ̅ ,
∗
!"# max * , と定義する．
また， *
,
( )
'
∗
= * ̅,
となる．このとき，
とする．
̅ となる．
証明：
̅ , は(1)式を満足し， ∈ ∑ ̅ であるため，(3)式より，* , ∗
∗
∈∑
であるため，制約条件(1)を満たし，(4)式より， * ,
̅ となる．
モデルが特定され，解が１つであるため，
2. MPEC approach to estimate
(4)
∗
≥ * ̅,
．
* ̅,
．
5
NFXP法：Bus-Engine Replacement Problem
Rust, J.(1987) のバスエンジン補修/交換の問題を例にして，NFXP法を説明（3章）
1期
…
τ-1期
τ期
バスの状態
observed state x τ
unobserved state ε τ
意思決定d τ
1 (エンジンの交換)
0 (エンジン補修により運行)
τ+1期
…
ある期の効用関数u
状態xの推移確率（一次マルコフ性を仮定）
c:補修コスト
θ1: 補修パラメータ
RC: 交換コスト
θ2, θ3: 状態推移パラメータ
p ( xt +1 , ε t +1 | xt , ε t , d t ;θ 2 , θ 3 )
3. Single-Agent Dynamic Discrete-Choice Models
6
NFXP法：将来期待効用の最大化
将来の価値関数は，時間割引を考慮した効用の最大化となる
(6)
時間割引率　β ∈ (0,1)
最適意思決定は無限期間先までを考慮しており，期によらず一定である
(7)
次期状態　( x' , ε ' )
↑今期と次期の状態により，価値関数を定義
3. Single-Agent Dynamic Discrete-Choice Models
7
NFXP法：期待価値関数・選択確率
仮定：推移確率の条件つき独立性(CI)
p( x' , ε ' | x, ε , d ;θ 2 , θ 3 ) = p2 (ε ' | x' ;θ 2 ) p3 ( x' | x, d ;θ 3 )
CIの仮定を用いて，期待価値関数を次で定義する．
選択肢の期待価値関数（(7)式からεを除いて）
これを期待価値関数の定義式に戻す
(8)
εを極値分布とし，ロジット型の条件付き選択確率を導出（θ
-., θ/ , θ0 がパラメータ）
(9)
3. Single-Agent Dynamic Discrete-Choice Models
8
NFXP法： Fixed-Point Solution
(7)式と極値分布により，Fixed-Point equationは次となる
(10)
今期の状態xをK分割，次期の状態x’をJ分割して，表記．
(11)
(11)式に代入
(12)
※ この式が定義されている
で，結局この式に落ち着く．不動点の求解．
(13)
3. Single-Agent Dynamic Discrete-Choice Models
9
背景：NFXP法(構造推定アプローチ)
Rust, J.(1988) Statistical Models of Discrete Choice Processes, Transportation Research Part B, Vol. 22(2), pp. 125-158.
の不動点を求める
EV
θ
の導入
⇒MPEC
3. Single-Agent Dynamic Discrete-Choice Models
Outer
構造推定パラメータをθ求める
期待効用
ごθとの繰り返し計算が負荷
Inner
10
NFXP法：最尤法によるパラメータ推定
バス会社iの尤度
M社の全体尤度
(14)
対数尤度
(15)
-., θ/ , θ0 を求める
対数尤度最大化により，θ
(16)
3. Single-Agent Dynamic Discrete-Choice Models
11
MPECによる定式化
(13)式，(16)式を等価な均衡制約条件付き最適化問題と定式化．
（等価であることの証明は定理1より）
(18)
NFXPが不動点の算出プロセスを毎回解いているのに比べて，
Bellmanの等式を一度評価すればよいので，計算負荷は小さい．
3. Single-Agent Dynamic Discrete-Choice Models
12
計算精度の比較
・250回計算の平均をとり，パラメー
タの平均，分散を比較
・βが大きい場合は，NFXPと同じ結
果であるなど，両者の精度の差は
ほぼない
4. Monte Carlo Experiments
13
計算時間の比較
・MPECのほうがNFXPよりも計算時間は短い(AMPLで180倍以上，MATLABで3倍以上)
4. Monte Carlo Experiments
14
＋NPL(擬似最尤推定法)との比較
Aguirregabiria and Mira(2002)
・計算速度はパラメータが4つの場合
は，NPLは9倍速い
・MPEC型はNFPXと等価であるが，
NPLは漸近等価．
15
まとめ
まとめ
・構造モデルの推定にMPECを用いる手法を提案
・シングルエージェントの動的離散選択モデルで実証
・標準的なソフトウェアで計算可能であり，NFXPよりも早い
今後の課題
・動的離散選択ゲームにも適用可能かを検証する
所感
・コロンブスの卵的？
・等価性と計算性の両方をカバー
つづく?
5. Conclusion
16
TRｃの式1(Nested Dynamic Discrete Choice)
時間割引率
スケールパラメータ
選択確率（時刻t, Pair Set g）
exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ ) exp(σ ln RL ,t )
P ( d t | S g , t ; θ ) = P ( d t | L, S g , t ; θ ) P ( L , S g , t ; θ ) =
RL , t
∑L ' exp(σ ln RL ',t )
選択結果上位ネストパラメータ
ログサム
RL ,t = ∑ g∈L exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ )
(2)
υ (d t , S g ,t ) = ∑S υ ( S g ,t +1 ) p( S g ,t +1 | d t , S g ,t )
(3)
v(d t , S g ,t ) = u (d t , S g ,t ) + σε t (d t ) + ε t ( L) + βυ (d t , S g ,t )
(4)
(1)
推移確率
将来価値
g ,t
価値関数
利他差
Network Utility
t期でintra g内
のリンクが形成
形成あり効用
形成なし効用
同調性(集中性)

l g ,t  1
dam
dam
intra
intra
inter
inter

θ
δ
θ
δ
θ
S g ,t ( d t ) = m 
|
x
−
x
|
+
ln
k
+
ln
k
∑
4
j ,t
g ,t
g
g ,t
 N ij∈g 1 i ,t
 g 3
g


inter
S g ,t (d t ) = S g ,t (d t = (l g ,t −1 + 1, k gintra
(6)
,t −1 + 1, k g ,t −1 ))
1
u ( d t , S g ,t ) = S g ,t ( d t ) +
Ng
危険度
rain
5 t
u ( d t , S g ,t ) = θ x
(5)
形成コスト
dis
(7)
2 ij
∑θ x
ij∈g
root
(8)
Nest L
m
l g ,t
Ng
形成による利他差の縮小
g内の一定時間以内の形成数
g内のpair数
δ gintra , δ ginter
gがintraかinterか
k
intra
g ,t
,k
inter
g ,t
g内の形成数
xijdis
ij間距離
xtrain
当該時間帯の雨量
xidam
,t
iのダメージ
making pair
Non-make
Pair Set g
Intra A
Inter A&B
…
Pair ij
a1-a2
Intra B
a1-a3
a2-a3
a1-b1
a1-b2
a1-b3 … a3-b3
b1-b2
b1-b3
b2-b3
17
TRc の式
効用関数
Pair Cost
new pair
Pair Altruism
Majority Tuning 同調
time
previous pair
non-make
t-1
state
st −1
DP
time
Future Utility
Pair Utility
non-make
t
state
st
空間的準拠集団形成
time
non-make
t+1
Network Utility
state
st +1
Spatial Stochastic
Choice Set
Observed
time
non-make
t+2
state
Choice
st + 2
Latent
pair
Inter Pairs of A & B
a1
node
a3
b1
b2
nest
b3
Intra Pairs of A
Intra Pairs of B
a1
b1
A
a2
B
a) Dividing Basic Group
b2
a3
a2
b3
b) Dividing Intra and Inter Pairs by basic groups
++. Omake
18
TRｃの式2 (Tuning Effect)
選択確率（時刻t, Pair Set g）
exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ ) exp(σ ln RL ,t )
P ( d t | S g , t ; θ ) = P ( d t | L, S g , t ; θ ) P ( L , S g , t ; θ ) =
RL , t
∑L ' exp(σ ln RL ',t )
Network Utility
 1
S g ,t ( d t ) = m 
N
 g
= O1 + θ ' ln k g ,t
l g ,t
exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ )
RL ,t
∑θ
ij∈g
1
dam
i ,t
|x
−x
= exp(u ( S g ,t ) σ )

|  + δ gintraθ 3 ln k gintra
+ δ ginterθ 4 ln k ginter
,
t
,t


dam
j ,t
exp(βυ ( S g ,t ) σ )
RL , t
[
] O
= [exp(θ ' ln k )exp(O )]
= exp(θ ' ln k g ,t + O1 )
1σ
2
1σ
g ,t
1
[ ( ( ))] O O
= (k ) O O = (k )
= exp ln k g ,t
1σ
θ'
3
θ' 1σ
g ,t
2
θ' σ
3
適応度モデル
P(vi ) =
ノード12 のリンク形成確率
O2
2
g ,t
O3O2
η i ki
∑ jη j k j
19
ご清聴ありがとうございました．
20

Download Report