Временная сложность этого алгоритма зависит от размера наименьшего совместимого определения. Предположим, что это определение включает р атрибутов из общего количества, равного п атрибутам. В таком случае алгоритм не отыщет данное определение до тех пор, пока не выполнит поиск во всех подмножествах А с размером р. Количество таких подмножеств измеряется значением
( П ) = 0(пр) , Р
поэтому сложность алгоритма зависит экспоненциально от размера минимального определения. Как оказалось, данная задача является NP-полной, поэтому не следует рассчитывать на то, что в общем случае будет достигнута более высокая производительность. Тем не менее во многих проблемных областях существует локальная структура (понятие локально структурированных проблемных областей рассматривается в главе 14), благодаря которой р становится небольшим.
Получив в свое распоряжение алгоритм изучения определений, обучающийся агент приобретает способность создавать минимальную гипотезу, с помощью которой он может изучать целевой предикат. Например, можно скомбинировать алгоритм Minimal-Consistent-Det с алгоритмом Decision-Tree-Learning. Это приведет к созданию алгоритма обучения дерева решений с учетом релевантности, RBDTL (Relevance-Based Decision-Tree Learning), в котором вначале определяется минимальное множество релевантных атрибутов, а затем это множество передается алгоритму формирования дерева решений для обучения. В отличие от алгоритма Decision-Tree-Learning, алгоритм RBDTL одновременно обеспечивает и обучение, и использование информации о релевантности для минимизации своего пространства гипотез. Можно рассчитывать на то, что алгоритм RBDTL даст возможность проводить обучение быстрее по сравнению с алгоритмом Decision-Tree-Learning, и действительно так и происходит. На рис. 19.6 показана производительность обучения для этих двух алгоритмов на основе случайно сгенерированных данных для функции, которая зависит только от 5 из 16 атрибутов. Ясно, что в тех случаях, когда все доступные атрибуты являются релевантными, алгоритм RBDTL не показывает каких-либо преимуществ.
В данном разделе приведены лишь самые основные сведения из области исследования декларативного смещения, задача которой состоит в изучении того, как могут использоваться априорные знания для выявления приемлемого пространства гипотез, в котором должен осуществляться поиск правильного целевого определения. В нем не даны ответы на многие вопросы, например, на те, которые приведены ниже.
• Как могут быть дополнены эти алгоритмы для того, чтобы в них учитывался шум?
• Можно ли обеспечить обработку переменных с непрерывными значениями?
• Можно ли использовать другие виды априорных знаний, кроме определений?
• Как можно обобщить эти алгоритмы для охвата любой теории первого порядка, а не только представлений на основе атрибутов?
Некоторые из этих вопросов рассматриваются в следующем разделе.