Data Processing Device and Method for Selecting Data Words Contained in a Dictionary

The invention relates to a data processing device containing a plurality of fixed-length exemplary words DR arranged in a multidimensional space and together constituting a dictionary, for upon presentation of a test word DO, in said dictionary selecting one or more corresponding words MS, that according to a predetermined correspondence criterion are closest to said test word DO.

The invention also relates to a method of selecting data words contained in a dictionary.

A device and a method of this kind are used in the compression of information or the classification of data.

The methods generally used are based on the search for a word A.sup.m which is nearest to a data word X to be processed. The word A.sup.m belongs to a group of M reference words which are called a dictionary. These words A.sup.m and X generally comprise N components A.sub.i.sup.m (or X.sub.i) where i=1..N.

The proximity is often evaluated on the basis of a distance criterion d(A.sup.m,X) between the word A.sup.m and the word X. When the components are numbers, for example the euclidean distance can be taken: ##EQU1##

Thus, it is necessary to determine the word A.sup.m1 for which the distance from the data word X is minimum. Thus, for any word A.sup.m of the dictionary it is necessary that:

It is not only possible to determine the one nearest word A.sup.m1, but also the K words A.sup.m1, A.sup.m2, . . . , A.sup.mK which are nearest with respect to a predetermined proximity limit. The search may be terminated, either when a sufficient number of corresponding words has been found or when all corresponding words have been found that correspond better than or at least as well as according to a correspondence limit.

The method currently used for the determination of the nearest word or words consists in the execution of a complete calculation of all distances between a data word and all respective words of the dictionary, followed by a search for the smallest distance or distances by way of a comparison operation. Such an operation enables an error-free result to be obtained. However, it is very costly in terms of calculation time, i.e. mainly for the calculation of all distances when the dictionary contains many words.

Various proposals have been made for reducing this calculation duration, but generally they all lead to either the introduction of errors or the imposition of constraints as regards the dictionary. A relevant reference is: "Delayed-decision binary tree-searched vector quantization for image compression" by CHIA LUNG YEH, SPIE Vol. 1989, pp. 154-158. The document proposes the execution of a tree-search on the words of the dictionary by examining several branches of said tree simultaneously. This method determines a code with few errors when the number of branches examined is large, but requires a long calculation time.

The problem to be solved, therefore, is the selection of the word or words of the dictionary which is or are nearest to a data word to be analysed, notably by reducing the duration of processing. It should be possible to carry out this operation with an arbitrarily low error rate.

According to one of its aspects, the object is realized by

first means (20) for meshing (netting) said multidimensional space whereby each exemplary word is either within one mesh or on a boundary between neighbouring meshes,

second means (24, 25) for assigning to each mesh a respective sub-dictionary that contains any word among said exemplary words that according to said correspondence criterion would correspond to at least one word, fiduciary or exemplary, assigned to the latter mesh;

third means for assigning said test word DO to any particular mesh to which it belongs and thereupon applying said correspondence criterion exclusively to the exemplary words of the sub-dictionary of said any particular mesh.

The solution may also be formed by a programmed device, for example a computer. In that case the device is characterized in that said device comprises preprogrammed means for successively:

firstly, meshing (netting) said multidimensional space (20) whereby each exemplary word is assigned to at least one mesh;

secondly, assigning (24, 25) to each mesh a respective sub-dictionary that contains any word among said exemplary words, that according to said correspondence criterion would correspond to at least one word, fiduciary or exemplary, assigned to the latter mesh;

thirdly, assigning said test word DO to any particular mesh to which it belongs and thereupon applying said correspondence criterion exclusively to the exemplary words in the sub-dictionary of said any particular mesh.

The assignment of all exemplary words of the dictionary to one or more sub-dictionaries each associated with a respective maze of the mesh allows for a substantial reduction of the calculation time during the examination of an arbitary data word to be processed. An arbitrarily small error rate can be achieved by the choice of the dimensions of the segments and the number of test samples.

The data words of the dictionary constitute an assembly which is partitioned by segmentation of the space enclosing this assembly. This segmentation can be realised by means of separators. In accordance with the invention, these separators are preferably generated by a neural network. It may concern a layered neural network or a tree-like neural work. However, it is alternatively possible for these separators to be determined on the basis of a programmed logic array (PLA) or on the basis of combinatory logic.

In the preferred case involving a neural network, the phase for positioning the separators (i.e. the segmentation phase) is carried out during a learning phase. The neural networks are formed by elements which are referred to as neurons and which realise a function in the input space.

Generally speaking, such function is given by: ##EQU2## where X.sub.j is the component of the order j of the data element X.sub.j,

C.sub.j is the component of the order j of the synaptic vector C,

N is the dimension of the space of the data X,

f is a generally non-linear function, proper to the neuron in question.

In accordance with the invention, the function f is preferably of the staircase type, i.e. it is constant per intervals, for example f(u)=i for a.sub.i <u.ltoreq.a.sub.i+1, where i=0..L-1, where a.sub.0 =-.infin.<a.sub.1 <a.sub.2 < . . . <a.sub.L-1 <a.sub.L =+.infin..

The neurons may be organised in a layered neural network or in a neutron tree.

In a layered neural network, a successive calculation takes place of all neurons of a given layer whose respective outputs V constitute the inputs of the next layer. Several successive layers can also be formed.

In a neural network one distinguishes the learning phase from the user phase. The learning phase implies calculation of all neuron states in order to position the separators and to determine the number of neurons necessary for the intended task. However, for a tree-like neuron network, all neuron states are no longer calculated for the user phase, but only a limited number which depends on the value of the output of the preceding neuron.

The end of the learning phase occurs when all layers of the layered neural network have their synaptic coefficients calculated or when it is no longer necessary to calculate a subsequent neuron in a tree-like neural network. Because the output states V.sub.j, j=1..r, assume a limited group of values, a distribution (segmentation) of the data space into a limited number of sub-groups (segments) is obtained. This distribution will be learned by one of the neural networks in the form of synaptic coefficients so generated. Therefore, during the learning phase the network is presented with a series of examples for which the output results is known in advance. Preferably, the examples chosen are words of the dictionary. However, it is also possible to choose examples of data which do not form part of the dictionary but for which the nearest word of the dictionary is known in advance. The learning process consists in the assigning of data examples according to the nearest dictionary word. Numerous learning algorithms and are known to those skilled in the art. For example, reference is made to the article by R. P. LIPPMANN "An introduction to computing with neural nets", IEEE ASSP Magazine, April 1987, pp. 4-22.

The data words introduced into the neural network may be either canonical (non-prepared) words or prepared words. Thus, for example in image processing the data words may define a characteristic of a sequence of pixels: luminosity, contrast, . . . For the processing of an acoustic signal, the data words may be formed by a sequence of samples relating to a time characteristic, frequency characteristic, etc. The situation is analogous for data word classification problems. Canonical coordinates of such canonical data words may be directly introduced into the neural network. However, it is also possible to consider the distribution (in a mathematical sense) formed by these data words and to prepare these data as a function of the characteristics of said distribution of the assembly of data relating to the problem to be treated. Thus, for example it is possible to perform an analysis into principal components of the whole distribution or a part of the distribution of the words of the dictionary, and to choose coordinate axes adapted to this distribution in order to prepare the data words and use a principal coordinate of the distribution. Several data preparation operations can be performed by performing analysis into successive principle components on parts of the data distribution, said parts being obtained in the course of the learning process.

The analysis into principal components is a statistical method which enables an assembly of N vectors y.sup..mu. (points in a d-dimensional space) to be described by means of a mean vector ##EQU3## of d principal directions and the d corresponding variances .sigma..sup.2. The method is described in detail in "Elements d'Analyse de Donnees" by E. DIDAY, J. LEMAIRE, J. POUGET, E. TESTU, Editeur Dunod (1982), page 167, ff.

The function f may be fixed for each neuron or be adapted as determined by the words of the dictionary. The learning phase enables calculation of the synaptic coefficients and determination of the function (functions) f so that each partition, that is to say each segment of the dictionary as determined by the outputs of the neurons considered, enclosed relatively few words of the dictionary.

For performing the learning operation a plural-layered network can be used and a particular intermediate layer H can be examined for the forming of the segments. This allows for an increased number of segments, because the number of segments effectively used increases as the first layer is approached.

When the segmentation has been performed, the sub-dictionaries relating to each segment are determined, i.e. for each output state of the neural network. The sub-dictionaries are formed by accumulating for each segment the results obtained by presentation of a sequence of examples X.sup.p :

an assembly of examples X.sup.p to be tested is chosen for which the solution is known, that is to say for which the K nearest words A.sup.m1(p), A.sup.m2(p), . . . , A.sup.mK(p) of the dictionary are known;

the output state of the network V.sub.1 (p), V.sub.2 (p), . . . , V.sub.r (p) which characterizes a particular segment is determined for each example X.sup.p, thus defining the assignment of the examples X.sup.p to said segment;

the sub-dictionary of each segment is formed by accumulating the words A.sup.m1(p), A.sup.m2(p), . . . , A.sup.mK(p) associated with each segment.

These sub-dictionaries can be stored in memories which each are addressed by the respective associated output state of the neural network.

By increasing the number of test examples, the error rate occurring during the subsequent user phase decreases. This rate can thus be made arbitrarily low.

After the neural network has learned its segmentation and the subdictionaries associated with each segment have been determined, the neural network can operate in the user phase on the test data words to be processed.

To this end, the data word X to be processed is introduced into the neural network whose output delivers a configuration of output stages V.sub.1, . . . , V.sub.r. This configuration enables determination of the relevant sub-dictionary for the processing of the data word X.

The correspondence criterion is then exhaustively determined for all words of this sub-dictionary A.sup.m1, A.sup.m2, . . . , A.sup.mK in order to calculate the correspondence between the data word X to be processed and each of the words of the sub-dictionary. This correspondence may be characterized as a distance or a similarity.

For a data word to be processed the calculation of the correspondence during the user phase is thus advantageously limited to the consideration of exclusively the words of the sub-dictionary whereto it relates. No restriction whatsoever is imposed as regards the dictionary.

The invention also characterizes a method of selecting data words contained in a dictionary, which method can be carried out by an appropriately programmed computer.

The method is characterized by the following steps:

a first step for segmenting the space enclosing the data words of the dictionary,

a second step for generating sub-dictionaries, including the establishment of correspondence, in accordance with a predetermined correspondence criterion, between given words of the dictionary and each segment in order to form the words of the sub-dictionaries associated with each segment,

a third step for the use of the sub-dictionaries by determining, for an arbitrary data word to be processed, its association with a segment and by subsequently determining, in accordance with said correspondence criterion, that word or words among the words of the sub-dictionary associated with said segment which corresponds (correspond) best to said arbitrary data word to be processed.

According to a further version of the invention, it is also possible to use pre-established sub-dictionaries with which the words of the dictionary are already associated. The neural network then serves to directly perform the selection of the appropriate sub-dictionary. The device in accordance with the invention in that case comprises a neural network which addresses the sub-dictionaries determined by each data word to be processed and means for determining, among the words of the addressed memory, that word or those words which corresponds (correspond) best to said arbitrary data word to be processed. The neural network may either have a tree-like organisation or a layered organisation.

Applications of a device or method in accordance with the invention are in the field of data compression for the processing of images or acoustic or other signals or in the field of data classification, and processing time is shortened appreciably. The relevant hardware is also simplified.

The invention will be described in detail hereinafter with reference to the accompanying drawing; therein:

FIG. 1 shows an example of the segmentation of the data space in a two-dimensional representation;

FIG. 2A shows a diagram illustrating the segmentation by means of a neural network;

FIG. 2B shows a diagram illustrating the formation of the sub-dictionaries;

FIG. 2C shows a diagram illustrating the use of the sub-dictionaries;

FIGS. 3A-3E illustrate the formation of a sub-dictionary.

FIG. 1 shows an example of the segmentation of the data space in a two-dimensional representation. During the learning phase, the neural network determines its synaptic coefficients in order to place separators 10 to 19 forming said segmentation. Each segment will enclose one or more words of the dictionary, for example the words A, B, C, D, E, F.

FIGS. 2A-2C are diagrams of an apparatus for implementing the invention. FIGS. 3A-3E illustrate the formation of a sub-dictionary. For better clarity, first the latter Figures are now treated in detail. First, FIG. 3A shows dictionary words, each represented by a cross, within a rectangle 30 that represents the whole space or a part thereof, wherein the dictionary has been defined. For clarity, a two-dimensional space has been chosen but the actual number of dimensions in practice may be much higher. Now the first operational step consists in meshing or netting the operational space. This is effected by positioning a plurality of hyperplanes in the multi-dimensional space, each such hyperplane forming a separator. Generally, the dimensionality of such hyperplane is one lower than the dimensionality of the space. In two-dimensional space they are lines, in three-dimensional space, planes, etc. The separators are shown in FIG. 3B, the mapping of the dictionary words on the meshed multi-dimensional space in FIG. 3C. Each dictionary word is shown to be inside a particular maze of the mesh. Alternatively, such dictionary word may be positioned exactly on one of the separators, or even on one or more intersecting separators.

The second step of the process consists in assigning to each respective maze (or mesh) a part of the words of the dictionary in general. In particular, all words are of uniform length. The assigning is effected on the basis of a correspondence criterion. For simplicity, first as correspondence criterion the distance between nearest neighbours is taken. Now, for example, the mesh mnpq contains dictionary words C, D. However, during the processing of a test word, the later could be found lying anywhere inside mesh mnpq (or even on one of its boundaries, which could also be the case for one or more of the dictionary words, but which has not been shown for simplicity). This means that in practice, the closest neighbour(s) of such test word among the dictionary words could by inside mesh mnpq as well as outside it. For finding the dictionary word best corresponding to a test word that itself could have been a dictionary word assigned to mesh mnpq, it is thus necessary to take also dictionary words into account that are situated outside mesh mnpq. In the example, to this effect words A, B, E, F, G, have been taken; these are the best corresponding dictionary words each to one or more words inside mesh mnpq but which have not included in the dictionary as exemplary words and are thus called fiduciary words. In consequence, there is assigned to mesh mnpq a sub-dictionary constituted by words A, B, C, D, E, F, G. The same process is executed for each one of the several meshes. So, for correctly determining the one exemplary word obeying best to the test word in question all exemplary words outside the mesh in question should be assigned to the mesh' dictionary if themselves they are the one most closely corresponding word to a word that could belong to the mesh. If the two best corresponding dictionary words should be found, always the two best corresponding dictionary words for each actual or fiduciary word inside the mesh should be assigned to the sub-dictionary in question. For other cases, even more dictionary words could be assigned, such as when a variable number of dictionary words should be assigned to a test word. In the above cases, the minimum sub-dictionary has been specified. It may always be extended to comprise more dictionary words. Further, the correspondence criterion may be expressed as being a maximum allowable distance to a test word. In that case, the correspondence criterion for assigning the exemplary words to a particular mesh's sub-dictionary would also be the same maximum distance (or a larger one) to any possible word assignable to the mesh itself.

A particular property of the above method is that the sub-dictionary is created independently of future test words. FIG. 3D shows the assigning of words to the sub-dictionary of mesh mnpq. For clarity, an arbitrary contour has been shown that encompasses all exemplary words of the sub-dictionary but no others. The shape of the contour is inconsequential.

During the processing of an unknown word W (FIG. 3E) first it is determined within which mesh it belongs, here mesh mnpq. Next, only the words of the sub-dictionary of mesh mnpq need to be checked against the correspondence criterion. Obviously checking only the words of one sub-dictionary is much easier and/or faster than checking of all dictionary words would be. From FIG. 3F it is clear that within the sub-dictionary, word D has the best correspondence to word W.

FIG. 2A shows in the form of a symbolic block a neural network 20 whose inputs 21 receive the words DR of the dictionary. Its outputs 22 supply output states whose various configurations each identify one segment of the input data word space. The neural network serves to position separators according to the learning method known to those skilled in the art. Thus, for example for the learning of a layered neural network it is possible to use the known error back-propagation method which consists of the presentation of examples to the input for which the output results are known in advance (nearest dictionary word A.sup.m1) and back propagation of the errors in the neural network. The learning then consists of the calculation of the synaptic coefficients of the neural network in order to ensure that the results which are known in advance are effectively obtained at the output of the neural network. Information in this respect is given in the article by R. P. LIPPMANN, "An introduction to computing with neural nets", IEEE ASSP Magazine, April 1987, pp. 4-22.

It is also possible to use tree-line neural networks, for example the networks described in the article by R. P. LIPPMANN "Pattern classification using neural networks", IEEE COM Magazine, November 1989, pp. 47-64. The neural network is in that case constructed so that the number of neurons as well as the synaptic coefficients are adapted to the function to be learned. The advantage of the use of a tree-like neural network resides in the fact that not only the number of neurons to be used is smaller than the number of neurons in a layered neural network, but above all in the fact that in the user mode not all neuron states are calculated but only those of the branches of the tree which are involved in the relevant task.

Preferably, in accordance with the invention learning is performed in order to ensure that each segment of the dictionary has exactly one date word. Alternatively, a segment may enclose several words of the dictionary.

When segmentation has been performed, the device must generate the sub-dictionaries. The diagram of FIG. 2B is an example of such generation. To this end, use is made of examples of data words EX which differ from the data words of the dictionary. These examples EX are distributed at random in the various segments of the input space. These examples EX are introduced into the neural network 20 and produce output state configurations on the output which serve to address, for example a memory 24. These examples EX and the words of the dictionary DR are introduced into an element 25 which tests the correspondence criterion. This correspondence criterion can determine a distance or a similarity between two data. This is, for example, the euclidean distance: d(DR,EX)=(DR-EX).sup.2

The distances between a given example EX and all respective words DR of the dictionary are then calculated. Depending on the predetermined desired correspondence, given words of the dictionary are chosen as explained supra to form the sub-dictionary assigned to the output state configuration (that is to say to the segment) relating to the example processed. This sub-dictionary is stored in the memory 24.

This predetermined correspondence may be the selection of the nearest neighbours or the neighbours showing best resemblance or an other characteristic.

Because operation takes place on a large number of examples, sub-dictionaries are thus obtained which are associated with each segment and which are sufficiently numerous, thanks to the number of segments and the number of examples EX, to enable reduction of the errors in the user mode. The error rates can thus be reduced to an arbitrarily small value by using a large number of examples EX. No restriction whatsoever is imposed as regards the dictionary itself.

When the sub-dictionaries have been formed, the device can be used so as to operate with data words DO to be processed (FIG. 2C). These data words DO are introduced into the neural network 20 and produce, on the output 22, an output state configuration which addresses the memory 24. The latter delivers the words of the sub-dictionary associated with the addressed segment. A member 27, which may be the already described member 25, determines the state of correspondence between the data word DO and the words of the addressed sub-dictionary. This determination, therefore, is performed on the very limited number of words of the sub-dictionary, offering a substantial gain in processing time.

Let us consider the data word X to be processed which is situated in the hatched cell of FIG. 1. Its addressed sub-dictionary comprises, for example the words A, B, C (no relation to A . . . in FIG. 3D,E) and not the words D, E, F, because they are too remote from the cell. The calculation of the correspondence will thus be realised exclusively for these words of the sub-dictionary.

According to the described embodiment, the neural network serves to generate the sub-dictionaries as well as to select each appropriate sub-dictionary for the processing of a data word in the user mode. When the dictionaries have already been established, either because they have already been identified or because they have already been determined by other approaches, the invention can be limited to the use shown in FIG. 2C. The neural network 20 addressed the memory 24 which delivers the words of the addressed dictionary to the correspondence comparison member 27 which determines the level of correspondence between said words of the addressed dictionary and the input data words DO. The memory 24 may be formed by any addressable member enabling reading of different addressed dictionaries.