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

[Circiter]

2Yuri Gendelman

Цитата:

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

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

[Yuri Gendelman]

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

2Yuri Gendelman

Цитата:

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

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

Логично

Circiter писал(а):

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

В обобщенном виде: строго большей, чем вероятность случайного выбора.

[Yuri Gendelman]

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

Цитата:

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

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

Между прочим, если некоторая функция $F(...)$ правильно оценивает следующий бит с вероятностью 30%, то функция $1 - F(...)$ будет правильно оценивать следующий бит с вероятностью 70%.

[Iura]

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

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

Цитата:

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

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

Между прочим, если некоторая функция $F(...)$ правильно оценивает следующий бит с вероятностью 30%, то функция $1 - F(...)$ будет правильно оценивать следующий бит с вероятностью 70%.

По логике да. А в жизни так ? :)

Могу сейчас придумать алгоритм, который будет угадывать бит с вероятностью 5%. Означает ли это, что если я буду делать инверсию прогнозируемых бит, то моя вероятность вырастит до 95%? Что-то меня мучают смутные сомнения :)

[VoloCh]

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

По логике да. А в жизни так ? :)

Гениальный вопрос! Вот уж точно есть 10 типов людей, понимающих двоичный код...

[Iura]

VoloCh в сообщении #307869 писал(а):

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

По логике да. А в жизни так ? :)

Гениальный вопрос! Вот уж точно есть 10 типов людей, понимающих двоичный код...

Типа, что задача придумать алгоритм, который будет угадывать бит с точность 20% равнозначна задаче угадать бит с точностью 80% (по инверсии). В таком случае все алгоритмы по определению предсказывают биты в диапазоне от 20% до 80%, поскольку предсказание в не этого диапазона очень сложная задача ?

[Yuri Gendelman]

VoloCh в сообщении #307869 писал(а):

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

По логике да. А в жизни так ? :)

Гениальный вопрос! Вот уж точно есть 10 типов людей, понимающих двоичный код...

Ну это же классика:
"В действительности всё не так, как на самом деле"
(Станислав Ежи Лец)

[blackbird72]

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

[blackbird72]

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

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

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

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

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

[mserg]

Выявление закономерности – это суть нахождение математической модели (формулы, системы уравнений, программы и т.п.), описывающих исходные данные (в данном случае последовательности бит). См. черновик по этой теме здесь:
http://np-soft.ru/downloads/automodel.zip

Как выяснилось, чтобы задача подбора модели стала «корректной», должны быть «заданы» «параметры» уверенности в полноте исходных данных, требуемая точность (здесь «вероятность») и возможный объем расхода ресурсов (памяти, числа шагов).

P.S. Вероятности можно подсчитать только в рамках (вероятностной) математической модели; в данной задаче происходит подбор самой модели и никто не гарантирует ее «правильности», т.е. гарантированная вероятность здесь в принципе невозможна. Ну, если считать подобранную модель правильной, то да, вероятность предсказания можно подсчитать.