Глава четвертая. Создание системы признаков

§ 4.1. Введение

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

При создании признаков обычно преследуются две цели: сокращение числа параметров для описания реализаций образов^* упрощение решающего правила.

^* (В этой главе описываются методы сокращения числа параметров (координат) в преобразованном пространстве признаков. Методы сокращения числа параметров исходного описания изложены в главе V. )

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

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

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

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

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

Оптимальной в рамках предлагаемого подхода явилась бы система из минимального числа признаков, сохраняющих ε-непересекаемость образов.

Система признаков, оптимизированная по этому критерию, описывает образы минимальным числом параметров, почти не ухудшая (а в некоторых случаях даже улучшая) их разделимость. Однако реализация алгоритма по этому критерию наталкивается на весьма большие вычислительные трудности.

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

Излагаемый в § 4.2 аппроксимационный критерий реализуется наиболее простыми алгоритмами. Вместе с тем этот критерий далек от желаемого и приводит к худшим результатам по сравнению с другими критериями (см. главу VIII). т

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

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

Если при построении решающего правила используется метрика l₂, то, как показано ниже, оптимизация признаков по взвешенному дискриминантному критерию (§ 4.4- 4.6) позволяет найти в исходном описании такое маломерное подпространство, в котором почти полностью сохранены свойства разделимости между учебными выборками наиболее близких пар образов. Относительное же сближение далеких пар образов не критично, так как это практически не влечет за собой увеличения числа эталонов.

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

Методам создания признаков, адекватных решающему правилу в метрике с, посвящены § 4.7, 4.8.

Приводимые в § 4.2-4.8 критерии оптимизации системы признаков обеспечивают метрическую разделимость учебной выборки с некоторым порогом d, который может иметь статистический и детерминистский смысл. Вопрос о соотношении оптимального в рамках данного подхода критерия качества системы признаков, требующего метрическую разделимость для генеральных совокупностей, и критериев, обеспечивающих разделимость учебной выборки, обсуждается в § 4.9.

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

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