# Машинное обучение (7 семестр) <!-- Не трогаем этот блок --> <a class="btn btn-primary hidden-print" role="button" data-toggle="collapse" href="#doc .toc" aria-expanded="false" aria-controls="collapseExample"><i class="fa fa-bars fa-fw"></i></a> <a class="btn btn-primary" href="#FAQ" role="button"><i class="fa fa-question-circle fa-fw"></i> FAQ</a> <a class="btn btn-danger" href="https://github.com/egormkn/ifmo-kt/releases/download/7.machinelearning/conspect.pdf" role="button"><i class="fa fa-file-pdf-o fa-fw"></i> Скачать PDF</a> <a class="btn btn-info" href="https://hackmd.io/s/By7h7fMmV" role="button"><i class="fa fa-file-text-o fa-fw"></i> Открыть на HackMD</a> <a class="btn btn-danger" href="https://t.me/year2015" role="button"><i class="fa fa-heart fa-fw"></i> year2015</a> <style> #doc .toc {display: none;} #doc .toc.in {display: block !important;} #doc.markdown-body {max-width: 900px;} #doc.markdown-body ul, #doc.markdown-body ol {padding-left: 20px !important;margin-left: 20px !important;} .markdown-body h4 {font-size: 1.2em;} </style> [TOC] ## Ссылки [Google Drive]: https://drive.google.com/drive/folders/1onB4Z6fonJYuYf63wnsRw_iAExyJJL84 [Курс Воронцова]: http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) [Воронцов1.pdf]: http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf [Воронцов2.pdf]: http://www.machinelearning.ru/wiki/images/0/0d/Voron-ML-Compositions.pdf - [Google Drive] В вопросах ниже презентации будут нумероваться так: p1, p2 и т.п. - [Курс Воронцова] - [Воронцов (pdf) 1 сем][Воронцов1.pdf] - [Воронцов (pdf) 2 сем][Воронцов2.pdf] ----------------------------------------- ## Вопросы ### 1. :ok: Понятие машинного обучения в искусственном интеллекте. ###### `Презентация 1` > **Machine learning** is process (field of study) that gives computers ability to learn without being explicitly programmed. > [name=A.L. Samuel] **Машинное обучение** — процесс, который даёт возможность компьютерам обучаться выполнять что-то без явного написания кода. > A computer program is said to be learn from experience $E$ with respect to some task $T$ and some performance measure $P$, if its performance on $T$, as measured by $P$, improves with experience $E$. > [name=T.M. Mitchell] Можно сказать, что компьютерная программа обучается, имея опыт $E$ по некоторой задаче $T$, если её производительность, измеренная мерой $P$, растёт с получением опыта $E$. **Знания** — шаблоны в некоторой области (принципы, закономерности, связи, правила, законы), полученные с практикой и профессиональным опытом, которые помогают формулировать и решать задачи в некоторой сфере. **Знания $\neq$ Данные** **Data Science** — набор методов обработки и анализа данных и применение их к практическим задачам. 1) Сбор данных 2) Интеграция данных 3) Хранение данных 4) Анализ данных 5) Высокопроизводительные вычисления **Data Analysis** (*Business Intelligence*) — область математики и информатики, занимающаяся построением и исследованием наиболее общих математических методов и вычислительных алгоритмов извлечения знаний из экспериментальных данных. 1) Разведочный анализ данных 2) Проверка статистических гипотез 3) Предсказательная аналитика 4) Визуализация данных **Data Mining** — создание знаний из структурированных и неструктурированных источников. 1) Сбор данных 2) Конструирование признаков 3) Применение алгоритмов машинного обучения ### 2. :ok: Классификация задач машинного обучения, их примеры и особенности. ###### `Презентация 1` - **Обучение с учителем** (*Supervised learning*) Тренировочные данные доступны все сразу и размечены (известны ответы для поставленной задачи). - Классификация - Регрессия - Ранжирование - Прогнозирование - **Обучение без учителя** (*Unsupervised learning*) Тренировочные данные доступны все сразу, но не размечены (ответы для поставленной задачи неизвестны). - Кластеризация - Поиск ассоциативных правил - Выдача рекомендаций - Уменьшение размерности - **Обучение с частичным привлечением учителя** (*Semi-supervised learning*) Тренировочные данные доступны все сразу, но размечено мало, либо малоинформативная часть. Применяется в случаях, когда разметка всех тренировочных данных требует больших затрат времени и ресурсов. - **Обучение с подкреплением** (*Reinforcement learning*) Частный случай *обучения с учителем*, в котором сигналы подкрепления (правильности ответа) выдаются не учителем, а некоторой средой, с которой взаимодействует программа. - **Активное обучение** (*Active learning*) Частный случай *обучения с частичным привлечением учителя*, в котором алгоритм интерактивно запрашивает разметку тех данных, информация о которых может повысить точность работы. - **Обучение в реальном времени** (*Online learning*) Тренировочные данные поступают последовательно с течением времени, с каждым шагом улучшая точность работы. Пример: предсказание курса валют - **Структурное прогнозирование** (*Structured prediction*) Класс задач машинного обучения, ответом на которые является не скалярное значение, а более сложный объект с внутренней структурой. Примеры: синтаксический разбор естественного языка, сегментация объекта на картинке. - **Выбор модели и валидация** (*Model selection and validation*) Задачи выбора лучших гиперпараметров для семейства моделей (алгоритма). ### 3. :ok: Задача обучения с учителем, классификация задач обучения с учителем, метод минимизации эмпирического риска. ###### `Презентация 1` #### Постановка задачи $X$ — **множество объектов** (входное множество) $Y$ — **множество ответов** (выходное множество) $y(x): X \to Y$ — неизвестная **целевая функция** (зависимость) Дана **обучающая выборка** $T^m$, состоящая из **тренировочного множества** $\{x_1, x_2,\ \ldots,\ x_m\} \subset X$, для которого указаны **известные значения** функции $y_i = y(x_i)$. Необходимо найти **функцию выбора решения** $a(x): X \to Y$, которая аппроксимирует $y(x)$ на $X$. #### Описание объектов **Признак** (атрибут) объекта — отображение $f(x): X \to D_f$. Каждый объект обучающей выборки $x_i \in X$ имеет некоторый набор признаков $\left(f_1(x_i),\ \ldots,\ f_n(x_i)\right)$, который называют **признаковым описанием** объекта. Признаковые описания допустимо отождествлять с самими объектами. Множество $D = D_{f_1} \times \ldots \times D_{f_n}$ называется **признаковым пространством**. Данные обычно представлены как **матрица объектов–признаков**: $F = \lVert f_j(x_i) \rVert = \begin{pmatrix} f_1(x_1) & \ldots & f_n(x_1) \\ \ldots & \ldots & \ldots \\ f_1(x_m) & \ldots & f_n(x_m) \end{pmatrix}$ **Типы признаков** - Бинарные: $D_f = \{0, 1\}$ - Категориальные: $D_f$ — конечное множество - Упорядоченные: $D_f$ — конечное упорядоченное множество - Численные: $D_f = \mathbb{R}$ #### Виды задач для обучения с учителем - Классификация - Бинарная: $Y = \{-1, +1\}$ - Непересекающиеся классы: $Y = \{1,\ \ldots,\ M\}$ - Пересекающиеся классы: $Y = \{0, 1\}^M$ - Ранжирование * $Y$ — конечное (частично) упорядоченное множество - Регрессия * $Y = \mathbb{R}$ или $Y = \mathbb{R}^m$ #### Выбор алгоритма **Модель алгоритмов** — параметрическое семейство функций $A = \{f(x, \theta)\ |\ \theta \in \Theta\}$, в рамках которого ищется функция, приближающая целевую зависимость. Здесь $\Theta$ — множество допустимых значений параметра $\theta$ некоторой зафиксированной функции $f: X \times \Theta \to Y$. Пример: **линейная модель** с вектором параметров $\theta = (\theta_1,\ \ldots,\ \theta_n), \Theta = \mathbb{R}^n$ **Метод обучения** — отображение $\mu: (X \times Y)^m \to A$, которое по обучающей выборке данных $T^m = \{(x_i, y_i)\}$ строит алгоритм $a \in A$, восстанавливающий неизвестную зависимость ответов от объектов. Два шага: 1. **Обучение**: с помощью метода $\mu$ по обучающей выборке $T^m$ построить алгоритм $a = \mu(T^m)$ 2. **Тестирование**: применить $a$ к новым объектам $x_j$ и проверить "качество" ответов $a(x_j)$. #### Измерение качества аппроксимации **Функция потерь** $L(a, x)$ — величина ошибки алгоритма $a$ на объекте $x$. - Для задачи классификации: $L(a, x) = [a(x) \neq y(x)]$ - Для задачи регрессии: $L(a, x) = d(a(x) - y(x))$ Обычно применяется квадратичная функция потерь: $L(a, x) = (a(x) - y(x))^2$ **Эмпирический риск** — средняя ошибка, мера качества алгоритма $a$ на обучающей выборке $T^m$ $Q(a, T^m) = \frac1{m}\sum\limits_{i = 1}^{m}L(a, x_i)$ **Метод минимизации эмпирического риска** заключается в том, чтобы в заданной модели алгоритмов $A = \{a: X \to Y\}$ найти алгоритм, минимизирующий среднюю ошибку на обучающей выборке: $a = \mathrm{arg}\min\limits_{a \in A} Q(a, T^m)$ Тем самым задача обучения сводится к оптимизации и может быть решена численными методами. ### 4. :ok: Понятие переобучения и методы борьбы с ним. ###### `Презентация 1 стр.37-39` [`Викиконспекты`](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D0%B5%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5) Минимизация ошибки на обучающей выборке может привести к потере способности к обобщению. **Переобучение** (*Overfitting*) — нежелательное явление, при котором вероятность ошибки обученного алгоритма на новых объектах оказывается существенно выше, чем средняя ошибка на обучающей выборке. **Проблема переобучения** — начиная с некоторого уровня сложности модели, чем лучше алгоритм работает на данных из обучающей выборки $T^m$, тем хуже он работает на объектах реального мира. Возможные решения проблемы переобучения: - Увеличение количества данных в наборе - Уменьшение количества параметров модели - Кросс-валидация - Добавление регуляризации / увеличение коэффициента регуляризации ### 5. :mailbox_with_mail: Меры оценки качества для классификации и регрессии. > Воронцов: пр. 2, стр. 3-4 > p2: 52-58 > [habr](https://habr.com/ru/company/ods/blog/328372/) > ![](https://i.imgur.com/lVCjqzo.png) [охуенная картинка, где всё понятно (для классификации)](https://en.wikipedia.org/wiki/F1_score) ### 6. :mailbox_with_mail: Метод ближайших соседей. > p2: 11-13, 19 > [machinelearning.ru](http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B1%D0%BB%D0%B8%D0%B6%D0%B0%D0%B9%D1%88%D0%B5%D0%B3%D0%BE_%D1%81%D0%BE%D1%81%D0%B5%D0%B4%D0%B0) **Схожесть объектов** - расстояние между ними в метрическом пространстве. Примеры расстояний: * Минковского $\rho (x, y) = \left(\sum_{i} {\mid x - y\mid}^p \right)^{\frac{1}{p}}$ (при $p = 2$ - евклидово расстояние, при $p = 1$ - манхэттенское) * Махаланобиса $\rho (x, y) = \sqrt{(x - y)^\top S^{-1} (x - y)}$, где $S$ - ковариационная матрица $x$ и $y$ На вход даётся некоторая точка $u$ из метрического пространства, необходимо выдать для неё ответ $y_u$. Алгоритм: 1. Для всех точек из тренировочной выборки вычислить расстояние $\rho (u, x_i)_{i = 1 .. n}$ 2. Отсортировать эти расстояния по возрастанию: $\rho(u, x_{i_1}) \le \rho(u, x_{i_2}) \le ... \le \rho(u, x_{i_n})$ 3. Дальше 2 варианта: 3.1. Оставить токлько $k$ первых точек, до которых расстояние минимально 3.2. Отсечь все точки, которые находятся на расстоянии большем, чем окно $w$ 4. Выбрать ответ исходя из оставшихся точек (для классификации, например, выдать класс, с максимальным представлением точками) Особенности: \+ Просто написать \+ Легко интерпретировать \- Чувствителен к шуму \- Низкая эффективность \- Необходимо хранить всю тренировочную выборку ### 7. :mailbox_with_mail: Метод ядерного сглаживания (непараметрическая регрессия) > p2: 35-45 (тут плохо) > [machinelearning.ru](http://www.machinelearning.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%BF%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F) > [Воронцов (pdf): 3-5](http://www.cs.ru/voron/download/Regression.pdf) ### 8. :mailbox_with_mail: Метод градиентного спуска, усовершенствования метода градиентного спуска. > p3: 13-24 > [Воронцов (pdf): 57+](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ### 9. :mailbox_with_mail: Линейная регрессия. Линейная регрессия - задача обучения с учителем. Требуется найти линейный функционал, минимизирующий эмпирический риск. > p3: 26-32 > [Воронцов (pdf): 2, 7-8](http://www.cs.ru/voron/download/Regression.pdf) ### 10. :mailbox_with_mail: Сингулярное разложение векторов. ![](https://i.imgur.com/YXeyNn3.png) > p3: 29-32 > [Воронцов (pdf): 9](http://www.cs.ru/voron/download/Regression.pdf) ### 11. :mailbox_with_mail: Метод опорных векторов для линейно разделимой выборки. > [williamspublishing.com: 1-3, 14-16](http://www.williamspublishing.com/PDF/978-5-9500296-2-2/part.pdf) > [Воронцов (pdf): 67+](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ### 12. :mailbox_with_mail: Ядра и ядерный трюк в методе опорных векторов. > [williamspublishing.com: 19-22](http://www.williamspublishing.com/PDF/978-5-9500296-2-2/part.pdf) (тяжко, но достаточно полная информация) > [Воронцов (pdf): 73+](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ### 13. :mailbox_with_mail: Вероятностная постановка задачи классификациии оптимальный байесовский классификатор. > [Воронцов (pdf): 18-21](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ### 14. :mailbox_with_mail: Непараметрический метод оценки плотности. > [Воронцов (pdf): 22+](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ### 15. :mailbox_with_no_mail: Параметрический метод оценки плотности и метод максимального правдоподобия. >Метод максимального правдоподобия, [видос](https://www.youtube.com/watch?v=RPtYRm2tboA) Вместо существования неизвестной целевой зависимости $y^∗(x)$ предположим существование неизвестного вероятностного распределения на множестве $X × Y$ с плотностью $p(x, y)$, из которого случайно и независимо выбираются $ℓ$ наблюдений $X^ℓ = (x_i, y_i)_{i=1}^ℓ$ Такие выборки называются простыми или случайными одинаково распределёнными (independent identically distributed, i.i.d.). При вероятностной постановке задачи вместо модели алгоритмов $g(x, θ)$, аппроксимирующей неизвестную зависимость $y^∗(x)$, задаётся модель совместной плотности распределения объектов и ответов $ϕ(x, y, θ)$, аппроксимирующая неизвестную плотность $p(x, y)$. Затем определяется значение параметра $θ$, при котором выборка данных $X^ℓ$ максимально правдоподобна, то есть наилучшим образом согласуется с моделью плотности. Если наблюдения в выборке $X^ℓ$ независимы, то совместная плотность распределения всех наблюдений равна произведению плотностей $p(x, y)$ в каждом наблюдении: $p(X^ℓ) = p(x^1, y^1), . . . ,(x^ℓ, y^ℓ) = p(x^1, y^1)· · ·p(x^ℓ, y^ℓ)$. Подставляя вместо $p(x, y)$ модель плотности $ϕ(x, y, θ)$, получаем функцию правдоподобия (likelihood): $L(θ, X^ℓ) = \prod_{i=1}^ℓϕ(x^i, y^i, θ)$ Больше - лучше. Проларифмируем чтобы не подливиться при производных и давай считать ### 16. :mailbox_with_mail: Логистическая регрессия. > [Воронцов (pdf): 62+](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ![](https://i.imgur.com/GdSV0wa.png) ![](https://i.imgur.com/Qa3WJhe.png) ### 17. :mailbox_with_no_mail: Логические правила и вывод закономерностей. > p6 с начала ![](https://i.imgur.com/TUz1l7R.png) p - true positive; n - false positive ![](https://i.imgur.com/4JDt5yD.png) Про вывод хз. ### 18. :mailbox_with_no_mail: Деревья принятия решений. ### 19. :mailbox_with_no_mail: Задача бустинга и градиентный бустинг. ### 20. :mailbox_with_mail: AdaBoost и его теоретические свойства. > [neerc wiki](http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%83%D1%81%D1%82%D0%B8%D0%BD%D0%B3,_AdaBoost) > [Воронцов2 (pdf) 4](http://www.machinelearning.ru/wiki/images/archive/c/cd/20110320194858%21Voron-ML-Compositions-slides.pdf) ![](https://i.imgur.com/u0SVsl6.png) ### 21. :mailbox_with_no_mail: Случайный лес и стэкинг. ### 22. :mailbox_with_no_mail: Нейрон Маккалока-Питтса, выразительная мощность нейрона. > [machinelearning.ru](http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C_%D0%9C%D0%B0%D0%BA%D0%9A%D0%B0%D0%BB%D0%BB%D0%BE%D0%BA%D0%B0-%D0%9F%D0%B8%D1%82%D1%82%D1%81%D0%B0) > Мощность: через нейрон с пороговой функцией можно выразить И, ИЛИ и НЕ. Значит, можно выразить вообще все логические функции от n аргументов. (На самом деле не через нейрон, а через сеть с 2 слоями). А с 3 - и аппроксимировать любые непрерывные функции. > …модель МакКаллока-Питтса эквивалентна пороговому линейному классификатору. ![](https://i.imgur.com/gP61fcQ.png) Конкретно у этих двух личностей фи — пороговая функция (т.е. f(x)=[z≥0]) ### 23. :mailbox_with_no_mail: Многослойная нейронная сеть и алгоритм обратного распространения ошибок. > [machinelearning.ru slides](http://www.machinelearning.ru/wiki/images/3/38/Voron-ML-NeuralNets1-2018-slides.pdf) > Вкратце — ошибка вычисляется на выходном слое, по ним вычисляются ошибки на предыдущем. Повторить. ### 24. :mailbox_with_no_mail: Декомпозиция обратного распространения ошибок. Граф вычислений для глубокой нейронной сети. ### 25. :mailbox_with_no_mail: Аугментация данных, дропаут и активационные функции для глубоких нейронных сетей. https://habr.com/en/company/wunderfund/blog/330814/ Аугментация - добавить измененные входные данные чтобы не размечать новые. Дропаут - слой в nn в котором в рандомный момент вырубаются нейроны. Гугл пользует чтоюы не оверфитаться. Активационные функции - relu, сигмоида, tanh, softputs ( $ln(1+e^x)$, хз зачем, никто не пользуется) ### 26. :mailbox_with_no_mail: Методы второго порядка и их применение в логистической регрессии. > p8: 4-15 > [machinelearning.ru](http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BA%D0%B0%D1%81%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%28%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0-%D0%A0%D0%B0%D1%84%D1%81%D0%BE%D0%BD%D0%B0%29) > [Воронцов (pdf)](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ### 27. :mailbox_with_no_mail: Предобработка данных для глубоких нейронных сетей, инициализация Xavier и He. > [habr](https://habr.com/ru/company/wunderfund/blog/315476/) ![](https://i.imgur.com/hGgtwvX.jpg) #### Xavier и He Мем в чем, мы все равно берем в начале рандомные веса, и сойдутся они не раньше чем ты к псж. Вот эти два умных дяденьки говорят что если у тебя функция активации симметрична (или сигмоид, она на [-1,+1] норм) то надо брать не рандомные веса, а веса с дисперсией $\mathrm{Var}(W) = {2 \over{n_{in} + n_{out}}}$ (Xavier) или $\mathrm{Var}(W) = {2 \over{n_{in}}}$(He) (это для ReLU) $n_{in}$ и $n_{out}$ — количества нейронов в предыдущем и последующем слоях соответственно. ### 28. :mailbox_with_no_mail: Проблемы градиентного спуска. Улучшенные методы оптимизации: Momentum, Nesterov accelerated gradient. >[habr](https://habr.com/en/post/318970) Раз мы куда-то шли по градиенту, возможно в будущем нам стоит двигаться тоже туда же. Запоминать все последние дорога поэтому тупа храним экспоненциальное скользящее среднее ![](https://i.imgur.com/qOQtsuS.png) Гамму беру 0.9. Меньше гамма - меньше смысла Нестеров получается, если вычислять сам градиент в точке после прибавки момента. ### 29. :mailbox_with_no_mail: Проблемы градиентного спуска. Улучшенные методы оптимизации: Adagrade, RMSProp, Adadelta. >[habr](https://habr.com/en/post/318970) >Переведите ебаные пикчи в инлайн плес, я умираю Adagrade - адаптивный градиент ![](https://i.imgur.com/xnZce0h.png) ![](https://i.imgur.com/EFwIibI.png) RMSProp — root mean square propagation ![](https://i.imgur.com/CEnBNQV.png) ![](https://i.imgur.com/M4mS4sW.png) Adadelta Если ![](https://i.imgur.com/1xWsYCt.png) то Adadelta от RMSProp отличается тем, что мы добавляем в числитель стабилизирующий член пропорциональный $RMS$ от $\Delta\theta_t$. На шаге $t$ мы ещё не знаем значение $RMS[\Delta \theta]_{t}$, поэтому обновление параметров происходит в три этапа, а не в два: сначала накапливаем квадрат градиента, затем обновляем $\theta$, после чего обновляем $RMS[\Delta \theta]$. ![](https://i.imgur.com/yMokBOq.png) ![](https://i.imgur.com/mAYDbVq.png) ![](https://i.imgur.com/TqI48qj.png) ![](https://i.imgur.com/4Iwlzu6.png) ### 30. :mailbox_with_no_mail: Проблемы градиентного спуска. Улучшенные методы оптимизации: Adam. >[habr](https://habr.com/en/post/318970) ### 31. :mailbox_with_no_mail: Батчевая нормализация. Мы умеем делать нормализацию входных данных, но в скрытых слоях вход с прошлого слоя может разбалансироваться и это плохо. Поэтому мы вставляем новый слой, который во время тренировки считает среднее и дисперсию всех входов, и отдает нормализованные входы. Во время предсказания он нормализует с помощью тех значений, которые получил в тренировке. >[Статья про пизданутый билет](https://towardsdatascience.com/batch-normalization-theory-and-how-to-use-it-with-tensorflow-1892ca0173ad) ![](https://i.imgur.com/qfe5icZ.png) ![](https://i.imgur.com/OH2VeOx.png) ![](https://i.imgur.com/NPavp01.png) ### 32. :mailbox_with_no_mail: Сверточные сети: понятие свертки, паддинга, пулинга, страйда. > [Паруске с гифками](https://neurohive.io/ru/osnovy-data-science/glubokaya-svertochnaja-nejronnaja-set/) > [На бусурманском](http://cs231n.github.io/convolutional-networks/#conv) ### 33. :mailbox_with_no_mail: Сверточные сети: идея, архитектура и алгоритм обучения. http://cs231n.github.io/convolutional-networks/#architectures ### 34. :mailbox_with_no_mail: Задачи семантической сегментации и детекции объектов. Примеры современных решений. >[что-то тут](https://towardsdatascience.com/r-cnn-fast-r-cnn-faster-r-cnn-yolo-object-detection-algorithms-36d53571365e) <details> <summary><b>Оригинальная паста</b></summary> Бля, чет так проорал. Открыл слайды, а там просто скрины из статьей известных архитктур для object detection. Well played. Хороший курс! Ну, короче, [R-CNN](https://habr.com/ru/post/421299/), YOLO и U-Net, рисуете модельки как в презенташке и махаете руками, как он махал (если он махал вообще). </details> #### The U-Net The so-called “fully convolutional network”. <details> <summary><b>Соль</b></summary> Сеть содержит сжимающий путь (слева) и расширяющий путь (справа), поэтому архитектура похожа на букву U, что и отражено в названии. На каждом шаге мы удваиваем количество каналов признаков. Сжимающий путь похож на типичную свёрточную сеть, он содержит два подряд свёрточных слоя 3x3, после которых идет слой ReLU и пулинг с функцией максимума 2×2 с шагом 2. Каждый шаг расширяющего пути содержит слой, обратный пулингу, который расширяет карту признаков, после которого следует свертка 2x2, которая уменьшает количество каналов признаков. После идет конкатенация с соответствующем образом обрезанной картой признаков из сжимающего пути и две свертки 3x3, после каждой из которой идет ReLU. Обрезка нужна из-за того, что мы теряем пограничные пиксели в каждой свертке. На последнем слое свертка 1x1 используется для приведения каждого 64-компонентного вектора признаков до требуемого количества классов. Всего сеть имеет 23 свёрточных слоя. ![](https://i.imgur.com/dyHT0aW.png) There are many applications of U-Net in biomedical image segmentation, such as brain image segmentation (''BRATS'') and liver image segmentation ("siliver07"). </details> #### R-CNN Use selective search to extract just 2000 regions from the image and he called them region proposals. Therefore, now, instead of trying to classify a huge number of regions, you can just work with 2000 regions. <details> <summary><b>Соль</b></summary> These 2000 region proposals are generated using the selective search algorithm which is written below. 1. Generate initial sub-segmentation, we generate many candidate regions 2. Use greedy algorithm to recursively combine similar regions into larger ones 3. Use the generated regions to produce the final candidate region proposals ![](https://i.imgur.com/TIgT8Bn.png) 2000 candidate region proposals are warped into a square and fed into a convolutional neural network that produces a 4096-dimensional feature vector as output </details> #### YOLO - You Only Look Once In YOLO a single convolutional network predicts the bounding boxes and the class probabilities for these boxes. <details> <summary><b>Соль</b></summary> ![](https://cdn-images-1.medium.com/max/800/1*JniWRt-ceWLNlkOULjhdpg.png) How YOLO works is that we take an image and split it into an SxS grid, within each of the grid we take m bounding boxes. For each of the bounding box, the network outputs a class probability and offset values for the bounding box. The bounding boxes having the class probability above a threshold value is selected and used to locate the object within the image. The limitation of YOLO algorithm is that it struggles with small objects within the image, for example it might have difficulties in detecting a flock of birds. This is due to the spatial constraints of the algorithm. </details> ### 35. :mailbox_with_no_mail: Обработка последовательностей в машинном обучении. Рекуррентные сети: идея, архитектура и алгоритм обучения. ### 36. :mailbox_with_no_mail: Глубокие сети с памятью: идея, архитектура и алгоритм обучения. [Хабр](https://habr.com/ru/company/wunderfund/blog/331310/) ### 37. :mailbox_with_no_mail: Классификация рекуррентных сетей. Двунаправленные рекуррентные сети и глубокие рекуррентные сети: архитектура и алгоритм обучения. ### 38. :mailbox_with_no_mail: Механизм внимания в рекуррентных сетях: принцип, архитектура и алгоритм обучение. Классическая RNN читает вход и складывает что-то в своё состояние (фиксированного размера). Однако зачастую на каждом этапе генерации вывода нас гораздо больше интересует некоторая часть входа больше, чем другая. Собственно, мы хотим "обратить внимание" на некоторые состояния (на разных этапах разные). **Как** Генерируем матрицу внимания A (n×m). Каждый элемент матрицы α~ij~ является коэффицентом, с которым учитывается состояние на i-том входе для j-того выхода (по сути мы подаём преобразованное состояние как вход). **Но как её генерить?** Сумма всех α~sj~ (по всем s) должна быть равна 1. \begin{equation}α_{ij} = \frac{exp(score(h_t, h_s))}{Σ_{s'}(exp(score(h_t, h_{s'})))}\end{equation} где h~s~ — состояние после s-ого входа, h~t~ — состояние на генерации t-того выхода, score — некая волшебная функция. `(В другом источнике предлагается в скор пихать вместо состояния после s-ого входа значение на этом входе).` То, что мы подаём на вход при генерации — context vector — считается как $C(t)=Σ_{s}α_{st}h_s$. В презентации предлагается вбрасывать на вход не сам context vector, а attention vector $a(t)=tgh(W_c[c_h;h_t])$. (что такое W — непонятно) <!-- Есть RNN, она читает последовательности и по тихому складывает их в стейт. Отлично. Но всё хуйня собачья, если нам надо поиметь влияние от более важных частей. Так, например, при машинном переводе при помощи RNN первое слово успешно проёбывается в **очень** длинных предложениях. Хорошо, можно поюзать память. Чуть более интересен общий случай — нас интересует то, о чём идёт речь, и что об этом хотели сказать; это можно находить. Собственно весь механизм внимания работает как некий набор коэффицентов для всей истории скрытого состояния. У нас есть __специально обученная штука__ (например, ещё одна маленькая нейросеть, вообще не важно), которая превращает предыдущий стейт и текущий токен в некий "вес". Отлично; дочитываем данные и начинаем выдавать ответ. Однако вместо унылого разворачивания маленького скрытого состояния мы ебашим серию (все при мягкой модели, самые топовые при жёсткой) старых состояний, сложенных с весами. Таким образом, правильная расстановка акцентов позволяет игнорировать всякий мусор и внимательно следить за важными вещами. Важно понимать, что веса генерятся каждый ход, т.е. матрица весов будет размера n×m, где n — длина входа, m — выхода. Как?--> ### 39. :mailbox_with_no_mail: Векторные представления слов. Word2Vec. Векторное представление — общее название для различных подходов к моделированию языка и обучению представлений в обработке естественного языка, направленных на сопоставление словам (и, возможно, фразам) из некоторого словаря векторов из значительно меньшего количества слов в словаре. Для этого используют нейронные сети , методы понижения размерности в применении к матрицам совместных упоминаний слов (word co-occurrence matrices) и явные представления, обучающиеся на контекстах упоминаний слов (explicit representations). Матрица совместного встречания - матрица, в которой отображается как часто одна сущность(как правило слово, но не обязательно) встречается в одном контексте с другой сущностью(опять же, скорее всего, словом). Легко придумать, как это круто использовать для анализа тональности текста. Word2vec - made in Google. word2vec принимает большой текстовый корпус в качестве входных данных и сопоставляет каждому слову вектор, выдавая координаты слов на выходе. Сначала он создает словарь, «обучаясь» на входных текстовых данных, а затем вычисляет векторное представление слов. Векторное представление основывается на контекстной близости: слова, встречающиеся в тексте рядом с одинаковыми словами (а следовательно, имеющие схожий смысл), в векторном представлении будут иметь близкие координаты векторов-слов. В word2vec существуют два основных алгоритма обучения : CBOW (Continuous Bag of Words) и Skip-gram. CBOW — «непрерывный мешок со словами» модельная архитектура, которая предсказывает текущее слово, исходя из окружающего его контекста. Архитектура типа Skip-gram действует иначе: она использует текущее слово, чтобы предугадывать окружающие его слова Полученные векторы-слова могут быть использованы для обработки естественного языка и машинного обучения. Получаемые на выходе координатные представления векторов-слов позволяют вычислять «семантическое расстояние» между словами. ### 40. :mailbox_with_no_mail: Задача кластеризации. Меры оценки. >в слайдах опять ничего нет. Воронцов: ![](https://i.imgur.com/PiWptzb.png) ![](https://i.imgur.com/GXsAqYH.png) ### 41. :mailbox_with_no_mail: Задача кластеризации. Графовые алгоритмы. > Суть в том что каждый объект это вершина, а ребро это расстояние между объектами. В слайдах после этого какое-то говно идет. С хабра: Графовое представление крутое потому что наглядно и все понятно **Алгоритм минимального покрывающего дерева** - построили остов и удаляем ребра с наибольшим весом. Сколько кластеров надо столько ребер и удаляем **Алгоритм выделения связных компонент** - подобрали R и ебнули ребра у которых вес больше R. Получили кластера. ### 42. :mailbox_with_no_mail: Задача кластеризации. Иерархические алгоритмы. [Воронцов 122+](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf) ### 43. :mailbox_with_no_mail: Задача кластеризации. Алгоритм k-Means. >Во-первых хабр https://habr.com/ru/post/67078/ В двух словах: Фиксируем число кластеров - выбираем рандомно центройды - Xдля каждого элемента в векторе по минимизации среднеквадратичного отклонения находим нужный центройд - для каждого кластера пытаемся выбрать новый центройд - повторяем с X пока центройды не меняются ### 44. :mailbox_with_no_mail: Задача кластеризации. Плотностные алгоритмы. ### 45. :mailbox_with_no_mail: Задача уменьшения размерности. Фильтрующие методы выбора признаков. Зачем отбирать фичи: 1. Долгая работа классификатора 2. Много памяти 3. Падение точности предсказания Фильтрующие методы выбора признаков тупа используют статистические методы и выкидывают признаки которые говно: 1. Хи-квадрат 2. Информейшен гейн 3. Коэффициент корреляции Спирмена ### 46. :mailbox_with_no_mail: Задача уменьшения размерности. Алгоритмы-обертки и встроенные методы. Алгоритмы-обертки. Суть: тренируемся на сете фичей и добавляем\удаляем фичи. Пример - SVM-RFE: 0. Выбрали количество фичей которое должно остаться. 1. Тренируем SVM. 2. Ранжируем фичи. 3. Выкидываем плохие. 4. Повторяем пока 0 не сатисфаед Встроенные методы называются встроенными потому что этап отбора фичей происходит прямо во время обучения классификатора. Примеры: Л1 регуляризация и дерево решений ### 47. :mailbox_with_no_mail: Задача уменьшения размерности. Алгоритм PCA. http://www.cs.ru/voron/download/Regression.pdf 1.3.8 **Задача:** есть $n$ исходных числовых признаков $f_1(x),\ldots ,f_n(x)$ и нам нужно получить $m\leqslant n$ новых числовых признаков $g_1(x),\ldots , g_m(x)$, которые будут содержать всю информацию о старых признаках. Старые признаки должны восстанавливаться из новых. Метод главных компонент подразумевает, что старые признаки линейно восстанавливаются по новым: \begin{align*} \stackrel{\wedge}{f}_j(x) = \sum\limits_{s=1}^m g_s(x)u_{js}, j = 1,\ldots,n, \forall x \in X \end{align*} Для удобства решения задачи рассмотрим ее в матричном виде: \begin{align*} F_{l\times n} = \begin{pmatrix}f_1(x_1) & \ldots & f_n(x_1) \\ \ldots & \ldots & \ldots \\ f_1(x_l) & \ldots & f_n(x_l)\end{pmatrix};\ \ G_{l\times m} = \begin{pmatrix}g_1(x_1) & \ldots & g_m(x_1) \\ \ldots & \ldots & \ldots \\ g_1(x_l) & \ldots & g_m(x_l)\end{pmatrix} \end{align*} где $F$ и $G$ -- матрицы "объекты-признаки" Нам нужна матрица линейного преобразования новых признаков в старые: \begin{align*} U_{n\times m} = \begin{pmatrix}u_{11} & \ldots & u_{1m}\\ \ldots & \ldots & \ldots \\ u_{n1} & \ldots & u_{nm}\end{pmatrix} \\ \ \stackrel{\wedge}{F} = GU^T\ и\ хотим,\ чтобы\ \stackrel{\wedge}{F}\approx F \end{align*} Для того чтобы получить это, нужно решить задаку наименьших квадратов, как обычно, как и везде. Для этого есть теорема МГК: Если $m \leqslant rk F$, то минимум $||GU^T - F||^2$ достигается, когда столбцы $U$ -- это собственные значения $F^TF$: $\lambda_1,\ldots ,\lambda_m$, а матрица $G = FU$. При этом: * матрица $U$ -- ортонормирована: $U^TU=I_m;$ * матрица $G$ -- ортогональна: $G^TG = \Lambda = \textrm{diag}(\lambda_1, \ldots, \lambda_m);$ * $U\Lambda = F^TFU;\ G\Lambda = FF^TG;$ * $||GU^T - F||^2 = ||F||^2 - tr\Lambda = \sum\limits_{j=m+1}^{n}\lambda_j.$ ### 48. :mailbox_with_no_mail: Задача уменьшения размерности. Алгоритм tSNE. http://datareview.info/article/algoritm-t-sne-illyustrirovannyiy-vvodnyiy-kurs/ Посчитаем сходство двух исходных точек как если бы одна из них - центр распределения Гаусса, а вторая - семпл из распределения. Точно так же посчитаем сходство двух точек отображения, но с распределением Стьюдента. Сделаем матрицы сходства у исходного и у отображения. Будем менять отображение так, чтобы матрицы стали похожими. Формулы - в статье. ### 49. :mailbox_with_no_mail: Задача уменьшения размерности. Автоэнкоды. Автоэнкодер - два алгоритма, тренирующиеся друг на друге - один сужает размерность данных, второй восстанавливает. Например, делаем нейросетку с большим числом входов, числом нейронов больше по краям и маленьким в середине, и учим выдавать похожее на исходное данные. Половина с уменьшением кол-ва нейронов = энкодер, половина с увеличением - декодер. ![](https://i.imgur.com/IHKRY07.png) ### 50. :mailbox_with_no_mail: Алгоритм Expectation minimization. > https://www.youtube.com/watch?v=iQoXFmbXRJA > ![](https://i.imgur.com/Vqe0iRU.png) ![](https://i.imgur.com/5VjASzj.png) TL;DR возьмем 2 случайных распределения, посчитаем насколько они "захватывают" точки ($b_i$ для синего), потом сделаем вид что распределений небыло и востановим их (посчитаем матожидаение и дисперсию) и будем повторять пока не надоест ### 51. :mailbox_with_no_mail: Задача и алгоритмы частичного обучения. >[воронцов](http://www.machinelearning.ru/wiki/images/archive/9/9f/20120508133039%21Voron-ML-SSL.pdf) ### 52. :mailbox_with_no_mail: Задача и алгоритмы активного обучения. >[воронцов](http://www.machinelearning.ru/wiki/images/6/6b/Voron-ML-AL-slides.pdf) ### 53. :mailbox_with_no_mail: Задача и алгоритмы сэмплирования. Сэмплирование – берем подмножество $X$ чтобы выявить некоторые свойства $X$. Например математического ожидания сложных вероятностных распределений для которых данный инеграл не может быть подсчитан аналитическим методом из-за сложности $p(z)$: $E[f]=\int f(z)p(z) dz$ Однако, можно подсчитать значение $p(z)$ в любой точке $z$. Основная идея заключается в создании незавсимой выборки $z^{(l)} (где l=1,...,L)$ из распределения $p(z)$. Это позволит оцениваемое математическое ожидание приблизить конечной суммой $\hat f=\frac{1}{L}\sum_{l=1}^{L} f(z^{(l)})$ Существует несколько методов сэмплирования для создания выборки $z^{(l)}$ * Simple random sampling; * Systematic sampling; * Rejection sampling; * Adaptive rejection sampling. ### 54. :mailbox_with_no_mail: Задача и алгоритмы обучения с первого взгляда. Обучение со сверхмалым количеством примеров (в пределе одним). e.g. показать ему студента с FX а потом спрашивать для кажого студента - is that a fx? ### 55. :mailbox_with_no_mail: Задача и алгоритмы поиска аномалий и удаления шумов. >[туть](https://dyakonov.org/2017/04/19/%D0%BF%D0%BE%D0%B8%D1%81%D0%BA-%D0%B0%D0%BD%D0%BE%D0%BC%D0%B0%D0%BB%D0%B8%D0%B9-anomaly-detection/) <details> <summary><b>Картинка</b></summary> <img src="https://i.imgur.com/2QWYFCg.png"/> </details> Шум — это выброс «в слабом смысле» (он может немного размывать границы класса/кластера). Нас же интересуют, прежде всего, выбросы «в сильном смысле», которые искажают эти границы. * Статистические тесты - отлавливать большое отклонение от среднего: <details> <summary><b>Картинка</b></summary> <img src="https://i.imgur.com/vvjb7WM.png"> </details> * Модельные тесты Строим модель, которая описывает данные. Точки на которых модель сильно ошибается - аномалии * Итерационные методы Для $R^n$ можно удалять выпуклую оболочку <details> <summary><b>Картинка</b></summary> <img src="https://i.imgur.com/bxtdfEX.png"> </details> В пространстве студентов отчислять самых неуспешных * Метрические методы Выкидываем то, у чего мало соседий. Получил 5 по мл? соре, ты аномалия, уходи <details> <summary><b>Картинка</b></summary> <img src="https://i.imgur.com/25JLWRv.png"> </details> Здесь используются специфические метрики, например расстояние Махалонобиса. ### 56. :mailbox_with_no_mail: Задача генерации объектов. PixelCNN и PixelRNN: идея, архитектура и алгоритм обучения. ### 57. :mailbox_with_mail: Генеративные противоборствующие сети: идея, архитектура и алгоритм обучения. [neerc wiki](http://neerc.ifmo.ru/wiki/index.php?title=Generative_Adversarial_Nets_(GAN)) ### 58. :mailbox_with_mail: СGAN и DCGAN: идея, архитектура и алгоритм обучения. https://arxiv.org/pdf/1511.06434.pdf -- DCGAN (GAN на сверточных слоях) https://arxiv.org/pdf/1411.1784.pdf -- CGAN (к шуму прибавляем one-hot вектор, чтобы регулировать класс)