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

/ ч *

, / ' / ;

V

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Чувашский государственный университет имени И.Н. Ульянова

На правах рукописи БЕЛЬЧУСОВ АНАТОЛИЙ АЛЕКСАНДРОВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ОЦЕНКИ КАЧЕСТВА РАСПОЗНАВАНИЯ И СОВЕРШЕНСТВОВАНИЕ ОБУЧАЮЩИХСЯ АЛГОРИТМОВ

05.13.16 "Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях"

(технические науки)

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

Научный руководитель -доктор технических наук, профессор О.И. Березкин

ЧЕБОКСАРЫ 1998

Введение

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

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

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

Для ответа на эти вопросы необходимо научиться сравнивать рассматриваемые алгоритмы. Любое сравнение предполагает:

- установление количественной меры качества алгоритма;

- выработку конструктивных способов её расчета.

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

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

В данном случае речь идет о широком классе алгоритмов распознавания, реализующих концепцию обучения с учителем [3, 22, 33, 36, 53, 88, 94]. Для разработки алгоритмов их авторы используют различные методы распознавания, подводят под свои рассуждения различную базу [57, 58, 74, 82, 92]. Но для оценки качества распознавания принципиально важно выяснить частоту совпадения ответов, данных алгоритмом, с действительными классами объектов. Поэтому в целях производимой оценки необходимо отвлечься от рассмотрения вопросов мотивации при выработке решений различными алгоритмами, поскольку оценивается и сравнивается только результат работы алгоритма.

Такой важный вопрос, как оценка качества распознавания алгоритмов, и связанные с ним прикладные задачи нашли свое отражение в научной литературе, главным образом в работах [23, 26, 33, 54, 59, 61, 90 и 104]. Однако после детального анализа предложенных в них методов оценки качества распознавания выясняется, что все они носят частный характер и затрагивают только отдельные аспекты проблемы. В большинстве работ качество распознавания оценивается для узкого класса алгоритмов [28]. В достаточной мере не обсуждается ни область использования, ни вопросы объективного и достоверного применения самих методов оценки.

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

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

На защиту выносятся: метод оценки качества обучающихся алгоритмов распознавания; математическая модель, позволяющая имитировать процесс распознавания.

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

Результаты работы докладывались на XXVII и XXVIII научных конференциях по гуманитарным, естественным и техническим наукам (Чебоксары, 1993,1994 г.), семинаре Вычислительного центра Российской академии наук (Москва, 1993), конференции «Математические методы распознавания образов» (Москва, 1994), научной конференции «Реформирование российской экономики» (Чебоксары, 1997), II всероссийской научно-технической конференции «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 1998). Тезисы докладов опубликованы.

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

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

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

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

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

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

Заключение содержит выводы по результатам исследований и проведенным расчетам.

Автор выражает искреннюю признательность научному руководителю, оппонентам, коллективам Чувашского государственного университета и Вычислительного центра Российской академии наук за ценные советы и рекомендации.

Глава 1. Обзор методов оценки качества распознавания

§1.1. Постановка задачи

В связи с тем, что в распознавании образов пока еще нет четко устоявшейся терминологии, приведем сначала основные определения, которые будут использоваться в данной работе.

Описание объекта. Объект характеризуется набором своих признаков, как качественных, так и количественных. Считается, что число признаков конечно и

любой объект 2Г однозначно задается значениями признаков хр = 1 ,п. Совокупность

значений признаков X/ определяет описание объекта /(г,.) для объекта гг [4, 89]. Набор признаков всегда один и тот же для объектов, рассматриваемых при решении конкретной задачи.

Класс объекта. Практически во всех работах по распознаванию образов предполагается наличие множества М, состоящего из объектов 2. Множество М

т

разбито на конечное число подмножеств К^М-^К^, которые и называются

;=1

классами объектов [39, 51].

Таблица эталонов. Разбиение множества М на классы в общем случае определено не полностью. Задана лишь некоторая информация /0(А'| ,..,Кп) о классах К!. Такую информацию часто представляют в виде прямоугольной таблицы эталонов Т (табл. 1.1). По каждой строке табл. 1.1 указан класс К1, которому

принадлежит объект гг, имеющий описание 1{гг). Таблица содержит конечное число

строк (объектов) гг и столбцов (признаков) хс известными значениями а ■.

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

Таблица 1.1

Объекты X, х2 хп Классы

«1,1 «1,2 аи «1 ,й

«2,1 «2,2 «2,и

... ... ... ... ...

2 г\ агь\ йгь 2 аП,п

... ... ... ... ...

аП-1+1Л «^,+1,2 ап- 1+1.У аП-Х+\,п

*»}_,+ 2 ^-1+2,1 аП-\+2,2 ап- 1+2.У аг,_х+2,п

... ... ... ... ...

ап,\ анЛ

... ... ... ... ...

2гт_\+1 агт-х+ 2,1 агт-1+\,2 агт- 1+1.У Кт

^„,4+2 <4,-1+2,1 йгт~ 1+2,2 «г„,ч+2,« Кт

... ... ... ... ...

2г 'т агт,2 ... «г / Я? >./ а>т>п Кт

2 Ъх ь2 ... Ь> Ът К7

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

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

Экзаменационная выборка (). Понятие экзаменационной выборки родственно обучающей выборке. Однако при ее формировании возможны два случая. В первом -в экзаменационную выборку включаются только объекты, не вошедшие в обучающую выборку. То есть множества объектов для обучения и экзамена не пересекаются. Во втором - наоборот их пересечение считается возможным и в экзаменационную выборку включаются объекты, уже вошедшие в обучающую выборку [47].

Таблица 1.2

Объекты X] х2 Хп Классы

а$2,г К*

... ... ... ... ... ...

■V а*„\ ав„п

£ - номер обучающей выборки; / -число объектов в обучающей выборке Р8. Таким образом, мы основываемся на предположении о вероятностной

концепции экзаменационной и обучающей выборок. Считаем, что обе выборки

сформированы из некоторой единой генеральной совокупности, которая не всегда

полностью известна, но обязательно подразумевается [25]. Для упрощения

дальнейшего изложения будем считать, что описания объектов, составляющих

экзаменационную или обучающую выборки, могут быть представлены в том же виде.

что и таблица эталонов. Таким образом, табл. 1.2 будет задавать обучающую выборку

Р, а табл. 1.3 -контрольную ().

Таблица 1.3

Объекты X, %2 ... х] ... Классы

аК\ акЛ аы ... ак1,п Ч

Ч2 ан2л ак2л ... ак2,п К1г2

... ... ... ... ... ...

%2 ... ... акч,п "д

к - номер обучающей выборки; ц -число объектов в обучающей выборке (2/;.

Класс алгоритмов. Алгоритмы распознавания, использующие родственные

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

Интеллект алгоритма (качество распознавания). Способность обучаться из опыта - отличительная черта любого живого существа. Насколько успешным окажется обучение, при прочих равных возможностях (здесь имеется в виду и время обучения, и примеры, на которых проводится обучения, и наличие или отсутствие учителя), и определяется интеллектом обучаемого. В общем случае интеллект понимается как интенсивность процесса получения нового знания из уже имеющейся информации [104]. Для искусственных систем интеллект определяется как процесс, посредством которого система уточняет свои характеристики на задаче или множестве задач с опытом через какое-то время [75, 76].

Вернемся к определению описания объекта. В дальнейшем, не нарушая

общности рассуждений, будем считать, что все признаки в описании объекта

квантованы по уровням, т.е. они могут принимать только дискретные значения. Это

заключение основано на том, что всякое значение признака определяется прибором, а

любой прибор имеет свой предел точности. Поэтому практические потребности вовсе

не диктуют условие непрерывности значений признаков. Такое допущение позволяет считать, что общее число различных объектов всегда конечно. Исходя из данного набора признаков, как правило, можно составить описаний намного больше, чем их содержится в обучающей выборке. Поэтому при конечном числе различных описаний важным становится соотношение числа объектов в таблице эталонов с числом теоретически возможных комбинаций, составленных из значений признаков объектов. От этого соотношения во многом зависит то, какой класс алгоритмов выбрать для распознавания.

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

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

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

- неполным знанием вероятностных характеристик самих оценок.

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

Второе - обусловлено низким качеством описаний объектов, недостаточной информативностью признаков и не может быть снято за счет увеличения обучающей выборки. Даже при бесконечном росте объема обучающей выборки и точном значении оценок вероятностей сохраняется случайная природа решений и, следовательно, возможны ошибки распознавания. Ошибки станут минимальными, если объекты распознавать по максимуму апостериорной вероятности. Такой метод математически точно дает наименьшую ошибку распознавания [22]. Считаем, что в процессе обучения за некоторый конечный интервал времени можно получить

приближенное значение априорных вероятностей Р(х,) и Р{К• ), где Р(хг) -вероятность появления признака хг-; ) - вероятность появления объекта из класса К]. Согласно формуле Байеса апостериорная вероятность того, что объект г принадлежит классу А' • при наличии в описании признака хг-, рассчитывается по формуле:

Р^^ ) = Р(Ку |Р^ )/Р(Х/)]. (1.1)

Величина у(х1) = р(х; А )/р(х,) рассматривается как вес признака х,- и

используется при принятии решения о том, что некоторый объект гг принадлежит классу А' • . Если входное изображение характеризуется п независимыми признаками, то формула (1.1) принимает вид:

Р{К] \хих2,..,хп)= Р(К/ )П гМ, (1.2)

¿=1

Для нахождения веса призн�