Труктура контекстного словаря FORTH

последнее слово из словаря FORTH. Ifa этого последнего слова указывает на предпоследнее слово (шестое) из данного контекстно­го словаря FORTH и т.д. вплоть до первого слова словаря FORTH,

в Ifa которого содержится нуль, означающий конец данного списка слов. Аналогично слово-словарь EDITOR содержит указатель на последнее определенное слово в словаре текстового редактора, FORTH находится в своем собственном контекстном словаре. Оба эти слова-словаря входят в словарь FORTH по определению.В системной переменной CONTEXT содержится указатель на

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

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

тот на который указывает CURRENT. Компилятор также приме-няет системную переменную LAST, указывающую на последнее определенное слово.

Так как контекстные словари определяются посредством слова VOCABULARY, cfa каждого из них содержат указатель на процедуру периода выполнения VOCABULARY. Поскольку слово (DOES> ) оставляет на стеке pfa  контекстного словаря, программа периода выполнения помещает его в переменную CONTEXT, делая тем самым активированный словарь очередным иросматривае мым словарем. Словарь, отмеченный как CURRENT, можно отметить как CОNTEXT с помощью  слова, DEFINITIONS, Это стандартное слово Форта, и его определение выглядит следующим образом:

 

: DEFINITIONS CONTEXT @ CURRENT! ;

Таким образом, выражения FORTH DEFINITIONS EDITOR отметит FORTH как словарь, в который должен помещаться вновь
вводимые определения, а EDITOR  - как словарь, где    будет осу-ществляться поиск слов, требуемых для определения новых слов
Побочный эффект слова: заключается в том, что оно устанавлива
ет содержимое CONTEXT в CURRENT, поэтому при употребле-

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

необходимо заключать в квадратные скобки. Контекстные словари связаны воедино указателями, расположенными в теле каждого контекстного словаря по адресу pfa+2. На " поле связи" словарей последнего определенного слова указывает системная переменная VOC-LINK. В поле связи первого словаря обычно находится нуль означающий завершение списка. Таким словарем является FORTH.

 

В экспериментальном расширении Форта-83 CONTEXT прев-ращен в стек указателей на словари, которыерые просматриваются в порядке размещения в стеке их указателейй. pfa слова CONTEXT является вершиной стека словарей. Слово ALSO применяеет

239

 

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

На дне каждого стека словарей имеется словарь ONLY» приме-
няемый по умолчанию. Кроме имен других словарей, он содержит
небольшую дополнительную информацию и представляет собой
словарь специального назначения. При активации этот словарь
помещается в стек словарей, предварительно очистив последний.
Таким образом, чтобы установить следующий порядок поиска:
EDITOR, FORTH, а затем по умолчанию ONLY, необходимо
ввести:

ONLY FORTH ALSO EDITOR

Тогда ONLY очистит стек и оставит в нем только словарь ONLY.
Поскольку в ONLY хранится лишь FORTH, он будет найден и ак-
тивирован. FORTH поместит сам себя в вершину стека, заместив.
ONLY (Вспомните, что ONLY всегда есть на дне стека), после чего
ALSO сделает дубль FORTH. Наконец, EDITOR заместит верхний
экземпляр FORTH. Теперь просмотр должен осуществляться в по-
рядке расположения словарей: F.DITOR, FORTH и затем подразу-
меваемый словарь ONLY.

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

Для автоматического определения принадлежности к классу i
наследования свойств можно ввести специальные слова, устанав-
ливающие порядок просмотра. Если заданы два словаря,
МЛЕКОПИТАЮЩЕЕ и КОЗЕЛ, то связь ЭТО между ними

устанавливается, как показано на рис. 10.1, словом:

: КОЗЕЛ! ONLY МЛЕКОПИТАЮЩЕЕ ALSO КОЗЕЛ;

Слово КОЗЕЛ! задает такой порядок просмотра, при котором КО-
ЗЕЛ принадлежит к классу МЛЕКОПИТАЮЩЕЕ, так кт этот
словарь просматривается вслед за словарем КОЗЕЛ в поисках
наследуемых подразумеваемых свойств. Сами свойства могут быть
представлены в виде переменных Форта или других типов данных.
Чтобы БОРЬКА принадлежат к классу КОЗЛЫ, нужно опреде-

лить:

: 'БОРЬКА! КОЗЕЛ! БОРЬКА;

Теперь БОРЬКА наследует свойства класса КОЗЛЫ, который в
свою очередь наследует свойства класса МЛЕКОПИТАЮЩЕЕ.

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

ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ

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

1.Выполнение унификации параллельными процессорами.

2. П араллельный   просмотр   альтернативных   узлов

уровня ИЛИ.

3. Параллельный просмотр  узлов,   соединенных  по

принципу И.

Унификация представляет собой наиболее времяемкую проце-
дуру Пролога, и, применив здесь параллелизм, вы получили бы
большой выигрыш в скорости вычислений. К сожалению, это в
принципе последовательный процесс. Конечно, было бы неплохо,
если бы аргументы сравниваемых предикатов могли сопоставляться
параллельно. Как показано в гл.9, для выполнения совместимых
подстановок переменные должны сопоставляться со своими пред-
шествующими связками. Если процессор П1 осуществляет связыва-
ние переменной X с переменной Y до того, как процессор П2 смо-
жет связать X с а, то П2 должен иметь связку от Ш с тем, чтобы
он мог связать с a Y, а не X. Однако тогда весь процесс протекает
последовательно, что исключает возможность параллельных вычис-
лений.

 

240

241

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

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

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

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

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

Помимо Пролога как еще одна успешная альтернатива тради-
ционной архитектуре (Фон Неймана) выступает и потоковая  архи-

тектура, или архитектура потоков данных ( data f low a rchi -
lecture ). Сущес т венным ограничением фон-неймановской архи-
те к тур ы (ее узким местом ) представляется скоро сть обмена между

центральным процессором (ЦП) и памятью, В потоковых   ма шинах

концептуальной основой архитектуры является фун кц иональное
программирование.Многочисленные ЦП получают кванты прог-
ра мм ы ( tokens ) - единицы данных, содержащие имя операции и
аргументы. Они передаются в виде пакетов информации коммуни-
кационной сети с идентифицирующими их " конвертами". Если не-
который ЦП может выполнить операцию по обработке такого
кванта, он ее выполняет, передавая результат в том же   конверте с
тем, чтобы ЦП, выдавший квант данных, смог бы опознать ре: зуль-
тат и им воспользоваться. Потоковая архитектура - одна из парал-
лельных структур вычислений, находящихся в поле зрения иссле-
дователей и выпускаемых промышленно.

УПРАЖНЕНИЯ

1. Напишите следующие функции из реализации Пролога, описанной в гл.9:

а) ВКЛЮЧИТЬ (X)

б) ВЫЗВАТЬ (X)

2. В Прологе реализован вывод с обратным рассуждением. Объясните, каким
образом можно реализовать прямое рассуждение без внесения изменений в интер-
претатор Пролога.

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

а) вывод по умолчанию;

б) метадоказательства;

в) факторы достоверности;

г) нечеткую логику;                                             

д) множество баз знаний на различных уровнях
абстракции.

4. Выделите в приведенных ниже системах структурные и функциональные
уровни абстракции:

а)автомобиль;

б)цифровой компьютер;

в)почтовая система;

г)система армейских строевых приемов;

д) разум/рассудок.

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

242

Глава 11

ОБУЧЕНИЕ 14 РАСПОЗНАВАНИЕ ОБРАЗОВ

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

Один из видов обучения - формирование плана, например;
плана движения роботов при выполнении поставленной перед ним
задачи. Планирование связано с обучением. Планировщику, кото-

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

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

при обработке числовых данных нечисловые результаты. Эта об-область исследований получила  название распознование образов
(PО), Первоначально РО входило составной частью в ИИ, но позд-

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

ОБУЧЕНИЕ

В p a боте А. Л. Самуэля “ Исследования в области машинного

Обучения на примере игры в шашки” (1959г) описывается программа   игры в шашки, способная обучаться на основе опыта. Дере

во обхода шашечных позиций содержит огромное число вариантов,
что требует больших временных затрат на поиск, оптимального хо-
да. Для такого поиска (узла на следующем уровне просмотра) не-
обходимы эвристические правила. А.Л.Самуэль оценивает " полез-
ность" хода с помощью полинома. Члены полинома представляют
различные аспекты ситуации, скажем, позиционное преимущество
или инициативу. Обучение программы состоит в пересчете коэф-
фициентов полинома через несколько ходов после их оценки.

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

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

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

Индукция - это рассуждение от частного к общему. Концепту-
альное обучение (обучение на примерах) представляет собой фор-
му индукции. Приведем несколько областей, где применимо кон-
цептуальное обучение:

* построение конечного автомата по строкам символов;

* генерация математических функций по парам ввод-вывод;

* разработка общих процедур по особенностям поведения.

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

 

244

245

Следующий подход к обучению был исследован  Дж. K ap б o -

нелло м из университета Карне г и- М елло н а - обучение по ана-

логии. При таком подходе запоминаются решения задач (в соот-

ветствии со списками РЕШЕНИЯ программы ПОИСК, описанны-ми в гл. 9).Каждая новая задача начинает решаться обычным спо-собом. Как только ход решения в зависимости от заданой цели
становится ясным, он сравнивается с решениями, хранимыми в

памяти.

Если обнаруживаются аналогичные решения, то решатель за-дач дач ставится о них в известность. Ис следуется уже

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

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

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

Существует несколько методов применения известных реше-

ний к текущей задаче. Задачи с известным решением сравнивают-

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

Другой метод обучения состоит в задании обучающейся прог-

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

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

конечным состоянием которого является состояние цели, исполь-

зуется эвристический подход.

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

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

применении и понижения степени достоверности при неудачном.
Оценка достоверности { credit assignment ) при таком способе
производится после того, как задача будет полностью решена.

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

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

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

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

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

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

РАСПОЗНАВАНИЕ ОБРАЗОВ

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

факторов достоверности требуется вычисление значений ФД, Сами
методы вывода, как н рассмотренные выше методы обучения, стро-
ятся на чисто символьных преобразованиях. Однако программа
игры в шашки Самуэля в качестве функции оценки задействует
полином. Принятие решений в эвристической программе Самуэля
ориентировано на вычисления, В основе распознавания образов {не
смешивайте с сопоставлением по образцу при унификации или с
вызовом, управляемым образцом) лежат численные методы клас-
с и фи к ации образов. Образы представляют собой совокупность
свойств, извлекаемых из входных данных. Функционирование сис-
тем распознавания образов (РО) разбивается на два этапа:

 

246

247

1. Извлечени е свой с тв из входных (числовых)данных и полу-

чение на ИХ ОСНОВЕ ОБРАЗОВ, ВКЛЮЧАЕМЫХ  В СОВОКУПНОСТЬ ОБРАЗОВ

или совокупность свойств.

2. Классификация образов, т.е. отнесение их к одному, двум или более классам классификационной совокупности.

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

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

Рис. 11.1. Решающая функция d ( x )= O разделяет области двумерного
пространства, занимаемые векторами образов Xj и Х2

нормализации или обработки иного вида. Математически образ эк-
вивалентен вектору и выражается точкой в гиперпространстве.
При n свойствах векторы образов считаются n-мерными и занима-
ют n-пространство, или гиперпространство. В нашем примере век
торы имеют n + 1 значений, последнее из которых является допол-
нительным. В обшей форме образ X выражается так:

Х = [Х, Х₂... Xn 1]^Т

Здесь верхний индекс Т означает, что данный вектор транспониро-
ван, т.е. в действительности является вектором-столбцом, или вер-
тикальным вектором. Смысл аргумента 1 6yдет объяснен позднее.
Область образов может быть описана вектором из m векторов образов - матрицей X.

Область образов можно представить в виде гиперпространства
с рассеянными внутри него точками, отображающими образы, В
том случае, когда выбор свойств удачен, образы, принадлежащие
одному и тому же классу, группируются в так называемые клас-
теры отдельно от точек, принадлежащих другим классам. Если
нет пересекающихся кластеров, то с помощью гиперплоскостей
можно разделить гиперпространство таким образом, что области,
определяемые этими гиперплоскостями, буду; представлять раз-
личные классы. Например, в двумерном пространстве (с двумя
свойствами) гиперплоскость изображается прямой. На рис. 11.1
показана обычная кластеризация в подобном пространстве. Прямая
выделяет два кластера так, что образы выше ее могут бытъ отнесе-
ны к классу 1., а ниже - к классу 2.

Математические уравнения плоскостей разбиения на кластеры
называются решающими функци я ми ( decision / unctions ). Прямые
или гиперплоскости в общем случае выражаются линейными реша-
ющими функциями и могут правильно классифицировать только
линейно разделимые образы. Если образы, принадлежащие различ-
ным классам, пересекаются, то требуется либо улучшить отбор
свойств и повысить качество обработки, либо использовать более
сложную решающую функцию. При пересечении кластеров под-
ход, основанный на решающих функциях, не применим к детер-
министским функциям. Здесь для определения вероятности попа-
дания образа в определенный класс необходимы статистические
функция. Большинство практических задач решаются с помощью
статистических средств распознавания образов.

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

у = mх + b

Здесь m определяет угол наклона, b - пересечение с осью у.
Данное уравнение можно переписать в форме:

x₁ - mx₂ - b = О

где х₁ = у, а х ₂ = х, Преобразуем уравнение еще раз:
w₁x₁ +w₂x₂ +w₃ = 0

где w₁ = 1, w₂ = -m, a w₃ = -b. Расширив это уравнение прямой на
n- мерное пространство, получим:

w, x, + w₂x₂ +... + w_nx_n + w_n+1 = 0

Запишем полученное уравнение в более компактной векторной
форме:

W * X = О

где

d ( X ₂ ) - [1 – 0.5 - 2][3 1 1] ^T = 0.5

Для d ( X ) > 0 точка X находится над решающей функцией, а для d(X)< 0 под ней.
Следоватеяыю, в случае двух классов

 

W = [ W ₁ W ₂... W n _{+ 1} ]

X = [ X ₁ Х ₂... Х n 1] ^Т

Решающая функция d(X) является уравнением прямой в простран-
стве с образами. Рассмотрим пример с двумя образами:

X₁=[14]
X₂=[31]^T
d(X₁) = [1 -0.5-2][141] ^T =-3.

Решающая функция, которая их разделяет, имеет вид:

d(Х) = х₁ - 0.5х ₂ - 2 = 0
или в векторной форме:

d(X) = [1 - 0.5 - 2][х₁х₂1]^T

Рис. 11.2. Классификатор типа 1 отделяет заданный класс от всех

остальных

Подставив х₂ в решающую функцию, получим:
250

Рис. 11.3. Классификатор типа 2 разбивает классы на пары

класс, которому принадлежит образ, определяется знаком d(X).
Для d(X) = 0 точка лежит на прямой и может быть произвольно
отнесена к любому из классов, а возможно, и к некоторому треть-
ему классу.

В примере с двумя классами требуется только одна решающая
функция. При нескольких классах одной решающей функции не-

 достаточно. Здесь могут быть три типа классификаторов:

1. Класс 1 считается первым классом, а все остальные классы
в совокупности - классом 2. Находится решающая функция, разде-
ляющая эти два класса. При n классах требуется n решающих
функций. Для данного образа, принадлежащего классу 1, di(X) >
О, а для других значение решающей функции отрицательно. Клас-
сификатор такого типа показан на рис. 11.2.

2. Множество классов разбивается на пары. Находится решаю-
щая функция для разделения каждой пары. Решающее значение
будет положительным для образа X в dij(X), если X принадлежит
классу i (где j не равно i). Классификатор этого типа изображен на
Рис. 11.3,

3. Классификаторы первых двух типов комбинируются в це-
лях устранения неопределенных областей (которые не могут быть
отнесены ни к одному классу). Если X принадлежит классу i, то
di > dj для всех j, не равных i (рис. 11.4).

251

Рис. 11.4. Классификатор типа 3 объединяет классификаторы 1
и 2 и не оставляет неопределенных областей

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

неопределенных областей

Свойства гиперплоскости

В трех схемах кл а ссиф и каци и используются решающие функ-
ции, создание которых входит как составная часть в разработку
классификаторов. В общем случае решающие функции представля
ются n-мерными гиперплоскостями в форме W * X =0, где W-век-
тор весов { weight vector ), Его компоненты w₁, w₂, ..., w_n+1 служат
коэффициентами уравнения функци и решения. Уравнение гипер
плоскости выглядит следующим образом:

W_o * X + W_{n +1} = 0

где

W₀=[W₁ W₂... Wn]^T

Век rop W_0, как показано.на рис. 11.5 , является ортотональным,

или норма а л ьным пер р пен д ик ул я р н ы м в двумерном пространстве)
гиперклоскости. Ориентация гип ер п ло схо ст и м о-

Рис. 11.5. Прямая W * X = 0 имеет вектор ориентации W₀ с нормой
|W₀| и единичным вектором ориентации W'_o

 жет определяться единичным вектором W'_o, который имеет норму (или длину), равную единице, в направлении W_o. Единичный век-
тор определяется по формуле

w'₀--w₀/ |w_c|

а норма вектора, | WO |, - по формуле

|W₀| = (W₁² + W₂²  + … + W_n²)^1/2

Можно показать, что W'_o нормален по отношению к гаперплоскос-
ти W * X =0 на примере двух измерений (рис. 11.6). Пусть X и
Р - точки на прямой W * X = 0. Эти векторы могут быть изображе-
ны направленными отрезками (стрелками) к точкам прямой, кото-
рые также представляют и сами векторы. Разность векторов X - Р

 

252

253

также лежит на прямой, как показано на рис. 11.6. Выполнив
подстановку в уравнение прямой, получим:

W * ( X - Р) = О

 тью данной прямой. Следовательно, W₀ нормален и ко всей пря-
мой.

Обратите внимание на то, что расстояние от начала координат
до прямой (рис. 11.4) равно норме W_o * Р. Это справедливо для
любой точки X, принадлежащей прямой, так как

 

Рис. 11.6. Расстояние от начала координат до прямой равно W_o * X,
где X - любая точка, принадлежащая прямой

или

W * X = W * Р

Раскрывая W и удаляя w_n+1 из обеих частей равенства, имеем:

W_o * X = W_o * Р
или

W_o * (X - Р) = 0

Произведение векторов равно нулю, а это означает, что вектор W₀
нормален по отношению к отрезку (X - Р.), который является час-

W_o * X = W_o * Р

Направленное расстояние, D, до W * X = 0 определяется по

формуле

Знак показывает направление измерения относительно прямой.

Для любой точки Y, принадлежащей гиперплоскости, рассто-
яние от W * X = 0 до Y равно:

D_y = W'_o * Y - W'_o * X

Первый терм представляет собой направленное расстояние от
начала координат до точки Y, а второй - направленное расстояние
от начала координат до прямой. Их разность и есть направленное
расстояние от точки до прямой. Второй терм можно представить
'следующим образом:

W'_o * X = W_o * X/|W₀| = W * X/|W₀| - w_n+1/|W₀|
Так как W * X = 0, то

W'₀*X = -W_n+1/|W₀|

Наконец, направленное расстояние от точки Y до гиперплоскости с
вектором ориентации W_o равно:

D_y = (W₀* Y + W_n+1)/ |W₀|

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

* единичный вектор W_o является нормалью к гиперплоскости
W * X = 0 и определяет ее ориентацию;

* постоянный член w_n+1 в уравнении гиперплоскости пропор-
ционален расстоянию от начала системы координат до гиперплос-
кости. Если w_n+1 = 0, то гиперплоскость проходит через начало ко-
ординат.

Следовательно, рассматривая компоненты вектора W, мы
можем многое узнать о представляющей его гиперплоскости.

 

254

255

Классификаторы, построенные п о критерию
минимального расстояний

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

Z = (X₁ + Х₂ +... + X_n)/N

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

Расстояние от точки X до прототипа Z находится по формуле

D = |Х - Z|

Для двумерного пространства (берется квадрат расстояния)
оно определяется следующим образом:

D² =(X₁ – Z₁)² + ( X₂ – Z₂)² =

  = x₁² – 2x₁z₁² + x₂² -2x₂z₂ + z₂²

В общем случае для множества классов расстояние до прототипа
класса i

D_i²= |(X – Z_i)|²= (X – Z_i)*(X-Z_i)=

Х*Х - 2X*Zi + Zi* Zi

Теперь, имея формулу для D², построим с ее помощью реша-
ющую функцию классификации по критерию минимального рас-
стояния. Поскольку выражение X * X не зависит от класса, его
можно устранить. Тогда, умножая оставшуюся часть на - 1 /2, по-
лучаем следующую решающую функцию:

di(X) = X * Zi - (1/2)Zi * Zj

В формуле для определения dj мы умножаем D на -1/2, чтобы
привести выражение к виду, при котором чем больше значение di,
тем полнее аналогия (меньше расстояние).

Далее можно вычислить компоненты W. Так как

d(X) = W * X = О ТО

Wi = Zi для всех i = 1,........, n

w_n+1 = -(1/2)Zi * Zi

Геометрическая интерпретация di показана на рис. 11.7.
Первый терм di является проекцией X на Z, а второй равен по-
ловине длины Z. В том случае, когда проекция X на Z больше

Рис. 11.7. Классификация X по критерию минимального расстояния
относительно точки-прототипа Z. Здесь приводится графическая ил-
люстрация решающей функции d(X) = X * Z - (1/2)Z * Z. Если про-
екция X на Z больше половины длины Z, то d> 0

половины Z, решающая функция di положительна.

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

 

256

257

 

В качестве примера создания классификатора, действующего
по критерию минимального расстояния, рассмотрим образы, приве-
денные на рис. 11.8, где представлены три кластера, а следова-
тельно, и три класса. Для осуществления необходимых вычислений
была разработана Форт-программа, текст которой приведен на эк-
ранах с 90 по 95. Структуры данных, создаваемые словом КЛАСС,
изображены на экране 90, а словом КЛАССЫ - на экране 92.
КЛАСС создает отдельные классы кластерных точек, используе-
мых при определении решающих функций. Память под слово
КЛАСС распределяется следующим образом:

Рис. 11.8. Три класса образов (по четыре в каждом)

Пространстве