機械学習とかコンピュータビジョンとか

CVやMLに関する勉強のメモ書き。

OpenAIのSpinning Upで強化学習を勉強してみた　その３

Reinforcement Learning

はじめに

その３ということで一応Introduction to RLの最終回．今回勉強したページはこちら

Part 3: Intro to Policy Optimization

今回はpolicy optimizationの基礎理論とその実装について．

Deriving the Simplest Policy Gradient

まずは\thetaでparameterizeされた確率的なpolicy \pi_\thetaを考える．目標はexpected return J(\pi_\theta)=\underset{\tau\sim\pi_\theta}{E}[R(\tau)]の最大化で，今回R(\tau)はfinite-horizon undercounted return（減衰しない固定長区間の報酬の和）とする（ただしinfinite-horizon discounted returnでも結果は同じ）．

基本的には次のような勾配上昇法によってpolicyを最適化していく．

\displaystyle \theta_{k+1}=\theta_k+\alpha\nabla_\theta J(\pi_\theta)|_{\theta_k}

\nabla_\theta J(\pi_\theta)はpolicy gradientと呼ばれ，policy gradientを使ってpolicyの最適化を行うアルゴリズムをpolicy gradient algorithmsというらしい．

ということでpolicy gradientを求めてみる．まずはpolicy gradientを計算するのに必要なtrajectoryの確率の微分を求める．Policy \pi_\thetaにおけるtrajectory \tau=(s_1,a_0,\dots,s_{T+1})の確率は次のように与えられる．

\displaystyle P(\tau|\theta)=\rho_0(s_0)\prod_{t=0}^TP(s_{t+1}|s_t,a_t)\pi_\theta(a_t|s_t)

ここで連鎖律と対数の導関数\nabla_\theta\log P(\tau|\theta)=\frac{1}{P(\tau|\theta)}\nabla_\theta P(\tau|\theta)を利用して次のようにP(\tau|\theta)の導関数を表現．

\displaystyle \nabla_\theta P(\tau|\theta)=P(\tau|\theta)\nabla_\theta\log P(\tau|\theta)

Trajectoryの確率の対数は

\displaystyle \log P(\tau|\theta)=\log\rho_0(s_0)+\sum_{t=0}^T\left(\log P(s_{t+1}|s_t,a_t)+\log\pi_\theta(a_t|s_t)\right)

となることから\nabla_\theta P(\tau|\theta)は次のようになる．

\displaystyle \nabla_\theta\log P(\tau|\theta)=\nabla_\theta\log\rho_0(s_0)+\sum_{t=0}^T\left(\nabla_\theta\log P(s_{t+1}|s_t,a_t)+\nabla_\theta\log\pi_\theta(a_t|s_t)\right)=\sum_{t=0}^T\nabla_\theta\log\pi_\theta(a_t|s_t)

最後の等式は\rho_0(s_0),P(s_{t+1}|s_t,a_t)が\thetaと無関係なことから導かれる．以上から最終的に求めたいpolicy gradientは次のようになる．

\displaystyle \nabla_\theta J(\pi_\theta)=\nabla_\theta\underset{\tau\sim\pi_\theta}{E}[R(\tau)]=\nabla_\theta\int_\tau P(\tau|\theta)R(\tau)=\int_\tau\nabla_\theta P(\tau|\theta)R(\tau) \\ \displaystyle =\int_\tau P(\tau|\theta)\nabla_\theta\log P(\tau|\theta)R(\tau)=\underset{\tau\sim\pi_\theta}{E}[\nabla_\theta\log P(\tau|\theta)R(\tau)]\\ \displaystyle =\underset{\tau\sim\pi_\theta}{E}\left[\sum_{t=0}^T\nabla_\theta\log\pi_\theta(a_t|s_t)R(\tau)\right]

最後の期待値の計算はサンプル平均として計算することで勾配を実際に計算することが可能．すなわち，trajectoryの集合\mathcal{D}=\{\tau_i\}_{i=1,\dots,N}がエージェントの行動の結果得られたとした時，policy gradientは次のように計算される．

\displaystyle \hat{g}=\frac{1}{|\mathcal{D}|}\sum_{\tau\in\mathcal{D}}\sum_{t=0}^T\nabla_\theta\log\pi_theta(a_t|s_t)R(\tau)

ここにはpolicyの対数が微分可能であるという仮定と，trajectoryのデータを集めるために環境においてpolicyを実行可能という仮定が入っていることには注意．ただ，実際は自動微分のおかげで勝手に計算してくれるので実装に関してはめちゃくちゃ簡単にできる．

Implementing the Simplest Policy Gradient

Spinning upのgithubのrepositoryにpolicy gradient algorithmの実装例があって，わずか122行で実装可能とのこと．ただ自分はpytorch派なので，pytorchで再現実装してみました（元のコードをなるべく崩さないように書いたので不自然な記述方法があったりするので注意）．以下コード．

import torch
import torch.nn as nn
import torch.optim as optim
import numpy as np
import gym
from gym.spaces import Discrete, Box


def mlp(sizes, activation=nn.Tanh, output_activation=None):
    layers = []
    for i in range(1,len(sizes)-1):
        layers.append(nn.Sequential(
            nn.Linear(sizes[i-1], sizes[i]), activation()
        ))
    layers.append(nn.Linear(sizes[-2], sizes[-1]))
    if output_activation is not None:
        layers.append(output_activation())
    return nn.Sequential(*layers)

def multinomial(logits, num_samples=1):
    return torch.distributions.Multinomial(num_samples, logits=logits).sample()

def train(env_name="CartPole-v0", hidden_sizes=[32], lr=1e-2,
        epochs=50, batch_size=5000, render=False):

        if torch.cuda.is_available():
            device = "cuda"
        else:
            device = "cpu"

        # make environment, check spaces, get obs / act dims
        env = gym.make(env_name)
        assert isinstance(env.observation_space, Box), \
            "This example only works for envs with continuous state spaces."
        assert isinstance(env.action_space, Discrete), \
            "This example only works for envs with discrete action spaces."

        obs_dim = env.observation_space.shape[0]
        n_acts  = env.action_space.n

        # make core of policy network
        policy = mlp([obs_dim] + hidden_sizes+[n_acts]).to(device)

        optimizer = optim.Adam(policy.parameters(), lr=lr)

        def train_one_epoch():
            # make some empty lists for logging
            batch_obs     = []
            batch_acts    = []
            batch_weights = []
            batch_rets    = []
            batch_lens    = []

            # make
            obs     = env.reset()
            done    = False
            ep_rews = []

            finished_rendering_this_epoch = False

            while True:
                with torch.no_grad():
                    # rendering
                    if not finished_rendering_this_epoch:
                        env.render()

                    # save obs
                    batch_obs.append(obs.copy())

                    logits = policy(torch.from_numpy(obs[None]).float().to(device))
                    act    = multinomial(logits).squeeze().to("cpu").detach().numpy()
                    obs, rew, done, _ = env.step(act.argmax(0))

                    # save obs
                    batch_acts.append(act)
                    ep_rews.append(rew)

                    if done:
                        # if episode is over, record info about episode
                        ep_ret, ep_len = sum(ep_rews), len(ep_rews)
                        batch_rets.append(ep_ret)
                        batch_lens.append(ep_len)

                        # the weight for each logprob(a|s) is R(tau)
                        batch_weights += [ep_ret] * ep_len

                        # reset episode-specific variables
                        obs, done, ep_rews = env.reset(), False, []

                        # won't render again this epoch
                        finished_rendering_this_epoch = True

                        # end experience loop if we have enough of it
                        if len(batch_obs) > batch_size:
                            break

            # take a single policy gradient update step
            batch_obs     = torch.from_numpy(np.array(batch_obs)).float().to(device)
            batch_acts    = torch.from_numpy(np.array(batch_acts)).float().to(device)
            batch_weights = torch.from_numpy(np.array(batch_weights)).float().to(device)
            logits = policy(batch_obs)
            loss = -( batch_weights * (batch_acts * nn.functional.log_softmax(logits, 1)).sum(1)).mean()

            optimizer.zero_grad()
            loss.backward()
            optimizer.step()
            return loss, batch_rets, batch_lens
        
        for i in range(epochs):
            batch_loss, batch_rets, batch_lens = train_one_epoch()
            print('epoch: %3d \t loss: %.3f \t return: %.3f \t ep_len: %.3f'%
                (i, batch_loss, np.mean(batch_rets), np.mean(batch_lens)))
        env.env.close()

if __name__ == '__main__':
    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument('--env_name', '--env', type=str, default='CartPole-v0')
    parser.add_argument('--render', action='store_true')
    parser.add_argument('--lr', type=float, default=1e-2)
    args = parser.parse_args()
    print('\nUsing simplest formulation of policy gradient.\n')
    train(env_name=args.env_name, render=args.render, lr=args.lr)

雑に移植しただけなのでコードは元のやつが参考になるかと．

サンプルコードの問題設定はCartPoleで棒が倒れないようにするあれ．強化学習の環境についてはopenai gymを使って実装．今回のCartPoleについてはここ参照．観測としてはcartの位置と速度，poleの角度と速度の4次元が得られる．Policyは2層のニューラルネットなので観測の4次元を\mathbf{x}とすれば\pi_\theta(\mathbf{x})=\mathbf{SoftMax}(\mathbf{W}\cdot\mathrm{Tanh}(\mathbf{W}\cdot\mathbf{x}+\mathbf{b})+\mathbf{b})のように表現される．行動はcartを左か右に動かすかの2択なのでpolicyの出力は2次元．出力された確率からサンプリングによって行動を選択し，poleが倒れるなどの終了条件を満たすまで繰り返しサンプルを収集．rewardは毎行動ごとに1与えられる．よって最大化すべき関数は選択された行動を示すone-hotベクトルをaとすれば\frac{1}{T}\sum_{t=0}^Ta_t\log\left(\pi_\theta(s_t)\right)R(\tau)として計算できる．

コード内でlossを計算しているいわゆるloss functionの役割を果たしている式があるが，これは厳密にはloss functionではない．基本的にloss functionはデータ分布が固定の元で計算されるが，この場合では直近のpolicyにおいてサンプルされたデータで学習を行うためデータ分布がパラメータ（policy）に依存する．また，基本的にはloss functionは予測結果の良し悪しをはかる指標となるが，ここでのloss functionは現在のパラメータの良し悪しをはかる．要は何が言いたいかというと，強化学習においてデータはエージェントの行動の結果得られるため，行動を決めるpolicyのパラメータ次第でデータの分布が変わるのでいわゆるloss functionとしての役割とは少し違うということ．

Expected Grad-Log-Prob Lemma

ここではExpected Grad-Log-Prod (EGLP)と呼ばれる命題を解説．

・EGLP Lemma

ここではpolicy gradientsを通して使われる中間的な結果を導く． ある確率変数xが従う\thetaでparameterizeされた確率分布はP_\theta次を満たす．

\displaystyle \underset{x\sim P_\theta}{E}[\nabla_\theta\log P_\theta(x)]=0

・証明

P_\theta(x)は確率分布なので\int_xP_\theta(x)=1．\thetaについて微分すれば\nabla_\theta\int_xP_\theta(x)=\nabla_\theta 1=0．この関係を用いれば

\displaystyle 0=\nabla_\theta\int_xP_\theta(x)=\int_x\nabla_\theta P_\theta(x)=\int_xP_\theta(x)\nabla_\theta\log P_\theta(x)\\ \displaystyle \therefore 0=\underset{x\sim P_\theta}{E}[\nabla_\theta\log P_\theta(x)]

Don't Let the Past Distract You

ここまでpolicy gradientを以下のように表現した．

\displaystyle \nabla_\theta J(\pi_\theta)=\underset{\tau\sim\pi_\theta}{E}\left[\sum_{t=0}^T\nabla_\theta\log\pi_\theta(a_t|s_t)R(\tau)\right]

この勾配を使えば報酬の和であるR(\tau)に比例した行動の対数確率を増加させることができるが，実はこれはあまりよくないとのこと．

エージェントは結果に基づいて行動を決めるべきだが，行動の前に得られる報酬は行動がどれくらいよかったかには全く関係がない．この問題を解決するために次のようにpolicy gradientを表現する．

\displaystyle \nabla_\theta J(\pi_\theta)=\underset{\tau\sim\pi_\theta}{E}\left[\sum_{t=0}^T\nabla_\theta\log\pi_\theta(a_t|s_t)\sum_{t'=t}^TR(s_{t'},a_{t'},s_{t'+1})\right]

何が変わったかというと，rewardの計算がもともとR(\tau)=\sum_{t=0}^TR(s_t,a_t,s_{t+1})と行動を起こした時刻に関係なく全ての時刻に対する総和の計算だったのに対し，行動を選択した時刻t以降の足し合わせ\sum_{t'=t}^TR(s_{t'},a_{t'},s_{t'+1})に変わっている．こうすることによって，行動を起こす以前の報酬を考慮しない形になるので良いだろうということ．ちなみにこれをreward-to-go policy gradientと呼び\hat{R}_t\overset{\cdot}{=}\sum_{t'=t}^TR(s_{t'},a_{t'},s_{t'+1})と表す．

Implementing Reward-to-Go Policy Gradient

ということでreward-to-go policy gradientを実装．rewardの計算が変わるだけなのでさっきのコードを一部修正するだけで動く．具体的には次のreward-to-goを計算する関数（サンプルコードまんま）を用意．

def reward_to_go(rews):
    n = len(rews)
    rtgs = np.zeros_like(rews)
    for i in reversed(range(n)):
        rtgs[i] = rews[i] + (rtgs[i+1] if i+1 < n else 0)
    return rtgs

batch_weightsの部分を

batch_weights += list(reward_to_go(ep_rews))

に変更．これでreward-to-goバージョンのpolicy gradientになる．学習の安定性は増した気がする．

Baselines in Policy Gradients

EGLPの結果は状態のみに依存する任意の関数bに対して適用可能．

\displaystyle \underset{a_t\sim\pi_\theta}{E}[\nabla_\theta\log\pi_\theta(a_t|s_t)b(s_t)]=0

なので，次のように任意の数を引いたり足したりすることが可能．

\displaystyle \nabla_\theta J(\pi_\theta)=\underset{\tau\sim\pi_\theta}{E}\left[\sum_{t=0}^T\nabla_\theta\log\pi_\theta(a_t|s_t)\left(\sum_{t'=t}^TR(s_{t'},a_{t'},s_{t'+1})-b(s_t)\right)\right]

ここで使われる関数bはbaselineと呼ばれ，一般的な選択肢としてon-policy value function V^\pi(s_t)がある．

経験的にb(s_t)=V^\pi(s_t)とすることはpolicy gradientにおいてsampleのばらつきを減らす効果があるらしく，結果として学習の速度と安定性が向上するとのこと．ただ，実践的にはV^\pi(s_t)を正確に計算することはできないので近似計算することになる．近似計算にはニューラルネットを使うことが多く，このvalue functionを計算するvalue network V_\phiはpolicyと同時に更新されていく．

V_\phiを学習する最も単純なものは以下の二乗誤差を目的関数として学習する方法．

\displaystyle \phi_k=\underset{\phi}{\mathrm{argmin}}\underset{s_t,\hat{R}_t\sim\pi_k}{E}\left[\left(V_\phi(s_t)-\hat{R}_t\right)^2\right]

\pi_kはkエポック目のpolicyで，過去のパラメータ\phi_{k-1}から\phi_kまでに複数回のパラメータの更新が行われる．

Other Forms of the Policy Gradient

今までの内容を踏まえてpolicy gradientを一般化すると次の形になる．

\displaystyle \nabla_\theta J(\pi_\theta)=\underset{\tau\sim\pi_\theta}{E}\left[\sum_{t=0}^T\nabla_\theta\log\pi_\theta(a_t|s_t)\Phi_t\right]

\Phi_tはここまでやってきた例で言えば，\Phi_t=R(\tau)だったり，\Phi_t=\sum_{t'=t}^TR(s_{t'},a_{t'},s_{s'+1})だったり，\Phi_t=\sum_{t'=t}^TR(s_{t'},a_{t'},s_{t'+1})-b(s_t)だったりする．その他\Phi_tの選択肢として次の2つも重要．

  1. On-Policy Action-Value Function

\displaystyle \Phi_t=Q^{\pi_\theta}(s_t,a_t)

Q関数を使っても良いという証明はこちら．

  1. The Advantage Function

\displaystyle \Phi_t=A^{\pi_\theta}(s_t,a_t)=Q^\pi(s_t,a_t)-V^\pi(s_t)

Advantage functionを使っても良いというのはQ関数を使っても良いということから言える．

曰くadvantage functionを使ったpolicy gradientsはとても一般的な方法らしく，advantage functionを推定するたくさんの方法があるそうで，Generalized Advantage Estimation(GAE)の論文を読むことを推奨していた．のでまた今度読む．

まとめ

とりあえず単純なアルゴリズムで強化学習を試すというところまで．OpenAI gymがよくできていて，実装にかかるコストがめちゃくちゃ削減されているのが嬉しい．

とりあえずspinning upのintroduction to RLはこれで終わり．後は実際に色々手を動かしたり論文読んだりして各々頑張ってくれ的な感じなのでやってみようと思う．

OpenAIのSpinning Upで強化学習を勉強してみた　その２

Reinforcement Learning

はじめに

OpenAIが提供するSpinning Upで深層強化学習の勉強をしたのでメモその２．今回勉強した内容はこちら．

Taxonomy of RL Algorithms

RLアルゴリズムを手法ごとに分類しようというもの．Part2のページに木構造でいい感じにまとめた図がある．Part 2の目標として各アルゴリズムが何をどのように学習しているか，アルゴリズムの長所と短所，最近のアルゴリズムをここでの枠組みに当てはめられるようになることの三点．

Model-Free vs Model-Based RL

RLアルゴリズムを分類する上で最も重要な点の一つが，エージェントが環境のモデルを参照もしくは学習するかどうか．ここでの環境のモデルというのは状態遷移と報酬を予測する関数を意味する．

環境モデルを利用する方法は，エージェントが行動を選択した結果何が起こるかを見て計画を立てるというもの．有名な例としてはAlphaZeroがこのアプローチを利用している．将棋や囲碁のようなボードゲームでは指し手を数手先まで予想してから行動を決定する．これが行動の結果を見るということ．

逆にモデルを持たない方法は環境の真のモデルをエージェントは利用できない．仮に利用したいと思う場合には学習して獲得する必要がある．ただ学習することの大きな課題として，学習して得られた環境モデルのバイアスをエージェントが直に受け取ってしまうという点．そのため実環境においてパフォーマンスを大きく低下させる場合がある．基本的にモデルの学習は困難で，大量の時間と計算リソースを費やす必要があるとのこと．

モデルを利用するアルゴリズムをmodel-based methodsといい，その逆をmodel-free methodsという．model-freeはモデルから得られる潜在的な利得を諦める代わりに実装が単純という利点があり，今自分が読んでるpart2執筆時点ではmodel-free methodsが広く使われているということ．

What to Learn

もう一つのアルゴリズム分類基準として何を学習しているかという点がある．学習対象の候補としては以下の4つ．

・policies

・action-value functions (Q関数）

・value functions

・environment model（環境モデル）

What to Learn in Model-Free RL

Model-free RLには主に二つのアプローチが存在．

Policy Optimization

Policy \pi_\theta(a|s)を学習する方法．J(\pi_\theta)を直接または間接的に最大化することで\thetaを最適化する．この最適化はほとんどがon-policyとして行われ，実際行動した結果集められたデータを利用して最適化が行われる．また，policy optimizationは普通on-policy value function V^\pi(s)を近似するV_\phi(s)の学習も含む．

Policy optimizationの例として勾配上昇法を利用して直接最大化するA2C/A3CやJ(\pi_\theta)を上昇させるような代わりとなる目的関数を最適化するPPOアルゴリズムなどがある．

Q-Learning

Optimal action-value function Q^\ast(s,a)を近似するQ_\theta(s,a)を学習する方法．Bellman方程式に基づく目的関数を利用するのが一般的．最適化はoff-policyで行われ，エージェントの振る舞いに関わらず任意の時点で得られたデータを使って最適化が行われる．Q-learningによって選ばれる行動は次のように与えられる．

\displaystyle a(s)=\underset{a}{\mathrm{argmax}}Q_\theta(s,a)

Q-learningの例としてはDQNやC51がある．

Trade-offs Between Policy Optimization and Q-Learning

Policy optimizationの強みとしては，目的に対して直接的に最適化を行うことができるという点．対して，Q-learningはself-consistency equationを満たすようにQ_\thetaを学習することによってエージェントの振る舞いを間接的に最適化するだけで成り立っているため，学習に失敗しやすい．ただ，Q-learningはpolicy optimizationに比べサンプルを効率的に収集/再利用可能なためデータ量において利点がある．

What to Learn in Model-Based RL

Model-free RLと比べてmodel-based RLには簡単な分類手段がないとのこと．ここではいくつかの例をあげる．

Background: Pure Planning

多くの基本的なアプローチはpolicyを陽に表現することはなく，代わりに行動選択のためにmodel-predictive control (MPC)のようなpure planning techniquesを使う．MPCでは，エージェントが環境を観測するたび，モデルに従って最適な行動を選ぶ．この時，現時刻からある固定長先の時刻までの間で取ることができる全ての行動を記述することで最適な行動を選ぶ．将棋や囲碁でいうと，5手先までの選択肢を全て列挙して最適な指し手を選ぶというところ（これが俗に言う水平線効果を生じさせる原因？）．

Expert Iteration

Pure planningを単純に改変しようとするとpolicy \pi_\theta(a|s)を陽に表現または学習して獲得するという方法が考えられる．エージェントはモデルを利用したplanning algorithmを使うことで現在のpolicyからサンプリングすることで行動の候補を生成する．この生成された行動はpolicyのみで選択された行動より良い行動となる．そのためこのpolicyに対して"expert"と呼ばれ，policyはplanningアルゴリズムの出力，すなわちexpartのような行動をするように学習されていく．

Data Augmentation for Model-Free Methods

これはpolicyもしくはQ関数を学習するためにmodel-free RLを使うものだが，エージェントの更新においてシミュレーション結果を現実のものとして拡張する（これがどう言う意味かはいまいちわからなかった．），もしかはシミュレーション結果のみを使ってエージェントの更新を行う．

Embedding Planning Loops

もう一つのアプローチとしてはplanning procedureをpolicyとして利用するというもの．この方法はモデルのバイアスを減らすことが可能とのこと．

まとめ

ざっくりとRLのアルゴリズムを分類．各分類ごとに手法の例が示されていたので適当に論文も読んで勉強して行きたい．

OpenAIのSpinning Upで強化学習を勉強してみた　その１

Reinforcement Learning

はじめに

OpenAIが提供するSpinning Upで深層強化学習の勉強をしたのでメモ．ちなみに強化学習は完全素人で何も知らない状態から始めていて，とりあえずの取っ掛かりとしてSpinning Upを利用してみたと言うところ．個人的にtensorflowで書かれているのがしんどい．

Part 1: Key Concepts in RL

まず，強化学習（RL; Reinforcement Learning）とは何かというざっくりとした概念の説明．

Part 1のページはこちら．

Key Concepts and Terminology

RLはエージェント（agent）と環境（environment）という二つの主要な要素から成り立っている．環境はエージェントが存在して行動をする世界のこと．エージェントは行動のたびに世界の状態を観測して取りべき行動（action）を決定する．例えば将棋（趣味が将棋なので）の場合は，盤面の駒の配置（環境）を観測した後エージェントはどの駒をどこに動かすか（action）を決定するということ．

ただ，エージェントは闇雲に行動しても意味がないので，エージェントは行動した結果に対し環境から報酬（reward）を受け取る．報酬は行動の良し悪しによって与えられる報酬が変わり，この報酬を目安として最適な行動を取るように学習していくと言うものがRL．

以下，RLを学ぶ上で基本かつ重要な概念など．

States and Observations

状態（state）sは世界（environmentとworldの違いがイマイチわからないがとりあえず環境，世界と区別して書く）の状態を記述したもので，sに含まれない世界の状態の情報はない．それに対し観測（observation）oは状態の一部を記述したもの．

Deep RLにおいて状態と観測はreal-valued vector, matrixまたはhigher-order tensorによって記述される．例えばロボットは観測をRGBカメラによって得るとすれば，oはカメラによって得られたRGBの画像となる．この場合小さな部屋にロボットがいれば世界はその部屋の中で，観測はカメラで撮影された部屋の一部ということ．

仮にエージェントが環境の全ての状態を観測可能な場合には，その環境のことをfully observedといい，一部しか観測できない場合にはpartially observedという．

Action Spaces

異なる環境においては取れる行動の種類は異なる．車の制御ならアクセルとブレーキとハンドル操作，囲碁ならどこに石を置くかなど．逆にいえば車の制御という課題で碁石をおくという行動はできない．そのため，与えられた環境で許されている行動の集合をaction spaceと呼ぶ．このaction spaceは離散な行動のみを許すdiscrete action spacesと連続な行動を許すcontinuous action spacesがある．さっきあげた例だと車はcontinuousで囲碁はdiscrete．

このdiscreteかcontinuousかはRLの手法に大きな影響を与え，多くの場合どちらか一方にしか適用できないことが多く，もう一方のaction spacesに適用する場合にはアルゴリズムに大きな変更を要する場合があるとのこと．

Policies

Policyはエージェントがどの行動を取るか決めるのに使うルール．行動の選択が決定的な場合次のように\muによって表現される．

\displaystyle a_t=\mu(s_t)

もしくは確率的なものとして\piを使って次のように表現される．

\displaystyle a_t\sim\pi(\cdot|s_t)

場合によってはagentをpolicyと置き換えて使うこともあるそう．

Deep RLにおいてはparameterized policiesを使い，上記の\muや\piがニューラルネットによって表されるとのこと．つまり，ニューラルネットのパラメータを\thetaと表現すれば次のように表現可能．

\displaystyle a_t=\mu_\theta(s_t)\\ \displaystyle a_t\sim\pi_\theta(\cdot|s_t)

Deterministic Policies

Continuous action spaceにおけるdeterministic policiesの例として次のようなtensorflowのコードがあげられてた．

obs = tf.placeholder(shape=(None, obs_dim), dtype=tf.float32)
net = mlp(obs, hidden_dims=(64,64), activation=tf.tanh)
actions = tf.layers.dense(net, units=act_dim, activation=None)

これは先ほどの数式を使えばa_t=\mu_\theta(s_t)で表現できて，\muがいわゆる1層の全結合層になっている状態．

Stochastic Policies

Deep RLにおけるstochastic policiesは基本的にcategorical policiesかdiagonal Gaussian policiesを使うとのこと．

Categorical policiesはdiscrete action spacesの場合に使われ，diagonal Gaussian policiesはcontinuous action spacesの時に使われる．

Stochastic policiesでは次の2つの計算が重要となる．

・policyからの行動のサンプリング

・特定の行動の対数尤度\log\pi_\theta(a|s)の計算

Diagonal Gaussian policyに関してはガウス分布の平均は状態に関する関数\mu_\theta(s)として表現するのが一般的だが，分散\sigma^2に関しては2種類の表現が使われていて，一つは状態とは関係のないただのベクトル\log\sigmaとして表現する方法で，もう一つは\log\sigma_\theta(s)とする方法．

Trajectories

Trajectory \tauは次のような世界の状態と行動の系列のこと．

\displaystyle \tau=(s_0,a_0,s_1,a_1,\dots)

つまり強化学習していく上で，環境がどのように変化したか，その時どのような行動をとったかのログ．初期の状態s_0はstart-state distribution \rho_0なる分布からサンプリングされる．

\displaystyle s_0\sim\rho(\cdot)

状態の遷移（時刻tの状態s_tから時刻t+1で状態s_{t+1}への移り変わり）は環境における自然な法則によって拘束されていて（つまりありえない移り変わりはできない），直近の行動a_tにのみ依存する．この遷移も決定的，確率的なものがあり次のように表現される．

\displaystyle s_{t+1}=f(s_t,a_t)\\ \displaystyle s_{t+1}\sim P(\cdot|s_t,a_t)

また，行動はpolicyから決められる．ちなみにtrajectoriesはepisodesやrolloutsと呼ばれることもあるとのこと．

Reward and Return

Reward function RはRLにおいてめちゃくちゃ重要で，世界の現在の状態と選択された行動，それによって遷移した状態に依存する．

\displaystyle r_t=R(s_t,a_t,s_{t+1}

ただし，場合によっては簡単化されて現在の状態のみに依存r_t=R(s_t)，または状態と行動に依存r_t=R(s_t,a_t)する場合もある．

目標としてはtrajectoryに対してcumulative reward R(\tau)を最大化すること．選択肢の一つとしてfinite-horizon undisputed returnがあり，これは次のように固定ウィンドウ幅Tで報酬の和を取るというもの．

\displaystyle R(\tau)=\sum_{t=0}^Tr_t

もう一つの選択肢としてはinfinite-horizon discounted returnで，エージェントから得られた全ての報酬の和を取るというもの．ただし，一般には適当な減衰率\gamma\in(0,1)を使って重み付き和で表現される．

\displaystyle R(\tau)=\sum_{t=0}^\infty\gamma^tr_t

この減衰という操作には直感的な解釈と数学的な利点があって，直感的には後で受け取る報酬より直近の報酬の方が重要（出だしでつまづいたらどうしようもないということか），数学的には無限の足し合わせだと有限の値に収束しなくなって扱いにくいが，適当な減衰係数があることで収束するから嬉しいということらしい．

通常のRLだと上の二つのreturnは明確に定義されているが，ことdeep RLに関しては明確でない場合があるそう．deep RLだとしばしばundiscounted returnを最適化するアルゴリズムをセットアップするが，value functionsを推定するのに減衰係数を使うとのこと．（まだ詳しい話出てきてないのにいきなりこんなこと言われてもよくわからないが）

The RL Problem

Return functionやpolicyをどう選んだとてRLの目標はexpected returnを最大化するpolicyを選択すること(policyの選択がなんであろうとゴールは最適なpolicyを選ぶとはこれいかに\dots)．

Expected returnの説明をするために，状態遷移とpolicyが確率的な状況について考える．この時，Tステップめのtrajectoryの確率は次のように与えられる．

\displaystyle P(\tau|\pi)=\rho_0(s_0)\prod_{t=0}^{T-1}P(s_{t+1}|s_t,a_t)\pi(a_t|s_t)

この式は状態s_{t+1}がs_t,a_t以外とは独立なことから得られる．この時returnがどのようなものであれ，expected return J(\pi)は次のように計算できる．

\displaystyle J(\pi)=\int_\tau P(\tau|\pi)R(\tau)=\underset{\tau\sim\pi}{E}[R(\tau)]

これは普通に期待値の計算．するとRLの最適化問題はexpected returnの最大化なので次のように表現される．

\displaystyle \pi^\ast=\underset{\pi}{\mathrm{argmax}}J(\pi)

Value Functions

Value functionsは状態または状態と行動のペアの価値を知るために使われる関数でほぼ全てのRLアルゴリズムで使われる．一般的にはexpected returnで表現され，主に次の4種類に分類される．

  1. On-Policy Value Function

状態sから始まり，常にpolicy\piに従って行動する場合

\displaystyle V^\pi(s)=\underset{\tau\sim\pi}{E}[R(\tau)|s_0=s]

2.On-Policy Actoin-Value Function

状態sから始まり，最初にある行動aを取り，その後常にpolicy \piに従って行動する場合

\displaystyle Q^\pi(s,a)=\underset{\tau\sim\pi}{E}[R(\tau)|s_0=0,a_0=a]

  1. Optimal Value Function

状態sから始まり，その環境において最適なpolicyに従って常に行動するような場合

\displaystyle V^\ast(s)=\max_\pi\underset{\tau\sim\pi}{E}[R(\tau)|s_0=s]

  1. Optimal Action-Value Function

状態sから始まり，最初にある行動aを取り，その後その環境において最適なpolicyに従って常に行動するような場合．

\displaystyle Q^\ast(s,a)=\max_\pi\underset{\tau\sim\pi}{E}[R(\tau)|s_0=s,a_0=a]

Value FunctionとAction-Value Functionの間には次のような関係がある．

\displaystyle V^\pi(s)=\underset{a\sim\pi}{E}[Q^\pi(s,a)] \\ \displaystyle V^\ast(s)=\max_aQ^\ast(s,a)

要は取りうる行動に対してaction-value functionを周辺化すればvalue functionになる．

The Optimal Q-Function and the Optimal Action

状態sにおける最適なpolicyはsから始まるexpected returnを最大化する行動を選択する．その結果もしQ^\astが得られれば，最適な行動a^\ast(s)を直接得ることができる．

\displaystyle a^\ast(s)=\underset{a}{\mathrm{argmax}}Q^\ast(s,a)

ただし，expected returnを最大化する行動が複数存在する場合もあり，その時は行動はランダムに選ぶ．

Bellman Equations

実は先ほどあげた4つのタイプのvalue functionsは全てBellman equationsと呼ばれるspecial self-consistency equations（これは日本語だとなんて訳を当てるのか\dots）に従う．

On-policy value functionsにおけるBellman方程式は次のように表現される．

\displaystyle V^\pi(s)=\underset{\overset{a\sim\pi}{s'\sim P}}{E}[r(s,a)+\gamma V^\pi(s')]\\ \displaystyle Q^\pi(s,a)=\underset{s'\sim P}{E}\left[r(s,a)+\gamma\underset{a'\sim\pi}{E}[Q^\pi(s',a')]\right]

s'\sim Pはs'\sim P(\dot|s,a)のことで，次の状態s'が環境の遷移分布からサンプリングされることを意味していて，a\sim\piはa\sim\pi(\dot|s)，a'\sim\piはa'\sim\pi(\dot|s')を表す，Bellman方程式は開始点における価値（value）はその点から期待される報酬（ Reward）r(s,a)と次の点の価値[V^\pi(s')]の足し合わせであるという考えに基づいている．

Optimal value functionsに関するBellman方程式も同様に表現できる．

\displaystyle V^\ast(s)=\max_a\underset{s'\sim P}{E}[r(s,a)+\gamma V^\ast(s')]\\ \displaystyle Q^\ast(s,a)=\underset{s'\sim P}{E}\left[r(s,a)+\gamma\max_{a'}Q^\ast(s',a')\right]

On-policy/optimal value functionのBellman方程式間の明確な違いは行動に対する最大化があるかないかのみ．

Advantage Functions

RLにおいてたまに，特定の状況下でとった行動がどれくらいよかったかではなく，ほかと比べて平均的にどれくらいよかったかを知りたい場合がある（ローカルに見るかグローバルに見るかという感じ）．そのためadvantage functionの概念を作る．

あるpolicy \piに対応するadvantage function A^\pi(sea)は，永久に\piに従って行動するという仮定の下，ある状態sにおいて特定の行動aをとった時にどれくらいよかったかを記述するもの．数学的には次のようにかける．

\displaystyle A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)

Advantage functionsに関してはまた後ほど解説がある．

Formalism

文献を読んでいくとMarkov Decision Processes (MDPs)の設定に遭遇する場合があるだろうということ．ここはoptionalなので特に詳しいことはないが，MDPsは5-tuple，\langle S,A,R,P,\rho_0\rangleで定義されるもので，

・Sは取りうる全ての状態の集合

・Aは取りうる全ての行動の集合

・R:S\times A\times S\rightarrow\mathbb{R}はreward functionでr_t=R(s_t,a_t,s_{t+1}

・P:S\times A\rightarrow \mathcal{P}(S)は遷移確率関数でP(s'|s,a)は状態sで行動aをとった時に状態s'に遷移する確率

・\rho_0は初期状態分布（starting state distribution）

まとめ

とりあえずpart 1まで．まだここで出てきたものがどのように使われるか出てきてないので理解が進みにくいがなんとなく雰囲気はつかめた．

HOW POWERFUL ARE GRAPH NEURAL NETWORKS?を読んだのでメモ

graph convolutional network

はじめに

HOW POWERFUL ARE GRAPH NEURAL NETWORKS?を読んだのでメモ．各命題，定理の証明は今回は割愛．

2018.11.24

Openreviewにて論文で提案しているGINが定理3を満たさない（= WL testと同等の識別能力を有すると言えない）ということが示されて内容が変更されていたのでこちらのメモも少し修正．(修正抜けがあると思うので正確な内容を知りたい場合は論文を参照)．

気持ち

Graph convolutional networks（GNN）がグラフデータに関する様々な課題においてstate-of-the-artを記録しているが，どの研究もヒューリスティックスに頼ったtrial-and-errorで手法が作られていることを問題視．もう少し理論的な理解とともに新しいGNNを提案するというもの．

Graph Neural networks

まずは一般的なGNNについて．G=(V,E)を各ノードが特徴ベクトルX_v,\:v\in Vを持つグラフとする．今回はnode classification（各ノードのラベルy_vの予測）とgraph classification（グラフそのもののラベルy_Gの予測）の二つに焦点を当てる．

GNNは主にノードの表現ベクトルh_vまたはグラフそのものの表現ベクトルh_Gを学習するために用いられ，基本的な戦略としては隣接ノードの情報を集約を繰り返すことでそのノードの持つ表現ベクトルを更新していく．一般的にk回集約を繰り返すことでk-hopの情報を得ることが可能．この集約の手続きは次のように表現できる．

\displaystyle a_v^{(k)}=\mathrm{AGGREGATE}^{(k)}\left(\left\{h_u^{(k-1)}:u\in\mathcal{N}(v)\right\}\right),\:h_v^{(k)}=\mathrm{COMBINE}^{(k)}\left(h_v^{(k-1)},a_v^{(k)}\right)

h_v^{(k)}はk層目のノードvが持つ特徴ベクトルで，h_v^{(0)}=X_v．\mathcal{N}(v)はvに隣接するノード集合．\mathrm{AGGREGATE}^{(k)}(\cdot),\mathrm{COMBINE}^{(k)}(\cdot)の選び方によってGNNは区別される．例えば，KipfとWellingが提案したGCNは次のような\mathrm{AGGREGATE}関数として定義される．

\displaystyle a_v^{(k)}=\mathrm{MEAN}\left(\left\{\mathrm{ReLU}\left(W\cdot h_u^{(k-1)}\right),\forall u\in\mathcal{N}(v)\right\}\right)

Wは学習パラメータとなる行列．GraphSAGEは\mathrm{MEAN}関数を要素ごとのmax-poolingに置き換えたものとして表現できる．またGraphSAGEにおいては\mathrm{COMBINE}のステップとしてW\cdot\left[h_v^{(k-1)}|a_v^{(k)}\right]という演算が存在する（GCNには\mathrm{COMBINE}の処理はない）．

Node classificationにおいては，ノードの表現ベクトルh_v^{(K)}を使って予測を行い，graph classificationにおいては次のような\mathrm{READOUT}関数によりノードの表現ベクトルの集約が行われる．

\displaystyle h_G=\mathrm{READOUT}\left(\left\{h_v^{(K)}|v\in G\right\}\right)

\mathrm{READOUT}は基本的にpermutation invariantな関数である必要がある．

Weisfeiler-Lehman test

Weisfeiler-Lehman test（WL test）は各ノードにカテゴリカルラベルが付与されていると仮定した元で，(1)ノードとその隣接ノードのラベルをaggregate，(2)集約されたラベルをユニークな新しいラベルに変換，という処理を繰り返すもので，この処理を繰り返した結果二つのグラフの各ノードが異なるかどうかでグラフの同型性を判断するというもの．この処理はGNNの処理と 似ているというのがここでの主張．

WL testを使ったGNN的な手法としてShervashidzeらが提案したWL subtree kernelがある．これはWL testの異なる繰り返し回数でのノードラベルをノードの特徴ベクトルとして使う手法で，k-th iterationにおいてあるノードをルートとしたのきの高さkの木構造を表現可能（Figure 1がその例）．

Theoretical framework

GNNの表現力の高さを分析する．仮定としてグラフの各ノードの特徴ベクトルとしてunique label\in\{a,b,c,\dots\}を割り当てる．この時隣接ノードの集合の特徴ベクトルは以下で定義されるmultisetを形成する．これは異なるノードが同一の特徴ベクトルを持つため同一の要素が複数回現れることを意味する．

Definition 1 (Multiset)

Multisetは集合の一般化された概念で，その要素として複数のインスタンスを持つことを許す．すなわち，multisetは2-tuple X=(S,m)であり，この時SはXの基底となる集合で個別の要素によって形成され，m:S\rightarrow\mathbb{N}_{\geq 1}は要素の多様性を与える．

ここではGNNの表現力を測るため，GNNに二つのノードを同一の場所に埋め込む時を考える．直感的には，これは二つのノードが同一の特徴量，同一のsubtree構造を持つ時にのみ可能だと思える．面白いのはmultisetsな状況においてGNNはこれは不可能だと言っていて，aggregation schemeはinjectiveであるという．よってここではCNNをmultisets上の関数の集合として考え，それがinjective multiset functionsを表現できるかどうかを分析する．

Generalizing the WL test with graph neural networks

理想的にGNNの表現力の高さは異なるグラフを区別できるかどうかであるが，これはグラフの同型性の識別問題を解決したことになってしまう．ここでの分析においては少しゆるい指標を使ってGNNの表現力を分析する．

Lemma 2.

G_1,G_2を非同型なグラフとする．もしneighborhood aggregation schemeに従うGNN \mathcal{A}:\mathcal{g}\rightarrow\mathbb{R}^bがG_1とG_2に異なる埋め込みを与えるならば，WL graph isomorphism testを使ってG_1とG_2は非同型であると判別できる．

Lemma 2からaggregation-based GNNはグラフ識別においてWL testと同等の能力がある．では現状提案されてるGNNはどれもWL testと同等の能力があるのかというのが疑問．論文では次のTheoremから同等な能力があるとしている．

Theorem 3

\mathcal{A}:\mathcal{g}\rightarrow\mathbb{R}^dをneighborhood aggregation schemeに従うGNNとする．十分な回数集約の操作が行われたとき，もし次の条件が満たされれば\mathcal{A}はWL testにおいて非同型と判断されたG_1とG_2を異なる埋め込みへと写像する．

a) \mathcal{A}はノードの特徴ベクトルを次のように繰り返し集約，更新する．

\displaystyle h_v^{(k)}=\phi\left(h_v^{(k-1)},f\left(\left\{h_u^{(k-1)}:u\in\mathcal{N}(v)\right\}\right)\right)\:or\:h_v^{(k)}=f\left(\left\{h_v^{(k-1)},h_u^{(k-1)}:u\in\mathcal{N}(v)\right\}\right)

関数fはmultisets上の演算子で，\phiは単射．

b)\mathcal{A}のグラフレベルのreadout（multiset上の演算）は単射．

ここまでGNNとWL testは同等とは言いつつも，GNNはWL test以上に重要な利益をもたらす．というのもWL testでのノードの特徴ベクトルはone-hotベクトルでsubtree間の類似性などを得ることはできない．つまりGNNはWL testを連続空間に拡張かつ学習ベースにしたものと言える．これはGNNが構造の識別だけでなく埋め込みの学習やグラフ構造間のdependenciesも取得可能ということを意味する．

Graph isomorphism network (GIN)

ここではTheorem 3を満たすことで一般化されたWL testという保証のあるGraph Isomorphism Network (GIN)を提案．

Lemma 4によりsum aggregatorsが単射，特にmultisets上のuniversal functionsを表現できるということを示す．

Lemma 4

\mathcal{X}が可算であるとする．h(c,X)=(1+\epsilon)\cdot f(c)+\sum_{x\in X}f(x)が有限のmultiset X\subset\mathcal{X}においてuniqueとなるような関数f:\mathcal{X}\rightarrow\mathbb{R}^nが存在する．さらに，任意のmultiset function gはある関数\phiを用いてg(X)=\phi( (1+\epsilon)\cdot f(c)+\sum_{x\in X}f(x) )のように分解される．

Multi-layer perceptrons（MLPs）のuniversal approximation theoremから，f,\phiをMLPsでモデリングすることができる．実践的にはf^{(k+1)}\circ\phi^{(k)}は一つのMLPでモデル化したとのこと．するとGINは次のような形でノードの特徴量を更新する．

\displaystyle h_v^{(k)}=\mathrm{MLP}^{(k)}\left((1+\epsilon)^{(k)}h_v^{(k-1)}+\sum_{u\in\mathcal{N}(v)}h_u^{(k-1)}\right)

\epsilonは実験では0または学習パラメータとしていた（ちなみに0の場合はTheorem 3を満たさない）．この演算は言ってしまえば自分自身に適当な係数をかけて全ての隣接ノードとの和をとってMLPに入力するというもの．またGINは\mathrm{AGGREGATE}のみで\mathrm{COMBINE}は行わない．めちゃくちゃシンプルで直感的にはうまくいかなさそうだがTheorem 3からより複雑なものと比べても同程度の性能を発揮できる保証がある．

Readout subtree structures of different depths

グラフレベルのreadoutの重要な側面としては繰り返し回数が増えるほどノードの表現はrefinementされ，かつglobalな情報を得ることができるという点．この繰り返しの回数は重要だが，稀に回数が少ない時に得られた表現が良いものである場合もある．そのためGINでは全てのdepths/iterationsから得られた情報を用いることにする．これをJumping Knowledge Networks (JK-Nets)に似た構造で実現する．すなわち次のようなreadoutの関数を用いる．

\displaystyle h_G=\mathrm{CONCAT}\left(\mathrm{READOUT}\left(\left\{h_v^{(k)}|v\in G\right\}\right)|k=0,1,\dots,K\right)

つまり全てのiterationにまたがって特徴ベクトルをconcatするというもの．Theorem 3とLemma 4に従えばこのreadoutの処理はWL testとWL subtree kernelの一般化になっている．

Less powerful but still interesting GNNs

最後にGCNやGraphSAGEを含むTheorem 3を満たさないGNNについて考える．ここではGINの集約の処理を(1)MLPsではなく単層のパーセプトロンにした場合，(2)sumの代わりにmeanまたはmax-poolingを使った場合のモデルについて掘り下げる．これらのGNNのバリエーションがWL testより劣り，単純なグラフにおいて機能しないことを示す．それでもなおsumの代わりにmeanを使うGCNはnode classificationにおいてよく機能するらしい．この理解を深めるためにGNNがグラフの何を捉えることができて何を捉えることができないかを論じる．

1-layer perceptron is insufficient for capturing structures

Lemma 4における関数fは異なるmultisetsをuniqueなembeddingsに写像する役割を果たし，universal approximation theoremからMLPによってパラメタライズされる．にも関わらず多くのGNNは単層のパーセプトロンを使っている．するとグラフの学習に単層のパーセプトロンで十分かという疑問がわく．実際には単層のパーセプトロンモデルはできないことが次のLemma 5から言える．

Lemma 5

任意の線形変換W,\:\sum_{x\in X_1}\mathrm{ReLU}(Wx)=\sum_{x\in X_2}\mathrm{ReLU}(Wx)に対して有限のmultisets X_1\neq X_2が存在する．

すなわち違うmultisetsに対して同じ表現を割り当ててしまう（区別できなる）場合があるということ．これを後ほど実験的にも証明した．

Structures that confuse mean and max-pooling

今度はsumをmeanまたはmax-poolingに置き換えたらどうなるかを考える．基本的にmeanまたはmax-poolingはpermutation invariantなため良いmultisite functionであるが，単射でないという問題がある．Figure 2と3にmeanやmaxにした場合に非常に単純なグラフの識別に失敗する例が示されている．

Mean learns distributions

ここではmean aggregatorが区別可能なmultisetsを調べるため，X_1=(S,m),X_2=(S,k\cdot m)という例を考える．この二つのmultisetsはmean aggregatorによって同じ埋め込みが与えられる．そのため，mean aggregatorはmultisetの要素の分布を捉えていて，正確なmultisetを捉えることはしていないと言える．

Corollary 6

\mathcal{X}が可算であるとする．もし，有限のmultisetsX_1,X_2が同じ分布を持つならば，h(X)=\frac{1}{|X|}\sum_{x\in X}f(x),\:h(X_1)=h(X_2)に関して関数f:\mathcal{X}\rightarrow\mathbb{R}^nが存在する．

もし解きたい問題がグラフの構造よりも統計的な情報を重視する場合にはmean aggregatorはうまく機能する．さらに言えば，ノードの特徴が多様な場合にはsum aggregatorと同程度の性能を発揮する．これがnode classificationにおいてmean aggregator (GCN)が機能する理由だと考えられる．

Max-pooling leans sets with distinct elements

Max-poolingは残念なことに正確な構造も分布も捉えることができない．ただし，代表的な要素を捉えるのが重要なタスクにおいては適していると言える．実際PointNet (point cloudのためのNN)ではmax poolingを使っていて，ノイズや外れ値に頑健な認識を可能にしている．

Corollary 7

\mathcal{X}が可算であるとする．もしX_1,X_2が同じunderlying setを持つなら，h(X)=\max_{x\in X}f(x),\:h(X_1)=h(X_2)に関してf:\mathcal{X}\rightarrow\mathbb{R}^\inftyが存在する．

まとめ

個人的にめちゃくちゃ面白かった．GNNの論文は色々読んだけど確かに表現力に関して突っ込んだ論文はなかったなと．読み応えあってメモも一部和訳レベルで残してしまった．ICLR2019のレビュー中なようだけど3人目のレビュワーがしきりに"I quite liked the paper"て言っててテンション上がってたのが印象的．

Neural Nearest Neighbors Networksを読んだのでメモ

Neural Network

はじめに

Neural Nearest Neighbors Networksを読んだのでメモ．differentiableなKNN selection ruleを提案するというもの．NIPS 2018でgithubにコードも公開されている．

Differentiable k-Nearest Neighbors

クエリとなるアイテムをq，データベースの候補を(x_i)_{i\in I}，距離関数をd(\cdot,\cdot)とする．qはデータベースの中にないものと仮定し，dはクエリからの距離に従ってデータベースのアイテムのランキングを生成する．ここで[tes:\pi_q:I\rightarrow I]をqの距離にしたがってソートを行うpermutationと定義する．

\displaystyle \pi_q(i)\lt\pi_q(I')\Rightarrow d(q,x_i)\leq d(q,x_{i'}),\:\forall i,i'\in I

するとqのKNNはpermutation \pi_qにおいて最初のk個のアイテムの集合として与えられる．

\displaystyle \mathrm{KNN}(q)=\{x_i|\pi_q(i)\leq k\}

KNNのselection ruleはdeterministicなため微分不可能で，距離に関する微分を伝播することができない．そこでこの問題をone-hotベクトルの連続値への緩和を使って解消する．

KNN rule as limit distribution

ここではKNN selection ruleをカテゴリカル分布の極限分布としてみなすことで緩和する．\mathrm{Cat}(w^1|\alpha^1,t)をデータベースのアイテムのインデックスIに関するカテゴリカル分布とする．クエリアイテムとの距離d(q,x_i)を\alpha_i^1とし，温度パラメータtを導入すれば，i\in I番目のアイテムを選択する確率w_1は次のように与えられる．

\displaystyle \mathbb{P}[ w^1=i|\alpha^1,t]\equiv\mathrm{Cat}(\alpha^1,t)=\frac{\exp(\alpha_i^1/t)}{\sum_{i'\in I}\exp(\alpha_{i'}^1/t)}\\ \mathrm{where}\:\alpha_i^1\equiv -d(q,x_i)

Gumbel softmaxやconcrete distributionで見たような式だが，ここではアイテム間の距離によって決定的にサンプリングされるアイテムが決まるためgumbel分布からのサンプリングがない．t\rightarrow 0の時w^1はone-hotベクトルとなる．この式を1-NNのstochastic relaxationとしてみなすことができるため，これをkの場合に拡張することでKNNを微分可能な形に緩和することができる．そのために条件付き分布\mathrm{Cat}(w^{j+1}|\alpha^{j+1},t)へと拡張する．ここで\alpha^{j+1}は次のように計算される．

\displaystyle \alpha_i^{j+1}\equiv\alpha_i^j+\log(1-w_i^j)

つまり一度選択されたアイテムは選択される確率が0に近くなるようクエリアイテムとの距離を離すというもの．実際w_i^jがone-hotベクトルの場合には\alpha_i^{j+1}はw^j=iにおいて-\inftyになる．これによってj+1番目のサンプルのインデックスは次のように得られる．

\displaystyle \mathbb{P}[w^{j+1}=i|\alpha^{j+1},t]\equiv\mathrm{Cat}(\alpha^{j+1},t)=\frac{\exp(\alpha_i^{j+1}/t)}{\sum_{i'\in I}\exp(\alpha_{i'}^{j+1}/t)}

Index vector w^jからqのstochastic nearest neighbors \{X^1,\dots,X^k\}を次のように定義する．

\displaystyle X^j\equiv\sum_{i\in I}w_i^jx_i

温度t\rightarrow 0の時w^j_iがone-hotベクトルとなりk nearest neighborsと一致する．ただ基本的にはone-hotベクトルではないので多分mixup的な形になるはず(というかone-hotベクトルに近づけば近づくほど勾配が消失していくので意味がなくなる)．

Neural Nearest Neighbors Block

今までの議論を踏まえてニューラルネットの一つの層としてneural nearest neighbors block (\mathrm{N}^3 blocks)を提案する．\mathrm{N}^3 blocksは二つの部分からなり，一つはembedding networkで，もう一つは連続緩和されたnearest neighborsを計算する部分がある．

Embedding network

Embedding networkはf_EでparameterizeされたCNNを使って入力から特徴ベクトルを得る部分．得られた特徴をEとし，ユークリッド距離を用いてD_{ij}=d(E_i,E_j)というpairwise distance matrix Dを得る．さらに，ここでは温度tを計算するもう一つのネットワークT=f_T(Y)を用意する．ただし，f_Eとf_Tは出力層以外は重み共有している．

Continuous nearest neighbors selection

距離行列D，温度テンソルT，入力の特徴Yからk continuous nearest neighbors feature volumes N_1,\dots,N_kを計算する．nearest neighborsとYは入力の次元が同じなのでelement-wiseな操作によってまとめることができるが今回はチャネル方向に結合することで情報をまとめたとのこと．

\mathrm{N}^3 block for image data

基本的に\mathrm{N}^3 blockは入力のドメインに関係なく適用可能だが，画像データにカニsてはちょっとした修正が必要．従来画像におけるnon-local methodはパッチレベルで行われ，パッチレベルの処理には様々な利点が存在する．そのため画像に\mathrm{N}^3 blockを適用する際にはim2colを使ってパッチレベルで計算するとのこと．

まとめ

基本的にはdeterministicなGumbel softmaxという感じ．実験ではdenoisingや超解像などの逆問題を解くのに使っていたが，いろいろなことに使えそう．ただ，複雑なことをしようとすると距離（というかembedding network）に何らかのpriorを持たせないと学習は難しそう．

Learning Laplacian Matrix in Smooth Graph Signal Representationsを読んだのでメモ

graph laplacian

はじめに

Learning Laplacian Matrix in Smooth Graph Signal Representationsを読んだのでメモ．

気持ち

データの構造をグラフで表現する際に，一般的にはgeographicalもしくはsocial friendshipなどに基づいてグラフ構造を決定する．ただこのような決め方は常に良い方法とは言えない，またはこのようなグラフ構造の導入が常にできるとは限らない．なので観測されたデータから学習ベースでグラフ構造を決めようというのがこの論文のゴール．ただしデータサンプルからグラフ構造の決定は基本的にはill-posed problemなのでグラフの滑らかさを使ってうまく扱う方法を提案．

Smooth graph signals

まず滑らかなグラフとは何かというところから．ここではノード数nの重み付き無向グラフG=\{V,E,\omega\}を考える．V,E,\omegaはそれぞれグラフのノードとエッジとエッジが持つ正の重みを表す．Wを重み付き隣接行列，Dを度数行列とすれば非正規化グラフラプラシアンLは次のように表現できる．

\displaystyle L=D-W

Lは固有値分解可能なため固有値\Lambda固有ベクトル\chiを使って次のように表現できる．

\displaystyle L=\chi\Lambda\chi^T

また，Lの最小固有値は0でその個数はグラフのconnected componentsの数に一致する．

ここでグラフG上のグラフ信号fのsmoothnessは次の2次形式で測ることができる．

\displaystyle f^TLf=\frac{1}{2}\sum_{i\sim j}w_{ij}(f(i)-f(j))^2

w_{ij}は頂点i,jを結ぶエッジの重みでf(i),f(j)は各頂点の信号の値．つまりエッジの重みを使って重みづけられたノード間の信号の変化分の大きさが小さいほどグラフは滑らかであるということ．

グラフラプラシアンの細かい話は以前勉強したメモがあるのでそちらを参照．

Representation via factor analysis model

ここでは因子分析に基づくsmooth graph signalsのための表現モデルを提案する．factor analysis modelは線形モデルの一種で，今回は次のモデルを考える．

\displaystyle x=\chi h+u_x+\epsilon

x\in\mathbb{R}^nは観測されたグラフ信号の表現で，h\in\mathbb{R}^nは潜在変数で固有ベクトル行列chiを通してxをコントロールする．u_x\in\mathbb{R}^nはxの平均．ここでは雑音\epsilonは等方性であるとし，平均0，分散\sigma^2_\epsilon I_nの多変量ガウス分布を仮定する．よって\epsilonの確率密度関数は次のようになる．

\displaystyle \epsilon\sim\mathcal{N}(0,\sigma^2_\epsilon I_n)

今回のモデルは一般的な因子分析モデルのグラフ信号への一般化になっていて，重要となるのはLの固有ベクトル\chiで表現される表現行列の選択．選び方には二つの観点があって，一つはグラフのトポロジーを反映したものを探すことで，もう一つは表現行列がグラフのフーリエ基底として解釈可能であるということ．なのでLの固有ベクトルは表現行列の良い候補になる．

今回はクラシカルな因子分析モデルに従って潜在変数をガウシアンと仮定．もっと言えばここではガウシアンを平均0，精度行列をLの固有値\Lambdaとする以下の形で定義する．

\displaystyle h\sim \mathcal{N}(0,\Lambda^\dagger)

\Lambda^\daggerは\Lambdaのムーアペンローズの擬似逆行列．Lの固有値はグラフの周波数を表しているため，低周波ほどエネルギーを持つということを暗に仮定していること．今までの関係を用いればxの条件付き確率とxの確率は次のように表現可能．

\displaystyle x|h\sim\mathcal{N}(\chi h+u_x,\sigma^2_\epsilon I_n) \\ \displaystyle x\sim\mathcal{N}(u_x,L^\dagger+\sigma^2_\epsilon I_n)

ただしL^\dagger=\chi\Lambda^\dagger\chi^Tの関係を満たす．

Learning framework

観測xとhの事前分布が与えられたとし，hのMAP推定を行う．するとhのMAP推定は次のように表される．

\displaystyle h_{MAP}(x):=\mathrm{argmax}_hp(h|x)=\mathrm{argmax}_hp(x|h)p(h)=\mathrm{argmin}_h(-\log p_E(x-\chi h)-\log p_H(h))

p_E(\epsilon)=p_E(x-\chi h),p_H(h)は雑音と潜在変数の確率密度関数を表し，p(h|x)はxが与えられた時のhの条件付き確率密度関数．ここでそれぞれガウス分布を仮定すれば次のように書き直せる．

\displaystyle h_{MAP}(x):=\mathrm{argmin}_h(-\log p_E(x-\chi h)-\log p_H(h))\\=\mathrm{argmin}_h(-\log e^{-(x-\chi h)^T(x-\chi h)}-\alpha\log e^{-h^T\Lambda h})=\mathrm{argmin}_h|x-\chi h|^2_2+\alpha h^T\Lambda h

\alphaは定数でノイズの無い状況においては解はx=\chi h．また\chiは直交行列なのでx=\chi hにおいてh=\chi^Txが成り立つので以下の最小化問題へと書き直せる．

\displaystyle h^T\Lambda h=(\chi^Tx)^T\Lambda\chi^Tx=x^T\chi\Lambda\chi^Tx=x^TLx

すなわちLの特性からこの最小化問題はグラフの信号xが滑らかになるような解を導く．

ここでグラフ構造は未知であるためこの最小化問題は潜在変数hと表現行列\chiとhの事前分布に対する精度行列\Lambdaを変数に持つ．すなわち次の最小化問題として表される．

\displaystyle \min_{\chi,\Lambda,h}|x-\chi h|_2^2+\alpha h^T\Lambda h

さらにy=\chi hという変数変換を用いれば次のようにかける．

\displaystyle \min_{L,y}|x-y|_2^2+\alpha y^TLy

Learning algorithm

最終的に得られた最小化問題を行列形式で書き直すと次のようになる．

\displaystyle \min_{L\in\mathbb{R}^{n\times n},Y\in\mathbb{R}^{n\times p}}|X-Y|^2_F+\alpha\mathrm{tr}(Y^TLY)+\beta|L|^2_F,\\ \mathrm{s.t.}\:\mathrm{tr}(L)=n,\:L_{ij}=L_{ji}\leq 0,\:i\neq j,\:L\cdot\mathbf{1}=\mathbf{0}

X\in\mathbb{R}^{n\times p}はp個のデータを並べたもので，\alpha,\betaは正の正則化パラメータ．この論文ではこの最小化問題をLとYの交互最適化によって解く．

\displaystyle \min_L\alpha\mathrm{tr}(Y^TLY)+\beta|L|_F^2\\ \mathrm{s.t.}\:\mathrm{tr}(L)=n,\:L_{ij}=L_{ji}\leq 0,\:i\neq j,\:L\cdot\mathbb{1}=\mathbb{0}

\displaystyle \min_Y|X-Y|_F^2+\alpha\mathrm{tr}(Y^TLY)

Lに関する最小化問題はinterior point methodsなどで効果的に解けるがここではADMMを使ったとのこと．またYに関しては次のclosed formな解がある．

\displaystyle Y=(I_n+\alpha L)^{-1}X

まとめ

最小化問題を解くのにグラフラプラシアンの制約が面倒な印象．この辺の話はGCNとかとは組み合わさらないのか．

ScratchDet: Exploring to Train Single-Shot Object Detectors from Scratchを読んだのでメモ

detection

はじめに

ScratchDet: Exploring to Train Single-Shot Object Detectors from Scratchを読んだのでメモ．

気持ち

現状の物体検出器は基本的にimageNetなどのpretrainedモデルを使って学習している．この論文ではこれが精度の低下を起こすと主張．その理由として

  1. 事前学習に使ったデータと検出の学習に使うデータのドメインのギャップ

  2. 分類と検出の目的関数間のギャップ

  3. ネットワーク構造の制約

の3つを挙げている．1に関しては別な文献で指摘があり，2に関しては分類と検出ではtranslationに対してのセンシティビティが異なる点を意味する．最後の3に関してはオリジナルのネットワークをimageNetなどで事前学習するコストが高いことから挙げている．

これらを解決するためにスクラッチから学習可能な枠組みを提案するというもの．論文通してとにかくBatchNormすごいということしか言ってない感はある．

ScratchDet

ここではSSDをスクラッチで学習することを仮定．オリジナルのSSDはBatchNormを使っていないがここではまずbackbone(VGGやresnetなどメインのネットワーク部分)に使うことを考える．理由としてはBatchNormは目的関数を滑らかにして勾配を落ち着かせる効果があると言われているのでスクラッチから学習する上では必要だろうという思いがある．これだけでとりあえずmAPが67.6%から72.8%まで上がるとのこと．さらに面白いのは学習率を大きくすればするほど精度が向上するらしい．具体的にはオリジナルのSSDでは学習率0.001だったが，BatchNormを入れて学習率を0.05にすると78%まで精度向上するとのこと．これは（実験条件をどこまで揃えているかわからないが）SSDの元の論文で報告されていた77.2%を上回っている．

次にdetection head subnetworkにBatchNormを入れることを考える．backboneに入れずdetection headに入れるだけでmAPが67.6%から71.0%に改善，さらに学習率を0.001から0.01にあげると75.6%まで改善する（さっきと違い0.05の場合は試していないよう）．学習途中の勾配のノルムを確認したところbatchnormを入れると入れないものより安定していてlandscapeが滑らかになっている，すなわちフラットな解になっていることが確認できる（と言い切るのはやりすぎ感はあるけど）．

Backboneとdetection head両方にBatchNormを入れた場合には最大で78.7%まで向上した．ただし，学習率が0.001，0.01の場合には両方に入れるよりbackboneのみの方がmAP的には良い．

BatchNormを使えばスクラッチからでも十分な性能が出せることが確認できたので，次はより良いbackbone networkの構造を探す．SSDで一般的なVGG-16とResNet-101を比べるとImageNetではResNet-101が良い結果を示しているが，DSSDの論文によるとSSDにおいてはVGG-16の方が良いmAPを達成している．これはResNet-101は最初の段階で一気に解像度を下げていることが原因で，これにより小さな物体の検出が難しくなる．なので入力の解像度をあげれば解決できる問題で実際論文でも解像度が大きい場合にはVGG-16よりもResNet-101が優っている．さらに言えば，cocoデータセットのように検出のカテゴリ数が増えればResNet-101の分類能力の高さが発揮されて入力の解像度が小さくてもVGG-16より良い結果を達成できる．詳細はDSSDの論文読めとのこと．

以上を踏まえて最初のdownsamplingをなくせば大体の状況でVGG-16よりいい精度を出せるだろうということで，Root-ResNetなる構造を提案．提案といっても内容は単純で最初の畳み込みのストライドを1にしてカーネルサイズを3に変更しただけとのこと（この畳み込みをroot blockと定義）．

実験

BatchNormの部分は繰り返しになるので割愛．root-resnetに関してResNet-18を使って検証．ResNetの最初の畳み込みのdownsamplingをなくすだけでmAPが4%ほど改善するそう．さらに最初の畳み込みをカーネルサイズ7の畳み込みの代わりにカーネルサイズ3の畳み込み数回で代用したところ精度が向上．具体的にResNetの構造に対し，7x7を3x3に変えて層の数を3にしたところ2%ちょっと改善，さらにroot-resnetの構造（downsamplingを無くす場合）にすればやはり4%程改善．

様々なベースライン手法とPascalVOCで比較．300x300の解像度を入力としてもスクラッチから学習したroot-resnet-34がほぼ全てを上回るmAPを達成．唯一負けたのがCoupleNetでroot-resnet-34がmAP78.5%に対してCoupleNetが80.4%．またms cocoでの比較ではtwo-stage系の手法（Faster R-CNNなど）には劣る結果．ただし，multi-scale testingをした場合では一応全ての手法を大きく上回っている．

まとめ

SSDの論文書いた人たちはBatchNorm入れてうまくいかなかったとかgithubのissueに書いてた気がするけどなんだろなという気持ち．内容としては技術レポート的な感じだが実践的に役立ちそうなことは多かった．数式は出てこなかったなあ