ARTIFICIAL INTELLIGENCE I FALL 2019 WRITTEN ASSIGNMENT 5 (100 POINTS)ASSIGNED: 10/22/2019 DUE: 11/5/201
代写AI作业 This assignment constitutes 5% of the course grade. You must work on it individually and are required to submit a PDF report.
This assignment constitutes 5% of the course grade. You must work on it individually and are required to submit a PDF report.
Question 1 (40 points) 代写AI作业
Consider a hidden Markov model (HMM) with hidden states X1:T and observed states or evidence variables E1:T . Consider the problem of finding the most likely sequence of states in the HMM, i.e., the sequence X1:T which maximizes P (X1:T | E1:T ).
(a)(20points) Describe an algorithm to find the most likely sequence X1:T given an observation sequence E1:T . You have to clearly describe the key variables, equation(s) and computation involved, and discuss the time complexity of the algorithm. You do not have to prove correctness of the algorithm.
(b)(20 points) Consider the following alternative approach to the above problem. We find P (Xt| E1:t) based on filtering, and pick the value of Xt∗ which maximizes the distribution P (Xt | E1:t). We repeat the process for all t, and concatenate the values Xt∗ to come up with a sequence X1∗:T . Will this alternative approach solve the problem of finding the most likely sequence of states? If yes, clearly explain If not, clearly explain why not or give a counterexample which illustrates that it will not solve the problem.
Question 2 (30 points) 代写AI作业
The binary XOR function has two boolean inputs [x1, x2] and gives an output of y = T if an odd number of inputs is T , and F otherwise. The ternary XOR function has three boolean inputs [x1, x2, x3] and gives an output of y = T if an odd number of inputs is T , and F otherwise. We consider building classifiers with F represented as -1, and T represented as 1, e.g., ([−1, 1], 1) or ([−1, −1], −1) are valid inputs ([x1, x2], y) for learning the binary XOR function.
(a)(15 points) While the binary XOR problem is not linearly separable in the original space [x1, x2], one can construct a mapping φ2([x1, x2]) to a space where the binary XOR problem is linearly separable1. Show that the mapping φ2([x1, x2]) = [x1, x1x2] makes the problem linearly separable, i.e., one can find suitable weights (w1, w2) such that y = sign(w1x1+ w2x1x2). 代写AI作业
(b)(15 points) The ternary XOR problem is not linearly separable in the original space [x1, x2, x3]. Can youconstruct a mapping φ3([x1, x2, x3]) to a space2 where the ternary XOR problem is linearly separable? If yes, give an example of such a mapping φ3. If no, clearly explain why such a mapping is not possible.
1Such mappings can be constructed in the context of kernel methods.
2The dimensionality of the mapped space can be higher, same, or lower than the original space [x1, x2, x3]. For the binary XOR example in (a), the mapped space has the same dimensionality as the original space [x1, x2].
Question 3 (30 points)
Consider a neural network with linear activation function g(·), i.e., 
(a)(15 points) Assume that the network has one hidden layer. For a given assignment to the weights W , write down the value of the units in the output layer as a function of W and the input layer I, without any explicit mention of the output of the hidden layer. Show that there is a network with no hidden units that computes the same function. 代写AI作业
(b)(10points) Repeat the above analysis in (a) above for a network with any fixed number of hidden layers.
(c)(5 points) Based on the relationship between the input and the output in such networks, what can you conclude about linear activationfunctions?
