Ülevaade olemasolevatest mustrituvastusmeetoditest

L.P. Popova , JA KOHTA. Datijev

Inimese, nagu ka teiste elusorganismide, peamiseks omaduseks peetakse võimet "ära tunda". Mustrituvastus on küberneetika haru, mis töötab välja põhimõtted ja meetodid objektide, nähtuste, protsesside, signaalide, olukordade klassifitseerimiseks ja tuvastamiseks – kõik need objektid, mida saab kirjeldada mingite objekti iseloomustavate tunnuste või omaduste lõpliku hulgaga.

Pilt on objekti kirjeldus. Piltidel on iseloomulik omadus, mis väljendub selles, et samast hulgast piiratud arvu nähtustega tutvumine võimaldab ära tunda meelevaldselt suure hulga selle esindajaid.

Mustrituvastuse teoorias on kaks peamist suunda:

inimese ja teiste elusorganismide äratundmisvõime uurimine;

teooria ja meetodite väljatöötamine seadmete konstrueerimiseks, mis on mõeldud teatud rakendusvaldkondade mustrituvastuse individuaalsete probleemide lahendamiseks.

Edasi kirjeldatakse artiklis teise suuna arendamisega seotud mustrituvastussüsteemide rakendamise probleeme, põhimõtteid ja meetodeid. Artikli teises osas käsitletakse mustrituvastuse närvivõrgu meetodeid, mida võib seostada mustrituvastuse teooria esimese suunaga.

Probleemid pildituvastussüsteemide ehitamisel

Automaatsete mustrituvastussüsteemide ehitamisel tekkivad ülesanded võib tavaliselt liigitada mitmeks põhivaldkonnaks. Neist esimene on seotud tuvastatava objekti mõõtmistulemustena saadud algandmete esitamisega. tundlikkuse probleem. Iga mõõdetud väärtus on mingi "kujutise või objekti tunnus. Oletame näiteks, et kujutised on tähtnumbrilised märgid. Sel juhul saab edukalt kasutada mõõtevõrkkest, mis on sarnane joonisel 1 (a) kujutatule. anduris.Kui võrkkest koosneb n-elementidest, siis saab mõõtmistulemusi esitada mõõtevektorina või kujutise vektorina ,

kus iga element xi saab näiteks väärtuse 1, kui sümboli kujutis läbib võrkkesta i-ndat rakku, ja väärtuseks 0 muul juhul.

Kaaluge joonist fig. 2(b). Sel juhul on kujutised muutuja t pidevad funktsioonid (helisignaalide tüübist). Kui funktsiooni väärtusi mõõdetakse diskreetsetes punktides t1,t2, ..., tn, saab kujutise vektori moodustada võttes x1= f(t1),x2=f(t2),... , xn = f(tn).

Joonis 1. Võrkkesta mõõtmine

Teine mustrituvastuse probleem on seotud iseloomulike tunnuste või omaduste valikuga saadud lähteandmetest ja mustrivektorite mõõtmete vähendamisega. Seda probleemi määratletakse sageli probleemina eeltöötlus ja funktsioonide valik.

Piltide klassi tunnused on iseloomulikud omadused, mis on ühised kõikidele antud klassi piltidele. Märgid, mis iseloomustavad üksikute klasside erinevusi, on tõlgendatavad klassidevaheliste märkidena. Kõigile vaadeldavatele klassidele ühised klassisisesed tunnused ei kanna äratundmise seisukohalt kasulikku teavet ja neid ei pruugita arvesse võtta. Funktsioonide valikut peetakse üheks oluliseks tuvastussüsteemide ehitamisega seotud ülesandeks. Kui mõõtmistulemused võimaldavad saada kõigi klasside eristavate tunnuste komplekti, ei tekita mustrite tegelik äratundmine ja klassifitseerimine erilisi raskusi. Seejärel taandataks automaatne tuvastamine lihtsaks sobitamisprotsessiks või protseduurideks, nagu tabeliotsing. Enamiku praktiliste äratundmisprobleemide puhul on eristavate tunnuste komplekti kindlaksmääramine aga äärmiselt keeruline, kui mitte võimatu. Algandmetest on tavaliselt võimalik välja võtta mõned eristavad tunnused ja kasutada neid automaatse mustrituvastuse protsessi lihtsustamiseks. Eelkõige saab mõõtevektorite mõõtmeid vähendada, kasutades teisendusi, mis minimeerivad teabe kadu.

Kolmas mustrituvastussüsteemide konstrueerimisega seotud probleem on identifitseerimiseks ja klassifitseerimiseks vajalike optimaalsete otsustusprotseduuride leidmine. Pärast seda, kui tuvastatavate mustrite kohta kogutud andmed on mustriruumis esitatud punktide või mõõtevektoritega, laske masinal välja selgitada, millisele mustrite klassile need andmed vastavad. Olgu masin konstrueeritud nii, et see eristab M-klassi, mida tähistatakse w1, w2, ... ..., wm. Sel juhul võib pildiruumi pidada M piirkonnast koosnevaks, millest igaüks sisaldab punkte, mis vastavad sama klassi piltidele. Sel juhul võib äratundmisprobleemiks pidada M klassi eraldavate otsustuspiirkondade piiride konstrueerimist registreeritud mõõtevektorite põhjal. Olgu need piirid defineeritud näiteks otsustusfunktsioonidega d1(х),d2(x),..., dm(х). Need funktsioonid, mida nimetatakse ka diskrimineerivateks funktsioonideks, on x-i kujutise skalaarsed ja üheväärtuslikud funktsioonid. Kui di (x) > dj (x), siis x-i kujutis kuulub klassi w1. Teisisõnu, kui i-ndal otsustusfunktsioonil di(x) on suurim väärtus, on sellise otsustusprotsessi rakendamisel põhineva automaatse klassifitseerimisskeemi tähendusrikas illustratsioon näidatud joonisel fig. 2 (skeemil "GR" - otsustavate funktsioonide generaator).

Joonis 2. Automaatse klassifitseerimise skeem.

Otsustusfunktsioone saab hankida mitmel viisil. Nendel juhtudel, kui äratuntavate mustrite kohta on olemas täielik a priori teave, saab selle teabe põhjal täpselt määrata otsustusfunktsioonid. Kui mustrite kohta on saadaval ainult kvalitatiivne informatsioon, saab otsustusfunktsioonide vormi kohta teha mõistlikke oletusi. Viimasel juhul võivad otsustuspiirkondade piirid tegelikest oluliselt erineda ja seetõttu on vaja luua süsteem, mis suudab saavutada rahuldava tulemuse läbi järjestikuste kohandamiste.

Automaatse mustrituvastussüsteemi abil äratuntavatel ja klassifitseeritavatel objektidel (kujutistel) peab olema mõõdetavate omaduste kogum. Kui terve kujutiste rühma puhul on vastavate mõõtmiste tulemused sarnased, siis loetakse, et need objektid kuuluvad samasse klassi. Mustrituvastussüsteemi eesmärk on määrata kogutud teabe põhjal objektide klass, mille tunnused on sarnased äratuntavate objektide puhul mõõdetavatega. Äratundmise õigsus sõltub mõõdetud tunnustes sisalduva eristava teabe hulgast ja selle teabe kasutamise efektiivsusest.

Mustrituvastussüsteemide juurutamise põhimeetodid

Mustrituvastus on ülesanne konstrueerida ja rakendada formaalseid tehteid reaalse või ideaalmaailma objektide arvulistel või sümboolsetel esitustel, mille tulemused peegeldavad nende objektide vahelisi ekvivalentseoseid. Ekvivalentsuseosed väljendavad hinnatavate objektide kuulumist mõnda klassi, mida peetakse iseseisvateks semantilisteks üksusteks.

Tuvastamisalgoritmide konstrueerimisel saab samaväärsusklasse määrata uurija, kes kasutab oma mõtestatud ideid või kasutab välist lisainformatsiooni objektide sarnasuse ja erinevuse kohta lahendatava probleemi kontekstis. Siis räägitakse "õpetajaga mõistmisest". Vastasel juhul, st. kui automatiseeritud süsteem lahendab klassifitseerimisprobleemi ilma välist koolitusteavet kaasamata, räägitakse automaatsest klassifitseerimisest või "järelevalveta tuvastamisest". Enamik mustrituvastusalgoritme nõuab väga märkimisväärse arvutusvõimsuse kaasamist, mida saab pakkuda ainult suure jõudlusega arvutitehnoloogia.

Erinevad autorid (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 jt) esitavad mustrituvastusmeetodite erineva tüpoloogia. Mõned autorid eristavad parameetrilisi, mitteparameetrilisi ja heuristlikke meetodeid, teised aga eristavad meetodite rühmi, mis põhinevad selle valdkonna ajaloolistel koolkondadel ja suundumustel.

Samas ei võeta tuntud tüpoloogiates arvesse üht väga olulist tunnust, mis peegeldab ainevaldkonna teadmiste esitamise spetsiifikat mis tahes formaalse mustrituvastusalgoritmi abil. D.A. Pospelov tuvastab kaks peamist teadmiste esitamise viisi:

Intensionaalne esitus - atribuutide (tunnuste) vaheliste seoste diagrammi kujul.

Laiendusesitus - konkreetsete faktide (objektid, näited) abil.

Tuleb märkida, et nende kahe tunnustamismeetodite rühma olemasolu: tunnustega opereerivad ja objektidega opereerivad on sügavalt loomulik. Sellest vaatenurgast ei võimalda ükski neist meetoditest teisest eraldi võetuna moodustada ainevaldkonna adekvaatset peegeldust. Nende meetodite vahel on N. Bohri mõistes komplementaarsussuhe, seetõttu peaksid paljutõotavad tunnustamissüsteemid tagama mõlema meetodi rakendamise, mitte ainult ühe neist.

Seega põhineb D. A. Pospelovi pakutud äratundmismeetodite klassifikatsioon fundamentaalsetel seaduspäradel, mis on inimese tunnetusviisi aluseks üldiselt, mis seab selle teiste klassifikatsioonidega võrreldes väga erilisse (privilegeeritud) positsiooni, mis sellel taustal paistavad. kergem ja kunstlikum.

Intensiivsed meetodid

Intensionaalsete meetodite eripäraks on see, et nad kasutavad mustrituvastusalgoritmide koostamisel ja rakendamisel operatsioonide elementidena tunnuste erinevaid omadusi ja nende seoseid. Sellised elemendid võivad olla üksikud väärtused või tunnuste väärtuste intervallid, keskmised väärtused ja dispersioonid, tunnuste seoste maatriksid jne, millega tehakse toiminguid, väljendatuna analüütilisel või konstruktiivsel kujul. Samas ei peeta nende meetodite objekte terviklikeks teabeüksusteks, vaid need toimivad indikaatoritena nende atribuutide koostoime ja käitumise hindamisel.

Intensiivsete mustrituvastusmeetodite rühm on ulatuslik ja selle jaotus alamklassideks on mõnevõrra meelevaldne:

– tunnuste väärtuste jaotustiheduse hinnangutel põhinevad meetodid

– meetodid, mis põhinevad eeldustel otsustusfunktsioonide klassi kohta

- loogilised meetodid

– keelelised (struktuuri)meetodid.

Meetodid, mis põhinevad tunnuste väärtuste jaotustiheduse hinnangutel. Need mustrituvastusmeetodid on laenatud klassikalisest statistiliste otsuste teooriast, milles uuritavaid objekte käsitletakse mõne seaduse järgi tunnusruumis jaotatud mitmemõõtmelise juhusliku suuruse realisatsioonidena. Need põhinevad Bayesi otsustusskeemil, mis apelleerib teatud äratuntavasse klassi kuuluvate objektide a priori tõenäosustele ja tunnusvektori väärtuste tingimuslikele jaotustihedustele. Need meetodid on taandatud tõenäosussuhte määramiseks mitmemõõtmelise tunnusruumi erinevates piirkondades.

Tunnuste väärtuste jaotustiheduse hindamisel põhinev meetodite rühm on otseselt seotud diskriminantanalüüsi meetoditega. Bayesi lähenemine otsuste tegemisele on kaasaegses statistikas üks arenenumaid, nn parameetrilisi meetodeid, mille puhul peetakse jaotusseaduse (antud juhul normaalseaduse) analüütilist väljendust teadaolevaks ja vaid väikeseks. parameetrite arv (keskmised vektorid ja kovariatsioonimaatriksid) tuleb hinnata.

See rühm sisaldab ka meetodit sõltumatute tunnuste tõenäosussuhte arvutamiseks. See meetod, välja arvatud tunnuste sõltumatuse eeldus (mis tegelikkuses peaaegu kunagi ei täitu), ei nõua jaotusseaduse funktsionaalse vormi tundmist. Seda võib seostada mitteparameetriliste meetoditega.

Teised mitteparameetrilised meetodid, mida kasutatakse juhul, kui jaotustiheduse kõvera kuju on teadmata ja selle olemuse kohta ei saa üldse oletusi teha, on erilisel positsioonil. Nende hulka kuuluvad tuntud mitmemõõtmeliste histogrammide meetod, “k-lähimate naabrite” meetod, Eukleidilise kauguse meetod, potentsiaalsete funktsioonide meetod jne, mille üldistus on meetod, mida nimetatakse “Parzeni hinnanguteks”. Need meetodid toimivad formaalselt objektidega terviklike struktuuridena, kuid olenevalt tuvastusülesande tüübist võivad nad toimida nii intensionaalsetes kui ka ekstensioonilistes hüpostaasides.

Mitteparameetrilised meetodid analüüsivad antud mitmemõõtmelistesse ruumaladesse langevate objektide suhtelist arvu ning kasutavad erinevaid kaugusfunktsioone treeningvalimi objektide ja äratuntavate objektide vahel. Kvantitatiivsete tunnuste puhul, kui nende arv on valimi suurusest palju väiksem, mängivad toimingud objektidega tinglike tõenäosuste lokaalse jaotustiheduse hindamisel vahepealset rolli ning objektid ei kanna sõltumatute teabeüksuste semantilist koormust. Samas, kui tunnuste arv on proportsionaalne või suurem kui uuritavate objektide arv ning tunnused on kvalitatiivse või dihhotoomse iseloomuga, siis tõenäosusjaotuse tiheduste lokaalsetest hinnangutest ei saa juttugi olla. Sel juhul käsitletakse nendes mitteparameetrilistes meetodites olevaid objekte iseseisvate teabeüksustena (holistiliste empiiriliste faktidena) ja need meetodid omandavad hinnangute tähenduse uuritavate objektide sarnasusele ja erinevusele.

Seega on samadel mitteparameetriliste meetodite tehnoloogilistel operatsioonidel, olenevalt ülesande tingimustest, mõttekas kas tunnusväärtuste tõenäosusjaotuse tiheduste lokaalsed hinnangud või objektide sarnasuse ja erinevuse hinnangud.

Teadmiste intensionaalse esituse kontekstis käsitletakse siin mitteparameetriliste meetodite esimest poolt, kui tõenäosusjaotuse tiheduste hinnanguid. Paljud autorid märgivad, et mitteparameetrilised meetodid, nagu Parzeni hinnangud, töötavad praktikas hästi. Peamised raskused nende meetodite rakendamisel on vajadus meeles pidada kogu koolitusvalimi, et arvutada kohaliku tõenäosusjaotuse tiheduse hinnangud ja kõrge tundlikkus koolitusvalimi mitterepresentatiivsuse suhtes.

Meetodid, mis põhinevad oletustel otsustusfunktsioonide klassi kohta. Selles meetodite rühmas loetakse otsustusfunktsiooni üldkuju teada ja antakse selle kvaliteedifunktsionaal. Selle funktsiooni põhjal otsitakse treeningjärjestuse jaoks parimat otsustusfunktsiooni lähendust. Kõige levinumad on otsustusfunktsioonide esitused lineaarsete ja üldistatud mittelineaarsete polünoomide kujul. Otsustusreegli kvaliteedifunktsioon on tavaliselt seotud klassifitseerimisveaga.

Otsustusfunktsioonide klassi eeldustel põhinevate meetodite peamine eelis on äratundmisprobleemi kui ekstreemumi leidmise probleemi matemaatilise sõnastuse selgus. Selle probleemi lahendus saavutatakse sageli mingite gradient-algoritmide abil. Selle rühma meetodite mitmekesisus on seletatav paljude kasutatavate otsustusreeglite kvaliteedi funktsionaalfunktsioonide ja äärmuslike otsingualgoritmidega. Vaadeldavate algoritmide, mis hõlmavad eelkõige Newtoni algoritmi, perceptron-tüüpi algoritme jne, üldistus on stohhastilise lähenduse meetod. Erinevalt parameetrilistest tuvastamismeetoditest ei sõltu selle meetodite rühma edu niivõrd objektide jaotusseaduste teoreetiliste ideede mittevastavusest tunnusruumis empiirilise reaalsusega. Kõik toimingud on allutatud ühele põhieesmärgile – otsustusreegli kvaliteedifunktsionaalse äärmuse leidmisele. Samal ajal võivad parameetrilise ja vaadeldava meetodi tulemused olla sarnased. Nagu eespool näidatud, viivad parameetrilised meetodid võrdsete kovariatsioonimaatriksitega erinevatesse klassidesse kuuluvate objektide normaaljaotuse korral lineaarsete otsustusfunktsioonideni. Samuti märgime, et lineaarsetes diagnostilistes mudelites informatiivsete tunnuste valimise algoritme saab tõlgendada ekstreemumi otsimiseks mõeldud gradient-algoritmide konkreetsete variantidena.

Üsna hästi on uuritud gradient-algoritmide võimalusi ekstreemumi leidmiseks, eriti lineaarsete otsustusreeglite rühmas. Nende algoritmide konvergents on tõestatud vaid juhul, kui objektide äratuntavad klassid kuvatakse tunnusruumis kompaktsete geomeetriliste struktuuridega. Otsustusreegli piisava kvaliteedi saavutamise soovi saab aga sageli rahuldada algoritmide abil, millel pole ranget matemaatilist tõestust lahenduse lähenemisest globaalsele ekstreemumile.

Sellised algoritmid hõlmavad suurt hulka heuristlikke programmeerimisprotseduure, mis esindavad evolutsioonilise modelleerimise suunda. Evolutsiooniline modelleerimine on loodusest laenatud biooniline meetod. See põhineb teadaolevate evolutsioonimehhanismide kasutamisel, et asendada keeruka objekti mõtestatud modelleerimise protsess selle evolutsiooni fenomenoloogilise modelleerimisega.

Tuntud evolutsioonilise modelleerimise esindaja mustrituvastuses on argumentide rühmaarvestuse meetod (MGUA). GMDH põhineb iseorganiseerumise põhimõttel ja GMDH algoritmid reprodutseerivad massivaliku skeemi. GMDH algoritmides sünteesitakse ja valitakse üldistatud polünoomi liikmed erilisel viisil, mida sageli nimetatakse Kolmogorovi-Gabori polünoomiks. See süntees ja valik viiakse läbi üha keerukamalt ning on võimatu ette ennustada, milline on üldistatud polünoomi lõplik vorm. Esiteks vaadeldakse tavaliselt algtunnuste lihtsaid paarikaupa kombinatsioone, millest koostatakse otsustavate funktsioonide võrrandid, mis reeglina ei ületa teist järku. Iga võrrandit analüüsitakse iseseisva otsustusfunktsioonina ja koostatud võrrandite parameetrite väärtused leitakse ühel või teisel viisil koolitusproovist. Seejärel valitakse saadud otsustusfunktsioonide komplektist välja osa mõnes mõttes parimast. Üksikute otsustusfunktsioonide kvaliteeti kontrollitakse kontroll- (test)valimil, mida mõnikord nimetatakse ka välise liitmise põhimõtteks. Valitud konkreetseid otsustusfunktsioone käsitletakse allpool vahemuutujatena, mis on lähteargumendiks uute otsustusfunktsioonide sarnaseks sünteesiks jne. Sellise hierarhilise sünteesi protsess jätkub, kuni jõutakse otsustusfunktsiooni kvaliteedikriteeriumi äärmuseni, mis praktikas väljendub selle kvaliteedi halvenemises, kui püütakse polünoomi liikmete järjestust esialgsete tunnuste suhtes veelgi suurendada.

GMDH aluseks olevat iseorganiseerumisprintsiipi nimetatakse heuristlikuks iseorganiseerumiseks, kuna kogu protsess põhineb heuristlikult valitud väliste täienduste sisseviimisel. Otsuse tulemus võib nendest heuristidest oluliselt sõltuda. Saadud diagnostikamudel sõltub sellest, kuidas objektid jaotatakse treening- ja testimisnäidisteks, kuidas määratakse tuvastamise kvaliteedikriteerium, kui palju muutujaid järgmisel valikureal vahele jäetakse jne.

Need GMDH-algoritmide omadused on iseloomulikud ka teistele evolutsioonilise modelleerimise lähenemisviisidele. Kuid märgime siin vaadeldavate meetodite veel ühe aspekti. See on nende sisu olemus. Kasutades meetodeid, mis põhinevad eeldustel otsustusfunktsioonide klassi kohta (evolutsiooniline ja gradient), on võimalik koostada kõrge keerukusega diagnostilisi mudeleid ja saada praktiliselt vastuvõetavaid tulemusi. Samas ei kaasne sel juhul praktiliste eesmärkide saavutamisega uute teadmiste ammutamist äratuntavate objektide olemuse kohta. Võimalus ammutada neid teadmisi, eriti teadmisi atribuutide (omaduste) vastasmõju mehhanismide kohta, on siin põhimõtteliselt piiratud sellise interaktsiooni antud struktuuriga, mis on fikseeritud otsustavate funktsioonide valitud vormis. Seetõttu on maksimaalne, mida saab pärast konkreetse diagnostikamudeli koostamist öelda, loetleda funktsioonide kombinatsioonid ja funktsioonid ise, mis on saadud mudelisse kaasatud. Kuid uuritavate objektide jaotuste olemust ja struktuuri peegeldavate kombinatsioonide tähendus jääb selle lähenemisviisi raames sageli avastamata.

Boole'i ​​meetodid. Mustrituvastuse loogilised meetodid põhinevad loogilise algebra aparaadil ja võimaldavad opereerida mitte ainult üksikutes tunnustes, vaid ka tunnuste väärtuste kombinatsioonides sisalduva teabega. Nendes meetodites käsitletakse mis tahes atribuudi väärtusi elementaarsete sündmustena.

Kõige üldisemal kujul võib loogilisi meetodeid iseloomustada kui omamoodi loogiliste mustrite otsimist koolitusvalimis ja teatud loogiliste otsustusreeglite süsteemi moodustamist (näiteks elementaarsündmuste sidesõnade kujul), iga millel on oma kaal. Loogiliste meetodite rühm on mitmekesine ja hõlmab erineva keerukuse ja analüüsi sügavusega meetodeid. Dihhotoomsete (tõve) tunnuste puhul on populaarsed nn puulaadsed klassifikaatorid, tupikkatsemeetod, Kora algoritm jt. Keerulisemad meetodid põhinevad D.S.Milli induktiivsete meetodite formaliseerimisel. Formaliseerimine viiakse läbi kvaasiaksiomaatilise teooria konstrueerimise teel ja see põhineb mitmesorditud mitme väärtusega loogikal koos kvantoritega muutuva pikkusega korteežide kohal.

Kora algoritm, nagu ka teised mustrituvastuse loogilised meetodid, on üsna töömahukas, kuna sidesõnade valimisel on vaja täielikku loendamist. Seetõttu esitatakse loogiliste meetodite rakendamisel kõrged nõuded arvutusprotsessi tõhusale korraldamisele ning need meetodid töötavad hästi suhteliselt väikeste funktsiooniruumi mõõtmetega ja ainult võimsatel arvutitel.

Keelelised (süntaktilised või struktuurilised) meetodid. Mustrituvastuse lingvistilised meetodid põhinevad keeli genereerivate spetsiaalsete grammatikate kasutamisel, mille abil saab kirjeldada äratuntavate objektide omaduste kogumit. Grammatika viitab nendest tuletamata elementidest objektide koostamise reeglitele.

Kui piltide kirjeldus on tehtud mittetuletiste elementide (alakujutiste) ja nende suhete abil, siis automaatsete tuvastussüsteemide ehitamisel kasutatakse omaduste ühisuse printsiipi kasutades keelelist või süntaktilist lähenemist. Kujutist saab kirjeldada, kasutades keele süntaktilise struktuuriga sarnast alamkujundite hierarhilist struktuuri. See asjaolu võimaldab rakendada formaalsete keelte teooriat mustrite tuvastamise probleemide lahendamisel. Eeldatakse, et kujutiste grammatika sisaldab lõplikke elementide komplekte, mida nimetatakse muutujateks, tuletamata elemente ja asendusreegleid. Asendusreeglite olemus määrab grammatika tüübi. Enim uuritud grammatikatest on tava-, kontekstivabad ja otseste koostisosade grammatikad. Selle lähenemise põhipunktid on pildi mittetuletuslike elementide valik, nende elementide ja nende seoste ühendamine kujundite grammatikateks ning lõpuks analüüsi- ja äratundmisprotsesside rakendamine vastavas keeles. . See lähenemine on eriti kasulik, kui töötate piltidega, mida ei saa kirjeldada numbriliste mõõtmistega või on nii keerulised, et nende lokaalseid omadusi ei ole võimalik tuvastada ja tuleb viidata objektide globaalsetele omadustele.

Näiteks E.A. Butakov, V.I. Ostrovski, I.L. Fadejev pakub pilditöötluseks järgmise süsteemistruktuuri (joonis 3), kasutades lingvistilist lähenemist, kus iga funktsionaalplokk on tarkvara (mikroprogrammi) kompleks (moodul), mis realiseerib vastavaid funktsioone.

Joonis 3. Tuvastaja struktuuriskeem

Katsed rakendada pildianalüüsi probleemile matemaatilise lingvistika meetodeid toovad kaasa vajaduse lahendada hulk probleeme, mis on seotud kahemõõtmelise pildistruktuuri kaardistamisega formaalse keele ühemõõtmelistele ahelatele.

Laiendusmeetodid

Selle rühma meetodites on erinevalt intensionaalsest suunast igale uuritavale objektile antud suuremal või vähemal määral iseseisev diagnostiline väärtus. Oma põhiolemuselt on need meetodid lähedased kliinilisele lähenemisele, mis käsitleb inimest mitte ühe või teise näitaja järgi järjestatud objektide ahelana, vaid terviklike süsteemidena, millest igaüks on individuaalne ja millel on eriline diagnostiline väärtus. Selline hoolikas suhtumine uuritavatesse objektidesse ei võimalda välistada ega kaotada teavet iga üksiku objekti kohta, mis ilmneb intensionaalse suuna meetodite rakendamisel, kasutades objekte ainult nende atribuutide käitumismustrite tuvastamiseks ja fikseerimiseks.

Peamised toimingud mustrituvastuses käsitletud meetodeid kasutades on objektide sarnasuse ja erinevuse määramise toimingud. Määratud meetodite rühma kuuluvad objektid mängivad diagnostiliste pretsedentide rolli. Samas võib individuaalse pretsedendi roll olenevalt konkreetse ülesande tingimustest varieeruda kõige laiemas piirides: peamisest ja määravast kuni väga kaudse osalemiseni tunnustamisprotsessis. Probleemi tingimused võivad omakorda nõuda edukaks lahendamiseks erineva arvu diagnostiliste pretsedentide osalemist: ühest igas äratuntavas klassis kuni kogu valimi suuruseni, samuti erinevaid viise sarnasuse ja erinevuse mõõtmiseks. objektid. Need nõuded selgitavad laiendusmeetodite edasist jaotamist alamklassidesse:

prototüüpide võrdlemise meetod;

k-lähima naabri meetod;

otsustusreeglite meeskonnad.

Prototüüpide võrdlemise meetod. See on lihtsaim laiendustuvastusmeetod. Seda kasutatakse näiteks siis, kui tuvastatud klassid kuvatakse objektiruumis kompaktsete geomeetriliste rühmitustega. Sel juhul valitakse tavaliselt prototüüppunktiks klassi geomeetrilise rühmituse keskpunkt (või keskpunktile lähim objekt).

Tundmatu objekti klassifitseerimiseks leitakse sellele lähim prototüüp ja objekt kuulub selle prototüübiga samasse klassi. Ilmselgelt ei moodustata selle meetodi puhul üldistatud klassipilte.

Läheduse mõõtmiseks saab kasutada erinevat tüüpi kaugusi. Sageli kasutatakse dihhotoomsete tunnuste puhul Hammingi kaugust, mis antud juhul võrdub eukleidilise kauguse ruuduga. Sel juhul on objektide klassifitseerimise otsustusreegel samaväärne lineaarse otsustusfunktsiooniga.

Seda asjaolu tuleks eriti tähele panna. See näitab selgelt seost prototüübi ja andmestruktuuri puudutava teabe indikatiivse esituse vahel. Kasutades ülaltoodud esitust, võib näiteks mis tahes traditsioonilist mõõteskaalat, mis on dihhotoomsete tunnuste väärtuste lineaarne funktsioon, pidada hüpoteetiliseks diagnostiliseks prototüübiks. Omakorda, kui tunnustatud klasside ruumilise struktuuri analüüs võimaldab järeldada, et need on geomeetriliselt kompaktsed, siis piisab, kui asendada kõik need klassid ühe prototüübiga, mis on tegelikult samaväärne lineaarse diagnostilise mudeliga.

Praktikas on olukord muidugi sageli kirjeldatud idealiseeritud näitest erinev. Teadlasel, kes kavatseb rakendada diagnostikaklasside prototüüpidega võrdlemisel põhinevat äratundmismeetodit, on rasked probleemid. See on ennekõike lähedusmõõdu (meetrika) valik, mis võib oluliselt muuta objektide jaotuse ruumilist konfiguratsiooni. Ja teiseks on iseseisev probleem eksperimentaalsete andmete mitmemõõtmeliste struktuuride analüüs. Mõlemad probleemid on uurija jaoks eriti teravad reaalsetele probleemidele omase tunnusruumi kõrge mõõtme tingimustes.

K-lähimate naabrite meetod. K-lähima naabri meetod diskriminantanalüüsi probleemide lahendamiseks pakuti esmakordselt välja 1952. aastal. See on järgmine.

Tundmatu objekti klassifitseerimisel leitakse etteantud arv (k) muid talle geomeetriliselt kõige lähemal olevaid objekte tunnusruumis (lähimad naabrid), mille kuuluvus on juba teada äratuntavatesse klassidesse. Otsus määrata tundmatu objekt konkreetsesse diagnostikaklassi tehakse, analüüsides teavet selle lähimate naabrite teadaoleva kuuluvuse kohta, kasutades näiteks lihtsat häälte lugemist.

Algselt peeti k-lähima naabri meetodit tõenäosussuhte hindamisel mitteparameetriliseks meetodiks. Selle meetodi puhul saadakse teoreetilised hinnangud selle tõhususe kohta võrreldes optimaalse Bayesi klassifikaatoriga. On tõestatud, et k-lähima naabri meetodi asümptootiliste vigade tõenäosused ületavad Bayesi reegli vigu mitte rohkem kui kaks korda.

Nagu eespool märgitud, on tegelike probleemide korral sageli vaja opereerida objektidega, mida kirjeldab suur hulk kvalitatiivseid (dihhotoomseid) tunnuseid. Samas on tunnusruumi mõõde proportsionaalne uuritava valimi mahuga või ületab selle. Sellistel tingimustel on mugav tõlgendada iga koolitusvalimi objekti eraldi lineaarse klassifikaatorina. Siis ei esinda seda või teist diagnostikaklassi mitte üks prototüüp, vaid lineaarsete klassifikaatorite komplekt. Lineaarsete klassifikaatorite kombineeritud interaktsiooni tulemuseks on tükkhaaval lineaarne pind, mis eraldab tunnusruumis äratuntavad klassid. Hüpertasandite tükkidest koosneva eralduspinna tüüp võib olla varieeruv ja sõltub klassifitseeritud agregaatide suhtelisest asukohast.

Võib kasutada ka teist k-lähima naabri klassifitseerimismehhanismide tõlgendust. See põhineb ideel mõnede varjatud muutujate olemasolust, mis on abstraktsed või seotud mõne teisendusega algse funktsiooniruumiga. Kui objektide paaridevahelised kaugused varjatud muutujate ruumis on samad, mis algtunnuste ruumis ja nende muutujate arv on palju väiksem kui objektide arv, siis võib kaaluda k-lähimate naabrite meetodi tõlgendust. tingimusliku tõenäosusjaotuse tiheduste mitteparameetriliste hinnangute võrdlemise seisukohast. Siin esitatud varjatud muutujate mõiste on oma olemuselt lähedane tõelise dimensioonilisuse kontseptsioonile ja muudele esitusviisidele, mida kasutatakse erinevates mõõtmete vähendamise meetodites.

Kui kasutate mustrite tuvastamiseks k-lähimate naabrite meetodit, peab uurija lahendama diagnoositud objektide läheduse määramise mõõdiku valimise keerulise probleemi. See probleem funktsiooniruumi suure mõõtme tingimustes on äärmiselt raskendatud selle meetodi piisava töömahukuse tõttu, mis muutub oluliseks isegi suure jõudlusega arvutite jaoks. Seetõttu on siin, nagu ka prototüüpide võrdlusmeetodi puhul, vaja lahendada eksperimentaalsete andmete mitmemõõtmelise struktuuri analüüsimise loominguline probleem, et minimeerida diagnostilisi klasse esindavate objektide arvu.

Hinnete arvutamise algoritmid (hääletus). Hindade arvutamise algoritmide (ABO) tööpõhimõte on tuvastatud ja võrdlusobjektide "lähedust" iseloomustava prioriteedi (sarnasusskooride) arvutamine vastavalt tunnuste ansamblite süsteemile, mis on antud objekti alamhulkade süsteem. funktsioonide komplekt.

Erinevalt kõigist varem käsitletud meetoditest töötavad hinnangute arvutamise algoritmid objektide kirjeldustega põhimõtteliselt uuel viisil. Nende algoritmide puhul eksisteerivad objektid samaaegselt funktsiooniruumi väga erinevates alamruumides. ABO klass viib tunnuste kasutamise idee loogilise järelduseni: kuna alati pole teada, millised tunnuste kombinatsioonid on kõige informatiivsemad, siis ABO-s arvutatakse objektide sarnasuse aste kõigi võimalike või teatud tunnuste kombinatsioonide võrdlemise teel. sisalduvad objektide kirjeldustes.

Otsustusreeglite meeskonnad. Otsustusreeglis kasutatakse kahetasandilist tunnustamisskeemi. Esimesel tasemel töötavad privaattuvastusalgoritmid, mille tulemused kombineeritakse teisel tasemel sünteesiplokis. Sellise kombinatsiooni kõige levinumad meetodid põhinevad konkreetse algoritmi pädevusvaldkondade jaotamisel. Lihtsaim viis kompetentsivaldkondade leidmiseks on tunnuste ruum a priori jagada, lähtudes konkreetse teaduse professionaalsetest kaalutlustest (näiteks valimi kihistamine mõne tunnuse järgi). Seejärel koostatakse iga valitud ala jaoks oma tuvastusalgoritm. Teine meetod põhineb formaalsel analüüsil, et määrata tunnusruumi lokaalsed alad äratuntavate objektide naabruskondadena, mille puhul on tõestatud mis tahes konkreetse tuvastamisalgoritmi edukus.

Kõige üldisem lähenemine sünteesiploki koostamisel käsitleb saadud osaalgoritmide indikaatoreid kui uue üldistatud otsustusreegli konstrueerimise algtunnuseid. Sel juhul saab mustrituvastuses kasutada kõiki ülaltoodud intensionaalsete ja pikendussuundade meetodeid. Otsustusreeglite komplekti loomise probleemi lahendamiseks on tõhusad "Kora" tüüpi loogilised algoritmid ja hinnangute arvutamise algoritmid (ABO), mis on aluseks niinimetatud algebralisele lähenemisviisile, mis pakub uurimistööd ja konstruktiivset kirjeldust. tuvastusalgoritmid, millesse mahuvad kõik olemasolevad algoritmitüübid.

Närvivõrgu meetodid

Närvivõrgu meetodid on meetodid, mis põhinevad erinevat tüüpi närvivõrkude (NN) kasutamisel. Erinevate NN-de peamised kasutusvaldkonnad mustrite ja kujutiste tuvastamiseks:

rakendus antud piltide põhiomaduste või funktsioonide eraldamiseks,

piltide endi või nendest juba eraldatud omaduste klassifitseerimine (esimesel juhul toimub põhiomaduste eraldamine võrgu sees kaudselt),

optimeerimisprobleemide lahendus.

Mitmekihilised närvivõrgud. Mitmekihilise närvivõrgu (MNN) arhitektuur koosneb järjestikku ühendatud kihtidest, kus iga kihi neuron on oma sisenditega ühendatud kõigi eelmise kihi neuronitega ning järgmise väljunditega.

Ühekihilise NN-i (nimetatakse automaatseks assotsiatiivseks mäluks) lihtsaim rakendus on koolitada võrk vookujutisi rekonstrueerima. Sisestades sisendisse testpildi ja arvutades rekonstrueeritud pildi kvaliteedi, saab hinnata, kui hästi võrk sisendpildi ära tundis. Selle meetodi positiivsed omadused on see, et võrk suudab taastada moonutatud ja mürarikkaid pilte, kuid see ei sobi tõsisemateks eesmärkideks.

MNN-i kasutatakse ka piltide otseseks klassifitseerimiseks - sisendiks on kas pilt ise mingil kujul või eelnevalt ekstraheeritud pildi võtmeomaduste kogum, väljundis näitab maksimaalse aktiivsusega neuron kuulumist tunnustatud klassi (joon. . 4). Kui see tegevus jääb alla teatud läve, siis loetakse, et esitatud pilt ei kuulu ühtegi teadaolevasse klassi. Õppeprotsess tuvastab sisendkujundite vastavuse teatud klassi kuulumisele. Seda nimetatakse juhendatud õppimiseks. See lähenemine on hea väikese inimrühma juurdepääsukontrolli ülesannete jaoks. See lähenemine võimaldab võrku võrrelda pilte endid, kuid klasside arvu suurenemisega pikeneb koolituse ja võrgu toimimise aeg hüppeliselt. Seetõttu nõuavad sellised toimingud nagu sarnase inimese otsimine suurest andmebaasist kompaktse võtmefunktsioonide komplekti väljavõtmist, millest otsida.

Kogu pildi sageduskarakteristikuid kasutavat klassifitseerimismeetodit kirjeldatakse artiklis. Kasutati mitme väärtusega neuronitel põhinevat ühekihilist NS-i.

B näitab NN-i kasutamist kujutiste klassifitseerimiseks, kui võrgusisend võtab vastu kujutise lagunemise tulemused põhikomponentide meetodil.

Klassikalises MNS-is on kihtidevahelised närviühendused täielikult ühendatud ja pilt on kujutatud ühemõõtmelise vektorina, kuigi see on kahemõõtmeline. Konvolutsioonilise närvivõrgu arhitektuuri eesmärk on need puudused ületada. See kasutas kohalikke retseptorivälju (pakkudes neuronite kohalikku kahemõõtmelist ühenduvust), üldisi kaalusid (mis võimaldas tuvastada mõningaid funktsioone kõikjal pildil) ja hierarhilist korraldust koos ruumilise alamvalimiga (ruumiline alamvalim). Konvolutsiooniline NN (CNN) tagab osalise vastupidavuse skaala muutustele, nihketele, pöörlemistele ja moonutustele.

MNS-i kasutatakse ka teatud tüüpi objektide tuvastamiseks. Lisaks sellele, et iga koolitatud MNS suudab mingil määral kindlaks teha, kas kujutised kuuluvad "oma" klassidesse, saab seda spetsiaalselt treenida teatud klasside usaldusväärseks tuvastamiseks. Sel juhul on väljundklassideks klassid, mis kuuluvad ja ei kuulu antud pilditüübi alla. Näopildi tuvastamiseks sisendpildis kasutati närvivõrgu detektorit. Pilt skaneeriti 20x20 pikslise aknaga, mis suunati võrgu sisendisse, mis otsustab, kas antud ala kuulub nägude klassi. Koolituse läbiviimisel kasutati nii positiivseid näiteid (erinevad näokujutised) kui ka negatiivseid näiteid (kujutised, mis ei ole näod). Tuvastamise usaldusväärsuse suurendamiseks kasutati erineva algraskusega treenitud NN-de meeskonda, mille tulemusena NN-d tegid erineval viisil vigu ning lõplik otsus tehti kogu meeskonna hääletamise teel.

Joonis 5. Põhikomponendid (omanägud) ja kujutise lagunemine põhikomponentideks

NN-i kasutatakse ka kujutise põhiomaduste eraldamiseks, mida seejärel kasutatakse hilisemaks klassifitseerimiseks. Aastal on näidatud meetod põhikomponentide analüüsi meetodi närvivõrgu rakendamiseks. Põhikomponentide analüüsi meetodi olemus on saada sisendmustreid iseloomustavad maksimaalselt dekorreleeritud koefitsiendid. Neid koefitsiente nimetatakse põhikomponentideks ja neid kasutatakse statistilise kujutise tihendamiseks, mille puhul kogu kujutise esitamiseks kasutatakse väikest arvu koefitsiente. NN ühe peidetud kihiga, mis sisaldab N neuronit (mis on palju väiksem kui pildi mõõde), mis on treenitud vigade tagasilevimise meetodil sisendkujutise taastamiseks väljundis, moodustab esimese N põhikomponendi koefitsiendid väljundis. peidetud neuronid, mida kasutatakse võrdluseks. Tavaliselt kasutatakse 10 kuni 200 põhikomponenti. Komponentide arvu suurenedes väheneb selle esinduslikkus tugevalt ning suurte arvudega komponente pole mõtet kasutada. Neuraalsete elementide mittelineaarsete aktiveerimisfunktsioonide kasutamisel on võimalik mittelineaarne lagunemine põhikomponentideks. Mittelineaarsus võimaldab teil sisendandmete variatsioone täpsemalt kajastada. Rakendades näopiltide dekomponeerimisel põhikomponentide analüüsi, saame põhikomponendid, mida nimetatakse õigeteks nägudeks, millel on ka kasulik omadus - on komponendid, mis peegeldavad peamiselt selliseid olulisi näoomadusi nagu sugu, rass, emotsioonid. Taastamisel on komponendid näokujulised, kusjuures esimene peegeldab näo kõige üldisemat kuju, teine ​​aga erinevaid väiksemaid erinevusi nägude vahel (joonis 5). See meetod sobib hästi sarnaste näopiltide otsimiseks suurtest andmebaasidest. Samuti on näidatud võimalus põhikomponentide mõõtmeid NS abil veelgi vähendada. Sisendpildi rekonstrueerimise kvaliteeti hinnates saab väga täpselt kindlaks teha, kas see kuulub nägude klassi.

Kõrgetasemelised närvivõrgud. Kõrge järgu närvivõrgud (HNN-id) erinevad MNN-idest selle poolest, et neil on ainult üks kiht, kuid neuronite sisendid saavad ka kõrget järku termineid, mis on sisendvektori kahe või enama komponendi korrutis. Sellised võrgud võivad moodustada ka keerukaid eralduspindu.

Hopfieldi närvivõrgud. Hopfield NN (HSH) on ühekihiline ja täielikult ühendatud (ei ole neuronite omavahelisi ühendusi), selle väljundid on ühendatud sisenditega. Erinevalt MNS-st on NSH lõdvestav, st. kui see on seatud algolekusse, töötab see seni, kuni jõuab stabiilsesse olekusse, mis on selle väljundväärtus. Optimeerimisprobleemide globaalse miinimumi otsimiseks kasutatakse NSH stohhastilisi modifikatsioone.

NSH kasutamine assotsiatiivse mäluna võimaldab teil täpselt taastada pildid, milleks võrk on koolitatud, kui sisendisse suunatakse moonutatud pilt. Sel juhul jätab võrk meelde lähima (kohaliku energiamiinimum tähenduses) pildi ja tunneb selle ära. Sellist funktsioneerimist võib pidada ka ülalkirjeldatud automaatse assotsiatiivse mälu järjestikuseks rakenduseks. Erinevalt automaatsest assotsiatiivsest mälust taastab NSH pildi täiesti täpselt. Häiremiinimumide vältimiseks ja võrgu läbilaskevõime suurendamiseks kasutatakse erinevaid meetodeid.

Kohonen iseorganiseeruvad närvivõrgud. Kohoneni iseorganiseeruvad närvivõrgud (SNNC) pakuvad sisendkujutise ruumi topoloogilist järjestust. Need võimaldavad topoloogiliselt pidevat sisend-n-mõõtmelise ruumi kaardistamist väljundiks m-mõõtmeline, m<

Cognitron. Kognitroon on oma arhitektuurilt sarnane visuaalse ajukoore struktuuriga, tal on hierarhiline mitmekihiline organisatsioon, milles kihtidevahelised neuronid on ühendatud ainult lokaalselt. Koolitatud võistlusõppe teel (ilma õpetajata). Iga ajukiht rakendab erinevaid üldistustasemeid; sisendkiht on tundlik lihtsate mustrite, näiteks joonte, ja nende orientatsiooni suhtes visuaalse ala teatud piirkondades, samas kui teiste kihtide reaktsioon on keerulisem, abstraktsem ja mustri asukohast sõltumatu. Sarnaseid funktsioone rakendatakse kognitronis, modelleerides visuaalse ajukoore korraldust.

Neokognitron on kognitironide idee edasiarendus ja peegeldab täpsemalt visuaalse süsteemi struktuuri, võimaldab ära tunda pilte sõltumata nende teisendustest, pöörlemistest, moonutustest ja mastaabimuutustest.

Cognitron on võimas pildituvastustööriist, kuid see nõuab suuri arvutuskulusid, mis on praegu kättesaamatud.

Vaadeldavad närvivõrgu meetodid tagavad kiire ja usaldusväärse pildituvastuse, kuid nende meetodite kasutamisel tekivad probleemid ruumiliste objektide äratundmisega. Sellel lähenemisviisil on aga palju eeliseid.

Järeldus

Praegu on erinevate rakendusprobleemide jaoks üsna palju automaatseid mustrituvastussüsteeme.

Mustri äratundmine formaalsete meetoditega fundamentaalse teadusliku suunana on ammendamatu.

Pilditöötluse matemaatilistel meetoditel on lai valik rakendusi: teadus, tehnoloogia, meditsiin, sotsiaalsfäär. Tulevikus suureneb mustrituvastuse roll inimelus veelgi.

Närvivõrgu meetodid tagavad kiire ja usaldusväärse pildituvastuse. Sellel lähenemisviisil on palju eeliseid ja see on üks paljutõotavamaid.

Kirjandus

D.V. Brilyuk, V.V. Starovoitov. Kujutise tuvastamise närvivõrgu meetodid // /

Kuzin L.T. Küberneetika alused: küberneetiliste mudelite alused. T.2. - M.: Energia, 1979. - 584 lk.

Peregudov F.I., Tarasenko F.P. Sissejuhatus süsteemianalüüsi: õpik. - M .: Kõrgkool, 1997. - 389s.

Temnikov F.E., Afonin V.A., Dmitriev V.I. Infotehnoloogia teoreetilised alused. - M.: Energia, 1979. - 511s.

Tu J., Gonzalez R. Mustri äratundmise põhimõtted. / Per. inglise keelest. - M.: Mir, 1978. - 410. aastad.

Winston P. Tehisintellekt. / Per. inglise keelest. - M.: Mir, 1980. - 520. aastad.

Fu K. Struktuursed meetodid mustrituvastuses: tõlgitud inglise keelest. - M.: Mir, 1977. - 320. aastad.

Tsypkin Ya.Z. Identifitseerimise infoteooria alused. - M.: Nauka, 1984. - 520ndad.

Pospelov G.S. Tehisintellekt on uue infotehnoloogia alus. - M.: Nauka, 1988. - 280ndad.

Yu Lifshits, Mustrituvastuse statistilised meetodid ///modern/07modernnote.pdf

Bohr N. Aatomifüüsika ja inimteadmised. / Tõlge inglise keelest. - M.: Mir, 1961. - 151s.

Butakov E.A., Ostrovski V.I., Fadejev I.L. Pilditöötlus arvutis.1987.-236s.

Duda R., Hart P. Mustri tuvastamine ja stseenianalüüs. / Tõlge inglise keelest. - M.: Mir, 1978. - 510. aastad.

Hertsog V.A. Arvuti psühhodiagnostika. - Peterburi: Vennaskond, 1994. - 365 lk.

Aizenberg I. N., Aizenberg N. N. ja Krivošejev G. A. Mitmeväärtuslikud ja universaalsed binaarsed neuronid: õppimisalgoritmid, rakendused pilditöötluseks ja äratundmiseks. Loengumärkmed tehisintellektist – masinõpe ja andmekaeve mustrituvastuses, 1999, lk. 21-35.

Ranganath S. ja Arun K. Näotuvastus teisendusfunktsioonide ja närvivõrkude abil. Mustri äratundmine 1997, kd. 30, lk. 1615-1622.

Golovko V.A. Neurointellekt: teooria ja rakendused. Raamat 1. Otsese ja tagasisidega närvivõrkude organiseerimine ja väljaõpe - Brest: BPI, 1999, - 260s.

Vetter T. ja Poggio T. Lineaarsed objektiklassid ja kujutise süntees ühest näidispildist. IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, lk. 733-742.

Golovko V.A. Neurointellekt: teooria ja rakendused. Raamat 2. Iseorganiseerumine, tõrketaluvus ja närvivõrkude kasutamine - Brest: BPI, 1999, - 228s.

Lawrence S., Giles C. L., Tsoi A. C. ja Back A. D. Näotuvastus: konvolutsiooniline närvivõrgu lähenemine. IEEE Transactions on Neural Networks, Special Issue on Neural Networks and Pattern Recognition, pp. 1-24.

Wasserman F. Neuroarvutitehnoloogia: teooria ja praktika, 1992 - 184lk.

Rowley H. A., Baluja S. ja Kanade T. Neuraalvõrgupõhine näotuvastus. IEEE Transactions on Pattern Analysis and Machine Intelligence 1998, Vol. 20, lk. 23-37.

Valentin D., Abdi H., O "Toole A. J. ja Cottrell G. W. Näotöötluse konneksionistlikud mudelid: uuring. IN: Pattern Recognition 1994, 27. kd, lk 1209-1230.

Dokument

Nad koostavad algoritme äratundminepilte. meetodidäratundminepilte Nagu eespool märgitud ... tegelikkus pole seda on olemas"ökosüsteemid üldiselt" ja olemas vaid mõned ... järeldused sellest üksikasjalikust arvustusmeetodidäratundmine esitlesime...

1. Ülevaade inimeste tuvastamise meetoditest näopiltide põhjal, võttes arvesse visuaalse tuvastamise tunnuseid

   Ülevaade

   ... äratundmine isiku poolt madala kontrastsusega objektide, sh. isikud. Toodud arvustus levinud meetodid ... Olemas terve rida meetodid ... tee, uuringu tulemusena platvormi arendamiseks meetodäratundmine ...

2. Imeni Glazkova Valentina Vladimirovna MITMETEEMALISTE HÜPERTEKSTIDOKUMENTIDE KLASSIFITSEERIMISE TARKVARATÖÖRIISTADE UURINGUD JA MEETODITE ARENDAMINE Eriala 05

   Väitekirja abstraktne

   hüperteksti dokumendid. Peatükk sisaldab arvustusolemasolevadmeetodid vaadeldava ülesande lahendus, kirjeldus ... kõige vähem olulised klassid ära lõigates // Matemaatika meetodidäratundminepilte: 13. ülevenemaaline konverents. Leningradi oblast...

3. Slide 0 Ülevaade bioinformaatika ülesannetest, mis on seotud geneetiliste tekstide analüüsi ja töötlemisega

   Loeng

   DNA ja valgu järjestused. Ülevaadeülesanded bioinformaatika ülesannetena ... signaalid nõuavad kaasaegsete kasutamist meetodidäratundminepilte, statistilised lähenemisviisid ja ... madala geenitihedusega. Olemasolev geeniennustusprogrammid ei...

Kaasaegsed nägemissüsteemidega varustatud robotid näevad hästi, et töötada reaalse maailmaga. Nad saavad järeldada, mis tüüpi objektid on olemas, millises suhtes nad omavahel on, milliseid rühmi nad moodustavad.

Tuvastamisprobleemi olemus seisneb selles, et teha kindlaks, kas uuritavatel objektidel on fikseeritud lõplik tunnuste hulk, mis võimaldab neid teatud klassile omistada.

Mustrituvastuse teaduse eesmärgid:

Inimeksperdi või keeruka ekspertsüsteemi asendamine lihtsama süsteemiga (inimtegevuse automatiseerimine või keerukate süsteemide lihtsustamine);

Õppesüsteemide ehitamine, mis on võimelised tegema otsuseid ilma selgeid reegleid määramata, nimelt süsteemid, mis suudavad ise otsustusreegleid sünteesida, tuginedes mõnele lõplikule arvule süsteemile “demonstreeritud” näidetele õigetest otsustest.

Tunnustamise ülesanded saab iseloomustada järgmiselt.

1. Need on informatiivsed ülesanded, mis koosnevad kahest põhietapist: lähteandmete viimine äratundmiseks mugavasse vormi ja äratundmine ise.

2. Nendes ülesannetes saab kasutusele võtta esemete analoogia ja sarnasuse mõiste ning sõnastada objektide läheduse mõiste, mis on aluseks objekti määramisel teatud klassi.

3. Nendes ülesannetes on võimalik opereerida näidete komplektiga, mille klassifikatsioon on teada ja mida formaliseeritud kirjelduste kujul saab esitada tuvastusalgoritmile õppeprotsessis ülesandega kohandamiseks.

4. Nende ülesannete jaoks on keeruline koostada formaalseid teooriaid ja rakendada klassikalisi matemaatilisi meetodeid.

5. Nende ülesannete puhul on võimalik "halb" teave.

Tuvastamisülesannete tüübid:

Esitletava objekti määramine ühte klassist (koolitus koos õpetajaga);

Automaatne klassifitseerimine - objektide (olukordade) kogumi jagamine vastavalt nende kirjeldusele mittekattuvate klasside süsteemiks;

Informatiivsete funktsioonide komplekti valimine äratundmiseks;

Lähteandmete viimine äratundmiseks mugavasse vormi;

Dünaamiline tuvastamine ja dünaamiline klassifikatsioon;

Prognoosimisülesanded.

Põhimääratlused

Pilt on objekti või nähtuse struktureeritud kirjeldus, mis on kujutatud tunnusvektoriga, mille iga element kujutab ühe antud objekti iseloomustava tunnuse arvväärtust. Teisisõnu: kujutis on mis tahes objekt, mille puhul saab mõõta teatud arvuliste tunnuste kogumit. Pildi näide: täht, pilt, kardiogramm jne.

Numbrimärk(või lihtsalt märk). on kindla numbrilise tunnusega objekti sobitamise meetodi valem või muu kirjeldus, mis toimib konkreetse mustrituvastusprobleemi raames. Iga objekti jaoks saab määratleda mitu erinevat tunnust, see tähendab mitu numbrilist tunnust.

funktsiooni ruumi.N-mõõtmeline ruum, mis on määratletud antud tuvastamisülesande jaoks, kus N on mis tahes objektide mõõdetud tunnuste fikseeritud arv. Tuvastamisprobleemi objektile vastav tunnusruumi vektor on N-mõõtmeline vektor komponentidega (x1, x2, ..., xN), mis on selle objekti tunnuste väärtused.

OBJEKT->Ntunnused->M-mõõtmeline tunnusvektor

Klass- mitteformaliseeritav (reeglina) idee võimalusest määrata tuvastusülesande objektide hulgast suvaline objekt teatud objektide rühmale. Sama klassi objektide puhul eeldatakse "sarnasuse" olemasolu. Mustrituvastuse probleemi jaoks saab määratleda suvalise arvu klasse, mis on suurem kui 1. Klasside arvu tähistatakse numbriga S.

Üldiselt koosneb mustrituvastuse probleem kahest osast: äratundmisest ja õppimisest.

Mustrituvastus on teatud objektide rühma klassifitseerimine teatud nõuete alusel. Samasse kujutiste klassi kuuluvatel objektidel on ühised omadused. Klassifikatsiooni määratlevad nõuded võivad olla erinevad, kuna erinevad olukorrad nõuavad erinevat tüüpi klassifikatsioone.

Näiteks ingliskeelsete tähtede äratundmisel moodustub 26 kujutiste klassi. Ingliskeelsete tähtede eristamiseks hiina tähemärkidest on äratundmisel vaja aga ainult kahte tüüpi pilte.

Lihtsaim viis mustrite tuvastamiseks on mustrite sobitamine. Sel juhul salvestatakse masina mällu piltide komplekt, üks igast pildiklassist. Sisend (tuntud klassi) kujutist võrreldakse iga klassi standardiga. Klassifikatsioon põhineb eelnevalt valitud sobivus- või sarnasuskriteeriumil. Teisisõnu, kui sisendpilt ühtib i-nda mustrite klassi mustriga paremini kui ükski teine ​​muster, siis klassifitseeritakse sisendmuster i-ndasse mustrite klassi kuuluvaks.

Selle lähenemise ehk standardiga sobitamise miinuseks on see, et mõnel juhul on raske igast pildiklassist sobivat standardit valida ja vajalikku sobivuskriteeriumi paika panna.

Täiustatud lähenemisviis on see, et klassifikatsioon põhineb mõnel sisendkujutistel tehtud valitud mõõtmiste komplektil. Eeldatakse, et need valitud mõõtmised, mida nimetatakse "funktsioonideks", on muutumatud või mittetundlikud sageli esinevate muutuste ja moonutuste suhtes ning neil on vähe redundantsi.

Teise “tunnuse mõõtmise” lähenemise erijuhtum, kus standardid salvestatakse mõõdetud tunnuste kujul ja klassifikaatoris kasutatakse spetsiaalset klassifitseerimiskriteeriumi (võrdlus).

Funktsioonid on määratlenud arendajad ja need peavad olema muutumatud objektide orientatsiooni, suuruse ja kuju variatsioonide suhtes.

Jne objektid, mida iseloomustab teatud omaduste ja tunnuste lõplik hulk. Selliseid ülesandeid lahendatakse üsna sageli näiteks foorituledes tänavat ületades või sõites. Põleva foori värvi äratundmine ja liiklusreeglite tundmine võimaldab teha õige otsuse, kas ületada tänav või mitte.

Vajadus sellise tunnustamise järele tekib erinevates valdkondades – alates sõjalistest asjadest ja turvasüsteemidest kuni analoogsignaalide digiteerimiseni.

Pildituvastuse probleem on muutunud silmapaistvaks teabe ülekülluse tingimustes, kui inimene ei saa hakkama temale saabuvate sõnumite lineaarselt järjestikuse mõistmisega, mille tulemusena lülitub tema aju samaaegse tajumise ja mõtlemise režiimile, millele selline äratundmine on iseloomulik.

Seetõttu pole juhus, et pildituvastuse probleem osutus interdistsiplinaarsete uuringute valdkonda - sealhulgas seoses tehisintellekti loomise ja tehniliste süsteemide loomisega. mustrituvastus tõmbab üha rohkem tähelepanu.

Entsüklopeediline YouTube

1 / 4

Sissejuhatus mustrituvastusse

R.V. Shamin. Loeng nr 6 Hopfieldi ja Hammingi võrgud mustrituvastuse probleemides

[DDSH-2016]: närvivõrgud ja kaasaegne arvutinägemine

Loeng 9. Eksponentsiaalne silumine. Mustri tuvastamine: k-s lähima naabri meetod

Subtiitrid

Juhised mustrituvastuses

On kaks peamist suunda:

• Elusolendite äratundmisvõimete uurimine, nende selgitamine ja modelleerimine;
• Rakenduslikel eesmärkidel üksikprobleemide lahendamiseks mõeldud seadmete konstrueerimise teooria ja meetodite väljatöötamine.

Probleemi ametlik avaldus

Mustrituvastus on algandmete määramine teatud klassi, tuues mitteoluliste andmete kogumassist esile neid andmeid iseloomustavad olulised tunnused.

Äratundmisprobleemide püstitamisel püütakse kasutada matemaatilist keelt, püüdes – vastupidiselt tehisnärvivõrkude teooriale, kus aluseks on tulemuse saamine läbi katse – asendada eksperiment loogilise arutluskäigu ja matemaatiliste tõestustega.

Mustrituvastuse probleemi klassikaline väide: antud objektide kogum. Neid tuleb klassifitseerida. Hulka esindavad alamhulgad, mida nimetatakse klassideks. Antud on: teave klasside kohta, kogu komplekti kirjeldus ja teabe kirjeldus objekti kohta, mille kuuluvus konkreetsesse klassi pole teada. Vastavalt olemasolevale teabele klasside ja objekti kirjelduse kohta tuleb määrata, millisesse klassi see objekt kuulub.

Kõige sagedamini käsitletakse mustrituvastusprobleemides ühevärvilisi kujutisi, mis võimaldab vaadelda pilti tasapinna funktsioonina. Kui arvestada tasapinnale seatud punkti T (\displaystyle T), kus funktsioon väljendab pildi igas punktis oma iseloomulikku - heledust, läbipaistvust, optilist tihedust, siis selline funktsioon on pildi formaalne salvestus.

Kõikide võimalike funktsioonide komplekt f (x, y) (\displaystyle f(x, y)) pinnal T (\displaystyle T)- on olemas kõigi piltide komplekti mudel X (\displaystyle X). Kontseptsiooni tutvustamine sarnasused piltide vahel saate määrata äratundmise ülesande. Sellise seadistuse konkreetne vorm sõltub suuresti tunnustamise järgmistest etappidest vastavalt ühele või teisele lähenemisviisile.

Mõned graafiliste piltide tuvastamise meetodid

Optilise kujutise tuvastamise jaoks saate rakendada iteratsiooni meetodit objekti välimuse üle erinevate nurkade, mõõtkavade, nihkete jms all. Tähtede puhul peate kordama fondi, fondi atribuute jne.

Teine lähenemisviis on leida objekti kontuur ja uurida selle omadusi (ühenduvus, nurkade olemasolu jne).

Teine võimalus on kasutada tehisnärvivõrke. See meetod nõuab kas suurt hulka tuvastusülesande näiteid (õigete vastustega) või spetsiaalset närvivõrgu struktuuri, mis arvestab selle ülesande eripäraga.

Pertseptron kui mustrite tuvastamise meetod

F. Rosenblatt, tutvustades ajumudeli kontseptsiooni, mille ülesandeks on näidata, kuidas psühholoogilised nähtused võivad tekkida mõnes füüsilises süsteemis, mille struktuur ja funktsionaalsed omadused on teada, kirjeldas lihtsamaid diskrimineerimiskatseid. Need katsed on täielikult seotud mustrituvastusmeetoditega, kuid erinevad selle poolest, et lahendusalgoritm ei ole deterministlik.

Lihtsaim eksperiment, mille põhjal on võimalik saada psühholoogiliselt olulist teavet teatud süsteemi kohta, taandub sellele, et mudel esitatakse kahe erineva stiimuliga ja on kohustatud neile reageerima erineval viisil. Sellise eksperimendi eesmärk võib olla uurida nende spontaanse diskrimineerimise võimalust süsteemi poolt, kui eksperimenteerija ei sekku, või vastupidi, uurida sunniviisilist diskrimineerimist, mille käigus katsetaja püüab õpetada süsteemi läbi viima nõutav klassifikatsioon.

Õppekatses esitatakse pertseptron tavaliselt teatud kujutiste jadaga, mis hõlmab iga eristatava klassi esindajaid. Mõne mälu muutmise reegli kohaselt tugevdatakse reaktsiooni õiget valikut. Seejärel esitatakse pertseptronile kontrollstiimul ja määratakse selle klassi stiimulitele õige vastuse saamise tõenäosus. Sõltuvalt sellest, kas valitud kontrollstiimul ühtib või ei ühti ühega treeningjärjestuses kasutatud kujutistest, saadakse erinevad tulemused:

1. Kui kontrollstiimul ei ühti ühegi õppimisstiimuliga, siis ei seostata eksperimenti ainult sellega puhas diskrimineerimine, vaid sisaldab ka elemente üldistused.
2. Kui kontrollstiimul ergastab teatud sensoorsete elementide komplekti, mis on täiesti erinevad nendest elementidest, mis aktiveerusid varem esitatud sama klassi stiimulite mõjul, siis on katse uurimine. puhas üldistus.

Pertseptronid ei oma puhta üldistusvõimet, kuid toimivad diskrimineerimiskatsetes üsna rahuldavalt, eriti kui kontrollstiimul langeb piisavalt täpselt kokku mõne mustriga, mille kohta pertseptronil on juba kogemusi kogunenud.

Näiteid mustrituvastusprobleemidest

• Vöötkoodi tuvastamine
• Numbrimärgituvastus
• Pildituvastus
• Maakoore kohalike alade äratundmine, kus maardlad asuvad

Käesolevas artiklis püüdsin esile tõsta mõningaid masinõppeteooria põhitulemusi viisil, mis muudab mõisted arusaadavaks lugejatele, kes on klassifitseerimis- ja regressiooniprobleemidega mõnevõrra tuttavad. Mõte kirjutada selline artikkel avaldus üha selgemalt minu peas iga loetud raamatuga, milles tuvastusmasinate õpetamise ideid räägiti otsekui keskelt ja jäi täiesti arusaamatuks, mis selle või teise meetodi autorid. millele selle väljatöötamisel tugineti. Teisest küljest on masinõppe põhimõistetele pühendatud mitmeid raamatuid, kuid neis sisalduva materjali esitamine võib esmalugemiseks tunduda liiga keeruline.

Motivatsioon

Vaatleme sellist ülesannet. Meil on kahe klassi õunu - maitsvad ja mittemaitsvad, 1 ja 0. Õuntel on omadused - värvus ja suurus. Värv muutub pidevalt vahemikus 0 kuni 1, st. 0 - täiesti roheline õun, 1 - täiesti punane. Suurus võib muutuda sarnaselt, 0 - väike õun, 1 - suur. Tahaksime välja töötada algoritmi, mis võtaks sisendiks värvi ja suuruse ning tagastaks väljundina õuna klassi – olgu see maitsev või mitte. Sel juhul on väga soovitav, et vigade arv oleks seda väiksem, seda parem. Samal ajal on meil lõplik nimekiri, mis sisaldab ajaloolisi andmeid õunte värvi, suuruse ja klassi kohta. Kuidas saaksime sellise probleemi lahendada?

loogiline lähenemine

Probleemi lahendamisel võib esimesena pähe tulla selline meetod: koostame käsitsi if-else tüübireeglid ja sõltuvalt värvi ja suuruse väärtustest määrame õunale kindla klassi. Need. meil on eeldused - see on värv ja suurus ning sellel on ka tagajärg - õuna maitse. See on üsna mõistlik, kui märke on vähe ja saab silma järgi hinnata võrdluslävesid. Aga võib juhtuda, et selgeid tingimusi ei suudeta välja mõelda ja andmetest ei selgu, milliseid lävendeid võtta ning edaspidi võib funktsioonide hulk suureneda. Aga mis siis, kui meie ajalooliste andmetega loendist leidsime kaks ühesuguse värvi ja suurusega õuna, kuid üks on märgitud maitsvaks ja teine ​​mitte? Seega ei ole meie esimene meetod nii paindlik ja skaleeritav, kui tahaksime.

Märge

Tutvustame järgmist tähistust. Tähistame th õuna kui . Omakorda koosneb igaüks kahest numbrist - värv ja suurus. Tähistame seda fakti numbripaariga: . Tähistame iga -nda õuna klassi kui . Ajalooliste andmetega loendit tähistatakse tähega, selle loendi pikkus on võrdne . Selle loendi th elemendiks on õuna ja selle klassi atribuudi väärtus. Need. . Nimetame seda ka prooviks. Suurtähtedega ja tähistame muutujaid, mis võivad võtta konkreetse tunnuse ja klassi väärtused. Tutvustame uut kontseptsiooni – otsustusreegel on funktsioon, mis võtab sisendiks värvi ja suuruse väärtuse ning tagastab väljundina klassi sildi:

Tõenäosuslik lähenemine

Arendades loogilise meetodi ideed eelduste ja tagajärgedega, esitame endale küsimuse - kui suur on tõenäosus, et meie valimisse mittekuuluv õun on mõõdetud väärtuste juures maitsev. värvi ja suuruse järgi? Tõenäosusteooria tähistuses saab selle küsimuse kirjutada järgmiselt:

Selles väljendis võib seda tõlgendada eeldusena, tagajärjena, kuid üleminek eelduselt tagajärjele järgib tõenäosusseadusi, mitte loogilisi. Need. klassi tõeväärtustega 0 ja 1 tõeväärtustabeli asemel on tõenäosusväärtused, mis võtavad väärtused vahemikus 0 kuni 1. Rakendage Bayesi valem ja hankige järgmine avaldis:

Vaatleme üksikasjalikumalt selle väljendi paremat külge. Kordajat nimetatakse eeltõenäosuseks ja see tähendab tõenäosust leida kõigi võimalike õunte hulgast maitsev õun. Ebamaitsva õunaga kohtumise a priori tõenäosus on . See tõenäosus võib peegeldada meie isiklikke teadmisi selle kohta, kuidas head ja halvad õunad looduses jagunevad. Näiteks teame oma varasemast kogemusest, et 80% kõikidest õuntest on maitsvad. Või saame hinnata seda väärtust lihtsalt loendades maitsvate õunte osakaalu meie loendis ajalooliste andmetega S. Järgmine kordaja näitab, kui tõenäoline on 1. klassi õuna jaoks teatud värvi ja suuruse väärtus. Seda väljendit nimetatakse ka tõenäosusfunktsioon ja võib olla mingi konkreetse jaotusega, näiteks normaaljaotusega. Nimetajat kasutame normaliseerimiskonstandina nii, et soovitud tõenäosus varieerub vahemikus 0 kuni 1. Meie lõppeesmärk ei ole leida tõenäosusi, vaid leida otsustusreegel, mis annaks meile kohe klassi. Otsustusreegli lõplik vorm sõltub sellest, milliseid väärtusi ja parameetreid me teame. Näiteks saame teada ainult eelneva tõenäosuse väärtusi ja ülejäänud väärtusi ei saa hinnata. Siis on otsustav reegel järgmine – määrata kõikidele õuntele selle klassi väärtus, mille a priori tõenäosus on suurim. Need. kui teame, et 80% õuntest looduses on maitsvad, siis paneme igale õunale klassi 1. Siis on meie viga 20%. Kui saame hinnata ka tõenäosusfunktsiooni $p(X=x_m | Y=1)$ väärtusi, siis saame Bayesi valemi abil leida ka vajaliku tõenäosuse väärtuse, nagu ülalpool kirjutatud. Otsustusreegel on siin järgmine: pange selle klassi silt, mille tõenäosus on maksimaalne:

Nimetame seda reeglit Bayesi klassifikaatoriks. Kuna tegemist on tõenäosustega, siis isegi suur tõenäosusväärtus ei garanteeri, et õun ei kuulu klassi 0. Hindame vea tõenäosust õunal järgmiselt: kui otsustusreegel tagastas klassi väärtuse, mis on võrdne 1-ga, siis vea tõenäosus on ja vastupidi:

Meid huvitab klassifikaatori vea tõenäosus mitte ainult selles konkreetses näites, vaid üldiselt kõigi võimalike õunte puhul:

See avaldis on vea matemaatiline ootus. Niisiis, algse probleemi lahendamisel jõudsime Bayesi klassifikaatorini, kuid millised on selle puudused? Peamine probleem on tingliku tõenäosuse hindamine andmete põhjal. Meie puhul kujutame objekti arvude paarina - värv ja suurus, kuid keerukamate ülesannete puhul võib tunnuste mõõde olla kordades suurem ja meie loendist koos ajalooliste andmetega tehtud vaatluste arv ei pruugi olla piisav, et hinnata mitmemõõtmelise juhusliku suuruse tõenäosust. Järgmisena proovime üldistada oma klassifikaatori vea kontseptsiooni ja vaadata, kas probleemi lahendamiseks on võimalik valida mõni muu klassifikaator.

Kaod klassifikaatori vigade tõttu

Oletame, et meil on juba mingi otsustusreegel. Siis võib see teha kahte tüüpi vigu – esimene on määrata objekt klassi 0, mille reaalklass on 1, ja vastupidi, määrata objekt klassi 1, mille reaalklass on 0. probleeme, võib olla oluline nendel juhtudel vahet teha. Näiteks kannatame rohkem selle pärast, et maitsvaks märgitud õun osutus maitsetuks ja vastupidi. Me vormistame oma ebamugavuse määra kontseptsioonis petetud ootustest. Üldisemalt on meil kadufunktsioon, mis tagastab iga klassifikaatori vea kohta arvu. Olgu tõeline klassi silt. Seejärel tagastab kadufunktsioon tegeliku klassisildi kaduväärtuse ja meie otsustusreegli väärtuse. Selle funktsiooni kasutamise näide on võtta teadaoleva klassiga õunast, edastada õun meie otsustusreegli sisendisse, saada otsustusreeglist klassi hinnang, kui väärtused ja ühtivad, siis arvestame, et klassifikaator ei eksinud ja kadu pole, kui väärtused ei ühti, siis ütleb meie funktsioon kao suurust

Tingimuslik ja Bayesi risk

Nüüd, kui meil on kadufunktsioon ja me teame, kui palju me kaotame objektide valesti klassifitseerimisest, oleks tore mõista, kui palju me kaotame keskmiselt paljude objektide puhul. Kui teame väärtust - tõenäosus, et -s õun on maitsev, arvestades mõõdetud värvi ja suuruse väärtusi, samuti klassi tegelikku väärtust (näiteks võtke õun proovist S, vt artikli alguses), siis saame tutvustada tingimusliku riski mõistet. Tingimuslik risk on otsustusreegli jaoks määratud kahjumi keskmine väärtus:

Meie binaarse klassifikatsiooni puhul, kui selgub:

Eespool kirjeldasime otsustusreeglit, mis määrab objekti kõrgeima tõenäosusväärtusega klassile. Selline reegel annab meie keskmiste kahjude miinimumi (Bayesi risk), seega on Bayesi klassifikaator meie kasutusele võetud riskifunktsiooni seisukohalt optimaalne. . See tähendab, et Bayesi klassifikaatoril on väikseim võimalik klassifitseerimisviga.

Mõned tüüpilised kadufunktsioonid

Üks levinumaid kadufunktsioone on sümmeetriline funktsioon, kui esimest ja teist tüüpi vigadest tulenevad kaod on samaväärsed. Näiteks 1-0 kadufunktsioon (null-üks kaotus) on määratletud järgmiselt:

Siis on tingimuslikuks riskiks a(x) = 1 puhul lihtsalt tõenäosusväärtus saada objektil klass 0:

Samamoodi, kui a(x) = 0:

Kaofunktsioon 1-0 võtab väärtuse 1, kui klassifikaator teeb objektil vea, ja 0, kui ta seda ei tee. Nüüd teeme nii, et vea väärtus ei ole 1, vaid mõni teine ​​funktsioon Q, olenevalt otsustusreeglist ja reaalklassi sildist:

Siis saab tingimusliku riski kirjutada järgmiselt:

Märkused noodikirja kohta

Eelmine tekst on kirjutatud Duda ja Harti raamatus omaks võetud noodikirja järgi. Algses raamatus V.N. Vapnik vaatles sellist protsessi: loodus valib objekti jaotuse $p(x)$ järgi ja seejärel määrab sellele klassisildi vastavalt tingimuslikule jaotusele $p(y|x)$. Seejärel defineeritakse risk (kahjumiootus) kui

Kus on funktsioon, millega me proovime tundmatut sõltuvust lähendada, on reaalväärtuse kadufunktsioon ja meie funktsiooni väärtus. See märge on kirjeldavam, et tutvustada järgmist mõistet – empiiriline risk.

Empiiriline risk

Selles etapis oleme juba avastanud, et loogiline meetod ei sobi meile, kuna see ei ole piisavalt paindlik ja me ei saa kasutada Bayesi klassifikaatorit, kui funktsioone on palju ja treenimiseks on piiratud arv andmeid, ja me ei saa seda tõenäosust taastada. Teame ka seda, et Bayesi klassifikaatoril on väikseim võimalik klassifitseerimisviga. Kuna me ei saa kasutada Bayesi klassifikaatorit, võtame midagi lihtsamat. Parandame mõne parameetrilise funktsioonide perekonna H ja valime sellest perekonnast klassifikaatori.

Näide: olgu vormi kõigi funktsioonide hulk

Kõik selle hulga funktsioonid erinevad üksteisest ainult koefitsientide poolest. Sellise perekonna valimisel eeldasime, et klassi 1 punktide ja klassi 0 punktide vahelises värvisuuruses koordinaatides saame tõmmata koefitsientidega sirge sellises nii, et erinevate klassidega punktid paiknevad piki sirge vastaskülgi. On teada, et seda tüüpi sirge korral on koefitsientide vektor sirge normaalne. Nüüd teeme nii – võtame oma õuna, mõõdame selle värvi ja suuruse ning joonistame saadud koordinaatidega punkti graafikule värvisuuruse telgedele. Järgmisena mõõdame selle punkti ja vektori $w$ vahelist nurka. Märgime, et meie punkt võib asuda kas ühel või teisel pool joont. Siis on punkti ja punkti vaheline nurk terav või nüri ning skalaarkorrutis on kas positiivne või negatiivne. Siit tulebki otsustusreegel:

Pärast seda, kui oleme funktsioonide klassi $H$ fikseerinud, tekib küsimus - kuidas valida sealt vajalike koefitsientidega funktsioon? Vastus on – valime funktsiooni, mis tagab meie Bayesi riski $R()$ miinimumi. Jällegi on probleem selles, et Bayesi riski väärtuste arvutamiseks peate teadma jaotust $p(x,y)$, kuid seda meile ei anta ja seda pole alati võimalik taastada. seda. Teine idee on minimeerida riski mitte kõigil võimalikel objektidel, vaid ainult näidisel. Need. minimeerimisfunktsioon:

Seda funktsiooni nimetatakse empiiriliseks riskiks. Järgmine küsimus on, miks me otsustasime, et minimeerides empiirilist riski, minimeerime ka Bayesi riski? Tuletan meelde, et meie praktiline ülesanne on teha võimalikult vähe klassifitseerimisvigu. Mida vähem vigu, seda väiksem on Bayesi risk. Põhjenduse empiirilise riski lähenemiseks Bayesi keelele koos andmete hulga suurenemisega leidsid 70ndatel kaks teadlast - V. N. Vapnik ja A. Ya. Chervonenkis.

Lähenemisgarantiid. Lihtsaim juhtum

Seega oleme jõudnud järeldusele, et Bayesi klassifikaator annab väikseima võimaliku vea, kuid enamikul juhtudel ei saa me seda treenida, samuti ei saa me viga (riski) arvutada. Siiski saame arvutada lähenduse Bayesi riskile, mida nimetatakse empiiriliseks riskiks, ja teades empiirilist riski, valida ligikaudse funktsiooni, mis minimeeriks empiirilise riski. Vaatleme kõige lihtsamat olukorda, kus empiiriline riski minimeerimine annab klassifikaatori, mis minimeerib ka Bayesi riski. Kõige lihtsamal juhul peame tegema eelduse, mis praktikas täitub harva, kuid mida saab hiljem nõrgendada. Kinnitame piiratud funktsioonide klassi, mille hulgast valime oma klassifikaatori ja eeldame, et tegelik funktsioon, mida loodus kasutab meie õunte maitse järgi märkimiseks, on selles piiratud hüpoteeside komplektis: . Meil on ka näidis, mis on saadud objektide jaotusest. Kõik näidisobjektid loetakse võrdselt sõltumatult jaotunuks (iid). Siis vastab järgnev tõele

Teoreem

Valides empiirilist riskiminimeerimist kasutavast klassist funktsiooni, leiame kindlasti väikese Bayesi riskiväärtusega funktsiooni, kui valim, mida minimeerime, on piisava suurusega.

Mõistete "väike väärtus" ja "piisav suurus" tähendusi vaadake allolevast kirjandusest.

Tõestuse idee

Teoreemi tingimusel saame valimi jaotusest , s.o. loodusest objektide valimise protsess on juhuslik. Iga kord, kui proovi kogume, on see samast jaotusest, kuid selles olevad objektid võivad olla erinevad. Tõestuse põhiidee seisneb selles, et saame nii õnnetu valimi, et algoritm, mille me valime antud valimi empiirilise riski minimeerides, on Bayesi riski minimeerimisel halb, kuid samas hea empiirilise riski minimeerimiseks, kuid sellise valimi saamise tõenäosus on väike ja valimi suurus suureneb, see tõenäosus langeb. Sarnased teoreemid on olemas ka realistlikumate eelduste jaoks, kuid me neid siin ei käsitle.

Praktilised tulemused

Kui on tõendeid selle kohta, et empiirilise riski minimeerimisel leitud funktsioonil ei teki piisava mahuga koolitusvalimi korral varem vaadeldud andmetel suurt viga, saame seda põhimõtet praktikas kasutada näiteks järgmiselt - võtame avaldise:

Ja sõltuvalt lahendatavast probleemist asendame erinevad kadufunktsioonid. Lineaarse regressiooni jaoks:

Logistilise regressiooni jaoks:

Kuigi tugivektori masinaid motiveerib peamiselt geomeetria, võib neid pidada ka empiirilisteks riskide minimeerimise probleemideks.

Järeldus

Paljusid juhendatud õppemeetodeid võib muuhulgas pidada V. N. Vapniku ja A. Ya. Chervonenkise väljatöötatud teooria erijuhtudeks. See teooria annab garantiid testikomplektis esineva vea kohta, eeldusel, et treeningkomplekt on piisavalt suur ja mõned nõuded hüpoteesiruumile, millest me oma algoritmi otsime.

Kasutatud Raamatud

• Statistilise õppimisteooria olemus, Vladimir N. Vapnik
• Mustri klassifikatsioon, 2. väljaanne, Richard O. Duda, Peter E. Hart, David G. Stork
• Masinõppe mõistmine: teooriast algoritmideni, Shai Shalev-Shwartz, Shai Ben-David

P.S. Kõigist ebatäpsustest ja kirjavigadest palun kirjutage isiklikult

Sildid: lisa sildid

Elussüsteemid, sealhulgas inimesed, on nende loomisest saati pidevalt seisnud silmitsi mustrite tuvastamise ülesandega. Eelkõige töötleb meeleelunditest tulevat infot aju, mis omakorda sorteerib infot, tagab otsuste tegemise ning seejärel elektrokeemiliste impulsside abil edastab vajaliku signaali edasi, näiteks liikumisorganitesse. , mis rakendavad vajalikke meetmeid. Siis toimub keskkonnamuutus ja ülaltoodud nähtused korduvad. Ja kui vaadata, siis iga etapiga kaasneb tunnustus.

Arvutitehnoloogia arenguga sai võimalikuks lahendada mitmeid eluprotsessis tekkivaid probleeme, hõlbustada, kiirendada, parandada tulemuse kvaliteeti. Näiteks erinevate elu toetavate süsteemide toimimine, inimese ja arvuti interaktsioon, robotsüsteemide tekkimine jne. Samas märgime, et praegu ei ole võimalik mõne ülesande puhul (kiiresti liikuvate sarnaste objektide äratundmine) rahuldavat tulemust anda. , käsitsi kirjutatud tekst).

Töö eesmärk: uurida mustrituvastussüsteemide ajalugu.

Märkida mustrituvastuse valdkonnas toimunud kvalitatiivsed muutused, nii teoreetilised kui tehnilised, tuues ära põhjused;

Arutleda arvutustehnikas kasutatavate meetodite ja põhimõtete üle;

Tooge näiteid lähitulevikus oodatavate väljavaadete kohta.

1. Mis on mustrituvastus?

Esimesed arvutitehnoloogiaga seotud uuringud järgisid põhimõtteliselt klassikalist matemaatilise modelleerimise skeemi – matemaatilist mudelit, algoritmi ja arvutust. Need olid aatomipommide plahvatuste käigus toimuvate protsesside modelleerimine, ballistiliste trajektooride arvutamine, majanduslikud ja muud rakendused. Kuid lisaks selle seeria klassikalistele ideedele leidus ka täiesti teistsuguse olemusega meetodeid ja nagu mõne ülesande lahendamise praktika näitas, andsid need sageli paremaid tulemusi kui ülekeerulistel matemaatilistel mudelitel põhinevad lahendused. Nende idee oli loobuda soovist luua uuritavast objektist ammendav matemaatiline mudel (pealegi oli sageli praktiliselt võimatu konstrueerida adekvaatseid mudeleid) ning selle asemel rahulduda vastusega vaid meid huvitavatele konkreetsetele küsimustele ning neid vastuseid tuleks otsida paljudele probleemidele ühistest kaalutlustest. Seda laadi uurimistöö hõlmas visuaalsete kujutiste tuvastamist, saagikuse, jõgede taseme prognoosimist, naftakandjate ja põhjaveekihtide eristamise probleemi kaudsete geofüüsikaliste andmete abil jne. Nende ülesannete puhul oli vaja konkreetset vastust üsna lihtsal kujul, näiteks näiteks kas objekt kuulub mõnda eelfikseeritud klassi. Ja nende ülesannete lähteandmed esitati reeglina uuritavate objektide kohta killustatud teabe kujul, näiteks eelnevalt klassifitseeritud objektide komplekti kujul. Matemaatilisest vaatenurgast tähendab see, et mustrituvastus (ja seda probleemide klassi nimetati meie riigis) on funktsioonide ekstrapoleerimise idee kaugeleulatuv üldistus.

Sellise sõnastuse tähtsus tehnikateaduste jaoks on väljaspool kahtlust ja see iseenesest õigustab arvukaid uuringuid selles valdkonnas. Mustrituvastuse probleemil on aga loodusteaduse jaoks ka laiem aspekt (oleks aga imelik, kui tehisküberneetiliste süsteemide jaoks midagi nii olulist poleks looduslike jaoks oluline). Selle teaduse kontekst hõlmas orgaaniliselt iidsete filosoofide küsimusi meie teadmiste olemuse, meie võime kohta ära tunda ümbritseva maailma pilte, mustreid ja olukordi. Tegelikult pole praktiliselt kahtlustki, et kõige lihtsamate kujundite, näiteks läheneva ohtliku kiskja või toidu kujutiste äratundmise mehhanismid tekkisid palju varem, kui tekkis elementaarne keel ja formaalne loogiline aparaat. Ja pole kahtlustki, et sellised mehhanismid on piisavalt arenenud ka kõrgematel loomadel, kes oma elutegevuses vajavad samuti hädasti oskust eristada üsna keerulist loodusmärkide süsteemi. Seega näeme looduses, et mõtlemise ja teadvuse fenomen põhineb selgelt mustrite äratundmise võimel ning intelligentsuse teaduse edasine areng on otseselt seotud äratundmise põhiseaduste mõistmise sügavusega. Mõistes tõsiasja, et ülaltoodud küsimused ulatuvad palju kaugemale mustrituvastuse standarddefinitsioonist (ingliskeelses kirjanduses on termin supervised learning rohkem levinud), on vaja mõista ka seda, et neil on selle suhteliselt kitsa (kuid siiski kauge) seos. kurnatud) suunast.

Ka praegu on mustrituvastus kindlalt igapäevaellu sisenenud ja on kaasaegse inseneri üks elulisemaid teadmisi. Meditsiinis aitab mustrituvastus arstidel täpsemaid diagnoose panna, tehastes kasutatakse seda kaubapartiide defektide ennustamiseks. Biomeetrilised isikutuvastussüsteemid kui nende algoritmiline tuum põhinevad samuti selle distsipliini tulemustel. Tehisintellekti edasiarendamine, eelkõige viienda põlvkonna arvutite projekteerimine, mis suudavad inimesega loomulikes keeltes inimeste jaoks ja kõne kaudu suhelda otsesemalt, on mõeldamatu ilma äratundmiseta. Siin on robootika ehk kunstlikud juhtimissüsteemid, mis sisaldavad tuvastussüsteeme elutähtsate alamsüsteemidena, käeulatuses.

Seetõttu pöörasid mustrituvastuse arendamisele algusest peale suurt tähelepanu erineva profiiliga spetsialistid - küberneetika, neurofüsioloogid, psühholoogid, matemaatikud, majandusteadlased jne. Suuresti sel põhjusel toidab kaasaegne mustrituvastus ise nende distsipliinide ideedest. Täiuslikkusele pretendeerimata (ja seda on võimatu väita lühikeses essees), kirjeldame mustrituvastuse ajalugu, võtmeideid.

Definitsioonid

Enne mustrituvastuse peamiste meetodite juurde asumist anname mõned vajalikud määratlused.

Kujutiste (objektide, signaalide, olukordade, nähtuste või protsesside) äratundmine on ülesanne tuvastada objekt või määrata selle mis tahes omadus pildi (optiline äratundmine) või helisalvestuse (akustiline äratundmine) ja muude tunnuste järgi.

Üks põhilisi on komplekti kontseptsioon, millel pole kindlat sõnastust. Arvutis esindab hulka sama tüüpi mittekorduvate elementide hulk. Sõna "mittekorduv" tähendab, et mõni element komplektis on kas olemas või ei ole. Universaalne komplekt sisaldab kõiki võimalikke elemente lahendatava probleemi jaoks, tühi komplekt ei sisalda ühtegi.

Pilt on klassifikatsioonisüsteemis olev klassifitseerimisrühmitus, mis ühendab (eraldab) teatud objektide rühma mõne atribuudi järgi. Piltidel on iseloomulik omadus, mis väljendub selles, et samast hulgast piiratud arvu nähtustega tutvumine võimaldab ära tunda meelevaldselt suure hulga selle esindajaid. Piltidel on iseloomulikud objektiivsed omadused selles mõttes, et erinevad inimesed, kes õpivad erinevast vaatlusmaterjalist, liigitavad samu objekte enamasti ühtemoodi ja üksteisest sõltumatult. Tunnustusprobleemi klassikalises sõnastuses on universaalne hulk jagatud osadeks-kujunditeks. Iga objekti kaardistamist äratundmissüsteemi tajuorganitega, olenemata selle asukohast nende organite suhtes, nimetatakse tavaliselt objekti kujutiseks ja selliste kujutiste komplektid, mida ühendavad mõned ühised omadused, on kujutised.

Mis tahes kujutisele elemendi määramise meetodit nimetatakse otsustusreegliks. Teine oluline mõiste on mõõdikud, universaalse komplekti elementide vahelise kauguse määramise viis. Mida väiksem on see kaugus, seda sarnasemad on objektid (sümbolid, helid jne), mida me ära tunneme. Tavaliselt määratakse elemendid arvude kogumina ja mõõdik funktsioonina. Programmi efektiivsus sõltub piltide esitusviisi valikust ja mõõdiku rakendamisest, üks erinevate mõõdikutega tuvastusalgoritm teeb erineva sagedusega vigu.

Õppimist nimetatakse tavaliselt protsessiks, mille käigus arendatakse mõnes süsteemis konkreetne reaktsioon väliste identsete signaalide rühmadele, mõjutades korduvalt välist parandussüsteemi. Sellist välist kohandamist treeningutel nimetatakse tavaliselt "julgustamiseks" ja "karistuseks". Selle kohanduse genereerimise mehhanism määrab peaaegu täielikult õppimisalgoritmi. Iseõppimine erineb õppimisest selle poolest, et siin ei esitata lisateavet süsteemile reageerimise õigsuse kohta.

Kohanemine on süsteemi parameetrite ja struktuuri ning võimalusel ka juhtimistoimingute muutmise protsess, mis põhineb jooksval infol, et saavutada süsteemi teatud olek esialgse ebakindluse ja muutuvate töötingimustega.

Õppimine on protsess, mille tulemusena omandab süsteem järk-järgult võime reageerida vajalike reaktsioonidega teatud kogumitele välismõjudele ning kohanemine on süsteemi parameetrite ja struktuuri kohandamine eesmärgiga saavutada vajalikku kvaliteeti. kontroll välistingimuste pidevate muutuste tingimustes.

Näiteid mustrituvastusülesannetest: - Tähtede tuvastamine;