Дорожная карта математических дисциплин для машинного обучения, часть 2 (вероятности)

Вместо введения

Давным давно была первая часть, теперь настало время для второй части! Здесь затронем вопросы, связанные с теорией вероятностей.

Как и в прошлой статье, будем выделять несколько "уровней" погружения в предмет и его проработку. На самом деле, я считаю, что каждый предмет надо проходить несколько раз на разных "уровнях" сложности: сначала вы погружаетесь в предмет, привыкаете к "словарю", к типичной постановке задач и методам их решения. Через некоторое время, обогащенные знаниями из других областей, вы готовы вновь пройти курс, но уже на несколько более высоком уровне. Вас теперь уже могут интересовать не только стандарные задачи, но и ограничения методологии, нестандартные подходы, возможно какая-то философия, из которой вырос предмет (вечный спор между "frequentist school" и "bayesian school").

Напомню, что мы выделяем три "уровня" сложности:

1. Bring it on — основная рабочая лошадка; это книги, что называется, «must have».
2. Hurt me plenty — уровень повыше, позволяет оглядеть с высоты птичьего полёта уровень 1, систематизирует знания, объединяет различные области знаний.
3. Nightmare — для сильных духом, уровень мехмата, для любителей математики и башен из слоновой кости.

В большинстве случаев я указываю те книги, которые либо прочел сам, либо которые пользуются большой популярностью в (математическом) сообществе — их советуют на stackoverflow, goodreads, quora и т.д.

Классическая вероятность

Я убежден, что нет смысла прыгать сразу через три ступеньки и сходу погружаться в мир байесовского вывода, не изучив предварительно классические разделы: теорию вероятностей и статистику.

Что (минимально) я должен знать после курса по классической вероятности?

• Базовые понятия: событие, (собственно) вероятность, условная вероятность (одного события при условии, что произошло какое-то событие);
• Случайные величины, их распределения, мат. ожидание, дисперсия;
• Независимость случайных величин: обычная/попарная, в чем различие, корреляция;
• Классические примеры распределений: Бернулли, геометрическое, биномиальное, Пуассон, экспоненциальное, нормальное;
• Предельные теоремы: закон больших чисел, центральная предельная теорема;

Практически любой учебник по теории вероятностей покрывает упомянутые темы (и как правило — много чего ещё). Это самый базовый аппарат, на котором строятся уже более сложные модели.

Что я должен знать дополнительно, чтобы комфортно ощущать себя в машинном обучении?

• Условное математическое ожидание: во всей общности это довольно сложное понятие, но к счастью, для дискретных и абсолютно непрерывных случайных величин (а эти два класса покрывают бОльшую часть того, с чем приходится сталкиваться обычному смертному в вероятностых моделях) определяется не очень трудно, и достаточно принять "на веру" всего несколько теорем без вмешательства сигма-алгебр и интегралов Лебега и прочей фигни.
• Многомерное нормальное распределение: основная рабочая лошадка регрессионного анализа. Можно целый курс прочесть по геометрии этого распределения (собственно, это обычно и происходит, когда читают курс по линейной регрессии).
• Марковские цепи: ещё одна отправная точка многих методов и моделей (от MCMC до марковских случайных полей)
• Сопряженные распределения: Бета, Гамма;
• Вероятности отклонений: неравенства Маркова, Хёфдинга/Чернова;
• Контрпримеры: помимо основных теорем неплохо бы знать, когда теоремы нарушаются и почему;

Bring it on

Из англоязычных источников я очень рекомендую книгу Blitzstein & Hwang "Introduction to Probability"; есть соответствующая страничка в интернете, посвященная курсу: stat110. Там же есть ссылки на курс на youtube и курс на edx stat110x. Советую пробовать все три источника и выбирать то, что ближе вам. В 110х дополнительно есть автоматическая проверка задач и некоторые симпатичные визуализации и симуляции.
Книга очень хороша своей подборкой задач, решения к части из них можно найти на том же сайте. Вообще я очень рекомендую решать как можно больше задач: от простых на "набить руку" до содержательных. Дополнительно к главам идет бонус в виде симуляций и численных экспериментов на R.

Из российских аналогов: есть хороший курс от Райгородского на coursera/лектории МФТИ/openedu (см. например openedu). Есть своя специфика: много задач в курсе посвящены случайным графам.
По книгам можно посоветовать:

1. Классический учебник Е.С. Вентцель "Теория вероятностей". Приятный литературный русский язык и бонус — задачи в виде "ведется обстрел такой-то позиции..."
2. Очень-очень классная книга от Чжун Кай Лай, АитСахлиа Фарид: "Элементарный курс теории вероятностей. Стохастические процессы и финансовая математика". Много задачек, от простых до "на подумать".

Hurt me plenty

Опять же из англоязычного есть хороший курс от MIT
Как учебник я бы советовал Grimmett, Stirzaker "Probability and random processes" , и соответствующий задачник (с прорешанными!!! задачами): One Thousand Exercises in Probability.
Отдельно выделю очень интересную книгу от Michael Mitzenmacher, Eli Upfal: "
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd Edition)". Примечательна эта книга тем, что применяет вероятностные методы в "real-world" задачах. Ну и много не самых стандартных тем: от хэширования до VC-размерности.

На русском языке:

1. Хорошая книга от Тутубалина "Теория вероятностей" от 2008 года;
2. "Курс теории вероятностей" от Гнеденко;
3. Конспект курса теории вероятностей от Н. Черновой: Чернова;
4. Феллер, тома 1-2. Второй том мне кажется несколько устаревшим, во всяком случае в него включены темы, которые сейчас не всегда рассказываются (скажем, тауберовы теоремы, функции Бесселя и т.д.). Тем не менее, каждый, кто заинтересован вероятностью, должен хотя бы раз открыть эту книгу. Чаще всего рекомендуют издание 1984-го года (зеленое).

Особо крепкие могут попробовать пройти курс на Степике: Храбров. Но там маловато задачек для набивания руки, и он приближен уже к третьему "уровню". Данный курс является немного усеченным онлайн-аналогом курса, читающегося в computer science center: тут.

Также отдельно упомяну курс от Райгородского в ШАДе: здесь. Опять же, есть своя специфика, связанная с научными интересами преподавателя, уклон в вероятностные методы в графах.

Nightmare

Этот раздел содержит книги уровня мехмата МГУ. В них абсолютно строго излагаются основы теории вероятностей с опорой на теорию меры и интеграл Лебега. Такие вещи конечно же никогда не помешают, но
Вот уж каких книг на русском языке полно, можно взять любую, все очень хорошие:

1. Ширяев, "Вероятность";
2. Боровков, "Теория вероятностей";
3. Коралов, Синай, "Теория вероятностей и случайные процессы", книга интересна тем, что содержит также материал по марковским случайным полям — кажется, это редкий гость на русском языке.

По онлайн-курсам это пожалуй любой курс с Лекториума, в котором содержится слово "вероятность", например: этот

Смысла советовать книги на английском не вижу: наши и так достаточно хорошие.
Тем не менее, если вам неудержимо хочется читать на английском, то упомяну:

1. RICK DURRETT, "Probability, Theory and Examples";
2. Kai Lai Chung, "A course in probability theory";

Unclassified

Сюда включу то, что не подпадает под классификацию.

Одна книга, которую я люблю

Есть одна книга, сложность которой я не берусь определить. Я даже не могу сказать, на кого она рассчитана: для новичков это overkill; продвинутые чаще берут книги третьего уровня.
Тем не менее, я обязан упомянуть об этой книге: David Williams, "Weighing the Odds".
Ничего более говорить не буду, пусть каждый сам для себя решит, что он думает о ней. Лично для меня это абсолютная жемчужина, но не для всех.

Cheatsheets

Например, есть очень-очень классные cheatsheets ("шпаргалки"), которые очень кратко освещают то, что обычно проходят семестр. Вот мои любимые:

1. Нумер 1;
2. Нумер 2;

Задачники

Задачники использовать можно и нужно. Вероятность в некотором смысле поначалу контр-интуитивна, и нужно решать много задач, чтобы к ней привыкнуть.

1. One Thousand Exercises in Probability — я уже его упоминал ранее, но пишу еще раз. Стоит взглянуть, можно использовать независимо от учебника от тех же авторов;
2. Кельберт, Сухов " Вероятность и статистика в примерах и задачах" — трехтомник, недавно вышедший под эгидой МЦНМО. Задачки там довольно жёсткие, я бы даже сказал, что они слxожные. В него стоит иногда поглядывать для общего развития, но я бы наверное не рекомендовал штудировать "от и до".
3. "Стохастический анализ в задачах" под редакцией Гасникова — классное пособие от преподов МФТИ; там есть много интересных и классических задачек, но всё идет несколько вперемешку, поэтому это уже для тех, кто более-менее освоился в материале;
4. Для любителей математики можно посоветовать сборники задач от Ширяева, например "Вероятность в теоремах и задачах";
5. Множество хороших задач содержится в учебнике Blitzstein & Hwang "Introduction to Probability";

Как это посчитать?

Задачи и задачники это хорошо, но также вы должны уметь "запрограммировать" численный эксперимент, проверить руками (с помощью компьютера, конечно) центральную предельную теорему; прикинуть вероятность события через моделирование; подготовить себя к восприятию байесовских методов (MCMC и далее) и вероятностного программирования вообще.

Если вы счастливый пользователь python/julia, то я вам искренне советую почитать лекции QuantEcon, хотя бы те, что непосредственно связаны с теорией вероятностей; вообще же существует великое множество книг, которые так или иначе показывают, как моделировать какие-либо вещи в R/Python/Julia.

Что далее?

Из вероятности остались совсем не затронутыми математическая статистика и байесовский подход. К моему сожалению, в этих областях я читал меньше книг, а следовательно, и советы будут иметь меньшую ценность. Непонятно, писать ли, и насколько подробно.