В полилинейной алгебре , то разложение тензора ранга или каноническое полиадическое разложение (CPD) является одним обобщением матрицы сингулярного разложения (SVD) для тензоров , которые нашли применение в статистике , обработки сигналов , компьютерное зрения , компьютерной графики , психометрии , лингвистики и хемометрия . Разложение по тензорным рангам было введено Хичкоком в 1927 году [1] и позже переоткрыто несколько раз, особенно в психометрике. [2][3] По этой причине разложение тензорного ранга часто называют CANDECOMP, [2] PARAFAC, [3] или CANDECOMP / PARAFAC (CP).
Другое популярное обобщение матрицы SVD известно как разложение по сингулярным числам высшего порядка .
Обозначение
Скалярная переменная обозначается строчными курсивными буквами, а постоянный скаляр обозначается заглавной курсивной буквой, .
Индексы обозначаются комбинацией строчных и прописных курсивных букв, . Множественные индексы, с которыми можно столкнуться при обращении к множественным модам тензора, удобно обозначать как где .
Вектор обозначается строчными полужирными буквами Times Roman, а матрица обозначается жирным шрифтом в верхнем регистре .
Тензор высшего порядка обозначается каллиграфическими буквами,. Элементтензор порядка обозначается или же .
Определение
Тензор - это полилинейное преобразование, которое отображает набор векторных пространств в другое векторное пространство. Тензор данных - это набор многомерных наблюдений, организованных в M-образный массив.
Рассмотрим тензор данных , где это либо реальное поле или сложное поле . Каждые (заказ-, относится к количеству мод) тензор в этом пространстве может быть представлен достаточно большим как линейная комбинация тензоры ранга 1:
где а также где . Когда количество сроков минимально в приведенном выше выражении, то называется рангом тензора, а разложение часто называют разложением (тензорного) ранга , минимальным CP-разложением или каноническим полиадическим разложением (CPD) . Напротив, если количество членов не минимально, то указанное выше разложение часто называют-членная декомпозиция , CANDECOMP / PARAFAC или полиадическая декомпозиция .
Тензорный ранг
В отличие от случая матриц, ранг тензора в настоящее время недостаточно изучен. Известно, что задача вычисления ранга тензора NP-сложна . [4] Единственный известный хорошо понятный случай состоит из тензоров в, ранг которого может быть получен из нормальной формы Кронекера - Вейерштрасса пучка линейных матриц, который представляет тензор. [5] Существует простой алгоритм с полиномиальным временем для подтверждения того, что тензор имеет ранг 1, а именно разложение по сингулярным значениям высшего порядка .
Ранг тензора нулей условно равен нулю. Ранг тензора один, при условии, что .
Полевая зависимость
Ранг тензора зависит от поля, по которому тензор разлагается. Известно, что некоторые вещественные тензоры могут допускать комплексное разложение, ранг которого строго меньше ранга действительного разложения того же тензора. В качестве примера [6] рассмотрим следующий вещественный тензор
где . Известно, что ранг этого тензора по действительным числам равен 3, в то время как его комплексный ранг равен только 2, потому что он является суммой комплексного тензора ранга 1 с его комплексно сопряженным элементом , а именно
где .
Напротив, ранг реальных матриц никогда не будет уменьшаться при расширении поля до: ранг действительной матрицы и ранг комплексной матрицы совпадают для действительных матриц.
Общий ранг
Общий ранг определяется как наименьший ранг такое, что замыкание в топологии Зарисского множества тензоров ранга не выше это все пространство . В случае комплексных тензоров тензоры ранга не вышеобразуют плотный набор : каждый тензор в вышеупомянутом пространстве либо имеет ранг меньше, чем общий ранг, либо это предел в евклидовой топологии последовательности тензоров из. В случае вещественных тензоров набор тензоров ранга не вышетолько образует открытое множество положительной меры в евклидовой топологии. Могут существовать евклидово открытые множества тензоров ранга строго выше общего ранга. Все ранги, появляющиеся на открытых множествах в евклидовой топологии, называются типичными рангами . Наименьший типичный ранг называется общим рангом; это определение применимо как к комплексным, так и к действительным тензорам. Общий ранг тензорных пространств был первоначально изучен в 1983 году Фолькером Штрассеном . [7]
В качестве иллюстрации приведенных выше концепций известно, что как 2, так и 3 являются типичными рангами в то время как общий ранг равно 2. Практически это означает, что вещественный тензор, выбранный случайным образом (из непрерывной вероятностной меры на пространстве тензоров), имеет размер будет тензором ранга 1 с вероятностью ноль, тензором ранга 2 с положительной вероятностью и тензором ранга 3 с положительной вероятностью. С другой стороны, случайно выбранный комплексный тензор того же размера будет тензором ранга 1 с вероятностью ноль, тензором ранга 2 с вероятностью один и тензором ранга 3 с вероятностью ноль. Известно даже, что типичный вещественный тензор ранга 3 в будет иметь комплексный ранг, равный 2.
Общий ранг тензорных пространств зависит от различия между сбалансированными и несбалансированными тензорными пространствами. Тензорное пространство, где , называется несбалансированным, когда
в противном случае он называется сбалансированным .
Несбалансированные тензорные пространства
Когда первый множитель очень велик по сравнению с другими множителями в тензорном произведении, тогда тензорное пространство по существу ведет себя как матричное пространство. Общий ранг тензоров, живущих в несбалансированных тензорных пространствах, как известно, равен
почти везде . Точнее, ранг каждого тензора в несбалансированном тензорном пространстве, где - некоторое неопределенное замкнутое множество в топологии Зарисского, равняется указанному выше значению. [8]
Сбалансированные тензорные пространства
Ожидаемый общий ранг тензоров , живущих в сбалансированном пространстве тензоров равно
почти всюду для комплексных тензоров и на евклидово-открытом множестве для вещественных тензоров, где
Точнее, ранг каждого тензора в , где - некоторое неопределенное замкнутое множество в топологии Зарисского , как ожидается, будет равно указанному выше значению. [9] Для вещественных тензоров- наименьший ранг, который, как ожидается, встречается на множестве положительной евклидовой меры. Значениечасто называют ожидаемым общим рангом тензорного пространствапотому что это верно только предположительно. Известно, что истинный общий ранг всегда удовлетворяет
Гипотеза Або – Оттавиани – Петерсона [9] утверждает, что равенство ожидается, т. Е., со следующими исключительными случаями:
В каждом из этих исключительных случаев общий ранг, как известно, равен . Отметим, что в то время как набор тензоров ранга 3 в является дефектным (13, а не ожидаемым 14), общий ранг в этом пространстве все еще является ожидаемым, 4.
Гипотеза АОП полностью доказана в ряде частных случаев. Ликтейг еще в 1985 году показал, что, при условии, что . [10] В 2011 году большой прорыв был сделан Каталисано, Герамита и Джимильяно, которые доказали, что ожидаемая размерность множества рангов тензоры формата является ожидаемым, за исключением тензоров ранга 3 в четырехфакторном случае, но ожидаемый ранг в этом случае по-прежнему равен 4. Как следствие, для всех бинарных тензоров. [11]
Максимальный ранг
Максимальный ранг , который может быть принят любой из тензоров в пространстве тензоров неизвестно в целом; отсутствует даже предположение об этом максимальном ранге. В настоящее время лучшая общая верхняя оценка утверждает, что максимальный ранг из , где , удовлетворяет
где является ( как минимум) общий ранг из. [12] Как известно, указанное выше неравенство может быть строгим. Например, общий ранг тензоров в равно двум, так что приведенная выше оценка дает , а известно, что максимальный ранг равен 3. [6]
Пограничный ранг
Ранг- тензор называется граничным тензором, если существует последовательность тензоров ранга не выше чей предел . Еслиэто наименьшее значение , для которого такая последовательность сходится существует, то она называется граница ранга из. Для тензоров порядка 2, т. Е. Матриц, ранг и граничный ранг всегда совпадают, однако для тензоров порядкаони могут отличаться. Тензоры границ были впервые изучены в контексте алгоритмов быстрого приближенного умножения матриц Бини, Лотти и Романи в 1980 году [13].
Классическим примером тензора границы является тензор ранга 3
Его можно сколь угодно хорошо аппроксимировать следующей последовательностью тензоров ранга 2
в виде . Следовательно, его граничный ранг равен 2, что строго меньше его ранга. Когда два вектора ортогональны, этот пример также известен как состояние W .
Характеристики
Идентифицируемость
Из определения чистого тензора следует, что тогда и только тогда, когда существует такой, что а также для всех м . По этой причине параметры тензора ранга 1 называются идентифицируемыми или по существу уникальными. Ранг- тензор называется идентифицируемым, если каждое его разложение тензорного ранга является суммой одного и того же набора различные тензоры где имеют ранг 1. Опознаваемый ранг - таким образом, имеет только одно существенно уникальное разложение
Общая идентифицируемость
Тензоры порядка 2 в , т.е. матрицы, не идентифицируются для . По существу это следует из наблюдения
Ситуация полностью меняется для тензоров высших порядков в с участием и все . Для простоты обозначений, без ограничения общности предположим, что множители упорядочены так, что. Позволятьобозначим множество тензоров ранга, ограниченного . Затем следующее утверждение было доказано с помощью компьютерного доказательства для всех пространств размерности, [15] и предполагается, что это справедливо в целом: [15] [16] [17]
Существует замкнутое множество в топологии Зарисского такая, что каждый тензор идентифицируемый (в этом случае называется обобщенно идентифицируемым ), если не выполняется один из следующих исключительных случаев:
- Ранг слишком велик: ;
- Пространство несбалансировано идентифицируемостью, т. Е. , и ранг слишком велик: ;
- Пространство - дефектный корпус и ранг ;
- Пространство - дефектный корпус , где , а ранг ;
- Пространство и ранг ;
- Пространство и ранг ; или же
- Пространство и ранг .
- Пространство идеальное, т.е. является целым числом, а ранг равен .
В этих исключительных случаях общее (а также минимальное) количество комплексных разложений равно
- оказался в первых 4 случаях;
- в случае 5 оказалось два; [18]
- ожидается, что [19] будет шесть в случае 6;
- в случае 7 оказалось два; [20] и
- Ожидается, что [19] будет не менее двух в случае 8, за исключением двух идентифицируемых случаев а также .
Таким образом, общий тензор порядка и ранг то, что не является идентифицируемым - предполагается, что несбалансированный будет идентифицируемым (по модулю исключительных случаев в небольших помещениях).
Некорректность задачи стандартного приближения
Задача аппроксимации ранга требует ранга наиболее близкое (в обычной евклидовой топологии) разложение к некоторому рангу тензор , где . То есть пытаются решить
где - норма Фробениуса .
В статье де Сильвы и Лима 2008 г. [6] было показано, что указанная выше стандартная задача аппроксимации может быть некорректной . Решение вышеупомянутой проблемы может иногда не существовать, потому что набор, по которому выполняется оптимизация, не закрыт. Таким образом, минимизатор может не существовать, даже если существует инфимум. В частности, известно, что некоторые так называемые граничные тензоры могут быть сколь угодно хорошо аппроксимированы последовательностью тензоров ранга не более, хотя предел последовательности сходится к тензору ранга строго выше, чем . Тензор 3-го ранга
можно сколь угодно хорошо аппроксимировать следующей последовательностью тензоров ранга 2
в виде . Этот пример четко иллюстрирует общий принцип, согласно которому последовательность рангов -тензоры, сходящиеся к тензору строго более высокого ранга, должны допускать по крайней мере два отдельных члена ранга 1, нормы которых становятся неограниченными. Формулируется формально, когда последовательность
имеет свойство, что (в евклидовой топологии) как , то должно существовать хотя бы такой, что
в виде . Это явление часто встречается при попытке аппроксимировать тензор с помощью алгоритмов численной оптимизации. Иногда это называют проблемой расходящихся компонентов . Кроме того, было показано, что случайный тензор низкого ранга над вещественными числами может не допускать приближения ранга 2 с положительной вероятностью, что привело к пониманию того, что проблема некорректности является важным фактором при использовании разложения по тензорному рангу.
Обычное частичное решение проблемы некорректности состоит в наложении дополнительного ограничения неравенства, которое ограничивает норму отдельных членов ранга 1 некоторой константой. Другие ограничения, которые приводят к замкнутому набору и, следовательно, к корректной задаче оптимизации, включают наложение положительности или ограниченного внутреннего продукта, строго меньшего, чем единица, между членами ранга 1, появляющимися в искомой декомпозиции.
Расчет CPD
Чередующиеся алгоритмы:
- альтернативный метод наименьших квадратов (ALS)
- чередующаяся послойная диагонализация (ASD)
Прямые алгоритмы:
- карандашные алгоритмы [21] [22] [23] [24] [25] [26] [27]
- моментные алгоритмы [28]
Общие алгоритмы оптимизации:
- одновременная диагонализация (SD)
- одновременное обобщенное разложение Шура (SGSD)
- Левенберг-Марквардт (LM)
- нелинейный сопряженный градиент (NCG)
- ограниченная память BFGS (L-BFGS)
Общие алгоритмы решения полиномиальной системы:
- продолжение гомотопии [29]
Приложения
В машинном обучении CP-декомпозиция является центральным ингредиентом в обучении вероятностных моделей скрытых переменных с помощью техники согласования моментов. Например, рассмотрим многовидовую модель [30], которая представляет собой вероятностную модель скрытых переменных. В этой модели создание выборок постулируется следующим образом: существует скрытая случайная величина, которая не наблюдается напрямую, при условии, что существует несколько условно независимых случайных величин, известных как различные «представления» скрытой переменной. Для простоты предположим, что есть три симметричных вида. из -состояние категориальная скрытая переменная . Тогда эмпирический третий момент этой модели скрытых переменных можно записать как:.
В таких приложениях, как тематическое моделирование , это можно интерпретировать как совместное появление слов в документе. Тогда собственные значения этого тензора эмпирического момента можно интерпретировать как вероятность выбора конкретной темы и каждого столбца фактор-матрицы. соответствует вероятностям слов в лексике в соответствующей теме.
Смотрите также
- Скрытый анализ класса
- Мультилинейное подпространственное обучение
- Разложение по сингулярным числам
- Разложение Таккера
- Разложение по сингулярным числам высшего порядка
- Тензорная декомпозиция
Рекомендации
- ^ FL Хичкок (1927). «Выражение тензора или полиадики как суммы произведений». Журнал математики и физики . 6 : 164–189.
- ^ а б Кэрролл, JD ; Чанг, Дж. (1970). «Анализ индивидуальных различий в многомерном масштабировании с помощью n- стороннего обобщения разложения Эккарта – Юнга». Психометрика . 35 (3): 283–319. DOI : 10.1007 / BF02310791 .
- ^ а б Харшман, Ричард А. (1970). «Основы процедуры PARAFAC: модели и условия для« пояснительного »многомодального факторного анализа» (PDF) . Рабочие документы UCLA по фонетике . 16 : 84. № 10,085. Архивировано из оригинального (PDF) 10 октября 2004 года.
- ^ Хиллар, CJ ; Лим, Л. (2013). «Большинство тензорных задач NP-Hard». Журнал ACM . 60 (6): 1–39. arXiv : 0911.1393 . DOI : 10.1145 / 2512329 .
- ^ Ландсберг, JM (2012). Тензоры: геометрия и приложения . AMS.
- ^ а б в де Сильва, В .; Лим, Л. (2008). «Тензорный ранг и некорректность задачи наилучшего приближения низкого ранга». Журнал SIAM по матричному анализу и приложениям . 30 (3): 1084–1127. arXiv : math / 0607647 . DOI : 10.1137 / 06066518x .
- ^ Штрассен, В. (1983). «Ранг и оптимальное вычисление типовых тензоров» . Линейная алгебра и ее приложения . 52/53: 645–685. DOI : 10.1016 / 0024-3795 (83) 80041-X .
- ^ Каталисано, М.В .; Герамита, А.В .; Джимильяно, А. (2002). «Ряды тензоров, секущие разновидности разновидностей Сегре и жирные точки» . Линейная алгебра и ее приложения . 355 : 263–285. DOI : 10.1016 / s0024-3795 (02) 00352-X .
- ^ а б Або, Х .; Оттавиани, Г .; Петерсон, К. (2009). «Индукция для секущих разновидностей разновидностей Сегре». Труды Американского математического общества . 361 (2): 767–792. arXiv : math / 0607191 . DOI : 10,1090 / s0002-9947-08-04725-9 .
- ^ Ликтейг, Томас (1985). «Типичный тензорный ранг» . Линейная алгебра и ее приложения . 69 : 95–120. DOI : 10.1016 / 0024-3795 (85) 90070-9 .
- ^ Каталисано, М.В .; Герамита, А.В .; Джимильяно, А. (2011). "Секущие разновидности1 × ··· ×1 ( n раз) не являются дефектными для n ≥ 5 ". Журнал алгебраической геометрии . 20 (2): 295–327. Doi : 10.1090 / s1056-3911-10-00537-0 .
- ^ Блехкерман, Г .; Тейтлер, З. (2014). «По высшим, типовым и родовым рангам». Mathematische Annalen . В прессе. (3–4): 1–11. arXiv : 1402.2371 . DOI : 10.1007 / s00208-014-1150-3 .
- ^ Бини, Д .; Lotti, G .; Романи, Ф. (1980). «Приближенные решения вычислительной задачи билинейной формы». Журнал СИАМ по научным вычислениям . 9 (4): 692–697. DOI : 10.1137 / 0209053 .
- ^ Харрис, Джо (1992). Алгебраическая геометрия SpringerLink . Тексты для выпускников по математике. 133 . DOI : 10.1007 / 978-1-4757-2189-8 . ISBN 978-1-4419-3099-6.
- ^ а б Chiantini, L .; Оттавиани, G .; Ванневенховен, Н. (01.01.2014). "Алгоритм универсальной и специфической идентифицируемости низкого ранга сложных тензоров". Журнал SIAM по матричному анализу и приложениям . 35 (4): 1265–1287. arXiv : 1403.4157 . DOI : 10.1137 / 140961389 . ISSN 0895-4798 .
- ^ Боччи, Криштиану; Кьянтини, Лука; Оттавиани, Джорджио (2014-12-01). «Уточненные методы идентифицируемости тензоров». Annali di Matematica Pura ed Applicata . 193 (6): 1691–1702. arXiv : 1303,6915 . DOI : 10.1007 / s10231-013-0352-8 . ISSN 0373-3114 .
- ^ Chiantini, L .; Оттавиани, G .; Ванневенховен, Н. (01.01.2017). «Эффективные критерии специфической идентифицируемости тензоров и форм». Журнал SIAM по матричному анализу и приложениям . 38 (2): 656–681. arXiv : 1609.00123 . DOI : 10.1137 / 16m1090132 . ISSN 0895-4798 .
- ^ Chiantini, L .; Оттавиани, Г. (01.01.2012). «Об универсальной идентифицируемости 3-тензоров малого ранга». Журнал SIAM по матричному анализу и приложениям . 33 (3): 1018–1037. arXiv : 1103.2696 . DOI : 10.1137 / 110829180 . ISSN 0895-4798 .
- ^ а б Hauenstein, JD; Oeding, L .; Оттавиани, G .; Сомме, AJ (2016). «Гомотопические методы тензорной декомпозиции и идеальной идентифицируемости». J. Reine Angew. Математика . arXiv : 1501,00090 . DOI : 10,1515 / Крелль-2016-0067 .
- ^ Боччи, Криштиану; Кьянтини, Лука (2013). «Об идентифицируемости бинарных продуктов Segre» . Журнал алгебраической геометрии . 22 (1): 1–11. arXiv : 1105,3643 . DOI : 10,1090 / s1056-3911-2011-00592-4 . ISSN 1056-3911 .
- ^ Доманов, Игнат; Латхаувер, Ливен Де (январь 2014 г.). "Каноническая полиадическая декомпозиция тензоров третьего порядка: редукция к обобщенной декомпозиции собственных значений". Журнал SIAM по матричному анализу и приложениям . 35 (2): 636–660. arXiv : 1312.2848 . DOI : 10.1137 / 130916084 . ISSN 0895-4798 .
- ^ Доманов, Игнат; Де Латхаувер, Ливен (январь 2017 г.). «Каноническое полиадическое разложение тензоров третьего порядка: ослабленные условия единственности и алгебраический алгоритм». Линейная алгебра и ее приложения . 513 : 342–375. arXiv : 1501.07251 . DOI : 10.1016 / j.laa.2016.10.019 . ISSN 0024-3795 .
- ^ Faber, Nicolaas (Klaas) M .; Ферре, Жанна; Боке, Рикар (январь 2001 г.). «Метод аннигиляции обобщенного ранга с итеративным перевесом». Хемометрика и интеллектуальные лабораторные системы . 55 (1–2): 67–90. DOI : 10.1016 / s0169-7439 (00) 00117-9 . ISSN 0169-7439 .
- ^ Leurgans, SE ; Росс, RT; Абель, РБ (октябрь 1993 г.). «Разложение для трехкомпонентных массивов». Журнал SIAM по матричному анализу и приложениям . 14 (4): 1064–1083. DOI : 10.1137 / 0614071 . ISSN 0895-4798 .
- ^ Лорбер, Авраам. (Октябрь 1985 г.). «Особенности количественного определения химического состава из двумерного массива данных методом рангового анализа факторов аннигиляции». Аналитическая химия . 57 (12): 2395–2397. DOI : 10.1021 / ac00289a052 . ISSN 0003-2700 .
- ^ Санчес, Эухенио; Ковальски, Брюс Р. (январь 1990 г.). «Тензорное разрешение: прямое трехлинейное разложение». Журнал хемометрики . 4 (1): 29–45. DOI : 10.1002 / cem.1180040105 . ISSN 0886-9383 .
- ^ Сэндс, Ричард; Янг, Форрест В. (март 1980 г.). «Компонентные модели для трехсторонних данных: альтернативный алгоритм наименьших квадратов с функциями оптимального масштабирования». Психометрика . 45 (1): 39–67. DOI : 10.1007 / bf02293598 . ISSN 0033-3123 .
- ^ Бернарди, А .; Brachat, J .; Comon, P .; Моррен, Б. (май 2013 г.). «Общее тензорное разложение, матрицы моментов и приложения». Журнал символических вычислений . 52 : 51–71. arXiv : 1105.1229 . DOI : 10.1016 / j.jsc.2012.05.012 . ISSN 0747-7171 .
- ^ Бернарди, Алессандра; Daleo, Noah S .; Hauenstein, Jonathan D .; Моррен, Бернар (декабрь 2017 г.). «Тензорное разложение и продолжение гомотопии». Дифференциальная геометрия и ее приложения . 55 : 78–105. arXiv : 1512.04312 . DOI : 10.1016 / j.difgeo.2017.07.009 . ISSN 0926-2245 .
- ^ Анандкумар, Анимашри; Ге, Ронг; Сюй, Даниэль; Какаде, Шам М; Телгарский, Матус (2014). «Тензорные разложения для изучения моделей со скрытыми переменными». Журнал исследований в области машинного обучения . 15 (1): 2773–2832.
дальнейшее чтение
- Колда, Тамара Г .; Бадер, Бретт В. (2009). «Тензорные декомпозиции и приложения». SIAM Ред . 51 (3): 455–500. CiteSeerX 10.1.1.153.2059 . DOI : 10.1137 / 07070111X .
- Ландсберг, Джозеф М. (2012). Тензоры: геометрия и приложения . AMS.
Внешние ссылки
- Учебное пособие по PARAFAC
- Параллельный факторный анализ (PARAFAC)
- FactoMineR (бесплатное программное обеспечение для многомерного анализа данных, связанное с R )