Teoría matemática del reconocimiento de patrones. Reconocimiento de patrones

Revisión de los métodos de reconocimiento de patrones existentes.

LP popova , Y SOBRE. datiev

La capacidad de “reconocer” se considera la propiedad principal del ser humano, así como de otros organismos vivos. El reconocimiento de patrones es una rama de la cibernética que desarrolla principios y métodos de clasificación, así como la identificación de objetos, fenómenos, procesos, señales, situaciones: todos aquellos objetos que pueden describirse mediante un conjunto finito de algunos signos o propiedades que caracterizan al objeto. .

Una imagen es una descripción de un objeto. Las imágenes tienen una propiedad característica, que se manifiesta en el hecho de que la familiarización con Número finito fenómenos del mismo conjunto hace posible reconocer todo lo que quieras Número grande sus representantes.

En la teoría del reconocimiento de patrones se pueden distinguir dos direcciones principales:

el estudio de las capacidades de reconocimiento que poseen los seres humanos y otros organismos vivos;

desarrollo de teoría y métodos para la construcción de dispositivos diseñados para resolver problemas individuales de reconocimiento de patrones en determinadas áreas de aplicación.

Además, el artículo describe los problemas, principios y métodos de implementación de sistemas de reconocimiento de imágenes asociados con el desarrollo de la segunda dirección. La segunda parte del artículo analiza los métodos de reconocimiento de patrones de redes neuronales, que pueden atribuirse a la primera dirección de la teoría del reconocimiento de patrones.

Problemas de construcción de sistemas de reconocimiento de imágenes.

Desafíos que surgen durante la construcción sistemas automáticos El reconocimiento de patrones generalmente se puede clasificar en varias áreas principales. El primero de ellos está relacionado con la presentación de los datos iniciales obtenidos como resultados de medición del objeto a reconocer. problema de sensibilidad. Cada valor medido es alguna “característica de una imagen u objeto”. Supongamos, por ejemplo, que las imágenes son caracteres alfanuméricos. En este caso, se puede realizar con éxito una medición de retina, similar a la que se muestra en la Fig. 1(a). utilizado en el sensor Si la retina consta de n elementos, entonces los resultados de la medición se pueden representar como un vector de medición o un vector de imagen. ,

donde cada elemento xi, toma, por ejemplo, el valor 1 si pasa por i-ésima celda la retina pasa la imagen del símbolo y el valor es 0 en caso contrario.

Veamos la figura. 2(b). En este caso, las imágenes son funciones continuas (como señales sonoras) de la variable t. Si la medición de los valores de la función se realiza en puntos discretos t1,t2, ..., tn, entonces el vector imagen se puede formar tomando x1= f(t1),x2=f(t2),... , xn = f(tn).

Figura 1. Medición de la retina

El segundo problema del reconocimiento de patrones está relacionado con la selección. rasgos característicos o propiedades de los datos fuente obtenidos y reduciendo la dimensión de los vectores de imagen. Este problema a menudo se define como un problema preprocesamiento y selección de características.

Las características de la clase de imagen son propiedades características, común a todas las imágenes. de esta clase. Las características que caracterizan las diferencias entre clases individuales pueden interpretarse como características entre clases. Las características intraclase, comunes a todas las clases consideradas, no contienen información útil desde el punto de vista del reconocimiento y no pueden tenerse en cuenta. La selección de características se considera una de las tareas importantes asociadas con la construcción de sistemas de reconocimiento. Si los resultados de la medición le permiten obtener un juego completo características distintivas Para todas las clases, el reconocimiento de imágenes y la clasificación en sí no causarán dificultades especiales. El reconocimiento automático se reducirá entonces a un simple proceso de comparación o a procedimientos como el escaneo de tablas. En la mayoría problemas prácticos reconocimiento, sin embargo, definición juego completo distinguir rasgos resulta extremadamente difícil, si no imposible. Generalmente es posible extraer algunas de las características distintivas de los datos sin procesar y utilizarlas para simplificar el proceso. reconocimiento automático imágenes En particular, la dimensión de los vectores de medición se puede reducir mediante transformaciones que minimicen la pérdida de información.

El tercer problema asociado con la construcción de sistemas de reconocimiento de patrones es encontrar los procedimientos de decisión óptimos necesarios para la identificación y clasificación. Una vez que los datos recopilados sobre los patrones a reconocer estén representados por puntos o vectores de medición en el espacio de patrones, deje que la máquina determine a qué clase de patrones corresponden estos datos. Supongamos que la máquina se diseñe para distinguir M clases, denotadas como w1, w2, ... ..., wm. En este caso, se puede considerar que el espacio de la imagen consta de M regiones, cada una de las cuales contiene puntos correspondientes a imágenes de una clase. En este caso, se puede considerar que la tarea de reconocimiento construye los límites de las áreas de decisión que separan M clases en función de los vectores de medición registrados. Definamos estos límites, por ejemplo, mediante las funciones de decisión d1(x), d2(x),..., dm(x). Estas funciones, también llamadas funciones discriminantes, son funciones escalares y univaluadas de la imagen de x. Si di (x) > dj (x), entonces la imagen x pertenece a la clase w1. En otras palabras, si i-ésimo decisivo función di(x) tiene el mayor valor, entonces en la figura se muestra una ilustración significativa de dicho esquema de clasificación automática basado en la implementación del proceso de toma de decisiones. 2 (en el diagrama “GR” - generador funciones decisivas).

Figura 2. Esquema de clasificación automática.

Las funciones decisivas se pueden obtener de varias formas. En el caso de que exista información a priori completa sobre las imágenes reconocidas, a partir de esta información se pueden determinar exactamente las funciones de decisión. Si sólo se dispone de información cualitativa sobre las imágenes, se pueden hacer suposiciones razonables sobre la forma de las funciones decisivas. B el último caso, los límites de las áreas de solución pueden desviarse significativamente de los reales, por lo que es necesario crear un sistema capaz de lograr un resultado satisfactorio a través de una serie de ajustes sucesivos.

Los objetos (imágenes) que se van a reconocer y clasificar mediante un sistema automático de reconocimiento de patrones deben tener un conjunto de características medibles. Cuando para todo un grupo de imágenes los resultados de las mediciones correspondientes resultan similares, se considera que estos objetos pertenecen a la misma clase. El objetivo del sistema de reconocimiento de patrones es, basándose en información recopilada Determinar una clase de objetos con características similares a las medidas en los objetos que se reconocen. La exactitud del reconocimiento depende de la cantidad de información discriminativa contenida en las características medidas y de la eficacia del uso de esta información.

Métodos básicos para implementar sistemas de reconocimiento de patrones.

El reconocimiento de patrones se refiere al problema de construir y aplicar operaciones formales sobre representaciones numéricas o simbólicas de objetos en el mundo real o ideal, cuyos resultados reflejan las relaciones de equivalencia entre estos objetos. Las relaciones de equivalencia expresan la pertenencia de los objetos evaluados a cualesquiera clases, consideradas como unidades semánticas independientes.

Al construir algoritmos de reconocimiento, las clases de equivalencia pueden ser especificadas por un investigador que utiliza sus propias representaciones significativas o utiliza fuentes externas. Información adicional sobre las similitudes y diferencias de los objetos en el contexto del problema que se resuelve. Luego hablan de “reconocimiento con un maestro”. De lo contrario, es decir Cuando sistema automático resuelve el problema de clasificación sin el uso de información de entrenamiento externo, hablan de clasificación automática o “reconocimiento no supervisado”. La mayoría de los algoritmos de reconocimiento de patrones requieren el uso de una potencia informática muy significativa, que sólo puede ser proporcionada por tecnología informática de alto rendimiento.

Varios autores (Yu.L. Barabash, V.I. Vasiliev, A.L. Gorelik, V.A. Skripkin, R. Duda, P. Hart, L.T. Kuzin, F.I. Peregudov, F.P. Tarasenko, Temnikov F.E., Afonin V.A., Dmitriev V.I., J. Tu, R. González, P. Winston, K. Fu, Ya.Z. diferente tipología Métodos de reconocimiento de patrones. Algunos autores distinguen entre métodos paramétricos, no paramétricos y heurísticos, otros identifican grupos de métodos basados ​​en escuelas y tendencias históricamente establecidas en este campo.

Al mismo tiempo, las tipologías conocidas no tienen en cuenta una característica muy significativa, que refleja la especificidad de la forma de presentar el conocimiento sobre área temática utilizando algún algoritmo formal de reconocimiento de patrones. D.A. Pospelov identifica dos formas principales de presentar el conocimiento:

Representación intencional: en forma de diagrama de conexiones entre atributos (características).

Representación extensiva: utilizando hechos específicos (objetos, ejemplos).

Cabe señalar que la existencia precisamente de estos dos grupos de métodos de reconocimiento: los que operan con signos y los que operan con objetos, es profundamente natural. Desde este punto de vista, ninguno de estos métodos, tomados por separado del otro, nos permite formar una reflexión adecuada del área temática. Entre estos métodos existe una relación de complementariedad en el sentido de N. Bohr, por lo que los sistemas de reconocimiento prometedores deberían prever la implementación de ambos métodos, y no solo de uno de ellos.

Así, la clasificación de los métodos de reconocimiento propuesta por D.A Pospelov se basa en las leyes fundamentales subyacentes. camino humano conocimiento en general, lo que lo coloca en una posición completamente especial (privilegiada) en comparación con otras clasificaciones, que en este contexto parecen más ligeras y artificiales.

Métodos intensionales

Una característica distintiva de los métodos intensionales es que utilizan elementos de operaciones al construir y aplicar algoritmos de reconocimiento de patrones. varias características signos y sus conexiones. Dichos elementos pueden ser valores individuales o intervalos de valores de características, valores promedio y variaciones, matrices de relaciones de características, etc., sobre las cuales se realizan acciones, expresadas en forma analítica o constructiva. Al mismo tiempo, los objetos en estos métodos no se consideran unidades de información integral, sino que actúan como indicadores para evaluar la interacción y el comportamiento de sus atributos.

El grupo de métodos intensionales para el reconocimiento de patrones es extenso y su división en subclases es hasta cierto punto condicional:

– métodos basados ​​en estimaciones de densidades de distribución de valores de características

– métodos basados ​​en suposiciones sobre la clase de funciones de decisión

– métodos lógicos

– métodos lingüísticos (estructurales).

Métodos basados ​​en estimaciones de densidades de distribución de valores de características. Estos métodos de reconocimiento de patrones están tomados de la teoría clásica. soluciones estadísticas, en el que los objetos de estudio son considerados como implementaciones de un universo multidimensional. variable aleatoria, distribuido en el espacio de características de acuerdo con alguna ley. Se basan en un marco bayesiano de toma de decisiones que atrae a probabilidades previas pertenencia de objetos a una u otra clase reconocible y densidades condicionales distribución de valores de vectores de características. Estos métodos se reducen a determinar la razón de probabilidad en Varias áreas espacio de características multidimensional.

Un grupo de métodos basados ​​en la estimación de las densidades de distribución de valores característicos está directamente relacionado con los métodos de análisis discriminante. El enfoque bayesiano para la toma de decisiones es uno de los más desarrollados en estadísticas modernas los llamados métodos paramétricos, por los que se considera conocido expresión analítica ley de distribución (en en este caso ley normal) y sólo necesita ser estimado una pequena cantidad de parámetros (vectores de valores medios y matrices de covarianza).

Este grupo también incluye el método de calcular el índice de verosimilitud de características independientes. Este método, con excepción del supuesto de independencia de las características (que en realidad casi nunca se cumple), no presupone conocimiento. tipo funcional ley de distribución. Se puede clasificar como un método no paramétrico.

Otros métodos no paramétricos, utilizados cuando se desconoce la forma de la curva de densidad de distribución y no se puede hacer ninguna suposición sobre su naturaleza, ocupan una posición especial. Estos incluyen el conocido método de histogramas multidimensionales, el " k-vecinos más cercanos, método de distancia euclidiana, método funciones potenciales y otros, cuya generalización es el método denominado “estimaciones de Parzen”. Estos métodos operan formalmente en objetos como estructuras integrales, pero dependiendo del tipo de tarea de reconocimiento, pueden actuar tanto en forma intensional como extensional.

Los métodos no paramétricos analizan el número relativo de objetos que caen en volúmenes multidimensionales determinados y utilizan Varias funciones distancias entre los objetos de la muestra de entrenamiento y los objetos reconocidos. Para las características cuantitativas, cuando su número es mucho menor que el tamaño de la muestra, las operaciones con objetos juegan un papel intermedio en la estimación de las densidades de distribución local. probabilidades condicionales y los objetos no llevan la carga semántica de unidades de información independientes. Al mismo tiempo, cuando el número de signos es proporcional o mas numero de los objetos en estudio, y los signos son de naturaleza cualitativa o dicotómica, entonces no se puede hablar de estimaciones locales de las densidades de distribución de probabilidad. En este caso, los objetos en los métodos no paramétricos especificados se consideran unidades de información independientes (integral hechos empíricos) y estos métodos adquieren el significado de evaluar las similitudes y diferencias de los objetos en estudio.

Por lo tanto, las mismas operaciones tecnológicas de los métodos no paramétricos, dependiendo de las condiciones del problema, dan sentido a las estimaciones locales de las densidades de distribución de probabilidad de los valores de las características o a las estimaciones de la similitud y diferencia de los objetos.

En el contexto de la representación intensional del conocimiento, aquí se considera el primer lado de los métodos no paramétricos, como estimaciones de densidades de distribución de probabilidad. Muchos autores señalan que en la práctica los métodos no paramétricos como los estimadores de Parzen funcionan bien. Las principales dificultades al utilizar estos métodos son la necesidad de recordar toda la muestra de entrenamiento para calcular estimaciones de las densidades de distribución de probabilidad local y la alta sensibilidad a la falta de representatividad de la muestra de entrenamiento.

Métodos basados ​​en supuestos sobre la clase de funciones de decisión. En este grupo de métodos se considera conocida la forma general de la función de decisión y se especifica la funcionalidad de su calidad. A partir de esta funcional se busca la mejor aproximación de la función de decisión en la secuencia de entrenamiento. Las más comunes son las representaciones de funciones de decisión en forma de polinomios lineales y no lineales generalizados. La regla de decisión funcional de calidad suele estar asociada con un error de clasificación.

La principal ventaja de los métodos basados ​​​​en supuestos sobre la clase de funciones de decisión es la claridad de la formulación matemática del problema de reconocimiento como un problema de búsqueda de un extremo. La solución a este problema a menudo se logra mediante algunos algoritmos de gradiente. La variedad de métodos en este grupo se explica por la amplia gama de funcionales de calidad de reglas de decisión y algoritmos de búsqueda extremos utilizados. Una generalización de los algoritmos considerados, que incluyen, en particular, el algoritmo de Newton, los algoritmos de tipo perceptrón, etc., es el método de aproximación estocástica. A diferencia de los métodos de reconocimiento paramétrico, el éxito de utilizar este grupo de métodos no depende tanto de la discrepancia entre las ideas teóricas sobre las leyes de distribución de objetos en el espacio de características y la realidad empírica. Todas las operaciones están subordinadas a un objetivo principal: encontrar el extremo de la calidad funcional de la regla de decisión. Al mismo tiempo, los resultados de los métodos paramétricos y considerados pueden ser similares. Como se muestra arriba, los métodos paramétricos para el caso distribuciones normales Los objetos de diferentes clases con matrices de covarianza iguales conducen a funciones de decisión lineal. Tenga en cuenta también que los algoritmos para seleccionar características informativas en modelos de diagnóstico lineal pueden interpretarse como versiones especiales de algoritmos de gradiente para buscar extremos.

Posibilidades de algoritmos de gradiente para buscar extremos, especialmente en el grupo de los lineales. reglas decisivas, han sido bastante bien estudiados. La convergencia de estos algoritmos se ha demostrado sólo en el caso en que las clases de objetos reconocidas se muestran en el espacio de características mediante estructuras geométricas compactas. Sin embargo, el deseo de lograr una calidad suficiente de la regla de decisión a menudo puede satisfacerse utilizando algoritmos que no tienen una estricta prueba matemática convergencia de la solución al extremo global.

Dichos algoritmos incluyen grupo grande Procedimientos de programación heurística que representan la dirección del modelado evolutivo. El modelado evolutivo es un método biónico tomado de la naturaleza. Se basa en el uso de mecanismos de evolución conocidos para reemplazar el proceso de modelado significativo de un objeto complejo por el modelado fenomenológico de su evolución.

Un conocido representante del modelado evolutivo en el reconocimiento de patrones es el método de contabilidad grupal de argumentos (MGUA). La base de GMDH es el principio de autoorganización y los algoritmos de GMDH reproducen el esquema de selección masiva. En los algoritmos GMDH, los miembros de un polinomio generalizado se sintetizan y seleccionan de una manera especial, lo que a menudo se denomina polinomio de Kolmogorov-Gabor. Esta síntesis y selección se lleva a cabo con una complejidad creciente y es imposible predecir de antemano qué forma final tendrá el polinomio generalizado. En primer lugar, generalmente se consideran combinaciones simples por pares de características iniciales, a partir de las cuales se compilan ecuaciones de funciones de decisión, generalmente no superiores al segundo orden. Cada ecuación se analiza como una función de decisión independiente y los valores de los parámetros de las ecuaciones compiladas se encuentran de una forma u otra utilizando la muestra de entrenamiento. Luego, del conjunto resultante de funciones de decisión, se seleccionan algunas de las mejores. La calidad de las funciones de decisión individuales se verifica en una muestra de control (validación), lo que a veces se denomina principio de suma externa. Las funciones de decisión parcial seleccionadas se consideran además como variables intermedias que sirven como argumentos iniciales para una síntesis similar de nuevas funciones de decisión, etc. El proceso de dicha síntesis jerárquica continúa hasta que se alcanza el extremo del criterio de calidad de la función de decisión, que en la práctica Se manifiesta en el deterioro de esta cualidad al intentar aumentar aún más el orden de los términos polinomiales con respecto a las características originales.

El principio de autoorganización que subyace al GMDH se denomina autoorganización heurística, ya que todo el proceso se basa en la introducción de adiciones externas, seleccionadas heurísticamente. El resultado de una decisión puede depender significativamente de estas heurísticas. El modelo de diagnóstico resultante depende de cómo se dividen los objetos en muestras de entrenamiento y prueba, cómo se determina el criterio de calidad del reconocimiento, cuántas variables se pasan a la siguiente fila de selección, etc.

Las características indicadas de los algoritmos GMDH también son características de otros enfoques del modelado evolutivo. Pero observemos aquí un aspecto más de los métodos que estamos considerando. Ésta es su esencia significativa. Utilizando métodos basados ​​en suposiciones sobre la clase de funciones de decisión (evolutivas y de gradiente), es posible construir modelos de diagnóstico. alta complejidad y obtener resultados prácticamente aceptables. Al mismo tiempo, el logro de objetivos prácticos en este caso no va acompañado de la extracción de nuevos conocimientos sobre la naturaleza de los objetos reconocidos. La posibilidad de extraer este conocimiento, en particular el conocimiento sobre los mecanismos de interacción de atributos (características), está aquí fundamentalmente limitada por la estructura dada de dicha interacción, fijada en la forma seleccionada de funciones de decisión. Por lo tanto, lo máximo que se puede decir después de construir un modelo de diagnóstico particular es enumerar combinaciones de características y las características mismas incluidas en el modelo resultante. Pero el significado de combinaciones que reflejan la naturaleza y estructura de las distribuciones de los objetos en estudio a menudo permanece sin revelar en el marco de este enfoque.

Métodos booleanos. Los métodos lógicos de reconocimiento de patrones se basan en el aparato del álgebra lógica y permiten operar con información contenida no solo en signos individuales, pero también en combinaciones de valores de características. En estos métodos, los valores de cualquier atributo se consideran eventos elementales.

En la forma más general, los métodos lógicos se pueden caracterizar como un tipo de búsqueda que utiliza una muestra de entrenamiento de patrones lógicos y la formación de algún sistema de reglas de decisión lógica (por ejemplo, en forma de conjunciones eventos elementales), cada uno de los cuales tiene su propio peso. Grupo métodos lógicos es diverso e incluye métodos de diversa complejidad y profundidad de análisis. Para características dicotómicas (booleanas), son populares los llamados clasificadores en forma de árbol, el método de prueba sin salida, el algoritmo "Bark" y otros. Más métodos complejos basado en la formalización métodos inductivos D.S.Mill. La formalización se lleva a cabo mediante la construcción de una teoría cuasi axiomática y se basa en una lógica multiclasificada de muchos valores con cuantificadores sobre tuplas de longitud variable.

El algoritmo "Kora", al igual que otros métodos lógicos de reconocimiento de patrones, requiere bastante mano de obra, ya que se requiere una búsqueda completa al seleccionar conjunciones. Por lo tanto, al aplicar métodos lógicos, altos requisitos A organización efectiva proceso computacional, y estos métodos funcionan bien con dimensiones relativamente pequeñas del espacio de características y solo en computadoras potentes.

Métodos lingüísticos (sintácticos o estructurales). Los métodos lingüísticos de reconocimiento de patrones se basan en el uso de gramáticas especiales que generan lenguajes, con la ayuda de las cuales se puede describir un conjunto de propiedades de los objetos reconocidos. La gramática se refiere a las reglas para construir objetos a partir de estos elementos no derivados.

Si la descripción de imágenes se realiza utilizando elementos no derivados (subimágenes) y sus relaciones, entonces se utiliza un enfoque lingüístico o sintáctico que utiliza el principio de generalidad de propiedades para construir sistemas de reconocimiento automático. La imagen se puede describir usando estructura jerarquica subimágenes, similares a la estructura sintáctica del lenguaje. Esta circunstancia permite aplicar la teoría de lenguajes formales. Se supone que una gramática de imágenes contiene conjuntos finitos de elementos llamados variables, elementos no derivados y reglas de sustitución. La naturaleza de las reglas de sustitución determina el tipo de gramática. Entre las gramáticas más estudiadas podemos destacar las gramáticas regulares, sin contexto y de componentes directos. Puntos clave de este enfoque son la selección de elementos no derivados de la imagen, la combinación de estos elementos y las relaciones que los conectan en gramáticas de imágenes y, finalmente, la implementación de los procesos de análisis y reconocimiento en el lenguaje apropiado. Este enfoque es especialmente útil cuando se trabaja con imágenes que no pueden describirse mediante mediciones numéricas o que son tan complejas que señales locales no se pueden identificar y tenemos que acceder a las propiedades globales de los objetos.

Por ejemplo, E.A. Butakov, V.I. Ostrovsky, I.L. Fadeev propone la siguiente estructura del sistema para el procesamiento de imágenes (Fig. 3), utilizando enfoque lingüístico, donde cada uno de los bloques funcionales es un complejo (módulo) de software (microprograma) que implementa funciones relevantes.

Figura 3. Esquema estructural dispositivo de reconocimiento

Los intentos de aplicar los métodos de la lingüística matemática al problema del análisis de imágenes conducen a la necesidad de resolver una serie de problemas asociados con el mapeo de la estructura bidimensional de una imagen en cadenas unidimensionales de un lenguaje formal.

Métodos extensionales

En los métodos de este grupo, a diferencia de la dirección intensional, a cada objeto estudiado se le da, en mayor o menor medida, una interpretación independiente. valor diagnóstico. En esencia, estos métodos se acercan al enfoque clínico, que considera a las personas no como una cadena de objetos clasificados según uno u otro indicador, sino como sistemas completos, cada uno de los cuales es individual y tiene un valor diagnóstico especial. Esta actitud cuidadosa hacia los objetos de investigación no permite excluir o perder información sobre cada objeto individual, lo que ocurre cuando se utilizan métodos de dirección intencional que utilizan objetos sólo para detectar y registrar patrones de comportamiento de sus atributos.

Las principales operaciones en el reconocimiento de patrones utilizando los métodos discutidos son las operaciones para determinar las similitudes y diferencias de objetos. Los objetos del grupo de métodos especificado desempeñan el papel de precedentes de diagnóstico. Además, dependiendo de las condiciones de una tarea específica, el papel de un precedente individual puede variar dentro de los límites más amplios: desde el principal y determinante hasta la participación muy indirecta en el proceso de reconocimiento. A su vez, las condiciones del problema pueden requerir la participación de varias cantidades precedentes de diagnóstico: desde uno en cada clase reconocida hasta el tamaño completo de la muestra, así como diferentes caminos calcular medidas de similitud y diferencia entre objetos. Estos requisitos explican la división adicional de los métodos extensionales en subclases:

método de comparación con el prototipo;

método de k-vecinos más cercanos;

colectivos de reglas de decisión.

Método de comparación con el prototipo. Este es el método de reconocimiento extensional más simple. Se utiliza, por ejemplo, cuando las clases reconocidas se muestran en el espacio de características mediante agrupaciones geométricas compactas. En este caso, normalmente se selecciona como punto prototipo el centro de la agrupación geométrica de la clase (o el objeto más cercano al centro).

Para clasificar un objeto desconocido, se encuentra el prototipo más cercano a él y el objeto pertenece a la misma clase que este prototipo. Obviamente, en este método no se generan imágenes de clases generalizadas.

Se pueden utilizar varios tipos de distancias como medida de proximidad. A menudo, para características dicotómicas, se utiliza la distancia de Hamming, que en este caso es igual al cuadrado de la distancia euclidiana. En este caso, la regla de decisión para clasificar objetos es equivalente a una función de decisión lineal.

Este hecho debe destacarse especialmente. Demuestra claramente la conexión entre el prototipo y la representación de atributos de información sobre la estructura de los datos. Usando la representación anterior, puede, por ejemplo, cualquier tradicional escala de medición, cual es función lineal a partir de los significados de rasgos dicotómicos, considerados como un hipotético prototipo diagnóstico. A su vez, si el análisis de la estructura espacial de las clases reconocidas nos permite sacar una conclusión sobre su compacidad geométrica, entonces basta con reemplazar cada una de estas clases con un prototipo, que en realidad equivale a un modelo de diagnóstico lineal.

En la práctica, por supuesto, la situación suele ser diferente de la descrita. ejemplo idealizado. Ante un investigador que pretende aplicar un método de reconocimiento basado en la comparación con prototipos clases de diagnostico, levantarse problemas difíciles. Se trata, en primer lugar, de la elección de la medida de proximidad (métrica), que puede cambiar significativamente la configuración espacial de la distribución de los objetos. Y, en segundo lugar, un problema independiente es el análisis de estructuras multidimensionales de datos experimentales. Ambos problemas son especialmente graves para el investigador en condiciones de alta dimensionalidad del espacio de características, característica de los problemas reales.

El método de los k vecinos más cercanos. El método de los k vecinos más cercanos para resolver problemas de análisis discriminante se propuso por primera vez en 1952. Es el siguiente.

Al clasificar un objeto desconocido, se encuentra numero dado(k) geométricamente más cercano a él en el espacio de características de otros objetos (vecinos más cercanos) con pertenencia ya conocida a clases reconocibles. La decisión de asignar un objeto desconocido a una clase de diagnóstico particular se toma analizando información sobre esta afiliación conocida de sus vecinos más cercanos, por ejemplo, utilizando un simple recuento de votos.

Inicialmente, el método de los k vecinos más cercanos se consideró como un método no paramétrico para estimar la razón de verosimilitud. Para este método, se obtuvieron estimaciones teóricas de su efectividad en comparación con el clasificador bayesiano óptimo. Se ha demostrado que las probabilidades de error asintótico para el método de los k vecinos más cercanos exceden los errores de la regla de Bayes en no más de dos veces.

Como se señaló anteriormente, en problemas reales A menudo hay que operar con objetos que se describen. gran cantidad características cualitativas (dicotómicas). En este caso, la dimensión del espacio característico es proporcional o excede el volumen de la muestra en estudio. En tales condiciones, es conveniente interpretar cada objeto de la muestra de entrenamiento como un clasificador lineal independiente. Entonces esta o aquella clase de diagnóstico no está representada por un prototipo, sino por un conjunto de clasificadores lineales. La interacción combinada de clasificadores lineales da como resultado en última instancia una superficie lineal por partes que separa las clases reconocidas en el espacio de características. El tipo de superficie de separación, que consta de piezas de hiperplanos, puede variar y depende de posición relativa poblaciones clasificadas.

También se puede utilizar otra interpretación de los mecanismos de clasificación utilizando la regla de los k vecinos más cercanos. Se basa en la idea de la existencia de algunas variables latentes, abstractas o relacionadas por alguna transformación con el espacio de características original. Si en el espacio de variables latentes las distancias por pares entre objetos son las mismas que en el espacio de características originales, y el número de estas variables es significativo menos numero objetos, entonces la interpretación del método de los k vecinos más cercanos puede considerarse desde el punto de vista de la comparación de estimaciones no paramétricas de las densidades de distribución de probabilidades condicionales. La visión de las variables latentes presentada aquí es de naturaleza similar a la visión de la dimensionalidad verdadera y otras vistas utilizadas en diversas técnicas de reducción de dimensionalidad.

Cuando se utiliza el método de los k vecinos más cercanos para el reconocimiento de patrones, el investigador tiene que decidir problema complejo elegir una métrica para determinar la proximidad de los objetos diagnosticados. Este problema en condiciones de alta dimensionalidad del espacio de características se agrava extremadamente debido a la suficiente complejidad. este método, lo que resulta significativo incluso para ordenadores de alto rendimiento. Por lo tanto, aquí, al igual que en el método de comparación con un prototipo, es necesario resolver el problema creativo de analizar la estructura multidimensional de los datos experimentales para minimizar el número de objetos que representan clases de diagnóstico.

Algoritmos de cálculo de valoraciones (votación). El principio de funcionamiento de los algoritmos de cálculo de evaluación (ABO) es calcular la prioridad (puntuaciones de similitud) caracterizando la "proximidad" de los objetos reconocidos y de referencia de acuerdo con un sistema de conjuntos de características, que es un sistema de subconjuntos de un conjunto de características dado. .

A diferencia de todos los métodos discutidos anteriormente, los algoritmos para calcular estimaciones operan con descripciones de objetos de una manera fundamentalmente nueva. Para estos algoritmos, los objetos existen simultáneamente en subespacios muy diferentes del espacio de características. La clase ABO lleva la idea de utilizar características a su conclusión lógica: dado que no siempre se sabe qué combinaciones de características son las más informativas, en ABO el grado de similitud de los objetos se calcula comparando todas las combinaciones posibles o específicas de características incluidas en las descripciones de los objetos.

Colectivos de reglas de decisión. EN regla decisiva Se utiliza un esquema de reconocimiento de dos niveles. En el primer nivel operan algoritmos de reconocimiento privado, cuyos resultados se combinan en el segundo nivel en el bloque de síntesis. Los métodos más comunes de dicha unificación se basan en identificar áreas de competencia de un algoritmo en particular. La forma más sencilla de encontrar áreas de competencia es dividir a priori el espacio de atributos basándose en consideraciones profesionales de una ciencia en particular (por ejemplo, estratificar la muestra según un determinado atributo). Luego, para cada una de las áreas seleccionadas, se construye su propio algoritmo de reconocimiento. Otro método se basa en el uso de análisis formal para determinar áreas locales del espacio de características como vecindades de objetos reconocidos para los cuales se ha demostrado el éxito de cualquier algoritmo de reconocimiento particular.

Mayoría enfoque general para construir un bloque de síntesis, considera los indicadores resultantes de algoritmos particulares como características iniciales para construir una nueva regla de decisión generalizada. En este caso, se pueden utilizar todos los métodos anteriores de direcciones intensionales y extensionales en el reconocimiento de patrones. Para resolver el problema de crear un grupo de reglas de decisión son eficaces los algoritmos lógicos del tipo "Kora" y los algoritmos de cálculo de estimaciones (ABO), que forman la base de los llamados enfoque algebraico, que proporciona investigación y descripción constructiva de los algoritmos de reconocimiento, en cuyo marco encajan todos los tipos de algoritmos existentes.

Métodos de redes neuronales

Los métodos de redes neuronales son métodos basados ​​en la aplicación. varios tipos redes neuronales (NN). Las principales áreas de aplicación de diversas redes neuronales para el reconocimiento de patrones e imágenes:

Aplicación para extraer características clave o rasgos de imágenes determinadas.

clasificación de las imágenes en sí o de las características ya extraídas de ellas (en el primer caso, la extracción de las características clave se produce implícitamente dentro de la red),

resolver problemas de optimización.

Multicapa Redes neuronales. La arquitectura de una red neuronal multicapa (MNN) consta de capas conectadas secuencialmente, donde la neurona de cada capa está conectada con sus entradas a todas las neuronas de la capa anterior y las salidas de la siguiente.

La aplicación más sencilla de una red neuronal de una sola capa (llamada memoria autoasociativa) es entrenar la red para reconstruir imágenes alimentadas. Al alimentar una imagen de prueba como entrada y calcular la calidad de la imagen reconstruida, puede evaluar qué tan bien la red reconoció la imagen de entrada. Propiedades positivas Este método permite restaurar imágenes distorsionadas y ruidosas en la red, pero no es adecuado para fines más serios.

MNN también se utiliza para la clasificación directa de imágenes: ya sea la imagen en sí de alguna forma o un conjunto de características clave de la imagen previamente extraídas se suministra como entrada en la salida, la neurona con actividad máxima indica la pertenencia a la clase reconocida (Fig. 4). Si esta actividad está por debajo de cierto umbral, se considera que la imagen enviada no pertenece a ninguna de las clases conocidas. El proceso de aprendizaje establece la correspondencia de las imágenes suministradas a la entrada con la pertenencia a una determinada clase. A esto se le llama aprendizaje supervisado. Este enfoque es bueno para tareas de control de acceso de un pequeño grupo de personas. Este enfoque garantiza que la red compare directamente las imágenes en sí, pero a medida que aumenta el número de clases, el tiempo de entrenamiento y operación de la red aumenta exponencialmente. Por lo tanto, para tareas como buscar persona similar en una base de datos grande, requiere extraer un conjunto compacto de características clave sobre las cuales realizar la búsqueda.

En se describe un enfoque para la clasificación utilizando características de frecuencia de toda la imagen. Se utilizó una red neuronal de una sola capa basada en neuronas multivalor.

La aplicación de una red neuronal para la clasificación de imágenes se muestra cuando la entrada de la red recibe los resultados de la descomposición de la imagen utilizando el método del componente principal.

En MNN clásico, las conexiones neuronales entre capas están completamente conectadas y la imagen se representa como un vector unidimensional, aunque es bidimensional. La arquitectura de la red neuronal convolucional tiene como objetivo superar estas deficiencias. Utilizó campos receptores locales (proporcionan conectividad bidimensional local de neuronas), pesos compartidos (proporcionan detección de ciertas características en cualquier parte de la imagen) y organización jerárquica con submuestreo espacial. La red neuronal convolucional (CNN) proporciona resistencia parcial a cambios de escala, desplazamientos, rotaciones y distorsiones.

Los MNN también se utilizan para detectar objetos de cierto tipo. Además del hecho de que cualquier MNN entrenado puede, hasta cierto punto, determinar si las imágenes pertenecen a “sus” clases, puede entrenarse especialmente para detectar de manera confiable ciertas clases. En este caso, las clases de salida serán clases que pertenecen y no pertenecen al tipo de imagen dado. Se utilizó un detector de red neuronal para detectar una imagen de rostro en la imagen de entrada. La imagen se escaneó con una ventana de 20x20 píxeles, que se introdujo en la entrada de la red, que decide si un área determinada pertenece a la clase de rostros. El entrenamiento se llevó a cabo utilizando ambos ejemplos positivos (varias imagenes rostros) y negativos (imágenes que no son rostros). Para aumentar la confiabilidad de la detección se utilizó un equipo de redes neuronales, entrenadas con diferentes pesos iniciales, como resultado de lo cual las redes neuronales cometieron errores de diferentes maneras, y la decisión final se tomó mediante votación de todo el equipo.

Figura 5. Componentes principales (caras propias) y descomposición de la imagen en componentes principales

También se utiliza una red neuronal para extraer características clave de la imagen, que luego se utilizan para la clasificación posterior. En , se muestra un método de implementación de redes neuronales del método de análisis de componentes principales. La esencia del método de análisis de componentes principales es obtener coeficientes decorados al máximo que caractericen las imágenes de entrada. Estos coeficientes se denominan componentes principales y se utilizan para la compresión estadística de imágenes, en la que se utiliza una pequeña cantidad de coeficientes para representar la imagen completa. Una red neuronal con una capa oculta que contiene N neuronas (que es mucho más pequeña que la dimensión de la imagen), entrenada utilizando el método propagación hacia atrás Los errores se restauran en la salida, la imagen suministrada a la entrada forma los coeficientes de los primeros N componentes principales en la salida de las neuronas ocultas, que se utilizan para comparar. Normalmente se utilizan de 10 a 200 componentes principales. A medida que aumenta el número de un componente, su representatividad disminuye considerablemente y no tiene sentido utilizar componentes con números grandes. Cuando se utilizan funciones de activación no lineales de elementos neuronales, es posible una descomposición no lineal en componentes principales. La no linealidad permite reflejar con mayor precisión las variaciones en los datos de entrada. Aplicando el análisis de componentes principales a la descomposición de imágenes de rostros, obtenemos componentes principales llamados rostros propios, que también se caracterizan por propiedad útil– hay componentes que reflejan principalmente características esenciales de una persona como el género, la raza, las emociones. Cuando se reconstruyen, los componentes tienen una apariencia de cara: los primeros reflejan la forma más general de la cara y los segundos representan varias pequeñas diferencias entre las caras (Fig. 5). Este método es muy adecuado para encontrar imágenes similares de rostros en bases de datos grandes. También se muestra la posibilidad de reducir aún más las dimensiones de los componentes principales utilizando NN. Al evaluar la calidad de la reconstrucción de la imagen de entrada, se puede determinar con mucha precisión su pertenencia a la clase de caras.

Redes neuronales alto orden. Las redes neuronales de alto orden (HANN) se diferencian de las MNN en que tienen una sola capa, pero las entradas de las neuronas también reciben términos de alto orden, que son el producto de dos o más componentes del vector de entrada. Estas redes también pueden formar superficies divisorias complejas.

Redes neuronales de Hopfield. Hopfield NN (HNS) es de una sola capa y está completamente conectado (no hay conexiones entre las neuronas), sus salidas están conectadas a las entradas. A diferencia de MNS, NSC es relajación, es decir al estar establecido en el estado inicial, opera hasta alcanzar un estado estable, que será su valor de salida. Para buscar un mínimo global en relación a problemas de optimización se utilizan modificaciones estocásticas del NSC.

El uso de NSH como memoria asociativa le permite restaurar con precisión las imágenes para las que está entrenada la red cuando se envía una imagen distorsionada a la entrada. En este caso, la red “recordará” el más cercano (en el sentido mínimo local energía) imagen, y así la reconoce. Dicho funcionamiento también puede representarse como la aplicación secuencial de la memoria autoasociativa descrita anteriormente. A diferencia de la memoria autoasociativa, NSC restaurará la imagen con perfecta precisión. Para evitar mínimos de interferencia y aumentar la capacidad de la red, utilice varios métodos.

Redes neuronales Kohonen autoorganizadas. Las redes neuronales Kohonen autoorganizadas (KONN) proporcionan un ordenamiento topológico del espacio de la imagen de entrada. Permiten un mapeo topológicamente continuo de un espacio de entrada n-dimensional en un espacio de salida m-dimensional, m<

Cognitrón. La arquitectura de Cognitron es similar a la estructura de la corteza visual; tiene una organización jerárquica de múltiples capas en la que las neuronas entre capas están conectadas sólo localmente. Se aprende mediante aprendizaje competitivo (sin profesor). Cada capa del cerebro implementa diferentes niveles de generalización; la capa de entrada es sensible a patrones simples, como líneas, y su orientación en ciertas áreas del dominio visual, mientras que la respuesta de otras capas es más compleja, abstracta e independiente de la posición del patrón. Se implementan funciones similares en el cognitrón modelando la organización de la corteza visual.

Neocognitron es un desarrollo posterior de la idea de cognitrón y refleja con mayor precisión la estructura del sistema visual, permite reconocer imágenes independientemente de sus transformaciones, rotaciones, distorsiones y cambios de escala.

Cognitron es una poderosa herramienta de reconocimiento de imágenes, pero requiere altos costos computacionales, que actualmente son inalcanzables.

Los métodos de redes neuronales considerados proporcionan un reconocimiento de imágenes rápido y confiable, pero cuando se utilizan estos métodos surgen problemas al reconocer objetos tridimensionales. Sin embargo, este enfoque tiene muchas ventajas.

Conclusión

Actualmente, existe una gran cantidad de sistemas de reconocimiento automático de patrones para diversas tareas aplicadas.

El reconocimiento de patrones mediante métodos formales como dirección científica fundamental es inagotable.

Los métodos matemáticos de procesamiento de imágenes tienen una amplia variedad de aplicaciones: ciencia, tecnología, medicina, ámbito social. En el futuro, el papel del reconocimiento de patrones en la vida humana aumentará aún más.

Los métodos de redes neuronales proporcionan un reconocimiento de imágenes rápido y confiable. Este enfoque tiene muchas ventajas y es uno de los más prometedores.

Literatura

D.V. Brilyuk, V.V. Starovoítov. Métodos de redes neuronales para el reconocimiento de imágenes. // /

Kuzin L.T. Fundamentos de la cibernética: Fundamentos de los modelos cibernéticos. T.2. - M.: Energía, 1979. - 584 p.

Peregudov F.I., Tarasenko F.P. Introducción al análisis de sistemas: Libro de texto. – M.: Escuela Superior, 1997. - 389 p.

Temnikov F.E., Afonin V.A., Dmitriev V.I. Fundamentos teóricos de las tecnologías de la información. - M.: Energía, 1979. - 511 p.

Tu J., González R. Principios de reconocimiento de patrones. /Trans. De inglés - M.: Mir, 1978. - 410 p.

Winston P. Inteligencia artificial. /Trans. De inglés - M.: Mir, 1980. - 520 p.

Fu K. Métodos estructurales en reconocimiento de patrones: traducido del inglés. - M.: Mir, 1977. - 320 p.

Tsypkin Ya.Z. Fundamentos de la teoría de la información de la identificación. - M.: Nauka, 1984. - 520 p.

Pospelov G.S. La inteligencia artificial es la base de las nuevas tecnologías de la información. - M.: Nauka, 1988. - 280 p.

Yu Lifshits, Métodos estadísticos de reconocimiento de patrones ///modern/07modernnote.pdf

Bohr N. Física atómica y cognición humana. /Traducido del inglés - M.: Mir, 1961. - 151 p.

Butakov E.A., Ostrovsky V.I., Fadeev I.L. Procesamiento de imágenes en una computadora.1987.-236p.

Duda R., Hart P. Reconocimiento de patrones y análisis de escenas. /Traducido del inglés - M.: Mir, 1978. - 510 p.

Duque V.A. Psicodiagnóstico informático. - San Petersburgo: Hermandad, 1994. - 365 p.

Aizenberg I. N., Aizenberg N. N. y Krivosheev G. A. Neuronas binarias universales y de valores múltiples: algoritmos de aprendizaje, aplicaciones al procesamiento y reconocimiento de imágenes. Apuntes de conferencias sobre inteligencia artificial: aprendizaje automático y minería de datos en el reconocimiento de patrones, 1999, págs. 21-35.

Ranganath S. y Arun K. Reconocimiento facial mediante funciones de transformación y redes neuronales. Reconocimiento de patrones 1997, vol. 30, págs. 1615-1622.

Golovko V.A. Neurointeligencia: teoría y aplicaciones. Libro 1. Organización y entrenamiento de redes neuronales con conexiones directas y de retroalimentación - Brest: BPI, 1999, - 260 págs.

Vetter T. y Poggio T. Clases de objetos lineales y síntesis de imágenes a partir de una única imagen de ejemplo. Transacciones IEEE sobre análisis de patrones e inteligencia artificial 1997, vol. 19, págs. 733-742.

Golovko V.A. Neurointeligencia: teoría y aplicaciones. Libro 2. Autoorganización, tolerancia a fallos y aplicación de redes neuronales - Brest: BPI, 1999, - 228 p.

Lawrence S., Giles C. L., Tsoi A. C. y Back A. D. Reconocimiento facial: un enfoque de red neuronal convolucional. Transacciones IEEE en redes neuronales, número especial sobre redes neuronales y reconocimiento de patrones, págs. 1-24.

Wasserman F. Tecnología de neurocomputadoras: teoría y práctica, 1992 - 184 p.

Rowley, H. A., Baluja, S. y Kanade, T. Detección de rostros basada en redes neuronales. Transacciones IEEE sobre análisis de patrones e inteligencia artificial 1998, vol. 20, págs. 23-37.

Valentin D., Abdi H., O"Toole A. J. y Cottrell G. W. Modelos conexionistas de procesamiento facial: una encuesta. EN: Pattern Recognition 1994, Vol. 27, págs. 1209-1230.

Documento

Ellos inventan algoritmos reconocimientoimágenes. Métodosreconocimientoimágenes Como se señaló anteriormente... la realidad no es existe"ecosistemas en general", y existir solo individual... conclusiones de este detallado revisarmétodosreconocimiento presentamos en...

1. Revisión de métodos de identificación de personas basándose en imágenes faciales, teniendo en cuenta las características del reconocimiento visual.

   Revisar

   ... reconocimiento por una persona de objetos de bajo contraste, incl. personas Dado revisar común métodos ... existe linea completa métodos ... forma, como resultado de la investigación, una plataforma para el desarrollo métodoreconocimiento ...

2. Nombrado en honor a Glazkova Valentina Vladimirovna INVESTIGACIÓN Y DESARROLLO DE MÉTODOS PARA LA CONSTRUCCIÓN DE HERRAMIENTAS DE SOFTWARE PARA LA CLASIFICACIÓN DE DOCUMENTOS DE HIPERTEXTO MULTITEMAS Especialidad 05

   Resumen de la tesis.

   Documentos de hipertexto. El capítulo proporciona revisarexistentemétodos soluciones al problema considerado, descripción... cortando las clases menos relevantes // Matemáticas métodosreconocimientoimágenes: XIII Conferencia Panrusa. Región de Leningrado...

3. Diapositiva 0 Revisión de tareas bioinformáticas relacionadas con el análisis y procesamiento de textos genéticos.

   Conferencia

   Secuencias de ADN y proteínas. Revisar tareas bioinformáticas como tareas... las señales requieren el uso de modernos métodosreconocimientoimágenes, enfoques estadísticos y... con baja densidad genética. Existente Los programas de predicción de genes no son...

Los robots modernos, equipados con sistemas de visión, pueden ver bien para poder trabajar con el mundo real. Pueden sacar conclusiones sobre qué tipo de objetos están presentes, qué relaciones tienen entre ellos y qué grupos forman.

La esencia de la tarea de reconocimiento es establecer si los objetos estudiados tienen un conjunto finito fijo de características que les permita clasificarlos en una determinada clase.

Objetivos de la ciencia del reconocimiento de patrones:

Reemplazar un experto humano o un sistema experto complejo por un sistema más simple (automatización de actividades humanas o simplificación de sistemas complejos);

Construcción de sistemas de aprendizaje que puedan tomar decisiones sin especificar reglas claras, es decir, sistemas que puedan sintetizar reglas de decisión basándose en un número finito de ejemplos de decisiones correctas "demostradas" al sistema.

Tareas de reconocimiento se puede caracterizar de la siguiente manera.

1. Se trata de tareas de información que constan de dos etapas principales: reducir los datos originales a una forma conveniente para el reconocimiento y el reconocimiento mismo.

2. En estas tareas, podrá introducir el concepto de analogía y similitud de objetos y formular el concepto de proximidad de objetos como base para incluir un objeto en una determinada clase.

3. En estas tareas se puede operar con un conjunto de ejemplos cuya clasificación se conoce y que, en forma de descripciones formalizadas, se pueden presentar al algoritmo de reconocimiento para que se ajuste a la tarea durante el proceso de aprendizaje.

4. Para estos problemas es difícil construir teorías formales y aplicar métodos matemáticos clásicos.

5. En estos problemas, la información “mala” es posible.

Tipos de tareas de reconocimiento:

Asignación del objeto presentado a una de las clases (formación con un profesor);

Clasificación automática: dividir un conjunto de objetos (situaciones) según su descripción en un sistema de clases que no se superponen;

Selección de un conjunto de características de información durante la descomposición;

Llevar los datos originales a una forma conveniente para su reconocimiento;

Reconocimiento dinámico y clasificación dinámica;

Problemas de previsión.

Definiciones basicas

Imagen– se trata de una descripción estructurada de un objeto o fenómeno, representada por un vector de características, cada elemento del cual representa el valor numérico de una de las características que caracterizan a este objeto. En otras palabras: una imagen es cualquier objeto para el cual se puede medir un conjunto de determinadas características numéricas. Ejemplo de imagen: letra, imagen, cardiograma, etc.

Signo numérico(o simplemente una señal). es una fórmula u otra descripción de un método para hacer coincidir un objeto con una determinada característica numérica, que opera en el marco de una tarea específica de reconocimiento de patrones. Para cada objeto se pueden definir varias características diferentes, es decir, varias características numéricas.

Espacio de funciones Espacio N-dimensional definido para una tarea de reconocimiento determinada, donde N es un número fijo de características medidas para cualquier objeto. El vector del espacio de características correspondiente al objeto de la tarea de reconocimiento es un vector N-dimensional con componentes (x1, x2, ..., xN), que son los valores de las características de este objeto.

OBJETO->Ncaracterísticas->Vector de características de dimensión M

Clase- una idea no formalizada (por regla general) de la posibilidad de asignar un objeto arbitrario del conjunto de objetos de una tarea de reconocimiento a un determinado grupo de objetos. Para objetos de la misma clase, se supone la presencia de "similitud". Para una tarea de reconocimiento de patrones, se puede definir un número arbitrario de clases mayor que 1. El número de clases se indica con el número S.

En general, el problema del reconocimiento de patrones consta de dos partes: reconocimiento y entrenamiento.

El reconocimiento de patrones consiste en clasificar un determinado grupo de objetos en función de unos requisitos determinados. Los objetos que pertenecen a la misma clase de imágenes tienen propiedades comunes. Los requisitos que definen una clasificación pueden variar, ya que diferentes situaciones requieren diferentes tipos de clasificaciones.

Por ejemplo, al reconocer letras inglesas se forman 26 clases de imágenes. Sin embargo, para distinguir las letras inglesas de los caracteres chinos durante el reconocimiento, sólo se necesitan dos clases de imágenes.

El método más sencillo para el reconocimiento de patrones es la coincidencia de patrones. En este caso, en la memoria de la máquina se almacena un determinado conjunto de imágenes, una de cada clase de imágenes. La imagen de entrada (reconocida) (de una clase desconocida) se compara con el estándar de cada clase. La clasificación se basa en un criterio de coincidencia o de similitud preseleccionado. En otras palabras, si la imagen de entrada coincide mejor con el estándar de la i-ésima clase de patrón que cualquier otro estándar, entonces la imagen de entrada se clasifica como perteneciente a la i-ésima clase de patrón.

La desventaja de este enfoque, es decir, la comparación con un estándar, es que en algunos casos es difícil seleccionar un estándar adecuado de cada clase de imágenes y establecer el criterio de coincidencia necesario.

Un enfoque más avanzado es que la clasificación se basa en un determinado conjunto de mediciones seleccionadas realizadas en las imágenes de entrada. Se supone que estas medidas seleccionadas, llamadas “características”, son invariantes o insensibles a las variaciones y distorsiones comúnmente encontradas y que tienen poca redundancia.

Un caso especial del segundo enfoque de "medición de características", en el que los estándares se almacenan en forma de características medidas y se utiliza un criterio de clasificación especial (comparación) en el clasificador.

Las características las definen los desarrolladores y deben ser invariables ante las variaciones de orientación, tamaño y forma de los objetos.

Conferencia número 17.MÉTODOS DE RECONOCIMIENTO DE PATRONES

Se distinguen los siguientes grupos de métodos de reconocimiento:

Métodos de función de proximidad

Métodos de función discriminante

Métodos de reconocimiento estadístico.

Métodos lingüísticos

Métodos heurísticos.

Los primeros tres grupos de métodos se centran en el análisis de características expresadas como números o vectores con componentes numéricos.

Un grupo de métodos lingüísticos proporciona reconocimiento de patrones basado en el análisis de su estructura, descrita por las características estructurales correspondientes y las relaciones entre ellas.

El grupo de métodos heurísticos combina técnicas características y procedimientos lógicos utilizados por los humanos en el reconocimiento de patrones.

Métodos de función de proximidad

Los métodos de este grupo se basan en el uso de funciones que estiman la medida de proximidad entre la imagen reconocida y el vector. X* = (X* 1 ,….,x*n), e imágenes de referencia de varias clases, representadas por vectores xyo = (xyo 1 ,…, x y n), yo = 1,…,norte, Dónde i - número de clase de imagen.

El procedimiento de reconocimiento según este método consiste en calcular la distancia entre el punto de la imagen reconocida y cada uno de los puntos que representan la imagen de referencia, es decir al calcular todos los valores yo , yo = 1,…,norte. La imagen pertenece a una clase para la cual el valor yo tiene la menor importancia entre todos yo = 1,…,norte .

Una función que asigna cada par de vectores. xyo, X* número real como medida de su proximidad, es decir determinar la distancia entre ellos puede ser bastante arbitrario. En matemáticas, esta función se llama métrica del espacio. Debe satisfacer los siguientes axiomas:

r(x,y)=r(y, x);

r(x,y) > 0 si X no es igual y Y r(x,y)=0 si x=y;

r(x,y) <=r(x,z)+r(z,y)

Los axiomas enumerados se satisfacen, en particular, mediante las siguientes funciones

un yo= 1/2 , j=1,2,…norte.

b yo= suma j=1,2,…norte.

c yo=abdominales máximos ( xyo‑ xj*), j=1,2,…norte.

La primera de ellas se denomina norma euclidiana de un espacio vectorial. En consecuencia, los espacios en los que se utiliza la función especificada como métrica se denominan espacio euclidiano.

A menudo, la diferencia cuadrática media en las coordenadas de la imagen reconocida se elige en función de la proximidad. X* y estándar xyo, es decir. función

yo = (1/norte) suma( x yo j‑ xj*) 2 , j=1,2,…norte.

Magnitud yo interpretado geométricamente como el cuadrado de la distancia entre puntos en el espacio característico, relacionado con la dimensión del espacio.

A menudo resulta que diferentes características no son igualmente importantes en el reconocimiento. Para tener en cuenta esta circunstancia al calcular las funciones de proximidad, las diferencias de coordenadas correspondientes a características más importantes se multiplican por coeficientes grandes y a las menos importantes, por otros más pequeños.

En este caso yo = (1/norte) suma wj (x yo j‑ xj*) 2 , j=1,2,…norte,

Dónde wj– coeficientes de ponderación.

La introducción de coeficientes de ponderación equivale a escalar los ejes del espacio de características y, en consecuencia, estirar o comprimir el espacio en ciertas direcciones.

Las deformaciones indicadas del espacio característico persiguen el objetivo de colocar los puntos de las imágenes de referencia de tal manera que corresponda al reconocimiento más confiable en condiciones de una dispersión significativa de imágenes de cada clase en las proximidades del punto de la imagen de referencia. .

Los grupos de puntos de imagen cercanos entre sí (grupos de imágenes) en el espacio de características se denominan grupos, y la tarea de identificar dichos grupos se denomina problema de agrupación.

La tarea de identificar grupos se clasifica como una tarea de reconocimiento de patrones no supervisada, es decir. a problemas de reconocimiento en ausencia de un ejemplo de reconocimiento correcto.

Métodos de función discriminante

La idea de los métodos de este grupo es construir funciones que definan límites en el espacio de imágenes que dividan el espacio en áreas correspondientes a clases de imágenes. Las funciones de este tipo más simples y utilizadas con mayor frecuencia son funciones que dependen linealmente de los valores de las características. En el espacio característico corresponden a superficies divisorias en forma de hiperplanos. En el caso de un espacio de características bidimensional, una línea recta actúa como función de separación.

La forma general de la función de decisión lineal viene dada por la fórmula

d(X)=w 1 X 1 + w 2 X 2 +…+wnxn +wn +1 = Wx+wn

Dónde X- imagen vectorial, w=(w 1 ,w 2 ,…wn) – vector de coeficientes de ponderación.

En caso de dividirse en dos clases X 1 y X 2 función discriminante d(x) permite el reconocimiento de acuerdo con la regla:

X pertenece X 1 si d(X)>0;

X pertenece X 2 si d(X)<0.

Si d(X)=0, entonces hay un caso de incertidumbre.

En el caso de dividirse en varias clases, se introducen varias funciones. En este caso, a cada clase de imágenes se le asigna una determinada combinación de signos de función discriminatoria.

Por ejemplo, si se introducen tres funciones discriminantes, entonces es posible la siguiente opción para identificar clases de imágenes:

X pertenece X 1 si d 1 (X)>0,d 2 (X)<0,d 3 (X)<0;

X pertenece X 2 si d(X)<0,d 2 (X)>0,d 3 (X)<0;

X pertenece X 3 si d(X)<0,d 2 (X)<0,d 3 (X)>0.

Se supone que para otras combinaciones de valores d 1 (X),d 2 (X),d 3 (X) hay un caso de incertidumbre.

Una variación del método de la función discriminante es el método de la función de decisión. En él, si está disponible. metro Se supone que existen clases. metro funciones yo(X), llamado decisivo, de modo que si X pertenece X yo, Eso yo(X) > DJ(X) para todos j desigual i,aquellos. función decisiva yo(X) tiene el valor máximo entre todas las funciones DJ(X), j=1,...,norte..

Una ilustración de este método puede ser un clasificador basado en la estimación de la distancia euclidiana mínima en el espacio de características entre el punto de la imagen y el estándar. Mostrémoslo.

Distancia euclidiana entre el vector característico de la imagen reconocida. X y el vector de la imagen de referencia está determinado por la fórmula || xyo ‑ X|| = 1/2 , j=1,2,…norte.

Vector X será asignado a la clase i, para el cual el valor || xyo ‑ X*|| mínimo.

En lugar de la distancia, puedes comparar el cuadrado de la distancia, es decir

||xyo ‑ X|| 2 = (xyo ‑ X)(xyo ‑ X)t = X X- 2X xyo +xyo xyo

Desde el valor X X lo mismo para todos i, función mínima || xyo ‑ X|| 2 coincidirá con el máximo de la función de decisión

yo(X) = 2X xyo -xyo xyo.

eso es X pertenece X yo, Si yo(X) > DJ(X) para todos j desigual i.

Eso. La máquina clasificadora de distancia mínima se basa en funciones de decisión lineales. La estructura general de dicha máquina utiliza funciones decisivas de la forma

yo (X)=yo 1 X 1 + yo 2 X 2 +…+w en x n +ganar +1

Se puede representar visualmente mediante el diagrama de bloques correspondiente.

Para una máquina que realiza la clasificación en función de la distancia mínima, se cumplen las siguientes igualdades: wij = -2x yo j , ganar +1 = xyo xyo.

El reconocimiento equivalente mediante el método de la función discriminante se puede llevar a cabo definiendo las funciones discriminantes como diferencias. dij (X)=yo (X)‑DJ (X).

La ventaja del método de la función discriminante es la estructura simple de la máquina de reconocimiento, así como la posibilidad de su implementación principalmente a través de bloques de decisión predominantemente lineales.

Otra ventaja importante del método de la función discriminante es la capacidad de entrenar automáticamente una máquina para el reconocimiento correcto en función de una muestra de imágenes determinada (de entrenamiento).

Al mismo tiempo, el algoritmo de aprendizaje automático resulta muy sencillo en comparación con otros métodos de reconocimiento.

Por estas razones, el método de la función discriminante ha ganado gran popularidad y se utiliza con mucha frecuencia en la práctica.

Procedimientos de autoformación para el reconocimiento de patrones.

Consideremos métodos para construir una función discriminante para una muestra dada (de entrenamiento) en relación con el problema de dividir imágenes en dos clases. Si se dan dos conjuntos de imágenes, pertenecientes respectivamente a las clases A y B, entonces la solución al problema de construir una función discriminante lineal se busca en forma de un vector de coeficientes de ponderación. W.=(w 1 ,w 2 ,...,wn,wn+1), que tiene la propiedad de que para cualquier imagen se cumplen las siguientes condiciones:

X pertenece a la clase A si >0, j=1,2,…norte.

X pertenece a la clase B si<0, j=1,2,…norte.

Si el conjunto de entrenamiento consta de norte imágenes de ambas clases, la tarea se reduce a encontrar un vector w que asegure la validez del sistema de desigualdades si la muestra de entrenamiento consta de. norte imágenes de ambas clases, la tarea se reduce a encontrar el vector w, asegurando la validez del sistema de desigualdades

X 1 1 yo+X 21 w 2 +...+xn 1 wn+wn +1 >0;

X 1 2 yo+X 22 w 2 +...+xn 2 wn+wn +1 <0;

X 1 iyo+X 2i w 2 +...+x ni w n+wn +1 >0;

................................................

X 1 nortew i + x 2norte w 2 +...+x nN w n +w n + 1>0;

Aquí xyo=(xyo 1 ,x yo 2 ,...,x yo n ,x yo n+ 1 ) - vector de valores de características de imagen de la muestra de entrenamiento, el signo > corresponde a vectores de imagen X, perteneciente a la clase A, y el signo< - векторам X, perteneciente a la clase B.

vector requerido w existe si las clases A y B son separables y no existe en caso contrario. Valores de componentes vectoriales w se puede encontrar de antemano, en la etapa anterior a la implementación del hardware del SRO, o directamente por el propio SRO durante su funcionamiento. El último de estos enfoques proporciona mayor flexibilidad y autonomía a la SRO. Considérelo usando el ejemplo de un dispositivo llamado percentrón. inventado en 1957 por el científico estadounidense Rosenblatt. En la siguiente figura se presenta una representación esquemática del percentrón, que garantiza que una imagen se asigne a una de dos clases.

Retina S Retina A Retina R

oh oh X 1

oh oh X 2

oh oh X 3

o (suma)-------> R(reacción)

oh oh xyo

oh oh xn

oh oh xn +1

El dispositivo consta de elementos sensoriales de la retina. S, que están conectados aleatoriamente a elementos asociativos de la retina. A. Cada elemento de la segunda retina produce una señal de salida solo si un número suficiente de elementos sensoriales conectados a su entrada están en estado excitado. Respuesta de todo el sistema R es proporcional a la suma de las reacciones de los elementos de la retina asociativa tomados con ciertos pesos.

Diseñado por xyo reacción iº elemento asociativo y a través de yo- coeficiente de peso de reacción iº elemento asociativo, la reacción del sistema se puede escribir como R=suma( wjxj), j=1,..,norte. Si R>0, entonces la imagen presentada al sistema pertenece a la clase A, y si R<0, то образ относится к классу B. Описание этой процедуры классификации соответствует рассмотренным нами раньше принципам классификации, и, очевидно, перцентронная модель распознавания образов представляет собой, за исключением сенсорной сетчатки, реализацию линейной дискриминантной функции. Принятый в перцентроне принцип формирования значений X 1 , X 2 ,...,xn Corresponde a algún algoritmo para generar características basadas en señales de sensores primarios.

En general puede haber varios elementos. R, formando la reacción del perceptrón. En este caso hablan de la presencia de una retina en el perceptrón. R elementos reactivos.

El esquema de percentrón se puede ampliar al caso en que el número de clases sea superior a dos, aumentando el número de elementos de la retina. R hasta el número de clases distinguibles y la introducción de un bloque para determinar la reacción máxima de acuerdo con el diagrama presentado en la figura anterior. En este caso, la imagen se asigna a la clase con número i, Si ri>Rj, para todos j.

El proceso de entrenamiento percentrón consiste en seleccionar los valores de los coeficientes de ponderación wj para que la señal de salida corresponda a la clase a la que pertenece la imagen reconocida.

Consideremos el algoritmo de acción percentrón usando el ejemplo de reconocimiento de objetos de dos clases: A y B. Los objetos de clase A deben corresponder al valor R= +1, y clase B - el valor R= -1.

El algoritmo de aprendizaje es el siguiente.

Si la siguiente imagen X pertenece a la clase A, pero R<0 (имеет место ошибка распознавания), тогда коэффициенты wj con índices a los que corresponden los valores xj>0, aumentar en cierta cantidad dw, y los coeficientes restantes wj reducido por dw. En este caso, el valor de la reacción. R recibe un incremento hacia sus valores positivos, correspondientes a la clasificación correcta.

Si X pertenece a la clase B, pero R>0 (hay un error de reconocimiento), entonces los coeficientes wj con índices que corresponden a xj<0, увеличивают на dw, y los coeficientes restantes wj reducido en la misma cantidad. En este caso, el valor de la reacción. R recibe un incremento hacia los valores negativos correspondientes a la clasificación correcta.

El algoritmo realiza así un cambio en el vector de pesos. w si y sólo si la imagen presentada en k-ésimo paso de entrenamiento, se clasificó incorrectamente al realizar este paso, y deja el vector de pesos w No hay cambios si se clasifica correctamente. La prueba de la convergencia de este algoritmo se presenta en [Tu, González]. En última instancia, dicha capacitación (con una selección adecuada) dw y separabilidad lineal de clases de imágenes) conduce al vector w, asegurando una correcta clasificación.

Métodos de reconocimiento estadístico.

Los métodos estadísticos se basan en minimizar la probabilidad de error de clasificación. Probabilidad P de clasificación incorrecta de una imagen enviada para reconocimiento, descrita por un vector de características X, está determinado por la fórmula

P = suma[ pag(i)problema( D(X)+i | X clase i)]

Dónde metro- número de clases,

pag(i) = problema ( X pertenece a la clase i) - probabilidad a priori de pertenecer a una imagen arbitraria X A iª clase (frecuencia de aparición de imágenes i-ésima clase),

D(X) - una función que toma una decisión de clasificación (vector de características X coincide con el número de clase i del conjunto (1,2,..., metro}),

problema( D(X) no es igual i| X pertenece a la clase i) - probabilidad del evento " D(X) no es igual i"cuando se cumple la condición de membresía X clase i, es decir. probabilidad de tomar una decisión errónea mediante la función D(X) para un valor dado X, propiedad i-ésima clase.

Se puede demostrar que la probabilidad de clasificación errónea alcanza un mínimo si D(X)=i si y solo si pag(X|i)· pag(i)>pag(x|j)· pag(j), para todos i+j, Dónde pag(x|i) - densidad de distribución de imágenes i-clase en el espacio de características.

Según la regla anterior, el punto X pertenece a la clase a la que corresponde el valor máximo pag(i) pag(x|i), es decir. producto de la probabilidad (frecuencia) previa de aparición de imágenes i-densidad de distribución de clase e imagen i-clase en el espacio de características. La regla de clasificación presentada se llama bayesiana, porque se desprende de la fórmula de Bayes conocida en la teoría de la probabilidad.

Ejemplo. Sea necesario reconocer señales discretas a la salida de un canal de información sujeto a ruido.

Cada señal de entrada representa un 0 o un 1. Como resultado de la transmisión de la señal, el valor aparece en la salida del canal. X, que se superpone con ruido gaussiano con media cero y varianza b.

Para sintetizar un clasificador que realice reconocimiento de señales, utilizaremos la regla de clasificación bayesiana.

Combinaremos señales que representan unos en la clase No. 1 y señales que representan ceros en la clase No. 2. Hágase saber de antemano que en promedio de cada 1000 señales a las señales representan unidades y b señales - cero. Entonces, los valores de las probabilidades a priori de aparición de señales de primera y segunda clase (unos y ceros), respectivamente, se pueden tomar iguales.

p(1)=a/1000, p(2)=b/1000.

Porque el ruido es gaussiano, es decir obedece a la ley de distribución normal (gaussiana), entonces la densidad de distribución de imágenes de primera clase depende del valor X, o lo que es lo mismo, la probabilidad de obtener el valor de salida X cuando se aplica una señal 1 en la entrada, está determinada por la expresión

pag(X¦1) =(2pib) -1/2 exp(-( X-1) 2 /(2b 2)),

y la densidad de distribución dependiendo del valor X imágenes de segunda clase, es decir probabilidad de obtener el valor de salida X cuando se aplica una señal 0 en la entrada, está determinada por la expresión

pag(X¦2)= (2pib) -1/2 exp(- X 2/(2b 2)),

La aplicación de la regla de decisión bayesiana lleva a la conclusión de que se ha transmitido una señal de clase 2, es decir se pasa nulo si

pag(2) pag(X¦2) > pag(1) pag(X¦1)

o, más concretamente, si

b Exp(- X 2 /(2b 2)) > a Exp(-( X-1) 2 /(2b 2)),

Dividiendo el lado izquierdo de la desigualdad por el derecho, obtenemos

(b/a)exp((1-2 X)/(2b 2)) >1,

donde después de tomar logaritmos encontramos

1-2X> 2b 2 ln(a/b)

X< 0.5 - б 2 ln(a/b)

De la desigualdad resultante se deduce que cuando a=b, es decir. con probabilidades a priori iguales de ocurrencia de las señales 0 y 1, a la imagen se le asigna el valor 0 cuando X<0.5, а значение 1, когда X>0.5.

Si se sabe de antemano que una de las señales aparece con más frecuencia y la otra con menos frecuencia, es decir en caso de valores desiguales a Y b, el umbral de respuesta del clasificador se desplaza en una dirección u otra.

Así que cuando a/b=2,71 (que corresponde a una transmisión de unidades 2,71 veces más frecuente) y b 2 =0,1, a la imagen se le asigna el valor 0 si X<0.4, и значение 1, если X>0,4. Si no hay información sobre las probabilidades de distribución previa, entonces se pueden utilizar métodos de reconocimiento estadístico, que se basan en reglas de clasificación distintas a las bayesianas.

Sin embargo, en la práctica, los métodos basados ​​en las reglas de Bayes son los más comunes debido a su mayor eficiencia, y también a que en la mayoría de los problemas de reconocimiento de patrones es posible establecer a priori probabilidades de aparición de imágenes de cada clase.

Métodos lingüísticos de reconocimiento de patrones.

Los métodos lingüísticos de reconocimiento de patrones se basan en el análisis de la descripción de una imagen idealizada, presentada en forma de gráfico o cadena de caracteres, que es una frase u oración de un determinado idioma.

Considere las imágenes idealizadas de letras obtenidas como resultado de la primera etapa de reconocimiento lingüístico descrita anteriormente. Estas imágenes idealizadas se pueden especificar mediante descripciones de gráficos, presentados, por ejemplo, en forma de matrices de conexión, como se hizo en el ejemplo discutido anteriormente. La misma descripción puede representarse mediante una frase de un lenguaje formal (expresión).

Ejemplo. Se dan tres imágenes de la letra A, obtenidas como resultado del procesamiento preliminar de imágenes. Designemos estas imágenes con los identificadores A1, A2 y A3.

Para describir lingüísticamente las imágenes presentadas, utilizaremos PDL (Lenguaje de descripción de imágenes). El vocabulario PDL incluye los siguientes símbolos:

1. Nombres de las imágenes más simples (primitivas). Tal como se aplica al caso que nos ocupa, las primitivas y sus nombres correspondientes son los siguientes.

Imágenes en forma de línea dirigida:

arriba e izquierda (le F t), norte (norte), arriba y a la derecha (derecha), este).

Nombres: L, N, R, E.

2. Símbolos de operaciones binarias. (+,*,-) Su significado corresponde a la conexión secuencial de las primitivas (+), la conexión de los comienzos y finales de las primitivas (*), la conexión de solo las terminaciones de las primitivas (-).

3. Soportes derecho e izquierdo. ((,)) Los paréntesis le permiten determinar la secuencia de operaciones en una expresión.

Las imágenes consideradas A1, A2 y A3 se describen en lenguaje PDL, respectivamente, mediante las siguientes expresiones.

T(1)=R+((R-(L+N))*E-L

T(2)=(R+N)+((N+R)-L)*E-L

T(3)=(N+R)+(R-L)*E-(L+N)

Una vez construida la descripción lingüística de la imagen, es necesario, mediante algún procedimiento de reconocimiento, analizar si esta imagen pertenece o no a la clase que nos interesa (clase de letras A), es decir Si esta imagen tiene o no alguna estructura. Para ello, en primer lugar, es necesario describir la clase de imágenes que tienen la estructura que nos interesa.

Evidentemente, la letra A siempre contiene los siguientes elementos estructurales: una pierna izquierda, una pierna derecha y una cabeza. Llamemos a estos elementos STL, STR, TR, respectivamente.

Luego, en el lenguaje PDL, la clase de símbolo A - SIMB A se describe mediante la expresión

SIMB A = STL + TR - STR

La "pata" izquierda de STL es siempre una cadena de elementos R y N, que se puede escribir así

STL ‑> R ¦ N ¦ (STL + R)¦ (STL + N)

(STL es el carácter R o N, o una cadena obtenida sumando los caracteres R o N a la cadena STL de origen)

El “tramo” derecho de STR es siempre una cadena de elementos L y N, que se puede escribir así, es decir

STR ‑> L¦N¦ (STR + L)¦(STR + N)

La cabecera de la letra TR es un contorno cerrado formado por el elemento E y cadenas como STL y STR.

En PDL, la estructura TR se describe mediante la expresión

TR ‑> (STL - STR) * E

Finalmente obtenemos la siguiente descripción de la clase de letras A:

SIMB A ‑> (STL + TR - STR),

STL ‑> R¦N¦ (STL + R)¦(STL + N)

STR ‑> L¦N¦ (STR + L)¦(STR + N)

TR ‑> (STL - STR) * E

El procedimiento de reconocimiento en este caso se puede implementar de la siguiente manera.

1. Se compara la expresión correspondiente a la imagen con la estructura de referencia STL + TR - STR.

2. Cada elemento de la estructura STL, TR, STR, si es posible, es decir. si la descripción de la imagen es comparable al estándar, alguna subexpresión de la expresión T(A) coincide. Por ejemplo,

para A1: STL=R, STR=L, TR=(R-(L+N))*E

para A2: STL = R + N, STR = L, TR = ((N + R) - L) * E

para A3: STL = N + R, STR = L + N, TR = (R - L) * E 3.

Las expresiones STL, STR, TR se comparan con sus correspondientes estructuras de referencia.

4. Si la estructura de cada expresión STL, STR, TR corresponde al estándar, se llega a la conclusión de que la imagen pertenece a la clase de letras A. Si en cualquiera de las etapas 2, 3, 4 hay una discrepancia entre la estructura de las analizadas Se detecta la expresión y el estándar, se llega a la conclusión de que la imagen no pertenece a la clase SIMB A. La comparación de estructuras de expresión se puede realizar utilizando lenguajes algorítmicos LISP, PLANER, PROLOG y otros lenguajes de inteligencia artificial similares.

En el ejemplo considerado, todas las cadenas STL se componen de los símbolos N y R, y las cadenas STR se componen de los símbolos L y N, lo que corresponde a la estructura dada de estas cadenas. La estructura de TR en las imágenes consideradas también corresponde a la de referencia, ya que Consiste en la “diferencia” de cadenas como STL, STR, “multiplicadas” por el símbolo E.

Así, llegamos a la conclusión de que las imágenes consideradas pertenecen a la clase SIMB A.

Síntesis de un controlador difuso para un accionamiento eléctrico de CC.en el entorno MatLab

Síntesis de un controlador difuso con una entrada y una salida.

El desafío es lograr que el variador siga con precisión las diferentes señales de entrada. El desarrollo de la acción de control se realiza mediante un controlador difuso, en el que estructuralmente se pueden distinguir los siguientes bloques funcionales: un fuzzificador, un bloque de reglas y un defuzzificador.

Fig.4 Diagrama funcional generalizado de un sistema con dos variables lingüísticas.

Fig.5 Diagrama esquemático de un controlador difuso con dos variables lingüísticas.

El algoritmo de control difuso en el caso general es una transformación de las variables de entrada de un controlador difuso en sus variables de salida utilizando los siguientes procedimientos interrelacionados:

1. transformación de variables físicas de entrada recibidas de los sensores de medición del objeto de control en variables lingüísticas de entrada de un controlador difuso;

2. procesamiento de declaraciones lógicas, llamadas reglas lingüísticas, relativas a las variables lingüísticas de entrada y salida del controlador;

3. transformación de las variables lingüísticas de salida del controlador difuso en variables de control físico.

Consideremos primero el caso más simple, cuando sólo se introducen dos variables lingüísticas para controlar el servoaccionamiento:

“ángulo” es una variable de entrada;

“acción de control” es la variable de salida.

Sintetizaremos el controlador en el entorno MatLab utilizando la caja de herramientas Fuzzy Logic. Le permite crear sistemas de inferencia difusa y clasificación difusa dentro del entorno MatLab, con la capacidad de integrarlos en Simulink. El concepto básico de Fuzzy Logic Toolbox es la estructura FIS: Fuzzy Inference System. La estructura FIS contiene todos los datos necesarios para implementar el mapeo funcional “entradas-salidas” basado en inferencia lógica difusa según el diagrama que se muestra en la Fig. 6.

Figura 6. Inferencia difusa.

X - vector nítido de entrada; - vector de conjuntos difusos correspondientes al vector de entrada X;
- el resultado de la inferencia lógica en forma de un vector de conjuntos difusos; Y - el vector claro de salida.

El módulo difuso le permite construir sistemas difusos de dos tipos: Mamdani y Sugeno. En sistemas como Mamdani, la base de conocimientos consta de reglas de la forma “Si x 1 = bajo y x 2 = medio, entonces y = alto”. En los sistemas de tipo Sugeno, la base de conocimientos consta de reglas de la forma “Si x 1 = bajo y x 2 = medio, entonces y = a 0 +a 1 x 1 +a 2 x 2 ". Así, la principal diferencia entre los sistemas Mamdani y Sugeno radica en las diferentes formas de especificar los valores de la variable de salida en las reglas que forman la base de conocimiento. En sistemas del tipo Mamdani, los valores de la variable de salida se especifican mediante términos difusos, en sistemas del tipo Sugeno, como una combinación lineal de variables de entrada. En nuestro caso, usaremos el sistema Sugeno, porque se presta mejor a la optimización.

Para controlar el servodrive se introducen dos variables lingüísticas: “error” (por posición) y “acción de control”. El primero de ellos es la entrada, el segundo es la salida. Definamos un conjunto de términos para las variables especificadas.

Componentes básicos de la inferencia lógica difusa. Difusor.

Para cada variable lingüística, definimos un conjunto de términos básicos de la forma, que incluye conjuntos difusos que pueden designarse: negativo alto, negativo bajo, cero, positivo bajo, positivo alto.

En primer lugar, definamos subjetivamente qué se entiende por los términos “gran error”, “pequeño error”, etc., definiendo funciones de pertenencia para los correspondientes conjuntos difusos. Aquí, por ahora, solo puede guiarse por la precisión requerida, los parámetros conocidos para la clase de señales de entrada y el sentido común. Nadie ha podido proponer todavía ningún algoritmo estricto para elegir los parámetros de las funciones de membresía. En nuestro caso, la variable lingüística "error" se verá así.

Fig.7. Variable lingüística "error".

Es más conveniente presentar la variable lingüística “control” en forma de tabla:

tabla 1

bloque de reglas.

Consideremos la secuencia de definición de varias reglas que describen algunas situaciones:

Supongamos, por ejemplo, que el ángulo de salida es igual a la señal de entrada (es decir, el error es cero). Evidentemente, esta es la situación deseada, y por tanto no tenemos que hacer nada (la acción de control es nula).

Consideremos ahora otro caso: el error de posición es mucho mayor que cero. Naturalmente, debemos compensarlo generando una gran señal de control positiva.

Eso. Se han elaborado dos reglas, que pueden definirse formalmente de la siguiente manera:

Si error = nulo, Eso acción de control = cero.

Si error = positivo grande, Eso influencia de control = gran positivo.

Fig.8. Formación de control con un pequeño error positivo en posición.

Fig.9. Formación de control con error de posición cero.

La siguiente tabla muestra todas las reglas correspondientes a todas las situaciones para este caso simple.

Tabla 2

En total, para un controlador difuso con n entradas y 1 salida, se pueden definir reglas de control, donde es el número de conjuntos difusos para la i-ésima entrada, pero para el funcionamiento normal del controlador no es necesario utilizar todos los posibles. reglas, pero puedes arreglártelas con menos. En nuestro caso, se utilizan las 5 reglas posibles para generar una señal de control difusa.

Desfuzzificador.

Así, el impacto resultante U estará determinado en función del cumplimiento de alguna regla. Si surge una situación en la que se ejecutan varias reglas a la vez, entonces el impacto resultante U se encuentra de acuerdo con la siguiente relación:

, donde n es el número de reglas activadas (desfusificación mediante el método del centro de región), u n– valor físico de la señal de control correspondiente a cada uno de los conjuntos difusos UBO, UMo, Ud.z, UMp, UBPAG. metroUn(u)– grado de pertenencia de la señal de control u al conjunto difuso correspondiente Un=( UBO, UMo, Ud.z, UMp, UBPAG). También existen otros métodos de defusificación en los que la variable lingüística de salida es proporcional a la regla "más fuerte" o "más débil".

Modelemos el proceso de control de un accionamiento eléctrico utilizando el controlador difuso descrito anteriormente.

Figura 10. Diagrama de bloques del sistema en el entorno.matlab.

Figura 11. Diagrama de bloques de un controlador difuso en un entorno.matlab.

Figura 12. Proceso transitorio bajo una acción de un solo paso.

Arroz. 13. Proceso transitorio bajo acción de entrada armónica para un modelo con un controlador difuso que contiene una variable lingüística de entrada.

Un análisis de las características del variador con un algoritmo de control sintetizado muestra que están lejos de ser óptimas y peores que cuando se sintetiza el control por otros métodos (el tiempo de control es demasiado largo para una acción de un solo paso y el error es armónico). Esto se explica por el hecho de que los parámetros de las funciones de pertenencia se eligieron de forma bastante arbitraria y sólo se utilizó el valor del error de posición como entrada del controlador. Naturalmente, no se puede hablar de optimidad del regulador resultante. Por lo tanto, la tarea de optimizar un controlador difuso se vuelve relevante para lograr los mayores indicadores de calidad de control posibles. Aquellos. La tarea es optimizar la función objetivo f(a 1 ,a 2 …a n), donde a 1 ,a 2 …a n son los coeficientes que determinan el tipo y las características del controlador difuso. Para optimizar el controlador difuso utilizaremos el bloque ANFIS del entorno Matlab. Además, una de las formas de mejorar las características del controlador puede ser aumentar el número de entradas. Esto hará que el regulador sea más flexible y mejorará su desempeño. Agreguemos una variable lingüística de entrada más: la tasa de cambio de la señal de entrada (su derivada). El número de reglas aumentará en consecuencia. Entonces el diagrama del circuito del regulador tomará la forma:

Fig. 14 Diagrama esquemático de un controlador difuso con tres variables lingüísticas.

Sea el valor de la velocidad de la señal de entrada. Definimos el conjunto de términos básico Tn como:

Tn=("negativo (BO)", "cero (Z)", "positivo (BP)").

La ubicación de las funciones de membresía para todas las variables lingüísticas se muestra en la figura.

Figura 15. Funciones de pertenencia de la variable lingüística “error”.

Figura 16. Funciones de pertenencia de la variable lingüística “velocidad de la señal de entrada”.

Debido a la adición de una variable lingüística más, el número de reglas aumentará a 3x5=15. El principio de su elaboración es completamente similar al discutido anteriormente. Todos ellos se muestran en la siguiente tabla:

Tabla 3

Por ejemplo, si Si error = cero y derivada de la señal de entrada = positivo grande, Eso influencia de control = pequeña negativa.

Figura 17. Formación del control bajo tres variables lingüísticas.

Debido al aumento en el número de entradas y, en consecuencia, de las reglas mismas, la estructura del controlador difuso se volverá más compleja.

Figura 18. Diagrama de bloques de un controlador difuso de dos entradas.

Añadir una imagen

Fig.20. Proceso transitorio bajo acción de entrada armónica para un modelo con un controlador difuso que contiene dos variables lingüísticas de entrada.

Arroz. 21. Señal de error bajo acción de entrada armónica para un modelo con un controlador difuso que contiene dos variables lingüísticas de entrada.

Simulemos el funcionamiento de un controlador difuso de dos entradas en el entorno Matlab. El diagrama de bloques del modelo será exactamente el mismo que en la Fig. 19. Del gráfico del proceso transitorio para un efecto de entrada armónico, se puede ver que la precisión del sistema ha aumentado significativamente, pero al mismo tiempo ha aumentado su oscilación, especialmente en lugares donde tiende la derivada de la coordenada de salida. a cero. Obviamente, las razones de esto, como se mencionó anteriormente, son la elección subóptima de los parámetros de la función de membresía para las variables lingüísticas de entrada y salida. Por tanto, optimizamos el controlador difuso utilizando el bloque ANFISedit en el entorno Matlab.

Optimización de un controlador difuso.

Consideremos el uso de algoritmos genéticos para optimizar un controlador difuso. Los algoritmos genéticos son métodos de búsqueda adaptativos que recientemente se han utilizado con frecuencia para resolver problemas de optimización funcional. Se basan en la similitud con los procesos genéticos de los organismos biológicos: las poblaciones biológicas se desarrollan a lo largo de varias generaciones, obedeciendo las leyes de la selección natural y según el principio de “supervivencia del más fuerte”, descubierto por Charles Darwin. Al imitar este proceso, los algoritmos genéticos pueden "evolucionar" soluciones a problemas del mundo real si se codifican adecuadamente.

Los algoritmos genéticos funcionan con un conjunto de “individuos” (una población), cada uno de los cuales representa una posible solución a un problema determinado. Cada individuo es evaluado por la medida de su “adaptabilidad” según cuán “buena” sea la solución al problema que le corresponde. Los individuos más aptos son capaces de “reproducir” descendencia mediante el “cruzamiento” con otros individuos de la población. Esto conduce al surgimiento de nuevos individuos que combinan algunas de las características que heredan de sus padres. Los individuos menos aptos tienen menos probabilidades de reproducirse, por lo que cualquier rasgo que posean desaparecerá gradualmente de la población.

Así se reproduce toda la nueva población de soluciones factibles, eligiendo los mejores representantes de la generación anterior, cruzándolos y obteniendo muchos individuos nuevos. Esta nueva generación contiene una mayor proporción de las características que poseían los buenos miembros de la generación anterior. Así, de generación en generación, las buenas características se difunden entre la población. En última instancia, la población convergerá hacia la solución óptima del problema.

Hay muchas formas de implementar la idea de evolución biológica en el marco de los algoritmos genéticos. Tradicional, se puede representar como el siguiente diagrama de bloques que se muestra en la Figura 22, donde:

1. Inicialización de la población inicial – generación de un número determinado de soluciones al problema, con lo cual comienza el proceso de optimización;

2. Aplicación de operadores de cruce y mutación;

3. Condiciones de parada: normalmente el proceso de optimización continúa hasta que se encuentra una solución al problema con una precisión determinada, o hasta que se determina que el proceso ha convergido (es decir, la solución al problema no ha mejorado en las últimas N generaciones).

En el entorno Matlab, los algoritmos genéticos están representados por una caja de herramientas separada, así como por el paquete ANFIS. ANFIS es una abreviatura de Sistema de inferencia difusa basado en red adaptativa: red de inferencia difusa adaptativa. ANFIS es una de las primeras variantes de las redes neurodifusas híbridas, un tipo especial de red neuronal de retroalimentación. La arquitectura de una red neurodifusa es isomorfa a una base de conocimiento difusa. Las redes neurodifusas utilizan implementaciones diferenciables de normas triangulares (multiplicación y OR probabilística), así como funciones de membresía fluidas. Esto le permite utilizar algoritmos genéticos y rápidos para entrenar redes neuronales basados ​​​​en el método de retropropagación para configurar redes neurodifusas. A continuación se describe la arquitectura y reglas de funcionamiento de cada capa de la red ANFIS.

ANFIS implementa el sistema de inferencia difusa de Sugeno como una red neuronal de avance de cinco capas. El propósito de las capas es el siguiente: la primera capa son los términos de las variables de entrada; la segunda capa: antecedentes (premisas) de reglas difusas; la tercera capa es la normalización de los grados de cumplimiento de las normas; la cuarta capa es la conclusión de las reglas; la quinta capa es la agregación del resultado obtenido según varias reglas.

Las entradas de la red no se asignan a una capa separada. La Figura 23 muestra una red ANFIS con una variable de entrada (“error”) y cinco reglas difusas. Para la evaluación lingüística de la variable de entrada "error" se utilizan 5 términos.

Fig.23. EstructuraANFIS-redes

Introduzcamos la siguiente notación necesaria para una mayor presentación:

Sean las entradas de la red;

y - salida de red;

Regla difusa con número de secuencia r;

m - número de reglas;

Un término difuso con una función de pertenencia utilizada para la evaluación lingüística de una variable en la r-ésima regla (,);

Números reales en la conclusión de la regla r-ésima (,).

La red ANFIS funciona de la siguiente manera.

Capa 1. Cada nodo en la primera capa representa un término con una función de membresía en forma de campana. Las entradas de la red están conectadas únicamente a sus términos. El número de nodos en la primera capa es igual a la suma de las cardinalidades de los conjuntos de términos de las variables de entrada. La salida del nodo es el grado en que el valor de la variable de entrada pertenece al término difuso correspondiente:

,

donde a, byc son parámetros configurables de la función de membresía.

Capa 2. El número de nodos en la segunda capa es m. Cada nodo de esta capa corresponde a una regla difusa. El nodo de la segunda capa está conectado a aquellos nodos de la primera capa que forman los antecedentes de la regla correspondiente. Por lo tanto, cada nodo de la segunda capa puede recibir de 1 a n señales de entrada. La salida del nodo es el grado de cumplimiento de la regla, que se calcula como el producto de las señales de entrada. Denotemos las salidas de los nodos de esta capa por , .

Capa 3. El número de nodos en la tercera capa también es m. Cada nodo de esta capa calcula el grado relativo de cumplimiento de la regla difusa:

Capa 4. El número de nodos en la cuarta capa también es m. Cada nodo está conectado a un nodo de la tercera capa, así como a todas las entradas de la red (las conexiones con las entradas no se muestran en la Fig. 18). El nodo de cuarta capa calcula la contribución de una regla difusa a la salida de la red:

Capa 5. Un único nodo en esta capa resume las contribuciones de todas las reglas:

.

Se pueden utilizar procedimientos típicos para entrenar redes neuronales para configurar la red ANFIS, ya que solo utiliza funciones diferenciables. Normalmente, se utiliza una combinación de descenso de gradiente en forma de retropropagación y mínimos cuadrados. El algoritmo de retropropagación ajusta los parámetros de los antecedentes de las reglas, es decir funciones de membresía. Los coeficientes de las conclusiones de las reglas se estiman mediante el método de mínimos cuadrados, ya que están relacionados linealmente con la salida de la red. Cada iteración del procedimiento de configuración se realiza en dos pasos. En la primera etapa, se suministra una muestra de entrenamiento a las entradas y, en función de la discrepancia entre el comportamiento deseado y real de la red, se encuentran los parámetros óptimos de los nodos de la cuarta capa utilizando el método iterativo de mínimos cuadrados. En la segunda etapa, el residuo se transfiere de la salida de la red a las entradas y los parámetros de los nodos de la primera capa se modifican mediante el método de retropropagación. En este caso, los coeficientes de conclusión de la regla encontrados en la primera etapa no cambian. El procedimiento de ajuste iterativo continúa hasta que la discrepancia excede un valor predeterminado. Para configurar funciones de membresía, además del método de retropropagación, se pueden utilizar otros algoritmos de optimización, por ejemplo, el método Levenberg-Marquardt.

Fig.24. Área de trabajo de ANFISedit.

Intentemos ahora optimizar el controlador difuso para una acción de un solo paso. El proceso transitorio deseado tiene aproximadamente la siguiente forma:

Fig.25. Proceso de transición deseado.

Del gráfico mostrado en la Fig. De ello se deduce que la mayor parte del tiempo el motor debe funcionar a máxima potencia para garantizar el máximo rendimiento y, cuando se acerque al valor deseado, debe frenar suavemente. Guiados por estos sencillos argumentos, tomaremos la siguiente muestra de valores, presentada a continuación en forma de tabla, como muestra de entrenamiento:

Tabla 4

Fig.26. Tipo de muestra de formación.

Realizaremos la formación en 100 pasos. Esto es más que suficiente para la convergencia del método utilizado.

Fig.27. El proceso de entrenamiento de una red neuronal.

Durante el proceso de aprendizaje, los parámetros de las funciones de pertenencia se forman de tal manera que, para un valor de error dado, el controlador crea el control necesario. En la zona entre los puntos nodales, la dependencia del control del error es una interpolación de los datos de la tabla. El método de interpolación depende de cómo se entrena la red neuronal. De hecho, después del entrenamiento, el modelo de controlador difuso se puede representar como una función no lineal de una variable, cuyo gráfico se presenta a continuación.

Fig.28. Gráfico de control versus error de posición dentro del controlador.

Habiendo guardado los parámetros encontrados de las funciones de membresía, simulamos el sistema con un controlador difuso optimizado.

Arroz. 29. Proceso transitorio bajo acción de entrada armónica para un modelo con un controlador difuso optimizado que contiene una variable lingüística de entrada.

Fig.30. Señal de error bajo acción de entrada armónica para un modelo con un controlador difuso que contiene dos variables lingüísticas de entrada.

De los gráficos se desprende que la optimización del controlador difuso mediante entrenamiento de redes neuronales fue exitosa. La variabilidad y magnitud del error se redujeron significativamente. Por tanto, el uso de una red neuronal está bastante justificado para optimizar reguladores cuyo principio de funcionamiento se basa en lógica difusa. Sin embargo, incluso un controlador optimizado no puede satisfacer los requisitos de precisión, por lo que es aconsejable considerar otro método de control cuando el controlador difuso no controla directamente el objeto, sino que combina varias leyes de control dependiendo de la situación actual.

Motivación

Enfoque lógico

Designaciones

Enfoque probabilístico

Esta expresión puede interpretarse como una premisa, como una consecuencia, pero el paso de premisa a consecuencia obedecerá a leyes probabilísticas, no lógicas. Aquellos. En lugar de una tabla de verdad con valores booleanos 0 y 1 para una clase, habrá valores de probabilidad que oscilan entre 0 y 1. Aplique la fórmula de Bayes y obtenga la siguiente expresión:

Veamos el lado derecho de esta expresión con más detalle. El multiplicador se llama probabilidad previa y significa la probabilidad de encontrar una manzana sabrosa entre todas las manzanas posibles. Existe a priori una probabilidad de encontrarnos con una manzana insípida. Esta probabilidad puede reflejar nuestro conocimiento personal de cómo se distribuyen en la naturaleza las manzanas sabrosas y desagradables. Por ejemplo, por nuestra experiencia pasada sabemos que el 80% de todas las manzanas son sabrosas. O podemos estimar este valor simplemente calculando la proporción de manzanas sabrosas en nuestra lista con datos históricos S. El siguiente factor muestra la probabilidad de obtener un valor específico de color y tamaño para una manzana de clase 1. Esta expresión también se llama la función de probabilidad y puede verse así: alguna distribución específica, por ejemplo, normal. Usamos el denominador como constante de normalización para que la probabilidad deseada varíe de 0 a 1. Nuestro objetivo final no es buscar probabilidades, sino buscar una regla decisiva que nos dé inmediatamente la clase. La forma final de la regla de decisión depende de los valores y parámetros que conocemos. Por ejemplo, solo podemos conocer los valores de la probabilidad anterior y los valores restantes no se pueden estimar. Entonces la regla decisiva será ésta: asignar a todas las manzanas el valor de la clase para la cual la probabilidad a priori sea mayor. Aquellos. si sabemos que el 80% de las manzanas en la naturaleza son sabrosas, entonces le damos a cada manzana una clase 1. Entonces nuestro error será del 20%. Si también podemos estimar los valores de la función de probabilidad $p(X=x_m | Y=1)$, entonces podemos encontrar el valor de la probabilidad deseada usando la fórmula de Bayes, como se escribió anteriormente. La regla decisiva aquí será la siguiente: ponga una etiqueta para la clase para la cual la probabilidad es máxima:

Llamemos a esta regla clasificador bayesiano. Dado que estamos tratando con probabilidades, incluso un valor de probabilidad grande no garantiza que la manzana no pertenezca a la clase 0. Estimemos la probabilidad de un error en una manzana de la siguiente manera: si la regla de decisión arroja un valor de clase igual a 1 , entonces la probabilidad de error será y viceversa:

Nos interesa la probabilidad de un error en el clasificador no sólo en este ejemplo específico, sino en general para todas las manzanas posibles:

Esta expresión es el valor esperado del error. Entonces, resolviendo el problema original, llegamos al clasificador bayesiano, pero ¿cuáles son sus desventajas? El principal problema es estimar la probabilidad condicional a partir de los datos. En nuestro caso, representamos un objeto con un par de números: color y tamaño, pero en problemas más complejos la dimensión de las características puede ser muchas veces mayor y el número de observaciones de nuestra lista con datos históricos puede no ser suficiente para estimar el probabilidad de una variable aleatoria multidimensional. A continuación, intentaremos generalizar nuestro concepto de error de clasificador y también ver si es posible seleccionar algún otro clasificador para resolver el problema.

Pérdidas por errores del clasificador

Riesgo condicional y bayesiano

En nuestro caso de clasificación binaria cuando resulta:

Arriba describimos la regla de decisión, que asigna un objeto a la clase que tiene el valor de probabilidad más alto. Esta regla proporciona un mínimo a nuestras pérdidas promedio (riesgo bayesiano), por lo tanto, el clasificador bayesiano es óptimo desde el punto de vista de la función de riesgo. presentamos. Esto significa que el clasificador bayesiano tiene el menor error de clasificación posible.

Algunas funciones de pérdida típicas

Entonces el riesgo condicional para a(x) = 1 será simplemente el valor de la probabilidad de obtener clase 0 en el objeto:

De manera similar para a(x) = 0:

La función de pérdida 1-0 toma el valor 1 si el clasificador comete un error en el objeto y 0 si no lo hace. Ahora asegurémonos de que el valor del error no sea igual a 1, sino a otra función Q, dependiendo de la regla de decisión y la etiqueta de clase real:

Entonces el riesgo condicional se puede escribir de la siguiente manera:

Notas sobre notación

Donde está la función con la que intentamos aproximar la dependencia desconocida, es la función de pérdida para el valor real y el valor de nuestra función. Esta notación es más clara para introducir el siguiente concepto: riesgo empírico.

Riesgo empírico

Ejemplo: deja el conjunto de todas las funciones del formulario.

Todas las funciones de este conjunto se diferenciarán entre sí sólo por los coeficientes. Cuando elegimos dicha familia, asumimos que en las coordenadas de color y tamaño entre los puntos de clase 1 y los puntos de clase 0 podemos trazar una línea recta con coeficientes de este tipo. forma que puntos con diferentes clases se ubican a lo largo de diferentes lados de la línea recta. Se sabe que para una recta de este tipo el vector de coeficientes es normal a la recta. Ahora hacemos esto: tomamos nuestra manzana, medimos su color y tamaño y trazamos el punto con las coordenadas obtenidas en el gráfico en los ejes color-tamaño. A continuación, medimos el ángulo entre este punto y el vector $w$. Observamos que nuestro punto puede estar en uno u otro lado de la línea recta. Entonces el ángulo entre y el punto será agudo u obtuso, y el producto escalar será positivo o negativo. Esto lleva a la regla decisiva:

Después de haber fijado la clase de funciones $H$, surge la pregunta: ¿cómo seleccionar una función con los coeficientes requeridos? La respuesta es: elijamos la función que minimice nuestro riesgo bayesiano $R()$. Nuevamente, el problema es que para calcular los valores de riesgo bayesianos, es necesario conocer la distribución $p(x,y)$, pero no nos la proporcionan y no siempre es posible restaurarla. Otra idea es minimizar el riesgo no en todos los objetos posibles, sino sólo en una muestra. Aquellos. función de minimizar:

Esta función se llama riesgo empírico. La siguiente pregunta es ¿por qué decidimos que al minimizar el riesgo empírico también minimizamos el riesgo bayesiano? Permítanme recordarles que nuestra tarea práctica es cometer el menor número posible de errores de clasificación. Cuantos menos errores, menor será el riesgo bayesiano. La justificación de la convergencia del riesgo empírico al riesgo bayesiano con un volumen de datos creciente fue obtenida en los años 70 por dos científicos: V. N. Vapnik y A. Ya Chervonenkis.

Garantías de convergencia. El caso más simple

Teorema

¿Qué significa "valor pequeño" y "tamaño suficiente"? Consulte la literatura a continuación.

Idea de prueba

Resultados prácticos

Y sustituimos diferentes funciones de pérdida, dependiendo del problema que se esté resolviendo. Para regresión lineal:

Para regresión logística:

Aunque las máquinas de vectores de soporte tienen una motivación principalmente geométrica, también pueden considerarse como un problema empírico de minimización de riesgos.

Conclusión

Libros usados

• La naturaleza de la teoría del aprendizaje estadístico, Vladimir N. Vapnik
• Clasificación de patrones, segunda edición, Richard O. Duda, Peter E. Hart, David G. Stork
• Comprensión del aprendizaje automático: de la teoría a los algoritmos, Shai Shalev-Shwartz, Shai Ben-David

Etiquetas: Agregar etiquetas

Capítulo 3: Revisión analítica de los métodos de reconocimiento de patrones y toma de decisiones

Teoría del reconocimiento de patrones y automatización del control.

Principales tareas del reconocimiento de patrones adaptativos.

El reconocimiento es un proceso de información implementado por algún conversor de información (canal de información inteligente, sistema de reconocimiento) que tiene una entrada y una salida. La entrada del sistema es información sobre las características que tienen los objetos presentados. La salida del sistema muestra información sobre a qué clases (imágenes generalizadas) pertenecen los objetos reconocidos.

Al crear y operar un sistema automatizado de reconocimiento de patrones, se resuelven una serie de problemas. Consideremos breve y simplemente estas tareas. Tenga en cuenta que diferentes autores tienen las mismas formulaciones de estos problemas, y el conjunto en sí no coincide, ya que depende en cierta medida del modelo matemático específico en el que se basa tal o cual sistema de reconocimiento. Además, algunos problemas en determinados modelos de reconocimiento no tienen solución y, por tanto, no se plantean.

La tarea de formalizar el área temática.

Básicamente, esta tarea es una tarea de codificación. Se compila una lista de clases generalizadas a las que pueden pertenecer implementaciones específicas de objetos, así como una lista de características que estos objetos, en principio, pueden poseer.

La tarea de formar una muestra de entrenamiento.

El conjunto de entrenamiento es una base de datos que contiene descripciones de implementaciones de objetos específicos en el lenguaje de características, complementadas con información sobre la pertenencia de estos objetos a ciertas clases de reconocimiento.

Tarea de entrenamiento del sistema de reconocimiento.

La muestra de entrenamiento se utiliza para formar imágenes generalizadas de clases de reconocimiento basadas en la generalización de información sobre qué características tienen los objetos de la muestra de entrenamiento que pertenecen a esta clase y otras clases.

El problema de reducir la dimensión del espacio de características.

Después de entrenar el sistema de reconocimiento (obteniendo estadísticas sobre la distribución de frecuencia de características por clase), es posible determinar para cada característica su valor para resolver el problema de reconocimiento. Después de esto, las funciones menos valiosas se pueden eliminar del sistema de funciones. Luego, el sistema de reconocimiento debe entrenarse nuevamente, ya que como resultado de eliminar algunas características, las estadísticas de la distribución de las características restantes por clase cambian. Este proceso se puede repetir, es decir ser iterativo.

Tarea de reconocimiento

Se reconocen objetos de la muestra reconocida, que en particular pueden estar compuestos por un solo objeto. La muestra de reconocimiento se forma de manera similar a la de entrenamiento, pero no contiene información sobre la pertenencia de los objetos a las clases, ya que esto es precisamente lo que se determina durante el proceso de reconocimiento. El resultado de reconocer cada objeto es una distribución o lista de todas las clases de reconocimiento en orden descendente del grado de similitud del objeto reconocido con ellas.

Problema de control de calidad de reconocimiento.

Tras el reconocimiento, se podrá establecer su adecuación. Para los objetos de la muestra de entrenamiento, esto se puede hacer de inmediato, ya que para ellos simplemente se sabe a qué clases pertenecen. Para otros objetos esta información se puede obtener más adelante. En cualquier caso, se puede determinar la probabilidad media real de error para todas las clases de reconocimiento, así como la probabilidad de error al asignar un objeto reconocido a una clase específica.

Los resultados del reconocimiento deben interpretarse teniendo en cuenta la información disponible sobre la calidad del reconocimiento.

Problema de adaptación

Si como resultado del procedimiento de control de calidad se determina que no es satisfactorio, entonces las descripciones de los objetos reconocidos incorrectamente pueden copiarse de la muestra de reconocimiento a la de entrenamiento, complementarse con información de clasificación adecuada y usarse para reformatear las reglas de decisión. , es decir. tenido en cuenta. Además, si estos objetos no pertenecen a clases de reconocimiento existentes, lo que podría ser el motivo de su reconocimiento incorrecto, entonces esta lista se puede ampliar. Como resultado, el sistema de reconocimiento se adapta y comienza a clasificar adecuadamente estos objetos.

Problema de reconocimiento inverso

La tarea de reconocimiento es que para un objeto determinado, en función de sus características conocidas, el sistema establece su pertenencia a alguna clase previamente desconocida. En el problema de reconocimiento inverso, por el contrario, para una determinada clase de reconocimiento, el sistema establece qué características son más características de los objetos de esta clase y cuáles no (o qué objetos de la muestra de entrenamiento pertenecen a esta clase).

Problemas de cluster y análisis constructivo.

Los clústeres son grupos de objetos, clases o características que dentro de cada clúster son lo más similares posible y entre diferentes clústeres son lo más diferentes posible.

Un constructo (en el contexto analizado en esta sección) es un sistema de grupos opuestos. Así, en cierto sentido, los constructos son el resultado del análisis de conglomerados de conglomerados.

En el análisis de conglomerados, se mide cuantitativamente el grado de similitud y diferencia entre objetos (clases, características) y esta información se utiliza para la clasificación. El resultado del análisis de conglomerados es la clasificación de objetos en conglomerados. Esta clasificación se puede representar en forma de redes semánticas.

Tarea de análisis cognitivo

En el análisis cognitivo, la información sobre las similitudes y diferencias entre clases o características es de interés para el investigador en sí misma, y ​​no para utilizarla para la clasificación, como en el análisis constructivo y de conglomerados.

Si el mismo rasgo es característico de dos clases de reconocimiento, esto contribuye a la similitud de estas dos clases. Si para una de las clases esta característica no es característica, entonces esto contribuye a la diferencia.

Si dos características se correlacionan entre sí, entonces, en cierto sentido, pueden considerarse como una característica, y si están anticorrelacionadas, entonces como diferentes. Teniendo en cuenta esta circunstancia, la presencia de diferentes características en diferentes clases también contribuye en cierta medida a su similitud y diferencia.

Los resultados del análisis cognitivo se pueden presentar en forma de diagramas cognitivos.

Métodos de reconocimiento de patrones y sus características.

Principios de clasificación de métodos de reconocimiento de patrones.

El reconocimiento de patrones se refiere al problema de construir y aplicar operaciones formales sobre representaciones numéricas o simbólicas de objetos en el mundo real o ideal, cuyos resultados reflejan las relaciones de equivalencia entre estos objetos. Las relaciones de equivalencia expresan la pertenencia de los objetos evaluados a cualesquiera clases, consideradas como unidades semánticas independientes.

Al construir algoritmos de reconocimiento, las clases de equivalencia pueden ser especificadas por un investigador que utiliza sus propias ideas significativas o utiliza información adicional externa sobre las similitudes y diferencias de los objetos en el contexto del problema que se está resolviendo. Luego hablan de “reconocimiento con un maestro”. De lo contrario, es decir Cuando un sistema automatizado resuelve un problema de clasificación sin el uso de información de entrenamiento externo, hablamos de clasificación automática o "reconocimiento no supervisado". La mayoría de los algoritmos de reconocimiento de patrones requieren el uso de una potencia informática muy significativa, que sólo puede ser proporcionada por tecnología informática de alto rendimiento.

Varios autores (Yu.L. Barabash, V.I. Vasiliev, A.L. Gorelik, V.A. Skripkin, R. Duda, P. Hart, L.T. Kuzin, F.I. Peregudov, F.P. Tarasenko, F.E. Temnikov, J. Tu, R. González, P. Winston, K. Fu, Ya.Z. Tsypkin, etc.) dan una tipología diferente de métodos de reconocimiento de patrones. Algunos autores distinguen entre métodos paramétricos, no paramétricos y heurísticos, otros identifican grupos de métodos basados ​​en escuelas y tendencias históricamente establecidas en este campo. Por ejemplo, en el trabajo, que proporciona una descripción académica de los métodos de reconocimiento, se utiliza la siguiente tipología de métodos de reconocimiento de patrones:

• métodos basados ​​en el principio de separación;
• métodos de estadística;
• métodos construidos sobre la base de “funciones potenciales”;
• métodos para calcular calificaciones (votación);
• métodos basados ​​en el cálculo proposicional, en particular en el aparato de álgebra lógica.

Esta clasificación se basa en la diferencia en los métodos formales de reconocimiento de patrones y, por lo tanto, omite la consideración del enfoque heurístico del reconocimiento, que ha recibido un desarrollo completo y adecuado en los sistemas expertos. El enfoque heurístico se basa en el conocimiento y la intuición del investigador, difíciles de formalizar. En este caso, el propio investigador determina qué información y cómo debe utilizar el sistema para lograr el efecto de reconocimiento requerido.

En muchos trabajos sobre reconocimiento se encuentra una tipología similar de métodos de reconocimiento con distintos grados de detalle. Al mismo tiempo, las tipologías conocidas no tienen en cuenta una característica muy significativa, que refleja la especificidad de la forma de representar el conocimiento sobre un área temática utilizando cualquier algoritmo formal de reconocimiento de patrones.

D.A. Pospelov (1990) identifica dos formas principales de presentar el conocimiento:

• intencional, en forma de diagrama de conexiones entre atributos (características).
• extensional, con la ayuda de hechos específicos (objetos, ejemplos).

La representación intencional captura los patrones y conexiones que explican la estructura de los datos. En relación con las tareas de diagnóstico, dicha fijación consiste en definir operaciones sobre atributos (características) de los objetos que conducen al resultado de diagnóstico requerido. Las representaciones intencionales se implementan mediante operaciones sobre valores de atributos y no implican operaciones sobre hechos de información específicos (objetos).

A su vez, las representaciones extensionales del conocimiento están asociadas a la descripción y fijación de objetos específicos del área temática y se implementan en operaciones, cuyos elementos son objetos como sistemas integrales.

Se puede establecer una analogía entre las representaciones intensionales y extensionales del conocimiento y los mecanismos subyacentes a la actividad de los hemisferios izquierdo y derecho del cerebro humano. Si el hemisferio derecho se caracteriza por una representación prototipo holística del mundo circundante, entonces el hemisferio izquierdo opera con patrones que reflejan las conexiones entre los atributos de este mundo.

Las dos formas fundamentales de representar el conocimiento descritas anteriormente nos permiten proponer la siguiente clasificación de métodos de reconocimiento de patrones:

• Métodos intencionales basados ​​en operaciones con atributos.
• Métodos extensionales basados ​​en operaciones con objetos.

Hay que subrayar especialmente que la existencia de precisamente estos dos (y sólo dos) grupos de métodos de reconocimiento: los que operan con signos y los que operan con objetos, es profundamente natural. Desde este punto de vista, ninguno de estos métodos, tomados por separado del otro, nos permite formar una reflexión adecuada del área temática. Según los autores, existe una relación de complementariedad entre estos métodos en el sentido de N. Bohr, por lo que los sistemas de reconocimiento prometedores deberían prever la implementación de ambos métodos, y no cualquiera de ellos.

Así, la clasificación de los métodos de reconocimiento propuesta por D. A. Pospelov se basa en los patrones fundamentales que subyacen al modo de conocimiento humano en general, lo que lo coloca en una posición completamente especial (privilegiada) en comparación con otras clasificaciones que, en este contexto, parecen más ligeras y artificial.

Métodos intensionales

Una característica distintiva de los métodos intensionales es que utilizan diversas características de características y sus conexiones como elementos de operaciones al construir y aplicar algoritmos de reconocimiento de patrones. Dichos elementos pueden ser valores individuales o intervalos de valores de características, valores promedio y variaciones, matrices de relaciones de características, etc., sobre las cuales se realizan acciones, expresadas en forma analítica o constructiva. Al mismo tiempo, los objetos en estos métodos no se consideran unidades de información integral, sino que actúan como indicadores para evaluar la interacción y el comportamiento de sus atributos.

El grupo de métodos intensionales para el reconocimiento de patrones es extenso y su división en subclases es hasta cierto punto condicional.

Métodos basados ​​en estimaciones de densidades de distribución de valores de características.

Estos métodos de reconocimiento de patrones se toman prestados de la teoría clásica de las decisiones estadísticas, en la que los objetos de estudio se consideran realizaciones de una variable aleatoria multidimensional distribuida en el espacio de características de acuerdo con alguna ley. Se basan en un esquema de toma de decisiones bayesiano que apela a probabilidades a priori de objetos que pertenecen a una clase reconocida particular y densidades de distribución condicionales de valores de vectores de características. Estos métodos se reducen a determinar la relación de probabilidad en varias áreas del espacio de características multidimensionales.

Un grupo de métodos basados ​​en la estimación de las densidades de distribución de valores característicos está directamente relacionado con los métodos de análisis discriminante. El enfoque bayesiano para la toma de decisiones es uno de los llamados métodos paramétricos más desarrollados en la estadística moderna, para el cual la expresión analítica de la ley de distribución (en este caso, la ley normal) se considera conocida y solo un pequeño número de parámetros ( Se requieren vectores de valores promedio y matrices de covarianza).

Las principales dificultades al utilizar estos métodos son la necesidad de recordar toda la muestra de entrenamiento para calcular estimaciones de las densidades de distribución de probabilidad local y la alta sensibilidad a la falta de representatividad de la muestra de entrenamiento.

Métodos basados ​​en supuestos sobre la clase de funciones de decisión.

En este grupo de métodos se considera conocida la forma general de la función de decisión y se especifica la funcionalidad de su calidad. Con base en esta funcional, la mejor aproximación de la función de decisión se encuentra utilizando la secuencia de entrenamiento. Las más comunes son las representaciones de funciones de decisión en forma de polinomios lineales y no lineales generalizados. La regla de decisión funcional de calidad suele estar asociada con un error de clasificación.

La principal ventaja de los métodos basados ​​​​en supuestos sobre la clase de funciones de decisión es la claridad de la formulación matemática del problema de reconocimiento como un problema de búsqueda de un extremo. La variedad de métodos en este grupo se explica por la amplia gama de funcionales de calidad de reglas de decisión y algoritmos de búsqueda extremos utilizados. Una generalización de los algoritmos considerados, que incluyen, en particular, el algoritmo de Newton, los algoritmos de tipo perceptrón, etc., es el método de aproximación estocástica.

Las capacidades de los algoritmos de búsqueda de extremos de gradiente, especialmente en el grupo de reglas de decisión lineal, han sido bastante estudiadas. La convergencia de estos algoritmos se ha demostrado sólo en el caso en que las clases de objetos reconocidas se muestran en el espacio de características mediante estructuras geométricas compactas.

Se puede lograr una calidad suficientemente alta de la regla de decisión utilizando algoritmos que no tienen una prueba matemática estricta de la convergencia de la solución a un extremo global. Dichos algoritmos incluyen un gran grupo de procedimientos de programación heurística que representan la dirección del modelado evolutivo. El modelado evolutivo es un método biónico tomado de la naturaleza. Se basa en el uso de mecanismos de evolución conocidos para reemplazar el proceso de modelado significativo de un objeto complejo por el modelado fenomenológico de su evolución. Un conocido representante del modelado evolutivo en el reconocimiento de patrones es el método de contabilidad grupal de argumentos (MGUA). La base de GMDH es el principio de autoorganización y los algoritmos de GMDH reproducen el esquema de selección masiva.

Sin embargo, el logro de objetivos prácticos en este caso no va acompañado de la extracción de nuevos conocimientos sobre la naturaleza de los objetos que se reconocen. La posibilidad de extraer este conocimiento, en particular el conocimiento sobre los mecanismos de interacción de atributos (características), está aquí fundamentalmente limitada por la estructura dada de dicha interacción, fijada en la forma seleccionada de funciones de decisión.

Métodos booleanos

Los métodos lógicos de reconocimiento de patrones se basan en el aparato del álgebra lógica y permiten operar con información contenida no sólo en características individuales, sino también en combinaciones de valores de características. En estos métodos, los valores de cualquier atributo se consideran eventos elementales.

En su forma más general, los métodos lógicos se pueden caracterizar como un tipo de búsqueda a través de una muestra de entrenamiento de patrones lógicos y la formación de un determinado sistema de reglas de decisión lógica (por ejemplo, en forma de conjunciones de eventos elementales), cada una de las cuales que tiene su propio peso. El grupo de métodos lógicos es diverso e incluye métodos de diversa complejidad y profundidad de análisis. Para características dicotómicas (booleanas), son populares los llamados clasificadores en forma de árbol, el método de prueba sin salida, el algoritmo "Bark", etc.

El algoritmo "Kora", al igual que otros métodos lógicos de reconocimiento de patrones, requiere un uso computacional bastante intensivo, ya que se requiere una búsqueda completa al seleccionar conjunciones. Por lo tanto, cuando se utilizan métodos lógicos, se imponen grandes exigencias a la organización eficiente del proceso computacional, y estos métodos funcionan bien con dimensiones relativamente pequeñas del espacio de características y solo en computadoras potentes.

Métodos lingüísticos (estructurales)

Los métodos lingüísticos de reconocimiento de patrones se basan en el uso de gramáticas especiales que generan lenguajes que pueden usarse para describir el conjunto de propiedades de los objetos reconocidos.

Para varias clases de objetos, se identifican elementos no derivados (atómicos) (subimágenes, atributos) y posibles relaciones entre ellos. La gramática se refiere a las reglas para construir objetos a partir de estos elementos no derivados.

Así, cada objeto es una colección de elementos no derivados, “conectados” entre sí de una forma u otra o, en otras palabras, por una “frase” de algún “lenguaje”. Me gustaría subrayar especialmente el valor ideológico muy significativo de este pensamiento.

Al analizar sintácticamente una “oración” se determina su “corrección” sintáctica o, de manera equivalente, si alguna gramática fija que describe una clase puede generar la descripción existente de un objeto.

Sin embargo, la tarea de reconstruir (definir) gramáticas a partir de un determinado conjunto de enunciados (oraciones - descripciones de objetos) que generan un lenguaje determinado es difícil de formalizar.

Métodos extensionales

En los métodos de este grupo, a diferencia de la dirección intensional, a cada objeto estudiado se le otorga, en mayor o menor medida, un significado diagnóstico independiente. En esencia, estos métodos se acercan al enfoque clínico, que considera a las personas no como una cadena de objetos clasificados según un indicador u otro, sino como sistemas integrales, cada uno de los cuales es individual y tiene un valor diagnóstico especial. Esta actitud cuidadosa hacia los objetos de investigación no permite excluir o perder información sobre cada objeto individual, lo que ocurre cuando se utilizan métodos de dirección intencional que utilizan objetos sólo para detectar y registrar patrones de comportamiento de sus atributos.

Las principales operaciones en el reconocimiento de patrones utilizando los métodos discutidos son las operaciones para determinar las similitudes y diferencias de objetos. Los objetos del grupo de métodos especificado desempeñan el papel de precedentes de diagnóstico. Además, dependiendo de las condiciones de una tarea específica, el papel de un precedente individual puede variar dentro de los límites más amplios: desde el principal y determinante hasta la participación muy indirecta en el proceso de reconocimiento. A su vez, las condiciones del problema pueden requerir la participación de un número diferente de precedentes de diagnóstico para una solución exitosa: desde uno en cada clase reconocida hasta el tamaño completo de la muestra, así como diferentes métodos para calcular medidas de similitud y diferencia entre objetos. . Estos requisitos explican la división adicional de los métodos extensionales en subclases.

Método de comparación con un prototipo.

Este es el método de reconocimiento extensional más simple. Se utiliza, por ejemplo, en el caso en que las clases reconocidas se muestran en el espacio de características mediante agrupaciones geométricas compactas. En este caso, normalmente se selecciona como punto prototipo el centro de la agrupación geométrica de la clase (o el objeto más cercano al centro).

Para clasificar un objeto desconocido, se encuentra el prototipo más cercano a él y el objeto pertenece a la misma clase que este prototipo. Obviamente, en este método no se generan imágenes de clases generalizadas.

Se pueden utilizar varios tipos de distancias como medida de proximidad. A menudo, para características dicotómicas, se utiliza la distancia de Hamming, que en este caso es igual al cuadrado de la distancia euclidiana. En este caso, la regla de decisión para clasificar objetos es equivalente a una función de decisión lineal.

Este hecho debe destacarse especialmente. Demuestra claramente la conexión entre el prototipo y la representación de atributos de información sobre la estructura de los datos. Utilizando la representación anterior, se puede, por ejemplo, considerar cualquier escala de medición tradicional, que sea una función lineal de los valores de características dicotómicas, como un prototipo de diagnóstico hipotético. A su vez, si el análisis de la estructura espacial de las clases reconocidas nos permite sacar una conclusión sobre su compacidad geométrica, entonces basta con reemplazar cada una de estas clases con un prototipo, que en realidad equivale a un modelo de diagnóstico lineal.

En la práctica, por supuesto, la situación suele ser diferente del ejemplo idealizado descrito. Un investigador que pretende aplicar un método de reconocimiento basado en la comparación con clases de diagnóstico prototipo se enfrenta a problemas difíciles.

En primer lugar, se trata de la elección de la medida de proximidad (métrica), que puede cambiar significativamente la configuración espacial de la distribución de los objetos. En segundo lugar, un problema independiente es el análisis de estructuras multidimensionales de datos experimentales. Ambos problemas son especialmente graves para el investigador en condiciones de alta dimensionalidad del espacio de características, característica de los problemas reales.

k método de vecinos más cercanos

El método del vecino más cercano para resolver problemas de análisis discriminante se propuso por primera vez en 1952. Es el siguiente.

Al clasificar un objeto desconocido, se encuentra un número dado (k) de características geométricamente más cercanas a él en el espacio de otros objetos (vecinos más cercanos) con pertenencia ya conocida a las clases reconocidas. La decisión de asignar un objeto desconocido a una clase de diagnóstico particular se toma analizando información sobre esta afiliación conocida de sus vecinos más cercanos, por ejemplo, utilizando un simple recuento de votos.

Inicialmente, el método de los k vecinos más cercanos se consideró como un método no paramétrico para estimar la razón de verosimilitud. Para este método, se obtuvieron estimaciones teóricas de su efectividad en comparación con el clasificador bayesiano óptimo. Se ha demostrado que las probabilidades de error asintótico para el método de los k vecinos más cercanos exceden los errores de la regla de Bayes en no más del doble.

Cuando se utiliza el método de los k vecinos más cercanos para el reconocimiento de patrones, el investigador tiene que resolver el difícil problema de elegir una métrica para determinar la proximidad de los objetos diagnosticados. Este problema en condiciones de alta dimensionalidad del espacio de características se agrava enormemente debido a la suficiente complejidad de este método, que resulta significativo incluso para computadoras de alto rendimiento. Por lo tanto, aquí, al igual que en el método de comparación con un prototipo, es necesario resolver el problema creativo de analizar la estructura multidimensional de los datos experimentales para minimizar el número de objetos que representan clases de diagnóstico.

La necesidad de reducir el número de objetos en la muestra de entrenamiento (precedentes de diagnóstico) es una desventaja de este método, ya que reduce la representatividad de la muestra de entrenamiento.

Algoritmos para calcular calificaciones (“votación”)

El principio de funcionamiento de los algoritmos de cálculo de evaluación (ABO) es calcular prioridades (puntuaciones de similitud) que caracterizan la "proximidad" de los objetos reconocidos y de referencia de acuerdo con un sistema de conjuntos de características, que es un sistema de subconjuntos de un conjunto de características dado. .

A diferencia de todos los métodos discutidos anteriormente, los algoritmos para calcular estimaciones operan con descripciones de objetos de una manera fundamentalmente nueva. Para estos algoritmos, los objetos existen simultáneamente en subespacios muy diferentes del espacio de características. La clase ABO lleva la idea de utilizar características a su conclusión lógica: dado que no siempre se sabe qué combinaciones de características son las más informativas, en ABO el grado de similitud de los objetos se calcula comparando todas las combinaciones posibles o específicas de características incluidas en las descripciones de los objetos.

Los autores denominan a las combinaciones de características utilizadas (subespacios) conjuntos de soporte o conjuntos de descripciones parciales de objetos. Se introduce el concepto de proximidad generalizada entre el objeto reconocido y los objetos de la muestra de entrenamiento (con una clasificación conocida), que se denominan objetos de referencia. Esta proximidad está representada por una combinación de la proximidad del objeto reconocido con los objetos de referencia, calculada sobre conjuntos de descripciones parciales. Por tanto, ABO es una extensión del método de los k vecinos más cercanos, en el que la proximidad de los objetos se considera sólo en un espacio de características determinado.

Otra extensión del ABO es que en estos algoritmos la tarea de determinar la similitud y diferencia de objetos se formula como paramétrica y se resalta la etapa de configuración del ABO en base al conjunto de entrenamiento, en el que se determinan los valores óptimos de los ingresados. Se seleccionan los parámetros. El criterio de calidad es el error de reconocimiento, y literalmente todo está parametrizado:

• reglas para calcular la proximidad de objetos en función de características individuales;
• reglas para calcular la proximidad de objetos en subespacios de características;
• el grado de importancia de un objeto de referencia particular como precedente de diagnóstico;
• la importancia de la contribución de cada conjunto de características de referencia a la evaluación final de la similitud del objeto reconocido con cualquier clase de diagnóstico.

Los parámetros ABO se especifican en forma de valores umbral y (o) como pesos de los componentes especificados.

Las capacidades teóricas de AVO no son al menos inferiores a las de cualquier otro algoritmo de reconocimiento de patrones, ya que con la ayuda de AVO se pueden implementar todas las operaciones imaginables con los objetos en estudio.

Pero, como suele ocurrir, la ampliación de las capacidades potenciales tropieza con grandes dificultades en su implementación práctica, especialmente en la etapa de construcción (ajuste) de algoritmos de este tipo.

Se observaron algunas dificultades anteriormente al analizar el método de los k vecinos más cercanos, que podría interpretarse como una versión truncada de ABO. También se puede considerar en forma paramétrica y reducir el problema a encontrar una métrica ponderada del tipo seleccionado. Al mismo tiempo, ya aquí, para problemas de alta dimensión, surgen cuestiones teóricas complejas y problemas relacionados con la organización de un proceso computacional efectivo.

Para AVO, si intenta utilizar las capacidades de estos algoritmos al máximo, estas dificultades aumentan muchas veces.

Los problemas señalados explican que en la práctica, el uso de ABO para resolver problemas de alta dimensión va acompañado de la introducción de algunas restricciones y suposiciones heurísticas. En particular, existe un ejemplo bien conocido del uso de ABO en psicodiagnóstico, en el que se probó un tipo de ABO que en realidad equivale al método de los k vecinos más cercanos.

Colectivos de reglas de decisión

Para completar nuestra revisión de los métodos de reconocimiento de patrones, veamos un enfoque más. Estos son los llamados colectivos de reglas de decisión (DRG).

Dado que diferentes algoritmos de reconocimiento se manifiestan de manera diferente en la misma muestra de objetos, naturalmente surge la cuestión de una regla de decisión sintética que utilice de manera adaptativa las fortalezas de estos algoritmos. La regla de decisión sintética utiliza un esquema de reconocimiento de dos niveles. En el primer nivel operan algoritmos de reconocimiento privado, cuyos resultados se combinan en el segundo nivel en el bloque de síntesis. Los métodos más comunes de dicha unificación se basan en identificar áreas de competencia de un algoritmo en particular. La forma más sencilla de encontrar áreas de competencia es dividir a priori el espacio de atributos basándose en consideraciones profesionales de una ciencia en particular (por ejemplo, estratificar la muestra según un determinado atributo). Luego, para cada una de las áreas seleccionadas, se construye su propio algoritmo de reconocimiento. Otro método se basa en el uso de análisis formal para determinar áreas locales del espacio de características como vecindades de objetos reconocidos para los cuales se ha demostrado el éxito de cualquier algoritmo de reconocimiento particular.

El enfoque más general para construir un bloque de síntesis considera los indicadores resultantes de algoritmos particulares como las características iniciales para construir una nueva regla de decisión generalizada. En este caso, se pueden utilizar todos los métodos anteriores de direcciones intensionales y extensionales en el reconocimiento de patrones. Para resolver el problema de crear un grupo de reglas de decisión son eficaces los algoritmos lógicos del tipo "Kora" y los algoritmos de cálculo de estimaciones (ABO), que forman la base del llamado enfoque algebraico, que proporciona el estudio y la descripción constructiva de algoritmos de reconocimiento, en cuyo marco encajan todos los tipos de algoritmos existentes.

Análisis comparativo de métodos de reconocimiento de patrones.

Comparemos los métodos de reconocimiento de patrones descritos anteriormente y evaluemos el grado de adecuación a los requisitos formulados en la Sección 3.3.3 para modelos SDA para sistemas de control automatizados adaptativos para sistemas complejos.

Para resolver problemas reales del grupo de métodos intensionales, los métodos paramétricos y los métodos basados ​​​​en propuestas sobre la forma de las funciones de decisión tienen valor práctico. Los métodos paramétricos forman la base de la metodología tradicional para la construcción de indicadores. La aplicación de estos métodos en problemas reales está asociada a la imposición de fuertes restricciones a la estructura de datos, que conducen a modelos de diagnóstico lineales con estimaciones muy aproximadas de sus parámetros. Cuando se utilizan métodos basados ​​en suposiciones sobre la forma de las funciones de decisión, el investigador también se ve obligado a recurrir a modelos lineales. Esto se debe a la alta dimensionalidad del espacio de características, característica de los problemas reales, que, al aumentar el grado de la función de decisión polinómica, da un enorme aumento en el número de sus miembros con un problemático aumento concomitante en la calidad del reconocimiento. Así, al proyectar el área de aplicación potencial de los métodos de reconocimiento intensional en problemas reales, obtenemos una imagen que corresponde a la metodología tradicional bien desarrollada de los modelos de diagnóstico lineal.

Se han estudiado bien las propiedades de los modelos de diagnóstico lineal, en los que el indicador de diagnóstico está representado por una suma ponderada de las características iniciales. Los resultados de estos modelos (con la normalización adecuada) se interpretan como distancias desde los objetos en estudio a algún hiperplano en el espacio de características o, de manera equivalente, como proyecciones de objetos sobre alguna línea recta en este espacio. Por lo tanto, los modelos lineales son adecuados sólo para configuraciones geométricas simples de áreas del espacio de características en las que se asignan objetos de diferentes clases de diagnóstico. Con distribuciones más complejas, estos modelos fundamentalmente no pueden reflejar muchas características de la estructura de los datos experimentales. Al mismo tiempo, estas funciones pueden proporcionar información de diagnóstico valiosa.

Al mismo tiempo, la aparición en cualquier problema real de estructuras multidimensionales simples (en particular, distribuciones normales multidimensionales) debe considerarse como una excepción y no como una regla. A menudo, las clases de diagnóstico se forman sobre la base de criterios externos complejos, lo que automáticamente implica una heterogeneidad geométrica de estas clases en el espacio de características. Esto es especialmente cierto en el caso de los criterios “vitales”, que son los que se encuentran con más frecuencia en la práctica. En tales condiciones, el uso de modelos lineales captura sólo los patrones más “aproximados” de información experimental.

El uso de métodos extensionales no está asociado con ninguna suposición sobre la estructura de la información experimental, excepto que dentro de las clases reconocidas debe haber uno o más grupos de objetos algo similares, y los objetos de diferentes clases deben ser algo diferentes entre sí. Obviamente, para cualquier tamaño finito de la muestra de entrenamiento (y no puede ser otro), este requisito siempre se cumple simplemente porque existen diferencias aleatorias entre los objetos. Como medidas de similitud, se utilizan varias medidas de proximidad (distancia) de objetos en el espacio característico. Por lo tanto, el uso efectivo de métodos extensionales de reconocimiento de patrones depende de qué tan bien se determinen las medidas de proximidad especificadas, así como de qué objetos de la muestra de entrenamiento (objetos con una clasificación conocida) sirven como precedentes de diagnóstico. La solución exitosa de estos problemas da resultados que se acercan a los límites teóricamente alcanzables de eficiencia de reconocimiento.

Las ventajas de los métodos extensionales de reconocimiento de patrones se ven contrarrestadas, en primer lugar, por la alta complejidad técnica de su implementación práctica. Para espacios de características de alta dimensión, la tarea aparentemente simple de encontrar pares de puntos más cercanos se convierte en un problema grave. Además, muchos autores señalan como problema la necesidad de recordar una cantidad suficientemente grande de objetos que representan clases reconocidas.

Esto en sí mismo no es un problema, pero se percibe como un problema (por ejemplo, en el método de k vecinos más cercanos) porque al reconocer cada objeto, se produce una búsqueda completa de todos los objetos en el conjunto de entrenamiento.

Por tanto, es recomendable aplicar un modelo de sistema de reconocimiento en el que se elimine el problema de una enumeración completa de objetos en la muestra de entrenamiento durante el reconocimiento, ya que se realiza solo una vez al generar imágenes generalizadas de clases de reconocimiento. Durante el reconocimiento en sí, el objeto identificado se compara sólo con imágenes generalizadas de clases de reconocimiento, cuyo número es fijo y completamente independiente del tamaño de la muestra de entrenamiento. Este enfoque le permite aumentar el tamaño de la muestra de entrenamiento hasta lograr la alta calidad requerida de imágenes generalizadas, sin temor a que esto pueda conducir a un aumento inaceptable en el tiempo de reconocimiento (ya que el tiempo de reconocimiento en este modelo no depende de la tamaño de la muestra de entrenamiento).

Los problemas teóricos del uso de métodos de reconocimiento extensional están asociados con los problemas de buscar grupos informativos de características, encontrar métricas óptimas para medir las similitudes y diferencias de objetos y analizar la estructura de la información experimental. Al mismo tiempo, la solución exitosa de estos problemas permite no solo construir algoritmos de reconocimiento efectivos, sino también hacer una transición del conocimiento extensional de hechos empíricos al conocimiento intensional sobre los patrones de su estructura.

La transición del conocimiento extensional al intensional ocurre en la etapa en la que ya se ha construido un algoritmo de reconocimiento formal y se ha demostrado su eficacia. Luego se estudian los mecanismos mediante los cuales se logra la eficiencia resultante. Un estudio de este tipo, asociado al análisis de la estructura geométrica de los datos, puede, por ejemplo, llevar a la conclusión de que basta con sustituir los objetos que representan una determinada clase diagnóstica por un representante típico (prototipo). Esto equivale, como se señaló anteriormente, a especificar una escala de diagnóstico lineal tradicional. También es posible que sea suficiente reemplazar cada clase de diagnóstico con varios objetos, conceptualizados como representantes típicos de algunas subclases, lo que equivale a construir un abanico de escalas lineales. Hay otras opciones que se discutirán a continuación.

Por lo tanto, una revisión de los métodos de reconocimiento muestra que ahora se han desarrollado teóricamente varios métodos diferentes de reconocimiento de patrones. La literatura proporciona una clasificación detallada de ellos. Sin embargo, para la mayoría de estos métodos no existe una implementación de software, y esto es profundamente natural, incluso se podría decir "predeterminado" por las características de los propios métodos de reconocimiento. Esto se puede juzgar por el hecho de que estos sistemas rara vez se mencionan en la literatura especializada y otras fuentes de información.

En consecuencia, la cuestión de la aplicabilidad práctica de ciertos métodos de reconocimiento teórico para resolver problemas prácticos con dimensiones de datos reales (es decir, bastante significativas) y en computadoras modernas reales sigue estando insuficientemente desarrollada.

La circunstancia anterior se puede entender si recordamos que la complejidad del modelo matemático aumenta exponencialmente la complejidad de la implementación del software del sistema y en la misma medida reduce las posibilidades de que este sistema funcione prácticamente. Esto significa que, en realidad, sólo se pueden implementar en el mercado sistemas de software que se basen en modelos matemáticos bastante simples y “transparentes”. Por lo tanto, un desarrollador interesado en replicar su producto de software aborda la cuestión de elegir un modelo matemático no desde un punto de vista puramente científico, sino como pragmático, teniendo en cuenta las posibilidades de implementación del software. Considera que el modelo debe ser lo más simple posible, es decir, implementarse a menor costo y con mejor calidad, y además debe funcionar (ser prácticamente efectivo).

En este sentido, parece especialmente relevante la tarea de implementar en los sistemas de reconocimiento un mecanismo para generalizar descripciones de objetos que pertenecen a la misma clase, es decir. Mecanismo para la formación de imágenes compactas generalizadas. Obviamente, tal mecanismo de generalización permitirá "comprimir" una muestra de entrenamiento de cualquier dimensión en una base de datos de imágenes generalizadas conocidas de antemano por dimensión. Esto también permitirá plantear y resolver una serie de problemas que ni siquiera pueden formularse con métodos de reconocimiento como el método de comparación con un prototipo, el método de los k vecinos más cercanos y ABO.

Estas son las tareas:

• determinar la contribución de información de las características al retrato informativo de una imagen generalizada;
• análisis constructivo de grupos de imágenes generalizadas;
• determinación de la carga semántica de una característica;
• análisis semántico de características constructivas de grupos;
• comparación significativa de imágenes generalizadas de clases entre sí y características entre sí (diagramas cognitivos, incluidos los diagramas de Merlín).

El método que permitió resolver estos problemas también distingue al prometedor sistema basado en él de otros sistemas, así como los compiladores se diferencian de los intérpretes, ya que gracias a la formación de imágenes generalizadas en este prometedor sistema, la independencia del tiempo de reconocimiento del Se logra el tamaño de la muestra de entrenamiento. Se sabe que es la existencia de esta dependencia la que conduce a costos prácticamente inaceptables de tiempo de computadora para el reconocimiento en métodos como el método de los k vecinos más cercanos, ABO y KRP en tales dimensiones de la muestra de entrenamiento cuando podemos hablar de estadísticas suficientes. .

Para concluir una breve descripción de los métodos de reconocimiento, presentemos la esencia de lo anterior en una tabla resumen (Tabla 3.1), que contiene una breve descripción de varios métodos de reconocimiento de patrones de acuerdo con los siguientes parámetros:

• clasificación de métodos de reconocimiento;
• áreas de aplicación de métodos de reconocimiento;
• clasificación de limitaciones de los métodos de reconocimiento.

Tabla 3.1 — Cuadro resumen de clasificación de métodos de reconocimiento, comparación de sus áreas de aplicación y limitaciones

El papel y el lugar del reconocimiento de patrones en la automatización del control de sistemas complejos.

Un sistema de control automatizado consta de dos partes principales: un objeto de control y un sistema de control.

El sistema de control realiza las siguientes funciones:

• identificación del estado del objeto de control;
• desarrollo de acciones de control basadas en objetivos de gestión, teniendo en cuenta el estado del objeto de control y el medio ambiente;
• proporcionar influencia de control sobre el objeto de control.

El reconocimiento de patrones no es más que identificar el estado de algún objeto.

En consecuencia, la posibilidad de utilizar un sistema de reconocimiento de patrones en la etapa de identificación del estado de un objeto de control parece bastante obvia y natural. Sin embargo, esto puede no ser necesario. Por tanto, surge la duda de en qué casos es recomendable utilizar un sistema de reconocimiento en un sistema de control automatizado, y en cuáles no.

Según la literatura, muchos sistemas de control automatizados modernos y previamente desarrollados en los subsistemas para identificar el estado del objeto de control y desarrollar acciones de control utilizan modelos matemáticos deterministas de "cálculo directo", que determinan de manera inequívoca y sencilla qué hacer con el control. objeto si tiene ciertos parámetros externos.

Al mismo tiempo, no se plantea ni se resuelve la cuestión de cómo se relacionan estos parámetros con ciertos estados del objeto de control. Esta posición corresponde al punto de vista de que “por defecto” se acepta su relación uno a uno. Por lo tanto, los términos "parámetros del objeto de control" y "estado del objeto de control" se consideran sinónimos, y el concepto de "estado del objeto de control" no se introduce explícitamente en absoluto. Sin embargo, es obvio que en el caso general la relación entre los parámetros observables del objeto de control y su estado es de naturaleza dinámica y probabilística.

Por tanto, los sistemas de control automatizados tradicionales son esencialmente sistemas de control paramétrico, es decir. sistemas que gestionan no los estados del objeto de control, sino solo sus parámetros observables. La decisión sobre la acción de control se toma en tales sistemas como "a ciegas", es decir. sin formar una imagen holística del objeto de control y el medio ambiente en su estado actual, así como sin predecir el desarrollo del medio ambiente y la reacción del objeto de control a ciertas influencias de control sobre él, actuando simultáneamente con la influencia prevista del medio ambiente. .

Desde la perspectiva desarrollada en este trabajo, el término "toma de decisiones" en el sentido moderno difícilmente es completamente aplicable a los sistemas de control automatizados tradicionales. El caso es que la “toma de decisiones”, como mínimo, presupone una visión holística de un objeto en el entorno, no sólo en su estado actual, sino también en su dinámica, y en la interacción tanto entre sí como con el sistema de control, implica considerar varias opciones alternativas para el desarrollo de todo este sistema, así como reducir la diversidad (reducción) de estas alternativas en función de ciertos criterios objetivo. Evidentemente, nada de esto se encuentra en los sistemas de control automatizados tradicionales, o existe, pero de forma simplificada.

Por supuesto, el método tradicional es adecuado y su uso es bastante correcto y justificado en los casos en que el objeto de control es verdaderamente un sistema estable y estrictamente determinado, y se puede despreciar la influencia del medio ambiente sobre él.

Sin embargo, en otros casos este método resulta ineficaz.

Si el objeto de control es dinámico, entonces los modelos subyacentes a los algoritmos de control rápidamente se vuelven inadecuados, ya que cambian las relaciones entre los parámetros de entrada y salida, así como el conjunto de parámetros esenciales. En esencia, esto significa que los sistemas de control automatizados tradicionales son capaces de controlar el estado del objeto de control sólo cerca del punto de equilibrio mediante acciones de control débiles sobre él, es decir por el método de pequeñas perturbaciones. Lejos del estado de equilibrio, desde el punto de vista tradicional, el comportamiento del objeto de control parece impredecible e incontrolable.

Si no existe una conexión inequívoca entre los parámetros de entrada y salida del objeto de control (es decir, entre los parámetros de entrada y el estado del objeto), en otras palabras, si esta conexión tiene un carácter probabilístico pronunciado, entonces se utilizan modelos deterministas en los que es Se supone que el resultado de medir un determinado parámetro es simplemente un número y no son aplicables inicialmente. Además, es posible que simplemente se desconozca el tipo de esta conexión, y entonces es necesario partir de la suposición más general: que es probabilística o que no está definida en absoluto.

Un sistema de control automatizado construido sobre principios tradicionales sólo puede funcionar sobre la base de parámetros cuyos patrones de conexión ya se conocen, se estudian y se reflejan en un modelo matemático. En este estudio, la tarea es desarrollar métodos de diseño automatizados. sistemas de control que permitirán crear sistemas capaces de identificar los parámetros más significativos y determinar la naturaleza de las conexiones entre ellos y los estados del objeto de control.

En este caso, es necesario utilizar métodos de medición más desarrollados y adecuados a la situación real:

• clasificación o reconocimiento de imágenes (aprendizaje basado en un conjunto de entrenamiento, adaptabilidad de los algoritmos de reconocimiento, adaptabilidad de conjuntos de clases y parámetros en estudio, selección de los parámetros más significativos y reducción de la dimensión de descripción manteniendo una determinada redundancia, etc.);
• mediciones estadísticas, cuando el resultado de medir un determinado parámetro no es un número separado, sino una distribución de probabilidad: un cambio en una variable estadística no significa un cambio en su valor en sí mismo, sino un cambio en las características de la distribución de probabilidad de sus valores.

Como resultado, los sistemas de control automatizados basados ​​en el enfoque determinista tradicional prácticamente no funcionan con objetos de control complejos, dinámicos, multiparamétricos y débilmente determinados, como, por ejemplo, sistemas macro y microsocioeconómicos en una economía dinámica del " período de transición”, élites jerárquicas y grupos étnicos, sociedad y electorado, fisiología y psique humana, ecosistemas naturales y artificiales y muchos otros.

Es muy significativo que a mediados de los años 80, la escuela de I. Prigogine desarrolló un enfoque según el cual el desarrollo de cualquier sistema (incluido el humano) alterna períodos durante los cuales el sistema se comporta como "principalmente determinista" o como "principalmente aleatorio". Naturalmente, un sistema de control real debe controlar de manera estable el objeto de control no sólo en las secciones "deterministas" de su historia, sino también en los puntos en los que su comportamiento posterior se vuelve altamente incierto. Esto por sí solo significa que es necesario desarrollar enfoques para controlar sistemas cuyo comportamiento contenga un gran elemento de aleatoriedad (o lo que actualmente se describe matemáticamente como “aleatoriedad”).

Por lo tanto, los sistemas de control automatizados prometedores que proporcionan control de sistemas complejos dinámicos multiparamétricos débilmente deterministas aparentemente incluirán subsistemas para identificar y predecir los estados del medio ambiente y el objeto de control, basados ​​en métodos de inteligencia artificial (principalmente reconocimiento de patrones), métodos de apoyo a la toma de decisiones. Creación y teoría de la información.

Consideremos brevemente el tema del uso de sistemas de reconocimiento de imágenes para tomar decisiones sobre acciones de control (este tema se discutirá con más detalle más adelante, ya que es clave para este trabajo). Si tomamos el objetivo y otros estados del objeto de control como clases de reconocimiento, y los factores que influyen en él como características, entonces se puede formar una medida de la relación entre factores y estados en el modelo de reconocimiento de patrones. Esto permite, para un determinado estado de un objeto de control, obtener información sobre los factores que promueven o dificultan su transición a este estado y, en base a esto, desarrollar una decisión sobre la acción de control.

Los factores se pueden dividir en los siguientes grupos:

• caracterizar el fondo del objeto de control;
• caracterizar el estado actual del objeto de control;
• factores ambientales;
• factores tecnológicos (controlables).

Por tanto, los sistemas de reconocimiento de patrones se pueden utilizar como parte de sistemas de control automatizados: en subsistemas para identificar el estado de un objeto de control y desarrollar acciones de control.

Esto es apropiado cuando el objeto de control es un sistema complejo.

Tomar una decisión sobre la acción de control en el sistema de control automatizado.

En este trabajo se considera la solución al problema de sintetizar sistemas de control automatizados adaptativos mediante sistemas complejos, teniendo en cuenta numerosas y profundas analogías entre los métodos de reconocimiento de patrones y toma de decisiones.

Por un lado, el problema del reconocimiento de patrones es tomar una decisión sobre si el objeto reconocido pertenece a una determinada clase de reconocimiento.

Por otro lado, los autores proponen considerar el problema de toma de decisiones como un problema de decodificación inversa o un problema de reconocimiento de patrones inverso (ver sección 2.2.2).

La similitud de las ideas básicas que subyacen a los métodos de reconocimiento de patrones y toma de decisiones se vuelve especialmente obvia cuando se las considera desde la perspectiva de la teoría de la información.

Variedad de problemas de toma de decisiones.

La toma de decisiones como realización de objetivos.

Definición: la toma de decisiones (“elección”) es una acción sobre un conjunto de alternativas, como resultado de lo cual el conjunto inicial de alternativas se reduce, es decir, se produce su reducción.

La elección es la acción que da propósito a todas las actividades. Es a través de actos de elección que se realiza la subordinación de todas las actividades a un objetivo específico o a un conjunto de objetivos interrelacionados.

Así, para que el acto de elección sea posible es necesario lo siguiente:

• generación o descubrimiento de un conjunto de alternativas sobre las cuales se debe hacer una elección;
• determinación de los objetivos por los cuales se hace la elección;
• desarrollo y aplicación de un método para comparar alternativas entre sí, es decir Determinar una calificación de preferencia para cada alternativa de acuerdo con ciertos criterios que permitan evaluar indirectamente qué tan bien corresponde cada alternativa al objetivo.

El trabajo moderno en el campo del apoyo a la toma de decisiones ha revelado una situación característica: la formalización completa para encontrar la mejor (en cierto sentido) solución sólo es posible para problemas bien estudiados y relativamente simples, mientras que en la práctica los problemas débilmente estructurados son posibles. Se encuentran con mayor frecuencia, para los cuales no se han desarrollado algoritmos completamente formalizados (excepto búsqueda exhaustiva y prueba y error). Sin embargo, los profesionales experimentados, competentes y capaces a menudo toman decisiones que resultan bastante buenas. Por lo tanto, la tendencia moderna en la práctica de la toma de decisiones en situaciones naturales es combinar la capacidad humana para resolver problemas informales con las capacidades de los métodos formales y el modelado por computadora: sistemas interactivos de soporte a decisiones, sistemas expertos, sistemas de control automatizados adaptativos hombre-máquina. , redes neuronales y sistemas cognitivos.

Toma de decisiones como eliminación de la incertidumbre (enfoque informativo)

El proceso de obtención de información puede considerarse como una reducción de la incertidumbre como resultado de recibir una señal, y la cantidad de información puede considerarse como una medida cuantitativa del grado de eliminación de la incertidumbre.

Pero como resultado de elegir un cierto subconjunto de alternativas del conjunto, es decir como resultado de la toma de decisiones sucede lo mismo (reducir la incertidumbre). Esto significa que cada elección, cada decisión genera una cierta cantidad de información y, por lo tanto, puede describirse en términos de teoría de la información.

Clasificación de los problemas de toma de decisiones.

La multiplicidad de tareas de toma de decisiones se debe al hecho de que cada componente de la situación en la que se toman las decisiones puede implementarse en opciones cualitativamente diferentes.

Enumeremos solo algunas de estas opciones:

• el conjunto de alternativas, por un lado, puede ser finito, contable o continuo, y por otro, cerrado (es decir, completamente conocido) o abierto (incluidos elementos desconocidos);
• la evaluación de alternativas puede realizarse según uno o más criterios, que, a su vez, pueden ser de carácter cuantitativo o cualitativo;
• El modo de selección puede ser único (único) o múltiple, repetitivo, incluida la retroalimentación sobre los resultados de la elección, es decir. permitir entrenar algoritmos de toma de decisiones teniendo en cuenta las consecuencias de elecciones anteriores;
• Las consecuencias de elegir cada alternativa pueden ser conocidas con precisión de antemano (elección en condiciones de certeza), tener un carácter probabilístico cuando se conocen las probabilidades de los posibles resultados después de la elección realizada (elección en condiciones de riesgo) o tener un resultado ambiguo sin conocerse. probabilidades (elección en condiciones de incertidumbre);
• la responsabilidad de elección puede estar ausente, ya sea individual o grupal;
• El grado de coherencia de los objetivos en la elección grupal puede variar desde la completa coincidencia de los intereses de las partes (elección cooperativa) hasta su opuesto (elección en una situación de conflicto). También son posibles opciones intermedias: compromiso, coalición, conflicto creciente o disipado.

Varias combinaciones de estas opciones conducen a numerosos problemas de toma de decisiones que se han estudiado en diversos grados.

Lenguajes para describir métodos de toma de decisiones.

Se puede hablar de un mismo fenómeno en diferentes idiomas con distintos grados de generalidad y adecuación. Hasta la fecha, han surgido tres lenguajes principales para describir la elección.

El más simple, más desarrollado y más popular es el lenguaje de criterios.

Idioma de los criterios

El nombre de este lenguaje está asociado con el supuesto básico de que cada alternativa individual puede evaluarse mediante algún (un) número específico, después de lo cual la comparación de alternativas se reduce a una comparación de los números correspondientes.

Sea, por ejemplo, (X) un conjunto de alternativas y x alguna alternativa específica perteneciente a este conjunto: x∈X. Entonces se cree que para todo x se puede especificar una función q(x), que se denomina criterio (criterio de calidad, función objetivo, función de preferencia, función de utilidad, etc.), que tiene la propiedad de que si la alternativa x 1 es preferible a x 2 (denotado: x 1 > x 2), entonces q(x 1) > q(x 2).

En este caso, la elección se reduce a encontrar una alternativa con valor más alto función de criterio.

Sin embargo, en la práctica, utilizar un solo criterio para comparar el grado de preferencia de las alternativas resulta una simplificación injustificada, ya que más consideración detallada alternativas conduce a la necesidad de evaluarlas no por uno, sino por muchos criterios que pueden tener diferente naturaleza y cualitativamente diferentes entre sí.

Por ejemplo, al elegir el tipo de aeronave más aceptable para los pasajeros y la organización operadora ciertos tipos Las rutas se comparan simultáneamente según muchos grupos de criterios: técnicos, tecnológicos, económicos, sociales, ergonómicos, etc.

Los problemas multicriterio no tienen una solución general única. Por lo tanto, se proponen muchas formas de plantear un problema multicriterio. vista privada, permitiendo sólo uno decisión común. Naturalmente, estas soluciones son generalmente diferentes para diferentes métodos. Por tanto, quizás lo más importante a la hora de resolver un problema multicriterio sea la justificación de este tipo de formulación.

Se utilizan varias opciones para simplificar el problema de selección multicriterio. Enumeremos algunos de ellos.

1. Maximización condicional (no se encuentra el extremo global del criterio integral, sino extremo local criterio principal).
2. Busque una alternativa con propiedades específicas.
3. Encontrar el conjunto de Pareto.
4. Reducir un problema multicriterio a un problema de un solo criterio introduciendo un criterio integral.

Consideremos con más detalle la formulación formal del método para reducir un problema multicriterio a uno de un solo criterio.

vamos a presentar criterio integral q 0 (x), como función escalar del argumento vectorial:

q 0 (x) = q 0 ((q 1 (x), q 2 (x), ..., q n (x)).

El criterio integral le permite ordenar alternativas según el valor de q 0, resaltando así la mejor (en el sentido de este criterio). La forma de la función q 0 está determinada por qué tan específicamente imaginamos la contribución de cada criterio al criterio integral. Normalmente se utilizan funciones aditivas y multiplicativas:

q 0 = ∑a yo ⋅q yo /s yo

1 - q 0 = ∏(1 - segundo yo ⋅q yo /s yo)

Coeficientes que proporciono:

1. Adimensionalidad o dimensión única del número a i ⋅q i /s i (varios criterios particulares pueden tener diferentes tamaños, y entonces es imposible realizar operaciones aritméticas con ellos y reducirlos a un criterio integral).
2. Normalización, es decir asegurando la condición: b i ⋅q i /s i<1.

Los coeficientes a i y b i reflejan la contribución relativa de los criterios parciales q i al criterio integral.

Entonces, en una formulación multicriterio, el problema de tomar una decisión sobre la elección de una de las alternativas se reduce a maximizar el criterio integral:

x * = arg max(q 0 (q 1 (x), q 2 (x), ..., q n (x)))

El principal problema en la formulación multicriterio del problema de toma de decisiones es que es necesario encontrar una forma analítica de los coeficientes a i y b i que proporcione las siguientes propiedades del modelo:

• un alto grado de adecuación al área temática y al punto de vista de los expertos;
• dificultades computacionales mínimas para maximizar el criterio integral, es decir, su cálculo para diferentes alternativas;
• estabilidad de los resultados de maximizar el criterio integral a partir de pequeñas perturbaciones de los datos iniciales.
• La estabilidad de la solución significa que un pequeño cambio en los datos iniciales debería conducir a un pequeño cambio en el valor del criterio integral y, en consecuencia, a un pequeño cambio en la decisión tomada. Así, si los datos iniciales son prácticamente los mismos, entonces la decisión debe tomarse igual o muy cercana.

Lenguaje de elección binaria secuencial

El lenguaje de las relaciones binarias es una generalización del lenguaje multicriterio y se basa en tener en cuenta el hecho de que cuando evaluamos una alternativa, esta evaluación es siempre relativa, es decir De manera explícita o más a menudo implícita, otras alternativas del conjunto bajo estudio o de la población general se utilizan como base o marco de referencia para la comparación. El pensamiento humano se basa en la búsqueda y análisis de opuestos (constructos), por lo que siempre nos resulta más fácil elegir una de dos opciones opuestas que una opción de un conjunto grande y de ninguna manera ordenado.

Así, los supuestos básicos de este lenguaje son los siguientes:

• no se evalúa una alternativa separada, es decir no se introduce la función de criterio;
• para cada par de alternativas se puede establecer de alguna manera que una de ellas es preferible a la otra o que son equivalentes o incomparables;
• la relación de preferencia en cualquier par de alternativas no depende de las alternativas restantes presentadas para elección.

Hay varias formas de especificar relaciones binarias: directa, matricial, usando gráficos de preferencias, el método de la sección, etc.

Las relaciones entre alternativas de un par se expresan mediante los conceptos de equivalencia, orden y dominancia.

Lenguaje de función de selección generalizada.

El lenguaje de la función de elección se basa en la teoría de conjuntos y le permite operar con asignaciones de conjuntos a sus subconjuntos correspondientes a diferentes opciones sin tener que enumerar los elementos. Este lenguaje es muy general y tiene el potencial de describir cualquier elección. Sin embargo, el aparato matemático de funciones de selección generalizadas todavía se está desarrollando y probando principalmente en problemas que ya se han resuelto mediante enfoques binarios o basados ​​en criterios.

Selección de grupo

Que haya un grupo de personas que tengan derecho a participar en la toma de decisiones colectiva. Supongamos que este grupo está considerando un determinado conjunto de alternativas y que cada miembro del grupo hace su propia elección. La tarea consiste en desarrollar una solución que en cierto modo coordine las elecciones individuales y en cierto sentido exprese la “opinión general” del grupo, es decir, aceptado como una elección grupal.

Naturalmente, diferentes principios para coordinar decisiones individuales corresponderán a diferentes decisiones grupales.

Las reglas para coordinar las decisiones individuales durante la elección grupal se denominan reglas de votación. La más común es la “regla de la mayoría”, en la que se acepta como decisión del grupo la alternativa con más votos.

Es necesario comprender que tal decisión refleja sólo la prevalencia de diferentes puntos de vista en el grupo, y no la opción verdaderamente óptima, por la que nadie puede votar en absoluto. "La verdad no se determina mediante la votación".

Además, existen las llamadas “paradojas del voto”, la más famosa de las cuales es la paradoja de Arrow.

Estas paradojas pueden conducir, y a veces conducen, a características muy desagradables del procedimiento de votación: por ejemplo, hay casos en los que el grupo no puede tomar ninguna decisión (no hay quórum o cada uno vota por su propia opción única, etc. .), y a veces (con votación en varias etapas), la minoría puede imponer su voluntad a la mayoría.

Elección en condiciones de incertidumbre

La certeza es un caso especial de incertidumbre, a saber: es una incertidumbre cercana a cero.

En la teoría de la elección moderna, se cree que existen tres tipos principales de incertidumbre en los problemas de toma de decisiones:

1. Incertidumbre informativa (estadística) de los datos iniciales para la toma de decisiones.
2. Incertidumbre de las consecuencias de la toma de decisiones (elección).
3. Vaguedad en la descripción de los componentes del proceso de toma de decisiones.

Veámoslos en orden.

Incertidumbre de la información (estadística) en los datos fuente.

Los datos obtenidos sobre el tema no pueden considerarse absolutamente exactos. Además, evidentemente, estos datos no nos interesan en sí mismos, sino sólo como señales que pueden llevar cierta información sobre lo que realmente nos interesa. Por tanto, es más realista considerar que estamos ante datos que no sólo son ruidosos e inexactos, sino también indirectos y quizás incompletos. Además, estos datos no se refieren a toda la población objeto de estudio, sino sólo a un subconjunto determinado de ella, sobre el cual pudimos recopilar datos, pero al mismo tiempo queremos sacar conclusiones sobre toda la población, y también Quiero saber el grado de fiabilidad de estas conclusiones.

En estas condiciones, se utiliza la teoría de las decisiones estadísticas.

Hay dos fuentes principales de incertidumbre en esta teoría. En primer lugar, no se sabe qué distribución siguen los datos originales. En segundo lugar, se desconoce qué distribución tiene el conjunto (población general) sobre el cual queremos sacar conclusiones a partir de su subconjunto que forma los datos iniciales.

Los procedimientos estadísticos son procedimientos de toma de decisiones que eliminan ambos tipos de incertidumbre.

Cabe señalar que existen varias razones que conducen a una aplicación incorrecta de métodos estadísticos:

• Las conclusiones estadísticas, como cualquier otra, siempre tienen cierta fiabilidad o validez. Pero, a diferencia de muchos otros casos, la fiabilidad de las conclusiones estadísticas se conoce y se determina durante el estudio estadístico;
• la calidad de la solución obtenida como resultado de la aplicación de un procedimiento estadístico depende de la calidad de los datos originales;
• los datos que no tengan carácter estadístico no deberían estar sujetos a procesamiento estadístico;
• Se deben utilizar procedimientos estadísticos que sean apropiados al nivel de información a priori sobre la población que se está estudiando (por ejemplo, los métodos ANOVA no deben aplicarse a datos no gaussianos). Si se desconoce la distribución de los datos iniciales, entonces es necesario establecerla o utilizar varios métodos diferentes y comparar los resultados. Si son muy diferentes, esto indica la inaplicabilidad de algunos de los procedimientos utilizados.

Incertidumbre de las consecuencias

Cuando las consecuencias de elegir una u otra alternativa están determinadas inequívocamente por la alternativa misma, entonces no podemos distinguir entre la alternativa y sus consecuencias, dando por sentado que al elegir una alternativa, en realidad estamos eligiendo sus consecuencias.

Sin embargo, en la práctica real a menudo uno tiene que lidiar con una situación más compleja, cuando la elección de una u otra alternativa determina de manera ambigua las consecuencias de la elección realizada.

En el caso de un conjunto discreto de alternativas y los resultados de su elección, siempre que el conjunto de resultados posibles sea común a todas las alternativas, podemos suponer que las diferentes alternativas difieren entre sí en la distribución de probabilidad de los resultados. Estas distribuciones de probabilidad en el caso general pueden depender de los resultados de la elección de alternativas y de los resultados reales que resultaron. En el caso más simple, los resultados son igualmente probables. Los resultados en sí mismos suelen tener el significado de ganancias o pérdidas y se expresan cuantitativamente.

Si los resultados son iguales para todas las alternativas, entonces no hay nada que elegir. Si son diferentes, entonces se pueden comparar alternativas introduciendo ciertas estimaciones cuantitativas para ellas. La variedad de problemas en la teoría de juegos está asociada con diferentes elecciones de características numéricas de pérdidas y ganancias como resultado de la elección de alternativas, diferentes grados de conflicto entre las partes que eligen alternativas, etc.

Considere este tipo de incertidumbre como incertidumbre vaga.

Cualquier tarea de elección es una tarea de reducción selectiva de un conjunto de alternativas. Tanto la descripción formal de las alternativas (su lista misma, la lista de sus características o parámetros) como la descripción de las reglas para su comparación (criterios, relaciones) siempre se dan en términos de una u otra escala de medición (incluso cuando quien ¿Esto no sabe sobre esto)?

Se sabe que todas las escalas están borrosas, pero en distintos grados. El término “difuminación” se refiere a la propiedad de las escalas, que consiste en que siempre es posible presentar dos alternativas que sean distinguibles, es decir diferentes en la misma escala e indistinguibles, es decir, idéntico, en el otro, más borroso. Cuantas menos gradaciones haya en una determinada escala, más borrosa será.

Así, podemos ver claramente las alternativas y al mismo tiempo clasificarlas vagamente, es decir, tienen incertidumbre sobre a qué clases pertenecen.

Ya en su primer trabajo sobre la toma de decisiones en situaciones vagas, Bellman y Zadeh propusieron la idea de que tanto los objetivos como las restricciones deberían representarse como conjuntos difusos en el conjunto de alternativas.

Acerca de algunas limitaciones del enfoque de optimización

En todos los problemas de selección y métodos de toma de decisiones discutidos anteriormente, el problema era encontrar los mejores en el conjunto original bajo condiciones dadas, es decir. alternativas que son óptimas en cierto sentido.

La idea de optimización es la idea central de la cibernética y se ha establecido firmemente en la práctica del diseño y operación de sistemas técnicos. Al mismo tiempo, esta idea requiere un manejo cuidadoso cuando intentamos trasladarla al campo de la gestión de sistemas complejos, grandes y débilmente determinados, como, por ejemplo, los sistemas socioeconómicos.

Hay muy buenas razones para esta conclusión. Veamos algunos de ellos:

1. La solución óptima a menudo resulta ser inestable, es decir cambios menores en las condiciones, insumos o restricciones del problema pueden conducir a la selección de alternativas significativamente diferentes.
2. Los modelos de optimización se desarrollan sólo para clases estrechas de problemas bastante simples, que no siempre reflejan adecuada y sistemáticamente objetos de control reales. Muy a menudo, los métodos de optimización permiten optimizar sólo subsistemas bastante simples y bien descritos formalmente de algunos sistemas grandes y complejos, es decir, permitir sólo la optimización local. Sin embargo, si cada subsistema de un sistema grande funciona de manera óptima, esto no significa en absoluto que el sistema en su conjunto funcionará de manera óptima. Por lo tanto, la optimización de un subsistema no conduce necesariamente al comportamiento que se le exige al optimizar el sistema en su conjunto. Además, a veces la optimización local puede tener consecuencias negativas para el sistema en su conjunto. Por lo tanto, al optimizar los subsistemas y el sistema en su conjunto, es necesario determinar un árbol de metas y submetas y su prioridad.
3. A menudo, maximizar un criterio de optimización según algún modelo matemático se considera el objetivo de la optimización, pero en realidad el objetivo es optimizar el objeto de control. Los criterios de optimización y los modelos matemáticos siempre están relacionados con el objetivo sólo indirectamente, es decir, más o menos adecuadamente, pero siempre aproximadamente.

Por tanto, la idea de optimidad, que es extremadamente fructífera para sistemas que pueden formalizarse matemáticamente adecuadamente, debe transferirse con precaución a sistemas complejos. Por supuesto, los modelos matemáticos que a veces pueden proponerse para tales sistemas pueden optimizarse. Sin embargo, siempre se debe tener en cuenta la fuerte simplificación de estos modelos, que en el caso de sistemas complejos ya no se puede descuidar, así como el hecho de que el grado de adecuación de estos modelos en el caso de sistemas complejos es prácticamente desconocido. . Por lo tanto, no se sabe qué significado puramente práctico tiene esta optimización. La gran practicidad de la optimización en sistemas técnicos no debería dar lugar a la ilusión de que será igualmente eficaz en la optimización de sistemas complejos. La modelización matemática significativa de sistemas complejos es muy difícil, aproximada e inexacta. Cuanto más complejo sea el sistema, más cuidado se debe tener con la idea de optimizarlo.

Por lo tanto, al desarrollar métodos para controlar sistemas complejos, grandes y débilmente deterministas, los autores consideran lo principal no solo la optimización del enfoque elegido desde un punto de vista matemático formal, sino también su adecuación al objetivo y la naturaleza misma del objeto de control.

Métodos de selección de expertos.

Al estudiar sistemas complejos, a menudo surgen problemas que, por diversas razones, no pueden formularse y resolverse estrictamente utilizando los aparatos matemáticos desarrollados actualmente. En estos casos se utilizan los servicios de expertos (analistas de sistemas), cuya experiencia e intuición ayudan a reducir la complejidad del problema.

Sin embargo, hay que tener en cuenta que los propios expertos son sistemas muy complejos y sus actividades también dependen de muchas condiciones externas e internas. Por lo tanto, en los métodos de organización de las evaluaciones de expertos, se presta mucha atención a la creación de condiciones externas y psicológicas favorables para el trabajo de los expertos.

El trabajo del experto está influenciado por los siguientes factores:

• responsabilidad por el uso de los resultados de los exámenes;
• conocimiento de que también participan otros expertos;
• disponibilidad de contacto de información entre expertos;
• relaciones interpersonales de expertos (si existe contacto informativo entre ellos);
• el interés personal del experto en los resultados de la evaluación;
• Cualidades personales de los expertos (presunción, conformismo, voluntad, etc.).

La interacción entre expertos puede tanto estimular como suprimir sus actividades. Por tanto, en diferentes casos se utilizan diversos métodos de examen, que se diferencian en la naturaleza de la interacción de los expertos entre sí: encuestas y cuestionarios anónimos y abiertos, reuniones, debates, juegos de negocios, lluvia de ideas, etc.

Existen varios métodos para el procesamiento matemático de opiniones de expertos. Se pide a los expertos que evalúen varias alternativas utilizando uno o un sistema de indicadores. Además, se les pide que evalúen el grado de importancia de cada indicador (su “peso” o “contribución”). A los propios expertos también se les asigna un nivel de competencia correspondiente a la contribución de cada uno de ellos a la opinión resultante del grupo.

Una metodología desarrollada para trabajar con expertos es el método Delphi. La idea principal de este método es que la crítica y la argumentación tienen un efecto beneficioso sobre el experto si no se ve afectado su orgullo y se brindan condiciones que excluyen la confrontación personal.

Debe enfatizarse especialmente que existe una diferencia fundamental en la naturaleza del uso de métodos expertos en sistemas expertos y en el apoyo a las decisiones. Si en el primer caso se requiere que los expertos formalicen los métodos de toma de decisiones, en el segundo, solo la decisión en sí, como tal.

Dado que los expertos participan en la implementación de precisamente aquellas funciones que actualmente no son proporcionadas por los sistemas automatizados o que los realizan peor que los humanos, una dirección prometedora para el desarrollo de sistemas automatizados es la máxima automatización de estas funciones.

Sistemas automatizados de soporte a la decisión.

El hombre siempre ha utilizado asistentes a la hora de tomar decisiones: estos eran simplemente proveedores de información sobre el objeto de gestión y consultores (asesores) que ofrecían opciones de decisión y analizaban sus consecuencias. Una persona que toma decisiones siempre las ha tomado en un determinado entorno de información: para un líder militar es el cuartel general, para el rector es el consejo académico, para el ministro es el colegio.

Hoy en día, la infraestructura de información para la toma de decisiones es impensable sin sistemas automatizados para la evaluación interactiva de decisiones y, especialmente, sistemas de soporte a la decisión (DDS - Decision Support Systems), es decir. Sistemas automatizados que están diseñados específicamente para preparar la información que una persona necesita para tomar una decisión. El desarrollo de sistemas de apoyo a la toma de decisiones se lleva a cabo, en particular, en el marco de un proyecto internacional llevado a cabo bajo los auspicios del Instituto Internacional de Análisis de Sistemas Aplicados de Laxenburg (Austria).

Tomar decisiones en situaciones de la vida real requiere una serie de operaciones, algunas de las cuales son realizadas de manera más eficiente por humanos y otras por máquinas. La combinación eficaz de sus ventajas y, al mismo tiempo, la compensación de sus deficiencias se materializa en los sistemas automatizados de apoyo a la toma de decisiones.

Una persona toma decisiones mejor que una máquina en condiciones de incertidumbre, pero para tomar la decisión correcta también necesita información adecuada (completa y confiable) que caracterice el área temática. Sin embargo, se sabe que los humanos no afrontamos bien grandes cantidades de información “en bruto” y sin procesar. Por lo tanto, el papel de una máquina en el apoyo a las decisiones puede ser llevar a cabo una preparación preliminar de información sobre el objeto de control y los factores incontrolables (entorno), para ayudar a ver las consecuencias de tomar ciertas decisiones y también presentar toda esta información de forma visual. y forma cómoda para la toma de decisiones.

Por lo tanto, los sistemas automatizados de apoyo a las decisiones compensan las debilidades de una persona, liberándola del procesamiento rutinario de información preliminar y brindándole un entorno de información cómodo en el que puede demostrar mejor sus fortalezas. Estos sistemas no tienen como objetivo automatizar las funciones de quien toma las decisiones (y, como resultado, alienarle estas funciones y, por lo tanto, la responsabilidad de las decisiones tomadas, lo que a menudo es generalmente inaceptable), sino brindarle asistencia para encontrar una buena solución. solución.