1.      Search (25 marks)

i.     Explain briefly in the context of problem solving that involves searching in a discrete state space the concepts on search space and search tree. K

[5 marks]

Answer:

The search space is the implicit tree generated from the initial state and the operators.  [2 marks]

The search tree is the explicit tree generated from a search strategy, which defines the order of state expansion.

[3 marks]

ii.    Consider the following search problem represented by the graph (Figure 1), where S and G are the start and goal states, respectively. The costs associated to arcs connecting the states (vertices) are given in the graph. The following Table 1 lists out three different heuristics (h1, h2, h3),each being a set of heuristic values from the current state to the goal state G. A, C

Figure 1

Table 1

a) Greedy and A* search are two different informed search methods. Explain briefly how A* search is different from greedy search.

[5 marks]

Answer:

The difference is mainly with the use of the evaluation function. Greedy search uses only the true cost so far to reach a state n starting from the initial state,  g(n). A* uses (summing) both g(n) and the estimated cost to the goal state     from the current state n, h(n).

[5 marks]

b) Construct the search tree associated to an A* search, where the evaluation function at state n is f(n), which is a simple sum of the total cost from S to the current state g(n) and the heuristic value from the current state to G given by h1(n). After that, write out the solution path and the total true cost.

[6 marks]

Answer:

S-B-C-G at cost of 6 units.

c)  Repeat the question above, this time using h3(n).

Answer:

[4 marks]

[6 marks]

[4 marks]

S-B-D-G at cost of 8 units.

[2 marks]

d) Given your results in (b)-(c), explain briefly if different solutions can be found for using different heuristics, and if so, why.

[5 marks]

Answer:

Different solutions can be obtained. With h3 a less than optimal solution is found. [2 marks]

Heuristics such as h3 are not admisibble (e.g. overestimate the cost to reach the goal).

[3 marks]

2.      Game Playing and Coevolution (25 marks)

iii.     Describe a typical coevolutionary system as a generate-and-test procedure. K, C

[10 marks]

Answer:

As a general generate-and-test procedure, a coevolutionary system involves

1. Initialize a population of agents (candidate solutions).

2.  Evaluate fitness through agent interactions (e.g. pairwise comparisons).

3. Select parents from the populations based on fitness.

4.  Generate offspring from parents in (3).

5.  Repeat steps (2-4) until some termination criterion reached.

[2 marks each point]

iv.    Formally explain how Chebyshev’s bounds are used for evaluation of performance of strategies produced (evolved) through coevolution (full marks for complete              mathematrical description). K, C

[10 marks]

Answer:

Consider a two-player, win-lose (0-1) game, having a set S of M pure strategies, {1,2,3,…,M}. The true generalization performance of a strategy i is

 =   ()  () 1

where PS(j) represents the random selection ofj ∈ S as test strategy with some probability, Gi(j) is the outcome for i for a game between i,j ∈ S.

[4 marks]

This can be estimated using a random sample SN of N test strategies drawn iid from S with probability PS

 () =          ()

 ∈ 

[3 marks] in which case, one can then apply Chebyshev’s Theorem to obtain the following bounds

   −    ≥  ≤ 4 2

for any positive  and R = 1.

[3 marks]

v.    Consider the case of a game with a win-lose (1-0) outcome. Using an i.i.d. random sample of 25000 test strategies to estimate the generalization performance of a strategy, what statistical claim can you make for a given precision of  = 0.1? If the variance associated with the game outcomes for the strategy is one-tenth of the worst case, what would be the improved statistical claim you can make?

[5 marks]

Answer:

Greedy    search    returns    the    path    a-c-f-i-l-m    with    a    total    distance    of 200+160+165+250+60=835 km. A* search returns the path a-c-f-i-l-m with a total distance of 200+160+165+250+60=835 km. Both returns the same total distance

travelled.

[5 marks]

2.      Artificial Neural Networks and Machine Learning (25 marks)

i.    What are the three activation functions that are used in an artificial neuron? For each activation function, mathematically formulate it and also provide a general graphical  representation. K

[12 marks]

Answer:

step () =             

sign() =                 

1

sigmoid() =                   

[2 marks for each point]

In the following figure, x = in  is the weighted sum of activation values ofjs (inputs) to unit i.

Sample diagram

[2 marks for each figure]

ii.    Consider two-dimensional classification problems that are not linearly separable (XOR- like). Explain with the aid of conceptual diagrams two ways in which classifiers such as neural networks solve these problems. C

[10 marks]

Answer:

The input-output response separating the two classes of the 2D feature space can be illustrated from the clusters of data points in the figure.