N-tuple or RAM based neural network classification system and method

• US 6,393,413 B1
• Filed: 10/19/1998
• Issued: 05/21/2002
• Est. Priority Date: 02/05/1998
• Status: Expired due to Term

• Current Assignee: Intellix Holdings Ltd.
• Original Assignee: Intellix A/S (American Diversified Group, Inc.)
• Inventors: Linneberg, Christian, Jorgensen, Thomas M.
• Primary Examiner(s): Davis, George B.
• Assistant Examiner(s): Booker, Kelvin
• Application Number:
  US09/174,905
• Time in Patent Office: 1,310 Days
• Field of Search: 706/20, 706/14, 706/15, 382/156, 382/159
• US Class Current: 706/20
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

A method and system for training a computer classification system which can be defined by a network of a number of n-tuples or Look Up Tables (LUTs), with each n-tuple or LUT including a number of rows corresponding to at least a subset of possible classes and further including a number of columns being addressed by signals or elements of sampled training input data examples, each column being defined by a vector having cells with values, wherein the column vector cell values are determined based on one or more training sets of input data examples for different classes so that at least part of the cells comprise or point to information based on the number of times the corresponding cell address is sample from one or more sets of training input examples, and weight cell values are determined, corresponding to one or more column vector cells being addressed or sampled by the training examples.

Claims

1. A method of training a computer classification system which can be defined by a network comprising a number of n-tuples or Look Up Tables (LUTs), with each n-tuple or LUT comprising a number of rows corresponding to at least a subset of possible classes and further comprising a number of columns being addressed by signals or elements of sampled training input data examples, each column being defined by a vector having cells with values, said method comprising determining the column vector cell values based on one or more training sets of input data examples for different classes so that at least part of the cells comprise or point to information based on the number of times the corresponding cell address is sampled from one or more sets of training input examples, and determining weight cell values corresponding to one or more column vector cells being addressed or sampled by the training examples to thereby allow weighting of one or more column vectors cells of positive value during a classification process, said weight cell values being determined based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples.

2. A method according to claim 1, wherein the determination of the weight cell values allows weighting of one or more column vector cells having a positive value (greater than 0) and one or more column vector cells having a non-positive value (lesser than or equal to 0).

3. A method according to claim 1, wherein the weight cell values are arranged in weight vectors corresponding to at least part of the column vectors.

4. A method according to claim 3, wherein all column vectors have corresponding weight vectors.

5. A method according to claim 1, wherein determination of the weight cells allows weighting of any column vector cell.

6. A method according to claim 1, wherein the weight cells are arranged in weight vectors and the determination of the weight cell values comprises initialising one or more sets of weight vectors corresponding to at least part of the column vectors, and adjusting weight vector cell values of at least part of the weight vectors based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples.

7. A method according to claim 6, wherein the column vector cell values are determined and stored in storing means before the adjustment of the weight vector cell values.

8. A method according to claim 6, wherein the initialisation of the weight vectors comprises setting all weight vector cell values to a predetermined constant value, said predetermined value preferably being 1.

9. A method according to claim 6, wherein the initialisation of the weight vectors comprises setting each weight vector cell to a predetermined specific cell value.

10. A method according to claim 6, wherein the adjustment of the weight vector cell values comprises the steps of determining a global quality value based on at least part of the weight and column vector cell values, determining if the global quality value fulfils a required quality criterion, and adjusting at least part of the weight cell values until the global quality criterion is fulfilled.

11. A method according to claim 10, wherein the global and/or the local quality criterion is changed during the adjustment iteration process.

12. A method according to claim 10, wherein the adjustment iteration process is stopped if the global quality criterion is not fulfilled after a given number of iterations.

13. A method according to claim 10, wherein the adjusted weight cell values are stored after each adjustment, and wherein the determination of the global quality value further is followed by separately storing the hereby obtained weight cell values or classification system configuration values if the determined global quality value is closer to fulfil the global quality criterion than the global quality value corresponding to previously separately stored weight cell values or configuration values.

14. A method according to claim 6, wherein the adjustment of the weight cell values comprises the steps of

a) selecting an input data example from the training set(s),

b) determining a local quality value corresponding to the sampled training input example, the local quality value being a function of at least part of the addressed weight and column vector cell values,

c) determining if the local quality value fulfils a required local quality criterion, if not, adjusting one or more of the addressed weight vector cell values if the local qua lity criterion is not fulfilled,

c) selecting a new input example from a predetermined number of examples of the training set(s),

d) repeating the local quality test steps (b)-(d) for all the predetermined training in put examples,

e) determining a global quality value based on at least part of the weight and column vectors being addressed during the local quality test,

f) determining if the global quality value fulfils a required global quality criterion, and,

h) repeating steps (a)-(g) until the global quality criterion is fulfilled.

15. A method according to claim 14, wherein steps (b)-(d) are carried out for all examples of the training set(s).

16. A method according to claim 1, wherein at least part of the column cell values are determined as a function of the number of times the corresponding cell address is sampled from the set(s) of training input examples.

17. A method according to claim 1, wherein the maximum column vector value is 1, but at least part of the values have an associated value being a function of the number of times the corresponding cell address is sampled from the training set(s) of input examples.

18. A method according to claim 1, wherein the determination of the column vector cell values comprises the training steps of

a) applying a training input data example of a known class to the classification network, thereby addressing one or more column vectors,

b) incrementing, preferably by one, the value or vote of the cells of the addressed column vector(s) corresponding to the row(s) of the known class, and

c) repeating steps (a)-(b) until all training examples have been applied to the network.

19. A method of classifying input data example into at least one of a plurality of classes using a computer classification system configured according to a method of claim 1, whereby the column vector cell values and the corresponding weight vector cell values are determined for each n-tuple or LUT based on one or more training sets of input data examples, said method comprising

a) applying an input data example to be classified to the configured classification network thereby addressing column vectors and corresponding weight vectors in the set of n-tuples or LUTs,

b) selecting a class thereby addressing specific rows in the set of n-tuples or LUTs,

c) determining an output value as a function of values of addressed weight cells,

d) repeating steps (b)-(c) until an output has been determined for all classes,

e) comparing the calculated output values, and

f) selecting the class or classes having maximum output value.

20. A method according to claim 19, wherein the output value further is determined as a function of values of addressed column cells.

21. A method according to claim 20, wherein said output value is determined as a first summation of all the addressed weight vector cell values corresponding to column vector cell values greater than or equal to a predetermined value, said predetermined value preferably being 1.

22. A method according to claim 20, wherein said step of determining an output value comprises determining a first summation of all the addressed weight vector cell values corresponding to column vector cell values greater than or equal to a predetermined value, determining a second summation of all the addressed weight vector cell values, and determining the output value by dividing the first summation by the second summation.

23. A method of training a computer classification system which can be defined by a network comprising a number of n-tuples or Look Up Tables (LUTs), with each n-tuple or LUT comprising a number of rows corresponding to at least a subset of possible classes and further comprising a number of columns being addressed by signals or elements of sampled training input data examples, each column being defined by a vector having cells with values, said method comprising determining the column vector cell values based on one or more training sets of input data examples for different classes so that at least part of the cells comprise or point to information based on the number of times the corresponding cell address is sampled from one or more sets of training input examples, and determining weight cell values corresponding to at least a subset of the column vector cells to thereby allow boosting of one or more column vector cells during a classification process, said weight cell values being determined based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples.

24. A method according to claim 23, wherein the weight cell values are determined so as to allow suppressing of one or more column vector cells during a classification process.

25. A method of determining weight cell values in a computer classification system which can be defined by a network comprising a number of n-tuples or Look Up Tables (LUTs), with each n-tuple or LUT comprising a number of rows corresponding to at least a subset of possible classes and further comprising a number of column vectors with at least part of said column vectors having corresponding weight vectors, each column vector being addressed by signals or elements of a sampled training input data example and each column vector and weight vector having cells with values being determined based on one or more training sets of input data examples for different classes, said method comprising determining the column vector cell values based on the training set(s) of input examples so that at least part of said values comprise or point to information based on the number of times the corresponding cell address is sampled from the set(s) of training input examples, and determining weight vector cell values corresponding to one or more column vector cells based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples, said determination allowing weighting of column vector cells having a positive value (greater than 0) and column vector cells having a non-positive value (lesser than or equal to 0).

26. A system for training a computer classification system which can be defined by a network comprising a stored number of n-tuples or Look Up Tables (LUTs), with each n-tuple or LUT comprising a number of rows corresponding to at least a subset of possible classes and further comprising a number of columns being addressed by signals or elements of sampled training input data examples, each column being defined by a vector having cells with values, said system comprising input means for receiving training input data examples of known classes, means for sampling the received input data examples and addressing column vectors in the stored set of n-tuples or LUTs, means for addressing specific rows in the set of n-tuples or LUTs, said rows corresponding to a known class, storage means for storing determined n-tuples or LUTs, means for determining column vector cell values so as to comprise or point to information based on the number of times the corresponding cell address is sampled from the training set(s) of input examples, and means for determining weight cell values corresponding to one or more column vector cells being addressed or sampled by the training examples to thereby allow weighting of one or more column vectors cells of positive value during a classification process, said weight cell values being determined based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples.

27. A system according to claim 26, wherein the means for determining the weight cell values is adapted to determine these values so as to allow weighting of one or more column vector cells having a positive value (greater than 0) and one or more column vector cells having a non-positive value (lesser than or equal to 0).

28. A system according to claim 26, wherein the means for determining the weight cell values is adapted to determine these values so that the weight cell values are arranged in weight vectors corresponding to at least part of the column vectors.

29. A system according to claim 26, wherein the means for determining the weight cell values is adapted to allow weighting of any column vector cell.

30. A system according to claim 26, wherein the means for determining the weight cell values comprises means for initialising one or more sets of weight vectors corresponding to at least part of the column vectors, and means for adjusting weight vector cell values of at least part of the weight vectors based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples.

31. A system according to claim 30, wherein the means for initialising the weight vectors is adapted to setting all weight vector cell values to a predetermined constant value, said predetermined value preferably being one.

32. A system according to claim 30, wherein the means for initialising the weight vectors is adapted to setting each weight vector cell to a predetermined specific value.

33. A system according to claim 30, wherein the means for adjusting the weight vector cell values is adapted to determine a global quality value based on at least part of the weight and column vector cell values, determine if the global quality value fulfils a required global quality criterion, and adjust at least part of the weight cell values until the global quality criterion is fulfilled.

34. A system according to claim 33, wherein the means for adjusting the weight vector cell values is adapted to stop the iteration process if the global quality criterion is not fulfilled after a given number of iterations.

35. A system according to claim 33, wherein the means for storing n-tuples or LUTs comprises means for storing adjusted weight cell values and separate means for storing best so far weight cell values, said means for adjusting the weight vector cell values further being adapted to replace previously separately stored best so far weight cell values with obtained adjusted weight cell values if the determined global quality value is closer to fulfil the global quality criterion than the global quality value corresponding to previously separately stored best so far weight values.

36. A system according to claim 30, wherein the means for adjusting the weight vector cell values is adapted to

a) determine a local quality value corresponding to a sampled training input example, the local quality value being a function of at least part of the addressed weight and column vector cell values,

b) determine if the local quality value fulfils a required local quality criterion,

c) adjust one or more of the addressed weight vector cell values if the local quality criterion is not fulfilled,

d) repeat the local quality test for a predetermined number of training input examples,

e) determine a global quality value based on at least part of the weight and column vectors being addressed during the local quality test,

f) determine if the global quality value fulfils a required global quality criterion, and,

g) repeat the local and the global quality test and associated weight adjustments until the global quality criterion is fulfilled.

37. A system according to claim 26, wherein the means for determining the column vector cell values is adapted to determine these values as a function of the number of times the corresponding cell address is sampled from the set(s) of training input examples.

38. A system according to claim 26, wherein the means for determining the column vector cell values is adapted to determine these values so that the maximum value is 1, but at least part of the values have an associated value being a function of the number of times the corresponding cell address is sampled from the training set(s) of input examples.

39. A system according to claim 26, wherein, when a training input data example belonging to a known class is applied to the classification network thereby addressing one or more column vectors, the means for determining the column vector cell values is adapted to increment the value or vote of the cells of the addressed column vector(s) corresponding to the row(s) of the known class, said value preferably being incremented by one.

40. A system according to claim 26, wherein all column vectors have corresponding weight vectors.

41. A system for training a computer classification system which can be defined by a network comprising a stored number of n-tuples or Look Up Tables (LUTs), with each n-tuple or LUT comprising a number of rows corresponding to at least a subset of possible classes and further comprising a number of columns being addressed by signals or elements of sampled training input data examples, each column being defined by a vector having cells with values, said system comprising input means for receiving training input data examples of known classes, means for sampling the received input data examples and addressing column vectors in the stored set of n-tuples or LUTs, means for addressing specific rows in the set of n-tuples or LUTs, said rows corresponding to a known class, storage means for storing determined n-tuples or LUTs, means for determining column vector cell values so as to comprise or point to information based on the number of times the corresponding cell address is sampled from the training set(s) of input examples, and means for determining weight cell values corresponding to at least a subset of the column vector cells to thereby allow boosting of one or more column vectors cells during a classification process, said weight cell values being determined based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples.

42. A system according to claim 41, wherein means for determining the weight cell values is adapted to determine these values so as to allow suppressing of one or more column vector cells during a classification process.

43. A system for determining weight cell values of a classification network which can be defined by a stored number of n-tuples or Look Up Tables (LUTs), with each n-tuple or LUT comprising a number of rows corresponding to at least a subset of the number of possible classes and further comprising a number of column vectors with at least part of said column vectors having corresponding weight vectors, each column vector being addressed by signals or elements of a sampled training input data example and each column vector and weight vector having cell values being determined during a training process based on one or more sets of training input data examples, said system comprising:

input means for receiving training input data examples of known classes, means for sampling the received input data examples and addressing column vectors and corresponding weight vectors in the stored set of n-tuples or LUTs, means for addressing specific rows in the set of n-tuples or LUTs, said rows corresponding to a known class, storage means for storing determined n-tuples or LUTs, means for determining column vector cell values so as to comprise or point to information based on the number of times the corresponding cell address is sampled from the training set(s) of input examples, and means for determining weight vector cell values corresponding to one or more column vector cells based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples, said determination allowing weighting of one or more column vector cells having a positive value (greater than

     0) and one or more column vector cells having a non-positive value (lesser than or equal to

     0).

44. A system for classifying input data examples into at least one of a plurality of classes, said system comprising:

storage means for storing a number or set of n-tuples or Look Up Tables (LUTs) with each n-tuple or LUT comprising a number of rows corresponding to at least a subset of the number of possible classes and further comprising a number of column vectors with corresponding weight vectors, each column vector being addressed by signals or elements of a sampled input data example and each column vector and weight vector having cells with values being determined during a training process based on one or more sets of training input data examples, said system further comprising;

input means for receiving an input data example to be classified, means for sampling the received input data example and addressing columns and corresponding weight vectors in the stored set of n-tuples or LUTs, means for addressing specific rows in the set of n-tuples or LUTs, said rows corresponding to a specific class, means for determining an output value as a function of addressed weight cells, and means for comparing calculated output values corresponding to all classes and selecting the class or classes having maximum output value.

45. A system according to claim 44, wherein the output value further is determined as a function of values of addressed column cells.

46. A system according to claim 44, wherein the output determining means comprises means for producing a first summation of all the addressed weight vector cell values corresponding to a specific class and corresponding to column vector cell values greater than or equal to a predetermined value.

47. A system according to claim 46, wherein the output determining means further comprises means for producing a second summation of all the addressed weight vector cell values corresponding to a specific class, and means for determining the output value by dividing the first summation by the second summation.

48. A system according to claim 44, wherein the cell values of the column vectors and the weight vectors have been determined by use of a training system, wherein the determination of the weight cell values allows weighting of one or more column vector cells having a positive value (greater than 0) and one or more column vector cells having a non-positive value (lesser than or equal to 0).

49. A system according to claim 44, wherein the cell values of the column vectors and the weight vectors have been determined during a training process comprising the steps of:

determining the column vector cell values based on one or more training sets of input data examples for different classes so that at least part of the cells comprise or point to information based on the number of times the corresponding cell address is sampled from one or more sets of training input examples, and

determining weight cell values corresponding to one or more column vector cells being addressed or sampled by the training examples to thereby allow weighting of one or more column vectors cells of positive value during a classification process, said weight cell values being determined based on the information of at least part of the determined column vector cell values and by use of at least part of the training set(s) of input examples.