Применение знаний в обучении
Поэтому, чтобы сформировать обобщение гипотезы Я2, необходимо просто найти определение Ci, которое логически следует из С2. Такая задача решается довольно легко. Например, если С2 (х) представляет собой высказывание Al ternate (х) лРаtrons (х, Some), то одно из возможных обобщений задается в виде Ci (х) =Раtrons (х, Some). Такая форма операции обобщения называется удалением условий. Интуитивно ясно, что в результате такой операции формируется более слабое определение и поэтому гипотеза допускает использование более крупного множества положительных примеров. Может быть также предусмотрен целый ряд других операций обобщения, в зависимости от языка, в котором выражаются эти операции. Аналогичным образом, уточнение гипотезы может осуществляться путем введения дополнительных условий в ее потенциальное определение или путем удаления дизъюнктов из какого-то дизъюнктивного определения. Рассмотрим, как могут быть выполнены подобные операции в задаче с рестораном, используя данные, приведенные в табл. 18.1.
• Первый пример, Xl9 является положительным. Выражение Alternate (Х имеет истинное значение, поэтому допустим, что начальная гипотеза имеет такой вид:
Hi: Vx WillWait (х) <=> Alternate (х)
• Второй пример, Х2, отрицателен. Гипотеза Ях предсказывает, что он должен быть положительным, поэтому данный пример — ложно положителен. Это означает, что необходимо уточнить гипотезу нг. Это можно сделать, введя дополнительное условие, позволяющее исключить пример х2. Один из возможных вариантов состоит в следующем:
Н2 : Vx WillWait {х) <=> Alternate (х) л Patrons (х, Some)
• Третий пример, х3, является положительным. Гипотеза я2 предсказывает, что он должен быть отрицательным, поэтому данный пример — ложно отрицательный. Это означает, что необходимо обобщить гипотезу Я2. Удалим условие Al ternate и получим следующее:
Н3: Vx WillWait (х) <=> Patrons (х, Some)
• Четвертый пример, х4, также положителен. Гипотеза Я3 предсказывает, что он должен быть отрицательным, поэтому данный пример — ложно отрицательный. Это означает, что необходимо обобщить гипотезу Я3. Условие Patrons удалить нельзя, поскольку такая операция приведет к созданию всеохватывающей гипотезы, которая будет несовместимой с примером х2. Одна из возможностей состоит в добавлении дизъюнкта:
Н4: Vx WillWait {х) <=> Patrons (х. Some)
v {Patrons (х. Full) л Fri/Sat{x))
Итак, гипотеза уже начинает выглядеть как приемлемая. Очевидно, что есть и другие варианты, совместимые с первыми четырьмя примерами; ниже приведены два из них.
Н4': Vx WillWait {х) -WaitEstimate {х, 30-60) Н4'': Vx WillWait (х) <=> Patrons (х. Some)
v(Patrons(x. Full) л WaitEstimate(x,10-30))
Алгоритм Current-Best-Learning описан здесь в недетерминированной форме, поскольку в любой момент может существовать возможность применить несколько вариантов уточнения или обобщения. Выбранный вариант не всегда обеспечивает получение простейшей гипотезы и может привести также к безвыходной ситуации, в которой ни одна простая модификация гипотезы не будет совместимой со всеми данными. В подобных случаях программа должна выполнить возврат к предыдущей точке выбора.
Алгоритм Current-Best-Learning и его варианты использовались во многих системах машинного обучения, начиная с программы "обучения распознаванию арок" Патрика Уинстона [1602]. Однако при большом количестве экземпляров примеров и большом пространстве гипотез возникают некоторые описанные ниже трудности.
1. В алгоритме снова и снова проводится проверка всех предыдущих экземпляров при каждой модификации, а это требует больших затрат.
2. Процесс поиска может быть связан с очень интенсивным перебором с возвратами. Как было показано в главе 18, размеры пространства гипотез могут определяться двойной экспоненциальной зависимостью.