Teorie vzorů - Pattern theory

Teorie vzorů , formulovaná Ulfem Grenanderem , je matematický formalismus, který popisuje znalost světa jako vzory . Liší se od ostatních přístupů k umělé inteligenci tím, že nezačíná předepisováním algoritmů a mechanismů k rozpoznávání a klasifikaci vzorců; spíše předepisuje slovník, který artikuuluje a přepracovává koncepty vzorů v přesném jazyce. Teorie vzorů má široké matematické pokrytí, zahrnuje algebru a statistiky , stejně jako lokální topologické a globální entropické vlastnosti.

Kromě nové algebraické slovní zásoby je její statistický přístup nový v jejím cíli:

• Identifikovat skryté proměnné z v souboru dat pomocí dat reálného světa a nikoli umělých stimulů, což bylo dříve běžné.
• Formulujte předchozí rozdělení pro skryté proměnné a modely pro pozorované proměnné, které tvoří vrcholy Gibbsova grafu.
• Studujte náhodnost a variabilitu těchto grafů.
• Vytvořte základní třídy stochastických modelů použitých vypsáním deformací vzorů.
• Syntetizujte (vzorky) z modelů, nejen s nimi analyzujte signály.

Brown University Pattern Theory Group byla založena v roce 1972 Ulf Grenander. V této skupině v současné době pracuje mnoho matematiků, mezi nimiž stojí za zmínku Fieldsův medailista David Mumford . Mumford považuje Grenandera za svého „guru“ v teorii vzorů.

Příklad: Gramatika přirozeného jazyka

Gramatický automat

Generátory gramatiky

Začneme příkladem, který motivuje následující algebraické definice. Pokud chceme reprezentovat jazykové vzorce, nejbezprostřednějším kandidátem na primitiva mohou být slova. Avšak sada fráze , například „aby“ okamžitě uvést nevhodnost slov jako atomy . Při hledání dalších primitiv, mohli bychom zkusit pravidla gramatiky . Můžeme reprezentovat gramatiky jako konečného automatu nebo bezkontextových gramatik . Níže je ukázkový automat gramatiky konečného stavu.

Následující fráze jsou generovány z několika jednoduchých pravidel automatu a programovacího kódu v teorii vzorů:

chlapec, který vlastnil malou chatku, šel do hlubokého lesa

princ šel k jezeru

dívka šla k jezeru a princezna šla k jezeru

krásný princ šel do temného lesa

Při vytváření takových vět fungují přepisovací pravidla v automatech s konečným stavem jako generátory pro vytváření vět takto: pokud se stroj spustí ve stavu 1, přejde do stavu 2 a napíše slovo „the“. Ze stavu 2 píše jedno ze 4 slov: princ, chlapec, princezna, dívka, vybrána náhodně. Pravděpodobnost výběru libovolného daného slova je dána Markovovým řetězcem odpovídajícím automatu. Takový zjednodušující automat občas generuje nepříjemnější věty:

zlý zlý princ přešel k jezeru

princ šel do temného lesa a princ do lesa a princezna, která žila v nějaké velké malé velké chatě, která vlastnila malý velký malý dům, šla do lesa

Z diagramu konečného stavu můžeme odvodit následující generátory (zobrazené vpravo), které vytvářejí signál. Generátor je n-tice: aktuální stav, další stav, napsané slovo, pravděpodobnost napsaného slova, pokud existuje více možností. To znamená, že každý generátor je šipka přechodu stavu stavového diagramu pro Markovův řetězec.

Představte si, že konfigurace generátorů je spojena lineárně, takže její výstup tvoří větu, takže každý generátor se „spojuje“ s generátory před a po něm. Označte tyto vazby jako 1x, 1y, 2x, 2y, ... 12x, 12y. Každý číselný štítek odpovídá stavu automatu a každé písmeno „x“ a „y“ odpovídá příchozím a odchozím vazbám. Následující tabulka vazeb (vlevo) je ekvivalentní automatickému diagramu. Kvůli zjednodušení je zobrazena pouze polovina tabulky vazeb - tabulka je ve skutečnosti symetrická .

Jak je zřejmé z tohoto příkladu a je typické pro signály, které jsou studovány, identifikace primitiv a vazebných tabulek vyžaduje určité zamyšlení. Příklad zdůrazňuje další důležitý fakt, který není snadno patrný u jiných problémů se signály: že konfigurace není signál, který je pozorován; spíše je pozorován jeho obraz jako věta. V tom spočívá významné odůvodnění pro rozlišení pozorovatelného od nepozorovatelného konstruktu. Navíc poskytuje algebraickou strukturu pro přidružení ke skrytým Markovovým modelům . V senzorických příkladech, jako je příklad vidění níže, jsou skryté konfigurace a pozorované obrazy mnohem podobnější a takové rozlišení se nemusí zdát oprávněné. Příklad gramatiky nám toto rozlišení naštěstí připomíná.

Složitější příklad lze nalézt v odkazu gramatická teorie přirozeného jazyka .

Algebraické základy

Motivováni příkladem máme následující definice:

1. Generátor , koncipován jako ${\ displaystyle g {\ in} G}$

   

   je primitivní teorie vzorů, která generuje pozorovaný signál. Strukturálně jde o hodnotu s rozhraními, která se nazývá vazby , která spojuje čísla a tvoří generátor signálu. 2 sousední generátory jsou připojeny, když jsou jejich hodnoty vazby stejné. Samomapy podobnosti s: G -> G vyjadřují invariáty světa, na který se díváme, jako jsou tuhé transformace těla nebo změna měřítka. ${\ displaystyle b {\ in} B}$${\ displaystyle g}$${\ displaystyle s {\ in} S}$
2. Spojuje generátory lepidla do konfigurace , c, která vytváří signál na pozadí Σ , s globálními rysy popsanými místně pomocí tabulky vazeb vazeb . Logická funkce je hlavní složkou pravidelnosti 4-tici <G, S, ρ, Σ>, který je definován jako ${\ displaystyle \ rho}$${\ displaystyle \ rho}$

   ${\ displaystyle \ rho (c) = \ prod _ {{\ text {sousední vazby}} b ', b' '\ v c} \ rho (b', b '').}$

   ${\ displaystyle \ rho}$ Zdá se, že zachycuje představu povolených sousedů generátoru. To znamená, že pravidelnost je zákon stimulační domény definující prostřednictvím tabulky vazeb, jaké sousedé jsou pro generátor přijatelné. Jsou to zákony stimulační domény. Později uvolníme pravidelnost z booleovské funkce na hodnotu pravděpodobnosti, která by zachytila, jaké stimuly sousedé jsou pravděpodobné. Σ je fyzické uspořádání generátorů. Ve vidění by to mohla být dvojrozměrná mříž. V jazyce se jedná o lineární uspořádání.
3. Obraz (C mod R) zachycuje pojem pozorované konfigurace, na rozdíl od jednoho, který existuje nezávisle na jakémkoli perceptuální přístroje. Obrázky jsou konfigurace, které se odlišují pouze jejich vnějšími vazbami, které zdědily transformace složení a podobnosti konfigurace. Formálně jsou obrázky třídami ekvivalence rozdělenými podle identifikačního pravidla „~“ se 3 vlastnostmi:
   1. ext (c) = ext (c ') kdykoli c ~ c'
   2. sc ~ sc 'kdykoli ~
   3. sigma (c1, c2) ~ sigma (c1 ', c2'), kdykoli jsou všechny řádky c1 ~ c1 ', c2 ~ c2'.
   Konfigurace odpovídající fyzickému stimulu může mít mnoho obrazů, což odpovídá pravidlu identifikace vnímání mnoha pozorovatelů.
4. Vzor je opakovatelnou složky obrazu, které jsou definovány jako S-invariantní podmnožina obrazu. Podobnosti jsou referenční transformace, které používáme k definování vzorů, např. Transformace tuhých těles. Na první pohled se tato definice jeví jako vhodná pouze pro texturní vzory, kde se minimální dílčí obraz opakuje znovu a znovu. Pokud bychom si měli prohlédnout obraz předmětu, jako je pes , neopakuje se, přesto se zdá, že se zdá známý a měl by být vzorem.
5. Deformace je transformace z původního obrazu, který odpovídá za hluk v životním prostředí a chyby v vjemové aparátu. Grenander identifikuje 4 typy deformací: šum a rozmazání, vícenásobná superpozice, deformace domény a přerušení.

   Příklad 2 Směrovaná hranice

   

   Konfigurace
   

   obraz
   

   Generátory

   Tato konfigurace generátorů generujících obraz je vytvořena primitivy tkanými dohromady vazební tabulkou a vnímána pozorovatelem s identifikačním pravidlem, které mapuje generátory „0“ a „1“ na jeden hraniční prvek. Devět dalších nezjištěných generátorů je vytvořeno otočením každého z generátorů jiných než „0“ a „1“ o 90 stupňů. Při zachování rysu „směrovaných hranic“ jsou generátory uvařeny s trochou myšlenky a jsou interpretovány následovně: „0“ generátor odpovídá vnitřním prvkům, „1“ exteriéru, „2“ a jeho rotace jsou přímé prvky a zbytek jsou otočné prvky.

   S logickou pravidelností definovanou jako Produkt (všechny vazby nbr) jsou všechny konfigurace, dokonce s jediným generátorem, který porušuje tabulku vazeb, vyřazeny z úvahy. Jsou tedy povoleny pouze funkce v nejčistší podobě se všemi sousedními generátory dodržujícími tabulku vazeb. Tuto přísnou podmínku lze uvolnit pomocí pravděpodobnostních opatření namísto booleovských vazebních tabulek.

   ${\ displaystyle p (c) = \ prod _ {{\ text {sousední vazby}} b ', b' '\ v c} A (b', b '')}$

   Nová pravidelnost již diktuje perfektně směrovanou hranici, ale definuje pravděpodobnost konfigurace z hlediska funkce Acceptor A (). Takové konfigurace mohou mít nečistoty a nedokonalosti s ohledem na zájmovou vlastnost.

   Výhodou je, že jsme dostali generátory a kompletní tabulky vazeb, a proto se provádí obtížná část analýzy vzorů. Při řešení nové třídy signálů a funkcí je úkol navrhnout generátory a tabulku vazeb mnohem obtížnější.

   Opět, stejně jako v gramatikách, identifikace generátorů a tabulek vazeb vyžaduje určité zamyšlení. Stejně jemná je skutečnost, že konfigurace není signál, který pozorujeme. Spíše pozorujeme jeho obraz jako projekce siluety pravidla identifikace.

Entropie

Teorie vzorů definuje pořadí z hlediska zájmové charakteristiky dané p ( c ).

Energie ( c ) = −log P ( c )

Statistika

Zdá se, že Grenanderova teorie vzorů Bayesiánské inference je zkreslená směrem k rekonstrukci obrazu (např. Paměť adresovatelná obsahu ). Je uveden obraz I-deformovaný, najít I. Mumfordova interpretace teorie vzorů je však širší a definuje PT tak, aby zahrnoval mnoho známějších statistických metod. Mumfordovými kritérii pro zařazení tématu do teorie vzorů jsou metody „charakterizované běžnými technikami a motivacemi“, jako je HMM , algoritmus EM , dynamický programovací kruh myšlenek. Témata v této části budou odrážet Mumfordovo pojetí teorie vzorů. Jeho princip statistické teorie vzorů je následující:

• K odvození skrytých stavů zájmu používejte spíše signály reálného světa než konstruované.
• Takové signály obsahují příliš mnoho složitosti a artefaktů, aby podlehly čistě deterministické analýze, proto používejte také stochastické metody.
• Respektujte přirozenou strukturu signálu, včetně všech symetrií, nezávislosti částí, okrajů klíčových statistik. Ověření vzorkováním z odvozených modelů a odvození skrytých stavů podle Bayesova pravidla.
• Napříč všemi způsoby omezená rodina deformací narušuje čisté vzory na signály reálného světa.
• Stochastické faktory ovlivňující pozorování ukazují silnou podmíněnou nezávislost.

Statistické PT všudypřítomně využívá podmíněnou pravděpodobnost ve formě Bayesovy věty a Markovových modelů. Oba tyto pojmy se používají k vyjádření vztahu mezi skrytými stavy (konfigurace) a pozorovanými stavy (obrázky). Markovovy modely také zachycují místní vlastnosti podnětu, což připomíná účel tabulky vazeb pro pravidelnost.

Obecné nastavení je následující:

Nechť s = skrytý stav dat, která chceme znát. i = pozorovaný obraz. Bayesova věta dává:

p ( s | i ) p ( i ) = p ( s , i ) = p ( i | s ) p ( s )

Chcete-li analyzovat signál (rozpoznávání): opravte i, maximalizujte p, odvodte s.

Syntéza signálů (vzorkování): opravte s, generujte i, porovnejte obrázky se skutečným světem

Následující příklady podmíněné pravděpodobnosti ilustrují tyto metody v akci:

Podmíněná pravděpodobnost pro místní vlastnosti

N-gramové textové řetězce: Viz Mumfordova teorie vzorů podle příkladů, kapitola 1.

MAP ~ MDL (MDL nabízí pohled na to, proč má pravděpodobnostní formulace MAP smysl analyticky)

Podmíněná pravděpodobnost pro skryté pozorované stavy

Bayesova věta pro strojový překlad

Předpokládejme, že chceme přeložit francouzské věty do angličtiny . Zde jsou skryté konfigurace anglické věty a pozorovaný signál, který generují, jsou francouzské věty. Bayesova věta dává p ( e | f ) p ( f ) = p ( e , f ) = p ( f | e ) p ( e ) a redukuje se na základní rovnici strojového překladu: maximalizovat p ( e | f ) = p ( f | e ) p ( e ) nad příslušným e (všimněte si, že p ( f ) je nezávislé na e , a proto vypadne, když maximalizujeme nad e ). Tím se problém sníží na tři hlavní výpočty pro:

1. p ( e ) pro jakékoli dané e pomocí metody N -gram a dynamického programování
2. p ( f | e ) pro jakékoli dané e a f , pomocí zarovnání a algoritmu očekávání-maximalizace (EM)
3. e , který maximalizuje produkt 1 a 2, opět s použitím dynamické programování

Analýza se zdá být symetrická s ohledem na tyto dva jazyky, a pokud si myslíme, že umí vypočítat p ( f | e ), proč analýzu neobrátit a vypočítat p ( e | f ) přímo? Důvodem je to, že během výpočtu p ( f | e ) je vytvořen asymetrický předpoklad, že zdrojová věta je dobře utvořena, a nemůžeme udělat žádný takový předpoklad o cílovém překladu, protože nevíme, do čeho se bude překládat.

Nyní se zaměříme na p ( f | e ) v třídílném rozkladu výše. Další dvě části, p ( e ) a maximalizace e , používají podobné techniky jako model N -gram. Vzhledem k francouzsko-anglickému překladu z velkého souboru dat o školení (takové soubory dat existují z kanadského parlamentu ):

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

pár vět lze zakódovat jako zarovnání (2, 3, 4, 5, 6, 6, 6), které zní následovně: první slovo ve francouzštině pochází z druhého anglického slova, druhé slovo ve francouzštině pochází z 3. Anglické slovo atd. Ačkoli je zarovnání přímým kódováním překladu, výpočetně pohodlnějším přístupem k zarovnání je jeho rozdělení do čtyř parametrů:

1. Plodnost : počet slov ve francouzském řetězci, která s ním budou spojena. Např. N (3 | implementováno) = pravděpodobnost, že se „implementováno“ promítne do tří slov - plodnosti slova
2. Podvodnost : představíme artefakt NULL jako slovo, které představuje pravděpodobnost vržení ve falešném francouzském slově. Např. P ₁ a jeho doplněk bude p ₀ = 1 -  p ₁ .
3. Překlad : přeložená verze každého slova. Např. T ( a | has) = ​​pravděpodobnost překladu, že anglické „has“ se překládá do francouzského „a“.
4. Zkreslení : skutečné pozice ve francouzském řetězci, které tato slova obsadí. Např. D (5 | 2, 4, 6) = zkreslení druhé polohy francouzského slova pohybujícího se na pátou pozici anglického slova pro čtyřslovnou anglickou větu a šestislovnou francouzskou větu. Zakódujeme zarovnání tímto způsobem, abychom snadno reprezentovali a extrahovali předchůdce z našich tréninkových dat a nový vzorec se stal

${\ displaystyle {\ begin {aligned} p (f | e) & = {\ text {Součet všech možných zarovnání an of}} p (a, f | e) \\ & = n_ {0} (v_ {0 } | \ sum _ {j = 1} ^ {l} {v_ {j}}) \ cdot \ prod _ {j = 1} ^ {l} n (v_ {j} | e_ {j}) v_ {j }! \ cdot \ prod _ {j = 1} ^ {m} t (f_ {j} | e_ {a_ {j}}) \ cdot \ prod _ {j: a_ {j} \ not = 0} ^ { m} d (j | a_ {j}, l, m) \ end {zarovnáno}}}$

Kvůli jednoduchosti demonstrace EM algoritmu projdeme jednoduchým výpočtem zahrnujícím pouze pravděpodobnosti překladu t (), ale netřeba říkat, že tato metoda platí pro všechny parametry v jejich plné slávě. Zvažte zjednodušený případ (1) bez slova NULL (2), kde každé slovo má plodnost 1 a (3) neexistují žádné pravděpodobnosti zkreslení. Náš tréninkový datový korpus bude obsahovat dvojvěty: bc  →  xy a b  →  y . Překlad dvouslovné anglické věty „bc“ do francouzské věty „ xy “ má dvě možná zarovnání a včetně jednoslovných slov jsou zarovnání následující:

                         b c   b c   b
                         | |    x    |
                         x y   x y   y

zvané Parallel, Crossed a Singleton.

Pro ilustraci algoritmu EM nejprve nastavte požadovaný parametr jednotně, to znamená

t ( x | b ) = t ( y | b ) = t ( x | c ) = t ( y | c ) = 1 ⁄ 2

Poté EM iteruje následujícím způsobem

Iterace EM algoritmu

Pravděpodobnost zarovnání pro „křížení zarovnání“ (kde b se připojí k y ) získala podporu od druhého větného páru b / y . To dále zpevnilo t ( y | b ), ale jako vedlejší účinek také posílilo t ( x | c ), protože x se připojí k c ve stejném „křížení“. Účinek posílení t ( x | c ) nutně znamená snížení stupně t ( y | c ), protože jsou součtem jednoho. Takže, i když y a c co-nastat, analýza ukazuje, že nejsou překlady navzájem. Se skutečnými daty podléhá EM také obvyklým lokálním extrémním pastem.

HMM pro rozpoznávání řeči

Vibrační rozpad „lyže“

Po celá desetiletí se zdálo, že rozpoznávání řeči zasáhlo patovou situaci, když vědci hledali popisné a analytické řešení. Zvuková vlna p (t) níže se vyrábí mluví slovo „lyže“.

Jeho čtyři odlišné segmenty mají velmi odlišné vlastnosti. Lze si vybrat z mnoha úrovní generátorů (skrytých proměnných): záměr mozku mluvčího , stav úst a hlasivek nebo samotné „telefony“. Telefony jsou generátorem volby, který lze odvodit, a kóduje slovo hlučným a vysoce variabilním způsobem. Rané práce na rozpoznávání řeči se pokusily tuto inferenci deterministicky provést pomocí logických pravidel založených na binárních funkcích extrahovaných z p (t). Například tabulka níže ukazuje některé funkce používané k rozlišení anglických souhlásek .

Ve skutečných situacích je signál dále komplikován zvuky na pozadí, jako jsou auta, která projíždějí, nebo artefakty, jako je kašel ve střední větě (druhá podpora Mumforda). Deterministický přístup založený na pravidlech selhal a současným stavem techniky (např. Dragon NaturallySpeaking ) je využívat rodinu přesně vyladěných odhadů HMM a Bayesian MAP k lepšímu výkonu. Podobné příběhy se odehrály ve vizi a dalších kategoriích podnětů.

Viz také

• Únosná úvaha
• Algebraické statistiky
• Výpočetní anatomie
• Formální koncepční analýza
• Gramatická indukce
• Analýza obrazu
• Indukce
• Teorie mřížky
• Prostorové statistiky

Reference

Další čtení

• 2007. Ulf Grenander a Michael Miller Theory Pattern: From Representation to Inference . Oxford University Press. Brožura. ( ISBN   9780199297061 )
• 1994. Ulf Grenander Obecná teorie vzorů . Oxford Science Publications. ( ISBN   978-0198536710 )
• 1996. Ulf Grenander Prvky teorie vzorů . Johns Hopkins University Press. ( ISBN   978-0801851889 )

externí odkazy

• Skupina teorie vzorů na Brown University
• Teorie vzorů: Grenanderovy nápady a příklady - video přednáška Davida Mumforda
• Teorie vzorů a aplikace - stránka postgraduálního kurzu s materiálem absolventa Brown University