Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 250
Текст из файла (страница 250)
В компьютерных науках для ускорения работы программ уже в течение долгого времени используется метод ж запоминания (гпегпо(ха()оп), который предусматривает сохранение в памяти результатов вычислений. Фундаментальная идея, лежащая в основе запоминающих функций, состоит в том, что должна накапливаться база данных, состоящая из входных/выходных пар; после вызова функции в первую очередь выполняется проверка базы данных для определения того, можно ли обойтись без решения рассматриваемой задачи с самого начала. Обучение на основе объяснения представляет собой значительный шаг вперед, поскольку в нем предусматривается созлание общих правил, охватывающих целый класс вариантов. В случае дифференцирования метод запоминания позволяет записать в память информацию о том, что производная от х' по х равна 2х, но потребует от агента, чтобы он вычислял производную 2' по д с самого начала. Однако было бы желательно иметь возможность извлечь общее правило', что для любого арифметического неизвестного и производная от и' по и равна 2 и.
В терминах логики такая мысль может быть выражена с помощью следующего правила: Лгдедгееетсцп)споет(и) =ь цест каеуме(и, и) = 2н Если база знаний содержит такое правило, то для любого нового случая, который является экземпляром этого правила, может быть немедленно найдено решение.
Безусловно, это лишь тривиальный пример очень общего феномена. После того как достигнуто понимание какой-то идеи, она может быть обобщена и повторно использована в других обстоятельствах. Освоенная идея становится "очевидным" этапом мышления, после чего может использоваться в качестве строительного блока при решении еше более сложных задач. Альфреду Норту Уайтхеду 11583], в соавторстве с которым Бертран Рассел написал свою знаменитую книгу Рпас(р(а Ма(Лета((са, принадлежат такие слова: с)В "Цивилизация развивается, увеличивая количества важных операций, которые ее представители могут выполнять, ие задумываясь".
По-видимому, сам Уайтхед применял обучение на основе объяснения, чтобы истолковать полученные им результаты, по аналогии с тем, как Зог объяснял соплеменникам свое открытие. Если вы поняли основную идею примера с дифференцированием, то ваш мозг уже занимается извлечением их него основных принципов обучения на основе объяснения. Обратите внимание на то, что вам не требовалось заранее изобретать принципы обучения на основе объяснения, прежде чем вы ознакомились с этим примером. Как и пещерным людям, наблюдающим за манипуляциями Зога, вам (и авторам данной книги) нужен был пример для того, чтобы прийти к пониманию основных принципов. Именно поэтому часто гораздо проще сначала показать, почему так хороша какая-то идея, чем сразу же ее изложить.
' Безусловно, может быль также сформировано общее правило ляя й', но текущего примера достаточно, чтобы проиллюстрировать общий принцип. 919 Глава 19. Применение знаний в обучении Извлечение общих правил из примеров Обучение на основе объяснения базируется на том важном принципе, что вначале необходимо составить объяснение данного наблюдения с использованием априорнь х знаний, а затем сформировать определение класса случаев, для которого может использоваться такая же структура объяснения. Подобное определение может лечь в основу правила, охватывающего все случаи данного класса.
Само "объяснение" может представлять собой логическое доказательство, но в более общем случае объяснением может служить любой процесс формирования рассуждений или решения задачи, этапы которого полностью определены. Ключом к успешному формированию объяснения является определение необходимых условий для того, чтобы такие же этапы процесса можно было применить к другому случаю. Мы будем использовать в качестве рассматриваемой здесь системы формирования логических рассуждений простую систему доказательства теорем по методу обратного логического вывода, которая описана в главе 9.
Дерево доказательства для случая е)епхиа сзие (х', х) =2х слишком велико для того, чтобы его можно было использовать в качестве примера, поэтому для иллюстрации применяемого метода обобщения рассмотрим более простую задачу. Предположим, что задача состоит в том, чтобы упростить выражение 1х ( О+х) . База знаний включает следующие правила: Яеьпзсе(и, зз) л Эзтр1зЕу(и, е) .=з Яхзпр1зЕу(и, е) Рпзтзезие(и) ~ 5зтр1зЕу(и, и) АЕЕС)зтеехоцл)спиел(и) =з РпзтЕСззе(и) Ъ)ипдзеп(и) ~ Рпттзетзе(и) деьпхее(1хи, и) деьпз Се(0+и, и) Доказательство того, что ответом является х, приведено на рис.
19.5, сее(зху. В методе обучения на основе объяснения фактически одновременно формируются два дерева доказательства. Во втором дереве доказательства используется цель, описанная с помощью переменных, в которой константы первоначальной цели заменены переменными. По мере развития первоначального доказательства так же поэтапно развивается доказательство с помощью переменных, в котором применяются точно такие же приложения правил. Использование некоторых правил может вызвать конкретизацию определенных переменных. Например, для того чтобы можно было применить правило деьпз Се(1хи, и), необходимо вначале связать с 1 переменную х в подцепи Яеж з се(хх(у+в), и) .
Аналогичным образом, переменная у должна быть связана с О в подцепи деьпЕ Се (у+в, и' ), для того чтобы можно было использовать правило )(еъзпхсе(О+и, и) . После получения обобщенного дерева доказательства остается только взять листовые узлы (с необходимыми связываниями) и сформулировать общее правило для целевого предиката, следующим образом: Леьпзее(1 х (О+а),Оеп) л Яеззгдее(0+а, и) л Апзе)зтеезопп)споззп(п) .=з эЕтр1зЕу(1х(Оьз), з) Обратите внимание на то, что первые два условия в левой части правила являются истинными независимо от значения ж Поэтому их можно удалить из данного правила, что приводит к получению такого соотношения: Апд ШтеС1оил!гпогзл ( з) ~ Яцтр11Еу(1х ( Оее), и) 920 Часть Ч!. Обучение геь( ) Рис.
19.5. Деревья доказительства для рассматриваемой задачи упрощения. Лервое дерево демонстрирует докизательство для первоначального экземпляра задачи, на основании которого можно вывести следующее: Акае)япеетс~мспоып(я) ~ я1тр1).еу(1х(О+я),я) Второе дерево демонстрирует доказительство для экземпляра задачи, в котором все константы заменены переменными, что позволяет вывести целый ряд других правил Вообще говоря, из окончательного правила можно удалять такие условия, которые не налагают ограничений на переменные в правой части правила, поскольку при этом результирующее правило остается истинным и становится более эффективным. Обратите внимание на то, что условие АядсЬтеезсггп)споып (а) удалять нельзя, поскольку не все возможные значения я являются арифметическими неизвестными.
Для значений, отличных от арифметических неизвестных, могут потребоваться другие формы упрощения; например, если переменная я равна 2хЗ, то правильным упрощением выражения 1х (0+ (2хЗ ) ) должно быть б, а не 2хЗ. Подводя итог, можно отметить, что основной процесс обучения на основе объяснения действует, как описано ниже. 1. Используя рассматриваемый пример, составить доказательство того, что целевой предикат является применимым к данному примеру, с использованием доступных фоновых знаний. 2. Одновременно с этим сформировать обобщенное дерево доказательства для цели, описанной с помощью переменных, в котором используются такие же этапы логического вывода, как и в первоначальном дереве доказательства.
921 Глава 19. Применение знаний в обучении 3. Сформулировать новое правило, левая часть которого состоит из листовых узлов дерева доказательства, а правая часть представляет собой цель, описанную с помощью переменных (после применения соответствующих связываний из обобщенного доказательства). 4. Удалить все условия, которые являются истинными независимо от значений переменных в цели. Повышение эффективности правила Обобщенное дерево доказательства, показанное на рис.
19.5, фактически приводит к получению больше чем одного обобщенного правила. Например, если будет прекращено наращивание правой ветви в дереве доказательства после того, как одна ветвь достигнет этапа ррхту схуе, т.е. если будет выполнено отсечение этой ветви, то получим следующее правило; Ргхтхсзте(г) ~ дхарма(Гу(1х(0->а), а) Это правило является таким же действительным, как и правило, в котором используется предикат Акус)паесуооп)споюп, но более общим, поскольку оно охватывает также случаи, в которых я является числом. Из дерева доказательства можно извлечь еше более общее правило, выполняя отсечение ветви после этапа яхгпр21 Еу(у+ а, ы), что приводит к получению такого правила: Бутр11гу(у+а, и) ~ Язтр11Гу(1х (у+а), и) Вообще говоря, из любого частичного поддерева обобщенного дерева доказательства можно извлечь какое-то правило. Это означает, что имеет место еше одна проблема: какое из этих правил следует выбрать? Выбор правила, подлежащего выработке, сводится к решению вопроса об эффективности выбранного правила.
Ниже описаны три фактора, которые касаются анализа прироста эффективности, достигнутого в результате обучения на основе объяснения. 1. Введение большого количества правил влечет за собой замедление процесса формирования рассуждений, поскольку механизм логического вывода так или иначе должен проверять эти правила, даже в тех случаях, когда они не приводят к решению. Иными словами, увеличение количества правил приводит к увеличению коэффициента ветвления в пространстве поиска. 2.
Для того чтобы компенсировать замедление процесса формирования рассуждений, производные правила должны обеспечивать существенное увеличение скорости для тех случаев, которые они охватывают. Такое увеличение достигается в основном благодаря тому, что производные правила позволяют избегать тупиков, которые могли бы возникнуть без их использования, а также в связи с тем, что они сокращают само доказательство. 3. Производные правила должны быть как можно более общими, для того чтобы они применялись к максимально возможному множеству случаев.
Общепринятый подход к обеспечению эффективности таких производных правил состоит в том, чтобы следить за соблюдением требования, касающегося ~. операционной пригодности каждой подцепи в правиле. Подцель является операционно пригодной, если ее можно достаточно "легко" решить. Например, подцель 922 Часть 'Л. Обучение р гзтз сз ие ( а) решить легко, и для этого требуется самое большее два этапа вывода, а для достижения подцели Язтр? з Еу(у+ а, ы) может потребоваться произвольный объем логического вывода в зависимости от значений у и ж Если проверка на операционную пригодность выполняется на каждом этапе формирования обобщенного доказательства, то появляется возможность отсечь оставшуюся ветвь, как только будет найдена операционно пригодная подцель, и оставить в качестве конъюнкта нового правила лишь эту операционно пригодную подцель.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
