WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 |

«РЕКУРРЕНТНЫЕ АЛГОРИТМЫ ОБУЧЕНИЯ И САМООБУЧЕНИЯ В ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ ( ...»

-- [ Страница 1 ] --

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

На правах рукописи

Измакова Ольга Анатольевна

РЕКУРРЕНТНЫЕ АЛГОРИТМЫ

ОБУЧЕНИЯ И САМООБУЧЕНИЯ

В ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ

(01.01.09 дискретная математика и математическая кибернетика)

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научные руководители:

доктор физико-математических наук профессор ФОМИН В. Н.

доктор физико-математических наук профессор ГРАНИЧИН О. Н.

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

Литература, посвященная распознаванию образов, весьма обширна. К ней относятся как работы теоретического характера ([1], [17], [24], [36], [37], [40], [41], [43]–[45]), так и работы, в которых обсуждаются вопросы функционирования конкретных опознающих систем ([18], [30]). Такое разделение достаточно условно, поскольку большинство работ первой группы также содержит практические рекомендации и результаты моделирования конкретных опознающих систем.

В диссертации рассматриваются актуальные на современном этапе вопросы теории распознавания образов.

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

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

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

По материалам диссертации были сделаны доклады на Первой международной конференции по мехатронике и робототехнике (Санкт-Петербург, 2000 г.), на заседании международной школы-семинара “Адаптивные роботы – 2004” (Санкт-Петербург), а также на семинарах кафедры теоретической кибернетики математико-механического факультета Санкт-Петербургского государственного университета. Основное содержание работы

было опубликовано в работах ([11], [14], [15], [19] – [21], [38]), часть из которых написана в соавторстве с научными руководителями В. Н. Фоминым и О. Н. Граничиным, которыми осуществлялась общая корректировка направлений исследования. В статье, написанной в соавторстве с С. С. Сысоевым, диссертанту принадлежит метод решения и его обоснование, а ее соавтору численное моделирование представленного алгоритма.

Диссертация организована следующим образом.

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

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



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

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

Метод изложен на абстрактном уровне и позволяет строить проекцию заданного элемента гильбертова пространства на замкнутую линейную оболочку набора конечномерных подпространств в предположении, что имеется возможность вычислять ортогональные проекции на произвольные конечномерные подпространства. Уточним постановку задачи. Пусть в гильбертовом пространстве H задана последовательность {Hk, k = 1, 2,...} базисных подпространств Hk (которые предполагаем конечномерными).

Пусть задан также элемент f H. Требуется найти ортогональную проекцию этого элемента на замкнутую линейную оболочку заданных подпространств, предполагая, что алгоритм вычисления искомой проекции может содержать только проектирование на Hk, k = 1, 2,..., дополненное одномерными проекциями. Обозначим через f1 = PH1 f ортогональную проекцию элемента f на базисное подпространство H1, а через H2 = Lin{H2, f1} линейную оболочку, порождаемую базисным подпространством H2 и элементом f1. Продолжая этот процесс, введем элементы fn и подпространства Введение Hn+1 согласно алгоритму:

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

Лемма 1. Для произвольного элемента f H и последовательности подпространств {Hk H, k = 1, 2,...} для последовательных проекций {fn, n N} справедливо предельное равенство некоторый элемент из замкнутой линейной оболочки, порождагде f емой подпространствами {Hk, k = 1, 2,...}.

Для того, чтобы установить условия, при которых предел последовательных проекций {fn, n = 1, 2,...} совпадает с искомой проекцией, введем следующее определение.

Определение 1.1 Последовательность {Hk H, k = 1, 2,...} назовем чередующейся, если каждый из элементов встречается в ней бесконечное число раз.

Теорема 1. Если последовательность базисных подпространств {Hk H, k = 1, 2,...} чередующаяся, то для произвольного элемента f H последовательные проекции fn, n = 1, 2,..., построенные в соответствии с алгоритмом (1), сходятся к ортогональной проекции элемента f на замкнутую линейную оболочку подпространств {Hk, k = 1, 2,...}:

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

Введение Третья глава посвящена развитию рандомизированных алгритмов стохастической оптимизации, адаптированных для решения задачи самообучения. Проблема самообучения ставится следующим образом. Пусть на вход обучающейся опознающей системы поступают входные сигналы или стимулы. Предположим, что множество стимулов состоит из элементов, каждый из которых принадлежит одному их l классов (число l конечно и известно заранее). Будем обозначать векторы, описывающие объекты, подлежащие классификации, через x. Вектор x, соответствующий определенному объекту, состоит из m компонент, называемых признаками, а последовательность векторов x1, x2,..., xt,..., соответсвующих стимулам, поступающим на вход опознающей системы, будем считать реализацией некоторой последовательности независимых, одинаково распределенных случайных величин. Пусть закон их распределения P (·) неизвестен. Всякий способ классификации связан с “потерями” ошибками классификатора, которые обычно характеризуются с помощью так называемых штрафных функций (функций стоимости) q k (x, T ), k = 1, 2,..., l (l число классов), зависящих, в частности, от матричного параметра T = (,,..., l ), ( k Rm k = 1, 2,...l), который удобно интерпретировать как набор центров классов. Функционал среднего риска в задаче самообучения имеет смысл математического ожидания общих потерь и может быть записан в виде где {Xk (T )}l разбиение выборочного пространства на l непересекаюk= щихся подмножеств Проблема самообучения распознаванию образов формулируется следующим образом: по заданной обучающей последовательности найти оценку значения T, которое доставляет минимум функционалу среднего риска и через разбиение {Xk (T )}l выборочного пространства определяет оптиk= мальное правило классификации.

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

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

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

Пусть задача самообучения осложнена тем, что функции q k (·, ·) не заданы аналитически, но их значения доступны измерению (может быть с помехами):

Через Y (x, T ) будем обозначать l-мерный вектор, составленный из величин y k (x, T ), k = 1, 2,..., l; через V l-мерный вектор помех. Для характеk ристических функций множеств X (T ) будем использовать обозначения JXk (T ) (·), (k = 1, 2,..., l), для образованной из них вектор-функции J(·, T ).

Формирование последовательности оценок {Tn } оптимального набоn= ра T может быть проведено в соответствии с одним из представленных ниже рандомизированных алгоритмов стохастической аппроксимации. Алгоритмы основаны на использовании наблюдаемой последовательности слуВведение чайных независимых друг от друга векторов n Rm, n = 1, 2,..., называемых в дальнейшем пробным одновременным возмущением и составленных из независимых бернуллиевских, равных ±1 случайных величин.

Зафиксируем некоторый начальный набор T0 Rml и выберем последовательности положительных чисел, стремящиеся к нулю: {n } и {n }.

Рассмотрим следующие алгоритмы построения искомой последовательности оценок:

Здесь PT оператор проектирования на некоторое выпуклое замкнутое ограниченное подмножество T Rml, которое содержит точку T. Будем предполагать, что такое множество известно.

Для того, чтобы упростить формулировку и доказательство основного результата третьей главы, ограничимся случаем однотипных функций q k (x, T ), k = 1, 2,..., l. Кроме того, будем предполагать, что функции q k (x, T ) = q k (x, k ) и не зависят от других векторных элементов набора T.

Таким образом, считаем, что q k (x, T ) = q (x, k ) (здесь q (·, ·) : XRm R некоторая общая для разных классов штрафная функция).

Сформулируем предположения, которым должна будет удовлетворять штрафная функция q (·, ·): П.1. Функция q (x, ·) : Rm R дифференцируема при любом x X и их градиенты удовлетворяют условию Липшица, т.е.

с некоторой постоянной M > 0, не зависящей от x X.

Введение П.3. Каждая из функций имеет единственный минимум в Rm в некоторой точке k и с некоторой постоянной µ > 0 : M > µ (условие сильной выпуклости).

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

Теорема 2. Пусть выполнены условия:

(П.1,2,3) для функции q (·, ·);

n 1 случайные вектора V1±, V2±..., Vn и x1, x2,..., xn1 не зависят от xn, n, а случайный вектор xn не зависит от n ;

E{vn} <, E{vn} n, |vn | Cv, Cv > 0;

n n = и n 0, n 0, n n 0 при n. Если обучающая последовательность x1, x2,..., xn,... состоит из независимых, одинаково распределенных векторных случайных величин с таким законом распределения, что они с ненулевой вероятностью принимают значения в каждом из l классов в пространстве признаков и из выполнения для некоторых k из {1, 2,..., l}, x Xk (T ) и неравенства |(x, )| dmax следует тогда последовательность оценок {Tn }, доставляемых алгоритмом (1) (или алгоритмом (2)) при произвольном выборе T0, сходится к точке T в среднеквадратичном смысле: E{ Tn T 2} 0 при n в том случае, когда Если, более того, n n n + n n вероятностью единица.

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

Принцип селекции или эвристической самоорганизации нашел свое отражение в одном из методов аппроксимации функций, развитом А. Г. Ивахненко ([18, 30]) и получившем название метод группового учета аргументов (МГУА). Кратко этот метод может быть описан следующим образом: на каждом шаге последовательной аппроксимации исходная конечная система функций специальным образом расширяется, из полученной расширенной системы выбираются всевозможные наборы из заданного числа функций и для каждого набора решается стандартная задача аппроксимации. Из функций, давших наилучшее приближение, формируется система, рассматриваемая как исходная на следующем шаге аппроксимации. Достоверность МГУА подтверждается многими численными примерами ([18]). Однако в связи с релизацией в обсуждаемом методе принципа свободы выбора решений представяется возможной потеря на первых циклах алгоритма важных базисных функций, наличие которых в дальнейшем может оказаться необходимым для получения более точных оценок. В [18] утверждается, что такой потери функций не происходит, и они включаются в оптимальное приближение косвенным образом. К сожалению, доказательства сходимости алгоритма МГУА нет.

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

Знания о функционировании нервной системы живых существ легли в Глава 1. Задача распознавания образов основу однй из областей современной теории интеллектуальных вычислений, связанной с построением и применением искусственных нейронных сетей (ИНС). В течении последнего десятилетия данная тематика завоевывает все большую популярность, ей посвящается значительное количество современных научных исследований. В значительной степени это связано с тем, что модели, разработанные в рамках данного направления, все более серьезно рассматриваются в качестве методологического базиса для создания сверхскоростных технических устройств параллельной обработки информации. В диссертации дано краткое описание биологических основ функционирования нейронов и нейронных сетей, рассмотрены некоторые подходы к описанию искусственных нейронных сетей. Основу функционирования нейронных сетей составляют алгоритмы обучения, позволяющие оптимизировать ее весовые коэффициенты. В качестве алгоритмов обучения нейронных сетей могут быть успешно использованы развитые в настоящей работе алгоритмы. В качестве примера применения представленных рандомизированных алгоритмов рассмотрена задача обучения нейронной сети Хебба-Хопфилда, и предложен метод ее решения, использующий рекуррентные рандомизированные алгоритмы самообучения 1 и 2.

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

Фиксация конкретного значения параметра определяет конкретную опознающую систему. Роль обучения в этом случае сводится к нахождению или оценке требуемого параметра. Процесс обучения имеет два возможных варианта обучение с учителем и самоообучение. Обучением с учителем называется вариант постановки задачи, когда для каждого элемента xk тренировочного множества известна априорная классификация, т. е. известно, к какому классу принадлежит изображение xk, и эта информация сообщается системе. Если априорная классификация обучающего множества не известна, встает задача, называемая обучением без учителя или самообучением. Изображения, поступающие на вход системы, воспринимаются ею с помощью конечного набора рецепторов, т. е. с помощью конечного набора вещественных функций, определенных на множестве изображений. Набор значений всех признаков (значений рецепторных функций), отвечающих данному изображению, называем его описанием. Описание изображения удобно трактовать как точку в конечномерном пространстве пространстве признаков, которую также часто называют признаковым изображением. Класс входных сигналов с помощью рецепторов отображается в некоторое множество в пространстве признаков, которое называется классом изображений в пространстве признаков. Имеется существенное различие между классами в пространстве входов и классами в пространстве признаков. По определению, классы входных сигналов (образы “идеальных” изображений) непересекающиеся множества, а отвечающие этим классам подмножества в пространстве признаков могут пересекаться. Обозначим через X пространство признаков, и через Xi классы изображений (подмножества пространства X). Будем предполагать, что число классов изображений известно и равно l.

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

Например, возможен учет следующих априорных сведений:

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

не пересекаются не только множества X1, X2,..., Xl, но и их выпуклые оболочки, т. е. имеет место попарная линейная разделимость признаковых классов изображений;

множества X1, X2,..., Xl пересекаются: в этом случае безошибочная классификация невозможна.

Детальное обсуждение различных постановок задач теории распознавания можно найти, например, в работах Айзермана М. А., Бравермана Э. М., и Розоноэра Л. И. ([1]), Загоруйко Н. Г. ([17]), Фомина В. Н. ([36], [37]), Цыпкина Я. З. ([40]), Якубовича В. А. ([43], [44]).

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

в рассматриваемых задачах размерность пространства образов весьма велика: (102 – 105), а часто и больше, в связи с чем затруднительно пользоваться решающими правилами, требующими вычисления матриц порядка 102 102 – 105 105, а затем обратных к ним;

необходимость малогабаритных технических реализаций приводит к специфическому требованию: элементы тренировочной последовательности должны предъявлятся машине не одновременно, а последовательно. Если при входе каждого нового элемента xn тренировочной последовательности новое значение параметра Tn+1 определяется лишь этим элементом и старым значением Tn, такой рекуррентный алгоритм задается уравнениями значением T0 и условием остановки и называется алгоритмом с памятью единица. Возможны более сложные варианты рекуррентных алгоритмов, например алгоритмы с памятью 2, имеющие вид и аналогичные с памятью больше 2.

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

Предположим, что при прогонке через алгоритм (6) обучающей последовательности Глава 1. Задача распознавания образов будет выполнено Такие алгоритмы называются циклически сходящимися.

Если при прогонке через алгоритм любой бесконечной обучающей последовательности для значений (6), начиная с некоторого целого n будет выполнено то алгоритм называется конечно-сходящимся. Если алгоритм обучения конечносходящийся, то опознающая система обучается за конечное, но неизвестное заранее число шагов. Отметим, что обученная система не обязательно правильно опознает все элементы тренировочной последовательности: правильно классифицироваться будет лишь “хвост” бесконечной обучающей последовательности, а изображения, поступившие в начальной стадии обучения могут опознаваться неправильно. В том случае, когда тренировочная последовательность составлена из конечного множества изображений, каждое из которых встречается в последовательности бесконечное число раз, в частности, имеет вид (7), обученная с помощью конечно-сходящегося алгоритма система будет правильно классифицировать все тренировочное множество.

2 Задача распознавания как задача аппроксимации индикаторной функции Каждая опознающая система является с математической точки зрения функцией, аргументами которой являются входные сигналы, а значениями ответы системы. Рассмотрим двухклассовый вариант задачи распознавания, к которому часто может быть сведен общий случай, и обсудим его строгую математическую постановку в виде задачи об экстраполяции функции ([1], [36], [37], [40], [15]).

Пусть на некотором подмножестве евклидова (признакового) m-мерного пространства Rm определена бинарная функция f (·), причем без ограничения общности можно принять, что функция f (·) принимает значения ±1.

Множества X1 = {x : f (x) = 1} и X2 = {x : f (x) = 1} интерпретируются как классы изображений в признаковом пространстве и предполагаются компактными непересекающимися множествами. Предполагается, что знаГлава 1. Задача распознавания образов чения функции f (·) известны на некоторых конечных подмножествах X и X2 множеств X1 и X2. Требуется экстраполировать функцию f (·), заданную на множестве X1 X2, на все множество X1 X2. Такая задача не является поставленной строго, так как не указано, что понимается под экстраполяцией функции f (·) с конечного подмножества на X1 X2. Всякую экстраполяцию f (·) функции f (·) можно интерпретировать как ее аппроксимацию (задача аппроксимации функций подробно обсуждается в главе 2), при этом погрешность экстраполяции f (·) f (·) желательно сделать минимальной. При геометрическом подходе к распознаванию образов часто достаточно принять, что экстраполирующая функция f (·) имеет тот же знак, что и f (·), на всем признаковом пространстве, точнее, функция f (·) должна находиться из условия Условие (8) не всегда может быть обеспечено, это зависит от структуры функций f (·) и f (·). Критерий качества аппроксимации можно выбрать и из других соображений, например, из условия, чтобы нарушение неравенства (8) происходило на возможно меньшем множестве признакового пространства в теории распознавания образов это требование обычно формализуется как требование минимизировать так называемую вероятность ошибки классификации. Эта вероятность может быть записана в несколько обобщенной форме где Q(·, ·) некоторая неотрицательная функция и P(·) вероятностное распределение, заданное на X1 X2, P(X1 X2 ) = 1. Наилучшая аппроксимация fopt функции f (·) тогда находится из условия где минимум берется по заданному множеству {f } всех допустимых аппроксимирующих функций. При выборе Глава 1. Задача распознавания образов функционал (9) принимает вид:

и называется вероятностью ошибки распознавания. Функционал F (f ) обращается в ноль, если с вероятностью 1 знаки функций f (·) и f (·) совпадают на всем множестве X1 X2. В следующей главе в качестве функционала F (f ), характеризующего качество аппроксимации функции f с помощью набора базисных функций, будет рассмотрен функционал (9) при Q(f, f) = (f f )2.

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

Примем, что в пространстве признаков X выделены два класса изображений: X1 = {x : f (x) > 0} и X2 = {x : f (x) 0}, которые порождаются в X функцией f (·). Назовем их идеальными образами. Пусть также имеется система, организованная так, что при предъявлении ей входного вектора x она “вырабатывает” значения функций 1 (x), 2(x),..., N (x) и вычисляет при заданном векторе коэффициентов T. Тем самым определяются множества (образы):

Таким образом, рассматриваемая система “классифицирует” любой сигнал, относя его либо к множеству X1(T ), либо к множеству X2(T ). Эта классификация может изменяться, если варьировать коэффициенты T. Система, дополненная способом изменения весовых коэффициентов T, может “подгонять” свою классификацию к некоторой требуемой. Если существует вектор T такой, что X1(T ) = X1 и X2 (T ) = X2, то существует принципиальная возможность добиться сколь угодно высокого качества классификации: порождаемые системой образы будут сколь угодно точно совпадать с идеальными. При таком подходе обучение системы сводится к построению в пространстве Rm поверхности, разделяющей множества X1 (T ) и X2(T ), т. е. разделяющей поверхности. Всякую такую поверхность можно рассматривать как приближение к “идеальной” разделяющей поверхности. Приведенная интерпретация обучения системы послужила поводом Глава 1. Задача распознавания образов назвать обсуждаемый вариант теории распознавания образов геометрическим подходом к задаче распознавания.

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

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

Рис. 1.1 Линейно-разделимые классы изображений В рассматриваемой ситуации, решение задачи обучения сводится к построению линейной поверхности, разделяющей выпуклые оболочки заданных множеств, и может быть выполнено, например, с помощью таких известных алгоритмов как “Ява”, “Полоска”, “Отражение” и др. ([36], [39], [45]). Для надежности работы опознающей обучающейся системы следует выбирать разделяющую плоскость, наиболее удаленную от изображений тренировочного множества. Очевидно, такой будет плоскость, проходящая через середину отрезка, соединяющего две ближайшие точки выпуклых оболочек Co X1 и Co X2 классов изображений X1 и X2, перпендикулярно этому отрезку. Приведем рекуррентный алгоритма “Оптимальное разделение” для нахождения искомой плоскости ([?], [36]). Основная задача алгоритма нахождение точек x0 Co X1 и y0 Co X2, реализующих расстояние между множествами Co X1 и Co X2. Остальные построения сложности не вызывают.

Пусть z1, z2,... элементы тренировочного множества и xn, yn точки, аппроксимирующие после n шагов алгоритма точки x0 и y0. Пусть также задано некоторое положительное число, которое предполагается сравнительно небольшим. Предположим, что zn X1. Тогда алгоритм имеет вид:

Глава 1. Задача распознавания образов yn+1 = yn, xn+1 = Если zn X2, то xn+1 = xn, а yn+1 получится по вышеприведенным формулам после замены в них xn и yn соответственно на yn и xn.

Утверждение 1 ([36]) Предположим, что каждое из множеств Co X и Co X2 ограничено и может быть заключено в некоторый шар радиуса R. Пусть в последовательности z1, z2,... элементов тренировочного множества каждое изображение повторяется бесконечное число раз.

Обозначим через Co X1 и Co X2 выпуклые оболочки изображений из тренировочной последовательности, принадлежащих соответственно множествам X1 и X2. Пусть x, y предельные точки для последовательностей {xn}, {yn}, построенных согласно алгоритму “Оптимальное разделение”, и x0, y0 точки, реализующие наименьшее расстояние между множествами Co X Число изменений точек xn, yn в процессе работы алгоритма не превосходит числа Это утверждение показывает, что алгоритм “Оптимальное разделение” конечно-сходящийся, и найденные с его помощью точки x и y при достаточно малом значении параметра сколь угодно точно реализуют расстояние между выпуклыми оболочками множеств X1 и X2. В следующей главе сформулирован и обоснован алгоритм последовательного проектирования, являющийся аналогом алгоритма “Оптимальное разделение” и предназначенный для разделения линейных оболочек множеств X1 и X2.

3.1 Выпуклые множества на единичном кубе Если элементы множеств X1 и X2 вершины единичного куба, то можно модифицировать алгоритм построения разделяющей плоскости так, чтобы Глава 1. Задача распознавания образов направляющий вектор плоскости состоял из нулей и единиц. Этот частный случай важен для приложений, поскольку обладает простой логикой, что существенно при реализации его в электронном вычислительном устройстве.

Приведенный ниже алгоритм ([36]) позволяет строить разделяющую плоскость в случае, когда “оболочки” рассматриваемых множеств не пересекаются (точное определение оболочки вершин единичного куба дается ниже). Отметим, что требование непересечения множеств бинарных векторов является в некотором смысле более сильным ограничением, чем требование непересечения выпуклых оболочек множеств в евклидовом пространстве.

Обсудим необходимые определения и понятия. Пусть x, y бинарные векторы, т. е. векторы, компоненты которых суть нули и единицы. Обозначим через xy вектор z, полученный покомпонентным сложением векторов x и y по модулю 2. Аналогично через xy обозначим вектор z, полученный покомпонентным умножением векторов x и y. Нормой |x| вектора x называется сумма содержащихся в нем единиц. Расстояние (x, y) (расстояние по Хеммингу) и скалярное произведение x, y векторов x и y определяются следующим образом:

Через ei, i = 1, 2,..., N обозначим базисные векторы, у которых i-я компонента равна 1, остальные 0. Очевидно, что всякий бинарный вектор x может быть однозначно представлен в виде где x(i) компоненты вектора x. Понятие вектора, расположенного между заданными векторами x и y, вводится следующим образом. Для этого образуют вектор z = x y, который может быть представлен в виде z = N z (i) ei. Говорят, что вектор w расположен между векторами x и y, если его можно представить в виде Штрих у знака суммы означает. что суммирование ведется по некоторому подмножеству индексов. Геометрически множество векторов, заключенных Глава 1. Задача распознавания образов между x и y, представляет собой множество вершин единичного куба, через которые проходит точка при движении от x к y вдоль ребер куба всевозможными кратчайшими путями.

Множество Q на единичном кубе называется подкубом, если из условия x1 Q, x2 Q следует, что множеству Q принадлежат все вершины, заключенные между x1 и x2. Оболочкой Q множества F на единичном кубе назывется подкуб наименьшей размерности, содержащий это множество.

Будем рассматривать множества F1 и F2, предполагая, что их оболочки Q1, Q2 не пересекаются. Расстоянием (F1, F2) между множествами на единичном кубе называется величина где минимум берется по всем x F1 и y F2. Можно показать, что для точек x0 Q1, y0 Q2, расстояние между которыми равно расстоянию между оболочками Q1, Q2, выполнены свойства:

где z0 = x0 y0. Следовательно, для разделения множеств F1, F2 достаточно построить по формуле (11) вектор z0, который определяет искомую плоскость, согласно формулам (10).

Для нахождения элементов x0, y0, реализующих расстояние между подкубами Q1 и Q2, может быть использован следующий рекуррентный алгоритм. Произвольно выбираются векторы x1 F1 и y1 F2. Допустим, что на n-м шаге алгоритма получены векторы xn Q1 и yn Q2, которые являются n-ой итерацией искомых векторов x0, y0. Пусть системе предъявлен вектор zn. Образуем вектор Тогда Глава 1. Задача распознавания образов Утверждение 2 ([36]) Пусть z1, z2,... бесконечная рекуррентная последовательность векторов, составленная из векторов множеств F1 и F2. Тогда существует конечное N такое, что xn+1 = xn, yn+1 = yn при n N, причем расстояние между оболочками Q1 и Q2 множеств F1 и F2 достигается на векторах xN и yN.

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

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

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

К ним относятся, например, кусочно-линейные поверхности, число параметров которых линейно растет с повышением размерности признакового пространства. Рассмотрим построение нелинейной разделяющей поверхности, определяемой конечным набором плоскостей. Пусть X подмножество евклидова пространства, X1, X2 разбиение этого подмножества X, Глава 1. Задача распознавания образов т. е. X1 X2 = X, X1 X2 =. Предположим, что существует конечное число плоскостей Lj = {c(j), (j) }, j = 1, 2,..., 2N + 1, таких, что для любого x X справедливо неравенство где Геометрический смысл неравенства (13) заключается в том, что каждая плоскость Lj “голосует”за принадлежность элемента x множеству X1 или X2 (если sign[ c(j), x + (j) ] > 0, то плоскость {Lj } относит x к классу X1, если знак обратный к классу X2). Система в целом классифицирует x по большинству поданных голосов. Набор плоскостей {Lj } называется комитетом неравенств, число 2N + 1 порядком комитета.

Известно, что для ограниченных и разделенных положительным расстоянием множеств X1 и X2 существует комитет неравенств конечного порядка ([36]). В предположении существования такого комитета разработаны различные алгоритмы его построения. Приведем одну из возможных рекуррентных процедур для построения комитета неравенств.

Введем обозначения Пусть известно, что для классов X1 и X2 существует комитет неравенств порядка 2N + 1. Более того, будем предполагать, что существует набор T, для которого выполнено условие (13) в усиленном варианте. Именно, для любого x X выполнено неравенство где Глава 1. Задача распознавания образов и, некоторые положительные постоянные. Условие (14) означает, что существует комитет T такой, что происходит правильная классификация, даже если не учитывать положительные “неуверенные” голоса.

Пусть T1 произвольный начальный вектор с векторными компонентаj) ми 1, j = 1, 2,..., 2N + 1. Последующие приближения строятся с помощью обучающей последовательности x1, x2,... по правилу Здесь yn = y(xn);

n последовательность независимых случайных величин, удовлетворяющих при любом n условиям произвольные числа из интервала (0, 2], q > 1.

Утверждение 3 ([36]) Предположим, что обучающая последовательность x1, x2,... составлена из независимых случайных величин со значениями в конечном множестве X, которые имеют одинаковое распределение F, F (X) = 1, а случайные величины n имеют распределение (19).

Предположим, что существует набор T, удовлетворяющий условию (14).

Тогда алгоритм (15) (18) является конечно-сходящимся.

4.2 Переход в спрямляющее пространство Другой способ разделения непересекающихся множеств заключается в переходе в спрямляющее пространство, в котором образы классов X1 и Глава 1. Задача распознавания образов X2 линейно разделимы. Этот путь связан с заданием системы отображений, которая должна быть эффективна. Выбор “хорошей” системы отображений обычно производится с точки зрения таких критериев, как возможность простой схемной реализации и полнота в том или ином смысле.

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

Предположим, что система отображений задана, т. е. задана система вещественных функций, определенных на множестве X = X1X2: {1(·), 2(·),...}.

Теперь задача построения обучающей опознающей системы свелась к задаче аппроксимации индикаторной функции f (·) множеств X1, X2 с помощью функций из заданной системы. Чем лучше функция f (·) будет аппроксимирована с помощью линейной комбинации функций {i(·)}, тем реже будет ошибаться обученная опознающая система. Так же, как и свойства пороговых функций, задача аппроксимации функции с помощью заданного набора функций подробно обсуждается в следующей главе. Там же изложен метод последовательного проектирования, позволяющий избежать некоторых вычислительных трудностей, возникающих при решении поставленной задачи.

5 Самообучение Как отмечалось выше, возможна постановка задачи обучения, в которой указания учителя не используются. В этом случае говорят о самообучении, а процесс обучения сводится к определению последовательности оценок, минимизирующей функционал специального вида. Задача самообучения обсуждалась, например, в [1], [36], [37], [40], [41], [42].

5.1 Автоматическая классификация сигналов Прежде чем переходить к постановке задачи самообучения, целесообразно описать тесно связанную с ней задачу автоматической классификаГлава 1. Задача распознавания образов ции образов ([37], [15]). Ее содержательный смысл состоит в построении правила, которое каждой точке x множества X Rm сопоставляет некоторый образ (класс). Подразумевается, что точки, которым сопоставляется некоторый общий класс, обладают определенным общим свойством, которое и порождает образ.

Правило классификации может быть однозначным (детерминированным), когда каждой точке множества X сопоставляется определенный класс, и недетерминированным, когда каждой точке x X сопоставляются значения некоторого набора функций, определяющих степень достоверности соответствия этой точки каждому из возможных образов. А именно, вводятся функции µ1 (·), µ2(·),..., µl (·) степени достоверности (l число классов, которое предполагается известным), обладающие свойствами:

В случае, когда функции µk (·) принимают лишь значения 0 и 1, получаем детерминистскую задачу.

Выбранный способ классификации может быть связан с “потерями” ошибками классификатора. Будем характеризовать их с помощью штрафных функций q k (x, T ), k = 1, 2,..., l, зависящих от параметра x и параметра T = ( 1, 2,..., l ), который удобно интерпретировать как набор “центров классов”.

Предполагается, что на множестве X выделена -алгебра, на которой определено распределение вероятностей P. Тогда можно вычислить средние потери классификации, определяемые набором µ = (µ1(·), µ2(·),..., µl (·)) и значениями центров классов 1, 2,..., l :

Формальная постановка задачи автоматической классификации состоит в определении наборов T = ( 1, 2,..., l ), µ = (µ1(·), µ2 (·),..., µl (·)) из условия минимизации функционала (21). Минимизация осуществляется в классе произвольных векторов k Rm и функций µk (·), удовлетворяющих условиям (20).

Глава 1. Задача распознавания образов Для фиксированного набора T при варьировании функций k (x) значения суммы, стоящей под знаком интеграла, заполняют всю выпуклую оболочку точек q k (x, T ), k = 1, 2,..., l. Следовательно, минимизация средних потерь классификации достигается на наборе функций (·), в котором k (x) = k j(x,T ), где символ Кронекера, а целочисленная функция j(·, T ) определяется как номер, соответствующий штрафной функции с минимальным значением Разобьм множество X на l классов (образов) X1(T ), X2(T ),..., Xl (T ) по правилу Обозначим через J k (T, x), k = 1, 2,..., l характеристические функции множеств Xk (T ), а через J(x, T ) и Q(x, T ) - l-мерные векторы, первый из которых составлен из значений J k (T, x) и состоит из нулей и единииз q k (x, T ). Учитывая последние замечания и введнные обозначения, функционал (21) можно рассматривать как функцию набора центров классов :

Этот функционал обычно называют функционалом среднего риска. Итак, задача автоматической классификации в принятой постановке свелась к определению l-разбиения пространства X из условия минимизации функционала (23):

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

Глава 1. Задача распознавания образов Если известна плотность p(·) распределения вероятности P, то с учетом вышесказанного функционал (23) может быть записан в виде:

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

Поясним геометрический смысл описанной выше задачи автоматической классификации. Пусть X - вещественное векторное пространство, и штрафные функции имеют похожий друг на друга вид Рассмотрим разбиение множества X на l классов X1(T ), X2(T ),..., Xl (T ) по правилу: к множеству Xk (T ) относятся все точки x, которые находятся к центру k ближе, чем к любому другому (в случае равенства расстояний до нескольких центров, точка x относится к классу, соответствующему центру с меньшим номером). Интеграл определяет рассеяние точек x в множестве Xk (T ). Определенный выше функционал среднего риска (23) принимает вид Таким образом, в рассмотренном случае задача автоматической классификации состоит в определении набора центров k, k = 1, 2,..., l, при которых суммарное рассеяние минимально.

Глава 1. Задача распознавания образов Искомый набор центров должен удовлетворять уравнению F (T ) = 0.

Нетрудно убедиться, что в последнем примере множества Xk (T ) имеют вид многогранников, а минимизирующий функционал среднего риска набор центров T = 1, 2,..., l совпадает с центрами тяжести этих множеств, т. е.

причем центры тяжести соседних множеств находятся на прямой, ортогональной разделяющей множества грани [[37]].

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

Проблема самообучения распознаванию образов может быть сформулирована следующим образом ([12, 36]): по заданной обучающей последовательности x1, x2,... xn,..., которая является реализацией некоторой последовательности независимых одинаково распределенных случайных величин 1, 2,..., n,... (xn =.n выборочное значение случайной величины функционалу среднего риска (23). Разбиение (22) {Xk (T )}l пространства R определяет тогда оптимальное правило классификации.

Одним из наиболее известных подходов к решению задачи самообучения является метод стохастической аппроксимации, к которому естественно отнести стохастические модификации разного рода градиентных и псевдоградиентных процедур. Этот метод доставляет рекуррентные процедуры, Глава 1. Задача распознавания образов удобные при использовании современной вычислительной техники. Например, для получения оценки неизвестного вектора T можно воспользоваться следующей рекуррентной процедурой ([24],[37]):

где {n} некоторая последовательность неотрицательных чисел.

При l = 1 процедура (25) совпадает с процедурой Роббинса-Монро, которая обеспечивает сходимость оценок {Tn } с вероятностью 1 к точке минимума функционала F (T ) при достаточно общих условиях. При l > результаты сходимости процедуры Робинса-Монро не выполнены, но можно установить сходимость алгоритма в более слабом смысле: для любых начальных значений T1 последовательность значений функционала F (Tn ) сходится к множеству стационарных значений F (T ).

Утверждение 4 ([24], [37]) Предположим, что выполнены условия:

1. Непрерывная функция p(·) отлична от нуля только на ограниченном множестве X Rm, и обучающая последовательность пределенных случайных величин с плотностью распределения p(·).

2. Функции потерь q k (x, T ) дифференцируемы по T, и градиент T q (x, T ) удовлетворяет условию Липшица:

3. Для некоторой постоянной c выполнено 4. Последовательность {n } удовлетворяет условиям:

Глава 1. Задача распознавания образов Тогда для последовательности Tn, доставляемой процедурой (25), с верояностью 1 существует предел:

и для некоторой последовательности ni выполнено Утверждение 4 не гарантирует существования предела последовательности Tn, сходится последовательность соответствующих значений функционала F (Tn ), причем предел F является стационарной точкой, но не обязательно минимумом функционала F (·). Если множество стационарных точек функционала F (·) состоит из единственной точки (например, функционал F (·) строго выпуклый), то из теоремы следует сходимость оценок Tn к точке минимума функционала F (·).

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

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

6.0.1 Постановка задачи Пусть заданы множество X, классифицированная обучающая последовательность {x1, x2,...} (т. е. множества X1, X2), критерий качества и допустимая на каждом шаге погрешность классификации, а также алгоритм построения K-разбиения множества X и алгоритм построения разделяющей поверхности (дискриминантной функции). Требуется классифицировать все элементы множества X, т. e. разбить его на классы X1, X2.

6.0.2 Обозначения Назовем набор = (1, 2,...), где i может принимать целые значения от 1 до K, кодом разбиения. Тогда X[] одно из подмножеств множества X, полученных в результате нескольких вложенных разбиений последнего.

Например, X[1] первое множество в K-разбиении X, а X[1,1] множество, полученное в результате K-разбиения множества X[1] и выбора первого множества из этого разбиения. Длина кода разбиения (число элементов в соответствующем наборе) показывает, сколько вложенных разбиений было произведено для получения рассматриваемого множества X[]. Условимся, что множеству X соответствует код разбиения [0]. Для удобства дальнейшего изложения введем операцию над кодами разбиений : запись = () означает, что где s - наибольший из номеров элементов кода, таких что s < K. В дальнейшем эта операция будет использована для нахождения “необработанных” подмножеств во вложенных разбиениях.

Обозначим через X1,X2 множества, образованные после построения разделяющей поверхности на множестве X[].

6.0.3 Алгоритм локального обучения 1. Положим (0) = 0.

Глава 2. Задача аппроксимации функций 2. Опишем n-й шаг обучения. Рассматриваем X[(n) ]. Определяем соответствующую ему обучающую последовательность ее роль играют те члены исходной последовательности, которые попали в рассматриваемое множество. Используя заданный алгоритм, строим разделяющую поверхность и вычисляем погрешность классификации n для множеств X1 (n)] X2 (n) ]. В случае, если n превышает заданный порог, производим K-разбиение множества X[ ] Если n <, полагаем (n+1) = ((n) ).

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

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

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

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

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

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

В общем виде задача аппроксимации состоит в следующем. Пусть на множестве аппроксимации X Rm задана вещественная функция f (·) :

Rm Rs, значения которой известны (могут быть вычислены или измерены) на множестве X0 X. В более общей постановке задачи предполагается, что вместо точных значений функции доступны зашумленные величины yi = f (xi) + vi, о помехах vi делаются те или иные предположения, например, характерны предположения о центрированности и некоррелированности помехи. Пусть на X также задана матричная функция состоящая из (s r)-матричных функций k (·) (r 1), которые известны в произвольной точке x X (будем называть эти матричные функции базисными). Задача состоит в продолжении (экстраполяции) функции f (·) с множества X0 на все X с помощью набора {k (·)}N ; точнее, требуетk= ся аппроксимировать функцию f (·) с помощью их линейной комбинации:

f (x) f (x, T ), коэффициенты T аппроксимирующей (или восстанавливающей) функции f (·, T ) выбираются в зависимости от того, в каком смысле понимается ее близость к f (·) на множестве X0. Обычно имеется в виду наилучшее приближение, что связано с заданием критерия качества аппроксимации.

7 Среднеквадратичное приближение Типичной задачей аппроксимации является задача среднеквадратичного приближения функции f (·) на множестве X0 с помощью базисных функций {k (·)}N. Для формулировки этой задачи примем, что на множестве X задана неотрицательная мера P (P(X) = 1). Обозначим через L2 (P, s) Глава 2. Задача аппроксимации функций множество квадратично интегрируемых по мере P(·) s-вектор-функций.

Множество L2 (P, s) является гильбертовым пространством по отношению к скалярному произведению звездочка означает транспонирование соответствующей матрицы (вектор рассматривается как одностолбцовая матрица). Введем функцию Коэффициент T аппроксимирующей функции f (·, T ) будем определять из условия Множество векторов T будем рассматривать как евклидово пространство RN ·r размерности N · r со скалярным произведением Соотношение тогда задает отображение : RN ·r L2 (P, s). Будем предполагать, что мера P(·) имеет вид где (·) -функция Дирака, X (x)(x)dx = (0) для любой достаточно гладкой функции (·) L2 (P, s)). В этом случае множество X0 состоит из конечного числа p точек. Пространство L2 (P, s) оказывается эквивалентным евклидову пространству Rs·p со скалярным произведением а функция F (·) (см. (28)) принимает вид Глава 2. Задача аппроксимации функций Набор коэффициентов T, при котором минимум в (29) достигается, называется оптимальным. Задача нахождения оптимального набора коэффициентов T из условия (29) всегда разрешима.

Наилучшее в среднеквадратичном смысле приближение имеет вид:

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

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

Остановимся подробнее на этих методах.

8 Алгоритм антиградиентного спуска Алгоритм антиградиентного спуска последовательно формирует оценки Tn оптимального вектора T в соответствии с рекуррентным алгоритмом где некоторый начальный векторный коэффициент. В алгоритме (32) обозначает оператор, сопряженный оператору в пространстве L2(P, s).

С учетом (30) поэтому имеем Глава 2. Задача аппроксимации функций т. е. является ((N ·r)(N ·r))-матрицей, f (N ·r)-вектором. Положительная константа (величина шага алгоритма) выбирается так, чтобы обеспечить монотонное приближение оценок Tn к оптимальному вектору T.

Это возможно, поскольку вектор (f T ) пропорционален градиенту минимизируемого функционала F (T ) (см. (28)).

Лемма 2 Для того чтобы для последовательности {Tn }, формируемой алгоритмом (32), выполнялось предельное равенство при произвольном выборе начального вектора T0 RN r (см. (33)), необходимо и достаточно, чтобы постоянная удовлетворяла условию где max наибольшее собственное значение неотрицательно определенной матрицы. Скорость сходимости характеризуется неравенством где min наименьшее отличное от нуля собственное значение матрицы и · = ( ·, · )1/2.

Доказательство Оптимальный набор коэффициентов T, как следует из (28), удовлетворяет линейному уравнению Это позволяет переписать соотношение (32) в виде где dn = T Tn и I единичная (N · r N · r)-матрица. Итерируя (35), получаем В силу (36) величина (F (Tn) inf T RN F (T )) (см. (28)) может быть представлена в виде откуда легко следуют утверждения леммы (напомним, что ненулевые собственные значения матриц и совпадают).

Глава 2. Задача аппроксимации функций В условиях леммы 2 скорость сходимости величин (F (Tn ) F (T )) к нулю мажорируется скоростью сходимости геометрической прогрессии со знаменателем прогрессии q = 1 min, |q| < 1.

Отметим, что алгоритм антиградиентного спуска можно рассматривать как упрощенный вариант рекуррентной процедуры МНК ([37], [?]).

9 Система нормальных уравнений Гаусса в стандартной задаче аппроксимации 9.0.4 Стационарные точки квадратичного функционала Алгоритм (32) может сойтись и за конечное число шагов, если начальная оценка T0 выбрана подходящим образом. Так, если в качестве начального элемента T0 выбрано какое-либо решение уравнения то при любом натуральном n в силу алгоритма (32) будет выполняться равенство Tn = T0, и алгоритм (32) “сойдется” с нулевого шага (произвольное решение уравнения (37) является стационарной точкой функции F (·)). Несложно убедиться, что в силу неотрицательности квадратичной функции F (·) всякая ее стационарная точка является точкой минимума.

С учетом формул (26), (27), (34) перепишем уравнение (37) в виде линейной системы Система (38) называется системой нормальных уравнений Гаусса, ассоциированной с задачей минимизации (28).

Глава 2. Задача аппроксимации функций Отметим, что уравнение (37) всегда разрешимо, его общее решение может быть представлено в виде где ()+ псевдообращение матрицы и T произвольный N вектор из нуль-пространства матрицы (T = 0). В частности, если матрица положительно определена, то ()+ = ()1 и уравнение (37) имеет единственное решение T = ()1f.

Замечание Напомним, что для симметричной неотрицательной матрицы A : Rn Rn псевдообращение A+ определяется следующим образом ([?]). Обозначим через Q ортопроектор на собственное подпространство матрицы A, отвечающее нулевому собственному значению, проекционная (n n)-матрица Q может быть определена по формуле где C произвольный гладкий контур в комплексной плоскости, охватывающий начало координат и не содержащий ненулевых собственных значений матрицы A (интегрирование осуществляется против часовой стрелки).

Обозначим через A сужение матрицы A на инвариантное подпространство (In Q)Rn: A = A|(In Q)Rn. Матрица A положительно определена и, следовательно, обратима. Тогда A+ = (In Q)A1(In Q).

9.0.5 Метод Карунена Лоэва решения системы нормальных уравнений Наиболее популярным методом решения системы нормальных уравнений (38) (или, что то же самое, уравнения (37)) является нерекуррентный алгоритм Гаусса, в соответствии с которым система (38) методом последовательного исключения переменных приводится к нижнетреугольному виду, а затем обратным ходом находится ее решение.

Метод исключения переменных предполагает, что матрица коэффициентов системы (38) неособая:

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

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

Следуя [37], опишем один из них, предполагая, что r = s = 1, т. е. аппроксимируемая функция f (·) скалярная и набор k (·), k = 1, 2,..., N, с помощью которого осуществляется аппроксимация, также состоит из скалярных функций. В этом случае коэффициенты kk и составляющие k правой части системы (38) являются скалярными величинами, с учетом (39) будем представлять их в виде Сделанное предположение не умаляет общности, так как при s = 1, r = 1 система (38) с помощью очевидных переобозначений может быть приведена к такому виду (однако порядок системы будет равен N · r, роль векторов k будут играть столбцы матрицы ).

Естественным способом преодоления трудностей, связанных с плохой обусловленностью либо вырождением матрицы, является переход от функций {k (·)}N к новым “линейно независимым” функциям с последуk= ющим их использованием для среднеквадратичной аппроксимации функГлава 2. Задача аппроксимации функций ции f (·). В теории обучаемых систем такой прием интерпретируется как переход к новому пространству “хороших” признаков или как предварительный отбор признаков в классификационных задачах. В математической статистике подобная конструкция лежит в основе факторного анализа (роль факторов, или существенных признаков, играют некоторые линейные комбинации функций {k (·)}N ). В теории информации аналогичk= ную роль играет разложение Карунена Лоэва, используемое как мощное средство сжатия информации ([25], [37]).

Формальная постановка задачи отбора “хороших” признаков может быть сформулирована следующим образом. С учетом обозначений (40) перепишем функционал (31) в виде Рассмотрим задачу для заданного натурального числа q, q N. Найти векторы k Rp, k = 1, 2,..., q, минимизирующие функционал и удовлетворяющие условиям где kk символ Кронекера. Итак, требуется определить q-мерное подпространство, определяемое базисом {k, k = 1, 2,..., q}, относительно которого среднеквадратичное рассеяние векторов k, k = 1, 2,..., N, минимально. Вид векторов {k, k = 1, 2,..., q} определяется следующим утверждением.

Утверждение 5 ([37]) Пусть Глава 2. Задача аппроксимации функций нормированные собственные векторы матрицы : ak = µk ak для собственных значений µk, упорядоченных по величине: µ1 µ2...

µN 0, и предположим, что µN > 0, µN +1 = µN +2 =... = µN = 0, q N N. С помощью векторов {k }, определенных формулами (40), введем векторы Тогда при p N векторы (44) ортонормированы и первые q из них доставляют минимум функционалу (42), причем где минимум вычисляется по всем наборам из q ортонормированных pвекторов.

Формула (44) показывает, что в терминах распознающих систем функции образуют новый набор признаков изображения x, которые в силу (43) “ортогональны” на обучающей последовательности x1, x2,..., xp. В терминах ют собой факторы, а формула (45) определяет рассеяние исходных данных {k } относительно найденных факторов.

Введенные векторы (44) не связаны с вектором f, ортогональная проекция PLin{k,k=1,2,...,N }f которого на линейную оболочку векторов {k, k = 1, 2,..., N } нас интересует. Нетрудно убедиться, что эта проекция может быть записана в виде Найденный набор из первых q векторов {k } позволяет найти Глава 2. Задача аппроксимации функций Если q < N, то в силу формул (44) имеем Формула (47) позволяет оценить потерю точности аппроксимации функции f (·), связанную с переходом от функций k (·), k = 1, 2,..., N, к их линейным комбинациям k, k = 1, 2,..., q, вычисляемым по формулам (46).

Очевидно, всегда |f | |f |. При q = N потери точности не происходит, так как в этом случае f = f.

9.0.6 Обобщенный метод Гаусса решения системы нормальных уравнений Переход к функциям (46) достаточно трудоемок, поскольку связан с определением собственных векторов и собственных значений матрицы.

Поэтому при больших N целесообразно использование более простых процедур отбора “хороших” признаков, хотя эти процедуры могут и не обладать оптимальными свойствами. Следуя [36], опишем одну из таких процедур, имеющую прозрачный геометрический смысл (по-прежнему предполагается, что s = r = 1). Идея состоит в отбраковке зависимых векторов из заданного набора k, k = 1, 2,..., N, так что процедура не связана с конструированием новых признаков. Описываемая ниже процедура представляет собой вариант метода Гаусса, когда при приведении системы нормальных уравнений к треугольному виду с помощью последовательного исключения искомых переменных обнуляются те переменные, исключение которых затруднительно ввиду плохой обусловленности либо вырожденности матрицы коэффициентов нормальной системы. Впервые алгоритм обобщенного метода Гаусса описан, по-видимому, в [13].

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

Фиксируем число d > 0. Если 11 > d, то первое уравнение системы (38) оставляем без изменения, а к k-му уравнению (k = 1, 2,..., N ) добавляем Глава 2. Задача аппроксимации функций первое, умноженное на k1 11. Получим систему где Если же 11 d, то индекс 1 назовем особым. В этом случае положим в системе (38) (1) = 0 и, отбросив первое уравнение, перейдем к системе В обоих случаях после первого шага имеем систему из (N 1)-го уравнения относительно векторов (k), k = 2, 3,..., N, с которой затем поступаем так же, как с исходной системой. После N шагов получим систему и особые индексы ki, i = 1, 2,..., q, причем q + q = N. Решая систему (48), последовательно определим векторы (kq ), (kq1),..., (k1 ). Полагая Описанный алгоритм решения системы нормальных уравнений Гаусса принято называть обобщенным методом Гаусса (если в процессе приведения исходной системы к треугольному виду особых индексов не возникает, то он совпадает с методом Гаусса). Строго говоря, для определенного формулами (49) вектора T выполняются лишь уравнения исходной системы, отвечающие неособым индексам. Более точно свойства полученного вектора T описаны в следующем утверждении.

Глава 2. Задача аппроксимации функций Утверждение 6 ([36]) Вектор T, определяемый с помощью соотношений (49), (48), удовлетворяет неравенствам причем для составляющих (k) вектора T справедлива оценка где постоянная C зависит от величин Достоинством приведенного алгоритма является то обстоятельство, что гарантируется малость невязки, не зависящая от числа исключенных уравнений, а само решение оказывается равномерно ограниченным по p числу точек множества X0. Если матрица не является плохо обусловленной (точнее, если выполнены неравенства kk > d, i = 1, 2,..., N ), то особых индексов не возникает и соотношение (49) определяет решение уравнения (38).

9.0.7 Геометрическая интерпретация обобщенного метода Гаусса Даны N p-векторов k, k = 1, 2,..., N, k =., и p-компоk (xp) нентный вектор f =.. Требуется найти ортогональную проекцию PLin{k, k=1,2,...,N } f вектора f на линейную оболочку Lin{k, k = 1, 2,..., N } векторов k, k = 1, 2,..., N. Именно такой смысл имеет решение системы нормальных уравнений Гаусса (38), (40). При геометрической интерпретации обобщенного метода Гаусса ([36]) важную роль играет определитель Глава 2. Задача аппроксимации функций Грама Величина (1, 2,..., s), как хорошо известно, равна квадрату объема параллелепипеда, порожденного векторами 1, 2,..., s. Несложно убеk1) диться, что коэффициент kk при (k), стоящий в k-м уравнении после (k1)-го шага преобразования системы нормальных уравнений к треугольному виду, имеет вид где s число неособых индексов, полученных к k-му шагу алгоритма.

Согласно алгоритму, задаемся числом d > 0 и начинаем проверять, велика ли норма вектора 1. Если |1 |2 = 11 d, то вектор 1 отбрасываем и переходим к рассмотрению вектора 2. Если же |1|2 > d, то вычислим отношение площади параллелограмма, образованного векторами 1, 2, к квадрату длины вектора 1, т. е. величину (1, 2)/|1|2. Если эта величина меньше или равна d, вектор 2 больше не рассматривается и операция повторяется с вектором 3. Если же величина окажется большей d, вычисляется отношение (1,,,)3 ) квадратов объемов и т. д. На каждом шаге оценивается отношение объема очередного параллелепипеда к объему предыдущего параллелепипеда, порожденного “невырожденными” векторами. При нормированных векторах отношение таких объемов характеризует угол, образуемый между очередным испытываемым вектором и линейной оболочкой уже отобранных векторов. Поэтому если этот угол мал, то испытуемый вектор отбраковывается (его индекс объявляется особым), в противном случае коллекция отобранных векторов пополняется.

Отобранные векторы “сильно независимы”. Когда отбор закончен, исходная задача заменяется следующей: отыскивается ортогональная проекция вектора f на линейную оболочку отобранных векторов, что может быть сделано, например, с помощью обычного метода Гаусса или любым другим стандартным способом решения линейной системы уравнений с невырожденной матрицей коэффициентов. Утверждение 6 гарантирует, что найденное таким способом решение является близким к точному в смысле Глава 2. Задача аппроксимации функций малости невязки. Этот результат геометрически также очевиден: невязка определяется скалярным произведением отбракованного вектора l и разностью между вектором f и его ортогональной проекцией на отобранные векторы. По способу отбраковки вектор l имеет малую проекцию на направление, ортогональное линейной оболочке уже отобранных векторов. Поэтому упомянутое скалярное произведение будет также мало. Это геометрическое рассуждение незначительно отличается от строгого доказательства малости невязки. В описанном алгоритме, кроме того, применен метод последовательного преобразования системы нормальных уравнений Гаусса к треугольному виду, позволяющий довольно просто найти нужную проекцию вектора f.

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

[37], теорема 1.4.5).

10 Последовательная аппроксимация Итак, минимизация функции (28) может быть осуществлена либо с помощью рекуррентного алгоритма (32), либо решением системы нормальных уравнений Гаусса (37). Решение уравнения (37) может быть найдено, например, с помощью алгоритма Гаусса, если матрица коэффициентов невырождена. Однако в приложениях матрица коэффициентов системы может оказаться плохо обусловленной и иметь большие размеры, т. е. возможны ситуации, когда реализация алгоритма нахождения оптимальных коэффициентов путем решения системы нормальных уравнений Гаусса (37) становится затруднительной или дает большую погрешность вычислений. Тем же недостатком обладает и рекуррентный алгоритм (32):

при больших N максимальное значение max матрицы может оказаться большой величиной, что в соответствии с леммой 2 приведет к малому шагу алгоритма (32). Рекуррентный метод наименьших квадратов также трудноприменим при оценке вектора параметров большой размерности.

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

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

Идея последовательной аппроксимации может быть пояснена на следующем простом примере. Предположим, что число базисных функций N в стандартной задаче аппроксимации, столь велико, что памяти вычислительного устройства, с помощью которого предполагается решать стандартную задачу аппроксимации, недостаточно, чтобы загрузить в нее данные задачи и алгоритм ее решения, но достаточны для решения стандартной задачи, характеризуемой числом 1 N. Другими словами, вычислительное устройство позволяет реализовывать алгоритмы проектирования вектора f на любое подпространство, размерность которого не превосходит числа 2 N (при этом для решения стандартных задач пониженных размеров могут использоваться, например, упомянутые выше рекуррентный алгоритм антиградиентного типа, алгоритм Гаусса или какие-либо другие алгоритмы), а по условию требуется найти ортогональную проекцию вектора f на заданное подпространство размерности N. В этом случае предлагается исходное N -мерное подпространство представить как прямую сумму некоторых 1 N -мерных подпространств и пытаться результаты последовательного проектирования вектора f на эти подпространства использовать так, чтобы с их помощью найти искомую проекцию вектора f на заданное N -мерное пространство. Ниже предложен и обоснован достаточно простой способ использования решений стандартных задач пониженного размера, позволяющий решить исходную стандартную задачу.

Перейдем к формальному описанию предлагаемого метода последоваГлава 2. Задача аппроксимации функций тельного проектирования ([14]).

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

Примем, что в гильбертовом пространстве H со скалярным произведением ·, · задана последовательность {Hk, k = 1, 2,...} конечномерных подпространств Hk (будем называть их базисными подпространствами).

Замкнутую линейную оболочку, порождаемую этими подпространствами, обозначим Пусть задан также элемент f H.

Требуется найти ортогональную проекцию PH0 f этого элемента на H0, предполагая, что алгоритм вычисления искомой проекции может содержать только проектирование на Hk, k = 1, 2,..., дополненное одномерными проекциями (алгоритм нахождения указанных ортогональных проекций предполагается заданным).

10.1.2 Построение последовательных проекций Обозначим через f1 = PH1 f ортогональную проекцию элемента f на базисное подпространство H1, а через H2 = Lin{H2, f1} линейную оболочку, порождаемую базисным подпространством H2 и элементом f1. Продолжая этот процесс, определим элементы fn и подпространства Hn+1 согласно алгоритму ([14]) Векторы fn, n N, назовем последовательными проекциями элемента f, порождаемыми заданной последовательностью подпространств {Hk, k = 1, 2,...} гильбертова пространства H.

Глава 2. Задача аппроксимации функций 10.1.3 Сходимость последовательных проекций Сформулируем важное свойство последовательных проекций.

Лемма 3 ([14]) Для произвольного элемента f H и последовательности подпространств {Hk H, k = 1, 2,...} для последовательных проекций {fn, n N} справедливо предельное равенство некоторый элемент из H где f замкнутой линейной оболочки, порождаемой подпространствами {Hk, k = 1, 2,...} (см. (50)).

Доказательство Поскольку fn = PHn f и (fn fn1) Hn, то есть f fn, fn fn1 = 0 (треугольник с вершинами в точках fn, fn1, f прямоугольный, причем отрезок f fn1 является гипотенузой), и в гильбертовом пространстве верна обобщенная теорема Пифагора, то построенные в соответствии с алгоритмом (51) последовательные проекции fn обладают следующим свойством:

(| · | = ( ·, · )1/2 норма в H). Поэтому при произвольных натуральных n, n(n > n ) справедливо равенство В силу определения числовая последовательность {|f fn|2, n N} монотонно невозрастающая и ограниченная, поэтому она имеет предел при n. Из (52) тогда следует, что Это означает, что последовательность {fn, n N} фундаментальная, и, следовательно, сходится к некоторому элементу из H0.

Глава 2. Задача аппроксимации функций 10.1.4 Основное утверждение Установим условия, при которых предел последовательных проекций {fn, n = 1, 2,...} совпадает с ортогональной проекцией элемента f на подпространство H0. В связи с этим введем следующее определение.

Последовательность {Hk H, k = 1, 2,...} назовем чередующейся, если каждый из ее элементов встречается в любой подпоследовательности {Hk, k = M, M + 1,...}, где M произвольное положительное число.

Теорема 3 ([14]) Если последовательность базисных подпространств {Hk H, k = 1, 2,...} чередующаяся, то для произвольного элемента f H последовательные проекции fn, n = 1, 2,..., построенные в соответствии с алгоритмом (51), сходятся к ортогональной проекции элемента f на подпространство H0 H (см. (50)):

Доказательство В соответствии с леммой 3 последовательные проекции fn, n N, имеют предельный элемент f H0. В силу того, что последовательность {Hk, k = 1, 2,..., } чередующаяся, элемент f f ортогонален каждому из подпространств Hk, k = 1, 2,.... Действительно, по построению, каждый элемент f fn ортогонален подпространству Hn, а потому и подпространству Hn Hn, т. е. e Hn выполнено Выберем подпоследовательность номеров ni такую, что Hni = Hn. Тогда f fni, e = 0. Поскольку limni fni = f, то и элемент f f ортогонален подпространству Hn n.

Ортогональность элемента f f каждому из подпространств Hk, k = 1, 2,... означает, что предел последовательных проекций f является ортогональной проекцией элемента f на H0.

Из теоремы 3 следует, что метод последовательного проектирования (51) является циклически сходящимся.

Глава 2. Задача аппроксимации функций 10.2 Последовательное проектирование в случае одномерных подпространств В качестве иллюстрации метода последовательных проекций рассмотрим частный случай, когда заданные базисные подпространства одномерные ([14], [38]). Точнее, примем, что на множестве X Rm определена вещественная скалярная функция f (·), значения которой известны на pточечном множестве X0 = {x1, x2,..., xp} X, p. Предположим, что на множестве X определены “базисные” скалярные функции k (·), k = 1, 2,..., N, т. е. функции, значения которых известны (могут быть вычислены в произвольной точке множества X). Требуется найти аппроксимант из условия Задачу нахождения минимума функции F (T ) будем решать в два этапа.

1) Определение ортогональной проекции f заданного вектора 2) Разложение вектора f по векторам 1, 2,..., N, т. е. нахождение Прохождение этапов 1), 2) обеспечивает решение исходной задачи (53) и может быть выполнено с помощью метода последовательного проектирования ([38]). Заметим, что в то время, как проекция f находится однозначно, коэффициенты разложения этой проекции по базисным векторам определяются единственным образом только при невырожденной матрице (1, 2,... N ) (1, 2,... N ). Прежде чем перейти к описанию каждого из указанных этапов, сформулируем и докажем одну простую лемму, результат которой будет использоваться в дальнейшем.

Глава 2. Задача аппроксимации функций Доказательство Пусть {e1, e2,..., el } ортонормированный базис подпространства L. Дополним его до ортонормированного базиса подпространства M: {e1, e2,..., el, el+1, el+2,..., em}. Тогда Следовательно, 10.2.1 Первый этап решения задачи (53) Опишем рекуррентный алгоритм нахождения ортогональной проекции вектора f на линейную оболочку векторов 1, 2,... N. Введем подпространства Gk = {k, R} Rp, k = 1, 2,..., N, и их замкнутую линейную оболочку подпространство G0 = Lin{Gk, k = 1, 2,... N } = Lin{k, k = 1, 2,..., N }. Продолжим последовательность подпространств Gk периодически: GN +k = Gk и т. д. Искомый вектор f есть проекция вектора f на подпространство G0. Будем искать его, используя метод последовательного проектирования. На первом шаге построим ортогональную проекцию вектора f на подпространство G1 и обозначим ее через f1. На втором построим ортогональную проекию вектора f на линейную оболочку вектора f1 и подпространства G2. Обозначим эту проекцию через f2. Далее этот процесс продолжается: на n-ом шаге строим ортогональную проекцию fn вектора f на линейную оболочку вектора fn1 и подпространства Gn.

Нетрудно получить явные формулы для вычисления этих проекций.

Лемма 5 Последовательные проекции fn определяются соотношениями Глава 2. Задача аппроксимации функций Доказательство По определению, fn Hn+1 и n+1 Hn+1. Следовательно, по лемме 4 последовательные проекции fn удовлетворяют условиям и, следовательно, Условие Dn = 0 указывает на то, что векторы fn и n+1 коллинеарны.

В этом случае очевидным образом выполнено fn+1 = fn. Если векторы fn и n+1 неколлинеарны (Dn = 0), то вектор fn+1 является линейной комбинацией векторов fn и n+1, Коэффициенты, находятся из условия C учетом (56) решение матричного уравнения (58) относительно неизвестного вектора легко выписать в явном виде (матрица в левой части уравнения неособая и имеет размерность 2 2). Формула (57) после этого приводит к (54).

В соответствии с леммой 3 последовательность {fn, n N} сходится.

Поскольку по определению последовательность {Hk, k N} чередующаяся, то по теореме 3 ее предел совпадает с искомой проекцией f вектора f.

Глава 2. Задача аппроксимации функций 10.2.2 Второй этап решения задачи (53) Для найденной на предыдущем этапе ортогональной проекции f спраN ведливо представление f = k = 1, 2,..., N. Для определения этих коэффициентов также можно воспользоваться алгоритмом последовательного проектирования. С этой цеxi) лью введем обозначения (xi) =. RN, i = 1, 2,..., p, и опреN (xi) делим подпространства Hi = {(xi), R} RN, i = 1, 2,..., p, и их замкнутую линейную оболочку подпространство H0 = Lin{Hi, i = 1, 2,..., p} = Lin{(x), x X0}. Так же, как и в предыдущем случае, предполагаем, что последовательность Hi продолжена периодически.

Как уже отмечалось, коэффициенты разложения f по векторам (xi) 1 = 1, 2,..., p в общем случае определяются неоднозначно. Обозначим один из векторов искомых коэффициентов через T. Заметим, что среди векторов, минимизирующих функционал (53) существует вектор T H0, т. к. на значения указанного функционала влияют только скалярные произведения T (xi), i = 1, 2,..., p. Вектор T является ортогональной проекцией вектора T на H0. С помощью метода последовательного проектирования c заданной последовательностью подпространств Hi, i = 1, 2,..., p, найдем вектор T : T1 ортогональная проекция вектора T на подпространство H1 ;

T2 ортогональная проекция вектора T на линейную оболочку вектора T и подпространства H2 и т. д. На n-ом шаге строим ортогональную проекцию Tn вектора T на линейную оболочку вектора Tn1 и подпространства Hn. Описанный алгоритм, на первый взгляд, представляется нереализуемым, поскольку векторы Tn определяются с использованием неизвестного решения T. Заметим однако, что хотя вектор T неизвестен, его ортогональная проекция PHi T на одномерные подпространства Hi, i = 1, 2,..., p, может быть найдена. Действительно, эта проекция определяется по формуле Здесь мы воспользовались соотношением T (x) = f (x), x X0, определяющим вектор T (вектор f можем считать известным).

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

Лемма 6 ([14]) Последовательные проекции Tn определяются соотношениями Dn = |Tn |2 |(xn+1)|2 [Tn(xn+1)]2, Tn+1 = PLin{Tn,(xn+1 )} T = Доказательство леммы 6 аналогично доказательству леммы 5.

В соответствии с леммой 3 последовательность {Tn, n N} сходится, и по теореме 3 ее предел совпадает с вектором T, минимизирующим функцию F (T ) (см. 53). Таким образом, исходная задача (53) решена.

Отметим, что алгоритмы (54), (60) являются естественными аналогами алгоритма “Оптимальное разделение” (см. п. 1.3) для нахождения точки, реализующей расстояние от начала координат до выпуклой оболочки заданного точечного множества.

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

11 Кусочно-параметрическая аппроксимация При аппроксимации функции с помощью функций из заданного набора разложение f (·) ищется в виде линейной комбинации базисных функций и критично к их выбору; эта критичность возрастает с увеличением множества X. Разбиение X на части и построение аппроксимирующей функции на каждой из них дают возможность улучшить качество аппроксимации.

Глава 2. Задача аппроксимации функций Остановимся на одном из методов, в основе которых лежит идея построения восстанавливающей функции на подмножествах из разбиения множества аппроксимации. Под кусочно-параметрической аппроксимацией функции понимается следующее: множество, на котором требуется построить приближение заданной функции, разбивается на непересекающиеся подмножества. На каждом таком подмножестве функция аппроксимируется функцией, выделенной из заданного семейства параметрисплайном ческих функций выбором параметра. Критерий аппроксимации требуется минимизировать как по этому параметру, так и по разбиению исходного множества ([2], [22]).

Уточним задачу. Пусть определена векторная, непрерывная и ограниченная на множестве определения X Rm функция f (·) : X Rs, значения которой измеряются в некоторых точках {xi X, i = 1, 2,...} с аддитивной помехой v = {vi Rs, i = 1, 2,...}, т.е. схема наблюдения имеет вид:

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

l-разбиение множества X:

и {(·, (k)), k = 1, 2, ·, l} некоторый набор сплайнов из заданного семейства. Кусочно-сплайновая функция где Глава 2. Задача аппроксимации функций индикаторные функции множеств X(k) ;

рассматривается как аппроксимация функции f (·), отвечающая выбранным наборам (T l, Xl ). Критерий качества аппроксимации функции f (·), осуществляемый с помощью наборов (Xl, T l ), принимается в виде Заметим, что для вычисления (61) важно знать лишь дискретные множества X(k) = X(k) {xi, i = 1, 2,...}, k = 1, 2,..., l.

Задача оптимальной аппроксимации может быть сформулирована в виде:

где инфимум берется по всевозможным l-разбиениям Xl множества X и векторам T l Rls.

Так же, как и в задаче автоматической классификации, разбиение Xl, отвечающее наименьшему значению критерия при фиксированном векторе T l, однозначно определяется этим вектором. Следовательно, критерий F (T, Xl ) кусочно-параметрической аппроксимации можно рассматривать как функцию F (T l ) : Rls R, т. е. задача кусочно-параметрической аппроксимации сводится к задаче конечномерной оптимизации:

где Глава 2. Задача аппроксимации функций Множества X(k) (T l ) в последнем выражении определяются соотношениями причем для определенности считаем, что граничные точки относятся к множеству с наименьшим индексом.

Задача минимизации (62) требует ряда предположений о свойствах помехи v и способа получения точек наблюдения xi. Рассмотрим стохастическую модель наблюдений и измерений. Точнее, предположим, что помеха v дискретный векторный белый шум, т. е. v является последовательностью случайных центрированных независимых одинаково распределенных s-векторов, удовлетворяющих условию где E символ математического ожидания, rv матрица корреляций помехи. Предположим также, что точки xi, в которых наблюдаются зашумленные значения функции f (·), являются независимыми реализациями случайного m-вектора, имеющего плотность распределения p (·), P (X) = 1, где P (·) распределение случайного вектора. Случайный вектор предполагается независимым с помехой v.

Рассмотрим далее частный случай поставленной задачи, когда множество сплайнов состоит из постоянных функций. В этом случае можно принять r = s и отождествить множество сплайновых функций с евклидовым пространством Rs, (·, T ) = T. Кусочно-сплайновая аппроксимация принимает вид:

а функционал (63) в силу сделанных предположений и закона больших чисел может быть переписан в виде:

где tr{rv } след корреляционной матрицы rv.

Глава 2. Задача аппроксимации функций Соотношения, которым должен удовлетворять вектор T l, минимизирующий функционал (64), имеют вид ([2]):

Разбиение Xl (T l ) определяется в рассматриваемом случае соотношениями:



Pages:     || 2 |


Похожие работы:

«Сергей Павлович Трудолюбов АНАЛИЗ И ИНТЕРПРЕТАЦИЯ ВРЕМЕННЫХ И СПЕКТРАЛЬНЫХ ХАРАКТЕРИСТИК РЕНТГЕНОВСКОГО ИЗЛУЧЕНИЯ ГАЛАКТИЧЕСКИХ КАНДИДАТОВ В ЧЕРНЫЕ ДЫРЫ 01.03.02 Астрофизика и радиоастрономия ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Научный руководитель доктор физ.-мат. наук М.Р. Гильфанов Москва Хочется сказать огромное спасибо Марату Гильфанову и Евгению Чуразову, под руководством...»

«КРЮЧКОВА НАТАЛЬЯ ДМИТРИЕВНА ОБРАЗ ЖИЗНИ БРИТАНСКОЙ ЭЛИТЫ В ТРЕТЬЕЙ ЧЕТВЕРТИ XIX ВЕКА Специальность 07.00.03. – Всеобщая история Диссертация на соискание ученой степени кандидата исторических наук Научный руководитель : доктор исторических наук профессор Аникеев А.А. Ставрополь – 2004 ОГЛАВЛЕНИЕ Введение.. Глава I. Изменение положения британской элиты в третьей четверти XIX в. §1. Распределение...»

«Стасенко Наталья Михайловна ОРГАНИЗАЦИЯ ВНЕУЧЕБНОЙ ВОСПИТАТЕЛЬНОЙ РАБОТЫ В ПЕДАГОГИЧЕСКОМ КОЛЛЕДЖЕ 13.00.01 – общая педагогика, история педагогики и образования Диссертация на соискание ученой степени кандидата педагогических наук Научный руководитель доктор педагогических наук, профессор Малашихина И.А. Ставрополь – 2004 СОДЕРЖАНИЕ стр. ВВЕДЕНИЕ.. ГЛАВА 1. Теоретические аспекты исследования организации внеучебной воспитательной...»

«Чечулин Виктор Львович МЕТОДИКА АВТОМАТИЗАЦИИ УПРАВЛЕНИЯ ДЛИТЕЛЬНОСТЬЮ ПРОЦЕССА ВАКУУМНОЙ СЕПАРАЦИИ ГУБЧАТОГО ТИТАНА И ЕЁ ОБОБЩЕНИЕ 05.13.06 – Автоматизация и управление технологическими процессами и производствами (в промышленности) Диссертация на соискание ученой степени кандидата технических наук Научный руководитель : Русаков С. В., д. ф.-м. н., профессор Пермь. | Содержание Введение Глава 1....»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Гениатулина, Ирина Анатольевна Улучшение условий и охраны труда работников животноводства и птицеводства путем разработки и внедрения озонаторных установок Москва Российская государственная библиотека diss.rsl.ru 2006 Гениатулина, Ирина Анатольевна.    Улучшение условий и охраны труда работников животноводства и птицеводства путем разработки и внедрения озонаторных установок  [Электронный ресурс] : Дис. . канд. техн. наук...»

«ЕГОРЫЧЕВА Элина Викторовна ТЕХНОЛОГИЯ ПРИМЕНЕНИЯ СРЕДСТВ ОЗДОРОВИТЕЛЬНОЙ ФИЗИЧЕСКОЙ КУЛЬТУРЫ НА ЗАНЯТИЯХ СО СТУДЕНТКАМИ СПЕЦИАЛЬНОГО УЧЕБНОГО ОТДЕЛЕНИЯ 13.00.04 – Теория и методика физического воспитания, спортивной тренировки, оздоровительной и адаптивной физической культуры ДИССЕРТАЦИЯ на соискание ученой степени кандидата педагогических наук Научный руководитель доктор биологических наук, профессор А.Д....»

«из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Устинов, Сергей Юрьевич 1. Динамика копирующей системы комБинированного сельскокозяйственного агрегата 1.1. Российская государственная Библиотека diss.rsl.ru 2005 Устинов, Сергей Юрьевич Динамика копирующей системы комБиниров анног о сельскокоз яйств енног о агрегата [Электронный ресурс]: Дис.. канд. теки, наук : 01.02.06, 05.20.01.-М РГБ, 2005 (Из фондов Российской Государственной Библиотеки) Сельское козяйство — Меканизация и электрификация...»

«Варюшина Елена Анатольевна ПРОВОСПАЛИТЕЛЬНЫЕ ЦИТОКИНЫ В РЕГУЛЯЦИИ ПРОЦЕССОВ ВОСПАЛЕНИЯ И РЕПАРАЦИИ 03.03.03 – иммунология Диссертация на соискание ученой степени доктора биологических наук Научные консультанты: доктор медицинских наук, профессор А.С. Симбирцев доктор биологических наук Г.О. Гудима...»

«Бабков Александр Сергеевич Интеллектуальная система поддержки принятия решений скрининг-диагностики рака желудка на основе комбинированных классификационных правил Специальность 05.11.17 Приборы, системы и изделия медицинского назначения. Диссертация на соискание ученой степени кандидата технических наук Научный руководитель : доктор технических наук, профессор Серебровский Вадим Владимирович Курск – 2014 СОДЕРЖАНИЕ Введение.. Глава 1...»

«ШАРЫПОВА НАТАЛЬЯ ГАВРИИЛОВНА Механизмы повреждений плазматических мембран лимфоцитов крови у больных опийной наркоманией в состоянии абстинентного синдрома 14.00.16 – патологическая физиология 14.00.45 – наркология Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : доктор медицинских наук, профессор СЕРЕБРОВ В.Ю....»

«Попова Ольга Петровна Коклюш у детей: клинико-иммунологические аспекты, диагностика и лечение 14.01.09 – инфекционные болезни Диссертация на соискание учёной степени доктора медицинских наук Научный консультант : доктор медицинских наук, профессор...»

«из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Корнилова, Ольга Алексеевна 1. Фактор значимый (внутрисемейнык) жизненный ситуаций в структуре и стратегии дезадаптивного поведения подростков 1.1. Российская государственная Библиотека diss.rsl.ru 2003 Корнилова, Ольга Алексеевна Фактор значимы к (в нутрисемейны к) жизненный ситуаций в структуре и стратегии дезадаптивного поведения подростков [Электронный ресурс]: Дис.. канд. псикол наук : 19.00.07.-М.: РГБ, 2003 (Из фондов Российской...»

«vy vy из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Богомолов, Евгений Викторович 1. Роль рекламы в формировании российского рынка 1.1. Российская государственная библиотека diss.rsl.ru 2002 Богомолов, Евгений Викторович Роль рекламы в формировании российского рынка [Электронный ресурс]: Дис.. канд. зкон. наук : 08.00.01 - М.: РГБ, 2002 (Из фондов Российской Государственной Библиотеки) Политическая экономия Полный текст: http://diss.rsl.ru/diss/02/0001/020001054.pdf Текст воспроизводится по...»

«vy \_/ из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Успенская, Юлия Михайловна 1. Деятельность школьного психолога по профилактике детской и подростковоипреступности 1.1. Российская государственная библиотека diss.rsl.ru 2003 Успенская, Юлия Михайловна Деятельность школьного психолога по профилактике детской и подростковоипреступности[Электронный ресурс]: Дис. канд. психол. наук : 19.00.03.-М.: РГБ, 2003 (Из фондов Российской Государственной библиотеки) Психология труда; инженерная...»

«Бородин Сергей Сергеевич СВОБОДНОЕ ИСПОЛЬЗОВАНИЕ ПРОИЗВЕДЕНИЙ В АСПЕКТЕ СИСТЕМНОГО ВЗАИМОДЕЙСТВИЯ ПРИНЦИПОВ АВТОРСКОГО ПРАВА 12.00.03 – гражданское право; предпринимательское право; семейное право; международное частное право ДИССЕРТАЦИЯ на соискание ученой степени кандидата юридических наук Научный руководитель – кандидат юридических...»

«Каторгин Игорь Юрьевич АНАЛИЗ И ОЦЕНКА АГРОЛАНДШАФТОВ СТАВРОПОЛЬСКОГО КРАЯ С ИСПОЛЬЗОВАНИЕМ ГЕОИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 25.00.26 – землеустройство, кадастр и мониторинг земель ДИССЕРТАЦИЯ на соискание ученой степени кандидата географических наук Научный руководитель : кандидат географических наук, профессор Шальнев Виктор Александрович Научный консультант : кандидат...»

«УДК 553.98:551.762 (571.1) 04200910149 ВИДИК СВЕТЛАНА ВЛАДИМИРОВНА НЕФТЕГЕНЕРАЦИОННЫЙ ПОТЕНЦИАЛ И ПЕРСПЕКТИВЫ НЕФТЕГАЗОНОСНОСТИ НИЖНЕ-СРЕДНЕЮРСКИХ ОТЛОЖЕНИЙ ЦЕНТРАЛЬНОЙ ЧАСТИ ЗАПАДНО-СИБИРСКОЙ ПЛИТЫ Специальность 25.00.12 - Геология, поиски и разведка горючих ископаемых...»

«Кособоков Михаил Дмитриевич ФУНКЦИОНАЛИЗИРОВАННЫЕ (ДИФТОРМЕТИЛ)ТРИМЕТИЛСИЛИЛЬНЫЕ РЕАГЕНТЫ 02.00.03 - Органическая химия ДИССЕРТАЦИЯ на соискание ученой степени кандидата химических наук Научный руководитель : д.х.н. А. Д. Дильман Москва 2014 OГЛАВЛЕНИЕ. OГЛАВЛЕНИЕ. I. ВВЕДЕНИЕ. II. ЛИТЕРАТУРНЫЙ ОБЗОР. Синтез и реакции,-дифторнитрилов.. II.1. Синтез,-дифторнитрилов....»

«ШЕЛЕПИНА НАТАЛЬЯ ВЛАДИМИРОВНА НАУЧНО-ПРАКТИЧЕСКОЕ ОБОСНОВАНИЕ ЭФФЕКТИВНЫХ СПОСОБОВ ПЕРЕРАБОТКИ ЗЕРНА СОВРЕМЕННЫХ СОРТОВ И ФОРМ ГОРОХА Специальность 05.18.01 – Технология обработки, хранения и переработки злаковых, бобовых культур, крупяных продуктов, плодоовощной продукции и виноградарства Диссертация на соискание ученой степени...»

«по специальности...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.