`
`SAMSUNG EXHIBIT 1006
`Samsung v. Image Processing Techs.
`
`
`
`U.S. Patent
`
`Aug. 24, 1993
`
`Sheet 1 of 10
`
`5,239,594
`
`~~
`
`2.
`
`Fig./
`
`(PRIOR ART)
`
`INPUT
`
`TRANSDUCER
`
`
`Fig2
`
`(PRIOR ART)
`
`Fig.3
`
`(PRIOR ART)
`
`Fig.4
`(PRIOR ART)
`
`Fig.5
`
`(PRIOR ART)
`
`
`* €
`
`
`
`7
`
`FEATURE
`
`EXTRACTOR
`
`
`aE
`
`KS
`
`
`\
`
`
`NO,OFSAMPLES
`
`
`
`GRAINPROMINENCEFo
`
`BRIGHTNESS Fy
`
`SAMSUNG EXHIBIT 1006
`Page 2 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 2 of 17
`
`
`
` oo(ONINVLJim9~T/uy=StonnatyFyOLos713s|yeni]|\P|
`Sunlvad aunivsd
`
`tYOLOVELX
`
`OY
`
`LNGNI
`
`YSONGSNVYL
`
`gOly
`
`U.S. Patent
`
`Aug. 24, 1993
`
`Sheet 2 of 10
`
`5,239,594
`
`WNOIS
`
`
`
`Z/
`
`»YOLOVYLXS
`
`-eZ|
`
`SAMSUNG EXHIBIT 1006
`Page 3 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 3 of 17
`
`
`
`
`US. Patent
`
`Aug. 24, 1993
`
`Sheet 3 of 10
`
`5,239,594
`
`Fig.7
`
`fit
`fi2
`
`fij
`
`SELF-
`ORGANIZING
`CLASSIFIER
`
`fiN
`
`
`mM CORRECTcass47
`
`29
`
` gienaL
`
`SAMSUNG EXHIBIT 1006
`Page 4 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 4 of 17
`
`
`
`U.S. Patent
`
`Aug. 24, 1993
`
`Sheet 4 of 10
`
`5,239,594
`
`Fig.9 CORRECT
`
`Ls
`23
`
`CLASS
`SIGNAL
`
`SAMSUNG EXHIBIT 1006
`Page 5 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 5 of 17
`
`
`
`U.S. Patent
`
`Aug. 24, 1993
`
`Sheet 5 of 10
`
`5,239,594
`
`
`
`SAMSUNG EXHIBIT 1006
`Page 6 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 6 of 17
`
`
`
`U.S. Patent
`
`Aug. 24, 1993
`
`Sheet 6 of 10
`
`5,239,594
`
`Figle
`
`24
`
`fn
`
`fi
`
`fj
`
`Fig. 13
`
`
`
`SAMSUNG EXHIBIT 1006
`Page 7 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 7 of 17
`
`
`
`U.S. Patent
`
`—
`
`Aug. 24, 1993
`
`Sheet 7 of 10
`
`5,239,594
`
`Fig/A
`
`Pe | 49
`CLASS ©
`|
`SELECTOR[|
`
`
`
`| |
`
`Is
`
`(al
`P
`
`||| |{
`
`|
`|
`
`|
`
`|{
`
`l
`|
`|
`|
`|
`
`)
`
`|
`|
`|
`|
`|
`
`riM
`
`riM
`
`;
`
`(7
`™
`
`|||| i
`
`#le
`CORRECT CLASS
`SIGNAL
`
`LEARNING
`TRIGGER
`
`oa
`Tr
`
`SAMSUNG EXHIBIT 1006
`Page 8 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 8 of 17
`
`
`
`U.S. Patent
`
`Aug. 24, 1993
`
`Sheet 8 of 10
`
`5,239,594
`
`
`
`SAMSUNG EXHIBIT 1006
`Page 9 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 9 of 17
`
`
`
`US. Patent
`
`Aug. 24, 1993
`
`Sheet9 of 10
`
`5,239,594
`
`Fig I6
`
`
`
`ARITHMETIC
`UNIT
`
`RAM
`(TEMPOLARY)
`
`
`
`SAMSUNG EXHIBIT 1006
`Page 10 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 10 of 17
`
`
`
`U.S. Patent
`
`Aug. 24, 1993
`
`Sheet 10 of 10
`
`5,239,594
`
`PIgIr
`
`INPUT TRANSDUCER GENERATES S
`
`DETERMINE FEATURE VECTORS
`
`GENERATE RESPONSE VECTORS
`
`DETERMINE OUTPUTS T1,T2... TM
`
`62
`
`63
`
`64
`
`65
`
`DETERMINE Cmini, Cmin2,Tmin! AND Tmin2
`
`LEARNING MODE
`
`INPUT TRAINING SIGNAL
`
`NO
`
`
`
`
`TRANSFER CORRECT CLASS TO
`SELF-ORGANIZING CLASSIFIERS
`
`
`
`
`MODIFY WEIGHTING VECTORS
`IN SEQUENCE
`
`
`7/
`
`YES
`
`SAMSUNG EXHIBIT 1006
`Page 11 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 11 of 17
`
`
`
`1
`
`5,239,594
`
`SELF-ORGANIZING PATTERN CLASSIFICATION
`NEURAL NETWORK SYSTEM
`
`This application is a continuation of application Ser.
`No. 654,424, filed Feb. 12, 1991, now abandoned.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention relates generally to pattern
`classification systems and, more particularly, to a com-
`pound pattern classification system using neural net-
`works whichis able to vary a response signal by learn-
`ing from repeatedly input pattern signals to provide
`correct classification results.
`2. Description of the Prior Art
`Pattern classification systems, such as character or
`voice recognition systems, separate and identify classes
`of incoming pattern signals. FIG. 1 shows a conven-
`tional pattern classification system such as described by
`Richard O. Duda and Peter E. Hart in Pattern Classifi-
`cation and Scene Analysis, Wiley-Interscience Publish-
`ers, pp. 2-4. This classification system includes an input
`transducer 1, such as a television camera, which per-
`forms opto-electronic conversion of characters to gen-
`erate pattern signals S providing characteristic informa-
`tion about the characters. The system further includes a
`feature extractor 2 which receives the pattern signals S
`and generates feature vectors F useful for classifying
`the characters. The system is also provided with a clas-
`sifier 3 which classifies the characters and generates
`classification responses P based on the distributions of
`the feature vectors F. In order to make suchclassifiers,
`pattern recognition techniques, such as a linear discrimi-
`nation method, have been developed. However, the
`classification systems using these techniques are unable
`to learn by adjusting classes to account for new input
`patterns or to create new classes. Consequently, it is
`necessary to manually develop the informationfor clas-
`sifying pattern signals and manually incorporate the
`information into the system. This manual development
`and incorporation diminishes the efficiency of the sys-
`tem and provides another potential source forerror(i.e.
`humanerror).
`In order to solve this problem, manyself-organizing
`pattern classifiers have been proposed whichareable to
`organize themselves correctly to separate a given num-
`ber of pattern signals into their classes. An example of a
`self-organizing pattern classifier is that which make use
`of a back propagation learning method such as shown
`by Richard P. Lippmann in “An Introduction to Com-
`puting with Neural Nets,” IEEE ASSP Magazine,
`April 1987, Vol. 4, No. 2, pp. 4-22. The back propaga-
`tion technique is an iterative gradient algorithum that
`seeks to minimize the mean square error between actual
`output and desired output. Another example ofa self-
`organizing pattern classifier is the learning vector quan-
`tization 2 technique such as shown by Teuvo Kohonen,
`Gyorgy Barna, and Ronald Chrisley, “Statistical Pat-
`tern Recognition with Neural Networks: Benchmark-
`ing Studies,” Proceedings of IEEE International Confer-
`ence on Neural Networks, Jul. 24-27 1988, Vol. 1, pp.
`61-68.
`These self-organizing pattern classifiers suffer the
`drawback that when they make a wrongclassification,
`they modify the information about stored weighting
`data to attempt to yield more accurate results. FIG. 2
`showsthe distributions of two classes C4 and Cg ina
`
`15
`
`20
`
`25
`
`35
`
`40
`
`45
`
`55
`
`65
`
`2
`two dimensional vector space defined by feature axes
`X1 and X2. The above self-organizing classifiers are
`able to make correct boundaries 9 by using the back
`propagation learning method or learning vector guanti-
`zation 2 technique (referenced above) to separate the
`two classes C4 and Cp.
`Aslong as the distributions of the respective feature
`vectors F, each consisting of N elements f1, f2,..., fN,
`do not overlap each other, the aboveclassifiers are able
`to learn to provide correctclassification with high clas-
`sification rates. However, as FIG. 3 shows, when the
`distributions 10 and 11 of the feature vectors F of two
`classes C4 and Cgoverlap each other in an area 12, none
`of the above learning techniques make it possible to
`separate these two classes.
`Whena large numberof classes are identified, such as
`are used withclassifying Chinese characters, it is rare
`for a feature vector of a given class to not overlap with
`feature vectors of otherclasses (hereinafter such feature
`vector will be referred to as a “single aspect feature
`vector”). Thus,
`the above described self-organizing
`classifiers which have ‘been designed for single aspect
`feature vectors fail to provide high recognition rates for
`multiple aspect feature vectors.
`One approach to overcoming this problem of over-
`lapping feature vectors of different classes is to utilize
`multiple features. FIG. 4 provides an example wherein
`a single feature is used. In particular, it shows the distri-
`butions 13 and 14 ofbrightness features F1 for ash wood
`and birch wood respectively, as described in Pattern
`Classification and Scene Analysis, at pp. 2-4. FIG. 5
`provides an example wherein multiple features are used.
`FIG. 5 showsthe distributions 15 and 16 of ash wood
`and birch wood,
`respectively, with respect
`to the
`brightness feature F1 and the grain prominencefeature
`F2. In FIG. 4, there is a large overlapping area in the
`brightness feature F1 of the ash wood 13 and the birch
`wood 14, As such, it is impossible to make correct clas-
`sification using only the brightness feature F1. How-
`ever, as shownin FIG.5, by using both the brightness
`feature F1 and the grain prominence feature F2,it is
`possible to classify these two objects correctly. In this
`way, by inputting two or more feature vectors, the use
`of multiple features does not suffer the drawback de-
`scribed abovefor single feature approaches.
`However, a drawback with the use of multiple fea-
`ture vectors is that the features of feature vectors F1,
`F2,..., FN (where N is a positive integer) are not
`generally related. As a result, not only large areas of
`memory but also large amounts of computing time are
`necessary to input the N feature vectors F1, F2,..., FN
`into the self organizing pattern classifier. For example,
`suppose that there are no relations among the three
`feature vectors F1, F2, and F3 which are used to iden-
`tify an object A. Further suppose that the object A has
`four different instances F11, F12, F13, and F14 of the
`feature vector F1, four different instances F21, F22,
`F23, and F24 at the feature vector F2, and four different
`instances F31, F32, F33, and F34 of the feature vector
`F3. Then, it is possible to represent the object A by
`using a vector F as follows:
`
`F=({Fli, F2j, F3k)}
`
`there are 64 (i.e.
`wherein i, j, k=1, 2, 3, 4. Thus,
`4x44) different instances, and 192(i.e. 64> 3) vectors
`are required to represent the object A.
`
`SAMSUNG EXHIBIT 1006
`Page 12 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 12 of 17
`
`
`
`3
`Accordingly, it is an object of the invention to pro-
`vide a compound self-organizing pattern classification
`system that effectively utilizes a plurality of different
`feature vectors.
`It is another object of the invention to provide a
`compoundself-organizing pattern classification system
`which is able to classify pattern signals with accuracies
`higher than those of respective pattern classifiers by
`making compoundclassification based on the outputs of
`a numberof independentself-organizing pattern classifi-
`ers into which a numberofdifferent feature vectors are
`input.
`
`SUMMARYOF THE INVENTION
`
`Accordingto the present invention,a self-organizing
`pattern classification neural network system classifies
`incoming pattern signals into classes. The system in-
`cludes feature extractors for extracting different feature
`vectors from an incomingpattern signal. For instance,if
`the inputis visual data focusing on a piece of wood,the
`feature extractors might extract the features of grain
`prominence and brightness from the visual data. The
`feature extractors are coupledto self-organizing neural
`networkclassifiers. A separate neural networkclassifier
`is provided for each ofthe feature extractors. The clas-
`sifiers receive the feature vectors and generate response
`vectors comprising a plurality of responsive scalars
`corresponding to the respective classes. The response
`scalar is forwarded to a discriminator which receives
`the response vectors for each class and generates a
`classification response. The classification response in-
`cludes information indicative of whether a classification
`is possible and also information indicating an identified
`class. Lastly, the system includes a learning trigger for
`transferring a correctclass signal to theself-organizing
`classifiers based on a class of the training signal and
`based on theclassification response.
`It is preferred that each self-organizing classifier is
`comprised of a neural networks having input nodes for
`receiving feature scalars of each of the feature vectors
`and a plurality of intermediate nodes for receiving the
`feature scalars for said input node. The intermediate
`nodes also generate a plurality of intermediate outputs
`that are received by output nodes of a given class.
`Hence, the intermediate nodesofa particular class are
`all coupled to a single output node. The output node
`determines a smallest
`intermediate output amongst
`those received from the intermediate node.It transfers
`this intermediate output to the discriminator as a re-
`sponse scalar. Theclassifier also includes a self-organiz-
`ing selector for receiving the smallest intermediate out-
`put and a node numberof said intermediate node which
`gives the smallest intermediate output. The self-organiz-
`ing selector determines a weight update signal based on
`the node number and intermediate output from this
`intermediate node. It also determines the correct class
`signal.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG.1 is a block diagram of a conventional pattern
`classification system;
`FIG. 2 is a plot illustrating how conventional ap-
`proaches can distinguish between non-overlapping
`classes.
`FIG. 3 is a plotillustrating how conventional ap-
`proaches
`cannot distinguish between overlapping
`classes.
`
`-_0
`
`30
`
`40
`
`45
`
`55
`
`65
`
`5,239,594
`
`4
`FIG. 4 is a plot of histograms of brightness of ash
`wood versus birch wood.
`FIG.Sisaplot illustrating how thefeatures ofbright-
`ness and grain prominence together accurately distin-
`guish between ash wood and birch wood.
`.
`FIG.6 is a block diagram ofa self-organizing pattern
`classification neural network system according to an
`embodimentof the invention.
`FIG.7 is an input output diagram ofa self-organizing
`pattern classifier useful for the classification system of
`FIG.6.
`FIG.8 is a block diagram of the self-organizing pat-
`tern classifier of FIG.7.
`FIG.9 is a block diagram of an intermediate node of
`the classification system of FIG.8.
`FIG.10 isan example of a block diagram of theself-
`organizing classifier of FIG.8.
`FIG.11 is a plot of a vector space illustrating inter-
`mediate nodes for two different classes.
`FIG.12 is a block diagram of a self-organizing classi-
`fier in which a new intermediate nodeis added.
`FIG.13 is a graph illustrating an example wherein
`templates for different classes are too closely situated.
`FIG.14 is a block diagram of a discriminator useful
`for the classification system of FIG. 6.
`FIG. 15 is a block diagram of a class summing node
`useful for the discriminator of FIG. 14.
`FIG.16 is a block diagram of a compoundself-organ-
`izing pattern classification neural network system using
`a sequential digital computer according to an embodi-
`mentof the invention.
`FIG. 17 is a flowchart useful for explaining operation
`of the classification system of FIG. 16.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`In accordance with a preferred embodiment of the
`present invention depicted in FIG.6, a self-organizing
`pattern classification neural network system includes an
`input transducer 1, K feature extractors 2 (where K is a
`positive integer), K self-organizing classifiers 17, a dis-
`criminator18; and a learningtrigger 19, all of which are
`interconnected as shown.
`The neural network system operates in either a classi-
`fication mode wherein pattern signals are classified or a
`learning mode wherein the weighting vectors stored in
`the self-organizing classifiers 17 are modified.
`In the classification mode,
`the input transducer 1
`generates pattern signal vectors S which represent the
`object to be classified. For example, when a printed
`character on paper is to be classified, the input trans-
`ducer 1 generates, by opto-electronic conversion a pat-
`tern signal vector S of a bit-mapped image. In this bit-
`mappediimage, pixel locations wherethe letter located
`is represented by values of“1” whereas the other pixel
`locations are represented by values of “0”.
`.
`Thepattern signal vector S is then transferred to the
`K feature extractors 2 in parallel. The K feature extrac-
`tors 2 generate K different feature vectors F1, F2,...,
`Fk from the pattern vector S. These feature vectors
`vary with the object to be identified. The objects to be
`identified may include characters or voices. The feature
`vectors are generated by using techniques well known
`in the prior art. In the character recognition field, for
`example, a characteristic loci or crossing add distance
`feature may be extracted as a feature vector F by em-
`ploying the technique described in C. Y. Suen, M.
`Berthod, and S. Mori in “Automatic Recognition of
`
`SAMSUNG EXHIBIT 1006
`Page 13 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 13 of 17
`
`
`
`5,239,594
`
`R={ril, ri2,..., ri26}
`
`20
`
`25
`
`30
`
`45
`
`55
`
`60
`
`65
`
`6
`5
`Handprinted Characters—the State of the Art,” Pro-
`32. The weight update signal 29 is based on the number
`ceedings of IEEE, Vol. 68, No. 4, April 1980, pp.
`i the output Oiof the intermediate node and the correct
`469-487,
`class signal L 23 supplied from outside.
`The K feature vectors Fl, F2,..., FK are then
`FIG. 9 shows a more detailed view of intermediate
`transferred to the correspondingKself-organizing clas-
`node Ui. Ui includes N element comparators 34, each
`sifiers 17. As FIG. 7 shows,
`the i-th self-organizing
`having a weighting scalar Wil, Wi2,..., WiN of a
`classifier 17 receives a feature vector Fi composed of N
`weighting vector Wi, that is compared with a corre-
`feature scalarsfil, fi2,..., fiN and generates a response
`sponding elementof the feature vector F by the element
`vector Ri composed of M response scalars ril, ri2,...,
`comparator. Theresults of the comparison indicate the
`riM. These M responsescalarsril, ri2,... , riM corre-
`difference between the weighting vector and the feature
`spond to M classes, and a response scalar rij indicates
`vector. The intermediate node Uialso includes an adder
`how far apart the pattern signal S is from the class Cj-in
`35 for summing the results of comparison performed by
`terms of the feature vector Fi. For example, when 26
`an element comparator34 via signal lines 37. Lastly, the
`Arabic characters “A” through “Z”are classified, the
`intermediate node Ui 25 includes a square root com-
`response vector R is composed of 26 responsescalars.
`puter 36 for calculating the square root of summed
`results produced by the adder 35. The square root com-
`puter receives the summed results over a signal line 38.
`In operation, the self-organizing classifier 17 receives
`, ri26 indicate how remote the
`.
`.
`.
`wherein ril, ri2,
`a feature vector F composed of N feature scalars fl, f2,
`pattern signal is from the respective letters “A”, “B”, .
`...,{£N and generates a response vector Ri composed of
`.., “Z”. The K response vectors R12, R2,..., RK of the
`K self-organizing classifiers 17 are then transferred to
`M response scalars ril, ri2,..., riM which correspond
`to the M classes to be separated. Morespecifically, the
`the discriminator 18, wherein the linear sum of response
`scalars rli, r2i, ..., rki of response vectors R1, R2...Rk
`input nodes 24 receive the N feature scalarsfl, f2,...,
`fN of a feature vector F from the feature extractor 2.
`corresponding to a class Ci is taken to determinetotal
`outputs T1, T2,..., TM for classes C1, C2,..., CM.
`The intermediate nodes 25 generate an intermediate
`Theclass which gives the smallest total output is deter-
`output 28 based on the feature vector F and the
`mined by the discriminator 18 and output asaclassifica-
`weighting vectors of the element comparators 34. This
`tion result P 21.
`is accomplished by matching the weighting vectors
`stored in the intermediate node 25 and the feature vec-
`In the learning mode,a classification result P 21 is
`determined in the same way as in the classification
`tor F as described below. Thatis, the weighting vectors
`mode. As FIG. 6 shows,the classification result P 21 is
`stored in the element comparators 34 of the intermedi-
`then transferred to the learning trigger 19, wherein
`ate node 25 function as a template which represents the
`whethera correct class signal L 23 is transferred to the
`features ofa letter.
`self-organizing classifiers 17 is determined based on the
`For example, the intermediate output Oi of the i-th
`classification result P 21 and a training signal Tr 22
`intermediate node Uiis given by the following expres-
`whichis externally supplied by the user. If the correct
`sion:
`class signal L 23is transferred, the correct class given
`by the training signal Tr 22 is transferred to all of the
`self-organizing classifiers 17, wherein the correct class
`signal L 23 is compared with the output at each output
`node for modifying the weighting vectors therein.
`FIG. 8 depicts the self organizing classifier in more
`detail. A suitable classifier is described in copending
`patent application, “Self-organizing Neural Network
`for Pattern Classification”, Ser. No. 07/654,800. This
`copending application has the same inventor, the same
`assignee and was filed on even date herewith as the
`present application. The self-organizing classifier 17
`includes N (where N is a positive integer) input nodes
`24 functioning as buffers for receiving N feature scalars
`fl, f2,..., fN of a feature vector F. The classifier 17 also
`includes intermediate nodes 25, each receiving an N-
`dimensional feature vector F from the N input nodes 24
`via N signal lines 30 and generating an intermediate
`output 28. The classifier 17 additionally includes M
`(where M is a positive integer) output nodes 26, each
`receiving intermediate outputs from the intermediate
`nodes 25of a class via signal lines 31. Each output node
`26 determines the smallest output among thoseit re-
`ceives and transfers the node numberi of the intermedi-
`ate node that sent the smallest output along with the
`smallest output Oi to the self-organizing selector 27 via
`signal lines 33B. The node numberand output value are
`also sent to the discriminator 18 via a signal line 33A as
`a response scalar ri of a response vector R. Theclassi-
`fier 17 further includes a self-organizing selector 27 for
`generating a weight update signal 29 for updating tem-
`plates encoded in the intermediate nodes onsignal lines
`
`whereinfj is the j-th feature scalar of the feature vector
`F and Wij is the j-th weighting scalar stored in the i-th
`intermediate node Ui.
`The intermediate output Oi is computed in the inter-
`mediate node Ui as shownin FIG.9. Thatis, the differ-
`ence between each feature scalar fj of the feature vector
`F and each weighting scalar Wij of the weighting vec-
`tor stored in the intermediate node Ui is squared in the
`element comparator 34. The computed results are trans-
`ferred to the adder 35 via the signal lines 37. The square
`root computer 36 computes the square root of the sum-
`ming result from the summer 35 and transfer the inter-
`mediate output Oi via the signal line 31 to the output
`node 26 of the class represented by the intermediate
`node Ui.
`Since the weighting vectors functioning as a template
`representative of each class are stored in the intermedi-
`ate node 25, the numberof intermediate nodes is greater
`than that of the classes to be separated. In other words,
`there are two or more intermediate nodesfor each class,
`indicating the distribution of feature vectors ofthe class.
`These intermediate nodes are comparable to templates
`of the multitemplate technique known. in the pattern
`recognitionfield. That is, the output Oi of the i-th inter-
`mediate node Ui corresponds to the matching between
`
`| N
`Oi = 1/N (3, 0-m)
`
`a)
`
`SAMSUNG EXHIBIT 1006
`Page 14 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 14 of 17
`
`
`
`5,239,594
`
`8
`rect class, the self-organizing selector 27 carries out the
`following process:
`It is determined whether the output Oj of the inter-
`mediate node Uj of a class which is identical with the
`correct class satisfies the following expression:
`
`7
`the feature vector F and the template represented by the
`weighting vector Wi, indicating the Euclidian distance
`between the feature vector F and the template in the
`vector space. Consequently, the smaller the intermedi-
`ate output Oi, the closer the feature vector F and the
`template represented by the weighting vector Wi.
`The output node 26 selects an intermediate node
`which gives the smallest intermediate output amongthe
`intermediate nodes 25 of the class and transfers a re-
`sponse scalar of the response vector R 20 to theself-
`organizing selector 27 via the signal line 33B.
`FIG. 10 showsa self organizing classifier 17 for re-
`ceiving a 2-dimensional feature vector Fx={fx1, fx2}
`and separating two classes C4 and Cg. Intermediate
`nodes Ua1, Ua2, Ua3, and Uss, and Ugi, Ug, and Ug3
`represent respective classes C4 and Cg: Output nodes
`Vaand Vz represent these classes C4 and Cg. As FIG.
`11 shows, when the feature vector Fx is inputted to the
`self-organizing classifier 17,
`the intermediate outputs
`Oi, O42, O43, and Ox4, and Og, Ox, and Og; are
`computed according to the aforementioned expression
`(1),
`indicating the respective distances between the
`feature vector F and the templates represented by the
`weighting vectors of the respective intermediate nodes.
`The output node V4 of the class C4 selects the smallest
`output O,) as a representative of the class and transfers
`it as an element rl of response vector R to the discrimi-
`nator18. it also transfers the node number “AJ”and the
`output O,; to the self-organizing selector 27. The out-
`put node Vz ofthe class Cg selects the smallest output
`Ojpzas a representative of the class Cg and transfers it as
`an element r2 of response vector R to the discriminator
`18, and the node number “‘B2”and the output Og to the
`self organizing selector 27.
`the
`27 modifies
`The
`self-organizing
`selector
`weighting vectorin the intermediate node based on the
`correct class signal L supplied by learning trigger 19.
`More specifically, upon receipt of the correct class
`signal L 23, the self-organizing selector 27 selects, as a
`response signal, the class corresponding to the smallest
`intermediate output among the intermediate outputs
`representing respective classes. It then compares the
`class of the smallest intermediate output with the class
`given by the correct class signal L 23.
`If the class of the response signal is identical with the
`class of the correct class signal L 23, the self-organizing
`classifier is determined to makea correctclassification,
`and no modification is made to the weighting vectors in
`the intermediate node.
`If the class of the response signalis different from the
`class of the correct class signal L 23, on the other hand,
`the self-organizing classifier modifies the weighting
`vectors of the intermediate node depending on whichof
`the following causes for the incorrect classification
`brought about incorrect classification:
`(1) the incoming pattern signal was very remote from
`the template represented by the weighting vector of the
`intermediate node of the correct class in the vector
`space;
`(2) there is a weighting vector of an intermediate
`node, having a class other than the correct class, which
`is very close in the vector space to the weighting vector
`in the intermediate node of the correct class; and
`(3) none of the above.
`If there does not exist an output nodeofa class identi-
`cal with the correct class, a warning messageis output-
`ted, and the learning process is terminated. If there
`exists an output node ofa class identical with the cor-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`‘55
`
`60
`
`65
`
`OjZthi
`
`(2)
`
`wherein th1 is a predetermined threshold constant. For
`more information on th1, see the copending patent ap-
`plication entitled “Self-organizing Neural Network for
`Pattern Classification” referenced above. The expres-
`sion (2) indicates that the Euclidian distance in a vector
`space between the feature vector and the template rep-
`resented by the weighting vector of an intermediate
`node Uj ofthe correct class is greater than or equal to
`thi. A large value is used for the constant th1. If the
`condition is satisfied, it means that an incoming feature
`vector is very remote in the vector space from the tem-
`plate represented by the weighting vector of an inter-
`mediate node of the correct class which has been regis-
`tered. Consequently, if the condition is satisfied, a new
`network consisting of an intermediate node 39, N signal
`lines 40 for connecting the input nodes 24 to the inter-
`mediate node 39, and a signal line 41 for connecting the
`intermediate node 39 to the output node 26 of the cor-
`rect class are added to the network as shownin FIG.12.
`The weighting vector of the intermediate node 39 is
`realized by assigning the N scalars fl, f2,...fN of the
`feature vector F as the elements of the weighting vec-
`tor.
`If the expression (2) is not satisfied, the smallest out-
`put Oi among the intermediate outputs for the respec-
`tive output nodes is determined. The intermediate node
`Ui that produced the smallest output Oi is also deter-
`mined. The output Oj of an intermediate node Uj of a
`class obtained from the output node ofthe correct class
`is also determined. Then,it is determined whether these
`two outputs Oi and Oj satisfy the following expression:
`
`Oj—-OiZth2
`
`(3)
`
`wherein th2 is a predetermined threshold constant. For
`more information on th2, see copending patent applica-
`tion entitled “Self-organizing Neural Network for Pat-
`ten Classification”. If expression (3) is satisfied,
`the
`classification results are incorrect due to the template
`represented by the weighting vectorin the intermediate
`node Uj of the correct class being close to the template
`of Ui of the wrong class. In this case, the weighting
`vectors of the intermediate nodes Ui and Uj are modi-
`fied according to the following expressions:
`
`Weight of Ui: Wik= Wik—af[fk— Wik] for k=1,...
`N
`
`Weight of Uj: Wik= Wjk + a[fk—Wjk] fork=1,...
`N (4)
`
`wherein fk is the k-th feature scalar of the feature vector
`F, Wik is the k-th scalar of the weighting vectorin the
`i-th intermediate node Ui, and a is a sufficiently small
`positive real number. a is described in moredetail in the
`copending patent application referenced above.
`The above modifications to the weighting vectors are
`illustrated in FIG. 13, wherein the intermediate node Ui
`42 is the node which does not belongto the correct class
`and the intermediate node Uj 43 is the node which
`belongs to the correct class. The feature vectoris desig-
`
`SAMSUNG EXHIBIT 1006
`Page 15 of 17
`
`SAMSUNG EXHIBIT 1006
`Page 15 of 17
`
`
`
`5,239,594
`
`10
`
`—_ 5
`
`30
`
`35
`
`40
`
`45
`
`50
`
`©
`
`Weight of Uj: Wjk = Wjk+a[fk—Wyjk] fork=1,...
`N (5)
`
`k
`Tis( 2 (uj * yi)
`j=!
`
`9
`.
`nated as Fx 44 and the window W 45is between the
`intermediate nodes Ui and Uj, and 46 and 47 are arrows
`indicating the directions in which the intermediate
`nodes Ui and Uj are moved. When expression (3) is
`satsified, the feature vector Fx falis within the window
`W 45 between the intermediate nodes Ui and Uj. This
`implies that the weighting vector in the intermediate
`node Uj, which belongs to the correct class, and the
`weighting victor in the intermediate node Ui, which
`does not belong to the correct class, are very close.
`The first equation of the expression (4) directs the
`modification of the weighting vector of the intermedi-
`ate node Ui so that the template represented by the
`weighting vector of the intermediate node Uiis sepa-
`rated further from the feature vector Fx in the vector
`space as shownbythe arrow 46. The second equation of
`the expression (4) directs the modification of the
`weighting vectorof the intermediate node Uj so that the
`template represented by the weighting vector of the
`intermediate node Uj is brought closer to the feature
`vector Fx in the vector space as shownbythe arrow 47.
`These modifications to the weighting vectors are re-
`peated so as to clearly place the input signal in the cor-
`rect class to facilitate higher classification rates.
`If neither expression (2) nor expression (3) are satis-
`fied, the weighting vectorof the intermediate node Uj is
`modified according to the following equation:
`
`wherein h1 and h2 are positive constants. Expression (7)
`is used to check whether the class Cminl, which has
`been determined to be closest to the pattern signal, falls
`within the predetermined area h1, while expression (8)
`is used to check whether the class Cmin1, which has
`been determined to be closest to the pattern signal, and
`the class Cmin2, which has been determined to be sec-
`ond closest, are close to each other.
`If the total output Tmin1 of the class Cmin1 and the
`total output Tmin2 of the class Cmin2 both satisfy the
`above expression (7) and (8), the class selector 49 deter-
`mines that the classification is correct and outputs an
`accept signal. It also outputs the class Cmin1 as a re-
`sponse signal P 21. If both of the above expressions are
`not satisfied, the class selector 49 outputs a reject signal
`and the class Cmin1 as a response signal P 21.
`The learning trigger 19 also operates in the learning
`mode. As FIG. 14 shows,it receives the training signal
`Tr 22 supplied by the user and the classification re-
`sponse P 21 from the discriminator 49. It subsequently
`transfers the correct class signal L 23 to the self-organ-
`izing classifiers 17. More specifically, if the classifica-
`tion response P 21 is a reject signal or the class Cmin1
`indicated by the classification response P 21is not iden-
`tical with that of the training signal Tr 22, the learning
`trigger 19 outputs a correct class signal L,to all of the
`self-organizing classifiers 18, wherein L 23 corresponds
`to the pattern signal which has been given by the train-
`ing signal Tr 22.
`whe