Aprendizado de Máquina

UFAL, Maceió — Inverno 2019

Inverno 2019

Introdução

Para quê estudar o Aprendizado de Máquina? A resposta esmagadora do guru Andrew Ng:

“I hope we can build an AI-powered society that gives everyone affordable healthcare, provides every child a personalized education, makes inexpensive self-driving cars available to all, and provides meaningful work for every man and woman.”

Traduzido para português:

"Espero que possamos criar uma sociedade baseada na inteligência artificial, que

Amem. Vamos levar o Brasil para frente!

Objetivo do Curso

Este curso inicia o leigo aos métodos básicos do aprendizado de máquina. Tradicionalmente, foram introduzidas regras ao computador para ele calcular as consequências. No aprendizado de máquina, são introduzidos dados ao computador para ele calcular as regras, detectar as regularidades neles (e, em seguida, calcular as consequências destas regras).

Com o advento de cada vez maiores volumes de dados e maior potência computacional, o aprendizado de máquina torna-se cada vez mais proveitoso. Por exemplo,

Resumo

O aprendizado de máquina faz cada vez mais sucesso na resolução de problemas computacionais até há pouco acreditados irresolúveis: Talvez o mais espetacular seja a derrota fulminante do melhor jogador de Go mundial por AlphaGo, uma inteligência artificial baseada no aprendizado de máquina. Até então, os computadores chegavam nem sequer perto aos mestres. Como exemplo protótipo e primeira aplicação, olhamos a classificação de e-mails em Spam (= lixo) e Ham (= não Spam) pelo aprendizado a partir dum conjunto exemplar de e-mails sorteados. Este algoritmo de aprendizado de máquina, baseando-se unicamente na frequência de palavras-chave lixosas no e-mail, revelou-se mais eficiente do que todos os outros até então criados.

Os métodos básicos por trás do aprendizado de máquina são principalmente geométricos: Dado um conjunto de pontos, buscam-se (por exemplo, nos métodos da regressão linear/logística, da Support vetor Machine ou do K-means) as melhores (em um sentido preciso) retas, hiperplanos (em dimensão maior) ou compartimentos para separá-los.

Além da solução deste problema teórico, geométrico, há os problemas práticos:

Para reduzir a dificuldade computacional há, por exemplo, o método da análise de componentes principais (para reduzir o número de parâmetros com perda informacional mínima). Como problema de significância, surge o do Sobre-Ajuste, quer dizer, que o resultado só se aplica aos dados usados, mas em geral não, e o Método de Regularização ajuda mitigá-lo.

Cronograma

Estudamos os fundamentos do curso Machine Learning por Andrew Ng disponível no coursera.org pelo livro Abu-Mostafa, Magdon-Ismail, e Lin (2012) disponível gratuitamente online no endereço Learning from Data.

Começamos com a parte teórica:

  1. Explicamos e formalizamos o que é um problema de aprendizado (supervisionado).

  2. Formalizamos a noção de aprendizagem pelo PAC (= Provavelmente Aproximadamente Correto). O PAC dá em particular uma explicação matemática ao problema recorrente do Sobre-Ajuste, quando as conclusões se aplicam só aos dados analisados, mas não revelam nada geral.

  3. Mostramos pela dimensão de Vapnik-Chervonenkis que uma grande classe de problemas é apreensível.

Concluímos com a parte prática:

  1. Os métodos lineares:

    1. O método do Perceptron em uma variável e em várias variáveis. Geometricamente, busca-se um hiperplano que separa dois conjuntos de pontos.
    2. O método da Regressão Linear, geometricamente, para dados pontos busca-se uma reta que os aproxime o melhor possível.
    3. O método da Regressão Logística que mede a probabilidade de uma propriedade; Por exemplo, se um e-mail é spam ou não.
  2. O Método do Máximo Declive (estocástico) (Gradient Descent) para encontrar extremos de funções (em várias variáveis); por exemplo, minimizar as distâncias nos métodos lineares acima.

  3. O método da Máquina de Vetores de Suporte (Support vetor Machine), como extensão não-linear (kernelization) do Perceptron: Geometricamente, busca-se um hiperplano que separa pontos em duas classes. Em comparação à Regressão Logística computacionalmente preferível quando há poucos parâmetros, quer dizer, a dimensão é pequena.

  4. Redes Neurais como iteração da Regressão Logística em várias variáveis;

  5. O método das K-médias (K-means) cuja saída é finita. Geometricamente, busca-se uma divisão de pontos em compartimentos tal que ela minimize as distâncias entre os pontos em cada compartimento.

  6. O método da Análise da Componente Principal (análise de componentes principais) para projetar um conjunto de pontos a um espaço de dimensão menor sem perda de informação quanto à sua classificação.

Otimizar

Para otimizar, isto é, encontrar um ponto em que uma função (de erro) EE tem o seu valor mínimo, usaremos

Os métodos numéricos (iterativos) para calcular esta projeção ou o ponto em que a derivada é zero serão só superficialmente explicadas.

Aspectos Matemáticos

Recapitulamos noções básicas

Lembremo-nos de que, mesmo se o link URL expirou, o conteúdo é ainda disponível pelo archive.org sob o endereço https://web.archive.org/web/URL/ . Por exemplo, a animação da regressão linear http://mste.illinois.edu/activity/regression/ da Universidade do Illinois permanecerá disponível sob https://web.archive.org/web/http://mste.illinois.edu/activity/regression/ . Neste caso, a página foi arquivada no dia 5 de maio 2018; o seu estado nesta data continua a estar disponível em https://web.archive.org/web/20180505102200/http://mste.illinois.edu/activity/regression/ .

Notações

Esta secção explica a linguagem matemática básica, conjuntos e funções. Como as notações usada na matemática acadêmica diferem em uns pontos das do ensino escolar, repitamos as mais comuns:

Conjuntos

A noção fundamental da matemática é a de um conjunto; segundo os dicionários Aurélio, Houaiss ou Michaelis:

Esta coleção de seres matemáticos é denotada por { seres matemáticos }\{ \text{ seres matemáticos } \}. Se um ser matemático aa pertence ao conjunto AA, dizemos que aa é em XX e escrevemos aAa \in A ou AaA \ni a.

Por exemplo, o conjunto

Podemos comparar dois conjuntos AA e BB:

Podemos formar um novo conjunto a partir de dois conjuntos AA e BB:

Por exemplo, os números irracionais são todos os números reais que não são racionais, isto é, que pertencem ao \mathbb{R} - \mathbb{Q}.

Denote A×BA \times B o seu produto cujos elementos são (a,b)(a,b) para aa em AA e bb em BB, isto é, A×B={(a,b) para a em A e b em B}. A \times B = \{ (a, b) \text{ para } a \text{ em } A \text{ e } b \text{ em } B \}. Se B=AB = A, escrevemos A2A^2 em vez de A×AA \times A, e A3A^3 em vez de A×A×AA \times A \times A, e assim por diante. Por exemplo, 2\mathbb{R}^2 é o plano (euclidiano), e 3\mathbb{R}^3 é o espaço.

Funções

Fórmula

Uma função descreve a dependência entre duas quantidades. No ensino escolar, é usualmente denotada por uma equação f(x)= expressão em x f(x) = \text{ expressão em $x$} onde na expressão figuram

Por exemplo:

  1. A distância ss percorrida por um objeto na queda livre depende do tempo da queda tt: vale s=gt2s = g \cdot t^2 onde g=9,8m/s2g = 9,8 \mathrm{m}/\mathrm{s}^2 é a constante da aceleração gravitacional da terra.
  2. A forca de atração KK entre duas massas mm' e mm'' depende de mm', mm'' e a distância rr entre elas: Pela lei gravitacional de Newton K=G(mm)/r2K = G (m' m'')/r^2 onde G=6,671011Nm2kg2G = 6,67 \cdot 10^{-11} \mathrm{N} \mathrm{m}^2 \mathrm{kg}^{-2} é a constante de gravidade universal de Newton.

Porém, existem outras dependências, por exemplo:

  1. O preço de uma entrada ao teatro de fantoches depende do número da fila do assento: Esta dependência descreve-se por uma tabela de preços, dando o número da fila 11, 22, 33, … e o preço correspondente de 100100 Centavos, 2020 Centavos, 55 Centavos, …

Definição. Uma função ff é uma regra que associa a cada elemento xx de um conjunto XX exatamente um elemento yy de um conjunto YY.

Esta associação é simbolicamente expressa por y=f(x)y = f(x). Refiramo-nos

A imf\mathrm{im} f de ff é o conjunto de todos os valores de ff, imf={ todos os f(x) para x em X}. \mathrm{im} f = \{ \text{ todos os } f(x) \text{ para } x \text{ em } X \}. Por exemplo, imsen=[1,1]\mathrm{im} \mathrm{sen} = [-1,1] e imf={c}\mathrm{im} f = \{c\} para a função constante fcf \equiv c. O contra-domínio contém a imagem, mas não necessariamente coincide com ela, imfY. \mathrm{im} f \subseteq Y.

Usualmente, vemos funções com XX e YY \subseteq \mathbb{R}, isto é, funções reais; chamamo-nas muitas vezes simplesmente de funções. Usualmente as letras a,b,c,,r,s,t,u,x,y,za,b,c,\ldots, r, s, t, u ,x,y,z denotem números reais; as letras i,j,k,l,n,mi,j,k, l, n,m denotem números naturais (usados para enumerações). Nos nossos exemplos:

  1. Aqui (a magnitude) de tt em 0\mathbb{R}_{\geq 0} e f(t)=s0f(t) = s \in \mathbb{R}_{\geq 0}. Tem-se X=0X = \mathbb{R}_{\geq 0} e imf=0\mathrm{im} f = \mathbb{R}_{\geq 0}.
  2. Aqui (a magnitude) de m,mm',m'' em 0\mathbb{R}_{\geq 0} e KK em 0\mathbb{R}_{\geq 0}. Tem-se X=(0×0)×0X = (\mathbb{R}_{\geq 0} \times \mathbb{R}_{\geq 0}) \times \mathbb{R}_{\geq 0} e imf=0\mathrm{im} f = \mathbb{R}_{\geq 0}.
  3. Aqui X=={1,2,3}X = \mathbb{N} = \{ 1, 2, 3 \} e imf={100,20,5}\mathrm{im} f = \{ 100, 20, 5 \}.

Funções reais aparecem em diversas formas: além de

obtemos pela substituição da variável por um número real como 0,50,5, 11, 22, 10001000, …

Em mais detalhes:

Coordenadas Cartesianas de um ponto nos eixos xx e yy

De vez em quando, para destacar que um objeto, por exemplo, uma função h:XYh \colon X \to Y, depende de outro objeto, por exemplo, de um conjunto DD ou uma ênupla ww, escrevemos h(D)h(D) ou hDh_D respetivamente h(w)h(w) ou hwh_w em vez de hh.

Aplicação

No ensino acadêmico, uma função ou aplicação é denotada por f:XY f \colon X \to Y para os dois conjuntos,

dizemos que manda ou envia cada argumento xx em XX a um único valor yy em YY.

Lê-se que ff é uma função de XX a YY, ou tem argumentos em XX e valores em YY. No contexto informático, pensamos de ff como um algoritmo, e referimo-nos a XX e YY como entrada e saída.

Uma função manda ou envia cada argumento xx em XX a um único valor yy em YY (ou associa a cada xx um único yy). Escrevemos xy x \mapsto y e denotemos este valor yy por f(x)f(x). Frequentemente, X=X = \mathbb{R} ou X=××X = \mathbb{R} \times \cdots \times \mathbb{R} e Y=Y = \mathbb{R} ou Y={±1}Y = \{ \pm 1 \}. Por exemplo, a função f:f \colon \mathbb{R} \to \mathbb{R} dada por xx2x \mapsto x^2 manda 22 em \mathbb{R} a 22=42^2 = 4 em \mathbb{R}.

Função e aplicação são sinónimos. Contudo, a conotação é outra: Se os objetas do domínio são, por exeplo, números inteiros, conjuntos, então aplicação é mais comum, enquanto função é principalmente usada quando o domínio consiste de (ênuplas de) números reais.

Formar Novas Funções

Composição

A partir de duas funções ff e gg (sobre quaisquer domínios e imagens) pode ser obtida outra por concatenação; a função composta ou a composição gfg \circ f, dado que a imagem de ff é contida no domínio de gg, isto é, Y(f)X(g)Y(f) \subseteq X(g). É definida por gf:xg(x)f(g(x)),g \circ f \colon x \mapsto g(x) \mapsto f(g(x)), simbolicamente, para obter gf(x)=g(f(x))g \circ f(x) = g(f(x)), substituímos xx em g(x)g(x) por f(x)f(x).

Se temos duas funções, f:XY, e g:YZ f \colon X \to Y, \quad \text{ e } \quad g \colon Y \to Z isto é, tais que os valores de ff são argumentos de gg, a sua composição é definida por xf(x)g(f(x)), x \mapsto f(x) \mapsto g(f(x)), isto é, a saída de ff é a entrada de gg, e denotada por gf:XZ. g \circ f \colon X \to Z.

Inversão de funções

Por definição, uma função f:XYf \colon X \to Y associa a cada argumento xXx \in X exatamente um valor yYy \in Y. Frequentemente surge o problema inverso: Dado um valor yy, determina o seu argumento xx sob ff, isto é, tal que y=f(x)y = f(x). Se uma função ff é injetora, isto é, xxx' \neq x'' implica f(x)f(x)f(x') \neq f(x''), isto é, a argumentos diferentes são associados valores diferentes, então a cada valor yimfy \in \mathrm{im} f é associado um único argumento xXx \in X. A função g:imfXg \colon \mathrm{im} f \to X obtida pela associação inequívoca inversa yxy \mapsto x, ou g(y)=xg(y) = x é a ou o de ff e denotada por g=f1g = f^{-1}. Ora, yy é a variável e xx a variável . Em fórmulas, a função inversa gg é obtida pela permutação das duas variáveis xx e yy na equação y=f(x)y = f(x).

Matematicamente, a função ff tem o inverso g=f1g = f^{-1}, se g(f(x))=xg(f(x)) = x e f(g(x))=xf(g(x)) = x. Por exemplo, sobre 0\mathbb{R}_{\geq 0} vale (x2)=x=(x)2\sqrt (x^2) = x = (\sqrt{x})^2 para f(x)=x2,g(x)=xf(x) = x^2, g(x) = \sqrt x, e (2x+1)/21/2=x=2(x/21/2)+1(2x + 1)/2-1/2 = x=2(x/2-1/2) + 1 para f(x)=2x+1f(x) = 2x + 1 e g(x)=x/21/2g(x) = x/2 - 1/2.

Para desenhar a função inversa, poderíamos permutar as designações dos dois eixos. Porém, isto comumente não se faz. Porém, se o domínio e a imagem coincidem, o gráfico da função inversa g=f1g = f^{-1} é o espelhamento do gráfico da função invertida ff na diagonal dos pontos cuja coordenada xx é igual à coordenada yy.

A função inversa

Exemplos. Olhemos uns exemplos de funções invertíveis. Observamos em particular que a invertibilidade depende do domínio: Quanto menor o domínio, tanto mais provável que a função seja invertível.

Resumimos:

Algarismos

Um número real no dia-a-dia é escrito em notação decimal aNa1a0,a1 a_N \ldots a_1 a_0, a_{-1} \ldots com aNa_N, , a1a_1, a0a_0, a1a_{-1} , em {0,1,,9}\{ 0, 1, \ldots, 9 \}. Isto é, é como soma em potências de 1010 e com algarismos 00, …, 99. Por exemplo, 321,34=3102+210+1+3101+4102. 321,34 = 3 \cdot 10^2 + 2 \cdot 10 + 1 + 3 \cdot 10^{-1} + 4 \cdot 10^{-2}. Em vez da base decimal b=10b = 10, existem outras. As mais comuns na informática são

Isto é,

Por exemplo, 1101=123+122+021+120 1101 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 e A02F=10163+0162+2161+15160. A02F = 10 \cdot 16^3 + 0 \cdot 16^2 + 2 \cdot 16^1 + 15 \cdot 16^0.

1 O que é um problema de aprendizado?

Tradicionalmente, foram introduzidas regras ao computador para ele calcular as consequências.

regras \to computador \to resultados

No aprendizado de máquina, são introduzidos dados ao computador para ele calcular as regras, detectar as regularidades neles (e, em seguida, calcular as consequências destas regras).

dados \to computador \to regras (\to computador \to resultados)

Com o advento de cada vez maiores volumes de dados e maior potência computacional, o aprendizado de máquina torna-se cada vez mais proveitoso.

1.1 Categorias de Aprendizado

Primeiro destacamos a diferença entre aprendizado e especificação para resolver um problema de classificação. Com efeito, o aprendizado leva a especificação:

Na especificação, são introduzidas regras ao computador para ele calcular as consequências. No aprendizado de máquina, são introduzidos dados ao computador para ele especificar as regras (e, em seguida, calcular as consequências das regras).

Recordemo-nos

dados \to computador \to regras \to computador \to resultados

Enquanto

Exemplo: para distinguir entre valores de moedas pelos seus pesos e tamanhos, usamos

Concluímos:

Figura 1.1: Agrupamento de moedas por peso e tamanho

Se os círculos foram desenhados antes dos pontos, trata-se de especificação. Se os círculos foram desenhados depois dos pontos, trata-se de aprendizado.

O termo que usamos daqui para diante

Pensamos

Aprendizado com Supervisionamento

No aprendizado com supervisionamento, os exemplos são classificados. Isto é, temos pares (entrada,saída) (\text{entrada}, \text{saída}) Por exemplo, duas pastas de e-mails, a primeira do tipo spam, a outra do tipo ham.

Aprendizado por Reforço

No aprendizado por reforço, os exemplos da amostra são parcialmente avaliados. Isto é, temos pares (entrada,saída e a sua avaliação) (\text{entrada}, \text{saída e a sua avaliação}) Destacamos que, dada uma entrada xx, não necessariamente todos os pares (x,y)(x,y) para todas as possíveis saídas yy são contidos na amostra.

Exploração

Quer dizer, não sabemos necessariamente quão boas outras saídas poderiam ter sido. Por exemplo, ao aprender um jogo de tabuleiro, dado uma configuração xx do tabuleiro, yy será o lance e a sua avaliação a probabilidade de ganhar o jogo.

A avaliação

No aprendizado por reforço, a avaliação é uma função na entrada e saída. Por exemplo,

Aprendizado sem Supervisionamento

No aprendizado sem supervisionamento, os exemplos são inclassificados.

Isto é, o algoritmo

  1. Precisa de criar as possíveis saídas, ou os rótulos, e
  2. depois classifica.

O exemplo principal é o clustering, ou agrupamento. Por exemplo, mesmo sem rótulos, as moedas podem ser agrupadas pelos seus pesos e tamanhos, vide Figura 1.1

1.2 Exemplos de Aprendizado Supervisionado

Por exemplo,

1.3 Formalização

Formalmente, em um problema de aprendizado, temos

e

Enfatizamos que

As hipóteses e o algoritmo são chamados o Método de Aprendizado.

Observação. Mais adiante, a função alvo, em vez de ser uma função determinista y:XYy \colon X \to Y, será uma variável aleatória, isto é, intuitivamente, para cada argumento xx, em vez de devolver

devolve

(Em linguagem matemática, cada possível valor y=y0y = y_0 constitui um evento cuja probabilidade P(y=y0)P(y = y_0) é medida pela distribuição, ou medida de probabilidade, PP.)

Porém, os valores y1y_1, …, yNy_N para os dados x1x_1, …., xNx_N continuam ser deterministas. O algoritmo tem de deduzir as probabilidades dos valores pelas suas frequências na amostra. Uma tal função divina aleatória é chamada de uma função com ruído.

1.4 Formalização dos Exemplos

Nos exemplo

Observamos que os últimos três exemplos, a classificação de e-mails, de credores e de jogadores, são exemplos de uma classificação binária, isto é, a saída é binária.

Enquanto as ênuplas na classificação de e-mails têm muitos entradas (já que existem muitas palavras), a dimensão dos outros dois exemplos é menor e poderemos dar uma interpretação geométrica. Em mais detalhes, olhamos, por exemplo

1.5 Pontuação

Nestes dois exemplos, da discriminação entre credores e jogadores aptos,

Neste caso, podemos dar uma pontuação ao possível devedor ou ao jogador relativo aos seus atributos financeiros ou físicos. Mais explicitamente, avaliar as suas importâncias (ou pesos) e somar os atributos (features) pesados. Se esta soma é suficientemente alto, quer dizer, em cima de um certo limiar, aceitamos o devedor ou jogador.

Por exemplo,

Por exemplo, poderíamos dar,

Obtemos,

Se Neymar e Roberto Carlo estão na seleção nacional, mas Frederico não, então, por exemplo, um limiar de 320320 modela isto.

Geometricamente, - os dois atributos de um jogador correspondem a um ponto no plano cartesiano, e - os pesos e o limiar a uma reta que separa entre os jogadores na seleção nacional e o resto.

Aplicaremos em Seção 4.1 o método geométrico do algoritmo Perceptron, ou, um nome mais expressivo, Discriminador Linear que busca (ou aprendre) esta reta.

Observamos que estes pesos separam perfeitamente para a nossa amostra, mas provavelmente, estes mesmos pesos falham com outra. Por exemplo, os pesos obtidos pela seleção pelo Filipão (em 2006) são bem diferentes dos pelo Tite (em 2018). Isto toca a questão do aprendizado discutida em Seção 2: Quando podemos dizer que a amostra é típica e nos levou a uma boa escolha dos pesos?

2 O que é aprendizado?

Recordemo-nos de que formalmente, em um problema de aprendizado (com supervisionamento), temos os dados, isto é,

e o método, isto é,

2.1 Erro

A escolha da proximidade, ou melhor, da distância mais apropriada do erro, isto é, entre os valores da hipótese hh e da função divina yy, depende, entre outros, da saída YY.

O que significa a mais próxima de yy?

Esta escolha faz parte da definição do algoritmo AA: Por exemplo,

O programador determina

em seguida

Porém, isto não quer dizer que hh minimize o erro fora da amostra, isto é, se aproxime da função divina em todo lugar. Esta proximidade depende da escolha justa de HH e ED\mathrm{E}_D.

Formalismo

Será a função de custo que capta todas as possíveis medidas de erro neste manuscrito. Quando a saída é binária, e as importâncias dos dois erros

são iguais, basta contar os pontos em que ff erra (isto é, difere de yy) ED(f):=P({xD tal que f(x)y(x)}) \mathrm{E}_D(f) := \mathrm{P}(\{ x \in D \text{ tal que } f(x) \neq y(x) \}) isto é, ED(f)=#{ os pontos x em D em que f(x)y(x)}/N, \mathrm{E}_D(f) = \# \{ \text{ os pontos } x \text{ em } D \text{ em que } f(x) \neq y(x) \} / N,

Porém, em geral precisamos de uma abordagem mais geral à avaliação da proximidade de ff à função divina yy:

A este fim, introduzimos a função de custo e:Y×Y[0,[e \colon Y \times Y \to [0,\infty[ tal que ED(f)=e(f(x1),y(x1))++e(f(xN),y(xN)). \mathrm{E}_D (f) % = % \int e(f, y) = e(f(x_1), y(x_1)) + \cdots + e(f(x_N), y(x_N)). A função de custo faz parte do algoritmo; isto é, a sua apropriada escolha é sob a responsabilidade do programador do algoritmo.

Por exemplo,

2.2 Provavelmente Aproximadamente Correto

O que significa aprendizado?

Isto é, qual é o nosso alvo no aprendizado de máquina?

Segundo o princípio PAC (Provavelmente Aproximadamente Correto) é, encontrar um algoritmo que consegue a partir de quase qualquer amostra (isto é, Provavelmente) encontrar uma função que quase sempre acerta (isto é, que é Aproximadamente Correta):

Uma hipótese mostra bom aprendizado se tira as conclusões certas a partir de uma amostra; isto é, mais importante do que acertar na amostra DD é acertar na entrada inteira XX:

Seja, por exemplo, a saída Y={±1}Y = \{ \pm 1 \} binária, isto é, um problema de classificação binária. Dada a amostra D={x1,...,xN}D = \{ x_1, ..., x_N \} e uma função ff, podemos calcular o erro específico por ED(f):=P({xD tal que f(x)y(x)})=#{ os pontos x em D em que f(x)y(x)}/N,\begin{align} \mathrm{E}_D(f) & := \mathrm{P}(\{ x \in D \text{ tal que } f(x) \neq y(x) \})\\ & = \# \{ \text{ os pontos } x \text{ em } D \text{ em que } f(x) \neq y(x) \} / N, \end{align} isto é, a probabilidade que ff erre sobre DD. (Em Abu-Mostafa, Magdon-Ismail, e Lin (2012), denotado por Ein\mathrm{E}_{\mathrm{in}} para significar dentro da amostra.) Por exemplo, o algoritmo Perceptron, se termina, consegue ED(f(D))=0\mathrm{E}_D(f(D)) = 0.

Mas, como yy é desconhecida, não sabemos o erro geral, EX(f):=P({xX tal que f(x)y(x)}), \mathrm{E}_X(f) := \mathrm{P}(\{ x \in X \text{ tal que } f(x) \neq y(x) \}), isto é, a probabilidade que ff erre sobre XX. (Em Abu-Mostafa, Magdon-Ismail, e Lin (2012), denotado por Eout\mathrm{E}_{\mathrm{out}} para significar fora da amostra.)

Veremos quando podemos minimizar esta probabilidade de erro. Porém, depende sempre da amostra, que pode ser atípica e levar mesmo um bom algoritmo à escolha de uma hipótese que tira conclusões erradas. Isto é, o algoritmo pode só acertar com certa probabilidade na escolha de uma hipótese próxima (a função divina); isto é, é provavelmente aproximadamente correto.

Formalismo

Dada a amostra D={x1,...,xN}D = \{ x_1, ..., x_N \} e uma função ff, podemos calcular o erro específico, ED(f) \mathrm{E}_D(f) isto é, a probabilidade que ff erre sobre DD. (Em Abu-Mostafa, Magdon-Ismail, e Lin (2012), denotado por Ein\mathrm{E}_{\mathrm{in}} para significar dentro da amostra.) Por exemplo, o algoritmo Perceptron, se termina, consegue ED(f(D))=0\mathrm{E}_D(f(D)) = 0.

Mas, como yy é desconhecida, não sabemos o erro geral (ou erro de generalização), EX(f) \mathrm{E}_X(f) isto é, a probabilidade que ff erre sobre XX. (Em Abu-Mostafa, Magdon-Ismail, e Lin (2012), denotado por Eout\mathrm{E}_{\mathrm{out}} para significar fora da amostra.)

Se, por exemplo,

qualquer função que coincide em DD com yy é uma possível solução; sobram 33 valores a definir. Qual destas #Y3=23\# Y^3 = 2^3 extensões dos 55 aos 88 pontos é a mais próxima da função alvo? Não há resposta definitiva, mas provavelmente aproximadamente correta:

O problema é apreensível por PAC ( = Provavelmente Aproximadamente Correto) se existe um algoritmo AA que calcula para qualquer amostra D={x1,...,xN}D= \{x_1, ..., x_N\} uma hipótese h=h(D)h = h(D) em HH que seja provavelmente aproximadamente correta, isto é:

Para todo (erro) ϵ>0\epsilon > 0 e (toda difidência) δ>0\delta > 0 e para toda distribuição (= medida de probabilidade) PP, existe um NN tal que para toda amostra DD com pelo menos NN exemplos independente e identicamente distribuídos P(EX(h(D))<ϵ)>1δ. \mathrm{P}( \mathrm{E}_X(h(D)) < \epsilon) > 1 -\delta. Para o algoritmo AA ser eficientemente computável, é mais exatamente requerido que NP(1/ϵ,1/δ)N \geq P(1/\epsilon, 1/\delta) para um polinómio PP, chamado de complexidade de amostra do algoritmo AA.

Recordemo-nos de que

Isto é, provavelmente a amostra leva a uma hipótese aproximadamente correta. Quer dizer, se a amostra é suficientemente típica (o que vale com uma probabilidade >1δ> 1 - \delta, isto é, provavelmente), então a probabilidade do erro é pequena, <ϵ< \epsilon, isto é, a função é aproximadamente correto.

Em Seção 3, dados ϵ\epsilon e δ>0\delta > 0, calcularemos para uns problemas de aprendizado o tamanho NN da amostra DD que garante que P(EX(h(D))<ϵ)>1δ. \mathrm{P}( \mathrm{E}_X(h(D)) < \epsilon) > 1 -\delta.

2.3 Treinar e Testar

Como saber se um método aprende bem, isto é, se a hipótese hh escolhida pelo algoritmo AA a partir de DD tem um erro geral EXh\mathrm{E}_X h pequeno?

Holdout

Na prática, uma abordagem é o holdout, isto é, não usar toda a amostra DD para a computação da melhor escolha hh por AA, mas divide aleatoriamente DD em dois subconjuntos DD' e DD'', por exemplo, 2/32/3 dos exemplos em DD' e 1/31/3 dos exemplos em DD'' para

No treinamento, minimizamos ED(h)\mathrm{E}_{D'} (h) (sobre todas as hipóteses hh). No teste, verificamos que ED(h)\mathrm{E}_{D''} (h) é pequeno.

Se a saída é finita, Y={1,2,...,n}Y = \{ 1, 2, ..., n \}, então o erro de teste ED(h)\mathrm{E}_{D''}(h) é visualizado por uma matriz de confusão, por exemplo, para n=3n = 3 com 1010 exemplos de cada tipo 11, 22 e 33,

h(x)h(x) \ y(x)y(x) 11 22 33
11 77 22 11
22 11 88 11
33 11 00 99

onde

Random Subsampling

Se o alvo do programador, em vez de encontrar pelo algoritmo a melhor hipótese a partir de uns exemplos (e em seguida medir o erro da hipótese para outros exemplos), é medir a média dos erros das hipóteses encontradas pelo algoritmo (isto é, em vez de medir a acuraria da hipótese, medir a acuraria do algoritmo), então se aplica, em vez do holdout, o random subsampling que varia o conjunto de teste: Divide DD em, no mínimo, três subconjuntos DD', DD'' e DD''' e

O nosso método

Neste manuscrito, porém, só treinamos, e não testamos: Confiaremos em que o método, isto é, as escolhas

são suficientemente apropriadas para o problema de aprendizado aprenda bem, isto é, que a minimização do erro da amostra EDh\mathrm{E}_D h (entre todas as hh em HH) garante um erro geral EXh\mathrm{E}_X h suficientemente pequeno (sem avaliar ETh\mathrm{E}_T h para um conjunto de teste TT diferente de DD).

3 Quão bem aprendemos?

O que é aprendizado? Afinal, queremos encontrar a partir de uma amostra, uns exemplos (por exemplo, clientes antigos de um banco) uma função simples, a hipótese, que prediz os valores em que nos interessamos (por exemplo, a quantia de um crédito) para outras entradas (isto é, futuros clientes).

Para o algoritmo acertar, quer dizer, fazer provavelmente um erro pequeno, precisamos muitos exemplos, clientes antigos. Nesta Seção descobrimos

Para isto, usamos uma estimativa geral, a desigualdade de Hoeffding (estatístico finlandês) que inicialmente só se aplicou para um número finito de hipóteses. Infelizmente, na prática o número de hipóteses é infinito. Por exemplo, no Perceptron no plano, as hipóteses são todas as retas.

Por isso, restringimos as hipóteses da entrada inteira infinita XX à amostra finita DD. Por exemplo, no Perceptron, restringimos aos valores das retas sobre NN pontos no plano. Vimos que já para N=4N = 4, tem valores de pontos que nenhuma reta consegue reproduzir, quer dizer, não existe reta que os separe, por exemplo:

        +

    -      -

        +

Quando um tal número como N=4N = 4 existe em que as hipóteses são insuficientes para reproduzir uma classificação da amostra, diremos que a dimensão (de Vapnik-Chervonenkis) dd das hipóteses é finita. Neste caso, podemos, para qualquer erro ϵ\epsilon e para qualquer confiança δ\delta, por exemplo, ϵ=0,1\epsilon = 0,1 e δ=0,1\delta = 0,1, garantir que a hipótese escolhida pelo algoritmo a partir de uma amostra com NN exemplos faça um erro <ϵ=0,1< \epsilon = 0,1 com uma probabilidade de 1δ=90%1 - \delta = 90 \%.

O resultado teórico é muito folgado, pois muito geral: Na teoria, N=10.000dN = 10.000 d, na prática N=10dN = 10 d. Por exemplo, para o Perceptron no plano, d=3d = 3.

3.1 Defeito

Dada a amostra D={x1,...,xN}D = \{ x_1, ..., x_N \} com os seus valores {y1,...,yN}\{ y_1, ..., y_N \} e uma hipótese hh, podemos calcular o seu erro específico, ED(h); \mathrm{E}_D(h); contudo, como yy é desconhecida, não o seu erro geral, EX(h), \mathrm{E}_X(h), cuja minimização é o alvo final. Para aproximá-lo, introduzamos o defeito ΔDh:=EX(h)ED(h) \Delta_D h := \mathrm{E}_X(h) - \mathrm{E}_D(h) que quantifica quão bem o algoritmo aprende, tira conclusões gerais certas a partir da amostra DD: Para limitar EX(h)\mathrm{E}_X(h), precisamos, pela desigualdade triangular |EX(h)||ΔDh|+|ED(h)|, | \mathrm{E}_X(h) | \leq | \Delta_D h | + | \mathrm{E}_D(h) |, de limitar |ΔDh| e |ED(h)|. | \Delta_D h | \quad \text{ e } \quad | \mathrm{E}_D(h) |. Isto é, a viabilidade de aprender corresponde à viabilidade de minimizar

Para simplificar a exposição, seja daqui em diante Y={±1}Y = \{\pm 1\}, problema de classificação binária, e o erro ED(h)=P(hy)=#{x em D tais que h(x)y(x)}/#D \mathrm{E}_D(h) = P(h \neq y) = \# \{ x \text{ em } D \text{ tais que } h(x) \neq y(x) \} / \# D dado pela probabilidade de errar.

3.2 Desigualdade de Hoeffding

Teorema. Dada uma função h:XYh \colon X \to Y, um limiar de erro ϵ>0\epsilon > 0 e um número de exemplos NN, a desigualdade de Hoeffding estima a probabilidade do defeito ser >ϵ> \epsilon por P(|ΔDh|>ϵ)2e2ϵ2N. P( | \Delta_D h | > \epsilon ) \leq 2 \mathrm{e}^{-2 \epsilon^2 N}.

Isto é, dada uma hipótese h:XYh \colon X \to Y, sabemos limitar a probabilidade do evento {D em X××X tal que |ΔDh|<ϵ}. \{ D \text{ em } X \times \cdots \times X \text{ tal que } |\Delta_D h| < \epsilon \}. de uma amostra D=(x1,...,xN)D = (x_1, ..., x_N) atípica, isto é, em que o erro de hh difira do erro geral de hh por mais de ϵ\epsilon, por um grande número de exemplos NN.

Num problema de aprendizado, dada uma função h:XYh \colon X \to Y, um limiar de erro ϵ>0\epsilon > 0 e um número de exemplos NN, queremos limitar o risco P(EXh(D)>ϵ) P(\mathrm{E}_X h(D) > \epsilon) que uma amostra DD leva o algoritmo a uma hipótese h(D)h(D) errada, isto é, com EXh(D)>ϵ\mathrm{E}_X h(D) > \epsilon. Como P(EXh(D)>ϵ)=P(EDh(D)+ΔDh(D)>ϵ); P(\mathrm{E}_X h(D) > \epsilon) = P(\mathrm{E}_D h(D) + \Delta_D h(D) > \epsilon); e como EDh(D)\mathrm{E}_D h(D) é conhecido, queremos limitar P(|ΔDh(D)|>ϵ)P( |\Delta_D h(D)| > \epsilon ), isto é, a probabilidade do evento {D em X××X tal que |ΔDh(D)|>ϵ}() \{ D \text{ em } X \times \cdots \times X \text{ tal que } |\Delta_D h(D)| > \epsilon \} \quad (\dagger) de uma amostra D=(x1,...,xN)D = (x_1, ..., x_N) atípica, isto é, em que o erro de h(D)h(D) difira do erro geral de h(D)h(D) por mais de ϵ\epsilon.

Para estimar P(|ΔDh(D)|>ϵ)P( |\Delta_D h(D)| > \epsilon ) pela aplicação da desigualdade de Hoeffding, observamos que

Em geral, sem conhecimento do algoritmo que escolhe h(D)h(D) a partir de DD, só podemos limitar a probabilidade de |ΔDh(D)|>ϵ|\Delta_D h(D)| > \epsilon para h(D)h(D) pela probabilidade que |ΔDh|>ϵ|\Delta_D h| > \epsilon para uma hh em HH. Isto é, que exista hh em HH com |ΔDh|>ϵ|\Delta_D h| > \epsilon; em fórmulas {D em X××X tal que |ΔDh(D)|>ϵ}h em H{D em X××X tal que |ΔDh(D)|>ϵ}.\begin{align} & \{ D \text{ em } X \times \cdots \times X \text{ tal que } |\Delta_D h(D)| > \epsilon \}\\ \subseteq & \bigcup_{h \text{ em } H} \{ D \text{ em } X \times \cdots \times X \text{ tal que } |\Delta_D h(D)| > \epsilon \}. \end{align} Se H={h1,...,hM}H = \{ h_1, ..., h_M \} é finito, então P(|ΔD(h(D))|>ϵ)P(|ΔD(h1)|>ϵ)++P(|ΔD(hM)|>ϵ)M2e2ϵ2N, P( | \Delta_D(h(D)) | > \epsilon ) \leq P( | \Delta_D(h_1) | > \epsilon ) + \cdots + P( | \Delta_D(h_M) | > \epsilon ) \leq M \cdot 2 \mathrm{e}^{-2 \epsilon^2 N}, onde, na última desigualdade, como h1h_1, …, hMh_M não variam com DD, aplicamos a cada um dos MM parcelas a mesma desigualdade de Hoeffding, obtendo na soma o fator MM.

Observação. Quanto maior #H=M\# H = M, tanto mais facilmente o algoritmo consegue diminuir P(|ED(h(D))|>ϵ), P( | \mathrm{E}_D(h(D)) | > \epsilon ), mas, também, tanto maior o limite da desigualdade P(|ΔD(h(D))|>ϵ)M2e2ϵ2N. P( | \Delta_D (h(D)) | > \epsilon ) \leq M \cdot 2 \mathrm{e}^{-2 \epsilon^2 N}. Não há saída deste dilema entre o erro geral e o erro específico, só podemos procurar um equilíbrio entre os dois.

3.3 A dimensão de Vapnik-Chervonenkis

Recordemo-nos de que para uma hipótese h:XYh \colon X \to Y e uma amostra DD, é a diferença, o defeito ΔDh=ED(h)EX(h), \Delta_D h = \mathrm{E}_D(h) - \mathrm{E}_X(h), a diferença entre

quantifica quão bem o algoritmo aprende, acerta as conclusões gerais a partir de exemplos. Logo, num problema de aprendizado, dada ϵ>0\epsilon > 0, queremos limitar a probabilidade P(|ΔDh(D)|>ϵ) P( |\Delta_D h(D)| > \epsilon ) para a hipótese h(D)h(D) em HH que é escolhida a partir de DD pelo algoritmo AA; em particular, que vária com DD. Como AA é desconhecido, logo h(D)h(D), precisamos de limitar o supremo de todas as hipóteses P(|ΔDh(D)|>ϵ)P(sup{|ΔD(h)|:h em H}>ϵ). P( |\Delta_D h(D)| > \epsilon ) \leq P( \sup \{ |\Delta_D(h)| : h \text{ em } H \} > \epsilon ). Observamos {D:sup{|ΔDh|:h em H}>ϵ}=h em H{D:|ΔDh|>ϵ}. \{ D : \sup \{|\Delta_D h| : h \text{ em } H \} > \epsilon\} = \bigcup_{h \text{ em } H} \{ D : |\Delta_D h| > \epsilon \}. Por isso, se H={h1,...,hM}H = \{ h_1, ..., h_M \} é finito, esta probabilidade pode ser estimada, da maneira mais grossa, por P(|ΔDh(D)|>ϵ)P(h em H{D:|ΔDh|>ϵ})M2e2ϵ2#D. P( |\Delta_D h(D)| > \epsilon ) \leq P(\bigcup_{h \text{ em } H} \{ D : |\Delta_D h| > \epsilon \}) \leq M \cdot 2 \mathrm{e}^{-2 \epsilon^2 \# D}. Porém, para HH infinito, precisamos de uma maneira mais fina para estimar P(|ΔDh(D)|>ϵ)P( |\Delta_D h(D)| > \epsilon ) que toma em conta as grandes interseções dos conjuntos {D:|ΔDh|>ϵ}\{ D : |\Delta_D h| > \epsilon \} para as hh em HH que diferem pouco.

Vamos agora conhecer a “dimensão” do conjunto de hipóteses HH, que permite limitar o defeito para HH infinito.

O número efetivo de hipóteses sobre uma amostra

Para limitar a probabilidade de um alto defeito,

Definição: O conjunto das restrições a DD das hipóteses hh em HH, as dicotomias geradas por HH, é denotado por H(D):={h|D:hH} H(D) := \{ h_{|D} : h \in H \} A função de crescimento mHm_H para HH (sobre \mathbb{N}) é definida por mH(N):=max{#H(D):D uma amostra em X com #D=N}. m_H(N) := \max \{ \# H(D) : D \text{ uma amostra em } X \text{ com } \# D = N \}.

Se #D=N\# D = N, então #H(D)#Y#Y=2N \# H(D) \leq \# Y \cdots \# Y = 2^N onde os fatores #Y\# Y, …, #Y\# Y correspondem aos dois possíveis valores {±1}\{ \pm 1 \} de x1x_1, …, xNx_N; logo, mH(N)2N. m_H(N) \leq 2^N. Observamos nos exemplos seguintes de mHm_H para HH diferentes que

Exemplos:

Se mH(N)=2Nm_H(N) = 2^N, isto é, se existe uma amostra DD tal que #H(D)=2N\# H(D) = 2^N, dizemos que HH estilhaça DD. Caso contrário, se mH(k)<2km_H(k) < 2^k, isto é, se nenhuma amostra de cardinalidade kk pode ser estilhaçada por HH, o número natural kk é um ponto de interrupção para HH.

Exemplos: Nos exemplos acima, o menor ponto de interrupção é k0=4,2,3k_0 = 4, 2, 3 e \infty. Para obter k0k_0, usa-se uma rotulagem (= dicotomia) sobre os pontos que é inestilhaçável, isto é, não pode provir de uma hipótese.

Definição: A dimensão de Vapnik-Chervonenkis é dVC(H):=max{N tal que mH(N)=2N} \mathrm{d}_{\mathrm{VC}}(H) := \max \{ N \text{ tal que } m_H(N) = 2^N \} e dVC(H):=\mathrm{d}_{\mathrm{VC}}(H) := \infty caso mH(N)=2Nm_H(N) = 2^N para todos os NN. Isto é, dVC(H)=k01\mathrm{d}_{\mathrm{VC}}(H) = k_0 - 1 para k0k_0 o menor ponto de interrupção para HH.

Para calcular dVC(H)\mathrm{d}_{\mathrm{VC}}(H), limitamos dVC(H)\mathrm{d}_{\mathrm{VC}}(H) abaixo e acima: Por definição, dVC(H)N uma amostra D com #D=N é estilhaçada por H, \mathrm{d}_{\mathrm{VC}}(H) \geq N \iff \text{ uma amostra } D \text{ com } \# D = N \text{ é estilhaçada por } H, ou, equivalentemente, em contra-posição, dVC(H)<N nenhuma amostra D com #D=N é estilhaçada por H. \mathrm{d}_{\mathrm{VC}}(H) < N \iff \text{ nenhuma amostra } D \text{ com } \# D = N \text{ é estilhaçada por } H.

Exemplo: Para o Perceptron sobre X={1}×dX = \{ 1 \} \times \mathbb{R}^d, temos dVC(H)=d+1\mathrm{d}_{\mathrm{VC}}(H) = d + 1. Por exemplo, para d=2d = 2, temos dVC(H)=3\mathrm{d}_{\mathrm{VC}}(H) = 3. Em geral, como heurística, dVC(H)\mathrm{d}_{\mathrm{VC}}(H) é proporcional ao número dos parâmetros que definem as funções em HH.

Cota do número efetivo de hipóteses sobre uma amostra

Dada uma amostra DD com NN elementos, ϵ>0\epsilon > 0, recordemo-nos da desigualdade de Hoeffding, para um conjunto de hipóteses finito de cardinalidade #H=M\# H = M, P(|ΔD(h(D))|ϵ)12M2N2ϵ2. P(|\Delta_D(h(D))| \leq \epsilon) \geq 1 - 2 M \cdot 2^{-N 2 \epsilon^2}. Logo, com δ=2M2N2ϵ2\delta = 2 M \cdot 2^{-N 2 \epsilon^2}, resolvendo para ϵ\epsilon, obtemos P(|ΔD(h(D))|[(1/2N)log(2M/δ)]1/2)1δ. P(|\Delta_D(h(D))| \leq [(1/2N) \cdot \log (2M/\delta)]^{1/2} ) \geq 1 - \delta. Para HH infinito, queremos substituir MM pelo número mH(N)m_H(N) (que depende de NN) e limitá-lo. Revela-se

Teorema(Lema de Sauer): Se há kk em \mathbb{N} tal que mH(k)<2km_H(k) < 2^k, então mH(N)1+N+N(N1)/2++N(N1)(Nk+2)/(k1)! m_H(N) \leq 1 + N + N(N-1)/2 + \cdots + N(N-1) \cdots (N-k + 2)/(k-1)! para todos os NN.

Em particular, para d=dVC(H)d = \mathrm{d}_{\mathrm{VC}}(H) a dimensão de Vapnik-Chervonenkis, mH(N)1+N+N(N1)/2++N(N1)(Nd+1)/d! m_H(N) \leq 1 + N + N(N-1)/2 + \cdots + N(N-1) \cdots (N-d + 1)/d! para todos os NN. Isto é, mH(N)m_H(N) é limitado por um polinômio de grau dd.

Corolário. Se d=dVC(H)<d = \mathrm{d}_{\mathrm{VC}}(H) < \infty, então mH(N)Nd+1 m_H(N) \leq N^{d} + 1

Demonstração: Por indução em dd.

Cota de erro

Teorema(Cota de Generalização de VC = o mais importante resultado matemático na teoria de aprendizado): Para δ>0\delta > 0, P(|ΔD(h)|[(8/N)log(4mH(2N)/δ)]1/2)1δ. P(|\Delta_D(h)| \leq [(8/N) \log(4 m_H(2N)/\delta)]^{1/2}) \geq 1 - \delta.

Corolário: Se d=dVC(H)<d = \mathrm{d}_{\mathrm{VC}}(H) < \infty, então para qualquer ϵ\epsilon e δ>0\delta > 0 existe NN tal que, para toda amostra DD com #DN\# D \geq N, P(|ΔD(h)|ϵ)>1δ. P(|\Delta_D(h)| \leq \epsilon) > 1 - \delta. Mais exatamente, para todo NN com N8/ϵ2log([4(2N)d+1]/δ). N \geq 8/\epsilon^2 \log([4 (2N)^d + 1] /\delta).

Demonstração: Se dVC(H)<\mathrm{d}_{\mathrm{VC}}(H) < \infty, então pelo Lema de Sauer, mH(N)Nd+1 m_H(N) \leq N^d + 1 Como log(x)/x0\log(x)/x \to 0, logo log(p(x))/x0\log(p(x))/x \to 0 para qualquer polinômio p(x)p(x), obtemos [(8/N)log(4mH(2N)/δ)]1/20 para N. [(8/N) \log(4 m_H(2N)/\delta)]^{1/2} \to 0 \quad \text{ para } N \to \infty. Mais exatamente, podemos resolver [(8/N)log(4mH(2N)/δ)]1/2ϵ [(8/N) \log(4 m_H(2N)/\delta)]^{1/2} \leq \epsilon para NN, obtendo a desigualdade para NN acima.

Vemos que [(8/N)log(4mH(2N)/δ)]1/20 para N. [(8/N) \log(4 m_H(2N)/\delta)]^{1/2} \to 0 \quad \text{ para } N \to \infty. exatamente porque mH(2N)m_H(2N) é polinomial, e não exponencial, 2N2^N. Neste caso, valeria log(2N)=cN\log(2^N) = c \cdot N; em particular, não converge a 00.

Observação. Porém, a desigualdade N8/ϵ2log([4(2N)d+1]/δ) N \geq 8/\epsilon^2 \log([4 (2N)^d + 1] /\delta) é implícita, isto é, NN aparece ao lado direto. Por isso, NN precisa de ser aproximado iterativamente: Se N0<f(N0)N_0 < f(N_0), onde f(N0)f(N_0) denote o lado direito, então o crescimento monótono da função ff permite aproximar o mínimo NN tal que Nf(N)N \geq f(N) pelos valores f(N0)f(N_0), f(f(N0))f(f(N_0)), …

Por exemplo, para d=3d = 3, uma confidência δ=0,1\delta = 0,1 e erro ϵ=0,1\epsilon = 0,1, uma escolha N=10000N = 10 000 leva a um valor no lado direto de N=21193N = 21 193. Esta iteração converge rápido a um valor de N30000N \approx 30 000. Semelhantemente, para d=4d = 4 e d=5d = 5, obtém-se N40000N \approx 40 000 e N=50000N = 50 000.

Isto é, o número de exemplos requerido é proporcional à dimensão de Vapnik-Chervonenkis com um fator de 1000010 000. Na prática, um fator de 1010 revelou-se suficiente (vide Deep Learning para um método de aprendizado que funciona bem na prática mas desafia o quadro teórico de Vapnik-Chervonenkis).

Contudo, apesar da cota demasiada ampla, as estimativas obtidas por Vapnik-Chervonenkis são

4 Hipóteses Lineares

Muitos problemas de aprendizado podem ser resolvidos por hipóteses que são funções lineares. Para três saídas diferentes,

vamos explicar três algoritmos que escolhem entre tais hipóteses:

Por exemplo, um banco pergunta-se sobre um cliente:

Recordemo-nos de que em um problema de aprendizado, temos um algoritmo AA que escolhe em função da amostra DD a melhor hipótese hh em HH. A melhor hipótese quer dizer a hipótese que é mais próxima da função divina yy. A proximidade de hh mede-se pela função de erro geral EX(h)\mathrm{E}_X (h), o erro sobre XX. Como yy é só conhecida sobre DD (mas não sobre XX), podemos só aproximá-lo pelo erro específico ED(h)\mathrm{E}_D (h) sobre a amostra DD.

Em todos os algoritmos lineares que serão apresentados,

Em todos os algoritmos lineares que serão apresentados, contentamo-nos com um algoritmo AA que para cada DD escolhe o ww que minimize esta soma finita ED(w)\mathrm{E}_D (w) nos valores wTx1w^\mathrm{T} x_1, …, wTxNw^\mathrm{T} x_N.

Frequentemente, acrescentamos uma coordenada constante a XX, isto é, X={1}×××X = \{ 1 \} \times \mathbb{R} \times \cdots \times \mathbb{R} como artifício para aumentar a dimensão de HH e preservar a dimensão de XX. Isto permite dispensar de um parâmetro constante nos algoritmos, isto é, em vez de (x1,...,xd)w0+w1x1++wdxd, (x_1, ..., x_d) \mapsto w_0 + w_1 x_1 + \cdots + w_d x_d, basta-nos considerar (x1,...,xd)w1x1++wdxd, (x_1, ..., x_d) \mapsto w_1 x_1 + \cdots + w_d x_d, pelo acréscimo de uma entrada x0=1x_0 = 1.

4.1 Perceptron (ou Discriminador Linear)

Formalizemos a questão de como decidir se um cliente consegue quitar um crédito a partir dos seus atributos (features) por comparação com as quitações históricas.

A ideia é pontuar o cliente, e conceder o crédito caso a pontuação foi suficientemente alta. Isto é, dar pontos aos clientes de um banco em relação aos seus atributos financeiros, por exemplo, o seu salário e os seus bens. Se a pontuação é suficientemente alta, o crédito lhe é concedia.

A questão surge como ponderar os atributos dos clientes, quais pesos dar aos seus atributos, e onde localizar o limiar a partir de que será aceito?

O algoritmo que busca estes pesos chama-se Perceptron: Mais abstratamente, se o problema de aprendizado é uma classificação binária, isto é

podemos aplicar o método de aprendizado do Perceptron, em que

com sinal(x)=1\mathrm{sinal}(x) = 1 se x>0x > 0 e 1-1 se x<0x < 0. Isto é, uma função hh em HH é dada pelos

e, para xx em XX, vale h(x)=±1 se e tão-somente se w1x1++wdxdb. h(x) = \pm 1 \quad \text{ se e tão-somente se } \quad w_1 x_1 + \cdots + w_d x_d \lessgtr b. Geometricamente, os pontos x=(x1,...,xd)x = (x_1, ..., x_d) que satisfazem a igualdade w1x1++wdxd=bw_1 x_1 + \cdots + w_d x_d = b formam um hiperplano que divide o espaço XX nos dois semiespaços dos pontos xx cuja soma é b\lessgtr b). Por exemplo, se XX é o plano, a igualdade define uma reta e cada lado dela um semiplano. Se as coordenadas sejam denotadas por xx e yy, os pesos por ww respetivamente v0v \neq 0, então a equação da reta como função no argumento xx com valor yy é dada por wx+vy=b se, e tão-somente se, y=Wx+B com W=wv e B=bv. w x + v y = b \text{ se, e tão-somente se, } y = W x + B \text{ com } W = \frac{-w}{v} \text{ e } B = \frac{b}{v}. Por exemplo, os parâmetros w=2w = 2, v=1v = 1 e b=1b = 1 correspondem à reta abaixo:

A reta y=12xy = 1 - 2x divisa o plano nos dois semiplanos y+2x1y + 2x \lessgtr 1

No caso

O algoritmo Perceptron aproxima os pesos e o limiar por iteração sobre todos os pontos no conjunto de dados exemplares DD a uma solução h0h_0, quer dizer, tal que h0(x)=y(x) para todo x em D. h_0(x) = y(x) \quad \text{ para todo } x \text{ em } D.

Hipóteses

Facilitemos a formulação do problema do aprendizado: Para abreviar a notação da soma dos atributos pesados w1x1++wdxdw_1 x_1 + \cdots + w_d x_d, usamos o produto escalar entre o vetor w=(w1,...,wd)w = (w_1, ..., w_d) e x=(v1,...,vd)x = (v_1, ..., v_d) dado por wTx:=w1x1++wdxd w^\mathrm{T} x := w_1 x_1 + \cdots + w_d x_d (A notação T\cdot^T significa vetor transposto. Isto é, o vetor wTw^T é visto como vetor de coluna e xx como vetor de linha. O produto escalar é o produto da matriz de uma coluna wTw^T com a matriz de uma linha xx.) Pondo x0=1x_0 = 1 e w0=bw_0 = -b, vale w1x1++wdxdb=w0x0+w1x1++wdxd w_1 x_1 + \cdots + w_d x_d - b = w_0 x_0 + w_1 x_1 + \cdots + w_d x_d isto é, para x=(1,x1,...,xd)x = (1, x_1, ..., x_d) e w=(b,w1,...,wd)w = (-b, w_1, ..., w_d), w1x1++wdxdb=wTx. w_1 x_1 + \cdots + w_d x_d - b = w^\mathrm{T} x. Concluímos que

e

com sinal(x)=1\mathrm{sinal}(x) = 1 se x>0x> 0 e 1-1 se x<0x < 0. (Geometricamente, para d=2d = 2,

Erro

O erro especifico ED(h)\mathrm{E}_D(h) que o algoritmo visa minimizar é o número dos pontos em que hh erra, ED(h)=#{x em D com h(x)y(x)}=x em D(h(x)y(x))2. \mathrm{E}_D (h) = \# \{ x \text{ em } D \text{ com } h(x) \neq y(x) \} = \sum_{x \text{ em } D} (h(x) - y(x))^2.

Na imagem correspondem:

Separação de pontos pelas suas cores e por uma reta

(Equivalentemente, o algoritmo visa minimizar PD(h):=ED(h)/NP_D(h) := \mathrm{E}_D (h) / N, a probabilidade que hh erre sobre DD.) Com efeito, o algoritmo Perceptron

Por isso, apresentaremos em seguida o algoritmo Pocket que remedia esta oscilação por iteração sobre o Perceptron. Assim, converge mesmo quando ED(h)=0\mathrm{E}_D(h) = 0 é impossível.

Algoritmo

O algoritmo Perceptron determina o limiar e os pesos w=(b,w1,...,wd)w = (b, w_1, ..., w_d) iterativamente a partir da amostra DD como segue:

Seja t=0,1,2,...t= 0, 1, 2, ... a iteração e w(t)w(t) o valor de ww na iteração tt. Seja x(t)x(t) em DD um ponto erroneamente classificado e y(t):=y(x(t))y(t) := y(x(t)) o seu valor correto. Formalmente, erroneamente classificado quer dizer sinal(w(t)Tx(t))y(t). \mathrm{sinal} (w(t)^\mathrm{T} x(t)) \neq y(t). ou, equivalentemente, y(t)(w(t)Tx(t))<0. y(t) (w(t)^\mathrm{T} x(t)) < 0.

ponto erroneamente classificado

O Perceptron põe w(t+1):=w(t)+y(t)x(t) w(t + 1) := w(t) + y(t)x(t) Geometricamente, para obter a nova reta (= o novo limiar e os novos pesos) w(t+1)w(t + 1), o Perceptron desloca a reta na direção correta (isto é, a dada por y(t)y(t)) do ponto erroneamente classificado. Formalmente, há duas possibilidades:

Como w(t+1)Tx(t)=w(t)Tx(t)+y(t)x(t)Tx(t) w(t + 1)^T x(t) = w(t)^\mathrm{T} x(t) + y(t) x(t)^\mathrm{T} x(t) e vTv>0v^\mathrm{T} v > 0 para qualquer vetor vv, vale

Isto é, o valor da (nova) função hipotecada h(t+1):=w(t+1)Th(t + 1) := w(t + 1)^\mathrm{T} \cdot é pelo menos no ponto por enquanto erroneamente classificado x(t)x(t) mais próximo do valor correto (do que o da antiga função hipotecada h(t)h(t)). (Isto não quer dizer que a cada iteração o erro em outros pontos pode aumentar! Diante disto é estupefaciente que a função finalmente obtida é totalmente correta — dado que uma tal função existe.)

O Perceptron itera a correção do limiar e dos pesos w(t)w(t+1)w(t) \to w(t + 1) até que não haja mais pontos erroneamente classificados. Geometricamente, desloca a reta até que separe as duas classes de pontos.

Código

Se denotamos a amostra por x1,...,xNx_1, ..., x_N e os seus valores sob a função divina yy por y1,...,yNy_1, ..., y_N, então, em pseudo-código, o algoritmo Perceptron é dado por

Põe w(0):=(0,...,0)w(0) := (0, ..., 0) e t:=0t := 0
Repete
\quad Para i=1,...,Ni = 1, ..., N
\quad \quad Se yiw(t)Txi<0y_i w(t)^T x_i < 0, então põe w(t+1):=w(t)+yixiw(t + 1) := w(t) + y_i x_i
\quad \quad Aumenta tt por 11
até yiw(t)Txi>0y_i w(t)^T x_i > 0 para todo i=1,....,Ni = 1, ...., N
Devolve w(t)w(t)

Em Python, para calcular os pesos e limiar ww (inspirado pela postagem Perceptron in a few lines of Python code),

import numpy as np

X = np.array([
    [-2, 4],
    [4, 1],
    [1, 6],
    [2, 4],
    [6, 2]
])

Y = np.array([-1,-1,1,1,1])

def perceptron(X, Y):
    w = np.zeros(len(X[0]))
    epochs = 100

    for t in range(epochs):
        errors = 0
        for i in enumerate(X):
            if (np.dot(X[i], w)*Y[i]) <= 0:
                w = w + X[i]*Y[i]
                errors += 1
        if errors == 0:
            break
    return w

Para desenhar os pontos classificados pela reta separadora,

from matplotlib import pyplot as plt

for d, sample in enumerate(X):
    # Plot the negative samples
    if d < 2:
        plt.scatter(sample[0], sample[1], s = 120, marker = '_', linewidths = 2)
    # Plot the positive samples
    else:
        plt.scatter(sample[0], sample[1], s = 120, marker = ' + ', linewidths = 2)

# Print the line computed by perceptron ()
x2 = [w[0],w[1],-w[1],w[0]]
x3 = [w[0],w[1],w[1],-w[0]]

x2x3 =np.array([x2,x3])
X,Y,U,V = zip(*x2x3)
ax = plt.gca()
ax.quiver(X,Y,U,V,scale = 1, color = 'blue')

Exemplo em dois passos

Seja d=2d = 2, e

Observamos que x=(x0,x1,x2)=(1,x,y)x= (x_0, x_1, x_2) = (1, x, y) satisfaz w0x0+w1x1+w2x2=0 w_0 x_0 + w_1 x_1 + w_2 x_2 = 0 se e tão-somente se y=ax+b com a=w1/w2 e b=w0/w2. y = a x + b \quad \text{ com } a = - w_1/w_2 \text{ e } b = - w_0/w_2. Isto é, descrevemos a projeção dos vetores ortonormais ao vetor ww aos seus últimos dois coordenados pela função (traslada) linear y=ax+by = a x + b.

  1. Como w(0)Tq=2>0w(0)^\mathrm{T} q = 2> 0 mas y(q)<0y(q) < 0, constatamos que qq é erroneamente classificado e determinamos w(1)=w(0)+y(q)q=(0,0,2)(1,1,1)=(1,1,1). w(1) = w(0) + y(q) q = (0, 0, 2) - (1, 1, 1) = (-1, -1, 1). Isto é, a=1a = 1 e b=1b = 1.
  2. Como w(1)q=1>0w(1) q = -1> 0 e y(q)<0y(q) < 0, constatamos que qq é bem classificado (e pp também) e o algoritmo termina.
O exemplo dado pelos pontos pp e qq

Tempo de Execução

A margem de um hiperplano separando dois conjuntos de pontos

Em fórmulas, o raio e a margem são definidos como segue:

Animação

Para ganharmos um intuito como o Perceptron se aproxima da reta separadora, há uma animação online (em JavaScript) da Universidade do Texas em Austin.

O Algoritmo Pocket (= bolso)

Recordemo-nos de que se o problema de aprendizado é um problema de classificação binária, isto é, X={1}×××X = \{ 1 \} \times \mathbb{R} \times \cdots \times \mathbb{R} (com 1+d1 + d fatores) e Y={±1}Y = \{ \pm 1 \}, então no algoritmo Perceptron as hipóteses HH têm a forma h:xsign(wTx) h \colon x \mapsto \mathrm{sign} (w^\mathrm{T} x) para vetores ww em d+1\mathbb{R}^{d + 1}.

Recordemo-nos de que na formalização PAC (= Provavelmente Aproximadamente Correto) do aprendizado, buscamos hh tal

O Algoritmo Perceptron

Se a amostra DD é linearmente separável, isto é, há hh em HH tal que ED(h)=0, \mathrm{E}_D(h) = 0, então o algoritmo Perceptron encontrará tal hh. Recordemo-nos de que, para cada passo t0t \geq 0, o Perceptron seleciona um ponto erroneamente classificado x(t)x(t) com valor y(t)=y(x(t))y(t) = y(x(t)) e atualiza w(t)w(t) por w(t+1):=w(t)+y(t)x(t). w(t + 1) := w(t) + y(t)x(t). Mas, se DD não é linearmente separável, isto é, não há uma solução em HH, este algoritmo não converge a uma solução aproximativa (quer dizer, que minimiza ED(h)\mathrm{E}_D(h), as classificações errôneas).

O Algoritmo Pocket

Se DD não é linearmente separável, isto é, é impossível achar hh tal que ED(h)=0\mathrm{E}_D(h) = 0, queremos pelo menos minimizá-lo, isto é, encontrar o (melhor) vetor de pesos ww (em d+1\mathbb{R}^{d + 1}) que minimiza ED(h)=#{xn em D tal que sign(wTxn)yn}/#D \mathrm{E}_D(h) = \# \{ x_n \text{ em } D \text{ tal que } \mathrm{sign}(w^\mathrm{T} x_n) \neq y_n \} / \# D O algoritmo Pocket (= bolso) aplica o Perceptron repetidamente (por exemplo, em TT repetições) e guarda no seu bolso o melhor vetor de pesos ww até então encontrado. Isto é,

Põe w := w(0)
Para t = 0, ..., T:
    Roda um passo do Perceptron para obter w(t + 1)
    Calcula E(w(t + 1))
    Se E(w(t + 1)) < E(w), então põe w = w(t + 1)
Devolve w

Isto é, em comparação ao Perceptron, o Pocket avalia após a atualização w(t)w(t+1)w(t) \mapsto w(t + 1) se o novo vetor é melhor (quanto o erro sobre a amostra) do que o melhor até então encontrado ww, e, caso sim, substitui ww por w(t+1)w(t + 1). Pela computação de ED(w(t+1))\mathrm{E}_D(w(t + 1)), que percorre todos os pontos da amostra, o algoritmo Pocket é mais lento do que o Perceptron.

Sabemos

A evolução do erro do Perceptron contro o do Pocket

Recapitulação

Questões para quem quiser testar a assimilação do conteúdo desta seção sobre o Perceptron:

  1. Qual é a medida de erro que o algoritmo Perceptron minimiza?
  2. Entre quais funções o Perceptron escolhe a melhor, isto é, que minimiza o erro?
  3. Quais parâmetros o Perceptron otimiza, isto é, quais números altera até ter minimizado o erro?
  4. O Perceptron consegue separar (por uma reta) qualquer rotulagem (= escolha de cruzes e bolas) de quatro pontos no plano?
  5. O número de erros sempre diminui após uma iteração adicional?

4.2 A Regressão Linear

O banco não somente quer decidir se o cliente recebe um crédito ou não, mas mais exatamente estimar o seu valor.

Tem-se

e

Hipóteses

Geometricamente, para X=X = \mathbb{R}, a regressão linear busca a reta hh que minimize a distância (quadrática) aos pontos da amostra DD.

As distâncias entre a reta hh e os valores y1y_1, …, yNy_N dos pontos da amostra

Cada hipótese h:XYh \colon X \to Y corresponde a um vetor w=(w1,...,wd)w = (w_1, ..., w_d) em ××\mathbb{R} \times \cdots \times \mathbb{R}; ela é dada por h:xxwT:=x1w1++xdwd. h \colon x \mapsto x w^\mathrm{T} := x_1 w_1 + \cdots + x_d w_d.

Erro

O erro que queremos minimizar é a distância quadrática entre hh e yy, isto é, o valor médio da diferença hyh - y ao quadrado sobre a amostra finita D={x1,...,xN}D = \{ x_1, ..., x_N \}, onde a integral do valor médio se torna a soma finita ED(h)=D(h(x)y(x))2dx=[(h(x1)y1)2++(h(xN)yN)2]/N \mathrm{E}_D(h) = \int_D (h(x) - y(x))^2 \; \mathrm{d}x = [(h(x_1)-y_1)^2 + \cdots + (h(x_N) - y_N)^2]/N

Cada hipótese hh corresponde ao vetor dos seus pesos ww. Por isso, denotamos o erro especifico daqui em diante por ED(w)\mathrm{E}_D(w) (em vez de ED(h)\mathrm{E}_D(h)), evidenciando como função em ××\mathbb{R} \times \cdots \times \mathbb{R}.

Se denotamos

então ED(w)=[(x1wTy1)2++(xNwTyN)2]/N=XwTy2/N(4.1) \mathrm{E}_D(w) = [(x_1 w^\mathrm{T} - y_1)^2 + \cdots + (x_N w^{\mathrm{T}} - y_N)^2]/N = \| Xw^{\mathrm{T}} - y \|^2/N \qquad(4.1)

onde

e onde

Algoritmo

A regressão linear calcula o vetor ww em ××\mathbb{R} \times \cdots \times \mathbb{R} que minimiza ED(w)\mathrm{E}_D(w).

Se X={1}×X = \{ 1 \} \times \mathbb{R}, podemos visualizar

A reta dada pela Regressão Linear para X={1}×X = \{ 1 \} \times \mathbb{R}

Com efeito, na Regressão Linear trata-se mais de uma fórmula do que de um algoritmo. Daremos duas vias para demonstrá-la, obtendo o vetor de pesos ww que minimiza esta distância

  1. como projeção de outro vetor a um espaço menor, e
  2. como zero da derivada do erro como função em ww.

Antes de começar, recordemo-nos de que, para uma matriz AA, a sua matriz transposta ATA^\mathrm{T} é a matriz cujas colunas são as linhas de AA, ou, equivalentemente, é a matriz obtida por espelhamento de AA ao longo da diagonal. Em particular, para v=Av = A uma matriz com uma linha ou coluna, um vetor linha respetivamente vetor coluna, vTv^{\mathrm{T}} é o vetor coluna respetivamente linha cujas entradas são as de vv.

Aproximação por Projeção

Para exemplificar a derivação da fórmula da regressão linear, restrinjamos primeiro a X=X = \mathbb{R}. Na Regressão Linear, queremos encontrar uma reta que minimize a distância a pontos (x1,y1)(x_1, y_1), …, (xN,yN)(x_N, y_N) no plano. Vimos que a distância entre

é medida pela distância Xwy \|X w - y\| entre o vetor XwXw e o vetor yy, onde

Então, qual é o ww que minimize esta distância? Os possíveis valores {Xw para w em }\{ Xw \text{ para } w \text{ em } \mathbb{R} \} formam uma reta (em N\mathbb{R}^N, o plano para N=2N = 2), e o ponto Xw0X w_0 da reta que é o mais próximo de yy é a projeção PyP y a esta reta; em fórmulas Xw0=Py. X w_0 = P y.

Projeção de um vetor a uma reta

O ponto Xw0X w_0 da reta é a projeção de yy se, e tão-somente se, a sua diferença yXw0y - X w_0 é ortogonal (ou perpendicular, isto é, forma um ângulo reto) à reta; em fórmulas, se o seu produto escalar é zero, XT(yXw0)=0 X^{\mathrm{T}} (y - X w_0) = 0 ou, equivalentemente, se XTXw0=XTy. X^{\mathrm{T}} X w_0 = X^{\mathrm{T}} y. Obtemos w0=X+y w_0 = X^+ y para o vetor X+=(XTX)1XTX^+ = (X^T X)^{-1} X^T escalado e transposto de XX.

Em geral, para XX de dimensão d<Nd < N maior, obtemos

enquanto y=(y1,...,yN)y = (y_1, ..., y_N) permanece um vetor de coluna com NN entradas (porque a saída Y=Y = \mathbb{R} não mudou).

Os possíveis valores {Xw para w em d}\{ Xw \text{ para } w \text{ em } \mathbb{R}^d \} formam um espaço (de dimensão dd em N\mathbb{R}^N; por exemplo, um plano para d=2d = 2). O ponto Xw0X w_0 do espaço que é o mais próximo de yy é a projeção PyPy de yy a este espaço; Obtemos, quando a matriz quadrática XTXX^T X é invertível (o que vale quase sempre porque N>dN > d, isto é, tem mais exemplos que parâmetros a especificar), da mesma forma w0=X+y w_0 = X^+ y para o pseudo-inverso X+=(XTX)1XTX^+ = (X^T X)^{-1} X^T de XX.

Aproximação por Derivação

Recordemo-nos de Equação 4.1, ED(w)=XwTy2/N. \mathrm{E}_D(w) = \| Xw^{\mathrm{T}} - y \|^2/N. Obtemos XwTy2/N=(XwTy)T(XwTy)/N=[wXTXwT2wXTy+yTy]/N,\begin{align} \| Xw^{\mathrm{T}} - y \|^2/N & = (Xw^{\mathrm{T}} - y)^{\mathrm{T}} (Xw^{\mathrm{T}} - y) /N\\ & = [w X^\mathrm{T} X w^\mathrm{T} - 2 w X^\mathrm{T} y + y^\mathrm{T} y]/N, \end{align} pela aplicação das igualdades (AB)T=BTAT e (AT)T=A (A B)^\mathrm{T} = B^\mathrm{T} A^\mathrm{T} \quad \text{ e } \quad (A^{\mathrm{T}})^{\mathrm{T}} = A para toda matriz AA e BB, em particular, para AA ou BB um vetor linha ou coluna vv (= matriz com uma única linha ou coluna); além, para dois vetores vv e ww, da simetria do seu produto escalar vTw=wTvv^{\mathrm{T}} w = w^{\mathrm{T}} v.

Como a função ED(w)\mathrm{E}_D(w) em ww é (por Equação 4.1) diferençável, podemos encontrar o seu mínimo no ponto w0w_0 em que o seu derivado iguala 00. Isto é, ED(w0)=0 \nabla \mathrm{E}_D(w_0) = 0 onde \nabla é o gradiente de ED\mathrm{E}_D, o vetor linha ED(w)=(ED(w)/w1,ED(w)/w2,...,ED(w)/wd) \nabla \mathrm{E}_D(w) = (\partial \mathrm{E}_D(w) / \partial w_1, \partial \mathrm{E}_D(w) / \partial w_2, ..., \partial \mathrm{E}_D(w) / \partial w_d) cujas entradas são as derivadas parciais.

Para derivar ED(w)D=[wXTXwT2wXTy+yTy]/N, \mathrm{E}_D(w)_D = [w X^\mathrm{T} X w^\mathrm{T} - 2 w X^\mathrm{T} y + y^\mathrm{T} y]/N, observamos primeiro

Para calcular wwXTXwT\nabla_w w X^\mathrm{T} X w^\mathrm{T}, abreviemos A=XTXA = X^{\mathrm{T}} X, e observemos que, para a função f:wwAwTf \colon w \mapsto w A w^{\mathrm{T}}, f(𝐰+𝐡)f(𝐰)=(𝐰+𝐡)A(𝐰+𝐡)T𝐰A𝐰T=𝐰A𝐡T+𝐡A𝐰T+𝐡A𝐡T=wf(w)+O(h)\begin{align} f(\mathbf{w}+\mathbf{h}) - f(\mathbf{w}) & = (\mathbf{w} + \mathbf{h}) A ( \mathbf{w} + \mathbf{h})^{\mathrm{T}} - \mathbf{w} A \mathbf{w}^{\mathrm{T}}\\ & = \mathbf{w} A \mathbf{h}^T + \mathbf{h} A \mathbf{w}^T + \mathbf{h} A \mathbf{h}^T\\ & = \nabla_w f(w) + O(\| h \|) \end{align} com wfh=𝐰A𝐡T+𝐡A𝐰T=𝐰A𝐡T+𝐰AT𝐡T \nabla_w f h = \mathbf{w} A \mathbf{h}^T + \mathbf{h} A \mathbf{w}^T = \mathbf{w} A \mathbf{h}^T + \mathbf{w} A^T \mathbf{h}^T onde usamos a simetria vTw=wTvv^{\mathrm{T}} \cdot w = w^{\mathrm{T}} v para v=hv = h e w=Axw = A x.

Se aplicamos estas equações a ED=[wTXTXw2wTXTy+yTy]/N\mathrm{E}_D = [w^\mathrm{T} X^\mathrm{T} X w - 2 w^\mathrm{T} X^\mathrm{T} y + y^\mathrm{T} y]/N, então obtemos o vetor linha En(w)=(2/N)(XTXwXTy). \nabla \mathrm{E}_{\mathrm{n}}(w) = (2/N) \cdot (X^\mathrm{T} X \cdot w - X^\mathrm{T} y). Logo, En(w)=0\nabla \mathrm{E}_{\mathrm{n}}(w) = 0 se, e tão-somente se, XTXw=XTyX^\mathrm{T} X \cdot w = X^\mathrm{T} y se, e tão-somente se, w=X+ycom X+=(XTX)1XT. w = X^+ y \quad \text{com } X^+ = (X^\mathrm{T} X)^{-1} X^\mathrm{T}.

Computação

Concluímos que o valor mínimo do erro específico ED(w) \mathrm{E}_D(w) é atingido se, e tão-somente se, XTXw=XTy, X^\mathrm{T} X w = X^\mathrm{T} y, isto é, se e tão-somente se, para XTXX^\mathrm{T} X invertível, w=Xy w = X^\dagger y onde X:=(XTX)1XT, X^\dagger := (X^\mathrm{T} X)^{-1} X^\mathrm{T}, é o pseudo-inverso (ou, mais exatamente, o Moore-Penrose inverso) de XX. Este vetor de pesos ww é a única solução ótima.

Esta computação do pseudo-inverso é a parte computacionalmente mais custosa da regressão linear.

Para acelerar a computação de X+X^+, computa-se uma fatoração X=QR X = Q R onde

por exemplo, pelo método de Gram-Schmidt: Denotem P1P_1, P2P_2, … as projeções aos vetores x1x_1, x2x_2, …, dadas por vx1Tvx1,vx2Tvx2,... v \mapsto x_1^{\mathrm{T}} v \cdot x_1, v \mapsto x_2^{\mathrm{T}} v \cdot x_2, ... Para cada ii = 11, 22, … o vetor 𝐪i:=xiP1xiPi1xi \mathbf{q}_i := x_i - P_1 x_i - \cdots - P_{i-1} x_i é ortogonal a 𝐪1\mathbf{q}_1, …, 𝐪i1\mathbf{q}_{i-1}. Logo, os vetores q1:=𝐪1/q1,q2:=𝐪2/q2,.... q_1 := \mathbf{q}_1 / \|q_1\|, q_2 := \mathbf{q}_2 / \|q_2\|, .... formam uma base ortonormal.

Isto é,

Porém, este método é frágil, isto é, pequenos erro de arredondamento em resultados intermediários podem levar a grandes erros nos resultados finais. A este fim, prefere-se o método de Gram-Schmidt modificado onde 𝐪i:=x1(1P1)(1Pi1)xi. \mathbf{q}_i := x_1 - (1 - P_1) \cdots (1 - P_{i-1}) x_i.

Graças a fatoração X=QRX = Q R com QQTQ Q^{\mathrm{T}}, obtemos X+=(RTR)1QRT. X^+ = (R^{\mathrm{T}} R)^{-1} QR^{\mathrm{T}}. A computação do inverso de uma matriz triangular em mais rápida do que a de uma matriz geral pois

Resumo

Concluímos que os passos do algoritmo da Regressão Linear consistem em:

  1. Dado D={(x1,y1),...,(xN,yN)}D = \{ (x_1, y_1), ..., (x_N, y_N) \}, define a matriz XX e o vetor yy por XT=(x1,...,xN) e yT=(y1,...,yN). X^\mathrm{T} = (x_1, ..., x_N) \quad \text{ e } \quad y^\mathrm{T} = (y_1, ..., y_N).
  2. Calcula o pseudo-inverso XX^\dagger da matriz XX, isto é, para XTXX^\mathrm{T} X invertível, X=(XTX)1XT. X^\dagger = (X^\mathrm{T} X)^{-1} X^\mathrm{T}.
  3. Devolve w=Xyw = X^\dagger y.

Animação

Para ganharmos um intuito como a Regressão Linear calcula a reta que aproxima melhor os pontos, há uma implementação online (em JavaScript) da Universidade do Illinois.

4.3 Regressão Logística

A Regressão Logística aplica-se quando

Por exemplo, nas questões,

Na Regressão Logística,

e

que são medidas de probabilidade obtidas pela composição com certa função logística.

Por exemplo, X=X = \mathbb{R}, onde xx mede a pressão sanguínea (ou arterial) do paciente, e yy indica se sofreu um ataque cardíaco ou não.

Enquanto o Perceptron decide para cada ponto se é preto ou branco (isto é, se é ao lado direito ou esquerdo da reta), a Regressão Logística agrisalha os pontos: quanto mais preto o ponto, tanto mais provável o evento em questão. Por exemplo, se cada ponto representa um cliente, que amortize as dívidas.

O grau de griso corresponde à probabilidade e os pontos aos exemplos observados

Com efeito, a função divina yy que queremos conhecer é uma variável aleatória condicional (binária).

Moralmente, yy,

Como Y={±1}Y = \{ \pm 1 \} é binário, P(y=1|x)=1P(y=1|x),(*) P (y = -1 | x) = 1 - P (y = 1 | x), \quad (*) basta conhecer P(y=1|x)P(y = 1 | x). Isto é, P(y=1|x)P(y = 1 | x) determina yy; em outras palavras, o conhecimento de P(y=1|x)P(y = 1 | x) corresponde ao conhecimento da variável aleatória condicional yy.

As nossas hipóteses serão aproximações a P(y=1|x)P (y = 1 | x); logo, por (*)(*), à variável aleatória condicional yy.

Função Logística

Para a regressão logística, em que as nossas hipóteses são funções cujos valores são probabilidades, precisamos de uma função (duas vezes) diferençável e monótona θ:[0,1]\theta \colon \mathbb{R} \to [0, 1].

A necessidade da monotonia da função θ\theta baseia-se na concepção que, dado um ponto xx, quanto maior o seu valor wTxw^\mathrm{T} \cdot x, tanto mais provável que a decisão seja positiva. (Por exemplo, quanto maior a pontuação do devedor, mais provável que consiga pagar os créditos.)

A função logística

A nossa escolha (e a da maioria) é a função logística (ou função sigmoid) definida por θ(s):=es/(1+es)=1/(1+es). \theta(s) := \mathrm{e}^s/(1 + \mathrm{e}^s) = 1/(1 + \mathrm{e}^{-s}). (Outra escolha popular para θ\theta é a função tangente hiperbólica θ=tanh:[1,1]\theta = \mathrm{tanh} \colon \mathbb{R} \to [-1, 1] definida por tanh:=(eses)/(es+es)\mathrm{tanh} := (\mathrm{e}^s - \mathrm{e}^{-s})/(\mathrm{e}^s + \mathrm{e}^{-s}).) Pelo gráfico da função logística, vemos que as duas extremidades se aproximam dos valores 00 e 11 rápido; também, satisfaz a simetria θ(s)=1θ(s)\theta(-s) = 1 - \theta(s) que nos será útil a seguir.

Log-Odds (= chances logarítmicas)

Relação à Distribuição Binomial

A medida de probabilidade, ou distribuição, mais simples é a de uma variável aleatória binária, isto é, que tem dois possíveis valores 00 e 11. Chama-se de Bernoulli, e para uma probabilidade fixa π\pi em [0,1][0, 1] é definida por p(x;π)=P(X=x)p(x; \pi) = P(X = x) onde P(X=1)=πeP(X=0)=1π P(X = 1) = \pi \quad e \quad P(X = 0) = 1 - \pi Expressemo-la pela função exponencial: p(x;π)=πx(1π)1x=exp(xlog(π)+(1x)log(1π))=exp(xlog(π1π)+log(1π)) \begin{aligned} p( x ; \pi) & = & \pi^x \left( 1 - \pi \right)^{1 - x}\\ & = & \exp \left( x \log \left( \pi \right) + \left( 1 - x \right) \log \left( 1 - \pi \right) \right) \\ & = & \exp \left( x \log \left( \frac{\pi}{1 - \pi} \right) + \log ( 1 - \pi) \right) \end{aligned} Isto é, p(x;η)=exp(xηc(η)) p ( x ; \eta ) = \exp ( x \eta - c(\eta) ) é uma distribuição definida pela exponencial (isto é, faz parte da família exponencial das distribuições) para um parâmetro η\eta e uma constante c(η)c(\eta) onde η:=log(π1π)\eta := \log ( \frac{\pi}{1 - \pi}) é a função logit (ou log-odds) de π\pi. A função logística (ou expit) é a função inversa da função logit; isto é, π=11+exp(η). \pi = \frac{1}{1 + \exp (- \eta)}.

Usos

Dificuldade da Computação da Distribuição Normal

Substituição

Comparação à Distribuição Normal

Regressão logística (modelo Logbit) em contraste ao modelo probit que usa a função da densidade da distribuição normal (e regressão de Poisson que usa a distribuição de Poisson).

As funções de densidade da distribuição normal e logística são próximas, uma da outra, para uma escolha de parâmetros apropriados a este fim:

Gráficos de densidade da distribuição normal e logística

Parâmetros

Como de costume, não explicitamos o parâmetro constante μ\mu, o valor esperado, na hipótese, mas usamos uma saída X={1}×××X = \{ 1 \} \times \mathbb{R} \times \cdots \times \mathbb{R} em que todos argumento tem a primeira entrada constante igual a 11. Isto é, w0=μw_0 = \mu.

Hipóteses

As nossas hipóteses são H:={h=θ(wT) para w=(w1,...,wd) em ××}. H := \{ h = \theta( w^\mathrm{T} \cdot ) \text{ para } w = (w_1, ..., w_d) \text{ em } \mathbb{R} \times \cdots \times \mathbb{R} \}.

O valor h(x)h(x) no intervalo [0,1][0, 1] corresponde à probabilidade condicional Ph(y|x)P_h(y | x) definida por: h(x) para y=1 e 1h(x) para y=1 h(x) \text{ para } y = 1 \quad \text{ e } \quad 1 - h(x) \text{ para } y = -1 (Por exemplo, dadas as características xx do cliente, a probabilidade que

A nossa função alvo é p(x)=P(y=1|x), p(x) = P(y = 1 | x), a probabilidade (condicional) que y=1y = 1 dado xx (por exemplo, dadas as características xx de um paciente, a probabilidade que ele sofra um ataque cardíaco, y=1y = 1).

Observamos mais exatamente que pp (e ph:=Ph(y=1|)p_h := P_h(y = 1 | \cdot)) é uma função densidade de probabilidade condicional (FDP), ou densidade de uma variável aleatória contínua condicional, que mede a probabilidade

Erro

A amostra D={x1,...,xN}D = \{ x_1, ..., x_N \} não revela diretamente p(x)=P(y=1|x)p(x) = P(y = 1 | x), a probabilidade que y=1y = 1 dado xx, mas a revela indiretamente: os seus valores y1y_1, …, yNy_N em {±1}\{ \pm 1 \} são distribuídos com probabilidade p(y1)p(y_1), …, p(yN)p(y_N).

Para estimar o erro que uma hipótese hh faz em aproximar yy sobre DD, usamos o estimador de máxima verossimilhança: Maximizar a verossimilhança quer dizer determinar os parâmetros hh da distribuição PhP_h que maximizam a probabilidade Ph(y1,...,yN|x1,...,xN)P_h(y_1, ..., y_N | x_1, ..., x_N).

Como supomos (x1,y1)(x_1, y_1), …, (xN,yN)(x_N, y_N) independente e identicamente distribuídos, Ph(y1,...,yN|x1,...,xN)=Ph(y1|x1)P(yN|xN). P_h(y_1, ..., y_N | x_1, ..., x_N) = P_h(y_1 | x_1 ) \cdots P(y_N | x_N ).

Recordemo-nos de que hh corresponde a probabilidade Ph(y|x)P_h(y | x) dada por: h(x) para y=1 e 1h(x) para y=1 h(x) \text{ para } y = 1 \quad \text{ e } \quad 1 - h(x) \text{ para } y = -1 Como h(x)=θ(wTx)h(x) = \theta(w^\mathrm{T} x) e θ(s)=1θ(s)\theta(-s) = 1 - \theta(s), esta igualdade pode ser simplificada a Ph(y|x)=θ(ywTx).(4.2) P_h(y | x) = \theta(y w^\mathrm{T} x). \qquad(4.2)

Como os valores de exp(x)=1/exp(x)\exp (- x) = 1/\exp (x) (e logo da função θ\theta) decrescem a zero rápido, é computacionalmente preferível maximizar esta probabilidade pelo seu logaritmo. Como a função N1log-N^{-1} \log é monótona decrescente (pelo fator de normalização negativo N1-N^{-1}), esta probabilidade é máxima se e tão-somente se ED(w)=N1logPh(y1,...,yN|x1,...,xN) \mathrm{E}_D (w) = -N^{-1} \log P_h(y_1, ..., y_N | x_1, ..., x_N) é mínima. Explicitamente, se e tão-somente se ED(w)=N1log(Ph(y1|x1)Ph(yN|xN))=N1log(1/Ph(y1|x1))++log(1/Ph(yN|xN))\begin{align} \mathrm{E}_D (w) & = - N^{-1} \log(P_h(y_1 | x_1 ) \cdots P_h(y_N | x_N ))\\ & = N^{-1} \log (1/P_h(y_1 | x_1)) + \cdots + \log (1/P_h(y_N | x_N)) \end{align} é mínima. Substituindo Equação 4.2, obtemos: N1n=1,...,Nlog(1/θ(ynwTxn)); N^{-1} \sum_{n = 1, ..., N} \log(1/\theta(y_n w^\mathrm{T} x_n)); substituindo θ1(s)=(1+es)/es=es+1\theta^{-1}(s) = (1 + e^{-s})/e^{-s} = e^{-s} + 1, concluímos: ED(w)=N1n=1,...,Nlog(1+eynwTxn). \mathrm{E}_D(w) = N^{-1} \sum_{n = 1, ..., N} \log(1 + \mathrm{e}^{-y_n w^\mathrm{T} x_n}). Observamos que ED\mathrm{E}_D é pequeno se sinal(wTxn)=yn\mathrm{sinal}(w^\mathrm{T} x_n) = y_n, isto é, quanto melhor ww classifica x1x_1, …, xNx_N, tanto menor este erro.

Algoritmo

Veremos como maximizar a verossimilhança, isto é, encontrar a medida que maximiza a probabilidade da nossa amostra. Equivalentemente, veremos como minimizar ED\mathrm{E}_D em dependência de ww. Para encontrar um mínimo, usa-se o gradiente de uma função que aponta na sua direção. Com efeito, para estar num mínimo, tem de ser zero.

Gradiente

Geometricamente, por exemplo, para uma função f:×f \colon \mathbb{R} \times \mathbb{R} \to \mathbb{R} de duas variáveis, no ponto (x0,y0)(x_0, y_0),

A derivada parcial como tangente na direção do eixo-xx

O gradiente f\nabla f de uma função f(x1,,xd)f(x_1, \ldots, x_d) no ponto x0x_0 é definido pelo vetor linha (e não coluna) f(x0)=(fx1(x0),,fxd(x0)). \nabla f(x_0) = (\frac{\partial f}{\partial x_1}(x_0), \ldots, \frac{\partial f}{\partial x_d}(x_0)).

Na nossa situação, onde f(w)=ED(w)=N1n=1,...,Nlog(1+eynwTxn), f(w) = \mathrm{E}_D(w) = N^{-1} \sum_{n = 1, ..., N} \log(1 + \mathrm{e}^{-y_n w^\mathrm{T} x_n}), para minimizar ED(w)\mathrm{E}_D(w),

  1. calculamos o seu gradiente em ww, o vetor linha cujas entradas são as derivadas parciais, ED(w)=(ED/w1(w),...,ED/wd(w))=N1(n=1,...,Nynxn/(1+eynwTxn))\begin{align} \nabla \mathrm{E}_D(w) & = (\partial \mathrm{E}_D/ \partial w_1(w), ..., \partial \mathrm{E}_D/ \partial w_d(w))\\ & = -N^{-1} (\sum_{n = 1, ..., N} y_n x_n /(1 + \mathrm{e}^{- y_n w^\mathrm{T} x_n})) \end{align} usadano

    note-se que cada parcela x=xnx = x_n é um vetor linha x=(x1,...,xd)x = (x_1, ..., x_d) em dd entradas, e

  2. buscamos ww tal que ED(w)=0\nabla \mathrm{E}_D (w) = 0.

Esta equação não tem uma solução analítica, isto é, não pode ser expressa por uma fórmula; do lado positivo, a função ED(w)\mathrm{E}_D(w) é convexa, por isso tem um único mínimo. Logo, nenhum dos métodos corre risco de convergir a um mínimo local (no lugar do mínimo global).

Para minimizar ED(w)\mathrm{E}_D(w), usamos

  1. ou o método de Newton aplicado à derivada wED(w)\nabla_w \mathrm{E}_D (w),
  2. ou o método do máximo declive aplicado à função ED(w)\mathrm{E}_D (w).

O método de Newton converge mais rapidamente do que o método do máximo declive; porém, a sua computação é mais custoso. Em geral, se a dimensão dd não é excecionalmente grande, continua a ser muito mais rápido.

Método de Newton

Estudamos o método de Newton

  1. para funções de uma variável com valores reais, e
  2. para funções de múltiplos argumentos com valores vetoriais (tal que o número das variáveis da entrada iguale ao da saída).

O uso do método de Newton para minimizar o erro na regressão logística (= o logaritmo da máxima verossimilhança) chama-se Fisher scoring.

Para funções reais

Dado uma função derivável f:f \colon \mathbb{R} \to \mathbb{R}, o método de Newton aproxima iterativamente um zero de ff, isto é, define x1x_1, x2x_2, …em \mathbb{R} com xnxx_n \to x tal que f(x)=0f(x) = 0. Geometricamente:

Pegamos um ponto (apropriado) x1x_1,

  1. olhamos o seu valor f(x1)f(x_1) sob ff, e
  2. a tangente em f(x1)f(x_1) ao gráfico de ff.

Esta tangente intersecta o eixo X em um ponto x2x_2.

  1. Olhamos o seu valor f(x2)f(x_2) sob ff, e
  2. a tangente em f(x2)f(x_2) ao gráfico de ff;

e assim por diante.

Moralmente, dado um ponto x0x_0, a tangente tx0t_{x_0} é a reta que aproxima ff em x0x_0 o melhor possível. Por isso, o zero x1x_1 de tx0t_{x_0}, que é facilmente computável graças a sua forma simples, aproxima o zero xx de ff. Em x1x_1, de novo, a tangente tx1t_{x_1} é a reta que aproxima ff em x1x_1 o melhor; de fato, como x1x_1 é mais próximo do zero xx de ff, a nova tangente tx1t_{x_1} aproxima ff melhor do que tx0t_{x_0} em volta de xx; em particular, o x2x_2 de tx1t_{x_1} é mais próximo do zero xx de ff do que o zero x1x_1 de tx0t_{x_0}.

O método de Newton

Como função no argumento hh, na iteração nn, a tangente tnt_n em f(xn)f(x_n) é definida por tn(xn+h):=f(xn)+f(xn)h, t_n(x_n + h) := f(x_n) + f'(x_n) h, logo, pondo h=xxnh = x - x_n, obtemos tn(x):=f(xn)+f(xn)(xxn). t_n(x) := f(x_n) + f'(x_n) (x-x_n). Como 0=t(xn+1)0 = t(x_{n + 1}), obtemos xn+1=xnf(xn)f(xn). x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_{n})}. Em outras palavras, o método de Newton é a iterada aplicação do operador de Newton N=Nf:\mathrm{N} = \mathrm{N}_f \colon \mathbb{R} \to \mathbb{R} definido por xxf(x)f(x). x \mapsto x - \frac{f(x)}{f'(x)}. De fato, se xn:=Nn(x0)xx_n := \mathrm{N}^n(x_0) \to x, então x=Nf(x)=xf(x)f(x)x = \mathrm{N}_f(x) = x - \frac{f(x)}{f'(x)}, logo f(x)=0f(x) = 0.

A única condição é o encontro de um ponto de partida x0x_0 tal que a sequência x1,x2,x_1, x_2, \ldots converge. Esta não é garantida, mas vale a convergência local quadrática:

Se ff é duas vezes diferençável, então pela Fórmula de Taylor f(x+h)=f(x)+f(x)h+Rf(x+h,h)h2 f(x + h) = f(x) + f'(x) h + \mathrm{R}'' f(x + h, h) h^2 com Rf(xh,h)f(x)/2\mathrm{R}'' f(x_h,h) \to f''(x)/2 para h0h \to 0. Para x+h=xn+1x + h = x_{n + 1} e x=xnx= x_n, e porque h=f(xn)f(xn)h = \frac{f(x_n)}{f'(x_n)}, obtemos f(xn+1)=f(xn)+f(xn)(xn+1xn)+Rf(xn+1,xn)(f(xn)f(xn))2=Rf(xn+1,xn)(f(xn)f(xn))2.\begin{align} f(x_{n + 1}) & = f(x_n) + f'(x_n) (x_{n + 1}-x_n) + \mathrm{R}'' f(x_{n + 1}, x_n) \left(\frac{f(x_n)}{f'(x_n)}\right)^2\\ & = \mathrm{R}'' f(x_{n + 1}, x_n) \left(\frac{f(x_n)}{f'(x_n)}\right)^2. \end{align} Em particular, |f(xn+1)||Rf(xn+1,xn)||f(xn)|2|f(xn)|2. |f(x_{n + 1})| \leq \frac{|\mathrm{R}'' f(x_{n + 1}, x_n)|}{|f'(x_n)|^2} \cdot |f(x_n)|^2.

Pondo

e C=M/m2C = M''/m'^2, obtemos |f(xn+1)|C|f(xn)|2. |f(x_{n + 1})| \leq C \cdot |f(x_n)|^2. Pondo dn=C|f(xn)|d_n = C \cdot |f(x_n)|, iterativamente dn+1dn2dn122dn1222d02n, d_{n + 1} \leq d_n^2 \leq d_{n-1}^{2 \cdot 2} \leq d_{n-1}^{2 \cdot 2 \cdot 2} \leq \ldots \leq d_0^{2^n}, isto é, C|f(xn)|(C|f(x0)|)2n. C \cdot |f(x_n)| \leq (C \cdot |f(x_0)|)^{2^n}. Concluímos que se |f(x0)|1/C=m2/M|f(x_0)| \leq 1/C = m'^2/M'', então f(xn)0f(x_n) \to 0 quadraticamente. Por exemplo, se |f(x0)|101m/M|f(x_0)| \leq 10^{-1} \cdot m'/M'', então o número de zeros de f(x0)f(x_0), f(x1)f(x_1), f(x2)f(x_2), … duplica a cada iteração.

Vemos aqui a convergência do método aplicado três vezes à função f(x)=x22f(x) = x^2 - 2 com o seu zero x0=2x_0 = \sqrt{2}:

Iteração Zero aproximativo Erro
0 11 0,4142135-0{,}4142135
1 1,51{,}5 0,08578640{,}0857864
2 1,416666671{,}41666667 0,00245310{,}0024531
3 1,414215691{,}41421569 0,00000210{,}0000021
Para funções de múltiplos argumentos

Suponhamos que f:XYf \colon X \to Y é uma função de várias variáveis independentes x1,...,xdx_1, ..., x_d tal que o número dd das variáveis dependentes da entrada iguale ao da saída, isto é, X=d e Y=d. X = \mathbb{R}^d \quad \text{ e } \quad Y = \mathbb{R}^d. Isto é, f=(f1,...,fd)f = (f_1, ..., f_d) onde cada função com valores reais f1f_1, …, fdf_d depende de dd variáveis x1x_1, …, xdx_d. Se ff é desta forma, então o seu gradiente f=f=gradff' = \nabla f = \mathrm{grad} f é uma matriz quadrática f=(fi/xj)i,j=1,...,d. \nabla f = (\partial f_i / \partial x_j)_{i,j = 1, ..., d}. Em particular, ff é desta forma quando ff é o gradiente de outra função FF, isto é, f=F=gradFf = \nabla F = \mathrm{grad} \, F. Neste caso, o seu gradiente f=(2F/xixj)i,j=1,...,d=(2Fx1x12Fx2x12Fxdx12Fx2x12Fx2x22Fx2xd2Fxdx12Fxdx22Fxdxd). \nabla f = (\partial^2 F / \partial x_i \partial x_j)_{i,j = 1, ..., d} = \begin{pmatrix} \frac{\partial^2 F}{\partial x_1 \partial x_1} & \frac{\partial^2 F}{\partial x_2 \partial x_1} & \ldots & \frac{\partial^2 F}{\partial x_d \partial x_1} \\ \frac{\partial^2 F}{\partial x_2 \partial x_1} & \frac{\partial^2 F}{\partial x_2 \partial x_2} & \ldots & \frac{\partial^2 F}{\partial x_2 \partial x_d} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 F}{\partial x_d \partial x_1} & \frac{\partial^2 F}{\partial x_d \partial x_2} & \ldots & \frac{\partial^2 F}{\partial x_d \partial x_d} \end{pmatrix}. é a matriz HF\mathrm{H}_F das segundas derivadas de FF, a matriz de Hesse de FF.

Se HF\mathrm{H}_F é invertível em xx (o que corresponde a f(x)f'(x)), então o operador de Newton se torna NF(x)=x+HF(x)1F(x) \mathrm{N}_F(x) = x + \mathrm{H}_F(x)^{-1} F(x)

O método de Newton continua a convergir rapidíssimo; porém, a computação da matriz de Hesse de FF em cada ponto é computacionalmente custoso (enquanto o método do máximo declive se contenta com a do mero gradiente). Contudo, se a dimensão dd não é excecionalmente grande, continua a ser muito mais rápido.

Método do Máximo Declive

Usamos o método numérico do Gradient Descent, o Método do Máximo Declive para minimizar ED(w)\mathrm{E}_D (w).

Seguindo iterativamente o máximo declive

Como a função ED(w)\mathrm{E}_D(w) é convexa, tem um único mínimo (em contraste à imagem). Este pode ser aproximado como segue:

Pelo gradiente, podemos calcular as derivadas fh(x):=limt0f(x+th)f(x)t \frac{\partial f}{\partial h}(x) := \lim_{t \to 0} \frac{f(x + t \cdot h)-f(x)}{t} em todas as direções hdh \in \mathbb{R}^d (enquanto, até agora, unicamente, nas dos eixos-x1x_1, …, xdx_d).

A derivada fh(x)\frac{\partial f}{\partial h}(x) da função ff em direção hh para hdh \in \mathbb{R}^d é dada por fh(x)=f(x)hT:=fx1(x)h1++fxd(x)hd. \frac{\partial f}{\partial h}(x) = \nabla f(x) \cdot h^{\mathrm{T}} := \frac{\partial f}{\partial x_1}(x) h_1 + \cdots + \frac{\partial f}{\partial x_d}(x) h_d. onde o produto xyT:=x1y1++xdyd x \cdot y^{\mathrm{T}} := x_1 y_1 + \cdots + x_d y_d é o produto escalar entre os vetores xx e yy. Tem-se xyT=||x||||y||cosα x \cdot y^{\mathrm{T}} = ||x|| ||y|| \cos \alpha onde α\alpha é o ângulo entre xx e yy.

Em particular, xyx \cdot y atinge o seu valor máximo, entre todos os vetores de um mesmo comprimento fixo, por exemplo entre todos os vetores unitários, quando xx e yy são múltiplos um do outro. Em particular, a derivada em x0x_0 é máxima, se derivamos em direção de f(x0)\nabla f(x_0); Isto é, geometricamente: O vetor gradiente indica a direção do máximo aclive (ou declive) cujo grau é medido pelo comprimento do gradiente!

Computação

Resumimos o algoritmo para a melhor escolha da hipótese

  1. pelo método de Newton aplicado à derivada wED(w)\nabla_w \mathrm{E}_D (w), e
  2. pelo método do máximo declive aplicado à função ED(w)\mathrm{E}_D (w).

Pelo Método de Newton

  1. Inicializa o vetor de pesos w(0)w(0). (**)
  2. Para t=0,1,...t = 0, 1, ...
    1. Calcula a matriz de Hesse H(t):=2ED(w(t))\mathrm{H}(t) := \nabla^2 \mathrm{E}_D (w(t)) em w(t)w(t).
    2. Calcula o novo zero w(t+1)=Nf(w(t))=w(t)+H(t)1f(w(t))w(t+1) = \mathrm{N}_{\nabla f}(w(t)) = \nabla w(t) + \mathrm{H}(t)^{-1} \nabla f(w(t)).
    3. Decide se continuar (com w(t+1)w(t + 1)) ou terminar a iteração. (\dagger)
  3. Devolve o último w(t)w(t) (isto é, onde a iteração parou).

onde recordamos ED(w)=N1(n=1,...,Nynxn/(1+eynwTxn))T \nabla \mathrm{E}_D(w) = -N^{-1} (\sum_{n = 1, ..., N} y_n x_n /(1 + \mathrm{e}^{y_n w^\mathrm{T} x_n}))^\mathrm{T} e 2ED(w)=(ED(w)) \nabla^2 \mathrm{E}_D (w) = \nabla (\nabla \mathrm{E}_D (w))

Quanto a (**), à escolha inicial de w(0)w(0), uma escolha comum para w(0)w(0) é 00, ou, para evitar o risco de uma má escolha específica, escolher cada peso w1w_1, …, wdw_d independentemente por uma distribuição normal.

Quanto a (\dagger), um bom critério para a decisão sobre a terminação da iteração, ele é dado pela satisfação de

enquanto t=0,1,...t = 0, 1, ... não chegou a

Pelo Método do Máximo Declive

  1. Inicializa o vetor de pesos w(0)w(0) (e define a margem de traslado η>0\eta > 0). (**)
  2. Para t=0,1,...t = 0, 1, ...
    1. Calcula o gradiente gt:=ED(w(t))g_t := \nabla \mathrm{E}_D (w(t)) em w(t)w(t).
    2. Põe a direção vt:=gt/gtv_t := - g_t / \|g_t\|.
    3. Atualiza o vetor de pesos w(t+1)=w(t)+ηvtw(t + 1) = w(t) + \eta \cdot v_t.
    4. Decide se continuar (com w(t+1)w(t + 1)) ou terminar a iteração. (\dagger)
  3. Devolve o último w(t)w(t) (isto é, onde a iteração parou).

onde recordamos ED(w)=N1(n=1,...,Nynxn/(1+eynwTxn))T \nabla \mathrm{E}_D(w) = -N^{-1} (\sum_{n = 1, ..., N} y_n x_n /(1 + \mathrm{e}^{y_n w^\mathrm{T} x_n}))^\mathrm{T}

Quanto a (**), às escolhas iniciais de η\eta e w(0)w(0),

Quanto a (\dagger), um bom critério para a decisão sobre a terminação da iteração, ele é dado pela satisfação de

enquanto t=0,1,...t = 0, 1, ... não chegou a

5 Transformação Linear

Estudaremos como transformar um problema polinomial em um problema linear, isto é,

Aí, podemos aplicar um dos nossos algoritmos lineares, como o Perceptron, a Regressão Linear ou Logística; depois, invertemos a linearização para responder ao problema inicial.

Em mais detalhes: Dada uma amostra DD, o algoritmo AA escolhe a hipótese hDh_D em HH que minimiza o erro específico ED(hD)\mathrm{E}_D(h_D). Em todos os algoritmos lineares, isto é, o Perceptron, a Regressão Linear ou Logística, temos a parametrização H𝐑××𝐑 H \leftrightarrow \mathbf{R} \times \cdots \times \mathbf{R} por h0(wT)w h_0(w^\mathrm{T} \cdot) \mapsfrom w onde h0h_0 é

Isto é, AA minimiza a função wED(h0(wT)) w \mapsto \mathrm{E}_D(h_0(w^\mathrm{T} \cdot)) sobre 𝐑××𝐑\mathbf{R} \times \cdots \times \mathbf{R}; os pontos da amostra x1x_1, …, xNx_N entram como constantes! Portanto, antes de ser dada a amostra, podemos adaptar a entrada XX ao algoritmo linear; isto é, aplicar uma função Φ:XX\Phi \colon X \to X' que diminua EΦ(D)(h0(wT)):=ED(h0(wTΦ())) \mathrm{E}_{\Phi(D)}(h_0({w'}^\mathrm{T} \cdot)) := \mathrm{E}_D(h_0({w'}^\mathrm{T} \Phi(\cdot))) (onde ww' é agora um vetor de pesos tal que wT{w'}^\mathrm{T} \cdot seja definido sobre XX').

Aplicar uma transformação polinomial para separar linearmente

5.1 Linearizar Elipses em torno da origem

Usamos o Perceptron sobre o plano X=𝐑×𝐑X = \mathbf{R} \times \mathbf{R} para separar os pontos do tipo +1+1, positivos, dos pontos do tipo 1-1, negativos, de uma amostra x1x_1, …, xNx_N por uma reta. Suponhamos que a amostra não é linearmente separável, mas que todos os pontos positivos estão cercados por um círculo.

Pontos Cercados

Um círculo no plano com raio rr é dado pela equação x12+x22=r, x_1^2 + x_2^2 = r, isto é, dado por uma equação polinomial quadrática, e a função h(x)=sinal(x12+x22r) h(x) = \mathrm{sinal} (x_1^2 + x_2^2 - r) separa entre os pontos positivos e negativos. Se escrevemos h(x)=sinal(w0x0+w1x1+w2x2) h(x) = \mathrm{sinal} (w'_0 x'_0 + w'_1 x'_1 + w'_2 x'_2) onde w0=r,w1=1,w2=1 e x0=1,x1=x12,x2=x22, w'_0 = r, w'_1 = 1, w'_2 = 1 \quad \text{ e } \quad x'_0 = 1, x'_1 = x_1^2, x'_2 = x_2^2, então hh é uma função linear (ignorando o sinal) hh' em x=(x0,x1,x2)x' = (x'_0, x'_1, x'_2) com (o vetor de) pesos w=(w0,w1,w2)w' = (w'_0, w'_1, w'_2). Explicitamente, h=sinal(hΦ) com h=wT e Φ:XX dada por (x0,x1,x2)(x0,x12,x22). h = \mathrm{sinal} (h' \circ \Phi) \quad \text{ com } h' = w'^\mathrm{T} \cdot \text{ e } \Phi \colon X \to X' \text{ dada por } (x_0, x_1, x_2) \mapsto (x_0, x_1^2, x_2^2). A função Φ:XX\Phi \colon X \to X' é chamada a transformação de características. A transformação leva toda função linear h:XYh' \colon X' \to Y sobre o espaço transformado XX' por h:=hΦ. h := h' \circ \Phi. a uma função, não necessariamente linear, h:XYh \colon X \to Y sobre o espaço original.

Ida e volta ao espaço transformado

Se hh' anula o erro específico, EΦ(D)h=0\mathrm{E}_{\Phi(D)} h' = 0, então igualmente hh o anula, ED=EΦ(D)h=0\mathrm{E}_D = \mathrm{E}_{\Phi(D)} h' = 0.

Se Φ\Phi é estabelecida antes de ser dada a amostra, então dVC(HΦ)dVC(H) \mathrm{d}_{\mathrm{VC}}(H_\Phi) \leq \mathrm{d}_{\mathrm{VC}}(H') onde HΦH_\Phi é o espaço das hipóteses {hΦ:h em H}\{ h \circ \Phi : h \text{ em } H \} e HH' é o espaço das hipóteses sobre XX'. Vale somente a desigualdade, mas não necessariamente a igualdade, isto é, não necessariamente toda função em HH' pode ser obtida por pré-composição de uma função em HH com Φ\Phi.

Por exemplo, se Φ\Phi é a transformação acima e o algoritmo é o Perceptron, Φ:XX dada por (x0,x1,x2)(x0,x12,x22). \Phi \colon X \to X' \text{ dada por } (x_0, x_1, x_2) \mapsto (x_0, x_1^2, x_2^2). então dVC(HΦ)dVC(H)=dVC(H)=3. \mathrm{d}_{\mathrm{VC}}(H_\Phi) \leq \mathrm{d}_{\mathrm{VC}}(H') = \mathrm{d}_{\mathrm{VC}}(H) = 3. Com efeito, a mesma configuração de pontos como em Figura 3.1 é também linearmente inseparável por uma elipse (que é centrada na origem).

Observação. A aplicação Φ\Phi tem de ser escolhida antes de ser dada a amostra; isto é, não pela avaliação dos dados, mas pela nossa compreensão do problema. Caso contrário, estamos efetivamente aumentando HH e assim dVC(H)\mathrm{d}_{\mathrm{VC}}(H).

5.2 Generalização da Transformação

Restamos no plano, isto é, d:=dimensão X=2d := \textrm{dimensão } X = 2. Enquanto a dimensão de XX' é igualmente d=2d = 2, somente podemos separar pontos por elipses centradas na origem do plano, o ponto (0,0)(0,0). Contudo, para obter todas as curvas quadráticas, precisamos aumentar a dimensão de XX' a d=5d' = 5 para aplicar Φ:(1,x1,x2)(1,x1,x2,x12,x1x2,x22). \Phi \colon (1, x_1, x_2) \mapsto (1, x_1, x_2, x_1^2, x_1 x_2, x_2^2). (Descontamos a primeira coordenada pela sua entrada fixa x0x_0.) Por esta transformação de características, podemos, por exemplo, trasladar o centro das elipses da origem (0,0)(0,0) a qualquer ponto no plano.

Mais geralmente, podemos considerar a transformação de características para curvas cúbicas, enfim, para polinômios de grau QQ qualquer. Uma tal transformação é chamada a transformação polinomial de grau QQ.

Mas, cautela! Agora d=2d = 2 tornou se d=Q(Q+3)/2d' = Q(Q+3)/2. Além de aumentar o esforço computacional do algoritmo, aumenta a dimensão de Vapnik-Chervonenkis, por exemplo, para o Perceptron de dVC(H)=d+1=3\mathrm{d}_{\mathrm{VC}}(H) = d+1 = 3 à dVC(H)=d+1=[Q(Q+3)/2]+1\mathrm{d}_{\mathrm{VC}}(H') = d'+ 1 = [Q(Q+3)/2] + 1.

Surge outra vez o dilema entre o erro geral e o erro específico:

5.3 O Artifício do Núcleo

Dada uma transformação Φ:XX\Phi \colon X \to X' do espaço vetorial XX de dimensão menor ao espaço vetorial (de re-descrição) XX' de dimensão maior. O artifício no Artifício do Núcleo consiste em calcular o núcleo (= produto escalar transformado) K:=Φ()Φ()K := \Phi(\cdot) \cdot \Phi(\cdot) sobre XX' diretamente a partir de XX, sem conhecer XX' nem Φ\Phi! Como XX' é de dimensão maior, isto é computacionalmente mais econômico.

Em vez de definir a transformação Φ\Phi, o produto KK é definido diretamente e a existência de Φ\Phi é implícita; se KK satisfaz uma certa positividade, ela é assegurada pelo Teorema de Mercer.

Com efeito, recordamos que o objetivo final num problema de aprendizado é a escolha da melhor hipótese hh em HH pelo algoritmo AA a partir da amostra DD. Para nós, melhor quer dizer minimizar certo erro EDh\mathrm{E}_D h sobre a amostra DD. Em todos os algoritmos lineares em Seção 4, identificamos hh com um vetor de pesos ww e obtivemos

A observação que importa é que em todos os três casos, para minimizar o erro ED(h)\mathrm{E}_D(h), basta saber o produto escalar wTxw^\mathrm{T} x! Em particular, se DD é transformado por uma aplicação Φ:XX\Phi \colon X \to X', é suficiente saber o valor do produto escalar transformado wTΦ(x)w^\mathrm{T} \Phi(x) para todos os xx em DD; contudo, é desnecessário conhecer Φ\Phi em si! Na prática, em vez de definir Φ\Phi, é diretamente definido o produto escalar transformado K(w,x):=wTxK(w, x) := w^\mathrm{T} x; o Teorema de Mercer define Φ\Phi implicitamente.

Aumentar a dimensão por uma transformação polinómial para poder separar linearmente

Princípio

Em cada um dos nossos algoritmos lineares em Seção 4, o erro específico ED\mathrm{E}_D dependia no final somente de um produto escalar. Após uma transformação linear Φ:XX\Phi \colon X \to X', este toma a forma: Φ(x)Φ(y) \Phi ( x ) \cdot \Phi ( y ) Si o espaço vetorial XX' é de alta dimensão, então a computação deste produto fica impraticável. A ideia é então substituir este produto por uma função KK da forma K(x,y)=Φ(x)Φ(y). K ( x , y ) = \Phi ( x ) \cdot \Phi ( y ).

Teorema de Mercer

O Teorema de Mercer (James Mercer, matemático inglês do século 1919) mostra que uma função contínua, simétrica e semi-definida KK pode ser expressa por um produto escalar em um espaço vetorial de grande dimensão.

Mais exatamente, se o domínio X×XX \times X de KK é um espaço mensurável, e se KK é semi-definida, isto é, i,jK(xi,xj)cicj0 \sum_{i,j}K(x_i,x_j)c_ic_j \geq 0 para qualquer conjunto finito {x1,...,xn}\{ x_1, ..., x_n \} no domínio XX e conjunto finito {c1,...,cN}\{ c_1, ..., c_N \} no contra-domínio YY (tipicamente 𝐑\mathbf{R}), então existe uma função Φ:XX\Phi \colon X \to X' onde XX' é um espaço vetorial pré-hilbertiano (provavelmente de maior dimensão) tal que: K(x,y)=Φ(x)Φ(y) K ( x , y ) = \Phi ( x ) \cdot \Phi ( y )

Vantagem

Assim, o produto escalar em um espaço vetorial de grande dimensão é substituído por um núcleo que é mais facilmente calculável. Esta é uma maneira econômica de transformar um classificador linear em um classificador não-linear. Pelo núcleo, a transformação Φ:XX\Phi \colon X \to X' nem precisa ser explicitada. Desta maneira, mesmo se o espaço vetorial XX' é de dimensão infinita, o produto escalar transformado, o núcleo, permanece calculável como exemplificado pelo núcleo gaussiano radial-simétrica: K(x,y)=exp(𝐱𝐲2/2σ2). K ( x , y ) = \exp (-{\|\mathbf {x} -\mathbf {y} \|^2}/{2 \sigma ^2}). Ele é muito usado para SVMs.

Outro exemplo, popular no processamento automático de linguagem natural, é o núcleo polinomial k(x,y)=(xy)d k(x,y) = (x \cdot y)^d para um inteiro d>1d > 1.

Aplicações

O artifício do núcleo foi apresentada pela primeira vez em 19641964 por Aizerman, mas teve pouca repercussão. Ele pegou pelo artigo “A Training Algorithm for Optimal Margin Classifiers” por Boser et al. (publicado em 19921992) que fundou a teoria dos Support Vector Machines. Desde então, aplica-se em algoritmos de aprendizado de máquina como

6 Redes Neurais

Recordemo-nos de que, formalmente, em um problema de aprendizado, temos

e o método de aprendizado:

Uma rede neural (feed-forward ou sem realimentação) consiste em neurónios agrupados em camadas onde a entrada de cada neurónio são as saídas de todos os neurónios da camada anterior.

A primeira camada é a da entrada, e a última a da saída; as outras chamam se camadas ocultas. Por exemplo, o diagrama

  /o\
o--o--o
  \o/

representa uma rede neural de uma única camada oculta com três neurónios.

Se a rede neural tem múltiplas camadas ocultas, então é uma rede neural profunda, as quais são usadas no Deep Learning, no aprendizado profundo.

  /o\-/o\-/o\
o--o---o---o--o
  \o/-\o/-\o/

Um neurónio é uma função h:×× h \colon \mathbb{R} \times \cdots \times \mathbb{R} \to \mathbb{R} que é uma composição h(x)=g(f(x))h(x) = g(f(x)) de

6.1 Rede Neural de uma Única Camada

Para entender estes diagramas, comecemos o curso com as redes neurais de uma única camada: Uma rede de Perceptron que tem uma única camada oculta e uma única saída consiste em um único neurónio.

Um neurónio descreve uma classe de problemas de aprendizado cujas hipóteses se caracterizam pela composição de uma função de saída não-linear com uma função afim; esta classe compreende, entre outros métodos,

Neles,

Uma rede neural com um úncio neurónio.

O método de aprendizado:

6.2 Teorema de Aproximação Universal

Em uma rede neural de múltiplas camadas, a hipótese hh é a composição de camadas de neurónios 𝐡\mathbf{h} onde

Observação. Se (a função de cada) o neurónio fosse linear ou afim, então a função da rede neural inteira seria linear ou afim.

Contudo, a função divina raramente é afim (isto é, o seu gráfico uma reta). Para aproximar qualquer função contínua, o Teorema de Aproximação Universal confirma que para qualquer função contínua, existe uma combinação linear de composições de uma função afim com uma função contínua, monótona e limitada que se aproxima dela arbitrariamente bem. Isto é, basta compor a função afim com uma função (escalada) contínua, monótona e limitada para poder aprender (= aproximar) qualquer função contínua:

Teorema de Aproximação Universal. Seja gg uma função não-constante, limitada, monotonamente crescente e contínua. Dada qualquer função f:[0,1]f \colon [0, 1] \to \mathbb{R} e ϵ>0\epsilon > 0, existem funções afins f1f_1, f2f_2, … :[0,1]\colon [0, 1] \to \mathbb{R} e escalares α1\alpha_1, α2\alpha_2, … tal que d(f,α1gf1+α1gf1+)<ϵ \mathrm{d}(f, \alpha_1 g \circ f_1 + \alpha_1 g \circ f_1 + \cdots) < \epsilon onde

Uma tal função gg é chamada de uma função de ativação. Exemplos são, por exemplo,

O Teorema de Aproximação Universal vale, de forma análoga, para funções afins de múltiplos argumentos com múltiplos pesos w1w_1, …, wew_e, isto é,

Observação. O Teorema de Aproximação Universal se aplica diretamente a uma rede neural de propagação à frente de uma única camada. Porém, é apenas um teorema de existência. Não trata as questões de aprendizagem, em particular, as

Observação. A função de ativação satisfaz só no caso da função logística as propriedades do Teorema de Aproximação Universal, isto é, é

Porém, a função do sinal não é contínua, e a identidade não é limitada.

6.3 Rede Neural de Múltiplas Camadas

Uma rede neural aa (artificial, tacitamente subentendido de agora em diante) de propagação dianteira ou à frente (= Feedforwad) consiste em múltiplas camadas:

Uma rede neural com duas camadas ocultas.

Hipótese

Cada camada é uma função de múltiplas entradas e saídas ××××\mathbb{R} \times \cdots \times \mathbb{R} \to \mathbb{R} \times \cdots \times \mathbb{R} da seguinte forma:

  1. A camada de entrada é a identidade,

  2. cada camada oculta é uma ênupla 𝐡=(h1,h2,...)\mathbf{h} = (h_1, h_2, ...) de neurónios. Cada neurónio hh é a composição h=gfh = g \circ f de

    1. uma função de ativação gg fixa, isto é, que é a mesma para todos os neurónios em todas as camadas ocultas (mas não os da camada da saída). Exemplos são, por exemplo,

      • para a regressão linear, a identidade g=idg = \mathrm{id},
      • para o Perceptron, o sinal g(x)=1g(x) = 1 se x0x \geq 0 e 1-1 caso contrário,
      • para o MultiClass-Perceptron, g=argmaxg = \mathrm{argmax}, isto é, o argumento ii com fi(x)=max{f1(x),...,fn(x)}f_i(x) = \max \{ f_1(x), ..., f_n(x) \},
      • para a regressão logística
        • a função logística θ:[1,1]\theta \colon \mathbb{R} \to [-1, 1] definida por θ(x)=1/(1+ex)\theta(x) = 1/(1 + e^x), ou
        • a função tangente hiperbólica θ=tanh:[1,1]\theta = \mathrm{tanh} \colon \mathbb{R} \to [-1, 1] definida por tanh:=(eses)/(es+es)\mathrm{tanh} := (\mathrm{e}^s - \mathrm{e}^{-s})/(\mathrm{e}^s + \mathrm{e}^{-s}).
      • para a regressão logística multinomial, certa função softmax
    2. uma função afim ff que é definida por certos coeficientes w1w_1, w2w_2, … e por um certo limiar bb, isto é, f(x)=wTx+b=w1x1++wdxd+b f(x) = w^T x + b = w_1 x_1 + \cdots + w_d x_d + b

  3. A camada de saída é um neurónio onde a função de ativação é uma função de saída que pode ter uma forma diferente, por exemplo,

Se todos os neurónios da mesma camada têm como número de entradas o dos neurónios da camada precedente, então a rede de Perceptron é totalmente conectada (= fully connected);

A função (de hipótese hh que se aproxima da função divina) de uma rede neural de propagação à frente é a sucessiva composição das ênuplas das funções para cada camada h=𝐡1𝐡2 h = \mathbf{h}^1 \circ \mathbf{h}^2 \circ \cdots

Em vez de um limiar, para facilitar a notação, suponhamos que exista uma entrada adicional igual a 11:

Convenção. Para facilitar a notação, suponhamos de agora em diante que cada camada tenha como entrada um fator igual a 11, isto é, X={1}××× X = \{ 1 \} \times \mathbb{R} \times \cdots \times \mathbb{R} cujas ênuplas numeremos por (x0,x1,...)(x_0, x_1, ...). Desta maneira, o limiar bb corresponde ao peso w0w_0, e não necessita mais ser considerado separadamente.

Medida de Erro

Com a saída não discreta, gostaríamos de tomar em conta o tamanho da diferença h(x)y(x)h(x) - y(x) em cada ponto xx; usaremos a diferença quadrática a este fim, isto é ED(h)=[h(x1)y(x1)]2++[h(xN)y(xN)]2. \mathrm{E}_D (h) = [h(x_1) - y(x_1)]^2 + \cdots + [h(x_N) - y(x_N)]^2.

O método do Máximo Declive

O algoritmo usa o método do Máximo Declive para minimizar o erro quadrático. Ele busca um mínimo local por um ponto no qual a derivada, o gradiente, da medida de erro ED\mathrm{E}_D como função em ww é zero, isto é, todas as derivadas parciais ao longo dos pesos dos neurónios esvaem-se.

Mais exatamente, recordemo-nos de que cada camada ll tem múltiplos neurónios hilh^l_i, e cada neurónio atribui a cada entrada jj (= a saída do neurónio jj da camada precedente) um peso wijlw^l_{ij}. Para minimizar ED(w)\mathrm{E}_D (w) como função dos pesos w=(wijl)w = (w^l_{ij}), isto é, para calcular o gradiente ED(w)=ED(w)/wijl\nabla \mathrm{E}_D (w) = \partial \mathrm{E}_D (w) / \partial w^l_{ij}, dado pelas derivadas parciais, e aproximar o valor zero:

  1. Inicializa o vetor de pesos w(0)w(0) (e define a margem de traslado η>0\eta > 0). (\dagger)
  2. Para t=0,1,...t = 0, 1, ...
    1. Calcula o gradiente gt:=ED(w(t))g_t := \nabla \mathrm{E}_D (w(t)) em w(t)w(t).
    2. Põe a direção vt:=gt/gtv_t := - g_t / \|g_t\|.
    3. Atualiza o vetor de pesos w(t+1)=w(t)+ηvtw(t + 1) = w(t) + \eta \cdot v_t.
    4. Decide se continuar (com w(t+1)w(t + 1)) ou terminar a iteração. (\ddagger)
  3. Devolve o último w(t)w(t) (isto é, onde a iteração parou).

Quanto a (\dagger), às escolhas iniciais de η\eta e w(0)w(0),

Quanto a (\ddagger), um bom critério para a decisão sobre a terminação da iteração, ele é dado pela satisfação de

enquanto t=0,1,...t = 0, 1, ... não chegou a

6.4 Vetorização

Para acelerar a computação, as saídas da função afim (de múltiplas saídas) de cada camada é calculada por matrizes:

Saída

Em vez de calcular separadamente, para cada neurónio de uma camada, z1=w1Tx+b1,z2=w2Tx+b2,... z_1 = w_1^T x + b_1, z_2 = w_2^T x + b_2, ... e a1=g(z1),a2=g(z2),..., a_1 = g(z_1), a_2 = g(z_2), ..., é mais eficiente calcular z=WTx+b z = W^T x + b e a=(g(z1),g(z2),...) a = (g(z_1), g(z_2), ...) onde z=(z1,z2,...)z = (z_1, z_2, ...), b=(b1,b2,...)b = (b_1, b_2, ...) e WW é a matriz com as linhas w1w_1, w2w_2, …

Amostra

Para vetorizar, simultanear, a computação sobre múltiplas entradas, isto é, sobre todos os exemplos x1x_1, x2x_2, … da amostra, pomos X=(x1,x2,...) e b=(b,b,...) X = (x_1 , x_2 , ... ) \quad \text{ e } \quad b = (b, b, ...) e calculamos Z=(z1,z2,...)=WX+b Z = (z_1, z_2, ...) = W X + b

6.5 Auto-diferenciação inversa pela Regra da Cadeia

Dada uma rede neural de propagação à frente cuja medida de erro é o erro quadrático. Dada uma amostra x1x_1, …, xNx_N com valores y(x1)y(x_1), …, y(xN)y(x_N), (a metade d’) o erro quadrático é E=(h(x1)y(x1)2++h(xN)y(xN)2)/2N. \mathrm{E} = (\|h(x_1) - y(x_1)\|^2 + \cdots + \|h(x_N) - y(x_N)\|^2)/2N. (O fator de normalização 1/21/2 simplificará a fórmula da derivada a seguir.) A rede é parametrizada pelos pesos w=(wijl)w = (w^l_{ij}) dos neurónios. Queremos minimizar E\mathrm{E} em dependência de ww. Para minimizar E\mathrm{E} em dependência de ww, calculemos as derivada parciais E/wijl \partial \mathrm{E} / \partial w^l_{ij} para, idealmente, encontrar um zero comum entre elas. Como E=(h(x1)y(x1)2++h(xN)y(xN)2)/2N. \mathrm{E} = (\|h(x_1) - y(x_1)\|^2 + \cdots + \|h(x_N) - y(x_N)\|^2)/2N. e h(x)y(x)2=(h1(x)y1(x))2++(hd(x)yd(x))2, \|h(x) - y(x)\|^2 = (h_1(x) - y_1(x))^2 + \cdots + (h_d(x) - y_d(x))^2, podemos primeiro calcular E/wijl\partial \mathrm{E} / \partial w^l_{ij} para cada exemplo x=x1x = x_1, …, xNx_N e cada neurónio i=1i = 1, …, dd da saída e depois somar os resultados. Logo, para simplificar as fórmulas, suponhamos um único exemplo xx e um único neurónio de saída, isto é, N=1N = 1 e d=1d = 1 tais que E=12(h(x)y(x))2. \mathrm{E} = \frac{1}{2} (h(x) - y(x))^2.

Pela Regra da Cadeia, E/wijl=E/zjlzjl/wijl(*) \partial \mathrm{E} / \partial w^l_{ij} = \partial \mathrm{E} / \partial z^l_j \cdot \partial z^l_j / \partial w^l_{ij} \quad (*) onde zjlz^l_j é a função afim do neurónio jj da camada ll cujo valor em xx é computado por zjl(x)=w0jla0l1(x)+w1jla1l1(x)+ z^l_j(x) = w^l_{0j} a^{l-1}_0(x) + w^l_{1j} a^{l-1}_1(x) + \cdots

Para o neurónio ii na camada ll, denotemos

Para calcular o fator ao lado direito do produto em (*)(*), observemos que pela Regra do Produto zjl/wijl=(w0jla0l1+w1jla1l1+)/wijl=ail1. \partial z^l_j / \partial w^l_{ij} = \partial (w^l_{0j} a^{l-1}_{0} + w^l_{1j} a^{l-1}_{1} + \cdots) / \partial w^l_{ij} = a^{l-1}_{i}. Concluímos E/wijl=δjlail1.() \partial \mathrm{E} / \partial w^l_{ij} = \delta^l_j \cdot a^{l-1}_{i}. \quad (\dagger)

A Derivada do Erro da última camada

Calculemos o fator ao lado esquerdo do produto em (*)(*), o erro δL\delta^L da saída, do único neurónio da última camada LL. Pela Regra da Cadeia, δjL=E/zL=12(aLy)2/zL=(gzLy)gzL=(hy)gzL. \delta^L_j = \partial \mathrm{E} / \partial z^L = \frac{1}{2} \partial (a^L - y)^2 / \partial z^L = (g \circ z^L - y) \cdot g' \circ z^L = (h - y) \cdot g' \circ z^L. Concluímos E/wiL=δjLaiL1=(hy)gzjLaiL1. \partial \mathrm{E} / \partial w^L_i = \delta^L_j a^{L-1}_{i} = (h - y) g' \circ z^L_j \cdot a^{L-1}_{i}.

Expressemos recursivamente as derivadas parciais das camadas anteriores l=L1l = L-1, … pelas posteriores; comecemos por expressar as de l=L1l = L-1 pelas de l=Ll = L:

A Derivada do Erro da penúltima camada

Para calcular E/wijL1\partial \mathrm{E} / \partial w^{L-1}_{ij} do neurónio ii da penúltima camada L1L-1, basta por ()(\dagger) calcular δiL1\delta^{L-1}_i. Para calcular o erro δiL1\delta^{L-1}_i do neurónio ii da penúltima camada L1L-1, observemos que zLz^L depende de a1L1a^{L-1}_1, a2L1a^{L-1}_2, … Explicitamente, zL=w1La1L1+w2La2L1+=w1Lgz1L1+w2Lgz2L1+.(**) z^L = w^L_{1} a^{L-1}_1 + w^L_{2} a^{L-1}_2 + \cdots = w^L_{1} g \circ z^{L-1}_1 + w^L_{2} g \circ z^{L-1}_2 + \cdots. \quad (**) Pela Regra da Cadeia δiL1=E/ziL1=E/zLzL/ziL1. \delta^{L-1}_i = \partial \mathrm{E} / \partial z^{L-1}_i = \partial \mathrm{E} / \partial z^{L} \cdot \partial z^{L} / \partial z^{L-1}_i. Os dois fatores, por definição respetivamente derivação parcial de (**)(**), são E/zjL=δL e zL/ziL1=wiLgziL1; \partial \mathrm{E} / \partial z^{L}_j = \delta^L \quad \text{ e } \quad \partial z^{L} / \partial z^{L-1}_i = w^L_i g' \circ z^{L-1}_i; logo δiL1=gziL1wiLδL. \delta^{L-1}_i = g' \circ z^{L-1}_i w^L_i \cdot \delta^L.

A Derivada do Erro da antepenúLTIMA CAMADA

Para calcular E/wijL2\partial \mathrm{E} / \partial w^{L-2}_{ij} do neurónio ii da antepenúltima camada L2L-2, basta por ()(\dagger) calcular δiL2\delta^{L-2}_i. Para calcular o erro δiL2\delta^{L-2}_i do neurónio ii da antepenúltima camada L2L-2, observemos outra vez que zL1z^{L-1} depende de a1L2a^{L-2}_1, a2L2a^{L-2}_2, … Explicitamente, zjL1=w1jL1a1L2+w2jL1a2L2+=w1jL1g(z1L2)+w2jL1g(z2L2)+.(***) z^{L-1}_j = w^{L-1}_{1j} a^{L-2}_1 + w^{L-1}_{2j} a^{L-2}_2 + \cdots = w^{L-1}_{1j} g(z^{L-2}_1) + w^{L-1}_{2j} g(z^{L-2}_2) + \cdots. \quad (***) Pela Regra da Cadeia δiL2=E/ziL2=E/zL1zL1/ziL2=jE/zjL1zjL1/ziL2 \delta^{L-2}_i = \partial \mathrm{E} / \partial z^{L-2}_i = \partial \mathrm{E} / \partial z^{L-1} \cdot \partial z^{L-1} / \partial z^{L-2}_i = \sum_j \partial \mathrm{E} / \partial z^{L-1}_j \cdot \partial z^{L-1}_j / \partial z^{L-2}_i onde a última igualdade expande o produto matricial do penúltimo termo. Os dois fatores de cada termo da soma, por definição respetivamente derivação parcial de (***)(***), são E/zjL1=δjL1 e zjL1/ziL2=wijL1gziL2; \partial \mathrm{E} / \partial z^{L-1}_j = \delta^{L-1}_j \quad \text{ e } \quad \partial z^{L-1}_j / \partial z^{L-2}_i = w^{L-1}_{ij} g' \circ z^{L-2}_i; logo δiL2=jδjL1wijL1gziL2=gziL2jwijL1δjL1. \delta^{L-2}_i = \sum_j \delta^{L-1}_j \cdot w^{L-1}_{ij} g' \circ z^{L-2}_i = g' \circ z^{L-2}_i \sum_j w^{L-1}_{ij} \cdot \delta^{L-1}_j. Por indução, vale esta equação para cada neurónio jj em qualquer camada l=L3l = L-3, … no lugar de L2L-2.

6.6 Algoritmo Propagação para Trás

O algoritmo da Propagação para Trás (= Backpropagation) é um algoritmo para calcular eficientemente o gradiente E\nabla \mathrm{E} pela Regra da Cadeia (de funções deriváveis). Em geral, fora do contexto de uma rede neural, este algoritmo é conhecido como auto-diferenciação inversa.

Seja niln^l_i a função do neurónio ii da camada ll. Lembremo-nos de que n=ghn = g \circ h para uma função de ativação gg e uma função afim hh. O algoritmo da Propagação para Trás,

  1. Calcula para cada entrada x=xnx = x_n os valores dos neurónios para a frente, isto é, dada a entrada xx,
    1. calcula h(x)h(x) e n(x)=g(h(x))n(x) = g(h(x)) para todos os neurónios n=nijl=ghijln = n^l_{ij} = g \circ h^l_{ij} das camadas ocultas 11, 22, …, m1m-1 e
    2. calcula h(x)h(x) e n(x)=gs(h(x))n(x) = g_s(h(x)) para todos os neurónios da última camada mm.
  2. Calcula para cada entrada x=xnx = x_n as derivadas E/wijl\partial \mathrm{E} / \partial w^l_{ij} dos neurónios para trás, isto é, calcula
    1. o erro δm\delta^m da última camada,
    2. os erros δm1\delta^{m-1}, δm2\delta^{m-2}, … das camadas precedentes, e
    3. as derivadas parciais E/wijl=δjlnil1\partial \mathrm{E} / \partial w^l_{ij} = \delta^l_j n^{l-1}_i
  3. Calcula a derivada do erro da amostra inteira E/wijl=E/wijl(x1)++E/wijl(xN) \partial \mathrm{E} / \partial w^l_{ij} = \partial \mathrm{E} / \partial w^l_{ij}(x_1) + \cdots + \partial \mathrm{E} / \partial w^l_{ij}(x_N)
  4. Atualiza os pesos por wijl(t+1)=wijl(t+1)αE/wijl w^l_{ij}(t+1) = w^l_{ij}(t+1) - \alpha \partial \mathrm{E} / \partial w^l_{ij}

Observação. A computação das derivadas das funções de ativação é usualmente fácil, por exemplo:

7 Redes Recorrentes

7.1 Redes Recorrentes

Redes recorrentes são redes neurais artificiais que contêm ciclos (direcionados). Fazem sucesso

Redes recorrentes de Elman

Uma rede recorrente
Uma rede recorrente desdobrada

As matrizes ponderadas dos neurónios são W(a),W(x),W(y), e W=[W(a)|W(x)] W(a), W(x), W(y), \text{ e } W = [W(a) | W(x)] Pomos, no passo t+1t+1, a(t+1)=g(a)(W[a(t)|x(t)]+b(a)) e y(t+1)=g(y)(W(y)a(t)+b(y)) a(t+1) = g(a)(W [a(t) | x(t)] + b(a)) \quad \text{ e } \quad y(t+1) = g(y)(W(y) a(t) + b(y)) onde

Comparação com Redes de retropropagação

Uma rede recorrente não precisa de ter uma entrada e saída de comprimento fixo, mas ambas podem variar. Esta restrição poderia ser contornada por um tamanho máximo suficiente (da entrada e saída) e preenchimento.

Tipos

Tipos diferentes

Retropropagação através do tempo

Retropropagação numa rede recorrente desdobrada

7.2 Redes Convolucionais

7.3 Mapas Auto-Organizáveis

Um mapa auto-organizável é usado no aprendizado não-supervisionado; isto é, para encontrar um espaço de rótulos YY e aproximar a função divina y:XYy \colon X \to Y que rotula as entradas sem erros.

São dados

Como método, usamos como

Exemplo

Sejam v(1)v(1), …, v(4)v(4) dados por [0.8,0.7,0.4],[0.6,0.9,0.9],[0.3,0.4,0.1],[0.1,0.1,0.3] [ 0.8, 0.7, 0.4 ], [ 0.6, 0.9, 0.9], [ 0.3, 0.4, 0.1 ], [ 0.1, 0.1, 0.3 ] e w1w_1 e w2w_2 por [0.5,0.6,0.8] e [0.4,0.2,0.5]. [0.5, 0.6, 0.8] \quad \text{ e } \quad [0.4, 0.2, 0.5]. Seja η(t)=0,5\eta(t) = 0,5 e h(i,i0)=1h(i,i_0) = 1 se, e tão-somente se, i=i0i = i_0. Calculamos d1(t)=v(1)w1d_1(t) = \| v(1) - w_1 \| e d2(t)=v(1)w2d_2(t) = \| v(1) - w_2 \| d1(t)=(0.50.8)2+(0.60.7)2+(0.80.4)2=0.26 e d2(t)=(0.40.8)2+(0.20.7)2+(0.50.4)2=0.42 d_1(t) = ( 0.5 - 0.8 )^2 + ( 0.6 - 0.7 )^2 + ( 0.8 - 0.4 )^2 = 0.26 \quad \text{ e } \quad d_2(t) = ( 0.4 - 0.8 )^2 + ( 0.2 - 0.7 )^2 + ( 0.5 - 0.4 )^2 = 0.42

Como d1<d2d_1 < d_2, atualizamos w1w_1 e obtemos w1=[0.65,0.65,0.6]w_1 = [0.65, 0.65, 0.6]. Calculemos novamente d1=(0.650.6)2+(0.650.9)2+(0.600.9)2=0.155 e d2=(0.40.6)2+(0.20.9)2+(0.50.9)2=0.69 d_1 = ( 0.65 - 0.6 )^2 + ( 0.65 - 0.9 )^2 + ( 0.60 - 0.9 )^2 = 0.155 \quad \text{ e } \quad d_2 = ( 0.4 - 0.6 )^2 + ( 0.2 - 0.9 )^2 + ( 0.5 - 0.9 )^2 = 0.69 Como d1<d2d_1 < d_2, atualizamos w1w_1 e obtemos w1=[0.625,0.775,0.75]w_1 = [0.625, 0.775, 0.75]. Calculemos novamente d1=(0.6250.3)2+(0.7750.4)2+(0.7500.1)2=0.67 e d2=(0.40.3)2+(0.20.4)2+(0.50.1)2=0.21 d_1 = ( 0.625 - 0.3 )^2 + ( 0.775 - 0.4 )^2 + ( 0.750 - 0.1 )^2 = 0.67 \quad \text{ e } \quad d_2 = ( 0.4 - 0.3 )^2 + ( 0.2 - 0.4 )^2 + ( 0.5 - 0.1 )^2 = 0.21 Como d2<d1d_2 < d_1, atualizamos w2=[0.35,0.3,0.3]w_2 = [0.35, 0.3, 0.3]; calculamos d1=(0.6250.1)2+(0.7750.1)2+(0.7500.3)2=0.93 e d2=(0.3500.1)2+(0.3000.1)2+(0.3000.3)2=0.10 d_1 = ( 0.625 - 0.1 )^2 + ( 0.775 - 0.1 )^2 + ( 0.750 - 0.3 )^2 = 0.93 \quad \text{ e } \quad d_2 = ( 0.350 - 0.1 )^2 + ( 0.300 - 0.1 )^2 + ( 0.300 - 0.3 )^2 = 0.10 Como d2<d1d_2 < d_1, atualizamos w2=[0.225,0.2,0.3]w_2 = [0.225, 0.2, 0.3].

Referências Bibliográficas

Abu-Mostafa, Yaser S., Malik Magdon-Ismail, e Hsuan-Tien Lin. 2012. Learning from Data. Vol. 4. AMLBook New York, NY, USA.