代写SCC462、代写Python设计程序

日期：2023-02-27 08:38

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%)

6