Classificador linear

Um classificador linear é um tipo de modelo de aprendizado de máquina que separa dados em diferentes classes utilizando uma função linear. A ideia central por trás de um classificador linear é criar uma fronteira de decisão que pode ser representada por uma linha (em duas dimensões), um plano (em três dimensões) ou um hiperplano (em dimensões superiores), etc

Classificadores lineares são de implementação bastante simples, computabilidade rápida e são apropriados para uma grande diversidade de problemas de classificação. São ótimos quando as fronteiras entre as classes de um determinado problema podem ser construídas a partir de funções lineares.

Como funciona

Um classificador linear calcula uma combinação linear dos atributos de entrada e, com base nessa combinação, calcula a saída. Ou seja, matematicamente, um classificador linear é algo como:

\[
[Y]=[X][\theta]
\]

Na realidade, é o mesmo modelo utilizado em uma regressão linear ou no método dos mínimos quadrados. A diferença aqui é como utilizamos esse modelo em relação aos dados de classificação.

A saída do sistema é um vetor $[Y]$, a entrada é uma matriz $[X]$ e os parâmetros do sistema estão contidos no vetor $[\theta]$. $[Y]$ e $[X]$ não são exatamente os dados de classificação fornecidos para treinar o sistema. Entretanto, essas matrizes são construídas a partir destes dados.

A saída do sistema normalmente é um vetor do tipo “um entre zeros” ou one-hot. Nesta abordagem, a dimensão do vetor é igual ao número de classes no sistema. E cada classe é associada a uma dimensão do vetor de saída. Por exemplo, se você tiver três classes A, B e C, a codificação da saída é realizada da seguinte forma:

\[
A \rightarrow \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \hspace{10 mm}
B \rightarrow \begin{bmatrix} 0 & 1 & 0 \end{bmatrix} \hspace{10 mm}
C \rightarrow \begin{bmatrix} 0 & 0 & 1 \end{bmatrix} \hspace{10 mm}
\]

Logicamente, em um caso real, é difícil obter uma combinação linear de características da entrada de tal forma a obter exatamente a codificação acima. Assim, frequentemente após a saída do sistema linear é realizada algum tipo de aproximação ou limiarização através de uma função não linear. Entretanto, a limiarização é aplicada após a parte linear e não é utilizada nos procedimentos de cálculos dos parâmetros do sistema, caso contrário não poderíamos dizer que o sistema é um classificador “linear”.

Um exemplo de função não linear utilizada para a determinação final da classe é o $argmax(.)$ de um vetor. Assim, ainda considerando o exemplo de um sistema de classificação com três classes, poderíamos ter a seguinte saída $[Y]$ desse sistema:

\[
[Y]=\begin{bmatrix} 0.1 & 0.7 & -0.3 \end{bmatrix}
\rightarrow
argmax([Y])=2
\]

No caso acima, o resultado da função $argmax$ é a posição ou índice do maior elemento. Nos exemplo, por convenção, associamos a posição $2$ a classe $B$. Assim, ao aplicar a limiarização por $argmax$ ao vetor $[0.1,0.7,-0.3]$ teríamos como resposta que esse vetor pertence a classe $B$.

Uma outra opção a utilização de $argmax(.)$ é utilizar um algoritmo de distância mínima entre a saída $[Y]$ e os vetores binários para cada classe (No exemplo: $A=[1,0,0]$, $B=[0,1,0]$, $C=[0,0,1]$ ). Em todos os casos, esse processo de aproximação não faz parte do treinamento do sistema. Sendo utilizado apenas para obtenção de um resultado de classificação discretizado. A função não linear utilizada na saída é, na realidade, opcional. Ou seja, poderíamos utilizar diretamente a saída linear do classificador. Neste caso, valores intermediários aos que codificam as classes podem ser interpretados como uma medida de semelhança. Por exemplo, no caso anterior, uma amostra $[x]$ que resulte em uma saída $[Y]=[0.1,0.7,-0.3]$ poderia ser interpretada como sendo majoritariamente semelhante a classe $B$, mas que também possui alguma similaridade com $A$. A saída linear do sistema pode também ser importante para identificar situações limítrofes ou de “dúvida” entre duas ou mais classes. Frequentemente, amostras muito próximas da fronteira de decisão do sistema tem uma alta probabilidade de serem classificadas erroneamente. Assim, caso uma amostra $[x]$ resulte em uma saída $[Y]=[0.5,0.51, -0.1]$, isso é indicativo que a amostra $[x]$ possui praticamente os mesmos graus de semelhança com as classes $A$ e $B$. Nesta situação, talvez seja necessário algum outro tipo de procedimento para mitigação de possíveis erros de classificação. Em resumo, considerando a saída linear é possível fazer inferências sobre o grau de semelhança de um determinado padrão de entrada com cada classe e verificar se não há situações limítrofes no resultado da classificação.

No caso do sistema ser um dicotomizador, ou seja, um classificador que só precisa se decidir entre duas classes, a saída $[Y]$ pode ser também um escalar que varia entre 1 e -1. Onde, saída 1 é associada a uma classe e a saída -1 é associada a segunda classe do dicotomizador. Neste caso, se for preciso realizar algum tipo de limiarização após a saída linear há duas alternativas bem simples. A primeira opção de limiarização é aplicar a função “sinal” ou $sgn$ a saída linear. A função $sgn$ tem saída igual a 1 caso o valor da entrada seja positivo e valor -1 caso o valor da entrada seja negativo. $sgn$ tem valor 0 se a entrada for zero, mas para fins de dicotomização podemos definir $sgn(0)=1$ ou $sgn(0)=-1$ de forma arbitrária. Esse procedimento é apenas para evitar situações indefinidas já que, por definição, um dicotomizador só pode ter dois tipo de saída. Uma segunda opção de limiarização é utilizar a função degrau unitário ou $hardLim$. Essa função tem saída zero quando possui uma entrada com valores negativos e saída 1 quando a entrada é positiva. $hardLim$ tem valor de saída 0.5 quando sua entrada é igual a zero. Entretanto, de forma análoga ao caso da função $sgn$, para a finalidade de dicotomização podemos definir de forma arbitrária $hardLim(0)=1$ ou $hardLim(0)=0$. Abaixo segue alguns exemplos de aplicação destas funções.

\[
[Y]=0.7
\rightarrow
sgn([Y])=1
\]

\[
[Y]=-0.8
\rightarrow
sgn([Y])=-1
\]

\[
[Y]=0.7
\rightarrow
hardLim([Y])=1
\]

\[
[Y]=-0.8
\rightarrow
hardLim([Y])=0
\]

Algumas pessoas poderiam pensar que também seria uma boa ideia representar múltiplas classes com escalares. Por exemplo, poderíamos ter uma saída escalar $Y$ que seria igual a $Y=1$ caso a entrada fosse pertencente a classe A, $y=2$ caso a entrada fosse pertencente a classe B e $Y=3$ caso a entrada fosse pertencente a classe C. Essa estratégia funciona bem para algoritmos como o KNN e o classificador de distância mínima. Nestes algoritmos, a saída não é uma combinação linear das entradas. Entretanto, quando a saída é uma combinação linear da entrada, teríamos um problema de distância entre classes. O classificador poderia gerar uma saída limítrofe entre as classes A e B e entre as classes B e C. Entretanto, uma saída limítrofe entre as classes A e C, na realidade resultaria em uma classificação como pertencente a classe B(a classe que está entre A e C). Isso ocorreria porque as distâncias entre as classes A e B e entre as classes B e C não seriam iguais as distância entre A e C. Ou seja, o classificador ficaria enviesado. Em resumo, não use uma saída escalar de um classificador linear para representar múltiplas classes. Isso não vai funcionar bem. Na realidade, essa abordagem também não funciona muito bem mesmo em alguns classificadores não lineares, como por exemplo, redes neurais.

Construção das matrizes de entrada $[X]$ e saída $[Y]$ a partir dos dados de treinamento

Uma vez que se tenha uma tabela com as instâncias de treinamento e suas respectivas classificações, é necessário realizar a codificação das classes como descrito acima. Em relação a entrada, é necessário avaliar se o sistema precisa ter uma entrada de offset ou bias. Esse entrada é necessária sempre que a distribuição das instâncias não ocorrer ao redor da origem do sistema. Entretanto, na prática, isso pode ser considerado quase como um caso padrão. Assim, considerando um exemplo prático, temos na Tabela 1 um conjunto de 9 instâncias para classificar em duas classes: A e B.

Considerando os dados da Tabela 1 e supondo que o sistema deve precisar de um bias, a matriz de amostras fica da seguinte forma:

\[
[X]_{9 \times 3}=\begin{bmatrix} 1 & 1.5 & 1 \\ 2 & 1 & 1 \\ 0.5 & 2 & 1 \\ 1.75 & 1.75 & 1 \\ 0.5 & 0 & 1 \\ 0 & 2 & 1 \\ 0.5 & 0.8 & 1 \\ 1 & 0 & 1 \\ 1 & 0.5 & 1 \end{bmatrix}
\]

Notem que a presença de um bias nas amostras consiste basicamente de adicionar uma coluna de “1” na matriz. A saída do sistema, a matriz $[Y]$, pode ser construída basicamente realizando a substituição dos rótulos (Ex: A e B) pelas suas respectivas codificações numéricas (Ex: 1 e -1). Abaixo segue a codificação da saída a partir dos dados da Tabela 1.

\[
[Y]_{9 \times 1}=\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ -1 \\ -1 \\ -1 \\ -1 \end{bmatrix}
\]

O calculo dos parâmetros do modelo são realizados utilizando o método dos mínimos quadrados com a pseudo-inversa da matriz $[X]$ ou inversa de Moore–Penrose.

\[
[\theta] = ([X]^T [X])^{-1} [X]^T [Y]
\]

Após o calculo dos parâmetros do modelo, a avaliação da saída $[Y]$ para qualquer vetor de teste $[X]$ pode ser feita do seguinte modo:

\[
[Y]=\begin{bmatrix} x_1 & x_2 & 1 \end{bmatrix} [\theta]
\]

Abaixo segue um exemplo de implementação no Scilab de um classificador linear para os dados da Tabela 1.

function y=sgn(x)
    y=zeros(x)
    y(x>0)=1
    y(x<0)=-1
endfunction

//Entrada colunas 1 e 2, offset e saída(ultima coluna)
X=[
1   1.5 1  1
2   1   1  1
0.5   2   1  1
1.75 1.75 1 1
0.5 0   1 -1
0   2   1 -1
0.5   0.8  1  -1
1   0   1 -1
1   0.5 1 -1
];

//Saída
Y= X(:,$)

Xs=X(:,1:3)
//W=pinv(X(:,1:3))*X(:,4)
W=inv(Xs'*Xs)*Xs'*X(:,4) //Pesos
yy=sgn(Xs*W) //Saída do classificado com limiarização

err=0.5*(Y-yy)'*(Y-yy) //Erro 

x=-0.5:0.1:2.5
y=-W(1)*x/W(2)-W(3)/W(2)

plot(X(1:4,1),X(1:4,2),'r.')
plot(X(5:$,1),X(5:$,2),'g.')
plot(x,y,'k-.') //Plot da fronteira de decisão do sistema

//Perfumaria para o gráfico ficar mais bonito
xtitle("www.drgomes.pro")
xlabel("x1")
ylabel("x2")
xgrid
isoview
ax=gca(),//Captura dos parâmetros do plot atual.
ax.data_bounds=[-0.5 -0.5; 2.5 2.5]; //

Utilizando o código acima e calculando o valor da classe de saída para cada ponto em um intervalo $-0.5 \leq x_1 \leq 2.5$ e $-0.5 \leq x_2 \leq 2.5$ podemos construir o gráfico da Figura 1.

Figura 1: Fronteira de decisão(linha preta tracejada) e regiões de decisão (áreas verdes e vermelhas) para um classificador linear. As instâncias utilizadas para gerar essas fronteiras estão marcadas com “bolinhas”, sendo um total de 2 classes: classe A(bolinhas vermelhas) e classe B( bolinhas verdes).

No gráfico da Figura 1, as “bolinhas” são as instâncias da Tabela 1 utilizadas para encontrar os parâmetros do modelo linear. Uma vez definido os parâmetros do modelo $[\theta]$ , pode-se avaliar o resultado da classificação para qualquer ponto no plano $x_{1},x_{2}$. Para efeitos visuais, pode-se atribuir uma cor para cada classe. No caso da Figura 1, a cor verde foi utilizada para representar os resultados de classificação com saída pertencente a classe $B$ (em relação a Tabela 1) e com cor vermelha com saída pertencente a classe $A$ (também em relação a Tabela 1).

Conclusões

Classificadores lineares são sistemas de classificação simples, de fácil implementação e computabilidade rápida que podem ser utilizados em muitas aplicações do dia a dia. Este post foi uma pequena introdução sobre classificadores lineares, como eles podem ser implementados e utilizados. Evidentemente que esse assunto não se esgota aqui. Há muitas coisas sobre classificadores lineares que não foram comentadas aqui. Pretendo fazer isso em posts futuros, mas no momento é só! Comentários, críticas e sugestões são sempre bem vindas.

That’s all folks!