オートエンコーダーによるクラスタリング

AutoEncoder(AE)は一般に砂時計の形をしたNNで,入力の次元よりも小さい次元に一旦情報を落とし込み(code),また元の次元の情報を再構成する.再構成された情報と元の入力の誤差によって学習を行うため,self-supervisedな学習と言われる.AEによる次元削減を利用してクラスタリングを行うことができる.もとのデータが高次元過ぎるとk-meansのような伝統的なクラスタリングアルゴリズムがうまく動かないので,低次元な空間に写してクラスタリングを行うのである.直感的には移した先の空間で従来のクラスタリングを行うのが簡単だが,アルゴリズムの途中でNNのパラメータを更新するアルゴリズムもある.今回はAEによるクラスタリングについての3本の論文を読む.
以下,データセットを\(\{x_1, ..., x_n\} = X \subset \mathbf{R}^{D_{X}}\)とし,AEによってそれぞれの元は\(\{z_1, ..., z_n\}=Z \subset \mathbf{R}^{D_{Z}}\)に写されるとし,その写像を\(\phi_W\)と書き,クラスターの数を\(K\)とする.

I. Unsupervised Deep Embedding for Clustering Analysis, 2016

1. parameter initialization

深いAEを学習させるため,すべての層を同時に学習させるのではなく,それぞれの層を取り出して隠れ層1のAEとして学習させ,あとで結合させる学習法をStacked AutoEncoder(SAE)という. この論文ではSAEによってfully connectedなAEを学習させて,\(\phi_W\)の初期値を決定している.
\(\{z_i\}_1^n = \{\phi_W(x_i)\}_1^n\)を得て,さらにk-meansで\(\{z_i\}\)のセントロイドの集合\(\{\mu_j\}_1^K\)を計算する.

2. optimization

(1) soft assignment

\(z_i\)がセントロイド\(\mu_j\)に属している確率\(q_{ij}\)をt分布によって以下のように計算する.(\(\alpha=1\)に統一)
\[q_{ij} = \frac{(1+\|z_i - \mu_j\|^2/\alpha)^{-\frac{\alpha + 1}{2}}}{\sum_{j'} (1+\|z_i - \mu_j'\|^2/\alpha)^{-\frac{\alpha + 1}{2}}}\]

(2) KL divergence minimization

auxiliary target distribution \(P\)を導入する. \(P\)は真の分布に近いと仮定されており,本アルゴリズムがやることはsoft assignmentと\(P\)を合致させることであって,そのために,soft assignment \(Q\)と\(P\)のKL divergenceを目的関数として最小化する:
\[L = D_{KL}(P||Q) = \sum_i \sum_j p_{ij} \log \frac{p_{ij}}{q_{ij}}\]
\(P\)の選び方は難しい問題で,論文内では
\[p_{ij} = \frac{q^2_{ij} / f_j}{\sum_{j'} q^2_{ij'} / f_j'}, \ f_j = \sum_i q_{ij}\text{ (soft cluster frequency)}\]
としている…
\[\frac{\partial L}{\partial z_i} = \frac{\alpha + 1}{\alpha} \sum_j \left(1 + \frac{\|z_i - \mu_j\|^2}{\alpha} \right)^{-1}\]
\[\frac{\partial L}{ \partial \mu_j } =-\frac{\alpha + 1}{\alpha} \sum_i \left(1 + \frac{\|z_i - \mu_j\|^2}{\alpha} \right)^{-1} \times (p_{ij}-q_{ij})(z_i-\mu_j)\]
が成立し,これをNNに渡してbackpropagationすることでNNをも同時に更新でき,新しい\(Z\)の点\(\{z_i\}\)とセントロイド\(\{\mu_j\}\)が計算できる. NNを更新しない場合.つまり\(\{\mu_j\}\)だけを更新する場合,NNを更新する場合よりも性能が下回る.
データ点のクラスター間の変動が,総データ数\(n\)の\(tol\) %を下回ったら計算を打ち切る.

II. Deep Clustering with Convolutional Autoencoders, 2017

Iの自然な拡張. AEをCovolutional AutoEncoderに変更し,空間的な情報をより活用できるとしている. Poolingではなくstrided convolutionによってencodeし,strided transposed convolutionによってdecodeしている.

また,I.ではdecoder部分は削除していたが,この論文では残し,objective functionにreconstruction lossを加えて,code部分が空間情報を再構成するための情報を保存するようにしているこれによって,単にAEをCAEに変えただけの場合よりも性能が向上している.

III Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization

(I, IIと揃えるため,auxiliary distributionをP, それに近づけていくモデル分布をQとする)
このアルゴリズムはモデルの分布\(Q\)に近く,事前分布を満足する\(P\)を推定(expectation step)してから,\(P\)に近づくようにモデル分布\(Q\)を更新する(maximization step).
\(\mathbf{R}^{d_Z}\)を\(\mathbf{R}^K\)に移す写像\(f_\theta\)を
\[f_\theta(z) = \frac{\exp(\theta^T_k z_i)}{\sum_{k'} \exp(\theta^T_{k'} z_i)}\]
と定める.このとき,\(x_i\)がクラスター\(j\)に属する確率を\(f_\theta(z_i)\)とする.つまり
\[q_{ij} = P(y_i = j| z_i, \theta) = \frac{\exp(\theta^T_k z_i)}{\sum_{j'} \exp(\theta_{j_i}^T z_i)}\]
である.ただし\(\theta = [\theta_1, ..., \theta_k] \in \mathbf{R}^{d_z \times K}, f_\theta: Z \rightarrow Y \subset \mathbf{R}^K\) .

\(f_\theta\)と\(\phi_W\)によってこのモデルの分布\(Q_{\theta, W}\)が決まる.auxiliary distribution Pを用意すると,KL divergenceは
\[D_{KL}(Q||P) = E_Q [\log Q(X)/P(X)] = \frac{1}{N} \sum_I^N \sum_j^K p_{ij} \log \frac{p_{ij}}{q_{ij}}\]
また,殆どのデータ点を一つのクラスターに入れてしまうような解を避けるため,regularization項を追加する.そのため,Pのラベルの頻度分布\(f_j = \frac{1}{N} \sum_i p_{ij}\)と,事前知識から得られるラベルの一様分布\(\mathbf{u}\)(ここでは一様分布)を定義して,
\[ \begin{aligned}L &= D_{KL}(P||Q) + D_{KL} (\mathbf{f} || \mathbf{u}) \\&=\frac{1}{N} \sum_{i}^N \sum_j^K \left[q_{ij} \log \frac{q_{ij}}{p_{ij}} + q_{ij} \log \frac{f_j}{u_j}\right] \end{aligned}\]
と目的関数を定める.\(L\)を最小化する\(P\)は
\[p_{ij} = \frac{q_{ij} / (\sum_{i'} q_{i'j})^{1/2}}{\sum_{j'} q_{ij'} / (\sum_{i'} q_{i'j'})^{1/2}}\]
さらに\(Q\)を更新するための目的関数は通常のクロスエントロピーと同じ
\[-\frac{1}{N} \sum_i \sum_j p_{ij} \log q_{ij}\]
で,backpropagationによってNNのパラメーターを更新できる.

DEPICT

decoderとパラメータを共有する2つのAEを用意し,片方(corrupted pathway)にはノイズをかけた画像,もう一方(clean pathway)にはクリーンな入力を与える. パラメータの更新はもっぱらclean pathwayで行う(更新の結果はcorrupted pathwayにも適用される). corrupted pathwayが\(Q\)を計算することでより頑強な分布\(Q\)を得られ,clean pathwayが\(P\)を計算し,パラメータ更新をすることでより精度の高いauxiliary distributionを得られるとしている.
NNの目的関数は\(l=0, ..L-1\)をAEの\(l\)層として
\[\frac{1}{N} \sum_i \sum_j p_{ij} \log \tilde{q_{ij}} + \frac{1}{N} \sum_i \sum_{l=0}^{L-1} \frac{1}{|z^l_i|} \|z^l_i - \hat{z}^l_i\|^2\]
とし,backpropagationによってパラメータを更新する.

IV 性能比較

accuracy/normalized mutual information	MNIST-FULL	USPS
DEC	0.844/0.816	0.702/0.693
DCEC	0.890/0.885	0.790/0.826
DEPICT	0.965/0.917	0.964/0.927

DCECはその論文から,DECとDEPICTはDEPICT

暗号学 二歩目

代数学

体論

Definition 2-1

集合\(\mathbf{R}\)と\(\mathbf{R}\)上の二項演算\(+, *\)(それぞれを加算,乗算という)があって、以下の条件を満たすとき\((\mathbf{R}, +, *)\)を環(Ring)という.

(1) \((\mathbf{R}, +)\) は可換群である. \(+\)についての単位元を\(0_\mathbf{R}\)と書く.
(2) \((\mathbf{R}, *)\)はモノイドである. i.e.

(1) \(*\) は結合法則を満たす
(2) \(*\)は\(\mathbf{R}\)に閉じている
(3) \(*\)の単位元が存在する

\((\mathbf{R}, *)\)の単位元を\(1_\mathbf{R}\)と書く.

(3) \((\mathbf{R}, +, *)\)は分配法則を満たす. i.e.

\[\begin{aligned}\forall a, b, c. (a + b) * c &= a *c + b* c\\ a *(b+c) &= a * b + a * c\end{aligned}\]

さらに,環\((\mathbf{R}, +, *)\)の乗算が\(0_\mathbf{R}\)以外のすべての元に逆元をもつときこれを体(field)といい,特に\(*\)が可換なとき可換体という.可換体を単に体といい,\(*\)が非可換なとき特に非可換体や斜体ということもある.(後者を採用する)

Examples

1. \(\mathbb{Q}\)や\(\mathbb{R}\)は通常の加算・乗算で体
2. \(\mathbf{R}\)上のn次の正方行列の集合\(M_n(\mathbb{R})\)は通常の加算・乗算で非可換環をなす.
   3. \(\mathbf{R}\)上のn次の可逆な行列\(GL_n (\mathbb{R})\)を一般線形(general linear)群,とくにdeterminant が1な行列の集合\(SL_n(\mathbb{R})\)を特殊線形(special linear)群といい,ともに通常の加算・乗算で斜体をなす.

Definition 2-2 素数体

\(p\):素数 について,\(\mathbb{F}_p = \{0, 1, ..., p-1\}\)に,演算を
加算: \((a, b) \mapsto a + b \mod p\)
乗算: \((a, b) \mapsto a \times b \mod p\)
と定義し,単に\((+, *)\)と書くことにすると、\((\mathbf{F}_p, +, *)\)は体である.(証明略)

第2回次世代脳型人工知能研究会 メモ

招待講演1 岡田真人先生

途中入場したのでよくわからない.

• sparseなモデルが重要と主張する.
• Data Driven Science
• DLは脳を模倣しているがまだまだ模倣しきれていない部分が有る
• 自分の言いたいことは海外の学者たちの発言をつなぎ合わせて言う
• ImPactのQNNはD-Waveに勝てる

応用統計学 vol.45 no.3
情報処理学会 vol.59 No.1 42-47

招待講演2 丸山宏先生

DLはパラメータが多い割に過学習しづらい

DLの応用例の紹介

1. ピッキング
2. 自動車の走らせ方(仮想サーキットでの強化学習)
3. 線画の着色

本質的な限界

1. 教師データと将来のデータの分布が同じでないと適用できない
2. 教師データに現れない稀な事象を近似できない(臨機応変な対応ができない)
3. 訓練データが現実の分布からi.i.d.に抽出したか証明できない

実用的な限界

1. 計算リソースが大量に必要 -> 精度の低い計算/ Reservoir Computing

技術者の不足について

60年台にもプログラマが不足して社会問題になったが、ソフトウェア工学の創始によってなんとかなった(のか？)。機械学習工学ともいうべき新たな工学が必要に成るのでは。

暗号学 1歩目

[TOC]

代数学

群論

Definition 1-1. 群

集合\(G\)と\(G\)の上の2項演算\(\phi\)(簡単のため\(\phi(g_1, g_2) = g_1 g_2\)とも書く)が以下を満たすとき,\((G, \phi)\)は群(group)であるという.
(0) \[\forall g_1, g_2 \in G, g_1 \cdot g_2 \in G\]
これは\(\phi\)が\(G\)上の二項演算であるという条件である.
(1) 結合法則(associative law)
\[\forall g_1, g_2, g_3 \in G, g_1(g_2g_3) = (g_1 g_2) g_3\]
(2) 単位元の存在
\[\exists e \in G \text{ s.t. } \forall g \in G g e = e g = g\]この\(e\)を\((G, \phi)\)の単位元(identity)という.
(3) 逆元の存在
\[\forall g \in G , \exists g^{-1} \text{ s.t. } g g^{-1} = g^{-1} g = e\]
この\(g^{-1}\)を\(g\)の逆元(inverse)という.

群\((G, \phi)\)について,演算\(\phi\)に混同の恐れがないときは単に\(G\)と書く.
群の要素数\(\# G = | G|\)を\(G\)の位数(order)とも呼ぶ.

Corollary 1-2.

\((G, \phi)\)の単位元はただひとつだけ存在する.
proof.
\(e, e'\)を\(G\)の単位元とすると,\(e = ee' = e'e = e'\)

Definition 1-3. 部分群

群\((G, \phi)\)があって,\(H \subset G\)が同じ演算によって群になるとき,すなわち\((H, \phi)\)が群であるとき,\((H, \phi)\)は\((G, \phi)\)の部分群(subgroup)であるという.

Definition 1-4. 同値関係

集合\(S\)とその上の関係\(\sim\)が以下の条件を満たすとき\(\sim\)を同値関係(equivalency)という.
(1) 反射律(reflexivility)
\[ \forall x \in \S x \sim x\]
(2) 対象律(symmetry)
\[x \sim y \Rightarrow y \sim x\]
(3) 推移律(transitivity)
\[x \sim y, y \sim z \Rightarrow x \sim z\]
\[\forall x \in S x \sim x\]

Definition 1-5. 同値関係による商

(1)集合\(C(x) = \{ y| y \in S, y \sim x\}\)を\(x\)の同値類(equivalence class)といい,同値類の集合\(\{C(x) | x \in S\}\)を\(S\)の\(\sim\)による商(quotient set)といい,\(S / \sim\)と書く.
(2)\(C \in S / \sim\)について,\(x = C \Leftrightarrow C = C(x)\)なる\(x\)を\(C\)の代表元という.
(3) \(R \subset S\)が\(S / \sim\)の代表元を一つづつ含むとき,\(S / \sim\)の完全代表系という.明らかに\(|R| = |S/\sim|\)である.

群\(G\)と部分群\(H\)があって,\(g_1, g_2 \in G\)が\(g_1^{-1} g_2 \in H\)をみたすとき,\(g_1 \sim g_2\)と書くことにすると,\(\sim\)は同値関係である(証明略).同値類\(C(g)\)を特に\(gH\)と書いて左剰余類(left coset)と呼ぶ. \(\{gH| g\in G\}\)はこの同値関係による商 \(G / \sim = \{gH| g \in G\}\) に等しく,特に\(G / H\)と書く.

Proposition 1-6

任意の\(g \in G\)に\(|gH| = |H|\)
proof.

\[\phi: H\ni h \mapsto gh \in gH\]
という写像を考え,全単射であることを示す. 全射なのは明らかで,
\(h_1, h_2 \in H\)について,\(gh_1 = gh_2\)ならば左から\(g^{-1}\)をかけて\(h_1 =h_2\)
よって示せた.

Theorem 1-7 (Lagrange)

\[|G/H| |H|= |G|\]
proof.

\(G/H\)の完全代表系を\(\{x_i\}\)とする. \(| \{x_i\}|=|G/H|\)(def. 1-5)であり,また\(|C(x_i)| = |gH| = |H|\)(prop.1-6)から,
\[|G| = \sum_{i} |C(x_i)| = \sum_i |H| = |G/H||H|\]

参考文献:
代数学1群論入門, 雪絵明彦, 日本評論社, 2010
代数入門―群と加群, 堀田良之, 裳華房, 1987

RLでトレード

Introduction to Learning to Trade with Reinforcement Learning

株価や為替は時系列データだからRNNを使って解析すると思っていたが,たしかにReinformcement Learningを利用することも出来るはず. RLには興味がなかったがそのうちやらなければ

Local Contrast Normalizationメモ

What is the Best Multi-Stage Architecture for Object Recognition?, Jarrett et al. 2009のLocal Contrast Normalizationについてのメモ

ネットワーク内部で同じlayerのfeature mapsにまたがって行うnormalization.
第\(i\)feature map,の\((j, k)\)成分\(x_{ijk}\)に対して\(w_{pq}\)​を\(\sum_{ipq}w_{pq}=1\)なるGaussian weightinig windowとして,
\[v_{ijk}=x_{ijk}- \sum_{ipq}w_{pq} \cdot x_{i,j+p,k+q}\]
おそらく上の\(\sum\)の添字は\(p, q\)だけでいいはず
(要素の値が全て同じであるような画像を与えられると\(v\)は負になってしまうのでやはり添字は\(p, q\)か?)¹
\[y_{ijk}=v_{ijk}/max(c, \sigma_{jk}), \]
ただし
\[\sigma_{jk} = \left( \sum_{ipq} w_{pq} \cdot v_{i, j+p, k+q}^2 \right)^{1/2} ,\ c = mean_{jk} (\sigma_{jk})\]

---

1. インテルのページでは,カーネルをチャンネル数で割っている. ↩

論文読み 2018, Towards Principled Design of Deep Convolutional Networks: Introducing SimpNet

Towards Principled Design of Deep Convolutional Networks: Introducing SimpNet, Hasanpour et al. githubでコードが公開されている Deep Learningのモデル設計についての論文. 著者の前の論文と同じく,モデルを設計する上でのいくつかの指針を示し,それに従って作ったモデルと他のモデルの性能を比較している.著者は軽い(パラメータの小さい,浅い)モデルで,他の重いモデルに匹敵する性能のモデルを目指し,SIMPNETを開発した.また,SAF-poolingという新しいプーリング層を導入し,汎化性能を向上させたと主張している.

モデル設計上の指針

A. Gradual Expansion with Minimum Allocation

小さなモデルから始めて,じょじょに広く,深いモデルにしていく.その際深さよりも広さを優先する.

B. Homogeneous Groups of Layers

畳み込み層,プーリング層,正規化 etc.のように層を積み上げていくと考えるのではなく,目的を持ったgroup(他の文献ではblockと呼ばれるものか？)をいくつか設計し,それらを積み重ねていく.同じgroupを複数回使っても良い.

C. Local Correlation Preservation

1x1のカーネルは特に入力に近いところでは避ける.また出力に近いところでfeature mapを急激に小さくするのではなく,層をいくつか設けて徐々に小さくする.

D. Maximum Information Utilization

プーリングそうを入力の近くに多く置きすぎないこと.Max poolingはtransition invarianceを与えるし,strideが2以上のconvolutionによるpoolingを上回るが,入力層の近くで(空間的に)大きなfeature mapを使うことは一般に有益である.

E. Maximum Performance Utilization

3x3のカーネルが計算速度とモデルとしての性能の両方を備えている

F. Balanced Distribution Scheme

ネットワークを大きくするときには,少数のレイヤーだけを大きくするのではなく,すべてのレイヤーをまんべんなく大きくする.

G. Rapid Prototyping In Isolation

ネットワークの構造自体を替える前に最適化のポリシー(learning rate, regularization method)を替えてみるべきだし,またそのときは2つ以上の要素を同時に替えるのではなく,一つづつ替えて実験する.

H. Dropout Utilization

dropoutの重要性を説いている.

I. Simple Adaptive Feature Composition Pooling

dropoutの前に置くmax-poolingをSimple Adaptive Feature Composition Pooling(SAF-Pooling)として導入する.poolingとdropoutの順番は実装によって違う¹²³が名前を付けたのは初めてなのか？ SAF-Poolingによって,dropoutの後のpoolingより高度な特徴を抽出できると考えている.

J. Final Regulation Stage

A-Iの指針は絶対ではない

SIMPNET

13層からなる単純なCNNで,convolutionには3x3のカーネルのみを使用している.10層のCNNから始めて,性能の向上が見られなく成るまで各層を広くしてゆき,それから層を増やすという手順で設計した.

SCはCaffeでいうscale layer(意味は知らない)で,ReLUとDropoutの操作のようだ. Max Poolingはコードを見ると直後にDropoutが置かれているのでつまりSAF-Poolingのこと.dropout率は0.25.

¹

---

1. Using convolutional neural nets to detect facial keypoints tutorial, December 17, 2014, danielnouri.org ↩︎ ↩︎

2. Max Pooling Dropout for Regularization of Convolutional Neural Networks, Wu and Gu, 2015 ↩︎

3. Fast, Simple Calcium Imaging Segmentation with Fully Convolutional Networks, Aleksander Klibisz, Derek Rose, Matthew Eicholtz, Jay Blundon, Stanislav Zakharenko, Jul 2017 ↩︎