\documentclass[10pt]{article}

\usepackage{amsfonts,amssymb}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage{multicol}

\newcommand{\argmin}{\mathop{\rm arg\,min}\limits}
\newcommand{\argmax}{\mathop{\rm arg\,max}\limits}
\newcommand{\sign}{\mathop{\rm sign}\limits}
\newcommand{\cond}{\mspace{3mu}{|}\mspace{3mu}}
\def\RR{\mathbb{R}}
\def\XX{\mathbb{X}}
\def\EE{\mathbb{E}}
\def\NN{\mathcal{N}}
\def\LL{\mathcal{L}}
\def\YY{\mathbb{Y}}


\textheight=220mm
\textwidth=160mm

\title{Школа анализа данных\\Машинное обучение, часть 2\\Домашнее задание №2}
\author{}
\date{}

\begin{document}


\voffset=-20mm
\hoffset=-17mm
\font\Got=eufm10 scaled\magstep2 \font\Got=eufm10


\maketitle


\textbf{Задача 1 (1.5 балла) Композиции алгоритмов, бустинг, AdaBoost}.

    Обозначим через~$\tilde w^{(N)}$ нормированный вектор весов
    на~$N$-й итерации алгоритма AdaBoost.
    Покажите, что взвешенная ошибка базового классификатора~$b_N$
    относительно весов со следующего шага~$\tilde w_i^{(N + 1)}$
    равна~$1/2$:
    \[
        \sum_{i = 1}^{\ell}
            \tilde w_i^{(N + 1)}
            [b_N(x_i) \neq y_i]
        =
        \frac{1}{2}.
    \]

\bigskip


\textbf{Задача 2 (2 балла) Градиентный бустинг}.
    ~

    \begin{enumerate}


        \item Какой функции потерь будет соответствовать градиентный бустинг, который на каждой итерации настраивается на разность между вектором истинных меток и текущим вектором предсказанных меток?

        \item Градиентный бустинг обучается на пяти объектах с функцией потерь для одного объекта
        \[
            \mathcal{L}(\tilde y, y) = (\tilde y - y)^4.
        \]
        На некоторой итерации полученная композиция дает ответ $(5, 10, 6, 3, 0)$. На какой вектор ответов будет настраиваться следующий базовый алгоритм, если истинный вектор ответов равен $(6, 8, 6, 4, 1)$?

        \item Рассмотрим задачу бинарной классификации,~$Y = \{0, 1\}$.
    Будем считать, что все алгоритмы из базового семейства~$\mathcal{A}$
    возвращают ответы из отрезка~$[0, 1]$, которые можно интерпретировать
    как вероятности принадлежности объекта к классу~$1$.
    В качестве функции потерь возьмем отрицательный
    логарифм правдоподобия~(negative log-likelihood):
    \[
        L(y, z)
        =
        -\bigl(
        y \log z
        +
        (1 - y) \log(1 - z)
        \bigr),
    \]
    где~$y$~--- правильный ответ, а~$z$~--- ответ алгоритма.

    Выпишите формулы для поиска базовых алгоритмов~$b_n$
    и коэффициентов~$\gamma_n$ в градиентном бустинге.
    \end{enumerate}
\bigskip



\bigskip
\textbf{Задача 3 (1.5 балла) Композиции, устойчивость к шуму}.
    ~

    \begin{enumerate}
      \item Рассмотрим алгоритм AdaBoost~--- бустинг с экспоненциальной функцией потерь \\
      $$\mathcal{L}(M)=\exp(-M),$$
где $M$ — отступ объекта. Покажите, что алгоритм неустойчив к шуму, т.е. возможен неограниченный рост отношения весов шумовых объектов по отношению к весам пороговых объектов.
      \item Покажите, что бустинг с логистической функцией потерь\\
      $$\mathcal{L}(M) = \log (1+\exp(-M))$$
устойчив к шуму в описанном выше смысле смысле.
    \end{enumerate}

    ~

    Примечание. Пороговые объекты~--- это те, для которых значение отступа положительно и порядка нуля, то есть они лежат близко к границе между классами и в своем классе. Шумовые объекты лежат глубоко в чужом классе, на них отступ принимает большие отрицательные значения.
\bigskip







\textbf{Задача 4 (2 балла) Ранжирование.}

    Имеются два ранжирующих правила $h_1(x)$ и $h_2(x)$. Дана выборка из одного запроса и $N$ документов. Релевантности документов и ответы каждого из ранжирующих правил на каждом документе этой выборки известны.
    Предложите точный алгоритм построения линейной композиции
    \[
        h(x) = \alpha h_1(x) + (1-\alpha) h_2(x),~~\alpha \in [0,1]
    \]
    двух ранкеров, имеющей оптимальное значение NDCG на этой выборке.
    Сложность алгоритма должна быть не выше $O(N^3)$.

\bigskip

\textbf{Задача 5 (2 балла) Рекомендательные системы, матричные разложения.}

    Допустим, мы хотим обучить рекомендательную систему, имея историю взаимодействия $n$ пользователей и $m$ товаров. Рассмотрим матрицу оценок $R\in \mathbb{R}^{n\times m}$, в которой известны лишь некоторые элементы: $r_{ui}$ -- оценка пользователя~$1\le u\le n$ для товара~$1\le i\le m$. Дополнительно предположим, что доля пар $(u,i)$  с известными оценками относительно всех пар равна $\alpha$, причем эти пары равномерно распределены по матрице оценок. Рассмотрим способ предсказания неизвестных оценок на основе модели Latent Factor Model, которая использует малоранговую аппроксимацию ранга~$r$ матрицы $R$:
    $$\tilde r_{ui} = p_u^T q_i, \quad p_u \in \mathbb{R}^{r}, \quad q_i \in \mathbb{R}^{r}.$$
    Параметры модели можно подбирать в ходе решения задачи восстановления пропущенных значений матрицы оценок (Matrix Completion):
    $$P,Q = \argmin_{P \in \mathbb{R}^{r\times n}, Q \in \mathbb{R}^{r\times m}} \sum_{(u,i)\in \text{known}}(r_{ui} - p_u^Tq_i)^2.$$
    Рассмотрим один из алгоритмов решения этой оптимизационной задачи -- Alternating Least Squares (ALS). Этот алгоритм поочередно фиксирует матрицы $P$ или $Q$ и подбирает оптимальное значение другой  матрицы, точно решая задачу с помощью линейного метода наименьших квадратов. Например, при фиксированном $P$:
    $$Q = \argmin_{Q \in \mathbb{R}^{r\times m}} \sum_{(u,i)\in \text{known}}(r_{ui} - p_u^Tq_i)^2.$$
    Выпишите явные формулы для вычисления оптимального $Q$ при фиксированном $P$, а также покажите, что вычислительная сложность одного такого шага равна $O\left(r^2m(\alpha n + r)\right)$.

\bigskip
\textbf{Задача 6 (1 балла) Рекомендательные системы, матричные разложения.}

    В факторизационных машинах предсказание для объекта~$x \in \RR^{d}$ делается по формуле
    \[
        a(x)
        =
        w_0
        +
        \sum_{i = 1}^{d}
            w_j x_j
        +
        \sum_{i = 1}^{d} \sum_{j = i + 1}^{d}
            x_i x_j
            \langle \vec v_i, \vec v_j \rangle.
    \]
    Вычисление предсказания по этой формуле требует~$O(rd^2)$ операций,
    где~$r$~--- размер векторов~$\vec v_1, \dots, \vec v_d$.
    Покажите, что это же предсказание может быть найдено за~$O(rd)$ операций.

\bigskip





\end{document}