[ОТСУТСТВУЕТ_ЗВУК] В

этом видео мы поговорим о жадных методах отбора признаков, которые позволяют

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

Итак, мы уже в первом видео этого урока упоминали такие методы.

Они, по сути, являются надстройками над методами обучения моделей.

То есть они перебирают каким-то образом различные подмножества признаков,

для каждого подмножества строят модель, оценивают ее качество и выбирают то

подмножество, которое дает наилучшее качество этой модели машинного обучения.

Как устроен этот процесс?

Мы считаем обучение модели черным ящиком, который на вход

принимает информацию о том, как какие из его признаков можно использовать при

обучении модели, обучает модель, и дальше как-то мы оцениваем ее качество.

Например, по отложенной выборке, кросс-валидации или как-то еще.

По сути, здесь должна решаться задача оптимизации этого

черного ящика по подмножеству признаков.

Подмножество признаков — это дискретный объект, и мы приходим к задаче дискретной

оптимизации, которые, как правило, очень сложные.

И вряд ли можно придумать что-то лучше, чем полный перебор

всех возможных вариантов, то есть всех подмножеств признаков.

Собственно, так вот подходим к первому способу отбора признаков.

Полный перебор.

Мы пробуем все возможные подмножества признаков и оцениваем их качество.

Выбираем то, которое оказывается лучше всего.

Можно немного структурировать перебор и перебирать подмножества последовательно.

Сначала те, которые имеют мощность 1, то есть наборы из 1 признака,

потом наборы из 2 признаков, наборы из 3 и так далее.

Это подход очень хороший, он найдет оптимальное подмножество признаков,

но при этом очень сложный, поскольку всего таких подмножеств 2 в степени d,

где d — это число признаков.

Если признаков много — сотни или тысячи, то такой перебор невозможен.

Он займет слишком много времени,

возможно даже за вашу жизнь вы не успеете узнать правильный ответ.

Поэтому такой метод подходит только для небольшого количества признаков.

Если их 10, то вы вполне можете найти оптимальное подмножество.

Или, например, он может быть неплох, если вы знаете, что информативных признаков,

признаков, которые важны для решения задачи, очень мало, единицы.

Если же признаков много и вы знаете,

что информативных признаков тоже много, то нужна какая-то жадная стратегия.

Жадная стратегия используется всегда,

когда полный перебор не подходит для решения той или иной задачи.

Например, может оказаться неплохой стратегия жадного наращивания,

жадного добавления.

Сначала мы находим один признак, который дает наилучшее качество модели.

То есть такой один признак, что если над ним построить модель,

она получится лучшей среди всех моделей над одним признаком.

Обозначим его как i1, это его индекс, и обозначим множество,

состоящее из этого одного признака, как J1.

Дальше попытаемся добавить к этому множеству еще один признак так,

чтобы как можно сильнее уменьшить ошибку модели.

То есть мы будем перебирать все признаки i,

добавлять их к признаку i1, строить над этим модели и оценивать их ошибку.

Функция Q как раз оценивает ошибку модели, построенной на подмножестве признаков,

которые передаются ей в качестве аргументов.

Мы находим признак i, который дает наименьшее значение ошибки,

обозначаем его как i2 и добавляем к нашему подмножеству признаков J.

Теперь оно будет обозначаться как J2, поскольку в нем 2 признака.

И так далее будем продолжать эту процедуру,

добавляя по одному признаку к нашим множествам.

Будем получать множество J3, J4 и так далее.

Продолжаем это до тех пор, пока ошибка уменьшается.

Если в какой-то момент мы не сможем добавить новый признак так,

чтобы уменьшить ошибку, мы остановим процедуру.

Обратите внимание, что в этом случае,

как только мы добавили признак на какой-то итерации,

он навсегда остается в подмножестве признаков, мы не можем его удалить.

Именно в этом и заключается жадность процедуры.

Этот подход довольно быстрый.

В нем столько итераций, сколько признаков в выборке.

Но при этом он слишком жадный.

Если мы добавили признак, мы уже не можем его удалить.

Мы перебираем слишком мало вариантов, и хочется как-то усложнить эту процедуру.

Один из подходов к усложнению — это алгоритм ADD-DEL,

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

Давайте обсудим, как он работает.

Начинаем мы с того, что проводим процедуру жадного добавления.

Наращиваем множество признаков до тех пор, пока получается уменьшить ошибку.

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

То есть мы перебираем все возможные варианты удаления признака,

оцениваем ошибку и удаляем тот,

который приводит к наибольшему уменьшению ошибки на выборке.

Повторяем такую процедуру удаления до тех пор, пока уменьшается ошибка.

Как только мы дошли до момента, когда мы не можем уменьшить ошибку удалением

признака, снова начинаем добавлять их и так далее.

То есть эта процедура повторяет добавление и удаление признаков до тех пор,

пока уменьшается ошибка.

Этот алгоритм всё еще жадный, но при этом он менее жадный, чем предыдущий,

посколько он может исправлять ошибки, сделанные в начале перебора.

Если мы вначале добавили какой-то признак, который был не очень хороший,

то на этапе удаления можем его устранить и добавить какой-то более подходящий для

решения этой задачи.

Итак, мы обсудили подход к отбору признаков,

который оптимизирует качество произвольной модели.

И алгоритм обучения модели мы рассматриваем как некий черный ящик,

который принимает на вход только подмножества признаков.

Это очень прямой подход к решению задачи отбора признаков, но при этом он приводит

к задаче дискретной оптимизации, которая сложная и решать ее можно либо перебором,

что может быть слишком трудозатратно, либо жадными алгоритмами.

Например, жадным добавлением или алгоритмом ADD-DEL.

А в следующем видео мы поговорим о том,

как отбирать признаки с помощью моделей машинного обучения.

Жадные методы отбора признаков

Поиск структуры в данных

Meet the Instructors