6.5. Сходимость в последовательном распознавании образов

6.5.0. Введение

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

6.5.1. Моделирование последовательных процедур параллельными

В ряде случаев теоремы сходимости установить можно; кроме того, встречаются случаи, в которых сходимость обычно имеет место, но ее нельзя гарантировать. Может оказаться, что процедуру, которую интуитивно можно считать последовательной процедурой классификации, легко превратить в параллельную линейную процедуру. Рассмотрим случай, когда все измерения представляют собой двоичные переменные, как в персептроне. Предположим, что корректное правило классификации гласит: „Объект относится к классу тогда и только тогда, когда — наибольший индекс, для которого признак в описании объекта имеет наибольший индекс". Это правило можно описать деревом последовательной классификации (рис. 6.5): классификация начинается с выяснения, равно ли единице измерение затем до тех пор, пока не обнаружится присутствующий признак. Алгебраически условия такого правила классификации можно записать в виде

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

в самом деле существует. Например, если взять любое вещественное число и положить

то

тогда и только тогда, когда . К сожалению, число коэффициентов так быстро растет, что реальной „машине» их было бы трудно хранить!

Рис. 6.5. Правило последовательной классификации, которое можно смоделировать процедурой параллельного распознавания образов. Приведен случай

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