3. Представление

Вид материала

Обзор

Содержание Таблица 20.1. Обучающая выборка примеров

Подобный материал:

• Вопросы к экзамену по курсу " ЭВМ и периферийные устройства" для групп К2-121, -122,, 75.03kb.
• И представление налоговой отчетности, 357.06kb.
• И представление налоговой отчетности, 394.07kb.
• Дать детям представление о речевом этикете, как о правилах поведения в различных ситуациях;, 241.98kb.
• Дать общее представление о витаминах, познакомить учащихся с их классификацией, представителями, 180.08kb.
• Урок Окружающий мир 2 класс умк «Перспективная начальная школа», 44.76kb.
• Задачи:; развивать обобщенное представление о казахстанцах; сформировать представление, 49.53kb.
• Урок 57 Источники права Цель, 56.46kb.
• Вопросы для подготовки к экзамену по архитектуре ЭВМ, 79.1kb.
• Отчет об оказании юридических услуг за 20 г. Представляют, 89.3kb.

ГЛАВА 20. Формирование знаний на основе машинного обучения

20.1. Индуктивное обучение

20.2. Система Meta-DENDRAL

20.3. Построение дерева решений и порождающих правил

20.4. Уточнение наборов правил

Рекомендуемая литература

Упражнения

В главе 1 мы уже вскользь упоминали о связи между приобретением знаний экспертной системой и использованием автоматизированных методов формирования знаний на базе машинного обучения (machine learning). Было отмечено, что в ряду тех проблем, с которыми сталкивается разработчик экспертной системы, приобретение знаний является одной из наиболее трудоемких. В главе 10 было рассмотрено множество методов извлечения знаний, но ни один из них не позволяет избавиться от услуг человека-эксперта и соответственно от значительного объема работы, выполняемой "вручную".

Можно предложить три варианта приобретения знаний, которые позволят обойтись без создания базы знаний "вручную" объединенными усилиями человека-эксперта и инженера по знаниям.

(1) Использовать интерактивные программы, которые извлекали бы знания непосредственно у человека-эксперта в процессе диалога за терминалом. Различные варианты такого рода программ мы рассматривали в предыдущих главах. Вы могли убедиться, что такой вариант может успешно использоваться на практике в том случае, если диалоговая система обладает некоторым запасом базовых знаний об определенной предметной области.

(2) Использовать программы, способные обучаться, читая тексты, аналогично тому, как учится человек в процессе чтения технической литературы. Этот метод "упирается" в более общую проблему машинного распознавания смысла естественного языка человека. Поскольку сложность этой проблемы, пожалуй, на порядок выше, чем проблемы приобретения знаний о конкретной предметной области, вряд ли на таком пути мы быстро достигнем цели (по крайней мере, при современном уровне решения проблемы распознавания естественного языка).

(3) Использовать программы, которые способны обучаться под руководством человека-учителя. Один из подходов состоит в том, что учитель предъявляет программе примеры реализации некоторого концепта, а задача программы состоит в том, чтобы извлечь из предъявленных примеров набор атрибутов и значений, определяющих этот концепт. Такой подход уже успешно опробован в ряде исследовательских систем, и использованные при этом базовые методы составляют предмет обсуждения данной главы.

За последние 10 лет в области исследования методов формирования знаний на основе машинного обучения (в дальнейшем для краткости мы будем употреблять термин машинное обучение — machine learning) наблюдается бурный прогресс. Но мы не будем в этой главе делать широкого, а следовательно, и поверхностного обзора имеющихся работ, а сконцентрируемся на тех методах, которые имеют прямое отношение к проблематике экспертных систем:

извлечение множества правил из предъявляемых примеров;

анализ важности отдельных правил;

оптимизация производительности набора правил.

Существуют и другие аспекты машинного обучения, которых мы здесь касаться не будем, поскольку пока что еще не видно, как они смогут повлиять на технологию экспертных систем (но нельзя исключать, что в будущем дело может радикально измениться). Читатели, которых заинтересуют такие аспекты, могут обратиться к работам, перечисленным в конце главы.

20.1. Индуктивное обучение

Точное определение термину "обучение" дать довольно трудно, но большинство авторов сходятся во мнении, что это — качество адаптивной системы, которая способна совершенствовать свое поведение (умение справляться с проблемами), накапливая опыт, например опыт решения аналогичных задач [Simon, 1983]. Таким образом, обучение — это одновременно и способность, и действие. Любая программа обучения должна обеспечивать возможность сохранять и анализировать полученный опыт решения проблем, а также обладать способностью применять сделанные выводы для решения новых проблем.

В работе [Carbonell et al, 1983] представлена классификация программ обучения на основе используемой стратегии. Попросту говоря, использованная стратегия зависит от того, насколько глубоко может программа проникнуть в суть той информации, которую она получает в процессе обучения.

На одном конце спектра находятся программы, которые обучаются, непосредственно воспринимая новые знания, и не выполняют при этом никакого логического анализа. Обычно такую методику обучения называют rote learning ("зубрежка", а программы соответственно — "зубрилками"). Аналогов такой методике в обычной жизни не счесть. Самый знакомый всем — зазубривание таблицы умножения (или "Отче наш..."). На другом конце спектра обучающих программ находятся те, которые пользуются методикой unsupervised learning, т.е. обучение без преподавателя. Под этим подразумевается способность формулировать теоремы, которая имеет очевидную аналогию с образом мышления человека, делающего научное открытие на основе эмпирических фактов.

В этой главе мы рассмотрим методики, лежащие посередине между этими двумя крайностями. Они получили наименование супервизорного обучения (supervised learning). Программам, использующим такую методику, демонстрируются ряд примеров. Программа должна проанализировать набор свойств этих примеров и идентифицировать подходящие концепты. Свойства примеров известны и представлены парами "атрибут-значение". "Надзор" за процессом обучения заключается, главным образом, в подборе репрезентативных примеров, т.е. в формировании пространства атрибутов, над которым будет размышлять программа.

Наиболее общая форма задач, решаемых в такой системе обучения, получила наименовании индукции (induction). Таким образом, индуктивная программа обучения — это программа, способная к обучению на основе обобщения свойств предъявляемых ей примеров (экземпляров, образцов). В работе [Michalski, 1983, р. 83] дано такое определение процессу обучения:

"Эвристический поиск в пространстве символических описаний, сформированный применением различных правил вывода к исходным наблюдаемым проявлениям".

Символические описания представляют собой, как правило, обобщения, которые можно сделать на основе наблюдаемых проявлений. Такие обобщения являются формой логического заключения, т.е. они предполагают выполнение определенных, регламентируемых некоторыми правилами трансформаций символических описаний, которые представляют наблюдаемые проявления. Одна из форм индуктивного обучения предусматривает демонстрацию примеров двух типов — тех, которые соответствуют концепту (позитивные экземпляры), и тех, которые ему не соответствуют (негативные экземпляры). Задача программы обучения — выявить или сконструировать подходящий концепт, т.е. такой, который включал бы все позитивные экземпляры и не включал ни одного негативного. Такой тип обучения получил название обучение концептам (concept learning).

Рассмотрим набор данных, представленный в табл. 20.1.

^ Таблица 20.1. Обучающая выборка примеров

	Экземпляр	Страна-изготовитель	Размер	Старая модель	Позитивный/ негативный
	Oldsmobile Cutlass	США	Большой	Нет	Негативный
	BMW 31 6	Германия	Малый	Нет	Позитивный
	Thunderbird Raodster	США	Малый	Да	Негативный
	VW Cabriolet	Германия	Малый	Нет	Позитивный
	Rolls Royce Corniche	Великобритания	Большой	Да	Негативный
	Chevrolet Bel Air	США	Малый	Да	Негативный

Предположим, что концепт, которому мы хотим обучить программу, это Немецкий автомобиль. Тогда позитивными экземплярами для этого концепта будут BMW 316 и VW Cabriolet, а остальные— негативными. Если же целевой концепт— Американский автомобиль старой марки, то позитивными экземплярами будут Thunderbird Raodster и Chevrolet Bel Air, а остальные — негативными.

Очень существенно предъявлять программе и позитивные, и негативные экземпляры. В первой из рассмотренных выше задач и BMW 316, и VW Cabriolet являются малыми автомобилями, поэтому если программе не представить в качестве негативного экземпляра Chevrolet Bel Air, то она может сделать вывод, что концепт Немецкий автомобиль совпадает с концептом Малый автомобиль. Аналогично, если во второй задаче не будет представлен негативный экземпляр Oldsmobile Cutlass, то программа может посчитать концепт Американский автомобиль старой марки совпадающим с более общим концептом Американский автомобиль.

С формальной точки зрения любое множество данных, в котором выделены положительные и отрицательные экземпляры, можно считать обучающей выборкой для индуктивной программы обучения. В обучающей выборке также нужно специфицировать некоторый набор атрибутов, имеющих отношение к обучаемым концептам, а запись каждого экземпляра должна содержать значения этих атрибутов. В табл. 20.1 представлены значения атрибутов обучающей выборки для концепта Немецкий автомобиль.

Другая задача обучения получила наименование обобщение дескрипторов (descriptive generalization). Формулируется задача следующим образом: программе обучения предъявляется набор экземпляров некоторого класса объектов (т.е. представляющих некоторый концепт), а программа должна сформировать описание, которое позволит идентифицировать (распознавать) любые объекты этого класса. Пусть, например, обучающая выборка имеет вид

{Cadillac Seville, Oldsmobile Cutlass, Lincoln Continental},

причем каждый экземпляр выборки имеет атрибуты размер, уровень комфорта и расход топлива. Тогда в результате выполнения задачи обобщения дескрипторов программа сформирует описание, представляющее набор значений дескрипторов, характерный для данного класса объектов:

{большой, комфортабельный, прожорливый}.

Отличие между задачами обучение концептам и обобщение дескрипторов состоит в следующем:

задача обучения концептам предполагает включение в обучающую выборку как позитивных, так и негативных экземпляров некоторого заранее заданного набора концептов, а в процессе выполнения задачи будет сформировано правило, позволяющее затем программе распознавать ранее неизвестные экземпляры концепта;

задача обобщения дескрипторов предполагает включение в обучающую выборку только экземпляров определенного класса, а в процессе выполнения задачи создается наиболее компактный вариант описания из всех, которые подходят к каждому из предъявленных экземпляров.

Обе задачи относятся к классу методик, который мы назвали супервизорным обучением, поскольку в распоряжении программы имеется и специально подготовленная обучающая выборка, и пространство атрибутов.

В следующем разделе мы рассмотрим две программы обучения, которые разработаны в связи с созданием экспертной системы DENDRAL. Первый вариант реализации программы обучения нельзя отнести ни к одной из перечисленных выше категорий, но второй вариант использовал методику, которую мы сейчас можем отнести к категории "индуктивное обучение". В оригинальном описании программы авторы назвали ее version space (пространство версий). Постановка задачи очень напоминает обучение концептам, поскольку предусматривает включение в обучающую выборку позитивных и негативных экземпляров концепта.

Интересно сравнить оба варианта системы и выяснить, как знания, специфичные для определенной предметной области (в данном случае, химии), могут быть использованы алгоритмом обучения, независящим от предметной области.

В разделе 20.3 описана современная программа индуктивного обучения, на примере которой будет продемонстрировано, как формируются правила для экспертных систем. В разделе 20.4 мы затронем вопрос настройки отдельных правил и набора связанных правил.