ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 3, с. 547-552
УДК 519.714
ПРЕДИКАТНОЕ ЗАДАНИЕ УНИВЕРСАЛЬНЫХ ОГРАНИЧЕНИЙ В АЛГЕБРАИЧЕСКОМ ПОДХОДЕ К ЗАДАЧАМ РАСПОЗНАВАНИЯ
© 2007 г. Р. С. Таханов
(119991 Москва, у. Вавилова, 40, ВЦ РАН) e-mail: takhanov@mail.ru Поступила в редакцию 09.06.2005 г. Переработанный вариант 17.07.2006 г.
В рамках алгебраического подхода к проблеме распознавания и на основании теории локальных и универсальных ограничений предлагается описывать универсальные ограничения как множества отображений, сохраняющих m-местные предикаты. Показано, что симметрические и функциональные ограничения допускают подобное описание. Библ. 3.
Ключевые слова: обучение по прецедентам, распознавание образов, алгебраический подход, теория локальных и универсальных ограничений.
1. ВВЕДЕНИЕ
Согласно [1], проблема распознавания заключается в том, чтобы построить отображение из множества объектов (описаний объектов) в конечное множество ответов, удовлетворяющее локальным и универсальным ограничениям. Локальные ограничения, как правило, формулируются в следующем виде: задано конечное множество прецедентов - пар вида "объект-ответ", и требуется построить отображение, которое на каждом из этих объектов выдает соответствующий ему ответ. Универсальные ограничения в общем случае задаются как некоторое подмножество всех отображений (например, множество всех монотонных относительно некоторого частичного порядка отображений).
В алгебраическом подходе (см. [2]) требуемое отображение строится в виде суперпозиции алгоритмических операторов, корректирующих операций и решающего правила таким образом, чтобы универсальные ограничения выполнялись "по построению". Необходимые и достаточные условия существования таких отображений в наиболее общем виде, на языке теории категорий, получены в теории универсальных и локальных ограничений.
В работах [1], [3] рассматривались различные виды универсальных ограничений: симметрические, функциональные и монотонные. В данной работе предлагается новый, более общий способ описания универсальных ограничений, формулируемый как условие сохранения заданных га-местных предикатов. Показывается, как построить эти предикаты, чтобы описать симметрические, функциональные и монотонные универсальные ограничения в рамках предлагаемого формализма.
Пусть задано Я, - множество объектов и Яу - множество возможных ответов. Универсальные ограничения Iй,, задаются, как подмножество М[ Iй,, ] множества отображений из ^^ в Яу, т.е.
М[ I]1 ] с М = { а : —- Я у}. Локальные ограничения М[ 1[ ] задаются, как множество отображений
М[4 ] = { а : Я,^ Я у; а (х,) = у,, , = 1, п }, где (х, у,), = 1 - конечное множество прецедентов, xi е Я,, у, е Яу.
Требуется найти отображение (если оно существует) а* е М[Iй,, ] п М[ 1[ ]. Любое такое а* принимается как решение задачи.
В алгебраическом подходе наряду с множествами Я, и Яу вводится пространство оценок Я,
Затем выбирается множество алгоритмических операторов Ш0 с М* = {Ь : Я, —- Яе}, семей-
547 13*
e'
ство решающих правил Ш1 с ^^ =1 {c : —► ^у} и семейство корректирующих операций ^ с ^^ =1{у: —" Все семейства выбираются так, чтобы выполнялось включение
° с м[ ].
2. ПРЕДИКАТНОЕ ЗАДАНИЕ УНИВЕРСАЛЬНЫХ ОГРАНИЧЕНИЙ
В общей теории универсальных и локальных ограничений (см. [1]) универсальные ограничения рассматриваются как некоторые специальные категории, называемые допустимыми. Допустимые категории характеризуются следующими свойствами.
1. Объекты категории - некоторые множества и всевозможные декартовы степени этих множеств, морфизмы - отображения.
2. Если у : Л" —► Вт - морфизм из объекта Л" в объект Вт, то у^(х) = У(х, ..., х) - морфизм из объекта А в объект Вт.
3. Если у: Л" —► Вт и g : Лр —► Вд - морфизмы, то У х g : Л" +р —► Вт + д, определяемый в виде Ух g(Xl, ..., X",у1, ...,ур) = (Ух1, ..., X"), g(yl, ...,ур)), - тоже морфизм.
Покажем, как с помощью т-местных предикатов можно задавать категории такого типа.
Определение 1. Пусть на множествах Л и В заданы т-местные предикаты рЛ и рВ, т.е. рЛ с Лт и рВ с Вт. Тогда будем говорить, что функция ф : Л —- В сохраняет пару (рЛ, рВ), если У(х1, ..., хт) е е рЛ —► (ф(х1), ..., ф(хт)} е рВ. Множество функций, сохраняющих пару (рЛ, рВ), будем обозначать через Н(рЛ, рВ).
Следующее очевидное свойство предикатного задания и определяет его выбор в качестве языка описания соответствующих универсальных ограничений.
Предложение 1. Если У: Л —- В сохраняет пару (рЛ, рВ), а g : В —- С сохраняет пару (рВ, рс), то g ° у сохраняет пару (рЛ, рс).
Определение 2. Пусть на множестве Л задан т-местный предикат рЛ. Тогда назовем 5-й степенью рЛ и через рЛ обозначим т-местный предикат на Л5 такой, что ((а1, ..., а1), ..., (ат, ..., а^)} е
5 . ~Л /1 т ч
е рЛ ^ V/ = 1, 5 (а, , ..., а, ) е рЛ.
Рассмотрим некоторый класс множеств I. Пусть на каждом множестве Л е I задан т-местный предикат рЛ, и пусть дана категория ¥(! р), объектами которой являются множества А и их декартовы степени Л5, 5 = 1, 2, 3, ..., а множества морфизмов для любых Л, В е I и 5, г е N определяются равенством Иош(Л5, Вг) = Н(рЛ , рВ). То, что ¥ - категория, следует из предложения 1 и
из того, что ТА : Л5 —- Л5 (единичный оператор) сохраняет (рЛ , рЛ), т.е. ТА е Нош(Л5, Л5). Допустимость этой категории очевидна из построения. Скажем, что категория ¥(1, р) порождена классом всех таких пар (Л, рЛ}. Обозначим этот класс через $:(!, р).
Рассмотрим примеры категорий, порождаемых классами р).
2.1. Ограничения монотонности
Пусть каждому множеству А из класса I поставлен в соответствие частичный порядок >Л на этом множестве. Категория (I, >), порожденная классом >), формализует универсальные ограничения монотонности.
2.2. Симметрические ограничения
Следуя [3], рассмотрим множество ©^ ¡(Л) - множество матриц q х I над множеством Л, и пусть I- класс всех множеств ©^ ¡(Л). Пусть нам дана некоторая подгруппа £ = {е, 51, ..., 5к} группы подстановок Sqt 1 над {(1, 1), (1, 2), ..., ¡)}.
Для и е © (Л) и 5 е Sqt 1 положим 5(||Ц4, ¡) = I и для иъ ..., Ц е (Л) и 5 е Sqt I положим
5Ц ..., Ц) = {5(Ц), ..., 5(Ц)).
Напомним, что симметрической категорией, соответствующей группе S, называется категория классом объектов которой служат множества матриц ©«, (А) над произвольными множествами А и их декартовы степени ©«, I (А), а множества морфизмов определяются в виде
Нош^(©«,(А), ©«,(В)) = {ф : ©«,(А)^ ©«,¿(В) \ V, = 1Д, чие ©«,(А) Ф(8(10)) = *(Ф(и))}.
Теперь для каждого множества ©«, (А) определим к + 1-местный предикат рА = {(О, ^(О), ... ..., 8к(0)) | О е ©«, ¿(А)} с ©«,+1 (А). Легко видеть, что г-я степень предиката рА есть ргА = {(О,
^(О), ..., 8к(0)) | О е ©«,I(А)} с (©«,I(А))к + 1 Таким образом, класс Ш(1, р) определяет категорию ¥(!, р). Тогда справедливо
Предложение 2. Справедливо соотношение
Ноштр)(©«, (А), ©I (В)) =
= {ф : ©«,¿(А) —-©«,¿(В) \ V, = ТД, VIе ©«,I(А) ф((О)) = *(ф(О))}.
Доказательство. По определению,
нош¥у,р)( ©«, ¿(А), ©«, (В)) =
= {ф : ©«,¿(А) —► ©«,¿(В) \ ЧОе ©«,¿(А) ЗУ е ©«,¿(В) (ф(О) = V) л (V, = 1Д ф^О)) = *,(У))} =
= {ф : ©«,¿(А) —► ©«,(В) \ ЧОе ©«, 1 (А), V, = Тд ф(О)) = *(ф(О))}.
Утверждение доказано.
Таким образом, ¥(!, р) = т.е. категория ¥(1, р) определяет симметрические ограничения, введенные в [3].
2.3. Функциональные ограничения
Пусть дана некоторая сигнатура ф = (§>(!, §(^ 2), -., §(«, г>, X), где §(,,у) - линейно упорядоченные подмножества множества § = {(1, 1), (1, 2), ..., («, /)}, а X : § —► {1, 2, ..., , t < «Д причем [Х(,ьу\) = Х(,2,Л)] —- | §(,Т,]Т) | = |§(,2,у2) |. Следуя [3], обозначаем 2(,,у) = §у) и к-й элемент §(,,у) -
как у, к), а также V?" е {1, 2, ..., t} z(r) = г(, (г),у(г)), если Х(, (г),у(г)) = г. Оставим объекты теми же и определим множество отображений в виде
Ф(©«, 1 (А), ©; 1 (В)) = {и : ©; 1 (А) ©«, 1 (В) I З/П : Аг(п)г —-В, к = й, п = й,
и (11 Оь\\ч, I, •••' II) = (|| И^уИ«, г^ ^у = у)( ОЕ;(,, у, 1), •••> ОТ(,, у, г(,, у)), •••, О$(г, у, г(,, у))) } .
В [3] было показано, что полученная структура будет категорией (ее обозначают через ¥ф), если и только если будут выполнены следующие условия:
1) V(i,у) е § — (,,у) е §(,,у);
2) [Х(,У,у\) = Х(,2,72)] Л [(,!,ух) = 7!, к)] — [(,2,72) = ^2,у2, к)];
3) [Х(,у, у\) = Х(,2, уз)] — у1, к)) = Х(^(,2, у2, к))];
4) С,у) е §(,2,у2) — §(у.) с §(,2,у2);
5) [Х(,у, у1) = Х(,2, Уг)] — у1, к), к1) = у1, к2) ^ ^(^(,2, у2, к), к1) = ^(,2, у2, кг)]. Предложение 3. При выполнении условий 1) и 4), а также при Х(,1,у1) = Х(,2,у2) о (,у,у2) = (,2,у2)
множество Ф можно переписать в следующем виде:
Ф(©«,I(А), ©«,I(В)) = ПФ,,у,
,,у
где Ф,,у - множество функций таких, что элементы с индексами из §(,,у) матриц образа зави-ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ том 47 < 3 2007
сят только от элементов с индексами из §(;,;) прообраза, т.е.
Ф, ; = { u : l (A ©'q> (B) | V|| Ul\\q, „ ||FjJ q, „ • .., \\Ul\\q, „ \\Vrtv\q, , I Vp = tT
Up(;, J, T) = Vp(;, j, T), •••, Up(;, j, z(i, j)) = Vp(;, j, z (;, j)) "Vi = T, Z (¡, J) ( u (|| UTv|| q, l, •••, llUiv|| q, l) j, i) = ( u (ll VJ q, l, •"> llViv|| q, l ))^(i, j, i) } •
Доказательство. Пусть Ф- j - множество функций таких, что элементы с индексом (i, j) матриц образа зависят только от элементов с индексами из S(jJ) матриц прообраза, т.е.
Ф),j = {u : ©q,l(A©q,l(B) I 3f,; (u(||UTJq,, • .., I\Urtv\\q,l)),j =
= fi, j ( UT(i, j, T), •••, UT(), j, z( i, j)), •••, U^( i, j, z (i, j)))} •
Очевидно, что Ф; j с Ф' j, так как (i, j) е §(;, j) по свойству 1). Отсюда имеем
пФ), j спФ), j = Ф(©q,l(A), ©sq,l(B))• i, j i, j
Обратное вложение также верно, так как, по свойству 4), имеем (ii,ji) е §(;-2, J2) —► S^, j) с §(;-2, J2),
т.е. элементы с индексами из S(i, ;) матриц образа зависят только от элементов с индексами из
S( i2, j) матриц прообраза. Утверждение доказано.
Предложение 4. При удовлетворении условий, 1)-5) множество Ф можно описать в следующем виде:
Ф( ©q, l (A ), ©sq, l ( B )) = П Фг, j,r, J,
i, ■ ;i , j : мi, j) = M;', j)
где Ф;,; ¡' j' - множество функций таких, что функ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.