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

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

MINEを使ってinfoGANを実装した

生成モデル 実装 GAN

はじめに

Mutual information neural estimation（MINE）を使ってinfoGANを実装したのでメモ．MINEに関してのメモはこちら．

設定

オリジナルのinfoGANと同様にMNISTで離散変数1つ，連続変数2つでgeneratorを学習した．infoGANの特徴である相互情報量最大化の部分をMINEに置き換えた．MINEに関しては雰囲気を知りたかったのでだいぶ簡略化した実装にした． 具体的にはMINEのオリジナルの論文ではKLDが無限に大きくなってしまい勾配のバランスが崩れるため，adaptive gradient clippingを使っていたが，今回はKLDではなくDIM（DIMのメモはこちら）で使われていたJensen-Shannonダイバージェンスバージョンを使ってclippingの実装は省いた．また，statistics networkとgeneratorは別々に最適化するところを，これもDIMと同様同時に最適化するようにした．ただし，DIMではgeneratorとstatistics networkの一部を共有していたが完全に別々にした．

モデルはgeneratorとdiscriminator，3つの変数それぞれに対して相互情報量を計算するためのstatistics networkを用意．目的関数は以下のように定義した．

\displaystyle \max_{G, S_1, S_2, S_3}\min_D\mathbb{E}_x[\log D(X)]+\mathbb{E}_z[\log(1-D(G(z))]+\frac{1}{3}\left(\mathcal{I}_{S_1}(G(X),c_1)+\mathcal{I}_{S_2}(G(X),c_2)+\mathcal{I}_{S_3}(G(X),c_3)\right)\\ \displaystyle \mathcal{I}_{S}(X,c)=\mathbb{E}_{P(X,c)}[-softplus(-S(X,c))]-\mathbb{E}_{P(X)P(c)}[softplus(S(X,c'))]

相互情報量は平均をとった．こうしないと相互情報量のロスに引っ張られて生成画像があんまり綺麗にならなかった．

モデルの構成はその辺に落ちてたinfoGANの実装のモデルを真似た．statistics networkに関してはとりあえず画像をベクトル化して潜在変数とくっつけたものを入力とするMLPとして実装した．後一応，discriminatorにはspectral normalizationを付けてる（なくても多分動くんじゃないかな）．

離散変数はonehotベクトルで連続変数とノイズは-1~1の範囲の一様分布からサンプリングした．

実験結果

100エポック学習した結果．100エポックもいらなかった．

離散変数と連続変数の片方を-1から1で動かした場合．

f:id:peluigi:20180829120208p:plain

離散変数と連続変数のもう一方を-1から1で動かした場合．

f:id:peluigi:20180829120216p:plain

思った以上にうまく動いてびっくり．ただ，3と5の区別が微妙な感じなのと文字の太さはあんまり表現できてない．もう少しちゃんと実装すればもっとうまくいくのかどうか． とりあえず現状の実装だと相互情報量がサチってたからこれ以上は無理な気がする．

コード

適当に転がってたGANのコードを改変して作ったのでいろんなところがハードコードされているけどとりあえず動くはず． 以下メインファイル．

import torch
import torch.optim as optim
import torch.nn.functional as F

import numpy as np
import os

import torchvision.utils as vutils
from torchvision.datasets import MNIST
from torchvision.transforms import ToTensor
from torch.utils.data import DataLoader

from model import generator, disciminator, disc_statistics, cont_statistics

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

BATCH_SIZE = 100
NUM_WORKERS = 8
RANGE = 1

G = generator().to(device)
D = disciminator().to(device)
S_disc = disc_statistics().to(device)
S_cont1 = cont_statistics().to(device)
S_cont2 = cont_statistics().to(device)

optimG = optim.Adam(G.parameters(), lr=1e-3, betas=(0.5, 0.999))
optimD = optim.Adam(D.parameters(), lr=2e-4, betas=(0.5, 0.999))
optimS = optim.Adam([{"params":S_disc.parameters()}, {"params":S_cont1.parameters()}, {"params":S_cont2.parameters()}], lr=1e-3, betas=(0.5, 0.999))

train_data = MNIST("./data", train=True, download=True, transform=ToTensor())
loader = DataLoader(train_data, batch_size=BATCH_SIZE, shuffle=True, drop_last=True, num_workers=NUM_WORKERS)

label = torch.zeros(BATCH_SIZE).to(device).float()
real_label = 1
fake_label = 0

c = torch.linspace(-1, 1, 10).repeat(10).reshape(-1, 1)
c1 = torch.cat([c, torch.zeros_like(c)], 1).float() * RANGE
c2 = torch.cat([torch.zeros_like(c), c], 1).float() * RANGE

idx = torch.from_numpy(np.arange(10).repeat(10))
one_hot = torch.zeros((100, 10)).float()
one_hot[range(100), idx] = 1
fix_z = torch.Tensor(100, 62).uniform_(-1, 1)

fix_noise1 = torch.cat([fix_z, c1, one_hot], 1)[...,None,None].to(device)
fix_noise2 = torch.cat([fix_z, c2, one_hot], 1)[...,None,None].to(device)

for epoch in range(100):
    for i, data in enumerate(loader):
        # discriminator
        optimD.zero_grad()
        ## real
        real, _ = data
        real = real.to(device)
        label.fill_(real_label)
        real_prob = D(real).squeeze()
        real_loss = F.binary_cross_entropy_with_logits(real_prob, label)
        real_loss.backward()
        ## fake
        label.fill_(fake_label)
        ### get noise
        idx = torch.randint(0, 10, (BATCH_SIZE,)).long()
        disc_c = torch.eye(10)[idx][...,None,None].float().to(device)
        cont_c = torch.zeros(BATCH_SIZE, 2, 1, 1).uniform_(-1, 1).float().to(device) * RANGE
        z = torch.zeros(BATCH_SIZE, 62, 1, 1).uniform_(-1, 1).float().to(device)
        noise = torch.cat([z, cont_c, disc_c], 1).to(device).float()
        ### generate
        fake = G(noise)

        fake_prob = D(fake.detach()).squeeze()
        fake_loss = F.binary_cross_entropy_with_logits(fake_prob, label)
        fake_loss.backward()
        loss_D = real_loss + fake_loss
        optimD.step()

        # generator
        optimG.zero_grad()
        optimS.zero_grad()
        label.fill_(real_label)
        ## adversarial loss
        inv_fake_prob = D(fake).squeeze()
        inv_fake_loss = F.binary_cross_entropy_with_logits(inv_fake_prob, label)
        ## MINE
        ### c ~ P(C)
        idx = torch.randint(0, 10, (100,)).long()
        disc_c_bar = torch.eye(10)[idx].float().to(device)
        cont_c_bar = torch.zeros(100, 2, 1, 1).uniform_(-1, 1).float().to(device) * RANGE
        ### discrete variable
        joint_disc = S_disc(torch.cat([fake.reshape(100, -1), disc_c.reshape(100, -1)], 1))
        marginal_disc = S_disc(torch.cat([fake.reshape(100, -1), disc_c_bar.reshape(100, -1)], 1))
        ### continuout variable
        joint_cont1 = S_cont1(torch.cat([fake.reshape(100, -1), cont_c[:,0].reshape(100, -1)], 1))
        joint_cont2 = S_cont2(torch.cat([fake.reshape(100, -1), cont_c[:,1].reshape(100, -1)], 1))
        marginal_cont1 = S_cont1(torch.cat([fake.reshape(100, -1), cont_c_bar[:,0].reshape(100, -1)], 1))
        marginal_cont2 = S_cont2(torch.cat([fake.reshape(100, -1), cont_c_bar[:,1].reshape(100, -1)], 1))
        ### calc mutual information
        mi_disc = F.softplus(-joint_disc).mean() + F.softplus(marginal_disc).mean()
        mi_cont1 = F.softplus(-joint_cont1).mean() + F.softplus(marginal_cont1).mean()
        mi_cont2 = F.softplus(-joint_cont2).mean() + F.softplus(marginal_cont2).mean()
        mi = (mi_disc + mi_cont1 + mi_cont2)/3

        loss = mi + inv_fake_loss
        loss.backward()
        optimG.step()
        optimS.step()
        print("epoch [{}/{}], iter [{}/{}], D : {}, G : {}, S : {}".format(
            epoch, 100, i, len(loader), loss_D.item(), inv_fake_loss.item(), mi.item()
        ))
    with torch.no_grad():
        fake1 = G(fix_noise1)
        fake2 = G(fix_noise2)
        if not os.path.exists("results_1"):
            os.mkdir("results_1")
        vutils.save_image(fake1.detach(),
                    "results_1/{}epoch_fake1.png".format(epoch),
                    normalize=True, nrow=10)
        vutils.save_image(fake2.detach(),
                    "results_1/{}epoch_fake2.png".format(epoch),
                    normalize=True, nrow=10)

以下モデルファイル．

import torch.nn as nn

class generator(nn.Module):
    def __init__(self):
        super().__init__()
        self.main = nn.Sequential(
            nn.ConvTranspose2d(74, 1024, 1, 1, bias=False),
            nn.BatchNorm2d(1024),
            nn.ReLU(),
            nn.ConvTranspose2d(1024, 128, 7, 1, bias=False),
            nn.BatchNorm2d(128),
            nn.ReLU(),
            nn.ConvTranspose2d(128, 64, 4, 2, 1, bias=False),
            nn.BatchNorm2d(64),
            nn.ReLU(),
            nn.ConvTranspose2d(64, 1, 4, 2, 1, bias=False),
            nn.Sigmoid()
        )

        for m in self.modules():
            if isinstance(m, nn.ConvTranspose2d):
                nn.init.normal_(m.weight, 0, 0.02)
            elif isinstance(m, nn.BatchNorm2d):
                nn.init.normal_(m.weight, 1, 0.02)
                nn.init.constant_(m.bias, 0)

    def forward(self, x):
        return self.main(x)

class disciminator(nn.Module):
    def __init__(self):
        super().__init__()
        self.main = nn.Sequential(
            nn.Conv2d(1, 64, 4, 2, 1, bias=False),
            nn.LeakyReLU(0.1),
            nn.Conv2d(64, 128, 4, 2, 1, bias=False),
            nn.BatchNorm2d(128),
            nn.LeakyReLU(0.1),
            nn.Conv2d(128, 1024, 7, bias=False),
            nn.BatchNorm2d(1024),
            nn.LeakyReLU(0.1),
            nn.Conv2d(1024, 1, 1, bias=False)
        )

        for m in self.modules():
            if isinstance(m, nn.Conv2d):
                nn.init.normal_(m.weight, 0, 0.02)
                nn.utils.spectral_norm(m, n_power_iterations=2)
            elif isinstance(m, nn.BatchNorm2d):
                nn.init.normal_(m.weight, 1, 0.02)
                nn.init.constant_(m.bias, 0)

    def forward(self, x):
        return self.main(x)

class cont_statistics(nn.Module):
    def __init__(self):
        super().__init__()
        self.main = nn.Sequential(
            nn.Linear(28**2 + 1, 1024, bias=False),
            nn.BatchNorm1d(1024),
            nn.LeakyReLU(0.1),
            nn.Linear(1024, 1024, bias=False),
            nn.BatchNorm1d(1024),
            nn.LeakyReLU(0.1),
            nn.Linear(1024, 1, bias=False),
        )

        for m in self.modules():
            if isinstance(m, nn.Linear):
                nn.init.normal_(m.weight, 0, 0.02)
            elif isinstance(m, nn.BatchNorm1d):
                nn.init.normal_(m.weight, 1, 0.02)
                nn.init.constant_(m.bias, 0)

    def forward(self, x):
        return self.main(x)


class disc_statistics(nn.Module):
    def __init__(self):
        super().__init__()
        self.main = nn.Sequential(
            nn.Linear(28**2 + 10, 1024, bias=False),
            nn.BatchNorm1d(1024),
            nn.LeakyReLU(0.1),
            nn.Linear(1024, 1024, bias=False),
            nn.BatchNorm1d(1024),
            nn.LeakyReLU(0.1),
            nn.Linear(1024, 1, bias=False),
        )

        for m in self.modules():
            if isinstance(m, nn.Linear):
                nn.init.normal_(m.weight, 0, 0.02)
            elif isinstance(m, nn.BatchNorm1d):
                nn.init.normal_(m.weight, 1, 0.02)
                nn.init.constant_(m.bias, 0)

    def forward(self, x):
        return self.main(x)

まとめ

MINEを論文通りに実装しようとするとちょっと面倒かなという印象で逃げてしまった．というかclippingの実装気になるからちゃんとした実装上がって欲しい．

実装は何も考えずにネットワークひとつ用意するだけなのでめちゃくちゃ簡単（厳密にやるともう少し複雑だけどこれでも十分動く）．相互情報量の面だけみればmin-max gameのような不安定要素も入らないのでMINEとても良い．

Learning deep representations by mutual information estimation and maximizationを読んだのでメモ

representation learning mutual information unsupervised

はじめに

Learning deep representations by mutual information estimation and maximizationを読んだのでメモ．Abstractの最後の１文で"DIM opens new avenues for unsupervised learn- ing of representations and is an important step towards flexible formulations of representation-learning objectives catered towards specific end-goals."といっている非常に力強い論文．

気持ち

現状の表現学習はreconstruction lossを使った自己符号化器で行われるものが多いが，それは入力のデータに依存した目的関数になっているからよくないと論文では言っている．Introductionに書いてあるように"is it possible to learn representations with a training objective that is not defined in input space?"というのが論文の思い．

モチベーションとしては，reconstruction lossは相互情報量と以下の関係があるというところから，相互情報量に基づいた表現学習をしようというもの．

\displaystyle \mathcal{I}_e(X,Y)=\mathcal{H}_e(Y)-\mathcal{D}_{KL}(\mathbb{Q}_d(Y|X)||\mathbb{P}_e(Y|X))-\mathcal{R}_{e,d}(X)

\mathcal{H}はエントロピーで下付きのe,dはそれぞれencoder，decoderを表す．また，X,Yは入力と中間表現の確率変数を示す． 上記の式から分かるようにreconstruction loss\mathcal{R}_{e,d}(X)を最小化することは相互情報量を大きくすることにつながる．すなわち，入力Xと中間表現Yが強い関連を持つようになる．同様にBiGANのようなadversarialな表現学習もD_{KL}(\mathbb{P}_d(X,Y)||\mathbb{Q}_e(X,Y))を最小化するという文脈で同様に相互情報量を大きくしている．

Reconstructionを目的関数とした表現学習の問題点は，reconstruction lossを個々のピクセルごとに計算する事で，解像度が高くなると背景のような意味のないピクセルに誤差が引っ張られてしまい真に意味のある表現を獲得する妨げとなる．なので直接的に相互情報量を多くしたいというのが話の流れ．

Deep INFOMAX

提案手法であるDeep INFOMAX (DIM)について．DIMは3つのロスの組み合わせからなる．ここでは入出力間の相互情報量を最大化するようにencoderを学習する問題設定を考える．パラメータ\psiを持つニューラルネットをE_\psi:\mathcal{X}\rightarrow\mathcal{Y}と定義する．ここで入力空間上の経験分布\mathbb{P}に従う学習サンプルの集合\mathcal{X}:\mathbb{X}:=\{x^{(i)}\in\mathcal{X}\}_{i=1}^{N}が与えられたと仮定する．ここで\mathbb{U}_{\psi,\mathbb{P}}=E_\psi\sharp\mathbb{P}をpush-forward distributionとして定義する．Push-forward distributionは\mathbb{P}に従うサンプルをE_\psiに通す事で得られる分布のこと．以下，marginal, joint, product of marginal push-forward distributionを定義する．

\displaystyle \mathbb{U}_{\psi,\mathbb{P}}(Y=y):=\mathbb{P}(\{x^{(i)}\in\mathbf{X}|E_\psi(x^{(i)})=y\}), \\ \displaystyle \mathbb{J}_{\psi,\mathbb{P}}(X=x,Y=y):=\mathbb{P}(X=x)\delta_y(E_\psi(x)), \\ \displaystyle \mathbb{M}_{\psi,\mathbb{P}}(X=x,Y=y):=\mathbb{P}(X=x)\mathbb{P}(\{x^{(i)}\in\mathbf{X}|E_\psi(x^{(i)})=y\}),

ただし，\delta_y(E_\psi(x))はY上でのディラック測度．

Mutual information estimation and maximization

ここではMINEの枠組みに従って相互情報量を推定する．すなわち次のように相互情報量を求める．

\displaystyle \mathcal{I}(X;Y):=\mathcal{D}_{KL}(\mathbb{J}||\mathbb{M})\geq\hat{\mathcal{I}}_\omega(X;Y):=\mathbb{E}_\mathbb{J}[T_\omega]-\log\mathbb{E}_\mathbb{M}[e^{T_\omega}]

ただし，T_\omega:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}でパラメータ\omegaを持つニューラルネットを表す．MINEに関しては以前読んでメモした．この相互情報量を使ってencoder E_\psiを次の目的関数に従って学習する．

\displaystyle (\hat{\omega},\hat{\psi})=\mathrm{arg}\max_{\omega,\psi}\hat{\mathcal{I}}_\omega(X;E_\psi(X))

ここにはMINEと重要な異なる点があり，ここではencoderとMINEが同じ目的関数で最適化される事とどちらもCNNによる計算が行われることから，両方のネットワークの初期レイヤーをE_\psi=f_\psi\circ C_\psi,\:T_{\psi,\omega}=D_\omega\circ C_\psiのように組み合わせる． もう一つの違いは，相互情報量の推定をKLダイバージェンスではなくJensen-Shannonダイバージェンス (JSD)で行っている点． これらの違いにより最終的な目的関数は次のようになる．

\displaystyle (\hat{\omega},\hat{\psi})_G=\mathrm{arg}\max_{\omega,\psi}\hat{\mathcal{I}}_{\omega,\psi}^{(JSD)}(X;E_\psi(X))=\mathrm{arg}\max_{\omega,\psi}\mathbb{E}_{\mathbb{E}_{\psi,\mathbb{P}}}[-\mathrm{sp}(-T_{\psi,\omega}(x,y(x)))]-\mathbb{E}_{\mathbb{M}_{\psi,\mathbb{P}}}[\mathrm{sp}(T_{\psi,\omega}(x',y(x)))]

xは入力のサンプルで，y(x)はhigh-level representation，x'はy(x)に関係のないもう一方のサンプル，\mathrm{sp}(\cdot)はsoftplus関数で\mathrm{sp}(z)=\log(1+e^z)．

このJSDに基づく推定器とKLに基づく推定器は似た振る舞いをするが，JSDベースの方が同時最適するのには適しているとのこと．というのも，相互情報量はunboundedであるから不安定になるのに対し，Jensen-Shannonは上界が\log 2になるため，MINEで行われていたclippingの必要がない．もう一つの理由が，KLのDonsker-Varadhan表現(MINEの論文またはメモを参照)における\logの期待値がバイアスの乗った勾配を導いてしまうのに対しJSDではunbiasな勾配を求めることができる．あとは単純に実験的にJSDが優れていたということらしい．ただ，JSDの場合の相互情報量の式の導出がいまいちわからなかった．

Local mutual information maximization

前節の目的関数は入出力間の相互情報量を最大化することだったが，タスクによってはあまり意味のない表現を獲得する可能性がある．というのも画像の分類問題などでは局所的に見れば意味のないピクセルが存在していて，そのような領域からくる情報は表現獲得の邪魔をする可能性がある．そこで画像分類問題のためにhigh-level representationと画像のlocal patch間の平均相互情報量を最大化することを考える．

Local mutual information maximization frameworkの概要は論文のFigure 3に書いてある．まず初めに画像を特徴マップにエンコードするC_\psi(x):=\{C_\psi^{(i)}(x)\}_{i=1}^{M\times M} (iはパッチのこと)．次にこの特徴マップを大局的な特徴ベクトルy(x)=f_\psi\circ C_\psi(x):=E_\psi(x)へとエンコードする．この特徴ベクトルを\{[C_\psi^{(i)}(x),y(x)]\}_{i=1}^{M\times M}のようにlower-level feature mapと結合し，1\times 1 convolutional discriminatorによりペアスコアを算出する．

\displaystyle T_{\psi,\omega}^{(i)}(x,y(x))=D_\omega([C_\psi^{(i)}(x),y(x)])

上の手順で作った特徴ベクトルをrealとし，fakeは異なる画像x'を使って次のように作る．

\displaystyle T_{\psi,\omega}^{(i)}(x',y(x))=D_\omega([C_\psi^{(i)}(x'),y(x)])

つまりlower-level feature mapを別な画像から作るということ．この場合には次の平均JSD相互情報量を最大化することで学習を行う．

\displaystyle (\hat{\omega},\hat{\psi})_L=\mathrm{arg}\max_{\omega,\psi}\frac{1}{M^2}\sum_{i=1}^{M^2}\hat{\mathcal{I}}^{(JSD)}_{\omega,\psi}(X^{(i)};E_\psi(X))\\ \displaystyle =\mathrm{arg}\max_{\omega,\psi}\frac{1}{M^2}\sum_{i=1}^{M^2}\mathbb{E}_{\mathbb{J}_{\psi,\mathbb{P}}}[-\mathrm{sp}(-T_{\psi,\omega}^{(i)}(x,y(x)))]-\mathbb{E}_{\mathbb{M}_{\psi,\mathbb{P}}}[\mathrm{sp}(T_{\psi,\omega}^{(i)}(x',y(x)))]

Matching representations to a prior distribution

ここではpush-forward distribution\mathbb{U}_{\psi,\mathbb{P}}をprior\mathbb{V}にマッチするように学習する事を考える．priorに合わせるように学習すれば潜在表現をコントロールしやすくなって色々な場面で便利だろうという事．基本的な戦略としては次のmin-max gameによって学習する．

\displaystyle (\hat{\omega},\hat{\psi})_P=\mathrm{arg}\min_\psi\mathrm{arg}\max_\phi\hat{\mathcal{D}}_\phi(\mathbb{V}||\mathbb{U}_{\psi,\mathbb{P}})=\mathbb{E}_\mathbb{V}[\log D_\phi(y)]+\mathbb{E}_\mathbb{P}[\log(1-D_\phi(E_\psi(x)))]

この学習方法はadversarial autoencodersやBiGANに似ているが，generatorがないということが大きな違い．

ここまでで，最初に定式化したglobal mutual information mazimizationとパッチを使うlocal mutual information maximization，最後のprior matchingの3つの目的関数を提案した．ただ，これは全部を同時に使うこともできて，これをここではdeep INFOMAX (DIM)として提案する．

\displaystyle \mathrm{arg}\max_{\omega_1,\omega_2,\psi}(\alpha\hat{\mathcal{I}}_{\omega_1,\psi}(X;E_\psi(X))+\frac{\beta}{M^2}\sum_{i=1}^{M^2}\hat{\mathcal{I}}_{\omega_2,\psi}(X^{(i)};E_\psi(X)))+\mathrm{arg}\min_\psi\mathrm{arg}\max_\phi\gamma\hat{\mathcal{D}}_\phi(\mathbb{V}||\mathbb{U}_{\psi,\mathbb{P}})

\omega_1,\omega_2はlocalとglobalの目的関数に関するdiscriminatorのパラメータで\alpha,\beta,\gammaはハイパーパラメータ．(実験では\alpha=0にしたlocal-onlyと\beta=0にしたglobal-only，\alpha=0.5,\beta=0.1の両方入りを使って比較してたが，local-onlyが一番うまく動いているよう．)

まとめ

設定によっては教師あり（提案手法も識別器は教師ありだけど）より良い精度が出ていて少し驚き． IntroductionからMotivation and Backgroundまでで語られてたコンセプトはなるほどという感じ．

Mutual Information Neural Estimationを読んだのでメモ

mutual information 生成モデル

はじめに

Mutual Information Neural Estimationを読んだのでメモ．書き終わってちょっと殴り書きすぎたと反省．正直このメモ読んでもよくわからないと思う…

気持ち

相互情報量は二つの確率変数の依存関係を知る良い指標だが一般的に計算するのが難しく，離散変数または確率分布が既知の問題を除いて基本的に扱いにくい．また，ノンパラメトリックカーネル密度推定やガウス性を仮定した場合にも高次元になると計算が困難になる．そこでscalableでflexibleでback-prop可能でcompletely trainableな新たな手法を理論解析付きで提案するという話．

相互情報量

相互情報量は簡単に言えば二つの確率変数の依存関係を測る尺度で，相互情報量が0の時二つの確率変数は独立となり，P(X,Y)=P(X)P(Y)のように因子分解された形でかける．相互情報量はいろんな書き方ができるが論文では次の表現を用いる．

\displaystyle I(X;Z):=H(X)-H(X|Z)

Hは相互情報量エントロピーを示し，H(X|Z)は条件付きエントロピーを表す．条件付きエントロピーはH(X|Z)=\mathbb{E}_{P(x),P(Z)}\log P(X|Z)で表すことができる．これらの関係を使うと相互情報量は次のようなKLダイバージェンスの形で表現することができる．

\displaystyle I(X,Z)=-\mathbb{E}_{P(X)}[\log P(X)]+\mathbb{E}_{P(X)P(Z)}[\log P(X|Z)]\\ \displaystyle =\mathbb{E}_{P(X),P(Z)}\left[{\log P(X|Z)}{P(X)}\right] \\ \displaystyle =\mathbb{E}_{P(X),P(Z)}\left[{\log P(X,Z)}{P(X)P(Z)}\right] = D_{KL}(P(X,Z)||P(X)P(Z))

この辺りは情報理論の初等的な教科書に書いてある内容．式からもわかるように相互情報量が大きければP(X,Z)とP(X)P(Z)のKLダイバージェンスが大きくなるということで確率変数X,Zの依存関係が強くなる．

Dual representations of the KL-divergence

以下で説明するDonsker-Varadhan representationとf-divergence representationと呼ばれる二つのKL-divergenceの表現が提案手法の核となる理論らしい．

Theorem 1 (Donsker-Varahan representation)

KLダイバージェンスは次のような表現を持つ．

\displaystyle D_{KL}(\mathbb{P}||\mathbb{Q})=\sup_{T:\Omega\rightarrow\mathbb{R}}\mathbb{E}_{\mathbb{P}}[T]-\log(\mathbb{E}_{\mathbb{Q}}[e^T])

証明

関数Tが与えられた時，d\mathbb{G}=\frac{1}{Z}e^Td\mathbb{Q}で定義されるギブス分布\mathbb{G}を考える．ただし，Z=\mathbb{E}_\mathbb{Q}[e^T]．すると次のような関係を考えることができる．

\displaystyle \mathbb{E}_\mathbb{P}[T]-\log Z=\mathbb{E}_\mathbb{P}[\log e^T]-\log(e^T\frac{d\mathbb{Q}}{d\mathbb{G}}) \\ \displaystyle =\mathbb{E}_\mathbb{P}\left[\log e^T-\log e^T-\log \frac{d\mathbb{Q}}{d\mathbb{G}}\right] \\ \displaystyle =\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{G}}{d\mathbb{Q}}\right]

\Deltaを次のようなgapとして定義する．

\displaystyle \Delta:=D_{KL}(\mathbb{P}||\mathbb{Q})-\left(\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])\right)

すると，\Deltaは次のような\mathbb{P},\mathbb{G}のKLダイバージェンスとして定義できる．

\displaystyle \Delta=\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{P}}{d\mathbb{Q}}-\log\frac{d\mathbb{G}}{d\mathbb{Q}}\right]=\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{P}}{d\mathbb{G}}\right]=D_{KL}(\mathbb{P}||\mathbb{G})

ただし，\mathbb{E}_\mathbb{P}[T]-\log Z=\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{G}}{d\mathbb{Q}}\right]の関係を使った．KLダイバージェンスは負の値を取らないため\Delta\leq 0となりあらゆるTにおいて次の不等式が成立する．

\displaystyle D_{KL}(\mathbb{P}||\mathbb{Q})=\Delta+\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])\geq\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])

上の関係は\mathbb{G}=\mathbb{P}の時に等式が成り立ち，その時d\mathbb{G}=\frac{1}{Z}e^Td\mathbb{Q}よりT^\ast=\log\frac{d\mathbb{P}}{d\mathbb{G}}+Cの形をとる．ただし，Cは定数．この時のT^\astをoptimal functionsとして名付ける．よって，右辺の上界，すなわちTがoptimal functionsである場合等号が成立するのでTheorem 1が成り立つ．

f-divergence representation

KLダイバージェンスは次の下界が成り立つことも知られている．

\displaystyle D_{KL}(\mathbb{P}||\mathbb{Q})\geq\sup_{T\in\mathcal{F}}\mathbb{E}_\mathbb{P}[T]-\mathbb{E}_\mathbb{Q}[e^{T-1}]

一般のT\in\mathcal{F}においてはDonsker-Varadhanの下界の方が負の項が対数表現になっているため上式の下界よりも大きくなることがわかる．

Mutual Information Neural Estimator

提案手法であるMINEの定式化をする．MINEではパラメータ\thetaを持つDNNで表現された関数族T_\theta:\mathcal{X}\times\mathcal{Z}\rightarrow\mathbb{R}によって\mathcal{F}を与える．このネットワークをstatistics networkと呼び，次のような相互情報量の下界を与えるものとする．

\displaystyle I(X;Z)\geq I_\Theta(X,Z)

このI_\Theta(X,Z)をneural information measureと呼び次のように定義する．

\displaystyle I_\Theta(X,Z)=\sup_{\theta\in\Theta}\mathbb{E}_{P(X,Z)}[T_\theta]-\log(\mathbb{E}_{P(X)P(Z)}[e^{T_\theta}])

この期待値はP(X,Z),P(X)P(Z)からのサンプリングなどを用いて計算され，勾配上昇法を使って最大化することで上界を求める．これは情報量の新しいクラスであって，ニューラルネットワークの表現力から任意の精度で相互情報量を近似することができる．

Difinition 3.1 (Mutual Information Neural Estimator)

\mathcal{F}=\{T_\theta\}_{\theta\in\Theta}をニューラルネットで表現される関数の集合とするとMINEは次のように定義される．

\displaystyle \widehat{I(X;Z)_n}=\sup_{\theta\in\Theta}\mathbb{E}_{P^{(n)}(X,Z)}[T_\theta]-\log(\mathbb{E}_{P^{(n)}(X)\hat{P}^{(n)}(Z)}[e^{T_\theta}])

ただし，P^{(n)}はi.i.dに得られたn個のサンプルから計算される経験分布を表す．また，f-divergence representationに従った下界を与えたものをMINE-fとして定義する．今までの議論からMINEとMINE-fを比較すれば，MINEの方が良い近似を与えるが，mini-batchを使ったSGDで求められる勾配にはバイアスがのるとのこと．

Correctiong the bias from the stochastic gradients

MINEの勾配は次のように計算ができる．

\displaystyle \hat{G}_B=\mathbb{E}_B[\nabla_\theta T_\theta]-\frac{\mathbb{E}_B[\nabla_\theta T_\theta e^{T_\theta}]}{\mathbb{E}_B[e^{T_\theta}]}

右辺第2項の期待値はミニバッチBから計算され，full batchの勾配にバイアスがのった推定結果を導く（この辺りがうまく理解できなかったがMINE-fの方はunbiasな勾配を導けるらしい）．ただし，分母を期待値の移動平均として置き換えることでそのバイアスは減らせるらしい．もっと言えばsmall learning rateを使えばバイアスを任意の大きさに抑えることができるとのこと．

Theoretical properties

ここでMINEのconsistencyとconvergenceを解析する．

Consistency

MINEはstatistics networkとデータ分布P(X,Z)からのサンプルの選び方に依存する．

Definition 3.2 (Strong consistency)

次の関係性において全ての\epsilonにおいて\epsilon\lt 0が成り立ち次の関係が成り立つstatistics networkを選択したとき，推定器\widehat{I(X;Z)_n}はstrongly consistentとなる．

\displaystyle \forall n\geq N,\:|I(X,Z)-\widehat{I(X;Z)}_n|\leq\epsilon,\:a.e.

知識不足でconsistencyの意味がいまいちわからなかったが，consistencyの話は\mathcal{F}のサイズに関連したapproximation problemと経験測度（empirical measure）に関するestimation problemの二つの問題に分けられるらしい．

以下，面倒なnotationを避けるため\mathbb{P}=P(X,Z),\:\mathbb{Q}=P(X)P(Z)として定義し．\mathbb{P}_n,\mathbb{Q}_nをempirical versionとする．また，\hat{I}(T)=\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])とする．

Lemma 1 (approximation)

\eta\lt 0とする．compact domainにおいて次の関係を満たすパラメータ\thetaを持つニューラルネットの関数族T_\thetaが存在する．

\displaystyle |I(X,Z)-I_\Theta(X,Z)|\leq\eta,\\ \displaystyle I_\Theta(X,Z)=\sup_{\theta\in\Theta}\mathbb{E}_\mathbb{P}[T_\theta]-\log(\mathbb{E}_\mathbb{Q}[e^{T_\theta}])

証明

T^\ast=\log\frac{d\mathbb{P}}{d\mathbb{Q}}とすると，T^\astは次の式を満たす．

\displaystyle \mathbb{E}_\mathbb{P}[T^\ast]=I(X,Z),\:\mathbb{E}_\mathbb{Q}[e^{T^\ast}]=1

単純に左辺にT^\ast=\log\frac{d\mathbb{P}}{d\mathbb{Q}}を代入すれば求まる．これに対し，関数Tに関して，正のgapI(X,Z)-\hat{I}(T)は次のようにかける．

\displaystyle I(X,Z)-\hat{I}(T)=\mathbb{E}_\mathbb{P}[T^\ast-T]+\log\mathbb{E}_\mathbb{Q}[e^T]\leq\mathbb{E}_\mathbb{P}[T^\ast-T]+\mathbb{E}_\mathbb{Q}[e^T-e^{T^\ast}]

最後の不等式は\log x\leq x-1から\log\mathbb{E}_\mathbb{Q}[e^T]\leq\mathbb{E}_\mathbb{Q}[e^T]-1=\mathbb{E}_\mathbb{Q}[e^T-\frac{d\mathbb{Q}}{d\mathbb{P}}]となることから示せる．

\eta\gt 0の定数とし，T^\astが定数Mによってboundされる場合を考える．ここで，ニューラルネットのuniversal approximation theoremを考えれば，次の関係を満たすfeedforward network functionT_\hat{\theta}\leq Mを選択することができる．

\displaystyle \mathbb{E}_\mathbb{P}|T^\ast-T_\hat{\theta}|\leq\frac{\eta}{2},\:\mathbb{E}_\mathbb{Q}|T^\ast-T_\hat{\theta}|\leq\frac{\eta}{2}e^{-M}

\expが(\infty,M]でe^Mのリプシッツ連続であることから，次の関係が得られる．

\displaystyle \mathbb{E}_\mathbb{Q}|e^{T^\ast}-T^{T_\hat{\theta}}|\leq e^M\mathbb{E}_\mathbb{Q}|T^\ast-T_\hat{\theta}|\leq\frac{\eta}{2}

さらに三角不等式とI(X,Z)-\hat{I}(T)から次の不等式が得られる．

\displaystyle |I(X,Z)-\hat{I}(T_\hat{\theta})|\leq\mathbb{E}_\mathbb{P}|T^\ast-T_\hat{\theta}|+\mathbb{E}_\mathbb{Q}|e^{T^\ast}-e^{T_\hat{\theta}}|\leq\frac{\eta}{2}+\frac{\eta}{2}\leq\eta

一般の場合についても解説されていたが割愛．

Lemma 2 (estimation)

\eta\gt 0とする．compact domain\Theta\subset\mathbb{R}^kにおけるパラメータ\thetaのニューラルネットT_\thetaの族\mathcal{F}が与えられたとき，次の関係を満たすN\in\mathbb{N}が存在する．

\displaystyle \forall n\geq N,\:Pr\left(\widehat{I(X;Z)}_n-I_\mathcal{F}(X,Z)|\leq\eta\right)=1

証明

まずは|\widehat{I(X;Z)}_n-\sup_{T_\theta\in\mathcal{F}}\hat{I}(T_\theta)|に三角不等式を使う．

\displaystyle |\widehat{I(X;Z)}_n-\sup_{T_\theta\in\mathcal{F}}\hat{I}(T_\theta)|\leq\sup_{T_\theta\in\mathcal{F}}|\mathbb{E}_\mathbb{P}[T_\theta]-\mathbb{E}_{\mathbb{P}_n}[T_\theta]|+\sup_{T_\theta\in\mathcal{F}}|\log\mathbb{E}_\mathbb{Q}[e^{T_\theta}]-\log\mathbb{E}_{\mathbb{Q}_n}[e^{T_\theta}]|

導出は\widehat{I(X;Z)}_n,\hat{I}(T_\theta)にそれぞれ代入してT_\theta,e^{T_\theta}でまとめて三角不等式を使うだけ．compact domain\Theta\times\Omega上で定義された関数\theta,\omega\rightarrow T_\theta(\omega)はboundされる．さらに関数T_\thetaは定数Mによって|T_\theta|\leq Mと一様にboundされる．\logが定数[e^{-M},e^M]に対してe^Mのリプシッツ連続であるため次の関係が成り立つ．

\displaystyle | \log \mathbb{E}_\mathbb{Q} [ e^{T_\theta} ] - \log \mathbb{E}_{\mathbb{Q}_n} [ e^{T_\theta} ] | \geq e^M | \mathbb{E}_\mathbb{Q} [ e^{T_\theta} ] -\mathbb{E}_{\mathbb{Q}_n}[e^{T_\theta}]|

\Thetaがコンパクトで，feedforward network functionが連続であることから，関数T_\thetaとe^{T_\theta}の族はuniform law of large numbersを満たすらしい．\eta\gt 0が与えられたとき，次の関係を満たし\forall n\geq NとなるようなN\in\mathbb{N}を選ぶことができる．

\displaystyle \sup_{T_\theta\in\mathcal{F}}|\mathbb{E}_\mathbb{P}[T_\theta]-\mathbb{E}_{\mathbb{P}_n}[T_\theta]|\leq\frac{\eta}{2},\\ \displaystyle \sup_{T_\theta\in\mathcal{F}}|\mathbb{E}_\mathbb{Q}[e^{T_\theta}]-\mathbb{E}_{\mathbb{Q}_n}[e^{T_\theta}]|\leq\frac{\eta}{2}e^{-M}

三角不等式とリプシッツ連続の性質を合わせることで以下の関係が導かれる．

\displaystyle |\widehat{I(X,Z)}_n-\sup_{T_\theta\in\mathcal{F}}\hat{I}(T_\theta)|\leq\frac{\eta}{2}+\frac{\eta}{2}=\eta

よってlemma 2が成り立つ．

Sample complexity

提案している推定器のsample complexityを議論する．まず仮定として，相互情報量はneural information measureI_\Theta(X,Z)によって十分に近似可能であるとする．ここではLemma 2に手を加えてneural information measureの推定量が十分な精度と信頼度を達成するのにどれくらいのサンプル数が必要かを与える．

まず以下の仮定を置く．関数T_\thetaはM-bounded（|T_\theta|\leq M）であり，パラメータ\thetaに関してL-リプシッツであるとする．domain\Theta\subset\mathbb{R}^dがboundされていて，定数Kに関して||\theta||\leq Kが成り立つ．以下の定理はd次元のパラメータ空間において\tilde{O}\left(\frac{d\log d}{\epsilon^2}\right)のsample complexityを持つことを示す．

Theorem 3

任意の値のaccuracy\epsilonとconfidence parameters\deltaが与えられたとき，以下をの関係を満たす．

\displaystyle Pr\left(|\widehat{I(X;Z)}_n-I_\Theta(X,Z)|\leq\epsilon\right)\geq 1-\delta, \\ \displaystyle \mathrm{whenever\:the\:number}\:n\:\mathrm{of\:samples\:satisfies}\\ \displaystyle n\geq\frac{2M^2(d\log(16KL\sqrt{d}/\epsilon)+2dM+\log(2/\delta))}{\epsilon^2}

書くのに力尽きたので証明は割愛．

Maximizing mutual information to improve GANs

実験の一つとして行っていたGANの改善．GANの目的関数は以下のように記述される．

\displaystyle \min_G\max_DV(D,G):=\mathbb{E}_{P(X)}[D(X)]+\mathbb{E}_{P(Z)}[\log(1-D(G(Z))]

ここではinfoGANの枠組みを考えて，入力はノイズとコードを合わせたZ=[\epsilon,c]とする．ここではサンプルとコード間の相互情報量I(G([\epsilon,c]);c)=H(G([\epsilon,c]))-H(G([\epsilon,c])|c)を最大化することでmode collapseが怒るのを防ぐアプローチを考える．するとgeneratorの目的関数は次のようになる．

\displaystyle \mathrm{arg}\max_G\mathbb{E}[\log(D(G([\epsilon,c])))]+\beta I(G([\epsilon,c]);c)

GeneratorはGのパラメータに関して微分可能で，statistics networkは微分可能な関数であることからback-propと勾配上昇法を使うことで相互情報量を最大化することができる．相互情報量は任意の大きさにできてしまうためここではadaptive gradient clippingを使ってdiscriminatorとstatistics networkからくる勾配が同じ程度になるようにしたとのこと．ちなみにadaptive gradient clippingはmutual informationから計算される勾配を次のようにclippingすること．

\displaystyle g_a=\min(||g_u||,||g_m||)\frac{g_m}{||g_m||}

ただし，g_u,g_mはそれぞれdiscriminatorの勾配と相互情報量の勾配．実験結果を見る限りは通常のGANに比べてMode collapsを回避しているよう．

まとめ

証明等をかなり殴り書いたせいで結局論文の主張がこのメモから分かりにくくなってしまったけど，簡単に言えば相互情報量をニューラルネットを使ってI_\Theta(X,Z)=\sup_{\theta\in\Theta}\mathbb{E}_{P(X,Z)}[T_\theta]-\log(\mathbb{E}_{P(X)P(Z)}[e^{T_\theta}]として推定可能で，その推定精度がサンプル数n次第で任意精度を達成可能というところを証明した論文．実装ではGANのように生成モデル+相互情報量を推定するstatistics networkを用意して目的関数に相互情報量の最大化を組み込む感じ．手法自体はすごくシンプルでアルゴリズムテーブル1を見れば実装もなんとなく予想できる．

これかなり有用な手法な気がするので，とりあえず実装してどんなもんか確認したい．ただ実装が公開されてないのとclippingの実装がめんどくさそう．

一応MINEを使ってInfoGANを実装して遊んでみた内容もメモした．

Image Generation from Scene Graphsを読んだのでメモ

graph convolutional network 画像生成

はじめに

Image Generation from Scene Graphsを読んだのでメモ．言語から画像を生成する研究．複雑な文章からでも安定して画像生成ができるとのこと．

概要

ここではシーングラフGとノイズzを入力として画像を生成するモデルfの構築と学習を目標とする．モデルの特徴としてはシーングラフGをgraph convolutionで処理するところで，graph convolutionで埋め込まれた各物体の特徴ベクトルを使って物体とその関係性を考慮したsegmentation maskとBB(bounding box)を生成する．後は得られたsegmentation maskとBBとノイズを合わせて，cascaded refinement network (CRN)で画像\hat{I}を生成するというのが処理の大まかな流れ．

Scene Graphs

モデルの入力となるのは画像のシーングラフで，シーングラフは画像中に何の物体がいて，画像中の物体間にどのような関係性があるかを記述したグラフ．具体的には物体のカテゴリ\mathcal{C}と関係性のカテゴリ\mathcal{R}が与えられた時，グラフはG=(O,E)で記述され，O=\{o_1,\dots,o_n),\:o_i\in\mathcal{C}は物体の集合で，E有向エッジを表し，(o_i,r,o_j),\:o_j\in O,\:r\in Rで形成される．

この論文の問題設定では物体とその関係性を示すカテゴリは言語として与えられるため，自然言語で使われる埋め込み処理によりdenseな特徴ベクトルを作る．

Graph Convolution Network

単語の埋め込みベクトルを持ったシーングラフをend-to-endで処理するために，ここではオリジナルのgraph convolution networkを使う．

入力のグラフ(o_i,r,o_j)が持つ特徴ベクトルを(v_i,v_r,v_j),\:v_i,v_r,v_j\in\mathbb{R}^{N_{in}}とした時，3つの関数g_s,g_p,g_oを使って出力(v_i',v_r')を作る．v_r'を出力する関数g_pは関係性のベクトルが二つの物体からのみ決められるため単純で，v_r'=g_p(v_i,v_r,v_j)として3つのベクトルを入力とする関数．逆に物体に関するベクトルo_iを更新する場合は，ひとつの物体が複数の物体と関係性を持つためv_rの更新よりも複雑になる．もっと言えば，今回は有向グラフを考えているため，入ってくるエッジと出て行くエッジで意味合いが変わってくる．当然ある物体o_iに関するベクトルv_iはo_iと関係性を持つ全ての物体のベクトルを使って更新されるべきである．そこで，o_iから伸びる全てのエッジに対してg_sを使ってcandidate vectorを計算する．それと同様にo_iに入るエッジに対してg_oを使ってcandidate vectorを計算する．

\displaystyle V_i^s=\{g_s(v_i,v_r,v_j):(o_i,r,o_j)\in E\}\\ \displaystyle V_i^o=\{g_o(v_j,v_r,v_i):(o_j,r,o_i)\in E\}

このように各方向のエッジに関するcandidate vectorの集合が得られたらo_iに関する出力v_i'をv_i'=h(V_i^s\cup V_i^oとして計算する．ただし，hは入力の集合をひとつのベクトルにするpooling関数．この論文では各関数g_s,g_p,g_oは3つのベクトルを入力とするニューラルネットで構成したとのこと．また，pooling関数hは入力のベクトルを平均する関数として定義したらしい．

Scene Layout

Graph convolution networkによってシーングラフからいい感じの情報を抽出した後はグラフで表現された情報を画像に起こす必要がある．ここでは画像生成の第１段階としてシーングラフをシーンレイアウトへと変換することを考える．シーンレイアウトはsegmentation maskとBBから作られ，maskとBBの推定にobject layout networkを使う．

Object layout networkは物体に関する埋め込みベクトルv_iを入力とし，M\times Mのsoft binary mask \hat{m}_iとBBの座標\hat{b}_i=(x_0,y_0,x_1,y_1)を出力する．要はGANのgeneratorの入力ノイズがgraph convolution networkで計算された物体の特徴ベクトルになったということ．細かいことを言えば，maskを出力するネットワークはtranspose convolutionで構成されたネットワークで最終層の活性化関数はsigmoid，BBを出力するネットワークは一般的な多層ニューラルネット．Object layout networkによって出力されたmaskはBBの領域にwarpされ，最終的に全ての物体に関するマスクを統合することでシーンレイアウトを作る．学習中はBBはground-truthを使ってシーンレイアウトをつくることに注意．

Cascaded Refinement Network

シーンレイアウトができたら後はそれをリアルな画像に起こすだけ．ここでは従来手法のCascaded Refinement Network (CRN)を使うとのこと．Cascadedと言うように，解像度を2倍にして行くmoduleを多段に積み上げていて，各moduleはシーンレイアウトと前のmoduleの出力を入力とする(ただし最初のmoduleは前段の出力の代わりにガウスノイズを入力とする)．

Discriminator

ここまでで，シーングラフからの特徴抽出，シーンレイアウトの生成，画像の生成という3段構成で画像を生成したが，このプロセスをまとめて画像生成ネットワークfとしてend-to-endで学習する．学習はGANの枠組みに沿って行われ，discriminatorとしてD_{img},D_{obj}の二つを用意する．D_{img}は画像全体を入力とし，D_{obj}は物体領域を切り取って固定サイズにリサイズしたものを入力とする．要は画像全体のそれっぽさと物体のそれっぽさをそれぞれ学習するということ．ただし，D_{obj}は物体の分類問題も同時に解く．

Training

モデルが3段階構成でそれぞれGTを必要とするのでロスは結構複雑．まとめると次の6つのロスの重み付き和を最小化するように学習する．

・Box Loss Object layout networkのBBに関するロスでL_1 loss

・Mask Loss Object layout networkのmaskに関するロスでcross-entropy loss

・Pixel loss 画像の再構成に関するロスで，生成画像と真の画像とL_1 loss

・Image adversarial loss D_{img}に関するmin-max game

・Object adversarial loss D_{obj}に関するmin-max game

・Auxiliarly classifier loss D_{obj}の物体の分類問題に関するロス．

まとめ

これ学習できるのすごいなという気持ち．複雑なモデルを思いついても実際に学習させきる力がないからそういう力も養っていきたい．

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKSを読んだのでメモ

graph convolutional network

はじめに

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKSを読んだのでメモ．

Fast approximate convolutions on graphs

ここでは次のような多層のgraph convolutional networks（GCN）を考える．

\displaystyle H^{(l+1)}=\sigma\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)}\right)

\tilde{A}=A+I_Nは無向グラフ\mathcal{g}に自己ループを加えた隣接行列を表し，\tilde{D}_{ii}=\sum_j\tilde{A}_{ij}とW^{(l)}は学習パラメータ．\sigma(\cdot)はReLUなどの活性化関数で，H^{(l)}\in\mathbb{R}^{N\times D}はl層目の出力．

Spectral graph convolution

グラフフーリエ変換によるグラフ上でのフィルタリングは次のような入力信号x\in\mathbb{R}^Nと\thetaをパラメータとするフィルタg_\theta=\mathrm{diag}(\theta)の積によって表現される．

\displaystyle Ug_\theta U^{T}x

ここでUはnormalized graph LaplacianL=I_N-D^{-1/2}AD^{-1/2}=U\Lambda U^Tの固有ベクトルで，\Lambdaは固有値を対角成分とする対角行列．ここでg_\thetaは固有値の関数g_\theta(\Lambda)と見ることができる．ここでの問題として，固有ベクトル行列Uの行列積が\mathcal{O}(N^)となり計算コストが高いことと，グラフラプラシアンの固有値分解の計算が巨大なグラフに対しては現実的でないことがあげられる．ここでは次のようなk次のチェビシェフ多項式による近似を使ってこの問題を回避する．

\displaystyle g_{\theta'}(\Lambda)\approx\sum_{k=0}^K\theta_k'T_k(\tilde{\Lambda})

ただし，\tilde{\Lambda}=\frac{2}{\lambda_{\mathrm{max}}}\Lambda-I_Nで\lambda_{\mathrm{max}}はLの最大固有値．また，\theta'\in\mathbb{R}^Lはチェビシェフ係数．チェビシェフ多項式はT_k(x)=2xT_{k-1}(x)-T_{k-2}(x),\:T_0(x)=1,\:T_1(x)=xとして再帰的に計算される．

畳み込みの話に戻れば，近似を使った畳み込みの計算は以下のように定義される．

\displaystyle Ug_\theta U^{T}x\approx\sum_{k=0}^K\theta_k'T_k(\tilde{L})x

ただし，\tilde{L}=\frac{2}{\lambda_{max}}L-I_N．重要なのはチェビシェフ多項式の次数Kがフィルタサイズと対応している．ここまでは前回読んだ論文の内容．

Layer-wise linear model

この論文ではチェビシェフの多項式で近似されたモデルに対しK=1の場合のみについて考える．この場合モデルはグラフラプラシアンに関して線形になっている．そのためモデルの表現力は大きく下がるが，そこはNNの多層構造によって補う．むしろK=1とすることで，過学習を抑制する効果が期待できる．

以降，計算を簡単にするため\lambda_{\max}\approx 2として扱う．この近似のもとではgraph convの計算式は以下のようになる．

\displaystyle \theta_0'x+\theta_1'(L-I_N)x=\theta_0'x+\theta_1'D^{-1/2}AD^{-1/2}x

これは\theta_1,\theta_2という二つの学習パラメータを持つ．そこで，過学習を抑制するためのさらなるパラメータ数の制限として以下のような表現を用いる．

\displaystyle \theta\left(I_N+D^{-1/2}AD^{-1/2}\right)x

ここでは一つのパラメータ\theta=\theta_0'=-\theta_1'のみを持つ．こんなんありかという感じだがまあ実験的にはいいんでしょう．グラフ上でのフィルタリング処理は元々はグラフ信号処理で研究されていたものなので，deep neural netに適用した際に勾配消失や爆発に関する問題を避けるような工夫はない．そこでさらなるテクニック(論文中でrenormalization trickと呼ばれていた)として，I_N+D^{-1/2}AD^{-1/2}\rightarrow \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}という変換を行う．ただし，\tilde{A}=A+I_N,\:\tilde{D}_{ii}=\sum_j\tilde{A}_{ij}．これにより勾配の消失，爆発を抑制できるらしい（よくわからない）．

ここまでの定義を，入力信号X\in\mathbb{R}^{N\times C} (Cは入力のチャネル数)に対して一般化すると次のようにかける．

\displaystyle Z=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X\Theta

\Theta\in\mathbb{R}^{C\times F}は学習パラメータで，Z\in\mathbb{R}^{N\times F}は出力．計算オーダーとしては\mathcal{O}(|\mathcal{E}|FC)となり，\tilde{A}Xは疎な行列と密な行列の積として実装可能．

Semi-supervised node classification

今まで頑張って定義したGCNを使ってsemi-supervised learningをしようというもの．基本的には最終層にsoftmax関数をかけて得た出力Zと，正解ラベルYを使って次のcross-entropyを最小化するよう学習する．

\displaystyle L=-\sum_{l\in\mathcal{Y}_L}\sum_{f=1}^FY_{lf}\mathrm{ln}Z_{lf}

\mathcal{Y}_Lはラベルを持つ各ノードの集合．要はラベルがあるノードだけを使って分類問題を学習するという単純なもの．ただし，この論文ではSGDではなくbatch gradient descentで学習したとのこと．ただし，確率要素を加えるためdropoutを使ったらしい．dropout使うならデータをサンプリングしてSGDでやってもいい気はするけどどうなんでしょうという気持ち．

まとめ

Renormalizationのあたりがよくわからなかったが実験的にはrenormした方が精度が上がっていた．renormしないほうがresnetの残差学習の形になっていていい気がするんだけどよくわからん．でもこの論文の実験結果からもパラメータ2つより1つにした方が精度上がってたから，前の論文でチェビシェフ使った近似の方が精度良くなってたのはやっぱりパラメータ数が減ったからなのか．

後，ひとつ面白かったのはAppendixのBの実験で，2,3層くらいの浅いモデルが一番汎化して精度がよかったこと．データセットの問題かグラフデータの性質かモデルが悪いのかわからないけどGCNでdeepなモデルを学習するのはひとつの課題っぽい．

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringを読んだのでメモ

graph convolutional network

はじめに

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringを読んだのでメモ．

Convolution on Graph

この論文ではグラフフーリエ変換に基づく畳み込みを考える．

Graph Fourier transform

無向グラフ\mathcal{g}=(\mathcal{V},\mathcal{E},W)で定義された信号を考える．\mathcal{V}は|\mathcal{V}|=n個の頂点集合，\mathcal{E}はエッジの集合，W\in\mathbb{R}^{n\times n}は重み付きの隣接行列を表す．D\in\mathbb{R}^{n\times n}を対角行列D_{ii}=\sum_jW_{ij}とすれば，非正規化ラプラシアンはL=D-W\in\mathbb{R}^{n\times n}，正規化ラプラシアンはL=I_n-D^{-1/2}WD^{-1/2}として表現される．グラフラプラシアンは実対称半正定値行列であるため直交固有ベクトル\{u_l\}_{l=0}^{n-1}\in\mathbb{R}^nを持ち，非負の固有値\{\lambda_l\}_{l=0}^{n-1}を持つ．グラフラプラシアンの固有ベクトルはフーリエ基底U=[u_0,\dots,u_{n-1}]\in\mathbb{R}^{n\times n}として知られ，固有値分解からグラフラプラシアンはフーリエ基底をもちいてL=U\Lambda A^Tとして表現できる．グラフ上に定義された信号x\in\mathbb{R}^nのフーリエ変換は\hat{x}=U^Tx\in\mathbb{R}^n，逆フーリエ変換はx=U\hat{x}として記述される．

Spectral filtering of graph signals

以前読んだ論文と変わりないのでさっくりと式だけ．Fourier domainで定義された信号xに対するパラメータ\theta\in\mathbb{R}^nを持つフィルタg_\thetaによる畳み込みは次のように表現できる．

\displaystyle y=g_\theta(L)x=g_\theta(U\Lambda U^T)x=Ug_\theta(\Lambda)U^Tx

ただしフィルタはg_\theta(\Lambda)=\mathrm{diag}(\theta)．

Polynomial parametrization for localized filters

グラフ上でのフィルタの学習はvertex domainでの局所性を考慮できないこととパラメータが\mathcal{O}(n)とデータの次元によるという問題がある．そこでこの論文ではこの問題を解決するため次のような多項式展開したフィルタを使う．

\displaystyle g_\theta(\Lambda)=\sum_{k=0}^{K-1}\theta_k\Lambda^k

パラメータ\theta\in\mathbb{R}^Kは多項式の係数．頂点iを中心とするフィルタg_\thetaの頂点jの値は(g_\theta(L)\delta_i)_j=(g_\theta(L))_{i,j}=\sum_k\theta_k(L^k)_{i,j}で与えられ，カーネルはクロネッカーのデルタ\delta_i\in\mathbb{R}^nによって表現される．ここで，グラフ上の2つの頂点を最短距離で結ぶパスのエッジの数がd_\mathcal{g}(i,j)\gt Kである時(L^K)_{i,j}=0であることが知られている．結果としてラプラシアンのK次の多項式で表現されるspectral fileterはK近傍までの頂点を含んだ計算になっていることがわかる(つまりKを畳み込みのカーネルサイズとした時に(L^K)_{i,j}=0からKより遠い頂点は畳み込みの計算に含まれないということ)．さらにパラメータ数も\mathcal{O}(K)になっていて従来のCNNと同様のオーダーになっている．

Recursive formulation for fast filtering

ここがこの論文の主な貢献部分．基本的にフィルタリングの処理y=Ug_\theta(\Lambda)U^Txは\mathcal{O}(n^2)の計算コストがかかる．解決方法としては前節のようなLから再帰的に計算可能な多項式関数としてg_\theta(L)を定義することが考えられる．疎な行列Lに対してK回行列積を計算する時その演算回数のオーダーは\mathcal{O}(K|\mathcal{E}|)\ll\mathcal{O}(n^2)になる．グラフ信号処理においてはグラフ上での畳み込みにおけるフィルタの多項式表現は昔から研究されていて，一般的な方法としてチェビシェフ多項式を使ってフィルタの近似をする方法がある．そこでここではチェビシェフ多項式を使ってフィルタを近似する．

k次のチェビシェフ多項式T_k(x)はT_k(x)=2xT_{k-1}(x)-T_{k-2}(x),\:T_0=1,\:T_1=xとして計算することが可能．この多項式はdy/\sqrt{1-y^2}を測度とするヒルベルト空間L^2([-1,1],dy/\sqrt{1-y^2})を作ることが知られている(ちなみにこのあたりの初等的な教科書として金谷 健一先生の「これならわかる応用数学教室」などが自分のような数学弱者にも優しい)．K-1次のチェビシェフ多項式を使えばフィルタは次のように定義できる．

\displaystyle g_\theta(\Lambda)=\sum_{k=0}^{K-1}\theta_kT_k(\tilde{\Lambda})

\theta\in\mathbb{R}^Kはチェビシェフ係数でT_k(\tilde{\Lambda})\in\mathbb{R}^{n\times n}は\tilde{\Lambda}=2\Lambda/\lambda_{max}-I_nによって計算されるk次のチェビシェフ多項式．\bar{x}_k=T_k(\tilde{L})x\in\mathbb{R}^nと定義すれば，チェビシェフ多項式の再帰関係から\bar{x}_k=2\tilde{L}\bar{x}_{k-1}-\bar{x}_{k-2},\:\bar{x}_0=x,\:\bar{x}_1=\tilde{L}xとして計算することができ，フィルタリング計算y=g_\theta(L)x=[\bar{x}_0,\dots,\bar{x}_{K-1}]\thetaの演算回数は\mathcal{O}(K|\mathcal{E}|)になる．

Learning filters

サンプルsのj番目の出力の特徴マップは次のように計算できる．

\displaystyle y_{s,j}=\sum_{I=1}^{F_{in}}g_{\theta_{i,j}}(L)x_{s,j}\in\mathbb{R}^n

x_{s,i}は入力の特徴マップでチェビシェフ係数\theta\in\mathbb{R}^{F_{in}\times F_{out}\times K}が学習係数となっている．よって最終的な計算コストは\mathcal{O}(K|\mathcal{E}|F_{in}F_{out}S)になる．フィルタリング処理の入力と学習パラメータに関するbackprop中の微分計算は次のようになる．

\displaystyle \frac{\partial E}{\partial \theta_{i,j}}=\sum_{s=1}^S[\bar{x}_{s,i,0},\dots,\bar{x}_{s,i,K-1}]^T\frac{\partial E}{\partial y_{s,j}}\\ \displaystyle \frac{\partial E}{\partial x_{s,i}}=\sum_{j=1}^{F_{out}}g_{\theta_{i,j}}(L)\frac{\partial E}{\partial y_{s,j}}

ただし，Eは目的関数でSはミニバッチ内のサンプル数．

Graph Coarsening

ここではグラフ上でのプーリングについて考える．グラフ上のプーリングは基本的に近傍の似た頂点同士を一つのクラスタにまとめる処理を指す．ただし，グラフのクラスタリングはNP-hardであることが知られていて一般的には何らかの近似を用いなければならない．Grapn Convの文脈ではマルチレベルなクラスタリングが可能でダウンサンプリングのスケールがコントロールできる必要がある．この論文ではGraclus multilevel clustering algorithmを転用したとのこと．このアルゴリズムはgreedy algorithmの一種で，クラスタが割り振られていないノードを適当に取り出して局所的なnormalized cut W_{ij}(1/d_i+1/d_j)を最大化するような近傍のノードjを選んでクラスタリングする．

Fast Pooling of Graph Signals

グラフ上でプーリングの処理は単純に行うと対応関係を保持する必要があって計算コストが非常にかさむ．そこでこの論文ではちょっとした工夫をして1Dプーリングと同程度の計算効率でgraph poolingを行う．具体的にはbalanced binary treeの構築と頂点の振り直しの二つの処理によって効率化する．

グラフ上でのプーリング処理が行われた場合，プーリング後のグラフの各ノードはプーリング前の2つ，もしくは1つのノードと結びつくことになる．そこで，全てのノードが二つの子ノードを持つように擬似ノード(fake node)を作る(これがbalanced binary tree)．すると，全てのノードは(1)二つの真のノードを持つ(2)1つの真のノードと1つの擬似ノードを持つ(3)2つの擬似ノードを持つ３種類のノードに分けられる．ただし，全ての擬似ノードは(3)にあたる．擬似ノードはプーリング後に影響を及ぼさないような値，例えばReLUを活性化関数に使ってmaxpoolingをする場合は0などの値で初期化される．当然擬似ノードを導入するとその分次元が増えて計算コストは増えるが，実験的にGraclus algorithmを使った時には孤立ノードは少量しか出ないため特に問題はないとのこと．

で，このbalanced binary treeを作ることの何がいいかというと，こうして作られたグラフは二つのノードを一つにまとめることでプーリングされる，すなわち孤立ノードがないため綺麗に番号を並び替えることで1Dプーリングと同様の演算でプーリングを行うことが可能なため高速に演算することができる．Figure 2にこのプーリング処理の図解があるのでそこを見ればわかりやすい．ちなみに，今までの説明はスケールを２分の１にする際の処理だが，ダウンサンプリングのスケールを大きくしたい場合にはスケールに対応した数の子ノードを持つように擬似ノードを導入すればいい．

まとめ

実験で面白かったのは普通にフィルタの重みを用意するより多項式近似の形にした方が精度がよかったというところ（MNISTでの実験だからなんとも言えないが）．普通のspectral filteringの方法で学習するとパラメータ多すぎて過学習気味になるってことなのかなんなのか．

Spectral Networks and Deep Locally Connected Networks on Graphsを読んだのでメモ

graph convolutional network

はじめに

Spectral Networks and Deep Locally Connected Networks on Graphsを読んだのでメモ．前回spectral clusteringの勉強の中でgraph Laplacianについて触れたので，せっかくだから今一度いわゆるgraph convolution関連の論文を読み漁ろうかなと．この論文は2013年の論文で，サーベイ不足でなければ世間で言われているgraph convolutionをちゃんと定式化した最初の論文．

CNNとgraph

Convolutional Neural Networks (CNNs)は基本的にregular grid上のデータ(画像や動画など)を処理する上で優れた性能を発揮している．特に，そのregular gridの構造をうまく使うことでパラメータ数の大きな削減ができていることがポイント．具体的には以下の3つがCNNの重要な点．

  1. The translation structure (一般的な線形写像の代わりにfilterを使うことによるweight sharing)
  2. The metric on the grid (入力信号に比べて非常に小さいサイズのフィルタの適用)
  3. The multi scale dyadic clustering of the grid (strideが2以上のconvolutionやpoolingによるsubsampling)

ただし，CNNはregular gridでない，一般的なgraph構造を持つデータには適用できない．そこでここではCNNの拡張として2つの構造を提案する．最初に2.と3.を一般のgraphに拡張したSpatial Constructionを導入し，次にFourier domainにおける畳み込みを使うSpectal Constructionを導入する．

Spatial Construction

入力データとして重み付きグラフG=(\Omega, W)を考える．\Omegaはサイズmの離散集合でグラフの頂点を表現するもの．Wはm\times mの要素が非負の対象行列でいわゆる重み付きの隣接行列．

Wにおける局所性

局所性(隣接関係)はグラフにおいて簡単に一般化が可能．例えば，Wにおける隣接の定義はある閾値\delta\gt 0を超えるものとして以下のように記述可能．

\displaystyle N_\delta(j)=\{i\in\Omega :W_{ij}\gt\delta\}

この定義によって与えられる隣接関係を使えば，局所的な接続のみを見ることでCNNと同様にパラメータ数を減らすことができる，

グラフ上でのMultiresolution

CNNで使われるpooling等によるsubsampling layerはgridのmultiscale clusteringとして考えることが可能．multiscael clusteringはクラスタに含まれる全ての頂点の持つ特徴量を入力として，クラスタの代表値として一つの特徴量を出力する関数として考えることができる．クラスタリングのためのクラスタはgraph Laplacianの文脈で様々な研究がされているためここではあまり深入りせず，naive agglomerative methodを使ってクラスタを決めるとのこと．このクラスタリングのクラスタ数によってグラフの解像度が決定する．

Deep locally connected networks

グラフにおける局所性と解像度が定義できたので一般化されたネットワークを導入する．まずネットワークによる計算の前にグラフのmultiscale clusteringから始める． ここではK個のスケールを考える．入力として\Omega_0=\Omegaを定義し，各スケールk=1,\dots,Kにおけるグラフのクラスタリング結果を\Omega_kとする．ただし，\Omega_kは\Omega_{k-1}をd_k個のクラスタに分けた結果．さらに，kにおける隣接関係は次のように与えられる．

\displaystyle \mathcal{N}_k=\{\mathcal{N}_{k,i};i=1,\dots,d_{k-1}\}

以上を使って，ネットワークの第k層を定義する。入力は\Omega_0で定義される実数の信号とし，f_kを第k層のフィルタの数とする．ネットワークの第k層は\Omega_{k-1}で記述されるf_{k-1}次元の信号を\Omega_kで記述されるf_k次元の信号へと変換する．

より一般的に，k層目の入力をx_k\in\mathbb{R}^{d_{k-1}\times f_{k-1}}とすればその出力x_{k+1}は次のように記述される．

\displaystyle x_{k+1,j}=L_kh\left(\sum_{i=1}^{f_{k-1}}F_{k,i,j}x_{k,i}\right)\:\:(j=1,\dots,f_k)

F_{k,i,j}\in\mathbb{R}^{d_{k-1}\times d_{k-1}}は隣接関係\mathcal{N}_kに従って定義されるスパースな行列．L_kは出力を\Omega_kに従ってクラスタリングするプーリングの操作を表す．

論文の文章を無視して簡単にまとめると，上の式のi,jはそれぞれCNNでいう入力のチャネルと出力のチャネルを表していて，F_{k,i,j}は隣接関係があるとこのみ値を持つd_{k-1}\times d_{k-1}行列，すなわちF_k自体はF_k\in\mathbb{R}^{f_{k-1}\times f_k\times d_{k-1}\times d_{k-1}}になる．またx_{k.i}\in\mathbb{R}^{d_{k-1}}からF_{k,i,j}x_{k,i}は行列とベクトルの積になっていて，要は隣接関係のあるノードにだけ重みをかけて総和を取る処理になっている．それに加えて\sum_{i=1}^{f_{k-1}}でチャネルでの総和を取っているため，CNNと同一の処理（空間方向，チャネル方向に重みをかけて総和）になっていることがわかる．

ここでは隣接関係\mathcal{N}_kは次の手順によって得られる．

\displaystyle W_0=W \\ \displaystyle A_k(i,j)=\sum_{s\in\Omega_k(i)}\sum_{t\in\Omega_k(j)}W_{k-1}(s,t),\:(k\leq K) \\ \displaystyle W_k=\mathrm{rownormalize}(A_k),\:(k\leq K) \\ \displaystyle \mathcal{N}_k=\mathrm{supp}(W_k),\:(k\leq K)

またクラスタリング結果\Omega_kはここでは\epsilon coveringで与える．\epsilon coveringは類似度カーネルK (ガウスカーネル等)とグラフの分割結果\mathcal{P}=\{\mathcal{P}_1,\dots,\mathcal{P}_n\}を使って\sup_n\sup_{x,x'\in\mathcal{P}_n}K(x,x')\geq\epsilonとして分割を与える方法で，簡単にいってしまえば以前のspectral clusteringの勉強でやったfully connected graphに閾値を設けてグラフを分割するという感じ．

ここでS_kを各ノードの隣接ノード数の平均とすれば，k層における学習パラメータのオーダーは\mathcal{O}(S_k\cdot|\Omega_k|\cdot f_k\cdot f_{k-1})となる．

ただ，論文にも書いてあるよう，隣接関係はデータごとに違うためweight shareの構造を導入するのは容易ではなく，単純に実装してしまえばF_k\in\mathbb{R}^{f_{k-1}\times f_k\times d_{k-1}\times d_{k-1}}を学習パラメータとして持つことになる．一応グラフ全体を低次元空間に埋め込むというのが回避策として書かれているが，この論文で考えているようなデータではそこまで高次元のものはほとんど出てこないからおっけー的なことも主張している．

Spectral Construction

今度はgraph Laplacianの固有値を使った畳み込みの一般化を考える．

重み付きグラフ上での調和解析

ここではgraph Laplacianの呼び方は前回の勉強のメモに合わせて，L-D-Wをunnormalized Laplacian，\mathcal{L}=I-D^{-1/2}WD^{-1/2}をnormalized Laplacianとする（論文ではそれぞれcombinatorial Laplacian，graph Laplacianと定義している）．ここではシンプルにunnormalized Laplacianを使う．仮に信号xをm次元のベクトルとすれば，ノードiにおける信号の変化の滑らかさ||\nabla x||^2_W (グラフにおける周波数)は次のように定義できる．

\displaystyle ||\nabla x||^2_W(i)=\sum_jW_{ij}[x(i)-x(j)]^2

さらに全体としては

\displaystyle ||\nabla x||^2_W=\sum_i\sum_jW_{ij}[x(i)-x(j)]^2

となる．上記の定義に従えば最も滑らかなベクトルは常に

\displaystyle v_0=\mathop{\mathrm{argmin}}_{x\in\mathbb{R}^m,||x||=1}||\nabla x||^2_W=(1/\sqrt{m})1_m

となり，続く値

\displaystyle v_i=\mathop{\mathrm{argmin}}_{x\in\mathbb{R}^m,||x||=1,x\perp\{v_0,\dots,v_{i-1}\}}||\nabla x||^2_W

はLの固有ベクトルで与えられる．最小化問題の解v_iがLの固有ベクトルから得られるのは2x'Lx=\sum_i\sum_jW_{ij}[x(i)-x(j)]の関係からわかる．この関係の証明は前の記事参照． 各固有ベクトルに対応する固有値\lambda_ijはgridに定義された信号のフーリエ係数として見ることができ，同様に固有ベクトルはフーリエ基底として考えられる． 直感的なところではグラフにおける周波数||\nabla x||^2_Wのargminがgraph Laplacianの固有ベクトルから与えられることと，固有値と固有ベクトルの関係からLx=\lambda xの関係が成り立つ，すなわちグラフの構造を表すLが固有ベクトル（フーリエ基底）とその固有値による線形結合で与えられることからフーリエ変換としてみなせるというもの？（グラフ信号処理ど素人の自分なりの解釈なので自信はない）

以上を踏まえれば信号の変換はフーリエ基底の結合係数を変化させることと考えられる，すなわち固有ベクトルとdiagonalな行列の積として考えられるためパラメータ数は\mathcal{O}(m^2)から\mathcal{O}(m)として表現できる．

Extending convolutions

ここまでの関係を使って，ネットワークの定義を行う．Vをgraph Laplacianの固有ベクトルとする．すると第k=1,\dots,K層における入力x_k\in\mathbb{R}^{|\Omega|\times f_{k-1}}に対する変換はsubsamplingを考えなければ次のようにかける．

\displaystyle x_{k+1,j}=h\left(V\sum_{i=1}^{f_{k-1}}F_{k,i,j}V^Tx_{k,i}\right)\:\:(j=1,\dots,f_k)

F_{k,i,j}は対角行列で，hは非線形関数を表す．実験的に，graph Laplacianの最初のd個の固有ベクトルを使う場合の方がいい場合があるらしい（つまりは高周波成分は無視するということ）．仮にd個の固有ベクトルを使ったとすれば，学習パラメータのオーダーは\mathcal{O}(f_{k-1}\cdot f_k\cdot d)になる．ただし，計算コストの面においてはVとV^Tの積があるため非常に大きくなっていることには注意（加えてgraph Laplacianの固有ベクトルを求める必要もある）．

まとめ

この論文が出た時点ではまだまだgraph convolutionは問題点が多いから，最新の論文がどれくらい進化しているか楽しみ．また続けて関連論文を読んで行きたいところ．