Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 39

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

Текст из файла (страница 39)

5, Линейные риэдеяяющие функции удовлетворяющий условию ая1Я)еи1 «.. О. Более того, правило постоянных приращений для коррекции 1,д в точности совпадает с таким же правилом для коррекции а,, т. е. ая„, — — ау+ т)п. я Таким образом, мы пришли к полному соответствию между случаем многих классов и случаем двух классов; при этом в процедуре для многих классов используется последовательность выборок Ч, т)е...,, е)», ...

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

К сожалению, непосредственное использование изложенной методики невозможно для обобщения метода наименьших квадратов и линейного программирования. 6.12.3. ОБОБЩЕНИЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ По-видимому, наиболее простым способом обобщения метода наименьших квадратов для случая многих классов является такой, при котором исходная задача сводится к рассмотрению множества из с задач для двух классов. Первая задача данного множества состоит в том, чтобы получить весовой вектор ае, который является решением в смысле минимума квадрата ошибки уравнений а',у=1 для всех уамбо '( а',у= — 1 для всех у(9;. )' На основе результатов п.

5.8.3 можно сказать, что при очень большом числе выборок получается наилучшее в смысле минимума среднеквадратичной ошибки приближение для байесовской разделяющей функции Р (еее ) х) — Р (не еее ( х) = 2Р (кц ! х) — 1. бдй. Обсбзалния для случая многих классов Отсюда немедленно вытекают два следствия. Первое: если несколько изменить постановку (-й задачи, то она будет звучать так: найти весовой вектор аь который является решением в смысле минимума квадрата ошибки уравнений а[у=1 для всех убйо Ит-о ы, „тзз„[ при этом а' у будет наилучшим приближением для Р (шр [х) по критерию минимума среднеквадратичной ошибки.

Второе: вполне оправданным является использование решающих разделяющих функций в линейной машине, которая относит у к классу шз при условии а,'. у) а( у для всех уФ(. Псевдообращение для решения задачи минимизации квадрата ошибки в случае многих классов можно представить в виде, аналогичном случаю двух классов. Пусть т' будетматрицей размера пхни, которая может быть разбита на блоки следующим образом: Г)г ) (95) ) У,.з причем выборки, помеченные символом шы включают в себя строки Гы Далее обозначим через А матрицу размера Йхсвесовых векторов А =[а,аз...а,1 (96) и через В матрицу размера пхс в, в, (97) сВ,~ где все элементы Вз являются нулевыми, за исключением элементов 1-го столбца, равных 1. Тогда след квадратичной матрицы ошибок ()'А — В)'(УА — В) будет минимален при решении ') А =- 1'тВ, (98) где, как обычно, )') есть псевдообращение матрицы )х.

'! Если Ьй столбец В обозначить через Ьь след матрицы (УА — В)1()'А — В) эквивалентен сумме квадратов длин векторов ошибок )газ — Ь;. Решение А= т'т В чинимизирует не только всю сумму, но и каждый член этой суммы. Гл о, Лансйнью разделяющие Функции Полученный результат может быть обобщен в форме, интересной с теоретической точки зрения. Обозначим через )см потери для случая, когда принято решение шо а истинным является решение аь и предположим, что уця подматрица В задается выражением гх» х„ )'з/ )"су и, 1=1, ...,с.

)сзу )" з/ )ссу (99) Тогда если число выборок стремится к бесконечности, то решение А=)'г В дает разделяющие функции азу, которые обеспечивают оптимальное в смысле минимума среднеквадратичной ошибки приближение байесовской разделяющей функции с дм (х) =- — ~~.", )иуР (<о ~ х). (100) 7=1 Доказательство этого результата можно получить, если распро- странить на рассматриваемый случай метод, использованный и и. 5. 8. 3. Следуя сложившейся традиции, предоставим сделать зто читателю в качестве самостоятельного упражнения.

амза. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ В силу того что линейные разделяющие функции чрезвычайно удобны для аналитического исследования, им было посвящено значительно больше работ, чем они того заслуживают. Поэтому приведенный ниже обширный список литературы на эту тему ни в коей мере нельзя считать исчерпывающим.

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

Во всех упомянутых выше работах был использован статистический подход; вместе с тем в большом количестве публикаций, ') Наша интерпретация итеративных процедур как мосолов градиентного спуска для минимизации функций критерия явилась результатом влияния идей, изложенных в докладе Блайдона ()ЗВ7). Б.18. Бибяиоврофические и исторические сведения зо! которые появились в конце 50-х — начале 60-х годов, задача распознавания образов рассматривалась с иных позиций.

Один из подходов основывался на модели работы нервной сети головного мозга, в которой каждый нейрон представлялся в виде порогового элемента, или линейной машины для двух классов. В работах этого направления, начало которому было положено знаменитой публикацией Маккаллока и Питтса (1943), всячески подчеркивалась необходимость безошибочного выполнения функции разделения; большое значение придавалось такому свойству, как приспособляемость или обучаемость. Для повышения качества работы системы в персептроне Розенблатта (Розенблатт, 1957, 1962; Блок, !962) были использованы некоторые вспомогательные правила, в соответствии с которыми изменялись весовые коэффициенты нейронов.

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

Наше доказательство основано на том, которое было дано Ридгуэем (1962), Поведение правила постоянных приращений в задачах с отсутствием разделяемости было проанализировано Эфроном (1964); более доступное изложение можно найти у Минского и Пейперта (1969), а также у Блока и Левина (1970). Простые преобразования с целью повышения качества распознавания в задачах с отсутствием разделяемости были предложены Дудой и Синглтоном (1964) и Бутцем (1967). В задачах с отсутствием разделяемости часто предполагалось использовать более сложные разделяющие функции и более сложные, иногда составленные случайным образом сети пороговых элементов. Обозначения, которые применялись при описании этих задач, могут быть использованы и при описании работы персептронов более общего класса, таких, например, как различные кусочно линейные классификаторы (Нильсон, 1965; Дуда и Фоссум, 1966; Мангасарян, 1968).

К сожалению, анализ таких сетей является чрезвычайно сложной задачей. В работе Хокинса (1961) дан хороший обзор трудов, посвященных проблеме обучения в системах, построенных на основе сетей пороговых элементов, а Минский и Селфридж (1961) проводят критический анализ этих работ. Для множества ранних работ по распознаванию образов характерен подход, основанный на теории переключений. И здесь основной упор делается на безошибочность выполнения функции разделения. Переключающей схемой, которая наиболее часто предлагалась для использования при распознавании образов, был единственный пороговый элемент; иногда его называли пороговой логической единицей, линейным входным элементом, мажоритарным клапаном или, когда он был адаптивным, адалайном (ас(а11пе).

Характеристики

Список файлов книги