Что оглавление учебника по машинному обучению говорит о самой области

TL;DR. Второе издание Foundations of Machine Learning (MIT Press, 2018) Мори, Ростамизаде и Талвалкара строит курс вокруг выборочной сложности, оценок Радемахера и гарантий.

Ключевые выводы

Книга с точной родословной. Начнём с фактов, которые закрепляют предмет разговора.
Определение, которое несёт основную нагрузку. Всё последующее зависит от одного предложения.
Один разобранный пример: документы и темы. Введение привязывает определение к конкретной задаче обучения.
Три сложности, а не две. Здесь книга делает свой самый характерный ход, и его легко не заметить, потому что он подан как короткое замечание.

Второе издание Foundations of Machine Learning (MIT Press, 2018) Мехриара Мори, Афшина Ростамизаде и Амита Талвалкара определяет обучение как использование опыта для точных предсказаний и строит строгий курс вокруг выборочной сложности, оценок Радемахера и теоретических гарантий.

Большинство книг о машинном обучении начинаются с обещания того, что вы сможете построить. Эта начинается с определения и списка величин, от которых зависит, справится ли обучающийся алгоритм. Такой порядок показывает, чем авторы считают свой предмет, и, по-моему, это верное решение. Область, которая продаёт себя через предсказания, должна объяснить читателю, когда предсказаниям можно доверять, и именно это объяснение книга и берётся дать.

Эта статья читает книгу по тому, что на самом деле сказано в её вводных материалах, предисловии и первых страницах. Это более узкая задача, чем рецензия на каждую главу, и она честно признаёт свои пределы: источники здесь ограничены титульным листом, оглавлением, предисловием и началом введения. В этих пределах есть ясная линия рассуждения. Она касается того, что такое машинное обучение, от чего оно зависит, что авторы решили охватить и что решили оставить за бортом.

Книга с точной родословной #

Начнём с фактов, которые закрепляют предмет разговора. Книга называется Foundations of Machine Learning, и это второе издание. Она входит в серию Adaptive Computation and Machine Learning, редактор которой Фрэнсис Бах. Авторы: Мехриар Мори, Афшин Ростамизаде и Амит Талвалкар. Издатель: The MIT Press, Кембридж, Массачусетс, авторские права принадлежат Массачусетскому технологическому институту, год 2018. Издание в твёрдой обложке имеет ISBN 9780262039406.

Две производственные детали заслуживают по предложению. Книгу сверстали в LaTeX сами авторы, что подходит тексту, насыщенному оценками, определениями и доказательствами, а напечатана и переплетена она в Соединённых Штатах Америки. Ни одна из этих деталей не меняет того, как читать математику. Но авторы, которые сами верстали книгу, держали в руках каждую страницу, и для книги такого рода это обнадёживает.

Происхождение материала важнее. Большая его часть восходит к магистерскому курсу, который тоже называется Foundations of Machine Learning и который первый автор последние четырнадцать лет читает в Курантовском институте математических наук Нью-Йоркского университета. Это конкретное и проверяемое происхождение. Учебник, выросший из четырнадцати лет преподавания одного курса, по всей видимости, сформирован тем, что давалось студентам с трудом, и описанные ниже упражнения и приложения читаются именно так. Я бы не стал продвигать этот вывод дальше, чем позволяет источник. Предисловие говорит, откуда взялся материал, но не говорит, сколько переработок прошёл курс и с чем студенты боролись. Того, что сказано, достаточно: это материал курса, а не обзор, собранный по литературе.

Определение, которое несёт основную нагрузку #

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

Каждое существительное в этом предложении выполняет свою работу. «Вычислительные методы» помещают предмет внутрь информатики. Затем уточняется «опыт»: это прошлая информация, доступная обучающемуся алгоритму. В предложении нет утверждения, что алгоритм что-либо понимает, и ничего не сказано об интеллекте. У обучающегося алгоритма есть прошлая информация и цель, то есть улучшение качества или точное предсказание, и вся дисциплина посвящена связи между ними.

Я бы сказал, что для технических читателей и основателей компаний это определение полезнее более громких, что ходят вокруг, потому что оно прямо указывает на рычаги, которыми вы управляете. Если обучение есть функция прошлой информации, то ваше влияние на результат заключено в том, какую информацию вы собираете и сколько её. Следующее утверждение текста говорит то же: качество и объём данных решают успех предсказаний, которые делает обучающийся алгоритм. В тексте это утверждение подано как простой механизм, без всяких оговорок.

Авторы описывают и сами методы. Это методы, движимые данными, которые сочетают фундаментальные понятия информатики с идеями из статистики, теории вероятностей и оптимизации. Это предложение служит одновременно списком предварительных знаний и картой соседей области. Команда, которая хочет строить обучающиеся системы, опирается сразу на информатику, статистику, теорию вероятностей и оптимизацию. Считать любую из них необязательной означает сделать выбор, который книга не одобряет.

Один разобранный пример: документы и темы #

Введение привязывает определение к конкретной задаче обучения. Возьмём конечную выборку случайно отобранных документов, каждый из которых помечен темой. Задача состоит в том, чтобы по этой выборке предсказывать тему ещё не виденных документов.

Эта постановка вознаграждает медленное чтение. Выборка конечна, поэтому алгоритм никогда не видит всего. Документы отобраны случайно, и именно это позволяет конечной выборке говорить что-то о невиданных документах. Каждый помечен темой, так что у алгоритма есть разметка. А целью служат документы, которых он не видел, и в этом разница между предсказанием и запоминанием.

Затем авторы выделяют две вещи, которые делают задачу легче или труднее. Первая из них размер: очевидно, чем больше выборка, тем задача легче. Вторая из них качество меток. Сложность задачи зависит также от качества меток, присвоенных документам выборки, поскольку не все метки могут быть верными, и от числа возможных тем.

В этом предложении три отдельные ручки настройки. Одна из них размер выборки. Другая правильность меток. Третья число возможных тем. Ни одна не касается алгоритма. Все они представляют собой свойства задачи и данных и определяют, насколько трудна задача, ещё до выбора метода. Для основателя, который решает, куда тратить бюджет, это точное наблюдение. Если вы можете улучшить метки или увеличить выборку, вы воздействуете на те факторы, которые авторы прямо называют определяющими сложность.

Пример называет и собственную задачу. Предсказание метки документа известно также как классификация документов, и авторы сразу добавляют, что это вовсе не единственная задача обучения. Эту оговорку легко пропустить. Пример с документами служит лишь средством, а утверждение под ним общее.

Три сложности, а не две #

Здесь книга делает свой самый характерный ход, и его легко не заметить, потому что он подан как короткое замечание. Машинное обучение, говорят авторы, состоит в разработке эффективных и точных алгоритмов предсказания. Как и в других областях информатики, временная и пространственная сложность служат ключевыми мерами качества таких алгоритмов. Всякий, кто изучал алгоритмы, узнает эти две меры. Сколько времени это занимает и сколько памяти нужно?

Затем следует добавление. Машинному обучению нужно, кроме того, понятие выборочной сложности, чтобы оценить размер выборки, который требуется алгоритму, чтобы выучить семейство понятий. У этой меры нет аналога в процедуре сортировки. Алгоритму сортировки не нужно сообщать, сколько примеров ему требуется. Обучающемуся алгоритму нужно, потому что его результат представляет собой предсказание о случаях, которых он не видел, и объём опыта за этим предсказанием входит в то, за что вы платите.

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

Текст продолжает в том же направлении. В более общем виде теоретические гарантии обучения для алгоритма зависят от сложности рассматриваемых классов понятий и от размера обучающей выборки. Это сжатая формулировка того, из чего состоит гарантия. Есть два входа, насколько богато семейство понятий и сколько у вас обучающих данных, и гарантия связывает их с качеством работы. Обратите внимание, что из этого следует для структуры книги. Последующие главы должны дать способы измерять сложность класса понятий, и оглавление показывает, что они это делают.

Авторы объясняют и то, почему область находится там, где находится. Поскольку успех обучающегося алгоритма зависит от используемых данных, машинное обучение по своей природе связано с анализом данных и статистикой. Механизм назван прямо: успех зависит от данных, следовательно, предмет переплетён с дисциплинами, которые изучают данные. По-моему, это самое честное предложение во введении. Оно не представляет статистику ни соперницей, ни прародительницей. Оно представляет статистику следствием того, от чего зависит обучение.

Измерение	Временная сложность	Пространственная сложность	Выборочная сложность
Операционное определение	Асимптотическое время работы, нужное, чтобы выдать гипотезу $h$	Объём памяти, необходимый при обучении и оценке	Число обучающих примеров $m$, нужное, чтобы выучить семейство понятий
Определяющая теория	Вычислительная сложность (P против NP, трудность обучения)	Ограничения памяти архитектуры и локальность кэша	PAC-обучение, сложность Радемахера и VC-размерность
Следствие для затрат	Серверные вычисления и бюджет вывода на GPU/CPU	Объём RAM и встроенной SRAM	Затраты на сбор, аннотирование и разметку данных
Теоретическая роль	Измеряет эффективность алгоритма по времени работы	Измеряет эффективность использования памяти	Определяет ошибку обобщения и оценки на невиданных данных

Теоретический хребет #

Предисловие говорит, как устроена книга. Первые три или четыре главы закладывают теоретический фундамент для последующего материала. Оглавление позволяет увидеть, из чего этот фундамент сделан, по крайней мере по названиям.

Первая глава в оглавлении называется «The PAC Learning Framework» (рамки PAC-обучения), и в ней есть разделы «Guarantees for finite hypothesis sets - consistent case» и «Guarantees for finite hypothesis sets - inconsistent case» (гарантии для конечных множеств гипотез в согласованном и несогласованном случаях). Названия разделов сообщают две вещи. Во-первых, рамки дают гарантии, что совпадает с акцентом введения. Во-вторых, гарантии разделены по тому, согласован случай или нет, и книга рассматривает эти случаи отдельно. Я не буду гадать, что содержат согласованный и несогласованный случаи, потому что источники дают только названия разделов. Но сама пара показывает, что авторы не выдают одну чистую теорему и не идут дальше. Более трудному и запутанному случаю они отводят собственный раздел.

Следующая глава в списке называется «Rademacher Complexity and VC-Dimension» (сложность Радемахера и VC-размерность). Её разделы охватывают сложность Радемахера, функцию роста, VC-размерность и нижние оценки. Если читать её на фоне введения, эта глава естественно отвечает на вопрос, который введение ставит. Если гарантии зависят от сложности рассматриваемых классов понятий, нужны инструменты для измерения этой сложности. Сложность Радемахера, функция роста и VC-размерность перечислены как разделы, которые несут эту нагрузку. Стоит отметить и то, что в списке разделов есть нижние оценки. Книга, которая приводит только верхние оценки, говорит вам, что достижимо. Книга, которая включает и нижние, говорит ещё и о том, что недостижимо.

Дальше идёт глава 4, «Model Selection» (выбор модели), с разделами, среди которых минимизация эмпирического риска (ERM) и минимизация структурного риска (SRM). Мы вернёмся к этой главе, когда будем смотреть на второе издание, потому что именно здесь новое издание меняет больше всего.

Структура продумана. Сначала фундамент, затем аппарат для измерения сложности, затем выбор модели, и только после этого алгоритмы. Это защитимый способ преподавания, и он совпадает с тем, как книга сама описывает своё устройство: первые главы закладывают теорию, а остальное строится на ней.

От теории к алгоритмам: опорные векторы и ядра #

Оглавление называет и следующие за этим алгоритмические главы. Одна называется «Support Vector Machines» (метод опорных векторов) и содержит разделы для разделимого и неразделимого случаев. Каждый из них охватывает прямую задачу оптимизации, опорные векторы и двойственную задачу оптимизации. Другая называется «Kernel Methods» (ядерные методы).

Сама форма главы о методе опорных векторов информативна. Под заголовками разделимого и неразделимого случаев повторяются одни и те же три темы: прямая задача оптимизации, опорные векторы и двойственная задача оптимизации. Такое повторение говорит о параллельном изложении, когда одни и те же вопросы задаются дважды при разных допущениях. Эта параллель повторяет деление на согласованный и несогласованный случаи в главе о PAC, и по всей книге проступает закономерность: сначала чистый случай, затем случай, в котором чистое допущение не выполняется.

Я бы остерегался вычитывать из оглавления слишком много. Оно может сказать, что охватывает книга и как делит материал. Оно не может сказать, насколько хорошо написан какой-либо раздел, и в этих источниках ничего об этом нет. Зато оно показывает, что язык оптимизации в главе о методе опорных векторов, прямая и двойственная задачи, отсылает к описанию методов во введении как сочетания информатики с идеями из статистики, теории вероятностей и оптимизации. Оптимизационная нить этого списка конкретно проявляется в названиях этих разделов.

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

Что книга решает не охватывать #

Самый интересный фрагмент предисловия посвящён пропускам. Книга, говорят авторы, представляет собой общее введение в машинное обучение, которое может служить справочником для исследователей и учебником для студентов. Сделав это широкое заявление, они добавляют ограничение: они решили опустить несколько важных тем, в том числе графические модели и нейронные сети.

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

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

Свяжите это с введением. Книга организована вокруг теоретических гарантий обучения. Гарантии зависят от сложности классов понятий и размера обучающей выборки, а теоретические главы идут первыми, потому что на них строится всё остальное. Метод, для которого надёжных гарантий сейчас нет, плохо вписывается в книгу, построенную так. Значит, пропуск вытекает из центрального принципа книги. Он согласуется с тем определением предмета, с которого авторы решили начать.

Здесь нужна осторожность. Текст говорит «некоторых методов», так что речь идёт об отсутствии надёжных гарантий для некоторых методов, а не для всех опущенных тем, и говорит «нынешнего», что привязывает суждение ко времени написания. Я бы удержался от соблазна свести это к фразе «у нейронных сетей нет теории». Источник говорит не это. Он говорит, что гарантий для некоторых методов сейчас нет и что именно это вместе с краткостью стало причиной, по которой графические модели и нейронные сети не вошли в книгу.

Для технических читателей, выбирающих, что изучать, практический вывод прост. Эта книга даёт вам словарь гарантий и прямо говорит, каких областей она не касается.

Что меняет второе издание #

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

Главное изменение составляет полноценная глава о выборе модели, глава 4, посвящённая теме, которую авторы называют важной и которая в предыдущем издании обсуждалась лишь кратко. Формулировка прямая. Авторы не утверждают, что первое издание хорошо её охватывало. Они говорят, что она обсуждалась лишь кратко и что теперь ей отведена целая глава. Среди разделов минимизация эмпирического риска (ERM) и минимизация структурного риска (SRM), как показывает оглавление.

Почему выбор модели заслуживает такого повышения? Источники этого не говорят, и я не стану придумывать причину за авторов. Но расположение показательно. Глава 4 следует сразу за главами о рамках PAC и о сложности Радемахера и VC-размерности, то есть попадает в те первые три или четыре главы, которые, по словам предисловия, закладывают теоретический фундамент. Значит, авторы не пристроили выбор модели как запоздалую мысль. Они встроили его в теоретический фундамент.

Следующие дополнения представляют собой новую главу о моделях максимальной энтропии, главу 12, и новую главу об условных моделях максимальной энтропии, главу 13. Две совершенно новые главы составляют существенное расширение, и теперь книга посвящает этой паре идущие подряд главы.

Меняются и приложения. Авторы добавили полный раздел о двойственности Фенхеля в приложение B по выпуклой оптимизации и добавили приложение E по теории информации. В книге есть также обширное приложение с кратким обзором линейной алгебры. Эти изменения указывают в одном направлении: вспомогательная математика выросла вместе с главами. Двойственность Фенхеля присоединяется к приложению по выпуклой оптимизации, а теория информации получает собственное приложение. Я бы не стал утверждать, что теория информации появилась именно для поддержки глав о максимальной энтропии, поскольку источники такой связи не указывают, а в предисловии эти два дополнения идут отдельными пунктами. Их совпадение по времени, в одном и том же издании, я так и оставлю совпадением.

Для кого книга и как её предполагается читать #

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

Книга говорит и о том, что она предполагает. От читателя ожидается знакомство с основными понятиями линейной алгебры, теории вероятностей и анализа алгоритмов. Список короткий, и он совпадает со списком составляющих из введения, хотя и не полностью. Введение называет источниками методов информатику, статистику, теорию вероятностей и оптимизацию. Предварительные требования называют линейную алгебру, теорию вероятностей и анализ алгоритмов. Оптимизации среди требований нет, и книга закрывает это с другой стороны: приложение B посвящено выпуклой оптимизации, с новым разделом о двойственности Фенхеля. Линейная алгебра ожидается как подготовка, и книга всё же даёт обширное приложение с её обзором. Так что требования и приложения пересекаются намеренно, и читатель, чья линейная алгебра заржавела, найдёт краткий обзор под той же обложкой.

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

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

Применения широки, и книга так и говорит #

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

Обнаружение спама служит хорошим примером по причине, которую объясняет собственная схема авторов. Это задача классификации документов ровно в смысле предыдущего примера: на входе размеченные документы, на выходе предсказания о невиданных документах. Факторы размера выборки и качества меток применимы к ней напрямую. Большая выборка облегчает задачу, а неверно размеченные сообщения затрудняют её. Число возможных категорий мало, и по логике предыдущего фрагмента это тоже влияет на сложность. Я применяю заявленные в книге факторы к заявленному в ней примеру и ничего не утверждаю о спам-фильтрах в реальной жизни.

В расположении этого фрагмента есть и негромкий аргумент. Авторы вводят классификацию документов как задачу обучения и сразу отмечают, что она вовсе не единственная. Применения широки, потому что широко исходное определение. Подходит всё, что укладывается в формулу «вычислительные методы, использующие опыт для улучшения качества работы или для точных предсказаний». Эта общность и объясняет, зачем книге теория. Схема, рассчитанная на очень широкий круг применений, не может быть привязана к деталям какого-то одного, а гарантии, сформулированные через сложность класса понятий и размер выборки, как раз переносятся с задачи на задачу.

Ставка, которую делает книга #

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

Это ставка на теорию как на то, что остаётся. Я понимаю, почему её сделали авторы, годами преподававшие магистерский курс. У ставки есть цена, и авторы её называют: пропуск графических моделей и нейронных сетей становится платой за настойчивое требование надёжных гарантий. Читателю стоит честно взвесить эту цену. Если в вашей работе преобладают опущенные области, эта книга служит фундаментом, а не руководством. Если вашей работе нужно рассуждать о том, обобщит ли алгоритм по конечной выборке, словарь книги и составляет её смысл.

Для основателей полезный вывод оказывается самым непритязательным. Качество и объём данных решают успех предсказаний, а сложность задачи зависит от качества меток и от числа возможных тем. Это утверждения о входных данных, на которые вы часто можете влиять. Книга не обещает, что какой-либо конкретный алгоритм спасёт скудную или неверно размеченную выборку, и правильно делает.

Для технических читателей интереснее вопрос, который предисловие оставляет открытым. Авторы опустили некоторые методы из-за нынешнего отсутствия надёжных теоретических гарантий. Слово «нынешнего» обозначает положение дел на момент написания, и источники не говорят, изменится ли оно и как. Что потребовалось бы, чтобы эти гарантии стали достаточно надёжными и заслужили главу? Книга не может на это ответить. Но, точно указав, что она оставляет за бортом и почему, она по крайней мере показывает, куда смотреть.

Что это значит по отраслям #

Настойчивое требование статистических гарантий обучения и выборочной сложности задаёт практические границы в ряде областей разработки программ и исследований.

Академическое машинное обучение и разработка учебных программ #

Образовательные программы должны сопротивляться давлению, превращающему машинное обучение в эмпирическую инженерию промптов или в обвязку фреймворков. Обучение студентов на основе рамок PAC, сложности Радемахера и минимизации структурного риска формирует устойчивую математическую интуицию, которая переживёт смену недолговечных архитектур глубокого обучения.

Корпоративная разработка ИИ и оценка стоимости данных #

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

Передовые исследования ИИ и аудит моделей #

Когда регуляторные рамки, такие как EU AI Act, требуют предсказуемых границ для автоматизированных систем принятия решений, статистические гарантии обучения, формализованные в Foundations of Machine Learning, становятся необходимостью для соответствия требованиям. Регуляторы и аудиторы безопасности требуют доказуемых оценок обобщения и строгих процедур выбора модели, а не эвристических оценок на валидации.

Заключение #

Foundations of Machine Learning остаётся незаменимой опорой в области, которую часто тянет к голому эмпиризму. Построив целый курс вокруг PAC-обучения, сложности Радемахера и VC-размерности, Мехриар Мори, Афшин Ростамизаде и Амит Талвалкар напоминают исследователям, что изящество алгоритма не заменяет математических гарантий. Откровенный пропуск нейронных сетей и графических моделей из-за отсутствия гарантий в замкнутой форме не изъян, а определяющая сила книги, которая ясно отделяет то, что дисциплина может строго доказать, от того, что она лишь наблюдает.

Часто задаваемые вопросы #

Почему авторы не включили нейронные сети и графические модели во второе издание?

Авторы сознательно опустили нейронные сети и графические модели ради краткости и из-за нынешнего отсутствия надёжных теоретических гарантий для ряда этих методов. Книга строго организована вокруг алгоритмов, для которых возможны строгие оценки обобщения.

Чем выборочная сложность отличается от временной и пространственной?

Временная сложность оценивает скорость выполнения, пространственная измеряет потребление памяти, а выборочная сложность количественно определяет математический объём обучающих данных, который нужен алгоритму, чтобы выучить семейство понятий с заданными допусками на ошибку и уверенность.

В чём главное различие между минимизацией эмпирического риска и минимизацией структурного риска?

Минимизация эмпирического риска (ERM) выбирает гипотезу, которая напрямую минимизирует ошибку на обучении, рискуя переобучением при высокой сложности гипотез. Минимизация структурного риска (SRM) уравновешивает ошибку на обучении и сложность гипотез (например, VC-размерность или сложность Радемахера), давая формальные оценки риска обобщения.

Источники #

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, (2018). Foundations of Machine Learning, второе издание ⧉. The MIT Press.
Leslie G. Valiant, (1984). Теория обучаемого ⧉. Communications of the ACM.
Vladimir N. Vapnik, (1998). Статистическая теория обучения ⧉. John Wiley & Sons.

Последняя проверка 2026-10-10.

Последняя проверка 2026-10-27.

Опубликовать заново

Что оглавление учебника по машинному обучению говорит о самой области — Sebastien Rousseau

Второе издание Foundations of Machine Learning (MIT Press, 2018) Мори, Ростамизаде и Талвалкара строит курс вокруг выборочной сложности, оценок Радемахера и гарантий.

Эта статья распространяется по лицензии Creative Commons Attribution 4.0 International. При повторной публикации требуется указание канонической ссылки.

Что оглавление учебника по машинному обучению говорит о самой области — Sebastien Rousseau

Второе издание Foundations of Machine Learning (MIT Press, 2018) Мори, Ростамизаде и Талвалкара строит курс вокруг выборочной сложности, оценок Радемахера и гарантий.

Originally published at https://sebastienrousseau.com/ru/2026-10-10-oglavlenie-uchebnika-mashinnomu-obucheniyu-govorit-samoy/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER