Тензорный способ нахождения грамоник, прогноз

[Schrodinger's cat]

Всем доброго здоровья и хорошего настроения.

ilghiz в сообщении #1565444 писал(а):

Есть еще один метод, посдвигать все на две размерности, получить тензор, и его тензорным разложением покромсать. Метод клевый, достаточно устойчивый, можно под тысячу экспонент вытаскивать, но вычислительная сложность получается очень не ахти. Я когда-то много в этой области наследил, могу и ссылок накидать, и порассказывать детали.

ilghiz пожалуйста расскажите с чего начать.

По всей видимости мне нужно изучить тензор трейн?

[ilghiz]

Schrodinger's cat в сообщении #1566655 писал(а):

Всем доброго здоровья и хорошего настроения.

ilghiz в сообщении #1565444 писал(а):

Есть еще один метод, посдвигать все на две размерности, получить тензор, и его тензорным разложением покромсать. Метод клевый, достаточно устойчивый, можно под тысячу экспонент вытаскивать, но вычислительная сложность получается очень не ахти. Я когда-то много в этой области наследил, могу и ссылок накидать, и порассказывать детали.

ilghiz пожалуйста расскажите с чего начать.

Ключевая идея тензорного или multillinear, three-way, multi-way decomposition в том, что представление в трех и более мерном пространстве вида

$$a_{ijk} = \sum_{r=1}^R \alpha_r b_{ir}^{(1)} b_{jr}^{(2)} b_{kr}^{(3)}$$

не требует ортогональности матриц $B^{(1)} = \{ b_{ir}^{(1)} \}$, $B^{(2)} = \{ b_{ir}^{(2)} \}$, $B^{(3)} = \{ b_{ir}^{(3)} \}$, как в сингулярном разложении, поэтому, такое разложение для такого сдвинутого тензора сразу дает правильное решение. Если решение не отрицательно по физике, оно и получается в виде матриц с неотрицательными числами. Первым это осознал в 1977 году Крускал doi: 10.1016/0024-3795(77)90069-6

Да, вычислительная сложность тензорного разложения обычно очень большая, но, ведь решает, поэтому им и пользуются.

Еще можно увеличивать размерности - например, если у вас сигнал в виде комплексной экспоненты на 1024 отсчетах, вы можете его представить в виде, например, пятимерного тензора $4 \times 4 \times 4 \times 4 \times 4$ (или даже 10-ти мерного) и напустить на него такую тензорную аппроксимацию. Тогда ничего сдвигать не надо и тензор будет довольно маленький. Мы когда-то как раз это с соавторами и придумали 10.1038/nmeth900

Как это решать, надо всегда смотреть по обстоятельствам. Готового решателя на все случаи жизни нет.

Обычно более-менее хорошо сходится ALS, не я его придумал, кажется Харшман в 1970-м году, только он написал очень не понятно, поэтому, все Кирса или Бро цитируют, да и у меня тоже понятно написано в 10.1002/nla.297 . Сорсы топового решателя есть в приложении одного из наших патентов, с номером десять семь семь три ноль девяноста два, выданном пару лет назад в американском патентном ведомстве. Для многомерных разреженных данных я не знаю альтернатив, которые решают эту задачу устойчивее и быстрее.

Schrodinger's cat в сообщении #1566655 писал(а):

По всей видимости мне нужно изучить тензор трейн?

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

[Schrodinger's cat]

ilghiz в сообщении #1566664 писал(а):

$$a_{ijk} = \sum_{r=1}^R \alpha_r b_{ir}^{(1)} b_{jr}^{(2)} b_{kr}^{(3)}$$

Насколько я понял, это каноническое разложение.
В сами разложения пока ударяться нет желания, оставлю эту задачу на потом.
Нашел готовые решатели для канонического разложения, разложения Такера и еще несколько вариаций.
https://tensorly.org/stable/user_guide/tensor_decomposition.html

ilghiz в сообщении #1565538 писал(а):

С тензорным разложением, просто строите 3-х мерный тензор, сдвигая по второй и третьей координате ваши данные. Тогда если данных у вас было $N$ и вы планируете найти $R$ компонент, то надо строить тензо размерности $(N-2R) \times R \times R$, и напускаете на него любое доступное тензорное разложение.

Уточните пожалуйста алгоритм получения $a_{ijk}$.
Если $Y_i$ исходный ряд, то $a_{ijk} = Y_{i+j+k}$ так?

Цитата:

кажется Харшман в 1970-м году, только он написал очень не понятно, поэтому, все Кирса или Бро цитируют

Уточните пожалуйста Харшмана, Кирса и Бро где читать. Поиски не дели результатов.

В ссылках на Вашу литературу везде платный доступ, к сожалению покупать не готов.

[ilghiz]

Schrodinger's cat в сообщении #1566908 писал(а):

Если $Y_i$ исходный ряд, то $a_{ijk} = Y_{i+j+k}$ так?

нет, не так. Пусть у вас индекс $i=0,...,511$ имеет двоичное представление $i_1,...,i_9$, вот тогда $a_{i_1,...,i_9} = Y_i$. Для не полных данных как раз sparse версия - это если у вас исходный массив, скажем только до 400, то все остальное до 511 вы как не заданные числа подаете с весом на аппроксимации равным нулю.

Schrodinger's cat в сообщении #1566908 писал(а):

В ссылках на Вашу литературу везде платный доступ, к сожалению покупать не готов.

а вы еще sci-hub не научились пользоваться? Гуглите на сци-хаб, ибо у них название сайта часто меняется. В нем все по doi можно выкачивать. Если вдруг конечно не осилите, то пришлю сами статьи.

[Schrodinger's cat]

ilghiz в сообщении #1566912 писал(а):

а вы еще sci-hub не научились пользоваться?

С Вашей подачи научился, спасибо большое.

ilghiz в сообщении #1566912 писал(а):

Пусть у вас индекс $i=0,...,511$ имеет двоичное представление $i_1,...,i_9$, вот тогда $a_{i_1,...,i_9} = Y_i$

Что такое $i_1,...,i_9$?
Допустим $i=0$ - первое число ряда, тогда $0_1,...,0_9$ как это понимать? 1-9 это индекс чего?
Поясните пожалуйста.

[svv]

$\begin{array}{l}a_{000000000}=Y_0 \\a_{000000001}=Y_1 \\a_{000000010}=Y_2 \\a_{000000011}=Y_3 \\a_{000000100}=Y_4 \\a_{000000101}=Y_5\\a_{000000110}=Y_6 \\a_{000000111}=Y_7 \\...\\a_{100101011}=Y_{299} \\a_{100101100}=Y_{300} \\a_{100101101}=Y_{301} \\...\\a_{111111110}=Y_{510} \\a_{111111111}=Y_{511}\end{array}$

[Schrodinger's cat]

Т.е. декады двоичного числа нужно рассматривать как отдельные оси тензора, в данном случае у тензора будет 9 осей каждая длиной 2?
Получается размерность тензора зависит от длины исходного ряда.
Как тогда это соотносится с формулой:

Schrodinger's cat в сообщении #1566908 писал(а):

$(N-2R) \times R \times R$,

Тут всего 3 оси и не зависит от длины исходного ряда.

Простите но я до сих пор не могу понять алгоритм построения исходного тензора. Поясните пожалуйста.

[svv]

У меня декада прочно ассоциируется с двоично-десятичным кодом. А тут просто — двоичные разряды двоичного же представления индекса $i$.
Но вообще я в этой теме случайный прохожий.

[ilghiz]

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

Иногда из самой физики задачи есть еще одна-вторая размерность, как в многомерном ЯМРе. Там оно само нативно получается. В моих современных ЯМР и МРТшных задачах меньше пяти нативных размерностей из их физической постановки у меня редко бывает :)

Какую комбинацию методов выбрать - тут нужно просто пробовать, но проще, понятное дело, не раздувать исходные данные. Если так не работает, то только тогда и добавлять такие "искусственные" размерности как в методе Прони. На своих спектральных задачах (ЯМР, флюоресценция, всякие урматфизы типа горения на сверхзвуке) я уже и на кошках и не на кошках примерно 25 лет как тренировался и могу многое посоветовать. На ваших задачах - хз, надо чуть лучше представлять что у вас есть сам сигнал, а что - шум, тогда конечно же я смогу вам что-то посоветовать. А так - этот инструмент просто дает огромный выбор возможностей, и, эти возможности позволяют решать очень не тривиальные задачи.

[Schrodinger's cat]

У меня пока нет конкретных задач. Конкретная задача научиться методу.
Хотел бы как и в случае Прони изучить все возможные пути или хотя бы их обзор. Научиться базовым методам.
В качестве данных я обычно брал чисто искусственные суммы гармоник и шум, техногенез энергопотребления, биржевые данные например акции какие нибудь, звуковые дорожки...
Нужно начать с самого простого. Давайте например разложим сумму гармоник с шумом.
У этого метода есть какой то базовый подход?

ПС: Напомнило: Купи 2 чебурека и собери кошку В смысле тренировки на "кошках" получается что мы их раскладываем

svv в сообщении #1567050 писал(а):

Но вообще я в этой теме случайный прохожий.

Не проходите мимо, загляните к нам на чай. Скоро испеку тензор торт.

[ilghiz]

Schrodinger's cat в сообщении #1567078 писал(а):

В качестве данных я обычно брал чисто искусственные суммы гармоник и шум

Так и сейчас возьмите и сделайте! Перебрать делать ли многомерность в лоб, или расширять тензор - вроде ума большого не надо - игра для детей школьного возраста. У меня дочь в 10-ом классе недавно так экспериментировала для каких-то своих биологических данных.

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

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

То есть ИМХО, брать, генерировать данные, втыкать в готовые решатели и смотреть, что получается - будет бесценный опыт.

Чисто на моих многолетних наблюдениях - метод на порядки более стабильный, чем Прони, или фиттинг в лоб комплексных экспонент или еще каких нелинейных песцов наименьшими квадратами, но, существенно более вычислительно дорогой по сравнению с Фурье или SVD.

Причем метод стабильный даже в руках очень и очень начинающих.

А если у вас данные по физике разлагаются таким разложением, то, фактически единственный из того, что без бубнов сразу дает правильное решение.

[Schrodinger's cat]

Ткните пожалуйста носом. Я просмотрел все ссылки, но где написано как формируется начальный тензор не увидел.
Так же до сих пор не видел тех исходников про которые вы говорите.
Хотя убил на это прорву времени.

ПС: Видимо когда все алгоритмы реализованы ума большого и не надо...
Я бы не задавал "глупых" вопросов если бы где то было понятно написано. Сидел бы и делал.
Нельзя ли как то поконкретнее, читай это делай так. Читаю загадки и долго думаю, потом понимаю что вариантов нет пишу сюда получаю очередную порцию загадок...
Не прошу ничего делать за меня, всего лишь прошу четких указаний чтобы можно было разобраться.

[ilghiz]

Schrodinger's cat в сообщении #1567084 писал(а):

Ткните пожалуйста носом. Я просмотрел все ссылки, но где написано как формируется начальный тензор не увидел.

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

Schrodinger's cat в сообщении #1567084 писал(а):

Так же до сих пор не видел тех исходников про которые вы говорите.
Хотя убил на это прорву времени.

Я кажется понял почему - раньше в гугл-патентах их можно было вытащить, а теперь почему-то гугл супплементы не видит. Надо идти в patentcenter.uspto.gov и вписывать в поиск номер патента, не application!!! а именно patent, что я выше указал (не пишите прямую ссылку тут, пожалуйста).

Там в документах есть полный список всего обсуждения и надо вытащить Supplemental Information и во втором супплементе есть листинг, а в тексте - само описание почему все так. Если не найдете, в личку пришлю :)

[Schrodinger's cat]

ilghiz, большое спасибо. Дело продолжило двигаться, вроде нашел.
Там 2 функции NW_SPF1 и NWSPF. Вы про это говорите?

ilghiz в сообщении #1567093 писал(а):

Тогда проще всего последовать тому, как уважаемый svv выше написал и превратить 512 элементов этого вектора в 9-ти мерный массив.

Эта часть понятна.

ilghiz в сообщении #1567093 писал(а):

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

А вот эта часть нет. Для иного результата нужно основание системы счисления изменить? Троичная например. Тогда длина осей тензора увеличится а количество размерностей уменьшится. Верно мыслю?

ilghiz в сообщении #1567093 писал(а):

(не пишите прямую ссылку тут, пожалуйста)

Да, я понял по тому как вы номер словами написали.
Все остальное, содержимое, формулы тут можно обсуждать?

ПС: Ушел читать 60 листов англо математической жести.

[ilghiz]

Не отвечал, так по моей основной работе совсем завал был, простите за задержку с ответом!

Schrodinger's cat в сообщении #1567113 писал(а):

ilghiz, большое спасибо. Дело продолжило двигаться, вроде нашел.
Там 2 функции NW_SPF1 и NWSPF. Вы про это говорите?

да, они самые!

Schrodinger's cat в сообщении #1567113 писал(а):

Для иного результата нужно основание системы счисления изменить? Троичная например. Тогда длина осей тензора увеличится а количество размерностей уменьшится. Верно мыслю?

Правильно. Вот, например, для 512 отсчетов вместо 9-ти мерного массива $2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$ я обычно делаю просто трехмерный $8 \times 8 \times 8$

Можно и $9 \times 9 \times 9$ сделать, а недостающие точки пометить как отсутствующие и скормить из в sparse структуру у NWSPF.

Schrodinger's cat в сообщении #1567113 писал(а):

Все остальное, содержимое, формулы тут можно обсуждать?

конечно давайте обсуждать - я радостью популяризую наши результаты!

Schrodinger's cat в сообщении #1567113 писал(а):

ПС: Ушел читать 60 листов англо математической жести.

да, там конечно много ЯМРной специфики, хотя не спорю, большая часть текста - как раз математика и именно обработка сигналов.