Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 40
Текст из файла (страница 40)
Уиндер Гл. д, линейные разделяющие функции 202 (1968) проводит очень хороший обзор работ, относящихся к этому направлению. Стандартные процедуры, используемые для получення переключающих функций, в основном те же, что применяются для решения системы линейных неравенств. Однако некоторые нз данных процедур, являющиеся алгебраическими, неприменимы в задачах распознавания образов. Метод релаксаций для решения линейных неревенств был развит Агмоном (1954) н Моцкнном н Шенбергом (1954); использование допуска для получения решения за конечное число шагов было предложено Мейсом (!964). Тот факт, что системы линейных неравенств могут быть решены с помощью линейного программирования '), был отмечен Чарнсом н др. (1953). Мннннк показал, как можно использовать линейное программирование для определения весов порогового элемента (Мннннк, 1961), а Мангасарян (1965) предложил использовать данный элемент для классификации образов.
Все этн способы либо приводили к решению задачи в замкнутом виде, либо обеспечивали доказательство неразделяемостн, прн этом никакой полезной информация о возможном решении онн не давали. В знаменитой работе Смита (1968) показано, что задача минимизации ошибки персептрона решается методом линейного программирования. Грннолд (1969) указал, что с помощью преобразованного симплекс-метода прн ограннченнн переменных сверху все преимущества вычислительного процесса, свойственные задаче в двойственной постановке, могут быть распространены н на задачу в постановке Смита.
Нельзя сказать, что во всех работах, основанных на теории переключений, решение задачи непременно связывалось с безошибочным выполненнем функции разделения. Действительно, в одной нз первых работ, где предлагалось использовать прн классификации образов адаптивный пороговый элемент, постановка задачи была статистической (Матсон, 1959). Точно так же процедура Вндроу— Хоффа для минимизации среднеквадратичной ошнбкн была впервые описана как статистическая процедура спуска (Вндроу н Хофф, 1960), н свопм появлением она обязана задаче вннеровской $ нльтрацнн, возникающей в теории связи н теории управления.
офорд н Гронер (1966) указаЛи на связь решения, которое получается с помощью метода наименьших квадратов, с линейным дискрнмннантом Фишера; Паттерсон н Вомак (1966) показали, что это решение является, кроме того, наилучшим в смысле минимума среднеквадратичной ошибки приближением для байесовской разделяющей функция.
Тот факт, что с помощью псевдообращення обеспечивается решение задачи в замкнутой форме, был впервые отмечен Хо н Кашьяпом (1965)1 онн же показали связь между решением по з) Имеется прекрасная литература по линейному программированию, например образцовые книги Данцига (1963) и Гесса (1969). Исключительно ясное и а6статочно простое изложение можно найти у Гликсмана (1963). дпд. Библиографические и исторические сведения методу наименьших квадратов для классической теории переключений и предложенной ими итеративной процедурой (Хо и Кашьяп, 1965, 1966).
Теория псевдообращения (которую иначе называют общим обращением, обобщенным обращением или обращением Муа — Пенроуза) была окончательно оформлена в работах Рао и итра (1971). Использование стохастической аппроксимации и метода потенциальных функций для распознавания образов имеет достаточно богатую историю. Метод потенциальных функций впервые был сформулирован Башкировым, Браверманом и Мучником (1964), а дальнейшее свое развитие получил в серии статей Айзермана, Бравермана и Розоноэра. В первых статьях была показана связь между правилом коррекции для потенциальной функции и правилом постоянных приращений (Айзерман и др., 1964а); вскоре после этого была предложена модификация метода, которая позволила получить наилучшее в смысле минимума среднеквадратичной ошибки приближение для байесовской разделяющей функции (Айзерман и др., 1964б).
На связь между методом потенциальных функций и стохастической аппроксимацией было указано Цыпкиным (1965) и Айзерманом и др. (1965) и независимо от них Блайдоном (1966), Как показал Айзерман (1969), метод потенциальных функций является довольно общим методом классификации образов; целый ряд методов может быть получен как его модификации. Наибольшее внимание из них привлекла та, в которую входил в качестве составной части метод стохастической аппроксимации. Изложение метода стохастической аппроксимации в его наиболее завершенном виде можно найти у Вазана (1969); более краткое изложение (которое мы настоятельно рекомендуем читателю) — у Уайлда (1964).
Прикладные задачи теории классификации образов рассмотрены в работах Блайдона и Хо (1966), Фу (1968), Йа и Шумперта (1968); там же можно найти ссылки на другие работы, посвященные этим вопросам. При обращении к случаю многих классов достаточно серьезной становится задача выбора соответствующего метода решения, по. скольку при использовании одних методов может встретиться больше трудностей, чем при использовании других; в этом смысле различные процедуры не равноценны.
Структура линейной машины практически полностью определяется многомерным нормальным решением или даже более простыми классификаторами, использующими в качестве критерия ближайшее среднее значение или максимум корреляционной функции. Такой тип классификатора был использован в первых вариантах устройств считывания информации, записанной с помощью магнитных чернил (Элдридж, Камфефнер и Вендт, 1956). Исследование функционирования адаптивных вариантов таких устройств началось задолго до того, как были получены доказательства сходимости соответствующих процессов (напри- з"л. 5. Линеанмв разделяющие функции мер, доказательство Робертса (1960) и хорошо известная обучающая матрица Штейнбуха (Штейнбух и Писке, 1963)).
Как считает Нильсон (1966), приоритет в создании метода Кеслера и получении доказательства сходимости для правила постоянных приращений следует отдать Карлу Кеслеру, Чаплин и Левади (1967) предложили для использования в задачах многих классов модифицированный метод наименьших квадратов; идея метода состоит в отображении векторов у заданного класса в одну из вершин (с — 1)-мерного симплекса. Наша трактовка использования метода наименьших квадратов в таких задачах основана на обобщенном обращении Ви (1968).
Йа и Шумперт (!968) предложили модифицированный для случая многих классов метод стохастической аппроксимации, а Смит (1969) — процедуру, с помощью которой на этот случай может быть распространен метод линейного программирования. СПИСОК ЛИТЕРАТУРЫ Агмон (А2топ 5,) ТЬе ге!еха1 юп те!Ьоб !ог Ипезг )пециз)!Иез, Сападгап Заигпа1 о/ Ма(йвта!(сз, 6, 382 — 392 (1954).
Айзермвн (Аыегшзп М. А.) мета!)гз оп 1мо ргоЫетз соппес(еб ю(Ш рвИегп гесоипн!оп„!и Ме!Ьобо1ок(ез о1 Рзпегп кесо2пи(оп, рр. ! — 10, 5. %в(епаЬе, ес(. (Асебепнс Ргеззз Ыетч Чогк, 1969). Айзермэн М. А., Браверман Э. М., Розоноэр Л. И. Теоретические основы метода потенциальных функций в задаче об обучении автоматов рвзделенню ситуаций на классы, Автоматика и телемеханики, 25, 821 — 837 (июнь 1964з). Айзерман М. А., Браверман Э. М., Розоноэр Л, И. Вероятностная задача об обучении автоматов распознаванию классов и метод потенциальных функций, Автоматика и телвмеханика, 25, 1175 †11 (сентябрь 19646). Айзермзн М. А., Брввермвн Э. М., Розоноэр Л. И.
Процесс Роббинса — Монро и метод погенцнзльных функций, Автоматика и тгяемвланика, 25, 1882 †!885 (ноябрь 1965). Андерсон, Бахадур (Апбегзоп Т. %., Ввьзбиг н. й.) С1вззйсеноп (п1о1ъо пшц!чаыз1е ногте! б!з(г(ьи()опт чп(Ь 511(егеп! сочвпзп. се тэ!Псез, Апп. А(аои 5(аг., 33, 420 — 431 (зине 1962).
Бвшкнров О. А„Брзвермен Э. М., Мучник И. Б. Алгоритм обучения мешин распознаванию зрительных образов, основенный не использовании метода потенциальных функций, Автоматика и твлвмвка. ника, 25, 629 — 631 (май 1964). Блайдон (В!аубоп С. С.) Оп з ра11егп с)азз)цел!!оп гезиИ о1 А|зеппзп, Вгзчеппэп, Рогопоег, )ЕЕЕ Тгапк 1п!о. Тдвогу (Соггезропбепсе), !Т-12, 82 — 83 (Зепиагу 1966).
Блвйдон (В!еубоп С. С.) йесипиче з(йогцьшз !ог ранегп с!зм1псвиоп, Тесьп!св1 )серег( № 520, ()1- чн!оп о1 Епк!пеег!пк впб Аррнеб РЬунсз, Нагчзгб ()п)чегзиу, Сетьг(бее, Мамесьизецз (Мвгсь 1967). Блвйдон, Хо (В1аудоп С. С., Но Ч. С.) Оп 1Ье зЬз1гвс1!оп ргоЫегп !и рецсгп с1вмйсв((оп, Ргас. МЕС, 22, 857 — 862 (Ос1оЬег 1966), Санат литературы Блок (В!осй Н, О.) ТЬе регсер|гоп: а воде! 1ог Ьга|п (ипсйоп|пй. 1, Вес. Моб.
Рйуз., 34, 123 — 135 (бапиагу 1962). Блок, Левин (В!осй Н. О., 1.еч|п 5. А.) Оп 1Ье Ьоипбебпыз о1 ап Иегайче ргосебиге |ог ьо!ч!пй а зуз|егп о| Ипеаг !пе. йиаййеь, Ргое. Атепсаи Маумиют|са! 5осмгу, 26, 229 — 235 (Ос1оЬег 1970). Браверман Э. М. О методе потенциальных функций, Автоматика и телемеханики, 26, 2130— 2!38 (декабрь 1965). Бутц (Вн|г А. й.) Регсер|гоп |уре 1евпг|пд а1йогИЬвь |п попьерагаЫе я1на|юпь, Л Ма!й. Апа!.
ат( Арр|., 17, 560 — 576 (МагсЬ 1967). Вазан (%агап М. Т.) 5(осйазйс Арргохгвайоп (СлвЬг!Ййе ()п!четий(у Ргеы, Нем Хогй, 1969). [Русский перевод: Стокастическая аппроксимация, «Мир», М., 1972.) Вн (%ее %. О.) Оепега1 !в 6 |пчегье арргоасЬ 1о абар1|че вн|йс|аы райегп с!аььй!сайоп, 1ЕЕЕ Тгаиз. Совр., С-17, |!57 — 1164 (ОесевЬег !968). Видроу, Хофф (Хгг!бгогч В., Ной М. Е.) Адарйче ьгчйсЫпй с!гсййь, 1960 1йЕ йгЕВСОАГ Соко. )7«согг(, Раг| 4, 96 — !04 (Анбиь! |960). Гасе (Оаьь 5. 1.) (йпеаг Ргойгавв|пй (ТЫгд Ебй!оп, МсОгагч-НИ1, Ыегч Хогй, 1969). [Русский перевод: Линейное программирование, Физматгиз, М., 196!.[ Гликсман (Ойс1«япап А.
М.) !Апеаг Ргодгагппнпя апд 1Ье ТЬеогу о1 Оввс« (лойп )к'Иеу, Ые«ч Хогй, 1963). Гринолд (Ог!по!д Е. С.) Соннпеп1 оп 'Райегп с!аы|Исайоп беь!йп Ьу Ипеаг ргойгавпнпй,' /ЕЕЕ Тгапь. Сотр. (Соггеьропдепсе), С-18, 378 — 379 (Аргй !969). Данциг (Пап(г!8 О. В.) !Апеяг Ргодгавв|пй апб Ех|епз|опз (Рппсе1оп 1)п|чегьйу Ргеы, Рт|псе1оп, ЬЬ Л, |963). [Русский перевод. Линейное программирование, его обобщение и применение, М., «Прогресс», 1966.[ Дуда, Сннглтон (Онба Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
