Введение к работе
Актуальность теш. К числу наиболее актуальних проблем теории распознавания образов относится задача синтеза из алгоритмов модели с помощью корректирующих операций оптимальных по точности распознавашя алгоритмов.
Один из подходов к решению этой задачи связан с понятием "корректора по результатам". Суть подхода состоит в том, чтобы корректирующие операции выполнялись над информационными матрицами, вырабатываемыми алгоритмами модели.
В семидесятых годах школой Журавлева Ю.И. начал активно разрабатываться иной подход, получивший название алгебраического. Он предусматривает введение так называемого пространства оценок, промежуточного по отношению к исходным описаниям и допустимым ответам (информационным матрицам). Алгоритм распознавания при этом рассматривается как суперпозиция двух алгоритмов. В частности, Всякий алгоритм вычисления оценок можно представить как последовательное выполнение двух алгоритмов: оператора вычисления оценок и решающего правила. Оператор строит для набора классифицируемых объектов числовув матрицу оцэнок, а решающее правило по полученной матрице оценок строит информационную матрицу. При таком представлении распознащвго алгоритма корректирующие операции можно вводить'не над информационными матрицами, а на болев раннем этапе - над матрицами оценок. Тем самым возможности выбора корректирующих операций значительнее расширяются, а сами операции существенно обогащаются свойствами.
Много внимания в исследованиях школы Журавлева Ю.И. уделяется трем операциям: операциям сложения и умножения операторов и умножения оператора на число (им соответствуют операции покомпонентного сложения и умножения матриц оценок и умножения матрицы оценок на число). Рассматриваются линейные и алгебраические замыкания различных моделей алгоритмов относительно названных операций. Исследуется корректность этих замыканий и их подмножеств как над классом всех регулярных задач, так и над всевозможными его подклассами.
В работах Матросова В.Л. было доказано, что линейное вамыкание в алгебраическое вамыкание второй степени семейства алгоритмов вычисления оценок некорректны над множеством всех регулярных задач.
;>
Принципиальный характер имеет вопрос: будут ли обладать свойством корректности алгебраические замыкания степени К при К^З, т.е. подклассы из алгебраического замыкания, содержащие алгоритмические многочлени степени не выше К ?
Для практического применения имеет значение оценка степени алгебраического замыкания семейства алгоритмов, корректного для фиксированной задачи или некоторого класса задач.
В работах. Журавлева Ю.И. получена асимптотическая оценка степени К алгебраического замыкания семейства алгортмов вычисления оценок, содержащего корректный' алгоритм для произвольной регулярной задачи: при <-*<>*> K«
Конкретные примеры показывают, что в отдельных случаях оценку К » І ^гЯ^ ] можно понизить.
Наряду с оценкой степени корректного замыкания не меньшее практическое значение имеет разработка критериев корректности различных семейств алгоритмов для регулярных задач.
Эта проблема глубоко исследуется в работах матросова В.Л., исследования продолжены Кукулиевым Б.М., Ивановой Е.А. и могут быть развиты дальше.
Цель работы. Целью настоящего исследования является:
-
Доказательство некорректности алгебраического замыкания степени К семейства алгоритмов вычисления оценок над классом всех регулярных задач для любого К > 3.
-
Оценка степени корректного^алгебраического замыкания семейства-алгоритмов вычисления оценок для произвольной регулярной задачи.
-
Получение условий корректности алгебраического замыкания степени К семейства алгоритмов вычисления оценок для
произвольно выбранной регулярной задачи.
Научная новизна. В основе диссертационной работы лежит теорема о сводимости, в которой построена "базисная" совокупность мегриц оценок, являющихся булевыми.
Использование "базисной" совокупности булевых матриц оценок позволяет получить следующие основные результаты:
-
Доказать некорректность алгебраического замыкания. степени К семейства алгоритмов вычисления оценок над классом всех регулярных задач (для любого натурального К > 3).
-
Доказать необходимые и достаточные условия корректности алгебраического замыкания "степени К семейства алгоритмов вычисления оценок для произвольной регулярной задачи, которые сводятся к исследованию совместности системы неравенств специального вида.
-
Доказать, что алгебраическое замыкание степени К семейства алгоритмов вычисления оценок корректно над классом всех регулярных задач, объем обучающей информации которых не превосходит К; причем К является минимальной корректной степенью для такого класса задач.
-
Уточнить оценки степени корректного замыкания семейства алгоритмов вычисления оценок для произвольно выбранной регулярной задачи.
Все эти результаты являются новыми и получены впервые автором дассартвции.
Методологическую основу работы составляют методы булевой алгебры, линейной алгебры, алгебраической теории распознавания.
Диссертация выполнена в соответствии с планом научно-исследовательской работы кафедры (номер государственной регистрации
0812702% 19).
Научная и практическая значимость работы.
Результаты, полученные в работе, имеют правде всего теоретическое значение. Предложенная в работе методика исследования свойств алгебраических замыканий конечной степени семейства алгоритмов вычисления оценок с помощью булевых матриц может быть развита й применена в дальнейших исследованиях подобного рода.
Апробация работы. Материалы диссертации докладывались на научных семинарах математического факультета Московского педагогического государственного университета имени В.И.Ленина (1985-1993 гг.); на научно-технических конференциях Ульяновского политехнического института (1992-1993 гг.); на научно-техническом совещании "Логико-алгебраические
модели представления знаний в экономических, технических и организационных системах" (г.Ашхабад, 1983 г.); на I Всесоюзной конференции "Математические метода распознавания образов" (г.Диликан, 1985 г.); на 17 Всесоюзной конфоренции "Математические методы распознавания образов" (г.Рига, 1989 г.) и опубликованы в семи печатных работах (юс список приведен в конце автореферата).
Структура и обшл диссертации. Работа состоит из введения, трех глав и списка использованной литературы. Она содержит 126 страниц основного текста, 59 наименований использованной литературы.
