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.[1] 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 nyelvtanSzerkesztés

 
Nyelvtani automata
 
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.

1x 1y 2x 2y 3x 3y 4x 4y 5x 5y 6x 6y 7x 7y 8x 8y 9x 9y 10x 10y 11x 11y 12x 12y
1x 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 alapokSzerkesztés

A példa alapján a következő meghatározások léteznek:

  1. A Generátor  , jelölése
    </img> 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.
  2. 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.

  1. 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
    1. ext (c) = ext (c '), amikor c ~ c'
    2. sc ~ sc 'valahányszor c ~ c'
    3. 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.
  2. 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.
  3. 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ópiaSzerkesztés

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 )

StatisztikaSzerkesztés

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.

A statisztikai PT mindenütt használja a feltételes valószínűséget a Bayes-tétel és a Markov-modellek formájában. Mindkét fogalom a rejtett állapotok (konfigurációk) és a megfigyelt állapotok (képek) közötti kapcsolat kifejezésére szolgál. A Markov-modellek az inger helyi tulajdonságait is megragadják, emlékeztetve a kötéstáblázat céljára a szabályosságra.

Az általános felépítés a következő:

Legyen s = az adatok rejtett állapota, amelyet meg akarunk tudni. i = megfigyelt kép. A Bayes-tétel alapján:

p ( s | i ) p ( i ) = p ( s, i ) = p ( i | s ) p ( s )
A jel (felismerés) elemzése: állandó i, maximalizál p, következtet s.
A jelek szintetizálása (mintavétel): állandó s, generált i, hasonlítsa össze a valóvilágban készült képekkel

A következő feltételes valószínűségi példák szemléltetik ezeket a módszereket működés közben:

Helyi tulajdonságok feltételes valószínűségeSzerkesztés

N grammos szöveges karakterláncok: Lásd Mumford mintázatelmélete példákkal, 1. fejezet.

MAP ~ MDL (az MDL bepillantást ad abba, hogy miért értelmezhető a MAP valószínűségi formulája analitikusan)

Feltételes valószínűség rejtett megfigyelt állapotok eseténSzerkesztés

A gépi fordítás Bayes-tételeSzerkesztés

Tegyük fel, hogy francia mondatokat akarunk lefordítani angolra. Itt a rejtett konfigurációk az angol mondatok, az általuk generált megfigyelt jel pedig a francia mondatok. A Bayes-tétel szerint p(e|f)p(f) = p(e, f) = p(f|e)p(e), és ez a gépi fordítás alapvető egyenletére vezethető vissza: maximalizáljuk a p(e|f) = p(f|e)p(e) értéket a megfelelő e-n (vegyük észre, hogy a p(f) független e-től, és így kiesik, ha e-n maximalizálunk). Ez a problémát három fő számításra csökkenti:

  1. p(e) bármely adott e-re, az N-gram módszer és a dinamikus programozás.
  2. p ( f | e ) bármely adott e és f esetén, igazítások és várakozásmaximalizálás EM-algoritmus használatával
  3. e, mely maximalizálja a termék az 1-et és 2-t, ismét, dinamikus programozás használata

Az elemzés szimmetrikusnak tűnik a két nyelv tekintetében, és ha úgy gondoljuk, hogy ki tudjuk számítani a p(f|e) értéket, miért ne fordíthatnánk meg az elemzést, és miért ne számolhatnánk ki közvetlenül a p(e|f) értéket? Ennek az az oka, hogy a p(f|e) kiszámítása során azt az aszimmetrikus feltételezést tesszük, hogy a forrásmondat jól megformált, a célfordítással kapcsolatban pedig nem tehetünk ilyen feltételezést, mert nem tudjuk, hogy mire fog fordítani.

Most a p(f|e)-re összpontosítunk a fenti háromrészes bontásban. A másik két rész, a p(e) és az e maximalizálása hasonló technikákat használ, mint az N-gramm modell. Adott egy francia-angol fordítás egy nagy gyakorló adathalmazból (ilyen fajta adathalmazok a kanadai parlamentből származnak):

NULL   And    the    program      has    been    implemented
                     Le     programme    a ete     mis en application

a mondatpár kódolható (2, 3, 4, 5, 6, 6, 6, 6) igazításként, amely a következőképpen hangzik: az első francia szó a második angol szóból származik, a második francia szó a harmadik angol szóból származik, és így tovább. Bár az összehangolás a fordítás egyszerű kódolása, számítás szempontjából kényelmesebb megközelítése az összehangolásnak, ha azt négy paraméterre bontjuk:

  1. Fertilitás: a francia sztringben található szavak száma, amelyek a francia sztringhez kapcsolódnak. Pl. n( 3 | implemented ) = annak valószínűsége, hogy a "implemented" három szóra fordítható - a szó termékenysége.
  2. Tévesztés: bevezetjük a NULL-t, mint szót, amely egy hamis francia szó bedobásának valószínűségét reprezentálja. Pl. p1 és komplementere p0 = 1 - p1 lesz.
  3. Fordítás: az egyes szavak lefordított változata. Pl. t(a | has ) = annak a fordítási valószínűsége, hogy az angol "has" a francia "a"-ra fordítható.
  4. Torzítás: a szavak tényleges pozíciói a francia karakterláncban. Pl. d( 5 | 2, 4, 6 ) = a második pozícióban lévő francia szó torzulása, amely az ötödik pozícióba kerül az angol szóhoz egy négyszavas angol mondat és egy hatszavas francia mondat esetében. Az igazításokat így kódoljuk, hogy könnyen reprezentálhassuk és kivonhassuk a priorokat a képzési adatainkból, és az új képlet a következő lesz
 

Az egyszerűség kedvéért az EM-algoritmus bemutatásakor egy egyszerű számításon megyünk keresztül, amely csak a t() fordítási valószínűségeket érinti, de mondanunk sem kell, hogy a módszer minden paraméterre teljes pompájában alkalmazható. Tekintsük az egyszerűsített esetet (1) NULL szó nélkül (2), ahol minden szó termékenysége 1, és (3) nincsenek torzítási valószínűségek. A képzési adatkorpuszunk kétmondatos mondatpárokat tartalmaz: bc → xy és b → y. A kétmondatos angol "b c" mondat francia "x y" mondatra való fordításának két lehetséges igazítása van, és az egymondatos szavakkal együtt az igazítások a következők:

bcbcb
             | | x |
             xyxyy

Párhuzamosnak, Keresztezettnek és Singletonnak hívják.

Az EM algoritmus bemutatásához először állítsa be egységesen a kívánt paramétert, vagyis

t (x | b) = T (y | b) = T (x | c) = T (y | C) =

Ezután az EM a következőképpen ismétlődik

Fájl:Em iterations.jpg
EM-algoritmus ismétlései

A "keresztező igazítás" (ahol b kapcsolódik y-hoz) igazítási valószínűsége a második b/y mondatpár miatt növekedett. Ez tovább szilárdította a t(y | b) értéket, de mellékhatásként növelte a t(x | c) értéket is, mivel x ugyanebben a "keresztező igazításban" kapcsolódik c-hez. A t(x | c) növelésének hatása szükségszerűen a t(y | c) leminősítését jelenti, mivel ezek összege egy. Tehát, bár y és c együtt fordulnak elő, az elemzés azt mutatja, hogy nem egymás fordításai. Valós adatok esetén az EM is ki van téve a szokásos lokális szélsőértékcsapdáknak.

HMM-ek beszédfelismeréshezSzerkesztés

Fájl:Ski recording.jpg
A "sí" szó vibrációs bontása

Évtizedekig úgy tűnt, hogy a beszédfelismerés zsákutcába jutott, mivel a tudósok leíró és analitikus megoldást kerestek. Az alábbi p(t) hanghullámot a "ski" (síelés) szó kimondásával állítjuk elő.

Négy különböző szegmense nagyon eltérő jellemzőkkel bír. A generátorok (rejtett változók) számos szintje közül választhatunk: a beszélő agyának szándéka, a száj és a hangszalagok állapota, vagy maguk a "telefonok". A telefonok a választandó generátor, amelyből következtetni lehet, és amely a szót zajos, nagymértékben változó módon kódolja. A beszédfelismeréssel kapcsolatos korai munkák ezt a következtetést determinisztikusan próbálták megtenni, a p(t)-ből kinyert bináris jellemzőkön alapuló logikai szabályok segítségével. Az alábbi táblázat például az angol mássalhangzók megkülönböztetésére használt jellemzők közül mutat be néhányat.

Valós helyzetekben a jelet tovább bonyolítják a háttérzajok, például az elhaladó autók vagy az olyan jelenségek, mint egy köhögés a mondat közepén (Mumford 2. alátámasztása). A determinisztikus szabályalapú megközelítés kudarcot vallott, és a technika jelenlegi állása (pl. Dragon NaturallySpeaking) az, hogy pontosan hangolt HMM-ek és Bayes-féle MAP-becslők családját használja, hogy jobban teljesítsen. Hasonló történetek játszódtak le a látás és más stimulációs kategóriák esetében is.

A beszédfelismerés determinisztikus megközelítése
o t k b d g m n f s v z
Folytató + + + +
Zöngés + + + + + + +
Orr + +
Ajak + + + + +
Koronális + + + + +
Elülső + + + + + + + + + +
Metsző + + + +
(Lásd Mumford mintaelmélet: a percepció matematikája)

A Markov-féle sztochasztikus folyamatot az alábbiak szerint ábrázoljuk:

 

exponenciálok, EM algoritmus

FordításSzerkesztés

Ez a szócikk részben vagy egészben a Pattern theory című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Ulf Grenander's Home Page, 2009. január 22. [2009. január 22-i dátummal az eredetiből archiválva].

ForrásokSzerkesztés

További InformációkSzerkesztés

  • 2007. Ulf Grenander és Michael Miller mintaelmélet: A reprezentációtól a következtetésig . Oxford University Press. Puhakötés. (ISBN 9780199297061 )
  • 1994. Ulf Grenander általános mintaelmélet. Oxford Science Publications. (ISBN 978-0198536710 )
  • 1996. Ulf Grenander A mintaelmélet elemei. Johns Hopkins University Press. (ISBN 978-0801851889 )

Kapcsolódó szócikkekSzerkesztés