Машинное обучение (семинары, ВМК МГУ)/2012

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

Семинары по годовому курсу лекций «Машинное обучение» К.В.Воронцова. На занятиях будут решаться теоретические задачи, важные для понимания и лучшего усвоения материала, читаемого на лекциях. Разбираемые на семинарах задачи частично составлены И.О.Толстихиным и М.Н.Ивановым, частично взяты из учебников, книжек и статей (в том числе указанных в списке литературы) и частично позаимствованы из аналогичных курсов, читаемых в западных университетах (в том числе из курсов MIT и Стэнфордского университета). Семинары ведутся на кафедре ММП ВМиК МГУ с осени 2012 года. Семинарист: И.О.Толстихин.

Содержание 1 Новости 2 Оценка за курс и «правила игры» 3 Осенний семестр 2012 3.1 Расписание занятий 3.2 Оценки 4 Весенний семестр 2013 4.1 Расписание занятий 4.2 Оценки 5 Литература

Новости

• В тексте семинара 8 была ошибка. Во втором неравенстве теоремы 2.2 в знаменателе дроби должно быть 2n а не n. [13.04.2013]
• В выложенной версии текста последнего семинара обнаружилась опечатка. На странице 8 в формулах (9) и (b) величины и надо заменить на и соответственно. [31.03.2013]
• Ориентировочно через 2 семинара будет контрольная работа по линейным методам классификации. [14.11.2012]
• Обратите внимание. Добавлена домашка по материалам 6го семинара (логистическая регрессия). [6.11.2012]
• В материалах 5го семинара найдена опечатка: в последней части, где речь идет о связи алгоритма ближайших соседей с парзеновским окном, была опечатка в мат.ожидании биномиального распределения. Исправления отмечены красным.
• 30 октября будет контрольная работа по байесовским методам и метрическим алгоритмам классификации. В ближайший вторник (23 октября) вместо семинара будет лекция, которая пройдет в той же аудитории и в то же время, что семинар. В ближайшее время, скорее всего, будет вывешен список задачек для подготовки к контрольной работе. В отличие от проверочных, этого списка будет не достаточно для успешной сдачи контрольной работы. Так что повторяйте весь пройденный на лекциях и семинарах материал, все домашки и все проверочные.
• Скорее всего через один семинар (23 октября) будет контрольная по темам "Байесовские методы" и "Метрические классификаторы". Имейте ввиду. [11.10.2012 18:20]
• На четвертом семинаре в материалах была допущена серия очень обидных опечаток. Во многих местах в описании ЕМ алгоритма был потерян логарифм! Обратите на это внимание, в материалах исправоения отмечены красным цветом!
• Принято решение вывешивать мои черновики к семинарам вместе с решениями. Домашние задания также будут вывешиваться на этой странице. Ищите все в расписании занятий.
• На втором семинаре, возможно, я допустил ошибку. Когда мы выводили ОМП для ковариационной матрицы многомерного нормального распределения, по-моему, я записал дифференцирование по , тогда как, конечно же, дифференцирование шло по . Еще раз загляните к себе в записи и убедитесь, что там все правильно.
• 18 и 25 сентября семинары не состоялись по причине командировки семинариста.

Оценка за курс и «правила игры»

Итоговая оценка за семестр будет вычисляться по формуле 0.67*(оценка за работу в семестре) + 0.33*(оценка на устном экзамене). При этом

• Округляться итоговая дробная оценка будет до ближайшего целого числа (*.5 будет округляться вверх).
• Оценка за экзамен — целая оценка 0, 3, 4 или 5.
• Оценка за работу в семестре — действительное число от 0 до 5. Оценка складывается из баллов, набранных студентом за
  1. контрольные работы (0.4),
  2. регулярные короткие проверочные работы на семинарах (0.3),
  3. коллоквиум (0.3),
  4. возможно, некоторые дополнительные активности (может быть доклады, решение задач со звездочками, и т.д. по усмотрению семинариста).
• За каждую работу студент получает дробную оценку от 0 до 5, пропорциональную числу решенных в данной работе задач. Так, если в работе было 4 задачи, а студент решает 2 из них, он получает 2.5 балла.
• Каждый вид из перечисленных выше семестровых активностей получает коэффициент, отражающий его степень важности (см. выше жирным в скобках). В сумме коэффициенты дают 1. Баллы внутри одного вида активности усредняются (если всего было 4 проверочных и студент набрал 0, 2.5, 3, 2.5, то за проверочные он получает (2.5+3+2.5)/4 = 2). Семестровая оценка вычисляется как взвешенная сумма усредненных баллов с указанными коэффициентами.
• Для успешного написания проверочных работ студенту домой будут выдаваться несколько типовых задач по темам, пройденным на последнем семинаре. Самостоятельного разбора этих задач будет вполне достаточно для успешного написания проверочной работы на следующем семинаре. За решение домашних задач оценки выставляться не будут.
• В проверочную работу будут входить также «задачи со звездочкой». Решение этих задач не обязательно для получения отличного балла (они не учитываются при подсчете доли решенных в работе задач), но они могут дать бонусные баллы.
• Студенты имеют возможность всегда написать семинаристу письмо с возникающими у них вопросами по домашним задачам. Семинарист по мере возможностей готов обсуждать вопросы студента и помогать ему в их разборе.
• К студентам, не набравшим в результате достаточного для «3» балла, применяются особые меры. Во-первых, они автоматически не смогут получить финальную оценку больше 3. Во-вторых, для получения оценки «удовл» им придется начать экзамен с написания большой письменной работы, куда войдут все пройденные в семестре темы. Студент будет пересдавать экзамен, пока не наберет нужного количества баллов.

Осенний семестр 2012

Расписание занятий

Дата	Семинар	Материалы	Д/З
4 сентября	Семинар 1: правила игры основные определения, постановки задач и примеры прикладных задач
11 сентября	Семинар 2: работа с вероятностью, условные вероятности, формула Байеса, формула полной вероятности вероятностная постановка задачи обучения, минимизация риска, минимизация эмпирического риска функция правдоподобия, оценки максимального правдоподобия одномерное и многомерное нормальное распределение, ОМП для его параметров	Короткий конспект (PDF, 151Кб)	Задачи
18 сентября	Семинар не состоялся
25 сентября	Семинар не состоялся
2 октября	Семинар 3: байесовский подход к классификации, байесовский оптимальный классификатор параметрическое оценивание плотностей классов, нормальный дискриминантный анализ Линейный Дискриминант Фишера (ЛДФ) Проверочная работа 1	Короткий конспект (PDF, 154Кб)	Задачи
9 октября	Семинар 4: смеси нормальных распределений скрытые переменные, совместное распределение скрытых и наблюдаемых переменных KL"=дивергенция, свойства ЕМ"=алгоритм в общем виде Проверочная работа 2	Короткий конспект (PDF, 152Кб)	Задачи
16 октября	Семинар 5: Разбор прошлой домашки: ЕМ-алгоритм Проклятие размерности Связь парзеновского окна с алгоритмом ближайших соседей Проверочная работа 3	Короткий конспект (PDF, 152Кб)	TBC
23 октября	Вместо семинара состоялась дополнительная лекция
30 октября	Контрольная работа №1 Байесовские методы классификации.
6 ноября	Семинар 6: Производящие и разделяющие подходы к классификации; Линейные методы классификации; Логистическая регрессия; Многоклассовая логистическая регрессия.	Короткий конспект (PDF, 146Кб)	Задачи
13 ноября	Семинар 7: Разбор прошлой домашки: логистическая регрессия Метод множителей Лагранжа, условия Куна-Таккера; Оптимальная разделающая гиперплоскость (hard-margin); Проверочная работа 4	Короткий конспект (PDF, 200Кб)	Задачи
20 ноября	Семинар 8: Разбор прошлой домашки: опт. раздел. гип-ть.; Двойственная функция, двойственная задача; Метод опорных векторов (soft-margin) Проверочная работа 5	Короткий конспект (PDF, 200Кб)	Задачи
27 ноября	Семинар не состоялся
4 декабря	Семинар 9: Разбор прошлой домашки: soft-margin SVM; Линейные классификаторы, SVM; Ядровой переход, ядровая функция; Проверочная работа 6	Короткий конспект (PDF, 165Кб)	Задачи
10 декабря	Контрольная работа 2
11 декабря	Семинар 10: Линейная регрессия; Метод наименьших квадратов; Геометрическая интерпретация	Короткий конспект (PDF, 160Кб)	Задачи
18 декабря	Письменный коллоквиум

Оценки

Информация по средним баллам актуальна!

ФИО студента	Группа	Проверочные работы						Сред. пров.	Контрольные работы			Коллоквиум	Экзамен	Итоговая оценка
		№1(3)	№2(4)	№3 (5)	№4 (5)	№5 (5)	№6 (5)		№1(6)	№2(24)	Сред.
Алешин И.	317	1.66	2.5	3	1	5	3	2.693	2.5	1.25	1.875	5		3
Антипов А.	317	0	2.5	1	2	5	1	1.917	1.67	1.875	1.773	4.71		4
Арбузова Д.	317	0	2.5	3	3	5	4	2.917	4.17	2.29	3.23	4.855		5
Горелов А.	317	3.33	0	3	3	5	3	2.888	3.33	3.33	3.33	4.71		5
Зиннурова Э.	317	1.66	3.75	1	3	3	3	2.568	1.67	3.125	2.398	4.71		4
Кузьмин А.	317	3.33	1.25	3	2	3	3	2.597	4.17	3.54	3.855	3.696		4
Ломов Н.	317	3.33	1.25	2	3	5	3	2.93	4.17	3.33	3.75	4.493		5
Львов С.	317	1.66	3.75	3	3	0	4	2.568	1.67	1.875	1.773	4.565		4
Найдин О.	317	0	0	1	2	5	2	1.667	2.5	1.875	2.188	3.913		4
Никифоров А.	317	5	2.5	4	3	5	3	3.75	5	3.125	4.063	4.42		5
Новиков А.	317	5	3.75	4	5	5	5	4.625	3.33	4.58	3.955	4.71		5
Петров Г.	317	1.66	3.75	2	2	5	3	2.901	0.83	1.04	0.935	4.493		3
Подоприхин Д.	317	5	1.25	4	3	5	5	3.875	3.33	2.08	2.705	4.928		5
Рыжков А.	317	3.33	3.75	3	2	4	5	3.513	2.5	1.875	2.188	4.493		4
Сокурский Ю.	317	3.33	3.75	3	2	5	3	3.347	2.5	3.125	2.813	4.493		4
Ульянов Д.	317	1.66	3.75	2	5	5	3	3.402	2.5	3.125	2.813	4.71		5
Харациди О.	317	1.66	0	0	2	4	2	1.61	3.33	3.33	3.33	4.565		4
Шабашев Ф.	317	3.33	0	1	4	5	1	2.388	2.5	1.875	2.813	4.348		4
Шадриков А.	317	1.66	2.5	3	3	4	2	2.693	4.17	3.958	4.064	3.55		4
Швец П.	317	0	0	2	0	3	1	0.5	2.5
Афанасьев К.	316	1.66	2.5	1	1	3	3	2.027	1.67	н	?	3.044		4

Весенний семестр 2013

Расписание занятий

Дата	Семинар	Материалы	Д/З
19 февраля	Семинар 1: Композиции; Boosting: adaboost, anyboost; Многоклассовый AdaBoost	Короткий конспект	Задачи
26 февраля	Семинар 2: Композиции; Bias-variance decomposition; Bagging Проверочная работа 1	Короткий конспект	Задачи
5 марта	Семинар 3: Композиции; Gradient Boosting; Stochastic Gradient Boosting	Короткий конспект	Задачи
12 марта	Семинар 4: Контрольная работа 1
19 марта	Семинар 5: Оценки обобщающей способности; Неравенства Буля, Маркова, Чебышев, метод Чернова; Лемма Хевдинга, неравенство Хевдинга.	Короткий конспект	См конспект
26 марта	Семинары 6,7: Оценки обобщающей способности; Оценка для одной функции; Оценка для конечного класса функций; Оценка "Бритва Оккама" для счетного класса функций; Оценка Вапника--Червоненкиса для общего случая; Функция роста, размерность Вапника--Червоненкиса.	Короткий конспект	Задачи на дом
9 апреля	Семинар 8: Оценки обобщающей способности; Неравенства Азумы--Хевдинга и МакДиармила; Радемахеровская сложность; Оценка с радемахеровской сложностью.	Короткий конспект	Задачи на дом
16 апреля	Семинар 9: Разбор задач из домашек	-	-
23 апреля	Семинар 10: Контрольная работа 2	-	-
30 апреля	Семинар 11: Деревья; Построение деревьев классификации; Построение деревьев регрессии; Пост-прунинг деревьев: cost-complexity pruning.	Короткий конспект	Докажите теоремы 2.2 и 2.3 из семинара
7 мая	Семинар 12: Случайный многорукий бандит; Алгоритмы Hoeffding race, Bernstein race.	Короткий конспект	TBA

Оценки

ФИО студента	Группа	Проверочные работы	Контрольные работы			Экзамен	Итоговая оценка
		№1(7)	№1	№2	Сред.
Алешин И.	317	0.71	2.78	2.33	2.56
Антипов А.	317	4.0	2.78	1	1.89
Арбузова Д.	317	2.86	2.22	3.75 (+)	2.99
Горелов А.	317	1.43	3.89	1.83	2.86
Зиннурова Э.	317	1.43	1.67	2.92	2.30
Корольков М.	317	0	2.78	2.92	2.85
Кузьмин А.	317	3.57	4.44	2.92	3.68
Ломов Н.	317	3.57	4.44	3.17	3.81
Львов С.	317	0.71	3.33	2.75	3.04
Найдин О.	317	2.86	4.44	1.67	3.06
Никифоров А.	317	5.0	3.89	4.83	4.36
Новиков А.	317	5.0	5	4.58	4.79
Петров Г.	317	1.43	2.78	1.42	2.10
Подоприхин Д.	317	3.57	3.33	5.0	4.17
Рыжков А.	317	4.29	3.89	3.83	3.86
Сокурский Ю.	317	4.29	5	2.92	3.96
Ульянов Д.	317	2.14	3.89	4.83	4.36
Харациди О.	317	2.86	3.89	2.75	3.32
Шабашев Ф.	317	0.71	2.22	2.92	2.57
Шадриков А.	317	2.86	2.22	2.5	2.36

Арбузова (+): подробные комментарии к тексту семинаров с исправлением ошибок.

Литература

1. Курс лекций К.В.Воронцова (1 часть, PDF, 3 МБ)
2. Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
3. Hastie T., TIbshirani R, Friedman J. The Elements of Statistical Learning (2nd edition). Springer, 2008.