Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 256
Текст из файла (страница 256)
Кроме того, зависимости использовались в методе декларативного смещения Расселом н Грософом [1327]. Эквивалентность таких понятий, как определения н пространства гипотез с ограниченным словарем, была доказана в [1323]. Возможность применения алгоритмов обучения к определениям и достижения повышенной производительности с помощью метода КВОТЕ впервые была показана на примере алгоритма Росна в [20]. Тадепалли [1485] описал остроумный алгоритм обучения на основе определений, который демонстрирует существенное увеличение скорости обучения. Идею о том, что индуктивное обучение может осуществляться по методу обратной дедукции, можно проследить до работы В.С.
Джевонса [736], который писал: "Изучение формальной логики и теории вероятностей привело меня к тому, что я стал приверженцем мнения, что не существует такой вещи, как отдельный метод ин- 942 Часть Ч1. Обучение дукции, противопоставляемый дедукции, но индукция является просто обратным воплощением дедукции". Исследования в области вычислительных алгоритмов начались с замечательных тезисов докторской диссертации Гордона Плоткина [1216), опубликованных в Эдинбурге.
Хотя Плоткин разработал множество теорем и методов, которые в настояШее время находят применение в индуктивном логическом программировании, он был разочарован некоторыми результатами, показывающими неразрешимость определенных подзадач методами индукции. В системе М)8 [1396) снова была предпринята попытка решения задачи изучения логических программ, но самим автором эта работа в основном рассматривалась как вклад в теорию автоматизированной отладки. Работа в области индуктивного вывода правил, подобная проведенной при создании систем 1РЗ [1257) и СХ2 [263], привела к появлению системы Ро52 [1258], которая впервые позволила осуществлять на практике методы индуктивного вывода реляционных правил.
Исследования в области реляционного обучения получили новый стимул после публикации работы Магглтона и Бантайна [1100), в которой была описана программа С!8о1, реализуюшая немного неполную версию метода обратной резолюции, но способную вырабатывать новые преликаты'. Задачи изобретения предикатов рассматриваются также в [!604). Следуюшей важной системой стала Оо!ет [1102), в которой используется алгоритм формирования покрытия, основанный на выдвинутом Плоткином понятии относительного наименьшего обшего обобщения. Тогда как система роз2 была нисходяшей, системы С!8о! и Оо1егп действовали в восходящем направлении.
К примерам других систем, появившихся в тот период, относятся 1гоц [1312) и С1!пг [352]. В разработанной в дальнейшем системе Ргойо! [1098] был принят гибридный (нисходящий и восходящий) подход к формированию обратного логического следствия; эта система применялась для решения целого ряда практических задач, особенно в области биологии и обработки естественного языка.
В [1099) описано расширение системы Ргойо1, позволяющее учитывать неопределенность, в форме стохастических логических программ. Формальный анализ методов П.Р приведен в [1096], большая подборка статей представлена в [1097), а описания методов и приложений собраны в [897]. В [1163] можно найти более современный обзор истории развития этой области и описание проблем, которые должны быть решены в будушем. Первые результаты анализа сложности, опубликованные в [632], свидетельствовали о том, что задача изучения высказываний в логике первого порядка является безнадежно сложной.
Однако благодаря лучшему пониманию важности синтаксических ограничений различного рода, налагаемых на выражения, удалось получить положительные результаты даже для выражений с рекурсией [426]. Результаты изучения возможности обучения для методов П.Р изложены в [279) и [794).
Несмотря на то что в настоящее время индуктивное логическое программирование, по-видимому, является доминирующим подходом к решению задач конструктивной индукции, это — не единственный опробованный подход. Разработаны так называемые Ъ. системы открытий, которые направлены на моделирование процесса научного открытия новых понятий, обычно путем прямого поиска в пространстве определений понятий. В системе АМ, или Ацготагес[ Магйегпаг)с!ап [автоматизированный матема- з Метод обратной резолюции опубликован также в 113221, где в одной нз сносок приведен простой алгоритм. 943 Глава 19. Применение знаний в обучении тик), Дуга Лената [337] использовались эвристики открытий, выраженные в виде правил экспертной системы для управления осуществляемым в ней поиском понятий и научных предположений в области элементарной теории чисел. В отличие от большинства систем, предназначенных для формирования математических рассуждений, в системе АМ отсутствовало понятие доказательства, поэтому она могла выдвигать только предположения.
Эта система повторно открыла предположение Гольдбаха и теорему уникального разложения на простые множители. Архитектура системы АМ бьша обобщена в системе Еипз)го [907] в результате введения механизма, способного перезаписывать собственные эвристики открытия этой системы. Система Еипзйо применялась во многих областях, отличных от области поиска математических открытий, хотя и с меньшим успехом, чем АМ. Но методология систем АМ и Еипз)со оказалась противоречивой [909],[1292]. Еше один класс систем открытия предназначен для обработки реальных научных данных в целях поиска новых законов.
Системы Оа)гоп, 0)аиЬег и 8)ай) [885] прелставляют собой системы на основе правил, предназначенные для поиска количественных связей в экспериментальных данных, полученных из физических систем; в каждом случае системы показали свою способность снова выдвинуть широко известное открытие из истории науки. Системы открытия, основанные на вероятностных методах (в частности, алгоритмы кластеризации, позволяющие обнаруживать новые категории), рассматриваются в главе 20.
УПРАЖНЕНИЯ 19.1. Преобразовав выражение в коньюнктивную нормальную форму и применив метод резолюции, покажите, что приведенное на с. 923 заключение, касающееся бразильцев, является обоснованным. 19.2. Для каждого из следующих определений запишите логическое представление и обьясните, почему это определение является истинным (если его лействительно можно считать таковым). а) Название штата (в США) можно определить по почтовому индексу.
б) Масса монеты зависит от ее проекта и номинала. б) Применительно к конкретной программе выходные данные определяются входными данными. в) Изменение массы тела в большую или меньшую сторону происходит под влиянием климата, рациона питания, физической нагрузки и интенсивности обмена веществ. г) Наличие лысины у мужчины определяется тем, была ли лысина у деда со стороны матери. 19.3. Могла бы найти применение вероятностная версия определения? Предложите приемлемую трактовку такого понятия.
19.4. Подставьте недостающие значения выражения С, или С, (или обоих выражений) в приведенный ниже ряд выражений, при условии, по С вЂ” резольвента С, и С,. а) С = Тхие =г Р(Л,В), С, = Р(х,у) => 0(х,у), С, = ??. б) С = Тхие =г Р(Л, В), Сг = ??, Сг = '??. Частью. Обучение В) С = Р(х,у) =З Р(х, Х(у) ), С„= ??, С, = ??. Если имеется больше одного возможного решения, приведите по одному примеру каждого из различных решений. 19.5. (Й Предположим, что разрабатывается логическая программа, которая осу- ществляет один из этапов логического вывода по методу резолюции. Это означает, что такая программа, Веэс1ке ( с„с,, с), завершается успешно, если с — результат применения операции резолюции к выражениям с, и с,.
При обычных обстоятельствах программа деэо1ке используется в составе системы автоматического доказательства теорем, в которой она вызывается с параметрами с, и с„конкретизированными значениями некоторых выражений, и возврашает значение резольвенты с. А теперь предположим, что вместо этого данная программа вызывается с конкретизированным значением с и неконкретизированными значениями с, и с,. Приведет ли это к успешному получению приемлемых результатов на этапе обратной резолюции? Потребуется ли внести какие-либо специальные изменения в рассматриваемую систему логического программирования для того, чтобы можно было применять программу в такой форме? 19.б. Предположим, что в системе Ро11 рассматривается задача введения литерала в выражение с использованием бинарного предиката Р и что предыдущие литералы (включая голову выражения) содержат пять разных переменных.
а) Какое количество функционально различных литералов может быть сформировано? Два литерала являются функционально идентичными, если они отличаются только по именам содержащихся в них новых переменных. б) Можете ли вы найти общую формулу для количества различных литералов с предикатом, имеющим арность и, если ранее использовалось п переменных? в) Почему в системе Ро11 не допускается введение литералов, которые не содержат ранее использованных переменных? 19.7. Используя данные из генеалогического дерева, приведенного на рис. 19.8, или подмножество этих данных, примените алгоритм Ро11 для изучения опреде- ления предиката лисеэ с еж В данной главе рассматривается обучение как способ формиро- вания рассуждений в условиях неопределенности на основании результатов наблюдении.
В главах части Ч было указано, что в реальных вариантах среды ситуации преимугцественно являются неопределенными. Агенты могут справиться с неопределенностью, используя методы теории вероятностей и теории решений, но вначале должны сформировать в процессе обучения на основании полученного опыта свои вероятностные теории о мире. В этой главе показано, как может быть достигнута эта цель. В ней описано, как сформулировать саму задачу обучения в виде процесса вероятностного вывода (раздел 20.!).
Материал, изложенный в данной главе, свидетельствует о том, что байесовский подход к обучению является чрезвычайно мощным и предоставляет общие решения проблем шума, чрезмерно тгцательной подгонки и оптимального предсказания. В настоящей главе учитывается также тот факт, что агент, не являющийся полностью всезнающим, не будет никогда уверен в том, что та или иная теория о мире действительно является правильной, но все равно обязан принимать решения, используя некоторую теорию о мире. В разделах 20.2 и 20.3 описаны методы обучения вероятностных моделей (в основном байесовских сетей).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
