Pattern Recognition and Problem Decomposition in Artificial Intelligence

Home / AI / Pattern Recognition and Problem Decomposition in Artificial Intelligence

 

Introduction

Artificial Intelligence (A.I) is a word created in 1955 by J. McCarthy, M. L., N, and C.E. Shannon after a proposed “Dartmouth summer research project on artificial intelligence”, remembered now as the Dartmouth Conference. This Conference held in the summer of 1956, discussed various aspects of learning and intelligence that could be simulated on machines.

Artificial intelligence is based around the idea that human intelligence can be defined in such exact terms that a machine can mimic it. The goals of artificial intelligence include learning, reasoning and perception, and machines are wired using a cross-disciplinary approach based in mathematics, computer science, linguistics, psychology and more (Investopedia, 2018)

Since then Pattern Recognition has remained one of the principal fields in Artificial Intelligence till the beginning of 70’s when the first IJCPR (International Joint Conference on Pattern Recognition) was organized.

The name of Pattern Recognition appeared later on with the objective of developing techniques in the area of classification, oriented to solve engineering problems. Both areas share objectives and applications that can be solved in different ways.

pattern recognition is the scientific discipline of machine learning (or artificial intelligence) that aims at classifying data (patterns) into a number of categories or classes” ( Kidiyo, 2007)

Pattern Recognition

Pattern recognition is defined as the study of how machines can distinguish the environment, learn to singularize patterns of interest from their background, and make good and reasonable decisions about the categories of the patterns by using machine learning algorithm; classifying data based on knowledge already gained or on statistical information extracted from patterns and/or their representation.

With almost 50 years of on-going research, design of a general-purpose machine pattern recognizer remains a shadowy goal. The best pattern recognizers in almost all instances are still humans, yet we do not fully comprehend how humans recognize patterns.

Pattern Recognition PR has found its application in multimedia document recognition (MDR), Speech recognition, speaker identification, automatic medical diagnosis to say but a few.

In a typical pattern recognition application, the raw data is processed and decomposed into a form that is flexible for a machine usage. i.e classification and cluster of patterns.

Patterns

Satoshi Watanabe in 1985 defined a pattern as “the opposite of chaos; it is an entity, vaguely defined, that could be given a name.” (Watanabe, 1985).

A pattern can be any entity of interest which one needs to recognize and/or identify; it is so worthy that one would like to know its name (its identity). A pattern is an object, process or event that can be given a name. Pattern is everything around in this digital world, a pattern can either be seen physically or it can be observed mathematically by applying algorithms.

Examples of patterns include a pixel in an image, a 2D or 3D shape, a typewritten or handwritten character, the gait of an individual, a gesture, a fingerprint, a footprint, a human face, the voice of an individual, a speech signal, ECG time series, a building, a shape of an animal., The colours on the clothes, speech pattern etc. In computer science, a pattern is represented using vector features values.

 Pattern Class

Pattern class or category is a set of patterns sharing common attributes and usually originating from the same source

Features

Features also described as attributes, characteristics, signatures or measurements which are extracted from a pattern to represent it in the features space. In other words, pattern analysis enables us to use some features to describe and represent it instead of using the pattern itself. the recognition efficiency and reliability are dependent on their choice. Features can be represented as a continuous, discrete or discrete binary variable. A feature is a function of one or more measurements, computed so that it quantifies some significant characteristics of the object.
Example of feature is considering our height and weight etc.  are features of boys and girls.

Feature Vector

A set of features that are taken together, forms the features vector. Feature vector is the sequence of a features represented as a d-dimensional column vector.

Table 1: feature vector

Class Weight (kg) Height (cm) Feature Vector
boys 41 145 (41,145)
boys 45 149 (45,149)
boys 42 150 (42,150)
boys 50 152 (50,152)
boys 48 155 (48,155)
boys 38 142 (38,142)
girls 37 141 (37,141)
girls 39 139 (39,139)
girls 41 143 (41,143)
girls 32 143 (32,143)
girls 31 145 (31,145)

 

In the above example of the measurement of boys and girls showing their weight and height, if all the features (weight, height) are taken together then the sequence is a two-dimensional feature vector ([weight, height]).



In case of speech, MFCC (Melfrequency Cepstral Coefficient) is the spectral features of the speech. Sequence of first 13 features forms a feature vector

An obvious representation of a pattern will be a vector. Each element of the vector can represent one attribute of the pattern. The first element of the vector will contain the value of the first attribute for the pattern being considered.

Another example could while representing spherical objects, (25, 1) may be represented as an spherical object with 25 units of weight and 1 unit diameter. The class label can form a part of the vector. If spherical objects belong to class 1, the vector would be (25, 1, 1), where the first element represents the weight of the object, the second element, the diameter of the object and the third element represents the class of the object.

In Recognition or classification process given objects are assigned to prescribed classes

 

Problem Decomposition

Problem decomposition in computer science parlance, known also as problem factoring, is breaking or splitting a complex problem or system into parts that are easier to conceive, understand, program, and maintain.

decomposition in computer programming is often to referred to as a strategy for organizing a program as a number of parts, and it usually implies a specific way to organize a program text. Generally, decomposition paradigm aims to optimize different metrics related to program complexity, for example the modularity of the program or its maintainability. (Wikipedia, 2018).

Different types of decomposition exist and are defined in computer sciences as follows

  • In structured programming, algorithmic decomposition breaks a process down into well-defined steps.
  • Structured analysis breaks down a software system from the system context level to system functions and data entities.
  • Object-oriented decomposition, on the other hand, breaks a large system down into progressively smaller classes or objects that are responsible for some part of the problem domain.
  • According to Booch, algorithmic decomposition is a necessary part of object-oriented analysis and design, but object-oriented systems start with and emphasize decomposition into classes.

More generally, functional decomposition in computer science is a technique for mastering the complexity of the function of a model. A functional model of a system is thereby replaced by a series of functional models of subsystems.

 

Problem Decomposition and Pattern Recognition

Problem decomposition aids computational thinking for Pattern recognition systems, Computational thinking is the thought processes involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by an information-processing agent (Jeanette M. Wing, 2018).

Pattern recognition involves finding the similarities or patterns among small, decomposed problems, once a complex problem has been decomposed, it helps to examine the smaller problems for similarities or patterns. Identifying and extracting the features of these patterns can help us to solve complex problems more efficiently.



In computational thinking, objects (problems) has characteristics are known as patterns. Once we know how to describe one object by decomposing them in to patterns, we can describe others, simply by following this pattern. The only things that are different are the specifics; where one object may be bigger or smaller etc.

Object and patterns

Figure 1: Object and Patterns

Finding patterns is extremely important. Patterns make our task simpler, problems are easier to solve when they share patterns, because we can use the same problem-solving solution wherever the pattern exists. The more patterns we can find, the easier and quicker our overall task of problem solving will be.

If we want to draw a number of cats, finding a pattern to describe cats in general, eg they all have eyes, tails and fur, makes this task quicker and easier.

We know that all cats follow this pattern, so we don’t have to stop each time we start to draw a new cat to work this out. From the patterns we know cats follow, we can quickly draw several cats.

 Recognizing patterns by problem decomposition

To find patterns in problems we look for things that are the same (or very similar) in each problem. It may turn out that no common characteristics exist among problems, but we should still look. Patterns exist among different problems and within individual problems. We need to look for both.

To find patterns among problems we look for things that are the same (or very similar) for each problem. For example, decomposing the task of traveling from one city to other would highlight the need for us to know the solutions to a series of smaller problems:

  • Which city are you traveling to
  • What is the exact coordinate of the place in the city you are traveling to
  • What means of transportation (air, land or sea).

Once we know how to travel from one city to another, we can see that traveling to another city is not that different – because patterns exist.

For example:

  • Each city has a name
  • Every city has a coordinate
  • A means of transportation must exist

Once we have the patterns identified, we can work on common solutions between the problems.

Example: Decomposing Characters for Pattern Recognition

Let’s say we are given four characters (A, B, C, D) to decompose for pattern recognition. Observing the four characters closely we can see a pattern made up of two features, curves and lines, which can aid its decomposition and classification.

Table 2: Features of Characters

Character Number of Lines Number of Curves Representation
A 5 0 (5,0)
B 2 2 (2,2)
C 0 1 (0,1)
D 1 1 (1,1)

Figure 2: Character Decomposition

If we are trying to recognize a hand-written pattern, we shall call it an unknow character

Figure 3: Unknown Character

Trying to decompose it, we find out that’ its made of four (4) lines and one (1) curve which we shall represent as (4,1)

Figure 4: Classification of unknown character

We can observe its closest to A, so it be classified as A.

 

However, this does not hold true for all the characters, for example (N and Z)

They have exactly same number of lines (3 lines), therefore to efficiently decompose and classify all the characters, we will need more features; example, number horizontal lines, number of vertical and diagonal lines; hence the more features, the more the efficiency of the pattern recognition system.

Example: Classification of Teenage Boys and Girls in a School

In a given class of 11 students made of 6 boys and 5 girls, to effectively classify, we may need to look for easily measurable features which we can decompose to classify them, here we can choose their weight and their height.

Table 3: Features of students in the class

Class Weight Height
boys 41 145
boys 45 149
boys 42 150
boys 50 152
boys 48 155
boys 38 142
girls 37 141
girls 39 139
girls 41 143
girls 32 143
girls 31 145

The features can be converted to a vector space as shown below

Table 4: Feature vector students in the class

Class Feature Vector
boys (41,145)
boys (45,149)
boys (42,150)
boys (50,152)
boys (48,155)
boys (38,142)
girls (37,141)
girls (39,139)
girls (41,143)
girls (32,143)
girls (31,145)

And can be represent in a chart below

 

Figure 4:          Classification of boys and girls

With this problem decomposed, we can easily classify and assign an unknown data points, to one of the predefined class labels. Assuming we have an unknown student with feature vector of (35, 132), can easily be classified as a girl from the graph above.

Steps of Pattern Recognition

  1. Sensing – how we capture data from an object for classification purpose, using devices like Camera, Microphone, thermometer
  2. Segmentation – this involves decomposition and extracting the information of our interest from the captured signal
  3. Feature Extraction – which feature to select, feature value of an object belonging to same class should be close to each other; the feature value of the objects should be very far from each other which belong to different classes. Example, no of eyes cannot be a good feature
  4. Designing of classifier: – this belongs to the process which creates class regions or boundaries between classes
  5. Classification: this assigning an unknown data points to one of the predefined class labels.

 

Pattern Recognition System

A pattern recognition system (PRS) is an automatic system that aims at classifying the input pattern into a specific class. pattern recognition system proceeds into two successive tasks:

(1) the analysis (or description) that extracts the characteristics from the pattern being studied

(2) the classification (or recognition) that enables us to recognize an object (or a pattern) by using some characteristics derived from the first task.

Pattern Recognition System

Figure 5: Pattern Recognition System

Approaches to Pattern Recognition

There are four (4) main methodologies in pattern recognition systems;

  1. Statistical Approach
  2. Syntactic approach
  3. Template matching
  4. Neural networks



Applications of Pattern Recognition

  1. Image processing, segmentation and analysis
  2. Computer vision
  3. Seismic analysis
  4. Radar signal classification/analysis
  5. Speech recognition
  6. Finger print identification etc.

CONCLUSION

In summary, we introduced pattern recognition and discussed problem decomposition as important step needed for designing an effective Pattern recognition system; once a problem can be decomposed into patterns it becomes easy to recognize and match subsequent patterns. Pattern Recognition field of Artificial Intelligence is still an ongoing research  with a lot of breakthroughs.

REFERENCES

Brunelli, R. and Poggio, T. (1997). Template Matching: Matched Spatial Filters And Beyond,

Pattern Recognition, 30(5) 751-768

Ekomersial (2018) Spam filtering image retrieved online at

Investopedia (2018) Artificial Intelligence, available online at

https://www.investopedia.com/terms/a/artificial-intelligence-ai.asp

Kidiyo Kpalma, Joseph Ronsin. An Overview of Advances of Pattern Recognition Systems in

Computer Vision. Prof. Goro Obinata and Dr. Ashish Dutta. Vision Systems, Advanced Robotic Systems, 26, 2007. <hal-00143842>

Liu, J., Sun, J. and Wang, S. (2006). Pattern Recognition: An overview, International Journal

of Computer Science and Network Security (IJCSNS),  6(6) June 2006

Samuel, Arthur (1959). “Some Studies in Machine Learning Using the Game of Checkers”. IBM

Journal of Research and Development. 3 (3): 210–229.

Sonka, M.; Hlavac, V. and Boyle, R. (1993). Image Processing, Analysis and Machine Vision,

Chapman & Hall, London, UK, 193–242.

Venguerov, M. & P. Cunningham, P. (1998). Generalised Syntactic Pattern Recognition as a

Unifying Approach in Image Analysis, LNCS,  1451, 913-920, Springer

Verlag, Sydney, (Australia)

Watanabe, S. (1985). Pattern recognition: human and mechanical. Wiley, 1985

Wikipedia (2018), Decomposition retrieved online from

https://en.wikipedia.org/wiki/Decomposition_(computer_science)

 

 

 

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

Facebook
Facebook
LinkedIn
RSS