Teoria wzorców - Pattern theory

Teoria wzorców , sformułowana przez Ulfa Grenandera , jest formalizmem matematycznym opisującym wiedzę o świecie jako wzorce . Różni się od innych podejść do sztucznej inteligencji tym, że nie zaczyna się od przepisywania algorytmów i maszyn do rozpoznawania i klasyfikowania wzorców; raczej nakazuje słownictwo do artykułowania i przekształcania pojęć wzorcowych w precyzyjnym języku. Szeroka pod względem matematycznym teoria wzorców obejmuje algebrę i statystykę , a także lokalne topologiczne i globalne właściwości entropiczne.

Oprócz nowego słownictwa algebraicznego, jego podejście statystyczne jest nowatorskie w swoim celu:

• Identyfikacji ukrytych zmiennych o zbiorze danych z wykorzystaniem rzeczywistych danych światowych zamiast sztucznych bodźców, co było wcześniej powszechne.
• Sformułuj wcześniejsze rozkłady dla ukrytych zmiennych i modele dla obserwowanych zmiennych, które tworzą wierzchołki wykresu podobnego do Gibbsa .
• Zbadaj losowość i zmienność tych wykresów.
• Utwórz podstawowe klasy modeli stochastycznych zastosowanych, wypisując deformacje wzorców.
• Zsyntetyzuj (próbkuj) z modeli, a nie tylko analizuj za ich pomocą sygnały.

The Brown University Pattern Theory Group została założona w 1972 roku przez Ulfa Grenandera. Obecnie w tej grupie pracuje wielu matematyków, wśród nich na uwagę zasługuje medalista Fields David Mumford . Mumford uważa Grenandera za swojego „guru” w teorii wzorców.

Przykład: gramatyka języka naturalnego

Automat gramatyczny

Generatory gramatyki

Zaczniemy od przykładu, aby zmotywować poniższe definicje algebraiczne. Jeśli chcemy przedstawić wzorce językowe, najbliższym kandydatem na prymitywy mogą być słowa. Jednak ustawione frazy , takie jak „w celu” natychmiastowego wskazania niewłaściwości słów jako atomów . Szukając innych prymitywów, możemy wypróbować reguły gramatyki . Gramatyki możemy przedstawić jako automaty skończone lub gramatyki bezkontekstowe . Poniżej jest przykładowym automatem do gramatyki skończonej.

Poniższe frazy są generowane z kilku prostych reguł automatu i kodu programowania w teorii wzorców:

chłopiec, który był właścicielem małego domku, udał się do głębokiego lasu

książę podszedł do jeziora

dziewczyna poszła nad jezioro, a księżniczka poszła nad jezioro

ładny książę poszedł do ciemnego lasu

Aby stworzyć takie zdania, reguły przepisywania w automatach skończonych działają jak generatory do tworzenia zdań w następujący sposób: jeśli maszyna zaczyna się w stanie 1, przechodzi do stanu 2 i zapisuje słowo „the”. Ze stanu 2 zapisuje jedno z 4 słów: książę, chłopiec, księżniczka, dziewczyna, wybrana losowo. Prawdopodobieństwo wybrania dowolnego słowa daje łańcuch Markowa odpowiadający automatowi. Taki uproszczony automat czasami generuje bardziej niezręczne zdania:

zły, zły książę podszedł do jeziora

książę poszedł do ciemnego lasu, a książę do lasu, a księżniczka, która mieszkała w jakimś dużym małym dużym domku, która była właścicielem małego dużego małego domu, poszła do lasu

Z diagramu stanów skończonych możemy wywnioskować następujące generatory (pokazane po prawej), które tworzą sygnał. Generator to czteroosobowa krotka: stan bieżący, stan następny, zapisane słowo, prawdopodobieństwo wystąpienia słowa pisanego, gdy istnieje wiele możliwości wyboru. Oznacza to, że każdy generator jest strzałką przejścia stanów diagramu stanów dla łańcucha Markowa.

Wyobraź sobie, że konfiguracja generatorów jest połączona ze sobą liniowo, więc jej wyjście tworzy zdanie, więc każdy generator „łączy się” z generatorami przed i po nim. Oznacz te obligacje jako 1x, 1y, 2x, 2y, ... 12x, 12y. Każda etykieta numeryczna odpowiada stanowi automatu, a każda litera „x” i „y” odpowiada obligacjom przychodzącym i wychodzącym. Następnie poniższa tabela wiązań (po lewej) jest odpowiednikiem diagramu automatu. Dla uproszczenia pokazano tylko połowę tabeli wiązań - tabela jest w rzeczywistości symetryczna .

Jak wynika z tego przykładu i jest to typowe dla badanych sygnałów, identyfikacja prymitywów i tablic wiązań wymaga przemyślenia. Przykład podkreśla inny ważny fakt, który nie jest widoczny w innych problemach z sygnałami: że konfiguracja nie jest obserwowanym sygnałem; raczej obserwuje się jego obraz jako zdanie. Tutaj znajduje się istotne uzasadnienie dla odróżnienia konstruktu obserwowalnego od nieobserwowalnego. Dodatkowo zapewnia strukturę algebraiczną do powiązania z ukrytymi modelami Markowa . W przykładach sensorycznych, takich jak przykład widzenia poniżej, ukryte konfiguracje i obserwowane obrazy są znacznie bardziej podobne i takie rozróżnienie może wydawać się nieuzasadnione. Na szczęście przykład gramatyki przypomina nam o tym rozróżnieniu.

Bardziej wyrafinowany przykład można znaleźć w teorii gramatyki linków języka naturalnego .

Podstawy algebraiczne

Zmotywowani przykładem mamy następujące definicje:

1. Generatora , sporządzony jako ${\ displaystyle g {\ in} G}$

   

   jest prymitywem teorii wzorców, który generuje obserwowany sygnał. Strukturalnie jest to wartość z interfejsami, zwanymi wiązaniami , które łączą je, tworząc generator sygnału. 2 sąsiednie generatory są połączone, gdy ich wartości wiązania są takie same. Auto-mapy podobieństwa s: G -> G wyrażają niezmienności świata, na który patrzymy, takie jak przemiany ciała sztywnego lub skalowanie. ${\ displaystyle b {\ in} B}$${\ displaystyle g}$${\ displaystyle s {\ in} S}$
2. Łączy generatory kleju w konfigurację c, która tworzy sygnał na tle Σ , z globalnymi cechami opisanymi lokalnie przez tabelę sprzężenia wiązań o nazwie . Wartość logiczna funkcja jest głównym składnikiem regularność 4-krotnego <G S ρ, Σ>, który jest zdefiniowany jako ${\ displaystyle \ rho}$${\ displaystyle \ rho}$

   ${\ Displaystyle \ rho (c) = \ prod _ {{\ tekst {sąsiednie obligacje}} b ', b' '\ w c} \ rho (b', b ').}$

   ${\ displaystyle \ rho}$ wydaje się uchwycić pojęcie dopuszczalnych sąsiadów generatorów. Oznacza to, że regularność jest prawem domeny bodźców określającym, poprzez tablicę wiązań, jakie sąsiedzi są akceptowane przez generator. To prawa domeny bodźców. Później rozluźnimy regularność z funkcji boolowskiej do wartości prawdopodobieństwa, by uchwycić, jakie bodźce sąsiedzi są prawdopodobni. Σ to fizyczne rozmieszczenie generatorów. W wizji może to być dwuwymiarowa krata. W języku jest to układ liniowy.
3. Obrazu (C mod R) rejestruje pojęcie obserwowanego konfiguracji, w przeciwieństwie do, który istnieje niezależnie od jakiegokolwiek urządzenia percepcyjnego. Obrazy są konfiguracjami wyróżniającymi się jedynie zewnętrznymi wiązaniami, dziedziczącymi skład konfiguracji i przekształceniami podobieństw. Formalnie obrazy są klasami równoważności podzielonymi według reguły identyfikacji „~” z trzema właściwościami:
   1. ext (c) = ext (c ') kiedykolwiek c ~ c'
   2. sc ~ sc 'kiedy c ~ c'
   3. sigma (c1, c2) ~ sigma (c1 ', c2') zawsze, gdy c1 ~ c1 ', c2 ~ c2' są regularne.
   Konfiguracja odpowiadająca bodźcowi fizycznemu może mieć wiele obrazów, odpowiadających zasadzie identyfikacji wielu obserwatorów.
4. Wzór jest powtarzalne elementy obrazu, określane jako podzbiór S-niezmienniczy obrazu. Podobieństwa to transformacje odniesienia, których używamy do definiowania wzorców, np. Transformacje ciała sztywnego. Na pierwszy rzut oka ta definicja wydaje się odpowiednia tylko dla wzorów tekstur, w których minimalny podobraz jest powtarzany w kółko. Gdybyśmy mieli zobaczyć obraz obiektu, takiego jak pies , nie jest on powtarzany, ale wydaje się, że wydaje się znajomy i powinien być wzorem.
5. Deformacja jest przekształcenie pierwotnego obrazu, uwzględniającego hałasu w środowisku i błędów w urządzeniu percepcyjnej. Grenander identyfikuje 4 rodzaje deformacji: szum i rozmycie, wieloskalowa superpozycja, wypaczanie domeny i przerwy.

   Przykład 2 Granica ukierunkowana

   

   Konfiguracja
   

   Wizerunek
   

   Generatory

   Ta konfiguracja generatorów generujących obraz jest tworzona przez prymitywy splecione ze sobą przez stół wiążący i postrzegane przez obserwatora z regułą identyfikacji, która odwzorowuje generatory inne niż „0” i „1” na pojedynczy element brzegowy. Dziewięć innych nieprzewidzianych generatorów jest tworzonych przez obrócenie każdego z generatorów innych niż „0” i „1” o 90 stopni. Mając na uwadze cechę „ukierunkowanych granic”, generatory są przygotowywane z pewną myślą i jest interpretowane w następujący sposób: generator „0” odpowiada elementom wewnętrznym, „1” zewnętrznemu, „2”, a jego obroty są elementami prostymi a reszta to elementy obrotowe.

   Z regularnością boolowską zdefiniowaną jako Produkt (wszystkie wiązania nbr), wszelkie konfiguracje z nawet jednym generatorem naruszającym tablicę wiązań są odrzucane z rozważań. W związku z tym dozwolone są tylko funkcje w najczystszej postaci ze wszystkimi sąsiednimi generatorami przylegającymi do tabeli wiązań. Ten rygorystyczny warunek można złagodzić za pomocą miar prawdopodobieństwa zamiast tablic wiązań boolowskich.

   ${\ Displaystyle p (c) = \ prod _ {{\ tekst {sąsiednie obligacje}} b ', b' '\ w c} A (b', b ')}$

   Nowa regularność nie dyktuje już idealnej skierowanej granicy, ale definiuje prawdopodobieństwo konfiguracji w odniesieniu do funkcji akceptora A (). Takie konfiguracje mogą mieć zanieczyszczenia i niedoskonałości w odniesieniu do interesującej cechy.

   Mając na uwadze generatory i kompletne tabele wiązań, wykonywana jest trudna część analizy wzorców. W przypadku nowej klasy sygnałów i cech zadanie opracowania generatorów i tablicy wiązań jest znacznie trudniejsze.

   Znowu, podobnie jak w gramatyce, identyfikacja generatorów i tablic wiązań wymaga pewnego przemyślenia. Równie subtelny jest fakt, że konfiguracja nie jest sygnałem, który obserwujemy. Raczej obserwujemy jego obraz jako rzutowanie sylwetki reguły identyfikacji.

Entropia

Teoria wzorców definiuje porządek w kategoriach interesującej nas cechy podanej przez p ( c ).

Energia ( c ) = −log P ( c )

Statystyka

Traktowanie wnioskowania bayesowskiego w teorii wzorców Grenandera wydaje się być wypaczone w kierunku rekonstrukcji obrazu (np. Pamięci adresowalnej treści ). To jest obraz I-zdeformowany, znajdź I. Jednakże interpretacja teorii wzorców Mumforda jest szersza i definiuje PT tak, aby obejmowała wiele bardziej znanych metod statystycznych. Kryteriami Mumforda do włączenia tematu jako teorii wzorców są metody „charakteryzujące się wspólnymi technikami i motywacjami”, takie jak HMM , algorytm EM , dynamiczny krąg pomysłów. Tematy w tej sekcji będą odzwierciedlać podejście Mumforda do teorii wzorców. Jego zasady statystycznej teorii wzorców są następujące:

• Użyj sygnałów ze świata rzeczywistego, a nie skonstruowanych, aby wywnioskować interesujące stany ukryte.
• Takie sygnały zawierają zbyt dużo złożoności i artefaktów, aby poddać się czysto deterministycznej analizie, więc należy również zastosować metody stochastyczne.
• Szanuj naturalną strukturę sygnału, w tym wszelkie symetrie, niezależność części, marginesy w kluczowych statystykach. Sprawdź poprawność przez próbkowanie z modeli pochodnych i wnioskuj stany ukryte za pomocą reguły Bayesa.
• We wszystkich modalnościach ograniczona rodzina deformacji zniekształca czyste wzorce w sygnały ze świata rzeczywistego.
• Czynniki stochastyczne wpływające na obserwację wykazują silną warunkową niezależność.

Statystyczne PT wszechobecne wykorzystuje prawdopodobieństwo warunkowe w postaci twierdzenia Bayesa i modeli Markowa . Obie te koncepcje służą do wyrażenia relacji między stanami ukrytymi (konfiguracjami) a stanami obserwowanymi (obrazy). Modele Markowa wychwytują również lokalne właściwości bodźca, przypominając cel tabeli wiązań dla regularności.

Ogólna konfiguracja jest następująca:

Niech s = ukryty stan danych, które chcemy poznać. i = obraz obserwowany. Twierdzenie Bayesa daje:

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

Aby przeanalizować sygnał (rozpoznanie): napraw i, maksymalizuj p, wnioskuj s.

Aby syntetyzować sygnały (próbkowanie): naprawiaj, generuj i, porównuj z obrazami świata rzeczywistego

Poniższe przykłady prawdopodobieństwa warunkowego ilustrują działanie tych metod:

Prawdopodobieństwo warunkowe dla dóbr lokalnych

N-gramowe ciągi tekstowe: patrz teoria wzorców Mumforda według przykładów, rozdział 1.

MAP ~ MDL (MDL daje wgląd w to, dlaczego probabilistyczne sformułowanie MAP ma sens analityczny)

Prawdopodobieństwo warunkowe dla stanów ukrytych obserwowanych

Twierdzenie Bayesa dotyczące tłumaczenia maszynowego

Przypuśćmy, że chcemy przetłumaczyć francuskie zdania na angielski . Tutaj ukryte konfiguracje to zdania angielskie, a obserwowany sygnał, który generują, to zdania francuskie. Twierdzenie Bayesa daje p ( e | f ) p ( f ) = p ( e , f ) = p ( f | e ) p ( e ) i redukuje do podstawowego równania tłumaczenia maszynowego: maksymalizuj p ( e | f ) = p ( f | e ) p ( e ) nad odpowiednim e (zauważ, że p ( f ) jest niezależne od e , a więc odpada, gdy maksymalizujemy nad e ). Zmniejsza to problem do trzech głównych obliczeń dla:

1. p ( e ) dla dowolnego e , przy użyciu metody N- gramów i programowania dynamicznego
2. P ( f | e ) dla każdej E i F , za pomocą trasowania i oczekiwanie, maksymalizacja algorytm (EM)
3. e, która maksymalizuje iloczyn 1 i 2, ponownie przy użyciu programowania dynamicznego

Analiza wydaje się być symetryczna w odniesieniu do tych dwóch języków, a jeśli uważamy, że możemy obliczyć p ( f | e ), dlaczego nie odwrócić analizy i bezpośrednio obliczyć p ( e | f )? Powodem jest to, że podczas obliczania p ( f | e ) przyjmuje się asymetryczne założenie, że zdanie źródłowe jest dobrze sformułowane i nie możemy przyjąć takiego założenia co do tłumaczenia docelowego, ponieważ nie wiemy, na co się przełoży.

Skupimy się teraz na p ( f | e ) w powyższym trzyczęściowym rozkładzie. Pozostałe dwie części, p ( e ) i maksymalizacja e , wykorzystują podobne techniki jak model N- gramowy. Biorąc pod uwagę francusko-angielskie tłumaczenie dużego zbioru danych szkoleniowych (takie zestawy danych istnieją w kanadyjskim parlamencie ):

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

parę zdań można zakodować jako wyrównanie (2, 3, 4, 5, 6, 6, 6) o następującej treści: pierwsze słowo w języku francuskim pochodzi od drugiego słowa angielskiego, drugie słowo w języku francuskim pochodzi z trzeciego Angielskie słowo i tak dalej. Chociaż wyrównanie jest prostym kodowaniem tłumaczenia, bardziej wygodnym obliczeniowo podejściem do wyrównania jest rozbicie go na cztery parametry:

1. Płodność : liczba słów we francuskim ciągu, które będą z nim połączone. Np. N (3 | zaimplementowane) = prawdopodobieństwo, że „zaimplementowane” przekłada się na trzy słowa - płodność słowa
2. Fałszywy : wprowadzamy artefakt NULL jako słowo reprezentujące prawdopodobieństwo dorzucenia fałszywego francuskiego słowa. Np. P _1, a jego dopełnienie wyniesie p ₀ = 1 -  p ₁ .
3. Tłumaczenie : przetłumaczona wersja każdego słowa. Np. T ( a | has) = ​​prawdopodobieństwo tłumaczenia, że ​​angielski „ma” przekłada się na francuskie „a”.
4. Zniekształcenie : rzeczywiste pozycje we francuskim ciągu, które będą zajmować te słowa. Np. D (5 | 2, 4, 6) = zniekształcenie drugiej pozycji Francuskie słowo przesunięte na piątą pozycję Angielskie słowo oznaczające czterowyrazowe zdanie angielskie i sześciowyrazowe zdanie francuskie. Kodujemy dopasowania w ten sposób, aby łatwo przedstawić i wyodrębnić wcześniejsze z naszych danych szkoleniowych, a nowa formuła staje się

${\ Displaystyle {\ rozpocząć {wyrównane} p (fa | e) & = {\ tekst {Suma wszystkich możliwych wyrównań 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) \ koniec {wyrównane}}}$

Ze względu na prostotę w zademonstrowaniu algorytmu EM, przejdziemy przez proste obliczenia uwzględniające tylko prawdopodobieństwa translacji t (), ale nie trzeba dodawać, że metoda ta odnosi się do wszystkich parametrów w ich pełnej krasie. Rozważmy przypadek uproszczony (1) bez słowa NULL (2), gdzie każde słowo ma płodność 1 i (3) nie ma prawdopodobieństwa zniekształcenia. Nasz korpus danych treningowych będzie zawierał pary dwuzdaniowe : bc  →  xy i b  →  y . Tłumaczenie angielskiego zdania „bc” składającego się z dwóch wyrazów na zdanie francuskie „ xy ” ma dwa możliwe wyrównania, a uwzględniając słowa jednozdaniowe, wyrównania są następujące:

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

zwane odpowiednio Parallel, Crossed i Singleton.

Aby zilustrować algorytm EM, najpierw ustaw równomiernie żądany parametr, to znaczy

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

Następnie EM wykonuje iterację w następujący sposób

Iteracje algorytmu EM

Prawdopodobieństwo dopasowania dla „wyrównania krzyżowego” (gdzie b łączy się z y ) uzyskało wzmocnienie z drugiej pary zdań b / y . To dodatkowo wzmocniło t ( y | b ), ale jako efekt uboczny również wzmocniło t ( x | c ), ponieważ x łączy się z c w tym samym „wyrównaniu krzyżującym”. Efekt wzmocnienia t ( x | c ) koniecznie oznacza obniżenie t ( y | c ), ponieważ sumują się do jednego. Tak więc, mimo że y i c współwystępują, analiza ujawnia, że ​​nie są one wzajemnymi tłumaczeniami. W przypadku prawdziwych danych EM podlega również zwykłym lokalnym pułapkom ekstremalnym.

HMM do rozpoznawania mowy

Rozkład wibracyjny słowa „narty”

Przez dziesięciolecia rozpoznawanie mowy wydawało się wpadać w impas, gdy naukowcy szukali opisowego i analitycznego rozwiązania. Fala dźwiękowa P (t) poniżej, jest wytwarzana przez wypowiedzenie tego słowa „nart”.

Jego cztery odrębne segmenty mają bardzo różne cechy. Do wyboru jest wiele poziomów generatorów (zmiennych ukrytych): intencja mózgu mówiącego , stan ust i strun głosowych czy same „telefony”. Telefony są preferowanym generatorem, który należy wywnioskować, i koduje słowo w hałaśliwy, wysoce zmienny sposób. Wczesne prace nad rozpoznawaniem mowy próbowały dokonać tego wnioskowania w sposób deterministyczny przy użyciu reguł logicznych opartych na cechach binarnych wyodrębnionych z p (t). Na przykład poniższa tabela przedstawia niektóre cechy używane do rozróżniania angielskich spółgłosek .

W rzeczywistych sytuacjach sygnał jest dodatkowo komplikowany przez hałasy w tle, takie jak przejeżdżające samochody lub artefakty, takie jak kaszel w połowie zdania (druga podpora Mumforda). Deterministyczne podejście oparte na regułach zawiodło, a najnowszy stan wiedzy (np. Dragon NaturallySpeaking ) polega na wykorzystaniu rodziny precyzyjnie dostrojonych HMM i estymatorów Bayesian MAP, aby działać lepiej. Podobne historie rozgrywały się w wizji i innych kategoriach bodźców.

Zobacz też

• Rozumowanie abdukcyjne
• Statystyka algebraiczna
• Anatomia obliczeniowa
• Analiza koncepcji formalnej
• Wprowadzenie do gramatyki
• Analiza obrazu
• Indukcja
• Teoria krat
• Statystyka przestrzenna

Bibliografia

Dalsza lektura

• 2007. Ulf Grenander i Michael Miller Teoria wzorców: od reprezentacji do wnioskowania . Oxford University Press. Książka w broszurowej oprawie. ( ISBN   9780199297061 )
• 1994. Ulf Grenander Ogólna teoria wzorców . Publikacje Oxford Science. ( ISBN   978-0198536710 )
• 1996. Ulf Grenander Elementy teorii wzorców . Johns Hopkins University Press. ( ISBN   978-0801851889 )

Linki zewnętrzne

• Grupa teorii wzorców na Uniwersytecie Browna
• Teoria wzorców: pomysły i przykłady Grenandera - wykład wideo Davida Mumforda
• Teoria wzorców i zastosowania - strona kursu dla absolwentów z materiałem absolwenta Brown University