Основы тензорных вычислений (2022/2023) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Esquerte (обсуждение | вклад) |
Esquerte (обсуждение | вклад) (→Лекции и семинары) |
||
(не показано 13 промежуточных версии 2 участников) | |||
Строка 22: | Строка 22: | ||
[https://t.me/+vstK2gSXdvUzMzZi Телеграм-канал курса] | [https://t.me/+vstK2gSXdvUzMzZi Телеграм-канал курса] | ||
− | |||
− | |||
== Лекции и семинары == | == Лекции и семинары == | ||
* '''Лекция 1. Введение.''' [[https://disk.yandex.ru/i/kiu97MKE9mTOzA Конспект] [https://disk.yandex.ru/d/dV7cFhCHyoUiwA/Основы%20тензорных%20вычислений%20лекция%202022-09-09T10-05-01Z.mp4 Zoom-запись]] Тензоры и тензорные произведения. Свёртки тензоров. Тензоры как мультилинейные отображения: нормы, сингулярные числа и векторы. | * '''Лекция 1. Введение.''' [[https://disk.yandex.ru/i/kiu97MKE9mTOzA Конспект] [https://disk.yandex.ru/d/dV7cFhCHyoUiwA/Основы%20тензорных%20вычислений%20лекция%202022-09-09T10-05-01Z.mp4 Zoom-запись]] Тензоры и тензорные произведения. Свёртки тензоров. Тензоры как мультилинейные отображения: нормы, сингулярные числа и векторы. | ||
− | * '''Семинар 1.''' [[https://disk.yandex.ru/i/r5TnpctNcadhOA Конспект] [https://disk.yandex.ru/ | + | * '''Семинар 1.''' [[https://disk.yandex.ru/i/r5TnpctNcadhOA Конспект] [https://disk.yandex.ru/i/LZND-fVJgMVhsA Zoom-запись]] Абстрактные тензоры. Универсальное свойство тензорного произведения. Тензорные диаграммы. Сингулярные числа и векторы (продолжение). |
− | * '''Лекция 2. Каноническое разложение тензоров (CP).''' [[https://disk.yandex.ru/i/N2y9Z1an3A1DJw Конспект] [https://disk.yandex.ru/ | + | * '''Лекция 2. Каноническое разложение тензоров (CP).''' [[https://disk.yandex.ru/i/N2y9Z1an3A1DJw Конспект] [https://disk.yandex.ru/i/-aZDOPpocHOxdQ Zoom-запись]] Определение. Канонический ранг тензоров. Произведение Хатри-Рао. Оценки на ранг. Единственность разложения. |
− | * '''Семинар 2.''' [[https://disk.yandex.ru/i/VpBo7wUoAVCUwA Конспект] [https://disk.yandex.ru/ | + | * '''Семинар 2.''' [[https://disk.yandex.ru/i/VpBo7wUoAVCUwA Конспект] [https://disk.yandex.ru/i/vBCHolC5rV1s9w Zoom-запись]] Тензорные диаграммы (продолжение). Каноническое разложение: пример вычисления, комплексный вариант. Приближение тензорами меньшего ранга. |
− | * '''Лекция 3. Алгоритмы вычисления CP-разложения.''' [[https://disk.yandex.ru/i/7fBacInaoOPPOA Конспект] [https://disk.yandex.ru/ | + | * '''Лекция 3. Алгоритмы вычисления CP-разложения.''' [[https://disk.yandex.ru/i/7fBacInaoOPPOA Конспект] [https://disk.yandex.ru/i/8nCQPpqYyfN0Xg Zoom-запись]] Единственность разложения (продолжение). Алгоритм Дженриха. ALS. Гаусс-Ньютон. |
− | * '''Семинар 3.''' [[https://disk.yandex.ru/i/Y1uZduxeVVI15w Конспект] [https://disk.yandex.ru/ | + | * '''Семинар 3.''' [[https://disk.yandex.ru/i/Y1uZduxeVVI15w Конспект] [https://disk.yandex.ru/i/F7S2mwSjD8_Ohw Zoom-запись]] Построение канонического разложения: метод Ньютона, метод Гаусса-Ньютона. |
− | * '''Лекция 4. Обобщение SVD на многомерный случай.''' [[https://disk.yandex.ru/i/H1yQsyauxS6Vdg Конспект] [https:// | + | * '''Лекция 4. Обобщение SVD на многомерный случай.''' [[https://disk.yandex.ru/i/H1yQsyauxS6Vdg Конспект] [https://disk.yandex.ru/i/gfFJHtOEuJhjZw Zoom-запись]] Разложение Таккера. Higher-order SVD (HOSVD). Приближение тензора тензором меньшего ранга, T-HOSVD (truncated HOSVD). |
− | * '''Семинар 4.''' [[https://disk.yandex.ru/i/pk_lbKPMFoULXg Конспект] [https://disk.yandex.ru/ | + | * '''Семинар 4.''' [[https://disk.yandex.ru/i/pk_lbKPMFoULXg Конспект] [https://disk.yandex.ru/i/cIaKxEPE0diDSA Zoom-запись]] T-HOSVD (продолжение). Переход к новому базису в тензорном произведении пространств. Связь между тензорами и ЭЭГ. Эффективное вычисление тензорных операций. |
− | * '''Лекция 5. Обобщение SVD на многомерный случай — 2.''' [[https://disk.yandex.ru/i/o2xmjHO5DbH51Q Конспект] [https:// | + | * '''Лекция 5. Обобщение SVD на многомерный случай — 2.''' [[https://disk.yandex.ru/i/o2xmjHO5DbH51Q Конспект] [https://disk.yandex.ru/i/qNmL1vfLhxigMA Zoom-запись]] Квазиоптимальность T-HOSVD. Алгоритмы поиска разложения Таккера: HOSVD, HOOI. "Арифметика" малоранговых тензоров. |
− | * '''Семинар 5.''' [[https://disk.yandex.ru/i/8hk8hyDjBg7lyA Конспект] [https://disk.yandex.ru/ | + | * '''Семинар 5.''' [[https://disk.yandex.ru/i/8hk8hyDjBg7lyA Конспект] [https://disk.yandex.ru/i/6J2YsfKgEDzZiQ Zoom-запись]] (Не)Единственность разложения Таккера. Приведение разложения Таккера к HOSVD. T-HOSVD (продолжение). |
* '''Лекция 6. Приложения тензорных вычислений.''' [[https://disk.yandex.ru/i/DEQUD0wniNh2kw Конспект] [https://disk.yandex.ru/i/1Jymwxyv9z3RoQ Zoom-запись]] "Арифметика" малоранговых тензоров (продолжение). Некоторые приложения: мультилинейный PCA, задача коллаборативной фильтрации, графы знаний, сжатие слоёв нейросетей. Проклятье размерности. | * '''Лекция 6. Приложения тензорных вычислений.''' [[https://disk.yandex.ru/i/DEQUD0wniNh2kw Конспект] [https://disk.yandex.ru/i/1Jymwxyv9z3RoQ Zoom-запись]] "Арифметика" малоранговых тензоров (продолжение). Некоторые приложения: мультилинейный PCA, задача коллаборативной фильтрации, графы знаний, сжатие слоёв нейросетей. Проклятье размерности. | ||
* '''Семинар 6.''' [[https://disk.yandex.ru/i/uHzi6zJoB9za1g Конспект] [https://disk.yandex.ru/i/pcKMl6gNjFBLQw Zoom-запись]] ST-HOSVD. HOOI vs ALS. Сложность алгоритмов. Поэлементное умножение тензоров. Поэлементное обращение тензора. | * '''Семинар 6.''' [[https://disk.yandex.ru/i/uHzi6zJoB9za1g Конспект] [https://disk.yandex.ru/i/pcKMl6gNjFBLQw Zoom-запись]] ST-HOSVD. HOOI vs ALS. Сложность алгоритмов. Поэлементное умножение тензоров. Поэлементное обращение тензора. | ||
+ | * '''Лекция 7. Разложение тензорного поезда (TT).''' [[https://disk.yandex.ru/i/7OTeq5tyG5XZ1Q Конспект] [https://disk.yandex.ru/i/uWTa39bqY__2IA Zoom-запись]] Определение, формы записи. Сильное кронекерово произведение. TT-ранги. Ортогонализация ядер. | ||
+ | * '''Семинар 7.''' [[https://disk.yandex.ru/i/5B82B-Jx35XMtg Конспект] [https://disk.yandex.ru/i/tVluzYBSE00kwg Zoom-запись]] Разреженные тензоры. Numba. TT-разложение: пример вычисления. | ||
+ | * '''Лекция 8. TT-разложение (продолжение).''' [[https://disk.yandex.ru/i/Ghru8n8y9eyYDw Конспект] [https://disk.yandex.ru/i/5LI1P63nzORLQQ Zoom-запись]] Ортогонализация ядер (продолжение). Алгоритм TT-SVD. Эффективная рекомпрессия TT-разложения. Арифметика в TT-формате. | ||
+ | * '''Семинар 8.''' [[https://disk.yandex.ru/i/VeV_TDLkhnGZqQ Конспект] [https://disk.yandex.ru/i/2g0lgpw8J4n8Yg Zoom-запись]] TT-SVD в виде псевдокода. Почему ошибка в TT-SVD не накапливается экспоненциально? TT-SVD с округлением. | ||
+ | * '''Лекция 9. Линейные операторы в TT-формате.''' [[https://disk.yandex.ru/i/l_oxpfd0rflJyg Конспект] [https://disk.yandex.ru/i/9x12pc6rt4_woA Zoom-запись]] Введение, формулировка, где встречаются. ALS для TT. DMRG. Крестовая аппроксимация матриц. | ||
+ | * '''Семинар 9.''' [[https://disk.yandex.ru/i/hjK5eWk4Rc5Fsw Конспект] [https://disk.yandex.ru/i/DdLzrLL_v9w6JA Zoom-запись]] TT-матрицы (продолжение). Примеры приведения операторов к TT-формату. Переход от канонического разложения к TT-разложению. ALS для TT (продолжение). | ||
+ | * '''Лекция 10. Крестовая аппроксимация тензоров. Риманова оптимизация.''' [[https://disk.yandex.ru/i/XuQe330EE6Z-kg Конспект] [https://disk.yandex.ru/d/YBuZI8MoSNhQzQ Zoom-запись]] Крестовая аппроксимация матриц (продолжение). Крестовая аппроксимация тензоров, TT-cross. Интегрирование многомерных функций. Методы римановой оптимизации. | ||
+ | * '''Семинар 10.''' [[https://disk.yandex.ru/i/qlZ5vvQ2jM-arw Конспект] [https://disk.yandex.ru/d/f0KBV3hJRJbl-A Ноутбук] [https://disk.yandex.ru/d/G3n81itEagfktA Zoom-запись]] Оптимизация на многообразиях (продолжение). Касательное пространство к S^{n-1}. Минимальное собственное значение симметричной вещественной матрицы. Многообразие матриц фиксированного ранга, касательное пространство к нему. Многообразие тензоров фиксированного TT-ранга. | ||
+ | * '''Лекция 11. Риманова оптимизация. Иерархический Таккер.''' [[https://disk.yandex.ru/i/5xm9koAHY90Rqw Конспект] [https://disk.yandex.ru/i/XXMttocMmdsIdw Zoom-запись]] Риманова оптимизация (продолжение). Разложение иерархического Таккера (HT): определение, ранги, ортогонализация, сложение. Замкнутость множеств тензоров ограниченного ранга. | ||
+ | * '''Семинар 11.''' [[https://disk.yandex.ru/i/9iYjKFcMoyIISQ Конспект] [https://disk.yandex.ru/d/hYf8kHcE37zrLQ Ноутбук] [https://disk.yandex.ru/i/SmDjkgsNh6tvSQ Zoom-запись]] Является ли TT частным случаем HT? Степени свободы в HT и TT. Пример HT-разложения. Библиотека ttpy. | ||
+ | * '''Лекция 12. Обзор тензорных сетей.''' [[https://disk.yandex.ru/i/GtHYpjxwUasV8g Конспект] [https://disk.yandex.ru/i/PfY0CQnp8THGkA Zoom-запись]] Замкнутость тензорных сетей: теорема Ландсберга. Популярные тензорные сети: тензорное кольцо (TR), PEPS, MERA. Ранги произвольных развёрток. Канонические формы тензорных сетей. Тензоризация в ML. Приближение функций по сетке. | ||
+ | * '''Семинар 12.''' [[https://disk.yandex.ru/i/W2WUjrEQRhZgQw Конспект] [https://disk.yandex.ru/i/zXdEcLb3kj_aCw Zoom-запись]] Теорема Ландсберга: пример незамкнутого множества. TR-разложение (продолжение). MERA (продолжение). Введение в пракДЗ-3. PEPS (продолжение). | ||
+ | * '''Лекция 13. Вычисление свёрток.''' [[https://disk.yandex.ru/i/aJZS6WLMivLrzQ Конспект] [https://disk.yandex.ru/i/1sRhEItUXQLz3w Zoom-запись]] Тензоризация (продолжение). Билинейные алгоритмы и каноническое разложение. Одномерная свёртка: виды свёрток, алгоритм Тоома-Кука, малоранговый случай. | ||
+ | * '''Семинар 13.''' [[https://disk.yandex.ru/i/z7D-AUFaIyoBng Конспект] [https://disk.yandex.ru/d/RXt1GhKYUhSeLA Ноутбук] [https://disk.yandex.ru/i/HM4HdCFs_mUwEA Zoom-запись]] Тензоризация многочленов. Библиотека TensorNetwork. Билинейные алгоритмы: алгоритм Карацубы. | ||
+ | * '''Лекция 14. Вычисление свёрток — 2.''' [[https://disk.yandex.ru/i/dxCMvH94AOwrXA Конспект] [https://disk.yandex.ru/i/96TG-gFakZRfJg Zoom-запись]] Алгоритм Винограда. Вычисление многомерных свёрток. Свёрточный слой, его сингулярные числа. Тензорные разложения ядра свёртки. | ||
+ | * '''Семинар 14.''' [[https://disk.yandex.ru/i/UlEnLUjNb-mxQQ Конспект] [https://disk.yandex.ru/i/VHglaR1o6tyYaQ Zoom-запись]] Алгоритм Винограда: китайская теорема об остатках для чисел и для полиномов, пример вычисления. Многомерные свёртки (продолжение). "Устойчивость" нейросетей. | ||
== Домашние задания == | == Домашние задания == | ||
Строка 49: | Строка 63: | ||
* '''Практическое ДЗ-1.''' [[https://disk.yandex.ru/d/ond3qqk1qIiYeg/hw_practice/hw1 Папка с файлами]] Дедлайн: 24.10.22 в 23:59. | * '''Практическое ДЗ-1.''' [[https://disk.yandex.ru/d/ond3qqk1qIiYeg/hw_practice/hw1 Папка с файлами]] Дедлайн: 24.10.22 в 23:59. | ||
* '''Теоретическое ДЗ-2.''' [[https://disk.yandex.ru/i/mbCPXXXxO9WljA PDF] [https://disk.yandex.ru/d/6Pwmv-YJrwEgjg TEX]] Дедлайн: 18.10.22 в 23:59. | * '''Теоретическое ДЗ-2.''' [[https://disk.yandex.ru/i/mbCPXXXxO9WljA PDF] [https://disk.yandex.ru/d/6Pwmv-YJrwEgjg TEX]] Дедлайн: 18.10.22 в 23:59. | ||
+ | * '''Теоретическое ДЗ-3.''' [[https://disk.yandex.ru/i/norXtm0LEO73WQ PDF] [https://disk.yandex.ru/d/a_A_aLMiOaQFsw TEX]] Дедлайн: 14.11.22 в 23:59. | ||
+ | * '''Практическое ДЗ-2.''' [[https://disk.yandex.ru/d/0zBI7magEWuuCg Папка с файлами]] Дедлайн: 23.11.22 в 23:59. | ||
+ | * '''Теоретическое ДЗ-4.''' [[https://disk.yandex.ru/i/3eEPmhMOEYotmg PDF]] Дедлайн: 05.12.22 в 23:59. | ||
+ | * '''Теоретическое ДЗ-5.''' [[https://disk.yandex.ru/i/4UQh_QWlnT9ZrQ PDF] [https://disk.yandex.ru/d/SozCxp2wdXlQyw TEX]] Дедлайн: 18.12.22 в 23:59. | ||
+ | * '''Практическое ДЗ-3.''' [[https://disk.yandex.ru/d/LHuCjFyw8gqLMQ Папка с файлами]] Дедлайн: 21.12.22 в 23:59. | ||
== Итоговая оценка за курс == | == Итоговая оценка за курс == |
Текущая версия на 19:18, 25 декабря 2022
Содержание
О курсе
Курс читается для студентов 3-го и 4-го курса ПМИ.
Лектор: Рахуба Максим Владимирович
Семинарист: Высоцкий Лев Игоревич
Учебные ассистенты: Ира Голобородько, Миша Петров
Полезные ссылки
Записи занятий (часть 1) (часть 2)
Лекции и семинары
- Лекция 1. Введение. [Конспект Zoom-запись] Тензоры и тензорные произведения. Свёртки тензоров. Тензоры как мультилинейные отображения: нормы, сингулярные числа и векторы.
- Семинар 1. [Конспект Zoom-запись] Абстрактные тензоры. Универсальное свойство тензорного произведения. Тензорные диаграммы. Сингулярные числа и векторы (продолжение).
- Лекция 2. Каноническое разложение тензоров (CP). [Конспект Zoom-запись] Определение. Канонический ранг тензоров. Произведение Хатри-Рао. Оценки на ранг. Единственность разложения.
- Семинар 2. [Конспект Zoom-запись] Тензорные диаграммы (продолжение). Каноническое разложение: пример вычисления, комплексный вариант. Приближение тензорами меньшего ранга.
- Лекция 3. Алгоритмы вычисления CP-разложения. [Конспект Zoom-запись] Единственность разложения (продолжение). Алгоритм Дженриха. ALS. Гаусс-Ньютон.
- Семинар 3. [Конспект Zoom-запись] Построение канонического разложения: метод Ньютона, метод Гаусса-Ньютона.
- Лекция 4. Обобщение SVD на многомерный случай. [Конспект Zoom-запись] Разложение Таккера. Higher-order SVD (HOSVD). Приближение тензора тензором меньшего ранга, T-HOSVD (truncated HOSVD).
- Семинар 4. [Конспект Zoom-запись] T-HOSVD (продолжение). Переход к новому базису в тензорном произведении пространств. Связь между тензорами и ЭЭГ. Эффективное вычисление тензорных операций.
- Лекция 5. Обобщение SVD на многомерный случай — 2. [Конспект Zoom-запись] Квазиоптимальность T-HOSVD. Алгоритмы поиска разложения Таккера: HOSVD, HOOI. "Арифметика" малоранговых тензоров.
- Семинар 5. [Конспект Zoom-запись] (Не)Единственность разложения Таккера. Приведение разложения Таккера к HOSVD. T-HOSVD (продолжение).
- Лекция 6. Приложения тензорных вычислений. [Конспект Zoom-запись] "Арифметика" малоранговых тензоров (продолжение). Некоторые приложения: мультилинейный PCA, задача коллаборативной фильтрации, графы знаний, сжатие слоёв нейросетей. Проклятье размерности.
- Семинар 6. [Конспект Zoom-запись] ST-HOSVD. HOOI vs ALS. Сложность алгоритмов. Поэлементное умножение тензоров. Поэлементное обращение тензора.
- Лекция 7. Разложение тензорного поезда (TT). [Конспект Zoom-запись] Определение, формы записи. Сильное кронекерово произведение. TT-ранги. Ортогонализация ядер.
- Семинар 7. [Конспект Zoom-запись] Разреженные тензоры. Numba. TT-разложение: пример вычисления.
- Лекция 8. TT-разложение (продолжение). [Конспект Zoom-запись] Ортогонализация ядер (продолжение). Алгоритм TT-SVD. Эффективная рекомпрессия TT-разложения. Арифметика в TT-формате.
- Семинар 8. [Конспект Zoom-запись] TT-SVD в виде псевдокода. Почему ошибка в TT-SVD не накапливается экспоненциально? TT-SVD с округлением.
- Лекция 9. Линейные операторы в TT-формате. [Конспект Zoom-запись] Введение, формулировка, где встречаются. ALS для TT. DMRG. Крестовая аппроксимация матриц.
- Семинар 9. [Конспект Zoom-запись] TT-матрицы (продолжение). Примеры приведения операторов к TT-формату. Переход от канонического разложения к TT-разложению. ALS для TT (продолжение).
- Лекция 10. Крестовая аппроксимация тензоров. Риманова оптимизация. [Конспект Zoom-запись] Крестовая аппроксимация матриц (продолжение). Крестовая аппроксимация тензоров, TT-cross. Интегрирование многомерных функций. Методы римановой оптимизации.
- Семинар 10. [Конспект Ноутбук Zoom-запись] Оптимизация на многообразиях (продолжение). Касательное пространство к S^{n-1}. Минимальное собственное значение симметричной вещественной матрицы. Многообразие матриц фиксированного ранга, касательное пространство к нему. Многообразие тензоров фиксированного TT-ранга.
- Лекция 11. Риманова оптимизация. Иерархический Таккер. [Конспект Zoom-запись] Риманова оптимизация (продолжение). Разложение иерархического Таккера (HT): определение, ранги, ортогонализация, сложение. Замкнутость множеств тензоров ограниченного ранга.
- Семинар 11. [Конспект Ноутбук Zoom-запись] Является ли TT частным случаем HT? Степени свободы в HT и TT. Пример HT-разложения. Библиотека ttpy.
- Лекция 12. Обзор тензорных сетей. [Конспект Zoom-запись] Замкнутость тензорных сетей: теорема Ландсберга. Популярные тензорные сети: тензорное кольцо (TR), PEPS, MERA. Ранги произвольных развёрток. Канонические формы тензорных сетей. Тензоризация в ML. Приближение функций по сетке.
- Семинар 12. [Конспект Zoom-запись] Теорема Ландсберга: пример незамкнутого множества. TR-разложение (продолжение). MERA (продолжение). Введение в пракДЗ-3. PEPS (продолжение).
- Лекция 13. Вычисление свёрток. [Конспект Zoom-запись] Тензоризация (продолжение). Билинейные алгоритмы и каноническое разложение. Одномерная свёртка: виды свёрток, алгоритм Тоома-Кука, малоранговый случай.
- Семинар 13. [Конспект Ноутбук Zoom-запись] Тензоризация многочленов. Библиотека TensorNetwork. Билинейные алгоритмы: алгоритм Карацубы.
- Лекция 14. Вычисление свёрток — 2. [Конспект Zoom-запись] Алгоритм Винограда. Вычисление многомерных свёрток. Свёрточный слой, его сингулярные числа. Тензорные разложения ядра свёртки.
- Семинар 14. [Конспект Zoom-запись] Алгоритм Винограда: китайская теорема об остатках для чисел и для полиномов, пример вычисления. Многомерные свёртки (продолжение). "Устойчивость" нейросетей.
Домашние задания
Теоретические ДЗ выдаются каждые 2 или 3 недели.
Также планируется 3-4 практических ДЗ.
- Теоретическое ДЗ-1. [PDF TEX] Дедлайн: 03.10.22 в 23:59.
- Практическое ДЗ-1. [Папка с файлами] Дедлайн: 24.10.22 в 23:59.
- Теоретическое ДЗ-2. [PDF TEX] Дедлайн: 18.10.22 в 23:59.
- Теоретическое ДЗ-3. [PDF TEX] Дедлайн: 14.11.22 в 23:59.
- Практическое ДЗ-2. [Папка с файлами] Дедлайн: 23.11.22 в 23:59.
- Теоретическое ДЗ-4. [PDF] Дедлайн: 05.12.22 в 23:59.
- Теоретическое ДЗ-5. [PDF TEX] Дедлайн: 18.12.22 в 23:59.
- Практическое ДЗ-3. [Папка с файлами] Дедлайн: 21.12.22 в 23:59.
Итоговая оценка за курс
Итог = Округление(min(10, 0.2 * ДЗ_Теор + 0.15 * ДЗ_Практ + 0.1 * Б + 0.15 * ПР + 0.2 * К + 0.3 * Э))
ДЗ_Теор –– средняя оценка за теоретические домашние задания
ДЗ_Практ –– средняя оценка за практические домашние задания
Б –– средняя оценка за бонусные задачи в ДЗ
ПР — средняя оценка за самостоятельные работы на семинарах
К –– оценка за устный коллоквиум (проводится в начале 2-го модуля)
Э –– письменный экзамен.
Округление арифметическое.