PowerPoint プレゼンテーション

Size: px

Start display at page:

Download "PowerPoint プレゼンテーション"

ときなこのえ
5 years ago
Views:

1 A nested recursive logit model for route choice analysis Tien Mai, Mogens Fosgerau, Emma Frejinger Transportation Research Part B, Vol. 75, pp , /06/19( 金 ) 理論談話会 2015#6 B4 三木真理子

2 目次 1. NRLモデルの強み 2. NRLモデルの定式化 3. 期待価値関数の計算方法と最尤推定法 4. ケーススタディ 5. アクティビティネットワークでの経路選択問題への適用 2

3 経路選択問題の目標と課題ネットワーク上の経路選択問題の分析には一般に離散選択モデルが用いられる 2 6 経路選択モデルを作るうえでの目標 1 すべてのパラメータを矛盾なく一貫して推定する 2 将来予測にも有効なものを作る経路選択モデルの難点 1 経路の選択肢集合が分析者にはわからない上にある OD ペアについてすべての可能な経路を列挙するのは不可能 2 経路の効用は互いに独立ではなく相関していると思われる目標を 2 つともクリアし難点を 2 つとも克服したモデルは NRL モデルのみ! 1 NRL モデルの強み 3

4 既往研究 ( 選択肢集合抽出型 ) 現存する多くの経路選択モデル : 経路の選択肢集合に基づいた経路選択モデル ( 例. Guevara and Ben-Akiva(2013a,b) GEV モデルと mixed ロジットモデル ) 難点 1 経路列挙の不可能性のため推定や適用の前に選択肢集合を抽出する必要がある抽出された選択肢集合に応じて選択肢の効用を調整する必要があるパラメータを矛盾なく推定することはできるが予測にどう用いたら良いかはまだわからない 1 NRL モデルの強み 4

5 既往研究 ( 選択肢集合抽出型 ) 難点 2 経路がリンクの重なりによる相関をもつことと向き合った経路選択モデル :link-nested logitモデル (Vovsha and Bekhor, 1998) 誤差項の相関を考慮したmixed logitモデル (Frejinger amd Bierlaire, 2007) 現状抽出された選択肢集合に基づいて効用を修正することなしに推定している選択肢集合からいくつか経路を抜いたり足したりするだけで推定値が変わる実際の選択肢集合がわからない現実世界で用いるには不向き? ただし先ほど示したように効用を調整することはできる 1 NRL モデルの強み 5

6 RL(recursive logit) モデル経路の選択肢集合を抽出することなく経路の選択確率を求める逐次的離散選択モデル : 選択者は次に進むリンクをマルコフ性をもつ確率的な過程で選んでいき結果的に経路の選択が行われる (link-based approach) (1にいる) 2 2に向かうリンク 3に向かうリンク 4に向かうリンクの中からどれかを選択 1 (4にいる) 5に向かうリンクか7に向かうリンクかを選択これを繰り返すこれはすべての可能な経路に対して MNL で経路選択を行うことと同等! 1 NRL モデルの強み 6

7 RL から NRL へということで RL モデルは 2 つの目標はクリアし難点 1 を克服したが難点 2 はまだ不十分リンクサイズ LS という指標でリンクの共有による経路の相関は考慮することはできるがリンクサイズ以外の要素 ( リンク旅行時間など ) が変化した場合 IIA 特性は残っているスケールパラメータを各リンクに固有なものとして与えることで IIA 特性を緩和 NRL(nested recursive logit) モデルネスティットロジットモデルと同様のアイディアなので nested RL モデル 1 NRL モデルの強み 7

8 ( 復習 ) Nested Logit model(nl) ー 2 種のスケールパラメータを使った選択確率 U dm = V d + V m + V dm + ε d + ε dm ε 1 ε l ε K V d : 目的地選択肢 d に特有な効用の確定項 U dm : 選択肢 (d,m) の真の効用 B 1 B l B K V m : 手段選択肢 m に特有な効用の確定項 1 j i N V dm : 選択肢 (d,m) に特有な効用の確定項 ε d : 目的地選択 d に特有な効用の確率項 ε dm : 選択肢 (d,m) に特有な効用の確率項スケールパラメータ μ の IIA ガンベル分布に従う V d = 1 ln μ m exp μ V m + V dm, ε d = max V m + V dm + ε dm V d として m P d, m = exp μ V m + V dm m exp{μ V m + V dm } exp μ d V d + V d d exp{μ d V d + V d } 1 NRL モデルの強み 8

9 スケールパラメータをリンク固有にする意義例としていくつかのネットワークで経路選択確率を出してみる簡単のためにリンク長のみを説明変数としているため経路の重なり具合は説明変数としては考慮されないリンク b のスケールパラメータを変化させそれ以外を 1 に固定した結果が以下 RL モデル ( すべてのリンクのスケールパラメータが 1) ではどの経路も 1/3 の選択確率 NRL モデルではスケールパラメータの違いによって選択確率に変化が起こっている 1 NRL モデルの強み 9

10 スケールパラメータをリンク固有にする意義ネットワーク例経路選択肢のネスト上のネットワークでリンク a のスケールパラメータを 0.5 リンク b のスケールパラメータを 0.8 それ以外のリンクのスケールパラメータを 1 とするここからリンク a1,a2,b1,b2 をそれぞれ取り除いた場合他のリンクの選択確率がどのように変化するかを見る 1 NRL モデルの強み 10

11 スケールパラメータをリンク固有にする意義ネットワーク例経路選択肢のネスト Probabilities with link removed Paths Original a1 a2 b1 b (+20%) 0.55(+1%) 0.56(+4%) (+151%) (+1%) 0.16(+4%) (+93%) 0.05(+20%) 0.05(+1%) 0.05(+4%) (+93%) 0.03(+15%) (+19%) (+93%) 0.07(+15%) 0.17(+6%) (+93%) 0.20(+15%) 0.18(+6%) 0.21(+19%) 1 NRL モデルの強み 11

12 スケールパラメータをリンク固有にする意義ネットワーク例経路選択肢のネスト Probabilities with link removed Paths Original a1 b3 f 1:[o,a,a1,d] (+12%) 0.54(+0.7%) 2:[o,a,a2,d] (+150%) 0.17(+12%) 0.15(+0.7%) 3:[o,a,a3,e,d] (+148%) 0.05(+11%) 0.04(-1.3%) 4:[o,b,b1,e,d] (+86%) 0.05(+90%) 0.02(-6.7%) 5:[o,b,b2,d] (+93%) 0.12(+91%) 0.06(+1.4%) 6:[o,b,b3,d] (+93%) (+1.4%) 結論 :IIA 特性は緩和され代替のされ方はネットワーク構造に依存する 1 NRL モデルの強み 12

13 経路選択モデルの比較経路選択モデルを比較する 4 つの視点 1 すべてのパラメータを矛盾なく推定できるか 2 将来予測にも有効かどうか 3 選択肢集合を限定する必要がないかどうか 4 経路の重なりなどによる効用の相関を記述できているかどうか選択肢集合抽出型 ( 従来の大多数 ) 1 のみクリア 4 は努力しだい RL モデルはクリア 4 は LS による部分的な解決にとどまる NRL モデルのすべてをクリア! ということで NRL を定式化していく 1 NRL モデルの強み 13

14 ネットワークの定義 G = (A, ν) : 方向を持つリンクで結ばれたネットワーク A : リンクの集合 ν : ノードの集合サイクルのあるネットワークでも OK それぞれのリンク k A について k の終点から伸びるリンクの集合を A(k) とするそれぞれの目的地 D について D からダミーリンク d を伸ばすことで吸収状態を表現この結果全リンクの集合 A は以下のようになる A = A {d} 2 NRL モデルの定式化 14

15 リンクの効用関数の定義あるリンク k の終点ノードにおいて次のリンクを選ぶときの原理効用最大化 k から a に移るときおよびリンク a の通過に関する効用 (IU) + リンク a を選んだ場合のリンク a 通過後から目的地まで経路の期待効用 (EU) あるリンク k の終点ノードで a A(k) を選択するとき IU: u n a k; β = v n a k; β + μ k ε a (1) EU: V d k; β = E max a A k v n a k; β + V d a; β + μ k ε a (2) v n a k; β : IU の確定項 ( ダミーリンク d 以外では負の値 ) ε a : IU の確率項 (iid ガンベル分布に従う ) β: 未知パラメータ μ k : リンク k に固有の確率項のスケールパラメータ ( 正の値 ) 2 NRL モデルの定式化 15

16 P d (a k) を求める P d a k = δ(a k) exp( 1 μ k v a k +V d a ) a A(k) exp( 1 μ k v a k +V d a ) ここで V d k; β = E より 1 μ k V d k = E よって a A k = ln( max a A k max a A k a A k v n a k; β + V d a; β + μ k ε a 1 μ k (v a k + V d a ) + ε a exp 1 μ k v a k + V d a ) exp 1 μ k v a k + V d a = e 1 V μ d k k (3) 左の結果から P d v a k +V a k = δ a k eμ d a V d k k 1 δ a k = 1 if a A(k) 0 otherwise この式は k, a A において成り立つ. (4) 2 NRL モデルの定式化 16

17 経路の選択確率 [k 0, k 1,, k l ] というリンクで成り立つ経路 σ が選択される確率は P d v a k +V μ a k = δ a k e d a V d k k 1 より P σ = l 1 i=0 1 v k μ e ki i+1 k i +V d k i+1 V d k i 5 ちなみに 2 つの経路 σ 1 = [k 0, k 1,, k l1 ] と σ 2 = [h 0, h 1,, h l2 ] の選択確率の比は P σ 1 P(σ 2 ) = 1 l 1 1 v k e μ ki i+1 k i +V d k i+1 V d k i i=0 1 l 2 1 v h i=0 e μ hi i+1 h i +V d h i+1 V d h i 複数の V d k がある確率の比にネットワーク全体が影響する IIA 特性はもはや保たれていない! 2 NRL モデルの定式化 17

18 NRL モデルの難しさ NRLモデルを実装するうえで困難なことが2つある 1 期待価値関数 V d k の計算非線形の行列計算再帰的に求める必要があるため計算負荷が高い効率的な求解方法の提案 2 最尤推定法尤度関数の定義とそのヘッセ行列を効率的に求められることを示す今回は触れません 3 期待価値関数の計算方法と最尤推定法 18

19 1 期待価値関数 V d k の計算 3 a A k exp 1 μ k v a k + V d a = e 1 μ k V d k について仮定より V d d = 0 よって (3) は以下のようにかける 1 V eμ d k k exp 1 v a k + V d a k A = μ k a A 1 k = d (6) ここで A A 行列 M d と A 1ベクトルz d を以下のように定義する v(a k) = δ a k e μ k, d V(k) zk = e μ k, k, a A 7 M d ka この z d を求めることで V d k を計算することを目指す 3 期待価値関数の計算方法と最尤推定法 19

20 1 期待価値関数 V d k の計算 z d の計算より 1 V eμ d k k exp 1 v a k + V d a k A = μ k a A 1 k = d z d M d k = ka zd μ a/μ k a k A a A 1 k = d (7) M d ka (6) z a d = e v(a k) = δ a k e μ k V(a) μ a この z d を繰り返し計算によって求める 3 期待価値関数の計算方法と最尤推定法 20

21 1 期待価値関数 V d k の計算 z d の計算 A A 行列 X(z) を以下のように定義する X z ka = z a μ a /μ k k, a A 8 このとき 7 z d k = a A M d d ka z μ a/μ k a k A 1 k = d は z = M X z e + b 9 b: A 1ベクトル. リンクdは1 それ以外は0 e: A 1ベクトル. 全要素が1 : 要素同士を掛け合わせる操作のようにかける 3 期待価値関数の計算方法と最尤推定法 21

22 1 期待価値関数 V d k の計算 z d の計算厳密解 z d は 9 z = M X z e + b を満たすこれを繰り返し計算で求める初期値を z 0 として z i+1 M X z i e + b 10 以上の操作で次のz i を求めるある閾値 γを決めて z i+1 z i 2 < γ を満たすまで計算を繰り返す (9) 式が解を持つ場合有限解の操作で必ず収束し収束の速さは z 0 に依存する RL モデルでの解 (μ k = μ k A と仮定した場合の解 ) を入れると速い V d k が線形の関数で計算できるため計算負荷が低く求められる 3 期待価値関数の計算方法と最尤推定法 22

23 1 期待価値関数 V d k の計算 z d の計算実際の V d k はパラメータ β の値に依存する最尤推定法で β を計算するたびに V d k も繰り返し解く必要がある閾値 γ を最初は大きめの値で設定し計算を繰り返すたびにより小さい値に更新していくことで計算負荷を減らす 3 期待価値関数の計算方法と最尤推定法 23

24 2 最尤推定法 Rust(1987) の Nested fixed point algorithm(nfxp) を使って逐次的離散選択モデルを推定する仕組み : 尤度関数の最大化を行うことでパラメータを推定する尤度関数の最大化をするアルゴリズムの中で先ほどのやり方で V d k を求める推定するパラメータ :β とスケールパラメータ μ k すべてのスケールパラメータをそれぞれ推定することはできないので μ k を β の関数 μ k (β) と仮定する観測された経路集合 (n=1,2,,n) について尤度関数 LL を定義すると LL β = = N n=1 N n=1 t=0 lnp(σ n, β) l n 1 μ kt (v n ( k t+1 k t + V n k t+1 V n (k t )) 3 期待価値関数の計算方法と最尤推定法 24

25 実ネットワークと使用サンプルスウェーデンのボルレンゲという街の実ネットワークで経路選択をしてみる ( リンク数 7459 ノード数 3077 交通量の増加による旅行時間の変化はないものと仮定 ) < 推定に用いるサンプル > 1832 トリップ ( 観測された経路のうちもっともリンク数の少ないもので 5 リンク ) 到着地ノード :466 個 OD ペア :1420 種類 37,000 回以上のリンク選択が行われているこれらを RL モデルと NRL モデル双方で推定双方についてリンクサイズ (LS) を考慮したものと考慮しないものの 2 種類のモデルがある計 4 種類のモデルで比較 4 ケーススタディ 25

26 リンク効用関数の定義 v RL a k; β = v NRL a k; β = β TT TT a + β LT LT a k + β LC LC a + β UT UT a k v RL LS a k; β = v NRL LS a k; β = β TT TT a + β LT LT a k + β LC LC a + β UT UT a k + β LS LS a TT a : リンクaの旅行時間 LT a k : 左折ダミー ( リンクaとkのなす角が40 以上 177 以下 ) LC a : リンク固有定数 UT a k :Uターンダミー( リンクaとkのなす角が177 以上 ) LS a : リンクサイズ ( 対象経路のODに絞った場合のリンクの期待フロー ) β は未知パラメータ初期値のみこちらが与える 4 ケーススタディ 26

27 IU の定義 < スケールパラメータ μ k について > すべてを未知パラメータとして推定するのは不可能 μ k をリンクの説明変数の関数として考える μ k > 0 より μ k = e λ k とおけて λ k = ω TT TT k + ω LS LS k + ω OL OL k TT k : リンクkの旅行時間 LS k : リンクサイズ ( 対象経路のODに絞った場合のリンクの期待フロー ) OL k : A(k) リンクkの終点ノードから伸びるリンク数よって IU は以下のように定義される u RL a k; β = v RL a k; β + με a u RL LS a k; β = v RL LS a k; β + με a u NRL a k; β, ω = v RL a k; β + e λ kε a u NRL LS a k; β, ω = v RL LS a k; β + e λ kε(a) 4 ケーススタディ 27

28 推定結果 Parameters RL NRL RL-LS NRL-LS βtt Rob. Std. Err Rob. t-test(0) βlt Rob. Std. Err Rob. t-test(0) βlc Rob. Std. Err Rob. t-test(0) βut Rob. Std. Err Rob. t-test(0) βls Rob. Std. Err Rob. t-test(0) ωtt Rob. Std. Err Rob. t-test(0) LS を確定項に入れたほうが尤度が高いリンクの共有具合によって経路の効用を修正するために導入された変数だがたとえ誤差項の相関を認めていたとしても確定項に LS を加えたほうが説明力が上がる ω LS と ω OL には説明力があり負の値フローが大きく続くリンクが多いほど誤差項の分散が小さい ωls Rob. Std. Err Rob. t-test(0) ωol Rob. Std. Err Rob. t-test(0) LL(β) ケーススタディ 28

29 推定結果 μ k は OL k のため離散的なピークを取る 1 を超えるものもわずかながらある Φ ka = μ a /μ k は 0 に関して対称な分布 4 ケーススタディ 29

30 将来予測の有効性検証の仕方 1 サンプルを 2 つに分ける 80% は推定に用いる推定されたモデルによる予測確率を残り 20% で評価する 2 残しておいた 20% を同じ大きさの 40 個のサンプル集合に分ける 3 それぞれのサンプル集合に対し当該サンプル集合以外のサンプルを使ってパラメータ β i を推定し以下の err i を計算することで予測の誤差を測る err i = 1 PS i σ j PS i lnp(σ j, β i ) err i はサンプル集合 i に依存する確率変数なので平均を用いる p err p = 1 p i=1 err i 1 p 40 尤度関数負の値尤度が高いと絶対値が小さくなる err i は小さくなる 4 ケーススタディ 30

31 将来予測の有効性 LS なしよりも LS ありのほうが RL モデルよりも NRL モデルのほうが予測制度が高い 4 ケーススタディ 31

32 まとめ NRL モデルの利点を確認 ( 経路列挙を行うことなく経路の相関を考慮したうえで経路選択モデルを定式化している ) 期待関数を求めるアルゴリズムを確認実ネットワークへの適用を行い説明力の向上と将来予測の有効性を確認 32

2014 BinN 論文セミナーについて

2014 BinN 論文セミナーについて内容論文ゼミは,BinN で毎年行なっているゼミの 1 つで, 昨年度から外部に公開してやっています. 毎週 2 人のひとが, 各自論文 ( 基本英語 ) を読んでその内容をまとめ, 発表議論するものです. 単に論文を理解するだけでなく, 先生方を交えてどのように応用可能か, 自分の研究にどう生かせそうかなどを議論できる場となっています. 論文ゼミ基本事項