2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Экстрополяция двоичной последовательности
Сообщение20.03.2010, 04:30 


16/03/10
212
Circiter в сообщении #299633 писал(а):
А можно хотя-бы кусочек послушать?
Ну если вам это честно очень важно, дайте знать и я попробую потрясти старых знакомых (которых не видел много лет) и выцепить у них точную ссылку (один из знакомых - автор статьи).

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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение20.03.2010, 04:37 
Заслуженный участник


26/07/09
1559
Алматы
2VoloCh
Да не, не беспокойтесь. Мне просто было интересно. За сведения спасибо.

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение21.03.2010, 10:15 


03/03/10
26
Как обещал пересылаю пример
Это набор чисел представленных в двоичном представлении.
На основе имеющихся данных и использую алгоритм для прогнозирования двоичной последовательности, нужно рассчитать наиболее вероятные значение бит для 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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение21.03.2010, 14:02 


16/03/10
212
Iura в сообщении #294118 писал(а):
Помогите найти/подскажите описание алгоритма (для написания программы) или уже готовую программу, которая может по N бит данных, рассчитать с большой вероятностью значение N+1 бита (с вероятностью >80%). Исходная последовательность генерируется не датчиком случайных чисел и содержит закономерности.
Оппа! Сначала вам надо было угадать один бит, а теперь оказыцца целых пять! Это другая задача, сэр!

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение21.03.2010, 18:08 


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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение21.03.2010, 18:51 
Заслуженный участник


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

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

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

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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение21.03.2010, 19:03 


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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение21.03.2010, 19:22 
Заслуженный участник


26/07/09
1559
Алматы
Цитата:
Мне нужно угадать не само число, а каждый бит нового числа.

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

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

001011?

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение21.03.2010, 19:31 


03/03/10
26
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/

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение25.03.2010, 12:47 


03/03/10
26
Circiter в сообщении #300494 писал(а):
Цитата:
Мне нужно угадать не само число, а каждый бит нового числа.

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

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

001011?


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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение31.03.2010, 17:00 
Заслуженный участник


26/07/09
1559
Алматы
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

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

Цитата:

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

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

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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение31.03.2010, 17:10 


03/03/10
26
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

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

Цитата:

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

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

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


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

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

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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение31.03.2010, 17:24 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение01.04.2010, 21:28 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Экстрополяция двоичной последовательности
Сообщение02.04.2010, 07:55 


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 70 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group