大体DFOLSがうまく行かないのは、初期点の問題かlocal minimaの方向へ行ってしまっているので、そのあたりを考える。 今回の場合、常識的な観点からnon-tradable goodsの価格がだいたい1くらいのはずなのに30の方へ行ったりしてたらそれはlocal minimumかなんかがそっちのほうこうになるということになる。なので、解を探す範囲を狭めて、かつ初期点を動かすことでそっちの方へ行かせないようにすることが重要。
経済学と競技プログラミングの動的計画法
個人的に競技プログラミングの動的計画法(Dynamic Programming)と経済学の動学的最適化の違いがしっくり来なかったのだけれど、今日ネットを眺めていたらわかった。
競技プログラミングではグラフのような構造でどの経路が最短かとか、ナップザック問題とかを指して、動的計画法と呼んでいるらしい。そしてそれらの代表的アルゴリズムの中には深さ優先探索とか幅優先探索、全探索、なんかをよく用いる気がする。この場合、選択肢は離散で、次の道A、B、C…と可算有限個であるからだ。
対して、少なくとも大学院レベルの経済学では、離散ないし連続時間の経済主体の最適化問題を指して動的計画法と呼ぶのだが、この問題のキモは、答えがある値で決まるのではなく、基本的に離散時間のモデルでは関数のセット(解析解は稀であり、関数の形を数値計算で解く)になる。
つまり、解は、もし今日の貯蓄(所与の変数)がこれくらいあって、そしたらどのくらい消費してどのくらい明日への貯蓄にしますか?今日の貯蓄が変わったら、どのくらい消費と明日への貯蓄が変化しますか?みたいなことを調べるのが目的になる。*1 これは、経済学で扱うのはすべて連続変数なので、選択肢が非可算無限個で、その中から最適な選択を示すとなれば必然的に関数形になるからだ。
んで、基本的にマクロ経済学での最適化問題(家計の最適化問題など)は解析的に解けない(数式で表せない)ので、少なくとも今日の貯蓄という所与の変数の方はめちゃくちゃ細かいグリッドで離散化して、その元で最適な選択を数値計算で導いて、擬似的な関数を得るということになる。
数学的には、(不等号)制約付き関数方程式を解くことであり、これはベルマン方程式で書くことで再帰的になり(ショックがある場合は定常なマルコフ過程であるとする)、これを元に関数の形を解として導くことになる。
競プロで動的計画法って言われて俺に馴染みがなさすぎたのは以上のような理由でした。
そんなことより誰か猿でもわかるように連続時間の動的最適化について教えてくれ
*1:もしくは、今あなたの目の前にケーキ1ホールがあって、これから1分毎にどのくらい食べていったらハッピーさが最大化されますか?みたいなのも超初歩問題で頻出
2つ以上のマルコフ過程
経済学において確率変数を扱うことは多い。特にAR(1)過程に従う外生ショックが主流だ。例えばがAR(1)過程であるとは
である。 ショック項が正規分布に従う場合、も連続確率変数となり数値計算では扱えないので、Tauchen (1986)やRouwenhorstの手法でマルコフ過程として離散化することになる。
今回、いつもわからなくなる遷移確率行列と、2つ以上のマルコフ過程が合わさったときの遷移確率行列の作成、動的計画法におけるインデックスゼーションについてかんたんにまとめておきたい。
- 遷移確率行列のおさらい
n状態のStationary Markov Processを考える。遷移確率行列は行列で
数学的に正しい定義は縦が今期の状態ごと、横に来期ごととなる。すなわち、このは状態から状態への推移確率になる。 覚え方は"Row(行) is Now"。行は今期の状態を所与とした確率になる。
経済学、特にHeterogeneous Agents Modelでは非可算無限な経済主体を考える。例えば、各Stateにおけるagentsのmeasureを縦に積んだサイズベクトルがであるとする。この場合、このTransition probability matrixから求められる来季のDistributionは
となる。
同様に、Standard Aiyagari modelを考えた場合に、数値計算でValue functionの期待値を考える場合は、Value functionの値を格納した行列をとしたとき、サイズの遷移確率行列によって
で求められる。
(の要素は、来季の期所(state variable)のassetがグリッドであったとして、今期のlabor productivity shockがだったときのValue functionの期待値)
- 2つ以上のMarkov ProcessのindexとTransition Probability Matrix
Markov process2つを考える。この場合、Aiyagariの簡単な拡張として 2 exogenous states model(no aggregate uncertainty)とすれば、state variableはassetと2つのショックを入れて3つのになる。
これを数値計算で解くときにValue functionやPolicy functionの次元を3次元にすればindexは簡単になるが、遷移確率の扱いが面倒くさくなるので、とにかく2次元にしたい。
仮定として、 とする、すなわち、は個の、は個の値を取れるとする。(上記でsetの{}が数式モードで出せなかった。)
このとき、縦にassetとして、横にexogenous stateを取った2次元行列を作成する場合、以下のような順序で取るのが好ましい。
この場合、遷移確率行列がですぐに求まる。3つ以上のMarkovの合成も、同様にして
とすれば、遷移確率行列がとなるはず(俺がクロネッカー積の定義を間違えてなければ)
問題は、何列目が一体どのstateを指すのか、もしくは任意のの組み合わせは何列目に当たるのか(ここなくても今後困らない気がしてきたから気が向いたら書く、必要な場合は、A practical Guide to Parallelization in Economics (Fernandez-Villaverde & Valencia 2018)の記事内かGithubのサンプルコードを見るとどうゆうふうに次元を下げられるかが乗っているので、そんな感じで。
JuliaのバージョンアップデートしたあとのPyCall
コンパイルに失敗する?もしかして以下のような感じ?
[ Info: Precompiling PyCall [438e738f-606a-5dbb-bf0a-cddfbfd45ab0] ERROR: LoadError: LoadError: could not load library "/usr/local/Cellar/python/3.7.3/Frameworks/Python.framework/Versions/3.7/Python" dlopen(/usr/local/Cellar/python/3.7.3/Frameworks/Python.framework/Versions/3.7/Python.dylib, 9): image not found
なら、呼び出す前にパッケージモードで build PyCall しましょう。そんだけ。
ちなみにPythonをhomebrewからアプデしたあとにJuliaが落ちることがあって、これの場合もbuildすれば治った。
AtCoderに手を出してしまった
はっきりいって僕が普段やっているマクロ経済学の数値計算は、世間一般で求められているコーディング技術とは少し違う。
- 所与の価格のもとで制約付き動的計画法を解いて家計の政策関数を導出。
- その政策関数を元に、家計の財需要ないし資本や労働供給を計算。それが市場の需給が一致するかチェック。していれば終了、していなければ価格を変更して再計算。
が定常状態計算。ここから景気循環やら何かしらのショックが起きたときに経済変数がどのように変動するか、また別のコーディングで計算する(DynareやMIT ShockのTransition Pathなど)。
ただ、そういった中でも、例えば行列から条件に当てはまる要素を探し出すことなんかは頻繁に出てくる。(まあJuliaならsearchsortedlastなどのBase関数でやれば一発ではあるが。)
というわけで全然別物というわけでもないことも気付かされた。入出力をほぼ使わないという点を除けば。
AtCoderの問題というか競技プログラミングの問題は、意外とパズルっぽいものも多く、みんながハマる理由がわかった気がする。(Cまで解いた感想です)。
それに経済学のコードだとあまりネットに落ちていない分、どんなアルゴリズムやコードの書き方がいいのかということがわかりにくいが、AtCoderなら解説も存在するし、普通の人はこういうふうに捉えるのかというのが学べてとても面白い。
たとえば、Beginnerコンテスト117回目のB問題
これは解くのに必要な定理が示されているので、それ通りにコードを書くだけである。 問題はどうやって最大の長さを調べるか、そしてそれ以外の辺の長さの合計をどう出すか、だと思うのだが、僕自身が何も考えずに書いた結果、はforループを3回も使う書き方しかピンとこなかった。
#include <bits/stdc++.h> using namespace std; int main() { int N, maxl =0, ind = 0, total = 0; cin >> N; vector<int> length(N); for (int i = 0; i < N; ++i){ cin >> length.at(i); } // max for (int i = 0; i < N; ++i){ if (maxl < length.at(i)){ maxl = length.at(i); ind = i; } } // total length except for the max for (int i = 0; i < N; ++i){ if (i != ind ){ total += length.at(i); } } if (total > maxl){ cout << "Yes" << endl; } else{ cout << "No" << endl; } }
しかし、解説を見れば、長さのベクトルを取得したあとにsortでやる、または長さを取得した際にすべての合計sumとmaxを取得し、それ以外の長さはsum-maxとすればよいなど、言われてみればたしかにそのとおりだという解き方が示されていた。 そういった細かいアルゴリズムが、自分の数値計算コードに役立つ日が来るといいと願いながら、今後もやっていきたい。
まあ発表スライド作るのが嫌すぎて現実逃避しているだけなのだが。
MacのC環境更新
ご多分に漏れずあんまり良くわかってないので、間違ってたら指摘していただけるとありがたいのですが、 MacはデフォルトでC言語が入っている(正確にはCLang)。が、バージョンが古いのでアプデしようと思ったのです。 それで、Homebewからgccをインストールしたんですね。
> brew install gcc //インストール
でもなんだかうまくいかない。調べてみる。
> gcc -v Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 10.0.1 (clang-1001.0.46.4) Target: x86_64-apple-darwin18.6.0 Thread model: posix InstalledDir: /Library/Developer/CommandLineTools/usr/bin
うん、これデフォルトのまま。まず、シンボリックリンクを貼って、ターミナルにgccと打ったときに認識されるようにする。
> ls /usr/local/bin | grep gcc > ls /usr/local/bin | grep g++
現在はgcc-9などがあるので、それを使う。
> ln -s /usr/local/bin/gcc-9 /usr/local/bin/gcc > ln -s /usr/local/bin/g++-9 /usr/local/bin/g++
はい、これでいけますかね。
> gcc -v Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 10.0.1 (clang-1001.0.46.4) Target: x86_64-apple-darwin18.6.0 Thread model: posix InstalledDir: /Library/Developer/CommandLineTools/usr/bin
えー、いけない。ちょっとここで気づいたのだけれど、
>which g++ /usr/bin/g++
(which gccはなぜか反応しなかったので、こっちでチェックした)あ、これ/usr/local/bin/g++よりも先に/usr/bin/g++が来てますね。で、つまり、シェルに対して優先的に探すパスを変更する必要がありますね。
6月27日追記:おそらくこのタイミングでターミナルを再起動すれば問題ない気がする。
/usr/bin/はPC全体の、/usr/local/bin/は個別のユーザーに対してですよね、どう見ても。
まあそれで、zsh使ってるんで優先パスの通し方を探したんだけど、bashのばっか。最終的にホームディレクトリ下のzprofileをいじればいいことに気づく。
> cd //一応 > open .zprofile
するとこの中に
# Set the list of directories that Zsh searches for programs. path=( /usr/local/{bin,sbin} $path )
という部分があるので、ここを
path=( /usr/local/bin /usr/local/{bin,sbin} $path )
ととりあえずしてみる。解決!gccと打ってデフォでHomebrewで入れたgcc-9が呼び出されている。 ただ、この優先パスの書き換えで他のところに影響がでるかもしれないし、このパスの通し方が冗長である、間違ってる可能性があるので、何があっても自己責任で。。。
6月27日追記 それで、おそらくこの部分が悪さをしていると考えられることが生じた。 具体的には、これを変更したあと初めてvs Codeを再起動したら、latex workshop経由のtexのコンパイルが通らなくなった。 どうも環境変数パスからlatex等のコマンドが見つからなくなったせいらしい。つまり、この部分の変更でなにか変なことが生じたみたいだ。 環境変数について少し理解が深まったのだが、いかんせんどこで永続的に$PATHが定義されているのかよくわからない。おそらく.zprofileの上の部分だと思うのだけれど、そうなるとこのファイル内の$pathはどこで規定されてるの???
とりあえず、動けばいいのでもとに戻した。しかも普通にwhich g++で/usr/local/bin/g++が出てくる。この前インスコ後に一度ターミナルを再起動させなきゃいけなかったのだろうか。
いつもお世話になってる動画
まあタイトルは冗談として。 個人的に食事や料理モノのテレビ番組や動画が好きでよく見ます。アニメだと食戟のソーマ(原作完結したそうですね)、衛宮さんちの今日のご飯、異世界食堂、甘々と稲妻。小さい頃に中華一番とかミスター味っこの再放送っぽいの何度か見てた記憶がある。 マンガだと小さい頃にクッキングパパとか。 テレビ番組は孤独のグルメ、コウケンテツの世界の食卓、駅前食堂、サラメシ。(日本にいる間だけ)
んで、最近はYouTuberで料理モノとかよく見るんですよ。最近はレシピ参考とかも兼ねて、にぎりっ娘さんのお弁当中。じゅんさいに楽しむ形でGenの本棚食堂さん(とそのサブチャンネル)とか、岡奈なな子さん。
プロの料理人系はCOCOCORO's キッチンさん。
あとはお酒系でおっくんの宅飲みグルメさん、にゃんたこさん。前はいい加減に作る晩御飯さんも好きだったんですが、見始めたときには既に更新されなくなってまして。。。
あとは大食い系で谷やんさん、大食いラスカルさん。 ラーメン見たいときは、SUSURUさんとか。
海外枠は、Liziqiさんとかですかね。
全部飯テロなので、早く日本帰りたくなりますわ。
日本でよく使うような食材がなかなか手に入らないので、レシピなんかを見つけてもなかなか再現しづらいんですよね。 もやしは遠出してやっと手に入っても1.5ドル。魚は全然売ってないし、魚製品ももちろんなし。 肉は薄切りなんて近くには売ってないので、チャイナタウンか韓国系スーパーの冷凍を買ってくるしかないのですが、持ち帰る間に勝手に半解凍されてしまうし。 野菜も葉物はなかなか…ほうれん草は葉っぱの部分しか見あたらず、キャベツとかは日本のと違う種類。人参もクソまずくて、大根もアジア系スーパーまで足を伸ばさないとですね。
逆にアジア系スーパーまで行けば、そこそこの調味料や根菜も手に入ります。牛蒡や長芋なんかに、日本の冷凍食品や加工食品。納豆も冷凍なら売ってます。 ただ電車で30分とかなんですけどね。。。
もう少しいろいろ簡単に手に入るようになればいいなぁ、なんて考えながら、動画でお弁当や夕飯のレシピを考えたりする日々です。