[Solved] CS760 Homewok 7-Background Test

$25

File Name: CS760_Homewok_7-Background_Test.zip
File Size: 292.02 KB

SKU: [Solved] CS760 Homewok 7-Background Test Category: Tag:
5/5 - (1 vote)

Directed Graphical Model

Consider the directed graphical model (aka Bayesian network) in Figure ??.

Figure 1: A Bayesian Network example.

Compute P(B = t | E = f,J = t,M = t) and P(B = t | E = t,J = t,M = t). These are the conditional probabilities of a burglar in your house (yikes!) when both of your neighbors John and Mary call you and say they hear an alarm in your house, but without or with an earthquake also going on in that area (what a busy day), respectively.

2 Chow-Liu Algorithm

Suppose we wish to construct a directed graphical model for 3 features X, Y , and Z using the Chow-Liu algorithm. We are given data from 100 independent experiments where each feature is binary and takes value T or F. Below is a table summarizing the observations of the experiment:

X Y Z Count

  1. Compute the mutual information I(X,Y ) based on the frequencies observed in the data.
  2. Compute the mutual information I(X,Z) based on the frequencies observed in the data.
  3. Compute the mutual information I(Z,Y ) based on the frequencies observed in the data.
  4. Which undirected edges will be selected by the Chow-Liu algorithm as the maximum spanning tree?
  5. Root your tree at node X, assign directions to the selected edges.

3 Kernel SVM

Consider the following kernel function defined over z,z0 Z:

0 (1 if z = z0, k(z,z ) =

0 otherwise.

  1. Prove that for any integer m > 0, any z1,,zm Z, the m m kernel matrix K = [Kij] is positive semi-definite, where Kij = k(zi,zj) for i,j = 1m. (Let us assume that for i 6= j, we have zi 6= zj.) Hint: An m m matrix K is positive semi-definite if v Rm,v>Kv 0.
  2. Given a training set (z1,y1),,(zn,yn) with binary labels, the dual SVM problem with the above kernel k will have parameters 1,,n,b (Assume that for i 6= j, we have zi 6= zj.) The predictor for input z takes the form

Recall the label prediction is sgn(f(z)). Prove that there exists 1,,n,b such that f correctly separates the training set. In other words, k induces a feature space rich enough such that in it any training set can be linearly separated.

  1. How does that f predict input z that is not in the training set?

Comment: One useful property of kernel functions is that the input space Z does not need to be a vector space; in other words, z does not need to be a feature vector. For all we know, Z can be turkeys in the world. As long as we can compute k(z,z0), kernel SVM works on turkeys.

4 Extra Credit: Kernel functions over discrete space

Kernel functions can be defined over objects as diverse as graphs, sets, strings, and text documents. Consider, for instance, a fixed set D and define a nonvectorial space consisting of all possible subsets of this set D. If A1 and A2 are two such subsets then one simple choice of kernel would be

k(A1,A2) = 2|A1A2|

where A1 A2 denotes the intersection of sets A1 and A2, and |A| denotes the size of A. Show that this is a valid kernel function, by showing that it corresponds to an inner product in a feature space. Solution goes here.

5 Extra Credit: Support Vector Machines

Given data {(xi,yi),1 i n}, the (hard margin) SVM objective is

s.t. yi(w>xi + b) 1(i).

The dual is

s.t. i 0(i), Xiyi = 0.

i=1

Suppose the optimal solution for the dual is, and the optimal solution for the primal is

(w,b). Show that the margin

satisfies

.

Hint: use the KKT conditions. Solution goes here.

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart
[Solved] CS760 Homewok 7-Background Test
$25