Как мы заставили наш оптимизатор порогов классификации с несколькими метками сходиться за минуты, а не за дни

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

Самый наивный подход к этой проблеме — применять метку при вероятности >0,5, но этот порог может быть выше (или ниже). Мы также можем решить использовать отдельный порог для каждой метки, и выбор правильного порога для каждой метки сам по себе является проблемой оптимизации. Этот пост в блоге о том, как мы ускорили реализацию алгоритма для решения этой проблемы и сократили время его выполнения с 31 дня до всего лишь пяти минут.

Мы использовали подход, предложенный Pillar et al. (2013) в своей исследовательской статье Пороговая оптимизация для классификаторов с несколькими метками». Предлагаемый алгоритм решения этой оптимизационной задачи можно увидеть в псевдокоде ниже:

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

Код очень похож на псевдокод в документе с добавлением параметра nb-thresholds, чтобы ограничить количество порогов для сканирования, тем самым отделив время выполнения от используемого размера набора данных. Запуск этого алгоритма на двух случайно разреженных матрицах занимает 30 секунд на каждую метку. Это делает его непомерно дорогим для больших пространств меток, например: если предположить, что нам нужно три итерации для сходимости алгоритма, и мы работаем с 30 тысячами меток, это займет 30 с x 30 000 x 3 ~ 31 день!

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

Профилировщик линий был представлен моему вниманию из отличной книги High performance python от Ian Ozvald и Micha Gorelick, которую я настоятельно рекомендую, если вы хотите ускорить свой код на python. Все, что нам нужно сделать, это установить профилировщик линий pip install liner_profiler и добавить декоратор @profile в функции, которые мы хотим профилировать. Запуск нашего алгоритма с ним дает следующий результат:

Как мы видим, большая часть времени тратится внутри функции sklearn f1_score. Если мы продолжим и профилируем его, добавив декоратор @profile в функцию argmax, мы получим:

Как оказалось, половина времени уходит на проверку правильности передаваемых данных (см. строку 1547). В большинстве случаев это очень полезно, так как выдает ошибку, если данные или флаги не имеют смысла, но в нашем случае это совершенно неэффективно, поскольку мы постоянно передаем одни и те же данные. Поскольку мы не можем отключить это поведение, мы можем просто написать собственную функцию f1_score.

Это сокращает время выполнения до 17 секунд на этикетку, что составляет половину нашей первой попытки, но все еще довольно медленно. Если мы снова профилируем, мы получаем

В строке 17 мы видим, что мы, похоже, сместили вес на multilabel_confusion_matrix sklearn. Давайте профилируем функцию multilabel_confusion_matrix, добавив декоратор @profile во внутренний код sklearn. Вы можете найти место, где установлены пакеты сайтов, запустив python -m site. Матрица путаницы с несколькими метками уходит в _classification.py внутри метрик, полный путь sklearn/metrics/_classification.py.

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

Использование нашей собственной матрицы путаницы с несколькими метками еще больше сокращает время до 3 с, что на данный момент является 10-кратным улучшением. Теперь посмотрим, что нас тормозит.

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

На данный момент наш алгоритм занимает 0,46 с на каждую метку, что означает ускорение в 65 раз. На самом деле вся оптимизация может завершиться за 5 часов, что приемлемо. Но можем ли мы сделать лучше?

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

Это изменение сокращает время до 0,17 с на этикетку, что означает ускорение в 176 раз. Это начинает быть быстрым 💨, но давайте посмотрим, сможем ли мы продвинуться дальше.

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

Это приводит нас к 0,02 с на этикетку, что дает еще 10-кратное ускорение, что в сумме дает 1500-кратное ускорение. Мы могли бы закончить на этом, но давайте посмотрим, есть ли еще какая-нибудь легкая победа.

Мы видим, что много времени уходит на выбор столбца разреженной матрицы, строки 78–79. Как оказалось, эти матрицы имеют формат CSR, который весьма эффективен для многих общих операций по науке о данных, но не для выбора столбцов.

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

Этот переключатель заставляет алгоритм работать со скоростью 0,003 с на метку, что дает нам окончательное ускорение на 10 000. Весь алгоритм займет примерно 5 минут для 30 тыс. меток и несколько часов для миллионов меток, что очень быстро для рассматриваемой проблемы. На этом можно остановиться, но стоит сказать, что мы достигли предела убывающей отдачи, если продолжим. Большая часть времени тратится на высокооптимизированные функции в numpy и scipy, и даже если мы напишем свои собственные и скомпилируем их с помощью numba, мы не сможем работать быстрее.

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

Вы можете найти весь код в этом репозитории https://github.com/nsorros/threshold_optimizer, а также можете следить за первыми 8 коммитами, которые вносят эти изменения.