Machine_Learning_I_Exam_WS_14_15

The Bayes error for classification is:

Independent Component Analysis can be achieved by:

The K-means algorithm:

A biased estimator is sometimes used to:

Which is False? The Restricted Boltzmann machine is:

Sketch a two-dimensional two-class supervised dataset that Fishers linear discriminant and the linear hard-margin SVM would learn separating bounderies with different directions. Your example must be stereotyping for the two classification techniques.

Sketch a two-dimensional unsupervised dataset for which K-means (K=3) may get stuck at a local optimum. In your drawing show (using square markers) the position of the centroids for the local minimum and (with circels) the position of the global minimum. Your example must be stereotyping in order to show the difference between the local and global minimum.

Show that if $k_1$ and $k_2$ are PSD kernels, then $k_3 = \alpha k_1 + \beta k_2$ with $\alpha, \beta \ge 0$ is also a PSD kernel.

Give an example showing that the positive semi-definiteness is not guaranteed if $\alpha < 0$ or $\beta < 0$

A feature map associated to a kernel $k$ must satisfy: $\langle \phi(x_i), \phi(x_j) \rangle = k(x_i, x_j) \forall i, j \in X$ Find the feature map of $k_3 = \alpha k_1 + \beta k_2$ and show that it fulfills the equation above.

Write down the Lagrangian function associated to this constrained optimization problem.

Show using the Lagrangian method that the optimal probability distribution is uniform with $p(i) = 0.1$ for all $i$.

Explain briefly why the same Lagrange method cannot be used to find probability distribution with minimum entropy

Show that the optimization problem can be rewritten as:
$\min_W w^T X^T X w - 2y^T X w$ subject to $w_i \leq 1$ and $w_i \geq -1$

You have at your disposal a quadratic solver quadprog(Q,1,A,b) that is solving
$\min_V v^T Q v + 1^T v$ subject to $Av \leq b$
Write down the code that builds the numpy array Q,1,A,b from the data X and y.