单层感知机不能表示XOR(异或逻辑）问题的证明

柔光的暖阳◎ 2022-03-14 10:34 413阅读 0赞

针对问题 a XOR b，真值表为：

从数据集线性可分性的角度证明XOR逻辑是非线性（即线性不可分的）：  
设数据集T为：

其中：

假设T是线性可分的，则存在超平面  
对T中的4个实例正确进行分类，则有

注意：这里的大于小于0与y的取值无关，与参考系有关，表示两个类比，所以也并不需要要求y的取值是正1和负1。  
设  
  
对上式进行化简有

四个不等式之间相互矛盾，所以XOR（异或逻辑）是非线性的，得证。

感知机的学习策略是极小化误差分类点到超平面S的总距离，即经验风险最小化。对于线性不可分数据集，由于总是存在误分类点，算法将不能收敛。事实上，最后的迭代（随机梯度下降SGD）将发生震荡，证明过程可以见Novikoff定理。  
Novikoff定理表明：  
如果分类超平面存在, 仅需在序列 S 上迭代几次，在界为

的错误次数下就可以找到分类超平面，算法停止。

XOR（异或逻辑）图  
  
综上，单层感知机不能表示异或逻辑。而多层神经网络能够解决这一问题，深度学习进一步采用了包含隐藏层的神经网络，来解决线性不可分的问题。