Implementing automatic learning according to the K nearest...

Details Implementing automatic learning according to the K nearest... Implementing automatic learning according to the K nearest...

1999-06-22

2002-04-23

Davis, George B. (Department: 2122)

Data processing: artificial intelligence

Neural network

Structure

Reexamination Certificate

active

06377941

ABSTRACT:

FIELD OF INVENTION
The present invention relates, generally, to neural networks and, more particularly, to a method and circuit for implementing automatic learning using the k nearest neighbor (KNN) mode (or algorithm) in artificial neural networks.
BACKGROUND OF INVENTION
Artificial neural networks (ANNs) are used with increased frequency in applications where no mathematical algorithm can describe the problem to be solved. Moreover, they have proven to be highly successful in classifying and recognizing objects. ANNs give excellent results because they learn by example and are able to generalize in order to respond to an input vector that was never present before. Thus far, most ANNs have been implemented in software and only a few in hardware. When implemented in software, no automatic learning is possible. This is one of the reasons why the tendency to date is to implement ANNs in hardware, typically in semiconductor chips. In this case, hardware ANNs are generally based on an algorithm known in the art as Region of Influence (ROI). The ROI algorithm gives good results if the input vector presented to the ANN can be separated into classes of objects well segregated from each other. When an input vector is recognized by neurons belonging to two different classes (or categories), the ANN will respond with an uncertainty. By way of example,
FIG. 1
shows two prototypes A and B with their respective actual influence fields (AIF) and categories ‘a’ and ‘b’ in a two-dimensional feature space. As apparent in
FIG. 1
, an input vector V falling in the hatched zone cannot be classified according to the ROI approach during the recognition phase because it is recognized by two prototypes that belong to different classes. In contradistinction to the K Nearest Neighbor (KNN) approach, an input vector V closer to prototype A will be assigned a class ‘a’. When operating in a KNN mode, the uncertainty is limited to a line, as depicted in
FIG. 1
instead of a surface, represented by the hatched zone.
Several neuron and artificial neural network architectures implemented in semiconductor chips are described in the following related patents:
U.S. Pat. No. 5,621,863 “Neuron Circuit”, issued on Apr. 15, 1997 to Boulet et al.;
U.S. Pat. No. 5,701,397 “Circuit for Pre-charging a Free Neuron Circuit”, issued on Dec. 23, 1997 to Steimle et al.;
U.S. Pat. No. 5,710,869 “Daisy Chain Circuit for Serial Connection of Neuron Circuits”, issued on Jan. 20, 1998 to Godefroy et al.;
U.S. Pat. No. 5,717,832 “Neural Semiconductor Chip and Neural Networks Incorporated Therein”, issued on Feb. 10, 1998 to Steimle et al.; and
U.S. Pat. No. 5,740,326 “Circuit for Searching/Sorting Data in Neural Networks”, issued on Apr. 14, 1998 to Boulet et al.;
all of which are incorporated herein by reference.
The ROI learning mode can be advantageously implemented in chips known as ZISC chips (ZISC is an IBM Corporation Trademark), because they incorporate a specific circuit, i.e., “Dmin determination circuit”, also referred to as a “minimum circuit”. Normally, the minimum circuit is designed to compute the minimum distance between the input vector and the prototypes stored in the neurons. Moreover, it is also adapted to identify which neuron computes the minimum distance.
The following description will be made in the light of the aforementioned U.S. patents, wherein the same terms and names of circuits will be kept whenever possible.
Several ZISC chips can be connected in parallel in order to reach the number of neurons needed for a given application defined by the user. All the neurons of the ANN compute the distance (e.g., the Manhattan distance) between the input vector to be recognized or learned and the prototypes stored in a Read/Write memory, typically a local RAM (Random Access Memory), implemented in each neuron.
FIG. 2
schematically shows a few neurons as part of an ANN, referenced
10
, and which illustrates the essence of a conventional ZISC chip architecture. Referring more specifically to
FIG. 2
, neurons
11
-
1
to
11
-N are fed in parallel by way of input bus
12
to enable communication with each other and with the external world. This is made possible through communication bus
13
. The latter terminates at the chip boundary, namely, at open drain drivers to make it possible, by dotting all chips, to extend the neural network from the chip to a card. Let it be assumed that neurons
11
-
1
and
11
-
2
are the last two active (i.e., engaged) neurons of the ANN, and
11
-
3
, the third neuron, is the first inactive (i.e., free) neuron thereof, i.e., not yet engaged by learning. As apparent from
FIG. 2
, the four main components of the neuron, e.g., neuron
11
-
1
, are a local RAM
14
-
1
which stores the components of the prototype; a distance evaluator circuit
15
-
1
which computes the distance (e.g. the Manhattan distance) between the input vector and the prototype; a minimum circuit
16
-
1
, which is required for ROI learning, as will be explained in more detail hereinafter and, finally, a daisy chain circuit
17
-
1
, which is serially connected to two adjacent neurons chaining the neurons of the ANN. The daisy chain circuit in essential; or determining the neuron state, i.e., whether it is free or engaged.
FIG. 3
shows the circuit of
FIG. 2
limited to neurons
11
-
1
and
11
-
2
, wherein only the elements that are dedicated to ROI learning (and recognition as well) are represented. Focusing now more particularly on neuron
11
-
1
, register
18
-
1
(which is integral to the RAM
14
-
1
of
FIG. 2
) is dedicated to store the category CAT. Comparator
19
-
1
compares the category stored in register
18
-
1
with the incoming category on input bus
12
in the learning phase, or the category obtained by ORing all the categories of the neurons which have fired and which appeared initially on communication bus
13
, and subsequently, on input bus
12
during the recognition phase. Comparator
20
-
1
compares the global context CXT to the neuron (or local) context CXT stored in register
21
-
1
. Comparator
20
-
1
generates an output signal which enables the selection of the minimum circuit of the neurons whose local context matches the global context. More details regarding minimum circuit
16
-
1
and daisy chain circuit
17
-
1
may be found in U.S. Pat. No. 5,717,832 to Steimle et al. (e.g., box
500
in
FIGS. 5 and 8
and their related description) and U.S. Pat. No. 5,710,869 to Godefroy et al. (e.g., box
150
in
FIGS. 5 and 16
and their related description), respectively. Signal ST is applied to all the daisy chain circuits of the ANN. The first free neuron is the one which has DCI and DCO signals in a complementary state. This complementary state is detected by an exclusive-OR circuit.
As apparent from
FIG. 3
, there is shown a further circuit, bearing numeral
22
, which corresponds to the identification circuit referenced
400
in
FIGS. 5 and 25
of the aforementioned U.S. Pat. No. 5,717,832. The function of logic block
22
is to generate a signal UNC (UNC stands for UNCertain) which is activated when an input vector cannot be classified with certainty. Still considering neuron
11
-
1
, the signal which is outputted from comparator
19
-
1
is applied to the first input terminal of 2-way XOR circuit
23
-
1
which receives the L signal (L stands for Learning) at the second input terminal. The output of the XOR circuit
23
-
1
is connected to a first input terminal of a 2-way AND gate
24
-
1
which receives the F signal (F stands for Fire) on its second input terminal. As apparent from
FIG. 3
, all the outputs of AND gates
24
-
1
,
24
-
2
, . . . of neurons
11
-
1
,
11
-
2
, . . . are connected to an N-way OR gate
25
. The signal UNC mentioned above is generated by OR gate
25
and is available to the external logic circuit
22
on pad
26
.
Still considering
FIG. 3
, the circuit operation during the recognition of an input vector when in the ROI mode will now be described. Two cases must be considered:
1) If only neurons belonging to the same category have fi

Affiliated with

Also associated with

Rating

Implementing automatic learning according to the K nearest... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Implementing automatic learning according to the K nearest..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementing automatic learning according to the K nearest... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2822062