Pull to refresh

Comments 22

Спасибо за статью!

А чем отличается расчет information gain от простого расчета корреляции между фичами и целевой переменной?
Вам спасибо за комментарий.
Если под корреляцией вы подразумеваете линейный коэффициент корреляции, то метод расчета у них совсем разный. Я его не использовала и даже в статьях его упоминаний не видела, так что ничего не могу сказать про эффективность, к сожалению.
Спасибо!

Возникли следующие вопросы:
  1. По какому принципу выбирается целевая переменная, что делать в случае высокой размерности фич?
  2. Как оценивается точность отбора фич?
  3. Довольно часто после выделения фич применяется не классификация, а кластеризация. Как от этого может поменяться выбор метода и как оценить качество кластеризации?
Постараюсь ответить (если я неправильно пойму какой-либо вопрос – поправьте меня).

1. У нашего анализа, как правило, есть цель – предсказать что-либо (погоду, цену на рынке, тип документа, объект на фотографии). Она и обуславливает выбор целевой переменной, т.е. объекта предсказания. При слишком большом количестве фич (большой размерности массива) можно избавиться от части используя методы фильтрации, можно уменьшить размерность (dimensionality reduction методы, например, PCA).
2. Тут довольно просто. Следует использовать кросс валидацию и оставлять некоторое количество как тестовый сет. На нем можно оценить эффективность, сравнив точность классификатора на полном и на урезанном массиве фич.
3. Самый сложный вопрос потому, что самый объемный. Я не смогу сейчас описать все возможные методы и нюансы, связанные с unsupervised learning (как правило, кластеризация используется в этом случае). Для такого случая для уменьшения размерности фич можно применять feature extraction методы.
  1. Извиняюсь, это я не сразу понял, что вы назвали целевой переменной. Я подумал, что целевая переменная — это одна из компонент дескриптора фичи. Если рассмотреть область поиска изображений, то в случае с SIFT это одна из 128 компонент.
  2. Вот такой подход меня всегда смущает. Насколько корректно оценивать качество отбора по результатам классификации? Ведь результат классификации очень сильно зависит от самого классификатора. И при выборе неподходящего метода классификации можно получить результаты далекие от правды.
  3. А разве перед отбором фич их не надо получить? Вы же в любом случае будете применять feature extraction методы.
Проблема отбора фич очень неоднозначная — прежде всего потому, что разные методы могут давать диаметрально противоположные результаты: univariate filters дают один набор переменных, а, скажем, feature selection using genetic algorithms — совершенно другой. В R для модуля caret есть неплохой мануал по этой теме. Вот еще практическая реализация простого и относительно универсального метода «перетасовок».
Постараюсь ответить (если я неправильно пойму какой-либо вопрос – поправьте меня).

1. У нашего анализа, как правило, есть цель – предсказать что-либо (погоду, цену на рынке, тип документа, объект на фотографии). Она и обуславливает выбор целевой переменной, т.е. объекта предсказания. При слишком большом количестве фич (большой размерности массива) можно избавиться от части используя методы фильтрации, можно уменьшить размерность (dimensionality reduction методы, например, PCA).
2. Тут довольно просто. Следует использовать кросс валидацию и оставлять некоторое количество как тестовый сет. На нем можно оценить эффективность, сравнив точность классификатора на полном и на урезанном массиве фич.
3. Самый сложный вопрос потому, что самый объемный. Я не смогу сейчас описать все возможные методы, связанные с unsupervised learning (как правило, кластеризация используется в этом случае). Для такого случая для уменьшения размерности фич можно применять feature extraction методы.
Ошиблась с ответом, извините.
Методы фильтрации не идеальны, поэтому, разумеется, могут давать разный результат. Хотя на счет диаметрально мне сложно поверить. У вас были такие случаи?
Из сравнительно недавних — соревнование на Kaggle: в датасете 41 фича, из них 37 анонимные (P* — неизвестно, что они на самом деле означают).

FS with genetic algorithm (5-fold CV): «P5»,«P13»,«P14»,«P16»,«P17»,«P18»,«P19»,«P20»,«P21»,«P23»,«P24»,«P27»,«P28»,«P30»,«P32»,«P33»,«P36».
FS with simulated annealing (5-fold CV): «P1»,«P2»,«P3»,«P4»,«P7»,«P8»,«P13»,«P17», «P20»,«P21»,«P22»,«P28»,«P34»,«P35»,«P37».

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

Подскажите, какая целевая функция минимизировалась в обоих случаях?
Можно придумать искусственный пример, когда разные алгоритмы (или разные реализации одного алгоритма) в итоге сойдутся к разным наборам фич. Например, взять исходное множество признаков и «продублировать» каждый признак. Т.к. в итоге получится минимум по два полностью скореллированных признака, то алгоритмы типа mrmr могут выбрать случайный из них.
Обзор неплох, но слегка поверхностен. Мне было интересно почить про методы включения и ислючения, но не хватает обзора их недостатков.

Для взаимной информации, названной у вас information gain, как меры связи между предиктором и зависимой переменной (кстати, не упомянули, что ее можно посчитать и между набором предикторов и зависимой переменной), характерна одна большая проблема, которая, кстати, решается (об этом также не сказано): предиктор может обладать настолько большой энтропией, что будет прекрасно якобы детерминировать зависимую переменную на обучающей выборке, однако вся кажущаяся детерминированность пропадет при проверке на независимой выборке. Пример: есть 100 наблюдений, предиктор с 90 уровнями встречающимися в тесте.

Для метода mRmR характерна одна тоже большая проблема (расчет получается очень не точный): брать сумму значений взаимной информации для каждой пары предиктор-зависимая переменная корректно лишь в том случае, если предикторы независимы между собой. Иначе можно получить огромную избыточную взаимную информацию. Также не корректно усреднять взаимную информацию между предикторами, когда есть корректный метод, называемый multiinformation.

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

Вы правы, что в смысле точности никакой из методов фильтрации не сравнится с wrapper. Но недостаток wrapper-методов (стоимость вычислений) очень весомый. Если есть возможность тренировать модель на всем объеме фич, то проще и лучше использовать классификатор с регуляризацией. Это будет дешевле в смысле вычислений, и точность не хуже.
Ниша методов фильтрации — случаи, когда тренировать модель на всем объеме фич мы просто не можем – памяти не хватает. Тогда другие методы не сработают.
Посмотрите здесь, это наверное лучшее, что я видел по методам включения-исключения.
Поддерживаю, как раз этот эффект я и наблюдал. Случайная величина (равномерное распределение, наивысшая энтропия из возможных) при некоторых условиях (малая выборка либо высокое число степеней свободы) начинает казаться значимым предиктором. Это знак, что поиск очередной «лучшей влияющей величины» следует прекращать )
Вопрос про mrmr: вы пишете, что приведенные методы фильтрации, к которым также относится mrmr, хороши тем, что их стоимость зависит линейно от количества фич. Но разве алгоритм mrmr работает за линейное время?

Правильно ли я понимаю, как работает алгоритм:
1) Проходим по всем признакам, для каждого признака считаем выражение с учетом текущего множества «отобранных».
2) Выбираем признак, для которого значение этого выражения было максимально.
3) Если добавление нового признака улучшает значение функции, то добавляем признак в множество «отобранных» и возвращаемся к пункту 1.

То есть, так как формула считается за O(|S|^2), при этом она на каждый новый признак будет вызываться порядка |X|(кол-во признаков) раз, а в худшем случае мы будем добавлять все признаки из X, то алгоритм работает за квадратичное от количества признаков время. Или я что-то не так понял?
Edit: не квадратичное, а четвертая степень.

И даже если есть какие-либо методы всё это дело ускорить, не вижу возможности сделать алгоритм быстрее, чем квадратичным — при рассчете redundancy нужно пройтись по всем парам признаков.
Видимо из-за неточности в обзоре mRmR выдан за фильтрующий метод отбора, тогда как он суть метод расчета фитнесс функции.

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

А можно подробнее про это? Может быть, вы можете посоветовать каую-нибудь статью
Я статью не могу порекомендовать.

Пример приведу, который мне близко знаком.

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

Можно таким же образом использовать mRmR, например, в паре с алгоритмом включения или исключения предикторов.

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

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

В чем его неверность:

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

А еще более подробно: если предикторы взаимосвязаны (взаимная информация между ними не нулевая), то их сумма взаимной информации будет больше (избыточнее), чем взаимная информация их взаимодействий. А если переменные по отдельности не влияют на зависимую переменную, но их взаимодействия влияют, то взаимная информация, передаваемая их взаимодействием, будет больше, чем их атомарные взаимные информации.
Все верно, спасибо за замечание (чуть позже исправлю в статье). Статья писалась не линейно, и кусок про mRmR появился позже. Мои слова про сложность методов фильтрации верны для взаимной информации, хи-квадрата, но не для mRmR.
Sign up to leave a comment.

Articles