GPU в задачах машинного обучения

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

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

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

По сути, поточечный способ — это решение классической задачи регрессии:

Где F — множество возможных функций ранжирования, а L — функция потерь, которая может иметь следующий вид: L(l _qi , f(d _­qi )) = (l _qi – f(d _qi )) ² , где d _qi , l _qi — документ и его оценка для запроса q. Для решения регрессионной задачи имеется много различных методов, отличающихся вычислительной сложностью. Существенное развитие сегодня получили методы, основанные на построении ансамблей, — алгоритмы бустинга и бэгинга. Идея бустинга [1] заключается в построении модели в виде аддитивного разложения на простые функции h(d). Другими словами, множественный метод подбирает сложную модель как комбинацию более простых. Это итеративный процесс, который начинается с некоторого начального предположения и последовательно добавляет новые функции. Благодаря такому подходу, становится возможно менять качество и эффективность полученных моделей на машинное время их расчета. Таким образом, проблема производительности подбора перестала быть второстепенной и вышла на первый план наряду со сбором данных и разработкой математической модели.

Конкретная реализация простых функций может зависеть от решаемой задачи. Исследования, например [2], показали, что выбор деревьев решений в качестве слабых моделей позволяет добиться наилучших результатов — дерево разделяет векторное пространство факторов на несколько непересекающихся областей и для каждой из них предсказывает постоянное значение. Дерево определяется конфигурацией его листьев и порядком подсчета оптимального решения в рамках этих листьев. Например, в качестве конфигурации может выступать набор условий вида f _i > c _ij , а оптимальное решение определяться средним значением целевой функции по всем элементам, которые вошли в лист. Тот факт, что области не пересекаются, позволяет распараллелить процесс построения дерева решений.

Графические процессоры

Графический процессор (Graphical Processing Unit, GPU) очень хорошо подходит для решения задач, допускающих распараллеливание по данным, одновременно обладая средствами выполнения потоков арифметических операций, характеризуемых частыми обращениями к памяти. Благодаря одновременному выполнению множества арифметических операций для нескольких элементов, удается скрыть задержки доступа к памяти.

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

Программная модель CUDA расширяет язык программирования Си путем определения специализированных вычислительных процедур (kernel), выполняемых непосредственно на графическом процессоре при помощи большого количества параллельных потоков, образующих отдельные группы, идентифицируемые уникальным трехкомпонентным индексом. Такая индексация обеспечивает естественный способ моделирования вычислений для трех структур: вектор, матрица и объемное тело. Группы потоков, в свою очередь, формируют сетку соответствующей размерности. Количество блоков в сетке определяется размером данных либо структурой конкретного графического процессора. В любом графическом процессоре имеется оперативная память, к которой могут обращаться вычислительные модули. Каждый поток обладает собственной памятью, доступной только для него, а всем потокам одного блока на время его выполнения доступна разделяемая память. Все блоки сетки могут обращаться в глобальную, константную и текстурную области памяти GPU, причем последние два типа доступны только для чтения. Все доступные типы памяти оптимизированы для различных вариантов использования данных и обладают различной пропускной способностью.

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

Матрикснет на графическом процессоре

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

В качестве множества функций «Матрикснет» использует множество «забывчивых» деревьев решений, включающих 6 разбиений и, соответственно, 64 листа. Построение дерева осуществляется «жадным» способом — на каждом шаге выбирается самое выгодное разбиение пространства. Алгоритм не рассматривает все возможные деления — это слишком трудоемко, а вместо этого вещественные значения каждого фактора упорядочиваются и делятся на 32 равные по количеству группы, причем значения на границе каждой группы выступают в качестве возможного деления пространства — именно они рассматриваются при построении дерева. Основной вычислительной нагрузкой «Матрикснета» является построение слабой модели на каждой итерации, поэтому наибольшее усилие должно быть сфокусировано на эффективной реализации составления дерева решений на графическом процессоре.

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

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

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

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

Если использовать всю доступную разделяемую память (ее объем для современных архитектур Kepler и Fermi составляет 48 Кбайт), то можно обрабатывать максимум 384 потока в блоке, которые будут один раз читать значение из глобальной памяти и добавлять его в гистограмму. Следовательно, для неконфликтного доступа в гистограмме необходима индексация вида tid + b _tid * 384, где tid — индекс потока в блоке, которому соответствует один документ, а b _tid — индекс корзинки, в которую попадает документ. Однако в этом случае один блок занимает все ресурсы процессора и обрабатывает только один фактор. Можно увеличить их количество до четырех, но тогда важно сохранить текущий способ доступа к глобальной памяти и использовать максимум потоков. Этого можно добиться, изменив индексацию в гистограмме.

Поделим потоки на группы по 32 штуки. Для группы выделим часть гистограммы размером 1024 элемента. Распределим факторы между потоками по формуле f _k = (tid & 7 + k * 2) + (tid & 1) + (tid & 24), где k меняется от 0 до 3, чтобы учесть все факторы. Тогда индексация в этом куске будет иметь вид f _k + b _tid * 32. Такой подход (рис. 1) позволяет каждому потоку разместить значение градиента для каждого фактора отдельно, не пересекаясь с другими потоками и не требуя сложной синхронизации или большего количества разделяемой памяти. Для получения полной гистограммы остается только просуммировать отдельные куски.

Рис. 1. Гистограмма для четырех факторов

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

Результаты

На графике (рис. 2) приведено относительное сравнение скорости выполнения одной итерации алгоритма «Матрикснет» на различном числе центральных процессоров в зависимости от размера данных. На вертикальной оси указано ускорение, полученное относительно выполнения на конфигурации из восьми центральных процессоров. Запуски производились с использованием Intel Xeon E5-2650, в качестве GPU служил ускоритель Tesla C2075. Для обучения применялись актуальные данные, на которых обучаются текущие формулы ранжирования поисковой машины «Яндекс» и которые описываются более чем 700 факторами. Увеличение количества потоков вдвое приводит к соответствующему росту производительности, однако применение только одного графического ускорителя позволяет ускорить процесс более чем в 20 раз.

Рис. 2. Относительное ускорение алгоритма «Матрикснет» для разных конфигураций

***

Графические процессоры весьма эффективны при решении задачи ранжирования, в частности для построения деревьев решений. В первую очередь это связано с тем, что алгоритм построения деревьев допускает высокую степень параллелизма и требует значительных вычислений. «Яндекс» применяет графические процессоры для оптимизации вычислительных процессов. В частности, «Матрикcнет» — основной метод машинного обучения — полностью реализован на GPU. Кроме того, графические процессоры помогают ускорить проверку новых факторов, существенно экономя аппаратные ресурсы, — например, для проверки одного фактора используется 500 однопроцессорных серверов, однако эту задачу за то же время решают шесть машин, оснащенных четырьмя графическими ускорителями.

Литература

1. Friedman J. Greedy function approximation: A gradient boosting machine // Annals of Statistics. 2001. 29 p. 1189-1232.
2. Chapelle O., Chang Y. Yahoo! Learning to rank challenge overview // J. of Machine Learning Research — Proceedings Track. 2011. 14. pp. 1-24.
3. Gulin A., Kuralenok I., Pavlov D. Winning the transfer learning track of Yahoo!'s learning to rank challenge with YetiRank // J. of Machine Learning Research — Workshop and Conference Proceedings. 2011. 14. pp. 63-76.

Игорь Кураленок (solar@yandex-team.ru) — руководитель отдела, Александр Щекалев (sancho@yandex-team.ru) — старший разработчик, компания «Яндекс» (Санкт-Петербург). Статья подготовлена на основе материалов доклада, представленного на IV Московский суперкомпьютерный форум (МСКФ-2013, грант РФФИ 13-07-06046 г).