Após a apresentação teórica dos diversos métodos bem como exemplos de aplicação, pretende-se nesta secção apresentar uma análise a cada um dos métodos, focando nomeadamente vantagens e desvantagens de cada um.
2.7.1 Método Todos-contra-todos
O número de problemas a classificar nesta abordagem é superior ao número de classes do problema original. Para além disso, k' cresce exponencialmente com k. No entanto, a criação dos modelos de decisão é simplificada pois os conjuntos de treino dos novos problemas baseiam-se em exemplos de apenas 2 classes. Garante-se assim que os conjuntos de treino B, deste método apresentam uma dimensão inferior ao conjunto de treino do problema inicial multi-classe.
Considere-se um problema de 4 classes, A, B, C e D. A decomposição resultaria em 6 problemas: A-B, A-C, A-D, B-C, B-D, C-D. Caso um exemplo de teste fosse da classe A, seria sempre classificado erradamente nos seguintes casos: B-C, B-D, C-D, num total de 3. Suponha-se que, no exemplo da Tabela 2-2, bA-B(a)=B. Nesse caso, a aplicação da função r(F') resultaria na classificação do exemplo como sendo da classe B.
Para um problema de 5 classes (A, B, C, D e E) existiriam 10 combinações possíveis. Se o exemplo de teste fosse da classe A, em 6 combinações seria classificado erradamente (contra o acerto máximo de 4).
Caso se tratasse de um problema com 10 classes, o número de combinações seria de 45. Dessas, apenas 9 poderiam classificar correctamente o exemplo, sendo que as restantes 36 o classificariam erradamente.
Uma potencial desvantagem da utilização deste método reside no aumento de probabilidade de um exemplo ser mal classificado à medida que aumenta o número de classes k no problema original.
Número de classes n no problema original Número de problemas m bi-classe gerados Número de problemas que, garantidamente. farão classificação errada Número máximo de problemas que farão classificação correcta 3 3 1 2 4 6 3 3 5 10 6 4 6 15 10 5 7 21 15 6 10 45 36 9 20 190 171 19 24 276 253 23 k
k(k-\)
2
(k-l)(k-2)
2
k-1Tabela 2-8 - todos-contra-todos para n classes
Simultaneamente, à medida que o número de classes k aumenta, o número de problemas que garantidamente farão uma classificação errada aumenta igualmente e de forma exponencial. O esforço de cálculo é aplicado cada vez mais a resolver problemas que é sabido serem inúteis em termos de obtenção de uma classificação final correcta.
O método de reconstrução apresentado em 2.4.1.1 permite amenizar esta desvantagem através da utilização de probabilidades [5]. Por exemplo: se se estiver perante um exemplo da classe C e o modelo de decisão for bA.B(a), a predição será A ou B e obviamente errada. No entanto, espera-se que
a probabilidade de ser A ou B seja relativamente semelhante, isto é, a diferença das probabilidades seja baixa. Já se o modelo de decisão for bA-c(a) espera-se que a probabilidade de ser da classe C seja
muito superior à probabilidade de ser da classe A. Assim, para além de permitir uma diminuição no peso final de uma predição errada, todos os problemas contribuem para a solução final.
2.7.2 Método Um-contra-todos
Neste método, o número de problemas bi-classe é igual ao número de classes do problema multi- classe. Logo, o crescimento do número de problemas bi-classe é linearmente proporcional ao número de classes do problema multi-classe k. A dimensão do conjunto de treino B, é igual para todos os problemas bi-classe. Simultaneamente, estes apresentam a mesma dimensão do conjunto de treino do problema multi-classe.
Para além disso, é possível garantir que todos os problemas contribuem para a obtenção da predição final. Esse foi o objectivo por detrás no método de votação atrás exposto (Secção 2.4.2), nomeadamente o apresentado no Algoritmo 2-1.
Não obstante, quando a distribuição das classes é muito desigual (pouco uniforme) este método apresenta algumas desvantagens. A existência de classes com baixa frequência implica que existam poucos exemplos de treino pertencentes a essas classes que permitam a construção dum modelo de predição suficientemente robusto. Mesmo nas situações de distribuições relativamente uniformes, será sempre uma classe contra £-1 classes, conduzindo a uma maior probabilidade de erro com o aumento do número de classes do problema original. Também neste caso, a utilização de probabilidades na fase de reconstrução (2.4.2.1) poderia amenizar estas desvantagens.
2.7.3 Método ECOCs
Neste método, a dimensão dos vários conjuntos de treino B, é a mesma do conjunto de treino do problema multi-classe. O número de modelo de decisão bi-classe necessários é dado pelo tamanho da palavra binária e. Este valor está dependente do número de classes do problema original mas apenas para a definição dos limites mínimos e máximos (expressões (15) e (16)). Dentro deste intervalo, qualquer valor pode ser usado.
Se por um lado temos a vantagem de poder definir o número de problemas bi-classe a gerar no modelo, temos, por outro lado, um crescimento exponencialmente deste número com o número de classes k, complicando essa escolha. Sintetizando, temos:
k tamanho min e tamanho max e
3 2 3 4 2 7 5 3 15 6 3 31 7 3 63 10 4 511 24 5 8 388 607 k log 2 k~\ 2 * " 1- !
Consequentemente, uma das questões que surge associada à utilização ecoes é saber, dado um problema de k classes, qual o melhor tamanho para a palavra binária.
Para além disso, as palavras binárias (cw) devem respeitar algumas regras nomeadamente: - inexistência de palavras binárias equivalentes
\/iJ,cwl^cwj (32)
inexistência de colunas iguais
Vu,cwTi *cWj (33)
inexistência de colunas complementares
V,,> cw7,-cw',* [l] (34)
nenhuma colunas apenas com 0 ou 1.
V , , C M / , * [ I ]
V,.,cw7'/ *[0] ( 3 5 )
Encontrar um conjunto de k palavras binárias de dimensão e que respeitem estas propriedades não é um problema trivial.
2.7.4 Discussão
A decomposição através do método um-contra-todos conduz a um menor número de problemas bi- classe do que no método todos-contra-todos, podendo-se obter aqui ganhos de eficiência tanto na criação dos modelos de decisão, bem como na aplicação desses modelos aos exemplos de teste.
A aplicação do método todos-contra-todos permite construir modelos de decisão mais eficientemente graças à utilização de conjuntos de treino reduzidos no número de exemplos. No entanto, o número de problemas bi-classe gerados é superior ao método um-contra-todos e cresce exponencialmente com k.
Em [2] demonstra-se que a complexidade do método todos-contra-todos é linear ao número de classes (e não exponencial como a expressão (13) faz crer) e, simultaneamente, é inferior ao do método um-contra-todos.
Considere-se o tempo necessário de aprendizagem de um determinado algoritmo para um conjunto de treino com n exemplos como uma função f(n).
Defina-se como gb\f(k,n) a complexidade total resultante de usar um algoritmo h de complexidade
Considere-se o custo como a performance de um algoritmo a num problema bi-classe decomposto a partir de problema de k classes (k>2) relativamente à performance do mesmo algoritmo num problema simples de duas classes e da mesma dimensão n:
7taU{k,rí)= u (36)
Para o método um-contra-todos, existem k problemas de aprendizagem, usando cada um deles a totalidade de exemplos n.
Então a complexidade é
gua\f(k>n) = ¥{n) (37)
E o custo será
x»c<\f(k,n) = k (38)
No caso do método todos-contra-todos, cada exemplo será usado k-1 vezes, ou seja, uma vez em cada umas das k-\ que a classe a que o exemplo pertence será comparada com as restantes. Para um conjunto de treino tem dimensão n, o número total de exemplos utilizados será (k-\)n.
Para algoritmos de aprendizagem com complexidade linear no número de exemplos O(n)2, temos que f1(n)=Ãn, isto é, o somatório da complexidade de diversos problemas é igual á complexidade de
um problema único com a dimensão dos diversos problemas referidos:
E / i ^ ) = /i(Z^) (39)
A complexidade do método todos-contra-todos é:
Í W , (*. ") = /i « * -1)») = Mk - \)n = (* - \){Án) = (k-1)/, (n) ( 4 0)
Logo, o custo é:
^ d / , (£) = £ - ! (41)
Para o caso de árvores de decisão, com complexidade 0(n\og(n)), fi(n)=nlog(n) e a complexidade do método todos-contra-todos é agora:
W , &> ") = -/i ((* - !)") = (* " ! ) " • l o8 ( ( * - !)") = »/i ( * " ! ) + ( * - 1 ) / , (") (42)
O custo é:
>W, (*) = * - !
log(n)
(43)Considerando que n » k ■=> tenderá para 0, pelo que ;r lf (A:) « (A: - 1 ) . log(«)
Conforme se pode concluir, o custo do método todos-contra-todos é inferior ao do método ura- contra-todos e portanto mais vantajoso.
Resumidamente, o número de problemas bi-classe gerados em cada um dos 3 métodos será:
k todos-contra-
todos um-contra-todos
ecoe
k todos-contra-
todos um-contra-todos tam. min tam. max
3 3 3 2 3 4 6 4 2 7 5 10 5 3 15 6 15 6 3 31 7 21 7 3 63 10 45 10 4 511 20 190 20 5 524 287 24 276 24 5 8 388 607 k
k(k-l)
2
kflog
2k]
2*"
1-!
Tabela 2-10 - Comparativo do número de problemas bi-classe gerados nos diversos métodos
Note-se que o número de modelos de decisão bi-classe resultantes da decomposição do método um-contra-todos é inferior ao número de modelos de decisão resultantes da decomposição pelo método todos-contra-todos (excepto para k=3 onde é equivalente).
No caso dos ecoes, o número de modelos de decisão criados depende da dimensão das palavras binárias varia entre:
— máximo: superior ao do método todos-contra-todos (excepto para k=3 onde é equivalente).
Em termos de resultados na classificação, o método um-contra-todos poderá apresentar algumas vantagens caso a função de reconstrução r(F') utilizada seja a exposta no Algoritmo 2-1, uma vez que todos os problemas contribuem para a obtenção da predição final.
Para além disso, a utilização de probabilidades nos diversos métodos poderá melhorar o comportamento destes.
A grande vantagem dos ecoes está na versatilidade do número de problemas a gerar e na possibilidade de representar os outros métodos referidos (todos-contra-todos e um-contra-todos).
De facto, para o caso de 4 classes, poder-se-ia ter as seguintes palavras binárias de dimensão 6:
b,(a) b2(a) b3(a) b4(a) b5(a) b6(a) A cwi Classe original é substituída por 1 1 1 0 0 0 B cw2 Classe original é substituída por -1 0 0 1 1 0 C cw3 Classe original é substituída por 0 -1 0 -1 0 1 D cw4 Classe original é substituída por 0 0 -1 0 -1 -1
Tabela 2-11 - Representação com palavras binárias do método todos-contra-todos
Se considerarmos que os bits a 0 não devem ser tidos em conta na criação do modelo de decisão estaremos presente um modelo tipo todos-contra-todos:
- b](a) - Exemplo é da classe é A ou B - b2(a) - Exemplo é da classe é A ou C - b3(a) - Exemplo é da classe é A ou D - b4(a) - Exemplo é da classe é B ou C - b5(a) - Exemplo é da classe é B ou D - bô(a) - Exemplo é da classe é C ou D
Neste caso, a função de reconstrução também deveria ser alterada, passando a ser:
d(cwf,cwl) = Yj \cwf,j-w,,j ,cwfJ,cwtJ * 0 (44)
7=1
Resultaria que quando os bits fossem iguais e ambos diferentes de zero, a distância de Hamming seria 0. Quando os bits fosses diferentes entre eles e simultaneamente diferentes de 0, a distância seria 1. Caso um dos bits fosse 0, não seria efectuado qualquer cálculo. É uma expressão que apresenta em termos práticos os mesmos resultados de expressão (28) ignorando as distâncias em que um dos bits seja 0.
Para o método um-contra-todos a representação por ecoes seria
b,(a) b2(a) b3(a) b4(a)
A cwi Classe original é substituída por 1 0 0 0 B cw2 Classe original é substituída por 0 1 0 0 C cw3 Classe original é substituída por 0 0 1 0 D cw4 Classe original é substituída por 0 0 0 1
Tabela 2-12 - Representação com palavras binárias do método um-contra-todos Teríamos:
- bi(a) - Exemplo é da classe é A ou outra - b2(a) - Exemplo é da classe é B ou outra - b3(a) - Exemplo é da classe é C ou outra - b/t(a) - Exemplo é da classe é D ou outra
Neste caso específico, a função de reconstrução r(F') teria como base a distância de Hamming, e não uma votação (conforme a função de reconstrução apresentada em 2.4.2) fazendo com que o resultado de cada problema bi-classe fosse tratado de forma independente. Esta situação poderia conduzir a resultados ligeiramente diferentes do método um-contra-todos.
Os ecoes construídos de forma a representar o método um-contra-todos apresentam uma capacidade de correcção de erros nula, isto é, não são capazes de corrigir erros de classificação que eventualmente ocorram.
Logo, uma das vantagens dos ecoes provém da sua versatilidade e da capacidade de representar os outros dois métodos de decomposição apresentados.
Finalmente, em [29] é demonstrado que a decomposição por ecoes e reconstrução com base na distância de Hamming (associada a ecoes) permite reduzir tanto o desvio como a variabilidade das soluções.