Билет 1
Виды обучения с учителем (supervised), без учителя (unsupervised), частичное (semi-supervised), трансдуктивное. Типы моделей: генеративные, дискриминативные. Типы признаков и типы откликов. Принцип минимизации эмпирического риска. Переобучение, её зависимость от размера обучающей выборки и сложности модели. Кросс-валидация и A/B тестирование. Дискриминантные функции. Признаковое представление документов - бинарное, TF, TF-IDF.
| Сергей Иванов: Частичный и трансдуктивный вид обучения можно описать в статье о задаче машинного обучения в целом. Если по типам моделей мало информации, их можно объединить в одну статью, а ссылки дать на разделы (как это сделать?). Типы признаков и типы откликов, наверное, есть часть статьи о генеративной модели, если так, ссылку надо также сделать на раздел. A/B тестирование, наверное, подраздел статьи о кросс-валидации. |
Билет 2
Метод k ближайших соседей. Проклятие размерности. Метрики: , косинусная, Жаккарда. Декоррелирующее преобразование (whitening) и расстояние, которое оно порождает. Взвешенный учёт объектов. Пример весов. Отступ и классификация объектов на выбросы, пограничные, типичные, эталонные. Методы фильтрации обучающей выборки для ускорения работы метода.
| Сергей Иванов: Взвешенный учёт объектов скорее всего пойдёт как подраздел kNN-а. Про отступ отдельная статья, "классификация объектов" по отступу туда же как раздел. |
Билет 3
Идея алгоритма оптимизации метода ближайших соседей через структурирование пространства признаков - KD-деревья и ball-деревья. Нахождение расстояния от точки до гиперпрямоугольника и до шара.
| Сергей Иванов: Про расстояние от точки до шара - подраздел ball-деревьев. Про ball-tree и KD-tree в зависимости от объёма информации можно отдельные статьи, а можно подразделы структурирования пространства признаков (в этой общей статье идеи и цели этих методов + навигационные ссылки) |
Билет 4
Задача снижения размерности. Метод главных компонент - 2 определения (через проекции и отклонения), их эквивалентность. Оценка качества аппроксимации отдельной компонентой и первыми компонентами.
| Сергей Иванов: Задача снижения размерности - отдельная статья. Остальное по разделам можно в одну статью по методу главных компонент, здесь ссылки на разделы. Причём надо смотреть по сторонам, билет 5 тоже содержится в этой статье (?) |
Билет 5
Метод главных компонент — определение и итеративный алгоритм их построения. Доказательство, что итеративный алгоритм действительно даёт главные компоненты (полученные компоненты соотв. определению).
| Сергей Иванов: Внимание, опасность коллизии с билетом №4! |
Билет 6
Сингулярное разложение (SVD) — определение. Его связь с главными компонентами. Сокращённое сингулярное разложение порядка , критерий выбора . Определить и доказать оптимальность аппроксимации сокращённого сингулярного разложения с точки зрения нормы Фробениуса. Применения сингулярного разложения.
Билет 7
Определение решающего дерева. Для решающих деревьев CART: выбор решающего правила в каждом узле для случая классификации/регрессии. Назначение прогнозов узлам дерева в случае регрессии/классификации, симметричных/несимметричных потерь.
Билет 8
Определение решающего дерева. Правила (прим. — в билетах тут какая-то опечатка) и критерии остановки наращивания дерева. Обрезка (pruning) для решающих деревьев CART.
Билет 9
Оценка классификаторов. Матрица ошибок. Точность, полнота, F-мера, ROC-кривая, мера AUC. ROC-кривая для случайного назначения классов. Меры, оценивающие, насколько хорошо классификатор предсказывает вероятности классов.
Билет 10
Линейный классификатор. Отступ (margin) и его интуиция. Оптимизационная задача по настройке весов. Основные функции потерь. Метод градиентного спуска и метод стохастического градиента.
Билет 11
и регуляризация. Какая из них отбирает признаки и почему? Связь минимизации эмпирического риска и принципа максимума правдоподобия. Чему в методе максимального правдоподобия соответствует регуляризация? Вероятностная модель, соответствующая и регуляризации.
Билет 12
Определение логистической регрессии через вероятности классов. Какой функции потерь она соответствует? Многомерная логистическая регрессия. Функция soft-max.
Билет 13
Метод опорных векторов в линейно разделимом и линейно неразделимом случае. Его вывод геометрически. Какой функции потерь и регуляризации он соответствует? Классификация типов объектов в методе опорных векторов.
Билет 14
Обобщение методов машинного обучения через ядра. Теорема Мерсера. Операции, не выводящие из класса ядер. Линейное, полиномиальное и RBF-ядро - формулы и доказательства, что это действительно ядра. Определение расстояние через ядра.
Билет 15
Решение для метода опорных векторов - исходное (с выводом) и его обобщение через ядра
| Сергей Иванов: По идеи, это можно вставить как часть статьи об SVM и дать тут ссылку на раздел |
Билет 16
Решение для метода гребневой регрессии - исходное и обобщённое через ядра (с выводом)
| Сергей Иванов: см. комментарий к предыдущему билету |
Билет 17
Матрица штрафов (cost matrix). Байесовское правило минимальной цены. Его упрощение для случая одинаковых штрафов для ошибок на одном классе. Его упрощение для случая единичной матрицы штрафов. Доказать, что последнее упрощение приведёт к минимизации числа ошибок классификации.
| Сергей Иванов: Про матрицу штрафов статья отдельная будет, про байесовское правило на неё просто ссылка. |
Билет 18
Гауссов классификатор. Сколько параметров имеет этот метод и какие модельные ограничения используются для снижения числа параметров? Доказать, что граница между классами будет квадратичной в общем случае и линейной при предположении одинаковых внутриклассовых ковариционных матриц.
Билет 19
Модель Бернулли и мультиномиальная модель классификации. Являются ли они линейными классификаторами? Сглаживание вероятностей Лапласа. Предположение "наивного Байеса". Как оно работает в случае моделей Бернулли, мультиномиальной и Гауссова классификатора?
Билет 20
Ядерное сглаживание для оценки плотности. Виды ядер в одномерном и многомерном случае. Выбор параметра ширины окна (bandwidth). Метод Парзеновского окна. Какому методу оценки плотности соответствует метод k ближайших соседей?
Билет 21
Регрессия. Вывод решения для обычной и гребневой регрессии. LASSO и ElasticNet регрессия. Какие регуляризации могут отбирать признаки? Взвешенный учёт наблюдений. Алгоритм робастной регрессии. Регрессия Надарая-Ватсона.
Билет 22
Сравнение методов классификации: ближайших соседей, логистическая регрессия с регуляризацией, дерево решений, метод опорных векторов с линейным и RBF-ядром, байесовское правило калссификации с оценкой плотности - Гауссовой и ядерным сглаживанием (метод Парзеновского окна). Какие методы подвёрнуты (прим. - возможно, имелось в виду "подвергнуты"...) проклятию размерности? Какие методы всегда дают линейные границы между классами? Какие методы используют не все объекты для прогнозирования? Насколько методы устойчивы к выбросам? Сравните вычислительную трудоёмкость на этапе прогнозирования.
| Сергей Иванов: Содержимое этого билета с навигационными ссылками имеет смысл оформить в статье "Задача классификации" в виде таблички с ответами (возможно, комментариями) и, наверное, ссылками на другие статьи. |
Билет 23
Сравнение методов регрессии: ближайших соседей, регрессия Надарая-Ватсона, линейная регрессия с регуляризацией, решающее дерево, робастная регрессия, гребневая (ridge) регрессия с RBF-ядром. Прогноз каких методов зависит линейно от исходных признаков? Какие методы используют не все объекты для прогнозирования? Какие методы используют не все признаки для прогнозирования? Насколько методы устойчивы к выбросам? Сравните вычислительную трудоёмкость на этапе прогнозирования.
| Сергей Иванов:: см. примечание к билету №22 |