\documentclass[a4paper,10pt,oneside]{article}
\usepackage{a4wide,amsmath,amsfonts,german}
\usepackage[utf8]{inputenc}
\usepackage{algorithm}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{algorithmic}
\addtolength{\topmargin}{-2cm} \addtolength{\textheight}{3cm}
%
%\input blattdefs.tex
\usepackage{bm}
\bmdefine\c{c} \bmdefine\C{C} \bmdefine\U{U} \bmdefine\X{X}
\bmdefine\D{D} \bmdefine\K{K} \bmdefine\Z{Z} \bmdefine\x{x}
\bmdefine\z{z} \bmdefine\y{y} \bmdefine\Y{Y}
\bmdefine\bfalpha{\alpha} \bmdefine\bfmu{\mu} \bmdefine\M{M}
\bmdefine\Q{Q} \bmdefine\P{P} \bmdefine\w{w} \bmdefine\W{W}
\bmdefine\p{p} \bmdefine\T{T} \bmdefine\t{t} \bmdefine\r{r}
\bmdefine\a{a} \bmdefine\B{B} \bmdefine\I{I} \bmdefine\u{u}
\bmdefine\p{p} \bmdefine\Sig{\Sigma} \bmdefine\E{E} \bmdefine\F{F}
\bmdefine\S{S} \bmdefine\s{s} \bmdefine\w{w} \bmdefine\b{b}
\bmdefine\W{W} \bmdefine\w{w} \bmdefine\V{V} \bmdefine\v{v}
\bmdefine\q{q} \bmdefine\R{R} \bmdefine\A{A} \bmdefine\H{H}
\bmdefine\d{d} \bmdefine\g{g}
\bmdefine\G{G}
\DeclareMathOperator{\kk}{k}
\newcommand{\match}{{\boldsymbol{\mathrm I}}}
\newcommand{\bweight}{{B}}
\newcommand{\weight}{{\beta}}
\newcommand{\lweight}{w}
\newcommand{\weights}{\boldsymbol{\beta}}
\renewcommand{\w}{\boldsymbol{w}}
\newcommand{\lweights}{\boldsymbol{w}}
\newcommand{\order}{K}
\newcommand{\kmer}{$\order$-mer}
\newcommand{\kmers}{$\order$-mers}
\newcommand{\eps}{\varepsilon}%
\DeclareMathOperator*{\argmax}{argmax}
\newcommand{\svmlight}{SVM$^\text{\it light}$}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Der Header
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent \begin{minipage}[t]{0.6\linewidth}
Übung zur Vorlesung\\[.5em]

{\Huge Maschinelles Lernen 2}\\[.1em]

Sommersemester 2009
\end{minipage}\hfill
\begin{minipage}[t]{0.4\linewidth}
  \small
  \sffamily
  \begin{flushright}
    Abteilung Maschinelles Lernen\\
    Institut für Softwaretechnik und theoretische Informatik\\
    Fakultät IV, Technische Universität Berlin\\
    Prof. Dr. Klaus-Robert Müller\\
    Email: krm@cs.tu-berlin.de
  \end{flushright}
\end{minipage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Irgendwelche Informationen zum Blatt
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hyphenation{Ko-ef-fi-zien-ten}
\hyphenation{or-tho-go-na-len}
\hyphenation{trans-for-mier-ten}
\hyphenation{Ska-lie-run-gen}
\hyphenation{Stan-dard-ab-wei-chun-gen}
\hyphenation{pe-na-lized}
\hyphenation{Re-gu-la-ri-sie-rung}

\begin{center}
  {\Large\textbf{Blatt 10}}\\
  Abgabe bis \emph{Mittwoch}, 1. Juli 2009 bis 13 Uhr, Ausarbeitung im
  Sekretariat FR6052, oder bei Mikio Braun, FR6058, Lösung des
  praktischen Teils per Email an mikio@cs.tu-berlin.de.
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Die Aufgaben
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Aufgaben}

\noindent
Auf dem letzten Übungsblatt wurde der Weighted-Degree-Kernel per Email
an mikio@cs.tu-berlin.devorgestellt. Zur Erinnerung, wenn
$\u_{k,l}(x)$ der Teilstring der Länge $k$ an der Position $l$ des
Strings $\x$ ist, so ist der WDK definiert durch
\begin{equation*}
  \kk(\x_i,\x_j)=\sum_{k=1}^\order
  \weight_k\sum_{l=1}^{L-k+1}\match(\u_{k,l}(\x_i)=\u_{k,l}(\x_j)).
\end{equation*}
Auf diesem Übungsblatt soll der WDK zur Detektierung von Splicestellen
verwendet werden. Wir verwenden hierzu die SVM Implementierung
\svmlight{} (http://svmlight.joachims.org/).

\svmlight{} unterstützt von Hause aus nicht den WDK, daher werde wir
explizit die Merkmale
\begin{equation*}
  \phi_{w,k,l} = \sqrt{\weight_k}\match(\u_{k,l}(\x) = w).
\end{equation*}
für alle $w \in \{A, C, G, T\}^k$, $k \in \{1, \ldots, K\}$, $l \in
\{1, \ldots |\x| - k\}$ berechnen und dann einen linearen Kern
verwenden.

\begin{enumerate}
\item \textbf{15 Punkte} Vervollständige im Programmskelett die
  Funktion \verb|write_wdk_features|, die die WDK Merkmale wie oben
  beschrieben in eine \svmlight{}-Datei schreibt.
\item \textbf{15 Punkte} Trainiere \svmlight{} auf dem
  Splice-Datensatz für $K = \{1, 2, 3\}$ mit Regularisierungskonstante
  $C = \{0.001, 0.01, 0.1, 1, 10\}$ und messe die
  Vorhersagegenauigkeit auf dem Trainings- und Testdatensatz. Erzeuge
  für jedes $k$ einen Plot, der diese Genauigkeiten für Training und
  Test gegen $C$ plotte.
  
  Gib die Ergebnisse als Tabelle zusammen mit diesen drei Plots ab.
\end{enumerate}

\bigbreak
\hrule
\begin{verbatim}
function sheet10

X = textread('splice-train-data.txt', '%s');
Y = load('splice-train-label.txt');
XE = textread('splice-test-data.txt', '%s');
YE = load('splice-test-label.txt');

tic
fprintf('Writing training features for k = 1\n');
write_wdk_features('wdk1-train.txt', 1, X, Y);
fprintf('Writing test features for k = 1\n');
write_wdk_features('wdk1-test.txt', 1, XE, YE);
toc

tic
fprintf('Writing training features for k = 2\n');
write_wdk_features('wdk2-train.txt', 2, X, Y);
fprintf('Writing test features for k = 2\n');
write_wdk_features('wdk2-test.txt', 2, XE, YE);
toc

tic
fprintf('Writing training features for k = 3\n');
write_wdk_features('wdk3-train.txt', 3, X, Y);
fprintf('Writing test features for k = 3\n');
write_wdk_features('wdk3-test.txt', 3, XE, YE);
toc

function beta = beta(K, k)
beta = 2 * (K - k + 1) / K / (K + 1);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Your solution below
%

% 1. write out weighted degree kernel features
% out into file FN up to degree K. (You should accept values of K = 1, 2,
% 3
function write_wdk_features(FN, K, X, Y)
% ...
\end{verbatim}
\hrule

\end{document}
