Data processing: artificial intelligence – Neural network – Structure
Reexamination Certificate
1997-11-26
2001-09-11
Powell, Mark (Department: 2122)
Data processing: artificial intelligence
Neural network
Structure
C706S015000, C706S025000
Reexamination Certificate
active
06289329
ABSTRACT:
BACKGROUND AND SUMMARY OF THE INVENTION
The present invention relates generally to computer-implemented artificial intelligence systems. More particularly, the present invention relates to computer-implemented neural networks and expert systems.
Despite their success in diverse application domains for difficult classification tasks, feedforward networks are still viewed as black boxes by many users. This is due to the fact that the internal representation learned by a feedforward network for a classification task is not transparent, i.e. the knowledge embodied in network's numerical weights is not easily comprehensible. According to Minsky, this problem of internal representation of a trained network being opaque is a crucial problem as many real world applications often require multiple representation schemes for acquired knowledge (Minsky, M. “Logical versus analogical or symbolic versus connectionist or neat versus scruffy,”
AI Magazine
, Vol 12, pp 34-51, 1991). Furthermore, the users of neural networks are unable to gain better understanding of a classification task learned by a network when the knowledge acquired by a neural network through training remains incomprehensible.
To alleviate the problem of opacity, several schemes in the literature have been suggested. These schemes fall into one of two categories. The first category consists of schemes as discussed for example by Fu and by Gallant that attempt to explain the knowledge stored in connection weights of a trained network by a set of rules for explaining the output in terms of inputs (see, Fu, L. “Rule generation from neural networks,”
IEEE Trans. Systems, Man, and Cybernetics
, Vol 24, pp 1114-1124, 1994; and Gallant, S. I. “Connectionist Expert Systems,”
Comm. ACM
, Vol 31, pp 152-169, 1988). While these schemes make the transference of knowledge embodied in a network into another representation possible, they fail to bring out the internal representation learned by hidden units by stressing only the input-output behavior.
The second category of schemes are more focused on hidden units and try to bring out the features developed by internal units as a result of training. The Hinton diagram, which relies on a pictorial representation of connection weights to represent the concepts learned by internal neurons is an example of this category (see, Hinton, G. E. “Connectionist learning procedures,”
Artificial Intelligence
, Vol 40, pp 185-234, 1989).
The methods described by Saito and Nakano, as well as by Fu are based on a heuristic search which is conducted separately for positive and negative weights. (see, Saito, K. and Nakano, R. “Medical diagnostic expert system based on PDP model,”
Proc. IEEE Int'Conf. Neural Networks
, Vol I, pp 255-262, 1988; and Fu, L. “Rule generation from neural networks,”
IEEE Trans. Systems, Man, and Cybernetics
, Vol 24, pp 1114-1124, 1994). Moreover, these methods have a requirement of a set of training examples along with numerical weights in order to uncover the knowledge stored in a network.
The present invention overcomes these and other disadvantages found in previous approaches. The present invention extends the symbolic mapping to a multiple-valued logic (MVL) representation of a neuron. This extension to MVL representation is desirable due to several factors. First, multivalued inputs, e.g. the eye color attribute—brown, black, and blue, or the status of blood pressure—low, normal, and high, are natural in many applications, and thus MVL representation is the most appropriate representation. Second, MVL representation can be easily used to deal with continuous inputs by multilevel quantization. Third, multivalued logic provides a compact representation even for neurons with binary inputs by grouping several binary features into a single multivalued feature. Moreover, the present invention symbolic mapping process uncovers an algorithm learned by a network without worrying about the set of training examples that might have been used.
In accordance with the teachings of the present invention, a computer-implemented apparatus and method is provided for generating a rule-based expert system from a trained neural network which is expressed as network data stored in a computer-readable medium. The rule-based expert system represents an interconnected network of neurons with associated weights data and threshold data. A network configuration extractor is provided for accessing the network data and for ascertaining the interconnection structure of the trained neural network by examining the network data.
A transformation system is utilized to alter the algebraic sign of at least a portion of the weights data to eliminate differences in the algebraic sign among the weights data while selectively adjusting the threshold data to preserve the logical relationships defined by the neural network. A symbolic representation generator applies a sum-of-products search upon each neuron in the network to generate a multivalued logic representation for each neuron. A propagation mechanism combines the multivalued logic representation of each neuron through network propagation to yield a final logical expression corresponding to a rule-based expert system of the trained neural network.
The present invention utilizes the following expressions in order to accomplish the aforementioned operations. If x
i
is a multivalued variable which takes any value in the set P
i
={0,1, . . . p
i
−1}, then for any subset S
i
⊂
P
i
, x
i
S
i
is a literal of x
i
representing the function such that:
x
i
s
i
=
{
1
if
x
i
∈
S
i
0
if
x
i
∉
S
i
When S
i
≡P
i
, the value of the literal is always 1, and when S
i
≡Ø, the value of the literal is always 0. The complement of the literal, denoted as {overscore (x)}
i
S
i
, is defined as
{overscore (x)}
i
S
i
=x
i
P
i
−S
i
Additionally, a product of literals x
1
s
1
x
2
s
2
. . . x
n
s
n
is termed within the present invention a product. A multiple-valued input, binary-valued output function or simply a Boolean function is a mapping according to the following expression:
f
:
(
∏
i
n
P
i
)
→
B
where P
i
={0,1, . . . ,p
i
−1} and B={0,1}. A Boolean function expressed as a sum of product form is said to be in sop or disjunctive normal form (dnf).
The following expression for ƒ is an example of dnf representation with three variables x
1
,x
2
, and x
3
with P
1
={0,1}, P
2
={0,1,2}, and P
3
={0,1,2}.
ƒ=x
1
0
x
2
{1,2}
x
1
1
x
2
0
x
3
{0,1}
In the following fashion, ƒ can be written using complement of the second literal in the second product term.
ƒ=x
1
0
x
2
{1,2}
x
1
1
{overscore (x)}
2
{1,2}
x
3
{0,1}
The truth table for function ƒ is shown in Table 1.
TABLE 1
x
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
x
2
0
0
0
1
1
1
2
2
2
0
0
0
1
1
1
2
2
2
x
3
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
f
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
A multiple-valued input, multiple-valued output function is a mapping
f
:
(
∏
i
n
P
i
)
→
R
where P
i
={0,1, . . . ,p
i
−1} and R={0,1, . . . ,r−1}. A multiple-valued input, multiple-valued output function is expressed through r multiple-valued input, binary output functions, one function for each output state.
The multiple-valued logic provides a compact notation even for applications that essentially deal with binary logic. This feature of multivalued logic is used in designing programmable logic arrays with decoders. For example, consider the following function of three binary variables x
1
, x
2
, and x
3
:
ƒ=x
1
x
2
x
2
x
3
x
3
x
1
In this example, a multivalued variable y is defined which takes any value in the set {0,1,2,3} in such a way that value r implies r of the variables x
1
, x
2
, and x
3
are true. The above function ƒ can then
Sethi Ishwar K.
Yoo Jae H.
Harness & Dickey & Pierce P.L.C.
Khatri Anil
Powell Mark
LandOfFree
System for converting neural network to rule-based expert... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for converting neural network to rule-based expert..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for converting neural network to rule-based expert... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2471286