ДОКЛАДЫ АКАДЕМИИ НАУК, 2010, том 432, № 4, с. 465-468
ИНФОРМАТИКА
УДК 681.3+519.7
О НЕКОТОРЫХ КОНСТРУКТИВНЫХ И КОРРЕКТНЫХ КЛАССАХ АЛГЕБРАИЧЕСКИХ ЕП-АЛГОРИТМОВ
© 2010 г. З. М. Шибзухов
Представлено академиком Ю.И. Журавлевым 19.08.2009 г. Поступило 31.08.2009 г.
В настоящей работе рассматриваются абстрактные классы ЕП-алгоритмов, которые обрабатывают информацию, кодируемую в одном классе алгебр с нулем и единицей. Устанавливается, что в этих классах при определенных условиях корректно разрешима задача обучения с учителем по стандартной обучающей информации. Обучение корректных [1] ЕП-алгоритмов осуществляется при помощи прямой конструктивной алгебраической процедуры построения [2], которая позволяет одновременно формировать структуру ЕП-алгоритма и настраивать его параметры, не прибегая к решению сложных оптимизационных задач для достижения корректности его функционирования. Рассматриваемый класс ЕП-алго-ритмов обобщает алгоритмы, представимые при помощи ЕП-нейронов и простых ЕП-нейронных сетей, исследованных в [3].
1. Рассмотрим класс алгебр % = %(+, •) на множестве X з {0, 1}. Операции "+" и "■" удовлетворяют условиям:
0 + х = х + 0 = х, Х1 • х2 = 0 ^ Х1 = 0 V х2 = 0,
X • 1 = 1 • X = X.
Для множеств отображений 91 = {/: А ^ Б(}, где I = 1, 2, ..., т (т > 1), и С = {#: Б1 х В2 х ... х Бт ^ ^ С} будем обозначать С(91, 92, ..., 9т) множество всех композиций g(fl,/,, ...,/т), где g е С,/ е 91 (1 < I < т). Для любой пары множеств отображе-
ний
9 = / А ^ Б} и С = и С , где Ст = {g: Вт ^
I = 1
Научно-исследовательский институт прикладной математики и автоматизации Кабардино-Балкарского научного центра Российской Академии наук, Нальчик
2. Рассмотрим последовательность вложений множеств функций
©0 с ©0 С ...с е...с ©0 = и
где ©^ с {Е: Х^ ^ X}, ©0 = {0}, {1ё} с ©0.
Пусть УЕ е ©0
е ©и-1
= 0 е ©0
N
Ук е {1, 2, ..., N1: Е(уь «2,
Типичный пример ©0 — класс функций, которые строятся из множества тождественных функций {1ё(«к): к е по следующим правилам композиции: 1) 8(©0, ©0) с ©0; 2) Н(©0) с ©0. Здесь {+} с 8 — множество функций а: X2 ^ X, таких что ст(5, 0) = а(0, «) = {1ё} с Н — множество функций П: X ^ X, таких что п(х) = 0 ^ х = 0.
Определим класс псевдосуммирующих функций
© = и и {Е(«1, ^
N = 1 ЕЕ ©Ц
где 1 <]1 <]2 < ... <]„ < N аъ а2,
аС[ е X.
^ С}, будем обозначать С[9] множество всех композиций g(fl,/2, ...,/т), где/1,/2, .-;/т е 9, g е Ст, т е N. Пусть также 1ё(«) =
Пусть р: X ^ У — решающая функция, где У — некоторое заданное множество (например, {0, 1, ..., О — 1} — номера классов).
Определение. р(«) допустимая относительно ©, если Уа1, а2, ..., ам—1 е X УЬ е е X: Ь ф 0 Уу е У УЕ е ©^ ЗЕ' е ©n, такая что: 1) ЕЧ* , 82, "•, sn-1, 0) = Е(81 , 82, "•, sn— 1); 2) р(Е'(а1,
а2, аN-l, Ь)) = у.
3. Рассмотрим конечную последовательность множеств функций {^т}, где — множество функций вида Xm ^ X, 1 < т < п. Пусть х = (х1, х2, ..., хп); для любого мультиндекса 1 = (¡1,12, ..., 1Г), где 1 с {1, 2, ..., п}, выражение х|1 обозначает набор
аргументов (х, ,
V Х1, ).
2
Пусть УФ(х|0 е и V/ е 1 определена операция исключения /-го аргумента д*': ^ удовлетворяющая условию
Ф(х11 )ф 0 ^(д*'Ф)(х|Г)ф 0, (1)
где 1' = 1\{ /}.
Рассмотрим последовательности функций {Фк(х|1к) с где {1к} — последовательность муль-тииндексов. Пусть задана последовательность
{хЛ с X".
Определение. {Фк(х|1к)} треугольно упорядочена на хк, если 1) V] < к: Фк(ху- |1к) = 0; 2) Vk: Фк(хк|1к) ф 0.
Обозначим ^{хк} класс всех последовательностей {Фк(х|1к)} с треугольно упорядоченных на {хк}.
Пусть X" — некоторый класс конечных множеств {х} с X".
Определение. допустимый для X", если для любого конечного множества {х} е X" можно, пронумеровав его элементы, построить последовательности {хк} и {Фк(х|1к)} е ^{хк}.
Пусть {Фк(х|1к)} е ^{хк}. Рассмотрим нетривиальные преобразования {Фк(х|1к)} ^ {Фк(х|!к)},
где Фк = Фк и 1к = 1к или Фк (х| 1к) получается из Фк(х|1к) в результате последовательного исключения некоторых аргументов, а 1к получается из 1к исключением индексов из аргументов Фк(х|1к). Оно допустимое, если {Фк (х| 1к)} е ^{хк}. Последовательность {Фк(х|1к)} е ^{хк} существенная, если не существует применимого к ней допустимого преобразования. В силу (1), для любой несущественной последовательности {Фк(х|1к)} е ^{хк} при помощи допустимых преобразований можно построить существенные последовательности {Фк(х| 1* )} е ^{хк}, такие что 1к с 1к.
4. Рассмотрим класс функций, которые
будем называть алгебраическими ЕФ-функция-ми. Определим р(©[^"]) — класс алгебраических ЕФ-алгоритмов, который состоит из композиций вида р(ЕФ), где ЕФ е ©[$"].
Рассмотрим задачу обучения с учителем по стандартной обучающей информации Д{хк}, {ук}), где последовательность {хк} е X" и соответствующая ей последовательность {ук} с У, где к = 1, 2, ..., N.
Определение. ЕФ-алгоритм 8Га корректный для Д{хк}, {ук}), если Vk: 81а(хк) = ук.
Рассматриваем задачу построения ЕФ-алго-ритма 81а(х), корректного на Д{хк}, {ук}). Построение начинается с некоторого начального ЕФ-ал-
горитма 81а0 = р(ЕФ0), где ЕФ0 — произвольная ЕФ-функция (например, константа). Перед началом или в процессе обучения строится последовательность функций {Фк(х|1к)} е ^{хк}. В процессе обучения строим последовательность ЕФ-алго-ритмов {8Гак(х)}, где
^к = р(Ек(Ф1,Ф2, ...,Ф„)).
Если 8Гак—1 (хк) = Ук, то Е^, «2, -, «к) = Ек-1(^1, «2, ••, «к — 1).
Если 8Гак- 1(хк) ф ук, то Ек^ь б2, ..., «к) выбирается так, чтобы
Ек (51, 5 2, 5к - 1, 0 ) = Е к - 1 (51, 5 2, 5к - 1) , а также выполнялось равенство
У к = р(Ек( 02, ..., йк - 1, йк)) ,
где а. = ФДхк) для всех] = 1, 2, ..., к. Если р допустимая относительно ©, то всегда найдется такая функция Ек(«1, «2, «к) е ©.
Лемма. Vk V] < к: 8Гак(ху) = у.
При помощи допустимых преобразований строятся множества существенных последовательностей функций {Фк(х|1к)} е ^{хк} и, таким образом, множество ЕФ-алгоритмов ^а(х)}, корректных для Z({xk}, {ук}). Затем применяются процедуры взвешенного голосования или линейные (выпуклые) корректоры для повышения надежности функционирования ЕФ-алгоритмов, а также производится отбор наиболее оптимальных по дополнительным (внешним) критериям качества.
Введем понятие корректного класса ЕФ-алго-ритмов.
Определение. р(©[^"]) — корректный на X", если для любой задачи Д{хк}, {ук}) существует и может быть эффективно построен корректный ЕФ-алгоритм 8Га.
Теорема 1. Если р допустимая и допустимый для X", то класс р(©[^"]) корректный на X".
5. Рассмотрим некоторые классы алгебраических псевдомультиплицирующих функций. Рассмотрим последовательность вложений множеств функций
^0 с ^0 с.с ^ с.с ^0 = и
где ^ с {П: X" ^ X}, ^0 = {1}, М с ^0.
Пусть VП е V/ е {1, 2, ..., "}: П(х1, х2, ...
"•, Х")|*' = 1 е ^0 .
Типичный пример — класс функций, которые строятся из множества тождественных функций {1ё(х(): / = 1, 2, ... } по следующим правилам
О НЕКОТОРЫХ КОНСТРУКТИВНЫХ И КОРРЕКТНЫХ КЛАССАХ
467
композиции: 1) Р(^0, ^0) с 2) с
Здесь {•} с Р — множество функций я: X2 ^ X, таких что
я(*1, *2) = 0 о *1 = 0 V *2 = 0,
п(х, 1) = я( 1, *) = *; {1ё} с Е — множество функций X ^ X, таких что Х(х) = 0 о * = 0, х( 1) = 1.
Определим класс псевдомультиплицирующих функций
^ = U U {П(*1, Xn) I
n = 1 П е
= } '
где 1 < i1 < i2 < ... < ir < n, a1, ..., ar e X. Пусть с с ^ — подмножество всех функций, зависящих не более чем от n независимых аргументов.
Пусть ^ — некоторый класс функций. Определим — класс алгебраических ПФ-функций. Алгебраический ЕП-алгоритм реализует композицию spa = p(spf), где spf e ©№]. Алгебраический ЕПФ-алгоритм реализует композицию spa = = p(spf), где spf e ©[?[$]].
Из алгебраических псевдомультиплицирую-щих функций при некоторых предположениях можно эффективно строить треугольно упорядоченные последовательности. На их основе конструктивно строятся алгебраические ЕП-алгорит-мы и ЕПФ-алгоритмы, корректные на обучающей информации. Рассмотрим примеры.
6. Пусть задана последовательность {хк} с Xn и последовательность мультииндексов {ik}, где ik с с{1, ..., n}.
Определение. хк упорядочена по нулям относительно {ik}, если: 1) Vi e ik xki Ф 0; 2) Vj < k 3/: xki Ф 0 л xп = 0.
Последовательность {xk} упорядочена по нулям, если она упорядочена по нулям относитель-
г 1 I- , ni
но {ik}, где ik = {i: хш Ф 0}.
Класс последовательностей, упорядоченных по нулям, обозначим ЖО.
Пусть задана последовательность функций {Щх^)}, где Пк e
Лемма. {Пк(х^)} e ^{Хк} ^ {Хк} упорядочена по нулям относительно {ik}.
Теорема 2. Если р допустимая относительно ©, то класс ЕП-алгоритмов © [^n] корректен на Ж о.
7. Не всякое конечное подмножество X" можно упорядочить по нулям. Однако можно построить преобразование, переводящее исходное множество в множество разреженных векторов, которое можно упорядочить по нулям, например используя метод покрытий.
Пусть задано некоторое конечное множество {ик} с X" и некоторое конечное покрытие {ик} с ь
с и ир , разделяющее векторы из {ик}, т.е. V] ф к
р = 1
Зр: и. е ир л ик ё ир.
Пусть для каждого р определена функция Фр(и), такая что фр(и) = 0 о и ё ир. Пусть 1к = = {/: ик е и}. Определим преобразование ф(и) = = (ф1(и), ф2(и), ..., Фх(и)). Тогда {хк}, где хк = ф(ик), можно упорядочить по нулям относительно {1к}.
8. Пусть на X задано отношение линейного порядка >. Для любой пары векторов х' и х'' из X" и мультииндекса 1 с {1, 2, ..., "} определим отношения > и 3 относительно 1.
Определение. х' 3 х''(1), если З/ е 1: 3 . Определение. х' > х''(1), если V/ е 1: > .
Введем понятие 3-упорядоченной относительно {1к} последовательности векторов хк.
Определение. {хк} 3-упорядоченная относительно {1к}, если V] < к: х. 3 хк(1к). Последовательность {хк} 3-упорядоченная,
если она 3-упорядоченная относительно {1к}, где 1к = {/: (З]: Х/ < хк/)}. Класс 3-упорядоченных последовательностей обозначим X%. .
Введем понятие 3-упорядоченной пары последовательностей относительно {1к}.
Определение. Последовательности {хк} и {ак} образуют ^-упорядоченную пару относительно {1к}, если: 1) V] < к: ху- 3 ак(1к);
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.