Индуктивное обучение
Индуктивный алгоритм построения дерева решений ID3
Один способ сокращения перебора состоит в выборе более "информированного" оператора, который не строит так много вершин, не относящихся к делу.
Одно из направлений исследований в этой области – автоматизированное извлечение знаний. Идея состоит в том, чтобы машина училась решать проблемы примерно так, как учиться человек.
Можно предложить три варианта приобретения знаний, которые позволят обойтись без создания базы знаний "вручную" объединенными усилиями человека-эксперта и инженера по знаниям, которые имеют прямое отношение к проблемам экспертных систем:
- извлечение множества правил из предъявляемых примеров;
- анализ важности отдельных правил;
- оптимизация производительности набора правил.
Существуют и другие аспекты машинного обучения, которых мы здесь касаться не будем.
Точное, определение термину "обучение" дать довольно трудно, но большинство авторов сходятся во мнении, что это - качество адаптивной системы, которая способна совершенствовать свое поведение (умение справляться с проблемами), накапливая опыт, например опыт решения аналогичных задач.
Любая программа обучения должна обеспечивать возможность сохранять и анализировать полученный опыт решения проблем, а также обладать способностью, применять сделанные выводы для решения новых проблем.
Рассмотрим одну из методик обучения, которая получила наименование пространство версий. Поиск в пространстве версий основан на том, что операция обобщения упорядочивает понятия в пространстве поиска. Затем этот порядок используется для выбора направления поиска.
Рассмотрим один из алгоритмов.
Алгоритм ID3обеспечивает изучение понятий на примерах. Особый интерес представляют способ хранения полученных знаний, подход к управлению сложностью, эвристика для выбора понятий-кандидатов и возможности обработки зашумленных данных. Такое представление позволяет классифицировать объект путем проверки значения определенных свойств.
В алгоритме ID3 понятия представляются в виде дерева решений. Такое представление позволяет классифицировать объект путем проверки значения определенных свойств.
Например, рассмотрим задачу оценки кредитного риска на основе кредитной истории, долга, наличия поручительства и дохода. В таблице 1 представлены примеры с известным кредитным риском.
Таблица 1 - Данные о кредитной истории
Дерево решений на рисунке 13содержит приведенные в таблице 1 данные и позволяет корректно классифицировать все объекты в таблице.
Рисунок 13 - Дерево решений для оценки кредитного риска
Каждый внутренний узел дерева решений представляет некоторое свойство, например, кредитную историю или доход. Каждому возможному значению этого свойства соответствует ветвь дерева. Узлы-листья отражают результаты классификации, в частности, низкий или средним риск. С помощью этого дерева можно классифицировать клиента, тип которого неизвестен: для каждого внутреннего узла проверяется значение соответствующего свойства для данного клиента и осуществляется переход по соответствующей ветви. Процесс завершается при достижении конечного узла, определяющего класс объекта.
Заметим, что при классификации каждого конкретного экземпляра с помощью этого дерева учитываются не все свойства, представленные в таблице 1. Например, если человек имеет хорошую кредитную историю и низкий долг, то согласно дереву без учета дохода и поручительства с ним связывается низкий риск. Это дерево позволяет корректно классифицировать все примеры.
В целом, размер дерева, необходимого для классификации конкретного набора примеров, варьируется в зависимости от проверяемых свойств. На рисунке 14 показано дерево, которое гораздо проще предыдущего, но позволяет корректно классифицировать, примеры из таблицы 1.
Рисунок 14 - Упрощенное дерево решений для оценки кредитного риска
Имея набор обучающих примеров и несколько деревьев решений, позволяющих корректно классифицировать эти примеры, следует выбрать дерево, которое с наибольшей вероятностью позволит корректно классифицировать неизвестные экземпляры. По алгоритму ID3 таким деревом считается простейшее дерево решений, покрывающее все обучающие примеры. В основу такого предположения положена проверенная временем эвристика, согласно, которой предпочтение отдается простоте без дополнительных ограничений. "Глупо прилагать больше усилий, чем нужно для достижения цели... Не стоит приумножать сущности сверх необходимого."
Более современная версия этого принципа сводится к выбору простейшего ответа, соответствующего исходным данным. В данном случае это наименьшее дерево решений, которое позволяет корректно классифицировать все имеющиеся примеры.
Если предположить, что существующих примеров достаточно для построения корректного обобщения, то проблема сводится к выделению необходимых свойств из дополнительных примеров. Простейшее дерево решений, покрывающее все примеры, вероятнее всего, не будет содержать излишних ограничений. Хотя эта идея основывается на интуитивных рассуждениях, ее можно проверить на практике