5.13. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ

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

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

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

В задачах с отсутствием разделяемое™ часто предполагалось использовать более сложные разделяющие функций и более сложные, иногда составленные случайным образом сети пороговых элементов. Обозначения, которые применялись при описании этих задач, могут быть использованы и при описании работы персептро- нов более общего класса, таких, например, как различные кусочно линейные классификаторы (Нильсон, 1965; Дуда и Фоссум, 1966; Мангасарян, 1968). К сожалению, анализ таких сетей является чрезвычайно сложной задачей. В работе Хокинса (1961) дан хороший обзор трудов, посвященных проблеме обучения в системах, построенных на основе сетей пороговых элементов, а Минский и Селфридж (1961) проводят критический анализ этих работ.

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

(1963)    проводит очень хороший обзор работ, относящихся к этому направлению. Стандартные процедуры, используемые для получения переключающих функций, в основном те же, что применяются для решения системы линейных неравенств. Однако некоторые из данных процедур, являющиеся алгебраическими, неприменимы в задачах распознавания образов. Метод релаксаций для решения линейных неревенств был развит Агмоном (1954) и Моцкином и Шёнбергом (1954); использование допуска для получения решения за конечное число шагов было предложено Мейсом (1964).

Тот факт, что системы линейных неравенств могут быть решены с помощью линейного программирования х), был отмечен Чарн- сом и др. (1953). Минник показал, как можно использовать линейное программирование для определения весов порогового элемента (Минник, 1961), а Мангасарян (1965) предложил использовать данный элемент для классификации образов. Все эти способы либо приводили к решению задачи в замкнутом виде, либо обеспечивали доказательство неразделяемое™, при этом никакой полезной информации о возможном решении они не давали. В знаменитой работе Смита (1968) показано, что задача минимизации ошибки персептро- на решается методом линейного программирования. Гринолд (1969) указал, что с помощью преобразованного симплекс-метода при ограничении переменных сверху все преимущества вычислительного процесса, свойственные задаче в двойственной постановке, могут быть распространены и на задачу в постановке Смита.

Нельзя сказать, что во всех работах, основанных на теории переключений, решение задачи непременно связывалось с безошибочным выполнением функции разделения. Действительно, в одной из первых работ, где предлагалось использовать при классификации образов адаптивный пороговый элемент, постановка задачи была статистической (Матсон, 1959). Точно так же процедура Видроу — Хоффа для минимизации среднеквадратичной ошибки была впервые описана как статистическая процедура спуска (Видроу и Хофф, 1960), и своим появлением она обязана задаче винеровской фильтрации, возникающей в теории связи и теории управления. Кофорд и Гронер (1966) указали на связь решения, которое полу- чае*гся с помощью метода наименьших квадратов, с линейным дискриминантом Фишера; Паттерсон и Вомак (1966) показали, что это решение является, кроме того, наилучшим в смысле минимума среднеквадратичной ошибки приближением для байесовской разделяющей функции. Тот факт, что с помощью псевдообраідения обеспечивается решение задачи в замкнутой форме, был впервые отмечен Хо и Кашьяпом (І965)-; они же показали связь между решением по

методу наименьших квадратов для классической теории переключений и предложенной ими итеративной процедурой (Хо и Кашьяп, 1965, 1966). Теория псевдообращения- (которую иначе называют общим обращением, обобщенным обращением или обращением Мура — Пенроуза) была окончательно оформлена в работах Рао и Митра (1971).

Использование стохастической аппроксимации и метода потенциальных функций для распознавания образов имеет достаточно богатую историю. Метод потенциальных функций впервые был сформулирован Башкировым, Браверманом и Мучником (1964), а дальнейшее свое развитие получил в серии статей Айзермана, Бравер- мана и Розоноэра. В первых статьях была показана связь между правилом коррекции для потенциальной функции и правилом постоянных приращений (Айзерман и др., 1964а); вскоре после этого была предложена модификация метода, которая позволила получить наилучшее в смысле минимума среднеквадратичной ошибки приближение для байесовской разделяющей функции (Айзерман и др., 19646). На связь между методом потенциальных функций и стохастической аппроксимацией было указано Цыпкиным (1965) и Айзерманом и др. (1965) и независимо от них Блайдоном (1966). Как показал Айзерман (1969), метод потенциальных функций является довольно общим методом классификации образов; целый ряд методов может быть получен как его модификации. Наибольшее внимание из них привлекла та, в которую входил в качестве составной части метод стохастической аппроксимации. Изложение метода стохастической аппроксимации в его наиболее завершенном виде можно найти у Вазана (1969); более краткое изложение (которое мы настоятельно рекомендуем читателю)— у Уайлда (1964). Прикладные задачи теории классификации образов рассмотрены в работах Блайдона и Хо (1966), Фу (1968), Йа и Шумперта (1968); там же можно найти ссылки на другие работы, посвященные этим вопросам.

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

мер, доказательство Робертса (I960) и хорошо известная обучающая матрица Штейнбуха (Штейнбух и Писке, 1963)). Как считает Нильсон (1965), приоритет в создании метода Кеслера и получении доказательства сходимости для правила постоянных приращений следует отдать Карлу Кеслеру. Чаплин и Левади (1967) предложили для использования в задачах многих классов модифицированный метод наименьших квадратов; идея метода состоит в отображении векторов у заданного класса в одну из вершин (с — 1)-мерного симплекса. Наша трактовка использования метода наименьших квадратов в таких задачах основана на обобщенном обращении Ви

(1968). Йа и Шумперт (1968) предложили модифицированный для случая многих классов метод стохастической аппроксимации, а Смит (1969) — процедуру, с помощью которой на этот случай может быть распространен метод линейного программирования.