Pregled postojeće metode prepoznavanje uzoraka

L.P. Popova , I O. Datiev

Sposobnost "prepoznavanja" smatra se glavnim svojstvom ljudskih bića, kao i drugih živih organizama. Prepoznavanje uzoraka je dio kibernetike koji razvija principe i metode za klasifikaciju i identifikaciju objekata, pojava, procesa, signala, situacija – svih onih objekata koji se mogu opisati konačnim skupom nekih karakteristika ili svojstava koja karakteriziraju objekt.

Slika je opis objekta. Slike imaju karakteristično svojstvo koje se očituje u činjenici da se upoznaju konačan broj pojava iz istog skupa omogućava proizvoljno prepoznavanje veliki broj njenih predstavnika.

Postoje dva glavna pravca u teoriji prepoznavanja obrazaca:

proučavanje moći prepoznavanja koje posjeduju ljudska bića i drugi živi organizmi;

razvoj teorije i metoda za konstruisanje uređaja namenjenih rešavanju pojedinačnih problema prepoznavanja obrazaca u određenim oblastima primene.

Nadalje, članak opisuje probleme, principe i metode za implementaciju sistema za prepoznavanje obrazaca koji se odnose na razvoj drugog smjera. U drugom dijelu članka razmatraju se neuromrežne metode prepoznavanja obrazaca, koje se mogu pripisati prvom smjeru teorije prepoznavanja obrazaca.

Problemi izgradnje sistema za prepoznavanje slika

Zadaci koji se javljaju u izgradnji sistema za automatsko prepoznavanje uzoraka obično se mogu klasificirati u nekoliko glavnih područja. Prvi od njih se odnosi na predstavljanje početnih podataka dobijenih kao rezultata mjerenja za objekt koji treba prepoznati. problem osetljivosti. Svaka izmjerena vrijednost je neka "karakteristika slike ili objekta. Pretpostavimo, na primjer, da su slike alfanumerički znakovi. U ovom slučaju, mjerna mrežnica, slična onoj prikazanoj na slici 1(a), može se uspješno koristiti Ako se retina sastoji od n-elemenata, tada se rezultati mjerenja mogu predstaviti kao vektor mjerenja ili vektor slike ,

gdje svaki element xi uzima, na primjer, vrijednost 1 ako je kroz i-ta ćelija mrežnica prolazi kroz sliku karaktera, a vrijednost je 0 inače.

Razmotrite sl. 2(b). U ovom slučaju, slike su kontinuirane funkcije (vrste zvučnih signala) varijable t. Ako se vrijednosti funkcije mjere u diskretnim tačkama t1,t2, ..., tn, tada se vektor slike može formirati uzimanjem x1= f(t1),x2=f(t2),... , xn = f(tn).

Slika 1. Mjerenje retine

Drugi problem prepoznavanja obrazaca vezan je za selekciju karakteristične karakteristike ili svojstva iz dobijenih početnih podataka i smanjenje dimenzije vektora slike. Ovaj problem se često definiše kao problem pretprocesiranje i izbor karakteristika.

Karakteristike klase slika su karakteristična svojstva, zajedničko za sve slike ove klase. Osobine koje karakterišu razlike između pojedinačnih klasa mogu se tumačiti kao međuklasne karakteristike. Unutarklasne karakteristike zajedničke za sve klase koje se razmatraju ne nose korisne informacije u smislu priznavanja i ne mogu se uzeti u obzir. Izbor karakteristika se smatra jednim od važnih zadataka vezanih za izgradnju sistema prepoznavanja. Ako rezultati mjerenja omogućavaju dobivanje kompletnog skupa razlikovnih karakteristika za sve klase, stvarno prepoznavanje i klasifikacija uzoraka neće uzrokovati posebne poteškoće. Automatsko prepoznavanje bi se tada svelo na jednostavan proces uparivanja ili procedure kao što je traženje tablica. U većini praktičnih problema prepoznavanja, međutim, definicija kompletan set Ispostavlja se da je razlikovanje karakteristika izuzetno teško, ako ne i nemoguće. Iz originalnih podataka obično je moguće izdvojiti neke od karakteristika i koristiti ih za pojednostavljenje procesa automatskog prepoznavanja uzoraka. Konkretno, dimenzija mjernih vektora može se smanjiti korištenjem transformacija koje minimiziraju gubitak informacija.

Treći problem povezan sa konstrukcijom sistema za prepoznavanje obrazaca je pronalaženje optimalnih procedura odlučivanja koje su neophodne za identifikaciju i klasifikaciju. Nakon što prikupljeni podaci o obrascima koje treba prepoznati budu predstavljeni tačkama ili vektorima mjerenja u prostoru uzorka, neka mašina shvati kojoj klasi uzoraka ti podaci odgovaraju. Neka mašina bude dizajnirana da razlikuje M klase, označene sa w1, w2, ... ..., wm. U ovom slučaju se može smatrati da se prostor slike sastoji od M regiona, od kojih svaka sadrži tačke koje odgovaraju slikama iz iste klase. U ovom slučaju, problem prepoznavanja se može posmatrati kao konstruisanje granica regiona odlučivanja koji razdvajaju M klase na osnovu registrovanih vektora merenja. Neka su ove granice definirane, na primjer, funkcijama odlučivanja d1(h),d2(x),..., dm(h). Ove funkcije, koje se nazivaju i diskriminantne funkcije, su skalarne i jednovrijedne funkcije slike x. Ako je di (x) > dj (x), onda slika x pripada klasi w1. Drugim riječima, ako i-ti odlučujući funkcija di(x) ima najveća vrijednost, onda je smislena ilustracija takve automatske klasifikacione šeme zasnovane na implementaciji procesa donošenja odluka prikazana na Sl. 2 (na dijagramu "GR" - generator odlučujuće funkcije).

Slika 2. Šema automatske klasifikacije.

Funkcije odlučivanja mogu se dobiti na više načina. U onim slučajevima kada su dostupne potpune a priori informacije o prepoznatljivim obrascima, funkcije odlučivanja se mogu odrediti upravo na osnovu ovih informacija. Ako su dostupne samo kvalitativne informacije o obrascima, mogu se napraviti razumne pretpostavke o obliku funkcija odlučivanja. B poslednji slučaj, granice regiona odlučivanja mogu značajno odstupati od pravih, te je stoga neophodno stvoriti sistem koji će nizom uzastopnih prilagođavanja postići zadovoljavajući rezultat.

Objekti (slike) koje treba prepoznati i klasificirati pomoću automatskog sistema za prepoznavanje uzoraka moraju imati skup mjerljivih karakteristika. Kada su za cijelu grupu slika slični rezultati odgovarajućih mjerenja, smatra se da ti objekti pripadaju istoj klasi. Svrha sistema za prepoznavanje uzoraka je da na osnovu prikupljenih informacija odredi klasu objekata sa karakteristikama sličnim onima izmjerenim za prepoznatljive objekte. Ispravnost prepoznavanja zavisi od količine razlikovnih informacija sadržanih u izmjerenim karakteristikama i efikasnosti korištenja ovih informacija.

Osnovne metode za implementaciju sistema za prepoznavanje uzoraka

Prepoznavanje uzoraka je zadatak konstruiranja i primjene formalnih operacija na numeričkim ili simboličkim prikazima objekata stvarnog ili idealnog svijeta, čiji rezultati odražavaju relacije ekvivalencije između ovih objekata. Relacije ekvivalencije izražavaju pripadnost evaluiranih objekata nekim klasama, koje se smatraju nezavisnim semantičkim jedinicama.

Prilikom konstruisanja algoritama za prepoznavanje, klase ekvivalencije može postaviti istraživač koji koristi svoje smislene reprezentacije ili koristi eksterne Dodatne informacije o sličnosti i različitosti objekata u kontekstu problema koji se rješava. Zatim se govori o "razboritosti prema učitelju". Inače, tj. kada automatizovani sistem rješava problem klasifikacije bez uključivanja vanjskih informacija o obuci, govori se o automatskoj klasifikaciji ili “nenadziranom prepoznavanju”. Većina algoritama za prepoznavanje uzoraka zahtijeva uključivanje veoma značajne računarske snage, koju može obezbijediti samo kompjuterska tehnologija visokih performansi.

Razni autori (Yu.L. Barabash, V.I. Vasiliev, A.L. Gorelik, V.A. Skripkin, R. Duda, P. Hart, L.T. Kuzin, F.I. Peregudov, F.P. Tarasenko, Temnikov F.E., Afonin V.A., Dmitriev V.I. Gonzalez, P. Winston, K. Fu, Ya.Z. Tsypkin i drugi) daju drugačiju tipologiju metoda prepoznavanja obrazaca. Neki autori razlikuju parametarsko, neparametarsko i heurističke metode, drugi - razlikuju grupe metoda zasnovanih na istorijski uspostavljenim školama i trendovima u ovoj oblasti.

Istovremeno, poznate tipologije ne uzimaju u obzir jednu veoma značajnu karakteristiku, koja odražava specifičnosti načina prezentovanja znanja o predmetna oblast koristeći neki formalni algoritam za prepoznavanje obrazaca. D.A. Pospelov identifikuje dva glavna načina predstavljanja znanja:

Intenzivna reprezentacija - u obliku dijagrama odnosa između atributa (obilježja).

Ekstenzivna reprezentacija - korištenje konkretne činjenice(predmeti, primjeri).

Treba napomenuti da je postojanje ove dvije grupe metoda prepoznavanja: onih koje rade sa karakteristikama i onih koje rade sa objektima, duboko prirodno. Sa ove tačke gledišta, nijedna od ovih metoda, uzeta odvojeno od druge, ne omogućava formiranje adekvatnog odraza predmetnog područja. Između ovih metoda postoji odnos komplementarnosti u smislu N. Bora, stoga bi obećavajući sistemi prepoznavanja trebali omogućiti implementaciju obje ove metode, a ne bilo koje od njih.

Dakle, klasifikacija metoda prepoznavanja koju je predložio D. A. Pospelov zasniva se na osnovnim zakonima koji leže u osnovi ljudskog načina spoznaje uopšte, što ga stavlja u veoma poseban (privilegovan) položaj u odnosu na druge klasifikacije, koje na ovoj pozadini izgledaju lakši i veštački.

Intenzivne metode

Posebnost intenzivnih metoda je da se koriste kao elementi operacija u konstrukciji i primjeni algoritama za prepoznavanje uzoraka. razne karakteristike karakteristike i njihove veze. Takvi elementi mogu biti individualne vrednosti ili intervale vrijednosti karakteristika, srednje vrijednosti i varijanse, matrice odnosa karakteristika, itd., na kojima se izvode radnje, izražene u analitičkom ili konstruktivnom obliku. Pritom se objekti u ovim metodama ne smatraju integralnim informacijskim jedinicama, već djeluju kao indikatori za procjenu interakcije i ponašanja njihovih atributa.

Grupa metoda intenzivnog prepoznavanja obrazaca je opsežna, a njena podjela na podklase je donekle proizvoljna:

– metode zasnovane na procjenama gustine distribucije vrijednosti karakteristika

– metode zasnovane na pretpostavkama o klasi funkcija odlučivanja

– logičke metode

– lingvističke (strukturalne) metode.

Metode zasnovane na procjenama gustine distribucije vrijednosti karakteristika. Ove metode prepoznavanja uzoraka su posuđene iz klasična teorija statističke odluke, u kojem se predmeti proučavanja razmatraju kao realizacije višedimenzionalnog slučajna varijabla raspoređeni u prostoru obeležja prema nekom zakonu. Oni su zasnovani na Bayesovoj šemi odlučivanja koja se poziva na apriorne vjerovatnoće objekata koji pripadaju određenoj prepoznatljivoj klasi i uslovne gustine distribucije vrijednosti vektora karakteristika. Ove metode se svode na određivanje omjera vjerovatnoće u raznim poljima višedimenzionalni prostor karakteristika.

Grupa metoda zasnovanih na procjeni gustoće distribucije vrijednosti karakteristika direktno je povezana sa metodama diskriminantne analize. Bayesov pristup odlučivanju je jedan od najrazvijenijih u modernoj statistici, tzv. parametarske metode, za koje se smatra da je poznat analitički izraz zakona raspodjele (u ovaj slučaj normalni zakon) i treba procijeniti samo mali broj parametara (srednji vektori i matrice kovarijanse).

Ova grupa također uključuje metodu za izračunavanje omjera vjerovatnoće za nezavisne karakteristike. Ova metoda, sa izuzetkom pretpostavke o nezavisnosti karakteristika (koja u stvarnosti gotovo nikada nije ispunjena), ne zahtijeva poznavanje funkcionalnog oblika zakona raspodjele. Može se pripisati neparametarskim metodama.

Druge neparametarske metode, koje se koriste kada je oblik krivulje gustine distribucije nepoznat i ne mogu se napraviti pretpostavke o njegovoj prirodi, zauzimaju poseban položaj. To uključuje dobro poznatu metodu višedimenzionalnih histograma, metodu „k-najbližih susjeda“, metodu Euklidske udaljenosti, metodu potencijalnih funkcija, itd., čija je generalizacija metoda koja se naziva „Parzenove procjene“. Ove metode formalno djeluju s objektima kao integralnim strukturama, ali ovisno o vrsti zadatka prepoznavanja, mogu djelovati i u intenzivnim i ekstenzionalnim hipostazama.

Neparametarske metode analiziraju relativne brojeve objekata koji spadaju u date višedimenzionalne volumene i koriste različite funkcije udaljenosti između objekata uzorka za obuku i prepoznatih objekata. Za kvantitativne osobine, kada je njihov broj mnogo manji od veličine uzorka, operacije s objektima igraju srednju ulogu u procjeni gustoće lokalne distribucije uslovne vjerovatnoće a objekti ne nose semantičko opterećenje nezavisnih informacionih jedinica. Istovremeno, kada je broj karakteristika srazmjeran ili veći od broja objekata koji se proučavaju, a karakteristike su kvalitativne ili dihotomne prirode, onda ne može biti govora o bilo kakvim lokalnim procjenama gustoće distribucije vjerovatnoće. U ovom slučaju, objekti u ovim neparametarskim metodama se smatraju nezavisnim informacionim jedinicama (holističke empirijske činjenice) i ove metode dobijaju značenje procene sličnosti i različitosti objekata koji se proučavaju.

Dakle, iste tehnološke operacije neparametarskih metoda, u zavisnosti od uslova problema, imaju smisla ili lokalne procene gustine distribucije verovatnoće vrednosti karakteristika, ili procene sličnosti i razlike objekata.

U kontekstu intenzivne reprezentacije znanja, ovdje se razmatra prva strana neparametarskih metoda, kao procjene gustoće raspodjele vjerovatnoće. Mnogi autori primjećuju da neparametarske metode kao što su Parzenove procjene dobro funkcionišu u praksi. Glavne poteškoće u primjeni ovih metoda smatraju se potrebom da se zapamti cijeli uzorak obuke kako bi se izračunale procjene gustine lokalne distribucije vjerovatnoće i visoka osjetljivost na nereprezentativnost uzorka za obuku.

Metode zasnovane na pretpostavkama o klasi funkcija odlučivanja. U ovoj grupi metoda, opći oblik funkcije odlučivanja smatra se poznatim i daje se njen kvalitetni funkcional. Na osnovu ove funkcionalnosti traži se najbolja aproksimacija funkcije odlučivanja za sekvencu obuke. Najčešći su prikazi funkcija odlučivanja u obliku linearnih i generaliziranih nelinearnih polinoma. Funkcionalnost kvaliteta pravila odlučivanja obično je povezana s greškom u klasifikaciji.

Glavna prednost metoda zasnovanih na pretpostavkama o klasi funkcija odlučivanja je jasnoća matematičke formulacije problema prepoznavanja kao problema nalaženja ekstrema. Rješenje ovog problema se često postiže korištenjem neke vrste gradijentnih algoritama. Raznolikost metoda ove grupe objašnjava se širokim spektrom korištenih funkcionalnosti kvaliteta pravila odlučivanja i algoritama pretraživanja ekstrema. Generalizacija razmatranih algoritama, koji uključuju, posebno, Newtonov algoritam, algoritme tipa perceptron, itd., je metoda stohastičke aproksimacije. Za razliku od parametarskih metoda prepoznavanja, uspjeh ove grupe metoda ne zavisi toliko od neusklađenosti teorijskih ideja o zakonima distribucije objekata u prostoru karakteristika sa empirijskom stvarnošću. Sve operacije podliježu jednom glavni cilj- pronalaženje ekstrema funkcionalnog kvaliteta pravila odlučivanja. Istovremeno, rezultati parametarske i razmatrane metode mogu biti slični. Kao što je gore prikazano, parametarske metode za slučaj normalne distribucije objekti u različitim klasama sa jednakim matricama kovarijanse dovode do linearnih funkcija odlučivanja. Također napominjemo da se algoritmi za odabir informativnih karakteristika u linearnim dijagnostičkim modelima mogu tumačiti kao posebne varijante gradijentnih algoritama za traženje ekstrema.

Mogućnosti gradijentnih algoritama za pretragu ekstrema, posebno u grupi linearnih pravila odlučivanja, su prilično dobro proučeni. Konvergencija ovih algoritama je dokazana samo za slučaj kada su prepoznatljive klase objekata prikazane u prostoru karakteristika kompaktnim geometrijskim strukturama. Međutim, želja da se postigne dovoljan kvalitet pravila odlučivanja često se može zadovoljiti uz pomoć algoritama koji nemaju strogu matematički dokaz konvergencija rješenja globalnom ekstremumu .

Takvi algoritmi uključuju veliku grupu heurističkih programskih procedura koje predstavljaju pravac evolucijskog modeliranja. Evolucijsko modeliranje je bionička metoda posuđena iz prirode. Zasnovan je na korištenju poznatih mehanizama evolucije kako bi se proces smislenog modeliranja kompleksnog objekta zamijenio fenomenološkim modeliranjem njegove evolucije.

Poznati predstavnik evolucijskog modeliranja u prepoznavanju obrazaca je metoda grupnog obračuna argumenata (MGUA). GMDH se zasniva na principu samoorganizacije, a GMDH algoritmi reproduciraju shemu masovne selekcije. U GMDH algoritmima, članovi generaliziranog polinoma se sintetiziraju i biraju na poseban način, koji se često naziva Kolmogorov-Gaborov polinom. Ova sinteza i selekcija se izvode sa sve većom složenošću i nemoguće je unaprijed predvidjeti kakav će konačni oblik imati generalizirani polinom. Prvo se obično razmatraju jednostavne parne kombinacije početnih karakteristika, od kojih se sastavljaju jednadžbe odlučujućih funkcija, po pravilu, ne više od drugog reda. Svaka se jednadžba analizira kao nezavisna funkcija odlučivanja, a vrijednosti parametara sastavljenih jednadžbi se na ovaj ili onaj način pronalaze iz uzorka za obuku. Zatim se iz rezultirajućeg skupa funkcija odlučivanja odabire dio najboljeg u nekom smislu. Kvalitet pojedinih funkcija odlučivanja se provjerava na kontrolnom (testnom) uzorku, što se ponekad naziva principom eksternog sabiranja. Odabrane parcijalne funkcije odlučivanja se u nastavku razmatraju kao međuvarijable koje služe kao početni argumenti za sličnu sintezu novih funkcija odlučivanja itd. Proces takve hijerarhijske sinteze nastavlja se sve dok se ne postigne ekstremum kriterija kvalitete funkcije odlučivanja, što u praksi manifestuje se u pogoršanju ovog kvaliteta kada se pokušava dalje povećati red članova polinoma u odnosu na originalne karakteristike.

Princip samoorganizacije koji leži u osnovi GMDH naziva se heuristička samoorganizacija, budući da se cijeli proces temelji na uvođenju vanjskih dodataka odabranih heuristički. Rezultat odluke može značajno zavisiti od ovih heuristika. Rezultirajući dijagnostički model ovisi o tome kako su objekti podijeljeni na uzorke za obuku i testiranje, kako je određen kriterij kvalitete prepoznavanja, koliko je varijabli preskočeno u sljedećem retku za odabir, itd.

Ove karakteristike GMDH algoritama su takođe karakteristične za druge pristupe evolucionom modeliranju. Ali ovdje napominjemo još jedan aspekt razmatranih metoda. To je njihova sadržajna suština. Koristeći metode zasnovane na pretpostavkama o klasi funkcija odlučivanja (evolucijske i gradijentne), mogu se izgraditi dijagnostički modeli visoka složenost i dobiti praktično prihvatljive rezultate. Istovremeno, postizanje praktičnih ciljeva u ovom slučaju nije praćeno izvlačenjem novih znanja o prirodi prepoznatljivih predmeta. Mogućnost izvlačenja ovog znanja, posebno znanja o mehanizmima interakcije atributa (obilježja), ovdje je u osnovi ograničena datom strukturom takve interakcije, fiksiranom u odabranom obliku odlučujućih funkcija. Stoga je maksimum koji se može reći nakon konstruiranja određenog dijagnostičkog modela navesti kombinacije karakteristika i samih karakteristika koje su uključene u rezultirajući model. Ali značenje kombinacija koje odražavaju prirodu i strukturu distribucije objekata koji se proučavaju često ostaje neotkriveno u okviru ovog pristupa.

Boolean Methods. Logičke metode prepoznavanja obrazaca zasnovane su na aparatu logičke algebre i omogućavaju rad sa informacijama sadržanim ne samo u pojedinačnim karakteristikama, već iu kombinacijama vrijednosti karakteristika. U ovim metodama vrijednosti bilo kojeg atributa se smatraju elementarnim događajima.

U samom opšti pogled logičke metode se mogu okarakterisati kao neka vrsta potrage za logičkim obrascima u uzorku za obuku i formiranje određenog sistema pravila logičkog odlučivanja (na primjer, u obliku konjukcija elementarni događaji), od kojih svaka ima svoju težinu. Grupa logičkih metoda je raznolika i uključuje metode različite složenosti i dubine analize. Za dihotomne (booleove) karakteristike, popularni su takozvani klasifikatori nalik stablu, metoda testa slijepe ulice, Kora algoritam i drugi. Složenije metode se zasnivaju na formalizaciji induktivne metode D.S. Mill. Formalizacija se provodi konstruiranjem kvazi-aksiomatske teorije i bazira se na višestruko sortiranoj viševrijednoj logici sa kvantifikatorima preko skupova promjenjive dužine.

Kora algoritam, kao i druge logičke metode prepoznavanja uzoraka, prilično je naporan, jer je pri odabiru veznika potrebno kompletno nabrajanje. Stoga se pri primjeni logičkih metoda postavljaju visoki zahtjevi na efikasnu organizaciju računskog procesa, a ove metode dobro funkcionišu sa relativno malim dimenzijama prostora karakteristika i samo na moćnim računarima.

Jezičke (sintaktičke ili strukturalne) metode. Lingvističke metode prepoznavanja obrazaca temelje se na upotrebi posebnih gramatika koje generiraju jezike, uz pomoć kojih se može opisati skup svojstava prepoznatljivih objekata. Gramatika se odnosi na pravila za konstruisanje objekata od ovih neizvedenih elemenata.

Ako se opis slika vrši uz pomoć nederivativnih elemenata (podslika) i njihovih relacija, tada se koristi lingvistički ili sintaktički pristup za izgradnju sistema automatskog prepoznavanja koristeći princip zajedništva svojstava. Slika se može opisati korištenjem hijerarhijske strukture podslika slične sintaksičkoj strukturi jezika. Ova okolnost omogućava primjenu teorije formalni jezici. Pretpostavlja se da gramatika slika sadrži konačan skup elemenata koji se nazivaju varijable, neizvedeni elementi i pravila zamjene. Priroda pravila zamjene određuje tip gramatike. Među najviše proučavanim gramatikama su regularne, bez konteksta i gramatike direktnih konstituenata. Ključne tačke ovog pristupa su izbor nederivativnih elemenata slike, udruživanje ovih elemenata i relacija koji ih povezuju u gramatiku slike i, konačno, implementacija procesa analize i prepoznavanja u odgovarajućim jezik. Ovaj pristup je posebno koristan kada se radi sa slikama koje se ili ne mogu opisati numeričkim mjerenjima, ili su toliko složene da se njihove lokalne karakteristike ne mogu identificirati i moraju se pozivati ​​na globalna svojstva objekata.

Na primjer, E.A. Butakov, V.I. Ostrovsky, I.L. Fadeev ponuda sljedeća struktura sistema za obradu slike (slika 3), koristeći lingvistički pristup, gdje je svaki od funkcionalnih blokova softverski (firmverski) kompleks (modul) koji implementira odgovarajuće funkcije.

Slika 3 Strukturna shema uređaj za prepoznavanje

Pokušaji primjene metoda matematičke lingvistike na problem analize slike dovode do potrebe rješavanja niza problema vezanih za preslikavanje dvodimenzionalne strukture slike na jednodimenzionalne lance formalnog jezika.

Ekstenzivne metode

U metodama ove grupe, za razliku od intenzivnog smjera, svakom proučavanom objektu se u većoj ili manjoj mjeri daje nezavisna dijagnostička vrijednost. U suštini, ove metode su bliske kliničkom pristupu, koji ljude ne posmatra kao lanac objekata rangiranih prema jednom ili drugom pokazatelju, već kao kompletni sistemi, od kojih je svaki individualan i ima posebnu dijagnostičku vrijednost. Takav pažljiv odnos prema objektima proučavanja ne dopušta da se isključi ili izgubi informacija o svakom pojedinačnom objektu, što se događa primjenom metoda intenzivnog usmjeravanja, korištenjem objekata samo za otkrivanje i fiksiranje obrazaca ponašanja njihovih atributa.

Glavne operacije u prepoznavanju uzoraka pomoću razmatranih metoda su operacije utvrđivanja sličnosti i razlike objekata. Objekti u navedenoj grupi metoda imaju ulogu dijagnostičkih presedana. Istovremeno, u zavisnosti od uslova određenog zadatka, uloga pojedinačnog presedana može varirati u najširim granicama: od glavnog i određujućeg do vrlo indirektnog učešća u procesu priznavanja. Zauzvrat, uslovi problema mogu zahtevati za uspješno rješenje učešće različitog broja dijagnostičkih slučajeva: od jednog u svakoj priznatoj klasi do cjelokupne veličine uzorka, a takođe Različiti putevi izračunavanje mjera sličnosti i razlike objekata. Ovi zahtjevi objašnjavaju dalju podelu ekstenzijskih metoda u podklase:

metoda poređenja prototipa;

metoda k-najbližeg susjeda;

timovi pravila odlučivanja.

Metoda poređenja prototipa. Ovo je najjednostavniji metod ekstenzivnog prepoznavanja. Koristi se, na primjer, kada se prepoznate klase prikazuju u prostoru karakteristika u kompaktnim geometrijskim grupama. U ovom slučaju, centar geometrijskog grupiranja klase (ili objekt najbliži centru) obično se bira kao tačka prototipa.

Da bi se klasifikovao nepoznati objekat, pronalazi se prototip koji mu je najbliži, a objekat pripada istoj klasi kao i ovaj prototip. Očigledno, u ovoj metodi se ne formiraju uopštene slike klasa.

Različite vrste udaljenosti mogu se koristiti kao mjera blizine. Često se za dihotomne karakteristike koristi Hammingova udaljenost, koja je u ovom slučaju jednaka kvadratu Euklidske udaljenosti. U ovom slučaju, pravilo odlučivanja za klasifikaciju objekata je ekvivalentno linearnoj funkciji odlučivanja.

Ovu činjenicu treba posebno istaći. To jasno pokazuje vezu između prototipa i indikativnog prikaza informacija o strukturi podataka. Koristeći gornju reprezentaciju, na primjer, bilo koja tradicionalna mjerna skala, koja je linearna funkcija vrijednosti dihotomnih karakteristika, može se smatrati hipotetičkim dijagnostičkim prototipom. Zauzvrat, ako nam analiza prostorne strukture prepoznatih klasa dopušta da zaključimo da su one geometrijski kompaktne, onda je dovoljno svaku od ovih klasa zamijeniti jednim prototipom, koji je zapravo ekvivalentan linearnom dijagnostičkom modelu.

U praksi se, naravno, situacija često razlikuje od opisanog idealiziranog primjera. Istraživač koji namerava da primeni metodu prepoznavanja zasnovanu na poređenju sa prototipovima dijagnostičkih klasa suočava se sa teškim problemima. To je, prije svega, izbor mjere blizine (metrike), koja može značajno promijeniti prostornu konfiguraciju distribucije objekata. i drugo, nezavisni problem je analiza višedimenzionalnih struktura eksperimentalnih podataka. Oba ova problema posebno su akutna za istraživača u uslovima velike dimenzije prostora obeležja, što je tipično za realne probleme.

Metoda k-najbližih susjeda. Metoda k-najbližeg susjeda za rješavanje problema diskriminantne analize prvi put je predložena davne 1952. godine. To je kako slijedi.

Prilikom klasifikacije nepoznatog objekta pronalazi se zadati broj (k) drugih objekata koji su mu geometrijski najbliži u prostoru karakteristika (najbliži susjedi) za koje je već poznato da pripadaju prepoznatljivim klasama. Odluka da se nepoznati objekat dodeli određenoj dijagnostičkoj klasi se donosi analizom informacija o ovom poznatom članstvu njegovih najbližih suseda, na primer, korišćenjem jednostavnog brojanja glasova.

U početku se metoda k-najbližeg susjeda smatrala neparametarskom metodom za procjenu omjera vjerovatnoće. Za ovu metodu dobijene su teorijske procjene njene efikasnosti u poređenju sa optimalnim Bayesovim klasifikatorom. Dokazano je da vjerovatnoće asimptotske greške za metodu k-najbližeg susjeda ne premašuju greške Bayesovog pravila za najviše dva puta.

Kao što je gore navedeno, u stvarni zadacičesto je potrebno operisati objektima koji su opisani velikim brojem kvalitativnih (dihotomnih) karakteristika. Istovremeno, dimenzija prostora obeležja je srazmerna ili prelazi zapreminu uzorka koji se proučava. Pod takvim uslovima, pogodno je tumačiti svaki objekat uzorka za obuku kao poseban linearni klasifikator. Onda jedno ili drugo dijagnostička klasa nije predstavljen jednim prototipom, već skupom linearnih klasifikatora. Kombinovana interakcija linearnih klasifikatora rezultira linearnom površinom koja razdvaja prepoznatljive klase u prostoru obeležja. Vrsta razdjelne površine, koja se sastoji od komada hiperravnina, može varirati i ovisi o tome relativnu poziciju klasifikovane kolekcije.

Može se koristiti i druga interpretacija mehanizama klasifikacije k-najbližih susjeda. Zasniva se na ideji postojanja nekih latentnih varijabli, apstraktnih ili povezanih nekom transformacijom sa izvornim prostorom karakteristika. Ako su u prostoru latentnih varijabli poparne udaljenosti između objekata iste kao u prostoru početnih karakteristika, a broj ovih varijabli je značajno manje od broja objekata, onda se interpretacija metode k-najbližih susjeda može razmatrati sa stanovišta poređenja neparametarskih procjena gustine distribucije uslovnih vjerovatnoća. Koncept latentnih varijabli koji je ovdje predstavljen je po prirodi blizak konceptu prave dimenzionalnosti i drugim reprezentacijama koje se koriste u različitim metodama redukcije dimenzionalnosti.

Kada se koristi metoda k-najbližih susjeda za prepoznavanje uzoraka, istraživač mora riješiti težak problem odabira metrike za određivanje blizine dijagnostikovanih objekata. Ovaj problem u uslovima velike dimenzionalnosti karakterističnog prostora izuzetno je otežan zbog dovoljnog intenziteta rada. ovu metodu, što postaje značajno čak i za računare visokih performansi. Stoga je i ovdje, kao iu načinu poređenja sa prototipom, potrebno odlučiti kreativni zadatak analiza višedimenzionalne strukture eksperimentalnih podataka kako bi se minimizirao broj objekata koji predstavljaju dijagnostičke klase.

Algoritmi za izračunavanje ocjena (glasanje). Princip rada algoritama evaluacije (ABO) je izračunavanje prioriteta (skora sličnosti) koji karakterišu „blizinu“ prepoznatih i referentnih objekata prema sistemu ansambala karakteristika, koji predstavlja sistem podskupova datog skupa. karakteristika.

Za razliku od svih prethodno razmatranih metoda, algoritmi za izračunavanje procjena rade s opisima objekata na fundamentalno nov način. Za ove algoritme, objekti postoje istovremeno u veoma različitim podprostorima prostora karakteristika. Klasa ABO dovodi ideju korištenja karakteristika do svog logičnog zaključka: budući da nije uvijek poznato koje kombinacije karakteristika su najinformativnije, u ABO se stepen sličnosti objekata izračunava poređenjem svih mogućih ili određenih kombinacija karakteristika uključeni u opise objekata.

Timovi pravila odlučivanja. Pravilo odlučivanja koristi dvostepenu šemu prepoznavanja. Na prvom nivou rade privatni algoritmi za prepoznavanje, čiji se rezultati kombinuju na drugom nivou u bloku sinteze. Najčešći metodi takve kombinacije baziraju se na dodjeli područja nadležnosti određenog algoritma. Najjednostavniji način za pronalaženje područja kompetencije je da se a priori podijeli prostor karakteristika na osnovu stručnih razmatranja određene nauke (na primjer, stratifikacija uzorka prema nekom obilježju). Zatim se za svako od odabranih područja gradi vlastiti algoritam prepoznavanja. Drugi metod se zasniva na upotrebi formalne analize za određivanje lokalnih područja prostora obeležja kao susedstva prepoznatljivih objekata za koje je dokazan uspeh bilo kog algoritma za prepoznavanje.

Najopštiji pristup konstruisanju bloka sinteze razmatra rezultirajuće indikatore parcijalnih algoritama kao početne karakteristike za konstruisanje novog generalizovanog pravila odlučivanja. U ovom slučaju mogu se koristiti sve gore navedene metode intenzionalnih i ekstenzijskih smjerova u prepoznavanju obrazaca. Za rješavanje problema kreiranja skupa pravila odlučivanja su logički algoritmi tipa “Kora” i algoritmi za izračunavanje procjena (ABO), koji su osnova tzv. algebarskog pristupa, koji omogućava istraživanje i konstruktivan opis algoritmi za prepoznavanje, unutar kojih se uklapaju svi postojeći tipovi algoritama.

Metode neuronskih mreža

Metode neuronske mreže su metode zasnovane na aplikaciji razne vrste neuronske mreže (NN). Glavna područja primjene različitih NN-a za prepoznavanje uzoraka i slika:

aplikacija za izdvajanje ključnih karakteristika ili karakteristika datih slika,

klasifikacija samih slika ili karakteristika koje su već izvučene iz njih (u prvom slučaju, izdvajanje ključnih karakteristika se događa implicitno unutar mreže),

rješenje optimizacijskih problema.

Višeslojni neuronske mreže. Arhitektura višeslojne neuronske mreže (MNN) sastoji se od sekvencijalno povezanih slojeva, gdje je neuron svakog sloja svojim ulazima povezan sa svim neuronima prethodnog sloja, a izlazima sljedećeg.

Najjednostavnija primjena jednoslojne NN (koja se naziva auto-asocijativna memorija) je obučavanje mreže da rekonstruiše slike feeda. Unošenjem probne slike na ulaz i izračunavanjem kvaliteta rekonstruisane slike, može se proceniti koliko je dobro mreža prepoznala ulaznu sliku. Pozitivna svojstva ove metode su da mreža može oporaviti izobličene i bučne slike, ali nije prikladna za ozbiljnije svrhe.

MNN se koristi i za direktnu klasifikaciju slika - ulaz je ili sama slika u nekom obliku, ili skup prethodno ekstrahovanih ključnih karakteristika slike, na izlazu neuron sa maksimalnom aktivnošću ukazuje na pripadnost prepoznatoj klasi (sl. 4). Ako je ova aktivnost ispod određenog praga, onda se smatra da dostavljena slika ne pripada nijednoj od poznatih klasa. Proces učenja uspostavlja korespondenciju ulaznih slika sa pripadanjem određenoj klasi. Ovo se zove učenje pod nadzorom. Ovaj pristup je dobar za zadatke kontrole pristupa za malu grupu ljudi. Ovaj pristup omogućava direktno poređenje samih slika od strane mreže, ali s povećanjem broja časova, vrijeme obuke i rada mreže raste eksponencijalno. Stoga, za zadatke kao što je traženje slične osobe u velikoj bazi podataka, potrebno je izdvajanje kompaktnog skupa ključnih karakteristika iz kojih se može pretraživati.

Pristup klasifikaciji koji koristi frekvencijske karakteristike cijele slike opisan je u . Korišten je jednoslojni NS baziran na viševrijednim neuronima.

B prikazuje upotrebu NN za klasifikaciju slike, kada mrežni ulaz prima rezultate dekompozicije slike metodom glavnih komponenti.

U klasičnom MNS-u, međuslojne neuronske veze su potpuno povezane, a slika je predstavljena kao jednodimenzionalni vektor, iako je dvodimenzionalna. Arhitektura konvolucione neuronske mreže ima za cilj da prevaziđe ove nedostatke. Koristio je lokalna receptorska polja (obezbeđujući lokalnu dvodimenzionalnu povezanost neurona), opšte težine (obezbeđujući detekciju nekih karakteristika bilo gde na slici) i hijerarhijsku organizaciju sa prostornim poduzorkovanjem (prostorno poduzorkovanje). Konvolucijski NN (CNN) pruža djelomičnu otpornost na promjene skale, pomake, rotacije, izobličenja.

MNS se također koristi za otkrivanje objekata određenog tipa. Pored činjenice da svaki obučeni MNS može u određenoj mjeri utvrditi pripadnost slika „svojim“ klasama, može se posebno osposobiti da pouzdano detektuje određene klase. U ovom slučaju, izlazne klase će biti klase koje pripadaju i ne pripadaju datom tipu slike. Za detekciju slike lica na ulaznoj slici korišten je detektor neuronske mreže. Slika je skenirana sa prozorom od 20x20 piksela, koji je uveden na ulaz mreže, koja odlučuje da li dato područje pripada klasi lica. Obuka je obavljena na pozitivnim primjerima ( razne slike lica) i negativ (slike koje nisu lica). Da bi se poboljšala pouzdanost detekcije, korišćena je grupa NN-a obučenih sa različitim početnim težinama, usled čega su NN-i pravili greške na različite načine, a konačna odluka usvojena glasanjem cijelog tima.

Slika 5. Glavne komponente (eigenfaces) i dekompozicija slike na glavne komponente

NN se također koristi za izdvajanje ključnih karakteristika slike, koje se zatim koriste za kasniju klasifikaciju. U , prikazana je metoda za implementaciju metode analize glavne komponente neuronskom mrežom. Suština metode analize glavnih komponenti je da se dobiju maksimalno dekorelirani koeficijenti koji karakteriziraju ulazne obrasce. Ovi koeficijenti se nazivaju glavnim komponentama i koriste se za statističku kompresiju slike, u kojoj se mali broj koeficijenata koristi za predstavljanje cijele slike. NN sa jednim skrivenim slojem koji sadrži N neurona (što je mnogo manje od dimenzije slike), obučeno metodom propagacije greške unazad da vrati ulaznu sliku na izlaz, generiše koeficijente prvih N glavnih komponenti na izlazu skrivenih neurona, koji se koriste za poređenje. Obično se koristi 10 do 200 glavnih komponenti. Kako se broj komponente povećava, njena reprezentativnost uvelike opada i nema smisla koristiti komponente s velikim brojevima. Kada se koriste nelinearne aktivacijske funkcije neuronskih elemenata, moguća je nelinearna dekompozicija na glavne komponente. Nelinearnost vam omogućava da preciznije odrazite varijacije u ulaznim podacima. Primjenjujući analizu glavnih komponenti na dekompoziciju slika lica, dobijamo glavne komponente, nazvane pravilna lica, koje također imaju korisno svojstvo- postoje komponente koje uglavnom odražavaju takve bitne karakteristike osobe kao što su spol, rasa, emocije. Kada se restauriraju, komponente izgledaju kao lice, s tim da prvi odražava najviše opšti oblik lica, ovo drugo - razne male razlike između lica (slika 5). Ova metoda je dobro primjenjiva za pretraživanje sličnih slika lica u velikim bazama podataka. Takođe je prikazana mogućnost daljeg smanjenja dimenzija glavnih komponenti uz pomoć NS. Procjenom kvaliteta rekonstrukcije ulazne slike može se vrlo precizno utvrditi da li ona pripada klasi lica.

Neuralne mreže high order. Neuralne mreže visokog reda (HNN) se razlikuju od MNN-a po tome što imaju samo jedan sloj, ali ulazi neurona također primaju članove visokog reda, koji su proizvod dvije ili više komponenti ulaznog vektora. Takve mreže također mogu formirati složene površine za razdvajanje.

Hopfieldove neuronske mreže. Hopfield NN (HSH) je jednoslojni i potpuno povezan (ne postoje veze neurona sa samim sobom), njegovi izlazi su povezani sa ulazima. Za razliku od MNS-a, NSH je relaksacioni, tj. kada je postavljen na početno stanje, funkcioniše sve dok ne dostigne stabilno stanje, što će biti njegova izlazna vrednost. Da se pronađe globalni minimum u odnosu na problemi optimizacije koristiti stohastičke modifikacije NSH.

Upotreba NSH kao asocijativno pamćenje omogućava vam da precizno vratite slike na koje je mreža uvježbana kada se izobličena slika unese na ulaz. U ovom slučaju, mreža će "zapamtiti" najbliže (u smislu lokalni minimum energetska) sliku, i na taj način je prepoznaje. Takvo funkcioniranje se također može smatrati sekvencijalnom primjenom gore opisane auto-asocijativne memorije. Za razliku od auto-asocijativne memorije, NSH će savršeno precizno vratiti sliku. Kako bi se izbjegli minimumi smetnji i povećao kapacitet mreže, koriste se različite metode.

Kohonenove samoorganizirajuće neuronske mreže. Kohonenove samoorganizirajuće neuronske mreže (SNNC) pružaju topološko uređenje prostora ulazne slike. Oni omogućavaju topološki kontinuirano mapiranje ulaza n-dimenzionalni prostor na izlaz m-dimenzionalan, m<

Cognitron. Kognitron je u svojoj arhitekturi sličan strukturi vizualnog korteksa, ima hijerarhijsku višeslojnu organizaciju, u kojoj su neuroni između slojeva povezani samo lokalno. Obučen takmičarskim učenjem (bez nastavnika). Svaki sloj mozga implementira različite nivoe generalizacije; ulazni sloj je osjetljiv na jednostavne obrasce, kao što su linije, i njihovu orijentaciju u određenim područjima vizualnog područja, dok je odgovor ostalih slojeva složeniji, apstraktniji i nezavisan od položaja uzorka. Slične funkcije se implementiraju u kognitronu modeliranjem organizacije vidnog korteksa.

Neokognitron je dalji razvoj kognitronske ideje i preciznije odražava strukturu vizuelnog sistema, omogućava vam da prepoznate slike bez obzira na njihove transformacije, rotacije, izobličenja i promene razmera.

Cognitron je moćan alat za prepoznavanje slika, međutim, zahtijeva visoke računske troškove, koji su trenutno nedostižni.

Razmatrane metode neuronske mreže omogućavaju brzo i pouzdano prepoznavanje slike, ali pri korištenju ovih metoda nastaju problemi u prepoznavanju trodimenzionalnih objekata. Međutim, ovaj pristup ima mnogo prednosti.

Zaključak

Trenutno postoji prilično veliki broj automatskih sistema za prepoznavanje uzoraka za različite primijenjene probleme.

Prepoznavanje obrazaca formalnim metodama kao fundamentalni naučni pravac je neiscrpno.

Matematičke metode obrade slike imaju široku lepezu primene: nauka, tehnologija, medicina, društvena sfera. U budućnosti će se uloga prepoznavanja obrazaca u ljudskom životu još više povećati.

Metode neuronske mreže omogućavaju brzo i pouzdano prepoznavanje slike. Ovaj pristup ima mnoge prednosti i jedan je od najperspektivnijih.

Književnost

D.V. Brilyuk, V.V. Starovoitov. Metode neuronske mreže prepoznavanja slike // /

Kuzin L.T. Osnove kibernetike: Osnove kibernetičkih modela. T.2. - M.: Energy, 1979. - 584 str.

Peregudov F.I., Tarasenko F.P. Uvod u analizu sistema: Udžbenik. - M.: Viša škola, 1997. - 389s.

Temnikov F.E., Afonin V.A., Dmitriev V.I. Teorijske osnove informacione tehnologije. - M.: Energija, 1979. - 511s.

Tu J., Gonzalez R. Principles of Pattern Recognition. / Per. sa engleskog. - M.: Mir, 1978. - 410s.

Winston P. Umjetna inteligencija. / Per. sa engleskog. - M.: Mir, 1980. - 520s.

Fu K. Strukturne metode u prepoznavanju obrazaca: Prevedeno s engleskog. - M.: Mir, 1977. - 320s.

Tsypkin Ya.Z. Osnove informacijske teorije identifikacije. - M.: Nauka, 1984. - 520s.

Pospelov G.S. Umjetna inteligencija je osnova nove informacione tehnologije. - M.: Nauka, 1988. - 280s.

Yu. Lifshits, Statističke metode prepoznavanja obrazaca ///modern/07modernnote.pdf

Bohr N. Atomska fizika i ljudsko znanje. / Prevod sa engleskog. - M.: Mir, 1961. - 151s.

Butakov E.A., Ostrovsky V.I., Fadeev I.L. Obrada slike na kompjuteru.1987.-236s.

Duda R., Hart P. Prepoznavanje uzoraka i analiza scene. / Prevod sa engleskog. - M.: Mir, 1978. - 510s.

Duke V.A. Kompjuterska psihodijagnostika. - Sankt Peterburg: Bratstvo, 1994. - 365 str.

Aizenberg I. N., Aizenberg N. N. i Krivosheev G. A. Viševrijedni i univerzalni binarni neuroni: algoritmi učenja, primjene za obradu i prepoznavanje slika. Bilješke s predavanja iz umjetne inteligencije - mašinsko učenje i rudarenje podataka u prepoznavanju uzoraka, 1999, str. 21-35.

Ranganath S. i Arun K. Prepoznavanje lica koristeći transformacijske karakteristike i neuronske mreže. Pattern Recognition 1997, Vol. 30, str. 1615-1622.

Golovko V.A. Neurointeligencija: teorija i primjene. Knjiga 1. Organizacija i obuka neuronskih mreža sa direktnim i povratnim informacijama - Brest: BPI, 1999, - 260s.

Vetter T. i Poggio T. Klase linearnih objekata i sinteza slike iz jednog primjera slike. IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, str. 733-742.

Golovko V.A. Neurointeligencija: teorija i primjene. Knjiga 2. Samoorganizacija, tolerancija grešaka i upotreba neuronskih mreža - Brest: BPI, 1999, - 228s.

Lawrence S., Giles C. L., Tsoi A. C. i Back A. D. Prepoznavanje lica: pristup konvolucionoj neuronskoj mreži. IEEE Transactions on Neural Networks, Special Issue on Neural Networks and Pattern Recognition, str. 1-24.

Wasserman F. Neurokompjuterska tehnologija: teorija i praksa, 1992. - 184 str.

Rowley H. A., Baluja S. i Kanade T. Detekcija lica zasnovana na neuronskim mrežama. IEEE Transactions on Pattern Analysis and Machine Intelligence 1998, Vol. 20, str. 23-37.

Valentin D., Abdi H., O "Toole A. J. i Cottrell G. W. Konekcionistički modeli obrade lica: anketa. IN: Pattern Recognition 1994, Vol. 27, str. 1209-1230.

Dokument

Oni prave algoritme prepoznavanjeslike. Metodeprepoznavanjeslike Kao što je gore navedeno... stvarnost nije postoje"ekosistemi uopšte" i postoji samo nekoliko ... zaključaka iz ovog detaljnog recenzijametodeprepoznavanje predstavili smo u...

1. Pregled metoda za identifikaciju ljudi na osnovu slika lica, uzimajući u obzir karakteristike vizuelnog prepoznavanja

   Pregled

   ... prepoznavanje od strane osobe sa objektima niskog kontrasta, uklj. osobe. Doneli recenzijačesto metode ... Postoji cela linija metode ... način, kao rezultat studije, platforma za razvoj metodaprepoznavanje ...

2. Imeni Glazkova Valentina Vladimirovna ISTRAŽIVANJE I RAZVOJ METODA ZA KONSTRUKCIJU SOFTVERSKIH ALATA ZA KLASIFIKACIJU VIŠETEMATSKIH HIPERTEKSTNIH DOKUMENTA Specijalnost 05

   Sažetak disertacije

   hipertekstualni dokumenti. Poglavlje sadrži recenzijapostojećimetode rješenje problema koji se razmatra, opis ... odsijecanjem najmanje relevantnih klasa // Matematika metodeprepoznavanjeslike: 13. Sveruska konferencija. Lenjingradska oblast...

3. Slide 0 Pregled zadataka bioinformatike vezanih za analizu i obradu genetskih tekstova

   Predavanje

   DNK i proteinske sekvence. Pregled zadaci bioinformatike kao zadaci ... signali zahtijevaju upotrebu modernih metodeprepoznavanjeslike, statistički pristupi i ... sa niskom gustinom gena. Postojeći programi za predviđanje gena ne...

Moderni roboti opremljeni sistemima za vid mogu dobro vidjeti kako bi mogli raditi sa stvarnim svijetom. Oni mogu zaključiti koje vrste objekata su prisutne, u kakvom su međusobnom odnosu, koje grupe formiraju.

Suština problema prepoznavanja je da se utvrdi da li predmeti koji se proučavaju imaju fiksni konačan skup karakteristika koji im omogućava da se pripisuju određenoj klasi.

Ciljevi nauke o prepoznavanju obrazaca:

Zamjena ljudskog eksperta ili složenog ekspertnog sistema jednostavnijim sistemom (automatizacija ljudske aktivnosti ili pojednostavljenje složenih sistema);

Izgradnja sistema za učenje koji su u stanju da donose odluke bez specificiranja jasnih pravila, odnosno sistema koji su u stanju da sami sintetiziraju pravila odlučivanja na osnovu nekog konačnog broja primjera ispravnih odluka „demonstriranih“ sistemu.

Zadaci prepoznavanja može se okarakterisati na sledeći način.

1. Ovo su informativni zadaci, koji se sastoje od dvije glavne faze: dovođenje izvornih podataka u oblik pogodan za prepoznavanje i samo prepoznavanje.

2. U ove probleme se može uvesti koncept analogije i sličnosti objekata i formulisati koncept blizine objekata kao osnova za pripisivanje objekta određenoj klasi.

3. U ovim zadacima moguće je raditi sa skupom primjera čija je klasifikacija poznata i koji se u obliku formaliziranih opisa mogu predstaviti algoritmu prepoznavanja za prilagođavanje zadatku u procesu učenja.

4. Za ove probleme je teško izgraditi formalne teorije i primijeniti klasične matematičke metode.

5. U ovim zadacima su moguće "loše" informacije.

Vrste zadataka prepoznavanja:

Dodjeljivanje predstavljenog objekta jednom od časova (obuka sa nastavnikom);

Automatska klasifikacija - razdvajanje skupa objekata (situacija) prema njihovom opisu u sistem klasa koje se ne preklapaju;

Odabir skupa informativnih karakteristika za prepoznavanje;

Dovođenje izvornih podataka u oblik pogodan za prepoznavanje;

Dinamičko prepoznavanje i dinamička klasifikacija;

Zadaci predviđanja.

Osnovne definicije

Slika je strukturirani opis objekta ili pojave, predstavljen vektorom obilježja, čiji svaki element predstavlja numeričku vrijednost jedne od karakteristika koje karakteriziraju dati objekt. Drugim riječima: slika je svaki predmet za koji se može izmjeriti skup određenih numeričkih karakteristika. Primjer slike: slovo, slika, kardiogram itd.

Numerički znak(ili samo znak). je formula ili drugi opis metode za uparivanje objekta sa određenom numeričkom karakteristikom, koja radi u okviru specifičnog problema prepoznavanja obrazaca. Za svaki objekat može se definisati nekoliko različitih karakteristika, odnosno nekoliko numeričkih karakteristika.

karakterističan prostor.N-dimenzionalni prostor definiran za dati zadatak prepoznavanja, gdje je N fiksni broj izmjerenih karakteristika za bilo koji objekt. Vektor iz prostora karakteristika koji odgovara objektu problema prepoznavanja je N-dimenzionalni vektor sa komponentama (x1, x2, ..., xN), koje su vrijednosti karakteristika ovog objekta.

OBJECT->Nfeatures->M-dimenzionalni vektor karakteristika

Klasa- neformalizirajuća (u pravilu) ideja o mogućnosti dodjele proizvoljnog objekta iz skupa objekata zadatka prepoznavanja određenoj grupi objekata. Za objekte iste klase pretpostavlja se prisustvo "sličnosti". Za problem prepoznavanja obrazaca može se definirati proizvoljan broj klasa, veći od 1. Broj klasa se označava brojem S.

Općenito, problem prepoznavanja obrazaca sastoji se od dva dijela: prepoznavanja i učenja.

Prepoznavanje uzoraka je klasifikacija određene grupe objekata na osnovu određenih zahtjeva. Objekti koji pripadaju istoj klasi slika imaju zajednička svojstva. Zahtjevi koji definiraju klasifikaciju mogu biti različiti, budući da različite situacije zahtijevaju različite vrste klasifikacija.

Na primjer, prilikom prepoznavanja engleskih slova formira se 26 klasa slika. Međutim, da bi se razlikovala engleska slova od kineskih znakova prilikom prepoznavanja, potrebne su samo dvije klase slika.

Najjednostavniji pristup prepoznavanju obrazaca je podudaranje uzoraka. U ovom slučaju, skup slika, po jedna iz svake klase slika, pohranjuje se u memoriju uređaja. Ulazna (prepoznatljiva) slika (nepoznate klase) se upoređuje sa standardom svake klase. Klasifikacija se zasniva na unaprijed odabranom kriteriju podudaranja ili sličnosti. Drugim riječima, ako ulazna slika odgovara uzorku i-te klase uzoraka bolje od bilo kojeg drugog uzorka, tada se ulazni uzorak klasificira kao da pripada i-toj klasi uzoraka.

Nedostatak ovog pristupa, odnosno usklađivanja sa standardom, je u tome što je u nekim slučajevima teško izabrati odgovarajući standard iz svake klase slika i uspostaviti neophodan kriterij podudaranja.

Napredniji pristup je da se klasifikacija zasniva na nekom skupu odabranih mjerenja na ulaznim slikama. Pretpostavlja se da su ova odabrana mjerenja, nazvana "obilježja", nepromjenjiva ili neosjetljiva na uobičajene promjene i izobličenja i da imaju malu redundantnost.

Poseban slučaj drugog pristupa „mjeranja karakteristika“, u kojem se etaloni pohranjuju u obliku izmjerenih karakteristika, a u klasifikatoru se koristi poseban kriterij klasifikacije (poređenje).

Karakteristike definiraju programeri i moraju biti nepromjenjive u odnosu na orijentaciju, veličinu i varijacije oblika objekata.

itd. objekti koje karakteriše konačan skup određenih svojstava i karakteristika. Takvi se zadaci rješavaju prilično često, na primjer, kada prelazite ili vozite ulicu na semaforu. Prepoznavanje boje upaljenog semafora i poznavanje pravila na putu omogućavaju vam da donesete ispravnu odluku o tome da li ćete preći ulicu ili ne.

Potreba za takvim prepoznavanjem javlja se u raznim oblastima – od vojnih poslova i sigurnosnih sistema do digitalizacije analognih signala.

Problem prepoznavanja slike dobio je izuzetan značaj u uslovima preopterećenosti informacijama, kada se osoba ne može nositi s linearno-sekvencijskim razumijevanjem poruka koje mu pristižu, zbog čega se njegov mozak prebacuje na način simultanosti percepcije i razmišljanja. , za koje je karakteristično takvo prepoznavanje.

Stoga nije slučajno što se pokazalo da je problem prepoznavanja slika u polju interdisciplinarnih istraživanja, uključujući i u vezi s radom na stvaranju umjetne inteligencije i stvaranju tehničkih sistema. prepoznavanje uzoraka privlači sve više pažnje.

Enciklopedijski YouTube

1 / 4

Uvod u prepoznavanje uzoraka

R.V. Shamin. Predavanje br. 6 Hopfieldove i Hamingove mreže u problemima prepoznavanja obrazaca

[DDSH-2016]: Neuronske mreže i savremeni kompjuterski vid

Predavanje 9. Eksponencijalno izglađivanje. Prepoznavanje uzoraka: k-ti metod najbližeg susjeda

Titlovi

Smjerovi u prepoznavanju obrazaca

Postoje dva glavna pravca:

• Proučavanje sposobnosti prepoznavanja koje posjeduju živa bića, njihovo objašnjavanje i modeliranje;
• Razvoj teorije i metoda za konstruisanje uređaja namenjenih rešavanju pojedinačnih problema u primenjene svrhe.

Formalna izjava o problemu

Prepoznavanje uzoraka je dodjela početnih podataka određenoj klasi isticanjem bitnih karakteristika koje karakteriziraju ove podatke iz ukupne mase nebitnih podataka.

Prilikom postavljanja problema prepoznavanja pokušavaju koristiti matematički jezik, pokušavajući - za razliku od teorije umjetnih neuronskih mreža, gdje je osnova da se dobije rezultat eksperimentom - eksperiment zamijeniti logičkim zaključivanjem i matematičkim dokazima.

Klasična izjava o problemu prepoznavanja obrazaca: Dat skup objekata. Treba ih klasificirati. Skup je predstavljen podskupovima, koji se nazivaju klase. Dato je: informacije o klasama, opis cijelog skupa i opis informacija o objektu čija pripadnost određenoj klasi nije poznata. Potrebno je, prema dostupnim informacijama o klasama i opisu objekta, odrediti kojoj klasi ovaj objekt pripada.

U problemima prepoznavanja obrazaca najčešće se razmatraju jednobojne slike, što omogućava razmatranje slike kao funkcije na ravni. Ako uzmemo u obzir tačku skupu na ravni T (\displaystyle T), gdje funkcija izražava u svakoj tački slike njenu karakteristiku - svjetlinu, transparentnost, optičku gustoću, tada je takva funkcija formalni zapis slike.

Skup svih mogućih funkcija f (x, y) (\displaystyle f(x, y)) na površini T (\displaystyle T)- postoji model skupa svih slika X (\displaystyle X). Predstavljamo koncept sličnosti između slika možete postaviti zadatak prepoznavanja. Specifičan oblik takve postavke snažno zavisi od narednih faza u prepoznavanju u skladu sa ovim ili drugim pristupom.

Neke metode prepoznavanja grafičkih slika

Za optičko prepoznavanje slike, možete primijeniti metodu iteracije nad izgledom objekta pod različitim uglovima, skalama, pomacima itd. Za slova morate iterirati preko fonta, svojstava fonta itd.

Drugi pristup je pronalaženje konture objekta i ispitivanje njegovih svojstava (povezanost, prisustvo uglova, itd.)

Drugi pristup je korištenje umjetnih neuralnih mrež. Ova metoda zahtijeva ili veliki broj primjera zadatka prepoznavanja (sa tačnim odgovorima), ili posebnu strukturu neuronske mreže koja uzima u obzir specifičnosti ovog zadatka.

Perceptron kao metoda prepoznavanja obrazaca

F. Rosenblatt je, uvodeći koncept modela mozga, čiji je zadatak da pokaže kako psihološki fenomeni mogu nastati u nekom fizičkom sistemu čija su struktura i funkcionalna svojstva poznata, opisao najjednostavnije eksperimente o diskriminaciji. Ovi eksperimenti se u potpunosti odnose na metode prepoznavanja obrazaca, ali se razlikuju po tome što algoritam rješenja nije deterministički.

Najjednostavniji eksperiment, na osnovu kojeg je moguće dobiti psihološki značajnu informaciju o određenom sistemu, svodi se na to da se modelu predoče dva različita stimulusa i da se na njih traži da odgovori na različite načine. Svrha takvog eksperimenta može biti proučavanje mogućnosti njihove spontane diskriminacije od strane sistema u odsustvu intervencije eksperimentatora, ili, obrnuto, proučavanje prisilne diskriminacije, u kojoj eksperimentator nastoji naučiti sistem da izvrši potrebna klasifikacija.

U eksperimentu učenja, perceptron se obično prikazuje s određenim nizom slika, koji uključuje predstavnike svake od klasa koje treba razlikovati. Prema nekom pravilu modifikacije memorije, ispravan izbor reakcije je pojačan. Zatim se kontrolni stimulus predstavlja perceptronu i određuje se vjerovatnoća dobijanja ispravnog odgovora za stimuluse ove klase. Ovisno o tome da li se odabrani kontrolni stimulus poklapa ili ne poklapa s jednom od slika koje su korištene u sekvenci treninga, dobijaju se različiti rezultati:

1. Ako se kontrolni stimulus ne poklapa ni sa jednim stimulusom učenja, tada je eksperiment povezan ne samo sa čista diskriminacija, ali uključuje i elemente generalizacije.
2. Ako kontrolni podražaj pobuđuje određeni skup osjetilnih elemenata koji su potpuno različiti od onih elemenata koji su aktivirani pod utjecajem prethodno prikazanih podražaja iste klase, tada je eksperiment istražni. čista generalizacija.

Perceptroni nemaju kapacitet za čistu generalizaciju, ali sasvim zadovoljavajuće funkcionišu u eksperimentima diskriminacije, posebno ako se kontrolni stimulans dovoljno poklapa s jednim od obrazaca o kojima je perceptron već stekao određeno iskustvo.

Primjeri problema prepoznavanja obrazaca

• Prepoznavanje barkodova
• Prepoznavanje registarskih tablica
• Prepoznavanje slike
• Prepoznavanje lokalnih područja zemljine kore u kojima se nalaze nalazišta

U ovom članku pokušao sam da istaknem neke od osnovnih rezultata teorije mašinskog učenja na način koji čini koncepte razumljivim čitaocima koji su donekle upoznati sa problemima klasifikacije i regresije. Ideja da napišem takav članak sve jasnije se manifestirala u mom umu sa svakom knjigom koju sam pročitao, u kojoj su ideje učenja mašina za prepoznavanje bile izrečene kao iz sredine i uopće nije bilo jasno šta su autori ovog ili na koji se metod oslanjao prilikom razvoja. S druge strane, postoji veliki broj knjiga posvećenih osnovnim konceptima u mašinskom učenju, ali predstavljanje materijala u njima može izgledati previše komplikovano za prvo čitanje.

Motivacija

Razmotrimo takav zadatak. Imamo jabuke dvije klase - ukusne i neukusne, 1 i 0. Jabuke imaju karakteristike - boju i veličinu. Boja će se kontinuirano mijenjati od 0 do 1, tj. 0 - potpuno zelena jabuka, 1 - potpuno crvena. Veličina se može promijeniti na sličan način, 0 - mala jabuka, 1 - velika. Željeli bismo razviti algoritam koji bi uzeo boju i veličinu kao ulaz, a vratio klasu jabuke kao izlaz - bila ona ukusna ili ne. Vrlo je poželjno da broj grešaka u ovom slučaju bude što manji to bolji. Istovremeno, imamo konačnu listu koja sadrži istorijske podatke o boji, veličini i klasi jabuka. Kako bismo mogli riješiti takav problem?

logičan pristup

Rješavajući naš problem, prva metoda koja vam može pasti na pamet može biti ova: hajde da ručno sastavimo if-else pravila i, ovisno o vrijednostima boje i veličine, dodijelit ćemo određenu klasu jabuci. One. imamo preduslove - to su boja i veličina, a tu je i posledica - ukus jabuke. Sasvim je razumno kada ima malo znakova, a pragove za poređenje možete procijeniti na oko. Ali može se desiti da neće biti moguće doći do jasnih uslova, a iz podataka nije vidljivo koje pragove uzeti, a broj karakteristika se može povećati u budućnosti. Ali što ako smo u našoj listi s povijesnim podacima pronašli dvije jabuke iste boje i veličine, ali jedna je označena kao ukusna, a druga nije? Dakle, naša prva metoda nije tako fleksibilna i skalabilna koliko bismo željeli.

Notacija

Hajde da uvedemo sljedeću notaciju. Označit ćemo jabuku kao . Zauzvrat, svaki se sastoji od dva broja - boje i veličine. Ovu činjenicu ćemo označiti parom brojeva: . Klasu svake -te jabuke označavamo sa . Lista sa istorijskim podacima će biti označena slovom , dužina ove liste je jednaka . Treći element ove liste je vrijednost atributa jabuke i njene klase. One. . Nazvaćemo ga i uzorkom. Velikim slovima i označavamo varijable koje mogu poprimiti vrijednosti određene karakteristike i klase. Uvodimo novi koncept - pravilo odlučivanja je funkcija koja uzima vrijednost boje i veličine kao ulaz i vraća oznaku klase kao izlaz:

Vjerovatni pristup

Razvijajući ideju o logičkoj metodi sa premisama i posledicama, postavimo sebi pitanje - kolika je verovatnoća da će -ta jabuka, koja ne pripada našem uzorku, biti ukusna, s obzirom na izmerene vrednosti boje i veličine? U notaciji teorije vjerovatnoće, ovo pitanje se može napisati na sljedeći način:

U ovom izrazu, to se može tumačiti kao premisa, kao posljedica, ali prijelaz iz premise u posljedicu će se pokoravati vjerojatnosnim zakonima, a ne logičkim. One. umjesto tablice istine sa booleovim vrijednostima 0 i 1 za klasu, postojaće vrijednosti vjerovatnoće koje uzimaju vrijednosti od 0 do 1. Primijenite Bayesovu formulu i dobijete sljedeći izraz:

Razmotrimo desnu stranu ovog izraza detaljnije. Multiplikator se naziva prethodna vjerovatnoća i označava vjerovatnoću pronalaženja ukusne jabuke među svim mogućim jabukama. Apriorna vjerovatnoća da ćete naići na neukusnu jabuku je . Ova vjerovatnoća može odražavati naše lično znanje o tome kako su dobre i loše jabuke raspoređene u prirodi. Na primjer, iz našeg prethodnog iskustva znamo da je 80% svih jabuka ukusno. Ili možemo procijeniti ovu vrijednost jednostavnim prebrojavanjem udjela ukusnih jabuka na našoj listi s historijskim podacima S. Sljedeći množitelj pokazuje kolika je vjerovatnoća da će se dobiti određena boja i veličina jabuke klase 1. Ovaj izraz se također naziva funkcija vjerovatnoće i može biti u obliku neke posebne distribucije, na primjer, normalne. Imenilac koristimo kao konstantu normalizacije tako da željena vjerovatnoća varira od 0 do 1. Naš krajnji cilj nije da tražimo vjerovatnoće, već da pronađemo pravilo odluke koje bi nam odmah dalo klasu. Konačni oblik pravila odlučivanja ovisi o tome koje vrijednosti i parametre znamo. Na primjer, možemo znati samo vrijednosti prethodne vjerovatnoće, a ostale vrijednosti se ne mogu procijeniti. Tada će odlučujuće pravilo biti sljedeće - svim jabukama dodijeliti vrijednost klase za koju je apriorna vjerovatnoća najveća. One. ako znamo da je 80% jabuka u prirodi ukusno, onda za svaku jabuku stavljamo klasu 1. Tada će naša greška biti 20%. Ako možemo procijeniti i vrijednosti funkcije vjerovatnoće $p(X=x_m | Y=1)$, tada također možemo pronaći vrijednost tražene vjerovatnoće koristeći Bayesovu formulu, kako je gore napisano. Pravilo odluke ovdje će biti sljedeće: stavite oznaku klase za koju je vjerovatnoća maksimalna:

Ovo pravilo ćemo nazvati Bayesovim klasifikatorom. Pošto se radi o vjerovatnoćama, čak ni velika vrijednost vjerovatnoće ne garantuje da jabuka ne pripada klasi 0. Procijenimo vjerovatnoću greške na jabuci na sljedeći način: ako je pravilo odlučivanja vratilo vrijednost klase jednaku 1, onda vjerovatnoća greške će biti i obrnuto:

Zanima nas vjerovatnoća greške klasifikatora ne samo u ovom konkretnom primjeru, već općenito za sve moguće jabuke:

Ovaj izraz je matematičko očekivanje greške. Dakle, rješavajući prvobitni problem, došli smo do Bayesovog klasifikatora, ali koji su njegovi nedostaci? Glavni problem je procijeniti uslovnu vjerovatnoću iz podataka. U našem slučaju objekt predstavljamo kao par brojeva – boja i veličina, ali u složenijim zadacima dimenzija karakteristika može biti višestruko veća, a broj zapažanja sa naše liste sa istorijskim podacima možda neće biti dovoljan za procijeniti vjerovatnoću višedimenzionalne slučajne varijable. Zatim ćemo pokušati generalizirati naš koncept greške klasifikatora, a također ćemo vidjeti da li je moguće odabrati bilo koji drugi klasifikator za rješavanje problema.

Gubici zbog grešaka u klasifikatoru

Pretpostavimo da već imamo neku vrstu pravila odlučivanja. Tada može napraviti dvije vrste grešaka - prva je dodijeliti objekt klasi 0, koja ima stvarnu klasu 1, i obrnuto, dodijeliti objekt klasi 1, koja ima stvarnu klasu 0. U nekim problema, može biti važno razlikovati ove slučajeve. Na primjer, više patimo od činjenice da se jabuka označena kao ukusna pokazala neukusnom i obrnuto. Formaliziramo stepen naše nelagode zbog prevarenih očekivanja u konceptu. Općenito, imamo funkciju gubitka koja vraća broj za svaku grešku klasifikatora. Neka bude prava oznaka klase. Funkcija gubitka tada vraća vrijednost gubitka za stvarnu oznaku klase i vrijednost našeg pravila odlučivanja. Primjer korištenja ove funkcije je uzeti iz jabuke s poznatom klasom, proslijediti jabuku na ulaz našeg pravila odlučivanja, dobiti procjenu klase iz pravila odlučivanja, ako se vrijednosti i podudaraju, onda smatramo da klasifikator nije pogriješio i nema gubitka, ako se vrijednosti ne poklapaju, iznos gubitka će naša funkcija reći

Uslovni i Bayesov rizik

Sada kada imamo funkciju gubitka i znamo koliko gubimo zbog pogrešne klasifikacije objekata, bilo bi lijepo razumjeti koliko gubimo u prosjeku, na mnogo objekata. Ako znamo vrijednost - vjerovatnoća da će -ta jabuka biti ukusna, s obzirom na izmjerene vrijednosti boje i veličine, kao i stvarnu vrijednost klase (npr. uzeti jabuku iz uzorka S, vidi na početku članka), tada možemo uvesti koncept uslovnog rizika. Uslovni rizik je prosječna vrijednost gubitaka u objektu za pravilo odluke:

U našem slučaju binarne klasifikacije, kada se ispostavi:

Iznad smo opisali pravilo odlučivanja koje dodjeljuje objekt klasi koja ima najveću vrijednost vjerovatnoće. Takvo pravilo donosi minimum naših prosječnih gubitaka (Bayesian rizik), tako da je Bayesov klasifikator optimalan u smislu funkcionalnog rizika koji smo uveli . To znači da Bayesov klasifikator ima najmanju moguću grešku u klasifikaciji.

Neke tipične funkcije gubitka

Jedna od najčešćih funkcija gubitka je simetrična funkcija, kada su gubici od prve i druge vrste grešaka ekvivalentni. Na primjer, funkcija gubitka 1-0 (gubitak nula-jedan) definirana je na sljedeći način:

Tada će uslovni rizik za a(x) = 1 jednostavno biti vrijednost vjerovatnoće dobivanja klase 0 na objektu:

Slično za a(x) = 0:

Funkcija gubitka 1-0 uzima vrijednost 1 ako klasifikator napravi grešku na objektu i 0 ako ne. Sada napravimo tako da vrijednost greške ne bude 1, već druga funkcija Q, ovisno o pravilu odluke i oznaci prave klase:

Tada se uslovni rizik može zapisati na sljedeći način:

Napomene o notaciji

Prethodni tekst napisan je prema notaciji koju su u knjizi usvojili Duda i Hart. U originalnoj knjizi V.N. Vapnik je razmatrao takav proces: priroda bira objekat prema distribuciji $p(x)$, a zatim mu dodeljuje oznaku klase prema uslovnoj raspodeli $p(y|x)$. Tada se rizik (očekivanje gubitka) definira kao

Gdje je funkcija s kojom pokušavamo aproksimirati nepoznatu ovisnost, je funkcija gubitka za stvarnu vrijednost i vrijednost naše funkcije. Ova notacija je više deskriptivna kako bi se uveo sljedeći koncept - empirijski rizik.

Empirijski rizik

U ovoj fazi smo već otkrili da logička metoda nije prikladna za nas, jer nije dovoljno fleksibilna, a ne možemo koristiti Bayesov klasifikator kada postoji mnogo karakteristika, a postoji ograničen broj podataka za obuku, i nećemo moći vratiti vjerovatnoću. Također znamo da Bayesov klasifikator ima najmanju moguću grešku u klasifikaciji. Pošto ne možemo koristiti Bayesov klasifikator, uzmimo nešto jednostavnije. Hajde da popravimo neku parametarsku porodicu funkcija H i izaberemo klasifikator iz ove porodice.

Primjer: neka je skup svih funkcija forme

Sve funkcije ovog skupa će se razlikovati jedna od druge samo po koeficijentima.Kada smo odabrali takvu familiju, pretpostavili smo da je u koordinatama veličine boje između tačaka klase 1 i tačaka klase 0 moguće povući pravu liniju sa koeficijentima na takav način da se tačke različitih klasa nalaze duž suprotnih strana prave linije. Poznato je da je za pravu liniju ove vrste vektor koeficijenata normalan na pravu liniju. Sada radimo ovo - uzimamo našu jabuku, mjerimo njenu boju i veličinu i iscrtavamo tačku sa dobijenim koordinatama na grafikonu u osi veličine boje. Zatim mjerimo ugao između ove tačke i vektora $w$. Napominjemo da naša tačka može ležati na jednoj ili na drugoj strani linije. Tada će ugao između i tačke biti ili oštar ili tup, a skalarni proizvod je pozitivan ili negativan. Ovdje dolazi do pravila odluke:

Nakon što smo fiksirali klasu funkcija $H$, postavlja se pitanje - kako iz nje izabrati funkciju sa traženim koeficijentima? Odgovor je - hajde da izaberemo funkciju koja isporučuje minimum našem Bayesovom riziku $R()$. Opet, problem je u tome što da biste izračunali vrijednosti Bayesovog rizika, morate znati distribuciju $p(x,y)$, ali ona nam nije data i nije uvijek moguće vratiti to. Druga ideja je da se rizik minimizira ne na sve moguće objekte, već samo na uzorak. One. minimiziraj funkciju:

Ova funkcija se naziva empirijski rizik. Sljedeće pitanje je zašto smo odlučili da minimiziranjem empirijskog rizika minimiziramo i Bayesov rizik? Podsjećam da je naš praktični zadatak da napravimo što manje grešaka u klasifikaciji. Što je manje grešaka, manji je Bayesov rizik. Obrazloženje za konvergenciju empirijskog rizika na Bayesian s povećanjem količine podataka su 70-ih godina dobili dva naučnika - V. N. Vapnik i A. Ya. Chervonenkis.

Garancije konvergencije. Najjednostavniji slučaj

Dakle, došli smo do zaključka da Bayesov klasifikator daje najmanju moguću grešku, ali ga u većini slučajeva ne možemo trenirati, a ne možemo ni izračunati grešku (rizik). Međutim, možemo izračunati aproksimaciju Bayesovom riziku, koji se naziva empirijski rizik, i znajući empirijski rizik, izabrati aproksimirajuću funkciju koja bi minimizirala empirijski rizik. Razmotrimo najjednostavniju situaciju u kojoj empirijska minimizacija rizika daje klasifikator koji također minimizira Bayesov rizik. Za najjednostavniji slučaj, moraćemo da napravimo pretpostavku koja se retko ispunjava u praksi, ali se kasnije može oslabiti. Fiksiramo konačnu klasu funkcija iz koje ćemo izabrati naš klasifikator i pretpostaviti da je prava funkcija koju priroda koristi za označavanje naših jabuka za ukus nalazi u ovom konačnom skupu hipoteza: . Imamo i uzorak dobijen iz distribucije po objektima. Svi uzorci objekata smatraju se jednako nezavisno raspoređenim (iid). Tada će biti istinito sljedeće

Teorema

Odabirom funkcije iz klase koristeći empirijsku minimizaciju rizika, zajamčeno je da ćemo naći takvu da ima malu Bayesovu vrijednost rizika ako uzorak na kojem minimiziramo ima dovoljnu veličinu.

Za značenje pojmova "mala vrijednost" i "dovoljna veličina" pogledajte literaturu u nastavku.

Ideja za dokaz

Uslovom teoreme dobijamo uzorak iz distribucije, tj. proces odabira objekata iz prirode je nasumičan. Svaki put kada prikupimo uzorak, on će biti iz iste distribucije, ali sami objekti u njemu mogu biti različiti. Glavna ideja dokaza je da možemo dobiti tako nesretan uzorak da će algoritam koji odaberemo minimiziranjem empirijskog rizika na datom uzorku biti loš u minimiziranju Bayesovog rizika, ali će u isto vrijeme biti dobar. da bi se minimizirao empirijski rizik, ali vjerovatnoća dobijanja takvog uzorka je mala i povećanjem veličine uzorka ova vjerovatnoća opada. Slične teoreme postoje za realnije pretpostavke, ali ih ovdje nećemo razmatrati.

Praktični rezultati

Imajući dokaze da funkcija pronađena minimiziranjem empirijskog rizika neće imati veliku grešku na prethodno neopaženim podacima sa dovoljnom veličinom uzorka za obuku, ovaj princip možemo koristiti u praksi, na primjer, na sljedeći način - uzimamo izraz:

I zamjenjujemo različite funkcije gubitka, ovisno o problemu koji se rješava. Za linearnu regresiju:

Za logističku regresiju:

Iako su mašine sa vektorima podrške prvenstveno motivisane geometrijom, one se takođe mogu smatrati empirijskim problemima minimizacije rizika.

Zaključak

Mnoge metode nadgledane nastave mogu se smatrati, između ostalog, posebnim slučajevima teorije koju su razvili V. N. Vapnik i A. Ya. Chervonenkis. Ova teorija daje garancije u pogledu greške na testnom skupu, s obzirom na dovoljnu veličinu skupa za obuku i neke zahtjeve za prostor hipoteza u kojem tražimo naš algoritam.

Korištene knjige

• Priroda statističke teorije učenja, Vladimir N. Vapnik
• Klasifikacija uzoraka, 2. izdanje, Richard O. Duda, Peter E. Hart, David G. Stork
• Razumijevanje mašinskog učenja: od teorije do algoritama, Shai Shalev-Shwartz, Shai Ben-David

P.S. O svim netačnostima i greškama u kucanju pišite lično

Oznake: Dodajte oznake

Živi sistemi, uključujući ljude, stalno su suočeni sa zadatkom prepoznavanja obrazaca od svog nastanka. Konkretno, informacije koje dolaze iz osjetilnih organa obrađuje mozak, koji zauzvrat sortira informacije, osigurava donošenje odluka, a zatim, koristeći elektrohemijske impulse, dalje prenosi neophodan signal, na primjer, do organa kretanja, koji sprovesti potrebne radnje. Tada dolazi do promjene okoline i gore navedene pojave se ponovo javljaju. A ako pogledate, onda je svaka faza praćena priznanjem.

Razvojem kompjuterske tehnologije postalo je moguće riješiti niz problema koji se javljaju u procesu života, olakšati, ubrzati, poboljšati kvalitetu rezultata. Na primjer, rad različitih sistema za održavanje života, interakcija čovjeka i računara, pojava robotskih sistema itd. Međutim, napominjemo da trenutno nije moguće obezbijediti zadovoljavajući rezultat u nekim zadacima (prepoznavanje brzo pokretnih sličnih objekata , rukom pisani tekst).

Svrha rada: proučavanje istorije sistema za prepoznavanje obrazaca.

Navedite kvalitativne promjene koje su se dogodile u oblasti prepoznavanja obrazaca, teorijske i tehničke, uz navođenje razloga;

Razgovarajte o metodama i principima koji se koriste u računarstvu;

Navedite primjere perspektiva koje se očekuju u bliskoj budućnosti.

1. Šta je prepoznavanje obrazaca?

Prva istraživanja sa kompjuterskom tehnologijom u osnovi su pratila klasičnu šemu matematičkog modeliranja – matematički model, algoritam i proračun. To su bili zadaci modeliranja procesa koji se dešavaju prilikom eksplozija atomskih bombi, proračun balističkih putanja, ekonomske i druge primjene. Međutim, pored klasičnih ideja ove serije, postojale su i metode potpuno drugačije prirode, a kako je praksa rješavanja nekih problema pokazala, često su davale bolje rezultate od rješenja zasnovanih na prekompliciranim matematičkim modelima. Njihova ideja je bila da odustanu od želje za stvaranjem iscrpnog matematičkog modela predmeta koji se proučava (štaviše, često je bilo praktično nemoguće konstruisati adekvatne modele), i umjesto toga da se zadovolje odgovorom samo na konkretna pitanja koja nas zanimaju, i ove odgovore treba tražiti iz razmatranja zajedničkih za široku klasu problema. Istraživanja ove vrste uključivala su prepoznavanje vizuelnih slika, predviđanje prinosa, vodostaja rijeka, problem razlikovanja naftonosnih i vodonosnih slojeva pomoću indirektnih geofizičkih podataka, itd. Konkretan odgovor u ovim zadacima bio je potreban u prilično jednostavnom obliku, kao npr. na primjer, da li objekt pripada jednoj od unaprijed fiksiranih klasa. I početni podaci ovih zadataka, u pravilu, davani su u obliku fragmentarnih informacija o objektima koji se proučavaju, na primjer, u obliku skupa prethodno klasificiranih objekata. Sa matematičke tačke gledišta, to znači da je prepoznavanje obrazaca (a ova klasa problema nazvana u našoj zemlji) dalekosežna generalizacija ideje ekstrapolacije funkcija.

Značaj takve formulacije za tehničke nauke je nesumnjiv, a to samo po sebi opravdava brojna istraživanja u ovoj oblasti. Međutim, problem prepoznavanja obrazaca ima i širi aspekt za prirodnu nauku (međutim, bilo bi čudno da nešto toliko važno za vještačke kibernetičke sisteme ne bi bilo važno za prirodne). Kontekst ove nauke organski je uključivao pitanja koja su postavljali antički filozofi o prirodi našeg znanja, našoj sposobnosti da prepoznamo slike, obrasce, situacije okolnog sveta. Zapravo, praktički nema sumnje da su mehanizmi za prepoznavanje najjednostavnijih slika, poput slika opasnog grabežljivca ili hrane koji se približava, nastali mnogo prije nego što su nastali elementarni jezik i formalno-logički aparat. I nema sumnje da su takvi mehanizmi dovoljno razvijeni i kod viših životinja, kojima je u svojoj vitalnoj aktivnosti također hitno potrebna sposobnost razlikovanja prilično složenog sistema znakova prirode. Tako u prirodi vidimo da se fenomen mišljenja i svijesti jasno zasniva na sposobnosti prepoznavanja obrazaca, a dalji napredak nauke o inteligenciji direktno je povezan sa dubinom razumijevanja osnovnih zakona prepoznavanja. Razumijevajući činjenicu da gornja pitanja nadilaze standardnu ​​definiciju prepoznavanja obrazaca (izraz nadzirano učenje je češći u literaturi na engleskom jeziku), također je potrebno razumjeti da ona imaju duboke veze s ovim relativno uskim (ali ipak daleko od iscrpljenog) smjera.

Čak i sada, prepoznavanje uzoraka je čvrsto ušlo u svakodnevni život i jedno je od najvažnijih znanja modernog inženjera. U medicini, prepoznavanje uzoraka pomaže liječnicima da postave preciznije dijagnoze; u tvornicama se koristi za predviđanje nedostataka u serijama robe. Biometrijski sistemi lične identifikacije kao njihova algoritamska jezgra su takođe zasnovani na rezultatima ove discipline. Dalji razvoj umjetne inteligencije, a posebno dizajn kompjutera pete generacije sposobnih za direktniju komunikaciju s osobom na prirodnim jezicima za ljude i kroz govor, nezamisliv je bez prepoznavanja. Ovdje su robotika, umjetni sistemi upravljanja koji sadrže sisteme prepoznavanja kao vitalne podsisteme, na dohvat ruke.

Zato je na razvoj prepoznavanja obrazaca od samog početka privučena velika pažnja od strane stručnjaka različitih profila - kibernetičara, neurofiziologa, psihologa, matematičara, ekonomista itd. Uglavnom iz tog razloga, samo moderno prepoznavanje obrazaca se hrani idejama ovih disciplina. Bez tvrdnje da smo potpuni (a to je nemoguće tvrditi u kratkom eseju), opisati ćemo povijest prepoznavanja obrazaca, ključne ideje.

Definicije

Prije nego što pređemo na glavne metode prepoznavanja uzoraka, dajemo nekoliko potrebnih definicija.

Prepoznavanje slika (objekata, signala, situacija, pojava ili procesa) je zadatak identifikacije objekta ili određivanja bilo kojeg njegovog svojstva po njegovoj slici (optičko prepoznavanje) ili audio zapisu (akustičko prepoznavanje) i drugim karakteristikama.

Jedan od osnovnih je koncept skupa koji nema određenu formulaciju. U računaru, skup je predstavljen skupom neponavljajućih elemenata istog tipa. Riječ "neponavljajući" znači da neki element u skupu ili postoji ili ga nema. Univerzalni skup uključuje sve moguće elemente za problem koji se rješava, prazan skup ne sadrži nijedan.

Slika je klasifikaciono grupisanje u sistemu klasifikacije koje objedinjuje (izdvaja) određenu grupu objekata prema nekom atributu. Slike imaju karakteristično svojstvo koje se očituje u činjenici da poznavanje konačnog broja pojava iz istog skupa omogućava prepoznavanje proizvoljno velikog broja njegovih predstavnika. Slike imaju karakteristična objektivna svojstva u smislu da različiti ljudi koji uče iz različitog materijala za posmatranje, uglavnom, klasifikuju iste objekte na isti način i nezavisno jedan od drugog. U klasičnoj formulaciji problema prepoznavanja, univerzalni skup je podijeljen na dijelove-slike. Svako preslikavanje bilo kog objekta u organe opažanja sistema prepoznavanja, bez obzira na njegov položaj u odnosu na te organe, obično se naziva slikom objekta, a skupovi takvih slika, ujedinjenih nekim zajedničkim svojstvima, su slike.

Metoda dodjeljivanja elementa bilo kojoj slici naziva se pravilo odluke. Drugi važan koncept je metrika, način za određivanje udaljenosti između elemenata univerzalnog skupa. Što je ova udaljenost manja, objekti (simboli, zvuci itd.) koje prepoznajemo sličniji su. Tipično, elementi su specificirani kao skup brojeva, a metrika je navedena kao funkcija. Efikasnost programa zavisi od izbora reprezentacije slika i implementacije metrike, jedan algoritam za prepoznavanje sa različitim metrikama će praviti greške sa različitim frekvencijama.

Učenjem se obično naziva proces razvijanja u nekom sistemu određene reakcije na grupe spoljašnjih identičnih signala uzastopnim uticajem na sistem eksterne korekcije. Takvo vanjsko prilagođavanje u treningu obično se naziva "ohrabrenjem" i "kaznom". Mehanizam za generisanje ovog prilagođavanja gotovo u potpunosti određuje algoritam učenja. Samoučenje se razlikuje od učenja po tome što se ovdje ne navode dodatne informacije o ispravnosti reakcije na sistem.

Adaptacija je proces promene parametara i strukture sistema, a moguće i kontrolnih radnji, na osnovu trenutnih informacija u cilju postizanja određenog stanja sistema sa početnom nesigurnošću i promenom uslova rada.

Učenje je proces, usled kojeg sistem postepeno stiče sposobnost da odgovori potrebnim reakcijama na određene skupove spoljašnjih uticaja, a prilagođavanje je prilagođavanje parametara i strukture sistema kako bi se postigao traženi kvalitet. kontrola u uslovima kontinuiranih promena spoljašnjih uslova.

Primjeri zadataka prepoznavanja obrazaca: - Prepoznavanje slova;