What is a Dichotomy?

Question

I am currently reading:

Stephen Jose Hanson: Meiosis Networks, 1990.

and I stumbled about this:

It is possible to precisely characterize the search problem in terms of the resources or degress of freedom in the learning model. If the task the learning system is to perform is classification then the system can be analyzed in terms of its ability to dichotomize stimulus points in feature space.

Dichotomization Capability: Network Capacity Using a linear fan-in or hyperplane type neuron we can characterize the degrees of freedom inherent in a network of units with thresholded output. For example, with linear boundaries, consider 4 points, well distributed in a 2-dimensional feature space. There are exactly 14 linearly separable dichotomies that can be formed with the 4 target points. However, there are actually 16 ($2^4$) possible dichotomies of 4 points in 2 dimensions consequently, the number of possible dichotomies or arbitrary categories that are linearly implementable can be thought of as a capacity of the linear network in $k$ dimensions with $n$ examples.

What is a "dichonomy" in this case?

(Side questions: what is a fan-in type neuron?)

Answer 1

In a machine learning context, a dichotomy is simply a split of a set into two mutually exclusive subsets whose union is the original set. The point being made in your quoted text is that for four points, a linear boundary can not form all possible dichotomies (i.e., it does not shatter the set). For example, if the four points are arranged on the corners of a square, a linear boundary can be used to create all possible dichotomies except it cannot produce a boundary that splits the two points lying along one diagonal from the other two points (and vice versa), as you indicated in your own answer.

Answer 2

It seems to be about classification with 2 classes. To understand where the 14 comes from, just try all cases of 4 points being in one of two classes:

#!/usr/bin/env python

"""Print all cases of 4 points being in one of two classes in 2D."""


def print_pattern(pattern):
    """Print four points in 2D."""
    print("%s\t%s" % (pattern[0], pattern[1]))
    print("%s\t%s" % (pattern[2], pattern[3]))


get_bin = lambda x, n: format(x, 'b').zfill(n)

# 16 possible cases how 4 points can belong to 2 classes
for i in range(16):
    bin_ = get_bin(i, 4)
    print_pattern(bin_)
    print("-"*60)

which gives:

0    0
0    0
------------------------------------------------------------
0    0
0    1
------------------------------------------------------------
0    0
1    0
------------------------------------------------------------
0    0
1    1
------------------------------------------------------------
0    1
0    0
------------------------------------------------------------
0    1
0    1
------------------------------------------------------------
0    1        --- Not linearly seperable
1    0
------------------------------------------------------------
0    1
1    1
------------------------------------------------------------
1    0
0    0
------------------------------------------------------------
1    0        --- Not linearly seperable
0    1
------------------------------------------------------------
1    0
1    0
------------------------------------------------------------
1    0
1    1
------------------------------------------------------------
1    1
0    0
------------------------------------------------------------
1    1
0    1
------------------------------------------------------------
1    1
1    0
------------------------------------------------------------
1    1
1    1
------------------------------------------------------------

I'm still not quite sure what a dichtonomy is, but this seems to be part of the answer.