SGDの実装を読んでみる（その1）

Scikit-learnのSGDに関係あるソースコードを読んだ。

• モチベーション
• 主要なクラス概観
• 高速化の要因（予想）

モチベーション

Scikit-learnに実装されている最適化アルゴリズム（Cythonで実装）を読むことで、Pythonで実装するときと比べて高速化する要因を推察する。

今回はSGD(Stochastic Gradient Descent)のソースコードを読む。
scikit-learn/sgd_fast.pyx at master · scikit-learn/scikit-learn · GitHub

主要なクラス概観

重要そうに見えるクラスは

• SequentialDataset
• WeightVector

の二つ。

SequentialDataset

• 有限のデータセットからnextメソッドで一つサンプルを選ぶ
• サンプルは毎回ランダムに選ぶのではなく、置換したインデックスを順に見る
• GILが必要な部分をコンストラクタにまとめている

scikit-learn/seq_dataset.pyx at master · scikit-learn/scikit-learn · GitHub

WeightVector
細かいところをまだ読み切れてないけどメモ。

• ベクトルの和や内積を計算できる
• スカラー倍の計算時間を定数にするためにスカラー倍用の変数をもつ
• avarage_weightsがよくわからない

scikit-learn/weight_vector.pyx at master · scikit-learn/scikit-learn · GitHub

高速化の要因（予想）

• ベクトルなどの型を指定
• ベクトルの演算時にGILを取得しないで済む
• ベクトルの演算時に境界のチェックとかが入らないようにしている

おわりに

次回はWeightVectorをもうちょっとちゃんと読みたい。
高速化の要因をだいたい挙げ切ったと思えたら実装して速度比較したい。