Aprendizado profundo com capacidade computacional reduzida

Diogo Felipe Félix de Melo

Aprendizado profundo com capacidadecomputacional reduzida: uma aplicação à

quebra de CAPTCHAs.

Recife

Julho de 2018

Diogo Felipe Félix de Melo

Aprendizado profundo com capacidade computacionalreduzida: uma aplicação à quebra de CAPTCHAs.

Monografia apresentada ao Curso de Bachare-lado em Ciências da Camputação da Univer-sidade Federal Rural de Pernambuco, comorequisito parcial para obtenção do título deBacharel em Ciências da Camputação.

Universidade Federal Rural de Pernambuco – UFRPE

Departamento de Computação

Bacharelado em Ciências da Camputação

Orientador: Pablo de Azevedo Sampaio

RecifeJulho de 2018

Agradecimentos

Meus pais, familiares e amigos.

Ao meu orientador, por toda a paciência e dedicação.

ResumoNa última década, Redes Neurais Profundas tem se mostrado uma poderosa técnica deaprendizado de máquina. Em geral, essas técnicas demandam alto poder computacionale grandes volumes de dados para obter resultados expressivos, o que pode ser um fatorlimitante em algumas realidades. Entretanto, o projeto cuidadoso da arquitetura e do treinopodem ajudar a reduzir estes requisitos. Neste trabalho apresentamos uma abordagemcomparativa para a aplicação de redes neurais profundas à quebra de CAPTCHAs de textocomo uma forma de contornar essas limitações. Estudamos modelos capazes de aprender asegmentar e identificar o texto contido em imagens baseando-se apenas em exemplos. Apartir da experimentação de diferentes hiper-parâmetros e arquiteturas, fomos capazes deobter um modelo final com acurácia de 96.06% de acerto por token em aproximadamente3 horas de treino executado em um simples computador pessoal.

Palavras-chave: Aprendizado de Maquina, Aprendizado Profundo, CAPTCHA.

AbstractDuring the last decade, Deep Neural Networks has been shown to be a powerfull ma-chine learn technique. Generally, to obtain relevant results, these techniques require highcomputacional power and large volumes of data, which can be a limiting factor on somecases. Neverthless, a careful project of trainig and archtecture may help to reduce theserequirements. In the this work we present a comparative approach to the application ofdeep neural networks to text based CAPTCHAs as a way to cope with these limitations.We studied models that are capable of learn to segment and identify the text content ofimages, only based on examples. By experimentation of different hiper-parameters andarchitectures, we were capable to obtain a final model with 96.06% of token predictionaccuracy in approximately 3 hours of training in a simple personal computer.

Keywords: Machine Learning, Deep Learning, CAPTCHA.

Lista de ilustrações

Figura 1 – Diferentes tipos de CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . 15Figura 2 – Diferentes CPATCHAs de texto em uso por instituições brasileiras. . . 18Figura 3 – Imagem ilustrativa das possíveis projeções aprendidas em uma camada

(a) densa e (b) convolucional em um problema de reconhecimento defaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Figura 4 – Exemplo esquemático da execução da operação de convolução em umcanal do tensor de entrada x. . . . . . . . . . . . . . . . . . . . . . . . 24

Figura 5 – Exemplo de comportamento característico da função de custo duranteo aprendizado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Figura 6 – Exemplo ilustrativo de overfitting e underfitting. . . . . . . . . . . . . . 28Figura 7 – Exemplos de CAPTCHAs gerados e seus respectivos tokens. . . . . . . 40Figura 8 – Dinâmica inicial de arquiteturas selecionadas. . . . . . . . . . . . . . . 46Figura 9 – Dinâmica da arquitetura C6C12C36C36Fl100MD. . . . . . . . . . . . . . 50

Lista de tabelas

Tabela 1 – Comparação entre os requisitos dos modelos encontrados na literatura. 32Tabela 2 – Arquitetura M [D] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Tabela 3 – Arquitetura C6M [D] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Tabela 4 – Arquitetura C6C12M [D] . . . . . . . . . . . . . . . . . . . . . . . . . . 37Tabela 5 – Arquitetura C6C12Fl100M [D] . . . . . . . . . . . . . . . . . . . . . . . 38Tabela 6 – Arquitetura C6C12C36C36M [D] . . . . . . . . . . . . . . . . . . . . . . 38Tabela 7 – Arquitetura C6C12C36C36Fl100M [D] . . . . . . . . . . . . . . . . . . . 39Tabela 8 – Comparação do tempo de treino entre as arquiteturas. . . . . . . . . . 44Tabela 9 – Comparação entre as arquiteturas na décima época. . . . . . . . . . . . 47

Lista de abreviaturas e siglas

CAPTCHA Completely Automated Public Turing tests to tell Computers and Hu-mans Apart. Testes automatizados de Turing para diferenciar humanose computadores.

OCR Optical Character Recognition. Reconhecimento do caractere em umaimagem.

RGB Red-Green-Blue. Canais de codificação de cores.

RAM Random Access Memory. Memória de Acesso Aleatório.

HIP Human Interaction Proofs. Provas de interação humana.

Lista de símbolos

i, j, k, . . . Índices.

I, J , K, . . . Conjunto de todos os valores dos índices i, j, k, . . .. κ = (I, J,K, . . .)é uma coleção de índices.

x Um vetor.

xi Coordenada i do vetor x.

Tκ Um tensor com índices na coleção κ. O tamanho da coleção define oranque do tensor. Sendo ranque 1 vetores, 2 matrizes, etc. Quandodefinido no contexto, omitiremos κ.

Ti,j,k,... O elemento i, j, k, . . . do tensor T.

{. . .} Conjunto de todas as possibilidades de um variável. Usualmente umespaço vetorial.

〈. . .〉D Valor esperado de uma variável no conjunto D.

|D| Número de elementos no conjunto D.

|T|p Norma p do tensor T. Quando omitido, p = 2 (norma euclidiana).

∇T Operador gradiente com respeito ao tensor T. Isto é, as derivadas emcada elemento de T.

< Conjunto dos números reais.

<κ Espaço dos tensores de ranque Tκ sob o conjunto dos números reais.Isto é, Ti,j,k,... ∈ <.

<κdb0, 1ce Compacto dos tensores Tκ sob o conjunto [a, b], com a, b ∈ <.

2D Conjunto de todos os subconjuntos de D.

x Variável aleatória.

P (x = a) Probabilidade do evento x = a ocorrer. Quando estiver claro no contexto,utilizamos apenas P (a)

Sumário

Lista de ilustrações . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 CAPTCHAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.1 CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Captchas de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 REDES NEURAIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Camadas Densas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Camadas Convolucionais . . . . . . . . . . . . . . . . . . . . . . . . . 213.4 Aprendizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.5 Regularização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.6 Redes Neurais e CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . . 29

4 MODELAGEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.1 Abordagem Comparativa . . . . . . . . . . . . . . . . . . . . . . . . . 334.2 Camadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.3 Arquiteturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5 METODOLOGIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.1 Geração dos CAPTCHAs . . . . . . . . . . . . . . . . . . . . . . . . . 405.2 Treino e Validação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.3 Métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6 RESULTADOS E DISCUSSÃO . . . . . . . . . . . . . . . . . . . . . 446.1 Experimentos Preliminares . . . . . . . . . . . . . . . . . . . . . . . . 446.2 Treino completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.3 Discussão do Método . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

7 CONCLUSÕES E TRABALHOS FUTUROS . . . . . . . . . . . . . 527.1 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.2 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

A CONFIGURAÇÕES COM lr = 10−3 e 10−4 NA DÉCIMA ÉPOCA. . 57

B DESCRIÇÃO COMPLETA DAS ARQUITETURAS. . . . . . . . . . 59

12

1 Introdução

Algoritmos de aprendizado baseados em neurologia são conhecidos desde meadosdo século passado (1). Das proposições iniciais até os dias de hoje, essa classe de modelostem evoluído em complexidade e técnicas de forma contínua, culminando em um altopoder de expressividade e níveis cada vez mais abstratos de representação (ver (2) ou (3)para uma breve revisão histórica). Os poucos resultados teóricos disponíveis demonstramque redes neurais possuem um alto poder de generalização, sendo capazes de, sob certascircunstâncias, codificar diversas classes de funções (4, 5). Apesar dos avanços na área,foi apenas recentemente que modelos neurais começaram a redefinir o estado da arte,superando outras classes de algoritmos de aprendizado de máquina (6) e até mesmoalcançando performances sobre-humanas (7). Á estes modelos propostos mais recentementeé comum a denominação de redes neurais de aprendizado profundo. Tais avanços forampossíveis devido a três fatores chaves: a viabilização de bases de dados cada vez maiores, oaumento do poder computacional e o desenvolvimento de novas arquiteturas e técnicas detreino.

A crescente melhoria de performance dos modelos neurais de aprendizado profundotem motivado estudos em áreas onde é preciso distinguir computadores e humanos. Dentreessas áreas temos os CAPTCHAs (8) (do inglês Completely Automated Public Turing teststo tell Computers and Humans Apart) ou HIPs (9) (do inglês Human Interaction Proofs),que definem uma coleção de técnicas que tem como objetivo bloquear a ação de agentesautônomos na rede mundial de computadores. Um dos subconjuntos mais conhecidosdessas técnicas talvez seja o de CAPTCHAs baseados em texto (10). Nesse tipo de desafio,uma imagem contendo uma sequência de caracteres é exibida e a validação é feita pelacomparação entre o texto informado pelo usuário e a resposta correta. Formulado comoum problema de aprendizado de máquina, desejamos descobrir de forma automatizadaum mapa entre a imagem e o texto codificado. Na versão informada do problema, umser humano escolhe previamente técnicas de preprocessamento (filtros, segmentação decaracteres, etc.) antes que o aprendizado propriamente dito ocorra. Ajudados por humanos,redes neurais simples e com poucos exemplos conseguem resultados satisfatórios nessetipo de desafio (9). De fato, mesmo técnicas ingênuas como contagem de pixels podemobter bons resultados quando o preprocessamento correto é fornecido (11). Na versão nãoinformada, entretanto, encontrar mapas imagem-texto de forma automatizada é usualmentemuito mais desafiador. Em trabalhos recentes, foram relatados modelos baseados em redesneurais capazes de burlar esse tipo de desafio com acurácias de acerto próximos à humanaem sequências sorteadas a partir de um repositório (12) e modelos com alta eficiência dedados (13). Para o problema geral de quebrar CAPTCHAs baseados em texto, entretanto,

Capítulo 1. Introdução 13

modelos de aprendizado profundo ainda mostram desempenho inferior ao humano. Contudo,pesquisas recentes apontam para avanços claros nos próximos anos (14). Em comum, essesmodelos possuem a necessidade de clusters e/ou sistemas de computação sob demandapara treinamento, com hardware de alto poder de processamento e/ou paralelização, comoGPUs e TPUs. Adicionalmente, as bases de treinamento necessárias comumente alcançamalguns terabytes e envolvem grandes operações de aquisição e/ou geração.

Neste trabalho propomos uma abordagem comparativa entre diferentes arquiteturasde redes neurais para a solução de CAPTCHAs baseados em texto sem informaçãohumana, nos restringindo, entretanto, à um ambiente com poder computacional reduzido.Pretendemos mostrar que é possível fazer uso dessas técnicas em um mero computadorpessoal (na contramão dos trabalhos usualmente encontrados na literatura) e ainda obterresultados próximos ao estado da arte. Este trabalho se encontra organizado como segue.No capítulo 2 apresentamos uma breve introdução à diferentes tipos de CAPTCHAs,com ênfase em desafios baseados em texto. Sequencialmente, no capítulo 3, arquiteturase técnicas de projeto e treino de redes neurais comuns na literatura são abordados, osprincipais resultados do uso dessas técnicas em CAPTCHAs de texto explorados e nossasconsiderações iniciais sobre essa aplicação apresentadas. No capítulo 4 uma descriçãodas arquiteturas dos modelos usados neste estudo é feita em conjunto com uma brevefundamentação para as escolhas. No capítulo 5, detalhes dos experimentos realizados sãoformalizados. Por fim, no capítulo 6 os resultados dos experimentos são apresentados eanalisados e no capítulo 7 nossas conclusões e considerações finais apresentadas.

14

2 CAPTCHAs

Neste capítulo abordaremos como funcionam os principais tipos de CAPTCHAconhecidos. Daremos um enfoque especial aos CAPTCHAs baseados em texto, objeto deestudo do presente trabalho. Na secção 2.2 daremos uma definição mais precisa para esteHIP em particular.

2.1 CAPTCHAsCAPTCHAs (8) ou HIP (9), são um conjunto de técnicas que tem como objetivo

discernir a ação automatizada de robôs da ação de seres humanos na Rede Mundialde Computadores. Esses filtros tem sido usados de forma efetiva na defesa de diversostipos de ataque: proteger informações sensíveis, como e-mail e dados pessoais; impedirtentativas de login automatizados; coibir acesso massivo à sistemas de bases de dados;entre outros. Entretanto, desde as primeiras aplicações até os dias de hoje, existe umacorrida co-evolucionária entre atacantes e defensores. Por um lado, algoritmos de ’quebra’de CAPTCHA se tornam cada vez mais sofisticados e precisos. Por outro lado, filtrosmais complexos são desenvolvidos. Contudo, como explicado por Chellapilla Et al. (9),existe um balanço entre complexidade e factibilidade que os defensores devem buscar,explorando habilidades em que humanos ainda não foram ultrapassados por máquinas. Oautor também estima que os requisitos mínimos de um HIP para ser considerado efetivo éser solúvel por humanos 90% das vezes e é considerado ’quebrado’ se puder ser enganadopor robôs em mais do que 1% das tentativas, sendo esses valores dependentes do custo derepetição do ataque.

De forma geral, esses filtros podem ser formulados como um desafio sobre umconjunto de domínio cuja a resposta é um token. O domínio pode ser um trecho de áudio,uma sequencia de imagens ou até mesmo o histórico de navegação do desafiado. O tokenpode ser constituído de um conjunto de ações, o texto extraído de um áudio ou imagem, oupossuir um histórico de navegação confiável. Podem ainda ser constituídos de uma únicaetapa ou de varias. Uma categorização dos tipos de CAPTCHA pode ser encontrado em(15). Na figura 1 podemos ver diferentes tipos de CAPTCHAs gerados com a biblioteca decódigo aberto Securimage (16).

O processo de ’quebra’ envolve duas ideias principais: explorar vulnerabilidadese/ou uso de algoritmos inteligentes. Por serem testes automatizados, CAPTCHAs geral-mente apresentam algum padrão de comportamento ou falha de projeto. A padronizaçãona geração de desafios pode permitir que um atacante desenvolva heurísticas de ataque.Imagens com mesmo espaçamento de caracteres ou padrões repetitivos podem ser explora-

Capítulo 2. CAPTCHAs 15

Figura 1 – Diferentes tipos de CAPTCHAs

(a) Letras (b) Desafio matemático

(c) Duas palavras (d) Áudio

(a) O desafiado deve reconhecer corretamente um texto formado por caracteres não correla-cionados. (b) O desafio consiste em extrair e resolver corretamente um problema simples deálgebra. (c) Identificar palavras sorteadas de um repositório. (d) O desafio consiste com extraircorretamente um conjunto de símbolos codificados em áudio. Todos os exemplos foram geradospelo autor utilizando a biblioteca Securimage. O espectro de intensidades em (d) foi gerado peloautor a partir do áudio de um CAPTCHA gerado pela biblioteca.

dos e facilitar a segmentação da imagem, como foi explorado por (11). Falhas ou viesesno projeto desses métodos também podem expor brechas. Quanto ao uso de algoritmosinteligentes, redes neurais recebem um lugar de destaque devido a flexibilidade e capacidadede generalização que esses modelos conseguem alcançar. O uso dessa classe de algoritmosfoi a abordagem escolhida por (12) e (9), por exemplo. Redes neurais são exploradas nocapítulo 3.

Ao longo dos anos os domínio e os desafios tem evoluído em complexidade, namedida que os atacantes evoluem em técnicas de ataque. Um exemplo da co-evoluçãodesses sistemas é a forma como o sistema reCaptcha (17) tem mudado ao longo dos anos.Quando proposto, o sistema era baseado em trechos de livros e jornais antigos em queos melhores algoritmos conhecidos à época falharam em uma tarefa de OCR (do inglêsoptical character recognition). Trechos que não haviam sido corretamente identificados(teste) eram separados e exibidos para humanos juntamente com imagens de trechosonde o reconhecimento havia falhado (controle). Teste e controle eram comparados paracertificar a atuação humana. Quando proposto, os autores alegaram que humanos seriamcapazes de resolver o desafio em quase todos os casos e que comutadores teriam chance


quase nula de passarem desapercebidos, já que o repositório de exemplos era compostapor imagens em que as técnicas vigentes à época haviam falhado. Porém, poucos anosdepois, avanços em técnicas de OCR baseadas em redes neurais obtiveram 99% de precisãona base de palavras utilizada por esse sistema (12), inviabilizando o uso dessa técnicae forçando o reCaptcha a evoluir para uma segunda versão. Nessa nova abordagem, osdados de navegação dos usuários são analisados por um algoritmo de risco. Caso umapontuação mínima seja atingida, o usuário é considerado humano, caso contrário, é expostoa problemas conhecidamente difíceis para computadores, como reconhecimento de objetos,contextualização de imagens e busca de similaridades, combinados com diferentes açõesque devem ser performadas pelo usuário. Entretanto, Sivakorn Et al. (18) mostraram queexplorando-se os critérios de avaliação de risco, seria possível enganar o sistema em 85%das vezes, forçando a constante atualização dos desafios.

2.2 Captchas de textoNos CAPTCHAs baseados em texto, uma imagem contendo uma sequência de

caracteres é exibida ao desafiado. O teste consiste em conseguir recuperar corretamenteo texto codificado na imagem. Matematicamente, uma imagem com altura A, largura Le C canais pode ser representada como um tensor X ∈ <A,L,C [0, 1], de modo que Xijk

representa a intensidade do pixel na posição (i, j) canal k. Um token é uma sequencia usob um alfabeto de símbolos Σ, podendo o comprimento da sequência ser limitado ou não.Assim, ’quebrar ’ um CAPTCHA de texo é encontrar um mapa f(X)→ u que obtenha umataxa de acerto maior do que 1% como comentado na seção 2.1. Um sistema de CAPTCHAtorna-se completamente inútil se não conseguir diferenciar humanos de robores.

Quanto à imagem, usualmente são utilizadas adição de ruído, linhas e/ou grades paradificultar o processo de segmentação de caracteres, bem como efeitos de distorção, corrosãoe/ou dilatação, e transformações geométricas como rotação e translação, entre outros. Emdesafios mais simplórios, o número de canais pode ser reduzido, podendo a imagem serrepresentada como em tons de cinza. Em desafios mais complexos, o espaços de canais éexplorado, aumentando algebricamente as possibilidades representação, mantendo, todavia,a factibilidade do desafio para seres humanos, dada nossa facilidade em distinguir cores1.É possível explorar imagens sintéticas, geradas de forma automatizada por computadores,ou imagens naturais, como paisagens ou textos em fotos reais.

Quanto ao texto, diferentes complexidades podem ser adicionadas. Fixadas asdemais variáveis, a dificuldade do desafio é usualmente proporcional ao tamanho de1 Nem sempre esta afirmação é verdadeira. De fato, pessoas que sofrem da Síndrome de Dalton, o

Daltoninsmo, podem ter dificuldades em resolver desafios que explorem diferentes cores. O balançoentre complexidade e inclusão de pessoas com necessidades especiais ainda é uma questão em abertono projeto de CAPTCHAs.


alfabeto escolhido. Dentre os mais simples, o conjunto dos números Σ = 0123456789 possuiapenas dez símbolos. No outro extremo, os logogramas chineses constituem alfabetos comum número indeterminado de símbolos, com as representações mais usuais se limitandoa algo em torno de 3000 caracteres. A tipografia também interfere na dificuldade deresolver um CAPTCHA. Para o mesmo alfabeto Σ existem diferentes possibilidades derepresentação gráfica dos seus caracteres. Fontes regulares tendem a fornecer representaçõesmais simples, com a desvantagem de serem facilmente reconhecíveis por OCR. No outroextremo, fontes simbólicas e caracteres escritos à mão podem representar um grandedesafio para máquinas. Quando os símbolos são sorteados de forma aleatória, humanose máquinas, tipicamente, presenciam maiores dificuldades, dado que cada entrada deveser reconhecida separadamente (errar o reconhecimento um símbolo significa uma falhacompleta). Quando sorteamos palavras a partir de um repositório, o desafio se tornamais amigável para humanos, primeiro por termos uma facilidade maior em reconhecerpadrões do que especifidades e segundo por nos permitir o uso indireto de outras fontesde conhecimento para a solução do problema. Se soubermos que os textos estão emPortuguês, por exemplo, podemos esperar que nenhuma palavra conterá uma subsequênciatt (gramaticalmente incorreto) ou que uma vogal será, provavelmente, seguida por umaconsoante ou por uma vogal diferente (padrão mais frequente na língua). Entretanto,quando o repositório de palavras é exposto, atacantes podem desenvolver heurísticas paraexplorar o problema, como um dicionário de palavras ou correção gramatical para aprimorara eficiência das técnicas. Além disso, repositórios de palavras induzem correlações entre oscaracteres, o que limita bastante o espaço de possíveis tokens. Ver (19) para um apanhadode CAPTCHAs de texto utilizados pelo mundo e (10) para uma a evolução desses sistemasao longo dos anos. Na figura 2 temos alguns exemplos utilizados por instituições brasileiras.


Figura 2 – Diferentes CPATCHAs de texto em uso por instituições brasileiras.

(a) Banco Central do Brasil (b) Instituto Nacional do Seguro Social (INSS)

(c) Banco Itaú (d) Ministério da Educação (MEC)

(e) Ministério Público do Estado do Rio deJaneiro (MPRJ)

(f) Tribunal de Justiça do Estado de Pernam-buco (TJPE)

(a) Disponível em: <https://www3.bcb.gov.br/faleconosco/#/login/consultar>. Acesso em:23/06/201. (b) Disponível em: <https://cadsenha.inss.gov.br/cadsenha-internet-web/faces/pages/segurado/entradaNitNb.xhtml>. Acesso em: 23/06/201. (c) Disponível em:<https://bankline.itau.com.br/boletos-novosite/simulador_etapas_boletos_02.htm>.Acesso em: 23/06/201. (d) Disponível em: <http://painel.mec.gov.br/painel/captcha>.Acesso em: 23/06/201. (e) Disponível em: <http://www.mprj.mp.br/comunicacao/ouvidoria/consulte-a-sua-comunicacao>. Acesso em: 23/06/201. (f) Disponível em:<https://srv01.tjpe.jus.br/consultaprocessualunificada/>. Acesso em: 23/06/201.

https://www3.bcb.gov.br/faleconosco/#/login/consultar

https://cadsenha.inss.gov.br/cadsenha-internet-web/faces/pages/segurado/entradaNitNb.xhtml

https://cadsenha.inss.gov.br/cadsenha-internet-web/faces/pages/segurado/entradaNitNb.xhtml

https://bankline.itau.com.br/boletos-novosite/simulador_etapas_boletos_02.htm

http://painel.mec.gov.br/painel/captcha

http://www.mprj.mp.br/comunicacao/ouvidoria/consulte-a-sua-comunicacao

http://www.mprj.mp.br/comunicacao/ouvidoria/consulte-a-sua-comunicacao

https://srv01.tjpe.jus.br/consultaprocessualunificada/

19

3 Redes Neurais

Neste capítulo introduziremos redes neurais como uma forma genérica para escreverfamílias de funções. Os conceitos de composição, tipos de camadas e arquiteturas sãoapresentados. Daremos um enfoque aos dois tipos de camadas que foram usados no presentetrabalho. Posteriormente, detalhes técnicos do treino de redes neurais são explorados. Porfim, apresentamos trabalhos selecionados da literatura que utilizaram redes neurais para aquebra de CAPTCHAs de texto.

3.1 IntroduçãoDentro do campo de Inteligência Artificial, aprendizado de máquina é uma aborda-

gem algorítmica para inferir regras em um problema a partir de exemplos. Uma categoriaespecial é a de aprendizado supervisionado, onde os exemplos constituem-se de um elementoem um domínio conhecido e um rótulo associado. O objetivo é deduzir abstrações quepermitam relacionar elementos e rótulos. Nesse contexto, uma rede neural1 é, em últimaanálise, uma forma genérica de descrever funções2 sobre relações elemento-rótulo. Dadauma métrica para a estimativa dos erros cometidos por uma relação inferida, o desafio deinferir regras de associação ótimas se torna um problema de encontrar uma função queminimiza nossa estimativa de erro. O adjetivo ’neural’ advém da inspiração em funçõesbiológicas que historicamente influenciaram e ainda influenciam essa forma de exprimirrelações. Em resumo, redes neurais são um conjunto de técnicas inspiradas em processoscognitivos desempenhados pelo sistema nervoso que fornecem uma maneira genérica dedescrever famílias de funções.

De forma mais específica, dado um conjunto de exemplos D = {(x, y)}, onde xpertence algum domínio conhecido e y um rótulo associado, desejamos encontrar a funçãoy = f(x), de tal modo que y seja o mais similar possível à y. Por ’mais similar o possível’entende-se que conhecemos uma estimativa para os erros, também referida como funçãocusto, que é tão menor quanto melhor for a aproximação dada por f(x), e é normalmenterepresentada como J(y, y). Formalmente, desejamos encontrar f ∗ tal que

f ∗ = arg min{f}

J (D) = arg min{f}

〈J(y, f(x))〉D, (3.1)

onde 〈. . .〉D representa o valor esperado no conjunto D.1 Apesar de introduzidas aqui como um algoritmo supervisionado, redes neurais podem ser aplicadas de

forma efetiva à problemas não supervisionados.2 Funções estão sendo usadas aqui com um sentido mais relaxado do que o usualmente utilizado na

matemática.

Capítulo 3. Redes Neurais 20

Dada uma família de funções fΘ : x → y definida por uma rede neural e para-metrizadas por Θ, podemos vasculhar o espaço de busca induzido, {Θ}, para encontrarum função que satisfaça alguma propriedade de interesse. Em particular, no caso deaprendizado de máquina, estamos interessados em encontrar o parâmetro Θ∗ tal que:

Θ∗ = arg min{Θ}

〈J(y, fΘ(x))〉D. (3.2)

A versatilidade desse formalismo nos permite explorar diferentes tipos de estruturasrelacionais. Em particular, relações hierárquicas podem ser emuladas utilizando-se compo-sição de funções. Essa abordagem nos permite construir redes neurais mais complexas eexpressivas a partir de unidades básicas mais simples. Neste caso, podemos reescrever afunção fΘ como:

fΘ(x) = fΘ(1)

1 (fΘ(2)

2 (fΘ(3)

3 (. . . (x)))), (3.3)

sendo Θ = (Θ(1),Θ(2),Θ(3), . . .) o parâmetro composto por cada um dos parâmetrosindividuais. Quando compomos funções desta forma, é comum nos referirmos à cadafunção fΘ(i)

i como sendo a i-ésima camada da rede neural, sendo as camadas para alémda mais externa também conhecidas como camadas escondias (em inglês hidden layers).A profundidade da rede é uma referência à quantidade de funções internas usadas nacomposição. Diferentes tipos de funções definem diferentes tipos de transformações, asquais nos referimos como tipo da camada. A especificação de todas as camadas em umarede neural é o que chamamos de arquitetura da rede. Não existe um consenso sobre o queseria exatamente a profundidade de uma arquitetura, ou a partir de que ponto podemoschamá-la de profunda (2). Neste trabalho vamos adotar a convenção de que a profundidadede um modelo é dado pelo número de camadas e que uma arquitetura é profunda se possuirmais de uma camada escondida. A seguir vamos explorar dois tipos de camadas que foramutilizados no presente estudo.

3.2 Camadas DensasCamadas densas ou totalmente conectadas definem uma transformação afim entre

o conjunto de entradas e saídas. Tipicamente, após a transformação afim, segue-se aaplicação de uma função não linear elemento-a-elemento, conhecida como função deativação, permitindo a expressão de relações mais complexas. As camadas densas sãobiologicamente inspiradas no mecanismo de comunicação dos neurônios, onde a diferençade potencial elétrico exprimida nas sinapses do axônio é proporcional, em alguma medida,à soma das diferenças de potenciais experimentadas nos dendritos (20). As conexões deentrada em um neurônio e sua regra de composição dos sinais definem sua regra de ativação,ou seja, quais outros neurônios devem estar ativos (e em que intensidade) para que hajauma transição de estado. Como veremos mais adiante, camadas totalmente conectadastentam emular o comportamento de vários neurônios simultaneamente.


De maneira mais formal, seja x um vetor no conjunto de entrada, a relação expressapor uma camada densa é dada por:

fW,b(x) = act(W · x + b) (3.4)

onde b é referido como viés (ou, no inglês, bias), W uma matriz de transformação, actuma função de ativação e · é a operação usual de multiplicação de matrizes, definidaelemento-à-elemento como [W · x]i = ∑

kWikxk. Diferentes funções de ativação expressamrelações distintas sob um vetor de entrada z. Dentre os exemplos mais conhecidos naliteratura, ressaltamos a função sigmoide, σ(z)i = 1

1+exp(−zi) , que mapeia os elementosde saída no intervalo <[0, 1], a função de retificação linear (relu), relu(z)i = max(0, zi),e a função máximo atenuado (softmax), σ(z)i = exp(zi)∑

jexp(zj) , que possui a interessante

propriedade ∑i σ(z)i = 1, sendo usualmente utilizada para expressar distribuições deprobabilidade.

Podemos interpretar a transformação expressa na equação 3.4 como uma projeçãodo exemplo x sob um espaço de características que descrevem uma relação que desejamosexpressar. De fato, se reescrevermos a i-ésima linha de W como αiwi, onde wi é um vetornormalizado e αi a constante de normalização, podemos interpretar cada uma das saídas deuma camada densa (antes da função de ativação) como uma série de projeções balanceadasαiwi · x + bi (· aqui é o produto interno usual). Em outras palavras, a contribuição dai-ésima saída da camada é dada pela importância αi dessa característica multiplicada poro quanto do exemplo é composto por essa característica, wi · x, adicionado de um viésbi que independe do exemplo em questão. Assim, para camadas densas, determinar osparâmetros ótimos pode ser entendido como encontrar projeções do espaço de entrada emum conjunto de características que sejam pertinentes ao problema. Neste sentido, cadasaída de uma camada densa pode ser interpretada como um neurônio, que exprime emsua saída uma soma ponderada dos estímulos de entrada. Quando compomos camadasdensas expressamos características que dependem de outras características. Durante oaprendizado, esperamos que essas projeções sejam descobertas de forma automática pelomodelo. Um desenho esquemático de como essas projeções funcionam pode ser visto nafigura 3. O número de parâmetros em uma camada densa é dado pelo produto entretamanho do exemplo de entrada e a quantidade de características.

3.3 Camadas ConvolucionaisCamadas convolucionais (21, 22) possuem similaridades com as densas: definem

uma transformação afim representada por uma matriz, seguida, possivelmente, de umafunção de ativação. Diferem, entretanto, no tipo de operação matricial utilizada, trocando-se o produto usual de matrizes por uma operação convolucional. Como vimos na seçãoanterior, as saídas de uma camada densa podem ser interpretadas como uma coleção


Figura 3 – Imagem ilustrativa das possíveis projeções aprendidas em uma camada (a)densa e (b) convolucional em um problema de reconhecimento de faces.

(a)

(b)

Em (a) as projeções atuam sobre todo o exemplo de entrada, mapeando-os em um espaço deimportâncias de cada característica. Note que as projeções densas são fixas, no sentido queexpressamos ’olho direito’ em uma posição específica. Em (b) expressamos projeções menoresque ’varrem’ o exemplo de entrada buscando por uma característica em particular, projetando oexemplo em canais de características. Note que, neste caso, procuramos por uma característicaque esteja presente em qualquer lugar da imagem, com os sinais de resposta registrados no canalrespectivo. (Fonte: elaborado pelo autor.)


de projeções independentes do exemplo de entrada sob um espaço de características.Em camadas convolucionais, os parâmetros definem um operador de projeção, que éreutilizado em diferentes subespaços do conjunto de domínio, varrendo o mesmo exemploem busca de padrões específicos em diferentes localizações. Esta peculiaridade é usualmentereferida como compartilhamento de parâmetros. O reuso promove a vantagem de reduzirconsideravelmente o espaço de busca {Θ} (Uma imagem ilustrativa do funcionamentodessas camadas pode ser visto na figura 3). O número de parâmetros nesse caso é dado peloproduto entre o tamanho da projeção e o número características. Camadas convolucionaissão especialmente efetivas quando os elementos do domínio possuem alta localidade, comoé o caso de imagens (cada pixel é altamente correlacionado com seus vizinhos em imagensnaturais) e séries temporais periódicas (o valor da série do tempo t é correlacionadocom o valor da série em t + τ , onde τ é o período da série). Tipicamente, mais de umaprojeção é encapsulada em um mesmo tensor de transformação, sendo a matriz de cadaprojeção referida como núcleo. O resultado da convolução de cada núcleo com o exemplode entrada é tipicamente referida como canal de saída. Cada um desses canais saídas podeser interpretada como o mapa de intensidades da presença da característica definida pelonúcleo da operação no subespaço de aplicação correspondente, isto é, o canal de saída k éa distribuição de similaridade com o núcleo k.

Matematicamente, dado um tensor x, a atuação da camada de convolução podeser escrita como:

fW,b(x) = act(W⊗ x + b) (3.5)

onde W é um tensor de transformação que encapsula a informação de diferentes projeções,b é o vetor de viés, de dimensão igual ao número de canais de saída, act uma função deativação e ⊗ é a operação de convolução, definida elemento-à-elemento por3

[W⊗ x]ijd =∑c

i′+ki∑m=i′−ki

j′+kj∑n=j′−kj

Wm,n,c,dxm,n,c (3.6)

onde c (d) se estende por todos os canais de entrada (saída), 2ki + 1 (2kj + 1) é o tamanhodo núcleo da projeção na direção i (j) e a relação si = i′/i (sj = j′/j) define o passo datransformação (em geral, ki = kj = k e si = sj = s). Uma forma intuitiva de visualizaruma operação convolucional é imaginar que a cada etapa (i, j), cada operador de projeçãow no tensor W define, por canal, uma região x no tensor de entrada centrada em (i, j). Oresultado da operação de convolução é dado pelo produto interno usual entre w e x. Nopasso seguinte a operação é repetida em outra região da entrada até que todos os (i, j)’s deentrada sejam cobertos. Um esquema ilustrativo pode ser visto na figura 4. A contribuiçãototal para cada canal de saída é dado pela soma das convoluções nos canais de entrada(somatório em c na equação 3.6).3 Por simplicidade, estamos definindo aqui a operação de convolução para imagens coloridas, representadas

por tensores de ranque 3. Entretanto, operações de convolução podem ser definidas para outros domínios,como séries temporais (ranque 1), imagens em tons de cinza (ranque 2) e vídeo (ranque 4).


Figura 4 – Exemplo esquemático da execução da operação de convolução em um canal dotensor de entrada x.

No passo i, j, cada operador de projeção w define um campo de atuação x. Para o canal z,zi,j = w · x. O produto interno é realizado transformando w em um vetor linha e x em um vetorcoluna. (Fonte: elaborado pelo autor.)

Como visto, a operação de convolução atua mapeando uma região (do tamanho donúcleo) no canal de entrada em um único pixel no canal de saída. Dada a propriedade delocalidade, essas representações podem adicionar muita redundância de informação no canalde saída. Uma forma de contornar o problema é adicionando uma operação de agrupamento(em inglês pooling) após as ativações da camada. Uma forma simples de realizar umagrupamento é aplicar um mapa entre um conjunto de pixels de entrada em apenas umpixel de saída, reduzindo o tamanho da representação e forçando a rede a encontrarrepresentações mais eficientes entre os níveis de abstração. Escolhas usuais são a média, ovalor máximo (maxpooling) ou uma posição fixa das ativações de entrada. As operações deagrupamento podem ser vistas como um tipo especial de convolução (possivelmente nãolinear) com parâmetros fixos. De fato, uma forma eficiente de implementar agrupamentocom um valor fixo é escolher um passo maior que 1 na operação de convolução.

Camadas de convolução são inspiradas na interpretação vigente do funcionamentodo córtex visual de mamíferos. Diferentes camadas hierárquicas são sensíveis à níveisdistintos de abstração na representação de imagens: as iniciais apreendem informaçõesde traços simples, posteriormente composições de traços, formas geométricas, objetoscomplexos e assim por diante. De fato, estudos mais detalhados das projeções hierárquicasaprendidas após o treino por redes convolucionais profundas mostraram similaridades com


o seu análogo biológico (23) e crescentes níveis de abstração na representação das imagens(24, 25), iniciando com traços simples e texturas nas camadas iniciais e culminando emrepresentações abstratas para objetos nas finais.

Frisamos que esta não é uma lista exaustiva dos diferentes tipos de camadaque podem ser encontrados na literatura. Não listadas aqui, mas que merecem destaque,podemos citar redes de capsula (26), que desempenham operações de convolução e posterioralinhamento das ativações dos filtros, e redes recorrentes (e suas variações), que adicionamcorrelação temporal entre os exemplos através de mecanismos de memória. Uma revisãohistórica da evolução dessas camadas pode ser encontrado em (3). Para uma descrição maisdetalhada das arquiteturas descritas nesse capítulo, incluindo limitações, aplicabilidade edetalhes técnicos, ver (2).

3.4 AprendizadoDefinida a arquitetura da rede neural, isto é, a sequencia das camadas e respectivas

funções de ativação, procedemos para o treino da rede, que consiste em encontrar osparâmetros ótimos Θ∗ como definido na equação 3.2. A forma mais ingênua para procuraro valor ótimo seria utilizar o método do gradiente (ou método do máximo declive), queconsiste em atualizar iterativamente Θ na direção contrária à do gradiente da função custosegundo a regra

Θ← Θ− lr∇ΘJ(D), (3.7)

onde lr é o hiper-parâmetro de aprendizado ou taxa de aprendizado, D o conjunto ondea atualização é realizada e ∇Θ o operador gradiente com respeito aos parâmetros Θ. Aevolução de Θ ao longo do treino é referida como dinâmica do aprendizado.

O método do gradiente nos garante que, uma vez atingido o mínimo global, ogradiente da função custo é nulo (∇ΘJ

(D) = 0), e nenhuma atualização posterior se faránecessária. Entretanto, não nos é garantido o recíproco: uma vez que ∇ΘJ

(D) = 0, nãopodemos afirmar se encontramos um mínimo local, um ponto de sela ou até mesmo umponto de máximo. Também não é garantido se eventualmente um ponto de gradientenulo será encontrado. Adicionalmente, a escolha do hiper-parâmetro lr e do conjunto deatualização D não são especificados pelo método.

Quanto à escolha do conjunto de atualização, podemos escolher dentre atualizar osparâmetros para cada exemplo, para um subconjunto ou para todos os exemplos disponíveispor vez. No primeiro caso, conhecido como gradiente estocástico, temos a vantagem deatualizar Θ sempre que a rede é exposta à um exemplo, o que poderia levar a umaconvergência mais rápida. Essa escolha é comumente referida como aprendizado online.Entretanto, as flutuações estatísticas de cada exemplo podem gerar uma condição de difícilconvergência, com o gradiente da função custo mudando drasticamente de direção a cada


atualização. No outro extremo, conhecido como gradiente em lote, D constitui todo oconjunto disponível de treino. Nessa escolha, o gradiente calculado para cada exemploé acumulado e a atualização é feita pela média dos gradientes em todos os exemplos detreino. Apesar da vantagem da estabilidade estatística, corremos dois riscos: média sobreo conjunto de treino pode anular ou diminuir particularidades de subconjuntos específicosou podemos demorar demais para atualizar Θ, o que torna o aprendizado mais lento.Uma terceira opção consiste em juntar o melhor das duas escolhas anteriores: promover aatualização dos parâmetros à cada NB exemplos. Tal técnica é denominada atualizaçãoem mini-lote ou gradiente em mini-lote e foi a técnica escolhida no presente trabalho.

Quanto à escolha de lr temos que buscar um compromisso entre dois extremos.Valores pequenos produzem dinâmicas lentas, onde as atualizações dos parâmetros sãopequenas e o tempo de treino se estende por diversas iterações. Em alguns casos, a dinâmicapode estagnar em regiões onde ∇ΘJ

(D) é pequeno mas o valor do custo ainda é alto. Nooutro extremo, temos uma dinâmica mais rápida, porem mais instável. Pontos de mínimopodem ser completamente ignorados (fenômeno referido como overshoot) e a função de errotende a exibir flutuações que dificultam a convergência. Para valores extremamente altos,a dinâmica pode superestimar os erros cometidos e/ou amplificar demais as flutuações,fazendo o valor do custo aumentar ao invés de diminuir. Uma maneira de contornar oproblema é utilizar uma abordagem adaptativa. Uma solução simples é diminuir o valorda taxa de aprendizado ao longo do treino, sendo decaimento linear ou exponencial duasescolhas bastante comuns. Dessa forma, temos um balanço entre rápido aprendizado noinício da dinâmica e maior estabilidade próximo ao fim. Outras técnicas incluem estabelecerregras de atualização baseadas no gradiente da função de custo e no momento (taxa deatualização do gradiente). A descrição detalhada dessas técnicas fogem ao escopo destetrabalho. Nos experimentos utilizamos a técnica conhecida como Estimativa Adaptativado Momento (em inglês, Adaptive Moment Estimation), também referida como Adam (27)que foi especialmente desenvolvida para atualizações em mini-lote e utiliza o momento dosgradientes do custo para estabilizar o aprendizado e decaimento da taxa de treino. Umexemplo esquemático de uma dinâmica lenta (lr pequeno) e rápida (lr grande) pode servista na figura 5.

Para redes compostas por várias camadas, como descrito na equação 3.3, a atuali-zação dos parâmetros torna-se complicada e potencialmente suscetível a erros numéricos.Uma forma eficiente de contornar o problema é utilizar a técnica de propagação reversa(em inglês back-propagation). Nesta técnica, a computação realizada pela rede é mapeadaem um grafo, sendo cada operação realizada na computação expresso como um nó e o fluxode dados entre duas operações representado por uma aresta direcionada. Durante a fasedireta (feed-foward) a computação é executada nó-a-nó e os resultados parciais de cadaoperação armazenados. Durante a fase reversa, as arestas são invertidas e o erro propagadoentre os vértices do grafo reverso utilizando-se os valores previamente armazenados e a


Figura 5 – Exemplo de comportamento característico da função de custo durante o apren-dizado.

Em vermelho o aprendizado é lento e apresenta flutuações menores. Em verde o custo decairapidamente, mas apresenta flutuações mais drásticas. (Fonte: elaborado pelo autor.)

regra da cadeia para expressar a dependência entre os erros. Durante essa etapa, cadanó que possui um parâmetro a ser aprendido é atualizado. Ver (3) para uma revisão dométodo.

3.5 RegularizaçãoComo visto da seção 3.4, durante a evolução da dinâmica de aprendizado, os

parâmetros da rede evoluem de forma a reduzir o valor esperado da função de custo noconjunto de treino. Entretanto, diminuir o erro nos exemplos vistos não garante que omodelo apresentará a mesma qualidade em novos elementos ausentes durante essa fase.De forma mais precisa, seja U o conjunto de todos elemento-rótulo possíveis, tipicamentetemos a disposição um subconjunto D ⊂ U para otimizar a rede, e utilizamos J (D) como umestimador estatístico para J (U), isto é, supondo que D tenha sido formado por instânciasaleatórias de U , teremos J (D) → J (U) quando |D| → |U |. Tipicamente, entretanto, temosa situação em que |D|≪ |U |. Como o modelo foi otimizado neste subconjunto, o valoresperado da função custo em D se torna um estimador enviesado para o erro esperadoem exemplos não vistos. Uma maneira simples e eficiente de estimar a capacidade degeneralização modelo é criar a cobertura exata (Dtr, Dval) para D, treinar o modelo emDtr e estimar sua qualidade em Dval. Esta técnica é conhecida como hold-out, e J (Dval)

uma estimativa para o poder de generalização do modelo (28).


Um outro problema recorrente no treino de modelos de aprendizado de máquinaé a adaptação do modelo ao conjunto de treino. Em um extremo, modelos de baixaexpressividade podem não conseguir capturar a complexidade das relações exemplo-rótulo.Esse fenômeno é conhecido como underfitting. No outro limite, a medida que aumentamosa expressividade (mais camadas, mais projeções, etc.), aumenta também capacidade deapreender relações mais complexas entre exemplos e rótulos. Entretanto, modelos commaior expressividade tendem a ser mais propensos a ’decorar ’ exceções e superestimarparticularidades do conjunto de treino. Tal fenômeno é conhecido como coadaptação ouoverfitting. Outra situação em que podemos incorrer em overfitting é quando o modelo éexcessivamente exposto aos mesmos exemplos durante uma seção de treino. O underfittingpode ser detectado diretamente da qualidade do modelo em Dtr, quando seu desempenhose mostra aquém do esperado. O segundo pode ser estimado utilizando a decomposiçãoviés-variância da estimativa do erro, onde entendemos que parte do erro cometido é devidoa baixa expressividade e parte por superestimar particularidades do conjunto de treino.Para tal, a qualidade do modelo em Dtr e sua capacidade de generalização (estimada emDval) são comparadas e a diferença entre as duas servem para estimar a relação entre viése variância. Um exemplo ilustrativo do comportamento do erro nesses dois conjuntos podeser visto na figura 6.

Figura 6 – Exemplo ilustrativo de overfitting e underfitting.

Em verde vemos que o erro estimado no conjunto de treino se comporta como uma funçãodecrescente da complexidade do modelo. Em vermelho, o erro estimado o conjunto de validaçãomostra que existe um valor ótimo para o poder de generalização. Fixada a complexidade domodelo, experimenta-se um comportamento similar quando aumentamos a exposição aos exemplosno conjunto de treino. (Fonte: elaborado pelo autor.)

Para minimizar o efeito de coadaptação dos parâmetros, podemos impor condições


extras durante o processo de aprendizado. Uma das condições mais usuais é aplicar aovetor de parâmetros Θ alguma restrição. Podemos, por exemplo, adicionar à função custoum termo proporcional à norma do vetor Θ, na forma

J = J + λ |Θ|p , (3.8)

onde J é o custo utilizado durante a minimização, |Θ|p = p√

Θp é a norma p e λ ohiper-parâmetro de regularização ou constante de normalização. Desta forma penalizamosparâmetros que ’aprendam’ demais uma determinada característica. Apesar de efetivo, ouso de regularização baseado em normas adiciona dois novos hiper-parâmetros: a constantede normalização e o tipo de norma que devemos usar. Outra forma de regularização comumna literatura é o dropout (29). Nesta técnica, a saída i de uma camada é removida dacomputação (atribuída o valor zero) com uma probabilidade p, hiper-parâmetro da técnica.Intuitivamente, o uso do dropout durante o treino força a rede a encontrar representaçõesredundantes e mais robustas à detalhes, dado que a cada nova iteração uma característicaaprendida anteriormente pode estar ausente.

3.6 Redes Neurais e CAPTCHAsComo visto na secção 2.2, CAPTCHAs de texto podem ser vistos como um problema

de extração de texto em imagens, sendo assim uma generalização para o problema de OCRe um subproblema de localização de texto em imagens (identificar, se existir, a localizaçãode todos os textos em uma imagem). É preciso ressaltar, entretanto, que nesses HIPs asimagens são especialmente desenvolvidas para serem de difícil solução para computadorese preferencialmente fáceis para seres humanos. Assim, algoritmos usuais de OCR tendema demonstrar baixo desempenho na solução desses desafios. Vamos separar as abordagenspara o problema em dois grandes grupos: abordagens informadas e não informadas.

Em abordagens informadas o autor do ataque estuda os efeitos e o alfabeto utilizadona composição do desafio e confecciona um pipeline para preprocessamento e segmentaçãodos caracteres componentes do token. Esta etapa envolve o uso de heurísticas e é extre-mamente dependente da regularidade das imagens4 e da habilidade do atacante para quebons resultados sejam alcançados. Após a segmentação, o desafio se resume à reconhecercorretamente cada símbolo. Um dos trabalhos pioneiros na quebra de CAPTCHAs de textofoi conduzido por (9) e utiliza essa abordagem. Inicialmente as imagens foram preproces-sadas e segmentadas. Para o reconhecimento foram usadas redes convolucionais de duascamadas, alcançando acurácias entre 10% e 50% (fortemente dependente da qualidade dopreprocessamento). Bursztein et al. formalizaram ainda mais o pipeline de processamento,lançando a ferramenta Decaptcha (19), que permite explorar e testar etapas do processo4 Isso é tipicamente verdade quando a imagem é gerada automaticamente por um computador. Neste

caso, técnicas de engenharia reversa podem guiar o desenvolvimento de heurísticas.


de quebra especificando-se técnicas de preprocessamento, segmentação, pos-segmentação,reconhecimento e aprimoramento pós reconhecimento. Com o auxilio dessa ferramenta,os autores relataram modelos com acurácias mais baixas em trono de 20%, chegando100% de acertos em desafios mais simples. Entretanto, como sugerido pelos própriosautores, na fase de reconhecimento a ferramente utiliza algoritmos com baixo poder deexpressividade (k-vizinhos mais próximos e máquinas de vetores de suporte) se comparadoscom técnicas mais atuais. Se olharmos apenas para o desafio pós segmentação, a extraçãode texto de CAPTCHAs se resume a um problema de reconhecimento de caracteres, enesse campo o estado da arte é dominado por redes neurais. De fato, no repositório doMNIST5 (30), por exemplo, redes convolucionais pontuam entre as melhores taxas deacerto, sendo o melhor modelo registrado o desenvolvido por Cireşan et al., que alcançou99.77% de acerto e é baseado na média do voto de 35 redes convolucionais independentes(31). Para CAPTCHAs de texto formados por imagens reais, as diversas condições deaquisição (iluminação, ângulo, escala, etc.) degradam as vantagens de um pipeline únicode preprocessamento. Mesmo neste caso, redes neurais ainda são capazes de demonstrarbom desempenho. Netzer et al. propuseram o repositório SVHN6 como benchmark paraesse tipo de desafio (32). Partindo das imagens já segmentadas, os autores foram capazesde obter precisões em torno de 90% utilizando-se abordagens não supervisionadas deredes neurais. O resultado foi posteriormente refinado utilizando-se redes convolucionaisprofundas e treino supervisionado, alcançando 94.5% de precisão (33).

Quanto às abordagens não informadas, o modelo deve aprender de forma autônomacomo localizar, segmentar e reconhecer os caracteres em uma imagem, minimizando ainterferência direta humana. Entretanto, inferir esse nível de abstração apenas baseadoem exemplos pode requerer quantidades massivas de dados anotados. Utilizando umaabordagem não informada, Goodfellow et al. foram capazes de obter 99.8% de acerto nostextos da primeira versão do reCAPTCHA (12). Os autores ainda conduziram um estudo norepositório SVHN, obtendo acertos de 97.84% por caractere e 96% para o token completo.Entretanto, a base de treino utilizada era formada por 600 mil imagens para o SVHN (todaa base de teino) e mais de um milhão de imagens para o reCaptcha. Mais recentemente,foi investigada uma alternativa para diminuir volume de dados necessário para esse tipode abordagem através de uma nova arquitetura denominada Redes Corticais Recorrentes(do inglês, Recurrent Cortical Network) (13). Utilizando esta nova arquitetura, os autores5 O MNIST (Modified National Institute of Standards and Technology database) é um repositório aberto

contendo 70000 imagens de dígitos escritos à mão e usualmente usado como benchmark para técnicasde OCR. A tarefa consiste em reconhecer corretamente o número codificado na imagem. No sítio dorepositório existe uma tabela comparativa da precisão de diversos estudos publicados utilizando-sediferentes técnicas ao longo dos anos.

6 SVHN (Street View House Numbers), composto por mais de 600000 fotos de fachadas de construçõescontendo números. O desafio consistem em reconhecer corretamente os algarismos codificados naimagem. O repositório possui dois formatos para os mesmas imagens: a) Caracteres segmentados; e b)Apenas a região contendo os números.


do estudo relataram uma alta eficiência de dados, obtendo resultados satisfatórios comalgumas milhares ou até mesmo centenas de exemplos. O diferencial dessa arquitetura sãoconexões extras adicionadas entre as camadas que permite um fluxo mais complexo dainformação. Aplicada à quebra de CAPTCHA, os autores treinaram esse tipo de rede emimagens contendo diferentes fontes tipográficas para o mesmo alfabeto. Durante a validação,a arquitetura mostrou capacidade de generalizar e abstrair as transformações aplicadas emCAPTCHAs sintéticos, sendo capaz de reconhecer os símbolos mesmo após as deformações.Um ponto negativo, entretanto, é o tempo de treino dessa nova arquitetura. As mensagenstrocadas entres as camadas e o algoritmo proposto para supressão de característica limitama capacidade de paralelização e tornam a execução mais lenta. De fato, há uma nota norepositório dos autores informando que o treino em 1000 imagens do desafio MNIST (ondeo algoritmo se aproxima do estado da arte nesse desafio) pode levar horas em múltiplasCPUs7. Adicionalmente, os autores alegam que fizeram ajustes nos filtros convolucionais enas fontes de treino para cada aplicação, o que pode ser interpretado com uma forma deadicionar viés ao modelo (algo como uma abordagem semi-informada).

Em um estudo similar ao nosso, Pinto alcançou 76, 6% de precisão na quebraCAPTCHAs de texto utilizando redes neurais profundas. Contudo, foram necessáriosuma base de treino com 180 mil imagens e placas de processamento gráfico de últimageração, sendo o treino realizado em sistemas de computação sob demanda (34). Sendoeste o trabalho mais recente diretamente relacionado ao nosso encontrado na literatura, odefinimos como trabalho de referência para comparações com os resultados obtidos emnosso trabalho.

Diante disso, apesar da qualidade dos resultados encontrados na literatura, osrequisitos desses sistemas os tornam proibitivos para serem treinados em computadorescomuns. Na tabela 1 apresentamos um breve comparativo dos requisitos de alguns dosestudos selecionados. Essas restrições limitam o acesso dessa tecnologia à ambientes commenor poder de processamento ou restrições orçamentárias. É particularmente proibitivopara o estudante médio brasileiro, o que pode gerar uma defasagem de aprendizadotecnológico, e para pequenas empresas experimentarem soluções inovadoras baseadasnessas descobertas. Assim, o objetivo deste trabalho é propor um abordagem construtivapara a experimentação de redes neurais profundas em computadores comuns focada noproblema de quebra não informada de CAPTCHAs de texto. Pretendemos mostrarque é possível alcançar resultados próximos ao estado da arte a partir da investigaçãocautelosa do comportamento dos modelos durante a dinâmica de treino, com bases detreinos menores e arquiteturas mais simples.

7 Fonte: <https://github.com/vicariousinc/science_rcn>. Acesso em: 23/06/2018.

https://github.com/vicariousinc/science_rcn


Tabela 1 – Comparação entre os requisitos dos modelos encontrados na literatura.

Referência Limitação

Netzer et al. (32) 600 mil imagens, 500 filtrosconvolucionais 8x8.

Sermanet et al. (33) 16 filtros 5x5, 512 filtros 7x7, 2camadas densas de 4000 entradas.

Goodfellow et al. (12)

De 9 a 11 camadas convolucionais(8-192 filtros), camada densa com mais

de 3 mil entradas, mais de 500 milexemplos.

Pinto (34)

180 mil exemplos, quatro camadasconvolucionais com 64, 128, 256 e 512canais, duas camadas densas com maisde 4000 entradas, totalizando mais de

6 107 parâmetros.

George et al. (13)

Treinamento de difícil paralelização.Muitas horas de treino para alcançarresultados satisfatórios. Necessidade de

acompanhamento por humanos.

33

4 Modelagem

Neste capítulo apresentamos uma justificativa para a abordagem comparativaproposta no presente estudo. Em seguida descrevemos as camadas e arquiteturas que foramutilizadas. Adicionalmente, definimos a nomenclatura adotada de forma a simplificar atransmissão de nossos resultados.

4.1 Abordagem ComparativaO projeto da arquitetura é um ponto crucial para a obtenção de resultados satisfa-

tórios. Infelizmente, até o presente momento, não existe nenhum estudo que demonstrede forma precisa como as camadas interagem entre si ou sobre como estimar o impactode cada componente no modelo final. Encontramos um problema similar na escolha doshiper-parâmetros. Em sua grande maioria, não existe uma metodologia definida de comoescolher os valores que apresentarão os melhores resultados, sendo nosso conhecimentousualmente limitado a ideias gerais. De fato, se imaginarmos que um hiper-parâmetro é umvalor que altera o funcionamento de um método, mas que precisa ser escolhido para cadacaso, a própria arquitetura da rede pode ser vista como uma espécie de hiper-parâmetroque precisa ser definido. Assim, deste ponto em diante, iremos nos referir à escolha daarquitetura e dos hiper-parâmetros simplesmente como configuração. A falta de umsuporte teórico para as decisões à serem tomadas no projeto de uma configuração, obrigamo projetista a basear suas escolhas em critérios arbitrários.

Uma forma de contornar o problema seria realizar uma busca em todas as possíveiscombinações e escolher a melhor dentre elas. Entretanto, basta notar que as possibilidadesde configurações aumentam de forma algébrica com cada possibilidade para se convencerde que esta é uma solução computacionalmente inviável. Mesmo se encontrarmos umaforma de simplificar a busca por soluções, impondo limites às configurações válidas e/ouutilizando algum algoritmo inteligente (busca heurística, algoritmos evolucionários, etc.),ainda teríamos de realizar um treino completo de cada configuração para poder estimarsua performance1. O problema de escolher uma boa configuração é ainda mais grave emambientes restritivos, onde adicionalmente temos que nos limitar aos recursos disponíveis.

Podemos, entretanto, lançar mão de alguns pressupostos para realizar uma escolhaeficiente de configurações para experimentação:1 O problema de encontrar configurações de algoritmos de aprendizado de máquina de forma automática

é referido na literatura como automl (do ingles, auto machine learning). Mesmo para modelos maissimples ainda é um problema de intensa pesquisa.

Capítulo 4. Modelagem 34

1. O início da dinâmica de uma configuração fornece informações importantes sobre ocomportamento seu ao longo do resto treino.

2. Configurações similares tendem a produzir resultados similares.

3. Uma experimentação mais consistente, isolando o máximo possível a influência decada variável, resulta em conclusões mais consistentes.

Neste trabalho, propomos a realização de experimentos comparativos entre diferentesconfigurações como uma forma de ajudar o processo do projeto da arquitetura e escolhade hiper-parâmetros satisfazendo os pressupostos da seguinte forma:

1. Várias configurações são treinadas durante um tempo reduzido e sua performanceavaliada.

2. As arquiteturas a serem estudadas são substancialmente diferentes entre si. Esseprincípio também é aplicado à parâmetros contínuos como a taxa de aprendizado,por exemplo.

3. Um conjunto de hiper-parâmetros sempre será mantido fixo enquanto os demais sãoexplorados de forma mais minuciosa, permitindo uma comparação direta do impactode cada escolha. De outra forma, é preferível fixar um configuração e variar apenasum parâmetro do que ter diferentes configurações que não podem ser diretamentecomparadas.

Este método nos permite, ao mesmo tempo, satisfazer as restrições e executartreinos de forma mais eficiente. Tipicamente, cada etapa de treino consiste dos mesmospassos, assim, se calcularmos o tempo médio de duração de cada etapa no inicio dadinâmica, podemos estimar o tempo máximo do treino (restrição de tempo). Geralmente,fenômenos como coadaptação e divergência podem ser detectados nas primeiras etapasde treino, poupando-nos de prosseguir com a experimentação. Adicionalmente, duranteo tempo que seria usado em um treino completo, podemos realizar vários treinos maisrápidos. Como projetamos cada uma das arquiteturas, podemos nos restringir àquelas queobedecem ao limite disponível de recursos (restrição de memória e processamento) e aindaobter uma variabilidade de experimentação. A escolha consistente dos hiper-parâmetrosnos permite determinar de forma mais precisa sua influência na performance e decidir deforma consciente qual valor usar (pressupostos 3). O método pode ser aplicado de formaiterativa quantas vezes forem necessárias de forma a refinar ainda mais os resultados. Nestecaso, os novos experimentos devem ser construídos com base nos já realizados. Com osexperimentos concluídos, podemos então escolher uma configuração que apresente boaperformance e obedeça os critérios impostos e então realizar um treino completo.


4.2 CamadasNesta secção descrevemos as camadas utilizadas no presente trabalho. Tendo em

mente o pressuposto 3 da metodologia proposta, cada camada é descrita explicitando oshiper-parâmetros que serão mantidos fixos os que serão objeto de experimentação.

Camadas densas (FlO) possuem O neurônios ou projeções como visto no capítulo3. Estas camadas mapeiam uma soma balanceada dos I sinais de entrada em O sinais desaída, tendo I ×O parâmetros. Quando presente, a ativação relu é aplicada aos sinais desaída. Camadas multi-caracteres (M) mapeiam os sinais de entrada em uma distribuiçãode probabilidades para cada caractere no token. Mais especificamente, esta camada éformada por N (sendo N = 5, o tamanho fixo do token) classificadores independentes,cada um formado por uma camada densa seguida de uma ativação softmax. Os parâmetrosde cada classificador não são compartilhados entre si. A camada multi-caracteres estápresente em todas as arquiteturas, sendo sempre a última. Sendo o sinal de entrada umvetor de tamanho I e o de saída de tamanho O (onde O = 36 é o tamanho fixo do alfabeto),o número de parâmetros da camada M é dado por N × I ×O (= 180× I).

Camadas convolucionais CO possuem núcleos de tamanho fixo k = 5 em cada umadas direções, O canais de saída e passo s = 1 ou s = 2 dependendo da arquitetura. Se acamada convolucional for seguida por uma agregação de maxpooling, ela sempre terá passo1, caso contrário, o passo é 2, exceto quando houver mais de uma camada convolucional.Neste caso, a primeira tem passo 1 e as demais 2. O tamanho de um camada convolucionalcom I canais de entrada e O canais de saída é dado por k2 × I ×O (= 25× I ×O). SejaXH,W,I o tensor e entrada, a saída é um tensor Z(H−k+1)/s,(W−k+1)/s,O. Após cada camadaconvolucional é aplicada uma ativação relu.

A operação de linearização transforma o tensor de entrada em vetor de saída,através da reordenação dos índices. Seja o tensor de entrada XH,W,I , a saída desta camadaé um vetor x′

H×W×I . A linearização está sempre presente antes da primeira camada densada arquitetura. As operações de dropout (D) e de maxpooling (Max) podem estar presentesou não, dependendo da arquitetura. Quando presente, o dropout atuará em cada umadas camadas ocultas da rede, anulando cada um dos sinais de saída da camada de formaindependente com probabilidade de pdrop = 30%. A única exceção é nas arquiteturas comapenas a camada multi-caractere. Neste caso, o dropout é aplicado diretamente nos sinaisde entrada da rede, isto é, diretamente na imagem. A operação de maxpooling, quandopresente, atua depois de cada camada convolucional, com passo fixo em 2 em ambas asdireções. Ou seja, apenas o maior valor dos quatro pixels de entrada (2 na direção i e 2na direção j) estará presente no canal de saída. A operação agregação só é aplicada aofim de camadas convolucionais que teriam passo 2 (vide descrição no parágrafo anterior).Caso presente, as camadas convolucionais passam a ter passo 1. O tensor de saída temas dimensões transformadas de forma similar à uma operação convolucional com k = 2


e s = 2. Nenhuma dessas operações (linearização, agrupamento ou dropout) adicionamparâmetros à arquitetura, tendo tamanho 0.

4.3 ArquiteturasAs arquiteturas estudadas são formadas pela composição das camadas descritas na

seção 4.2. De modo a facilitar a referência posterior, o nome dado a cada uma é definidopela concatenação dos nomes de cada camada, com a indicação das operações facultativasquando presentes. Nas tabelas 2-7 a seguir as arquiteturas são descritas por camada,estando as dimensões de entrada e saída e número de parâmetros explicitados. A presençada regularização é indicada entre colchetes. O fluxo de dados durante a computaçãoocorre da primeira para a última linha na tabela. Todas as arquiteturas definidas aquitambém foram experimentadas em versões usando agregação maxout, mas e o detalhamentodelas podem ser facilmente obtidos a partir das descrições apresentadas, sendo, portanto,omitidas (vide apêndice B).

No próximo capítulo descrevemos os detalhes do treino e validação das arquiteturasaqui descritas, completando a definição de uma configuração e de como foram executadasas experimentações. Para os hiper-parâmetros foram utilizados os mesmos princípiosexplicitados neste capítulo. No capítulo de resultados, as métricas de interesses paras essasarquiteturas são comparadas e um modelo escolhido à luz da metodologia proposta.


Tabela 2 – Arquitetura M [D]

Camada Descrição Entrada Saída ParâmetrosLin [Dropout] (50,200,3) (30.000) 0M 5 classificadores. (30.000) (5,36) 5.400.000total 5400000

Tabela 3 – Arquitetura C6M [D]

Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de entrada

e 6 de saída. Passo da convolução 2.[Dropout]

(50,200,3) (23,98,6) 450

Lin - (23,98,6) (13.524) 0M 5 classificadores. (13.524) (5,36) 2.434.320total 2.434.770

Tabela 4 – Arquitetura C6C12M [D]

Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-

trada e 6 de saída. Passo da convo-lução 1. [Dropout]

(50,200,3) (46,196,6) 450

C12 Convolucional com 6 canais de en-trada e 12 de saída. Passo da con-volução 2. [Dropout]

(46,196,6) (21,96,12) 1.800

Lin - (21,96,12) (24.192) 0M 5 classificadores. (24.192) (5,36) 4.354.560total 4.356.810


Tabela 5 – Arquitetura C6C12Fl100M [D]



(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1.800

Lin - (21,96,12) (24.192) 0Fl100 Camada densa com 24.192 sinais de

entrada e 100 sinais de saída. [Dro-pout]

(24.192) (100) 2.419.200

M 5 classificadores. (100) (5,36) 18.000total 2.439.450

Tabela 6 – Arquitetura C6C12C36C36M [D]



(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1.800

C36 Convolucional com 12 canais de en-trada e 36 de saída. Passo da convo-lução 2. [Dropout]

(21,96,12) (9,46,36) 10.800


(9,46,36) (3,21,36) 32.400

Lin - (3,21,36) (2.268) 0M 5 classificadores. (2.268) (5,36) 408.240total 453.690


Tabela 7 – Arquitetura C6C12C36C36Fl100M [D]



(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1.800


(21,96,12) (9,46,36) 10.800


(9,46,36) (3,21,36) 32.400

Lin - (3,21,36) (2.268) 0Fl100 Camada densa com 2.268 sinais de en-

trada e 100 sinais de saída. [Dropout](2.268) (100) 226.800

M 5 classificadores. (100) (5,36) 18.000total 290.250

40

5 Metodologia

Neste capítulo apresentamos os detalhes envolvidos no treino e avaliação dosmodelos. Primeiramente a geração das imagens de CAPTCHAs é abordada. Em seguida,definimos as grandezas de interesse que nos permitem estimar a qualidade dos modelostreinados. Por fim, as etapas de treino e validação são formalizadas.

5.1 Geração dos CAPTCHAsTodos os exemplos foram gerados utilizando a biblioteca SimpleCaptcha(35). Ao

total, foram gerados 30000 pares imagem-token. As sequências de texto possuem compri-mento fixo em 5 e os caracteres foram sorteados de forma independente a partir do alfabetoordenado Σ = {0123456789abcdefghijklmnopqrstuvwxyz} de 36 símbolos. Dentre osefeitos escolhidos para as imagens, enfatizamos as variações nas cores de fundo, desenhode grades, adição de linhas aleatórias e deformação em explosão, que são técnicas efetivaspara construir desafios fáceis para humanos e difíceis para computadores, de acordo comestudo conduzido por (9). Uma pequena amostra dos pares imagen-token gerados pode servista na figura 7.

Figura 7 – Exemplos de CAPTCHAs gerados e seus respectivos tokens.

(a) b26bf (b) ep8nb

(c) b7rw8 (d) 74wf6

(e) dnyny (f) g4cxh

Capítulo 5. Metodologia 41

Considere D = (X,Y) o conjunto formado por todos os pares de imagem-tokengerados. Durante o treino, cada exemplo de entrada é formado por um tensor imagemX e uma matriz Y representando o token correto u, de dimensões (200, 50, 3) e (5, 36),respectivamente. Ao realizar uma predição, apenas a entrada X é fornecida à rede. CadaXijk ∈ <[0, 1] representa a intensidade do pixel localizado na posição (i, j) e canal k,enquanto Yij ∈ <[0, 1] foi codificado utilizando-se a técnica one-hot encoding, onde irepresenta a posição na sequência u e j o índice no vocabulário do caractere nessa posição,de modo que

Yij =

1, se ui = Σj

0, caso contrário,(5.1)

ou, de forma mais compacta, Yij = δui,Σj, onde δm,n é o delta de Kronecker. Essa codifica-

ção nos permite interpretar Y como uma coleção de distribuições de probabilidade. Seimaginarmos z como uma variável aleatória descrevendo a i-ésima entrada na sequência, epi(z|X) como a distribuição de probabilidade condicional de z dada a imagem X, paraos exemplos gerados, o conhecimento da imagem define automaticamente qual o carac-tere em cada posição com 100% de certeza, ou seja, pi(z = ui|X) = 1 e, caso contrário,pi(z 6= ui|X) = 0. Ou, utilizando o delta de Kronecker, pi(z|X) = δz,ui

. Definindo ord(c)como o índice do caractere c no alfabeto Σ (isto é, c = Σord(c)) e sendo j o índice de z novocabulário, da equação 5.1, vem que pi(z|X) = δz,ui

= δui,z = δui,Σord(z) = δui,Σj= yij.

A saída da rede neural é a matriz Y = fΘ(X) contendo as distribuições deprobabilidade inferida pela rede. O caractere predito na posição i é dado pelo caracteremais provável nesta posição, isto é, Σarg maxj Yij

, sendo o token predito formado peloscaracteres mais prováveis em cada posição. Nosso objetivo é encontrar Y como umaaproximação para Y.

Para a preparação da base, o D foi reordenando de forma aleatória e separado emdois subconjuntos: o conjunto de treino, Dtr, com 2

3 do total de pares, e o conjunto devalidação, Dval, com os demais exemplos. Devido à natureza combinatória do espaço deimagens possíveis (365 tokens × 2553 cores de fundo × espaço de todas as pertubaçõespossíveis), D é muito menor do que o conjunto de todas as possíveis composições imagem-token e, supondo que seus elementos tenham sido construídos ao acaso, é muito improvávelque existam exemplos repetidos nesse conjunto.

5.2 Treino e ValidaçãoUma época de aprendizado consiste em duas etapas: treino e validação. Durante a

etapa de treino, um subconjunto Dbatch ⊂ Dtr é sorteado ao acaso. Os parâmetros da redesão atualizados utilizando o algoritmo adaptativo Adam com os parâmetros sugeridos em(27) (β1 = 0.9, β2 = 0.999 e ε = 10−8) e taxa de aprendizado lr de forma a minimizar o erro


nesse subconjunto. Esta etapa (treino dentro de uma época) se encerra após |Dtr|/|Dbatch|atualizações. Na etapa de validação, as medidas de interesse são calculadas para Dtr eDval e salvas para posterior análise. Em todos os experimentos fixamos |Dbatch| = NB = 10exemplos.

As redes foram inicializadas segundo a heurística proposta em (36) e as épocasde aprendizado se sucedem até que o critério de parada seja alcançado. Escolhemoscomo critério de parada uma heurística semelhante às definidas por (37). A dinâmica deaprendizado leva no mínimo Tmin e no máximo Tmax épocas. Após a etapa de validação,o aprendizado é interrompido prematuramente se um dos dois critérios forem verificados:o custo calculado em Dval na época atual ultrapasse em mais de 3% o menor valor deJ (Dval) nas épocas anteriores; o valor de J (Dtr) atual seja maior do que 97% da média doscinco últimos custos nesse conjunto, isto é, a média móvel dos últimos valores é sempredecrescente. Ou seja, o treinamento é parado prematuramente se for detectado overfitting(critério de controle) ou se não houver melhora significativa em relação aos últimos valores(critério de consistência). Consideramos que o treino do modelo foi exitoso se alcançarmosTmax épocas sem que os demais critérios de parada sejam alcançados.

Para selecionar o valor do hiper-parâmetro lr, foram realizados experimentos duranteas 10 primeiras épocas e lr = 10−η, com η = 1, 2, 3, 4, 5, para cada arquitetura. A partirdos experimentos, selecionamos manualmente os limites inferior e superior, (l−r , l+r ), queapresentam o melhor compromisso entre velocidade de aprendizado e estabilidade (videseções 3.4 e 4.1). A arquitetura escolhida é então treinada com uma taxa de aprendizadona época t segundo a equação:

lr(t) = l+r + (l−r − l+r ) ∗ t

Tmax − 1 . (5.2)

Todos os experimentos realizados nesse trabalho foram executados ema máquinacom processador Intel R© CoreTMi5-6200U, 8gb de RAM e placa de aceleração gráficaNVIDIA R© 920M com 2 gb de memória, utilizando a biblioteca de código aberto Tensorflow(38).

5.3 MétricasNo capítulo de fundamentação teórica de redes neurais (capítulo 3), vimos que

cada arquitetura é parametrizada por Θ. Mais especificamente, cada uma das arquiteturasutilizadas neste trabalho possui como parâmetros um conjuntos de números reais. Assim,definimos o tamanho do modelo, para fins de comparação, como a soma da quantidadede parâmetros de cada camada da arquitetura. Para treinar e avaliar a qualidade dosmodelos, consideramos as grandezas definidas à seguir. Em todas as definições, considere


D um conjunto de exemplos, (X,Y) ∈ D e Y = fΘ(X) a distribuição de probabilidadeinferida pelo modelo (eq. 5.1).

Para avaliar o erro cometido pelos classificadores, podemos utilizar a entropiacruzada (no inglês cross entropy), que pode ser interpretada como uma medida dedivergência entre duas distribuições de probabilidade. Assim, o custo associado ao inferirY quando a verdadeira distribuição deveria ser Y, por caractere, é dado por

Hi(Y, Y) = −∑j

Yij log2 Yij (5.3)

= −∑j

δui,Σjlog2 Yij (5.4)

= − log2 Yi ord(ui) (5.5)

onde utilizamos o fato de δui,Σj= 0 exceto em j = ord(ui). Em outras palavras, a entropia

associada ao classificador da posição i é o negativo do logaritmo da probabilidade preditapara o caractere correto nessa posição. Definimos o custo esperado por caractere doclassificador i em D como

J(D)i = 〈Hi(Y, Y)〉D (5.6)

e custo esperado por token como a média dos erros em cada posição, ou seja:

J (D) = 〈J (D)i 〉{i}. (5.7)

Durante o treino tentaremos minimizar a 5.6 para cada classificador, e o custo totalassociado aos erros cometidos pelo modelo é calculado pela equação 5.7.

Uma estimativa da probabilidade de acerto por caractere é dada pela acurácia decada classificador, isto é, o número de acertos do caractere i no conjunto D, representadopor Ni, normalizado pelo tamanho do conjunto D:

p(D)i = acc

(D)i = Ni

|D|. (5.8)

Estimamos a probabilidade de acerto do token através da acurácia do modelo pelaequação:

p(D)u = Nu

|D|, (5.9)

onde Nu é o número de tokens preditos corretamente.

Quanto ao tempo da dinâmica de aprendizado, definimos, para cada época t, otempo de treino por época, τ , como sendo o tempo gasto durante a etapa de treinonessa época e o tempo total de uma época, τ , com a soma dos tempos gastos comtreino e validação nesta época.

44

6 Resultados e Discussão

Neste capítulo apresentamos e analisamos os dados dos experimentos realizadoscom as configurações de rede propostas. Na seção 6.1 analisamos o comportamento dasarquiteturas durante as épocas iniciais. Na seção 6.2, a configuração de rede escolhida éapresentada e sua performance comparada com o trabalho de referência. Na última seçãoapresentamos nossas discussão sobre a eficácia do método proposto.

6.1 Experimentos PreliminaresComo descrito no capítulo 4, as configurações propostas foram treinadas durante as

10 primeiras épocas para os valores de lr = 10−η, com η = 1, 2, 3, 4, 5. Na tabela 8 vemoso tamanho, o tempo médio na fase de treino e o tempo médio total por época de algumasdas configurações propostas. O desvio padrão relativo é menor do que 0.1% em todas asmédias. Em geral, a etapa de treino constitui de 70% a 85% do tempo total de uma época.

Tabela 8 – Comparação do tempo de treino entre as arquiteturas.

modelo tamanho(parâmetros)

τ

(segundos)τ

(segundos)(a) M 5.4 106 72.63 100.97(b) MD 5.4 106 75.96 108.14(c) C6M 2.4 106 66.96 91.24(d) C6MD 2.4 106 71.19 97.57

(e) C6C12MD 4.4 106 238.66 291.03(f) C6C12Fl100MD 2.4 106 311.42 357.51(g) C6C12C36C36MD 4.5 105 249.53 302.44

(h) C6C12C36C36Fl100MD 2.9 105 256.97 308.77

A partir da tabela podemos ver que o tempo consumido para o treino de uma con-figuração depende não apenas da quantidade de parâmetros, mas também da arquitetura.As arquiteturas C6M e C6C12Fl100MD, por exemplo, possuem aproximadamente o mesmonúmero de parâmetros, sendo a última, entretanto, pelo menos quatro vezes mais lenta.Em todas as configurações estudadas, a adição do dropout aumentou ligeiramente o tempode treino (entre 4% e 19%), mostrando-se uma operação computacionalmente barata.Operações de maxpooling (ver apêndice B), entretanto, mostraram-se computacionalmentecustosas, aumentando a demanda de tempo em mais de duas vezes para algumas arquitetu-ras. Chamamos a atenção para o fato de que a relação entre as camadas é tão importante

Capítulo 6. Resultados e Discussão 45

para o tamanho e tempo de execução quanto a especificação da camada em sí. No par(d)-(e), por exemplo, a adição de uma camada convolucional aumentou consideravelmenteo tamanho e o tempo de execução. Nesse caso, os canais extras adicionados aumentaramsubstancialmente o número de sinais de entrada na camada densa seguinte. No par (e)-(f),por outro lado, a camada densa reduz drasticamente a quantidade de sinais (de 24192para 100), reduzindo o tamanho da entrada da camada multi-caractere seguinte, adicio-nando, entretanto, uma maior de demanda de tempo. Em geral, podemos estabelecer quecamadas densas normalmente demandam mais tempo, enquanto camadas convolucionais,usualmente reduzem o número de sinais e tamanho total da arquitetura, mas o impactoexato precisa ser estimado em concordância demais camadas. Para comparação, o modelono estudo de Pinto(34) possui, aproximadamente, 13 vezes o tamanho do maior e 250vezes o do menor modelo proposto em nossos experimentos.

Na figura 8 podemos ver a evolução da função custo no conjunto de validaçãodurante as 10 primeiras épocas para as arquiteturas na tabela 8 e valores η = 1, 2, 3, 4, 5.Para η = 1 e η = 2, vemos que o custo atinge um platô já durante as primeiras épocasda dinâmica. A estagnação em J é um indicativo de que o gradiente da função de custocresce de forma descontrolada. Quando isso ocorre, o algoritmo adaptativo Adam tendea privilegiar as atualizações em uma direção no espaço de {Θ}, anulando-as nas demais.Mais precisamente, antes das atualizações, o algoritmo normaliza ∇ΘJ pelo módulo dogradiente acumulado nos últimos lotes. Assim, se |∇ΘJ | → ∞, ∆Θ → 0, exceto nasregiões onde o gradiente é proporcional ao seu momento. Em outras palavras, o algoritmosuperestima o erro em uma determinada direção um detrimento das demais. Isso leva arede a cometer os mesmos erros repetidamente nas direções não atualizadas. É importanteressaltar que quando esse fenômeno ocorre em algoritmos onde essa normalização não éaplicada (como o método do gradiente, por exemplo), o gradiente e os parâmetros tambémcrescem de forma descontrolada, evidenciado por uma divergência na função de custo.A dinâmica da função de custo nas redes M e MD corroboram para essa interpretação.No gráfico dessas arquiteturas podemos observar um aumento significativo no valor de Jantes das atualizações cessarem. Para uma análise mais precisa teríamos de acompanhara evolução de Θ ao longo do treino, o que esta fora do escopo do presente trabalho. Nooutro extremo, η = 5, vemos um comportamento similar durante as épocas iniciais paraalgumas arquiteturas (c-h). Entretanto, a aparente estagnação nesses casos é devida àlenta convergência causada por esse valor do hiper-parâmetro. De fato, observamos umamelhoria no valor de J na sequência da dinâmica. Desta forma, os valores η = 1, 2 e 5apresentam comportamentos que devem ser evitados durante o treino, definindo, assim, oslimites práticos para a busca do melhor hiper-parâmetro de aprendizado neste problema.

Dentro da região de interesse, o valor η = 4 exibe as dinâmicas mais estáveis, ondea função de custo apresenta um comportamento monotonicamente decrescente durantetoda dinâmica, eventualmente estagnando, como visto em (a-d). Para as demais redes (d-h)


Figura 8 – Dinâmica inicial de arquiteturas selecionadas.

0 2 4 6 8 10

10−1

100

101

(a) Mη = 1

η = 2

η = 3

η = 4

η = 5

0 2 4 6 8 10

10−1

100

101

(b) MDη = 1

η = 2

η = 3

η = 4

η = 5

0 2 4 6 8 10

10−1

100(c) C6M

η = 1

η = 2

η = 3

η = 4

η = 5

0 2 4 6 8 10

10−1

(d) C6MD

η = 1

η = 2

η = 3

η = 4

η = 5

log( J

(Dv

al))

0 2 4 6 8 10

10−1

100

(e) C6C12MD

η = 1

η = 2

η = 3

η = 4

η = 5

0 2 4 6 8 10

10−1

(f) C6C12Fl100MD

η = 1

η = 2

η = 3

η = 4

η = 5

0 2 4 6 8 10

10−1

(g) C6C12C36C36MD

η = 1

η = 2

η = 3

η = 4

η = 5

0 2 4 6 8 10

10−1

(h) C6C12C36C36Fl100MD

η = 1

η = 2

η = 3

η = 4

η = 5

t (épocas)

Nos gráficos apresentamos a função custo na escala logarítmica de modo a facilitar a visualização.Os traços são apenas guias visuais. As arquiteturas estão indicadas nos títulos em correspondênciacom a tabela 8 e os valores do hiper-parâmetro de aprendizado estão indicados na legenda.


percebemos que o valor da função de custo ainda apresentaria melhoras caso continuássemosa evolução por mais épocas. Para η = 3, vemos que a dinâmica é, de fato, mais rápida nasarquiteturas (c-h). Contudo, esse valor leva a instabilidades e, eventualmente, pioras novalor da função de custo (visto de (a) a (f) e mais acentuadamente em (c)). Esse fenômenode overfitting foi discutido previamente no capítulo 3. Nestes casos, o comportamentopode ser explicado por uma possível memorização dos exemplos de treino, ou seja, essevalor do hiper-parâmetro tende a superestimar os erros cometidos em casos específicos,levando à um cenário de coadaptação. Concluímos, então, que os valores lr = 10−3 e 10−4

são os que apresentam o melhor compromisso entre velocidade de treino e estabilidade,respectivamente. Em seguida, analisaremos de forma mais detalhada essas configurações.

Tabela 9 – Comparação entre as arquiteturas na décima época.

modelo lrDtr Dval J(Dval)

J(Dtr) − 1J pu J pu

(a) M 10−3 1.81 10−1 0.37 3.98 10−1 0.21 1.2010−4 4.77 10−2 0.53 9.34 10−2 0.30 0.96

(b) MD10−3 1.50 10−1 0.44 3.31 10−1 0.26 1.2010−4 7.59 10−2 0.49 1.17 10−1 0.35 0.55

(c) C6M10−3 2.88 10−3 0.96 1.20 10−1 0.49 40.4910−4 2.41 10−2 0.74 7.34 10−2 0.41 2.05

(d) C6MD10−3 2.80 10−3 0.96 6.56 10−2 0.56 22.4010−4 3.27 10−2 0.72 6.02 10−2 0.51 0.84

(e) C6C12MD10−3 2.33 10−3 0.96 4.49 10−2 0.68 18.2410−4 2.12 10−2 0.81 4.21 10−2 0.65 0.99

(f) C6C12Fl100MD10−3 1.99 10−2 0.74 4.34 10−2 0.60 1.1810−4 2.10 10−2 0.78 4.16 10−2 0.62 0.98

(g) C6C12C36C36MD10−3 6.93 10−3 0.92 1.61 10−2 0.86 1.3310−4 2.32 10−2 0.81 2.91 10−2 0.76 0.25

(h) C6C12C36C36Fl100MD10−3 1.06 10−2 0.86 1.66 10−2 0.81 0.5710−4 1.81 10−2 0.81 2.52 10−2 0.75 0.40

Pinto(34) - - 0.95 - 0.77 -

A última linha foi reproduzida do trabalho em (34) que utilizou uma rede equivalente àC64C128C256C512MaxFl4096MD e 25 épocas em nossa nomenclatura.

Para melhor visualizar os modelos treinados com esses valores de lr fixos, compilamosna tabela 9 o valor da função de custo, a acurácia do modelo para os conjuntos de validaçãoe treino e o valor relativo do custo entre esses dois conjunto, dado por J (Dval)/J (Dtr) − 1,para as arquiteturas na tabela 8. Todos os valores na tabela foram medidos na décimaépoca de treino. Na última linha temos o valor reportado por Pinto(34) para comparação. A


partir da tabela, a análise do valor relativo do custo (última coluna) denuncia a ocorrênciade overffiting nos modelos (c), (d) e (e). De fato, estes foram os modelos que alcançarama maior acurácia no conjunto de treino não apresentando, entretanto, uma performanceexpressiva no conjunto de validação. Comparando os pares (a)-(b) e (c)-(d) podemos ver quea adição de dropout contribuiu de forma significativa para o controle da coadaptação dosparâmetros da rede. Comportamento semelhante foi observado em todas as comparaçõesfeitas entre modelos com e sem regularização (ver apêndice A). Nas redes treinadas commaxpooling, notamos, em geral, puco impacto ou até mesmo degradação na acurácia dosmodelos quando defrontados com seus análogos com agrupamento fixo (ver apêndiceA). No geral, a adição de camadas convolucionais melhoraram o desempenho das redesao mesmo tempo em que limitaram a quantidade de parâmetros a serem optimizados.Nos pares (e)-(f) e (g)-(h), vemos que a adição de uma camada totalmente conectadadeteriorou o desempenho. Este é um indicativo de que a adição arbitrária de camadas nãonecessariamente se traduz em arquiteturas mais expressivas.

Na última linha da tabela temos a precisão reportada no estudo de referência.Através da comparação com as configurações de rede utilizados no referido trabalho,podemos demonstrar a importância do estudo comparativo no projeto de redes neurais.Fomos capazes de obter resultados muito mais expressivos utilizando menos exemplos eredes mais simples. Em particular, nosso melhor resultado nos experimentos foi obtido emuma rede com 150 vezes menos parâmetros e uma base de treino 9 vezes menor. No estudode referência estão presentes também fortes indicativos de coadaptação nos parâmetros. Aacurácia reportada pelo autor é 23% maior no conjunto de treino do que no de validação,a despeito da aplicação de regularização com norma L2 e dropout de 50%, sendo essesforte indicativos de memorização da base de treino.

6.2 Treino completoAssim com descrito na seção 4.1, escolhemos uma das configurações propostas

para realizar um treino completo. Vamos definir como critério de escolha a eficiência derepresentação alcançada pela arquitetura, isto é, escolher a configuração que conseguealcançar o menor custo esperado com o uso de menos parâmetros. A escolha é fundamentadaem duas considerações: a Navalha de Occam e a generalidade de uso. A primeira nosleva a preterir soluções mais simples em detrimento das mais complexas, traduzindo-se,neste caso, em uma preferência por arquitetura de menos parâmetros. A segunda vem daobservação de que em diferentes arquiteturas computacionais a memória é usualmenteum fator limitante. Em sistemas embarcados ou smartphones, por exemplo, esse seria umfator determinante para a escolha. De outra forma, com esta escolha estamos definindoque uma acurácia um pouco menor e alguns milissegundos a mais para a classificação deum token são trocas aceitáveis. A partir da tabela 9 vemos que as configurações (g) e (h)


apresentam um valor muito similar no valor esperado da função de custo, sendo (h) aescolhida por possuir menos parâmetros. Outros requisitos levariam a escolhas diferentes.Frisamos que é possível estimar de antemão o tempo máximo de treino multiplicando onúmero de épocas máximas pelo tempo médio por época na tabela 8.

O modelo C6C12C36C36Fl100MD foi treinado até a quinquagésima época e a di-nâmica do custo e da acurácia (total e por caractere) podem ser vistas na figura 9. Em(i) vemos que o custo, no intervalo de épocas estudado, é uma função decrescente notempo, comprovando a eficácia do método utilizado para a escolha da taxa de aprendizado.Notamos ainda que a inclinação na curva para o custo sugere que o modelo continuariaapresentando ganhos de performance caso o treino fosse continuado, evidenciando a escolhade uma configuração com boa expressividade. Isso nos permitiria obter um modelo aindamais preciso, caso fosse necessário. Ressaltamos que o treino atingiu o número máximode épocas predefinido, sem atingir nenhum dos demais critérios de parada propostos, oque evidência um aprendizado consistente (a média móvel no conjunto de treino é sempredecrescente) e controlado (sem overfitting detectado no conjunto de validação), sendo assimum treino exitoso segundo os critérios definidos na seção 5.2. Em (ii) vemos que o acertopor token apresenta um comportamento inverso ao do custo esperado tanto no conjuntode treino quanto no de validação, sendo tão maior quanto menor for o erro esperado pelomodelo.

Na última época, a acurácia por token foi de 96.06%, sendo o classificador para oprimeiro caractere o que apresentou melhor desempenho de acertos, com acurácia finalde 99.98% e o classificador para o quarto o que apresentou pior desempenho, com umaacurácia final de 97.78%. A comparação entre os gráficos (iii) e (iv) mostram que, assimcomo esperado, o acerto de cada classificador é tão maior quanto menor for o custoassociado. Um detalhe interessante a ser notado é que os caractere mais difíceis de seremidentificados se encontram no meio do token (terceiro e quarto caractere) enquanto oprimeiro classificador apresenta a melhor performance desde o inicio do treino. Apesarde não haver nenhuma forma de provarmos isso no momento, acreditamos que isso sejadevido à facilidade de segmentação dos caracteres nessas posições, sendo o terceiro e oquarto os mais difíceis e o primeiro o mais fácil (vide figura 7 no capítulo 5).

O tempo total de treino foi de aproximadamente 4 horas e 16 minutos (3 horas e33 minutos se descontarmos a etapa de validação), o que está de acordo com a estimativafornecida a partir do tempos médio calculado durante a fase de experimentação na tabela8. Para efeito de comparação, os experimentos do tralho de referência foram realizados emuma máquina com processador Intel R© XeonTME5-2686v4 (Broadwell) de oito núcleos com61 gb memória RAM e placa de aceleração gráfica VIDIA R© K80 com 12 gb de memória,durando aproximadamente 1 hora 18 minutos. Apesar de não podermos realizar umacomparação direta entre esses tempos, é de se notar que o aprendizado do modelo escolhido


na infraestrutura que dispomos foi apenas três vezes mais longo que o aprendizado notrabalho de referência, a despeito da gritante diferença de poder computacional.

Figura 9 – Dinâmica da arquitetura C6C12C36C36Fl100MD.

0 10 20 30 40 50

t (epocas)

10−3

10−2

10−1

log(J)

(i)treino

validacao

0 10 20 30 40 50

t (epocas)

0.0

0.2

0.4

0.6

0.8

1.0

acuracia

(ii)

treino

validacao

0 10 20 30 40 50

t (epocas)

0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

custopor

caractere

(iii)J0

J1

J2

J3

J4

40 42 44 46 48 50

0.000

0.005

0.010

0 10 20 30 40 50

t (epocas)

0.0

0.2

0.4

0.6

0.8

1.0

acuraciapor

caractere

(iv)

p0

p1p2

p3

p4

40 42 44 46 48 500.96

0.98

1.00

(i) custo (escala logarítmica) e (ii) acurácia ao longo das épocas para o conjunto de treino evalidação. (iii) custo e (iv) acurácia por classificador ao longo das épocas para o conjunto devalidação.

6.3 Discussão do MétodoO uso da metodologia proposta mostrou-se eficaz na construção de uma experi-

mentação diversificada de configurações, abrangendo comportamentos substancialmentedistintos entre sí. Essa diversidade foi o que permitiu fundamentar a escolha de umaarquitetura final baseando-se em critérios sólidos, possíveis devido ao pressuposto de com-paração no qual o método se baseia. A configuração escolhida, de fato, demonstrou acuráciasuperior e maior eficiência de representação (menos parâmetros) do que os resultadosdo estudo escolhido como referência, demonstrando que a adição arbitrária de camadasnão necessariamente se traduz em maior poder de expressividade. O resultado tambémcorrobora o pressuposto de que a dinâmica inicial é informativa sobre o comportamentoda rede durante o treino subsequente.


A partir dos experimentos realizados, podemos desenhar as observações que se-guem. Arquiteturas convolucionais mostraram-se extremamente eficazes para o problema.Fixadas as demais configurações de rede, novas camadas convolucionais tendem à produzirmodelos mais expressivos. De fato, esse tipo de camada tem sido aplicada com sucessoem diversos problemas de processamento de imagem. O compartilhamento de parâmetrosnessas camadas ao mesmo tempo reduz o tamanho das arquiteturas e adiciona maiorpoder de expressão aos modelos. Camadas densas mostraram-se eficazes na redução dasrepresentações utilizadas no espaço de características, mas devem ser usadas de formacautelosa. O dropout mostrou-se uma ferramenta eficaz e computacionalmente baratapara combater o overfitting, melhorando a performance dos modelos estudados sem de-gradação significativa no tempo de computação. A operação de agrupamento com valorfixo apresentou tempo de execução menor do que a de maxout, sem grandes diferençasde performance. Comportamentos substancialmente diferentes foram observados a partirda variação da taxa de aprendizado, indo da divergência das redes (altos valores) até aestagnação do aprendizado (baixos valores). Diferentes arquiteturas possuem requisitospróprios e alcançam performances distintas.

Em resumo, o método proposto nos permitiu escolher de forma embasada umaconfiguração de rede que atendesse aos requisitos impostos e ainda apresentasse umaboa performance. Adicionalmente, a análise comparativa nos fornece informações cruciaispara a construções se novas configurações e refinamento dos resultados para o problemaestudado.

52

7 Conclusões e Trabalhos futuros

7.1 ConclusõesNeste trabalho propusemos uma abordagem comparativa entre configurações como

uma forma efetiva de experimentação para redes neurais profundas. A metodologia pro-posta se baseia em princípios simples e visa fornecer ao informações importantes queservem de embasamento para a posterior tomada de decisões no projeto de redes neurais.Adicionalmente, os passos propostos podem ser aplicados em ambientes com restriçõescomputacionais, satisfazendo diferentes limitações de recursos. Aplicado ao problema dequebra de CAPTCHAs baseados em texto sem informação humana, mostramos que épossível obter performances próximas ao estado da arte, a despeito das limitações. Omodelo final escolhido obteve uma acurácia final de 96.06% de acerto por token, utilizandomenos parâmetros, com requisitos de tempo aceitáveis e treinado em um mero computa-dor pessoal. Adicionalmente, a técnica pode ser aplicada de forma iterativa, produzindoresultados mais refinados a cada rodada de experimentos.

7.2 Trabalhos futurosA seguir apresentamos uma lista não exaustiva de possíveis desdobramentos para o

estudo apresentado neste trabalho, separadas por grupos de interesse.

Aperfeiçoamento dos resultados atuais

De acordo com o método proposto, diversos hiper-parâmetros e detalhes das arqui-teturas propostas foram mantidos constantes de forma a permitir uma comparação diretado resultado. Acreditamos que resultados ainda mais expressivos possam ser alcançadosatravés do estudo comparativo dessas variáveis. Dentre elas destacamos o número de canaise o tamanho dos núcleos usados nas camadas. Outra possível melhoria a ser investigadaseria a realização de um treinamento mais longo para a rede selecionada.

Validação do método proposto

Aplicar a mesma abordagem comparativa proposta no presente trabalho à outrosproblemas de processamento de imagem, como detecção de objetos, por exemplo, ou outrasáreas como predição de sequências temporais. Uma aplicação interessante diretamenteligada ao problema de quebra de CAPTCHAs de texto seria estender a nossa definição doproblema de forma a permitir tokens com um número variável de caracteres.

Capítulo 7. Conclusões e Trabalhos futuros 53

Segurança e CAPTCHAs

Durante as pesquisas desenvolvidas nesse trabalho notamos que grandes instituiçõesno Brasil se utilizam de CAPTCHAs de texto como medida de segurança. Dada a acuráciaalcançada pelo modelo escolhido, propomos como um estudo futuro avaliar o quão eficazé a segurança desses sistemas através da validação da acurácia obtida por redes neuraisprofundas aplicadas ao problema. Sugerindo, se possível, melhorias nas técnicas que possamser aplicadas de forma a tornar o ataque mais difícil.

54

Referências

1 ROSENBLATT, F. The perceptron: A probabilistic model for information storage andorganization in the brain. Psychological Review, p. 65–386, 1958. Citado na página 12.

2 GOODFELLOW, I.; BENGIO, Y.; COURVILLE, A. Deep Learning. [S.l.]: MIT Press,2016. Citado 3 vezes nas páginas 12, 20 e 25.

3 SCHMIDHUBER, J. Deep learning in neural networks: An overview. Neural Networks,v. 61, p. 85–117, 2015. Published online 2014; based on TR arXiv:1404.7828 [cs.NE].Citado 3 vezes nas páginas 12, 25 e 27.

4 BARRON, A. R. Universal approximation bounds for superpositions of a sigmoidalfunction. IEEE Trans. Information Theory, v. 39, p. 930–945, 1993. Citado na página 12.

5 ANDONI, A. et al. Learning polynomials with neural networks. In: Proceedings of the31st International Conference on Machine Learning, ICML 2014. Beijing, China: PMLR,2014. v. 32, p. 1908–1916. Disponível em: <http://proceedings.mlr.press/v32/>. Citadona página 12.

6 KRIZHEVSKY, A.; SUTSKEVER, I.; HINTON, G. E. Imagenet classi-fication with deep convolutional neural networks. In: PEREIRA, F. et al.(Ed.). Advances in Neural Information Processing Systems 25. Curran Associ-ates, Inc., 2012. p. 1097–1105. Disponível em: <http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf>. Citado napágina 12.

7 MNIH, V. et al. Human-level control through deep reinforcement learning.Nature, Nature Publishing Group, a division of Macmillan Publishers Limited.,v. 518, n. 7540, p. 529–533, fev. 2015. ISSN 00280836. Disponível em: <http://dx.doi.org/10.1038/nature14236>. Citado na página 12.

8 AHN, L. von et al. Captcha: using hard ai problems for security. In: Advances inCryptology, Eurocrypt. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. v. 2656, p.294–311. Citado 2 vezes nas páginas 12 e 14.

9 CHELLAPILLA, K. et al. Building Segmentation Based Human-Friendly HumanInteraction Proofs (HIPs). [S.l.]: Springer, Berlin, Heidelberg, 2005. v. 3517. 1-26 p.Citado 5 vezes nas páginas 12, 14, 15, 29 e 40.

10 CHOW, Y. W.; SUSILO, W. Text-based captchas over the years. IOP ConferenceSeries: Materials Science and Engineering, v. 273, n. 1, p. 012001, 2017. Disponível em:<http://stacks.iop.org/1757-899X/273/i=1/a=012001>. Citado 2 vezes nas páginas 12e 17.

11 YAN, J.; AHMAD, A. S. E. Breaking visual captchas with naive pattern recognitionalgorithms. p. 279–291, 01 2008. Citado 2 vezes nas páginas 12 e 15.

12 GOODFELLOW, I. J. et al. Multi-digit number recognition from street view imageryusing deep convolutional neural networks. CoRR, abs/1312.6082, 2013. Disponível em:<http://arxiv.org/abs/1312.6082>. Citado 5 vezes nas páginas 12, 15, 16, 30 e 32.

http://proceedings.mlr.press/v32/

http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf

http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf

http://dx.doi.org/10.1038/nature14236

http://dx.doi.org/10.1038/nature14236

http://stacks.iop.org/1757-899X/273/i=1/a=012001

http://arxiv.org/abs/1312.6082

Referências 55

13 GEORGE, D. et al. A generative vision model that trains with high dataefficiency and breaks text-based captchas. Science, American Association forthe Advancement of Science, 2017. ISSN 0036-8075. Disponível em: <http://science.sciencemag.org/content/early/2017/10/26/science.aag2612>. Citado 3 vezesnas páginas 12, 30 e 32.

14 BURSZTEIN, E. et al. The end is nigh: Generic solving of text-based captchas. In:WOOT. [S.l.: s.n.], 2014. Citado na página 13.

15 SINGH, V. P.; PAL, P. Survey of different types of captcha. International Journal ofComputer Science and Information Technologies, v. 5, n. 2, p. 2242–2245, 2014. Citadona página 14.

16 SECURIMAGE. An open-source free PHP CAPTCHA script f. 2018. Disponível em:<https://www.phpcaptcha.org/>. Acesso em: 23/06/2018. Citado na página 14.

17 AHN, L. von et al. recaptcha: Human-based character recognition via web securitymeasures. v. 321, p. 1465–8, 09 2008. Citado na página 15.

18 SIVAKORN, S.; POLAKIS, I.; KEROMYTIS, A. D. I am robot: (deep) learning tobreak semantic image captchas. In: . [S.l.]: IEEE, 2016. p. 388–403. Citado na página 16.

19 BURSZTEIN, E.; MARTIN, M.; MITCHELL, J. Text-based captcha strengthsand weaknesses. In: Proceedings of the 18th ACM Conference on Computer andCommunications Security. New York, NY, USA: ACM, 2011. (CCS ’11), p. 125–138. ISBN978-1-4503-0948-6. Disponível em: <http://doi.acm.org/10.1145/2046707.2046724>.Citado 2 vezes nas páginas 17 e 29.

20 GERSTNER, W. et al. Neuronal dynamics: From single neurons to networksand models of cognition. Cambridge University Press, 2014. Disponível em:<http://neuronaldynamics.epfl.ch/>. Acesso em: 23/06/2018. Citado na página 20.

21 LECUN, Y. et al. Backpropagation applied to handwritten zip code recognition.Neural Comput., MIT Press, Cambridge, MA, USA, v. 1, n. 4, p. 541–551, dez. 1989.ISSN 0899-7667. Disponível em: <http://dx.doi.org/10.1162/neco.1989.1.4.541>. Citadona página 21.

22 LECUN, Y. et al. Gradient-based learning applied to document recognition. In:Proceedings of the IEEE. [S.l.: s.n.], 1998. v. 86, p. 2278 – 2324. Citado na página 21.

23 LEE, H.; EKANADHAM, C.; NG, A. Y. Sparse deep belief net model for visual areav2. In: Advances in neural information processing systems. [S.l.: s.n.], 2008. p. 873–880.Citado na página 25.

24 GATYS, L. A.; ECKER, A. S.; BETHGE, M. Texture synthesis using convolutionalneural networks. In: Proceedings of the 28th International Conference on Neural InformationProcessing Systems - Volume 1. Cambridge, MA, USA: MIT Press, 2015. (NIPS’15), p.262–270. Disponível em: <http://dl.acm.org/citation.cfm?id=2969239.2969269>. Acessoem: 23/06/2018. Citado na página 25.

25 GATYS, L. A.; ECKER, A. S.; BETHGE, M. Image style transfer using convolutionalneural networks. In: Proceedings of the IEEE Conference on Computer Vision and PatternRecognition. [S.l.: s.n.], 2016. p. 2414–2423. Citado na página 25.

http://science.sciencemag.org/content/early/2017/10/26/science.aag2612

http://science.sciencemag.org/content/early/2017/10/26/science.aag2612

https://www.phpcaptcha.org/

http://doi.acm.org/10.1145/2046707.2046724

http://neuronaldynamics.epfl.ch/

http://dx.doi.org/10.1162/neco.1989.1.4.541

http://dl.acm.org/citation.cfm?id=2969239.2969269

Referências 56

26 SABOUR, S.; FROSST, N.; HINTON, G. E. Dynamic routing between capsules.In: Advances in Neural Information Processing Systems. [S.l.: s.n.], 2017. p. 3856–3866.Citado na página 25.

27 KINGMA, D. P.; BA, J. Adam: A method for stochastic optimization. CoRR,abs/1412.6980, 2014. Disponível em: <http://arxiv.org/abs/1412.6980>. Citado 2 vezesnas páginas 26 e 41.

28 FRIEDMAN, J.; HASTIE, T.; TIBSHIRANI, R. The elements of statistical learning.[S.l.]: Springer series in statistics New York, NY, USA:, 2001. v. 1. Citado na página 27.

29 HINTON, G. E. et al. Improving neural networks by preventing co-adaptation of featuredetectors. CoRR, abs/1207.0580, 2012. Disponível em: <http://arxiv.org/abs/1207.0580>.Citado na página 29.

30 YANN, L.; CORINNA, C.; CHRISTOPHER, J. The MNIST database of handwrittendigits. 1998. Disponível em: <http://yann.lecun.com/exdb/mnist>. Acesso em:23/06/2018. Citado na página 30.

31 Cireşan, D.; Meier, U.; Schmidhuber, J. Multi-column Deep Neural Networks forImage Classification. CoRR, fev. 2012. Citado na página 30.

32 NETZER, Y. et al. Reading digits in natural images with unsupervised featurelearning. In: NIPS workshop on deep learning and unsupervised feature learning. [S.l.: s.n.],2011. v. 2011, n. 2, p. 5. Citado 2 vezes nas páginas 30 e 32.

33 SERMANET, P.; CHINTALA, S.; LECUN, Y. Convolutional neural networks appliedto house numbers digit classification. In: IEEE. Pattern Recognition (ICPR), 2012 21stInternational Conference on. [S.l.], 2012. p. 3288–3291. Citado 2 vezes nas páginas 30e 32.

34 PINTO, V. A. Redes Neurais Convolucionais de Profundidade Para Reconhecimentode Texto em Imagens de CAPTCHA. Florianópolis, Santa Catarina.: UNIVERSIDADEFEDERAL DE SANTA CATARINA - DEPARTAMENTO DE INFORMÁTICA EESTATÍSTICA, 2016. Disponível em: <https://repositorio.ufsc.br/xmlui/handle/123456789/171436>. Acesso em: 23/06/2018. Citado 4 vezes nas páginas 31, 32, 45 e 47.

35 SIMPLECAPTCHA. A CAPTCHA Framework for Java. 2018. Disponível em:<http://simplecaptcha.sourceforge.net/>. Acesso em: 23/06/2018. Citado na página 40.

36 HE, K. et al. Delving deep into rectifiers: Surpassing human-level performanceon imagenet classification. CoRR, abs/1502.01852, 2015. Disponível em: <http://arxiv.org/abs/1502.01852>. Citado na página 42.

37 PRECHELT, L. Automatic early stopping using cross validation: Quantifying thecriteria. v. 11, p. 761–767, 06 1998. Citado na página 42.

38 ABADI, M. et al. Tensorflow: a system for large-scale machine learning. In:OSDI. Savannah, GA, USA: [s.n.], 2016. v. 16, p. 265–283. ISBN 978-1-931971-33-1.Disponível em: <http://download.tensorflow.org/paper/whitepaper2015.pdf>. Acesso em:23/06/2018. Citado na página 42.



http://yann.lecun.com/exdb/mnist

https://repositorio.ufsc.br/xmlui/handle/123456789/171436

https://repositorio.ufsc.br/xmlui/handle/123456789/171436

http://simplecaptcha.sourceforge.net/



http://download.tensorflow.org/paper/whitepaper2015.pdf

57

A Configurações com lr = 10−3 e 10−4 nadécima época.



M10−3 1.81 10−1 0.37 3.98 10−1 0.21 1.2010−4 4.77 10−2 0.53 9.34 10−2 0.30 0.96

MD10−3 1.50 10−1 0.44 3.31 10−1 0.26 1.2010−4 7.59 10−2 0.49 1.17 10−1 0.35 0.55

C6M10−3 2.88 10−3 0.96 1.20 10−1 0.49 40.4910−4 2.41 10−2 0.74 7.34 10−2 0.41 2.05

C6MD10−3 2.80 10−3 0.96 6.56 10−2 0.56 22.4010−4 3.27 10−2 0.72 6.02 10−2 0.51 0.84

C6MMax10−3 2.26 10−3 0.97 1.01 10−1 0.54 43.5610−4 1.93 10−2 0.79 6.63 10−2 0.47 2.43

C6C12M10−3 2.16 10−3 0.97 8.50 10−2 0.64 38.4310−4 1.45 10−2 0.81 6.15 10−2 0.54 3.23

C6C12MD10−3 2.33 10−3 0.96 4.49 10−2 0.68 18.2410−4 2.12 10−2 0.81 4.21 10−2 0.65 0.99

C6C12MMax10−3 3.49 10−3 0.95 7.89 10−2 0.64 21.5810−4 1.24 10−2 0.83 5.60 10−2 0.57 3.50

C6C12Fl100M10−3 1.00 10−2 0.85 6.95 10−2 0.57 5.9510−4 3.28 10−2 0.62 7.07 10−2 0.40 1.15

C6C12Fl100MD10−3 1.99 10−2 0.74 4.34 10−2 0.60 1.1810−4 2.10 10−2 0.78 4.16 10−2 0.62 0.98

C6C12Fl100MMax10−3 4.88 10−2 0.46 1.14 10−1 0.27 1.3310−4 8.87 10−2 0.19 1.09 10−1 0.13 0.23

Apêndice A. Configurações com lr = 10−3 e 10−4 na décima época. 58

(Continuação)



C6C12C36C36M10−3 4.61 10−3 0.93 3.19 10−2 0.80 5.9110−4 1.86 10−2 0.78 4.19 10−2 0.63 1.26

C6C12C36C36MD10−3 6.93 10−3 0.92 1.61 10−2 0.86 1.3310−4 2.32 10−2 0.81 2.91 10−2 0.76 0.25

C6C12C36C36MMax10−3 8.19 10−3 0.89 3.47 10−2 0.76 3.2410−4 1.39 10−2 0.83 3.58 10−2 0.71 1.58

C6C12C36C36Fl100M10−3 1.02 10−2 0.86 2.61 10−2 0.76 1.5610−4 1.56 10−2 0.80 3.46 10−2 0.67 1.22

C6C12C36C36Fl100MD10−3 1.06 10−2 0.86 1.66 10−2 0.81 0.5710−4 1.81 10−2 0.81 2.52 10−2 0.75 0.40

C6C12C36C36Fl100MMax10−3 9.67 10−3 0.87 2.32 10−2 0.79 1.3910−4 1.40 10−2 0.82 3.21 10−2 0.70 1.28

59

B Descrição completa das arquiteturas.

M [D]

M τ = 726.29(+0.00%), τ = 1009.74(+0.00%)Camada Descrição Entrada Saída Parâmetros

Lin - (50,200,3) (30000) 0M 5 classificadores. (30000) (5,36) 5400000total 5400000

MD τ = 759.56(+4.58%), τ = 1081.43(+7.10%)Camada Descrição Entrada Saída Parâmetros

Lin - (50,200,3) (30000) 0Dropout Dropout com pdrop = 30%. (30000) (30000) 0

M 5 classificadores. (30000) (5,36) 5400000total 5400000

C6M [D][Max]

C6M τ = 669.60(+0.00%), τ = 912.38(+0.00%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de entrada

e 6 de saída. Passo da transformação2.

(50,200,3) (23,98,6) 450


C6MD τ = 711.85(+6.31%), τ = 975.67(+6.94%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de entrada

e 6 de saída. Passo da transformação2.

(50,200,3) (23,98,6) 450

Lin - (23,98,6) (13524) 0Dropout Dropout com pdrop = 30%. (13524) (13524) 0


Apêndice B. Descrição completa das arquiteturas. 60

C6MMax τ = 1334.50(+99.30%), τ = 1652.03(+81.07%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de entrada

e 6 de saída. Passo da transformação 2.Maxout.

(50,200,3) (23,98,6) 450


C6C12M [D][Max]

C6C12M τ = 2138.93(+0.00%), τ = 2547.99(+0.00%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-

trada e 6 de saída. Passo da trans-formação 1.

(50,200,3) (46,196,6) 450

C12 Convolucional com 6 canais de en-trada e 12 de saída. Passo da trans-formação 2.

(46,196,6) (21,96,12) 1800


C6C12MD τ = 2386.58(+11.58%), τ = 2910.10(+14.21%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450

Dropout Dropout com pdrop = 30%. (46,196,6) (46,196,6) 0C12 Convolucional com 6 canais de en-


(46,196,6) (21,96,12) 1800

Dropout Dropout com pdrop = 30%. (21,96,12) (21,96,12) 0Lin - (21,96,12) (24192) 0M 5 classificadores. (24192) (5,36) 4354560total 4356810


C6C12MMax τ = 3821.52(+78.67%), τ = 4365.97(+71.35%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-

trada e 6 de saída. Passo da trans-formação 1. Maxout.

(50,200,3) (46,196,6) 450

C12 Convolucional com 6 canais de en-trada e 12 de saída. Passo da trans-formação 2. Maxout.

(46,196,6) (21,96,12) 1800


C6C12Fl100M [D][Max]

C6C12Fl100M τ = 2873.60(+0.00%), τ = 3219.16(+0.00%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1800

Lin - (21,96,12) (24192) 0Fl100 Camada densa com 24192 sinais de

entrada e 100 sinais de saída.(24192) (100) 2419200



C6C12Fl100MD τ = 3114.23(+8.37%), τ = 3575.14(+11.06%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450



(46,196,6) (21,96,12) 1800

Dropout Dropout com pdrop = 30%. (21,96,12) (21,96,12) 0Lin - (21,96,12) (24192) 0Fl100 Camada densa com 24192 sinais de



C6C12Fl100MMax τ = 4563.22(+58.80%), τ = 5045.06(+56.72%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1800

Lin - (21,96,12) (24192) 0Fl100 Camada densa com 24192 sinais de




C6C12C36C36M [D][Max]

C6C12C36C36M τ = 2191.11(+0.00%), τ = 2580.79(+0.00%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1800


(21,96,12) (9,46,36) 10800


(9,46,36) (3,21,36) 32400


C6C12C36C36MD τ = 2495.31(+13.88%), τ = 3024.40(+17.19%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450



(46,196,6) (21,96,12) 1800



(21,96,12) (9,46,36) 10800



(9,46,36) (3,21,36) 32400

Dropout Dropout com pdrop = 30%. (3,21,36) (3,21,36) 0Lin - (3,21,36) (2268) 0M 5 classificadores. (2268) (5,36) 408240total 453690


C6C12C36C36MMax τ = 5099.87(+132.75%), τ = 5718.50(+121.58%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1800


(21,96,12) (8,46,36) 10800


(8,46,36) (2,21,36) 32400


C6C12C36C36Fl100M [D][Max]

C6C12C36C36Fl100M τ = 2262.46(+0.00%), τ = 2625.29(+0.00%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1800


(21,96,12) (9,46,36) 10800


(9,46,36) (3,21,36) 32400

Lin - (3,21,36) (2268) 0Fl100 Camada densa com 2268 sinais de en-

trada e 100 sinais de saída.(2268) (100) 226800



C6C12C36C36Fl100MD τ = 2568.47(+13.53%), τ = 3086.29(+17.56%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450



(46,196,6) (21,96,12) 1800



(21,96,12) (9,46,36) 10800



(9,46,36) (3,21,36) 32400

Dropout Dropout com pdrop = 30%. (3,21,36) (3,21,36) 0Lin - (3,21,36) (2268) 0Fl100 Camada densa com 2268 sinais de en-



C6C12C36C36Fl100MMax τ = 5159.74(+128.06%), τ = 5769.04(+119.75%)Camada Descrição Entrada Saída ParâmetrosC6 Convolucional com 3 canais de en-


(50,200,3) (46,196,6) 450


(46,196,6) (21,96,12) 1800


(21,96,12) (8,46,36) 10800


(8,46,36) (2,21,36) 32400

Lin - (2,21,36) (1512) 0Fl100 Camada densa com 1512 sinais de en-



Documents

Aprendizado profundo com capacidade computacional reduzida