Teori om mønstergjenkjenning. Metoder basert på antakelser om klassen av beslutningsfunksjoner

Og tegn. Slike oppgaver løses ganske ofte, for eksempel når du krysser eller kjører en gate i trafikklys. Anerkjennelse av fargen på et lyskryss og kunnskap om reglene trafikk lar deg ta den riktige avgjørelsen om du skal krysse gaten eller ikke for øyeblikket.

I prosess biologisk evolusjon mange dyr ved hjelp av visuelle og auditive apparater løste problemer mønstergjenkjenning bra nok. Opprettelse kunstige systemer mønstergjenkjenning forblir en kompleks teoretisk og Tekniske problemer. Behovet for slik anerkjennelse oppstår på en rekke områder – fra militære saker og sikkerhetssystemer til digitalisering av alle slags analoge signaler.

Tradisjonelt er bildegjenkjenningsoppgaver inkludert i omfanget av kunstig intelligensoppgaver.

Veibeskrivelse i mønstergjenkjenning

Det er to hovedretninger:

Studiet av gjenkjennelsesevner som levende vesener besitter, deres forklaring og modellering;
Utvikling av teori og metoder for å konstruere enheter designet for å løse individuelle problemer i anvendte problemer.

Formell redegjørelse for problemet

Mønstergjenkjenning er tilordningen av innledende data til en bestemt klasse ved å fremheve essensielle funksjoner som karakteriserer disse dataene fra total masse irrelevante data.

Når de setter gjenkjenningsproblemer, prøver de å bruke det matematiske språket, og prøver, i motsetning til teorien om kunstige nevrale nettverk, hvor grunnlaget er å oppnå et resultat ved å eksperimentere, å erstatte eksperimentet med logiske resonnementer og matematiske bevis.

Oftest vurderes monokrome bilder i mønstergjenkjenningsproblemer, noe som gjør det mulig å betrakte et bilde som en funksjon på et plan. Hvis vi vurderer poengsett på overflaten T, hvor funksjonen x(x,y) uttrykker på hvert punkt av bildet dens karakteristikk - lysstyrke, gjennomsiktighet, optisk tetthet, så er en slik funksjon en formell registrering av bildet.

Settet med alle mulige funksjoner x(x,y) på overflaten T- det er en modell av settet med alle bilder X. Introduserer konseptet likheter mellom bildene kan du angi oppgaven med gjenkjenning. Den spesifikke formen for en slik setting avhenger sterkt av de påfølgende stadiene i anerkjennelse i samsvar med en eller annen tilnærming.

Metoder for mønstergjenkjenning

Til optisk gjenkjenning bilder, kan du bruke metoden for å iterere objekttypen i forskjellige vinkler, skalaer, forskyvninger osv. For bokstaver må du iterere over fonten, skriftegenskaper osv.

Den andre tilnærmingen er å finne konturen til objektet og undersøke dets egenskaper (tilkobling, tilstedeværelse av hjørner, etc.)

En annen tilnærming er å bruke kunstige nevrale nettverk. Denne metoden krever enten et stort antall eksempler på en gjenkjennelsesoppgave (med riktige svar), eller en spesiell struktur av et nevralt nettverk som tar hensyn til spesifikasjonene til denne oppgaven.

Perceptron som en metode for mønstergjenkjenning

F. Rosenblatt, introduserer konseptet med en hjernemodell, hvis oppgave er å vise hvordan, i noen fysisk system, struktur og funksjonelle egenskaper som er kjent, kan forekomme psykologiske fenomener- beskrevet det enkleste diskrimineringseksperimenter. Disse eksperimentene er helt relatert til mønstergjenkjenningsmetoder, men skiller seg ut ved at løsningsalgoritmen ikke er deterministisk.

Det enkleste eksperimentet, på grunnlag av hvilket det er mulig å få psykologisk signifikant informasjon om et bestemt system, koker ned til det faktum at modellen presenteres med to forskjellige stimuli og er pålagt å svare på dem på forskjellige måter. Hensikten med et slikt eksperiment kan være å studere muligheten for deres spontane diskriminering av systemet i fravær av intervensjon fra eksperimentatoren, eller omvendt å studere tvungen diskriminering, der eksperimentatoren søker å lære systemet å utføre nødvendig klassifisering.

I et læringseksperiment blir en perceptron vanligvis presentert med en viss sekvens av bilder, som inkluderer representanter for hver av klassene som skal skilles ut. I henhold til noen minnemodifikasjonsregel forsterkes det riktige valget av reaksjon. Deretter blir kontrollstimulus presentert for perceptronen og sannsynligheten for å oppnå riktig respons for stimuli av denne klassen bestemmes. Avhengig av om den valgte kontrollstimulusen samsvarer med eller ikke samsvarer med et av bildene som ble brukt i treningssekvensen, oppnås forskjellige resultater:

1. Hvis kontrollstimulus ikke sammenfaller med noen av læringsstimuliene, er eksperimentet ikke bare assosiert med ren diskriminering, men inkluderer også elementer generaliseringer.
2. Hvis kontrollstimulusen eksiterer et visst sett med sensoriske elementer som er helt forskjellige fra de elementene som ble aktivert under påvirkning av tidligere presenterte stimuli fra samme klasse, så er eksperimentet en studie ren generalisering .

Perceptroner har ikke kapasitet til ren generalisering, men de fungerer ganske tilfredsstillende i diskrimineringseksperimenter, spesielt hvis kontrollstimulusen sammenfaller tett nok med et av mønstrene som perceptronen allerede har akkumulert noe erfaring om.

Eksempler på problemer med mønstergjenkjenning

Bokstavgjenkjenning.
Strekkodegjenkjenning.
Nummerskiltgjenkjenning.
Ansiktsgjenkjenning.
Talegjenkjenning.
Bildegjenkjenning.
Anerkjennelse av lokalområder jordskorpen som inneholder mineralforekomster.

Mønstergjenkjenningsprogrammer

se også

Notater

Linker

Yuri Lifshits. Emne "Modern Problems of Teoretical Informatics" - forelesninger vedr statistiske metoder bildegjenkjenning, ansiktsgjenkjenning, tekstklassifisering
Journal of Pattern Recognition Research (Journal of Pattern Recognition Research)

Litteratur

David A. Forsyth, Jean Pons Datamaskin syn. Modern Approach = Computer Vision: A Modern Approach. - M.: "Williams", 2004. - S. 928. - ISBN 0-13-085198-1
George Stockman, Linda Shapiro Datasyn = Datasyn. - M.: Binom. Kunnskapslaboratoriet, 2006. - S. 752. - ISBN 5947743841

A.L. Gorelik, V.A. Skripkin, Gjenkjenningsmetoder, M.: forskerskolen, 1989.
Sh.-K. Cheng, Designprinsipper for visuelle informasjonssystemer, M.: Mir, 1994.

Wikimedia Foundation. 2010 .

- i teknologi, en vitenskapelig og teknisk retning knyttet til utvikling av metoder og konstruksjon av systemer (inkludert på grunnlag av en datamaskin) for å etablere tilhørigheten til et bestemt objekt (objekt, prosess, fenomen, situasjon, signal) til en av før ...... Stor encyklopedisk ordbok

En av de nye regionene kybernetikk. Innholdet i teorien til R. om. er ekstrapolering av egenskapene til objekter (bilder) som tilhører flere klasser til objekter som er nær dem på en eller annen måte. Vanligvis, når du lærer en automat R. om. det er ... ... Geologisk leksikon

Engelsk anerkjennelse, bilde; tysk Gestalt alterkennung. En gren av matematisk kybernetikk som utvikler prinsipper og metoder for å klassifisere og identifisere objekter beskrevet av et begrenset sett med funksjoner som kjennetegner dem. Antinazi. Encyclopedia ... ... Encyclopedia of Sociology

Mønstergjenkjenning- metode for å studere komplekse objekter ved hjelp av en datamaskin; består i valg av funksjoner og utvikling av algoritmer og programmer som lar datamaskiner automatisk klassifisere objekter i henhold til disse funksjonene. For eksempel for å finne ut hvilken ... ... Økonomisk og matematisk ordbok

- (teknisk), en vitenskapelig og teknisk retning knyttet til utvikling av metoder og konstruksjon av systemer (inkludert datamaskinbaserte) for å fastslå tilhørigheten til et objekt (emne, prosess, fenomen, situasjon, signal) til en av før ... ... encyklopedisk ordbok

MØNSTERGJENKJENNING- en seksjon av matematisk kybernetikk som utvikler metoder for å klassifisere, samt identifisere objekter, fenomener, prosesser, signaler, situasjoner for alle disse objektene som kan beskrives av et begrenset sett av visse funksjoner eller egenskaper, ... ... Russisk sosiologisk leksikon

mønstergjenkjenning- 160 mønstergjenkjenning: Identifikasjon av skjemarepresentasjoner og konfigurasjoner ved hjelp av automatiske midler

Anmeldelse eksisterende metoder mønstergjenkjenning

L.P. Popova , OG OM. Datev

Evnen til å "gjenkjenne" regnes som hovedegenskapen til mennesker, som faktisk andre levende organismer. Mønstergjenkjenning er en del av kybernetikk som utvikler prinsipper og metoder for å klassifisere og identifisere objekter, fenomener, prosesser, signaler, situasjoner - alle de objektene som kan beskrives av et begrenset sett av noen funksjoner eller egenskaper som karakteriserer et objekt.

Et bilde er en beskrivelse av et objekt. Bilder har en karakteristisk egenskap, som manifesterer seg i det faktum at kjennskap til endelig antall fenomener fra samme sett gjør det mulig å gjenkjenne et vilkårlig stort antall av dets representanter.

Det er to hovedretninger i teorien om mønstergjenkjenning:

studiet av gjenkjennelseskreftene som besittes av mennesker og andre levende organismer;

utvikling av teori og metoder for å konstruere enheter designet for å løse individuelle problemer med mønstergjenkjenning i visse bruksområder.

Videre beskriver artikkelen problemene, prinsippene og metodene for å implementere mønstergjenkjenningssystemer knyttet til utviklingen av den andre retningen. Den andre delen av artikkelen diskuterer nevrale nettverksmetoder for mønstergjenkjenning, som kan tilskrives den første retningen for mønstergjenkjenningsteori.

Problemer med å bygge bildegjenkjenningssystemer

Oppgavene som oppstår ved konstruksjon av automatiske mønstergjenkjenningssystemer kan vanligvis klassifiseres i flere hovedområder. Den første av dem er relatert til presentasjonen av de opprinnelige dataene som er oppnådd som resultater av målinger for gjenstanden som skal gjenkjennes. følsomhetsproblem. Hver målte verdi er noen "karakteristikk for et bilde eller et objekt. Anta for eksempel at bildene er alfanumeriske tegn. I dette tilfellet kan en målenetthinne, lik den som er vist i fig. 1(a), brukes med hell. i sensoren Hvis netthinnen består av n-elementer, kan måleresultatene representeres som en målevektor eller en bildevektor ,

hvor hvert element xi tar for eksempel verdien 1 hvis bildet av symbolet går gjennom netthinnens i-te celle, og verdien 0 ellers.

Tenk på fig. 2(b). I dette tilfellet er bildene kontinuerlige funksjoner (av typen lydsignaler) av variabelen t. Hvis funksjonsverdiene måles ved diskrete punkter t1,t2, ..., tn, kan bildevektoren dannes ved å ta x1= f(t1),x2=f(t2),... , xn = f(tn).

Figur 1. Måling av netthinnen

Det andre problemet med mønstergjenkjenning er relatert til utvalget karakteristiske trekk eller egenskaper fra de oppnådde startdataene og redusere dimensjonen til bildevektorer. Dette problemet defineres ofte som et problem forbehandling og funksjonsvalg.

Funksjonene til bildeklassen er karakteristiske egenskaper, felles for alle bildene i denne klassen. De trekkene som kjennetegner forskjellene mellom enkeltklasser kan tolkes som interklassetrekk. Intraklassefunksjoner som er felles for alle klasser som vurderes, har ikke nyttig informasjon når det gjelder anerkjennelse og kan ikke tas i betraktning. Funksjonsvalg regnes som en av de viktige oppgaver knyttet til konstruksjon av gjenkjenningssystemer. Hvis måleresultatene gjør det mulig å oppnå et komplett sett med kjennetegn for alle klasser, vil den faktiske gjenkjenningen og klassifiseringen av mønstre ikke forårsake noen spesielle vanskeligheter. Automatisk gjenkjenning vil da bli redusert til en enkel matchingsprosess eller prosedyrer som tabelloppslag. I de fleste praktiske gjenkjennelsesproblemer er imidlertid definisjonen komplett sett kjennetegn viser seg å være ekstremt vanskelig, om ikke umulig i det hele tatt. Fra de originale dataene er det vanligvis mulig å trekke ut noen av kjennetegnene og bruke dem til å forenkle prosessen med automatisk mønstergjenkjenning. Spesielt kan dimensjonen til målevektorene reduseres ved hjelp av transformasjoner som minimerer tap av informasjon.

Det tredje problemet knyttet til konstruksjonen av mønstergjenkjenningssystemer er å finne de optimale beslutningsprosedyrene som er nødvendige for identifikasjon og klassifisering. Etter at dataene som er samlet inn om mønstrene som skal gjenkjennes er representert av punkter eller målevektorer i mønsterrommet, la maskinen finne ut hvilken klasse av mønstre disse dataene tilsvarer. La maskinen være utformet for å skille mellom M-klasser, betegnet med w1, w2, ... ..., wm. I dette tilfellet kan bilderommet anses å bestå av M regioner, som hver inneholder punkter som tilsvarer bilder fra samme klasse. I dette tilfellet kan gjenkjenningsproblemet betraktes som å konstruere grensene for beslutningsregionene som skiller M-klasser basert på de registrerte målevektorene. La disse grensene være definert, for eksempel ved beslutningsfunksjoner d1(х),d2(x),..., dm(х). Disse funksjonene, også kalt diskriminantfunksjoner, er skalære funksjoner og funksjoner med én verdi av bildet av x. Hvis di (x) > dj (x), så tilhører bildet av x klassen w1. Med andre ord, hvis i-th avgjørende funksjon di(x) har høyeste verdi, så er en meningsfull illustrasjon av et slikt automatisk klassifiseringsskjema basert på implementeringen av beslutningsprosessen vist i fig. 2 (på ordningen "GR" - generatoren av avgjørende funksjoner).

Figur 2. Skjema for automatisk klassifisering.

Beslutningsfunksjoner kan oppnås på en rekke måter. I de tilfellene hvor fullstendig a priori informasjon er tilgjengelig om de gjenkjennelige mønstrene, kan beslutningsfunksjonene bestemmes nøyaktig på grunnlag av denne informasjonen. Dersom det kun foreligger kvalitativ informasjon om mønstrene, kan det gjøres rimelige antakelser om formen på beslutningsfunksjonene. I sistnevnte tilfelle kan grensene for beslutningsregionene avvike betydelig fra de sanne, og derfor er det nødvendig å lage et system som er i stand til å komme frem til et tilfredsstillende resultat gjennom en rekke suksessive justeringer.

Objekter (bilder) som skal gjenkjennes og klassifiseres ved hjelp av et automatisk mønstergjenkjenningssystem må ha et sett med målbare egenskaper. Når resultatene av de tilsvarende målingene for en hel gruppe bilder er like, anses det at disse objektene tilhører samme klasse. Formålet med mønstergjenkjenningssystemet er å bestemme, på grunnlag av den innsamlede informasjonen, en klasse av objekter med egenskaper som ligner de som måles for gjenkjennelige objekter. Korrektheten av gjenkjenningen avhenger av mengden kjennetegnende informasjon som finnes i de målte egenskapene, og effektiviteten av å bruke denne informasjonen.

Grunnleggende metoder for implementering av mønstergjenkjenningssystemer

Mønstergjenkjenning er oppgaven med å konstruere og bruke formelle operasjoner på numeriske eller symbolske representasjoner av objekter i den virkelige eller ideelle verden, hvis resultater reflekterer ekvivalensforholdet mellom disse objektene. Ekvivalensrelasjoner uttrykker tilhørigheten til de evaluerte objektene til noen klasser, betraktet som uavhengige semantiske enheter.

Ved konstruksjon av gjenkjennelsesalgoritmer kan ekvivalensklasser settes av en forsker som bruker sine egne meningsfulle ideer eller bruker ekstern tilleggsinformasjon om likheten og forskjellen mellom objekter i sammenheng med problemet som skal løses. Da snakker man om «å skjelne med læreren». Ellers, dvs. når et automatisert system løser et klassifiseringsproblem uten å involvere ekstern opplæringsinformasjon, snakker man om automatisk klassifisering eller "uovervåket anerkjennelse". De fleste mønstergjenkjenningsalgoritmer krever involvering av svært betydelig datakraft, som bare kan leveres av høyytelses datateknologi.

Ulike forfattere (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 og andre) gir en annen typologi av metoder for mønstergjenkjenning. Noen forfattere skiller mellom parametrisk, ikke-parametrisk og heuristiske metoder, andre - skille grupper av metoder basert på historisk etablerte skoler og trender på dette området.

Samtidig tar de velkjente typologiene ikke hensyn til en veldig viktig egenskap, som gjenspeiler spesifikasjonene ved måten å presentere kunnskap om fagområde ved hjelp av en formell mønstergjenkjenningsalgoritme. D.A. Pospelov identifiserer to hovedmåter for å representere kunnskap:

Intensjonell representasjon - i form av et diagram over forhold mellom attributter (funksjoner).

Utvidende representasjon - ved hjelp av konkrete fakta(objekter, eksempler).

Det skal bemerkes at eksistensen av disse to gruppene av gjenkjennelsesmetoder: de som opererer med funksjoner og de som opererer med objekter, er dypt naturlig. Fra dette synspunktet gjør ingen av disse metodene, tatt adskilt fra den andre, det mulig å danne en adekvat refleksjon av fagområdet. Mellom disse metodene er det en relasjon av komplementaritet i betydningen N. Bohr, derfor bør lovende gjenkjenningssystemer gi implementering av begge disse metodene, og ikke bare en av dem.

Klassifiseringen av anerkjennelsesmetoder foreslått av D.A. Pospelov er derfor basert på de grunnleggende lovene som ligger til grunn for den menneskelige måten å erkjenne på generelt, noe som setter den i en veldig spesiell (privilegert) posisjon sammenlignet med andre klassifikasjoner, som på denne bakgrunn ser ut. mer lett og kunstig.

Intensjonelle metoder

Et særtrekk ved intensjonelle metoder er at de bruker ulike egenskaper ved funksjoner og deres relasjoner som elementer av operasjoner i konstruksjon og anvendelse av mønstergjenkjenningsalgoritmer. Slike elementer kan være individuelle verdier eller intervaller av funksjonsverdier, gjennomsnittsverdier og varianser, funksjonsforholdsmatriser, etc., som handlinger utføres på, uttrykt i en analytisk eller konstruktiv form. Samtidig regnes ikke objektene i disse metodene som integrerte informasjonsenheter, men fungerer som indikatorer for å vurdere samspillet og oppførselen til deres attributter.

Gruppen av intensjonelle mønstergjenkjenningsmetoder er omfattende, og inndelingen i underklasser er noe vilkårlig:

– metoder basert på estimater av fordelingstetthetene til funksjonsverdier

– metoder basert på antakelser om klassen av beslutningsfunksjoner

– logiske metoder

– språklige (strukturelle) metoder.

Metoder basert på estimater av fordelingstetthetene til funksjonsverdier. Disse metodene for mønstergjenkjenning er lånt fra den klassiske teorien om statistiske beslutninger, der studieobjektene betraktes som implementeringer av en flerdimensjonal tilfeldig variabel fordelt i funksjonsrommet i henhold til noen lov. De er basert på et Bayesiansk beslutningsskjema som appellerer til a priori sannsynligheter for objekter som tilhører en bestemt gjenkjennelig klasse og betingede distribusjonstettheter av funksjonsvektorverdier. Disse metodene er redusert til å bestemme sannsynlighetsforholdet i forskjellige områder av det flerdimensjonale funksjonsrommet.

Gruppen av metoder basert på estimering av fordelingstetthetene til funksjonsverdier er direkte relatert til metodene for diskriminant analyse. Den Bayesianske tilnærmingen til beslutningstaking er en av de mest utviklede i moderne statistikk, de såkalte parametriske metodene, som det analytiske uttrykket for distribusjonsloven anses å være kjent for (i dette tilfellet normal lov) og bare et lite antall parametere må estimeres (gjennomsnittlige vektorer og kovariansmatriser).

Denne gruppen inkluderer også en metode for å beregne likelihood ratio for uavhengige funksjoner. Denne metoden, med unntak av antagelsen om trekks uavhengighet (som i realiteten nesten aldri oppfylles), krever ikke kunnskap om fordelingslovens funksjonelle form. Det kan tilskrives ikke-parametriske metoder.

Andre ikke-parametriske metoder, brukt når formen på fordelingstetthetskurven er ukjent og det ikke kan gjøres noen antagelser om dens natur i det hele tatt, inntar en spesiell posisjon. Disse inkluderer den velkjente metoden for flerdimensjonale histogrammer, metoden "k-nærmeste naboer", den euklidiske avstandsmetoden, metoden for potensielle funksjoner, etc., hvis generalisering er metoden kalt "Parzen-estimater". Disse metodene opererer formelt med objekter som integrerte strukturer, men avhengig av type gjenkjenningsoppgave kan de virke både i intensjonelle og ekstensjonelle hypostaser.

Ikke-parametriske metoder analyserer det relative antallet objekter som faller inn i de gitte flerdimensjonale volumene og bruker ulike avstandsfunksjoner mellom objektene i treningsprøven og de gjenkjente objektene. Til kvantitative egenskaper, når antallet er mye mindre enn prøvestørrelsen, spiller operasjoner med objekter en mellomrolle i å estimere lokale distribusjonstettheter betingede sannsynligheter og objekter bærer ikke den semantiske belastningen av uavhengige informasjonsenheter. Samtidig, når antallet funksjoner er tilsvarende eller flere tall av objektene som studeres, og trekkene er av kvalitativ eller dikotom karakter, så kan det ikke være snakk om noen lokale estimater avne. I dette tilfellet betraktes objektene i disse ikke-parametriske metodene som uavhengige informasjonsenheter (holistiske empiriske fakta), og disse metodene får betydningen av vurderinger av likheten og forskjellen til objektene som studeres.

Dermed gir de samme teknologiske operasjonene til ikke-parametriske metoder, avhengig av forholdene til problemet, mening enten lokale estimater av satil funksjonsverdier, eller estimater av likheten og forskjellen til objekter.

I sammenheng med intensjonell representasjon av kunnskap, betraktes den første siden av ikke-parametriske metoder her, som estimater avr. Mange forfattere bemerker at ikke-parametriske metoder som Parzen-estimeringer fungerer bra i praksis. De største vanskelighetene med å bruke disse metodene er behovet for å huske hele treningsutvalget for å beregne estimater av lokale sog høy følsomhet for ikke-representativiteten til treningsutvalget.

Metoder basert på antakelser om klassen av beslutningsfunksjoner. I denne gruppen av metoder anses den generelle formen for beslutningsfunksjonen som kjent og dens kvalitet funksjonell er gitt. Basert på denne funksjonen søkes den beste tilnærmingen til beslutningsfunksjonen for treningssekvensen. Det vanligste er representasjoner av beslutningsfunksjoner i form av lineære og generaliserte ikke-lineære polynomer. Kvalitetsfunksjonen til beslutningsregelen er vanligvis forbundet med klassifiseringsfeilen.

Hovedfordelen med metoder basert på antakelser om klassen av beslutningsfunksjoner er klarheten i den matematiske formuleringen av gjenkjennelsesproblemet som et problem med å finne et ekstremum. Løsningen på dette problemet oppnås ofte ved å bruke en slags gradientalgoritmer. Variasjonen av metoder for denne gruppen forklares av det brede spekteret av brukte kvalitetsfunksjoner for beslutningsregeler og ekstremumsøkealgoritmer. En generalisering av de betraktede algoritmene, som spesielt inkluderer Newtons algoritme, perceptron-type algoritmer, etc., er metoden for stokastisk tilnærming. I motsetning til parametriske gjenkjenningsmetoder, avhenger ikke suksessen til denne gruppen av metoder så mye av misforholdet mellom teoretiske ideer om lovene for distribusjon av objekter i funksjonsrommet med empirisk virkelighet. Alle operasjoner er underlagt en Hoved mål- finne det ytterste av kvalitetsfunksjonen til beslutningsregelen. Samtidig kan resultatene av de parametriske og vurderte metodene være like. Som vist ovenfor, parametriske metoder for saken normalfordelinger objekter i forskjellige klasser med like kovariansmatriser fører til lineære beslutningsfunksjoner. Vi legger også merke til at algoritmene for å velge informative funksjoner i lineære diagnostiske modeller kan tolkes som spesielle varianter av gradientalgoritmer for å søke etter et ekstremum.

Muligheter for gradientalgoritmer for ekstremumsøk, spesielt i gruppen lineære vedtaksregler, har blitt ganske godt studert. Konvergensen til disse algoritmene har blitt bevist bare for tilfellet når de gjenkjennelige klassene av objekter vises i funksjonsrommet av kompakte geometriske strukturer. Ønsket om å oppnå tilstrekkelig kvalitet på beslutningsregelen kan imidlertid ofte tilfredsstilles ved hjelp av algoritmer som ikke har et strengt matematisk bevis på konvergensen av løsningen til det globale ekstremumet.

Disse algoritmene inkluderer stor gruppe heuristiske programmeringsprosedyrer som representerer retningen for evolusjonær modellering. Evolusjonsmodellering er en bionisk metode lånt fra naturen. Den er basert på bruken av kjente evolusjonsmekanismer for å erstatte prosessen med meningsfull modellering av et komplekst objekt med fenomenologisk modellering av dets evolusjon.

En velkjent representant for evolusjonær modellering i mønstergjenkjenning er metoden for grupperegnskap for argumenter (MGUA). GMDH er basert på prinsippet om selvorganisering, og GMDH-algoritmene gjengir ordningen med masseutvelgelse. I GMDH-algoritmer syntetiseres og velges medlemmer av et generalisert polynom på en spesiell måte, som ofte kalles Kolmogorov-Gabor-polynomet. Denne syntesen og seleksjonen utføres med økende kompleksitet, og det er umulig å forutsi på forhånd hvilken endelig form det generaliserte polynomet vil ha. For det første vurderes vanligvis enkle parvise kombinasjoner av innledende funksjoner, hvorfra ligningene til de avgjørende funksjonene er sammensatt, som regel ikke høyere enn andre orden. Hver ligning analyseres som en uavhengig beslutningsfunksjon, og verdiene til parametrene til de sammensatte ligningene finnes på en eller annen måte fra treningsutvalget. Deretter, fra det resulterende settet med beslutningsfunksjoner, velges en del av de beste på en eller annen måte. Kvaliteten på individuelle beslutningsfunksjoner kontrolleres på en kontroll (test) prøve, som noen ganger kalles prinsippet om ekstern addisjon. De utvalgte delbeslutningsfunksjonene betraktes nedenfor som mellomvariabler som tjener som startargumenter for en lignende syntese av nye beslutningsfunksjoner osv. Prosessen med en slik hierarkisk syntese fortsetter til ytterpunktet av beslutningsfunksjonens kvalitetskriterie er nådd, noe som i praksis manifesterer seg i forringelsen av denne kvaliteten når man prøver å ytterligere øke rekkefølgen til medlemmene av polynomet i forhold til de opprinnelige trekkene.

Selvorganiseringsprinsippet som ligger til grunn for GMDH kalles heuristisk selvorganisering, siden hele prosessen er basert på introduksjon av eksterne tillegg valgt heuristisk. Resultatet av avgjørelsen kan i betydelig grad avhenge av disse heuristikkene. Den resulterende diagnostiske modellen avhenger av hvordan objektene er delt inn i trenings- og testprøver, hvordan bestemmes, hvor mange variabler som hoppes over i neste utvalgsrad osv.

Disse funksjonene til GMDH-algoritmer er også karakteristiske for andre tilnærminger til evolusjonær modellering. Men vi bemerker her enda et aspekt av metodene som vurderes. Dette er innholdets essens. Ved å bruke metoder basert på antakelser om klassen av beslutningsfunksjoner (evolusjonær og gradient), kan man bygge diagnostiske modeller høy kompleksitet og få praktisk talt akseptable resultater. Samtidig er oppnåelsen av praktiske mål i dette tilfellet ikke ledsaget av utvinning av ny kunnskap om naturen til gjenkjennelige objekter. Muligheten for å trekke ut denne kunnskapen, spesielt kunnskap om mekanismene for interaksjon av attributter (funksjoner), er fundamentalt begrenset her av den gitte strukturen til slik interaksjon, festet i den valgte formen for avgjørende funksjoner. Derfor er det maksimale som kan sies etter å ha konstruert en bestemt diagnostisk modell å liste kombinasjonene av funksjoner og funksjonene i seg selv som er inkludert i den resulterende modellen. Men betydningen av kombinasjoner som reflekterer arten og strukturen til fordelingen av objektene som studeres, forblir ofte uoppdaget innenfor rammen av denne tilnærmingen.

boolske metoder. Logiske metoder for mønstergjenkjenning er basert på apparatet til logisk algebra og tillater å operere med informasjon som ikke bare finnes i individuelle funksjoner, men også i kombinasjoner av funksjonsverdier. I disse metodene betraktes verdiene til ethvert attributt som elementære hendelser.

I selve generelt syn logiske metoder kan karakteriseres som en slags søk etter logiske mønstre i treningsutvalget og dannelsen av et visst system med logiske beslutningsregler (for eksempel i form av konjunksjoner elementære hendelser), som hver har sin egen vekt. Gruppe logiske metoder er mangfoldig og inkluderer metoder med varierende kompleksitet og analysedybde. For dikotome (boolske) funksjoner er de såkalte trelignende klassifikatorene, blindveistestmetoden, Kora-algoritmen og andre populære. Mer komplekse metoder er basert på formalisering induktive metoder D.S. Mill. Formalisering utføres ved å konstruere en kvasi-aksiomatisk teori og er basert på multisortert flerverdilogikk med kvantifiserere over tupler med variabel lengde.

Kora-algoritmen, som andre logiske metoder for mønstergjenkjenning, er ganske arbeidskrevende, siden en fullstendig oppregning er nødvendig når du velger konjunksjoner. Ved bruk av logiske metoder stilles det derfor høye krav til effektiv organisasjon beregningsprosess, og disse metodene fungerer godt for relativt små dimensjoner av funksjonsområdet og bare på kraftige datamaskiner.

Språklige (syntaktiske eller strukturelle) metoder. Språklige metoder for mønstergjenkjenning er basert på bruk av spesielle grammatikker som genererer språk, ved hjelp av hvilke et sett med egenskaper til gjenkjennelige objekter kan beskrives. Grammatikk refererer til reglene for å konstruere objekter fra disse ikke-avledede elementene.

Hvis beskrivelsen av bilder er laget ved hjelp av ikke-avledede elementer (underbilder) og deres relasjoner, brukes en språklig eller syntaktisk tilnærming for å bygge automatiske gjenkjenningssystemer ved å bruke prinsippet om fellesegenskaper. Et bilde kan beskrives ved hjelp av en hierarkisk struktur av underbilder som ligner på den syntaktiske strukturen til et språk. Denne omstendigheten gjør det mulig å anvende teorien formelle språk. Det antas at bilders grammatikk inneholder endelige sett med elementer kalt variabler, ikke-avledede elementer og substitusjonsregler. Arten av substitusjonsreglene bestemmer typen grammatikk. Blant de mest studerte grammatikkene er vanlige, kontekstfrie og grammatikker av direkte bestanddeler. Nøkkelpunktene i denne tilnærmingen er valget av ikke-avledede elementer i bildet, foreningen av disse elementene og relasjonene som forbinder dem med bilders grammatikk, og til slutt implementeringen av prosessene for analyse og gjenkjennelse i de tilsvarende. Språk. Denne tilnærmingen er spesielt nyttig når du arbeider med bilder som enten ikke kan beskrives med numeriske målinger, eller som er så komplekse at deres lokale egenskaper ikke kan identifiseres og man må referere til objekters globale egenskaper.

For eksempel har E.A. Butakov, V.I. Ostrovsky, I.L. Fadeev foreslår følgende systemstruktur for bildebehandling (fig. 3), ved bruk av en språklig tilnærming, der hver av funksjonsblokkene er et programvare- (mikroprogram) kompleks (modul) som implementerer de tilsvarende funksjonene.

Figur 3 Strukturopplegg gjenkjenningsenhet

Forsøk på å anvende metodene for matematisk lingvistikk på problemet med bildeanalyse fører til behovet for å løse en rekke problemer knyttet til kartlegging av en todimensjonal bildestruktur på endimensjonale kjeder av et formelt språk.

Utvidende metoder

I metodene til denne gruppen, i motsetning til intensjonsretningen, gis hvert studert objekt en uavhengig diagnostisk verdi i større eller mindre grad. I kjernen ligger disse metodene nær den kliniske tilnærmingen, som vurderer mennesker ikke som en kjede av objekter rangert i henhold til en eller annen indikator, men som integrerte systemer, som hver er individuelle og har en spesiell diagnostisk verdi. En slik forsiktig holdning til studieobjektene tillater ikke at man utelukker eller mister informasjon om hvert enkelt objekt, som oppstår når man bruker metodene for intensjonell retning, ved å bruke objekter kun for å oppdage og fikse oppførselsmønstrene til deres attributter.

Hovedoperasjonene i mønstergjenkjenning ved å bruke de diskuterte metodene er operasjonene for å bestemme likheten og forskjellen mellom objekter. Objekter i den angitte gruppen av metoder spiller rollen som diagnostiske presedenser. Samtidig, avhengig av betingelsene for en bestemt oppgave, kan rollen til en individuell presedens variere innenfor de videste grensene: fra den viktigste og definerende til svært indirekte deltakelse i anerkjennelsesprosessen. På sin side kan forholdene for problemet kreve deltakelse av et annet antall diagnostiske presedenser for en vellykket løsning: fra én i hver gjenkjennelig klasse til full prøvestørrelse, samt forskjellige måter beregning av mål for likhet og forskjell på objekter. Disse kravene forklarer den videre inndelingen av utvidelsesmetoder i underklasser:

prototype sammenligning metode;

k-nærmeste nabo metode;

lag av beslutningsregler.

Prototype sammenligningsmetode. Dette er den enkleste utvidelsesgjenkjenningsmetoden. Den brukes for eksempel når de gjenkjente klassene vises i funksjonsområdet i kompakte geometriske grupperinger. I dette tilfellet velges vanligvis midten av den geometriske grupperingen av klassen (eller objektet nærmest midten) som prototypepunkt.

For å klassifisere et ukjent objekt, blir prototypen nærmest funnet, og objektet tilhører samme klasse som denne prototypen. Det dannes åpenbart ingen generaliserte klassebilder i denne metoden.

Ulike typer avstander kan brukes som mål på nærhet. Ofte for dikotome trekk brukes Hamming-avstanden, som i dette tilfellet er lik kvadratet på den euklidiske avstanden. I dette tilfellet tilsvarer beslutningsregelen for klassifisering av objekter en lineær beslutningsfunksjon.

Dette faktum bør spesielt bemerkes. Den demonstrerer tydelig sammenhengen mellom prototype og veiledende representasjon av informasjon om datastrukturen. Ved å bruke representasjonen ovenfor, for eksempel, kan enhver tradisjonell måleskala, som er en lineær funksjon av verdiene til dikotome trekk, betraktes som en hypotetisk diagnostisk prototype. På sin side, hvis analysen av den romlige strukturen til de anerkjente klassene lar oss konkludere med at de er geometrisk kompakte, er det nok å erstatte hver av disse klassene med en prototype, som faktisk tilsvarer en lineær diagnostisk modell.

I praksis er situasjonen selvsagt ofte annerledes enn det idealiserte eksemplet som er beskrevet. En forsker som har til hensikt å bruke en gjenkjennelsesmetode basert på sammenligning med prototypene til diagnostiske klasser, møter vanskelige problemer. Dette er først og fremst valget av et nærhetsmål (metrisk), som kan endre den romlige konfigurasjonen av fordelingen av objekter betydelig. Og for det andre selvstendig problem er analysen av flerdimensjonale strukturer av eksperimentelle data. Begge disse problemene er spesielt akutte for forskeren under forhold med høy dimensjon av funksjonsrommet, noe som er typisk for reelle problemer.

Metode til k-nærmeste naboer. K-nærmeste nabo-metoden for å løse diskriminerende analyseproblemer ble først foreslått tilbake i 1952. Det er som følger.

Ved klassifisering av et ukjent objekt, finnes et gitt antall (k) av andre objekter geometrisk nærmest det i funksjonsrommet (nærmeste naboer) med allerede kjent tilhørighet til gjenkjennelige klasser. Beslutningen om å tilordne et ukjent objekt til en bestemt diagnoseklasse gjøres ved å analysere informasjon om dette kjente medlemskapet til de nærmeste naboene, for eksempel ved å bruke en enkel stemmetelling.

Opprinnelig ble k-nearest neighbor-metoden vurdert som en ikke-parametrisk metode for å estimere sannsynlighetsforholdet. For denne metoden oppnås teoretiske estimater av dens effektivitet sammenlignet med den optimale Bayesianske klassifikatoren. Det er bevist at de asymptotiske feilsannsynlighetene for k-nærmeste nabometoden overskrider feilene i Bayes-regelen med ikke mer enn to ganger.

Som nevnt ovenfor, i reelle oppgaver ofte er det nødvendig å operere med objekter som er beskrevet av et stort antall kvalitative (dikotome) trekk. Samtidig er dimensjonen til funksjonsrommet i samsvar med eller overstiger volumet til prøven som studeres. Under slike forhold er det praktisk å tolke hvert objekt i treningsprøven som en separat lineær klassifikator. Da er denne eller den diagnostiske klassen ikke representert av én prototype, men av et sett med lineære klassifikatorer. Den kombinerte interaksjonen mellom lineære klassifikatorer resulterer i en stykkevis lineær overflate som skiller de gjenkjennelige klassene i funksjonsrommet. Type skilleflate, som består av biter av hyperplan, kan varieres og avhenger av relativ posisjon klassifiserte samlinger.

En annen tolkning av klassifiseringsmekanismer for k-nærmeste nabo kan også brukes. Den er basert på ideen om eksistensen av noen latente variabler, abstrakte eller relatert til en eller annen transformasjon med det originale funksjonsrommet. Hvis i rommet til latente variabler parvise avstander mellom objekter er de samme som i rommet med innledende funksjoner, og antallet av disse variablene er betydelig mindre enn antall objekter, så kan tolkningen av k-nærmeste naboer-metoden vurderes fra synspunktet om å sammenligne ikke-parametriske estimater av fordelingstetthetene til betingede sannsynligheter. Konseptet med latente variabler som presenteres her, er nært til begrepet ekte dimensjonalitet og andre representasjoner som brukes i forskjelliger.

Når man bruker metoden k-nærmeste naboer for mønstergjenkjenning, må forskeren løse det vanskelige problemet med å velge en metrikk for å bestemme nærheten til diagnostiserte objekter. Dette problemet under forholdene med høy dimensjonalitet av funksjonsrommet er ekstremt forverret på grunn av den tilstrekkelige arbeidsintensiteten. denne metoden, som blir betydelig selv for datamaskiner med høy ytelse. Derfor, her, så vel som i metoden for sammenligning med prototypen, er det nødvendig å bestemme seg kreativ oppgave analyse av den flerdimensjonale strukturen til eksperimentelle data for å minimere antallet objekter som representerer diagnostiske klasser.

Algoritmer for å beregne karakterer (stemmegivning). Prinsippet for driften av evalueringsalgoritmene (ABO) er å beregne prioriteten (likhetspoeng) som karakteriserer "nærheten" til de gjenkjente objektene og referanseobjektene i henhold til systemet med funksjonsensembler, som er et system av undergrupper av et gitt sett av funksjoner.

I motsetning til alle tidligere vurderte metoder, opererer algoritmer for beregning av estimater med objektbeskrivelser på en fundamentalt ny måte. For disse algoritmene eksisterer objekter samtidig i svært forskjellige underrom av funksjonsrommet. ABO-klassen bringer ideen om å bruke funksjoner til sin logiske konklusjon: siden det ikke alltid er kjent hvilke kombinasjoner av funksjoner som er de mest informative, i ABO beregnes graden av likhet mellom objekter ved å sammenligne alle mulige eller visse kombinasjoner av funksjoner inkludert i beskrivelsene av objekter.

Lag av beslutningsregler. Vedtaksregelen bruker en to-nivå anerkjennelsesordning. På det første nivået fungerer private gjenkjennelsesalgoritmer, hvis resultater kombineres på andre nivå i synteseblokken. De vanligste metodene for en slik kombinasjon er basert på tildeling av kompetanseområder for en bestemt algoritme. Den enkleste måtenå finne kompetanseområder består i a priori oppdeling av funksjonsrommet basert på faglige betraktninger av en bestemt vitenskap (for eksempel stratifisering av utvalget i henhold til noen funksjon). Deretter, for hvert av de valgte områdene, bygges en egen gjenkjennelsesalgoritme. En annen metode er basert på bruken av formell analyse for å bestemme lokale områder av funksjonsrommet som nabolag med gjenkjennelige objekter som har bevist suksessen til en bestemt gjenkjennelsesalgoritme.

Mest generell tilnærming til konstruksjonen av synteseblokken, vurderer de resulterende indikatorene for spesielle algoritmer som innledende funksjoner for å konstruere en ny generalisert beslutningsregel. I dette tilfellet kan alle de ovennevnte metodene for intensjonelle og ekstensjonelle retninger i mønstergjenkjenning brukes. Effektive for å løse problemet med å lage et sett med beslutningsregler er logiske algoritmer av typen "Kora" og algoritmer for beregning av estimater (ABO), som er grunnlaget for den såkalte algebraiske tilnærmingen, som gir forskning og en konstruktiv beskrivelse av gjenkjenningsalgoritmer, som alle eksisterende typer algoritmer passer innenfor.

Nevrale nettverksmetoder

Nevrale nettverksmetoder er metoder basert på applikasjonen forskjellige typer nevrale nettverk (NN). De viktigste bruksområdene for ulike NN-er for mønster- og bildegjenkjenning:

applikasjon for å trekke ut nøkkelegenskaper eller funksjoner til gitte bilder,

klassifisering av selve bildene eller egenskapene som allerede er hentet fra dem (i det første tilfellet skjer utvinningen av nøkkelegenskaper implisitt i nettverket),

løsning av optimaliseringsproblemer.

Flerlags nevrale nettverk. Arkitekturen til et flerlags nevralt nettverk (MNN) består av sekvensielt koblede lag, der nevronen til hvert lag er koblet til alle nevronene i det forrige laget med dets innganger, og utgangene til det neste.

Den enkleste anvendelsen av et enkeltlags NN (kalt autoassosiativt minne) er å trene nettverket til å rekonstruere feedbildene. Ved å mate et testbilde til inngangen og beregne kvaliteten på det rekonstruerte bildet, kan man estimere hvor godt nettverket gjenkjente inngangsbildet. De positive egenskapene til denne metoden er at nettverket kan gjenopprette forvrengte og støyende bilder, men den er ikke egnet for mer seriøse formål.

MNN brukes også for direkte klassifisering av bilder - inngangen er enten selve bildet i en eller annen form, eller et sett med tidligere ekstraherte nøkkelegenskaper til bildet, ved utgangen indikerer nevronet med maksimal aktivitet tilhørighet til den anerkjente klassen (fig. 4). Hvis denne aktiviteten er under en viss terskel, anses det at det innsendte bildet ikke tilhører noen av de kjente klassene. Læringsprosessen etablerer korrespondanse mellom inngangsbildene med tilhørighet til en bestemt klasse. Dette kalles veiledet læring. Denne tilnærmingen er bra for tilgangskontrolloppgaver for en liten gruppe mennesker. Denne tilnærmingen gir en direkte sammenligning av selve bildene av nettverket, men med en økning i antall klasser øker treningstiden og nettverksdriften eksponentielt. Derfor, for oppgaver som å søke etter en lignende person i en stor database, krever det å trekke ut et kompakt sett med nøkkelfunksjoner å søke fra.

En klassifiseringstilnærming som bruker frekvenskarakteristikkene til hele bildet er beskrevet i . En enkeltlags NS basert på flerverdiede nevroner ble brukt.

B viser bruken av NN for bildeklassifisering, når nettverksinngangen mottar resultatene av bildedekomponering ved metoden for hovedkomponenter.

I den klassiske MNS er de mellomlags nevrale forbindelsene fullstendig forbundet, og bildet er representert som en endimensjonal vektor, selv om det er todimensjonalt. Arkitekturen til det konvolusjonelle nevrale nettverket tar sikte på å overvinne disse manglene. Den brukte lokale reseptorfelt (som gir lokal todimensjonal tilkobling av nevroner), generelle vekter (som gir deteksjon av noen funksjoner hvor som helst i bildet), og hierarkisk organisering med romlig subsampling (romlig subsampling). Convolutional NN (CNN) gir delvis motstand mot skalaendringer, forskyvninger, rotasjoner, forvrengninger.

MNS brukes også til å oppdage objekter av en bestemt type. I tillegg til at en hvilken som helst trent MNS til en viss grad kan bestemme tilhørigheten av bilder til "sine" klasser, kan den være spesialtrent for pålitelig å oppdage visse klasser. I dette tilfellet vil utgangsklassene være klasser som tilhører og ikke tilhører den gitte bildetypen. En nevrale nettverksdetektor ble brukt til å oppdage ansiktsbildet i inngangsbildet. Bildet ble skannet med et vindu på 20x20 piksler, som ble matet til inngangen til nettverket, som avgjør om det gitte området tilhører klassen av ansikter. Opplæringen ble gjennomført vha gode eksempler (ulike bilder ansikter) og negative (bilder som ikke er ansikter). For å forbedre påliteligheten til deteksjonen ble det brukt en gruppe NN-er trent med ulik startvekt, som et resultat av at NN-ene gjorde feil på forskjellige måter, og siste avgjørelse vedtatt av hele lagets stemme.

Figur 5. Hovedkomponenter (egenflater) og dekomponering av bildet til hovedkomponenter

NN brukes også til å trekke ut nøkkelkarakteristikkene til bildet, som deretter brukes til etterfølgende klassifisering. I er en metode for nevrale nettverksimplementering av hovedkomponentanalysemetoden vist. Essensen av hovedkomponentanalysemetoden er å oppnå de maksimalt dekorelle koeffisientene som karakteriserer inngangsmønstrene. Disse koeffisientene kalles hovedkomponenter og brukes til statistisk bildekomprimering, der et lite antall koeffisienter brukes til å representere hele bildet. Et NN med ett skjult lag som inneholder N nevroner (som er mye mindre enn bildedimensjonen), trent ved metoden for feiltilbakepropagering for å gjenopprette inngangsbildet ved utgangen, genererer koeffisientene til de første N hovedkomponentene ved utgangen av skjulte nevroner, som brukes til sammenligning. Vanligvis brukes 10 til 200 hovedkomponenter. Når komponenttallet øker, reduseres representativiteten betraktelig, og det gir ingen mening å bruke komponenter med store tall. Ved bruk av ikke-lineære aktiveringsfunksjoner av nevrale elementer, er en ikke-lineær dekomponering til hovedkomponenter mulig. Ikke-linearitet lar deg reflektere variasjonene i inndata mer nøyaktig. Ved å bruke hovedkomponentanalyse på dekomponering av ansiktsbilder, får vi hovedkomponentene, kalt riktige ansikter, som også har nyttig eiendom- det er komponenter som hovedsakelig gjenspeiler slike essensielle egenskaper ved en person som kjønn, rase, følelser. Når de gjenopprettes, ser komponentene ut som et ansikt, hvor førstnevnte reflekterer mest generell form ansikter, sistnevnte - ulike små forskjeller mellom ansikter (fig. 5). Denne metoden er godt anvendelig for å søke lignende ansiktsbilder i store databaser. Muligheten for ytterligere reduksjon av dimensjonen til hovedkomponenter ved hjelp av NS vises også. Ved å evaluere kvaliteten på rekonstruksjonen av inngangsbildet kan man svært nøyaktig fastslå om det tilhører klassen ansikter.

Nevrale nettverk høy orden. Høyordens nevrale nettverk (HNN) skiller seg fra MNN ved at de bare har ett lag, men inngangene til nevroner mottar også termer av høy orden, som er produktet av to eller flere komponenter i inngangsvektoren. Slike nettverk kan også danne komplekse skilleflater.

Hopfield nevrale nettverk. Hopfield NN (HSH) er enkeltlags og fullstendig tilkoblet (det er ingen nevronforbindelser til seg selv), utgangene er koblet til innganger. I motsetning til MNS er NSH avslappende, dvs. blir satt til den opprinnelige tilstanden, fungerer den til den når en stabil tilstand, som vil være dens utgangsverdi. Å finne det globale minimum i forhold til optimaliseringsproblemer bruke stokastiske modifikasjoner av NSH.

Bruken av NSH som assosiativ hukommelse lar deg gjenopprette bildene som nettverket er opplært til nøyaktig når et forvrengt bilde mates til inngangen. I dette tilfellet vil nettverket "huske" det nærmeste (i betydningen lokalt minimum energi) bildet, og gjenkjenner det dermed. Slik funksjon kan også betraktes som en sekvensiell anvendelse av det autoassosiative minnet beskrevet ovenfor. I motsetning til autoassosiativt minne, vil NSH gjenopprette bildet perfekt nøyaktig. For å unngå interferensminima og øke nettverkskapasiteten, bruk ulike metoder.

Kohonen selvorganiserende nevrale nettverk. Kohonen selvorganiserende nevrale nettverk (SNNCs) gir topologisk rekkefølge av inngangsbilderommet. De tillater topologisk kontinuerlig kartlegging av inngangen n-dimensjonalt rom til utgangen m-dimensjonal, m<

Cognitron. Kognitronen i sin arkitektur ligner strukturen til den visuelle cortex, den har en hierarkisk flerlagsorganisasjon, der nevroner mellom lag bare er lokalt koblet. Opplært av konkurrerende læring (uten lærer). Hvert lag av hjernen implementerer forskjellige nivåer av generalisering; inputlaget er følsomt for enkle mønstre, som linjer, og deres orientering i visse områder av det visuelle området, mens responsen til andre lag er mer kompleks, abstrakt og uavhengig av mønsterets posisjon. Lignende funksjoner implementeres i kognitronen ved å modellere organisasjonen av den visuelle cortex.

Neocognitron er en videreutvikling av kognitronideen og gjenspeiler mer nøyaktig strukturen til det visuelle systemet, lar deg gjenkjenne bilder uavhengig av deres transformasjoner, rotasjoner, forvrengninger og skalaendringer.

Cognitron er et kraftig bildegjenkjenningsverktøy, men det krever høye beregningskostnader, som for øyeblikket er uoppnåelige.

De vurderte nevrale nettverksmetodene gir rask og pålitelig bildegjenkjenning, men ved bruk av disse metodene oppstår det problemer med gjenkjennelsen av tredimensjonale objekter. Imidlertid har denne tilnærmingen mange fordeler.

Konklusjon

For tiden er det et ganske stort antall automatiske mønstergjenkjenningssystemer for ulike anvendte problemer.

Mønstergjenkjenning ved formelle metoder som en grunnleggende vitenskapelig retning er uuttømmelig.

Matematiske metoder for bildebehandling har en lang rekke bruksområder: vitenskap, teknologi, medisin, sosial sfære. I fremtiden vil mønstergjenkjenningens rolle i menneskelivet øke enda mer.

Nevrale nettverksmetoder gir rask og pålitelig bildegjenkjenning. Denne tilnærmingen har mange fordeler og er en av de mest lovende.

Litteratur

D.V. Brilyuk, V.V. Starovoitov. Nevrale nettverksmetoder for bildegjenkjenning // /

Kuzin L.T. Fundamentals of Cybernetics: Fundamentals of Cybernetic Models. T.2. - M.: Energi, 1979. - 584 s.

Peregudov F.I., Tarasenko F.P. Introduksjon til systemanalyse: Lærebok. - M .: Videregående skole, 1997. - 389s.

Temnikov F.E., Afonin V.A., Dmitriev V.I. Teoretisk grunnlag for informasjonsteknologi. - M.: Energi, 1979. - 511s.

Tu J., Gonzalez R. Prinsipper for mønstergjenkjenning. / Per. fra engelsk. - M.: Mir, 1978. - 410-tallet.

Winston P. Kunstig intelligens. / Per. fra engelsk. - M.: Mir, 1980. - 520-tallet.

Fu K. Strukturelle metoder i mønstergjenkjenning: Oversatt fra engelsk. - M.: Mir, 1977. - 320-tallet.

Tsypkin Ya.Z. Fundamentals of Information Theory of Identification. - M.: Nauka, 1984. - 520-tallet.

Pospelov G.S. Kunstig intelligens er grunnlaget for ny informasjonsteknologi. - M.: Nauka, 1988. - 280-tallet.

Yu. Lifshits, Statistiske metoder for mønstergjenkjenning ///modern/07modernnote.pdf

Bohr N. Atomfysikk og menneskelig kunnskap. / Oversettelse fra engelsk. - M.: Mir, 1961. - 151s.

Butakov E.A., Ostrovsky V.I., Fadeev I.L. Bildebehandling på datamaskin.1987.-236s.

Duda R., Hart P. Mønstergjenkjenning og sceneanalyse. / Oversettelse fra engelsk. - M.: Mir, 1978. - 510-tallet.

Duke V.A. Datapsykodiagnostikk. - St. Petersburg: Brotherhood, 1994. - 365 s.

Aizenberg I. N., Aizenberg N. N. og Krivosheev G.A. Flerverdier og universelle binære nevroner: læringsalgoritmer, applikasjoner til bildebehandling og gjenkjenning. Lecture Notes in Artificial Intelligence - Machine Learning and Data Mining in Pattern Recognition, 1999, s. 21-35.

Ranganath S. og Arun K. Ansiktsgjenkjenning ved bruk av transformasjonsfunksjoner og nevrale nettverk. Pattern Recognition 1997, Vol. 30, s. 1615-1622.

Golovko V.A. Nevrointelligens: teori og anvendelser. Bok 1. Organisering og trening av nevrale nettverk med direkte og tilbakemelding - Brest: BPI, 1999, - 260s.

Vetter T. og Poggio T. Lineære objektklasser og bildesyntese fra et enkelt eksempelbilde. IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, s. 733-742.

Golovko V.A. Nevrointelligens: teori og anvendelser. Bok 2. Selvorganisering, feiltoleranse og bruk av nevrale nettverk - Brest: BPI, 1999, - 228s.

Lawrence S., Giles C. L., Tsoi A. C. og Back A. D. Face Recognition: A Convolutional Neural Network Approach. IEEE Transactions on Neural Networks, Special Issue on Neural Networks and Pattern Recognition, s. 1-24.

Wasserman F. Nevrodatamaskinteknologi: Teori og praksis, 1992 - 184s.

Rowley H. A., Baluja S. og Kanade T. Neural Network-Based Face Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 1998, Vol. 20, s. 23-37.

Valentin D., Abdi H., O "Toole A. J. og Cottrell G. W. Connectionist-modeller for ansiktsbehandling: en undersøkelse. IN: Pattern Recognition 1994, Vol. 27, s. 1209-1230.

Dokument

De lager algoritmer AnerkjennelseBilder. MetoderAnerkjennelseBilder Som nevnt ovenfor ... er det ikke virkeligheten finnes"økosystemer generelt" og eksistere bare noen få ... konklusjoner fra denne detaljerte anmeldelsemetoderAnerkjennelse vi presenterte i...

Oversikt over metoder for å identifisere personer basert på ansiktsbilder, tatt i betraktning funksjonene til visuell gjenkjenning
Anmeldelse
... Anerkjennelse av en person av lavkontrastobjekter, inkl. personer. brakte med seg anmeldelse felles metoder ... Finnes hele linjen metoder ... vei, som et resultat av studien, en plattform for utvikling av metodeAnerkjennelse ...
Imeni Glazkova Valentina Vladimirovna FORSKNING OG UTVIKLING AV METODER FOR KONSTRUKSJON AV PROGRAMVAREVERKTØY FOR KLASSIFISERING AV MULTI-EMNE HYPERTEKSTDOKUMENT Spesialitet 05
Avhandlingsabstrakt
hypertekstdokumenter. Kapitlet inneholder anmeldelseeksisterendemetoder løsning av problemet under vurdering, beskrivelse ... ved å kutte av de minst relevante klassene // Matematisk metoderAnerkjennelseBilder: 13. allrussiske konferanse. Leningrad-regionen...
Lysbilde 0 Oversikt over bioinformatikkens oppgaver knyttet til analyse og prosessering av genetiske tekster
Foredrag
DNA og proteinsekvenser. Anmeldelse oppgaver av bioinformatikk som oppgaver ... signaler krever bruk av moderne metoderAnerkjennelseBilder, statistiske tilnærminger og ... med lav gentetthet. Eksisterende genprediksjonsprogrammer gjør det ikke...

→

Kapittel 3: Analytisk gjennomgang av metoder for mønstergjenkjenning og beslutningstaking

Mønstergjenkjenningsteori og kontrollautomatisering

Hovedoppgavene til adaptiv mønstergjenkjenning

Gjenkjenning er en informasjonsprosess implementert av en informasjonsomformer (intelligent informasjonskanal, gjenkjenningssystem) som har en inngang og utgang. Inngangen til systemet er informasjon om hvilke funksjoner de presenterte objektene har. Utdataene fra systemet viser informasjon om hvilke klasser (generaliserte bilder) de gjenkjennelige objektene er tilordnet.

Ved opprettelse og drift av et automatisert mønstergjenkjenningssystem løses en rekke oppgaver. La oss kort og enkelt vurdere disse oppgavene. Det skal bemerkes at formuleringene av disse problemene, og settet i seg selv, ikke sammenfaller med forskjellige forfattere, siden det til en viss grad avhenger av den spesifikke matematiske modellen som dette eller det gjenkjenningssystemet er basert på. I tillegg har noen oppgaver i visse gjenkjennelsesmodeller ikke en løsning og er følgelig ikke stilt.

Oppgaven med å formalisere fagområdet

Faktisk er denne oppgaven en oppgave med koding. En liste over generaliserte klasser er kompilert, som kan inkludere spesifikke implementeringer av objekter, samt en liste over funksjoner som disse objektene i prinsippet kan ha.

Oppgaven med å danne en treningsprøve

Treningseksemplet er en database som inneholder beskrivelser av spesifikke implementeringer av objekter på funksjonsspråket, supplert med informasjon om tilhørigheten til disse objektene til visse gjenkjennelsesklasser.

Oppgaven med å trene opp gjenkjenningssystemet

Treningsutvalget brukes til å danne generaliserte bilder av gjenkjennelsesklasser basert på generalisering av informasjon om hvilke egenskaper objektene i treningsutvalget har som tilhører denne klassen og andre klasser.

Problemet med reduksjon av funksjonsromsdimensjoner

Etter å ha trent gjenkjenningssystemet (innhenting av statistikk over fordelingen av funksjonsfrekvenser etter klasse), blir det mulig å bestemme verdien for hver funksjon for å løse gjenkjenningsproblemet. Etter det kan de minst verdifulle funksjonene fjernes fra funksjonssystemet. Deretter må gjenkjennelsessystemet omskoleres, siden som et resultat av fjerning av noen funksjoner, endres distribusjonsstatistikken til de gjenværende funksjonene etter klasse. Denne prosessen kan gjentas, dvs. være iterativ.

Gjenkjennelsesoppgave

Objekter av en gjenkjennelig prøve gjenkjennes, som spesielt kan bestå av ett objekt. Det gjenkjennelige utvalget er dannet på samme måte som treningsutvalget, men inneholder ikke informasjon om tilhørighet av objekter til klasser, siden det er nettopp dette som bestemmes i gjenkjenningsprosessen. Resultatet av gjenkjennelsen av hvert objekt er en fordeling eller en liste over alle gjenkjennelsesklasser i synkende rekkefølge etter graden av likhet mellom det gjenkjente objektet med dem.

Kvalitetskontrolloppgave for anerkjennelse

Etter anerkjennelse kan dens tilstrekkelighet fastslås. For objekter av treningsprøven kan dette gjøres umiddelbart, siden det for dem ganske enkelt er kjent hvilke klasser de tilhører. For andre objekter kan denne informasjonen innhentes senere. I alle fall kan den faktiske gjennomsnittlige feilsannsynligheten for alle gjenkjennelsesklasser bestemmes, samt feilsannsynligheten ved tilordning av et gjenkjent objekt til en bestemt klasse.

Anerkjennelsesresultatene bør tolkes under hensyntagen til tilgjengelig informasjon om anerkjennelseskvaliteten.

Tilpasningsoppgave

Hvis det, som et resultat av kvalitetskontrollprosedyren, blir konstatert at den er utilfredsstillende, kan beskrivelsene av feil gjenkjente objekter kopieres fra det gjenkjennelige utvalget til opplæringen, supplert med tilstrekkelig klassifiseringsinformasjon og brukes til å omforme beslutningen. regler, dvs. tatt i betraktning. Dessuten, hvis disse objektene ikke tilhører de allerede eksisterende gjenkjenningsklassene, noe som kan være årsaken til deres feilaktige gjenkjennelse, kan denne listen utvides. Som et resultat tilpasser gjenkjenningssystemet seg og begynner å klassifisere disse objektene tilstrekkelig.

Problem med omvendt gjenkjenning

Oppgaven med gjenkjennelse er at for et gitt objekt, i henhold til dets kjente egenskaper, etablerer systemet sin tilhørighet til en tidligere ukjent klasse. I det omvendte gjenkjenningsproblemet, tvert imot, for en gitt gjenkjennelsesklasse, bestemmer systemet hvilke funksjoner som er mest karakteristiske for objekter i denne klassen og hvilke som ikke er det (eller hvilke objekter i treningsutvalget som tilhører denne klassen).

Oppgaver med klynge og konstruktiv analyse

Klynger er slike grupper av objekter, klasser eller funksjoner at de innenfor hver klynge er så like som mulig, og mellom ulike klynger er de så forskjellige som mulig.

En konstruksjon (i konteksten som er vurdert i denne delen) er et system av motsatte klynger. Dermed er konstruksjoner i en viss forstand resultatet av en klyngeanalyse av klynger.

I klyngeanalyse måles graden av likhet og forskjell mellom objekter (klasser, funksjoner) kvantitativt, og denne informasjonen brukes til klassifisering. Resultatet av klyngeanalyse er selve klassifiseringen av objekter etter klynger. Denne klassifiseringen kan representeres i form av semantiske nettverk.

Oppgaven med kognitiv analyse

I kognitiv analyse er informasjon om likhet og forskjell mellom klasser eller trekk av interesse for forskeren i seg selv, og ikke for å bruke den til klassifisering, som i klyngeanalyse og konstruktiv analyse.

Hvis to klasser av anerkjennelse er preget av samme funksjon, så bidrar dette til likheten mellom disse to klassene. Hvis denne funksjonen er ukarakteristisk for en av klassene, bidrar dette til forskjellen.

Hvis to tegn korrelerer med hverandre, kan de i en viss forstand betraktes som ett tegn, og hvis de er anti-relaterte, så som forskjellige. Tatt i betraktning denne omstendigheten, gir tilstedeværelsen av forskjellige funksjoner i forskjellige klasser også et visst bidrag til deres likhet og forskjell.

Resultatene av kognitiv analyse kan presenteres i form av kognitive diagrammer.

Metoder for mønstergjenkjenning og deres egenskaper

Prinsipper for klassifisering av mønstergjenkjenningsmetoder

Mønstergjenkjenning er oppgaven med å konstruere og bruke formelle operasjoner på numeriske eller symbolske representasjoner av objekter i den virkelige eller ideelle verden, hvis resultater gjenspeiler ekvivalensrelasjonene mellom disse objektene. Ekvivalensrelasjoner uttrykker tilhørigheten til de evaluerte objektene til noen klasser, betraktet som uavhengige semantiske enheter.

Ved konstruksjon av gjenkjennelsesalgoritmer kan ekvivalensklasser settes av en forsker som bruker sine egne meningsfulle ideer eller bruker ekstern tilleggsinformasjon om likheten og forskjellen mellom objekter i sammenheng med problemet som skal løses. Da snakker man om «anerkjennelse med læreren». Ellers, dvs. når et automatisert system løser et klassifiseringsproblem uten å involvere ekstern opplæringsinformasjon, snakker man om automatisk klassifisering eller "uovervåket anerkjennelse". De fleste mønstergjenkjenningsalgoritmer krever involvering av svært betydelig datakraft, som bare kan leveres av høyytelses datateknologi.

Ulike forfattere (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, F.E. Temnikov, J. Tu, R. Gonzalez, P. Winston, P. Winston K. Fu, Ya. Z. Tsypkin og andre) gir en annen typologi for mønstergjenkjenningsmetoder. Noen forfattere skiller mellom parametriske, ikke-parametriske og heuristiske metoder, mens andre skiller ut grupper av metoder basert på historiske skoler og trender i feltet. For eksempel, i arbeidet, som gir en akademisk oversikt over gjenkjenningsmetoder, brukes følgende typologi for mønstergjenkjenningsmetoder:

metoder basert på prinsippet om separasjon;
statistiske metoder;
metoder bygget på grunnlag av "potensielle funksjoner";
metoder for å beregne karakterer (stemmegivning);
metoder basert på proposisjonskalkylen, spesielt på apparatet til logikkens algebra.

Denne klassifiseringen er basert på forskjellen i de formelle metodene for mønstergjenkjenning, og derfor er hensynet til den heuristiske tilnærmingen til gjenkjenning, som har fått full og adekvat utvikling i ekspertsystemer, utelatt. Den heuristiske tilnærmingen er basert på vanskelig å formaliserbar kunnskap og intuisjon hos forskeren. Samtidig bestemmer forskeren selv hvilken informasjon og hvordan systemet skal bruke for å oppnå ønsket gjenkjennelseseffekt.

En lignende typologi av gjenkjennelsesmetoder med varierende detaljeringsgrad finnes i mange arbeider om gjenkjennelse. Samtidig tar ikke velkjente typologier hensyn til en veldig viktig egenskap, som gjenspeiler spesifikasjonene ved måten kunnskap om fagområdet er representert ved å bruke en formell mønstergjenkjenningsalgoritme.

D.A. Pospelov (1990) identifiserer to hovedmåter for å representere kunnskap:

intensjonell, i form av et skjema av forbindelser mellom attributter (funksjoner).
utvidelse, ved hjelp av spesifikke fakta (objekter, eksempler).

Den intensjonelle representasjonen fanger opp mønstrene og relasjonene som forklarer strukturen til dataene. Når det gjelder diagnostiske oppgaver, består slik fiksering i å bestemme operasjoner på attributtene (funksjonene) til objekter som fører til det nødvendige diagnostiske resultatet. Intensjonelle representasjoner implementeres gjennom operasjoner på attributtverdier og innebærer ikke operasjoner på spesifikke informasjonsfakta (objekter).

I sin tur er utvidelsesrepresentasjoner av kunnskap assosiert med beskrivelse og fiksering av spesifikke objekter fra fagområdet og implementeres i operasjoner, hvis elementer er objekter som integrerte systemer.

Det er mulig å trekke en analogi mellom intensjonelle og ekstensjonelle representasjoner av kunnskap og mekanismene som ligger til grunn for aktiviteten til venstre og høyre hjernehalvdel. Hvis den høyre hjernehalvdelen er preget av en helhetlig prototypisk representasjon av omverdenen, så opererer venstre hjernehalvdel med mønstre som gjenspeiler forbindelsene til denne verdens attributter.

De to grunnleggende måtene for kunnskapsrepresentasjon beskrevet ovenfor tillater oss å foreslå følgende klassifisering av mønstergjenkjenningsmetoder:

intensjonelle metoder basert på operasjoner med attributter.
utvidelsesmetoder basert på operasjoner med objekter.

Det er nødvendig å understreke at eksistensen av disse to (og bare to) gruppene av gjenkjennelsesmetoder: de som opererer med funksjoner og de som opererer med objekter, er dypt naturlig. Fra dette synspunktet gjør ingen av disse metodene, tatt adskilt fra den andre, det mulig å danne en adekvat refleksjon av fagområdet. I følge forfatterne er det mellom disse metodene en relasjon av komplementaritet i betydningen N. Bohr, derfor bør lovende gjenkjenningssystemer sikre implementeringen av begge disse metodene, og ikke hvilken som helst av dem.

Klassifiseringen av anerkjennelsesmetoder foreslått av D. A. Pospelov er derfor basert på de grunnleggende lovene som ligger til grunn for den menneskelige måten å erkjenne på generelt, noe som setter den i en helt spesiell (privilegert) posisjon sammenlignet med andre klassifikasjoner, som på denne bakgrunn ser ut. mer lett og kunstig.

Intensjonelle metoder

Gruppen av intensjonelle mønstergjenkjenningsmetoder er omfattende, og dens inndeling i underklasser er noe vilkårlig.

Metoder basert på estimater av fordelingstetthetene til funksjonsverdier

Disse mønstergjenkjenningsmetodene er lånt fra den klassiske teorien om statistiske beslutninger, der studieobjektene betraktes som realiseringer av en flerdimensjonal tilfeldig variabel fordelt i funksjonsrommet i henhold til en lov. De er basert på et Bayesiansk beslutningsskjema som appellerer til a priori sannsynligheter for objekter som tilhører en bestemt gjenkjennelig klasse og betingede distribusjonstettheter av funksjonsvektorverdier. Disse metodene er redusert til å bestemme sannsynlighetsforholdet i forskjellige områder av det flerdimensjonale funksjonsrommet.

Gruppen av metoder basert på estimering av fordelingstetthetene til funksjonsverdier er direkte relatert til metodene for diskriminant analyse. Den bayesianske tilnærmingen til beslutningstaking er en av de mest utviklede i moderne statistikk, de såkalte parametriske metodene, for hvilke det analytiske uttrykket for distribusjonsloven (i dette tilfellet normalloven) anses å være kjent, og bare en et lite antall parametere (middelvektorer og kovariansmatriser) må estimeres.

De største vanskelighetene med å bruke disse metodene er behovet for å huske hele treningsutvalget for å beregne estimater av lokale sog høy følsomhet for ikke-representativiteten til treningsutvalget.

Metoder basert på antakelser om klassen av beslutningsfunksjoner

I denne gruppen av metoder anses den generelle formen for beslutningsfunksjonen som kjent og dens kvalitet funksjonell er gitt. Basert på denne funksjonen finner man den beste tilnærmingen til beslutningsfunksjonen fra treningssekvensen. Det vanligste er representasjoner av beslutningsfunksjoner i form av lineære og generaliserte ikke-lineære polynomer. Kvalitetsfunksjonen til beslutningsregelen er vanligvis forbundet med klassifiseringsfeilen.

Hovedfordelen med metoder basert på antakelser om klassen av beslutningsfunksjoner er klarheten i den matematiske formuleringen av gjenkjennelsesproblemet som et problem med å finne et ekstremum. Variasjonen av metoder for denne gruppen forklares av det brede spekteret av brukte kvalitetsfunksjoner for beslutningsregeler og ekstremumsøkealgoritmer. En generalisering av de betraktede algoritmene, som spesielt inkluderer Newtons algoritme, perceptron-type algoritmer, etc., er metoden for stokastisk tilnærming.

Gradientalgoritmers muligheter for å finne et ekstremum, spesielt i gruppen av lineære beslutningsregler, er studert ganske godt. Konvergensen til disse algoritmene har blitt bevist bare for tilfellet når de gjenkjennelige klassene av objekter vises i funksjonsrommet av kompakte geometriske strukturer.

Tilstrekkelig høy kvalitet på beslutningsregelen kan oppnås ved å bruke algoritmer som ikke har et strengt matematisk bevis på konvergensen av løsningen til det globale ekstremumet. Slike algoritmer inkluderer en stor gruppe heuristiske programmeringsprosedyrer som representerer retningen for evolusjonær modellering. Evolusjonsmodellering er en bionisk metode lånt fra naturen. Den er basert på bruken av kjente evolusjonsmekanismer for å erstatte prosessen med meningsfull modellering av et komplekst objekt med fenomenologisk modellering av dets evolusjon. En velkjent representant for evolusjonær modellering i mønstergjenkjenning er metoden for grupperegnskap for argumenter (MGUA). GMDH er basert på prinsippet om selvorganisering, og GMDH-algoritmene gjengir ordningen med masseutvelgelse.

Oppnåelsen av praktiske mål i dette tilfellet er imidlertid ikke ledsaget av utvinning av ny kunnskap om naturen til gjenkjennelige objekter. Muligheten for å trekke ut denne kunnskapen, spesielt kunnskap om mekanismene for interaksjon av attributter (funksjoner), er fundamentalt begrenset her av den gitte strukturen til slik interaksjon, festet i den valgte formen for avgjørende funksjoner.

boolske metoder

Logiske metoder for mønstergjenkjenning er basert på apparatet til logisk algebra og tillater å operere med informasjon som ikke bare finnes i individuelle funksjoner, men også i kombinasjoner av funksjonsverdier. I disse metodene betraktes verdiene til ethvert attributt som elementære hendelser.

I den mest generelle formen kan logiske metoder karakteriseres som et slags søk etter logiske mønstre i treningsutvalget og dannelsen av et visst system av logiske beslutningsregler (for eksempel i form av konjunksjoner av elementære hendelser), hver av som har sin egen vekt. Gruppen av logiske metoder er mangfoldig og inkluderer metoder med varierende kompleksitet og analysedybde. For dikotome (boolske) funksjoner er de såkalte trelignende klassifikatorene, blindveistestmetoden, Bark-algoritmen, etc. populære.

Kora-algoritmen, som andre logiske metoder for mønstergjenkjenning, er ganske arbeidskrevende når det gjelder beregning, siden en fullstendig oppregning er nødvendig når du velger konjunksjoner. Ved bruk av logiske metoder stilles det derfor høye krav til effektiv organisering av beregningsprosessen, og disse metodene fungerer godt med relativt små dimensjoner av funksjonsrommet og kun på kraftige datamaskiner.

Språklige (strukturelle) metoder

Språklige metoder for mønstergjenkjenning er basert på bruk av spesielle grammatikker som genererer språk som kan brukes til å beskrive et sett med egenskaper til gjenkjennelige objekter.

For forskjellige klasser av objekter skilles ikke-avledede (atomiske) elementer (underbilder, tegn) og mulige forhold mellom dem. Grammatikk refererer til reglene for å konstruere objekter fra disse ikke-avledede elementene.

Dermed er hvert objekt en samling av ikke-avledede elementer, "koblet" til hverandre på en eller annen måte, eller, med andre ord, av en "setning" av et eller annet "språk". Jeg vil gjerne understreke den svært betydelige ideologiske verdien av denne tanken.

Ved å analysere (parse) en "setning", bestemmes dens syntaktiske "riktighet", eller tilsvarende, om noen fast grammatikk som beskriver en klasse kan generere en eksisterende objektbeskrivelse.

Oppgaven med å gjenopprette (definere) grammatikk fra et bestemt sett med utsagn (setninger - beskrivelser av objekter) som genererer et gitt språk er imidlertid vanskelig å formalisere.

Utvidende metoder

Hovedoperasjonene i mønstergjenkjenning ved å bruke de diskuterte metodene er operasjonene for å bestemme likheten og forskjellen mellom objekter. Objekter i den angitte gruppen av metoder spiller rollen som diagnostiske presedenser. Samtidig, avhengig av betingelsene for en bestemt oppgave, kan rollen til en individuell presedens variere innenfor de videste grensene: fra den viktigste og definerende til svært indirekte deltakelse i anerkjennelsesprosessen. På sin side kan betingelsene for problemet kreve deltakelse av et annet antall diagnostiske presedenser for en vellykket løsning: fra en i hver gjenkjennelig klasse til full prøvestørrelse, samt forskjellige måter å beregne målene for likhet og forskjell mellom gjenstander. Disse kravene forklarer den videre inndelingen av utvidelsesmetoder i underklasser.

Prototype sammenligningsmetode

Dette er den enkleste utvidelsesgjenkjenningsmetoden. Den brukes for eksempel i tilfellet når de gjenkjente klassene vises i funksjonsområdet ved kompakte geometriske grupperinger. I dette tilfellet velges vanligvis midten av den geometriske grupperingen av klassen (eller objektet nærmest midten) som prototypepunkt.

For å klassifisere et ukjent objekt, blir prototypen nærmest funnet, og objektet tilhører samme klasse som denne prototypen. Det dannes åpenbart ingen generaliserte klassebilder i denne metoden.

I praksis er situasjonen selvsagt ofte annerledes enn det beskrevne idealiserte eksempelet. En forsker som har til hensikt å bruke en gjenkjennelsesmetode basert på sammenligning med prototypene til diagnostiske klasser, møter vanskelige problemer.

For det første er det valget av et nærhetsmål (metrisk), som kan endre den romlige konfigurasjonen av fordelingen av objekter betydelig. For det andre er et uavhengig problem analysen av flerdimensjonale strukturer av eksperimentelle data. Begge disse problemene er spesielt akutte for forskeren under forhold med høy dimensjon av funksjonsrommet, noe som er typisk for reelle problemer.

k nærmeste nabo metode

Den k nærmeste nabo-metoden for å løse diskriminerende analyseproblemer ble først foreslått tilbake i 1952. Det er som følger.

Opprinnelig ble metoden k nærmeste naboer vurdert som en ikke-parametrisk metode for å estimere sannsynlighetsforholdet. For denne metoden oppnås teoretiske estimater av dens effektivitet sammenlignet med den optimale Bayesianske klassifikatoren. Det er bevist at de asymptotiske feilsannsynlighetene for k nærmeste nabo-metoden overskrider feilene i Bayes-regelen med ikke mer enn to ganger.

Når man bruker metoden k nærmeste naboer for mønstergjenkjenning, må forskeren løse det vanskelige problemet med å velge en metrikk for å bestemme nærheten til diagnostiserte objekter. Dette problemet i forholdene med høy dimensjon av funksjonsrommet blir ekstremt forverret på grunn av den tilstrekkelige kompleksiteten til denne metoden, som blir betydelig selv for datamaskiner med høy ytelse. Derfor, akkurat som i prototypesammenligningsmetoden, er det nødvendig å løse det kreative problemet med å analysere den flerdimensjonale strukturen til eksperimentelle data for å minimere antallet objekter som representerer diagnostiske klasser.

Behovet for å redusere antall objekter i treningsutvalget (diagnostiske presedenser) er en ulempe ved denne metoden, da den reduserer representativiteten til treningsutvalget.

Algoritmer for å beregne karakterer ("stemme")

Prinsippet for drift av evalueringsalgoritmer (ABO) er å beregne prioriteter (likhetspoeng) som karakteriserer "nærheten" til de gjenkjente og referanseobjektene i henhold til systemet med funksjonsensembler, som er et system av undersett av et gitt sett med funksjoner .

De brukte kombinasjonene av attributter (underrom) kalles støttesett eller sett med delvise beskrivelser av objekter. Konseptet med generalisert nærhet mellom det gjenkjente objektet og objektene i treningsutvalget (med en kjent klassifisering), som kalles referanseobjekter, introduseres. Denne nærheten er representert ved en kombinasjon av nærheten til det gjenkjente objektet med referanseobjektene beregnet på sett med delbeskrivelser. Dermed er ABO en utvidelse av metoden k nærmeste naboer, der nærhet til objekter kun vurderes i ett gitt funksjonsrom.

En annen utvidelse av ABO er at i disse algoritmene er problemet med å bestemme likheten og forskjellen mellom objekter formulert som en parametrisk, og trinnet for å justere ABO på treningsprøven velges, hvor de optimale verdiene for de angitte parametere er valgt. Kvalitetskriteriet er gjenkjenningsfeilen, og bokstavelig talt er alt parametrisert:

regler for å beregne nærheten til objekter etter individuelle funksjoner;
regler for å beregne nærheten til objekter i funksjonsunderrom;
graden av betydning av et bestemt referanseobjekt som en diagnostisk presedens;
betydningen av bidraget til hvert referansesett med funksjoner til den endelige vurderingen av likheten til det anerkjente objektet med en hvilken som helst diagnostisk klasse.

Luftkjølerparametere settes i form av terskelverdier og (eller) som vekter av de spesifiserte komponentene.

De teoretiske mulighetene til ABO er i det minste ikke lavere enn for noen annen mønstergjenkjenningsalgoritme, siden ved hjelp av ABO kan alle tenkelige operasjoner med objektene som studeres implementeres.

Men, som det vanligvis skjer, møter utvidelsen av potensialer store vanskeligheter i deres praktiske implementering, spesielt på stadiet med å konstruere (tuning) algoritmer av denne typen.

Separate vanskeligheter ble bemerket tidligere når man diskuterte metoden k nærmeste naboer, som kunne tolkes som en avkortet versjon av ABO. Det kan også vurderes i en parametrisk form og redusere problemet til å finne en vektet metrikk av den valgte typen. Samtidig oppstår komplekse teoretiske spørsmål og problemer knyttet til organiseringen av en effektiv beregningsprosess allerede her for høydimensjonale problemer.

For ABO, hvis du prøver å bruke mulighetene til disse algoritmene fullt ut, øker disse vanskelighetene mange ganger.

De bemerkede problemene forklarer det faktum at bruken av ABO for å løse høydimensjonale problemer i praksis er ledsaget av innføring av eventuelle heuristiske begrensninger og forutsetninger. Spesielt er det et eksempel på bruk av ABO i psykodiagnostikk, der en versjon av ABO ble testet, som faktisk tilsvarer metoden k nærmeste naboer.

Avgjørende regelkollektiver

På slutten av gjennomgangen av metoder for mønstergjenkjenning, la oss dvele ved en tilnærming til. Dette er de såkalte teams of decision rules (CRC).

Siden ulike gjenkjennelsesalgoritmer oppfører seg forskjellig på samme utvalg av objekter, oppstår naturligvis spørsmålet om en syntetisk beslutningsregel som adaptivt bruker styrken til disse algoritmene. Den syntetiske beslutningsregelen bruker en to-nivå anerkjennelsesordning. På det første nivået fungerer private gjenkjennelsesalgoritmer, hvis resultater kombineres på andre nivå i synteseblokken. De vanligste metodene for en slik kombinasjon er basert på tildeling av kompetanseområder for en bestemt algoritme. Den enkleste måten å finne kompetanseområder på er å a priori dele opp rommet av funksjoner basert på de faglige vurderingene til en bestemt vitenskap (for eksempel stratifisering av utvalget i henhold til noen funksjoner). Deretter, for hvert av de valgte områdene, bygges en egen gjenkjennelsesalgoritme. En annen metode er basert på bruken av formell analyse for å bestemme lokale områder av funksjonsrommet som nabolag med gjenkjennelige objekter som har bevist suksessen til en bestemt gjenkjennelsesalgoritme.

Den mest generelle tilnærmingen til å konstruere en synteseblokk vurderer de resulterende indikatorene for bestemte algoritmer som innledende funksjoner for å konstruere en ny generalisert beslutningsregel. I dette tilfellet kan alle de ovennevnte metodene for intensjonelle og ekstensjonelle retninger i mønstergjenkjenning brukes. Effektive for å løse problemet med å lage et sett med beslutningsregler er logiske algoritmer av typen "Kora" og algoritmer for beregning av estimater (ABO), som danner grunnlaget for den såkalte algebraiske tilnærmingen, som gir forskning og en konstruktiv beskrivelse av gjenkjenningsalgoritmer, som alle eksisterende typer algoritmer passer innenfor.

Komparativ analyse av mønstergjenkjenningsmetoder

La oss sammenligne mønstergjenkjenningsmetodene beskrevet ovenfor og evaluere graden av deres tilstrekkelighet til kravene formulert i avsnitt 3.3.3 for SDA-modeller for adaptive automatiserte kontrollsystemer for komplekse systemer.

For å løse reelle problemer fra gruppen av metoder i intensjonsretningen, er parametriske metoder og metoder basert på forslag om form av avgjørende funksjoner av praktisk verdi. Parametriske metoder danner grunnlaget for den tradisjonelle metodikken for å konstruere indikatorer. Anvendelsen av disse metodene i reelle problemer er assosiert med å pålegge sterke restriksjoner på datastrukturen, noe som fører til lineære diagnostiske modeller med svært omtrentlige estimater av parameterne deres. Ved bruk av metoder basert på antakelser om form for beslutningsfunksjoner, er forskeren også tvunget til å vende seg til lineære modeller. Dette skyldes den høye dimensjonen til funksjonsrommet, som er typisk for reelle problemer, som, med en økning i graden av polynomavgjørelsesfunksjonen, gir en enorm økning i antallet medlemmer med en problematisk samtidig økning i kvalitet på anerkjennelse. Ved å projisere området med potensiell anvendelse av intensjonelle gjenkjenningsmetoder på reelle problemer, får vi et bilde som tilsvarer den veletablerte tradisjonelle metodikken for lineære diagnostiske modeller.

Egenskapene til lineære diagnostiske modeller, der den diagnostiske indikatoren er representert av en vektet sum av innledende funksjoner, er godt studert. Resultatene av disse modellene (med passende normalisering) tolkes som avstander fra objektene som studeres til et eller annet hyperplan i funksjonsrommet eller tilsvarende som projeksjoner av objektene på en rett linje i det gitte rommet. Derfor er lineære modeller tilstrekkelige bare for enkle geometriske konfigurasjoner av funksjonsromregioner der objekter av forskjellige diagnostiske klasser er kartlagt. Med mer komplekse distribusjoner kan disse modellene fundamentalt ikke reflektere mange funksjoner i den eksperimentelle datastrukturen. Samtidig kan slike funksjoner gi verdifull diagnostisk informasjon.

Samtidig bør utseendet i ethvert reelt problem av enkle flerdimensjonale strukturer (spesielt flerdimensjonale normalfordelinger) betraktes som et unntak snarere enn som en regel. Ofte dannes diagnostiske klasser på grunnlag av komplekse eksterne kriterier, som automatisk medfører den geometriske heterogeniteten til disse klassene i funksjonsrommet. Dette gjelder spesielt for "livs"-kriteriene som man ofte møter i praksis. Under slike forhold fanger bruken av lineære modeller bare de mest "røffe" mønstrene av eksperimentell informasjon.

Bruk av utvidelsesmetoder er ikke assosiert med noen antakelser om strukturen til eksperimentell informasjon, bortsett fra at innenfor de anerkjente klassene må det være en eller flere grupper av objekter som er noe like, og objekter av forskjellige klasser må skille seg fra hverandre i enkelte vei. Det er åpenbart at for enhver begrenset dimensjon av treningsutvalget (og det kan ikke være annerledes), er dette kravet alltid oppfylt bare fordi det er tilfeldige forskjeller mellom objekter. Ulike mål for nærhet (avstand) til objekter i funksjonsrommet brukes som likhetsmål. Derfor avhenger effektiv bruk av ekstensjonelle mønstergjenkjenningsmetoder av hvor godt disse nærhetsmålene er definert, samt av hvilke objekter i treningsutvalget (objekter med kjent klassifisering) som spiller rollen som diagnostiske presedenser. Vellykket løsning av disse problemene gir et resultat som nærmer seg de teoretisk oppnåelige grensene for gjenkjenningseffektivitet.

Fordelene med utvidelsesmetoder for mønstergjenkjenning motvirkes først og fremst av den høye tekniske kompleksiteten til deres praktiske implementering. For høydimensjonale funksjonsrom blir den tilsynelatende enkle oppgaven med å finne par med nærmeste punkter til et alvorlig problem. Mange forfattere bemerker også behovet for å huske et tilstrekkelig stort antall objekter som representerer gjenkjennelige klasser som et problem.

I seg selv er ikke dette et problem, men det oppfattes som et problem (for eksempel i k nearest neighbours-metoden) av den grunn at når man gjenkjenner hvert objekt, skjer en fullstendig oppregning av alle objektene i treningsutvalget.

Derfor er det tilrådelig å bruke modellen av gjenkjennelsessystemet, der problemet med en fullstendig oppregning av gjenstander fra treningsprøven under gjenkjennelse fjernes, siden det bare utføres én gang når det dannes generaliserte bilder av gjenkjennelsesklasser. I selve gjenkjennelsen sammenlignes det identifiserte objektet bare med generaliserte bilder av gjenkjennelsesklasser, hvor antallet er fast og ikke i det hele tatt avhenger av dimensjonen til treningsutvalget. Denne tilnærmingen lar deg øke dimensjonen på treningsprøven til den nødvendige høye kvaliteten på generaliserte bilder er oppnådd, uten frykt for at dette kan føre til en uakseptabel økning i gjenkjenningstiden (siden gjenkjenningstiden i denne modellen ikke er avhengig av dimensjonen av opplæringen i det hele tatt).

De teoretiske problemene med å bruke metoder for utvidelsesgjenkjenning er relatert til problemene med å søke etter informative grupper av funksjoner, finne optimale beregninger for å måle likheter og forskjeller mellom objekter og analysere strukturen til eksperimentell informasjon. Samtidig tillater den vellykkede løsningen av disse problemene ikke bare å designe effektive gjenkjennelsesalgoritmer, men også å gjøre overgangen fra utvidende kunnskap om empiriske fakta til intensjonell kunnskap om mønstrene i deres struktur.

Overgangen fra utvidelseskunnskap til intensjonell kunnskap skjer på det stadiet når en formell gjenkjennelsesalgoritme allerede er konstruert og dens effektivitet er demonstrert. Deretter utføres studiet av mekanismene som oppnår den oppnådde effektiviteten. En slik studie, assosiert med analysen av den geometriske strukturen til data, kan for eksempel føre til konklusjonen at det er nok å erstatte objektene som representerer en bestemt diagnostisk klasse med en typisk representant (prototype). Dette tilsvarer, som nevnt ovenfor, å sette en tradisjonell lineær diagnostisk skala. Det er også mulig at det er nok å erstatte hver diagnostisk klasse med flere objekter som er meningsfulle som typiske representanter for noen underklasser, noe som tilsvarer å konstruere en vifte av lineære skalaer. Det er andre alternativer, som vil bli diskutert nedenfor.

En gjennomgang av gjenkjenningsmetoder viser således at en rekke ulike metoder for mønstergjenkjenning er teoretisk utviklet i dag. Litteraturen gir en detaljert klassifisering av dem. For de fleste av disse metodene er imidlertid programvareimplementeringen fraværende, og dette er dypt naturlig, man kan til og med si "forhåndsbestemt" av egenskapene til selve gjenkjenningsmetodene. Dette kan bedømmes ut fra det faktum at slike systemer er lite omtalt i den spesialiserte litteraturen og andre informasjonskilder.

Følgelig er spørsmålet om den praktiske anvendeligheten av visse teoretiske gjenkjennelsesmetoder for å løse praktiske problemer med reelle (dvs. ganske betydelige) datadimensjoner og på ekte moderne datamaskiner fortsatt utilstrekkelig utviklet.

Ovennevnte omstendighet kan forstås hvis vi husker at kompleksiteten til den matematiske modellen eksponentielt øker kompleksiteten til programvareimplementeringen av systemet og i samme grad reduserer sjansene for at dette systemet faktisk vil fungere. Dette betyr at kun programvaresystemer basert på ganske enkle og «transparente» matematiske modeller kan implementeres på markedet. Derfor nærmer en utvikler som er interessert i å replikere programvareproduktet sitt spørsmålet om å velge en matematisk modell ikke fra et rent vitenskapelig synspunkt, men som en pragmatiker, og tar hensyn til mulighetene for programvareimplementering. Han mener at modellen bør være så enkel som mulig, noe som betyr at den bør implementeres til lavere kostnad og med bedre kvalitet, og den bør også fungere (være praktisk talt effektiv).

I denne forbindelse er oppgaven med å implementere i gjenkjenningssystemer en mekanisme for å generalisere beskrivelser av objekter som tilhører samme klasse, dvs. mekanisme for dannelse av kompakte generaliserte bilder. Det er åpenbart at en slik generaliseringsmekanisme vil tillate å "komprimere" en hvilken som helst treningsprøve når det gjelder dimensjon til en base av generaliserte bilder kjent på forhånd når det gjelder dimensjon. Dette vil også tillate oss å sette og løse en rekke problemer som ikke engang kan formuleres i slike gjenkjennelsesmetoder som sammenligning med prototypemetoden, k nærmeste nabo-metoden og ABO.

Dette er oppgavene:

å bestemme informasjonsbidraget til funksjoner til informasjonsportrettet av et generalisert bilde;
klyngekonstruktiv analyse av generaliserte bilder;
bestemmelse av den semantiske belastningen til attributtet;
semantisk klyngekonstruktiv analyse av funksjoner;
en meningsfull sammenligning av generaliserte klassebilder med hverandre og funksjoner med hverandre (kognitive diagrammer, inkludert Merlin-diagrammer).

Metoden som gjorde det mulig å oppnå løsningen av disse problemene skiller også perspektivsystemet basert på det fra andre systemer, på samme måte som kompilatorer skiller seg fra tolker, siden gjenkjenningstiden på grunn av dannelsen av generaliserte bilder i dette perspektivsystemet er uavhengig av størrelsen på opplæringsutvalget. Det er kjent at det er eksistensen av denne avhengigheten som fører til praktisk talt uakseptable utgifter til datatid for gjenkjenning i slike metoder som k nærmeste nabo-metoden, ABO og CRP ved slike dimensjoner av treningsutvalget, når man kan snakke om tilstrekkelig statistikk.

Som konklusjon av en kort gjennomgang av gjenkjenningsmetoder presenterer vi essensen av ovenstående i en sammendragstabell (tabell 3.1), som inneholder en kort beskrivelse av de ulike metodene for mønstergjenkjenning i følgende parametere:

klassifisering av anerkjennelsesmetoder;
bruksområder for anerkjennelsesmetoder;
klassifisering av begrensninger av anerkjennelsesmetoder.

Klassifisering av gjenkjennelsesmetoder		Bruksområde	Begrensninger (ulemper)
Intensive gjenkjenningsmetoder	Metoder basert på estimater av distribusjonstettheten til funksjonsverdier (eller likheter og forskjeller mellom objekter)	Problemer med en kjent fordeling, vanligvis normal, behovet for å samle inn store statistikker	Behovet for å telle opp hele treningssettet under gjenkjennelse, høy følsomhet for ikke-representativitet av treningssettet og artefakter
	Metoder basert på antakelser om klassen av beslutningsfunksjoner	Klasser bør være godt separerbare, funksjonssystemet bør være ortonormalt	Vedtaksfunksjonens form skal være kjent på forhånd. Umuligheten av å ta hensyn til ny kunnskap om sammenhenger mellom funksjoner
	boolske metoder		Når du velger logiske beslutningsregler (konjunksjoner), er en fullstendig oppregning nødvendig. Høy beregningskompleksitet
	Språklige (strukturelle) metoder	Problemer med liten dimensjon av funksjonsplass	Oppgaven med å gjenopprette (definere) grammatikk fra et bestemt sett med utsagn (beskrivelser av objekter) er vanskelig å formalisere. Uløste teoretiske problemer
Utvidede metoder for anerkjennelse	Prototype sammenligningsmetode	Problemer med liten dimensjon av funksjonsplass	Høy avhengighet av klassifiseringsresultater av avstandsmål (metrikk). Ukjent optimal beregning
	k nærmeste nabo metode		Høy avhengighet av klassifiseringsresultater av avstandsmål (metrikk). Behovet for en fullstendig oppregning av treningsutvalget under anerkjennelse. Beregningsmessig kompleksitet
	Algoritmer for å beregne karakterer (stemme) AVO	Problemer med liten dimensjon når det gjelder antall klasser og funksjoner	Avhengighet av klassifiseringsresultater på avstandsmål (metrisk). Behovet for en fullstendig oppregning av treningsutvalget under anerkjennelse. Høy teknisk kompleksitet av metoden
	Decisive Rule Collectives (CRCs)	Problemer med liten dimensjon når det gjelder antall klasser og funksjoner	Svært høy teknisk kompleksitet av metoden, det uløste antallet teoretiske problemer, både når det gjelder å bestemme kompetanseområdene til bestemte metoder, og i de spesielle metodene i seg selv

Tabell 3.1 - Sammendragstabell over klassifisering av anerkjennelsesmetoder, sammenligning av deres bruksområder og begrensninger

Rollen og stedet for mønstergjenkjenning i automatisering av kompleks systemadministrasjon

Det automatiserte kontrollsystemet består av to hoveddeler: kontrollobjektet og kontrollsystemet.

Kontrollsystemet utfører følgende funksjoner:

identifikasjon av tilstanden til kontrollobjektet;
utvikling av en kontrollhandling basert på ledelsens mål, under hensyntagen til tilstanden til kontrollobjektet og miljøet;
gir en kontrolleffekt på kontrollobjektet.

Mønstergjenkjenning er ikke annet enn identifikasjon av tilstanden til et objekt.

Derfor virker muligheten for å bruke mønstergjenkjenningssystemet på stadiet for å identifisere tilstanden til kontrollobjektet ganske åpenbar og naturlig. Dette kan imidlertid ikke være nødvendig. Derfor oppstår spørsmålet i hvilke tilfeller det er tilrådelig å bruke gjenkjenningssystemet i det automatiserte kontrollsystemet, og i hvilke det ikke er det.

I henhold til litteraturdataene, i mange tidligere utviklede og moderne automatiserte kontrollsystemer, i delsystemene for å identifisere tilstanden til kontrollobjektet og generere kontrollhandlinger, brukes deterministiske matematiske modeller for "direkte telling", som entydig og ganske enkelt bestemmer hva å gjøre med kontrollobjektet hvis det har visse eksterne parametere.

Samtidig er ikke spørsmålet om hvordan disse parameterne er relatert til visse tilstander til kontrollobjektet reist eller løst. Denne posisjonen tilsvarer synspunktet, som består i at deres en-til-en-forhold aksepteres "som standard". Derfor betraktes begrepene: "kontrollobjektets parametre" og "kontrollobjektets tilstand" som synonymer, og konseptet "kontrollobjektets tilstand" er ikke eksplisitt introdusert i det hele tatt. Imidlertid er det åpenbart at i det generelle tilfellet er forholdet mellom de observerte parametrene til kontrollobjektet og dets tilstand dynamisk og sannsynlighet.

Dermed er tradisjonelle automatiserte kontrollsystemer i hovedsak parametriske kontrollsystemer, dvs. systemer som ikke håndterer tilstandene til kontrollobjektet, men bare dets observerbare parametere. Beslutningen om kontrollhandlingen tas i slike systemer som "blindt", dvs. uten å danne et helhetlig bilde av kontrollobjektet og miljøet i deres nåværende tilstand, samt uten å forutsi utviklingen av miljøet og reaksjonen til kontrollobjektet på visse kontrollhandlinger på det, som virker samtidig med den forutsagte påvirkningen av miljøet .

Fra posisjonene utviklet i denne artikkelen, er begrepet "beslutningstaking" i moderne forstand knapt anvendelig for tradisjonelle automatiserte kontrollsystemer. Faktum er at "beslutningstaking" i det minste innebærer en helhetlig visjon av et objekt i miljøet, og ikke bare i deres nåværende tilstand, men også i dynamikk og i samspill både med hverandre og med kontrollsystemet, innebærer vurdering av ulike alternative muligheter for utvikling av hele dette systemet, samt innsnevring av mangfoldet (reduksjon) av disse alternativene basert på bestemte målkriterier. Ingenting av dette er åpenbart ikke i tradisjonell ACS, eller det er det, men i en forenklet form.

Selvfølgelig er den tradisjonelle metoden tilstrekkelig og dens anvendelse er ganske korrekt og berettiget i tilfeller der kontrollobjektet faktisk er et stabilt og stivt bestemt system, og påvirkningen fra miljøet på det kan neglisjeres.

Men i andre tilfeller er denne metoden ineffektiv.

Hvis kontrollobjektet er dynamisk, blir modellene som ligger til grunn for kontrollalgoritmene raskt utilstrekkelige, ettersom forholdet mellom inngangs- og utgangsparametere endres, så vel som selve settet med essensielle parametere. I hovedsak betyr dette at tradisjonelle automatiserte kontrollsystemer er i stand til å kontrollere tilstanden til kontrollobjektet kun nær likevektspunktet ved hjelp av svake kontrollhandlinger på det, dvs. ved metoden med små forstyrrelser. Langt fra tilstanden av likevekt, fra det tradisjonelle synspunktet, ser oppførselen til kontrollobjektet uforutsigbar og ukontrollerbar ut.

Hvis det ikke er en entydig sammenheng mellom inngangs- og utgangsparametere til kontrollobjektet (det vil si mellom inngangsparametere og objektets tilstand), med andre ord, hvis dette forholdet har en uttalt sannsynlighet, vil deterministiske modeller, i som det antas at resultatet av å måle en viss parameter er ganske enkelt tall, i utgangspunktet ikke aktuelt. I tillegg kan formen på dette forholdet rett og slett være ukjent, og da er det nødvendig å gå ut fra den mest generelle antagelsen: at den er sannsynlighetsovervekt, eller ikke definert i det hele tatt.

Et automatisert kontrollsystem bygget på tradisjonelle prinsipper kan kun fungere på grunnlag av parametere, hvis relasjonsmønstre allerede er kjent, studert og reflektert i den matematiske modellen, i denne studien ble oppgaven satt til å utvikle slike metoder for utforming av automatisert kontroll systemer som vil tillate å lage systemer som kan identifisere og angi de viktigste parameterne, og bestemme arten av koblingene mellom dem og tilstandene til kontrollobjektet.

I dette tilfellet er det nødvendig å bruke mer utviklede og tilstrekkelige målemetoder til den virkelige situasjonen:

klassifisering eller mønstergjenkjenning (læring basert på et treningsutvalg, tilpasningsevne for gjenkjennelsesalgoritmer, tilpasningsevne for sett med klasser og studerte parametere, valg av de viktigste parameterne og reduksjon av beskrivelsesdimensjon samtidig som en gitt redundans opprettholdes, etc.);
statistiske målinger, når resultatet av å måle en viss parameter ikke er et enkelt tall, men en sannsynlighetsfordeling: en endring i en statistisk variabel betyr ikke en endring i verdien i seg selv, men en endring i egenskapene til sannsynlighetsfordelingen til sine verdier.

Som et resultat fungerer automatiserte kontrollsystemer basert på den tradisjonelle deterministiske tilnærmingen praktisk talt ikke med komplekse dynamiske multi-parameter svakt bestemte kontrollobjekter, som for eksempel makro- og mikrososioøkonomiske systemer i en dynamisk økonomi i " overgangsperiode”, hierarkisk elite og etniske grupper, samfunn og velgere, menneskelig fysiologi og psyke, naturlige og kunstige økosystemer og mange andre.

Det er veldig viktig at skolen til I.Prigozhin på midten av 80-tallet utviklet en tilnærming, ifølge hvilken i utviklingen av ethvert system (inkludert en person), veksler perioder der systemet oppfører seg enten som "for det meste deterministisk", eller som «for det meste tilfeldig». Naturligvis må et reelt kontrollsystem stabilt styre kontrollobjektet, ikke bare i "deterministiske" deler av dets historie, men også på punkter der dets videre oppførsel blir svært usikker. Dette alene betyr at det er nødvendig å utvikle tilnærminger til styring av systemer der det er et stort element av tilfeldighet (eller det som i dag matematisk beskrives som "tilfeldighet").

Derfor vil sammensetningen av lovende automatiserte kontrollsystemer som gir kontroll over komplekse dynamiske multiparameter svakt deterministiske systemer, som essensielle funksjonelle lenker, tilsynelatende inkludere delsystemer for å identifisere og forutsi tilstandene til miljøet og kontrollobjektet, basert på metoder kunstig intelligens(primært mønstergjenkjenning), beslutningsstøttemetoder og informasjonsteori.

La oss kort vurdere spørsmålet om bruk av bildegjenkjenningssystemer for å ta en beslutning om en kontrollhandling (dette spørsmålet vil bli diskutert mer detaljert senere, siden det er nøkkelen for dette arbeidet). Hvis vi tar målet og andre tilstander til kontrollobjektet som gjenkjennelsesklasser, og faktorene som påvirker det som tegn, så kan et mål på forholdet mellom faktorer og tilstander dannes i mønstergjenkjenningsmodellen. Dette gjør det mulig å innhente informasjon om faktorene som bidrar til eller hindrer overgangen til denne tilstanden, basert på en gitt tilstand av kontrollobjektet, og på dette grunnlag utvikle en beslutning om kontrollhandlingen.

Faktorer kan deles inn i følgende grupper:

karakterisere forhistorien til kontrollobjektet;
karakterisering av den nåværende tilstanden til kontrollobjektet;
miljøfaktorer;
teknologiske (administrerte) faktorer.

Dermed kan bildegjenkjenningssystemer brukes som en del av et automatisert kontrollsystem: i undersystemer for å identifisere tilstanden til et kontrollobjekt og generere kontrollhandlinger.

Dette er nyttig når kontrollobjektet er et komplekst system.

Ta en beslutning om kontrollhandlingen i det automatiserte kontrollsystemet

Løsningen av problemet med syntese av adaptive automatiserte kontrollsystemer av komplekse systemer vurderes i denne artikkelen, og tar hensyn til mange og dype analogier mellom metodene for mønstergjenkjenning og beslutningstaking.

På den ene siden er oppgaven med mønstergjenkjenning en beslutning om tilhørigheten til et gjenkjennelig objekt til en bestemt gjenkjennelsesklasse.

På den annen side foreslår forfatterne å betrakte problemet med beslutningstaking som et omvendt problem med dekoding eller et omvendt problem med mønstergjenkjenning (se avsnitt 2.2.2).

Fellesskapet til de grunnleggende ideene som ligger til grunn for metodene for mønstergjenkjenning og beslutningstaking blir spesielt tydelig når man vurderer dem fra informasjonsteoriens ståsted.

En rekke beslutningsoppgaver

Beslutningstaking som realisering av et mål

Definisjon: å ta en beslutning («valg») er en handling på et sett med alternativer, som et resultat av at det opprinnelige settet med alternativer innsnevres, dvs. den reduseres.

Valg er en handling som gir målrettethet til all aktivitet. Det er gjennom valghandlinger at underordningen av all aktivitet til et spesifikt mål eller et sett med sammenhengende mål realiseres.

Derfor, for at den valgte handlingen skal bli mulig, er følgende nødvendig:

generering eller oppdagelse av et sett med alternativer for å ta et valg;
bestemmelse av målene for oppnåelsen av valget;
utvikling og anvendelse av en metode for å sammenligne alternativer med hverandre, dvs. fastsettelse av en preferansevurdering for hvert alternativ i henhold til visse kriterier, noe som gjør det mulig å indirekte vurdere hvordan hvert alternativ oppfyller målet.

Moderne arbeid innen beslutningsstøtte har avslørt en karakteristisk situasjon, som består i det faktum at fullstendig formalisering av å finne den beste (i en viss forstand) løsning bare er mulig for godt studerte, relativt enkle problemer, mens i praksis, svakt strukturerte problemer er mer vanlige, for hvilke fullstendig formaliserte algoritmer ikke er utviklet (bortsett fra uttømmende oppregning og prøving og feiling). Men erfarne, kompetente og dyktige fagfolk tar ofte valg som viser seg å være ganske gode. Derfor er den nåværende trenden i beslutningspraksis i naturlige situasjoner å kombinere en persons evne til å løse ikke-formaliserte problemer med evnene til formelle metoder og datamodellering: interaktive beslutningsstøttesystemer, ekspertsystemer, adaptiv menneske-maskin automatisert kontrollsystemer, nevrale nettverk og kognitive systemer.

Beslutningstaking som fjerning av usikkerhet (informasjonstilnærming)

Prosessen med å innhente informasjon kan betraktes som en reduksjon i usikkerhet som følge av mottak av et signal, og mengden informasjon som et kvantitativt mål på graden av fjerning av usikkerhet.

Men som et resultat av å velge en del av alternativer fra settet, dvs. som et resultat av å ta en beslutning, skjer det samme (nedgang i usikkerhet). Dette betyr at hvert valg, hver beslutning genererer en viss mengde informasjon, og kan derfor beskrives i form av informasjonsteori.

Klassifisering av beslutningsproblemer

Mangfoldet av beslutningsoppgaver skyldes det faktum at hver komponent i situasjonen der beslutningstaking utføres kan implementeres i kvalitativt forskjellige alternativer.

Her er bare noen av disse alternativene:

settet med alternativer kan på den ene siden være endelig, tellbar eller kontinuerlig, og på den annen side kan den være lukket (det vil si fullstendig kjent) eller åpen (inkludert ukjente elementer);
alternativer kan vurderes etter ett eller flere kriterier, som igjen kan være kvantitative eller kvalitative;
utvalgsmodusen kan være enkelt (en gang), eller flere, repeterende, inkludert tilbakemelding på resultatene av utvalget, dvs. tillate læring av beslutningsalgoritmer, med tanke på konsekvensene av tidligere valg;
konsekvensene av å velge hvert alternativ kan være nøyaktig kjent på forhånd (valg under sikkerhet), ha en sannsynlighet når sannsynlighetene for mulige utfall er kjent etter at valget er tatt (valg under risiko) eller ha et tvetydig utfall med ukjente sannsynligheter (valg) under usikkerhet);
ansvaret for valget kan være fraværende, være individuelt eller gruppe;
graden av konsistens av mål i et gruppevalg kan variere fra fullstendig sammenfall av partenes interesser (samarbeidsvalg) til deres motsatte (valg i en konfliktsituasjon). Mellomliggende alternativer er også mulige: et kompromiss, en koalisjon, en voksende eller falmende konflikt.

Ulike kombinasjoner av disse alternativene fører til mange beslutningsproblemer som har blitt studert i ulik grad.

Språk for å beskrive beslutningsmetoder

Ett og samme fenomen kan snakkes om på forskjellige språk med ulik grad av generalitet og adekvans. Til dags dato har det vært tre hovedspråk for å beskrive valg.

Det enkleste, mest utviklede og mest populære er kriteriespråket.

Kriteriespråk

Navnet på dette språket er assosiert med den grunnleggende antakelsen om at hvert enkelt alternativ kan evalueres med et bestemt (ett) tall, hvoretter sammenligningen av alternativer reduseres til en sammenligning av deres tilsvarende tall.

La for eksempel (X) være et sett med alternativer, og x være et bestemt alternativ som hører til denne mengden: x∈X. Da vurderes det at det for alle x kan gis en funksjon q(x), som kalles et kriterium (kvalitetskriterium, objektivfunksjon, preferansefunksjon, nyttefunksjon osv.), som har den egenskapen at hvis alternativet x 1 er foretrukket fremfor x 2 (betegnet: x 1 > x 2), deretter q (x 1) > q (x 2).

I dette tilfellet reduseres valget til å finne et alternativ med den høyeste verdien av kriteriefunksjonen.

Men i praksis viser bruken av kun ett kriterium for å sammenligne graden av preferanse for alternativer å være en uberettiget forenkling, siden en mer detaljert vurdering av alternativer fører til behovet for å vurdere dem ikke etter ett, men ifølge mange kriterier som kan være av ulik karakter og kvalitativt forskjellige fra hverandre.

For eksempel, når du velger den mest akseptable flytypen for passasjerer og driftsorganisasjonen på visse typer ruter, utføres sammenligningen samtidig i henhold til mange grupper av kriterier: teknisk, teknologisk, økonomisk, sosial, ergonomisk, etc.

Multikriterieproblemer har ikke en unik generell løsning. Derfor foreslås det mange måter å gi et multikriteriaproblem en bestemt form som tillater en enkelt generell løsning. Naturligvis er disse løsningene generelt forskjellige for forskjellige metoder. Derfor er kanskje det viktigste for å løse et multikriteriaproblem begrunnelsen for denne typen formulering.

Ulike alternativer for å forenkle mbrukes. La oss liste noen av dem.

Betinget maksimering (ikke det globale ekstremumet til integralkriteriet er funnet, men det lokale ekstremumet til hovedkriteriet).
Søk etter et alternativ med gitte egenskaper.
Finne Pareto-settet.
Reduksjon av et problem med flere kriterier til et enkeltkriterium ved å innføre et integrert kriterium.

La oss vurdere mer detaljert den formelle formuleringen av metoden for å redusere et multikriterieproblem til et enkeltkriterie.

Vi introduserer integralkriteriet q 0 (x) som en skalarfunksjon av vektorargumentet:

q 0 (x) = q 0 ((q 1 (x), q 2 (x), ..., q n (x)).

Integralkriteriet gjør det mulig å sortere alternativene etter q 0 , og dermed fremheve det beste (i betydningen av dette kriteriet). Formen til funksjonen q 0 bestemmes av hvor spesifikt vi forestiller oss bidraget til hvert kriterium til integralkriteriet. Vanligvis brukes additive og multiplikative funksjoner:

q 0 = ∑a i ⋅q i /s i

1 - q 0 = ∏(1 - b i ⋅q i /s i)

Koeffisienter jeg gir:

Dimensjonsløshet eller en enkelt dimensjon av tallet a i ⋅q i /s i (ulike spesielle kriterier kan ha forskjellige dimensjoner, og da er det umulig å utføre aritmetiske operasjoner på dem og redusere dem til et integrert kriterium).
Normalisering, dvs. bestemmelse av betingelsen: b i ⋅q i /s i<1.

Koeffisientene a i og b i reflekterer det relative bidraget til bestemte kriterier q i til integralkriteriet.

Så, i en multi-kriterie-innstilling, er problemet med å ta en beslutning om å velge ett av alternativene redusert til å maksimere det integrerte kriteriet:

x * = arg maks(q 0 (q 1 (x), q 2 (x), ..., q n (x)))

Hovedproblemet i multikriteria-formuleringen av beslutningstakingsproblemet er at det er nødvendig å finne en slik analytisk form av koeffisientene a i og bi, som vil gi følgende egenskaper til modellen:

en høy grad av tilstrekkelighet av fagområdet og synspunktet til eksperter;
minimale beregningsvansker med å maksimere integralkriteriet, dvs. dens beregning for ulike alternativer;
stabilitet av resultatene for å maksimere integreringskriteriet fra små forstyrrelser av de første dataene.
Løsningens stabilitet betyr at en liten endring i de opprinnelige dataene bør føre til en liten endring i verdien av integralkriteriet, og følgelig til en liten endring i beslutningen. Derfor, hvis de første dataene er praktisk talt de samme, bør avgjørelsen tas enten den samme eller veldig nærme.

Sekvensielt binært utvalgsspråk

Språket for binære relasjoner er en generalisering av multikriteriespråket og er basert på at når vi vurderer et eller annet alternativ, er denne vurderingen alltid relativ, dvs. eksplisitt eller oftere implisitt brukes andre alternativer fra settet som studeres eller fra befolkningen generelt som en base eller referanseramme for sammenligning. Menneskelig tenkning er basert på søk og analyse av motsetninger (konstruksjoner), så det er alltid lettere for oss å velge ett av to motsatte alternativer enn ett alternativ fra et stort og på ingen måte uordnet sett.

Dermed koker hovedantakelsene til dette språket ned til følgende:

et enkelt alternativ er ikke evaluert, dvs. kriteriefunksjonen er ikke introdusert;
for hvert par av alternativer kan det på en eller annen måte fastslås at ett av dem er å foretrekke fremfor det andre, eller at de er likeverdige eller uforlignelige;
preferanserelasjonen i et par av alternativer avhenger ikke av de andre alternativene som presenteres for valg.

Det er forskjellige måter å spesifisere binære relasjoner: direkte, matrise, bruk av preferansegrafer, metode for seksjoner, etc.

Relasjoner mellom alternativer av ett par uttrykkes gjennom begrepene ekvivalens, orden og dominans.

Generaliserte valgspråkfunksjoner

Valgspråkfunksjonene er basert på settteori og lar en operere med tilordninger av sett til deres delmengder som tilsvarer ulike valg uten behov for å telle opp elementer. Dette språket er veldig generelt og lar potensielt ethvert valg beskrives. Imidlertid blir det matematiske apparatet med generaliserte valgfunksjoner foreløpig kun utviklet og testet hovedsakelig på problemer som allerede er løst ved bruk av kriterier eller binære tilnærminger.

gruppevalg

La det være en gruppe mennesker som har rett til å ta del i kollektive beslutninger. Anta at denne gruppen vurderer et sett med alternativer, og hvert medlem av gruppen gjør sitt valg. Oppgaven er å utvikle en løsning som på en viss måte koordinerer individuelle valg og på en eller annen måte uttrykker gruppens «generelle mening», d.v.s. tatt som et gruppevalg.

Naturligvis vil ulike gruppevedtak tilsvare ulike prinsipper for samordning av enkeltvedtak.

Reglene for samordning av enkeltvedtak i et gruppevalg kalles stemmeregler. Den vanligste er «flertallsregelen», der gruppevedtaket tas av det alternativet som får flest stemmer.

Det må forstås at en slik beslutning bare gjenspeiler utbredelsen av forskjellige synspunkter i gruppen, og ikke et virkelig optimalt alternativ, som ingen kan stemme for i det hele tatt. "Sannheten bestemmes ikke ved å stemme."

I tillegg kommer såkalte «stemmeparadokser», hvor det mest kjente er Arrows paradoks.

Disse paradoksene kan føre, og noen ganger føre, til svært ubehagelige trekk ved avstemningsprosedyren: for eksempel er det tilfeller der gruppen ikke kan ta en enkelt beslutning i det hele tatt (det er ikke beslutningsdyktig eller alle stemmer for sitt eget unike alternativ osv. .), og noen ganger (i flertrinnsstemmegivning) kan minoriteten påtvinge flertallet sin vilje.

Valg under Usikkerhet

Sikkerhet er et spesielt tilfelle av usikkerhet, nemlig: det er en usikkerhet nær null.

I moderne valgteori antas det at det er tre hovedtyper av usikkerhet i beslutningsproblemer:

Informasjonsmessig (statistisk) usikkerhet av innledende data for beslutningstaking.
Usikkerhet om konsekvensene av beslutningstaking (valg).
Uklarhet i beskrivelsen av komponentene i beslutningsprosessen.

La oss vurdere dem i rekkefølge.

Informasjonsmessig (statistisk) usikkerhet i innledende data

Dataene innhentet om fagområdet kan ikke anses som absolutt nøyaktige. I tillegg er det åpenbart at disse dataene ikke er av interesse for oss i seg selv, men bare som signaler som kanskje bærer viss informasjon om hva vi egentlig er interessert i. Dermed er det mer realistisk å vurdere at vi har å gjøre med data som ikke bare er støyende og unøyaktige, men også indirekte, og muligens ufullstendige. I tillegg angår disse dataene ikke hele (generelle) populasjonen som studeres, men bare en viss undergruppe av den, som vi faktisk har kunnet samle inn data om, men samtidig ønsker vi å trekke konklusjoner om hele populasjonen, og vi ønsker også å vite graden av pålitelighet av disse konklusjonene.

Under disse forholdene brukes teorien om statistiske beslutninger.

Det er to hovedkilder til usikkerhet i denne teorien. For det første er det ikke kjent hvilken distribusjon de opprinnelige dataene adlyder. For det andre er det ikke kjent hvilken fordeling som har mengden (generelle populasjonen) som vi ønsker å trekke konklusjoner om fra undergruppen som danner de første dataene.

Statistiske prosedyrer er beslutningsprosedyrer som fjerner begge disse typer usikkerhet.

Det skal bemerkes at det er en rekke årsaker som fører til feil bruk av statistiske metoder:

statistiske slutninger, som alle andre, har alltid en viss pålitelighet eller sikkerhet. Men, i motsetning til mange andre tilfeller, er påliteligheten til statistiske funn kjent og bestemt i løpet av statistisk forskning;
kvaliteten på løsningen oppnådd som et resultat av bruk av den statistiske prosedyren avhenger av kvaliteten på de første dataene;
data som ikke har statistisk karakter bør ikke underkastes statistisk behandling;
det er nødvendig å bruke statistiske prosedyrer som tilsvarer nivået av a priori-informasjon om populasjonen som studeres (du bør for eksempel ikke bruke variansanalysemetoder på ikke-Gaussiske data). Hvis distribusjonen av de opprinnelige dataene er ukjent, må man enten etablere den, eller bruke flere ulike metoder og sammenligne resultatene. Hvis de er svært forskjellige, indikerer dette at noen av prosedyrene som brukes, ikke er anvendelige.

Usikkerhet om konsekvenser

Når konsekvensene av å velge et eller annet alternativ er unikt bestemt av alternativet i seg selv, så kan vi ikke skille mellom et alternativ og dets konsekvenser, og tar det for gitt at å velge et alternativ, vi velger faktisk konsekvensene.

Men i reell praksis må man ofte forholde seg til en mer kompleks situasjon, når valget av et eller annet alternativ tvetydig avgjør konsekvensene av valget som tas.

Ved et diskret sett med alternativer og utfall etter eget valg, forutsatt at settet med mulige utfall er felles for alle alternativer, kan vi anta at ulike alternativer skiller seg fra hverandre i fordelingen av utfallssannsynligheter. Disse sannsynlighetsfordelingene kan i det generelle tilfellet avhenge av resultatene av valg av alternativer og de utfallene som faktisk oppsto som følge av dette. I det enkleste tilfellet er utfallene like sannsynlige. Resultatene i seg selv har vanligvis betydningen av gevinster eller tap og er kvantifisert.

Hvis resultatene er like for alle alternativer, så er det ingenting å velge. Hvis de er forskjellige, kan alternativer sammenlignes ved å innføre visse kvantitative estimater for dem. Variasjonen av problemer i spillteori er forbundet med et annet valg av numeriske kjennetegn ved tap og gevinster som følge av valg av alternativer, ulik grad av konflikt mellom partene som velger alternativer mv.

Betrakt denne typen usikkerhet som vag usikkerhet

Ethvert valgproblem er en målinnsnevring av settet av alternativer. Både den formelle beskrivelsen av alternativer (selve listen deres, listen over deres attributter eller parametere) og beskrivelsen av reglene for deres sammenligning (kriterier, relasjoner) er alltid gitt i form av en eller annen måleskala (selv når den som vet ikke dette om dette).

Det er kjent at alle skalaer er uskarpe, men i varierende grad. Begrepet «blurring» refererer til vektens egenskap, som består i at det alltid er mulig å presentere to alternativer som kan skilles, dvs. forskjellig i en skala og ikke å skille, dvs. er identiske, i den andre - mer uskarpe. Jo færre graderinger i en bestemt skala, jo mer uskarp er den.

Dermed kan vi tydelig se alternativene og samtidig vagt klassifisere dem, d.v.s. være tvetydig med hensyn til hvilke klasser de tilhører.

Allerede i deres første arbeid med beslutningstaking i en uklar situasjon, fremmet Bellman og Zadeh ideen om at både mål og begrensninger skulle representeres som uklare (fuzzy) sett på et sett med alternativer.

Om noen begrensninger ved optimaliseringstilnærmingen

I alle utvelgelsesproblemene og beslutningsmetodene vurdert ovenfor, var problemet å finne de beste i det innledende settet under gitte forhold, dvs. optimale alternativer i en viss forstand.

Ideen om optimalitet er den sentrale ideen om kybernetikk og har gått inn i praksisen med å designe og betjene tekniske systemer. Samtidig må denne ideen behandles med forsiktighet når vi prøver å overføre den til området for å administrere komplekse, store og svakt bestemte systemer, som for eksempel sosioøkonomiske systemer.

Det er gode grunner for denne konklusjonen. La oss vurdere noen av dem:

Den optimale løsningen viser seg ofte å være ustabil, d.v.s. mindre endringer i problemforholdene, inndata eller begrensninger kan føre til valg av vesentlig forskjellige alternativer.
Optimaliseringsmodeller er utviklet kun for smale klasser av ganske enkle oppgaver som ikke alltid reflekterer adekvat og systematisk reelle kontrollobjekter. Oftest gjør optimeringsmetoder det mulig å optimalisere kun ganske enkle og velformelt beskrevne delsystemer av noen store og komplekse systemer, dvs. tillate kun lokal optimalisering. Men hvis hvert delsystem av et eller annet stort system fungerer optimalt, betyr ikke dette i det hele tatt at systemet som helhet også vil fungere optimalt. Derfor fører optimering av et delsystem ikke nødvendigvis til dets oppførsel, som kreves av det når man optimaliserer systemet som helhet. Noen ganger kan dessuten lokal optimalisering føre til negative konsekvenser for systemet som helhet. Derfor, når du optimaliserer delsystemer og systemet som helhet, er det nødvendig å bestemme treet av mål og delmål og deres prioritet.
Ofte anses å maksimere optimaliseringskriteriet i henhold til en matematisk modell for å være målet for optimalisering, men i realiteten er målet å optimalisere kontrollobjektet. Optimaliseringskriterier og matematiske modeller er alltid relatert til målet kun indirekte, dvs. mer eller mindre tilstrekkelig, men alltid omtrentlig.

Derfor må ideen om optimalitet, som er ekstremt fruktbar for systemer som egner seg til tilstrekkelig matematisk formalisering, overføres til komplekse systemer med forsiktighet. Selvfølgelig kan matematiske modeller som noen ganger kan foreslås for slike systemer optimaliseres. Man bør imidlertid alltid ta hensyn til den sterke forenklingen av disse modellene, som i tilfelle av komplekse systemer ikke lenger kan neglisjeres, samt det faktum at graden av tilstrekkelighet til disse modellene i tilfelle av komplekse systemer faktisk er ukjent. . Derfor er det ikke kjent hvilken rent praktisk betydning denne optimaliseringen har. Den høye praktiske optimeringen i tekniske systemer bør ikke gi opphav til illusjonen om at det vil være like effektivt for å optimalisere komplekse systemer. Meningsfull matematisk modellering av komplekse systemer er svært vanskelig, omtrentlig og unøyaktig. Jo mer komplekst systemet er, desto mer forsiktig bør man være med ideen om optimalisering.

Derfor, når de utvikler kontrollmetoder for komplekse, store, svakt bestemte systemer, vurderer forfatterne det viktigste ikke bare optimaliteten til den valgte tilnærmingen fra et formelt matematisk synspunkt, men også dens tilstrekkelighet til målet og selve naturen til den valgte tilnærmingen. kontrollobjekt.

Ekspertvalgsmetoder

I studiet av komplekse systemer oppstår det ofte problemer som av ulike årsaker ikke kan stilles og løses strengt ved hjelp av det nå utviklede matematiske apparatet. I disse tilfellene brukes tjenestene til eksperter (systemanalytikere), hvis erfaring og intuisjon bidrar til å redusere kompleksiteten til problemet.

Det må imidlertid tas i betraktning at eksperter selv er svært komplekse systemer, og deres aktiviteter avhenger også av mange ytre og interne forhold. Derfor, i metodene for å organisere ekspertvurderinger, legges det stor vekt på å skape gunstige ytre og psykologiske forhold for eksperters arbeid.

Følgende faktorer påvirker arbeidet til en ekspert:

ansvar for bruken av resultatene fra eksamen;
å vite at andre eksperter er involvert;
tilgjengelighet av informasjon kontakt mellom eksperter;
mellommenneskelige forhold til eksperter (hvis det er informasjonskontakt mellom dem);
ekspertens personlige interesse i resultatene av vurderingen;
eksperters personlige egenskaper (selvtillit, konformitet, vilje osv.)

Interaksjon mellom eksperter kan enten stimulere eller hemme deres aktivitet. Derfor, i forskjellige tilfeller, brukes forskjellige undersøkelsesmetoder, som er forskjellige i arten av eksperters interaksjon med hverandre: anonyme og åpne undersøkelser og spørreskjemaer, møter, diskusjoner, forretningsspill, idédugnad, etc.

Det finnes ulike metoder for matematisk behandling av ekspertuttalelser. Eksperter blir bedt om å vurdere ulike alternativer enten ved ett eller et system av indikatorer. I tillegg blir de bedt om å vurdere graden av viktighet for hver indikator (dens "vekt" eller "bidrag"). Ekspertene selv er også tildelt et kompetansenivå som tilsvarer bidraget fra hver av dem til gruppens resulterende mening.

En utviklet metode for å jobbe med eksperter er "Delphi"-metoden. Hovedideen med denne metoden er at kritikk og argumentasjon har en gunstig effekt på eksperten, hvis hans selvtillit ikke påvirkes og det er gitt forhold som utelukker personlig konfrontasjon.

Det skal understrekes at det er en grunnleggende forskjell i karakteren av bruken av ekspertmetoder i ekspertsystemer og i beslutningsstøtte. Hvis eksperter i det første tilfellet er pålagt å formalisere metodene for beslutningstaking, så i det andre - bare selve beslutningen som sådan.

Siden eksperter er involvert i implementeringen av nettopp de funksjonene som for øyeblikket enten ikke leveres av automatiserte systemer i det hele tatt, eller utføres dårligere enn av mennesker, er en lovende retning i utviklingen av automatiserte systemer maksimal automatisering av disse funksjonene.

Automatiserte beslutningsstøttesystemer

En person har alltid brukt assistenter til å ta beslutninger: de var både rett og slett leverandører av informasjon om kontrollobjektet, og konsulenter (rådgivere) som tilbyr valgmuligheter og analyserer konsekvensene av dem. Personen som tok beslutninger tok dem alltid i et bestemt informasjonsmiljø: for en militær sjef er dette hovedkvarteret, for rektor, det akademiske rådet, for ministeren, kollegiet.

I vår tid er beslututenkelig uten automatiserte systemer for iterativ beslutningsevaluering og spesielt beslutningsstøttesystemer (DDS – Decision Support Systems), dvs. automatiserte systemer som er spesielt utviklet for å forberede informasjonen en person trenger for å ta en beslutning. Utviklingen av beslutningsstøttesystemer utføres særlig innenfor rammen av et internasjonalt prosjekt utført i regi av International Institute for Applied Systems Analysis i Laxenburg (Østerrike).

Valget i virkelige situasjoner krever utførelse av en rekke operasjoner, hvorav noen utføres mer effektivt av en person, og andre av en maskin. Effektiv kombinasjon av fordelene deres med samtidig kompensasjon av mangler er nedfelt i automatiserte beslutningsstøttesystemer.

En person tar beslutninger bedre enn en maskin under forhold med usikkerhet, men for å ta den riktige avgjørelsen trenger han også tilstrekkelig (fullstendig og pålitelig) informasjon som karakteriserer fagområdet. Det er imidlertid kjent at en person ikke takler store mengder «rå» ubehandlet informasjon. Derfor kan maskinens rolle i beslutningsstøtte være å utføre foreløpig forberedelse av informasjon om kontrollobjektet og ukontrollerbare faktorer (miljø), for å hjelpe til med å se konsekvensene av å ta bestemte beslutninger, og også å presentere all denne informasjonen i en visuell og praktisk måte å ta beslutninger på.

Dermed kompenserer automatiserte beslutningsstøttesystemer for svakhetene til en person, frigjør ham fra den rutinemessige foreløpige behandlingen av informasjon, og gir ham et komfortabelt informasjonsmiljø der han bedre kan vise sine styrker. Disse systemene er ikke fokusert på å automatisere funksjonene til beslutningstakeren (og som et resultat fremmedgjøre disse funksjonene fra ham, og dermed ansvaret for beslutningene som tas, noe som ofte er generelt uakseptabelt), men på å gi ham hjelp til å finne en god løsning.

opplæringen

Jeg har lenge ønsket å skrive en generell artikkel som inneholder det helt grunnleggende om bildegjenkjenning, en slags veiledning om grunnleggende metoder, som forteller når de skal brukes, hvilke oppgaver de løser, hva som kan gjøres om kvelden på kneet, og hva er bedre å ikke tenke på uten å ha et team med mennesker på 20.

Jeg har skrevet noen artikler om optisk gjenkjenning i lang tid, så et par ganger i måneden skriver forskjellige personer til meg med spørsmål om dette emnet. Noen ganger får du følelsen av at du lever med dem i forskjellige verdener. På den ene siden forstår du at en person mest sannsynlig er en profesjonell innen et relatert emne, men vet veldig lite om optiske gjenkjenningsmetoder. Og det mest irriterende er at han prøver å bruke en metode fra et nærliggende kunnskapsfelt, som er logisk, men som ikke fungerer helt i bildegjenkjenning, men forstår ikke dette og blir veldig fornærmet hvis han begynner å fortelle ham noe fra veldig grunnleggende. Og med tanke på at det å fortelle fra det grunnleggende er mye tid, som ofte ikke er der, blir det enda tristere.

Denne artikkelen er laget slik at en person som aldri har beskjeftiget seg med bildegjenkjenningsmetoder, i løpet av 10-15 minutter kan skape i hodet sitt et visst grunnbilde av verden tilsvarende temaet, og forstå i hvilken retning han skal grave. Mange av metodene beskrevet her er anvendelige for radar- og lydbehandling.
Jeg starter med et par prinsipper som vi alltid begynner å fortelle en potensiell kunde, eller en person som ønsker å begynne med optisk gjenkjenning:

Når du løser et problem, gå alltid fra det enkleste. Det er mye lettere å henge en oransje etikett på en person enn å følge en person og fremheve ham i kaskader. Det er mye lettere å ta et kamera med høyere oppløsning enn å utvikle en superoppløsningsalgoritme.
En streng problemstilling i optiske gjenkjenningsmetoder er størrelsesordener viktigere enn i systemprogrammeringsproblemer: ett ekstra ord i TK kan legge til 50 % av arbeidet.
I gjenkjennelsesproblemer er det ingen universelle løsninger. Du kan ikke lage en algoritme som bare "gjenkjenner enhver inskripsjon." Et skilt på gaten og et tekstark er fundamentalt forskjellige objekter. Det er nok mulig å lage en generell algoritme (et godt eksempel fra Google), men dette vil kreve mye arbeid fra et stort team og bestå av dusinvis av ulike subrutiner.
OpenCV er bibelen, som har mange metoder, og som du kan løse 50% av volumet av nesten ethvert problem med, men OpenCV er bare en liten del av det som kan gjøres i virkeligheten. I en studie ble det skrevet i konklusjonene: "Problemet er ikke løst med OpenCV-metoder, derfor er det uløselig." Prøv å unngå dette, ikke vær lat og nøkternt evaluer gjeldende oppgave hver gang fra bunnen av, uten å bruke OpenCV-maler.

Det er veldig vanskelig å gi noen form for universelle råd, eller fortelle hvordan man kan lage en slags struktur som man kan bygge en løsning på vilkårlige problemer med datasyn. Hensikten med denne artikkelen er å strukturere hva som kan brukes. Jeg vil prøve å dele de eksisterende metodene inn i tre grupper. Den første gruppen er forhåndsfiltrering og bildeforberedelse. Den andre gruppen er den logiske behandlingen av filtreringsresultatene. Den tredje gruppen er beslutningsalgoritmer basert på logisk prosessering. Grensene mellom grupper er veldig vilkårlige. For å løse et problem er det langt fra alltid nødvendig å bruke metoder fra alle grupper, noen ganger er to nok, og noen ganger til og med én.

Listen over metoder som presenteres her er ikke fullstendig. Jeg foreslår å legge til kritiske metoder som jeg ikke skrev i kommentarene, og tilskrive 2-3 medfølgende ord til hver.

Del 1. Filtrering

I denne gruppen plasserte jeg metoder som lar deg velge interesseområder i bilder uten å analysere dem. De fleste av disse metodene bruker en slags enhetlig transformasjon på alle punkter i bildet. På filtreringsnivå analyseres ikke bildet, men punktene som filtreres kan betraktes som områder med spesielle egenskaper.

Terskelbinarisering, valg av histogramområde

Den enkleste transformasjonen er binariseringen av bildet etter terskelen. For RGB- og gråtonebilder er terskelen fargeverdien. Det er ideelle problemer der en slik transformasjon er tilstrekkelig. Anta at du automatisk vil velge elementer på et hvitt ark:

Valget av terskelen som binarisering finner sted ved, bestemmer i stor grad selve binariseringsprosessen. I dette tilfellet ble bildet binarisert av gjennomsnittsfargen. Vanligvis gjøres binarisering med en algoritme som adaptivt velger en terskel. En slik algoritme kan være valget av forventning eller modus. Og du kan velge den største toppen av histogrammet.

Binarisering kan gi svært interessante resultater når du arbeider med histogrammer, inkludert situasjonen hvis vi vurderer et bilde ikke i RGB, men i HSV. Segmenter for eksempel fargene av interesse. På dette prinsippet er det mulig å bygge både en etikettdetektor og en human huddetektor.

Klassisk filtrering: Fourier, LPF, HPF

Klassiske filtreringsmetoder fra radar og signalbehandling kan med hell brukes i en rekke mønstergjenkjenningsoppgaver. Den tradisjonelle metoden innen radar, som nesten aldri brukes i bilder i sin rene form, er Fourier-transformasjonen (nærmere bestemt FFT). Et av de få unntakene der 1D Fourier-transformasjonen brukes er bildekomprimering. For bildeanalyse er en endimensjonal transformasjon vanligvis ikke nok, du må bruke en mye mer ressurskrevende todimensjonal transformasjon.

Det er få som faktisk beregner det, vanligvis er det mye raskere og enklere å bruke konvolusjonen til området av interesse med et ferdig filter skarpt til høye (HPF) eller lave (LPF) frekvenser. En slik metode tillater selvfølgelig ikke spektrumanalyse, men i en spesifikk videobehandlingsoppgave er det vanligvis ikke en analyse som trengs, men et resultat.

De enkleste eksemplene på filtre som legger vekt på lave frekvenser (Gaussisk filter) og høye frekvenser (Gabor-filter).
For hvert bildepunkt velges et vindu og multipliseres med et filter av samme størrelse. Resultatet av en slik konvolusjon er den nye verdien av punktet. Når du implementerer LPF og HPF, oppnås bilder av denne typen:

Wavelets

Men hva om vi bruker en vilkårlig karakteristisk funksjon for konvolusjon med signalet? Da vil den hete "Wvelet Transform". Denne definisjonen av wavelets er ikke korrekt, men tradisjonelt, i mange team, er wavelet-analyse søket etter et vilkårlig mønster i et bilde ved å bruke konvolusjon med en modell av dette mønsteret. Det er et sett med klassiske funksjoner som brukes i wavelet-analyse. Disse inkluderer Haar wavelet, Morlet wavelet, den meksikanske hatt wavelet, og så videre. Haar primitiver, som det var flere av mine tidligere artikler om ( , ), viser til slike funksjoner for et todimensjonalt rom.

Over er 4 eksempler på klassiske wavelets. 3D Haar wavelet, 2D Meyer wavelet, Mexican Hat wavelet, Daubechies wavelet. Et godt eksempel på bruk av den utvidede tolkningen av wavelets er problemet med å finne et glimt i øyet, som selve glimtet er en wavelet for:

Klassiske wavelets brukes vanligvis for , eller for deres klassifisering (som skal beskrives nedenfor).

Sammenheng

Etter en slik fri tolkning av wavelets fra min side, er det verdt å nevne den faktiske korrelasjonen som ligger til grunn for dem. Ved filtrering av bilder er dette et uunnværlig verktøy. En klassisk applikasjon er videostrømkorrelasjon for å finne forskyvninger eller optiske strømmer. Den enkleste skiftdetektoren er også på en måte en forskjellskorrelator. Der bildene ikke samsvarer, var det bevegelse.

Funksjonsfiltrering

En interessant klasse med filtre er filtreringsfunksjoner. Dette er rent matematiske filtre som lar deg oppdage en enkel matematisk funksjon i et bilde (linje, parabel, sirkel). Det bygges et akkumulert bilde, der for hvert punkt i originalbildet tegnes et sett med funksjoner som genererer det. Den mest klassiske transformasjonen er Hough-transformasjonen for linjer. I denne transformasjonen, for hvert punkt (x;y), tegnes et sett med punkter (a;b) på linjen y=ax+b, for hvilke likhet er sann. Få vakre bilder:

(det første pluss for den som er den første til å finne en fangst i bildet og en slik definisjon og forklare det, det andre pluss for den som er den første til å si det som vises her)
Hough-transformasjonen lar deg finne alle parameteriserbare funksjoner. For eksempel sirkler. Det er en modifisert transformasjon som lar deg søke etter hvilken som helst . Denne transformasjonen er fryktelig glad i matematikere. Men når du behandler bilder, fungerer det dessverre ikke alltid. Veldig lav hastighet, veldig høy følsomhet for kvaliteten på binarisering. Selv i ideelle situasjoner foretrakk jeg å klare meg med andre metoder.
Motstykket til Hough-transformasjonen for linjer er Radon-transformasjonen. Det beregnes gjennom FFT, som gir en ytelsesgevinst i en situasjon hvor det er mange poeng. I tillegg kan den brukes på et ikke-binarisert bilde.

Konturfiltrering

En egen klasse med filtre er kant- og konturfiltrering. Baner er veldig nyttige når vi ønsker å gå fra å jobbe med et bilde til å jobbe med objekter i det bildet. Når et objekt er ganske komplekst, men godt utpekt, er ofte den eneste måten å jobbe med det på å velge konturene. Det finnes en rekke algoritmer som løser problemet med konturfiltrering:

Den mest brukte er Kenny, som fungerer bra og hvis implementering er i OpenCV (Sobel er også der, men han ser etter konturer dårligere).

Andre filtre

Over er filtre, modifikasjoner som bidrar til å løse 80-90% av oppgavene. Men i tillegg til dem er det mer sjeldne filtre som brukes i lokale oppgaver. Det er dusinvis av slike filtre, jeg vil ikke liste dem alle. Av interesse er iterative filtre (for eksempel ), samt ridgelet- og curvlet-transformasjoner, som er en legering av klassisk wavelet-filtrering og analyse i radontransformasjonsfeltet. Beamlet-transformasjon fungerer vakkert på grensen til wavelet-transformasjon og logisk analyse, slik at du kan fremheve konturene:

Men disse transformasjonene er veldig spesifikke og skreddersydd for sjeldne oppgaver.

Del 2. Logisk behandling av filtreringsresultater

Filtrering gir et sett med data som er egnet for behandling. Men ofte kan du ikke bare ta og bruke disse dataene uten å behandle dem. I denne delen vil det være flere klassiske metoder som lar deg gå fra bildet til egenskapene til objekter, eller til selve objektene.

Morfologi

Overgangen fra filtrering til logikk er etter min mening metodene for matematisk morfologi ( , ). Faktisk er dette de enkleste operasjonene for å øke og erodere binære bilder. Disse metodene lar deg fjerne støy fra et binært bilde ved å øke eller redusere de tilgjengelige elementene. Basert på matematisk morfologi finnes det konturalgoritmer, men vanligvis bruker de en slags hybridalgoritmer eller algoritmer i kombinasjon.

konturanalyse

I avsnittet om filtrering er algoritmer for å oppnå grenser allerede nevnt. De resulterende grensene blir ganske enkelt omgjort til konturer. For Canny-algoritmen skjer dette automatisk, for andre algoritmer kreves ytterligere binarisering. Du kan få en kontur for en binær algoritme, for eksempel med billealgoritmen.
Konturen er en unik egenskap ved et objekt. Ofte lar dette deg identifisere objektet langs konturen. Det er et kraftig matematisk apparat som lar deg gjøre dette. Apparatet kalles konturanalyse ( , ).

For å være ærlig har jeg aldri klart å bruke konturanalyse i reelle problemer. Det kreves for ideelle forhold. Enten er det ingen grense, eller så er det for mye støy. Men hvis du trenger å gjenkjenne noe under ideelle forhold, er konturanalyse et flott alternativ. Det fungerer veldig raskt, vakker matematikk og forståelig logikk.

Enkeltpunkter

Nøkkelpunkter er unike egenskaper ved et objekt som gjør at objektet kan assosieres med seg selv eller med lignende objektklasser. Det er dusinvis av måter å velge slike punkter på. Noen metoder fremhever spesielle punkter i nærliggende rammer, noen etter lang tid og når belysningen endres, noen lar deg finne spesielle punkter som forblir slik selv når objektet roterer. La oss starte med metoder som lar oss finne spesielle punkter som ikke er så stabile, men som raskt beregnes, og så vil vi gå i økende kompleksitet:
Første klasse. Enkeltpunkter som er stabile i sekunder. Slike punkter brukes til å lede et objekt mellom tilstøtende videobilder, eller for å konvergere bilder fra nabokameraer. Disse punktene inkluderer lokale maksima for bildet, hjørner i bildet (den beste av detektorene, kanskje Haris-detektoren), punkter der spredningsmaksima nås, visse gradienter, etc.
Andre klasse. Enkelte punkter som er stabile ved skifte av belysning og små bevegelser av objektet. Slike punkter tjener først og fremst til opplæring og etterfølgende klassifisering av objekttyper. For eksempel er en fotgjengerklassifiserer eller en ansiktsklassifiser produktet av et system bygget på nettopp slike punkter. Noen av de tidligere nevnte wavelets kan være grunnlaget for slike punkter. For eksempel Haar primitiver, blendesøk, søk etter andre spesifikke funksjoner. Disse punktene inkluderer punkter funnet ved metoden for histogrammer av retningsgradienter (HOG).
Tredje klasse. stabile punkter. Jeg vet bare om to metoder som gir fullstendig stabilitet og om deres modifikasjoner. Dette og . De lar deg finne nøkkelpunkter selv når du roterer bildet. Beregningen av slike poeng tar lengre tid enn andre metoder, men i en ganske begrenset tid. Dessverre er disse metodene patentert. Selv om det i Russland er umulig å patentere algoritmer, så bruk det for hjemmemarkedet.

Del 3. Opplæring

Den tredje delen av historien vil være viet metoder som ikke fungerer direkte med bildet, men som lar deg ta avgjørelser. I utgangspunktet er dette ulike metoder for maskinlæring og beslutningstaking. Nylig postet Yandyks på Habr om dette emnet, det er et veldig godt utvalg. Her er den i tekstversjon. For en seriøs studie av emnet, anbefaler jeg sterkt at du ser på dem. Her vil jeg prøve å identifisere flere grunnleggende metoder som brukes spesifikt i mønstergjenkjenning.
I 80 % av situasjonene er essensen av læring i gjenkjenningsproblemet som følger:
Det er en testprøve hvor det er flere klasser av objekter. La det være tilstedeværelsen / fraværet av en person på bildet. For hvert bilde er det et sett med funksjoner som har blitt fremhevet av en funksjon, enten det er Haar, HOG, SURF eller en wavelet. Læringsalgoritmen må bygge en slik modell, etter hvilken den skal kunne analysere det nye bildet og bestemme hvilke av objektene som er på bildet.
Hvordan gjøres det? Hvert av testbildene er et punkt i funksjonsrommet. Koordinatene er vekten av hver funksjon i bildet. La våre tegn være: "Tilstedeværelsen av øyne", "Tilstedeværelsen av en nese", "Tilstedeværelsen av to hender", "Tilstedeværelsen av ører", etc. Vi vil tildele alle disse tegnene med detektorene vi har, som er trent på kroppsdeler som ligner på mennesker. For en person i et slikt rom vil det riktige punktet være . For apen, prikk for hesten. Klassifisereren er trent på et utvalg eksempler. Men ikke alle fotografiene viste hender, andre hadde ingen øyne, og i det tredje hadde apen en menneskenese på grunn av en klassifiseringsfeil. Den trenbare menneskelige klassifisereren deler automatisk funksjonsrommet på en slik måte at det sier: hvis den første funksjonen ligger i området 0,5 I hovedsak er formålet med klassifikatoren å tegne i funksjonsrommet områdene som er karakteristiske for klassifiseringsobjektene. Slik vil den suksessive tilnærmingen til svaret for en av klassifisørene (AdaBoost) i todimensjonalt rom se ut:

Det er mange klassifiserere. Hver av dem fungerer bedre i noen av sine oppgaver. Oppgaven med å velge en klassifiserer for en spesifikk oppgave er i stor grad en kunst. Her er noen fine bilder om temaet.

Enkel sak, endimensjonal separasjon

La oss ta et eksempel på det enkleste tilfellet med klassifisering, når funksjonsrommet er endimensjonalt, og vi må skille to klasser. Situasjonen oppstår oftere enn det kan virke: for eksempel når du trenger å skille mellom to signaler, eller sammenligne et mønster med en prøve. La oss si at vi har en treningsprøve. I dette tilfellet oppnås et bilde, hvor X-aksen vil være et mål på likhet, og Y-aksen vil være antall hendelser med et slikt mål. Når ønsket objekt ligner seg selv, oppnås en venstre gaussisk. Når ikke lik - ikke sant. Verdien X=0,4 skiller prøvene slik at en feilaktig avgjørelse minimerer sannsynligheten for å ta feil avgjørelse. Det er søket etter en slik separator som er klassifiseringsoppgaven.

Lite notat. Kriteriet som minimerer feilen vil ikke alltid være optimalt. Følgende graf er en graf over et faktisk irisgjenkjenningssystem. For et slikt system er kriteriet valgt på en slik måte at det minimerer sannsynligheten for falsk innrømmelse av en utenforstående til objektet. En slik sannsynlighet kalles "feil av den første typen", "sannsynlighet for falsk alarm", "falsk positiv". I engelsk litteratur "False Access Rate".
) AdaBusta er en av de vanligste klassifikatorene. For eksempel er Haar-kaskaden bygget på den. Brukes vanligvis når binær klassifisering er nødvendig, men ingenting hindrer undervisning i flere klasser.
SVM ( , , , ) En av de kraftigste klassifisere med mange implementeringer. I prinsippet, på læringsoppgavene jeg møtte, fungerte det på samme måte som adabusta. Det anses som ganske raskt, men treningen er vanskeligere enn Adabusta og krever valg av riktig kjerne.

Det er også nevrale nettverk og regresjon. Men for å kort klassifisere dem og vise hvordan de skiller seg ut, trengs en artikkel som er mye større enn dette.
________________________________________________
Jeg håper jeg klarte å gi en rask oversikt over metodene som ble brukt uten å dykke ned i matematikk og beskrivelse. Kanskje dette vil hjelpe noen. Selv om artikkelen selvfølgelig er ufullstendig og det er ikke et ord om å jobbe med stereobilder, eller om LSM med Kalman-filteret, eller om den adaptive Bayesianske tilnærmingen.
Hvis du liker artikkelen, så vil jeg prøve å lage den andre delen med et utvalg eksempler på hvordan eksisterende ImageRecognition-problemer løses.

Og endelig

Hva skal man lese?
1) En gang likte jeg veldig godt boken "Digital Image Processing" av B. Yana, som er skrevet enkelt og tydelig, men samtidig er nesten all matematikk gitt. Bra for å bli kjent med eksisterende metoder.
2) Klassikeren i sjangeren er R Gonzalez, R. Woods "Digital Image Processing". Av en eller annen grunn var det vanskeligere for meg enn den første. Mye mindre matematikk, men mer metoder og bilder.
3) "Bildebehandling og analyse i maskinsynsproblemer" - skrevet på grunnlag av et kurs undervist ved en av avdelingene til PhysTech. Mange metoder og deres detaljerte beskrivelse. Men etter min mening har boken to store minuser: boken er sterkt fokusert på programvarepakken som følger med, i boken blir beskrivelsen av en enkel metode for ofte til en matematisk jungel, som den er vanskelig å ta ut av. strukturdiagrammet for metoden. Men forfatterne har laget et praktisk nettsted, der nesten alt innholdet presenteres - wiki.technicalvision.ru Legg til tagger

Iterasjonsmetode. I denne metoden er det gjort en sammenligning med en bestemt database, hvor det for hvert av objektene er forskjellige alternativer for å endre visningen. For eksempel, for optisk bildegjenkjenning, kan du bruke iterasjonsmetoden i forskjellige vinkler eller skalaer, forskyvninger, deformasjoner osv. For bokstaver kan du iterere over fonten eller dens egenskaper. Når det gjelder lydmønstergjenkjenning, er det en sammenligning med noen kjente mønstre (et ord som snakkes av mange mennesker). Videre utføres en dypere analyse av egenskapene til bildet. Ved optisk gjenkjenning kan dette være definisjonen av geometriske egenskaper. Lydprøven i dette tilfellet blir utsatt for frekvens- og amplitudeanalyse.

Den neste metoden er bruk av kunstige nevrale nettverk(INS). Det krever enten et stort antall eksempler på gjenkjenningsoppgaven, eller en spesiell nevrale nettverksstruktur som tar hensyn til detaljene ved denne oppgaven. Men ikke desto mindre er denne metoden preget av høy effektivitet og produktivitet.

Metoder basert på estimater av fordelingstetthetene til funksjonsverdier. Lånt fra den klassiske teorien om statistiske beslutninger, der studieobjektene betraktes som realiseringer av en flerdimensjonal tilfeldig variabel fordelt i funksjonsrommet i henhold til en lov. De er basert på det Bayesianske beslutningsskjemaet, som appellerer til de opprinnelige sannsynlighetene for objekter som tilhører en bestemt klasse og betingede funksjonsfordelingstettheter.

Gruppen av metoder basert på estimering av fordelingstetthetene til funksjonsverdier er direkte relatert til metodene for diskriminant analyse. Den Bayesianske tilnærmingen til beslutningstaking er en av de mest utviklede parametriske metodene i moderne statistikk, der det analytiske uttrykket av distribusjonsloven (normalloven) anses å være kjent og bare et lite antall parametere (gjennomsnittsvektorer og kovariansmatriser) ) må estimeres. Hovedvanskene ved å bruke denne metoden anses å være behovet for å huske hele treningsutvalget for å beregne tetthetsestimater og høy følsomhet for treningsutvalget.

Metoder basert på antakelser om klassen av beslutningsfunksjoner. I denne gruppen anses typen beslutningsfunksjon som kjent og dens funksjonelle kvalitet er gitt. Basert på denne funksjonen finner man den optimale tilnærmingen til beslutningsfunksjonen fra treningssekvensen. Beser vanligvis forbundet med en feil. Hovedfordelen med metoden er klarheten i den matematiske formuleringen av gjenkjenningsproblemet. Muligheten for å trekke ut ny kunnskap om et objekts natur, spesielt kunnskap om mekanismene for interaksjon av attributter, er her fundamentalt begrenset av en gitt struktur for interaksjon, festet i den valgte formen for beslutningsfunksjoner.

Prototype sammenligningsmetode. Dette er den enkleste utvidelsesgjenkjenningsmetoden i praksis. Det gjelder når de gjenkjennelige klassene vises som kompakte geometriske klasser. Deretter velges midten av den geometriske grupperingen (eller objektet nærmest sentrum) som prototypepunkt.

For å klassifisere et ubestemt objekt, blir prototypen nærmest funnet, og objektet tilhører samme klasse som det. Det dannes åpenbart ingen generaliserte bilder i denne metoden. Ulike typer avstander kan brukes som mål.

Metode for k nærmeste naboer. Metoden ligger i det faktum at når man klassifiserer et ukjent objekt, finner man et gitt antall (k) av geometrisk nærmeste trekkrom av andre nærmeste naboer med allerede kjent tilhørighet til en klasse. Beslutningen om å tildele et ukjent objekt tas ved å analysere informasjon om dets nærmeste naboer. Behovet for å redusere antall objekter i treningsutvalget (diagnostiske presedenser) er en ulempe ved denne metoden, siden dette reduserer representativiteten til treningsutvalget.

Basert på det faktum at ulike gjenkjenningsalgoritmer oppfører seg forskjellig på samme prøve, oppstår spørsmålet om en syntetisk beslutningsregel som vil bruke styrken til alle algoritmer. For dette er det en syntetisk metode eller sett med beslutningsregler som kombinerer de mest positive aspektene ved hver av metodene.

Som konklusjon av gjennomgangen av anerkjennelsesmetoder presenterer vi essensen av ovenstående i en sammendragstabell, og legger til noen andre metoder som brukes i praksis.

Tabell 1. Klassifikasjonstabell over gjenkjennelsesmetoder, sammenligning av deres bruksområder og begrensninger

Klassifisering av gjenkjennelsesmetoder	Bruksområde	Begrensninger (ulemper)
Intensive gjenkjenningsmetoder	Metoder basert på tetthetsestimater	Problemer med kjent fordeling (normal), behov for å samle inn store statistikker	Behovet for å telle opp hele treningssettet under gjenkjennelse, høy følsomhet for ikke-representativitet av treningssettet og artefakter
Forutsetningsbaserte metoder	Klassene bør være godt atskilt	Vedtaksfunksjonens form skal være kjent på forhånd. Umuligheten av å ta hensyn til ny kunnskap om sammenhenger mellom funksjoner
boolske metoder	Problemer av liten dimensjon	Når du velger logiske beslutningsregler, er en fullstendig oppregning nødvendig. Høy arbeidsintensitet
Språklige metoder		Oppgaven med å bestemme grammatikken for et bestemt sett med utsagn (beskrivelser av objekter) er vanskelig å formalisere. Uløste teoretiske problemer
Utvidede metoder for anerkjennelse	Prototype sammenligningsmetode	Problemer med liten dimensjon av funksjonsplass	Høy avhengighet av klassifiseringsresultater på metrikken. Ukjent optimal beregning
k nærmeste nabo metode		Høy avhengighet av klassifiseringsresultater på metrikken. Behovet for en fullstendig oppregning av treningsutvalget under anerkjennelse. Beregningsmessig kompleksitet
Algoritmer for karakterberegning (ABO)	Problemer med liten dimensjon når det gjelder antall klasser og funksjoner	Avhengighet av klassifiseringsresultater på metrikken. Behovet for en fullstendig oppregning av treningsutvalget under anerkjennelse. Høy teknisk kompleksitet av metoden
Kollektive beslutningsregler (CRC) er en syntetisk metode.	Problemer med liten dimensjon når det gjelder antall klasser og funksjoner	Svært høy teknisk kompleksitet av metoden, det uløste antallet teoretiske problemer, både når det gjelder å bestemme kompetanseområdene til bestemte metoder, og i de spesielle metodene i seg selv