Виталий Бормотов (bormvit) wrote,
Виталий Бормотов
bormvit

  • Mood:

К задаче ниже

(вынесено из комментариев отсюда)

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

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

Предположим, что Петя берет, к примеру, не 70, а потом 100 чисел (куда включаются и эти 70), а N1, N2... Nm (мне лень индексы форматировать, но это они :)), в данной задаче Nm = 100, при этом каждая последующая выборка включает в себя предыдущую (т. е. он рассматривает N(i+1)-Ni новых чисел на каждом i+1-м шаге; а вообще это могут быть и не числа, а что угодно, любые данные, удовлетворяющие любой структуре гипотез). При этом N1 << Nm, но N1 достаточно велико, чтобы создать достаточно узкое множество гипотез (десятку чисел может удовлетворять 6 разумных гипотез, двум числам - 6000 :)) При переходе N(i) -> N(i+1) каждый раз часть гипотез отсекается; Петя каждый раз следит за упорядоченностью множества гипотез по сложности (сложность - это, скажем, длина простейшей булевой функции-детектора гипотезы на C++ с определенным ограничениями ну или что-то такое).

Петя обращает внимание на следующие данные:
1. Частота отсекания гипотез;
2. Простота отсекаемых гипотез;
3. Зависимость частоты отсекания и простоты отсекаемого от N(i+1)/Ni (соотношения выборок).
4. Зависимость частоты отсекания и простоты отсекаемого от N(i+1)/Nm (близости текущей выборки к наиболее полной из имеющихся - отсекание гипотез при переходе от выборки из 2 чисел к выборке из 3 чисел не даст практически ничего, а от 60 к 80, если чисел всего 100, даст вполне релевантный результат).

Эти данные ничего, разумеется, не говорят ни о числах, ни о гипотезе сами по себе, но они релевантны в качестве оценки способности Петиного мозга строить гипотезы, и экстраполировав их (думаю, есть способ сделать это численно, но над этим придется покорпеть) на некие еще большие выборки - и неважно, что их у нас нет - Петя сможет оценить достоверность своей гипотезы. (Может быть ситуация, когда нет нужды найти точное определение интересного числа, но есть смысл найти такую булевую функцию, которая будет совпадать с этим определением, скажем, в (1-epsilon)*100% случаев на некоем множестве чисел, где epsilon мало - и тогда Петя, теоретически, сможет оценить вероятность того, что его гипотеза соответствует подобному критерию.)

Вопрос 4, правда, все еще остается открытым. Думаю, m - т. е. число итераций - должно быть сильно больше двух, N(i+1)-N(i) можно сделать примерно одинаковым для всех i (чтобы было проще считать), а N1 примерно равным этому N(i+1)-N(i) (и сильно больше 5-6). Но это интуитивно, формализовать, наверное, можно, но а) лень, б) идея, кажется, и так ясна :)

(прочитать дальше или откомментировать)

И еще задачка примерно о том же:

Есть примерно те же условия, только у нас нет 100 чисел таких и таких, зато у нас есть черный ящик, который принимает на вход число и выдает, интересное оно или нет (безошибочно). До всех экспериментов известно, что среди 100 случайных чисел не меньше 30 в среднем будут интересными, не меньше 30 неинтересными (истинное распределение пока неизвестно, но где-то в этих пределах). Одно обращение к ЧЯ стоит 1 $. Требуется составить гипотезу о природе интересности чисел, которая будет работать в 95% случаев, потратив как можно меньше долларов. Для простоты все числа меньше 10^9.

(прочитать дальше или откомментировать)

Все комментарии, чтобы всё было рядом, - туда :)
Tags: познание
Subscribe
Comments for this post were disabled by the author