ECE471-571 Pattern Recognition Lecture 18: Syntactic Pattern Recognition Hairong Qi, Gonzalez Family Professor Electrical Engineering and Computer Science University of Tennessee, Knoxville http://www.eecs.utk.edu/faculty/qi Email: [email protected] Pattern Classification Statistical Approach Supervised Basic concepts: Baysian decision rule (MPP, LR, Discri.) Non-Statistical Approach
Unsupervised Decision-tree Syntactic approach Basic concepts: Distance Agglomerative method Parameter estimate (ML, BL) k-means Non-Parametric learning (kNN) Winner-takes-all
LDF (Perceptron) Kohonen maps NN (BP) Mean-shift Support Vector Machine Deep Learning (DL) Dimensionality Reduction FLD, PCA
Performance Evaluation ROC curve (TP, TN, FN, FP ) local opt (GD) cross validation Classifier Fusion majority voting NB, BKS References King Sun Fu, Syntactic Pattern Recognition, Applications. Springer, 1977 International Association for Pattern Recognition (IAPR), 1976
TPAMI, 1978 DL Davies, DW Bouldin - Pattern Analysis and Machine , 1979 (citation: 2275) 3 Key Concept If we can draw it (automatically), then we can recognize it Based on formal language 4 Philosophy A grammar generates a (possibly infinite) set of strings (pictures)
If we can design a grammar which generates a class of strings, then we can build a machine which will recognize any string in that class 5 Types of Grammars - Symbols VN: the set of non-terminal symbols VT: the set of terminal symbols P: the set of rewriting rules (productions) S: the start symbol : the empty (null) symbol 6 Type 0 Grammar
No restrictions on rewriting rules The string (whenever it occurs in a deviation) may be replaced by the string 7 Type 1 Context Sensitive is allowed only if (length) 8 Type 2 Context Free Left side must be a single non-terminal
A Example S 0S1S1 S 0S11 9 Type 3 - Regular A aB, or A a A and B are single non-terminal Is a regular grammar also context-free? 10S1 Example
Describe two types of chromosomes for recognition (submedian chromosome and telocentric chromosome) Chromosome is represented as a string, obtained by tracing the outline in clockwise direction Pattern primitives = terminal symbols 11 Example (cont) Grammar for recognition of submedian and telocentric chromosomes G = (VN, VT, P, S) Non-terminals
VN = {S, S1*, S2*, A, B, C, D, E, F} S start symbol S1* submedian chromosome S2* telocentric chromosome A armpair, B bottom, C side, D arm, E rightpart, F - leftpart 12 Example (cont) Production (rewriting rules)
S S1* S1* AA A CA A DE B bD B C C D E
e Cb d Db cD S S2* BA A A FD B Bb S2*
C AC D F C bC b D bD a Dc 13 Example (cont) babcbabdacad
ebabcbab S S1* AA ACA FDCA DcDCA bDcDCA bDbcDCA babcDCA babcbDCA babcbDbCA babcbabCA babcbabdA babcbabdAC babcbabdDEC babcbabdaEC babcbabdacDC babcbabdacaC babcbabdacad 14 Finite State Machine A regular expression determines a finite-state machine 0(010)*1
S A, A 0B, B 0C, C 1D, D 0B, B 1 15 Recognition of Abnormal ECG Regular grammar G = ({S, A, B, C, D, E, H}, {p, r, t, b}, P, S) Productions: S pA, A rB, B bC, C tD, D b, D bE, E b, E bH, E pA, H b, H bS, H pA r p b
t b b b 16 ECG (cont) Example of derivation of a well formed ECG wave: S pA prB prbC prbtD prbtbE prbtbbH prbtbbbS prbtbbbpA prbtbbbprB prbtbbbprbC prbtbbbprbtD prbtbbbprbtbE
prbtbbbprbtbb etc. Note possibility of variable number of bs One to three to accommodate normal variations of heart rate 17 The FSM p A r
B b p S b p H C t D b E b b
b b FSM 18 Education is what remains after one has forgotten everything one learned in school. -- Albert Einstein 19