Количество конъюнкций из к литералов с n атрибутами может быть определено таким образом:

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

Это соотношение можно подставить в уравнение 18.1, чтобы показать, что количество примеров, необходимое для РАС-обучения некоторой функции k-DL, определяется полиномиальной зависимостью от n:

Поэтому любой алгоритм, возвращающий согласованный список решений, будет обеспечивать РАС-обучение некоторой функции k-DL с помощью приемлемого количества примеров, если значение к невелико.

Следующая задача состоит в том, чтобы найти эффективный алгоритм, который возвращает совместимый список решений. Мы будем использовать жадный алгоритм, называемый Decision-List-Learning, который повторно отыскивает проверку, точно согласующуюся с некоторым подмножеством обучающего множества. Найдя такую проверку, алгоритм добавляет ее к создаваемому списку решений и удаляет соответствуюшие примеры. Затем алгоритм формирует только оставшуюся часть списка решений, используя лишь оставшиеся примеры. Такая операция повторяется до тех пор, пока не останется ни одного примера. Этот алгоритм показан в листинге 18.3.

Листинг 18.3. Алгоритм обучения списков решений

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

Рис. 18.11. Кривая обучения по данным о ресторане при использовании алгоритма Decision-Lis t-Learning. Для сравнения показана кривая, соответствующая алгоритму Decision-Tree-Learning