Теорема представления для матричных произведений состояний

Основная информация

• ID статьи: 2103.08277
• Название: Representation Theorem for Matrix Product States
• Авторы: Erdong Guo, David Draper (Университет Калифорнии, Санта-Крус)
• Классификация: stat.ML cs.LG cs.NE quant-ph
• Дата публикации: 15 марта 2021 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2103.08277

Аннотация

В данной работе исследуется универсальная представимость матричных произведений состояний (Matrix Product States, MPS) с точки зрения булевых и непрерывных функций. Авторы доказывают, что MPS может точно реализовать произвольную булеву функцию и предоставляют конструктивный метод построения соответствующей структуры MPS для любого булева вентиля. Кроме того, доказывается, что пространство функций MPS с масштабно-инвариантной сигмоидальной функцией активации плотно в пространстве непрерывных функций, определённых на компактных подмножествах n-мерного вещественного координатного пространства. Исследуется связь между MPS и нейронными сетями, показывающая эквивалентность MPS с масштабно-инвариантной сигмоидальной функцией однослойной нейронной сети с ядровой функцией. Наконец, обсуждается реализация гауссовского процесса (GP) бесконечно широким MPS через исследование эквивалентной нейронной сети.

Исследовательский контекст и мотивация

Проблемный контекст

1. Возникновение тензорных сетей: Тензорные сети как мощный графический язык для представления многотельных квантовых систем получили широкое применение в квантовой информации, физике конденсированного состояния, прикладной математике и информатике.
2. Проблема представимости MPS: Хотя MPS имеет важное физическое значение в квантовой физике, при использовании его в качестве алгебраического инструмента в машинном обучении возникает естественный вопрос: насколько сильна представимость MPS как алгебраической машины?
3. Необходимость теории универсальной аппроксимации: Подобно теореме универсальной аппроксимации для нейронных сетей, требуется теоретическое доказательство границ представимости MPS.

Исследовательская мотивация

1. Заполнение теоретического пробела: Существующие исследования сосредоточены в основном на физических свойствах MPS, но не хватает теоретического анализа его как аппроксиматора функций.
2. Установление связи между MPS и нейронными сетями: Исследование эквивалентности между MPS и классическими моделями машинного обучения, особенно нейронными сетями.
3. Практические соображения: В практических приложениях полный базис обычно является бесконечномерным, поэтому необходимо исследовать, какое пространство функций может "натянуть" MPS при мягких предположениях.

Основные вклады

1. Точное представление булевых функций: Доказано, что MPS может точно реализовать произвольную булеву функцию с предоставлением конструктивного метода доказательства.
2. Универсальная аппроксимация непрерывных функций: Доказано, что пространство функций MPS с масштабно-инвариантной сигмоидальной активацией плотно в пространстве непрерывных функций (относительно нормы супремума).
3. Эквивалентность MPS и нейронных сетей: Установлена связь между MPS и однослойной нейронной сетью, раскрывающая естественное появление ядровых функций в MPS.
4. Реализация гауссовского процесса: Обсуждение реализации гауссовского процесса через бесконечно широкий MPS.

Подробное описание методов

Определение модели MPS

Стандартная структура MPS

Исходная модель MPS определяется как: $\Psi_l(x|w,B) = \sum_{\{\alpha,s\}} A^{s_1}_{\alpha_1\alpha_2} \cdots A^{s_i}_{l\alpha_i\alpha_{i+1}} \cdots A^{s_n}_{\alpha_n\alpha_1} \Phi^{s_1\cdots s_n}(x)$

где ядровая функция определяется как: $\Phi^{s_1\cdots s_n}(x) = \phi^{s_1}(x_1) \otimes \cdots \otimes \phi^{s_i}(x_i) \cdots \otimes \phi^{s_n}(x_n)$

Модифицированная структура MPS

Для достижения универсальной аппроксимации авторы предлагают модифицированную структуру MPS: $\Psi(x|w,B) = \sum_l \sigma\left(\sum_{\{\alpha,s\}} A^{s_1}_{\alpha_1\alpha_2} \cdots A^{s_i}_{l\alpha_i\alpha_{i+1}} \cdots A^{s_n}_{\alpha_n\alpha_1} \Phi^{s_1\cdots s_n}(x)\right)$

где $\sigma(\cdot)$ — масштабно-инвариантная сигмоидальная функция: $\sigma(x) \to \begin{cases} 0 & x \to -\infty \\ C & x \to +\infty \end{cases}$

Методы представления булевых функций

Реализация базовых булевых вентилей

Реализация вентиля AND (теорема 2.1):

• Ядровая функция: $\phi_i(X_i) = [X_i, 1-X_i]$
• Узел тензора: $A^{s_i} = [1, 0]$, размерность связи $|\alpha| = 1$

Реализация вентиля OR (теорема 2.2):

• Ядровая функция: $\phi_i(X_i) = [X_i, 1-X_i]$
• Размерность связи узла тензора: $|\alpha| = 3$
• Конкретная структура тензора: $A^{s_1}_{\alpha_1\alpha_2} = [[1, 0, 1], [0, 1, 0]]$$A^{s_2}_{\alpha_2\alpha_1} = [[0, 1, 1], [1, 0, 0]]$

Реализация вентиля NOT (теорема 2.3):

• Ядровая функция: $\phi_1(X_1) = 1-X_1$
• Узел тензора: $A^{s_1} = 1$

Универсальный вентиль AND и произвольные булевы функции

Универсальный вентиль AND (теорема 2.4): Для $n$ входных переменных можно реализовать: $\Psi(X_1, \cdots, X_n) = (\bigwedge_{i=1}^l X_i) \bigwedge (\bigwedge_{j=l+1}^n \overline{X_j})$

Произвольная булева функция (теорема 2.5): Путём представления произвольной булевой функции в виде дизъюнктивной нормальной формы соответствующих универсальных вентилей AND можно построить соответствующий MPS. Правила построения:

1. Запись булевой функции в дизъюнктивной нормальной форме, соответствующей таблице истинности
2. Установка размерности связи равной количеству дизъюнктивных членов $m$
3. Заполнение элементов тензора согласно определённым правилам

Теория аппроксимации непрерывных функций

Основная теорема (теорема 3.1)

Пространство функций MPS плотно в $C_0(I^n)$ (пространство непрерывных функций на единичном кубе), то есть для любой $f(x) \in C_0(I^n)$ и любого $\varepsilon > 0$ существует функция MPS $\Psi(x)$ такая, что: $\sup_x |\Psi(x) - f(x)| < \varepsilon$

Методы доказательства

Доказательство линейности (лемма 3.2): Доказательство того, что семейство функций MPS $\mathcal{M}$ является линейным подпространством $C_0(I^n)$:

1. Замкнутость относительно скалярного умножения: использование масштабной инвариантности
2. Замкнутость относительно сложения: построение нового MPS, представляющего сумму двух MPS

Свойство дискриминативности (лемма 3.4): Доказательство того, что масштабно-инвариантная сигмоидальная функция обладает свойством дискриминативности: если конечная знаковая мера $\mu$ такова, что интеграл всех функций MPS равен нулю, то $\mu = 0$.

Доказательство основной теоремы: Использование доказательства от противного с применением теоремы Хана-Банаха и теоремы представления Рисца:

1. Предположение, что $\overline{\mathcal{M}}$ является собственным подмножеством $C_0(I^n)$
2. По теореме Хана-Банаха существует нетривиальный функционал, аннулирующий $\overline{\mathcal{M}}$
3. По теореме представления Рисца ему соответствует нетривиальная мера
4. По свойству дискриминативности эта мера должна быть нулевой, что приводит к противоречию

Эквивалентность MPS и нейронных сетей

Теорема эквивалентности (теорема 3.5)

MPS с масштабно-инвариантной сигмоидальной активацией эквивалентен однослойной нейронной сети с ядровой функцией.

Метод преобразования

Путём свёртывания внутренних индексов $\{\alpha_i\}$ MPS можно записать как: $\Psi(x) = \sum_l \sigma\left(\sum_s W^l_s \Phi^s(x)\right)$

Это именно форма однослойной нейронной сети, где:

• $W^l_s$ — параметры весов
• $\Phi^s(x)$ — ядровая функция, естественно вводящая связь между входными компонентами

Естественное появление ядровых функций

На конкретных примерах показано, как нелинейные ядра, такие как полиномиальные ядра, естественно появляются в эквивалентной нейронной сети, например: $(\Phi^s)^T = [x_1x_2x_3, x_2x_3, x_1x_3, x_1x_2, x_1, x_2, x_3, 1]$

Экспериментальные результаты и анализ примеров

Примеры реализации булевых функций

Вентиль OR с 3 входами: Булево выражение: $f(X_1,X_2,X_3) = X_1 \vee X_2 \vee X_3$ Соответствующая структура тензора MPS подробно приведена в разделе методов.

Вентиль проверки чётности с 3 входами: Булево выражение: $f(X_1,X_2,X_3) = X_1 \oplus X_2 \oplus X_3$ Веса эквивалентной нейронной сети: $W^s = [1, 0, 0, 1, 0, 1, 1, 0]$

Пороговый вентиль Th₃²: Пороговая функция, выдающая 1, когда по крайней мере 2 входа равны 1.

Анализ сложности

Для булева вентиля с $n$ входами в крайнем случае размерность связи требует $O(2^n)$, но путём упрощения карт Карно может быть снижена до $O(2^{n-1})$, при этом общее количество параметров составляет $O(n2^{n-1})$, что сравнимо с эффективностью однослойной нейронной сети.

Связанные работы

Теоретические основы тензорных сетей

• Графическая система тензорного исчисления Пенроуза (1971)
• Методы разложения Шмидта и DMRG Видаля (2003, 2007)
• Систематическое исследование свойств MPS Перес-Гарсией и др. (2006)

Тензорные сети в машинном обучении

• Применение в контролируемом обучении Стауденмайра и Шваба (2016)
• Различные применения тензорных сетей в регрессии, классификации и оценке плотности

Теория универсальной аппроксимации

• Классические работы о универсальной аппроксимации нейронных сетей Кибенко (1989), Хорника (1991)
• Данная работа использует аналогичные методы функционального анализа

Выводы и обсуждение

Основные выводы

1. Теоретическая полнота: MPS обладает способностью представлять произвольные булевы функции и аппроксимировать произвольные непрерывные функции
2. Раскрытие эквивалентности: MPS по существу эквивалентен однослойной нейронной сети с ядровой функцией
3. Важность ядровой функции: Ядровая функция $\Phi^{s_1\cdots s_n}$ является ключом к представимости MPS, а не индексы связей $\{\alpha_i\}$

Ограничения

1. Проблемы практичности: Реализация булевых функций MPS требует экспоненциальной размерности связи
2. Потеря физического смысла: При использовании в качестве чистого алгебраического инструмента MPS теряет важные физические свойства, такие как запутанность в квантовой физике
3. Проектирование ядровой функции: Требуется тщательное проектирование ядровой функции для получения достаточной представимости

Направления будущих исследований

1. Эффективные методы построения: Поиск более эффективных методов построения MPS для снижения сложности
2. Глубокие структуры: Исследование многослойных структур MPS по аналогии с глубокими нейронными сетями
3. Квантовое преимущество: Исследование уникальных преимуществ MPS в квантовой вычислительной среде

Глубокая оценка

Преимущества

1. Значительный теоретический вклад: Первое систематическое исследование представимости MPS с точки зрения аппроксимации функций
2. Строгие доказательства: Использование классических инструментов функционального анализа с тщательной разработкой доказательств
3. Инсайты о связности: Раскрытие глубокой связи между MPS и нейронными сетями, обеспечивающее мост для кросс-доменного понимания
4. Конструктивные доказательства: Не только доказана существование, но и предоставлены конкретные методы построения

Недостатки

1. Ограниченная практичность: Теоретические результаты могут столкнуться с проклятием размерности при практическом применении
2. Недостаточная экспериментальная проверка: Отсутствие крупномасштабных численных экспериментов для проверки теоретических результатов
3. Отсутствие алгоритмов оптимизации: Не обсуждается, как эффективно обучать такие модели MPS
4. Недостаточный сравнительный анализ: Недостаточно подробное сравнение с другими универсальными аппроксиматорами

Влияние

1. Высокая теоретическая ценность: Обеспечивает прочную теоретическую основу для применения тензорных сетей в машинном обучении
2. Кросс-доменное значение: Связывает две области — квантовую физику и машинное обучение
3. Высокая вдохновляющая ценность: Служит важным справочником для последующих исследований представимости тензорных сетей и методов оптимизации

Применимые сценарии

1. Теоретические исследования: Подходит в качестве основополагающей литературы для теории представления тензорных сетей
2. Образовательные цели: Может использоваться для объяснения связи между MPS и нейронными сетями
3. Проектирование алгоритмов: Обеспечивает теоретическое руководство для разработки алгоритмов машинного обучения на основе MPS
4. Квантовое машинное обучение: Обеспечивает теоретическую поддержку для разработки алгоритмов квантового машинного обучения

Библиография

В данной работе цитируются важные работы из нескольких областей — тензорных сетей, квантовой информации, машинного обучения и функционального анализа, включая:

• Теоретические основы тензорных сетей (Пенроуз, 1971; Видаль, 2007; Перес-Гарсия и др., 2006)
• Теория универсальной аппроксимации нейронных сетей (Кибенко, 1989; Хорник, 1991)
• Применение тензорных сетей в машинном обучении (Стауденмайр и Шваб, 2016; и др.)
• Теоретические основы функционального анализа (Фоллэнд, 2013)