パーセプトロン（書籍）

パーセプトロンを とし、各サポート サイズが最大 であるとします。これを、各サイズが最大 であるマスクの線形和に変換します。 ${\textstyle \theta \left(\sum _{i}a_{i}\psi _{i}\right)}$${\textstyle \psi _{i}}$${\textstyle k}$${\textstyle k}$

が集合 上でサポートされているとします。 を返すの各サブセットごとに 1 つの節を持つ選言標準形でこれを記述し、各サブセットについて、サブセット内の各要素ごとに 1 つの正のリテラルを記述し、それ以外の場合は 1 つの負のリテラルを記述します。 ${\textstyle \psi _{i}}$${\textstyle A}$${\textstyle A}$${\textstyle \psi _{i}}$${\textstyle 1}$

例えば、が でサポートされ、 がすべての奇数サイズの部分集合上でサポートされるとすると、次のように書くことができます。${\textstyle \psi _{i}}$${\textstyle \{1,2\}}$${\textstyle 1}$$${\displaystyle (x_{1}\land \neg x_{2})\lor (\neg x_{1}\land x_{2})}$$

さて、この式をブール代数式に変換し、展開してマスクの線形和を求めます。例えば、上記の式は次のように変換されます。$${\displaystyle x_{1}(1-x_{2})+(1-x_{1})x_{2}=x_{1}+x_{2}-2x_{1}x_{2}}$$

パーセプトロンで使用される述語ごとにこれを繰り返し、合計すると、マスクのみを使用した同等のパーセプトロンが得られます。

証明のアイデアは、 のすべての要素の平均を取ることです。 ${\textstyle G}$

内の述語をとして列挙し、任意の に対してとなる述語のインデックスを と書きます。つまり、集合 に対するグループアクションを定義したことになります。 ${\textstyle \Phi }$${\textstyle \psi _{1},\psi _{2},...}$${\textstyle g(j)}$${\textstyle \psi _{g(j)}=\psi _{j}\circ g}$${\textstyle g\in G}$${\textstyle \Phi }$

を定義します。これが目的のパーセプトロンであると主張します。 ${\textstyle a_{j}:=\sum _{g\in G}b_{g^{-1}(j)}}$

なので、次のような実数が存在する。${\textstyle \psi \in L(\Phi )}$${\textstyle b_{j}}$$${\displaystyle \theta \left(\sum _{j}b_{j}\psi _{j}\right)=\psi }$$

-不変性の定義により、 であれば、すべての に対して となる。つまり、であり、したがって のすべての要素の平均をとると、${\textstyle G}$${\textstyle \psi (A)=1}$${\textstyle \psi (g(A))=1}$${\textstyle g\in G}$$${\displaystyle \sum _{j}b_{j}(\psi _{j}\circ g)(A)>0;\quad g\in G}$$${\textstyle G}$$${\displaystyle 0<\sum _{g\in G}\sum _{j}b_{j}(\psi _{j}\circ g)(A)=\sum _{g\in G}\sum _{j}b_{g^{-1}(j)}\psi _{j}(A)=\sum _{j}\left(\sum _{g\in G}b_{g^{-1}(j)}\right)\psi _{j}(A)=\sum _{j}a_{j}\psi _{j}(A)}$$

の場合も同様です。 ${\textstyle \psi (A)=0}$

をパリティ関数とし、をサイズのすべてのマスクの集合とします。明らかに、 と はいずれもすべての順列に対して不変です。 ${\textstyle \psi _{parity}}$${\textstyle \Phi }$${\textstyle \leq |R|-1}$${\textstyle \psi _{parity}}$${\textstyle \Phi }$

が の位数を持つと仮定すると、正の正規形定理により、 となります。 ${\textstyle \psi _{parity}}$${\textstyle \leq |R|-1}$${\textstyle \psi _{parity}\in L(\Phi )}$

群不変性定理により、 がマスク の同値類のみに依存し、したがって がマスク のサイズ のみに依存するようなパーセプトロンが存在します。つまり、が上のマスクである場合、となる実数 が存在します。 $${\displaystyle \theta \left(\sum _{i}a_{i}\psi _{i}\right)=\psi _{parity}}$$${\textstyle a_{i}}$${\textstyle S_{R}}$${\textstyle \psi _{i}}$${\textstyle \psi _{i}}$${\textstyle b_{0},b_{1},...,b_{|R|-1}}$${\textstyle \psi _{i}}$${\textstyle A}$${\textstyle a_{i}=b_{|A|}}$

これで、任意のサブセット上のパーセプトロンを明示的に計算できるようになりました。 ${\textstyle X\subset R}$

にはサイズ のサブセットが含まれているため、パーセプトロンの式を代入して計算します。${\textstyle X}$${\textstyle {\binom {|X|}{k}}}$${\textstyle k}$$${\displaystyle \psi _{parity}(X)=\theta \left(\sum _{k=0}^{|R|-1}b_{k}{\binom {|X|}{k}}\right)}$$

ここで、 の多項式関数を定義します。この関数は最大次数を持ちます。すると、 の各 に対して となるので、小さい正の に対して次が成り立ちます。 $${\displaystyle p(x):=\sum _{k=0}^{|R|-1}b_{k}{\binom {x}{k}}}$$${\textstyle {\binom {x}{k}}={\frac {x(x-1)\cdots (x-k+1)}{k!}}}$${\textstyle |R|-1}$${\textstyle \theta (p(|X|))=\psi _{parity}(X)}$${\textstyle |X|=0,1,2,...,|R|}$$${\displaystyle p(0)-\epsilon >0,\quad p(1)-\epsilon <0,\quad p(2)-\epsilon >0,\quad \cdots }$$${\textstyle \epsilon }$

したがって、次数多項式には少なくとも各 に 1 つの異なる根があり、矛盾が生じます。 ${\textstyle \leq |R|-1}$${\textstyle p-\epsilon }$${\textstyle |R|}$${\textstyle (0,1),(1,2),...,(|R|-1,|R|)}$