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 (xq), 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 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 = {c1, c2, …, cm}.

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: boostingrandom subspace 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.

ss
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 (xq).

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 (ci) por instância de teste (xq) [adaptada de Cruz et al. 2018]
des
Seleção dinâmica de um ensemble (C’) por instância de teste (xq) [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., ci(xq).

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 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. vox-populi-vox-dei3Esse “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-mcsNela, 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.