Umas das principais ferramentas na nossa caixa de ferramentas de reconhecimento de padrões certamente vem dos classificadores de padrões.
Então para começarmos nossa jornada, vamos entender alguns conceitos fundamentais.
Classificação de Padrões
Imagine um cenário onde temos diversas amostras separadas em diferentes grupos.
De forma bastante simples, qualquer pessoa mesmo que não conheça pokémon, é capaz de encontrar algum padrão na organização desses grupos. E, com isso, incluir uma nova amostra em um desses grupos.
Esse processo de identificar um padrão, e aprender a organizar novas amostras, seguindo o padrão pre-estabelecido é conhecido como classificação de padrões.
De forma mais simples, dado um conjunto de amostras que representem um problema que queremos aprender, as quais vamos chamar de base de treinamento, e aplicar essa mesma regra de organização para qualquer outra amostra nova que também pertença a essa população, num processo conhecido como predição.
Agora como podemos criar uma forma automática capaz de encontrar padrões, aprender seu processo de construção, e aplicar essa regra a novas amostras desconhecidas?
Magia arcana e matemática, são as principais abordagens utilizadas nessa tarefa. Devido a restrições de tempo, por hora vamos usar matemática para resolver esse problema.
Mais especificamente, vamos usar probabilidade, e um conceito conhecido como Teorema de Bayes.
Base de treinamento
Para os nossos exemplos, vamos trabalhar com a base de dados de classificação de flores Iris, onde dadas as informações de comprimento e largura das sépalas e pétalas, aprendemos a distinguir entre Iris setosa, Iris virginica e Iris versicolor.
Classificadores Probabilísticos
O mesmo conceito pode ser descrito, ainda de forma bem superficial, com uma abordagem um pouco mais formal. Afinal, o que é a nossa amostra? Para propositos práticos, vamos representar nossas amostras matematicamente como um vetor de características numericas (ao menos por enquanto). Dessa forma cada amostra \(x\) é representada como um ponto na dimensão \(R^n\), ou seja, \(x\in\mathbb{R}^n\). Cada uma dessas amostras, como comentamos anteriormente, é divida entre \(C=\{c_1,c_2,\dots,c_c\}\) classes distintas, onde um rótulo \(y\in C\) representa o grupo ao qual essa amostra pertence.
Agora, pensando numa abordagem probabilística, nosso classificador pode ser definido como a probabilidade
para cada uma das classes em \(c\).
Auxílio Alzheimer: P(A|B) significa a probabilidade condicional de A dado B. Que nos dá a probabilidade de um evento A ocorrer, dado que um evento B já ocorreu.
Teorema de Bayes
De forma muito simplificada, o teorema de Bayes nos permite calcular uma probabilidade condicionada a um evento, a partir de informações de probabilidade que conhecemos.
Ok, muito vago.
Então, vamos definí-lo de forma mais clara.
Basicamente, o teorema de Bayes nos permite calcular a probabilidade de um evento condicional, desde que conheçamos a probabilidade de cada evento isolado -> \(P(A) \)e \(P(B)\), bem como a probabilidade da condicional inversa -> \(P(B|A)\).
Num cenário de classificação de padrões, isso nos permite descrever a probabilidade de uma amostra pertencer a uma determinada classe \(c\), como:
Isso significa que conseguimos construir um classificador probabilístico desde que possamos calcular os valores (ou uma aproximação) das probabilidades dos eventos base \(P(y=c_i),P(x)\ e\ P(x|y=c_i)\).
Agora que temos a estrutura necessária para o nosso classificador bayesiano, precisamos definir como computar as probabilidades para cada um dos eventos base.
\( \mathbf{P(y=c_i)} \)
A probabilidade de que caso selecionemos qualquer amostra aleatoriamente do nosso problema ela pertença a classe \(c_i\). Considerando que nossa base de treinamento tenha sido construída de forma aleatória (o que é importante, mas comumente ignorado), podemos dizer que a probabilidade de tal evento pode ser aproximada pelo número de amostras que pertencem a classe \(c_i\), pelo número total de amostras da nossa base de treinamento.
Achei fácil.
\( \mathbf{P(x)} \)
A probabilidade de ocorrencia da nossa amostra \(x\). Agora temos algo um pouco mais complicado. pois \(x\in\mathbb{R}^n\), ou seja, além de um número real, temos n variaveis distintas a considerar.
Para tratar o caso de múltiplas variáveis, vamos introduzir uma suposição, a de que todas as características sao mutuamente exclusivas, dessa forma uma probabilidade \(P(x)\) corresponde ao produto das probabilidades de cada variável \(x_i\). Ou seja:
Contudo, ainda nos resta computar \(P(x_i)\) para cada variável do nosso vetor de características. E aí reside nosso maior problema. Para tal, teríamos que conhecer a distribuição de cada uma das variáveis do nosso vetor de características, as quais não conhecemos.
Como quase sempre em machine learning, a resposta é assumir que os dados seguem alguma distribuição (quase sempre uma distribuição normal), fechar os olhos e seguir a vida. E, desde que essa nossa distribuição não se afaste (muito) da distribição real dos dados, o modelo consegue se virar razoavelmente bem.
Mas tem um limite pro quanto você pode chutar o balde, seu preguiçoso. Então, no mínimo, de uma olhada nos seus dados pra saber se a distribuição que você está assumindo não está muito longe da distribuição real dos seus dados, antes de assumir que o pobre classificador bayesiano não funciona.
Para os nossos dados da base de iris, vamos asumir uma distribuição normal, onde média e desvio padrão sao computadas a partir dos dados.
Como podemos notar, embora a distribuição assumida (linhas) não apresente um casamento perfeito com os dados (barras), temos uma aproximação boa o suficiente para assumir, para nossos propósitos maléficos, que nossa distribuição está correta.
\(\mathbf{P(x|y=c_i)}\)
Valem as mesmas regras para o computo de \(P(x)\), contudo, nesse caso, vamos isolar apenas as amostras em que \(y=c_i\).
Com isso temos os conceitos básicos pra entender a base de um classificador bayesiano, bem como podemos entender as principais restrições na construção de seu modelo, que são a independencia entre as variáveis do nosso vetor de características, e que o modelo da *função densidade probabilidade reflita a distribuição real dos dados.
É bastante importante que você leve em consideração as restrições de um modelo antes de utilizá-lo em qualquer problema de classificação. Dessa forma, você pode ignorar essas restrições de forma consciente (como todo bom cientista de dados), e aplicar o modelo ainda assim, porque vai que funciona.
Implementando a p###a toda
Considerando as definições utilizadas anteriormente, a maioria das implementações de classificadores terão uma mesma interface comum, tanto para o aprendizado quanto para a predição. Algo nas linhas de:
proc train(X: [1..m][1..n] real, Y: [1..m] int) {
...
}
proc predict(x: [1..n] real): int {
...
}
Com isso, podemos implementar os passos para o treinamento do nosso classificador.
Eu sei que chapel nao é la uma linguagem muito conhecida, mas ela é legivel o suficiente, pra qualquer um que venha de Python ou C++.
proc train(X, Y) {
const (n_train, n_feats) = X.shape;
const n_classes = max(Y): int(64);
//global feature model
var mu: [1..n_feats] real;
var sigma: [1..n_feats] real;
//classes feature model
var mu_c: [1..n_classes, 1..n_feats] real;
var sigma_c: [1..n_classes, 1..n_feats] real;
var p_class: [1..n_classes] real;
Essas sao as principais variaveis que vamos usar. Onde n_train, n_feats e n_classes sao exatamente isso que elas descrevem, nem sei porque incluí isso, mu e mu_c representam o valor médio global das features e o valor médio das features para cada classe, da mesma forma, sigma e sigma_c, representam o desvio padrão global e das classe, p_class representa a probabilidade de uma amostra pertencer a uma determinada classe (\(P(y=c_i)\)).
var n_train_c: [1..n_classes] int = 0;
mu = 0.0;
mu_c = 0.0;
sigma = 0.0;
sigma_c = 0.0;
//compute mean
for i in 1..n_train {
var c = Y(i): int;
mu += X(i,..);
mu_c(c, ..) += X(i, ..);
n_train_c(c) += 1;
}
mu /= n_train;
for f in 1..n_feats {
mu_c(.., f) /= n_train_c;
}
//compute standard deviation
for i in 1..n_train {
var c = Y(i): int;
sigma += (X(i, ..) - mu)**2;
sigma_c(c, ..) += (X(i, ..) - mu_c(c, ..))**2;
}
sigma = sqrt(sigma / n_train);
for f in 1..n_feats {
sigma_c(.., f) = sqrt(sigma_c(..,f) / n_train_c);
}
//compute P(class)
for c in 1..n_classes {
p_class(c) = n_train_c(c): real / n_train;
}
Com isso, já temos todas as informações necessárias ao nosso modelo.
Mas, na maioria das implementações você verá que trabalha-se com o log das probabilidades. Pois assim, podemos substituir o produtório citado acima, por uma simples soma, já que:
, e o mesmo vale pra demais operacões de multiplicação ou divisão que são substituídas por uma simples soma/subtração.
Então, uma linha a mais:
p_class = log(p_class);
A predicão, agora, nada mais é do que, utilizarmos essas variaveis de modelo, para computar as probabilidades condicionais necessárias ao classificador bayesiano.
proc predict(x): int {
//P(x)
var p_data = gaussianPdf(x, mu, sigma);
var p_joint_data = sum(log(p_data));
//P(y|x)
var p_class_given_data: [1..n_classes] real;
for c in 1..n_classes {
//P(x|y)
var p_data_given_class = gaussianPdf(x, mu_c(c, ..), sigma_c(c, ..));
var p_joint_data_given_class = sum(log(p_data_given_class));
var p = p_joint_data_given_class + p_class(c) - p_joint_data;
p_class_given_data(c) = p;
}
return argmax(p_class_given_data);
}
Após computado o vetor de probabilidades \(P(y=c_i|x)\), nossa classe predita corresponde a classe de maior probabilidade \(\arg\max(P(y=c_i))\).
E, como adotamos um modelo gaussiano, a implementação da função densidade probabilidade gaussiana:
proc gaussianPdf(x, mu, sigma) {
const expo = -(x-mu)**2 + epsilon / (2 * sigma**2 + epsilon);
return (1.0 / (sqrt(2 * pi) * (sigma + epsilon ))) * exp(expo);
}
Vale lembrar, que nesse caso, adotamos um modelo gaussiano para o nosso classificador, mas você pode adotar outras funções que descrevam melhor seu modelo. Mas aí, já é um problema seu.
Por fim, vamos colocar tudo pra rodar num exemplo.
Nossa base de dados de classificação de flores está num arquivo CSV, contendo os três descritores da amostra, e sua classe, respectivamente.
5.30,3.70,1.50,0.20,1.00
5.00,3.30,1.40,0.20,1.00
7.00,3.20,4.70,1.40,2.00
6.40,3.20,4.50,1.50,2.00
Para testar nosso classificador bayesiano, vamos dividir aleatoriamente esse conjunto de dados em 2, chamados de treino e teste. O conjunto de treino será utilizado no treinamento do nosso classificador, e o conjunto de testes será usado para verificarmos o grau de acerto do nosso classificador, comparando a classe predita, com a classe real da amostra.
use data;
use naive_bayes;
use math;
use utils;
config const csv_dataset: string;
proc main() {
try {
var dataset = data.readCSV(csv_dataset, delimiter=',');
var (Xtrain, Ytrain, Xtest, Ytest) = dataset.split(trainRatio=0.5);
var clf = naive_bayes.train(Xtrain, Ytrain);
var Ypred: [1..Ytest.size] int = -1;
Ypred = clf.predict_batch(Xtest);
writeln("Score: %4.2dr".format(accuracy(Ytest, Ypred) * 100.0));
} catch e {
writeln("deu ruim " + e:string);
}
}
Boa parte desse código é composto apenas de operações chatas como ler arquivos com a base de dados, dividí-lo aleatóriamente em conjunto de treino e testes, e outras coisas mundanas. Fora isso, incluímos dois pontos mais importantes que são, a predição em lote e o cálculo de acurácia (grau de acerto do nosso classificador).
proc predict_batch(X): [] int {
const n_test = X.shape(0);
var Y: [1..n_test] int;
forall i in 1..n_test {
Y(i) = predict(X(i, ..));
}
return Y;
}
A predição em batch, nada mais é do que uma função que calcula a predição do nosso modelo, para um conjunto de amostras, onde podemos aproveitar a natureza independente das amostras para executar cada predição de forma paralela.
proc accuracy(X1, X2) {
var correct = 0.0;
const total = X1.size;
for (x1, x2) in zip(X1, X2) {
if x1 == x2 {
correct += 1;
}
}
return correct/total;
}
E a acurácia, que nada mais é do que a mais simples medida de acerto que podemos usar para avaliar nosso classificador: a proporção entre amostras corretamente classificadas e o número total de amostras do nosso conjunto de testes.
Rodando pra checar os resultados, temos ...
./run_naive_bayes --csv_dataset ./data/digits.csv
Score: 90.32
Como nosso classificador "aprende" com os dados de entrada, podemos notar que, diferentes conjuntos de treinamento podem fazer com que nosso classificador aprenda modelos com diferentes taxas de acerto.
Então, rodando de novo ...
./run_naive_bayes --csv_dataset ./data/digits.csv
Score: 90.77
Por isso, usualmente, para avaliarmos nosso modelo, é comum que calculemos a média de várias rodadas de treino e teste, e assim conseguirmos uma melhor avaliação do nosso modelo.
Mas, basicamente, é isso aí. Com esses conceitos basicos, você consegue implementar seu próprio classificador, e entender um pouco das entranhas de como funciona um modelo de aprendizado de máquina.
Se quiser rodar o código completo, ele está disponível aqui.
Comment