On the number of multilinear partitions and the computing capacity of multiple-valued multiple-threshold perceptrons

Abstract

We introduce the concept of multilinear partition of a point set V ⊂ Rn and the concept of multilinear separability of a function f : V → K = {0,..., k-1}. Based on well-known relationships between linear partitions and minimal pairs, we derive formulae for the number of multilinear partitions of a point set in general position and of the set K2. The (n, k, s)-perceptrons partition the input space V into s + 1 regions with s parallel hyperplanes. We obtain results on the capacity of a single (n, k, s)-perceptron, respectively, for V ⊂ Rn in general position and for V = K2. Finally, we describe a fast polynomial-time algorithm for counting the multilinear partitions of K2.