Linearly Separable Problem

A linearly separable problem is a problem that, when represented as a pattern space, requires only one straight cut to separate all of the patterns of one type in the space from all of the patterns of another type.  For example, AND is linearly separable because one straight cut is required to separate the one true patterns from the three false patterns in a two-dimensional pattern space.  This is important because if a problem is linearly separable, then it can be solved by a perceptron (Minsky & Papert, 1988).  While perceptrons are limited to solving linearly separable problems, this does not mean that they are uninteresting. For instance, a wide variety of Pavlovian conditioning paradigms are linearly separable (Dawson, 2008), as is the reorientation task that is used to study fundamentals of animal navigation (Dawson, Kelly, Spetch & Dupuis, 2010).

References:

1. Dawson, M. R. W. (2008). Connectionism and classical conditioning. Comparative Cognition and Behavior Reviews, 3 (Monograph), 1-115.
2. Dawson, M. R. W., Kelly, D. M., Spetch, M. L., & Dupuis, B. (2010). Using perceptrons to explore the reorientation task. Cognition, 114(2), 207-226.
3. Minsky, M., & Papert, S. (1988). Perceptrons, 3rd Edition. Cambridge, MA: MIT Press..

.(Added January, 2010)