Обучение и использование информации о релевантности
Как было указано во введении к данной главе, априорные знания являются полезными при обучении, но они также должны быть освоены в процессе обучения. Поэтому для обеспечения целостного подхода к обучению с учетом релевантности необходимо предусмотреть алгоритм обучения, относящийся к определениям. Алгоритм обучения, приведенный в этом разделе, представляет собой прямолинейную попытку найти простейшее определение, совместимое с рассматриваемыми результатами наблюдений. В частности, определение PQ говорит о том, что если какие-либо примеры согласуются по выражению Р, то они должны также согласовываться по выражению Q. Поэтому определение является совместимым с множеством примеров, если каждая пара, которая согласуется по предикатам в левой части определения, согласуется также по целевому предикату, т.е. входит в одну и ту же классификацию. Например, предположим, что имеются примеры результатов измерения проводимости образцов материалов, приведенные в табл. 19.1.
Минимальным согласованным определением является MaterialATemperaturey Conductance. Существует также одно не минимальное, но совместимое определение, а именно MassASizeATemperatureyConductance. Оно совместимо с примерами, поскольку масса и размер определяют плотность, а в рассматриваемом наборе данных отсутствуют два разных материала с одной и той же плотностью. Как обычно, для устранения гипотез, которые только внешне кажутся правильными, необходимо иметь более крупное множество примеров.
Для поиска минимальных совместимых определений можно применить несколько подходящих для этого алгоритмов. Наиболее очевидный подход состоит в проведении поиска в пространстве определений и проверке всех определений с одним предикатом, двумя предикатами и т.д. до тех пор, пока не будет найдено совместимое определение. Предполагается, что используется простое представление на основе атрибутов, аналогичное тому, которое использовалось при обучении деревьев решений в главе 18. Определение d будет представлено с помощью множества атрибутов в левой части, поскольку предполагается, что целевой предикат остается постоянным. Основной алгоритм, соответствующий этому подходу, приведен в листинге 19.3.
Листинг 19.3. Алгоритм поиска минимального совместимого определения
function Minimal-Consistent-Det{Е, A) returns множество атрибутов inputs: Е, множество примеров
А, множество атрибутов с количеством элементов п
for i <— 0 ,..., п do
for each подмножество Ai множества А с количеством элементов i do if Consistent-Det?(Ai, E) then return Ai
function Consistent-Det?(A, E) returns истинностное значение inputs: А, множество атрибутов
некоторый пример в таблице Я имеет такое же значение множества атрибутов А, что и пример е, но имеет другую классификацию then return false сохранить обозначение класса примера е в таблице Я под
индексом, соответствующим значениям атрибутов А примера е return true