GPU в завданнях машинного навчання
Машинне навчання відіграє ключову роль у багатьох областях науки і промисловості - зокрема, при вирішенні задач статистики, аналізу даних і штучного інтелекту. У пошуковій системі «Яндекс» вже давно використовується машинне навчання для вирішення задачі ранжування - визначення порядку знайдених результатів у відповіді на запит користувача. Машинне навчання в «Яндексі»
Обсяги даних, які обробляються сучасними інформаційними системами, ростуть, а логіка бізнес-додатків ускладнюється, що виключає будь-яку участь людини і викликає потребу в адаптивних алгоритмах, що враховують зміни навколишнього середовища.
Андрій Устюжанін, Денис Юркін
Завдання навчання ранжирування полягає в розподілі документів, отриманих на конкретний запит, в порядку, максимально близькому до ідеального ранжирування, зробленому на основі експертних оцінок. При цьому документи представлені набором факторів, що описують їх різні властивості (зміст слів запиту в тексті, кількість посилань, вік документа і т. Д.), А міра близькості визначається заданою функцією втрат, наприклад середньої квадратичної помилкою.
Алгоритми навчання ранжирування можна розділити на три групи в залежності від способу представлення даних: поточечной, попарні і позапросние. У поточечной випадку завдання ранжирування може бути представлена у вигляді звичайної завдання регресії, яка полягає в прогнозі оцінки для заданої пари запит-документ. Попарний підхід зводиться до побудови класифікатора, який визначає кращий документ в парі, отриманої для заданого запиту. Позапросний спосіб оптимізує середнє значення функції втрат на всі запити, доступним для навчання.
По суті, поточечной спосіб - це рішення класичної задачі регресії:
Де F - безліч можливих функцій ранжирування, а L - функція втрат, яка може мати такий вигляд: L (l qi, f (d qi)) = (l qi - f (d qi)) 2, де d qi, l qi - документ і його оцінка для запиту q. Для вирішення регресійної завдання є багато різних методів, що відрізняються обчислювальною складністю. Істотне розвиток сьогодні отримали методи, засновані на побудові ансамблів, - алгоритми бустінга і бегінга. ідея бустінга [1] полягає в побудові моделі у вигляді адитивної розкладання на прості функції h (d). Іншими словами, множинний метод підбирає складну модель як комбінацію більш простих. Це ітеративний процес, який починається з деякого початкового припущення і послідовно додає нові функції. Завдяки такому підходу, стає можливо змінювати якість і ефективність отриманих моделей на машинний час їх розрахунку. Таким чином, проблема продуктивності підбору перестала бути другорядною і вийшла на перший план поряд зі збором даних та розробкою математичної моделі.
Конкретна реалізація простих функцій може залежати від розв'язуваної задачі. Дослідження, наприклад [2] , Показали, що вибір дерев рішень в якості слабких моделей дозволяє домогтися найкращих результатів - дерево розділяє векторний простір факторів на кілька непересічних областей і для кожної з них передбачає постійне значення. Дерево визначається конфігурацією його листя і порядком підрахунку оптимального рішення в рамках цих листів. Наприклад, в якості конфігурації може виступати набір умов виду fi> 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 елемента. Розподілимо фактори між потоками за формулою fk = (tid & 7 + k * 2) + (tid & 1) + (tid & 24), де k змінюється від 0 до 3, щоб врахувати всі чинники. Тоді індексація в цьому шматку буде мати вигляд fk + b tid * 32. Такий підхід (рис. 1) дозволяє кожному потоку розмістити значення градієнта для кожного фактора окремо, перетинаючись з іншими потоками і не вимагаючи складної синхронізації або більшої кількості розділяється пам'яті. Для отримання повної гістограми залишається тільки підсумувати окремі шматки.
Додавання кожного нового рівня дерева означає поділ навчального набору документів на фрагменти, що стосуються окремого аркушу. Найчастіше це може порушити рівномірний доступ при читанні масиву зі значеннями градієнта з глобальної пам'яті. Ці значення залишаються постійними під час побудови дерева, причому всі блоки потоків, що відповідають за різні фактори, звертаються до масиву однаково. У цьому випадку корисно завантажувати дані градієнта через текстурну пам'ять, так як вона забезпечує спеціальний механізм кешування, який не потребує рівномірного доступу суміжних потоків.
результати
На графіку (рис. 2) наведено відносне порівняння швидкості виконання однієї ітерації алгоритму «Матрикснет» на різній кількості центральних процесорів в залежності від розміру даних. На вертикальній осі зазначено прискорення, отримане щодо виконання на конфігурації з восьми центральних процесорів. Запуски проводилися з використанням Intel Xeon E5-2650, як GPU служив прискорювач Tesla C2075. Для навчання застосовувалися актуальні дані, на яких навчаються поточні формули ранжирування пошукової машини «Яндекс» і які описуються більш ніж 700 факторами. Збільшення кількості потоків вдвічі призводить до відповідного зростання продуктивності, однак застосування тільки одного графічного прискорювача дозволяє прискорити процес більш ніж в 20 разів.
***
Графічні процесори вельми ефективні при вирішенні задачі ранжування, зокрема для побудови дерев рішень. В першу чергу це пов'язано з тим, що алгоритм побудови дерев допускає високий ступінь паралелізму і вимагає значних обчислень. «Яндекс» застосовує графічні процесори для оптимізації обчислювальних процесів. Зокрема, «Матрікcнет» - основний метод машинного навчання - повністю реалізований на GPU. Крім того, графічні процесори допомагають прискорити перевірку нових факторів, істотно економлячи апаратні ресурси, - наприклад, для перевірки одного фактора використовується 500 однопроцесорних серверів, проте це завдання за той же час вирішують шість машин, оснащених чотирма графічними прискорювачами.
література
- Friedman J. Greedy function approximation: A gradient boosting machine // Annals of Statistics. 2001. 29 p. 1189-1232.
- Chapelle O., Chang Y. Yahoo! Learning to rank challenge overview // J. of Machine Learning Research - Proceedings Track. 2011. 14. pp. 1-24.
- 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.
Ігор Кураленок ( [email protected] ) - керівник відділу, Олександр Щекалев ( [email protected] ) - старший розробник, компанія «Яндекс» (Санкт-Петербург). Стаття підготовлена на основі матеріалів доповіді, представленої на IV Московський суперкомп'ютерний форум ( МСКФ-2013 , Грант РФФД 13-07-06046 г).
