1700537921
1700537922
1
1700537923
1700537924
0
1700537925
1700537926
0
1700537927
1700537928
1
1700537929
1700537930
1
1700537931
1700537932
0
1700537933
1700537934
0
1700537935
1700537936
问题2 如果只使用一个隐层，需要多少隐节点能够实现包含n元输入的任意布尔函数？
1700537937
1700537938
难度：★★★☆☆
1700537939
1700537940
分析与解答
1700537941
1700537942
包含n元输入的任意布尔函数可以唯一表示为析取范式（Disjunctive Normal Form，DNF）（由有限个简单合取式构成的析取式）的形式。先看一个n=5的简单示例
1700537943
1700537944
1700537945
1700537946
1700537947
（9.2）
1700537948
1700537949
在式（9.2）中，最终的输出Y可以表示成由6个合取范式所组成的析取范式。该函数可由包含6个隐节点的3层感知机实现，如图9.2所示。
1700537950
1700537951
1700537952
1700537953
1700537954
图9.2 用多层感知机实现由6个合取范式组成的析取范式
1700537955
1700537956
1700537957
首先证明单个隐结点可以表示任意合取范式。考虑任意布尔变量假设Xi，若它在合取范式中出现的形式为正（Xi），则设权重为1；若出现的形式为非（i），则设权重为−1；若没有在合取范式中出现。设权重为0；并且偏置设为合区范式中变量的总数取负之后再加1。可以看出，当采用ReLU激活函数之后，当且仅当所有出现的布尔变量均满足条件时，该隐藏单元才会被激活（输出1），否则输出0，这与合取范式的定义的相符的。然后，令所有隐藏单元到输出层的参数为1，并设输出单元的偏置为0。这样，当且仅当所有的隐藏单元都未被激活时，才会输出0，否则都将输出一个正数，起到了析取的作用。
1700537958
1700537959
我们可以使用卡诺图表示析取式，即用网格表示真值表，当输入的合取式值为1时，则填充相应的网格。卡诺图中相邻的填色区域可以进行规约，以达到化简布尔函数的目的，如图9.3所示，由图可见，有W、X、Y、Z共4个布尔变量，WX的取值组合在纵轴显示，YZ的取值组合在横轴显示。7个填色网格最终可规约为3个合取式，故该函数可由包含3个隐节点的3层感知机实现：
1700537960
1700537961
1700537962
1700537963
1700537964
图9.3 用卡洛图表示析取范式
1700537965
1700537966
回顾初始问题：在最差情况下，需要多少个隐藏结点来表示包含n元输入的布尔函数呢？现在问题可以转化为：寻找“最大不可规约的”n元析取范式，也等价于最大不可规约的卡诺图。直观上，我们只需间隔填充网格即可实现，其表示的布尔函数恰为n元输入的异或操作，如图9.4所示。容易看出，在间隔填充的网格上反转任意网格的取值都会引起一次规约，因此，n元布尔函数的析取范式最多包含2(n−1)个不可规约的合取范式，对于单隐层的感知机，需要2(n−1)个隐节点实现。
1700537967
1700537968
1700537969
1700537970