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
1700537971
图9.4 多元异或运算
1700537972
1700537973
问题3 考虑多隐层的情况，实现包含n元输入的任意布尔函数最少需要多少个网络节点和网络层？
1700537974
1700537975
难度：★★★☆☆
1700537976
1700537977
分析与解答
1700537978
1700537979
参考问题1的解答，考虑二元输入的情况，需要3个结点可以完成一次异或操作，其中隐藏层由两个节点构成，输出层需要一个结点，用来输出异或的结果并作为下一个结点的输入。对于四元输入，包含三次异或操作，需要3×3=9个节点即可完成。图9.5展示了一种可能的网络结构。输入W、X、Y、Z 4个布尔变量；首先用3个结点计算W⊕X；然后再加入3个节点，将W⊕X的输出与Y进行异或，得到W⊕X⊕Y；最后与Z进行异或，整个网络总共需要9个结点。而六元输入包含五次异或操作，因此需要3×5=15个节点，网络的构造方式可参考图9.6所示。依此类推，n元异或函数需要包括3(n−1)个节点（包括最终输出节点）。可以发现，多隐层结构可以将隐节点的数目从指数级O(2(n−1))直接减少至线性级O(3(n−1))！
1700537980
1700537981
1700537982
1700537983
1700537984
图9.5 实现四元异或运算的一种网络结构样例
1700537985
1700537986
在上面所举的例子中，n元异或所需的3(n−1)个结点可以对应2(n−1)个网络层（包括隐含层和输出层），实际上，层数可以进一步减小。考虑到四元的输入W、X、Y、Z；如果我们在同一层中计算W⊕X和Y⊕Z，再将二者的输出进行异或，就可以将层数从6降到4。根据二分思想，每层节点两两分组进行异或运算，需要的最少网络层数为2log2N（向上取整）。
1700537987
1700537988
1700537989
1700537990
1700537991
图9.6 实现六元异或运算的一种网络结构样例
1700537992
1700537993
1700537994
1700537995
1700537996
百面机器学习：算法工程师带你去面试 [:1700532221]
1700537997
百面机器学习：算法工程师带你去面试 深度神经网络中的激活函数
1700537998
1700537999