Найти паттерны во временных рядах

[jabra]

Призываю на мозговой штурм :)

Есть поток данных, например аудио или видео сигнал.
Нужно найти повторяющиеся паттерны, но заранее не известно какими они будут.
Предположим для начала небольшие, например 20x20 пикселей или 0.2 секунды.

Понятно что не точные, с шумами и погрешностями. На выходе нужны паттерны и относительные частоты их появления.

Как подойти к такой задаче, есть какие-то мысли?
Как мне кажется, нейросети не лучший вариант.

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

[Pphantom]

Гм... а словосочетание "анализ временных рядов" Вам что-нибудь говорит?

[jabra]

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

Гм... а словосочетание "анализ временных рядов" Вам что-нибудь говорит?

Оно то знакомо, но с какой стороны подступиться?

Расшифрую задачу - есть картинка например с диаграммой Вороного, там паттернами будут всевозможные линии, области однородной окраски, границы 2 областей, точки пересечения линий. Это так сказать типичные элементы.
Если на входе мячик скачущий на фоне градиентов синего, то соответственно нужно выявить быстро летящий мячик, просто мячик, синяя область, мячик на фоне синего... количество и сложность найденных паттернов пусть зависит от объёма памяти и времени работы распознавателя.

Вопросов возникает несколько:
1. В каком виде хранить эти выявленные паттерны, чтобы их можно было использовать для распознавания других данных.
2. Как собственно их находить наиболее эффективным способом.

Потом задачу придётся ещё усложнить - искать паттерны на паттернах и так далее, строить такую иерархическую структуру входных данных.

[Pphantom]

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

[Pavia]

jabra
Как вам верно заметили это разные задачи и решаются они по разному.

jabra в сообщении #1259524 писал(а):

1. В каком виде хранить эти выявленные паттерны, чтобы их можно было использовать для распознавания других данных.

А на каком уровне обработке? А какой алгоритм распознавания?

jabra в сообщении #1259524 писал(а):

2. Как собственно их находить наиболее эффективным способом.

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

А выделение через методы сегментацию: методы, фагацита, супер-пиксели, разрез-графа, градиенты изображения, FAST(corne detector) и прочие методы.

[jabra]

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

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

Я задачу распознавания образов пытаюсь решить с помощью нейронной сети, но не классической а такой где нейроны или их группы реализуют функцию распознавания time series. Такая модель более приближена с тому что происходит в живых нейронах.

В общем, общая задача которую я расписал сводится к эффективному распознаванию рядов. Не одного одномерного ряда, а скажем N одномерных потоков, где N от 2 до сотен-тысяч.

Попробую формализовать:
Чёрный ящик, N входов, K выходов. Нужно реализовать его так чтобы повторяемые последовательности сигналов на входах вызывали сингал на одном или нескольких выходах. То есть определённая последовательность на подмножестве входов включает выход. Конечно, последовательность нечёткая, допустимы шумы и отклонения как по абсолютным значениям так и "растянутость" во времени. Ящик должен самообучаться - если мы начнём подавать другие последовательности, через некоторое время он должен стабилизироваться и научиться их узнавать и выдавать предсказуемый вывод.

-- 28.10.2017, 13:00 --

Pavia в сообщении #1259584 писал(а):

А на каком уровне обработке? А какой алгоритм распознавания?

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

Pavia в сообщении #1259584 писал(а):

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

От больших объёмов никуда не деться. Но хотелось бы по соптимизировать и распараллелить, чтобы на полную использовать возмонжости GPU/NPU.
Пока я работаю над универсальным ядром - понимание смысла, работа с естественными языками и всё такое, насколько получится. Если возникнет необходимость, потом можно будет заюзать специфичные алгоритмы для изображений/видео, хотя бы opencv.

[Pphantom]

jabra в сообщении #1259884 писал(а):

Я задачу распознавания образов пытаюсь решить с помощью нейронной сети, но не классической а такой где нейроны или их группы реализуют функцию распознавания time series.

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

[Pavia]

jabra в сообщении #1259884 писал(а):

Такая модель более приближена с тому что происходит в живых нейронах.

Насколько знаю нет. У вас есть доказательства?

jabra в сообщении #1259884 писал(а):

Но хотелось бы по соптимизировать и распараллелить, чтобы на полную использовать возмонжости GPU/NPU.

Сначала напишите алгоритм. Тогда можно будет сказать как его оптимизировать.

jabra в сообщении #1259884 писал(а):

Попробую формализовать:

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

jabra в сообщении #1259524 писал(а):

Вопросов возникает несколько:
...
2. Как собственно их находить наиболее эффективным способом.

jabra в сообщении #1259884 писал(а):

В общем, общая задача которую я расписал сводится к эффективному распознаванию рядов.

Вот тут Вы противоречите сами себе. Я так понимаю вы и так всё знаете. Тогда, чего Вы хотите от данной дискуссии?

jabra в сообщении #1259884 писал(а):

Пока я работаю над универсальным ядром - понимание смысла, работа с естественными языками и всё такое, насколько получится.

А каким же образом вы связали поиск повторов и понимания смыслов?

[jabra]

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

jabra в сообщении #1259884 писал(а):

Я задачу распознавания образов пытаюсь решить с помощью нейронной сети, но не классической а такой где нейроны или их группы реализуют функцию распознавания time series.

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

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

Пока я бы ограничился отдельными элементами, этими чёрными ящиками - распознавателями последовательностей.

-- 28.10.2017, 23:45 --

Pavia в сообщении #1259913 писал(а):

jabra в сообщении #1259884 писал(а):

Такая модель более приближена с тому что происходит в живых нейронах.

Насколько знаю нет. У вас есть доказательства?

Ну как же. Живые нейроны только и умеют распознавать и предсказывать последовательности сигналов, больше они ничего не умеют. Хотя бы эта статья - http://elementy.ru/novosti_nauki/430504/Neyrony_sorevnuyutsya_za_pravo_uchastiya_v_formirovanii_refleksov. Улитке прикасаются к сифону, затем бьют по хвосту что вызывает сокращение мышцы, и так несколько раз (обучение). Затем уже просто прикосновение к сифону вызывает сокращение мышцы. Математически - улитка научилась предсказывать последовательность входных импульсов. Это элементарный пример, последовательность всего из 2 сигналов, но и реализована всего одним нейроном (не считая двух сенсорных и мышечного). Нетрудно представить, что будет если собрать каскад и нескольких таких нейронов - они научатся распознавать и предсказывать более сложные последовательности. В пользу этого говорят и другие источники по нейрофизиологии, я изучил их достаточно.
Принцип один - когда на входы нейрона приходят импульсы, это повышает или понижает его потенциал. Когда потенциал достигает порога, происходит деполяризация - нейрон выдаёт импульс на выходе и чувствительность входов активных в этот момент повышается. В живых клетках есть куча всяких белков, молекулярных насосов и прочего, регулирующих эти процессы, характеристики входов, скорость угасания потенциала, но я пришёл к выводу что математически это описывается куда проще - это просто последовательности дискретных сигналов которые клетки учатся узнавать и предсказывать.
Поэтому, если мы вместо моделирования отдельных нейронов будет моделировать сразу функциональность их групп да ещё алгоритмически более простым способом, и потом искать способ коммутировать такие блоки, мы сможем ускорить всё на порядки. А это уже может дать интересные результаты.

Pavia в сообщении #1259913 писал(а):

jabra в сообщении #1259884 писал(а):

Но хотелось бы по соптимизировать и распараллелить, чтобы на полную использовать возмонжости GPU/NPU.

Сначала напишите алгоритм. Тогда можно будет сказать как его оптимизировать.

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

Pavia в сообщении #1259913 писал(а):

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

Здесь интересный подход нашёл, изучаю пока https://en.wikipedia.org/wiki/Long_short-term_memory#Convolutional_LSTM, в ссылках там есть статья "Time series prediction".
Но мне по-прежнему кажется, что использовать нейросети для этой задачи это слишком большое усложнение, слишком сложно их обучать.
Я думаю что-нибудь вроде множества вероятностных конечных автоматов, или байесовы сети, которые можно обучить просто пересчитывая вероятности при поступлении каждого нового элемента входных последовательностей. Что-нибудь такое, но пока я не нашёл быстрого решения. Это должно работать как хэш - функция от элементов последовательности, мы сохраняем частоты последних хэшей и если они начинают повторяться, выдаём сигналы на выходе, как-то так. Но как вычислить этот хэш - вот в чём вопрос.
В общем, именно здесь нужны свежие идеи :)

Pavia в сообщении #1259913 писал(а):

jabra в сообщении #1259884 писал(а):

Пока я работаю над универсальным ядром - понимание смысла, работа с естественными языками и всё такое, насколько получится.

А каким же образом вы связали поиск повторов и понимания смыслов?

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

[Mihaylo]

jabra в сообщении #1260033 писал(а):

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

В реальных данных преобладают гладкость и компактность, а еще линейность. А еще наблюдаются резкие/лавинообразные изменения - что-то вроде $sign()$. Плавные линейные градиенты сменяются резкими или сглаженными скачками (границами). Еще наблюдается повторяемость во времени и пространстве. Это касается аудиоданных, видеоданных, различных временных рядов...

Вы хотите открыть еще более утонченные зависимости? Пожалуйста, совершенствуйте нейронные сети.

Кстати, универсальность - враг простоты. Модель получится более сложной, её труднее будет обучать. Увеличится время обучения (добавится время адаптации универсальной модели к конкретным задачам).

В общем я скептически отношусь к постановке цели.

[jabra]

Mihaylo в сообщении #1260237 писал(а):

В реальных данных преобладают гладкость и компактность, а еще линейность. А еще наблюдаются резкие/лавинообразные изменения - что-то вроде $sign()$. Плавные линейные градиенты сменяются резкими или сглаженными скачками (границами). Еще наблюдается повторяемость во времени и пространстве. Это касается аудиоданных, видеоданных, различных временных рядов...

Ну и что?

Mihaylo в сообщении #1260237 писал(а):

Вы хотите открыть еще более утонченные зависимости? Пожалуйста, совершенствуйте нейронные сети.

Кстати, универсальность - враг простоты. Модель получится более сложной, её труднее будет обучать. Увеличится время обучения (добавится время адаптации универсальной модели к конкретным задачам).

Она не выглядит более сложной, и насчёт обучения вопрос спорный.
Сомнения в основном в скорости моделирования такой сети. Хотя универсальность часто важнее производительности. С++ в разы быстрее, но куда больше народу пользуется питоном.

[ffbskt]

jabra
Так что в итоге? Я вот примерно тем же занимаюсь... Пишите в телегу у меня тот же ник если захотите ответить.

Вот нашел https://mipt.ru/upload/6ad/f_gb4q-arphcxl1tgs.pdf про алгоритм нахождения патернов во временных рядах,