Главная arrow книги arrow Копия Глава 18. Обучение на основе наблюдений arrow Обучение списков решений
Обучение списков решений

Список решений — это логическое выражение с ограниченной формой. Он состоит из ряда проверок, каждая из которых представляет собой конъюнкцию литералов. Если проверка, применяемая к описанию примера, завершается успешно, то список решений задает возвращаемое значение. Если же проверка оканчивается неудачей, то обработка продолжается со следующей проверки в списке6. Списки решений напоминают деревья решений, но их общая структура проще. С другой стороны, отдельные проверки в них намного сложнее. На рис. 18.10 показан список решений, который представляет следующую гипотезу:

Если допускается применение проверок с произвольными размерами, то списки решений становятся способными представить любую булеву функцию (упр. 18.15). С другой стороны, если размер каждой проверки ограничен, самое большее, к литералами, то для обучающего алгоритма появляется возможность успешно создавать обобщения на основе небольшого количества примеров. Мы будем называть такой язык списков решений с к литералами языком k-DL (DL— Decision List). Пример, приведенный на рис. 18.10, относится к языку 2-DL. Можно легко показать (упр. 18.15), что язык k-DL включает в качестве подмножества язык k-DT (DT — Decision Tree), который представляет собой множество всех деревьев решений с глубиной, не превышающей k. Важно помнить, что конкретный язык, к которому применяется обозначение k-DL, зависит от атрибутов, используемых для описания примеров. Мы будем использовать запись k-DL(n) для обозначения языка k-DL, в котором применяется η булевых атрибутов.

Рис. 18.10. Список решений для задачи с рестораном

Первая задача состоит в том, чтобы показать, что язык k-DL доступен для изучения, т.е. что любая функция, заданная в языке k-DL, может быть точно аппроксимирована после обучения на приемлемом количестве примеров. Для этого необходимо рассчитать количество гипотез, которые могут быть представлены на этом языке. Допустим, что язык проверок (конъюнкций из самое большее к литералов, в которых используется η атрибутов) обозначается как Conj (n, к). Поскольку любой список решений состоит из проверок, а каждая проверка может быть связана с результатом Yes или No или может отсутствовать в списке решений, то количество различных множеств проверок, из которых могут состоять гипотезы, измеряется величиной . Каждое из этих множеств проверок может быть задано в любом порядке, поэтому справедливо следующее соотношение: