暗号学 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 ↩︎

リストの和のリストのアルゴリズム

\(A=[a_1, a_2,a_3 ...]\)というリストあって,\(s_n = \sum_{i=1}^n a_i\)として,\(S=[s_1, s_2, s_3,...]\)というリストを新たに作りたいとする.うっかりしているとリスト内包表記を使えば早かろうと思って

def ls_comp_sum(A):
    length = len(A)
    return [sum(A[:i]) for i in range(length)]

と書いてしまったりするが,forループを使って,

def for_sum(A):
    result = [arr[0]]
    length = len(arr)
    for i in range(1, length):
        result.append(result[-1] + arr[i])
    return result

としたほうがずっと早い(Dynamic Programmingというらしい).

論文読み 2017, Data Distillation: Towards Omni-Supervised Learning

Data Distillation: Towards Omni-Supervised Learning, Radosavovic et al.

semi-supervised learningについての論文. ここでは正解データ(annotation)の付いた教師データを"ラベルありデータ",付いていない教師データを"ラベルなしデータ"と呼ぶことにする.
著者らは,ラベルありデータを最大限活用しながら,インターネット経由で得られるようなほとんど無尽蔵のラベルなしデータをも使って学習するモデルをomni-supervised learningと呼んでいる. 著者らは,ラベルありデータで学習してからラベルなしデータに推測を行い,その推測を仮のラベルとしてラベルなしデータについても学習を行うとしている.このとき,ラベルなしデータに対して様々なtransformation(回転,反転 など)を行った結果を統合した結果の推測をensemble(統合)したラベルを仮のラベルとすることで,Hinton et al.[^1] の提案した Model Distillationと似たことが行えると著者らは主張しており(fig.1),これをData Distillationと名付けた.

figure 1. 上:Hinton et al[^1] のモデル, 下: 著者らのモデル

こうしたモデルは古くからあるが,近年の教師あり学習モデルの性能向上によって現実的になってきたとしている.
著者らはMask R-CNNを,リスケーリングと左右反転をtransformationとして,Data Distillation を使って学習させ,keypoint detectionとobject detectionで,supervised learningよりも良い結果を得た

deformable convolutionを試す

Dai, Jifeng, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei. 2017. “Deformable Convolutional Networks.”のpytorch実装を試した.
条件は付属のcifar10に対するテスト(torch_deform_conv/cnn.pyとtests/test_deform_conv.py)にdropoutを加える以外はそのまま流用し,通常のconvolutionとdeformable convolutionを比較した.

結果

dropout率0.5の場合.

training lossはnegative log likelihood. deformable convolutionのtraining errorは通常のconvolutionの場合よりも低くなる一方で,generalization errorはわずかに収束が早まるだけのようだ.

dropout = 0.0, 0.25, 0.50(それぞれ緑,黄色,赤)のときのgeneralization error. Early stoppingすれば差はない.cifar-10では対象物が画像の中央に大きく写っているので,deformable convolutionの効果が薄いのかもしれない.
convolution 4, fully-connected 1の単純なモデルだが,deformable convolutionの場合,100 epochを回すのに5時間以上かかった. この実装は実用に耐えないようだ.
こちらの実装はcudaを使っているので速そう.そのうち試したい.