Pattern Matching AI.pdf

Artificial INtelligence

1. 1
Pattern Recognition
Why?
•To provide machines with perception & cognition
capabilities so that they could interact independently
with their environments.
Pattern Recognition
•a natural ability of human
•based on some description of an object, such
description is termed Pattern.

2. 2
Patterns and Pattern Classes
•Almost anything within the reach of our five senses can
be chosen as a pattern:
–Sensory patterns: speech, odors, tastes
–Spatial patterns: characters, fingerprints, pictures
–Temporal patterns: waveforms, electrocardiograms, movies
–Conceptual recognition for abstract items
(We will limit ourselves to deal with only physical objects/
events, but NOT abstract entities, say, concepts.)
•A pattern classis a group of patterns with certain
common characteristics.

3. 3
Pattern Recognition
•Pattern Recognitionis the science to assign an
object/event of interest to one of several prespecified
categories/classes based on certain measurements or
observations.
•Measurementsare usually problem dependent.
E.g.weight or height for basketball players/jockeys
color for apples/oranges
•Feature vectorsrepresent measurements as
coordinates of points in a vector space (feature space).

4. 4
Pattern Recognition SystemsDeterministic Statistic
Mathematical
Syntactic Linguistic
Structural
PR systems

5. 5
Statistical Pattern Recognition
•Taps into the vast and thorough knowledge of statistics
to provide a formal treatment of PR.
•Observations are assumed to be generated by a state of
nature
–data can be described by a statistical model
–model by a set of probability functions
•Strength: many powerful mathematical “tools” from
the theory of probability and statistics.
•Shortcoming: it is usually impossible to design
(statistically) errorfree systems.

6. 6
Supervised vs. Unsupervised
Supervised PR
•Representative patterns from each pattern class under
consideration are available.
•Supervised learning.
Unsupervised PR
•A set of training patterns of unknown classification is
given.
•Unsupervised learning.

7. 7
Decision Boundary

8. Examples of Patterns
Crystal patterns at atomic and molecular levels
Their structures are represented by 3D graphs and can be described by
deterministic grammar or formal language

9. Examples of Patterns
Constellation patterns in the sky.
The constellation patterns are represented by 2D (often planar) graphs
Human perception has strong tendency to find patterns from anything. We see patterns
from even random noise ---we are more likely to believe a hidden pattern than denying it
when the risk (reward) for missing (discovering) a pattern is often high.

10. Examples of Patterns
Biology pattern ---morphology
Landmarks are identified from biologic forms and these patterns are then
represented by a list of points. But for other forms, like the root of plants,
Points cannot be registered crossing instances.
Applications: biometrics, computational anatomy, brain mapping, …

11. Examples of Patterns
Pattern discovery and association
Statistics show connections between the shape of one’s face (adults)
and his/her Character. There is also evidence that the outline of children’s
face is related to alcohol abuse during pregnancy.

12. Examples of Patterns
We may understand patterns of brain activity and find relationships
between brain activities, cognition, and behaviors
Patterns of brain activities:

13. Examples of Patterns
Patterns with variations:
1. Expression –geometric deformation
2. lighting ---photometric deformation
3. 3D pose transform
4. Noise and occlusion

14. Examples of Patterns
A wide variety of texture patterns are generated by various stochastic processes.
How are these patterns represented in human brain?

15. Pattern Recognition

16. What is Pattern Recognition?
⚫Patternrecognitionisasub-topicofmachine
learning.PRisthesciencethatconcernsthe
descriptionorclassification(recognition)of
measurements.Itcanbedefinedas:
“Theactoftakinginrawdataandtakingan
actionbasedonthecategoryofthedata".
“The assignment of a physical object or event to
one of several prespecified categories”.

17. ⚫Apatternisanobject,processoreventthatcan
begivenaname.
⚫Apatternclass(orcategory)isasetofpatterns
sharingcommon attributesandusually
originatingfromthesamesource.
⚫Duringrecognition(orclassification)given
objectsareassignedtoprescribedclasses.
⚫Aclassifierisamachinewhichperforms
classification.

18. Pattern recognition system
Acompletepatternrecognitionsystemconsists
of:-
⚫Sensor-gatherstheobservationstobe
classifiedordescribed.
⚫Featureextractionmechanism-computes
numericorsymbolicinformationfromthe
observations.
⚫Classificationordescriptionscheme-that
doestheactualjobofclassifyingordescribing
observations,relyingontheextractedfeatures.

19. Algorithms used by pattern recognition systems
DESCRIPTION CLASSIFICATION
PATTERN RECOGNITION ALGORITHMS
data
identification
features

20. Description task
Thedescriptiontasktransformsdatacollectedfromthe
environmentintofeatures.
Thedescriptiontaskcaninvolveseveraldifferent,but
interrelated,activities:
⚫Preprocessing:-To modify the data
⚫Feature extraction:-To generate features
--Elementary features
--Higher order features
⚫Feature selection:-To reduce features

21. Description task (cont.)
⚫The end result of the description task is a
set of features, commonly called a feature
vectorwhich constitutes a representation
of the data.

22. Classification task
⚫Usesaclassifiertomapafeaturevectortoa
group.
⚫Suchamappingcanbespecifiedbyhandor,
morecommonly,atrainingphaseisusedto
inducethemappingfromacollectionoffeature
vectorsknowntoberepresentativeofthe
variousgroupsamongwhichdiscriminationis
beingperformed(i.e.,thetrainingset).
⚫Onceformulated,themappingcanbeusedto
assignanidentificationtoeachunlabeled
featurevectorsubsequentlypresentedtothe
classifier.

23. What makes a ”good” feature vector

24. Approachesto pattern recognition
Thereare2fundamentalapproachesto
implementapatternrecognitionsystem:
1.Statistical(ordecisiontheoretic):-Statistical
patternrecognitionisbasedonstatistical
characterizationsofpatterns,assumingthatthe
patternsaregeneratedbyaprobabilistic
system.
2.Syntactic(orstructural):-Syntacticalpattern
recognitionisbasedonthestructural
interrelationshipsoffeatures.

25. Statistical pattern recognition
⚫Itdrawsfromestablishedconceptsinstatistical
decisiontheorytodiscriminateamongdata
fromdifferentgroupsbaseduponquantitative
featuresofthedata.
⚫Thereareawidevarietyofstatisticaltechniques
thatcanbeusedwithinthedescriptiontaskfor
featureextraction,rangingfromsimple
descriptivestatisticstocomplextransformations.

26. Syntactic pattern recognition
⚫Syntacticpatternrecognitionorstructuralpattern
recognitionisaformofpatternrecognition,whereitems
arepresentedpatternstructureswhichcantakeinto
accountmorecomplexinterrelationshipsbetween
featuresthansimplenumericalfeaturevectorsusedin
statisticalclassification.
⚫It can be used (instead of statistical pattern recognition)
if there is clear structure in the patterns.
⚫One way to present such structure is strings of a formal
language. In this case differences in the structures of the
classes are encoded as different grammars.

27. Approachesto pattern recognition

28. Difference Between Statistical and
Structural Pattern Recognition
Statistical Structural
Foundation Statistical decision theoryHuman perception and
cognition
Description Quantativefeatures
Fixed no. of features
Ignores feature relationships
Semantics from feature
position
Morphological primitives
Variable number of primitives
Captures primitive relationships
Semantics from primitive
encoding
ClassificationStatistical classifiers Parsing with syntactic
grammars

29. Neural networks pattern recognition
⚫An“ArtificialNeuralNetwork"(ANN),isa
mathematicalmodelorcomputationalmodel
basedonbiologicalneuralnetworks.Itconsists
ofaninterconnectedgroupofartificialneurons
andprocessesinformationusingaconnectionist
approachtocomputation.
⚫Inmorepracticaltermsneuralnetworksarenon-
linearstatisticaldatamodelingtools.Theycan
beusedtomodelcomplexrelationships
betweeninputsandoutputsortofindpatternsin
data.

30. Neural networks pattern recognition
⚫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 weights.
⚫NeurPRisatrainable,non-algorithmic,black-box
strategy.
⚫NeurPRis very attractive since
-it requires minimum a priori knowledge
-with enough layers and neurons, an ANN can create
any complex decision region.