La teoría de patrones , formulada por Ulf Grenander , es un formalismo matemático para describir el conocimiento del mundo como patrones . Se diferencia de otros enfoques de la inteligencia artificial en que no comienza prescribiendo algoritmos y maquinaria para reconocer y clasificar patrones; más bien, prescribe un vocabulario para articular y reformular los conceptos de patrones en un lenguaje preciso. Amplia en su cobertura matemática, la teoría de patrones abarca el álgebra y la estadística , así como las propiedades topológicas locales y entrópicas globales.
Además del nuevo vocabulario algebraico, su enfoque estadístico es novedoso en su objetivo de:
- Identifique las variables ocultas de un conjunto de datos utilizando datos del mundo real en lugar de estímulos artificiales, lo que anteriormente era un lugar común.
- Formule distribuciones previas para variables ocultas y modelos para las variables observadas que forman los vértices de una gráfica similar a Gibbs .
- Estudie la aleatoriedad y variabilidad de estos gráficos.
- Cree las clases básicas de modelos estocásticos aplicados enumerando las deformaciones de los patrones.
- Sintetice (muestree) los modelos, no solo analice señales con ellos.
El Grupo de Teoría de Patrones de la Universidad de Brown fue formado en 1972 por Ulf Grenander. [1] Muchos matemáticos están trabajando actualmente en este grupo, entre los que destaca el medallista Fields David Mumford . Mumford considera a Grenander como su "gurú" en la teoría de patrones. [ cita requerida ]
Ejemplo: gramática del lenguaje natural
Comenzamos con un ejemplo para motivar las definiciones algebraicas que siguen. Si queremos representar patrones de lenguaje, el candidato más inmediato para primitivas podrían ser las palabras. Sin embargo, frases establecidas , como "con el fin de", indican inmediatamente que las palabras son inapropiadas como átomos . Al buscar otras primitivas, podríamos probar las reglas de la gramática . Podemos representar las gramáticas como autómatas de estado finito o gramáticas libres de contexto . es un autómata de gramática de estado finito de muestra.
Las siguientes frases se generan a partir de algunas reglas simples del autómata y el código de programación en la teoría de patrones:
- el chico que era dueño de la pequeña cabaña se fue al bosque profundo
- el príncipe caminó hacia el lago
- la niña caminó hacia el lago y la princesa fue al lago
- el lindo príncipe caminó hacia el bosque oscuro
Para crear tales oraciones, las reglas de reescritura en los autómatas de estado finito actúan como generadores para crear las oraciones de la siguiente manera: si una máquina comienza en el estado 1, pasa al estado 2 y escribe la palabra "el". Del estado 2, escribe una de 4 palabras: príncipe, niño, princesa, niña, elegida al azar. La probabilidad de elegir cualquier palabra dada viene dada por la cadena de Markov correspondiente al autómata. Un autómata tan simplista ocasionalmente genera oraciones más incómodas:
- el malvado príncipe malvado caminó hacia el lago
- el príncipe caminó hacia el bosque oscuro y el príncipe caminó hacia un bosque y la princesa que vivía en una cabaña grande, pequeña y grande que era dueña de la casa pequeña, grande, se fue a un bosque
Del diagrama de estados finitos podemos inferir los siguientes generadores (mostrados a la derecha) que crean la señal. Un generador es una tupla de 4: estado actual, estado siguiente, palabra escrita, probabilidad de palabra escrita cuando hay múltiples opciones. Es decir, cada generador es una flecha de transición de estado del diagrama de estado para una cadena de Markov.
Imagine que una configuración de generadores está unida linealmente para que su salida forme una oración, por lo que cada generador se "une" a los generadores antes y después de él. Denote estos enlaces como 1x, 1y, 2x, 2y, ... 12x, 12y. Cada etiqueta numérica corresponde al estado del autómata y cada letra "x" e "y" corresponde a los enlaces entrantes y salientes. Entonces, la siguiente tabla de enlaces (izquierda) es equivalente al diagrama de autómatas. En aras de la simplicidad, solo se muestra la mitad de la tabla de enlaces; en realidad, la tabla es simétrica .
1x | 1 año | 2x | 2 años | 3 veces | 3 años | 4x | 4 años | 5 veces | 5 años | 6x | 6 años | 7 veces | 7 años | 8x | 8 años | 9 veces | 9 años | 10 veces | 10 años | 11 veces | 11 años | 12 veces | 12 años | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1x | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | 1 | - | - |
1 año | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | |
2x | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||
2 años | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | |||
3 veces | - | - | - | - | - | - | - | - | - | 1 | - | - | - | - | - | - | - | - | - | - | ||||
3 años | - | 1 | - | - | - | - | - | - | - | 1 | - | - | - | - | - | - | - | - | - | |||||
4x | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||||||
4 años | - | 1 | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | |||||||
5 veces | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||||||||
5 años | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | |||||||||
6x | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||||||||||
6 años | - | 1 | - | - | - | - | - | - | - | - | - | - | - | |||||||||||
7 veces | - | 1 | - | - | - | - | - | - | - | - | - | - | ||||||||||||
7 años | - | - | - | - | - | - | - | - | - | - | - | |||||||||||||
8x | - | - | - | - | - | - | - | - | - | - | ||||||||||||||
8 años | - | 1 | - | - | - | - | - | - | - | |||||||||||||||
9 veces | - | - | - | - | - | - | - | - | ||||||||||||||||
9 años | - | 1 | - | - | - | - | - | |||||||||||||||||
10 veces | - | - | - | - | - | - | ||||||||||||||||||
10 años | - | 1 | - | - | - | |||||||||||||||||||
11 veces | - | 1 | - | - | ||||||||||||||||||||
11 años | - | 1 | - | |||||||||||||||||||||
12 veces | - | - | ||||||||||||||||||||||
12 años | - |
Como se puede deducir de este ejemplo, y es típico de las señales que se estudian, la identificación de las primitivas y las tablas de enlaces requiere cierta reflexión. El ejemplo destaca otro hecho importante que no es evidente en otros problemas de señales: que una configuración no es la señal que se observa; más bien, se observa su imagen como oración. Aquí radica una justificación significativa para distinguir un constructo observable de uno no observable. Además, proporciona una estructura algebraica para asociarla con modelos de Markov ocultos . En ejemplos sensoriales como el ejemplo de visión a continuación, las configuraciones ocultas y las imágenes observadas son mucho más similares, y tal distinción puede no parecer justificada. Afortunadamente, el ejemplo gramatical nos recuerda esta distinción.
Un ejemplo más sofisticado se puede encontrar en la teoría de la gramática de enlaces del lenguaje natural .
Fundamentos algebraicos
Motivados por el ejemplo, tenemos las siguientes definiciones:
- Un generador , dibujado como es el primitivo de la teoría de patrones que genera la señal observada. Estructuralmente, es un valor con interfaces, llamadas enlaces., que conecta el es para formar un generador de señales. 2 generadores vecinos están conectados cuando sus valores de enlace son los mismos. Automapas de similitud s: G -> G expresan las invariancias del mundo que estamos viendo, como transformaciones de cuerpos rígidos o escalado.
- Bonds pegamento generadores en una configuración , c, que crea la señal en un contexto Σ , con características globales describen localmente por una mesa de acoplamiento de enlace de llamada. La función booleana es el componente principal de la regularidad 4-tupla
, que se define como ,> - Una imagen (C mod R) captura la noción de una Configuración observada, a diferencia de una que existe independientemente de cualquier aparato de percepción. Las imágenes son configuraciones que se distinguen solo por sus vínculos externos, heredando la composición de la configuración y las transformaciones de similitudes. Formalmente, las imágenes son clases de equivalencia divididas por una regla de identificación "~" con 3 propiedades:
- ext (c) = ext (c ') siempre que c ~ c'
- sc ~ sc 'siempre que c ~ c'
- sigma (c1, c2) ~ sigma (c1 ', c2') siempre que c1 ~ c1 ', c2 ~ c2' sean todos regulares.
- Un patrón son los componentes repetibles de una imagen, definidos como el subconjunto S invariante de una imagen. Las similitudes son transformaciones de referencia que usamos para definir patrones, por ejemplo, transformaciones de cuerpos rígidos. A primera vista, esta definición parece adecuada solo para patrones de textura donde la subimagen mínima se repite una y otra vez. Si tuviéramos que ver una imagen de un objeto como un perro , no se repite, pero parece familiar y debería ser un patrón.
- Una deformación es una transformación de la imagen original que explica el ruido en el entorno y el error en el aparato perceptivo. Grenander identifica 4 tipos de deformaciones: ruido y desenfoque, superposición de múltiples escalas, deformación de dominio e interrupciones.
- Ejemplo 2 Límite dirigido
- Esta configuración de generadores que generan la imagen es creada por primitivas tejidas juntas por la tabla de enlace, y percibidas por un observador con la regla de identificación que mapea los generadores que no son "0" y "1" a un solo elemento límite. Otros nueve generadores no representados se crean girando cada uno de los generadores que no son "0" y "1" en 90 grados. Teniendo en cuenta la característica de los "límites dirigidos", los generadores se cocinan con un poco de pensamiento y se interpretan de la siguiente manera: el generador "0" corresponde a elementos interiores, "1" al exterior, "2" y sus rotaciones son elementos rectos , y el resto son los elementos de giro.
- Con la regularidad booleana definida como Producto (todos los enlaces nbr), cualquier configuración con incluso un solo generador que viole la tabla de enlaces se descarta de la consideración. Por lo tanto, solo se permiten características en su forma más pura con todos los generadores vecinos adheridos a la tabla de enlace. Esta estricta condición se puede relajar utilizando medidas de probabilidad en lugar de tablas de enlaces booleanos.
- La nueva regularidad ya no dicta un límite dirigido perfecto, sino que define una probabilidad de una configuración en términos de la función Aceptadora A (). Se permite que tales configuraciones tengan impurezas e imperfecciones con respecto a la característica de interés.
Con la ventaja de contar con generadores y tablas de enlace completas, se realiza una parte difícil del análisis de patrones. Al abordar una nueva clase de señales y características, la tarea de diseñar los generadores y la mesa de enlace es mucho más difícil.
Nuevamente, al igual que en las gramáticas, la identificación de los generadores y las tablas de enlaces requiere cierta reflexión. Igual de sutil es el hecho de que una configuración no es la señal que observamos. Más bien, observamos su imagen como proyecciones de silueta de la regla de identificación.
Valores de los bonos | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 1 | - | - | - | 1 | - |
1 | 1 | - | - | - | 1 | |
2 | - | 1 | - | - | ||
3 | - | - | - | |||
4 | - | - | ||||
5 | - |
Entropía
La teoría de patrones define el orden en términos de la característica de interés dada por p ( c ).
- Energía ( c ) = −log P ( c )
Estadísticas
El tratamiento de la teoría de patrones de Grenander de la inferencia bayesiana parece estar sesgado hacia la reconstrucción de imágenes (por ejemplo , memoria direccionable de contenido ). A eso se le da una imagen I-deformada, encontrar I. Sin embargo, la interpretación de Mumford de la teoría de patrones es más amplia y define PT para incluir muchos métodos estadísticos más conocidos. Los criterios de Mumford para la inclusión de un tema como la teoría de patrones son aquellos métodos "caracterizados por técnicas y motivaciones comunes", como el HMM , el algoritmo EM , el círculo de ideas de programación dinámica . Los temas de esta sección reflejarán el tratamiento de Mumford de la teoría de patrones. Sus principios de teoría estadística de patrones son los siguientes:
- Utilice señales del mundo real en lugar de construidas para inferir los estados de interés ocultos.
- Tales señales contienen demasiada complejidad y artefactos para sucumbir a un análisis puramente determinista, así que emplee también métodos estocásticos.
- Respete la estructura natural de la señal, incluidas las simetrías, la independencia de las partes y los márgenes de las estadísticas clave. Valide tomando muestras de los modelos derivados e infiera estados ocultos con la regla de Bayes.
- En todas las modalidades, una familia limitada de deformaciones distorsiona los patrones puros en señales del mundo real.
- Los factores estocásticos que afectan una observación muestran una fuerte independencia condicional.
El PT estadístico hace un uso omnipresente de la probabilidad condicional en la forma del teorema de Bayes y los modelos de Markov . Ambos conceptos se utilizan para expresar la relación entre estados ocultos (configuraciones) y estados observados (imágenes). Los modelos de Markov también capturan las propiedades locales del estímulo, que recuerdan el propósito de la tabla de enlaces para la regularidad.
La configuración genérica es la siguiente:
Sea s = el estado oculto de los datos que deseamos conocer. i = imagen observada. El teorema de Bayes da:
- p ( s | i ) p ( i ) = p ( s , i ) = p ( i | s ) p ( s )
- Para analizar la señal (reconocimiento): fije i, maximice p, infiera s.
- Para sintetizar señales (muestreo): arregle s, genere i's, compare con imágenes del mundo real
Los siguientes ejemplos de probabilidad condicional ilustran estos métodos en acción:
Probabilidad condicional para propiedades locales
Cadenas de texto de N-gram: consulte la teoría de patrones de Mumford mediante ejemplos, capítulo 1.
MAP ~ MDL (MDL ofrece una idea de por qué la formulación probabilística MAP tiene sentido analíticamente)
Teorema de Bayes para la traducción automática
Supongamos que queremos traducir frases del francés al inglés . Aquí, las configuraciones ocultas son oraciones en inglés y la señal observada que generan son oraciones en francés. El teorema de Bayes da p ( e | f ) p ( f ) = p ( e , f ) = p ( f | e ) p ( e ) y se reduce a la ecuación fundamental de la traducción automática: maximizar p ( e | f ) = p ( f | e ) p ( e ) sobre la e apropiada (observe que p ( f ) es independiente de e , por lo que desaparece cuando maximizamos sobre e ). Esto reduce el problema a tres cálculos principales para:
- p ( e ) para cualquier e dado , utilizando el método de N -gram y programación dinámica
- p ( f | e ) para cualquier determinado e y f , utilizando alineaciones y una expectativa de maximización (EM) algoritmo
- e que maximiza el producto de 1 y 2, nuevamente, usando programación dinámica
El análisis parece ser simétrico con respecto a los dos lenguajes, y si creemos que podemos calcular p ( f | e ), ¿por qué no darle la vuelta al análisis y calcular p ( e | f ) directamente? La razón es que durante el cálculo de p ( f | e ) se hace la suposición asimétrica de que la oración fuente está bien formada y no podemos hacer tal suposición sobre la traducción de destino porque no sabemos a qué se traducirá.
Ahora nos enfocamos en p ( f | e ) en la descomposición de tres partes anterior. Las otras dos partes, p ( e ) y maximización de e , utilizan técnicas similares al modelo de N -gram. Dada una traducción del francés al inglés de un gran conjunto de datos de capacitación (tales conjuntos de datos existen en el parlamento canadiense ):
NULL Y el programa se ha implementado Le program a ete mis en application
el par de oraciones se puede codificar como una alineación (2, 3, 4, 5, 6, 6, 6) que dice lo siguiente: la primera palabra en francés proviene de la segunda palabra en inglés, la segunda palabra en francés proviene de la tercera Palabra inglesa, etc. Aunque una alineación es una codificación sencilla de la traducción, un enfoque computacionalmente más conveniente para una alineación es dividirla en cuatro parámetros:
- Fertilidad : la cantidad de palabras en la cadena francesa que se conectarán a ella. Por ejemplo, n (3 | implementado) = probabilidad de que "implementado" se traduzca en tres palabras: la palabra fertilidad
- Espuria : introducimos el artefacto NULL como una palabra para representar la probabilidad de arrojar una palabra francesa falsa. Por ejemplo, p 1 y su complemento será p 0 = 1 - p 1 .
- Traducción : la versión traducida de cada palabra. Por ejemplo, t ( a | has) = probabilidad de traducción de que el inglés "has" se traduzca al francés "a".
- Distorsión : las posiciones reales en la cadena francesa que ocuparán estas palabras. Por ejemplo, d (5 | 2, 4, 6) = distorsión de la palabra francesa de la segunda posición moviéndose a la palabra inglesa de la quinta posición para una oración en inglés de cuatro palabras y una oración en francés de seis palabras. Codificamos las alineaciones de esta manera para representar y extraer fácilmente los antecedentes de nuestros datos de entrenamiento y la nueva fórmula se convierte en
En aras de la simplicidad en la demostración de un algoritmo EM, realizaremos un cálculo simple que involucra solo probabilidades de traducción t (), pero no hace falta decir que el método se aplica a todos los parámetros en todo su esplendor. Considere el caso simplificado (1) sin la palabra NULL (2) donde cada palabra tiene fertilidad 1 y (3) no hay probabilidades de distorsión. Nuestro corpus de datos de entrenamiento contendrá pares de dos oraciones: bc → xy y b → y . La traducción de una oración inglesa de dos palabras "bc" a la oración francesa " xy " tiene dos alineamientos posibles, e incluyendo las palabras de una oración, los alineamientos son:
bcbcb | | x | xyxyy
llamados Parallel, Crossed y Singleton respectivamente.
Para ilustrar un algoritmo EM, primero configure el parámetro deseado de manera uniforme, es decir
- t ( x | segundo ) = t ( y | segundo ) = t ( x | c ) = t ( y | c ) = 1 ⁄ 2
Entonces EM itera de la siguiente manera
La probabilidad de alineación para el “alineación cruzar” (donde B se conecta a y ) recibieron un impulso desde el segundo par de frases b / y . Eso solidificó aún más t ( y | b ), pero como efecto secundario también impulsó t ( x | c ), porque x se conecta ac en esa misma "alineación cruzada". El efecto de aumentar t ( x | c ) necesariamente significa rebajar t ( y | c ) porque suman uno. Así, a pesar de que Y y c co-ocurren, el análisis revela que no son traducciones de uno al otro. Con datos reales, EM también está sujeto a las habituales trampas de extremos locales.
HMM para reconocimiento de voz
Durante décadas, el reconocimiento de voz pareció llegar a un punto muerto mientras los científicos buscaban una solución descriptiva y analítica. La onda de sonido p (t) a continuación se produce al pronunciar la palabra "esquí".
Sus cuatro segmentos distintos tienen características muy diferentes. Se puede elegir entre muchos niveles de generadores (variables ocultas): la intención del cerebro del hablante , el estado de la boca y las cuerdas vocales , o los propios 'teléfonos'. Los teléfonos son el generador de elección para inferir y codifica la palabra de una manera ruidosa y muy variable. Los primeros trabajos sobre reconocimiento de voz intentaron hacer esta inferencia de manera determinista utilizando reglas lógicas basadas en características binarias extraídas de p (t). Por ejemplo, la siguiente tabla muestra algunas de las características que se utilizan para distinguir las consonantes en inglés .
En situaciones reales, la señal se complica aún más por ruidos de fondo, como automóviles que pasan o artefactos como una tos en la mitad de la oración (segundo fundamento de Mumford). El enfoque determinista basado en reglas falló y el estado del arte (por ejemplo, Dragon NaturallySpeaking ) es utilizar una familia de estimadores de MAP bayesianos y HMM ajustados con precisión para hacerlo mejor. Historias similares se desarrollaron en la visión y otras categorías de estímulos.
pag | t | k | B | D | gramo | metro | norte | F | s | v | z | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Continua | - | - | - | - | - | - | - | - | + | + | + | + |
Expresado | - | - | - | + | + | + | + | + | - | - | + | + |
Nasal | - | - | - | - | - | - | + | + | - | - | - | - |
Labial | + | - | - | + | - | - | + | - | + | - | + | - |
Coronal | - | + | - | - | + | - | - | + | - | + | - | + |
Anterior | + | + | - | + | + | - | + | + | + | + | + | + |
Estridente | - | - | - | - | - | - | - | - | + | + | + | + |
(Ver Teoría de patrones de Mumford: las matemáticas de la percepción) El proceso estocástico de Markov se esquematiza de la siguiente manera: exponenciales, algoritmo EM |
Ver también
- Razonamiento abductivo
- Estadística algebraica
- Anatomía computacional
- Análisis de concepto formal
- Inducción gramatical
- Análisis de imagen
- Inducción
- Teoría de la celosía
- Estadísticas espaciales
Referencias
- ^ "Página de inicio de Ulf Grenander" . 22 de enero de 2009. Archivado desde el original el 22 de enero de 2009 .
Otras lecturas
- 2007. Teoría de patrones de Ulf Grenander y Michael Miller : de la representación a la inferencia . Prensa de la Universidad de Oxford. Libro de bolsillo. ( ISBN 9780199297061 )
- 1994. Ulf Grenander General Pattern Theory . Publicaciones científicas de Oxford. ( ISBN 978-0198536710 )
- 1996. Elementos de la teoría de patrones de Ulf Grenander . Prensa de la Universidad Johns Hopkins. ( ISBN 978-0801851889 )
enlaces externos
- Grupo de teoría de patrones en la Universidad de Brown
- Teoría de patrones: ideas y ejemplos de Grenander - una conferencia en video de David Mumford
- Teoría y aplicaciones de patrones : página del curso de posgrado con material de un alumno de la Universidad de Brown