Comments 41
Хорошая статья. Заплюсовал. Однако, первым её предложением должно быть следующий дисклеймер: «Если вы не выучили алгебру матриц и алгебру тензоров, а так же не набили руку на задачах закрепляющих операции этих алгебр, читать далее вам не имеет смысла».
Немножко не по теме, но есть такой вопрос существует 6 мерный тензор , свертка которого с трехмерным дает другой трехмерный . Аналог метода Гаусса для такого случая существует ??
Интересный подход. Весьма забавно наблюдать, как техники из сурового теорпола и квантовых моделей переползают в междисциплинарную область.
Специфический вопрос по теме. Из пары статей по тензорным поездам понял, что они потенциально могут быть использованы для низкорангового представления полиномиальных приближений для функций. Могут ли подобные тензорные представления быть сформулированы для более сложных функций, например вложенных [вида h(g(f(x)))] или свёрток [вида интеграл по y от `f(x, y) g(y, x)` ]? И если такие представления существуют, можно ли показать/доказать, что они будут относительно невысокого ранга?
Если использовать тот самый метод, что описывается в статье -- с прямым построение ядер, то сделать композицию функций g(h(f(x))) совсем просто, так как не меняется размер образа функций, а все изменений затронут только последнюю производящую функцию (на рисунке -- f^(l)). А вообще, для произвольного ТТ-тензора, даже простая функция от него, например, экспонента, может привести сильному росту рангов. Так что в общем случае, теорем, к сожалению, нет.
Насчёт интеграла -- проще всего вначале сжать в ТТ подынтегральную функцию, а потом уже проинтегрировать в ТТ-формате: он это позволяет, и это одно из преимуществ ТТ-формата, что возможно довольно много интересных операций проводить сразу с ним. Понятно, что формально будет не интеграл, а сумма, и для хорошей точности нужно будет взять довольно много точек по оси y. В этом случае ТТ-ранг интеграла по построению будет не больше TT-ранга исходной функции. Если подынтегральная функция представляет собой произведение двух других, то можно их сжать в ТТ по сдельности, а затем перемножить в ТТ-формате. Ранги в этом случае также перемножается.
Спасибо! скажите, а вы можете порекоммендовать готовые пакеты программ для работы с поездами тензоров?
Есть самый первый пакет по ТТ -- ttpy , он ещё использует фортран для ускорения.
Есть более современный пакет, который основан на torch -- tntorch (автор тот самый Баллестер, который упоминается в статье)
Есть пакеты уже нашей группы -- teneva , написанный на голом питоне для совместимости с чем угодно, и его расширения на jax -- teneva_jax.
Ну а пакет, который реализует алгоритм в статье -- вот этот.
Термин "трехмерный тензор" не очень удачен, поскольку провоцирует путаницу. Все же количество измерений тензора - это "арность" (валентность). Соответственно тензор из 3-х измерений - тернарный.
А вот каждое измерение тензора имеет собственную "мерность" (размер). Поэтому унарный тензор (вектор) может быть трехмерным. Бинарный тензор (матрица или массив) имеет две размерности и т.д.
Да, спасибо, согласен, писал статью как можно проще для понимания, поэтому старался использовать самые простые термины. Поправлю ;)
Вообще-то в тензорном исчислении существует общепринятая терминология (см.Википедию). У тензора есть ранг и размерность (пространства в котором тензор существует). В частности, вектор - это тензор ранга 1, при этом может быть любой конечной размерности. Соответственно, то, что все называют матрицей и задается 2- мерной таблицей (причем квадратной NxN), можно назвать тезором ранга 2, причем только в том случае, если компоненты определенным образом зависят от изменения системы координат. Термины типа "размерность тензора" очень сбивают с толку, особенно если Вы имеете в виду именно ранг или около того. Любовь разработчиков ПО к громким названиям естественна, поскольку это на деньги влияет, но человеку, у которого понятие тензора в крови, читать очень тяжело.
Любовь к громким названиями тут ни при чём, просто тензор для программиста — это просто массив, а у массивов размерность и ранг — синонимы.
Это связано с тем, что массивы традиционно рассматриваются не как физическая величина в некотором пространстве, а как само пространство.
А у матрицы ранг - это число ненулевых сингулярных значений
Вот именно, ранг матрицы и ранг тензора - абсолютно разные вещи. Как и ранг капитана ВМФ :))
Интересно, это действительно так? Ссылку пришлете?
На что, простите? Или это промах с комментом?
Почему ранг матрицы рамен числу ненулевых сингулярных значений? По-моему, это не очевидно, где-то должно быть доказательство.
Не думал, что а) потребуется прикладывать ссылку и б) что при желании ее трудно будет найти. Для начала можно и в вики заглянуть: https://en.wikipedia.org/wiki/Singular_value_decomposition
А вообще немного странный запрос. Может это и не очевидно, но это широко известный (в узких кругах, хаха) факт (по крайней мере если этого нет в курсе линейной алгебры, то это г***о, а не курс).
UPD: я в том смысле, что, кажется, Вы владеете аппаратом, поэтому странно было услышать такой вопрос.
Вопрос был чисто познавательный. Вы будете смеяться, но на мех-мате МГУ 40 лет назад в курсе линейной алгебры не было сингулярного разложения (как и многих других полезных разложений). На это справедливо обратил внимание г-н Оселедец, последователем которого является автор обсуждаемой статьи. Когда я году этак в 1987-м начал заниматься численными расчетами, я с удивлением обнаружил, что существует много эффективных методов обработки матриц, позволяющих делать такие расчеты в принципе (на компьютере PC AT). А студентам про это не рассказывали. Так что тема для меня ностальгическая.
Но сути дела это не меняет - ранг матрицы и ранг тензора - суть разные величины
На самом деле, очевидно:
ранг диагональной матрицы равен количеству ненулевых диагональных значений
умножение на унитарную матрицу (как и на любую обратимую) не меняет ранг
при сингулярном разложении мы умножаем диагональную матрицу на унитарную слева и справа, с-но ранг итоговой матрицы равен рангу исходной диагональной, а ее ранг - число ненулевых сингулярных значений
Зачем называть тензором то, что тензором не является? Называйте это 3-хмерной или N-мерной матрицей или, как Вы правильно отметили, массивом, и вас все поймут. А что означает Ваша фраза, что массив это и есть пространство, вообще не пойму. Пространство - это множество точек, причем несчетное (надеюсь, термин "несчетное множество" программистам понятен понятен), в котором есть система координат, или векторный базис. А массив - конечный набор чисел, кстати говоря, в программировании всегда одномерный (!).
Пространство не обязано быть несчётным, как и непрерывным. Z53 — вполне себе трёхмерное линейное пространство над полем Z5. Которое соответствует массиву 5х5х5.
И с одномерностью массивов вы как-то погорячились. В Фортране они могут быть многомерными, в Бейсике — тоже, как и в Паскале, Си, С++, C# и Rust.
А что означает Ваша фраза, что массив это и есть пространство, вообще не пойму.
Ну вот вам альтернативная формулировка того же самого наблюдения: размерностью массива называют размерность вектора, образованного его индексами.
Зачем называть тензором то, что тензором не является?
А вот тут не понимаю уже я. Кто именно тут называет тензором то, что тензором не является?
Мы углубляемся в дискуссию в стиле рассказов Шукшина. ОК. Количество элементов линейного пространства - несчетно, как несчетно множество действительных чисел. Далее буду ссылаться Википедию и прочие познавательные сайты по всем вопросам.
Пространство: https://ru.wikipedia.org/wiki/Векторное_пространство
Как располагается и адресуется массив в памяти компьютера: https://foxford.ru/wiki/informatika/dvumernye-massivy-v-s
Определение тензора: https://ru.wikipedia.org/wiki/Тензор
Альтернативных формулировок можно придумать множество, но если автор хочет, чтобы его поняли и внятно подискутировали, надо пользоваться общепринятой терминологией.
Количество элементов линейного пространства — несчетно, как несчетно множество действительных чисел.
Только если это линейное пространство над несчётным полем.
Линейное пространство Z53 конечно.
Линейное пространство Q2 счётно.
Кстати, по вашим ссылкам нет ничего что бы подтверждало ваши слова.
Автор статьи, которую мы обсуждаем (надеюсь, мы этим занимаемся?) приводит пример как многомерный "тензор" можно представить в виде двумерной матрицы, просто часть индексов обозвав"строчные", а часть - "столбцовые". Можно пойти дальше и все индексы обозвать как "столбцовые" и получить вектор-столбец, элементы которого (возможно) расположенны в памяти компьютера даже в том же поряке. Проблема в том, что с этим вектором, как и с большой 2-мерной матрицей ничего путного нельзя сделать, поэтому приходится искать другие пути. Вот народ и хочет разобраться что к чему.
Дело в том, что тензоры бывают разные: https://en.wikipedia.org/wiki/Tensor_(disambiguation)
В целом, это нормальная ситуация, когда один и тот же термин или одно и то же обозначение в разных разделах и контекстах используется по разному. Даже обозначение π может означать не то, к чему мы привыкли со школы. Так что я могу ещё согласиться, что не ввёл все необходимые определения в самом начале, стараясь делать статью попроще. Но термин "тензор" действительно многозначный, как и говорит википедия, на которую я-таки зашёл ;) https://en.wikipedia.org/wiki/Tensor_(machine_learning)
"Тензор" в смысле "многомерный массив" используется не для громкого названия, а для удобства.
В физике (и механике в том числе) тензор это нечто, компоненты которого преобразуются заданным образом при повороте / отражении / инверсии пространства. А не просто многомерный массив.
Хорошо бы в этой теме как-то договориться о терминах. Иначе возникает путаница. Есть понятие ранга тензора (для скаляра - 0, для вектора - 1, для мартицы - 2), а есть ранг матрицы - максимальный размер ненулевого минора. Есть размерность матрицы (например NxM) и есть размерность массива ( 1 - для вектора, 2 для матрицы). Дело не в том, что какие-то термины простые, а какие-то сложные. Должно быть понятно читателю, терминологию можно зафиксировать в начале статьи или сослаться на источник, например что-то по линейной алгебре.
>Поэтому унарный тензор (вектор)
На самом деле все круче - унарный тензор может вообще не быть вектором (из базового пр-ва, то есть) :).
>где количество матриц в произведении равно числу размерности тензора:
Размерность тензора - это размерность модуля, над которым строится соответствующая тензорная алгебра. А то, о чем тут написано - это ранг (или порядок, или степень - когда не хочется путать с рангом матрицы и ядра). Если испольдуете нестандартную терминологию - то это следует оговаривать в самом начале.
Формально, в худшем случае (r~n) у вас алгоритм O(n^3). Чем он тогда лучше алгоритма Копперсмита — Винограда с O(n^2.4) ?
Алгоритм Копперсмита — Винограда -- это про умножение матриц. Но наш метод может решать задачи, связанные с многомерным суммированием, например. И тут оценка сложности зависит от конкретной задачи. Например, в задаче вычисления перманента матрицы есть стандартный и довольно-таки искусственный механизм суммирования, который даёт довольно хорошую сложность именно для заданной суммы, и к этой сложности мы подошли используя наш довольно общий метод.
Какие можете посоветовать материалы, чтобы получше разобраться с тензорной алгеброй именно для таких задач (т.е. не для сложной физики, а в рамках вычислительной линейной алгебры)? считаем, что хорошая база по линейной алгебре есть
Здесь нет никакой тензорной алгебры, как нет и собственно тензоров. Это все - просто матрицы, поэтому кроме линейной алгебры ничего не нужно.
Сходу сложно вспомнить что-то на русском языке специфичное. Всё-таки, это относительно новая область. Из английских обзоров могу посоветовать не так довольно вышедший двухтомник https://arxiv.org/abs/1609.00893 https://arxiv.org/abs/1708.09165
Так в целом подробно всё описывается, хотя, конечно, предполагается подготовка по общей линейной алгебре от читателя.
Тема, конечно, интересная и полезная. Я решил у нее углубиться, посмотрел выступление Оселедеца на ДатаФесте, и сразу возник вопрос по азам Вашей публикации. В первом абзаце главы Тензорный Поезд Вы называете множители разложения трех-мерными тензорами (не будем спорить о терминах, только о размерностях). Но ведь это 2-мерные матрицы, каждая из которых аналитически зависит от своего индекса. Или я что-то не понял?
Да, мы можем рассматривать ядра ТТ-разложения как параметризованные матрицы одинакового размера. Но по сути это и есть 3D массив (3-way tensor) (2 размерности от матрицы и ещё одна размерность -- это номер матрицы в списке). Технически, удобно такую конструкцию хранить в одном массиве. Причём, в процессе разных манипуляций с ТТ-тензором строят т.н. "развёртки" -- матрицы, состоящие из всех элементов ядра, расположенных в определённом порядке. Поэтому и говорят о 3D тензорах в этом случае.
Прибытие тензорного поезда. Как достижения мультилинейной алгебры помогают преодолеть проклятие размерности