поэтому сложность алгоритма зависит экспоненциально от размера минимального определения. Как оказалось, данная задача является 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 не показывает каких-либо преимуществ.

Рис. 19.6. Сравнение производительности алгоритмов RBDTL и Decision-Tree-Learning при обработке случайно сгенерированных данных применительно к целевой функции, которая зависит только от 5 из 16 атрибутов

В данном разделе приведены лишь самые основные сведения из области исследования декларативного смещения, задача которой состоит в изучении того, как могут использоваться априорные знания для выявления приемлемого пространства гипотез, в котором должен осуществляться поиск правильного целевого определения. В нем не даны ответы на многие вопросы, например, на те, которые приведены ниже.

•    Как могут быть дополнены эти алгоритмы для того, чтобы в них учитывался шум?

•    Можно ли обеспечить обработку переменных с непрерывными значениями?

•    Можно ли использовать другие виды априорных знаний, кроме определений?

•    Как можно обобщить эти алгоритмы для охвата любой теории первого порядка, а не только представлений на основе атрибутов?

Некоторые из этих вопросов рассматриваются в следующем разделе.