机器学习理论作业1

机器学习理论作业1

10211900416 郭夏辉

Q2.1: 证明感知机不能表示异或问题

感知机模型：\(f(x)=sign(w·x+b)\)

其中：\(x \in R^n为输入的特征向量,w \in R^n 为权重,b \in R 为偏置\)

假设感知机模型可以表示异或问题，设向量\(x\)维度为2，\(x=[x_1,x_2]^T\)与之对应，\(w=[w_1,w_2]^T\)

对异或函数来说，先来列出其对应的输入和输出。

\(x_1\)	\(x_2\)	\(x_1 ⊕ x_2\)
0	0	-1
0	1	1
1	0	1
1	1	-1

1. 若\(x_1=0,x_2=0,f(x)=-1\),此时\(w·x+b<0\),可得\(b<0\),即\(-b> 0\);
2. 若\(x_1=0,x_2=1,f(x)=1\),此时\(w·x+b>0\),可得\(w_2> {-b}>{0}\),即\(w_2+b> 0\);
3. 若\(x_1=1,x_2=0,f(x)=1\),此时\(w·x+b > 0\),可得\(w_1> {-b}>{0}\),即\(w_1+b> 0\);
4. 若\(x_1=1,x_2=1,f(x)=-1\),此时\(w·x+b<0\),可得\(w_1+w_2+b<0\)

在1.、2.和3.中，对所推出的条件做加法，可得\(w_1+w_2+2b-b=w_1+w_2+b>0\),这与4.中所等价的条件矛盾，故原假设不成立，不存在任何感知机模型表示异或问题，感知机不能表示异或问题，原式得证。

当然这个题目还可以通过画图法直观地证明，无法找到一条直线将相应的点分离，此处就不赘述了。