--- title: "Pattern Recognition by Quasi-Linguistic Translation Into Artificial Noise-Resistant Language" authors: - "A. N. Radchenko" doi: "" url: "https://ijcai.org/proceedings/1971/41" pdf: "https://ijcai.org/proceedings/1971/0041.pdf" venue: "Proceedings of the Second International Joint Conference on Artificial Intelligence" year: 1971 pages: "402-409" track: "" keywords: --- # Pattern Recognition by Quasi-Linguistic Translation Into Artificial Noise-Resistant Language A. N. Radchenko *Proceedings of the Second International Joint Conference on Artificial Intelligence*, pages 402-409. ## Abstract A new approach to the recognition problem is considered, which does not require clustering of the sampling space into the appropriate number of regions. Each sample mapped in multi-dimensional space is represented by a family of points (vectors), forming a certain configuration, Less compact location of the points leads to more simple and reliable pattern recognition. The input description is represented by the "text" formed by a set of binary pulse sequences. The recognition implies that the text fragments of different space-temporal structure should be related to one of the different classes. The recognition is carried out as an informational transformation of the inpnt text into another one, invariant of any small variations in the space-temporal structure of the input text. Sufficiently different texts are translated into non-identical output texts. Repeated transformation of the input text by a number of translators is accompanied by an increasing "abstraction" (stabilization) of the output text relative to the input text variations. As a result, the output text structure can be considered as a list of classes, to which the input text fragments belong. It is pointed out that the information compression characterizing the recognition process can not necessarily be carried out a priori but it can always be carried out as a consequence of the recognition process. A correspondence is implied between the features of the "translation" process and some neuro-physiological phenomena. ## Full text ## Introduction Methods for an automatic pattern recognition can be classified on the ba­ sis of: - 1) forms of the input information representation, - 2) the information coding methods, 3. }) methods for the coded signal processing. The first item characterizes the physical information carrier and is not of principle importance, since the in­ formational description of any physical process (image, speech etc.) can be transduced to binary vectors and sequences. The second item characterizes the relation between the physical process and the code. It is of importance that sufficient variations in the physical process must correspond to th' suffi­ cient variations in the output vector. As for small variations, they, ae a rule, must correspond to small variations in the output vector. Such variations can often be neglected and it is not neces­ sary to transfer them to the output vec­ tor. In other cases, on the contrary, the small variations must be emphasized by transforming them into larger output variations. Henceforth it will be enough to require that the coding does not dis­ tort sufficiently the metric relations which should be determined on the input and output signals of the encoder. The third item is of principle im­ portance. Many methods have been sug­ gested to reduce the recognition problem to the clustering of a metric space into the domains the number of which is di­ rectly or indirectly related to the num­ ber of identified objects, i.e. to the construction of a deterministic or pro­ babilistic "decoder" ( 1 ). As an information transformation, recognition consists in the elimination of redundancy from the input vector. This process of information compression is facilitated in the earlier stages by detecting and eliminating lees informa­ tive co-ordinates and by a reasonable amount of feature extracting from the original data. In any case, the infor­ mation losses are accumulated during the inf"ormation compression process, which sometimes leads to noticeable errors in the recognition results. The pattern recognition method sug­ gested in this work leads to lower in­ formation losses because the information compression (e.g. transition to a more laconic sign system) does not necessa­ rily precede the recognition. At the sa­ me time, the information compression is quite feasible as a consequence of reco­ gnition in which the information losses are minimized. The advantage of this work is the deliberate rejection of single-domain pattern localization in the sampling space and the rejection of the space clustering into domains, the n~ber of which directly or indirectly depends on the number of classes. Each sample in this space is represented by a set of dislocated vectors (points). Patterns b.elonging to the same class are repre­ sented in the signal space by a set of domains the disposition of which to some extent repeats and generalizes the disposition of pointe of a certain sampliDg. A less compact disposition of these points and domains facilitates the solu­ tion of the sample belonging to the par­ ticular class. fhe larger is number of dislocated points contained in a single sample, the more reliable is their iden­ tification. The recognition process is consi­ dered as a translation from one language into the other more economic one: 1. The input "text" is represented by a set of binary coded pulse sequences. Fragments of this text are to be recogni­ zed differing in their space-temporal structure of the pulse position. 2. The classification results in the identical translation of the frag­ ments which differ slightly. The trans­ lation of sufficiently differing frag­ ments is also different. 3. Repeated transformation of the input text by a number of translators is followed by on increasing "abstraction" (stabilization) of output texts relative to the input text variations. 4. ~. Stable output text fragments are decoded (recognition) or receded by a more economic code (the information com­ pression). ## I. The essence of information ## processing Let us consider the original in­ formation which is encoded without lossee and sufficient metric distortion in­ to the binary pulse sequences, defined as a function of discrete time t· ~;.""''! where :.t;(t) = 0 or { and d is the se­ quence length. Information /1/ will be called "the input text X". It is convenient to ima­ gine the text /1/ as a description of pulse activity of the afferent nerve consisted of « fibres, during the long time 't . To determine · the metric the text /1/ can be represented in the form of slidiDg n. -segments /l(t): is the "window" of the same "height" as the text /1/, but much more narrower than it. For the convenience, the rows of R(t) can be rewritten in one line as an N-dimensional vector The notation /3/ enables us to re­ present the input text in the form of an At-dimensional cube apex sequence. This sequence given as a function of time, will be named "the signal trace". The r..umber of points on the signal trace un­ der the accepted limitations /2/ almost equals the input text length. The distance between the points will be measured by the number of noncoincident elements of the vector &(t) . We shall be interested in many point segments of the signal trace Ottrl) 1 R(t+2)J ·.· 1 G(t+() and in their belonging to particular classes. The conception of sample is not defined in the training process, since the segmentation problem arises in this case. It should be noted that not each segment of the sigrml trace belongs to one sample. It should be pointed out that the Hamming distance between vectors !)(c) and a((-t1) in the adjacent transition is sufficiently large. Actually, if /1/ represents the random realization with uniform and independent distribution of zeroes and units, then the distance pro­ bability f'(d) in the adjacent transi- It follows from the above formula, that on the average the "leap" is very large /5/ The "leap" form is one of the essential properties of the signal trace. Let us fix in AV-cube the signal trace corresponding to a realization of the input text irrespective of whether the trace belongs to the particular classes. Using well-known taxonomic methode, the trace point set can be clus­ tered into two parts in such a way that the boundary zone would be the largest. The separability criterion can take into account the number of short distance pointe belonging to different subsets, the values of their distances, etc. If the criterion for equidistantness of the separated subsets is chosen, then the separation surface can be constructed inside the boundary zone and the separa­ tion function can be defined ~Jt) = F (ar(J) /6/ where ~ (t) is "1", if the points are lo­ cated on one of the surface sides, and "u", if the points are located on the opposite side. The separation function /6/ allow the transformation of the text /1/ and other similar texts into a certain dif­ ferent text Y 'f ={a-rt}} :1 ~(f), #(z),. .. ,~fr) 171 For the concordance of the text /1/ and /71 lengths it is supposed that the first of them is added by h. -1 zero signs which are not taken into accow1t in tact numeration. If powers of the se­ parated subsets are equal the leap pat­ tern of the trace /3/ causes an appro­ ximately equal probability of transitions ( ., ... f, t~o) o~ f, c~ (J ) in the output text /7/, i.e. the absence of no­ ticeable correlation between the adja­ cent symbols. It lays a foundation for obtaining high informative output reac­ tions for the appropriate input. In the case of long texts ( f>> n ) it is convenient to consider X- Y transformation as a translation from one language into the other one. The trans­ latioD has the following properties: 1. Numerous eliBhtly differing texts are transformed into an identical output text (the stabilization effect). Sufficiently different texts correspond to the different translations. Indeed, a lot of small differences in the input text ~eads to proportional shifts of the signa1 trace points. If the removing point doea not erose the separation sur­ face, the output text does not change. 2. Recognition properties of the translation are not uniform in this pro­ cess: the beet stabilization is observed 3. for the ;V -cube pointe located far from the surface, while the worst staoiliza­ tion is observed for the points located near by the surface. 3. The effect of an increase in the variations is observed for t .he sig­ nal trace pointe located on the surface or in the vicinity of it. It is caused by the fact that the single distortion of the text/1/ leads to single shifts of n signal trace points. This feature should be taken into account in the separability criterion. Taking the dif­ ferent separation surfaces, one can en­ sure the wanted metric transformation of the input text. 5. 4-. A new text composed of "quota­ tions" of the text used in the training process will be reproduced on the trans­ lator output in the form of associated fragments of the output text following the appropriately changed sequence. The limited quotation distortion do not affect the translation correctness. 5. Invariant output text fragments can be considered as a list of classes related to the appropriate quotations on the input. Variable output text frag­ ments are associated with the quotation joints on the input. These output va­ riations are grouped into burets of ma­ ximum length 11.- t -1 , where J is the halfwidth of the separation zone. If the invariant fragments of the output text are considered as roots of words, then the variable ones could be considered as an adjustment ot· the grammar. 6. Strongly different input quota­ tions are translated into different output "words". The shorter quotations can not be contained in the longer fragments. Thus, the sliding segments of the output text can be readily registered on the shift register by the decoder (recogni­ tion) or can be recoded into more econo­ mic code (information compression). vn the other aide, the above property can be considered as limitations on the minimum input text quotation length. 7. Taking the different separation surfaces, we determine one of the arti­ ficial languages for the translation. Clustering II -space into many regions and varying their designations, we can extend the variety of. artificial langua­ ges and make an attempt to appro%imate one of them to the natural ones, e.g · . to transform the speech into the teletype code. - B. It is possible to suggest that the clustering of lY-space carried out after the long pithy training could lead to the creation of a translator ensuring a stabilizing translation (recognition) of ~he words, which are not used in the training. ## 2. Estimation of recognition efficiency in the worst indeterministic case. Let us suppose that the input text /1/ is represented by a set of binary pulse sequences, in which zeroes and units are distributed independently and uniformly. It is necessary for the reco­ gnition transiation of the text to know if it is possible to separate the sig­ nal trace points into two subsets in such a way that the points would not mo­ ve from one subset to the other, as a result of single shifts of the points. This condition is deliberately observed if the subset. points are distant from the separation surface at least by one of the co-ordinates. A calculation will be given below of a posteriori division of the random Af-cube points by the zone consisting o:t' t random points. If these separated subset are con­ tained in two Hamming's spheres with~ their centers located at the princip diagonal, then the number m of possible separation zones is equal to the number of complementary vector pairs of the ./I -cube points. Th.en we get Each separating zone contains b points ,, t /: ;:.""-2.~ {1) where ~ is the sphere radius. Let each of 't tests result in eli­ mination of the zones containing /l{t) :rrom the separation zone set. If even one zone will remain at the end of the tests, then the desired division is pos­ sible. The division probability should be determined. The general separation zone set has a symmetric location in JY' -cube accor­ ding to the zone formation law. Each po­ int of Al-cube belongs simultaneously to the different separation zones. The num­ ber of the zone~ containing one point is Suppose that it is possible to select y of M variants in such a way that their zones form a single-layer packing containing all Al-cube points, and that the general set of ~ zones can be represented by A -layer packing. It is evident that 2~ Actually such a division can be carried out only approximately. For the particu­ lar layer, the probability /'t that all separation zones will contain the points ~(t) in J' independent tests is given by (.~) Hence the probability that at least one neutral separation zone can be founded The second member vanishes with increa­ sing ;V · Hence the desired division o:f the signal trace points into subsets can be readily found. In connection with the suggestion of ff -cube packing separabi­ lity, the results /8/ and /9/ should be considered as the upper limit estimation. The lower lin:t estimation can be obtained on the assumption that each layer of v4f-cube packing contains only one of m neutral zones. The probability for the point !Ht) to be contained in one of the fixed separation zones in a single test is The current value of the remaining zone number is designed by m (t). Then the mean number of the single .AI -cube point packing by the separation zones is The expected value of the remaining zone number after the next teet is lt1 (~+1) Then the expected value of the num­ ber of the zones remaining after the training can be readily obtained: The probability that each particular zone will remain after the training is pt. The probability that all zones will be removed is The probability that at least one separation zone will remain is given by A/ I 2 K-1 R = f- [ 1-( f- ( J.- ') ] I to I Suppose that the 4Pndition {.Y-t)6t 2.- ~& ::: ~ {A) /11/ is satisfied, where '-" is a real number Then It follows from /11/ that to obtain f{ \_,. f the linear function of .AI must be the upper limit of the valueoC=('IZ~ Hence the desirable separation of the signal trace points into subsets can be found. The larger JV is the easier this separation can be carried out. ## 3. The worst deterministic case. Much worse than the random location of the signal trace points in ~-cube is a set of locations eo determined that all J" pointe occupy uniformly the /-cu­ be volume, being separated by equal dis­ tances d = 2. t + f Then we have It is necessary for stabilizing translation to ensure 't ~ I for any pair of points. Une can find a certain ~ eo that this condition will be observed. Using the Shannon's approximation (2) The larger AI is the easier the eq./14/ is satisfied. Hence there are no difficulties in the separation even in this case. ## Conclusions. According to the above considera­ tions the following conclusions can be drawn: 1. Correspondence between the num­ ber of distinctive patterns and that of the appropriate separable domains of the sign space is not necessary for the pat­ tern classification. 2. The transformation suggested in this work does not require a priori so­ lution of the input text segmentation problem. 3. To improve the classification the dimensions of the signal space sho­ uld not be reduced. Hence: - a) transition from the initial co­ ordinates to a more economic sign system is not necessary. - b) leas informative co-ordinates should not be left out. 4. The suggested method enables us to carry out the information compression within any limits given in advance as a consequence of the recognition. 5. The suggested method has some features of its neuro-physiological pro­ totype, the brain, in particular, the distributivity phenomenon. The concep­ tion of recognition translation is the linguistic treatment of the conditioned reflex(4). It should be noted that the segmen­ tation problem solution in this case is closely related to the problem of shift, angle and size invariance in the pattern recognition. The solution of those pro­ blems is difficult, since the samples belonging to the same class have large Hamming's distances. At the same time, it is usually impossible to find any metrics which would not be connected with abrupt leap variation in the dis­ tance in one-step transition. One can see that this "difficulty" has been used in this work as a natural basis for the separation and construction of noise-re sistant (stabilizing) translation into an artificial language. Hence one should try to obtain the "leap" signal trace by the appropriate choice of the quantization step, metrics, scanning etc. The seeming increase in complication of the recognition process due to the multiple representation of samples in an Af-cube is not the case indeed, since the #'-cube division can be made by the simplest methods. The lack of a priori limitations for the number of separated domains also facili­ tates the recognition problem in compa­ rison with other available methods. Cur­ rent clustering techniques and in parti­ cular, taxonomic methods are entirely acceptable for the solution of the re­ cognition problem by the methods men­ tioned above. ## R e f e r e n c e s 1. V.I.Vasiliev, "Recognition systems", Uaukova dumka, Kiev, 1969. 2. W.Peterson, "Error-correcting codes", Mir, ~oscow, 1964. 3. W.Feller, "Introduction to the theo­ ry of probability and its applica­ tions", Mir, Moscow, 1967. 4. A.N.Radchenko "Analytical study of neuro-physiological processes of in­ formation recording and reproduction on the speculate model", in "Cyber­ netical aspects in the study of the brain action", Nauka, .Moscow, 1970. ## References 1. V.I.Vasiliev, "Recognition systems", Uaukova dumka, Kiev, 1969. 2. W.Peterson, "Error-correcting codes", Mir, ~oscow, 1964. 3. W.Feller, "Introduction to the theo- ry of probability and its applica- tions", Mir, Moscow, 1967. 4. A.N.Radchenko "Analytical study of neuro-physiological processes of in- formation recording and reproduction on the speculate model", in "Cyber- netical aspects in the study of the brain action", Nauka, .Moscow, 1970.