Fundamental Seminar
vol.7
Huge set of alternatives & Multi Agent Simulation

2018.5.25
Fukuda lab
Noriko KANEKO
1

巨大選択肢集合の取り扱い，その前に行動モデルの構築〜交通手段選択モデルの場合〜① 選択肢の列挙｛鉄道、自動車、バス、自転車、徒歩｝←今日のお話② 選択肢間の相関や誤差構造を考慮し、モデルを選ぶ｛MNL,MNP,NL,MXL,,,｝③ 効用関数を各々定義｛𝑉 = 𝐵𝑡𝑖𝑚𝑒 ∗ 𝑡𝑖𝑚𝑒 + 𝐵𝑐𝑜𝑠𝑡 ∗ 𝑐𝑜𝑠𝑡 + ⋯｝←今までの基礎ゼミのお話④ モデルを推定する｛最尤推定法、シミュレーション推定法、ベイズ推定法｝
2

巨大選択肢集合の取り扱い，その前に選択肢の列挙• 交通手段選択モデル→割と列挙可能• 目的地選択モデル→列挙困難• 立地選択モデル→列挙困難

今日のテーマはこのあたりです！！

• 経路選択モデル→列挙困難

3

選択肢の設定方法① 全選択肢を分析する方法② サンプリングによる方法：ある確率分布に従ってランダムに少数の選択肢を取り出して，パラメーター推定に用いる方法③ 選択肢を集計する方法：数多くの選択肢をいくつかのグループに集計統合する手法④ 選択肢をカテゴリー分割する手法：選択肢をいくつかのカテゴリーに統合する方法

4

選択肢の設定方法～立地選択モデルの場合～① 全選択肢を分析する方法

すべての住宅を選択肢として扱う
短所；選択肢列挙が困難，すべての選択肢に特性値設定が困難，計算困難↓

限定的な選択肢しか有さないような場合には有効

5選択肢の設定方法～立地選択モデルの場合～② サンプリングによる方法

ある確率分布に従ってランダムに少数の選択肢を取り出してパラメータ推定に用いる方法
長所；①より効率的短所；IIA特性が成り立つことを仮定，サンプル選択肢の数が多くないと，歪みが生じる（注）各個人に対して｛選択したもの，選択しなかったものから１つ｝をサンプルし，選択肢集合とすることが多い．

6

選択肢の設定方法～立地選択モデルの場合～③ 選択肢を集計する方法

数多くの選択肢をいくつかのグループに集計・統合
𝑃𝑛 𝑖 =exp(𝑉𝑖𝑛 + 𝑙𝑛𝑀𝑖 )σ𝑗∈𝐴𝑔𝑛 (𝑉𝑗𝑛 +𝑙𝑛𝑀𝑗 )𝑀𝑖 :ゾーン𝑖内の個々の住宅の数,
𝑍𝑖 :ゾーン内の全住宅の平均特性を𝑍𝑖 ,𝐴𝑔𝑛 𝑡 :ゾーン𝑖の選択肢集合を𝐴𝑔𝑛 𝑡

平均効用の修正
選択肢要素数の重み

短所； 𝑀𝑖 は，利用可能面積などに置換できるが，分析の精度にあった客観的な値の設定が困難
7

選択肢の設定方法～立地選択モデルの場合～④ 選択肢をカテゴリー分割する方法

各カテゴリーに属する個々の選択肢の数は考慮しない(EX) 例えばどの寮を選ぶか？どの部屋かは考えない．
→かなり選択肢が限定されていて個々の特性が明らかな場合には有効
そうでない場合は③のほうが良い

8選択肢の利用可能性① ヒューリスティックに選択肢集合を作る方法…選択肢の利用可能性に制限を設けることにより選択肢集合を限定する方法
Ex)分析対象地域に境界を設ける，予算制約を設けるetc…
〇分析結果に大きな影響は出にくい
×経験的な面もある② 各個人の選択候補の情報による方法…アンケートで最終候補として考慮した選択肢を調査し，選択肢集合を作る
×回答そのものの信頼性
×長期的な予測には使えない③ 選択肢集合の生成確率を考える方法…選択肢集合が生成される確率と，選択肢集合から選択肢が選択される確率を考える④ 検討対象集合を考える方法…地域全域ではなく，鉄道沿線といった一部具体的な区画の検討を行う競合目的地モデル
9

選択肢の利用可能性③ 選択肢集合の生成確率を考える方法…𝑃𝑛 𝑖 = σ𝐵𝑘 𝑃𝑛 𝑖 𝐵𝑘 𝑃𝑛 (𝐵𝑘 )選択肢集合𝐵𝑘 から𝑖を選択する確率

ロジットモデル

選択肢の全集合𝐴𝑛 のすべての部分集合𝐵𝑘が生成される確率• 選択肢の部分集合を１つの選択肢として求める• 𝑃𝑛 𝐵𝑘 = ς𝑝∈𝐵𝑘 𝑅𝑝𝑚 ς𝑝∉𝐵𝑘 (1 − 𝑅𝑝𝑚 )𝑅𝑝𝑚 :選択肢𝑝の個人𝑛に対する利用可能確率→パラメータ推定が難しい④ 検討対象集合を考える方法…地域全域ではなく，鉄道沿線といった一部具体的な区画の検討を行う競合目的
地モデル．
exp 𝑉𝑖𝑗 𝑝𝑖 (𝑗 ∈ 𝑀)
𝑃𝑖𝑗 =σ𝑘 exp 𝑉𝑖𝑗 𝑝𝑖 (𝑗 ∈ 𝑀)
選択肢jが比較検討する選択肢集合Mに属する確率10

効用関数の推定と選択確率の導出①

ジョイントチョイス分析②

Nested Logit Model③

識閾を考慮したNested Logit Model④

連続型ロジットモデルによる方法⑤

選択確率の動学化

11効用関数の推定と選択確率の導出①

地域A

住宅タイプA

地域B

住宅タイプB

地域C

住宅タイプC…

…

②

ジョイントチョイス分析

地域n

住宅タイプnそれぞれ無関係な選択肢の全組み合わせを選択肢としてMNLを推定する方法

Nested Logit Model
地域A

住宅タイプA

住宅タイプB
住宅タイプC
地域B

それぞれ無関係な選択肢の全組み合わせを選択肢としてMNLを推定する方法

住宅タイプA
住宅タイプB
住宅タイプC12

効用関数の推定と選択確率の導出③

識閾を考慮したNested Logit Model
ロジットモデルの確率の定義に∆𝑈𝑖𝑛 = 𝑈𝑖𝑛 − 𝑈𝑜𝑛 ≥ 𝛿を加え，これを満たすとき選択肢𝑖を選択し，そうでないときは状態(0)のままであると仮定する．すると，選択肢𝑖の選択確率は
1𝑃𝑛 𝑖 =
1 + exp 𝑉𝑜𝑛 − 𝑉𝑖𝑛 ∗ 𝛿となり，定数項として推定可能となる．

④

連続型ロジットモデルによる方法
専属的な空間において，個々の地点を選ぶ確率に対して，各選択肢にIIA特性を仮定すれば，
𝑀𝑗 exp 𝑉𝑖𝑛
𝑃𝑛 𝑖 =σ𝑗∈𝐴𝑔𝑛 𝑀𝑗 exp 𝑉𝑗𝑛
ただし，ゾーン内の選択肢の数を𝑀𝑗 とする．確率密度関数は，exp 𝑉𝑖𝑛𝑓𝑛 𝑖 =‫ 𝑆∈𝑗׬‬exp 𝑉𝑖𝑛 𝑑𝑗𝑛となる．効用関数の説明変数が簡単な連続変数で表されるときのみ有効13効用関数の推定と選択確率の導出⑤

選択確率の動学化
立地選択行動に選択確率に時間要素を導入すること時間要素を考慮する方法．
∆𝑡の期間に住み替える効用を∆𝑡
𝑉𝑐𝑛 = 𝑉𝑜𝑐𝑛 + ln𝑡のように置く．𝑡は平均的な移転に要する時間，𝑉𝑜𝑐𝑛 は時間に関係しない平均効用．∆𝑡の間に𝑖から𝑗に住み替える確率は𝑃𝑖𝑗 ∆𝑡 = 𝑃(𝑐ℎ𝑎𝑛𝑔𝑒|𝑖, ∆𝑡) 𝑃(𝑗|𝑐ℎ𝑎𝑛𝑔𝑒, 𝑖)となる．

𝑖に居住していて∆𝑡の間に その条件のもと，𝑗を選択する確率
住み替える確率→理論提案であり，今のところ実用モデルとしては使われておらず．

14経路選択モデルに対する巨大選択肢集合の取り扱い
今熱い2つのアプローチ• ZDD( Zero-suppressed BDD )BDD: Binary Decision Diagram…ZDDと呼ばれるデータ構造を用いて，とにかく全てを数え上げるアプローチ（詳しくは基礎ゼミ9にて）• Recursive Logit Model…リンクベースで再帰的にロジットモデルを組むことによって，経路選択肢を列挙することなく，モデルを構築するアプローチ（今回はこちらを）全列挙（同じところを通らない）
2×2 ： 12通り
3×3 : 184通り
4×4 :
8512通り各ノードで，効用最大化するようにロジットモデルを繰り返す

15

Recursive Logit Model (RL Model)• Fosgerau et al. (2013)• Link Based Model• 旅行者が各ノードで，即時効用＋下流効用の和を最大化するように行動する

Path Based Model

Link Based Model特徴• 選択肢列挙の必要あり• 旅行者は，目的地までの一貫した効用を最大化するように行動する• 選択肢列挙の必要なし• 旅行者は，次のリンクから得られる即時効用と，目的地までの期待効用である下流効用を最大化する
ように行動する

長所• 説明変数を入れやすい• 選択肢列挙のコストがない• 動的計画法の枠組みに準拠

短所• 選択肢列挙が難しい• 変化するネットワークに対応しにくい• 下流効用を算出の計算負荷が大きい• 説明変数にNon link additiveな項（料金など）を入れにくい 16

Recursive Logit Model (RL Model)
即時効用

下流効用

𝐺 = 𝐴, 𝜈 : ネットワーク 𝜈 ∶ ノードのセット 𝐴 ∶ リンクのセット(𝑘, 𝑎 ∈ 𝐴)𝑘 ∶ 状態リンク 𝑎 ∶ kにおける行動リンク A(k) : kから出発するリンク𝑑 ∶ 目的地からのダミーリンク 𝐴ሚ ∶ 𝐴ሚ = 𝐴 ∪ 𝑑 Recursive Logit Modelの基本概念
𝑑
旅行者𝑛は，即時効用𝑣(𝑎|𝑘)と下流効用𝑉𝑎1(𝑎1 )の和を最大化するようにリンクを選17択していくRecursive Logit Model (RL Model)即時効用：次のリンクの効用
確定効用と確率効用の和
𝑢𝑛 𝑎 𝑘 = 𝑣𝑛 𝑎 𝑘 + 𝜏𝜀𝑛 𝑎𝜏 ∶ 𝑠𝑐𝑎𝑙𝑒 𝑝𝑎𝑟𝑎𝑚𝑒𝑡𝑒𝑟𝑒𝑥 𝑣 𝑎 𝑘 = 𝛽𝑇𝑇 𝑇𝑇+𝛽𝐿𝑇 L𝑇𝑎|𝑘 +𝛽𝐿𝐶 𝐿𝐶+𝛽𝑈𝑇 𝑈𝑇𝑎|𝑘𝐹𝑜𝑠𝑔𝑒𝑟𝑎𝑢 𝑒𝑡 𝑎𝑙. 2013より

下流効用：目的地までの期待効用
𝑉𝑛𝑑 = 𝐸 max(𝑣𝑛 𝑎 𝑘 + 𝜇𝜀𝑛 𝑎 + 𝑉𝑛𝑑 (𝑎))
リンク選択確率：第一種極値分布を仮定
exp{𝑣𝑛 𝑎 𝑘 +𝑉𝑛𝑑 (𝑎)}𝑑𝑃𝑛 𝑎 𝑘 = σexp{𝑣𝑛 𝑎 𝑘 +𝑉𝑛𝑑 (𝑎)}
経路選択確率：リンク選択の繰り返し
𝑃 𝜎 = ς𝐼−1𝑖=0 𝑃(𝑘𝑖+1 |𝑘𝑖 )𝑘1𝑘2𝑘4𝑘18

Recursive Logit Model (RL Model)
下流効用：目的地までの期待効用
𝑉𝑛𝑑 = 𝐸 max(𝑣𝑛 𝑎 𝑘 + 𝜇𝜀𝑛 𝑎 + 𝑉𝑛𝑑 (𝑎))ログサムをとる

𝑉𝑛𝑑 = ൞𝜇𝑙𝑛 ෍ 𝛿 𝑎 𝑘 𝑒𝑥𝑝
0

指数化する

行列で表現
する

1
𝑣𝑛 𝑎 𝑘 + 𝑉𝑛𝑑 (𝑎)𝜇∀𝑘 ∈ 𝐴

𝑘=𝑑11𝑙𝑛 ෍ 𝛿 𝑎 𝑘 𝑒𝑥𝑝 𝑣𝑛 𝑎 𝑘 + 𝑉 𝑎
𝜇exp{ 𝑉 𝑘 } = ൞𝜇1
𝑘=𝑑∀𝑘 ∈ 𝐴

1𝛿 𝑎 𝑘 𝑒𝑥𝑝 𝑣 𝑎 𝑘 + 𝑉 𝑎𝑎 ∈ 𝐴(𝑘)𝑀𝑘𝑎 = ቐ𝜇0𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

𝐼: 𝐴ሚ × 𝐴ሚ の単位行列
M: 𝐴ሚ × 𝐴ሚ の即時効用を表す行列
𝑧: 𝐴ሚ × 1 の 下流効用を表すベクトル b: 𝐴ሚ × 1 の 目的地を表すベクトル
ベルマン方程式𝒛 = 𝑰 − 𝑴 −𝟏 𝒃で表せるとすると，

19

Recursive Logit Model (RL Model)経路選択確率：リンク選択の繰り返し
𝑃 𝜎 = ς𝐼−1
𝑖=0 𝑃(𝑘𝑖+1 |𝑘𝑖 )exp 1/𝜇{𝑣 𝑘𝑖+1 𝑘𝑖 +𝑉 𝑘𝑖+1 )}= ς𝐼−1𝑖=0 σ𝑎∈𝐴(𝑘𝑖 ) exp 1/𝜇{𝑣 𝑘𝑖+1 𝑘𝑖 +𝑉 𝑘𝑖+1 )}1= ς𝐼−1𝑖=0 𝑒𝑥𝑝 𝜇 𝑣 𝑘𝑖+1 𝑘𝑖 + 𝑉 𝑘𝑖+1 − 𝑉(𝑘𝑖 )11= 𝑒𝑥𝑝 − 𝜇 𝑉(𝑘0 ) ς𝐼−1𝑖=0 𝑒𝑥𝑝 𝜇 𝑣 𝑘𝑖+1 𝑘𝑖

ここで𝑣 𝜎 = σ𝐼−1𝑖=0 𝑣(𝑘𝑖+1 |𝑘𝑖 )とすると，（ Ω ：経路の選択肢集合）1𝑃 𝜎 =

𝑒𝑥𝑝𝜇𝑣 𝜎൘σ1𝜎′∈Ω 𝑒𝑥𝑝𝜇𝑣 𝜎となり，選択肢∞のMNLと同様の形を得ることができる．
 最尤推定法
対数尤度関数は，
𝑁𝐿𝐿 𝛽 = 𝑙𝑛 ෑ𝑃 𝜎𝑛𝑛=1𝑁𝐼𝑛 −11= ෍෍𝑣 𝑘𝑖+1 𝑘𝑖 − 𝑉(𝑘0 )𝜇𝑛=1𝑖=0(注)本ゼミでは基本的なRL概念の紹介にとどめておきます．
経路相関の考え方などについては，Fosgerau et al.(2013)を参考にしてください→coding してみよう！

20

Coding• Fosgerau et al. (2013)で使われている上のネットワークについて検証• 読み込むFile①link.csv(ネットワークデータの入ったcsv)①route.csv(仮想観測データの入ったcsv)①link.csv①route.csv※本ゼミでは兵頭先生の練習用ネットワークデータを使用しております21

Coding－R編

ሚ• Fosgerau(2013)でいう𝐴, 𝐴の定義

• RLの対数尤度関数を記述• リンクインシデンスマト
リクスは，多くは０の行列となるため，疎行列sparseMatrixを使用する• 今回は練習のため，効用関数の説明変数はATT1,ATT2の２つのみとする

逆行列を求め必要がある
ため，Hawkins-Simon‘sconditionを満足さなければならない．初期値重要22Coding－Python編• NumdiftoolsというHessian，Gradientを求めるmoduleを入れる• 恐らく，もともとは入っていないのでpipを使ってインストール• コマンドプロンプトで”pip”
あるいはipython セル上で”! pip”

ሚ• Fosgerau(2013)でいう𝐴, 𝐴の定義

23

Coding－Python編• RL対数尤度関数の定義• Rと同じく疎行列を使うscipy.sparse• Rのコードと見比べてみよう！！

• 初期値の定義• 初期値が悪いとNan,-infなどになり推定できない• 統計量の計算• L-BFGS-Bで最適解を探索

24

参考文献
1. Fosgerau, M., Frejinger, E., & Karlstrom, A. (2013). A link based network route choice modelwith unrestricted choice set. Transportation Research Part B: Methodological, 56, 70-80.
2. 日集計行動モデルの理論と考察

8章

3. 羽藤研 理論ゼミ資料
4. 兵頭先生ー講義資料，コード
5. 力石先生ーTSUゼミ講義資料，コード25