中間ニューロン数a1, a2個の3層のReLUニューラルネットワークで任意のa1*a2個のデータが誤差0で表現できてしまう話とその実装

#はじめに
この記事は論文["Expressive Number of Two or More Hidden Layer ReLU Neural Networks"](https://ieeexplore.ieee.org/document/8951658)の実装記事です。

#概略
活性化関数がReLU関数であり、入力がn次元、出力が1次元の中間層2層のニューラルネットワークを考える。中間ニューロン数が入力側から順にa1個、a2個であったとき、任意のa1*a2個の入出力データに対し、それらのデータを誤差0で表現するようなニューラルネットワークのパラメータが存在する。ここでいう「入出力データを誤差0で表現する」とは、ニューラルネットワークに各入力データを与えると、それぞれ対応した出力データと等しい値を返すことを表している。
まとめると、**機械学習における訓練データがa1*a2個以下のとき、学習の収束先が必ず存在する**ということです。(ただし収束先の存在性が言えるだけで、実際に学習が収束するとは限らない。)
例えば、出力1次元の訓練データが10,000個あったとき、中間ニューロン数が100個、100個の中間層2層のReLUニューラルネットワークで全てのデータが誤差0で表現できます。
この事実はデータの入力次元に依存しないので、入力次元はいくら大きくても大丈夫です。(出力が1次元でない場合は後述します。)
証明は[元論文](https://ieeexplore.ieee.org/document/8951658)にあるので省略しますが、本記事では、実際にその収束先であるパラメータ１組を表示するプログラムを紹介します。まずは実行例をご覧ください。

#実行例
入力が5次元、中間ニューロン数が入力側から順に3個、3個、出力が1次元のReLUニューラルネットワークで、3*3=9個のデータを表現するパラメータを出力する例です。

```
$python3 NNH2.py

( 5 , 3 , 3 , 1 ) ReLU neural network

the number of data = 9

 input =
[[93 59 58 20 80 57 35 21 38]
 [ 4 91 47 69 98 85 68  2 15]
 [14 60 31 86 37 12 23 69 42]
 [ 4 14 52 98 72 60 67 51 90]
 [27 12  6 32 76 63 49 41 28]]
output =
[ 1 81 17 65 25 33 45 77 10]


parameters

1st layer
W1 =
[[Fraction(823849691, 1) Fraction(4336051, 1) Fraction(28907, 1)
  Fraction(149, 1) Fraction(1, 1)]
 [Fraction(823849691, 1) Fraction(4336051, 1) Fraction(28907, 1)
  Fraction(149, 1) Fraction(1, 1)]
 [Fraction(823849691, 1) Fraction(4336051, 1) Fraction(28907, 1)
  Fraction(149, 1) Fraction(1, 1)]]
b1 =
[[Fraction(-16778681974, 1)]
 [Fraction(-60502822101, 2)]
 [Fraction(-48495714637, 1)]]

2nd layer
W2 =
[[Fraction(148, 1) Fraction(-9237952317912, 35473138591)
  Fraction(4049615396998340012232, 18010928872046123981)]
 [Fraction(15800556778618364518367199397870934943209115691793, 1077111270972508432064314372084032376028236629)
  Fraction(-11216317162890245084133171070123933902029519034081603343913003835232890, 434989745706342223538442515057047029191074444247675999926788518821)
  Fraction(2686834406446276617746833568279126654074919365089537293846487174104542, 224870468718735937295513181927691380500164378143178284849730556247)]
 [Fraction(843610077776665412761527367413211990104912799146270139270113712675305808525969059554219936165800, 154068217051841137536218687813904006692418581384372306328955832146429671252437697)
  Fraction(-57625119985396507975392986118005960657818304694554844951150042194684795633743261029837087833785575305876950, 5262027877233168541064334417747189692030849998640803800770876843784630220816492104662661549)
  Fraction(100319159657643248312549073786161213853603634088990731217920689495343417295177190966187025547162361565044553868359914, 11390289225651438251169009216834446835092039706616191741035899343815780751119047453235035761689895223)]]
b2 =
[[Fraction(-99, 1)]
 [Fraction(-31282288621675736677206673372946695670689268182842, 4042938352270697695885621047346217759)]
 [Fraction(-912723226773529956403403228639959057460803178243124784475781762180477870767754518136094, 13495462068042154164632946308945540668991317744154109409049607)]]

3rd layer
W3 =
[[ 1 -1  1]]
b3 =
[[16]]


check

MP(x) = [Fraction(1, 1), Fraction(81, 1), Fraction(17, 1), Fraction(65, 1), Fraction(25, 1), Fraction(33, 1), Fraction(45, 1), Fraction(77, 1), Fraction(10, 1)]
output= [ 1 81 17 65 25 33 45 77 10]

MP(x) - output = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
```

順に解説していくと、
まず任意の3*3=9個の入出力データが表現できるので、データを以下のように与えます。

```
input =
[[93 59 58 20 80 57 35 21 38]
 [ 4 91 47 69 98 85 68  2 15]
 [14 60 31 86 37 12 23 69 42]
 [ 4 14 52 98 72 60 67 51 90]
 [27 12  6 32 76 63 49 41 28]]
output =
[ 1 81 17 65 25 33 45 77 10]
```

これは入力`[[93] [4] [14] [4] [27]]`に対応する出力が`[1]`であるようなデータを意味しており、そのような入出力データが9個並んでいます。この例では乱数でデータを与えましたが、具体的なデータを与えることもできます。
与えられたデータに対し、それらを表現するニューラルネットワークのパラメータである各層の重み値とバイアス値は、それぞれ1層目`W1`、`b1`、2層目`W2`、`b2`、3層目`W3`、`b3`として出力されます。(`Fraction(n,m)`とは有理数$\frac{n}{m}$を表す。)

```
1st layer
W1 =
[[Fraction(823849691, 1) Fraction(4336051, 1) Fraction(28907, 1)
  Fraction(149, 1) Fraction(1, 1)]
 [Fraction(823849691, 1) Fraction(4336051, 1) Fraction(28907, 1)
  Fraction(149, 1) Fraction(1, 1)]
 [Fraction(823849691, 1) Fraction(4336051, 1) Fraction(28907, 1)
  Fraction(149, 1) Fraction(1, 1)]]
b1 =
[[Fraction(-16778681974, 1)]
 [Fraction(-60502822101, 2)]
 [Fraction(-48495714637, 1)]]
...
```

パラメータの分母分子は非常に大きい値が計算されますが、9個の各入力に対するニューラルネットワークの出力はキレイに割り切れて、それぞれ

```
MP(x) = [Fraction(1, 1), Fraction(81, 1), Fraction(17, 1), Fraction(65, 1), Fraction(25, 1), Fraction(33, 1), Fraction(45, 1), Fraction(77, 1), Fraction(10, 1)]
```

となります。実際に元データの出力との誤差を比較すると、

```
MP(x) - output = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
```

となり、誤差0となることがわかります。(見やすさのため`float`型に変換しています。) 
この結果は入出力データや入力次元、中間ニューロン数に依存せず、任意の値で誤差が0になるはずです。

#実装
アルゴリズムは元論文のTeorem 3の証明と["表現可能なデータ数に基づいたニューラルネットワークの表現能力"](https://search.ieice.org/bin/index.php?category=D&lang=J&vol=J102-D&num=6&abst=)の定理3の証明を参考にしました。具体的には、証明中に求めた連立方程式の1つの解を計算するようなプログラムなのですが、相互再帰な二変数漸化式が出てきたりとけっこう複雑なので、詳細が知りたい方は[元論文](https://ieeexplore.ieee.org/document/8951658
)をどうぞ。
Pythonによる実装コードは[こちら](https://github.com/nekonistyle/Python)

##変更可能なパラメータ

###ニューロン数

```python:
# constants
idim = 5 # the number of input neurons
a1 = 3 # the number of 1st hidden neurons
a2 = 3 # the number of 2nd hidden neurons

N = a1 * a2 # the number of data (do not change)
```

`idim`が入力次元、`a1`、`a2`がそれぞれ1層目、2層目の中間ニューロン数です。
`N = a1 * a2`がデータ数であり、これは変更しないでください。

###与えるデータ

```python
idata = randomidata(idim,idataRange) # input data must be unique
odata = randomodata(odataRange)
```

`idata`は入力データであり、`idim`×`N`行列でかつ同じ列ベクトルが存在しない状態、`odata`は出力データであり、`N`次元ベクトルである必要があります。
この例では乱数取得のためデータ範囲を制限していますが、実際にはどちらも制限する必要なく、任意の値でパラメータを計算できます。

###商演算

```python
# select division operator ('Fraction' or '/')
divop = fractions.Fraction
# divop = lambda x,y: x / y
```
パラメータを計算するのに四則演算しか使わないので、商演算`divop`は有理数演算`Fraction`で定義していますが、不動小数点数の演算`/`に変更することが可能です。しかし非常に大きい数で割ることがあり、`/`だと誤差が大きくなる可能性があるため注意が必要です。

#出力がm次元の場合
元論文のTheorem 4より、出力がm次元の場合は$a_1(a_2 \operatorname{div} m) + a_2 \operatorname{mod} m$個のデータが表現できます。(実装はしていませんが出力が1次元の時のパラメータを流用すれば同じように作れます。)
すなわち2層目の中間ニューロンを出力次元の倍数にすれば
[訓練データ数]×[出力次元] ≦ [1層目の中間ニューロン数]×[2層目の中間ニューロン数]
を満たしていれば表現できるので、例えば訓練データ10,000個、出力が10次元であれば、中間ニューロン数400個、250個のニューラルネットワークで全てのデータが表現できます。

#まとめ
中間ニューロン数がa1、a2個である中間層2層のReLUニューラルネットワークにおいて、与えられたa1*a2個のデータを表現するようなパラメータ１組を出力するようなプログラムを解説しました。
このプログラムで出力されるパラメータは絶対値が非常に大きいように思えますが、どんな歪なデータに対しても表現するようなパラメータ計算式のため、このような結果になったと考えられます。しかし幸いなことに、与えられたデータを表現するパラメータには一般には一意性が成り立たたないため、データによってはもっと絶対値の小さいパラメータで表現できる可能性があります。