Основы тензорных вычислений (2022/2023) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Esquerte (обсуждение | вклад) (→Лекции и семинары) |
Esquerte (обсуждение | вклад) |
||
Строка 29: | Строка 29: | ||
* '''Лекция 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/d/dV7cFhCHyoUiwA/Основы%20тензорных%20вычислений%20семинар%202022-09-09T11-34-32Z.mp4 Zoom-запись]] Абстрактные тензоры. Универсальное свойство тензорного произведения. Тензорные диаграммы. Сингулярные числа и векторы (продолжение). | * '''Семинар 1.''' [[https://disk.yandex.ru/i/r5TnpctNcadhOA Конспект] [https://disk.yandex.ru/d/dV7cFhCHyoUiwA/Основы%20тензорных%20вычислений%20семинар%202022-09-09T11-34-32Z.mp4 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. Сложность алгоритмов. Поэлементное умножение тензоров. Поэлементное обращение тензора. | ||
Строка 43: | Строка 43: | ||
* '''Лекция 8. TT-разложение (продолжение).''' [[https://disk.yandex.ru/i/Ghru8n8y9eyYDw Конспект] [https://disk.yandex.ru/i/5LI1P63nzORLQQ Zoom-запись]] Ортогонализация ядер (продолжение). Алгоритм TT-SVD. Эффективная рекомпрессия TT-разложения. Арифметика в 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 с округлением. | * '''Семинар 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 Конспект]] Введение, формулировка, где встречаются. ALS для TT. DMRG. Крестовая аппроксимация матриц. | + | * '''Лекция 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 Конспект]] TT-матрицы (продолжение). Примеры приведения операторов к TT-формату. Переход от канонического разложения к TT-разложению. ALS для TT (продолжение). | + | * '''Семинар 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-ранга. | ||
== Домашние задания == | == Домашние задания == |
Версия 19:29, 24 ноября 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-ранга.
Домашние задания
Теоретические ДЗ выдаются каждые 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.
Итоговая оценка за курс
Итог = Округление(min(10, 0.2 * ДЗ_Теор + 0.15 * ДЗ_Практ + 0.1 * Б + 0.15 * ПР + 0.2 * К + 0.3 * Э))
ДЗ_Теор –– средняя оценка за теоретические домашние задания
ДЗ_Практ –– средняя оценка за практические домашние задания
Б –– средняя оценка за бонусные задачи в ДЗ
ПР — средняя оценка за самостоятельные работы на семинарах
К –– оценка за устный коллоквиум (проводится в начале 2-го модуля)
Э –– письменный экзамен.
Округление арифметическое.