Arquivo da tag: Estatística

O que é deep learning?

Rookie

Moda é algo difícil de explicar. Em ciência e tecnologia, todo ano temos assuntos que são mais comentados, esperados, publicados, as modinhas científicas do momento. Em 2000 tínhamos a palavra cyber, em 2005 era a web 2.0, em 2010 só se falava em big data. De todas essas modas, nunca vi nada parecido com a atual. Ela transcende a moda, vejo-a em artigos de física, matemática, informática, na mídia, em palestras, até na apresentação do próximo telefone que vou comprar. Como ela faz parte de meu trabalho, chegou o momento de explicar o que é deep learning. Vou tentar fazer isso com a menor quantidade de matemática que consigo, deixo para outro post a explicação com matemática pura, sem gelo e sem limão. Primeiro, explico o que é essa história de learning. Depois, explico o que o deep quer dizer.

Essa história de learning

Aprender é ver alguém fazendo alguns exemplos e conseguir não apenas reproduzir o que viu, mas aplicar o que viu em casos que ainda não viu. Essa capacidade de lidar com casos não vistos durante o treinamento é a marca do aprendizado genuíno, chamamos isso de generalização. Em poucas palavras: entendimento é previsão que pode ser generalizada. Um aluno que só é capaz de resolver na prova as questões que ele viu na lista de exercícios não aprendeu nada. Ele memoriza, mas não entende.

Uma prova pode ser entendida, matematicamente, como uma função que leva perguntas em respostas. Todo aprendizado estatístico, seja deep learning, machine learning ou reinforcement learning, consiste apenas nisso: associar uma resposta a uma pergunta, achar a melhor função que leva nossas questões às boas soluções tanto nas situações em que nosso modelo foi treinado (a lista de exercícios), mas para outras situações em que ele não foi treinado (a prova final).

Então toda essa história de machine learning e deep learning é a arte de achar a melhor função para explicar um conjunto de dados. Em espírito, não são muito diferentes de, dados alguns pontos, encontrar a melhor reta que passa por eles. Toda a literatura científica desse meio, se você quiser ofender quem trabalha na área, pode ser resumida em técnicas mais ou menos sofisticadas que traçar retas complicadas por uma quantidade bem grande de pontos.

Vamos direto para o exemplo, então. Precisamos de pontos para traçar uma função, e eu proponho esses:

O problema é bem simples: precisamos da melhor função que poderia servir como o “modelo teórico” que gerou esses dados. Nossa mentalidade é a de que existe um mecanismo subjacente simples o suficiente para ser expresso com uma função, a que buscamos, e a diferença entre os pontos de nossa experiência e nossa função vem apenas de pequenas flutuações naturais que não conseguimos, ou não pretendemos, explicar ou incluir no modelo. Como se esses pontos fossem nossas medidas de quanto tempo um peso leva para chegar ao chão em função da altura que deixamos ele cair. Existe uma lei por trás disso, a da gravidade, mas há pequenas flutuações possíveis no resultado quando faço a experiência: minha velocidade de reação no cronômetro, resistência do ar ou o erro mecânico do relógio.

Sem um modelo, fica bem difícil resolver esse problema. Tenho muitas opções para explicar esses pontos, eis algumas:

Todo caminho é bom para quem não sabe para onde ir. Não vou entrar em detalhes de como escolher uma dessas opções se você não conhece muita coisa sobre o modelo, vou apenas pegar o caso mais simples e supor que o modelo certo é uma reta. Para descobrir qual a melhor das retas possíveis, preciso especificar dois parâmetros: inclinação e altura. Existem maneiras de encontrar exatamente, com apenas uma equação, quais parâmetros criam a reta que mais bem explica os dados ((Para quem fez exatas, o método dos mínimos quadrados está aí para isso)),  mas não pretendo usar uma dessas soluções exatas. Elas só funcionam quando o problema é fácil, como traçar uma reta, qualquer método ligeiramente mais sofisticado precisa de ajuda que nenhuma resolução exata consegue fornecer. Vamos usar uma abordagem iterativa, mais parecida com o que o deep learning usa, e muito mais próxima do conceito de aprendizado.

Nossa reta terá dois parâmetros: $\alpha$ e $\beta$. Nosso modelo será descrito pela equação $y = \alpha x + \beta$, preciso apenas encontrar os parâmetros que fazem dessa curva a melhor possível. Pense nesses parâmetros como um botão daqueles de aparelhos de som profissionais, que você pode aumentar e diminuir gradualmente. Eu começo com os valores dos parâmetros aleatórios. O resumo da estratégia é: pego um ponto, vejo se acertei. Se errei, o que é provável, vejo para que lado tenho que girar o botão de cada parâmetro para melhorar o resultado. Giro e repito o processo para o próximo ponto.

A ideia é bem simples: tento, erro, vejo para onde devia andar para errar menos, ando, repito o processo. O quanto eu mexo do botão a cada iteração, o tamanho do passo que dou, varia e depende de meu problema. Nesse contexto, chamamos de taxa de aprendizado, ou learning rate, porque tudo é importado do inglês nesse meio; e o nome da técnica é descida de gradiente (chamamos de gradiente a direção que temos que mexer os parâmetros para diminuirmos o erro do modelo). Vamos aplicar essa técnica em nosso problema:

A ideia é mais simples do que parece. Começamos com um ponto aleatório, e por acaso pegamos o segundo ponto. Traçamos uma reta qualquer. Depois, pegamos outro ponto ao acaso, que foi o sétimo, e corrigimos a reta para também passar nele. Em seguida, pegamos outro ponto e fazemos a reta andar mais na direção dele. Essa direção é guiada pelo sentido do erro calculado usando a reta como modelo. Se o erro é positivo, enviamos a reta mais para baixo. Se é negativo, mandamos a reta mais para cima. Depois de usar vários pontos, a reta muda pouco e temos um modelo que tenta, na medida do possível, satisfazer todo mundo.

Esse processo de apresentar exemplos ao modelo e ir corrigindo pouco a pouco é o que chamamos de aprendizado estatístico, é a base da palavra learning nessa história de deep learning. A reta não é a única maneira de traçar um modelo, há várias, o deep learning fornece uma delas que é particularmente poderosa para alguns problemas específicos. Se ao invés de pontos simples nós tivéssemos que encontrar um modelo que leva um conjunto de pixels, uma imagem, a um valor, que representa o conteúdo da imagem, uma reta teria bastante dificuldade em fazê-lo. Nisso entra nosso convidado de hoje, a aprendizagem profunda.

Essa história de deep learning

Nosso problema agora é esse: tenho 15 pixels, organizados em uma rede 5 x 3. Eles apenas possuem valores 0 e 1, preto e branco. Com eles, posso desenhar formas bem primitivas. Estou bem interessado em números, como aqueles do seu relógio digital velho. Por exemplo:

 

Meu objetivo é: dados esses pixels, qual número parece estar escrito neles? Não parece uma tarefa difícil, até você pensar no que essas imagens significam para o computador. Cada uma delas é uma de 32768 configurações possíveis de tabelas com quinze coordenadas cada, sendo cada coordenada um zero ou um. Para o computador, essas imagens são:

Se eu não ligar para invariâncias espaciais ((Eu deveria ligar! É possível, e recomendado, usar técnicas de aprendizagem profunda que levam em conta invariâncias translacional e rotacional. Estou ignorando aqui para simplificar as coisas.)), essas imagens são vistas pelo computador como:

[1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 0.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0]
[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]
[0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0]
[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0]
[1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0]
[1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0]
[1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]
[1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0]
[1.0, 0.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0]
[1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]

Aqui fica claro que é bem complicado interpretar esses números como imagens, e é isso que queremos fazer nosso modelo aprender. Quero uma função que leve cada conjunto de quinze coordenadas binárias em um valor entre zero e nove de forma razoavelmente precisa. Não há reta que resolva. A reta fica perdida sem entender as complicadas correlações entre pontos distantes ou próximos. Esse é um ponto que pretendo desenvolver em outro post, mas menciono aqui: métodos clássicos estatísticos focam em descobrir correlações de caráter mais simples entre os dados. A grande vantagem do deep learning é a possibilidade de descobrir correlações e padrões bem mais complicados.

E o que, afinal, é isso? Deep learning envolve o uso de um modelo chamado rede neural. Para nosso modelo anterior, o dos pontos, chutamos uma relação linear com dois parâmetros $y = \alpha x + \beta$ e pareceu funcionar bem. Primeiro, vamos imaginar como seria um jeito de tentar resolver o problema dos dígitos usando uma reta. Temos quinze valores de entrada, então uma “reta” com quinze variáveis (ela na verdade vira um plano) seria:

\[ y = \alpha_1 x_1 +\alpha_2 x_2 +\ldots +\alpha_{15} x_{15} +\beta \]

Por mais que eu mexa nos $\alpha$’s e no $\beta$, não há jeito ou maneira de fazer $y$ acertar os valores, mesmo se eu arredondar seu valor para virar um número inteiro. Os padrões do meu problema não são lineares, não existe uma correspondência clara de “quando um pixel aumenta, o valor do dígito aumenta”. Se queremos capturar uma relação mais complicada entre entrada e saída, precisamos de mais poder de fogo. Uma rede neural é exatamente isso: uma função mais complicada que a reta e com mais parâmetros para acertar, ainda que a ideia geral seja a mesma.

A rede neural consiste em pegar os quinze elementos de entrada e aplicar uma sequência de operações lineares e não-lineares. Uma operação linear é uma que envolve só soma e multiplicação, como aquela que eu usei acima para definir a “reta”. A ideia é pegar os elementos de entrada, fazer aquela operação do $\alpha_1 x_1+\ldots +\alpha_{15}x_{15}+ \beta = z_1$ e depois fazer o resultado dessa operação, que eu chamei de $z_1$ passar por alguma função não-linear que dê uma torcida nos resultados. A função não-linear escolhida para compor o valor dos $z$’s varia. Vamos pegar uma escolha clássica, a função sigmoide, que tem essa cara:

Não vou fazer isso uma vez apenas, vou fazer isso dez vezes diferentes. Ou seja, vou criar uma coleção de dez $z$’s, cada um calculado a partir das mesmas entradas, mas com coeficientes $\alpha$ diferentes. Uma imagem vale mais que esse parágrafo, a ideia é fazer uma conta assim:

Onde cada linha representa um $\alpha_{i,j}$ que multiplica a entrada $x_i$ e leva para a composição do $z_j$. Depois eu vejo qual dos meus $z$’s tem o maior valor. Se é o $z_3$, por exemplo, então digo que esses pixels correspondem ao número 3. É como se essas operações tentassem, através de combinações complicadas, definir qual $z$ é o vencedor dados esses pixels. Escolhendo o vencedor, tenho a previsão do modelo.

Parece complicado, mas realmente não é. Estou apenas multiplicando as entradas por números (os $\alpha$’s), somando, passando por uma função um pouco mais torta (a sigmoide), e colecionando o valor que dá como resposta. Terei assim 150 valores diferentes de $\alpha$’s e 15 $\beta$’s para acertar, tunar, mexer como um ladrão experimenta com a maçaneta do cofre para encontrar a combinação certa. Não vou acertar esses coeficientes na mão, claro, não sou capaz disso. Uso o mesmo método de antes: pego um ponto, vejo se acertei, vejo em qual direção eu teria que mexer os coeficientes para minha previsão chegar mais perto da resposta certa, mexo, repito o processo.

Minha função final agora é pegar o maior valor de dez possibilidades, sendo cada uma delas uma combinação das entradas com 16 parâmetros diferentes (15 $\alpha$’s e 1 $\beta$). Ela é bem mais complicada, mas me permite capturar relações mais complicadas. Com o modelo linear, a “reta”, eu tinha apenas 16 parâmetros para acertar, agora tenho 165. Isso me dá bastante espaço para aprender as sutilezas dos pixels, mas ainda não é o suficiente. Preciso de mais poder de cálculo, mais parâmetros. Preciso ir mais fundo nessa rede neural para tentar aprender alguma coisa.

Essa transformação dos valores de entrada em operações lineares e não-lineares para formar os $z$’s é chamada de camada. Para criar um modelo de aprendizagem profunda, a ideia é usar os $z$’s como entradas de uma próxima camada. Essa concatenação de camadas é o que dá o nome de deep learning. A imagem talvez deixe as coisas mais claras:

E por fim, você vê qual dos $w$ é o maior e elege ele como a previsão do modelo. Se o dígito deveria representar um 4 e o maior valor é o $w_4$, você acertou. Se errou, calcula para onde os parâmetros, que agora são 275, devem ser mexidos para você obter um $w_4$ mais elevado.

Isso funciona?

Por incrível que pareça, sim, mas ninguém sabe direito porquê. Os elementos de resposta que temos são bem complicados e deixo para um post geek ou hardcore, o de hoje termina com você brincando com a rede neural que eu descrevi acima. Gerando um monte daqueles dígitos, treinamos os 275 parâmetros e temos uma coleção de $\alpha$’s e $\beta$’s que talvez sejam capazes de entender quando uma imagem é um dígito. Tente você mesmo, na planilha abaixo, produzida por meu grande amigo Gabriel Rovina:

REDE NEURAL TREINADA PARA VOCÊ SE DIVERTIR

Salve uma cópia local (Arquivo -> Salvar uma cópia) dessa planilha para poder editá-la. Em seguida, brinque com o número na entrada, acendendo e apagando os pixels para formar o dígito que deseja. Não é um sistema perfeito, você pode não concordar com alguns resultados dele, mas é bem certinho na sua capacidade de deduzir o que é cada dígito.

Isso é deep learning, nada mais, nada menos. No final, temos uma função complicada que é uma combinação de somas, produtos e passagem por sigmoides, com muitos parâmetros para acertar usando aquela estratégia de tentar, errar, corrigir e tentar de novo. É um sistema bem eficaz para análise de dados cujos padrões são complicados de extrair, especialmente imagens, sons e linguagem. Planejo um post futuro, mais geek ou hardcore, para aprofundar nos motivos de funcionamento de deep learning e em quais problemas ele não funciona de jeito nenhum. Por enquanto, divirta-se com essa rede que eu preparei na planilha, e não me xingue se você formar algum número que ela não reconhece. Com menos de 300 parâmetros e sem invariância espacial, foi difícil fazer coisa melhor.

3 respostas

A justiça do aleatório

Rookie

Estatística com poucos dados sempre dá calafrios. Uma das grandes ameaças a qualquer conclusão de um estudo é, tendo poucos dados, você pode confundir um efeito real com pura sorte. Não estou nem falando de fontes de viés mais graves, como uma pesquisa online que privilegia quem tem acesso a internet ou uma pesquisa boca de urna que privilegia pessoas dispostas a parar para conversar. Estou falando de pura sorte, ou, no caso do experimento estatístico, puro azar de ter estudado casos que justamente apresentam uma conclusão diferente daquela que o estudo deveria ter dado. Hoje vamos falar dessa sorte, e de um de meus métodos favoritos para tentar separar o que é efeito e o que é acaso fortuito.

Quando você tem muitos dados e seu método de escolha não tem nenhum viés, é mais difícil sofrer com os efeitos do azar. A exata quantidade de pessoas que você precisa para evitar isso tem a ver com o teorema do limite central, um conceito que vale um post próprio. A ideia é que se você seleciona elementos o suficiente da população, você claro tem chance de pegar anomalias que poderiam mexer em seus resultados, mas se seu método de seleção é bom você deve pegar anomalias que puxam o resultado para o outro lado também. As bizarrices de uns compensa as bizarrices de outros e você termina com um resultado médio confiável. Mais ou menos como quando uma multidão sai de um estádio. Você nunca sabe para onde uma pessoa vai, mas a massa humana se move de maneira previsível e você pode criar mecanismos de escoamento adaptados a essa situação confiando nesse princípio fundamental da estatística. Mas muitos dados não é nosso caso hoje, vamos ver o que dá para fazer tendo apenas catorze.

Tenho catorze plantas de tomate e dois fertilizantes: marca A e marca B. Quero saber qual dos fertilizantes é melhor. Divido minha horta em catorze pedaços. Vou fertilizar a terra, plantar e regar, tendo plantado a mesma quantidade de pés de tomate em cada pedaço de terra. Porque não sou besta e sei que plantar com fertilizante A de um lado e B de outro pode criar uma tendência, afinal, a fertilidade inerente da terra pode estar associada com a região da horta (por receber mais sol, por exemplo), eu tiro na sorte qual fertilizante vai em cada pedaço. Tirar na sorte é fácil, basta pegar catorze cartas de baralho, sete vermelhas e sete pretas, embaralhar bem e tirar uma para cada pedaço de terra.

Com minha horta plantada, colho os tomates, peso e comparo o quanto obtive em cada pedaço de terra.

Não parece haver uma tendência de região. Digo, é possível, nunca se sabe se a tendência de região compensou a tendência do fertilizante, mas isso é um pouco especulativo. Temos nossos 14 resultados e queremos saber quem é melhor: A ou B. Fazemos a média do peso de tomates de cada um deles e o resultado é:

Fertilizante Média
A 24.9Kg
B 26.1Kg

O B parece ser o vencedor, e um estudo qualquer talvez até pudesse parar aí: B é melhor. Mas prestando atenção com calma, ele não é tão maior assim, apenas 1.2Kg de diferença na média, sendo que os valores médios são vinte vezes maiores que essa diferença! É possível que a vantagem de B seja apenas sorte, um acaso surgido de uma experiência com poucos dados? Quão provável seria sair esse resultado se A e B fossem perfeitamente equivalentes?

Essa última pergunta é bem difícil de responder, porque não conhecemos a distribuição de probabilidade de A e B, ainda que fosse a mesma. Com bastantes dados, poderíamos estimar a distribuição, calcular desvio padrão, ter toda uma pletora de ferramentas e instrumentos estatísticos para nos ajudar, temos apenas catorze pontos e vamos nos virar com isso. Minhas estratégia será usar a aleatoriedade da nossa escolha de lugares para plantar para gerar “novos dados”, apostando na justiça do aleatório para decidir se essa diferença é significativa ou não.

Qual a ideia? Nossa escolha de lugares para plantar foi A, B, A, A, B, A, B, B, B, A, B, B, A, A; confiando no coração das cartas. A diferença entre as médias de A e B foi de 1.2Kg, então eu pergunto: se a ordem dos fertilizantes fosse trocada, com os resultados ficando onde estão, qual seria essa diferença. Por exemplo, se os sete piores resultados fossem do A e os sete melhores fossem do B, a diferença seria de 2Kg. Existem outras permutações da ordem dos fertilizantes que dariam diferenças menores, variando entre 0Kg e 2Kg. Estudando todas as configurações possíveis de fertilizante, guardando os resultados onde estão, ganhamos uma boa noção do quanto é sorte ou do quanto é efeito de verdade.

Temos 3432 permutações não-repetidas possíveis desse conjunto. Uma delas é A, B, A, A, B, A, B, B, B, A, B, B, A, A, cuja diferença entre as médias é de 1.2Kg. Como são as outras? O histograma abaixo dá uma boa ideia, onde os resultados são da diferença entre as médias de B e A (por isso pode ser negativo).

Com apenas um resultado, quase invisível, no -2 e no 2, o resto todo distribuído simetricamente em torno de zero. A simetria é esperada, já que toda vez que existe uma permutação em que B ganha de A existe o oposto espelhado dessa combinação em que A ganha de B. E onde entra nosso caso, o caso real, nesse histograma?

Temos nosso resultado visualizado e com ele conseguimos ganhar alguma perspectiva. Basta contar quantas permutações de nosso conjunto produzem resultados maiores que a que obtivemos para estimarmos a probabilidade de termos dado sorte! Se nosso resultado estivesse muito perto do centro, muitas outras seriam mais discrepantes e a chance da diferença ter vindo do acaso fortuito passa a ser alta. Se nossa permutação fosse a que causa a maior diferença possível, teríamos quase certeza de que o tipo de fertilizante impacta profundamente a quantidade de tomates produzida por cada pé.

Em nosso caso, 133 das 3432 combinações possíveis são maiores que 1.2Kg, o que representa apenas 3.9% dos casos totais. Uma regra bem comum na estatística é estimar que se menos de 5% das permutações seriam melhores do que a realidade, então seu efeito provavelmente é real e não pode ser descartado facilmente. Não é uma regra fixa e perfeita, afinal, se o número de permutações fosse 6%, ou 7%, eu ainda poderia ficar desconfiado. Mas é uma maneira bonita, eu acho, de tirar leite de pedra, de fazer estatística com poucos dados sem perder o rigor da análise.

É um truque interessante que aprendi nas ruas, nem sempre temos todos os dados que queremos. É também útil para a vida, quando encontramos uma experiência na vida real e queremos estimar se um efeito é verdadeiro ou fruto do acaso. Se comparamos o horário de dois trens seis vezes e um deles está sempre mais atrasado que o outro, em todas as vezes, assumimos que o trem é atrasado porque a chance desse resultado acontecer com dois trens equivalentes é de $1/2^{6} \approx 1.6\%$. Usamos a medida do aleatório constantemente para dar chances a modelos que às vezes não merecem. É uma  maneira fundamental de medir dois efeitos, usando o acaso como justiça, como o grande mediador do nosso experimento.

Deixe um comentário

A população brasileira

Rookie

A reforma da previdência é um assunto quente no momento. Um governo desestabilizado deve atacar uma importante reforma que leva em conta a situação política, econômica e demográfica brasileira. Não tenho competência para atacar a parte da economia, não acho que alguém tenha competência para entender qualquer coisa de política atualmente, então dedico um post às mudanças demográficas brasileiras dos últimos 17 anos, e futuros dois.

A evolução da população brasileira é fácil de achar no site do IBGE, mas não é fácil visualizar. Para isso, decidi afinar minhas habilidades em JavaScript e construir um gráfico interativo para facilitar a compreensão. Esse é o resultado:

View in percentage


Os dados usados são os reais até 2013 e projetados até 2020. Basta clicar em alguma barra, ou em alguma legenda, para visualizar uma faixa de idade com mais detalhe. Coloco aqui uma versão maior desse gráfico. Nessa página também disponibilizo o código e os dados; você pode fazer seu próprio gráfico interativo em casa, basta trocar os dados de entrada e ele deve, sem reclamar muito, montar-se sozinho.

O post de hoje é sem análise, o gráfico deve falar por si.

Deixe um comentário

Os ônibus de Cuernavaca

Geek

Para o post de hoje, vamos ao México. Ele será um pouco mais sofisticado que meus posts habituais, mas acho que esse blog sentia falta de uma matemática um pouquinho mais pesada. Vou tentar manter Geek, sem passar ao Hardcore, prometo que, lendo com paciência, é um assunto fascinante.

A cidade de Cuernava, um pouco ao sul da Cidade do México, é um lugar muito especial para a física estatística e para quem gosta de matrizes aleatórias. Com um pouco mais que 300.000 habitantes, essa cidade apresenta um urbanismo estranho: ela é construída entre duas grandes rodovias que levam à capital do país e, entre elas, possui uma grande avenida central. Suas demais ruas, como os ramos de uma folha, se espalham entre as rodovias ao redor da avenida. Nessa avenida principal passa a linha 4 de ônibus de Cuernavaca, foco de nosso maior interesse, que possui propriedades fascinantes.

A linha 4 não é regulada por um sistema unificado de transportes, cada condutor de ônibus em Cuernavaca é dono de seu ônibus, como se fosse apenas um táxi grande, e quer, certamente maximizar seus lucros. Se, no entanto, dois ônibus estiverem muito próximos, o que está logo atrás sofrerá prejuízo financeiro; para evitar essa situação, os motoristas de Cuernavaca chegam a pagar “olheiros” posicionados estrategicamente na avenida para contar ao motoristas há quanto tempo o outro ônibus passou para que, assim, eles possam acelerar ou diminuir o passo, evitando encontrar o ônibus seguinte e o anterior. Diminuir a velocidade demais também não é bom pois, não apenas isso seria um serviço profundamente mal-prestado, mas ele correria o risco de ser ultrapassado pelo ônibus que o precede.

Dois físicos visitaram Cuernavaca em 2000 e ficaram fascinados com as características desse sistema de transporte. Durante um mês, eles coletaram dados de chegada e saída dos ônibus da estação central da linha 4 de Cuernavaca. Seus resultados foram relatados em um intrigante artigo, reproduzo o gráfico:

cuernavaca

O valor que interessou os físicos foi: dada a chegada de um ônibus, quanto tempo o próximo demorava? Eles armazenaram esses dados em um belo histograma que, propriamente normalizado, resultou nos dados marcados com uma cruz no gráfico acima. As barras e a linha, que coincidem quase perfeitamente com os dados, são resultados teóricos de um modelo que os físicos suspeitaram ter a ver com o problema.

Se você tomar uma matriz hermitiana ($A=A^\dagger$) e colocar como entradas nela valores aleatórios tirados de uma distribuição gaussiana complexa, terá o que chamados de uma matriz do GUE, Gaussian Unitary Ensemble. Falei um pouco sobre matrizes gaussianas em um post anterior. Se as entradas da matriz são gaussianas, seus autovalores, como vocês devem suspeitar, possuem uma densidade de probabilidade bem diferente e, em particular, apresentam um fenômeno de repulsão logarítmica, ou seja, se os autovalores fossem partículas, elas se repeliriam com uma força que poderia ser interpretada como um potencial logarítmico na distância entre as partículas: $V(x) \propto \log|x_i-x_j|$. Em português, se você encontra um autovalor de uma matriz gaussiana em um ponto, é extremamente improvável encontrar outro muito perto dele. Se você estudar a estatística da distância entre os autovalores: tirar várias matrizes gaussianas aleatoriamente, diagonalizar, extrair autovalores, estudar a distância entre um autovalor e seu vizinho, fazer um histograma, normalizar corretamente e plotar em um gráfico, a teoria de matrizes aleatórias diz que você terá, quanto maior for a matriz, uma função cada vez mais próxima de $\frac{32}{\pi} s^2 e^{-4s^2/\pi}$.

Surpreendentemente, essa função é a linha plotada no gráfico acima, encaixando-se com perfeição nos dados. As barras são resultados de simulações feitas com matrizes gaussianas, colando mais uma vez com o resultado dos ônibus. O fato de os motoristas tomarem cuidado para não se aproximarem demais de seus vizinhos fazia o papel da repulsão logarítmica dos autovalores, e fazia com que os ônibus de Cuernavaca se comportassem como os autovalores de uma matriz gaussiana complexa.

O artigo segue com mais detalhes para comprovar seu argumento, mas aquilo não era o suficiente. Faltava criar um modelo para os ônibus que permitisse deduzir esse fato, que não é nada óbvio. Isso foi feito em um artigo seguinte, modelizando com carinho essa rede de transportes. Como queremos simplificar para compreender, o modelo pode não parecer muito realista; mas é isso que físico fazem: simplificam e tentam, na simplicidade, perceber a emergência de um fenômeno complexo e suas causas. Vamos aos ônibus.

Como o acelerar, desacelerar, parar, desabastecer-se e abastecer-se de passageiros é um processo complicado e imprevisível, precisamos simplificar drasticamente para que a matemática do modelo seja tratável. Ao invés de andar o caminho entre um ponto e outro, tomemos um modelo com duas hipóteses:

  • Os ônibus ficam parados um tempo aleatório em cada ponto. Passado esse tempo, são “teleportados” ao próximo ponto.
  • Dois ônibus jamais se encontram. Enquanto um está em um ponto, o próximo não pode teleportar a ele.

Com essas duas regras, podemos simular o comportamento desses ônibus em uma linha. Reproduzo o gráfico do artigo novamente:

buses_cuernavacaEsse modelo, depois de algumas contas complicadas, nos conduz ao que queríamos provar: a distância entre os ônibus será dada pela mesma fórmula da distância entre valores próprios de uma matriz gaussiana. Claro, fizemos o modelo para que isso desse certo, e ficamos felizes que, apesar de simples, ele reproduz elementos importantes da realidade.

Não é um caso isolado. Os ônibus de Cuernavaca são um exemplo curioso e interessante do fenômeno de universalidade em matrizes aleatórias. Em uma analogia, é como se em sistemas complexos houvesse uma versão do teoria central do limite para processos altamente correlacionados. Não foi por acaso que Wigner, Dyson e Mehta escolheram matrizes aleatórias como tentativa de modelizar a interação forte no núcleo atômico, eles desconfiavam, com razão, que um processo estatístico acontecia em sistemas com um número suficientemente elevado de elementos. Tal processo, como toda boa estatística, mata as flutuações aberrantes e preserva as características extensivas do modelo.

Ainda não solucionamos o mistério da universalidade. A teoria de matrizes aleatórias aparece em contextos demais, não conseguimos ainda desvendar a razão disso. Em caos quântico há conjecturas fundamentais a respeito, em teoria dos números também. Essa emergência pode ser coincidência, ou pode ser manifestações de um teorema central do limite para variáveis fortemente acopladas. Não sabemos ainda, mas buscamos. Meu trabalho atual é um pouco sobre isso, estudar como é a transição de um sistema fortemente correlacionado, como os ônibus de Cuernavaca, a um sistema de variáveis independentes, como os ônibus de São Paulo. Essa mudança de comportamento é profundamente interessante, ocorre em diversos fenômenos físicos e é mediada pelas mais variadas formas de interação. Mas um novo post sobre meu trabalho fica para outro dia.

No grande tomo The Oxford Handbook of Random Matrix Theory, Freeman Dyson escreve no prefácio, após comentar sobre os ônibus de Cuernavaca:

“O benefício do sistema autorregulatório dos ônibus à população é medido pela variável $R$, a razão entre o tempo de espera médio de um passageiro e o tempo médio entre os ônibus. O melhor valor possível de $R$ é 0,5, quando a distância entre os ônibus é exatamente igual. Se os ônibus não são correlacionados, teremos $R=1$. Em Cuernavaca, como eles se comportam como autovalores de uma matriz gaussiana, temos $R=3\pi / 16=0.589$, muito mais perto da situação ideal que da situação independente. Não sou capaz de determinar se as aplicações de matrizes aleatórias no mercado financeiro, como as descritas no capítulo 40 deste livro por Bouchaud e Potters, geram algum benefício comparável. Quando um especialista em finanças me diz que algum pedaço de feitiçaria financeira certamente irá beneficiar a humanidade, sou levado a acreditar que um motorista de ônibus de Cuernavaca faria um trabalho melhor.”

 

5 respostas

Top na balada

Geek Rookie

No post de hoje, vamos resolver um problema grave, clássico e profundo: como escolher o melhor namorado ou namorada para casar, ou como escolher o melhor garoto ou garota na balada para levar para casa aquela noite. Não são problemas simples, mas, como a maior parte dos dilemas pessoais, usando frieza, crueldade e fechando os olhos para os reais problemas sociais envolvidos, podemos tirar conclusões bem interessantes. No post de hoje, vamos deduzir a estratégia para maximizar suas chances de, em uma noite, levar o melhor parceiro possível para seu quarto mostrar sua coleção de discos do Elvis.

Deixo apenas registrado que se você está buscando referências sérias nesse blog sobre como se dar bem em uma balada, deve estar realmente desesperado. Continuemos.

O problema se apresenta da seguinte forma: você pegará na noite de hoje um número $N$ de pessoas. Dentre essas pessoas, você estabelece um ranking de qualidade, seu objetivo é levar a melhor delas para casa porque, convenhamos, você já passou da idade de ficar só dando beijinho em balada. Você encontra uma pessoa, corteja, afeiçoa-se e tem duas opções: ou escolhe essa para levar para casa, ou rejeita. O problema é claro: você corre o risco de estar rejeitando a melhor dentre as $N$. Supondo que você e a pessoa têm um pingo de dignidade, não poderá voltar atrás nessa decisão! Nessa lógica, qual a melhor estratégia para maximizar suas chances de escolher de fato a melhor dentre as $N$ possíveis?

Se achou as contas a seguir chatas e complicadas, tudo bem, eu entendo; você pode pular para o final do post para descobrir a melhor estratégia.

A natureza do seu dilema é a informação incompleta. Cortejando a pessoa número $n$, você tem apenas o ranking dela em relação às que já viu, não tem a menor ideia de como ela se compara às que virão. A primeira pessoa sempre será a melhor até então (e a pior), não parece uma boa estratégia aceitar a primeira que aparece, porque a noite é longa e promete. Por outro lado, se você encontrar a melhor até então na penúltima pessoa, as chances são baixas de encontrar a melhor de todas na última, desprezar a melhor na penúltima parece também uma estratégia ruim. Entre uma recusa quase certeira da primeira e uma aceitação quase certa da penúltima, deve haver algum ponto intermediário em que a estratégia fica a melhor possível.

Vamos calcular esse ponto e determinar qual a melhor estratégia para o problema. Para isso, vamos primeiro modelizar o problema de forma precisa:

  • Você estima que cortejará $N$ pessoas até o final da noite.
  • Uma vez rejeitando a pessoa, não pode voltar atrás.
  • Seu ganho é 1 se você escolher a melhor dentre as $N$ pessoas e 0 se escolher qualquer outra.
  • Se chegar à última, leva a última. Em outras palavras, se a balada começou a miar e são seis da manhã, você leva para casa a pessoa que sobrou, sinto muito. Nisso, convenhamos que o modelo é bem preciso.

Confesso que o modelo tem um problema, a noção de tudo ou nada, de que seu ganho é zero ainda que você leve a segunda melhor, enquanto, convenhamos, não é algo tão ruim. Vamos imaginar que você é extremamente exigente e sentirá que a noite não valeu a pena porque, levando a segunda melhor, pensará apenas na primeira durante a noite toda.

Para resolver o problema, vamos definir duas variáveis. $X_n(1)$ é o seu ganho esperado se na $n$-ésima pessoa entrevistada você encontrar a melhor até então; $X_n(0)$ é seu ganho esperado caso a $n$-ésima entrevistada não seja a melhor vista até então. Em nosso modelo, claro, $X_n(0)=0$, você não espera ganhar nada levando alguém para casa que nem é o melhor dos primeiros $n$ que você já viu, vale mais tentar outras pessoas e correr o risco de encontrar o melhor nos seguintes. Se você encontrar na $n$-ésima a melhor até então, o seu ganho é a chance de a melhor pessoa estar entre as $n$ primeiras. Como a ordem em que você pega as pessoas é aleatória, essa chance é de $n/N$. Assim, $X_n(0) = 0$ e $X_n(1)=n/N$.

Em seguida, definimos o ganho esperado se descartamos a pessoa $n-1$ e passamos para a $n$, chamamos essa variável de $Y_n$. O seu ganho esperado descartando a pessoa $n-1$ depende do que você vai fazer encontrando a pessoa $n$. Se você decidir ficar com a pessoa $n$, seu ganho esperado saltando $n-1$ é o ganho esperado de $n$, ou seja, $X_{n}$. Se você decide saltar também a $n$, então seu ganho esperado será $Y_{n+1}$. Você vai tomar essa decisão baseando-se nesses valores, você deve se perguntar “Quem é maior: $X_{n}$ ou o valor médio de $Y_{n+1}$?”. Comparando esses dois valores, você sabe qual será seu comportamento no próxima pessoa. A fórmula para $Y_n$ será, portanto, definida de forma recursiva:

\[ Y_n = \max \{X_{n},\langle Y_{n+1} \rangle \} \]

Onde $\langle x \rangle$ é a média de $x$, escrita desse jeito com o único objetivo de fazer os estatísticos lendo esse texto terem um pequeno derrame de nervoso.

Esse cálculo recursivo encorpora bem o dilema descrito acima. Perto das últimas escolhas, $X_n$ fica grande se você encontra a melhor pessoa até então e $Y_n$ fica pequeno. No início, contudo, $X_n$ é pequeno e vale mais apostar no futuro do que estacionar no começo. Para que a fórmula recursiva faça sentido, ela precisa ter um ponto de partida. Nisso usamos a última hipótese, o ganho esperado pulando a última casa é o mesmo que o da última casa, ou seja, pular a última não adianta, você leva a última opção se chegar nela: $X_N=Y_N$. Usando a fórmula acima, e com algum malabarismo que não cabe aqui, você consegue deduzir a expressão de $Y_n$:

\[ Y_n = \frac{n}{N}\sum_{k=n}^{N-1} \frac{1}{k} \]

Assim, começa a valer a pena escolher uma pessoa a partir do momento em que $X_n > Y_n$, ou seja, quando estamos na $k$-ésima pessoa e $1>\sum_{k=n}^{N-1} \frac{1}{k}$. A partir desse valor, seu ganho esperado ficando com a melhor pessoa encontrada até agora é maior que o ganho esperado no futuro pulando essa pessoa; logo, é estatisticamente mais interessante levar essa para casa.

Claro que encontrar esse valor de $k$ não é simples, tem que somar fração e isso é chato, tem umas partes que envolvem MMC e isso me dá fadiga. Melhor que somar essas frações seria usar uma boa aproximação para essa soma, que eu conheço bem, é a série harmônica $\sum_k \frac{1}{k}$. Como você deve se lembrar de sua infância, essa soma de 0 a $n$ pode ser aproximada, para grandes valores de $n$, por $\ln n $. Assim, a soma de $n$ até $N-1$ deve ser $\ln (N-1)-\ln(n) = \ln\left(\frac{N-1}{n}\right)$. Como usamos a hipótese de valores grandes de $N$, podemos escrever isso como $\ln\left(\frac{N}{n}\right)$. Assim, devemos parar de pular candidatos quando encontramos o melhor a partir do $n$-ésimo, sendo $n$ o número tal que $\ln\left(\frac{N}{n}\right)<1$, ou seja, $n = \frac{N}{e}$, onde $e$ é o número de Euler $e=2,71828\ldots $.

Percebemos que essa conta nos diz para pularmos os primeiros $\frac{N}{e}$ pretendentes e, após esses, ficar com o primeiro que for melhor que todos os anteriores. Note que $\frac{1}{e}\approx 0.37$. Em outras palavras, a estratégia optimal para encontrar o melhor pretendente da balada para levar para casa é a seguinte: estabeleça um número de pessoas para pegar na balada. Rejeite necessariamente os primeiros 37% delas. Cole na primeira pessoa que aparecer que for melhor que todas as anteriores e leve esta para casa.

O mesmo vale para namorados ou namoradas durante sua juventude. Se quer maximizar suas chances de casar com a melhor opção, estabeleça uma estimativa do número de pessoas com que vai namorar durante sua vida, termine com os primeiros 37% e case com a primeira que aparecer que for melhor que todas as anteriores.

Vamos ver quão bem isso funciona. Para isso, vamos contar a história de Pedro.

Pedro é um garoto que costuma ir a três baladas diferentes. Ele está atrás de garotas, e quer levar a melhor delas para casa. As baladas são diferentes, e a qualidade dos frequentadores tem uma distribuição variada para cada balada. Vejamos quais são elas, usando descrições do site cidadedesaopaulo.com:

  1.  A The History, localizada na Vila Olímpia, tem piso que muda de cor e agrada tanto àqueles que já curtiram os hits dos tempos da brilhantina quanto às novas gerações. Possui um público pouco variado e previsível, a qualidade dos frequentadores será dada por uma distribuição gaussiana.
  2. Localizado no Baixo Augusta, o Beco 203 é reduto dos moderninhos e alternativos que curtem um rock mais soft e festas em que o som é tocado através de fones de ouvido. Atraindo um público mais variado, a distribuição da qualidade de seus frequentadores será dada pela distribuição uniforme.
  3. A Lab, localizada na Rua Augusta, possui em sua programação dias dedicados à música eletrônica. Com um público ligeiramente variado, mas não muito, a qualidade de seus frequentadores está mais concentrada nas piores notas que nas melhores e será modelada pela distribuição exponencial.

Pedro é uma máquina e se dispõe inicialmente a pegar 100 garotas. Ele vai vezes o suficiente às baladas para poder testar diferentes estratégias, e está disposto a tentar todas as possibilidades. A experiência é a seguinte: um dia ele leva a primeira que encontrar para casa. No dia seguinte, ele rejeita a primeira e leva a primeira melhor que as anteriores para casa. Em seguida, rejeita as duas primeiras e leva a primeira melhor que as anteriores que encontrar para casa. Fazendo isso até a centésima vezes o suficiente, ele consegue estimar a taxa de sucesso de cada estratégia. Uma noite é bem sucedida se a que ele levou para casa era a melhor dentre as 100 possíveis. São bastantes opções, vejamos qual a taxa de sucesso de cada uma das estratégias.

top_na_baladaÉ facil acreditar que o valor ideal para a estratégia é 37, ou seja, rejeitar os primeiros 37% e aceitar a primeira opção melhor que todas as anteriores. Note como esse valor independe de como a qualidade das pretendentes está distribuída, seja uniforme ou extremamente concentrada em torno da média, a eficácia de cada estratégia é a mesma.

Falando um pouco mais sério, esse pequeno problema estatístico revela uma matemática internalizada em diversas decisões em nosso cotidiano, a ideia de “assentar”, de escolher uma opção para ser a definitiva. Quando você é jovem, seus namoros são em média curtos, explosivos, cheios de emoções e problemas, a idade vai trazendo mais estabilidade e em um ponto da vida você encontra aquela que acha ser a pessoa certa. Você experimentou o suficiente para identificar uma pessoa melhor que as anteriores e entender que a melhor estratégia é juntar os chinelos com esta; porque, conhecendo as alternativas, você prefere não arriscar e entende que é pouco provável encontrar algo tão melhor nas futuras opções. Casamento é sobre amor, sobre almas gêmeas, some encontrar a pessoa prometida e amada; mas quando você começa a beirar os trinta anos a realidade bate na porta e a estatística, aliada a sua experiência, fala mais alto.

E se você me perguntar se sigo essa estratégia, não vou poder responder. O modelo tem várias hipóteses, várias delas são boas, a maior parte se aplica a minha situação, mas um grande valor de $N$, certamente, não é o caso.

Deixe um comentário