E資格対策の暗記シート

この記事は自分がE資格の受験をするために、忘れがちや間違いがちの知識について、色々な勉強資料から抜粋して整理した内容です。

NumPy

np.random.permutation(5)
# array([3, 1, 2, 4, 0])

# 重複を許すサンプリング（復元抽出）３つ抽出、それぞれの範囲は[0, 5)
np.random.choice(5, 3)
# array([3, 3, 2])

np.min([1,2,3])
# 1

np.amin([1,2,3])
# 1

# 連続一様分布から0.0以上1.0未満の乱数配列を生成
np.random.random_sample()
# 0.1322630747589819
np.random.random_sample(3)
# array([0.8892175 , 0.86287021, 0.15078942])

l, v = np.linalg.eig(cov)
# l：covの固有値。l.shape：(次元数,)
# v：covの固有ベクトル。v.shape：(次元数, 次元数)
# lの第0次元とvの第1次元は固有ベクトルの本数を意味する
# 入力データとvの各列の内積を取ることで、新たな変数が生成される

機械学習

計画行列（Design Matrix）：事例（データ）を行に、特徴量を列に対応させた一般的なデータ集合
バプニック（Vapnik）原理：ある問題を解くとき、すぐに（途中段階で）それより一般的な問題を解こうとしてはいけない

タスクの種類

• 転写（Transcription）：構造化されていないデータを変換する問題。例：文字認識、音声認識
• 構造出力：入力データの構造を推定する問題。例：自然言語処理の構文解析
• 異常検知：入力データが異常か正常か推定する問題
• 合成とサンプリング：訓練データと類似した新たなデータを生成する問題。例：音声合成
• 密度推定：入力データの確率密度（そのデータが得られる確率はどのくらいか）を推定する問題

誤差の種類

• バイアス：モデルの表現力が不足していることによって生じる誤差
  • 予測値の期待値$E[y(x)]$が理想の予測値$h(x)$から離れている程度。例えば予測モデル$y(x)$が線形モデル、理想の予測モデル$h(x)$が非線形モデルの場合、この誤差が大きい
• バリアンス：訓練データの選び方によって生じる誤差
  • 予測値$y(x)$が予測値の期待値$E[y(x)]$からばらついている程度
• ノイズ：データの測定誤差などによって生じる誤差
  • 理想的なモデル$h(x)$が真値$t$から離れている程度

特徴選択

• フィルタ法：相関係数などの重要度で選択する
• ラッパー法：学習と変数選択を何度も繰り返す
  • 計算に時間がかかる
  • 検証誤差の小さい特徴量の組合せを見つけやすい
  • 検証データに過剰適合するかも
  • ステップワイズ法が代表
• 埋め込み法：線形回帰の損失関数に正則化項を加えて、学習と同時に最適な特徴量の組合せを見つける
  • フィルタ法とラッパー法の中間性質を持つ

アルゴリズム

用いる経験の種類により、教師あり学習、教師なし学習、強化学習に大きく分類される。
強化学習：固定のデータ集合を用いるだけでなく、学習結果のフィードバックとして新たな経験を得て学習するアルゴリズム。

ロジスティック回帰

• 2クラス分類問題
• クラスに所属する確率を予測する

y = \frac{1}{1 + e^{-z}} \\
z = a_0 + a_1 x_1 + \ldots + a_n x_n

$y$はシグモイド（sigmoid）関数

負の対数尤度

L = - \sum_n (y_n \log \hat{y}_n + (1 - y_n) \log (1 - \hat{y}_n)) \\
\frac{\partial L}{\partial \hat{y}} = -\frac{y}{\hat{y}} + \frac{1 - y}{1 - \hat{y}} 

オッズ

\frac{\hat{y}}{1 - \hat{y}} = \exp(w^T x + b) \\
\hat{y} = \frac{1}{1 + \exp(-w^T x - b)}

SVM

• サポートベクトル：境界線に最も近い点
• マージン：境界線とサポートベクトルとの距離；マージンが最大となるような境界線がSVMの境界線
• 誤識別に対してペナルティを科すため、スラック変数を導入
  • スラック変数を導入し、マージン最大化とペナルティの最小化を同時に行うSVMはソフトマージンSVMと呼ぶ
  • ハードマージンSVMはペナルティを考えない
• 1クラスSVM：異常検知に使う
• LIBSVM：SVMに関するライブラリ

カーネルトリック

データを高次元空間に写像したら、高次元データ同士の内積計算$\phi(x)^T\phi(x')$は計算コストが高くなる。この問題を解決するため、高次元内積を直接計算する代わりに、元の空間における関数$k(x,x')$を高次元内積の結果として使う。関数$k(x,x')$には、下記動径基底関数がよく使う。

k(x,x') = \exp\left(-\frac{||x - x'||^2}{\beta}\right) 

k近傍法

• 目的：分類
• 教師あり
• 教師データ：
• 各データのラベル
• 位置によって領域に分割されている多次元の特徴空間におけるベクトル
• 分類基準：k個の最近傍のデータに最も多く付けられているクラスラベルが割り当てられる

k-means++

最初の重心の位置を互いに遠くに配置することで収束も早くなる。
初期値はルーレット（Roulette）選択で設定する。他の代表ベクトルとの距離の二乗に比例する確率で確率的に代表ベクトルを選択する。

主成分分析

データの分散共分散行列の固有ベクトルから構成される。
最も固有値が大きな固有ベクトルは第一主成分。
寄与率：各主成分の固有値を固有値の総和で割った比率。

次元の呪（のろ）い、球面集中現象

ナイーブベイズ

分類モデル、スパムメール判定に適している。

正則化

• Lasso回帰（L1正則化）：回帰係数のいくつかの値が0になる
• Ridge回帰（L2正則化）：回帰係数の絶対値の値は小さくなりますが、基本的には0にならない
• Elastic Net回帰：L1とL2組み合わせ、それぞれの比率を調整する

バッチ正規化

h' = \frac{h - \mu}{\sigma}

$h$はあるノードの入力。
$\mu$と$\sigma$はテスト時に、訓練時に計算しておいた移動平均値を使う。

モデルの表現力を維持するため

h' \leftarrow \gamma h' + \beta

特徴：

• 学習率を大きくできる
• 初期時にそれほど依存しない
• 過剰適合を抑制する（ドロップアウトなどの必要性が減る）
• ミニバッチごとのデータ数が極めて少ない場合に適さない
  • 例えばデータ数が1であるオンライン学習に適用しても意味ない

いくつかの正規化手法

• 記号
  • N：バッチ方向
  • C：チャンネル方向
  • H：特徴マップの高さ
  • W：特徴マップの幅
• 種類
  • ア：バッチ正規化
  • イ：レイヤー正規化
  • ウ：インスタンス正規化
    • バッチの中のデータごと、またチャンネルごとに（1特徴マップの1チャンネル分）平均と分散を計算する
    • スタイル転送に使う
      • 入力のコンテント画像の構造とスタイル画像の画風を合わせて、合成画像を出力する
      • 合成画像のコントラストはコンテント画像のコントラストに依存しない
  • エ：グループ正規化
    • バッチの中のデータごと、またチャンネルのグループごとに平均と分散を計算する

検証

• Hold-Out：X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)
• Leave One Out：一つ抜き法、ジャックナイフ法とも呼ばれ、データ全体のうち1つだけをテストデータとすることを繰り返す。Cross Validationと似ている

分類問題の評価

• 正解率（Accuracy） $\frac{TP+TN}{TP+TN+FP+FN}$
• 適合率（Precision） $\frac{TP}{TP+FP}$
• 再現率（Recall） $\frac{TP}{TP+FN}$、見逃していないかどうかの指標
• F値 $\frac{2 \cdot Precision \cdot Recall}{Precision + Recall}$、正解率で評価するのが適さないような不均衡データには有効

ROC曲線（受信者動作特性曲線）

• Receiver Operating Characteristic
• 横軸：偽陽性率（FPR, False Positive Rate）、$\frac{FP}{FP+TN}$
• 縦軸：真陽性率（TPR, True Positive Rate）、$\frac{TP}{TP+FN}$
• AUC：Area Under the Curve、ROC曲線の下の面積

回帰問題の評価

• 決定係数（$R^2$）
  • $R^2 = 1 - A / B$
    • $A = \sum_{i=1}^{n}(y_i - \hat{y}_i)^2$
    • $B = \sum_{i=1}^n (y_i - \overline{y}_i)^2$
• 二乗誤差（RMSE、Root Mean Squared Error）
  • 予測対象が幅広い実数値を取る場合に使う
  • 観測誤差の分布として正規分布を仮定
  • 目的変数に外れ値が存在する場合に適さない
• 平均絶対誤差（MAE、Mean Absolute Error）
  • $\frac{1}{n}\sum_{i=1}^n |y_i - \hat{y}_i|$
  • RMSEより外れ値の影響を受けにくい
• 対数2乗平均平方根誤差（RMSLE、Root Mean Squared Logarithmic Error）
  • $\sqrt{\frac{1}{n}\sum_{i=1}^n (\log (y_i + 1) - \log (\hat{y}_i + 1))^2}$
  • スケールの大きな値の影響を軽減する

ハイパーパラメータのチューニング

グリッドサーチ

• すべての組み合わせを試す
• 学習時間が長い

ランダムサーチ

• パラメータをランダムに探索
• 計算時間が短いが、最適な組み合わせにたどり着かない可能性がある

ベイズ最適化

• 正答率が良さそうなエリアを優先的に探索
• 局所解に陥らないように、稀にその他のエリアを探索
• 帯域的で観測ノイズを考慮した探索が可能
• 予測モデル（最適化する関数）：ガウス過程回帰
• 獲得関数
  • ガウス過程回帰で得た予測値と不確かさ（分散）の情報で、次の探索点を決める関数
  • PI（Probability of Improvement）戦略：（改善量はわずかであっても）改善される確率がもっとも高い点を選ぶ
  • EI（Expected Improvement）戦略：改善量の期待値が最も高い点を選ぶ
  • UCB（Upper Confidence Bound）戦略：信頼区間の上限が最も高くなる点を選ぶ。最大化が目的の時に使う
  • LCB（Lower Confidence Bound）戦略：信頼区間の下限が最も低くなる点を選ぶ。最小化が目的の時に使う

深層学習の基礎

バッチ学習vsミニバッチ学習

• バッチ学習
  • 全ての学習データを1イテレーションに投入する
  • 重みの初期値をランダムに設定したあとに、確率的に変動する要素はない
• ミニバッチ学習
  • イテレーションのたびに目的変数は変わる
  • 局所的最小解から抜け出せる可能性がある

万能近似定理

隠れ層が少なくとも1つ必要。
関数が学習できることを保証していない。
活性化関数が非線形必要。
ネットワークの大きさについて述べていない。

誤差逆伝播法

シンボリック表現：$x$や$y$などのシンボルによって数式や信号の流れを扱うこと
シンボル間の微分：導関数（微分処理）についても明示的にシンボルをおき、微分を計算していくアプローチ

勾配法の必要条件：目的関数がパラメータによって微分可能
確率的勾配降下法：無作為に選び出されたデータを使って行う勾配降下法

正則化

• 重み減衰
  • 損失関数にL2ノルムを加える
  • パラメータが原点から離れていくことに対してペナルティを課す
• 重み共有
  • 位置によって別々のフィルタ（重み）を用いるのではなく、１つのフィルタ（重み）を共有する
  • パラメータの自由度が減って、正則化の一種
• 早期終了：検証誤差が最小になる時点（訓練誤差を超える時点ではない！）に終了

アンサンブル

複数のモデルを使い、単一モデルより高い性能を引き出す手法の総称

• バギング（bagging, bootstrap aggregating）
  • 学習データからブートストラップサンプルと呼ばれるデータの集合を複数作成
  • 例：ランダムフォレスト
• ブースティング
  • 間違えたサンプルの重み（係数）を大きくして学習

Drop Out vs Drop Connect

• Drop Out：出力の一部を0にするを行う
• Drop Connect：Drop Outの一般化、重みの一部を0にする
• Drop ConnectはDrop Outより性能がいいが、乱数の与え方が異なると同じ性能を達成するのが難しいので、Drop Outが一般的に使われている

学習率の最適化

• SGD
  • Stochastic Gradient Descent、確率的勾配降下法
  • $\theta \leftarrow \theta - \eta \frac{\partial L}{\partial \theta}$
• Momentum
  • $v \leftarrow \alpha v - \eta \frac{\partial L}{\partial \theta}$
  • $\theta \leftarrow \theta + v$
  • $0 \leq \alpha < 1$：速度減衰のパラメータ
• Nesterov（ネステロフ）
  • 理論
    • $v \leftarrow \alpha v - \eta \frac{\partial L}{\partial (\theta + \alpha v)}$
    • $\theta \leftarrow \theta + v$
  • 実装
    • $\Theta \leftarrow \theta + \alpha v$
    • $v \leftarrow \alpha v - \eta \frac{\partial L}{\partial \Theta}$
    • $\Theta \leftarrow \Theta + \alpha^2 v - (1 + \alpha)\eta \frac{\partial L}{\partial \Theta}$
• AdaGrad：勾配の二乗和が加算され続けて、パラメータの更新幅は小さくなっていく
  • $h \leftarrow h + \frac{\partial L}{\partial \theta} \otimes \frac{\partial L}{\partial \theta}$
  • $\theta \leftarrow \theta - \eta \frac{1}{\epsilon + \sqrt{h}} \otimes \frac{\partial L}{\partial \theta}$
• RMSProp：最近の勾配を重視し、AdaGradでは更新が進まなくなる問題を解決
  • $h \leftarrow \rho h + (1 - \rho) \frac{\partial L}{\partial \theta} \otimes \frac{\partial L}{\partial \theta}$
  • $\theta \leftarrow \theta - \eta \frac{1}{\varepsilon + \sqrt{h}} \otimes \frac{\partial L}{\partial \theta}$
• Adam：
  • RMSPropとモメンタム法を組み合わせ
  • モメンタムは勾配の一次モーメントの推定
  • 一次モーメントと二次モーメント両方に対して、学習ステップに応じたバイアス（偏り）補正が導入
  • $m \leftarrow \rho_1 m + (1 - \rho_1) \frac{\partial L}{\partial \theta}$
  • $v \leftarrow \rho_2 v + (1 - \rho_2) \frac{\partial L}{\partial \theta} \otimes \frac{\partial L}{\partial \theta}$
  • バイアス修正
    • $\hat{m} \leftarrow \frac{\hat{m}}{1 - \rho^t_1}$
    • $\hat{v} \leftarrow \frac{\hat{v}}{1 - \rho^t_2}$
  • $\theta \leftarrow \theta - \eta \frac{1}{\sqrt{\hat{v}} + \varepsilon} \otimes \hat{m}$

https://www.dragonarrow.work/articles/195

自己符号化器（Autoencoder）

応用例：異常検知、ノイズ除去、データ生成

h = \phi_1 (W_1 x + b_1) \\
\hat{x} = \phi_2(W_2 h + b_2)

１番目の式は符号化器（encoder）$f$。
２番目の式は複合化器（decoder）$g$。
中間表現$h$の次元は通常入力$x$より小さい。いわゆる不完備（undercomplete）な自己符号化器。

損失関数は$L(x, g(f(x)))$。

雑音除去自己符号化器（denoising autoencoder, DAE）

損失関数は$L(x, g(f(\tilde{x})))$。$\tilde{x}$は雑音により破損した$x$のコピー。

縮小自己符号化器（contractive autoencoder, CAE）：損失関数にペナルティ項

\Omega = \lambda \sum_i || \triangledown_x h_i ||^2 

を課す。入力にわずかな違いによる影響を受けにくくなる。

畳み込み

• MobileNet
  • depthwise畳み込み
    • チャンネル方向への畳み込みは行わずに、チャンネルごとに畳み込みを行う
    • チャンネル数$c_{\text{in}} = c_{\text{out}}$
    • 畳み込みパラメータ数：$c_{\text{in}}f^2$（$f$はフィルターのサイズ）
  • pointwise畳み込み
    • フィルタサイズを1とした畳み込み
    • 畳み込みパラメータ数：$c_{\text{in}}c_{\text{out}}$
• ダイレイト畳み込み：少ないパラメータ数で広範囲の畳み込み
• 転置畳み込み
  • 入力データを拡大するためにデータを補完してから畳み込みを行ウ
  • 生成モデルなどで小さな画像から大きな画像を作成する際に使う

画像認識

• GoogLeNet
  • Inception Module
  • Auxiliary Loss
  • Global Average Pooling クラス分類確率を出力する際に使う
• VGG
  • フィルタサイズ3x3
  • 大きなフィルタで畳み込むのと同等
• ResNet
  • ショートカット
  • 勾配消失の問題解決
  • 特徴マップ同士を足し合わせる
  • 100層超えても学習可能
• DenseNet
  • ショートカット
  • Dense Block
  • 特徴マップをチャンネル方向に結合

物体検知

非最大値抑制：信頼度スコアが最も高いバウンディングボックスを採用する

YOLO

• You Only Look Once
• 物体検出とクラス分類をCNNでまとめて行う
• 入力画像を複数の小領域に分割し、各小領域ごとにクラス分類とバウンディングボックスの位置や大きさなどの回帰を行う
• 処理速度はFaster R-CNNより高速だが精度は劣る
• YOLO v3の出力は13x13、26x26、52x52の3種類のテンソルとなる

SSD

• Single Shot multibox Detector
• 大きさ（解像度）の異なる複数の特徴マップを使ってクラス分類やバウンディングボックス回帰を行う
• 高速かつYOLOより高精度

R-CNN

• 物体候補領域の抽出と各領域に対するCNNを組み合わせる
• 色や濃淡勾配などの特徴が類似する領域に分別し、類似度が高い隣接領域を結合
• 欠点：物体候補領域の抽出はSelective Searchで行う、且つ複数の学習のモデルは個別で学習が必要で、処理速度が遅い

Fast R-CNN

分類とバウンディングボックス回帰の２つのタスクを同時に学習する。マルチタスク学習です。
画像全体の特徴抽出にCNNを使い、R-CNNより速い。

Faster R-CNN

• 領域提案ネットワーク（Region Proposal Network）で物体の候補領域抽出にもCNNを使い、Fast R-CNNより速い
• $k$個それぞれ異なるスケールとアスベクト比を持つアンカーボックス
• 正例（物体）：IoU（Intersection over Union）が最大のアンカーボックス
• アンカーボックスの数：$H \times W \times k$

損失関数：

L(\{p_i\},\{t_i\}) = \frac{1}{N_{\text{cls}}} \sum_i L_{\text{cls}} (p_i, p_i^*) + \lambda \frac{1}{N_{\text{reg}}} \sum_i p_i^* L_{\text{reg}}(t_i, t_i^*)

• $i$：ミニバッチ内でのアンカーボックスのインデックス
• $p_i$：アンカーボックス$i$が物体である確率
• $p_i^*$：正解ラベル、アンカーボックスが正例（物体）の時は1、負例（背景）の時は0
• $t_i$：予測された座標ベクトル
• $t_i^*$：真の座標ベクトル
• $L_{\text{cls}}$：分類損失、対数損失を使う
• $L_{\text{reg}}(t_i, t_i^\ast) = R(t_i - t_i^\ast)$：回帰損失、$R$はロバスト損失関数（smooth $L_1$ loss）。係数$p_i^*$は正例（物体）のアンカーボックスの場合にのみ、回帰損失が加味されるようにするため

R-FCN

• Region-of-Interest（RoI）と呼ばれる画像領域に対し、クラス分類とバウンディングボックスの推定をCNNでまとめて行う
• Faster R-CNNより速い

Mask R-CNN

• 物体検知 + セグメンテーション
• Faster R-CNNより少し遅い

セグメンテーション

• 条件付き確率場（Conditional Random Field）
  • 画像をグラフとして表現する
  • いくつかのピクセルが孤立して異なるクラスに割り当てられてしまう問題を解決する
• 全畳み込みネットワーク
  • Fully Convolutional Network, FCN
  • 全結合層を用いずに、畳み込み層のみを用いる
  • 入力画像サイズが異なっていても単一のモデルで予測できる
  • 特徴マップを各画素ごとに足し合わせる
• SegNet
  • 解像度を下げる際の最大値プーリングの情報を覚えておき、特徴マップの解像度を上げる
  • FCNより精度が高く、メモリ効率がいい
  • 自己符号化器型の構造
• U-Net
  • 医療分野における細胞のセグメンテーション
  • U字型のアーキテクチャによって、様々な解像度の特徴マップを組み合わせた予測
  • 自己符号化器型の構造
  • 特徴マップをチャンネル方向に結合

時系列モデル

LSTM（Long Short Term Memory）

• 目的：勾配消失を防ぐ
• CEC（Constant Error Carousel）：過去のデータを保持する機能、記憶セル
  • $C_t = f_t \otimes C_{t-1} + i_t \otimes \tilde{C_t}$
  • $\otimes$：要素ごと（element-wise）の乗算（アダマール積）
  • $\tilde{C_t} = tanh(x_t W_x^c + h_{t-1} W_h^c + b^c) $は新しい記憶セル
  • $f_{i,j,t}$が0.2ならば、その要素の情報の80%を忘却
• ゲート：情報の保持と**消去（忘却）**の仕組み
  • 忘却ゲート：どの情報を忘却（Forget）するかを調整する
    • $f_t = \sigma (x_t W_x^f + h_{t-1} W_h^f + b^f)$
  • 入力ゲート：記憶セルに追加する情報の取捨選択を行う
    • $i_t = \sigma (x_t W_x^i + h_{t-1} W_h^i + b^i)$
  • 出力ゲート：記憶セルの情報が隠れ状態$h_t$にとってどの程度重要であるかを表す
    • $o_t = \sigma (x_t W_x^o + h_{t-1} W_h^o + b^o)$
• 隠れ状態 $h_t = o_t \otimes tanh(C_t)$
• 活性化関数
  • ゲートに0〜1に制約されるシグモイド関数を使って、データを通過させる割合を決定
  • 新しい記憶セルにtanh関数を使う

GRU（Gated Recurrent Unit）

• 目的：勾配消失を防ぎながら、モデルをシンプルにし、計算スピードを向上させる
• リセットゲート：過去の隠れ層$h_{t-1}$の情報をどれだけ無視するかを決定
  • $r_t = \sigma (x_t W_x^r + h_{t-1} W_h^r + b^r)$
• アップデートゲート：LSTMでの忘却ゲートと入力ゲートが統合されたもの
  • $z_t = \sigma (x_t W_x^z + h_{t-1} W_h^z + b^z)$
• 新しい隠れ状態 $\tilde{h}_t = tanh(x_t W_x^{\tilde{h}} + s W_h^{\tilde{h}} + b^{\tilde{h}})$
  • $s = r \otimes h_{t-1}$
• $h_t = (1 - z) \otimes h_{t-1} + z \otimes \tilde{h}_t$
• 勾配消失が発生しにくい理由：LSTMと同様、$h_t$は$tanh$や行列積のノードを通らず、「＋」と「×（アダマール積）」のノードしか通らないため

LSTMとGRUとの大きな違い

LSTM：隠れ状態と記憶セルの2つを使う
GRU：隠れ状態のみを使う

Echo State Network

• 入力から隠れ層のマッピングや隠れ層間の遷移の重みは固定する
• 隠れ層から出力への変換の部分だけ学習する
• メリット：学習は単なる線形回帰の問題なので
  • 勾配消失や勾配爆発はない
  • 学習速度が速い

Leaky Unit

Self-Connetion：Unitの値の更新の際に自分の過去の値をそのまま利用する

u_t = \alpha u_{t-1} + (1 - \alpha) v_t

移動平均の効果がある

WaveNet

統計的パラメトリック音声合成とDilated Causal Convolutionの組み合わせ

生成モデル

入力分布と出力分布を両方モデル化する。

GAN

TTUR（Two-Timescale Update Rule）：GeneratorよりもDiscriminatorの学習率が大きくして収束速度を向上させる

GAN vs Conditional GAN：後者ではDiscriminatorに正解ラベルが与えられ、Generatorに偽ラベルが与えられる

画像元：https://learnopencv.com/conditional-gan-cgan-in-pytorch-and-tensorflow/

強化学習

方策勾配法

確率的方策$\pi$のパラメータ$\theta$を勾配法で更新していく方法。

前提：$\theta$が微分可能。

更新は勾配上昇法でやる。

\theta^{t+1} = \theta^t + \eta \triangledown_\theta J(\theta)

方策勾配定理

\triangledown_\theta J(\theta) = \sum_s d^{\pi_\theta}(s) \sum_a \triangledown_\theta \pi_\theta (a|s, \theta) Q^{\pi_\theta}(s,a) \\
d^{\pi_\theta}(s) = \sum_{k=0}^{\infty} \gamma^k P^{\pi_\theta} (s_k = s|s_0)

$d^{\pi_\theta}(s)$は$s_0$から開始して方策$\pi_\theta$に従って行動した場合どれだけ頻繁に状態$s$を訪れるかを表す（割引率$\gamma$で割引付き）。
$P^{\pi_\theta} (s' \mid s)$は状態の推移の確率。

\triangledown_\theta \log \pi_\theta (a \mid s, \theta) = \frac{\partial \pi_\theta (a \mid s, \theta) }{\partial \theta} \frac{1}{\pi_\theta (a \mid s, \theta)} 

を用いると

\triangledown_\theta J(\theta) = E_{\pi_\theta} [\triangledown_\theta \log \pi_\theta (a \mid s,\theta) Q^{\pi_\theta}(s,a)] 

モンテカルロ法で

\triangledown_\theta J(\theta) = E_{\pi_\theta} [f(s,a)] \approx \frac{1}{N} \sum_{n=1}^N \frac{1}{T} \sum_{t=1}^T \log \pi_\theta (a_t^n \mid s_t^n, \theta) Q^{\pi_\theta} (s_t^n, a_t^n)

$N$はエピソード数、$T$は時間ステップ数。

REINFORCEアルゴリズム

• エピソード的タスク
  • 例：囲碁
  • 価値関数Qを各エピソード内でモンテカルロ法で観測した実際の報酬系列で近似
• 連続タスク（状態が連続値で計算困難の場合）
  • 例：ロボット
  • ある時刻$t$で得られた**$r_t$（即時報酬）の観測値との誤差を使って、出力を状態価値関数**とするニューラルネットで近似して算出

動的計画法 vs モンテカルロ法 vs TD学習

• 動的計画法
  • 環境の完全なモデルを必要とし、適用できる場面は限られている
  • 代表：方策反復法、価値反復法
• モンテカルロ法
  • 遷移のサンプルを取得し、得られた収益を平均化し、価値関数を推定する
  • 価値関数または方策の改善はエピソード終了後に行う
• TD学習（temporal difference learning）
  • 目標価値と現在価値のずれを修正していって、価値関数を推定する。そのずれはTDといい
  • 代表：SarsaとQ学習

Sarsa学習

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]

On-Policy、行動を決定する方策と行動価値関数の更新に利用される方策が同じ。
Q学習と比べ、行動価値の小さい探索結果が反映されやすいが、計算が不安定。
方策勾配法を利用しない。

Q学習・DQN

行動価値関数$Q$の更新が行動の決定方法に依存しない。
Sarsaより行動価値関数の収束が早くなることが多いが、保証されているわけではない。
Off-Policy、行動を決定する方策と行動価値関数の更新に利用される方策が違う。

目標値

r + \gamma \max_{a'} Q(s',a';\theta)

TD（Temporal Difference）誤差、いわゆる損失関数

r + \gamma \max_{a'} Q(s',a';\theta) - Q(s,a;\theta)

• 体験再生：Agentが経験した状態、行動、報酬と状態の遷移先をメモリに保存し、価値を計算するときにメモリから取り出す
  • 利点１：同じ経験を何回も学習に使えて、学習効率がいい
  • 利点２：経験はランダムに取り出され、入力系列の相関が軽減され、更新の分散が軽減される
  • 利点３：パラメータの振動を避ける
• 目標Qネットワーク
  • 目標値を算出するネットワークのパラメータ$\overline{\theta}$を固定して、一定期間更新する
  • $r + \gamma \max_{a'} Q(s',a';\overline{\theta}) - Q(s,a;\theta)$
  • 利点：Q関数に起因するTD誤差の変動が小さくなり、学習が安定になる
• 報酬クリッピング
  • 成功した場合には1
  • 失敗した場合には-1
  • それ以外の場合には0
  • 利点：学習を安定させる
• Huber関数
  • 誤差が-1~1の間は二乗誤差の値となり
  • -1より小さいときや1より大きいときには誤差の絶対値をとる
  • 利点：誤差が-1~1よりも外側にあるときは、誤差が二乗誤差より小さい

AlphaGo

• 方策ネットワーク：局面を入力にして、打ち手の確率を返す
• 状態価値ネットワーク：局面を入力にして、勝率を返す
  • CNNで学習する
• 学習
  • ステップ1：SL（Supervised Learning、教師あり）方策ネットワークの学習
    • 人間対戦データ利用
    • 入力：盤面
    • 出力：それぞれの手を選ぶ確率
    • CNNで学習する
    • パラメータ更新：$\Delta\sigma = \frac{\alpha}{m} \sum_{k=1}^m \frac{\partial \log p_\sigma(a^k | s^k)}{\partial \sigma} $
      • $\alpha$：学習率
      • $a$：行動（手）
      • $s$：状態（盤面）
      • $m$：ミニバッチのサイズ
    • ロールアウト方策（$p_\pi$）も人間対戦データで学習
      • Logistic回帰で次の手を予測する
  • ステップ2：RL（強化学習）方策ネットワークの学習
    • 自己対戦
    • 構造はSL方策ネットワークと同じ、初期値はステップ1で学習したパラメータ
    • 方策勾配法
    • パラメータ更新：$\Delta\rho = \frac{\alpha}{n} \sum_{i=1}^n \sum_{t=1}^{T^i} \frac{\partial \log p_\rho (a_t^i | s_t^i)}{\partial \rho}$
      • $T^i$：$i$番目の対戦の最終タイムステップ
      • $z_i^t$：$i$番目の対戦のタイムステップ$t$における報酬
  • ステップ3：状態価値ネットワークの学習
    • 入力：盤面
    • 出力：勝つ確率（-1から1）
    • 勾配降下法
    • パラメータ更新：$\Delta \theta = \frac{\alpha}{m} \sum_{k=1}^m (z^k - v_\theta(s^k)) \frac{\partial v_\theta(s^k)}{\partial \theta}$
    • 教師あり、データを作るために対戦する
      • $t = 1, \ldots, U - 1$の時間ステップではSL方策ネットワークで手を選ぶ
      • $t = U$は乱数的に手を選ぶ
      • $t = U+1, \ldots, T$はRL方策ネットワークで手を選ぶ
• 学習後の実戦
  • モンテカルロ木探索
    • Rollout：ある局面から黒番と白番が互いに手を選んで終局まで進める
      • Logistic回帰で次の手を予測する
    • 選択（Selection）
      • 行動選択基準：$a_t = \text{argmax}_a(Q(s_t, a) + u(s_t, a))$
        • $Q(s_t, a)$：行動価値
        • $u(s_t, a) = c_\text{puct}P(s,a)\frac{\sqrt{\sum_b N_r(s,b)}}{1 + N_r(s,a)}$
          • 未探索のノードへの探索を促進する信頼上限
          • 多く訪問した手の採用確率を低くし、探索を広くする
          • $c_\text{puct}$：定数
          • $P(s,a)$：SL方策ネットワークによって算出される事前確率
          • $N_r(s,a)$：ロールアウト回数
    • 展開（Expansion）：訪問回数が閾値を超えたら、$s$から行動した結果の状態$s'$を探索木に追加する
    • 評価（Evaluation）：価値ネットワークとロールアウトで報酬を計算する
      • 勝ったら1
      • 負けたら-1
    • 記録（Backup）：統計量を更新する
      • 負けた回数$n_{rl}$
      • 葉で価値ネットワークで評価した回数$N_v(s,a)$
      • $N_v(s,a)$回の評価に対する行動価値の総和$W_v(s,a)$
      • ロールアウトの訪問回数$N_r(s,a)$
      • $N_r(s,a)$回の訪問に対する行動価値の総和$W_r(s,a)$
      • 行動価値：$Q(s,a) = (1 - \lambda) \frac{W_v(s,a)}{N_v(s,a)} + \lambda \frac{W_r(s,a)}{N_r(s,a)}$
    • 繰り返しの探索が終了したら、最も訪問回数が多い行動を次の指してに採用する

AlphaGo Zero

• AlphaGoの4つのDNN（ロールアウト方策、SL方策、RL方策、価値）を1つのデュアルネットワークにした
• 層をより深く40層にした
• 探索木において、$Q(s,a)$の計算にロールアウトによる評価（$N_r(s,a)$と$W_r(s,a)$）をやめた
  • 探索をより深く行える

さまざまな数式

グラムシュミットの直交化法

$n$個のベクトルの組$\lbrace a_1, a_2, \ldots, a_n\rbrace$から正規直交系$\lbrace e_1, e_2, \ldots, e_n\rbrace$を構成する場合

1. $e_1 = \frac{a_1}{||a_1||}$
2. $f_2 = a_2 - (a_2, e_1) e_1, e_2 = \frac{f_2}{||f_2||}$、$(a_2, e_1)$は内積です　
3. $f_n = a_n - \sum_{i=1}^{n-1} (a_n, e_i) e_i, e_n = \frac{f_n}{||f_n||}$

固有値分解

A = P^{-1} \Lambda P

• $\Lambda$：固有値を左上から右下に向かって並べた対角行列
• $P$：固有ベクトルを列ベクトルとして並べた行列

特異値分解

A = U D V^T

• $U$：$AA^T$の固有ベクトルからなる直行行列
• $D$：特異値を左上から右下に向かって並べた行列
  • 特異値は$AA^T$の固有値の正の平方根
• $V$：$A^T A$の固有ベクトルからなる直行行列

ノルム

L_1 = \sum_i^n |x_i| \\
L_2 = \sqrt{\sum_i^n x_i^2} \\
L_\infty = \max_i |x_i|  

統計

• 分散：$S_x = E[(X - \overline{X})^2]$
• 共分散：$S_{xy} = Cov(X,Y) = E[(X - \overline{X})(Y - \overline{Y})] = \frac{1}{n} \sum_{i=1}^n (x_i - \overline{x})(y_i - \overline{y})$
• 相関係数：$r_{xy} = \frac{S_{xy}}{S_x S_y}$

情報理論

• 情報$x$の自己情報量：$I(x) = -\log_e P(x)$、単位はナット
• シャノン：$i(x) = -\log_2 P(x)$、単位はビット
• エントロピー（平均情報量）：$H(X) = - \sum_i p(x_i) log_2 p(x_i)$
• KL（カルバック・ライブラー）ダイバージェンス
  • $P(x)$、$Q(x)$が離散型確率分布のとき：$D_{KL}(P||Q) = \sum_i P(x_i) \log \frac{P(x_i)}{Q(x_i)}$
  • $P(x)$、$Q(x)$が連続型確率分布のとき：$D_{KL}(P||Q) = \int_{-\infty}^{\infty} P(x) \log \frac{P(x)}{Q(x)}$
  • 常に0以上であり、0となるのは$P(x)$と$Q(x)$が一致するときのみ
• JS（ジェンセン・シャノン）ダイバージェンス：$D_{JS}(P||Q) = \frac{1}{2} (D_{KL}(P||M) + D_{KL}(Q||M))$、$M(x) = \frac{P(x) + Q(x)}{2}$
• 交差エントロピー
  • KLダイバージェンスに似ている
  • $P(x)$、$Q(x)$が離散型確率分布のとき：$H(P, Q) = -\sum_i P(x_i) \log Q(x_i)$
  • $P(x)$、$Q(x)$が連続型確率分布のとき：$H(P, Q) = -\int_{-\infty}^{\infty} P(x) \log Q(x)$
  • $H(P, Q) = H(P) + D_{KL}(P||Q)$
  • 真の分布$P(x)$での期待値をデータ$D$による平均に置き換える（モンテカルロ積分）：$\tilde{H}(P,Q) = - \frac{1}{n} \sum_{i=1}^n \log Q(x_i;\theta)$

Sigmoid

y = \frac{1}{1 + e^{-z}}

Softmax

h_k(x) = \frac{e^{x_k}}{\sum_{i=1}^n e^{x_i}}

def softmax(x):
    x = x.T # 縦方向(axis=0)にmax、sumを計算するため転置
    x = x - np.max(x, axis=0) # オーバーフロー対策
    y = np.exp(x) / np.sum(np.exp(x), axis=0)
    return y.T

逆伝播

\frac{\partial y_k}{\partial x_j} = y_k (\delta_{kj} - y_j) \\
\frac{\partial L}{\partial x_k} = y_k \left(\frac{\partial L}{\partial y_k} - \sum_i \frac{\partial L}{\partial y_i} y_i \right)

Cross Entropy

l(y, t) = -\sum_{i=1}^k t_i \log y_i

$t_i$：$i$番目のクラスの正解ラベル。正解ラベルには１、間違いのラベルは０
$y_i$：$i$番目のクラスの予測値、０から１の値

def cross_entropy_error(y, t):
    delta = 1e-7 
    return -np.sum(t * np.log(y + delta))

逆伝播

\frac{\partial l}{\partial x_j} = y_j - t_j

Affine変換

H = XW + B

逆伝播

\frac{\partial L}{\partial W} = X^T \frac{\partial L}{\partial H} \\
\frac{\partial L}{\partial X} = \frac{\partial L}{\partial H} W^T

$B$の勾配は$\frac{\partial L}{\partial H}$のバッチ方向の和です。

tanh

f(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}} \in (-1, 1)