Тензорні розкладання і їх застосування. Лекція в Яндексі

Попередня лекція з Data Fest була присвячена алгоритмами, необхідним для побудови нового виду пошуку. Сьогоднішній доповідь теж в деякому сенсі про різні алгоритми, а точніше про математику, лежить в основі багатьох з них. Про матричних разложениях глядачам розповів доктор наук і керівник групи обчислювальних методів «Сколтеха» Іван Оселедець.


Під катом — розшифровка і більшість слайдів.



Є невелике — щодо machine learning — співтовариство, яке займається лінійною алгеброю. Є лінійна алгебра, а в ній є люди, які займаються мультилінійного алгеброю, тензорними разложениями. Я до них ставлюся. Там отримано достатньо велику кількість цікавих результатів, але в силу здатності спільноти самоорганізовуватися і не виходити назовні, деякі з цих результатів невідомі. До речі, це відноситься і до лінійної алгебри теж. Якщо подивитися на статті провідних конференцій NIPS, ICML і т. д., то можна побачити досить багато статей, пов'язаних з тривіальними фактами лінійної алгебри. Так відбувається, але тим не менш.

Будемо говорити про тензорних разложениях, але насамперед треба сказати про матричні розкладання.



Матриці. Просто двовимірна таблиця. Матричне розкладання — це представлення матриці у вигляді творів булевих простих. Насправді вони використовуються скрізь, у всіх є мобільні телефони, і поки ви сидите, вони вирішують лінійні системи, передають дані, розкладають матриці. Правда, ці матриці дуже невеликі — 4х4, 8х8. Але практично ці матриці дуже важливі.

Треба сказати, що є LU-розкладання, розкладання Гаусса, QR-розкладання, але я буду в основному говорити про сингулярном розкладанні, яке чомусь, наприклад, в курсах лінійної алгебри в наших університетах незаслужено забувається. Читають таку дурницю з точки зору обчислювальної науки, як жорданова форма, яка ніде не використовується. Сингулярне розкладання зазвичай десь в кінці, опціонально і т. д. Це неправильно. Якщо взяти книжку «Gold One Loan» (нерозбірливо — прим. ред.), «Матричний аналіз», то вона починається ні з LU-, ні з QR-, а з сингулярного розкладання. Це представлення матриці на увазі твори унітарної, діагональної та унітарною.

Про матричні розкладання добре те, що про них дійсно багато чого відомо. Для базових розкладань існують ефективні алгоритми, вони стійкі, існує, яке ви можете викликати в MATLAB, Python, написані вони і на Фортране. Коректно розцінювати це як одиничну операція, яку можна порахувати, і ви впевнені, що отримаєте точний результат — що вам не потрібно робити ніяких градієнтних спусків. Фактично це один квант операції. Якщо ви звели своє завдання до обчислення матричних розкладів, то ви її, фактично, вирішили. Це, наприклад, лежить в основі різних спектральних методів. Наприклад, якщо є ЕМ-алгоритм, він ітераційний, у нього повільна збіжність. А якщо вам вдалося отримати спектральний метод, то ви молодці і у вас буде рішення в один крок.

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



Є подивитися на те, що таке сингулярне розкладання і записати його в індексному вигляді, ми отримаємо наступну формулу. Це призводить до класичної старої ідеї — до розділення змінних, якщо повернутися до перших курсів університету. Розкладаємо x від t, а тут відокремлюємо I j, один дискретний індекс відокремлюємо від іншого, тобто представляємо функцію від двох змінних у вигляді добутку функцій від однієї змінної. Ясно, що практично жодна функція в такому вигляді не наближається, але якщо ви напишете суму таких функцій, ви отримаєте досить широкий клас.

Фактично, основне застосування сингулярного розкладання — це побудова таких малоранговых апроксимацій. Це матриця рангу r, і, природно, нас цікавить випадок, коли ранг істотно менше, ніж загальний розмір матриці.

Тут все добре. Ми можемо зафіксувати ранг, поставити завдання пошуку найкращої апроксимації і рішення буде дано для сингулярного розкладання. Насправді там відомо набагато більше і можна це зробити швидше, ніж за допомогою сингулярного розкладання: не обчислюючи всіх елементів матриці і т. д. Існує велика гарна теорія — теорія малоранговых матриць, яка продовжує розвиватися і ще далеко не закрита.



Тим не менш, вона не закрита, але хочеться зробити більше, ніж два індексу.

Мій початковий інтерес до цієї теми був суто теоретичний. Ми вміємо щось робити з матрицями, розкладати їх, представляти в деяких додатках — поки неважливо, в яких. В кінці скажу.

А що буде, якщо замість А(i, j) ми напишемо А (i, jk), і теж спробуємо розділити змінні. Звідси цілком природним чином виникає задача тензорних розкладань. У нас є тензор — під тензором я розумію багатовимірний масив, просту двовимірну таблицю, — і ми хочемо ці багатовимірні масиви, грубо кажучи, стиснути, побудувати малопараметрическое подання і, зазвичай красиві слова говорять, — подолати прокляття розмірності. Насправді цей термін — він, як завжди, з'явився зовсім в іншій зв'язку з зовсім іншої завданням, у роботі Беллмана в 1961 році. Але зараз він використовується в тому сенсі, що в ступені n d — це дуже погано. Якщо ви хочете збільшити d, то у вас буде експонентний ріст і т. д.

Факторизація в самому загальному сенсі: ви намагаєтеся вибрати якийсь клас тензорів, який виникає у вашій прикладної задачі, і побудувати таке малопараметрическое уявлення, що за нього ви досить швидко зможете відновити сам тензор. А параметрів мало. В принципі, можна сказати, що нейронні мережі в якомусь сенсі вирішують задачу апроксимації тензорів, тому що намагаються побудувати відображення простору параметрів кудись ще.



Якщо завдання факторизації, тобто представлення у вигляді добутку простих об'єктів, є матриці і твори матриць з тензорами, то визначити тензори — завдання вже більш складна. Але якщо ми подивимося на індексну запис неповного сингулярного розкладання малоранговой апроксимації, у нас абсолютно природним чином виникне аналогічна формула. Ось вона. Ми намагаємося наблизити тензор об'єктами, які є творами функції від однієї дискретної змінної, функція t1 помножити на функцію t2. Ідея абсолютно природна. Якщо доданок тільки одне, нічого ви так не наблизите. А якщо ви дозволяєте брати досить невелика кількість параметрів, виникає дуже цікавий клас тензорів, який явно або неявно використовується у багатьох задачах методів. Можна сказати, що приблизно такий формат використовується в квантової хімії для подання хвильової функції. Там ще антисимметричность, замість твору виникає визначник — але ціла величезна галузь науки заснована, фактично, на такий сепарабельной апроксимації.

Тому, природно, цікаво вивчити властивості, зрозуміти, що тут відбувається, і т. д.



Ця сутність — подання у вигляді суми твору функцій від однієї змінної — називається канонічним розкладанням. Уперше воно було запропоновано десь у 1927 році. Потім використовувалося далеко не в математиці. Були роботи в статистикою, в журналах, таких як Chemometrics, Psychomatrix, — де люди отримували куби даних. Є ознаки — щось вийшло. Таким чином вони будували багатофакторні моделі. Ці матриці факторів можна інтерпретувати як певні фактори. З них, у свою чергу, можна робити якісь висновки.

Якщо порахувати число параметрів, ми отримаємо d-n-r параметрів. Якщо r маленький, то все добре. Але проблема, яку я намагаюся вирішувати — що це в принципі порахувати таку апроксимацію, навіть якщо відомо, що вона існує, — завдання складне. Можна навіть сказати, що вона NP-складна в загальному випадку, як і задача обчислення рангу. Для матриці це не так. Ранг матриці ви можете порахувати — наприклад, з допомогою Гаусового винятку це можна зробити за полиномиальное число операцій. Тут все не так.

Є приклад тензора розміру 9х9х9, для якого досі невідоме точне значення мінімального числа доданків. Відомо, що воно не більше 23 і не менше 21. Суперкомп'ютери, прості поліноміальні: це питання розв'язності системи поліноміальних рівнянь. Але така задача може бути дуже складною. А тензор має практичне значення. Ранг цього тензора пов'язаний з показником складності алгоритму множення матриць. Штрассен-двійковий логарифм від семи. Відповідно, насправді задача обчислення експоненти зводиться до обчислення канонічного рангу деякого тензора.

У багатьох додатках це подання для якогось конкретного тензора працює добре. Але в загальному випадку ця задача погана.

Нещодавно з'явилася робота досить шанованих людей, де вони це подання з роздільними змінними намагаються пов'язати з глибокими нейронними мережами і доводять якісь результати. Насправді вони, якщо їх розшифрувати, є досить цікавими алгебраїчними результатами по тензорним разложениям. Якщо перевести результати мовами тензорних розкладань, вийде, що одна тензорну розкладання, канонічне, краще іншого. Те, що краще, я ще не показав, а канонічне показав. Канонічне — погане в цьому сенсі. Такий висновок обґрунтовується тим, що канонічна архітектура — shallow, неглибока, а повинна бути глибока, більш велика і т. д.

Тому давайте спробуємо плавно до цього перейти. Для канонічного розкладання оптимізаційні алгоритми сходяться повільно, тобто існує болото і т. д. Якщо подивитися на цю формулу, кожен, хто знайомий з лінійною алгеброю, відразу зрозуміє, який алгоритм можна використовувати. Можна градієнтні спуски використовувати — фіксувати всі співмножники крім одного і отримувати лінійну задачу найменших квадратів. Але такий метод буде досить повільним.

У такої моделі є одна хороша властивість: якщо рішення все-таки знайдено, воно єдине з точністю до тривіальних речей. Наприклад, не виникає проблеми матричних розкладань, коли ви можете вставити s, s-1. Якщо канонічне розкладання пораховано, воно єдине, і це добре. Але на жаль, порахувати його іноді досить складно.



Є інше розкладання Таккера. Це був якийсь психометрик. Ідея в тому, щоб ввести якийсь тут клеючий множник — щоб не було зв'язку кожного з кожним. Все добре, це розкладання стає стійким, що найкраще наближення завжди існує. Але якщо ви спробуєте його використовувати, скажімо, для d=10, то виникне допоміжний двовимірний масив, який потрібно буде зберігати, і прокляття розмірності, хоча і в ослабленому вигляді, залишиться.

Так, наприклад, для тривимірних-чотиривимірних завдань розкладання Таккера чудово працює. Існує досить велика кількість робіт, де воно застосовується. Але тим не менш, наша кінцева мета полягає не в цьому.



Ми хочемо отримати щось, де за замовчуванням немає експоненціального числа параметрів, але де ми всі можемо порахувати. Вихідна ідея була досить проста: якщо для матриць все добре, давайте ліпити матриці з тензорів, багатовимірних масивів. Як це робити? Досить просто. У нас індексів d — давайте розбивати їх на групи, робити матриці, вважати розкладання.

Розбиваємо. Одну частину індексів оголошуємо малими індексами, іншу частину — столбцовыми. Може, як-то переставляємо. В MATLAB і Python це все робиться командою reshape і transpose, вважаємо малоранговую апроксимацію. Інше питання — як ми це робимо.

Звичайно, ми можемо спробувати зробити виникли маленькі масиви рекурсивно. Досить легко бачити, що якщо ми їх зробимо наївним чином, у нас вийде приблизно така складність: rlog d. Вона вже не експоненціальна, але r буде досить великою мірою.

Якщо зробити це акуратно, то — я тільки одну фразу скажу — виникне один додатковий індекс. Його треба вважати новим індексом. Нехай у нас був девятимерный масив і ми розбили індекси на 5+4, розклали отримали додатковий індекс отримали шестимерный і один пятимерный тензор і продовжуємо їх розкладати. У такому вигляді ніякої експоненційної складності не виникає, і виходить уявлення, яке має ось таке число параметрів. А якщо нам хтось сказав, щоб всі отримувані по дорозі матриці мали малий ранг? Виходить така рекурсивна структура. Вона досить противна, програмувати її досить огидно, мені було лінь це робити.



В якийсь момент я зрозумів, що можна вибрати найпростіший вид цієї структури — який, тим не менш, досить потужний. Це те, що стало тензорним поїздом, tensor-train. Ми таке запропонували, ім'я прижилося. Потім виявилось, що ми були, природно, не першими, хто це придумав. У фізиці твердого тіла воно було відоме під назвою matrix product states. Але я на кожному доповіді повторюю, що хорошу річ треба відкрити як мінімум двічі — інакше не дуже зрозуміло, чи хороша вона. Принаймні, це подання відкривалося мінімум два, а то й два з половиною рази або навіть три.

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

Ми представляємо тензор у вигляді добутку об'єктів, які залежать тільки від одного індексу. Фактично, мова йде про поділ змінних, але за одним маленьким винятком: тепер ці маленькі штучки — матриці. Ми перемножуємо, щоб отримати значення тензорів точки, ці матриці. Перший елемент — рядок, потім матриця, матриця, стовпці — ми отримуємо число. А зазначені матриці залежать від параметрів, їх можна зберігати як тривимірний тензор. У нас є колекція матриць, спочатку — колекція рядків. Ми говоримо: нам потрібна нульова рядок звідси, п'ята матриця звідси, третя звідси — ми їх просто перемножуємо. Ясно, що обчислення елемента займає dr2 операцій. В індексному вигляді теж. Компактний такий вигляд.

Начебто нічого сильно не змінюється, але насправді таке подання зберігає всі властивості сингулярного розкладання. Його можна порахувати, можна ортогонализовывать, можна знаходити найкращі апроксимації. Це малопараметрическое різноманіття в безлічі всіх тензорів, але можна сказати, що якщо нам пощастило і рішення на ньому лежить — легко його знайдемо.



Тут — якісь властивості. У нас тепер не один ранг. У матриці тільки один ранг, столбцовый або рядковий, але вони однакові для матриці, так пощастило. Для тензорів рангів багато. Число r спочатку — це канонічний ранг. Тут у нас ранг d-1. Для кожного d свій ранг, у нас багато рангів. Тим не менше, всі ці визначають складність ранги і пам'ять для зберігання такого подання можна порахувати, принаймні, теоретично — як ранги деяких матриць, так званих розгорток. Беремо багатовимірний масив, перетворюємо в матриці, вважаємо ранги — ага, є розкладання з такими рангами.

Чому це називається форматом? Якщо у нас об'єкти зберігаються у такому форматі, алгебраїчні операції додавання, множення, обчислення норми можна зробити прямо не виходячи з формату. При цьому все одно щось відбувається. Наприклад, якщо ми склали два тензора, то результат буде мати ранг, який не перевершує суму рангів. Якщо проробляти таке багато раз в якому-небудь итерационном процесі, то ранг стане дуже великим, навіть попри те, що за d залежність лінійна, а r — квадратична. Спокійно можна працювати з рангом 100-200. Фізики на кластерах вміють працювати з рангами 4000-5000, але більше не можна, тому що треба зберігати досить великі щільні матриці.

Але є дуже простий і красивий алгебраїчний алгоритм, що дозволяє зменшувати ранги. Я маю якусь допустиму точність в нормі Фрабениуса і хочу знайти мінімальні ранги, які дають точність. Але я зменшую ранги. Округлення. Коли ви працюєте з числами з плаваючою точкою, ви ж не зберігайте всі 100 цифр. Ви залишаєте тільки 16 цифр. Ми знаходимо ті параметри, такий розмір цих матриць, які дають допустиму точність. Є надійний робастний алгоритм, який це робить, — він займає 20-30 рядків в MATLAB або на Python.

Є і ще одна гарна річ. Фізики її точно не знали. Цим результатом я пишаюся, він мій з моїм тодішнім шефом, Євгеном Євгеновичем Тартышниковым. Якщо ми знаємо, що даний нам тензор має таку структуру, то ми його точно можемо відновити за dnr2 елементів. Тобто ми, не обчислюючи всіх елементів, можемо подивитися на невелику їх кількість і відновити весь тензор, не використовуючи ні базисів, нічого. Це цікавий факт, він для матриць не наскільки добре відомий, яким міг би бути. Є d = 2, матриця рангу r. Її можна відновити за r стовпцям і r рядками.

Коли у нас є таке різноманіття, ми можемо мінімізувати функціонал з обмеженням на ранг. Стандартна ситуація: доступу до елементам у нас немає, але є якийсь функціонал якості, який ми хотіли б мінімізувати. Для цього виникає цілий окремий напрям досліджень питання, як оптимізувати із зазначеними обмеженнями. Мова йде не про опуклому множині, але воно має багато цікавих топологічних властивостей, що потребують окремого вивчення.

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



Пробіжимося по тому, як рахувати ТТ-ранги. Беремо матрицю, перші k індексів вважаємо малими індексами, останні d-k — столбцовыми. Робимо величезну матрицю, вважаємо ранги. Тоді існує розкладання ось з такими рангами.

Теорема конструктивна і дає алгоритм обчислення. Фактично, мова йде просто про послідовному обчисленні сингулярних розкладань невеликих матриць. І можна довести оцінку стійкості такого алгоритму. Там виникає множник — корінь з d-1 щодо сингулярних чисел, які ми по дорозі відкидаємо. Але в цілому, якщо ми працюємо з точністю 10-6, це ні на що не впливає.

Операції мають лінійну d складність. Ось моя улюблена операція — її можна написати коротше всього. Якщо ми беремо два тензора і хочемо їх поелементно перемножити, то ядра просто перемножуються кронекоровым чином. Розмір ядер був 10х10, значить буде 100х100. Якщо зробити так пару раз, вже буде 10000х10000, тому потрібно округляти.



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

Те ж саме для матриць. Якщо вам хтось дав матрицю рангу 100 і цю факторизацию, побудувати факторизацию рангу 10 можна дешево, не вважаючи всю матрицю.

Проекцію на безліч тензорів з обмеженими рангами теж можна обчислити стійким чином. Це дуже важливо в різних оптимізаційних алгоритмів.



Хрестова апроксимація. Я говорив, що матриці й тензори малого рангу можна відновлювати підмножини елементів. Це незаслужено маловідомий факт. Зараз в Америці він придбав деяку популярність, але тим не менш, все треба перевідкривати і т. д. Однак він давно був відомий і в Росії в групі Тартышникова, і в Німеччині.

Якщо у вас є матриця рангу r, ви можете точно відновити її з r стовпцям і r рядками, використовуючи ось таку чудову формулою. Взяли стовпці, взяли подматрицу, яка невирождена, і ось вона, формула.

Якщо на неї уважно подивитися, з'ясується, що це формула гаусового виключення. Можна спокійно сказати, що все це придумав Гаусс і не мучитися, але тим не менш чудова формула. Якщо матриця — мільйон на мільйон і ви знаєте, що вона рангу 5, то вам в ній досить порахувати 5 стовпців і 5 рядків, щоб відновити її цілком.

Ясно, що виникає проблема пошуку цих стовпців і рядків стійким чином. Ви повинні потрапити в подматрицу, яка досить добре обумовлена.

Існують досить ефективні емпіричні алгоритми, які, природно, не будуть працювати в загальному випадку. Якийсь нехороший чоловік візьме і тут один елемент зіпсує. Ви такий елемент ніколи не знайдете, не переглянувши всю матрицю. Але якщо матриця володіє певним властивістю гладкості і до неї недобрі люди не допускаються, то для класів таких матриць можна довести, що у вас все буде добре. І на практиці ці методи працюють абсолютно блискуче. Усталений алгоритм: вам дали матрицю, що вони це роблять.

Абсолютно те ж саме можна зробити для тензорів. Якщо ми знаємо, що тензори мають малі ранги в змісті ТТ-формату, то можемо потикати в якісь підмножини і відновити весь тензор. Природно, тоді ефект може бути величезним. Ви зможете вважати тензори, кількість елементів яких формально більше, ніж число атомів у Всесвіті. Причому робити це буде на ноутбуці. Цілком ніхто ніколи не вважатиме, але тим не менш.

Існують, як я сказав, ефективні емпіричні алгоритми.

Найсерйозніше напрям досліджень — рішення оптимізаційних задач, до яких зводиться більшість практичних. Коли у вас є якийсь функціонал, невідомий об'єкт може бути проіндексований d-індексами. d-індекс введений або природним чином, або штучні. Це окрема тема. Можна брати вектор довжини 2d і перетворювати його в тензор 2х2х2х2. І в нього будуть малі ранги, навіть якщо взятий вектор складається просто з значень одновимірної функції. Така одна з красивих речей. Можна штучно робити тензори, вводити віртуальні розмірності дані, де їх не було, і отримувати малі ранги.

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

Але у нас є дуже спеціальний формат. Це абсолютно відкрита тема. Виникає спеціальне різноманіття, виникає риманова геометрія. Таке треба вміти робити, але ми багато чого вміємо робити, і у нас є програми, які такі алгоритми реалізують. Мінімізація функціоналу з обмеженням — досить багато завдань можна сформулювати так.

Є два пакету: ttpy для Python і TT-Toolbox для MATLAB. Документовані вони фігово, але все ж працюють, і всі алгоритми, які є у нас, є й там. Базові, просунуті, придумані нами і не тільки нами.

Про приклади застосувань. Так як я однією ногою відчуваю себе в чисельному аналізі, в рішенні диференціальних або інтегральних рівнянь, то насправді йдеться про одну з областей, де машинне навчання не представлено практично ніяк і має шалено погану репутацію. Якщо ти скажеш людині, яка займається вирішенням рівнянь в приватних похідних, що хочеш щось робити нейронними мережами, він буде плюватися. Репутація більш-менш зрозуміла. Напевно, за цим стоїть фундаментальна проблема: в таких рівняннях потрібно отримувати рішення з високою точністю. Потрібні значення 10-6 10-8. Для задач класифікації нейронні мережі — блискуча ідея, а от для завдань регресії — не завжди вдала. Як це можна було б застосувати — зовсім окрема тема, абсолютно порожня. Успішних прикладів мало, і людей, які цим займаються, теж не так багато. Я намагаюся і то, і то, в надії, що щось чудове придумається. Подивимося.

Є відчуття, що можна задіяти, але потрібна серйозна доробка. Не можна взяти умовний TensorFlow і застосувати. Ми взяли, застосували — нічого не працює, треба думати. Коли щось не працює, це чудова ситуація. Значить, ти повинен зрозуміти, чому воно не працює.

Тим не менш, тензори добре працюють в цьому випадку. Є теорема. Ми їх формально дискретизируем завдання на сітці з 260 віртуальних комірок і будуємо рішення на ноутбуці за кілька секунд. Там виникає купа всяких проблем. Ми беремо тривимірний кубик, розбиваємо його на n3 осередків, а n = 2d, тобто 220, є мільйон на мільйон на мільйон. І все перераховане ми перетворюємо в 2х2х2х2, 60-мірний тензор. Ось цю штуку ми й шукаємо.

Насправді, число параметрів дуже маленьке: 2 d, яке 60, і на ранг, який 50. Формально ми вирішуємо задачу, де дуже багато невідомих.

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



Далі є приклад, коли ТТ був застосований безпосередньо до нейронних мереж. Це TensorNet, робота Саші Новікова і групи Дмитра Вєтрова, робота з NIPS минулого року. Просто замість полносвязного шару взято шар, який має таку структуру. У нас виходить нелінійний структурований шар, але при цьому число параметрів падає величезна кількість разів, а точність несильно змінюється.

Можна стискати і згорткові шари. Була у нас робота з групою Віктора Лемпицкого. Він сьогодні буде читати блискучу лекцію, всім рекомендую.

Там ми ТТ не застосовували, застосували канонічне розкладання. Згортковий шар можна представити як згортку з чотиривимірним тензором, який ми просто засунули в ПО, що вважає малоранговые апроксимації. Виявилося, що можна вісім разів стиснути. Там є деталі, безпосередньо воно не спрацювало, але результат наступний: чи можна дійсно стиснути вісім разів, і без особливої втрати точності.



Ось приклад з біології. Що мені подобається в таких речах: можна застосовувати практично один і той же код в біології, в машинному навчанні, в хімії, та ще й не знаючи предметного мови, а перекладаючи все на мову багатовимірних масивів і запускаючи чорний ящик. Звичайно, цієї скриньки потребує доопрацювання, але все ж прикладів застосування в абсолютно різних областях у нас вже досить багато. Мова йде про якомусь біологічному циклі, де завдання шестимерная. Він виникає, коли ведмідь спить — йому потрібно швидко виробити енергію, щоб прогрітися. Це футильный даремний цикл, робота групи Крістофа Шваба з Цюріха. Володимир Козеев, який був студентом нашої кафедри ЕОМ, коли я там працював. Є метод Монте-Карло, вирішальний якесь стохастичне диференціальне рівняння. 1500 ядер — 105 секунд. В MATLAB це все вважалося тисячу секунд. Гарне прискорення.



Вважали коливальні стани молекул. Було 12 ступенів свободи, 12-мірна завдання, приблизно 3012 формальних невідомих. Порівняно з деякими хитрими і досить складними хімічними методами вдалося домогтися прискорення в десятки разів.



Недавня робота на воркшопі з Олександром Новіковим під гордою назвою Exponential Machines, де в якості фіч ми вибираємо x1, x2, всілякі підмножини, яких 2d. Ми запхали їх у тензор 2х2х2х2 і сказали: нехай він буде малого рангу. Працює. Далі виникає оптимізація за цим тензору, треба все робити, але працює.

Останній приклад пов'язаний з рекомендаційними системами. Мій аспірант Женя Фролов, великий експерт у рекомендаційних системах, може годинами про них говорити. Часто поговорити йому про них не з ким, тому якщо хтось цікавиться рекомендаційними системами — напишіть йому, будь ласка. Нещодавно нашу статтю прийняли на RecSys. Він створив якийсь фреймворк для рекомендаційних систем під назвою Polara. Там ми тензори застосували до класичної задачі побудови рекомендацій, де у вас є користувачі, фільми і рейтинг. У цій області є якась проблема: всі сучасні методи рекомендацій не враховують негативний фідбек. Тут приклад: людина говорить, що йому не подобається фільм «Обличчя зі шрамом», а йому SVD рекомендує подивитися ще «Хрещеного батька». «Історія іграшок» йому б більше сподобалася. Стаття написана дуже добре. Ідея така: замість розгляду матриці «користувач — фільм» ми розглядаємо матрицю «користувач — фільм — рейтинг» і пишемо одиницю, якщо користувач поставив оцінку фільму. У якомусь сенсі рейтинги стають вирівняними. Ми до зазначеного тривимірному тензору вже будуємо факторизацию, робимо практично те, що робиться стандартно, і отримуємо щось на зразок парадигми: якщо вам не подобається це, вам, можливо, сподобається щось інше. Ми можемо давати осмислені рекомендації на основі одного негативного фідбек, що досить складно.



Є класи задач, коли у вас є експоненціальна точність — тобто коли помилка за кількістю параметрів буває експоненційної. Є надійний набір алгоритмів. Можна вкласти і сказати, що це теж deep learning. В даній роботі товариша з Ізраїлю як раз говориться, що мова йде про arithmetic circuit. Але для нього є надійний набір алгоритмів, можна вважати.

У нас є сторінка, проект на GitHub, можна писати і питати. Все, спасибі.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.