научная статья по теме О ПОТОЧЕЧНО КОРРЕКТНЫХ ОПЕРАЦИЯХ НАД АЛГОРИТМАМИ РАСПОЗНАВАНИЯ И ПРОГНОЗИРОВАНИЯ Математика

Текст научной статьи на тему «О ПОТОЧЕЧНО КОРРЕКТНЫХ ОПЕРАЦИЯХ НАД АЛГОРИТМАМИ РАСПОЗНАВАНИЯ И ПРОГНОЗИРОВАНИЯ»

ИНФОРМАТИКА

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 рублей.

Показать целиком