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

В данной главе мы рассмотрели некоторые фундаментальные непараметрические методы, которые играют значительную роль в статистической классификации образов. Неупомянутыми остались многие другие вопросы непараметрической статистики, и заинтересованный в этих вопросах читатель может обратиться к работам Гиббонса (1971) или Томаса (1970) за введением в литературу по этим вопросам. Классической традицией в статистике является вывод оценок плотности распределения вероятностей из эмпирических функций распределения (Фиш, 1963), но для многомерного случая это довольно громоздкий метод. В часто упоминаемом, но довольно труднодоступном отчете Фикса и Ходжеса (1951) разработаны методы применения оценки плотности распределения в теории классификации. Эта работа явилась отправной для большинства дальнейших исследований в области оценки плотности распределения.

Наше изложение метода окна Парзена является некоторым обобщением одномерной формулировки Розенблатта (1956). В действительности работа Розенблатта предшествовала работе Парзена (1962), но Парзен еще раньше использовал аналогичные методы для оценки спектров, и термин «окно Парзена» является хорошо установившимся. Кроме того, что Парзен продемонстрировал точечную сходимость, он показал, что оценка плотности является асимптотически нормальной, и определил условия, при которых результирующая мода выборки сходится к истинной моде. Связь между

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

Строгое доказательство того, что метод ближайших соседей дает состоятельную оценку многомерной плотности, приведено Лофтегарденом и Квешенберри (1965). Удивительные результаты классификации методом ближайшего соседа получены в работе Ковера и Харта (1967), авторы которой установили также границы действия правила k ближайших соседей. Вагнер (1971) расширил эти результаты, показав, что вероятность условной ошибки при выборках сходится с вероятностью единица к среднему значению вероятности ошибки . Хелман (1970) показал, как можно дополнить правило ближайшего соседа, чтобы оно позволяло включить в рассмотрение отказы от принятия решений. Важные вопросы скорости сходимости рассматривались Ковером (1968). Поскольку уровень ошибки правила ближайшего соседа ограничивает уровень Байеса, его можно использовать для измерения трудности, присущей задаче классификации образов. Ковер (1969) высказывает предположение, что даже в случае с небольшим числом выборок результаты будут свидетельствовать о том, насколько хорошо будет работать любая непараметрическая процедура, использующая те же самые выборки. Фрелик и Скотт (1971) проводят экспериментальное сравнение использования правил окна Парзена и ближайшего соседа для оценки уровня ошибки Байеса.

У всех этих методов есть один общий недостаток — для них следует хранить полное множество выборок, поиск по которому производится каждый раз, когда нужно классифицировать новый вектор признаков. Предлагался ряд методов уменьшения числа выборок, но только для немногих из них известны какие-либо статистические свойства. Барус (1966) предложил интересную аппроксимацию для процедуры Фикса и Ходжеса, а Харт (1968) — сжатое правило ближайшего соседа. Задача нахождения эффективного небольшого опорного множества будет являться, по существу, задачей разбиения совокупности на группы. Более того, определенные процедуры разбиения совокупности на группы, такие, как предложенные Себестьяном (1962) и Себестьяном и Эди (1966), можно считать эвристическими методами аппроксимации плотностей

распределения вероятностей. Тартер, Холкомб и Кронмел (1967) предложили использовать для оценки плотности распределения вероятностей разложение в ортогональные ряды. Идея получения полиномиальных разделяющих функций путем аппроксимации оценки окна Парзена g помощью рядов Тейлора была высказана Спештом (1967). Мейзел (1969) указал, что для сходимости таких разложений может потребоваться много членов, и связал метод окна Парзена с методом потенциальных функций Аркадьева и Бравермана (1966). Метод потенциальных функций соотнесен с адаптивными методами и методами стохастической аппроксимации, рассмотренными в гл. 5. Большинство из этих методов связано с получением апостериорных вероятностей. Однако Цыпкин (1966) и Кашьяп и Блайдон (1968) показали, что теоретически их также можно использовать для оценки плотностей распределения.

Необходимость в преимущественно бинарных измерениях во многих практических системах распознавания образов вынесла вопросы оценки совместной вероятности бинарных переменных за рамки чисто академического интереса. Разложение Радемахера — Уолша часто встречается в теории переключений, и оно тесно связано с разложением Бахадура — Лазарсфельда. Бахадур (1961) дает расширение этого последнего разложения, перенося его с бинарного случая на общий дискретный случай. Если же разложения по ортогональным функциям минимизируют среднеквадратичную ошибку, Браун (1959) и Льюис (1959) показывают, что при определенных условиях аппроксимация произведений максимизирует энтропию. Иго (1969) приводит границы уровня ошибки, возникающей в результате усечения разложений в ряд. Идея об упрощении аппроксимаций за счет ограничения характера зависимости изучалась Чоу (1962) и Абендом, Харли и Кеналом (1965), которые, в частности, интересовались естественными пространственными зависимостями в бинарных картинах. Чоу (1966) была высказана интересная идея о древовидной зависимости, а методы нахождения дерева зависимости сообщаются Чоу и Лю (1966, 1968). Значительное расширение этой концепции на многомерный нормальный случай приводится Чоу (1970).

Дискриминантный анализ берет начало в классической работе Фишера (1936). Литература по этому предмету довольно обширная, и хороший обзор по ней сделан Тацуокой и Тайдменом (1954). Обобщение метода линейного дискриминанта Фишера на случай со многими классами сделано Брайаном (1951). Можно получить линейные разделяющие функции других типов, используя не отношение разброса между классами к разбросу внутри класса, а другие критерии. Кульбаком (1959) предлагаются другие критерии и исследуются их характеристики. Петерсон и Матсон (1966) разработали общую процедуру нахождения оптимальной разделяющей функции для довольно широкого класса функций критерия. Как мы уже

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