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

• oferece um plano de saúde acessível a todo mundo,
• proporciona uma educação personalizada a cada criança,
• disponibiliza carros auto-conduzidos baratos a todos, e
• um trabalho significativo com sentido a cada homem e mulher."

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,

• na medicina: a partir de um conjunto de dados de saúde com os diagnósticos por especialistas, aprender a diagnosticar.

• na mineração de dados, o uso de aprendizado de máquina para detectar estruturas estatísticas lucrativas (em bancos de dados relacionais). Notavelmente, para antecipar

  • os interesses de um usuário de um portal on-line a partir daqueles nas visitas anteriores;
  • em particular, as futuras compras dos clientes de um comércio on-line a partir das anteriores.

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:

• o da dificuldade computacional, e
• o da significância (como modelação da realidade).

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:

4. 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.

5. 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.

6. 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.

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

   • os seus modelos, e
   • o algoritmo da Retropropagação de Erro, um método de máximo declive que reajusta os pesos dos neurônios conforme a uma regra de correção de erro.

8. 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.

9. 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) $E$ tem o seu valor mínimo, usaremos

• uma aproximação iterativa, um método de ensaio e erro direcionado, como no Perceptron,
• a projeção de um vetor a um (hiper)plano (onde o vetor de saída é o vetor do (hiper)plano que é mais próximo do vetor de entrada), e
• a computação de um ponto em que a derivada $\nabla E$ de $E$ é zero.

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

• da Álgebra Linear para tratar problemas multidimensionais como o da regressão linear em várias variáveis,
• da análise multidimensional para encontrar pontos (localmente) máximos de funções em várias variáveis.

Links

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:

• qualquer coleção de seres matemáticos,
• qualquer reunião de objetos, determinados e diferenciáveis, quer esses objetos pertençam à realidade exterior, quer sejam objetos do pensamento, ou
• qualquer reunião das partes que constituem um todo.

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

Por exemplo, o conjunto

• dos números naturais $\mathbb{N} = \{ 1, 2, 3, \ldots \}$ é denotado por $\mathbb{N}$ .
• dos números inteiros $\mathbb{Z} = \{ -2, -1, 0, 1, 2, \ldots \}$ é denotado por $\mathbb{Z}$,
• dos números racionais $\{ x/y \text{ para } x,y \text{ em } \mathbb{Z} \}$ é denotado por $\mathbb{Q}$; por exemplo, $2/3$ é nele , e
• dos números reais $\{ a_N 10^N + \cdots + a_1 10 + a_0 + a_{-1} 10^{-1} + \cdots \}$ para $a_N$, , $a_1$, $a_0$, $a_{-1}$ em $\{$ $0$, $1$, , $9$ $\}$ é denotado por $\mathbb{R}$; por exemplo, $\pi = 3,14159 \ldots$ é nele.

Podemos comparar dois conjuntos $A$ e $B$:

• denote $A \supseteq B$ que $A$ contém (ou inclui) $B$, e
• denote $A \subseteq B$ que $A$ é contido (ou incluso) $B$.

Podemos formar um novo conjunto a partir de dois conjuntos $A$ e $B$:

• denote $A \cup B$ a união de $A$ e $B$, o conjunto dos elementos que pertencem a $A$ ou $B$,
• denote $A \cap B$ a intersecção de $A$ e $B$, o conjunto dos elementos que pertencem a $A$ e $B$;
• se $A \supseteq B$, então denote $A - B$ a diferença entre $A$ e $B$, o conjunto dos elementos que pertencem a $A$ mas não a $B$.

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 \times B$ o seu produto cujos elementos são $(a,b)$ para $a$ em $A$ e $b$ em $B$, isto é, $$A \times B = \{ (a, b) \text{ para } a \text{ em } A \text{ e } b \text{ em } B \}.$$ Se $B = A$, escrevemos $A^2$ em vez de $A \times A$, e $A^3$ em vez de $A \times A \times A$, e assim por diante. Por exemplo, $\mathbb{R}^2$ é o plano (euclidiano), e $\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) = \text{ expressão em $x$}$$ onde na expressão figuram

• operações aritméticas $+$, $-$, $\cdot$, $/$ …
• sobre números reais, constantes, funções algébricas como $x^2$ e funções especiais como $\exp(x)$, $\log(x)$, $\mathrm{sen}(x)$, …

Por exemplo:

1. A distância $s$ percorrida por um objeto na queda livre depende do tempo da queda $t$: vale $s = g \cdot t^2$ onde $g = 9,8 \mathrm{m}/\mathrm{s}^2$ é a constante da aceleração gravitacional da terra.
2. A forca de atração $K$ entre duas massas $m'$ e $m''$ depende de $m'$, $m''$ e a distância $r$ entre elas: Pela lei gravitacional de Newton $K = G (m' m'')/r^2$ onde $G = 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:

3. 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 $1$, $2$, $3$, … e o preço correspondente de $100$ Centavos, $20$ Centavos, $5$ Centavos, …

Definição. Uma função $f$ é uma regra que associa a cada elemento $x$ de um conjunto $X$ exatamente um elemento $y$ de um conjunto $Y$.

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

• a $x$ como variável (independente) ou argumento,
• a $y$ como variável dependente ou valor (da função),
• a $X$ como domínio da função, e
• a $Y$ como contra-domínio da função.

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

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

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

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

• uma equação,

obtemos pela substituição da variável por um número real como $0,5$, $1$, $2$, $1000$, …

• uma tabela de valores $x$ e $y$ dado pela avaliação do lado direito da igualdade $f(x) = ...$, e

• um gráfico

  1. pela marcação dos pontos $(x,y)$ no plano que são dados pelos valores da tabela, e
  2. pela conexão destes pontos.

Em mais detalhes:

• Na forma de uma equação como nos exemplos acima: $y = f(x)$, por exemplo, $y = x^2,\mathrm{sen} x \ldots$ Para facilitar, fazemos o convênio seguinte: Se escrevemos apenas a regra de associação, por exemplo, $f(x) = 1/(x(x-3))$ ou $\sqrt x$, então o domínio é o subconjunto máximo de $\mathbb{R}$ para que esta regra seja definida (quer dizer, faça sentido). Por exemplo, nestes exemplos, $X = \mathbb{R} - \{0,3\}$ e $X = \mathbb{R}_{\geq 0}$.

• Na forma de uma tabela de valores, por exemplo: Um experimento mede a tensão $U$ de um resistor em dependência da corrente $Y$. A tabela tem as entradas $Y = 50;100;150, \ldots (mA)$ e $U = 2;4,6; \ldots (V)$. Aqui $X = \{50,100, \ldots\}$ (e $Y = \mathbb{R}_{\geq 0}$). (Gostaríamos de extrapolar esta função, isto é, estender o seu domínio a $\mathbb{R}_{\geq 0}$; a este fim, parece provável que $U = RI$ com $R = 0,04 \Omega$.)

• A equação funcional $y = f(x)$ associa a cada valor $x$ um único valor $y$, em símbolos, $x \mapsto y = f(x)$. Um tal par de valores $(x_0, y_0)$ pode ser interpretado como ponto $P$ no plano cartesiano. Para cada par de valores $(x_0,y_0)$ obtemos exatamente um ponto. Dado um ponto $P$, os números reais $x_0$ e $y_0$ são chamados das coordenadas (cartesianas). O conjunto de todos os pontos $(x, y = f(x))$ forma a curva da função (ou gráfico), que ilustra o percurso da função $y = f (x)$. (Por exemplo, a parábola $y = x^2$ ou uma função afim $y = ax + b$.)

  Para desenhar a curva:

  1. Enche uma tabela de valores para uns argumentos $x'$, $x''$, …

  2. Desenha os pontos dados nela, e

  3. Conecta-os para obter o percurso da curva da função.

De vez em quando, para destacar que um objeto, por exemplo, uma função $h \colon X \to Y$, depende de outro objeto, por exemplo, de um conjunto $D$ ou uma ênupla $w$, escrevemos $h(D)$ ou $h_D$ respetivamente $h(w)$ ou $h_w$ em vez de $h$.

Aplicação

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

• o domínio $X$, e
• o contra-domínio $Y$ de $f$

dizemos que manda ou envia cada argumento $x$ em $X$ a um único valor $y$ em $Y$.

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

Uma função manda ou envia cada argumento $x$ em $X$ a um único valor $y$ em $Y$ (ou associa a cada $x$ um único $y$). Escrevemos $$x \mapsto y$$ e denotemos este valor $y$ por $f(x)$. Frequentemente, $X = \mathbb{R}$ ou $X = \mathbb{R} \times \cdots \times \mathbb{R}$ e $Y = \mathbb{R}$ ou $Y = \{ \pm 1 \}$. Por exemplo, a função $f \colon \mathbb{R} \to \mathbb{R}$ dada por $x \mapsto x^2$ manda $2$ em $\mathbb{R}$ a $2^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 $f$ e $g$ (sobre quaisquer domínios e imagens) pode ser obtida outra por concatenação; a função composta ou a composição $g \circ f$, dado que a imagem de $f$ é contida no domínio de $g$, isto é, $Y(f) \subseteq X(g)$. É definida por $$g \circ f \colon x \mapsto g(x) \mapsto f(g(x)),$$ simbolicamente, para obter $g \circ f(x) = g(f(x))$, substituímos $x$ em $g(x)$ por $f(x)$.

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

Inversão de funções

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

Matematicamente, a função $f$ tem o inverso $g = f^{-1}$, se $g(f(x)) = x$ e $f(g(x)) = x$. Por exemplo, sobre $\mathbb{R}_{\geq 0}$ vale $\sqrt (x^2) = x = (\sqrt{x})^2$ para $f(x) = x^2, g(x) = \sqrt x$, e $(2x + 1)/2-1/2 = x=2(x/2-1/2) + 1$ para $f(x) = 2x + 1$ e $g(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 = f^{-1}$ é o espelhamento do gráfico da função invertida $f$ na diagonal dos pontos cuja coordenada $x$ é igual à coordenada $y$.

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.

• A parábola $y = x^2$ não é invertível sobre $\mathbb{R}$, mas só sobre $\mathbb{R}_{\geq 0}$ e $\mathbb{R}_{\leq 0}$ (pela radiciação quadrática).
• A função $y = 2x + 1$ cresce de modo estritamente monótono, em particular, é invertível.
• O seno (que mede o comprimento do cateto oposto no círculo unitário) cresce de modo estritamente monótono no intervalo $[-\pi/2,\pi/2]$; logo tem um inverso, o neste intervalo.
• a exponencial $\exp$ é invertível pelo logaritmo $\log$.

Resumimos:

• Toda função estritamente monótona (crescente ou decrescente) é invertível.
• Na inversão o domínio e imagem trocam os papéis.
• Se o domínio e imagem coincidem, obtemos o gráfico da função inversa pelo espelhamento do gráfico da função na diagonal $y = x$.

Algarismos

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

• a base binária $b = 2$ com os algarismos $0$ e $1$, e
• a base hexadecimal $b = 16$ com os algarismos $0, ..., 9$ e $A$, $B$, $C$, $D$, $E$ e $F$ (que correspondem a $10$, $11$, $12$, $13$, $14$ e $15$).

Isto é,

• no conta-quilómetro binário, o último algarismo retorna à posição inicial após dois quilómetros, o penúltimo após $2^2 = 4$ quilómetros, e assim por diante,
• no conta-quilómetro hexadecimal, o último algarismo retorna à posição inicial após $16$ quilómetros, o penúltimo após $16^2 = 256$ quilómetros, e assim por diante.

Por exemplo, $$1101 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$$ e $$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.

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.

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

Enquanto

• o computador à esquerda aprende as regras, especifica-as,
• o computador à direita aplica-as para calcular os resultados.

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

• a especificação se contatamos a cada da moeda e classificamos as moedas por estas medidas com uma certa margem de erro, e
• o aprendizado se derivamos estas medidas com uma certa margem de erro a partir de um grande conjunto de moedas.

Concluímos:

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

• para os dados a partir de que aprenderemos será a amostra ou os exemplos.

Pensamos

• de cada exemplo como uma entrada, e
• do nosso resultado de aprendizado (tipicamente uma classificação) como saída.

Aprendizado com Supervisionamento

No aprendizado com supervisionamento, os exemplos são classificados. Isto é, temos pares $$(\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 $$(\text{entrada}, \text{saída e a sua avaliação})$$ Destacamos que, dada uma entrada $x$, não necessariamente todos os pares $(x,y)$ para todas as possíveis saídas $y$ 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 $x$ do tabuleiro, $y$ 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,

• no jogo Xadrez, a função poderia avaliar a configuração do tabuleiro
  • pelo número de peças de cada um,
  • pela a sua centralidade e agilidade;
• no jogo Go, a função poderia contar
  • as pedras e
  • as casas controladas por elas;
• no jogo Gamão, simplesmente avaliar uma configuração como
  • neutra se o partido é indeciso,
  • positiva ($+ 1$), se o partido é ganhado, e
  • negativa ($-1$), se o partido é perdido.

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,

• na medicina: Aprender a diagnosticar a partir de

  • dados sobre à saúde dos pacientes e
  • os seus diagnósticos.

• na identificação de conteúdo: Decidir se um e-mail é Spam (= lixo) (ou Ham [= não Spam]) a partir de duas pastas de e-mails,

  • uma do tipo Spam e
  • a outra do tipo Ham.

  O algoritmo de aprendizado a ser apresentado, que se baseia unicamente na frequência de palavras-chave lixosas no e-mail, revelou-se mais eficiente do que todos os outros até então criados.

• nas finanças: Decidir, para um suplicante de um crédito, sobre

  • a questão se conseguirá pagar as suas dívidas ou não,
  • a probabilidade que conseguirá pagar as suas dívidas,
  • sobre a quantia que lhe será concedida,

  a partir

  • dos dados financeiros de credores anteriores e
  • dos seus desempenhos no pagamento das dívidas (quer dizer, faliu ou cumpriu?).

• no futebol: decidir se um jogador pertence à seleção nacional a partir das

  • capacidades (físicas) de jogadores da Série A e
  • se foram nomeados.

1.3 Formalização

Formalmente, em um problema de aprendizado, temos

• a entrada $X$,
• a saída $Y$,
• os dados ou a amostra $D = \{ x_1, ..., x_N \}$ (= um conjunto finito em $X$ sobre o qual a função alvo é conhecida, isto é, $y_1 = y(x_1)$, …, $y_N = y(x_N)$ são conhecidos, e
• a função alvo (ou função de regressão ou classificadora) $y \colon X \to Y$ (= a função ótima, que sempre acerta, a ser aproximada; chamamo-la também de função divina para exprimir que existe e é aproximável com certa probabilidade, mas inatingível)

e

• as hipóteses $H = \{ h \colon X \to Y \}$ (= um conjunto de funções que aproximam $y$), e
• uma medida de erro $\mathrm{E} \colon X \times X \to [0, \infty]$ que mede a diferença entre os valores da hipótese e os da função alvo, e
• um algoritmo $A$ que escolhe uma função $h$ em $H$ que aproxima" $y$ “o melhor”, em particular, minimiza $\mathrm{E}$ sobre $D$.

Enfatizamos que

• a entrada, a saída, a amostra e a função alvo são dadas,
• as hipóteses e o algoritmo são escolhidos pelo programador.

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 \colon X \to Y$, será uma variável aleatória, isto é, intuitivamente, para cada argumento $x$, em vez de devolver

• um único valor $y_0$,

devolve

• ou para cada valor $y_0$ uma probabilidade $P(y = y_0)$ (quando $Y$ é discreto, por exemplo, binário, finito ou $\mathbb{N}$),
• ou para cada intervalo de valores $[y', y'']$ uma probabilidade $P(y \text{ em } [y', y''])$ (quando $Y$ é contínuo, por exemplo, um intervalo $[a, b]$, a reta $\mathbb{R}$, ou o plano $\mathbb{R} \times \mathbb{R}$).

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

Porém, os valores $y_1$, …, $y_N$ para os dados $x_1$, …., $x_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

• do diagnóstico, temos
  • $X$ = ênuplas de atributos médicos (= os de um paciente)
  • $Y$ = doenças
  • $D$ = diagnósticos históricos
• da classificação de e-mails em Spam ou Ham, temos
  • $X$ = ênuplas do número de ocorrências de palavras (= os de um e-mail)
  • $Y$ = Sim ou Não
  • $D$ = e-mails recebidos e suas classificações como Spam ou Ham
• da questão se um devedor poderá pagar as suas dívidas ou não, temos
  • $X$ = ênuplas de atributos financeiros (= os de um e-mail)
  • $Y$ = Sim ou Não
  • $D$ = históricos de créditos concedidos
• da composição da seleção nacional, temos
  • $X$ = ênuplas de capacidades (= as de um jogador)
  • $Y$ = Sim ou Não
  • $D$ = seleções anteriores.

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

• a avaliação da solvência de um possível devedor por um banco. A entrada $X$ aqui são os dados financeiros de um cliente, por exemplo

  • idade
  • salário
  • haveres
  • dívidas

• a avaliação da aptidão de um jogador para a seleção nacional. A entrada $X$ aqui são os dados físicos do jogador, por exemplo a velocidade

  • do chute, e
  • do jogador

1.5 Pontuação

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

• a entrada pode ser interpretada como ênupla de números reais, e
• a saída é binária: Sim e Não.

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,

• para certo Neymar, a velocidade
  • do chute é 100 km por hora, e
  • do jogador é 40 km por hora;
• para certo Roberto Carlos, a velocidade do
  • do chute é 200 km por hora, e
  • do jogador é 20 km por hora;
• para certo Frederico, a velocidade do
  • do chute é 100 km por hora, e
  • do jogador é 20 km por hora

Por exemplo, poderíamos dar,

• peso $10$ à velocidade do jogador, e
• peso $1$ à velocidade do chute.

Obtemos,

• para Neymar a pontuação $1 \cdot 100 + 10 \cdot 40 = 500$
• para Roberto Carlos a pontuação $1 \cdot 200 + 10 \cdot 20 = 400$
• para Frederico a pontuação $\cdot 100 + 10 \cdot 20 = 300$

Se Neymar e Roberto Carlo estão na seleção nacional, mas Frederico não, então, por exemplo, um limiar de $320$ 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 é,

• a entrada $X$
• a saída $Y$
• a amostra $D = \{ x_1, ..., x_N \}$ (= um conjunto finito em $X$ sobre o qual a função alvo é conhecida, isto é, $y_1 = y(x_1)$, …, $y_N = y(x_N)$ são conhecidos, e
• a função alvo (ou divina) $y \colon X \to Y$ (= a função ótima, que sempre acerta, a ser aproximada)

e o método, isto é,

• as hipóteses $H = \{ h \colon X \to Y \}$ (= um conjunto de funções que aproximam $y$), e
• um algoritmo $A$ que escolhe uma função $h$ em $H$ que aproxima" $y$ (e em particular $D$) o mais possível.

2.1 Erro

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

O que significa a mais próxima de $y$?

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

• quando $Y = \{ \pm 1 \}$ é binária, isto é, existem os dois erros $h(x) = 1$, mas $y(x) = -1$ e vice versa $h(x) = -1$, mas $y(x) = 1$,
  • podemos atribuir a cada erro a mesma importância, isto é, definir a distância pelo número de erros $$\mathrm{E}_D (h) = \# \{ \text{erros} \}, \quad \text{ ou }$$
  • podemos distinguir entre as gravidades $w$ e $v$ dos erros (por exemplo, quando pensamos na deteção de uma doença grave e contagiosa como HIV, é menos grave detetar à toa, um falso positivo $w$, do que deixá-la passar impercebida, $v$), isto é, definir o erro por $$\mathrm{E}_D (h) = w \cdot \# \{ \text{erros do primeiro tipo} \} + v \cdot \# \{ \text{erros do segundo tipo} \}.$$
• quando $Y = \mathbb{R}$, gostaríamos de tomar em conta o tamanho da diferença $h(x) - y(x)$ em cada ponto $x$; usualmente, usa se a diferença quadrática a este fim, isto é $$\mathrm{E}_D (h) = [h(x_1) - y(x_1)]^2 + \cdots + [h(x_N) - y(x_N)]^2.$$

O programador determina

• as hipóteses $H = \{ h \colon X \to Y \}$, e
• a medida do erro na amostra $\mathrm{E}_D$, e

em seguida

• o algoritmo $A$ que busca a hipótese $h$ que minimize $\mathrm{E}_D(h)$.

Porém, isto não quer dizer que $h$ minimize o erro fora da amostra, isto é, se aproxime da função divina em todo lugar. Esta proximidade depende da escolha justa de $H$ e $\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

• $f(x) = 1$, mas $y(x) = -1$ e, vice versa,
• $f(x) = -1$, mas $y(x) = 1$,

são iguais, basta contar os pontos em que $f$ erra (isto é, difere de $y$) $$\mathrm{E}_D(f) := \mathrm{P}(\{ x \in D \text{ tal que } f(x) \neq y(x) \})$$ isto é, $$\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 $f$ à função divina $y$:

• para uma saída binária $Y = \{ \pm 1 \}$, isto é, os dois erros $f(x) = 1$, mas $y(x) = -1$ e, vice versa, $f(x) = -1$, mas $y(x) = 1$, queremos distinguir entre as gravidades $w$ e $v$ dos erros, ou
• para $Y = \mathbb{R}$, queremos tomar em conta o tamanho da diferença $f(x) - y(x)$ em cada ponto $x$

A este fim, introduzimos a função de custo $e \colon Y \times Y \to [0,\infty[$ tal que $$\mathrm{E}_D (f) = 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,

• Quando $Y = \{ \pm 1 \}$, sim ou não, e queremos tomar em conta que o erro

  • que $f(x) = 1$ mas $y(x) = -1$ é muito mais grave
  • que $f(x) = -1$, mas $y(x) = 1$.

  Por exemplo, é muito mais grave um leitor de dedo num caixa eletrônico

  • aceitar uma impressão digital erroneamente como a dono do cartão de crédito

  do que

  • rejeitar erroneamente a do dono.

  Por exemplo, se o primeiro erro é $1000$ vezes mais grave, isto é,

  $f(x)$ \ $y(x)$	$1$	$-1$
  $1$	$0$	$1000$
  $-1$	$1$	$0$

  obtemos $$\begin{align} & \mathrm{E}_D(h)\\ = & 1000 \cdot P_D(f(x) = 1 \text{ e } y(x) = -1) + 1 \cdot P_D(f(x) = -1 \text{ e } y(x) = 1). \end{align}$$ Isto é, a função de custo $$e(f(x), y(x)) \colon \{ (-1,-1), (1,1), (-1,1), (1,-1) \} \to \mathbb{R}$$ é dada por $(1, -1) \mapsto 1000$, $(-1, 1) \mapsto 1$ (e $0$ alhures).

• Quando $Y = \mathbb{R}$, e queremos tomar em conta a distância entre $f(x)$ e $y(x)$, a escolha mais comum é o valor médio da diferença quadrática, $$\begin{align} \mathrm{E}_D(f) & = \mathbf{E}_D [(f-y)^2]\\ & = [(f(x_1) - y(x_1))^2 + \cdots + (f(x_1) - y(x_1))^2]/N \end{align}$$ isto é, $e(f(x), y(x)) := [f(x) - y(x)]^2$. Usa-se, por exemplo, na regressão linear. Observamos

  • que o quadrado $\cdot^2$ (em vez do valor absoluto $| \cdot |$ ) penaliza poucos pontos muito distantes mais do que muitos pontos pouco distantes; por exemplo, $1$ erro de uma distância de $3$ mais do que $3$ erros de uma distância de $1$;
  • que se $Y = \{ \pm 1 \}$, então $[f(x) - y(x)]^2 = 1$ se e tão-somente se $f(x) \neq y(x)$. Isto é, a função de custo para funções reais generaliza a função de custo de contagem (isto é, que conta os erros) de para funções cujos valores são binárias.

• Quando $Y = [0, 1]$, isto é, $y$ é uma (media de) probabilidade, a melhor escolha para a hipótese $P = f$ (parametrizada por certos parâmetros como a média e a variância da probabilidade) a partir da amostra $D$ e os resultados $y(D)$ é, segundo o princípio da máxima verossimilhança, aquela escolha que maximiza a probabilidade $P(y(D) \mid D)$ da observação dos valores $y(D)$ dada a amostra $D$. Isto é, $$\mathrm{E}_D(f) = P(y(D) \mid D)$$ Para $(x_1, y_1)$, …, $(x_N, y_N)$ independente e identicamente distribuídos, após aplicação do logaritmo (ao negativo), queremos minimizar o erro logarítmico (a verossimilhança logarítmica, ou log-likelihood em inglês) $$\mathrm{E}_D(f) = -[\log P(y_1 | x_1) + \cdots + \log P(y_N | x_N)]/N$$ Isto é, a função de custo para cada exemplo é $$e(f, y)(x) = - \log (Py(x) | x).$$

• Como estamos mais interessados em minimizar o erro do que no seu valor exato, podemos aplicar uma função monótona $m$ ao estimador do erro $e$, por exemplo, como acima, o logaritmo $\log$ (para diminuir valores muito grandes). Isto é, como $m$ é monótona, a composição $m \circ e$ é mínima se e tão-somente se $e$ é mínimo.

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 $D$ é acertar na entrada inteira $X$:

Seja, por exemplo, a saída $Y = \{ \pm 1 \}$ binária, isto é, um problema de classificação binária. Dada a amostra $D = \{ x_1, ..., x_N \}$ e uma função $f$, podemos calcular o erro específico por $$\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 $f$ erre sobre $D$. (Em Abu-Mostafa, Magdon-Ismail, e Lin (2012), denotado por $\mathrm{E}_{\mathrm{in}}$ para significar dentro da amostra.) Por exemplo, o algoritmo Perceptron, se termina, consegue $\mathrm{E}_D(f(D)) = 0$.

Mas, como $y$ é desconhecida, não sabemos o erro geral, $$\mathrm{E}_X(f) := \mathrm{P}(\{ x \in X \text{ tal que } f(x) \neq y(x) \}),$$ isto é, a probabilidade que $f$ erre sobre $X$. (Em Abu-Mostafa, Magdon-Ismail, e Lin (2012), denotado por $\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 = \{ x_1, ..., x_N \}$ e uma função $f$, podemos calcular o erro específico, $$\mathrm{E}_D(f)$$ isto é, a probabilidade que $f$ erre sobre $D$. (Em Abu-Mostafa, Magdon-Ismail, e Lin (2012), denotado por $\mathrm{E}_{\mathrm{in}}$ para significar dentro da amostra.) Por exemplo, o algoritmo Perceptron, se termina, consegue $\mathrm{E}_D(f(D)) = 0$.

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

Se, por exemplo,

• $X = \{ 1, 2, 3, ..., 8 \}$ e $Y = \{ \pm 1 \}$ (classificação binária), e
• $D$ tem $5$ pontos,

qualquer função que coincide em $D$ com $y$ é uma possível solução; sobram $3$ valores a definir. Qual destas $\# Y^3 = 2^3$ extensões dos $5$ aos $8$ 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 $A$ que calcula para qualquer amostra $D= \{x_1, ..., x_N\}$ uma hipótese $h = h(D)$ em $H$ que seja provavelmente aproximadamente correta, isto é:

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

Recordemo-nos de que

• a integral $\mathrm{E}_X(h(D)) = \int_X e(h(D), y) \mathrm{dP}$ mede o erro geral entre $h(D)$ e $y$ ($< \epsilon$ = Aproximadamente Correto), e
• a probabilidade $\mathrm{P}(\mathrm{E}_X(h(D)) < \epsilon)$ mede o conjunto (em $X \times \cdots \times X$) em que a ênupla $D = (x_1, ..., x_N)$ implica uma escolha $h(D)$ pelo algoritmo $A$ que é próxima de $y$, isto é, tal que o erro $\mathrm{E}_X(h(D)) < \epsilon$; como é $> 1 - \delta$, é, em palavras, (altamente) provável.

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 - \delta$, isto é, provavelmente), então a probabilidade do erro é pequena, $< \epsilon$, isto é, a função é aproximadamente correto.

Em Seção 3, dados $\epsilon$ e $\delta > 0$, calcularemos para uns problemas de aprendizado o tamanho $N$ da amostra $D$ que garante que $$\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 $h$ escolhida pelo algoritmo $A$ a partir de $D$ tem um erro geral $\mathrm{E}_X h$ pequeno?

Holdout

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

• usar o conjunto $D'$ como amostra para a computação da melhor hipótese $h$, o conjunto de treinamento, e
• usar o conjunto $D''$ para verificar a hipótese $h$, o conjunto de teste.

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

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

onde

• as casas na diagonal indica o número de exemplos que foram acertados e
• as outras o número dos que foram confundidos.

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 $D$ em, no mínimo, três subconjuntos $D'$, $D''$ e $D'''$ e

• usa $D'$ como conjunto de teste (e $D'' \cup D'''$ como conjunto de treinamento),
• usa $D''$ como conjunto de teste (e $D' \cup D'''$ como conjunto de treinamento), e
• usa $D'''$ como conjunto de teste (e $D' \cup D''$ como conjunto de treinamento).

O nosso método

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

• de $H$,
• da medida de erro $\mathrm{E}$, e
• do algoritmo $A$

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

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 quais problemas o algoritmo consegue provavelmente acertar, e
• caso consiga, quantos exemplos precisa para isto.

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 $X$ à amostra finita $D$. Por exemplo, no Perceptron, restringimos aos valores das retas sobre $N$ pontos no plano. Vimos que já para $N = 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 = 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) $d$ das hipóteses é finita. Neste caso, podemos, para qualquer erro $\epsilon$ e para qualquer confiança $\delta$, por exemplo, $\epsilon = 0,1$ e $\delta = 0,1$, garantir que a hipótese escolhida pelo algoritmo a partir de uma amostra com $N$ exemplos faça um erro $< \epsilon = 0,1$ com uma probabilidade de $1 - \delta = 90 \%$.

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

3.1 Defeito

Dada a amostra $D = \{ x_1, ..., x_N \}$ com os seus valores $\{ y_1, ..., y_N \}$ e uma hipótese $h$, podemos calcular o seu erro específico, $$\mathrm{E}_D(h);$$ contudo, como $y$ é desconhecida, não o seu erro geral, $$\mathrm{E}_X(h),$$ cuja minimização é o alvo final. Para aproximá-lo, introduzamos o defeito $$\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 $D$: Para limitar $\mathrm{E}_X(h)$, precisamos, pela desigualdade triangular $$| \mathrm{E}_X(h) | \leq | \Delta_D h | + | \mathrm{E}_D(h) |,$$ de limitar $$| \Delta_D h | \quad \text{ e } \quad | \mathrm{E}_D(h) |.$$ Isto é, a viabilidade de aprender corresponde à viabilidade de minimizar

• o defeito $\Delta_D h$, e
• o erro específico $\mathrm{E}_D(h)$.

Para simplificar a exposição, seja daqui em diante $Y = \{\pm 1\}$, problema de classificação binária, e o erro $$\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 \colon X \to Y$, um limiar de erro $\epsilon > 0$ e um número de exemplos $N$, a desigualdade de Hoeffding estima a probabilidade do defeito ser $> \epsilon$ por $$P( | \Delta_D h | > \epsilon ) \leq 2 \mathrm{e}^{-2 \epsilon^2 N}.$$

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

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

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

• no evento da desigualdade de Hoeffding, a função é fixa, independente de $D$, enquanto
• no evento $(\dagger)$, a função varia com $D$!

Em geral, sem conhecimento do algoritmo que escolhe $h(D)$ a partir de $D$, só podemos limitar a probabilidade de $|\Delta_D h(D)| > \epsilon$ para $h(D)$ pela probabilidade que $|\Delta_D h| > \epsilon$ para uma $h$ em $H$. Isto é, que exista $h$ em $H$ com $|\Delta_D h| > \epsilon$; em fórmulas $$\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 = \{ h_1, ..., h_M \}$ é finito, então $$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 $h_1$, …, $h_M$ não variam com $D$, aplicamos a cada um dos $M$ parcelas a mesma desigualdade de Hoeffding, obtendo na soma o fator $M$.

Observação. Quanto maior $\# H = M$, tanto mais facilmente o algoritmo consegue diminuir $$P( | \mathrm{E}_D(h(D)) | > \epsilon ),$$ mas, também, tanto maior o limite da desigualdade $$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 \colon X \to Y$ e uma amostra $D$, é a diferença, o defeito $$\Delta_D h = \mathrm{E}_D(h) - \mathrm{E}_X(h),$$ a diferença entre

• o erro específico $\mathrm{E}_D(h)$ (sobre a amostra $D$) e
• o erro geral $\mathrm{E}_X(h)$ (sobre $X$).

quantifica quão bem o algoritmo aprende, acerta as conclusões gerais a partir de exemplos. Logo, num problema de aprendizado, dada $\epsilon > 0$, queremos limitar a probabilidade $$P( |\Delta_D h(D)| > \epsilon )$$ para a hipótese $h(D)$ em $H$ que é escolhida a partir de $D$ pelo algoritmo $A$; em particular, que vária com $D$. Como $A$ é desconhecido, logo $h(D)$, precisamos de limitar o supremo de todas as hipóteses $$P( |\Delta_D h(D)| > \epsilon ) \leq P( \sup \{ |\Delta_D(h)| : h \text{ em } H \} > \epsilon ).$$ Observamos $$\{ D : \sup \{|\Delta_D h| : h \text{ em } H \} > \epsilon\} = \bigcup_{h \text{ em } H} \{ D : |\Delta_D h| > \epsilon \}.$$ Por isso, se $H = \{ h_1, ..., h_M \}$ é finito, esta probabilidade pode ser estimada, da maneira mais grossa, por $$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 $H$ infinito, precisamos de uma maneira mais fina para estimar $P( |\Delta_D h(D)| > \epsilon )$ que toma em conta as grandes interseções dos conjuntos $\{ D : |\Delta_D h| > \epsilon \}$ para as $h$ em $H$ que diferem pouco.

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

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

Para limitar a probabilidade de um alto defeito,

• em vez do número total $\# H$ infinito de hipóteses, isto é, como funções sobre $X$ inteiro,
• estudamos o crescimento o número finito $\# H(D)$ das suas restrições a amostras $D$ (conjuntos finitos em $X$) crescentes.

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

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

• o seu valor máximo $m_H(N) = 2^N$ é frequentemente só alcançado para argumentos pequenos $N = 1,2,3, ...$, e
• quanto maior o número dos parâmetros que definem $H$, tanto mais argumentos (pequenos sucessivos) alcançam este máximo:

Exemplos:

• Seja $X = \mathbb{R} \times \mathbb{R}$ o plano e $H$ o conjunto das hipóteses do Perceptron. Observamos que $m_H(3) = 8$ é máximo, mas para $N = 4$ há para qualquer amostra $D$ uma dicotomia $D \to \{ \pm 1 \}$ que não pode ser gerada por $H$. Isto é, sempre podemos rotular quatro pontos no plano tal que eles não sejam linearmente separáveis. (Isto é, o Perceptron não termina.)

  

  Com efeito, $m_H(4) = 14$.

• Para $X = \mathbb{R}$ e $H := \{ h = \mathrm{signal}(\cdot - a) : a \in \mathbb{R} \}$, temos $m_H(N) = N + 1$: como $N$ pontos cindem a reta em $N + 1$ segmentos, há $N + 1$ escolhas para $a$ relativo a estes segmentos.

• Para $X = \mathbb{R}$ e $H := \{ h = I[a,b] : a,b \in \mathbb{R} \}$ com $I[a,b](x) = 1$ se $x$ está no intervalo $[a,b]$ (e $= -1$ caso contrário), temos $m_H(N) = N(N + 1)/2 + 1$: Como $N$ pontos cindem a reta em $N + 1$ regiões, há

  • a escolha que o intervalo está inteiramente incluso em um destes segmentos, e
  • mais $N + 1$ escolhas para a primeira extremidade e $N$ escolhas sobrantes para a segunda extremidade do intervalo, sem importar a ordem cronológica da escolha das extremidades; isto é, $N(N + 1)/2$ escolhas.

• Seja $X = \mathbb{R} \times \mathbb{R}$ o plano e $H$ a família dada pelos conjuntos convexos (isto é, para cada dois pontos no conjunto, também o segmento entre eles fica no conjunto) em $X$, isto é, $h(x) = 1$ se $x$ está no conjunto convexo que corresponde a $h$. Para mostrar que $m_H(N)$ é máximo, olhamos a amostra $D$ dada por $N$ pontos na borda de um círculo. Para qualquer dicotomia, conecta todos os pontos do tipo $+ 1$ por um polígono convexo (assim que todos os pontos do tipo $-1$ estão fora dele).