ÚVOD DO ROZPOZNÁVÁNÍ Václav Hlaváč Fakulta elektrotechnická ČVUT v Praze katedra kybernetiky, Centrum strojového vnímání
[email protected], http://cmp.felk.cvut.cz/∼hlavac
Modelování a teorie systémů.
Rozpoznávání.
Formulace Bayesovské úlohy.
Osnova přednášky
Příznakové a strukturní rozpoznávání.
1/29
K NÁZVU ROZPOZNÁVÁNÍ
Význam českého pojmu rozpoznávání chápu jako ekvivalent disciplíny anglicky nazývané pattern recognition.
Zejména v dřívějších českých publikacích z šedesátých až sedmdesátých let zazníval ve stejném smyslu i pojem rozpoznávání obrazců. Do češtiny asi přešel z původního anglického názvu přes ruský překlad—raspoznavanie obrazcov.
2/29
V ruštině obrazec odpovídá českému vzor či anglickému pattern.
MOTIVACE
Člověk je na špičce pomyslné pyramidy živočichů i proto, že je schopen přemýšlet o postupech, jakými sám uvažuje.
Panuje všeobecný zájem o strojové napodobení biologického vnímání s cílem napodobit inteligentní chování v nepříliš známém prostředí.
Základním atributem inteligentního chování je schopnost učit se na základě vnímání okolního prostředí.
3/29
Klíčová je otázka reprezentace znalosti. Přirozený jazyk je nejdokonalejší nástroj lidí pro vyjádření pozorování, pro popis jevu, formulaci úloh, jejich řešení a pro související otázky učení.
SLOŽITÉ JEVY A SYSTÉMOVÉ MYŠLENÍ
Potřeba porozumět složitým jevům například v biologii, technice nebo sociálních vědách vede k nutnosti zkoumat jevy komplexně v mnoha souvislostech.
4/29
Přístup je nazýván systémovým myšlením, aby se odlišil od newtonovské snahy zredukovat každý jev na vztahy mezi základními prvky a jejich vlastnostmi.
POJMY Z TEORIE SYSTÉMŮ
Při zkoumání složitého jevu se omezujeme na část, která nás zajímá, a říkáme jí objekt (nebo systém).
Vše ostatní, co nám z daného pohledu připadá nezajímavé, nazýváme pozadí.
Objekty většinou nezkoumáme v celé jejich složitosti. Při jednom zkoumání pozorujeme nebo měříme jen určité vlastnosti, které nám právě připadají zajímavé. Teorie systémů zde používá pojem rozlišovací úroveň.
5/29
Popis a chápání objektu se přirozeně může vyvíjet s měnící se rozlišovací úrovní. Jde o metapohled hledající kvalitativní změnu v popisu objektu.
DVA MOŽNÉ PŘÍSTUPY 6/29
Snaha o exaktní popis objektů nástroji matematiky vede zhruba řečeno ke dvěma možným přístupům: 1. Matematické modelování (v newtonovském smyslu). 2. Rozpoznávání.
MATEMATICKÉ MODELOVÁNÍ
Podstatné rysy objektu se napodobují formou matematických rovnic. Často se hledá relace mezi vstupem a výstupem.
Obvykle blíže k newtonovskému pojetí. Snaha o co nejpodrobnější a deterministické vysvětlení.
Příklad: dobrý matematický model elektrárenského kotle v teorii řízení předpovídá téměř stejné odezvy na vstupní signály jako kotel sám.
7/29
V mnoha případech nejsme schopni matematický model vůbec vytvořit (např. model fungování lidského těla).
Pattern recognition assigns observations according to some decision rule to a priori known classes of objects.
Equivalence classes (reflexivity, symmetry, transitivity).
8/29
Objects within classes are more similar to each other than objects from different classes.
PATTERN RECOGNITION AS AN ALTERNATIVE TO MODELLING
The understanding to the object is often weaker in pattern recognition than in modelling.
9/29
The advantage of PR is that a human creating the recognition rule does not need to understand the complex nature of the object.
ROLE OF LEARNING IN PATTERN RECOGNITION
A decision rule can be learned empirically from many observed examples. Supervised learning based on the training set comprising of observations and corresponding decisions assigned by a teacher (an expert). Unsupervised learning seeks for similarities among observations without having an expert classification at hand.
PATTERN RECOGNITION AND APPLICATIONS
10/29
Pattern recognition theory and tools can be separated from applications.
Getting Object formal description
Object representation
Classification
Class label
PATTERN RECOGNITION, MOTIVATION EXAMPLE Object (situation) is described by two parameters: x – observablefeature (also observation). k – hidden parameter (state, special case—a class). Example statistical PR: jockeys and and basketballists. height [cm]
jockeys
basketballists
weight [kg]
11/29
BAYESIAN DECISION MAKING 12/29
Bayesian task of statistical decision making seeks for sets X (observations), K (hidden states) and D (decisions), a joint probability pXK : X × K → R and the penalty function W:K × D → R a strategy Q: X → D which minimizes the Bayesian risk XX R(Q) = pXK (x, k ) W (k, Q(x)) . x∈X k∈K
The solution to the Bayesian task is the Bayesian strategy Q minimizing the risk. Notes: deterministic strategy, separation into convex subsets.
PŘÍKLAD 2 SKRYTÉ STAVY, 3 ROZHODNUTÍ
13/29
Objekt: pacient vyšetřovaný lékařem. Pozorování X: některé měřitelné parametry (teplota, krevní tlak, . . . ). 2 skryté stavy K = {zdravý, nemocný}. 3 rozhodnutí D = {neléčit, slabý lék, silný lék}. Pokutová funkce W : K × D → R W (k, d) neléčit slabý lék silný lék nemocný 10 2 0 zdravý 0 5 10
GENERALITY OF BAYESIAN FORMULATION 14/29
Statistical pattern recognition results are very general. Properties of sets X (observations) and K (hidden parameters) were not constrained.
Sets X and K can have formally (mathematically) diversed structure.
Motto: “Let set X (observations) and set K (hidden states) be two finite sets.”
The approach can be and is used in very different applications.
Observation X can be a number, a symbol, a function of two variables (e.g., an image), a graph, other algebraical structure.
DVĚ ZÁKLADNÍ SKUPINY METOD ROZPOZNÁVÁNÍ
Objekty jsou reprezentovány jako body ve vektorovém prostoru.
1. Statistické (příznakové) rozpoznávání.
Souřadné osy prostoru odpovídají jednotlivým číselně vyjádřeným pozorováním.
Mezi pozorováními existuje struktura a ta je reprezentována.
2. Strukturní rozpoznávání.
Nejrozvinutější a nejstarší je reprezentace struktury gramatikami.
15/29
KOMPONENTY ROZPOZNÁVACÍHO SYSTÉMU
Objekt
Senzory a pøedzpracování
Uèitel
Výbìr pøíznakù
Klasifikátor
Algoritmus uèení
16/29
Pøiøazení ke tøídì
UMĚLÉ NEURONOVÉ SÍTĚ 17/29
Model dopředné neuronové sítě (McCulloch, Pitts, 1943).
ČTENÍ O ROZPOZNÁVÁNÍ
Duda Richard O., Hart Peter E., Stork, David G.:, Pattern Classification, John Wiley & Sons, New York, USA, 2001, 654 s.
18/29
Schlesinger M.I., Hlaváč V.: Ten lectures on statistical and syntactic pattern recognition, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002, 521 p. (předchůdce v češtině, Vydavatelství ČVUT 1999).
NÁSTROJ PRO EXPERIMENTY Franc V. (doktorand CMP): Statistical Pattern Recognition Toolbox, nad MATLABem, 2000 - stále rozvíjen, http://cmp.felk.cvut.cz
STATISTICKÉ ROZPOZNÁVÁNÍ 19/29
Popis objektu n-ticí čísel, která odpovídají n podstatným vlastnostem a jsou oceněny reálným číslem (míra vlastnosti). Příznakový prostor. n-tice popisující jeden objekt ⇒ bod v příznakovém prostoru. Hledá se reprezentace objektu pro klasifikaci v příznakovém prostoru, v níž body jedné třídy tvoří kompaktní shluky dobře oddělitelné rozhodovací strategií. S příznaky se zde zachází metodami matematické statistiky. Naučení klasifikátoru ze statisticky významné trénovací množiny.
Recommendations are based on concepts as: mathematical expectation, dispersion, correlation, covariance matrix, . . . Tools of mathematical statistics can be used to solve many practical problems provided the random object can be represented by a number (or a vector of numbers).
20/29
Substantial success in statistical pattern recognition for vectors of features.
APPLICATION OF MATHEMATICAL STATISTICS The most developed part of statistics is the statistics of random numbers.
Failure for images f (x, y ), where f is brightness or color of a pixel and x, y are pixel coordinates.
21/29
Učení z příkladů—v rozpoznávání se ví, kterým souvisejícím úlohám rozumí. Je zřejmé, které úlohy již nejsou pohádkami.
CO SE UMÍ VE STATISTICKÉM ROZPOZNÁVÁNÍ (1) ?
Tato znalost je vyjádřena matematicky formulovanými větami. Lze rozlišit • co se umí, • co nelze řešit nebo nelze řešit s polynomiální složitostí, • o čem nelze nic říci.
Linear classifiers and their learning. E.g., a popular special case—Support Vector Machines. Learning.
Estimate of needed length of training multi-set for prescribed precision and reliability of classification (e.g., Vapnik’s theory of learning).
Embedding of a non-linear problem to a higher dimensional vector space (feature space straightening, allowing linear classifiers), kernel methods.
WHAT IS KNOWN IN STATISTICAL PATTERN RECOGNITION (2) ? 22/29 Solution to some non-Bayesian tasks, e.g., class “I don’t know” can be introduced. Tasks with non-random interventions.
Unsupervised learning, variants of EM algorithm.
Many researchers treat as self-evident the assumption, that n-tuple can be understood as a point in n-dimensional linear space.
SET OF OBSERVATIONS versus LINEAR SPACE 23/29 One observation about one object is n-tuple of numbers.
On the other hand, pattern recognition theory is more general. Many researchers wrongly assumed formalization of the set X (observations) in linear space as the only possible.
Example: The image n × n pixels can be ordered row-wise as n2 numbers (features), e.g., eigen images.
24/29
Pro účelné použití statistických metod musí být množiny X a K vyjádřeny co nejkonkrétněji.
OBECNOST STATISTICKÉHO ROZPOZNÁVÁNÍ JE I NEVÝHODOU
Z nepřehledné množiny možností musí vybrat taková, která odpovídá příslušné aplikační úloze. To nemusí být vůbec lehké.
STRUKTURNÍ ROZPOZNÁVÁNÍ
Objekt je popsán primitivy, tj. nejjednoduššími kvalitativními charakteristikami.
Strukturní rozpoznávání se opírá o teorii formálních jazyků. Gramatiky. Syntaktická analýza.
Primitiva tvoří abecedu jazyka. Vztahy mezi primitivy lze vyjádřit relacemi.
Kolik je tříd, tolik je potřebných gramatik.
Slovo odpovídající určité třídě generuje právě jedna gramatika.
Rozpoznávání = syntaktická analýza.
25/29
Problém: zašuměná data.
PARAMETERS AND THEIR STRUCTURE 26/29
Statistical pattern recognition results are very general. Properties of sets X (observations) and K (hidden parameters) were not constrained, e.g., in Bayesian task.
Sets X and K can have formally (mathematically) diverse structure.
Motto: “Let set X (observations) and set K (hidden states) be two finite sets.”
The approach can be an is used in very diverse applications.
PŘÍKLADY RŮZNÉ STRUKTURY JEDNOHO POZOROVÁNÍ
27/29
Hmotnost pacienta - kladné reálné číslo [kg]. Dobře strukturovaná množina (sčítání, násobení, invertování, atd.). Známka na vysvědčení - {1, 2, 3, 4, 5}. Úplně uspořádaná množina, nic víc, =, <, >. Čísla tramvajových linek - výčtový typ. Tramvaj číslo 22 není o nic horší/lepší než tramvaj číslo 12.
STRUKTURA VZTAHŮ MEZI VÍCE PŘÍZNAKY ILUSTRACE Uvažujme n-tici x1, x2, . . . , xn
28/29
Údaje o jednom pacientovi. Věk, výška, hmotnost, teplota, krevní tlak dolní, krevní tlak horní, množství cukru v moči ... Nic by se nestalo, kdyby příznaky byly očíslovány jinak. Žádná struktura. Jednotlivá čísla se chápou jako symboly v abstraktní abecedě. n-krát měření údaje v pravidelných časových intervalech. Posloupnost. Index příznaku má význam celého čísla. Množina indexů má jasnou strukturu.
Still in its infancy. Disconnected islands of knowledge.
CONNECTION BETWEEN STATISTICAL AND STRUCTURAL PATTERN RECOGNITION
Progress achieved in:
29/29
• Recognition of Markovian chains and acyclic structures (also Bayesian networks). • Levenstein dissimilarity between an expression and regular language (≈ edit distance). • Consistent labelling (Markovian fields, spacial case). • Generalization of 2D context free grammars.
