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

[VoloCh]

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

А можно хотя-бы кусочек послушать?

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

А идейно что-то вроде такого. Пишем из головы какую-нибудь последовательность "как бы" случайную. Не очень длинную. Теперь будем ее улучшать. Для этого напишем ее несколько раз (а может 1 раз?) рядом. Потом вырежем кусок из середины (типа одну треть) и переставим местами эти 3 куска. Вроде "непредсказуемость" этой получившейся шняги строго возрастет.

[Circiter]

2VoloCh
Да не, не беспокойтесь. Мне просто было интересно. За сведения спасибо.

[Iura]

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

№ bit5 bit4 bit3 bit2 bit1 bit0
1 0 0 1 0 0 1
2 0 0 0 1 0 1
3 0 0 0 0 1 0
4 0 0 1 1 0 0
5 0 0 0 0 1 1
6 0 0 0 0 1 0
7 0 0 0 1 0 0
8 0 0 0 1 0 0
9 0 0 1 1 1 1
10 0 0 1 0 1 0
11 0 0 1 1 0 0
12 0 0 0 1 0 0
13 0 1 0 0 1 0
14 0 0 1 0 1 1
15 0 0 1 0 1 1
16 0 0 0 1 1 1
17 0 0 1 0 0 0
18 0 0 0 1 0 1

[VoloCh]

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

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

Оппа! Сначала вам надо было угадать один бит, а теперь оказыцца целых пять! Это другая задача, сэр!

[Iura]

Мне нужно угадать не само число, а каждый бит нового числа.

[Circiter]

2Iura
К сожалению, моя программулька ничего дельного на ваши биты не отвечает, говорит, что, мол, следующий бит нулем будет (с вероятностью большей 0,6).

То ли длины вашей последовательности не хватает чтобы собрать необходимую статистику, то ли я алгоритм неправильно реализовал (нет ли у вас, кстати, его точного описания?).

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

P.S.: А вы пробовали экстраполировать эти числа многочленом каким-нибудь?

[Iura]

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

[Circiter]

Цитата:

Мне нужно угадать не само число, а каждый бит нового числа.

Это одно и тоже.

Цитата:

нужно рассчитать наиболее вероятные значение бит для 19 числа

001011?

[Iura]

000001

-- Вс мар 21, 2010 19:34:35 --

из 6 бит угадали 4. То есть точность прогноза для числа 66.67%

Как оценить точность прогноза/вероятность для каждого бита ?

-- Вс мар 21, 2010 19:59:04 --

Частота появления 1 для каждого бита в заданной последовательности

0,00% 5,56% 44,44% 50,00% 50,00% 44,44%

Часто появления "пар" бит

Bit0
10 2
11 3
Вероятность, что после 1 будет 1 - 60%
Bit1
00 4
01 4
Вероятность, что после 0 будет 1 - 50%
Bit2
10 4
11 3
Вероятность, что после 1 будет 0 - 57%
Bit3
00 6
01 4
Вероятность, что после 0 будет 0 - 60%

-- Вс мар 21, 2010 20:14:02 --

Читаю - http://www.basegroup.ru/library/optimization/ga_math/

[Iura]

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

Цитата:

Мне нужно угадать не само число, а каждый бит нового числа.

Это одно и тоже.

Цитата:

нужно рассчитать наиболее вероятные значение бит для 19 числа

001011?

То что ты не смогу угадать значения новых бит - возможно ты и попал в эти 20% точности ? как это просчитать ?

[Circiter]

2Iura
Кажется, откопал наконец хоть что-то по алгоритмам, подобным шенноновской гадалке. А именно, речь идет о PPM-сжатии (Prediction by Partial Matching), которое, как оказалось, в той или иной форме применяется во многих популярных архиваторах типа zip/rar/etc; и об ориентированном на работу с битовыми строками DMC-сжатии (Dynamic Markov compression). Начальные сведения об этих методах (в основе которых лежат марковские цепи) можно получить в следующих статьях:

• J.G.Cleary, I.H.Witten, Data compression using adaptive coding and partial string matching
• A.Moffat, Implementing the PPM data compression scheme
• C.Bloom, Solving the problems of context modeling
• G.V.Cormak, R.N.S.Horspool, Data Compression Using Dynamic Markov Modeling

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

Цитата:

Читаю - http://www.basegroup.ru/library/optimization/ga_math/

А что, генетические алгоритмы тоже как-то относятся к текущей теме?

Цитата:

То что ты не смогу угадать значения новых бит - возможно ты и попал в эти 20% точности ? как это просчитать ?

Незнаю, скорее всего никак. :)

[Iura]

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

2Iura
Кажется, откопал наконец хоть что-то по алгоритмам, подобным шенноновской гадалке. А именно, речь идет о PPM-сжатии (Prediction by Partial Matching), которое, как оказалось, в той или иной форме применяется во многих популярных архиваторах типа zip/rar/etc; и об ориентированном на работу с битовыми строками DMC-сжатии (Dynamic Markov compression). Начальные сведения об этих методах (в основе которых лежат марковские цепи) можно получить в следующих статьях:

• J.G.Cleary, I.H.Witten, Data compression using adaptive coding and partial string matching
• A.Moffat, Implementing the PPM data compression scheme
• C.Bloom, Solving the problems of context modeling
• G.V.Cormak, R.N.S.Horspool, Data Compression Using Dynamic Markov Modeling

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

Цитата:

Читаю - http://www.basegroup.ru/library/optimization/ga_math/

А что, генетические алгоритмы тоже как-то относятся к текущей теме?

Цитата:

То что ты не смогу угадать значения новых бит - возможно ты и попал в эти 20% точности ? как это просчитать ?

Незнаю, скорее всего никак. :)

Генетические - возможно.

Жду результатов экспериментов:)

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

[Circiter]

И статейки почитайте обязательно, ok? Там все разжеванно, на прикладном уровне и в точности по вашей тематике.

Цитата:

Генетические - возможно.

Объясните, пожалуйста. Я почему-то не вижу пока связи.

[Circiter]

Кстати, чтобы зря не писать код на выброс, может быть сразу в виде какой-нибудь утилитки оформлять сии потуги? Какое практическое значение может иметь такая программка-предсказатель (недоделанный архиватор)? Какой у неё может быть интерфейс (форматы входных/выходных данных)? Какими ещё возможностями можно её снабздить? Или лучше оформить её в виде библиотечки для статистических приложений?

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

[Iura]

Как я понимаю - следующая популяция это и есть "экстраполяция" последовательности. Или мое предположение не верное ?

http://algolist.manual.ru/ai/ga/
http://ru.wikipedia.org/wiki/%D0%93%D0% ... 1%82%D0%BC

По поводу программы - я все равно хочу перевести алгоритм на sql.
А для тестов можно написать программу, которая берет в качестве исходного параметра - текстовой файл с последовательностью 1 и 0 разделенных ',' , а также кол-во прогнозируемых на M шагов (значение указывается в качестве параметра программы. по дефолту значение 1). Выходным параметром текстовой файл в таком же формате с прогнозированными на M шагов бит.