Об одном семействе рекуррентных алгоритмов распознавания, основанных на случайных разбиениях множества допустимых объектов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение.3 3

Глава I. Семейство рекуррентных алгоритмов распознавания.13 13

§1» Описание семейства алгоритмов,.* 13 13

§2. Предварительные результаты.16 16*

§3. Сходимость алгоритмов в точке. 24 24

§4. Сходимость алгоритмов почти всюду в одном частном случае.35 35

Глава П. Оценки трудоемкости алгоритмов.49 49

Глава Ш. Вопросы практической реализации алгоритмов.59 59

§1. Два способа, реализации алгоритмов.59 59

§2. Метод случайных перестановок.64 64

§3. Решение практических задач.67 67

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

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

§е К' для каждого ^ £ .

В большинстве прикладных задач исходная информация о классах представляет собой набор описаний по совокупности признаков II конечного числа объектов из • \ * - РЛя каждого из которых точно известно, к какому из I классов относится данный объект. Никаких других сведений о классах не имеется.

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

Модели статистических алгоритмов распознавания. Если бы исходные сведения о массах включали в себя информацию о плотности распределения в К точек каждого класса, то оптимальное ( в смысле минимума среднего риска) решение задачи распознавания произвольной точки ЗеК давалось бы байесовским подходом. Однако в силу неполноты априорной информации непосредственно этот подход применен быть не может. Был предложен целый ряд процедур, в которых по начальной информации о конечном числе объектов ■ ^т ) оценивались необходимые плотности вероятностей, после чего полученные оценки использовались для проведения байесовского анализа [2, 4, 16] . При этом оценивание носило как параметрический характер (когда плотности предполагались известными с точностью до параметров), так и непараметрический (метод окна Парзена, ближайших соседей, и т. д.). Поскольку, как правило, начальная информация недостаточна для получения достоверных оценок, указанные методы распознавания могут рассматриваться как эвристические.

Модели, основанные на принципе разделения [2, 131 . Алгоритмы этих моделей используются в тех случаях, когда правдоподобно предположение о том, что объекты разных классов могут быть хорошо разделены одной или несколькими поверхностями заданного вида. При этом вид поверхности задается с точностью до параметров, для определения которых используется начальная информация УД^) •

Модели, основанные на принципе потенциалов £1, 15 7• Принцип потенциалов использует соображение о том, что влияние каждой из , на распознавание точек из К. максимально в непосредственной близости от ¿¿и убывает по мере удаления от 3; • Б этих методах решение вопроса о свойствах 8 £ КУ основывается на сравнении величин суммарного влияния на В точек , принадлежащих и не принадлежащих К^ ,

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

12, 17] *

Модели вычисления оценок [б! • Алгоритмы этих моделей основаны на принципе частичной прецедентности, В указанных алгоритмах на основании исходной информации ) и описания по определенному правилу оцениваются некие характеристики близости частей описания р и объектов Ьи---** т. , принадлежащих разным классам. Полученные оценки используются затем для вывода общих оценок объекта по классу, по значениям которых и устанавливается свойство в £ К^ ? ^ = У,. ^ £

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

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

Накопленный опыт работы с методами распознавания и их моделями позволил перейти к построению общей теории распознающих алгоритмов [7, 8] . Было предложено рассматривать алгоритм распознавания как произведение двух операторов: /)=ЯЙ ' . При этом распознающий оператор переводит начальную информацию задачи, состоящую из описаний и 3(5',., 5*) , где З^б -■ ?с{,) - предъявленные к распознаванию объекты, в числовую матрицу размера ^ х I , ( I ,^ )-ый элемент которой есть оценка объекта З*' по классу КУ • Оператор ^ - решающее правило - переводит полученную матрицу оценок в матрицу окончательных ответов. Для операторов Й.д вводятся действия сложения, умножения, умножения на скаляр как специально определенные действия над соответствующими матрицами. В модели путем подбора параметров выделяются базисные операторы, так что любой другой оператор модели представляется операторным полиномом конечной степени над базисными операторами. Если решающее правило Хц фиксировано, то из такого представления распознающих операторов легко следует аналогичное представление алгоритмов распознавания.

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

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

Среди существующих на сегодня эвристических алгоритмов распознавания можно выделить группу с условным названием - локальные алгоритмы. Указанные алгоритмы характеризуются тем, что при их использовании каждая точка обучающей выборки участвует в распознавании точек только некоторой области, определяемой в процессе обучения. Форма и размеры области являются случайными, зависящими от предъявленной обучающей совокупности. К таким алгоритмам относятся, например, алгоритмы типа "ближайшего соседа" £12, 173 » а также корректные алгоритмы, построенные в модели вычисления оценок [8], в которых в результате обуче» ния вокруг каждой точки обучающей выборки выстраивается так на** зываемая область устойчивого распознавания.

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

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

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

Основой предлагаемого семейства алгоритмов является случайное разбиение множества допустимых объектов, индуцируемое последовательно предъявляемыми точками обучающей выборки. Разбиение осуществляется гиперплоскостями, проходящими через точки обучения и перпендикулярными некоторым направлениям. При этом на каждом шаге, то есть после предъявления очередной точки обучения, разбивается то и только то из подмножеств множества допустимых объектов, полученных на предыдущих шагах, в которое попадает данная точка обучения. Заметим, что основная идея локальных алгоритмов близка также и методу потенциальных фикций, имеющему рекуррентный характер, - в этом методе вокруг каждой точки обучения строится область, точки которой с разными весами относятся к тому же классу, что и соответствующая точка обучения. Однако вид области в этих алгоритмах определяется априори заданной потенциальной функцией При практическом использовании метода выбор потенциальной функции представляет собой определяющий момент для удачной работы алгоритма. Чем более "вычурной" оказывается истинная разделяющая функция, тем более близкой к ¿Г-функции должна быть для того, чтобы процедура метода сходилась к разделяющей функции. Наоборот, при большой области множества допустимых объектов очень "узкие" потенциаяьные функции могут не обеспечить распознавание всех точек области после предъявления конечного числа обучающих векторов. Для сбалансирования этих требований, а также для учета при выборе потенциальной функции информации, содержащейся в обучающей выборке, авторы метода предлагают рассматривать потенциальную функцию зависящей от параметра с/. - Ы.) 0 «=• и подбирать значение этого параметра в каждом случае экспериментально.

Аналогичное разбиение рассматривалось в работе [II] при построении одной схемы случайного поиска.

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

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

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

В работе предлагаются два способа практической реализации алгоритмов, В первом способе вначале осуществляется обучение, а затем распознавание заданных точек из множества допустимых объектов. Во втором способе процесс распознавания заданной точки проводится одновременно с предъявлением точек обучающей выборки. Показано» что при любой размерности пространства в первом способе оценка средней трудоемкости процесса обучения при больших п заключена в пределах от 0(пРп к) до 0(пе*2-^ , средней трудоемкости распознавания одной точки - от 0(2нп) до О(вн^п) . Во втором способе величины порядка ОС&гк) и 0({!пгП') дают при больших п соответственно нижнюю и верхнюю оценки для числа точек обучения, участвующих в распознавании заданной точки из К •

Отметим, что нам известны два аналогичных результата о трудоемкости алгоритмов распознавания. Первый из них относится к правилу ближайшего соседа в случае двухмерного признакового пространства. В работе [18] показано, что после проведения некоторого предварительного построения трудоемкость нахождения среди п точек точки, ближайшей к данной, может быть оценена при больших п величиной порядка 0(йг7п) , Трудоемкость предварительного построения, состоящего в построении диаграммы Вороного для данных и- точек обучения, оценивается величиной порядка О(пОкп) , Второй результат, полученный также для плоскости, относится к алгоритму распознавания, в котором в процессе обучения для множества Л; точек обучения, принадлежащих классу К^ , Р) + п^-Уь 9 строится его минимальная выпуклая оболочка Ь; , а распознавание произвольной точки состоит в определении положения этой точки относительно каждой из 1лI . В работе Сз] изложен алгоритм построения выпуклой оболочки множества точек на плоскости, который позволяет при больших п- указать в качестве трудоемкости обучения в рассматриваемом алгоритме распознавания величину порядка 0(к&гп) . с другой стороны, в [10] приведен результат о том, что ожидаемое число сторон минимальной выпуклой оболочки множества п- точек, равномерно распределенных в некотором выпуклом многоугольнике, возрастает с ростом п как (лгк \ Поэтому, если каждый из

Ь классов представляет собой выпуклый многоугольник, а точки обучения выбираются в К согласно равномерному закону распределения, средняя трудоемкость распознавания одной точки в указанном алгоритме может быть оценена величиной порядка 0[Ьгп) .

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

Во второй главе получены оценки характеристик трудоемкости алгоритмов.

Третья глава диссертации посвящена вопросам практической реализации алгоритмов. Здесь предлагается представление случайных разбиений множества допустимых объектов в виде дерева. Такое представление позволяет получить два эффективных способа реализации алгоритмов. Второй вопрос, рассматриваемый в данной главе, связан с тем, что результат применения предложенных алгоритмов в случае заданной фиксированной выборки конечного объема гь зависит от порядка предъявления точек обучения и от выбранных направлений секущих гиперплоскостей. Чтобы сделать результаты работы алгоритмов нечувствительными к указанным факторам, предлагается использовать один прием, приводящий к неким естественным детерминированным результатам. Наконец, в данной главе приведены результаты решения на ЭВМ с помощью введенных алгоритмов двух практических задач. Величина ошибки в обеих задачах при распознаваний "неизвестных" объектов оказалась не превосходящей 8$.

В приложении приведены описания и тексты двух программ, соответствующих двум способам реализации алгоритмов, описанным в главе Ш. Программы написаны на языке АЛГ0Л-60 для ЭВМ БЭСМ-6 ВЦ АН СССР.

Основные результаты, полученные в работе, опубликованы в [19-21] ,

Автор выражает искреннюю благодарность своему научному руководителю Ю.И.ЖУРАВЛЕВУ за постоянное внимание к работе.

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

Количество пермутаций Точность распознавания контрольного массива (в %) Число ошибок

I 73.0 17

10 85.7 9

20 92.0 5 от 30 до 200 93.7-96.8 2-4

Время счета 5 ; 20" .

Алгоритм Б ("суммирование в случае неравенства")

Количество Точность распознавания Число пермутаций контрольного массива (в %) ошибок I от 10 до 20

70.0

87.3

18 8 от 30 до 120 88.9-90,5 6-7 от 130 до 200 92.0-93.7 4-5

Время счета 5 1 4011 .

Задача технической диагностики. Одним из основных элементов конструкции автобуса является его несущая система. Стоимость несущей системы, ее эксплуатационные качества, а также трудоемкость при капитальном ремонте на 70-80$ определяют соответствующие характеристики всего автобуса.

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

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

Такая классификация несущих систем производится на основании значений трех основных групп признаков: функциональные (срок эксплуатации, возраст, надежностные характеристики), технические (количество обрывов, вмятин, степень коррозийного повреждения, угол закручивания по базе и т. д.) и экономические (материалоемкость и трудоемкость при капитальном ремонте, время нахождения в ремонте и т. д.). В нашей задаче, поставленной как задача распознавания, были использованы 17 признаков, из которых семь являлись действительными числами, а десять - экспертными оценками. Предъявленные объекты (всего 91) по своему техническому состоянию разделялись на четыре класса (первый - 15 объектов, второй - 39, третий - 23, четвертый - 14). Для обучения использовались 20 объектов (соответственно, 4, 7, 5 и 4 для первого -четвертого классов). Остальные 71 образовали контрольный массив (II, 32, 18 и 10). Так же, как и в первой задаче, для каждого класса вводились веса, обратно пропорциональные долям классов в обучении. Таким образом, алгоритмы (1.1.1) и (1.1.2) использовались с некоторыми изменениями, описанными в предыдущей задаче. Результаты работы алгоритмов следующие. Алгоритм А ("распознавание по последней точке").

Количество Точность распознавания пермутаций контрольного массива (в %)

Число ошибок

I 10 от 20 до 200

97.2 93.0 95.8 2 3 5

Время счета 3 ' 16.

Алгоритм Б ("суммирование в случае неравенства")

Количество Точность распознавания Число пермутаций контрольного массива (в %) ошибок

I 95.8 3

10 93.0 5 от 20 до 200 95.8 3

Время счета 3 1 547/

1. Айзерман М*А*, Бравермая Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: "Наука", 1970*

2. Вапник В*Н,, Червоненкис А.Я* Теория распознавания образов, М.: "Наука", 1974,3* Гренандер У. Лекции по теории образов » Т.2* Анализ образов, М.: "Мир", 1981.

3. Дуда Р., Харт П. Распознавание образов и анализ сцен» М.: "Мир", 1976*

4. Евграфов М.А- Асимптотические оценки и целые функции. М.: "Наука", 1979.

5. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок. Кибернетика, 1971, №3, И1.

6. Журавлев Ю,И. Об алгебраическом подходе к решению задач распознавания и классификации. В сб.: "Проблемы кибернетики". М.: "Наука", 1978, вып.ЗЗ, 5-68.

7. Журавлее Ю.И, Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I. Кибернетика, 1977, №4, 5-17; П. Кибернетика, 1977, №6, 21>27; Ш. Кибернетика, 1978, №. 35-43.

8. Колмогоров А.Н. Основные понятия теории вероятностей. М.: "Наука", 1974.

9. Кендалл М., Моран П, Геометрические вероятности. М.: "Наука", 1972.

10. Левин А.Ю., Шварц А.С* Об одной схеме случайного поиска. В сб.: "Труды семинара по функциональному анализу". Воронеж, 1963, вып.7, 67«69.

11. Себастиан Г.С. Процессы принятия решений при распознавании образов. Киев: "Наукова думка", 1965.

12. Ту Д., Гонсалес Р. Принципы распознавания образов. М,: "Мир", 1978.

13. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: "Мир", 1967.

14. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: "Наука", 1968.

15. Цыпкин Я.З. Основы теории обучающихся систем. М.: "Наука", 1970.

16. Саосл. Т. М.? Р. ё. О^гал&и: п^АЛсп /р&Л&иж

17. Л й ё Ё Тссы^и . . Зкахугу?

18. МгСигьО^ ОТ1. Л. мёЛгъсС и^сг^ф.ижп. О*г- . Ор. у. р4345\ М4-&33.

19. Промахина И.М. Об одном рекуррентном алгоритме распознавания. В сб.: Всесоюзный научно-практический семинар "Прикладные аспекты управления сложными системами". Тезисы докладов. М., 1983, 268-269.

20. Промахина И.М., Коростелев А.П. Об одном классе стохастических рекуррентных алгоритмов распознавания. Препринт. М.: ВНИИСИ ГКНТ и АН СССР, 1984.

21. Коростелев А.П., Промахина И.М. Об одной задаче о случайных разбиениях в непараметрическом алгоритме распознавания. В сб.; Теория сложных систем и методы их моделирования. Труды семинара. М.: ВНИИСИ ГКНТ и АН СССР, 1984, 76-86.