Structured and syntactic pattern recognition is based on the idea that patterns can be represented by symbolic data structures like strings, trees, and graphs. In order to figure out what a pattern is that hasn't been seen before, its symbolic representation is compared to a number of prototypes that have already been seen.
Syntactic pattern recognition or structural pattern recognition is a form of pattern recognition, where items are presented with pattern structures that can take into account more complex inter relationships between features than simple numerical feature vectors used in statistical classification.
If the patterns have a clear structure, syntactic pattern recognition can be used instead of statistical pattern recognition. Strings of a formal language are one way to show this kind of structure. In this case, the different ways the classes are put together are represented by different grammar.
An example of this would be a diagnosis of the heart with ECG measurements. ECG waveforms can be approximated with diagonal and vertical line segments. If normal and unhealthy waveforms can be described as formal grammars, measured ECG signals can be classified as healthy or unhealthy by first describing them in terms of the basic line segments and then trying to parse the descriptions according to the grammars. Another example is the tessellation of tiling patterns.
Another way to represent relations is graphs, where nodes are connected if corresponding sub-patterns 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 subtasks of first identifying sub-patterns and only then the actual patterns.
Structural methods provide descriptions of items, which may use in their own right. For example, syntactic pattern recognition can be used to find out what object are present in an image. Grammatical induction, also known as grammatical inference or syntactic pattern recognition, refers to the process in machine learning of inducing a formal grammar (usually in the form of re-write rules or productions) from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects. The grammatical inference is distinguished from traditional decision rules and other such methods principally by the nature of the resulting model, which in the case of grammatical inference relies heavily on hierarchical substitutions.
Whereas a traditional decision rule set is geared toward assessing object classification, a grammatical rule set is geared toward the generation of examples. In this sense, the grammatical induction problem can be said to seek a generative model, while the decision rule problem seeks a descriptive model.
In many recognition problems involving complex patterns, it is more appropriate to adopt a hierarchical perspective where a pattern is viewed as being composed of simple sub patterns which are themselves built from yet simpler sub-patterns.
The simplest elementary sub-pattern to be recognized are called primitives and the given complex pattern is represented in terms of the inter relationships between these primitives. In syntactic pattern recognition, a formal analogy is drawn between the structure of patterns and the syntax of a language. The patterns are viewed as sentences belonging to a language, primitives are viewed as the alphabet of the language grammar.
Thus, a large collection of complex patterns can be described by a small number of primitives and grammatical rules. The grammar for each pattern must be inferred from the available training samples. Structural pattern recognition is intuitively appealing because, in addition to classification, this approach also provides how the given pattern is constructed from the primitives. This paradigm has been used in situations where the patterns have a definite structure that can be captured in terms of a set of rules such as EKG waveforms, textured images, and shape analysis of contours. The implementation of a syntactic approach, however, leads to many difficulties which primarily have to do with the segmentation of noisy patterns (to detect the primitives) and the inference of the grammar from training data.