BR102014023780B1 - Método para classificação multiclasse em cenários abertos e usos do mesmo - Google Patents

Abstract

MÉTODO PARA CLASSIFICAÇÃO MULTICLASSE EM CENÁRIOS ABERTOS E USOS DE MESMO. O método proposto é utilizado para classificação em cenários abertos, em que muitas vezes não é possível obter previamente os dados de treinamento para todas as classes possíveis que podem surgi na fase de teste. Durante a fase de teste, as amostras de testes pertencentes a uma das classes utilizadas na fase de treinamento devem ser classificadas com base em uma razão emtre medidas de similaridade, como classe conhecida correta e as amostras de teste pertencentes a qualquer outra classe devem ser rejeitadas e classificadas como desconhecidas.

Description

Campo da Invenção

[0001] O método proposto é utilizado para classificação em cenários abertos, em que muitas vezes não é possível obter previamente os dados de treinamento para todas as classes possíveis que podem surgir na fase de teste (que corresponde ao uso do método proposto). Durante a fase de teste, as amostras de teste pertencentes a uma das classes utilizadas na fase de treinamento devem ser classificadas como classe conhecida correta e as amostras de teste pertencentes a qualquer outra classe devem ser rejeitadas e classificadas como desconhecidas.

[0002] Em comparação com as soluções existentes, a presente invenção agrega valor às soluções/produtos ao possibilitar um desempenho superior em sistemas de classificação e reconhecimento, tais como: reconhecimento de impressões digitais, reconhecimento de face, reconhecimento de voz, reconhecimento de objetos, reconhecimento de cena, reconhecimento de caracteres, reconhecimento de ações, classificação de imagens obtidas por sensoriamento remoto e outras aplicações gerais de reconhecimento de padrões. Aplicações médicas também podem se beneficiar com a presente invenção, tendo em vista que grande parte dos casos médicos reais deve lidar com classes desconhecidas (por exemplo: um novo tipo de câncer, uma perspectiva de imagem de ultrassom do coração que não interessa ao médico naquele caso específico, tipos ainda desconhecidos de doença, etc.).

Antecedentes da Invenção

[0003] Um método conhecido no estado da técnica é o classificador Optimum-Path Forest (OPF), que é um classificador baseado em grafos que foi desenvolvido como uma generalização de outro método, Image Forest Transform (IFT), e é inerentemente multiclasse e independente de parametrização. O método OPF é similar ao conhecido método K-Nearest Neighbors (KNN). O OPF não faz nenhuma suposição sobre a forma das classes e suporta certo grau de intersecção/sobreposição entre as classes. OPF tem apresentado bons resultados em muitos problemas de classificação. Observe-se que o método OPF é inerentemente fechado, ou seja, uma amostra de teste sempre será classificada como uma das classes treinadas.

[0004] Outro método conhecido no estado da técnica é o tradicional classificador binário Support Vector Machines (SVM), que pode atribuir uma amostra de teste a uma determinada classe mesmo que a amostra de teste seja muito diferente das amostras de treinamento dessa classe. SVM define “semiespaços” e não verifica quão longe a amostra de teste está das amostras de treinamento. Essa forte generalização pode não ser útil no cenário aberto; provavelmente a amostra de teste distante do hiperplano deveria ser classificada como desconhecida, ao invés de uma das classes conhecidas. Portanto, SVM pode ser considerado como um classificador binário fechado, ou seja, para o cenário fechado. Entretanto, a abordagem um-contra-todos aplicada no SVM gera um classificador multiclasse (MCSVM) que pode ser considerado apropriado para o cenário aberto.

[0005] O documento de patente JP 2993826 B2, intitulado “Method and Device for Recognizing Signal and Learning Method and Device of Signal Recognizing Device”, publicado em 27 de dezembro de 1999, descreve um método de reconhecimento que trata o cenário aberto de maneira trivial: simplesmente define um limiar na saída da classificação. Por exemplo, o estudo de Phillips et al. (P. J. Phillips, P. Grother, R. Micheals, “Evaluation methods in face recognition”, em: S. Z. Li, A. K. Jain (Eds.), Handbook of Face Recognition, Springer, 2011, pp. 551-574) também utiliza a abordagem de definir um limiar sobre a “medida de similaridade” para classificar como desconhecido. Entretanto, essa abordagem possui desvantagens, como a degradação de desempenho considerando a dificuldade de estabelecer/computar medidas de similaridade em espaço de características de alta dimensionalidade. O método proposto na presente invenção define um limite sobre a “razão de medidas de similaridade”, que é diferente e vantajoso em comparação com o limiar sobre a “medida de similaridade” (proposta em JP 2993826 B2, e que é a abordagem conhecida mais usada para tratar problemas de classificação de cenário aberto), como será demonstrado ao longo desse documento. Outra diferença é que a solução proposta no documento JP 2993826 B2 permite atualizar o “limiar de rejeição” e outros parâmetros, enquanto o método da presente invenção obtém o limiar sobre a razão das medidas de similaridade e esse limiar não será mais atualizado durante a fase de teste.

[0006] O documento de patente US 2013/0144937 A1, intitulado “Apparatus and Method for Sharing User’s Emotion”, publicado em 06 de junho de 2013, descreve um método de classificação para o cenário fechado. Diferentemente do método proposto na presente invenção, o documento US 2013/0144937 A1 não propõe um método de reconhecimento para cenário aberto e não usa a razão entre medidas de similaridade da classificação. Uma eventual proximidade com o método proposto na presente invenção está no fato de que o método do documento US 2013/0144937 A1 usa uma “taxa de emoção” baseada em dois “estados emocionais” (conforme a reivindicação 1 de US 2013/0144937 A1). Mas o “estado emocional” revelado no documento US 2013/0144937 A1 não é o mesmo que a “razão de medidas de similaridade” do método proposto na presente invenção. De acordo com a Figura 2, reivindicação 1 e os parágrafos [0056]- [0058] do relatório descritivo de US 2013/0144937 A1, fica claro que a “taxa de emoção” é usada para dar uma resposta para o usuário com um grau (taxa) dentro de uma faixa de possíveis estados emocionais, ou seja, a “taxa de emoção” não é utilizada para a tarefa de reconhecimento. O documento US 2013/0144937 A1 não menciona ou sugere uma “razão” ou comparação entre diferentes medidas/pontos de classificação com o propósito de automaticamente aprender o relacionamento entre as classes conhecidas para eliminar aquelas amostras que se caracterizam como desconhecidas durante a fase de teste, conforme proposto no método da presente invenção.

[0007] Os próximos quatro documentos de patente US 7,308,133 B2, US 8,306,818 B2, US 8,515,758 B2 e KR 2013/0006030 A, não propõem métodos de reconhecimento em cenário aberto; ao contrário da presente invenção, visam propor soluções para problemas de classificação/reconhecimento em cenário fechado.

[0008] O documento de patente US 7,308,133 B2, intitulado “System and Method of Face Recognition Using Proportions of Learned Model”, publicado em 11 de dezembro de 2007, propõe um sistema e método para reconhecimento de face usando proporções do modelo aprendido. Trata-se de um classificador para classificar múltiplos perfis de indivíduos adicionalmente à face frontal. Com base na imagem usada na fase de teste, a matéria revelada do documento US 7,308,133 B2 gera diferentes versões (proporções) daquela imagem para comparação com as imagens de treinamento. Um esquema de votação, em que cada parte da imagem gera um voto, é usado para decidir a classe da imagem de teste. Mas não é mencionado como são tratados os casos em que a imagem de teste não pertence a qualquer uma das classes de treinamento (ou seja, lida apenas com cenário fechado). O termo “desconhecido” usado no documento US 7,308,133 B2 refere-se à amostra que aparece durante a fase de teste em que sua classe não é conhecida antes da classificação ser feita, mas o documento US 7,308,133 B2 assume que a amostra de teste pertence a pelo menos uma das classes de treinamento e será classificada como tal. Diferentemente, no contexto da presente invenção o termo “desconhecido” é usado para se referir às amostras de teste que não pertencem a qualquer uma das classes de treinamento. Além disso, em contraste com a presente invenção, o documento US 7,308,133 B2 não propõe um método de reconhecimento para o cenário aberto e não usa a razão sobre as “medidas de similaridade” para classificação.

[0009] O documento de patente US 8,306,818 B2, intitulado “Discriminative Training of Language Models Text and Speech Classification”, publicado em 06 de novembro de 2012, descreve um classificador estatístico para o problema específico de classificação de voz e texto. Esse classificador não realiza o reconhecimento em cenário aberto, conforme pode ser observado na Fig. 4 do documento US 8,306,818 B2. Na verdade, a amostra de teste é atribuída à “classe com o maior valor resultante” (coluna 8, linha 46), ou seja, trata-se de um classificador de cenário fechado. O classificador pode classificar a amostra de teste em uma ou mais classes, dependendo da probabilidade (coluna 1, linha 44). O termo “desconhecido” mencionado no documento de patente US 8,306,818 B2 refere-se às classes de palavras não consideradas pelo sistema, isto é, explicitamente eliminadas dele. Diferentemente, no contexto da presente invenção, o termo “desconhecido” refere-se às amostras de teste que pertencem a nenhuma das classes de treinamento, devendo ser, portanto, classificadas como “desconhecido”. Além disso, em contraste com a presente invenção, o documento US 8,306,818 B2 não propõe um método de reconhecimento em cenário aberto e não utiliza “razão sobre as medidas de similaridade” para classificação.

[0010] O documento de patente US 8,515,758 B2, intitulado “Speech Recognition Including Removal of Irrelevant Information”, publicado em 20 de agosto de 2013, apresenta um sistema de reconhecimento de voz baseado em um classificador estatístico responsável por classificar uma elocução/dicção de entrada, e o método de classificação não é baseado em medidas de similaridade (tampouco em “razão sobre medidas de similaridade”, como proposto pela presente invenção). O termo “desconhecido” mencionado no documento US 8,515,758 B2 refere-se à amostra de teste em que sua classe correta não é conhecida a priori, isto é, quando ainda não se sabe a qual das classes de treinamento a amostra de teste pertence. Diferentemente, na presente invenção, o termo “desconhecido” refere-se às amostras de teste que pertencem a nenhuma das classes de treinamento.

[0011] O documento de patente KR 2013/0006030 A, intitulado: “Construction Method of Classification Model for Emotion Recognition and Apparatus Thereof”, publicado em 16 de janeiro de 2013, apresenta método e aparato para classificar uma pluralidade de emoções (reconhecimento de emoções) a partir de dados biométricos usando um sistema binário. Em contraste com a presente invenção, o documento KR 2013/0006030 A não apresenta um método de reconhecimento em cenário aberto, isto é, um método para classificar uma amostra de teste como pertencente a nenhuma das classes treinadas. O documento KR 2013/0006030 A também não apresenta qualquer tipo de “razão sobre medidas de similaridade” para classificação.

[0012] O documento de patente US 2006/093208 A1, intitulado: “Open Set Recognition Using Transduction”, publicado em 04 de maio de 2006, propõe o TCM-kNN (Transductive Confidence Machine-k Nearest Neighbors), um método para reconhecimento biométrico de cenário aberto. Um sistema especificamente projetado para reconhecimento de face é usado como exemplo de aplicação do método proposto, e menciona-se que o método pode ser aplicado a outros problemas de reconhecimento, mas não especifica como isso poderia ser feito. Para permitir classificação de “desconhecidos”, automaticamente se define um limiar de rejeição sobre o que os inventores chamaram “razão de pico- a-lado” (“peak-to-side ratio”). A “razão de pico-a-lado” é um valor que pode ser obtido baseado em valores-p (p- values) para cada classe de treinamento. Obtém-se o limiar com base em várias “razões de pico-a-lado” (uma para cada classe de treinamento). O método do documento US 2006/0933208 A1 pode ser usado em aplicações em que cada classe de treinamento pode ser representada como uma amostra modelo (ou identificador de amostra). Em contraste, o método proposto na presente invenção pode ser aplicado a problemas genéricos de reconhecimento em cenário aberto, não apenas aqueles em que todas as amostras de treinamento de uma certa classe possam ser condensadas em uma amostra modelo.

[0013] Uma contribuição da solução proposta no documento US 2006/0933208 A1 é a definição automática de um limiar sobre as amostras modelos de treinamento para permitir a classificação de amostras como “desconhecida”. Em contraste, o método da presente invenção não define o limiar sobre a função distância, mas ao contrário, o limiar é definido sobre a razão das distâncias (medidas de similaridade) de duas classes diferentes. Além disso, não fica claro no documento US 2006/0933208 A1 se a razão pico- a-lado continua a fazer sentido ou funcionar perfeitamente quando um classificador é treinado com diversas amostras para cada classe.

[0014] O documento de patente WO 2008008142 A2, intitulado “Machine Learning Techniques and Transductive Data Classification”, publicado em 17 de janeiro de 2008, descreve um classificador binário que usa aprendizado transdutivo (transductive learning), que é um tipo de aprendizado semi-supervisionado. O método proposto não lida com classificação de transdução nem com classificação semi- supervisionada, isto é, não usa “pontos de dados não rotulados como exemplos de treinamento” nem propaga rótulos dos exemplos conhecidos para os desconhecidos. Finalmente, o método proposto no documento WO 2008008142 A2 requer pelo menos um exemplo rotulado por classe, o que transforma o problema em um problema de classificação em cenário fechado. Este não é o escopo nem o propósito do método da presente invenção.

[0015] O documento de patente US 6,205,247 B1, intitulado: “Method and arrangement for pattern recognition on the basis of statistics”, concedido em 20 de março de 2001, se refere a criação de um método de reconhecimento de padrões baseado em estatísticas e um arranjo para executar o método, com o qual são evitados os problemas delineados do estado da técnica, com um grande número de classes e custos justificáveis, e que é capaz de realizar tarefas gerais de reconhecimento em tempo real, evitando uma iteração baseada em regras de classificadores de rede. Entretanto, o documento US 6,205,247 B1, em contraste com a presente invenção, não rejeita as amostras desconhecidas, ou seja, não há amostras de teste pertencentes a qualquer outra classe e, portanto, não há rejeição e classificação dessas amostras como desconhecidas, conforme acontece na presente invenção. Dessa forma, o documento US 6,205,247 B1 pode ser considerado um classificador binário fechado, ou seja, para o cenário fechado. Além disso, o documento US 6,205,247 B1 não apresenta qualquer tipo de “razão sobre medidas de similaridade” para classificação.

[0016] O documento de patente US 2004/0096100 A1, intitulado: “Method and computer program product for identifying output classes with multi-modal dispersion in feature space and incorporating multi-modal structure into a pattern recognition system”, publicado em 20 de maio de 2004, se refere a um método de identificação e correção de classes de saída com uma distribuição multimodal através do espaço de características em um sistema de reconhecimento de padrões. Os sistemas de processamento de imagens geralmente contêm dispositivos de reconhecimento de padrões (classificadores).

[0017] O documento de patente US 2004/0022441 A1, intitulado: “Method and computer program product for identifying and incorporating new output classes in a pattern recognition system during system operation”, publicado em 05 de fevereiro de 2004, se refere a um sistema para localizar e incorporar novas classes em um dispositivo de reconhecimento de padrão ou classificador. Sistemas de processamento de imagem geralmente contém dispositivos de reconhecimento de padrão (classificadores).

[0018] De acordo com os documentos US 2004/0096100 A1 e US 2004/0022441 A1, uma pluralidade de padrões de entrada, determinados a não serem associados com nenhum de um conjunto de pelo menos uma classe de saída representada por um classificador de reconhecimento de padrão, são rejeitados. As amostras de padrões rejeitados são agrupadas em clusters de acordo com as similaridades entre as amostras de padrão.

[0019] Entretanto, os documentos US 2004/0096100 A1 e US 2004/0022441 A1 falham em descrever qualquer tipo de “razão sobre medidas de similaridade” para classificação. A presente invenção, em contraste com os documentos US 2004/0096100 A1 e US 2004/0022441 A1, descreve um método que identifica as duas classes mais similares e estabelece um limiar sobre a razão de duas medidas de similaridade, o que permite ao método uma melhor adaptação frente às soluções existentes, quando muitas características são extraídas dos dados de entrada.

[0020] Na publicação intitulada “Estimating the Support of a High-Dimensional Distribution” (B. Scholkopf; J. Platt; J. Shawe-Taylor; A. Smola; R. Williamsom; Technical Report MSR-TR-99-87; Microsoft Research; 1999), Scholkopf et al. (1999) propõe uma extensão do SVM chamada SVM de classe única (OCSVM). Esse classificador é treinado em apenas uma classe conhecida, e encontra a melhor margem em relação à origem. Esta é a abordagem mais confiável em casos em que o acesso a uma segunda classe é muito difícil ou mesmo impossível. Apesar de essa abordagem ser muito apropriada para o cenário aberto, trata-se de um classificador de uma única classe e, portanto não tira vantagens de todas as classes disponíveis para o treinamento (pelo fato de usar apenas uma única classe conhecida para treinamento, mesmo que haja outras classes disponíveis).

[0021] De fato, o artigo “Relevance Feedback in Image Retrieval: A Comprehensive Review” (X. Zhou and T. Huang; Multimedia Systems 8; pp. 536-544; Springer-Verlag; 2003) menciona que o OCSVM tem um uso limitado porque não tem capacidade para boa generalização ou boa especialização. Diferentemente do método proposto por Scholkopf et al. (1999), o método proposto na presente invenção é um classificador multiclasse e não é baseado em SVM.

[0022] No artigo “Open Set Source Camera Attribution” (F. Costa, M. Eckmann, W. Scheirer e A. Rocha; XXV SIBGRAPI - Conf. on Graphics, Patterns and Images, 2012, pp. 71-78), Costa et al. (2012) apresenta um algoritmo de atribuição de fonte de câmera considerando o cenário aberto. Como a minimização de risco do SVM tradicional binário é baseada apenas nas classes conhecidas, ela pode classificar erroneamente as classes negativas e desconhecidas que aparecem durante a fase de teste. Assim, Costa et al. (2012) propôs o método conhecido no estado da técnica como SVM with Decision Boundary Carving (SVMDBC) que minimiza o risco do desconhecido em vez de encontrar o hiperplano de separação de máxima margem. A minimização do risco do desconhecido é feita movendo o hiperplano de decisão encontrado pelo SVM tradicional por um valor e para dentro ou para fora da classe positiva. O valor e é definido por uma busca exaustiva para minimizar o erro com base nos dados de treinamento. O método SVMDBC apresentado por Costa et al. (2012) é baseado em SVM e é binário, diferentemente do método da presente invenção, que não é baseado em SVM, e é multiclasse e de cenário aberto. Efetivamente, o método apresentado por Costa et al. (2012) trata-se de um método para controle de falsos positivos.

[0023] No artigo intitulado “Towards Open Set Recognition” (W. Scheirer, A. Rocha, A. Sapkota, T. Boult; IEEE Transactions on Pattern Analysis and Machine Intelligence - TPAMI, Julho de 2013, vol. 35, no. 7, pp. 1757-1772), Scheirer et al. (2013) apresenta a 1-vs-Set Machine com uma formulação de kernel linear que pode ser aplicada ao SVM binário e SVM de classe única. O objetivo deste documento também é minimizar o risco do desconhecido, o que é feito através da minimização da região rotulada como positiva (isto é, o espaço aberto de risco) combinada com as restrições de margem para minimizar o risco empírico (medido em dados de treinamento). Scheirer et al. (2013), similarmente ao que é feito por Costa et al. (2012), também move o hiperplano do SVM original para dentro da classe positiva, mas agora adicionando também um hiperplano distante “depois” das amostras positivas, com o objetivo de diminuir o espaço aberto de risco. Os hiperplanos são inicializados de modo a conter todas as amostras positivas. Então é executada uma etapa de refinamento para ajustar o hiperplano para generalizar ou especializar o classificador de acordo com parâmetros do usuário. Conforme observado por Scheirer et al. (2013), resultados melhores são usualmente obtidos quando o hiperplano do SVM original está próximo da borda positiva visando uma especialização, e o hiperplano adicionado é ajustado visando generalização. Apesar da generalização do segundo hiperplano, essa é uma forma de especialização quando comparado ao SVM original, na qual pode ser considerado que o segundo hiperplano está no infinito. De acordo com os autores do artigo, as amostras negativas após o segundo hiperplano (adicionado) não estão próximas às amostras positivas, e essa é a razão da generalização desse segundo hiperplano. O método proposto na presente invenção vai além ao permitir tratar problemas de classificação multiclasse no cenário aberto e definir um espaço aberto de risco delimitado.

[0024] O espaço aberto de risco refere-se à região no espaço de características das amostras tal que uma amostra de teste localizada nessa região é sempre classificada como pertencente a uma das classes conhecidas em vez de desconhecida. No estado da técnica, as soluções propostas para lidar com o problema de reconhecimento em cenário aberto são principalmente baseadas em SVM. Nessas soluções, o objetivo é minimizar o risco do desconhecido através da minimização do espaço aberto de risco. Como os métodos SVM definem “semiespaços” (ou seja, fronteiras simples), não é trivial criar um espaço aberto de risco ilimitado. Toda extensão ou aprimoramento de métodos SVM para o cenário aberto descritos no estado da técnica mantém um espaço aberto de risco ilimitado. O desafio para potenciais soluções é minimizar o espaço aberto de risco, criando preferencialmente um espaço aberto de risco finito, o que o método da presente invensão faz.

[0025] De acordo com o estado da técnica conhecido e as soluções analisadas, existem quatro tipos de métodos para o problema de classificação/reconhecimento: (1) Multiclasse e para cenário fechado: OPF, kNN; (2) Binário e para cenário fechado: SVM; (3) Binário e para cenário aberto: SVM, OCSVM (Scholkopf et al. 1999), SVMDBC (Costa et al. 2012), 1-vs- Set Machine (Scheirer et al., 2013); (4) Multiclasse e para cenário aberto: o método da presente invenção; MCSVM (SVM adaptado); kNN ajustado usando um limiar sobre a medida de similaridade (kNN adaptado); MCSVMDBC (SVMDBC adaptado utilizando abordagem um-contra-todos); e 1-vs-Set Machine (quando adaptado para o cenário aberto utilizando abordagem um-contra-todos).

[0026] Nenhum artigo ou documento de patente descreve um método inerentemente multiclasse para o cenário aberto, apesar de que alguns métodos do estado da técnica podem ser adaptados para serem multiclasse e de cenário aberto (entretanto, sem bons resultados). Conforme será descrito em detalhes a seguir, o método proposto na presente invenção apresenta características e aspectos novos e diferenciais em comparação ao estado da técnica.

Sumário da Invenção

[0027] A presente invenção refere-se a um método de reconhecimento que permite rejeitar amostras (ou seja, classificá-las como desconhecidas) em problemas gerais de reconhecimento multiclasse em cenário aberto. Já existem soluções do estado da técnica que permitem a classificação multiclasse, mas não permitem classificar amostras como desconhecidas a menos que seja definido um limiar não trivial sobre a medida de similaridade do classificador. Também existem no estado da técnica soluções para cenário aberto para casos binários, que não suportam a classificação multiclasse em seu algoritmo principal. Na verdade, o cenário binário não é realmente um cenário aberto e as soluções binárias propostas para cenário aberto se tratam de soluções para controle de falso positivo.

[0028] A solução proposta na presente invenção gera um espaço aberto de risco delimitado, enquanto as atuais soluções binárias aplicadas ao cenário aberto deixam um espaço aberto de risco ilimitado. Em outras palavras, as amostras pertencentes a classes não vistas durante a fase de treinamento podem ser devidamente identificadas e tratadas (não classificadas como uma classe de interesse) pelo método da presente invenção durante a fase de teste/execução. Sem modificações, as atuais soluções multiclasse classificariam erroneamente as referidas amostras como uma classe conhecida. Diferentemente das atuais soluções multiclasse, o presente método não necessita de uma parametrização complexa de acordo com cada conjunto de dados de treinamento e teste (dataset), isto é, ele pode ser diretamente aplicado em problemas multiclasse de cenário aberto independentemente se apenas algumas classes ou todas elas são conhecidas durante a fase de treinamento.

[0029] Essa invenção é um método de classificação que recebe o vetor de características (dado de entrada a ser classificado) e retorna os resultados da classificação (a classe do dado de entrada ou “desconhecido”). Para usar o método da presente invenção em aplicações ou produtos reais, é necessário apenas um dispositivo executando o método proposto. Qualquer descritor de dados também pode ser inserido no dito dispositivo para gerar o vetor de características a partir dos dados de entrada a serem processados pelo método da invenção. Em alguns casos, a coleção de dados e o uso dos resultados da classificação podem ser tratados pelo mesmo dispositivo. Muitas ações podem ser executadas a partir dos resultados gerados pelo presente método de classificação. Logo, a presente invenção apresenta amplo escopo e é genérica suficiente para ser utilizada em uma grande variedade de problemas de classificação em diversas aplicações.

[0030] Em aplicações reais, a maioria das amostras de teste é considerada “desconhecida”, porque é impossível conhecer integralmente o mundo real e toda a gama de possíveis classes. Resultados de experimentos, mostrados adiante neste documento, indicam que o método proposto supera os métodos existentes para o cenário aberto. Usando o método proposto, a maioria das amostras de teste desconhecida é corretamente classificada como desconhecida, e a maioria das amostras de teste conhecidas é devidamente classificada com sua classe correta correspondente.

[0031] Em vez de usar um limiar de medida de similaridade obtido com base no dado de entrada e na classe mais similar (que é a abordagem usual para lidar com o cenário aberto), o método da presente invenção identifica as duas classes mais similares e estabelece um limiar sobre a razão de duas medidas de similaridade, o que permite ao método uma melhor adaptação frente às soluções existentes, quando muitas características são extraídas dos dados de entrada (espaço de características de alta dimensionalidade).

[0032] Um sistema ou dispositivo ao implementar uma concretização da presente invenção proverá vantagem competitiva no mercado correspondente. Qualquer aplicação que requeira a negação/rejeição de alguns tipos de dados de entrada pode usar o método da presente invenção. Aplicações gerais de reconhecimento, que são inerentemente de cenário aberto, como, por exemplo: reconhecimento biométrico, reconhecimento de objeto, reconhecimento de cenas, reconhecimento de voz, reconhecimento de caracteres, reconhecimento de padrões, etc. podem se beneficiar da presente invenção. Aplicações médicas, nas quais apenas um número finito de doenças é conhecido durante a fase de treinamento e muitas outras (desconhecidas) surgem durante o uso do método (fase de teste), também podem utilizar-se do método aqui proposto.

Breve Descrição das Figuras

[0033] Os objetivos e vantagens da presente invenção ficarão mais claros através da seguinte descrição detalhada de uma concretização exemplar e não limitativa a partir das figuras a seguir, em que:

[0034] A Figura 1A representa a fase de treinamento com o grafo completo de cinco amostras, segundo um classificador OPF conhecido do estado da técnica.

[0035] A Figura 1B mostra o cálculo Minimum Spanning Tree (MST) M, em que as amostras tracejadas S2 e S3 são escolhidas como protótipos, segundo o classificador OPF da Figura 1A.

[0036] A Figura 1C apresenta uma fase de teste, segundo o classificador OPF da Figura 1A.

[0037] A Figura 2 ilustra um exemplo de classificação realizada pelo método Multiclass Support Vector Machine (MCSVM) utilizando a abordagem um-contra- todos, conhecido no estado da técnica.

[0038] A Figura 3 apresenta um fluxograma com os passos/etapas principais do método proposto na presente invenção.

[0039] A Figura 4A mostra uma primeira representação do particionamento dos dados de treinamento, de acordo com uma concretização do método da presente invenção.

[0040] A Figura 4B mostra uma segunda representação do particionamento dos dados de treinamento e a característica esperada desses dados no cenário real.

[0041] A Figura 4C mostra uma terceira representação do particionamento dos dados de treinamento, de acordo com uma concretização do método proposto na presente invenção.

[0042] A Figura 5 ilustra o funcionamento do método para classificação de amostras proposto na presente invenção.

[0043] A Figura 6 ilustra um exemplo da classificação realizada pelo método proposto da presente invenção.

[0044] A Figura 7A apresenta o resultado de um experimento com Bordas de Decisão usando o método OPF conhecido no estado da técnica para o conjunto de dados Cone-torus.

[0045] A Figura 7B apresenta o resultado do experimento Bordas de Decisão usando o método MCSVM conhecido no estado da técnica para o conjunto de dados Cone-torus.

[0046] A Figura 7C apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVMDBC conhecido no estado da técnica para o conjunto de dados Cone-torus.

[0047] A Figura 7D apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVM1VS conhecido no estado da técnica para o conjunto de dados Cone-torus.

[0048] A Figura 7E apresenta o resultado de um experimento com Bordas de Decisão usando o método da presente invenção para o conjunto de dados Cone-torus.

[0049] A Figura 8A apresenta o resultado de um experimento com Bordas de Decisão usando o método OPF conhecido no estado da técnica para o conjunto de dados Four-gauss.

[0050] A Figura 8B apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVM conhecido no estado da técnica para o conjunto de dados Four-gauss.

[0051] A Figura 8C apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVMDBC conhecido no estado da técnica para o conjunto de dados Four-gauss.

[0052] A Figura 8D apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVM1VS conhecido no estado da técnica para o conjunto de dados Four-gauss.

[0053] A Figura 8E apresenta o resultado de um experimento com Bordas de Decisão usando o método da presente invenção para o conjunto de dados Four-gauss.

[0054] A Figura 9A apresenta o resultado de um experimento com Bordas de Decisão usando o método OPF conhecido no estado da técnica para o conjunto de dados R15.

[0055] A Figura 9B apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVM conhecido no estado da técnica para o conjunto de dados R15.

[0056] A Figura 9C apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVMDBC conhecido no estado da técnica para o conjunto de dados R15.

[0057] A Figura 9D apresenta o resultado de um experimento com Bordas de Decisão usando o método MCSVM1VS conhecido no estado da técnica para o conjunto de dados R15.

[0058] A Figura 9E apresenta o resultado de um experimento com Bordas de Decisão usando o método da presente invenção para o conjunto de dados R15.

[0059] A Figura 10A apresenta o resultado de um experimento com a Curva Conhecido-Desconhecido, contrabalançando a precisão/acurácia com base nas amostras conhecidas (eixo x) e a precisão/acurácia com base nas amostras desconhecidas (eixo y), usada para obter a precisão/acurácia normalizada para o conjunto de dados Caltech-256.

[0060] A Figura 10B apresenta o resultado de um experimento com a Curva Conhecido-Desconhecido, contrabalançando a precisão/acurácia com base nas amostras conhecidas (eixo x) e a precisão/acurácia com base nas amostras desconhecidas (eixo y), usada para obter a precisão/acurácia normalizada para o conjunto de dados ALOI.

[0061] A Figura 10C apresenta o resultado de um experimento com a Curva Conhecido-Desconhecido, contrabalançando a precisão/acurácia com base nas amostras conhecidas (eixo x) e a precisão/acurácia com base nas amostras desconhecidas (eixo y), usada para obter a precisão/acurácia normalizada para o conjunto de dados Auslan.

[0062] A Figura 10D apresenta o resultado de um experimento com a Curva Conhecido-Desconhecido, contrabalançando a precisão/acurácia com base nas amostras conhecidas (eixo x) e a precisão/acurácia com base nas amostras desconhecidas (eixo y), usada para obter a precisão/acurácia normalizada para o conjunto de dados 15- Scenes.

[0063] A Figura 10E apresenta o resultado de um experimento com a Curva Conhecido-Desconhecido, contrabalançando a precisão/acurácia com base nas amostras conhecidas (eixo x) e a precisão/acurácia com base nas amostras desconhecidas (eixo y), usada para obter a precisão/acurácia normalizada para o conjunto de dados letter.

[0064] A Figura 10F apresenta o resultado de um experimento com a Curva Conhecido-Desconhecido, contrabalançando a precisão/acurácia com base nas amostras conhecidas (eixo x) e a precisão/acurácia com base nas amostras desconhecidas (eixo y), usada para obter a precisão/acurácia normalizada para o conjunto de dados ukbench.

Descrição Detalhada da Invenção

[0065] A classificação refere-se ao problema de atribuição de uma amostra de teste a uma ou mais classes de um conjunto de classes conhecidas. Por outro lado, o reconhecimento é a tarefa de verificar se uma amostra de teste pertence a uma das classes conhecidas e, em caso afirmativo, descobrir a qual das classes conhecidas a amostra de teste pertence.

[0066] Um método conhecido do estado da técnica é o OPF, cujo funcionamento é sucintamente ilustrado nas Figuras 1A-1C, em que as Figuras 1A-1B representam a fase de treinamento/ajuste e a Figura 1C ilustra a fase de teste/predição. O exemplo mostra cinco amostras de treinamento: S3, S4, e S5 da “classe branca” e S1 e S2 da “classe escura”.

[0067] A Figura 1A apresenta o cálculo do grafo completo a partir das amostras de treinamento, em que os valores numéricos nos arcos indicam a distância entre as amostras no espaço de características.

[0068] A Figura 1B mostra o cálculo da árvore geradora mínima (Minimum Spanning Tree - MST), em que as amostras tracejadas S2 e S3 são escolhidas como protótipos.

[0069] A Figura 1C apresenta a classificação da amostra de teste S (bordas pontilhadas e tom claro), que é atribuída a árvore enraizada/originada no protótipo S3 porque ele oferece a menor distância (menor custo) e, portanto, a amostra de teste S será classificada como pertencente à “classe branca”.

[0070] Entretanto, deve-se observar que é possível ter uma amostra de teste que não pertence a qualquer uma das classes conhecidas (ou seja, não se trata de um cenário fechado). Por exemplo, reconhecer se uma amostra biométrica pertence a um dos indivíduos registrados em um sistema de reconhecimento biométrico (isto é, a amostra pertence a uma classe conhecida e o sistema de reconhecimento biométrico deve aceitá-la) ou não pertence (nesse caso, a amostra não pertence a qualquer classe conhecida e o sistema deve rejeitá-la).

[0071] Nesse caso, o cenário de reconhecimento é mais próximo ao cenário aberto. No cenário de aberto, o classificador não pode ser treinado com todas as classes possíveis (ao contrário do cenário fechado, em que supõe-se que todas as classes são conhecidas a priori e podem ser aplicadas a problemas muito específicos). O cenário aberto é multiclasse quando o classificador deve classificar uma amostra de teste como uma das classes de treinamento conhecidas ou como desconhecida. Nesse caso, é possível ter os seguintes tipos de erro: (1) a amostra de teste pertence a uma das classes de treinamento conhecidas, mas o classificador atribui-lhe uma classe conhecida errada; (2) a amostra de teste pertence a uma das classes de treinamento conhecidas, mas o classificador classificou-a como desconhecida; e (3) a amostra de teste pertence a uma classe desconhecida, mas o classificador classificou-a como uma das classes de treinamento conhecidas. Em um cenário de classificação fechado, apenas o erro (1) faz sentido, ou seja, o cenário fechado não é adequado para lidar corretamente com amostras de teste que pertençam a classes de treinamento desconhecidas.

[0072] Uma abordagem comum para lidar parcialmente com o cenário aberto é definir um limiar T e verificar se a medida correspondente é maior ou igual a T. Essa abordagem consiste em classificar uma amostra de teste como desconhecida quando a classe de treinamento mais similar não é suficientemente similar. Sem esse limiar T, uma amostra de teste desconhecida sempre será atribuída a uma das classes de treinamento, o que não é verdade em um cenário aberto.

[0073] A Figura 2 ilustra o método SVM multiclasse utilizando a abordagem um-contra-todos (MCSVM), conhecido do estado da técnica, que pode classificar algumas amostras de teste como desconhecidas (representado por “?” na Figura 2) tendo em vista que elas são classificadas negativamente por todos os classificadores binários que compõem o MCSVM (nesse caso: 1 vs 2,3; 2 vs 1,3; 3 vs 1,2). De todo modo, as amostras de teste distantes também serão classificadas como uma das classes conhecidas na maioria dos casos pelo MCSVM, porque esse método classificador cria um espaço aberto de risco ilimitado.

[0074] A Figura 3 é uma visão geral da presente invenção, representada por um fluxograma com os passos/etapas principais do método proposto na presente invenção. O fluxograma está dividido em duas partes: fase de treinamento (passos 1, 2 e 3) e a fase de teste (passos 4, 5, 6 e 7).

[0075] Na fase de treinamento, um conjunto de amostras usadas para treinamento é dividido em n classes de interesse (etapa 1), que será usado para treinar o classificador multiclasse (etapa 2), isto é, obter os parâmetros intrínsecos do classificador. Há muitas maneiras de se treinar um classificador multiclasse, por exemplo (mas não limitado a) através de Optimum Path Forest (OPF) e k-Nearest Neighbors (kNN), entre outras técnicas conhecidas no estado da técnica. O parâmetro de rejeição T (0.0<T<1.0) é obtido a partir da otimização de parâmetros (etapa 3) e será posteriormente usada (na etapa 7, fase de teste) para determinar se as amostras de teste serão classificadas como desconhecidas ou como uma das n classes treinadas/conhecidas.

[0076] No contexto da presente invenção, as amostras são divididas entre conjuntos de treinamento e de teste, conforme ilustrado na Figura 4A. Em um cenário aberto, o conjunto de teste é a união do conjunto conhecido e do conjunto desconhecido, pelo fato de haver classes em que não há amostras disponíveis para treinamento, conforme ilustrado na Figura 4B. Para um melhor resultado da otimização de parâmetro (etapa 3), as amostras do conjunto de treinamento (etapa 1) são divididas em conjunto de ajuste (amostras usadas para efetivamente treinar um classificador) e conjunto de validação (amostras usadas para verificar a precisão/precisão baseada em um valor teste de T), sendo que a referida divisão é feita da seguinte maneira: (i) apenas metade das classes disponíveis possuem amostras representativas no conjunto de ajuste; (ii) para cada classe que possui amostras representativas no conjunto de ajuste, metade de suas amostras está no conjunto de ajuste e a outra metade está no conjunto de validação, conforme ilustrado na Figura 4C. Observe que a otimização de parâmetro (etapa 3) é simplesmente uma maneira de simular o cenário aberto e obter um limiar T razoável, e portanto essa otimização de parâmetros (etapa 3) pode ser feita de diversas maneiras.

[0077] De acordo com a Figura 4C, tendo definido o conjunto de ajuste e conjunto de validação, a otimização de parâmetro (etapa 3) ajusta um classificador a partir das amostras do conjunto de ajuste, e um procedimento tradicional de grid search é realizado para encontrar o melhor valor do parâmetro de rejeição T a partir das amostras do conjunto de validação.

[0078] Durante a fase de teste (que corresponde ao uso/funcionamento propriamente dito do método, após o classificador ter sido ajustado na fase de teste), uma amostra de teste S (um novo descritor) é submetida (etapa 4) ao método proposto, que obtém as duas melhores classes (etapa 5), ou seja, as duas classes c1, c2 “mais próximas” à amostra de teste S entre as n classes treinadas/conhecidas. A seguir, o método computa a razão das duas melhores medidas de similaridade (etapa 6), isto é, a razão R = δ1/δ2 entre a “medida de similaridade/distância” δ1 da amostra de teste S para a melhor classe c1 e a “medida de similaridade/distância” δ2 da amostra de teste S para a segunda melhor classe c2 (considerando que o menor valor de medida de similaridade/distância representa o melhor). Há muitas maneiras de determinar a “medida de similaridade/distância” δ, por exemplo, (mas não limitado) a função de custo fcost do OPF e as métricas de distância do kNN, entre outras técnicas conhecidas no estado da técnica. Finalmente, o método verifica (etapa 7) se a razão R das duas melhores medidas de similaridade (obtidas na etapa 6) é maior que o parâmetro de rejeição T (obtido na etapa 3): em caso afirmativo (R>T), a amostra de teste S (submetida na etapa 4) é classificada como desconhecida (nenhuma das n classes treinadas/conhecidas); caso contrário (R<T), amostra de teste S (submetida na etapa 4) é atribuída à melhor classe c1 (uma das n classes treinadas/conhecidas, obtida na etapa 5).

[0079] Para melhor compreensão do método proposto, um exemplo de seu funcionamento/uso (fase de teste) é apresentado na Figura 5. No exemplo da Figura 5, foi usado um classificador OPF para encontrar as duas melhores classes durante a fase de teste (etapa 5 do método proposto). As amostras cinza escuro N são de uma classe e as amostras cinza escuro P pertencem à outra classe. As amostras cinza claras de bordas pontilhadas X, Y e Z são amostras de teste S. As amostras com bordas tracejadas N e P são protótipos de suas respectivas classes. O padrão das arestas/linhas das amostras de teste S (X, Y e Z) indica em qual classe poderão ser classificadas após a execução do método proposto: linhas/arestas pontilhadas para a classe P e ponto-traço para a classe N. As arestas pontilhadas adjacentes à amostra de teste S (X, Y e Z) são arestas para a amostra vizinha de S no caminho da melhor medida de similaridade/distância δ1. As arestas ponto-traço são adjacentes à amostra vizinha de S no caminho da segunda melhor medida de similaridade/distância δ2. Arestas com linhas contínuas representam as arestas obtidas durante a fase de treinamento (etapa 2, no caso desse exemplo, também usando um classificador OPF). Supondo que nesse caso o parâmetro de rejeição T (limiar) seja 0.80, a amostra de teste X seria classificada como desconhecida, porque sua razão R = δ1/δ2 resulta em 0.98>T. As amostras de teste Y e Z seriam classificadas como P porque suas razões R = δ1/δ2 resultam em 0.40 e 0.61, respectivamente, ou seja, ambas são menores que o parâmetro T (e nesse caso P é a melhor classe para Y e Z).

[0080] A Figura 6 mostra um exemplo de classificação gerada pelo método proposto. Para fins de comparação, as amostras são as mesmas usadas no exemplo da Figura 2 (MCSVM usando abordagem One-vs-All). Conforme pode ser observado, a classificação feita pelo presente método não é igual às classificações feitas por métodos do estado da técnica (MCSVM). Devido ao fato de que o método proposto é baseado na razão (R) das duas melhores medidas de similaridade (δ1,δ2), são definidas fronteiras adicionais (representadas pelas linhas curvas pontilhadas na Figura 6 - e inexistentes na Figura 2), criando regiões delimitadas.

[0081] Nesse caso, uma amostra de teste S que esteja “distante” das amostras de treinamento será classificada como desconhecida, mesmo que todas as amostras de treinamento de uma certa classe estejam mais próximas do que a amostra mais próxima das demais classes. Isso ocorre porque a razão R tende a 1 conforme ambas as medidas de similaridade/distância δ1 e δ2 aumentam (e, portanto, a razão R também tende a ser maior que T, 0.0<T<1.0 - o que faz com que a amostra de teste S seja classificada como desconhecida). Por exemplo, na Figura 6, a amostra “??” seria classificada como desconhecida pelo método proposto: apesar da amostra “??” estar mais próxima de todas as amostras de treinamento da classe “3” que a amostra mais próxima das outras classes (“1” e “2”), a amostra “??” também está relativamente distante (baseado na razão R) das amostras de treinamento da classe “3”.

[0082] Portanto, essas regiões delimitadas do espaço de características definem um espaço aberto de risco finito (que é infinito ou muito grande no caso dos classificadores de cenário aberto conhecidos até então). O espaço aberto de risco finito aumenta a capacidade do classificador em classificar corretamente uma amostra de teste como desconhecida ou como melhor classe. De fato, experimentos (apresentados ao final desse documento) comprovam que o método proposto tem melhor precisão no cenário aberto.

[0083] A principal característica do método proposto é estender classificadores multiclasse para tratar adequada e eficientemente o cenário aberto, isto é, buscar soluções na qual o risco do desconhecido é minimizado. É importante minimizar esse risco porque durante a fase de treinamento não existem amostras das classes desconhecidas.

[0084] Outra vantagem importante da presente invenção sobre a maioria dos classificadores para cenário aberto conhecidos no estado da técnica é o fato de que o método proposto é inerentemente multiclasse, e, portanto, sua eficiência não depende do número n de classes disponíveis para fase de treinamento. Os classificadores multiclasse baseados em classificadores binários (abordagem um-contra-todos), que são geralmente usados no estado da técnica para o cenário aberto, apresentam uma inconveniência: conforme o número n de classes disponíveis aumenta, o número de classificadores binários necessários também aumenta e, consequentemente, a eficiência do processo de classificação é afetada, levando a outras duas indesejáveis consequências: (i) torna-se computacionalmente muito custoso usar classificadores multiclasse baseados em classificadores binários quando n é alto; e/ou (ii) isso não resulta em boa classificação.

Experimentos e Resultados

[0085] No contexto dos experimentos usando o método proposto da presente invenção, as amostras conhecidas são aquelas que pertencem a uma das classes disponíveis na fase de treinamento e as amostras desconhecidas pertencem às classes em que nenhuma amostra representativa foi usada durante a fase de treinamento.

Experimento 1 - Eficácia do método no cenário aberto

[0086] Para analisar a eficácia e precisão do método proposto na presente invenção, o mesmo foi comparado com os seguintes métodos já conhecidos no estado da técnica: OPF, SVM multiclasse com abordagem um-contra-todos (MCSVM), e SVMDBC multiclasse (Costa et al., 2012) com abordagem um-contra-todos (MCSVMDBC) e 1-vs-Set Machine multiclasse (Scheirer et al. 2013) com abordagem um-contra- todos (MCSVM1VS), variando do cenário menos aberto ao cenário mais aberto possível. Seis conjuntos de dados (datasets) conhecidos no estado da técnica foram usados nesse experimento: Caltech-256, ALOI, Auslan, 15-Scene, letter e ukbench. Esses conjuntos de dados representam aplicações de reconhecimento de objetos (Caltech-256, ALOI, ukbench), reconhecimento de cena (15-Scene), reconhecimento de linguagem de sinais (Auslan) e reconhecimento de letras/caracteres (letter).

[0087] Foram realizados experimentos em todos os conjuntos de dados, supondo acesso a um número de 3, 6, 9 e 12 classes entre o número total de classes de cada conjunto de dados. Para cada número n de classes disponíveis, foram realizados 10 experimentos. Para cada experimento: (1) foram aleatoriamente escolhidas n classes disponíveis para treinamento; (2) foram consideradas metade das amostras conhecidas em cada classe para teste; (3) as amostras de outras classes foram consideradas como desconhecidas para teste; e (4) foram obtidos resultados com base em medidas de cenário aberto. O teste estatístico “Analysis of Variance” (ANOVA) foi realizado e, em seguida, foi usado o método pós-teste “Tukey Honest Significant Differences” (HSD) para confirmar a superioridade do método proposto. Como já foi dito, para cada combinação de classificador, conjunto de dados e número n de classes disponíveis, foram executados 10 experimentos com diferentes grupos de classes disponíveis.

[0088] Na Tabela 1 abaixo, para cada par de métodos (intersecção entre linha e coluna) as setas (j e ^) indicam o método vencedor (j para o método da linha, ^ para o método da coluna), e os espaços em branco indicam que a diferença entre o par de métodos não é estatisticamente significante (eficácia similar) de acordo com o pós-teste Tukey HSD. A coluna ac indica o número de classes disponíveis (3, 6, 9, e 12). Observa-se que o método proposto obtém melhores resultados que OPF, MCSVM, MCSVMDBC, e MCSVM1VS (versão multiclasse do 1-vs-Set Machine) em todos os experimentos. Tabela 1 - Resultados do experimento 1.

Experimento 2 - Bordas de Decisão (Decision Boundaries)

[0089] Com o objetivo de entender os diferentes comportamentos dos classificadores, foram realizados testes em conjuntos de dados sintéticos bidimensionais para facilitar a visualização. Foram usados os seguintes conjuntos de dados, já conhecidos no estado da técnica: Cone-torus, Four-gauss, e R15. Os classificadores foram treinados usando todas as amostras do conjunto de dados para traçar Bordas de decisão para cada classe. As Bordas de decisão de uma classe definem a região na qual uma eventual amostra de teste seria classificada como pertencente à classe que define a região.

[0090] As Figuras 7, 8 e 9 apresentam os resultados do experimento 2 - Bordas de decisão para os conjuntos de dados Cone-torus, Four-gauss, e R15, respectivamente. Figuras 7E, 8E e 9E apresentam os resultados do experimento Bordas de Decisão usando o método proposto. Figuras 7A, 8A e 9A representam resultados do experimento Bordas de Decisão usando OPF. Figuras 7B, 8B e 9B representam resultados do experimento Bordas de Decisão usando MCSVM. Figuras 7C, 8C e 9C representam resultados do experimento Bordas de Decisão usando MCSVMDBC. Figuras 7D, 8D e 9D representam resultados do experimento Bordas de Decisão usando MCSVM1VS. As regiões não brancas representam a região na qual uma amostra de teste seria classificada como a mesma classe das amostras com mesma cor. Todas as amostras nas regiões brancas seriam classificadas como desconhecidas.

[0091] Baseado nos resultados apresentados nas Figuras 7A-7E, 8A-8E, 9A-9E, o método proposto é o classificador melhor adaptado/ajustado para classificar as amostras de teste como desconhecidas. O método OPF (Figuras 7A, 8A, 9A) é fechado e não classifica amostras como desconhecidas. E enquanto os métodos baseados em SVM (Figuras 7B-7D, 8B-8D, 9B-9D) são capazes de classificar como desconhecidas apenas as amostras duvidosas entre as classes disponíveis, o método proposto (Figuras 7E, 8E, 9E) também evita classificar como conhecido as amostras distantes, pelo fato de limitar o espaço aberto de risco. Experimento 3 - Curva Conhecido-Desconhecido (Known-unknown curve)

[0092] Para melhor compreensão do impacto do limiar T (parâmetro de rejeição) definido pelo método proposto, foram realizados experimentos supondo cinco classes disponíveis de cada conjunto de dados (Caltech-256, ALOI, Auslan, 15-Scene, letter e eukbench), variando T de 0.0 (todas as amostras são classificadas como desconhecidas) a 1.0 (nenhuma amostra é classificada como desconhecida) variando em 0.005.

[0093] As Figuras 10A-10F apresentam os resultados desse experimento para cada conjunto de dados, com um gráfico de curvas que mostra o contrabalanço entre a precisão das amostras conhecidas (eixo x) e a precisão das amostras desconhecidas (eixo y). O ponto cruzado na curva indica o ponto de melhor precisão normalizada.

[0094] De acordo com os gráficos de todos os conjuntos de dados, é possível observar que o método proposto se comporta bem diante da mudança de parâmetro, ou seja, uma estimação razoável do limiar T (parâmetro de rejeição) garante um classificador para cenário aberto viável para uso em um cenário operacional. Aplicações gerais do método proposto e um exemplo detalhado de seu uso em um problema do mundo real

[0095] Conforme descrito, o método proposto pode ser usado para resolver problemas de classificação/reconhecimento em cenário aberto (que representa a maioria das aplicações e problemas do mundo real). Além disso, experimentos indicam que o método proposto supera outros métodos conhecidos no estado da técnica.

[0096] O método proposto pode ser aplicado para resolver qualquer aplicação/problema que requeira a negação/rejeição de alguns tipos de dados de entrada. Aplicações gerais de reconhecimento, que são inerentemente de cenário aberto (por exemplo: reconhecimento biométrico, reconhecimento de objetos, reconhecimento de cenas, reconhecimento de voz, reconhecimento de caracteres, reconhecimento de padrões, etc.) podem tirar proveito da presente invenção.

[0097] Por exemplo, o método proposto pode ser aplicado a problemas de biometria. O método reconheceria um número n de pessoas. Qualquer pessoa que não esteja entre as n pessoas conhecidas deve ser classificada pelo sistema biométrico como desconhecida, isto é, a pessoa não pode ser reconhecida como sendo uma das n pessoas conhecidas e deve ser rejeitada pelo método. Pode-se exemplificar o uso da invenção em um sistema de reconhecimento de face no qual há interesse em se reconhecer apenas um pequeno grupo de indivíduos. Por exemplo, considere a seguinte aplicação: o usuário tem a imagem de uma multidão e está interessado em encontrar três indivíduos específicos (por exemplo, três crianças perdidas). O usuário deve ter imagens de treinamento para os três indivíduos de interesse, e assim será capaz de treinar o método proposto para usá-lo em imagens de multidão (imagem de teste). Com o apoio de um algoritmo de localização de faces, cada face na multidão será classificada pelo método proposto como uma das três pessoas de interesse ou como desconhecido (nenhum dos três). Na abordagem usual de tratar o cenário aberto, o limiar é difícil de definir e é comum classificar muitas amostras desconhecidas como uma das classes treinadas. Ou seja, usando esse exemplo de reconhecimento de face, um método tradicional do estado da técnica iria classificar muitas faces da multidão como sendo a face de uma das três pessoas de interesse (a mais similar).

[0098] O método proposto também pode ser aplicado a problemas médicos. Muitos problemas médicos reduzem a questão de verificar se alguém está saudável ou não baseado em dados observados e opiniões de especialistas. Algumas doenças podem ser conhecidas a priori, mas em alguns casos o classificador pode não ter sido treinado com todas as possíveis manifestações de uma doença, devido à evidente limitação em se adquirir amostras de doenças dos mais diversos tipos. Além disso, é possível o surgimento de um novo tipo de doença e, em todos esses casos, o classificador deve avaliar se a pessoa avaliada está saudável ou não. Um exemplo específico de aplicação médica são os problemas oncológicos. Em casos reais, geralmente apenas algumas amostras de um número limitado de tipos de câncer estão disponíveis, porque é difícil obter dados de todas as possíveis variações da doença. O método da presente invenção pode ser treinado com os tipos de câncer conhecidos e, durante seu uso (fase de teste), se amostras desconhecidas (um tipo diferente de câncer) forem submetidas, o método deve ser capaz de classificá-las como desconhecidas, ao invés de classificá-las erroneamente como uma das classes (tipo de câncer) conhecidas; e se uma amostra conhecida (tipo de câncer) for submetida, o método também deve ser capaz de classificar como a classe conhecida correta. Outro problema é a classificação de visões do coração, em que o método deve ser capaz de classificar a visão da sonda da máquina como um dos pontos de vista em que o médico está interessado. Porém, algumas das visões podem não fazer sentido para aquele caso específico e é melhor que sejam classificadas como desconhecidas, como, por exemplo, as visões obtidas durante a transição de um ponto da sonda para outro. Além disso, novas máquinas de ultrassom são capazes de obter muita informação para o médico, por exemplo, construir um modelo 3D do coração baseado em visões ortogonais. Entretanto, nessas máquinas o operador deve especificar qual tipo de visões estão sendo usadas (por exemplo: visões apical quatro câmaras, duas câmaras, eixo longo e eixo curto paraesternal). Usando um método melhor para classificação de visões, o sistema da máquina de ultrassom possivelmente será capaz de usar as informações disponíveis das visões para construir o modelo 3D automaticamente, sem incomodar o operador sobre o tipo de cada visão e, consequentemente obter mais visões para usar nessa construção de modelo 3D.

[0099] O método proposto pode ser aplicado à predição de ações em casas inteligentes, em que o objetivo é reconhecer atividades dos indivíduos da casa a partir de diferentes sensores. Algumas pesquisas recentes sobre predição de ações em casas inteligentes e para saúde onipresente (u-healthcare) tratam sobre a classificação das ações dos usuários como uma das ações possíveis. Entretanto, ações inesperadas podem ocorrer (por exemplo, a queda de um idoso) e elas são muito diferentes entre si. Logo, um classificador capaz de reconhecer uma ação desconhecida é fundamental em tais aplicações. Nesse cenário, os classificadores para cenário fechado existentes sempre classificarão a ação de um indivíduo como uma das ações conhecidas. Consequentemente, ações inesperadas podem não ser identificadas. A abordagem usual para tratar o cenário aberto também não é muito confiável porque o limiar sobre a medida de similaridade é difícil de estimar e o classificador tende a classificar a amostra de teste como uma das classes conhecidas. Consequentemente, ações anormais podem passar desapercebidas. O método proposto serve para reconhecer a ação do usuário como uma das ações conhecidas/esperadas quando o indivíduo realmente executa uma delas, ou classificar a ação como desconhecida (ou seja, uma ação anormal).

[0100] O método proposto na presente invenção também pode ser aplicado ao problema de classificação de sensoriamento remoto de imagens para classificar imagens de entrada como contendo um dos padrões de interesse ou como desconhecida. Por exemplo, pode ser de interesse reconhecer cinco tipos de vegetação (floresta tropical, floresta subtropical, savana, mangue, pantanal) e os outros tipos de vegetação devem ser classificados como desconhecido pelo sistema. O método proposto permite esse tipo de classificação. Ao identificar que muitas das sub-regiões de uma grande região são desconhecidas (nenhum dos cinco tipos de vegetação mencionados), o sistema pode automaticamente inferir que a região provavelmente não pertence a um país específico (por exemplo, Brasil). Usar um classificador de cenário fechado ou a abordagem tradicional que trata o cenário aberto (baseado no limiar da medida de similaridade) faz com que o sistema tenda a classificar a amostra de entrada como uma das classes conhecidas disponíveis, levando a um erro de classificação.

[0101] O método proposto também pode ser usado para aplicações de segurança, em que o objetivo é permitir apenas processos não ofensivos. O comportamento normal pode ser bem conhecido pelo sistema de segurança. Por outro lado, o comportamento de ataque é mais raro, diferente dos comportamentos normais, e potencialmente muito diferentes entre si. Novas formas de ataque podem ser criadas a qualquer momento por criminosos e o sistema de segurança (usando o método proposto) deve identificar que eles não são processos com comportamento normal, ou seja, deve classificar o comportamento desse processo como desconhecido e rejeitá-lo.

[0102] O método proposto pode ainda ser aplicado à classificação de imagens não desejáveis (por exemplo, vídeos e imagens violentas ou pornográficas). Dado que o método tem categorias de cenas não desejáveis (imagens com sangue, explosão, brigas, corpos nus, etc.), seria capaz de corretamente classificar as cenas (amostras) de teste como um dos tipos conhecidos de cenas não desejáveis; e todos os outros tipos de imagens que potencialmente aparecerem devem ser classificados como desconhecidos.

[0103] O método proposto também pode ser aplicado ao reconhecimento de gestos e linguagem de sinais, em que apenas os sinais e gestos conhecidos devem ser reconhecidos, e qualquer outro tipo deve ser rejeitado.

[0104] O método proposto também pode ser aplicado a reconhecimento de voz, em que há muitos tipos de comandos que são conhecidos durante o treinamento do método. Porém, durante o uso do método (fase de teste), comandos de voz desconhecidos podem eventualmente surgir. O método proposto deve ser capaz de corretamente reconhecer os comandos de voz bem como ser capaz de corretamente rejeitar comandos desconhecidos.

[0105] O método proposto também pode ser aplicado ao problema de detecção de objetos e cenas, em que devem ser reconhecidos um grupo limitado de objetos, e todo o restante deve ser ignorado/rejeitado, isto é, classificado como desconhecido. Detecção de cenas e objetos é muito importante para diversos tipos de aplicação, como: reconhecimento de pontos de referência, geocodificação visual, recuperação de informação, etc. Podem-se imaginar aplicações embarcadas em celulares e dispositivos vestíveis em que o objetivo é reconhecer automaticamente as cenas e objetos próximos ao aparelho. O exemplo detalhado mais adiante mostra uma aplicação de detecção de cenas em um problema do mundo real.

[0106] As aplicações supracitadas não são exaustivas e muitas outras são possíveis, sempre que houver um problema em que apenas algumas poucas classes são conhecidas (disponíveis, consideradas) durante a fase de treinamento de um sistema de aprendizagem de máquina. O método proposto na presente invenção é capaz de tratar devidamente todos esses casos, ao contrário dos classificadores para cenário fechado. Exemplo detalhado de uso do método proposto em um problema do mundo real

[0107] Para melhor entendimento de seu potencial, será apresentado um exemplo detalhado de uso do método proposto em um problema do mundo real; no caso, um problema de reconhecimento de cenas. O reconhecimento de cenas é um problema de cenário muito aberto, pois existem incontáveis classes possíveis a se reconhecer, variando das mais genéricas (por exemplo: litoral, floresta, montanha, estrada, arranha-céus, cozinha, escritório, loja, etc.) às mais específicas (por exemplo, determinadas cidades: Rio de Janeiro, Seul, Nova Iorque, Londres, etc.). Nesse caso, os sistemas de reconhecimento não podem ser treinados com todas as classes de cenas existentes. Cenas que são desconhecidas na fase de treinamento, mas que aparecem durante o uso do método devem ser classificadas como desconhecidas em vez de serem classificadas erroneamente como uma das classes existentes/conhecidas.

[0108] Suponha uma pessoa usando o método de classificação/reconhecimento em óculos inteligentes, com o objetivo de obter informações sobre o local em que ela está (a cena). Quando essa pessoa vai a um determinado lugar, por exemplo, um estabelecimento famoso como Starbucks, os óculos inteligentes devem ser capazes de mostrar à pessoa a informação sobre a empresa, resenha de clientes, etc.

[0109] Para esse problema específico, há algumas coisas que um simples casamento de logotipo pode não resolver e um método de aprendizagem de máquina para cenário aberto é essencial, como será explicado a seguir. Se a pessoa vai a um estabelecimento ou ponto de referência não famoso, o sistema não seria capaz de reconhecê-lo se for baseado somente em casamento de padrões porque em um local não famoso não há logotipo ou algum sinal padrão bem estabelecido para ser reconhecido. Nesses casos é necessário usar um método mais genérico de aprendizagem de máquina. O método proposto trata esse problema porque todos os locais cadastrados em sua base de dados tem uma representação geral de cada classe, e quando a imagem do local é captada/processada pelos óculos inteligentes da pessoa, também é apresentada em uma representação geral. Assim o método da presente invenção é capaz de reconhecer a qual local, estabelecimento ou ponto de referência se refere a imagem captada, ou ainda reconhecer que a imagem captada não pertence a qualquer representação armazenada em seu banco de dados e assim avisar à pessoa que aquele é um local desconhecido (se for o caso).

[0110] Como exemplo, suponha que haja um conjunto de representações treinadas para três pontos de referência importantes da cidade do Rio de Janeiro (Cristo Redentor, Pão de Açúcar e estádio do Maracanã). Um turista visitando o Rio de Janeiro receberá mais informações sobre os três pontos de interesse ao capturar sua imagem usando óculos inteligentes ou um telefone celular. Porém, como o método não foi treinado para identificar outros pontos de interesse, quando o usuário/turista apontar para um local não visto anteriormente, deve-se automaticamente ignorar essa cena não a associando a um dos pontos de referência conhecido. Por exemplo, se o usuário/turista estiver em frente a outro estádio (por exemplo, estádio das Laranjeiras), o sistema deve reconhecer que não é o estádio do Maracanã e assim não apresentar informação errada ao turista/usuário.

[0111] Usando esse exemplo dos pontos de referência da cidade do Rio de Janeiro, a presente invenção funciona da seguinte maneira. Baseado na amostra/imagem de entrada X do estádio das Laranjeiras obtida, por exemplo, pelos óculos inteligentes, o método obtém a classe (Cristo Redentor, Pão de Açúcar e estádio do Maracanã) mais próxima/similar a X. Nesse caso, muito provavelmente a classe mais próxima/similar a X (estádio das Laranjeiras) será o estádio do Maracanã. A segunda classe mais próxima/similar a X também é identificada (suponha que, nesse caso, seja Pão de Açúcar). A medida de similaridade δ1 entre a representação de X (estádio das Laranjeiras) e a representação da classe estádio do Maracanã é obtida. A medida de similaridade δ2 entre a representação de X (estádio das Laranjeiras) e a representação da classe Pão de Açúcar também é obtida. Note que quanto menor a medida de similaridade, mais similares serão as duas representações comparadas, ou seja, δ1<δ2 porque o estádio do Maracanã é mais similar/próximo a X (estádio das Laranjeiras) do que o Pão de Açúcar. O método calcula a razão R = δ1/δ2 e compara R com T, sendo T um limiar entre 0 e 1 definido na fase de treinamento do método. Se R<T, o método classifica X como estádio do Maracanã. Se R>T, o método classifica X como desconhecido. Nesse caso, δ1 provavelmente será grande o suficiente para fazer com que a razão R tenda a 1 (consequentemente, R>T) e X (estádio das Laranjeiras) seria classificado como uma cena desconhecida pelo classificador. Obviamente, a medida de similaridade δ1 depende das características extraídas tanto da amostra/cena X quanto da classe estádio do Maracanã: se for extraída uma única característica, δ1 será pequeno porque X (estádio das Laranjeiras) e estádio do Maracanã possuem características visuais em comum (por exemplo, se vistos de cima em uma imagem aérea, ambos apresentam uma região de gramado verde). Entretanto, usando características apropriadas (capazes de captar as sutilezas da cena), a diferença entre X (estádio das Laranjeiras) e estádio do Maracanã se torna mais evidente (um maior valor de δ1).

[0112] Indo ainda mais além, o uso do método da presente invenção permite ao sistema de reconhecimento de cena dos óculos inteligentes atualizar seu banco de dados com novas entradas. Por exemplo, quando o usuário submete (mira) uma imagem/cena para classificação e o método contido nos óculos inteligentes a classifica como desconhecida, os óculos inteligentes podem enviar as informações de localização/GPS para um servidor/sistema. Quando muitos usuários tentam obter informações da mesma posição global e enviam essas informações de localização/GPS ao servidor, o sistema será capaz de descobrir uma nova classe e incorporá-la à sua base de dados. Certamente também seria possível que o próprio usuário enviasse informações sobre aquela imagem/cena, como por exemplo, o nome do lugar, telefone, etc. Uma vez que esse novo registro fosse incorporado à base de dados, quando um novo usuário tentar obter informação desse lugar, o lugar passaria a ser reconhecido (não seria mais considerado desconhecido).

[0113] Embora a presente invenção tenha sido descrita em conexão com certas concretizações preferenciais, deve ser entendido que não se pretende limitar a invenção àquelas concretizações particulares. Ao contrário, pretende-se cobrir todas as alternativas, modificações e equivalentes possíveis dentro do escopo da invenção, conforme definido pelas reivindicações em anexo.

Claims (12)

1. Método para classificação multiclasse aplicado a cenários abertos, dividido em fase de treinamento (1, 2 e 3) e fase de teste (4, 5, 6, 7), caracterizado por ser baseado em uma razão entre medidas de similaridade R = δ1/δ 2 e compreender os seguintes passos: - dividir (1) um conjunto de amostras de treinamento em n classes de interesse; - treinar um classificador multiclasse (2) usando as amostras divididas em n classes de interesse, de modo a obter os parâmetros intrínsecos; - obter um parâmetro de rejeição (3) T através da otimização de parâmetro; - receber uma amostra de teste (4) s; - encontrar as duas classes (5) c1, c2 mais similares à amostra de teste S entre as n classes treinadas; - calcular a razão R = δ1/δ2 das duas melhores medidas de similaridade (6), sendo δ1 a medida de similaridade/distância da amostra de teste S para a melhor classe c1 e δ2 a medida de similaridade/distância da amostra de teste S para a segunda melhor classe c2; - verificar (7) se a razão R das duas melhores medidas de similaridade (6) é maior que o parâmetro de rejeição T (3).

2. Método, de acordo com a reivindicação 1, caracterizado pelo fato de que a etapa de dividir as amostras do conjunto de treinamento (1) compreende dividi- las em um conjunto de ajuste e um conjunto de validação, a referida divisão sendo realizada da seguinte maneira: (i) apenas metade das classes disponíveis possui amostras representativas no conjunto de ajuste; (ii) para cada classe que possui amostras representativas no conjunto de ajuste, metade de suas amostras está no conjunto de ajuste e a outra metade está no conjunto de validação.

3. Método, de acordo com as reivindicações 1 e 2, caracterizado pelo fato de que a otimização de parâmetro (3) ajusta a classificação com base nas amostras do conjunto de ajuste para simular o cenário aberto, e executa um procedimento tradicional de grid search para encontrar o melhor valor para o parâmetro de rejeição T baseado nas amostras do conjunto de validação.

4. Método, de acordo com a reivindicação 1, caracterizado pelo fato de que a etapa de encontrar as duas melhores classes de ajuste compreende encontrar as duas classes c1, c2 mais similares à amostra teste S entre as n classes treinadas.

5. Método, de acordo com a reivindicação 1, caracterizado pelo fato de que o dito parâmetro de rejeição está compreendido entre 0.0 < T < 1.0.

6. Método, de acordo com a reivindicação 5, caracterizado pelo fato de que caso R > T na etapa de verificação da razão entre medidas de similaridade, a amostra teste S (4) é classificada como desconhecida.

7. Método, de acordo com a reivindicação 6, caracterizado pelo fato de que caso R < T na etapa de verificação da razão entre medidas de similaridade, a amostra teste S (4) é classificada como a melhor classe c1.

8. Método, de acordo com a reivindicação 1, caracterizado pelo fato de que compreende um número limitado de classes durante a fase de treinamento e um número qualquer de classes durante a fase de teste.

9. Método, de acordo com a reivindicação 1, caracterizado pelo fato de que adicionalmente compreende a etapa de identificar informações de uma classe desconhecida.

10. Método, de acordo com a reivindicação 5, caracterizado pelo fato de que o parâmetro de rejeição T sobre a razão das duas medidas de similaridade R = δ1/δ2 define uma região delimitada no espaço de características em que uma amostra de teste S é classificada como uma das classes treinadas/conhecidas, e uma região ilimitada complementar em que uma amostra de teste S é classificada como desconhecida.

11. Método, de acordo com as reivindicações 1, caracterizado pelo fato de que a medida de similaridade δ, compreende a função de custo fcost do OPF, métricas de distância do kNN, entre outras.

12. Método, de acordo com as reivindicações 1 a 6, caracterizado pelo fato de que pode ser aplicado a produtos e dispositivos gerais, tais como: smartphone, tablet, TV inteligente, relógio inteligente, óculos inteligentes e outros.

Images