Reconocimiento de patrones

El reconocimiento de patrones es el reconocimiento automatizado de patrones y regularidades en los datos. Tiene aplicaciones en análisis de datos estadísticos, procesamiento de señales, análisis de imágenes, recuperación de información, bioinformática, compresión de datos, gráficos por computadora y aprendizaje automático. El reconocimiento de patrones tiene su origen en la estadística y la ingeniería; algunos enfoques modernos para el reconocimiento de patrones incluyen el uso de aprendizaje automático, debido a la mayor disponibilidad de big data y una nueva abundancia de poder de procesamiento. Estas actividades pueden verse como dos facetas de un mismo campo de aplicación, y han experimentado un desarrollo sustancial en las últimas décadas.

Los sistemas de reconocimiento de patrones se entrenan comúnmente a partir de datos de "entrenamiento" etiquetados. Cuando no hay datos etiquetados disponibles, se pueden usar otros algoritmos para descubrir patrones previamente desconocidos. KDD y la minería de datos tienen un mayor enfoque en métodos no supervisados ​​y una conexión más fuerte con el uso comercial. El reconocimiento de patrones se centra más en la señal y también tiene en cuenta la adquisición y el procesamiento de señales. Se originó en la ingeniería y el término es popular en el contexto de la visión por computadora: una conferencia líder sobre visión por computadora se llama Conferencia sobre visión por computadora y reconocimiento de patrones.

En el aprendizaje automático, el reconocimiento de patrones es la asignación de una etiqueta a un valor de entrada dado. En estadística, el análisis discriminante se introdujo con este mismo propósito en 1936. Un ejemplo de reconocimiento de patrones es la clasificación, que intenta asignar cada valor de entrada a uno de un conjunto determinado de clases (por ejemplo, determinar si un correo electrónico determinado es "spam" o "no spam"). El reconocimiento de patrones es un problema más general que abarca también otros tipos de salida. Otros ejemplos son la regresión, que asigna una salida de valor real a cada entrada; etiquetado de secuencias, que asigna una clase a cada miembro de una secuencia de valores(por ejemplo, etiquetado de parte del discurso, que asigna una parte del discurso a cada palabra en una oración de entrada); y análisis, que asigna un árbol de análisis a una oración de entrada, describiendo la estructura sintáctica de la oración.

En sociología, el reconocimiento de patrones se ha determinado como un factor de desigualdad racial y sexista (https://www.inc.com/kimberly-weisul/vivek-wadhwa-pattern-recognition-another-name-racism-sexism.html).

Los algoritmos de reconocimiento de patrones generalmente tienen como objetivo proporcionar una respuesta razonable para todas las entradas posibles y realizar la coincidencia "más probable" de las entradas, teniendo en cuenta su variación estadística. Esto se opone a los algoritmos de coincidencia de patrones, que buscan coincidencias exactas en la entrada con patrones preexistentes. Un ejemplo común de un algoritmo de coincidencia de patrones es la coincidencia de expresiones regulares, que busca patrones de un tipo determinado en datos textuales y se incluye en las capacidades de búsqueda de muchos editores de texto y procesadores de texto.

Visión general

Una definición moderna de reconocimiento de patrones es:

El campo del reconocimiento de patrones se ocupa del descubrimiento automático de regularidades en los datos mediante el uso de algoritmos informáticos y del uso de estas regularidades para realizar acciones como clasificar los datos en diferentes categorías.

El reconocimiento de patrones generalmente se clasifica según el tipo de procedimiento de aprendizaje utilizado para generar el valor de salida. Aprendizaje supervisadoasume que se ha proporcionado un conjunto de datos de entrenamiento (el conjunto de entrenamiento), que consta de un conjunto de instancias que se han etiquetado correctamente a mano con el resultado correcto. Luego, un procedimiento de aprendizaje genera un modelo que intenta cumplir con dos objetivos a veces en conflicto: desempeñarse lo mejor posible con los datos de entrenamiento y generalizar lo mejor posible a los datos nuevos (por lo general, esto significa ser lo más simple posible, para alguna definición técnica). de "simple", de acuerdo con la navaja de Occam, discutida más adelante). El aprendizaje no supervisado, por otro lado, asume datos de entrenamiento que no han sido etiquetados a mano e intenta encontrar patrones inherentes en los datos que luego se pueden usar para determinar el valor de salida correcto para nuevas instancias de datos.Una combinación de los dos que se ha explorado es el aprendizaje semisupervisado, que utiliza una combinación de datos etiquetados y no etiquetados (por lo general, un pequeño conjunto de datos etiquetados combinados con una gran cantidad de datos no etiquetados). En los casos de aprendizaje no supervisado, es posible que no haya ningún dato de entrenamiento.

A veces se utilizan diferentes términos para describir los correspondientes procedimientos de aprendizaje supervisado y no supervisado para el mismo tipo de salida. El equivalente no supervisado de la clasificación normalmente se conoce como agrupamiento, basado en la percepción común de que la tarea no involucra datos de entrenamiento de los que hablar, y de agrupar los datos de entrada en grupos en función de alguna medida de similitud inherente (por ejemplo, la distancia entre instancias, considerada como vectores en un espacio vectorial multidimensional), en lugar de asignar cada instancia de entrada a una de un conjunto de clases predefinidas. En algunos campos, la terminología es diferente. En ecología comunitaria, el término clasificación se utiliza para referirse a lo que comúnmente se conoce como "agrupamiento".

La pieza de datos de entrada para la que se genera un valor de salida se denomina formalmente una instancia. La instancia se describe formalmente mediante un vector de características, que juntas constituyen una descripción de todas las características conocidas de la instancia. Estos vectores de características pueden verse como puntos de definición en un espacio multidimensional apropiado, y los métodos para manipular vectores en espacios vectoriales pueden aplicarse correspondientemente a ellos, como calcular el producto escalar o el ángulo entre dos vectores. Las características suelen ser categóricas (también conocidas como nominales, es decir, que consisten en uno de un conjunto de elementos no ordenados, como el género "masculino" o "femenino", o un tipo de sangre de "A", "B", " AB" u "O"), ordinal (que consta de uno de un conjunto de elementos ordenados, por ejemplo, "grande", "mediano" o "pequeño"), de valor entero (por ejemplo, un recuento del número de ocurrencias de una palabra en particular en un correo electrónico) o valor real (por ejemplo, una medición de la presión arterial). A menudo, los datos categóricos y ordinales se agrupan, y este también es el caso de los datos con valores enteros y valores reales. Muchos algoritmos funcionan solo en términos de datos categóricos y requieren que los datos con valores reales o con valores enteros seandiscretizados en grupos (por ejemplo, menos de 5, entre 5 y 10, o más de 10).

Clasificadores probabilísticos

Muchos algoritmos comunes de reconocimiento de patrones son de naturaleza probabilística, ya que utilizan la inferencia estadística para encontrar la mejor etiqueta para una instancia determinada. A diferencia de otros algoritmos, que simplemente generan una etiqueta "mejor", a menudo los algoritmos probabilísticos también generan una probabilidad de que la instancia sea descrita por la etiqueta dada. Además, muchos algoritmos probabilísticos generan una lista de las N mejores etiquetas con probabilidades asociadas, para algún valor de N, en lugar de simplemente una sola mejor etiqueta. Cuando el número de etiquetas posibles es bastante pequeño (p. ej., en el caso de la clasificación), se puede establecer N de modo que se emita la probabilidad de todas las etiquetas posibles. Los algoritmos probabilísticos tienen muchas ventajas sobre los algoritmos no probabilísticos:

• Producen un valor de confianza asociado con su elección. (Tenga en cuenta que algunos otros algoritmos también pueden generar valores de confianza, pero en general, solo para los algoritmos probabilísticos este valor se basa matemáticamente en la teoría de la probabilidad. En general, a los valores de confianza no probabilísticos no se les puede dar ningún significado específico, y solo se usan para compararlos con otros valores de confianza generados por el mismo algoritmo).
• En consecuencia, pueden abstenerse cuando la confianza de elegir un resultado en particular es demasiado baja.
• Debido a la salida de probabilidades, los algoritmos de reconocimiento de patrones probabilísticos se pueden incorporar de manera más efectiva en tareas de aprendizaje automático más grandes, de una manera que evita parcial o completamente el problema de la propagación de errores.

Número de variables de características importantes

Los algoritmos de selección de funciones intentan eliminar directamente las funciones redundantes o irrelevantes. Se ha proporcionado una introducción general a la selección de funciones que resume los enfoques y desafíos. La complejidad de la selección de características es, debido a su carácter no monótono, un problema de optimización en el que, dado un total de características, es necesario explorar el conjunto de potencia que consta de todos los subconjuntos de características. El algoritmo Branch-and-Bound reduce esta complejidad, pero es intratable para valores medianos a grandes de la cantidad de funciones disponibles.

Las técnicas para transformar los vectores de características sin procesar (extracción de características) a veces se utilizan antes de la aplicación del algoritmo de coincidencia de patrones. Los algoritmos de extracción de características intentan reducir un vector de características de gran dimensionalidad a un vector de menor dimensionalidad con el que es más fácil trabajar y codifica menos redundancia, utilizando técnicas matemáticas como el análisis de componentes principales (PCA). La distinción entre la selección de funciones y la extracción de funciones es que las funciones resultantes después de que se haya realizado la extracción de funciones son de un tipo diferente a las funciones originales y es posible que no se interpreten fácilmente, mientras que las funciones que quedan después de la selección de funciones son simplemente un subconjunto de las funciones originales..

Planteamiento del problema

El problema del reconocimiento de patrones se puede plantear de la siguiente manera: dada una función desconocida (la verdad fundamental) que asigna instancias de entrada a etiquetas de salida , junto con datos de entrenamiento que se supone que representan ejemplos precisos del mapeo, producir una función que se aproxime lo más posible el mapeo correcto . (Por ejemplo, si el problema es filtrar spam, entonces es alguna representación de un correo electrónico yes "spam" o "no-spam"). Para que este sea un problema bien definido, "se aproxima lo más posible" debe definirse rigurosamente. En la teoría de la decisión, esto se define especificando una función de pérdida o función de costo que asigna un valor específico a la "pérdida" resultante de producir una etiqueta incorrecta. Entonces, el objetivo es minimizar la pérdida esperada, tomando la expectativa sobre la distribución de probabilidad de . En la práctica, ni la distribución ni la función de verdad básica se conocen con exactitud, pero solo se pueden calcular empíricamente recolectando una gran cantidad de muestras y etiquetándolas a mano usando el valor correcto de(un proceso que consume mucho tiempo, que suele ser el factor limitante en la cantidad de datos de este tipo que se pueden recopilar). La función de pérdida particular depende del tipo de etiqueta que se prediga. Por ejemplo, en el caso de la clasificación, la función de pérdida simple de cero a menudo es suficiente. Esto corresponde simplemente a asignar una pérdida de 1 a cualquier etiquetado incorrecto e implica que el clasificador óptimo minimiza la tasa de error en los datos de prueba independientes (es decir, contar la fracción de instancias que la función aprendida etiqueta incorrectamente, lo que equivale a maximizar el número de instancias clasificadas correctamente). El objetivo del procedimiento de aprendizaje es entonces minimizar la tasa de error (maximizar la corrección) en un conjunto de prueba "típico".

Para un reconocedor de patrones probabilísticos, el problema es estimar la probabilidad de cada etiqueta de salida posible dada una instancia de entrada particular, es decir, estimar una función de la forma

donde la entrada del vector de características es , y la función f suele estar parametrizada por algunos parámetros . En un enfoque discriminativo del problema, f se estima directamente. Sin embargo, en un enfoque generativo, la probabilidad inversa se estima y se combina con la probabilidad previa utilizando la regla de Bayes, de la siguiente manera:

Cuando las etiquetas se distribuyen continuamente (p. ej., en el análisis de regresión), el denominador involucra la integración en lugar de la suma:

El valor de se aprende normalmente utilizando la estimación máxima a posteriori (MAP). Esto encuentra el mejor valor que cumple simultáneamente con dos objetos en conflicto: Para realizar lo mejor posible en los datos de entrenamiento (menor tasa de error) y para encontrar el modelo más simple posible. Esencialmente, esto combina la estimación de máxima verosimilitud con un procedimiento de regularización que favorece los modelos más simples sobre los modelos más complejos. En un contexto bayesiano, se puede considerar que el procedimiento de regularización coloca una probabilidad previa en diferentes valores de . Matemáticamente:

donde es el valor utilizado para en el procedimiento de evaluación posterior, y , la probabilidad posterior de , viene dada por

En el enfoque bayesiano de este problema, en lugar de elegir un solo vector de parámetros , la probabilidad de una etiqueta dada para una nueva instancia se calcula integrando todos los valores posibles de , ponderados de acuerdo con la probabilidad posterior:

Enfoque frecuentista o bayesiano para el reconocimiento de patrones

El primer clasificador de patrones, el discriminante lineal presentado por Fisher, se desarrolló en la tradición frecuentista. El enfoque frecuentista implica que los parámetros del modelo se consideran desconocidos, pero objetivos. A continuación, los parámetros se calculan (estiman) a partir de los datos recopilados. Para el discriminante lineal, estos parámetros son precisamente los vectores medios y la matriz de covarianza. Además, la probabilidad de cada clase se estima a partir del conjunto de datos recopilados. Tenga en cuenta que el uso de la 'regla de Bayes' en un clasificador de patrones no hace que el enfoque de clasificación sea bayesiano.

La estadística bayesiana tiene su origen en la filosofía griega donde ya se hacía una distinción entre el conocimiento 'a priori' y el 'a posteriori'. Más tarde, Kant definió su distinción entre lo que se conoce a priori, antes de la observación, y el conocimiento empírico obtenido de las observaciones. En un clasificador de patrón bayesiano, el usuario puede elegir las probabilidades de clase, que son entonces a priori. Además, la experiencia cuantificada como valores de parámetros a priori se puede ponderar con observaciones empíricas, utilizando, por ejemplo, las distribuciones Beta (a priori conjugada) y Dirichlet. El enfoque bayesiano facilita una mezcla perfecta entre el conocimiento experto en forma de probabilidades subjetivas y observaciones objetivas.

Los clasificadores de patrones probabilísticos se pueden utilizar de acuerdo con un enfoque frecuentista o bayesiano.

Usos

Dentro de la ciencia médica, el reconocimiento de patrones es la base de los sistemas de diagnóstico asistido por computadora (CAD). CAD describe un procedimiento que respalda las interpretaciones y hallazgos del médico. Otras aplicaciones típicas de las técnicas de reconocimiento de patrones son el reconocimiento automático de voz, la identificación del hablante, la clasificación de texto en varias categorías (por ejemplo, mensajes de correo electrónico spam o no spam), el reconocimiento automático de escritura a mano en sobres postales, reconocimiento automático de imágenes de rostros humanos, o extracción de imágenes de escritura a mano de formularios médicos. Los dos últimos ejemplos forman el subtema de análisis de imágenes de reconocimiento de patrones que se ocupa de las imágenes digitales como entrada a los sistemas de reconocimiento de patrones.

El reconocimiento óptico de caracteres es un ejemplo de la aplicación de un clasificador de patrones. El método de firmar el nombre de uno se capturó con lápiz óptico y superposición a partir de 1990. Los trazos, la velocidad, el mínimo relativo, el máximo relativo, la aceleración y la presión se utilizan para identificar y confirmar la identidad de manera única. A los bancos se les ofreció esta tecnología por primera vez, pero se contentaron con cobrar de la FDIC por cualquier fraude bancario y no querían incomodar a los clientes.

El reconocimiento de patrones tiene muchas aplicaciones del mundo real en el procesamiento de imágenes. Algunos ejemplos incluyen:

• identificación y autenticación: por ejemplo, reconocimiento de matrículas, análisis de huellas dactilares, detección/verificación de rostros y autenticación basada en voz.
• diagnóstico médico: por ejemplo, detección de cáncer de cuello uterino (Papnet), tumores de mama o ruidos cardíacos;
• defensa: varios sistemas de navegación y guía, sistemas de reconocimiento de objetivos, tecnología de reconocimiento de formas, etc.
• movilidad: sistemas avanzados de asistencia a la conducción, tecnología de vehículos autónomos, etc.

En psicología, el reconocimiento de patrones se utiliza para dar sentido e identificar objetos, y está estrechamente relacionado con la percepción. Esto explica cómo las entradas sensoriales que reciben los humanos se vuelven significativas. El reconocimiento de patrones se puede considerar de dos maneras diferentes. El primero se refiere a la coincidencia de plantillas y el segundo a la detección de características. Una plantilla es un patrón utilizado para producir elementos de las mismas proporciones. La hipótesis de coincidencia de plantillas sugiere que los estímulos entrantes se comparan con plantillas en la memoria a largo plazo. Si hay una coincidencia, se identifica el estímulo. Los modelos de detección de características, como el sistema Pandemonium para clasificar letras (Selfridge, 1959), sugieren que los estímulos se descomponen en sus componentes para su identificación. Una observación es una E mayúscula que tiene tres líneas horizontales y una línea vertical.

Algoritmos

Los algoritmos para el reconocimiento de patrones dependen del tipo de etiqueta de salida, de si el aprendizaje es supervisado o no, y de si el algoritmo es de naturaleza estadística o no estadística. Los algoritmos estadísticos se pueden clasificar además como generativos o discriminativos.

Métodos de clasificación (métodos que predicen etiquetas categóricas)

Paramétrico:

• Análisis discriminante lineal
• Análisis cuadrático discriminante
• Clasificador de entropía máxima (también conocido como regresión logística, regresión logística multinomial): tenga en cuenta que la regresión logística es un algoritmo para la clasificación, a pesar de su nombre. (El nombre proviene del hecho de que la regresión logística usa una extensión de un modelo de regresión lineal para modelar la probabilidad de que una entrada esté en una clase particular).

No paramétrico:

• Árboles de decisión, listas de decisiones
• Estimación de kernel y algoritmos de K-vecino más cercano
• Clasificador Naive Bayes
• Redes neuronales (perceptrones multicapa)
• perceptrones
• Máquinas de vectores de soporte
• Programación de expresión génica

Métodos de agrupamiento (métodos para clasificar y predecir etiquetas categóricas)

• Modelos de mezcla categórica
• Agrupación jerárquica (aglomerativa o divisiva)
• Agrupamiento de K-medias
• Agrupación de correlación
• Análisis de componentes principales del kernel (Kernel PCA)

Conjunto de algoritmos de aprendizaje (metaalgoritmos supervisados ​​para combinar varios algoritmos de aprendizaje)

• Impulso (meta-algoritmo)
• Agregación Bootstrap ("empaquetado")
• promedio de conjunto
• Mezcla de expertos, mezcla jerárquica de expertos

Métodos generales para predecir (conjuntos de) etiquetas estructuradas arbitrariamente

• redes bayesianas
• Campos aleatorios de Markov

Algoritmos de aprendizaje del subespacio multilineal (predicción de etiquetas de datos multidimensionales mediante representaciones de tensor)

Sin supervisión:

• Análisis multilineal de componentes principales (MPCA)

Métodos de etiquetado de secuencias con valores reales (predicción de secuencias de etiquetas con valores reales)

• Filtros Kalman
• Filtros de partículas

Métodos de regresión (predicción de etiquetas con valores reales)

• Regresión del proceso gaussiano (kriging)
• Regresión lineal y extensiones
• Análisis de componentes independientes (ICA)
• Análisis de componentes principales (PCA)

Métodos de etiquetado de secuencias (predicción de secuencias de etiquetas categóricas)

• Campos aleatorios condicionales (CRF)
• Modelos ocultos de Markov (HMM)
• Modelos de Markov de máxima entropía (MEMM)
• Redes neuronales recurrentes (RNN)
• Deformación dinámica del tiempo (DTW)