1 \documentclass[a4paper,10pt,oneside]{article}
   2 \usepackage{a4wide,amsmath,amsfonts,german}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{algorithm}
   5 \usepackage{graphicx}
   6 \usepackage{hyperref}
   7 \usepackage{algorithmic}
   8 \addtolength{\topmargin}{-2cm} \addtolength{\textheight}{3cm}
   9 %
  10 %\input blattdefs.tex
  11 \usepackage{bm}
  12 \bmdefine\c{c} \bmdefine\C{C} \bmdefine\U{U} \bmdefine\X{X}
  13 \bmdefine\D{D} \bmdefine\K{K} \bmdefine\Z{Z} \bmdefine\x{x}
  14 \bmdefine\z{z} \bmdefine\y{y} \bmdefine\Y{Y}
  15 \bmdefine\bfalpha{\alpha} \bmdefine\bfmu{\mu} \bmdefine\M{M}
  16 \bmdefine\Q{Q} \bmdefine\P{P} \bmdefine\w{w} \bmdefine\W{W}
  17 \bmdefine\p{p} \bmdefine\T{T} \bmdefine\t{t} \bmdefine\r{r}
  18 \bmdefine\a{a} \bmdefine\B{B} \bmdefine\I{I} \bmdefine\u{u}
  19 \bmdefine\p{p} \bmdefine\Sig{\Sigma} \bmdefine\E{E} \bmdefine\F{F}
  20 \bmdefine\S{S} \bmdefine\s{s} \bmdefine\w{w} \bmdefine\b{b}
  21 \bmdefine\W{W} \bmdefine\w{w} \bmdefine\V{V} \bmdefine\v{v}
  22 \bmdefine\q{q} \bmdefine\R{R} \bmdefine\A{A} \bmdefine\H{H}
  23 \bmdefine\d{d} \bmdefine\g{g}
  24 \bmdefine\G{G}
  25 \DeclareMathOperator{\kk}{k}
  26 \newcommand{\match}{{\boldsymbol{\mathrm I}}}
  27 \newcommand{\bweight}{{B}}
  28 \newcommand{\weight}{{\beta}}
  29 \newcommand{\lweight}{w}
  30 \newcommand{\weights}{\boldsymbol{\beta}}
  31 \renewcommand{\w}{\boldsymbol{w}}
  32 \newcommand{\lweights}{\boldsymbol{w}}
  33 \newcommand{\order}{K}
  34 \newcommand{\kmer}{$\order$-mer}
  35 \newcommand{\kmers}{$\order$-mers}
  36 \newcommand{\eps}{\varepsilon}%
  37 \DeclareMathOperator*{\argmax}{argmax}
  38 \newcommand{\svmlight}{SVM$^\text{\it light}$}
  39 \begin{document}
  40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  41 %
  42 % Der Header
  43 %
  44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  45 
  46 \noindent \begin{minipage}[t]{0.6\linewidth}
  47 Übung zur Vorlesung\\[.5em]
  48 
  49 {\Huge Maschinelles Lernen 2}\\[.1em]
  50 
  51 Sommersemester 2009
  52 \end{minipage}\hfill
  53 \begin{minipage}[t]{0.4\linewidth}
  54   \small
  55   \sffamily
  56   \begin{flushright}
  57     Abteilung Maschinelles Lernen\\
  58     Institut für Softwaretechnik und theoretische Informatik\\
  59     Fakultät IV, Technische Universität Berlin\\
  60     Prof. Dr. Klaus-Robert Müller\\
  61     Email: krm@cs.tu-berlin.de
  62   \end{flushright}
  63 \end{minipage}
  64 
  65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  66 %
  67 % Irgendwelche Informationen zum Blatt
  68 %
  69 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  70 \hyphenation{Ko-ef-fi-zien-ten}
  71 \hyphenation{or-tho-go-na-len}
  72 \hyphenation{trans-for-mier-ten}
  73 \hyphenation{Ska-lie-run-gen}
  74 \hyphenation{Stan-dard-ab-wei-chun-gen}
  75 \hyphenation{pe-na-lized}
  76 \hyphenation{Re-gu-la-ri-sie-rung}
  77 
  78 \begin{center}
  79   {\Large\textbf{Blatt 10}}\\
  80   Abgabe bis \emph{Mittwoch}, 1. Juli 2009 bis 13 Uhr, Ausarbeitung im
  81   Sekretariat FR6052, oder bei Mikio Braun, FR6058, Lösung des
  82   praktischen Teils per Email an mikio@cs.tu-berlin.de.
  83 \end{center}
  84 
  85 
  86 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  87 %
  88 % Die Aufgaben
  89 %
  90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  91 
  92 \section*{Aufgaben}
  93 
  94 \noindent
  95 Auf dem letzten Übungsblatt wurde der Weighted-Degree-Kernel per Email
  96 an mikio@cs.tu-berlin.devorgestellt. Zur Erinnerung, wenn
  97 $\u_{k,l}(x)$ der Teilstring der Länge $k$ an der Position $l$ des
  98 Strings $\x$ ist, so ist der WDK definiert durch
  99 \begin{equation*}
 100   \kk(\x_i,\x_j)=\sum_{k=1}^\order
 101   \weight_k\sum_{l=1}^{L-k+1}\match(\u_{k,l}(\x_i)=\u_{k,l}(\x_j)).
 102 \end{equation*}
 103 Auf diesem Übungsblatt soll der WDK zur Detektierung von Splicestellen
 104 verwendet werden. Wir verwenden hierzu die SVM Implementierung
 105 \svmlight{} (http://svmlight.joachims.org/).
 106 
 107 \svmlight{} unterstützt von Hause aus nicht den WDK, daher werde wir
 108 explizit die Merkmale
 109 \begin{equation*}
 110   \phi_{w,k,l} = \sqrt{\weight_k}\match(\u_{k,l}(\x) = w).
 111 \end{equation*}
 112 für alle $w \in \{A, C, G, T\}^k$, $k \in \{1, \ldots, K\}$, $l \in
 113 \{1, \ldots |\x| - k\}$ berechnen und dann einen linearen Kern
 114 verwenden.
 115 
 116 \begin{enumerate}
 117 \item \textbf{15 Punkte} Vervollständige im Programmskelett die
 118   Funktion \verb|write_wdk_features|, die die WDK Merkmale wie oben
 119   beschrieben in eine \svmlight{}-Datei schreibt.
 120 \item \textbf{15 Punkte} Trainiere \svmlight{} auf dem
 121   Splice-Datensatz für $K = \{1, 2, 3\}$ mit Regularisierungskonstante
 122   $C = \{0.001, 0.01, 0.1, 1, 10\}$ und messe die
 123   Vorhersagegenauigkeit auf dem Trainings- und Testdatensatz. Erzeuge
 124   für jedes $k$ einen Plot, der diese Genauigkeiten für Training und
 125   Test gegen $C$ plotte.
 126   
 127   Gib die Ergebnisse als Tabelle zusammen mit diesen drei Plots ab.
 128 \end{enumerate}
 129 
 130 \bigbreak
 131 \hrule
 132 \begin{verbatim}
 133 function sheet10
 134 
 135 X = textread('splice-train-data.txt', '%s');
 136 Y = load('splice-train-label.txt');
 137 XE = textread('splice-test-data.txt', '%s');
 138 YE = load('splice-test-label.txt');
 139 
 140 tic
 141 fprintf('Writing training features for k = 1\n');
 142 write_wdk_features('wdk1-train.txt', 1, X, Y);
 143 fprintf('Writing test features for k = 1\n');
 144 write_wdk_features('wdk1-test.txt', 1, XE, YE);
 145 toc
 146 
 147 tic
 148 fprintf('Writing training features for k = 2\n');
 149 write_wdk_features('wdk2-train.txt', 2, X, Y);
 150 fprintf('Writing test features for k = 2\n');
 151 write_wdk_features('wdk2-test.txt', 2, XE, YE);
 152 toc
 153 
 154 tic
 155 fprintf('Writing training features for k = 3\n');
 156 write_wdk_features('wdk3-train.txt', 3, X, Y);
 157 fprintf('Writing test features for k = 3\n');
 158 write_wdk_features('wdk3-test.txt', 3, XE, YE);
 159 toc
 160 
 161 function beta = beta(K, k)
 162 beta = 2 * (K - k + 1) / K / (K + 1);
 163 
 164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 165 %
 166 % Your solution below
 167 %
 168 
 169 % 1. write out weighted degree kernel features
 170 % out into file FN up to degree K. (You should accept values of K = 1, 2,
 171 % 3
 172 function write_wdk_features(FN, K, X, Y)
 173 % ...
 174 \end{verbatim}
 175 \hrule
 176 
 177 \end{document}