Teoria dei modelli - Pattern theory

La teoria dei modelli , formulata da Ulf Grenander , è un formalismo matematico per descrivere la conoscenza del mondo come modelli . Si differenzia da altri approcci all'intelligenza artificiale in quanto non inizia prescrivendo algoritmi e macchinari per riconoscere e classificare i modelli; piuttosto, prescrive un vocabolario per articolare e riformulare i concetti del modello in un linguaggio preciso. Ampia nella sua copertura matematica, la teoria dei pattern abbraccia algebra e statistica , nonché proprietà entropiche globali e topologiche locali.

Oltre al nuovo vocabolario algebrico, il suo approccio statistico è innovativo nel suo scopo di:

• Identifica le variabili nascoste di un set di dati utilizzando dati del mondo reale anziché stimoli artificiali, che in precedenza erano comuni.
• Formulare distribuzioni precedenti per variabili nascoste e modelli per variabili osservate che formano i vertici di un grafo simile a Gibbs .
• Studia la casualità e la variabilità di questi grafici.
• Creare le classi base dei modelli stocastici applicati elencando le deformazioni dei modelli.
• Sintetizza (campiona) dai modelli, non solo analizza i segnali con essi.

Il Brown University Pattern Theory Group è stato formato nel 1972 da Ulf Grenander. Molti matematici stanno attualmente lavorando in questo gruppo, tra cui degno di nota è il medaglia Fields David Mumford . Mumford considera Grenander come il suo "guru" in Pattern Theory.

Esempio: grammatica in linguaggio naturale

Automa grammaticale

Generatori di grammatica

Cominciamo con un esempio per motivare le definizioni algebriche che seguono. Se vogliamo rappresentare modelli linguistici, il candidato più immediato per le primitive potrebbero essere le parole. Tuttavia, impostare frasi , come "per" indicare immediatamente l'inappropriatezza delle parole come atomi . Nella ricerca di altre primitive, potremmo provare le regole della grammatica . Possiamo rappresentare le grammatiche come automi a stati finiti o grammatiche prive di contesto . Di seguito è un esempio di automa grammaticale a stati finiti.

Le seguenti frasi sono generate da alcune semplici regole dell'automa e del codice di programmazione nella teoria dei modelli:

il ragazzo che possedeva il piccolo cottage andò nella foresta profonda

il principe andò al lago

la ragazza andò al lago e la principessa andò al lago

il grazioso principe si diresse verso la foresta oscura

Per creare tali frasi, le regole di riscrittura negli automi a stati finiti agiscono come generatori per creare le frasi come segue: se una macchina si avvia nello stato 1, va allo stato 2 e scrive la parola "the". Dallo stato 2, scrive una delle 4 parole: principe, ragazzo, principessa, ragazza, scelte a caso. La probabilità di scegliere una determinata parola è data dalla catena di Markov corrispondente all'automa. Un tale automa semplicistico genera occasionalmente frasi più imbarazzanti:

il malvagio principe malvagio si diresse verso il lago

il principe andò nella foresta oscura e il principe andò in una foresta e la principessa che viveva in un grande piccolo grande cottage che possedeva la piccola grande piccola casa andò in una foresta

Dal diagramma a stati finiti possiamo dedurre i seguenti generatori (mostrati a destra) che creano il segnale. Un generatore è una tupla di 4: stato corrente, stato successivo, parola scritta, probabilità di parola scritta quando ci sono più scelte. Cioè, ogni generatore è una freccia di transizione di stato del diagramma di stato per una catena di Markov.

Immagina che una configurazione di generatori sia messa insieme linearmente in modo che il suo output formi una frase, così ogni generatore "si lega" ai generatori prima e dopo di esso. Indica questi legami come 1x, 1y, 2x, 2y, ... 12x, 12y. Ogni etichetta numerica corrisponde allo stato dell'automa e ogni lettera "x" e "y" corrisponde ai legami in entrata e in uscita. Quindi la seguente tabella dei legami (a sinistra) è equivalente al diagramma dell'automa. Per semplicità, viene mostrata solo la metà della tabella dei legami: la tabella è in realtà simmetrica .

Come si può dedurre da questo esempio, e tipico dei segnali che vengono studiati, identificare le primitive e le tabelle dei legami richiede una riflessione. L'esempio evidenzia un altro fatto importante non immediatamente evidente in altri problemi di segnali: che una configurazione non è il segnale che si osserva; piuttosto, si osserva la sua immagine di frase. Qui sta una giustificazione significativa per distinguere un costrutto osservabile da uno non osservabile. Inoltre, fornisce una struttura algebrica da associare a modelli di Markov nascosti . In esempi sensoriali come l'esempio di visione qui sotto, le configurazioni nascoste e le immagini osservate sono molto più simili, e una tale distinzione potrebbe non sembrare giustificata. Fortunatamente, l'esempio grammaticale ci ricorda questa distinzione.

Un esempio più sofisticato può essere trovato nella teoria della grammatica di collegamento del linguaggio naturale .

Fondamenti algebrici

Motivati ​​dall'esempio, abbiamo le seguenti definizioni:

1. Un generatore , disegnato come ${\ displaystyle g {\ in} G}$

   

   è la primitiva della teoria dei pattern che genera il segnale osservato. Strutturalmente, è un valore con interfacce, chiamate legami , che collega gli 's per formare un generatore di segnali. 2 generatori vicini sono collegati quando i loro valori di legame sono gli stessi. Auto-mappe di somiglianza s: G -> G esprimono le invarianze del mondo che stiamo guardando, come le trasformazioni del corpo rigido o il ridimensionamento. ${\ displaystyle b {\ in} B}$${\ displaystyle g}$${\ displaystyle s {\ in} S}$
2. Incolla i generatori di colla in una configurazione , c, che crea il segnale su uno sfondo Σ , con caratteristiche globali descritte localmente da una tabella di accoppiamento di legami chiamata . La funzione booleana è la componente principale della regolarità 4-tupla <G, S, ρ, Σ>, che è definita come ${\ displaystyle \ rho}$${\ displaystyle \ rho}$

   ${\ Displaystyle \ rho (c) = \ prod _ {{\ text {legami vicini}} b ', b' '\ in c} \ rho (b', b '').}$

   ${\ displaystyle \ rho}$ sembra catturare la nozione di vicini generatori consentiti. Cioè, la regolarità è la legge del dominio dello stimolo che definisce, tramite una tabella di legame, quali vicini sono accettabili per un generatore. Sono le leggi del dominio dello stimolo. Successivamente, rilasseremo la regolarità da una funzione booleana a un valore di probabilità, catturerebbe quale stimolo è probabile che i vicini siano. Σ è la disposizione fisica dei generatori. In visione, potrebbe essere un reticolo bidimensionale. Nel linguaggio, è una disposizione lineare.
3. Un'immagine (C mod R) cattura la nozione di una configurazione osservato, al contrario di quello che esiste indipendentemente da qualsiasi apparato percettivo. Le immagini sono configurazioni che si distinguono solo per i loro legami esterni, che ereditano la composizione della configurazione e le trasformazioni di somiglianze. Formalmente, le immagini sono classi di equivalenza partizionate da una regola di identificazione "~" con 3 proprietà:
   1. ext (c) = ext (c ') ogniqualvolta c ~ c'
   2. sc ~ sc 'ogni volta che c ~ c'
   3. sigma (c1, c2) ~ sigma (c1 ', c2') ogni volta che c1 ~ c1 ', c2 ~ c2' sono tutti regolari.
   Una configurazione corrispondente a uno stimolo fisico può avere molte immagini, corrispondenti alla regola di identificazione della percezione di molti osservatori.
4. Un pattern sono i componenti ripetibili di un'immagine, definiti come il sottoinsieme S-invariante di un'immagine. Le somiglianze sono trasformazioni di riferimento che usiamo per definire modelli, ad esempio trasformazioni di corpi rigidi. A prima vista, questa definizione sembra adatta solo per i modelli di trama in cui l'immagine secondaria minima viene ripetuta più e più volte. Se dovessimo visualizzare l'immagine di un oggetto come un cane , non si ripeterà, ma sembrerebbe familiare e dovrebbe essere uno schema.
5. Una deformazione è una trasformazione dell'immagine originale che tiene conto del rumore nell'ambiente e dell'errore nell'apparato percettivo. Grenander identifica 4 tipi di deformazioni: rumore e sfocatura, sovrapposizione multi-scala, deformazione del dominio e interruzioni.

   Esempio 2 Confine diretto

   

   Configurazione
   

   Immagine
   

   Generatori

   Questa configurazione di generatori che generano l'immagine è creata da primitive tessute insieme dalla tavola di legame, e percepite da un osservatore con la regola di identificazione che mappa i generatori non "0" e "1" su un singolo elemento di confine. Nove altri generatori non rappresentati vengono creati ruotando ciascuno dei generatori non "0" e "1" di 90 gradi. Tenendo presente la caratteristica dei "confini diretti", i generatori sono cucinati con un po 'di pensiero e vengono interpretati come segue: il generatore "0" corrisponde agli elementi interni, "1" all'esterno, "2" e le sue rotazioni sono elementi rettilinei , e il resto sono gli elementi rotanti.

   Con la regolarità booleana definita come Prodotto (tutti i legami nbr), qualsiasi configurazione con anche un singolo generatore che viola la tabella dei vincoli viene scartata dalla considerazione. Pertanto sono consentite solo le caratteristiche nella sua forma più pura con tutti i generatori vicini che aderiscono alla tabella di legame. Questa condizione rigorosa può essere attenuata utilizzando misure di probabilità anziché tabelle di obbligazioni booleane.

   ${\ displaystyle p (c) = \ prod _ {{\ text {legami vicini}} b ', b' '\ in c} A (b', b '')}$

   La nuova regolarità non detta più un confine diretto perfetto, ma definisce una probabilità di una configurazione in termini della funzione Accettatore A (). Tali configurazioni possono presentare impurità e imperfezioni rispetto alla caratteristica di interesse.

   Con il vantaggio di ricevere generatori e tabelle obbligazionarie complete, viene eseguita una parte difficile dell'analisi del modello. Nell'affrontare una nuova classe di segnali e caratteristiche, il compito di ideare i generatori e la tabella dei legami è molto più difficile.

   Ancora una volta, proprio come nelle grammatiche, l'identificazione dei generatori e delle tabelle di legame richiede un po 'di riflessione. Altrettanto sottile è il fatto che una configurazione non è il segnale che osserviamo. Piuttosto, osserviamo la sua immagine come proiezioni di silhouette della regola di identificazione.

Entropia

La teoria dei pattern definisce l'ordine in termini di caratteristica di interesse data da p ( c ).

Energia ( c ) = −log P ( c )

Statistiche

Il trattamento della teoria dei pattern di Grenander dell'inferenza bayesiana in sembra essere sbilanciato verso la ricostruzione dell'immagine (es. Memoria indirizzabile del contenuto ). Viene data un'immagine I-deformata, trova I. Tuttavia, l'interpretazione di Mumford della Pattern Theory è più ampia e definisce PT in modo da includere molti metodi statistici più noti. I criteri di Mumford per l'inclusione di un argomento come Teoria dei Pattern sono quei metodi "caratterizzati da tecniche e motivazioni comuni", come l' HMM , l' algoritmo EM , il circolo delle idee di programmazione dinamica . Gli argomenti di questa sezione rifletteranno il modo in cui Mumford ha trattato la teoria dei modelli. I suoi principi di teoria statistica dei modelli sono i seguenti:

• Usa segnali del mondo reale piuttosto che quelli costruiti per dedurre gli stati di interesse nascosti.
• Tali segnali contengono troppa complessità e artefatti per soccombere a un'analisi puramente deterministica, quindi impiegare anche metodi stocastici.
• Rispettare la struttura naturale del segnale, comprese eventuali simmetrie, indipendenza delle parti, marginalità sulle statistiche chiave. Convalida campionando dai modelli derivati ​​e deduci stati nascosti con la regola di Bayes.
• In tutte le modalità, una famiglia limitata di deformazioni distorce i modelli puri in segnali del mondo reale.
• I fattori stocastici che influenzano un'osservazione mostrano una forte indipendenza condizionale.

Il PT statistico fa un uso onnipresente della probabilità condizionata nella forma del teorema di Bayes e dei modelli di Markov . Entrambi questi concetti sono usati per esprimere la relazione tra stati nascosti (configurazioni) e stati osservati (immagini). Markov Models cattura anche le proprietà locali dello stimolo, che ricorda lo scopo della tabella dei legami per la regolarità.

La configurazione generica è la seguente:

Sia s = lo stato nascosto dei dati che desideriamo conoscere. i = immagine osservata. Il teorema di Bayes fornisce:

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

Per analizzare il segnale (riconoscimento): fissare i, massimizzare p, dedurre s.

Per sintetizzare i segnali (campionamento): correggi, genera i, confronta con immagini del mondo reale

I seguenti esempi di probabilità condizionale illustrano questi metodi in azione:

Probabilità condizionata per proprietà locali

Stringhe di testo in N-gram: vedere la teoria dei modelli di Mumford per esempi, capitolo 1.

MAP ~ MDL (MDL offre un assaggio del motivo per cui la formulazione probabilistica MAP ha senso analiticamente)

Probabilità condizionata per stati osservati nascosti

Teorema di Bayes per la traduzione automatica

Supponiamo di voler tradurre frasi francesi in inglese . Qui, le configurazioni nascoste sono frasi in inglese e il segnale osservato che generano sono frasi in francese. Il teorema di Bayes fornisce p ( e | f ) p ( f ) = p ( e , f ) = p ( f | e ) p ( e ) e si riduce all'equazione fondamentale della traduzione automatica: massimizza p ( e | f ) = p ( f | e ) p ( e ) sull'appropriata e (si noti che p ( f ) è indipendente da e , e quindi si interrompe quando massimizziamo su e ). Ciò riduce il problema a tre calcoli principali per:

1. p ( e ) per ogni dato e , usando il metodo N -gram e la programmazione dinamica
2. p ( f | e ) per ogni dato e e f , utilizzando allineamenti e un algoritmo di massimizzazione delle aspettative (EM)
3. e che massimizza il prodotto di 1 e 2, ancora una volta, utilizzando la programmazione dinamica

L'analisi sembra essere simmetrica rispetto alle due lingue, e se pensiamo di poter calcolare p ( f | e ), perché non capovolgere l'analisi e calcolare direttamente p ( e | f )? Il motivo è che durante il calcolo di p ( f | e ) si assume l'asimmetria che la frase sorgente sia ben formata e non possiamo fare alcuna ipotesi del genere sulla traduzione di destinazione perché non sappiamo in cosa si tradurrà.

Ci concentriamo ora su p ( f | e ) nella scomposizione in tre parti sopra. Le altre due parti, p ( e ) e massimizzazione e , utilizzano tecniche simili al modello N -gram. Data una traduzione francese-inglese da un ampio set di dati di addestramento (tali set di dati esistono dal parlamento canadese ):

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

la coppia di frasi può essere codificata come un allineamento (2, 3, 4, 5, 6, 6, 6) che si legge come segue: la prima parola in francese proviene dalla seconda parola inglese, la seconda parola in francese proviene dalla terza Parola inglese e così via. Sebbene un allineamento sia una codifica diretta della traduzione, un approccio più conveniente dal punto di vista computazionale a un allineamento consiste nel suddividerlo in quattro parametri:

1. Fertilità : il numero di parole nella stringa francese che saranno collegate ad essa. Ad esempio n (3 | implementato) = probabilità che "implementato" si traduca in tre parole: la fertilità della parola
2. Spurie : introduciamo l'artefatto NULL come parola per rappresentare la probabilità di lanciare una parola francese spuria. Ad esempio p ₁ e il suo complemento sarà p ₀ = 1 -  p ₁ .
3. Traduzione : la versione tradotta di ogni parola. Ad esempio t ( a | has) = ​​probabilità di traduzione che l'inglese "has" si traduca in francese "a".
4. Distorsione : le posizioni effettive nella stringa francese che queste parole occuperanno. Ad esempio d (5 | 2, 4, 6) = distorsione della seconda parola francese che si sposta in quinta posizione parola inglese per una frase inglese di quattro parole e una frase francese di sei parole. Codifichiamo gli allineamenti in questo modo per rappresentare ed estrarre facilmente i priori dai nostri dati di addestramento e la nuova formula diventa

${\ displaystyle {\ begin {align} p (f | e) & = {\ text {Sum over all possible alignments 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 {allineato}}}$

Per semplicità nel dimostrare un algoritmo EM, eseguiremo un semplice calcolo che coinvolge solo le probabilità di traduzione t (), ma inutile dire che il metodo si applica a tutti i parametri nella loro piena gloria. Considera il caso semplificato (1) senza la parola NULL (2) dove ogni parola ha fertilità 1 e (3) non ci sono probabilità di distorsione. Il nostro corpus di dati di addestramento conterrà coppie di due frasi: bc  →  xy e b  →  y . La traduzione di una frase inglese di due parole "bc" nella frase francese " xy " ha due possibili allineamenti, e includendo le parole di una frase, gli allineamenti sono:

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

rispettivamente denominati Parallel, Crossed e Singleton.

Per illustrare un algoritmo EM, impostare prima il parametro desiderato in modo uniforme, ovvero

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

Quindi EM itera come segue

Iterazioni di un algoritmo EM

La probabilità di allineamento per l '"allineamento incrociato" (dove b si collega a y ) ha ottenuto un aumento dalla seconda coppia di frasi b / y . Questo ha ulteriormente solidificato t ( y | b ), ma come effetto collaterale ha anche potenziato t ( x | c ), perché x si collega a c in quello stesso "allineamento incrociato". L'effetto dell'aumento di t ( x | c ) significa necessariamente declassare t ( y | c ) perché sommano a uno. Quindi, anche se y e c si verificano contemporaneamente, l'analisi rivela che non sono traduzioni l'una dell'altra. Con dati reali, l'EM è anche soggetto alle solite trappole locali degli estremi.

HMM per il riconoscimento vocale

Ripartizione vibrazionale dello "sci"

Per decenni, il riconoscimento vocale è sembrato colpire un vicolo cieco mentre gli scienziati cercavano una soluzione descrittiva e analitica. L' onda sonora p (t) di seguito è prodotta pronunciando la parola "sci".

I suoi quattro segmenti distinti hanno caratteristiche molto diverse. Si può scegliere tra molti livelli di generatori (variabili nascoste): l'intenzione del cervello di chi parla , lo stato della bocca e delle corde vocali o gli stessi "telefoni". I telefoni sono il generatore di scelta da dedurre e codifica la parola in modo rumoroso e altamente variabile. I primi lavori sul riconoscimento vocale hanno tentato di fare questa inferenza in modo deterministico utilizzando regole logiche basate su caratteristiche binarie estratte da p (t). Ad esempio, la tabella seguente mostra alcune delle caratteristiche utilizzate per distinguere le consonanti inglesi .

In situazioni reali, il segnale è ulteriormente complicato da rumori di sottofondo come automobili che passano o artefatti come un colpo di tosse a metà frase (il 2 ° sostegno di Mumford). L'approccio deterministico basato su regole ha fallito e lo stato dell'arte (ad esempio Dragon NaturallySpeaking ) è quello di utilizzare una famiglia di HMM sintonizzati con precisione e stimatori Bayesiani MAP per fare meglio. Storie simili riprodotte nella visione e in altre categorie di stimoli.

Guarda anche

• Ragionamento abduttivo
• Statistica algebrica
• Anatomia computazionale
• Analisi formale del concetto
• Induzione grammaticale
• Analisi delle immagini
• Induzione
• Teoria del reticolo
• Statistiche spaziali

Riferimenti

Ulteriore lettura

• 2007. Ulf Grenander e Michael Miller Pattern Theory: From Representation to Inference . La stampa dell'università di Oxford. Paperback. ( ISBN   9780199297061 )
• 1994. Ulf Grenander General Pattern Theory . Pubblicazioni scientifiche di Oxford. ( ISBN   978-0198536710 )
• 1996. Elementi di teoria dei modelli di Ulf Grenander . Johns Hopkins University Press. ( ISBN   978-0801851889 )

link esterno

• Pattern Theory Group presso la Brown University
• Teoria dei modelli: idee ed esempi di Grenander - una conferenza video di David Mumford
• Teoria dei modelli e applicazioni - pagina del corso di laurea con materiale di un alunno della Brown University