Vermeille's blog

A differentiable graph for neural networks

Following the work by (Grefenstette et al. 2015) in the paper "Learning to transduce with unbounded memory", they invented a fully differentiable Stack, Queue, and DeQueue, I'm trying to create a differentiable graph model. Although the work is not finished yet since it misses proper experiments, I'm writing this article so that someone may help me with those ideas.

Still, I actually didn't study maths the past 5 years in an academic context, so don't expect perfect notation and terminology, I'm self taught in ML and maths. However, I think the ideas are reasonnably introduced, and that the concept is not totally wrong.

Basic graph model

The simple model stores the edges in an adjancency matrix of size $$|V|\times |V|$$, where row $$a$$ column $$b$$ contains $$P(\text{edge}_{ab})$$, that is: the strength of a link from vertex $$a$$ to $$b$$. The vertices are stored in a vector of size $$|V|$$ where each cell contains $$P(a)$$, ie, the strength of existence of $$a$$. Let's call the adjacency matrix $$\mathbf{C}$$, where $$C_{ab}$$ is the $$a$$th row and $$b$$th column of $$C$$, and $$\mathbf{s}$$ the strength vector. Both the vector and the matrix contains values only in $$[0;1]$$

For two vertices $$a$$ and $$b$$ (I will discuss later about how to adress them), some operations are:

Are two vertices directly connected?

$\text{connected?(a, b)} = s_a s_b C_{ab}$

Returns the strength of the edge between $$a$$ and $$b$$. We can also propose to read $$\mathbf{C}^n$$ to access the graph's transitive closure of nth order.

Successors of $$a$$

$\text{succ}(a) = (\mathbf{s} \circ \mathbf{C}_{*,a}) s_a$

Where $$\mathbf{C}_{*,a}$$, following MATLAB's notation, denotes the $$a$$th column of $$\mathbf{C}$$.

Returns a vector of strength. The $$i$$th value indicates the strength of $$i$$ as a successor of $$b$$.

The predecessor function can be implemented trivially by using rows intead of columns in the matrix.

Change the strength of a vertex

Changing strength of a vertex $$a$$ to target strength $$t$$ with amount $$p$$ is:

$s_a := (1-p)s_a + p t$

So that nothing changes if $$p = 0$$

and similarly for all edges.

Similarly to what have been proposed for the Neural Turing Machine (Graves et al. 2014), I propose two adressing modes: by location and by content. The manipulation of the associated graph function almost work the way the Neural Random Access Machine (Kurach et al. 2015) uses its modules.

By location

Let's take the example of the $$\text{connected?(a, b)}$$ function.

To be able to call this function in a fully differentiable way, we can't hardly choose $$a$$ and $$b$$. We instead have to make $$a$$ and $$b$$ distributions over vertices.

Let $$A$$ and $$B$$ be distributions over vertices. The $$\text{connected?(a, b)}$$ can be used in a differentiable way like this:

$\text{out} = \sum_a \sum_b P(A = a)P(B = b)\text{connected?}(a, b)$ $\text{out} = \sum_a \sum_b P(A = a)P(B = b) s_a s_b C_{a,b}$

Same goes for the successor function:

$\text{out} = \sum_a P(A = a)\text{succ}(a)$

And so on.

However, addressing by locations has severe cons:

• You can't grow the number of vertices. It would need the neural net emitting addressing distributions to grow accordingly.

• As you grow the number of available operations or "views" of the graph (such as adding the ability to read the nth order transitive closure to study connexity, you need to emit more and more distributions over $$V$$.

• You need to emit $$V^2$$ value of $$p, t$$ at each time step to gain the ability to modify each edge. Which is a lot. Way too much. A RNN may be able to do it sequentially, or might not.

Hence, the graph must stay with a fixed size, and the dimensionnality of controls is already huge.

I will discuss a way to reduce dimensionality and allow the graph to have an unfixed size with content.

By content

So far, our vertices and edges were unlabeled. I have no idea how an unlabeled graph would be useful, but the neural net controlling it would have to find a way on its own to know which node is what. And it might not achieve that.

Here, I propose to extend our model with embeddings. With $$d$$ being the size of embeddings, we need an additionnal matrix $$\mathbf{E} \in \mathbb{R}^{|V| \times d}$$ to embed the vertices.

Adressing the nodes is now done by generating a distribution over the nodes defined as the softmax of the similarity (dot product) of the embedding outputted by the neural net and the actual vertices' embeddings.

For instance, let $$\mathbf{x_a, x_b} \in \mathbb{R}^{d \times d}$$ be two embeddings given by the controller. We can have the strength of connection of those embeddings by:

$\text{out} = \sum_a \sum_b \text{softmax}(\mathbf{E} \mathbf{x_a})_a\text{softmax}(\mathbf{E} \mathbf{x_b})_b \text{connected?}(a, b)$ $\text{out} = \sum_a \sum_b \text{softmax}(\mathbf{E} \mathbf{x_a})_a\text{softmax}(\mathbf{E} \mathbf{x_b})_b s_a s_b C_{a,b}$

Same goes for the successor function:

$\text{out} = \text{softmax}(\mathbf{E} \mathbf{x_a}) \circ \sum_a \text{succ}(a)$

We can extend the model again by adding a tensor $$\mathbf{F} \in \mathbb{R}^{|V| \times |V| \times d}$$ to embed the edges, but I'm not sure yet about the use case of the benefices. Maybe one could find it useful to know which (fuzzy) pair of vertices is linked by a given embedded edge $$\mathbf{x}$$, like

$\text{vertex1} = \sum_a \text{softmax}(\sum_b s_b F_{a,b,*} \cdot \mathbf{x})_a s_a E_a$ $\text{vertex2} = \sum_a \text{softmax}(\sum_b s_b F_{b,a,*} \cdot \mathbf{x})_a s_a E_a$

We can derive other operations in a similar fashion easily.

To grow the graph, let the controller output, at each timestep, a pair of an embedding and a strength. At each timestep, add the node with the said embedding and strength to the graph. For the edges, it's possible to either init their strength and embedding to 0, or to initialize the embedding of the edge from the new vertex $$a$$ to $$b$$ as $F_{a,b,*} = \frac{E_{a,*} + E_{b,*}}{2}$ and their strength as a cropped cosine distance of their embedding $C_{a,b} = \text{max}(0, \frac{\mathbf{E_{a,*} \cdot E_{b,*}}}{\Vert\mathbf{E_{a,*}}\Vert \Vert\mathbf{E_{b,*}}\Vert})$

With this addressing mode, the underlying graph structure given by $$\mathbf{C}$$ and $$\mathbf{s}$$ is never accessed by the controller which manipulates only embeddings to allow fuzzy operations. And the number of vertices is never needed for the controller, which allows to use a growing graph without growing the controller, solving the issue we had when addressing by locations.

Experiments

They are to come as soon as I'll find an idea to test this concept, and decided of a clear way to architect the inputs / outputs of the controller. I'm thinking about question answering about relationships between things, but we'll see. I don't really know how to design such an experiment yet.

Maybe the neural net won't be able to learn how to use this. Maybe it won't use it the expected way. That's the kind of things you never really know.

Yahtzee

I will describe a simple AI I did for the Yahtzee game. The solution is not optimal because of one small point. There are probably smarter ways to write this program, but as I needed to write this program quickly to play with my friends at New Year's Eve, (I had less than 3 days, actually), my priority was to have a solution almost guaranteeing me to win, not a beautiful and optimal one. If you know how to make it better, let me know in the comments.

As I am self taught in probability ans statistics, my notations and terminology might not be accurate. You're more than welcome to help me improve this in the comments.

Description

The game of Yahtzee is a mix of poker and dice rolls: you have 5 dices to roll, the ability to reroll any of them twice, and, depending of the combinations you have, score some points. Each combination can be scored only once, and if no combination was made, the player must sacrifice one of them, so that the number of turns is fixed.

The combinations are:

Name Score Description
One Sum of 1s Number of 1s obtained
Two Sum of 2s Number of 2s obtained * 2
Three Sum of 3s Number of 3s obtained * 3
Four Sum of 4s Number of 4s obtained * 4
Five Sum of 5s Number of 5s obtained * 5
Six Sum of 6s Number of 6s obtained * 6
Set Sum of 3 dices Three same dices. Score is the sum of those 3.
Full House 25 Three same dices + two same dices.
Quad Sum of 4 dices Four same dices. Score is the sum of those 4.
Straight 30 Four dices in sequence (1234 / 2345 / 3456)
Full straight 40 Five dices in sequence (12345 / 23456)
Yahtzee 50 Five same dices
Luck Sum of dices Any combination. Usually, when nothing else works.

Each player, in turn do this:

1. Roll all dices. The player can select a combination and end his turn, or...
2. Select some dices to roll again. Then, the player can select a combination and end his turn, or...
3. Select some dices to roll again. Then, the player MUST select a combination to score or sacrifice.

The AI

The numbers

The game has a fairly low dimensionnality. Any of the 5 dices can take values from 1 to 6. Hence, the (naive) number of possible games is $$6^5 = 7776$$. But this is actually a higher bound: the dices are not ordered, and a lot of the combinations are equivalent (11234 is equivalent to 12431, etc). The real number of possible games is given by the formula of unordered combinations with repetitions. With $$n = 6$$ and $$k = 5$$:

$C'_k(n) = {n+k-1 \choose k}$ $C'_{ 5 }( 6 ) = C_{{ 5}}(10) = {{ 10} \choose 5} = \frac{ 10! }{ 5!(10-5)!} = 252$

Which is, fortunately, far from intractable, and we can bruteforce all of them.

We will also find useful later to know how many outcomes are possible for any number of dices.

# of dices # of outcomes
0 1
1 6
2 21
3 56
4 126
5 252

The number of possible actions (set of dices to reroll) is the number of subsets of the dices, ie $$2^k=2^5=32$$.

The program

The program is fairly simple to use: given a dice roll, it will tell you which dices to reroll (if any), and the associated statistical expected score.

First, we need to precompute the score that each roll gets for all of the combinations. I first enumerate each of the (ordered) possible games, compute their score for each combination, and store than in a table of $$7776 \times 13$$.

The user is then prompted to write the hand he got. The objective is the following:

$\text{action*} = \underset{\text{action}}{\operatorname{argmax}} \mathbb{E}[\text{best score | action}]$

ie: find the subset of dices to reroll that leads to the best score (ie, the best scored combination for each possible outcome given this reroll) where $$action$$ is successively one of the 32 possible subsets of dices to reroll, and $$action*$$ the best choice according (with an eager strategy).

This expectation can be computed as follows:

$\text{action*} = \underset{\text{action}}{\operatorname{argmax}} \frac{1}{\text{# of equivalent outcomes | action}} \sum_{\text{possible games} g \text{| action}} \underset{\text{combination} c}{\operatorname{max}}(\text{score for} c | g)$

This is an eager policy that maximizes the score for each turn. As such, this algorithm does not take into account the waste of points that you can make by choosing a combination, to allow maximizing your score for the whole game. As I was unable to think of an optimal solution for this (and I would really enjoy to know if there's one), I chose to apply a (quite arbitraty) penalty to each combination's maximum score following:

$\text{penalty(combination, current_score)} = \exp{-\frac{\text{best possible score for combination} - \text{current_score})}{100}}$

In code terms, this would lead to something like:

1. Read input hand $$r$$
2. Initialize $$e$$, the expectation for each possible reroll, to 0
3. For each possible game $$g_i$$:
1. $$d = \text{dices to reroll to go from } r \text{ to } g_i$$
2. $e[d] \text{+=} \frac{1}{\text{number of possible outcomes for } d} \text{maximum score for } g_i$
4. return $$\underset{\text{d}}{\operatorname{argmax}} e[d]$$

And that's it.

Conclusion

I won, statistically. Which is good. Bad point: my friends were angry because taking some time to make an often "obvious" choice was not worth it according to them :D. Make sure your friends enjoy maths and / or CS before doing something like this!

The code is available on my GitHub page. As I said, don't expect magnificent code.

Writing a french POS tagger (2)

How to choose those confidence levels? That's where we start to apply machine learning.

Okay, we're into maths now, so everything is a number. Let's assign a unique natural integer to every word in our vocabulary, so that $$w_i$$ is the word with the id i, and a unique integer to every POS class, so that $$c_i$$ is the class with the id i.

Maximum Likelihood Estimate

Since we're doing ML, let's use some vocabulary. Everything we extract from the ith word (noted wi) is called "features", denoted , the POS we're trying to tag are named "classes" and hence will be noted c, and our confidence is a probability. If we forget a little about suffixes, prefixes and capitalization, we have only the word as a source of info. Predicting is just the act of doing

$\underset{c}{\operatorname{argmax}} P(c | w_i)$

which is like asking "which class i'm the most confident about considering this word?". How do we find such a probability? We can use a simple algorithm called Maximum Likelihood Estimate which works like this:

$P(c | w_i) = \frac{\operatorname{Count}(w_i\text{ is a }c)}{\operatorname{Count}(w_i)}$

"How many times, in a big text corpus, is $$w_i$$ of class c relatively to is global appearance?". And since the denominator is the same for all classes (it varies solely on w_i), we can leave it off.

$\underset{c}{\operatorname{argmax}} P(c | w_i) = \underset{c}{\operatorname{argmax}} \operatorname{Count}(w_i\text{ is a }c)$

Super simple, but we can't do anything for unknown words despite having all those fancy morphological features. We need something to incorporate them.

Maximum Entropy model

Prediction

Let's say we have what we call a feature vector $$\theta$$, for which $$\theta_i$$ is the $$i$$th feature being 1 if the feature is present, 0 otherwise. When we try to predict the class $$c$$, the ith feature will be more or less discriminative. Let's represent that by weighting it with $$\lambda_{c,i}$$ "how indicative is $$\theta_i$$ for class $$c$$?" where:

• a high lambda means "wow, super discriminative, this is super indicative of this class!"
• a low (negative) lambda means "Wow, super discriminative, this super indicative of NOT this class!"
• and a lambda about 0 means "this is not helping me for class c". Emphasis, $$\lambda_{c,i}\theta_i$$ is NOT a probability, it's just a score. Continuing this way, evaluating the score of class $$c$$ for the whole feature vector is a the dot product $$\lambda_c\cdot\theta$$. Weighting then summing.

Note: Here, $$\lambda$$ is essentially a matrix from which I pick the column $$c$$, which is contrary to everything you'll read in the litterature. I'm doing this because, contrary to what the litterature says, I assume that a feature can be discriminative for every class, whereas most papers wants you to condition the features on the class being predicted, allowing a different set of features per class. With my approach, we have more parameters, some of them will be weighted to 0, but it prevents from early optimization. Later on, and after having analyzed the lambdas, one can purge the unnecessary features and weights in the actual implementation, without having missed a discriminative indication.

Once we have this score, easy stuff, find the class with the best score.

$\underset{c}{\operatorname{argmax}} P(c | \theta, \lambda) = \underset{c}{\operatorname{argmax}} \lambda_c\cdot\theta$

how cool? Wait, how do I choose all those lambdas?

Learning

Well, that's a different story. To make a long story short, we have a very handy algorithm, called Maximum Entropy. It relies on the fact that the probability distribution which best represents the current state of knowledge is the one with largest entropy.

I said earlier that scores weren't probabilities. I say that ME works on probabilities. We need to turn those score into probabilities. First we needs the class scores to be on the same scale. Fairly easy, just divide the score for the class $$c$$ by the absolute score of all $$c$$. We're mapping all of our values to [-1;1].

$\operatorname{not-really-P}(c | \theta, \lambda) = \frac{\lambda_c\cdot\theta}{\sum_{c'}|\lambda_{c'}\cdot\theta|}$

Still not good, we need [0, 1]. Well, we could just +1, but actually, we don't like computers to work on [0;1], because computation in such a range tends to quickly turn to NaN and absurdely small numbers. And divisions and multiplications are not cheap. That's why we prefer to deal with log-probabilities instead of probabilities. Log is monotonic, has nice additive properties and is cute looking function, despite its undefined log(0) value. It turns out that the best way to make probabilities from those scores is the exp function.

$P(c | \theta,\lambda) = \frac{\exp{\lambda_c\cdot\theta}}{\sum_{c'}\exp{\lambda_{c'}\cdot\theta}}$

It maps to the correct values range, and if we take the log probability, the division turns to a substraction and the exp cancel out. How nice.

And the super good thing is that, by whichever mathemagics I'm not fully getting yet (please someone explain?), Maximum Entropy and Maximum Likelihood are linked, which brings us to an optimization objective of:

$\underset{\lambda}{\operatorname{argmin}} -\log \mathcal{L} = -\sum_x\log\frac{\exp{\lambda_c\cdot\theta^{(x)}}}{\sum_{c'}\exp{\lambda_{c'}\cdot\theta^{(x)}}}$

Where $$\theta^{(x)}$$ is the feature vector of the $$x$$th example in the dataset.

Cool. We have to take the gradient with respect to lambda, which gives us

$\frac{\partial \mathcal{L}}{\partial\lambda_c} = \sum_x (1\{x\text{ is a }c\}\theta^{(x)} - \sum_c P(c | \theta^{(x)}, \lambda)\theta^{(x)})$

with this derivative, we can take a simple iterative approach to update lambda.

$\lambda := \lambda - \alpha\frac{\partial \mathcal{L}}{\partial \lambda}$

This is quite slow, but it works.

And in the end, you have your model.

Wait, what about the context? We used only features from the word, and we can't disambiguate from the very first example "je commande" and "une commande". Well, we'll have to use something a little smarter than a Maximum Entropy Model and use a MEMM, a Maximum Entropy Markov Model.

Context

French lacks a lot of NLP tools in the FOSS community. And everyone focuses on english AI. Then, french technology sucks. How sad for us. Thing is, I want an AI in my home, for various automation stuff. And I want it to run locally, for privacy reasons (I don't want to share with companies my personnal audio and video at any single second). Then, someone has to start something. Let's say this someone is me, hahaha, sounds so much like a noble duty, hahaha.

The very first step in NLP is to have a POS tagger, that is, something tagging every word in a sentence with its part-of-speech (verb, noun, pronoun, adjective, adverb, etc). Having this allows to have another features that will allow higher level model to generalize more easily (like "oh, this word is a noun. Even if I never saw this word before, I know that this sentence is synctactically correct") and with less data.

One might at first think that this is not even an issue: look at the dictionnary entry for this word. Sadly, language is highly ambiguous. Let's consider "Je commande" (I order) and "une commande" (an order); depending on the context, "commande" is either a noun or a verbal form. Thankfully, french is much more morphologically rich than english, which makes it a less ambiguous language and provides more patterns in the words to guess their POS (like a word ending in "ly" is most likely an adverb).

Word features

Alright, let's brainstorm for a little, and see what kind of clues we can have to guess a word's POS. in machine learning terminology, that's called "features".

• hopefully, we already know the word, and this word will have a clear frequential dominance of one its many possible POS. For instance, the determiner "la" is ambiguous with "LA" (Los Angeles), but the determiner occuring much more than the city, always tagging it as the determiner will fail in only very few cases. Same applies for the "est" (a form of "être"/"be") and "est", the latin locution.
• Case would also help disambiguate the LA case. So, keeping the shape is a good feature. We'll unlikely to know every city and possible name and every organisation etc, then something starting with a capitalized letter is actually a good indication to tag it as a proper noun.
• If we don't know the word, we can use some morphological features of french. Suffixes like "er", "é", "ées", "ée", "eindre", "oindre", "ir", "issons", "issez", "ent" are very strong features.
• Same applies for prefixes.

Great. But they're another question. More than one, actually. How much can I trust every of these features? What are their relative levels of confidence? I mean, I believe they help. I don't know how if I'm right, and if I am, I don't know how much. A "ement" prefix is alwyas an adverb (tbh, I just don't have any counter example on top of head right now), while "er" is super often discriminative to infinitive verbs, but one counter example could be the adjective "léger" (not heavy), so we're slightly less confident in this one.

How to choose those confidence levels? That's where we start to apply machine learning.

As a computer geek who eventually turned into a software engineer, one of the questions I've been asked the most (if not the most), is

Can you hack someone's service account?

And I'm sure it's super common among SWEs, and I'm sure I'm not the only one raging about that.

No, I fuckin' can't.

To understand why, let me explain what it takes to hack something.

An internet service

Any internet service (GMail, Facebook, MSN, any blogging service, etc) is a (complex) system built by engineers. Compare it to an engine, in a mechanical sense, or an electronic circuit, if you like, in a black box. This service is cut into many different parts:

• The web view is what you actually see and quite often the only way you have to use the website. On a minimal or poorly designed website, you directly receive the view filled with the data (the content of the page).

• Sometimes, this webview calls another service on the web. For exemple, when you go on Facebook, you want to see the webview. When it's showing, the webview queries another service on the web to know what it must show, this service is known as an API. The API sends data back to the webview in an easy to process but very not pretty way.

• Both of them are generated on a webserver where the company's code is running. You have absolutely no control on that. Actually, that's all of what hacking is about: be able to access this server and do bad stuff.

• Most of the time, there's also a database service where all of user data is stored. This is the most precious piece of such services. Breaking into this is actually even better than the webserver. Engineers know that. That's why it has most often no interaction to the external world. It's directly accessible only from the inside of the company, and very few people have the credentials. For such big companies, most engineers never see actual data, and work only on generated and fictious data for privacy concerns, some being by company's ethics, other enforced by law. So that data can be actually rendered to the user, the webserver queries the database about what's needed, filters the result and renders it to the webview or the API.

How do we get in?

You have to find a weakness of the system. You have to misuse it. If we continue with the analogies proposed before, the question of hacking is:

Given what we could see and how we could interact with the engine, how can we misuse it so that it does what we want?

If you have a car with an artificial speed limitation, you have to understand how the engine works, why it has this limitation, and how you can remove it. Not that hard'uh? Everybody at least a little known in mechanics can do that! Sure thing SWEs know how software works and can do the same!

Nope. In the case of an internet service, you can't even touch the engine. You can only see what it produces, and use it in the way engineers allowed you. You don't know how it works because most of the time the company keeps it secret. That's trying to bypass the car's speed limitation by only using the car's controls. Now it sounds way harder, doesn't it?

What is hacking about, in the end?

Hacking is misusing you service, trying to guess what are the mistakes the engineers could have done, so that you can do more than what you should. It's about forgetting to handle server's state properly when doing two opposite actions; not securing some text fields, allowing you to inject code (super old, everybody's aware about this one), not checking properly filetypes when uploading files etc.

So, the hacker has to guess, try, fail, imagine what the engineers have done wrong. Try everything that comes to his mind, and, hopefully, that'll work. And even if you find a weakness, you have no clue that you can exploit it to do what you'd like. Maybe it will just produce garbage results.

I know a weakness and how to exploit it

Good, you have two choices now:

1. Contact the service, and tell them about it. They'll thank you, you'll save people data, maybe can write an article that will get famous for few weeks, and be given some money by the said company.

2. Keep it for yourself. Obviously, if it gets known, they will eventually fix it, and it will become unusable.

So, exploits are well kept secrets. No, I can't hack your ex-girlfriend's account.

But I had my account hacked!

Well, odds are it's not Facebook's fault. As long as a service has users, there is a major vulnerability: the user's stupidity. Users are dumb. Beyond imagination. They write their passwords in a non secured file on their computers, they use public data like their birthday, or they use publicly available answer to their secret question (seriously guys, just enter garbage if you're asked. And if you want to "hack" someone you know, just ask them for the answer, they'll never remind this question can leak their accounts), they use the same password on every service, they leave their computers unlocked, they believe phishing, etc etc.

If you've been hacked, chances are that you've been stupid at some point. If you want to hack someone, just exploit his stupidity and send a phishing page.