Элементы алгебраической теории синтеза обучаемых алгоритмов выделения трендов

• Автор: Чехович, Юрий Викторович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 70 с.

Глава 1. Формализация, разрешимость и регулярность задач синтеза обучаемых алгоритмов выделения трендов

1.1. Конфигурации и разметки

1.2. Аксиомы (правила) разметки

1.3. Разрешимость и регулярность

Глава 2. Проблема локализации

2.1. Окрестности в конечных плоских конфигурациях

2.2. Локальность аксиом разметки

2.3. Локальность алгоритмов разметки

2.4. Локальная разрешимость и регулярность

2.5. Проблемы мощности систем окрестностей

2.6. Отношения порядка на конфигурациях и окрестностях

2.7. О построении оптимальной системы окрестностей
2.8. Монотонность свойства локальной регулярности
2.9. Монотонность свойства локальной разрешимости
Глава 3. Проблемы полноты
3.1. Задачи классификации с теоретико-множественными ограничениями
3.2. Понятия полноты для задач с теоретико-множественными ограничениями
3.3. Критерий полноты для семейств решающих правил
3.4. Критерий полноты для семейств корректирующих операций
3.5. Критерий полноты для моделей алгоритмических операторов
Заключение
Список иллюстраций
Список литературы

Основы алгебраического подхода к проблеме синтеза корректных алгоритмов были заложены в 70-х годах прошлого века в работах академика РАН Ю.И. Журавлева [10,11]. В этих работах были развиты “прямые методы” построения корректных, то есть точных на прецедентах, алгоритмов классификации путем применения специальных алгебраических операций к эвристическим распознающим операторам. При этом были введены основополагающие понятия (регулярность, полнота и т.д.) и конструкции, область потенциального применения которых существенно шире, чем задачи и алгоритмы распознавания и классификации.
В настоящее время представляется несомненным, что алгебраический подход представляет собой не специализированную теорию, а скорее математическую технологию построения проблемно-ориентированных теорий синтеза высококачественных алгоритмов на базе соответствующих эвристических информационных моделей, то есть параметрических семейств операторов, отражающих те или иные экспертные знания о предметной области. Можно сказать, что выработалась определенная культура применения алгебраических методов при исследовании конкретных предметных областей, которая позволяет сформулировать правильную последовательность вопросов, ответы на которые и составляют проблемно-ориентированную теорию.
Прежде всего, отметим, что решениями задач, для которых предназначен алгебраический подход, являются не ответы на конкретные содержательные вопросы, а алгоритмы, способные давать такие ответы. При этом объектом изучения оказывается не сама предметная область, а собственно алгоритмы, семейства алгоритмов, а также операции над алгоритмами. В соответствии с этим под качеством решения понимается качество построенного алгоритма, определяемое чаще всего точностью его
работы на прецедентах и его соответствием различного рода дополнительным требованиям.
Основной технический прием алгебраического подхода состоит в том, что эвристические информационные модели (параметрические семейства алгоритмов) используются не в качестве области оптимизации, а как источник базовых операторов, применение к которым соответствующих корректирующих операций и приводит к построению высококачественного алгоритма - решения.
При разработке конкретной проблемно-ориентированной теории первый шаг состоит в точном описании класса задач, которые должны решаться искомыми алгоритмами. Такое описание включает в себя фиксацию множества начальных информаций (входов алгоритмов), множества финальных информаций (выходов алгоритмов) и структурной информации (вида прецедентов и дополнительных ограничений) [12,25-33].
Существенно, что уже на первом шаге возникает возможность постановки и решения ряда содержательных вопросов. А именно, устанавливаются условия, обеспечивающие разрешимость изучаемых задач. Эти условия определяют по сути дела непротиворечивость прецедентной и дополнительной информации. Они же, естественно, оказываются условиями существования корректного алгоритма — решения.
Как правило, наряду с разрешимостью изучается вопрос о так называемой регулярности рассматриваемых задач. Под регулярностью понимается при этом усиление свойства разрешимости, сводящееся к требованию разрешимости не только для самой задачи, но и для задач, в некотором смысле близких к рассматриваемой. Установление критериев регулярности задач автоматически приводит к критериям полноты для семейств алгоритмов: под полнотой семейства понимается существование в нем решений для всех регулярных задач.
В тех случаях, когда на множестве задач оказывается возможным введение адекватной метрики, решается вопрос и о получении оценок для так

Конструкции алгебраического подхода к проблеме синтеза корректных алгоритмов основаны на использовании “промежуточного” по отношению к 3(- и Зу пространства оценок 3^ = ^}. При этом корректные алгоритмы
синтезируются на базе эвристических информационных моделей, т.е. параметрических семейств отображений из 3; в Зу, представляющих собой
специальные суперпозиции алгоритмических операторов (отображений из 3,
в Зе) и решающих правил (отображений из 3^ в Зу, р - арность решающего правила).
Напомним, что при произвольных множествах ‘’Ц., Т), <31(/ и Т/ и
пары {и,и') из %х«5Ц/ выполнено равенство (и,и') = (и(и),и(и')) [1]
будем называть отображение из % в Т) такое, что для любого и из % выполнено равенство ил(и) = и(и,и,---,и)-
Модели Эи определяются моделями алгоритмических операторов 9п°,
Для синтеза корректных алгоритмов используются также множества У корректирующих операции, определенных над множеством отображений 9к„. Корректирующие операции рассматриваемые в настоящей работе, индуцируются операциями Р над пространством оценок Зе:
произвольных отображениях и из в Т) и и' из в Т)’ произведением ux.it' называется отображение V из ^Их^Н/ в Т)хТ)/ такое, что для любой
произвольного отображения и из ‘’її/ в Т) при р> 1 диагонализацией и&
где 9л0 с9я. = {я| В :3, -.3,,}, и решающих правил Эн.1, где Эн1 с иісіслг-з,},