This invention relates to methods of coding information and recognising patterns in information, and is particularly applicable to sequences of values or "value sets" representing numbers or coded symbols.

A value set is defined as a set of discrete values from a real value range or a set of coded symbols (a symbol alphabet) .

A sequence S of length N over a value set is defined as (K=i<=N) is one value from the value set and a component (static pattern) of S. Any part of S, p-t-p ₍ + _{] )} "• • -p^ , where l(<=j<=k<=N, is called a subsequence of S.

The sequence S can also be represented as a vector V _s consisting of N coefficients:

Pi P ₂

V = P ₃

PN

It is also assumed that the presentation to or production from a system of a sequence S is performed in component order as follows: p-^, p ₂ , PM.

The term "Sequence Processing System" is used herein to mean a system which is capable of manipulating sequences. This definition includes entities capable of sequence learning, recognition, production, storage, representation and/or truncation.

The present invention is particularly concerned with a type of representation of sequences which will be referred to as "Sequence Component Ratio Coding (SCRC)", in systems that perform sequence processing, as defined below.

Commonly, two methods of presentation of the sequence S have been used; by presenting the vector V _s or vector D _s to the system, where

These vectors are presented to, and also form the representation of the sequence S in the sequence processing system. The vector D _s is commonly called the difference or delta vector, where the local difference between sequence component p.: and its predecessor (p-;.-^) is used (K=j<=N) as input to the system instead of the actual sequence components p^(K=i<=N) .

According to one aspect of the present invention there is provided a sequence processing system which is adapted to represent a sequence in terms of the ratios of successive component values of the sequence.

Preferably, the invention provides a method of encoding a sequence of values in terms of the ratios of successive components, comprising the steps of:

(a) calculating a quotient relationship between the second and the first component; and

(b) calculating corresponding quotient relationships between successive pairs of components, so as to produce a sequence component ratio coded vector.

Thus the ratio vector R _s can be used to represent part of the sequence representation information in the sequence processing system where

This representation of a sequence will be referred to herein as Sequence Component Ratio Coding.

The Rs vector coefficients are based on the ratios between successive component values of sequence S. The ratios are obtained as follows

r _j _ = (Ki<=N)

^P (i-D

It can be shown that information is preserved using the D _s vectors, in the sense that the original sequence vector Vg can be reconstructed, as long as a single original sequence component, p> (K=i<=N) , is provided. This is also the case with the R _s vector representation.

The reconstruction of components of the original sequence S (and vector form V _s ) from D _£ and component p^ is as follows:

Simarly the reconstruction of components of the original sequence S from vector R _s and components p, is as follows:

^{Pi =} ^ι ^χ ri ⁷ > y = 2

The reconstruction from any component, px (K=x<=N), of any other component, pi (K=j<=N) , of the original sequence S, from the Sequence Component Ratio Coded vector Rs is as follows:

Px pi =

P _* ^x ϋ ^r j tf (i > x ⁾ j = x + 1

Rg ratio coded sequence data gives scale invariant properties to a sequence processing system, as explained below, that cannot be attributed to the D _s , delta-coded representations.

Accordingly it will be appreciated that the present invention extends to the use of SCRC of sequences in sequence processing systems, and the use of entire SCRC ratio vectors or parts of such information for sequence processing, involving any kind of sequence recognition, sequence learning sequence production, sequence truncations, sequence storage and sequence representation.

In particular the invention also extends to a method of pattern recognition or identification comprising the steps of:

(a) representing one or more prototype patterns as a sequence of values;

(b) representing the, or each, prototype sequence in terms of its sequence component ratio vector as previously defined;

(c) representing the pattern which is to be recognised, or identified, in terms of its ratio vector as previously defined; and

(d) comparing the ratio vector of the pattern with the or each prototype, in order to detect a correlation between them.

Scale invariant properties

To illustrate the scale invariance property of Sequence Component Ratio Coding, we will show the following example:

Let S be a sequence with components

1.0 - 2.0 - 1.0 - 4.0 - 8.0 - 2.0

This sequence can be represented as a vector

Vs=[1.0 2.0 1.0 4.0 8.0 2.0]

The Rs vector for sequence S is Rs=[2.0 0.5 4.0 2.0 0.25]

Now let M be a sequence with components

2.0 - 4.0 - 2.0 - 8.0 - 16.0 - 4.0. and can be represented by a vector representation Vm=[2.0 4.0 2.0 8.0 16.0 4.0]

The Sequence Component Ratio Coded vector for sequence M is Rm=[2.0 0.5 4.0 2.0 0.25].

It will be seen that Rm=Rs.

Also, it will be seen that V is a scaled version of Vs, namel that V _m =V _s * 2.

It can also be shown that for Vx such that

Vx = Vs*c(c!^0) ,R _χ =R _s .

This is an important property of the Sequence Component

Ratio Coding method.

A sequence recognition system based on Sequence Component Ratio Coded representations is capable of recognising both of the aforementioned sequences, S and M from only a single ratio vector (R _™ ) , as their ratio coded representations are identical. (R^ = R _s )

Examples of Applications of Sequence Component Ratio Coded Representations to Sequential Data

To illustrate the usefulness of the scale invariant properties there follow two specific examples of

sequential information that benefit from Sequence Component Ratio Coding. Also, a general rule is established regarding necessary properties of data that is to be processed using Sequence Component Ratio Coded representations.

(i) Tempo Invariance

This example uses sequence LI, where the components of LI are values of durational information in any unit (for example, seconds) . This information can be imagined as a rhythm where the duration of each beat is represented by a value.

Let LI be the sequence 2-2-1-1-1-1-4. V _χ =[2 2 1 1 1 1 ] R _L =[1 0.5 1 1 1 4 ] .

A rhythm represented by sequence L2 is twice as slow as in sequence LI and is the following: 4-4-2-2-2-2-8 V _L2 =[4 4 2 2 2 2 8] R _L2 =[1 0.5 1 1 1 4] .

^R L1 ^{= R} L2

We can clearly see that both durational patterns are represented by the same SCRC ratio vector. Therefore, we suggest using this type of representation for tempo- invariant sequence recognition.

ii) Sound-wave frequency (pitch) invariance for sound processing, including speech processing.

The following example uses sequence T,, where the components of T, are values of sound frequency information in Hz. This information can be imagined as a tune without durational information, where each component of the sequence T-, is a value of a note in Hz. Let T, be the sequence:

T _χ = [440.00 523.25 659.26 440.00 493.88 523.25] T, corresponds to the tune A4-C5-E5-A4-B4-C5 in A minor (the number denotes the octave) . R _T1 =[1.189 1.26 0.667 1.122 1.059]

Producing the same tune in a different key (C minor starting from C5) would give us the following tune

C5 - Eflat5 - G -C5 - D5 - Eflat5, that generates the following frequency sequence vector.

T ₂ =[523.25 622.25 783.99 523.25 587.33 622.25]

R _T2 =[1.189 1.26 0.667 1.122 1.059]

^R T1 ^=R T2

It can be seen that both patterns T^ and T ₂ are represented b_ same SCRC ratio vector. Therefore, this type of representation may be used for pitch-invariant sound frequency sequence recognition.

(iii) General Scale Invariance Operating on 2 ^X power function.

The SCRC coding method can be used with any data mode that sea based on the function 2 ^~ x where x is the scaling factor or any data which can be mapped to such a scale.

Potential applications of the technique thus include:

1. Music tracking and tune recognition: application in listening devices tempo-invariant accompaniments for solo instruments using sound production system toys; dolls and other toys that sing-along with children music /sound recognition devices auto-speed adjustable orator/prompting devices speech recognition/word recognition male/female voice pre-processor engine speaker detection karaoke

2. Handwriting Applications handwriting recognition signature recognition

3. Rhythm tempo-invariant— detection

4. Filter: as pre-processor for neural engine as pre-processor for computational engine

5. Sequence Learning pre-processor

6. Data compression engine for analogue or digital storage systems

7. DNA Fingerprint Analysis & Matching

It is therefore possible to employ artificial neural systems using SCRC coded information to achieve efficient representations for types of human-like temporal sequence processing. As an example of using SCRC coding in a aritifical neural network (ANN) architecture, a network for musical tune recognition, which has both pitch-invariant and tempo-invariant properties, is shown in Figure 1. The network comprises two layers. The lower network layer (2) is named the Component layer, where each node ₁ , N ₂ .... represents a note change in the prototype sequence. Each node, N, in the Component layer receives as input the SCRC coded values of both frequency (X^) and duration (X ₂ ) °f each musical note change in the musical tune processed by the system. The error of input against the learnt ratio values is calculated as follows:

Error (Nj) = max(f , f (x ₂ /w ₂ j ) ) where f(z) = z if z>l or f(z) = 1/z otherwise

and where ,.: and w _2- : are the learnt ratio values of frequency and duration respectively. The local activation function Act(Nj,t) for node N; at time step t is as follows:

Act(Nj,t) = 1.0 if Error (Nj)< ψ(where φ is the error threshold) or

Act(Nj,t) = λ * Act(Nj,t-l) otherwise (λ is a decay constant where 0<X<1)

A short term memory potentiation mechanism also operating on the lower (Component) layer giving potential to nodes following activated nodes. The nodes preceding node Nj contribute to the short term potential of node Nj . The length of the short-term memory is L, where the potential of / preceding nodes (N-^ -^ to N-ι_ ₁ ) contribute to the follows (j(<=i<=L) : the Short-Ter memory contribution of N ^ towards neuron N-

stm_decay_constant ¹ *λ ¹ if (n<0) or st .decay.constant ¹ * Act(N.:_ t) otherwise

J i

The total Short-Term potential at node N is passed to the upper layer 4, which is referred to as the sequence layer if Act (N^) has spiked, thus Act (N.; t) = 1.0,

J J / otherwise no potential is passed to the relevant Sequence Layer node.

In the Sequence layer, each node is assigned to a particular sequence prototype that is learnt by the ANN system. The upper layer is in fact a winner-takes-all layer where, a function of the greatest potential node from the lower layers contributes towards the activation of a node. The Sequence Layer node decays at a rate specified by the sequence node decay constant. The activation function of the Upper layer nodes, U, is as follows:

Act(U_: t) =sequence_node_decay constant*Act(U^ t-l)

J I ~ J I

÷Component Potential Typical values for these parameters are as follows:

L=15, φ-1 .15,λ=0.8,stm_decay_constant = 0.5, sequence_node_decay constant = 0.8.

Network Learning

The learning process involves supervised one step learning, where a single presentation of a sequence is sufficient for the ANN model to learn it. The input vector in this system consists of two coefficients: the note frequency ratio and the note duration (length) ratio. On changing the note to the following note in the tune, the ratios are calculated and the input vector is updated. The new input vector is then presented to the network. Sequence Laver: a single node is created in the Sequence layer for each new sequence that is learnt by the system. During the presentation of one sequence any node created in the Component layer is connected to this node in the Sequence layer.

Component Laver: a node is created in the Component layer (CL) for each newly presented input vector. The two weights of the CL node are assigned the same values as the respective input coefficients: w,^ = x, and w-,.: = x ₂ . Short term memory connections are also created from up to L nodes preceding the newly created node to the node. The contribution output of the CL node is connected to the relevant Sequence layer node. This process is repeated for every input pattern (note change) in the sequence (tune) until the sequence completes. Any number of sequences can be trained in this manner.

Tune Identification and Tracking Sequence Identification

Having been trained the relevant sequence prototypes can be used for identification of input sequences. At t=0, all activations are initialised to 0 and the presentation of sequences can begin. The operation of the network is described above. The most active node in the Sequence layer (the Winner node) then represents the identified sequence.

Sequence Tracking using SCRC Coded Representations

An alternative use for the above mentioned ANN system is tracking the sequence being input. This can be achieved first by identifying the sequence being input into the systems and subsequently monitoring the node with the highest activation in the Component layer, belonging to the set of nodes contributing to the winning Sequence layer node.

Both the identification and tracking of musical tunes played on a MIDI (Musical Instrument Digital Interface) keyboard have been achieved by a computer- simulation of the ANN model. The MIDI codes representing notes were transformed to sound frequencies for input to the network.

References

[1] Mrsic-Flogel, J., Approaching Cognitive Systems Design, Artificial Neural Networks, Proc. of International Conference on Artificial Networks (ICANN-91) , Editors T. Kohonen et al, Elsevier, 1991.

[2] Mrsic-Flogel J. , Automatic Speech Recognition using Adder Neurons and Ear Filter Model, International Conference on Artificial Neural Networks 1994 Sorrento proceedings, Springer Verlag, 1994.

[3] Mrsic-Flogel, J. Aspects of Information Detecting using Entropy, WCCI World Congress on Computational Intelligence Orlands 1994

[4] Wang D., Temporal Pattern Processing, Handbook of Brain Theory and Neural Networks, MIT press, in press, 1995 [5] Wang D., Arbib M. A., Complex Temporal Sequence Learning based on Short-term Memory, Proc. of IEEE, Vol.78 no.9, 1990 [6] Wang D. , Yuwono B., Anticipation-based temporal pattern generation, IEEE Trans. SMC 25.3, March 1995

[7] Tsukada M. et al., Temporal pattern sensitivity of long- term potentiation in hippocampal CA1 neurons, Biol.Cyb., 70,495-503