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

Что такое M

Прежде чем продолжить, давайте сначала посмотрим на неравенство, с которым мы работаем:

Где у нас есть следующие компоненты:

  • M: размер нашей гипотезы, H.
  • N: размер выборки.
  • E_in (h): ошибка в выборке h.
  • E_out (h): ошибка вне выборки h.
  • ε: это наша допустимая величина отклонения E_in от E_out.

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

Граница утверждает, что если мы выберем уровень допуска, δ, и тогда мы сможем с вероятностью не менее 1 - δ утверждать, что граница выполняется. Но для начала мы будем работать с первой версией.

Как уже говорилось, у нас есть настоящая проблема, когда M бесконечно, но давайте сначала снова поймем, откуда M в нашем неравенстве. В предыдущей статье мы упоминали, что это связано с объединением всех наших гипотез в наборе гипотез. Что подразумевается под объединением этих гипотез? Когда мы берем границу для единственной гипотезы, мы ограничиваем вероятность плохого события - точнее, то, что наша ошибка в выборке отклоняется от нашей ошибки вне выборки больше, чем наш допуск, ε. Математически это можно записать так:

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

Гарантируется, что это будет включать нашу финальную гипотезу g, поскольку она является объединением всех наших гипотез в H. Поскольку g всегда находится в H, мы уверены, что граница всегда включает g. Мы можем проиллюстрировать это объединение плохих событий на конкретном примере. Допустим, у нас есть 4 гипотезы в нашем наборе гипотез.

Граница объединения говорит о том, что общая площадь, охватываемая Event_1, Event_2, Event_3 или Event_4, меньше суммы отдельных областей. Это утверждение явно верно, но мы также можем видеть, насколько эти четыре гипотезы пересекаются, что граница очень слабая. Мы можем показать это наглядно:

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

Функция роста

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

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

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

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

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

Поскольку это верхняя граница - значит ли это, что у нас может быть меньше максимального количества гипотез? Да, и это называется точкой останова. Формально точка разрыва определяется как когда H не может сгенерировать все дихотомии на определенном наборе данных размера k. Тогда k - точка излома для набора гипотез. Это будет интересно позже, когда мы попытаемся заменить M функцией роста, но давайте сначала рассмотрим пример точки останова.

Мы могли видеть, что можно разбить все созвездия из 3 точек - следовательно, 3 не является точкой излома для 2-мерного персептрона. Если вместо этого мы попытаемся разбить 4 точки, то внезапно столкнемся с проблемой в случае 15 и 16 (последние два квадрата). Как бы мы ни поворачивали или крутили точки, мы не сможем правильно их классифицировать по нашей линии! Следовательно, мы можем сказать, что 4 - это точка останова для 2-мерного персептрона. Если мы вернемся к функции роста, это означает, что мы можем сказать, что верно следующее:

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

Теперь мы нашли способ ограничить функцию роста, если мы знаем точку останова нашей модели. Есть ли более простой способ определить это?

Размеры VC

Определение размеров VC напрямую связано с точкой останова - она ​​определяется как наибольшее значение N, для которого:

Если это количество возможных дихтомий для всех возможных N, то размерность VC равна бесконечности. Следовательно, мы можем сказать, что размеры ВК равны k - 1, где k является точкой останова нашей модели. Эта линия кажется вам знакомой? Это означает, что мы можем переписать нашу оценку функции роста более простым способом:

Теперь может показаться, что мы далеко отошли от того, что мы намеревались сделать - заменить M в нашем исходном неравенстве на что-то лучшее. Так почему же потрачено все это время на определение размеров VC и точки останова? Потому что мы могли бы заменить его на M, хотя и не напрямую!

Замена M

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

Эта оценка утверждает, что если мы выберем уровень толерантности, δ, и тогда мы сможем с вероятностью не менее 1 - δ утверждать, что оценка выполняется. Эта граница устанавливает возможность обучения с бесконечным набором гипотез благодаря рассмотрению выборок, а не всего входного пространства. Если мы будем основывать его на измерении VC вместо функции роста, то мы получим следующую оценку:

Мы можем визуально показать влияние замены M на VC:

Мы предполагаем, что прямоугольник, наш холст, представляет собой пространство всех наборов данных с областями, соответствующими вероятностям. Для гипотезы цветные точки соответствуют наборам данных, где E_in плохо обобщается на E_out (то есть, наши предыдущие определенные плохие события!). Неравенство Хёффдинга гарантирует небольшую вероятность - следовательно, небольшую окрашенную область. С M у нас есть граница объединения - поэтому он не предполагает перекрытий, поэтому цветная область большая. Размер VC предполагает перекрытие между гипотезами, поэтому цветная область меньше, чем с границей объединения.

Заключение

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

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

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

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