Формирование знаний на основе машинного обучения

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

Оригинальный алгоритм формирования дерева страдает еще одной "хворью" - он часто формирует сложное дерево, в котором фиксируются несущественные для задачи классификации отличия в элементах обучающей выборки. Один из способов справиться с этой проблемой -- использовать правило "останова", которое прекращало бы процесс дальнейшего разделения ветвей дерева при выполнении определенного условия. Но оказалось, что сформулировать это условие не менее сложно, а потому Квинлан пошел по другому пути. Он решил "обрезать" дерево решений после того, как оно будет сформировано алгоритмом. Можно показать, что такое "обрезание" может привести к тому, что новое дерево будет обрабатывать обучающую выборку с ошибками, но с новыми данными оно обычно справляется лучше, чем полное дерево. Проблема "обрезания" довольно сложна и выходит за рамки данной книги. Читателям, которые заинтересуются ею, я рекомендую познакомиться с работами [Mingers, 1989, b] и [Mitchell, 1997], а подробное описание реализации этого процесса в С4.5 можно найти в [Quinlan, 1993, Chapter 4].

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

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

Квинлан применил следующую стратегию формирования множества правил из дерева решений.

(1) Сформировать начальный вариант множества правил, перечислив все пути от корня дерева к листьям.

(2) Обобщить правила и при этом удалить из них те условия, которые представляются излишними.

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

(4) Упорядочить множества правил по классам и выбрать класс, который будет являться классом по умолчанию.

Упорядочение правил, которое выполняется на шаге (4), можно рассматривать как примитивную форму механизма разрешения конфликтов (см. главу 5). Порядок классов внутри определенного подмножества теперь уже не будет иметь значения. Назначение класса по умолчанию можно считать своего рода правилом по умолчанию, которое действует в том случае, когда не подходит ни одно другое правило.

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

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

Перечень классов, с которыми в дальнейшем будет оперировать экспертная система, необходимо сформулировать заранее. Другими словами, алгоритмы, положенные в основу функционирования системы С4.5, не способны формировать перечень классов на основе группировки обучающей последовательности объектов. Кроме того, классы должны быть четко очерченными, а не "расплывчатыми" -- некоторый объект либо принадлежит к данному классу, либо нет, никаких промежуточных состояний быть не может. И, кроме того, классы не должны перекрываться.

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

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

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

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

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

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

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

ѕ эффективность набора правил в целом и достоверность получаемого результата.

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

В работе [Langlotz et al, 1986] представлен метод теории принятия решений, который позволяет уточнять характеристики отдельных правил. Если в спецификации правила имеются свойства, которые можно варьировать, например связанные с вероятностными характеристиками, очень полезно выяснить, как сказывается изменение этого параметра на результатах работы системы.

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

ЕСЛИ

1) против инфекции предполагается применение тетрациклина;

2) возраст пациента (лет) менее 8,

ТО

есть серьезное основание полагать (0.8), что применение тетрациклина не рекомендуется против этой инфекции.

Это правило содержит в себе возможность варьирования между воздействием на поразившую пациента инфекцию и риском отрицательного побочного эффекта. Ожидаемая полезность применения этого правила является функцией полезности результатов правила и вероятностей реального получения этих результатов.

В теории принятия решений ожидаемая полезность (EU -- expected utility) действия А, возможные результаты которого есть элементы множества {О1, О2, ...,Оn}, причем исходы характеризуются вероятностями р1,р2, ...,рn, выражается формулой

EU(A) = Sumi[pi u(Oi) i=1,..,n.]

В этой формуле и(Оi) означает оценку полезности отдельного варианта результата операции (исхода) Оi. Нас интересует, как будет меняться полезность действия, которое рекомендуется правилом, при изменении вероятностей рi и оценок полезности и(Оi). Если, например, инфекция, к которой имеет отношение это правило, устойчива против всех прочих препаратов, кроме тетрациклина, а вероятность побочного эффекта довольно мала, то значение EU(A) будет более высоким по сравнению с ситуацией, когда против инфекции можно применить и другие препараты, не имеющие побочных эффектов, а вероятность побочного эффекта от применения тетрациклина довольно высока.

Авторы описывают применение методов анализа чувствительности, которые позволяют выявить зависимость между полезностью исходов и их вероятностями. Точка, в которой рекомендации альтернативных курсов лечения имеют равную полезность, представляет пороговое значение вероятности. Анализируя эти пороговые значения, можно определить, насколько далеко отстоит оценка вероятности в модели от того значения, при котором потребуется изменить принятое оптимальное решение. Усилия, затраченные на выполнение описанного анализа, окупаются тем, что инженер по знаниям и эксперт получают более точное обоснование рациональности применения того или иного правила. В частности, методы теории принятия решений позволяют определить в явном виде значения тех переменных, от которых зависит применимость отдельных правил. Это поможет инженеру по знаниям отыскать нежелательные взаимосвязи между правилами в наборе, включая и такие, которые являются результатом вероятностных зависимостей, рассмотренных нами в главе 9.

В работе [Wilkins and Buchanan, 1986] основное внимание уделено комплексной отладке набора эвристических правил. Авторы работы утверждают, что поочередная (инкрементальная) модификация отдельных правил в процессе настройки и эксплуатации экспертной системы (например, как это делается в программе TEIRESIAS, описанной в главе 10) не гарантирует сходимости процесса к оптимальному набору правил. Они предостерегают против применения "универсальных стратегий" делать правила более общими или более специализированными в тех случаях, когда обнаруживаются неверные результаты работы системы в целом.

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

Авторы дают определение оптимальному набору правил, как такому, который минимизирует вероятность получения неверных результатов. Предполагается, что отдельные правила в наборе соответствуют определенному стандарту качества, а главные усилия направляются на выбор в существующем наборе подмножества правил, наилучшего в определенном смысле. Процесс отбора такого оптимального подмножества формулируется как проблема минимизации двудольного графа (bipartite graph minimization problem), которая базируется на отображении множества вершин, представляющих объекты обучающей выборки, на множество вершин, представляющих исходное множество правил. Показано, что хотя в общем виде эта проблема относится к классу необозримых, но существует эвристический метод ее решения для конкретной постановки, связанной со спецификой экспертных систем. Предлагаемое решение в основном сводится к тому, чтобы минимизировать в наборе вредные взаимные связи между "хорошими" эвристическими правилами, которые сформированы индуктивными методами.

Другая работа, имеющая отношение к проблематике настройки наборов порождающих правил, посвящена описанию системы LAS (Learning Apprentice System) [Smith et al, 1985]. LAS представляет собой интерактивный инструментальный комплекс для создания и настройки баз знаний. В системе частично автоматизирован процесс формирования эвристических правил на основании теории предметной области и отладки этих правил при возникновении каких-либо проблем с их применением в экспертной системе. Работа LAS базируется на формализме сетей зависимостей (они обсуждаются в главе 19), который используется для представления обоснования правил в терминах теории предметной области. Эти же структуры используются и для формирования пояснений при возникновении сбоев в работе системы.

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

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