Авторы: Патрик Каллиер | Джонатан Лэнди

Внимание, мы переехали! Если вы хотите и дальше следить за последними техническими новостями Square, посетите наш новый дом https://developer.squareup.com/blog

Введение

В этом посте мы рассмотрим некоторые вещи, которые мы узнали из наших первых экспериментов над производственными приложениями для выбора функций. Мы сосредотачиваемся на двух вариантах пошагового выбора: (1) линейный пошаговый метод выбора Эфроймсона [2], в данном случае известный как линейный пошаговый вперед, и (2) пошаговый метод выбора с пользовательской логистической регрессией. используя два прохода через данные, которые мы дублируем двухпроходным пошагово вперед. Оба метода основаны на использовании простого подхода для итеративного выбора наиболее подходящих функций. После завершения работы алгоритмов выбранные функции были переданы в более сложные модели, и мы используем перекрестную проверку, чтобы выбрать, сколько оставить.

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

II. Пошаговые методы

Родительский набор из N функций всегда будет иметь 2 ^ N возможных подмножеств функций, количество, которое экспоненциально растет с N. Эта скорость роста означает, что поиск оптимального подмножества даже при небольшом N методом грубой силы редко возможен [1]. Это мотивирует поиск быстрых, но приблизительных стратегий поиска с отбором признаков.

Оба метода выбора признаков, которые мы рассматриваем, являются вариантами метода прямого пошагового выбора. Традиционный пошаговый выбор вперед работает следующим образом: мы начинаем процесс выбора характеристик с выбора класса модели (например, линейная или логистическая регрессия). Затем мы спрашиваем, какая из N функций сама по себе предоставит лучшую модель в нашем классе для прогнозирования нашей цели. Это влечет за собой построение N отдельных моделей, каждая из которых имеет доступ только к одной из функций, присутствующих в нашем исходном наборе данных. Как только оптимальная первая функция определена, она фиксируется на месте. Затем мы повторяем: не снимая выделения с первой функции, мы спрашиваем, какая вторая функция при добавлении к нашей первой дает лучшую модель, имеющую две функции. Это требует рассмотрения отдельных моделей N-1. Продолжая таким образом, мы можем перемещаться по всем N функциям, возвращая ранжирование функций в том порядке, когда они должны быть добавлены к сохраненному набору функций. Для выполнения полного процесса требуется N + (N-1) + (N-2) +… + 1 = N x (N + 1) / 2 построений модели.

Фактическое время выполнения вышеуказанного процесса зависит от выбранного класса модели. Если время выполнения для одной подгонки равно O (N ^ g), где g - константа, зависящая от сложности времени выполнения данного типа модели, то время выполнения полной прямой развертки будет равняться O (N ^ ( 2 + g)) - потому что нам нужно O (N²) сборок модели, как отмечалось выше. Это верно для подхода логистической регрессии (где g = 3 [3]), что разочаровывает, потому что логистическая регрессия обучается даже быстрее, чем большинство моделей, которые мы использовали бы в производстве. Однако в случае линейной регрессии существует эффективный метод выполнения пошагового прямого выбора, который позволяет выполнять весь алгоритм с той же временной сложностью, что и построение одной модели. Это достигается за счет эффективного обновления модели по мере добавления функций к набору функций. См. [2] для ссылок и кода, относящихся к этому подходу, впервые обнаруженному Эфроймсоном, который мы называем ниже линейным подходом.

Второй метод, который мы рассматриваем, двухпроходная процедура, также относится к семейству прямых пошаговых подходов и был впервые разработан Эззери Эса (github), специалистом по данным Square. Вместо того, чтобы оценивать весь набор функций, он использует жадный метод, который требует только 2N моделей.

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

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

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

К сожалению, с настраиваемой метрикой (и модельной формой) двухпроходного метода мы не знаем каких-либо ускорений, подобных тому, что обнаружил Эфроймсон. Таким образом, у нас есть в двухпроходном методе процедура выбора функции O (N ^ (1 + g)). На практике мы обнаружили, что он имеет неблагоприятное время выполнения, когда он включает в себя более нескольких сотен функций или несколько тысяч наблюдений, иногда для работы на одном из наших ноутбуков требуются часы или дни. Напротив, линейный подход часто выполняется за секунды для наборов данных такого размера, а также может масштабироваться до более крупных наборов данных.

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

III. Эксперименты

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

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

После того, как была определена «лучшая» модель для каждой модели и доступное количество функций, мы протестировали каждую на невидимом удерживающем наборе и собрали показатели производительности модели, такие как площадь под кривой ROC (AUC) и отзыв с фиксированной точностью.

Линейный метод производит полное ранжирование по всему набору функций, поэтому мы обучили модели по 5, 10, 25, 50, 100, 500, 1000 и всем характеристикам - чуть более 2000. Напротив, двухпроходный метод делает это. не предоставляет простой способ ранжирования отклоненных функций, поэтому мы взяли его выходные данные при нескольких значениях порогового параметра, в результате чего было выбрано от 20 до 60 функций. Мы рассказали о двухпроходном методе оптимизации ROC AUC в качестве выбранной метрики.

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

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

При очень небольшом количестве функций двухпроходный метод превосходит линейный выбор. Это преимущество исчезает, когда мы смотрим на производительность по другой метрике, вспомним, что точность = 0,33:

По этой метрике сохраняется тенденция к увеличению производительности при увеличении количества функций, но нет заметной разницы между любым методом при любом размере набора функций. Мы обнаружили, что, хотя двухпроходный отбор обычно превосходит линейный по метрике, для которой он настроен (здесь ROC AUC), его производительность почти всегда более хрупкая по метрикам, для которых он не настроен.

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

IV. Обсуждение

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

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

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

Другой важный вариант использования - интерпретируемость модели. Линейная модель с небольшим количеством (неколлинеарных) функций имеет серьезные преимущества перед многими другими подходами к машинному обучению, поскольку она предлагает интерпретируемость. Например, если модель риска оценивает продавца только по трем характеристикам - скажем, как долго он находится на Square, сколько объем платежей они обработали и сколько возвратных платежей они получили, - тогда эта модель помечает торговец, легко определить, почему он так поступил. Мы провели еще несколько экспериментов с гораздо более общими подходами к интерпретируемости, но линейные модели с редкими характеристиками по-прежнему являются золотым стандартом в большей части отрасли.

использованная литература

[1] Выбор оптимального подмножества NP-сложен. См. Б. К. Натараджан. Разреженные приближенные решения линейных систем. Журнал SIAM по вычислениям, 24 (2): 227–234, 1995.

[2] М. Эфроймсон. Множественный регрессионный анализ. Математические методы для цифровых вычислительных машин, 1: 191–203, 1960.

Недавняя реализация подхода Efroymson на Python доступна на GitHub здесь. Математические детали - с упором на расширение неконтролируемого выбора - обсуждаются в статье arXiv, ссылка на которую есть там.

[3] Тезис о сложности выполнения некоторых моделей здесь.