2019.5.16
○ スタートアップゼミの発表に関するメモ
・MNL
ハフモデル 商圏の分析に利用、店舗の魅力度として売場面積を採用
尤度比 モデルとしての精度
基本的に説明変数を増やして、モデルの尤度比をあげる。選択肢固有定数は1番最後。
説明変数同士に強い相関があるとダメ。多重共線型性。
選択肢ごとにも個人ごとにも値が異なる説明変数のみ、パラメータをすべての選択肢に入れて良い
・PP
probeデータを過去の地図に重ねることで、古町の衰退がわかる。probeの良さを全てなくすような手法だが、だからこそ面白い
locationデータから個人属性割とわかる
PPデータから動画を作成するツールがあった
○ 理論談話会
・RL
経路選択において、MNLは経路列挙型であるのに対し、経路選択肢を非列挙。マルコフ連鎖もそう。
ある状態kにおいて、次の状態aへ遷移する効用は、k→aの遷移による効用と、aからDまでの期待効用の最大値との和なる。これは再帰的な定式化になっているので、どんどん引き戻していくことができる。
これはBellman方程式の形になっていて、行列表示することで、解ける!
各効用がわかれば、各状態遷移の確率を例のexpの分数の形で出せて、それが分かれば経路の選択確率を各状態遷移確率の積で出せて、また、各リンク交通量も出せる。
また、path size logit でやったような、異なる経路におけるパスの重複において効用を下げる効果も見積らねばならない。
MNLだと、経路列挙型なので、純粋に重複しているパスの長さをカウントできるが、RLは経路非列挙なので、そういうやり方はできない。
そこで、単位交通量を流した時の、各リンク交通量を用いて、パスの重複を考慮する。Link size 修正項。
将棋とかオセロとかチェスは、評価関数が適当でも割と良い勝率を出せるので良かったが、囲碁はそうはいかない。
評価関数が出しにくい時に、モンテカルロ的にランダムに手を試すことで、どの手の勝率が高いかを試す。ただ、全部を試すことはできないから、実際に試す手をいかにうまく制限するかがポイント。
たとえば、Multi-Armed Bandit問題、沢山のスロットでどれが1番良いやつかを当てる問題、の解法である、UCB1アルゴリズムを用いる。
UVB1アルゴリズムは、
1. まず全てのスロットにコインを1枚ずつ投入
2. UCB1値が最大のものにコインを投入することを繰り返す。
端末jのUCB1値 = 端末jのこれまでの報酬の平均値 + \sqrt{2log(n)/n_j}
nはこれまでに投入した全コインの枚数
こうすると、最善でないスロットに投入されるコインの枚数はO(log(n))で抑えられるので、n→∞において、最も期待値の大きいスロットのみにコインを投入できる。すごい!
これは、これまでの各端末の期待値だけでなく、第2項で、投入枚数が少ない時は、揺らぎが大きくなることを考慮に入れていることがポイント。
2019.5.15
・スタートアップゼミの課題を仕上げる
各アルゴリズムの原理についてまとめ直した。A*については、具体例も入れた。
発表のスライドを作る、という作業は、コンペにおけるパネル同様、それだけで時間を要するものなので、今後も理解と発表準備との時間配分に気をつけたい。
・夏研究について
オークション理論の基礎を勉強し,駐車場利用権の入札に用いた場合に,同時に駐車場の配置を最適化するような問題を定式化することに取り組んではどうでしょうか.車両そのものを都市のどこに配置させることが物販車として考えた場合と,歩行者として考えた場合の最適配置問題について考えつつ,駐車料金のオークショ
ン問題を通じて,動的なサービス設計を考えることを通じて,理論研究になれるのがいいように思います.
今日の打ち合わせでは,
・1次元線形都市で,郊外-周縁-中心モデルを作成し,駐車場最適配置問題の定式化を行う.解の性質をみる.
・次にこれを動学的な問題に拡張するとともに,利用権配布問題として定義.
・駐車場選択問題をRLモデルでマッチングさせるVCGメカニズムの証明.
・休めるうちに休むということで、理論談話会の論文を読むのは明日に回した
2019.5.14
・スタートアップゼミの課題に取り組む
経路選択モデルを様々なアルゴリズム、言語で実装して比較する。
アルゴリズムはDijkstra法、Bellman-Ford法、A*法、言語はCとPython。
3つのアルゴリズムについて理解した後、実装。結果をGISで可視化。GISがなかなかうまくいかず、意外と時間を食ってしまった。
Bellman-Ford法は、リンクコストが負の場合も計算できるので、災害時に配給がある、というようなリンクコストが負になりうるネットワークを想定して、Dijkstra法ではうまくいかないが、Bellman-Ford法だとちゃんと最短経路出せることを示す。
CとPythonの比較は前やったが、200倍くらい違う。
なぜか、A*の方がDijkstra法より遅くなったので、原因を考える。
A*はヒューリスティック関数をいじれる。マンハッタン距離と直線距離で計算時間比較する。
理論談話会の反省も踏まえて、スライド作りながらやる。
・ArcGisエラーあるある
- 南東、北西方向に、400mくらいズレる
- 地図の真ん中に点が表示される
→ 座標がNULLの点をプロットしている
2019.5.13
事務作業や雑務に追われて研究面での進捗はなかった
2019.5.10
理論談話会二つ
・simplification decomposition
均衡配分を解く方法として、Frank-Wolfe法を非対称問題にまで拡張したもの。
1番時間の短いところに全てのフローを流す
> 全部のフローを流した結果、先の最短経路以外で、最短のところができた場合、それら2つの経路の時間が同じになるようにフローを決定
> それら2つにフローを流して時間を計算して、それ以外の経路でさらに時間が短い経路があるなら、それも含めた3つの経路に時間が同じになるように流す
> 以降、繰り返し
でもこれって、Frank-Wolfeも同じだったような気がするが、どこが違うのか....
・都市形成モデル
内容自体は正直あまりよく分からなかったが、輸送における氷解コストをうまく設定することで、資源分布や地形情報を入れると、最適な交通ネットワークが生成できるというモデルが作れる。これにより、インフラ投資の必要性が言えたりもする。
・確率フロンティア
入力に対して、出力の効率性を評価する方法。非常に簡便な方法で効率性を相対的に評価できる。ただし、相対的な効率の順位がわかるだけで、なんの入力が効いているかや、効率性の原因は決定できない。
効率性の評価と捉えると、非常に汎用性が高く、かつ簡便。駐車場の効率化、都市計画の効率化、色々評価はできる。
・アクティビティモデル
自分の発表分。スライド作りに時間をかけすぎたか。まあその甲斐あってか、発表はよかった。やはりアクティビティモデルはなかなかすごい。
2019.5.9
・スタートアップゼミ
都市形成史分析。土地所有権の変遷を読み解く論文を題材に、文献の集め方、そのデータ化の方法などを扱った。
元来、歴史研究というのは、普遍性と固有性の塩梅が難しくて、研究としていかにシャープになるのかがわかっていなかったが、単純にその地域についての歴史をまとめること自体にも、それが残るという意味で研究的価値はあるのだと思わされた。
・基礎プロTA
一個下のレイヤー分析の課題を見る。完成度が高かった。やはり地図上で手を動かす、という営みは本当に価値があって、そうした営みの深さは分析や理解の質に決定的な影響を与える。
去年、自分のやつは、扱う範囲の決定を曖昧にしてしまって、範囲がずれる形でレイヤーを重ねてしまったので、結果的に深いところまでいけなかった。また、1:10,000の地図があったりなかったり、あるいは、範囲がずれたり、みたいなので、歴史的なところも読み込めていなかった。応プロ1の雑司が谷の分析はそこそこ良かったので、あの感じを忘れないようにしたい。
また、テクニカルな話としては、ダイアグラムにはベースマップがあった方が良い。
2019.5.8
・activityモデルの論文、part2、実装の方も読み終える。
実装の方の思想と読み合わせることで、理論の方の理解も深まった。実装をするとなると、何をインプットとして、何をアウトプットとするのか、どういう流れでやるのかがきちんとわかっていないと出来ないので、その辺りは整理になった。
ただ、じゃあプログラムを書けと言われると相当難しそうで、スタートアップゼミで該当回があるので、そこまで楽しみにしておくということにしようかと思う。
また、発表のためのスライド作りにも取りかかれた。理論の部分に差し掛かったところなので、明日、引き続き、よく構造化された、明快で平易な説明を心がけたい。