ECE471-571 Lecture 1 - Introduction

ECE471-571 Lecture 1 - Introduction

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

Recently Viewed Presentations

  • 2019 CPT Code Changes NCHIMA Fall Conference Surgery

    2019 CPT Code Changes NCHIMA Fall Conference Surgery

    Fine Needle Aspiration. When more than one FNA biopsy is performed on separate lesions, same session, same day, using different imaging modalities, report the corresponding primary code with modifier 59 for each additional imaging modality and corresponding add-on codes for...
  • Giant Structures

    Giant Structures

    Diamond is a Giant Covalent Structure. This is a giant covalent structure - it continues on and on in three dimensions. ... including the covalent bonds. This needs very large amounts of energy because the bonds are so strong. 3....
  • Subject/Title

    Subject/Title

    HQDA EXORD 101-17: The U.S. Army Commemoration of the World War I (WWI) Centennial 26 July 2017 * * * * * * * Purpose To provide an overview of HQDA EXORD 101-17 Aisne-Marne American Cemetery, France Agenda Situation /...
  • MCAS-Alt and the Every Student Succeeds Act (ESSA)

    MCAS-Alt and the Every Student Succeeds Act (ESSA)

    Every Student Succeeds Act (ESSA): The "One Percent" Rule for Statewide Alternate Assessment "The total number of students assessed in a subject using an alternate assessment aligned with alternate academic achievement standards…may not exceed 1 percent of the total number...
  • Graphs: Shortest path and mst Shortest Path: Single-source

    Graphs: Shortest path and mst Shortest Path: Single-source

    Idea: We've got a graph with edges and distances between connected edges (may be represented as a 2-dimensional array) Initiate all distances to infinity (or a really big number) except the distance from our starting vertex (0)
  • Run-on Sentences-on Sentences A run-on sentence is a

    Run-on Sentences-on Sentences A run-on sentence is a

    Document presentation format: On-screen Show Other titles: Times New Roman Arial Narrow Arial Wingdings Times Generic Run-on Sentences-on Sentences There are two types of run-on sentences: Fused Sentences Comma Splices Four Ways to Correct Run-on Sentences. Use a Semicolon Use...
  • Chapter 18

    Chapter 18

    Nominalism and the . via . moderna. undermined the belief that the Church was an objective feature of the structure of reality, and that there were other models which could serve the same purpose. Wyclif's realism produced doctrines of Bible,...
  • Writing an Expository Essay

    Writing an Expository Essay

    An expository essay is. a writing that conveys information or explains and proves something . ... He worked tirelessly at rehabilitation, ultimately regaining his speech and vision, while trying to reclaim enough balance to one day ride his snowboard again....