Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 176
Текст из файла (страница 176)
На основании приведенного выше примера можно составить общую процедуру вероятностного вывода. Мы будем придерживаться того случая, в котором запрос касается только одной переменной. Кроме того, потребуются некоторые обозначения: допустим, что Х вЂ” переменная запроса (в данном примере Саух су); Š— множество переменных свидетельства (в данном примере к нему относится только тоогпас)зе); е — наблюдаемые значения этих переменных; х — оставшиеся ненаблюдаемые переменные (в данном примере таковой является только сагой). запросом является Р (х ~ е ), и ответ на него может быть вычислен следующим образом: б41 Глава 13.
Неопределенность Р(Х)е) = а Р(Х,е) = а ~) Р(Х,е,у) (23.6) где суммирование осуществляется по всем возможным значениям у (т.е. по всем возможным комбинациям значений ненаблюдаемых переменных х). Обратите внимание на то, что переменные Х, е и у, вместе взятые, составляют полное множество переменных для данной проблемной области, поэтому Р (х, е, у) представляет собой подмножество вероятностей из полного совместного распределения.
Алгоритм вычисления ответа на запрос приведен в листинге 13.2. В этом алгоритме проверяются в циклах значения Хи значения у для перебора всех возможных атомарных событий с фиксированными значениями е, складываются их вероятности из таблицы совместного распределения, после чего результаты нормализуются.
Листинг 13.2. Алгоритм вероятностного вывода путем перебора всех элементов в таблице полного совместного распределения Випсввоп Епитегасе-повис-Азх(Х, е, Р) гевигпз распределение по Х Ьпривн: Х, переменная запроса е, наблюдаемые значения переменных Е Р, совместное распределение по переменным (х) ы е г~ у) у* х — скрытые переменные *) ()(Х) ь- распределение по Х, первоначально пустое гог еасЬ значение х, переменной Х йо (2(х,) ь- епишегаге-товпг(х„ е, у, (), Р) гегигп ногтатгге(()(х)) Яипсевоп Евиюегасе-доупг(х, е, вага, иа2неа, Р) гееигпз действительное число ЕВ Етрсуэ(иагз) Г)эеп гееигп Р(х,е,казиев) у ь- ввгзг(иагз) гееигп ~ Епитегасе-эоупс(х, е, Лезс(иагз), (у)«азпез), Р) у При наличии полного совместного распределения, с которым можно было бы работать, алгоритм еппгпегаге-эоьпг-Аз)г становится полным алгоритмом получения ответов на вероятностные запросы, касаюгциеся дискретных переменных. Но этот алгоритм недостаточно хорошо масштабируется, поскольку при наличии проблемной области, которая описана п булевыми переменными, он требует входной таблицы с размером О (2"'), а обработка этой таблицы занимает время О (2" ) .
В реальных задачах может потребоваться рассмотреть сотни или тысячи случайных переменных, а не только три. Попытка определить огромные количества требуемых вероятностей быстро становится полностью неосуществимой, поскольку может быть даже не накоплено достаточного количества экспериментальных данных, которые требуются для того, чтобы отдельно оценить каждую из записей этой таблицы. По этим причинам полное совместное распределение вероятностей в табличной форме нельзя считать практически применимым инструментальным средством для создания систем формирования рассуждений (хотя в исторических заметках в конце данной главы упоминается одно реальное приложение, основанное на этом методе). б42 Часть Хг.
Неопределенные знания и рассуждения в условиях неопределенности Вместо этого данный подход следует рассматривать как теоретическую основу, на которой могут быть созданы более эффективные подходы. В оставшейся части данной главы представлены некоторые основные идеи, которые потребуются для подготовки к разработке реально осуществимых систем, описанных в главе 14. 13.5. НЕЗАВИСИМОСТЬ Расширим полное совместное распределение, приведенное в табл.!3.2, введя четвертую переменную, всеасЛет. После этого полное совместное распределение, состоящее из 32 элементов (поскольку переменная (уеасЛет имеет четыре значения), принимает вид Р ( тоо ела еле, са сел, саид су, ыеа слет) . Оно содержит четыре варианта таблицы, показанной в табл.
13.2, по олному на каждый вид погоды. Напрашивается резонный вопрос о том, какую связь имеют эти варианты друг с другом и с первоначальной таблицей, состоящей из трех переменных. Например, как связаны друг с другом высказывания Р ( соо сла еле, са ссл, саку су, )ГеаСЛет=с1оис)у) и Р( СооСЛасЛе, сагсЛ, саи1 Су)? Один из способов получения ответа на этот вопрос состоит в использования правила произведения: Р(тооСЛасле, саесЛ, саи1Су, )Геатлет = с1оиоу) — Р()ГеаСЛет=с1оиоу( Соотласле, сагоЛ, саи1Су) Р( Соотласле, сатсЛ, саи1 су) Но человек, не верящий в существование колдунов, не может себе представить, что чьи-то проблемы с зубами могут влиять на погоду.
Поэтому кажется резонным следующее утверждение: Р(ГГеаСЛет = с1оис)у( Соотласле, сагсЛ, саид ту) — Р()(еаСЛет = с1оис)у) (13.7) На основании этого можно вывести следующее: Р(тооСЛасле, сатсЛ, сауд еу, )ГеаСЛет = с1оис)у) Р(Г)еаСЛет = с1оис)у) Р( Соотласле, саесЛ, саид Су) Аналогичное уравнение существует для каждого элемента в распределении Р(тоосласле, сассл, саи1су, л)еасЛет). В действительности можно записать такое общее уравнение: Р ( тооСЛасле, Са Сел, Саит Су, )Геа СЛет) Р(тооСЛасле, Сатсл, Саид Су) Р()(еаСЛет) Таким образом, 32-элементная таблица для четырех переменных может быть сконструирована из одной 8-элементной таблицы и одной 4-элементной. Такая декомпозиция показана схематически на рис.
13.1, а. Свойство вероятностей, используемое при составлении уравнения 13.7, называется 'а. независимостью (а также маргинальной независимостью и абсолютной независимостью). В частности, погода независима от чьих-то проблем с зубами. Независимость между высказываниями а и Ь может быть показана следующим образом: Р(а(Ь) = Р(а) или Р(Ь~ а) = Р(Ь) или Р(а л Ь) = Р(а) Р(Ь) (13.
8) б43 Глава 13. Неопределенность декомпонуетен на декомпонуетен на о И'еа!() ег Сот ) а) Рис. )3. й Два прпмера факторизации большого совместного распредсленил на меньшие распределенил с использованием своиства абсолютной независимости: независимы друг от друга погода и проблемы с зубами (а); независимы друг от друга броски монеты (б) Все эти формы записи являются эквивалентными (упр.
13.7). Свойство независимости между переменными х и у можно сформулировать следующим образом (все эти формы записи также эквивалентны): в(х) Ю = в(х) мпм в(г~х) .—. в(у) лн в(х, г) = в(х)в!у) Утверждения о независимости обычно основаны на знаниях о проблемной области. Как показывает приведенный выше пример, эти утверждения позволяют существенно уменьшить обьем информации, необходимой для описания полного совместного распределения.
Если все множество переменных может быть разделено на независимые подмножества, то полное совместное распределение может быть факторизовано на отдельные совместные распределения, заданные на этих подмножествах. Например, совместное распределение результатов и независимых бросков монеты, в (С„..., С,), может быть представлено как произведение и распределений в (с, ) с одной переменной. Например, с точки зрения практики очень благоприятным фактором является независимость данных зубоврачебного дела и метеорологии, поскольку в противном случае для занятия зубоврачебным делом потребовались бы глубокие знания в области метеорологии, и наоборот. Поэтому утверждения о независимости, если они имеются, позволяют сократить размеры представления проблемной области и уменьшить сложность проблемы вывода.
К сожалению, чистое разделение целых множеств переменных по признаку независимости встречается редко. Если между двумя переменными существует хоть какая-то связь, пусть даже косвенная, свойство независимости перестает соблюдаться. Кроме того, даже независимые подмножества могут оказаться чрезвычайно большими, например, в области стоматологии могут встретиться десятки заболеваний и сотни симптомов, причем все они взаимосвязаны друг с другом.
Чтобы справиться с такими проблемами, мы должны иметь более тонкие методы, чем прямолинейная концепция независимости. 644 Часть Ч. Неопределенные знания н рассуждения в условиях неопределенности 13.6. ПРАВИЛО БАЙЕСА И ЕГО ИСПОЛЬЗОВАНИЕ На с. 632 определено правило произведения и указано, что оно может быть записано в двух следующих формах благодаря коммутативности коньюнкции: Р(а л Ь) = Р(а( Ь) Р(Ь) Р(а л Ь) = Р(Ь)а) Р(а) Приравняв две правые части стороны и разделив их на Р(а), получим такое уравнение: ( ~ ) ( ) (13.9) Это уравнение известно под названием 'в.
правила Байеса (а также закона Байеса, или теоремы Байеса)'. Это простое уравнение лежит в основе всех современных систем искусственного интеллекта для вероятностного вывода. Более общий случай многозначных переменных может быть записан в системе обозначений р следующим образом; мяг )я(ь р (х) Это уравнение также следует рассматривать как представляющее множество уравнений, в каждом из которых рассматриваются конкретные значения переменных. Время от времени нам также придется использовать более общую версию, которая обусловлена некоторым фоновым свидетельством е; р(Х у,а)р(у а) р(1')х,е) (х) ) (13.10) Применение правила Байеса: простой случай На первый взгляд правило Байеса не кажется очень полезным.
В нем требуются три терма (одна условная вероятность и две безусловных вероятности) только для вычисления одной условной вероятности. Но правило Байеса находит очень широкое практическое применение, поскольку во многих случаях имеются хорошие оценки вероятностей для этих трех термов и нужно вычислить четвертый. В такой задаче, как медицинская диагностика, часто известны условные вероятности причинных связей и требуется определить диагноз. Врач знает, что такое заболевание, как менингит, очень часто вызывает у пациента симптом, характеризующийся снижением подвижности шеи; предположим, что этот симптом наблюдается в 50% случаев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
