Барыкин С.Г., Плотникова Н.В. Системы искусственного интеллекта

Подождите немного. Документ загружается.

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

т.е. построения многомерного отображения

yxF ⇒:

, обобщающего заданный

набор примеров

{

}

αα

yx ,

В зависимости от типа выходных переменных (тип входных не имеет ре-

шающего значения), аппроксимация функций может принимать вид

– классификации (дискретный набор выходных значений), или

– регрессии (непрерывные выходные значения)

Многие практические задачи распознавания образов, фильтрации шумов,

предсказания временных рядов и др. сводится к этим базовым прототипическим

постановкам.

Причина популярности персептронов кроется в том, что для своего круга

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

точки зрения вычислительной сложности устройствами.

Простейшим устройством распознавания образов, принадлежащим к рас-

сматриваемому классу сетей, является одиночный нейрон, превращающий вход-

ной вектор признаков в скалярный ответ, зависящий от линейной комбинации

входных переменных:













∑

wxwfy

(2.23)

Скалярный выход нейрона можно использовать в качестве так называемой

дискриминантной функции – индикатора принадлежности входного вектора к

одному из заданных классов. Так, если входные векторы могут принадлежать

одному из двух классов, нейрон способен различить тип входа, например, сле-

дующим образом: если

0)( ≥xf

, входной вектор принадлежит первому классу,

в противном случае – второму.

Поскольку дискриминантная функция зависит лишь от линейной комбина-

ции входов, нейрон является линейным дискриминатором. В некоторых про-

стейших ситуациях линейный дискриминатор – наилучший из возможных. Гра-

ницы, разделяющие области, состоят из гиперплоскостей (рис. 2.23).

Рис. 2.23 Линейный дискриминатор

В более общем случае поверхности раздела между классами можно описы-

вать приближенно набором гиперплоскостей – но для этого уже потребуется не-

сколько линейных дискриминаторов – нейронов.

Доказанная Розенблаттом теорема обучения персептрона [4] говорит, что

персептрон способен научиться всему, что он способен представлять. Понятие

представляемости относится к СП

особности персептрона (или другой сети) моделировать определенную

функцию. Обучаемость же требует наличия систематической процедуры на-

стройки весов сети для реализации этой функции. Однослойный персептрон не

может воспроизвести такую простую функцию, как исключающее ИЛИ.

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

правильно решать лишь ограниченный круг задач – когда классы, подлежащие

классификации линейно-разделимы, т.е. могут быть разделены гиперплоскостью

(рис. 2.24).

Рис. 2.24 Пример линей-

но разделимых (слева) и

линейно-неразделимых

(справа) множеств

В d-мерном пространстве гиперплоскость может разделить произвольным

образом лишь d+1 точки. Если точек больше чем d+1 всегда существуют такие

способы их разбиения по двум классам, которые нельзя осуществить с помощью

одной гиперплоскости. Однако этого можно достичь с помощью нескольких ги-

перплоскостей.

Для решения таких более сложных классификационных задач необходимо

усложнить сеть, вводя дополнительные (их называют скрытыми) слои нейронов,

производящих промежуточную предобработку входных данных таким образом,

чтобы выходной нейрон-классификатор получал на свои входы уже линейно-

разделимые множества.

Это достигается использованием иерархических архитектур. Идея такова:

на низших уровнях иерархии классы преобразуются таким образом, чтобы сфор-

мировать линейно разделимые множества, которые в свою очередь будут успеш-

но распознаваться нейронами на следующих (высших) уровнях иерархии. При-

чем, в принципе, всегда можно обойтись всего лишь одним скрытым слоем, со-

держащим достаточно большое число нейронов.

Резюмируем результаты многих исследований аппроксимирующих спо-

собностей персептронов.

– сеть с одним скрытым слоем, содержащим Н нейронов со ступенчатой

функцией активации, способна осуществить произвольную классификацию Hd

точек d-мерного пространства (т.е. классифицировать Hd примеров).

– одного скрытого слоя нейронов с сигмоидной функцией активации дос-

таточно для аппроксимации любой границы между классами со сколь угодно вы-

сокой точностью.

Нейрон с п двоичными входами может иметь 2

различных входных обра-

зов, состоящих из нулей и единиц. Так как каждый входной образ может соот-

ветствовать двум различным бинарным выходам (единица и ноль), то всего име-

ется

функций от n переменных [6].

Таблица 2.4.

Линейно разделимые функции

Число линейно разделимых функций

4 4

16 14

256 104

65536 1 882

103.4 ⋅

94 572

108.1 ⋅

15 028 134

Как видно по табл. 2.4, вероятность того, что случайно выбранная функция

окажется линейно разделимой, весьма мала даже для умеренного числа перемен-

ных. По этой причине однослойные персептроны на практике ограничены про-

стыми задачами.

Обучение сети состоит в подстройке весовых коэффициентов каждого ней-

рона. Пусть имеется набор пар векторов

(

)

pyx ..1,, =

αα

, называемый обучаю-

щей выборкой. Будем называть нейронную сеть обученной на данной обучаю-

щей выборке, если при подаче на входы сети каждого вектора

на выходах

всякий раз получается соответствующий вектор

Метод обучения персептрона состоит в итерационной подстройке матрицы

весов, последовательно уменьшающей ошибку в выходных векторах. Чтобы сеть

представляла практическую ценность, нужен систематический метод (алгоритм)

для вычисления нужных значений для весов и порогов. Алгоритм обучения пер-

септрона может быть реализован на цифровом компьютере [5].

Алгоритм обучения персептрона:

1. Всем весам сети присваиваются некоторые малые случайные значения.

2. На вход сети подается входной обучающий вектор Х и вычислить сигнал

NET от каждого нейрона, используя стандартное выражение

∑

ijij

wxwNET

(2.24)

3. Вычисляется значение пороговой функции активации для сигнала NET

от каждого нейрона следующим образом:







Θ<=

Θ≥=

JJj

NETOUT

(2.25)

Здесь

представляет собой порог, соответствующий нейрону j (в про-

стейшем случае, все нейроны имеют один и тот же порог).

4. Вычисляется ошибка для каждого нейрона посредством вычитания по-

лученного выхода из требуемого выхода:

jjj

OUTy

−

(2.26)

5. а) Если выход правильный (

), то перейти на шаг 1;

б) Если выход неправильный и равен нулю (

), то добавить все вхо-

ды к соответствующим им весам;

в) Если выход неправильный и равен единице (

), то вычесть каж-

дый вход из соответствующего ему веса.

Каждый вес модифицируется следующим образом:

jiijij

xnwnw

)()1(

(2.27)

где

– коррекция, связанная с i-м входом

(С целью обобщения вводится

коэффициент «скорости обучения»

, который умножается на

, что позволя-

ет управлять средней величиной изменения весов.);

)1( +nw

– значение веса i

после коррекции;

)(nw

– значение веса i до коррекции.

6. Повторяются шаги со второго по пятый до тех пор, пока ошибка не ста-

нет достаточно малой.

Данный метод обучения носит название «

-правила».

ГЛАВА 3. РАСПОЗНАВАНИЕ ОБРАЗОВ

3.1. ПОДХОДЫ К РАСПОЗНАВАНИЮ ОБРАЗОВ

Многие из тех полезных функций, которые легко осуществляет мозг, но

которые достаточно трудны для вычислительной машины, попадают в категорию

распознавания образов. Распознавание образов – это особый тип интеллекта;

ввод и вывод данных в таких системах осуществляется в текстовом и цифровом

виде. Когда данные поступают от человека-оператора, наиболее вероятно, что

они будут тщательно отобраны и заведомо окажутся «по существу». Вычисли-

тельная машина с «глазами» и «ушами» лишена преимущества такого предвари-

тельного отбора: она должна сама выбрать нужные данные из того громадного

потока информации, который в основном не имеет прямого отношения к делу,

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

Искусственное распознавание образов вводит вычислительную машину в

тесный контакт с реальным миром. Исследования в этой области направлены на

то, чтобы дать машине возможность непосредственно взаимодействовать с ре-

альным миром, и придают искусственному интеллекту особый характер, весьма

отличный от всего достигнутого ранее.

Распознавание образов может относиться к любой из сенсорных модаль-

ностей и не обязательно ограничиваться одной из них. Наибольшее развитие по-

лучило распознавание зрительных образов. К числу сравнительно простых отно-

сятся работы по распознаванию печатных символов, используемых для «читаю-

щих машин», которые применяются в деловых сферах, или тех знаков, которые

используются в системах чтения для слепых.

Автоматическое чтение напечатанных символов (оптическое распознава-

ние образов) находит широкое применение. Многие финансовые и другие до-

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

машины. Чтение существенно упрощается, когда буквы в соответствующих тек-

стах напечатаны одним стандартным шрифтом. Тогда распознавание сводится к

применению шаблонов.

Пример печатного материала, предназначенного для чтения машиной,

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

чатаны магнитными чернилами и читаются не оптическими средствами, а уст-

ройствами, регистрирующими магнитное поле.

Машинное чтение существенно затрудняется, если символы на документах

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

встречаются печатные цифры, вписанные человеком. Существуют читающие

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

чатными символами); однако добиться того, чтобы машина читала обычные ру-

кописные символы, весьма трудно. Очень сложной при этом оказывается про-

блема сегментации, т.е. решение вопроса о том, где кончается одна буква и на-

чинается другая.

Распознавание символов – это лишь один из видов распознавания зри-

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

годня основное внимание уделяется анализу сцен, тогда как прежде обычно

предполагалось, что изображение, подлежащее распознаванию, расположено

изолированно на каком-то фоне. При распознавании образов, как правило, удаёт-

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

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

объектами и расположенные на достаточно сложном фоне.

Другая сенсорная модальность – автоматическое распознавание речи –

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

внимание. Герои научно-фантастических фильмов чаще всего общаются с вы-

числительными машинами, используя обычную речь. При этом зрителям легче

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

числительной машиной вёлся с помощью клавиатуры. Но кроме того, в этом на-

ходит отражение тот факт, что для людей речь - наиболее естественное средство

общения.

Без сомнения, устройство распознавания речи, способное работать, не имея

никаких ограничений на входные сигналы, – дело далёкого будущего. В действи-

тельности же заставить такое устройство работать на основе лишь речевого

входного сигнала – задача вряд ли выполнимая. (У человека процесс распознава-

ния речи действует не изолированно, а опирается на механизмы, связанные с по-

ниманием смысла.)

Но в том смысле, если требуется узнать слово из небольшого словаря воз-

можных слов, автоматическое распознавание речи представляется делом вполне

реальным, если устройство распознавания может быть «натренировано», т.е. ка-

ким-то образом приспособлено к данному конкретному диктору. Даже устройст-

во, способное различать произносимые вслух десять цифр, может обеспечить по-

лезный диалог с вычислительной машиной по телефонной линии.

Подобными устройствами были снабжены коммерческие вычислительные

установки. (Генерирование речевых сигналов на выходе вычислительной ма-

шины осуществить сравнительно просто: соответствующие устройства имеются

в продаже, причём покупатель может выбрать по желанию мужской или женский

голос.)

Устройство, способное распознавать слова из небольшого словаря, может

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

приказы, когда его руки чем-то заняты. Такое устройство полезно рабочему, ко-

торый благодаря ему получает возможность отдавать довольно однообразные

команды типа «вверх», «вниз», «влево», «вправо», «стоп» цеховому подъёмному

крану. Аналогичная ситуация возникает при сортировке почтовых посылок, ко-

гда оператор помещает посылку на ленту конвейера и в то же время называет го-

род, в который она посылается. В отсутствие устройства автоматического распо-

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

был бы нажимать кнопки, передавая информацию о пункте назначения оборудо-

ванию, направляющему посылки с конвейера в соответствующие почтовые меш-

ки. При автоматическом распознавании речи можно обойтись одним оператором.

Известны [1] системы распознавания речи, способные реагировать на сло-

варь в несколько сотен слов.

3.2.

АЛГОРИТМЫ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

В СИСТЕМАХ ТЕХНИЧЕСКОГО ЗРЕНИЯ

Процесс идентификации объектов, находящихся в рабочей зоне системы,

обычно включает два этапа: выделение характерных признаков объектов; собст-

венно распознавание объектов по найденной совокупности характерных призна-

ков. В соответствии с такой структурой процесса идентификации алгоритмы об-

работки информации в системах технического зрения (СТЗ) принято делить на

алгоритмы предварительной обработки и алгоритмы распознавания, что носит в

известной степени условный характер, так как в некоторых практических прило-

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

ны на обоих этапах рассматриваемого процесса [10].

В соответствии со спектральным диапазоном преобразователей свет-сигнал

и принципом действия СТЗ датчик формирует изображение рабочей зоны. Под

изображением обычно понимается двумерная картина поля интенсивности излу-

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

лении функциональной зависимости интенсивности излучений рабочей зоны от

координат точек изображения х и у.

),( yxfJ

(3.1)

В дальнейшем под «изображением» будем понимать именно функцио-

нальную зависимость f(х, у). С учётом принятой терминологии задачей пред-

варительной обработки является поиск каких-либо особенностей функции f(x, у),

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

Алгоритмы выделения признаков изображений.

На этапе предварительной обработки стремятся создать сжатое описание

объекта в выбранной системе признаков, а затем проводится обработка получен-

ного образа.

Выбор признаков осуществляется на основе анализа класса объектов, воз-

можностей датчиков изображения по разрешению, требований к скорости обра-

ботки. Наиболее используемыми можно считать геометрические (топологиче-

ские) признаки, к которым относятся площадь и периметр изображения, число

отверстий, размеры вписанных и описанных относительно изображения фигур,

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

заключается в моментах инерции изображений заданного класса, тогда их выби-

рают в качестве признаков.

Геометрические признаки инвариантны относительно поворотов изобра-

жения в поле зрения. Инвариантность относительно масштаба изображения дос-

тигается нормированием по площади или периметру. Это важное положительное

свойство сжатого описания изображений в системе геометрических признаков.

Наиболее просто вычисляется площадь изображения. Её значение можно

получить простым подсчётом числа элементов цифрового изображения при ска-

нировании кадра. Инвариантность этого признака относительно масштаба изо-

бражения достигается нормированием по значению квадрата периметра. Пери-

метр изображения вычисляется после выделения границ. Следовательно, вычис-

лению периметра предшествует определение краёв и линий изображения, из ко-

торых затем нужно выделить граничные элементы. Наиболее просто это решает-

ся для бинарных цифровых изображений, когда граничные элементы выделяются

на перепаде освещённости объекта и фона, т.е. на переходе от силуэта (единицы)

к фону (нулю). В случае изображений с несколькими градациями яркости необ-

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

при любых значениях яркости изображения.

Для вычисления радиусов вписанных и описанных окружностей следует

предварительно определить координаты геометрического центра изображения.

Если их обозначить через (X

, Y

), через М обозначить множество координат (х, у)

элементов цифрового изображения, принадлежащих объекту (в отличие от фо-

на), то координаты центра можно выразить как

;

∑∑

⋅

ijij

∑∑

∑

⋅

ijij

;

где

– функция, принимающая значения 0 или 1













∉

∈

Mji

),(;0

),(;1

– дискретные отсчёты координат в поле цифрового изображения.

После определения Х

и Y

вычисляются минимальное и максимальное рас-

стояния (радиусы вписанной и описанной окружностей) до уже выделенных гра-

ничных элементов. Нормирование радиусов по квадратному корню из площади

или по периметру приводит к инвариантности этих признаков относительно

масштаба изображения

Проще определяется длина сторон описанного прямоугольника. При ска-

нировании изображения запоминаются максимальная и минимальная абсциссы

max

и J

min

, на которые в кадре попадает изображение объекта, и ординаты J

max

min

. Высота Y и основание X прямоугольника являются соответственно их разно-

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

по периметру.

Несколько сложнее найти моменты инерции изображения относительно

его главных осей инерции. Однако промежуточные результаты вычислений мо-

гут быть использованы для определения ориентации объекта, что будет показано

дальше.

Главные моменты инерции изображения J

и J

определяются через мо-

менты инерции J

и J

относительно осей координат OX и OY, связанных с полем

зрения, а также через смешанный момент инерции J

. Если N – общее число

элементов изображения объекта в поле зрения, f(x, у) – функция распределения

освещённости, то координаты центра тяжести изображения











⋅=

∑∑

ijc

yxfy

yxfx

),,(

);,(

где x

и y

– дискретные отсчёты координат на цифровом изображении.

Далее по известным значениям Х

и Y

вычисляются моменты инерции изо-

бражения относительно координатных осей











⋅−=

∑∑

cijy

cijx

yxfYx

yxfXx

),()(

);,()(

и смешанный момент инерции

∑

⋅−⋅−=

cijcijxy

yxfYyXxJ ),()()(

Теперь можно определить главные моменты инерции

.)(

2,1













+−⋅±

xyx

JJJ

Эти моменты принимают за отличительные признаки изображения объек-

тов. Именно пары J

, J

несут наибольшую информацию о различии объектов за-

данного класса.

В некоторых случаях целесообразно в качестве признаков использовать

взаимное положение углов в контуре изображения (рис. 3.1). Такая система при-

знаков наиболее эффективна при бинарных цифровых изображениях, поскольку

обрабатывается информация о силуэте объекта, а углы, выявленные по перепа-

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

лишь координаты вершин углов силуэта на общем фоне.

Допустим, что контурные элементы найдены и пронумерованы на преды-

дущих этапах обработки. Один из алгоритмов основан на последовательной про-

верке фрагментов контура и оценке их кривизны. Проверяемый элемент является

центральным для каждого шага проверки (рис. 3.1). Если кривизна фрагмента

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

ловым элементам контура. Однако для определения кривизны необходимо про-

граммно строить дугу, аппроксимирующую точки контура, а затем проводить

вычисление радиуса её кривизны.

{

(

k–

2),

(

–2)}

{

(

2),

(

+2)}

–2

Рис. 3.1. Последователь-

ность проверки элемен-

тов контура при выделе-

нии углов

Эти операции предполагают значительный объём вычислений и замедляют

обработку изображений. Более эффективна, но менее точна оценка, основанная

на нахождении модуля разности координат контурных элементов с номерами k–2

и k+2. Кривизна заменяется некоторой мерой отстояния конечных точек фраг-

мента друг от друга. Полученное отстояние сравнивается с заданным пороговым

значением Н, и по результатам проверки элемент с порядковым номером к может

быть отнесен к угловым. Если абсциссы и ординаты контурных элементов с их

номерами обозначить соответственно x(k), y(k), то правило выделения углов

можно определить так

{}

,)()2()2()2()2( LkMHkxkxkyky ∈⇒≤+−−++−−

где M(k) – проверяемый на данном шаге элемент контура; L – множество угло-

вых элементов анализируемого контура.

Пороговое значение Н следует выбирать при анализе дискретных изобра-

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

переменной k, причём два первых и два последних по нумерации элемента необ-

ходимо проверять вне цикла, поскольку для них невозможно задать элементы с

номерами k–2 и k+2. Если выделены несколько соседних элементов контура в

качестве угловых, то оператор селекции должен оставить только один из них уг-

лом контура.

По мере выделения угловых элементов контура и их селекции целесооб-

разно присваивать выделенным углам порядковые номера. На следующем этапе

обработки, когда формируется система признаков изображения, нумерация даёт

возможность последовательно определять эти признаки – отстояния углов друг

от друга или их отстояние от заранее вычисленного геометрического центра. В

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

признаков

),...,,(

21 n

lllA =

, где

, – вычисленные отстояния, а n – число выде-