Экстрополяция двоичной последовательности

[Iura]

Всем привет !

Помогите найти/подскажите описание алгоритма (для написания программы) или уже готовую программу, которая может по N бит данных, рассчитать с большой вероятностью значение N+1 бита (с вероятностью >80%). Исходная последовательность генерируется не датчиком случайных чисел и содержит закономерности.

[Mikhail Sokolov]

Попробуйте почитать по теме universal prediction.

[ИСН]

Короче, там надо накапливать и хранить частоты встречаемости всех последовательностей по N+1 бит (и меньше), и по ним предсказывать.

[gris]

Я бы определил вначале некоторый критерий закономерности, который рассчитывается для подпоследовательностей достаточно большой длины и должен иметь приближённо одинаковое значение для всех подпоследовательностей. Потом рассмотрел последовательность плюс 0 и последовательность плюс 1. У которой значение критерия ближе к среднему, та и вероятнее. В статистике, наверное, можно нарыть чего-нибудь.

[Iura]

Можно переслать ссылки на конкретные стать или программы и по конкретной теме ?

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

-- Ср мар 03, 2010 12:22:11 --

[Xaositect]

Если известен вид закономерности, то можно использовать специализированные алгоритмы. Скажем, если зависимость линейная, то есть алгоритм Берлекэмпа-Мэсси.

[Профессор Снэйп]

Iura в сообщении #294118 писал(а):

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

Тогда, если чисто теоретически... Можно перебирать все программы, начиная с самых коротких и для каждой проверять, генерирует ли она эту самую последовательность. Как только будет найдена кратчайшая программа, её генерирующая, посмотреть, что эта программа выдаст на $(N+1)$-ый бит.

Тут правда проблема остановки... Время работы программы ничем не ограничено, может оказаться так, что длинная программа даст нужные $N$ битов и этот факт обнаружится довольно быстро, а ещё через какое-то время выяснится, что другая, более короткая программа, даст те же самые $N$ битов. Получается алгоритм с конечным числом ошибок...

Вроде есть такая тема "Learning system", это как раз то, что в теме спрашивается. У нас в Институте народ этим занимается. Я не интересовался никогда, надо поспрашивать.

[Iura]

Профессор Снэйп в сообщении #294168 писал(а):

Iura в сообщении #294118 писал(а):

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

Тогда, если чисто теоретически... Можно перебирать все программы, начиная с самых коротких и для каждой проверять, генерирует ли она эту самую последовательность. Как только будет найдена кратчайшая программа, её генерирующая, посмотреть, что эта программа выдаст на $(N+1)$-ый бит.

Тут правда проблема остановки... Время работы программы ничем не ограничено, может оказаться так, что длинная программа даст нужные $N$ битов и этот факт обнаружится довольно быстро, а ещё через какое-то время выяснится, что другая, более короткая программа, даст те же самые $N$ битов. Получается алгоритм с конечным числом ошибок...

Вроде есть такая тема "Learning system", это как раз то, что в теме спрашивается. У нас в Институте народ этим занимается. Я не интересовался никогда, надо поспрашивать.

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

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

[Профессор Снэйп]

Iura в сообщении #294437 писал(а):

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

Не, у нас всё чисто теоретически. Такого точно не будет

[Iura]

Профессор Снэйп в сообщении #294447 писал(а):

Iura в сообщении #294437 писал(а):

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

Не, у нас всё чисто теоретически. Такого точно не будет

Мдя ...
только теории все без практики

[Circiter]

2Iura

Цитата:

Помогите найти/подскажите описание алгоритма (для написания программы) или уже готовую программу, которая может по N бит данных, рассчитать с большой вероятностью значение N+1 бита (с вероятностью >80%).

Две наивные идеи:

1. Можно выделять из данной последовательности суффиксы длины от $\lfloor 0,5N\rfloor$ до $2$ и пытаться найти их (сопоставление с образцом) в оставшейся префиксной части последовательности. При удачном сопоставлении в качестве искомого бита следует взять бит, следующий сразу за блоком, похожим на рассматриваемый в данный момент суффикс.
   
   Останавливаться при первом удачном поиске не обязательно, можно рассмотреть все варианты, а потом выбрать наиболее часто встречающийся.
   
   Кроме того, сопоставление можно производить нечетко, e.g., минимизируя расстояние редактирования.
   
2. А что если нарезать последовательность на пронумерованные куски (равные по длине), а потом решать более классическую задачу экстраполяции функции, сопоставляющей номеру куска кодируемое им число?

[Iura]

ПО SPSS statistics может помочь мне решить поставленную задачу ?

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

[Circiter]

2Iura
Вбейте в поисковик "Гадалка Шеннона". Нам её в универе на первом или втором курсе задавали как домашнюю работу по теории информации. Реализуется очень просто, буквально в несколько строк кода и неплохо угадывает очередной бит при использовании плохого генератора случайных чисел (т.е., при игре с человеком).

[Iura]

Circiter в сообщении #294728 писал(а):

2Iura
Вбейте в поисковик "Гадалка Шеннона". Нам её в универе на первом или втором курсе задавали как домашнюю работу по теории информации. Реализуется очень просто, буквально в несколько строк кода и неплохо угадывает очередной бит при использовании плохого генератора случайных чисел (т.е., при игре с человеком).

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

[ИСН]

Именно это она и делает. И именно она Вам и нужна.