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

[Pavia]

Iura смешной вы человек. Вы сами не понимаете о чем пишете. Вам с озов надо учиться что есть вероятность, что есть случайные числа, что есть не случайные. Как вообще проводятся измерения, что такое Критерий Стьюденту. И тд.

Самые дельные советы были на первой странице. А еще у вас постановка задачи хромает.

[Iura]

Pavia ? сообщении #305559 писал(а):

Iura смешной вы человек. Вы сами не понимаете о чем пишете. Вам с озов надо учиться что есть вероятность, что есть случайные числа, что есть не случайные. Как вообще проводятся измерения, что такое Критерий Стьюденту. И тд.

Самые дельные советы были на первой странице. А еще у вас постановка задачи хромает.

Ia ne matematik.
Obratilsia na forum za pomoshiu znaiushix liudei.
postanovka zadachi korrektna.
drygoe delo dlia chego ia xochu ispolzovat polucheni algoritm.
blagodaren vsem kto pomogaet razobratsa.

[Circiter]

2Pavia

Цитата:

постановка задачи хромает

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

[Circiter]

2Iura

(Оффтоп)

Не пишите на транслите.

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

Оказывается, дополнительную информацию пересылать вовсе не нужно. Достаточно применить т.н. динамическое моделирование при котором статистика для предсказания и для распаковки собирается по одному и тому же алгоритму и, получается, декомпрессор может извлечь её прямо из сжатых данных.

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

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

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

Именно поэтому, на практике, для сжатия применяют, например, арифметическое кодирование, при котором более вероятные элементы (числа) последовательности кодируются меньшим числом бит чем менее вероятные.

Такой алгоритм "хорошие" данные уж точно будет сжимать, да ещё и без потерь (т.е. обратимо). Вот, только сейчас яность начала приходить потихоньку. :)

-- Сб апр 03, 2010 00:02:33 --

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

[Iura]

-- Сб апр 03, 2010 00:02:33 --

Связь же задачи предсказания с задачей оптимизации мне так и не стала понятна, увы. Разве что здесь речь может идти о минимизации ошибки предсказания, правда тогда опять непонятен выбор именно генетических алгоритмов... Хотя да, в некотором смысле, эволюция, создавая новые виды, совершает своего рода "предсказания". Но хотелось бы все-таки пощупать более формальную сторону этой догадки-интуиции. По-прежнему надеюсь на подробные объяснения (при этом я сильно сомневаюсь в практической значимости таких результатов, слишком уж ГА "тормознутые").[/quote]


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

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

[Pavia]

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

А что бы это все понять надо выбрать конкретную задачу и ее решать.

Цитата:

postanovka zadachi korrektna.
drygoe delo dlia chego ia xochu ispolzovat polucheni algoritm.

А у вас все наоборот. Перепутаны причины и следствия.
Решением вашей задачи является исследование все возможных вариантов условий.

Так что задачу надо ставить конкретнее.

А иначе.

(Оффтоп)

Шерлок Холмс и Ватсон летели на воздушном шаре и совершили вынужденную посадку в пустыне. Вокруг от горизонта до горизонта - один песок... Вдруг видят - проходит мимо человек. Ватсон спрашивает у него:
- Вы не могли бы сказать хотя бы приблизительно, где мы находимся?
В ответ слышат:
- Не только приблизительно, но и совершенно точно - вы находитесь в корзине воздушного шара!
Холмс:
- Да-а-а... Это - математик!
Ватсон (изумленно):
- Как Вы об этом узнали, Холмс?
Холмс:
- Элементарно, Ватсон! Только у математика мог быть такой абсолютно точный и абсолютно бесполезный ответ

[Circiter]

Охр хорошая (правда очень старая) обзорная статья: T.Bell, I.N.Witten, J.G.Cleary, Modeling for Text Compression.

-- Сб апр 03, 2010 02:02:48 --

2Iura

Цитата:

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

Это таже самая тема, поверьте. :) Кстати, вы прочитали рекомендованные мной статьи?

Цитата:

Предлагаю эту тему обсудить отдельно по электронной почте.

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

[Iura]

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

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

А что бы это все понять надо выбрать конкретную задачу и ее решать.

Цитата:

postanovka zadachi korrektna.
drygoe delo dlia chego ia xochu ispolzovat polucheni algoritm.

А у вас все наоборот. Перепутаны причины и следствия.
Решением вашей задачи является исследование все возможных вариантов условий.

Так что задачу надо ставить конкретнее.

А иначе.

(Оффтоп)

Шерлок Холмс и Ватсон летели на воздушном шаре и совершили вынужденную посадку в пустыне. Вокруг от горизонта до горизонта - один песок... Вдруг видят - проходит мимо человек. Ватсон спрашивает у него:
- Вы не могли бы сказать хотя бы приблизительно, где мы находимся?
В ответ слышат:
- Не только приблизительно, но и совершенно точно - вы находитесь в корзине воздушного шара!
Холмс:
- Да-а-а... Это - математик!
Ватсон (изумленно):
- Как Вы об этом узнали, Холмс?
Холмс:
- Элементарно, Ватсон! Только у математика мог быть такой абсолютно точный и абсолютно бесполезный ответ

Мне нужен алгоритм или программа для нахождения значения N+1 бита (с заданной вероятностью) на основе известной последовательности N бит.

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

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

Прошу дальнейшее обсуждения "правильности" подхода вынести за рамки ветки форума.

Дайте возможность сосредоточиться на решении текущей задачи с N+1 бит. Заранее спасибо за понимание.

-- Сб апр 03, 2010 09:11:46 --

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

Охр хорошая (правда очень старая) обзорная статья: T.Bell, I.N.Witten, J.G.Cleary, Modeling for Text Compression.

-- Сб апр 03, 2010 02:02:48 --

2Iura

Цитата:

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

Это таже самая тема, поверьте. :) Кстати, вы прочитали рекомендованные мной статьи?

Цитата:

Предлагаю эту тему обсудить отдельно по электронной почте.

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

Отвечаю честно.
Смогу заняться чтением на следующей неделе.
Сейчас выполняю срочную проект на работе. Пока успеваю, только просматривать сообщения на ветке форума и оставлять сообщения :(

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

[Pavia]

Цитата:

Если вам очень интересно, то я могу вам переслать условие задачи в не рамках форума,

Высылай, тогда можно будет поговорить.

Цитата:

Мне нужен алгоритм или программа для нахождения значения N+1 бита (с заданной вероятностью) на основе известной последовательности N бит.

Возьмем идеальный случай алгоритм может быть каким угодно. Допустим что количество алгоритмов счетно и вероятность выбора каждого алгоритма равновероятна. Отсюда имеем вероятность выпадания 0 и 1 равных 0.5.Ответ с заданной вероятностью нельзя. Она будет всегда 0.5. Дальше можно по фантазировать на тему о не случайности выбора алгоритма да и других темах коих несчетное множество (Или счетное?).
В общих чертах задача не решаема так как дополнительно можно навесить много всего, в частных сколько угодно.

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

У вас процесс какой?

[Iura]

Цитата:

Отсюда имеем вероятность выпадания 0 и 1 равных 0.5.

Вероятность выпадания чего ? События которое я анализирую? Оно по определению не может быть 0.5, поскольку это сложный физический процесс. Физический мир не идеален.

[Circiter]

2Pavia
Но здесь ведь под вероятностью понимают нечто специальное, что-то вроде относительной частоты. В теории информации так и делают, даже если это и не совсем строго.

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

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

В общем, некоторая некорректность постановки задачи (проблемы) проистекает именно из сугубо прикладного её характера.

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

То есть можно ведь предсказывать, значит решение есть.

Короче говоря, попытка формализовать и корректно поставить исходную задачу уже дает половину решения, поэтому это не так-то просто сделать... :)

2Iura

Цитата:

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

Эх, почему-бы вам все-таки "не расколоться" и не описать свой подход прямо здесь?

Цитата:

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

А почему именно свой? Чем существующие методы не устраивают? Это не риторический вопрос, просто хочется услышать о мотивах.

[Iura]

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

2Pavia
Но здесь ведь под вероятностью понимают нечто специальное, что-то вроде относительной частоты. В теории информации так и делают, даже если это и не совсем строго.

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

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

В общем, некоторая некорректность постановки задачи (проблемы) проистекает именно из сугубо прикладного её характера.

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

То есть можно ведь предсказывать, значит решение есть.

Короче говоря, попытка формализовать и корректно поставить исходную задачу уже дает половину решения, поэтому это не так-то просто сделать... :)

2Iura

Цитата:

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

Эх, почему-бы вам все-таки "не расколоться" и не описать свой подход прямо здесь?

Цитата:

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

А почему именно свой? Чем существующие методы не устраивают? Это не риторический вопрос, просто хочется услышать о мотивах.

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

[Circiter]

2Iura

Цитата:

Методы, для решения основной задачи дают достоверный результат с вероятностью до 30%.

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

[Yuri Gendelman]

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

... хоть какая-то польза от предиктора может быть, только если он делает предсказания с вероятностью строго большей 0,5...

Это зависит от соотношения между ценой ошибки и ценой успеха. Возможно, например, что предиктор применяется в теоретико-игровом контексте.

[Iura]

Yuri Gendelman в сообщении #306644 писал(а):

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

... хоть какая-то польза от предиктора может быть, только если он делает предсказания с вероятностью строго большей 0,5...

Это зависит от соотношения между ценой ошибки и ценой успеха. Возможно, например, что предиктор применяется в теоретико-игровом контексте.

Близко к истине