---

Novembro de 2017

Volume 33 - Número 11

Execução de Teste - Regressão Logística do Kernel Usando C#

De James McCaffrey

KLR (Regressão Logística do Kernel) é uma técnica de aprendizado de máquina que pode ser usada para fazer previsões binárias. Por exemplo, a KLR poderia prever se uma pessoa pagará um empréstimo (não pagam = 0, pagam = 1) com base em variáveis da previsão, como idade, renda e quantia devida. A KLR é uma variação avançada da regressão logística comum.

A melhor maneira de saber o rumo que este artigo tomará é examinar o programa de demonstração na Figura 1 e os dados associados na Figura 2. O objetivo do programa de demonstração é prever a classe, 0 ou 1, de dados fictícios que tenham apenas duas variáveis da previsão (às vezes chamadas de recursos), x0 e x1. Por exemplo, o primeiro item de dados de treinamento é (2.0, 3.0, 0), o que significa que, se os valores da previsão forem x0 = 2.0 e x1 = 3.0, a classe correta será 0. A KLR pode lidar com dados com qualquer número de variáveis da previão, mas usa somente duas para permitir que você visualize facilmente a técnica.

Os 21 pontos de dados de treinamento têm uma geometria circular, o que significa que técnicas de classificação linear simples, como a regressão logística comum, são ineficientes. Tais dados são chamados de separáveis não linearmente.

Nos bastidores, a KLR usa uma função chamada de kernel de função de base radial (RBF). A função do kernel de RBF tem um parâmetro chamado sigma. O valor do sigma deve ser determinado por tentativa e erro, e o sigma é definido como 1.9 na demonstração. Treinar um modelo de KLR é um processo iterativo, e a demonstração define o número máximo de iterações como 1,000, além de definir uma taxa de aprendizado, eta, como 0.001.

Treinar um modelo de KLR cria um conjunto de “valores alfa”, um para cada item de dados de treinamento, além de um valor “bias” adicional. O programa de demonstração exibe os valores alfa para os três primeiros itens de treinamento (-0.3071, -0.3043, -0.3071), para os últimos dois itens (0.8999, 0.6108) e para o bias (-1.0722).

Após o treinamento, o modelo KLR prevê corretamente todos os 21 itens de dados. Em seguida, o modelo é aplicado a quatro itens de dados de teste, mostrados como pontos pretos na Figura 2. O primeiro item de teste tem entradas (1.5, 4.5) e uma classe correta de 0. O modelo de previsão prevê corretamente esse item e os outros três itens de teste também.

Este artigo pressupõe que você tenha habilidades de programação intermediárias ou avançadas, mesmo que não tenha familiaridade alguma com a KLR. Codifiquei o programa de demonstração usando a linguagem C#, mas você não deve ter dificuldade alguma para refatorar o código em outra linguagem, como Java ou Python, se desejar. O programa de demonstração é um pouco longo para ser apresentado inteiro, mas o código-fonte está disponível no download do arquivo que acompanha este artigo.

O kernel de RBF

Uma função de kernel mede a semelhança de dois vetores ou matrizes. A função de kernel de RBF que mencionei anteriormente é a mais comum, o tipo usado pelo programa de demonstração. Um valor de RBF de 1.0 significa que dois vetores são idênticos. Valores de RBF menores indicam dois vetores menos semelhantes.

A equação da RBF é:

K(v1, v2) = exp( - || v1 - v2 ||^2 / (2 * sigma^2) )

Aqui, K significa kernel; v1 e v2 são dois vetores com o mesmo comprimento; sigma é um parâmetro com um valor como 1.0 ou 1.5; o || indica a distância euclidiana e a função exp é o número de Euler (e = 2.71828) elevado a uma potência.

A função RBF fica mais clara quando vemos um exemplo. Suponha v1 = (3.0, 1.0, 2.0) e v2 = (1.0, 0.0, 5.0), e o sigma será 1.5. Primeiro, você calcula a distância euclidiana ao quadrado:

|| v1 - v2 ||^2 = (3.0 - 1.0)^2 + (1.0 - 0.0)^2 + (2.0 - 5.0)^2

                      = 4.0 + 1.0 + 9.0

                      = 14.0

Em seguida, divide a distância ao quadrado por duas vezes o sigma ao quadrado:

14.0 / (2 * (1.5)^2) = 14.0 / 4.5 = 3.11

Por último, eleva o número de Euler ao negativo do resultado anterior:

K(v1, v2) = e^(-3.11) = 0.0446

O valor baixo do kernel indica que o v1 e o v2 não são muito semelhantes. O programa de demonstração define a função de kernel de RBF como:

static double Kernel(double[] v1, double[] v2,
  double sigma)
{
  double num = 0.0;
  for (int i = 0; i < v1.Length - 1; ++i)
    num += (v1[i] - v2[i]) * (v1[i] - v2[i]);
  double denom = 2.0 * sigma * sigma;
  double z = num / denom;
  return Math.Exp(-z);
}

A função pressupõe que a última célula de cada matriz contém o rótulo da classe (0 ou 1) e, portanto, a última célula não é incluída no cálculo. A KRL usa a função kernel para comparar um determinado item de dados com todos os itens de treinamento, e usa essas informações para determinar um rótulo de classe previsto.

Regressão logística comum

A regressão logística comum (LR) fica mais clara quando vemos um exemplo. Vamos supor que você tem três variáveis da previsão: x0 = 2.5, x1 = 1.7 e x2 = 3.4. Um modelo LR regular cria um conjunto de constantes numéricas chamadas pesos (wi), um para cada variável da previsão, e uma constante numérica adicional chamada bias (b). Observe que o bias na LR regular não é igual ao bias KLR mostrado na Figura 1. 

Figura 1 Demonstração da regressão logística do kernel

Suponha w0 = 0.11, w1 = 0.33, w2 = 0.22, b = 0.44. Para prever o rótulo da classe, 0 ou 1, para os dados de entrada (2.5, 1.7, 3.4), primeiro você calcula a soma dos produtos de cada x e seu w associado, e adiciona o bias:

z = (2.5)(0.11) + (1.7)(0.33) + (3.4)(0.22) + 0.44

   = 2.024

Em seguida, calcula p = 1.0 / (1.0 + exp(-z)):

p = 1.0 / (1.0 + exp(-2.024))

   = 0.8833

O valor p é a probabilidade de o item de dados ter o rótulo de classe = 1; portanto, se p é inferior a 0.5, sua previsão será 0, e se p for superior a 0.5 (como é neste exemplo), sua previsão será 1.

Ok, mas de onde vêm os valores de pesos e valores de bias na LR regular? A ideia é que você determine os valores dos pesos e do bias usando um conjunto de dados de treinamento que tenha valores de entrada conhecidos, corrija rótulos de classe e, em seguida, use um algoritmo de otimização para localizar valores para os pesos e biases, para que os rótulos de classe previstos correspondam aos valores de rótulo corretos e conhecidos. Existem muitos algoritmos que podem ser usados para localizar valores de peso e de bias para LR regular, incluindo ascendente gradiente com probabilidade de log, descendente gradiente com erro ao quadrado, Newton-Raphson ultrapassado, otimização simples, L-BFGS e otimização de nuvem de partículas.

A principal desvantagem da LR regular é que ela só pode lidar com dados que sejam separáveis linearmente. A LR regular não pode lidar com dados que não sejam separáveis linearmente, como os dados de demonstração mostrados na Figura 2.

Figura 2 Dados de treinamento da Regressão Logística do Kernel

Noções básicas sobre a Regressão Logística do Kernel

A KLR fica mais clara quando vemos um exemplo. À primeira vista, a KLR não se parece muito com a LR comum. No entanto, as duas técnicas são bem parecidas em termos de matemática.

Suponha que existam apenas quatro itens de dados de treinamento:

td[0] = (2.0, 4.0, 0)

td[1] = (4.0, 1.0, 1)

td[2] = (5.0, 3.0, 0)

td[3] = (6.0, 7.0, 1)

Seu objetivo é prever o rótulo da classe para x = (3.0, 5.0). Suponha que o modelo de KLR treinado tenha fornecido valores alfa e um bias de: alpha[0] = -0.3, alpha[1] = 0.4, alpha[2] = -0.2, alpha[3] =0.6, b = 0.1.

A primeira etapa é calcular a semelhança de RBF entre os itens de dados para prever cada um dos itens de treinamento:

K(td[0], x) = 0.3679

K(td[1], x) = 0.0002

K(td[2], x) = 0.0183

K(td[3], x) = 0.0015

Observe que, neste ponto, x é mais semelhante a td[0] e td[2], pois ambos têm o rótulo de classe 0. Em seguida, você calcula a soma dos produtos de cada valor k e o alfa associado, e adiciona o valor de bias:

z = (0.3679)(-0.3) + (0.0002)(0.4) + (0.0183)(-0.2) + (0.0015)(0.6) + 0.1

   = -0.1120

Agora, você calcula p = 1.0 / (1.0 + exp(-z)):

p = 1.0 / (1.0 + exp(0.1120))

   = 0.4720

Se o valor p for superior a 0.5, a classe prevista será 1, e se o valor p for inferior a 0.5, a classe prevista será 0, como (quase) acontece nesse exemplo.

Treinamento de um modelo KLR

Treinar um modelo KLR é o processo de usar os dados de treinamento para encontrar os valores alfa e o valor de bias. Expresso em pseudocódigo de alto nível, o algoritmo do treinamento de KLR é:

compute K(td[i], td[j]) for all i, j
loop maxIter times
  for-each curr training item, i
    for-each j: sum += alphas[j] * K(i j)
    sum += bias
    y = 1.0 / (1.0 + exp(-sum))
    t = target class (0 or 1)
    for-each j:
      alpha[j] += eta * (t - y) * K(i, j)
    bias += eta * (t - y) * 1.0
end-loop

A instrução-chave no código de demonstração é alphas[j] += eta * (t - y) * kernelMatrix[i][j], que atualiza o valor de alfa para o item de dados de treinamento no índice [j] com base no item de dados de treinamento atual no índice [i]. Aqui, t é a classe de destino conhecida e correta, 0 ou 1, e y é uma probabilidade calculada de que o item em [i] tenha a classe 1.

Por exemplo, suponha que um valor de alfa para um item de treinamento seja 0,1234, que a classe de destino seja 1 e a probabilidade calculada seja de 0.60. A previsão atual seria correta, mas você gostaria que o valor de p fosse ainda mais próximo de 1. Suponha que a semelhança entre os dois itens seja K(i, j) = 0.70, e a eta da taxa de aprendizado seja 0.10. O novo valor de alfa seria:

alpha = 0.1234 + 0.10 * (1 - 0.60) * 0.70

          = 0.1234 + 0.0280

          = 0.1514

Como o alfa é um valor multiplicador no cálculo de probabilidade, o valor novo, ligeiramente mais alto, de alfa aumentará um pouco o valor de p, tornando a previsão mais precisa.

O programa de demonstração

Para codificar o programa de demonstração, iniciei o Visual Studio, criei um novo programa de aplicativo do console C# e o nomeei como KernelLogistic. Usei o Visual Studio 2015, mas o programa de demonstração não tem dependências significativas do .NET Framework, portanto, qualquer versão relativamente recente do Visual Studio funcionará bem.

Após o código do modelo ser carregado na janela do editor, cliquei com o botão direito do mouse no arquivo Program.cs na janela do Gerenciador de Soluções e renomeei o arquivo como KernelLogisticProgram.cs. Depois, permiti que o Visual Studio renomeasse automaticamente a classe Program para mim. Na parte superior do código gerado por modelo, excluí tudo o que era desnecessário usando instruções, exceto o que faz referência ao namespace do Sistema de nível superior. Então, instanciei um objeto aleatório:

using System;
namespace KernelLogistic
{
  class KernelLogisticProgram
  {
    static Random rnd = new Random(0);
    static void Main(string[] args)
    {
      Console.WriteLine(“Begin KLR demo”);
      int numFeatures = 2;
...

Para simplificar, codifiquei a demonstração usando uma abordagem de método estática, em vez da programação orientada a objetos, e removi a verificação normal de erros. O método principal configura os 21 itens de treinamento e os 4 itens de teste da seguinte forma:

double[][] trainData = new double[21][];
trainData[0] = new double[] { 2.0, 3.0, 0 };
...
trainData[20] = new double[] { 5.0, 6.0, 1 };
double[][] testData = new double[4][];
testData[0] = new double[] { 1.5, 4.5, 0 };
...
testData[3] = new double[] { 5.5, 5.5, 1 };

Em um cenário não demonstração, você provavelmente leria os dados de um arquivo de texto. Em seguida, os valores alfa são inicializados:

int numTrain = trainData.Length;
int numTest = testData.Length;
double[] alphas = new double[numTrain + 1];
for (int i = 0; i < alphas.Length; ++i)
  alphas[i] = 0.0;

Quando os sistemas de aprendizado de máquina são codificados, geralmente existem várias formas de se lidar com valores de bias. Aqui, armazenei o bias KLR na última célula da matriz de alfas. Um design alternativo é criar uma variável autônoma separada. Em seguida, as semelhanças de kernel entre todos os pares de itens de treinamento são calculadas:

double[][] kernelMatrix = new double[numTrain][];
for (int i = 0; i < kernelMatrix.Length; ++i)
  kernelMatrix[i] = new double[numTrain];
double sigma = 1.0;
for (int i = 0; i < numTrain; ++i) {
  for (int j = 0; j < numTrain; ++j) {
    double k = Kernel(trainData[i], trainData[j], sigma);
    kernelMatrix[i][j] = kernelMatrix[j][i] = k;
  }
}

Como existem somente 21 itens de dados, sacrifico a eficiência em nome da simplicidade. Eu poderia ter reduzido o número de cálculos de kernel usando os fatos: K(v1, v2) = K(v2, v1) e K(v, v) = 1. Em seguida, o programa de demonstração prepara para o treinamento:

double eta = 0.001;
int iter = 0;
int maxIter = 1000;
int[] indices = new int[numTrain];
for (int i = 0; i < indices.Length; ++i)
  indices[i] = i;

Os valores de eta e maxIter foram determinados por tentativa e erro. A ideia por trás da matriz nomeada como índices é que, ao treinar, é importante visitar os itens de treinamento em ordem aleatória a cada passada, evitando entrar em uma situação em que o treinamento pare ou oscile para trás e para frente. O loop principal de treinamento começa:

while (iter < maxIter) {
  Shuffle(indices); 
  for (int idx = 0; idx < indices.Length; ++idx) {
    int i = indices[idx];

O método de Ordem aleatória é um auxiliar que embaralha a ordem dos itens de treinamento usando o minialgoritmo Fisher-Yates. O rótulo da classe de destino e a probabilidade prevista do item de treinamento atual são calculados da seguinte forma:

double sum = 0.0;
for (int j = 0; j < alphas.Length-1; ++j)
  sum += alphas[j] * kernelMatrix[i][j];
sum += alphas[alphas.Length - 1]; 
double y = 1.0 / (1.0 + Math.Exp(-sum));
double t = trainData[i][numFeatures];

Observe que este design pressupõe que o rótulo de classe esteja na última célula de uma matriz de dados de treinamento. Em seguida, os alfas e os valores de beta são atualizados:

for (int j = 0; j < alphas.Length - 1; ++j)
      alphas[j] = alphas[j] +
        (eta * (t - y) * kernelMatrix[i][j]);
    alphas[alphas.Length-1] = alphas[alphas.Length - 1] +
      (eta * (t - y)) * 1; 
  }
  ++iter;
} // While (train)

A atualização do valor de bias usa um valor fictício de 1 no lugar do valor de semelhança de kernel apenas para tornar clara a simetria da relação. É claro que você pode remover a multiplicação por 1 porque ela não tem efeito algum. Após o treinamento, alguns dos valores de alfa e o valor do bias são exibidos, como mostrado na Figura 1.

O programa de demonstração é concluído calculando-se a precisão da classificação do modelo KLR treinado nos dados de treinamento e de teste:

double accTrain = Accuracy(trainData, trainData,
  alphas, sigma, false);
Console.WriteLine(“accuracy = “ +
  accTrain.ToString(“F4”) + “\n”);
double accTest = Accuracy(testData, trainData,
  alphas, sigma, true); // Verbose

O argumento booliano passado ao método Precisão indica se a computação deve ser feita no modo detalhado (com mensagens de diagnóstico) ou no modo silencioso.

Conclusão

A regressão logística do kernel não é usada com muita frequência, pelo menos entre meus colegas. Sua principal vantagem é a simplicidade. A principal desvantagem da KLR é que ela é bem dimensionada em conjuntos de dados grandes porque você tem que pré-calcular todos os valores de semelhança do kernel, item por item, ou tem que manter todos os dados de treinamento e depois calcular rapidamente todos os valores de semelhança para cada previsão.

A KLR foi projetada para classificação binária. É possível estender oaKLR para lidar com problemas de classificação com três ou mais valores de classe, mas, na minha opinião, existem alternativas melhores a serem usadas, especialmente uma rede neural de encaminhamento do feed com uma única camada oculta. A KLR tem algumas semelhanças com o algoritmo de classificação de K-NN (Vizinho Mais Próximo) e de SVM (Máquina de Vetores de Suporte).

---

Dr. James McCaffrey trabalha para a Microsoft Research em Redmond, Washington. Ele trabalhou em vários produtos da Microsoft, incluindo Internet Explorer e Bing. Entre em contato com o Dr. McCaffrey em jamccaff@microsoft.com.

Agradecemos aos seguintes especialistas técnicos da Microsoft pela revisão deste artigo: Chris Lee e Adith Swaminathan

---

Discuta esse artigo no fórum do MSDN Magazine