Введение в разработку CatBoost. Доклад Яндекса / Хабр

Меня зовут Стас Кириллов, я ведущий разработчик в группе ML-платформ в Яндексе. Мы занимаемся разработкой инструментов машинного обучения, поддержкой и развитием инфраструктуры для них. Ниже — мой недавний доклад о том, как устроена библиотека CatBoost. В докладе я рассказал о входных точках и особенностях кода для тех, кто хочет его понять или стать нашим контрибьютором.

— CatBoost у нас живет на GitHub под лицензией Apache 2.0, то есть открыт и бесплатен для всех. Проект активно развивается, сейчас у нашего репозитория больше четырех тысяч звездочек. CatBoost написан на C++, это библиотека для градиентного бустинга на деревьях решений. В ней поддержано несколько видов деревьев, в том числе так называемые «симметричные» деревья, которые используются в библиотеке по умолчанию.

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

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

Как происходит процесс обучения в CatBoost? Расскажу, как это устроено с точки зрения кода. Сначала мы парсим параметры обучения, которые передает пользователь, валидируем их и дальше смотрим, нужно ли нам загружать данные. Потому что данные уже могут быть загружены — например, в Python или R. Далее мы загружаем данные и строим сетку из бордеров с целью квантизовать численные фичи. Это нужно, чтобы делать обучение быстрым.

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

Дальше мы запускаем непосредственно training loop — главный цикл нашего машинного обучения, где мы итеративно строим деревья. После этого цикла происходит экспорт модели.

Сам цикл обучения состоит из четырех пунктов. Первый — мы пытаемся построить одно дерево. Дальше смотрим, какой прирост или убыль качества оно дает. Потом проверяем, не сработал ли наш детектор переобучения. Далее мы, если пришло время, сохраняем снэпшот.

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

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

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

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

Очень сложно выделить какое-то одно место, в котором происходит обучение, так что на этом слайде — его можно использовать как некоторую точку входа — перечислены основные файлы, которые у нас применяются для обучения. Это greedy_tensor_search, в котором у нас живет сама процедура жадного подбора сплитов. Это train.cpp, где у нас находится главная фабрика CPU-обучения. Это aprox_calcer, где лежат функции обновления значений в листьях. А также score_calcer — функция оценки какого-то кандидата.

Не менее важные части — catboost.pyx и core.py. Это код питоновской обертки, скорее всего, многие из вас будут внедрять какие-то вещи в питоновскую обертку. Наша питоновская обертка написана на Cython, Cython транслируется в C++, так что этот код должен быть быстрым.

Наша R-обертка лежит в папке R-package. Возможно, кому-то придется добавлять или исправлять какие-то опции, для опций у нас есть отдельная библиотека — catboost/libs/options.

Мы пришли из Arcadia в GitHub, поэтому у нас есть много интересных артефактов, с которыми вам придется столкнуться.

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

У нас есть library, где лежат библиотеки общего пользования, которыми пользуются в Яндексе, — многие, не только CatBoost.

Папка CatBoost и contrib — это код сторонних библиотек, с которыми мы линкуемся.

Давайте теперь поговорим про примитивы C++, с которыми вам придется столкнуться. Первое — умные указатели. В Яндексе у нас со времен std::unique_ptr используется THolder, а вместо std::make_unique используется MakeHolder.

У нас есть свой SharedPtr. Причем он существует в двух ипостасях, SimpleSharedPtr и AtomicSharedPtr, которые отличаются типом счетчика. В одном случае он атомарный, это значит, что объектом могут владеть как будто бы несколько потоков. Так будет безопасно с точки зрения передачи между потоками.

Отдельный класс IntrusivePtr позволяет владеть объектами, унаследованными от класса TRefCounted, то есть классами, у которых внутри встроен счетчик ссылок. Это чтобы аллоцировать такие объекты за один раз, не аллоцируя дополнительно контрольный блок со счетчиком.

Также у нас своя система для ввода и вывода. IInputStream и IOutputStream — это интерфейсы для ввода и вывода. У них есть полезные методы, такие как ReadTo, ReadLine, ReadAll, в общем, всё, что можно ожидать от InputStreams. И у нас есть реализации этих стримов для работы с консолью: Cin, Cout, Cerr и отдельно Endl, который похож на std::endl, то есть он флашит поток.

Еще у нас есть свои реализации интерфейсов для файлов: TInputFile, TOutputFile. Это буферизованное чтение. Они реализуют буферизованное чтение и буферизованную запись в файл, поэтому можно ими пользоваться.

У util/system/fs.h есть методы NFs::Exists и NFs::Copy, если вдруг вам что-то понадобится скопировать или проверить, что какой-то файл действительно существует.

У нас свои контейнеры. Они довольно давно переехали на использование std::vector, то есть они просто наследуются от std::vector, std::set и std::map, но у нас есть и свои THashMap и THashSet, у которых отчасти интерфейсы совместимы с unordered_map и unordered_set. Но для некоторых задач они оказались быстрее, поэтому они у нас до сих пор используются.

Ссылки на массивы — аналог std::span из C++. Правда, появился он у нас не в двадцатом году, а сильно раньше. Мы его активно используем, чтобы передавать ссылки на массивы, как будто бы аллоцированные на больших буферах, чтобы не аллоцировать временные буферы каждый раз. Допустим, для подсчета производных или каких-то аппроксов мы можем выделять память на каком-то предаллоцированном большом буфере и передавать функцию подсчета только TArrayRef. Это очень удобно, и мы много где это используем.

В Arcadia применяется свой набор классов для работы со строками. Это, во-первых, TStingBuf — аналог str::string_view из C++17.

TString — совсем не std::sting, это CopyOnWrite-строка, поэтому нужно с ней работать довольно аккуратно. Кроме того, TUtf16String — такая же TString, только у нее базовый тип — не char, а 16-битный wchar.

И у нас есть инструменты для преобразования из строк и в строку. Это ToString, который является аналогом std::to_string и FromString в паре с TryFromString, которые позволяют превратить строку в необходимый вам тип.

У нас есть своя структура исключений, базовым исключением в аркадийных библиотеках является yexception, который наследуется от std::exception. У нас есть макрос ythrow, который добавляет информацию о месте, откуда бросилось исключение в yexception, это просто удобная обертка.

Есть свой аналог std::current_exception — CurrentExceptionMessage, эта функция выводит текущее исключение в виде строки.

Есть свои макросы для asserts и verifies — это Y_ASSERT и Y_VERIFY.

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

Так получилось, что у нас в CatBoost используются две версии сериализации. Первый вариант работает через интерфейсные методы Save и Load, которые сериализуют в поток. Другой вариант используется в нашем распределенном обучении, там применяется довольно старая внутренняя библиотека BinSaver, удобная для сериализации полиморфных объектов, которые должны быть зарегистрированы в специальной фабрике. Это нужно для распределенного обучения, про которое мы здесь в силу недостатка времени вряд ли успеем рассказать.

Также у нас есть свой аналог boost_optional или std::optional — TMaybe. Аналог std::variant — TVariant. Нужно пользоваться ими.

Есть и некое соглашение, что внутри CatBoost-кода мы вместо yexception бросаем TCatBoostException. Это тот же самый yexception, только в нем всегда при бросании добавляется stack trace.

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

^{_{Ссылки со слайда: первая, вторая}}

Обязательно перед началом работы рекомендуем ознакомиться с code style, он состоит из двух частей. Первая — общеаркадийный code style, который лежит прямо в корне репозитория в файле CPP_STYLE_GUIDE. md. Также в корне репозитория лежит отдельный гайд для нашей команды: catboost_command_style_guide_extension.md.

Python-код мы стараемся оформлять по PEP8. Не всегда получается, потому что для Cython кода у нас не работает линтер, и иногда там что-то разъезжается с PEP8.

Каковы особенности нашей сборки? Аркадийная сборка изначально была нацелена на то, чтобы собирать максимально герметичные приложения, то есть чтобы был минимум внешних зависимостей за счет статической линковки. Это позволяет использовать один и тот же бинарник на разных версиях Linux без рекомпиляции, что довольно удобно. Цели сборки описываются в ya.make-файлах. Пример ya.make можно посмотреть на следующем слайде.

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

Есть полезная штука, GENERATE_ENUM_SERIALIZATION, необходимая для того, чтобы сгенерировать ToString, FromString методы для enum classes и enums, описанных в каком-то заголовочном файле, который вы передаете в этот макрос.

Теперь о самом важном — как скомпилировать и запустить какой-нибудь тест. В корне репозитория лежит скрипт ya, который загружает необходимые toolkits и инструменты, и у него есть команда ya make — подкоманда make, — которая позволяет собрать с ключиком -r релиз, с ключиком -d дебаг-версию. Артефакты в ней передаются далее и разделяются через пробел.

Для сборки Python я здесь сразу же указал флаги, которые могут быть полезны. Речь идет про сборку с системным Python, в данном случае с Python 3. Если вдруг на вашем ноутбуке или разработческой машине есть установленный CUDA Toolkit, то для более быстрой сборки рекомендуем указывать флаг –d have_cuda no. CUDA собирается довольно долго, особенно на 4-ядерных системах.

Еще уже должна работать ya ide. Это инструмент, который сгенерирует для вас clion либо qt solution. И для тех, кто пришел с Windows, у нас есть Microsoft Visual Studio solution, который лежит в папке msvs.

Слушатель:

— А у вас все тесты через Python-обертку?

Стас:

— Нет, у нас отдельно есть тесты, которые лежат в папке pytest. Это тесты нашего CLI-интерфейса, то есть нашего приложения. Правда, они работают через pytest, то есть это Python-функции, в которых мы делаем subprocess check call и проверяем то, что программа не падает и правильно работает при каких-то параметрах.

Слушатель:

— А юнит-тесты на C++?

Стас:

— Юнит-тесты на C++ у нас тоже есть. Они обычно лежат в папке lib в подпапках ut. И они так и пишутся — unit test либо unit test for. Там есть примеры. Есть специальные макросы для того, чтобы объявить класс с юнит-тестами, и отдельные регистры для функции юнит-тестов.

Слушатель:

— Для проверки того, что ничего не сломалось, лучше запускать и те, и те?

Стас:

— Да. Единственное, наши тесты в опенсорсе зеленые только на Linux. Поэтому если вы компилируетесь, например, под Mac, если там пять тестов будет падать — ничего страшного. Из-за разной реализации экспоненты на разных платформах или еще каких-то мелких различий результаты могут сильно разъезжаться.

Для примера возьмем задачку. Хочется показать какой-то пример. У нас есть файлик с задачками — open_problems.md. Решим задачку №4 из open_problems.md. Она формулируется так: если пользователь задал learning rate нулевым, то мы должны падать с TCatBoostException. Нужно добавить валидацию опций.

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

Как вообще происходит парсинг опций? Как я уже сказал, у нас есть важная папка catboost/libs/options, где хранится парсинг всех опций.

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

Мы каким-то образом узнали — например, поискав грепом или прочитав код, — что learning rate у нас находится в TBoostingOptions. Попробуем написать код, который просто добавляет CB_ENSURE, что наш learning rate больше чем std::numeric_limits::epsilon, что пользователь ввел нечто более-менее разумное.

Мы здесь как раз воспользовались макросом CB_ENSURE, написали какой-то код и теперь хотим добавить тесты.

В данном случае мы добавляем тест на Command Line Interface. В папке pytest у нас лежит скрипт test. py, где уже есть довольно много примеров тестов и можно просто подобрать похожий на вашу задачу, скопировать его и поменять параметры так, чтобы он начал падать либо не падать — в зависимости от переданных вами параметров. В данном случае мы просто берем и создаем простой пул из двух строчек. (Пулами мы в Яндексе называем датасет. Такая у нас особенность.) И дальше проверяем то, что наш бинарник правда падает, если передать learning rate 0.0.

Также мы добавляем в python-package тест, который находится в сatBoost/python-package/ut/medium. У нас есть еще large, большие тесты, которые связаны с тестами на сборку python wheel-пакетов.

Дальше у нас есть ключики для ya make — -t и -A. -t запускает тесты, -A заставляет запускать все тесты вне зависимости от того, какие у них теги: large или medium.

Здесь я для красоты также использовал фильтр по имени теста. Он задается с помощью опции -F и указанного дальше имени теста, которым могут быть wild char-звездочки. В данном случае я использовал test.py::test_zero_learning_rate*, потому что, посмотрев на наши тесты python-package, вы увидите: почти все функции принимают внутрь себя фикстуру task type. Это чтобы по коду наши тесты python-package выглядели одинаково и для CPU-, и для GPU-обучения и могли использоваться для тестов GPU и CPU trainer.

Дальше коммитим наши изменения и пушим их в наш форкнутый репозиторий. Публикуем пул-реквест. Он уже влился, всё хорошо.

Яндекс открывает технологию машинного обучения CatBoost / Хабр

Сегодня Яндекс выложил в open source собственную библиотеку CatBoost, разработанную с учетом многолетнего опыта компании в области машинного обучения. С ее помощью можно эффективно обучать модели на разнородных данных, в том числе таких, которые трудно представить в виде чисел (например, виды облаков или категории товаров). Исходный код, документация, бенчмарки и необходимые инструменты уже опубликованы на GitHub под лицензией Apache 2. 0.

CatBoost – это новый метод машинного обучения, основанный на градиентном бустинге. Он внедряется в Яндексе для решения задач ранжирования, предсказания и построения рекомендаций. Более того, он уже применяется в рамках сотрудничества с Европейской организацией по ядерным исследованиям (CERN) и промышленными клиентами Yandex Data Factory. Так чем же CatBoost отличается от других открытых аналогов? Почему бустинг, а не метод нейронных сетей? Как эта технология связана с уже известным Матрикснетом? И причем здесь котики? Сегодня мы ответим на все эти вопросы.

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

Нейросети или градиентный бустинг

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

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

Например, если вам нужен точный прогноз погоды, где учитывается огромное количество факторов (температура, влажность, данные с радаров, наблюдения пользователей и многие другие). Или если вам нужно качественно ранжировать поисковую выдачу – именно это в свое время и подтолкнуло Яндекс к разработке собственного метода машинного обучения.

Матрикснет

Первые поисковые системы были не такими сложными, как сейчас. Фактически сначала был просто поиск слов – сайтов было так мало, что особой конкуренции между ними не было. Потом страниц стало больше, их стало нужно ранжировать. Начали учитываться разные усложнения — частота слов, tf-idf. Затем страниц стало слишком много на любую тему, произошёл первый важный прорыв — начали учитывать ссылки.

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

Лет десять назад человеческого разума перестало хватать на то, чтобы придумывать, как ранжировать документы. Вы, наверное, замечали, что количество найденного почти по любому запросу огромно: сотни тысяч, часто — миллионы результатов. Большая часть из них неинтересные, бесполезные, лишь случайно упоминают слова запроса или вообще являются спамом. Для ответа на ваш запрос нужно мгновенно отобрать из всех найденных результатов десятку лучших. Написать программу, которая делает это с приемлемым качеством, стало не под силу программисту-человеку. Произошёл следующий переход — поисковики стали активно использовать машинное обучение.

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

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

Ещё одна важная особенность Матрикснета — в том, что формулу ранжирования можно настраивать отдельно для достаточно узких классов запросов. Например, улучшить качество поиска только по запросам про музыку. При этом ранжирование по остальным классам запросов не ухудшится.

Именно Матрикснет и его достоинства легли в основу CatBoost. Но зачем нам вообще понадобилось изобретать что-то новое?

Категориальный бустинг

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

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

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

Именно поэтому было важно научить машину работать не только с числами, но и с категориями напрямую, закономерности между которыми она будет выявлять самостоятельно, без нашей ручной «помощи». И CatBoost разработан нами так, чтобы одинаково хорошо работать «из коробки» как с числовыми признаками, так и с категориальными. Благодаря этому он показывает более высокое качество обучения при работе с разнородными данными, чем альтернативные решения. Его можно применять в самых разных областях — от банковской сферы до промышленности.

Кстати, название технологии происходит как раз от Categorical Boosting (категориальный бустинг). И ни один кот при разработке не пострадал.

Бенчмарки

Можно долго говорить о теоретических отличиях библиотеки, но лучше один раз показать на практике. Для наглядности мы сравнили работу библиотеки CatBoost с открытыми аналогами XGBoost, LightGBM и h30 на наборе публичных датасетов. И вот результаты (чем меньше, тем лучше): https://catboost.yandex/#benchmark

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

CatBoost на практике

Новый метод уже протестировали на сервисах Яндекса. Он применялся для улучшения результатов поиска, ранжирования ленты рекомендаций Яндекс.Дзен и для расчета прогноза погоды в технологии Метеум — и во всех случаях показал себя лучше Матрикснета. В дальнейшем CatBoost будет работать и на других сервисах. Не будем здесь останавливаться – лучше сразу расскажем про Большой адронный коллайдер (БАК).

CatBoost успел найти себе применение и в рамках сотрудничества с Европейской организацией по ядерным исследованиям. В БАК работает детектор LHCb, используемый для исследования асимметрии материи и антиматерии во взаимодействиях тяжёлых прелестных кварков. Чтобы точно отслеживать разные частицы, регистрируемые в эксперименте, в детекторе существуют несколько специфических частей, каждая из которых определяет специальные свойства частиц. Наиболее сложной задачей при этом является объединение информации с различных частей детектора в максимально точное, агрегированное знание о частице. Здесь и приходит на помощь машинное обучение. Используя для комбинирования данных CatBoost, учёным удалось добиться улучшения качественных характеристик финального решения. Результаты CatBoost оказались лучше результатов, получаемых с использованием других методов.

Как начать использовать CatBoost?

Для работы с CatBoost достаточно установить его на свой компьютер. Библиотека поддерживает операционные системы Linux, Windows и macOS и доступна на языках программирования Python и R. Яндекс разработал также программу визуализации CatBoost Viewer, которая позволяет следить за процессом обучения на графиках.

Более подробно все описано в нашей документации.

CatBoost — первая российская технология машинного обучения такого масштаба, которая стала доступна в open sourсe. Выкладывая библиотеку в открытый доступ, мы хотим внести свой вклад в развитие машинного обучения. Надеемся, что сообщество специалистов оценит технологию и примет участие в ее развитии.

CatBoost — библиотека повышения градиента с открытым исходным кодом

CatBoost — высокопроизводительная библиотека с открытым исходным кодом для повышения градиента на деревьях решений

Как установитьУчебники

Сегодня мы открываем исходный код нашей библиотеки повышения градиента CatBoost. Он хорошо подходит для обучения моделей машинного обучения задачам, в которых данные разнородны, т. е. описываются различными входными данными, такими как содержимое, историческая статистика и выходные данные других моделей машинного обучения. Новый алгоритм повышения градиента теперь доступен на GitHub под лицензией Apache License 2.0.

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

CatBoost поддерживает Linux, Windows и macOS, а также им можно управлять из командной строки или через удобный API для Python или R. В дополнение к открытому исходному коду нашего алгоритма повышения градиента мы выпускаем наш инструмент визуализации CatBoost Viewer , что позволяет отслеживать процессы обучения в iPython Notebook или в автономном режиме. Мы также предоставляем всем пользователям CatBoost инструмент для сравнения результатов популярных алгоритмов повышения градиента.

«Яндекс имеет долгую историю машинного обучения. У нас работают лучшие специалисты в этой области. Открывая CatBoost с открытым исходным кодом, мы надеемся, что наш вклад в машинное обучение будет оценен экспертным сообществом, которое поможет нам продвигать его дальнейшее развитие», — говорит Миша Биленко, руководитель отдела машинного интеллекта и исследований Яндекса.

CatBoost уже успешно протестирован в различных приложениях для целого ряда сервисов Яндекса, включая прогноз погоды для технологии Meteum, ранжирование контента для сервиса персональных рекомендаций Яндекс Дзен и улучшение результатов поиска. Со временем этот алгоритм будет реализован на большинстве сервисов Яндекса. Помимо Яндекса, CatBoost уже используется учеными из Европейской организации ядерных исследований (CERN) для повышения производительности обработки данных в их косметическом эксперименте на Большом адронном коллайдере.

Обучение работе с CatBoost на кластере ЦП/ГП с набором данных из триллионов запросов помогает идентифицировать трафик вредоносных ботов.

Careem, ведущая платформа для заказа такси на Ближнем Востоке, объяснила, как CatBoost помогает прогнозировать следующий шаг клиента.

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

Полный список новостей

Знакомство с CatBoost. Отчет Яндекса / Хабр0001

Меня зовут Стас Кириллов, я ведущий разработчик группы ML-платформ в Яндексе. Мы разрабатываем инструменты машинного обучения, поддерживаем и развиваем для них инфраструктуру. Ниже мой недавний доклад о том, как работает библиотека CatBoost. В докладе я рассказал о точках входа и особенностях кода для тех, кто хочет в нем разобраться или стать нашим контрибьютором.

— CatBoost живет на GitHub под лицензией Apache 2.0, то есть он открыт и бесплатен для всех. Проект активно развивается, сейчас в нашем репозитории более четырех тысяч звезд. CatBoost написан на C++, это библиотека для повышения градиента на деревьях решений. Он поддерживает несколько типов деревьев, в том числе так называемые «симметричные» деревья, которые используются в библиотеке по умолчанию.

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

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

Как проходит процесс обучения в CatBoost? Расскажу, как это работает с точки зрения кода. Сначала мы анализируем параметры обучения, которые передает пользователь, проверяем их, а затем смотрим, нужно ли нам загружать данные. Потому что данные уже могут быть загружены — например, в Python или R. Далее мы загружаем данные и строим сетку из границ, чтобы квантовать числовые признаки. Это необходимо для ускорения обучения.

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

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

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

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

Как устроен жадный древовидный цикл? В самом начале делается бутстрап — перевзвешиваем или семплируем объекты, после чего для построения дерева будут использоваться только выбранные объекты. Бутстрап также можно пересчитывать перед выбором каждого разделения, если включена опция выборки на каждом уровне.

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

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

Очень сложно выделить одно место, где происходит обучение, поэтому на этом слайде — его можно использовать как некую точку входа — перечислены основные файлы, которые мы используем для обучения. Это greedy_tensor_search, в котором проживается сама процедура жадного выбора сплитов. Это train.cpp, где у нас находится основная фабрика по обучению ЦП. Это aprox_calcer, где лежат функции обновления значений в листьях. А также score_calcer — функция для оценки какого-то кандидата.

Одинаково важными частями являются catboost.pyx и core.py. Это код оболочки python, скорее всего, многие из вас будут встраивать какие-то вещи в обертку python. Наша обертка на python написана на Cython, Cython переведен на C++, поэтому этот код должен быть быстрым.

Наша R-обертка лежит в папке R-package. Возможно кому-то придется добавить или исправить некоторые опции, для опций у нас есть отдельная библиотека — catboost/libs/options.

Мы пришли из Аркадии на GitHub, поэтому у нас много интересных артефактов, с которыми вы столкнетесь.

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

У нас есть библиотека, где лежат расшаренные библиотеки, используемые Яндексом — многие, не только CatBoost.

Папка CatBoost и contrib — это код сторонних библиотек, на которые мы ссылаемся.

Теперь поговорим о примитивах C++, с которыми вы столкнетесь. Во-первых, это умные указатели. В Яндексе мы использовали THolder начиная с std::unique_ptr, а MakeHolder используется вместо std::make_unique.

У нас есть собственный SharedPtr. Более того, он существует в двух формах, SimpleSharedPtr и AtomicSharedPtr, которые отличаются типом счетчика. В одном случае он атомарный, что означает, что объектом могут владеть как бы несколько потоков. Так что это будет безопасно с точки зрения передачи между потоками.

Отдельный класс IntrusivePtr позволяет владеть объектами, унаследованными от класса TRefCounted, то есть классами, имеющими встроенный счетчик ссылок. Это для единовременного выделения таких объектов без дополнительного выделения управляющего блока со счетчиком.

У нас также есть собственная система ввода и вывода. IInputStream и IOutputStream — это интерфейсы для ввода и вывода. У них есть полезные методы, такие как ReadTo, ReadLine, ReadAll, в общем все, что можно ожидать от InputStreams. И у нас есть реализации этих потоков для работы с консолью: Cin, Cout, Cerr и отдельно Endl, который аналогичен std::endl, то есть сбрасывает поток.

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

Util/system/fs.h имеет методы NFs::Exists и NFs::Copy, если вам вдруг нужно что-то скопировать или проверить, что какой-то файл действительно существует.

У нас есть собственные контейнеры. На использование std::vector перешли довольно давно, то есть просто наследуются от std::vector, std::set и std::map, но у нас есть и свои THashMap и THashSet, которые частично имеют совместимые интерфейсы с unordered_map и unordered_set. Но для некоторых задач они оказались быстрее, поэтому до сих пор их используем.

Ссылки на массив аналогичны std::span из C++. Правда, появился он у нас не в двадцатом году, а гораздо раньше. Активно используем его для переноса ссылок на массивы, как бы выделенные на большие буферы, чтобы не выделять каждый раз временные буферы. Допустим, для подсчета производных или каких-то приближений мы можем выделить память на какой-то заранее выделенный большой буфер и передать только функцию подсчета TArrayRef. Это очень удобно, и мы часто этим пользуемся.

Arcadia использует собственный набор классов для работы со строками. Это, во-первых, TStingBuf — аналог str::string_view из C++ 17.

TString — это вовсе не std::sting, это строка CopyOnWrite, поэтому работать с ней нужно достаточно осторожно. Кроме того, TUtf16String — это тот же TString, только его базовый тип — не char, а 16-битный wchar.

И у нас есть инструменты для преобразования строки в строку. Это ToString, который является аналогом std::to_string и FromString в паре с TryFromString, что позволяет превратить строку в нужный вам тип.

У нас своя структура исключений, базовое исключение в аркадной библиотеке — yexception, которое наследуется от std::exception. У нас есть макрос ythrow, который добавляет информацию о том, где было сгенерировано исключение в yexception, это просто удобная обертка.

Есть аналог std::current_exception — CurrentExceptionMessage, эта функция выбрасывает текущее исключение в виде строки.

Есть макросы для ассертов и верификаций — это Y_ASSERT и Y_VERIFY.

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

Так получилось, что у нас две версии сериализации в CatBoost. Первый вариант работает через методы интерфейса Save и Load, которые сериализуются в поток. Другой вариант используется в нашем распределенном обучении, он использует довольно старую внутреннюю библиотеку BinSaver, удобную для сериализации полиморфных объектов, которые необходимо регистрировать в специальной фабрике. Это необходимо для распределенного обучения, о котором мы вряд ли успеем здесь рассказать из-за нехватки времени.

У нас тоже есть свой аналог boost_Optional или std::Optional — TMaybe. Аналог std::variant — TVariant. Вы должны использовать их.

Существует определенное соглашение, согласно которому внутри кода CatBoost мы выбрасываем исключение TCatBoostException вместо исключения y. Это то же самое исключение y, только трассировка стека всегда добавляется при его генерировании.

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

^{_{Ссылки со слайда: первая, вторая}}

Обязательно ознакомьтесь со стилем кода перед началом работы, он состоит из двух частей. Первый — это стиль кода all-arcade, который лежит прямо в корне репозитория в файле CPP_STYLE_GUIDE.md. Также в корне репозитория находится отдельное руководство для нашей команды: catboost_command_style_guide_extension.md.

Мы пытаемся отформатировать код Python с помощью PEP8. Не всегда получается, потому что для кода Cython у нас не работает линтер, а с PEP8 иногда что-то аукнется.

В чем особенности нашей сборки? Сборка Arcadia изначально была нацелена на сбор максимально герметичных приложений, то есть что бы было минимум внешних зависимостей за счет статической линковки. Это позволяет использовать один и тот же бинарник на разных версиях Linux без перекомпиляции, что довольно удобно. Цели сборки описаны в файлах ya.make. Пример ya.make можно увидеть на следующем слайде.

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

Есть полезная вещь GENERATE_ENUM_SERIALIZATION, необходимая для генерации методов ToString, FromString для классов enum и перечислений, описанных в каком-то заголовочном файле, который вы передаете этому макросу.

Теперь о самом главном — как скомпилировать и запустить какой-нибудь тест. В корне репозитория лежит скрипт ya, загружающий необходимые наборы инструментов и инструментов, и у него есть команда ya make — подкоманда make — которая позволяет собрать релиз -r с ключом -d и отладочную версию с переключатель -d. Артефакты в нем передаются и разделяются пробелом.

Чтобы собрать Python, я сразу указал здесь флаги, которые могут быть полезны. Речь идет о сборке с системным Python, в данном случае с Python 3. Если вдруг у вас на ноутбуке или машине для разработки установлен CUDA Toolkit, то для более быстрой сборки рекомендуем указать флаг –d have_cuda no. CUDA собирается довольно долго, особенно на 4-ядерных системах.

Я ide уже должен работать. Это инструмент, который создаст для вас решение clion или qt. А для тех, кто пришел с Windows, у нас есть решение Microsoft Visual Studio, которое лежит в папке msvs.

Студент:
— У вас есть все тесты через оболочку Python?

Стас:
— Нет, у нас отдельно есть тесты, которые лежат в папке pytest. Это тесты нашего CLI-интерфейса, то есть нашего приложения. Правда работают они через pytest, то есть это функции Python, в которых мы делаем вызов проверки подпроцесса и проверяем, что программа не падает и корректно работает с некоторыми параметрами.

Студент:
— А модульные тесты в C++?

Стас:
— У нас также есть юнит-тесты на C++. Обычно они лежат в папке lib в подпапках ut. И пишутся они так — юнит-тест или юнит-тест для. Есть примеры. Существуют специальные макросы для объявления класса юнит-теста и отдельные регистры для функции юнит-теста.

Студент:
— Чтобы убедиться, что ничего не сломалось, лучше запустить и те, и те?

Стас:
— Да. Единственное, наши тесты с открытым исходным кодом зеленые только на Linux. Поэтому, если компилировать, например, под Mac, если там пять тестов не пройдено, то беспокоиться не о чем. Из-за разной реализации экспонента на разных платформах или каких-то других незначительных отличий результаты могут сильно отличаться.

Для примера возьмем задачу. Я хотел бы показать какой-то пример. У нас есть файл с задачами — open_problems.md. Решим задачу №4 от open_problems.md. Он формулируется следующим образом: если пользователь поставил скорость обучения равной нулю, то мы должны выпасть из TCatBoostException. Вам нужно добавить валидацию опций.

Для начала нам нужно создать ветку, клонировать наш форк, клонировать origin, pop origin, запустить origin в нашем форке, а затем создать ветку и начать в ней работать.

Как работает разбор опций? Как я уже сказал, у нас есть важная папка catboost/libs/options, где хранится парсинг всех опций.

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

Мы каким-то образом выяснили — например, поиском с помощью grep или чтением кода — что у нас есть скорость обучения в TBoostingOptions. Попробуем написать код, который просто добавляет CB_ENSURE, что наша скорость обучения больше, чем std::numeric_limits::epsilon, что пользователь ввел что-то более-менее разумное.

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

В этом случае мы добавляем тест в интерфейсе командной строки. В папке pytest у нас лежит скрипт test.py, где уже довольно много тестовых примеров и вы можете просто выбрать похожий на вашу задачу, скопировать его и изменить параметры, чтобы он начал падать или не падать , в зависимости от переданных вами параметров. В данном случае мы просто берем и создаем простой пул из двух линий. (Мы в Яндексе называем пулы наборов данных. Это наша особенность.) А потом проверяем, что наш бинарник действительно падает, если мы проходим скорость обучения 0.0.

Так же добавляем тест в python-package, который находится по адресу atBoost/python-package/ut/medium. У нас также есть большие, большие тесты, связанные с тестами для создания пакетов колеса Python.

Далее у нас есть ключи для ya make — -t и -A. -t запускает тесты, -A заставляет запускаться все тесты независимо от того, имеют ли они большие или средние теги.

This entry was posted in Популярное