SCC462 – Distributed Artificial Intelligence
Midterm Assignment
Deadline: 01/03/2023, 4pm. 25 points in total.
Instructions
This assignment consists of essay questions and coding questions.
Please submit your replies on the Quiz available on Moodle. You can only submit
one time.
The Quiz closes on 04/03/2023, 4pm, in order to allow for delayed submissions.
However, submissions made after 01/03/2023, 4pm, will have a 10% penalty in
the grade. Your attempt will be automatically submitted on 04/03/2023, 4pm, if
you do not click to finish the attempt on Moodle.
Coding questions must have many comments. Please use the Precheck button
to check if you made enough comments in your code. Solutions without enough
comments will not be accepted. Note that the system only recognises the #
character for comments.
Coding questions will be checked against test cases, and will be pre-graded based
on the weight assigned to each test that successfully passes. The Moodle Quiz
shows some tests as an example (usually one test), and the Precheck button will
check against the example test with no penalties. There are (many) more tests
that are not visible to you now.
There is no “Check” button. Once you submit, your code will be checked against
all test cases. The final grade is given by me, not by the system.
There are no test cases where the input has wrong type. However, the input could
be such that a calculation is impossible due to theoretical reasons.
This is an INDIVIDUAL assignment. You must study the course contents, and
write your replies and your code based on your understanding.
– Solutions copied from another student will not be accepted, even if they have
minor modifications.
– Solutions found on-line will not be accepted, even if you include a reference.
– You are allowed to check references only for:
* Fundamental Python information. For example, how to handle lists of
lists, how to randomly sample a number between 0 and 1 using the stan-
dard library, etc.
* Theoretical information. For example, what is the formal definition of
a Nash Equilibrium, what is the pseudo-code of AdaBoost (not Python
code), etc.
– Hence, Python code obtained on-line that, for example, implements Ad-
aBoost, calculates Nash Equilibria, etc, will not be accepted.
1
1. Reynolds (1987), despite being a paper in Computer Graphics, was a great inspira-
tion for the development of the potential field approach in robotics, where multiple
force vectors are applied to a robot in order to make it move in an environment.
In particular, usually the robot suffers an attraction force towards its goal, and
repulsive forces against obstacles. Based on Reynolds (1987), however, what are
the potential issues with this approach? (5%)
2. You were hired by “Stuck with Stocks” Investment Company to help them with
team formation problems. They have a set of agents that they use to receive advice
on the best action to take in a certain economic scenario. These agents, however,
are not perfect, so there is a certain probability pi,j of agent i recommending
the action with j-th rank in a certain scenario. In order to increase the quality
of the predictions, “Stuck with Stocks” is currently using teams of 3 agents and
considering the recommendation of each agent as a vote. The recommendation of
the team is the one given by the plurality voting rule. A team can be composed
by different agents, and by copies of a certain agent. Consider that ties are broken
randomly.
We assume that there are 3 possible actions in their problem. Based on simu-
lations, they can estimate the probabilities of the agents in different situations.
You were required to implement a function that returns the best team of 3 agents
based on their estimations. Hence, in detail, you must implement the function
findBestTeam(bestAgent, diverseAgent1, diverseAgent2), where:
- bestAgent, diverseAgent1 and diverseAgent2 represent the probability dis-
tribution function of the agent that is usually considered the strongest one, and
the probability distribution function of two additional “diverse” agents. These are
represented as lists, following the ranking across actions. That is, the first element
corresponds to the probability of recommending the best action, and the second
and third elements corresponds to the probability of recommending the two other
suboptimal actions, in order. For instance, bestAgent = [0.6, 0.3, 0.1] would mean
that the usually best agent would recommend the best action with probability 0.6,
the second best with probability 0.3, and the third best with probability 0.1.
- The method returns a tuple (team, probBestAction). team is a list with 3
elements, representing how many copies of each agent would be used. For example,
team = [2, 1, 0] means a team composed by two copies of bestAgent, and one
copy of diverseAgent1. probBestAction is the probability of the best team
recommending the best action, rounded to 6 decimal places (using the function
round in Python). (15%)
3. According to Schapire (1990), each recursive application of the Boosting algorithm
reduces the error of a classifier from x to 3x2 ? 2x3 (see Figure 1 in the paper).
Based on this, write a Python function howManyIterations(x,epsilon), which
returns how many recursive iterations of the Boosting algorithm would be needed
to reduce the error of a base classifier from x to a value lower than epsilon. In
case the number of iterations cannot be calculated, then the function must return
?1. (10%)
4. What is the meaning of defun in the pseudo-code in Figure 2 of Schapire (1990)?
Why that is important for defining the Boosting algorithm? (5%)
2
5. Implement in Python the AdaBoost algorithm, following Freund and Schapire
(1996). You must write your own code, solutions from on-line resources are not
going to be accepted.
Write a class AdaBoost, with the following methods:
- AdaBoost(nItems=20), constructor. It initialises the hyper-parameter nItems,
which specifies how many randomly sampled items will be used for training.
- train(dataset, labels, D, T), which trains the AdaBoost system with T clas-
sifiers, given a dataset in dataset and the corresponding ground truth labels in
labels. D is the starting distribution over the examples, as in the AdaBoost paper.
At each iteration, please sample (with repetition) the number of items specified in
the constructor (nItems), in order to form the training set of each classifier.
dataset is represented as a list of lists, and labels is a list of labels. Similarly, D
is a list of probabilities, one for each item in the dataset.
Attention: differently from the original algorithm, you must re-train a Weak Clas-
sifier if the error obtained after training would be such that the probability of
correctly classified items would increase.
- classify(item), which classifies an item using the trained AdaBoost system.
For the Weak Classifier, you are given a Logistic Regression class (LogisticRegression),
which has the following interface:
- LogisticRegression(alpha = 0.01, threshold = 0.5, nEpochs = 500): Class
constructor. alpha is the learning rate, and threshold is used to define whether
the output of the logistic regression will be interpreted as a label 0 or 1. That is,
outputs lower than or equal to threshold will be defined as 0 when classifying
items. nEpochs defines the number of epochs that will be used during training.
Please use the default parameters when training each classifier.
- train(dataset, labels): Trains the Logistic Regression classifier, using the
dataset dataset and the corresponding labels labels.
- classify(item): Returns a predicted label for the item item, using the trained
Logistic Regression classifier.
This classifier is already given to you, see the file LogisticRegression.py attached.
It will be automatically added to the beginning of your code.
Additionally, for sampling you are given a function sample(p), which samples
a natural number from 0 to len(p) ? 1, following the probabilities specified in
the list of probabilities p. That is, for instance, if p = [0.5,0.3,0.2], then the
number 0 is sampled with 0.5 probability, 1 with 0.3 probability and 2 with 0.2
probability. The function is available in the sample.py file attached, and it will be
automatically added to the beginning of your code. (15%)
6. In Freund and Schapire (1996), how does the on-line allocation problem and pro-
posed solution (first part of the paper) relate to the development of the AdaBoost
algorithm (second part of the paper)? (5%)
7. Open BI has an ensemble system composed of n neural networks. They use one-
hot encoding in a classification problem, with l possible labels. That is, at train-
ing time, assuming for example 3 labels, the label 0 would be represented as
3
[1, 0, 0], label 1 as [0, 1, 0], and label 2 as [0, 0, 1], where each element
is the desired output of the corresponding output neuron. At inference time, how-
ever, each neuron returns a value between 0 and 1. These neural networks have a
softmax layer in the end, so their output can be seen as a probability distribution
function.
You were asked to interpret the output of the neurons as a ranking, and write a
function to aggregate the rankings using the Borda voting rule. Additionally,
all ties must be broken randomly. When deciding the winner of a tie, please use
the function choice from the random module.
Hence, you must implement bordaAggregation(opinions), where:
- opinions is a list of lists. Each inner list corresponds to a neural network,
and each element of that list corresponds to the output of an output neuron.
For example, opinions = [[0.4,0.5,0.1],[0.2,0.3,0.5]] represents a system
with two neural networks, where the first one assigns value 0.4 to label 0, 0.5 to
label 1, and 0.1 to label 2. Similarly, the second neural network assigns value 0.2
to label 0, 0.3 to label 1, and 0.5 to label 2. Note that in general we can have any
number of neural networks and labels/output neurons.
- The function returns ranking, where each element corresponds to the final rank-
ing position. For instance, ranking = [2,0,1] would mean that label 2 is in the
top position of the final aggregated ranking, label 0 in the middle position, and
label 1 in the last position. (10%)
8. Giggle wants to apply Stacked Generalisation to improve its predictions about cus-
tomer behaviour. Currently they are using a Logistic Regression class (LogisticRegression),
which was described previously. As before, this classifier is already given to you,
see the file LogisticRegression.py attached. It will be automatically added to the
beginning of your code.
You were hired to implement the class StackedGeneralisation for Giggle. Al-
though Stacked Generalisation can work with a diverse set of classifiers, we will
use only Logistic Regression as our base classifiers and as our aggregator, for their
initial tests.
We will use blocks of size 1. That is, the training set will be divided in n blocks of
1 item each. In order to match with their test cases, please generate the training
set of the aggregator following the original ordering of the training set, and train
the classifiers in order. That is, when training the base classifiers, train first the
first classifier, followed by training the second classifier, then the third classifier
and so on. Similarly, when creating the dataset for the aggregator, please generate
first the first row, then the second row, etc.
Hence, your task is to implement the StackedGeneralisation class with the
following methods:
- StackedGeneralisation(classifiers, aggregator): Class constructor. Re-
ceives a list classifiers of classifier objects, in order. That is, the first element
corresponds to the first classifier, the second to the second classifier and so on. Ad-
ditionally, receives a classifier object aggregator, which will learn the aggregation
rule.
- train(dataset, labels): Trains the Stacked Generalisation system, given a
dataset in dataset, and the corresponding labels in labels. The dataset will be
4
represented as a list of lists, where each inner list is an item, and each element of
the inner lists are features of the item.
- classify(item): Classify the item in item using the trained StackedGeneralisation
system. It returns a label (0 or 1). (10%)
9. Consider the team/ensemble success prediction system described in Marcolino,
Lakshminarayanan et al. (2016). Let’s assume that we have an ensemble of 3
classifiers (c0, c1, c2), working across batches of 4 items, in a problem with 3 possible
labels (0, 1 or 2). The final decision of the ensemble is given by the plurality voting
rule.
For each batch of items, we store the vote of each agent for each item, the fi-
nal classification and the corresponding ground truth label, in a list of lists.
Using this data, and the Logistic Regression class provided, create a classifier
to predict the success of the ensemble. You must implement two functions:
predictionFeatureVector(batch) and successPrediction(batches).
predictionFeatureVector(batch) is an auxiliary function that returns the fea-
ture vector of the prediction methodology, given the stored information for one
batch of items. In detail:
- batch is a list of lists, where each list corresponds to one item within the
batch. For each item, we first list the votes of each classifier, then the deci-
sion taken by the team, and finally the ground truth label. For example, batch =
[[0, 1, 0, 0, 1], [1, 1, 0, 1, 1], [0, 1, 2, 0, 0], [0, 0, 0, 0, 0]] shows a case where the votes for
each item were, respectively: [0, 1, 0], [1, 1, 0], [0, 1, 2], [0, 0, 0]. Additionally, the de-
cision for each item was: 0, 1, 0, 0, respectively. Finally, the ground truth labels
were 1, 1, 0, 0.
- The function returns a list featureVector, where each element corresponds to a
subset of the classifiers. We will use the following ordering across possible subsets:
{c0}, {c1}, {c2}, {c0, c1}, {c0, c2}, {c1, c2}. Hence, featureVector = [1/4,0,0,1/4,1/2,0]
would mean that in this batch classifier {c0} was responsible for 1/4 of the final
team decisions, {c0, c1} for 1/4 of the decisions, and {c0, c2} for 1/2 of the decisions.
Concerning successPrediction(batches):
- batches is a 3D Python list (list of lists of lists), containing a list of batches, as de-
scribed above. For example, batches = [[[0, 1, 0, 0, 1], [1, 1, 0, 1, 1], [0, 1, 2, 0, 0], [0, 0, 0, 0, 0]],
[[0,0,0,0,0],[1,1,2,1,2],[0,1,1,1,1],[2,2,1,2,2]]] contains information
about two batches of items. The first batch is [[0, 1, 0, 0, 1], [1, 1, 0, 1, 1], [0, 1, 2, 0, 0], [0, 0, 0, 0, 0]]
as described above, and the second batch is [[0, 0, 0, 0, 0], [1, 1, 2, 1, 2], [0, 1, 1, 1, 1], [2, 2, 1, 2, 2]].
- The function returns an object of type Logistic Regression, with the trained
classifier. Use default learning rate, threshold for classification, and number of
epochs when training in the Logistic Regression.
The code for the Logistic Regression classifier will be automatically added to the
beginning of your code. (15%)
10. Consider we have a game between two agents A and B, with two possible actions,
as follows:
A/B a0 a1
a0 r0,0, r
′
0,0 r0,1, r
′
0,1
a1 r1,0, r
′
1,0 r1,1, r
′
1,1
5
Reward ri,j is the reward the Row player (agent A) receives when it takes action
ai and Column player (agent B) takes action aj . Similarly, r
′
i,j corresponds to the
reward for the column player (agent B) when A takes ai and B takes aj . We will
represent that table in Python as a list of lists, where each inner list corresponds
to a row, as follows: [[(r0,0, r
′
0,0), (r0,1, r
′
0,1)], [(r1,0, r
′
1,0), (r1,1, r
′
1,1)]].
(a) Write in Python a function nashEquilibria(rewards), which returns all
the pure strategy Nash Equilibria in the game. rewards is a list of lists with
the rewards for each player, as defined above. The function returns a list of
tuples, where each tuple is a pair of actions for each player if that pair is a
Nash Equilibria of the game. For instance, [(0, 0), (1, 1)] means that there
are two Nash Equilibria in the game: when A takes action a0 and B takes
action a0, and when A takes action a1 and B takes action a1. If the game
has no pure strategy Nash Equilibria, then it returns an empty list: []. (5%)
(b) Write in Python a function mixedEquilibria(rewards), which returns a
mixed strategy Nash Equilibria in the game defined by the rewards in rewards.
The function returns a tuple (x, y) where x is the probability of the A player
playing a0 and y is the probability of the B player playing a0. If there is no
mixed strategy Equilibria, then it returns an empty tuple: (). (5%)