xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-SCC462

时间：2021-02-19

SCC462 – Distributed Artificial Intelligence

Leandro Soriano Marcolino

Midterm Assignment

Deadline: 19/02/2021, 4pm. 25 points in total.

Instructions

• Please reply all questions below.

• If you make any additional assumptions, please state that clearly.

• You are allowed to use external resources (papers, books, Internet, etc), but you

have to provide a reference if you use anything beyond the papers indicated in

class.

• You are allowed to discuss the questions with your class-mates. Any discussion

must be reported in a brief acknowledgement after the corresponding

question that was discussed.

• You are not allowed to copy the answers of a friend/class-mate. This is

an individual exam, so you must work on your own replies.

• An unreported discussion or a reply that was directly copied will lead

to a 0 in the corresponding question.

• In all questions of this assignment, X corresponds to the last digit of your student

ID, or 1 if your last digit is 0. That is, if your student ID is 12345678, you have

to assume X = 8. If your student ID is 22345670, you have to assume X = 1.

We will use the symbol % to indicate mod. That is, for example: 3%2 = 1, and

4%2 = 0.

When we write 0.X we are concatenating “0.” with the digit X . For example, if

X = 3, then 0.X = 0.3.

• Please always show your calculations. Note that the final result depends on

X . You may lose marks in a question if you do not show your calculations, even

if the final result is correct.

1

0. What is your Student ID? What is the value of X ?

1. Write a rejection review of Marcolino, Passos et al (2016). That is, you must

summarise the paper, explain why it is not yet suitable for publication, and give

suggestions to the authors for further improvement. (10%)

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 given different economic scenarios. These agents, how-

ever, 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.

“Stuck with Stocks” wants to get ready for a forthcoming economic scenario. Based

on simulations, they estimate the probabilities of the agents as follows:

Action 1 Action 2 Action 3

Agent 1 0.51 0.39 0.1

Agent 2 0.Y 0.2 1 - 0.2 - 0.Y

Agent 3 0.3 0.Y 1 - 0.3 - 0.Y

Where Y = X%6. Action 1 is the best action in these economic scenarios, and

Agent 1 is considered to be the “best agent”.

(a) Are the “necessary conditions” for a diverse team (composed by Agents 1,

2, and 3) to outperform a uniform team stated in Marcolino et al. (2013)

satisfied in this economic scenario? Why? (5%)

(b) What is the probability that a team composed by 3 copies of Agent 1 recom-

mends the best action (Action 1) for this economic scenario? And a diverse

team of 3 agents, composed by one copy of each agent? Which one of these

two teams you would recommend for “Stuck with Stocks”? (You can use a

calculator, but please show your calculations, e.g. 0.5∗0.3+0.7∗0.4...) (10%)

3. Consider the Boosting system with two levels of recursion shown below. For this

exercise, you must consider the version of Boosting described in Schapire (1990),

not the one described in Polikar (2012).

M1 M2 M3

M1.1 M1.2 M1.3 M2.1 M2.2 M2.3 M3.1 M3.2 M3.3

2

M1, M2, and M3 are the meta-classifiers; and the others are the base classi-

fiers (“Weak Learner”). Let’s consider that the original training data is: φ1 =

{(A, 1), (B, 1), (C, 0), (D, 1), (E, 1), (F, 1), (G, 0), (H, 1), (I, 0), (J, 0), (K, 0), (L, 1),

(M, 0), (N, 0), (O, 0), (P, 1), (Q, 1), (R, 0)}. The first element of a tuple is the item,

and the second element of a tuple is the item’s true label.

After training the first meta-classifier M1, another training data is used for train-

ingM2. For example: φ2 = {(A, 1), (C, 0), (C, 0), (E, 1), (K, 0), (O, 0), (P, 1), (P, 1),

(Q, 1), (R, 0)}.

• How was the dataset φ2 formed? Show a concrete example of M1’s out-

put across the training data that could lead to the training set φ2 in your

explanation. (5%)

• Let φ2.3 be the dataset used for training M2.3. How is that dataset formed?

Show which items form the oracle EX, which would be used when defining

the oracle EX3 for M2.3 in your explanation. (5%)

4. Based on Schapire (1990), why a concept is strongly learnable if and only if it is

weakly learnable? Please explain using your own words. (5%)

5. Which variation is proposed by Schapire (1990) in order to make the Boosting

algorithm run faster than its original version? Why is it faster? (5%)

6. In this exercise we will simulate by hand the result of training and executing an

AdaBoost system. When solving this exercise, you can simulate “in your head”

the result of randomness. I.e., if you have to pick 3 items with uniform probability,

you can just select any 3 items. If some item has a higher probability, you should

have a higher tendency of selecting it. Likewise, if you train a weak classifier with a

set of items, you can state which subset the weak classifier will correctly identify,

and which subset the weak classifier will commit mistakes. However, you must

make reasonable assumptions, i.e., the weak classifier is not able to learn the full

set of items, it is only slightly better than random guessing. (To be clear: you

are not being asked to implement any algorithm in the computer, but

just to “simulate” by hand the algorithms!)

Let’s assume the following training set, where the first element of a tuple is the

item, and the second element of a tuple is the item’s label.

(A, 1), (B,X%2), (C, 0), (D, 1), (E, 0), (F, (X + 1)%2)

Simulate AdaBoost with 3 classifiers, including training the system and the final

classification of 1 item. You must follow the equations in Freund and Schapire

(1996). Please clearly show all the steps of the algorithm, and your calculations.

(10%)

7. 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)? Why that was a significant advancement in

relation to what was done before? (5%)

8. Let’s consider now the ensemble system algorithm called Stacked Generalisation:

• Write a pseudo-code for the Stacked Generalisation meta-classifier. (5%)

3

• Consider that we have 3 classifiers available, and we are going to train and

test a Stacked Generalisation meta-classifier. We will assume the following

dataset:

(A, 0), (B,X%2), (C, 0), (D, 1), (E, 1), (F, (X + 1)%2), (G, 1), (H,X%2), (I, 0)

Items A,B,C,D,E, F are going to be used for training the meta-classifier,

and items G,H, I will be used for testing the meta-classifier. Show step-by-

step the full training and testing procedure. When training the meta-

classifier, use blocks of size 1. That is, the training set will be

divided in 6 blocks of 1 item each. Similarly to Question 6, you should

“simulate” the output of the individual classifiers. (10%)

9. Consider a set of 4 Neural Networks, using one-hot encoding in a classification

problem with 4 possible labels. Assume that when classifying an item, we obtained

the following result:

Output

Label 0 0.X

Label 1 0.3

Label 2 0.Y

Label 3 0.4

(a) Neural Network 1

Output

Label 0 0.Y

Label 1 0.4

Label 2 0.5

Label 3 0.25

(b) Neural Network 2

Output

Label 0 0.7

Label 1 0.05

Label 2 0.6

Label 3 0.Z

(c) Neural Network 3

Output

Label 0 0.1

Label 1 0.Z

Label 2 0.3

Label 3 0.5

(d) Neural Network 4

Assume Y = X%6, and Z = Y + 1.

We will interpret the output of the neurons as a ranking, and aggregate the rank-

ings using the Borda voting rule. What would be the final aggregated ranking?

Please show your calculations (5%)

10. 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. The final decision of the

ensemble is given by the plurality voting rule. Let’s assume the following training

process for the team performance prediction, where we show the classifiers vote

across four batches, and the true label of the item they tried to classify:

4

c0 c1 c2 True Label

0 0 1 X%2

1 1 1 0

0 0 0 1

1 1 0 1

(a) Batch 1

c0 c1 c2 True Label

1 0 1 0

0 1 1 1

0 1 Y%2 1

1 1 0 0

(b) Batch 2

c0 c1 c2 True Label

1 1 1 1

1 0 0 0

0 X%2 1 1

1 0 0 Y%2

(c) Batch 3

c0 c1 c2 True Label

1 1 0 X%2

1 0 1 1

0 1 X%2 1

0 1 1 0

(d) Batch 4

We assume that Y = X + 1.

Show one full training iteration of the team prediction methodology using stochas-

tic gradient descent. That is, show one update of the weights of the team predic-

tion classifier for each batch. Assume that weights start as 0.1 (βi = 0.1), and

the learning rate is 0.01 (α = 0.01). As usual in stochastic gradient descent, you

can process the batches in any order. Note: Recall that the stochastic gradient

descent algorithm was described in the Coursework 10 of SCC461.(10%)

11. Consider the following game between two agents A and B. A is the column player

(with actions A1 and A2), and B is the row player (with actions B1 and B2). The

payoffs are shown below; the first number is for agent B and the second for agent

A.

A1 A2

B1 X , 6 0, 4

B2 4, 7 5,X ∗ 2

(a) What is the pure strategy Nash equilibrium of this game? Why? (2%)

(b) Is there a mixed strategy Nash equilibrium for this game where agent A takes

action A1 with probability p, and agent B takes action B1 with probability

q? What are the values of p and q? (0 < p < 1, 0 < q < 1) (3%)

(c) Consider now the payoffs below:

A1 A2

B1 5, 2 1, 5

B2 1000, 1 −20, 1.1

• If this were a Stackelberg game1, where the row player (B) is allowed

to commit to a pure strategy (not to a mixed strategy), which strategy

should it commit to? Why? (1%)

• Can the row player perform even better by committing to a mixed strat-

egy? Why? (4%)

1We will discuss Stackelberg games in Week 16.

5

学霸联盟

Leandro Soriano Marcolino

Midterm Assignment

Deadline: 19/02/2021, 4pm. 25 points in total.

Instructions

• Please reply all questions below.

• If you make any additional assumptions, please state that clearly.

• You are allowed to use external resources (papers, books, Internet, etc), but you

have to provide a reference if you use anything beyond the papers indicated in

class.

• You are allowed to discuss the questions with your class-mates. Any discussion

must be reported in a brief acknowledgement after the corresponding

question that was discussed.

• You are not allowed to copy the answers of a friend/class-mate. This is

an individual exam, so you must work on your own replies.

• An unreported discussion or a reply that was directly copied will lead

to a 0 in the corresponding question.

• In all questions of this assignment, X corresponds to the last digit of your student

ID, or 1 if your last digit is 0. That is, if your student ID is 12345678, you have

to assume X = 8. If your student ID is 22345670, you have to assume X = 1.

We will use the symbol % to indicate mod. That is, for example: 3%2 = 1, and

4%2 = 0.

When we write 0.X we are concatenating “0.” with the digit X . For example, if

X = 3, then 0.X = 0.3.

• Please always show your calculations. Note that the final result depends on

X . You may lose marks in a question if you do not show your calculations, even

if the final result is correct.

1

0. What is your Student ID? What is the value of X ?

1. Write a rejection review of Marcolino, Passos et al (2016). That is, you must

summarise the paper, explain why it is not yet suitable for publication, and give

suggestions to the authors for further improvement. (10%)

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 given different economic scenarios. These agents, how-

ever, 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.

“Stuck with Stocks” wants to get ready for a forthcoming economic scenario. Based

on simulations, they estimate the probabilities of the agents as follows:

Action 1 Action 2 Action 3

Agent 1 0.51 0.39 0.1

Agent 2 0.Y 0.2 1 - 0.2 - 0.Y

Agent 3 0.3 0.Y 1 - 0.3 - 0.Y

Where Y = X%6. Action 1 is the best action in these economic scenarios, and

Agent 1 is considered to be the “best agent”.

(a) Are the “necessary conditions” for a diverse team (composed by Agents 1,

2, and 3) to outperform a uniform team stated in Marcolino et al. (2013)

satisfied in this economic scenario? Why? (5%)

(b) What is the probability that a team composed by 3 copies of Agent 1 recom-

mends the best action (Action 1) for this economic scenario? And a diverse

team of 3 agents, composed by one copy of each agent? Which one of these

two teams you would recommend for “Stuck with Stocks”? (You can use a

calculator, but please show your calculations, e.g. 0.5∗0.3+0.7∗0.4...) (10%)

3. Consider the Boosting system with two levels of recursion shown below. For this

exercise, you must consider the version of Boosting described in Schapire (1990),

not the one described in Polikar (2012).

M1 M2 M3

M1.1 M1.2 M1.3 M2.1 M2.2 M2.3 M3.1 M3.2 M3.3

2

M1, M2, and M3 are the meta-classifiers; and the others are the base classi-

fiers (“Weak Learner”). Let’s consider that the original training data is: φ1 =

{(A, 1), (B, 1), (C, 0), (D, 1), (E, 1), (F, 1), (G, 0), (H, 1), (I, 0), (J, 0), (K, 0), (L, 1),

(M, 0), (N, 0), (O, 0), (P, 1), (Q, 1), (R, 0)}. The first element of a tuple is the item,

and the second element of a tuple is the item’s true label.

After training the first meta-classifier M1, another training data is used for train-

ingM2. For example: φ2 = {(A, 1), (C, 0), (C, 0), (E, 1), (K, 0), (O, 0), (P, 1), (P, 1),

(Q, 1), (R, 0)}.

• How was the dataset φ2 formed? Show a concrete example of M1’s out-

put across the training data that could lead to the training set φ2 in your

explanation. (5%)

• Let φ2.3 be the dataset used for training M2.3. How is that dataset formed?

Show which items form the oracle EX, which would be used when defining

the oracle EX3 for M2.3 in your explanation. (5%)

4. Based on Schapire (1990), why a concept is strongly learnable if and only if it is

weakly learnable? Please explain using your own words. (5%)

5. Which variation is proposed by Schapire (1990) in order to make the Boosting

algorithm run faster than its original version? Why is it faster? (5%)

6. In this exercise we will simulate by hand the result of training and executing an

AdaBoost system. When solving this exercise, you can simulate “in your head”

the result of randomness. I.e., if you have to pick 3 items with uniform probability,

you can just select any 3 items. If some item has a higher probability, you should

have a higher tendency of selecting it. Likewise, if you train a weak classifier with a

set of items, you can state which subset the weak classifier will correctly identify,

and which subset the weak classifier will commit mistakes. However, you must

make reasonable assumptions, i.e., the weak classifier is not able to learn the full

set of items, it is only slightly better than random guessing. (To be clear: you

are not being asked to implement any algorithm in the computer, but

just to “simulate” by hand the algorithms!)

Let’s assume the following training set, where the first element of a tuple is the

item, and the second element of a tuple is the item’s label.

(A, 1), (B,X%2), (C, 0), (D, 1), (E, 0), (F, (X + 1)%2)

Simulate AdaBoost with 3 classifiers, including training the system and the final

classification of 1 item. You must follow the equations in Freund and Schapire

(1996). Please clearly show all the steps of the algorithm, and your calculations.

(10%)

7. 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)? Why that was a significant advancement in

relation to what was done before? (5%)

8. Let’s consider now the ensemble system algorithm called Stacked Generalisation:

• Write a pseudo-code for the Stacked Generalisation meta-classifier. (5%)

3

• Consider that we have 3 classifiers available, and we are going to train and

test a Stacked Generalisation meta-classifier. We will assume the following

dataset:

(A, 0), (B,X%2), (C, 0), (D, 1), (E, 1), (F, (X + 1)%2), (G, 1), (H,X%2), (I, 0)

Items A,B,C,D,E, F are going to be used for training the meta-classifier,

and items G,H, I will be used for testing the meta-classifier. Show step-by-

step the full training and testing procedure. When training the meta-

classifier, use blocks of size 1. That is, the training set will be

divided in 6 blocks of 1 item each. Similarly to Question 6, you should

“simulate” the output of the individual classifiers. (10%)

9. Consider a set of 4 Neural Networks, using one-hot encoding in a classification

problem with 4 possible labels. Assume that when classifying an item, we obtained

the following result:

Output

Label 0 0.X

Label 1 0.3

Label 2 0.Y

Label 3 0.4

(a) Neural Network 1

Output

Label 0 0.Y

Label 1 0.4

Label 2 0.5

Label 3 0.25

(b) Neural Network 2

Output

Label 0 0.7

Label 1 0.05

Label 2 0.6

Label 3 0.Z

(c) Neural Network 3

Output

Label 0 0.1

Label 1 0.Z

Label 2 0.3

Label 3 0.5

(d) Neural Network 4

Assume Y = X%6, and Z = Y + 1.

We will interpret the output of the neurons as a ranking, and aggregate the rank-

ings using the Borda voting rule. What would be the final aggregated ranking?

Please show your calculations (5%)

10. 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. The final decision of the

ensemble is given by the plurality voting rule. Let’s assume the following training

process for the team performance prediction, where we show the classifiers vote

across four batches, and the true label of the item they tried to classify:

4

c0 c1 c2 True Label

0 0 1 X%2

1 1 1 0

0 0 0 1

1 1 0 1

(a) Batch 1

c0 c1 c2 True Label

1 0 1 0

0 1 1 1

0 1 Y%2 1

1 1 0 0

(b) Batch 2

c0 c1 c2 True Label

1 1 1 1

1 0 0 0

0 X%2 1 1

1 0 0 Y%2

(c) Batch 3

c0 c1 c2 True Label

1 1 0 X%2

1 0 1 1

0 1 X%2 1

0 1 1 0

(d) Batch 4

We assume that Y = X + 1.

Show one full training iteration of the team prediction methodology using stochas-

tic gradient descent. That is, show one update of the weights of the team predic-

tion classifier for each batch. Assume that weights start as 0.1 (βi = 0.1), and

the learning rate is 0.01 (α = 0.01). As usual in stochastic gradient descent, you

can process the batches in any order. Note: Recall that the stochastic gradient

descent algorithm was described in the Coursework 10 of SCC461.(10%)

11. Consider the following game between two agents A and B. A is the column player

(with actions A1 and A2), and B is the row player (with actions B1 and B2). The

payoffs are shown below; the first number is for agent B and the second for agent

A.

A1 A2

B1 X , 6 0, 4

B2 4, 7 5,X ∗ 2

(a) What is the pure strategy Nash equilibrium of this game? Why? (2%)

(b) Is there a mixed strategy Nash equilibrium for this game where agent A takes

action A1 with probability p, and agent B takes action B1 with probability

q? What are the values of p and q? (0 < p < 1, 0 < q < 1) (3%)

(c) Consider now the payoffs below:

A1 A2

B1 5, 2 1, 5

B2 1000, 1 −20, 1.1

• If this were a Stackelberg game1, where the row player (B) is allowed

to commit to a pure strategy (not to a mixed strategy), which strategy

should it commit to? Why? (1%)

• Can the row player perform even better by committing to a mixed strat-

egy? Why? (4%)

1We will discuss Stackelberg games in Week 16.

5

学霸联盟