Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 252
Текст из файла (страница 252)
Обучение Временная сложность этого алгоритма зависит от размера наименьшего совместимого определения. Предположим, что это определение включает р атрибутов из общего количества, равного п атрибутам. В таком случае алгоритм не отыщет данное определение до тех пор, пока не выполнит поиск во всех подмножествах л с размером р.
Количество таких подмножеств измеряется значением п ( ) = 01ие1, Р поэтому сложность алгоритма зависит экспоненциально от размера минимального определения. Как оказалось, данная задача является ХР-полной, поэтому не следует рассчитывать на то, что в общем случае будет достигнута более высокая производительность. Тем не менее во многих проблемных областях существует локальная структура 1понятие локально структурированных проблемных областей рассматривается в главе 14), благодаря которой р становится небольшим.
Получив в свое распоряжение алгоритм изучения определений, обучающийся агент приобретает способность созлавать минимальную гипотезу, с помощью которой он может изучать целевой преликат. Например, можно скомбинировать алпуритм мупуща1- сопвхвсепс-Вес с алгоритмом гуесуэхоп-тхее-ьеахпупд. Это приведет к созданию алгоритма обучения дерева решений с учетом релевантности, ВВОТ1.
(гче1ечапсе-Вазед 1)ес181оп-Тгее 1.еагпптя), в котором вначале определяется минимальное множество релевантных атрибутов, а затем это множество передается алгоритму формирования дерева решений для обучения. В отличие от алгоритма 2эесуэз.оп-Тхее-у еахпхпд, алгоритм ВВОТ1. одновременно обеспечивает и обучение, и использование информации о релевантности для минимизации своего пространства гипотез.
Можно рассчитывать на то, что алгоритм ВВОТ1. даст возможность проводить обучение быстрее по сравнению салгоритмом ГУесТэьоп-Тхее-ьеахпхпд, и действительно так и происходит. На рис. 19.6 показана производительность обучения для этих двух алгоритмов на основе случайно сгенерированных данных для функции, которая зависит только от 5 из 16 атрибутов. Ясно, что в тех случаях, когда все доступные атрибуты являются релевантными, алгоритм ЙВОТ1 не показывает каких-либо преимуществ.
о о 0,9 о Я 0,8 й %о 07 о о ,ф „ 0,5 о 0,4 0 20 40 60 80 100 120 140 Обеем обучающего множества ).ггс. 19.б. Сравнение производительности алгоритмов лвпть и Песхв хоп-тхее-Ьеахпьпд при обработке случайно сгенерированных данных применительно к целевой функции, которая зависит только от 5 из 1б атрибутов 927 Глава!9. Применение знаний в обучении В данном разделе приведены лишь самые основные сведения из области исследования Ъ. декларативного смещения, задача которой состоит в изучении того, как могут использоваться априорные знания для выявления приемлемого пространства гипотез, в котором должен осуществляться поиск правильного целевого определения.
В нем не даны ответы на многие вопросы, например, на те, которые приведены ниже. ° Как могут быть дополнены эти алгоритмы для того, чтобы в них учитывался шум? ° Можно ли обеспечить обработку переменных с непрерывными значениями! ° Можно ли использовать другие виды априорных знаний, кроме определений? ° Как можно обобщить эти алгоритмы для охвата любой теории первого порядка, а не только представлений на основе атрибутов? Некоторые из этих вопросов рассматриваются в следующем разделе. 19.5. ИНДУКТИВНОЕ ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В индуктивном логическом программировании (1пбцсг)уе ) оя)с Ргоягашгп)пав П.Р) объединяются индуктивные методы с мощными представлениями в логике первого порядка, и оно в основном сосредоточивается на представлении теорий в виде логических программ4.
Это научное направление получило широкую известность по трем причинам. Во-первых, индуктивное логическое программирование лежит в основе строгого подхода к решению общих задач индуктивного обучения на основе базы знаний. Во-вторых, в рамках этого направления созданы полные алгоритмы логического вывода общих теорий в логике первого порядка с использованием примеров; это означает, что данные алгоритмы могут успешно применяться лля обучения в тех проблемных областях, в которых использование алгоритмов на основе атрибутов связано с определенными затруднениями. В качестве соответствующего примера можно привести применение методов П.Р в изучении того, как сворачиваются белковые структуры 1рис.
19.7). Трехмерную конфигурацию молекулы белка невозможно представить с помощью какого-либо приемлемого способа в виде множества атрибутов, поскольку конфигурация молекулы неявно обусловлена связями между объектами, а не атрибутами отдельного объекта. Одним из языков, подхоляших для описания таких связей, является логика первого порядка. В-третьих, с помощью методов индуктивного логического программирования могут вырабатываться гипотезы, которые являются 1относительно) простыми для восприятия людьми. Например, перевод на естественный язык правила, приведенного в подписи к рис. 19.7, может уточняться и подвергаться критике биологами, которые работают в данной области.
Это означает, что системы индуктивного логического программирования могут участвовать в научном цикле экспериментирования, выработки гипотез, обсуждения и опровержения. Такое участие невозможно при использовании таких систем, которые вырабатывают классификаторы в виде "черных ящиков", например нейронных сетей. 4 На данном этапе читателю может потребоваться обратиться к главе 9 лля повторного ознакомления с некоторыми из основных понятий, включая хорновские выражения, конъюнктивную нормальную форму, унификацию и резолюпию Часть Ч1.
Обучение Н щз 3!) ьья 1щиг - восходящая и нисходящая связка из четырех спиралей )ощд - ЕЕ-Напд а) б) Рис. )9. 7. Пример решения задачи об ченит по ния понятия "восходя ей и и д у: ложительный и отрицательный примеры приме нечивания белка а), б. П име к щ исходящей связки из четырех спиралей" в пробле " б мной о ласти свора- , (). ример каждой структуры кодируется в виде логического стоящего примерно из 300 конь ческого выражения, со- з коньюнктов, такого как тота1Ьепдт?з (Р2пйзт, 11 В) л НппЬетне1 хсеп (Р2пйзт, б) л....
На основи нии этих описаний и таких классификаций, как Ро10 (Рост-не1?са1-др-лпс?-Роып-вппс)1е, Р2пйзт), система инд ктивно программирования Рсо о(,П09В)сфо ми т, система индуктивного логического ния гобо ( ) сформировала по методу обучения следующее правцяо: Ро1с)(Рост-не1зса1-пр-лпс?-Роып-вппс?1е,р) ч'= Не1хх(р,нз) л Ьепде?з(?з„нхдн) л Ров?стоп (р,?зз,п) л (1 б п и 3) л Ас)эасепс (р,?зз,из) л Не1хх (р,?зз) Правило такого да нев ро озможно выработать путем обучения или даже п едставшпь с любых механизмов, основанных на ат иб тах, д на атрибутах, наподобие тех„которые рассматривались в п едыущих главах Это правило можно перевести но е стественный язык, как показано ниже.
ь варе ы- Белок Р относится к кла ссу методов сворачивания "связка из четырех восходящих и нисходящих спиралей", если он включает ет длинную спираль )з, во второй структурной позиции между позициями 1 и 3 и если с пароль )з, находится рядом со второй спиралью Практический пример Как было указано выпзе, из уравнения 19.5 следует, что общая задача индукции на основе знаний состоит в " "решении" ограничения логического следствия я низвестной гипотезы н ы урое)зеязя, если даны фоновые знания Вас)сдтоплс) и примеры, представленные с пом ощыо описаний Реястзрсзсня И КЛаССИЛ ИКа ий С1аяязбхсасзопяс фи ации 929 Глава 19.
Применение знаний в обучении Вас)гсгоипс( л Вурослеета л Реесгтрстопв и С1аеетЕЕса стопа Для иллюстрации этого процесса рассмотрим задачу изучения семейных связей на примерах. Описания будут состоять из развернутого генеалогического лерева, описанного в терминах отношений мосьег (мать), Расьег (Отец) и магг1ес( (Состоит в браке), а также свойств Ма1е (Мужчина) и Рета1е (Женшина). В качестве примера будет использоваться генеалогическое дерево, рассматриваемое в упр.
8. ! 1, которое показано на рис. 19.8. Соответствующие описания приведены ниже. Зрепсег М Куве Е(иаьещ М Рптр Ма!загс! Р(апа М Сьаг)еа Аппе М МагМ Апвтн М Вагап Евнагв Л Л Р~ %)())ат Наггу Рсгег Лага ива!псе Епасп(е УЬгс. 19.8. Типичное генеалогическое дерево Раслег(РЬ111р,СЛаг1ее) Раслег(РЬ111р,лппе) Иоелег(Мит,Магсагее) Иослег(ншп,Е11гаЬеСЬ) Пагг1ед(РЕапа,СЬаг1ее) Паггтес((Е11гаЬеСЬ,РЬ111р) Ма1е(РЬ111р) Ма1е(СЬаг1ее) Рета1е(Веаегтсе) Рета1е(Магдагее) Высказывания, входящие в состав классификаций С1аееЕЕЕсасуопа, зависят от изучаемого целевого понятия. Например, может потребоваться изучить понятия егапс)рагепс (Дедушка или бабушка), Вгосьегтпьапг (Двоюродный брат) или лпсеасог (Предок).
Что касается понятия сгапс)рагепс, то полное множество с1аее1ЕЕса сусла содержит 20х20=400 конъюнктов в следующей форме: Егапс(рагепС(Мшп,СЬаг1ее) ЕгапсграгепС(Е11гаЬеСЬ,Веасгтсе) Егапс)ракете(нит,Маггу) †,Сгапс(рагепс(лрепсег, РеСег) Безусловно, обучение может быть проведено на основе какого-то подмножества этого полного множества. 930 Часть У]. Обучение Задачей применения любой программы индуктивного обучения является выработка множества высказываний, соответствующих гипотезе пурпе]?еауа, такого, что в нем выполняется заданное ограничение логического следствия.
На данный момент прелположим, что у агента отсутствуют фоновые знания: отношение Вас?гдгоцпс) является пустым. В таком случае одно из возможных решений для нурое?зеауе состоит в следующем: дгапг?рагепе (х,у) ьь [Лг Мое??ег(х, г) л Моспег(г, у) ] ч [5г Мог??ег(х, г) л Раг?2ег(г,у) ] ч [Лг Раь??ег(х, г) л Мог??ег(г, у) ] ч [Зя Распег(х, г) л Раг??ег(г, у) ] Следует отметить, что алгоритм обучения на основе атрибутов, такой как [зесувуоп-тгее-? еагпупд, в попытке решить эту задачу бесконечно углубится в дерево, но не достигнет успеха. Для того чтобы выразить отношение дгапг?рагепг в виде атрибута (т.е.
унарного предиката), необходимо будет преобразовывать пары людей в объекты: Бгапс?рагепг((мое, С??аг1еа)) Затем мы окажемся в тупике, пытаясь представить описания примеров. Единственно возможными атрибутами станут такие ужасно неуклюжие конструкции, как следующая; Р?гзсл1етепстемас??егсйд1?га?зес?з ((Мит, С??аг1ее)) Определением отношения дгапг?рагепг в терминах этих атрибутов становится большая дизъюнкция описаний конкретных случаев, которая вообще не может быть обобщена с учетом новых примеров. св Алгоритмы обучения на основе атрибутоа не способны обеспечить изучение реляционных нредикатов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
