diff --git a/is/UB4/ISUB4.pdf b/is/UB4/ISUB4.pdf new file mode 100644 index 0000000..49e24e8 --- /dev/null +++ b/is/UB4/ISUB4.pdf Binary files differ diff --git a/is/UB4/ISUB4.tex b/is/UB4/ISUB4.tex new file mode 100644 index 0000000..f17f27f --- /dev/null +++ b/is/UB4/ISUB4.tex @@ -0,0 +1,198 @@ +\documentclass[a4paper,12pt]{scrartcl} +\usepackage[ngerman]{babel} +\usepackage{graphicx} %BIlder einbinden +\usepackage{amsmath} %erweiterte Mathe-Zeichen +\usepackage{amsfonts} %weitere fonts +\usepackage[utf8]{inputenc} %Umlaute & Co +\usepackage{hyperref} %Links +\usepackage{ifthen} %ifthenelse +\usepackage{enumerate} +\usepackage{listings} +\lstset{language=Python} + +\usepackage{algpseudocode} %Pseudocode +\usepackage{dsfont} % schöne Zahlenräumezeichen +\usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen +\usepackage{tikz} %TikZ ist kein Zeichenprogramm +\usetikzlibrary{trees,automata,arrows,shapes} + +\pagestyle{empty} + + +\topmargin-50pt + +\newcounter{aufgabe} +\def\tand{&} + +\newcommand{\makeTableLine}[2][0]{% + \setcounter{aufgabe}{1}% + \whiledo{\value{aufgabe} < #1}% + {% + #2\tand\stepcounter{aufgabe}% + } +} + +\newcommand{\aufgTable}[1]{ + \def\spalten{\numexpr #1 + 1 \relax} + \begin{tabular}{|*{\spalten}{p{1cm}|}} + \makeTableLine[\spalten]{A\theaufgabe}$\Sigma$~~\\ \hline + \rule{0pt}{15pt}\makeTableLine[\spalten]{}\\ + \end{tabular} +} + +\def\header#1#2#3#4#5#6#7{\pagestyle{empty} +\begin{minipage}[t]{0.47\textwidth} +\begin{flushleft} +{\bf #4}\\ +#5 +\end{flushleft} +\end{minipage} +\begin{minipage}[t]{0.5\textwidth} +\begin{flushright} +#6 \vspace{0.5cm}\\ +% Number of Columns Definition of Columns second empty line +% \begin{tabular}{|*{5}{C{1cm}|}}\hline A1&A2&A3&A4&$\Sigma$\\\hline&&&&\\\hline\end{tabular}\\\vspace*{0.1cm} +\aufgTable{#7} +\end{flushright} +\end{minipage} +\vspace{1cm} +\begin{center} +{\Large\bf Sheet #1} + +{(Hand in #3)} +\end{center} +} + + + +%counts the exercisenumber +\newcounter{n} + +%Kommando für Aufgaben +%\Aufgabe{AufgTitel}{Punktezahl} +\newcommand{\Aufgabe}[2]{\stepcounter{n} + \textbf{Exercise \arabic{n}: #1} (#2 Points)\\} + +\newcommand{\norm}[1]{\left \| #1 \right \|} +\DeclareMathOperator{\minimize}{minimize} +\DeclareMathOperator{\maximize}{maximize} +\newcommand{\real}{\mathbb{R}} +\newcommand{\blasso}{\beta^{\mathrm{LASSO}}} +\newcommand{\bzero}{\beta^0} +\newcommand{\bLS}{\hat{\beta}^{\mathrm{LS}}} + + + +\begin{document} + %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben} + \header{1}{}{2015-04-22}{Intelligent Systems I}{\textit{Maximus Mutschler}\\ \textit{Jan-Peter Hohloch} + }{SS 15}{4} + \vspace{1cm} + \Aufgabe{LASSO \& $l_0$}{30} + \begin{enumerate} + \item \begin{enumerate} + \item \includegraphics[width=.4\textwidth]{ghard.png} + \item \begin{align*} + \hat{\beta}^{LS}&=\left(X^TX\right)^{-1}X^T\mathbf{y}\\ + &=\left(nI_{n\times n} \right)^{-1}X^T\mathbf{y}\\ + &=\frac{1}{n}\cdot I_{n\times n}X^T\mathbf{y}\\ + &=\frac{1}{n}\cdot X^T\mathbf{y} + \end{align*} + \item \begin{math} + \bzero(\lambda) := \mathrm{arg \, min}_{\beta} \frac{1}{n} \norm{Y - X \beta}_2^2 + \lambda \norm{\beta}_0 ,\\ + =\mathrm{arg \, min}_{\beta} \underbrace{\frac{1}{n} Y^{T}Y}_{constant}- \frac{2}{n}Y^{T}X\beta+\norm{\beta}^2+\lambda \norm{\beta}_0 \\ + =\mathrm{arg \, min}_{\beta} -\frac{2}{n}Y^{T}X\beta+\norm{\beta}^2+\lambda \norm{\beta}_0 \\ + =\mathrm{min}_{\beta} \sum^p_{i=1}-\frac{2}{n}Y^{T}_iX_i\beta_i+\beta_i^2+\lambda \cdot \begin{cases} + 0, \beta_i =0\\ + 1, \beta_i \neq 0\\ + \end{cases} %0 oder eins + \\\text{The problem can be simplified to one}\\ \text{ some element representing all others}\\ + L_i=\begin{cases} + 0, \beta_i =0\\ + -\frac{2}{n}Y^{T}_iX_i\beta_i+\beta_i^2+\lambda , \beta_i \neq 0\\ + \end{cases} \\ + \\\frac{d L_i }{d \beta}= -\frac{2}{n} X_i^TY_i +2 \beta_i \overset{!}{=} 0\\ + \beta_i= \frac{1}{n} X^T_iY_i\\ + \text{$\beta_i$ in $L_i$,$\beta_i \neq 0$, determine for which $\lambda$ $\beta_i =0$}\\ + 0= -2\beta_i^2+\beta_i^2 +\lambda\\ + \lambda=|\beta_i|^2\\ + \lambda = \left|\frac{1}{n} X^T_iY_i\right|^2 \\ + \sqrt{\lambda} = \left|\frac{1}{n} X^T_iY_i\right| \\ + \bzero(\lambda) = \frac{1}{n} X^T_iY_i \cdot + \begin{cases} + 0, |X^T_iY_i| =\sqrt{\lambda}\\ + 1, |X^T_iY_i|><\sqrt{\lambda}\\ + \end{cases} + \end{math} + \end{enumerate} + \item \begin{enumerate} + \item \includegraphics[width=0.4\textwidth]{gsoft.png} + \item \begin{math}\blasso(\lambda) := \mathrm{arg \, min}_{\beta} \frac{1}{n} \norm{Y - X \beta}_2^2 + \lambda \norm{\beta}_1 ,\\ + =\mathrm{arg \, min}_{\beta} \underbrace{\frac{1}{n} Y^{T}Y}_{constant}- \frac{2}{n}Y^{T}X\beta+\norm{\beta}^2+\lambda \norm{\beta}_1 \\ + =\mathrm{arg \, min}_{\beta} -\frac{2}{n}Y^{T}X\beta+\norm{\beta}^2+\lambda \norm{\beta}_1 \\ + =\mathrm{min}_{\beta} \sum^p_{i=1}-\frac{2}{n}Y^{T}_iX_i\beta_i+\beta_i^2+\lambda |\beta_i|\\ + \text{Minimize for a fixed i}\\\text{The problem can be simplified to the sum of its parts}\\ + L_i=-\frac{2}{n}Y^{T}_iX_i\beta_i+\beta_i^2+\lambda |\beta_i|\\ + \text{ $Y^{T}_iX_i >0$ subjects to $\beta_i \geq 0$}\\\text{and vice versa $Y^{T}_iX_i \leq0$ subjects to $\beta_i \leq 0$ }\\\\ + \text{Case 1: $Y^{T}_iX_i >0$ and $\beta_i \geq 0$}\\ + \frac{dL_i}{d\beta} =-\frac{2}{n}Y^{T}_iX_i+2\beta_i+\lambda \overset{!}{=} 0\\ + \beta_i = \frac{1}{n}Y^{T}_iX_i-\frac{\lambda}{2}\\ + \text{this is only feasible if the right-hand side is nonnegative}\\ + \blasso_i(\lambda) =\left(\frac{1}{n}Y^{T}_iX_i-\frac{\lambda}{2}\right)^+ + \\= sgn(\frac{1}{n}Y^{T}_iX_i)% den schritt verstehe ich nicht + \cdot\left(\left|\frac{1}{n}Y^{T}_iX_i\right|-\frac{\lambda}{2}\right)^+\\ + \text{Case 2: $Y^{T}_iX_i \leq0$ and $\beta_i \leq 0$}\\ + \text{leads obviously to the same equation, so it's proven} + % quelle http://stats.stackexchange.com/questions/17781/derivation-of-closed-form-lasso-solution + \end{math}\\ + We needed more than 12 hours to solve these equations. Please be aware of the fact that we are computer scientist with only a basic math education. We are not mathematics students! + \end{enumerate} + \end{enumerate} + \Aufgabe{LASSO}{70} + \begin{lstlisting} +def printOutput(lm_, Xtest_, ytest_): # lm_ = instance of linear_model.xxx(xxx) +yhat = lm_.predict(Xtest_) +plt.figure(1) +plt.title("Regression Weights") +plt.plot(lm_.coef_.T) +plt.figure(2) +plt.title('yhat vs ytest') +plt.plot(ytest_, yhat, 'ro') +plt.show() +print('R2 :', lm_.score(Xtest_,ytest_)) +print('Gene with Strongest Coefficient :' , abs(lm_.coef_).argmax()) +if hasattr(lm_, 'alpha'): print('Used Lambda :', lm.alpha) +if hasattr(lm_, 'alpha_'): print('Lambda_ResultOfCV :', lm.alpha_ ) + \end{lstlisting} + \begin{enumerate}[a)] + \item What should happen if you tried to apply linear regression without any regularizer on this data set? + \begin{itemize} + \item many non-zero weights + \item possible large weights + \end{itemize} + \item Does this happen with the function \_linear\_model.LinearReagression()\_ ? + \begin{itemize} + \item yes (only 1 zero for 4710, 3290) + \item no (largest weight for 4710 ~0.0227, for 3290 ~0.0477) + \end{itemize} + \end{enumerate} + \includegraphics[width=0.49\textwidth]{outputLinear.png} + \includegraphics[width=0.49\textwidth]{outputRidge.png}\\ + \includegraphics[width=\textwidth]{outputLasso.png}\\ + with the following Code: + \begin{lstlisting} +lm = linear_model.RidgeCV(cv=10) ### CHANGE THIS LINE ### +lm.n_jobs=-1 +lm.fit(Xtrain, ytrain); +#------------------------------------------------------------- +lm = linear_model.LassoCV(cv=10) ### CHANGE THIS LINE ### +lm.n_jobs=-1 +lm.max_iter=1000 +lm.fit(Xtrain, ytrain) + +printOutput(lm, Xtest, ytest) ### PROVIDE THE OUTPUT ### + +print('Regression Coefficient of Gene 5954 : ', lm.coef_[5954]) + \end{lstlisting} +\end{document} + diff --git a/is/UB4/ghard.png b/is/UB4/ghard.png new file mode 100644 index 0000000..00b6f44 --- /dev/null +++ b/is/UB4/ghard.png Binary files differ diff --git a/is/UB4/gsoft.png b/is/UB4/gsoft.png new file mode 100644 index 0000000..e0c078b --- /dev/null +++ b/is/UB4/gsoft.png Binary files differ diff --git a/is/UB4/outputLasso.png b/is/UB4/outputLasso.png new file mode 100644 index 0000000..3ea7034 --- /dev/null +++ b/is/UB4/outputLasso.png Binary files differ diff --git a/is/UB4/outputLinear.png b/is/UB4/outputLinear.png new file mode 100644 index 0000000..0f11c8c --- /dev/null +++ b/is/UB4/outputLinear.png Binary files differ diff --git a/is/UB4/outputRidge.png b/is/UB4/outputRidge.png new file mode 100644 index 0000000..fa1cd51 --- /dev/null +++ b/is/UB4/outputRidge.png Binary files differ