?

Log in

No account? Create an account
Человек из Кумертау
April 9th, 2013
08:44 pm

[Link]

Previous Entry Share Flag Next Entry
Прикладной вопрос
(формулирую с использованием формальной математики, но смысл должен быть понятен и нематематикам, просто так точнее)

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

Мы знаем следующее:
1) существует много - возможно, бесконечно много, но в любом случае достаточно много чисел (мы говорим только о натуральных: 1, 2, 3...), как обладающих этим свойством, так и нет;
2) свойство имеет какое-то достаточно простое словесное или формульное выражение, которое также можно (если оно будет известно) формализовать на любом языке программирования.

У нас есть два набора чисел, в каждом из которых их ровно 100. Все числа в первом наборе обладают интересностью, во втором - ни одно (естественно, никакое число не входит в оба набора одновременно). Для простоты предположим, что все рассматриваемые числа достаточно малы (если качественное определение вас не устраивает, скажу, что, в совокупости с п. 2 это говорит нам, что асимптотическая сложность проверки любого числа из набора на соответствие любой осмысленной гипотезе о том, что такое интересность, не превышает O(1)).

Наша задача - определить, в чем именно заключается интересность.

Задачу пытаются решить наши старые друзья Вася и Петя. Они делают это независимо друг от друга.

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

Петя случайным образом выбирает 70 чисел из ста в том и другом списке, стараясь даже не посмотреть на остальные дважды тридцать, и проделывает с ними ту же операцию, что и Вася; в результате он выдвигает 4 гипотезы и называет их a, b, c, d в порядке сложности, при этом a - наиболее сложная, d - самая простая. Затем он применяет эти гипотезы к оставшимся числам (30 интересным и 30 неинтересным) и узнает, что гипотезы a и d неверны, а b и c соответствуют имеющимся данным. Он выбирает гипотезу c как наиболее простую среди подходящих и пишет в ЖЖ пост, где говорит, что интересность - это, скорее всего, c.

Интуитивно - по крайней мере, мне - кажется, что подход Пети корректнее, так как не дает "подогнать" гипотезу под исходные данные, а оставляет возможность апостерирной проверки. А как вы считаете:

1) Какой подход продуктивнее? Как бы поступили вы?
2) Какой результат является более достоверным в строгом смысле слова (при условии, что исходные данные ровно таковы, как в описании задачи, ну разве что)? Можете ли вы это доказать?
3) Можно ли количественно, а не только качественно охарактеризовать различие достоверности в том или ином случае?
4) Если подход Пети действительно лучше, то в какой пропорции стоит разбивать исходные данные? 70/30? 80/20? 50/50? Почему?

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

Также загляните сюда - оно почти о том же самом, просто в другой предметной области и другими словами :) Подробнее еще будет.

Tags:

(16 comments | Leave a comment)

Comments
 
From:onery
Date:April 9th, 2013 05:34 pm (UTC)
(Link)
Ну если брать частный случай -- то методом пристального взгляда в голове удержать больше 10 чисел все-равно не получится. То есть будет так: смотрю первые три - гипотеза - проверка на следующих 2х - не сошлась - пытаюсь построить гипотезу по этим пяти - проверка - сошлась - проверяю еще пять - не сошлась - новая гипотеза
примерно так
в эту стопку и достаточность количества чисел
есть подозрение, что это довольно естественный процесс, то есть если чисел _достаточно_ он будет идти сам собой

а если задана ограниченная выборка, то и возникают странные спецэффекты в виде достоверности, которая в обоих случаях настолько подозрительная, что научность второго подхода обосновать не выходит
[User Picture]
From:bormvit
Date:April 9th, 2013 05:42 pm (UTC)
(Link)
1) Ну представим, что Вася и Петя живут в XXX веке, и технологии их времени позволяют держать в памяти и работать сразу с десятками чисел - но качественно мышление не изменилось, т. е. когнитивные искажения, предвзятость, способ подбора гипотез - такой же.

2) Можно также представить, что Вася и Петя нормальны, но большинство интересных чисел в выборке выглядит, скажем, как 1001, 1015, ..., 1000+10x+y, .. 1059, из неинтересных ни одно не имеет такой вид, но в выборе интересных есть и несколько числа, не имеющих вида 1000+10x+y (x, y - цифры от 0 до 9). И в 70 из 100 Петиных чисел эти интересные, но не такие, как прочие, не попали - и вид 1000+10x+y и стал гипотезой d (которая "видна" по списку).

Это условности, конечно; речь о том, что важен сам подход (Пети и Васи), а не применимость к данным условиям. Похожие данные сложно обнаружить в чистом виде (но "с примесями" и менее формально, как я думаю и позже напишу, подобные задачки встречаются гораздо чаще, чем кажется), поэтому и приходится навешивать условности; однако мы говорим не о самих условностях.
From:onery
Date:April 9th, 2013 05:45 pm (UTC)
(Link)
Мне кажется, про d вообще можно не думать, потому что она в Пети была отсеяна, а Вася ее и не генерировал. Вопрос, является ли c достовернее, чем Васина гипотеза. Безотносительно d вообще.
[User Picture]
From:bormvit
Date:April 9th, 2013 05:50 pm (UTC)
(Link)
Возможно, что это в итоге одна и та же гипотеза (которая, как и d, может отсеяться на еще большем наборе чисел - а может, это разные гипотезы, но эквивалентные на достаточно большом наборе чисел):)

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

(Стоп. Так, кажется, я постиг это дао, сейчас еще поколдую с ручкой над листом бумаги и скажу, постиг или нет :) )
From:onery
Date:April 9th, 2013 05:51 pm (UTC)
(Link)
Ага, расскажи, а я буду думать, чем можно занять студентов на 4,5 часа так, чтобы у них мозги не закипели.
[User Picture]
From:bormvit
Date:April 9th, 2013 05:52 pm (UTC)
(Link)
этой задачкой
From:onery
Date:April 9th, 2013 05:53 pm (UTC)
(Link)
Через 20 минут они просто отвернутся от нее.
Но за идею спасибо ))

Edited at 2013-04-09 05:54 pm (UTC)
[User Picture]
From:bormvit
Date:April 9th, 2013 05:58 pm (UTC)
(Link)
Ну, я не всерьез предположил, т. к. программа же, наверное, все-таки о другом :)

Но если бы я решил бы и имел возможность заняться этой задачкой на практике, то я бы и придумал несколько вариантов интересности (интересных, конечно, хотя долго думать), разбил бы студентов на группы на каждый вариант и пусть анализируют :) Дальнейшие извращения в духе "одним давать методику, другим нет, одним давать сразу все, другим порциями, одни варианты интересности делать с уклоном туда, другие - сюда" опциональны :)
[User Picture]
From:bormvit
Date:April 9th, 2013 06:29 pm (UTC)
(Link)
В общем, дао примерно вот в чем. Это, наверное, можно выразить и количественно, хотя и неточно, но зело эвристично и долго, поэтому объяснию качественно.

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

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

Предположим, что Петя берет, к примеру, не 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). Но это интуитивно, формализовать, наверное, можно, но а) лень, б) идея, кажется, и так ясна :)
From:onery
Date:April 9th, 2013 06:51 pm (UTC)
(Link)
Здесь ты кажется, описал примерно то же, о чем я говорила. Но проблема, которую я увидела, была в том, что на любом ограниченном множестве мы не можем сказать, почему Вася нехорош. Почему его соответствие данным мы за достоверность не считаем.

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

(Вот еще нигде не было обоснованно, почему модель нужно выбирать саму простую :))
[User Picture]
From:bormvit
Date:April 9th, 2013 07:02 pm (UTC)
(Link)
Ну, описываемость интересности некой моделью - допустим, известна по условию.

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

Если даже не предполагать точно, что интересность действительно так уж и интересна описывается некой внятной моделью, но не быть уверенным и в обратном, то это ничего не меняет: если мы предположим наличие модели, а ее по факту не окажется, то ничего страшного не случится (и мы это с большой достоверностью поймем по несущестовованию простой описывающей выборку гипотезы), а вот если на самом деле модель есть, а мы ее не заметим, то это будет... обидно :)
From:onery
Date:April 9th, 2013 07:15 pm (UTC)
(Link)
Вопрос, откуда берется предсказательная сила модели - отдельный интересный вопрос.
И как мы можем определить отсутствие модели?
[User Picture]
From:bormvit
Date:April 9th, 2013 07:23 pm (UTC)
(Link)
> Вопрос, откуда берется предсказательная сила модели - отдельный интересный вопрос.

Ну, чем проще модель, тем больший диапазон случаев она охватывает. Модель "встать в 8:02, решить еще поспать, встать в 8:09, поесть яичницу, сесть на 51-й трамвай и доехать на завод "Искра"" верна для конкретного утра одного человека, модель "встать с утра и поехать на работу" - для неизмеримо большего диапазона случаев. Модель "тела падают на планету с ускорением 9,81 м/с^2" верна для гравитационного поля вблизи поверхности Земли, модель "тела падают на планету с ускорением GM/r^2" верна для неизмеримо большего количества планет (хотя, возможно, не для всех). Не знаю, как ответить на вопрос, почему так, но что так - наблюдаемо :) Как для законов природы, так и для того, что выдумано человеком. (Разумеется, если наши модели в своей простоте не отбрасывают какую-то важную часть реальности :)

> И как мы можем определить отсутствие модели?
Точно, наверное, никак (но мы и не говорим об абсолютной точности), но если разом осушить пузырек с пометкой "яд" очень долго пытаться подобрать простую модель к хаотичным числам, то рано или поздно ты можешь понять, что здесь что-то не так :)
From:onery
Date:April 9th, 2013 07:35 pm (UTC)
(Link)
То, что ты назвал, это не более простые модели, а более общие. Тогда "все есть" - самая простая и работающая модель :)

Мне чудится, что в доказательстве преимуществ петиного подхода существенно будет использоваться познаваемость мира описываемость моделью интересующего свойства. Что модель может быть достоверной вообще, и что это ее свойство можно проверить.
[User Picture]
From:bormvit
Date:April 9th, 2013 07:42 pm (UTC)
(Link)
Нет, "все есть" - неработающая модель. Она не позволяет предсказать ничего нового и отделить истину от лжи. Модель с гравитацией позволяет сказать, будет ли высказывание "на Марсе тела падают с таким-то ускорением" истинным или ложным и предсказать напряженность гравитационного поля вблизи Альфы Центавра; модель с хождением на работу позволяет оценить вероятность того, что случайный человек идет утром на работу. Но в целом да, примеры не совсем удачные: общие/частные и простые/сложные модели - немножко разные оси.
[User Picture]
From:bormvit
Date:April 9th, 2013 06:52 pm (UTC)
(Link)
А вот скажи.

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