Как создаётся тензор?

[Narn]

Pphantom в сообщении #1225350 писал(а):

Насколько я понял, в таком случае и "разложение" - это просто представление многомерного массива в виде списка массивов меньшей размерности (возникающее в основном из-за технических проблем с представлением многомерных массивов в конкретном языке).

Нет, это все-таки вещь более интересная. Например, можно обобщать singular-value decomposition (
https://en.wikipedia.org/wiki/Higher-order_singular_value_decomposition), и их там много разных вариантов, напр., Такера. Они и на практике используются, и теоретический интерес тоже представляют.

[Pphantom]

Narn в сообщении #1225354 писал(а):

Нет, это все-таки вещь более интересная.

Понятно, спасибо.

[CptPwnage]

Разложение Такера применяется для трехмерных массивов, для более высокомерных например Tensor Train, для которого тоже есть аналог SVD. Одно из применений - работа с астрономически большими сетками, например $2^{20} \times 2^{20} \times 2^{20}$ в 3D. Если использовать Tensor Train разложение (где значения функций на сетке предварительно конвертированы в $2 \times 2 \times \hdots \times 2$ массив - называется Quantized Tensor Train), то сложность и хранения и операций будет логарифмическая по отношению к размеру сетки.

Применения разнообразны, например вот статья https://arxiv.org/abs/1605.08422.

[qwarck]

Ок, спасибо, теперь понятно; верно, это то, о чём я говорил.
Только я одного всё ещё не понимаю; чтобы подробнее показать то, что я не понимаю, ещё раз приведу пример. Представьте, что имеется таблица значений вроде:

Время Длина Ширина Высота Масса
1 11.1 0.4 1.1 21
2 12.3 0.7 1.4 22
3 13.1 0.9 1.6 25
4 15.2 0.8 2.1 31
5 16.2 0.5 2.2 43
6 17 0.3 3 45

Представьте, что значений намного больше. Меня интересует вопрос, как можно представить эти данные в виде массива, как можно упростить этот массив, можно ли применить разложения? Нужно ли создавать 4-мерный массив для каждого из параметров и потом делать разложение? Как на практике люди, работающие с большими массивами, обрабатывают эти массивы?

[mihaild]

qwarck, а что вы потом с этим хотите делать? Например, можно просто сложить структуры из 5 чисел в массив.
(или, если моменты времени у вас не случайно все натуральные и идущие подряд - считать время индексом, и складывать структуры из четырех чисел)

[Geen]

CptPwnage в сообщении #1225384 писал(а):

Если использовать Tensor Train разложение (где значения функций на сетке предварительно конвертированы в $2 \times 2 \times \hdots \times 2$ массив - называется Quantized Tensor Train), то сложность и хранения и операций будет логарифмическая по отношению к размеру сетки.

? Можно чуть подробнее?, просто идею без терминов?

[CptPwnage]

Если коротко, то идея в том чтобы некоторым образом обобщать разделение переменных на многомерный случай.
Например для матриц, если есть матрица $A$ ранга $1$, то ее можно записать в виде

$$ A = u v^{T}, $$

или

$$A = u \otimes v,$$

что соответсвует ситуации когда индексы $i$ и $j$ в матрице $A$ разделяются идеально. В общем случае для матрицы ранга $r$ имеем

$$A = \sum_{i=1}^{r} u_i \otimes v_i.$$

Понятно, что если ранг $r$ мал, то хранение вместо матрицы $A$ векторов $u_i, v_i$ сильно снижает объем данных которые мы храним - $O(n)$ вместо $O(n^2)$.
Если попробовать обобщать это на многомерные массивы (скажем трехмерные) в виде

$$\mathcal{X}^{ijk} = \sum_{i=1}^{r} u^{(1)}_i \otimes u^{(2)}_i \otimes u^{(3)}_i,$$

- это так называемое каноническое разложение тензора (CP - canonical polyadic), и определить "ранг" как минимальное $r$, такое что такое разложение найдется, то оказывается что это очень плохое во всех смыслах определение, например задача о поиске CP ранга произвольного тензора является NP полной. Ну и там всякие вещи что при произвольно малом возмущении ранг может скакнуть и стать вообще любым.
Поэтому люди стали думать какие еще разложения можно придумать. Есть разложение Такера, есть TT (Tensor-Train) разложение. Первое для тензоров с больше чем $3$ модами мало используется, поэтому напишу про второе. Мы представляем $d$ - мерный тензор $X \in \mathbb{R}^{n_1 \times n_2 \hdots n_d}$ в виде списка из $d$ $3$-х мерных тензоров $G^{(i)}$, таких что $G^{(i)} \in \mathbb{R}^{r_{i-1} \times n_i \times r_i}$, где $r_i$ - числа которые называют рангами TT-тензора и $r_0 = 1, r_{d} = 1$. "Ядра" $G$ удовлетворяют соотношению

$$X^{i_1 i_2 \hdots i_d} = G^{(1)}[:, i_1, :] G^{(2)}[:, i_2, :] \hdots G^{(d)}[:, i_d, :].$$

Поясню что имеется ввиду - $G^{(i)}$ это $3$-х мерный массив. При подстановке туда в качестве среднего индекса $i_k$ мы получаем матрицу размера $r_{i-1} \times r_i$. Произведение этих матриц дает нам число - соответствующий элемент тензора $X$ (число так как размеры крайних ядер есть $1 \times \hdots$ и $\hdots \times 1$). Посчитаем число параметров -

$$\sum_i r_i n_i r_{i-1} = O(d \max n_i r^2),$$

что существенно меньше чем изначального размер $X$ - $O(n^d).$
Для массивов $X \in \mathbb{R}^{N}$ при $N = 2^d$, можно добиться еще более сильного сжатия если сначала его превратить в тензор $\hat{X} \in \mathbb{R}^{2 \times 2 \times ... \times 2},$ тогда сложность будет линейна по $d$ - логарифмическая по $N$. Идея тут в том что мы вместо индекса используем его бинарное разложение - $i \to i_1 i_2 \hdots i_d$, и что в таких переменных у многих функций тоже разделяются переменные. Например для массива значений экспоненты на сетке

$$e^{i h } = e^{ \sum_j 2^{j} i_j h} = e^{i_0 h} e^{2i_1h} \hdots e^{2^{d-1} i_d h},$$

переменные разделяются полностью. То есть экспоненту мы можем задать фактически на любой сетке вообще практически, и для хранения понадобится всего $\approx \log N$ чисел.

[Geen]

CptPwnage
Спасибо большое.
Но, если я не путаю, при $d=2$ TT полностью эквивалентен CP, а значит имеем всё те же проблемы:

CptPwnage в сообщении #1225658 писал(а):

задача о поиске CP ранга произвольного тензора является NP полной. Ну и там всякие вещи что при произвольно малом возмущении ранг может скакнуть и стать вообще любым.

?

[CptPwnage]

Совершенно верно, при $d=2$ разложения совпадают, но это матричный случай про которой все хорошо известно. CP разложение матрицы дается SVD разложением. Проблемы у CP начинаются при $d>2$.