九州大学大学院 情報学専攻特別講義 （８） ニューラルネットワークの 離散モデル 九州大学大学院　情報学専攻特別講義 （８） ニューラルネットワークの 離散モデル 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義内容 バイオインフォマティクス概論（資料なし） 配列アラインメント 配列解析 RNA二次構造予測 タンパク質立体構造の比較と予測 固定パラメータアルゴリズムと部分k木 グラフの比較と列挙 ニューラルネットワークの離散モデル ブーリアンネットワークの解析と制御 講義の進展状況によっては内容に変更の可能性あり

しきい値関数

閾値関数（１） X1 X2 X3 Y W2 W1 W3 W1×X1 + W2×X2 + W3×X3 ≧ Θ ➡ Y=1 ニューロン（神経細胞）のモデルの一つ 興奮状態＝１、それ以外＝０ 入力の線形和が閾値以上なら１、未満なら０ X1 X2 X3 Y W1 W2 W3 W1×X1 + W2×X2 + W3×X3 ≧ Θ　➡　Y=1 W1×X1 + W2×X2 + W3×X3 < Θ　➡　Y=0

閾値関数（２） X1 X2 X3 Y ２ １ Θ=3 1 ２ １ 2×1 + 1×0 + 1×1 ≧ 3 1 ２ １ 2×0 + 1×1 + 1×1 < 3

決定リスト

決定リスト（decision list） 決定リスト： 決定木（decision tree）で木をリストに限定 <(f1,c1),(f2,c2),…,(fL,cL) > という形式で表現 fi は入力変数から 0,1 を返す関数、ci∊{0,1} 左から順に fi を計算し、fi=1 となったら ci を出力して終了 すべて fi=0 なら 0 を出力 1-決定リスト:　fi は、リテラルか1 OR: AND:

決定リスト と 閾値関数 定理： 1-決定リストは閾値関数 証明： リストの要素数に関する帰納法 １個の時： 明らか （例： ） １個の時：　明らか　（例：　　　　　　　　　　　　　　　　　　　） L個の時（L>1）： リストを　　　　　　　　　　　　　　　　とする。帰納法の仮定より 　　　　　　　　　　　　　　　　と等価な　　　　　　　　　が存在 　　　に応じて閾値関数 　　　　　　　　　　 を以下のように定義 ただし、 （一般性を失うことなく）ℓ1はx1かその否定、かつ、 i 説明

しきい値関数の個数

閾値関数の個数 n変数ブール関数の個数： 個 Tn = n変数閾値関数の集合 が成立 n変数への 0,1 割り当ては 2n 通り それぞれについて 0/1 を選択可 Tn = n変数閾値関数の集合 　　　　　　　　　　　　が成立 (ここでは、下限は 2n(n-1)/2 のみを証明） ⇒ 閾値関数はブール関数全体より、はるかに少ない AND/OR関数より、はるかに多い x1 x2 x3 f 0/1 1

上限の導出（１） C(N,d): d次元ユークリッド空間において原点を通るN個の超平面により分割される領域の最大数 定理： 証明（帰納法）：　N=1の時、明らかに C(1,d)=2． N>1の時：　N-1個の超平面による分割に、超平面 H を追加 ⇒ H自体はd-1次元 ⇒ H上の分割数は C(N-1,d-1) ⇒

上限の導出（２） 定理： 証明：{0,1}nの要素を u1,…,uN (N=2n)とし、ui’=(ui,-1)とする w1’=(w1,θ1)とw2’=(w2,θ2)が同じブール関数に対応 ⇔ w1’・ui’ と w2’・ui’ の符号が全ての ui’ で一致 よって、異なる閾値関数の個数は、 n+1次元の2n 個の超平面w’・ui’ =0 （w’ がn+1次元上の点に対応）で分割される領域の個数以下　⇒ ここで、d≦mの時、以下が成立 よって、n>3の場合、以下が成立　（n=1,2,3の時もOK）

下限の導出（１） 定理： 略証（帰納法）： n=1の時、明らかに成立． w1,…,wn-1に対して |Tn-1|個が存在。これに wn を追加してどう増えるかを考える（なお、閾値θは常に同じ値） {0,1}n-1 の要素を以下により並び替えたものを x(i) とする wn = -w・x(i)+Δ+θ (i=0,…,2n-1)（Δは小さな正定数）とおくことにより、異なる2n-1+1個の関数を得る。xn=0 の時はもとと同じ、xn=1の時が違う ので よって、

下限の導出（２） 補足： wn を下図右のように変化させることにより、新たに2n-1+1個の異なる関数を得る

しきい値ネットワーク

DNFと閾値ネットワーク DNF（Disjunctive Normal Form, 論理和標準形) ブール関数を[リテラルのAND]のORで表現 任意のブール関数はDNFで表現可能 例１:　 閾値ネットワーク：　各頂点（素子）が閾値関数 本講義ではループのない階層型ネットワークのみを対象 定理：任意のブール関数は１層の中間層を持つ素子数2n+1個のネットワークで表現可能 証明：ANDを中間層、ORを出力層として、各関数を閾値関数で表現 例１に対応する 閾値ネットワーク

閾値ネットワークの素子数の下限 （ブール関数に対する）万能ネットワーク（universal network） 定理：万能ネットワークの素子数は 証明：di を i 番目の素子の入次数（入力の個数）とする。 以前の結果より、この素子が表現できるブール関数の個数は よって、N素子のネットワークが表現できるブール関数の個数は 一方、　　　　　　　　　より　　　　　　　　　．よって、 定理：中間層が１層の万能ネットワークの素子数は 証明: 　　　　　　　　　　　　　　　　　　　　　　　　が成立するので、 　　　　　　　　　　　より、

パリティ関数に対する素子数の下限（１） パリティ関数 PARITYn： x1,…,xn のうち、1となる 　　変数の個数が奇数個の時に1（偶数個の時は0） 　　となる関数 定理：中間層が１層、かつ、入出力層間を結ぶ辺が ないネットワークにおいて、パリティ関数計算のため の素子数は 証明：　Cnを n次元hypercube とする （{0,1}n の各要素を頂点とし、ハミング距離が1の 頂点間に辺があるグラフ） Cnにおいては辺を通過するたびに PARITYnの値が変化 どの辺も、どれかの閾値関数（に対応 する超平面）と交差することが必要 x1 x2 x3 f 1

パリティ関数に対する素子数の下限（２） 証明（つづき） （簡単のため n は偶数とする） 閾値関数(w,θ）において、一般性を失うことなく wi > 0 とする すると、1となる座標数が n/2 の頂点と n/2-1 の頂点を結ぶ辺すべてと超平面が交差する場合が交差数最大となる（証明略） その場合、交差する辺の個数は Cnには全部で　　　　　本の辺があるので、中間層の素子数をN個とすると　　　　　　　　　　　　　よって、 なお、スターリンの公式　　　　　　　　　　　より、以下を利用

結論

まとめ 閾値関数が表現できるブール関数： 個程度 任意の n変数ブール関数を表現するための素子数 閾値関数が表現できるブール関数：　　　　個程度 決定リストを含むが、ブール関数全体（　　　）よりはかなり狭い 任意の n変数ブール関数を表現するための素子数 上限は 2n+1, 下限は パリティ関数を表現する深さ２のネットワークの素子数： 補足 第８回の内容は以下の本に基づく M. Anthony: Discrete Mathematics of Neural Networks – Selected Topics, SIAM, 2001 第８回の内容は古典的な結果が多いが、その後の大幅な改善は少ないと思われる しかし活発な研究が続いており、様々な進展がある（e.g., [Kane & Williams, STOC 2016]）