\documentclass[a4paper,12pt]{article}
\usepackage[top=1.5cm, bottom=1.5cm, left=2.5cm, right=2.5cm]{geometry}

\begin{document}
\thispagestyle{empty}
\section*{\bf Recognition \hfill January 10,  2013}
\section*{\bf Name: }

\begin{enumerate}
\item 
 Objects from two classes $k \in \{1,2\}$ are classified given a single
 observation, a non-negative real number $x$.  Conditional probability
 densities $p(x|k)$ are:
 $p(x|1)=1, x \in (0,1)$ and 0 elsewhere, $p(x|2)=\exp(-x)$.
 Find the decision $d$ optimal for the 
 \begin{enumerate}
   \item (2 points) the minmax formulation of the recognition task. \\
   \item (2 points) the Neyman-Pearson formulation of the recognition task. 
         The false negative rate (probability of misclassifying 
         a dangerous object) is required to be below 0.1 (10\%). 
         Class 1 is considered dangerous.
  \item (2 points) the Bayesian recognition task, 
        for equal a priori probabilities and
        the 0-1 loss matrix (i.e. for the minimisation of the probability of 
        incorrect decision)
  \item (2 points) the Bayesian recognition task, 
       for equal a priori probabilities and
       the loss matrix $W$ of the form (row: true class, column: decision)
        $$W= \left[ \begin{array}{cc}0 & 1  \\
                                     2 & 0  \\
                                      \end{array} \right]\:.$$
  \item (2 points) the Bayesian recognition task with a reject option ("don't know"
       decision), for equal a priori probabilities and
       the loss matrix $W$ of the form (row: true class, column:
       decision): 
    $$W= \left[ \begin{array}{ccc}0 & 1 & \varepsilon \\
                                 1 & 0 & \varepsilon \\
                                     \end{array} \right]\:.$$
         Consider $\varepsilon=0.1$ and $\varepsilon=0.2$.
     Bonus (1 point): consider $\varepsilon$ a free parameter and
     express the decision as its function.
  \end{enumerate}


\item (5 points) Describe the AdaBoost learning algorithm. Include the
    formula for setting $\alpha_i$ and justify it. Discuss the time
    complexity of the algorithm. Compare its properties with SVM,
    neareast neighbour and neural network learning and classification methods. 

\item The K-means algorithm. 
  \begin{enumerate}
     \item (1 point) Describe the basic algorithm. 
     \item (1 point) Your implementation of the K-means algorithm is
            run for $K=5$ and $K=6$ and the value of the cost function, i.e.
            the sum of squared difference from the prototypes is lower
            for $K=6$ than for $K=5$. Is this possible with a correct
            implementation ?
     \item (1 point) Describe a generalization to $L_1$ minimization,
         i.e. to the minimization of the sum of absolute differences.
     \item (1 point) Describe how to use k-means for string clustering.
     \item (1 point) Discuss the time complexity of various
         implementations of the standard algorithm and the generalizations. 
  \end{enumerate}

\end{enumerate}
\end{document}


