WIXLIB

Pattern Recognition.A pattern is essentially an arrangement. Itis characterized by the order of theelements of which it is made, rather than bythe intrinsic nature of these elements.Norbert Wiener1

What is Pattern Recognition?zzPattern recognition (PR) is the scientificdiscipline that concerns the description andclassification (recognition) of patterns (objects)PR techniques are an important component ofintelligent systems and are used for manyapplication domains Decision making Object and pattern classification2

What is Pattern Recognition-Definitions from the literaturezzzzzz“The assignment of a physical object or event to one ofseveral pre-specified categories” –Duda and Hart“A problem of estimating density functions in a highdimensional space and dividing the space into the regions ofcategories or classes” – Fukunaga“Given some examples of complex signals and the correctdecisions for them, make decisions automatically for astream of future examples” –Ripley“The science that concerns the description or classification(recognition) of measurements” –Schalkoff“The process of giving names ω to observations x”, –SchürmannPattern Recognition is concerned with answering thequestion “What is this?” –Morse3

Pattern Recognition and Related AreaszzzzzzzzzImage processingVideo processingSpeech/audio processingNatural Language processingMachine learningNeural networksDatabase engineeringBioinformaticsMuch more .4

Machine PerceptionzBuild a machine that can recognizepatterns: Speech recognition Fingerprint identification OCR (Optical Character Recognition) DNA sequence identification5

An “Toy” Example: Fish Classificationz“Sort incoming Fish on a conveyoraccording to species using opticalsensing”Sea bassSpeciesSalmon6

zProblem Analysis Set up a camera and take some sample images toextract features Length Lightness Width Number and shape of fins Position of the mouth, etc This is the set of all suggested features to explore for use inour classifier!7

zPreprocessing Use a segmentation operation to isolate fishes from zone another and from the backgroundTo extract one fish for the next stepFeature extraction Measuring certain features of the fish to be classified Is one of the most critical steps in the patternrecognition system designzClassification Select the length of the fish as a possible feature fordiscrimination8

9

10

Adopt the lightness and add the width of thefishxT [x1, x2]FishLightness11Width

zWe might add other features that are not correlated with theones we already have. A precaution should be taken not toreduce the performance by adding such “noisy features”zIdeally, the best decision boundary should be the one whichprovides an optimal performance such as in the following figure:12

Pattern Recognition SystemszSensing Use of a transducer (camera or microphone) PR system depends on the bandwidth, theresolution sensitivity distortion of thetransducer, etc.zSegmentation and grouping Patterns should be well separated and shouldnot overlap13

14

zFeature extraction Discriminative features Invariant features with respect to translation, rotation andscale.zClassification Use a feature vector provided by a feature extractor toassign the object to a categoryzPost Processing Exploit context dependent information other than from thetarget pattern itself to improve performance15

The Design CyclezzzzzzData collectionFeature ChoiceModel ChoiceTrainingEvaluationComputational Complexity16

17

zData Collection zHow do we know when we have collected anadequately large and representative set ofexamples for training and testing the system?Feature Choice Depends on the characteristics of theproblem domain. Simple to extract, invariantto irrelevant transformation, insensitive tonoise.18

zModel Choice zUnsatisfied with the performance of our fishclassifier and want to jump to another class ofmodelTraining Use data to determine the classifier. Manydifferent procedures for training classifiersand choosing models19

zEvaluation Measure the error rate for: Different feature sets Different training methods Different training and test data setszComputational Complexity What is the trade-off between computationalease and performance?(How an algorithm scales as a function of thenumber of features, patterns or categories?)20

Supervised & Unsupervised LearningzSupervised learning zUnsupervised learning zA teacher provides a category label or cost for eachpattern in the training set ( i.e., ground truth based onexperts’ knowledge)The system forms clusters or “natural groupings” ofthe input patternsSemi-supervised learning Use both labeled and un-labeled patterns to reducethe labeling cost21

Approaches for PRzStatistical (StatPR)Patterns classified based on an underlying statistical model of thefeatures zNeural (NeurPR) zThe statistical model is defined by a family of class-conditional probabilitydensity functions Pr(x ci) (Probability of feature vector x given class ci)Classification is based on the response of a network of processing units(neurons) to an input stimuli (pattern) “Knowledge” is stored in the connectivity and strength of the synaptic weightsNeurPR is a trainable, non-algorithmic, black-box strategyNeurPR is very attractive since it requires minimum a priori knowledgewith enough layers and neurons, an ANN can create any complex decision regionSyntactic (SyntPR) Patterns classified based on measures of structural similarity “Knowledge” is represented by means of formal grammars or relationaldescriptions (graphs)SyntPR is used not only for classification, but also for description Typically, SyntPR approaches formulate hierarchical descriptions of complex patternsbuilt up from simpler sub patternsFrom: Ricardo Gutierrez-Osuna Texas A&MUniversity22

23

Decision-Theoretic MethodszDecision (discriminant) functionGiven pattern vector x ( x1 , x2 ,.xn ); x R nGiven pattern classes ω1 , ω2 ,.ωWFind W decision functions d1 (x), d 2 (x),.dW (x)such that, if x ωi then d i (x) d j (x) j 1,2,.W ; j izDecision boundaryd i ( x) d j ( x) 0 0 x ωi For two classes ωi , ω j : d ij (x) d i (x) d j (x) 0 ? 0 x ωj 25

Decision-Theoretic MethodszMatching: each class is represented by a protopypepattern vector. A predifined metric is needed zOptimal Statistical Classifiers zMinimum distance clasifierMatching by correlationBayes classifierNeural Networks PerceptronsLayersTraining24

MatchingzMinimum distance classifier Prototype def. as the mean vector of the class m j Comparing the Eucledian distances D j (x) x m j 1Decision function d j (x) xT m j mTj m j2 Decision boundary between two classesdij (x) di (x) d j (x) xT (mi m j ) 1Nj x jj 1,2,.,Wx ω jj 1,2,.,Wj 1,2,.,W1(m i m j )T (m i m j ) 02The surface is the perpendicular bisector of the line segment joining miand mj. For n 2 it is a line, for n 3 it is a plane, and for n 3 it is ahyperplane.Controlable mean separation and class spread26

MatchingzMatching by correlation Find matches of a subimage w(x,y) of size JxK within the imagef(x,y) of size MxN.c( x, y ) s t f ( s, t ) w( x s ), y t ) x 0,1,.M 1; y 0,1.N 1 a relative (normalized) correlation coefficient is prefered[f ( s, t ) f ( s, t )][w( x s ), y t ) w ] s tγ ( x, y ) 1/ 222{ s t [ f (s, t) f (s, t)] s t [w( x s), y t) w ] }vulnerable to scale changes or rotation changesThe non-normalized version can be realized in FFT domain as well27

Optimal Statistical ClassifierszOptimality in the sence that the classifier yields the lowestprobability of commiting classification error Probability that x comes from ωi: p(ωi /x) If x is assigned (wrongly) to ωj : loss Lij W Conditional averaged risk (loss) r j ( x) Lkj p (ω k / x)k 1p ( A / B ) [ p ( A) p( B / A)] / p ( B )p(x / ω k ) pdf of the patterns from class ω k ,1 Wr j ( x) Lkj p(x / ωk ) P(ω k ); where P(ω k ) probabilty of occurence of class ωkp(x) k 1 Bayes classifier minimises the cond. avaraged risk, i.e. assigns anew pattern x to the class ωi if:WWk 1q 1ri (x) r j (x) Lki p(x / ω k ) P(ω k ) Lqj p (x / ω q ) P(ω q)28

Bayes classifier (cont.)The loss for correct decision is 0, the loss for any incorrect decision is 1. Then :Lij 1 δ ij , where δ ij 1 if i j and δ ij 0 if i j.Wr j ( x ) (1 δ kj ) p ( x / ω k ) P (ω k ) p ( x ) p ( x / ω j ) P (ω j )k 1Decision : x ω i if p ( x ) p ( x / ω i ) P (ω i ) p ( x ) p ( x / ω j ) P (ω j )Equavalent ly : p ( x / ω i ) P (ω i ) p ( x / ω j ) P (ω j )Decision fuction : d j ( x ) p ( x / ω j ) P (ω j ) j 1,2,.WzTwo probabilities needed. While P(ωj) is easy to find (estimate), p(x/ωi)requires multivariate probability methods for its estimation. This is toocomplicated to be used in practice. Instead, analytical expressions(models) of the pdf are used. The necessary parameters are estimatedfrom sample patterns from each class.29

Bayes classifier (cont.)zB.C. for Gaussian pattern classes Consider 1-D case (n 1), two classes (W 2) governed byGaussian densities N(m1,σ1), N(m2,σ2)d j ( x) p( x / ω j ) P(ω j ) ( x m j )212πσ j2σ 2jeP(ω j ) j 1,2For n-dimensional case, instead of simple variance, covariancematrix is involvedp(x / ω j ) 1(2π )n/2Cj1/ 2e1 ( x m j )T ( x m j )2where m j E j {x}; C j E j {( x m j )T (x m j )}; E j {.} expected valueApproximations of E j {.} : m j 1Nj x ω j30x; C j 1Nj x ω jxxT m j m jT

Bayes classifier (cont.)zB.C. for Gaussian pattern classes Exponents allow working with natural logarithms, since logarithm isa monotonically increasing function preserving the numerical orderd j (x) ln p (x / ω j ) ln P (ω j )nn1d j ( x) ln P(ω j ) ln 2π ln C j (x m j )T C j1 (x m j222n1or d j (x) ln P(ω j ) ln C j (x m j )T C j1 (x m j22The decision functions in n-D space are hyperquadrics (quadraticfunction in n-D space).Simplifications:[[ ]]If all covariance matrices are equal linear decision functions(hyperplanes)C I, P(ωj) 1/W. Then Bayes clsfr reduces to min. distance clsfr31

Neural NetworkszPreliminaries Training patterns and training sets. The process by which a training set is used to obtain decision functions is called learning or traininge.g. the training is used to determine the parameters ofthe decision function (means, covariance matrices)The statistical properties of pattern classes often areunknown (hard to estimate). Such problems are besthandled by direct training (no need to makeassumptions regarding the unknown pdfs)Neurons: non-linear computing elements Organized in networks Learning mashines called perceptrons32

Perceptronzx0 1x1xnThe appropriate weights are applied tothe inputs, and the resulting weightedsum passed to a function whichproduces the output yw0w1wnyu i xi w i y f (u )y f (u ) f (xT w )33

Neural NetworkszPerceptron for two pattern classes (see fig. above). Weights modify the inputs to the input ot an activationfunctionDecision boundary is a hyperplane in n-D space First n coeff. establish the orientation, while wn 1determines the distance to the originFormally the free weight wn 1 can be included in thesummation part by assuming one more inputThe key problem is to find the weight vector w using agiven training set of patterns from each of two classes34

Neural NetworkszTraining algorithms Linearly separable classes: an iterative algorithm w(1) –initial weight vector (arbitrary chosen) at the k-th iterative step if y(k) ω1, and wT(k)y(k) 0, replace w(k) withw(k 1) w(k) cy(k), c is a positive correction incrementif y(k) ω2, and wT(k)y(k) 0, replace w(k) withw(k 1) w(k) cy(k)otherwise, leave w(k) unchanged w(k 1) w(k)The algorithm converges if the two training sets arelinearly separable.This is called the perceptron training theorem35