十五：多层感知机与布尔函数

今天没有别的话，好好学习，多多转发！

本期内容是

【多层感知机与布尔函数】

场景描述

神经网络概念的诞生很大程度上受到了神经科学的启发。生物学研究表明，大脑皮层的感知与计算功能是通过分多层实现的，例如视觉图像，首先光信号进入大脑皮层的V1区，即初级视皮层，之后依次通过V2层，V4层，即纹外皮层，进入下颞叶参与物体识别。深度神经网络，除了其模拟人脑功能的多层结构，最大的优势在于能够以紧凑简洁的方式来表达比浅层网络更复杂的函数集合（这里的“简洁”可定义为隐层单元的数目与输入单元的数目呈多项式关系）我们的问题将从一个简单的例子引出，已知神经网络中每个节点都可以进行“逻辑与／或／非”的运算，如何构造一个多层感知机 (Multi-Layer Perceptron, MLP) 网络实现n个输入比特的奇偶校验码（任意布尔函数）？

问题描述

如何用多层感知机实现一个异或逻辑（仅考虑二元输入）？

如果只使用一个隐层，需要多少隐节点能够实现包含n元输入的任意布尔函数？

上面的问题中，由单隐层变为多隐层，需要多少节点？

合理配置后所需的最少网络层数是多少？

背景知识：数理逻辑、深度学习

解答与分析

1. 如何用多层感知机实现一个异或逻辑（仅考虑二元输入）？

如下图所示（可有其他解法）：

2. 如果只使用一个隐层，需要多少隐节点能够实现包含n元输入的任意布尔函数？

包含n元输入的任意布尔函数可以唯一表示为“析取范式 (Disjunctive Normal Form, DNF)”（由有限个简单合取式构成的析取式）的形式。先看一个简单的例子：

由于每个隐节点可以表示析取范式中的一个简单合取式，所以该函数可由包含六个隐节点的三层感知机实现，如下图：

我们可以使用卡诺图表示析取式，即用网格表示真值表，当输入的合取式值为1时，则填充相应的网格。卡诺图中相邻的填色区域可以进行规约，以达到化简布尔函数的目的，如下图所示，七个填色网格最终可规约为三个合取式，故该函数可由包含三个隐节点的三层感知机实现：

于是我们的问题可转化为，寻找“最大不可规约的”n元析取范式DNF，也等价于最大不可规约的卡诺图，直观上，我们只需间隔填充网格即可实现，其表示的布尔函数恰为n元输入的异或操作，如图：

因此，n元布尔函数的析取范式最多包含2(n-1)个合取式，对于单隐层的MLP，需要2(n-1)个隐节点可以实现。

3. 上面的问题中，由单隐层变为多隐层，构造一个n元异或函数需要多少节点？

考虑二元输入的情况，需要三个节点可完成一次异或操作；对于四元输入，包含三次异或操作，需要3×3＝9个节点即可完成；而对于六元输入，包含五次异或操作，需要3×5＝15个节点…依此类推，n元异或函数需要3(n－1)个节点（包括最终输出节点）。网络的构造方式可参考下图：

我们可以发现，多隐层结构可以将隐节点的数目从指数级O(2(n-1))直接减少至线性级O(3(n﹣1))！

4. 合理配置后所需的最少网络层数是多少？

根据二分思想，每层节点两两分组进行异或运算，需要两个隐层操作完成，故合理配置后需要的网络层数为2㏒2(N)。