Az Ulf Grenander által megfogalmazott mintaelmélet egy olyan matematikai formalizmus, amely a világról ismert tudást mintaként írja le. Abban különbözik a mesterséges intelligencia más megközelítéseitől, hogy nem a minták felismerésére és osztályozására szolgáló algoritmusok és gépek előírásával kezd, hanem egy olyan szókincset ír elő, amellyel a mintaképek fogalmait pontos nyelven lehet meg -és újrafogalmazni. Matematikai lefedettségét tekintve a mintaelmélet kiterjed az algebrára és a statisztikára, valamint a helyi topológiai és globális entropikus tulajdonságokra.
Az új algebrai szókincs mellett a statisztikai megközelítés újszerű célja, hogy:
Valós adatok felhasználásával azonosítsa az adathalmaz rejtett változóit, nem pedig mesterséges ingerek segítségével, ami korábban megszokott volt. Megfogalmazza a rejtett változók és a megfigyelt változók modelljeinek előzetes eloszlásait, amelyek egy Gibbs-szerű gráf csúcsait alkotják. Tanulmányozza e gráfok véletlenszerűségét és változékonyságát. Hozza létre a minták deformációinak felsorolásával az alkalmazott sztochasztikus modellek alapvető osztályait. Szintetizáljon (mintázzon) a modellekből, ne csak jeleket elemezzen velük.
A Brown Egyetem mintaelméleti csoportját 1972-ben Ulf Grenander alapította. Jelenleg számos matematikus dolgozik ebben a csoportban, köztük kiemelkedik a Fields-érmes David Mumford. Mumford Grenandert tekinti "gurujának" a mintaelmélet területén.
Példa: Természetes nyelvtan jobbra|bélyegkép|220x220px| Nyelvtani automata jobbra|keretezett| Nyelvtangenerátorok Egy példával kezdjük, hogy szemléltessük a következő algebrai definíciókat. Ha nyelvi mintákat akarunk reprezentálni, akkor a legközvetlenebb jelöltek a primitívek közül a szavak lehetnek. Azonban a gyakorta használt mondatok, mint például az "annak érdekében, hogy", azonnal jelzik a szavak mint atomok alkalmatlanságát. Más primitívek keresése során megpróbálkozhatunk a nyelvtani szabályokkal. A nyelvtanokat ábrázolhatjuk véges állapotú automatákként vagy kontextusmentes nyelvtanokként. Az alábbiakban egy véges állapotú nyelvtani automata mintája látható.
A következő mondatok az automata és a programozási kód néhány egyszerű szabályából generálódnak a mintaelméletben:
a fiú, akinek a kis házikója volt, a mély erdőbe ment a herceg a tóhoz sétált a lány elsétált a tóhoz, a hercegnő pedig elment a tóhoz a csinos herceg a sötét erdőbe sétált
Az ilyen mondatok létrehozásához a véges automaták újraírási szabályai generátorként működnek, és a következőképpen hozzák létre a mondatokat: ha egy gép az 1. állapotban indul, akkor a 2. állapotba lép, és leírja a "a/az" szót. A 2. állapotból a véletlenszerűen kiválasztott 4 szó közül egyet ír: herceg, fiú, hercegnő, lány. Az adott szó kiválasztásának valószínűségét az automatának megfelelő Markov-lánc adja meg. Egy ilyen leegyszerűsített automata időnként kínosabbnál kínosabb mondatokat generál:
a gonosz gonosz herceg a tóhoz sétált a herceg elment a sötét erdőbe és a herceg elment egy erdőbe és a hercegnő aki valami nagy kis nagy házikóban lakott akié volt a kis nagy kis házikó elment egy erdőbe.
A véges állapotdiagramból következtethetünk a következő generátorokra (jobbra látható), amelyek létrehozzák a jelet. Egy generátor egy 4-tuplából áll: aktuális állapot, következő állapot, kiírt szó, kiírt szó valószínűsége, ha több választási lehetőség van. Vagyis minden generátor egy Markov-lánc állapotdiagramjának állapotátmenet-nyila.
Képzeljük el, hogy a generátorok egy konfigurációját lineárisan felfűzzük úgy, hogy a kimenete egy mondatot alkot, tehát minden generátor "kötődik" az előtte és utána lévő generátorokhoz. Jelöljük ezeket a kötéseket 1x,1y,2x,2y,...12x,12y. Minden egyes numerikus címke az automata állapotának felel meg, az egyes "x" és "y" betűk pedig a befelé és kifelé irányuló kötéseknek. Ekkor a következő kötéstáblázat (balra) egyenértékű az automata diagramjával. Az egyszerűség kedvéért a kötéstáblázatnak csak a fele látható - a táblázat valójában szimmetrikus. 1x1y2x2y3x3y4x4y5x5y6x6y7x7y8x8y9x9y10x10y11x11y12x12y1x — — — — — — — — — — — — — — — — — — — — — 1 — —1y — 1 — — — — — — — — — — — — — — — — — — — — —2x — 1— — — — — — — — — — — — — — — — — — — —2y — 1 — — — — — — — — — — — — — — — — — — —3x — — — — — — — — — 1 — — — — — — — — — —3y — 1 — — — — — — — 1 — — — — — — — — —4x — — — — — — — — — — — — — — — — — —4y — 1 — 1 — — — — — — — — — — — — —5x — — — — — — — — — — — — — — — —5y — 1 — — — — — — — — — — — — —6x — — — — — — — — — — — — — —6y — 1 — — — — — — — — — — —7x — 1— — — — — — — — — —7y — — — — — — — — — — —8x — — — — — — — — — —8y — 1 — — — — — — —9x — — — — — — — —9y — 1 — — — — —10x — — — — — —10y — 1 — — —11x — 1— —11y — 1 —12x — —12y — Mint ebből a példából is látható, és a vizsgált jelekre jellemző, a primitívek és a kötéstáblák azonosítása némi gondolkodást igényel. A példa rávilágít egy másik fontos tényre is, ami más jelproblémáknál nem tűnik fel egykönnyen: egy konfiguráció nem maga a megfigyelt jel, hanem annak képe, mint egy mondat van megfigyelve. Ebben rejlik a megfigyelhető és a nem megfigyelhető konstrukció megkülönböztetésének jelentős indoklása. Ezenkívül ez egy algebrai struktúrát biztosít a rejtett Markov-modellekhez való társításhoz. Az olyan érzékszervi példákban, mint az alábbi látási példa, a rejtett konfigurációk és a megfigyelt képek sokkal hasonlóbbak, és egy ilyen megkülönböztetés nem tűnik indokoltnak. Szerencsére a nyelvtani példa emlékeztet minket erre a megkülönböztetésre.
Egy kifinomultabb példát találunk a természetes nyelv kapcsolati nyelvtanában.
Algebrai alapok A példa alapján a következő meghatározások léteznek:
A Generátor , jelölése a mintaelmélet azon primitívje, amely a megfigyelt jelet létrehozza. Szerkezetileg ez egy érték, amely interfészekkel, úgynevezett kötésekkel rendelkezik , amelyek összekötik a -ket, hogy egy jelgenerátort alkossanak. 2 szomszédos generátor akkor kapcsolódik, ha kötésértékük azonos. Hasonlósági önábrázolások s: G -> G a szemlélt világ invariánsait fejezik ki, például szilárdtest-transzformációkat vagy skálázást. A kötések generátorokat ragasztanak össze egy konfigurációba, c-be, amely a jelet egy Σ háttér előtt hozza létre, melynek globális jellemzőit lokálisan egy kötéskapcsolási táblázat írja le, az úgynevezett . A logikai függvény a <G, S, ρ, Σ> négyszeres szabályosság fő összetevője, melynek jelölése
láthatóan jelzi a megengedhető generátorszomszédokat. Vagyis a regularitás az ingerterület törvénye, amely egy kötéstáblázaton keresztül meghatározza, hogy egy generátor számára milyen szomszédok elfogadhatóak. Ezek az ingerterület törvényei. Később a regularitást egy boolean függvényből valószínűségi értékké alakítjuk, ez megmutatja, hogy milyen stimulusszomszédok valószínűek. Σ a generátorok fizikai elrendezése. A szemléltetve ez lehet egy 2 dimenziós rács. A nyelvben ez egy lineáris elrendezés. Egy kép (C mod R) egy megfigyelt konfiguráció fogalmát ragadja meg, ellentétben azzal, ami az észlelőkészüléktől függetlenül létezik. A képek olyan konfigurációk, amelyeket csak külső kötöttségeik különböztetnek meg, és amelyek öröklik a konfiguráció összetételét és a hasonló transzformációkat. Formálisan a képek olyan ekvivalenciaosztályok, amelyeket egy "~" azonosítási szabály tagol 3 tulajdonság alapján ext (c) = ext (c '), amikor c ~ c' sc ~ sc 'valahányszor c ~ c' sigma (c1, c2) ~ sigma (c1 ', c2'), amikor c1 ~ c1 ', c2 ~ c2' mind szabályos. Egy fizikai ingerhez tartozó konfigurációnak sok képe lehet, ami a sok megfigyelői észlelés azonosítási szabályának felel meg. A minta egy kép ismétlődő összetevői, amelyet a kép S-invariáns részhalmazaként határozunk meg. A hasonlóságok olyan referencia-transzformációk, amelyeket a minták meghatározásához használunk, pl. szilárdtest-transzformációk. Első pillantásra ez a definíció csak olyan textúramintázatokra tűnik alkalmasnak, ahol a minimális részkép újra és újra ismétlődik. Ha egy tárgy, például egy kutya képét nézzük, az nem ismétlődik, mégis ismerősnek tűnik, és mintának kellene lennie. A deformáció az eredeti kép olyan átalakítása, amely figyelembe veszi a környezet zaját és az érzékelőkészülék hibáját. Grenander a deformációk 4 típusát különbözteti meg: zaj és elmosódás, több skálájú szuperpozíció, tartománytorzítás és megszakítások. 2. példa Irányított határ A képet generáló generátoroknak ezt a konfigurációját a kötéstábla által egymásba szőtt primitívek hozzák létre, és a megfigyelő az azonosítási szabállyal érzékeli, amely a nem "0" és "1" generátorokat egyetlen határelemhez rendeli. Kilenc másik, nem ábrázolt generátor úgy jön létre, hogy a nem "0" és "1" generátorok mindegyikét 90 fokkal elforgatjuk. Az "irányított határok" tulajdonságát szem előtt tartva a generátorokat némi gondolkodással a következőképpen értelmezzük: a "0" generátor a belső elemeknek, az "1" a külsőnek, a "2" és annak elforgatásai az egyenes elemeknek, a többi pedig a forduló elemeknek felel meg. A Boole-szabályosságot termékként definiálva (minden nbr kötés), minden olyan konfigurációt, amelynek akár egyetlen generátora is sérti a kötéstáblát, elvetünk a vizsgálatból. Így csak a legtisztább formában lévő, a kötéstáblához ragaszkodó összes szomszédos generátorral rendelkező tulajdonságok engedélyezettek. Ez a szigorú feltétel enyhíthető, ha a Boole-féle kötéstáblák helyett valószínűségi mértékeket használunk.
Az új szabályosság már nem egy tökéletes irányított határt ír elő, hanem egy konfiguráció valószínűségét határozza meg az A() elfogadási függvény szempontjából. Az ilyen konfigurációknak megengedjük, hogy az érdeklődésre számot tartó tulajdonság tekintetében "szennyeződések" és tökéletlenségek legyenek. A generátorok és a teljes kötéstáblázatok segítségével a mintaelemzés nehéz része már megtörtént. A jelek és jellemzők új osztályának kezelésénél a generátorok és a kötéstáblázat kidolgozása sokkal nehezebb feladat. Ismét, a nyelvtanokhoz hasonlóan a generátorok és a kötéstáblák azonosítása is igényel némi gondolkodást. Ugyanígy kifinomult az a tény, hogy a konfiguráció nem az általunk megfigyelt jel. Inkább a képét figyeljük meg, mint az azonosítási szabály sziluettvetületeit.
+ Boole-féle kötési igazságtábla Értékek 0 1 2 3 4 5 0 1 — — — 1 — 1 1 — — — 1 2 — 1 — — 3 — — — 4 — — 5 —
Entrópia A mintaelmélet a sorrendet a p ( c ) által adott érdeklődés jellemzője alapján határozza meg.
Energia ( c ) = − log P ( c )
Statisztika Grenander mintaelmélete a bayes-i következtetés alapján az, hogy torzul a kép rekonstrukciója (pl. tartalom alapján címezhető memória). Azaz ha adott kép I-deformált, akkor meg kell találni I-t. Azonban Mumford értelmezése a mintaelméletről szélesebb körű. Ő egy PT-t határoz meg, hogy magába foglaljon számos jól ismert statisztikai módszert. Mumford kritériumai egy téma mintaelméletként való felvételéhez azok a módszerek, amelyeket "közös technikák és motivációk jellemeznek", mint például a HMM, az EM-algoritmus, a dinamikus programozás ötletköre. Az ebben a szakaszban szereplő témák Mumford mintaelméleti kezelését tükrözik. A statisztikai mintaelméletre vonatkozó elvei a következők:
A valós világ jeleit használja a konstruált jelek helyett az érdeklődésre számot tartó rejtett állapotok kikövetkeztetéséhez. Az ilyen jelek túl sok komplexitást és leletet tartalmaznak ahhoz, hogy pusztán determinisztikus elemzésnek engedjenek, ezért alkalmazzunk sztochasztikus módszereket is. Figyeljünk a jel természetes szerkezetére, beleértve a szimmetriákat, a részek függetlenségét, a kulcsfontosságú statisztikák marginálisait. Validálja a származtatott modellekből történő mintavételezéssel, és a Bayes-szabály segítségével következtessen rejtett állapotokra. Minden modalitásban a deformációk korlátozott családja a tiszta mintákat valós jelekké torzítja. A megfigyelést befolyásoló sztochasztikus tényezők erős feltételes függetlenséget mutatnak.