Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 251
Текст из файла (страница 251)
К сожалению, обычно приходится искать компромисс между операционной пригодностью и общностью. Для более конкретных подцелей обычно бывает проще найти решение, но они охватывают меньше случаев. Кроме того, сам критерий операционной пригодности в определенной степени субъективен: можно уверенно сказать, что подцель, для достижения которой требуется один или два этапа, является операционно пригодной, но можно ли это утверждать, если количество этапов приближается к 10 или ! 00? Наконец, стоимость поиска решения для данной конкретной подцели зависит от того, какие еше правила имеются в базе знаний.
По мере введения дополнительных правил эта стоимость может и увеличиваться, и уменьшаться. Таким образом, при эксплуатации систем ЕВЕ фактически приходится сталкиваться с очень сложными проблемами оптимизации, пытаясь добиться максимальной эффективности заданной начальной базы знаний.
Иногда существует возможность вывести математическую модель влияния операции добавления какого-то конкретного правила на общую эффективность и использовать эту модель для определения наилучшего правила, подлежащего добавлению. Но такой анализ может стать очень сложным, особенно когда приходится сталкиваться с рекурсивными правилами.
Один из перспективных подходов состоит в эмпирическом решении проблемы эффективности путем добавления нескольких правил и определения того, какое из них является полезным и действительно позволяет ускорить работу. Эмпирический анализ эффективности фактически становится основой системы ЕВ).. То, что в предыдущем абзаце неформально было названо "эффективностью заданной базы знаний", в действительности представляет собой усредненную по рассматриваемым случаям сложность решения задач, предъявляемых системе и описываемых некоторым распределением вероятностей. эп Система ЕВЕ позволяет проводить обобщение по результатам решения примеров задач, встретившихся в прошлом, поэтому способствует повышению эффективности базы знаний применительно к тем типам задач, которые, скорее всего, должны встретиться в будущем.
Такая организация работы способствует достижению успеха, при условии, что распределение вероятностей прошлых примеров приблизительно соответствует распределению вероятностей будущих примеров; это — такое же предположение, которое лежало в основе метода РАС-обучения, описанного в разделе 18.5.
Если проведено тщательное и продуманное проектирование системы ЕВЕ, то появляется возможность достичь существенного ускорения работы. Например, очень крупная система обработки естественного языка на основе Рго!08, предназначенная для прямого и обратного перевода речи со шведского на английский, позволила добиться приемлемой производительности работы в реальном времени только благодаря применению системы ЕВЕ в процессе синтаксического анализа (1351].
Глава 19. Применение знаний в обучении 923 19.4. ОБУЧЕНИЕ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИИ О РЕЛЕВАНТНОСТИ Путешественник, приехавший в Бразилию, о котором говорилось раньше, повидимому, сумел прийти к достоверному обобщению, касающемуся языка, на котором говорят остальные бразильцы. Полученный этим путешественником логический вывод был основан на его фоновых знаниях, а именно на знаниях о том, что население данной конкретной страны (обычно) говорит на одном и тот же языке. Это утверждение можно выразить в логике первого порядка слелующим образом': ьгаезопа1зсу(х,п) л дгаезопа1зеу(у,п) л ьапдиаде(х,1) =ь Ьапдиаде(у,1) (19.6) Это высказывание буквально означает; "Если х и у имеют одинаковое гражданство и и х говорит на языке 1, то у также говорит на этом языке". Нетрудно показать, что на основании этого высказывания и следующего наблюдения: Дтаецопа1зсу(уехпапс)о,вхая11) л Ьапдиаде(уехпапс(о,рохеидиеее) можно прийти к такому заключению (см.
упр. 19.1): Дтасзопа1з Су(х,Вгаяз1) т ьапдиаде(х, Рохеидиеае) Высказывания, подобные приведенному в уравнении 19.б, выражают строгую форму релевантности: если известно гражданство человека, то полностью определен язык, на котором он говорит (эту мысль можно выразить иначе — язык определяется функциональной зависимостью от гражданства). Такие высказывания называются Ъ. функциональными зависимостями, или пк определениями, и встречаются настолько часто в приложениях определенных типов (например, в спецификациях проектов баз данных), что для их записи используется специальный синтаксис. В этой главе мы будем придерживаться системы обозначений, предложенной Дэвисом (329): Дтастопа1зсу(х,п) Ь Ьапдиаде(х,1) Как обычно, это обозначение представляет собой синтаксическое упрощение, но оно подчеркивает тот факт, что определение в действительности показывает связь между предикатами; в данном случае гражданство определяет язык.
Аналогичным образом могут быть представлены релевантные свойства, определяющие проводимость и плотность: Наеехза1(х,т) л тетрехаеихе(х, С) ь сопс)иоеапое(х,р) Насех1а1(х,т) л тетрехасипе(х,е) ь Вепэтсу(х,с)) Соответствующие обобщения следуют логически из определений и наблюдений. Определение пространства гипотез Хотя определения позволяют обосновать общие заключения, касающиеся всех бразильцев или всех образцов меди, исследуемых при заданной температуре, они, безусловно, не позволяют создать на основании одного примера общую прогности- з Для упрощения в этой главе предполагается, что каждый человек говорит только нв одном языке.
Безусловно, в это правило потребовачось бы ввести поправку, если бы дело касалось таких многоязычных стран, как Швейцария или Индия. 924 Часть Ч1. Обучение ческую теорию, которая распространялась бы на граждан всех государств или на любые материалы, исследуемые при любых температурах. По существу, основной эффект применения определений можно рассматривать как ограничение пространства гипотез, которые должен рассматривать обучающийся агент. В частности, согласно определению, при прогнозировании проводимости достаточно учитывать только материал и температуру, но игнорировать массу, права собственности на рассматриваемый образец, день недели, фамилию главы правительства и т.д.
Но гипотезы, касающиеся проводимости, безусловно, могут включать термы, которые в свою очерель зависят от материалы и температуры, в том числе учитывающие молекулярную структуру, тепловую энергию или плотность свободных электронов. ж Определения задают базовый аюварь, достаточный для построения гипотез, касающихся цевевого предиката. Это утверждение можно доказать, продемонстрировав, что данное конкретное определение логически эквивалентно утверждению о том, что правильная формулировка целевого предиката является одной из множества всех формулировок, которые могут быть представлены с помощью предикатов из левой части определения. Интуитивно ясно, что сокращение размера пространства гипотез должно способствовать упрощению задачи изучения целевого предиката.
Возможный при этом прирост эффективности можно оценить с использованием основных результатов теории вычислительного обучения (см. раздел 18.5). Вначале напомним, что для булевых функций требуется 1од ( ~ н ~ ) примеров, чтобы свести все пространство гипотез к одной приемлемой гипотезе, где ! и! — размер пространства гипотез. Если в распоряжении ученика имеется и булевых характеристик, для которых должны быть построены гипотезы, то в отсутствии дополнительных ограничений ~ н~ =0(2' ), поэтому необходимое количество примеров составляет 0 ( 2') .
Если же в левой части определения находятся с) предикатов, то для ученика потребуется только 0(2в) примеров, что соответствует сокращению в 0(2' в) раз. Для смещенного пространства гипотез, такого как конъюнктивно смещенное пространство, это сокращение будет не столь радикальным, но все еше достаточно существенным. Обучение и использование информации о релевантности Как было указано во введении к данной главе, априорные знания являются полезными при обучении, но они также должны быть освоены в процессе обучения. Поэтому для обеспечения целостного подхода к обучению с учетом релевантности необходимо предусмотреть алгоритм обучения, относящийся к определениям. Алгоритм обучения, приведенный в этом разделе, представляет собой прямолинейную попытку найти простейшее определение, совместимое с рассматриваемыми результатами наблюдений.
В частности, определение р 0 говорит о том, что если какие- либо примеры согласуются по выражению р, то они должны также согласовываться по выражению 0. Поэтому определение является совместимым с множеством примеров, если каждая пара, которая согласуется по предикатам в левой части определения, согласуется также по целевому предикату, т.е. входит в одну и ту же классификацию. Например, предположим, что имеются примеры результатов измерения проводимости образцов материалов, приведенные в табл. !9. !. Минимальным согласованным определением является ма сехза1нтетрехасихе~ 0опс)иссапсе. Существует также одно не минимальное, но совместимое определе- Глава 19. Применение знаний в обучении 925 ние, а именно маддлЯЕаелТешрегасиге)-Сопс)иссапсе.
Оно совместимо с примерами, поскольку масса и размер определяют плотность, а в рассматриваемом наборе данных отсутствуют два разных материала с одной и той же плотностью. Как обычно, для устранения гипотез, которые только внешне кажутся правильными, необходимо иметь более крупное множество примеров. Таблица 19.1. Примеры результатов измерения проводимости образцов материалов Образец Масса Температура Материал Размер Проводимость Медь Медь Медь Свинец Свинец Свинец Для поиска минимальных совместимых определений можно применить несколько подходящих для этого алгоритмов. Наиболее очевидный подход состоит в проведении поиска в пространстве определений и проверке всех определений с одним предикатом, двумя предикатами и т.д. до тех пор, пока не будет найдено совместимое определение.
Предполагается, что используется простое представление на основе атрибутов, аналогичное тому, которое использовалось при обучении деревьев решений в главе 18. Определение с) будет представлено с помощью множества атрибутов в левой части, поскольку предполагается, что целевой предикат остается постоянным. Основной алгоритм, соответствующий этому подходу, приведен в листинге 19.3.
Листинг 19.3. Алгоритм поиска минимального совместимого определения Ецпссвоп Нфпзша1-Сопвзвеепг-вел(Е, А) геецгпн множество атрибутов зпрцепз Е, множество примеров А, множество атрибутов с количеством элементов п Еог з г — О,...,п бо Еог еасЬ подмножество А, множества А с количеством элементов 1 бо 1Е Сопвзвеепе-Пее?(Аз, Е) СЬеп геецгп Аг Енпсе1оп Сопвзвеепе-веет(А, Е) георгин истинностное значение зпрценг А, множество атрибутов Е, мнсжествО примврОВ 1оса1 чаг1аЪ1епз Н, хзш-таблица Еог еасЬ пример е зп Е бо зЕ некоторый пример в таблице Н имеет такое же значение множества атрибутов А, что и пример е, но имеет другую классификацию СЬеп геецгп Еа2ве сохранить обозначение класса примера е в таблице Н под индексом, соответствуюшим значениям атрибутов А примера е гесцгп сгие 5! 51 52 53 53 54 12 12 24 12 12 24 26 100 26 26 !00 26 0,59 0,57 0,59 0,05 0,04 0,05 926 Часть тг).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
