Method and apparatus for input classification using non-spherical neurons

• US 5,438,629 A
• Filed: 06/19/1992
• Issued: 08/01/1995
• Est. Priority Date: 06/19/1992
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Moed, Michael C., Lee, Chih-Ping
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US07/901,429
• Time in Patent Office: 1,138 Days
• Field of Search: 382/14, 382/15, 382/36, 382/49, 395/21, 395/22, 395/23
• US Class Current: 382/156
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/2414 Smoothing the distance, e.g. radial basis function networks [RBFN]
• CPC Class Codes: G06F 18/24143 Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN]
• CPC Class Codes: G06N 3/082 modifying the architecture, e.g. adding, deleting or silencing nodes or connections
• CPC Class Codes: G06V 30/19107 Clustering techniques
• CPC Class Codes: G06V 30/19173 Classification techniques

Abstract

A classification method and apparatus for classifying an input into one of a plurality of possible outputs. Information representative of the input is compared to a neuron, where the neuron comprises a boundary defined by two or more neuron axes of different length. One of the possible outputs is then selected as corresponding to the input in accordance with that comparison. The invention is also a training method and apparatus for creating a new neuron or adjusting an existing neuron. A feature vector representative of a training input is generated, where the training input corresponds to one of a plurality of possible outputs. If no existing neuron corresponding to the training input encompasses the feature vector, then a new neuron is created, where the new neuron comprises a boundary defined by two or more neuron axes of different length. If the neuron encompasses the feature vector and if the neuron does not correspond to the training input, then the neuron is adjusted spatially, where the adjusted neuron comprises a boundary defined by two or more adjusted neuron axes of different length.

Claims

1. A classification method for classifying an input into one of a plurality of possible outputs, comprising the steps of:

(a) comparing information representative of said input to a neuron, wherein said neuron comprises a boundary defined by two or more neuron axes, wherein the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes; and

(b) selecting one of said possible outputs as corresponding to said input in accordance with the comparison of step (a), wherein;

step (a) comprises the step of comparing information representative of said input to a plurality of neurons;

each neuron of said plurality of neurons comprises a boundary defined by two or more neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said information representative of said input comprises a feature vector;

step (a) further comprises the step of selecting each neuron that encompasses said feature vector; and

step (b) further comprises the steps of;

(i) determining a first number that is a function of the number of said selected neurons that are associated with a first possible output of said plurality of possible outputs;

(ii) de. termining a second number that is a function of the number of said selected neurons that are associated with a second possible output of said plurality of possible outputs; and

(iii) if said first number is greater than said second number then determining that said input does not correspond to said second possible output, else if said second number is greater than said first number then determining that said input does not correspond to said first possible output.

2. The classification method of claim 1, wherein said input is representative of a character.

3. The classification method of claim 1, wherein said information representative of said input comprises a feature vector.

4. The classification method of claim 3, wherein said feature Vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

5. The classification method of claim 3, wherein step (a) comprises the step of determining whether said neuron encompasses said feature vector.

6. The classification method of claim 3, wherein step (a) comprises the step of determining a distance measure from said feature vector to said neuron.

7. The classification method of claim 1, wherein said neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

8. The classification method of claim 1, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to one of said feature-space axes.

9. The classification method of claim 1, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to none of said feature-space axes.

10. The classification method of claim 1, wherein said first number is equal to the number of said selected neurons that are associated with said first possible output, and said second number that is equal to the number of said selected neurons that are associated with said second possible output.

11. A training method for creating a new neuron in a feature space having at least one existing neuron, comprising the steps of:

(a) generating a feature vector representative of a training input, wherein said training input corresponds to one of a plurality of possible outputs;

(b) determining whether any existing neuron corresponding to said training input encompasses said feature vector; and

(c) creating said new neuron in accordance with the determination of step (b), wherein;

said new neuron comprises a boundary defined by two or more neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said feature space comprises an existing feature vector;

step (c) comprises the steps of;

(i) creating a temporary neuron comprising a boundary defined by two or more tempQrary neuron axes; and

(ii) if said temporary neuron encompasses said existing feature vector and said existing feature vector does not correspond to said training input then spatially adjusting said temporary neuron to create said new neuron; and

step (c)(ii) comprises the steps of;

(1) selecting at least one of said temporary neuron axes;

(2) calculating the distances along each of said selected temporary neuron axes from the center of said temporary neuron to said existing feature vector; and

(3) reducing said selected temporary neuron axes by amounts proportional to said distances and the lengths of said selected temporary neuron axes to create said new neuron.

12. The training method of claim 11, wherein said training input is representative of a character.

13. The training method of claim 11, wherein said information representative of said input comprises a feature vector.

14. The training method of claim 13, wherein said feature vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

15. The training method of claim 11, wherein said new neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

16. The training method of claim 11, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said neuron axes is parallel to one of said feature-space axes.

17. The training method of claim 11, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said neuron axes is parallel to none of said feature-space axes.

18. The training method of claim 11, wherein step (c)(ii)(1) comprises the step of selecting all of said temporary neuron axes.

19. The training method of claim 11, wherein step (c)(ii) comprises the steps of:

(1) selecting only one of said temporary neuron axes;

(2) calculating a distance in accordance with said selected temporary neuron axis and said existing feature vector; and

(3) reducing said selected temporary neuron axis by said distance to create said new neuron.

20. A training method for adjusting a neuron, comprising the steps of:

(a) generating a feature vector representative of a training input, wherein said training input corresponds to one of a plurality of possible outputs;

(b) determining whether said neuron encompasses said feature vector and whether said neuron does not correspond to said training input; and

(c) spatially adjusting said neuron in accordance with the determination of step (b), wherein;

said adjusted neuron comprises a boundary defined by two or more adjusted neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said neuron is in a feature space comprising an existing feature vector;

said neuron comprises a boundary defined by two or more neuron axes; and

step (c) further comprises the steps of;

(i) selecting at least one of said neuron axes;

(ii) calculating the distances along each of said selected neuron axes from the center of said neuron to said existing feature vector; and

(iii) reducing said selected neuron axes by amounts proportional to said distances and the lengths of said selected neuron axes to create said adjusted neuron.

21. The training method of claim 20, wherein said training input is representative of a character.

22. The training method of claim 20, wherein said information representative of said input comprises a feature vector.

23. The training method of claim 22, wherein said feature vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

24. The training method of claim 20, wherein said neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

25. The training method of claim 20, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said adjusted neuron axes is parallel to one of said feature-space axes.

26. The training method of claim 20, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said adjusted neuron axes is parallel to none of said feature-space axes.

27. The training method of claim 20, wherein step (c)(i) comprises the step of selecting all of said neuron axes.

28. The training method of claim 20, wherein step (c) comprises the steps of:

(i) selecting only one of said neuron axes; and

(ii) calculating a distance in accordance with said selected neuron axis and said existing feature vector; and

(iii) reducing said selected neuron axis by said distance to create said adjusted neuron.

57. The training method of claim 20, wherein step (c) comprises the step of spatially adjusting said neuron to exclude said feature vector.

29. A classification apparatus for classifying an input into one of a plurality of possible outputs, comprising:

comparing means for comparing information representative of said input to a neuron, wherein said neuron comprises a boundary defined by two or more neuron axes, wherein the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes; and

selecting means for selecting one of said possible outputs as corresponding to said input in accordance with the comparison by said comparing means;

wherein;

said comparing means compares information representative of said input to a plurality of neurons;

each neuron of said plurality of neurons comprises a boundary defined by two or more neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said information representative of said input comprises a feature vector;

said comparing means selects each neuron that encompasses said feature vector;

said selecting means determines a first number that is a function of the number of said selected neurons that are associated with a first possible output of said plurality of possible outputs;

said selecting means determines a second number that is a function of the number of said selected neurons that are associated with a second possible output of said plurality of possible outputs;

if said first number is greater than said second number, then said selecting means determines that said input does not correspond to said second possible output, else if said second number is greater than said first number, then said selecting means determines that said input does not correspond to said first possible output.

30. The classification apparatus of claim 29, wherein said input is representative of a character.

31. The classification apparatus of claim 29, wherein said information representative of said input comprises a feature vector.

32. The classification apparatus of claim 31, wherein said feature vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

33. The classification apparatus of claim 31, wherein said comparing means determines whether said neuron encompasses said feature vector.

34. The classification apparatus of claim 31, wherein said comparing means determines a distance measure from said feature vector to said neuron.

35. The classification apparatus of claim 29, wherein said neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

36. The classification apparatus of claim 29, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to one of said feature-space axes.

37. The classification apparatus of claim 29, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to none of said feature-space axes.

38. The classification apparatus of claim 29, wherein said first number is equal to the number of said selected neurons that are associated with said first possible output, and said second number that is equal to the number of said selected neurons that are associated with said second possible output.

39. A training apparatus for creating a new neuron in a feature space having at least one existing neuron, comprising:

generating means for generating a feature vector representative of a training input, wherein said training input corresponds to one of a plurality of possible outputs; and

creating means for creating said new neuron, if no existing neuron corresponding to said training input encompasses said feature vector, wherein;

said new neuron comprises a boundary defined by two or more neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said feature space comprises an existing feature vector;

said creating means creates a temporary. neuron comprising a boundary defined by two or more temporary neuron axes;

if said temporary neuron encompasses said existing feature vector and said existing feature vector does not correspond to said training input, then said creating means spatially adjusts said temporary neuron to create said new neuron;

said creating means selects at least one of said temporary neuron axes;

said creating means calculates the distances along each of said selected temporary neuron axes from the center of said temporary neuron to said existing feature vector; and

said creating means reduces said selected temporary neuron axes by amounts proportional to said distances and the lengths of said selected temporary neuron axes to create said new neuron.

40. The training apparatus of claim 39, wherein said training input is representative of a character.

41. The training apparatus of claim 39, wherein said information representative of said input comprises a feature vector.

42. The training apparatus of claim 41, wherein said feature vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

43. The training apparatus of claim 39, wherein said new neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

44. The training apparatus of claim 39, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said neuron axes is parallel to one of said feature-space axes.

45. The training apparatus of claim 39, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said neuron axes is parallel to none of said feature-space axes.

46. The training apparatus of claim 39, wherein said creating means selects all of said temporary neuron axes for said reduction.

47. The training apparatus of claim 39, wherein said creating means selects only one of said temporary neuron axes, said creating means calculates a distance in accordance with said selected temporary neuron axis and said existing feature vector, and said creating means reduces said selected temporary neuron axis by said distance to create said new neuron.

48. A training apparatus for adjusting a neuron, comprising:

generating means for generating a feature vector representative of a training input, wherein said training input corresponds to one of a plurality of possible outputs; and

adjusting means for spatially adjusting said neuron, if said neuron encompasses said feature vector and said neuron does not correspond to said training input, wherein;

said adjusted neuron comprises a boundary defined by two or more adjusted neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said neuron is in a feature space comprising an existing feature vector;

said neuron comprises a boundary defined by two or more neuron axes;

said adjusting means selects at least one of said neuron axes;

said adjusting means calculates the distances along each of said selected neuron axes from the center of said neuron to said existing feature vector; and

said adjusting means reduces said selected neuron axes by amounts proportional to said distances and the lengths of said selected neuron axes to create said adjusted neuron.

49. The training apparatus of claim 48, wherein said training input is representative of a character.

50. The training apparatus of claim 48, wherein said information representative of said input comprises a feature vector.

51. The training apparatus of claim 50, wherein said feature vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

52. The training apparatus of claim 48, wherein said neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

53. The training apparatus of claim 48, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said adjusted neuron axes is parallel to one of said feature-space axes.

54. The training apparatus of claim 48, wherein said feature space comprises two or more feature-space axes, and wherein at least one of said adjusted neuron axes is parallel to none of said feature-space axes.

55. The training apparatus of claim 48, wherein said adjusting means selects all of said neuron axes for said reduction.

56. The training apparatus of claim 48, wherein said adjusting means selects only one of said neuron axes, said adjusting means calculates a distance in accordance with said selected neuron axis and said existing feature vector, and said adjusting means reduces said selected neuron axis by said distance to create said adjusted neuron.

58. The training apparatus of claim 48, wherein said adjusting means spatially adjusts said neuron to exclude said feature vector.

59. A classification method for classifying an input into one of a plurality of possible outputs, comprising the steps of:

(a) comparing information representative of said input to a neuron, wherein;

said neuron comprises a boundary defined by two or more neuron axes; and

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes; and

(b) selecting one of said possible outputs as corresponding to said input in accordance with the comparison of step (a), wherein;

step (a) comprises the step of comparing information representative of said input to a plurality of neurons;

each neuron of said plurality of neurons comprises a boundary defined by two or more neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said information representative of said input comprises a feature vector;

step (a) further comprises the step of determining distance measures from said feature vector to each of said neurons; and

step (b) comprises the steps of;

(i) selecting a neuron of said plurality of neurons having the smallest distance measure of said distance measures; and

(ii) selecting a possible output of said plurality of possible outputs that is associated with said selected neuron as corresponding to said input.

60. The classification method of claim 59, wherein said input is representative of a character.

61. The classification method of claim 59, wherein said information representative of said input comprises a feature vector.

62. The classification method of claim 61, wherein said feature vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

63. The classification method of claim 61, wherein step (a) comprises the step of determining whether said neuron encompasses said feature vector.

64. The classification method of claim 61, wherein step (a) comprises the step of determining a distance measure from said feature vector to said neuron.

65. The classification method of claim 59, wherein said neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

66. The classification method of claim 59, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to one of said feature-space axes.

67. The classification method of claim 59, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to none of said feature-space axes.

68. A classification apparatus for classifying an input into one of a plurality of possible outputs, comprising:

comparing means for comparing information representative of said input to a neuron, wherein;

said neuron comprises a boundary defined by two or more neuron axes; and

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes; and

selecting means for selecting one of said possible outputs as corresponding to said input in accordance with the comparison by said comparing means, wherein;

said comparing means compares information representative of said input to a plurality of neurons;

each neuron of said plurality of neurons comprises a boundary defined by two or more neuron axes;

the length of at least one of said two or more neuron axes differs from the length of at least one other of said two or more neuron axes;

said information representative of said input comprises a feature vector;

said comparing means determines distance measures from said feature vector to each of said neurons;

said selecting means selects a neuron of said plurality of neurons having the smallest distance measure of said distance measures; and

said selecting means selects a possible output of said plurality of possible outputs that is associated with said selected neuron as corresponding to said input.

69. The classification apparatus of claim 68, wherein said input is representative of a character.

70. The classification apparatus of claim 68, wherein said information representative of said input comprises a feature vector.

71. The classification apparatus of claim 70, wherein said feature vector comprises a feature element, wherein said feature element is a Grid feature element or a Hadamard feature element.

72. The classification apparatus of claim 70, wherein said comparing means determines whether said neuron encompasses said feature vector.

73. The classification apparatus of claim 70, wherein said comparing means determines a distance measure from said feature vector to said neuron.

74. The classification apparatus of claim 68, wherein said neuron is a hyper-ellipse or a hyper-rectangle in k-dimensional feature space, where k is greater than or equal to two.

75. The classification apparatus of claim 68, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to one of said feature-space axes.

76. The classification apparatus of claim 68, wherein said neuron is in a feature space comprising two or more feature-space axes, wherein at least one of said neuron axes is parallel to none of said feature-space axes.