An Approach to the Construction of a Level Description of Classes by Means of a Predicate Calculus Language

УДК 004.93.51 Т.М. КОСОВСКАЯ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ ПОСТРОЕНИЯ МНОГОУРОВНЕВОГО ОПИСАНИЯ КЛАССОВ НА ЯЗЫКЕ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ Косовская Т.М. Подход к решению задачи построения многоуровневого описания классов на языке исчисления предикатов. Аннотация. Рассматривается задача построения многоуровневого описания классов, объекты которых характеризуются свойствами своих элементов и отношениями между ними. Задачи распознавания и анализа таких объектов являются NP-трудными, но при наличии достаточно коротких и часто встречающихся подформул в описаниях классов можно построить многоуровневое описание классов, существенно понижающее значение показателя степени в оценках числа шагов алгоритмов, решающих эти задачи. До сих пор выделение таких подформул оставлялось на усмотрение разработчика системы распознавания. В работе предлагается подход к их автоматическому выделению. Ключевые слова: исскуственный интеллект, предикатные формулы исчисления, сложность алгоритма, NP-полнота, уровневое описание классов. Kosovskaya T.M. An approach to the construction of a level description of classes by means of a predicate calculus language. Abstract. A problem of construction of a level description of classes with objects characterized by properties of their elements and relations between them is under consideration in the paper. The problems of recognition and analysis of such objects are NP-hard, but if descriptions of classes contain short enough and frequently occurred sub-formulas then it is possible to build a level description of classes essentially decreasing an exponent in upper bounds of steps for an algorithm solving the problemr. Usually an extracting of these sub-formulas is leaved to the investigator will. An approach to their automatic extraction is proposed in the paper. Keywords: artificial intelligence, predicate calculus formulas, complexity of algorithm, NPcompleteness, level description of classes. 1. Введение. В работе рассматриваются такие задачи искусственного интеллекта, как распознавание образов и прогнозирование, допускающие формализацию средствами исчисления предикатов при условии, что объект рассматривается как совокупность своих элементов. Такой подход к решению сформулированныъ задач назван логикопредметным. Для рассматриваемых задач в [3, 6] доказано, что они являются NP-трудными. Для уменьшения числа шагов их решения в [4] предложено создание уровневого описания классов, заключающееся в выделении «часто» встречающихся среди исходных описаний классов подформул «небольшой сложности». Термины «часто» и «небольшой сложности» уточняются в зависимости от алгоритма, с помощью которого решается поставленная задача. В частности, в этих работах доказаны условия уменьшения числа шагов при использовании уровневого описания 204 SPIIRAS Proceedings. 2014. Issue 3(34). ISSN 2078-9181 (print), ISSN 2078-9599 (online) www.proceedings.spiiras.nw.ru классов для переборного алгоритма и для алгоритмов, основанных на построении вывода в исчислении предикатов. Примеры, приведённые в [4], иллюстрируют существенное уменьшение числа шагов распознавания контурного изображения на сложной сцене при введении двухуровневого описания, основанного на «здравом смысле». Ниже предлагается подход к решению задачи построения уровневого описания классов, базирующийся на применении понятия неполной выводимости предикатной формулы, введённого в [5] для решения задач распознавания объектов с неполной информацией при логикопредметном подходе. Рассматривается модельный пример построения трёхуровневого описания классов по имеющемуся исходному описанию. 2. Общая постановка задачи. Пусть исследуемый объект представлен как множество своих элементов ω = {ω1 , . . . , ωt }. На ω задан набор предикатов p1 , . . . , pn , характеризующих свойства элементов ω и отношения между ними. Логическим описанием S(ω) объекта ω называется множество всех атомарных формул или их отрицаний, истинных на ω. Множество всех объектов разбито на классы Ω = ∪K k=1 Ωk . Логическим описанием класса называется формула Ak (x), заданная в виде дизъюнкции элементарных конъюнкций, такая что если Ak (ω) истинна, то ω ∈ Ωk .1 С помощью построенных описаний объектов и классов предлагается решать следующие задачи. Задача идентификации. Проверить, удовлетворяет ли объект ω или его часть описанию класса Ak (x) и предъявить эту часть объекта. Задача классификации. Найти все такие номера k, что верна формула Ak (ω). Задача анализа. Найти и классифицировать все части τ объекта ω, для которых Ak (τ ). Решение задач идентификации, классификации и анализа для распознавания сложного объекта сведено в к доказательству соответ1 Здесь и далее посредством x обозначается список элементов конечного множества x, соответствующий некоторой перестановке номеров его элементов. Тот факт, что элементами списка x являются элементы множества y, будем записывать в виде x ⊆ y. Труды СПИИРАН. 2014. Вып. 3(34). ISSN 2078-9181 (печ.), ISSN 2078-9599 (онлайн) www.proceedings.spiiras.nw.ru 205 ственно логических следований2 : S(ω) ⇒ ∃x6= Ak (x), S(ω) ⇒ M _ (1) Ak (ω), (2) ∃x6= Ak (x). (3) k=1 S(ω) ⇒ M _ k=1 Строго говоря, вместо формул (1), (2), (3) следовало бы писать соответственно: S(ω) ⇒ (?x6= ) Ak (x), (1′ ) M S(ω) ⇒ (?kk=1 )Ak (ω), (2′ ) M )(?x6= ) Ak (x), S(ω) ⇒ (?kk=1 (3′ ) но рассматриваемые алгоритмы доказательства логических следований не только отвечают на вопрос «существвует ли ... ?», но и предъявляют значения для переменных. При решении задач медицинской диагностики в качестве множеств ω выступают пациенты, рассматриваемые как множество своих частей (органов), а исходные предикаты pi — свойства этих частей и отношения между ними, обычно называемые симптомами. В этом случае классы объектов — это классы заболеваний или синдромы. Решение задач идентификации, классификации и анализа в этом случае сводится к доказательству тех же самых формул и соответствуют таким задачам как «обладает ли пациент заданным заболеванием (синдромом) и какие именно симптомы каких органов влекут это заболевание?», «какими заболеваниями (синдромами) страдает заданный орган?», «какие области пациента какими заболеваниями (синдромами) обладают?». При решении задач анализа рынка в качестве множеств ω выступают множества субъектов и объектов рынка, исходные предикаты pi — свойства этих объектов и субъектов, а также отношения между ними. 2 Для того, чтобы записать, что значения для переменных списка x, удовлетворяющие формуле A(x), различны, вместо формулы: m ∃x1 ...∃xm (&m i=1 &j=i+1 (xi 6= xj ) & A(x1 , ..., xm )) , будет использоваться обозначение: ∃x6= A(x). 206 SPIIRAS Proceedings. 2014. Issue 3(34). ISSN 2078-9181 (print), ISSN 2078-9599 (online) www.proceedings.spiiras.nw.ru Описания классов могут задавать желаемые (или негативные) ситуации на рынке. Решение задач идентификации, классификации и анализа в этом случае сводится к доказательству тех же самых формул и соответствуют таким задачам как «какие объекты рынка влияют на то, что при имеющемся состоянии рынка будет получена заданная ситуация?», «какие ситуации следуют из заданных свойств объектов рынка?», «какие подмножества объектов рынка к каким ситуациям приводят?». Можно привести ещё много задач искусственного интеллекта, решение которых является решением сформулированных задач и сводится к доказательству логических следований (1), (2), (3). Заметим, что для того, чтобы уметь доказывать (1), (2), (3), достаточно уметь доказывать логическое следование: S(ω) ⇒ ∃x6= A(x), (4) где A(x) — элементарная конъюнкция атомарных формул и их отрицаний. В [3, 6] доказаны оценки числа шагов алгоритмов, решающих задачу (4), а также задачи (1), (2), (3). Так, например, для алгоритма полного перебора всех возможных подстановок констант из ω вместо переменных из A(x), число шагов P2n составляет Am t · i=1 ai · (si + 1), где t – число элементов в ω, m – количество переменных в A(x), si , ai – количества вхождений атомарных m формул с предикатом pi в S(ω) и в A(x) соответственно, Pn At – число m размещений из t по m. Эта оценка составляет O(t · i=1 ai · (si + 1)). Для алгоритмов, основанных на построении вывода в исчислеa1 a an нии предикатов [?]cl), Pn оценки имеют вид O(s1 · ... · sn ) = O(s ), где s = maxi (si ), a = i=1 ai Доказана NP-полнота задач (1), (2), (3) и, следовательно, NPтрудность задач (1’), (2’), (3’). 3. Многоуровневое описание классов. Для уменьшения числа шагов работы алгоритмов, решающих описанные задачи, в [4] предложено иерархическое многоуровневое описание классов распознаваемых объектов. Рассматриваются объекты, структура которых позволяет выделить достаточно простые их части и дать описание объекта в терминах свойств этих частей и отношений между ними. В частности, это можно сделать, выделяя «часто» встречающиеся подформулы Pi1 (y), формул Ak (x) «небольшой сложности». При этом записывается система эквивалентностей вида pi 1 (y 1 ) ↔ Pi1 (y), где pi 1 – новые предикаты, которые будем называть предикатами 1-го уровня, а переменные y 1 – Труды СПИИРАН. 2014. Вып. 3(34). ISSN 2078-9181 (печ.), ISSN 2078-9599 (онлайн) www.proceedings.spiiras.nw.ru 207 новые переменные для списков исходных переменных, которые будем называть переменными 1-го уровня. Обозначим предикаты, задаваемые этими подформулами, посредством p1i (i = 1, . . . , n1 ) и назовем их предикатами первого уровня. Эти предикаты при i = 1, . . . , n1 определяются равносильностями: pi 1 (x1i ) ↔ Pi1 (y 1i ). Обозначим формулы, полученные из Ak (x) путем замены всех вхождений формул вида Pi1 (y 1i ) на атомарные формулы p1i (x1i ) (при yi1 ⊆ x) посредством A1k (x1 ). Здесь x1 – список всех переменных формулы A1k (x1 ), состоящий как из некоторых (быть может всех) исходных переменных формулы Ak (x), так и из переменных первого уровня, появившихся в формуле A1k (x1 ). Такие формулы A1k (x1 ) можно рассматривать как описания классов в терминах предикатов исходного (нулевого) и первого уровней. Описанием объекта S 1 (ω) первого уровня назовем множество 1 всех атомарных формул вида p1i (ωij ), для которых истинна определя1 1 1 1 ющая подформула Pi (τij ) при τij ⊂ ω, а объект первого уровня ωij 1 представляет из себя список исходных объектов τ ij . Процедуру выделения «часто» встречающихся подформул «небольшой сложности» можно повторить с формулами A1k (x1 ). В результате построения составных предикатов (т.е. предикатов различных уровней) и многоуровневого описания классов исходная система описаний классов может быть записана с помощью равносильной ей многоуровневой системы описаний классов вида:  L AL  k (x )         p11 (x11 ) ⇔ P11 (y11 )    .   ..    1 1 pn1 (xn1 ) ⇔ Pn11 (yn1 1 ) .  .  ..       pli (xli ) ⇔ Pil (yil )     .  ..     L L pnL (xnL ) ⇔ PnLL (ynLL ) Решение рассмотренных задач распознавания может быть сведено к последовательной реализации L + 1 этапов. 208 SPIIRAS Proceedings. 2014. Issue 3(34). ISSN 2078-9181 (print), ISSN 2078-9599 (online) www.proceedings.spiiras.nw.ru 1. Для каждого j = 1, . . . , n1 осуществляется проверка выводимости из S(ω) формулы ∃x1j 6= Pj1 (x1j ) и нахождение всех таких объектов 1-го уровня, существование которых утверждается в правой части логического следования и, следовательно, истинны атомарные формулы p1j (ωj1 ). При этом будет получено описание объекта 1-го уровня S 1 (ω). .. . l. Для каждого j = 1, . . . , nl осуществляется проверка выводимоS S сти из S(ω) S 1 (ω)... S l−1 (ω) формулы ∃xlj 6= Pjl (xlj ) и нахождение всех таких объектов l-го уровня, существование которых утверждается в правой части логического следования, а следовательно истинны атомарные формулы plj (ωjl ). При этом будет получено описание объекта l-го уровня S l (ω). .. . S S L+1. Проверка выводимости из S(ω) S 1 (ω)... S L (ω) формулы, соответствующей решаемой задаче, с заменой исходных описаний классов Ak на описания классов L-го уровня AL k. Суммарное число шагов решения сформулированных задач (1), (2) и (3) складывается из числа шагов, затраченных на выполнение п.п. 1, ..., L. Следует отметить, что при реализации каждого из п.п. 1, ..., L по сути дела проверяется логическое следование вида (4). В связи с этим можно уточнить понятие «небольшая сложность». Для переборного алгоритма это означает «небольшое» количество предметных переменных в формулах. Для алгоритмов же, основанных на проверке выводимости в исчислении предикатов, «небольшая сложность» означает «небольшое» количество атомарных формул в формулах, участвующих в выполнении п.п. 1, ..., L. 4. Понятие неполной выводимости формулы. Понятие неполной выводимости предикатной формулы было введено в [5] для распознавания объектов с неполной информацией. При этом рассматривается задача проверки того, что из истинности всех формул множества S(ω) следует истинность A(x) или некоторой её максимальной подформуe лы A(y) на наборе различных констант из ω, где список переменных y является подсписком списка переменных x. e Пусть a и e a – количество атомарных формул в A(x) и в A(y) соответственно, m и m e – количество предметных переменных в A(x) и e A(y) соответственно. e Числа q и r вычисляются по формулам q = eaa , r = m m и характеТруды СПИИРАН. 2014. Вып. 3(34). ISSN 2078-9181 (печ.), ISSN 2078-9599 (онлайн) www.proceedings.spiiras.nw.ru 209 e ризуют степень совпадения формул A(x) и A(y). При этом 0 < q ≤ 1, e 0 < r ≤ 1. Кроме того, q = r = 1 тогда и только тогда, когда A(y) совпадает с A(x). Замечание. Возможен другой вариант определения чисел q и r. Каждому предикату и каждой предметной переменной формулы можно приписать их «вес», определяемые либо экспертами, либо из вероятw e , r = vve , где w и w e – сумма «весов» ностных соображений. Тогда q = w e предикатных формул в A(x) и в A(y) соответственно, v и ve – сумма e «весов» предметных переменных в A(x) и A(y) соответственно. e При таких обозначениях формулу A(y) будем называть (q, r)фрагментом формулы A(x). Задача нахождения (q, r)-фрагмента с максимально возможным значением параметра q называется задачей проверки неполной выводимости формулы. В [5] приведён один из возможных алгоритмов её решения. 5. Подход к построению многоуровневого описания классов. Понятие неполной выводимости формулы позволяет разработать подход к выделению подформул с требуемыми свойствами. 1. Для каждой пары элементарных конъюнкций Ai (xi ) и Aj (xj ), входящих в описания классов, посредством проверки неполной выводимости для Ai (xi ) ⇒ ∃xj 6= Aj (xj ) и Aj (xj ) ⇒ ∃xi6= Ai (xi ) выделяем их максимальную (с точностью до имён предметных переменных) подформулу Q1ij (xij ). 2. Повторяем процесс выделения общих подформул для l−1 Ql−1 i1 ...i2l−1 (xi1 ...i2l−1 ) и Qj1 ...j2l−1 (xj1 ...j2l−1 ), получив их общие (с точностью до имён предметных переменных) подформулы Qli1 ...i l−1 j1 ...j l−1 (xi1 ...i2l−1 j1 ...j2l−1 ) (l = 2, . . . , L). Процесс завершит2 2 ся, так как на каждой итерации длины подформул уменьшаются. 3. Выберем среди подформул Qli1 ...i l−1 j1 ...j l−1 (xi1 ...i2l−1 j1 ...j2l−1 ) 2 2 такие, которые удовлетворяют требуемым условиям и обозначим их посредством Pi1 (yi1 ) (i = 1, . . . , n1 ). 4. Формулы Pil+1 (yil+1 ) (i = 1, . . . nl+1 , l = 2, . . . , L) строятся из выделенных ранее подформул Qli1 ...i l−1 j1 ...j l−1 (xi1 ...i2l−1 j1 ...j2l−1 ) с 2 2 учётом требуемых условий. 6. Пример построения уровневого описания. Пример контурных изображений взят из [1]. Пусть имеется множество контурных изображений, составленных из отрезков прямых, задаваемых своими концами. Заданы два предиката V и L, определяемых следующим образом: 210 SPIIRAS Proceedings. 2014. Issue 3(34). ISSN 2078-9181 (print), ISSN 2078-9599 (online) www.proceedings.spiiras.nw.ru y z ❅ ✁ ❅ ✁ ❅✁ x y x V (x, y, z) ⇐⇒ (∠yxz < π) L(x, y, z, ) ⇐⇒ x лежит на отрезке с концами y и z z Задан класс контурных изображений ящика в различных ракурсах, представленных на рисунке 1. 9 9 7 6 3 1 4 a ✂ ✂ ✂ ✂ ✂✂ 10 7 8 7 3 3 4 8 ✂✂ 8 5 4 2 1 5 6 b 2 1 ❇❇ 5 c 6 3 4 2 1 10 7 8 ❇ ❇ ❇❇ ❇❇ 5 c 6 2 Рис. 1. Контурные изображения ящика в различных ракурсах Эти эталонные изображения позволяют создать описание класса почти всех контурных изображений ящика (с точностью до зеркального отображения) путём замены различных констант в их описаниях на различные переменные и выписывания знака & между атомарными формулами. Это описание класса содержит 4 элементарные конъюнкции, содержащие соответственно 10, 8, 10, 8 переменных и 30, 22, 26, 32 атомарные формулы. Так, например, элементарная конъюнкция, соответствующая изображению b, имеет вид: V (x1 , x4 , x2 )&V (x2 , x1 , x6 )&V (x2 , x6 , x3 )&V (x2 , x1 , x3 )& V (x3 , x2 , x8 )&V (x4 , x5 , x1 )&V (x4 , x6 , x1 )&V (x4 , x7 , x5 )& V (x5 , x4 , x7 )&V (x5 , x7 , x6 )&V (x6 , x2 , x5 )&V (x6 , x2 , x4 )& V (x6 , x5 , x8 )&V (x6 , x4 , x8 )&V (x6 , x8 , x2 )&V (x7 , x5 , x4 )& V (x7 , x8 , x5 )&V (x7 , x8 , x4 &V (x8 , x3 , x6 )&V (x8 , x6 , x7 )& V (x8 , x3 , x7 )&L(x5 , x4 , x6 ) . Если требуется найти изображения всех коробок на сложной сцене, содержащей t вершин, то экспоненциальный сомножитель в оценке числа шагов для переборного алгоритма имеет вид t10 , а для алгоритма, основанного на построении вывода, s32 (здесь s – максимальное число вхождений одного и того же предиката в описание сцены и приблизительно равно, но меньше, чем 3t). Труды СПИИРАН. 2014. Вып. 3(34). ISSN 2078-9181 (печ.), ISSN 2078-9599 (онлайн) www.proceedings.spiiras.nw.ru 211 Попарная проверка частичной выводимости между этими элементарными конъюнкциями позволяет выделить их общие подформулы, соответствующие изображениям на рисунке 2. 9 10 9 8 6 9 10 10 3 4 5 3 4 5 3 4 5 1 ab 2 1 ac 2 1 ad 2 9 10 9 10 7 3 4 5 3 1 bc 2 1 4 bd 8 ✂✂ 6 ❇❇ 5 3 4 5 2 1 cd 6 2 Рис. 2. Изображения, соответствующие выделенным подформулам Эти подформулы содержат соответственно 8, 8, 7, 7, 7, 8 переменных и 18, 15, 11, 11, 15, 16 атомарных формул. Последующее попарное выделение общих подформул даёт одну подформулу, содержащую 7 переменных и 11 атомарных формул, соответствующую изображению на рисунке 3. 9 3 1 10 4 5 2 Рис. 3. Изображение, соответствующее повторному выделению подформул Элементарная конъюнкция P 1 (x1 , x2 , x3 , x4 , x5 , x9 , x10 ) = V (x1 , x3 , x2 )&V (x2 , x1 , x5 )&V (x3 , x4 , x1 )&V (x3 , x5 , x1 )& V (x3 , x9 , x4 )&V (x3 , x9 , x5 )&V (x3 , x9 , x1 )&V (x5 , x2 , x4 )& V (x5 , x2 , x3 )&V (x9 , x10 , x3 )&L(x4 , x3 , x5 ), соответствующая этому изображению, определяет предикат 1-го уровня p1 (x1 ). Переменная первого уровня x1 – это переменная для списка из 7 исходных переменных. Элементарные конъюнкции P12 (y12 ), P22 (y22 ), P32 (y32 ), P42 (y42 ), соответствующие изображениям ab, ac, bd, cd и записанные с использо212 SPIIRAS Proceedings. 2014. Issue 3(34). ISSN 2078-9181 (print), ISSN 2078-9599 (online) www.proceedings.spiiras.nw.ru ванием предиката p1 (x1 ) определяют предикаты второго уровня p21 (x21 ), p22 (x22 ), p23 (x23 ), p24 (x24 ). Например, подформула P12 (y12 ) = p1 (x1 )&V (x2 , x5 , x8)& V (x2 , x1 , x8 )&V (x5 , x4 , x10 )&V (x5 , x3 , x10 )&V (x8 , x2 , x10 )& V (x10 , x8 , x5 )&V (x10 , x5 , x9 )&V (x10 , x8 , x9 ) соответствует изображению ab. Здесь y12 – переменная для списка, состоящего из переменных x1 , x1 , x2 , x4 , x5 , x8 , x9 , x10 , причём переменная 1-го уровня x1 – это переменная для списка исходных переменных x1 , x2 , x3 , x4 ,x5 , x9 , x10 . Заметим, что при определении значения для переменной 1-го уровня x1 только переменная x8 не получила значения. Если требуется найти изображения всех коробок на сложной сцене, содержащей t вершин, доказательство следования из S(ω) элементарной конъюнкции P 1 (x1 , x2 , x3 , x4 , x5 , x9 , x10 ), определяющей предикат 1-го уровня p1 (x1 ), и определение значений для переменных x1 , x2 , x3 , x4 , x5 , x9 , x10 то экспоненциальный сомножитель в оценке числа шагов для переборного алгоритма имеет вид t7 , а для алгоритма, основанного на построении вывода, s11 . При этом описание S 1 (ω) содержит столько членов, сколько на сцене имеется объектов «подозрительных» на то, чтобы быть коробкой. Пусть их t1 штук ( t1 много меньше, чем t). Элементарные конъюнкции P12 (y12 ), P22 (y22 ), P32 (y32 ), P42 (y42 ) содержат соответственно 1, 1, 0, 1 «новых» переменных и 7, 4, 4, 5 «новых» атомарных формул. Доказательство следования из S(ω) ∪ S 1 (ω) этих элементарных конъюнкций, определяющих предикаты 2-го уровня p21 (x21 ), p22 (x22 ), p23 (x23 ), p24 (x24 ) и определение значений для не более, чем одной переменной, экспоненциальный сомножитель в оценке числа шагов для переборного алгоритма имеет вид t + t1 = O(t), а для алгоритма, основанного на построении вывода, (s + t1 )7 = O(s7 ). При этом описание S 2 (ω) содержит не более членов, чем на сцене имеется объектов «подозрительных» на то, чтобы быть коробкой. Пусть их t2 штук ( t2 много меньше, чем t). Элементарные конъюнкции, полученные из описаний классов подстановкой предикатов 1-го и 2-го уровне1 вместо соответствующих подформул содержат соответственно 2, 0, 2, 2 «новых» переменных и 7, 4, 11, 16 «новых» атомарных формул. Доказательство следования из S(ω) ∪ S 1 (ω) ∪ S 2 (ω) элементарных конъюнкций, определяющих описание класса, и определение значений для не более, чем двух переменных, экспоненциальный сомножитель в оценке числа шагов для переборного алгоритма имеет вид t + t1 + t2 = O(t), а для алгоритма, основанного на построении вывода, (s + t1 + t2 )16 = O(s16 ). Труды СПИИРАН. 2014. Вып. 3(34). ISSN 2078-9181 (печ.), ISSN 2078-9599 (онлайн) www.proceedings.spiiras.nw.ru 213 Так как O(t7 )+O(t)+O(t2 ) = O(t7 ) < O(t10 ) и O(s11 )+O(s7 )+ O(s ) = O(s16 ) < O(s32 ), то как переборный алгоритм, так и алгоритм, основанный на построении вывода в исчислении предикатов, при использовании построенного двухуровневого описания классов совершают меньшее число шагов. 7. Обсуждение полученных результатов. В работе описан подход к построению уровневого описания классов, существенно уменьшающих число шагов алгоритмов, решающих NP-трудные задачи искусственного интеллекта. Этот подход основан на ранее введённом понятии неполной выводимости предикатных формул. Несмотря на то, что алгоритмы проверки неполной выводимости имеют достаточно высокие (экспоненциальные) верхние оценки числа шагов, их применение производится однократно на предварительном этапе формирования описаний классов, до начала решения основных задач. При этом число шагов алгоритмов, многократно решающих основные задачи, существенно уменьшается. 16 Литература 1. 2. 3. 4. 5. 6. Дуда Р., Харт П. Распознавание образов и анализ сцен // М.: Мир. 1976. 511 с. Клини С. Математическая логика // М.: Мир. 1973. 480 с. Косовская Т.М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестник Санкт-Петербургского университета. 2007. Сер. 1. Вып. 4. С. 82–90. Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов // Вестник Санкт-Петербургского университета. 2008. Сер. 10. Вып. 1. С. 64–72. Косовская Т. М. Частичная выводимость предикатных формул как средство распознавания объектов с неполной информацией // Вестник Санкт-Петербургского университета. 2009. Сер. 10. Вып. 1. С. 74–84. Косовская Т.М. Некоторые задачи искусственного интеллекта, допускающие формализацию на языке исчисления предикатов, и оценки числа шагов их решения // Труды СПИИРАН, 2010. Вып. 14. С. 58–75. References 1. 2. 3. 214 Duda R., Hart P. Raspoznavanie obrazov i analiz scen [Pattern recognition and scene analysis]. M., Mir. 1976. 511 p. (In Russ.). Klini S. Matematicheskaja logika [Mathematical logic]. M., Mir. 1973. 480 p. (In Russ.). Kosovskaja T.M. [Prove the estimates of the number of steps to solving some problems of pattern recognition with the logical description].Vestnik SPIIRAS Proceedings. 2014. Issue 3(34). ISSN 2078-9181 (print), ISSN 2078-9599 (online) www.proceedings.spiiras.nw.ru 4. 5. 6. of Saint Petersburg university – Vestnik Sankt-Peterburgskogo universiteta. 2007. Series 1. vol. 4. pp. 82–90. (In Russ.). Kosovskaja T.M. [Multi-level description of the classes to reduce the number of steps solving pattern recognition, described by formulas of the predicate calculus]. Vestnik of Saint Petersburg university – Vestnik SanktPeterburgskogo universiteta. 2008. Series 10. vol. 1. pp. 64–72. (In Russ.). Kosovskaja T.M. [Partial hatchability predicate formulas as a means of recognition of objects with incomplete information]. Vestnik of Saint Petersburg university – Vestnik Sankt-Peterburgskogo universiteta. 2009. Series 10. vol. 1. pp. 74–84. (In Russ.). Kosovskaja T.M. [Some problems of artificial intelligence, allowing the formalization of the language of the predicate calculus, and estimates of the number of steps to solve them]. Trudy SPIIRAN — SPIIRAS Proceedings. 2010. vol. 14. pp. 58–75. (In Russ.). Косовская Татьяна Матвеевна — д-р физ.-мат. наук, доцент, профессор кафедры информатики математико-механического факультета С.-Петербургского государственного университета (СПбГУ); ст. научн. сотр. лаборатории информационных технологий в управлении и робототехнике СПИИРАН. Область научных интересов: логический подход к решению задач искусственного интеллекта, теория сложности алгоритмов. Число научных публикаций — 78. kosovtm@gmail.com; мат-мех СПбГУ, Университетский пр., д. 28, Старый Петергоф, С.-Петербург, 198504, РФ; р.т. +7(812)428-4233; СПИИРАН, 14-я линия В.О., д. 39, г. Санкт-Петербург, 199178, РФ; р.т. +7(812)328-0421. Tatiana M. Kosovskaya — Ph.D., D.Sci., associate professor, professor of Computer Science Chair of St.Petersburg State University (SPbSU); senior researcher of Laboratory of Information Technologies in Control and Robototechniques, SPIIRAS. Research area: logical approach to the solving of Artificial Intelligence problems, theory of complexity of algorithms. Number of publications — 78. kosovtm@gmail.com; Faculty of Mathematics and Mechanics SPbSU, University av., 28, Stary Petergof, St.Petersburg, 198504, Russia; office phone +7(812)4284233; SPIIRAS, 14-th line V.O., 39, St. Petersburg, 199178, Russia; office phone +7(812)3280421. Поддержка исследований. Работа выполнена при финансовой поддержке РФФИ, проект № 14-08-01276-а. Acknowledgements. This research is supported by RFBR (grant 14-08-01276-а). Труды СПИИРАН. 2014. Вып. 3(34). ISSN 2078-9181 (печ.), ISSN 2078-9599 (онлайн) www.proceedings.spiiras.nw.ru 215 РЕФЕРАТ Косовская Т.М. Подход к решению задачи построения многоуровневого описания классов на языке исчисления предикатов. Рассматриваются задачи искусственного интеллекта, в которых исследуемый объект представлен как множество элементов со свойствами и отношениями из фиксированного множества, а также допускающие формализацию на языке исчисления предикатов. Исследуемый объект задаётся своим описанием, представленным как множество постоянных атомарных формул (или их отрицаний), истинных для этого объекта. Целевые формулы записываются в виде дизъюнкции элементарных конъюнкций атомарных формул. К рассматриваемым задачам относятся: • задача идентификации (проверить, удовлетворяет ли исследуемый объект или его часть заданной целевой формуле и предъявить эту часть объекта); • задача классификации (найти все такие целевые формулы, которые верны для исследуемого объекта); • задача анализа (Найти и классифицировать все части объекта, поддающиеся классификации). Все эти задачи NP-трудны. Построение уровневого описания целевых формул посредством выделения из них общих подформул позволяет существенно уменьшить число шагов алгоритмов, решающих рассматриваемые задачи. Такие уровневые описания соответствуют декомпозиции задачи большой размерности на несколько последовательно решаемых задач меньшей размерности. При этом в оценке числа шагов алгоритма вместо большого показателя степени экспоненты, соответствующего размерности исходной задачи, получается сумма, каждое слагаемое которой в показателе степени имеет размерность подзадачи. В настоящей статье предлагается подход к построению такого многоуровневого описания, основанного на попарном выделении общих подформул (с точностью до имён переменных) целевых формул. Такое попарное выделение общих подформул, в свою очередь, базируется на ранее введённом понятии неполной выводимости элементарной конъюнкции из множества постоянных атомарных формул. Многоуровневое описание, после попарного выделения общих подформул (с точностью до имён переменных) у элементарных конъюнкций (входящих в целевые формулы), общих подформул выделенных подформул, и т.д., строится, начиная с самых «простых» (например, с самых коротких или с зависящих от наименьшего числа переменных) подформул. Приведён модельный пример построения двухуровневого описания контурных изображений. 216 SPIIRAS Proceedings. 2014. Issue 3(34). ISSN 2078-9181 (print), ISSN 2078-9599 (online) www.proceedings.spiiras.nw.ru SUMMARY Kosovskaya T.M. An approach to the construction of a level description of classes by means of a predicate calculus language. Artificial Intelligence problems, an investigated object of which is presented as a set of elements with properties and relations from a fixed set, and permitting their formalization in predicate calculus language, are under consideration. An approach to the construction of a level description of classes of such objects is suggested. An investigated object is represented by its description as a set of constant atomic formulas (or their negations) which are true for this object. A goal formula is written in the form of disjunction of elementary conjunctions of atomic formulas. Problems under consideration are such as: • identification problem (whether an object or its part satisfies the given goal formula and extract such a part of the object); • classification problem (to find all such numbers goal formulas that are valid for the investigated object); • analysis problem (to find and classify all parts of an object which may be classified). All these problems are NP-hard. Construction of a level description for goal formulas, by means of extracting their common sub-formulas, allows essentially to decrease the number of steps for an algorithm solving a problem under consideration. These descriptions correspond to decomposition of a high-dimensional problem up to several less-dimensional sub-problems which are solved sequentially. In this case the upper bound of number of steps of an algorithm is the sum of terms with exponents equal to dimensions of sub-problems instead of one term which exponent equals to the dimension of the initial problem. An approach, based on pairwise extraction of common sub-formulas (up to the names of variables) from all goal formulas, is suggested to the construction of such a level description. This pairwise extraction of common sub-formulas is based, in turn, on the earlier introduced notion of partial deducibility of an elementary conjunction from a set of constant atomic formulas. After pairwise extraction of common sub-formulas (up to the names of variables) from elementary conjunctions (occurred in goal formulas), common subformulas of already extracted sub-formulas, ... etc. the level description is built beginning with the most «simple» (for example, the most short or containing the least number of variables) sub-formulas. A model example of construction of two-level description for contour images is presented. Труды СПИИРАН. 2014. Вып. 3(34). ISSN 2078-9181 (печ.), ISSN 2078-9599 (онлайн) www.proceedings.spiiras.nw.ru 217