2.4.1 Linear Separability and the XOR Problem

Consider two-input patterns $(X_1,X_2)$ being classified into two classes as shown in figure 2.9. Each point with either symbol of $x$ or $o$ represents a pattern with a set of values $(X_1,X_2)$. Each pattern is classified into one of two classes. Notice that these classes can be separated with a single line $L$. They are known as linearly separable patterns. Linear separability refers to the fact that classes of patterns with $n$-dimensional vector ${\bf x} = (x_1, x_2, ... , x_n)$ can be separated with a single decision surface. In the case above, the line $L$ represents the decision surface.

Figure 2.9: Linearly Separable Pattern

The processing unit of a single-layer perceptron network is able to categorize a set of patterns into two classes as the linear threshold function defines their linear separability. Conversely, the two classes must be linearly separable in order for the perceptron network to function correctly [Hay99]. Indeed, this is the main limitation of a single-layer perceptron network.

The most classic example of linearly inseparable pattern is a logical exclusive-OR (XOR) function. Shown in figure 2.10 is the illustration of XOR function that two classes, 0 for black dot and 1 for white dot, cannot be separated with a single line. The solution seems that patterns of $(X_1,X_2)$ can be logically classified with two lines $L_1$ and $L_2$ [BJ91].

Figure 2.10: Exclusive-OR Function