51代プロ研のしくがわです。Web班長をやってました。何故過去形なのかというと先日サークルを引退したからです。寂しくなりますね。 さて、以前大学の講義でロジスティック回帰を実装するといった課題が出たのですが、やっていてふと、
「これコンパイル時やればいいのでは？」
と思ったんですよね。んで、丁度アドベントカレンダーの時期だったこともあり良いネタになると考え、やってみようと思い立ちました。ここではコンパイル時に色々やるにあたって必要な知識とかを薄く話していきたいと思います。
メタプログラミングとは？
Wikipediaの説明はちょっと難しいのですが、要はコードを生成するコードを記述するプログラミング技法です。マクロのすごい奴だと思っていただければ良いでしょう。メタプログラミングという文脈に於いては、C++やRubyと言ったプログラミング言語が出てくることが多いです。ここではC++におけるメタプログラミングについて見ていきます。Rubyにおけるメタプログラミングはここでは語らないので直接僕に聞くなりしてください。
C++におけるメタプログラミング手法として代表的なものとしてテンプレートや定数式を使ったものがあります。僕はRubyでメタプログラミングを知った人間なので、静的型付け言語でメタプログラミング？と思っていたものです。C++におけるメタプログラミングとは、コンパイル時に計算を行い、実行結果をアセンブリに直接埋め込む言った形になります。つまり、実行時に行う計算をコンパイル時に実行することが出来るという事なので、実行すると非常に計算時間がかかるプログラムであっても、一瞬で計算結果を出力出来るという事なのです。これは、時間がかかり、かつ実行時に計算する必要がないような処理を行う場合に極めて強力な手段となり得ます。ただ、便利で強力な反面、実行時処理と比較すると極めてプログラミング的な制約が厳しいので慣れが必要です。
ロジスティック回帰とは？
回帰モデルの一種であり、]で成約された値を出力します。式で表すと以下のようになります。モデルのパラメータを
、データ集合をを
とすると、
$$ t_i = \displaystyle{\mathbf{\theta}^T\mathbf{x_i}} $$
$$ \displaystyle{f(t_i) = \frac{1}{1+e^{-{t_i}}}} $$
ここでのはロジスティックシグモイド関数です。
データ集合に対する正解ラベルのベクトルをとします。また、最小化する目的関数
として
と
との平均二乗誤差とすると、
$$ \displaystyle{E=\frac{1}{2}(y_i-f(t_i))^{2}} $$
ロジスティック回帰の目的はデータとラベルを対応付ける正確な予測モデルを構築する、つまりモデルのパラメータの真値を求めることにあります。しかし、目的関数の最適値を解析的に求めることは出来ません。そこで、逐次的に最適解を更新していくことで近似的に最適解を求めるという方法を利用します。そのためのアルゴリズムとして最も単純なものに最急降下法が挙げられます。最急降下法を適用すると、以下の式で表されるように解を更新していくことになります。
$$ \displaystyle{\theta_t =\theta_{t-1} -\alpha \partial_{\mathbf{\theta}} E} $$ $$ \displaystyle{\theta_t =\theta_{t-1} -\alpha (f(\theta^T\mathbf{x_i})-y_i)f(\theta^T\mathbf{x_i})(1-f(\theta^T\mathbf{x_i}))\mathbf{x_i}} $$
ここでのは学習係数と呼ばれ、パラメータの更新度合いを示します。小さければより細かく解を更新できるが収束に時間がかかり、大きければ大雑把に解を更新してしまうので収束しない可能性があるというトレードオフの関係を持ちます。
今回やったこととしては、このロジスティック回帰をコンパイル時に行うといったものになります。
実装
ソースコードは下に載せました。もう少しメタな実装をしたかったと思われる部分もあるのですが、時間的な都合もあり今回は見送りにさせていただきました。また機会があればお見せしたく思います。学習を行うにあたって、cmathモジュールの関数が定数式に対応していないものが多くあるというのがあったため、基本的に演算(ここでは指数関数、平方根、累乗くらいですが)を自前で実装する必要があります。指数関数に関してはテイラー展開(マクローリン展開)を使って実装するのが普通でしょう。平方根は近似解を求めるアルゴリズムが複数存在します。今回使用したのはBabylonian Methodと呼ばれる方法です。平方根の近似解アルゴリズムはこれ以外にもたくさん方法があるのですが、英語版Wikipediaの記事がかなり詳しいので興味ある方はこちらを見ていただければいいでしょう。
Methods of computing square roots - Wikipedia
ソースコード
以下のコマンドでコンパイル出来ます。-fconstexpr-stepsの値は十分に大きい数なら大丈夫です。
clang++ -std=c++17 program.cpp -fconstexpr-steps=100000000
出来上がった実行可能ファイルを実行すると、更新済みのパラメータの重み値が出てきます。
まとめ
この記事を読んでいるギークな方の中には「それ間違ってない？」とか「それおかしくない？」とか感じた方がいらっしゃるかもしれませんが、そういった鉞はTwitterのリプライなりDMなりで飛ばしていただければ嬉しく思います。
明日の記事は、あたふたさんの「半年近くシミュレーションRPGを作って感じたこと」です。有能企画長としてお仕事してきた彼がゲーム制作を通して何を感じたのか、とても気になりますね。お楽しみに！
