An alternative to mapping each n-tuple sample for each image to an address, is to instead store the vector defined by each n-tuple on each image explicitly. In this way, each n-tuple simply defines a sparse subset of the original image vector. This is illustrated in Figure 1 , which shows a continuous n-tuple sampling of a face for the case of n =3 and m =3; note that in practice m has to be much larger than this to get good performance.
Figure 1:
An illustration of the continuous n-tuple sampling process. A set of
random n-tuples are chosen, where each n-tuple defines a set of
n
locations in image space. In the continuous n-tuple method, the
grey-level values at each point are extracted and stored without any
further processing. For the compiled version of the continuous n-tuple
method, some further quantisation is necessary, for example, mapping
from 256 levels of grey down to 8.
By sampling the image in this way, we can deal directly with patterns defined as vectors of real numbers, or as grey scale images, as we have for the face recognition experiment described below. This approach is quite practical when there are only a small number of training patterns per class, or when it is possible to compile all the training vectors for each n-tuple into a look-up table using the algorithm described below.
As before (Equation
1
), let the
j
th n-tuple
be defined by a set of locations in pattern space.
Then, for a given pattern vector
we form a projection of this:
Denote the
k
th vector of the
c
th class as
.
The ``training algorithm'' is simply to extract and store all these vectors from the set of training images.
There are many possible strategies for performing recognition given these extracted vectors. The algorithm proposed here is in Table 3 .
For the j th projected vector, we find the closest (under distance metric D ) stored vector for each class. We then sum (over all j ) the distances (again, as measured by D ) for each class c , and assign class membership to the class with the minimum total.
In the experiments reported below we choose a Manhattan (city-block) distance metric:
i.e. the sum of the absolute differences along each dimension of the vector. Experiments were also made using an unweighted Euclidean distance metric, but with significantly poorer results.
The advantages of the continuous n-tuple method are twofold: firstly, it directly incorporates a useful distance metric, and therefore offers better generalisation than the basic n-tuple method; secondly, it allows us to deal directly with continuous or multi-level input spaces. There is no sacrifice in training speed (training speed should theoretically improve slightly, but this was not measurable in practice).
However, recognition time given a naive implementation of the algorithm is significantly poorer, and gets worse as more example patterns are stored. One solution to this that may be practical, is to perform some quantisation of the input space, and pre-compile the minimum-distances to each stored class vector for each n-tuple, from each possible address location. In this way, we get exactly the same recognition speed as the conventional n-tuple classifier, with something close to the recognition accuracy of the continuous n-tuple classifier. The only sacrifice now is training time; we have to step through all possible addresses in the address space of each n-tuple to set up the distance values for those addresses, and this must be repeated for each n-tuple and each class. For the face recognition problem described below, this is perfectly practical, and this is likely to be the case for many other applications.
There may be cases that the number of quantisation levels on the input space needed to retain the required accuracy make the address-space for each n-tuple too large. In such cases, a useful alternative would be to use the rapid retrieval method of the author [ 6 ], based on the lazy evaluation of a syntactic neural network (SNN). This would still require that each continuous input is quantised, but allows for a finer quantisation to be used than would otherwise be possible. Furthermore, the rapid retrieval method has the property that for some cases, retrieval time actually gets faster as more vectors are stored in it. It also guarantees best-first retrieval of the stored vectors, given some input vector to search for. Hence, the combination of the continuous n-tuple classifier with rapid retrieval lookup offers the possibility of searching massive databases of faces extremely rapidly, and in a way that could actually get faster as more faces are entered into the database!
Due to their attractive features, n-tuple methods have been the subject of much research. See Rohwer and Morciniec [ 8 ] for a comprehensive analysis.
Allinson and Kolcz [ 3 ] have developed a method of mapping scalar attributes into bit strings based on a combination of CMAC and Gray coding methods. This method has the property that for small differences in the arithmetic values of the attributes, the hamming distance between the bit strings is equal to the arithmetic difference. For larger values of the arithmetic distance, the hamming distance is guaranteed to be above a certain threshold. However, where practical, the continuous n-tuple method described in this paper should be preferable, since it incorporates the exact arithmetic distance between attributes.
The continuous n-tuple method clearly has a close relationship with
nearest neighbour classifiers. In fact, each n-tuple acts as a kind of
distance-weighted nearest neighbour classifier for that subset of the
input space. However, due to the fact that each n-tuple is a tiny
projection of the original pattern (and indeed, typically only about 20%
in total of the original pattern space needs to be sampled for optimum
performance), the continuous n-tuple method is much more efficient. It
also tends to perform more accurately. Note that if we use parameters of
n
=
d
(in this case,
) and m=1, then the continuous n-tuple method exactly implements a
1-nearest-neighbour classifier.
Probabilistic interpretations of n-tuple systems have also been used [ 9 , 11 , 7 ], but these are only likely to improve performance over the standard n-tuple method when there is a large quantity of training data available.
The continuous n-tuple method also shares some similarity at the architectural level with the single-layer look-up perceptron of Tattersall et al [ 12 ], though they differ in the way the class outputs are calculated, and in the training methods used to configure the contents of the look-up tables (RAMs).
Adrian F Clark
in input array into class
is a |
C
|-dimensional vector of real numbers
into look-up-table
is a quantisation function that
