Derive: Neural Networks: Simple Parts, Stacked

With the identity replacing both hidden steps, the two hidden answers are $$h_1=w_{11}{x}_1+w_{12}{x}_2+b_1,h_2=w_{21}{x}_1+w_{22}{x}_2+b_2.$$ The output unit forms $$z=w_{31}{h}_1+w_{32}{h}_2+b_3=(w_{31}{w}_{11}+w_{32}{w}_{21})x_1+(w_{31}{w}_{12}+w_{32}{w}_{22})x_2+(w_{31}{b}_1+w_{32}{b}_2+b_3).$$ So $z=a\cdot x+c$ with $a$ and $c$ as stated. The output is $\mathrm{step}(z)$, which is one linear threshold function of the input. Two hidden units that each compute an affine function have added no new shape to the boundary; they have only described the same plane in other coordinates.

For the weights of section 19.3, $w_{11}=w_{12}=1$, $b_1=-1.5$, $w_{21}=w_{22}=1$, $b_2=-0.5$, $w_{31}=-1$, $w_{32}=1$ and $b_3=-0.5$. The coefficients are $$a_1=(-1)(1)+(1)(1)=0,a_2=(-1)(1)+(1)(1)=0,$$ and the constant is $$c=(-1)(-1.5)+(1)(-0.5)-0.5=1.5-0.5-0.5=\mathrm{0.5.}$$ The pre-activation is the constant $0.5$ on every row, so the output step answers $1$ on all four rows. The labels are $0,1,1,0$, so the rows $(0,0)$ and $(1,1)$ are wrong and the network makes two errors. The two hidden units still form the weighted sums that fed AND and OR, but the output weights cancel their varying parts and leave only the constant.

No choice of the nine weights can repair this. Whatever the weights, $z$ is affine in $x$, and $\mathrm{step}(z)$ is a single straight boundary. Section 19.2 proves that XOR has no single straight boundary: its four inequalities contradict one another. The bend in section 19.3 came from the two hidden steps, not from the count of units. Remove the steps and the layer stops being a layer.

The score of a point is $w\cdot x$, since the bias is zero. Before the update, $A$ scores $(1,0)\cdot (-1,2)=-1$, which is the wrong sign for a $+1$ label. $B$ scores $1$ and $C$ scores $1$, both correct. So one point is wrong. The rule adds the offending input to the weights, giving $w=(1,0)+(-1,2)=(0,2)$. After the update, $A$ scores $4$ and is correct, but $B$ scores $(0,2)\cdot (1,-1)=-2$ and $C$ scores $(0,2)\cdot (1,-2)=-4$. Both were correct before and are wrong now. The error count rose from one to two.

Now the condition. A point $y$ labelled $+1$ is correct before the update when $w\cdot y>0$. After the update its score is $(w+x)\cdot y=w\cdot y+x\cdot y$. It is pushed across when that score is at most zero, that is, when $$x\cdot y\le -w\cdot y.$$ For $B$, the left side is $(-1)(1)+2(-1)=-3$ and the right side is $-1$, so $-3\le -1$ holds. For $C$ the left side is $-1-4=-5$, which also holds. The condition is a statement about the angle between the offending point and the point that was correct: a large negative dot product lets one correction damage another row.

Finally, the score of $x$ rises by $$(w+x)\cdot x-w\cdot x=x\cdot x.$$ For $A$ that is $(-1{)}^2+2^2=5$: the score goes from $-1$ to $4$. The same squared length measures both the repair of the offending row and the size of the collateral damage. Section 19.1 uses that fact to explain why the procedure is sensitive to the scale of the data, and this table shows why a falling error count is not guaranteed step by step.

Let $e_n=w_n-3$. The gradient of $J$ is $2(w-3)=2e_n$, so the update is $$w_{n+1}=w_n-\eta \cdot 2e_n.$$ Subtracting $3$ from both sides gives $$e_{n+1}=e_n-2\eta e_n=(1-2\eta )e_n.$$ Applying the same relation $n$ times gives $e_n=(1-2\eta {)}^n{e}_0$, which is the stated form.

At $\eta =0.1$ the factor is $0.8$, and $e_0=1-3=-2$. The errors are $-2$, $-1.6$, $-1.28$ and $-1.024$, so the parameters are $1$, $1.4$, $1.72$ and $1.976$. These are the three values printed in section 19.6.

The iterates converge to $3$ exactly when the error shrinks in size, that is, when $|1-2\eta |<1$. The inequality is equivalent to $-1<1-2\eta <1$, which gives $0<\eta <1$. At $\eta =\frac{1}{2}$ the factor is $0$ and one step lands on $3$. At $\eta =1$ the factor is $-1$, so the error keeps its size and flips sign: the parameters run $1,5,1,5,\dots$ and the loss stays at $4$. At $\eta >1$ the factor is below $-1$, so the error grows and the walk diverges while oscillating. At $\eta =0$ nothing moves.

For the step count at $\eta =0.1$, the error after $n$ steps is $2(0.8{)}^n$. You want $$2(0.8{)}^n\le 0.01,\text{that is}(0.8{)}^n\le \mathrm{0.005.}$$ Taking logarithms gives $n\ge \ln (0.005)/\ln (0.8)=23.74$, so $24$ steps. The check is close: after $23$ steps the error is $0.01181$, which is still above $0.01$, and after $24$ steps it is $0.00944$, which is below. The rounding matters, as it did for the power method in Chapter 9, because a geometric decay crosses a fixed tolerance between two consecutive integers.