Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы

Материал из MachineLearning.

Версия 06:17, 24 июня 2010

Основная статья: Машинное обучение (курс лекций, К.В.Воронцов)

Данная страница содержит вопросы к устному экзамену по учебному курсу К. В. Воронцова «Машинное обучение».

Первый семестр

Байесовская классификация

• Записать общую формулу байесовского классификатора (надо помнить формулу).
• Какие вы знаете три подхода к восстановлению плотности распределения по выборке?
• Что такое наивный байесовский классификатор?
• Что такое оценка плотности Парзена-Розенблатта (надо помнить формулу). Выписать формулу алгоритма классификации в методе парзеновского окна.
• На что влияет ширина окна, а на что вид ядра в методе парзеновского окна?
• Многомерное нормальное распределение (надо помнить формулу). Вывести формулу квадратичного дискриминанта. При каком условии он становится линейным?
• На каких предположениях осован линейный дискриминант Фишера?
• Что такое «проблема мультиколлинеарности», в каких задачах и при использовании каких алгоритмов она возникает? Какие есть подходы к её решению?
• Что такое «смесь распределений» (надо помнить формулу)?
• Что такое ЕМ-алгоритм, какова его основная идея? Какая задача решается на Е-шаге, на М-шаге? Каков вероятностный смысл скрытых переменных?
• Последовательное добавление компонент в ЕМ-алгоритме, основная идея алгоритма.
• Что такое стохастический ЕМ-алгоритм, какова основная идея? В чём его преимущество (какой недостаток стандартного ЕМ-алгоритма он устраняет)?
• Что такое сеть радиальных базисных функций?
• Что такое «выбросы»? Как осуществляется фильтрация выбросов?

Метрическая классификация

• Что такое обобщённый алгоритм классификации (надо помнить формулу)? Какие вы знаете частные случаи?
• Как определяется понятие отступа в метрических алгоритмах классификации?
• Что такое окно переменной ширины, в каких случаях его стоит использовать?
• Что такое метод потенциальных функций? Идея алгоритма настройки. Сравните с методом радиальных базисных функций.
• Зачем нужен отбор опорных объектов в метрических алгоритмах классификации?
• Основная идея алгоритма СТОЛП.
• Что такое функция конкурентного сходства? Основная идея алгоритма FRiS-СТОЛП.
• Приведите пример метрического алгоритма классификации, который одновременно является байесовским классификатором.
• Приведите пример метрического алгоритма классификации, который одновременно является линейным классификатором.

Линейная классификация

• Что такое модель МакКаллока-Питтса (надо помнить формулу)?
• Метод стохастического градиента. Расписать градиентный шаг для квадратичной функции потерь и сигмоидной функции активации.
• Недостатки метода SG и как с ними бороться?
• Что такое линейный адаптивный элемент ADALINE?
• Что такое правило Хэбба?
• Что такое «сокращение весов»?
• Обоснование логистической регрессии (основная теорема), основные посылки (3) и следствия (2). Как выражается апостериорная вероятность классов (надо помнить формулу).
• Как выражается функция потерь в логистической регрессии (надо помнить формулу).
• Две мотивации и постановка задачи метода опорных векторов. Уметь вывести постановку задачи SVM (рекомендуется помнить формулу постановки задачи).
• Какая функция потерь используется в SVM? В логистической регрессии? Какие ещё функции потерь Вы знаете?
• Что такое ядро в SVM? Зачем вводятся ядра? Любая ли функция может быть ядром?
• Какое ядро порождает полимиальные разделяющие поверхности?
• Что такое ROC-кривая, как она определяется? Как она эффективно вычисляется?
• В каких алгоритмах классификации можно узнать не только классовую принадлежность классифицируемого объекта, но и вероятность того, что данный объект принадлежит каждому из классов?
• Каков вероятностный смысл регуляризации? Какие типы регуляризаторов Вы знаете?
• Что такое принцип максимума совместного правдоподобия данных и модели (надо помнить формулу)?

Регрессия

• Что такое ядерное сглаживание?
• Что есть общего между ядром в непараметрической регрессии и ядром SVM?
• На что влияет ширина окна, а на что вид ядра в непараметрической регрессии?
• Что такое окна переменной ширины, и зачем они нужны?
• Что такое «выбросы»? Как осуществляется фильтрация выбросов в непараметрической регрессии?
• Постановка задачи многомерной линейной регрессии. Матричная запись.
• Что такое сингулярное разложение? Как оно используется для решения задачи наименьших квадратов?
• Что такое «проблема мультиколлинеарности» в задачах многомерной линейной регрессии? Какие есть три подхода к её устранению?
• Сравнить гребневую регрессию и лассо. В каких задачах предпочтительнее использовать лассо?
• Какую проблему решает метод главных компонент в многомерной линейной регрессии? Записать матричную постановку задачи для метода главных компонент.
• Как свести задачу многомерной нелинейной регрессии к последовательности линейных задач?
• Метод настройки с возвращениями (backfitting): постановка задачи и основная идея метода.
• Какие методы построения логичтической регрессии Вы знаете?
• Приведите примеры неквадратичных функций потерь в регрессионных задачах. С какой целью они вводятся?

Примеры задач

• Задана цена отказа от классификации. Выписать модифицированную формулу байесовского классификатора.
• Вывести формулу линейного дискриминанта для случая независимых признаков.
• Вывести формулу наивного байесовского классификатора для случая бинарных признаков (доказать, что он линеен).
• Вывести формулу градиентного шага в методе логистической регрессии для задачи классификации с двумя классами. Сравнить с правилом Хэбба.
• Вывести формулу непараметрической регрессии Надарая-Ватсона.
• Вывести формулу регуляризованного решения задачи многомерной линейной регрессии через сингулярное разложение.
• Вывести градиентный метод обучения в логистической регрессии.

Второй семестр

Выбор модели и отбор признаков

• В чём отличия внутренних и внешних критериев?
• Разновидности внешних критериев.
• Разновидности критерия скользящего контроля.
• Что такое критерий непротиворечивости? В чём его недостатки?
• Что такое многоступенчатый выбор модели по совокупности критериев?
• Основная идея отбора признаков методом полного перебора. Действительно ли это полный перебор?
• Основная идея отбора признаков методом добавлений и исключнений.
• Что такое шаговая регрессия? Можно ли её использовать для классификации, в каком методе?
• Основная идея отбора признаков методом поиска в глубину.
• Основная идея отбора признаков методом поиска в ширину.
• Что такое МГУА?
• Основная идея отбора признаков с помощью генетического алгоритма.
• Основная идея отбора признаков с помощью случайного поиска.
• В чём отличия случайного поиска от случайного поиска с адаптацией?

Нейронные сети

• Приведите пример выборки, которую невозможно классифицировать без ошибок с помощью линейного алгоритма классификации. Какова минимальная длина выборки, обладающая данным свойством? Какие существуют способы модифицировать линейный алгоритм так, чтобы данная выборка стала линейно разделимой?
• Почему любая булева функция представима в виде нейронной сети? Сколько в ней слоёв?
• Метод обратного распространения ошибок. Основная идея. Основные недостатки и способы их устранения.
• Как можно выбирать начальное приближение в градиентных методах настройки нейронных сетей?
• Как можно ускорить сходимость в градиентных методах настройки нейронных сетей?
• Что такое диагональный метод Левенберга-Марквардта?
• Что такое «паралич» сети, и как его избежать?
• Как выбирать число слоёв в градиентных методах настройки нейронных сетей?
• Как выбирать число нейронов скрытого слоя в градиентных методах настройки нейронных сетей?
• В чём заключается метод оптимального прореживания нейронной сети? Какие недостатки стандартного алгоритма обратного распространения ошибок позволяет устранить метод ODB?

Композиции алгоритмов классификации

• Дать определение алгоритмической композиции (помнить формулу). Какие типы корректирующих операций вы знаете?
• Какие типы голосования вы знаете? Какой из них наиболее общий? (помнить формулу)
• Как обнаружить объекты-выбросы при построении композиции классификаторов для голосования по большинству?
• Как обеспечивается различность базовых алгоритмов при голосовании по большинству?
• Как обеспечивается различность базовых алгоритмов при голосовании по старшинству?
• Какие возможны стратегии выбора классов базовых алгоритмов при голосовании по старшинству?
• Какие две эвристики лежат в основе алгоритма AdaBoost?
• Как обнаружить объекты-выбросы в алгоритме AdaBoost?
• Достоинства и недостатки алгоритма AdaBoost.
• Основная идея алгоритма AnyBoost.
• Основная идея метода bagging.
• Основная идея метода случайных подпространств.
• Что такое смесь экспертов (помнить формулу)?
• Приведите примеры выпуклых функций потерь. Почему свойство выпуклости помогает строить смеси экспертов?

Логические алгоритмы классификации

• Что такое логическая закономерность? Приведите примеры закономерностей в задаче распознавания спама.
• Часто используемые типы логических закономерностей.
• Дайте определение эпсилон-дельта-логической закономерности (помнить формулы).
• Дайте определение статистической закономерности (помнить формулы).
• Сравните области статистических и логических закономерностей в (p,n)-плоскости.
• С какой целью делается бинаризация?
• В чём заключается процедура бинаризации признака?
• Как происходит перебор в жадном алгоритме синтеза информативных конъюнкций?
• Какие критерии информативности используются в жадном алгоритме синтеза информативных конъюнкций и почему?
• Как приспособить жадный алгоритм синтеза конъюнкций для синтеза информативных шаров?
• Что такое стохастический локальный поиск?
• В чём отличия редукции и стабилизации? В чём их достоинства и недостатки?
• Что такое решающий список?
• Какие критерии информативности используются при синтезе решающего списка и почему?
• Достоинства и недостатки решающих списков.
• Что такое решающее дерево?
• Какие критерии информативности используются при синтезе решающего дерева и почему?
• Достоинства и недостатки решающих деревьев.
• Зачем делается редукция решающих деревьев?
• Какие есть два основных типа редукции решающих деревьев?
• Как преобразовать решающее дерево в решающий список, и зачем это делается?
• Что такое ADT (alternating decision tree)? Как происходит построение ADT?
• Основная идея алгоритма КОРА.
• Почему возникает проблема предпочтения признаков с меньшими номерами в алгоритме КОРА? Как она решается?
• Основная идея алгоритма ТЭМП.
• Какие критерии информативности используются в алгоритме ТЭМП и почему?
• Почему возникает проблема дублирования закономерностей в алгоритме ТЭМП? Как она решается?
• Достоинства и недостатки алгоритма ТЭМП.
• Как использовать алгоритм AdaBoost для построения взвешенного голосования закономерностей?
• Какой критерий информативности используется в алгоритме AdaBoost?
• Структура алгоритма вычисления оценок (АВО).
• Что такое ассоциативное правило? Приведите пример ассоциативного правила в задаче анализа потребительских корзин.
• Основная идея алгоритма поиска ассоциативных правил APriory.

Кластеризация и таксономия

• Каковы основные цели кластеризации?
• Основные типы кластерных структур. Приведите для каждой из этих структур пример алгоритма кластеризации, который для неё НЕ подходит.
• В чём заключается алгоритм кратчайшего незамкнутого пути? Как его использовать для кластеризации? Как с его помощью определить число кластеров? Всегда ли это возможно?
• Основная идея алгоритма ФорЭл.
• Как вычисляются центры кластеров в алгоритме ФорЭл, если объекты — элементы метрического (не обязательно линейного векторного) пространства?
• Какие существуют функционалы качества кластеризации и для чего они применяются?
• Основные отличия алгоритма k-средних и EM-алгоритма. Кто из них лучше и почему?
• Основная идея иерархического алгоритма Ланса-Вильямса.
• Какие основные типы расстояний между кластерами применяются в алгоритме Ланса-Вильямса?
• Какие расстояния между кластерами, применяемые в алгоритме Ланса-Вильямса, лучше и почему?
• Что такое дендрограмма? Всегда ли её можно построить?
• Какой функционал качества оптимизируется сетью Кохонена? (помнить формулу)
• В чем отличия правил мягкой и жёсткой конкуренции? В чём преимущества мягкой конкуренции?
• Как устроена самооганизующаяся карта Кохоненеа?
• Как интерпретируются карты Кохонена?
• Почему задачи с частичным обучением выделены в отдельный класс? Приведите примеры, когда методы классификации и кластеризации дают неадекватное решение задачи с частичным обучением.
• Как приспособить графовые алгоритмы кластеризации для решения задачи с частичным обучением?
• Как приспособить EM-алгоритм для решения задачи с частичным обучением?
• Какие способы решения задачи с частичным обучением Вы знаете?