AI.doll

にゃーん(機械学習, 深層学習, 強化学習のメモ。)

GAN

{} クラスメイトと隔週くらいで論文1本ずつ読んできてお互いに解説し合えば2倍のはやさで読めるし理解深まるくない?みたいになった。 その解説のためにスライド作るならブログにしてそれ見せて説明すれば残しとけて良くない?っておもったのでブログにしてみた。 今週はあとあとCycleGANとかの解説もしたいしGANの最初の論文にしといた。

目次

読んだ論文

Generative Adversarial Networks

概要

端的にいうとGANは教師なし学習で、データの確率分布を学習している。
最大の特徴は学習時、2つのモデル G (Generator)と D (Discriminator)を用意する点である。
 Gはランダムノイズから学習データと同じ形の出力を生成する。(つまりデータが28×28の画像(行列)なら28×28の行列を出力)  Dは与えられたデータが訓練データのもの(つまり、現実に存在するもの)なのか Gが生成したものなのかを判別する。
 Gは自分が生成した出力を Dが訓練データのものと間違うように学習して、 Dはできるだけ正しく判別できるように学習する。 このように、 G Dも目的が明確になり、評価関数を定義できるので、それぞれそれを最適化するように学習すればよい。

理論

以下、データのサンプリングされる空間の全体を X, ランダムノイズのサンプリングされる空間を Zとする。(つまりデータが2次元平面上の1点だとするとX={\mathbb R}^{2})
すでに述べたように、GANの学習ではGenerator  GとDiscriminator  Dの2つを学習する。
 Dは確率を出力するような関数で、その確率というのは(正しく学習されていれば)与えられたxが現実のデータのものである確からしさである。
以上から、GANで使用される評価関数が次式で与えられるのは自然に感じるはず。 $$ V(G, D) = {\mathbb E}_{x\sim p_{data}}\left[\log D(x)\right]+{\mathbb E}_{z\sim p_{z}}\left[\log (1-D(G(z)))\right] $$  p_{data}は訓練データの分布で、 p_{z} zの分布である。( zの分布というのは、学習させる側が決めるもので与えられると考えて良い。)
この評価関数の意味は下図の通り。
( Dの値域が[0, 1]であることに注意すれば \logはどちらも [-\infty, 0]) f:id:doll_r0:20180619201229p:plain これは、 Dのみを見ると、Binary Cross Entropy(BCE) になっていて、 Dは2値分類を学習しているだけだということも分かる。
また、図から Dはこれを最大化しようとして、 Gはこれを最小化しようとしているということも分かる。つまり、 D Gも最適になった時、評価関数の値は、 $$ V^{*}(G, D) = \mathop{\min}_{G}\mathop{\max}_{D} V(D, G) $$ となる。  Dについて最大化するというのは定性的には現実のデータと生成されたデータをできるだけ見分けるようなものを学習しているということだが、具体的には何が学習されているのだろうか?
まず、 Vを最大化するような Dについて考えてみる。
データの確率空間を (X, \sigma(X), p_{data})とすると、 Gとは確率空間 (Z, \sigma(Z), p_{z})から確率空間 (X, \sigma(X), p_g)を引き起こすような確率変数であると考えられる。( p_gはここで初めて書いたが、 Gによって引き起こされる確率空間の確率測度のこと。日本語で上手く説明できないのでこれで許して)
これを用いて、 Vを変形すると、 $$ \begin{align} V(G, D) &= \int_{x\in X}\log D(x) p_{data}(x) dx+\int_{z\in Z} \log (1-D(G(z))) p_{z}(z) dz\\ &= \int_{x\in X}\left\{\log D(x)p_{data}(x) + \log (1-D(x)) p_g(x)\right\} dx \end{align} $$ ここで、a\log(x) + b\log(1-x)の形の最大値は x = \frac{a}{a+b}で与えられることを利用して、 V(G, D)を最大化する Dは、 $$ D(x) = \frac{p_{data}(x)}{p_{data}(x)+p_g(x)} $$ 上式から、 p_{data} = p_gとなるとき、 D(x)は常に0.5であることが分かる。実際、最適な Gに対して p_g = p_{data}となる。 ここからはそれを確かめる。
 Dに関して最大化した Vを $$C(G) := \mathop{\max}_{D}V(G, D)$$ と表し、この時の D D^{\ast}とすると、 $$ \begin{align} C(G) &= \int_{x\in X}\left\{\log D^{\ast}(x)p_{data}(x) + \log (1-D^{\ast}(x)) p_g(x)\right\} dx \\ &= \int_{x\in X}\log\left(\frac{p_{data}(x)}{p_{data}(x)+p_g(x)}\right) p_{data}(x) dx + \int_{x\in X}\log\left(\frac{p_g(x)}{p_{data}(x)+p_g(x)}\right) p_g(x) dx \\ &= \int_{x\in X}\log\left(\frac{p_{data}(x)}{(p_{data}(x)+p_g(x))/2}\right) p_{data}(x) dx + \int_{x\in X}\log\left(\frac{p_g(x)}{(p_{data}(x)+p_g(x))/2}\right) p_g(x) dx - log4 \end{align} $$ ここで -log4が(変形が正しいことは明らかだが)謎に取り出されているのは、最適な p_g p_g=p_{data}だろうという予想のもとそれを代入した時、 C = -\log4だからである。 そして、2つの積分がそれぞれカルバック・ライブラー・ダイバージェンスであることがわかるので、整理すると、 $$ C(G) = KL\left(p_{data}\left|\left|\frac{p_{data}+p_g}{2}\right.\right.\right) + KL\left(p_g\left|\left|\frac{p_{data}+p_g}{2}\right.\right.\right) - \log4 $$ また前半2つのKLダイバージェンスイェンセン・シャノン・ダイバージェンスを用いるとさらに綺麗にかけて、 $$ C(G) = 2\cdot JSD\left(\left.\left.p_{data}\right|\right| p_g \right) - log4 $$ となる。 ここで、JSDにすると嬉しいのは1つにまとまって綺麗なのと、KLダイバージェンスは満たしていない距離の公理をJSDは満たすからである。
この式から、 C(G)を最小とするのはJSDを0(最小)とする、 p_g = p_{data}であることが分かる。(距離なのだから同じだったら0)

以上で、上手く学習されていれば  Gの分布は現実のデータと同じになり、そのときの Dは一様に0.5であることが分かる。

実際に学習する際は、 p_{data}は与えられず、確率分布 p_{data}からサンプリングされた実現値である学習データ(有限)が与えられる。 また、 zに関しても p_zから有限個サンプリングされる。 そのため、1度の \max,  \min操作で最適解は与えられない。さらに、それぞれのサンプルが有限であるため、そのデータに対して完全に最適化すると過学習してしまうという問題もある。
これらの理由から、 \max,  \min操作はそれぞれその勾配方向に移動するというものに置き換えて、これを反復する。
また、学習初期で \log (1-D(G(z))) D(G(z))が0に近くなるため( Gの分布がぜんぜんデータの分布になってないから) その勾配は緩やかであり、学習がなかなか進まないことが分かる。そのため、 Gを更新する際はこの部分を \log (D(G(z)))とする。これにより、 \maxの部分が \minになる。 よって、 D Gも勾配降下を繰り返す。 イメージ的には以下のような感じ。
( Sutton先生のGeneralized Policy Iterationの図から思いついた。) f:id:doll_r0:20180619231855p:plain

実装

もう実装はしたので1ヶ月以内くらいには上げるつもり。

機械学習の歴史

WikipediaTimeline of machine learningというページに機械学習の歴史がまとめられた表があったので、あとから見返しやすいように全て日本語にしてみた。
日本語訳はガバガバかもしれないので心配な人は元ページを見てね。
ムムッってとこがあったらコメントで教えてほしいにゃ🐾

年表

1763 ベイズの定理のベース
トマス・ベイズ(Thomas Bayes)の著書, "An Essay towards solving a Problem in Doctorine of Chances"がベイズが死んだ2年後, 彼の友人により修正・編集され出版された.

1805 最小二乗
アドリアン=マリ・ルジャンドル(Adrien-Marie Legendre)が最小二乗(méthode des moindres carrés)について記述.

1812 ベイズの定理
ピエール=シモン・ラプラス(Pierre-Simon Laplace)がThéorie Analytique des Probabilitésを出版. その著書の中で, ベイズの研究を発展させ, ベイズの定理として知られる定理を示した.

1913 マルコフ連鎖
アンドレイ・マルコフ(Andrey Markov)が詩の分析に用いた手法について初めて記述する. この手法は現在マルコフ連鎖として知られているものである.

1950 Turing's Learning Machine(チューリングの学習機?)
アラン・チューリング(Alan Turing)が学習により人工的に知性を持つ, learning machine(学習機?)を提案する. チューリングの具体的な?提案は遺伝的アルゴリズムを予見した?.

1951 最初のニューラルネットワーク
マービン・ミンスキー(Marvin Minsky)とディーン・エドモンズ(Dean Edmonds)は最初のニューラルネットワークを作り, SNARCを学習させた.

1952 チェッカーを機械がプレイする
アーサー・サミュエル(Arthur Samuel)がIBMのポキプシー研究所の一員になり, 初めの機械学習プログラムに取り掛かり, チェッカーをプレイするプログラムを作成した.

1957 パーセプトロン
フランク・ローゼンブラット(Frank Rosenblatt)がコーネル航空技術研究所で働いている間にパーセプトロンを発明する. その発明はかなりの反響を呼び, メディアにより広く報道された.

1963 機械がTic-Tac-Toe(まるばつゲーム)をプレイする
ドナルド・ミッキー(Donald Michie)が強化学習(304個のマッチ箱とビーズで実装)によりまるばつゲームをプレイする機械を作った.

1967 最近傍
最近傍法が考案され, ベーシックなパターン認識の始まりとなった. このアルゴリズムは地図上での経路決定に用いられた.

1969 ニューラルネットワークの限界
マービン・ミンスキーシーモア・パパード(Seymour Papert)が共著書Perceptronを出版し, パーセプトロンニューラルネットワークの限界について述べた. この本が示したニューラルネットワークには根本的な限界があるという考えはニューラルネットワーク研究の障害であったと考えられている.

1970 自動微分(誤差逆伝播法)
セポ・リンナインマー(Seppo Linnainmaa)が個別に接続された入れ子状の微分可能関数のネットワークの自動微分の一般的な方法を発表する. これは現在の誤差逆伝播法と対応するが, まだそのように名付けられてはいなかった.

1972 TF-IDF
Karen Spärck Jonesがある単語が文書の集合中もしくはコーパス中でどの程度重要かを反映するための統計量TF-IDFを発表した. 電子書籍分野のテキストベースのリコメンダシステムは83%がTF-IDFを用いている.

1972 Stanford Cart
スタンフォード大学の学生が部屋を障害物を避けて案内するカート(小さな車?)を開発した.

1980 ネオコグニトロン
福島邦彦が人工ニューラルネットワークの一種である, ネオコグニトロンに関する研究を発表した. 後の畳込みニューラルネットワークはこれに着想を得ている.

1981 説明にもとづく学習
ジェラルド・デ・ヨング(Gerald DeJong)がデータを解析し, 従うことか出来て重要ではないデータを捨てられる一般的なルールを作る説明にもとづく学習を提案した.

1982 リカレント・ニューラルネットワーク
ジョン・ホップフィールド(John Hopfield)がリカレントニューラルネットワークの一種で, 連想メモリとして役立つ, ホップフィールドネットワークを広めた.

1985 NetTalk
テリー・セジノウスキー(Terry Sejnowski)が赤ちゃんと同じ方法で発音を学ぶプログラムを開発した.

1986 誤差逆伝播
デビッド・ラメルハート( David Rumelhart), ジェフリー・ヒントン(Geoff Hinton), ロナルド・J・ウィリアムス(Ronald J. Williams)が誤差逆伝播法のプロセスを説明した.

1989 強化学習
クリスト・ファーワトキンス(Christopher Watkins)がQ学習を開発したことにより, 強化学習の実用性がかなり上がった.

1989 PC上での機械学習の商業利用
Axcelis, Inc.がPC上で遺伝的アルゴリズムを商業利用した初めてのソフトウェアEvolverを発売.

1992 機械がバックギャモンをプレイする
ジェラルド・テザウロ(Gerald Tesauro)がTD学習を用いてバックギャモンをプレイする, TD-Gammonを開発. TD-Gammonは人間のトッププレイヤーには優らないか, 同程度の能力があった.

1995 ランダムフォレスト
ティン・カム・ホ(Tin Kam Ho)がランダムフォレストについて記述した論文を発表した.

1997 IBM Deep Blueがカスパロフに勝利
IBMのDeep Blueが当時のチェス世界チャンピオンに勝利した.

1997 LSTM
Sepp HochreiterとJürgen SchmidhuberがLong Short-TermMemory(LSTM)を用いたリカレントニューラルネットワークを発明し, リカレントニューラルネットワークの効率と実用性を大きく向上させた.

1998 MNIST データ
Yann LeCunのチームがアメリカ合衆国国勢調査局の局員とアメリカの高校生の手書き数字データセットである, MNISTデータベースを公開した. これ以降, MNISTデータは手書き文字認識のベンチマークとして使用される.

2002 機械学習ライブラリTorch
機械学習ライブラリであるTorchが初めて公開される.

2006 Netflix Prize
機械学習を用いて, Netflix独自のリコメンデーションソフトの精度をユーザーの映画に対する評価を予測する点において上回ることを目的とした, Netflix Prizeが開始する. この競争は2009年に決着した.

2009 ImageNet
データが現実世界を反映していないと機械学習アルゴリズムはうまく機能しない事に気づいたスタンフォード大学のFei-Fei Liにより考案された, 大規模画像データベースであるImageNetが作成された.ImageNetは21世紀のAIブームのきっかけとなった.

2010 Kaggleコンペティション
機械学習コンペティションのプラットフォームであるウェブサイトKaggleが立ち上げられる.

2011 ジョパディ!で人間に勝利
機械学習, 自然言語処理, 情報検索技術を組み合わせることでIBM Watsonがジョパディ!のチャンピオン2人に勝利した.

2012 YouTube上の猫を認識
アンドリュー・エン(Andrew Ng), ジェフ・ディーン(Jeff Dean)が率いるGoogle BrainチームがYouTube動画から抽出されたラベル付けされていない画像から学習により猫を認識したニューラルネットワークを作成した.

2014 顔認識における飛躍
Facebookの研究者がニューラルネットワークを用い, 97.35%の精度で顔を識別するシステムであるDeepFaceに関する研究を発表した. 97.35%というのはそれ以前のモデルと比べ, 27%以上の改善であり, 人間にも匹敵する精度だった.

2014 Sibyl
Googleの研究者がユーザー行動の予測とリコメンデーションの提供のためにGoogleで使われていた大規模並列機械学習のためのプロプライエタリなプラットフォームであるSibylに関する研究の詳細を述べた.

2016 囲碁で人間に勝利
GoogleのAlphaGoは機械学習と木探索を組み合わせて, ハンデ無しの人間のプロプレイヤーに勝利した初めてのコンピュータ囲碁プログラムとなった. 後にAlphaGo Zeroとして改良され, 2017年にAlphaZeroとしてチェス等の二人ゲームに一般化された.


参考文献とかはWikipediaの方を見てね(消えてたらあれだけど)