Министерство образования и науки российской федерации федеральное агентство по образованию санктпетербургский государственный университет
 Скачать 1.41 Mb.
|
|
N 2,1 = 1; N 2,2 = 1; N 2,3 = 1; N 2,4 = 1; N 3,1 = 2. Исходя из имеющихся данных мы можем заключить (будем обозначать резолюции r1, r2 и т.д.): r1: M 1,5 \/ M 2,5 r2: M 1,5 \/ M 2,5 \/ M 3,3 \/ M 3,4 \/ M 3,5 r3: M 3,2 r4: M 3,2 \/ M 3,3 r5: M 3,2 \/ M 3,3 \/ M 3,4 r6: (M 3,2 & M 4,2 ) \/ (M 4,1 & M 4,2 ) \/ (M 3,2 \/ M 4,1 ) Можно заметить, что данные выражения некорректны с точки зрения булевой алгебры. Из r1 можно заключить, что мина находится либо в (1,5), либо в (2,5), либо в обеих клетках. В данной нотации используются т.н. хорновские выражения, где дизъюнкциями объединяются литералы, из которых один и только один является истинным. К данным резолюциям может быть применено правило поглощения: A & (A \/ B) = A Применяя его к резолюциям r3, r4 и r5 получим M 3,2 = 1, а значит, M 3,3 = 0, M 3,4 = 0. Таким образом, мы можем сделать первый логический вывод о том, что в клетке (3,2) находится мина, а в клетках (3,3) и (3,4) их нет. Добавим эти факт в базу знаний о минном поле, отметим мину флажком и откроем клетки (3,3) и (3,4). 47 Напишем хорновские выражения для полученной ситуации: r1: M 1,5 \/ M 2,5 r2: M 1,5 \/ M 2,5 \/ M 3,5 r3: M 2,5 \/ M 3,5 \/ M 4,3 \/ M 4,4 \/ M 4,5 r4: M 4,2 \/ M 4,1 r5: M 4,2 \/ M 4,3 \/ M 4,4 Применяя правило поглощения к выражениям r1, r2, r3, получим: (M 1,5 \/M 2,5 ) & (M 1,5 \/M 2,5 \/M 3,5 ) = (M 1,5 \/ M 2,5 ), следовательно, M 3,5 = 0, и мы можем открыть клетку (3,5). После открытия клетки (3,5), а затем и (2,5), получаем следующую картину. r1: M 1,6 \/ M 2,6 \/ M 3,6 r2: M 2,6 \/ M 3,6 \/ M 4,4 \/ M 4,5 \/ M 4,6 r3: M 4,3 \/ M 4,4 \/ M 4,5 r4: M 4,2 \/ M 4,1 r5: M 4,2 \/ M 4,3 \/ M 4,4 Применить правило поглощения здесь невозможно, а значит, однозначный вывод о том, какую клетку открыть, сделать невозможно в силу неопределенности ситуации. Но это не значит, что мы не можем минимизировать риски, располагая данной информацией. 48 4. Вероятностные рассуждения 4.1. Нечеткая логика Ранее мы рассматривали рассуждения на основе булевой логики, когда любая переменная либо истинна, либо ложна. Между тем, далеко не всегда мы располагаем полной информацией об истинности или ложности переменных, но имеем данные о степени их достоверности. Правила для вычисления достоверности сложных высказываний Т следующие: T(A /\ B) = min(T(A), T(B)) T(A \/ B) = max(T(A), T(B)) T(¬A) = 1 – T(A) Продолжая рассмотрение игры «Сапер», будем считать, что мины разбросаны по полю равномерно. Тогда приведенные выше хорновские выражения r1, …, r5 означают, что мина находится достоверно в одной из клеток, т.е. вероятность нахождения мины в одной из клеток равна сумме равных вероятностей для каждой из клеток и равна единице: r1: p 1,6 + p 2,6 + p 3,6 = 1; p 1,6 = p 2,6 = p 3,6 = 1/3 r2: p 2,6 + p 3,6 + p 4,4 + p 4,5 + p 4,6 = 1; p 2,6 = p 3,6 = p 4,4 = p 4,5 = p 4,6 = 1/5 r3: p 4,3 + p 4,4 + p 4,5 = 1; p 4,3 = p 4,4 = p 4,5 = 1/3 r4: p 4,2 + p 4,1 = 1; p 4,2 = p 4,1 = 1/2 r5: p 4,2 + p 4,3 + p 4,4 = 1; p 4,2 = p 4,3 = p 4,4 = 1/3 Поскольку нашей задачей на данном этапе является не постановка флажка (это мы делаем только когда достоверно знаем, что там мина), а открытие клеток без мины, то нам удобнее рассматривать вероятности того, что в клетке мины нет. Обозначим соответствующие вероятности буквой q. Тогда q 1,6 = q 2,6 = q 3,6 = 1- 1/3 = 2/3 q 2,6 = q 3,6 = q 4,4 = q 4,5 = q 4,6 = 1 - 1/5 = 4/5 q 4,3 = q 4,4 = q 4,5 = 1 = 1/3 = 2/3 q 4,2 = q 4,1 = 1 – 1/2 = 1/2 q 4,2 = q 4,3 = q 4,4 = 1 - 1/3 = 2/3 В связи с тем, что резолюции r1,…,r5 объединены конъюнкцией, то вероятность отсутствия мины в каждой из клеток вычисляется как минимум вероятностей из каждой резолюции. Тогда получим итоговую вероятность для каждой клетки Q: Q 1,6 = 2/3; Q 2,6 = 2/3; Q 3,6 = 2/3; Q 4,1 = 1/2; Q 4,2 = 1/2; Q 4,3 = 2/3; Q 4,4 = 2/3; Q 4,5 = 2/3; Q 4,6 = 4/5. Таким образом, не располагая достоверной информацией о том, где находятся мины, мы, тем не менее, можем утверждать, что выше всего вероятность отсутствия мины в клетке (4,6) – 4/5 против 1/2 и 2/3 в остальных рассматриваемых клетках – кандидатах. Отсюда следует не вполне очевидный вывод, что безопаснее открывать клетку (4,6). 49 Замечание. Если известно общее число мин, то этот факт может внести существенные коррективы в рассмотренную выше логику поиска. Если, например, известно, что число мин в 10 раз меньше общего числа клеток поля, т.е. вероятность нахождения мины в любой клетке, о которой нам ничего неизвестно, равна 1/10, что существенно ниже, чем в любой из рассмотренных клеток-кандидатов. Следовательно, следует открыть скорее совершенно неизвестную клетку, чем любую из соседних. Так, если мы открыли клетку в середине поля, и у нее есть один сосед с миной, то лучше поискать свободную от мин клетку где-нибудь в стороне, чем в соседних клетках, где вероятность напороться на мину равна 1/8. 4.2. Байесовские сети Рассмотрим простой пример, близкий всем студентам. Чтобы сдать (Pass) экзамен, нужно подготовиться к нему (Study) или воспользоваться шпаргалкой (Cheat). Таким образом, имеется 3 булевых переменных. Хочется узнать вероятность успешно сдать экзамен. В тех случаях, когда известны вероятности элементарных (атомарных) событий, можно воспользоваться методом вероятностного вывода на основе полного совместного распределения, которое описывается таблицей размерностью 2х2х2. Study ¬Study Cheat ¬Cheat Cheat ¬Cheat Pass 0,15 0,4 0,04 0,06 ¬Pass 0,01 0,04 0,05 0,25 Сумма всех вероятностей равна единице. В каждой клетке вероятность наступления элементарного события. Эта вероятность является результирующей, т.е. учитывает в себе все факторы. Так, вероятность успешной сдачи экзамена 0,4 учитывает вероятность подготовки к экзамену и вероятность того, что студент не воспользовался шпаргалкой. Вероятности сложных событий легко вычисляются суммированием соответствующих строк или столбцов таблицы. Вероятность подготовки к экзамену равна сумме клеток левой половины таблицы и соответствует событиям (учил, не пользовался шпаргалкой и сдал; учил, пользовался и сдал; учил, пользовался и не сдал; учил, не пользовался и не сдал): P(Study) = 0,15 + 0,4 + 0,01+ 0,04 = 0,6 Вероятность воспользоваться шпаргалкой равна сумме первого и третьего столбцов: P(Cheat) = 0,15 + 0,01 + 0,04 + 0,05 = 0,25 50 Вероятность сдачи экзамена равна сумме клеток первой строки (учил, пользовался и сдал; учил, не пользовался и сдал; не учил, пользовался и сдал; не учил, не пользовался и сдал): P(Pass) = 0,15 + 0,4 + 0,04 + 0,06 = 0,65 Метод вероятностного вывода на основе полного совместного распределения является скорее хорошей иллюстрацией принципа формирования вероятностей, чем практическим пособием, поскольку вероятности элементарных событий известны далеко не всегда. Чаще делают допущения о равной вероятности этих событий. Обычно можно оценить вероятности истинности отдельных переменных. Пусть P(Study) = 0,6 (в 40% случаев будут более важные дела, чем подготовка к экзамену), а P(Cheat) = 0,25 (один шанс из четырех воспользоваться шпаргалкой). Эти вероятности называются априорными или безусловными. Они представляют собой степень уверенности в истинности высказывания в отсутствии других данных. На первый взгляд, вероятность сдачи экзамена равна 0,6 + 0,25 = 0,85. На самом деле все сложнее. События Study и Cheat могут перекрываться, т.е. происходить совместно. Можно выучить материал и при этом для страховки воспользоваться шпаргалкой. Можно также все выучить, но не сдать (профессор придрался). Можно сдать без подготовки и шпаргалок (просто повезло). Для нахождения искомой вероятности необходимо располагать условными вероятностями, например, P(Pass|Study) – вероятность сдачи экзамена при условии полной подготовки. В общем случае вероятность события А равна P(A) = ∑ P(A|B i ) P(B i ) i где P(B i ) – априорная вероятность события B i , P(A|B i ) – условная вероятность события А при условии истинности события B i . Условная вероятность связывает зависимые события. Если мы введем четвертую переменную – солнечную погоду (Sunny), то должны задавать условные вероятности типа P(A | Sunny). В реальных ситуациях мы можем столкнуться с тем, что размерность задачи будет из-за этого непомерно велика. Для решения этой проблемы используются байесовские сети, которые позволяют установить зависимость переменных и упростить вычисление полного совместного распределения. Ниже приведена байесовская сеть для рассмотренного примера. Обратим внимание, что в нашей модели переменные Study и Cheat являются независимыми. Возможна другая модель, когда пользование шпаргалкой обусловлено отсутствием подготовки к экзамену. Она будет рассмотрена позже. Cheat Pass Study 51 Каждая вершина сети соответствует случайной переменной. Вершины соединяются направленными ребрами. Если стрелка направлена от A к В, то А называется родительской вершиной вершины В. Каждая вершина X i характеризуется распределением условных вероятностей P(X i | Parents(X i )), которое количественно оценивает влияние на вершину ее родительских вершин. В нашем примере считаем известными следующие условные вероятности: вероятность сдать экзамен при условии подготовки и подстраховки шпаргалками равна единице; при подготовке и не пользовании шпаргалкой – 0,889; при условии пользования шпаргалкой без подготовки к экзамену – 0,4; а вероятность сдать экзамен без подготовки и шпаргалки – 0,2 (просто повезло). Основной выигрыш при использовании байесовских сетей заключается в том, что вероятность любого состояния только на основе родительских (ближайших) вершин, а не всех вершин, от которых эта вершина зависит: P(X i | X i-1 , X i-2 , …, X 1 ) = P(X i | Parents(X i )) В нашем примере мы имеем вершину Study, которая на самом деле может быть конечным результатом связанных событий: студент посещал лекции, имел конспект, у него был доступ к компьютеру, он располагал временем, и т.п. Как результат этих событий мы имеем факт подготовки к экзамену. Событие использование шпаргалки также является следствием целого ряда событий, вероятностями которых необходимо располагать: наличие времени, технических средств, подобающая одежда для скрытного использования шпаргалки. Для вычисления полного совместного распределения нужно знать все условные вероятности, например, вероятность наличия радиопередатчика при условии посещения лекций. Нам же для вычисления вероятности сдачи экзамена достаточно знать вероятности P(Study) и P(Cheat). Приведенное выше правило называется цепным правилом. Следуя этому правилу достаточно просто вычислить вероятности событий, последовательно продвигаясь в направлении стрелок. В данном примере мы можем вычислить вероятность сдачи экзамена: P(Pass) = P(Pass | Study, Cheat) * P(Study) * P(Cheat) + + P(Pass | Study, ¬Cheat) *P(Study) * P(¬Cheat) + + P(Pass | ¬Study, Cheat) * P(¬Study) * P(Cheat) + +P(Pass | ¬Study, ¬Cheat) * P(¬Study) * P(¬Cheat) = = 1,0 * 0,6 * 0,25 + 0,889 * 0,6 * 0,75 + 0,4 * 0,4 * 0,25 + 0,2 * 0,4 * 0,75 = 0,65 В нашем сильно упрощенном примере этот выигрыш в сложности вычислений незаметен, поскольку цепочка байесовской сети не такая длинная. Второй фактор – независимость переменных Study и Cheat. Опытные студенты могут заметить некоторое неправдоподобие вероятностей: при условии Cheat Pass Study P(Study) 0,6 Study Cheat P(Pass) 1 1 1,0 1 0 0,889 0 1 0,4 0 0 0,2 P(Cheat) 0,25 52 подготовки к экзамену шпаргалка лишь добавляет риск быть пойманным и выгнанным с экзамена. Изменим логику следующим образом. Будем считать, что пытаться воспользоваться шпаргалкой студент будет, только если не подготовится к экзамену. Байесовская сеть изменится так, как показано ниже. Условная вероятность воспользоваться шпаргалкой равна нулю в случае подготовки к экзамену и 0,75 при отсутствии подготовки. Вероятность P(Pass | Study, Cheat) = 0. Вычислим P(Cheat) и P(¬Cheat): P(Cheat) = P(Cheat | ¬Study) * P(¬Study) = 0,75 *(1-0,6) = 0,3 P(¬Cheat) = 1-P(Cheat) = 0,7 Теперь, используя цепное правило, мы можем вычислить вероятность успешной сдачи экзамена: P(Pass) = P(Pass|Study,¬Cheat) * P(Study) * P(¬Cheat) + P(Pass | ¬Study, Cheat) * P(¬Study) * P(Cheat) + P(Pass|¬Study, ¬Cheat) * P(¬Study) * P(¬Cheat) = 0,889 * 0,6 * 0,7 + 0,7 * 0,4 * 0,3 + 0,2 * 0,4 * 0,7 = 0,513 Байесовские сети позволяют решать и обратные задачи. Например, известно, что студент экзамен сдал успешно. Требуется найти вероятность того, что он был к экзамену подготовлен. Для этого надо воспользоваться правилом Байеса: P(A | B) = P(B | A) * P(A) / P(B) В нашем случае вероятность сдачи экзамена, который был успешно сдан, P(Pass) = 0,513; вероятность сдачи экзамена при подготовке к нему P(Pass | Study, ¬Cheat) = 0,889; вероятность подготовки и не пользования шпаргалкой P(Study, ¬Cheat) = 0,6 * 0,7 = 0,42, следовательно, P(Study, ¬Cheat | Pass) = P(Pass | Study, ¬Cheat) * P(Study, ¬Cheat) / P(Pass) = = 0,889* 0,6 * 0,7 / 0,513 = 0,727 Найдем теперь вероятность того, что экзамен сдан с помощью шпаргалки: P(¬Study, Cheat | Pass) = P(Pass | ¬Study, Cheat) * P(¬Study, Cheat) / P(Pass) = = 0,7 * 0,4* 0,3 * / 0,513 = 0,164 И, наконец, вероятность того, что причиной сдачи экзамена было чистое везение: P(¬Study,¬Cheat | Pass) = P(Pass | ¬Study,¬Cheat) * P(¬Study, ¬Cheat) / P(Pass) = 0,2 * 0,4 * 0,7 / 0,513 = 0,109 Таким образом, байесовские сети обеспечивают декомпозицию сложных задач и при этом избавляют от необходимости задавать множество условных вероятностей. Cheat Pass Study Study Cheat P(Pass) 1 1 0 1 0 0,889 0 1 0,7 0 0 0,2 P(Study) 0,6 Study P(Cheat) 1 0,0 0 0,75 53 4.3. Иллюстрация: Парадокс Монти Холл Для иллюстрации применения правила Байеса рассмотрим следующую задачу, получившую в литературе название парадокса Монти Холл. Пусть Вы участвуете в телевизионной игре, в ходе которой Вам надо сделать выбор одной из трех дверей. За одной из них стоит автомобиль, за двумя другими – козы. Предположим, Вы указали на дверь №1. Ведущий открывает другую дверь, пусть это будет дверь №3, за которой обнаруживается коза, и предлагает Вам, пока не поздно, передумать и открыть дверь №2. Вопрос: имеет ли смысл прислушаться к мнению ведущего и открыть дверь номер два? На первый взгляд, вероятности того, что машина находится за одной из оставшихся дверей равны P(С 1 ) = P(С 2 ) = ½, и менять решение бессмысленно. Однако, при внимательном подходе мы можем извлечь полезную информацию из факта открытии ведущим именно двери №3. Пусть априорные вероятности того, что машина находится за дверью №1, №2 и №3 P(С 1 ) = P(С 2 ) = P(С 3 ) = 1/3. Найдем вероятности того, что ведущий откроет дверь №2 и №3 (дверь №1 он открыть не может, поскольку мы на нее уже указали). Если машина находится за дверью №1, то условные вероятности того, что он откроет двери №2 и №3: P(D = 2 | C 1 ) = 0,5 ; P(D = 3 | C 1 ) = 0,5 То есть, ведущему все равно, какую из оставшихся дверей открыть. Если же машина находится за дверью №2, то вероятности того, что он откроет двери №2 и №3: P(D = 2 | C 2 ) = 0 ; P(D = 3 | C 2 ) = 1 Поскольку машина стоит за второй дверью, то открыть эту дверь ведущий не может, а с вероятностью 1 откроет третью дверь. И наоборот, если машина стоит за третьей дверью, то соответствующие вероятности: P(D = 2 | C 3 ) = 1 ; P(D = 3 | C 3 ) = 0 Итак, мы располагаем вероятностями того, какую дверь откроет ведущий в зависимости от того, где стоит автомобиль. Чтобы найти обратную условную вероятность, воспользуемся правилом Байеса. Поскольку известно, что D = 3, то P(C i | D = 3) = P(D = 3 | C i ) * P(C i ) / P(D=3) Подставляя в эту формулу C 1 и C 2 , получаем: P(C 1 | D = 3) = P(D = 3 | C 1 ) * P(C 1 ) / P(D=3) = ½ * 1/3 / 1/2 = 1/3. P(C 2 | D = 3) = P(D = 3 | C 2 ) * P(C 2 ) / P(D=3) = 1 * 1/3 / 1/2 = 2/3. Таким образом, вероятность того, что машина находится за второй дверью, в два раза выше! Вывод, полученный «на кончике пера», может быть подкреплен и логическими рассуждениями: Если машина стоит за первой дверью, которую мы уже выбрали, то ведущему все равно, какую из оставшихся дверей выбрать. Если же машина за второй дверью, то у ведущего нет выбора, кроме двери №3. Сменив выбор, мы в худшем случае остаемся при тех же шансах, а в лучшем — получаем машину. 54 4.4. Обучение на основе наблюдений Рассмотренные в предыдущем разделе примеры могут вызвать резонный вопрос: а как пользоваться этими замечательными инструментами в реальной жизни? Откуда взять все эти вероятности? Математики обходят это вопрос достаточно просто. Все рассуждения начинаются словами: пусть вероятность события А равна Х. Таким образом, математики делают то, что можно могут, так, как нужно. Инженеру же приходится делать то, что нужно, так, как можно. Если не брать идеальные примеры, такие, как бросание игральных костей или раздача колоды карт, то найти вероятности можно только на основе наблюдений. В нашем примере с экзаменом источником информации может стать только exit poll, т.е. анонимный опрос на выходе с экзамена. Результаты этого опроса могут выглядеть следующим образом: № п/п Study Cheat Pass 1 Yes No Yes 2 No Yes Yes 3 Yes No Yes 4 Yes No No 5 No Yes No 6 No No No 7 Yes No Yes 8 No Yes No 9 Yes No Yes 10 No No Yes Из этой выборки можно вычислить вероятность сдачи экзамена, которая равна отношению количества успешно сдавших к общему числу сдававших P(Pass) = 6 / 10 = 0,6. Аналогично получим вероятность подготовки P(Study) = 5 / 10 = 0,5 и пользования шпаргалкой P(Cheat) = 3 / 10 = 0,3. Таким же образом мы может получить условные вероятности P(Pass | Study) = 3 / 5 = 0,6 (отношение количества сдавших экзамен из тех, кто к нему готовился, к общему числу готовившихся к экзамену) и P(Pass | Cheat) = 1 / 3. Распределение удобно отобразить в виде дерева (рис.4.1): 55 Рис.4.1. Дерево наблюдений Здесь, как и в рассмотренных ранее задачах поиска, желательно сформировать дерево минимальной глубины. В этой связи необходимо вначале задействовать наиболее важные, т.е. наиболее информативные атрибуты поиска. Одним из подходящих критериев для выбора атрибута является объем информации, содержащийся в ответе. Количество информации вычисляется по формуле Шеннона. Если возможные ответы v i имеют вероятности p(v i ), то информационное содержание фактического ответа I, измеренное в битах, равно I(p(v 1 ), p(v 2 ), … , p(v n ) = -∑ p(v i ) log 2 p(v i ) i Вычислим количество информации в ответе о подготовке к экзамену: I(p(Study), p(¬Study)) = - 5/10 * log 2 5/10 - 5/10 * log 2 5/10 = 1 бит Количество информации в ответе о шпаргалке: I(p(Cheat), p(¬Cheat)) = - 3/10 * log 2 3/10 -7/10 * log 2 7/10 = 1,533 бит Таким образом, ответ о шпаргалке в полтора раза более информативен, и в дереве поиска его следовало бы поставить раньше. Другая проблема – достаточность информации в обучающей выборке. Приведенный выше пример дает весьма грубую оценку. Реальные вероятности могут существенно отличаться. Другая крайность – большой объем выборки, соизмеримый с генеральной совокупностью. Если мы устроим exit poll для всех студентов поголовно, то мы получим исчерпывающий ответ на все вопросы и в моделях уже нуждаться не будем. Полезность использования моделей достигается тогда, когда на небольшой выборке мы можем сделать вывод о всей генеральной совокупности. Например, узнав, что 10% студентов сдают экзамен с помощью шпаргалок, можно изменить формат экзамена, например, Yes Yes Yes Yes No N o No No Pass? Pass? Pass Pass? Yes No Yes Yes No No 1 0 3 2 5 5 5 0 1 2 1 Study? Cheat? Cheat? 1 0 4 0 56 разрешить пользоваться любыми источниками, но усложнить вопросы. Одним из способов оценки достаточности выборки является постепенное добавление данных в первоначальную таблицу опроса со сравнением изменения вероятностей в каждой новой итерации. Как только изменение результатов станет меньше допустимой погрешности, обучение можно считать законченным. |