Глава пятая. Сокращение размерности исходного описания

§ 5.1. Введение

В главе IV рассматривались вопросы создания пространства признаков, размерность которого намного меньше размерности исходного описания.

При этом предполагалось, что в формировании пространства признаков участвуют все параметры исходного описания.

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

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

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

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

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

Такая задача является слишком сложной, и оптимизацию приходится производить поэтапно.

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

1) максимально упростить пространство признаков и решающее правило, после чего, по возможности, уменьшить размерность исходного описания;

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

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

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

Эти две задачи приводят к двум различным подходам для их решения.

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

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

При этом решающее правило может значительно усложниться.

В таких задачах пространство признаков, как правило, не формируется, и решение принимается непосредственно в пространстве оставшихся исходных параметров.

Примером первого подхода являются работы 15.2, 5.31, а примером второго [5.4-5.8].

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

Большинство предложенных к настоящему времени методов сокращения размерности исходного описания, в том числе и изложенные в § 5.2 и 5.3, отличаются друг от друга формулировкой критериев оптимальности, которые в различной степени разрешают противоречия между близостью формальных критериев к описанным выше содержательным задачам и сложностью вычислительных процедур Что касается методов решения этих задач, то их целочисленный характер требует перебора подмножеств параметров исходного описания. При большом числе исходных параметров этот путь трудно реализуем, так как наталкивается на "проклятие размерности". Поэтому применяют методы направленного [5.9, 5.101 или сокращенного перебора [5.10-5.12].

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

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