НИИ прикладной математики и автоматизации КБНЦ РАН, Нальчик
*****@***com
ПОТОЧЕЧНО КОРРЕКТНЫЕ ОПЕРАЦИИ
НАД АЛГОРИТМАМИ РАСПОЗНАВАНИЯ
И ПРОГНОЗИРОВАНИЯ1
Работа посвящена изучению разновидности корректирующих операций над алгоритмами – корректных операций, которые преобразуют наборы корректных алгоритмов в корректные алгоритмы. Основное внимание уделено изучению поточечно корректных операций, когда алгоритм является корректным на множестве описаний тогда и только тогда, когда все ответы алгоритма на этом множестве являются корректными. Описана общая схема порождения таких операций.
___________
1Работа выполнена при поддержке гранта РФФИ № -а.
Ключевые слова: распознавание, прогнозирование, корректный алгоритм, корректирующая операция, корректная операция, нейронная сеть
Введение
В настоящей работе обсуждается понятие корректной операции (КО) [3] над алгоритмами распознавания и прогнозирования. КО возникают в связи с проблемой построения корректных алгоритмов [2]. КО являются разновидностью корректирующих операций [1].
КО образуют значительный подкласс корректирующих операций [2]. Они обладают важным свойством -- сохраняют свойство корректности алгоритмов. Это свойство является весьма полезным при построении процедур монотонно корректного обучения с возможностью порождения семейств корректных алгоритмов, таких как конструктивное обучение 
-нейронных сетей [4] и многослойных перцептронных сетей [5]. Существует содержательная схема порождения поточечно КО.
Пусть 
− множество допустимых описаний объектов, 
− множество допустимых ответов, 
− неизвестная зависимость, 
− алгоритм из класса 
, “аппроксимирующий” 
.
Понятие корректности алгоритма 
на множестве описаний 
можно вводить различными способами. Например, поточечно, когда все ответы алгоритма должны быть верными, или аггрегированно, когда оценивается совокупное качество ответов на 
и необходимо, чтобы оно принимало оптимальное значение. Приняв то или иное определение корректности алгоритма, можно определить понятие КО над алгоритмами.
Определение 2. Операция 
над алгоритмами является корректной, если для всякого набора алгоритмов 
из , корректных на множестве 
, алгоритм 
также является корректным на .
Поточечно корректные операции
Для установления корректности алгоритма, как правило, используется вещественная функция качества 
ответа 
вида 
.
Определение 1. Ответ − корректный, если 
, где 
− множество значений 
, содержательно соответствующих корректным ответам.
Определение 2. Алгоритм − поточечно корректный на , если для всех 
ответ − корректный.
Корректные алгоритмы ищутся как решение системы:
, .
Поточечно корректные операции по ответам
Пусть 
. Качество ответа 
оценивается при помощи неотрицательной двуместной функции 
при условии, что верный ответ 
известен. Тогда корректные операции по ответам алгоритма можно порождать при помощи функций 
, удовлетворяющих следующему требованию:
,
где 
− окрестность диагонали множества 
, которая состоит из пар ответов 
, таких, что ответ 
корректно согласован с 
.
Рассмотрим следующее представление
,
где 
− непрерывная функция 
, такая, что 
− взаимно однозначная функция 
.
Утверждение 1. Пусть для любого 
:
1) 
− связное;
2) 
− непрерывная и строго монотонная на ;
3) область значений на совпадает с областью значений на 
.
Тогда функция 
вида порождает поточечно корректную операцию по ответам.
Пример. Взвешенное среднее по Колмогорову. Пусть
где 
− непрерывная взаимно обратная функция, 
. Тогда
порождает корректную операцию по ответам:
· если
, то получаем степенные средние;
· если 
, то получаем экспоненциальные средние;
· если 
, то получаем среднее геометрическое.
Пример. Несимметричное среднее по Колмогорову. Пусть
где 
− непрерывная функции одновременно возрастающие или одновременно убывающие. Тогда функция
где 
порождает корректную операцию по ответам.
Пример. Пусть
где 
, 
, 
– строго монотонная функция. Тогда
порождает корректную операцию по ответам. Например, пусть 
. Тогда:
· если 
то 
;
· если 
, то
;
· если 
, то
.
Поточечно корректные операции по оценкам
Если множество ответов − дискретное множество, а 
невелико, то алгоритм, как правило, является композицией оператора оценки 
и корректного решающего правила 
: 
. Вместо оценивания качества ответов оценивается качество самих оценок, так что оптимальные оценки соответствуют правильным ответам. Оно является двухместной функцией 
.
Определение 3. Оценка 
является поточечно корректной для ответа 
, если 
, где 
− множество оценок, которые содержательно корректны относительно ответа .
Корректные операции по оценкам можно порождать при помощи преобразований 
, удовлетворяющих следующему требованию:
Значительная часть таких преобразований может иметь вид
,
где 
− непрерывное отображение, 
− взаимно однозначное отображение 
.
Утверждение 2. Пусть для любого :
1) − связное;
2) 
− непрерывное и строго монотонное на ;
3) область значений на совпадает с областью значений 
на 
. Тогда функция 
порождает поточечно корректную операцию по оценкам.
Пример. Взвешенное векторное среднее по Колмогорову. Пусть
где 
− непрерывное взаимно обратное отображение, 
, 
обозначает покомпонентное умножение. Тогда
порождает корректную операцию по оценкам.
Пример. Пусть
где 
, 
, 
– строго монотонная функция. Тогда
порождает корректную операцию по оценкам.
Аггрегированно корректные операции
Определение корректности алгоритма строится при помощи функционала качества 
, который определяется как аггрегирующая функция от значений качества ответов на :
.
Как правило, оптимальный алгоритм на обучающем множестве ищется как решение экстремальной задачи оптимизации:
или
,
или как решение задачи
,
где − некоторая окрестность оптимального значения , которая эвристически соответствуют корректным алгоритмам на .
Определение 4. Алгоритм 
– аггрегированно корректный на относительно функционала качества , если 
.
Функционалы среднего качества
Очень часто функционал 
определяется как взвешенное среднее качества ответов для всех . Тогда в непрерывном случае его можно представить как взвешенное среднее по Колмогорову:
Пусть 
− непрерывная строго монотонная функция. Определим функционал качества как взвешенное среднее по Колмогорову от ошибок алгоритма:
Пусть j также выпуклая функция, 
, 
− такая функция, что для любых , 
, 
и 
.
Утверждение 3. Если 
− корректные алгоритмы на относительно , то 
− также корректный алгоритм на относительно .
Например, линейное взвешенное среднее
удовлетворяет этому условию.
Пусть 
− монотонно возрастающая функция. Тогда
Отсюда
Заключение
Таким образом, корректные операции представляют собой значительный подкласс корректирующих операций, который содержит линейные смеси, значительный подкласс монотонных корректирующих операций. Существует содержательная схема построения поточечно корректных операций. Применение корректных операций позволяет строить корректные операции, которые имеют более лучшее качество функционирования на контроле.
Список литературы
1. Журавлев алгебры над множествами некорректных (эвристических) алгоритмов // Кибернетика, 1977. № 4. С. 14-21; 1977. № 6. С. 21-27; 1978. № 2. С. 35-43.
2. Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики. М.: Наука, 1978. Т. 33. С. 5-68.
3. Шибзухов расширения корректных -алгоритмов // Доклады 15-й Всероссийской конференции "Математические методы распознавания образов". М.: Макс-Пресс. 2011. С. 116-119.
4. Шибзухов методы обучения -нейронных сетей. - М: МАИК Наука, 2006.
5. Parekh R., Yang J., Honavar V. IEEE Transactions on Neural Networks. V. 11. No. 2. P. 436-451.
6. Колмогоров труды. Математика и механика. С. 136-138. М.: Наука, 1985.
7. Pap E. Univ. u N. Sadu Zb. Rad. Prirod-Mat. Fak. Ser. Mat. 1993. Vol. 23, No. 1. P. 145-156.
8. Pap E. Preprint ESI 1448. Vienna, 2004.
