8.5. Как важно быть умным

Всегда разумно стремиться к тому, чтобы стать умнее, даже если такое пожелание, выраженное в виде совета, и расстраивает собеседника. В наших экспериментах мы оказались в дураках потому, что наша программа была в некотором смысле умнее нас, когда мы определяли признаки. На самом деле для того чтобы решать многие практические задачи устройством распознавания образов, следует стремиться не к универсальным методам, а к методам, локально сильным, но и весьма специализированным, подходящим для решения имеющейся конкретной проблемы. Это утверждение прекрасно иллюстрируется процедурой Ледли (1964), в которой методы грамматической классификации образов применяются для анализа хромосом. Основные признаки были выбраны им на основе способов, которыми хромосомы разделяются; не было и попытки заставить машину породить эти признаки. Человек, решающий реальную задачу, крайне заинтересован в том, чтобы при поиске решения использовать всю информацию, которой он располагает.

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

В первом примере для классификации цифр применяется метод „пробного вектора», который нашел широкое применение при разработке оптических систем распознавания знаков. Задача состоит в распознавании заранее отцентрированной на зрительном поле цифры. Способ, которым она решается, заключается в построении множества “пробных векторов", т. е. отрезков на поле, где находится изображение (рис. 8.9, а). Каждый из векторов можно рассматривать как признак. Когда реальная фигура, например цифра „2“, будет проектироваться на это множество (рис. 8.9, б), она пересечет различные пробные векторы. В наших предыдущих обозначениях пересечение фигурой определенных пробных векторов соответствует

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

Рис. 8.9. Метод пробных векторов для распознавания знаков: а — пробные векторы; б — цифра 2, наложенная на пробные векторы.

Бонгард (1970) предлагает еще более впечатляющий способ выделения признаков в необычной задаче распознавания образов. Рассмотрим две таблицы (рис. 8.10), строки которых получены по двум математическим формулам. Таблица I образована функцией а таблица II — функцией

Рис. 8.10. Таблицы функций, предназначенные для распознаваний: (I):

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

сообщается в явной форме вид соответствующей функции. Бонгард дает описание программы, названной АРИФМЕТИКА, которая обладает требуемыми свойствами. На нас особое впечатление произвела процедура выделения признаков, поэтому обсудим ее подробнее.

Выделение признаков в программе АРИФМЕТИКА осуществляется в три этапа. На первом генерируется определенное число арифметических признаков. Каждый арифметический признак связывает два из трех табличных элементов арифметической операцией. Таким образом, на этом этапе можно было бы выработать признаки, имеющие вещественные значения, такие, как Если известно, что возможны только три операнда и ограниченное число операторов, то число возможных арифметических признаков невелико. Каждый из них можно оценить для каждой строки таблицы. Затем арифметические операции преобразуются в логические переменные при помощи одного из шести возможных правил преобразования. Все эти правила основаны на результате арифметической операции. Возможным логическим правилом преобразования является, например, правило „утверждение истинно тогда и только тогда, когда Преобразования можно применить к таким функциям, как или , когда описаны аргументы функции утверждение принимает определенное значение. В частности, в нашем примере принимает значение истина для первой строки таблицы I. Теперь мы получили признаки, которые дают возможность отобразить строку таблицы в вектор логических переменных.

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

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

Программе АРИФМЕТИКА задаются таблицы, связанные с различными (но неизвестными) функциями. Соответствующие табличные признаки порождаются до тех пор, пока программа не получит 33 функции, истинные для приблизительно половины таблиц (это число определялось характеристиками ЭВМ, на которой прогонялась программа, и не имеет особого значения). Затем

программа исследует новое множество таблиц, порожденных теми же функциями, и пытается определить, с какой из таблиц, использованных на этапе обучения, должна быть сопоставлена каждая из новых таблиц. Решение осуществляется простым алгоритмом группирования, основанном на близости образов для каждой пары таблиц. Бонгард сообщает, что программа верно классифицировала простые арифметические функции почти во всех возможных тестовых случаях, ошибаясь лишь в 3% случаев. В определенном смысле это впечатляющий результат, хотя и неясно, что же делать дальше. С одной стороны, программа в некотором смысле „индуктивно определяла функцию", поскольку она может распознать новые примеры этой функции. С другой стороны, сама функция не была определена. Программу не удалось обучить давать значение С для конкретной пары аргументов А, В, хотя ее можно было модифицировать так, чтобы она могла строить разумную гипотезу относительно того, какое из двух возможных значений С больше похоже на правильное.

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

В качестве последней иллюстрации полезного и неочевидного анализа признаков рассмотрим метод обработки двумерных изображений, при котором изображения трактуются как математические объекты. Черно-белое изображение можно определить „функцией зачерненности" значения которой представляют степень зачерненности в точке на плоскости изображения. Эту функцию можно разбить на независимые компоненты с помощью метода, называемого двумерным анализом Фурье. Мы не будем вдаваться в математические подробности (интересующийся читатель отсылается к сжатому обсуждению в книге Дуды и Харта (1973), где можно найти и дальнейшие ссылки). Мы неформально изложим здесь этот подход.

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

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

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

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

Рис. 8.11. (см. скан) Пример декомпозиции функции А. Кривая А получена как взвешенная сумма гармоник 1—4.

Чтобы применить этот метод в распознавании изображений, рассмотрим сначала простое изображение, состоящее из последовательности одинаково затененных вертикальных полос. Такое изображение можно было бы считать взвешенной суммой решеток с различными частотами смены белых и черных вертикальных полос (рис. 8.12). Аналогично изображение, состоящее из одинаковых

(кликните для просмотра скана)

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

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

Ограничение на степень разрешения вылилось бы в ограничение на частоты решеток, использованных для этого построения. Высокие частоты и, таким образом, частые тонкие линии привели бы к очень мелкой мозаике. Однако для определения большинства изображений одних блоков недостаточно, поскольку край предмета может расположиться по диагонали. Выражаясь весьма приближенно, диагонали соответствуют отношениям между частотами по направлениям х и у. Иными словами, если частоты, определяемые вертикальными и горизонтальными полосами, то пару можно представить множеством прямых с наклоном — (Заметим, что могут быть отрицательными.) Расстояние между прямыми определяется значениями Чем больше эти значения, тем ближе прямые друг к другу (рис. 8.13). Фундаментальный результат пространственного гармонического

Рис. 8.14. Изображения, полученные (а) квантованием изображения, имевшего высокое разрешение, и (б) последующей фильтрацией высоких частот, что приводит к сглаживанию краев. (Взято из статьи Хармона и Юлеша (1973).)

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

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

и Юлеш (1973) выполнили необычайно интересный эксперимент, посвященный этому вопросу. Они разбили на блоки фотографию с высоким разрешением портрета Авраама Линкольна, приписали всем точкам каждого блока значения средней зачерненности блока. Получилось изображение, показанное на рис. 8.14, а. Следствием такого квантования изображения было введение высокочастотных „шумовых" компонент, связанных с границами между блоками. Хармон и Юлеш затем получили второе изображение, отфильтровывая из блочного изображения почти все частоты, более высокие, чем те, которые могли бы поступить из оригинальной фотографии в блочную. (Размер блоков определяет верхний предел частоты, которая может быть передана из оригинала в блочное изображение.) Результат восстановления показан на рис. 8.14, б; он представляет собой легко узнаваемый портрет Авраама Линкольна.

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