О свойствах задач и алгоритмов разметки точечных конфигураций

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

Содержание
Введение

1 Формализация, разрешимость и регулярность задач разметки точечных конфигураций

1.1 Окрестности, разметки, метрики

1.2 Аксиомы разметки

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

2 Вопросы полноты

2.1 Полнота семейств и моделей алгоритмов

2.2 Критерии полноты

3 Программный стенд

Заключение
Список иллюстраций
Список литературы

Введение
Настоящая работа выполнена в рамках алгебраического подхода к проблеме синтеза алгоритмов распознавания. Основные идеи и конструкции алгебраического подхода были сформулированы академиком РАН 10. И. Журавлёвым в конце 70-х годов прошлого века [12-15] и в последствии развивались его учениками. К тому времени накопилась существенная потребность решения задач обработки информации, которые возникали в различных плохо формализованных областях, для которых, как правило, отсутствовали удовлетворительные математические модели. Примерами таких задач могут послужить задачи анализа социально-демографических и экономических временных рядов, геологической разведки, оценки привлекательности заёмщиков при выдаче кредитов и многие другие.
Идея, послужившая отправной точкой для формирования алгебраического подхода заключается в следующем: в случае, когда отсутствует как адекватная математическая модель, описывающая исследуемую ситуацию, так и модель того, как схожие задачи решает человек, можно строить алгоритмы, осуществляющие требуемое преобразование информации, исходя из имеющихся эмпирических данных и соображений здравого смысла. Чаще всего в таких задачах математическая модель заменялась прецедентной информацией — множеством пар вида «входная информация — ответ». Постепенное накопление примеров удачно решённых прикладных задач послужило практическим доказательством того, что решение плохо формализованных задач, для которых отсутствуют адекватные математические модели реальных процессов, возможно на основе ряда общих информационных принципов. С накоплени-

ем алгоритмов решения различных практических задач стало заметно, что различные задачи решают алгоритмы, устроенные сходным образом. Это наблюдение позволило постепенно перейти от принципа «прикладная задача — алгоритм-решение», к принципу «семейство алгоритмов — прикладная задача»: возникли достаточно общие параметрические семейства алгоритмов, называемые моделями алгоритмов распознавания, а решение практических задач сводилось к выбору параметров, которые выделяли из этих параметрических семейств алгоритмы, решающие конкретную задачу оптимальным образом. Эти модели, обычно, возникают в результате формализации некоторых интуитивных представлений о том, как устроены зависимости между входными и выходными данными в задаче, поэтому их ещё называют эвристическими информационными моделями. Решение задач распознавания на основе параметрических семейств получило ряд обоснований, в основе которых лежало принятие различных гипотез метрического, статистического и комбинаторного характера [2,3,19,20,24-26,33]. Работы в первом направлении проводились непосредственно Ю. И. Журавлёвым и его последователями, в то время как исследования второго типа осуществлялись академиком РАН В. Л. Матросовым [27-32]. Третье направление развивает д.ф.-м.н. К. В. Воронцов [4-7].
Однако использование фиксированных параметрических семейств алгоритмов несло в себе некоторое противоречие. С одной стороны для поиска решения следовало выбрать но возможности наиболее «богатое» семейство, так как оно с большей вероятностью содержит алгоритм, дающий наилучший результат. С другой стороны «богатые» семейства обычно достаточно сложно устроены, что приводит к возникновению сложных, а порой неразрешимых, оптимизационных задач и необходимости

Именно а-П-локальная непротиворечивость набора прецедентов задачи является основным условием разрешимости этой задачи. Докажем это в следующей теореме.
Теорема 5 Задача Е а-41-локально разрешима тогда и только тогда, когда набор прецедентов II не является ос-41-локально противоречивым.
Доказательство.
Необходимость. Допустим, что задача Z разрешима, т.е. существует подходящий корректный алгоритм А, удовлетворяющий условию локальности, но набор прецедентов противоречив. Это означает, что в существует пара окрестностей 01,02 с метками р, и д2 соответственно таких, что 1(рI, Ц2) > ар (0Ь02). Из требования корректности алгоритма непосредственно вытекает, что А{0) = р,, А (02) = Д2-Но тогда I (А (0), А (О2)) > а/ДООг), что противоречит условию а-Г2-Р/"-локальности алгоритма. Следовательно, сделанное предположение неверно, и набор прецедентов Н не является а--локалыю противоречивым.
Достаточность. Рассмотрим набор размеченных окрестностей О'ц — набор прецедентов задачи. Метки этого набора являются подходящими и удовлетворяют условию близости по определению непротиворечивого набора прецедентов. Следовательно, в силу того, что система аксиом П является непрерывно покрывающей, для всякой окрестности существует подходящая метка, соответственно близкая всем меткам из набора прецедентов. Аналогичные рассуждения можно повторить для следующей окрестности и так далее. Следовательно, существует множество меток М в котором каждой окрестности из 41 соответствует единственная