ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 462, № 6, с. 649-652
= ИНФОРМАТИКА
УДК 519.7
АГРЕГИРУЮЩИЕ КОРРЕКТНЫЕ ОПЕРАЦИИ НАД АЛГОРИТМАМИ
© 2015 г. З. М. Шибзухов
Представлено академиком РАН Ю.И. Журавлевым 18.12.2014 г. Поступило 25.12.2014 г.
бо1: 10.7868/80869565215180085
Одной из фундаментальных проблем машинного обучения является проблема построения корректных алгоритмов [1—4]. При построении алгоритмов, корректных на своей обучающей выборке, приходится сталкиваться с проблемой переобучения, которая проявляется в том, что обученные алгоритмы имеют низкие показатели обобщающей способности. Однако существуют модели алгоритмов и методы обучения, которые позволяют генерировать семейства алгоритмов, корректных на своем обучающем множестве. Например, конструктивный метод обучения ЕП-нейрона и его обобщений по специальным образом предварительно упорядоченной обучающей выборке [5—8] позволяет генерировать семейство ЕП-нейронов, корректных на своем обучающем множестве. В связи с этим возникает возможность построения новых корректных алгоритмов при помощи операций над корректными алгоритмами с целью улучшения их обобщающей способности, подобно тому как корректирующие операции используются для улучшения качества функционирования некорректных алгоритмов. Так возникает понятие корректной операции над алгоритмами [9—10].
По определению, корректная операция преобразует произвольный набор алгоритмов, корректных на выборочном множестве входов, в алгоритм, который также является корректным на этом же множестве входов, т.е. корректные операции сохраняют свойство корректности алгоритма.
Для формализации понятия корректной операции используется понятие корректного алгоритма. Рассматриваются два типа корректных алгоритмов: поточечно корректный и агрегирован-но корректный алгоритм. Поточечно корректный
Научно-исследовательский институт прикладной математики и автоматизации Кабардино-Балкарского научного центра Российской Академии наук, Нальчик E-mail: szport@gmail.com
алгоритм имеет корректные ответы для всех элементов заданной выборки. Агрегированно корректный алгоритм доставляет некоторый оптимум для заданной агрегирующей функции от значений функции качества ответов алгоритма на элементах заданного множества входов.
В настоящей работе рассматриваются корректные операции над алгоритмами, которые строятся на базе агрегирующих функций и операций [11, 12], и приводятся условия, при которых агрегирующие операции типа среднего приводят к корректным операциям над алгоритмами. Для обоснования корректных операций над агрегиро-ванно корректными алгоритмами вводится понятие Б/О-выпуклой и вогнутой функции (определения 4, 5) относительно заданной пары агрегирующих операций среднего значения Б и О применительно к функции качества ответа алгоритма. Также используется понятие доминирования (определение 6) агрегирующей операции О, участвующей в Б/О-выпуклости или вогнутости функции качества ответа алгоритма, над агрегирующей операцией, лежащей в основе функционала качества алгоритма. На базе этих понятий формулируются и обосновываются достаточные условия (теоремы 1, 2) того, что агрегирующая операция над алгоритмами является агрегированно корректной. Это позволяет строить не только линейные корректные операции над агрегиро-ванно корректными алгоритмами, но также и нелинейные, например такие, которые являются аналогами операции взвешенного среднего по Колмогорову. По существу, применение корректных операций над корректными алгоритмами позволяет расширять модели базовых корректных алгоритмов, выходя за рамки их ограничений так же, как и корректирующие операции над алгоритмами позволяют выйти за рамки ограничений моделей, приводящих к некорректным алгоритмам.
Начальные определения. Пусть X — множество допустимых описаний исследуемых объектов, Y — множество ответов на определен-
ный вопрос относительно исследуемых объектов. Пусть существует неизвестная функциональная зависимость у = у(х) между произвольным описанием х е X и ответом у е У на вопрос относительно х. Пусть а: X ^ У алгоритм из некоторого класса А, при помощи которого предпринимается попытка "аппроксимировать" зависимость у(х). Рассматриваются алгоритмы, представимые в виде композиции а = Я ° А, где А: X ^ и — некоторый оператор вычисления оценки, и с [К? или и с — пространство оценок (X — индексное множество), Я: и ^ У — некоторое решающее правило. Оператор А вычисляет некоторую оценку и = А(х), а решающее правило Я находит по ней искомый ответ у = Я(и). Решающее правило должно быть корректным [4].
Функция качества ответа и корректные ответы алгоритма. Понятие поточечно корректного алгоритма основано на понятии корректного ответа алгоритма. Обозначим v- — подмножество ответов, которые принимаются как верные наравне с ответом у е У (например, v- = {у: у — у | < е}), и- = {и е и: Я(и) е v-} -множество оценок, корректно согласованных с заданным ответом у.
Для оценки качества алгоритма а = Я ° А определяется функция качества ответа 0: и х У ^ Я, где Я с К — область значений функции качества. Функция 0(и, у) оценивает качество ответа алгоритма у = а(х) по отношению к заданному верному ответу у = у(х) на основе оценки и = А(х). Для любого у введем функцию Qу (и) = 0(и, у).
Для каждого ответа у е У обозначим ь- с Я — подмножество значений функции качества, являющихся индикатором верности ответа алгоритма. Так, если Qу (и) е ь-, то ответ у = Я(и) должен быть верным. Поэтому 0(и, у) всегда такая, что для любого у е У и любого и е и-: Qу (и) е ь-.
Агрегирующие функционалы качества алгоритма. Пусть xx = {хк: к = 1, 2, ..., — произвольное выборочное подмножество X. Довольно часто невозможно построить алгоритм, который дает корректные ответы для всех
входов из xx. Качество функционирования алгоритма на x- определяется как значение определенной агрегирующей функции на множестве значений
функции качества ответов на x-.
Пусть М — агрегирующая функция, определенная на множестве значений функции качества ответов 0, X — множество конечных выборочных
подмножеств xx с X. Агрегирующий функционал
качества 2: А х X ^ [ определяется как агрегирующая функция от величин качества ответов:
2(x) = Q{zk: k = 1, 2, ...,N}, (1)
где zk = Q(uk, Ук), = A(xk), ~yk = y(xk). Функционал 2 вычисляет качество алгоритма а на базе значений качества ответов для всех описаний из x.
Пусть L2 — выделенное подмножество значений функционала 2, которые соответствуют алгоритмам, принимаемым как верные. Будем называть L2 характеристическим множеством корректности алгоритмов относительно функционала 2. Введем теперь понятие агрегированно корректного алгоритма относительно функционала качества на выборочном множестве.
Определение 1. Алгоритм a — а г р е г и -рованно корректный относительно
функционала качества 2 на множестве xy , если
2(a | x) е L2.
Агрегированно корректные операции над алгоритмами. Для построения корректных операций над алгоритмами будем использовать обобщенные операции, действующие на множестве U. Обобщенная операция F определена для любого набора оценок и1, ..., ит:
да
F = U Fm, Fm: um ^ u.
m = 1
Пусть на U задано некоторое отношение частичного порядка <. Например, и' < и'', если u1 < u", ...
..., uq < <. Будем также рассматривать отношение < на упорядоченных наборах и е {и1, ..., ит} е е Um как т-кратную степень отношения < на U.
Определение 2. F является агрегирующей операцией на U, если
1) для любой пары {u1, ..., um} < {u" , ..., um'}:
F{ ui, um} < f{ <, o;
2) F{infU, ., infU} = infU, F{supU, ., supU} = = supU.
Здесь infU = (infU^ ..., infUm), supU = (sup U1, ... ..., supUm), U1, ..., Um — проекции U на оси 1, ..., q соответственно. Если U с [, то F — агрегирующая функция.
Определение 3. Операция F — идемпо-тентная на U, если для любого и е U: F{u, ..., и} = = и.
Обобщенная операция F на U порождает обобщенную операцию над алгоритмами из А, которые имеют вид R ° A по следующему правилу F{R ° A1, ..., R ° Am} = R ° F{A1, ..., Am}. Если R — тождественная, то a = F{a1, ..., am}.
Пусть R с [, f: U ^ R — некоторая вещественная функция m переменных, F - идемпотентная
АГРЕГИРУЮЩИЕ КОРРЕКТНЫЕ ОПЕРАЦИИ
651
агрегирующая операция на U, G — идемпотент-ная агрегирующая операция на R.
Определение 4./(u) — F/G-выпуклая, если для любых u1, ..., um е U:
f( F { u!,..., um })< G {f( ui ),..., f( um )} .
Например, если F, G — агрегирующая операция взвешенного среднего, то
f(aiUi + . + « m Um) < af( U1) + ... + aJ( Um) ,
т.е. получаем стандартное определение выпуклой функции.
Определение 5. f(u) — F/G-в о гнутая, если для любых u1, ..., um е U:
f( F { ui,..., um })> G{f( ui ),..., f( um )} .
Например, если F, G — агрегирующая операция взвешенного среднего, то
f(«iui + ... + «mum) > af(ui) + . + af um) , т.е. получаем стандартное определение вогнутой функции.
Пусть M — агрегирующая функция на R. Определение 6. G — доминирует над M, если
M { G { Uii, .. Uim }, .. G{ Uni, ..., UNm}}<
< G { M { Uii, ..., Uni }, M { Uim, ..., UNm}} . Следствие 1. Если VN е N функция H(ub ... ..., uN) = M{u1, ..., uN} — выпуклая, то
M
X• • Xг - Xам {иу • • и^},
Ч у J у
т.е. операция линейного взвешенного среднего доминирует над М.
Следствие 2. Если Ут е N функция Н(иь •.. •, ит) = О{м1, •, ит} — вогнутая, то
N Г N N г
X ак ик1, •.., икт}< G <| X акик1, • .., X akUkN к
У ^ к = 1 к = 1 '
т.е. О доминирует над операцией линейного взвешенного среднего.
Следующий факт является следствием двух предыдущих.
Следствие 3. Пусть g, к — две строго монотонно возрастающие и обратимые функции, Mg и Мк — агрегирующие функции взвешенного среднего по Колмогорову. Тогда
1) еслиg ° к-1 — выпуклая, то Мк доминирует над М^
2) если g ° к-1 — вогнутая, то Mg доминирует над
Мк.
Сформулируем достаточные условия того, что идемпотентная агрегирующая операция является агрегированно корректной. Те о р е м а 1. Пусть
1) для любого у е Y функция 0 (u) — Б/О-выпук-лая;
2) G доминирует над M;
3) множество Lq замкнуто относительно G;
4) если Q' е La и Q " < Q ', то Q " е La.
Тогда F — агрегированно корректная операция над
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.