DGB1 (BScCs). Evolving Strategies for the Iterated Prisoner's Dilemma
The Prisoner's Dilemma 'game' seems unbelievably simple, but it
has generated huge quantities of research. It's a game whose principles
may have wide-ranging explanatory power. For example, some biologists
believe "that many wild animals and plants are engaged in ceaseless
games of Prisoner's Dilemma" (Dawkins 1989, chapter 12). The game may
also explain aspects of economic, social and political behaviour.
You and your opponent are prisoners, suspected of collaborating in a
crime. You have no way of communicating with each other. Your gaolers
offer both of you a choice of two actions: Cooperate or Defect. Here
are the outcomes (in terms of points scored) of the different pairs of
actions:
| | |
What your opponent does |
|---|
| | |
Cooperate |
Defect |
|---|
| What you do |
Cooperate |
3 | 0 |
|---|
| Defect |
5 | 1 |
|---|
So if you both choose the Cooperate action, you both get 3 points.
If you choose the Cooperate action but your opponent chooses to
Defect, then you get 0 and your opponent gets 5. And vice versa: if
you Defect and your opponent Cooperates, you get 5 and s/he gets 0.
If you both Defect, you both get 1 point.
There is only one rational way to play this game: always Defect.
(If you think your opponent will Cooperate, then you can get a higher
score by choosing Defect. If you think your opponent will Defect,
the best you can do is also to Defect.) Yet, and this is the dilemma,
if you had both Cooperated, each of you would have done better! If
only you could have reached a trust-worthy agreement...
As the game stands, it's only mildly interesting: as we've seen,
rational players must both Defect. But there's another version of
the game called Iterated Prisoner's Dilemma. In this version,
you simply play the game repeatedly, an indefinite number of times.
"The successive rounds of the game give us the opportunity to build
up trust or mistrust, to reciprocate or placate, forgive or avenge." (Dawkins, p.206)
Now strategies other than 'always Defect' might be worth playing.
Consider a prisoner who plays the strategy known as 'nice_tit_for_tat'.
In this strategy, the prisoner's first move is Cooperate. On subsequent
bouts, this prisoner simply copies the previous move of the other
prisoner.
Here's an example of how advantageous this strategy can be. Suppose
two prisoners both playing 'nice_tit_for_tat' meet. They
both start by Cooperating, and then they both copy each other's
previous move. So they end up always Cooperating, which gives them
both the highest possible scores.
In this project, the student will research the relevant literature
and then design and build software that allows a pool of prisoners,
each with different strategies, to play Iterated Prisoner's
Dilemma against each other. I have used this as an exercise in
a programming module, so this part of the project should be very
straightforward!
But, in this project, the student will go further. The student
will design and implement a Genetic Algorithm that allows strategies
to be evolved.
The fitness of prisoners will be measured by their performance
when playing Iterated Prisoner's Dilemma against other members
of their generation. The fittest prisoners are the ones who have the
greatest probability of influencing the make-up of the next generation
of the population.
With this program, we will be able to see whether, over successive
generations, strategies such as 'nice_tit_for_tat' are evolved.
Background reading
Skills required
This project will suit a student who has good programming skills.
DGB2 (BScCS). The Baldwin Effect
Programs that emulate evolution are referred to as Genetic Algorithms
or Evolutionary Algorithms; see [Holland 1992].
There is a theory that organisms that can learn have an advantage over
organisms that cannot learn and this advantage can speed up
genetic evolution. This is called the Baldwin Effect. A clear
explanation is given in [Dennet 1991, pp.182-187].
In this project, we seek to demonstrate this effect.
The student will research the relevant literature and then design and
build software that evolves a population of organisms in the cases
both where they have and where they don't have the ability to learn.
Simple graphics in the front-end of the system will allow the user to
observe the spread of good phenes and good genes in the population.
The student's initial designs can be based on the early work described in [Hinton and Nowlan, 1987] and
[French and Messenger, 1994]. But, for higher marks, the student will
incorporate ideas from the later research literature or ideas of their own
and will experiment with variants of the systems.
Background reading
- Dennet, D.C.: Consciousness Explained, Penguin Books, 1991
- French, R.M. and Messinger, A.: Genes, Phenes and the Baldwin
Effect: Learning and Evolution in a Simulated Population,
in Brooks, R. and Maes, P. (eds.), Artificial Life IV,
MIT Press, pp.277-282, 1994
- Hinton, G.E and Nowlan, S.J.: How learning can guide evolution. Complex Systems, 495–502, 1987.
- Holland, J.H.: Genetic Algorithms, Scientific American,
July 1992
Skills required
This project will suit a student who has good programming skills and
a willingness to delve into the research literature.
DGB3 (BScCS). Predicting Differences
You want to predict the selling price of a house, q. You have a dataset that contains examples of recently-sold houses and their selling prices, D.
One simple method is: find k houses in D that are similar to q. Your prediction for q is the mean of the prices of the neighbours. This method is referred to as k nearest-neighbours (kNN). One variant is to calculate a weighted-mean, so that the more similar houses count for more in the prediction.
Another way to predict house prices is to train an artificial neural network (ANN) on dataset D so that, given a house , it can predict its selling price.
There are additionally a number of intriguing ways of combing the two and we will investigate some of these in this project.
Let's illustrate one of these ideas here. We have a dataset D = {<x1, p1>, <x2, p2>, ..., <xm, pm>} containing descriptions of houses x1, x2, ..., xm and their selling prices p1, p2, ..., pm. We can construct another dataset D' by taking pairs of examples, <xi, pi> and <xj, pj> from D and inserting their difference <xi - xj, pi - pj> into D'. We then train a neural network on D'. This neural network, given a pair of houses, predicts the difference in their price. So now, to predict the price of q, we find an example <x, p> in D (e.g. using kNN), we ask the neural network to predict the difference in price between p and x, and we apply this difference to x's price, p.
In this project, we will build and evaluate one or more systems of this kind, comparing them with kNN on its own and ANN on its own. A good student will implement several of the variants (see the Background reading below), and will apply the ideas across a range of domains, e.g. datasets that contains images, e.g. datasets that predict things other than numbers such as prices.
Background reading
Skills required
This project is suitable for a student who wants to study the research literature, has very good programming skills and is unafraid of mathematical notation.
DGB4 (BScCS). Co-Training a Recommender System
Many machine learning algorithms learn from large volumes of labeled data: the labels give 'correct' answers and the algorithm generalises from these. Sometimes, you have large volumes of unlabeled data but only small volumes of labeled data. Co-training is one possible way of coping with this scenario. In one form of co-training, you use two or more (preferably independent) learning algorithms. Iteratively, you use one of the algorithms to provide more labeled data to the other algorithm.
Co-training can be applied to recommender systems, where the shortage of labeled data is a well-known problem, see the paper by da Costa et al 2018, below. In this project, we will explore their ideas further: we will try different recommender algorithms, we will try different datasets, we will try different ways of measuring uncertainty, and so on.
Background reading
-
Arthur F. da Costa, Marcelo G. Manzato and Ricardo J. G. B. Campello, CoRec: A Co-Training Approach for Recommender Systems. Proceedings of the 33rd Annual ACM Symposium on Applied Computing, 2018, https://doi.org/10.1145/3167132.3167209
Skills required
This project is suitable for a student who has very good programming skills.