Esta é uma página de captura bilíngue salva pelo usuário em 2024-7-19 7:28 para https://app.immersivetranslate.com/pdf-pro/f56562de-fdf4-442b-815e-fd607b487fd1, fornecida com suporte bilíngue por Tradução Imersiva. Aprenda como salvar?
2024_07_18_0bfac7405f8d828c8755g
 "Uma obra-prima."
  • Geoffrey Hinton

 Porque é que as máquinas aprendem


"Alguns livros sobre o desenvolvimento das redes neuronais descrevem a matemática subjacente, enquanto outros descrevem a história social. Este livro apresenta a matemática no contexto da história social. É uma obra-prima. O autor é muito bom a explicar a matemática de uma forma que a torna acessível a pessoas com apenas um conhecimento rudimentar da área, mas é também um excelente escritor que dá vida à história social."

-GEOFFREY HINTON, pioneiro da aprendizagem profunda, vencedor do Prémio Turing, antigo vice-presidente da Google e professor emérito da Universidade de Toronto

"Depois de apenas alguns minutos de leitura de Why Machines Learn, sentirá os seus próprios pesos sinápticos a serem actualizados. No final, terá alcançado a sua própria versão de aprendizagem profunda - com um profundo prazer e conhecimento ao longo do caminho."

-STEVEN STROGATZ, autor de Infinito, bestseller do New York Times

Powers e professor de matemática na Universidade de Cornell

"Se estava à procura de uma forma de dar sentido à revolução da IA que está em curso, não procure mais. Com este livro abrangente e cativante, Anil Ananthaswamy contextualiza tudo, desde a origem da ideia e das equações que a regem até ao seu potencial para transformar a medicina, a física quântica e praticamente todos os aspectos da nossa vida. Uma leitura essencial para compreender tanto as possibilidades como as limitações da inteligência artificial."

-SABINE HOSSENFELDER, física e autora do bestseller do New York Times Física Existencial: O Guia de um Cientista para as Maiores Questões da Vida

"Porque é que as máquinas aprendem" é uma obra magistral que explica - de forma clara, acessível e divertida - a matemática subjacente às modernas


aprendizagem automática, juntamente com a história colorida do campo e dos seus investigadores pioneiros. Dado que a IA tem um impacto cada vez mais profundo no nosso mundo, este livro será um companheiro inestimável para todos os que pretendem ter uma compreensão profunda do que está por detrás destas máquinas muitas vezes inescrutáveis."

-MELANIE MITCHELL, autora de Inteligência Artificial e professora no Instituto de Santa Fé

"A IA generativa, com os seus fundamentos na aprendizagem automática, é um avanço tão fundamental como a criação do microprocessador, da Internet e do telemóvel. Mas quase ninguém, para além de um punhado de especialistas, compreende o seu funcionamento. Anil Ananthaswamy eliminou o mistério, dando-nos uma introdução suave, intuitiva e orientada para o ser humano à matemática que está na base deste desenvolvimento revolucionário."

-PETER E. HART, pioneiro da IA, empresário e coautor de Pattern Classification

"Why Machines Learn", de Anil Ananthaswamy, embarca numa viagem emocionante pelas origens da aprendizagem automática contemporânea. Com uma narrativa cativante, o livro mergulha nas vidas de figuras influentes que impulsionam a revolução da IA, explorando simultaneamente o intrincado formalismo matemático que lhe está subjacente. À medida que Anil traça as raízes e desvenda os mistérios da IA moderna, introduz suavemente a matemática subjacente, tornando o tema complexo acessível e entusiasmante para leitores de todas as origens."

-BJÖRN OMMER, professor na Universidade Ludwig Maximilian de Munique e líder da equipa original por detrás de Stable Diffusion


TAMBÉM POR ANIL ANANTHASWAMY Através de duas portas ao mesmo tempo O homem que não estava lá O limite da física Comunicações de dados usando design orientado a objetos e


Porque é que as máquinas aprendem A matemática elegante por detrás da IA moderna

Anil Ananthaswamy


Direitos de autor © 2024 por Anil Ananthaswamy

A Penguin Random House apoia os direitos de autor. Os direitos de autor estimulam a criatividade, encorajam vozes diversas, promovem a liberdade de expressão e criam uma cultura vibrante. Obrigado por comprar uma edição autorizada deste livro e por cumprir as leis de direitos autorais, não reproduzindo, digitalizando ou distribuindo qualquer parte dele, sob qualquer forma, sem permissão. Está a apoiar os escritores e a permitir que a Penguin Random

A Casa continuará a publicar livros para todos os leitores.

DUTTON e o cólofon D são marcas registadas da Penguin Random House LLC.

Partes do capítulo 12 e do epílogo apareceram na revista Quanta. A ilustração no capítulo 6 sobre PCA efectuada em dados EEG foi adaptada com a permissão de John Abel. As ilustrações do capítulo 12 sobre as curvas de viés-variância e de dupla descida foram adaptadas com a permissão de Mikhail Belkin. As ilustrações sobre as propriedades dos pinguins no capítulo 4 foram criadas por cortesia dos dados disponibilizados gratuitamente por Kristen Gorman, Allison Horst e Alison Hill. As ilustrações de neurónio biológico (esta pąge), campos de arroz (esta página) e o mapa de Manhattan (esta página) por Roshan Shakeel.

DADOS DE CATALOGAÇÃO EM PUBLICAÇÃO DA BIBLIOTECA DO CONGRESSO

Nomes: Ananthaswamy, Anil, autor.

Título: Porque é que as máquinas aprendem: a matemática elegante por detrás da IA moderna / Anil Ananthaswamy.

Descrição: New York : Dutton, [2024] | Inclui referências bibliográficas e índice.

Identificadores: LCCN 2024000738 | ISBN 9780593185742 (capa dura) | ISBN 9780593185759 (ebook)

Temas: LCSH: Aprendizagem de máquinas. | Aprendizagem profunda (aprendizagem de máquinas) | Inteligência artificial. |

Matemática. Classificação: LCC Q325.5 .A56 2024 | DDC 006.3/1-dc23/eng/20240326

Registo LC disponível em https://lccn.loc.gov/2024000738
Ebook ISBN 9780593185759

Desenho da capa por Dominique Jones

Ilustração de Jason Booher "segundo M.C. Escher"

CONCEPÇÃO DO LIVRO POR ASHLEY TUCKER, ADAPTADO PARA EBOOK POR MOLLY JESZKE

Embora o autor tenha feito todos os esforços para fornecer números de telefone, endereços de Internet e outras informações de contacto exactos no momento da publicação, nem o editor nem o autor assumem qualquer responsabilidade por erros ou por alterações que ocorram após a publicação. Além disso, a editora não


não tem qualquer controlo e não assume qualquer responsabilidade pelos sítios Web do autor ou de terceiros ou pelo seu conteúdo.
pid_prh_7.0_147548044_c0_r0

 ÍNDICE

 Dedicação

 Nota do autor
 Prólogo
 CAPÍTULO I

Procura desesperada de padrões
 CAPÍTULO 2

Aqui somos todos apenas números...
 CAPÍTULO 3

O fundo da taça
 CAPÍTULO 4
 Com toda a probabilidade.
 CAPÍTULO 5

Pássaros de uma pena
 CAPÍTULO 6

Há magia nessas matrizes
 CAPÍTULO 7

O grande truque da corda de amêndoa
 CAPÍTULO 8

Com uma pequena ajuda da Física

 CAPÍTULO 9


O homem que fez recuar a aprendizagem profunda_(Nem por isso.).
 CAPÍTULO 10

O algoritmo que pôs fim a um mito persistente
 CAPÍTULO 11

Os olhos de uma máquina
 CAPÍTULO 12
 Terra Incógnita

 Epílogo

 Agradecimentos
 Notas
 Índice
 Sobre o autor

aos professores de todo o mundo, cantados e não cantados

Façamos o que fizermos, temos de fazer os nossos vectores de vida.

Linhas com força e direção.

-LIAM NEESON COMO AGENTE DO FBI MARK FELT NO FILME DE 2017

FILME COM O MESMO NOME

O autor reconhece com gratidão o apoio da Alfred P. Sloan Foundation na investigação e redação deste livro.

 Prólogo


Nesta página da edição de 8 de julho de 1958 do The New York Times estava enterrada uma história bastante extraordinária. A manchete dizia: "Novo dispositivo da Marinha aprende fazendo: Psicólogo mostra embrião de computador concebido para ler e tornar-se mais sábio". O parágrafo de abertura aumentava a parada: "A Marinha revelou hoje o embrião de um computador eletrónico que espera que seja capaz de andar, falar, ver, escrever, reproduzir-se e ter consciência da sua existência."

Em retrospetiva, a hipérbole é óbvia e embaraçosa. Mas a culpa não foi inteiramente do The New York Times. Parte do discurso exagerado também veio de Frank Rosenblatt, um psicólogo da Universidade de Cornell e engenheiro de projectos. Rosenblatt, com financiamento do Gabinete de Investigação Naval dos EUA, inventou o perceptron, cuja versão foi apresentada numa conferência de imprensa no dia anterior à publicação do artigo do New York Times sobre o mesmo. De acordo com Rosenblatt, o perceptron seria o "primeiro dispositivo a pensar como o cérebro humano" e essas máquinas poderiam até ser enviadas para outros planetas como "exploradores espaciais mecânicos".

Nada disto aconteceu. O perceptron nunca correspondeu às expectativas. No entanto, o trabalho de Rosenblatt foi seminal. Hoje em dia, quase todos os professores de inteligência artificial (IA) recordam o perceptron. E isso justifica-se. Este momento da história - a chegada de grandes modelos de linguagem (LLMs) como o ChatGPT e os seus semelhantes e a nossa reação a ele - que alguns compararam ao que deve ter sido a sensação nos anos 1910 e 20, quando os físicos foram confrontados com a loucura da mecânica quântica, tem as suas raízes na investigação iniciada por Rosenblatt. Há uma frase no artigo do New York Times que apenas dá uma ideia da revolução que o perceptron provocou


movimento: "O Dr. Rosenblatt disse que só poderia explicar porque é que a máquina aprendeu em termos altamente técnicos" (itálico meu). A história, no entanto, não tinha nenhum dos pormenores "altamente técnicos".

Este livro fá-lo. Aborda os pormenores técnicos. Explica a matemática e os algoritmos elegantes que, durante décadas, estimularam e entusiasmaram os investigadores da "aprendizagem automática", um tipo de IA que envolve a construção de máquinas capazes de aprender a discernir padrões nos dados sem serem explicitamente programadas para o fazer. As máquinas treinadas podem então detetar padrões semelhantes em dados novos e nunca antes vistos, tornando possíveis aplicações que vão desde o reconhecimento de fotografias de gatos e cães até à criação, potencialmente, de carros autónomos e outras tecnologias. As máquinas podem aprender graças à extraordinária confluência da matemática e da informática, com mais do que uma pitada de física e neurociência adicionadas à mistura.

A aprendizagem automática (ML) é um vasto domínio povoado por algoritmos que utilizam matemática relativamente simples que remonta a séculos, matemática que se aprende no liceu ou no início da faculdade. Há, evidentemente, a álgebra elementar. Outra pedra angular extremamente importante da aprendizagem automática é o cálculo, co-inventado por nada menos que um polímata, Isaac Newton. O campo também se baseia fortemente no trabalho de Thomas Bayes, o estatístico e ministro inglês do século XVIII que nos deu o teorema de Bayes com o mesmo nome, uma contribuição fundamental para o campo da probabilidade e da estatística. O trabalho do matemático alemão Carl Friedrich Gauss sobre a distribuição gaussiana (e a curva em forma de sino) também permeia a aprendizagem automática. Depois, há a álgebra linear, que constitui a espinha dorsal da aprendizagem automática. A exposição mais antiga deste ramo da matemática aparece num texto chinês com dois mil anos, Nine Chapters on the Mathematical Art (Nove capítulos sobre a arte matemática). A versão moderna da álgebra linear tem as suas raízes no trabalho de muitos matemáticos, mas principalmente de Gauss, Gottfried Wilhelm Leibniz, Wilhelm Jordan, Gabriel Cramer, Hermann Günther Grassmann, James Joseph Sylvester e Arthur Cayley.

Em meados da década de 1850, já existia alguma da matemática básica que viria a ser necessária para a construção de máquinas de aprendizagem, mesmo quando outros matemáticos continuavam a desenvolver matemática mais relevante e a criar e a desenvolver


no domínio das ciências da computação. No entanto, poucos poderiam ter sonhado que esse trabalho matemático inicial seria a base para os espantosos desenvolvimentos da IA ao longo do último meio século, em especial na última década, alguns dos quais podem legitimamente permitir-nos vislumbrar uma aparência do tipo de futuro que Rosenblatt estava a prever de forma demasiado otimista na década de 1950.

Este livro conta a história desta viagem, desde o perceptron de Rosenblatt até às redes neuronais profundas dos dias de hoje, redes elaboradas de unidades computacionais chamadas neurónios artificiais, através da lente das ideias matemáticas fundamentais que sustentam o campo da aprendizagem automática. A matemática é introduzida com suavidade e depois, muito lentamente, aumenta a dificuldade, à medida que passamos das ideias relativamente simples dos anos 50 para a matemática e os algoritmos um pouco mais complexos que alimentam os actuais sistemas de aprendizagem automática.

Por isso, vamos abraçar sem pudor equações e conceitos de, pelo menos, quatro grandes áreas da matemática - álgebra linear, cálculo, probabilidade e estatística e teoria da otimização - para adquirir os conhecimentos teóricos e conceptuais mínimos necessários para apreciar o incrível poder que estamos a conceder às máquinas. Só quando compreendermos a inevitabilidade da aprendizagem das máquinas é que estaremos preparados para enfrentar um futuro em que a IA será omnipresente, para o bem e para o mal.

Conhecer a fundo a matemática da aprendizagem automática é crucial para compreendermos não só o poder da tecnologia, mas também as suas limitações. Os sistemas de aprendizagem automática já tomam decisões que alteram a nossa vida: aprovam pedidos de cartões de crédito e empréstimos hipotecários, determinam se um tumor é cancerígeno, prevêem o prognóstico de uma pessoa em declínio cognitivo (será que vai ter Alzheimer?) e decidem se concedem fiança a alguém. A aprendizagem automática também penetrou na ciência: Está a influenciar a química, a biologia, a física e tudo o que está entre elas. Está a ser utilizada no estudo de genomas, planetas extra-solares, as complexidades dos sistemas quânticos e muito mais. E, no momento em que escrevemos este artigo, o mundo da IA está a fervilhar com o advento de grandes modelos de linguagem, como o ChatGPT. A bola só agora começou a rolar.

Não podemos deixar as decisões sobre a forma como a IA será construída e implantada apenas aos seus praticantes. Se quisermos regulamentar eficazmente esta tecnologia extremamente


Para que a aprendizagem automática seja uma tecnologia útil, mas perturbadora e potencialmente ameaçadora, é necessário que outra camada da sociedade - educadores, políticos, decisores políticos, divulgadores científicos ou mesmo consumidores interessados em IA - se familiarize com os princípios básicos da matemática da aprendizagem automática.

No seu livro Is Math Real?, a matemática Eugenia Cheng escreve sobre o processo gradual de aprendizagem da matemática: "Pode parecer que estamos a dar passos muito pequenos e não chegamos a lado nenhum, até que de repente olhamos para trás e descobrimos que escalámos uma montanha gigante. Todas estas coisas podem ser desconcertantes, mas aceitar um pouco de desconforto intelectual (ou, por vezes, muito desconforto) é uma parte importante do progresso em matemática."

Felizmente, o "desconforto intelectual" que nos espera é eminentemente suportável e mais do que atenuado pela recompensa intelectual, porque subjacente ao ML moderno está uma matemática relativamente simples e elegante - uma noção que é melhor ilustrada com uma anedota sobre Ilya Sutskever. Atualmente, Sutskever é mais conhecido como o cofundador da OpenAI, a empresa por detrás do ChatGPT. Há mais de uma década, quando era um jovem estudante universitário à procura de um conselheiro académico na Universidade de Toronto, Sutskever bateu à porta de Geoffrey Hinton. Hinton já era um nome bem conhecido no domínio da "aprendizagem profunda", uma forma de aprendizagem automática, e Sutskever queria trabalhar com ele. Hinton deu a Sutskever alguns artigos para ler, que ele devorou. Lembra-se de ter ficado perplexo com a simplicidade da matemática, em comparação com a matemática e a física do seu curso regular de licenciatura. Conseguia ler estes documentos sobre aprendizagem profunda e compreender conceitos poderosos. "Como é possível que seja tão simples... tão simples que se pode explicar a alunos do ensino secundário sem grande esforço?", disse-me. "Acho que isso é de facto milagroso. Para mim, isso também é uma indicação de que estamos provavelmente no caminho certo. [Não pode ser uma coincidência que conceitos tão simples cheguem tão longe".

Claro que Sutskever já tinha conhecimentos matemáticos sofisticados, por isso o que lhe parecia simples pode não o ser para a maioria de nós, incluindo eu. Mas vejamos.

Este livro tem como objetivo comunicar a simplicidade concetual subjacente ao ML e à aprendizagem profunda. Isto não quer dizer que tudo aquilo a que estamos a assistir


na IA atual - em particular, o comportamento das redes neuronais profundas e dos grandes modelos de linguagem - é passível de ser analisado usando matemática simples. De facto, o desfecho deste livro leva-nos a um lugar que alguns poderão considerar desconcertante, embora outros o achem estimulante: Estas redes e IAs parecem desrespeitar algumas das ideias fundamentais que, durante décadas, sustentaram a aprendizagem automática. É como se a evidência empírica tivesse quebrado a espinha do camelo teórico da mesma forma que as observações experimentais do mundo material no início do século XX quebraram a física clássica; precisamos de algo novo para dar sentido ao admirável mundo novo que nos espera.

Ao fazer a pesquisa para este livro, observei um padrão na minha aprendizagem que me fez lembrar a forma como as redes neurais artificiais modernas aprendem: Com cada passagem que o algoritmo faz pelos dados, aprende mais sobre os padrões que existem nesses dados. Uma passagem pode não ser suficiente; nem dez; nem cem. Por vezes, as redes neuronais aprendem ao longo de dezenas de milhares de iterações através dos dados. Foi, de facto, desta forma que aprendi o assunto para poder escrever sobre ele. Cada passagem por um canto desta vasta base de conhecimento fez com que alguns neurónios do meu cérebro fizessem ligações, literal e metaforicamente. Coisas que não faziam sentido à primeira ou à segunda vez, acabaram por fazer em passagens posteriores.

Utilizei esta técnica para ajudar os leitores a estabelecer ligações semelhantes: Dei por mim a repetir ideias e conceitos ao longo da escrita deste livro, por vezes utilizando a mesma fraseologia ou, por vezes, uma abordagem diferente do mesmo conceito. Estas repetições e reformulações são intencionais: São uma forma de a maior parte de nós, que não somos matemáticos ou praticantes de ML, conseguirmos compreender um assunto paradoxalmente simples mas complexo. Uma vez exposta uma ideia, os nossos cérebros podem ver padrões e estabelecer ligações quando se deparam com essa ideia noutros locais, dando-lhe mais sentido do que seria possível à primeira vista.

Espero que os vossos neurónios gostem tanto deste processo como os meus gostaram.

 CAPÍTULO 1


Procura desesperada de padrões


Quando era criança, o cientista austríaco Konrad Lorenz, encantado com os contos de um livro chamado As Maravilhosas Aventuras de Nils - a história das aventuras de um rapaz com gansos selvagens escrita pela romancista sueca e vencedora do Prémio Nobel da Literatura, Selma Lagerlöf - "ansiava por se tornar um ganso selvagem". Incapaz de satisfazer a sua fantasia, o jovem Lorenz contentou-se em tomar conta de um patinho de um dia que o seu vizinho lhe deu. Para alegria do rapaz, o patinho começou a segui-lo por todo o lado: O patinho tinha-lhe ficado marcado. O termo "impressão" refere-se à capacidade de muitos animais, incluindo patos e gansos bebés (gansinhos), criarem laços com a primeira coisa móvel que vêem ao nascer. Lorenz viria a tornar-se etólogo e seria pioneiro em estudos no domínio do comportamento animal, nomeadamente no que respeita ao "imprinting". (Conseguiu que os patinhos lhe dessem as suas impressões; seguiam-no enquanto ele andava, corria, nadava e até remava numa canoa). Ganhou o Prémio Nobel da Fisiologia ou Medicina em 1973, juntamente com os colegas etólogos Karl von Frisch e Nikolaas Tinbergen. Os três foram distinguidos "pelas suas descobertas sobre a organização e a obtenção de padrões de comportamento individual e social".

Padrões. Enquanto os etólogos os discerniam no comportamento dos animais, estes detectavam os seus próprios padrões. Os patinhos recém-nascidos devem ter a capacidade de distinguir as propriedades das coisas que vêem mover-se à sua volta. Acontece que os patinhos conseguem identificar não só a primeira criatura viva que vêem a mover-se, mas também coisas inanimadas. Os patinhos-reais, por exemplo, conseguem fixar as suas impressões num par de objectos em movimento que sejam semelhantes em forma ou cor. Especificamente, eles imprimem o conceito relacional incorporado nos objectos. Assim, se à nascença os patinhos


Se os patinhos virem dois objectos vermelhos em movimento, seguirão mais tarde dois objectos da mesma cor (mesmo que estes últimos sejam azuis e não vermelhos), mas não dois objectos de cores diferentes. Neste caso, os patinhos imprimem a ideia de semelhança. Também demonstram a capacidade de discernir a diferença. Se os primeiros objectos em movimento que os patinhos vêem são, por exemplo, um cubo e um prisma retangular, reconhecerão que os objectos têm formas diferentes e seguirão mais tarde dois objectos que têm formas diferentes (uma pirâmide e um cone, por exemplo), mas ignorarão dois objectos que têm a mesma forma.

Pondera isto por um momento. Os patinhos recém-nascidos, com a mais breve exposição a estímulos sensoriais, detectam padrões no que vêem, formam noções abstractas de semelhança/dissemelhança e depois reconhecem essas abstracções em estímulos que vêem mais tarde e agem com base nelas. Os investigadores de inteligência artificial dariam um braço e uma perna para saber como é que os patinhos conseguem fazer isto.

Embora a IA atual esteja longe de ser capaz de realizar essas tarefas com a facilidade e eficiência dos patinhos, tem algo em comum com os patinhos: a capacidade de identificar e aprender sobre padrões nos dados. Quando Frank Rosenblatt inventou o perceptron no final dos anos 50, uma das razões pelas quais causou tanto impacto foi o facto de ser o primeiro algoritmo formidável "inspirado no cérebro" que podia aprender sobre padrões nos dados simplesmente examinando-os. Mais importante ainda, dados certos pressupostos sobre os dados, os investigadores provaram que o perceptron de Rosenblatt encontrará sempre o padrão escondido nos dados num período de tempo finito; ou, dito de outra forma, o perceptron convergirá para uma solução sem falhas. Estas certezas em computação são como ouro em pó. Não admira que o algoritmo de aprendizagem perceptron tenha criado tanto alarido.

Mas o que é que estes termos significam? O que são "padrões" nos dados? O que é que "aprender sobre estes padrões" implica? Comecemos por examinar esta tabela:

Cada linha da tabela é um tripleto de valores para as variáveis , e . Há um padrão simples oculto nesses dados: Em cada linha, o valor de está relacionado com os valores correspondentes de e . Veja se consegue identificá-lo antes de continuar a ler.

Neste caso, com um lápis, papel e um pouco de esforço é possível descobrir que é igual a mais duas vezes .

Uma pequena observação sobre a notação: Vamos dispensar o sinal de multiplicação (" ") entre duas variáveis ou entre uma constante e uma variável. Por exemplo, vamos escrever

Idealmente, deveríamos escrever como e como , com as variáveis subscritas. Mas vamos dispensar os subscritos também, a menos que seja absolutamente necessário usá-los. (Os puristas vão ficar com vergonha, mas este método ajuda a manter o nosso texto menos desordenado e fácil de ver; quando encontrarmos subscritos, leia como "x sub-i.") Portanto, tenha isto em mente: Se houver um símbolo como " " seguido de um dígito como "2", dando-nos , considere o símbolo inteiro como significando uma coisa. Se um símbolo (digamos, ou ) é precedido por um número (digamos, 9), ou por outro símbolo (digamos, w1), então o número e o símbolo, ou os dois símbolos, estão a ser multiplicados. Assim:

Voltando à nossa equação , de uma forma mais geral, podemos escrevê-la como:

Para sermos claros, encontrámos uma das muitas relações possíveis entre e e . Podem existir outras. E de facto, para este exemplo, existem, mas não precisamos de nos preocupar com elas para os nossos propósitos aqui. Encontrar padrões não é nem de longe tão simples como este exemplo sugere, mas serve para começarmos.

Identificámos o que se chama uma relação linear entre , por um lado, e e , por outro. ("Linear" significa que depende apenas de e , e não de ou elevado a alguma potência, ou de qualquer produto de e .) Além disso, estou a usar as palavras "equação" e "relação" indistintamente aqui.

A relação entre , e é definida pelas constantes e . Essas constantes são chamadas de coeficientes, ou pesos, da equação linear que liga a e . Neste caso simples, assumindo que essa relação linear existe, descobrimos os valores de e depois de inspecionar os dados. Mas muitas vezes, a relação entre e não é tão simples, especialmente quando se estende a mais valores no lado direito da equação.
 Por exemplo, considere:

Ou, mais geralmente, para um conjunto de pesos, e utilizando notação matemática formal:

A expressão à direita, utilizando a notação sigma, é uma forma abreviada de somar todos os wixi, em que assume valores de 1 a .

No caso de 9 entradas, seria difícil extrair os valores de a apenas inspeccionando visualmente os dados e fazendo alguma aritmética mental. É aí que entra a aprendizagem. Se existe uma forma de descobrir algoritmicamente os pesos, então o algoritmo está a "aprender" os pesos. Mas qual é o objetivo de fazer isso?

Bem, uma vez que você aprendeu os pesos - digamos, e em nosso exemplo simples e de brinquedo - então, dado algum valor de e que não estava em nosso conjunto de dados inicial, podemos calcular o valor de . Digamos, e . Insira esses valores na equação e você obterá o valor de .

O que é que tudo isto tem a ver com a vida real? Tomemos um problema muito simples, prático e, segundo alguns, absolutamente aborrecido. Digamos que representa o número de quartos de uma casa, representa a metragem quadrada total e representa o preço da casa. Vamos supor que existe uma relação linear entre e . Então, ao aprender os pesos da equação linear a partir de alguns dados existentes sobre casas e seus preços, construímos essencialmente um modelo muito simples para prever o preço de uma casa, dado o número de quartos e a metragem quadrada.

O exemplo acima - um pequeníssimo passo de bebé, na verdade - é o início da aprendizagem automática. O que acabámos de fazer é uma forma simplista de algo chamado aprendizagem supervisionada. Foram-nos dadas amostras de dados que tinham escondida alguma correlação entre um conjunto de entradas e um conjunto de saídas. Diz-se que esses dados são anotados ou rotulados; são também designados por dados de treino. Cada entrada ( ) tem uma etiqueta associada. Assim, na nossa tabela numérica anterior, o par de números é rotulado com , o par com 5 ,


e assim por diante. Descobrimos a correlação. Uma vez aprendida, podemos utilizá-la para fazer previsões sobre novas entradas que não faziam parte dos dados de treino.

Além disso, fizemos um tipo muito particular de resolução de problemas chamado regressão, em que, dadas algumas variáveis independentes ( ), construímos um modelo (ou equação) para prever o valor de uma variável dependente ( ). Há muitos outros tipos de modelos que poderíamos ter construído, e falaremos deles na devida altura.

Neste caso, a correlação, ou padrão, era tão simples que só precisávamos de uma pequena quantidade de dados rotulados. Mas o ML moderno requer ordens de magnitude superiores - e a disponibilidade de tais dados tem sido um dos factores que alimentam a revolução da IA. (Os patinhos, por seu lado, provavelmente entregam-se a uma forma mais sofisticada de aprendizagem. Nenhum pato pai fica sentado a rotular os dados para os seus patinhos e, no entanto, os bebés aprendem. Como é que eles o fazem? Alerta de spoiler: não sabemos, mas talvez ao compreendermos porque é que as máquinas aprendem, possamos um dia compreender totalmente como é que os patinhos e, na verdade, os humanos aprendem).

Pode parecer implausível, mas este primeiro passo que demos utilizando um exemplo ridiculamente simples de aprendizagem supervisionada coloca-nos no caminho da compreensão das redes neuronais profundas modernas - um passo de cada vez, claro (com pequenas, suaves e, ocasionalmente, talvez não tão suaves doses de vectores, matrizes, álgebra linear, cálculo, probabilidade e estatística e teoria da otimização servidas, conforme necessário, ao longo do caminho).

O perceptron de Rosenblatt, que encontrámos brevemente no prólogo, foi para a sua época um exemplo espantoso de um desses algoritmos de aprendizagem. E como foi modelado de acordo com a forma como os neurocientistas pensavam que os neurónios humanos funcionavam, veio imbuído de mística e da promessa de que, um dia, os perceptrões iriam de facto cumprir a promessa da IA.


O PRIMEIRO NEURÓNIO ARTIFICIAL


As raízes do perceptron estão num artigo de 1943, escrito por uma combinação improvável de um neurocientista de espírito filosófico com quarenta e poucos anos e um adolescente sem-abrigo. Warren McCulloch era um neurofisiologista americano formado em


filosofia, psicologia e medicina. Durante a década de 1930, trabalhou em neuroanatomia, criando mapas da conetividade de partes do cérebro de macacos. Ao mesmo tempo, ficou obcecado com a "lógica do cérebro". Nessa altura, o trabalho de matemáticos e filósofos como Alan Turing, Alfred North Whitehead e Bertrand Russell estava a sugerir uma ligação profunda entre a computação e a lógica. A afirmação "Se P é verdadeira E Q é verdadeira, então S é verdadeira" é um exemplo de uma proposição lógica. A afirmação era que toda a computação podia ser reduzida a essa lógica. Dada esta forma de pensar sobre a computação, a questão que incomodava McCulloch era a seguinte: Se o cérebro é um dispositivo computacional, como muitos pensam que é, como é que implementa essa lógica?

Com estas questões em mente, McCulloch mudou-se em 1941 da Universidade de Yale para a Universidade de Illinois, onde conheceu um adolescente prodigiosamente talentoso chamado Walter Pitts. O jovem, já um lógico de sucesso ("um protegido do eminente lógico matemático Rudolf Carnap"), estava a frequentar seminários dirigidos pelo físico matemático ucraniano Nicolas Rashevsky em Chicago. Pitts, no entanto, era um "adolescente confuso, essencialmente um fugitivo de uma família que não conseguia apreciar o seu génio". McCulloch e a sua mulher, Rook, deram uma casa a Walter. "Seguiram-se serões intermináveis sentados à volta da mesa da cozinha dos McCulloch a tentar perceber como funcionava o cérebro, com a filha dos McCulloch, Taffy, a fazer pequenos desenhos", escreveu o cientista informático Michael Arbib. Os desenhos de Taffy viriam mais tarde a ilustrar o artigo de McCulloch e Pitts de 1943, "A Logical Calculus of the Ideas Immanent in Nervous Activity".

Nesse trabalho, McCulloch e Pitts propuseram um modelo simples de um neurónio biológico. Primeiro, eis uma ilustração de um neurónio biológico genérico:

O corpo celular do neurónio recebe inputs através das suas projecções em forma de árvore, denominadas dendrites. O corpo celular efectua um cálculo com base nessas entradas. Depois, com base nos resultados desse cálculo, pode enviar um sinal elétrico ao longo de outra projeção mais longa, chamada axónio. Esse sinal viaja ao longo do axónio e atinge os seus terminais ramificados, onde é comunicado aos dendritos dos neurónios vizinhos. E assim por diante. Os neurónios interligados desta forma formam uma rede neuronal biológica.

McCulloch e Pitts transformaram isto num modelo computacional simples, um neurónio artificial. Mostraram como, utilizando um desses neurónios artificiais, ou neurode (para "neurónio" + "nó"), se podiam implementar certas operações lógicas booleanas básicas, como AND, OR, NOT, etc., que são os blocos de construção da computação digital. (Para algumas operações booleanas, como o OU exclusivo, ou XOR, é necessário mais do que um neurónio, mas falaremos disso mais tarde). O que se segue é uma imagem de um único neuróide. (Ignore o " " e o " " dentro do neurónio por agora; falaremos deles daqui a pouco).

Nesta versão simples do modelo de McCulloch-Pitts, e podem ser 0 ou 1 . Em notação formal, podemos dizer:

Isso deve ser lido como é um elemento do conjunto e é um elemento do conjunto e pode assumir apenas os valores 0 ou 1 e nada mais. A saída do neurodo é calculada somando primeiro as entradas e depois verificando se essa soma é maior ou igual a um certo limiar, theta . Em caso afirmativo, é igual a 1 ; em caso negativo, é igual a 0 .

Generalizando isso para uma seqüência arbitrária de entradas, , pode-se escrever a descrição matemática formal da neurode simples. Primeiro, definimos a função - lida como "g de x", onde é o conjunto de entradas ( - que soma as entradas. Então


definimos a função - mais uma vez, leia isso como " f de g de x "- que pega a soma e realiza o limiar para gerar a saída, : É zero se for menor que algum e 1 se for maior ou igual a .

Com um neurónio artificial como o descrito, podemos desenhar algumas das portas lógicas booleanas básicas (AND e OR, por exemplo). Numa porta lógica AND, a saída deve ser 1 se ambos e forem iguais a 1 ; caso contrário, a saída deve ser 0 . Neste caso, faz o truque. Agora, a saída será 1 somente quando e forem ambos 1 (somente então será maior ou igual a 2). Você pode brincar com o valor de para desenhar as outras portas lógicas. Por exemplo, numa porta OR, a saída deve ser 1 se ou for 1 ; caso contrário, a saída deve ser 0 . Qual deve ser o valor de ?

O modelo simples de CIM pode ser alargado. É possível aumentar o número de entradas. É possível permitir que as entradas sejam "inibitórias", o que significa que ou podem ser multiplicados por -1. Se uma das entradas para o neurodo for inibitória e o limiar for definido de forma adequada, o neurodo emitirá sempre um 0 , independentemente do valor de todas as outras entradas. Isto permite-lhe construir uma lógica mais complexa. O mesmo acontece com a interconexão de vários neurodos, de modo a que a saída de um neurodo sirva de entrada para outro.

Tudo isto era espantoso, mas limitado. O neurónio McCulloch-Pitts (MCP) é uma unidade de computação e é possível utilizar combinações dele para criar qualquer tipo de lógica booleana. Dado que toda a computação digital no seu


O mais básico é uma sequência de operações lógicas, pelo que é possível misturar e combinar neurónios MCP para efetuar qualquer cálculo. Esta era uma afirmação extraordinária para ser feita em 1943. As raízes matemáticas do artigo de McCulloch e Pitts eram evidentes. O artigo tinha apenas três referências - The Logical Syntax of Language, de Carnap; Foundations of Theoretical Logic, de David Hilbert e Wilhelm Ackermann; e Principia Mathematica, de Whitehead e Russell - e nenhuma delas tinha a ver com biologia. Não havia dúvidas quanto aos resultados rigorosos obtidos no artigo de McCulloch-Pitts. E, no entanto, o resultado era simplesmente uma máquina que podia computar, não aprender. Em particular, o valor de tinha de ser concebido à mão; o neurónio não podia examinar os dados e descobrir .

Não é de admirar que o perceptron de Rosenblatt tenha feito tanto sucesso. Podia aprender os seus pesos a partir dos dados. Os pesos codificavam algum conhecimento, ainda que mínimo, sobre os padrões nos dados e lembravam-se deles, por assim dizer.

 APRENDER COM OS ERROS


Os estudos de Rosenblatt deixavam muitas vezes os seus alunos boquiabertos. George Nagy, que veio para a Universidade de Cornell em Ithaca, Nova Iorque, em 1960, para fazer o seu doutoramento com Rosenblatt, recordou um passeio que os dois fizeram, durante o qual falaram sobre visão estéreo. Rosenblatt surpreendeu Nagy com o seu domínio do tema. "Era difícil não nos sentirmos ingénuos ao falar com ele em geral", disse Nagy, agora professor emérito no Rensselaer Polytechnic Institute em Troy, Nova Iorque; a evidente erudição de Rosenblatt era acentuada pela sua relativa juventude. (Ele era apenas dez anos mais velho que Nagy).

A juventude de Rosenblatt quase os meteu em sarilhos durante uma viagem de carro. Ele e Nagy tinham de ir de Ithaca a Chicago para uma conferência. Rosenblatt ainda não tinha escrito o trabalho que queria apresentar, por isso pediu a Nagy que conduzisse enquanto ele trabalhava. Nagy nunca tinha tido um carro e mal sabia conduzir, mas mesmo assim concordou. "Infelizmente, conduzi em várias faixas de rodagem ao mesmo tempo e um polícia mandou-nos parar", conta Nagy. Rosenblatt disse ao polícia que era professor e que tinha pedido ao seu aluno para conduzir. O


O polícia riu-se e disse: 'Tu não és um professor, és um estudante'". "Felizmente, Rosenblatt tinha documentos suficientes para convencer o polícia das suas credenciais e o polícia deixou-os ir embora. Rosenblatt conduziu o resto do caminho até Chicago, onde ficou acordado toda a noite a escrever o seu trabalho, que apresentou no dia seguinte. "Ele era capaz de fazer estas coisas", disse-me Nagy.

Na altura em que Nagy chegou a Cornell, Rosenblatt já tinha construído o Mark I Perceptron; vimos no prólogo que Rosenblatt o tinha feito em 1958, o que levou à cobertura do The New York Times. Nagy começou a trabalhar na máquina seguinte, chamada Tobermory (nome do gato falante criado por H. H. Munro, também conhecido por Saki), uma rede neuronal de hardware concebida para o reconhecimento da fala. Entretanto, o Mark I Perceptron e as ideias de Rosenblatt já tinham atraído muita atenção.

No verão de 1958, o editor da revista Research Trends do Laboratório Aeronáutico de Cornell dedicou uma edição inteira a Rosenblatt ("devido ao significado invulgar do artigo do Dr. Rosenblatt", segundo o editor). O artigo intitulava-se "The Design of an Intelligent Automaton: Introducing the Perceptron-A Machine that Senses, Recognizes, Remembers, and Responds Like the Human Mind". Rosenblatt acabaria por se arrepender de ter escolhido o termo "perceptron" para descrever o seu trabalho. "Tornou-se um dos grandes arrependimentos de Rosenblatt o facto de ter usado uma palavra que soa como uma máquina", disse-me Nagy. Com "perceptron", Rosenblatt referia-se realmente a uma classe de modelos do sistema nervoso para a perceção e a cognição.

A sua ênfase no cérebro não foi uma surpresa. Rosenblatt tinha estudado com James Gibson, um dos gigantes no domínio da perceção visual. Também admirava McCulloch e Pitts e Donald Hebb, um psicólogo canadiano que, em 1949, apresentou um modelo de aprendizagem dos neurónios biológicos - para ser claro, "aprendizagem" refere-se aqui à aprendizagem de padrões nos dados e não ao tipo de aprendizagem que normalmente associamos à cognição humana de alto nível. "Ele falava sempre muito bem deles", disse Nagy.

Embora McCulloch e Pitts tivessem desenvolvido modelos de neurónios, as redes destes neurónios artificiais não conseguiam aprender. No contexto dos neurónios biológicos, Hebb tinha proposto um mecanismo de aprendizagem que é


muitas vezes sucintamente, mas de forma algo errónea, como "os neurónios que disparam juntos ligam-se uns aos outros". Mais precisamente, de acordo com esta forma de pensar, os nossos cérebros aprendem porque as ligações entre os neurónios se reforçam quando a saída de um neurónio está consistentemente envolvida no disparo de outro, e enfraquecem quando isso não acontece. Este processo é designado por aprendizagem hebbiana. Foi Rosenblatt que pegou no trabalho destes pioneiros e o sintetizou numa nova ideia: neurónios artificiais que se reconfiguram à medida que aprendem, incorporando informação na força das suas ligações.

Como psicólogo, Rosenblatt não tinha acesso ao tipo de potência informática de que necessitava para simular as suas ideias em hardware ou software. Por isso, pediu emprestado tempo ao IBM 704 do Laboratório Aeronáutico de Cornell, um gigante de cinco toneladas, do tamanho de uma sala. A colaboração revelou-se frutuosa quando o trabalho de Rosenblatt chamou a atenção dos físicos, resultando em artigos em revistas de psicologia e da American Physical Society. Rosenblatt acabou por construir o Perceptron Mark I. O dispositivo tinha uma câmara que produzia uma imagem de 20x20 pixels. O Mark I, quando lhe eram mostradas estas imagens, conseguia reconhecer as letras do alfabeto. Mas dizer que o Mark I "reconhecia" caracteres não é o mesmo que dizer que o Mark I "reconhecia" caracteres, disse Nagy. Afinal, os sistemas de reconhecimento ótico de caracteres, que tinham as mesmas capacidades, estavam disponíveis comercialmente em meados da década de 1950. "A questão é que o Mark I aprendeu a reconhecer letras ao ser eletrocutado quando cometia um erro!" dizia Nagy nas suas palestras.

Mas o que é exatamente um perceptron e como aprende? Na sua forma mais simples, um perceptron é um neurónio McCulloch-Pitts aumentado, imbuído de um algoritmo de aprendizagem. O que se segue é um exemplo com duas entradas. Note-se que cada entrada está a ser multiplicada pelo seu peso correspondente. (Há também uma entrada extra, , cuja razão de ser ficará clara em breve).

O cálculo efectuado pelo perceptron é o seguinte:
 Outro:

De uma forma mais geral e em notação matemática:

A principal diferença em relação ao modelo MCP apresentado anteriormente é que as entradas do perceptron não têm de ser binárias (0 ou 1), mas podem assumir qualquer valor. Além disso, essas entradas são multiplicadas por seus pesos correspondentes, de modo que agora temos uma soma ponderada. A isso é adicionado um termo adicional , o viés. A saída, , é -1 ou +1 (em vez de 0 ou 1 , como no neurónio MCP). Crucialmente, ao contrário do neurônio MCP, o perceptron pode aprender o valor correto para os pesos e o viés para resolver algum problema.

Para entender como isso funciona, considere um perceptron que procura classificar alguém como obeso, , ou não-obeso, . As entradas são o peso corporal de uma pessoa, , e a altura, . Digamos que o conjunto de dados contém uma centena de entradas, com cada entrada compreendendo o peso corporal e a altura de uma pessoa e um rótulo dizendo se um médico acha que a pessoa é obesa de acordo com as diretrizes estabelecidas pelo National Heart, Lung, and Blood Institute. A tarefa de um perceptron é aprender os valores de e e o valor do termo de polarização , de modo a classificar corretamente cada pessoa no conjunto de dados como "obesa" ou "não obesa". Nota: Estamos a analisar o peso corporal e a altura de uma pessoa, ao mesmo tempo que falamos dos pesos do perceptron ( e w2); tenha em mente estes dois significados diferentes da palavra "peso" durante a leitura.

Uma vez que o perceptron tenha aprendido os valores corretos para e e o termo de viés, ele está pronto para fazer previsões. Dado o peso corporal e a altura de outra pessoa - essa pessoa não estava no conjunto de dados original, portanto não é uma simples questão de consultar uma tabela de entradas - o perceptron pode classificar a pessoa como obesa ou não obesa. Claro que este modelo tem subjacentes alguns pressupostos, muitos deles relacionados com distribuições de probabilidade, que abordaremos nos capítulos seguintes. Mas o perceptron faz uma suposição básica: Assume que existe uma divisão clara e linear entre as categorias de pessoas classificadas como obesas e as classificadas como não obesas.

No contexto deste exemplo simples, se se traçassem os pesos e as alturas das pessoas num gráfico xy, com os pesos no eixo e as alturas no eixo , de modo a que cada pessoa fosse um ponto no gráfico, então a hipótese da "divisão clara" afirma que existiria uma linha reta a separar os pontos que representam os obesos dos pontos que representam os não obesos. Se assim for, diz-se que o conjunto de dados é linearmente separável.

Aqui está uma visão gráfica do que acontece quando o perceptron aprende. Começamos com dois conjuntos de pontos de dados, um caracterizado por círculos pretos ( , obeso) e outro por triângulos pretos ( , não obeso). Cada ponto de dados é caracterizado por um par de valores ( ), em que é o peso corporal da pessoa em quilogramas, traçado ao longo do eixo , e é a altura em centímetros, traçada ao longo do eixo y.

O perceptron começa com seus pesos, e , e a polarização inicializada em zero. Os pesos e a polarização representam uma linha no plano xy. O perceptron tenta então encontrar uma linha de separação, definida por algum conjunto de valores para seus pesos e polarização, que tenta classificar os pontos. No início, classifica alguns pontos corretamente e outros incorretamente. Duas das tentativas incorrectas são mostradas como linhas cinzentas a tracejado. Neste caso, pode ver-se que, numa tentativa, todos os pontos se encontram de um lado da linha tracejada, pelo que os triângulos são classificados corretamente, mas os círculos não; e noutra tentativa, os círculos estão correctos, mas alguns dos triângulos estão errados. O perceptron aprende com os seus erros e ajusta os seus pesos e a sua tendência. Após inúmeras passagens pelos dados, o perceptron acaba por descobrir pelo menos um conjunto de valores correctos dos seus pesos e do seu termo de polarização. Encontra uma linha que delineia os clusters: Os círculos e os triângulos encontram-se em lados opostos. Isto é mostrado como uma linha preta sólida que separa o espaço de coordenadas em duas regiões (uma das quais está sombreada a cinzento). Os pesos aprendidos pelo perceptron ditam o declive da linha; o desvio determina a distância, ou offset, da linha em relação à origem.

Depois de o perceptron ter aprendido a correlação entre as características físicas de uma pessoa (peso corporal e altura) e o facto de essa pessoa ser obesa ou -1 , pode dar-lhe o peso corporal e a altura de


uma pessoa cujos dados não foram utilizados durante o treino, e o perceptron pode dizer se essa pessoa deve ser classificada como obesa. Claro que, agora, o perceptron está a fazer a sua melhor previsão, tendo aprendido os seus pesos e a sua tendência, mas a previsão pode estar errada. Consegues perceber porquê? Vê se consegues detetar o problema só de olhar para o gráfico. (Sugestão: Quantas linhas diferentes podes desenhar que consigam separar os círculos dos triângulos?) Como veremos, grande parte da aprendizagem automática resume-se a minimizar o erro de previsão.

O que é descrito acima é uma única unidade perceptron, ou um neurónio artificial. Parece simples, e pode perguntar-se o porquê de tanto alarido. Bem, imagine se o número de entradas para o perceptron fosse além de dois: ( , e assim por diante), com cada entrada ( ) recebendo seu próprio eixo. Já não é possível fazer uma simples aritmética mental e resolver o problema. Uma linha já não é suficiente para separar os dois grupos, que agora existem em dimensões muito maiores do que apenas duas. Por exemplo, quando há três pontos ( ), os dados são tridimensionais: é necessário um plano 2D para separar os pontos de dados. Em dimensões de quatro ou mais, é necessário um hiperplano (que não conseguimos visualizar com a nossa mente 3D). Em geral, este equivalente de dimensão superior de uma linha reta 1D ou de um plano 2D é designado por hiperplano.

Agora pense em 1958. Rosenblatt construiu o seu Perceptron Mark I com várias unidades deste tipo. Podia processar uma imagem de 20x20 pixels - num total de 400 pixels, correspondendo cada pixel a um valor de entrada . Assim, o Mark I recebeu como entrada uma longa fila de valores: . Um arranjo complexo de neurónios artificiais, tanto com pesos fixos e aleatórios como com pesos que podem ser aprendidos, transformou este vetor de 400 valores num sinal de saída que pode ser utilizado para discernir o padrão na imagem. (Esta é uma descrição demasiado simplificada. Parte da computação era suficientemente complexa para necessitar de um IBM 704. Teremos um vislumbre dos detalhes da arquitetura no capítulo 10). O Mark I podia aprender a classificar as letras do alfabeto codificadas nesses valores de pixéis. Toda a lógica que acabámos de descrever, aumentada para lidar com 400 entradas, era hardware incorporado. A máquina, depois de ter aprendido (veremos como no próximo capítulo), continha conhecimento nas forças


(pesos) das suas ligações. Não é de admirar que toda a gente dê largas à sua imaginação.

Mas se examinarmos de perto o que o perceptron aprende, as suas limitações - em retrospetiva, claro - tornam-se óbvias. O algoritmo está a ajudar o perceptron a aprender sobre as correlações entre os valores de ( ) e o valor correspondente de , se tais correlações existirem nos dados. É certo que aprende as correlações sem que lhe seja explicitamente dito o que são, mas são correlações na mesma. Identificar correlações é a mesma coisa que pensar e raciocinar? Certamente que, se o Mark I distinguiu a letra "B" da letra "G", estava simplesmente a seguir os padrões e não atribuiu qualquer significado a essas letras que pudesse gerar mais raciocínio. Estas questões estão no centro do debate moderno sobre os limites das redes neuronais profundas, os espantosos descendentes dos perceptrões. Há um caminho que liga estes primeiros perceptrões à tecnologia dos grandes modelos de linguagem ou à IA que está a ser desenvolvida para, por exemplo, carros autónomos. Esse caminho não é reto; pelo contrário, é longo e sinuoso, com falsas curvas e becos sem saída. Mas é um caminho fascinante e intrigante, e estamos a percorrê-lo agora.

A construção do dispositivo perceptron foi um grande feito. Um feito ainda maior foi a prova matemática de que uma única camada de perceptrons encontrará sempre um hiperplano de separação linear, se os dados forem linearmente separáveis. Para compreendermos esta prova, teremos de experimentar pela primeira vez os vectores e a forma como estes constituem a espinha dorsal dos métodos utilizados para representar dados na aprendizagem automática. É a nossa primeira paragem matemática.

 CAPÍTULO 2


Aqui somos todos apenas números...


m menos de um mês antes da sua morte, em setembro de 1865, o matemático irlandês William Rowan Hamilton escreveu uma carta em quatro parágrafos ao seu filho. Nessa carta, Hamilton recordava, entre outras coisas, um passeio ao longo do Royal Canal em Dublin, na Irlanda. Estávamos a 16 de outubro de 1843. Hamilton estava a caminho de participar numa reunião da Academia Real Irlandesa. A sua mulher acompanhava-o. Quando o casal passou por baixo da ponte Brougham, Hamilton, que há mais de uma década se debatia com algumas questões matemáticas profundas, teve um lampejo de inspiração. "Um circuito elétrico pareceu fechar-se; e uma faísca brilhou... Não pude resistir ao impulso - por muito pouco filosófico que fosse - de cortar com uma faca numa pedra da Ponte Brougham, ao passarmos por ela, a fórmula fundamental com os símbolos ; nomeadamente, ."

Hamilton assinou a carta ao seu filho com estas palavras: "Com este quaternário de parágrafos [ênfase minha] encerro esta carta... Seu pai afetuoso, William Rowan Hamilton." O uso da palavra "quaternion" foi deliberado. Um quaternion é uma entidade matemática composta por quatro elementos com propriedades muito estranhas e especiais, que Hamilton descobriu naquele dia fatídico sob a ponte Brougham. A equação que ele gravou na pedra, representando a forma geral do quaternion, é um dos exemplos mais famosos de graffiti matemático; o original, que há muito foi desfigurado, foi substituído por uma placa oficial onde se lê:

Aqui, enquanto ele passava

em 16 de outubro de 1843
Sir William Rowan Hamilton

num lampejo de génio descobriu

a fórmula fundamental para

multiplicação de quaterniões

cortou-o numa pedra desta ponte.

Os quaterniões são entidades exóticas e não nos dizem respeito. Mas para criar a álgebra para manipular quaterniões, Hamilton desenvolveu algumas outras ideias matemáticas que se tornaram centrais para a aprendizagem automática. Em particular, introduziu os termos "escalar" e "vetor". Hoje em dia, é provável que a maioria de nós não tenha ouvido falar de Hamilton, mas estamos intuitivamente familiarizados com a noção de escalares e vectores, mesmo que não com as suas definições formais. Aqui está uma breve introdução.

Consideremos um homem que caminha 8 quilómetros. Dada esta afirmação, a única coisa que podemos dizer sobre o que o homem fez é denotada por um único número: a distância percorrida. Esta é uma quantidade escalar, um número autónomo. Agora, se nos dissessem que o homem andou oito quilómetros na direção nordeste, teríamos duas informações: a distância e a direção. Isto pode ser representado por um vetor. Um vetor tem, portanto, um comprimento (magnitude) e uma direção. No gráfico seguinte, o vetor é uma seta de magnitude 5 .

Se examinar atentamente o vetor, verá que tem duas componentes: uma ao longo do eixo x e outra ao longo do eixo y. É equivalente a dizer que o homem andou quatro milhas na direção leste e três milhas na direção norte. O vetor que representa a caminhada real é uma seta que vai de a , indicando a direção e a distância. A magnitude do vetor é simplesmente o comprimento da hipotenusa do triângulo retângulo formado pelo vetor e pelas suas componentes ao longo dos eixos x - e y. Assim, a magnitude do vetor, ou comprimento, é igual a .

Pensar em termos de vectores, sem utilizar formas formais de os representar e manipular, é anterior a Hamilton. Por exemplo, em finais de 1600, Isaac Newton já utilizava formas geométricas de pensar sobre entidades vectoriais como a aceleração e a força. A segunda lei do movimento de Newton diz que a aceleração sofrida por um objeto é proporcional à força que actua sobre ele e que a aceleração do objeto e a força têm a mesma direção. O primeiro corolário das Leis do Movimento de Newton, nos seus Principia, afirma: "Um corpo, por duas forças conjugadas, descreverá a diagonal de um paralelogramo, ao mesmo tempo que descreveria a diagonal de um paralelogramo".


lados, por essas forças separadas". Esta é uma afirmação sobre a utilização da geometria para adicionar dois vectores, embora Newton não tenha chamado vectores às quantidades.

Para compreender a adição vetorial, podemos voltar ao nosso homem que andou 8 km, representado por um vetor que vai de a . Depois de chegar ao destino, o homem vira-se mais para norte de tal forma que, no plano de coordenadas, atinge (6, 9): Ele andou efetivamente mais duas milhas na direção leste e mais seis milhas na direção norte. Isto é representado por um segundo vetor, uma seta desenhada de para . Este novo vetor tem uma componente de 2 e uma componente y de 6 . Qual é a distância total que o homem percorreu? E qual é a distância líquida no espaço de coordenadas xy, desde a origem até ao destino final? Este gráfico mostra-lhe as respostas a ambas:

A magnitude dos dois vectores individuais, ou caminhadas, é e . Assim, a distância total que o homem caminha é milhas.

O vetor resultante é uma seta desenhada desde a origem até ao destino final, que é (6, 9), e a sua magnitude é . A distância líquida no espaço de coordenadas xy é de 10,82 milhas.

Isto ajuda-nos agora a perceber o que Newton estava a dizer. Digamos que a aceleração causada por uma força que actua sobre um objeto é dada pelo vetor e que a aceleração causada por outra força sobre o mesmo objeto é dada pelo vetor . Ambas as forças actuam sobre o objeto ao mesmo tempo. Qual é a aceleração total do objeto? De acordo com o corolário de Newton, a interpretação geométrica envolve o desenho de um paralelogramo, como mostra a figura seguinte; a aceleração total é, então, dada pelo vetor diagonal :

Se a aceleração for em unidades de metros por segundo por segundo ), então a aceleração líquida é dada pela magnitude do vetor , que é igual a , na direção da seta.

Neste caso optei por adicionar os mesmos vectores que no exemplo do homem a andar, mas aqui os dois vectores representam a aceleração e não a distância, e ambos têm a sua cauda em . O que isto lhe diz é que o vetor é o mesmo vetor independentemente de a sua cauda estar em ou em , como no exemplo anterior. Uma propriedade importante dos vectores é que podemos mover a seta que representa um vetor no espaço de coordenadas, e se não alterarmos o comprimento da seta e a sua orientação, é o mesmo vetor. Porquê? Bem, porque não alterámos o seu comprimento nem a sua direção, as duas propriedades que definem o vetor.

Nada disto foi formalmente entendido como o início da análise vetorial quando Newton publicou os seus Principia em 1687. O seu contemporâneo Gottfried Wilhelm Leibniz (1646-1716), no entanto, tinha mais do que um indício desta nova forma de pensar. Em 1679, numa carta a outro luminoso contemporâneo, Christiaan Huygens, Leibniz escreveu: "Creio ter encontrado a forma... de podermos representar figuras e até máquinas e movimentos por caracteres, tal como a álgebra representa números ou grandezas." Leibniz nunca chegou a formalizar a sua intuição, mas a sua presciência - como veremos quando compreendermos a importância dos vectores para a aprendizagem automática - foi espantosa. Depois de Leibniz, uma série de outros matemáticos, incluindo Johann Carl Friedrich Gauss (1777-1855), desenvolveram métodos para a representação geométrica de certos tipos de números em duas dimensões, preparando o terreno para a descoberta dos quaterniões por Hamilton e a formalização da análise vetorial.


VECTORES PELOS NÚMEROS


A análise vetorial não tem de ser geométrica. Pode resumir-se à manipulação de números escritos num determinado formato. E, de facto, para a aprendizagem automática, é assim que temos de pensar nos vectores. Por exemplo, as acelerações causadas pelas duas forças no exemplo anterior são simplesmente matrizes de dois números cada, [4, 3] e [2, 6], respetivamente. Adicioná-las é o mesmo que adicionar os componentes individuais de cada vetor (empilhados verticalmente, como uma coluna). Não precisa de se preocupar com setas:

A subtração de vectores é semelhante.

O que é que acabou de acontecer? Porque é que a componente y do vetor resultante é negativa? Se estes números ainda representam aceleração, então a subtração significou que a segunda força estava a atuar contra a primeira força; ao longo do eixo x, a aceleração é apenas um pouco menor do que quando estávamos a adicionar os dois vectores, mas ainda é positiva; ao longo do eixo y, no entanto, a força está agora a atuar contra a direção inicial do movimento, resultando numa desaceleração.

É possível multiplicar um vetor por um escalar - basta multiplicar cada elemento do vetor pelo escalar.

Geometricamente, isso é o mesmo que esticar a seta (ou vetor) cinco vezes na mesma direção. A magnitude do vetor original é 5 . Ao esticá-lo 5 vezes, obtemos uma nova magnitude de 25 . Se calculássemos a magnitude do novo vetor utilizando as suas coordenadas aumentadas, obteríamos novamente:

Há ainda outra forma de representar vectores. Restringindo-nos a duas dimensões, pensemos num vetor de comprimento um, , ao longo do eixo , e num vetor de comprimento um, , ao longo do eixo . Note-se que e estão em minúsculas e em negrito; isto significa que são vectores. Então, pode ser pensado como uma seta que aponta de para e como uma seta que aponta de


a . Cada um tem uma magnitude de 1 e é também chamado de vetor unitário. Dado isto, os vectores e , em coordenadas cartesianas, podem ser escritos como e , respetivamente. Isto é o mesmo que dizer que o vetor tem 4 unidades no eixo e 3 unidades no eixo e que o vetor tem 2 unidades no eixo e 6 unidades no eixo . A utilização de e é uma forma abreviada de representar vectores. Também é importante salientar que um vetor unitário é simplesmente um vetor com uma magnitude de 1; não tem que estar ao longo dos eixos perpendiculares de um espaço de coordenadas.

Estas ideias também se aplicam a dimensões superiores, e já lá iremos. Por agora, conhecer a manipulação matemática de vectores de 2 D e os seus significados geométricos correspondentes ajudará muito a compreender o papel dos seus homólogos de dimensões superiores na aprendizagem automática.

 O PRODUTO ESCALAR


Outra operação importante com vectores é algo chamado produto escalar. Considere o vetor , chame-lhe a, e o vetor , chame-lhe . (Mais uma vez, as letras e em negrito e minúsculas significam que são vectores). Conceptualmente, o produto escalar a.b - leia-se "a ponto b" - é definido como a magnitude de a multiplicada pela projeção de sobre , em que a projeção pode ser considerada como a "sombra projectada" por um vetor sobre outro.

A magnitude de é denotada por ou . A projeção de sobre a é dada pela magnitude de , ou , multiplicada pelo cosseno do ângulo entre os dois vectores. Para os vectores que escolhemos, o ângulo entre eles é de 45 graus (ou radianos), como mostra o gráfico anterior. Assim:

Nota: o símbolo significa "o que implica que".

Agora vamos fazer alguns pequenos ajustes. Seja o vetor a dado por , o vetor por . O vetor a tem uma magnitude de 1 , logo é um "vetor unitário". Agora, se tomássemos o produto escalar a.b, obteríamos:

O produto escalar é igual à componente do vetor , ou à sombra projectada por sobre o eixo , a direção do vetor unitário. Isto dá-nos uma intuição geométrica crucial: Se um dos vectores envolvidos num produto escalar tem comprimento 1 , então o produto escalar é igual à projeção do outro vetor


sobre o vetor de comprimento unitário. No nosso caso especial, o vetor unitário está ao longo do eixo , pelo que a projeção do vetor sobre o eixo x é simplesmente a sua componente x, 3 .

Mas há uma coisa espantosa sobre os produtos escalares. Mesmo que o vetor unitário não esteja ao longo de um dos eixos, esta verdade geométrica mantém-se. Digamos que a é . A sua magnitude é 1 , portanto é um vetor unitário, mas está num ângulo de 45 graus em relação ao eixo . Digamos que é o vetor . O produto escalar a.b é , que é igual a , que por sua vez é a projeção do vetor sobre a reta que se estende ao longo do vetor a (ver figura abaixo).

Outra coisa importante que o produto escalar nos diz sobre dois vectores é se são perpendiculares, ou ortogonais, um ao outro. Se estiverem perpendiculares, então o cosseno de é igual a zero. Assim, independentemente do comprimento dos vectores, o seu produto escalar, ou a projeção do vetor sobre o vetor , é sempre zero. Por outro lado, se o produto escalar de dois vectores for zero, eles são ortogonais entre si.

Como calcularíamos o produto escalar se utilizássemos o outro método para representar vectores, utilizando as suas componentes, e não


saber o ângulo entre os dois vectores?

Digamos, e . Então:
j.j

Note-se que o segundo e terceiro termos da equação são zero. Os vectores e são ortogonais, pelo que i.j e são nulos. Além disso, tanto como j.j são iguais a 1. Tudo o que nos resta é uma quantidade escalar:

 MÁQUINAS E VECTORES


Se tudo isto parece muito distante da aprendizagem automática, dos perceptrões e das redes neuronais profundas, pode ter a certeza de que não é assim. É fundamental para o enredo. E estamos a chegar lá, aos trancos e barrancos, mas pisando cuidadosamente apenas as pedras necessárias para uma base segura.

É altura de revisitar o perceptron e pensar nele em termos de vectores. A intenção é obter conhecimentos geométricos sobre como os pontos de dados e os pesos de um perceptron podem ser representados como vectores e como visualizar o que acontece quando um perceptron tenta encontrar um hiperplano de separação linear que divide os pontos de dados em dois grupos. Muito disto tem a ver com a utilização de produtos escalares de vectores para encontrar as distâncias relativas dos pontos de dados em relação ao hiperplano, como veremos.

Recorde-se a equação genérica para um perceptron, que diz que o perceptron produz 1 se a soma ponderada das suas entradas mais um termo de polarização, , for superior a 0; caso contrário, produz -1 .

Fizemos uma alteração subtil à notação que usámos anteriormente: O argumento da função é agora um vetor; no capítulo anterior, como ainda não tínhamos introduzido a noção de vectores, tínhamos simplesmente em vez de . Vamos nos ater ao caso bidimensional, com pontos de dados dados por diferentes valores de e os pesos do perceptron dados por ( , w2). O perceptron calcula primeiro a soma ponderada das entradas:

Se esta soma ponderada for superior a um determinado limiar, denominado , então a saída do perceptrão, , é 1 . Caso contrário, é -1 . Assim:

Isto pode ser reescrito como:

Vamos colocar o nosso chapéu de vectores. O conjunto de pesos não é mais do que um vetor w. Mas o que é que w representa exatamente?

A figura acima mostra um vetor de peso, . Também mostra um vetor unitário na mesma direção, u. A linha tracejada dá-nos a direção ao longo da qual os dois vectores se encontram. Vamos desenhar uma linha preta sólida perpendicular, ou ortogonal, aos vectores e . Esta linha separa a área sombreada do resto do espaço de coordenadas. Assim, se estivéssemos a tentar encontrar uma linha que delineasse claramente o plano xy em duas regiões, sombreada e não sombreada, tudo o que precisaríamos para especificar tal fronteira seria o vetor , ou o vetor unitário correspondente, . Se a linha sólida, ou fronteira, na figura anterior é o hiperplano de separação, então o vetor é ortogonal a ele e caracteriza esse hiperplano. A fronteira é uma linha quando estamos a dividir um espaço 2D, um plano quando estamos a dividir um volume 3D, e um hiperplano em dimensões superiores.

A nossa análise anterior do algoritmo de aprendizagem do perceptron mostrou que este tenta encontrar um hiperplano que divide o espaço de coordenadas em dois. Assim, o perceptron encontra, ou aprende, um conjunto apropriado de pesos. Estes pesos constituem um vetor, w, que é ortogonal ao hiperplano. Quando se alteram os pesos do perceptron, altera-se a direção de , alterando-se assim a orientação do hiperplano, que é sempre perpendicular


para . E o que é verdade para também é verdade para o vetor unitário que se encontra na mesma direção. Assim, uma forma de reformular o que o perceptron faz é dizer que encontra o vetor , o que é o mesmo que dizer que encontra o hiperplano perpendicular correspondente.

Agora considere os pontos de dados que se encontram ou não na área sombreada. Cada ponto de dados é dado por e também pode ser considerado como um vetor. Então, a soma ponderada é igual ao produto escalar do vetor que representa o ponto de dados com o vetor de pesos. Observe que se o ponto de dados estiver no hiperplano, que no caso 2D é apenas uma linha, então o vetor será ortogonal a , fazendo com que o produto escalar seja igual a zero. Abaixo está uma visão gráfica do produto escalar dos pontos de dados e do vetor de peso. Por conveniência, trabalharemos com um vetor de peso de comprimento unitário. Não muda nada concetualmente, mas simplifica a matemática. Vamos começar com o vetor a, dado pelo ponto de dados .

Como é um vetor unitário, o seu produto escalar com a é igual à projeção de a sobre a linha tracejada. O ponto em que a pousa na reta perpendicular ao hiperplano é uma medida da distância do ponto (3, 1) ao hiperplano.

Em seguida, vejamos esta representação, um pouco movimentada mas importante, do produto escalar do vetor peso com quatro pontos de dados diferentes, ou vectores, a (3, , e .

É claro que o produto escalar de cada vetor com diz-lhe algo sobre esse vetor: a sua distância ao hiperplano e se está de um lado (o produto escalar é +ve ) ou do outro (-ve). Neste cenário, os pontos e estão linearmente separados dos pontos e . (Os pontos situados na área sombreada a cinzento representam ; os pontos situados na área não sombreada e os pontos situados na própria linha divisória representam .)

Então, digamos que o perceptron, na primeira tentativa, encontre os pesos e o hiperplano conforme descrito acima. Mas digamos também que, de acordo com nossos dados de treinamento rotulados, os pontos e deveriam estar em um lado do hiperplano e apenas o ponto no outro. Para fins de argumentação, digamos que , e representam pessoas classificadas como aquelas que gostam de filmes de suspense; representa uma pessoa que não gosta. Isto significa que o perceptron ainda não encontrou o hiperplano correto. Um amante de filmes de suspense foi classificado como um odiador de filmes de suspense. É aí que entra o termo de polarização. Adicionar um termo de polarização à equação é o mesmo que afastar o hiperplano da origem, mas


sem alterar a sua orientação. Por exemplo, depois de iterar através dos dados de treino, o perceptron poderia ter encontrado este hiperplano:

É evidente, olhando para a figura acima, que se os dados são linearmente separáveis em dois grupos, então existem muitos, muitos hiperplanos de separação (para diferentes valores do termo de polarização e diferentes orientações de w). Basta pensar na quantidade de linhas rectas que se podem traçar no espaço entre e : em princípio, infinitamente numerosas. O perceptron garante apenas que vai encontrar uma, e não necessariamente a melhor. Veremos o que significa "melhor" em mais pormenor, mas tem a ver com a previsão. Afinal, o perceptron está a aprender os pesos e o termo de polarização para classificar um ponto de dados ainda não visto em relação ao hiperplano. Por exemplo, dadas duas características de uma pessoa que estamos a utilizar para a classificar como amante ou odiadora de filmes de suspense, em que lado do hiperplano teria de estar a pessoa para ser classificada como uma ou outra? Um bom hiperplano ou o melhor hiperplano possível minimizará os erros de previsão futuros. (Definir um erro de previsão "futuro", quanto mais minimizá-lo, é um problema não trivial, ou não fácil).

Estes gráficos são uma forma de desenvolver um sentido intuitivo do que estava a acontecer quando um perceptron aprendia. Se tentássemos escrever um programa de computador para simular um perceptron, não estaríamos a desenhar tabelas e gráficos. Estaria a manipular números. Felizmente, as representações numéricas que vimos dos vectores até agora já são suficientes para mostrar o poder destas abstracções. No nosso exemplo 2D, os pontos de dados são apenas matrizes de números, cada matriz com dois elementos. O vetor de peso é igualmente outra matriz de dois números. Encontrar o produto escalar é uma questão de manipular estas matrizes.

Mais genericamente, esses vetores são chamados de matrizes, que contêm linhas e colunas de números. Por exemplo, se há linhas e colunas, então temos o que é chamado de uma matriz (lida como uma "matriz m por n"). Um vetor é uma forma particular de matriz com uma linha ou uma coluna: ou . Vimos isso antes, só que o termo "matriz" ainda não tinha sido introduzido. Mas é isso que os vectores são: matrizes com apenas uma coluna ou uma linha. Aqui está o exemplo da adição de duas matrizes de uma coluna para obter uma terceira matriz de uma coluna.

Se virarmos uma das matrizes de uma coluna de lado, obtemos uma matriz com uma única linha:

Assim, em notação formal, uma matriz de uma coluna com dois elementos é dada por:

A notação diz que a matriz coluna tem duas linhas (indexadas pelos números 1 e 2) e que cada linha tem apenas um elemento (índice 1). Quando se vira a matriz de lado, a numeração muda. (Note que o índice da linha é 1, enquanto as colunas têm índices 1 e 2).

A isto chama-se tomar a "transposição" de uma matriz. (Parece trivial, ou fácil, para uma matriz coluna, mas torna-se mais complicado para matrizes de ordem superior, que abordaremos em capítulos posteriores). Tomar a transposição é um aspeto fundamental do cálculo do produto escalar entre duas matrizes coluna. Utilizaremos letras maiúsculas em negrito para designar as matrizes. Seja A a matriz coluna e a matriz coluna . Não se pode tomar o produto escalar de duas matrizes coluna. Isso porque, para fazer o produto escalar, o número de colunas da primeira matriz deve ser igual ao número de linhas da segunda. Então, no nosso caso, uma delas deve ser transposta. A transposição de é escrita como . O produto escalar de escreve-se como ou . (São uma e a mesma coisa neste caso).

Note que este é exatamente o valor que obteria se escrevesse os vectores em termos dos seus vectores unitários e . Se e , então:

Aqui está outra coisa interessante sobre a utilização de matrizes, em vez de setas, para representar vectores: Pode simplesmente manipular os números e obter um valor escalar para o produto escalar sem se preocupar com o cosseno do ângulo entre eles. O que isto significa é que se tivermos um conjunto de pontos de dados, cada um representado por um vetor, e quisermos encontrar as suas distâncias relativas a um hiperplano caracterizado por um vetor de peso , tudo o que temos de fazer é tomar os produtos escalares de cada ponto de dados com , e teremos a informação necessária.

E se um dos pontos de dados estiver no hiperplano, o seu produto escalar com o vetor de peso será zero, o que significa que o ponto de dados é ortogonal ao vetor de peso e que a sua distância ao hiperplano é zero.

 MONTAGEM


Tudo isto conduz a uma notação abreviada bastante elegante para o perceptron.

Considere as entradas . Isto pode ser escrito como um vetor coluna . Da mesma forma, os pesos, usando um peso para cada entrada, [w1, w2,... , wn], são o vetor coluna . Note que fizemos outra mudança subtil na notação: Usamos parênteses rectos para conter os elementos de e , [], em vez de parênteses, (), para sinalizar que e são matrizes ou vectores.

Sabemos que a saída de um perceptron envolve o cálculo da soma ponderada . Isso é escrito de forma mais concisa como o produto escalar de e , ou . Dado isso, aqui está o que um perceptron faz:

Em termos pictóricos, vejamos novamente o perceptron com duas entradas e dois pesos:

O termo de polarização parece incongruente. Há um pequeno truque para o incluir no vetor de peso (ver primeira figura abaixo).

Nessa representação, o termo de viés é igual ao peso e é multiplicado por . No entanto, é sempre definido como 1 , garantindo que o viés seja sempre adicionado à soma ponderada das outras entradas. O vetor de pesos, , é agora dado por . O vetor de entrada, , é igual a , em que .

O perceptron genérico, para um vetor de entrada e um vetor de pesos , tem o aspeto da figura imediatamente acima.

A equação do perceptron parece ainda mais simples:

Vamos gravar esta equação na nossa mente. É uma declaração simples e eloquente destes factos: O vetor de peso é perpendicular à linha, ou hiperplano, que separa os pontos de dados em dois grupos. Para um grupo de pontos, é menor ou igual a zero, e a saída do perceptron é -1. Para o outro grupo de pontos, é maior que zero, e a saída do perceptron é 1 . Os pontos que se encontram no hiperplano (dado por 0 ) são atribuídos ao grupo com o rótulo . Do ponto de vista da aprendizagem automática, a tarefa de um perceptron é aprender o vetor de peso, dado um conjunto de vectores de dados de entrada, de modo a que o vetor de peso represente um hiperplano que separa os dados em dois grupos. Depois de ter aprendido o vetor de peso e de lhe ser dado um novo ponto de dados para classificar (por exemplo, como "obeso" ou "não obeso"), o perceptron tem simplesmente de calcular para a nova instância de dados, ver se cai num lado ou no outro do hiperplano e classificá-la em conformidade.

Esta foi uma viagem um pouco longa desde as ideias de Rosenblatt até uma notação formal para uma transformação linear de uma entrada para uma saída, mas é difícil exagerar a importância desta formulação. É uma das pedras angulares das nossas eventuais incursões noutras técnicas de ML, incluindo as modernas redes neuronais profundas.

 GARANTIA DE SUCESSO


Pouco depois de Rosenblatt ter inventado o algoritmo de aprendizagem perceptron - falaremos da sua formulação exacta daqui a pouco - os investigadores, incluindo Rosenblatt, começaram a analisá-lo, desenvolvendo teoremas e provas para mostrar que era de facto um algoritmo computacionalmente viável. Entre estas provas estavam as que mostravam que os perceptrons convergiriam para uma solução se esta existisse, sendo a "solução" definida como um hiperplano que separava linearmente os dados em dois grupos. George Nagy recorda essa altura. "O próprio Rosenblatt coleccionava isto", disse-me Nagy. "Tinha uma coleção de... provas que tinham sido publicadas na década de 1960." Uma dessas provas foi desenvolvida em 1962 por Henry David Block, um matemático aplicado da Universidade de Cornell que colaborou com Rosenblatt na análise matemática dos perceptrões. A prova de Block era complicada, mas estabelecia limites máximos para o número de erros cometidos pelo algoritmo de aprendizagem perceptron quando este tentava encontrar um hiperplano de separação linear. Block era um teórico de sucesso, à vontade com o raciocínio sobre máquinas e "a lógica do possível". Quando morreu em 1978, a faculdade de Cornell disse na sua declaração fúnebre: "Apesar de toda a sua inteligência e realizações excepcionais, David Block era uma pessoa profundamente modesta e humilde, tolerante com tudo exceto com a presunção."

A intolerância de Block à presunção transparece na sua clássica recensão de vinte e duas páginas de Perceptrons: An Introduction to Computational Geometry, um livro de trezentas páginas dos cientistas do MIT e pioneiros da IA Marvin Minsky e Seymour Papert. Um tour de force de exposição, teoremas e provas, Perceptrons causou um enorme impacto aquando da sua publicação em 1969. "Vamos estudar em grande pormenor uma classe de cálculos que fazem


decisões através da ponderação de provas", escrevem Minsky e Papert na sua introdução. "As máquinas que vamos estudar são versões abstractas de uma classe de dispositivos conhecidos por vários nomes; concordámos em usar o nome 'perceptron' em reconhecimento do trabalho pioneiro de Frank Rosenblatt." Block elogia o livro logo no início da sua recensão: "É um livro notável. Os autores não só formulam uma estrutura concetual nova e fundamental, como também preenchem os detalhes utilizando técnicas matemáticas surpreendentemente engenhosas." Uma dessas técnicas matemáticas engenhosas era a versão de Minsky e Papert da prova de convergência, mas as notas que a acompanhavam pareciam irritar Block. A dupla tinha chamado a atenção para um artigo de 1954 do matemático israelita Shmuel Agmon, que aparentemente tinha antecipado a prova de convergência. "Num sentido matemático abstrato, tanto o teorema como a prova já existiam antes do perceptron", escrevem Minsky e Papert. "É evidente que o teorema teria sido imediatamente óbvio se os ciberneticistas interessados nos perceptrões tivessem tido conhecimento do trabalho de Agmon."

A crítica aos ciberneticistas não agradou a Block. "Cibernética", um termo cunhado pelo matemático americano Norbert Wiener no seu livro de 1948 com o mesmo nome, refere-se ao estudo do "controlo e comunicação no animal e na máquina". Assim, aqueles que investigavam os perceptrões como meio de compreender o cérebro e o sistema nervoso humano eram ciberneticistas. Deveriam ter tido conhecimento dos precursores da prova de convergência dos perceptrões, que mostra que o algoritmo encontrará uma resposta após um número finito de passos? "Uma vez que não há nada no 'trabalho de Agmon'... sobre o fim do processo após um número finito de passos, este aspeto do teorema não parece ser 'instantaneamente óbvio'", gracejou Block na sua recensão. "Além disso, não é claro quem são 'os ciberneticistas'; mas presumivelmente os autores não se incluem nesta categoria. Podemos perguntar-nos porque é que a repreensão não se aplica a todos os interessados no perceptron". Block continuou com referências a artigos de 1961 de Minsky e Papert sobre tópicos relacionados com os perceptrões, implicando que a repreensão de Minsky e Papert se deveria aplicar igualmente a eles. Block diz o que pensa: "Em suma, a formulação de Minsky e Papert da sua teoria dos perceptrões é precisa e elegante. A sua formulação matemática


A sua análise é brilhante. A sua exposição é viva, muitas vezes bombástica e, ocasionalmente, sarcástica".

Deixando de lado as suas observações bombásticas e sarcásticas, vamos concentrar-nos na precisão e elegância da prova de convergência de Minsky e Papert. Mas primeiro, precisamos de revisitar o algoritmo de Rosenblatt com notações mais formais em mãos.

Vejamos um problema potencialmente real. Partindo do princípio de que aprendemos com a nossa experiência desastrosa com a pandemia do coronavírus, esperemos que possamos trazer alguma inteligência à forma como reagimos durante os primeiros meses da próxima pandemia que envolva um novo agente patogénico respiratório infecioso. (Neste cenário mais esclarecido, os hospitais de todo o mundo recolhem diligentemente dados sobre os doentes que vêem no início da pandemia. Cada paciente é categorizado usando seis variáveis: idade, índice de massa corporal, tem dificuldade em respirar (sim não ), tem febre (sim/não), tem diabetes (sim/não), tomografia computadorizada de tórax clara, infeção leve, infeção grave). Os valores para estas variáveis constituem um vetor de seis dimensões. Cada paciente é uma seta apontando no espaço 6D, ou simplesmente um ponto no espaço 6D.

Assim, para o ésimo doente, o vetor é dado por 6 atributos , .

Os médicos notam que os doentes ou estão bem cerca de três dias depois de chegarem ao hospital e são mandados para casa ou pioram e precisam de suporte ventilatório. Assim, cada doente tem um resultado associado (não necessitou de suporte ventilatório após três dias) ou (necessitou de suporte ventilatório após três dias).

Assim, o ésimo doente, xi, tem um resultado marcado, , que pode ser -1 ou 1 .

Em muitos países, os médicos recolhem dados sobre pacientes, criando um conjunto de pontos de dados:

Note-se que são todos vectores. Todos eles têm a mesma dimensão, neste caso 6. Temos de treinar um perceptron de modo a que, dada uma entrada, digamos, (a informação sobre o primeiro doente), o perceptron produza a


valor correspondente . O mesmo acontece com , e assim por diante. No nosso conjunto de dados, cada é classificado como pertencente ao grupo -1 ou ao grupo 1 .

Assumimos que os dados, que existem em seis dimensões, são linearmente separáveis em dois grupos. O hiperplano de separação seria fivedimensional e impossível de visualizar. Como é que se utiliza esta informação? Bem, em primeiro lugar, treinaria o perceptron com os dados recolhidos, de modo a que este encontrasse um hiperplano de separação.

Então, se o que é verdade para os pacientes nesta amostra de treinamento vale para todos os pacientes futuros - esta é uma suposição importante, e nós a examinaremos com mais cuidado em capítulos posteriores - imagine um cenário em que um novo paciente chega ao hospital. Você coleta os dados necessários (os valores de , e ) e os insere no seu perceptron. O perceptron deve dizer se o doente vai precisar de suporte ventilatório dentro de três dias, emitindo -1 ou 1 . Isto pode, por exemplo, ser utilizado para decisões de triagem. Os médicos podem, com alguma confiança, mandar algumas pessoas para casa mas manter outras em observação.

Treinar o perceptron significa encontrar os pesos [ , do vetor de pesos , tais que:

Recorde-se que w0 representa o termo de polarização e está incluído no vetor de pesos. É sempre multiplicado pelo valor 1 , ou .

Tendo isto em conta, o algoritmo de formação requer os seguintes passos:

  • Passo 1. Inicializar o vetor de pesos a zero: definir

  • Passo 2. Para cada ponto de dados no conjunto de dados de treino, faça o seguinte: - Passo 2a se :

o vetor de peso está errado, por isso actualize-o:

  • Passo 3. Se não tiver havido actualizações do vetor de pesos na etapa 2, terminar; caso contrário, voltar à etapa 2 e iterar novamente sobre todos os pontos de dados.

O perceptron começa por inicializar o vetor de pesos com zero e, em seguida, verifica se o vetor de pesos escolhido classifica corretamente cada ponto de dados, um de cada vez. Isso é feito calculando primeiro o valor da expressão para um ponto de dados. Se os pesos estiverem correctos para o ponto de dados e a expressão tiver um valor negativo, significa que se encontra à esquerda do hiperplano; significa também que é classificado com a etiqueta . Assim, se o valor esperado de for -1 e a expressão for avaliada como um número negativo, o seu produto será positivo. Da mesma forma, se os pesos estiverem correctos e se tiver um valor positivo, significa que está do lado direito do hiperplano; e significa que é classificado com a etiqueta . Assim, se o valor esperado for 1 e a expressão for avaliada como um número positivo, o seu produto será novamente positivo. Por outras palavras, se os pesos estiverem correctos, a expressão será sempre positiva.

Mas se os pesos estiverem errados, então será sempre um número negativo. (A expressão é avaliada como um número positivo, mas o valor esperado de é -1 , então será negativo; ou, a expressão é avaliada como um número negativo, mas o valor esperado de é +1 , então será negativo). Portanto, se for menor ou igual a zero, então algo está errado e devemos atualizar os pesos e a tendência.

De acordo com o algoritmo, atualizar os pesos implica adicionar a . Porque é que isto funciona? Intuitivamente, essa atualização está mudando a direção e a magnitude do vetor de peso (e, portanto, a direção do hiperplano) de tal forma que o ponto de dados , que estava no lado errado do hiperplano, acaba um pouco mais perto de estar no lado correto dele. Para um dado ponto de dados , pode ser necessário fazer várias actualizações deste tipo para garantir que é corretamente classificado como estando do lado correto do hiperplano. (Para uma prova formal, ver a coda matemática nesta página.) É claro,


fazer a correção para um ponto de dados significa que o hiperplano pode estar errado para alguns ou todos os outros pontos de dados.

Assim, o perceptron repete este processo, ponto de dados por ponto de dados, até chegar a um conjunto aceitável de valores para os pesos e a polarização que funcione para todos os pontos de dados. Ao fazê-lo, o perceptron encontra a divisão linear entre os dois conjuntos de pontos de dados.

No que diz respeito aos algoritmos informáticos, este é incrivelmente simples. A questão para os matemáticos era a seguinte: Como é que podemos ter a certeza de que vai terminar? Porque é que não continua indefinidamente, errando sempre pelo menos um ponto de dados?

É aí que entram as provas de convergência - em particular, uma prova especialmente elegante de Minsky e Papert no seu livro, Perceptrons. Começamos por reafirmar o pressuposto principal: Existe um hiperplano linearmente separador caracterizado pelo vetor de peso . O perceptron tem de encontrar . Existem, é claro, muitos hiperplanos potenciais, e o algoritmo precisa encontrar apenas um.

O algoritmo começa por utilizar um vetor de pesos inicializado a zero. Agora considere o produto escalar de e . À medida que actualizamos o vetor de peso e este começa a apontar cada vez mais na direção do vetor de peso desejado , o ângulo entre e aproxima-se de zero, independentemente da escolha de . O produto escalar de e , dado por , continua a aumentar, porque passa de zero (quando os dois vectores são perpendiculares e muito diferentes um do outro) para 1 (quando são paralelos e, portanto, apontam na mesma direção). Assim, à medida que o algoritmo aprende, queremos que w.w* continue a aumentar; isso é uma indicação de que está a funcionar. No entanto, w. também pode aumentar simplesmente porque a magnitude de continua a aumentar sem mostrar qualquer mudança de direção. Nesse caso, w.w (o produto escalar de por ele mesmo) também aumentará. Assim, a essência da prova consiste em mostrar que, durante o treino, w.w aumenta menos rapidamente que w.w*. Se for esse o caso, o algoritmo convergirá num número finito de passos, quando coincidir com . Os leitores interessados em compreender a prova podem encontrá-la na coda matemática desta página.

A prova estabelece uma desigualdade. Diz que se o algoritmo actualiza o vetor de pesos M vezes (ou comete M erros) antes de encontrar a solução, então M deve ser menor ou igual a um número finito. Isto é feito estabelecendo os chamados limites inferior e superior para o algoritmo, que são medidas de, no mínimo e no máximo, quanto tempo e recursos o algoritmo precisa para chegar à solução desejada. Provar esses limites para algoritmos é uma tarefa difícil, intrincada e esotérica num campo de investigação chamado teoria da complexidade computacional.

Em 2018, Manuel Sabin, um jovem investigador que conheci na Universidade da Califórnia, em Berkeley, apresentou uma perspetiva eloquente desse trabalho numa curta-metragem que escrevi, apresentei e co-dirigi (o filme fazia parte de uma série de documentários). "Existem ligações profundas entre limites inferiores e limites superiores. Muitas vezes, pode dizer-se que são duas faces da mesma moeda", disse. Os limites inferiores dizem-nos se algo é impossível. Digamos que se prova que um algoritmo demora exponencialmente mais tempo a executar à medida que se aumenta o número de pontos de dados. Nessa altura, encontraremos problemas para os quais "não saberemos a resposta até que o sol engula a terra", disse Sabin. "Por isso, os limites inferiores... dizem respeito ao que é possível saber durante a nossa vida".

Não é de admirar que o estabelecimento de tais limites para o algoritmo de aprendizagem perceptron tenha sido um grande negócio na década de 1960. O algoritmo encontrará sempre um hiperplano de separação linear em tempo finito, se existir. Minsky e Papert, Block e outros foram responsáveis por uma série de provas deste tipo. Os Perceptrons estavam na moda.


O PRIMEIRO GRANDE ARREPIO


Mas depois, o livro de Minsky e Papert de 1969, que forneceu uma base matemática tão sólida para a investigação sobre os perceptrões, também lhe deitou uma enorme quantidade de água fria. Entre as muitas provas do seu livro, uma aborda um problema muito simples que uma única camada de perceptrões nunca poderia resolver: o problema XOR. Observe os quatro pontos de dados mostrados na figura abaixo.

Nenhuma linha reta que se possa traçar separará os círculos dos triângulos. Os pontos , neste caso, são: e . Para que o perceptron separe os círculos, representados pelos pontos e , dos triângulos, representados por e , ele deve ser capaz de gerar uma saída quando ambos e são 0 ou ambos e são 1, e uma saída caso contrário. Não existe tal linha reta, algo que é fácil de ver visualmente. Minsky e Papert provaram que uma única camada de perceptrons não consegue resolver este tipo de problemas. A situação ilustrada acima é o caso mais simples e faz lembrar a porta XOR com duas entradas na lógica booleana, em que a porta lógica produz um 1 se ambas as entradas forem iguais e um 0 caso contrário.

É possível resolver o problema XOR se empilharmos perceptrões, de tal forma que a saída de um alimenta a entrada de outro. Estes seriam os chamados perceptrões multi-camadas. Rosenblatt não estava alheio a este problema. "Ele sabia certamente tão bem ou melhor do que Minsky as limitações de uma única camada", disse-me Nagy. No entanto, o problema das camadas múltiplas de perceptrões era que ninguém sabia como treinar essas redes, incluindo Minsky e Papert. O algoritmo que encontrámos anteriormente não funciona se os pesos de mais do que uma camada de perceptrons tiverem de ser actualizados.

O alarido em torno das redes neuronais diminuiu. Tudo o que se falava de um computador eletrónico que "andaria, falaria, veria, escreveria, reproduzir-se-ia e


ter consciência da sua existência" evaporou-se, tal como qualquer noção de enviar dispositivos perceptrónicos para outros planetas como "exploradores espaciais mecânicos". As agências de financiamento hesitaram, o dinheiro desapareceu e um campo de investigação outrora promissor quase parou. Os profissionais da área referem-se aos anos de 1974 a 1980 como o primeiro inverno da IA. Sir James Lighthill, o professor lucasiano de matemática aplicada na Universidade de Cambridge, analisou o campo e, em 1972, publicou um relatório sobre o estado da IA. O seu relatório tinha até uma secção chamada "Desilusões do passado". Começa com estas palavras: "A maioria dos trabalhadores da investigação em IA e de áreas relacionadas confessam um sentimento pronunciado de desilusão com o que foi alcançado nos últimos vinte e cinco anos. Os trabalhadores entraram neste campo por volta de 1950, e mesmo por volta de 1960, com grandes esperanças que estão muito longe de se terem realizado em 1972. Em nenhuma parte do campo as descobertas feitas até agora produziram o grande impacto que foi então prometido."

No que diz respeito às redes neuronais, foi necessária uma solução única de um físico para um problema biológico para reativar o campo. Isso aconteceu em 1982. Depois, em 1986, David E. Rumelhart, Geoffrey E. Hinton e Ronald J. Williams publicaram um artigo inovador sobre um algoritmo chamado retropropagação. (A ideia em si era anterior ao seu trabalho, mas o seu artigo colocou-a firmemente no mapa). O algoritmo, que mostrou como treinar perceptrons multicamadas, baseia-se no cálculo e na teoria da otimização. Só passados mais quinze anos é que os computadores se tornariam suficientemente potentes para lidar com as exigências computacionais das redes neuronais artificiais, mas o artigo "backprop" pôs em marcha uma revolução lenta.

No entanto, o precursor do algoritmo de retropropagação, com a sua ênfase no cálculo, estava a tomar forma mais ou menos na mesma altura em que Rosenblatt exibia o seu perceptron. No final da década de 1950, ao longo de um fim de semana, um jovem professor assistente e um aluno de pós-graduação extremamente talentoso inventaram e implementaram um algoritmo que viria a revelar-se tão importante como o perceptron e que conteria pistas para um dia treinar redes neuronais de várias camadas.

 CODA MATEMÁTICA


Pode saltar a prova que se segue; fazê-lo não terá impacto na sua compreensão do que vem nos capítulos seguintes. Devo dizer, no entanto, que foi ao ouvir gravações de palestras de Kilian Weinberger, professor de ciência da computação na Universidade de Cornell, em que ele explica esta prova aos alunos do seu curso de 2018 sobre aprendizagem automática, que percebi que queria escrever este livro. É uma bela prova.


O ALGORITMO: A REGRA DE ACTUALIZAÇÃO DO PERCEPTRON

(This rule and proof adapted from Weinberger's lecture.)

  • Passo 1. Inicializar o vetor de pesos a zero: definir .

  • Passo 2. Para cada ponto de dados no conjunto de dados de treino, faça o seguinte:

  • Etapa 2a se :

o vetor de peso está errado, por isso actualize-o:

  • Passo 3. Se não tiver havido actualizações do vetor de pesos na etapa 2, terminar; caso contrário, voltar à etapa 2 e iterar novamente sobre todos os pontos de dados.

Fazemos uma atualização do vetor de pesos se (ver a explicação em "Garantido para ter sucesso" nesta página para saber porque é que isto acontece):

Para que o novo vetor de pesos classifique corretamente, temos de provar que, eventualmente, (porque se fosse , teria sido necessário actualizá-lo). Em cada passo da atualização:

O segundo termo do lado direito é , porque , e . Porque é que ? Bem, é o produto escalar de um vetor com ele próprio. Este é sempre um número positivo ou zero. É semelhante a elevar um escalar ao quadrado - obtém-se sempre um número positivo ou zero.

Assim, , após uma atualização, é um pouco menos negativo do que , o que significa que o vetor de pesos está a mover-se na direção certa para o único ponto de dados . Eventualmente, após um número não especificado de actualizações, o algoritmo classificará corretamente. Este processo deve ser repetido para cada ponto de dados até que o vetor de pesos classifique todos os dados corretamente.

A prova que se segue mostra que o número de actualizações necessárias para encontrar o novo vetor de pesos correto é sempre finito.


A PROVA DE CONVERGÊNCIA DO PERCEPTRÃO

 Pressupostos:

w: o vetor de peso d-dimensional inicializado a zero;

: o vetor de peso d-dimensional que o perceptron tem de aprender; é perpendicular ao hiperplano de separação linear. Seja um vetor unitário de magnitude 1 ;

: o vetor que representa um ponto de dados de entrada, ou instância; é um vetor ddimensional, portanto com elementos . Se houver pontos de dados, então cada uma dessas instâncias é uma linha numa matriz maior (n linhas, d colunas);


: a saída do perceptron, para um vetor de entrada ; a saída pode ser -1 ou 1 . Todas as saídas podem ser reunidas num vetor unidimensional ; e

Y (gamma): distância entre o hiperplano de separação linear e o ponto de dados mais próximo.

A equação seguinte é a equação para o perceptron (ignorando um termo de polarização explícito; vimos anteriormente como incorporá-lo nesta formulação):

O objetivo é provar que, se continuar a atualizar , este convergirá para (ou seja, os dois vectores apontarão na mesma direção). E como , por definição, é perpendicular ao hiperplano de separação, o mesmo acontecerá com .

Primeiro, normalize todos os pontos de dados de entrada de modo que o ponto de dados mais distante da origem tenha uma magnitude de 1 e todos os outros pontos de dados tenham magnitudes menores ou iguais a 1 . Isto pode ser feito dividindo cada vetor pela magnitude do ponto de dados, ou vetor, que está mais afastado da origem. Assim, o vetor mais afastado terá agora uma magnitude de 1 , e todos os outros vectores terão magnitudes que são menores ou iguais a 1 . Isto não altera a relação entre os pontos de dados/vectores porque estamos simplesmente a reduzir as suas magnitudes pela mesma quantidade; as suas direcções permanecem as mesmas.

Uma vez normalizado, .

Recorde-se que actualizamos o vetor de pesos quando uma entrada, , é classificada incorretamente:

À medida que se aproxima de , que é a nossa direção desejada, o produto escalar dos dois vectores, ou , aumenta.

Mas também pode aumentar se crescer em magnitude sem mudar de direção em relação a . Se estiver a crescer em magnitude, então , que é o produto escalar de por si próprio, também aumentará. Assim, o algoritmo só converge se aumentar mais depressa que , pois isso só acontece porque está a ficar alinhado com e não apenas a aumentar em magnitude.

Vamos calcular em cada atualização:

O segundo termo do lado direito é . Se tivermos dois vectores ddimensionais e , sabemos que . Então, . Sabemos que , porque é o vetor de pesos presumidos correto, e deve classificar corretamente.

O produto escalar do vetor unitário e é a distância de ao hiperplano caracterizado por . Definimos como a distância entre o ponto de dados mais próximo e o hiperplano. Assim, não só é maior que 0 , como também é sempre maior ou igual a .
 Assim,

Resultado provisório 1: Isto está a dizer-nos algo importante. O produto escalar entre e cresce pelo menos com cada atualização.

Vamos agora examinar a taxa de crescimento de .
 Desde então:

Assim, o produto escalar do novo vetor de peso por si próprio é igual ao produto escalar do antigo vetor de peso por si próprio mais dois novos termos. Temos de descobrir a contribuição dos novos termos.

Sabemos que o primeiro termo novo porque . É por essa razão que estamos a fazer uma atualização do vetor de pesos.

O segundo novo termo é . Porque ou é +1 ou . Além disso, é sempre menor ou igual a 1 (isto porque normalizámos todos os vectores que representam os pontos de dados anteriormente, pelo que as suas magnitudes são sempre menores ou iguais a 1 ).

Assim, a equação torna-se:

Resultado provisório 2: Isto diz-nos que o produto escalar do vetor de pesos com ele próprio cresce no máximo 1 em cada atualização.

Agora, por um lado, temos a crescer pelo menos em cada atualização e, por outro lado, temos a crescer no máximo 1 em cada atualização.

Digamos que o algoritmo faz M actualizações para encontrar o hiperplano linearmente separador. A nossa tarefa é provar que M é um número finito e que o algoritmo converge para uma solução.

Começamos com o vetor de pesos inicializado a zero, pelo que o valor inicial de é zero. Após a primeira atualização, o produto escalar teria crescido pelo menos .

Após 1 atualização:

Após 2 actualizações:

Após 3 actualizações:

Após actualizações:
 Então:

Do mesmo modo, usando o resultado intermédio 2, que diz que aumenta no máximo 1 após cada atualização, após actualizações, devemos ter:

Agora, devido a (1), temos:

; esta é a definição do produto escalar.

, porque e , por conceção.
 Por conseguinte:

, porque , por definição.

O lado direito pode ser substituído usando o resultado em (2), dando-nos:

Depois de toda esta análise, chegámos a um resultado surpreendente: O número de actualizações que o perceptron faz para encontrar um hiperplano linearmente separador é menor ou igual a 1 sobre . Porque gamma é sempre uma quantidade positiva que é menor ou igual a é sempre uma quantidade finita. O perceptron irá convergir sem falhas num número finito de passos.

QED

 CAPÍTULO 3


O fundo da taça


stávamos no outono de 1959. Bernard Widrow, um jovem académico prestes a completar trinta anos, estava no seu gabinete na Universidade de Stanford quando um estudante licenciado chamado Marcian "Ted" Hoff o procurou. O jovem chegou muito bem recomendado. No dia anterior, um professor sénior de Stanford tinha contactado Widrow em nome de Hoff, dizendo: "Tenho um aluno chamado Ted Hoff. Não consigo fazer com que ele se interesse [pela minha investigação]; talvez ele se interesse pelo que você está a fazer. Estaria disposto a falar com ele?" Widrow respondeu: "Claro, com todo o gosto."

"No dia seguinte, quem bateu à minha porta foi Ted Hoff", contou-me Widrow.

Widrow deu-lhe as boas-vindas e começou a falar do seu trabalho, que se centrava em filtros adaptativos - dispositivos electrónicos que aprendem a separar os sinais do ruído - e na utilização do cálculo para otimizar esses filtros. Enquanto Widrow escrevia os cálculos no quadro negro, Hoff juntou-se a ele e rapidamente a conversa se transformou em algo mais dramático. Durante essa discussão, os dois inventaram o que veio a ser designado por algoritmo dos mínimos quadrados médios (LMS), que se revelou um dos algoritmos mais influentes na aprendizagem de máquinas, tendo-se revelado fundamental para quem estava a tentar descobrir como treinar redes neuronais artificiais. "Quando escrevi o algoritmo LMS no quadro pela primeira vez, de alguma forma soube intuitivamente que se tratava de uma coisa profunda", disse-me Widrow. "Foi pena não ter uma câmara para tirar uma fotografia".

Widrow cresceu numa pequena cidade do Connecticut. Dificilmente poderia ter imaginado a sua luminosa carreira académica. O seu pai geria uma fábrica de produção de gelo. Um jovem e curioso Widrow andava pela fábrica, no meio de


geradores, motores e compressores, fazendo sempre perguntas. Admirava o eletricista da fábrica, que lhe ensinou as bases da profissão. Quando Widrow ainda estava no liceu, o pai sentou-se com ele e perguntou-lhe: "O que achas que queres ser quando fores grande?"

O adolescente respondeu: "Quero ser eletricista".

O pai dele disse: "Não queres ser eletricista. Queres ser engenheiro eletrotécnico".

Essa subtil correção de rumo levou Widrow ao MIT em 1947, onde obteve a licenciatura, o mestrado e o doutoramento; entrou para o MIT como professor assistente em 1956. Um dia, durante o verão desse ano, o colega de Widrow, Ken Shoulders, foi ao laboratório e falou-lhe de um workshop sobre inteligência artificial no Dartmouth College a que ia assistir; Widrow queria ir? Eu perguntei-lhe: "O que é a inteligência artificial? Ele respondeu: "Não sei. Mas parece-me interessante'. Por isso, eu disse: "Claro. Vou contigo. '

A criação do termo "inteligência artificial" é atribuída a John McCarthy, um professor de matemática do Dartmouth College. Em agosto de 1955, McCarthy, Marvin Minsky, que estava então na Universidade de Harvard, Nathaniel Rochester da IBM e Claude Shannon dos Laboratórios Bell Telephone, apresentaram "A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence". Começava com uma declaração ousada:

Propomos que seja efectuado um estudo sobre inteligência artificial com a duração de 2 meses e 10 pessoas, durante o verão de 1956, no Dartmouth College em Hanover, New Hampshire. O estudo deve prosseguir com base na conjetura de que todos os aspectos da aprendizagem ou qualquer outra caraterística da inteligência podem, em princípio, ser descritos com tanta precisão que uma máquina pode ser feita para os simular. Tentar-se-á descobrir como fazer com que as máquinas utilizem a linguagem, formem abstracções e conceitos, resolvam tipos de problemas atualmente reservados aos seres humanos e se aperfeiçoem. Pensamos que é possível fazer um avanço significativo num ou mais destes problemas se um grupo de cientistas cuidadosamente selecionado trabalhar em conjunto durante um verão.

Widrow lembrava-se que se tratava de um seminário aberto, sem necessidade de convite. Podia-se ir e ficar o tempo que se quisesse. Falava-se quando se tinha algo a dizer, ou podia-se simplesmente ouvir. Widrow ouviu e depois regressou ao MIT cheio de energia. Ele queria construir uma máquina pensante. "Passei seis meses a pensar sobre o pensamento", disse ele. "A conclusão foi que, com os circuitos e a tecnologia de que dispúnhamos na altura, esperava que passassem vinte e cinco anos até conseguirmos construir uma máquina pensante." Para um jovem investigador em início de carreira, parecia uma aventura imprudente. Widrow abandonou os seus planos e voltou-se para algo mais concreto: filtros adaptativos que pudessem aprender a remover o ruído dos sinais. Ele estava particularmente interessado na forma digital de filtros analógicos adaptativos desenvolvidos por Norbert Wiener. (Encontrámos Wiener no capítulo anterior como o homem que cunhou o termo "cibernética").

Para entender o filtro analógico de Wiener, considere uma fonte de sinal continuamente variável (portanto, analógica). É adicionado algum ruído ao sinal, e a função do filtro é distinguir o sinal do ruído. A teoria do filtro de Wiener mostrou como isto pode ser feito. Outros adaptaram a teoria aos sinais digitais. Em vez de serem contínuos, os sinais digitais são discretos, o que significa que só têm valores em determinados momentos (por exemplo, uma vez a cada milissegundo). Widrow queria construir um filtro digital, mas um que pudesse aprender e melhorar com o tempo. Por outras palavras, aprenderia com os seus erros e tornar-se-ia uma versão melhor de si próprio.

No cerne de um filtro adaptativo está um pequeno cálculo. Imagine que o filtro, num determinado momento, comete um erro. Vamos assumir que somos capazes de registar esses erros durante dez passos de tempo. Temos de reduzir o erro que o filtro comete olhando para os dez erros anteriores e ajustando os seus parâmetros. Uma medida dos erros é simplesmente a média dos dez erros anteriores. No entanto, os erros podem ser positivos ou negativos e, se os adicionarmos para obter a média, podem anular-se mutuamente, dando a impressão errada de que o filtro está a funcionar bem. Para evitar isso, tome o quadrado de cada erro (transformando-o assim numa quantidade positiva) e depois tome a média dos quadrados dos erros. Há outras vantagens em elevar os erros ao quadrado e calcular a média, que têm a ver com estatística e


cálculo, mas ainda não precisamos de nos concentrar nisso. O objetivo é minimizar este "erro quadrático médio" (MSE) em relação aos parâmetros do filtro. Em outras palavras, devemos alterar os valores dos parâmetros do filtro a cada passo de tempo de forma que a média dos erros quadráticos dos últimos dez passos seja minimizada. Para entender como isso funciona, é necessário mergulhar em alguns cálculos simples e aprender um método que foi proposto pela primeira vez em 1847 pelo Barão Augustin-Louis Cauchy, um matemático, engenheiro e físico francês. É o chamado método da descida mais íngreme.


DESCIDO DO ALTO


Se já viu fotografias - ou, melhor ainda, se já visitou - de arrozais em encostas, particularmente na China, no Japão e no Vietname, deve ter ficado maravilhado com os terraços planos cortados nas encostas das colinas. Se caminharmos ao longo de qualquer terraço, mantemo-nos à mesma altitude. As extremidades dos socalcos acompanham os contornos do terreno. Imaginemos que estamos num terraço no cimo de uma colina. No vale, em baixo, há uma aldeia. Temos de chegar à aldeia, mas está a escurecer e só conseguimos ver alguns metros à nossa frente. Digamos que


a encosta não é demasiado íngreme e que é possível descer mesmo nas partes mais íngremes. Como é que vamos proceder?

Podemos ficar na borda do terraço e procurar o caminho mais íngreme para o terraço abaixo. Esse é também o caminho mais curto para o próximo pedaço de terreno plano. Se repetirmos o processo de terraço em terraço, acabaremos por chegar à aldeia. Ao fazê-lo, teremos seguido o caminho de descida mais íngreme. (Pode não ser uma linha reta da nossa posição inicial até à aldeia; podemos ter tido de descer a encosta em ziguezague).

O que fazíamos instintivamente era avaliar a inclinação, ou o declive, da encosta quando olhávamos em diferentes direcções enquanto estávamos à beira de um terraço e, em seguida, tomávamos o caminho mais íngreme para baixo de cada vez. Fizemos um cálculo na nossa cabeça, por assim dizer.

Mais formalmente, vejamos a descida de um declive para uma curva 2D, dada pela equação .

Primeiro, traçamos a curva no plano xy e, em seguida, localizamo-nos na curva em algum valor de , digamos, . Nesse ponto, a curva tem um declive.

Uma forma de determinar o declive de uma curva é desenhar uma tangente à curva no ponto de interesse. A tangente é uma linha reta. Imagine que caminha um pouco ao longo da linha reta. Estaria num novo local, onde a coordenada x mudou numa quantidade infinitesimal ( ; leia-se "delta x") e a coordenada y também mudou numa quantidade correspondente


quantidade infinitesimal ( . O declive é . (Se pensarmos em subir escadas, então o declive das escadas é dado pela subida dividida pela corrida, em que a subida é , ou o quanto se sobe verticalmente com cada passo, e a corrida é , a quantidade que se move horizontalmente com cada passo).

É claro que, ao fazer isto no nosso exemplo, deslocámo-nos ao longo da tangente à curva e não ao longo da própria curva. Assim, o declive diz respeito à tangente e não à curva. No entanto, se a mudança na direção x, , se aproximar de zero, então o declive da linha tangente aproxima-se cada vez mais do declive da curva no ponto de interesse, até que os dois se tornam iguais quando . Mas como é que se calcula o declive quando o denominador em é zero? É aí que o cálculo entra em ação.

O cálculo diferencial é um ramo do cálculo que nos permite calcular o declive de uma função contínua (que não tem cúspides, quebras ou descontinuidades). Permite-lhe derivar analiticamente o declive no limite (leia-se "delta-x tende para zero"), o que significa que o passo que dá na direção se torna extremamente pequeno, aproximando-se de zero. Este declive é chamado a derivada de uma função.

Para a nossa função , a derivada é igual a . (Encontrar a derivada de uma função está no cerne do cálculo diferencial, mas não entraremos em detalhes aqui. Para as funções usadas neste livro, vou simplesmente fornecer as derivadas. Para entender como encontrar a derivada de uma função e para obter uma lista de derivadas de funções comuns, consulte o Wolfram MathWorld).

Escrevemos a nossa derivada como:

A isto chama-se a derivada de em relação a .

O cálculo pode fazer com que os nossos olhos fiquem vidrados, ou mesmo induzir um verdadeiro pavor. Mas como Silvanus P. Thompson, um professor de física, eletricidade e


engenheiro e membro da Royal Society, escreveu no seu clássico Calculus Made Easy (publicado pela primeira vez em 1910), o "terror preliminar" dos símbolos em cálculo "pode ser abolido de uma vez por todas, bastando para isso dizer qual é o significado - em termos de senso comum - dos... símbolos principais". O símbolo , salienta, significa simplesmente "um pouco de". Assim, é um pouco de dividido por um pouco de . A beleza do cálculo é que você pode calcular essa proporção mesmo quando esse "pouco de " tende a zero, ou .

Dada a derivada, temos agora uma forma de determinar o declive em qualquer ponto da curva. Assim, para a função , a inclinação , e em a inclinação é igual a , que é igual a 4 . Em , a inclinação é 2 ; em , a inclinação é 1 ; e em , a inclinação é 0 . Podemos ver que quando nos deslocamos ao longo da curva, à medida que o valor de diminui de 2 , o mesmo acontece com o declive, até que a função atinge um mínimo (onde o declive se torna zero), e depois diminui ainda mais. O declive em geral é zero no mínimo de uma função; neste exemplo, as coordenadas ( ) também são no mínimo, mas não tem de ser assim.

Estamos agora preparados para compreender o método da descida mais íngreme, também conhecido como método da descida do gradiente. Digamos que estamos na coordenada . Queremos chegar à base da curva, onde o declive é zero e o valor da função está no seu mínimo. Em qualquer ponto da curva, só há dois caminhos a seguir. Ir por um caminho afasta-o da base; ir pelo outro caminho aproxima-o da base. O truque para dar um passo na direção certa é, em primeiro lugar, calcular o declive, ou gradiente, na sua localização atual. (O termo "gradiente" tem um significado mais específico, mas vamos usá-lo aqui mesmo assim). Neste caso, para , o declive é 2. Se a função tem forma de taça, como é o caso, então o caminho para o mínimo envolve ir numa direção que diminui o declive. Assim, damos um passo tal que o valor da coordenada x é reduzido por algum tamanho de passo multiplicado pelo gradiente nesse ponto:

Vamos ver por que é que dar um passo que reduz o valor de reduz o gradiente. Para a nossa equação, o gradiente é dado por . Portanto, se o novo valor de for menor que o antigo valor de , o gradiente no novo local será menor que antes. A nova coordenada x dá-nos uma nova coordenada y. Acabamos por chegar a uma nova localização. Repetimos o processo até que o gradiente seja zero ou próximo de zero. (Atingimos o fundo ou estamos suficientemente perto dele.) Eis um gráfico que descreve o processo:

O tamanho do passo, , deve ser um número pequeno, uma fração (digamos, 0,1 ). Porquê? Principalmente porque à medida que se aproxima do fundo, quer ter muito cuidado para não ultrapassar o mínimo e acabar mais alto do outro lado da curva. Se o fizer, dependendo da função, o algoritmo pode começar a levá-lo mais acima na curva, para longe do mínimo. Repare também que, embora o tamanho do passo seja o mesmo em cada iteração do algoritmo, o tamanho dos saltos ao longo da curva é maior no início e torna-se menor à medida que se aproxima do fundo. Mais uma vez, porquê? Porque estamos a subtrair um múltiplo do gradiente da coordenada x para obter uma nova coordenada x. O múltiplo, ou tamanho do passo, não muda no nosso algoritmo. Mas o que é que


mudar é o gradiente: Está a ficar mais pequeno. Assim, os saltos ao longo da curva também se tornam progressivamente mais pequenos.

Funções como a descrita acima, que têm um mínimo único e bem definido, são também chamadas funções convexas. Quando encontramos o fundo da taça, tecnicamente, encontrámos o mínimo "global" da função. (Se uma função tem vários mínimos, então cada um deles é chamado de mínimo "local").

Agora considere o caso em que a minimização envolve uma função que recebe duas entradas. Aqui está a função:

O gráfico mostra a superfície 3D em forma de taça, designada por paraboloide elíptico. Se começarmos em qualquer ponto acima do fundo da taça, a descida ao longo da superfície deste paraboloide pode ser facilmente visualizada. A diferença em relação ao caso 2D é que utilizamos o gradiente em qualquer localização para


calcula as novas coordenadas x e y, em vez de apenas a coordenada x. (A mesma operação: Subtrair a cada coordenada o gradiente vezes o tamanho de um passo). Isto dá-nos então uma nova coordenada z, e descemos para uma nova localização na superfície. Fazendo isto iterativamente, chegamos ao fundo da taça.

Aqui está uma função diferente para ajudar a visualizar porque é que pode não ser possível encontrar o mínimo para certas funções.

A superfície 3 D é definida por esta equação:
Z

A superfície é designada por paraboloide hiperbólico. Repare que se assemelha a uma sela: parte superfície convexa e parte côncava. Na figura acima, começamos a descer a partir da nossa localização e, ostensivamente, chegamos a um local onde o gradiente é zero. Mas este é um local instável. É o chamado ponto de sela. Um passo em falso e a superfície cai. Esta função não tem um mínimo global ou local. Além disso, o ponto de partida inicial pode ditar se


nem sequer se aproximar do ponto de sela durante a descida. Veja este cenário, por exemplo:

Neste caso, tentar descer o declive seguindo a mesma técnica (porque se começa noutro sítio) pode fazer com que se desvie do ponto de sela.

Tudo isto pode parecer terrivelmente abstrato, mas a descida de gradiente é crucial não só para o algoritmo de Widrow e Hoff, mas também para a aprendizagem automática moderna. Mas antes de ligarmos a descida gradiente ao trabalho de Widrow e Hoff, há um pormenor importante que temos de abordar.

Repetir esta função:

Recorde-se que quando tínhamos uma função com uma variável , podíamos utilizar o cálculo para determinar a derivada e utilizar este valor para efetuar a descida do gradiente. Mas o que é que fazemos quando a função envolve


múltiplas variáveis? Bem, existe todo um campo do chamado cálculo multivariável ou multivariado. E embora possa ser assustador confrontar o cálculo multivariado na sua totalidade, podemos apreciar o papel central que desempenha na aprendizagem automática, concentrando-nos em algumas ideias simples.

Imagine que está num ponto qualquer da superfície de um paraboloide elíptico, . Para descobrir a direção da descida mais íngreme, temos de nos preocupar com duas direcções, dado que temos duas variáveis. Seguindo a exortação de Thompson para dizer as coisas de forma simples, sabemos que movermo-nos ao longo da superfície significa uma pequena mudança no valor da variável . Assim, a nossa tarefa é calcular e ; ou uma "pequena mudança em dividida por uma pequena mudança em " e uma "pequena mudança em dividida por uma pequena mudança em ," respetivamente.

Em linguagem de cálculo, estamos a tomar a derivada parcial de em relação a , e a derivada parcial de em relação a . Para o nosso paraboloide elíptico, as derivadas parciais são: .

Além disso, note-se a ligeira alteração do símbolo utilizado: em vez de e em vez de . O "d" curvo significa uma derivada parcial de uma função em relação a uma das muitas variáveis. Para uma compreensão concetual do que se segue, não precisamos de nos preocupar com a forma de derivar estas derivadas parciais. É suficiente saber que, dadas funções diferenciáveis, o cálculo mostra-nos como chegar a estas expressões analíticas.

O conceito mais importante aqui é que a direção da descida mais acentuada, para este exemplo, é dada por duas derivadas parciais. Digamos que está num local onde:

Neste local, as duas derivadas parciais têm os valores:

Se escrevermos estes números nesta forma, parece algo muito familiar: . É um vetor!

Assim, se tiver de se mover ligeiramente na direção da descida mais íngreme, essa direção pode ser inferida a partir deste vetor. Lembre-se que um vetor tem uma magnitude (ou comprimento) e uma direção. Neste caso, o nosso vetor é uma seta que vai de para . Este vetor é chamado gradiente. Um ponto técnico: O gradiente aponta para longe do mínimo. Assim, para descer em direção ao mínimo, é necessário dar um pequeno passo na direção oposta ou seguir o negativo do gradiente.

Se há uma coisa a retirar desta discussão, é o seguinte: Para uma função multidimensional ou de elevada dimensão (ou seja, uma função de muitas variáveis), o gradiente é dado por um vetor. Os componentes do vetor são derivadas parciais dessa função em relação a cada uma das variáveis.

Para o nosso paraboloide elíptico, o gradiente é escrito como:

O gradiente pode ser escrito como um vetor linha ou um vetor coluna.

O que acabámos de ver é extraordinariamente poderoso. Se soubermos como obter a derivada parcial de uma função em relação a cada uma das suas variáveis, independentemente do número de variáveis ou da complexidade da função, podemos sempre exprimir o gradiente como um vetor linha ou vetor coluna. Apenas para ilustrar o poder desta abordagem, considere esta equação ligeiramente mais complicada:

A função depende de três variáveis e está representada num espaço 4D. Não há forma de visualizarmos o seu aspeto. E só de olhar para a equação, é impossível dizer se a função tem um valor global


mínimo em direção ao qual podemos descer. Mas é possível escrever o gradiente usando as derivadas parciais. (Mais uma vez, não estamos a tentar descobrir como diferenciar exatamente a função em relação a cada variável; vamos assumir que se a função puder ser diferenciada, o cálculo dará uma resposta. Pode usar o Wolfram MathWorld para encontrar estas derivadas).

Agora, dado um conjunto de valores para , e , podemos avaliar o gradiente da função nesse ponto, dar um pequeno passo na direção oposta e atualizar os valores de , e . Se a função tiver um mínimo global ou mínimos locais, a iteração sobre este processo levar-nos-á até lá. A nossa análise também ligou os pontos entre dois conceitos importantes: funções, por um lado, e vectores, por outro. Tenha isto em mente. Estes campos aparentemente díspares da matemática - vectores, matrizes, álgebra linear, cálculo, probabilidade e estatística, e teoria da otimização (ainda não tocámos nos dois últimos) - vão juntar-se à medida que percebermos porque é que as máquinas aprendem.


LAMPEJOS DE UM NEURÓNIO


Bernard Widrow regressou da conferência sobre IA de 1956 em Dartmouth com, como ele disse, um macaco às costas: o desejo de construir uma máquina capaz de pensar. "Está sempre presente", disse-me ele mais de seis décadas depois. "Nunca o consegui tirar do meu sistema." No entanto, em 1956, o jovem Widrow era suficientemente inteligente para se aperceber da futilidade de construir máquinas pensantes e voltou-se para coisas mais práticas. A construção de um filtro adaptativo foi um desses objectivos.

No domínio do processamento de sinais, um filtro é algo que recebe um sinal de entrada, processa-o e produz um sinal de saída que tem determinadas propriedades desejadas. Digamos que está a trabalhar num equipamento eletrónico de lazer e precisa de medir um sinal. Mas misturado com o seu sinal está um zumbido irritante com uma frequência de 60 Hz . É a interferência da rede eléctrica AC. Um filtro pode pegar na entrada carregada de ruído, remover apenas o componente de 60 Hz e emitir um sinal limpo. Este tipo de filtro é fácil de conceber, uma vez que o ruído é bem conhecido; está sempre a 60 Hz . Mas muitas vezes, um filtro precisa de aprender as características do ruído; precisa de se adaptar.

Considere uma aplicação importante para um filtro adaptativo deste tipo: comunicações digitais. Qualquer pessoa que já tenha utilizado um modem de acesso telefónico para se ligar à Internet lembrar-se-á dos sons característicos emitidos pelo modem. Primeiro, um tom de marcação, depois os tons do número que está a ser marcado, seguidos de bipes e explosões de gritos agudos, e depois silêncio após cerca de vinte segundos. Este é o som de um aperto de mão: dois dispositivos digitais a descobrir a melhor forma de falarem um com o outro através de uma linha telefónica normalmente utilizada para sinais de voz analógicos. Os dispositivos digitais devem transmitir e receber fluxos de zeros e uns. Mas as linhas de transmissão analógicas podem ser ruidosas - por isso, é necessário um filtro para remover o ruído que pode corromper os dados. Isso inclui o cancelamento de qualquer eco que um modem possa ouvir de suas próprias transmissões. Mas é impossível construir um filtro genérico para esses fins. O ruído pode ser, e muitas vezes é, diferente em cada instância de dois dispositivos em comunicação. Parte do que acontece durante um aperto de mão é que um filtro adaptativo em cada extremidade descobre as características do ruído, que pode então remover para criar um canal de comunicação quase livre de erros. (Widrow lembra-se de ter usado um fax que emitia estes sons de "aperto de mão" quando comunicava com um fax remoto; o seu neto, que por acaso estava perto dele nessa altura, começou a chamar aos sons do aperto de mão "música do avô").

Uma conceção de um filtro adaptativo é mostrada abaixo.

Aqui, é o sinal de entrada; representa a saída correspondente. O filtro transforma em . A saída é comparada com um sinal desejado ,


que é o sinal que o filtro deveria ter produzido. Qualquer discrepância entre e resulta num erro en.

Este erro é introduzido de novo no filtro. Um filtro adaptativo modifica-se de forma a minimizar o erro. A caixa preta chamada FILTRO tem algumas características, ou parâmetros, e esses parâmetros podem ser ajustados para tornar o filtro adaptativo.

Poderá dizer-se que, se se conhece o sinal pretendido, para que serve um filtro? Bem, não se sabe o sinal desejado para qualquer entrada genérica. Mas há maneiras de saber o que o filtro deve produzir para entradas conhecidas. Por exemplo, é isso que os modems fazem durante o aperto de mão: Eles transmitem um sinal previamente acordado, para que o outro lado saiba o que esperar. Esse é o sinal desejado . Mas o sinal chega por uma linha de transmissão ruidosa, então a entrada é simplesmente contaminada por ruído. Mas, ao contrário do zumbido de 60 Hz que vimos anteriormente, este ruído é aleatório. O recetor precisa de um filtro que tome como entrada e produza um sinal que seja o mais próximo possível do sinal desejado . Para isso, o algoritmo deve aprender as propriedades estatísticas do ruído, de modo a poder prever o ruído em cada passo de tempo e subtraí-lo em tempo real de para produzir o sinal desejado.

Embora tudo isto esteja longe de ser IA e ML, podemos ver vislumbres de máquinas que aprendem. Esta ligação - em particular com o perceptron de Rosenblatt e os neurónios artificiais - tornar-se-á ainda mais óbvia quando escrevermos os pormenores de um filtro.

Widrow começou a aperceber-se disso lentamente, enquanto ainda estava no MIT, onde foi profundamente influenciado pelo decano do design de filtros, Norbert Wiener. Na altura, Wiener era o professor mais conhecido do MIT. Décadas mais tarde, Widrow, recordando a personalidade de Wiener num livro, pintou uma imagem particularmente evocativa de um homem cuja cabeça estava muitas vezes, literal e metaforicamente, "nas nuvens" quando andava pelos corredores dos edifícios do MIT: "Vimo-lo lá todos os dias, e ele tinha sempre um charuto. Andava pelo corredor, a fumar o charuto, e o charuto estava num ângulo de 45 graus acima do chão. E nunca olhava para onde estava a andar... Mas estava a fumar, com a cabeça envolta numa nuvem de fumo, e estava no esquecimento. Claro que estava a derivar equações". Mesmo quando se aproximava dos degraus no fim de um corredor, Wiener olhava para cima e não para baixo. "Vê-se que ele se vai matar - vai cair daqueles degraus - mas se o perturbarmos, podemos interromper a sua linha de pensamento e fazer a ciência recuar uns dez anos! Havia sempre esse problema".

Apesar destas decisões de vida ou de morte, Widrow adoptou o trabalho de Wiener. Enquanto esteve no MIT, chegou mesmo a criar diferentes versões do filtro adaptativo. Aqui está um exemplo de um dos seus projectos:

No filtro, o sinal de entrada chega discretamente uma vez a cada passo de tempo (que pode ser qualquer coisa: uma vez por dia, por segundo, por milissegundo, por microssegundo, e assim por diante), e é a saída correspondente. Cada caixa rotulada DELAY pega um sinal e o atrasa por um passo de tempo, produzindo o sinal de e de . Após um atraso, o sinal é multiplicado por um peso , após dois atrasos é multiplicado por , e assim por diante. O sinal sem atraso é multiplicado por w0. Todos estes são somados. Assim, para o nosso exemplo da página anterior, o sinal de saída pode ser escrito como:

Podemos tratar como o vetor , e como o vetor . Então,

O diagrama mostra apenas dois atrasos, mas, em princípio, pode haver qualquer número deles. Agora, se é o sinal desejado, veja como otimizar os parâmetros do filtro, para minimizar o erro entre o que ele gera, que é , e o sinal desejado, .

O que temos é uma expressão para o erro que o filtro comete no n-ésimo passo de tempo. É claro que se o filtro prevê uma boa aproximação do sinal desejado, então o erro será minimizado. Para conseguir isso, o filtro deve aprender o valor de a cada passo de tempo. Naturalmente, esse filtro pode atualizar os seus parâmetros sempre que a previsão estiver errada - daí o nome "filtro adaptativo". Ele aprende. Idealmente, ao longo do tempo, o erro médio cometido pelo filtro deve tender para zero. (Talvez agora as ligações à aprendizagem automática estejam a começar a emergir deste nevoeiro da teoria dos filtros).

Uma pequena digressão sobre o ML: Como é que devemos calcular o erro médio? A adição dos erros para calcular a média não é suficiente; como vimos anteriormente, os erros negativos e positivos podem anular-se mutuamente, dando uma impressão inválida de que o erro médio é baixo. Podemos somar o valor absoluto dos erros e calcular a média: chama-se a isto erro médio absoluto (MAE). Mas os matemáticos preferem tomar a média do quadrado dos termos de erro e chamar-lhe erro médio quadrático (MSE). Acontece que o MSE tem algumas propriedades estatísticas interessantes que o MAE não tem. Além disso, o MSE é diferenciável em todo o lado. (Uma função diferenciável é aquela que tem uma derivada em todo o seu domínio, onde um domínio pode ser, digamos, o plano xy). O MAE não é. Isso também ajuda muito, e veremos isso quando chegarmos ao treinamento de redes neurais. Vale a pena mencionar mais um facto: Se quisermos que a estimativa de erro castigue os valores extremos, o MSE faz isso melhor do que o MAE, porque a contribuição de um


O erro em relação à média aumenta com o quadrado do erro no MSE, enquanto aumenta linearmente no MAE.

De volta ao filtro. Elevamos o erro ao quadrado em cada passo de tempo, adicionamos todos os erros ao quadrado e, em seguida, encontramos o valor esperado. O valor esperado, ou "expetativa", de algo que está variando aleatoriamente tem um significado muito específico na teoria da probabilidade, mas não vamos nos preocupar com isso. O principal insight aqui é que precisamos minimizar o valor esperado dos erros ao quadrado. Vamos chamar esse valor de :

O valor de deve ser minimizado. Se olharmos para a forma da equação que relaciona com o parâmetro de filtro , torna-se claro que a função que liga os dois será quadrática (ou seja, envolverá a segunda potência de ). Já vimos que tais funções quadráticas são convexas ( , ou , por exemplo). Assim, quando é minimizada, acabamos por chegar à base de uma função em forma de taça. Neste ponto, o declive, ou gradiente, de é zero. Isto dá-nos outra forma de encontrar o valor ótimo para . Podemos simplesmente definir o valor do gradiente de em relação a como zero e resolver a equação:

Em 1931, Wiener e o matemático alemão Eberhard Hopf conceberam uma forma de resolver essas equações, utilizando técnicas de álgebra linear. Mas isso requer algum conhecimento a priori sobre a correlação entre as entradas em todos os vários passos de tempo e a correlação entre as entradas e as


resultados desejados. Isto nem sempre é conhecido e, mesmo quando é, os cálculos podem ser computacionalmente intensivos. Além disso, o trabalho de Wiener aplicou-se a filtros analógicos.

Também podemos minimizar utilizando o método da descida mais íngreme. Porquê? Bem, por ser uma função convexa em forma de tigela, podemos sempre encontrar o valor para que minimiza o valor esperado dos erros ao quadrado, seguindo iterativamente um caminho até o fundo da tigela. Assim, independentemente do facto de o filtro ser caracterizado por um coeficiente ( ), dois ( ), três ( , ou mais, a afirmação é válida. A descida mais íngreme permite-lhe encontrar o mínimo. Mas este método também tem uma limitação: Precisamos de ser capazes de calcular as derivadas parciais de em relação aos coeficientes do filtro.

Existem outras preocupações de carácter computacional.

Por exemplo, dado xn e o correspondente , mais a saída desejada , pode-se usar o método da descida mais íngreme para calcular os parâmetros (no nosso exemplo: ). O problema é que, para encontrar os valores óptimos para os parâmetros, são necessárias cada vez mais amostras de entrada, saída e saída desejada, e estes cálculos demoram cada vez mais tempo a terminar.

Além disso, dado que o erro calculado para uma determinada amostra de dados não representa totalmente todos os erros possíveis, o gradiente que calcula em cada passo de tempo para ir em direção ao mínimo é apenas uma aproximação. Por vezes, está a apontar na direção certa, mas na maioria das vezes não está. Na nossa analogia de descer uma encosta em socalcos até à aldeia, é como se, para além de ter de navegar no escuro, estivesse um pouco embriagado. Em vez de seguirmos o caminho mais íngreme para o terraço seguinte, descemos a cambalear. Pode até subir-se ao terraço seguinte. A esperança é que, se der passos pequenos o suficiente, mesmo esta caminhada de bêbado o leve até à aldeia. E, na prática, os algoritmos que fazem isto são efetivamente bem sucedidos. Este método é designado por descida de gradiente estocástica (SGD), em que a palavra "estocástica" se refere ao facto de a direção de cada passo da descida ser ligeiramente aleatória.

Era nisto que Widrow estava a trabalhar no MIT, antes de se mudar para Stanford. Mas, para além dos filtros, ele estava a pensar em neurónios adaptativos, ou


elementos neurais, e apercebendo-se de que treinar um neurónio não era diferente de treinar um filtro.


UM FIM-DE-SEMANA COM BERNIE


Quando Ted Hoff entrou no gabinete de Widrow em Stanford, naquele fatídico dia do outono de 1959, Widrow começou a discutir essas ideias com ele. "Eu estava no quadro negro a explicar ao Ted o gradiente estocástico e a taça quadrática... e os filtros adaptativos e os elementos neurais adaptativos e... a falar sobre a forma de diferenciar para obter os componentes do gradiente", contou-me Widrow. "Não sei como aconteceu, mas tivemos a ideia de que podíamos obter um gradiente estocástico, um gradiente muito grosseiro, algebricamente - sem diferenciar nada, sem calcular a média de nada e sem elevar nada ao quadrado."

A técnica que conceberam pode ser aplicada a filtros adaptativos ou a neurónios artificiais. Até agora, aprendemos que a saída do nosso filtro adaptativo de exemplo é dada por:

Projetar um filtro que se adapta envolve aprender os valores de , e w2. Se nos lembrarmos do perceptron de Rosenblatt, veremos que também envolve a aprendizagem dos pesos para que possa classificar corretamente um novo dado como estando num ou noutro lado de um hiperplano. O algoritmo de Rosenblatt não é apresentado em termos de descida de gradiente. Mas o algoritmo de Widrow e Hoff é.

A figura abaixo mostra uma forma de pensar sobre o neurónio adaptativo concebido por Widrow e Hoff.

O neurónio produz uma saída :

Aqui, é sempre 1 ; isto faz com que seja o nosso termo de polarização, . As entradas reais são e . Em conjunto, constituem o vetor . O conjunto dos coeficientes , e é o vetor . Assim:

Suponha que tem várias amostras de treino para as quais tem as entradas e as correspondentes saídas desejadas (d). Então, o erro cometido pelo neurónio adaptativo para cada entrada é dado por:

Considere o problema em que a entrada é um conjunto de 16 valores, representando uma grelha de pixéis. Estes pixéis podem ser usados para mostrar letras do alfabeto. A letra "T", por exemplo, iluminaria alguns desses pixéis (ou seja, alguns pixéis teriam o valor "1" e outros "0"). A letra "J" iluminaria um conjunto diferente de pixéis.


Digamos que quando o conjunto de pixels que representam a letra "T" é a entrada do neurónio, este deve produzir o valor 1. E quando a entrada é o conjunto de valores de pixels que representam a letra "J", o neurónio deve produzir -1 . Assim, a saída desejada para "T" é 1 , e para "J" é -1 .

O treino do neurónio envolve fornecer-lhe uma entrada, representando uma letra, de cada vez. O algoritmo usa a entrada e a saída desejada para ajustar os seus pesos e gerar a saída correcta. Mas alterar os pesos para obter a saída correcta para a letra "T" pode fazer com que o neurónio cometa um erro para a letra "J". Se for esse o caso, o algoritmo ajusta novamente os seus pesos. Claro que agora os novos pesos podem causar um erro para a letra "T". Repete-se o processo. E isto continua até o neurónio produzir corretamente 1 para a letra "T" e -1 para a letra "J". O método da descida mais íngreme pode ser usado para treinar o neurónio.

Digamos que temos um conjunto de amostras de treinamento: entradas e suas saídas correspondentes. Se calcularmos os erros cometidos pelo neurónio para todas as amostras de entrada e traçarmos o valor esperado dos erros ao quadrado em função de todos os pesos, ou coeficientes, obtemos uma função em forma de taça (evidentemente, num espaço de dimensão superior que não podemos visualizar). Depois, pode minimizar o valor esperado utilizando o método da descida mais íngreme. Em cada passo, calcula-se o gradiente da função em relação a cada peso e, em seguida, modifica-se os pesos dando um pequeno passo na direção oposta (em direção ao mínimo).
 onde:

Recorde-se da nossa discussão anterior que o gradiente é simplesmente um vetor em que cada elemento é a derivada parcial do erro quadrático médio, , em relação a cada peso.

Assim, para os nossos três pesos, o gradiente é:

Cada elemento deste vetor será uma expressão analítica que pode ser calculada utilizando as regras do cálculo. Quando tiver as expressões, basta introduzir os valores actuais dos pesos e obter o gradiente, que pode ser utilizado para calcular os novos pesos. O problema: é preciso cálculo e, embora o nosso gradiente tenha apenas três elementos, na prática, pode ter elementos que chegam às dezenas, centenas, milhares ou até mais. Widrow e Hoff estavam à procura de algo mais simples. Foi isto que eles criaram:

Em vez de calcularem todo o gradiente, decidiram calcular apenas uma estimativa do mesmo. A estimativa basear-se-ia apenas num ponto de dados. Não se tratava de calcular o valor esperado do erro ao quadrado. Em vez disso, estavam simplesmente a estimá-lo. Mas estimar um parâmetro estatístico com base em apenas uma amostra é geralmente um anátema. Mesmo assim, Widrow e Hoff foram


com ele. Com um pouco de análise, chegaram à sua regra de atualização para os pesos:
 onde:
  tamanho do passo

erro baseado num ponto de dados

o vetor que representa um único ponto de dados

O erro em si é dado por:

Trata-se de álgebra simples. Basicamente, para cada entrada, calcula-se o erro e utiliza-se esse valor para atualizar os pesos.

Widrow e Hoff estavam cientes de que o seu método era extremamente aproximado. "O que fazemos é pegar no valor único do erro, elevá-lo ao quadrado, engolir com força, porque vamos dizer uma mentira, [e] dizemos que esse é o erro médio quadrático", disse-me Widrow. "É uma versão bastante ruidosa da média do quadrado do erro. E depois, quando se tomam as derivadas, é possível fazê-lo analiticamente, sem diferenciar. Não é preciso elevar nada ao quadrado. Não é preciso calcular a média de nada. Temos um gradiente extremamente ruidoso. Dá-se um pequeno passo, outro pequeno passo, outro pequeno passo".

E, no entanto, o algoritmo aproxima-o do mínimo da função. O algoritmo passou a chamar-se algoritmo dos mínimos quadrados médios (LMS). Num vídeo que Widrow carregou em 2012, para explicar o algoritmo, atribuiu a um dos seus alunos de pós-graduação o nome do algoritmo, mas não se lembra do nome do aluno.


nome do aluno. Espero que toda esta álgebra não tenha criado demasiado mistério. É tudo muito simples quando nos habituamos a ela. Mas, a não ser que se veja a álgebra, nunca se acreditaria que estes algoritmos pudessem realmente funcionar. O mais engraçado é que funcionam. O algoritmo LMS é utilizado em filtros adaptativos. São filtros digitais que podem ser treinados... Todos os modems do mundo usam alguma forma do algoritmo LMS. Por isso, este é o algoritmo adaptativo mais utilizado no planeta".

O algoritmo LMS não só seria utilizado no processamento de sinais, como também se tornaria o primeiro algoritmo de treino de um neurónio artificial que utilizava uma aproximação do método da descida mais íngreme. Para contextualizar: Atualmente, todas as redes neuronais profundas - com milhões, milhares de milhões, possivelmente triliões de pesos - utilizam alguma forma de descida de gradiente para o treino. Seria um longo caminho desde o algoritmo LMS até aos algoritmos modernos que alimentam a IA, mas Widrow e Hoff tinham colocado uma das primeiras pedras no caminho.

Naquela tarde de sexta-feira, no outono de 1959, no entanto, tudo o que tinham eram rabiscos matematicamente motivados num quadro negro. Widrow e Hoff não sabiam se o algoritmo funcionaria. Precisavam de o simular num computador; estavam entusiasmados por terem descoberto algo extremamente importante. "Eu estava a pensar: 'Descobrimos o segredo da vida'", contou Widrow.

Do outro lado do corredor do seu gabinete havia um computador analógico, uma prenda da Lockheed para Stanford. A porta estava aberta e qualquer pessoa podia usar o computador. Programá-lo era como operar uma central telefónica à moda antiga: Tirar um fio de um painel de ligação aqui, ligá-lo ali, e assim por diante. Em meia hora, Hoff tinha o algoritmo a funcionar na máquina analógica. "Ele fê-lo funcionar", disse Widrow. "Não sei como é que ele sabia como o fazer. Ele sabia como programar aquela coisa".

Tendo verificado que o algoritmo funcionava, os dois tinham como próximo passo a construção de um único neurónio adaptativo - um neurónio de hardware real. Mas já era fim de tarde. A sala de aprovisionamento de Stanford estava fechada para o fim de semana. "Bem, não íamos ficar à espera", disse-me Widrow. Na manhã seguinte, os dois foram à Zack Electronics, no centro de Palo Alto, e compraram todas as peças de que precisavam. De seguida, foram até ao apartamento de Hoff


e trabalharam todo o sábado e a maior parte da manhã de domingo. No domingo à tarde, tinham-no a funcionar. "Na segunda-feira de manhã, tinha-a na minha secretária", recorda Widrow. "Podia convidar pessoas e mostrar-lhes uma máquina que aprende. Chamámos-lhe ADALINE - "neurónio linear adaptável". Não era um filtro adaptativo, mas um neurónio adaptativo que aprendia a ser um bom neurónio."

O que o ADALINE faz, usando o algoritmo LMS, é separar um espaço de entrada (digamos, o espaço de 16 dimensões definido por , ou 16 , pixéis) em duas regiões. Numa região estão os vectores 16 -dimensionais, ou pontos que representam, digamos, a letra "T". Noutra região estão os vectores que representam a letra "J". Widrow e Hoff escolheram píxeis para representar as letras, pois era suficientemente grande para mostrar claramente as diferentes letras, mas suficientemente pequeno para trabalhar, dado que tinham de ajustar os pesos à mão (usando botões). Se fosse maior, teriam passado a maior parte do tempo a mexer nos botões. Mais uma vez, aqui estão as letras "T" e "J" no espaço de pixel:


Assim, cada letra é representada por 16 dígitos binários, cada um dos quais pode ser 0 ou 1 . Se imaginássemos representar estas letras como pontos num espaço de 16 D, então "J" seria um ponto (vetor) numa parte do espaço de coordenadas e "T" noutra. O algoritmo LMS ajuda o ADALINE a encontrar os pesos que representam o hiperplano linearmente separador - neste caso, um plano em quinze dimensões - que divide o espaço de entrada em dois. É exatamente o que faz o perceptron de Rosenblatt, utilizando um algoritmo diferente.