暗号学 二歩目

代数学

体論

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