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

Определение ошибки обобщения

Поскольку эта серия статей посвящена пониманию ошибки обобщения и тому, как ее минимизировать, важно сначала определить, что это такое. Проще говоря, ошибка обобщения - это мера того, насколько хорошо модель машинного обучения работает (то есть прогнозирует) на ранее невидимых данных. Значит, чем он меньше - тем лучше. Это также называется ошибкой вне выборки, которая будет подробнее объяснена далее в этой статье. Разобравшись с этим, давайте начнем.

Изучение правил

Давайте представим, что у нас есть набор данных D, который состоит из нескольких выборок - каждая выборка состоит из некоторых наблюдений и их результатов. Это наши обучающие данные, и мы хотим, чтобы наша модель научилась предсказывать на их основе. Чтобы это стало возможным, нам нужно найти функцию f, которую мы будем называть целевой функцией. Интуитивно целевую функцию можно сравнить с хорошо известной математической функцией f (x) - функция определяет выход на основе входных данных. Легко, не правда ли? Что ж, одна проблема - целевая функция нам неизвестна и всегда будет!

Поскольку целевая функция неизвестна, кроме как внутри нашего образца, как мы можем узнать, является ли наша приближенная функция хорошей? Любая функция, которая согласуется с целевой функцией внутри D, может быть правильной! Каждая из этих возможных функций называется гипотезой, а набор возможных функций называется классом гипотез, H.

Если наша целевая функция f неизвестна, мы не можем исключить какие-либо значения «f» за пределами D, нашего данного обучающего набора. Что мы можем сделать, так это использовать вероятность, чтобы сделать вывод о том, что находится вне D, используя только D. Это будет интуитивно объяснено с помощью примеров. Если вы ничего не знаете о неравенстве Хёффдинга, рекомендуется сначала прочитать мою статью об этом, поскольку она будет очень актуальна в следующем разделе.

Хёффдинг спасает положение

Теперь мы увидим, как вероятность может помочь нам оценить нашу целевую функцию f, просто используя наш образец набора данных D. Начнем с простого примера.

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

  • P (собирая желтый шар) = µ
  • P (взятие синего шара) = 1 - µ

Помните, что µ - это просто имя переменной, поскольку мы не знаем фактическую вероятность выбрать желтый шар! Теперь самое интересное - мы можем залезть в коробку и взять образец. Выбираем N шаров независимо друг от друга. Затем мы наблюдаем долю желтых шаров в нашей выборке, эта фракция будет называться v.

Тогда возникает вопрос на миллион долларов - может ли этот образец рассказать нам что-нибудь о нашем неизвестном дистрибутиве в коробке? Абсолютно! Если выборка достаточно велика - тогда v, ​​вероятно, будет близко к µ! Мы можем описать это следующим знакомым уравнением:

Другими словами, уравнение говорит, что по мере роста размера выборки N становится экспоненциально маловероятным, что v отклонится от µ больше, чем наш «допуск», ε. Обратите внимание, что на границу влияет только размер N образца, а не размер «рамки». «Коробка» может быть большой или маленькой, конечной или бесконечной, и мы все равно получаем ту же границу, когда используем тот же размер выборки. Если мы выберем ε маленьким, чтобы v было хорошим приближением к µ, нам понадобится больший размер выборки N. Стоит отметить следующее: µ не влияет на нашу границу вероятности! Теперь мы увидим, почему именно это интересно.

От коробки к обучению

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

  • Пространство ввода, X: «Пространство ввода» - это всего лишь все возможные поля ввода. В нашем случае поле является нашим входным пространством - мы не знаем, насколько оно велико, мы можем просто сказать, что оно содержит n точек. В нашем случае каждая точка x представляет собой желтый или синий шар.

Желтые шары - это точки, в которых наш h (x) получает правильное значение в соответствии с целевой функцией f (x). Итак, если h (x) совпадает с f (x), то мяч окрашивается в желтый цвет. Если шары окрашены в синий цвет, наша гипотеза не согласуется с целевой функцией. Теперь есть вероятность, связанная с коробкой - цвет, который получает каждая точка, нам не известен, поскольку неизвестно f. Однако, если мы выберем x случайным образом в соответствии с некоторым распределением вероятностей P во входном пространстве X, мы знаем, что x будет желтым с некоторой вероятностью, назовем его µ, и синим с вероятностью 1 - µ.

Независимо от значения µ пространство X теперь ведет себя как в примере с прямоугольником. Проблема обучения теперь сводится к проблеме ящика при предположении, что входные данные в D выбираются независимо в соответствии с некоторым распределением P на X, нашем входном пространстве. Любой P будет транслироваться в некоторый µ в эквивалентном блоке. Поскольку µ может быть неизвестным, то P тоже может быть неизвестным. Теперь нам нужно изменить некоторые обозначения.

  • E_in (h) - v: Мы называем это in-sample of h, Ein (h), потому что мы пытаемся увидеть ошибку аппроксимации цели функции с помощью h.
  • E_out (h) - µ: Out of sample - это то, чего мы не видели - это ошибка обобщения, которая эквивалентна µ.

Это можно напрямую перевести в неравенство Хёффдинга - вместо того, чтобы аппроксимировать разницу между mu и v, мы пытаемся аппроксимировать разницу между E_in и E_out.

Обучение или проверка?

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

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

Однако у нас есть одна проблема - неравенство Хёффдинга не применимо к нескольким коробкам! У нас есть предположение с помощью неравенства Хёффдинга, что функция гипотез фиксируется до набора данных. С несколькими гипотезами, то есть с учетом всего набора гипотез, алгоритм обучения выбирает окончательную гипотезу g на основе D. Это означает, что она выбирается после создания набора данных. Как это решить?

Ослабление ограничений

Способ обойти это - попытаться связать P | E_in (g) - E_out (g) | ›Ε | таким образом, чтобы это не зависело от конкретной выбранной гипотезы. Способ сделать это - взять объединение всех оценок вероятностей для всех гипотез в наборе гипотез, H.

Тогда мы получим следующее неравенство:

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

Заключение

Вывод таков: мы видим, что да, обучение возможно! Принятие вероятностной точки зрения позволяет сделать вывод о возможности обучения. Не требуется даже конкретного распределения вероятностей или даже знания того, какое из них используется. Единственное необходимое предположение - это то, что примеры в наших выборочных данных созданы независимо. Нам также нужно только оценить, насколько хорошо наша выбранная гипотеза g соответствует целевой функции f. Это причина того, что «Неравенство» Хёффдинга так удачно сочетается.

Использованная литература:

— — — — — — — — — — — — — — — — — — — — — — — — -

[1] H-S. Лин, М. Магдон-Исмаил, Ю. С. Абу-Мостафа, Обучение на основе данных - краткий курс (2012).

[2] Я. Син, Понимание ошибки обобщения в машинном обучении (2018), https://medium.com/@yixinsun_56102/understanding-generalization-error-in-machine-learning-e6c03b203036