#はじめに
この記事は論文"Expressive Number of Two or More Hidden Layer ReLU Neural Networks"の実装記事です。
#概略
活性化関数がReLU関数であり、入力がn次元、出力が1次元の中間層2層のニューラルネットワークを考える。中間ニューロン数が入力側から順にa1個、a2個であったとき、任意のa1a2個の入出力データに対し、それらのデータを誤差0で表現するようなニューラルネットワークのパラメータが存在する。ここでいう「入出力データを誤差0で表現する」とは、ニューラルネットワークに各入力データを与えると、それぞれ対応した出力データと等しい値を返すことを表している。
まとめると、**機械学習における訓練データがa1a2個以下のとき、学習の収束先が必ず存在する**ということです。(ただし収束先の存在性が言えるだけで、実際に学習が収束するとは限らない。)
例えば、出力1次元の訓練データが10,000個あったとき、中間ニューロン数が100個、100個の中間層2層のReLUニューラルネットワークで全てのデータが誤差0で表現できます。
この事実はデータの入力次元に依存しないので、入力次元はいくら大きくても大丈夫です。(出力が1次元でない場合は後述します。)
証明は元論文にあるので省略しますが、本記事では、実際にその収束先であるパラメータ１組を表示するプログラムを紹介します。まずは実行例をご覧ください。
#実行例
入力が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の証明と"表現可能なデータ数に基づいたニューラルネットワークの表現能力"の定理3の証明を参考にしました。具体的には、証明中に求めた連立方程式の1つの解を計算するようなプログラムなのですが、相互再帰な二変数漸化式が出てきたりとけっこう複雑なので、詳細が知りたい方は元論文をどうぞ。
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がデータ数であり、これは変更しないでください。
###与えるデータ
idata = randomidata(idim,idataRange) # input data must be unique
odata = randomodata(odataRange)
idataは入力データであり、idim×N行列でかつ同じ列ベクトルが存在しない状態、odataは出力データであり、N次元ベクトルである必要があります。
この例では乱数取得のためデータ範囲を制限していますが、実際にはどちらも制限する必要なく、任意の値でパラメータを計算できます。
###商演算
# 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個のデータを表現するようなパラメータ１組を出力するようなプログラムを解説しました。
このプログラムで出力されるパラメータは絶対値が非常に大きいように思えますが、どんな歪なデータに対しても表現するようなパラメータ計算式のため、このような結果になったと考えられます。しかし幸いなことに、与えられたデータを表現するパラメータには一般には一意性が成り立たたないため、データによってはもっと絶対値の小さいパラメータで表現できる可能性があります。