Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності
У роботі описано побудову моделі паралелізації обчислення невід’ємної факторизації розріджених матриць надвеликої розмірності. Реалізації запропонованих моделей були порівняні в обробці надвеликої матриці....
Gespeichert in:
| Datum: | 2015 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2015
|
| Schriftenreihe: | Штучний інтелект |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/117201 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності / Е.М. Насіров // Штучний інтелект. — 2015. — № 3-4. — С. 17-26. — Бібліогр.: 17 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-117201 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1172012017-05-21T03:03:26Z Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності Насіров, Е.М. Природномовні системи У роботі описано побудову моделі паралелізації обчислення невід’ємної факторизації розріджених матриць надвеликої розмірності. Реалізації запропонованих моделей були порівняні в обробці надвеликої матриці. В работе описано построение модели параллелизация вычисления неотрицательной факторизации разреженных матриц сверхбольшой размерности. Реализации предложенных моделей были сравнены в обработке сверхбольшой матрицы. This paper proposes parallel methods of non-negative huge sparse matrix factorization. The implementation of proposed methods was tested and compared on huge matrix 2015 Article Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності / Е.М. Насіров // Штучний інтелект. — 2015. — № 3-4. — С. 17-26. — Бібліогр.: 17 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/117201 519.4 uk Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Природномовні системи Природномовні системи |
| spellingShingle |
Природномовні системи Природномовні системи Насіров, Е.М. Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності Штучний інтелект |
| description |
У роботі описано побудову моделі паралелізації обчислення невід’ємної факторизації розріджених матриць надвеликої розмірності. Реалізації запропонованих моделей були порівняні в обробці надвеликої матриці. |
| format |
Article |
| author |
Насіров, Е.М. |
| author_facet |
Насіров, Е.М. |
| author_sort |
Насіров, Е.М. |
| title |
Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності |
| title_short |
Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності |
| title_full |
Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності |
| title_fullStr |
Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності |
| title_full_unstemmed |
Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності |
| title_sort |
модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2015 |
| topic_facet |
Природномовні системи |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/117201 |
| citation_txt |
Модель паралелізації невід'ємної факторизації розріджених матриць надвеликої розмірності / Е.М. Насіров // Штучний інтелект. — 2015. — № 3-4. — С. 17-26. — Бібліогр.: 17 назв. — укр. |
| series |
Штучний інтелект |
| work_keys_str_mv |
AT nasírovem modelʹparalelízacíínevídêmnoífaktorizacíírozrídženihmatricʹnadvelikoírozmírností |
| first_indexed |
2025-07-08T11:49:08Z |
| last_indexed |
2025-07-08T11:49:08Z |
| _version_ |
1837079303166099456 |
| fulltext |
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
© E.М. Насіров 17
УДК 519.4
E.М. Насіров
Київський національний університет імені Тараса Шевченка, Україна
Україна, 03680, м. Київ, пр-т. Глушкова 4д
МОДЕЛЬ ПАРАЛЕЛІЗАЦІЇ НЕВІД'ЄМНОЇ ФАКТОРИЗАЦІЇ
РОЗРІДЖЕНИХ МАТРИЦЬ НАДВЕЛИКОЇ РОЗМІРНОСТІ
E.M. Nasirov
Kyiv National Taras Shevchenko University, Ukraine
Ukraine, 03680, c. Kyiv, Glushkova 4d
MODEL FOR PARALLEL NON-NEGATIVE SPARSE EXTRA-
LARGE MATRIX FACTORIZATION
Э.М. Насиров
Киевский национальный университет имени Тараса Шевченко, Украина
Украина, 03680, г. Киев, пр-т. Глушкова 4д
МОДЕЛЬ ПАРАЛЛЕЛИЗАЦИИ НЕОТРИЦАТЕЛЬНОЙ
ФАКТОРИЗАЦИИ РАЗРЯЖЕННЫХ МАТРИЦ
СВЕРХБОЛЬШОЙ РАЗМЕРНОСТИ
У роботі описано побудову моделі паралелізації обчислення невід’ємної факторизації розріджених
матриць надвеликої розмірності. Реалізації запропонованих моделей були порівняні в обробці
надвеликої матриці.
Ключові слова: лінгвістика, паралелізація, невід’ємна факторизація матриць, GPU.
This paper proposes parallel methods of non-negative huge sparse matrix factorization. The implementation of
proposed methods was tested and compared on huge matrix
Key words: computational linguistics, parallel computations, non-negative matrix factorization.
В работе описано построение модели параллелизация вычисления неотрицательной факторизации
разреженных матриц сверхбольшой размерности. Реализации предложенных моделей были сравнены в
обработке сверхбольшой матрицы.
Ключевые слова: лингвистика, параллелизация, неотрицательная факторизация матриц,
GPU.
Сьогодні невід’ємна факторизація матриць і тензорів є дуже популярною
технологією в штучному інтелекті взагалі, та, зокрема, в комп’ютерній
лінгвістиці. Використовуючи невід’ємну факторизацію в рамках парадигми
латентно-семантичного аналізу, комп’ютерні лінгвісти застосовують даний підхід
для розв’язання таких прикладних задач, як класифікація, кластеризація текстів та
термінів[1, 2], побудова мір семантичної близькості[3], автоматичне виділення
лінгвістичних структур та відношень (Selectional Preferences [4] and Verb Sub-
Categorization Frames [5]) та багато інших.
Дана робота описує побудову моделі паралелізації обчислення невід’ємної
факторизації розріджених матриць надвеликої розмірності, що представляє
особливий інтерес та актуальність для її застосування у великих NLP системах
загального тематичного напрямку, необмежених використанням лише для вузьких
предметних областей.
Задача невід’ємної факторизації розріджених матриць надвеликої
розмірності постала в процесі розробки системи визначення міри семантичної
близькості-зв’язності за технологією латентного семантичного аналізу[6]. Для
побудови системи був оброблений великий текстовий корпус статей англомовної
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
18 © E.М. Насіров
Вікіпедії. Обробка корпусу полягала у лексичному аналізі та лематизації лексем
речень статей та в обчисленні частот вживання множини слів та словосполучень
англійської мови в складі різних статей англомовної Вікіпедії. У результаті була
побудована велика матриця Слова×Статті, яка містила частотну оцінку вживання
слів в текстах статей Вікіпедії. Розмірність матриці дорівнює 2,437,234 слів-
словосполучень на 4,475,180 статей англомовної Вікіпедії. Після цього для
усунення з матриці випадкових даних був встановлений пороговий рівень Т=3,
частотні оцінки в матриці, які менші за пороговий рівень Т, були обнулені). У
результаті була побудована розріджена матриця надвеликого розміру ‒
156,236,043 ненульових елементів при розмірі 2,437,234×4,475,180. Для
невід’ємної факторизації розрідженої матриці такого розміру знадобилася
розробка спеціальної моделі паралелізації матричних обчислень, яка була
реалізована із застосуванням паралельних розподілених обчислень та обчислень
на GPU. Низка реалізацій факторизації матриць була вже реалізована і
представлена у [7,8,9,13]. Але жодна з розроблених моделей не є допустимою для
поставленої задачі. Деякі з них [7,8,9] не задовольняють потреби розмірності
матриці. Модель, запропонована в [13], проводить факторизацію матриць
запропонованого розміру за задовільний час, але потребує занадто великих
розрахункових комп’ютерних потужностей, що є не завжди доступним.
Алгоритм невід’ємної матричної факторизації
Алгоритм невід’ємної матричної факторизації[11] виконує декомпозицію
невід’ємної матриці V на невід’ємні матриці W та H таким чином, щоб:
𝑉 ≈ 𝑊𝐻
Як функція оцінки може бути використана функція виміру відстані між μ
двома невід’ємними матрицями. Однією з таких мір є квадрат Евклідової
метрики:
μ = ‖𝐴 ‒ 𝐵‖2 = ∑
𝑖𝑗
(𝐴𝑖𝑗 ‒ 𝐵𝑖𝑗)2
Така цільова функція обмежена знизу. Нижня границя 0 досягається тоді і
тільки тоді коли
𝐴 = 𝐵
Отже, при використанні Евклідової метрики, факторизація матриці полягає в
мінімізації за умови невід’ємності W та H.‖𝑉 ‒ 𝑊𝐻‖2
Така цільова функція не зростаюча за наступних правил:
𝐻𝑖𝑗 ←𝐻𝑖𝑗
(𝑊𝑇𝑉)𝑖𝑗
(𝑊𝑇𝑊𝐻)𝑖𝑗
(1)
𝑊𝑖𝑗←𝑊𝑖𝑗
(𝑉𝐻𝑇)𝑖𝑗
(𝑊𝐻𝐻𝑇)𝑖𝑗
(2)
Виконання ітерацій алгоритму продовжується до тих пір, поки не буде
досягнута стаціонарна точка, або не буде виконана максимальна кількість
ітерацій.
Аналіз моделі
У таблиці 1 представлено необхідні об’єми пам’яті для зберігання матриць
W та H при різних k при використанні типу даних float (32bit).
Описаний алгоритм на кожній ітерації потребує у 2 рази більше пам’яті для
збережень матриць (не враховуючи потреби на збереження початкової матриці V).
Враховуючи такі потреби в пам'яті, для виконання алгоритму на одному
комп'ютері необхідно проводити збереження даних на жорсткий диск. Далі буде
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
© E.М. Насіров 19
розглянуто та порівняно 2 підходи до паралелізації алгоритму: локальний та
розподілений.
Таблиця 1. Необхідні об’єми пам’яті для зберігання матриць W та H при різних k
K 100 200 300
W 0.98Gb 1.95Gb 2.92Gb
H 1.79Gb 3.58Gb 5.37Gb
Всього 2.76Gb 5.53Gb 8.29Gb
Паралелізація алгоритму з використанням GPU
Для спрощення, зробимо заміну в (1) та (2): . Отримаємо𝐻' = 𝐻𝑇
(𝐻'𝑡)𝑖𝑗 = (𝐻'𝑡 ‒ 1)𝑖𝑗
(𝑉𝑇𝑊𝑡 ‒ 1)𝑖𝑗
(𝐻'𝑡 ‒ 1𝑊 𝑇
𝑡 ‒ 1𝑊𝑡 ‒ 1 )𝑖𝑗
(4)
(𝑊𝑡)𝑖𝑗 = (𝑊𝑡 ‒ 1)𝑖𝑗
(𝑉𝐻 '
𝑡)𝑖𝑗
(𝑊𝑡 ‒ 1𝐻'𝑇
𝑡 𝐻 '
𝑡 )𝑖𝑗
(5)
Таким чином, обидві формули (4) та (5) ми можемо представити в одному
вигляді, завдяки заміні , W та , або W, та на A, B та S відповідно:𝐻’ 𝑉𝑇 𝐻’ 𝑉
𝐴𝑖𝑗 = 𝐴𝑖𝑗
(𝑆𝐵)𝑖𝑗
(𝐴𝐵𝑇𝐵)𝑖𝑗
(6)
Формула (6) може бути представлена як послідовність чотирьох кроків (7):
Такий порядок обчислень є оптимальним для виразу (6). Ці кроки мають
обчислювальну складність , , та відповідно, де 𝑂(𝑘 ∗ (𝑛𝑛𝑧(𝑆) + 𝑛)) 𝑂(𝑘2𝑚) 𝑂(𝑘2𝑛) 𝑂(𝑘𝑛)
– кількість ненульових елементів матриці S. Перші три кроки(7a-7c) 𝑛𝑛𝑧(𝑆)
підтримуються бібліотеками CUDA cuSPARSE[17] та cuBLAS[16]. Четвертий
крок (7d) для виконання потребує реалізації власного ядра GPU, але в той же час,
це відносно швидка операція і тому може бути виконана на CPU.
Так як матриці занадто великі для збереження в пам’яті GPU, ці операції(7a-
7d) повинні виконуватись над частинами, з врахуванням необхідності зменшення
об’ємів обміну даними з графічним адаптером.
Для виразу (7a) повинні розкласти матриці та 𝑆 = (𝑆 '
1|𝑆 '
2|…│𝑆 '
𝑡)𝑇 𝐵 = (𝐵1|𝐵2|…|𝐵𝑟)
та підрахувати С:
𝐶 = (𝑆 '
1𝐵1 ⋯ 𝑆 '
1𝐵𝑟
⋮ ⋱ ⋮
𝑆 '
𝑡𝐵1 ⋯ 𝑆 '
𝑡𝐵𝑟
) (8)
Для виразу (7b) варто розглядати , а отже . 𝐵 = (𝐵'1|𝐵'2|…|𝐵'𝑡) 𝐾 = 𝐵'𝑇1𝐵 '
1…𝐵`𝑇
𝑡𝐵`𝑡
Підрахунок цього виразу не потребує додаткового завантаження будь-яких матриць
у пам'ять графічного адаптера після виконання (7а).
Для підрахунку (7с) ми можемо залишити в пам'яті GPU матрицю К і
помножити матрицю А як стовпчик блоків.
𝐶 = 𝑆𝐵 (7a)
𝐾 = 𝐵𝑇𝐵 (7b)
𝐷 = 𝐴𝐾 (7c)
𝐴𝑖𝑗 = 𝐴𝑖𝑗
𝐶𝑖𝑗
𝐷𝑖𝑗
(7d)
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
20 © E.М. Насіров
Також можна зменшити використання пам’яті завдяки комбінуванню (7d) та
(7с), так як (7d) – поелементне правило і єдине інше правило, в якому
використовується матриця А – (7с). Не буде потреби зберігати в пам’яті матрицю
D, якщо виконувати (7d) на блоці з матриці А, який необхідний для обчислення
певного блоку матриці D.
Складність підрахунку Евклідової метрики між початковою та
факторизованою моделлю складає . Такий підрахунок просто реалізується з О(𝑛𝑚)
використанням графічних адаптерів.
Розподілений алгоритм
Наступним кроком для покращення швидкодії є використання мережі ПК
для проведення обчислень. Розглянемо можливі розподіленні моделі.
Припустимо, що мережа складається з двох вузлів. Можливі наступні моделі
розподілення обчислень:
1. Підраховувати та окремо на різних вузлах. Таким чином обидва 𝑊 𝐻’
вузли будуть перебувати в одному з двох альтернативних режимів. Або будуть
вузлом підтримки іншого вузла (передача даних на інший вузол) або будуть
проводити підрахунки (обчислювати матрицю, за яку відповідають, за
допомогою даних, отриманих з вузла підтримки). У такій моделі розподілення на
кожній ітерації ми повинні будемо передати по мережі дві матриці такого ж
розміру, як і W та H. Також вузол розрахунків буде в основному простоювати,
тому що (7а) є найбільш витратним кроком з усіх чотирьох.
2. Розділити матриці та на блоки та розподілити їх між вузлами. 𝑊 𝐻’
та . Робимо перший вузол відповідальним за , 𝐻' = (𝐻 '
1│𝐻 '
2) 𝑊 = (𝑊1│𝑊2) 𝐻 '
1, 𝑊1
другий за . При такому підході кожен вузол виступає як у ролі вузла 𝐻 '
2, 𝑊2
підтримки, так і у ролі вузла розрахунків одночасно. У такій моделі вузли повинні
передавати по мережі об’єм даних рівний , де 1.5 ∙ (𝑠𝑖𝑧𝑒𝑜𝑓 (𝑊 ) + 𝑠𝑖𝑧𝑒𝑜𝑓 (𝐻))
– об’єм пам’яті, необхідний для зберігання матриці Х 𝑠𝑖𝑧𝑒𝑜𝑓 (𝑋)
3. Розділити матриці та на блоки та розподілити їх між вузлами. 𝑊 𝐻’
та . Робимо перший вузол відповідальним за , 𝐻' = (𝐻1│𝐻2)𝑇 𝑊 = (𝑊1'│𝑊2')𝑇 𝐻1, 𝑊1'
другий за . У цій моделі, аналогічно до попередньої, кожен вузол мережі 𝐻2, 𝑊2'
виступає одночасно як у ролі вузла підтримки, так і у ролі вузла розрахунків.
Об’єм передачі даних вузлом рівний 𝑠𝑖𝑧𝑒𝑜𝑓 (𝑊 ) + 𝑠𝑖𝑧𝑒𝑜𝑓 (𝐻)
У кожній з представлених моделей також є необхідність передачі одної або
декількох матриць [k;k], але їх розміром можна знехтувати в порівнянні з
матрицями W та H. Для підрахунку функції оцінки μ в першій та третій моделі
вузлам необхідно передати дані в об’ємі , де – кількість
(𝑠𝑖𝑧𝑒𝑜𝑓(𝑊) + 𝑠𝑖𝑧𝑒𝑜𝑓(𝐻)) ∗ 𝐾
2 𝐾
вузлів в мережі, у другій моделі необхідно передати в раз більше даних.(𝐾 ‒ 1)
Варто також зазначити, що ріст мережі призведе до експоненціального росту
сумарного об’єму переданих даних, хоча об’єм передачі даних одного вузла буде
не більш ніж .2 ∙ (𝑠𝑖𝑧𝑒𝑜𝑓 (𝑊 ) + 𝑠𝑖𝑧𝑒𝑜𝑓 (𝐻))
Для кращого розподілення розрахунків між вузлами мережі, враховуючи
розрідженість початкової матриці V, необхідно виконати перестановки рядків та
стовпчиків для нормалізації кількості ненульових елементів у кожному блоці.
Очевидно, що третя модель найкраще підходить з точки зору мережевого
обміну даними та використання GPU. Тому саме ця модель була використана в
нашому дослідженні, реалізована з використанням мережі з чотирьох вузлів і
описана далі.
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
© E.М. Насіров 21
Згідно з моделлю 3 необхідно розділити матриці наступним чином: 𝑊, 𝐻` і 𝑉
, , .𝑊 = (𝑊 '
1│𝑊 '
2 | 𝑊 '
3 |𝑊 '
4)𝑇 𝐻' = (𝐻1|𝐻2|𝐻3│𝐻4)𝑇
𝑉 = (𝑉11 ⋯ 𝑉14
⋮ ⋱ ⋮
𝑉41 ⋯ 𝑉44
)
Алгоритм складається з трьох основних фаз: ініціалізації, ітерації,
підрахунку метрики. Під час фази ініціалізації матриці розподіляються 𝑊, 𝐻` і 𝑉
між чотирма вузлами так, щоб i-ий вузол отримав матриці та , де 𝑊'
𝑖, 𝐻𝑖 𝑉𝑘𝑖, 𝑉𝑖𝑘
. Дана фаза представлена на рисунку 1(а).𝑘 = ̅1,…,4
Фаза ітерації складається з двох аналогічних етапів, один для підрахунку , 𝐻'
а другий для . Кожен етап включає 3 кроки. 𝑊
На першому кроці кожний вузол підраховує матрицю розміру 𝑊'
𝑖 × 𝑊'
𝑖
𝑇
𝑘 × 𝑘
та надсилає її до агрегатору. Агрегатор об’єднує всі отримані блоки в одну
матрицю та надсилає отриманий результат всім вузлам. Цей крок представлено 𝐾𝑤
на Рисунку 1(а).
(a) (b)
Рис. 1. Розподілена модель з чотирма вузлами
На другому кроці кожен вузол підраховує власне . (𝑉 𝑇
1𝑖 |𝑉 𝑇
2𝑖 | 𝑉 𝑇
3𝑖 |𝑉 𝑇
4𝑖)
𝑇 × 𝑊'
𝑖
Отримана матриця співпадає за розмірами з . Далі кожний вузол ділить цю 𝐻'
матрицю згідно з початковим розбиттям матриці H та передає отримані блоки
відповідним вузлам. Цей крок представлено на Рисунку 1(b).
На третьому кроці вузли підраховують матрицю та виконують 𝐻𝑖 × 𝐾𝑤
оновлення матриці . Цей крок не потребує передачі даних по мережі. 𝐻'
Ці три кроки необхідні для підрахування матриці . Після поновлення , 𝐻' 𝐻'
аналогічні кроки необхідно виконати для . А саме необхідно підрахувати 𝑊
наступні матриці: , та .𝐻𝑖 × 𝐻𝑇
𝑖 (𝑉 𝑇
1𝑖 |𝑉 𝑇
2𝑖 | 𝑉 𝑇
3𝑖 |𝑉 𝑇
4𝑖)
𝑇 × 𝐻𝑖 𝑊'
𝑖 × 𝐾𝐻
У фазі підрахунку метрики кожен вузол передає відповідний блок всім 𝐻'
іншим блокам. Після отримання всіх блоків, кожний вузол підраховує відповідну
части метрики. Ця фаза також представлена на Рисунку 1(b).
Результати аналізу
Був реалізований розподілений алгоритм з використанням GPU, який був
описаний вище, та проведена факторзація розрідженої матриці оцінок части
вживання слів англійської мови в різних статтях Вікіпедії. Для порівняння
швидкодії була також реалізована локальна модель з використанням GPU та
жорсткого диску для запису даних.
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
22 © E.М. Насіров
Обидві моделі працювали з однаковими вхідними даними. Локальна версія
була запущена на одному з вузлів з тими ж обмеженнями пам'яті. Для проведення
тестів були використані наступні апаратні засоби: Intel Core i7 CPU, NVIDIA
GeForce GTX560 1Gb, 8Gb RAM, 1Gbit LAN, SATA III HD.
У таблиці 2 порівняно час та ресурси, необхідні для виконання однієї
ітерації в локальній та розподіленій версії. У таблиці 3 порівняно час та ресурси,
необхідні для підрахунку функції оцінки . Дані таблиць отриманні при .μ 𝑘 = 300
Таблиця 2. Результати порівняння виконання ітерації локальної та розподіленої
версії
Таблиця 3. Результати порівняння обчислення функції оцінки μ
На рис.2 показано графік отриманої залежності якості результатів
факторизації від k та кількості ітерацій.
Рис 2. Графік залежності збіжності алгоритму факторизації від k та кількості
ітерацій.
Застосування моделі до факторизації тензорів
Для того, щоб обчислити невід'ємні матриці-компоненти {A, B, C},
зазвичай застосовується обмежений оптимізаційний підхід для мінімізації функції
оцінки, що підходить. Зазвичай мінімізують наступну функцію:
, де – 𝐷𝐹(𝑌||⟦𝐴, 𝐵, 𝐶⟧) = ‖𝑌 ‒ ⟦𝐴, 𝐵, 𝐶⟧‖2
𝐹 + α𝐴‖𝐴‖2
𝐹 + α𝐵‖𝐵‖2
𝐹 + α𝐶‖𝐶‖2
𝐹 α𝐴, α𝐵, α𝐶
невід’ємні регуляційні параметри.
Існує щонайменше три різні підходи до розв’язання такої оптимізаційної
задачі. Перший підхід полягає у використанні векторної форми функції оцінки:
. Для розв’язання використовується метод найменших 𝐽(𝑋) = 𝑣𝑒𝑐(𝑌 ‒ [𝐴, 𝐵, 𝐶]) = 0
квадратів. Цей метод для факторизації тензорів вперше використав Паатеро [11].
Якобіан такої функції може мати розмір , а, отже, такий підхід 𝐼𝑇𝑄𝐽 × (𝐼 + 𝑇 + 𝑄)
потребує значних розрахункових витрат.
Local Distributed
Прочитано 34.44Gb 6.22Gb
Записано 16.58Gb 6.22Gb
Час ітерації
(розрахунки)
58s 62s
Час ітерації (I/O) 729s 287s
Local Distributed
Прочитано 13.66Gb 6.22Gb
Записано 0 6.22Gb
Час (розрахунки) 45865s 11371s
Час (I/O) 192s 280s
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
© E.М. Насіров 23
У другому підході Акар, Колда та Дунлаві запропонували штучно
оптимізувати функцію оцінки, використовуючи техніку нелінійної зв’язної
градієнтної оптимізації[1].
Третім, і найпоширенішим, підходом є використання техніки ALS. У цьому
підході підраховується градієнт функції оцінки для кожної матриці окремо.
,∇𝐴𝐷𝐹 =‒ 𝑌(1)(𝐶 ⊙ 𝐵) + 𝐴[(𝐶𝑇𝐶) ⊛ (𝐵𝑇𝐵) + α𝐴𝐼]
, ∇𝐵𝐷𝐹 =‒ 𝑌(2)(𝐶 ⊙ 𝐴) + 𝐵[(𝐶𝑇𝐶) ⊛ (𝐴𝑇𝐴) + α𝐵𝐼]
.∇С𝐷𝐹 =‒ 𝑌3(𝐵 ⊙ 𝐴) + 𝐶[(𝐵𝑇𝐵) ⊛ (𝐴𝑇𝐴) + α𝐶𝐼]
Прирівнюючи кожну компоненту градієнта до 0 та накладаючи умову
невід’ємності, можна отримати ефективні та прості правила оновлення матриць:
,𝐴←[𝑌(1)(𝐶 ⊙ 𝐵) + [(𝐶𝑇𝐶) ⊛ (𝐵𝑇𝐵) + α𝐴𝐼] ‒ 1] +
,𝐵←[𝑌(2)(𝐶 ⊙ 𝐴) + [(𝐶𝑇𝐶) ⊛ (𝐴𝑇𝐴) + α𝐵𝐼] ‒ 1] +
.𝐶←[𝑌(3)(𝐵 ⊙ 𝐴) + [(𝐵𝑇𝐵) ⊛ (𝐴𝑇𝐴) + α𝐶𝐼] ‒ 1] +
Основними перевагами такого підходу є висока швидкість збіжності та
можливість розподілення для задач великої розмірності.
Запропонована вище розподілена модель може бути застосована для
факторизації тензорів. Правила оновлення є однаковими. Тому буде показано
підрахунок на прикладі однієї матриці:
𝐴←[𝑌(1)(𝐶 ⊙ 𝐵) + [(𝐶𝑇𝐶) ⊛ (𝐵𝑇𝐵) + α𝐴𝐼] ‒ 1] +
Для мережі з двох вузлів необхідно розділити матриці та на блоки 𝑊 𝐻’
таким чином, що та , та розподілити їх між вузлами так, С' = (С1│С2)𝑇 𝐵 = (𝐵1'│𝐵2')𝑇
щоб перший вузол був відповідальним за , другий за .С1, 𝐵1' 𝐶2, 𝐵2'
При такому розподіленні на першому кроці кожний вузол підраховує
матрицю розміру та надсилає її до агрегатору. Агрегатор об’єднує всі 𝐶𝑇
𝑖 × 𝐶𝑖 𝑘 × 𝑘
отримані блоки в одну матрицю та надсилає відповідні частини до вузлів. Далі 𝐾𝐶
аналогічним чином виконуються розрахунки для . На наступному кроці (𝐵𝑇𝐵)
вузлам необхідно підрахувати та передати відповідні 𝑆𝑖 = [(𝐶𝑇𝐶)𝑖 ⊛ (𝐵𝑇𝐵)𝑖 + α𝐴𝐼]
матриці на агрегат, на якому підрахується . Після чого вузлам необхідно 𝑆 ‒ 1
підрахувати відповідні частини результуючої матриці у вигляді .(𝐶 ⊙ 𝐵)𝑖 + 𝑆 ‒ 1
𝑖
Таким чином, можливе використання запропонованої розподіленої моделі
до факторизації тензорів.
Оптимізація факторизації матриці зв’язності
Так як розглядувана розріджена матриця є матрицею зв’язності
Слова×Статті, отже можливі перестановки як рядків, так і стовпців початкової
матриці.
Розглядувана розріджена матриця має 156,236,043 ненульових елементів з
10,907,060,852,120 що складає лише 0,014%. Така розрідженість дозволяє
привести матрицю до блочно-діагональної форми за допомогою перестановок
рядків та стовпчиків. У випадку, коли слово може належати декільком блокам,
рядок може бути розділений.
Розміри блоків найкраще обирати такими, що можуть бути повністю
завантажені в пам’ять. У результаті буде отримано N блоків.
Переваги такого підходу:
1. Не потрібно мережевих операцій на кожній ітерації. Необхідне лише
початкове розподілення блоків матриці між вузлами.
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
24 © E.М. Насіров
2. Швидша збіжність. На рис. 3 та рис. 4 показано графіки залежності часу
та кількості ітерацій відповідно, необхідні для факторизації квадратних матриць в
один потік без використання GPU.
3. Швидший підрахунок функції оцінки . Кількість елементів для μ
підрахунку функції оцінки менша в N разів, кількість необхідних перевірок
менша, так як зменшується загальна кількість ітерацій.
4. Зменшення K, а, отже, і зменшення розмірів результатів.
У результаті для кожного слова буде отримано один або декілька рядків та
ідентифікатор блоку, в якому це слово знаходиться. При відновленні, якщо слово
та стаття знаходяться в різних блоках – результатом буде 0, інакше результатом
буде добуток відповідних рядка та стовпчика.
Література
1. Xu, W., Liu, X., & Gong, Y. (2003). Document-clustering based on XXXn-negative matrix
factorization. In Proceedings of SIGIR’03, July 28–August 1, Toronto, CA, pp. 267–273.
2. Farial Shahnaz, Michael W. Berry, V. Paul Pauca, Robert J. Plemmons Document clustering using
nonnegative matrix factorization// Information Processing and Management: Volume 42 Issue 2,
March 2006 P.P. 373 – 386
3. Anatoly Anisimov, Oleksandr Marchenko, Andrey Nikonenko, Elena Porkhun, Volodymyr
Taranukha: Ukrainian WordNet: Creation and Filling. FQAS 2013: 649-660
4. Tim Van de Cruys. 2010. Anon-negative tensor factor-ization model for selectional preference
induction. Natural Language Engineering, 16(4):417–437.
5. Tim Van de Cruys, Laura Rimell, Thierry Poibeau, and Anna Korhonen. 2012. Multi-way Tensor
Factorization for Unsupervised Lexical Acquisition. In International Conference on Computational
Lin-guistics (COLING), Mumbai, India, 08/12/2012-15/12/2012, pages 2703–2720. The COLING
2012 Organizing Committee.
6. Scott Deerwester, Susan T. Dumais, GeorgeW. Furnas, Thomas K. Landauer, and Richard Harshman.
1990. Indexing by latent semantic analysis. JOURNAL OF THE AMERICAN SOCIETY FOR
INFORMATION SCIENCE, 41(6):391–407.
7. Brett W. Bader, Tamara G. Kolda, et al. 2012. Matlab tensor toolbox version 2.5. Available online,
January.
8. Khushboo Kanjani. 2007. Parallel non negative matrix factorization for document clustering. May.
9. Volodymyr Kysenko, Karl Rupp, Oleksandr Marchenko, Siegfried Selberherr, and Anatoly Anisimov.
2012. Gpu-accelerated non-negative matrix factorization for text mining. volume 7337 of Lecture
Notes in Computer Science, pages 158–163. Springer.
10. T.K. Landauer, P.W. Foltz, and D. Laham. 1998. An introduction to latent semantic analysis.
Discourse processes, 25:259–284.
0
500
1000
1500
2000
2500
3000
Ч
ас
,
с
Розмір матриці
0
20
40
60
80
10
00
20
00
30
00
40
00
50
00
60
00
70
00
80
00
90
00
10
00
0
Кі
ль
кі
ст
ь
іте
ра
ці
й
Розмір матриці
Рис. 3. Графік залежності часу ітерацій
від розміру матриці
Рис. 4. Графік залежності кількості
ітерацій від розміру матриці
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
© E.М. Насіров 25
11. Daniel D. Lee and H. Sebastian Seung. 2000. Algorithms for non-negative matrix factorization. In In
NIPS, pages 556–562. MIT Press.
12. Chao Liu, Hung-chih Yang, Jinliang Fan, Li-Wei He, and Yi-Min Wang. 2010. Distributed
nonnegative matrix factorization for web-scale dyadic data anal-ysis on mapreduce. In Proceedings of
the 19th In-ternational Conference on World Wide Web, WWW’10, pages 681–690, New York, NY,
USA. ACM.
13. Rada Mihalcea, Courtney Corley, and Carlo Strappa-rava. 2006. Corpus-based and knowledge-based
measures of text semantic similarity. In IN AAAI06, pages 775–780, Menlo Park, CA; Cambridge,
MA; London. AAAI Press;.
14. nVidia, 2013a. CUBLAS Library User Guide. nVidia, v5.0 edition, October.
15. nVidia, 2013b. CUDA CUSPARSE Library. nVidia, August.
16. Farial Shahnaz, Michael W. Berry, V. Paul Pauca, and Robert J. Plemmons. 2006. Document
clustering using nonnegative matrix factorization. Inf. Process. Manage., 42(2):373–386, March.
17. Wei Xu, Xin Liu, and Yihong Gong. 2003. Document clustering based on non-negative matrix fac-
torization. In Proceedings of the 26th Annual Inter-national ACM SIGIR Conference on Research and
Development in Informaion Retrieval, SIGIR ’03, pages 267–273, New York, NY, USA. ACM.
RESUME
Е.М. Nasirov
Model for parallel non-negative sparse extra-large matrix factorization
This paper proposes parallel methods of non-negative large sparse matrix
factorization - very popular technique in computational linguistics. The problem of non-
negative factorization for a sparse large matrix emerged in the development of a
measure of semantic similarity between words with Latent Semantic Analysis usage.
Previously developed parallel models for Non-Negative Matrix Factorization do not
meet the requirements of the matrix dimensions or requires excessively large
computational resources.
It is difficult to execute NMF algorithm on a single machine, without dumping
data to the hard drive due to excessive memory requirements. Two variants of the
algorithm implementation are described: local with intensive hard drive and GPU usage
and distributed with intensive network and GPU usage. Basic iterations rules were
divided to steps in order that requires a minimal number of calculations in a manner that
reduces amount of excessive memory copying.
Three distribution models were compared. Memory usage and data transmitting
necessity of factorization algorithm was analyzed and optimized. The described
effective GPU-based and distributed algorithms were implemented, tested on the grid of
four nodes and compared by means of large sparse matrices processing.
GPU-based and distributed algorithms were combined, with special attention to
memory usage, which allows larger input matrices to be factorized. The experiments
showed the constructed model is effective. It can be used to perform the tasks of
industrial scale to factorize sparse matrices of large dimension with an acceptable time
using available computing resources. This paper describes modification of proposed
distributed model of matrix mactorization to be used for fast and effective non-negative
factorization of large sparse tensors.
Paper proposes blocks-diagonal approach for factorization of sparse extra-large
matrices which can be transformed to blocks-diagonal form. This approach can speed
up factorization, is easy paralleling, needs less network operations and memory
resources for iterations and results storage.
ISSN 1561 – 5359. Штучний інтелект, 2015, № 3-4
26 © E.М. Насіров
Е.М. Насіров
Модель паралелізації невід'ємної факторизації розріджених матриць
надвеликої розмірності
У цій статті запропоновано паралельні методи невід’ємної факторизації
надвеликих розріджених матриць ‒ популярний метод в комп'ютерній лінгвістиці.
Проблема невід’ємної факторизації розріджених матриць постала в процесі
розробки системи визначення міри семантичної близькості-зв’язності за
технологією Латентного Семантичного Аналізу. Існуючі паралельні моделі для
невід’ємної факторизації матриць не задовольняють потреби розмірності матриці
або вимагають занадто великих обчислювальних ресурсів.
Описано два варіанти реалізації алгоритму: локальний з використанням
жорсткого диска та GPU і розподілений з використанням мережі та використання
GPU. Основні правила ітерації були розділені на кроки з метою, яка вимагає
мінімальної кількості обчислень таким чином, що знижує кількість надлишкового
копіювання пам'яті.
Були зіставлені три моделі розподілу. Використання пам'яті і об’єми
передачі даних, необхідні для роботи алгоритму факторизації були проаналізовані
та оптимізовані. Описані локальна модель з використанням GPU та розподілена
модель були реалізовані, випробувані та порівняні.
Локальний та розподілений алгоритми були об'єднані, з особливою увагою
до використання пам'яті, що дозволяє факторизувати вхідні матриці надвеликої
розмірності. Експерименти показали, що побудована модель є ефективною. Вона
може бути використана для виконання завдань промислового масштабу по
факторізації розріджених матриць надвеликої розмірності за прийнятний час,
використовуючи доступні обчислювальні ресурси.
Ця стаття описує модифікацію запропонованої розподіленої моделі для
швидкої та ефективної факторизації розріджених тензорів великої розмірності.
У статті запропоновано блочно-діагональний підхід до факторизації
розріджених матриць, які можуть бути приведені до блочно-діагональної форми.
Цей підхід може прискорити факторизацію, потребує менше мережевих операцій
та пам'яті для ітерацій і зберігання результатів.
Надійшла до редакції 30.08.2015
|