\documentclass[a4paper,11pt]{article}
\usepackage{latexsym,amssymb,amsmath}
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc} 
\usepackage[MeX]{polski}
\usepackage{nicefrac}


\newcommand{\bx}{\boldsymbol{x}}
\newcommand{\by}{\boldsymbol{y}}
\newcommand{\bw}{\boldsymbol{w}}
\newcommand{\bh}{\boldsymbol{h}}
\DeclareMathOperator*{\argmax}{\arg \max}
\DeclareMathOperator*{\argmin}{\arg \min} 
\newcommand{\given}{\, | \,} 

\author{Imię Nazwisko}

\title{Elementy teorii uczenia maszynowego\\ 
\Large \textbf{Raport końcowy}} 

\date{}

\begin{document}

\maketitle 

\section{Propozycja rozwiązania problemu dziedzinowego metodami uczenia maszynowego}

Oddanie tej części raportu będzie wystarczające na ocenę 4.0. Ta część raportu powinna być zwięzła i treściwa. Nie może przekroczyć 4 stron. 

\subsection{Dziedzina problemu} 

Krótki opis dziedziny związanej z pracą badawczą lub zawodową studenta. 

Maksymalnie 1/2 strony.

\subsection{Opis problemu}

Krótki opis wyizolowanego problemu z rozważanej dziedziny, który może zostać rozwiązany metodami uczenia maszynowego

Maksymalnie 1/2 strony.

\subsection{Dane}

Opis danych, które będą używane podczas uczenia, testowania i fazy eksploatacji stworzonego modelu:
\begin{enumerate}
\item Cechy (\textit{features}), ich charakter i liczba,
\item Zmienna wyjściowa (\textit{supervision}, \textit{output}, \textit{outcome}), ich charakter (ciągła, dyskretna, jedno- lub wielowymiarowa, itp.) oraz rozmiar (np. liczba etykiet),
\item Sposób pozyskania cech i zmiennych wyjściowych do procesu uczenia i predykcji,
\item Podział danych na zbiór uczący, walidujący i testowy. 
\end{enumerate}

Maksymalnie 1 strona.

\subsection{Identyfikacja problemu}

Formalne zidentyfikowanie problemu:
\begin{enumerate}
\item Jaki jest charakter problemu? Regresja, klasyfikacja binarna, wieloklasowa, wieloetykietowa, ranking?
\item Funkcja straty używana do oceny jakości modelu?
\item Jak ma się liczba cech jest do liczby przykładów uczących (znacząco mniejsza/większa, porównywalna)?
\item Czy problem ma charakter inkrementacyjny?
\end{enumerate}


Maksymalnie 1 strona.

\subsection{Metoda/Rozwiązanie/Implementacja}

Opis możliwego rozwiązania:
\begin{enumerate}
\item Jaki algorytm można wykorzystać do rozwiązania problemu?
\item Jeżeli problem jest złożony, czy możliwe jest jego rozbicie na prostsze problemy? Czy taka redukcja pozwoli na optymalne rozwiązanie oryginalnego problemu?
\item Możliwe problemy implementacyjne wynikające z brakujących danych, dużego rozmiaru danych, itp..
\end{enumerate}

Maksymalnie 1 strona.

\subsection{Podsumowanie}

Na końcu zawsze powinno być jakieś podsumowanie :)

Maksymalnie 1/2 strony.


\section{Pytania dodatkowe}

Poprawna odpowiedź na każde z poniższych pytań podwyższa ocenę o 1 punkt. 

Lista pytań:
\begin{enumerate}
\item Rozważmy funkcję straty wartości bezwzględnej (\emph{absolute value loss function}):
\[
 \ell(y, \widehat{y}) = |y - \widehat{y}|.
\]
Pokaż, że jeśli $y$ pochodzi z jakiegoś rozkładu $P(y)$, to optymalną decyzją minimalizującą
oczekiwaną wartość funkcji straty jest \textbf{mediana}, tzn.:
\[
 \mathrm{median}(y) = \arg\min_{\widehat{y}} \mathbb{E}_{y \sim P} \left[ |y - \widehat{y}| \right].
\]
\item Dla klasyfikacji binarnej i zero-jedynkowej funkcji straty, optymalnym klasyfikatorem Bayesowskim jest:
\[
 h^*(\bx) = \mathrm{sgn}(\eta(\bx) - 1/2), \qquad \text{gdzie~~} \eta(\bx) = P(y=1|\bx).
\]
Wyznacz klasyfikator Bayesowski dla funkcji straty z kosztami klasyfiakcji (\emph{cost-sensitive loss function}):
\[
 \ell(y, \widehat{y}) = \left\{
 \begin{array}{ll}
  0 &\qquad \text{jeśli~~} y = \widehat{y},\\
  1 &\qquad \text{jeśli~~} y = 1, \, \widehat{y} = -1,\\
  \beta &\qquad \text{jeśli~~} y = -1,\,  \widehat{y} = 1.
 \end{array}
 \right.
\]
Uwaga: dla $\beta=1$ otrzymujemy błąd zero-jedynkowy, wtedy klasyfikator Bayesowski powininen zgadzać się z poprzednim wynikiem.
\item Naiwny klasyfikator bayesowski (\emph{Naive Bayes}) bazuje na założeniu niezależności cech w danej klasie, tzn.
dla dowolnej klasy $k$ i dowolnego $\bx = (x_1,\ldots,x_m)$,
\[
 P(\bx|y=k) = \prod_{j=1}^m P(x_j|y=k).
\]
Czy to założenie implikuje (lub jest implikowane przez) założenie o ogólnej niezależności cech:
\[
 P(\bx) = \prod_{j=1}^m P(x_j),
\]
bez warunkowania w danej klasie? Odpowiedź uzasadnij (podając kontrprzykład dla odpowiedzi negatywnej, bądź przedstawiając dowód
dla odpowiedzi pozytywnej).
\item Czy naiwny klasyfikator bayesowski (\emph{Naive Bayes}) jest klasyfikatorem liniowym, tzn. czy odpowiada funkcji klasyfikującej:
\[
 h(\bx) = \mathrm{sgn}(f(\bx)),\qquad \text{gdzie~~} f(\bx) = w_0 + \sum_{j=1}^m w_j x_j?
\]
Odpowiedź ściśle uzasadnij. Możesz ograniczyć się dla prostoty do cech binarnych, tj. $x \in \{0,1\}$.
\item Co dzieje się z rozwiązaniem regresji liniowej:
\[
 \widehat{\bw} = \left( \sum_{i=1}^n \bx_i \bx_i^\top \right)^{-1} \left(\sum_{i=1}^n  y_i \bx_i\right),
\]
gdy liczba cech $m$ jest większa od liczby przykładów uczących $n$? Odpowiedź uzasadnij. Opisz sposób (również z uzasadnieniem),
w jaki można temu problemowi zaradzić.
\item Pokaż, że minimalizacja błędu zero-jedynkowe w klasie klasyfikatorów liniowych jest problemem NP-trudnym (wykonaj redukcję
do innego problemu NP-trudnego).
\item Pokaż, że omawiane funkcje straty:
\begin{itemize}
\item kwadratowa $\ell(f) = (1-f)^2$,
\item logistyczna $\ell(f) = \log\left(1+e^{-f}\right)$,
\item zawiasowa $\ell(f) = \max\{0,1-f\}$,
\item wykładnicza $\ell(f) = e^{-f}$.
\end{itemize}
są wypukłe ze wględu na margines $f$.
\item  Pokaż, że jeśli przykłady uczące w klasyfikacji binarnej 
są generowane z rozkładu $y \sim P(y)$, $y \in \{-1,1\}$, a następnie
 $\bx | y \sim N(\mu_y , \Sigma)$ (tzn. każda z klas ma swoją własną średnią, ale macierz
 kowariancji jest wspólna), wtedy 
 $\log \frac{\eta(\bx)}{1 - \eta(\bx)}$ jest liniową funkcją $\bx$, 
 gdzie $\eta(\bx) = P(y=1|\bx)$. Dla prostoty możesz założyć, że $\Sigma$ jest macierzą jednostkową.
 \item Udowodnij, że wszystkie poniższe funkcje straty są skalibrowane ze względu na klasyfikację binarną (\emph{classification calibrated})
 i wyprowadź dla każdej funkcji starty postać klasyfikatora bayesowskiego:
\begin{itemize}
\item kwadratowa $\ell(f) = (1-f)^2$,
\item logistyczna $\ell(f) = \log\left(1+e^{-f}\right)$,
\item zawiasowa $\ell(f) = \max\{0,1-f\}$,
\item wykładnicza $\ell(f) = e^{-f}$.
\end{itemize}
\item Udowodnij, że klasa prostokątów na płaszczyźnie ma wymiar Vapnika-Chervonenkisa równy $4$.
\item Udowodnij, że klasyfikator bayesowski dla błędu Hamminga i wieloetykietowego błędu zerojedynkowego (ang. \emph{subset 0/1 loss}) wyraża się odpowiednio następującymi wzorami:
\begin{itemize}
\item błąd Hamminga: 
$$
\bh^*(\bx) = (h_1^*(\bx), h_2^*(\bx), \ldots, h_m^*(\bx)),
$$
gdzie $h_i^*(\bx) = \argmax_{y_i \in \{0,1\}} \Pr(y_i  \given \bx )$, dla $i = 1,\ldots,m$,
\item wieloetykietowy błąd 0/1: 
$$
\bh^*(\bx) = \arg \max_{\by \in \mathcal{Y}} \Pr(\by \given \bx) = \arg \max_{\by \in \mathcal{Y}} \Pr(\by \given \bx)
$$,
\end{itemize}
\item Pokaż, że strukturalna metoda wektorów wspierających (ang.\emph{structured support vector machines}) dla funkcji skoringowej $f(\bx,\by) = \sum_{i=1}^m f_i(\bx, y_i)$ sprowadza się do metody niezależnych klasyfikatorów binarnych (ang. \emph{binary relevance}) ze standardową (tzn. binarną) wersją metody wektorów wspierających. Równoważność należy wykazać na poziomie zastępczych funkcji strat (ang. \emph{surrogate loss functions}).
\item Pokaż, że metoda warunkowych pól losowych (ang.\emph{conditional random fields}) dla funkcji skoringowej $f(\bx,\by) = \sum_{i=1}^m f_i(\bx, y_i)$ sprowadza się do metody niezależnych klasyfikatorów binarnych (ang. \emph{binary relevance}) ze standardową (tzn. binarną) regresją logistyczną. Równoważność należy wykazać na poziomie zastępczych funkcji strat (ang. \emph{surrogate loss functions}).
 \end{enumerate}


\end{document}  
