《感知机：计算几何导论》中的奇偶校验与异或的关系

在人工智能领域的经典著作《感知机：计算几何导论》中，作者通过一个单纯的感知机无法解决异或问题，由此提出奇偶校验的例子作为示范。本文将首先证明感知机无法处理异或问题，接着证明奇偶校验与异或是等价的，最后提出解决方法。

1.感知机无法处理异或问题

在前一篇文章中，通过联通问题的例子，可以知道无法通过找到一个阈值来对四个点进行划分：

可以发现θ5作为信号强度的阈值，无法通过上下移动将四个信号强度进行正确的划分。

感知机实际上就是在找一个超平面对空间中的点进行划分：

可以发现，无论如何绘制这条直线，都无法对四个点进行划分。

以下是更严格的证明。实际上，在上一篇文章中采用的就是这样的证明方法：

通过矛盾，从而证明无法找到一组这样的参数。如此一来，就证明了感知机无法处理异或问题。

2.奇偶校验与异或

奇偶校验是指一串由0和1构成的数组中，如果1的个数为奇数，则输出1，如果为偶数，则输出0，只需要证明对数组当中的元素使用异或运算会得到同样的结果。

异或运算满足交换律和结合律，那么就可以将数组中的元素调整为一边都是1，另一边都是0，最终的结果是看都是1的那一边，因为不论是1还是0，当其与0做异或，最终的结果取决于其是什么，与0没有关系。

接着，使用结合律将1两两为一组进行异或，计算结果都为0，如果1为奇数个，那么最终必然会有一个1剩下，那么这个数组当中将只存在一个1，其他都为0，输出结果就为1，同理，如果1为偶数个，那么数组当中的元素全部为0，最终输出就是0。

这与奇偶校验的结果是一致的，以下举了一个具体的例子：

3.二阶项与两层感知机

或、与、与非，三种运算对应的公式与感知机的关系：

书中提到，引入二阶项，可以使感知机能处理异或。

异或可以用与或非来表达：

这里的x1·x2，被称作二阶项，这就使得感知机接收的信号输入当中有x1·x2的交互信息，这就不是一个单纯的感知机了，因为这实际上就是在感知机接受信号之前，信号被另一个东西处理过了。

使用这种方法，感知机需要接收2n个信号，即使以如今的计算能力而言，这都是极为恐怖的，因为即使输入是一个10×10的低分辨率图片，感知机要处理2100个信号。如果沿着这条路发展下去，或许会出现“核技巧”。

另一种方法，就是使用两层的感知机，先对输入数据进行与非、或，再进行与：

但是用于调整多层感知机参数的可行算法没有出现，这是一条在当时更不可行的路。不过随着反向传播算法被再次发现并使用，显然这是一条更正确的路。

顺带一提，决策树也能用于解决异或问题。