Dom, 29 de março de 2015

Atualmente, existem muitas tarefas nas quais é necessário tomar alguma decisão dependendo da presença de um objeto na imagem ou classificá-lo. A capacidade de "reconhecer" é considerada a principal propriedade dos seres biológicos, enquanto os sistemas computacionais não possuem totalmente essa propriedade.

Considere os elementos gerais do modelo de classificação.

Aula- um conjunto de objetos que possuem propriedades comuns. Para objetos da mesma classe, a presença de "semelhança" é assumida. Para a tarefa de reconhecimento, um número arbitrário de classes pode ser definido, mais de 1. O número de classes é denotado pelo número S. Cada classe tem seu próprio rótulo de classe de identificação.

Classificação- o processo de atribuição de rótulos de classe a objetos, de acordo com alguma descrição das propriedades desses objetos. Um classificador é um dispositivo que recebe um conjunto de características de um objeto como entrada e retorna um rótulo de classe como resultado.

Verificação- o processo de combinar uma instância de objeto com um único modelo de objeto ou descrição de classe.

Debaixo maneira entenderemos o nome da área no espaço de atributos, em que muitos objetos ou fenômenos do mundo material são exibidos. sinal- uma descrição quantitativa de uma propriedade particular do objeto ou fenômeno em estudo.

espaço de recurso este é um espaço N-dimensional definido para uma determinada tarefa de reconhecimento, onde N é um número fixo de características medidas para quaisquer objetos. O vetor do espaço de características x correspondente ao objeto do problema de reconhecimento é um vetor N-dimensional com componentes (x_1,x_2,…,x_N), que são os valores das características para o objeto dado.

Em outras palavras, o reconhecimento de padrões pode ser definido como a atribuição de dados iniciais a uma determinada classe, extraindo características ou propriedades essenciais que caracterizam esses dados da massa geral de detalhes irrelevantes.

Exemplos de problemas de classificação são:

• reconhecimento de caracteres;
• reconhecimento de fala;
• estabelecimento de diagnóstico médico;
• previsão do tempo;
• reconhecimento facial
• classificação de documentos, etc.

Na maioria das vezes, o material de origem é a imagem recebida da câmera. A tarefa pode ser formulada como a obtenção de vetores de características para cada classe na imagem considerada. O processo pode ser visto como um processo de codificação, que consiste em atribuir um valor a cada característica do espaço de características para cada classe.

Se considerarmos 2 classes de objetos: adultos e crianças. Como recursos, você pode escolher altura e peso. Como segue da figura, essas duas classes formam dois conjuntos sem interseção, o que pode ser explicado pelas características escolhidas. No entanto, nem sempre é possível escolher os parâmetros medidos corretos como características das classes. Por exemplo, os parâmetros selecionados não são adequados para criar classes não sobrepostas de jogadores de futebol e basquete.

A segunda tarefa de reconhecimento é a seleção de características ou propriedades das imagens originais. Esta tarefa pode ser atribuída ao pré-processamento. Se considerarmos a tarefa de reconhecimento de fala, podemos distinguir características como vogais e consoantes. O atributo deve ser uma propriedade característica de uma determinada classe, embora seja comum a essa classe. Sinais que caracterizam as diferenças entre - sinais interclasses. Características comuns a todas as classes não carregam informações úteis e não são consideradas como características no problema de reconhecimento. A escolha das características é uma das tarefas importantes associadas à construção de um sistema de reconhecimento.

Depois que as características são determinadas, é necessário determinar o procedimento de decisão ideal para classificação. Considere um sistema de reconhecimento de padrões projetado para reconhecer várias classes M, denotadas como m_1,m_2,…,m 3. Então podemos supor que o espaço da imagem consiste em M regiões, cada uma contendo pontos correspondentes a uma imagem de uma classe. Então o problema de reconhecimento pode ser considerado como a construção de limites separando M classes com base nos vetores de medição aceitos.

A solução do problema de pré-processamento de imagem, extração de características e o problema de obtenção da solução ótima e classificação geralmente está associada à necessidade de avaliar uma série de parâmetros. Isso leva ao problema de estimação de parâmetros. Além disso, é óbvio que a extração de recursos pode usar informações adicionais com base na natureza das classes.

A comparação de objetos pode ser feita com base em sua representação na forma de vetores de medição. É conveniente representar os dados de medição como números reais. Então a similaridade dos vetores de características de dois objetos pode ser descrita usando a distância euclidiana.

onde d é a dimensão do vetor de característica.

Existem 3 grupos de métodos de reconhecimento de padrões:

• Comparação de amostra. Este grupo inclui classificação por média mais próxima, classificação por distância ao vizinho mais próximo. Os métodos de reconhecimento estrutural também podem ser incluídos no grupo de comparação de amostras.
• Métodos estatísticos. Como o nome indica, os métodos estatísticos usam algumas informações estatísticas ao resolver um problema de reconhecimento. O método determina a pertença de um objeto a uma determinada classe com base na probabilidade. Em alguns casos, isso se resume a determinar a probabilidade a posteriori de um objeto pertencer a uma determinada classe, desde que as características desse objeto tenham tomado as devidas proporções valores. Um exemplo é o método de regra de decisão Bayesiana.
• Redes neurais. Uma classe separada de métodos de reconhecimento. Uma característica distintiva dos outros é a capacidade de aprender.

Classificação pela média mais próxima

Na abordagem clássica de reconhecimento de padrões, na qual um objeto desconhecido para classificação é representado como um vetor de características elementares. Um sistema de reconhecimento baseado em recursos pode ser desenvolvido de várias maneiras. Esses vetores podem ser conhecidos pelo sistema antecipadamente como resultado do treinamento ou previstos em tempo real com base em alguns modelos.

Um algoritmo de classificação simples consiste em agrupar dados de referência de classe usando o vetor de expectativa de classe (média).

onde x(i,j) é a j-ésima característica de referência da classe i, n_j é o número de vetores de referência da classe i.

Então o objeto desconhecido pertencerá à classe i se estiver muito mais próximo do vetor de expectativa da classe i do que dos vetores de expectativa de outras classes. Este método é adequado para problemas em que os pontos de cada classe estão localizados de forma compacta e distantes dos pontos de outras classes.

Dificuldades surgirão se as classes tiverem uma estrutura um pouco mais complexa, por exemplo, como na figura. Neste caso, a classe 2 é dividida em duas seções não sobrepostas, que são mal descritas por um único valor médio. Além disso, a classe 3 é muito alongada, amostras da 3ª classe com grandes valores de coordenadas x_2 estão mais próximas do valor médio da 1ª classe do que da 3ª classe.

O problema descrito em alguns casos pode ser resolvido alterando o cálculo da distância.

Levaremos em consideração a característica da "dispersão" de valores de classe - σ_i, ao longo de cada direção de coordenada i. O desvio padrão é igual à raiz quadrada da variância. A distância euclidiana em escala entre o vetor x e o vetor de expectativa x_c é

Essa fórmula de distância reduzirá o número de erros de classificação, mas, na realidade, a maioria dos problemas não pode ser representada por uma classe tão simples.

Classificação por distância ao vizinho mais próximo

Outra abordagem para classificação é atribuir um vetor de característica x desconhecido à classe à qual esse vetor está mais próximo de uma amostra separada. Essa regra é chamada de regra do vizinho mais próximo. A classificação do vizinho mais próximo pode ser mais eficiente mesmo quando as classes são complexas ou quando as classes se sobrepõem.

Esta abordagem não requer suposições sobre os modelos de distribuição de vetores de características no espaço. O algoritmo usa apenas informações sobre amostras de referência conhecidas. O método de solução é baseado em calcular a distância x para cada amostra no banco de dados e encontrar a distância mínima. As vantagens desta abordagem são óbvias:

• a qualquer momento você pode adicionar novas amostras ao banco de dados;
• estruturas de dados em árvore e grade reduzem o número de distâncias calculadas.

Além disso, a solução será melhor se você procurar no banco de dados não um vizinho mais próximo, mas k. Então, para k > 1, fornece a melhor amostra da distribuição de vetores no espaço d-dimensional. No entanto, o uso eficiente dos valores de k depende se há o suficiente em cada região do espaço. Se houver mais de duas classes, é mais difícil tomar a decisão certa.

Literatura

• M. Castrillon, . O. Deniz, . D. Hernández e J. Lorenzo, “Uma comparação de detectores de rosto e características faciais com base na estrutura geral de detecção de objetos Viola-Jones”, International Journal of Computer Vision, nº 22, pp. 481-494, 2011.
• Y.-Q. Wang, "An Analysis of Viola-Jones Face Detection Algorithm", IPOL Journal, 2013.
• L. Shapiro e D. Stockman, visão computacional, Binom. Laboratório do Conhecimento, 2006.
• Z. N. G., Métodos de reconhecimento e sua aplicação, rádio soviética, 1972.
• J. Tu, R. Gonzalez, Princípios Matemáticos de Reconhecimento de Padrões, Moscou: “Mir” Moscou, 1974.
• Khan, H. Abdullah e M. Shamian Bin Zainal, "Algoritmo de detecção de olhos e boca eficiente usando combinação de viola jones e detecção de pixel de cor da pele" International Journal of Engineering and Applied Sciences, no. Vol. 3 no 4, 2013.
• V. Gaede e O. Gunther, "Multidimensional Access Methods", ACM Computing Surveys, pp. 170-231, 1998.

→

Capítulo 3: Revisão Analítica de Reconhecimento de Padrões e Métodos de Tomada de Decisão

Teoria de reconhecimento de padrões e automação de controle

As principais tarefas do reconhecimento adaptativo de padrões

O reconhecimento é um processo de informação implementado por algum conversor de informação (canal de informação inteligente, sistema de reconhecimento) que possui uma entrada e uma saída. A entrada do sistema são informações sobre quais características os objetos apresentados possuem. A saída do sistema exibe informações sobre quais classes (imagens generalizadas) os objetos reconhecíveis são atribuídos.

Ao criar e operar um sistema automatizado de reconhecimento de padrões, várias tarefas são resolvidas. Consideremos brevemente e simplesmente essas tarefas. Note-se que as formulações destas tarefas, e o próprio conjunto, não coincidem com autores diferentes, pois em certa medida depende do modelo matemático específico em que se baseia este ou aquele sistema de reconhecimento. Além disso, algumas tarefas em determinados modelos de reconhecimento não têm solução e, portanto, não são propostas.

A tarefa de formalizar a área temática

Na verdade, essa tarefa é uma tarefa de codificação. É compilada uma lista de classes generalizadas, que podem incluir implementações específicas de objetos, bem como uma lista de recursos que esses objetos, em princípio, podem ter.

A tarefa de formar uma amostra de treinamento

A amostra de treinamento é um banco de dados contendo descrições de implementações específicas de objetos na linguagem de recursos, complementada com informações sobre a pertença desses objetos a determinadas classes de reconhecimento.

A tarefa de treinar o sistema de reconhecimento

A amostra de treinamento é usada para formar imagens generalizadas de classes de reconhecimento com base na generalização de informações sobre quais características os objetos da amostra de treinamento possuem que pertencem a esta classe e outras classes.

O problema da redução da dimensão do espaço de recursos

Após treinar o sistema de reconhecimento (obtendo estatísticas sobre a distribuição de frequências de características por classe), torna-se possível determinar para cada característica seu valor para a resolução do problema de reconhecimento. Depois disso, os recursos menos valiosos podem ser removidos do sistema de recursos. Então o sistema de reconhecimento deve ser retreinado, pois como resultado da remoção de algumas feições, as estatísticas de distribuição das feições restantes por classe mudam. Este processo pode ser repetido, i.e. seja iterativo.

Tarefa de reconhecimento

Os objetos de uma amostra reconhecível são reconhecidos, os quais, em particular, podem consistir em um objeto. A amostra reconhecível é formada de forma semelhante à de treinamento, mas não contém informações sobre o pertencimento dos objetos às classes, pois é justamente isso que é determinado no processo de reconhecimento. O resultado do reconhecimento de cada objeto é uma distribuição ou uma lista de todas as classes de reconhecimento em ordem decrescente do grau de similaridade do objeto reconhecido com elas.

Tarefa de controle de qualidade de reconhecimento

Após o reconhecimento, sua adequação pode ser estabelecida. Para objetos da amostra de treinamento, isso pode ser feito imediatamente, pois para eles é simplesmente conhecido a quais classes pertencem. Para outros objetos, essas informações podem ser obtidas posteriormente. Em qualquer caso, a probabilidade de erro média real para todas as classes de reconhecimento pode ser determinada, bem como a probabilidade de erro ao atribuir um objeto reconhecido a uma determinada classe.

Os resultados do reconhecimento devem ser interpretados levando em consideração as informações disponíveis sobre a qualidade do reconhecimento.

Tarefa de adaptação

Se, como resultado do procedimento de controle de qualidade, for constatado que ele é insatisfatório, as descrições de objetos incorretamente reconhecidos podem ser copiadas da amostra reconhecível para a de treinamento, complementadas com informações de classificação adequadas e usadas para reformular a decisão. regras, ou seja, levado em conta. Além disso, se esses objetos não pertencem às classes de reconhecimento já existentes, o que pode ser o motivo de seu reconhecimento incorreto, essa lista pode ser expandida. Como resultado, o sistema de reconhecimento se adapta e passa a classificar adequadamente esses objetos.

Problema de reconhecimento inverso

A tarefa de reconhecimento é que para um determinado objeto, de acordo com suas características conhecidas, o sistema estabelece sua pertença a alguma classe previamente desconhecida. No problema de reconhecimento inverso, ao contrário, para uma determinada classe de reconhecimento, o sistema determina quais características são mais características de objetos dessa classe e quais não são (ou quais objetos da amostra de treinamento pertencem a essa classe).

Tarefas de cluster e análise construtiva

Clusters são grupos de objetos, classes ou características que dentro de cada cluster são tão semelhantes quanto possível, e entre diferentes clusters são tão diferentes quanto possível.

Um construto (no contexto considerado nesta seção) é um sistema de clusters opostos. Assim, em certo sentido, os construtos são o resultado de uma análise de cluster de clusters.

Na análise de agrupamento, o grau de similaridade e diferença dos objetos (classes, características) é medido quantitativamente, e essa informação é utilizada para classificação. O resultado da análise de cluster é a própria classificação dos objetos por clusters. Essa classificação pode ser representada na forma de redes semânticas.

A tarefa da análise cognitiva

Na análise cognitiva, as informações sobre a semelhança e diferença de classes ou características são de interesse do pesquisador em si, e não para usá-las para classificação, como na análise de agrupamento e construtiva.

Se duas classes de reconhecimento são caracterizadas pela mesma característica, isso contribui para a semelhança dessas duas classes. Se para uma das classes esse recurso não for característico, isso contribui para a diferença.

Se dois signos se correlacionam, então, em certo sentido, eles podem ser considerados como um signo, e se são anticorrelacionados, então como diferentes. Tendo em conta esta circunstância, a presença de diferentes características em diferentes classes contribui também para a sua semelhança e diferença.

Os resultados da análise cognitiva podem ser apresentados na forma de diagramas cognitivos.

Métodos de reconhecimento de padrões e suas características

Princípios de classificação de métodos de reconhecimento de padrões

O reconhecimento de padrões é a tarefa de construir e aplicar operações formais em representações numéricas ou simbólicas de objetos do mundo real ou ideal, cujos resultados da solução refletem as relações de equivalência entre esses objetos. As relações de equivalência expressam o pertencimento dos objetos avaliados a algumas classes, consideradas como unidades semânticas independentes.

Ao construir algoritmos de reconhecimento, as classes de equivalência podem ser definidas por um pesquisador que usa suas próprias ideias significativas ou usa informações adicionais externas sobre a semelhança e diferença de objetos no contexto do problema que está sendo resolvido. Então se fala em "reconhecimento com o professor". Caso contrário, ou seja quando um sistema automatizado resolve um problema de classificação sem envolver informações externas de treinamento, fala-se de classificação automática ou “reconhecimento não supervisionado”. A maioria dos algoritmos de reconhecimento de padrões requer um poder computacional muito significativo, que só pode ser fornecido por tecnologia de computador de alto desempenho.

Vários 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. Gonzalez, P. Winston, K. Fu, Ya. Z. Tsypkin e outros) dão uma tipologia diferente de métodos de reconhecimento de padrões. Alguns autores distinguem entre métodos paramétricos, não paramétricos e heurísticos, enquanto outros destacam grupos de métodos baseados em escolas históricas e tendências da área. Por exemplo, no trabalho, que fornece uma visão acadêmica dos métodos de reconhecimento, é usada a seguinte tipologia de métodos de reconhecimento de padrões:

• métodos baseados no princípio da separação;
• Métodos estatísticos;
• métodos construídos com base em "funções potenciais";
• métodos de cálculo de notas (votação);
• métodos baseados no cálculo proposicional, em particular no aparato da álgebra da lógica.

Esta classificação é baseada na diferença de métodos formais de reconhecimento de padrões e, portanto, a consideração da abordagem heurística de reconhecimento, que recebeu desenvolvimento completo e adequado em sistemas especialistas, é omitida. A abordagem heurística baseia-se no conhecimento e na intuição do pesquisador de difícil formalização. Ao mesmo tempo, o próprio pesquisador determina quais informações e como o sistema deve usar para alcançar o efeito de reconhecimento desejado.

Uma tipologia semelhante de métodos de reconhecimento com vários graus de detalhes é encontrada em muitos trabalhos sobre reconhecimento. Ao mesmo tempo, as tipologias conhecidas não levam em conta uma característica muito significativa, que reflete as especificidades da forma como o conhecimento sobre a área temática é representado por meio de qualquer algoritmo formal de reconhecimento de padrões.

D.A. Pospelov (1990) identifica duas formas principais de representar o conhecimento:

• intencional, na forma de um esquema de conexões entre atributos (features).
• extensional, com a ajuda de fatos específicos (objetos, exemplos).

A representação intencional captura os padrões e relacionamentos que explicam a estrutura dos dados. No que diz respeito às tarefas de diagnóstico, tal fixação consiste em determinar as operações sobre os atributos (features) dos objetos que levam ao resultado de diagnóstico requerido. As representações intencionais são implementadas por meio de operações sobre valores de atributos e não implicam operações sobre fatos de informação específicos (objetos).

Por sua vez, as representações extensionais do conhecimento estão associadas à descrição e fixação de objetos específicos da área temática e são implementadas em operações, cujos elementos são objetos como sistemas integrais.

É possível traçar uma analogia entre as representações intensional e extensional do conhecimento e os mecanismos subjacentes à atividade dos hemisférios esquerdo e direito do cérebro humano. Se o hemisfério direito é caracterizado por uma representação prototípica holística do mundo circundante, então o hemisfério esquerdo opera com padrões que refletem as conexões dos atributos deste mundo.

As duas formas fundamentais de representação do conhecimento descritas acima nos permitem propor a seguinte classificação de métodos de reconhecimento de padrões:

• métodos intensionais baseados em operações com atributos.
• métodos extensionais baseados em operações com objetos.

É necessário enfatizar que a existência desses dois (e apenas dois) grupos de métodos de reconhecimento: os que operam com feições e os que operam com objetos, é profundamente natural. Deste ponto de vista, nenhum destes métodos, tomados separadamente do outro, permite formar uma reflexão adequada da área temática. Segundo os autores, entre esses métodos existe uma relação de complementaridade no sentido de N. Bohr, portanto, sistemas de reconhecimento promissores devem garantir a implementação de ambos os métodos, e não apenas de um deles.

Assim, a classificação dos métodos de reconhecimento proposta por D. A. Pospelov baseia-se nas leis fundamentais que fundamentam o modo de cognição humano em geral, o que o coloca em uma posição muito especial (privilegiada) em relação a outras classificações, que, neste contexto, procuram mais leve e artificial.

Métodos Intensionais

Uma característica distintiva dos métodos intensionais é que eles utilizam diferentes características de características e seus relacionamentos como elementos de operações na construção e aplicação de algoritmos de reconhecimento de padrões. Tais elementos podem ser valores individuais ou intervalos de valores de características, valores médios e variâncias, matrizes de relações de características, etc., sobre as quais as ações são executadas, expressas de forma analítica ou construtiva. Ao mesmo tempo, os objetos nesses métodos não são considerados unidades de informação integral, mas atuam como indicadores para avaliar a interação e o comportamento de seus atributos.

O grupo de métodos de reconhecimento de padrões intensionais é extenso, e sua divisão em subclasses é um tanto arbitrária.

Métodos baseados em estimativas das densidades de distribuição de valores de características

Esses métodos de reconhecimento de padrões são emprestados da teoria clássica das decisões estatísticas, na qual os objetos de estudo são considerados como realizações de uma variável aleatória multidimensional distribuída no espaço de características de acordo com alguma lei. Eles são baseados em um esquema de tomada de decisão Bayesiano que apela a probabilidades a priori de objetos pertencentes a uma determinada classe reconhecível e densidades de distribuição condicional de valores de vetores de características. Esses métodos são reduzidos a determinar a razão de verossimilhança em diferentes áreas do espaço de características multidimensionais.

O grupo de métodos baseados na estimativa das densidades de distribuição de valores de características está diretamente relacionado aos métodos de análise discriminante. A abordagem bayesiana para a tomada de decisão é uma das mais desenvolvidas na estatística moderna, os chamados métodos paramétricos, para os quais a expressão analítica da lei de distribuição (neste caso, a lei normal) é considerada conhecida e apenas uma pequena número de parâmetros (vetores médios e matrizes de covariância) precisam ser estimados.

As principais dificuldades na aplicação desses métodos são a necessidade de lembrar toda a amostra de treinamento para calcular estimativas de densidades de distribuição de probabilidade local e alta sensibilidade à não representatividade da amostra de treinamento.

Métodos baseados em suposições sobre a classe de funções de decisão

Neste grupo de métodos, a forma geral da função de decisão é considerada conhecida e seu funcional de qualidade é dado. Com base nesse funcional, a melhor aproximação da função de decisão é encontrada a partir da sequência de treinamento. As mais comuns são representações de funções de decisão na forma de polinômios lineares e não lineares generalizados. O funcional de qualidade da regra de decisão geralmente está associado ao erro de classificação.

A principal vantagem dos métodos baseados em suposições sobre a classe das funções de decisão é a clareza da formulação matemática do problema de reconhecimento como um problema de encontrar um extremo. A variedade de métodos deste grupo é explicada pela ampla gama de funcionais de qualidade de regra de decisão usados ​​e algoritmos de busca extrema. Uma generalização dos algoritmos considerados, que incluem, em particular, o algoritmo de Newton, algoritmos do tipo perceptron, etc., é o método de aproximação estocástica.

As possibilidades de algoritmos de gradiente para encontrar um extremo, especialmente no grupo de regras de decisão linear, têm sido bastante estudadas. A convergência desses algoritmos foi provada apenas para o caso em que as classes reconhecíveis de objetos são exibidas no espaço de características por estruturas geométricas compactas.

Uma qualidade suficientemente alta da regra de decisão pode ser alcançada usando algoritmos que não possuem uma prova matemática rigorosa da convergência da solução para o extremo global. Tais algoritmos incluem um grande grupo de procedimentos de programação heurística que representam a direção da modelagem evolutiva. A modelagem evolutiva é um método biônico emprestado da natureza. Baseia-se no uso de mecanismos de evolução conhecidos para substituir o processo de modelagem significativa de um objeto complexo pela modelagem fenomenológica de sua evolução. Um representante bem conhecido da modelagem evolutiva no reconhecimento de padrões é o método de contabilidade de grupo de argumentos (MGUA). O GMDH é baseado no princípio da auto-organização, e os algoritmos GMDH reproduzem o esquema de seleção em massa.

No entanto, a realização de objetivos práticos neste caso não é acompanhada pela extração de novos conhecimentos sobre a natureza dos objetos reconhecíveis. A possibilidade de extrair esse conhecimento, em particular o conhecimento sobre os mecanismos de interação de atributos (características), é fundamentalmente limitada aqui pela estrutura dada de tal interação, fixada na forma escolhida de funções decisivas.

Métodos Booleanos

Os métodos lógicos de reconhecimento de padrões são baseados no aparato da álgebra lógica e permitem operar com informações contidas não apenas em características individuais, mas também em combinações de valores de características. Nesses métodos, os valores de qualquer atributo são considerados como eventos elementares.

Na forma mais geral, os métodos lógicos podem ser caracterizados como uma espécie de busca de padrões lógicos na amostra de treinamento e a formação de um determinado sistema de regras de decisão lógica (por exemplo, na forma de conjunções de eventos elementares), cada um deles que tem seu próprio peso. O grupo de métodos lógicos é diversificado e inclui métodos de complexidade e profundidade de análise variadas. Para recursos dicotômicos (booleanos), os chamados classificadores em forma de árvore, o método de teste sem saída, o algoritmo Bark etc. são populares.

O algoritmo Kora, como outros métodos lógicos de reconhecimento de padrões, é bastante trabalhoso em termos de computação, pois é necessária uma enumeração completa ao selecionar as conjunções. Portanto, ao aplicar métodos lógicos, altos requisitos são colocados na organização eficiente do processo computacional, e esses métodos funcionam bem com dimensões relativamente pequenas do espaço de recursos e apenas em computadores poderosos.

Métodos linguísticos (estruturais)

Os métodos linguísticos de reconhecimento de padrões são baseados no uso de gramáticas especiais que geram linguagens que podem ser usadas para descrever um conjunto de propriedades de objetos reconhecíveis.

Para diferentes classes de objetos, são distinguidos elementos não derivativos (atômicos) (subimagens, signos) e possíveis relações entre eles. A gramática refere-se às regras para construir objetos a partir desses elementos não derivados.

Assim, cada objeto é uma coleção de elementos não derivativos, “conectados” uns aos outros de uma forma ou de outra, ou seja, por uma “frase” de alguma “linguagem”. Gostaria de enfatizar o valor ideológico muito significativo desse pensamento.

Ao analisar (parsing) uma "frase", sua "correção" sintática é determinada, ou, de forma equivalente, se alguma gramática fixa que descreve uma classe pode gerar uma descrição de objeto existente.

No entanto, a tarefa de recuperar (definir) gramáticas a partir de um determinado conjunto de declarações (frases - descrições de objetos) que geram uma determinada linguagem é difícil de formalizar.

Métodos extensionais

Nos métodos deste grupo, ao contrário da direção intensional, cada objeto estudado recebe um valor diagnóstico independente em maior ou menor grau. Em sua essência, esses métodos estão próximos da abordagem clínica, que considera as pessoas não como uma cadeia de objetos classificados de acordo com um ou outro indicador, mas como sistemas integrais, cada um dos quais é individual e tem um valor diagnóstico especial. Tal atitude cuidadosa em relação aos objetos de estudo não permite excluir ou perder informações sobre cada objeto individual, o que ocorre quando se aplicam os métodos de direção intencional, utilizando objetos apenas para detectar e fixar os padrões de comportamento de seus atributos.

As principais operações no reconhecimento de padrões usando os métodos discutidos são as operações de determinação da similaridade e diferença de objetos. Objetos no grupo especificado de métodos desempenham o papel de precedentes diagnósticos. Ao mesmo tempo, dependendo das condições de uma determinada tarefa, o papel de um precedente individual pode variar dentro dos mais amplos limites: desde o principal e definidor até a participação muito indireta no processo de reconhecimento. Por sua vez, as condições do problema podem exigir a participação de um número diferente de precedentes diagnósticos para uma solução bem-sucedida: de um em cada classe reconhecível para todo o tamanho da amostra, bem como diferentes formas de calcular as medidas de similaridade e diferença de objetos. Esses requisitos explicam a divisão adicional dos métodos extensionais em subclasses.

Método de comparação de protótipo

Este é o método de reconhecimento extensional mais simples. É usado, por exemplo, no caso em que as classes reconhecidas são exibidas no espaço de características por agrupamentos geométricos compactos. Nesse caso, o centro do agrupamento geométrico da classe (ou o objeto mais próximo do centro) geralmente é escolhido como ponto protótipo.

Para classificar um objeto desconhecido, o protótipo mais próximo dele é encontrado, e o objeto pertence à mesma classe desse protótipo. Obviamente, nenhuma imagem de classe generalizada é formada neste método.

Vários tipos de distâncias podem ser usados ​​como medida de proximidade. Muitas vezes para feições dicotômicas, a distância de Hamming é usada, que neste caso é igual ao quadrado da distância euclidiana. Neste caso, a regra de decisão para classificar objetos é equivalente a uma função de decisão linear.

Este fato deve ser especialmente observado. Demonstra claramente a conexão entre protótipo e representação indicativa de informações sobre a estrutura de dados. Usando a representação acima, por exemplo, qualquer escala de medição tradicional, que é uma função linear dos valores de características dicotômicas, pode ser considerada como um protótipo diagnóstico hipotético. Por sua vez, se a análise da estrutura espacial das classes reconhecidas nos permite concluir que elas são geometricamente compactas, basta substituir cada uma dessas classes por um protótipo, que na verdade equivale a um modelo de diagnóstico linear.

Na prática, é claro, a situação é muitas vezes diferente do exemplo idealizado descrito. Um pesquisador que pretenda aplicar um método de reconhecimento baseado na comparação com os protótipos de classes diagnósticas enfrenta problemas difíceis.

Em primeiro lugar, é a escolha de uma medida de proximidade (métrica), que pode alterar significativamente a configuração espacial da distribuição dos objetos. Em segundo lugar, um problema independente é a análise de estruturas multidimensionais de dados experimentais. Ambos os problemas são especialmente agudos para o pesquisador em condições de alta dimensão do espaço de características, o que é típico para problemas reais.

k método do vizinho mais próximo

O método dos k vizinhos mais próximos para resolver problemas de análise discriminante foi proposto pela primeira vez em 1952. É o seguinte.

Ao classificar um objeto desconhecido, um determinado número (k) de outros objetos geometricamente mais próximos a ele no espaço de características (vizinhos mais próximos) com já conhecidos pertencentes a classes reconhecíveis é encontrado. A decisão de atribuir um objeto desconhecido a uma determinada classe de diagnóstico é feita analisando informações sobre essa associação conhecida de seus vizinhos mais próximos, por exemplo, usando uma simples contagem de votos.

Inicialmente, o método dos k vizinhos mais próximos foi considerado um método não paramétrico para estimar a razão de verossimilhança. Para este método, são obtidas estimativas teóricas de sua eficácia em comparação com o classificador bayesiano ótimo. Prova-se que as probabilidades de erro assintótico para o método dos k vizinhos mais próximos excedem os erros da regra de Bayes em não mais que duas vezes.

Ao utilizar o método dos k vizinhos mais próximos para reconhecimento de padrões, o pesquisador tem que resolver o difícil problema de escolher uma métrica para determinar a proximidade dos objetos diagnosticados. Este problema nas condições de alta dimensão do espaço de características torna-se extremamente agravado devido à complexidade suficiente deste método, que se torna significativo mesmo para computadores de alto desempenho. Portanto, aqui, assim como no método de comparação de protótipos, é necessário resolver o problema criativo de analisar a estrutura multidimensional de dados experimentais para minimizar o número de objetos representando classes diagnósticas.

A necessidade de reduzir o número de objetos na amostra de treinamento (precedentes de diagnóstico) é uma desvantagem desse método, pois reduz a representatividade da amostra de treinamento.

Algoritmos para calcular notas ("votação")

O princípio de funcionamento dos algoritmos de avaliação (ABO) é calcular prioridades (escores de similaridade) que caracterizam a “proximidade” dos objetos reconhecidos e de referência de acordo com o sistema de conjuntos de características, que é um sistema de subconjuntos de um determinado conjunto de características .

Ao contrário de todos os métodos considerados anteriormente, os algoritmos para calcular estimativas operam com descrições de objetos de uma maneira fundamentalmente nova. Para esses algoritmos, os objetos existem simultaneamente em subespaços muito diferentes do espaço de características. A classe ABO traz a ideia de usar recursos ao seu fim lógico: como nem sempre se sabe quais combinações de recursos são mais informativas, no ABO o grau de similaridade dos objetos é calculado comparando todas as combinações possíveis ou determinadas de recursos incluídos nas descrições dos objetos.

As combinações de atributos utilizadas (subespaços) são chamadas de conjuntos de suporte ou conjuntos de descrições parciais de objetos. É introduzido o conceito de proximidade generalizada entre o objeto reconhecido e os objetos da amostra de treinamento (com uma classificação conhecida), que são chamados de objetos de referência. Essa proximidade é representada por uma combinação da proximidade do objeto reconhecível com objetos de referência calculados em conjuntos de descrições parciais. Assim, ABO é uma extensão do método dos k vizinhos mais próximos, no qual a proximidade dos objetos é considerada apenas em um determinado espaço de características.

Outra extensão do ABO é que nesses algoritmos o problema de determinar a similaridade e diferença de objetos é formulado como paramétrico e a etapa de configuração do ABO de acordo com a amostra de treinamento é selecionada, na qual os valores ótimos do parâmetros inseridos são selecionados. O critério de qualidade é o erro de reconhecimento, e literalmente tudo é parametrizado:

• regras para calcular a proximidade de objetos por características individuais;
• regras para calcular a proximidade de objetos em subespaços de recursos;
• o grau de importância de um determinado objeto de referência como precedente diagnóstico;
• o significado da contribuição de cada conjunto de características de referência para a avaliação final da semelhança do objeto reconhecido com qualquer classe diagnóstica.

Os parâmetros do resfriador de ar são definidos na forma de valores limite e (ou) como pesos dos componentes indicados.

As possibilidades teóricas do ABO não são pelo menos inferiores às de qualquer outro algoritmo de reconhecimento de padrões, uma vez que com a ajuda do ABO todas as operações concebíveis com os objetos em estudo podem ser implementadas.

Mas, como costuma acontecer, a expansão de potencialidades encontra grandes dificuldades na sua implementação prática, especialmente na fase de construção (tuning) de algoritmos deste tipo.

Dificuldades separadas foram observadas anteriormente ao discutir o método dos k vizinhos mais próximos, que pode ser interpretado como uma versão truncada do ABO. Também pode ser considerado de forma paramétrica e reduzir o problema a encontrar uma métrica ponderada do tipo selecionado. Ao mesmo tempo, questões teóricas complexas e problemas associados à organização de um processo computacional eficiente já surgem aqui para problemas de alta dimensão.

Para ABO, se você tentar usar os recursos desses algoritmos na íntegra, essas dificuldades aumentam muitas vezes.

Os problemas observados explicam o fato de que na prática o uso do ABO para resolver problemas de alta dimensão é acompanhado pela introdução de quaisquer restrições e suposições heurísticas. Em particular, há um exemplo do uso do ABO em psicodiagnóstico, no qual foi testada uma versão do ABO, que na verdade é equivalente ao método dos k vizinhos mais próximos.

Coletivos de Regras Decisivas

Ao final da revisão dos métodos de reconhecimento de padrões, vamos nos deter em mais uma abordagem. Essas são as chamadas equipes de regras de decisão (CRC).

Uma vez que diferentes algoritmos de reconhecimento se comportam de forma diferente na mesma amostra de objetos, surge naturalmente a questão de uma regra de decisão sintética que usa de forma adaptativa os pontos fortes desses algoritmos. A regra de decisão sintética usa um esquema de reconhecimento de dois níveis. No primeiro nível, os algoritmos de reconhecimento privado funcionam, cujos resultados são combinados no segundo nível no bloco de síntese. Os métodos mais comuns de tal combinação são baseados na alocação de áreas de competência de um determinado algoritmo. A maneira mais simples de encontrar áreas de competência é dividir a priori o espaço de atributos com base em considerações profissionais de uma determinada ciência (por exemplo, estratificação da amostra de acordo com algum atributo). Em seguida, para cada uma das áreas selecionadas, é construído seu próprio algoritmo de reconhecimento. Outro método é baseado no uso de análise formal para determinar áreas locais do espaço de características como vizinhanças de objetos reconhecíveis para os quais o sucesso de qualquer algoritmo de reconhecimento específico foi comprovado.

A abordagem mais geral para a construção de um bloco de síntese considera os indicadores resultantes de algoritmos parciais como características iniciais para a construção de uma nova regra de decisão generalizada. Neste caso, todos os métodos acima de direções intensional e extensional no reconhecimento de padrões podem ser usados. Eficazes para resolver o problema de criar um conjunto de regras de decisão são algoritmos lógicos do tipo "Kora" e algoritmos para cálculo de estimativas (ABO), que formam a base da chamada abordagem algébrica, que fornece pesquisa e uma descrição construtiva de algoritmos de reconhecimento, dentro dos quais se encaixam todos os tipos de algoritmos existentes.

Análise comparativa de métodos de reconhecimento de padrões

Vamos comparar os métodos de reconhecimento de padrões descritos acima e avaliar o grau de sua adequação aos requisitos formulados na Seção 3.3.3 para modelos SDA para sistemas de controle automatizado adaptativo para sistemas complexos.

Para resolver problemas reais do conjunto de métodos da direção intencional, métodos paramétricos e métodos baseados em propostas sobre a forma de funções decisivas são de valor prático. Os métodos paramétricos formam a base da metodologia tradicional de construção de indicadores. A aplicação destes métodos em problemas reais está associada à imposição de fortes restrições na estrutura dos dados, que levam a modelos de diagnóstico lineares com estimativas muito aproximadas de seus parâmetros. Ao usar métodos baseados em suposições sobre a forma das funções de decisão, o pesquisador também é forçado a recorrer a modelos lineares. Isso se deve à alta dimensão do espaço de características, típica de problemas reais, que, com o aumento do grau da função de decisão polinomial, dá um grande aumento no número de seus membros com um aumento concomitante problemático na qualidade do reconhecimento. Assim, projetando a área de aplicação potencial de métodos de reconhecimento intencional a problemas reais, obtemos um quadro que corresponde à metodologia tradicional bem estabelecida de modelos de diagnóstico linear.

As propriedades dos modelos diagnósticos lineares, nos quais o indicador diagnóstico é representado por uma soma ponderada das características iniciais, são bem estudadas. Os resultados desses modelos (com normalização apropriada) são interpretados como distâncias dos objetos em estudo a algum hiperplano no espaço de características ou, equivalentemente, como projeções dos objetos em alguma linha reta no espaço dado. Portanto, os modelos lineares são adequados apenas para configurações geométricas simples de regiões do espaço de características nas quais são mapeados objetos de diferentes classes de diagnóstico. Com distribuições mais complexas, esses modelos fundamentalmente não podem refletir muitos recursos da estrutura de dados experimental. Ao mesmo tempo, esses recursos podem fornecer informações de diagnóstico valiosas.

Ao mesmo tempo, o aparecimento em qualquer problema real de estruturas multidimensionais simples (em particular, distribuições normais multidimensionais) deve ser visto como uma exceção e não como uma regra. Muitas vezes, as classes diagnósticas são formadas com base em critérios externos complexos, o que implica automaticamente na heterogeneidade geométrica dessas classes no espaço de características. Isto é especialmente verdadeiro para os critérios de “vida” que são mais frequentemente encontrados na prática. Sob tais condições, o uso de modelos lineares captura apenas os padrões mais "ásperos" de informações experimentais.

O uso de métodos extensionais não está associado a nenhuma suposição sobre a estrutura da informação experimental, exceto que dentro das classes reconhecidas deve haver um ou mais grupos de objetos que são um pouco semelhantes, e objetos de diferentes classes devem diferir uns dos outros em alguns aspectos. maneira. É óbvio que para qualquer dimensão finita da amostra de treinamento (e não pode ser diferente), esse requisito é sempre atendido simplesmente porque existem diferenças aleatórias entre os objetos. Várias medidas de proximidade (distância) de objetos no espaço de características são usadas como medidas de similaridade. Portanto, o uso efetivo de métodos de reconhecimento de padrões extensionais depende de quão bem essas medidas de proximidade são determinadas, bem como de quais objetos da amostra de treinamento (objetos com classificação conhecida) desempenham o papel de precedentes diagnósticos. A solução bem-sucedida desses problemas dá um resultado que se aproxima dos limites teoricamente alcançáveis ​​da eficiência do reconhecimento.

As vantagens dos métodos extensionais de reconhecimento de padrões se opõem, em primeiro lugar, à alta complexidade técnica de sua implementação prática. Para espaços de características de alta dimensão, a tarefa aparentemente simples de encontrar pares de pontos mais próximos se torna um problema sério. Além disso, muitos autores notam como um problema a necessidade de lembrar um número suficientemente grande de objetos representando classes reconhecíveis.

Em si, isso não é um problema, mas é percebido como um problema (por exemplo, no método dos k vizinhos mais próximos) pelo motivo de que ao reconhecer cada objeto, ocorre uma enumeração completa de todos os objetos da amostra de treinamento.

Portanto, é aconselhável aplicar o modelo do sistema de reconhecimento, no qual o problema de uma enumeração completa dos objetos da amostra de treinamento durante o reconhecimento é removido, pois é realizado apenas uma vez ao formar imagens generalizadas de classes de reconhecimento. No próprio reconhecimento, o objeto identificado é comparado apenas com imagens generalizadas de classes de reconhecimento, cujo número é fixo e não depende em nada da dimensão da amostra de treinamento. Essa abordagem permite aumentar a dimensão da amostra de treinamento até que a alta qualidade necessária de imagens generalizadas seja alcançada, sem medo de que isso possa levar a um aumento inaceitável no tempo de reconhecimento (já que o tempo de reconhecimento neste modelo não depende de a dimensão do treinamento).

Os problemas teóricos de aplicação de métodos de reconhecimento extensional estão relacionados aos problemas de busca de grupos informativos de características, encontrar métricas ótimas para medir a similaridade e diferença de objetos e analisar a estrutura da informação experimental. Ao mesmo tempo, a solução bem-sucedida desses problemas permite não apenas projetar algoritmos de reconhecimento eficazes, mas também fazer a transição do conhecimento extensional dos fatos empíricos para o conhecimento intencional sobre os padrões de sua estrutura.

A transição do conhecimento extensional para o conhecimento intensional ocorre na fase em que um algoritmo de reconhecimento formal já foi construído e sua eficácia foi demonstrada. Em seguida, é realizado o estudo dos mecanismos pelos quais a eficiência obtida é alcançada. Tal estudo, associado à análise da estrutura geométrica dos dados, pode, por exemplo, levar à conclusão de que basta substituir os objetos que representam uma determinada classe diagnóstica por um representante típico (protótipo). Isso equivale, como observado acima, a definir uma escala de diagnóstico linear tradicional. Também é possível que seja suficiente substituir cada classe diagnóstica por vários objetos significativos como representantes típicos de algumas subclasses, o que equivale a construir um leque de escalas lineares. Existem outras opções, que serão discutidas abaixo.

Assim, uma revisão dos métodos de reconhecimento mostra que vários métodos diferentes de reconhecimento de padrões foram desenvolvidos teoricamente no presente. A literatura fornece uma classificação detalhada deles. No entanto, para a maioria desses métodos, sua implementação em software está ausente, e isso é profundamente natural, pode-se até dizer “predeterminado” pelas características dos próprios métodos de reconhecimento. Isso pode ser julgado pelo fato de tais sistemas serem pouco citados na literatura especializada e em outras fontes de informação.

Consequentemente, a questão da aplicabilidade prática de certos métodos de reconhecimento teórico para resolver problemas práticos com dimensões de dados reais (ou seja, bastante significativas) e em computadores modernos reais permanece insuficientemente desenvolvida.

A circunstância acima pode ser compreendida se lembrarmos que a complexidade do modelo matemático aumenta exponencialmente a complexidade da implementação de software do sistema e na mesma medida reduz as chances de que esse sistema realmente funcione. Isso significa que apenas sistemas de software baseados em modelos matemáticos bastante simples e “transparentes” podem ser implementados no mercado. Portanto, um desenvolvedor interessado em replicar seu produto de software aborda a questão da escolha de um modelo matemático não do ponto de vista puramente científico, mas como um pragmatista, levando em consideração as possibilidades de implementação do software. Ele acredita que o modelo deve ser o mais simples possível, o que significa que deve ser implementado com menor custo e com melhor qualidade, e também deve funcionar (ser praticamente eficaz).

Nesse sentido, a tarefa de implementar em sistemas de reconhecimento um mecanismo para generalizar descrições de objetos pertencentes à mesma classe, ou seja, mecanismo para a formação de imagens generalizadas compactas. É óbvio que tal mecanismo de generalização permitirá "comprimir" qualquer amostra de treinamento em termos de dimensão para uma base de imagens generalizadas conhecidas antecipadamente em termos de dimensão. Isso também nos permitirá definir e resolver uma série de problemas que não podem ser formulados em métodos de reconhecimento como a comparação com o método do protótipo, o método dos k vizinhos mais próximos e ABO.

Estas são as tarefas:

• determinar a contribuição de informações de recursos para o retrato de informações de uma imagem generalizada;
• análise cluster-construtiva de imagens generalizadas;
• determinação da carga semântica do recurso;
• análise semântica de agrupamento de características;
• uma comparação significativa de imagens de classes generalizadas entre si e recursos entre si (diagramas cognitivos, incluindo diagramas de Merlin).

O método que possibilitou a solução desses problemas também diferencia o sistema de perspectiva baseado nele de outros sistemas, assim como os compiladores diferem dos intérpretes, pois devido à formação de imagens generalizadas nesse sistema de perspectiva, o tempo de reconhecimento é independente do tempo de reconhecimento. o tamanho da amostra de treinamento. Sabe-se que é a existência dessa dependência que leva a um tempo de computador praticamente inaceitável gasto no reconhecimento em métodos como o método dos k vizinhos mais próximos, ABO e CLD em tais dimensões da amostra de treinamento, quando podemos falar em estatísticas suficientes .

Em conclusão de uma breve revisão dos métodos de reconhecimento, apresentamos a essência do exposto em uma tabela resumo (Tabela 3.1), contendo uma breve descrição dos vários métodos de reconhecimento de padrões nos seguintes parâmetros:

• classificação de métodos de reconhecimento;
• áreas de aplicação dos métodos de reconhecimento;
• classificação das limitações dos métodos de reconhecimento.

Classificação dos métodos de reconhecimento		Area de aplicação	Limitações (desvantagens)
Métodos de reconhecimento intensivo	Métodos baseados em estimativas das densidades de distribuição de valores de características (ou semelhanças e diferenças entre objetos)	Problemas com uma distribuição conhecida, geralmente normal, a necessidade de coletar grandes estatísticas	A necessidade de enumerar todo o conjunto de treinamento durante o reconhecimento, alta sensibilidade à não representatividade do conjunto de treinamento e artefatos
	Métodos baseados em suposições sobre a classe de funções de decisão	As classes devem ser bem separáveis, o sistema de características deve ser ortonnormal	A forma da função de decisão deve ser conhecida antecipadamente. A impossibilidade de levar em conta novos conhecimentos sobre correlações entre características
	Métodos Booleanos		Ao selecionar regras de decisão lógica (conjunções), é necessária uma enumeração completa. Alta complexidade computacional
	Métodos linguísticos (estruturais)	Problemas de pequena dimensão do espaço de recursos	A tarefa de restaurar (definir) a gramática de um determinado conjunto de declarações (descrições de objetos) é difícil de formalizar. Problemas teóricos não resolvidos
Métodos extensionais de reconhecimento	Método de comparação de protótipo	Problemas de pequena dimensão do espaço de recursos	Alta dependência dos resultados da classificação em medidas de distância (métricas). Métrica ideal desconhecida
	k método do vizinho mais próximo		Alta dependência dos resultados da classificação em medidas de distância (métricas). A necessidade de uma enumeração completa da amostra de treinamento durante o reconhecimento. Complexidade computacional
	Algoritmos para cálculo de notas (votação) AVO	Problemas de pequena dimensão em termos de número de classes e funcionalidades	Dependência dos resultados da classificação na medida de distância (métrica). A necessidade de uma enumeração completa da amostra de treinamento durante o reconhecimento. Alta complexidade técnica do método
	Coletivos de Regras Decisivas (CRCs)	Problemas de pequena dimensão em termos de número de classes e funcionalidades	Complexidade técnica muito alta do método, o número não resolvido de problemas teóricos, tanto na determinação das áreas de competência de métodos particulares, quanto nos próprios métodos particulares

Tabela 3.1 - Tabela-resumo de classificação dos métodos de reconhecimento, comparação de suas áreas de aplicação e limitações

O papel e o lugar do reconhecimento de padrões na automação da gestão de sistemas complexos

O sistema de controle automatizado consiste em duas partes principais: o objeto de controle e o sistema de controle.

O sistema de controle executa as seguintes funções:

• identificação do estado do objeto de controle;
• desenvolvimento de uma ação de controle com base nos objetivos da gestão, levando em consideração o estado do objeto de controle e o ambiente;
• fornecendo um efeito de controle sobre o objeto de controle.

O reconhecimento de padrões nada mais é do que a identificação do estado de algum objeto.

Portanto, a possibilidade de usar o sistema de reconhecimento de padrões na fase de identificação do estado do objeto de controle parece bastante óbvia e natural. No entanto, isso pode não ser necessário. Portanto, surge a pergunta em quais casos é aconselhável usar o sistema de reconhecimento no sistema de controle automatizado e em quais não é.

De acordo com os dados da literatura, em muitos sistemas de controle automatizados modernos e desenvolvidos anteriormente nos subsistemas para identificar o estado do objeto de controle e gerar ações de controle, são usados ​​modelos matemáticos determinísticos de “contagem direta”, que determinam de forma inequívoca e simples o que fazer com o objeto de controle se ele tiver determinados parâmetros externos.

Ao mesmo tempo, a questão de como esses parâmetros estão relacionados a determinados estados do objeto de controle não é levantada ou resolvida. Esta posição corresponde ao ponto de vista, que consiste no facto de a sua relação um-para-um ser aceite “por defeito”. Portanto, os termos: "parâmetros do objeto de controle" e "estado do objeto de controle" são considerados como sinônimos, e o conceito de "estado do objeto de controle" não é introduzido explicitamente. No entanto, é óbvio que, no caso geral, a relação entre os parâmetros observados do objeto de controle e seu estado é dinâmica e probabilística.

Assim, os sistemas de controle automatizados tradicionais são essencialmente sistemas de controle paramétricos, ou seja, sistemas que gerenciam não os estados do objeto de controle, mas apenas seus parâmetros observáveis. A decisão sobre a ação de controle é tomada em tais sistemas como se "às cegas", ou seja, sem formar uma imagem holística do objeto de controle e do ambiente em seu estado atual, bem como sem prever o desenvolvimento do ambiente e a reação do objeto de controle a certas ações de controle sobre ele, agindo simultaneamente com a influência prevista do ambiente .

A partir das posições desenvolvidas neste artigo, o termo "tomada de decisão" no sentido moderno dificilmente é aplicável aos sistemas de controle automatizados tradicionais. O fato é que a “tomada de decisão”, pelo menos, envolve uma visão holística de um objeto no ambiente, e não apenas em seu estado atual, mas também em dinâmica, e em interação tanto entre si quanto com o sistema de controle, envolve a consideração de várias opções alternativas para o desenvolvimento de todo este sistema, bem como o estreitamento da diversidade (redução) dessas alternativas com base em determinados critérios-alvo. Nada disso, obviamente, não está no ACS tradicional, ou está, mas de forma simplificada.

É claro que o método tradicional é adequado e sua aplicação é bastante correta e justificada nos casos em que o objeto de controle é de fato um sistema estável e rigidamente determinado, e a influência do ambiente sobre ele pode ser desprezada.

No entanto, em outros casos, este método é ineficaz.

Se o objeto de controle é dinâmico, então os modelos subjacentes aos seus algoritmos de controle rapidamente se tornam inadequados, pois a relação entre os parâmetros de entrada e saída muda, bem como o próprio conjunto de parâmetros essenciais. Em essência, isso significa que os sistemas de controle automatizados tradicionais são capazes de controlar o estado do objeto de controle apenas próximo ao ponto de equilíbrio por meio de ações de controle fracas sobre ele, ou seja, pelo método de pequenas perturbações. Longe do estado de equilíbrio, do ponto de vista tradicional, o comportamento do objeto de controle parece imprevisível e incontrolável.

Se não houver relação inequívoca entre os parâmetros de entrada e saída do objeto de controle (ou seja, entre os parâmetros de entrada e o estado do objeto), ou seja, se essa relação tiver uma natureza probabilística pronunciada, então os modelos determinísticos, em onde se assume que o resultado da medição de um determinado parâmetro é simplesmente número, inicialmente não aplicável. Além disso, a forma dessa relação pode simplesmente ser desconhecida, e então é necessário partir da suposição mais geral: que ela é probabilística, ou não definida.

Um sistema de controle automatizado construído sobre princípios tradicionais só pode funcionar com base em parâmetros, cujos padrões de relacionamento já são conhecidos, estudados e refletidos no modelo matemático, neste estudo a tarefa foi definida para desenvolver tais métodos para projetar controle automatizado sistemas que permitirão criar sistemas que possam identificar e definir os parâmetros mais significativos e determinar a natureza das ligações entre eles e os estados do objeto de controle.

Neste caso, é necessário aplicar métodos de medição mais desenvolvidos e adequados à situação real:

• classificação ou reconhecimento de padrões (aprendizagem baseada numa amostra de treino, adaptabilidade de algoritmos de reconhecimento, adaptabilidade de conjuntos de classes e parâmetros estudados, selecção dos parâmetros mais significativos e redução da dimensão de descrição mantendo uma dada redundância, etc.);
• medidas estatísticas, quando o resultado da medição de um determinado parâmetro não é um único número, mas uma distribuição de probabilidade: uma mudança em uma variável estatística não significa uma mudança em seu valor em si, mas uma mudança nas características da distribuição de probabilidade de seus valores.

Como resultado, os sistemas de controle automatizados baseados na abordagem determinística tradicional praticamente não funcionam com objetos de controle dinâmicos multiparâmetros e fracamente determinados, como, por exemplo, sistemas macro e micro-socioeconômicos em uma economia dinâmica do “ período de transição”, elite hierárquica e grupos étnicos, sociedade e eleitorado, fisiologia e psique humana, ecossistemas naturais e artificiais e muitos outros.

É muito significativo que, em meados dos anos 80, a escola de I.Prigozhin tenha desenvolvido uma abordagem segundo a qual, no desenvolvimento de qualquer sistema (incluindo uma pessoa), alternam-se períodos durante os quais o sistema se comporta como “principalmente determinístico”, ou como "principalmente aleatório". Naturalmente, um sistema de controle real deve gerenciar de forma estável o objeto de controle não apenas em seções “determinísticas” de sua história, mas também em pontos em que seu comportamento posterior se torna altamente incerto. Isso por si só significa que é necessário desenvolver abordagens para o gerenciamento de sistemas em cujo comportamento há um grande elemento de aleatoriedade (ou o que atualmente é descrito matematicamente como "aleatoriedade").

Portanto, a composição de sistemas de controle automatizados promissores que fornecem controle de sistemas dinâmicos complexos multiparâmetros fracamente determinísticos, como elos funcionais essenciais, aparentemente incluirá subsistemas para identificar e prever os estados do ambiente e do objeto de controle, baseados em métodos de inteligência artificial (principalmente reconhecimento de padrões), métodos de apoio à tomada de decisão e teoria da informação.

Consideremos brevemente a questão do uso de sistemas de reconhecimento de imagem para tomar uma decisão sobre uma ação de controle (essa questão será discutida com mais detalhes posteriormente, pois é a chave para este trabalho). Se tomarmos o alvo e outros estados do objeto de controle como classes de reconhecimento, e os fatores que o influenciam como características, então uma medida da relação entre fatores e estados pode ser formada no modelo de reconhecimento de padrões. Isso permite obter informações sobre os fatores que contribuem ou dificultam sua transição para esse estado, com base em um determinado estado do objeto de controle, e, com base nisso, desenvolver uma decisão sobre a ação de controle.

Os fatores podem ser divididos nos seguintes grupos:

• caracterizar a pré-história do objeto de controle;
• caracterizar o estado atual do objeto de controle;
• Fatores Ambientais;
• fatores tecnológicos (gerenciados).

Assim, os sistemas de reconhecimento de imagem podem ser usados ​​como parte de um sistema de controle automatizado: em subsistemas para identificar o estado de um objeto de controle e gerar ações de controle.

Isso é útil quando o objeto de controle é um sistema complexo.

Tomar uma decisão sobre a ação de controle no sistema de controle automatizado

A solução do problema de síntese de sistemas de controle automatizados adaptativos por sistemas complexos é considerada neste artigo, levando em conta inúmeras e profundas analogias entre os métodos de reconhecimento de padrões e tomada de decisão.

Por um lado, a tarefa de reconhecimento de padrões é uma decisão sobre o pertencimento de um objeto reconhecível a uma determinada classe de reconhecimento.

Por outro lado, os autores propõem considerar o problema de tomada de decisão como um problema inverso de decodificação ou um problema inverso de reconhecimento de padrões (ver seção 2.2.2).

A semelhança das ideias básicas subjacentes aos métodos de reconhecimento de padrões e tomada de decisão torna-se especialmente óbvia quando as consideramos do ponto de vista da teoria da informação.

Variedade de tarefas de tomada de decisão

A tomada de decisão como a realização de um objetivo

Definição: tomar uma decisão (“escolha”) é uma ação sobre um conjunto de alternativas, como resultado do estreitamento do conjunto original de alternativas, ou seja, ele é reduzido.

A escolha é uma ação que dá propósito a toda atividade. É por meio de atos de escolha que se realiza a subordinação de toda atividade a um objetivo específico ou a um conjunto de objetivos inter-relacionados.

Assim, para que o ato de escolha se torne possível, é necessário o seguinte:

• geração ou descoberta de um conjunto de alternativas sobre as quais fazer uma escolha;
• determinação das metas para a realização das quais a escolha é feita;
• desenvolvimento e aplicação de um método para comparar alternativas entre si, ou seja, determinação de uma classificação de preferência para cada alternativa de acordo com determinados critérios, permitindo avaliar indiretamente como cada alternativa atende ao objetivo.

O trabalho moderno no campo do suporte à decisão revelou uma situação característica, que consiste no fato de que a formalização completa de encontrar a melhor (em certo sentido) solução só é possível para problemas bem estudados e relativamente simples, enquanto na prática, problemas fracamente estruturados são mais comuns, para os quais algoritmos completamente formalizados não foram desenvolvidos (exceto para enumeração exaustiva e tentativa e erro). No entanto, profissionais experientes, competentes e capazes muitas vezes fazem escolhas que acabam sendo muito boas. Portanto, a tendência atual na prática de tomada de decisão em situações naturais é combinar a capacidade de uma pessoa para resolver problemas não formalizados com as capacidades de métodos formais e modelagem computacional: sistemas interativos de apoio à decisão, sistemas especialistas, sistemas adaptativos homem-máquina automatizados. sistemas de controle, redes neurais e sistemas cognitivos.

Tomada de decisão como remoção de incerteza (abordagem de informação)

O processo de obtenção de informações pode ser considerado como uma diminuição da incerteza como resultado do recebimento de um sinal, e a quantidade de informações - como uma medida quantitativa do grau de remoção da incerteza.

Mas como resultado da escolha de algum subconjunto de alternativas do conjunto, ou seja, como resultado da tomada de uma decisão, acontece a mesma coisa (diminuição da incerteza). Isso significa que cada escolha, cada decisão gera uma certa quantidade de informação e, portanto, pode ser descrita em termos de teoria da informação.

Classificação de problemas de tomada de decisão

A multiplicidade de tarefas de tomada de decisão deve-se ao fato de que cada componente da situação em que a tomada de decisão é realizada pode ser implementado em opções qualitativamente diferentes.

Aqui estão apenas algumas dessas opções:

• o conjunto de alternativas, por um lado, pode ser finito, contável ou contínuo e, por outro, pode ser fechado (ou seja, completamente conhecido) ou aberto (incluindo elementos desconhecidos);
• as alternativas podem ser avaliadas de acordo com um ou mais critérios, que, por sua vez, podem ser quantitativos ou qualitativos;
• o modo de seleção pode ser único (uma vez) ou múltiplo, repetitivo, incluindo feedback sobre os resultados da seleção, ou seja, permitir a aprendizagem de algoritmos de tomada de decisão, tendo em conta as consequências das eleições anteriores;
• as consequências da escolha de cada alternativa podem ser conhecidas com precisão antecipadamente (escolha sob certeza), ter uma natureza probabilística quando as probabilidades de resultados possíveis são conhecidas após a escolha ser feita (escolha sob risco) ou ter um resultado ambíguo com probabilidades desconhecidas (escolha sob incerteza);
• a responsabilidade pela escolha pode ser ausente, ser individual ou grupal;
• o grau de consistência dos objetivos em uma escolha grupal pode variar desde a completa coincidência dos interesses das partes (escolha cooperativa) até seu oposto (escolha em situação de conflito). Opções intermediárias também são possíveis: um compromisso, uma coalizão, um conflito crescente ou desaparecendo.

Várias combinações dessas opções levam a inúmeros problemas de tomada de decisão que foram estudados em graus variados.

Linguagens para descrever métodos de tomada de decisão

Um e o mesmo fenômeno pode ser falado em diferentes línguas de vários graus de generalidade e adequação. Até o momento, existem três linguagens principais para descrever a escolha.

A mais simples, mais desenvolvida e mais popular é a linguagem de critérios.

Idioma dos critérios

O nome dessa linguagem está associado à suposição básica de que cada alternativa individual pode ser avaliada por algum número específico (um), após o qual a comparação de alternativas é reduzida a uma comparação de seus números correspondentes.

Seja, por exemplo, (X) um conjunto de alternativas, e x uma alternativa definida pertencente a este conjunto: x∈X. Então considera-se que para todo x pode ser dada uma função q(x), que é chamada de critério (critério de qualidade, função objetivo, função de preferência, função de utilidade, etc.), que tem a propriedade de que se a alternativa x 1 for preferível a x 2 (indicado: x 1 > x 2), então q (x 1) > q (x 2).

Nesse caso, a escolha se reduz a encontrar uma alternativa com o maior valor da função critério.

No entanto, na prática, a utilização de apenas um critério para comparar o grau de preferência das alternativas acaba sendo uma simplificação injustificada, pois uma consideração mais detalhada das alternativas leva à necessidade de avaliá-las não de acordo com um, mas de acordo com muitos. critérios que podem ser de natureza diferente e qualitativamente diferentes entre si.

Por exemplo, ao escolher o tipo de aeronave mais aceitável para os passageiros e a organização operadora em determinados tipos de rotas, a comparação é realizada simultaneamente de acordo com vários grupos de critérios: técnicos, tecnológicos, econômicos, sociais, ergonômicos etc.

Os problemas multicritério não têm uma solução geral única. Portanto, muitas maneiras são propostas para dar a um problema multicritério uma forma particular que permite uma única solução geral. Naturalmente, essas soluções são geralmente diferentes para diferentes métodos. Portanto, talvez o principal na solução de um problema multicritério seja a justificativa desse tipo de sua formulação.

Várias opções para simplificar o problema de seleção multicritério são usadas. Vamos listar alguns deles.

1. Maximização condicional (não é encontrado o extremo global do critério integral, mas o extremo local do critério principal).
2. Procure uma alternativa com as propriedades dadas.
3. Encontrando o conjunto de Pareto.
4. Redução de um problema multicritério para um problema de critério único através da introdução de um critério integral.

Consideremos com mais detalhes a formulação formal do método de redução de um problema multicritério a um único critério.

Introduzimos o critério integral q 0 (x) como uma função escalar do argumento vetorial:

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

O critério integral permite ordenar as alternativas por q 0 , destacando a melhor (no sentido deste critério). A forma da função q 0 é determinada por quão especificamente imaginamos a contribuição de cada critério para o critério integral. Geralmente funções aditivas e multiplicativas são usadas:

q 0 = ∑a i ⋅q i /si

1 - q 0 = ∏(1 - b i ⋅q i /s i)

Coeficientes s i fornecem:

1. Adimensionalidade ou uma única dimensão do número a i ⋅q i /s i (diferentes critérios particulares podem ter dimensões diferentes, e então é impossível realizar operações aritméticas sobre eles e reduzi-los a um critério integral).
2. Normalização, ou seja. provisão da condição: b i ⋅q i /s i<1.

Os coeficientes a i e b i refletem a contribuição relativa de critérios particulares q i para o critério integral.

Assim, em um cenário multicritério, o problema de tomar uma decisão sobre a escolha de uma das alternativas é reduzido a maximizar o critério integral:

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

O principal problema na formulação multicritério do problema de tomada de decisão é que é necessário encontrar tal forma analítica dos coeficientes a i e b i , que forneceria as seguintes propriedades do modelo:

• alto grau de adequação da área temática e do ponto de vista dos especialistas;
• dificuldades computacionais mínimas em maximizar o critério integral, ou seja, seu cálculo para diferentes alternativas;
• estabilidade dos resultados da maximização do critério integral a partir de pequenas perturbações dos dados iniciais.
• A estabilidade da solução significa que uma pequena mudança nos dados iniciais deve levar a uma pequena mudança no valor do critério integral e, consequentemente, a uma pequena mudança na decisão que está sendo tomada. Assim, se os dados iniciais são praticamente os mesmos, então a decisão deve ser igual ou muito próxima.

Linguagem de Seleção Binária Sequencial

A linguagem das relações binárias é uma generalização da linguagem multicritério e se baseia no fato de que quando avaliamos alguma alternativa, essa avaliação é sempre relativa, ou seja, explicitamente ou mais frequentemente implicitamente, outras alternativas do conjunto em estudo ou da população em geral são usadas como base ou quadro de referência para comparação. O pensamento humano é baseado na busca e análise de opostos (construtos), por isso é sempre mais fácil para nós escolher uma entre duas opções opostas do que uma opção de um conjunto grande e de forma alguma desordenado.

Assim, os principais pressupostos desta linguagem resumem-se ao seguinte:

• uma única alternativa não é avaliada, ou seja, a função critério não é introduzida;
• para cada par de alternativas, pode-se estabelecer de alguma forma que uma delas é preferível à outra, ou que são equivalentes ou incomparáveis;
• a relação de preferência em qualquer par de alternativas não depende das outras alternativas apresentadas para escolha.

Existem várias maneiras de especificar relações binárias: direta, matricial, usando gráficos de preferência, o método das seções, etc.

As relações entre alternativas de um par são expressas através dos conceitos de equivalência, ordem e dominância.

Funções de linguagem generalizada de escolha

A linguagem de funções de escolha é baseada na teoria dos conjuntos e permite operar com mapeamentos de conjuntos para seus subconjuntos correspondentes a diferentes escolhas sem a necessidade de enumerar elementos. Esta linguagem é muito geral e potencialmente permite que qualquer escolha seja descrita. No entanto, o aparato matemático das funções de escolha generalizada está atualmente sendo desenvolvido e testado principalmente em problemas que já foram resolvidos usando o critério ou abordagens binárias.

escolha do grupo

Que haja um grupo de pessoas que tenham o direito de tomar parte nas decisões coletivas. Suponha que esse grupo esteja considerando algum conjunto de alternativas e cada membro do grupo faça sua escolha. A tarefa é desenvolver uma solução que de certa forma coordene as escolhas individuais e de alguma forma expresse a "opinião geral" do grupo, ou seja, tomada como uma escolha do grupo.

Naturalmente, diferentes decisões de grupo corresponderão a diferentes princípios de coordenação de decisões individuais.

As regras para coordenar decisões individuais em uma escolha de grupo são chamadas de regras de votação. A mais comum é a "regra da maioria", em que a decisão do grupo é tomada pela alternativa que recebe mais votos.

Deve-se entender que tal decisão reflete apenas a prevalência de diferentes pontos de vista no grupo, e não uma opção verdadeiramente ótima, na qual ninguém pode votar. "A verdade não é determinada pelo voto."

Além disso, existem os chamados "paradoxos do voto", sendo o mais famoso o paradoxo de Arrow.

Esses paradoxos podem levar, e às vezes levam, a aspectos muito desagradáveis ​​do procedimento de votação: por exemplo, há casos em que o grupo não pode tomar uma única decisão (não há quórum ou todos votam em sua própria opção única, etc.). .), e às vezes (na votação em vários estágios) a minoria pode impor sua vontade à maioria.

Escolha sob incerteza

A certeza é um caso especial de incerteza, a saber: é uma incerteza próxima de zero.

Na teoria da escolha moderna, acredita-se que existem três tipos principais de incerteza em problemas de tomada de decisão:

1. Incerteza informacional (estatística) dos dados iniciais para a tomada de decisão.
2. Incerteza das consequências da tomada de decisão (escolha).
3. Vaguidade na descrição dos componentes do processo decisório.

Vamos considerá-los em ordem.

Incerteza informacional (estatística) nos dados iniciais

Os dados obtidos sobre a área temática não podem ser considerados como absolutamente precisos. Além disso, é óbvio que esses dados nos interessam não em si mesmos, mas apenas como sinais que, talvez, tragam certas informações sobre o que realmente nos interessa. Assim, é mais realista considerar que estamos lidando com dados que não são apenas ruidosos e imprecisos, mas também indiretos e possivelmente incompletos. Além disso, esses dados não dizem respeito a toda a população (geral) em estudo, mas apenas a um certo subconjunto dela, sobre o qual conseguimos coletar dados, mas ao mesmo tempo queremos tirar conclusões sobre toda a população, e também queremos saber o grau de confiabilidade dessas conclusões.

Nessas condições, é utilizada a teoria das decisões estatísticas.

Existem duas fontes principais de incerteza nesta teoria. Primeiro, não se sabe a qual distribuição os dados originais obedecem. Em segundo lugar, não se sabe qual distribuição possui o conjunto (população geral) sobre o qual queremos tirar conclusões de seu subconjunto que forma os dados iniciais.

Os procedimentos estatísticos são os procedimentos de tomada de decisão que removem esses dois tipos de incerteza.

Deve-se notar que há uma série de razões que levam à aplicação incorreta de métodos estatísticos:

• inferências estatísticas, como qualquer outra, sempre têm alguma confiabilidade ou certeza definida. Mas, ao contrário de muitos outros casos, a confiabilidade dos achados estatísticos é conhecida e determinada no decorrer da pesquisa estatística;
• a qualidade da solução obtida como resultado da aplicação do procedimento estatístico depende da qualidade dos dados iniciais;
• os dados que não tenham natureza estatística não devem ser submetidos a tratamento estatístico;
• é necessário utilizar procedimentos estatísticos correspondentes ao nível de informação a priori sobre a população em estudo (por exemplo, não se deve aplicar métodos de análise de variância a dados não gaussianos). Se a distribuição dos dados originais for desconhecida, deve-se estabelecê-la ou usar vários métodos diferentes e comparar os resultados. Se forem muito diferentes, isso indica a inaplicabilidade de alguns dos procedimentos utilizados.

Incerteza das Consequências

Quando as consequências da escolha de uma alternativa são determinadas exclusivamente pela própria alternativa, então não podemos distinguir entre uma alternativa e suas consequências, assumindo que, escolhendo uma alternativa, na verdade escolhemos suas consequências.

No entanto, na prática real, muitas vezes temos que lidar com uma situação mais complexa, quando a escolha de uma ou outra alternativa determina de forma ambígua as consequências da escolha feita.

No caso de um conjunto discreto de alternativas e resultados de sua escolha, desde que o conjunto de resultados possíveis seja comum a todas as alternativas, podemos supor que diferentes alternativas diferem umas das outras na distribuição de probabilidades de resultados. Essas distribuições de probabilidade, no caso geral, podem depender dos resultados da escolha das alternativas e dos resultados que de fato ocorreram como resultado disso. No caso mais simples, os resultados são igualmente prováveis. Os próprios resultados geralmente têm o significado de ganhos ou perdas e são quantificados.

Se os resultados forem iguais para todas as alternativas, então não há nada a escolher. Se forem diferentes, as alternativas podem ser comparadas introduzindo certas estimativas quantitativas para elas. A variedade de problemas na teoria dos jogos está associada a uma escolha diferente de características numéricas de perdas e ganhos como resultado da escolha de alternativas, diferentes graus de conflito entre as partes que escolhem alternativas, etc.

Considere este tipo de incerteza como incerteza vaga

Qualquer problema de escolha é um objetivo de estreitamento do conjunto de alternativas. Tanto uma descrição formal das alternativas (sua própria lista, uma lista de seus atributos ou parâmetros) quanto uma descrição das regras para sua comparação (critérios, relações) são sempre dadas em termos de uma ou outra escala de medição (mesmo quando aquele que isso não sabe sobre isso).

Sabe-se que todas as escalas são borradas, mas em graus variados. O termo "borrão" refere-se à propriedade das escalas, que consiste no facto de ser sempre possível apresentar duas alternativas distinguíveis, i.e. diferentes em uma escala e indistinguíveis, ou seja, são idênticos, no outro - mais borrados. Quanto menos gradações em uma determinada escala, mais borrada ela é.

Assim, podemos ver claramente as alternativas e ao mesmo tempo classificá-las vagamente, ou seja, ser ambíguo quanto a quais classes pertencem.

Já em seu primeiro trabalho sobre tomada de decisão em uma situação difusa, Bellman e Zadeh apresentaram a ideia de que tanto as metas quanto as restrições devem ser representadas como conjuntos difusos (fuzzy) em um conjunto de alternativas.

Sobre algumas limitações da abordagem de otimização

Em todos os problemas de seleção e métodos de tomada de decisão considerados acima, o problema era encontrar os melhores no conjunto inicial sob determinadas condições, ou seja, alternativas ótimas em certo sentido.

A ideia de otimização é a ideia central da cibernética e entrou firmemente na prática de projetar e operar sistemas técnicos. Ao mesmo tempo, essa ideia precisa ser tratada com cautela quando tentamos transferi-la para a área de gestão de sistemas complexos, grandes e pouco determinados, como, por exemplo, sistemas socioeconômicos.

Há boas razões para esta conclusão. Vamos considerar alguns deles:

1. A solução ótima muitas vezes acaba sendo instável, ou seja, pequenas mudanças nas condições do problema, dados de entrada ou restrições podem levar à seleção de alternativas significativamente diferentes.
2. Os modelos de otimização são desenvolvidos apenas para classes restritas de tarefas bastante simples que nem sempre refletem de forma adequada e sistemática os objetos de controle reais. Na maioria das vezes, os métodos de otimização tornam possível otimizar apenas subsistemas bastante simples e bem descritos de alguns sistemas grandes e complexos, ou seja, permitem apenas otimização local. No entanto, se cada subsistema de algum grande sistema funcionar de forma otimizada, isso não significa que o sistema como um todo também funcionará de forma otimizada. Portanto, a otimização de um subsistema não leva necessariamente ao seu comportamento, que é exigido dele ao otimizar o sistema como um todo. Além disso, às vezes a otimização local pode levar a consequências negativas para o sistema como um todo. Portanto, ao otimizar os subsistemas e o sistema como um todo, é necessário determinar a árvore de metas e submetas e sua prioridade.
3. Muitas vezes, maximizar o critério de otimização de acordo com algum modelo matemático é considerado o objetivo da otimização, mas na realidade o objetivo é otimizar o objeto de controle. Os critérios de otimização e os modelos matemáticos estão sempre relacionados ao objetivo apenas indiretamente, ou seja, mais ou menos adequados, mas sempre aproximados.

Assim, a ideia de otimalidade, que é extremamente frutífera para sistemas que se prestam à formalização matemática adequada, deve ser transferida com cautela para sistemas complexos. É claro que modelos matemáticos que às vezes podem ser propostos para tais sistemas podem ser otimizados. No entanto, deve-se sempre levar em conta a forte simplificação desses modelos, que no caso de sistemas complexos não pode mais ser negligenciada, bem como o fato de o grau de adequação desses modelos no caso de sistemas complexos ser desconhecido. . Portanto, não se sabe qual o significado puramente prático dessa otimização. A alta praticidade da otimização em sistemas técnicos não deve dar origem à ilusão de que ela será tão eficaz na otimização de sistemas complexos. A modelagem matemática significativa de sistemas complexos é muito difícil, aproximada e imprecisa. Quanto mais complexo o sistema, mais cuidadoso deve ser com a ideia de sua otimização.

Portanto, ao desenvolver métodos de controle para sistemas complexos, grandes e fracamente determinados, os autores consideram o principal não apenas a otimalidade da abordagem escolhida do ponto de vista matemático formal, mas também sua adequação ao objetivo e à própria natureza do problema. objeto de controle.

Métodos de seleção de especialistas

No estudo de sistemas complexos, muitas vezes surgem problemas que, por várias razões, não podem ser rigorosamente colocados e resolvidos usando o aparato matemático atualmente desenvolvido. Nestes casos, recorre-se aos serviços de especialistas (analistas de sistemas), cuja experiência e intuição ajudam a reduzir a complexidade do problema.

No entanto, deve-se levar em consideração que os próprios especialistas são sistemas altamente complexos e suas atividades também dependem de muitas condições externas e internas. Portanto, nos métodos de organização de avaliações de especialistas, muita atenção é dada à criação de condições externas e psicológicas favoráveis ​​​​para o trabalho de especialistas.

Os seguintes fatores influenciam o trabalho de um especialista:

• responsabilidade pelo uso dos resultados do exame;
• saber que outros especialistas estão envolvidos;
• disponibilidade de contato de informações entre especialistas;
• relações interpessoais dos especialistas (se houver contato de informações entre eles);
• interesse pessoal do perito nos resultados da avaliação;
• qualidades pessoais dos especialistas (auto-estima, conformidade, vontade, etc.)

A interação entre especialistas pode estimular ou inibir sua atividade. Portanto, em diferentes casos, são utilizados diferentes métodos de exame, que diferem na natureza da interação dos especialistas entre si: pesquisas e questionários anônimos e abertos, reuniões, discussões, jogos de negócios, brainstorming etc.

Existem vários métodos de processamento matemático de opiniões de especialistas. Pede-se aos especialistas que avaliem várias alternativas por um ou por um sistema de indicadores. Além disso, eles são solicitados a avaliar o grau de importância de cada indicador (seu "peso" ou "contribuição"). Aos próprios especialistas também é atribuído um nível de competência correspondente à contribuição de cada um deles para a opinião resultante do grupo.

Um método desenvolvido de trabalhar com especialistas é o método "Delphi". A ideia principal deste método é que a crítica e a argumentação tenham um efeito benéfico sobre o especialista, se sua autoestima não for afetada e forem fornecidas condições que excluam o confronto pessoal.

Deve-se enfatizar que há uma diferença fundamental na natureza do uso de métodos especialistas em sistemas especialistas e no suporte à decisão. Se no primeiro caso, os especialistas são obrigados a formalizar os métodos de tomada de decisão, no segundo - apenas a própria decisão, como tal.

Como os especialistas estão envolvidos na implementação precisamente daquelas funções que atualmente não são fornecidas por sistemas automatizados ou são executadas pior do que por humanos, uma direção promissora no desenvolvimento de sistemas automatizados é a automação máxima dessas funções.

Sistemas automatizados de apoio à decisão

Uma pessoa sempre usou assistentes na tomada de decisões: eles eram simplesmente fornecedores de informações sobre o objeto de controle e consultores (assessores) que oferecem opções para decisões e analisam suas consequências. A pessoa que toma as decisões sempre as tomava em um determinado ambiente de informação: para um comandante militar, este é o quartel-general, para o reitor, o conselho acadêmico, para o ministro, o collegium.

Em nosso tempo, a infraestrutura de informação para tomada de decisão é impensável sem sistemas automatizados para avaliação iterativa de decisões e principalmente sistemas de suporte à decisão (DDS - Decision Support Systems), ou seja, sistemas automatizados que são projetados especificamente para preparar as informações que uma pessoa precisa para tomar uma decisão. O desenvolvimento de sistemas de apoio à decisão é realizado, em particular, no âmbito de um projeto internacional realizado sob os auspícios do Instituto Internacional de Análise de Sistemas Aplicados em Laxenburg (Áustria).

A escolha em situações reais exige a realização de uma série de operações, algumas das quais são realizadas de forma mais eficiente por uma pessoa, e outras por uma máquina. A combinação eficaz de suas vantagens com a compensação simultânea de deficiências é incorporada em sistemas automatizados de suporte à decisão.

Uma pessoa toma decisões melhor do que uma máquina em condições de incerteza, mas para tomar a decisão certa, ela também precisa de informações adequadas (completas e confiáveis) que caracterizem a área de assunto. No entanto, sabe-se que uma pessoa não lida bem com grandes quantidades de informações "cruas" não processadas. Portanto, o papel da máquina no apoio à decisão pode ser realizar a preparação preliminar de informações sobre o objeto de controle e fatores incontroláveis ​​(ambiente), para ajudar a visualizar as consequências de tomar certas decisões, e também apresentar todas essas informações de forma visual. forma conveniente e conveniente para tomar decisões.

Assim, os sistemas automatizados de apoio à decisão compensam as fraquezas de uma pessoa, liberando-a da rotina de processamento preliminar de informações, e fornecendo-lhe um ambiente informacional confortável no qual ela pode mostrar melhor seus pontos fortes. Esses sistemas estão focados não em automatizar as funções do tomador de decisão (e, como resultado, alienar essas funções dele e, portanto, a responsabilidade pelas decisões tomadas, o que geralmente é inaceitável), mas em ajudá-lo a encontrar um boa solução.

Os sistemas vivos, incluindo os humanos, têm sido constantemente confrontados com a tarefa de reconhecimento de padrões desde o seu início. Em particular, as informações provenientes dos órgãos dos sentidos são processadas pelo cérebro, que, por sua vez, classifica as informações, garante a tomada de decisões e, em seguida, usando impulsos eletroquímicos, transmite o sinal necessário ainda mais, por exemplo, para os órgãos do movimento , que implementam as ações necessárias. Então há uma mudança no ambiente, e os fenômenos acima ocorrem novamente. E se você olhar, então cada estágio é acompanhado de reconhecimento.

Com o desenvolvimento da tecnologia computacional, tornou-se possível solucionar uma série de problemas que surgem no processo da vida, para facilitar, agilizar, melhorar a qualidade do resultado. Por exemplo, o funcionamento de vários sistemas de suporte à vida, interação humano-computador, o surgimento de sistemas robóticos, etc. No entanto, notamos que atualmente não é possível fornecer um resultado satisfatório em algumas tarefas (reconhecimento de objetos semelhantes em movimento rápido , texto manuscrito).

Objetivo do trabalho: estudar a história dos sistemas de reconhecimento de padrões.

Indique as mudanças qualitativas ocorridas no campo do reconhecimento de padrões, tanto teóricas quanto técnicas, indicando as razões;

Discutir os métodos e princípios usados ​​na computação;

Dê exemplos de perspectivas que são esperadas no futuro próximo.

1. O que é reconhecimento de padrões?

As primeiras pesquisas com tecnologia computacional seguiram basicamente o esquema clássico de modelagem matemática - modelo matemático, algoritmo e cálculo. Estas eram as tarefas de modelar os processos ocorridos durante as explosões de bombas atômicas, calcular trajetórias balísticas, econômicas e outras aplicações. No entanto, além das ideias clássicas desta série, havia também métodos baseados em uma natureza completamente diferente, e como a prática de resolver alguns problemas mostrou, muitas vezes eles davam melhores resultados do que soluções baseadas em modelos matemáticos supercomplicados. A ideia deles era abandonar o desejo de criar um modelo matemático exaustivo do objeto em estudo (além disso, muitas vezes era praticamente impossível construir modelos adequados), e em vez disso se contentar com a resposta apenas a questões específicas de nosso interesse, e essas respostas devem ser buscadas a partir de considerações comuns a uma ampla classe de problemas. Pesquisas desse tipo incluíam reconhecimento de imagens visuais, previsão de rendimentos, níveis de rios, o problema de distinguir entre aquíferos e aquíferos usando dados geofísicos indiretos, etc. por exemplo, se um objeto pertence a uma das classes pré-fixadas. E os dados iniciais dessas tarefas, via de regra, eram dados na forma de informações fragmentárias sobre os objetos em estudo, por exemplo, na forma de um conjunto de objetos pré-classificados. Do ponto de vista matemático, isso significa que o reconhecimento de padrões (e essa classe de problemas foi nomeada em nosso país) é uma generalização de longo alcance da ideia de extrapolação de funções.

A importância de tal formulação para as ciências técnicas é inquestionável, e isso por si só justifica inúmeros estudos nesta área. No entanto, o problema do reconhecimento de padrões também tem um aspecto mais amplo para as ciências naturais (no entanto, seria estranho se algo tão importante para os sistemas cibernéticos artificiais não fosse importante para os naturais). O contexto dessa ciência incluía organicamente as questões colocadas por filósofos antigos sobre a natureza de nosso conhecimento, nossa capacidade de reconhecer imagens, padrões, situações do mundo ao nosso redor. De fato, praticamente não há dúvida de que os mecanismos para reconhecer as imagens mais simples, como imagens de um predador perigoso ou comida se aproximando, foram formados muito antes do surgimento da linguagem elementar e do aparato lógico formal. E não há dúvida de que tais mecanismos também são suficientemente desenvolvidos em animais superiores, que, em sua atividade vital, também precisam urgentemente da capacidade de distinguir um sistema bastante complexo de sinais da natureza. Assim, na natureza, vemos que o fenômeno do pensamento e da consciência é claramente baseado na capacidade de reconhecer padrões, e o progresso posterior da ciência da inteligência está diretamente relacionado à profundidade da compreensão das leis fundamentais do reconhecimento. Entendendo o fato de que as questões acima vão muito além da definição padrão de reconhecimento de padrões (na literatura inglesa, o termo aprendizado supervisionado é mais comum), também é necessário entender que elas possuem conexões profundas com esse relativamente estreito (mas ainda distante). de esgotado) direção.

Mesmo agora, o reconhecimento de padrões entrou firmemente na vida cotidiana e é um dos conhecimentos mais vitais de um engenheiro moderno. Na medicina, o reconhecimento de padrões ajuda os médicos a fazer diagnósticos mais precisos; nas fábricas, é usado para prever defeitos em lotes de mercadorias. Os sistemas biométricos de identificação pessoal como seu núcleo algorítmico também são baseados nos resultados desta disciplina. O desenvolvimento adicional da inteligência artificial, em particular o design de computadores de quinta geração capazes de comunicação mais direta com uma pessoa em línguas naturais para pessoas e por meio da fala, é impensável sem reconhecimento. Aqui, a robótica, sistemas de controle artificial contendo sistemas de reconhecimento como subsistemas vitais, são de fácil acesso.

É por isso que muita atenção foi dada ao desenvolvimento do reconhecimento de padrões desde o início por especialistas de vários perfis - cibernéticos, neurofisiologistas, psicólogos, matemáticos, economistas etc. Em grande parte por esse motivo, o próprio reconhecimento moderno de padrões se alimenta das ideias dessas disciplinas. Sem pretender ser completo (e é impossível reivindicá-lo em um pequeno ensaio), descreveremos a história do reconhecimento de padrões, ideias-chave.

Definições

Antes de prosseguir para os principais métodos de reconhecimento de padrões, damos algumas definições necessárias.

O reconhecimento de imagens (objetos, sinais, situações, fenômenos ou processos) é a tarefa de identificar um objeto ou determinar qualquer uma de suas propriedades por sua imagem (reconhecimento óptico) ou gravação de áudio (reconhecimento acústico) e outras características.

Um dos básicos é o conceito de conjunto que não possui uma formulação específica. Em um computador, um conjunto é representado por um conjunto de elementos não repetidos do mesmo tipo. A palavra "não repetitivo" significa que algum elemento no conjunto está ou não está lá. O conjunto universal inclui todos os elementos possíveis para o problema a ser resolvido, o conjunto vazio não contém nenhum.

Uma imagem é um agrupamento de classificação no sistema de classificação que une (single) um determinado grupo de objetos de acordo com algum atributo. As imagens têm uma propriedade característica, que se manifesta no fato de que o conhecimento de um número finito de fenômenos do mesmo conjunto permite reconhecer um número arbitrariamente grande de seus representantes. As imagens têm propriedades objetivas características no sentido de que diferentes pessoas que aprendem com diferentes materiais observacionais, em sua maioria, classificam os mesmos objetos da mesma maneira e independentemente uns dos outros. Na formulação clássica do problema de reconhecimento, o conjunto universal é dividido em partes-imagens. Cada mapeamento de qualquer objeto para os órgãos perceptivos do sistema de reconhecimento, independentemente de sua posição em relação a esses órgãos, geralmente é chamado de imagem do objeto, e conjuntos de tais imagens, unidos por algumas propriedades comuns, são imagens.

O método de atribuir um elemento a qualquer imagem é chamado de regra de decisão. Outro conceito importante é a métrica, uma forma de determinar a distância entre os elementos de um conjunto universal. Quanto menor essa distância, mais semelhantes são os objetos (símbolos, sons, etc.) que reconhecemos. Normalmente, os elementos são especificados como um conjunto de números e a métrica é especificada como uma função. A eficiência do programa depende da escolha da representação das imagens e da implementação da métrica, um algoritmo de reconhecimento com diferentes métricas cometerá erros com diferentes frequências.

A aprendizagem é geralmente chamada de processo de desenvolver em algum sistema uma reação particular a grupos de sinais externos idênticos, influenciando repetidamente o sistema de correção externo. Esse ajuste externo no treinamento geralmente é chamado de "incentivo" e "punição". O mecanismo para gerar esse ajuste determina quase completamente o algoritmo de aprendizado. A autoaprendizagem difere da aprendizagem, pois aqui não são relatadas informações adicionais sobre a correção da reação ao sistema.

A adaptação é um processo de alteração dos parâmetros e da estrutura do sistema, e possivelmente também de ações de controle, com base em informações atuais, a fim de alcançar um determinado estado do sistema com incerteza inicial e mudanças nas condições de operação.

A aprendizagem é um processo, pelo qual o sistema adquire gradualmente a capacidade de responder com as reações necessárias a determinados conjuntos de influências externas, e a adaptação é o ajuste dos parâmetros e da estrutura do sistema para atingir a qualidade necessária de controle em condições de mudanças contínuas nas condições externas.

Exemplos de tarefas de reconhecimento de padrões: - Reconhecimento de letras;

E sinais. Essas tarefas são resolvidas com bastante frequência, por exemplo, ao atravessar ou dirigir uma rua nos semáforos. Reconhecer a cor de um semáforo aceso e conhecer as regras da estrada permite que você tome a decisão certa sobre atravessar ou não a rua no momento.

No processo de evolução biológica, muitos animais resolveram problemas com a ajuda de aparelhos visuais e auditivos. reconhecimento de padrões bom o bastante. Criação de sistemas artificiais reconhecimento de padrões continua a ser um problema teórico e técnico difícil. A necessidade de tal reconhecimento surge em uma variedade de áreas - desde assuntos militares e sistemas de segurança até a digitalização de todos os tipos de sinais analógicos.

Tradicionalmente, as tarefas de reconhecimento de imagem estão incluídas no escopo das tarefas de inteligência artificial.

Direções no reconhecimento de padrões

Existem duas direções principais:

• O estudo das habilidades de reconhecimento dos seres vivos, sua explicação e modelagem;
• Desenvolvimento da teoria e métodos para a construção de dispositivos destinados a resolver problemas individuais em problemas aplicados.

Declaração formal do problema

O reconhecimento de padrões é a atribuição de dados iniciais a uma determinada classe, destacando características essenciais que caracterizam esses dados da massa total de dados não essenciais.

Ao definir problemas de reconhecimento, eles tentam usar a linguagem matemática, tentando, ao contrário da teoria das redes neurais artificiais, onde a base é obter um resultado por experimento, substituir o experimento por raciocínio lógico e provas matemáticas.

Na maioria das vezes, imagens monocromáticas são consideradas em problemas de reconhecimento de padrões, o que possibilita considerar uma imagem como uma função em um plano. Se considerarmos um ponto situado em um plano T, onde a função x(x,y) expressa em cada ponto da imagem sua característica - brilho, transparência, densidade óptica, então tal função é um registro formal da imagem.

O conjunto de todas as funções possíveis x(x,y) na superfície T- existe um modelo do conjunto de todas as imagens X. Apresentando o conceito semelhanças entre as imagens, você pode definir a tarefa de reconhecimento. A forma específica de tal cenário depende fortemente dos estágios subsequentes de reconhecimento de acordo com uma ou outra abordagem.

Métodos de reconhecimento de padrões

Para reconhecimento óptico de imagem, você pode aplicar o método de iteração sobre a aparência de um objeto em diferentes ângulos, escalas, deslocamentos, etc. Para letras, você precisa iterar sobre a fonte, propriedades da fonte etc.

A segunda abordagem é encontrar o contorno do objeto e examinar suas propriedades (conectividade, presença de cantos, etc.)

Outra abordagem é usar redes neurais artificiais. Esse método requer um grande número de exemplos da tarefa de reconhecimento (com respostas corretas) ou uma estrutura de rede neural especial que leva em consideração as especificidades dessa tarefa.

Perceptron como um método de reconhecimento de padrões

F. Rosenblatt, introduzindo o conceito de um modelo cerebral, cuja tarefa é mostrar como fenômenos psicológicos podem surgir em algum sistema físico, cuja estrutura e propriedades funcionais são conhecidas - descreveu o mais simples experimentos de discriminação. Esses experimentos estão inteiramente relacionados a métodos de reconhecimento de padrões, mas diferem pelo fato de o algoritmo de solução não ser determinístico.

O experimento mais simples, com base no qual é possível obter informações psicologicamente significativas sobre um determinado sistema, resume-se ao fato de que o modelo é apresentado a dois estímulos diferentes e é obrigado a responder a eles de maneiras diferentes. O objetivo de tal experimento pode ser estudar a possibilidade de sua discriminação espontânea pelo sistema na ausência de intervenção do experimentador, ou, inversamente, estudar a discriminação forçada, na qual o experimentador procura ensinar o sistema a realizar o experimento. classificação exigida.

Em um experimento de aprendizado, um perceptron geralmente é apresentado com uma certa sequência de imagens, que inclui representantes de cada uma das classes a serem distinguidas. De acordo com alguma regra de modificação de memória, a escolha correta da reação é reforçada. Em seguida, o estímulo de controle é apresentado ao perceptron e a probabilidade de obter a resposta correta para estímulos dessa classe é determinada. Dependendo se o estímulo de controle selecionado corresponde ou não a uma das imagens que foram usadas na sequência de treinamento, são obtidos resultados diferentes:

• 1. Se o estímulo de controle não coincide com nenhum dos estímulos de aprendizagem, então o experimento está associado não apenas a pura discriminação, mas também inclui elementos generalizações.
• 2. Se o estímulo de controle excita um determinado conjunto de elementos sensoriais que são completamente diferentes daqueles que foram ativados sob a influência de estímulos da mesma classe apresentados anteriormente, então o experimento é um estudo pura generalização .

Os perceptrons não têm a capacidade de generalização pura, mas funcionam satisfatoriamente em experimentos de discriminação, especialmente se o estímulo de controle combina o suficiente com um dos padrões sobre os quais o perceptron já acumulou alguma experiência.

Exemplos de problemas de reconhecimento de padrões

• Reconhecimento de letras.
• Reconhecimento de código de barras.
• Reconhecimento de placas.
• Reconhecimento facial.
• Reconhecimento de fala.
• Reconhecimento de imagem.
• Reconhecimento de áreas locais da crosta terrestre em que se encontram depósitos minerais.

Programas de reconhecimento de padrões

Veja também

Notas

Links

• Yuri Lifshits. Curso "Problemas Modernos de Informática Teórica" ​​- aulas sobre métodos estatísticos de reconhecimento de padrões, reconhecimento facial, classificação de textos
• Journal of Pattern Recognition Research (Journal of Pattern Recognition Research)

Literatura

• David A. Forsyth, Jean Pons Visão por computador. Abordagem Moderna = Visão Computacional: Uma Abordagem Moderna. - M.: "Williams", 2004. - S. 928. - ISBN 0-13-085198-1
• George Stockman, Linda Shapiro Visão por computador = Visão por computador. - M.: Binom. Laboratório do Conhecimento, 2006. - S. 752. - ISBN 5947743841

• A. L. Gorelik, V. A. Skripkin, Métodos de reconhecimento, M.: Escola superior, 1989.
• Sh.-K. Cheng, Princípios de design de sistemas de informação visual, M.: Mir, 1994.

Fundação Wikimedia. 2010.

- em tecnologia, uma direção científica e técnica associada ao desenvolvimento de métodos e à construção de sistemas (inclusive com base em um computador) para estabelecer a pertença de um determinado objeto (objeto, processo, fenômeno, situação, sinal) a um do pré... ... Grande Dicionário Enciclopédico

Uma das novas regiões cibernética. O conteúdo da teoria de R. sobre. é a extrapolação das propriedades de objetos (imagens) pertencentes a várias classes para objetos que estão próximos a eles em algum sentido. Normalmente, ao ensinar um autômato R. sobre. há ... ... Enciclopédia Geológica

Inglês reconhecimento, imagem; Alemão Gestalt alterkennung. Ramo da cibernética matemática que desenvolve princípios e métodos para classificar e identificar objetos descritos por um conjunto finito de características que os caracterizam. Antinazi. Enciclopédia ... ... Enciclopédia de Sociologia

Reconhecimento de padrões- método de estudar objetos complexos com a ajuda de um computador; consiste na seleção de características e no desenvolvimento de algoritmos e programas que permitem aos computadores classificar automaticamente os objetos de acordo com essas características. Por exemplo, para determinar qual ... ... Dicionário Econômico e Matemático

- (técnico), uma direção científica e técnica associada ao desenvolvimento de métodos e à construção de sistemas (incluindo os baseados em computador) para estabelecer a pertença de um objeto (sujeito, processo, fenômeno, situação, sinal) a um dos pré... ... dicionário enciclopédico

RECONHECIMENTO DE PADRÕES- uma seção de cibernética matemática que desenvolve métodos para classificar, bem como identificar objetos, fenômenos, processos, sinais, situações de todos aqueles objetos que podem ser descritos por um conjunto finito de certas características ou propriedades, ... ... enciclopédia sociológica russa

reconhecimento de padrões- Reconhecimento de 160 padrões: Identificação de representações e configurações de formulários usando meios automáticos

• tutorial

Por muito tempo eu quis escrever um artigo geral contendo os fundamentos do Reconhecimento de Imagem, uma espécie de guia sobre métodos básicos, dizendo quando aplicá-los, quais tarefas eles resolvem, o que pode ser feito à noite de joelhos e o que é melhor não pensar sem ter uma equipe de pessoas em 20.

Eu tenho escrito alguns artigos sobre Reconhecimento Óptico há muito tempo, então algumas vezes por mês várias pessoas me escrevem com perguntas sobre esse tópico. Às vezes você tem a sensação de que vive com eles em mundos diferentes. Por um lado, você entende que uma pessoa é provavelmente um profissional em um tópico relacionado, mas sabe muito pouco sobre métodos de reconhecimento óptico. E o mais chato é que ele tenta aplicar um método de um campo de conhecimento próximo, o que é lógico, mas não funciona completamente em Reconhecimento de Imagem, mas não entende isso e fica muito ofendido se começar a lhe contar algo do muito básico. E considerando que contar desde o básico é muito tempo, que muitas vezes não existe, fica ainda mais triste.

Este artigo foi projetado para que uma pessoa que nunca lidou com métodos de reconhecimento de imagem possa, em 10 a 15 minutos, criar em sua cabeça uma certa imagem básica do mundo correspondente ao tópico e entender em que direção ele deve cavar. Muitos dos métodos descritos aqui são aplicáveis ​​ao processamento de radar e áudio.
Vou começar com alguns princípios que sempre começamos a dizer a um cliente em potencial ou a uma pessoa que deseja começar a fazer Reconhecimento Óptico:

• Ao resolver um problema, sempre parta do mais simples. É muito mais fácil pendurar uma etiqueta laranja em uma pessoa do que seguir uma pessoa, destacando-a em cascatas. É muito mais fácil pegar uma câmera com uma resolução mais alta do que desenvolver um algoritmo de super-resolução.
• Uma declaração de problema estrita em métodos de reconhecimento óptico é ordens de magnitude mais importante do que em problemas de programação de sistema: uma palavra extra no TK pode adicionar 50% do trabalho.
• Em problemas de reconhecimento, não há soluções universais. Você não pode fazer um algoritmo que simplesmente "reconheça qualquer inscrição". Uma placa na rua e uma folha de texto são objetos fundamentalmente diferentes. Provavelmente é possível fazer um algoritmo geral (aqui está um bom exemplo do Google), mas isso exigirá muito trabalho de uma grande equipe e consistirá em dezenas de sub-rotinas diferentes.
• OpenCV é a bíblia, que tem muitos métodos e com a qual você pode resolver 50% do volume de quase qualquer problema, mas OpenCV é apenas uma pequena parte do que pode ser feito na realidade. Em um estudo, foi escrito nas conclusões: "O problema não é resolvido pelos métodos OpenCV, portanto, é insolúvel". Tente evitar isso, não seja preguiçoso e avalie sobriamente a tarefa atual sempre do zero, sem usar modelos OpenCV.

É muito difícil dar algum tipo de conselho universal, ou dizer como criar algum tipo de estrutura em torno da qual você possa construir uma solução para problemas arbitrários de visão computacional. O objetivo deste artigo é estruturar o que pode ser usado. Vou tentar dividir os métodos existentes em três grupos. O primeiro grupo é a pré-filtragem e preparação da imagem. O segundo grupo é o processamento lógico dos resultados da filtragem. O terceiro grupo são algoritmos de tomada de decisão baseados em processamento lógico. As fronteiras entre os grupos são muito arbitrárias. Para resolver um problema, nem sempre é necessário aplicar métodos de todos os grupos; às vezes dois são suficientes, às vezes até um.

A lista de métodos aqui apresentada não está completa. Proponho adicionar nos comentários métodos críticos que não escrevi e atribuir 2-3 palavras de acompanhamento a cada um.

Parte 1. Filtragem

Neste grupo, coloquei métodos que permitem selecionar áreas de interesse em imagens sem analisá-las. A maioria desses métodos aplica algum tipo de transformação uniforme em todos os pontos da imagem. No nível de filtragem, a imagem não é analisada, mas os pontos que são filtrados podem ser considerados como áreas com características especiais.

Binarização de limite, seleção de área de histograma

A transformação mais simples é a binarização da imagem pelo limiar. Para imagens RGB e em tons de cinza, o limite é o valor da cor. Existem problemas ideais em que tal transformação é suficiente. Suponha que você queira selecionar itens automaticamente em uma folha de papel branca:




A escolha do limiar pelo qual a binarização ocorre determina em grande parte o próprio processo de binarização. Neste caso, a imagem foi binarizada pela cor média. Normalmente, a binarização é feita com um algoritmo que seleciona de forma adaptativa um limite. Tal algoritmo pode ser a escolha de expectativa ou modo. E você pode escolher o maior pico do histograma.

A binarização pode dar resultados muito interessantes ao trabalhar com histogramas, incluindo a situação se considerarmos uma imagem não em RGB, mas em HSV. Por exemplo, segmente as cores de interesse. Com base neste princípio, é possível construir um detector de etiquetas e um detector de pele humana.

Filtragem clássica: Fourier, LPF, HPF

Métodos clássicos de filtragem de radar e processamento de sinal podem ser aplicados com sucesso em uma variedade de tarefas de reconhecimento de padrões. O método tradicional em radar, que quase nunca é utilizado em imagens em sua forma pura, é a transformada de Fourier (mais especificamente, a FFT). Uma das poucas exceções em que a transformada de Fourier 1D é usada é a compressão de imagem. Para análise de imagem, uma transformação unidimensional geralmente não é suficiente, você precisa usar uma transformação bidimensional muito mais intensiva em recursos.

Poucas pessoas realmente o calculam, geralmente é muito mais rápido e fácil usar a convolução da região de interesse com um filtro pronto afiado para frequências altas (HPF) ou baixas (LPF). Tal método, é claro, não permite análise de espectro, mas em uma tarefa específica de processamento de vídeo, geralmente não é uma análise que é necessária, mas um resultado.


Os exemplos mais simples de filtros que enfatizam baixas frequências (filtro Gaussiano) e altas frequências (filtro Gabor).
Para cada ponto de imagem, uma janela é selecionada e multiplicada com um filtro de mesmo tamanho. O resultado de tal convolução é o novo valor do ponto. Ao implementar LPF e HPF, são obtidas imagens desse tipo:

Wavelets

Mas e se usarmos alguma função característica arbitrária para convolução com o sinal? Em seguida, ele será chamado de "Transformação Wavelet". Essa definição de wavelets não está correta, mas tradicionalmente, em muitas equipes, a análise de wavelets é a busca de um padrão arbitrário em uma imagem usando convolução com um modelo desse padrão. Existe um conjunto de funções clássicas usadas na análise de wavelets. Estas incluem a wavelet de Haar, a wavelet de Morlet, a wavelet do chapéu mexicano e assim por diante. As primitivas de Haar, sobre as quais havia vários de meus artigos anteriores ( , ), referem-se a tais funções para um espaço bidimensional.


Acima estão 4 exemplos de wavelets clássicas. Wavelet 3D Haar, wavelet 2D Meyer, wavelet Mexican Hat, wavelet Daubechies. Um bom exemplo de uso da interpretação estendida de wavelets é o problema de encontrar um brilho no olho, para o qual o próprio brilho é uma wavelet:

As wavelets clássicas são geralmente usadas para compressão de imagens ou para sua classificação (a ser descrita abaixo).

Correlação

Depois de uma interpretação tão livre das wavelets da minha parte, vale a pena mencionar a correlação real subjacente a elas. Ao filtrar imagens, esta é uma ferramenta indispensável. Uma aplicação clássica é a correlação de fluxo de vídeo para encontrar deslocamentos ou fluxos ópticos. O detector de deslocamento mais simples também é, em certo sentido, um correlacionador de diferenças. Onde as imagens não se correlacionam, houve movimento.

Filtragem de função

Uma classe interessante de filtros são as funções de filtragem. Estes são filtros puramente matemáticos que permitem detectar uma função matemática simples em uma imagem (linha, parábola, círculo). É construída uma imagem acumulativa, na qual para cada ponto da imagem original é desenhado um conjunto de funções que a geram. A transformação mais clássica é a transformação de Hough para linhas. Nesta transformação, para cada ponto (x;y), é desenhado um conjunto de pontos (a;b) da reta y=ax+b, para os quais a igualdade é verdadeira. Obtenha belas fotos:


(o primeiro mais para quem for o primeiro a encontrar uma pegadinha na imagem e tal definição e explicá-la, o segundo mais para quem for o primeiro a dizer o que é mostrado aqui)
A transformação de Hough permite encontrar quaisquer funções parametrizáveis. Por exemplo, círculos. Há uma transformação modificada que permite pesquisar qualquer forma. Essa transformação gosta muito dos matemáticos. Mas ao processar imagens, infelizmente, nem sempre funciona. Velocidade muito lenta, sensibilidade muito alta para a qualidade da binarização. Mesmo em situações ideais, eu preferia me virar com outros métodos.
A contrapartida da transformada de Hough para linhas é a transformada de Radon. É calculado através da FFT, que dá um ganho de desempenho em uma situação onde há muitos pontos. Além disso, pode ser aplicado a uma imagem não binarizada.

Filtragem de contorno

Uma classe separada de filtros é a filtragem de borda e contorno. Os caminhos são muito úteis quando queremos passar do trabalho com uma imagem para o trabalho com objetos nessa imagem. Quando um objeto é bastante complexo, mas bem distinto, muitas vezes a única maneira de trabalhar com ele é selecionar seus contornos. Existem vários algoritmos que resolvem o problema de filtragem de contorno:

O mais usado é o Kenny, que funciona bem e cuja implementação é em OpenCV (o Sobel também está lá, mas ele procura contornos piores).

Outros filtros

Acima estão os filtros, cujas modificações ajudam a resolver 80-90% das tarefas. Mas além deles, existem filtros mais raros usados ​​em tarefas locais. Existem dezenas desses filtros, não vou listar todos eles. De interesse são os filtros iterativos (por exemplo, um modelo de aparência ativa), bem como as transformadas de ridgelet e curvlet, que são uma liga de filtragem de wavelet clássica e análise no campo de transformada de radônio. A transformação Beamlet funciona lindamente na borda da transformação wavelet e da análise lógica, permitindo destacar os contornos:

Mas essas transformações são muito específicas e adaptadas para tarefas raras.

Parte 2. Processamento lógico de resultados de filtragem

A filtragem fornece um conjunto de dados adequado para processamento. Mas muitas vezes você não pode simplesmente pegar e usar esses dados sem processá-los. Nesta seção, haverá vários métodos clássicos que permitem ir da imagem às propriedades dos objetos, ou aos próprios objetos.

Morfologia

A transição da filtragem para a lógica, na minha opinião, são os métodos da morfologia matemática ( , , ). Na verdade, essas são as operações mais simples de aumentar e erodir imagens binárias. Esses métodos permitem remover o ruído de uma imagem binária aumentando ou diminuindo os elementos disponíveis. Com base na morfologia matemática, existem algoritmos de contorno, mas geralmente eles usam algum tipo de algoritmo híbrido ou algoritmos em conjunto.

análise de contorno

Na seção sobre filtragem, os algoritmos para obtenção de limites já foram mencionados. Os limites resultantes são simplesmente convertidos em contornos. Para o algoritmo Canny isso acontece automaticamente, para outros algoritmos é necessária uma binarização adicional. Você pode obter um contorno para um algoritmo binário, por exemplo, com o algoritmo do besouro.
O contorno é uma característica única de um objeto. Muitas vezes, isso permite identificar o objeto ao longo do contorno. Existe um poderoso aparato matemático que permite que você faça isso. O aparato é chamado de análise de contorno ( , ).

Para ser sincero, nunca consegui aplicar a análise de contorno em problemas reais. São necessárias condições muito ideais. Ou não há fronteira, ou há muito barulho. Mas, se você precisa reconhecer algo em condições ideais, a análise de contorno é uma ótima opção. Funciona muito rápido, matemática bonita e lógica compreensível.

Pontos singulares

Pontos-chave são características exclusivas de um objeto que permitem que o objeto seja associado a si mesmo ou a classes de objetos semelhantes. Existem dezenas de maneiras de selecionar esses pontos. Alguns métodos destacam pontos especiais em quadros vizinhos, alguns após um longo período de tempo e quando a iluminação muda, alguns permitem que você encontre pontos especiais que permanecem assim mesmo quando o objeto gira. Vamos começar com métodos que nos permitem encontrar pontos especiais que não são tão estáveis, mas são calculados rapidamente, e então iremos em complexidade crescente:
Primeira série. Pontos singulares estáveis ​​por segundos. Esses pontos são usados ​​para guiar um objeto entre quadros de vídeo adjacentes ou para convergir imagens de câmeras vizinhas. Esses pontos incluem máximos locais da imagem, cantos na imagem (o melhor dos detectores, talvez, o detector Haris), pontos em que os máximos de dispersão são atingidos, certos gradientes, etc.
Segunda classe. Pontos singulares que são estáveis ​​ao mudar de iluminação e pequenos movimentos do objeto. Esses pontos servem principalmente para treinamento e classificação subsequente de tipos de objetos. Por exemplo, um classificador de pedestres ou um classificador de face é o produto de um sistema construído sobre esses pontos. Algumas das wavelets mencionadas anteriormente podem ser a base para tais pontos. Por exemplo, primitivos Haar, pesquisa de brilho, pesquisa de outros recursos específicos. Esses pontos incluem pontos encontrados pelo método de histogramas de gradientes direcionais (HOG).
Terceira classe. pontos estáveis. Conheço apenas dois métodos que dão total estabilidade e suas modificações. Estes são SURF e SIFT. Eles permitem que você encontre pontos-chave mesmo quando você gira a imagem. O cálculo de tais pontos leva mais tempo do que outros métodos, mas por um tempo bastante limitado. Infelizmente, esses métodos são patenteados. Embora, na Rússia, seja impossível patentear algoritmos, use-o para o mercado doméstico.

Parte 3. Treinamento

A terceira parte da história será dedicada a métodos que não trabalham diretamente com a imagem, mas que permitem tomar decisões. Basicamente, esses são vários métodos de aprendizado de máquina e tomada de decisão. Recentemente, Yandyks postou um curso sobre esse tópico no Habr, há uma seleção muito boa lá. Aqui está na versão em texto. Para um estudo sério do assunto, recomendo fortemente que você dê uma olhada neles. Aqui tentarei identificar vários métodos básicos usados ​​especificamente no reconhecimento de padrões.
Em 80% das situações, a essência da aprendizagem no problema de reconhecimento é a seguinte:
Existe uma amostra de teste na qual existem várias classes de objetos. Que seja a presença/ausência de uma pessoa na foto. Para cada imagem, há um conjunto de feições que foram destacadas por alguma feição, seja Haar, HOG, SURF ou alguma wavelet. O algoritmo de aprendizado deve construir tal modelo, segundo o qual será capaz de analisar a nova imagem e decidir qual dos objetos está na imagem.
Como isso é feito? Cada uma das imagens de teste é um ponto no espaço de recursos. Suas coordenadas são o peso de cada recurso na imagem. Sejam nossos sinais: “A presença de olhos”, “A presença de um nariz”, “A presença de duas mãos”, “A presença de ouvidos”, etc. Vamos alocar todos esses sinais com os detectores que temos, que são treinados em partes do corpo semelhantes ao humano. Para uma pessoa em tal espaço, o ponto correto será . Para o macaco, ponto para o cavalo. O classificador é treinado em uma amostra de exemplos. Mas nem todas as fotografias mostravam mãos, outras não tinham olhos e na terceira o macaco tinha nariz humano devido a um erro de classificação. O classificador humano treinável automaticamente divide o espaço de feição de forma a dizer: se a primeira feição estiver no intervalo 0,5 Em essência, o objetivo do classificador é desenhar no espaço de características as áreas características dos objetos de classificação. Assim será a aproximação sucessiva da resposta para um dos classificadores (AdaBoost) no espaço bidimensional:


Existem muitos classificadores. Cada um deles funciona melhor em algumas de suas tarefas. A tarefa de selecionar um classificador para uma tarefa específica é em grande parte uma arte. Aqui estão algumas fotos legais sobre o tema.

Caso simples, separação unidimensional

Vamos dar um exemplo do caso mais simples de classificação, quando o espaço de características é unidimensional, e precisamos separar 2 classes. A situação ocorre com mais frequência do que parece: por exemplo, quando você precisa distinguir dois sinais ou comparar um padrão com uma amostra. Digamos que temos uma amostra de treinamento. Neste caso, obtém-se uma imagem, onde o eixo X será uma medida de similaridade e o eixo Y será o número de eventos com tal medida. Quando o objeto desejado é semelhante a si mesmo, uma Gaussiana esquerda é obtida. Quando não é semelhante - certo. O valor X=0,4 separa as amostras para que uma decisão errada minimize a probabilidade de tomar qualquer decisão errada. É a busca de tal separador que é a tarefa da classificação.


Pequena nota. O critério que minimiza o erro nem sempre será ótimo. O gráfico a seguir é um gráfico de um sistema de reconhecimento de íris real. Para tal sistema, o critério é escolhido de forma a minimizar a probabilidade de falsa admissão de um estranho ao objeto. Tal probabilidade é chamada de "erro do primeiro tipo", "probabilidade de alarme falso", "falso positivo". Na literatura inglesa "False Access Rate".
) AdaBusta é um dos classificadores mais comuns. Por exemplo, a cascata Haar é construída sobre ela. Geralmente usado quando a classificação binária é necessária, mas nada impede o ensino para mais aulas.
SVM ( , , , ) Um dos classificadores mais poderosos com muitas implementações. Em princípio, nas tarefas de aprendizagem que encontrei, funcionou de forma semelhante ao adabusta. É considerado bastante rápido, mas seu treinamento é mais difícil que o do Adabústa e requer a escolha do kernel correto.

Há também redes neurais e regressão. Mas para classificá-los brevemente e mostrar como eles diferem, é necessário um artigo muito maior do que este.
________________________________________________
Espero ter conseguido dar uma rápida visão geral dos métodos usados ​​sem mergulhar na matemática e na descrição. Talvez isso ajude alguém. Embora, é claro, o artigo esteja incompleto e não haja uma palavra sobre trabalhar com imagens estéreo, ou sobre LSM com o filtro de Kalman, ou sobre a abordagem bayesiana adaptativa.
Se você gostar do artigo, tentarei fazer a segunda parte com uma seleção de exemplos de como os problemas existentes de ImageRecognition são resolvidos.

E finalmente

O que ler?
1) Uma vez gostei muito do livro "Digital Image Processing" de B. Yana, que é escrito de forma simples e clara, mas ao mesmo tempo quase toda a matemática é dada. Bom para se familiarizar com os métodos existentes.
2) O clássico do gênero é R Gonzalez, R. Woods "Digital Image Processing". Por alguma razão, foi mais difícil para mim do que o primeiro. Muito menos matemática, mas mais métodos e imagens.
3) “Processamento e análise de imagens em problemas de visão de máquina” - escrito com base em um curso ministrado em um dos departamentos da PhysTech. Muitos métodos e sua descrição detalhada. Mas, na minha opinião, o livro tem dois grandes pontos negativos: o livro é fortemente focado no pacote de software que está anexado a ele, no livro muitas vezes a descrição de um método simples se transforma em selva matemática, da qual é difícil tirar o diagrama estrutural do método. Mas os autores criaram um site conveniente, onde quase todo o conteúdo é apresentado - wiki.technicalvision.ru Adicionar tags