Модели и алгоритмы для задач распознавания с комбинированной обучающей информацией

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Модели и алгоритмы для задач распознавания с комбинированной обучающей информацией

Общая характеристика работы

Связь работы с крупными научными программами (проектами) и темами

Результаты, изложенные в диссертации, получены в рамках исследований и разработок, проводимых на кафедре информационных систем управления факультета прикладной математики и информатики Белорусского государственного университета, в соответствии с:

1) ГНТП «Информационные технологии», утвержденная приказом ГКНТ Республики Беларусь от 2 июня 2006 г. №137: задание 5-07 «Разработать технологию построения компьютерных систем для решения задач распознавания образов в области медицинской диагностики при условии неполноты информации и внедрить ее в спортивной травматологии и реабилитологии» (№ госрегистрации 20064847, срок выполнения 2006-2012 гг.), исполнитель;

2) государственной программой научных исследований на 2011-2015 гг. «Информатика и космос»: задание 1.4.05 «Разработать технологии и компьютерные системы для решения задач распознавания образов со сложной структурой информации» (№ госрегистрации 20114342, срок выполнения 2010-2013 гг.), исполнитель;

3) договором с Белорусским республиканским фондом фундаментальных исследований №Ф15РМ-037: задание «Разработка и исследование многоуровневых моделей решения многоклассовых задач распознавания» (договор с БРФФИ от 04 мая 2015 г., № госрегистрации 20150928, срок выполнения 04.05.2015 - 31.03.2017 гг.), ответственный исполнитель;

4) научно-исследовательской программой Белорусского государственного университета: задание «Разработать теоретические основы и технологии построения информационных систем управления с приложением в интеллектуальном анализе данных» программы НИР БГУ на 2011-2015 гг. (№ госрегистрации 20120332, срок выполнения 2011-2015 гг.), исполнитель.

Цель и задачи исследования

Цель диссертационной работы - разработка моделей и алгоритмов решения задач распознавания с комбинированной обучающей информацией, объединяющих результаты и преимущества различных видов алгоритмов.

Для достижения цели были поставлены и решены следующие задачи:

· провести анализ подходов к решению задач распознавания и установить алгоритмическую связь между логическим и прецедентным способами представления информации;

· модифицировать алгоритм резолюций для объектов с конечным числом значений признаков;

· разработать гибридный алгоритм, объединяющий результаты решения алгоритмов с логическим и прецедентным способами представления информации;

· провести теоретическую и экспериментальную оценку качества предлагаемых алгоритмов и на базе проведенных исследований разработать программную технологию для решения комбинированных задач.

Объект исследования - задачи распознавания, в которых одновременно используются различные типы обучающей информации.

Предмет исследования - методы и алгоритмы решения задач распознавания с комбинированной обучающей информацией.

Научная новизна

Научная новизна исследования заключается в разработке оригинального подхода к решению задач распознавания с комбинированной обучающей информацией.

Разработана алгебра объектов, с помощью которой установлена связь между логической и прецедентной моделями представления информации. Показано, что алгебра объектов изоморфна алгебре функций -значной логики. Предложена оригинальная кодировка объектов, учитывающая неопределенность значений признаков.

Разработаны модификация метода резолюций на случай задач распознавания с прецедентным представлением информации и гибридный алгоритм, ориентированный на различные способы представления обучающей информации.

Предложены эффективные реализации разработанных алгоритмов. Экспериментально показано, что уменьшение времени работы алгоритмов в среднем экспоненциально зависит от структуры информации об объектах.

Положения, выносимые на защиту

1. Модель алгебры объектов, устанавливающей связь между логическим и прецедентным способами представления информации, и алгоритмы перехода (в конечномерных пространствах) от одного представления информации к другому, что в совокупности позволяет решать задачи распознавания независимо от исходного способа представления информации.

2. Алгоритм объектных резолюций, позволяющий использовать метод резолюции в случаях, когда информация представлена прецедентным способом.

3. Гибридный алгоритм, построенный на базе алгоритмов объектной резолюции и индуктивного вывода, что позволяет одновременно использовать логический и прецедентный способы представления обучающей информации.

4. Эффективные (с вычислительной точки зрения) реализации предложенных алгоритмов, на базе которых программно реализовано алгоритмическое ядро для построения прикладных систем, ориентированных на решение специальных задач распознавания с не полностью заданной и сложной по структуре информацией.

Личный вклад соискателя

Основные результаты и положения, выносимые на защиту, получены лично соискателем. В публикациях с соавторами вклад соискателя определяется рамками излагаемых в диссертации результатов. Постановка целей и задач исследовательской работы, обсуждение и интерпретация полученных результатов, определение структуры диссертации выполнялись совместно с научным руководителем, кандидатом физико-математических наук Образцовым В.А.

Апробация результатов диссертации

Основные научные и практические результаты работы докладывались и обсуждались на следующих международных и отечественных конференциях: Computer Data Analysis and Modeling conference (CDAM'2010, Minsk); IV Машеровские чтения: международная научно-практическая конференция студентов, аспирантов и молодых ученых (2010, Витебск); Международный форум учащейся и студенческой молодёжи «Первый шаг в науку - 2011» (2011, Минск); Pattern Recognition and Information Processing (PRIP'2011, Minsk); Республиканская научная конференция студентов и аспирантов Республики Беларусь «НИРС-2011» (2011, Минск); International Congress of Computer Science: Information systems and Technologies (CSIST'2011, Minsk); Modeling and Simulation (MS'2012, Minsk); International Congress of Computer Science: Information systems and Technologies (CSIST'2013, Minsk); Pattern Recognition and Information Processing (PRIP'2014, Minsk).

По результатам диссертации получено 3 акта внедрения. Результаты диссертации используются в Республиканском научно-практическом центре спорта, а также в учебном процессе и при выполнении различных НИР на кафедре информационных систем управления ФПМИ БГУ.

Опубликованность результатов диссертации

Результаты диссертации опубликованы в 15 научных работах, включая: 5 статей в рецензируемых научных журналах в соответствии с п. 18 Положения о присуждении ученых степеней и присвоении ученых званий в Республике Беларусь (общим объемом 2,7 авторского листа), 9 статей в сборниках материалов научных конференций и 1 тезисы доклада.

Структура и объем диссертации

Диссертация состоит из перечня сокращений и условных обозначений, введения, общей характеристики работы, 4 глав, заключения, библиографического списка и 3 приложений. Полный объем диссертации составляет 114 страниц, в том числе 7 рисунков на 7 страницах, 15 таблиц на 10 страницах, 3 приложения на 11 страницах. Библиографический список содержит 68 наименований (включая собственные публикации соискателя).

Основное содержание работы

гибридный алгоритм логический

В первой главе исследуется задача распознавания образов с обучением. Выделены два основных способа представления обучающей информации: логический и прецедентный. Сформулирована задача распознавания с комбинированной обучающей информацией и определены основные проблемы, связанные с ее решением.

В рамках основных направлений теории распознавания рассматриваются дедуктивный и индуктивный подходы, использующие логический и прецедентный способы представления информации соответственно. Проведен анализ существующих алгоритмов решения задачи и показано, что каждый из них обладает определенными недостатками. При использовании алгоритмов дедуктивного типа невозможно получать решение за пределами ситуаций, ограниченных областью действия логического вывода. А при использовании алгоритмов индуктивного типа нельзя обосновать правильность получаемого решения. Вместе с тем существуют задачи распознавания (например, медицинская диагностика и др.), в которых по разным причинам необходимо использовать оба способа представления информации одновременно. Поэтому актуальной является проблема построения метода решения комбинированных задач распознавания, позволяющего заимствовать все лучшее в существующих алгоритмах.

Рассмотрены методы решения задач распознавания, в которых обучающая выборка содержит оба типа обучающей информации. На рисунке 1 приведены схемы процесса получения решения, которые на сегодняшний день можно считать общепринятыми. В первом случае происходит комбинирование результатов решения задачи, полученных алгоритмом резолюции и алгоритмом индуктивного вывода , а во втором - выборка, представленная логическим способом, переводится к прецедентному представлению, и задача решается алгоритмом .

Для решения комбинированных задач предлагается подход, основанный на объединении различных типов алгоритмов (рисунок 2).

Рисунок 1. Схемы решения задач для различных типов информации

Общая концепция подхода заключается в следующем. Вводится специальная алгебра объектов, в рамках которой устанавливается соотношение между логическим и прецедентным представлениями обучающей информации и строятся алгоритмы перехода от одного вида представления к другому. Результатом является адаптация классического метода резолюций к прецедентному представлению (алгоритм ), на основе которого строится гибридный алгоритм распознавания .

Далее в главе формулируются основные проблемы, решение которых позволяет реализовать изложенный подход и тем самым достичь поставленной в диссертации цели.

Рисунок 2. Предлагаемая схема решения комбинированных задач

Во второй главе исследуется связь между логическим и прецедентным способами представления информации, и предлагаются алгоритмы перехода между ними.

Пусть - произвольная задача распознавания. Для того, чтобы установить указанное соответствие, вводится понятие алгебры объектов.

Произвольный объект предлагается рассматривать в виде отображения:

где () - наименования признаков, - множество их значений ().

Вводится специальный объект-признак:

,

который получается фиксацией значения одного признака ().

В процессе построения объектов возникают ситуации, когда значение некоторых признаков не определено либо число их значений (т.н. шкалированные или непрерывные признаки). Для применимости алгоритмов в описанных выше случаях вводится несколько видов кодировки: регулярным образом расширяется признаковое пространство, но при этом сами значения признаков выбираются из множества . Кодировка, в результате которой устраняется неопределенность значений признаков, называется нормализацией.

Далее определяется базовая операция произведения двух произвольных объектов и (обозначается ):

,

с использованием которой вводятся операции над наборами объектов и :

- отрицание,

- умножение,

- сложение,

где - множество нормализованных объектов.

Показано, что система операций над наборами объектов обладает свойством полноты в том смысле, что любой набор может быть построен из объектов-признаков с помощью только этих операций.

Построены алгебры объектов и их нормализованных вариантов , где , - множество всех возможных наборов и нормализованных вариантов соответственно. Доказано, что алгебра является подалгеброй .

С использованием введенных кодировок построены также алгебры объектов и вида и соответственно. Показано, что алгебры и , а также и изоморфны. Кроме того, доказано, что эти алгебры изоморфны классическим алгебрам -значной логики.

В результате проведенных исследований построены алгоритмы перехода от логической модели представления информации к прецедентной () и обратно (). Вкратце их можно описать следующим образом.

Пусть - логическая формула, описывающая класс , где . Рассмотрим случай . Поскольку - булева функция, то ее можно представить в виде совершенной ДНФ:

,

Пусть - число элементарных конъюнкций в данном представлении формулы . Обозначим -ю элементарную конъюнкцию (ЭК) через . Тогда

.

Алгоритм :