Обучение списков решений
Список решений — это логическое выражение с ограниченной формой. Он состоит из ряда проверок, каждая из которых представляет собой конъюнкцию литералов. Если проверка, применяемая к описанию примера, завершается успешно, то список решений задает возвращаемое значение. Если же проверка оканчивается неудачей, то обработка продолжается со следующей проверки в списке6. Списки решений напоминают деревья решений, но их общая структура проще. С другой стороны, отдельные проверки в них намного сложнее. На рис. 18.10 показан список решений, который представляет следующую гипотезу:
Vx WillWait (х) <=$ Patrons (х, Some) v {Patrons {х, Full) л Fri/Sat{x))
Если допускается применение проверок с произвольными размерами, то списки решений становятся способными представить любую булеву функцию (упр. 18.15). С другой стороны, если размер каждой проверки ограничен, самое большее, к литералами, то для обучающего алгоритма появляется возможность успешно создавать обобщения на основе небольшого количества примеров. Мы будем называть такой язык списков решений с к литералами языком k-DL (DL— Decision List). Пример, приведенный на рис. 18.10, относится к языку 2-DL. Можно легко показать (упр. 18.15), что язык k-DL включает в качестве подмножества язык k-DT (DT — Decision Tree), который представляет собой множество всех деревьев решений с глубиной, не превышающей к. Важно помнить, что конкретный язык, к которому применяется обозначение k-DL, зависит от атрибутов, используемых для описания примеров. Мы будем использовать запись k-DL(n) для обозначения языка k-DL, в котором применяется п булевых атрибутов.
Первая задача состоит в том, чтобы показать, что язык k-DL доступен для изучения, т.е. что любая функция, заданная в языке k-DL, может быть точно аппроксимирована после обучения на приемлемом количестве примеров. Для этого необходимо рассчитать количество гипотез, которые могут быть представлены на этом языке. Допустим, что язык проверок (конъюнкций из самое большее к литералов, в которых используется п атрибутов) обозначается как Conj (п,к). Поскольку любой список решений состоит из проверок, а каждая проверка может быть связана с результатом Yes или No или может отсутствовать в списке решений, то количество различных множеств проверок, из которых могут состоять гипотезы, измеряется величиной 3|Con:i (n,k) 1. Каждое из этих множеств проверок может быть задано в любом порядке, поэтому справедливо следующее соотношение:
\k-BL{n)\ < 3|Con:i(n'k)| \Conj{n,k) I !
Количество конъюнкций из к литералов с п атрибутами может быть определено таким образом:
Это соотношение можно подставить в уравнение 18.1, чтобы показать, что количество примеров, необходимое для РАС-обучения некоторой функции k-DL, определяется полиномиальной зависимостью от п:
Поэтому любой алгоритм, возвращающий согласованный список решений, будет обеспечивать РАС-обучение некоторой функции k-DL с помощью приемлемого количества примеров, если значение к невелико.
Следующая задача состоит в том, чтобы найти эффективный алгоритм, который возвращает совместимый список решений. Мы будем использовать жадный алгоритм, называемый Decision-List-Learning, который повторно отыскивает проверку, точно согласующуюся с некоторым подмножеством обучающего множества. Найдя такую проверку, алгоритм добавляет ее к создаваемому списку решений и удаляет соответствуюшие примеры. Затем алгоритм формирует только оставшуюся часть списка решений, используя лишь оставшиеся примеры. Такая операция повторяется до тех пор, пока не останется ни одного примера. Этот алгоритм показан в листинге 18.3.
function Decision-List-Learning(examples) returns список решений или индикатор неудачи failure
if множество examples пусто
then return тривиальный список решений No t <— проверка, которая согласуется с непустым подмножеством
examplest множества examples, таким что все элементы examplest
являются либо положительными, либо отрицательными примерами if такая проверка t отсутствует then return failure if примеры в подмножестве examplest являются положительными
then о <— Yes else о <— No
return список решений с начальной проверкой t, результатом о и оставшимися проверками, определяемыми выражением Decision-List-Learning(examples-examplest)
В этом алгоритме не определен метод выбора следующей проверки для добавления к списку решений. Хотя формально приведенные выше результаты не зависят от такого метода выбора, представляется резонным подход, позволяющий отдавать предпочтение небольшим проверкам, которые согласуются с большими множествами однородно классифицируемых примеров, для того чтобы общий список решений был как можно более компактным. Простейшая стратегия достижения этой цели состоит в том, что нужно отыскивать наименьшую проверку t, которая согласуется с любым однородно классифицируемым подмножеством, независимо от размера этого подмножества. Как показано на рис. 18.11, даже такой примитивный подход действует вполне успешно.