Популярно об ИИ. Вероятностная логика. Выпуск 1
Сообщение Windows:
«Файл, скорее всего, скопирован, но я на 100% не уверена»
...из юмора
Запланированная серия «Популярно об ИИ» для нового сезона получается не такой однозначной. Дело в том, что сейчас на базе вероятностной (не булевой) логики строится не только множество известных программных алгоритмов, но уже объявлено о появлении аппаратных устройств, в частности, судя по августовским новостям, процессоров Liryc Semiconductors. И именно этой современной и очень насущной теме хочется уделить ряд материалов. Но все оказалось довольно трудоемким, поскольку затрагивает целый ряд аспектов и направлений, к тому же хочется все объяснить простым языком, потому как общая серия называется «ПОПУЛЯРНО(!) об ИИ». Так что сейчас практическая база для материалов только формируется, включая даже вероятностное программирование (например, когда мы работаем с ситуацией, в которой известно, что все алгоритмы дают правильный ответ с вероятностью 80%).
Также мы введем такой термин, как «стохастическая аппроксимация», где слово «стохастический» для объяснения переведем как «умеющий угадывать» (в переводе с греческого), а «аппроксимация» — упрощение.
В общем, интересного вас ожидает много.
Интересный пример алогичности
Рабочие Петров и Иванов только что вышли из подвала, где занимались починкой. Лицо Петрова было серым от пыли, а лицо Иванова, наоборот, осталось чистым. Кто решил пойти умыться в первую очередь? Прочитали условие, подумали... Многие ответят правильно: это сделал Иванов, взглянув на Петрова:) и подумав, что он такой же грязный. Петров же, смотря на товарища, сделал вывод, что все в порядке. Эта задача интересна, прежде всего, алогичностью, если составлять математический алгоритм решения ситуации, применяя ее конкретно к рабочим, каждый из которых поставил перед собой вопрос: «Загрязнился ли я?».
Объясняя простыми словами, Иванов предположил, что если его товарищ запачкался, то велика вероятность того, что то же самое и с ним. А других причинных событий, влияющих на величину вероятности предполагаемого, в задании не описано. В результате оба, пользуясь вероятностной логикой, на вопрос «Загрязнился ли я?» ответили неправильно.
С другой стороны, мы имеем ситуацию отсутствия всяких решений для каждого из рабочих, которую можно описать очень интересной фразой из одного задачника по физике: «Для решения необходимых данных нет, а приведенные не нужны». Эту тему можно развивать довольно долго.
Задачи с четкой и нечеткой логикой
А в общем и целом, в рамках этого выпуска предлагаю вам ряд интересных логических задач на самостоятельное решение. Правильные ответы и их объяснения, конечно, присутствуют, но лучше с ними сверяться, а не читать сразу.
№1. Поймать мышь
В стене имеется пять норок 1, 2, 3, 4, 5, в одной из которых находится мышь. Задача кота — поймать ее. При этом он может засунуть только одну лапу только в одну из норок, и при каждой такой попытке перепуганная мышка обязательно перебегает в соседнюю норку, расположенную рядом справа или слева. Опишите оптимальный алгоритм действий для кота.
№2. Массив булевых значений
В массиве, содержащем 100 булевых значений A[100], 10 равны единице и расположены в случайном порядке, все остальные — нули. Ваша задача: в случайном порядке выделив из A[100] n элементов, сформировать массив B[n], а оставшиеся поместить в массив C[100-n]. При этом, не зная, сколько в B[n] попало единиц, произвести в его рамках операцию, которая бы приравняла количество единиц в B[n] и C[100-n]. Вопрос: чему должно быть равно n и какую операцию нужно сделать с массивом B[n]?
№3. Пять жадных пиратов
Пять жадных пиратов, старшинство которых начинается с 1-го и заканчивается пятым, взяли большой куш, например 100 золотых монет, и теперь стоит задача их поделить.
Они решили сделать это по определенной схеме: старший предлагает, как это сделать, и если это предложение принимается меньше чем половиной всех голосов, его убивают. Затем свое предложение дает следующий по старшинству при таком же условии. Вопрос: как правильно повести себя старшему пирату? На всякий случай скажем, что жадность в данном случае соревнуется разве что с желанием остаться в живых. Коварство, одним словом:). Напомню, что задача логическая, а не социальная.
№4. Парадокс Монти Холла
Это одна из очень известных задач теории вероятностей, причем парадоксальных, то есть имеющих противоречие. Итак, в рамках телешоу перед вами расположены три ящика A, B и C, в одном из которых расположен приз. Вы определяетесь с первоначальным выбором и указываете ящик. Но ведущий, зная, где находится приз на самом деле, не торопится его открыть, а... открывает один из пустых среди тех, на которые вы не указывали. Вопрос: в уже сложившейся ситуации стоит ли вам отказаться от первоначального решения и поменять свой выбор? Объясните все математически.
№5. Игра в орлянку на деньги
Допустим, вы располагаете суммой в Х рублей. Ваш визави предлагает сыграть в орлянку, подбрасывая монету. Если выпадет орел, то ваша сумма удвоится, если решка — вы отдаете половину. Два вопроса:
1. Стоит ли ввязываться в такую игру?
2. Что должен сделать ваш визави, чтобы игра была выгодна для него?
Решения
Ну что же, теперь можно свериться. Также, если вы нашли свои варианты правильных решений, можете написать на e-mail: christopher@tut.by, и если они несут в себе разумное зерно, мы, конечно же, опубликуем присланное. При этом вы можете прислать и свои собственные задачи.
№1. Поймать мышь
Решение: 234234 или зеркальное ему 432432.
Объяснение: конечно, можно прикидывать множество вариантов, но проще оперировать четными и нечетными числами. При этом, находясь в четной норке, мышка перебегает в нечетную и так далее. Допустим, она спряталась в четной, то есть во 2-й или 4-й. Рассмотрим вариант 234234. При первой попытке кот либо сразу угадывает, либо мышка находится в 4-й, затем перебегая в 3-ю или 5-ю. При второй попытке отсекается вариант третьей норки, и уже известно, что мышь сидит в пятой, и третья попытка завершит обход.
Но (!), если изначально мышка находилась в нечетной норке, то есть 1-й, 3-й или 5-й, то после трех попыток кота она оказывается в четной. Поэтому повторяем три действия, описанных выше.
№2. Массив булевых значений
Решение: n=10, B[n] нужно инвертировать, то есть поменять все нули на единицы и наоборот.
Объяснение: мы знаем, что в массиве A[100] 10 единиц, остальные — нули. В случайном порядке мы выбрали 10 элементов, если среди них попала, например, только одна единица, девять остальных остались в массиве C[100-n], а инвертировав B[10], мы получаем то же количество единиц с одним нулем, полученным после инвертирования попавшейся единицы. И так далее.
№3. Пять жадных пиратов
Решение: 98 — себе, 1 — третьему, 1 — пятому.
Объяснение: классический вариант с разматыванием стека, в данном случае в уме. То есть начинать нужно с конца.
Итак, если останется только два пирата, а именно, 4-й и 5-й, то последний ничего не получит, потому как у 4-го уже будет 50% голосов.
Если останется три пирата, то есть 3-й, 4-й и 5-й, то третьему нужно отдать одну монету пятому и объяснить, что будет в случае, если тот не проголосует за его решение.
Если останется четыре пирата, 2-й, 3-й, 4-й и 5-й, то второму достаточно дать одну монету четвертому и объяснить тому, что может быть в случае, если тот не проголосует за его решение.
Соответственно, если все пять пиратов живы, то старшему нужно отдать по монете третьему и пятому, и объяснить им, что может быть в случае...
№4. Парадокс Монти Холла
Решение: да, стоит.
Объяснение: при первоначальном выборе вероятность размещения приза в одном из трех ящиков составляет 1/3. Допустим, вы остановили свой выбор на A. Соответственно, можно сказать, что вероятность того, что приз находится в нем — 1/3, а того, что в двух остальных — 2/3. Ведущий, открыв пустой ящик среди B и C, например С, изменил приоритеты «двух остальных», то есть у нас получилось, что вероятность нахождения приза в B=2/3*1=2/3, а того, что в C — уже отсутствует, то есть С=2/3*0=0. Следовательно, вам следует поменять свой выбор, потому как вероятность в A остается 1/3, а в B — 2/3.
Решение данной задачи у многих вызывает сложности с пониманием. Но представьте себе ситуацию, когда перед вами 10 ящиков, в одном из которых находится приз. Вы выбрали, например, первый, а потом ведущий открыл восемь пустых ящиков, оставив два. Таким образом, вы или очень везучий, угадав сразу нужный ящик, потому как вероятность нахождения приза в нем изначально составляет 1/10, или сделаете умный выбор с переменой решения, поскольку вероятность нахождения приза во втором неоткрытом составляет 9/10.
Сама тактика такого метода принятия решений очень часто себя оправдывает.
№5. Игра в орлянку на деньги.
Решение: 1 — да, стоит; 2 — поменять условия увеличения и уменьшения сумм (см. объяснение).
Объяснение: выпадение орла или решки равновероятно (если не рассматривать случаи монеты на ребро, монеты с ошибкой, у которой две решки и т.п.), то есть мы имеем вариант 50/50. Это если смотреть с позиции четкой детерминированной логики. Хотя есть и парадокс: с точки зрения вероятности проблема выбора не является симметричной. Давайте посмотрим на то, чем вы рискуете. В случае выигрыша вы получаете сумму 2Х, проигрыша — у вас остается 0,5Х. Таким образом, вероятный средний выигрыш равен (2X+0.5X)/2, то есть, 1,25Х. Поэтому участвовать стоит.
Если сделка должна быть выгодна для вашего визави, то он должен высчитать условия таким образом, чтобы вероятный средний выигрыш был равен меньше единицы. Например, увеличивать вашу сумму в 1,5 раза, а уменьшать в четыре ((1,5Х+0,25Х)/2=0,875Х). И так далее.
Альтернативный вариант для визави — предложить подбрасывать не монету, а что-нибудь с большим количеством позиций с сохранением первоначальных условий, например треугольный брусок, который может упасть только на одну из трех граней.
Кристофер
«Файл, скорее всего, скопирован, но я на 100% не уверена»
...из юмора
Также мы введем такой термин, как «стохастическая аппроксимация», где слово «стохастический» для объяснения переведем как «умеющий угадывать» (в переводе с греческого), а «аппроксимация» — упрощение.
В общем, интересного вас ожидает много.
Интересный пример алогичности
Рабочие Петров и Иванов только что вышли из подвала, где занимались починкой. Лицо Петрова было серым от пыли, а лицо Иванова, наоборот, осталось чистым. Кто решил пойти умыться в первую очередь? Прочитали условие, подумали... Многие ответят правильно: это сделал Иванов, взглянув на Петрова:) и подумав, что он такой же грязный. Петров же, смотря на товарища, сделал вывод, что все в порядке. Эта задача интересна, прежде всего, алогичностью, если составлять математический алгоритм решения ситуации, применяя ее конкретно к рабочим, каждый из которых поставил перед собой вопрос: «Загрязнился ли я?».
Объясняя простыми словами, Иванов предположил, что если его товарищ запачкался, то велика вероятность того, что то же самое и с ним. А других причинных событий, влияющих на величину вероятности предполагаемого, в задании не описано. В результате оба, пользуясь вероятностной логикой, на вопрос «Загрязнился ли я?» ответили неправильно.
С другой стороны, мы имеем ситуацию отсутствия всяких решений для каждого из рабочих, которую можно описать очень интересной фразой из одного задачника по физике: «Для решения необходимых данных нет, а приведенные не нужны». Эту тему можно развивать довольно долго.
Задачи с четкой и нечеткой логикой
А в общем и целом, в рамках этого выпуска предлагаю вам ряд интересных логических задач на самостоятельное решение. Правильные ответы и их объяснения, конечно, присутствуют, но лучше с ними сверяться, а не читать сразу.
№1. Поймать мышь
В стене имеется пять норок 1, 2, 3, 4, 5, в одной из которых находится мышь. Задача кота — поймать ее. При этом он может засунуть только одну лапу только в одну из норок, и при каждой такой попытке перепуганная мышка обязательно перебегает в соседнюю норку, расположенную рядом справа или слева. Опишите оптимальный алгоритм действий для кота.
№2. Массив булевых значений
В массиве, содержащем 100 булевых значений A[100], 10 равны единице и расположены в случайном порядке, все остальные — нули. Ваша задача: в случайном порядке выделив из A[100] n элементов, сформировать массив B[n], а оставшиеся поместить в массив C[100-n]. При этом, не зная, сколько в B[n] попало единиц, произвести в его рамках операцию, которая бы приравняла количество единиц в B[n] и C[100-n]. Вопрос: чему должно быть равно n и какую операцию нужно сделать с массивом B[n]?
№3. Пять жадных пиратов
Пять жадных пиратов, старшинство которых начинается с 1-го и заканчивается пятым, взяли большой куш, например 100 золотых монет, и теперь стоит задача их поделить.
Они решили сделать это по определенной схеме: старший предлагает, как это сделать, и если это предложение принимается меньше чем половиной всех голосов, его убивают. Затем свое предложение дает следующий по старшинству при таком же условии. Вопрос: как правильно повести себя старшему пирату? На всякий случай скажем, что жадность в данном случае соревнуется разве что с желанием остаться в живых. Коварство, одним словом:). Напомню, что задача логическая, а не социальная.
№4. Парадокс Монти Холла
Это одна из очень известных задач теории вероятностей, причем парадоксальных, то есть имеющих противоречие. Итак, в рамках телешоу перед вами расположены три ящика A, B и C, в одном из которых расположен приз. Вы определяетесь с первоначальным выбором и указываете ящик. Но ведущий, зная, где находится приз на самом деле, не торопится его открыть, а... открывает один из пустых среди тех, на которые вы не указывали. Вопрос: в уже сложившейся ситуации стоит ли вам отказаться от первоначального решения и поменять свой выбор? Объясните все математически.
№5. Игра в орлянку на деньги
Допустим, вы располагаете суммой в Х рублей. Ваш визави предлагает сыграть в орлянку, подбрасывая монету. Если выпадет орел, то ваша сумма удвоится, если решка — вы отдаете половину. Два вопроса:
1. Стоит ли ввязываться в такую игру?
2. Что должен сделать ваш визави, чтобы игра была выгодна для него?
Решения
Ну что же, теперь можно свериться. Также, если вы нашли свои варианты правильных решений, можете написать на e-mail: christopher@tut.by, и если они несут в себе разумное зерно, мы, конечно же, опубликуем присланное. При этом вы можете прислать и свои собственные задачи.
№1. Поймать мышь
Решение: 234234 или зеркальное ему 432432.
Объяснение: конечно, можно прикидывать множество вариантов, но проще оперировать четными и нечетными числами. При этом, находясь в четной норке, мышка перебегает в нечетную и так далее. Допустим, она спряталась в четной, то есть во 2-й или 4-й. Рассмотрим вариант 234234. При первой попытке кот либо сразу угадывает, либо мышка находится в 4-й, затем перебегая в 3-ю или 5-ю. При второй попытке отсекается вариант третьей норки, и уже известно, что мышь сидит в пятой, и третья попытка завершит обход.
Но (!), если изначально мышка находилась в нечетной норке, то есть 1-й, 3-й или 5-й, то после трех попыток кота она оказывается в четной. Поэтому повторяем три действия, описанных выше.
№2. Массив булевых значений
Решение: n=10, B[n] нужно инвертировать, то есть поменять все нули на единицы и наоборот.
Объяснение: мы знаем, что в массиве A[100] 10 единиц, остальные — нули. В случайном порядке мы выбрали 10 элементов, если среди них попала, например, только одна единица, девять остальных остались в массиве C[100-n], а инвертировав B[10], мы получаем то же количество единиц с одним нулем, полученным после инвертирования попавшейся единицы. И так далее.
№3. Пять жадных пиратов
Решение: 98 — себе, 1 — третьему, 1 — пятому.
Объяснение: классический вариант с разматыванием стека, в данном случае в уме. То есть начинать нужно с конца.
Итак, если останется только два пирата, а именно, 4-й и 5-й, то последний ничего не получит, потому как у 4-го уже будет 50% голосов.
Если останется три пирата, то есть 3-й, 4-й и 5-й, то третьему нужно отдать одну монету пятому и объяснить, что будет в случае, если тот не проголосует за его решение.
Если останется четыре пирата, 2-й, 3-й, 4-й и 5-й, то второму достаточно дать одну монету четвертому и объяснить тому, что может быть в случае, если тот не проголосует за его решение.
Соответственно, если все пять пиратов живы, то старшему нужно отдать по монете третьему и пятому, и объяснить им, что может быть в случае...
№4. Парадокс Монти Холла
Решение: да, стоит.
Объяснение: при первоначальном выборе вероятность размещения приза в одном из трех ящиков составляет 1/3. Допустим, вы остановили свой выбор на A. Соответственно, можно сказать, что вероятность того, что приз находится в нем — 1/3, а того, что в двух остальных — 2/3. Ведущий, открыв пустой ящик среди B и C, например С, изменил приоритеты «двух остальных», то есть у нас получилось, что вероятность нахождения приза в B=2/3*1=2/3, а того, что в C — уже отсутствует, то есть С=2/3*0=0. Следовательно, вам следует поменять свой выбор, потому как вероятность в A остается 1/3, а в B — 2/3.
Решение данной задачи у многих вызывает сложности с пониманием. Но представьте себе ситуацию, когда перед вами 10 ящиков, в одном из которых находится приз. Вы выбрали, например, первый, а потом ведущий открыл восемь пустых ящиков, оставив два. Таким образом, вы или очень везучий, угадав сразу нужный ящик, потому как вероятность нахождения приза в нем изначально составляет 1/10, или сделаете умный выбор с переменой решения, поскольку вероятность нахождения приза во втором неоткрытом составляет 9/10.
Сама тактика такого метода принятия решений очень часто себя оправдывает.
№5. Игра в орлянку на деньги.
Решение: 1 — да, стоит; 2 — поменять условия увеличения и уменьшения сумм (см. объяснение).
Объяснение: выпадение орла или решки равновероятно (если не рассматривать случаи монеты на ребро, монеты с ошибкой, у которой две решки и т.п.), то есть мы имеем вариант 50/50. Это если смотреть с позиции четкой детерминированной логики. Хотя есть и парадокс: с точки зрения вероятности проблема выбора не является симметричной. Давайте посмотрим на то, чем вы рискуете. В случае выигрыша вы получаете сумму 2Х, проигрыша — у вас остается 0,5Х. Таким образом, вероятный средний выигрыш равен (2X+0.5X)/2, то есть, 1,25Х. Поэтому участвовать стоит.
Если сделка должна быть выгодна для вашего визави, то он должен высчитать условия таким образом, чтобы вероятный средний выигрыш был равен меньше единицы. Например, увеличивать вашу сумму в 1,5 раза, а уменьшать в четыре ((1,5Х+0,25Х)/2=0,875Х). И так далее.
Альтернативный вариант для визави — предложить подбрасывать не монету, а что-нибудь с большим количеством позиций с сохранением первоначальных условий, например треугольный брусок, который может упасть только на одну из трех граней.
Кристофер
Компьютерная газета. Статья была опубликована в номере 35 за 2010 год в рубрике технологии
