Using Competition to Train ML Systems

Amos Rimon

| April 28, 2021 | 5 mins |

Introduction

In his visionary paper “Computing Machinery and Intelligence,” Alan Turing proposed a test for measuring whether computers can be regarded as intelligent. He called this “The Imitation Game.” Rather than ponder what it actually means to be able to “think” or “feel” – which will always be defined differently by different individuals – Turing searches for a pragmatic definition. He concludes that if you can’t determine if it is a man or a machine in a test, that machine is an “intelligent” being. Perhaps the most fundamental question in the field of Artificial Intelligence begins with a game.

In this post, we will discuss recent uses of games in the field of Machine Learning (ML). Games can be any sort of system affected by multiple agents that have different goals. This premise is often used to define a complex objective that cannot be explicitly stated.

What are GANs?

GANs (Generative Adversarial Networks) were introduced by Goodfellow et al. (2014). It aims to solve the generation of synthetic examples that are “similar” to a given dataset. More specifically, creating a probability distribution over examples that turns our discrete finite dataset into something continuous. This idea greatly impacted the ML world, enabling the generation of Deepfakes and achieving state-of-the-art results in Computer Vision tasks.

GANs provide the technology for creating Deepfakes ( source)

Generative Networks

While Discriminative Networks typically take in high dimensional data and then output something low dimensional, Generative Networks typically take in low dimensional data and create something high dimensional. Generative Networks can be used to generate synthetic pictures of faces, text, and even new musical compositions.

How does it work?

So far we’ve covered the generative part, which is the goal. Now we will focus on the adversarial part – the means.

It is not so straightforward to define whether a generated example could have been sampled from the original dataset. Of course, we could label each example from the dataset as 1 and anything else as 0, but that will incentivize our generative model to simply memorize the original dataset and sample from it, which is not our intention.

One way to define our objective is generating examples that a human can’t distinguish from the original dataset. That is the essence of our proposed method. We train two models simultaneously: G (the generator) and D (the discriminator). The discriminator’s objective is to detect whether a given input came from the original dataset or from the generator’s output, while the generator attempts to output examples that will fool the discriminator. This can be framed as a two-player minimax game with the following value function:

The generator G generates images from a low dimensional distribution G(z), and the discriminator D tries to classify input images into originals and fakes. The Discriminator tries to maximize the cross-entropy between the originals D(x) and the fakes D(G(z)), while the Generator attempts to minimize it. In less mathematical terms, we can imagine that G is a counterfeiter who prints fake money, while D is the cop trying to detect the fake banknotes.

( source)

During the training process, the Generator becomes increasingly good at producing fake examples that seem real, while the Discriminator becomes better at discerning what is real and what is fake.

Adversarial Debiasing

A current hot topic in the ML world is fairness. A fair ML model is one that is unbiased to attributes such as gender, race, or other sensitive parameters. Intuitively, we might think that simply throwing away protected attributes from the data before training or inference will suffice. But it turns out that it is not always so simple to define which attributes are considered protected. For example, a CV of a job applicant might include the words “my husband,” implying the applicant is probably female. So even if we remove the field “gender” from the structured data, we may very likely have correlated features that remain in the processed data. There is a need for more sophisticated methods for creating unbiased ML models.

One such method is called Adversarial Debiasing. In this method, we do not throw away any attributes from the input data, rather we ensure that the protected attributes cannot be predicted with high probability from our model’s prediction. To guarantee this, we train an adversarial model A which aims to detect the protected attributes based on the predictor (P) output. Our total loss function is composed of the predictor loss and the adversarial loss.

( source)

Constrained Optimization

The problem of creating unbiased predictive models can be viewed as a constrained optimization problem. We are interested in minimizing the original loss function of the predictor while satisfying the constraints – having an unbiased model with respect to sensitive attributes.

One of the most well-known methods for solving constrained optimization problems is the Lagrange Multipliers. If it’s been a while since you took some calculus courses or if you haven’t heard of this method before, here’s a quick refresher.

Suppose we want to minimize the following function:

Subject to the constraint:

If we would not have the constraint, we could simply find the solution by equating the gradient to zero:

But how do we fit the constraints into the problem?

Lagrange’s method tells us to introduce a new variable, and create the Lagrangian function:

We now search for extreme points of a new unconstrained problem and these give us candidates for the original problem. Magical, right?

An Intuitive Game-theoretic Explanation

It turns out that the Lagrangian can be the value function of a zero-sum game. Player 1 wants to minimize the expression while they control the values of x and y. Player 2 is looking to maximize the expression while controlling the value of λ. The Nash Equilibrium of this game gives us the values of x and y that satisfy the original constrained problem. How does this make sense?

Assume Player 1 chooses a point that does not satisfy the constraint. In this case, Player 2 can choose a value that will make the total expression explode, thus forcing Player 1 to try to minimize the function F while satisfying the constraint G.

This intuitive interpretation for the Lagrange Multipliers method offers insight for solving complex problems. Instead of attempting to have a single agent satisfy a complex constrained problem, we introduce a game with multiple agents wherein each player focuses on a simpler task.

Conclusion

We have seen multiple use-cases for training competing ML models simultaneously in a game-like setup. This can prove useful in cases where it is hard to define the objective function explicitly (as is the case with GANs), or where we want to solve a constrained optimization problem where it would be easier to use a “divide and conquer” policy. In my humble opinion, this idea is one of the most neat concept in Machine Learning, and I believe it will be applied and generalized to more use-cases in the future.