Введение В этой статье я решил осветить некоторые фундаментальные результаты теории машинного обучения таким образом, чтобы концепции были понятны читателям, имеющим некоторые знания в области классификации и регрессии.
Идея написания такой статьи становилась все более ясной в моем сознании с каждой прочитанной книгой, в которой идеи обучения машин распознаванию рассказывались как бы с середины и было совершенно непонятно, что авторы этой или этот метод использовался при его разработке.
С другой стороны, существует ряд книг, посвященных основным понятиям машинного обучения, но изложение материала в них может показаться слишком сложным для первого чтения.
Мотивация
Давайте рассмотрим эту проблему.У нас есть яблоки двух классов – вкусные и не вкусные, 1 и 0. У яблок есть характеристики – цвет и размер.
Цвет будет непрерывно меняться от 0 до 1, т.е.
0 – полностью зеленое яблоко, 1 – полностью красное яблоко.
Размер может меняться таким же образом, 0 – маленькое яблоко, 1 – большое.
Мы хотели бы разработать алгоритм, который бы на входе получал цвет и размер, а выдавал класс яблока — вкусное оно или нет. Очень желательно, чтобы чем меньше было ошибок, тем лучше.
При этом у нас есть окончательный список, содержащий исторические данные о цвете, размере и классе яблок.
Как мы могли бы решить такую проблему?
Логический подход
При решении нашей задачи первый метод, который может прийти на ум, может быть такой: давайте вручную создадим правила типа if-else и в зависимости от значений цвета и размера присвоим яблоку определенный класс.Те.
у нас есть предпосылки – цвет и размер, и есть следствие – вкус яблока.
Это вполне разумно, когда признаков мало и пороги можно оценить на глаз для сравнения.
Но может случиться так, что четких условий придумать не удастся, и из данных не будет очевидно, какие пороги брать, и количество признаков может увеличиться в будущем.
Что делать, если в нашем списке с историческими данными мы нашли два яблока одинакового цвета и размера, но одно помечено как вкусное, а другое нет? Таким образом, наш первый метод не такой гибкий и масштабируемый, как хотелось бы.
Обозначения
Введем следующие обозначения.
Мы будем обозначать
ох, как яблоко
.
В свою очередь, каждый
состоит из двух цифр - цвета и размера.
Обозначим этот факт парой цифр:
.
Класс каждого
мы обозначаем i-е яблоко как
.
Список с историческими данными будет обозначаться буквой
, длина этого списка равна
.
Четвертый элемент этого списка — значение атрибутов яблока и его класс.
Те.
.
Мы назовем это так же
выборка.
Заглавными буквами
И
мы будем обозначать переменные, которые могут принимать значения определенного признака и класса.
Вводим новую концепцию – решающее правило
есть функция, которая принимает на вход цвет и размер
и возвращает метку класса в качестве вывода:
Вероятностный подход
Развивая идею логического метода с посылками и следствиями, зададим себе вопрос – какова вероятность того, что-е яблоко, не принадлежащее нашей выборке
будет ли он вкусным при соблюдении измеренных значений цвета и размера? В обозначениях теории вероятностей этот вопрос можно записать так:
Это выражение можно интерпретировать
как посылка,
как следствие, но переход от предпосылки к следствию будет подчиняться вероятностным, а не логическим законам.
Те.
Вместо таблицы истинности с логическими значениями 0 и 1 для класса будут значения вероятности в диапазоне от 0 до 1. Примените формулу Байеса и получите следующее выражение:
Давайте рассмотрим правую часть этого выражения более подробно.
Фактор
называется априорной вероятностью и означает вероятность найти вкусное яблоко среди всех возможных яблок.
Априори есть вероятность встретить плохое яблоко
.
Эта вероятность может отражать наши личные знания о том, насколько вкусны и невкусны яблоки, распространенные в природе.
Например, из нашего прошлого опыта мы знаем, что 80% всех яблок вкусные.
Или мы можем оценить это значение, просто посчитав долю вкусных яблок в нашем списке с историческими данными S. Следующий фактор —
показывает, насколько вероятно получить определенное значение цвета и размера
для яблока 1 класса.
Это выражение также называется функцией правдоподобия и может принимать вид определенного распределения, например нормального.
Знаменатель
мы используем в качестве константы нормализации, чтобы искомая вероятность
варьировалось от 0 до 1. Наша конечная цель — не поиск вероятностей, а поиск решающего правила, которое сразу дало бы нам класс.
Окончательный вид решающего правила зависит от того, какие значения и параметры нам известны.
Например, мы можем знать только значения априорной вероятности, а остальные значения оценить невозможно.
Тогда решающим правилом будет следующее: присвоить всем яблокам значение того класса, для которого априорная вероятность наибольшая.
Те.
если мы знаем, что 80% яблок в природе вкусные, то каждому яблоку присвоим класс 1. Тогда наша ошибка составит 20%.
Если мы сможем также оценить значения функции правдоподобия $p(X=x_m | Y=1)$, то мы сможем найти значение искомой вероятности
по формуле Байеса, как написано выше.
Решающим правилом здесь будет следующее: ставьте метку на класс, для которого вероятность
максимум:
Назовем это правило байесовским классификатором.
Поскольку мы имеем дело с вероятностями, даже большое значение вероятности
не гарантирует, что яблоко
не принадлежит классу 0. Оценим вероятность ошибки на яблоке
следующим образом: если решающее правило вернуло значение класса, равное 1, то вероятность ошибки будет равна
и наоборот:
Нас интересует вероятность ошибки классификатора не только в этом конкретном примере, но и в целом для всех возможных яблок:
Это выражение представляет собой ожидаемое значение ошибки.
.
Итак, решив исходную задачу, мы пришли к байесовскому классификатору, но каковы его недостатки? Основная проблема состоит в том, чтобы оценить условную вероятность по данным
.
В нашем случае мы представляем объект парой чисел – цвет и размер, но в более сложных задачах размерность признаков может быть в разы выше и количества наблюдений из нашего списка с историческими данными может оказаться недостаточно для оценки вероятность многомерной случайной величины.
Далее мы попытаемся обобщить наше понятие об ошибке классификатора, а также посмотрим, можно ли выбрать какой-либо другой классификатор для решения задачи.
Потери от ошибок классификатора
Предположим, что у нас уже есть какое-то решающее правило.
.
Тогда он может допускать два типа ошибок: первый — относить объект к классу 0, реальный класс которого равен 1, и наоборот — относить объект к классу 1, реальный класс которого равен 0. В некоторых задачах это важно различать эти случаи.
Например, мы страдаем сильнее, когда яблоко, на этикетке которого написано вкусное, оказывается безвкусным и наоборот. Формализуем в понятии степень нашего дискомфорта от разочарованных ожиданий.
В более общем смысле у нас есть функция потерь, которая возвращает число для каждой ошибки классификатора.
Позволять
- настоящий ярлык класса.
Тогда функция потерь
возвращает значение потери для реальной метки класса
и смысл нашего решающего правила
.
Пример использования этой функции — взятие из яблока известного класса
мы передаем яблоко в качестве входных данных для нашего правила принятия решения
, мы получаем оценку класса из решающего правила, если значения
И
совпадение, то считаем, что классификатор не ошибся и потерь нет; если значения не совпадают, то наша функция подскажет сумму потерь
Условный и байесовский риск
Теперь, когда у нас есть функция потерь, мы знаем, сколько мы потеряем из-за неправильной классификации объекта.
, было бы неплохо понять, сколько мы в среднем теряем на многих сайтах.
Если мы знаем значение
- вероятность того, что
-е яблоко будет вкусным при условии измеренных значений цвета и размера, а также реальной ценности класса (например, возьмем яблоко образца S, см.
в начале статьи), тогда мы можно ввести понятие условного риска.
Условный риск – это среднее значение потерь на объекте.
для решающего правила
:
В нашем случае бинарной классификации, когда
оказывается:
Когда а(х) =0
Для расчета средних потерь для всех возможных объектов вводится понятие байесовского риска, который представляет собой математическое ожидание условного риска:
Выше мы описали решающее правило, которое относит объект к классу, имеющему наибольшее значение вероятности.
Это правило обеспечивает минимум наших средних потерь (байесовского риска), поэтому байесовский классификатор является оптимальным с точки зрения введенного нами функционала риска.
Это означает, что байесовский классификатор имеет наименьшую возможную ошибку классификации.
Некоторые типичные функции потерь
Одной из наиболее распространенных функций потерь является симметричная функция, когда потери от первого и второго типов ошибок эквивалентны.
Например, функция потерь 1-0 (потери ноль-единица) определяется следующим образом:
Тогда условный риск для a(x) = 1 будет просто значением вероятности получить на объекте класс 0.
:
Аналогично для a(x) = 0:
Функция потерь 1-0 принимает значение 1, если классификатор допускает ошибку в объекте, и 0, если нет. Теперь убедимся, что значение ошибки равно не 1, а другой функции Q, в зависимости от решающего правила и реальной метки класса:
Тогда условный риск можно записать следующим образом:
Примечания к обозначениям
Предыдущий текст был написан по обозначениям, принятым в книге Дуды и Харта.В оригинальной книге В.
Н.
Вапник рассмотрел следующий процесс: природа выбирает объект согласно распределению $p(x)$, а затем присваивает ему метку класса согласно условному распределению $p(y|x)$.
Тогда риск (ожидание потерь) определяется как
Где
- функция, с помощью которой мы пытаемся аппроксимировать неизвестную зависимость,
— функция потерь для реальной стоимости
и значения нашей функции
.
Эти обозначения более понятны для введения следующего понятия – эмпирического риска.
Эмпирический риск
На этом этапе мы уже выяснили, что логический метод нам не подходит, поскольку он недостаточно гибок, и мы не можем использовать байесовский классификатор, когда признаков много, а количество обучающих данных ограничено и мы не может восстановить вероятность.
Мы также знаем, что байесовский классификатор имеет наименьшую возможную ошибку классификации.
Поскольку мы не можем использовать байесовский классификатор, давайте воспользуемся чем-то более простым.
Зафиксируем некоторое параметрическое семейство функций H и выберем из этого семейства классификатор.
Пример: пусть
набор всех функций вида
Все функции этого набора будут отличаться друг от друга только коэффициентами
Когда мы выбирали такое семейство, мы предполагали, что в координатах цвет-размер можно провести прямую с коэффициентами между точками класса 1 и точками класса 0.
таким образом, чтобы точки разных классов располагались по разные стороны линии.
Известно, что линия такого типа имеет вектор коэффициентов
нормально к линии.
Теперь делаем следующее — берем наше яблоко, измеряем его цвет и размер и наносим точку с полученными координатами на график в осях цвет-размер.
Далее измеряем угол между этой точкой и вектором $w$.
Заметим, что наша точка может лежать как по одну, так и по другую сторону прямой.
Тогда угол между
и точка будет либо острой, либо тупой, а скалярное произведение будет либо положительным, либо отрицательным.
Это приводит к решающему правилу:
После того как мы зафиксировали класс функций $H$, возникает вопрос: как выбрать из него функцию с нужными коэффициентами? Ответ: давайте выберем функцию, которая минимизирует наш байесовский риск $R()$.
Опять же проблема в том, что для расчета значений байесовского риска необходимо знать распределение $p(x,y)$, а оно нам не дано и восстановить его не всегда возможно.
Другая идея — минимизировать риск не на всех возможных объектах, а только на выборке.
Те.
функция минимизации:
Эта функция называется эмпирическим риском.
Следующий вопрос: почему мы решили, что, минимизируя эмпирический риск, мы также минимизируем и байесовский риск? Напомню, что наша практическая задача — допустить как можно меньше ошибок классификации.
Чем меньше ошибок, тем ниже байесовский риск.
Обоснование сходимости эмпирического риска к байесовскому риску при увеличении объема данных было получено в 70-е годы двумя учеными - В.
Н.
Вапником и А.
Я.
Червоненкис.
Гарантии конвергенции.
Самый простой случай Итак, мы пришли к выводу, что байесовский классификатор дает наименьшую возможную ошибку, но в большинстве случаев мы не можем его обучить и также не можем рассчитать ошибку (риск).
Однако мы можем рассчитать приближение к байесовскому риску, который называется эмпирическим риском, и, зная эмпирический риск, выбрать аппроксимирующую функцию, которая бы минимизировала эмпирический риск.
Давайте рассмотрим простейшую ситуацию, когда минимизация эмпирического риска дает классификатор, который также минимизирует байесовский риск.
В простейшем случае нам придется сделать допущение, которое на практике редко выполняется, но которое позже можно ослабить.
Зафиксируем последний класс функций
из которого мы выберем наш классификатор и предположим, что реальная функция, которую природа использует для классификации наших яблок по вкусам, находится в этом конечном наборе гипотез:
.
У нас также есть выбор
, полученный из распределения
над объектами
.
Мы считаем, что все образцы объектов одинаково независимо распределены (iid).
Тогда будет верно следующее
Теорема
Выбор функции из классаминимизируя эмпирический риск, мы гарантированно найдем такие
что он имеет небольшое значение байесовского риска, если выборка, на которой мы выполняем минимизацию, имеет достаточный размер.
Что означает «небольшая величина» и «достаточный размер», смотрите в литературе ниже.
Идея доказательства
По условиям теоремы получаем выборкуот распространения
, т. е.
процесс отбора объектов из природы носит случайный характер.
Каждый раз, когда мы собираем выборку, она будет из одного и того же дистрибутива, но сами объекты могут быть разными.
Основная идея доказательства в том, что мы можем получить вот такую плохую выборку
, что алгоритм, который мы выберем, используя минимизацию эмпирического риска на заданной выборке, будет плохо минимизировать байесовский риск, но в то же время будет хорошо минимизировать эмпирический риск, но вероятность получения такой выборки мала и по мере увеличения размера выборки эта вероятность уменьшается.
Подобные теоремы существуют и для более реалистичных предположений, но мы не будем их здесь рассматривать.
Практические результаты
Имея доказательства того, что функция, найденная путем минимизации эмпирического риска, не будет иметь большой ошибки на ранее ненаблюдавшихся данных при достаточном размере обучающей выборки, мы можем использовать этот принцип на практике, например, следующим образом – возьмем выражение:И подставляем разные функции потерь в зависимости от решаемой задачи.
Для линейной регрессии:
Для логистической регрессии:
Хотя машины опорных векторов имеют в первую очередь геометрическую мотивацию, их также можно рассматривать как эмпирическую задачу минимизации риска.
Заключение
Многие методы обучения с учителем можно рассматривать, в том числе, как частные случаи теории, развитой В.Н.
Вапником и А.
Я.
Червоненкис.
Эта теория дает гарантии относительно ошибки на тестовой выборке при условии достаточного размера обучающей выборки и определенных требований к пространству гипотез, в котором мы ищем наш алгоритм.
Подержанные книги
- Природа статистической теории обучения, Владимир Н.
Вапник
- Классификация шаблонов, 2-е издание, Ричард О.
Дуда, Питер ?.
Харт, Дэвид Г.
Сторк
- Понимание машинного обучения: от теории к алгоритмам, Шай Шалев-Шварц, Шай Бен-Дэвид
П.
П.
С.
Большое спасибо авторам этот статьи для редактора TeX Теги: #распознавание образов #Машинное обучение
-
Код Аль-Каиды Взломан
19 Oct, 24 -
Спасите Проект: Самые Важные Вопросы
19 Oct, 24 -
Квантовая Физика: Декогеренция
19 Oct, 24 -
Аутсорсинг Интернет-Магазинов
19 Oct, 24
