017. Методы отбора признаков. Отбор признаков - К. В. Воронцов

Оценка качества методов обучения

0:10

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

Задача отбора признаков

3:50

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

Эвристики для решения задачи отбора признаков

8:29

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

Алгоритм полного перебора

9:44

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

Эвристический параметр

11:24

Эвристический параметр определяет количество шагов после минимума функционала.
Если текущая g больше или равна д, алгоритм возвращает оптимальный набор признаков.

Недостатки алгоритма

13:57

Если оптимальное число признаков большое, алгоритм будет работать долго.
Может возникнуть вторичное переобучение из-за большого количества вариантов.
Оптимизация по одному дискретному параметру может привести к небольшому переобучению.

Алгоритм жадного добавления

16:19

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

Алгоритм удаления признаков

24:11

Алгоритм удаляет признаки по одному, начиная с наименее выгодного.
Стратегия: два шага вперед-шаг назад, удаление одного признака после добавления двух.

Объединение алгоритмов

28:38

Эвристики для объединения алгоритмов: два добавили, один удалили, добавление и удаление пар и троек признаков.
Эффективные алгоритмы для линейной регрессии: шаговая регрессия или степ-вайс регрессия.

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

30:55

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

Поиск в глубину и ветви границ

39:44

В видео объясняется, как использовать поиск в глубину для сокращения перебора и оценки перспективности подмножеств признаков.
Упоминается, что поиск в ширину также может быть использован для этой цели.

Оценка перспективности подмножеств признаков

41:02

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

Рекурсивный алгоритм отбора признаков

43:33

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

Поиск в ширину и метод группового учета аргументов

48:11

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

Определение ряда и ширины поиска

52:14

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

Метод группового учета аргументов

55:08

В методе группового учета аргументов (МГУА) используется алгоритм поиска в ширину для отбора признаков.
Трудоемкость алгоритма порядка n^2, где n - количество признаков.
Отбор признаков происходит путем построения всех возможных наборов признаков и обучения на них.
Проблема с дубликатами решается путем сортировки по убыванию значения функционала.

Генетический алгоритм

1:04:45

Генетический алгоритм похож на метод группового учета аргументов, но использует бинарные векторы для кодирования признаков.
В генетическом алгоритме используются операции скрещивания и мутации для создания новых поколений.
Трудоемкость алгоритма зависит от параметров, таких как вероятность мутации и количество поколений.
В отличие от МГУА, в генетическом алгоритме нет ограничения на мощность наборов признаков.

Генетические алгоритмы

1:11:05

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

Островная модель эволюции

1:13:15

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

Случайный поиск с адаптацией

1:17:23

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

Адаптация случайного поиска

1:21:41

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

Параметры и ориентиры

1:29:48

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

Эффективность и ограничения

1:34:53

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

Отбор признаков

1:37:32

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

Практические задачи и отбор признаков

1:39:26

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

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

1:40:23

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

017. Методы отбора признаков. Отбор признаков - К. В. Воронцов

Ключевые темы и таймкоды

Оценка качества методов обучения

Задача отбора признаков

Эвристики для решения задачи отбора признаков

Алгоритм полного перебора

Эвристический параметр

Недостатки алгоритма

Алгоритм жадного добавления

Алгоритм удаления признаков

Объединение алгоритмов

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

Поиск в глубину и ветви границ

Оценка перспективности подмножеств признаков

Рекурсивный алгоритм отбора признаков

Поиск в ширину и метод группового учета аргументов

Определение ряда и ширины поиска

Метод группового учета аргументов

Генетический алгоритм

Генетические алгоритмы

Островная модель эволюции

Случайный поиск с адаптацией

Адаптация случайного поиска

Параметры и ориентиры

Эффективность и ограничения

Отбор признаков

Практические задачи и отбор признаков

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