ИНФОРМАТИКА
519.7
О ПОТОЧЕЧНО КОРРЕКТНЫХ ОПЕРАЦИЯХ НАД АЛГОРИТМАМИ РАСПОЗНАВАНИЯ И ПРОГНОЗИРОВАНИЯ
© 2013 г. З. М. Шибзухов
Представлено академиком Ю.И. Журавлевым 14.11.2012 г. Поступило 07.12.2012 г.
ДОКЛАДЫ АКАДЕМИИ НАУК, 2013, том 450, № 1, с. 24-27
УДК
Б01: 10.7868/80869565213130069
В настоящей работе обсуждается один класс корректных операций (КО) [1, 2] над алгоритмами распознавания и прогнозирования. Корректные операции возникают в связи с проблемой построения корректных алгоритмов [3].
Корректные операции образуют значительный подкласс корректирующих операций [4]. Они обладают важным свойством — сохраняют свойство корректности алгоритмов. Это свойство является весьма полезным при построении процедур монотонно корректного обучения с возможностью порождения семейств корректных алгоритмов, таких как конструктивное обучение ЕП-нейронных сетей [5] и многослойных перцеп-тронных сетей [6]. Существует содержательная схема порождения поточечно КО.
Типичная задача поиска корректной операции возникает, когда используемый метод обучения позволяет строить множество различных алгоритмов, корректных на своем обучающем множестве и обладающих относительно хорошим качеством функционирования на контроле. В этой ситуации применение корректной операции позволяет порождать новые алгоритмы в расширенной модели алгоритмов, которые, с одной стороны, сохраняют свойство корректности на обучающем множестве, а с другой — имеют лучшее качество функционирования на контроле.
Пусть а: X ^ У — алгоритм из некоторого класса алгоритмов А, X — множество допустимых описаний объектов, У — множество допустимых ответов, у^) — ожидаемый правильный ответ для x, который должен вычислять алгоритм а.
Корректные операции над алгоритмами. Понятие корректности алгоритма а на множестве описаний X с X можно вводить
Научно-исследовательский институт прикладной математики и автоматизации Кабардино-Балкарского научного центра Российской Академии наук, Нальчик
различными способами. Например, поточечно, когда все ответы алгоритма корректные, или агре-гированно, когда оценка совокупного качества ответов на X принимает оптимальное значение. Пусть ^ — операция над алгоритмами.
Определение 1. Операция ^ над алгоритмами является корректной, если для всякого набора алгоритмов а1, а2, ..., ат е А, корректных на множестве X0, алгоритм а = ^(а1, а2, ..., ат) также является корректным на X0.
Поточечно корректный алгоритм. Часто для установления корректности алгоритма используется неотрицательная вещественная функция качества ответа Q(а|x) алгоритма а на описании x. Пусть Ьд — множество значений 0, эвристически соответствующих корректным ответам.
Определение 2. Ответ а(х) коррект-н ы й, если б(а^) е Ьд.
Определение 3. Алгоритм а поточечно корректный на X0, если для всех x е X0 ответ а^) корректный.
Корректные алгоритмы ищутся как решение системы (Ы = Xю |)
0(а|х,) е Ь0, к = 1, 2.....N.
Поточечно корректные операции по ответам. Пусть множество ответов Ус К. В этом случае качество ответа алгоритма у' = а^) оценивается при помощи неотрицательной двуместной функции Ь(у\ у), так что Q(a|x) = Ь(а^), у^)). Корректные операции по ответам алгоритма можно порождать при помощи функций Ф: Ут ^ У, таких что
Ф( 1У, 1У, ..., 1У) с 1у,
где 1у = {у: Ь(у, у) е Ьд} — подмножество ответов у , корректно согласованных с заданным ответом у.
Рассмотрим следующее представление для Ф:
Ф(У1, У2, ... Ут) = ф-1 (Р(У1, У2, ...Ут)) , (1)
где F(y1, у2, ..., ут) — функция ¥п ^ У, такая что порождает КО по ответам. Например, пусть аи + ф(у) = F(y, у, ..., у) взаимно однозначная. Верно + ак2 + ... + акт = р. Тогда следующее достаточное условие.
Утверждение 1. Пусть F — непрерывная функция и для любого у е У
1) 1у — связное,
2) ф(у) — строго монотонная на 1у,
3) область значений ф(у) на 1у совпадает с областью значений F(y1, у2, ..., ут) на .
Тогда функция Ф(у1, у2, ..., ут) вида (1) порождает поточечно КО по ответам.
Пример 1. Взвешенное g-с р е д н е е по Колмогорову [7]. Пусть
Р(уь у2, Ут) = Х (у,) ,
(2)
I = 1
1) если gk(Уl, у 2, ут) = П УУ*", то
* = 1
Г N т \1/р
Ф(У1, У2, •••, Ут ) = I Х *кПУ°
1к = 1 * = 1 У / т
2) если gk(Уl, у2, ..., ут) = ехр I Х а^у,
Ч = 1 у
Г N / т
ф(У1, у* Ут) = -1п<! Х ехрI Х акУ
Р ^ к = 1 Ч =
/ т
3) если gk(Уl, у2, ..., ут) = 1пI ХашУ,
, то
У = 1 Л
, то
где w1 + + ... + wm = 1, g: У ^ К — непрерывная взаимно обратная функция. Тогда функция
ф(У1, У2, Ут) = М (У1, У2, ..., Ут) =
У = 1
N / т \
ф(У1, У2, Ут) = - П |Х ак'У>
к = 1 У = 1
Пример 4. Пусть
8 I Х ™'8(У'')
Ф(У1, У2, Ут) = агё тпХ 8(|Уг - У), (3)
У = 1
У е у-
I = 1
порождает корректную операцию по ответам. Та- где g: К+ ^ К+ — монотонно возрастающая функ-кие средние являются обычными взвешенными ™ такая чт° g(0) = При этом, функция
средними в g-исчислениях [8]. Пример 2. Пусть
F(Уl, У 2, ..., Ут) = Х 8г (У г) ,
I = 1
где g¡ — одновременно монотонно возрастают или убывают. Тогда функция
ф(У1, У2, Ут) = 8 11 Х81(Уг)
1' = 1
где g(y) = Х 81 (у), порождает КО по ответам.
г = 1
П р и м е р 3. Пусть
N
F(Уl, У 2, ..., Ут) = Х *к8к (У1, У2, Ут) ,
к = 1
где Wl + ^2 + ... + = 1, У к: gk(y, у, у) = g(y), ратная функция. Тогда где g(y) — строго монотонная функция. Тогда
Ф(у1, у2, ..., ут), как решение задачи (3), единственна. Тогда Ф(у1, у2, ..., ут) порождает КО по ответам.
В общем случае КО по ответам алгоритма можно порождать при помощи функций Ф: Xх Ут ^ У, таких что:
Ф(х, !у, 1у)С 1У, где у = у(х). В этом случае нужно рассматривать представление вида
Ф( Уъ Уъ; Ут) = Ф^ДХ У1, Уъ~; Ут)) , (4) где F(x, у1, у2, ..., ут) — функция Xх У" ^ У, такая что фх(у) = F(x, у, у, ..., у) — взаимно однозначная для каждого х.
Пример 5. Пусть
т
F(х, У1, У* Ут ) = Х (Х ) 8( У') ,
г = 1
где ^1(х) + ^2(х) + ... + ^т(х) = 1 задает нечеткое разбиение X, g: У ^ К — непрерывная взаимно об-
N
Ф(У1, У2, Ут) = 8 11 Х *к8к (У1, У2. Ут)
к = 1
Ф(Х, У1, У2, Ут) = 8 11 Х(Х)8(У1)
Ч = 1 У
порождает корректную операцию по ответам.
т
т
т
т
26
ШИБЗУХОВ
Пример 6. Пусть
m
F( X, yi, y2, ..., Ут ) = ^ W (X ) & (у-) ,
i = 1
где + w2(x) + ... + wm (x) = 1, g¡ одновременно монотонно возрастают или убывают. Тогда функция
ф( x, У1, У2, ..., Ут ) = g-! ^ Wi(X )gi(y-)
^ i = 1
где g(у) = ^g¡ (у), порождает КО по ответам.
I = 1
Корректные операции по ответам образуют алгебру операций, замкнутую относительно закона композиции операций, т.е. если функции Ф^, «1, «2, ..., И€), Ф^, у1, у2, ..., ут), ..., у1,
у2, ..., ут) порождают КО по ответам, то функция у1, у2, ..., ут) = Ф(x, Ф1, Ф2, ..., Ф€) также порождает КО по ответам.
Поточечно корректные операции по оценкам. Если множество ответов У — дискретное множество, а |У невелико, то алгоритм, как правило, является композицией а = Я ° А оператора оценки А: X ^ и с и корректного решающего правила Я: и ^ У. Теперь вместо оценивания качества ответов оценивается качество самих оценок, так что оптимальные оценки соответствуют правильным ответам. В общем случае оно является двухместной функцией Ь: и х У ^ К и О(а^) = = Ь(А^), у^)). Пусть Ьд — множество значений О, эвристически соответствующих корректным ответам.
Определение 4. Оценка u = А^) является поточечно корректной для ответа у, если u е и = {ш Ь(^ у) е Ье}.
Здесь иу — множество оценок, которые содержательно корректны относительно ответа у.
Корректные операции по оценкам можно порождать при помощи преобразований Ф: ит ^ и, удовлетворяющих требованию
Ф( и, иу,.,., иу )с иу.
Значительная часть таких преобразований может иметь вид
Ф( иь и 2, ..., ит) = ф-1( р( иь и 2, ..., ит)) , (5)
где ¥: ит ^ Vс Ке, ф(п) = ¥(u, u, ..., u) — взаимно однозначное отображение и ^ V.
Утверждение 2. Пусть ¥ — непрерывное отображение и для любого у е У:
1) иу — связное множество;
2) ф^) — непрерывная и строго монотонная на иу;
3) область значений ф^) на иу совпадает с областью значений Д^, ..., um) на .
Тогда функция Ф(^, u2, .., um) вида (5) порождает поточечно КО по оценкам.
Пример 7. Взвешенное векторное среднее по Колмогорову. Пусть
m
F(Ui, U2, ..., Um) = ^ Wig(U-) ,
i = 1
где w1 + w2 + ... + wm = 1, g: R? ^ Re — непрерывное взаимно обратное отображение. Тогда
/ т ^
Ф(U1, U2, Um) = g^i ^ Wig(Ui)
Ч = 1 У
порождает КО по оценкам.
Пример 8. Пусть g(u) = (gi(ui), g2(u2), gmW), gj: Ij ^ R — непрерывная монотонная функция, Ij с R — связный интервал. Тогда
Ф(Ub U2, ..., Um) =
= (Mgi(U1), Mg2(U2), ..., Mgm(Um)), (6)
где Mg (u) — взвешенное gj-среднее по Колмогорову.
Пример 9. Пусть
N
F(U1, U2, Um) = ^ wkgk(U1, U2, Um) ,
k = 1
где g: R? x R? x ... x R? ^ Re — непрерывное отображение, такое что для всех i gk(u, u, ..., u) = g(u), g(u) — непрерывное взаимно обратное отображение Re ^ Re; w1 + w2 + ... + wN = 1. Тогда
/ N
ф(U1, U2, ..., Um) = g] ^ wkgk(U1, U2' Um)
4 = 1 У
порождает КО по оценкам.
В общем случае КО по оценкам можно порождать при помощи преобразований Ф: Xx Um ^ U, удовлетворяющих требованию
Ф(x, Uy, Uy,..., Uy)с Uy, у = у(x).
Значительная часть таких преобразований может иметь вид
Ф(X, U1, U2, Um) = ф-1 (F(X, U1, U2, Um)), (7)
где F: Um ^ Vс Re, ф^) = F(x, u, u, ..., u) - взаимно однозначное отображение U ^ V при каждом x.
Пример 10. Пусть
m
F(Ub U2, ..., Um) = ^ Wi(X)g(Ui) ,
i = 1
m
где g: [ ^ [ — непрерывное взаимно обратное отображение, wx(x) + w2(x) + ... + wm(x) = 1. Тогда
ф(Ui, u2, ..., ит) = g1 X W(x)g(ui)
порождает КО по оценкам.
Пример 11. Пусть g(u) = ^(и^, g2(u2), ..., gm(um)), I ^ К — непрерывная монотонная функция, I с К — связный интервал. Тогда
Ф(х, ыъ щ, ..., Мт) = = (Ф1 (х, «1), Ф2(Х, «2), ..., Фт(х, Ыт)) , где ФДи) — взвешенное среднее по Колмогорову,
ф(х, и) = gj I X wji(х)gj(ui) 1 i = i
X Wji( х) = 1,
gi IX wjg^( uj)
7 = 1
- min {Uj}
j = i,
< 6;
2) если g строго монотонно возрастает, то
gi11X wjgi(uj)
- max {Uj}
7 = i
j = 1.....m
< 6.
г=1
Корректные операции по оценкам также образуют алгебру операций, замкнутую относительно закона композиции операций.
Экстремальное свойство корректных операций. Корректные
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.