Syntactic pattern recognition or structural pattern recognition is a form of
pattern recognition
Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphics ...
, in which each object can be represented by a variable-
cardinality set of symbolic,
nominal
Nominal may refer to:
Linguistics and grammar
* Nominal (linguistics), one of the parts of speech
* Nominal, the adjectival form of "noun", as in "nominal agreement" (= "noun agreement")
* Nominal sentence, a sentence without a finite verb
* Nou ...
features. This allows for representing pattern structures, taking into account more complex interrelationships between attributes than is possible in the case of flat, numerical
feature vector
In machine learning and pattern recognition, a feature is an individual measurable property or characteristic of a phenomenon. Choosing informative, discriminating and independent features is a crucial element of effective algorithms in pattern r ...
s of fixed dimensionality, that are used in
statistical classification
In statistics, classification is the problem of identifying which of a set of categories (sub-populations) an observation (or observations) belongs to. Examples are assigning a given email to the "spam" or "non-spam" class, and assigning a diagn ...
.
Syntactic pattern recognition can be used instead of statistical pattern recognition if there is clear structure in the patterns. One way to present such structure is by means of a
strings of symbols from a
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
. In this case the differences in the structures of the classes are encoded as different
grammars.
An example of this would be diagnosis of the
heart
The heart is a muscular organ in most animals. This organ pumps blood through the blood vessels of the circulatory system. The pumped blood carries oxygen and nutrients to the body, while carrying metabolic waste such as carbon dioxide to t ...
with
ECG
Electrocardiography is the process of producing an electrocardiogram (ECG or EKG), a recording of the heart's electrical activity. It is an electrogram of the heart which is a graph of voltage versus time of the electrical activity of the hear ...
measurements. ECG
waveform
In electronics, acoustics, and related fields, the waveform of a signal is the shape of its graph as a function of time, independent of its time and magnitude scales and of any displacement in time.David Crecraft, David Gorham, ''Electro ...
s can be approximated with diagonal and vertical line segments. If normal and unhealthy waveforms can be described as formal grammars, measured ECG signal can be classified as healthy or unhealthy by first describing it in term of the basic line segments and then trying to parse the descriptions according to the grammars. Another example is
tessellation
A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety o ...
of tiling patterns.
A second way to represent relations are
graphs, where nodes are connected if corresponding subpatterns are related. An item can be labeled as belonging to a class if its graph representation is
isomorphic with prototype graphs of the class.
Typically, patterns are constructed from simpler sub patterns in a hierarchical fashion. This helps in dividing the recognition task into easier subtask of first identifying sub patterns and only then the actual patterns.
Structural methods provide descriptions of items, which may be useful in their own right. For example, syntactic pattern recognition can be used to find out what objects are present in an image. Furthermore, structural methods are strong in finding a correspondence mapping between two images of an object. Under natural conditions, corresponding features will be in different positions and/or may be occluded in the two images, due to camera-attitude and perspective, as in
face recognition. A
graph matching
Graph matching is the problem of finding a similarity between graphs.Endika Bengoetxea"Inexact Graph Matching Using Estimation of Distribution Algorithms" Ph.
D., 2002Chapter 2:The graph matching problem(retrieved June 28, 2017)
Graphs are comm ...
algorithm will yield the optimal correspondence.
See also
*
Grammar induction
Grammar induction (or grammatical inference) is the process in machine learning of learning a formal grammar (usually as a collection of ''re-write rules'' or '' productions'' or alternatively as a finite state machine or automaton of some kind) fr ...
*
String matching
*
Hopcroft–Karp algorithm
In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of ...
*
Structural information theory
References
{{cite book , last= Flasinski, first = Mariusz , title = Syntactic pattern recognition , publisher = World Scientific , year = 2019 , ISBN = 978-981-3278-46-2
Classification algorithms