Combinação de classificadores – Máquinas que aprendem (MAp)

Seleção dinâmica de one-class classifiers

Mesmo sendo desenvolvidos para problemas que tenham apenas dados de uma classe, one-class classifiers (OCCs) também podem ser usados para tarefas que possuem várias classes. Nesse caso, um OCC é treinado para cada classe. Logo, para uma tarefa com n classes, n OCCs serão treinados. A classificação de uma nova instância é realizada da seguinte forma: essa instância é fornecida como entrada para cada um dos OCCs e sua classe é definida como a classe do OCC que responder com maior certeza.

Entretanto, quando uma nuvem de instâncias é multimodal, ou seja, quando essa nuvem possui mais de um grupo, boa parte dos OCCs não consegue lidar com essa dificuldade. Suponha que os pontos vermelhos na figura (a) acima pertençam à classe target e os pontos verdes à classe outlier. Vale destacar que durante o processo de treinamento do OCC, apenas os pontos vermelhos estão disponíveis. Assim, os pontos em verde são mostrados na figura apenas para fins de ilustração. A elipse em preto representa o classificador OCC e engloba todos os pontos vermelhos, dividindo a área do espaço de características em duas: target (dentre da elipse) e outlier (fora da elipse). Nessa figura, é possível notar que vários exemplos da classe outlier estão localizados dentro da região delimitada pelo OCC e, por consequência, esses pontos são incorretamente classificados como pertencentes à classe target. Nota-se também que as instâncias em vermelho compõem uma classe multimodal, ou seja, formada por várias modas/grupos.

Uma alternativa para lidar com essa multi-modalidade é criar várias meta-classes, uma para cada grupo, e treinar um OCC por grupo. Logo, uma nuvem de pontos (uma classe) será representada por vários OCC, um para cada meta-classe ou grupo. O desafio é definir o número de grupos em uma nuvem de pontos e, para esse fim, pode-se usar cluster validity indices para estimar este número.

Entretanto, não existe um índice (cluster validity index) que consiga definir de maneira precisa todos os grupos de qualquer nuvem de pontos, pois tal tarefa depende da medida de distância usada, da estrutura dos dados e de outras características. Em outras palavras, um dado índice pode ser a melhor escolha para uma classe e não ser para outra. Logo, esse mapeamento, do melhor índice por classe, é um problema em aberto. Além disso, quando os cluster validity indeces são aplicados a uma dada nuvem de pontos, eles podem separar essa nuvem de maneiras diferentes. Por exemplo, o índice Silhouette pode indicar que a nuvem possui 3 grupos, enquanto o índice NbClust pode indicar 5 grupos.

Diante deste contexto, foi proposto o método One-class Classifier Dynamic Ensemble Selection for Multi-class problems (MODES) que é um sistema de seleção dinâmica de classificadores para tarefas multi-classe. O MODES usa vários índices e treina um OCC para cada grupo definido por cada um dos índices. Essa estratégia permite que a diversidade das informações extraídas pelos índices seja incorporada ao sistema através do treinamento de vários OCCs. Por exemplo: a figura (b) ilustra que um dado cluster validity index encontra dois grupos; assim, dois OCC são treinados, um para cada grupo. Já outros cluster validity indexes encontram 4 e 5 grupos, como mostrado nas figuras (c) e (d), respectivamente; e, mais nove OCCs são treinados. Assim, cada OCC torna-se um especialista em uma determinada área do espaço de caraterística e minimiza o erro de classificar um outiler como target, como ocorre na figura (a).

Vale destacar que no MODES cada classe é tratada individualmente, logo, desbalanceamento entre as classes não é uma preocupação. Além disso, estratégias que decompõem as classes, como é o caso do MODES, podem se apresentar como alternativas interessantes para incremental learning e para open-set recognition.

O MODES propõe uma abordagem capaz de lidar com dados que possuem distribuições complexas usando uma estratégia que seleciona dinamicamente os OCCs mais competentes para cada uma das instâncias de teste.

Rogério CP Fragoso, George DC Cavalcanti, Roberto HW Pinheiro, Luiz S Oliveira. Dynamic selection and combination of one-class classifiers for multi-class classification. Knowledge-based Systems, 2021.

Normalização dos atributos & Desempenho dos classificadores

Pré-processar os dados, antes de treinar uma máquina de aprendizagem, é uma etapa vital para se conseguir extrair o melhor de cada máquina. São várias as formas de pré-processar os dados e esta tarefa depende da aplicação em investigação. Por exemplo: em processamento de linguagem natural, é comum realizar a tokenization que objetiva separar sentenças em unidades menores, tais como palavras.

O foco desta post é o pré-processamento dos atributos com o objetivo de colocá-los em uma mesma escala, ou dentro de um mesmo critério, com o intuito de minimizar a influência indevida de um atributo sobre o outro. Esta tarefa é realizada por técnicas de scaling, muitas vezes chamadas de normalização.

Min-max scaler é a mais utilizada e difundida técnicas de scaling. Nela, cada um dos atributos é ajustado para caber em um intervalo, geralmente, entre 0 e 1. Outras técnicas de scaling permeiam as aplicações e, entre elas, destaco: standard scaler, maximum absolute scaler, robust scaler e quantile transformer.

Diante desse contexto com várias técnicas de scaling e vários classificadores, alguns questionamentos emergem:

Vale a pena normalizar os dados?
A escolha da técnica de scaling influencia no desempenho dos modelos de aprendizagem?
Qual técnica escolher para um dado classificador?
Quais classificadores são mais sensíveis às escolhas das técnicas de scaling?

Estas e outras questões são abordadas no artigo de Amorim et al. que realiza uma ampla avaliação usando 82 bancos de dados públicos e cinco técnicas de scaling. Foi mostrado que escolher bem a técnica de scaling melhora a precisão de classificadores. Em particular, algoritmos baseados em árvores de decisão são pouco sensíveis à escolha da técnicas de scaling. Logo, em alguns casos, não normalizar pode ser a melhor opção.

O nível de desbalancamento do banco de dados é um fator que influencia a escolha da técnica de scaling. O standard scaler obteve melhor desempenho em bancos de dados com baixos níveis de desbalanceameto, enquanto o quantile transformer apresenta-se como a melhor escolha para os níveis médio e alto de desbalanceamento.

Os autores também ressaltam que a melhor técnica de scaling para um sistema de múltiplos classificadores coincide com a melhor técnica empregada por seu classificador-base. Assim, a definição da melhor técnica de scaling, para um sistema de múltiplos classificadores, pode ser realizada avaliando o comportamento das técnicas em um classificador-base, o que torna todo o processo mais rápido e barato.

Sabendo que o emprego de técnicas de scaling é bastante negligenciado nas mais diversas aplicações, Amorim et al. colocam luz nesta questão e mostram que devemos ficar alertas em relação a esse ponto sensível, pois a escolha da técnica influencia significativamente o desempenho de modelos de classificação.

Lucas B.V. de Amorim, George D.C. Cavalcanti, Rafael M.O. Cruz, The choice of scaling technique matters for classification performance, Applied Soft Computing, 2023.

Etapas de um sistema de múltiplos classificadores

Um sistema de múltiplos classificadores (multiple classifier system — MCS) é composto por um pipeline de três etapas: geração, seleção e integração — conforme mostrado na figura a seguir.

mcs — Etapas de um sistema de múltiplos classificadores. [adaptada de Cruz et al. 2018]

Pode-se observar essas três etapas de um MCS como uma caixa-preta que recebe como entrada um conjunto de treinamento (Γ), um conjunto validação e uma instância de teste (x_q), e que fornece como saída, a classe (no caso de classificação) ou o valor predito (no caso de regressão ou previsão de séries temporais) da instância de teste. Da mesma forma que máquinas de aprendizagem monolíticas (árvore e decisão, redes neurais, entre outras), um MCS busca uma função capaz de predizer com eficácia o rótulo das instâncias que lhe são apresentadas durante a generalização. A seguir, são descritas as três etapas de um MCS.

Geração

Na primeira etapa, geração, as máquinas de aprendizagem são treinadas e armazenadas em um pool C que pode ser homogêneo ou heterogêneo. Por homogêneo, entende-se que todos os modelos do pool são treinados usando o mesmo algoritmo de aprendizagem, e.g., árvore de decisão. Por outro lado, em um pool heterogêneo, os modelos são treinados com diferentes algoritmos, tais como: árvore de decisão, perceptron e redes neurais.

Usar algoritmos diferentes é uma forma de aumentar a diversidade do pool; sendo essa uma vantagem de um pool heterogêneo. Porém, escolher quais algoritmos de aprendizagem devem ser usados, e quantos, é um problema desafiador. Daí, gerar um pool homogêneo é uma alternativa interessante por sua simplicidade.

Mesmo trabalhando com um pool homogêneo, é necessário que os modelos desse pool sejam diversos. Bagging (bootstrap aggregating) é um algoritmo comumente usado para esse fim e funciona da seguinte forma: dado um banco de dados de treinamento (Γ) com n instâncias, bagging gera m bancos de dados usando reamostragem com reposição. Cada banco de dados gerado tem o mesmo número de instâncias (n) do banco de dados original. Mas, como bagging é um procedimento com reposição, cada banco de dados terá instâncias repetidas. É esperado que 63,2% sejam instâncias únicas de Γ, e que, o restante, 36,8%, seja composto de instâncias repetidas. Cada um dos bancos de dados gerado por bagging é usado para treinar um modelo. Assim, ao fim do processo, m modelos são treinados, C = {c₁, c₂, …, c_m}.

Dado que bagging usa um processo aleatório para adicionar instâncias a cada um dos bancos, pode-se afirmar, com alta probabilidade, que os bancos gerados são diferentes entre si. Diferença essa que auxilia na geração de modelos diversos. Além do bagging, outros algoritmos são usados para gerar o pool, entre eles: boosting, random subspace e rotation forest.

Seleção

Após a geração, a próxima etapa tem o objetivo de selecionar um subconjunto de modelos do pool que será usado para predizer a classe/valor da instância de teste. A seleção pode se dar de duas formas: estática ou dinâmica.

Seleçao estática [adaptada de Cruz et al. 2018]

A seleção estática (static selection – SS) escolhe os melhores modelos do pool C que comporão o ensemble de modelos C’, sendo C’ ⊂ C. A figura acima mostra que esse processo é realizado offline, ou seja, durante o treinamento, e usa o conjunto de validação como guia para a escolha dos modelos. Na seleção estática, o mesmo subconjunto de modelos C’ é usado para classificar/predizer todas as instâncias de teste (x_q).

Já na seleção dinâmica, os modelos selecionados podem diferir de uma instância de teste para outra; por esse motivo é chamada de dinâmica. Essa operação de seleção é realizada online, quando o sistema completo já está em operação, e depende da instância de teste que se deseja avaliar.

dcs — Seleção dinâmica de um modelo (c_i) por instância de teste (x_q) [adaptada de Cruz et al. 2018]

des — Seleção dinâmica de um *ensemble* (C’) por instância de teste (x_q) [adaptada de Cruz et al. 2018]

As duas figuras acima mostram formas de selecionar dinamicamente modelos: a primeira seleciona apenas um modelo por instância de teste, enquanto a segunda seleciona um ensemble, um subconjunto do pool inicial.

A seleção dinâmica é motivada pelo fato de que nem todos os modelos no pool são competentes para predizer o rótulo de todas as instâncias de teste. Assim, deseja-se encontrar, por instância, os melhores especialistas (modelos) para realizar essa predição.

Integração

A etapa de seleção pode escolher um ou mais modelos. Se apenas um modelo for selecionado, não há integração. Nesse caso, a resposta do sistema é dada pela aplicação do modelo selecionado à instância de teste, i.e., c_i(x_q).

Sob outra perspectiva, se mais de um modelo for selecionado, é necessário o emprego de alguma regra para combinar as respostas dos modelos. Essas regras podem ser divididas em duas categorias: treináveis e não-treináveis. As não-treináveis levam esse nome pois são regras fixas que não necessitam de um processo de treinamento. Nessa categoria, o voto majoritário é a regra mais empregada. Nesta regra, cada modelo vota em uma classe e a classe com mais votos é atribuída como sendo o rótulo da instância de teste. Outros exemplos de regras não-treináveis são: média, produto, soma, mínimo e máximo.

Como o próprio nome indica, as regras treináveis são definidas por um processo de treinamento. Assim, usam-se máquinas de aprendizagem com o propósito de aprender a melhor função que integrará as respostas dos modelos selecionados. Qualquer máquina de aprendizagem pode ser usada para esse fim, e.g., árvore de decisão e multi-layer perceptrons.

Quando não se sabe a priori quantos modelos serão escolhidos pela etapa de seleção, as regras não-treináveis são mais usadas do que as treináveis, pois a maioria das máquinas de aprendizagem requerem um vetor de características de tamanho fixo. Além disso, as regras não-treináveis são mais simples e, por conseguinte, mais fáceis de interpretar.

Combinação de classificadores: uma introdução

Ao treinar uma máquina de aprendizagem, muitos desafios espreitam o horizonte, entre eles: overfitting. Uma das alternativas para minimizar overfitting é escolher a máquina correta para a tarefa que se deseja resolver. Por exemplo: se tivermos poucos dados disponíveis, uma rede neural artificial pode não ser a melhor escolha; embora existam estratégias para gerar dados artificiais e aumentar a quantidade de dados de treinamento, tais como oversampling e data augmentation. Uma escolha mais apropriada seria um algoritmo de instante-based learning, e.g., k-nearest neighbor.

Escolher o melhor algoritmo de aprendizagem, por tarefa, é uma problema em busca de solução. Muitas abordagens que se valem de meta-learning já foram propostas, mas ainda existe muito terreno a percorrer nesse campo. Essa é uma pesquisa bem interessante e motivada, também, por um teorema de nome engraçado, mas, extremamente importante para a área, chamado de no free lunch theorem. Esse teorema nos indica que não existe uma máquina de aprendizagem que seja a melhor para todas as tarefas. Ou seja, cada tarefa tem suas peculiaridades que devem ser melhor resolvidas por máquinas que tenham características distintas. Nota: um teorema é uma afirmação provada como verdadeira; logo, essa difere de uma mera opinião.

Consequentemente, é responsabilidade do especialista em aprendizagem a escolha da melhor máquina para resolver uma nova tarefa. Mas, existe outra alternativa…

Se para cada tarefa, uma máquina deve ser escolhida, por que não unir esforços e juntar várias máquinas para resolver essa tal tarefa? Vox Populi, Vox Dei. Esse “poder das multidões” (wisdom of the crowd) é a premissa da área de Combinação de Classificadores (ensemble learning) que possui vários nomes, tais como: sistemas de múltiplos classificadores e máquinas de comitê. Esses sistemas combinam máquinas com o intuito de melhorar a precisão geral do sistema, fundamentando-se no argumento de que a junção das opiniões de um grupo de indivíduos é melhor do que a opinião de apenas um indivíduo.

Em um experimento, no início do século vinte, Sir Francis Galton — o mesmo que desenvolveu um método eficiente para classificação de impressões digitais — combinou a resposta de 787 pessoas que estimaram o peso de um boi morto e vestido. Ao calcular a média das respostas de todos os participantes, Galton observou que o erro foi menor do que um porcento (link). Ao invés de combinar as respostas de todos, Galton poderia ter escolhido o indivíduo mais competente para estimar o peso. Entretanto, essa escolha não seria uma tarefa trivial, da mesma forma que, escolher a melhor máquina de aprendizagem, por tarefa, não é uma tarefa simples. Assim, ao combinar todas as respostas, a probabilidade de escolher um indivíduo incompetente foi minimizada.

É inútil combinar máquinas que tenham o mesmo comportamento, ou seja, máquinas que acertem e errem as mesmas instâncias. Assim, ao juntar várias máquinas em um pool, é esperado que elas tenham um excelente desempenho em partes diferentes do espaço de características. Em outras palavras, é fundamental que as máquinas sejam diversas entre si. Existem várias maneiras de se obter diversidade, entre elas: usar diferentes algoritmos de aprendizagem e usar dados diferentes para treinar cada uma das máquinas.

Razões para combinar máquinas

Os aspectos que fortalecem o uso de estratégias de combinação de classificadores podem ser aglutinados em: estatístico, computacional e representacional. A figura ao lado é usada para explicar esses três aspectos. reasons-mcs Nela, vê-se que o “espaço dos bons modelos”, para uma dada tarefa, é um subconjunto do “espaço dos modelos”. Esses modelos são máquinas de aprendizagem, de classificação ou de regressão, que foram treinadas com dados de uma tarefa específica. Além disso, o asteriscos (∗) representa o classificar ideal, os círculos (•) são os classificadores individuais e o triângulo (Δ) representa a combinação dos classificadores (ensemble). Objetiva-se obter um modelo o mais próximo possível do modelo ideal (∗). Nota: essa figura foi adaptada da figura 3.2 do livro da Kuncheva, 2014.

Estatístico

Na figura que mostra o aspecto Estatístico, percebe-se que o modelo combinado (Δ) está bem mais próximo do modelo ideal (∗) do que a maioria dos modelos individuais (•). Vale salientar que o modelo combinado não é o melhor, pois existe pelo menos um modelo (•) que está mais próximo do modelo ideal do que o modelo combinado. Entretanto, por melhor que seja o seu procedimento experimental, a incerteza relacionada à precisão do modelo, aferida durante o treinamento, pode levar a escolha de um modelo inadequado. Assim, ao combinar os modelos, minimiza-se a chance de selecionar um modelo ruim.

Computacional

Durante o treinamento, um modelo é levado do “espaço dos modelos” para o “espaço dos bons modelos” — conforme mostrado pelas curvas em cinza na figura do aspecto Computacional. Cada um desses modelos (•) deve se posicionar em um mínimo local diferente da superfície de erro. Logo, a combinação desses modelos diversos gerará um modelo mais próximo do modelo ideal.

Representacional

Suponha que todos os modelos individuais (•) sejam lineares e que a tarefa, que se deseja resolver, seja não-linearmente separável. Logo, nenhum modelo, cuja representação é linear, será capaz de modelar essa tarefa. Por outro lado, ao combinar modelos lineares, regiões não-lineares podem ser modeladas. Assim, na figura que mostra o aspecto Representacional, percebe-se que o modelo combinado (Δ) está fora do “espaço dos modelos”, pois todos os modelo desse espaço são lineares e o alvo é um modelo não-linear que pode ser alcançado combinando modelos lineares. De maneira geral, regiões complexas de bordas entre classes podem ser modeladas usando modelos simples.

No próximo post, arquiteturas de combinação de classificadores — estática e dinâmica — serão discutidas.