Краткий обзор алгебры и геометрии, лежащих в основе контролируемого обучения для всех.

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

Измерение Вапника-Червоненкиса, также известное как грубая сила

Если четырех особей (x1,x2,x3,x4) можно разделить на 2 класса (класс A или класс B), то имеется 2^4=16 возможностей классификации: (x1 в A, x2 в A, x3 в A, x4 в A) или (x1 в A, x2 в A, x3 в A, x4 в B) или (x1 в A, x2 в A, x3 в B, x4 в A) и т. д. и т. д. Таким образом, 2^N задач обучения (или возможных меток) могут быть задается N точками данных. Если для всех этих задач обучения мы можем установить h (который принадлежит классу H), который правильно разделяет элементы на два класса, тогда H разбивает N точек. Другими словами, заданные N точек всегда правильно и без ошибки отделяются гипотезой h из H-класса.

Максимальное количество точек, разбиваемых H, называется размерностью Вапника-Червоненкиса (достаточно разбить конкретную выборку из N точек в пространстве, а не любые N точек в 2-мерном измерении). Например, четыре точки можно разбить прямоугольниками, хотя никак, если они выровнены, мы нашли образец, для которого это происходит. Для заданных 4 точек в двух измерениях мы можем найти прямоугольник h, который позволяет правильно разделить любую из 2⁴=16 задач обучения (или возможных маркировок), таким образом, 4 точки разбиваются на H:

Тем не менее, нет никакого способа разбить 5 точек на прямоугольники в двух измерениях. Для любых 5 точек в двух измерениях всегда есть некоторые из 2⁵=32 возможных маркировок, которые не могут быть решены:

Размерность Вапника-Червоненкиса для H, VC(H), равна 4, когда H является гипотетическим классом выровненных по оси прямоугольников в двух измерениях.

Почему я сказал, что это также известно как Brute Force? Что ж, большинство реальных проблем не могут принимать 2 ^ N возможностей. Реальные проблемы обычно обусловлены распределением, из которого взяты их точки, а точки, близкие в пространстве, обычно имеют одну и ту же метку. Нам не нужно беспокоиться обо всех возможных проблемах обучения, и мы собираемся использовать класс гипотез с небольшими размерностями VC по сравнению с другими классами гипотез с более высокими размерностями. Это упростит наш поиск и будет хорошо работать для большинства заданных точек (вы помните определение смещения?). Будут случаи, когда мы не сможем правильно разделить все нарисованные точки на два класса. В таких случаях нам придется сказать, насколько хорош или точен наш класс гипотез, например, он работает нормально с точностью 94 %или он работает с ошибкой менее 3 % более чем в 95 % случаев.

Вероятно, приблизительно правильное обучение, также известное как приближение к реальной жизни

Итак, представьте, что у нас есть гипотеза прямоугольника h из H для решения реальной задачи, точки данных которой взяты из неизвестного распределения вероятностей. Мы хотим найти количество точек, N, для которых гипотеза h имеет ошибку не более E с вероятностью 1- д. Другими словами, если исходным классом из H, который правильно делит все точки, является C,то область различия между C и h будет давать ложноотрицательные результаты при использовании h в качестве гипотезы. Вероятность неправильного присвоения баллов в этом регионе должна быть меньше E (вероятность ошибки) в 1–d% случаев (доверительная вероятность):

Область между C и h — это еще один прямоугольник (теневой прямоугольник на изображении), поэтому его можно разделить на 4 полосы (перекрывающиеся в углах). Вероятность попадания в каждую полосу равна E/4, а вероятность того, что случайно вытянутая точка не попадет в каждую полосу, равна 1-E/4. Вероятность того, что все N независимых точек не попадут в полосу, равна (1-E/4)^N. Кроме того, вероятность того, что все N независимых точек не попадут ни в одну из четырех полос, равна 4(1-E/4)^N. Эта вероятность должна быть не более d, то есть 4(1-E/4)^N‹d. Мы не хотим вдаваться в подробности, но разделив на четыре в обе стороны, взяв бревна и переставив их, получим N ›(4/E)log(4/d). Таким образом, нам нужен по крайней мере этот размер N, чтобы гарантировать эту вероятность ошибки с заданной доверительной вероятностью. В зависимости от класса вашей гипотезы (мы работали с прямоугольниками) необходимо вычислить эту формулу.

Изучение нескольких классов

До сих пор мы сосредоточились на бинарных классификаторах, но что, если классов несколько. Если у нас есть K разных классов, где каждый экземпляр принадлежит только одному из них, мы можем рассматривать это как K двухклассовых задач. Эмпирическая ошибка из обучающего набора X теперь представляет собой сумму прогнозов для всех классов (k) по всем экземплярам (N):

Регрессия

В классификации мы вычисляем эмпирическую ошибку с бинарным поведением: прогноз сделан хорошо или нет. Для данного экземпляра x значение C(x) было либо 0, либо 1. Когда мы не предсказываем классы, а вместо этого предсказываем значения, проблема меняется и называется регрессией. Теперь r является действительным значением и получается из входных данных следующим образом: r=f(x)+E. Мы должны добавить к выходным данным шум E, который представляет эффект скрытых переменных, которые мы не можем видеть. Чтобы быть на 100% точным, мы должны сказать, что r=f*(x,z), где z обозначает скрытые переменные. Если бы не было шума, это была бы интерполяция, а не регрессия (например, f* — это интерполяция). Пожалуйста, обратите внимание, что шум в функции естественного вывода не связан с неточностью записи или ошибками в маркировке, эти ошибки влияют только на прогнозирование.

Таким образом, мы хотим аппроксимировать f(·) с помощью нашего класса гипотез G(·), и эмпирическая ошибка на обучающем наборе X должна учитывать числовое расстояние в выходных данных, а не только равно/не равно, используемое в классификации. Способ учета этого расстояния состоит в том, чтобы использовать квадрат разности:

Наша G(·) может быть линейной, квадратичной или любой другой функцией более высокого порядка. Нам просто нужно заменить G(·) его определением в формуле эмпирической ошибки и минимизировать его, взяв частные производные для коэффициентов w (что является аналитическим решением для параметров). Пожалуйста, обратите внимание, что сначала мы выбираем класс G(·) (например, мы решаем использовать линейную функцию), но как только мы устанавливаем коэффициенты, минимизирующие эмпирическую ошибку, мы получаем экземпляр g(·) из класса G (·). Какой G(·) выбрать? Как я уже говорил в предыдущей статье, при увеличении порядка функции ошибка обучения уменьшается, но вы можете попасть в переобучение.

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

Библиография

Введение в машинное обучение. Четвертое издание. Этем Алпайдин. Издательство Массачусетского технологического института 2020.