Популярно об ИИ. Вероятностная логика. Выпуск 2
Вообще, понятие вероятностной логики, характерной для решения задач недетерминированного типа в динамично изменяющейся среде, именно в программировании весьма условно. Дело в том, что все потом все равно переводится на более понятный язык конкретных значений и булевых флагов. И пусть вас даже со страниц многотомных трудов мучают персептронами, нейронными сетями, использующими весовые коэффициенты для входящих сигналов — все равно это уже, по существу, чистая арифметика. Точнее сказать, при создании ИИ, специалист в этом вопросе пишет алгоритм вроде: «как считать будем». И, по существу, в большинстве случаев под вероятностной логикой понимают обычную с весовыми коэффициентами.
Причем стоит обратить внимание на то, что есть специализированные языки для ИИ (наиболее легкий в освоении для нынешних поколений — Visual Prolog), но в ряде случаев на практике они не используются. Вместо них применяют те же C/C++ или Lua.
В прошлом материале серии мы продемонстрировали классическую задачу алогичности с двумя рабочими. Напомню вкратце: два рабочих, Иванов и Петров, вышли из подвала, где делали починку оборудования. У Иванова лицо запылилось, у Петрова — нет. Вопрос: кто решит пойти умываться в первую очередь? Ответ: Петров, поскольку он посмотрит на Иванова и решит, что он тоже загрязнился. Сама задача абстрагирована, но при этом мы можем наглядно наблюдать алогичную (противоречащую логике) связь. Поведение обоих рабочих можно считать логичным только по их личным соображениям. Причем Иванов как был грязным, так и будет ходить, а Иванов, будучи чистым, умоется лишний раз:). Но это, так сказать, крайний случай.
Вероятность — замена незнанию
На самом деле, теорию вероятностей и сопутствующие направления в вычислениях обычно связывают с ситуациями, где знания человека ограничены. Допустим, игральные кости, вроде бы считаются игрой недетерминируемого типа (то есть заранее непредсказуемого). На самом деле это не так. Достаточно… только не смейтесь… учесть первоначальное расположение кубиков перед броском, рассчитать траекторию полета, скорость и углы вращения и так далее. То есть, на самом деле, вычислить все можно и математически. Но это подразумевает довольно громоздкую модель расчетов, хотя и самую правильную на самом деле.
С использованием вероятностной логики мы можем только примерно предсказать результат, и то, в рамках игральных костей — с небольшими процентами этой самой вероятности. Вместе с тем, это ближе к нашей природе восприятия.
Булевы переменные в большинстве случаев при программировании используются как обычные флаги, а в некоторых языках программирования такой тип данных как bool и вовсе упразднен, за исключением стандартных логических операций. Дело в том, что выразить «да»/«нет» вполне возможно различными способами, а между утверждениями истины и лжи может быть большой диапазон промежуточных значений, что активно применяется в недетерминированной логике.
Максимум входящих, минимум исходящих
Мы довольно часто сталкиваемся с ситуациями, в которых задачи имеют не одно, а множество решений. Мало того, поскольку само программирование зачастую производится по месту и исходя из реалий, алгоритмы приходится изобретать или модифицировать самостоятельно. Например, довольно часто встречается ситуация, когда на базе множества наблюдений строится некое общее описание процесса. При этом, если это общее описание поместить в отдельный алгоритм, то исходя из него мы не получим конкретные наблюдения, которые были раньше, а будем оперировать уже неким виртуальным массивом решений, часть из которых также нужно будет отсекать, и так далее. Это основная проблема трансформации: «наблюдения —> обобщающее правило, обобщающее правило —> результаты на его базе».
Чтобы было более понятно, приведем пример. Итак, наблюдения:
. Персонаж пришел с юга и двинулся на север.
. Персонаж пришел с запада и двинулся на север.
. Персонаж пришел с востока и двинулся на север.
На базе этих наблюдений выводим обобщающее правило: «Откуда бы персонаж ни пришел, он все время двигается на север».
Теперь «переворачиваем» алгоритм и пытаемся на базе только что созданного обобщающего правила ответить на вопрос: «Персонаж двигается на север, откуда он пришел?». И вот тут как раз таки и проявляется основная проблема алгоритмов, основанных на наблюдениях, потому как мы ответим: «Откуда угодно» или же просто: «Неизвестно». Мы ведь обобщили.
Поэтому нам нужно улучшать алгоритм. Каким образом? Мы должны отслеживать ситуацию и выставлять весовые коэффициенты. Например, для простоты: . 30 персонажей пришли с юга и двинулись на север.
. 20 персонажей пришли с запада и двинулись на север.
. 50 персонажей пришли с востока и двинулись на север.
В итоге, оперируем уже большим количеством входящих данных, которые являются по существу наблюдениями. Числовые данные для каждого из случаев мы вводим в сам алгоритм, а на поставленный вопрос: «Персонаж двигается на север, откуда он пришел?» отвечаем, что:
. 50% — он пришел с востока.
. 30% — с юга.
. 20% — с запада.
При этом на вопрос: «А если более конкретно?», конечно же, выберем вариант: «с востока», хотя, как вы понимаете, ошибемся в 50 случаях из 100. Этот вариант довольно прост.
Задача на формулу Байеса
Видоизменим нашу первоначальную задачу.
На север движется человек. Какова вероятность того, что он пришел с востока, если известно, что на север поворачивает каждый четвертый, идущий с юга, каждый пятый, идущий с запада и каждый второй, идущий с востока?
Решение
Для начала преобразуем задание в более понятный вид, вероятности поворота на север для идущего с юга (p1) = 0.25, запада (p2) = 0.2 и востока (p3) =0.5.
Для начала вспомним формулу Бейеса, в нашем случае она будет иметь вид:
P(H3|A)= P(H3)*P(А|H3)/(P(H1)*P(А|H1)+ P(H2)*P(А|H2)+ P(H3)*P(А|H3));
В этой формуле Н1, Н2, Н3 – гипотезы, что на север идет персонаж с юга, запада или востока соответственно. На самом деле, эти гипотезы равновероятны и их вероятность равна 1/3.
P(H3|A) – вероятность того, что мы говорим о человеке с востока при условии, что он уже повернул на север (событие А).
Вероятности того, что это может быть персонаж с юга, запада или востока до того как он повернул на север, соответственно равны:
P(А|H1)=p1*q2*q3=0,25*0,8*0,5=0,1;
P(А|H2)=q1*p2*q3=0,75*0,2*0,5=0,075;
P(А|H3)=q1*q2*p3=0,75*0,8*0,5=0,3;
Здесь q1 = 0,75; q2 = 0,8; q3 = 0,5 – вероятности того, что этот персонаж точно не с юга (q1), не с запада (q2) и не с востока (q3), рассчитаны как q = 1 – p, где р – вероятности попадания для каждого из стрелков.
Подставим эти значения в формулу Бейеса:
P(H3|A)=0,3/0,475=0,63.
Фильтрация спама по Байесу
Да, преподобный Томас Байес, живший еще в 18 веке, оказал довольно сильное влияние на нынешние технологии. Причем, что интересно, его теоремой не пользовались активно вплоть до 90-х годов прошлого столетия.
Итак, как же Байес нам помогает бороться со спамом. В рамках ключевого алгоритма используется формула Байеса, и давайте рассмотрим то, что в нее включено. Допустим, у нас имеется письмо со словом «распродажа», которое очень часто присутствует в рекламных рассылках…
Pr(S|W)= Pr(W|S)*Pr(S)/(Pr(W|S)*Pr(S)+Pr(W|H)*Pr(H));
Pr(S|W) — условная вероятность того, что сообщение является спамом, при условии, что слово «распродажа» находится в нем;
Pr(S) — полная вероятность того, что произвольное сообщение является спамом;
Pr(W|S) — условная вероятность того, что слово «распродажа» появляется в сообщениях, если они являются спамом;
Pr(H) — полная вероятность того, что произвольное сообщение не является спамом;
Pr(W|H)— условная вероятность того, что слово «распродажа» появляется в сообщениях, если они не являются спамом.
При этом стоит указать, что вероятность того, что письмо является спамом Pr(S) во множестве байесовских систем по умолчанию принимается равным 0,5, соответственно и Pr(H)=0,5, и наша формула преобразуется в:
Pr(S|W)= Pr(W|S)/(Pr(W|S)+Pr(W|H));
В дальнейшем предусматриваются некоторые усовершенствования, причем сама формула Байеса применяется обычно не к одному слову в сообщении, а к нескольким.
Вообще, мы продолжим эту интереснейшую тему в следующем материале серии, как затронем и ряд сопутствующих.
Кристофер http:/itcs.3dn.ru
Причем стоит обратить внимание на то, что есть специализированные языки для ИИ (наиболее легкий в освоении для нынешних поколений — Visual Prolog), но в ряде случаев на практике они не используются. Вместо них применяют те же C/C++ или Lua.
В прошлом материале серии мы продемонстрировали классическую задачу алогичности с двумя рабочими. Напомню вкратце: два рабочих, Иванов и Петров, вышли из подвала, где делали починку оборудования. У Иванова лицо запылилось, у Петрова — нет. Вопрос: кто решит пойти умываться в первую очередь? Ответ: Петров, поскольку он посмотрит на Иванова и решит, что он тоже загрязнился. Сама задача абстрагирована, но при этом мы можем наглядно наблюдать алогичную (противоречащую логике) связь. Поведение обоих рабочих можно считать логичным только по их личным соображениям. Причем Иванов как был грязным, так и будет ходить, а Иванов, будучи чистым, умоется лишний раз:). Но это, так сказать, крайний случай.
Вероятность — замена незнанию
На самом деле, теорию вероятностей и сопутствующие направления в вычислениях обычно связывают с ситуациями, где знания человека ограничены. Допустим, игральные кости, вроде бы считаются игрой недетерминируемого типа (то есть заранее непредсказуемого). На самом деле это не так. Достаточно… только не смейтесь… учесть первоначальное расположение кубиков перед броском, рассчитать траекторию полета, скорость и углы вращения и так далее. То есть, на самом деле, вычислить все можно и математически. Но это подразумевает довольно громоздкую модель расчетов, хотя и самую правильную на самом деле.
С использованием вероятностной логики мы можем только примерно предсказать результат, и то, в рамках игральных костей — с небольшими процентами этой самой вероятности. Вместе с тем, это ближе к нашей природе восприятия.
Булевы переменные в большинстве случаев при программировании используются как обычные флаги, а в некоторых языках программирования такой тип данных как bool и вовсе упразднен, за исключением стандартных логических операций. Дело в том, что выразить «да»/«нет» вполне возможно различными способами, а между утверждениями истины и лжи может быть большой диапазон промежуточных значений, что активно применяется в недетерминированной логике.
Максимум входящих, минимум исходящих
Мы довольно часто сталкиваемся с ситуациями, в которых задачи имеют не одно, а множество решений. Мало того, поскольку само программирование зачастую производится по месту и исходя из реалий, алгоритмы приходится изобретать или модифицировать самостоятельно. Например, довольно часто встречается ситуация, когда на базе множества наблюдений строится некое общее описание процесса. При этом, если это общее описание поместить в отдельный алгоритм, то исходя из него мы не получим конкретные наблюдения, которые были раньше, а будем оперировать уже неким виртуальным массивом решений, часть из которых также нужно будет отсекать, и так далее. Это основная проблема трансформации: «наблюдения —> обобщающее правило, обобщающее правило —> результаты на его базе».
Чтобы было более понятно, приведем пример. Итак, наблюдения:
. Персонаж пришел с юга и двинулся на север.
. Персонаж пришел с запада и двинулся на север.
. Персонаж пришел с востока и двинулся на север.
На базе этих наблюдений выводим обобщающее правило: «Откуда бы персонаж ни пришел, он все время двигается на север».
Теперь «переворачиваем» алгоритм и пытаемся на базе только что созданного обобщающего правила ответить на вопрос: «Персонаж двигается на север, откуда он пришел?». И вот тут как раз таки и проявляется основная проблема алгоритмов, основанных на наблюдениях, потому как мы ответим: «Откуда угодно» или же просто: «Неизвестно». Мы ведь обобщили.
Поэтому нам нужно улучшать алгоритм. Каким образом? Мы должны отслеживать ситуацию и выставлять весовые коэффициенты. Например, для простоты: . 30 персонажей пришли с юга и двинулись на север.
. 20 персонажей пришли с запада и двинулись на север.
. 50 персонажей пришли с востока и двинулись на север.
В итоге, оперируем уже большим количеством входящих данных, которые являются по существу наблюдениями. Числовые данные для каждого из случаев мы вводим в сам алгоритм, а на поставленный вопрос: «Персонаж двигается на север, откуда он пришел?» отвечаем, что:
. 50% — он пришел с востока.
. 30% — с юга.
. 20% — с запада.
При этом на вопрос: «А если более конкретно?», конечно же, выберем вариант: «с востока», хотя, как вы понимаете, ошибемся в 50 случаях из 100. Этот вариант довольно прост.
Задача на формулу Байеса
Видоизменим нашу первоначальную задачу.
На север движется человек. Какова вероятность того, что он пришел с востока, если известно, что на север поворачивает каждый четвертый, идущий с юга, каждый пятый, идущий с запада и каждый второй, идущий с востока?
Решение
Для начала преобразуем задание в более понятный вид, вероятности поворота на север для идущего с юга (p1) = 0.25, запада (p2) = 0.2 и востока (p3) =0.5.
Для начала вспомним формулу Бейеса, в нашем случае она будет иметь вид:
P(H3|A)= P(H3)*P(А|H3)/(P(H1)*P(А|H1)+ P(H2)*P(А|H2)+ P(H3)*P(А|H3));
В этой формуле Н1, Н2, Н3 – гипотезы, что на север идет персонаж с юга, запада или востока соответственно. На самом деле, эти гипотезы равновероятны и их вероятность равна 1/3.
P(H3|A) – вероятность того, что мы говорим о человеке с востока при условии, что он уже повернул на север (событие А).
Вероятности того, что это может быть персонаж с юга, запада или востока до того как он повернул на север, соответственно равны:
P(А|H1)=p1*q2*q3=0,25*0,8*0,5=0,1;
P(А|H2)=q1*p2*q3=0,75*0,2*0,5=0,075;
P(А|H3)=q1*q2*p3=0,75*0,8*0,5=0,3;
Здесь q1 = 0,75; q2 = 0,8; q3 = 0,5 – вероятности того, что этот персонаж точно не с юга (q1), не с запада (q2) и не с востока (q3), рассчитаны как q = 1 – p, где р – вероятности попадания для каждого из стрелков.
Подставим эти значения в формулу Бейеса:
P(H3|A)=0,3/0,475=0,63.
Фильтрация спама по Байесу
Да, преподобный Томас Байес, живший еще в 18 веке, оказал довольно сильное влияние на нынешние технологии. Причем, что интересно, его теоремой не пользовались активно вплоть до 90-х годов прошлого столетия.
Итак, как же Байес нам помогает бороться со спамом. В рамках ключевого алгоритма используется формула Байеса, и давайте рассмотрим то, что в нее включено. Допустим, у нас имеется письмо со словом «распродажа», которое очень часто присутствует в рекламных рассылках…
Pr(S|W)= Pr(W|S)*Pr(S)/(Pr(W|S)*Pr(S)+Pr(W|H)*Pr(H));
Pr(S|W) — условная вероятность того, что сообщение является спамом, при условии, что слово «распродажа» находится в нем;
Pr(S) — полная вероятность того, что произвольное сообщение является спамом;
Pr(W|S) — условная вероятность того, что слово «распродажа» появляется в сообщениях, если они являются спамом;
Pr(H) — полная вероятность того, что произвольное сообщение не является спамом;
Pr(W|H)— условная вероятность того, что слово «распродажа» появляется в сообщениях, если они не являются спамом.
При этом стоит указать, что вероятность того, что письмо является спамом Pr(S) во множестве байесовских систем по умолчанию принимается равным 0,5, соответственно и Pr(H)=0,5, и наша формула преобразуется в:
Pr(S|W)= Pr(W|S)/(Pr(W|S)+Pr(W|H));
В дальнейшем предусматриваются некоторые усовершенствования, причем сама формула Байеса применяется обычно не к одному слову в сообщении, а к нескольким.
Вообще, мы продолжим эту интереснейшую тему в следующем материале серии, как затронем и ряд сопутствующих.
Кристофер http:/itcs.3dn.ru
Компьютерная газета. Статья была опубликована в номере 45 за 2010 год в рубрике технологии
