Mathspp: mathematics and programming

New blog!!!

2020-02-02T21:52:00.001+00:00

< change language

My blog is being migrated to mathspp.com!!

O meu blogue está a ser migrado para o meu novo site: mathspp.com!!

- RGS

Generating natural-looking digits with neural networks

2019-03-16T22:28:00.001+00:00

< change language

In this post I will show you how I got a neural network to write digits that look like they've been handwritten. In fact, the digits you can see in the first image of this post where generated by said neural network. The code that did all this is here.

It all started when I read, some time ago, about this funny way in which you could use neural networks: you are going to train a neural network to take a vector of size $N$ as input, and you are going to teach your network to do nothing. That is, you are going to teach your neural network to behave as the identity function... but with a twist! If your input size is $N$, somewhere in the middle of the network you want to have a layer with less than $N$ neurons! If this happens, you can think that your vector $x$ that is going in, first has to be squeezed through that tight layer, and then it expands again to be the output of the network.

If now you slice your network in half, the part of the network from the input up until the "squeeze it tight" part, compresses your inputs. The second half, from the "squeeze it tight" part until the output, decompresses your data (for those of you interested in looking this up, I think the correct name for this network is "encoder", but I am not sure).

Let that sink in for a second.
Now that I "know" how to compress things, imagine this scenario: I teach a neural network to compress digit images into a vector of size $10$ (one component per existing digit), and let us call encoder to this network. To train the encoder, all I have to do is effectively teach the network to classify the images of the digits. After training the encoder, I will create a new network (let's call it decoder) that takes $10$ values as input, and returns an image as output. Now I will teach the decoder to undo whatever the encoder does.

After doing that for a bit, say I take this image of a $2$:

If I feed that image into my encoder, this is what comes out:

tensor([[-3.2723,  3.7296,  9.6557,  4.9145, -8.6327, -3.1320,
                    -3.5934,  6.0783, -0.8307, -5.3434]])

If now I take that vector and feed it into the decoder, this is the image that comes out:

Looks good, right? Of course it is not exactly the same, but take a second to appreciate that the original image was $28 \times 28$, hence had $784$ values; those $784$ values were compressed into the $10$ numbers you saw above and then those $10$ numbers were used to reconstruct this beautiful $2$.

Of course that to build this $2$ we had to first have a $2$ go through the encoder, but I don't really like that step. What I had envisioned was a system that only made use of a single network.

One possible first idea would be to feed the decoder a vector of zeroes with a single $1$ in the right place. The only reason that does not work so well is because the encoder doesn't really compress the images to such nice-looking vectors, so the decoder doesn't really know how to handle that. Instead, I have a little helper function that creates a random vector of size $10$, where each entry is randomly chosen in $[-2, 1]$, except for the coordinate that corresponds to the digit I want to create: that one is a random number in $[13, 14]$.

Using that $5$ times for each digit, I was able to create these "handwritten" digits:

It is true that they look practically the same, but they are not!

Then I looked at those pictures, chose one digit out of each row, and used some basic thresholding to try and set the background to black and the number to white, to see if I could make the digits more easily read. This is what I ended up with:

which is not too shabby, in my opinion.

As future work, there is still everything to be done! Trying different neural network architectures, studying if the accuracy of the encoder is very important or not, finding more clever ways of giving the input to the decoder, finding more clever ways of enhancing the image produced by the decoder, trying to understand if it is possible for the network to generate more distinct digits, etc.

All this was written in a Jupyter notebook that you can find here. I used pytorch for this, so if you want to run it you'll need to have that. Otherwise, you can still look at the pictures and check the specifications of what I did, and try to reproduce this with your own packages and whatnot. TL;DR the images throughout this post are of digits that were generated by a neural network.

Neste post vou mostrar como é que treinei uma rede neuronal para desenhar dígitos que parecem manuscritos. Na verdade, os dígitos que vêem no início do post foram desenhados pela tal rede neuronal. Todo o código que diz respeito a esta experiência está aqui.

Tudo começou quando eu li, há algum tempo atrás, sobre uma utilização engraçada que se podia dar às redes neuronais: treinamos uma rede neuronal (com $N$ inputs) para ser a função identidade, uma rede que devolve exatamente aquilo que recebeu. No entanto, no meio da rede neuronal pômos uma camada com tamanho menor que $N$. Se fizermos isto, então o que a rede neuronal está a fazer é a espremer o input pela camada que é mais apertada, e depois a expandi-lo de novo.

Se separarmos agora a nossa rede neuronal, a metade que está à esquerda da camada mais apertada serve para comprimir os nossos inputs. A segunda metade, à direita da camada mais apertada, é a metade da rede que expande os inputs depois de eles terem sido espremidos, i.e. é uma rede que descomprime (para os mais curiosos, acho que isto são "encoders" no mundo das redes neuronais, mas não tenho a certeza).

Vamos deixar a ideia repousar por um segundo.
Agora que "sabemos" comprimir coisas, imaginemos o seguinte: vou ensinar uma rede neuronal a comprimir imagens de dígitos em vetores de tamanho $10$ (uma coordenada no vetor por cada dígito que existe), e vamos dizer que essa rede se vai chamar encoder. Para treinar a minha rede encoder posso ensiná-la a classificar imagens dos $10$ dígitos. Depois de treinar o encoder, treino outra rede neuronal (a que vou chamar decoder) cujo objetivo vai ser desfazer tudo o que o encoder fizer.

Depois de treinar as duas redes neuronais um bocado, imaginemos que pego nesta imagem de um $2$:

Se eu passar esta imagem pelo meu encoder, o resultado que obtenho é este:

tensor([[-3.2723,  3.7296,  9.6557,  4.9145, -8.6327, -3.1320,
                    -3.5934,  6.0783, -0.8307, -5.3434]])

Se agora eu pegar nesse vetor e o puser dentro do decoder, obtenho esta imagem:

Até tem bom aspeto, não? Claro que não são exatamente a mesma coisa, mas reparem que a imagem original tem $28 \times 28$ valores, $784$ pedaços de informação; esses $784$ valores foram espremidos para apenas $10$ valores, e desses $10$ valores o decoder conseguiu retirar esta representação do $2$.

Claro que para construir este $2$ eu tive de fazer uso do encoder primeiro, mas não é assim que eu quero que isto funcione. Depois de usar o encoder para treinar o decoder, quero poder deitá-lo fora!

Uma possível ideia seria alimentar o decoder com um vetor de zeros, a menos de uma única coordenada onde estaria um $1$. O único motivo pelo qual isso não funciona tão bem é porque o encoder nunca comprimiu nenhuma imagem para um vetor tão lindinho, e portanto o decoder provavelmente não há de saber como descomprimir esse vetor. Para contornar este problema, arranjei uma função auxiliar que devolve um vetor de tamanho $10$, onde $9$ das coordenadas são escolhidas aleatoriamente em $[-2, 1]$ e a coordenada que diz respeito ao dígito que quero criar é um número aleatório em $[13, 14]$.

Usando essa função $5$ vezes para cada dígito, criei estas imagens:

As imagens são bastante semelhantes, e isso é um problema que vou tentar apresentar como resolvido num post futuro, mas não são exatamente iguais!

Depois de olhar para as figuras, para cada conjunto de $5$ imagens do mesmo dígito, escolhi uma com bom aspeto e tentei usar umas regras básicas para eliminar o ruído a cinzento claro no fundo de cada imagem. Depois desse passo intermédio, acabei com isto:

O que, na minha opinião, não é terrível.

No futuro, há muito que pode ser feito ainda: tentar arquiteturas de redes neuronais diferentes, estudar se a precisão do encoder a classificar é importante ou não, encontrar maneiras mais inteligentes de dar input ao decoder, encontrar maneiras mais inteligentes de melhorar a imagem devolvida pelo decoder, tentar entender se é possível que a rede neuronal gere dígitos mais distintos, etc.

Este código foi todo escrito num notebook Jupyter que podem encontrar aqui. Usei o pytorch para estas experiências, portanto hão de precisar dele para correr o meu código. Caso contrário, podem ver os bonecos que fiz e tentar reproduzir (e melhorar!) os meus resultados com outra livraria. TL;DR as imagens espalhadas pelo post são de dígitos desenhados por uma rede neuronal.

- RGS

Generating (better) random mazes

2019-03-09T21:58:00.002+00:00

< change language

In this previous post I shared some code and animations of an algorithm that created random mazes. I shared it with you and I got some feedback on Facebook, saying that even the stupidly large mazes I gave you were really easy to solve (I think this link can show you what I am talking about). So it was about time I got you some new mazes! And this time, I don't think they are as easy to solve as the old ones.

The mazes I am sharing today were created by code found in this GitHub repo. The README will tell you to run the wilson_generator.py file. You can also download the (windows) executable that is zipped inside the wilsonExe rar. (please notice that in both cases, you can use the wilsonconfig.ini file to change the size of the maze)

The way our algorithm works is really simple. It will start a random walk on the top left corner of the window. Whenever the random walk intersects itself (creating a loop), it removes the loop from the walk, and then continues. Whenever the random walk connects back to whatever part of the maze was already built, the random walk becomes a part of the maze itself and a new random walk is started somewhere else. This is a loop-erased random walk, the stepping stone of Wilson's algorithm to generate a random spanning tree of a graph, with a very nice property: it will generate any of the possible spanning trees with equal probability.

Generating any of the spanning trees uniformly means that our maze won't be biased and have only a couple of really long paths, or a bunch of very short paths. And the reason why this algorithm actually has that property is fairly intuitive: just suppose that before running the algorithm, you visit each vertex, and create an infinite random stack of directions; that is, for each vertex $v$ in the graph, you create a random sequence $\{v_i\}_i$, where each $v_i$ was selected randomly and uniformly from the direct neighbours of $v$. After you have done this for every vertex, there is an obvious way to start tracing paths in your graph: just pick a vertex and start following the directions you are given! But the thing is, following those directions might actually make you follow some loops. So before tracing the paths you are presented with, you remove all the loops that you can find on top of all the stacks you created... when that has been done, following the directions that are on top of the stacks will give you a uniformly generated random tree. Of course that to run our algorithm, we don't generate the infinite stacks in advance, we just generate the elements that are needed on-the-fly.

This algorithm creates really balanced mazes... As an example, take this maze:

Now imagine that on the top left corner I will pour a bucket of a special paint: one that gradually changes colour as it travels. The resulting (coloured) maze looks like this:

(please bear in mind that the colours used cycle back to the beginning, so it creates a continuous and infinite degradee)
Also notice that this algorithm can be painfully slow to watch, specially when it has just started. I would strongly recommend against changing the configuration save_frames = False to True, as that will slow down the algorithm for a bit... but if you must do that, point the screenshot_bin to some existing folder, so that the thousands of frames get dumped there.

That is it! You have a small animation of the algorithm on the beginning of the post and a massive maze down there! Let me know if you manage to find your way from the top left corner to the bottom right corner! (the black and white version of that maze is here)
I would also recommend checking this link, as it has some nice animations.

Num post antigo eu partilhei código e algumas animações de um algoritmo que criava labirintos aleatórios. Quando partilhei algumas imagens, recebi feedback a dizer que até os labirintos grandes eram fáceis de resolver (penso que aqui encontram o feedback a que me refiro). Portanto já estava na altura de eu arranjar uma maneira melhor de gerar os labirintos! E desta vez, acho que os resultados são melhores.

Os labirintos deste post foram criados por código que está neste repositório do GitHub. O ficheiro README explica como usar o ficheiro wilson_generator.py. Também há a opção de usarem o executável windows que está zippado dentro do ficheiro wilsonExe.rar. (em qualquer um dos casos, o ficheiro wilsonconfig.ini pode ser usado para mudar o tamanho do labirinto)

O modo como o algoritmo funciona é simples. Basta começar um caminho aleatório no canto superior esquerdo da janela. De cada vez que esse caminho aleatório se intersetar a si próprio (criando assim um ciclo), o algoritmo retira esse ciclo do caminho e retoma a construção do caminho aleatório. Sempre que o caminho aleatório tocar numa parte do labirinto que já estava construída, esse caminho aleatório passa a fazer parte do labirinto e começamos outro caminho aleatório noutra posição qualquer. Estes caminhos aleatórios sem ciclos são a base do algoritmo de Wilson para criar uma árvore geradora de um grafo com a seguinte propriedade: qualquer árvore geradora tem igual probabilidade de ser criada.

Como a árvore geradora é escolhida uniformemente de entre todas as árvores geradoras possíveis, em geral o nosso labirinto não tem os defeitos específicos de outros algoritmos, como só ter um par de caminhos muito longos ou ter imensos caminhos, mas todos muito curtos. Perceber porque é que o algoritmo tem esta propriedade não é completamente impossível: imaginemos que antes de começar o algoritmo, eu visitei cada vértice do grafo e criei uma pilha infinita de direções; ou seja, para cada vértice $v$ do grafo, criei uma sucessão aleatória $\{v_i\}_i$, onde cada $v_i$ é escolhido uniformemente de entre os vizinhos diretos de $v$. Depois de isto ser feito para cada vértice, há uma maneira óbvia de começar a percorrer caminhos no grafo: basta escolher um vértice e seguir as direções que me são dadas! Mas há um pequeno senão: seguir estas direções fará certamente com que encontremos ciclos. Para prevenir isto, antes de começarmos a seguir as indicações que nos são dadas, retiramos todos os ciclos que estejam a ser criados pelas direções que estão nas pilhas... quando isto tiver sido feito, podemos seguir as direções dos vários vértices e criamos assim uma árvore geradora do nosso grafo. Claro que para correr o algoritmo, não criamos pilhas infinitas à priori. Vamos calculando as direções à medida que elas são necessárias.

Os labirintos criados por este algoritmo são bastante equilibrados, no sentido de não terem poucos caminhos muito longos ou muitos caminhos bastante curtos. Na verdade, olhando para este labirinto:

Posso pensar em colori-lo de uma maneira especial: no canto superior esquerdo vou deitar um balde de tinta que muda de cor gradualmente à medida que escorre. O labirinto fica então pintado desta maneira:

(note-se que as cores da "tinta" são cíclicas, para que eu possa sempre criar uma difusão contínua e infinita)
Também gostava de avisar que este algoritmo pode ser particularmente aborrecido de ver correr, principalmente se tiver acabado de começar a correr. Não aconselho ninguém a mudar a configuração save_frames = False para True, porque isso desacelera o algoritmo ainda mais... mas se alguém quiser mesmo, então também é melhor mudar screenshot_bin para uma pasta qualquer que exista, para que as imagens sejam guardadas lá.

E por agora é tudo. Há uma pequena animação do algoritmo no início deste post e um labirinto absurdamente grande no fim! Avisem-me se o completarem, encontrando um caminho do canto superior esquerdo ao canto inferior direito. (a versão a preto e branco está aqui)
Também aconselho este link que tem algumas animações giras.

$600 \times 450$ maze

- RGS

Pocket maths: folding halves into thirds

2019-02-23T21:18:00.000+00:00

< change language

I have folded a piece of paper in half hundreds of times in my life. And probably so did you. Folding a piece of paper in half is fairly easy: just bend the piece of paper until the corners meet, and then crease. That is it. And with this method one can also fold a piece of paper in $4$, in $8$, etc. We just have to successively divide the sections of the paper in half.

But what if we wanted to fold a piece of paper into thirds, as in the picture above? Some people are good at doing that, but they don't really measure anything: they just do it approximately by looking at the paper and folding where it seems about right. I guess it goes without saying, but mathematicians don't like things to be "about right", they want them right... and even though I wasn't a mathematician, when I was a child I thought that maybe there was a way for me to successively fold different parts of the paper in half, until one of the creases would be the crease at a third of the paper.

I thought of doing that because dividing a piece of paper in half is easy, as everyone knows. So I decided to find a sequence of folds that would allow me to do that! Except that one such sequence does not exist.

I will give you a second to try and prove that for yourself...

The proof is actually quite simple. If such a sequence of folds existed, that would mean that $\frac{1}{3}$ could be written as a finite sum of some fractions of the form $\frac{1}{2^n}$ (can you see why?). We will assume that such a sequence exists, in order to arrive at a proof by contradiction.
Like I already said, if such a sequence exists, then there are some natural numbers $0 < n_1 < n_2 < \cdots < n_k$ such that $$\frac13 = \frac{1}{2^{n_1}} + \frac1{2^{n_2}} + \cdots + \frac1{2^{n_k}}$$ Of course that we can reduce all the fractions on the right hand side to the same denominator, getting $$\frac13 = \frac{2^{n_k-n_1}}{2^{n_k}} + \frac{2^{n_k - n_2}}{2^{n_k}} + \cdots + \frac{1}{2^{n_k}} = \frac{2^{n_k - n_1} + 2^{n_k-n_2} + \cdots + 1}{2^{n_k}}$$ from which one is able to get $$2^{n_k} = 3\times(2^{n_k - n_1} + 2^{n_k-n_2} + \cdots + 1)$$ which is absurd, because $2^{n_k}$ is not divisible by $3$.

And so the dreams of a young boy were shattered...

Toda a gente já dobrou folhas de papel ao meio centenas de vezes. Talvez seja por causa da prática ou talvez seja porque é uma tarefa mesmo simples, mas qualquer pessoa consegue dobrar uma folha ao meio razoavelmente bem. O modo como eu o faço é o que quase toda a gente faz: juntamos os cantos da folha com cuidado e depois vincamos a folha ao meio. Já está. E desta maneira também dá para dobrar a folha em $4$ ou em $8$, é só dobrar ao meio sucessivamente.

Mas e se eu quisesse dobrar a folha em três, tal como na imagem em cima? Há pessoas que o conseguem fazer bastante bem, mas não o fazem de forma precisa, fazem-no a olho. Claro que para efeitos práticos isso costuma chegar, mas para o meu "eu" de 10 anos isso não era satisfatório. Eu queria arranjar uma maneira de conseguir dobrar a folha em três e ter a certeza absoluta que os vincos estavam no sítio certo. Como eu conseguia dobrar a folha ao meio, pensei que se fosse dobrando ao meio as secções certas, conseguiria chegar à dobra do terço da folha.

Eu estava enganado, já que não há nenhuma sequência de "dobras ao meio" que me faça chegar à dobra a um terço da folha.

Pensem um pouco sobre isso...

A prova é bastante simples. Se essa sequência de dobras existisse, então $\frac13$ poderia ser escrito como uma soma de frações da forma $\frac1{2^n}$ (conseguem perceber porquê?). Vamos assumir que a sequência de dobras existe para fazermos uma prova por contradição.
Tal como eu disse em cima, se essa sequência existisse, existiriam números naturais $0 < n_1 < n_2 < \cdots < n_k$ tais que $$\frac13 = \frac{1}{2^{n_1}} + \frac1{2^{n_2}} + \cdots + \frac1{2^{n_k}}$$ Claro que podemos reduzir as frações do lado direito ao mesmo denominador, obtendo assim $$\frac13 = \frac{2^{n_k-n_1}}{2^{n_k}} + \frac{2^{n_k - n_2}}{2^{n_k}} + \cdots + \frac{1}{2^{n_k}} = \frac{2^{n_k - n_1} + 2^{n_k-n_2} + \cdots + 1}{2^{n_k}}$$ de onde se obtém $$2^{n_k} = 3\times(2^{n_k - n_1} + 2^{n_k-n_2} + \cdots + 1)$$ que é absurdo porque $2^{n_k}$ não é divisível por $3$.

E é assim que se destroem os sonhos de uma criança...

- RGS

Pocket maths: how to compute averages in your head

2019-01-27T23:27:00.000+00:00

< change language

Being able to do basic arithmetic calculations in your head is a great skill. Not because it is sexy but because it is useful in your daily life: it can help you check the change you are given when shopping, it can help you know if you will have enough money to pay for your groceries, it can help you estimate how much things cost after the discounts, etc...

This often reduces to being able to sum and subtract decently; sometimes you need to make a couple of small multiplications, but that is it.

More likely than not, you don't need to compute averages every day. But sometimes you just want the scoring average of your team for the past few games, or the average price per person of a given meal, or the average time you spent stuck in traffic this past week... And averages may appear nastier than simply adding or subtracting, because averages also require you to perform a division: in fact, you have to add all the numbers you want and then divide the total by how many numbers there were.

As an example, say I went to have a meal with three friends and we paid $7$, $8$, $10$ and $12$ euros for our meals. What was the average price? In school we learned to do $7+8+10+12 = 37$ and then $37/4 = 9.25$. Sure, this wasn't to bad if you are not afraid to do maths, but:

If you are good with mental maths, you can get to this result even faster;
If you hate doing weird mental calculations, you can get to a nice estimation with little effort.

For the "method" you just need three small steps. First, you guess what the average will be. It is good if you guess close, but it is often more useful if your guess is a round number. So $9$ or $10$ would be useful guesses but $9.2$ maybe not so much. Say I was guessing $10$. Then I just have to find the "score" of my guess, which is done by adding or subtracting the "points" each number gives. The "points" a number gives are just the difference between the number and my guess. So $7$ and $8$ are worth $-3$ and $-2$ points, because they fall short of my guess by $3$ and $2$ units respectively. $10$ is worth $0$ points and $12$ is worth $2$ points, so my final score would be $-3$. In the end, you just divide the score by how many numbers you dealt with, and add that to the guess: so $-3/4 = -0.75$ and $10 + (-0.75) = 9.25$.

Does this look bad? Maybe it does, but this is actually quite decent. If you didn't want to do $-3/4$ in your head you could even notice that $3/4$ is greater than $1/2$ and so the average price for the meal was between $9$ and $9.5$...
As you use this "trick" a couple of times, you will get good at getting decent first guesses, which means you will get a very small final score, which means you will be able to get a very good estimation even if you can't make the final division in your head! What is more, the final division is usually easier than the division of the standard way to compute the average because the number you are dividing is much smaller.

As a little test, try computing the average of these grades: $13$, $15$, $15$, $13$, $14$, $16$, $13$, $15$. I just wrote them down so I will be doing this as I write; I am guessing $14$, which means the scores are $-1$,$1$,$1$,$-1$,$0$,$2$,$-1$,$1$ adding up to a grand total of $2$, that I shall divide by $8$. So $2/8 = 1/4 = 0.25$ and the actual average is $14.25$. Don't believe me? Use a calculator. Do you think I got lucky? Maybe. But so will you. What if there were $7$ numbers instead of $8$? Then $2/7$ would be a bit more than $0.25$ and below $0.33$ (because of $2/6=1/3$) and so the average would be around $14.3$. These estimations are often enough for you and many people will be impressed by how accurate you can be in such a short time... not because the calculations were extremely difficult but because people aren't expecting you to even try.

For the sake of completeness, and you don't have to read this if you don't want to, I will just include the "proof" that the method I described works. Let us call $s$ to my guess, $\bar{x}$ to the average and $x_1, x_2, \cdots, x_n$ to the numbers you want to average out. The number $x_i$ contributes with $x_i - s$ points to the score, so the total score $T$ of my guess is $$T = (x_1 - s) + (x_2 - s) + \cdots + (x_n - s) = x_1 + x_2 + \cdots + x_n - n\times s$$ which I then divide by $n$ and add to the guess $s$.
In one equation, my method gives $$ \begin{align}s + \frac{T}{n} &= s + \frac{x_1 + x_2 + \cdots + x_n - n\times s}{n} \\ &= s + \frac{x_1 + x_2 + \cdots + x_n}{n} - s\\ &= \frac{x_1 + x_2 + \cdots + x_n}{n} = \bar{x}\end{align}$$ which means my method isn't dark magic!

Please use the comment section below to share any mental maths tricks you know and/or use!

Saber fazer contas de cabeça é uma habilidade bestial. Não por ser sexy mas sim porque é extremamente útil nas nossas vidas quotidianas: ajuda-nos a verificar o troco quando compramos algo, ajuda-nos a antever se temos dinheiro suficiente na carteira para pagar as compras ou se temos de usar o cartão, ajuda-nos a estimar o preço dos artigos depois de aplicados os descontos, etc...

Geralmente isto reduz-se a saber somar e subtrair bem de cabeça; às vezes também precisamos de fazer algumas multiplicações pequenas, mas não costuma passar daí.

Claro que o caso muda de figura quando estamos a falar de calcular médias de cabeça. Acho pouco provável que quem estiver a ler isto tenha a necessidade de calcular médias de cabeça com muita frequência, mas de vez em quando gostávamos de conseguir ter uma ideia da média de pontos que a nossa equipa preferida tem marcado, ou saber qual foi o preço médio por pessoa de certa refeição, ou então estimar o tempo médio que gastámos no trânsito esta semana. E fazer médias de cabeça adivinha-se ser mais chato que só fazer somas ou subtações, porque para calcular médias também é preciso fazer uma divisão: na verdade, fazer a média de alguns números é somá-los a todos e depois dividir por quantos eram.

Por exemplo, suponhamos que eu fui jantar com três amigos e pagámos $7$, $8$, $10$ e $12$ euros pelas nossas refeições. Qual foi o preço médio? Para calcular a média pelo método clássico somamos tudo, $7+8+10+12 = 37$ e depois dividimos por $4$, que dá $37/4 = 9.25$. Claro que esta conta não seria particularmente desagradável de se fazer de cabeça, mas:

Aqueles que já são bons a fazer contas de cabeça podem chegar ao resultado final ainda mais depressa;
Quem não gosta de fazer contas "chatas" de cabeça pode chegar a uma boa estimativa final sem muito trabalho mental.

O meu "método" é composto por três passos. Primeiro, adivinhamos quanto é que a média final vai ser. Dá jeito que o nosso palpite esteja perto da média certa mas também costuma ser mais útil que o nosso palpite seja um número redondo. Ou seja, os palpites $9$ ou $10$ são palpites úteis ao passo que $9.2$, apesar de estar mais perto da resposta certa, vai dar mais trabalho. Depois de termos o nosso palpite, vamos calcular qual é a "pontuação" do nosso palpite. Para a "pontuação" do nosso palpite temos de ver com quantos "pontos" é que cada número contribui e depois somamos tudo. Um número que seja mais pequeno que o nosso palpite contribui com "pontos" negativos e um número acima do nosso palpite contribui com "pontos" positivos; a quantidade de pontos é simplesmente a distância do número ao palpite. No nosso exemplo, e assumindo que o meu palpite inicial era $10$, temos que os números $7$ e $8$ dão "pontos" negativos, respetivamente $-3$ e $-2$. O número $10$ contribui com $0$ e o número $12$ contribui com $2$. Somando essas contribuições todas dá $-3$. O último passo é dividir a contribuição total pelo número de contribuintes e somar isso ao palpite: $-3$ (a contribuição total) a dividir por $4$ (o número de contribuintes) dá $-3/4 = -0.75$ que somado ao palpite dá $10 + (-0.75) = 9.25$, a média final.

É bastante provável que o método que descrevi pareça demasiado complicado... Mas há muitas coisas muito simples que são muito complicadas de explicar! O melhor que têm a fazer é testar o método e decidirem se é útil ou não. Para as pessoas que não queriam/conseguiam fazer a divisão $-3/4$ de cabeça, bastava notar que $3/4$ é maior que $1/2$ e portanto a média final era inferior a $9.5$ mas superior a $9$.
À medida que forem usando este truque vão começar a usar palpites iniciais melhores, o que significa que a "pontuação" final do palpite vai ser menor, o que significa que a divisão final vai ser mais simples (e vai dar um número mais pequeno) e portanto as estimativas vão ficar cada vez melhores. De qualquer das maneiras, a divisão que tem de ser feita neste método costuma ser mais simples que a divisão final se fizerem as contas usuais.

Como pequeno teste, tentem calcular a média dos seguintes números: $13$, $15$, $15$, $13$, $14$, $16$, $13$, $15$. Acabei de inventar os números, portanto este exemplo não foi fabricado para ser simpático. Eu vou adivinhar que a média é $14$, o que significa que as contribuições são $-1$,$1$,$1$,$-1$,$0$,$2$,$-1$,$1$, que somadas dão $2$. Como há $8$ contribuintes, calculo $2/8 = 1/4 = 0.25$, que somado ao palpite $14$ dá uma média final de $14.25$. Quem não acreditar pode usar a calculadora para confirmar. Será que eu tive sorte por causa da divisão que tive de fazer no fim..? Talvez, mas vocês também terão sorte nas contas que vos aparecerem à frente. O que teria acontecido se fossem $7$ números em vez de $8$? $2/7$ já não é tão fácil de calcular quanto $2/8$, mas neste caso podíamos notar que $2/7$ é maior que $0.25$ mas menor que $0.33$ (por causa de $2/6=1/3$) e portanto a média final estaria perto de $14.3$. Este tipo de estimativas costuma ser mais do que suficiente para qualquer propósito prático e muitas pessoas ficarão impressionadas pela exatidão da vossa estimativa versus o tempo que demoraram a calculá-a: não porque as contas fossem extremamente complicadas mas porque as pessoas não estão à espera que vocês se dêem ao trabalho.

Para terminar, vou provar que o meu método não é magia negra. Obviamente o método tem um fundamento matemático, que explano aqui: suponha-se que quero calcular a média dos números $x_1, x_2, \cdots, x_n$, vou chamar $s$ ao meu palpite e vou chamar $\bar{x}$ à média real dos vários $x_i$, que se calcula com a fórmula $$\frac{x_1 + x_2 + \cdots + x_n}{n} = \bar{x}$$ Ora cada número $x_i$ contribui com $x_i - s$ "pontos" para a pontuação total $P$ do meu palpite, logo a pontuação total do meu palpite é $$P = (x_1 - s) + (x_2 - s) + \cdots + (x_n - s) = x_1 + x_2 + \cdots + x_n - n\times s$$ que depois de calculada (a pontuação total) deve ser dividida por $n$ e somada ao palpite inicial $s$. Assim, numa única fórmula o meu método é $$\begin{align}s + \frac{P}{n} &= s + \frac{x_1 + x_2 + \cdots + x_n - n \times s }{n} \\ &= s + \frac{x_1 + x_2 + \cdots + x_n}{n} - s \\ &= \frac{x_1 + x_2 + \cdots + x_n}{n} = \bar{x}\end{align}$$
Partilhem comigo os vossos métodos de cálculo mental na secção de comentários em baixo.

- RGS

Introduction to the Hill Cipher

2019-01-13T19:59:00.001+00:00

< change language

The Hill cipher is a very simple cipher that works by using modular arithmetic and matrices.

In a nutshell, your key is a matrix in some $\mathbb{Z}_m$ and you encrypt messages by breaking them up into pieces and then multiplying the pieces by the key matrix. That's it.

I will be giving a workshop on this subject in a near future, and so I decided to write a Python notebook with a brief explanation of how the Hill cipher works, as well as providing an implementation of said cipher. The notebook can be downloaded and read here. I will be glad if you leave any suggestions/comments in the section below!

A cifra de Hill é uma cifra simples que faz uso de noções de aritmética modular e de álgebra linear (mais concretamente, matrizes).

Em duas frases, a cifra de Hill tem como chave uma matriz num dado $\mathbb{Z}_m$ e o modo como encripta mensagens é partindo-a em bocados com o mesmo tamanho e depois multiplicando a matriz chave por esses bocados.

Num futuro próximo eu vou dar um workshop sobre o assunto e por isso decidi escrever um notebook em Python com uma breve explicação da cifra, bem como com uma implementação da mesma cifra. O notebook está disponível para ser lido e descarregado aqui. Se tiverem alguma sugestão ou comentário, estão à vontade para o deixarem na secção em baixo.

- RGS

DumbFire, a simple shooting game

2018-12-26T01:43:00.004+00:00

< change language

DumbFire is a very simple shooting game that I created with Python and pygame and you can find the code here. As of now, the game does not have a menu whatsoever nor it has any kind of instructions...
(btw, to play it use the WASD keys to move and the space bar to shoot; if the coloured balls hit you, you lose health; if you shoot them, you get health back)

I have been incredibly busy so I am not sure I will tidy this up any time soon but feel free to fork the repo in GitHub and to add different types of enemies and maybe some kind of power-up or whatnot. Actually, I would be very interested in hearing from you the answer to: if I could only add one single extra functionality to the game, what would that be?

O jogo DumbFire é um jogo simplecíssimo de tiros que eu fiz com Python e com pygame. O código está no repo usual e convido-vos a fazerem uma cópia do mesmo para experimentarem alterar os tipos de inimigos, talvez juntar um ou outro power-up, etc. De momento o jogo não tem qualquer tipo de menu nem instruções.
(para jogar, usem as teclas WASD para mover a bola e o espaço para disparar; se as bolas coloridas chocarem contra vocês, perdem vida; se acertarem nas bolas coloridas, ganham vida)

Tenho andado com pouco tempo e portanto não acho que vá dar os toques finais neste joguinho em breve... Se puderem, gostava que partilhassem comigo qual seria o detalhe/funcionalidade que diriam que eu devia mesmo pôr neste jogo se eu já só pudesse implementar mais uma coisa.

- RGS

Building an 8-bit addition calculator with circuits

2018-12-20T16:09:00.000+00:00

< change language

I have a childhood friend that had very interesting toys... He used to play around with circuits, multimeters, LED lights, small batteries, etc. I loved going to his house and watch him play with all that. That is probably why I find circuits (in their basic form) very interesting: the current flowing and the logic gates operating on the circuits and whatnot.

Because of that, in this post I will show you how to build an 8-bit addition calculator just with circuits! For that I will be using logic.ly, a circuits simulator that I can run in my browser.

The best way to go about this is by starting with small components and then using a nice feature of logic.ly, which enables one to create "integrated circuits": it takes one circuit we created and transforms it into a single piece.

Of course that before anything else one must know how to add two numbers in binary. It is essentially the same as in with decimal numbers, except that $1 + 1 = 10$ now. To create an addition calculator, we will develop a circuit that adds two numbers bit by bit and that takes care of carries from one place to the other.

The image in the beginning of the post is a circuit that adds two bits $A$ and $B$ together. The result is in $S$ and the $Cout$ light bulb represents the carry digit we may get. This small circuit could be used to add the least significant digits in a sum, storing the least significant digit of the result in $S$ and then signaling if there is any carry in $Cout$.
The idea will be to create a circuit that adds two bits of the same significance (possibly taking a carry bit from the previous operation) and then returning both the resulting bit and a possible carry digit.

Let us start by understanding how one comes up with the first circuit shown, a half adder as it is called in electronics. To do that we will summarize the possible combinations of input bits $A, B$ in a table, together with the results of adding them:
\[ \begin{array}{|c|c|c|c|} \hline A & B & S & Cout\\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 0\\ \hline 1 & 0 & 1 & 0\\ \hline 1 & 1 & 0 & 1\\ \hline \end{array} \]
From the table above one can see clearly that $S$ should be $1$ only when there is exactly one input equal to $1$ and $Cout$ should be $1$ only when both inputs are equal to $1$; this means that $S = A\stackrel{\cdot}{\vee}B$ and $Cout = A\wedge B$ (the symbol $\stackrel{\cdot}{\vee}$ is the exclusive disjunction, also known as XOR).

The next step is creating a circuit that has three inputs $A$, $B$ and $Cin$, which represent two bits of the same significance and a carry bit from a least significant calculation (respectively) and returns the resulting bit $S$, as well as a carry digit $Cout$. If we build this, we will get a full adder. How does one do it?

First we notice that $S$ will only be $1$ if: all three input bits are $1$ or only one input bit is $1$. We already know if only one of $A$, $B$ is $1$, in which case we want $Cin$ to be $0$. If $A$,$B$ are both $1$ or both $0$, we want $Cin$ to be $1$. Joining the two we can write $$S = [(A\stackrel{\cdot}{\vee}B) \wedge \lnot Cin] \vee [\lnot(A \stackrel{\cdot}{\vee} B) \wedge Cin]$$ Carefull inspection shows that this can be simplified to $$S = (A \stackrel{\cdot}{\vee} B) \stackrel{\cdot}{\vee} Cin$$ In fact, that is exactly what is written in the first expression: $S$ is $1$ whenever only one of $A \stackrel{\cdot}{\vee} B$, $Cin$ is $1$.

Having computed $S$ we are only left with computing $Cout$. We know that there will be a carry digit if at least two of the input bits are $1$. We already know when $A$ and $B$ are both $1$, so the other alternative is when only one of $A, B$ is $1$ and $Cin$ is also $1$, hence $$Cout = (A \wedge B) \vee ([A \stackrel{\cdot}{\vee} B] \wedge Cin)$$ We use the exclusive disjuntion instead of the disjunction on the right because that allows us to reuse information we already have. If we put everything together in a circuit, we get this:

Because all switches are turned off, we are computing $0 + 0$ which is $0$, as the two light bulbs show.
If we compare the symbols of the logic gates with the first image in the post, we see two XOR gates on the top, an OR gate on the bottom right (the XOR gates are equal to the OR gate with an extra line on the left) and two AND gates centred on the bottom of the image.

With the full adder in place, we aggregate everything and use logic.ly's feature of creating an integrated circuit which creates this piece:

This piece is a compact representation of the circuit I showed above. With four of these it is straightforward to create a 4-bit addition calculator: a calculator that takes two 4-bit numbers and returns its result:

The image above shows the calculator computing the sum $5 + 12 = 17$. Notice how we plug in a constant $0$ on the first $Cin$ and how the last $Cout$ is connected to the fifth light bulb. Renaming the switches and plugging a switch into the first $Cin$ allows me to create yet another integrated circuit that already adds 4-bit numbers! This is how the modified circuit will look like, before creating the IC:

With two of those, one can create an 8-bit addition calculator, as shown below:

In this particular screenshot, the calculator is computing the sum $73 + 37 = 110$.

And this is it. In the future I might try to build the calculator with actual physical parts, who knows? If you try logic.ly and create something cool, consider sharing it in the comments! Does anyone have the patience to build a 16-bit number adder? Or maybe a circuit that performs subtraction?

Tenho um amigo de infância que tinha uns brinquedos super engraçados... Ele costumava brincar com circuitos, multímetros, LEDs, pilhas, etc. Adorava ir a casa dele e vê-lo mexer naquilo tudo e ele costumava ensinar-me qualquer coisinha. É provavelmente por causa disso que circuitos elétricos me fascinam tanto: como as portas lógicas conseguem fazer tudo o que fazem quando bem conjugadas.

É por causa desse fascínio que, neste post, vou mostrar como construir uma calculadora (que só sabe somar) com circuitos! Para isso vamos usar o logic.ly, um simulador de circuitos que se pode correr no browser.

A melhor maneira de fazer isto é começando com circuitos mais pequenos e depois usar uma funcionalidade do logic.ly que permite compactar circuitos em peças únicas.

Claro que antes de começar a montar seja o que for é preciso saber somar em binário. É essencialmente igual a fazer somas no sistema decimal, mas agora $1 + 1 = 10$. Para criar a calculadora vamos desenvolver um circuito que os soma bit a bit, tratando também do "e vai $1$", que chamamos "carry" em inglês (lamentavelmente não arranjei nenhuma outra designação para este "e vai $1$", e portanto é esta a designação que vou usar durante o post).

A imagem no início do post é de um circuito que soma dois bits $A$ e $B$. O bit resultante fica em $S$ e o "e vai $1$", se houver, fica em $Cout$, sinalizado pela lâmpada. Este circuito em particular pode ser usado para somar os dois dígitos menos significantes, i.e. pode ser usado para obter o dígito mais à direita numa soma.
A ideia vai ser criar um circuito que vá calculando cada bit do resultado, olhando para os bits respetivos do input, e que vá transferindo os "e vai $1$" sempre que necessário.

Vamos começar por entender como criar o primeiro circuito de todos, a que chamamos half adder em eletrónica. Para isso vamos começar por sumarizar todas as combinações que podemos ter no input para $A$ e $B$ e sistematizá-las numa tabela, juntamente com os resultados pretendidos (que obtemos se somarmos $A$ com $B$):
\[ \begin{array}{|c|c|c|c|} \hline A & B & S & Cout\\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 0\\ \hline 1 & 0 & 1 & 0\\ \hline 1 & 1 & 0 & 1\\ \hline \end{array} \]
Pela tabela em cima podemos ver que $S$ deve ser $1$ quando apenas um dos inputs é igual a $1$ e $Cout$ deve ser $1$ quando os dois inputs são $1$; isto significa que $S = A \stackrel{\cdot}{\vee} B$ e $Cout = A\wedge B$ (o símbolo $\stackrel{\cdot}{\vee}$ é a disjunção exclusiva, também conhecida como XOR).

O próximo passo é criar um circuito com três inputs $A$, $B$ e $Cin$, que representam respetivamente dois bits dos números que queremos somar e um possível "e vai $1$" do passo anterior, e que devolve o bit resultante em $S$, bem como o possível "vai $1$" desta adição em $Cout$. Se construirmos isto obtemos um full adder. Como o fazemos?

Primeiro notamos que $S$ só é $1$ se: ou os três bits de input forem $1$ ou se apenas um bit de input for $1$. Já temos como saber se apenas $A$ ou apenas $B$ são $1$, caso em que queremos que $Cin$ seja $0$. Se $A$ e $B$ têm o mesmo valor, então precisamos que $Cin$ seja $1$. Juntando estas duas premissas obtemos $$S = [(A\stackrel{\cdot}{\vee}B) \wedge \lnot Cin] \vee [\lnot(A \stackrel{\cdot}{\vee} B) \wedge Cin]$$ Se olharmos com atenção percebemos que podemos simplificar esta expressão para $$S = (A \stackrel{\cdot}{\vee} B) \stackrel{\cdot}{\vee} Cin$$ De facto, isto é exatamente o que está escrito na primeira expressão: $S$ é $1$ sempre que apenas um de $A \stackrel{\cdot}{\vee} B$ ou $Cin$ tenha o valor $1$.

Tendo calculado $S$, falta-nos calcular $Cout$. Sabemos que "vai $1$" se dois ou mais dos bits de input forem $1$. Já sabemos quando é que $A$ e $B$ são os dois $1$, portanto só falta ver quando apenas um de $A$, $B$ é $1$ e $Cin$ também é $1$, de onde vem $$Cout = (A \wedge B) \vee ([A \stackrel{\cdot}{\vee} B] \wedge Cin)$$ Usamos a disjunção exclusiva em vez da disjunção ("normal") porque desse modo podemos reutilizar uma porta lógica que já temos no circuito. Se montarmos tudo, obtemos o seguinte:

Porque todos os interruptores estão desligados, estamos a calcular a soma $0 + 0$ que é, obviamente, $0$, tal como as duas lâmpadas desligadas mostram.
Se compararmos estas portas lógicas com as da primeira imagem do post, vemos que as duas portas usadas no topo são portas XOR, vemos que temos uma porta OR em baixo à direita (com a mesma forma das portas XOR, a diferença é que a porta OR tem um traço a menos) e duas portas AND centradas na parte de baixo da imagem.

Com este circuito feito, compactamos tudo num circuito integrado (uma funcionalidade do logic.ly) para obter a seguinte peça:

Esta peça não é mais do que uma representação compacta do circuito em cima. Com quatro destas peças é facílimo construir uma calculadora que some dois números de 4 bits:

A imagem mostra-nos o cálculo $5 + 12 = 17$. Note-se que em baixo usámos um sinal constante igual a $0$ como primeiro $Cin$ e que ligámos o último $Cout$ à quinta lâmpada, a de maior significância (16). Se mudarmos os nomes dos interruptores e se ligarmos um interruptor ao primeiro $Cin$, podemos criar outro novo circuito integrado! Esta foi a modificação que fiz para poder criar o circuito integrado:

Com dois desses circuitos integrados maiores faz-se uma calculadora que some dois números de 8 bits, como se vê de seguida:

Nesta captura de ecrã em particular a calculadora computou a soma $73 + 37 = 110$.

Está feito! No futuro sou capaz de tentar construir fisicamente esta calculadora com as portas lógicas mesmo, só porque sim. Se forem experimentar o logic.ly e se fizerem alguma coisa engraçada, partilhem-na nos comentários! Será que alguém tem paciência para fazer um circuito que some números de 16 bits? Ou talvez que faça subtrações?

- RGS

Pocket maths: good rational approximations

2018-12-03T09:50:00.000+00:00

< change language

An obvious way of creating rational approximations for irrational numbers is by truncating its decimal expansion. For example, $3$, $3.1$ and $3.14$ are all rational approximations of $\pi $; as fractions, those approximations would be written $3$, $\frac{31}{10}$ and $\frac{314}{100} $.

Notice how $\frac{314}{100}$ has $100$ as the denominator and yet only produces an approximation correct up to two decimal places.

Claim: by using continued fractions one can obtain better rational approximations for irrational numbers.

Method: if $x $ is an irrational number, instead of truncating its decimal expansion, we can truncate its continued fraction.
Taking $\pi $ as an example, we have $$\pi = 3 + \frac1{7 + \frac1{15 + \cdots}} $$ and by taking $$\pi \approx 3 + \frac17 = \frac{22}{7} $$ we get the approximation $\pi \approx 3.14285\cdots$: it is correct up to two decimal places just as $\frac{314}{100} $, but $7$ is a much smaller denominator than $100$. (And all in all, $\frac{22}{7}$ is a much more elegant fraction that $\frac{314}{100} $)

This can be done for any irrational number and it can be shown that this method produces the best rational approximations for irrational numbers... maybe a post for another time!

What is your favourite continued fraction?

Truncar a expansão decimal de um número irracional é uma maneira óbvia de criar aproximações racionais para esse número. Por exemplo, $3$, $3.1$ e $3.14$ são aproximações racionais de $\pi$: estas aproximações escrevem-se $3$, $\frac{31}{10}$ e $\frac{314}{100} $ como frações.

Note-se que a fração $\frac{314}{100}$ tem $100$ como denominador e produz uma aproximação que só está certa até duas casas decimais.

Proposição: usando frações contínuas conseguimos obter aproximações racionais muito melhores para os números irracionais.

Método: se $x $ é um número irracional, em vez de truncarmos a sua expansão decimal podemos truncar a sua fração contínua.
Por exemplo, a fração contínua do $\pi $ é $$\pi = 3 + \frac1{7 + \frac1{15 + \cdots}} $$ e se a truncarmos depois do $7$, $$\pi \approx 3 + \frac17 = \frac{22}{7} $$ obtemos a aproximação $\pi \approx 3.14285\cdots$: está correta até à segunda casa decimal, tal como $\frac{314}{100} $, mas $7$ é um denominador muito mais pequeno que $100$. (Para além de que $\frac{22}{7} $ é uma aproximação muito mais elegante que $\frac{314}{100} $...)

Isto pode ser feito com qualquer número irracional e também se pode mostrar que este método produz as melhores aproximações racionais para números irracionais... talvez num post futuro!

Qual é a tua fração contínua preferida?

- RGS

Twitter proof: the roots go hand in hand

2018-11-26T10:05:00.000+00:00

< change language

In this twitter proof we will have a look at a rather curious, yet simple, property of real polynomials.

Claim: if $p(x) = \sum_{i=0}^n a_ix^i $ is a polynomial with real coefficients, then for all complex numbers $z $, $$p(z) = 0 \iff p(\bar{z}) = 0$$ which means that the complex roots of $p(x) $ come in conjugate pairs.

Twitter proof: it suffices to show that $p(z) = 0 \implies p(\bar{z}) = 0$. Assume that $p(z) = 0$ and recall that $a_i = \bar{a_i} $: $$\begin{align} p(\bar{z}) &= \sum_{i=0}^n a_i\bar{z}^i \\ &= \sum_{i=0}^n \overline{a_iz^i} \\ &= \overline{\sum_{i=0}^n a_iz^i} = \overline{p(z)} = 0 \end {align} $$

Neste post vamos dar uma olhadela a uma propriedade curiosa, mas simples, dos polinómios com coeficientes reais.

Proposição: se $p(x) = \sum_{i=0}^n a_ix^i $ é um polinómio com coeficientes reais, então para qualquer número complexo $z $ vem $$p(z) = 0 \iff p(\bar{z}) = 0$$ o que significa que as raízes complexas de $p(x) $ vêm em pares conjugados.

Prova num tweet: basta provar que $p(z) = 0 \implies p(\bar{z}) = 0$. Assumamos que $p(z) = 0$ (e lembremo-nos que $a_i = \bar{a_i} $): $$\begin{align} p(\bar{z}) &= \sum_{i=0}^n a_i\bar{z}^i \\ &= \sum_{i=0}^n \overline{a_iz^i} \\ &= \overline{\sum_{i=0}^n a_iz^i} = \overline{p(z)} = 0 \end {align} $$ provando assim o pretendido.

- RGS

Twitter proof: interpolating polynomials

2018-11-19T10:42:00.000+00:00

< change language

In this post I will show the existence of a family of polynomials that are very useful for interpolation. For that I will use what are known as Lagrange polynomials.

Claim: given $n+1$ pairs $(x_i, y_i) $ with $0\leq i \leq n $ and with $x_i \neq x_j $ whenever $i\neq j $, there exists a polynomial $p(x) $ of degree at most $n $ such that $$p(x_i) = y_i,\ i = 0, \cdots, n $$
Twitter proof: consider the polynomial $$l_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} $$ with $l_i(x_i) = 1$ and $l_i(x_j) = 0$ whenever $j \neq i$. Define $p(x) $ to be $$p(x) = \sum_{i=0}^{n} y_i l_i(x) $$ $p(x) $ has degree at most $n $ because so do the $l_i(x) $ and $p(x_k) = \sum_i y_i l_i(x_k) = y_k $.

In a future post I will show the uniqueness of the polynomial satisfying the constraints in the claim.

Neste post vou mostrar a existência de uma família interessante de polinómios, muito útil em interpolação. Para isso vou usar uns polinómios chamados polinómios de Lagrange.

Proposição: dados $n+1$ pares $(x_i, y_i) $ onde $0\leq i \leq n $ e tais que $x_i \neq x_j $ sempre que $i\neq j $, existe um polinómio $p(x) $ de grau menor ou igual a $n $ satisfazendo as igualdades $$p(x_i) = y_i,\ i = 0, \cdots, n $$
Prova num tweet: considere-se o polinómio $$l_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} $$ que satisfaz $l_i(x_i) = 1$ e $l_i(x_j) = 0$ sempre que $j \neq i$. Definimos $p(x) $ como $$p(x) = \sum_{i=0}^{n} y_i l_i(x) $$ $p(x) $ tem grau menor ou igual a $n $ porque os $l_i(x) $ o têm e $p(x_k) = \sum_i y_i l_i(x_k) = y_k $.

Num post futuro mostrarei a unicidade do polinómio que satisfaz as restrições da proposição.

- RGS

Twitter proof: can't touch this (exponential)

2018-11-12T10:15:00.000+00:00

< change language

In this twitter proof we will see that no polynomial grows faster than the exponential function.

Claim: the ratio $\frac{x^p}{e^x}$ tends to $0$ as $x $ tends to infinity.

Twitter proof: recall that by the Taylor expansion of $e^x $ we have $$e^x = \sum_{i=0}^\infty \frac{x^i}{i!}$$ and for $x > 0$ we have $$\frac{x^p}{e^x} \leq \frac{x^p}{\sum_{i=0}^{p+1} a_ix^i} \to 0 $$ where $a_{p+1} \neq 0$ thus proving our claim.

The way I like to look at this is "if the exponential has a bit of every polynomial inside, then it will grow faster than any fixed polynomial $p(x)$" (because, in particular, the exponential "has a bit" of all other polynomials that have degree higher than that of $p(x) $.

Neste post vamos ver que a função exponencial cresce mais depressa que qualquer função polinomial.

Proposição: o rácio $\frac{x^p}{e^x}$ tende para $0$ quando $x $ tende para infinito.

Prova num tweet: sabemos pela expansão de Taylor de $e^x $ que $$e^x = \sum_{i=0}^\infty \frac{x^i}{i!}$$ e portanto, para $x > 0$ temos $$\frac{x^p}{e^x} \leq \frac{x^p}{\sum_{i=0}^{p+1} a_ix^i} \to 0 $$ onde $a_{p+1} \neq 0$ provando assim a proposição.

O modo como eu gosto de interpretar isto é "se a exponencial tem um bocado de todos os polinómios, obviamente vai crescer mais depressa que qualquer polinómio $p(x) $ fixo", porque em particular a exponencial "tem bocados" de todos os polinómios com um grau superior ao de $p(x) $.

- RGS

Twitter proof: irrational high-order roots of 2

2018-11-05T09:50:00.000+00:00

< change language

For this twitter proof we will be using a piece of mathematics straight from the 17th century.

Claim: the number $\sqrt[n]{2} $ is irrational for $n \geq 3$.

Twitter proof: suppose that $n \geq 3$ and $\sqrt[n]{2}$ is rational, i.e. $\sqrt[n]{2} = \frac{a}{b}$ for some integers $a, b $. Then taking the $n $-th power of both sides we get $2 = \frac{a^n}{b^n} \iff b^n + b^n = a^n $, contradicting the well-known Fermat's Last Theorem.

Para esta prova num tweet vamos usar um pedaço de matemática do século 17.

Proposição: o número $\sqrt[n]{2} $ é irracional para $n \geq 3$.

Prova num tweet: suponhamos que $n\geq 3$ e que $\sqrt[n]{2} $ é racional, i.e. $\sqrt[n]{2} = \frac{a}{b} $ para alguns inteiros $a, b $. Se for esse o caso, elevando os dois lados da igualdade a $n $, obtemos $2 = \frac{a^n}{b^n} \iff b^n + b^n = a^n $, contrariando o famoso Último Teorema de Fermat.

- RGS

Twitter proof: the sum of inverses diverges

2018-10-29T08:30:00.000+00:00

< change language

In this post I will share with you my favourite proof that the series of the inverses diverges: $\sum_{i=1}^\infty \frac1i = \infty $.

Claim : the series $\sum_i \frac1i$ diverges.

Twitter proof: consider the series $$ \begin{align} &\frac12 + \frac12 + \frac12 + \cdots = \\ &\frac12 + 2 \times\frac14 + 4\times \frac18 + \cdots = \\ &\frac12 + \frac14 + \frac14 + \frac18 + \cdots \leq \\ &\frac12 + \frac13 + \frac14 + \frac15 + \cdots \end{align}$$ that clearly diverges because it is a series of a constant nonzero term. By the comparison test, the series of the inverses also diverges.

Comment with your favourite way to prove this fact!!

Neste post quero partilhar com todos a minha prova preferida de que a série dos inversos dos naturais diverge: $\sum_{i=1}^\infty \frac1i = \infty $.

Proposição: a série $\sum_i \frac1i$ diverge.

Prova num tweet: considere-se a série$$ \begin{align} &\frac12 + \frac12 + \frac12 + \cdots = \\ &\frac12 + 2 \times\frac14 + 4\times \frac18 + \cdots = \\ &\frac12 + \frac14 + \frac14 + \frac18 + \cdots \leq \\ &\frac12 + \frac13 + \frac14 + \frac15 + \cdots \end{align}$$ que diverge claramente porque é a série em que se soma um termo constante diferente de zero. Pelo teste da comparação, a série dos inversos também diverge.

Comentem qual a vossa forma preferida de provar este facto!!

- RGS

Twitter proof: the Tower of Hanoi

2018-10-02T18:29:00.000+01:00

< change language

In this post we prove what the minimum number of moves to solve the problem of the Tower of Hanoi is!

Claim: let $T(n)$ denote the number of moves it takes to solve the Tower of Hanoi with $n$ disks; then $T(n) = 2^{n}-1$.

Twitter proof: note that to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk. Each time we move the top $n-1$ disks to another pole we must take, at least, $T(n-1)$ moves (by definition of $T$) hence we clearly have $T(n) = 2T(n-1) + 1$. Just notice that $B(n) = 2^n - 1$ satisfies the recurrence relation and that $T(0) = B(0) = 0$.

If you are having trouble understanding what I mean by to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk, check the following sequence of images that contains some of the intermediate steps to solve the Tower of Hanoi with $4$ disks:

First we move the top $3$ disks to the centre pole in $T(3)$ moves...

Then we change the bottom disk to the available pole in $1$ move...

Then we move the top $3$ disks again in $T(3)$ moves!

Neste post vou provar qual é o número mínimo de movimentos necessário para resolver o problema da Torre de Hanoi!

Proposição: se $T(n)$ é o número mínimo de movimentos necessários para resolver o problema da Torre de Hanoi com $n$ discos, então $T(n) = 2^{n}-1$.

Prova num tweet: repare-se que para resolver o problema com $n$ discos, primeiro temos de mexer os $n-1$ discos mais pequenos para uma das duas varas livres, depois mexemos o maior disco para a outra vara vazia, depois voltamos a mexer os $n-1$ discos mais pequenos para cima do disco maior. De cada vez que mudamos os $n-1$ discos mais pequenos de vara, temos de fazer pelo menos $T(n-1)$ movimentos (pela definição de $T$) portanto temos claramente $T(n) = 2T(n-1) + 1$. Agora basta reparar que $B(n) = 2^n - 1$ satisfaz a relação de recurrência e que $T(0) = B(0) = 0$.

Se está a custar a entender o que quero dizer com para resolver o problema com $n$ discos, primeiro temos de mexer os $n-1$ discos mais pequenos para uma das duas varas livres, depois mexemos o maior disco para a outra vara vazia, depois voltamos a mexer os $n-1$ discos mais pequenos para cima do disco maior, vejam a sequência de imagens seguinte, que contém alguns passos intermédios para resolver a Torre de Hanoi com $4$ discos:

Primeiro mudamos os $3$ discos mais pequenos para a vara do meio em $T(3)$ movimentos...

Depois mudamos o disco maior para a vara livre em $1$ movimento...

Depois mudamos os $3$ discos mais pequenos da vara central para a vara mais à direita, em apenas $T(3)$ movimentos!

- RGS

Markov Decision Processes 03: optimal policy variation

2018-10-01T00:35:00.001+01:00

< change language

This post is going to follow up what was discussed here, and I will show you how changing the value of the discount factor may affect what the optimal policy is.

For that, consider the MDP defined below:

This MDP is inspired in the example I have been using; I added an extra state and stripped the MDP of the majority of the transitions so we can focus on what is essential here. From the MDP above there is a clear contender for the title of optimal policy: $$\begin{align} &\pi(H) = E\\ &\pi(T) = D\\ &\pi(TU) = D\end{align}$$ Assume that when we enter the MDP there is a $50\%$ chance we start Hungry and a $50\%$ chance we start Thirsty. If we use the policy $\pi$ then the expected reward is $$E[R | \pi] = 0.5E[R_T | \pi] + 0.5E[R_H | \pi]$$ where $E[R_s | \pi]$ is the expected reward we get by following policy $\pi$ starting from state $s$. From my previous post we know that $E[R_T | \pi] = E[R_H | \pi] = \frac{1}{1-\gamma}$ and hence $$E[R | \pi] = \frac{1}{1-\gamma}$$ But what if we followed the seemingly masochist policy $\pi'$ where we eat compulsively, getting a negative reward, just to be able to get a bigger reward when we drink and recover? Define $\pi'$ as $$\begin{align} &\pi'(H) = CE\\ &\pi'(TU) = D\\ &\pi'(T) = D\end{align}$$ Can we compute the expected reward for this policy, assuming the same $50/50$ probabilities for the initial state? Of course we can, just notice that $$\begin{cases} \begin{align} &E[R_H | \pi'] = -2 + \gamma E[R_{TU} | \pi'] \\ &E[R_{TU} | \pi'] = 5 + \gamma E[R_T | \pi'] \\ &E[R_T | \pi'] = 1 + \gamma E[R_H | \pi'] \end{align} \end{cases}$$ and we can compute those by solving the system it encodes, $$\begin{cases} \begin{align} &x = -2 + \gamma y \\ &y = 5 + \gamma z \\ &z = 1 + \gamma x \end{align} \end{cases}$$ giving $$\begin{cases} \begin{align} &x = -\frac{\gamma ^2+5 \gamma -2}{\gamma ^3-1}\\ &y = -\frac{-2 \gamma ^2+\gamma +5}{\gamma ^3-1}\\ &z = -\frac{5 \gamma ^2-2 \gamma +1}{\gamma ^3-1} \end{align} \end{cases}$$ for a final expected reward of $$E[R | \pi'] = \frac{6 \gamma ^2 + 3 \gamma - 1}{2 \left(1 - \gamma^3\right)}$$ Is this value greater than $E[R | \pi]$? With a bit more maths, one can find that for the legal values of $\gamma$, $$E[R | \pi'] \geq E[R | \pi] \iff \gamma \geq \frac34$$ For example, if $\gamma = 0.9$, then the regular policy $\pi$ has an expected reward of $10$ but the masochist policy $\pi'$ is worth $\approx 12.1$; at $\gamma = 0.75$ they are both worth $4$ and for $\gamma = 0.5$, $\pi$ has expected reward $2$ while $\pi'$ only has $\approx 1.14$.

This actually makes some sense: we would only consider the policy $\pi'$ if the $+5$ we can get, even though it comes amortized, is better than losing $-2$ right now; i.e. if we see the $+5$ as a long-term investment that will compensate our loss of $-2$. In particular, losing $2$ now and gaining an amortized $\gamma 5$ must be better than the safer option which is to go back and forth between being Hungry and Thirsty: if we are starting in the Hungry position, we either do $$EC \to D \to E,\ \text{following } \pi'$$ or we do $$E \to D \to E,\ \text{following } \pi$$ The first sequence is worth $-2 + 5\gamma + \gamma^2$ while the second sequence of actions is worth $1 + \gamma + \gamma^2$; therefore we would prefer $\pi'$ over $\pi$ whenever $$\begin{align} -2 + 5\gamma + \gamma^2 > 1 + \gamma + \gamma^2 &\iff -2 + 5\gamma > 1 + \gamma \\ &\iff -2 + 4\gamma > 1 \\ &\iff \gamma > \frac34 \end{align} $$ If we start in the Thirsty position, we either do $$D \to EC \to D,\ \text{following } \pi'$$ or we do $$D \to E \to D,\ \text{following } \pi$$ The first sequence is worth $1 - 2\gamma + 5\gamma^2$ while the second sequence of actions is worth $1 + \gamma + \gamma^2$; this means that, when we start Thirsty, we would prefer $\pi'$ over $\pi$ whenever (remember that $\gamma \geq 0$) $$\begin{align} 1 - 2\gamma + 5\gamma^2 > 1 + \gamma + \gamma^2 &\iff - 3\gamma + 4\gamma^2 > 0 \\ &\iff \gamma > \frac34 \end{align}$$ So we can see that everything adds up nicely; regardless of our starting position, we would prefer $\pi'$ over $\pi$ whenever $\gamma > 0.75$ so that is exactly the final result we got.

This concludes this post. We have seen how the value of $\gamma$ might affect what the optimal policy is! This example might seem fabricated, but that is because I wanted to show these changes in optimal policies with the simplest example possible. In real life the MDPs are way bigger and much more complex, so it shouldn't be difficult to believe the value of $\gamma$ might end up being decisive.

In a future post, we will be tackling algorithms to find the optimal policy in a general MDP and hopefully I will find a good example of application to show how they work!

This post was brought to you by the #100DaysOfMLCode initiative.

All posts on the MDP series:
MDP#01 Basics
MDP#02 Discount Factor
MDP#03 Optimal Policy Variation

(tradução indisponível de momento)

- RGS

Markov Decision Processes 02: how the discount factor works

2018-09-29T00:51:00.001+01:00

< change language

In this previous post I defined a Markov Decision Process and explained all of its components; now, we will be exploring what the discount factor $\gamma$ really is and how it influences the MDP.

Let us start with the complete example of last post:

In this MDP the states are Hungry and Thirsty (which we will represent with $H$ and $T$) and the actions are Eat and Drink (which we will represent with $E$ and $D$). The transition probabilities are specified by the numbers on top of the arrows. In the previous post we put forward that the best policy for this MDP was defined as $$\begin{cases} \pi(H) = E\\ \pi(T) = D\end{cases}$$ but I didn't really prove that. I will do that in a second, but first what are all the other possible policies? Well, recall that the policy $\pi$ is the "best strategy" to be followed, and $\pi$ is formally seen as a function from the states to the actions, i.e. $\pi: S \to A$. Because of that, we must know what $\pi(H)$ and $\pi(T)$ are: $$\begin{cases} \pi(T) = \text{action to be taken when Thirsty}\\ \pi(H) = \text{action to be taken when Hungry}\end{cases}$$ We know that both $\pi(H)$ and $\pi(T)$ can be either $D$ or $E$ so we really have $4$ possible policies: $$\begin{align} \pi_1(H) = E&,\ \pi_1(T) = E\\ \pi_2(H) = E&,\ \pi_2(T) = D\\ \pi_3(H) = D&,\ \pi_3(T) = E\\ \pi_4(H) = D&,\ \pi_4(T) = D\end{align}$$ All we have to do now is to measure how good each policy is, and to do that, we will use the rewards! Intuitively, what would be the best policy? The best policy is the one that allows us to collect more rewards.

How do we measure the rewards we can collect, then? We use the mathematical notion of expected value. For each policy, we should compute the expected reward we would get by following it, and then stick with the policy that has a bigger expected reward. We will compute the expected reward of $\pi_2$, the policy I claimed to be the best one, but first we will start with this simpler MDP:

In this MDP we only have one state and one action, which gives a reward of $+1$ whenever we choose it. The obvious policy here is to take the only action available. Suppose we are at a given time step $t$. To compute how good our position in the MDP is, we have to consider the reward we will get when we perform the next action (which will give us $+1$) but we must also consider the rewards we will get in the future:

except that those rewards we will get in the future aren't as good as the $+1$ we are going to receive right now! To compensate for that, we will make them less valuable by multiplying a number smaller than $1$ which we call a discount factor: our $\gamma$. When a reward $r$ is only one time step away, we multiply it by $\gamma$ yielding $\gamma r$; if a reward is three time steps away, we multiply it by $\gamma^3$ giving $\gamma^3 r$ and so on and so forth:

Therefore we get that the expected reward is $$1 + \gamma + \gamma^2 + \gamma^3 + \cdots$$ which can be simplified to $\frac{1}{1 - \gamma}$ when $0 \leq \gamma < 1$.

This computation was fairly easy because our actions never had bifurcations: even though we were looking into the future, we were always sure of where we would be... Now we will compute how good the policy $\pi_2$ is!

Let us assume that when we enter the MDP, we have a $50\%$ probability of starting Hungry and a $50\%$ probability of starting Thirsty. This means that the expected worth of the policy is $$E[R | \pi_2] = 0.5E[R_H|\pi_2] + 0.5E[R_T|\pi_2]$$ where $E[R_H | \pi_2]$ is the expected worth of starting Hungry and $E[R_T | \pi_2]$ is the expected worth of starting Thirsty.

How do we compute $E[R_H | \pi_2]$? Recall that this expected value can be interpreted as the total rewards we will get if we start Hungry and then follow the policy $\pi_2$. If we are Hungry and follow $\pi_2$, our action will be $\pi_2(H) = E$. If we Eat when we are Hungry, we get a reward $+1$ and then: there is a $10\%$ chance that we stay Hungry and there is a $90\%$ chance that we become Thirsty. This means that $$E[R_H | \pi_2] = 1 + 0.1\gamma E[R_H | \pi_2] + 0.9\gamma E[R_T | \pi_2]$$ What does this expression mean? The term $+1$ is the immediate reward we get when we choose to Eat and the remainder $0.1\gamma E[R_H | \pi_2] + 0.9\gamma E[R_T | \pi_2]$ accounts for the future rewards we hope to get (as in, expect to get).
Recall that when we are evaluating the worth of an action, we also have to think ahead (into the future) and account for the rewards we might get if we go down that road, making them slightly less valuable by multiplying with $\gamma$. Therefore, $$0.1\gamma E[R_H | \pi_2] + 0.9\gamma E[R_T | \pi_2]$$ breaks down into $0.1\gamma E[R_H | \pi_2]$ for what we might get if, after Eating, we stay Hungry ($E[R_H]$), and $0.9\gamma E[R_T | \pi_2]$ for what we might get if we become Thirsty ($E[R_T]$). Those expected values are multiplied by $\gamma$ because they are only future rewards and then the extra coefficient, either $0.1$ or $0.9$, accounts for the fact that we are not certain of where we will be.

In a similar way we get that $$E[R_T | \pi_2] = 1 + 0.1\gamma E[R_T | \pi_2] + 0.9\gamma E[R_H | \pi_2]$$ For the sake of brevity let me write $x = E[R_H | \pi_2]$ and $y = E[R_T | \pi_2]$. Rewriting the two equations from above we have $$\begin{cases} x = 1 + 0.1\gamma x + 0.9\gamma y \\ y = 1 + 0.1\gamma y + 0.9\gamma x \end{cases}$$ which is a system of two equations with two unknowns! If we solve it we find $$\begin{cases} x = E[R_H | \pi_2] = \frac{1}{1 - \gamma} \\ y = E[R_T | \pi_2] = \frac{1}{1 - \gamma} \end{cases}$$ that we can plug in the first expression $$E[R | \pi_2] = 0.5E[R_H|\pi_2] + 0.5E[R_T|\pi_2]$$ to get $$E[R | \pi_2] = \frac{1}{1 - \gamma}$$ It is not surprising that this gave the exact same result as the simpler MDP above: even though we are not sure of where we will start and we won't be able to tell to where will be going, whenever we act we get a reward of $+1$; for example, this could happen:

If $\pi_2$ is in fact the best policy, then this value $\frac{1}{1 - \gamma}$ will be greater than the worth of any of the three remaining policies. It is fairly simple to see that $E[R | \pi_3] = 0$. Computing $E[R | \pi_1]$ and $E[R | \pi_4]$ is similar, so we will do $\pi_1$ only: $$\begin{cases} E[R_H | \pi_1] = 1 + 0.1\gamma E[R_H | \pi_1] + 0.9\gamma E[R_T | \pi_1]\\ E[R_T | \pi_1] = 0 + \gamma E[R_T | \pi_1] \end{cases}$$ which gives (if $\gamma < 1$) $$\begin{cases} E[R_H | \pi_1] = \frac{1}{1 - 0.1\gamma}\\ E[R_T | \pi_1] = 0 \end{cases}$$ that adds up to $$E[R | \pi_1] = 0.5\frac{1}{1 - 0.1\gamma} < \frac{1}{1 - \gamma} = E[R | \pi_2]$$ showing that the policy $\pi_2$ is the best one!

After all these calculations, you could try to convince yourself that the general expressions for $E[R | \pi]$ and $E[R_s | \pi]$ are $$E[R | \pi] = \sum_{s \in S} P(s_0 = s)E[R_s | \pi]$$ where $P(s_0 = s)$ is the probability that we start at state $s$, and writing $a = \pi(s)$ $$E[R_s | \pi] = \sum_{s' \in S} P_{a}(s, s')\left( R_{a}(s, s') + \gamma E[R_{s'} | \pi] \right)$$
In this post we calculated some expected rewards with the discount factor. In the next post we will see an example of how changing the discount factor can change the best policy to follow!

This post was brought to you by the #100DaysOfMLCode initiative.

All posts on the MDP series:
MDP#01 Basics
MDP#02 Discount Factor
MDP#03 Optimal Policy Variation

(tradução ainda não está disponível)

- RGS

Markov Decision Processes 01: the basics

2018-09-27T17:39:00.000+01:00

< change language

In this post I will introduce Markov Decision Processes, a common tool used in Reinforcement Learning, a branch of Machine Learning. By the end of the post you will be able to make some sense of the figure above!
I will couple the formal details, definitions and maths with an intuitive example that will accompany us throughout this post. In later posts we will make our example more complete and use other examples to explain other properties and characteristics of the MDPs.

Let me introduce the context of the example:
From a simplistic point of view, I only have two moods: "hungry" and "thirsty". Thankfully, my parents taught me how to eat and how to drink, so that I can fulfill the needs I mentioned earlier. Of course that eating when I am hungry makes me happy, just as drinking when I am thirsty makes me happy! Not only that, but eating when I am hungry usually satisfies me, much like drinking when I am thirsty usually satisfies me.

Suppose that, given the situation I just described, you want to study formally the evolution of my happiness as I take different actions and feel different moods. Markov Decision Processes can be used just for that: studying a system with different states (my moods) and different possible actions (eating/drinking), as well as planning the optimal behaviour (the behaviour that makes me the happiest).

Googling for the definition of MDP will eventually take you to the mathematical one, so we might as well just deal with it now. An MDP is a quintuple $(S,A,P_a,R_a,\gamma)$ where:
$S$ is a set of states, defining the possible ways in which you can be; in my example, $S = \{ \text{Hungry}, \text{Thirsty} \}$ i.e., the states are my moods.

$A$ is the set of actions we can take in each state; in my example, $A = \{ \text{Eat}, \text{Drink} \}$.

$P_a$ is the collection of all transition probabilities. $P_a(s, s') = P(s_{t+1} = s' | s_t = s, a_t = a)$ is the probability that we change to state $s'$ if we used action $a$ when we were in state $s$. In our notation, $s_t$ is the state we are in at time step $t$ and $a_t$ is the action performed when in time step $t$. In the example (check the figure below) we have $P_E(H, T) = P_D(T, H) = 0.9$ (if we are Thirsty and Drink/if we are Hungry and Eat there is a $90\%$ chance we flip states); $P_E(H, H) = P_D(T, T) = 0.1$ (if we Eat when Hungry/Drink when Thirsty there is a $10\%$ chance we don't satisfy our needs); $P_E(T, T) = P_D(H, H) = 1$ (if we Drink when Hungry/Eat when Thirsty we end up exactly as we started).

$R_a$ is the collection of all immediate rewards. $R_a(s, s')$ is a numerical value representing the reward we get when we reach state $s'$ by using action $a$ when in state $s$. Notice that the reward may be good, if $R_a(s, s') > 0$, or it may be bad, if $R_a(s, s') < 0$. In our example the rewards won't depend on $s'$; for example, if we are Hungry and we Eat we get the exact same reward regardless of the state we go to: $R_E(H,H) = R_E(H,T) = R_D(T,T) = R_D(T,H) = +1$, i.e. trying to meet my needs gives a $+1$ reward, while $R_E(T,T) = R_D(H,H) = 0$, i.e. ignoring my needs isn't rewarded nor penalized.

Finally, $\gamma \in [0, 1]$ is the discount factor, which can be thought of as an exchange rate: it says that getting a $+1$ right now is as good as getting $+1/\gamma$ in the next time step. For example, if $\gamma = 0.5$, then getting a $+2$ in the next time step would be as good as getting a $+1$ in this time step. When we are trying to predict what is the best action to take at a given point, we need to consider the rewards of the possible actions BUT we should also try to see some steps ahead, and take into account what are the possible rewards of the future actions that will become available. The bigger $\gamma$ is, the more importance we are giving to future rewards. When $\gamma$ is small, it is as if we don't really care much about what is going to happen in the future, we only care about getting rewards now. The two limits are $\gamma = 0$ and $\gamma = 1$. When $\gamma = 0$, we care nothing about the future; when $\gamma = 0$, a reward of $+1$ now is better than any reward you can be offered in the next time step. When $\gamma = 1$, all future rewards are equally important, whether they are promised to you in the next time step or in $1000000$ time steps.

Now that we defined an MDP, what do we do? Usually one is looking for a strategy to employ that maximizes its rewards. Think of the MDP as a game and suppose the rewards are your points. Whenever you are in a state you must choose an action and then your points will change according to the reward. Your task is to find the best possible strategy for the game. In this context, we usually call policy to our "winning strategy". Commonly represented as $\pi$, the policy is a function $\pi: S \to A$ that receives states and outputs actions: when we are in a state $s \in S$ we should do action $\pi(s)$. For our example it is quite clear that our winning strategy (i.e. our policy) is to Drink when we are Thirsty ($\pi(T) = D$) and to Eat when we are Hungry ($\pi(H) = E)$, right?

How can we justify that? And for more complex examples, how do we find a winning strategy?
To answer the first question, a bit of maths can do the trick... as for the second question, the area of Reinforcement Learning provides us with algorithms to find the winning strategy!

Both questions will be answered in future posts, so subscribe to our mailing list, like the blog on facebook and follow the blog on instagram so as to stay tuned!

This post was brought to you because of the #100DaysofMLCode initiative.

All posts on the MDP series:
MDP#01 Basics
MDP#02 Discount Factor
MDP#03 Optimal Policy Variation

(tradução indisponível por agora)

- RGS

Twitter proof: folding my way to the moon

2018-09-24T19:43:00.000+01:00

< change language

In this twitter proof we will see how the exponential function can mess up with objects from our daily lives!..

Claim: with less than $50$ folds, a piece of paper will be so thick that it will cover the distance from the Earth to the Moon.

Twitter proof: a common sheet of paper is $0.1$mm thick. If we fold it once, it becomes $0.2$mm thick. Folding twice, $0.4$mm. Folding $49$ times, the paper becomes $2^{49}\times 0.1$mm thick, which is around $5.63\times 10^{13} $mm or $5.63\times10^7$km, $141$ times the distance from the Earth to the Moon ($398818$km).

Neste post vamos ver como a função exponencial pode interagir com objetos do nosso quotidiano e criar resultados inesperados.

Proposição: com menos de $50$ dobras, uma folha de papel fica com uma grossura superior à distância da Terra à Lua.

Prova num tweet: uma folha de papel normal tem $0.1$mm de grossura. Se a dobrarmos uma vez, fica com $0.2$mm de grossura. Dobrando de novo, fica com $0.4$mm. Dobrando $49$ vezes, a folha fica com uma grossura de $2^{49}\times 0.1$mm, que dá aproximadamente $5.63\times 10^{13} $mm ou $5.63\times10^7$hm, $141$ vezes mais do que a distância entre a Terra e a Lua ($398818$km).

- RGS

Twitter proof: neural networks and the linear activation function

2018-09-18T17:53:00.002+01:00

< change language

In this post we will see why it is not helpful to have two consecutive layers of neurons with linear activation functions in neural networks. With just a bit of maths we can conclude that $n$ consecutive linear layers compute the exact same functions as $1$ single layer.

Claim: having two fully connected layers of neurons using linear activation functions is the same as having just one layer with a linear activation function.

We just have to lay down some notation in order for the maths to be doable. Assume the two consecutive layers of linear neurons are preceded by a layer with $n_0$ neurons, whose outpus are $o_1, o_2, \cdots, o_{n_0}$.
Let us say that after that layer, there is a layer of $n_1$ neurons with linear activation functions $f_i(x) = a_ix + b_i$; the weight from neuron $t$ of the previous layer to the neuron $i$ of this layer is $w_{t,i}$.
The second layer of neurons has $n_2$ neurons, with linear activation functions $f_i'(x) = a_i'x+b_i'$ and the weight from neuron $i$ of the previous layer to neuron $j$ of this layer is $w'_{i,j}$.

Twitter proof: we will compute the outputs produced by the second layer, in terms of the values $o_1, \cdots, o_{n_0}$ of the $0$-th layer and conclude we obtain a linear function of those. The output of the $j$-th neuron will be:
$$\begin{align} f'_j\left[\sum_{i=1}^{n_1}w'_{i,j}f_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right)\right] &= a'_j\times\left[\sum_{i=1}^{n_1}w'_{i,j}f_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right) \right] + b'_j\\ &=a'_j \left[\sum_{i=1}^{n_1}w'_{i,j}\left(a_i\times\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right) + b_i\right) \right] + b'_j\\ &=a'_j \left[\sum_{i=1}^{n_1}w'_{i,j}a_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right) + \sum_{i=1}^{n_1}w'_{i,j}b_i \right] + b'_j\\ &=a'_j \left[\sum_{i=1}^{n_1}w'_{i,j}a_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right)\right] + a'_j\sum_{i=1}^{n_1}w'_{i,j}b_i + b'_j\\ &=a'_j \left[\sum_{t=1}^{n_0} \sum_{i=1}^{n_1}w'_{i,j}a_i w_{t,i}o_t\right] + a'_j\sum_{i=1}^{n_1}w'_{i,j}b_i + b'_j\\ \end{align}$$ now defining $a''_j = a'_j$, $$b''_j = b'_j + a'_j \sum_{i=1}^{n_1}w'_{i,j}b_i$$ and $$w''_{t,j} = \sum_{i=1}^{n_1} w'_{i,j} a_i w_{t,i}$$ we get that the output of the $j$-th neuron really is $$f''_j\left(\sum_{t=1}^{n_0} w''_{t,j} o_t\right)$$ where $f''_j(x) = a''_jx + b''_j$, a linear function. This concludes our proof!

I wrote this post today because of the #100DaysofMLcode initiative I started (yesterday!)!

Neste post vou mostrar porque é que não é nada útil, em redes neuronais, ter duas camadas consecutivas de neurónios com função de ativação linear. De facto, $n$ camadas consecutivas de neurónios com função de ativação linear calculam exatamente as mesmas funções que apenas $1$ camada!

Proposição: ter duas camadas consecutivas, totalmente ligadas, cuja função de ativação é linear, é exatamente o mesmo que ter apenas uma camada com função de ativação linear.

Para eu poder fazer as contas preciso apenas de estabelecer alguma notação. Vamos assumir que as duas camadas consecutivas de neurónios são precedidas por uma camada com $n_0$ neurónios, cujos outputs são $o_1, o_2, \cdots, o_{n_0}$.
Digamos que a camada seguinte é uma camada de $n_1$ neurónios que usam uma função de ativação linear $f_i(x) = a_ix + b_i$; o peso que vai do neurónio $t$ da camada anterior para o neurónio $i$ desta camada é $w_{t,i}$.
A segunda camada tem $n_2$ neurónios, com funções lineares de ativação $f_i'(x) = a'_ix + b'_i$; o peso que vai do neurónio $i$ da camada anterior para o neurónio $j$ desta camada é $w'_{i,j}$.

Prova num tweet: vamos calcular o output do $j$-ésimo neurónio desta segunda camada, em função dos outputs $o_1, \cdots, o_{n_0}$ da $0$-ésima camada, e verificar que obtemos uma expressão que depende linearmente desses valores. De facto, o output do $j$-ésimo neurónio da segunda camada vai ser:
$$\begin{align} f'_j\left[\sum_{i=1}^{n_1}w'_{i,j}f_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right)\right] &= a'_j\times\left[\sum_{i=1}^{n_1}w'_{i,j}f_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right) \right] + b'_j\\ &=a'_j \left[\sum_{i=1}^{n_1}w'_{i,j}\left(a_i\times\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right) + b_i\right) \right] + b'_j\\ &=a'_j \left[\sum_{i=1}^{n_1}w'_{i,j}a_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right) + \sum_{i=1}^{n_1}w'_{i,j}b_i \right] + b'_j\\ &=a'_j \left[\sum_{i=1}^{n_1}w'_{i,j}a_i\left(\sum_{t=1}^{n_0} w_{t,i}o_t\right)\right] + a'_j\sum_{i=1}^{n_1}w'_{i,j}b_i + b'_j\\ &=a'_j \left[\sum_{t=1}^{n_0} \sum_{i=1}^{n_1}w'_{i,j}a_i w_{t,i}o_t\right] + a'_j\sum_{i=1}^{n_1}w'_{i,j}b_i + b'_j\\ \end{align}$$ definindo agora $a''_j = a'_j$, $$b''_j = b'_j + a'_j \sum_{i=1}^{n_1}w'_{i,j}b_i$$ e $$w''_{t,j} = \sum_{i=1}^{n_1} w'_{i,j} a_i w_{t,i}$$ verificamos que o output do $j$-ésimo neurónio é $$f''_j\left(\sum_{t=1}^{n_0} w''_{t,j} o_t\right)$$ onde $f''_j(x) = a''_jx + b''_j$ é uma função linear. Isto conclui a nossa prova!

Escrevi este post hoje por causa da iniciativa #100DaysofMLcode que comecei (ontem!)!

- RGS

Pledging to do 100 days of Machine Learning and progress log!

2018-09-17T23:27:00.000+01:00

< change language

It is a shame but I kind of dropped this when I was $41\%$ done...

I hope I man up and finish this in the near future.

After watching this video from Siraj Raval, I decided to jump right on board of the #100daysofMLcode initiative! (even though I am something like 73 days late...) The goal here is to devote (at least) 1h every day, for the next 100 days, to studying ML or writing code!

According to the rules posted by Siraj, I must:

Make a public pledge for this, which this post is;
Make a log of everything, which this post will also be;
Whenever I see something related to this #100DaysofMLCode, be supportive!

Progress log

For the day $0$ I wrote this post and spent quite some time thinking about what I will do throughout. I am thinking of studying several topics about ML and then writing educative posts here, for the blog.

For today I wrote this twitter proof, tackling a mathematical property of neural networks with linear activation functions.
Started reading about Reinforcement Learning and Markov Decision Processes; already imagined a nice example I will be using when writing about this... it will involve cake, lemonade and eventually a stomach ache.
I have been reading more about MDPs, and I found this answer on Cross Validated specially enlightening.
Reading more about the functioning of MDPs in this blog (which seems to have taken inspiration from these slides for this particular blog post).
Kept reading the resources from above; started sketching an example MDP to be used in my next blog post.
Finished sketching the example MDP and did some calculations related to it; started writing the first blog post about this and created a representation of the MDP for the post.
Finished writing and published this post on the basics of Markov Decision Processes.
Started writing the second post on MDPs, where we will explore how the changes in $\gamma $ and the transition probabilities affect the policies.
I wrote another post on MDPs, this time about the discount factor $\gamma$.
Following up on the last post, I wrote here about how the optimal policy can change when the discount factor changes.
Decided to use the Hanoi Towers as a model problem and started encoding it as an MDP; wrote some helper code for that and you can find such code here.
Kept writing the code from the previous day and applied the algorithm of value iteration to the Hanoi Towers, solving them. The code is in this GitHub repo.
Wrote this post on how to encode the problem of the Tower of Hanoi into an MDP.
Wrote the code for the policy iteration algorithm to solve the Tower of Hanoi; the code is in my GitHub.
Today I tried implementing Q-learning to solve the Tower of Hanoi. It isn't learning properly yet, so I decided not to upload the code to GitHub.
For today I have been all over the internet to try and find the reason why my Q-learning algorithm isn't working... Still haven't succeeded.
Because Q-learning wasn't working I tried to implement double Q-learning, just to be sure my problem wasn't one of bias. At first double Q-learning wasn't working as well, but now both algorithms are working just fine! They have been uploaded to GitHub now.
Started writing a Python notebook where I will explain the algorithms and show how to use them to solve the Tower of Hanoi. Those explanations will also be put here in the blog as they are written. The notebook can be found in my GitHub as well.
Kept on working on the notebook! Practically finished the section on value iteration.
I had to stop a bit; sorry for that! I am back and I have been reading about ML on financial markets and have been taking an online course about data science. It isn't exactly the same as ML, but knowing how to handle data ought to make me better at ML, right?
Kept taking the course Data Science: Visualization on edX.
Today I read about using machine learning for text translation.
Advanced a lot in one of the modules of the Data Science course...
And today I finished it!
I started the module on probability...
And today I kept going...
And finished it today!
Today I resumed my work on the Hanoi RL notebook.
Wrote about Q-learning and double Q-learning on my notebook.
Started the new module of the Data Science course.
Kept learning!
Today I kept learning for the course I am taking.
...
...
...
...
...
...
...
...
For the past days I have been studying for my online course... I think I have done around 2/3 of the course by now.

Are you into #100DaysofMLCode as well? Let me know in the comments what you have been doing!

Perdi-me quando estava a $41\%$ desta tarefa, o que é um pouco vergonhoso...

Espero decidir voltar a isto em breve.

Depois de ter visto este vídeo do Siraj Raval, decidi fazer parte do movimento #100DaysofMLCode! (apesar de já vir uns 73 dias atrasado...) O objetivo desta iniciativa é dedicar (pelo menos) 1h por dia, durante os próximos 100 dias, à aprendizagem automática (ML): quer estudando, quer escrevendo código.

De acordo com as regras que o Siraj publicou, devo:

Comprometer-me publicamente a levar esta iniciativa até ao fim (e a fazer "figura de urso" se me perder a meio);
Registar publicamente os meus progressos diários;
Quando eu vir alguma coisa marcada com o hashtag #100DaysofMLCode, devo encorajar os autores.

Registo diário

Para o dia $0$ escrevi este post e gastei algum tempo a pensar sobre o que vou fazer. Tenciono ir estudando tópicos diversos e escrever posts educativos aqui no blog.

Hoje escrevi esta prova num tweet, sobre uma curiosidade matemática relacionada com redes neuronais e a função de ativação linear.
Comecei a ler sobre Reinforcement Learning e Markov Decision Processes. Também já imaginei um pequeno exemplo que vou usar para explicar estas noções; vai involver bolo, limonada e, quando chegar a altura, dores de barriga.
Continuei a ler sobre MDPs e esta resposta no Cross Validated foi particularmente esclarecedora... ou se calhar foi só porque finalmente tudo fez "clique"!
Ler mais sobre o modo como MDPs funcionam neste blog (que parece ter-se inspirado nestes slides para este post em particular).
Continuei a ler os recursos disponíveis aqui em cima; comecei a rascunhar um MDP que vou usar no meu próximo post.
Acabei o rabisco do MDP e fiz umas contas com ele; comecei a escrever o primeiro post do blog e criei uma representação esquemática do MDP para vos apresentar.
Acabei de escrever e publiquei este post sobre Markov Decision Processes.
Comecei a escrever o próximo post sobre MDPs, um post onde se vão explorar os efeitos de alterar o factor $\gamma $ e as probabilidades de transição.
Escrevi outro post sobre MDPs, desta vez sobre o factor de desconto $\gamma$.
No seguimento do último post, escrevi aqui sobre como a melhor estratégia pode variar quando o factor $\gamma$ varia.
Decidi que o problema das Torres de Hanoi vai ser o meu problema exemplo e comecei a codificá-lo num MDP; escrevi algum código para me ajudar nessa tarefa e o dito código pode ser encontrado aqui.
Acabei o código do dia anterior e usei o algoritmo de "value iteration" no problema das Torres de Hanoi, resolvendo-o. O código está todo neste repositório do GitHub.
Escrevi este post sobre como transformar o problema da Torre de Hanoi num MDP.
Escrevi o código para resolver a Torre de Hanoi com o algoritmo da policy iteration; o código está no meu GitHub.
Hoje implementei o algoritmo de Q-learning para resolver a Torre de Hanoi. O código ainda não está a funcionar e por isso ainda não fiz o upload do ficheiro para o GitHub.
Andei por todo o lado na internet a tentar descobrir porque é que o meu algoritmo de Q-learning não está a funcionar... Por enquanto, sem sucesso.
O algoritmo de Q-learning não estava a funcionar e eu achei que pudesse ser um problema de bias, então tentei implementar double Q-learning. Primeiro, nenhum dos dois estava a funcionar, depois consegui pôr os dois a funcionar corretamente! Já fiz o upload do código para o meu GitHub now.
Comecei a escrever um notebook de Python onde vou explicar os algoritmos que implementei e onde mostro como usá-los para resolver a Torre de Hanoi. Essas explicações também vão sendo postas aqui no blog à medida que forem concluídas. O notebook também pode ser encontrado no meu GitHub.
Continuei a trabalhar no notebook e a secção sobre o algoritmo de value iteration está praticamente concluída.
Infelizmente parei um par de dias, mas estou de volta! Tenho lido um pouco sobre ML nos mercados financeiros e tenho continuado um curso sobre ciência de dados que comecei no Verão. Eu sei que ML e ciência de dados não são a mesma coisa, mas saber mexer em dados há de me ser favorável, não?
Continuei o curso sobre visualização de dados no edX.
Hoje li sobre como usar ML para traduzir textos.
Fiz grandes progressos num dos módulos do curso sobre ciência de dados...
E hoje acabei-o!
Hoje comecei o módulo sobre probabilidade.
E hoje continuei-o...
E acabei-o hoje!
Hoje dei continuidade ao trabalho que já tinha feito no notebook sobre RL aplicado à Torre de Hanoi.
Escrevi sobre Q-learning e double Q-learning no meu notebook.
Comecei o módulo seguinte do curso de ciência de dados.
Continuei a aprender.
Hoje dei continuidade ao curso que estou a fazer.
...
...
...
...
...
...
...
...
Nos últimos dias tenho estudado para o curso online. Acho que por esta altura já acabei 2/3 do curso.

Há aqui algum leitor envolvido com o #100DaysofMLCode? Digam nos comentários o que andam a fazer!

- RGS

MatchWalker, a puzzle game of shape and colour

2018-09-16T19:59:00.000+01:00

< change language

In today's post I will be sharing a game I made with just under $400$ lines in Processing, a wrapper for Java that makes drawing to the screen really easy.

The goal of the game is really simple: go from the cell you are standing on (marked with the black outline of the ellipse, in the screenshot) to the cell that is framed in white. To do that, you can move a "cursor" (the black frame) with the $AWSD$ keys to choose the next cell you want to go to. To move, press the space bar. There are a couple of rules to moving, though:

You can only move to the selected cell if it is in the same row or same column as the cell you are in;
You can only move to the selected cell if it has the same colour or the same shape as the cell you are in.

Rule number $1$ says you can only go in the directions these orange arrows cover:

Rule number $2$ says that, from the cells specified by the above rule, you can only go to the white circle, diamond or vertical ellipse (precisely because they are white) or to the orange horizontal ellipse, because it has the same shape as the cell you are in (a horizontal white ellipse).

With these rules in mind, one possible way to finish the puzzle from the screenshot would be to follow these arrows:

The path being: first you go down to the white diamond and then up to the orange diamond; after that you go right to the orange circle, up to the orange vertical ellipse and then left to your final destination, the orange square.

When a given target cell is giving you too much trouble, you can press $Q$ to select a new target (i.e. the white frame chooses another cell for you to go to).

If any of you wants to contribute, there is one improvement I think could be made to the way the board is generated. As of now, I hard-coded four $3\times 3$ pieces and whenever the game starts, I shuffle them into the four corners and then randomly rotate them, thus creating the illusion of having a "new, random board" every time you start:

The board can, however be created in another way: just randomly assign each piece to a position of the board and then use a simple algorithm like a breadth-first or depth-first search, to ensure the graph induced by the pieces is connected. If it is not, just shuffle everything again.

The code is hosted in my GitHub repo; feel free to fork the repo and fiddle with the code! If you manage to find a more elegant way to create the game board, just make a pull request! You can also find Windows and Linux executables here.

Play a bit and let me know what you think!

No post de hoje vou partilhar um jogo que escrevi em Processing e em menos de $400$ linhas de código. Para quem não sabe, programar em Processing é essencialmente programar em Java, mas com umas funcionalidades extra que facilitam a criação de componentes gráficos.

O objetivo do jogo é simples: ir de um quadrado em que estamos (marcado pelo contorno preto à volta da elipse branca) para um quadrado que está marcado a branco. Para o fazer, podemos mexer o nosso cursor (o quadrado preto) com as teclas AWSD para escolher um novo quadrado de destino. Depois de escolhido, podemos mudar a nossa localização carregando no espaço. No entanto, há um par de regras que determinam como nos podemos mexer:

Só nos podemos mudar para um novo quadrado que esteja na mesma linha ou coluna do que aquele onde estamos;
Só nos podemos mexer se o novo quadrado tiver a mesma cor ou a mesma forma do que o quadrado em que estamos.

A regra $1$ diz que só poderíamos ir para quadrados cobertos pelas setas cor-de-laranja:

E a regra $2$ diz que, desses, só podemos ir para os quadrados brancos com o círculo, o losango ou a elipse vertical (precisamente porque são brancos) ou então para a elipse horizontal laranja, porque tem a mesma forma do que o quadrado em que estamos (que tem uma elipse horizontal branca).

Tendo estas regras em conta, um caminho possível para o puzzle da imagem em cima seria o seguinte:

O caminho é, portanto: descer para o losango branco e depois subir para o losango cor-de-laranja; depois, ir para a direita para o círculo laranja, depois subir para a elipse vertical laranja e finalmente ir para a esquerda para o destino final, o quadrado laranja.

Se chegar a um determinado quadrado estiver a ser muito difícil, pode mudar-se o quadrado alvo carregando no $Q$ (i.e. o destino marcado a branco passa a ser outro).

Se algum encarecido leitor quiser contribuir, acho que há uma pequena melhoria que pode ser feita ao modo como o "tabuleiro" é gerado. Por agora, tenho quatro quadrados $3\times 3$ explicitamente programados, e de cada vez que o jogo começa, esses quatro bocados de tabuleiro são distribuídos aleatoriamente e rodados: isto dá a ilusão de que temos um tabuleiro novo de cada vez que jogamos:

O tabuleiro poderia ser criado de outra maneira: baralhamos as $36$ peças de jogo e depois usamos um algoritmo de pesquisa, tipo pesquisa em largura ou pesquisa em profundidade, para garantir que o grafo induzido pela distribuição das peças é conexo. Se não for, baralhamos tudo e repetimos.

O código está todo no meu repositório do GitHub; estejam à vontade para ir ver o código e alterá-lo! Se conseguirem arranjar uma maneira mais elegante de gerar os novos tabuleiros, criem um "pull request"! Também tenho executáveis Windows e Linux aqui, para que todos possam jogar.

Joguem e digam-me o que acham!

- RGS

Pocket maths: your verification code is 446267

2018-09-12T23:59:00.000+01:00

< change language

It has become quite common for online services to provide some form of 2-factor authentication when logging in from unknown devices. For example, whenever I try to access my Gmail account from a computer I never used, I get a text message with a one-time use 6-digit code.

One day I was using that same service to log in into my email, when I noticed that one of the digits in the security code appeared twice, like the $1$ in $315641$. But when I read the other text messages from Google, I noticed that there were plenty more security codes with repeated digits than security codes that had six different digits. I found that weird and then decided to compute the probabilities of these events, just to check whether my intuition was tricking me or not...

We are about to compute some probabilities regarding these $6$-digit codes - which I will start calling PINs for the sake of brevity - with the rather intuitive formula $$P(\text{some property}\ A) = \frac{\text{# PINs that satisfy property}}{\text{# of existing PINs}}$$ It is easy to see that there are a total of $10^6$ valid PINs, so for the different properties we only need to compute the total number of PINs that satisfy it.

Below you can find a table with some properties listed and the probability that the next PIN you will receive on your cellphone satisfies that probability.
(if you find any mistake on the calculations, suspect one of the numbers is wrong or want to know how I computed a specific probability, leave a comment below!)

Property	Probability (up to $2$ decimal places)
$6$ unique digits (e.g. 123456)	$15.12\%$
$5$ or less unique digits (e.g. 525678)	$84.88\%$
$5$ unique digits, repeated digit is consecutive (e.g. 551234)	$18.14\%$
$5$ unique digits, no restrictions on repeated digit (e.g. 024328)	$45.36 \%$
$4$ or less unique digits (e.g. 235293)	$39.52 \%$
$4$ unique digits, repeated ones are together (e.g. 226997)	$3.02 \%$
$3$ or less unique digits (e.g. 123231)	$6.76 \%$
$2$ or less unique digits (e.g. 111331)	$0.28 \%$

After all, having a 6-digit code with a repeated digit is much more common than having a 6-digit code where every digit is different!!

Nos dias que correm já é comum os serviços online oferecerem alguma forma de autenticação a dois passos para proteger as nossas contas. Por exemplo, sempre que tento aceder à minha conta Google a partir de um computador que nunca usei, recebo um sms com um código único de 6 dígitos.

Numa das vezes em que usei esse serviço, reparei que o meu código tinha um dígito repetido, tal como o $1$ em $315641$. Quando olhei para os códigos que já tinha usado em vezes anteriores, reparei que na verdade isso acontecia bastantes mais vezes do que eu estaria à espera. Isto pareceu-me estranho e portanto decidi calcular as probabilidades desses eventos, verificando assim se a minha intuição me estava a pregar partidas ou não...

Vou mostrar uma tabela com probabilidades de várias propriedades destes códigos de $6$ dígitos - a que vou chamar PINs por comodidade minha - com a fórmula intuitiva usual: $$P(\text{some property}\ A) = \frac{\text{# PINs that satisfy property}}{\text{# of existing PINs}}$$ É fácil de ver que há um total de $10^6$ PINs válidos, portanto para cada propriedade que eu escolha só vou ter de calcular o número de PINs que a satisfazem.

A tabela que se segue contém algumas propriedades com as respetivas probabilidades: o próximo PIN que eu receber no meu telemóvel vai satisfazer a propriedade descrita com uma probabilidade igual à indicada.
(se encontrarem erros, se acharem que algum dos números está mal ou se quiserem saber como calculei alguma probabilidade específica, deixem um comentário!)

Property	Probability (up to $2$ decimal places)
$6$ dígitos únicos (e.g. 123456)	$15.12\%$
$5$ ou menos dígitos únicos (e.g. 525678)	$84.88\%$
$5$ dígitos únicos, os repetidos estão juntos (e.g. 551234)	$18.14\%$
$5$ dígitos únicos sem restrições no dígito repetido (e.g. 024328)	$45.36 \%$
$4$ ou menos dígitos únicos (e.g. 235293)	$39.52 \%$
$4$ dígitos únicos, os repetidos estão juntos (e.g. 226997)	$3.02 \%$
$3$ ou menos dígitos únicos (e.g. 123231)	$6.76 \%$
$2$ ou menos dígitos únicos (e.g. 111331)	$0.28 \%$

Afinal de contas é muito mais comum aparecer um código com um dígito repetido do que um código onde todos os dígitos são diferentes!!

- RGS

Teaching a robot how to vacuum clean with genetic algorithms!

2018-08-20T11:45:00.004+01:00

< change language

In this post I want to showcase the beginning of what I think will be a really cool project. After reading a really nice book (that Bill Gates himself recommends) on machine learning, I decided to experiment with genetic algorithms.

For that matter, the main goal here will be to develop a genetic algorithm that teaches a vacuum cleaner how it should move in a dirty room to clean it in the best way possible (that is what is happening in the animation above). The first step is to define what I mean by room: a room will be a rectangular grid where each cell has a number from $0$ to $1$. A cell with a $0$ is perfectly clean and a cell with a number $1$ is as dirty as a piece of floor can get. Below we see a $5\times 5$ room with a robot (in red) already in the middle of the room:

As I read in The Master Algorithm (and frankly I found it very enlightening), when one is going to use genetic algorithms we must previously define the structure of the solution and then the genetic algorithm will fill in the parameters for us.

Having said so, the genetic algorithm will try to learn a decision tree, which will be a binary tree where each node can be of one of two types:

Action node: an action node is always a leaf in our decision tree. If we reach an action node, the robot will move according to the action value of that node;
Sensing node: a sensing node is never a leaf in our decision tree. It has a relative position, to which the robot will look, and a threshold. If the level of dirt in the node we looked at is below the threshold, we will follow the left subtree of this node; otherwise we will follow the right subtree of this node.

As an example, consider the tree with only $3$ nodes, such that the root is a sensing node $(RIGHT+UP, 1/3)$ with left subtree an action node $(LEFT)$ and right subtree another action node $(UP)$. Say the robot is the red square on the image above. To decide where he will move next he traverses its decision tree: the root is a sensing node and so it will look to where the node says (RIGHT and UP) and will notice that there is a very dirty square. The level of dirt of that square is certainly bigger than $1/3$ which is the node threshold, so we proceed to the right subtree. The right subtree is just an action node and so we perform its action, deciding to go UP.

All robots in a population will start with random decision trees and then the genetic algorithm will keep mutating the trees! To create a random decision tree I used a recursive approach. We start by deciding if the root node is going to be an action node or a sensing node. Either way, the parameters of the node are filled in randomly. After that, if we created a sensing node we create two random decision trees and set them as the left and right subtrees of this node, but with a twist! The deeper we go, the less likely we are to create another sensing node and the more likely we are to create an action node. This is so that, in general, starting random trees are small.

With this set in place, mutating a decision tree is also simple (please bear in mind that the mutation events that I am going to describe happen with probabilities that were chosen rather arbitrarily). Again, we do this recursively by traversing the tree and deciding to mutate, or not, each node:

If the node is a sensing node and we are going to mutate it, we can either:
1. Amputate its subtrees and turn this node into an action node;
2. Swap the left and right subtrees;
3. Pick another value as threshold;
4. Change the square to which we look when we reach this node.
If the node is an action node and we are going to mutate it, we can either:
1. Expand this node into a sensing node and set random decision trees as the child;
2. Change the square to which we will move when we reach this node.

Having defined these behaviours, carrying out the simulation is easy: we create a starting population with $N$ individuals and a set of $K$ random rooms per generation. We make each robot clean each room and store their score, which will just be the sum of the cells they cleaned. We then pick the top performing $45\%$ robots. Those will proceed to the next generation and each one of them is also going to be copied and then mutated. The remaining $10\%$ of the next generation is created randomly from scratch.
Notice that this differs a bit from what I used to find on the internet in the sense that the first $45\%$ aren't mutated nor bred together, while the second $45\%$ are forced to be mutated. I took this approach because it was a bit easier than implementing a crossover algorithm for the decision trees, but I might do it as well in the future.

Either way this algorithm performs really nicely! In the end of the post you will find an animation of the best performing robot after a simulation with $100$ generations.

All the code I wrote (and am still writing) for this is available in my GitHub repo. There you can also find a small Java application for you to train your own generations of robots! You can choose the number of robots, the number of rooms each robot trains in and the number of generations. In the end it displays the animation of the best robot in a random room! Here is a screenshot of the app:

I am thinking of writing a series of blog posts as a "tutorial" on how to code all this. Would it be interesting? Let me know!!

Also, consider supporting me on Patreon if you like my content and would like extra benefits!

Neste post quero mostrar uma fase inicial daquilo que está a sre um projeto super interessante. Depois de ter lido um livro bestial sobre aprendizagem automática [ou machine learning], que o próprio Bill Gates recomenda, fiquei com imensa vontade de experimentar usar algoritmos genéticos para alguma coisa.

Foi assim que estabeleci o seguinte objetivo: desenvolver um algoritmo genético que ensina um robot a aspirar o chão de uma sala (é isso que está a acontecer na animação do início do post). O primeiro passo é definir o que é uma sala: uma sala é uma grelha retangular onde cada célula tem um número entre $0$ e $1$. Uma célula com o número $0$ está perfeitamente limpa e uma célula com o número $1$ está tão suja quanto é possível e imaginável. De seguida vemos uma imagem de uma sala $5\times 5$ com um robot (a vermelho) no centro:

Quando li A Revolução do Algoritmo Mestre (que achei francamente esclarecedor), percebi que quando usamos algoritmos genéticos temos de definir, à priori, a estrutura da solução de que estamos à procura; os algoritmos genéticos só preenchem os parâmetros.

Tendo percebido isso, decidi que o algoritmo genético ia tentar aprender uma árvore de decisão, que para este projeto seria uma árvore binária onde cada nó é de um de dois tipos:

Nó de ação: um nó de ação é sempre uma folha na nossa árvore de decisão. Se chegarmos a um nó de ação, o robot limita-se a deslocar-se para a posição indicada nesse nó.;
Nó com sensor: um nó com sensor nunca é uma folha. Tem indicada uma posição - para onde o robot vai olhar - e um valor numérico que serve de bitola. Se o nível de sujidade da célula para onde olhámos estiver abaixo da bitola, seguimos pela a sub-árvore esquerda, caso contrário seguimos pela sub-árvore direita.

Tome-se como exemplo uma árvore com $3$ nós apenas, onde a raíz é o nó com sensor $(DIREITA+CIMA, 1/3)$, onde a sub-árvore esquerda é o nó de ação $(ESQUERDA)$ e onde a sub-árvore direita é o nó com ação $(CIMA)$. Suponhamos que o robot é o quadrado vermelho da imagem em cima. Para decidir para onde vai temos de atravessar a árvore de decisão: a raíz é um nó com sensor, portanto olhamos para o quadrado em CIMA e à DIREITA (célula com rebordo encarnado) e notamos que é uma célula bastante escura (muito suja). O nível de sujidade dessa célula é certamente maior que $1/3$, que era a bitola da raíz da árvore. Por causa disso, seguimos para a sub-árvore direita onde encontramos um nó com ação que nos manda seguir para CIMA.

Todos os robots numa população começam com árvores de decisão aleatórias e depois o algoritmo genético vai ter a árdua tarefa de induzir mutações! Para criar árvores de decisão aleatórias usei um método recursivo. Começamos por decidir o tipo de nó da raíz e depois escolhemos os seus parâmetros aleatoriamente. Se o nó for do tipo com sensor, criamos outras duas árvores de decisão aleatórias e usamo-las como sub-árvores esquerda e direita do nó que acabámos de criar. Há apenas um pequeno detalhe: quanto mais "fundo" estivermos na árvore, mais provável é que um nó seja um nó de ação e menos provável é que seja um nó com sensor. Fazemos isto para que, em geral, as árvores aleatórias não sejam grandes.

Com tudo isto já definido é relativamente fácil de induzir as mutações nas árvores (note-se que as mutações que vou descrever acontecem com probabilidades que eu escolhi de forma relativamente arbitrária). Usamos de novo uma metodologia recursiva: atravessamos a árvore, tentando induzir mutações em cada nó:

Se o nó for um nó com sensor, podemos:
1. Amputar as suas sub-árvores e transformá-lo num nó com ação;
2. Trocar as sub-árvores esquerda e direita;
3. Escolher uma nova bitola;
4. Mudar a célula para onde temos de olhar.
Se o nó for um nó com ação, podemos:
1. Transformar o nó num nó com sensor e atribuir árvores aleatórias como sub-árvores;
2. Mudar a célula para onde nos deslocamos quando chegamos a este nó.

Com estes comportamentos definidos só falta a estrutura da simulação: criamos uma população inicial com $N$ indivíduos e para cada geração criamos $K$ salas aleatórias. Pomos cada robot a limpar cada sala e damos uma pontuação que vai ser o somatório dos valores das células que foram limpas. Da população toda, escolhemos o top $45\%$. Esses seguem para a próxima geração; são também copiados - para perfazerem outros $45\%$ da próxima geração - e nas cópias induzimos mutações. Os $10\%$ que faltam são compostos por robots novos aleatórios.
Repare-se que isto é um pouco diferente daquilo a que eu estava habituado a ver na internet: os primeiros $45\%$ não são mutados nem se reproduzem entre si, ao passo que os segundos $45\%$ são necessariamente alterados. Segui esta via porque achei um pouco mais simples do que implementar um algoritmo para reproduzir árvores de decisão... talvez o faça no futuro.

De qualquer das maneiras o algoritmo funciona bastante bem! No fim do post encontram uma animação do melhor robot de uma das simulações que fiz.

Todo o código que escrevi (e ainda estou a escrever) para isto pode ser encontrado neste repo do GitHub. Também encontram lá um pequeno executável em Java para poderem fazer as vossas próprias simulações! Pode escolher-se o número de robots na população, o número de salas em que cada geração treina e o número de gerações da simulação! No fim o programa mostra uma animação do melhor robot numa sala criada aleatoriamente. De seguida encontram uma captura de ecrã do programa:

Estou a pensar escrever uma série de posts em formato de "tutorial" sobre como programar isto. Parece-vos interessante? Dêem-me o vosso feedback!!

Já agora, considerem apoiar-me através do Patreon se gostam do meu conteúdo e se querem benefícios extra!

- RGS

Become a Patron!

Twitter proof: not too hairy

2018-08-18T12:32:00.000+01:00

In this post I will show that some londoners share more than their native language and their propension to get sunburnt. For that we need to notice that there are more than $8.5$ million londoners and that the average human has $100,000$ hairs in the head.

Assertion: there are, at least, $9$ londoners with the exact same number of hairs in their head.

Twitter proof: given the facts above, there are more than $8$ million londoners with less than $1$ million hairs in their head. By the pigeonhole principle this means at least $9$ londoners have the exact same number of hairs.

Neste post vamos mostrar que alguns londrinos partilham mais do que o inglês como língua materna e a propensão para apanhar escaldões. Para isso é preciso notar que há mais de $8.5$ milhões de londrinos e que o ser humano médio tem $100,000$ cabelos na sua cabeça.

Asserção: há pelo menos $9$ londrinos com exatamente o mesmo número de cabelos na cabeça.

Prova num tweet: pelos factos acima, extistem mais de $8$ milhões de londrinos com menos de $1$ milhão de cabelos na cabeça. Assim, pelo princípio do pombal há pelo menos $9$ londrinos com o mesmo número de cabelos.

- RGS