Neural Networks and Fuzzy Systems

Pattern Recognition

Rizoan Toufiq

Assistant Professor

Department of Computer Science & Engineering

Rajshahi University of Engineering & Technology

Introduction

Rizoan Toufiq, Assistant Professor, Dept. of CSE, RUET

2

Pattern Recognition

Artificial Neural Network

Problem-1

Problem-2

Problem-n

Apply

Other Methods/techniques

Introduction

• Currently the dominating area for the application of NN.
• It is a large area of computer science in itself.

Pattern Recognition In Perspective

• Patterns → alphabetic characters, text processing, handwritten text, speech, images, stock market trends, etc.

​

• One of the simpler pattern recognition tasks → Classification
• Simplest classifier – template matching technique –
• each letter is read into a fixed size frame and the frame is compared to a template of all the possible characters but cannot apply to all sizes.
• Problem→ change typeface of the text/ new font / handeritten text

​

• Complex domain → image processing, speech and stock market tends

Pattern Recognition – A Definition

• A pattern recognition system can be considered as a two stage device
• Feature extraction
• a measurement taken on the input pattern
• Example : to distinguish ‘E’ and ‘F’ – we need to compare the number of vertical and horizontal strokes.
• Classification
• Map these input features onto a classification state
• Given the input features, the classifier must decide which type of class category they match most closely – i.e. – distance metrics and probability theory.

Feature Vectors and Feature Space

• If we make n measurements on our input pattern, each of which is a unique feature, then we can use algebraic notation to create a set of these features and call it a feature vector.

​

• The dimensionality of the vector – the number of elements in it – creates an n dimensional feature space.

Feature Vectors and Feature Space

• The simplest way to describe feature space is to consider a simple two-dimensional example – two measurements on the pattern to form the feature vector.

​

• Example – to distinguish between ballet dancers from rugby players – two distinct measures – height and weight – take a series of height and weight measurements then plot a two-dimensional Euclidean plane (x₁, x₂) that defines our feature spaces – Fig. 2.1.

​

• This plot help us to visualize the concept of our feature space.

Feature Vectors and Feature Space

• This plot help us to visualize the concept of our feature space.

Discriminant Functions

• Fig. 2.2 – rugby-player/ ballet-dancer classification problem – samples form two distinct cluster – we could define boundary/ line to separate them – a decision boundary – discriminating function.
• A function that discriminate one class from another class.

Discriminant Functions

• The simplest function that separate the two clusters is a straight line.

​

• It represents a very widely used category of classifiers known as linear classifiers.

Classification Techniques

• Pattern classification techniques :
• numeric and non-numeric.
• Numeric technique –
• deterministic and statistical measures – made on the geometric pattern space.
• Non-numeric techniques –
• based on symbolic processing – i.e. – fuzzy set.

​

​

• Our concern - the numeric techniques –
• followed the same by neural computing since symbolic data manipulation is based on traditional AI approach.

Classification Techniques

• To implement discriminant function analysis:
• Nearest neighbor classification: Distance metrics, Euclidean, City Block, Square distance.
• Linear classifier
• Statistical techniques: Bayesian classifier
• Neural Networks

Nearest neighbor classification

Nearest neighbor classification

• We wish to decide to which of the two the unclassified pattern, X, belongs.

​

• We can define discriminating function as:
• f(X) = closest(class1) – closest(class2)

​

• f(X) > 0 → Belongs to class2
• f(X) < 0 → Belongs to class1

Nearest neighbor classification

Nearest neighbor classification

• However for rogue pattern, fig. 2.4, that has membership of one class but does in fact lie closer to another class.

​

• If our unclassified input is measured against rogue samples, it will invariably result in misclassification.

​

• To overcome rogue pattern – take average measurements or known as “K” nearest neighbor classification.

​

• The “K” is the number of neighboring samples.

Distance Metrics

• Nearest Neighbor pose problem of finding the distance.
• Methods of measurement based on distance:
• Hamming distance
• Euclidean distance
• City block distance
• Square distance

Distance Metrics

• Hamming distance
• For two vector

​

​

​

• The Hamming distance is found by evaluating the difference between each component of one vector with the corresponding component of the other, and summing these differences to provide an absolute value for the variation between the two vectors.
• The measure is defined by:

Distance Metrics

• Hamming distance
• The Hamming distance is often used to compare binary vectors.
• In actual fact the Hamming distance measure for binary data can be performed simply by the exclusive-OR function since

Distance Metrics

• Euclidean distance
• Two vectors ( X and Y)
• The Euclidean distance which is defined by:

​

​

​

• where n is the dimensionality of the vector.

Distance Metrics

• Euclidean distance
• For the two-dimensional example we have drawn, this gives us:

​

​

​

​

• A special case is given for binary vectors where the metric is then equivalent to the square root of the Hamming distance

​

​

​

​

• The metric is used in a neural network learning algorithm

Distance Metrics

• City block distance (Manhattan)
• A simplified version of the Euclidean distance measure is the city block measure.
• This method performs the Euclidean measure without calculating the squared or square root functions. Thus

​

​

​

​

​

• It is much faster to compute than the Euclidean

Distance Metrics

• City block distance (Manhattan)

Distance Metrics

• Square distance
• Simplifying the Euclidean distance measure still further-but consequently adding still more error.

​

• With this measure the distance between two vectors is defined as the maximum of the differences between each element of the two:

Distance Metrics

• Square distance
• This again defines a square boundary for points equidistant from a vector. It is however a larger square than that of the city block, and is consequently a coarser measure.
• As before, however, the error is tolerated as a compromise between speed and accuracy.

Summary

Rizoan Toufiq, Assistant Professor, Dept. of CSE, RUET

26

• Pattern recognition → feature extraction and classification.
• Features are pattern measurements used for comparison.
• Discriminant functions partition up feature space.
• A number of different distance metrics are used.

Read Task

Rizoan Toufiq, Assistant Professor, Dept. of CSE, RUET

27

B1: Neural Computing - An Introduction - R Beale and T Jackson, Publisher: Adam Hilger, 1990 IOP Publishing Ltd.

Chapter 2: Pattern Recognition

Query???

Rizoan Toufiq, Assistant Professor, Dept. of CSE, RUET

28