Artificial neural networks including Boolean-complete compartments

• US 6,052,679 A
• Filed: 09/11/1997
• Issued: 04/18/2000
• Est. Priority Date: 09/11/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aparicio, Manuel IV, Huang, Yen-Min
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): PENDER JR, MICHAEL J
• Application Number:
  US08/927,776
• Time in Patent Office: 950 Days
• Field of Search: 706/25, 706/26, 706/43, 706/41
• US Class Current: 706/15
• CPC Class Codes: G06N 3/063 using electronic means

Abstract

Artificial neural networks include a plurality of artificial neurons and a plurality of Boolean-complete compartments, a respective one of which couples a respective pair of artificial neurons. By providing Boolean-complete compartments, spurious complement memories can be avoided. A Boolean-complete compartment includes a collection of at least four Boolean functions that represent input vectors to the respective pair of artificial neurons. The collection of at least four Boolean functions are selected from sixteen possible Boolean functions that can represent input vectors to the respective pair of artificial neurons. A count for each of the at least four Boolean functions is also provided. The count represents a number of occurrences of each of the at least four Boolean functions in input vectors to the respective pair of artificial neurons. In order to read the artificial neural network, the network also includes a collection of transfer functions, a respective one of which is associated with a respective one the sixteen possible Boolean functions.

Claims

1. An artificial neural network comprising:

a plurality of artificial neurons; and

a plurality of Boolean-complete compartments, a respective one of which couples a respective pair of artificial neurons, wherein a respective Boolean-complete compartment comprises;

a collection of at least four Boolean functions that represent input vectors to the respective pair of artificial neurons, selected from sixteen possible Boolean functions that can represent input vectors to the respective pair of artificial neurons; and

a count for each of the at least four Boolean functions, representing a number of occurrences of each of the at least four Boolean functions in input vectors to the respective pair of artificial neurons.

2. An artificial neural network according to claim 1 wherein the count represents a count of ALWAYS functions included in the input vectors, a count of residual OR functions remaining in the input vectors after counting the ALWAYS functions, a count of residual two bit functions remaining in the input vectors after counting the ALWAYS and OR functions, and a count of residual AND functions remaining in the input vectors after counting the ALWAYS, OR and two bit functions.

3. An artificial neural network according to claim 1 further comprising:

means for selecting the collection of at least four Boolean functions that represent input vectors to a respective pair of artificial neurons and for accumulating a count for each of the selected functions; and

means for storing an indication of the selected collection of Boolean functions and the corresponding accumulated counts in the compartment that couples the respective pair of artificial neurons.

4. An artificial neural network according to claim 1 wherein each of the sixteen possible Boolean functions that can represent input vectors to the respective pair of artificial neurons is represented as a four bit bitwise OR of the input vectors.

5. An artificial neural network according to claim 3 wherein the collection of at least four Boolean functions is four Boolean functions.

6. An artificial neural network according to claim 1 wherein the collection of at least four Boolean functions is four Boolean functions.

7. An artificial neural network according to claim 3 wherein the selecting and accumulating means comprises:

first means for extracting a count of ALWAYS functions included in the input vectors;

second means, responsive to the first means, for extracting a count of residual OR functions remaining in the input vectors after extracting the count of ALWAYS functions;

third means, responsive to the second means, for extracting a count of residual two bit functions remaining in the input vectors after extracting the counts of ALWAYS and OR functions; and

fourth means, responsive to the third means, for extracting a count of residual AND functions remaining in the input vectors after extracting the counts of ALWAYS, OR and two bit functions.

8. An artificial neural network according to claim 3 wherein each of the sixteen possible Boolean functions that can represent input vectors to the respective pair of artificial neurons is represented as a four bit bitwise OR of the input vectors represented by the Boolean function, and wherein the selecting and accumulating means comprises:

first means for bitwise ANDing the at least four Boolean functions with an input vector;

second means, responsive to the first means, for identifying a largest Boolean function that is TRUE when bitwise ANDed with the input vector; and

third means, responsive to the second means, for decrementing the count of the largest Boolean function so identified and for incrementing the count of the next Boolean function following the largest Boolean function so identified.

9. An artificial neural network according to claim 1 further comprising a collection of transfer functions, a respective one of which is associated with a respective one of the sixteen possible Boolean functions.

10. An artificial neural network according to claim 9 further comprising:

means for reading the artificial neural network in response to an input vector, by combining the input vector, the counts and the associated transfer functions for the plurality of compartments.

11. An artificial neural network according to claim 10 wherein the reading means comprises means for calculating a dot product of an input vector to a respective pair of neurons, the transfer functions of the at least four Boolean functions of the compartment that is associated with the respective pair of neurons and the counts of the compartment that is associated with the respective pair of neurons.

12. An artificial neural network according to claim 11 wherein the reading means further comprises means, responsive to the calculating means, for averaging the dot products of the input vectors so calculated for the plurality of neurons.

13. An artificial neural network according to claim 1 further comprising means for encoding two bit input vectors to the respective pair of artificial neurons into a four bit representation in which only one bit is ONE.

14. An artificial neural network according to claim 13 wherein the encoding means comprises means for encoding a 00 input to the respective pair of artificial neurons as 0001, a 01 input as 0010, a 10 input as 0100 and an 11 input as 1000.

20. A method according to claim 14 further comprising the step of:

averaging the dot products of the input vectors so calculated for the plurality of artificial neurons.

29. A computer program product according to claim 1 wherein the collection of at least four Boolean functions is four Boolean functions.

15. A method of writing a plurality of input vectors into an artificial neural network comprising a plurality of artificial neurons, the writing method comprising the step of:

counting numbers of occurrences of at least four Boolean functions that represent a set of Boolean-complete functions in the input vectors for each pair of artificial neurons, wherein the counting step comprises the steps of;

extracting a count of ALWAYS functions included in the input vectors;

extracting a count of residual OR functions remaining in the input vectors after extracting the count of ALWAYS functions;

extracting a count of residual two bit functions remaining in the input vectors after extracting the counts of ALWAYS and OR functions; and

extracting a count of residual AND functions remaining in the input vectors after extracting the counts of ALWAYS, OR and two bits functions.

16. A method according to claim 15 wherein the at least four Boolean functions is four Boolean functions.

17. A method according to claim 15 wherein each of sixteen possible Boolean functions that can represent input vectors for each pair of artificial neurons is represented as a four bit bitwise OR of the input vectors represented by the Boolean function, and wherein the counting step comprises the steps of:

bitwise ANDing the at least four Boolean functions with an input vector;

identifying a largest Boolean function that is TRUE when bitwise ANDed with the input vector;

decrementing a count of the largest Boolean function so identified; and

incrementing a count of a Boolean function following the largest Boolean function so identified.

18. A method of reading an artificial neural network comprising a plurality of artificial neurons, in response to an input vector that is applied to the plurality of artificial neurons, the reading method comprising the step of:

combining the input vector, counts of at least four Boolean functions that are selected from sixteen possible Boolean functions that can represent input vectors to respective pairs of artificial neurons, the counts of at least four Boolean functions representing a number of occurrences of each of at least four Boolean functions in preceding input vectors to the respective pairs of artificial neurons, and transfer functions that are associated with the respective ones of the at least four Boolean functions.

19. A method according to claim 18 wherein the combining step comprises the step of:

calculating a dot product of an input vector to a respective pair of neurons, the transfer functions of the at least four Boolean functions that is associated with the respective pair of neurons and the counts of the at least four Boolean functions that is associated with the respective pair of neurons.

21. A method according to claim 18 wherein the combining step is preceded by the step of:

encoding two bit input vectors to a respective pair of artificial neurons into a four bit representation in which only one bit is ONE.

22. A method according to claim 21 wherein the encoding step comprises the step of encoding a 00 input to the respective pair of artificial neurons as 0001, a 01 input as 0010, a 10 input as 0100 and an 11 input as 1000.

23. A computer program product for providing an artificial neural network, the computer program product comprising a computer-readable storage medium having computer-readable program code means embodied in the medium, the computer-readable program code means comprising:

computer readable program code means for providing a plurality of artificial neurons; and

computer-readable program code means for providing a plurality of Boolean-complete compartments, a respective one of which couples a respective pair of artificial neurons, wherein a respective Boolean-complete compartment comprises;

computer-readable program code means for providing a collection of at least four Boolean functions that represent input vectors to the respective pair of artificial neurons, selected from sixteen possible Boolean functions that can represent input vectors to the respective pair of artificial neurons; and

computer-readable program code means for providing a count for each of the at least four Boolean functions representing a number of occurrences of each of the at least four Boolean functions in input vectors to the respective pair of artificial neurons.

24. A computer program product according to claim 23 wherein the count represents a count of ALWAYS functions included in the input vectors, a count of residual OR functions remaining in the input vectors after counting the ALWAYS functions, a count of residual two bit functions remaining in the input vectors after counting the ALWAYS and OR functions, and a count of residual AND functions remaining in the input vectors after counting the ALWAYS, OR and two bit functions.

25. An computer program product according to claim 23 further comprising:

computer-readable program code means for selecting the collection of at least four Boolean functions that represent input vectors to a respective pair of artificial neurons and for accumulating a count for each of the selected functions; and

computer-readable program code means for storing an indication of the selected collection of Boolean functions and the corresponding accumulated counts in the compartment that couples the respective pair of artificial neurons.

26. A computer program product according to claim 23 wherein each of the sixteen possible Boolean functions that can represent input vectors to the respective pair of artificial neurons is represented as a four bit bitwise OR of the input vectors represented by the Boolean function.

27. A computer program product according to claim 25 wherein the selecting and accumulating means comprises:

first computer-readable program code means for extracting a count of ALWAYS functions included in the input vectors;

second computer-readable program code means, responsive to the first means, for extracting a count of residual OR functions remaining in the input vectors after extracting the count of ALWAYS functions;

third computer-readable program code means, responsive to the second means, for extracting a count of residual two bit functions remaining in the input vectors after extracting the counts of ALWAYS and OR functions; and

fourth computer-readable program code means, responsive to the third means, for extracting a count of residual AND functions remaining in the input vectors after extracting the counts of ALWAYS, OR and two bit functions.

28. A computer program product according to claim 25 Wherein the collection of at least four Boolean functions is four Boolean functions.

30. A computer program product according to claim 25 wherein each of the sixteen possible Boolean functions that can represent input vectors to the respective pair of artificial neurons is represented as a four bit bitwise OR of the input vectors represented by the Boolean function, and wherein the selecting and accumulating computer-readable program code means comprises:

first computer-readable program code means for bitwise ANDing the at least four Boolean functions with an input vector;

second computer-readable program code means, responsive to the first means, for identifying a largest Boolean function that is TRUE when bitwise ANDed with the input vector; and

third computer-readable program code means, responsive to the second means, for decrementing the count of the largest Boolean function so identified and for incrementing the count of the next Boolean function following the largest Boolean function so identified.

31. A computer program product according to claim 23 further comprising computer-readable program code means for providing a collection of transfer functions, a respective one of which is associated with a respective one of the sixteen possible Boolean functions.

32. A computer program product according to claim 23 further comprising:

computer-readable program code means for reading the artificial neural network in response to an input vector, by combining the input vector, the counts and the associated transfer functions for the plurality of compartments.

33. A computer program product according to claim 32 wherein the reading means comprises computer-readable program code means for calculating a dot product of an input vector to a respective pair of neurons, the transfer functions of the at least four Boolean functions of the compartment that is associated with the respective pair of neurons and the counts of the compartment that is associated with the respective pair of neurons.

34. A computer program product according to claim 33 wherein the reading means further comprises computer-readable program code means, responsive to the calculating means, for averaging the dot products of the input vectors so calculated for the plurality of neurons.

35. A computer program product according to claim 23 further comprising computer-readable program code means for encoding two bit input vectors to the respective pair of artificial neurons into a four bit representation in which only one bit is ONE.

36. A computer program product according to claim 35 wherein the encoding means comprises computer-readable program code means for encoding a 00 input to the respective pair of artificial neurons as 0001, a 01 input as 0010, a 10 input as 0100 and an 11 input as 1000.