Точно Не проект 2 / Не books / Источник_1

г) обобщением некоторого свойства в соответствии с иерархией обобщений, например, предикаты

форма(Х, прямоугольная),

форма(Х, треугольная)

обобщаются с помощью формулы

форма(Х, многоугольная)

для иерархии обобщений, изображенной на рисунке 4.26.

Рисунок 4.26 – Иерархия обобщений

Если понятие р является более общим, чем понятие q, то р – охваты-

вающее понятие для q.

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

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

цвет = {желтый, зеленый, красный, синий};

форма = {круг, квадрат, треугольник}; размер = {маленький, средний, большой}.

Каждый из объектов можно представить предикатом

объект(Цвет, Форма, Размер),

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

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

-исключить из G все понятия-кандидаты, не охватывающие некоторые понятия, входящие в S;

5) если G = S и оба множества являются одноэлементным, то найденное понятие согласуется со всеми данными, и поиск заканчивается;

6)если G и S – пустые множества, то не существует понятия, которое охватывает все положительные примеры и не охватывает ни одного отрицательного примера.

Процесс обучения понятию “красный круг” с помощью рассмотренного алгоритма представлен в таблице 4.3

Таблица 4.3 – Обучение понятию “красный круг”

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

объект(средний, квадрат, зеленый)

множество G на первом этапе расширяется при выполнении операции специализации за счет понятий-кандидатов, не сопоставимых с примером:

объект(X, Y, желтый),

объект(X, Y, красный),

объект(X, Y, синий),

объект(X, круг, Z),

объект(X, треугольник, Z), объект(маленький, Y, Z), объект(большой, Y, Z).

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

Таким образом, алгоритм Митчелла относится к группе поисковых алгоритмов обучения. При этом выполняется поиск в ширину, что не эффективно, если множества G и S быстро расширяются. В этом случае могут применяться методы эвристического поиска.

В алгоритме Митчелла предполагается, что каждый класс описывается одним конъюнктивным правилом, и предъявляемые примеры не искажены шумом. На практике часто необходимо восстанавливать правила в условиях зашумленных данных. Алгоритм Митчелла весьма чувствителен к предъявляемым примерам. Даже один ошибочный пример может привести к потере сходимости.

4.3.4. Алгоритм обобщения ID3

Алгоритм ID3 (Iterative Dichotomizer 3) был предложен Дж. Квинланом в 1983 г. Также как и алгоритм Митчелла, он обеспечивает индуктивное формирование понятий по примерам. Однако понятия в этом случае представляются с помощью деревьев решений. Каждый нетерминальный узел дерева решений соответствует некоторому признаку классификации, а ветви, выходящие из узла, характеризуют альтернативные значения признака. Терминальные узлы дерева решений определяют класс (понятие), к которому относится предъявленный пример. На рисунке 4.28 изображен фрагмент дерева решений при определении степени риска сердечно-сосудистых заболеваний.

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

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

Рассмотрим процесс построения дерева решений, изображенного на рисунке 4.28. Множество примеров MP задано таблицей 4.4

Таблица 4.4– Примеры оценки риска сердечно-сосудистых заболеваний

При первом вызове функции Induce_Tree в качестве корня дерева выбирается признак “курение”, который характеризуется двумя значениями “да” и “нет”. Эти значения разбивают множество примеров МР на два подмножества МР1 и МР2. Элементами первого подмножества являются примеры 1 и 2. Элементами второго подмножества – примеры 3 и 4. Для каждого из подмножеств МР1 и МР2 функция Induce_Tree вызывается рекурсивно. При этом в ходе каждого из вызовов происходит дальнейшее разбиение подмножеств МР1 и МР2, но уже относительно признака потребления жиров. В этом случае образуются подмножества, составленные из элементов одного класса, и рекурсия возвращает листья дерева (рисунок 4.28), снабженные метками соответствующих классов. Листья связываются с соответствующими ветвями, отмеченными возможными значениями признака “потребление жиров”, т.е. “норма” и “излишек”. В итоге формируются два поддерева, соответствующие подмножествам МР1 и МР2. Указанные поддеревья, в свою очередь, связываются с ветвями, отмеченными возможными значениями признака “курение”, и процесс формирования дерева решений завершается.

Каждый вызов функции Induce_Tree формирует очередное поддерево решений, корень которого представляется признаком Р. В качестве критерия выбора очередного признака используется количество информации, обусловленное включением того или иного признака в дерево решений.

Пусть имеются независимые и несовместные сообщения х1, х2,…, хn, вероятности получения которых равны р(х1), р(х2),…, р(хn). Тогда количество информации для всей совокупности сообщений можно оценить с помощью меры К. Шеннона:

Если рассматривать обучающие примеры как сообщения, то с помощью (4.20) можно оценить количество информации, содержащееся в обучающей выборке и, следовательно, в дереве решений, которое охватывает

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

Вопросы для самопроверки

1.Приведите формулировку задачи дедуктивного вывода в терминах логики исчисления предикатов.

2.Сформулируйте этапы стандартизации предикатных формул.

3.Преобразуйте формулу x y{[P(x, y) Q(y)] zR(x, y,z)} к виду предложения.

4.Найдите НОУ для множества литералов {P(x,f(x),a), P(b,y,x)}.

5.Получите следствие xL(x) из посылок x(S(x) L(x)) и ( x)( S(x)), используя принцип резолюции.

6.Назовите и объясните основные стратегии поиска, применяемые в ходе выполнения процедуры резолюции.

7.Приведите пример применения принципа резолюции в ходе информационного поиска.

8.Сформулируйте и приведите пример решения задачи планирования перемещения робота на основе принципа резолюции.

9.Объясните общую схему поиска решения в системе STRIPS.

10.Какие три вида дизъюнктов лежат в основе языка Пролог?

11.Постройте дерево опровержения для целевого утверждения ?- member(1,[2,1,3]).

12.Назовите и объясните виды неопределенности.

13.Запишите и объясните формулу Байеса для вычисления апостериорной условной вероятности гипотезы Н

14.Объясните метод обработки неопределенности, используемый в системе

PROSPECTOR.

15.Объясните метод обработки неопределенности, используемый в системе

MYCIN (EMYCIN).

16.Как вычисляются степени доверия и правдоподобия в теории свидетельств Демпстера-Шефера.

17.Приведите и объясните определения нечеткой и лингвистической переменной.

18.Сформулируйте основные операции нечетких множеств.

19.Объясните понятие нечеткого отношения.

20.Представьте в виде нечеткого отношения правило “ если А, то B”, где А и В – нечеткие множества.

21.Что понимают под композицией нечетких отношений?

22.Сформулируйте правила вычисления функции принадлежности многозначной логики.

23.Приведите примеры нечетких правил вывода, предложенных Л. Заде в рамках лингвистической логики.

24.Какие выводы называют правдоподобными?