Определение пространства гипотез

Хотя определения позволяют обосновать общие заключения, касающиеся всех бразильцев или всех образцов меди, исследуемых при заданной температуре, они, безусловно, не позволяют создать на основании одного примера общую прогностическую теорию, которая распространялась бы на граждан всех государств или на любые материалы, исследуемые при любых температурах. По существу, основной эффект применения определений можно рассматривать как ограничение пространства гипотез, которые должен рассматривать обучающийся агент. В частности, согласно определению, при прогнозировании проводимости достаточно учитывать только материал и температуру, но игнорировать массу, права собственности на рассматриваемый образец, день недели, фамилию главы правительства и т.д. Но гипотезы, касающиеся проводимости, безусловно, могут включать термы, которые в свою очередь зависят от материалы и температуры, в том числе учитывающие молекулярную структуру, тепловую энергию или плотность свободных электронов. Определения задают базовый словарь, достаточный для построения гипотез, касающихся целевого предиката. Это утверждение можно доказать, продемонстрировав, что данное конкретное определение логически эквивалентно утверждению о том, что правильная формулировка целевого предиката является одной из множества всех формулировок, которые могут быть представлены с помощью предикатов из левой части определения.
Интуитивно ясно, что сокращение размера пространства гипотез должно способствовать упрощению задачи изучения целевого предиката. Возможный при этом прирост эффективности можно оценить с использованием основных результатов теории вычислительного обучения (см. раздел 18.5). Вначале напомним, что для булевых функций требуется 1од( |н| ) примеров, чтобы свести все пространство гипотез к одной приемлемой гипотезе, где | н | — размер пространства гипотез. Если в распоряжении ученика имеется п булевых характеристик, для которых должны быть построены гипотезы, то в отсутствии дополнительных ограничений |н|=0(22 ), поэтому необходимое количество примеров составляет О (2П). Если же в левой части определения находятся d предикатов, то для ученика потребуется только 0(2d) примеров, что соответствует сокращению в 0(2n_d) раз. Для смещенного пространства гипотез, такого как конъюнктивно смещенное пространство, это сокращение будет не столь радикальным, но все еще достаточно существенным.







Материалы

Яндекс.Метрика