Л.А.РАСТРИГИН
Р. Х.ЭРЕНШТЕЙН
МЕТОД КОЛЛЕКТИВНОГО РАСПОЗНАВАНИЯ
БИБЛИОТЕКА
ПО АВТОМАТИКЕ
Выпуск 615
Л. А. РАСТРИГИН, Р. X. ЭРЕНШТЕЙН
МЕТОД
КОЛЛЕКТИВНОГО
РАСПОЗНАВАНИЯ
МОСКВА ЭНЕРГОИЗДАТ 1981
ББК 32.81
Р24
УДК 681.015.24
Рецензент Вапник Владимир Наумович
РЕДАКЦИОННАЯ КОЛЛЕГИЯ:
И В. Антик, Г. Т Артамонов, А. А. Воронов, Л. М. Закс, В. К Левин, В. С. Малов, -В Э Низе, Д А. Поспелов, И. В. Прангишвили, Ф. Е. Темников, Г. М Уланов, Ю М. Черкасов, А С Шаталов *
Растригин Л. А., Эренштейн Р. X.
распознавания. — М.: Энер-ил. — (Б-ка по автоматике;
Рассмотрены вопросы построения иерархических распознающих систем Предложен качественно новый подход, позволяющий получить целый класс алгоритмов, моделирующий процесс принятия решения коллективом Рассмотрены процессы обучения такого коллектива и синтез оптимального коллектива линейных алгоритмов распознавания Решен ряд модельных задач. Предлагаемый подход реализован для синтеза решения коллектива экспертов
Для специалистов по теории автоматического,, управления, занятых проблемами распознавания образов, а также студентов и аспирантов соответствующих специальностей
30501-469
Р 051(0~1)-81 184’81 (Э)*	2404000000
HI 1|||<М*
L БИБЛИОТЕКА ‘
Уральского По »и- , хнТическогО институте им. С. М. Кирова _
-Л»	*-*	4
ББК 32.81
БФ6.5
© Энергоизд ат, 1981
ПРЕДИСЛОВИЕ
Коварство (и очарование) проблемы распознавания образов заключается в ее простоте. При первом знакомстве с ней исследователь прежде всего с легкостью привлекает для решения своей задачи знакомый ему аппарат и ... иногда получает удовлетворительный результат, но чаще его преследуют неприятности. И лишь хорошо разобравшись в своей конкретной задаче, ему удается решить ее. Задача распознавания, как правило, требует неформального подхода для своего решения.
Какие только методы не использовали для решения задач распознавания! Тут и вероятностные методы регрессионного и корреляционного анализов, разнообразные аппроксимационные подходы, связанные с построением гиперповерхности, разделяющей образы, многочисленные теоретико-множественные приемы, использующие аппарат алгебры логики, топологические подходы и т. д. Нет необходимости в продолжении этого списка многочисленных методов решения задачи распознавания, тем более что авторы этой книги пошли другим путем. Они не изобретали нового метода, а предложили способ использования уже известных. При этом широко привлекалась аналогия с методами коллективного решения, столь эффективно используемыми в обществе В результате вопреки желанию авторов получился новый метод классификации, который переносит задачу принятия решения на уровень выше, т. е. указывается способ, которым будет приниматься 'решение о принадлежности данной ситуации к классу. Сами же способы задаются априорно и образуют коллектив, эффективность которого практически всегда оказывается значительно выше любого из его членов.
Изложенная в этой книге идея коллектива может быть использована и в других задачах, но проблема распознавания, для которого она была высказана первоначально, является наиболее рельефным объектом ее приложения.
Авторы с благодарностью примут все замечания и пожелания, высказанные в адрес книги.
Авторы благодарны проф. Н. А. Андрееву и А. Ф. Абу, которые участвовали в обсуждении материала, изложенного в гл 4 и 3 соответственно.
Авторы приносят искреннюю признательность Н. Г Загоруйко, В. И. Васильеву, Я. А. Гельфандбейну, Ш. Ю. Раудису, В Е. Го-ленд^ру, Б. Я. Кавалерчуку, внимательно прочитавшим рукопись и сделавшим ряд полезных замечаний, которые учтены в окончательном варианте, и рецензенту В. Н. Вапнику, чьи советы авторы постарались учесть. Авторы глубоко признательны Э. М. Браверма-ну, ныне покойному, который предложил им написать эту книгу..
Авторы
3
ВВЕДЕНИЕ
В.1.	ИДЕЯ РАСПОЗНАВАНИЯ ОБРАЗОВ (КРАТКИЙ ОБЗОР)
Любая из известных в настоящее время книг по теории или практике распознавания образов так или иначе начинается с обзора задач, методов и возможных приложений этой теории Это объясняется, во-первых, *>ем, что идеология распознавания достаточно проста, чтобы ее можно было изложить в пределах одного печатного листа доступно и просто для специалистов самых различных профилей Во-вторых, это оправдано тем, что специалисты проявляют все больший интерес к проблеме распознавания, в результате чего область приложений этой теории постоянно расширяется. Авторы не хотели бы отклоняться от традиций и также начинают эту книгу с краткого обзора идей распознавания образов. При этом, однако, * будут вскрыты причины, которые заставили изыскать свой подход к задаче распознавания, существенно отличающийся от известных ранее Его основное отличие заключается в том, что это не новый метод, а'новый способ манипулирования старыми методами. Оказалось, чта можно существенно повысить эффективность известных процедур распознавания, если их организовать в своеобразный коллектив. Организатор этого коллектива и образует верхний уровень иерархической структуры, которая в результате дает качественно новый эффект. Чтобы доказать необходимость такой структуры, рассмотрим существующие методы распознавания и отметим их сильные и слабые стороны с тем, чтобы в коллективе воспользоваться их преимуществами.
Теория распознавания образов представляет собой сравнительно молодую, но уже хорошо разработанную теорию, точнее, несколько теорий. Об этом ярко свидетельствует прежде всего обилие монографий и статей по распознаванию. Многие из них упомянуты в библиографии, приведенной в конце данной книги [3, 4, 6, 9—15, 26, 28, 31—38, 40, 41, 46—49, 51—53, 55—57, 69—71, 74, 76, 77, 81—88, 91, 93—96]. Удачное применение этих теорий позволяет эффективно решать вопросы медицинской диагностики различных заболеваний [13) 28, 38], задачи распознавания неисправностей машин и механизмов, распознавания залежей полезных ископаемых [9], интерпретации сигналов при радио- и гидролокации [52], прогнозирования аварийных ситуаций в различных системах, в том числе и электроэнергетических [1], распознавания зрительных и слуховых образов [9, 10, 33, 35, 40,*41, 51] и т д
Однако вместе с успехами и достижениями теории распознавания в настоящее время наметился некоторый кризис. Его основная причина — отсутствие идей, существенно улучшающих качество распознавания. Здесь уместно привести высказывание Л Канала, который в своем обзоре [95] высказывает неудовлетворенность состоянием этой проблемы: «Сейчас стало ясно» что ни обучающиеся 4
машины, ни статистйческий подход, ни пространственная фильтрация, эвристическое программирование, методы формальной логики — словом, ни один из методов, предлагавшихся на протяжении последних 5—10 лет в качестве методов решения проблемы распознавания образов, не может, взятый в отдельности, дать решение этой проблеме. Нет модели, адекватной всем задачам распознавания образов, и нет метода, пригодного для решения всех задач. В действительности — распознавание образов — это совокупность методов- и совокупность задач». Авторам хотелось бы в этой книге несколько развеять пессимизм Л. Канала и оправдать приведенное высказывание в последней его части.
Большинству работ по вопросам распознавания свойственно повышенное внимание к достоинствам и преимуществам тех или иных алгоритмов. При этом обычно не- подчеркивается тот факт, что любой вновь разработанный или широко известный алгоритм всегда обладает рядом недостатков, существенно сужающих область «применимости этих алгоритмов, причем недостатки связаны только со спецификой решаемой задачи., Нет плохих алгоритмов, есть алгоритмы, применяемые не там, где следует.
Поэтому прежде всего следует остановиться на условиях, определяющих эффективность применения того или иного метода или алгоритма. Другими словами, нужно рассмотреть область применимости различных алгоритмов распознавания. Однако прежде чем перейти непосредственно к этому вопросу, рассмотрим некоторые основные понятия теории распознавания.-
Исходным является понятие образа или класса. Оно обобщает некоторое множество ситуаций или явлений, т. е. отождествляет их, пренебрегай их различием. Описываются ситуации с помощью совокупности признаков, составляющих пространство признаков. Под признаком, в свою очередь, подразумевается количественное или- качественное описание того или иного свойства исследуемого явления. Ситуацию удобно обозначать вектором X={xi, хг, ..., хп} в пространстве Q. Образ или класс представляет собой множество таких векторов (конечное или бесконечное), который будем обозначать буквой А3, / = 1, 2, ..., /, где J — число образов (классов)/
Известны различные способы систематизации и классификации, задач и методов теории распознавания образов [35, 52, 56, 57, 77]. Наиболее удачная классификация, на наш взгляд, приводится в [35]. Пусть А = {А3}, j—1, 2, ..., / — множество классов, /?— метод распознавания (решающее правило), а С — затраты, связанные с реализацией некоторого метода распознавания R. Под затратами здесь понимаются не только затраты на собственно реализацию того или иного решающего правила (машинное время, сложность программирования, объем необходимой, памяти и т. д.), но и затраты, связанные с потерями от неправильного распознавания.
Задача распознавания образов, таким образом, может характеризоваться следующей четверкой:
(Q, A, R, С).	(В.1)
Отсутствие в этой четверке одного из первых трех элементов и определяет тип задачи распознавания:
1)	заданы множество классов А (это множество обычно задается обучающей выборкой), пространство признаков Q; требуется найти решающее правило /?, минимизирующее затраты С;
5
2)	заданы множество классов А и тип решающего правила /?; требуется найти такую систему признаков Q, которая минимизировала бы величину С;
3)	задано пространство признаков Q, требуется найти множество А и решающее правило R Это задача классификации или обучения без учителя.
В этой книге рассматриваются лишь задачи первого типа. Задачи этого типа предполагают наличие в распоряжении исследователя последовательности ситуаций X, принадлежащих всем различным классам А3, /=1, 2, ..., I. При проверке работы алгоритма эта последовательность должна быть разбита на две подпоследовательности: обучающую и экзаменационную, или контрольную. Характер такого разбиения определяется экспертно и целиком лежит на совести исследователя. Иногда для этого используют генератор равномерно распределенных случайных чисел. Соотношение обучающей и контрольной последовательностей, их объемов варьируется в самых широких пределах в зависимости от общего объема всей последовательности, от размерности пространства признаков и т. п.
Если алгоритм оказывается работоспособным, то его обучение следует вести на всей имеющейся последовательности ситуаций. Задача заключается в том, чтобы на основании имеющейся обучающей последовательности синтезировать решающее правило, которое с минимальной ошибкой различало бы заданные классы, т. е. распознавало бы новые, ранее (при обучении) не встречавшиеся ситуации. Контрольная последовательность необходима для оценки качества построенного решающего правила.
Однако четверка (В.1) характеризует тип задачи распознавания формально. Здесь отсутствует связь между ее элементами. Поэтому к четверке элементов (В.1), определяющей тип задачи распознавания, следует добавить некие интуитивные' или эвристические предположения, обусловливающие применение того или иного алгоритма.
Одним из наиболее существенных предположений является требование представительности обучающей последовательности, т е. насколько хорошо элементы обучающей последовательности А отражают истинную структуру распознаваемых образов. Это предположение о представительности обучающей последовательности интуитивно в том смысле, что проверить его сложно, а подчас и невозможно. Именно поэтому на указанное требование практически почти не обращают внимание, поскольку исключительно редко исследователь способен управлять объемом и характером этой последовательности. Подобная ситуация нередко возникает в медицинской диагностике, где сбор статистического материала практически неуправляем, так как нельзя же искусственно вызывать заболевание. Иная ситуация возникает при решении задачи прогнозирования различных аварийных ситуаций, например, в электроэнергетической системе. Здесь возможно управление статистикой, так как обучающую последовательность можно получить и расчетным путем на модели (авария — не такое уже частое явление в энергосистеме).
Очень чувствителен к требованию представительности обучающей последовательности алгоритм ближайшей точки Этот алгоритм относит новую ситуацию X к тому из классов A3i /=1, 2, ..., /, элемент которого, в пространстве признаков Q находится ближе всего к данной ситуации в смысле некоторой метрики (например, евклидова расстояния):
ХеЛр если р (X, Xrt) = min р (X, Xf),	(В.2)
6
где Хг (i=l, 2, ..., /)—t-й элемент (ситуация) обучающей последовательности; р(Х, Хг)—расстояние между элементами X и Хг.
Чувствительность этого алгоритма к непредставительности обучающей последовательности связана с тем, что каждый непредставительный элемент при этом порождает вокруг себя целую зону непредставительности, что значительно снижает эффективность алгоритму.
Не менее чувствителен к этому требованию любой из алгоритмов статистической теории решений, основанный на вычислении оценок некоторых параметров по обучающей последовательности. Если представительность обучающей последовательности существенно влияет на достоверность получающихся оценок, то объем этой выборки влияет также и на точность оценок. Это относится к любому из известных параметрических методов {6, 16, 53, 56].
Другим важным требованием к применимости статистических алгоритмов^ является информация о плотности распределения ситуаций. Чаще всего используется нормальный закон, и тогда вычисляются оценки для первого и второго моментов. Это предположение (о нормальности) достаточно жесткое и поэтому не так уж часто выполняющееся на практике. Однако, как правило, исследователь это требование вообще не проверяет. Если же он пытается проверить его, то для этого необходимо вводить дополнительные упрощения, поскольку строгая проверка гипотезы нормальности < априорных распределений в многомерном случае — громоздкая, сложная и дорогая вычислительная процедура.
Наиболее общее описание статистических алгоритмов распознавания дано в [6, 16, 53, 56]. Многомерная плотность нормального распределения объектов класса А3 записывается следующим образом:
Р(*М,) = ^jn/2, s. |1/2-ехР	(x-M/)rs7‘ (х-м;)},
(В.З)
где Mj — вектор класса А/, 2/— ковариационная матрица этого же класса; Т — знак транспонирования.
Известно [53], что для симметричной функции потерь оптимальное решающее правило использует дискриминантные функции вида
Л(Х)=1пр (X/AJ+lnР(Д.), / = 1, 2, ..., Л (В.4)
где Р\(А3) — априорная вероятность /-го класса.
В случае /=2 единственная дискриминантная функция может быть записана следующим образом:
/(Х) = 1п^+1п]/-^ + 4-(О2“!-ОГ')> (В-5) где G^-1 = (X — Му)т ST"1 (X — Му) — положительно определенная квадратичная форма для /-го класса; / = 1,.2. Решающее правило записывается следующим образом:
Х£Л1, если f (X)	0;	|
Xg^2> если f (X) < 0. J	’
Таким образом, оптимальная разделяющая поверхность для нормального распределения объектов квадратична. Если ковариацион
7
ные матрицы равны 51 = 2з=2, то разделяющая поверхность мёж-ду множествами или классами Д1 и Лг линейна:
f (X) = In +_L Mr S-1M2 -
---+	— M2) = 0.	{B.7)
Наконец, наиболее частный и простой случай, когда множество объектов каждого класса является сферической группой (2 = 1) и все классы имеют одинаковые априорные вероятности Р(Д1) = = Р(А2) = 1/2. В этом случае
f (X) = X (М, — М2) + 4“ (Л*£ М2 —	М.) = О	(В.8)
и имеем алгоритм минимума расстояния до средних, разделяющая граница которого также линейна.
Если снять условие нормальности априорных распределений, можно легко получить алгоритм Байеса, объединяющий минимально полный класс статистических решающих функций [5]. Этот алгоритм основан на вычислении апостериорных вероятностей принадлежности ситуации X к классам Д1 и Аг:
P(A3/X)=kP(A3)p(X/A3),	(В.9)
где k — нормирующий множитель.
Принятие решения осуществляется по следующему правилу:
х (А-	Я(А/Х)>Р(А/Х);
U2, есЛи^Р(Л/Х)<Р(Л2/Х).	1	’
Применимость этого алгоритма ограничена тем, что ситуации должны представлять собой бинарные векторы, т. е. значения признаков должны быть равными 0 или 1. Это требование обусловлено тем, что оценка распределений р(Х/А3) представляет большие трудности, так как требует огромной обучающей последовательности. В случае двоичных признаков легко осуществима их частотная оценка Поэтому, когда на практике пользуются этим алгоритмом, предварительно решают задачу оптимального квантования непрерывных признаков. От того, насколько удачно это квантование, зависит во многом результат обучения При использовании этого решающего правила также чаще всего предполагается независимость признаков [13], что на практике не всегда выполняется
Статистические алгоритмы распознавания, о которых шла речь ^выше, опираются на предположение о статистическом характере обучающей последовательности и выявляют статические характеристики этой последовательности. Детерминистские алгор-итмы построены на иных принципах. Они выявляют регулярные свойства обучающей последовательности Примером является рассмотренный выше алгоритм ближайшей точки (В.2), который учитывает лишь одну или несколько ближайших точек. Существуют, однако, детерминистские алгоритмы, учитывающие все точки обучающей последовательности. Таким методом, в частности, является метод потенциальных функций [3, 4, 10—12]
Как отмечено в ’[35], детерминистские алгоритмы построены на абсолютном доверии к обучающей выборке Характер распределения 8
генеральной совокупности, получаемый в результате аппроксимации обучающей выборки, и решающая функция могут быть сколь угодно сложными. Для этих алгоритмов важно, чтобы все ситуации обучающей последовательности распознавались без ошибок. Отличаются эти алгоритмы лишь способом аппроксимации некоторой «функции распределения в точках пространства, не содержащих ситуации из обучающей последовательности.
Существует множество различных модификаций метода потенциальных функций. Основная идея этого метода заключается в следующем. Каждая ситуация обучающей последовательности Х={Хг}, 1 = 1, 2, ..., Д порождает в й потенциал, вычисляемый с помощью некоторой потенциальной функции (р(Х, Хг), зависящей от Хг-, как от параметра. Решающая функция Ф(Х, Xi, Х2, ..., X/) представляет собой суммарный потенциал, наводимый всеми точками обучающей последовательности X. Если теперь с обучающими ситуациями класса Ai связать положительные значения функций ср ^положительный потенциал), а с ситуациями класса А2 — отрицательные, то разделяющая поверхность определяется нулевым потенциалом, т. е. описывается уравнением
Ф(Х, Хь Х2,	Xi)=0.	(В.11)
Это уравнение есть геометрическое место точек, в которых суммарный потенциал, наведенный ситуациями обоих классов, равен нулю.
Обучение в этом алгоритме состоит в том, что потенциалы точек обучающей последовательности, распознанных неправильно, увеличиваются до тех пор, пока все точки обучающей последовательности не распознаются правильно. (Однако это требование нередко приводит к довольно плохой экстраполируемости результатов обучения, ше. к плохой классификации контрольной последовательности.)
В качестве потенциальной функции обычно выбираются монотонно затухающие функции от расстояния р между точками, например ндИ 1/(1-|-ар2). Обучение представляет собой итеративную процедуру и сходимость этой процедуры доказана [3] для случая компактных классов, хорошо разделимых с помощью не слишком вычурных разделяющих границ.
Здесь сталкиваемся с чрезвычайно важной гипотезой — гипотезой компактности, требованием, выполнение которого обеспечивает успех распознавания [3, 10—12, 16]. Эта гипотеза, сформулированная для зрительных образов, заключается в том, что простому зрительному образу (классу) соответствует компактное множество точек в пространстве признаков. Очевидно обобщение этой гипотезы на образы любой природы. Это определение дополняется следующими положениями.
Множества точек (ситуаций) в пространстве признаков, соответствующие классам, компактны, если при малых вариациях ситуаций § любом направлении они не выходят за пределы своего класса. Очевидно, количество граничных точек класса может служить показателем компактности. Действительно, чем больше у множеств граничных точек, тем труднее они разделимы, и компактным называется множество, для которого число граничных точек мало по сравнению с общим числом точек. Проверка гипотезы компактности также представляет значительную сложность.
2—1} 07	9
В этом небольшом обзоре рассмотрены лишь некоторые из известных алгоритмов распознавания и условия их применимости. Трудности, возникающие при проверке различных гипотез применимости тех или иных алгоритмов, а также необходимость решения сложных нелинейных задач распознавания породили идею объединения различных по характеру алгоритмов в коллектив. Общая схема коллектива будет рассмотрена подробно в следующей главе. Но перед тем, как непосредственно обратиться к основной теме данной книги, рассмотрим класс алгоритмов, который наиболее близок к рассматриваемому подходу. Это так называемые иерархические системы распознавания.
В.2.	ИЕРАРХИЧЕСКИЕ СИСТЕМЫ РАСПОЗНАВАНИЯ
Эти системы распознавания в последнее время получили широкое распространение [9, 1'2, 16, 3/, 47, 55, 71, 76, 86, 87, 91]. Остановимся подробнее на двух наиболее популярных подходах: перцептроном [12, 16, 47, 55, 71] и переборной схеме М. И. Бонгарда [9, 38].
Рассмотрим, что представляет из себя перцептрон — система распознавания образов, моделирующая зрительное восприятие живых организмов. Автор перцептрона Ф. Розенблат [7Ц предложил его не как распознающее устройство, а как некую модель мозга. Пер
цептрон состоит из множеств отдельных элементов, связанных в единую сеть. Множество элементов, реагирующих на сигналы внешней
Рис. В.1. Структурная схема трехслойного перцептрона.
среды, называется сетчаткой или полем рецепторов (S-элементы). Эффекторную роль выполняют R-элементы, а связь между ними реализуется множеством ассоциативных элементов (A-элементов) с изменяемой матрицей взаимодействия с R-элементами. Эта матрица образуется весами всех A-элементов. Структурная схема простейшего (трехслойного) перцептрона изображена на рис. В.1.
Воспринимающим устрой
ством перцептрона является поле рецепторов (ими могут быть, например, фоторецепторы), каждый из которых может находиться в одном из двух состояний: 1 или О, в зависимости от того, возбуждается соответствующий рецептор или нет. Следующий уровень (слой) образуют A-элементы, или ассоциативные элементы. Их число должно быть близко к числу рецепторов,
однако в этом случае практическая реализуемость перцептрона в силу его громоздкости становится затруднительной. Обычно используют значительно меньшее число A-элементов. Эти элементы имеют несколько входов и один выход. S-элементы подключаются ко входам A-элементов с разными знаками. Матрица связей между S- и A-элементами определяет, какие рецепторы связаны с определенным A-элементом и каков знак этой связи. Эта матрица может задаваться различным образом, например может быть случайной. Оказывается, что удачность выбора этой матрицы существенно влияет на качество обучения и распознавания. A-элементы осуществляют сумми-
40
Ройание сигналов, Поступающих на их входы, и сравнивают Полученные суммы с некоторым порогом 9. Сигнал a,j на выходе /-го A-элемента зависит от того, превышает ли полученная сумма заданный порог или нет:
п
1, если
1=1 п
О, если 2
1 = 1
(В. 12)
где bij — ±il определяет знак связи от i-ro рецептора к /-му А-эЛе-менту; если Ьгз=0, i-й рецептор с /-м A-элементом не соединен; п — число признаков; / = 1, 2, ..., 7И; А! — число А-элементов.
Выходные сигналы A-элементов взвешиваются с помощью коэффициентов и результат суммируется:
М
г=2 w /=1
(В. 13)
Этот сигнал поступает на вход решающего элемента (R-элемен-та). Этот элемент реализует следующее пороговое правило принятия решения:
(В.14)
0.
v (Alf если
XS л IА2, если Обучение перцептрона реализуется с помощью итеративной процедуры коррекции весов (3j, / = 1, 2..М. На каждом шаге обу-
чения на вход перцептрона подается изображение X объекта одного из образец В зависимости от принятого перцептроном решения производится коррекция коэффициентов 0,. Можно за конечное число шагов обучения привести перц|птрон в такое состояние, что он с достаточной надежностью будет распознавать предъявляемые ему изображения.
Известно большое число алгоритмов обучения перцептрона. Например, обучение может состоять в том, что коэффициенты изменяются лишь при ошибках перцептрона [12]. Если перцептрон при предъявлении объекта класса А4 отреагировал: ХеА2, то веса возбужденных A-элементов, для которых aj = l, увеличиваются, чтобы увеличить г. Если перцептрону был предъявлен объект класса А2> а перцептрон отреагировал: XsAi, то коэффициенты возбужденных A-элементов уменьшаются, чтобы уменьшить г. По поводу сходимости таких процедур обучения перцептрона доказаны соответствующие теоремы [87].
Следует отметить, что применимость перцептрона ограничена бинарными изображениями, в противном случае необходимо квантовать признаки, как в рассмотренном в § В.1 методе Байеса.
Это ограничение свойственно и второму классу иерархических алгоритмов, основанных на схеме М. М. Бонгарда [9], который ^предложил решающую функцию задачи распознавания искать >в классе логических функций в виде дизъюнкции конъюнкций, определенных на описаниях объектов. Этот класс методов часто называют методами перебора конъюнкций. Эти методы обладают опре-2*	11
Деленными преимуществами перед описанными в § В.1 методамй распознавания. Так, например, они не требуют апри®рной информации о характере функций распределения изображений в пространстве признаков. Кроме того, эти методы не требуют значения всех характеристик объектов, они работают и с объектами с неполным описанием, что очень ценно при решении задач медицинской диагностики.
Нетрудно заметить некоторую аналогию метода М. М. Бонгарда и перцептронных алгоритмов. Действительно, в перцептроне каждый A-элемент фактически реализует некоторую логическую функцию от признаков, которые связаны с этим А-элементом.
Алгоритм «Кора» основан на поиске сочетаний (дизъюнкций) признаков, которыми обладают объекты одного класса и не обладают объекты другого. Признаки класса образуются в виде конъюнкций, составленных из признаков исходного описания. Качество каждой конъюнкции как признака класса определяется числом объектов, на которых эта конъюнкция принимает единичное значение. Поиск производится среди всех возможных конъюнкций исходных переменных, описывающих объект, и их отрицаний. Считается, что объект обладает данным признаком, если конъюнкция, соответствующая этому признаку, принимает на этом- объекте единичное значение. Легко заметить, что число возможных перебираемых конъюнкций достаточно велико и резко возрастает при увеличении числа переменных в описании объекта. Для сокращения времени перебора максимальная длина просматриваемых конъюнкций ограничивается. При распознавании определяется число конъюнкций — признаков каждого класса, принимающих на контрольном объекте единичное значение. Объект относится к тому классу, для которого это число оказывается наибольшим.
Обучение этого алгоритма состоит в следующем. Рассматривается произвольная конъюнкция. Для нее подсчитывается число объектов каждого класса, на которых она принимает единичное значение. Число таких объектов для произвольного класса Aj обозначим через lj.
Если найдется такой класс что для него значение /у.* превышает некоторый заданный порог Zo, т. е. Zy*>Ze, а для остальных классов lj = 0, то данная конъюнкция является достаточным признаком класса А.* с оценкой Z/#. В простейшем виде алгоритм «Кора» отыскивает такие признаки каждого класса. Однако, информативными могут оказаться и более «слабые» конъюнкции, для которых на /*-м классе Zp»>Z, и на остальных классах lj <10. Существуют различные модификации этого алгоритма, но суть его заключается в том, что для каждого класса определяются конъюнкции, голосующие за него. Решение принимается по большинству голосов.
Перцептронный алгоритм и алгоритм, основанный на переборе различных конъюнкций исходного описания, являются иерархическими алгоритмами распознавания по двум причинам. С одной стороны, иерархичность связана с тем, что на первом нижнем уровне формируются обобщенные признаки, для перцептронного подхода — это выходы A-элементов, для процедуры М. М. Бонгарда — значения конъюнкций; на втором верхнем уровне принимается решение на базе этих обобщенных признаков путем суммирования или голосования. С другой стороны (наиболее интересной для нас), иерархии-12
ность здесь просматривается в том, что на первом уровне формируется много элементарных решений, а на втором уровне эти решения взвешиваются и голосуют за различные образы. Образ, набравший большинство голосов (с учетом их веса), и является принимаемым решением.
Следует отметить, что рассмотренный в предыдущем параграфе метод потенциальных функций может быть отнесен к таким иерархическим системам распознавания, так как здесь решающая функция представима в виде разложения по некоторой системе функций. Каждый элемент этого разложения может интерпретироваться как взвешенное элементарное решение нижнего уровня. Действительно, каждое слагаемое потенциальной функции является вкладом, голосом одного из элементов обучающей выборки за свой класс. Здесь голосует вся обучающая последовательность.
Следующим шагом к совершенствованию иерархических систем распознавания (и не только распознавания) является синтез и обучение иерархии алгоритмов с учетом специфики решаемой задачи.
Это обстоятельство и было основной причиной появления предлагаемого подхода. Решающее правило должно быть адекватно решаемой задаче распознавания.
Из приведенного краткого обзора становится ясным, что этот выбор такого правила чрезвычайно затруднен из-за огромного многообразия алгоритмов и правил распознавания, разработанных к настоящему времени. Часто применимость того или иного алгоритма во многом определяется полуинтуитивными соображениями исследователя (а интуиция здесь работает плохо!). Проверка условий применимости, как уже было сказано, не всегда возможна и обычно связана со значительными вычислительными затратами. Именно поэтому объединение различных решающих правил в коллектив позволяет обойти проверку условий их применимости и наилучшим образом исполь^вать особенности этих алгоритмов и решающих правил.
ГЛАВА ПЕРВАЯ
КОЛЛЕКТИВ РЕШАЮЩИХ ПРАВИЛ В ЗАДАЧЕ РАСПОЗНАВАНИЯ
1.1. ОБЩАЯ СХЕМА КОЛЛЕКТИВА
Рассмотренные в § В.2 иерархические алгоритмы распознавания можно рассматривать как голосующие алгоритмы, точнее, как коллектив решающих правил, между которыми устраивается голосование. Такое же голосование можно устраивать и между другими традиционными алгоритмами. Однако недостаток этих алгоритмов состоит в том, что весА решающих правил при голосовании фиксированы и- не изменяются. Другими словами, не учитываются индивидуальные особенности конкретной распознаваемой ситуации.
Перед тем как непосредственно перейти к рассмотрению алгоритмов коллективного распознавания, введем ряд формальных определений.'
Коллективом решающих правил будем называть некоторое ко нечное подмножество {/?} множества всех возможных решающих правил U, {R}ciU, {R} = {Ri}; /—1, 2, ..., L, образованное для выработки коллективного решения. Ri—1-е решающее правило. Вид
13
коллективного ращения конкретизируется типом задачи, решаемой данным коллективом. Поскольку речь идет о задаче распознавания образов, и коллективное решение, и индивидуальные решения, принимаемые членами этого коллектива, состоят в отнесении некоторой ситуации или объекта X к одному из классов или множеств Aj, i=lt 2...../,	например, как это изображено на рис. 1.1 для /=2.
Ситуация X характеризуется вектором параметров или признаков: Х={х1, хг, ...» хп}- Величину L будем называть порядком коллектива решающих правил.
Формально задача принятия коллективного решения ставится следующим образом: если Si, 1=1, 2.....'L — индивидуальные ре-
шения, принимаемые членами коллектива — решающими правилами Ri, 1, 2,..., L, то коллектив-
ное решение определяется как некоторая функция индивидуальных решений:
S=F(Si, S2.....SL, X). {1.1)
Рис. 1.1. Решение в задаче распознавания.
Рис. 1.2. Структурная схема коллективного принятия решений.
Здесь F — алгоритм принятия коллективного решения.
На рис. 1.2 представлена структурная схема коллективного принятия решений.
Решение S в задаче распознавания состоит в выборе номера одного из классов А3, / = 1, Q, ...» /, для каждой конкретной ситуации X, для которой правила Ri принимают различные решения:
Sz: ХеД,=^(Х); /=1, 2, ..., L; /=1, 2, ..., /.	(1.2)
Рассмотрим, например, алгоритм голосования. Пусть q3 — голосующая функция /-го класса:
=	=	/«=1.2, ..и/,	(1.3)
I
где jjii — соответствующим образом нормированный вес /-го решающего правила; суммирование ведется по тем /, для которых Sz=j. Решение о принадлежности ситуации X к одному из классов А}, / = 1, 2, ..., /, принимается по следующему правилу:
ХеЛу*» если ^# = шах<7р / = 1,2, ...,/.	(1.4)
Пример такого решения иълюстрируется рис. 1.3. Здесь Q (X) = =0—разделяющая поверхность между классами At и А2; St: Xq At; 14
32:ХеЛ2; SaZXeMj; р./ = 1, /=1,2,3; ^ = 2; q2 = 1; ситуация X относится к классу Д.
Введем понятие области или множества компетентности решающего правила. Под этим будем понимать совокупность ситуаций X, для которых данное правило коллектива в некотором смысле наи-
более компетентно, например, в смысле минимума вероятности ошибки распознавания. Обозначим эти множества Bi, /=1, 2, ...
.L. Очевидно, возможна ситуация, когда для какого-нибудь решающего правила область компетентности может не существовать, т. е. Bi=0. Поэтому число областей компетентности меньше или равно величине L.
Уже отмечалось, что основ* ной недостаток алгоритмов голосования (1.3) состоит в независимости весов от ситуации X,
а также и в том, что при усред-
нении легко может возникнуть Рис. 1.3. Решение, принимаемое ошибка за счет ошибки больший- голосованием.
ства членов коллектива. Поэтому предлагается ввести зависимость веса от распознаваемой ситуации X: p,f=(pz(X). В этом и состоит основная^ мысль. Далее будет рассматриваться лишь следую-
щая зависимость:
Y. fl, если ХеBf, ~ 10, если Х<£В(,
(1-5)
L
причем р./(Х) = 1;	= 1, 2, ..., L; Qn — л-мерное прост
z=i
ранство признаков (хь х2, ..., хп).
\ Обобщение этого случая не представляет большого труда.
Подставляя выражение (1.5) в алгоритм голосования 1(1.3), получаем, что решение коллектива решающих правил S определяется решением того правила /?ь к области компетентности которого Bi принадлежит распознаваемая ситуация X: S=Si.
Из сказанного следует, что предлагаемый подход относится к иерархическим и представляет собой двухуровневую процедуру распознавания. На первом уровне осуществляется распознавание принадлежности ситуации X к той или иной области компетент
ности Bi, Z=l, 2, ..., L; на втором же решение правила, соответствующего данной области, отождествляется с решением всего коллектива. Структурная схема этой
Рис. 1.4. Структурная схема двухуровневой процедуры принятия коллективного решения.
процедуры представлена на рис. 1.4.
Очевидно, что основным в процедуре является обучение рас
15
познаванию областей компетентности Bi решающих правил коллектива {/?}. Это требует привлечения классических алгоритмов обучения, и далее будут рассмотрены различные подходы к решению этой задачи Но прежде чем приступить к рассмотрению вопросов обучения коллектива решающих правил, введем понятие коэффициента компетентности решающего правила.
Пусть F' — алгоритм распознавания областей компетентности В/, Z==l, 2, ..L. Тогда можно построить следующее правило отнесения ситуации X к той или иной области компетентности:
F'
Х->В/#, если (X) = max v/(X); / = 1, 2, Л, (1.6)
где величину Vz(X) будем называть коэффициентом компетентности 1-го решающего правила в ситуации X. Как видно, задача сводится к правильному определению коэффициентов компетентности
Рассмотрим способы выделения областей компетентности решающих правил — членов коллектива.
Рис. 1.5. Структурная схема коллективного принятия решения с обучением коллектива.
1.2. АЛГОРИТМЫ ВЫДЕЛЕНИЯ ОБЛАСТЕЙ КОМПЕТЕНТНОСТИ РЕШАЮЩИХ ПРАВИЛ
Как следует из поставленной задачи, синтез коллективного решающего правила F (1.1) сводится к определению оценок областей компетентности каждого решающего правила — члена коллектива, т. е. к распознаванию в конкретной ситуации X номера правила, которое в этой ситуации следует применять. Эту задачу, как и всякую задачу распознавания, следует решать методом обучения. Структурная схема коллективного принятия решения с обучением коллектива представлена на рис. 1.5. Под учителем в схеме понимается информация о принадлежности ситуаций обучающей последовательности к распознаваемым множествам.
Для решения этой задачи следует использовать алгоритмы распознавания, способные решать многоклассовые (в данном случае L-классовые) задачи, не прибегая при этом к последовательной дихотомии. Это связано тем, что порядок коллектива решающих правил обычно больше двух. Кроме того, этот алгоритм должен непрерывных, и для случая ди-может базироваться на методе решающем правиле, если пара
метры можно дискретизировать, правиле ближайшей величины и т п Задача синтеза коллективного решающего правила F может быть рассмотрена двояким образом С одной стороны, можно искать зоны компетентности решающих правил, используя вероятностное 16
быть работоспособным и для случая скретных признаков. Такой алгоритм потенциальных функций, байесовом
свойства правил и восстановления плотности распределения вероятностей компетентности или используя гипотезу компактности и вводя потенциальные поверхности компетентности для каждого решающего правила. Математическим аппаратом для реализации последнего метода является известный аппарат потенциальных функций [3—4, 10—12, 16, 64—68].
С другой стороны, можно все пространство признаков Q?i заранее разбить на достаточно мелкие подобласти, в которых в процессе обучения следует определить коэффициенты компетентности каждого правила, что позволит определить решение коллектива во всем пространстве признаков. Этот алгоритм в дальнейшем называется методом априорного задания областей компетентности.
Следует сказать, что предлагаемые алгоритмы не ограничивают возможности включения в коллектив самых различных решающих правил и алгоритмов, даже неформализованных, т. е. таких, для которых нельзя формально описать процесс принятия решений.
Алгоритм А
Алгоритм, в основе которого лежит известная в теории вероятностей формула Байеса [5, 13, 28, 52], требует знания априорных вероятностей разделяемых множеств Р(Вг); такими множествами в данной задаче являются множества (области) компетентности решающих правил — Bi, 1=1, 2, ..., L, и условных распределений На основе этой информации алгоритм позволяет определить апосте^Яюрную вероятность принадлежности ситуации X к области компетентности Bi, 1—1,2, ..., L:
P(BZ/X)=^P(BZ)P(X/BZ),	(1.7)
где k — нормирующий множитель:
р (X) ‘
2 P(Bt) PiX/Bt) 1=1
Область компетентности Bp, к которой относится ситуация X, определяется согласно выражению
ХеВ/#, если Р(В.#/Х) = max P(BZ/X). (1.9) 1
Этим определяется то решающее правило чье решение в данной ситуации отождествляется с решением коллектива. Полученные по (1.7) .апостериорные вероятности определяют однозначно коэффициенты компетентности (1.5):
(1, если Р (В/#/Х) = max Р (Bz/X);
(X) ~ <	I
[0 в противном случае.
При реализации этого алгоритма предполагается следующее:
1. Каждый параметр или признак хг, i=l, 2, ..., п дискретен, в частности может принимать только два значения: 0 или 1. В этом случае оценка условного распределения P(X/Bi) заключается в вычислении элементов матрицы условных вероятностей {р(хг/Вг)}, что сравнительно просто ,реализуется. Если..-призняки непрерывны, то,
как уже отмечалось, возникает задача оптимального квантований и кодирования
2. Признаки Х{ и Xk V i, k [i=£k, z=l, 2, ...» л; k=l, 2, ..n] считаются независимыми. Это позволяет вычислять значения условных вероятностей P(X/Bz), используя теорему умножения вероятностей независимых событий, которая в случае, когда хг=0 или х<=1, имеет вид:
п
Р(Х/В/)=П {[1-p{xl/Bl)}-xl[\-2p(xi/Bl)]}. (1.10) 1=1
Под обучением в данном алгоритме понимаются выделение обучающих последовательностей для каждой из областей Bi, Z=l,
Рис. 1.6. Структурная схема последовательной процедуры обучения коллектива.
2, ..., L, и оценка по этим последовательностям значений p(xx/Bi), f=l, 2, ...» n; Z=l, 2, ..., L.
Следует различать последовательную и параллельную процедуры обучения, структурные схемы которых изображены соответственно на рис. 1.6 и 1.7.
На рисунках приняты следующие обозначения: {X} — множество ситуаций X, принадлежность которых к различаемым множествам или классам известна точно.
Рис. 1.7. Структурная схема параллельной процедуры обучения коллектива.
Это можно интерпретировать как результат применения некоего метаправила. Примером такого метаправила может служить патана-томическое вскрытие как критерий верификации в медицинской диагностике; q=1, если Z-e правило принимает правильное решение; cz=O, если /-е правило принимает ошибочное решение; {Xz} — обучающая последовательность для обучения распознаванию области компетентности Bi.
В последовательной процедуре обучения все множество объ
18
ектов на каждом шаге т усекается последовательно на подмножества {XJ, {Xjcz{X}. Для произвольного шага т
= | (1П) =	Z, m = 1, 2....L; m = Z, J
где {Xm} — множество объектов, из которого решающим правилом Ri выделяется обучающая последовательность {XJ. Для решающего правила Rt предлагается выбор последовательности {XJ из всего множества {X}. В результате применения всех решающих правил, т. е. после L шагов процедуры, остается множество {XL+i}, для ситуаций или объектов которого ни одно из решающих правил не принимает правильного решения.
Чаще нам приходилось использовать параллельную процедуру выделения обучающих последовательностей. Это касалось не только этого алгоритма, но и метода, основанного на методе потенциальных функций. В этой процедуре обучающая последовательность {X/} формируется из тех объектов Хе{Х}, для которых Ci= = 1, 1—1, 2,	, L. Последовательность {Xl+i} формируется из тех
объектов Хе{Х}, для которых ci=Q для всех 1=1, 2, ..., L.
Байесово решающее правило, вообще говоря, обеспечивает оптимальное в смысле минимума вероятности ошибки разбиение пространства признаков в данном случае на области компетентности. Как уже говорилось, это во многом ’зависит от качества обучения, от представительности обучающей последовательности. - Если бы можно было с достаточной уверенностью положиться на обучающую последовательность, то, по-видимому, не было бы необходимости в синтезе коллектива алгоритмов. Однако совершенно очевидно, что ошибка в определении наиболее компетентного решающего правила менее чувствительна, чем ошибка собственно распознавания. Дело в том, что второе по уровню компетентности правило может принимать правильное решение. Рассмотренной модификации этого алгоритма присущи все недостатки ее прототипа. Это требование достаточно представительной ^обучающей последовательности, что не всегда обеспечивается условиями конкретной задачи. Кроме того, применимость алгоритма ограничена объектами или ситуациями, описываемыми бинарными или, по крайней мере, дискретными признаками, поскольку оценка непрерывных распределений представляет большие трудности [5]. В противном случае, как уже не раз говорилось, возникает задача оптимального квантования и кодирования признаков, что в свою очередь является источником погрешностей.
Однако вместе с недостатками имеются и некоторые преимущества. Основное из них связано с простотой вычислительной реализации: не требуется хранить в памяти вычислительной машины обучающую последовательность, достаточно лишь помнить матрицу условных вероятностей p(Xi/Bi), 1=1, 2, ..., L, f=l, 2, ..., и, и вектор априорных вероятностей P(Bi), 1=1, 2, ..., L.
Следующий алгоритм обучения коллектива решающих правил использует широко известный в теории распознавания образов метод потенциальных функций [3, 4, 10—12].
19
Алгоритм Б
Этот алгоритм в обычной постановке требует, чтобы распознаваемые множества ситуаций были компактны [3, 11, 16]. Это означает, что разделяющая поверхность между ними должна быть не очень вычурна. Интуитивно кажется, это требование должно выполняться для областей компетентности. Действительно, ситуации, близко расположенные в пространстве признаков, относятся к области
_	.	компетентности	одного правила,
Рис.	1.8.	Потенциальная	функ-	т е. правильно	распознаются этим
Ция-	правилом. Это	можно проследить
на примере консилиума В область компетентности специалиста, как правило, входят больные с близкими клиническими картинами, причем это могут быть больные с разными заболеваниями.
В методе потенциальных функций [3] предполагается, что разделяющая функция представима в виде разложения в ряд по системе функций фг (X), Z==l, 2, ..., т:
т
Г(Х) = 2с,?((Х).	(1.12)
i
Алгоритмы метода потенциальных функций, используя обучающую последовательность, позволяют определять такую функцию fm(X), которая при т—>-оо должна точно аппроксимировать функцию /*(Х). Основным является вопрос выбора наилучшей системы таких функций. Возможны различные реализации этого метода. Например, к каждому (т+1)-му шагу в памяти машины хранится т чисел си, ..., aw и т объектов Xi, ..., X™ При «показе» (т+1)-го объекта Xm+1 подсчитывается значение frn(X7n+1), и решение принимается по следующему правилу:
Г(Х^)>0, Х^еЛ;
^(Х^+1)<о, х^еД,.-	1	'
Для случая обучения распознаванию областей компетентности решающих правил используется более простая модификация этого метода. Имеются обучающая последовательность Х={Хг), /=1, 2, .. , I, состоящая из представителей множеств А,, /=1, 2, ..., /, и коллектив решающих правил {7?}={i/?J, Z=l, 2, ..., L. Для каждого решающего правила Ri в каждой точке обучающей последовательности X устанавливается заряд компетентности giz^{—1, 1}, знак которого зависит от того, правильно или ошибочно распознается этот объект /-м правилом Потенциал компетентности в произвольной точке X, наводимый этим зарядом, определяется известным образом [3, 4, 11, 12]
?/(Х. х,)_ 1+а/(рГ(Х> Х() ,
(1.14)
20
где
+ 1, если Z-e решающее правило в точке Xz принимает правильное решение;
—1, если Z-e решающее правило в точке Х£- принимает ошибочное решение;
Р(Х, Хг) — расстояние между X и X; (не обязательно евклидово); ан — коэффициенты затухания потенциальной функции.
Характер поведения выбранной потенциальной функции (1.14) показан на рис. 1.8. На рис. 1.9 приведен пример, иллюстрирующий наведение потенциалов компетентности решающих правил точками обучающей последовательности. Так, в точке Хь £ц=—1, g2i=+l; в точке Ха: ^12=+ 1, g22=—1; в точке Х3: Я1з=Я2з==—1; в точке Х4: ^14=^24 = + !.
Рис. 1.9. Наведение потенциалов компетентности.
Потенциал компетентности Z-го решающего правила в точке X определяется, простым суммированием:
/
Ф|(Х) = 2 ?/(Х, Х().	(1.15)
/=1
Таким образом, в точке X фиксируется L потенциалов компетентности решающих правил — членов коллектива и решение в ситуации X принимает правило с номером /*, потенциал компетентности которого в данной ситуации максимален, т. е.
(X), если (X) = maxф/(X), Z=l,2,
(1.16)
Потенциал компетентности (1.5) решающего правила (1.16) представляет собой коэффициент компетентности в (1.6).
21
Этот алгоритм обеспечивал бы высокое качество распознавания областей компетентности, если бы обучающая последовательность отражала все разнообразие ситуаций каждой области {12]. Это означает, что потенциал, создаваемый в любой точке одного из классов точками других классов, был бы меньше потенциала, создаваемого точками своего класса. Однако такое нециклическое обучение не обеспечивает равномерного распределения точек, поэтому ошибочно распознаются даже точки обучающей последовательности. Как и в других алгоритмах распознавания образов, критерием качества обучения в методе потенциальных функций является вероятность ошибки распознавания объектов обучающей и контрольной последовательностей.
Для устранения указанного недостатка в алгоритме используется циклическая процедура обучения [3, 12], которая заключается в следующем. После ввода в ЭВМ обучающей последовательности ей предлагают распознавать те же самые объекты и контролировать правильность своей работы. Если происходит ошибка,v заряд соответствующей точки увеличивается на некоторое значение, например на единицу. Потенциал, наводимый этой точкой, на следующем шаге будет удваиваться. Затем повторяется такой же цикл до тех пор, пока в очередном цикле все точки обучающей последовательности не будут распознаны правильно. Такая процедура позволяет сделать распределение точек в области каждого класса более равномерным. Более редкие и близкие к чужим классам точки приобретают больший вес.
В предлагаемом алгоритме обучения распознаванию областей компетентности организуется аналогичная процедура. Следует заметить, что в отличие от традиционного метода потенциальных функций в рассматриваемом подходе отсутствует нормировка. Это обусловлено спецификой обучения: все точки обучающей последовательности распознаются каждым решающим правилом и определяющее значение имеет результат распознавания: правильно оно или ошибочно. Число представителей того или иного класса решающего значения не имеет.
После определения зарядов компетентности £ц, 1—1, 2, ..., L, t=l, 2, ..., I, объекты обучающей последовательности распознаются коллективом правил, решение которого организуется согласно (1.15) и (1.16). Если при этом правило Р/* ошибается в точке Хй то заряд компетентности этого правила уменьшается на некоторое значение, например на единицу. Тем самым уменьшается вклад этой точки в формирование поверхности компетентности этого правила. Такая коррекция однако, может привести к глобальному искажению потенциальной поверхности в силу характера зависимости (1.14). Чтобы этого не произошло и коррекция касалась потенциальной поверхности Z*-ro правила лишь в некоторой окрестности точки Хг, необходимо корректировать и коэффициент затухания^»;. Необходимо увеличить таким образом, чтобы при уменьшении заряда gpi вклад r-й точки в потенциальную поверхность Z*-ro правила вне некоторой окрестности этой точки остался прежним. Эту процедуру, очевидно, также следует организовать циклически.
Процесс обучения следует закончить, когда все точки Xt-, f= = 1, 2, ..., 7, обучающей последовательности будут правильно распознаны коллективом. Может, однако, оказаться, и это не такая уж редкая ситуация, что ряд точек не распознается правильно ни одним 22
йз правил или достаточно большое число циклов не приводит к заметному улучшению качества. Поэтому другим критерием остановки процесса обучения является некоторое число £ — число циклов, на которых вероятность ошибки распознавания объектов обучающей последовательности не уменьшается.
Нетрудно заметить, что в такой постановке метод потенциальных функций довольно быстро сходится на обучающей последовательности, если значительно увеличить а в (1.14). При этом потенциальная функция в каждой точке Xt стремится к дельт а-функции и не оказывает никакого влияния на соседние с ней точки. Используя же полученные потенциальные поверхности для объектов, не встретившихся в обучающей последовательности, трудно быть уверенным в хорошей экстраполируемости результатов обучения.
Отсутствие достоверного критерия качества процедуры обучения представляет собой серьезное затруднение при решении задач распознавания не только методом потенциальных функций, но и другими методами.
Устранить это затруднение позволяет метод регуляризации обучающей последовательности. Для этого обучающая последовательность некоторым образом, например случайно, разбивается на две части: одна используется для обучения, на другой проверяется качество этого обучения.
Последовательность, на которой проверяется качество обучения, принято называть экзаменационной или контрольной. В данной работе используется именно такой метод оценки качества обучения. Однако и он вызывает некоторые возражения. Когда решают практическую задачу распознавания, объектов для обучения обычно не так уж много, чтобы еще сокращать обучающую последовательность.
В последнее время для оценки качества обучения широко используется так называемый метод скользящего экзамена, в котором вся имеющаяся последовательность, за исключением одной точки, используется для обучения. Качество обучения проверяется на этой единственной точке. Такая операция повторяется I раз для каждой точки обучающей последовательности. После этого вычисляется среднее число ошибок. Такой подход, однако, связан с большими вычислительными затратами.
Как уже отмечалось, критерием качества предлагаемых процедур обучения является вероятность ошибки распознавания объектов экзаменационной последовательности. Эта вероятность в значительной степени определяется точностью восстановления областей компетентности решающих правил. Кроме того, ошибка при определении наиболее компетентного решающего правила влечет за собой не столь существенные последствия, как ошибка собственно распознавания. Это связано с тем, что часто оказывается так, что неправильно выделенное наиболее компетентное решающее правило правильно распознает данную ситуацию X. Поэтому процедура такого коллективного решения слабочувствительна к ошибкам при определении границ зон компетентности алгоритмов.
Данный алгоритм обучения коллектива решающих правил для своей реализации требует хранить в памяти ЭВМ векторы объектов обучающей последовательности Хг, i=l, 2, ...,/, а также полученные в результате циклической процедуры величины ga и а^, 1= ,= 1, 2, ...» L; i=l, 2, ..., /.
23
Алгоритм В
Используем метод Фикса — Ходжеса для выделейия областей Компетентности. Этот метод [15, 56, 96] относится к классу непараметрических (локальных) алгоритмов распознавания и исторически является первым из таких методов. Суть его в применении к коллективному распознаванию сводится к следующему.
Пусть заданы: обучающая последовательность Х={Хг), i— = 1, 2, метрика р в пространстве признаков Йп и объект или ситуация X, относительно которой следует принять решение о принадлежности ее к области компетентности того или иного решающего правила из коллектива {7?/}, /=1, 2, ..., L. В качестве метрики р может быть выбрано, например, евклидово расстояние:
р(Х, X,) = |X—Xj|.	(1.17)
Упорядочим объекты обучающей последовательности Хг, i — = 1, 2, ... о /, поблизости к X в смысле заданной метрикир. После этого рассмотрим первые k объектов этой последовательности.
Для каждого объекта Хг обучающей последовательности известен результат применения каждого из решающих правил Ri, 1~ = 1, 2, ..., L, — членов коллектива {7?} :
-1, если объект X/ правильно распознается правилом Tfy;
О, если объект Xz ошибочно распознается >	правилом 7?/.
(Ы8)
Для принятия решения относительно объекта X используется то правило, которое правильно распознает большинство из k ближайших к X объектов обучающей последовательности.
Другими словами, ситуация X относится к области компетентности того правила, для которого
Х£^, если C/# = maxQ,	(1.19)
где	*
elm*	(1.20)
т=\
Пример использования этого метода приведен на рис. 1.10. Допустим, k = 3. Три ближайших к X объекта обучающей последовательности: Х2, Х4, Х5; Ci2=l; с22=0; Ci4=0; с24==1; Ci5=0; с25= 1. Тогда Ci—1, С2=2, сле
довательно, ХеВ2 и решение относительно объекта X принимает правило Т?2.
Этот алгоритм позволяет оценивать компетентность решающих правил не по всей обучающей последовательности, а по выборке, попадающей
Рис. 1.10. Пример использования метода Фикса — Ходжеса.
24
в некоторую окрестность распознаваемой ситуации X. Интуитивно ясно, что в силу свойства локальности алгоритм Фикса— Ходжеса должен хорошо решать задачу распознавания областей компетентности решающих правил — членов коллектива.
Проблемы, связанные с реализацией алгоритма, в основном касаются выбора оптимального значения величины k — числа ближайших точек. В. Н. Вапник и А. Я. Червоненкис в своей книге [15] сделали попытку определения оптимальной окрестности для подобных локальных алгоритмов.
Существует ряд возможностей для модификации этого алгоритма. Например, голоса си можно сделать обратно пропорциональными величине метрики р, т. е.
1/р (X, X/), если X/ правильно распознается правилом Rr,
О, если X/ ошибочно распознается правилом Ri.
(1.21)
Другой путь — это задание в качестве параметра алгоритма не числа ближайших точек, а радиуса окрестности точки X. Суммирование в выражении (1.20) тогда ведется по точкам, попадающим в эту окрестность.
Наиболее существенным достоинством алгоритма Фикса — Ходжеса является его подкупающая простота. Это очень важно потому, что иерархичность предлагаемой распознающей системы предполагает использование на каждом уровне простых решающих правил. В противном случае вся процедура становится слишком громоздкой и повышение качества распознавания достигается слишком дорогой ценой.
Рассмотрим еще один метод определения наиболее компетентного решающего правила.
1.3. МЕТОД АПРИОРНОГО ЗАДАНИЯ ОБЛАСТЕЙ
КОМПЕТЕНТНОСТИ
Этот метод построен на основе дискретизации пространства признаков Qn. Во всех дальнейших экспериментах этот метод обозначен как алгоритм Г. Дискретизация пространства признаков в последнее время получила широкое распространение в самых разнообразных задачах. Особенно можно отметить методы кусочной аппроксимации как методы восстановления функций [39]. Сущность этих методов заключается в следующем.
Область определения восстанавливаемой функции F(X) разбивается на некоторое количество подобластей, и аппроксимация ^(Х) в пределах каждой подобласти осуществляется отдельно. Если в каждой из подобластей функция F(X) имеет достаточно простой вид, то в качестве аппроксимирующих функций можно также использовать простые функции.
Задача распознавания образов также является задачей аппроксимации функции [3], и предлагаемый подход в некотором смысле может считаться алгоритмом кусочной аппроксимации.
3-П07	25
Итак, пространство признаков Qn, точнее говоря, область определения разделяемых множеств /=1, 2, ../, каким-то образом, например случайно, разбивается на ряд подобластей 0m, U = 2Л, Л ®т = 0» т=1, 2, ..., М. Коллектив решающих Праги	т
вил {/?} состоит из решающих правил Ri, Z=l, 2, ..., L. В каждой из областей 0m, m=l, 2, ..., М, отыскивается наиболее компетентное решающее правило, для чего в них вводятся коэффициенты компетентности vim, характеризующие компетентность Z-ro правила в m-й области.
Эти коэффициенты получаются в результате обучения, которое реализуется следующим рекуррентным соотношением:
=	о-22)
где vrim — коэффициент компетентности Z-ro правила в m-й области на r-м шаге обучения; 6>0, в частном случае 6=1; orzm = l, если Z-e правило правильно распознает ситуацию Xre0m; orzm =— 1, если Z-e правило ошибочно распознает эту ситуацию; orzm = 0, если Х^0т.
Решением коллектива на r-м шаге обучения будет решение правила с номером Zr, коэффициент компетентности которого к этому шагу в области 0т максимален, причем Хге0т, т. е.
Хг€=Лу=>Яг (X'), если v^w = maxv^; Х'(=9Ш. (1.23)
Относительно сходимости этого мера, определяемого по (1 23), к
Рис. 1.11. Структурная схема специализированного вычислительного устройства, 26
алгоритма, т. е. сходимости иономеру правила, действительно наиболее компетентного в этой области, легко доказываются соответствующие теоремы.
Метод априорного задания областей компетентности требует для своей реализации хранить в памяти вычислительной машины границы областей 0m, т=1, 2,..., М и соответствующие этим областям номера наиболее компетентных решающих правил. Это создает возможность реализации этого алгоритма в специализированном ' вычислительном устройстве. Структурная схема такого специализированного устройства может иметь вид, изображенный на рис. 1.11.
Это дает данному алгоритму определенные преимущества перед алгоритмами, рассмотренными в предыдущем параграфе, однако при увеличении числа областей М и размерности пространства признаков объем памяти, требуемой для его реализации, быстро возрастает.
Кроме того, данный алгоритм использует только аппроксимирующие особенности самих правил — членов коллектива. В следующей главе будет показано, что эффект коллектива заключается не столько в аппроксимирующих особенностях самих правил, сколько в аппроксимирующих особенностях работы алгоритма верхнего уровня — алгоритма обучения распознаванию областей компетентности решающих правил.
Теперь обратимся к экспериментальному исследованию высказанных утверждений и предложенных алгоритмов.
1.4. ЭКСПЕРИМЕНТЫ С КОЛЛЕКТИВОМ НА МОДЕЛЬНЫХ ЗАДАЧАХ
Эксперименты по обучению коллектива решающих правил проводились на следующей модельной задаче. Рассматривался случай дихотомии — разделение области определения множеств на две непер есекающиеся части А1 и Д 2, Aif]A2=0. Объекты, подлежащие
распознаванию, описываются в трехмерном пространстве векторами Х={Х1, х2, х3}. Каждый признак может принимать целочисленные значения из интервала [0, 10], т. е.	р=1, 2,3. Область
определения множеств Ai и А2 представляет собой куб. В качестве разделяющей поверхности выбран кусок сферы, пересекающей этот куб. Уравнение разделяющей поверхности и решение, принимаемое с его помощью, определяются следующим образом:
Рис. 1.12. Модельная задача (1.24), (1.25).
Q (X) = (Xi—5) 2+ (х2— 13) 2+ (х3—5)2— 100 = 0;	(1.24)
|ХеАп если Q(X)>0;
(ХеА2, если<2(Х)<0.	'
Эта модельная задача иллюстрируется на рис. 1.12.
В дальнейшем для унификации программирования во всех задачах область определения множеств Аь /=1, 2, ..., /, заданная в виде гийерпараллелепипеда, стягивается в n-мерный единичный гиперклуб с помощью стандартной нормировки:
%р Xptnin р ~	;
л, ртах	Я'ртт
(1.26)
В коллектив решающих правил включались линейные правила следующего вида:
(п	\
2 rftpXp-d/o jXz=O, / = 1. 2......£; />=1,2,3;
р=1	/
если fi (X)	0;
X S Аг, если fl (X) < 0.
3*
(1.27)
(1.28)
27
Здесь —знак /-го решающего правила. Коэффициенты й знаки правил — членов коллектива задавались случайным образом. Вопрос генерации таких правил будет подробно рассмотрен в следующей главе.
Исследовались коллективы, состоящие из пяти решающих правил (1.27), (1.28), т. е. L=5. Для получения достоверных результатов исследовалось несколько коллективов, каждый из которых обучался на трех различных обучающих последовательностях объемом 7=100. Качество обучения проверялось на пяти контрольных последовательностях объектов того же объема.
Таблица 1.1
Алгоритм А	Алгоритм Б	Алгоритм Г
0,108^0,012	0,081^0,006	0,124^0,020
При исследовании метода априорного задания областей компетентности, рассмотренного в § 1.3 этой главы, использовалось следующее априорное разбиение пространства признаков или области определения разделяемых множеств Ai и А2. Каждый признак делился на две части: 0^хр<5 и 5^хР^10, число областей равнялось восьми, так как р = 3.
Обучение коллективов решающих правил проводилось с помощью трех алгоритмов: алгоритма А — алгоритма восстановления плотности распределения вероятностей компетентности решающих правил; алгоритма Б — алгоритма восстановления потенциальных поверхностей компетентности; алгоритма Г — метода априорного задания областей компетентности решающих правил. Метод, основанный на алгоритме Фикса — Ходжеса (алгоритм В), на данной модельной задаче не исследовался. В табл. 1.1 приведены усредненные сравнительные результаты обучения коллективов линейных решающих правил тремя указанными алгоритмами. Критерием качества, как уже упоминалось, является вероятность ошибки распознавания на контрольной последовательности.
Лучшие из исследовавшихся коллективов дали результаты, приведенные в табл. 1.2.
Таблица 1.2
Алгоритм А	Алгоритм Б	Алгоритм Г
0,090	0,071	0,097
Из таблиц видно, что алгоритм Б обеспечивает наилучшее качество обучения коллектива линейных решающих правил. Критерий вероятности ошибки распознавания считается определяющим при сравнительном анализе этих алгоритмов, хотя в вычислительном смысле алгоритм Б уступает другим при малых размерностях пространства признаков Оп. К вычислительным трудностям или затратам относятся время обучения и объем памяти вычислительной машины, занимаемый программой и информацией.
Характеристика		Алгоритм А
Число операторов FORTRAN-npo-граммы		271
Объем памяти, занимаемый обучаю-щей последовательностью (машинных схов), п = 3		300
Информация, необходимая для экзамена, — результаты обучения		Матрица {p(xr/Bi)}. Вектор {Р(В[)} г = 1, п, 1=1, L
Объем памяти, занимаемый ре-зультами обучения (машинных слов)	п	470
	3	
	10	1555
	20	3105
Среднее время рбучения, мин, л=3		3,5
Таблица 1.3
	Алгоритм Б*	Алгоритм В	Алгоритм Г
	276	501	179
	300	300	300
	Обучающая последовательность. Величины 4 = 1, I	Обучающая последовательность	Границы областей 0m, т = 1, М. Таблица соответствий номеров области и правила
	1315	315	71
	2050	1050	27 628
	3100	2100	6 062 180
	8—12	Время, затрачиваемое на ввод данных	5—10
В табл. 1.3 приводятся примерные характеристики вычислитель» ных затрат при реализации каждого из предложенных алгоритмов для случая L = 5, I—100 и п=3, 10, 20. Приведены также вычислительные затраты при реализации метода Фикса — Ходжеса для построения областей компетентности. При определении затрат на реализацию алгоритма В принималось, что для образования областей 0т, т—\, 12, ..., М, каждый признак разбивался на две части, т. е. М = 2п.
Характеристики, приведенные в табл. 1.3, получены при реализации предложенных алгоритмов на ЭВМ GE-415. Из таблицы можно сделать ряд важных выводов. При реализации алгоритма Г необходимо задаваться числом подобластей 0™, т—1, 2, ..., М, поскольку при образовании этих подобластей разбиением каждого при-
знака всего на две части их число М=2п быстро растет с увеличением размерности пространства. Уже при сравнительно небольших размерностях число подобластей хачинает превышать все разумные пределы и для запоминания их параметров требуется объем памяти, значительно превышающий допустимые границы оперативной памяти вычислительной машины.
Наименьшие затраты свойственны алгоритму Фикса—Ход-
жеса, поскольку при его реализа-
Рис. 1.13. Зависимость Р= ции практически отсутствует про-= ф(£).	цедура обучения, в памяти хра-
нятся только обучающая последовательность и параметры решающих правил. Время обучения складывается из затрат на ввод обучающей последовательности. Что же касается алгоритма, основанного на байесовом решающем правиле,— алгоритма А, то при небольших размерностях он имеет определенные преимущества перед алгоритмом Б, основанном на методе потенциальных функций, однако, как уже упоминалось, в этом алгоритме необходимо параллельно решать задачу оптимального квантования каждого признака, что является источником ошибок. В эксперименте каждый признак квантовался на 10 интервалов. При более мелком квантовании оценки распределений будут более точными, однако это требует увеличения обучающей последовательности и резкого
возрастания вычислительных затрат.
Далее в экспериментах исследовалась зависимость вероятности ошибок распознавания Р от порядка коллектива L. Эксперименты проводились на той же задаче с помощью алгоритма Г. Полученные результаты иллюстрируются рис. 1.13.
Как и ожидалось, вероятность ошибки распознавания Р асимптотически убывает с увеличением порядка коллектива L. Вместе с тем уменьшаются и дисперсии вероятности ошибки. Для каждого значения L исследовалось 10 коллективов случайных линейных решающих правил. Полученный результат легко объясняется тем, что с увеличением L увеличивается вероятность попадания в коллектив «хороших» правил.
Экспериментально исследовался и вопрос сходимости алгоритма В. На рис. 1.14 изображен пример, иллюстрирующий сходимость
30
алгоритма в одной из подобластей. Из рисунка видно, что после 12-го шага выделяется одно компетентное решающее правило Т?4 (здесь точками обозначены правила, имеющие максимальное значение коэффициента компетентности).
Эта же модельная задача была решена и с помощью ряда известных методов распознавания образов: а) метода минимума расстояния до средних; б) метода Байеса; в) метода потенциальных функций. Эти алгоритмы в свою очередь объединялись в коллектив, который обучался с помощью алгоритма Б. Результаты, приведенные в табл. 1.4, свидетельствуют о достоверном преимуществе предлагаемого подхода перед традиционными Алгоритмами распознавания. Для корректности сопоставления результатов эксперимента указанные алгоритмы обу-

0
2
6
8
10
12
74
16
18
20
Рис. 1.14. Пример, иллюстрирующий сходимость алгоритма Г.
чались на той же обучающей последовательности, что и коллектив
этих алгоритмов.
Таблица 1.4
Метод минимума расстояния до средних	Метод потенциальных функций	Метод Байеса	Коллектив алгоритмов
0,079+0,010	0,076+0,007	0,069+0,004	0,059+0,003 1
Предложенный подход имеет преимущество и перед алгоритмом голосования, который также может быть использован при принятии
Таблица 1.5
№ п/п.	Коллектив		Ra
1	0,081+0,010	0,334+0,021	0,170+0,043
2	0,080+0,013	0,400+0,050	0,610±0,043
3	0,085+0,016	0,386+0,059	0,200±0,040
4	0,089+0,013	0,510+0,047	0,380+0,045
5	0,071+0,012	0,390±0,040	0,406±0,045
31
Продолжение табл. 1.5
Nb п/п.	Rs	R<	Rs
1	0,480+0,063	0,386+0,059	0,348+0,062
2	0,640+0,046	0,371±0,068	0,610±0,053
3	0,374+0,063	0,610±0,053	0,164+0,043
4	0,408+0,062	0,210+0,048	0,398+0,048
5	0,466+0,061	0,622+0,032	0,616+0,045
коллективного решения. Голосование между указанными алгоритмами дает следующую вероятность ошибки распознавания: 0,076+0,008. Кроме того, исключительно важный факт состоит в том, что предложенный способ организации коллективного решения имеет преимущество и перед лучшими из алгоритмов или правил, включенных в этот коллектив. Об алгоритме голосования этого сказать нельзя, так как легко можно придумать ситуации, когда голосование ухудшает результат лучшего из правил. Указанный эффект обучения коллектива иллюстрируется и в табл. 1.5 на примере коллективов линейных решающих правил.
Как видно, качество коллектива значительно выше любого из его членов, даже самого лучшего. Голосование здесь дает тот же порядок ошибки, что и среднее голосующее правило.
ГЛАВА ВТОРАЯ
СИНТЕЗ ОПТИМАЛЬНОГО КОЛЛЕКТИВА
РЕШАЮЩИХ ПРАВИЛ
2.1. ЗАДАЧА ОПТИМИЗАЦИИ КОЛЛЕКТИВНОГО РЕШЕНИЯ
Не вызывает сомнений тот факт, что собранный наугад коллектив решающих правил будет содержать и некомпетентные, и малокомпетентные члены или решающие правила. Нужно попытаться заменить эти правила на более компетентные. Для этого прежде всего должна существовать возможность выбора новых членов коллектива из некоторого множества решающих правил, т. е. должен существовать генератор решающих правил В дополнение к этому следует, очевидно, иметь правило замены старых правил новыми. Процедуру оптимизации коллектива, которая состоит в подобной замене, следует называть селекцией.
Будем различать правила, для которых характерна широкая область компетентности, и правила, обладающие исключительно узкой областью компетентности. Первые условно можно называть эрудитами, вторые — узкими специалистами,
3?
Эффективность работы каждого решающего правила I— — 1, 2, ..L, можно оценить с помощью следующих двух критериев:
1. Средний вклад l-го решающего правила, т. е. доля объектов, распознаваемых этим правилом как наиболее компетентным,
ai^nJN, /=1, 2.....£,	1(2.1)
где ni — число объектов контрольной последовательности, попадающих в область компетентности /-го решающего правила; N— число ситуаций контрольной последовательности. Эта величина показывает, насколько часто решение /-го решающего правила отождествляется с решением всего коллектива, т. е. S = Нетрудно заметить, что правилам — эрудитам свойственно высокое значение среднего вклада щ, а узким специалистам — малое. Однако данный критерий неполностью характеризует качество работы решающего правила как члена коллектива..Введем еще один критерий.
2. Частотная оценка вероятности правильного распознавания l-м решающим правилом при условии, что оно является компетентным:
pi=*tnilnit /=1, 2, ..., L,	(2.2)
где mi — число объектов, правильно распознанных /-м решающим правилом, когда оно выделялось как компетентное. Очевидно, и правилам — эрудитам, и правилам — узким специалистам должно быть свойственно высокое значение этой величины. Следует сказать, что этот критерий позволяет проследить, как увеличивается вероятность правильного распознавания /-м решающим правилом, если оно принимает решение не во всем пространстве признаков, а только в свойственной этому правилу области. Этим частично объясняется эффективность коллектива.
С учетом введенных критериев задачу селекции, т. е. задачу синтеза оптимального коллектива правил, можно формулировать как многокритериальную задачу с 2L критериями:
ai -► шах;	(2.
eV
pl -* max, / = 1,2,	(2.4)
{Ri}&
где V — множество допустимых решающих правил, генерируемых для селекции.
Сведем эту задачу к однокритериальной путем введения некоторого обобщенного критерия. В данном случае такой критерий существует и легко выражается через локальные (2.1), (2.2). Это вероятность ошибки распознавания коллективом правил, которую следует минимизировать:
Р-* min ;	(2.5)
Wev
L	L
(2.6)
Z=1	/=1
33
Г'Де tii — показатель абсолютного вклада /-го решающего правила в работу коллектива или престижность решающего правила. Задачу оптимизации (2.5) можно иначе записать следующим образом:
L
V CLipi-^ max .	(2.7)
/=1
Решение поставленной задачи зависит от вклада в работу коллектива правил — эрудитов и правил — узких специалистов и качества распознавания этими правилами в своих областях компетентности.
Однако задача селекции остается многокритериальной, поскольку к задаче минимизации (2 5) добавляется еще и требование минимума числа решающих правил — членов коллектива.
£-> min ,	(2.8)
{Ri}&
которое нельзя не учитывать и которое позволяет, например, отдавать предпочтение коллективу меньшего порядка при равном значении вероятности ошибки распознавания. Это же условие позволяет исключать из коллектива одинаковые решающие правила.
2.2. ЭВРИСТИЧЕСКИЙ АЛГОРИТМ СЕЛЕКЦИИ
Будем искать алгоритм селекции в множестве эвристических алгоритмов. Под эвристическим алгоритмом здесь понимается последовательное применение неформальных приемов — эвристик, позволяющее решить поставленную задачу. Эвристика в свою очередь определяется [73] как правило, стратегия, метод или прием, используемые для повышения эффективности системы, которая пытается найти решение сложных задач.
Для решения поставленной задачи, т. е. синтеза оптимального коллектива, следует определить элементарные эвристики. Пусть Е= = {ei, в2, ..., ег} — множество таких элементарных эвристик. Алгоритм селекции А будет представлять собой правила перехода от одной эвристики к другой: А=А(£). Тогда решение поставленных задач (2.5), (2.8)—оптимальный коллектив {R} * — является результатом приложения алгоритма А(Е) к этим задачам, т. е.
Л (Е)
Р, £ -> min => {/?}*.	(2.9)
Коротко рассмотрим множество используемых эвристик Е. На каждом шаге процедуры селекции ситуация определяется величинами pft, Lk, ahif pkv, /=1, 2, ..., L, где верхний индекс k является номером шага селекции. Выбираемые при этЛи эвристики определяются в зависимости от поведения указанных величин Кроме того, фиксируются ограничения снизу на величины сц и pi в виде атгп и ртгп. В табл. 2 1 приведены возможные типы поведения величин Рк и Lk и соответствующие каждой ситуации z эвристики. Определяющим критерием является вероятность ошибки распознавания Р. 34
Ситуация	Характер поведения	
	pk	Lk
	pk p*k	Любой
^2	Pk > p*k	Любой
*8	Pk = p*k	Lk < L*k
	pk p»k	Lk > L\
Zb	p*k^pk^pk+^_...	Любой
Таблица 2.1
Проверка на ограничения	Эвристики
а^1 amin или Р^1 < Pmin.	
Независимо от ограничений	e2:/^:=>/?j+', если
amin или Pl ^Pmin	01
Независимо от ограничений	
То же	^.Rk+l^R'l
В таблице приняты следующие обозначения:
p*k==minptt /= 1, 2,	1,	(2.10)
т. е. P*k — вероятность ошибки распознавания наилучшим из исследовавшихся к £-му шагу селекции коллективов; L*k — порядок этого коллектива.
Эвристика ei применяется при уменьшении величины Ph, т. е. при Ph<ZP*k, и произвольном поведении величины Lh. При этом заменяются те решающие правила, для которых нарушены ограничения на величины ai и pi. Эти ограничения атгп и ртгп связаны с тем, что в коллективе не должно быть правил со слишком малой областью компетентности и правил, которые в своей области работают недостаточно качественно.
Эта эвристика имеет достаточно простой содержательный смысл: использование в коллективе слишком узких специалистов, а также не слишком надежных не дает должного эффекта, к их помощи прибегают слишком редко, чтобы оставлять их в коллективе. Замеца решающих правил в таблице обозначается следующим образом:
Если вероятность ошибки распознавания коллективом в результате введения новых правил возрастает:	то применяется
эвристика е2, состоящая в том, что правила, введенные на предыдущем шаге, заменяются другими. Это означает, что специалисты, ухудшающие работу коллектива, должны быть заменены.
Эвристика вз восстанавливает коллектив, для которого справедливо выражение (2.10). Она применяется после остановки процедуры селекции, критерием чего служит число шагов g, на которых вероятность ошибки распознавания не уменьшается. Когда величина Pk не меняется, алгоритм следит за поведением величины Lk, в зависимости от чего применяются эвристики ei и е2 (ситуации z3 и z4 соответственно).
Приведенные в табл. 2.1 эвристики ни в коем случае не ограничивают расширение этого множества другими разумными приемами, позволяющими улучшить качество распознавания коллективом. При наступлении ситуации z5, когда селекция считается законченной, можно попытаться улучшить качество работы коллектива за счет исключения решающих правил, для которых величины ai, и особенно pi, достаточно малы. В силу того, что при оценке компетентности решающих правил могут иметь место ошибки (как и в любой процедуре распознавания), такая эвристика, исключающая узкоспециализированные компетентные правила, может привести к успеху.
Вообще говоря, любую эвристическую процедуру можно считать законченной, если никакие эвристики не улучшают решения задачи, в данном случае не уменьшают критерия качества Р обучения коллектива.
Когда исследуются коллективы неформализованных решающих правил — специалистов, эвристики должны быть более гибкими ввиду того, что ограничены возможности введения в коллектив новых членов. Вопросы, касающиеся подобных коллективов обсуждаются в гл. 4.
Следует добавить, что полученный в результате селекции оптимальный коллектив {/?*} обладает обычно оптимальным разнообра-36
г		2i	za	Z2
k		1	2	3
Р*		0,078	0,078	0,100
р		0,656	0,656	0,002
	Pi	0,910	0,910	1,000
D	^2	0	0	0,218
^2	Pi	0	0	0,878
n	аз	0,240	0,240	0
”з	Рз	0,924	0,924	о
D		0	°	0,780
	Pi	0	°	0,907
P	. <h	0,094	0,094	°
	Рз	1,000	1,000	0
Таблица 2.2
z2	2з	21	Z3	21	21	2з
4	5	6	7	8	9	10
0,104	0,078	0,072	0,072	0,044	0,038	0,038
0,398	0,656	0,646	0,646	0	0	0
0,966	0,910	0,926	0,926	0	0	0
0,442	0	0	0	0,976	0,478	0,478
0,795	0	0	0	0,959	0,963	0,963
0,066	0,240	0,028	0,028	0	0,516	0,516
1,000	0,924	1,000	1,000	0	0,965	0,965
0,092	0,094	0	0	0,024	0,006	0,006
1,000	1,000	0	0	0,893	0,667	0,667
0	0	0,326	0,326	0	0	0
0	0	0,928	0,928	0	”	0
Продолжение табл. 2.2
2		Z,	2а	Хз	Хз	Хз	Zs	z3	Хз	Хз	Хз
k		11	12	13	14	15	16	17	18	19	20
pk		0,034	0,034	0,034	0,034	0,034	0,034	0,034	0,038	0,038	0,034
	/21	0	0	0	0	0	0	0	0,196	0	0
	Pl	0	0	0	0	0	0	0	0,948	0	0
D	/22	0,465	0,465	0,465	0,465	0,465	0,465	0,465	0,386	0,386	0,465
л2	Рг	0,964	0,964	0,964	0,964	0,964	0,964	0,964	0,956 1	1	0,956	0,964
D	/23	0,476	0,476	0,476	0,476	0,476	0,476	0,476	0,418	0,418	0,476
л8	Рз	0,967	0,967	0,967	0,967	0,967	0,967	0,967	0,970	0,970	0,967
D	а4	0	0	0	0	0	0	0	0	0,196	0
	Pl	0	0	0	0	0	0	0	0	0,948	0
П	аб	0,080	0,080	0,080	0,080	0,080	0,080	0,080	0	0	0,080
^5	Рб	0,973	0,973	0,973	0,973	0,973	0,973	0,973	0	0	0,973
Рис. £.1. Пример совпадения областей компетентности.
зием [51]. Очевидно, что правила, составляющие коллектив, не должны быть слишком похожими, например в смысле близости их разделяющих поверхностей или коэффициентов при одинаковых структурах правил. Области компетентности правил в этом случае совпадают, как это изображено на рис. 2.1 (области и В3). В жет служить, например, среднее
качестве меры разнообразия мо-значение расстояния между точ-
ками, соответствующими этим правилам в некотором пространстве правил. Если вырожденный коллектив состоит только из одного решающего правила, то оптимальное разнообразие его будет равно нулю.
В случае слишком большого разнообразия эффективность обучения коллектива также снижается. Допустим, исследуются коллективы случайных линейных решающих правил вида (1.27), (1.28). В силу случайности этих правил представляется целесообразным дополнить алгоритм селекции коррекцией выделенных правил, незначительной вариацией их коэффициентов. По-видимому, коррекцию каждого решающего правила следует вести в некоторой окрестности точки, соответствующей этому правилу в пространстве правил Dn+i.
2.3. ЭКСПЕРИМЕНТЫ НА МОДЕЛЬНЫХ ЗАДАЧАХ
Для иллюстрации работы алгоритма селекции коллектива ре-
шающих правил использовалась модельная задача, подробно описанная в § 1.4. В коллектив объединялось пять случайных линейных
Рис. 2.2. Эксперимент на модельной задаче (§ 1.4).
селекции коллектива позволяет
решающих правил вида (1.27), (1.28). Объем обучающей последовательности составлял 100 ситуаций, объем контрольной — 500. В табл. 2.2 и на рис. 2.2 приведены результаты применения предложенной эвристической процедуры селекции для решения данной модельной задачи.
В табл. 2.2 двойной чертой || отмечены те правила, которые заменяются на следующем шаге селекции. В качестве ограничений были выбраны: а„ип—$, Rmin— =0,8.
Из рис. 2.2 видно, что для данной задачи описанная процедура более чем вдвое уменьшить вероят-
ность ошибки распознавания таким коллективом линейных правил. Это происходит уже к 11-му шагу, причем порядок коллектива также уменьшается до трех правил. Полученный оптимальный коллектив {R} * состоит из правил, которым соответствуют следую-
39
щие уравнения:
f2 (X) = - 0,31х2 + 1 = 0;	1
f3(X) = — 0,55х2 + 0,17х3 + 1 = 0; ?	(2.11)
f6 (X) = 0,17xt — 0,55х2 +1=0.	'
Как уже упоминалось в гл. 1, на этой же модельной задаче исследовались возможности некоторых простых алгоритмов распознавания образов. Сравнительные результаты работы этих алгоритмов и коллектива, полученного в результате селекции, приведены
в табл. 2.3 и свидетельствуют о преимуществе последнего. Селекция велась на одной последовательности, а результаты в табл. 2.3 усреднены по нескольким экспериментам.
Таблица 2.3
Метод минимума расстояний до средних	Метод потенци-альных^функций	Метод Байеса	Коллектив из 3-линейных правил (2.11)
0,079±0,010	0,076+0,007	0,069+0,004	0,037+0,006
Условия второй модельной задачи, на которой проверялась эффективность процедуры селекции, отличались от первой лишь характером разделяющей поверхности и порядком коллектива. Уравнение разделяющей поверхности в этой задаче было выбрано в виде
Q (X) = (х,—5) 2+ (х2-5) 2+ (х3-5)2—20=0	(2.12)
(рис. 2.3). Решающее правило определяется согласно (1.25).
Линейные решающие правила генерировались случайным образом.
Порядок коллектива равнялся восьми. Объем обучающей последовательности, как и ранее, составлял 100 реализаций, контрольная последовательность состояла из 500 реализаций обоих классов. Результаты применения процедуры селекции приведены на рисунке 2.4 и в табл. 2.4.
40
1107
	z	Z>	21	?2	2a
	k	1	2	3	4
	Pk	0,334	0,140	0,214	0,152
Rl	al Pl	0 0	0 0	0,046 0,870	0,130 0,677
Rs	<22 P2	0 0	0 0	0,540 0,622	0 0
R,	аз Рз	0 0	0,014 1,000	0 0	0 0
R*	ai Pi	0,212 0,453	0,612 0,964	0,190 1,000	0,470 0,953
R„	a5 Pi	0,138 0,304	0,034 0,832	0 0	0 0
R,	at Pt	0,120 1,000	0 0	0,014 1,000	0,368 0,799
R,	ai Pi	0,292 0,986	0 0	0 0	0 0
Rs	CL^ Pt	0,238 0,504	0,340 0,671	0,210 0,981	0,032 0,562
Таблица 2.4
J	2а	21		2«	21	2i	2i
1 5	6	7	8	9	10	11
| 0,236	0,118	0,114	0,120	0,162	0,158	0,108
1 0	0	0	0,082	0,006»	0,002	0,238
°	0	0	0,951	0,667.,	1,000	0,866
0	0,016	! 0,020	0	0,494	0	0,226
°	1,000	0,700	0	0,700	0	1,000
0,010	0	II 0,002	0	0	0	0,044
0,000	°	I 1,000	0	0	0	0,909
0,420	0,656	0,646	0,260	0,480	0,368	0
0,962	0,973	0,978	1,000	0,979	1,000	0
0,010	0,002	0,010	0,010	0,012	0,006	0
0,800	0	0,800	1,000	0,833	0,667	0
0	0	0,322	0,158	0	0	0,182
0	0	0,714	0,899	0	0	0,901
0,008	0,326	0	0,490	0	0,546	0,158
1,000	0,699	0	0,796	0	0,722	0,873
0,552	0	0	0	0,008	0,078	0,152
0,605	0	0	0	1,000	0,949	0,776
Продолжение табл. 2.Ф
г	Z1	2Я	2Я	2Я	Za	z2	Zi	z2	*2	23	Ze
k	12	13	14	15	16	17	18	19	20	21	22
р*	0,092	0,096	0,100	0,094	0,092	0,094	0,072	0,074	0,082	0,072	0,072
	0,274	0,294	0,250	0,340	0,340	0,340	0,302	0,282	0,268	0,302	0,302
р\	0,883	0,857	0,880	0,859	0,859	0,859	0,887	0,879	0,888	0,887	0,887
	0,222	0,196	0,180	0,226	0,224.	0,220	0,222	0,222	0,224	0,222	0,222
R* Рг	1,000	1,000	1,000	1,000	1,000	1,000	1,000	1,000	1,000	1,000	1,000
П	^7 •	0,038	0,044	0,034	0,046	0,042	0,046	0,042	0,042	0,042	0,042	0,042
р>	0,895	0,864	0,941	0,869	0,905	0,869	0,905	0,905	0,905	0,905	0,905
	0,052	0	0	0	0,008	0,006	0,042	0,024	0,036	0,042	0,042
л	0,846	0	0	0	0,750	1,000	0,905	0,917	0,944	0,905	0,905
D	^5	0,092	0,104	0,096	0	0	0	0	0,044	0,078	0	0
6 Pi	0,804	0,923	0,896	0	0	0	0	0,864	0,795	0	0
Г)	0,124	0,198	0,150	0,202	0,202	0,202	0,198	0,194	0,182	0,198	0,198
‘ р‘	0,919	0,899	0,920	0,901	0,901	0,901	0,909	0,918	0,901	0,909	0,909
г>	1	0,162	0,164	0,154	0,186	0,184	0,186	0,178	0,178	0,154	0,178	0,178
*’ Pl 1	0,914	0,878	0,909	0,892	0,902	0,892	0,933	0,933	0,922	0,933	0,933
D	^8	0,036	0	0,136	0	0	0	0	0,016	0,014	0,016	0,016
*« А |	0,833	0	0,765	0	0	0	0	1,000	1,000	1,000	1,000
В результате селекции был получен коллектив, состоящий из семи линейных решающих правил, определяемых следующими уравнениями:
f, (X) = 0,478%, + 0,342хг — 0,810х3 — 1; f2(X) = — 0,1 Их, —0, 138х2 +0,950х3 + 1;
f, (X) = — 0,462х, — 0,257х2 + 0,351х3 + 1; f4 (X) = — 0,001х, + 0,025х2 — 0,289х3 + 1;
fe (X) = 0,020х, — 0,791х2 + 0,539ха— 1; f,(X)= — 0,761х, —0,060хг + 0,122х3+ 1; f8(X) = — 0,123х, —0,123хг —0,123х3+ 1. .
(2.13)
Селекцию в этой задаче можно разделить на два этапа: на первом ограничения были те же, что и в первой модельной задаче; с 12-го шага наступал второй этап с ргпгп=0,85. Это связано с тем, что при &=12 L12 = 8,/?z12> Ptnin. а\2 ат{Пд,ля всех /=1, 2, ..., 8. Вероятность ошибки распознавания коллективом после применения селекции уменьшилась более чем в 4 раза и составила 0,072.
В следующем параграфе делается попытка объяснения эффекта существенного уменьшения ошибки распознавания, возникающего при применении коллектива решающих правил.
2.4. АНАЛИЗ АППРОКСИМАЦИОННЫХ СВОЙСТВ РАБОТЫ КОЛЛЕКТИВА
Можно было предположить, что эффективность предложенного подхода объясняется тем, чго осуществляется обычная кусочная аппроксимация разделяющей поверхности, где каждой области или ряду областей соответствует определенное решающее правило из членов коллектива.
Однако обычную кусочную аппроксимацию можно получить более простыми и дешевыми средствами. На практике же, даже при решении сложных нелинейных задач распознавания, получали удовлетворительные результаты с помощью коллективов линейных решающих правил невысокого порядка. Так, например, в модельной задаче, описанной в § 1.4, оптимальный коллектив состоит всего из трех правил. В связи с этим возникла гипотеза, что работа коллектива не ограничивается простой аппроксимацией разделяющей поверхности.
Для подтверждения этого предположения был поставлен следующий простой эксперимент. Модельная задача, изображенная на рис. 2.3, решалась двумя способами. Во-первых, разделяющая поверхность аппроксимировалась восемью плоскостями, т. е. октаэдром. С помощью метода Монте-Карло было получено, что наилучшая кусочно-линейная аппроксимация сферы (аппроксимация октаэдром) осуществляется с ошибкой, равной 0,0826, эквивалентной ошибке распознавания. Во-вторых, был организован коллектив двух линейных решающих правил следующего вида:
fi(X) =х2=0; Ri: S<=Ai;	(2.14)
fa(X) =Х2—10 = 0; R2: Sg=A2,	(2.15)
4*	43
Рис. 2.5. Работа коллектива двух линейных решающих правил на модельной задаче (2.12).
каждое из которых относит всю область определения разделяемых множеств S к одному из классов >41 или Л2, как это показано на рис. 2.5. Коллектив этих двух правил решает данную модельную задачу с вероятностью ошибки, равной 0,072, при этом коллектив обучается с помощью алгоритма потенциальных функций. Получено наглядное свидетельство того, что характер аппроксимации коллективом отличен от линейного. Нетрудно заметить, что в данном примере разделяющая поверхность между множествами А\ и Л2 аппроксимируется разделяющей поверхностью между областями ком
петентности двух решающих правил. Этот же случай рассматривался в § 1.1. Эта поверхность, в силу того, что для обучения распознаванию областей компетентности использовался метод потенциальных функций, нелинейна. Очевидно, что возможность кусочной аппроксимации в коллективе полностью игнорировать не следует.
Таким образом, можно считать, что высокое качество распознавания коллективом решающих правил достигается благодаря двум указанным механизмам его работы. Если область компетентности решающего правила пересекается куском истинной разделяющей по-
верхности между множествами, то этот кусок аппроксимируется правилом, соответствующим этой области. Если же два решающих правила лежат по разные стороны от куска разделяющей поверхности, то он (этот кусок) в силу нелинейности алгоритма обучения коллектива аппроксимируется нелинейной разделяющей поверхностью между областями компетентности этих правил.
В заключение проиллюстрируем оба эти механизма работы коллектива на модельном примере. Пусть в двумерном пространстве признаков заданы два множества и Л2, уравнение разделяющей поверхности между которыми имеет вид:
(0,3 + Xj — х2 = 0, если %! =^0,4;
Q = I (xt — 0,6)2 + (х2 — 0,8)2 — 0,2 = 0, еслиХ > 0,4,
(2.16)
и изображена на рис/ 2.6,а сплошной линией. Область определения множеств Ai и Л2— единичный квадрат. Коллектив решающих правил состоит из правила, совпадающего с линейным участком разделяющей поверхности Q(X):
^(Х)=0,3+х!—х2=0;
Г,(Х)^о.
Ь (X) < о,
Х(=А; хеЛ,
(2.17)
и правила, целиком относящего область определения множеств S к классу Аг:
fa(X)==-x2=0; J?2: 3(=Л2.	(2.18)
Разделяющие поверхности, соответствующие правилам и Изображены на рис. 2.6,а штрихпунктиром.
44
Для обучения этого коллектива также применялся алгоритм потенциальных функций. Обучающая последовательность состояла из 100 случайно генерируемых точек, для контроля предъявлялось 10 000 реализаций. По данным обучения строились области компетентности решающих правил, изображенные на рисунке 2.6,6. На рисунке 2.6,в изображена разделяющая поверхность, восстановленная коллективом правил (пунктирная линия), заштрихована область ошибочного распознавания. Из рисунков легко можно видеть, как
Рис. 2.6. Аппроксимационные особенности работы коллектива.
линейный участок разделяющей функции (2.16) аппроксимируется совпадающим с ним участком решающего правила (2.17). Нелинейный же участок аппроксимируется разделяющей поверхностью между областями компетентности. Коллектив из двух линейных правил (2.17) и (2.18) решает эту задачу с вероятностью ошибки, .равной 0,0393. Алгоритм потенциальных функций с вероятностью 0,0826, т. е. значительно хуже.
ГЛАВА ТРЕТЬЯ
РАСПОЗНАВАНИЕ ОБЛАСТЕЙ СТАТИЧЕСКОЙ УСТОЙЧИВОСТИ С ПОМОЩЬЮ КОЛЛЕКТИВА
3.1.	ПОСТАНОВКА ЗАДАЧИ ПРОГНОЗА НАРУШЕНИЙ СТАТИЧЕСКОЙ АПЕРИОДИЧЕСКОЙ УСТОЙЧИВОСТИ РЕЖИМА РАБОТЫ ЭНЕРГЕТИЧЕСКОЙ СИСТЕМЫ
В настоящее время в Советском Союзе ведутся работы по созданию автоматизированных систем диспетчерского управления (АСДУ) режимами работы объединенных электроэнергетических систем (ОЭС) [19, 27, 72, 75]. На первом этапе разработки АСДУ вычислительная техника привлекается для помощи диспетчерскому персоналу, управляющему режимом ОЭС, как в реальном масштабе времени, так и в качестве ассистента в режиме диалога «человек — машина». Дело в том, что сложные ситуации, возникающие при управлении нормальными и послеаварийными режимами, когда необходимо выявить возможные незапланированные режимные ограничения и принять оптимальное решение, обеспечивающее экономичную и надежную работу ОЭС, требуют переработки значительной информации, для чего и используется ЭВМ.
45
Одно из основных ограничений в энергетической системе связано с обеспечением необходимых запасов по условиям сохранения статической апериодической устойчивости (САУ) ОЭС. В настоящее время в практике эксплуатации электрических систем нормирование уровня САУ, как правило, осуществляется детерминированным заданием граничных значений по перетокам активной мощности по линиям электропередачи (ЛЭП) и напряжениям в тех или иных узловых точках сети.
Однако режимы работы современных ОЭС в значительной степени подвержены влиянию случайных воздействий. Показатели уровня (запаса) устойчивости ОЭС изменяются в зависимости от состава оборудования, схемы электрической системы, параметров текущих режимов и имеют случайную природу.
В этих условиях становится актуальной задача разработки в рамках АСДУ моделей, отражающих статические связи между показателями уровня САУ и параметрами (независимыми переменными, признаками), определяющими режим работы ОЭС. Такие модели позволили бы диспетчерскому персоналу оценивать уровень устойчивости как в реальном масштабе времени, так и в ожидаемых будущих режимных ситуациях, выработать решения, обеспечивающие сохранение САУ в системе. Кроме того, с их помощью возможна будет целенаправленная разработка мероприятий по повышению уровня САУ в ОЭС.
Для построения подобных моделей ранее использовались метод статистических испытаний и корреляционно-регрессионный анализ [18, 54]. Метод статистических испытаний требует проведения большого количества расчетов для статистической оценки уровня САУ в каждой режимной ситуации. Для его использования необходимо знание многомерных законов распределения переменных, поскольку, как правило, признаки коррелируют. Эффективность корреляционно-регрессионных методов зависит от соблюдения ряда довольно жестких требований, таких как, например, предположения о стационарности исследуемого случайного процесса, возможности описания моделируемой зависимости непрерывной функцией, предположения о нормальности совместного многомерного распределения признаков, использование только количественных непрерывно изменяющихся признаков и т. д.
При моделировании реальных условий функционирования ОЭС многие из указанных предпосылок не выполняются, а именно:
а)	имеет место нарушение стационарности исследуемого процесса вследствие, например, изменения состава оборудования ОЭС во времени, естественного роста электропотребления, ввода новых генерирующих мощностей;
б)	законы распределения признаков (например, суммарного потребления активной мощности систем, межсистемных перетоков активной мощности) отличны от нормальных;
в)	для адекватного описания исследуемого процесса в модели часто приходится учитывать качественные и дискретно изменяющиеся количественные признаки (например, бинарный признак состояния «включено» или «отключено» для той или иной ЛЭП, реактивное сопротивление эквивалентных схем замещения и др.).
Все это снижает точность моделей, приводит к необходимости частого их пересчета при практическом использовании и поэтому резко ограничивает сферу применения классических регрессионных моделей в практике управления режимами работы ОЭС.
46
Ьыла сделана попытка интерпретировать задачу построения й использования прогностической модели САУ ОЭС как задачу распознавания образов [1]. Методы распознавания образов свободны от большинства ограничений, присущих регрессионному анализу, и тем самым расширяют возможности адекватного моделирования исследуемых процессов.
Возможны различные варианты прогностических моделей САУ ОЭС в терминах распознавания образов. При постановке задачи будем исходить из следующих физических предпосылок.
В ОЭС принципиально возможны два варианта нарушения САУ. Во-первых, нарушение устойчивости может произойти при медленном (статическом) изменении режима, например, из-за перераспределения генерируемой мощности при неизменном потреблении системы. Однако на практике подобная ситуация не представляет угрозы, поскольку для нормальных режимов нормируется запас САУ не менее чем 20%, и в нормальных ситуациях диспетчерский персонал (с помощью соответствующих автоматических устройств) имеет возможность корректировать режим, сохраняя запас САУ практически неизменным.
Другим, наибоее важным для практики вариантом является нарушение САУ в послеаварийном режиме из-за системных аварий в ОЭС, например после отключения транзитных ЛЭП в результате короткого замыкания, отключения генераторов и др. Переход от доаварийного режима к послеаварийному в этом случае происходит за несколько секунд, и, если новый режим неустойчив, персонал не успевает осуществить мероприятия по улучшению режима.
На практике диспетчерский персонал интересует не вообще уровень САУ в предполагаемом аварийном режиме, а предельная пропускная способность определенных транзитных ЛЭП между системами ОЭС, на которые ложится основная часть дополнительной мощности, поскольку общесистемные аварии приводят к перераспределению потоков мощности по системообразующим ЛЭП. Общепринято значение протекающей мощности по исследуемым ЛЭП в подобных ситуациях в момент нарушения САУ называть предельной пропускной способностью по условиям сохранения САУ данных ЛЭП. Модели предельной пропускной способности межсистемных ЛЭП исследуются именно в этих послеаварийных ситуациях.
Специфичность рассматриваемой задачи состоит в том, что требуемая для разработки модели исходная информация может быть получена лишь расчетным путем с помощью специализированных программ для ЭВМ. Особенности расчетов САУ здесь подробно обсуждаться не будут, поскольку данная проблема рассматривается в достаточном количестве работ, например [75]. Отметим лишь следующее. Как известно, в указанных программах моделирование нарушения САУ в ОЭС осуществляется на основе последовательного утяжеления режима. В общем случае при сложной структуре связей в ОЭС значения предельных перетоков мощности по межсистемным ЛЭП зависят от условий утяжеления режима. Применительно к рассматриваемой ситуации утяжеление режима должно осуществляться за счет увеличения генерируемых мощностей на реальных или эквивалентных электростанциях на отправном конце исследуемых ЛЭП. Выбор же схемы замещения сети, электростанций, утяжеляющих режим, и порядок изменения их мощностей при расчетах решается на неформальном уровне с помощью информации о составе оборудования и топологии сети в нормальном и послеаварийном режимах,
47
реальных ограничениях По располагаемым йктйвньш и реактивный мощностям крупных электростанций, примыкающих к системообразующей сети объединения. И хотя указанный выбор неоднозначен, как правило, с достаточной точностью для практики может быть осуществлено моделирование предельных по условиям сохранения САУ перетоков мощности по исследуемой совокупности транзитных ЛЭП в заданном послеаварийном режиме.
Таким образом, для каждой начальной режимной ситуации формируются серия утяжеленных режимов и режим, соответствующий нарушению САУ системы. Проведя расчеты для различных исходных режимных ситуаций, имеем в общем случае вектор Y размерностью т значений перетоков мощностей у^ /=1, ..., т, протекающих по интересующей нас совокупности транзитных ЛЭП с номерами /:
¥=(//1, Уг, .... Ут)	(3.1)
и матрицу W размерностью пХт соответствующих значений признаков (режийных параметров) wtj, i=l, ...» /г; /=1, ..т, выбранных нами и определяющих предельную пропускную способность исследуемых ЛЭП (/г— число параметров, т — число линий):
Wil ...
wn\ ... wnm
Выбор исходной системы признаков решается на основе указанной выше информации о нормальных и аварийных режимах в ОЭС. Для оценки относительной важности признаков и затрат на их измерение могут использоваться всевозможные модификации метода экспертных оценок [24].
Очевидно, что не может существовать априорной формальной процедуры определения оптимальной системы признаков, обеспечивающей приемлемые точность, надежность и затраты на построение прогностической модели САУ ОЭС. Поэтому вначале целесообразно выбрать избыточную совокупность признаков, а затем в процессе построения модели ее минимизировать, т. е. определить систему так называемых информативных признаков. Выбор системы информативных признаков — одна из важнейших составных частей задачи построения модели пропускной способности межсистемных ЛЭП.
Введем в рассмотрение матрицу X и вектор Z размерностью соответственно (л-Н)Хт и т с элементами хц и Zj, образованными следующим образом. Элементу zj присваивается значение, равное — 1, если переток мощности yj соответствует нарушению САУ системы, и +1 — в противном случае. Матрица X образуется добавлением к матрице W строки /г+1, составленной из элементов вектора Y. Любой /-й столбец Xj=(wi;, w2j, ..., wnj, у}) матрицы X определяет ситуацию в системе, отображающуюся в точку в (/г4-1)-мерном евклидовом пространстве Йп+1.
Ситуации Xj, соответствующие элементам	—1, образуют
класс режимных ситуаций в ОЭС, при которых имеет место нарушение САУ. Обозначим указанный класс через А (Авария). Соответственно ситуации Xj с Zj = + 1 образуют класс, который обозначим через Н (Норма). Класс Н соответствует совокупности проме-48
жуточных нормальных стационарных режимов при расчетах пределов САУ в ОЭС.
После введенных определений можно четко сформулировать поставленную задачу в терминах задачи распознавания образов: задана выборочная совокупность X с ситуациями Xj, /=1, 2.... т,
принадлежность которых к различаемым множествам А и Н известна (с помощью вектора Z). Требуется на основе данной информации построить решающее правило в пространстве Qn+1, которое оптимальным образом с точки зрения выбранного критерия распознавания разделяет пространство Qn+1 на две области: А и Н.
Рассмотрим пример разработки модели пропускной способности ЛЭП по условиям сохранения САУ.
Рис. 3.1. Схема замещения части электроэнергетической системы.
Рассматривалась одна из реально функционирующих ОЭС. Обобщенная схема замещения ее части, состоящей из четырех систем: А, В, С, D, показана на рис. 3.1. Штрихпунктирными линиями условно объединены элементы, принадлежащие к одной и той же энергосистеме, штриховыми стрелками указаны направления потоков активной мощности по межсистемным связям в нормальных режимах. Системообразующим является напряжение 330 кВ. Анализировалась пропускная способность межсистемной связи между системами В и С (ЛЭП 1—2 и 3—4) при разрыве связи между системами С и D.
Как уже говорилось, ЛЭП обладает вполне определенной максимально допустимой пропускной способностью по условиям сохранения САУ в ОЭС — Ртах. При передаче по ЛЭП мощности Р>Ртах имеет место нарушение устойчивой работы системы в целом или аварийная сйтуация. Обозначим потоки мощности из системы С в системы В и D соответственно Р°св и P°cd- Допустим, на линии между системами С и D по каким-то причинам произошло устойчивое короткое замыкание. Противоаварийная автоматика при этом отключит указанную ЛЭП. После затухания электромеханических процессов в системе, вызванных коротким замыканием, поток мощности ВР^св в систему увеличивается на значение мощности, протекающей до аварии в сторону системы D из С, т. е. Рсв==Р°св+
49
+P9cd. Если новое значение Рсв больше Ртах, то послеаварийный установившийся режим физически не может существовать.
С помощью эквивалентных генераторов Г1 и ГЗ моделировалась работа ГРЭС, а генератора Г2 — ГЭС. Расчеты САУ выполнялись по программе СУС-1 [63]. Моделирование послеаварийных ситуаций осуществлялось путем увеличения активной мощности, генерируемой ГЗ. В соответствии с опытными данными принималось, что в процессе утяжеления каждого режима напряжение на шинах 330 кВ генераторов Г1 и ГЗ постоянно, т. е. U = const, а Г2 замещался переходной ЭДС £'<1 = const и переходным реактивным сопротивлением x'd. Нагрузки при расчетах установившихся режимов в процессе утяжеления учитывались постоянными значениями активной и реактивной мощностей, а при расчетах критерия нарушения САУ — типовыми статическими характеристиками по напряжению.
В качестве признаков были выбраны следующие:
напряжение на шинах 330 кВ генератора Г Г кВ (wi); напряжение на шинах 330 кВ генератора Г1, кв (дог); суммарное электропотребление энергосистемы В, МВт (w3); активная мощность, генерируемая Г2, МВт (ап);
переходная ЭДС генератора Г2, кВ (w5);
эквивалентное реактивное сопротивление генератора Г2 до шин 330 кВ, Ом (w6).
Признаки wi, ...» W5 — непрерывно изменяющиеся, переменные. Признак w6 является дискретной переменной, поскольку определяется количеством работающих генераторов на ГЭС в каждом конкретном режиме. Важно отметить, что диспетчерский персонал ОЭС располагает информацией об указанных признаках.
3.2.	ЭКСПЕРИМЕНТЫ
Таким образом, режимная ситуация с точки зрения распознавания образов А и Н характеризовалась 7-мерным вектором Х = = (wi, ..., We, у), где у — значение перетока активной мощности между энергосистемами В и С (МВт). Все необходимые расчеты по построению модели САУ проводились с помощью комплекса программ, составленных на алгоритмическом языке FORTRAN-IV. Объем обучающей выборочной последовательности был равен 100 (70 нормальных и 30 аварийных ситуаций), для экзамена предъявлялись оставшиеся 300 ситуаций. Результаты .усреднялись по пяти случайным обучающим последовательностям. Область определения ситуаций X с помощью нормировки (1.26) сводилась к единичному гиперкубу.
Для исследования был выбран коллектив из десяти линейных решающих правил, при этом гиперплоскости были заданы уравнениями в отрезках
~ п
flW= 2 d'ipwp + d'i(p+^y—1 хь
-Р=1
(3.3)
где Xz=±l; d'lp^dipjdiQ, diQ=£V.
Далее была реализована процедура селекции, подробно описанная в гл. 2. Для обучения коллектива использовался алгоритм, основанный на методе потенциальных функций (см. гл. 1), с помощью 50
которого определялись поверхности компетентности. Каждое решающее правило — член коллектива оценивалось по системе критериев, введенных в § 2.1.
В табл. 3.1 и на рис. 3.2 приведены результаты применения процедуры селекции. В таблице || отмечены те решающие правила, которые заменяются к следующему шагу селекции. Следует заметить, что в этом эксперименте использовалась еще одна эвристика, не приведенная в табл. 2.1. Суть ее состоит в том, что из коллектива исключаются правила, для которых выделилась очень маленькая область компетентности. Моменты исключения правил отмечены в таблице X. Кроме того, частично изменяются ограничения и критерий останова. Это касается 19-го и 21-го шагов. До 19-го шага
Рис. 3.2. Результаты эксперимента.
ипользовались следующие ограничения: а7пгп=0,01 г< Pmin ==0,80, а критерий останова g равнялся 10. Согласно эвристикам из табл. 2.1 на 18-м шаге процедура должна была быть закончена. Однако было замечено, что в коллективе имеются правила, исключение которых вряд ли ухудшит качество распознавания — это правила /?2 и R6. Для этих правил выделяется очень незначительная область компетентности: а^8 = 0,018; а^8 =0,012, но даже в этой области они работают крайне ненадежно: рХ8 «=0; р™ =0,5 (см. табл. 3.1).
Это является следствием ошибок классификации областей компетентности решающих правил. В результате исключения этих правил из коллектива частично устраняется этот недостаток, их области компетентности перераспределяются между оставшимися правилами, которые справляются с объектами из этих областей гораздо лучше.
Подобный же прием использовался на 21-м шаге (исключены правила и /?ю) и также привел к успеху, т. е. Р21<Р20. После этого частично изменились ограничения: атгп = 0; pmin = 0,8, а критерий останова g был принят равным 5. Минимальное значение вероятности ошибка распознавания аварийных ситуаций коллективом линейных решающих правил достигается на 23-м шаге процедуры и оказалось равным Р*==Р23 = 0,118. Порядок коллектива в процессе селекции уменьшается с 10 правил до 6. Коллектив {/?}* состоит
51
2		Zl	z2	2»	21
k		1	2	3	4
pk		0,233	0,239	0,281	0,215
Rt	al Pl	0,257 1,000	0,006 1,000	0,121 0,900	0,468 0,993
Ra	CL 2 P2	0,341 0,540	0 0	0 0	0,079 0,961
Rt	Pi	0,018 0	0,003 0	0,091 0,800	0,003 0
К	a4 Рь	0 0	0,644 0,930	0 0	0,027 0,667
Rs	аъ Pi	0,003 0	0 0	0 0	0,356 0,542
Re	a6 Pi	0,033 0,545	0 0.	0 0	0,039 0,231
R?		«7 Pl	0 0	0 0	0,003 0	0,006 1,000
Re	Pi	0,030 0	0,015 0,400	0 0	0,003 ' 1,000
R,	Pi	0,317 0,971	0 0	0,012 0,500	0,018 0,833
Ло	aii Plb	0 0	0,332 0,455	0,773 0,687	0 0
Таблица ЗЛ
1	z4	z2	Zi	Zi	z2
5	6	7	8	9
0,215	0,239	0,190	0,151	0,169
0,623	0,091	0,015	0,100	0,003
0,943	0,967	1,000	0,879	1,000
0,060	0,003	0	0	0
0,856	1,000	0	0	0
0,006	0	0,707	0,079	0,003
0	0	0,919	0,923	1,000
0,009 •	0,149	0,003	0,003	0,202
0	0,510	0	1,000	0,716
0,103	0,003	0	0,172	0
0,118	0	0	0,772	0
0	0,447	0,015	0,076	0,039
0	0,899	1,000	0,360	0,385
0,099	0,039	0,136	0,009	0
0,606	0,077	0,133	0,667	0
0,039	0,021	0	0,559	0,749
0,462	0,427	0	0,924	0,88?
0	0	0	0	0,003
0	0	0	0	0
0	0,248	0,124	0,003	0
0	0,732	0,902	1,000	0
z		Z2	z2	z2	
k		10	11	12	13
pk		0,199	0,205	0,160	0,166
Ri	A Pi	0 0	0,085 0,821	0 0	0,112 0,757
Rs	^2 P2	0 0	0,006 0,500	0 0	0 0
Rs	az Рз	0,054 0,722	0,051 0,706	0,072 0,917	0,048 0,875
R<	a4 Pi	0,003 0	0 0	0,091 0,300	0,057 0,158
r5	<h> Ps	0,408 0,741	0 0	0 0	0 0
R«	a6 Pt	0,009 1,000	0,021 0,143	0,015 0,800	0 0	_
R,	A Pi	0 0	0 0	0,006 1,000	0 0
Rs	^8 P*	0,444 0,925	0,468 0,936	0,801 0,894	0,770 0,906
R.	A A	0 0	0 0	0,015 0,800	0,012 0
*10	Ao Ao	0,082 0,482	0,387 0,664	0 0	0 0
Продолжение табл. 3.1
z2	Z2	za	z2	Z5
14	15	16	17	18
0,160	0,220	0,175	0,178	0,151
0,010	0,006	0,030	0	0,012
0,833	1,000	0,700	0	1,000
0	0	0	0,003	0,018
0	0	0	0	0
0,097	0,030	0,060	0,018	0,009
0,906	0,800	0,900	0,667	1,000
0,076	0,356	0,127	0	0,003
0,280	0,729	0,833	0	1,000
0	0,057	0	0,009	0,196
0	0,263	0	0,667	0,754
0,003	0	0,205	0,015	0,012
1,000	0	0,735	0	0,500
0,012	0	0	0,471	0,066
0,750	0	0	0,820	0,682
0,795	0,526	0,508	0,366	0,634
0,886	0,897	0,935	0,926	0,924
0	0,021	0,069	0	0,015
0	0,143	0,261	0	0,800
0	0,003	0	0,118	0,033
0	0	0	0,667	0,818
Продолжение табл. 3.1'
Z		Zj	za	Zi	Za	21	Za	Za	Za	z»
k		19	20	21	22	23	24	25	26	27
Pk		0,136	0,145	0,130	0,184	0,118	0,128	0,122	0,130	0,151
Rs	a\ Pl	0,039 1,000	0,009 1,000	0,012 1,100	0,115 0,842	0,012 0,750	0,051 0,823	0,006 1,000	0,054 0,667	0,006 1,000
rs	a2 Pi	X	—	—	—	—	—	—	—	—
R,	Pi	0,036 0,833	0,190 0,841	0,193 0Л97	0 0	0,106 0,829	0,039 0,923	0,045 0,933	0,205 0,794	0,100 0,879
R*	a4 Pt	0,030 1,000	0,006 1,000	0,006 1,000	0,012 0,750	0,109 0,806	0,015 1,000	0,169 0,839	0,009 1,000	0 0
	a* Ръ	0,290 0,792	0,048 0,812	0,054 0,778	0,073 0,125	0,039 0,692	0,012 0	0,063 0,714	0,021 0,429	0,060 0,200
R.	a^ Pi	X	—;	—	—	—	—	—	—	—
R,		a7 Pl	0,042 0,500	0,027 0,444	0,030 0,500	0,021 0,143	0,039 0,846	0,033 0,818	0,006 1,000	0,015 0,600	0 0
R>	a9 Ps	0,529 0,931	0,685 0,908	0,704 0,910	0,779 0,895	0,695 0,917	0,849 0,890	0,710 0,898	0,695 0,926	0,834 0,891
R.		Ug Pi	0,027 0,667	0,021 0,143	X	—	—	—	—	—	—
^10 j	aio Pio	0,006 0,500	0,012 0,250	X	—	•—	-—	—	—	—
из следующих правил:
fj (X) = — О,172%, — 0,206%2 — 0,045%, + + 0,08%4—0,107%5 + 0,028%в + 1,39%7 + 1;
f2 (X) = 0,034%, — 0,005%2 + 0,048%3 + + 0,042%4 + 0,13%5 — 0,236%б — 0,92%7 + 1; f3 (X) = — 0,399%, — 0,147%2 — 0,399%3 — — 0,105%4 — 0,125%б— 0,358%e+0,111%7+1;
(X) = — 0,123хб— 1,245%6 + 0,012%7+ 1;
f6 (X) = 7,843%, — 4,319%2 + 13,243х3 — — 9,683%4 — 4,436х5 + 10,96хб+0,391х7+1;
f6 (X) = — 0,208%, — 0,077%2 — 0,401 %3 + +0,067%4 + 0,672%б — 0,227хв — 0,922%7+1.
(3.4)
Эта же задача решалась рядом традиционных алгоритмов распознавания образов: методом потенциальных функций, методом минимума расстояния до средних, методом ближайшей точки, методом, построенным на аппроксимации разделяющей поверхности квадратичной регрессией. Эксперименты проводились на пяти различных случайных обучающих последовательностях, и усредненные результаты приведены в табл. 3.2.
Таблица 3.2
Метод минимума расстояния до средних	Метод потенциальных функций	Метод ближайшей точки	Квадратичная регрессия	Коллектив линейных правил	
				до селекции	после селекции
0,325±	0,212+	0,172±	0,203±	0,233	0,118+
+0,049	+ 0,036	±0,022	±0,038		±0,009
Полученные результаты наглядно свидетельствуют о преимуществе коллектива линейных решающих правил перед рядом традиционных алгоритмов распознавания, а также об эффективности процедуры селекции.
Указанные традиционные алгоритмы распознавания в свою очередь объединялись в коллектив, который, во-первых, принимал решение голосованием, во-вторых, обучался с помощью метода потенциальных функций (см. гл. 1). Результаты, приведенные в табл. 3.3, также иллюстрируют эффективность предложенного способа организации коллективного решения как перед обычным голосованием, так и перед лучшим из алгоритмов, включенных в коллектив. Заметим, что, если в алгоритме голосования голоса решающих правил разделялись поровну между классами Н и А, решающий голос отдавался правилу ближайшей точки как наиболее надежному.
Следует заметить, что, собирая коллектив из обучающихся алгоритмов, необходимо частично изменить процедуру обучения, а именно из всей имеющейся в распоряжении исследователя последователь-55
ности ситуаций выделить две обучающие последовательности. Первая используется для обучения правил — членов коллектива, а вторая — для обучения самого коллектива. В связи с этим предпочтение следует отдавать коллективу обученных правил, какими являлись правила в первом эксперименте. По этой же причине результаты применения традиционных алгоритмов в табл. 3.2 и 3.3 несколько отличаются.
Таблица 3.3
Алгоритм	Метод минимума расстояния до средних	Метод потенциальных функций	Метод ближайшей точки 1	Квадратичная регрессия	Алгоритм голосования	Алгоритм* обучения коллектива
Рош	0,340+ 0,022	0,234+ 0,008	0 183± 0,017	0,213+ 0,013	0,196+ 0,027	0,160± 0,009
	0,231	0,212	0,292	0,265		
Pl	0,828	0,894	0,814	0,867		
В табл. 3.3 приведены также характеристики указанных решающих правил — членов коллектива, введенные в гл. 2. Заметим, что в данном коллективе трудно отдать предпочтение какому-нибудь одному правилу. Все они имеют приблизительно одинаковые области компетентности, качество распознавания в этих областях существующими правилами также примерно одно и то же. При этом не следует забывать, что полученные оценки касаются лишь данной задачи распознавания.
В заключение коротко рассмотрим, каким образом полученные результаты могут быть использованы в практической работе диспетчерского персонала ОЭС.
Процесс разработки системы прогнозирования пропускной способности ЛЭП осуществляется в соответствии со структурной схемой, изображенной на рис. 3.3. В блоке 1 — банке исходных данных (внешней памяти вычислительного комплекса) хранится ретроспективная информация о режимных ситуациях, в ОЭС (напряжения в контрольных точках, генерирующие мощности, электропотребление систем и др.). Информация поступает в банк данных как с помощью телеизмерений, так и в результате машинной обработки ведомостей по режимам работы ОЭС. В блоке 2 осуществляется расчет для любой режимной ситуации предела САУ для заданных межсистемных связей по специализированным программам. При этом используются хранящиеся во внешней памяти заданные схемы замещения сети и способы утяжеления режимов.
Значения режимных параметров, используемых при прогнозировании, в промежуточных и предельных стационарных режимах засылаются в третий блок 3, где происходит формирование выборочных совокупностей для всех заданных ЛЭП. В блоке 4 реализуется рассмотренный алгоритм. Программа (распознающее устройство) работает в двух режимах: обучения и экзамена. Определяются оптимальные параметры коллектива решающих правил и стати-
ётйческйе оценки качества распознавания. В блоке 4 заканчиваете^ получение моделей для заданных ЛЭП. Модели могут быть далее использованы в прогностических целях.
Прогнозирование величины пропускной способности для любой ЛЭП в ожидаемом диспетчером послеаварийном режиме осуществляется следующим образом. Диспетчер с пульта (блок 7) заносит в программу блока 5 информацию о значении вектора признаков W и признак jtj — «имя» исследуемой ЛЭП. В программе хранятся начальные значения предельного перетока активной мощности Р°пред
и приращения мощности ДР°пРед, а также параметры коллектива решающих правил для заданной ЛЭП. С помощью процедуры, аналогичной применяемой в блоке 4 режима экзамена, программа классифицирует ситуацию Х= {W, Р°пред} распознающим устройством со значениями параметров, соответствующих признаку зт;. Результат прогнозирования выдается на диспетчерский пульт управления ((блок 6).
В практике управления режимами работы ОЭС параметры распознающих устройств следует пересчитывать, поскольку с течением времени системы развиваются и изменяются условия их функционирования, что влияет в той или иной мере на пропускную способность межсистемных связей ОЭС. Вопросы, связанные с периодич’ ностью пересчета параметров моделей, а равно и с размерами выборок, обеспечивающих требуемое качество распознавания, могут быть решены окончательно лишь после внедрения в эксплуатацию автоматизированных систем прогнозирования.
5—1107	67
Следует заметить, что рассмотренная задача йе является единственной в энергетике, где можно применять теорию распознавания и предложенные алгоритмы. Рассмотренные здесь принципы могут быть применены при построении прогностических моделей техникоэкономических показателей функционирования ОЭС (уровня динамической устойчивости, потерь электрической энергии, оптимальных уровней напряжений в контрольных точках системообразующей сети), в противоаварийной защите и автоматике в качестве распознающих устройств аварийных ситуаций и многих других подсистем ОЭС.
ГЛАВА ЧЕТВЕРТАЯ
РАСПОЗНАВАНИЕ КОЛЛЕКТИВОМ ЭКСПЕРТОВ
4.1.	ПРОБЛЕМА КОЛЛЕКТИВНОГО РЕШЕНИЯ
Рассматриваемые в настоящей книге вопросы можно с уверенностью отнести к проблеме принятия коллективного решения. Эта проблема, встречающаяся в литературе чаще как проблема группового выбора, в настоящее время привлекает внимание широкого круга исследователей [7, 8, 20, 22, 30, 43, 44, 48, 50, 90, 92—95, 97]. Во многих работах рассматривается анализ различных процедур голосования [43, 44, 48, 92—95, 97]. Другая большая группа работ касается получившего исключительно широкое распространение метода экспертных оценок [2, 7, 20, 22, 23, 30, 48, 50, 90].
Обработка экспертных мнений также подразумевает анализ решения коллектива экспертов, поэтому эти вопросы неразрывно связаны и с первой группой работ. Кратко остановимся на этих вопросах, так как они имеют непосредственное отношение к нашей теме.
Под групповым выбором или коллективным решением обычно понимают {43, 44, 48, 92] выработку согласованного коллективного решения о порядке предпочтения рассматриваемых объектов на основе индивидуальных мнений членов коллектива. Примером такой ситуации может служить упорядочение альтернатив о возможном заболевании, о плане лечения и т. п., осуществляемых таким коллективом, как медицинский консилиум. Иногда главным является принятие коллективом решения о наиболее предпочтительной альтернативе или наиболее предпочтительном объекте. При этом вопрос упорядочения альтернатив отодвигается на второй план. Очевидно, обе эти задачи эквивалентны и подходят под общую формулировку коллективного решения. В [48] отмечается, что решение коллектива зависит от огромного числа факторов, выявить которые и оценить практически не представляется возможным, как например, эмоциональное состояние членов экспертной комиссии или медицинского консилиума во время выработки решения. Даже порядок выступлений экспертов может существенно влиять на конечный результат. В настоящее время не существует достаточно общих разумных концепций того, как происходит процесс группового выбора. Основной акцент делается на том, какими свойствами должен обладать конечный результат. Там же, в [48], сказано, что проблема группового выбора есть проблема перехода от заданных индивидуальных наборов данных к единому групповому набору. Природа индивидуумов и их предпочтений может быть самой различной. Это могут быть эксперты и их оценки, с одной стороны, и исходные признаки и порождаемые ими классификации, с другой.
Одним из первых, кто проанализировал этот вопрос, был К. Эрроу. В его истолковании [92] задача выработки группового или 58
коллективного решения состоит в том, как сочетать индивидуальные системы предпочтений относительно различных состояний так, чтобы создать единую систему предпочтений для общества, состоящего из данных индивидуумов. Существуют и приводятся [43] примеры некоторых методов или процедур для перехода от предпочтений индивидуумов относительно общественных альтернатив к предпочтению для общества: соглашение, обычай, религиозный закон, авторитет, диктаторский декрет, голосование и т. п.
Однако при анализе функций группового выбора или коллективного решения в явном виде не учитываются свойства индивидуумов, их социальные, интеллектуальные, психологические и другие особенности. Очевидно, что диктаторская функция группового выбора не может быть признана удовлетворительной, поскольку коллектив тогда вообще теряет смысл. На практике, особенно в медицинских консилиумах, такая функция встречается достаточно часто. В этом! случае ее лучше назвать авторитарной — мнение «непогрешимого» авторитета отождествляется с мнением всего коллектива. Этому во многом способствует явление конформизма, встречающееся в консилиуме, как, впрочем, и в других экспертных коллективах. Другая крайность в медицинском консилиуме — это равноправное голосование, но оно встречается не так уж часто. Существует также опасность принятия ошибочного решения за счет большинства голосов; ошибающихся членов консилиума. Ранжирование, не зависимое от оцениваемой ситуации, вряд ли улучшит дело — этот случай промежуточный между авторитарным подходом и простым голосованием. При этом ошибка члена консилиума с высоким рангом легко может стать ошибкой всего коллектива. Алгоритмы, предложенные в данной работе, устраняют указанные недостатки.
Рассматривая методы принятия коллективного решения, нельзя обойти вниманием методы экспертных оценок, получившие широкое распространение в самых различных областях науки и техники. Термин «экспертные методы» объединяет большую группу способов и процедур, основанных на теории экспертных оценок, которые как правило, являются голосующими со всеми свойственными этим методам недостатками. Эти недостатки обсуждались выше. Однако поскольку голосующие методы являются усредняющими, хочется еще раз процитировать выдержки из работы Д. Т. Гюйбо, представляющей замечательный образец историко-аналитического подхода к проблеме группового выбора. Он приводит так называемый принцип Курно, сформулированный еще в 1843 году: «Когда к различным частям сложной системы применяют операцию определения среднего арифметического (усреднения), необходимо очень хорошо помнить, что эти средние значения могут быть несовместимы друг с другом, если для каждого из элементов взять его среднее значение, определенное отдельно; система может находиться в запрещенном состоянии» [97]. Вот несколько простых примеров, иллюстрирующих сформулированный принцип: «... В общем случае не существует некоторого треугольника, которому соответствуют усредненные значения углов и сторон. Усреднение площадей не будет совпадать с площадью треугольника, построенного на средних значениях сторон, и т. д. ... Таким образом,' даже если известны размеры различных органов нескольких животных одного и того же вида, вполне возможно, что усредненные значения могут быть несовместимы друг с другом и условиями существования вида. Можно попытаться определить и описать среднего человека системой средних арифметических, подученных измерением веса и других ха
59
рактеристик большого числа индивидов. Так, определенный средний человек, далекий от того, чтобы быть прототипом вида, просто должен быть невозможным человеком, или по крайней мере ничто не позволяет нам считать его возможным» [44].
Вернемся к теории экспертных оценок. В работе [7] приводятся некоторые требования к идеальному эксперту. Это — интуиция, креативность, эвристичность, независимость, всесторонность и т. п. Подбор экспертов с такими свойствами представляет значительные трудности, если вообще возможен. При подборе экспертов пользуются различными оценками их компетентности. Наиболее важный вопрос — это оценка согласованности экспертов. Мнения экспертов должны быть максимально согласованы, в противном случае коллектив экспертов является несостоятельным. Однако при максимальной согласованности мнений экспертов теряется смысл в коллективе экспертов, поскольку мнение любого из экспертов является мнением всего коллектива.
/Коллективные экспертные оценки различаются методом их формирования. Различают метод комиссии, метод отнесенной оценки и метод Дельфи. Метод комиссии — это проведение группой экспертов дискуссии с целью выработки общей позиции по рассматриваемому вопросу, при этом существенно сказывается взаимное влияние экспертов. Вообще говоря, влияние самых разнообразных причин и факторов может привести к нежелательным последствиям. Эти недостатки частично устраняются методом отнесенной оценки или методом мозговой атаки. Наибольший интерес представляет метод Дельфи, который отказывается от коллективных обсуждений и заменяет их программой последовательных индивидуальных опросов. Ответы экспертов обобщают и вместе с новой дополнительной информацией передают в распоряжение экспертов, после чего они уточняют свои первоначальные ответы. Такая процедура повторяется несколько раз до достижения приемлемой согласованности всех высказанных мнений. Повторяя сказанное выше, отметим, что при анализе результатов экспертного опроса следует избегать двух постоянно грозящих крайностей: излишнего доверия к индивидуальным суждениям авторитетов, с одной стороны, и слепого следования за обезличенным статистическим большинством, с другой.
Интересный анализ методов экспертных оценок приводит Н. Н. Воробьев в работе [20]. Там отмечается, что статистические усреднения оценок не обязательно повышают их достоверность. Пусть задано множество экспертов, каждый из которых должен оценить некоторое явление, назвав его индивидуальную оценку. Таким образом, итогом деятельности коллектива экспертов оказывается некоторая выборка таких оценок. Результатом той или иной статистической обработки этой выборки и будет коллективная экспертная оценка. Индивидуальная оценка каждого эксперта несет в себе, во-первых, узкосубъективные, личные черты и представления эксперта, во-вторых, это коллективно-субъективные черты, которые присущи всему коллективу в целом. Если первая компонента является случайной и ее можно отфильтровать при увеличении числа экспертов, то вторая компонента субъективности по мере увеличения числа экспертов и уменьшения индивидуальных расхождений между ними не исчезает; коллективная оценка будет приближаться не к истинному значению оцениваемого параметра, а к некоторой величине, которую можно считать общественной точкой зрения на этот параметр. Метод экспертных оценок применяется в условиях принятия решения 60
в неопределенности. Теоретической основой принятия оптимальных решений в условиях неопределенности является теория игр. Поэтому при выработке решений на основе экспертных оценок должны учитываться и теоретико-игровые соображения. Там же отмечено, что математическая теория перехода от индивидуальных оценок к коллегиальным окажется (когда она будет построена) весьма сложной. В частности, пользоваться при этом усреднениями придется с большой осторожностью. Нетрудно построить пример, когда отдельно взятый эксперт может принять решение, которое будет лучше, чем средняя оценка коллектива в целом.
Не вызывает сомнения тот факт, что наибольшую ценность в коллективах, при прочих равных условиях, представляют эксперты-нонконформисты, высказывающие самостоятельные оригинальные суждения, способные противостоять авторитетам или мнению большинства [90].
Все сказанное позволяет сделать вывод о том, что предложенный в данной книге подход к принятию коллективного решения (это помимо того, что он является новым подходом к решению задачи распознавания образов) устраняет описанные недостатки методов голосования. Во-первых, в нем отсутствует процедура усреднения, во-вторых, он позволяет получать результат не хуже, чем лучший из членов этого коллектива. И, наконец, представляется, что он не противоречит теореме Эрроу '[43], поскольку его также можно интерпретировать как «диктаторский», однако «диктаторство» индивидуализируется областями компетентности каждого члена коллектива.
В качестве примера коллектива экспертов, обучаемого предложенными алгоритмами, рассмотрим медицинский консилиум.
4.2.	АНАЛИЗ ЭЛЕКТРОКАРДИОСИГНАЛОВ КОЛЛЕКТИВОМ ЭКСПЕРТОВ
Коллектив экспертов представляет собой группу специалистов, объединенную для проведения экспертизы и принятия коллективного решения.
Возможные информационные связи в коллективе можно представить так, как это сделано на рис. 4.1, причем часть связей может отсутствовать, так как не все члены коллектива обмениваются информацией.
Легко заметить, что эта схема мало отличается от общей схемы коллективного принятия решений, которая изображена на рис. 1.2.
Рис. 4.1. Информационные связи в коллективе экспертов.
61
Прежде чем сформулировать коллективное решение, лидер оценивает мнение каждого члена коллектива.
На формирование решения, очевидно, большое влияние оказывает правило, которым руководствуется лидер для оценки каждого специалиста.
Напомним ряд таких правил. В медицине издавна известен принцип: «Учитель сказал!» — «Magister discit». Этот принцип нередко встречается и в коллективах экспертов. Лидер в данном случае является непререкаемым авторитетом в данной области знаний, и его решение однозначно определяет решение всего коллектива. Такой авторитарный подход вряд ли может считаться оптимальным. Другая крайность — это равноправная оценка лидером высказанных мнений. Привлекая своей демократичностью, этот метод часто не приводит к положительному результату. Сравнительно легко построить случай, когда даже разумное ранжирование голосующих не улучшает коллективное решение.
Уже упоминалось выше, устранить недостатки таких методов можно введением адаптивности, зависимости решающего правила лидера от распознаваемой ситуации. Под этим понимается следующее: ранги или веса экспертов — членов коллектива не фиксируются неизменными и пропорциональными их индивидуальным качествам, например стажу работы, а вычисляются относительно каждой новой ситуации.
Интерпретируя работу такого коллектива с точки зрения предложенных в гл. 1 способов организации коллективного решения, следует заметить, что задача заключается в определении областей компетентности экспертов. Оценку этих областей можно получить по обучающей последовательности с помощью одного из предложенных алгоритмов обучения коллектива. Тогда относительно объекта будет принято решение специалистом, к чьей области компетентности этот объект принадлежит. Такая ситуация довольно типична в медицине, когда лидер консилиума не берет на себя ответственность за принятие окончательного решения, а обращается за консультацией к некоторому специалисту, который, с его точки зрения, наиболее квалифицирован и компетентен в данном случае. Другими словами, лидер реализует предложенный подход к организации коллективного решения. В этой связи уместно привести слова известного канадского физиолога Ганса Селье, который пишет: «В настоящее время редко можно встретить зрелого ученого, который сохранил бы общие знания хотя бы в том объеме, как только что окончивший обучение медик, в области гистологии, физиологии/ биохимии, фармакологии, клинической медицины и хирургии. Большинство спешит специализироваться и стать подлинным знатоком в одной определенной области. Это, несомненно, очень здравая позиция для огромного большинства, которое заинтересовано в решении заранее определенных проблем. Но всегда мы в медицинских исследованиях будем испытывать нужду хотя бы в небольшом числе широко мыслящих врачей-практиков, в людях, чей интеллект открыт многим вещам, встречающимся на их пути. Мы будем зависеть от их исследований, и нам всегда нужны будут в клинической медицине врачи широкого профиля, которые смогут взглянуть на больного как на единое целое и, как минимум, решить к какому специалисту его следует направить».
Итак, с учетом введенных выше определений и рассмотренных алгоритмов коллектив экспертов можно рассматривать как коллектив неформальных решающих правил. Очевидно, по отношению 62
к йеку могут йыть примейены алгоритмы обучейия, преДлоЖейнЫё в гл. 1, а также оценки качества работы специалистов, описанные в гл. 2.
Естественно возникает вопрос, какие решающие правила отождествляются с экспертами, каким правилом, например, руководствуется врач при постановке диагноза.
Очевидно, это правило невозможно описать формально, оно характеризуется такими факторами, как опыт, накопленный в той или иной области, методы исследования объекта, опыт практической работы эксперта, его интуиция, состояние его нервной системы в момент принятия решения и т. п. Это неформализуемое, эвристическое решающее правило. Можно предположить, что это правило учитывает и информационные связи между экспертами, изображенные на рис. 4.1.
Достаточно сложным является вопрос об организации обучающей последовательности. Ведь для этого необходимо иметь достаточно большое число прецедентов принятия решения этими экспертами. Очевидно, все объекты должны описываться по некоторой единой форме. В связи с этим обучению коллектива экспертов должна предшествовать большая организационная работа, начинающаяся с разработки системы описания объектов. После этого необходимо зафиксировать состав коллектива и предложить экспертам независимо от общего решения принимать свое решение относительно каждого объекта. На этом этапе обучения коллектив продолжает работать традиционным способом. Когда получено некоторое минимальное число случаев, коллектив обучается, после чего для каждого нового объекта определяется наиболее компетентный специалист. Решение этого специалиста отождествляется с решением коллектива Этот новый объект после верификации также добавляется к обучающей последовательности, и коллектив «доучивается».
В качестве примера рассмотрим процесс решения таким коллективом задачи анализа электрокардиосигналов с целью классификации нормальных и искаженных сигналов. Пространство признаков при этом определяется совокупностью тех параметров сигнала, которые обычно измеряет эксперт.
Основной целью данного эксперимента являлось выяснение вопросов, связанных с организацией коллективного решения с помощью предложенных алгоритмов. Материалом для обучения коллектива и проверки качества этого обучения служили образцы электрокардиосигналов с искажениями формы, являющимися следствием нарушений нормального функционирования системы (44 случая) и без таких искажений (56 случаев). Каждый сигнал характеризовался 35 признаками. В эксперименте был организован коллектив, состоящий из пяти экспертов: ...,
Все имеющиеся в нашем распоряжении образцы сигналов предъявлялись этим специалистам, которые должны были по каждому образцу делать краткое заключение (нормальный сигнал или нет). Специалистам была предоставлена полная свобода в выборе методов анализа. Каждый эксперт, очевидно, пользовался своим собственным неформальным алгоритмом, включающим ряд эвристик, таких, например, как визуальная оценка формы сигнала, сопоставление с эталонами и т. п.
Имеющиеся образцы сигналов случайным образом и многократно разбивались на две части: обучающую последовательность и контрольную последовательность. По первой согласно алгоритму Б, описанному в § 1.2, строились оценки потенциальных поверхностей
63
компетентности экспертов. На контрольной последовательности проверялось качество обучения, для чего каждому сигналу из этой последовательности ставился в соответствие специалист, потенциал компетентности которого был максимальным. Решение этого специалиста сравнивалось с истинной принадлежностью сигнала к искаженному или нормальному. Число несовпадений, отнесенное к общему объему контрольной последовательности, определяло вероятность ошибки распознавания данным коллективом. На той же последовательности оценивались правильность принятия решений каждым экспертом в отдельности, а также правильность работы коллектива, если бы он принимал решение равноправным или ранжированным голосованием. При ранжированном голосовании ранги были присвоены экспертным способом пропорционально опыту каждого специалиста от 5 до 1. Результаты эксперимента приведены в табл. 4.1.
Таблица 4.1
Алгоритм	Ry	R*	Rz	ч.	R*	Обучение коллектива	Голосование	
							равноправное	ранжированное
Лнн	0,324± ±0,033	0,304 ± ±0,022	0,376± ±0,033	0,454± ±0,034	0,412± ±0,018	0,244± ±0,013	0,304± +0,014	0,282 ± ±0,015
а1	0,196	0,588	0,148	0,062	0,006			
Pl	0,776	0,759	0,743	0,679	1,000			
Полученные результаты свидетельствуют о преимуществе предложенного способа организации решения коллектива (с доверительной вероятностью 0,95) перед равноправным и ранжированным голосованием, а также перед лучшим из экспертов R2. В данном эксперименте каждый специалист оценивался по системе критериев, введенных в § 2.1.
Результаты этой оценки приведены в табл. 4.1.
Из' этой таблицы следует ряд важных выводов. Во-первых, она наглядно свидетельствует о том, что в составе коллектива имеются и узкие специалисты и 7?з, и эрудиты R2 Исключение специалиста Т?5 как компетентного в слишком узкой области и специалиста Т?4 как недостаточно компетентного в своей области не ухудшает качества работы коллектива. Во-вторых, за счет выделения для каждого специалиста области компетентности вероятность правильного распознавания в своей области оказывается выше аналогичной вероятности, но определенной на всех объектах контрольной последовательности. Следует заметить, что применение традиционных алгоритмов распознавания дает следующий результат: метод потенциальных функций — 0,348, метод ближайшей точки — 0,338.
Рассмотрим еще один пример'использования предложенного подхода к организации решения коллектива экспертов, осуществляющего краткосрочный прогноз.
64
4.3.	ЗАДАЧА КРАТКОСРОЧНОГО ПРОГНОЗА И РЕШЕНИЕ ЕЕ КОЛЛЕКТИВОМ ЭКСПЕРТОВ
Особенность краткосрочного прогнозирования [89] состоит в том, что истинные значения прогнозируемых величин, неизвестные в момент осуществления прогноза, становятся известными спустя непродолжительное время. Это позволяет вычислять ошибки экспертов в предыдущих оценках прогнозируемых величин и получать показатели точности для каждого эксперта (например, относительная ошибка и среднеквадратическое отклонение).
Введем некоторые обозначения. Пусть — оценка прогнозируемой величины z-м экспертом; q — коллективная оценка; t — истинное значение оцениваемой величины; т]г==(^г—/)//— относительная ошибка /-го эксперта, t=l, 2, ..., п. О точности отдельных экспертов и коллективных оценок можно судить по следующим показателям:
1.	Оценка математического ожидания модуля относительной ошибки
т
Й|М=4	(4-П
/=1
2.	Оценка дисперсии относительной ошибки
т
01^1=^-	(4.2)
/=1
В работе [89] предлагаются два вида коллективных оценок прогнозируемой величины:
а) среднеарифметическая
п qAj=~T^qii’ / = 1,2.....т’
i-=\
б) средневзвешенная
п
(1 + MZ/)DZ/
где / — номер прогнозируемого объекта; М// и D/y равны соответственно:

(4.5)
в« -
(4.6)
65
a t]ia — относительная ошибка i-го эксперта в оценке k-ro объекта. Для построения средневзвешенной оценки /’-го объекта использовались точностные характеристики экспертов, вычисленные на основании всех объектов, за исключением /-го. Это является по сути дела скользящим контролем, о котором упоминалось ранее (см. гл. 1). Действительно, из последовательности исключается /’-й объект, а оставшиеся используются для определения весов экспертов в оценке этого /*-го объекта. Такая процедура повторяется для каждого из т объектов. Нужно заметить, что скользящий контроль осуществим только в условиях экспериментальной проверки того или иного алгоритма.
Рассмотрим, как может быть использован для этих целей предложенный подход.
Свойства прогнозируемого объекта образуют пространство признаков, в котором необходимо искать области компетентности экспертов. Для' этого целесообразно использовать рассмотренную в гл. 1 модификацию метода Фикса — Ходжеса. Когда число ближайших точек равно 1, выбор наиболее компетентного эксперта осуществляется следующим образом. Для /’-го объекта (опять имеется в виду режим скользящего контроля) среди оставшихся т—1 объектов в пространстве признаков отыскивается ближайший в смысле заданной метрики, например евклидова расстояния. Прогноз /‘-го объекта осуществляет эксперт, наиболее компетентный для /г-го объекта, ближайшего к /’-му. Это означает, что он наилучшим образом (например, по минимуму абсолютной ошибки) оценивает /-й объект. Оценки точности работы такого коллектива можно проводить по тем же выражениям (4.1), (4.2).
В качестве примера была решена следующая модельная задача. Коллективу, состоящему из трех экспертов, необходимо было прогнозировать стоимость книг. Каждую книгу можно охарактеризовать с помощью ряда признаков, таких, например, как объем книги, ее формат, качество бумаги, обложки, наличие иллюстраций, оригинальная книга или переводная и т. п. Каждая книга описывалась вектором в 7-мерном пространстве признаков. Было отобрано 80 книг различного характера: научно-технические, научно-медицинские, художественные и др. Эксперимент проводился в режиме скользящего контроля, и определялись точностные характеристики каждого эксперта, среднеарифметического прогноза, средневзвешенного прогноза, предложенные в [89], и коллективного прогноза, основанного на выделении наиболее компетентного эксперта для каждой книги. Эксперимент показал, что для каждого эксперта выделяется своя естественная область компетентности: инженер лучше прогнозирует стоимость технической литературы, врач — медицинской, филолог — художественной. За счет этого, очевидно, и наблюдается преимущество
Таблица 4.2
	/?1		Яз	Среднеарифметический прогноз	Средневзвешенный прогноз	Коллектив
Mhi	0,294	0,362	0,276	0,260	0,244	0,202
Dhl	0,127	0,286	0,067	0,113	0,087	0,097
60
Предложенного подхода к организации коллективного прогноза переД отдельным экспертом. Что же касается среднеарифметического прогноза и средневзвешенного, то трудно быть уверенным, что они всегда дадут результат лучше отдельного эксперта. Об этом уже говорилось в § 1 этой главы. Полученные результаты приведены в табл. 4.2.
Рассмотренные примеры наглядно свидетельствуют о том, что предложенный в книге подход применим при организации решения коллектива экспертов.
ЗАКЛЮЧЕНИЕ
Рассмотренный в книге алгоритм представляет собой эффективный алгоритм распознавания образов (РО), поэтому его целесообразно соотнести с другими известными методами распознавания. Рассмотрим, как этот и другие алгоритмы распознавания укладываются в общую схему коллективного принятия решений.
Начнем с таких широко распространенных алгоритмов, как алгоритмы, построенные на основе теории статистических решений [15, 77], локальные методы [15, 53], корреляционные методы [41, 42, 53] и т. д. Эти методы традиционны и основаны на получении по некоторой последовательности ситуаций (обучающей последовательности) решающего правила, которое не изменяется в процессе поступления контрольных ситуаций. В предлагаемой схеме, изображенной на рис. 3.1, подобной ситуации соответствует самый нижний уровень, когда коллектив вырожден, т. е. он состоит всего из одного члена и вес этого единственного члена коллектива фиксирован в результате обучения.
Следующий класс алгоритмов — это алгоритмы, в которых веса решающих правил — членов коллектива также фиксированы, но число правил в коллективе больше единицы. К этому классу относятся в первую очередь перцептронные алгоритмы распознавания [3, 47, 55]. Как известно, обучение простейшего перцептрона состоит в настройке весов A-элементов. Каждый A-элемент легко интерпретируется как самостоятельное решающее правило — член коллектива. Особенность этого правила состоит в том, что оно работает в некотором подпространстве исходного пространства описаний. Характер этого подпространства (составляющие его признаки) определяется связями между элементами' сетчатки и входами данного А-элемента. Решение, которое получаем на выходе перцептрона, в свою очередь можно интерпретировать как средневзвешенное решение коллектива, состоящего из A-элементов. Близок к алгоритмам перцептронного типа и метод потенциальных функций [3].
Предпринимались попытки совместного использования нескольких алгоритмов распознавания [45, 70]. В этих работах, как и в перцептроне, решение формулируется как средневзвешенное значение решений комбинируемых алгоритмов. Следует только заметить, что в этом случае комбинируемые алгоритмы могут отличаться и принципиально, а не только видом подпространства, как это происходит в перцептроне.
В смысле комбинирования однотипных алгоритмов, но функционирующих в различных подпространствах, еще ближе к перцептронному лежит подход, рассмотренный Бонгардом [9]. Этот подход породил множество разнообразных алгоритмов, различающихся по существу методами перебора конъюнкций [9, 14, 21, 25, 32—-34,
67
38,81,88], но укладывающихся примерно в одну и ту же схему. Анализ этого класса алгоритмов следует начать с алгоритма «Кора» [9, 14]. М. М. Бонгард выдвинул идею о том, что решение задачи распознавания образов следует искать среди возможных логических функций характеристик описания оъектов. Нетрудно заметить, что перцептрон также реализует эту идею: каждый A-элемент представляет собой некоторую логическую функцию от переменных, которые связаны со входами этого A-элемента. Алгоритм «Кора» основан на поиске для каждого класса признаков, которыми обладают объекты одного класса и не обладает ни один из объектов другого класса (или обладает достаточно малое число объектов этого класса). Признаками класса являются конъюнкции, составленные из харак-
Статистические методы РО /15,77 ]
Локальные методы РО [ 15,53 ]
Корреляционные методы РО /40,41, 53 7 
Рис. 3.1. Схема обобщения алгоритмов распознавания образов. 68
теристик исходного описания. При распознавании подсчитывается число конъюнкций — признаков каждого класса, принимающих на контрольном объекте единичное значение. Объект относится к тому из классов, для которого это число оказывается наибольшим.
Таким образом, и в этом алгоритме сталкиваемся с процедурой усреднения или голосования. Каждую конъюнкцию можно легко интерпретировать как самостоятельное решающее правило, поэтому алгоритм укладывается в общую схему коллектива распознающих алгоритмов, изображенную на рис. 1.2. Веса конъюнкций — решающих правил могут быть единичными, тогда имеем равноправное голосование, а могут определяться и разнообразными процедурами [9, 25], что приводит к взвешенному голосованию. Однако и в том, и в другом случае веса конъюнкций — решающих правил фиксированы и не изменяются от одной контрольной ситуации к другой.
Из различных модификаций метода перебора конъюнкций следует особо отметить так называемые методы вычисления оценок, предложенные Ю. И. Журавлевым. В этих методах делается попытка усечения полного перебора [34]. Покажем, что и этот метод можно отнести к классу коллективных решающих правил.
На всем множестве признаков задаются опорные, или голосующие, множества [34], представляющие собой проекции на определенным образом выбранные подпространства. Эти проекции можно интерпретировать как отдельные решающие правила. Контрольный объект проецируется на каждое опорное множество и сопоставляется с проекциями объектов обучающей последовательности. Далее подсчитывается число совпадающих проекций для обоих распознаваемых классов в каждом из опорных множеств. Число голосов суммируется, и объект относится к тому классу, за который подано большее число голосов. Можно также учитывать и вес каждого опорного множества, тогда голосование становится взвешенным.
Близок по идеологии к методам вычисления оценок [34] и алгоритму «Кора» [9, 14] предложенный П. Е. Куниным метод направленного обучения [38]. В этом алгоритме решающее правило индуцируется контрольным объектом. Это означает, что решающее правило вырабатывается направленно по отношению к каждому новому объекту. При этом изучаются зависимости только между признаками, которые имеются у контрольного объекта. Если при этом используется метод перебора конъюнкций, то в качестве признаков каждого класса отыскиваются только конъюнкции, принимающие единичные значения на контрольном объекте. Далее решение также принимается голосованием.
Последняя группа методов, которую можно отнести к методам коллективного принятия решений, включает в себя методы формирования понятий. Эти методы широко используются в распознавании [21, 85, 88]. По существу и алгоритм «Кора», и методы вычисления оценок могут быть отнесены к этому классу. Обзор методов формирования понятий дан в [21]. Частными алгоритмами формирования понятий являются концептуальный подход В. В. Чавчанидзе [88] и методы, основанные на построении дерева решений [21, 85]. В этих методах каждому контрольному объекту соответствует свой путь на дереве решений. Этот путь индуцируется наличием или отсутствием у данного объекта того или иного признака. Заканчивается он в определенной вершине, которой в соответствие поставлен индекс одного из распознаваемых классов. Путь на дереве решений также легко можно интерпретировать как некоторую конъюнкцию переменных и их отрицаний. Если в алгоритме «Кора» решение определяет
69
ся в процессе голосований между конъюнкциями, то в данном поД< ходе решение полностью определяется одной конъюнкцией, вес которой, как решающего правила, априорно фиксирован. В концептуальном подходе решение определяется наличием у объекта некоторого концепта, который определяется как совокупность признаков, причем в общем случае это могут быть и качественные, и количественные признаки. В последних двух методах коллективное решение определяется решением одного из правил — конъюнкции или концепта, однако выбор производится только по значениям признака у контрольного объекта, а не качественными характеристиками выбираемого правила. На этом заканчивается анализ второго уровня схемы, изображенной на рис. 3.1.
При рассмотрении методов, основанных на идеях перцептрона, и методов перебора конъюнкций уже отмечалось, что в этом случае членом коллектива является правило, определяемое либо как А-эле-мент, соединенный с рядом признаков, либо как конъюнкция некоторых признаков. Другими словами, характер самих правил не меняется, меняется лишь подпространство, в котором эти правила работают. Оказывается, если применять к такого рода правилам предложенный в работе подход, можно получать эффективные и достаточно простые системы распознавания.
Предложенному в работе подходу в приведенной схеме отведено место на верхнем уровне — это случай, когда веса алгоритмов — членов коллектива изменяются в зависимости от конкретной контрольной ситуации и интерпретируются как коэффициенты компетентности алгоритмов. На этом уровне можно рассмотреть два случая: простейший, когда решение коллектива определяется решением правила, коэффициент компетентности которого для данного объекта максимален, и более общий, когда для принятия решения правила голосуют с весами компетентности, причем в таком голосовании могут участвовать как все решающие правила — члены коллектива, так и только первые L' наиболее компетентных. Во втором случае можно говорить о некоторой наиболее компетентной коалиции, в частности, состоящей только из одного правила.
Рассмотренный в книге подход касается не только задачи распознавания образов. Действительно, в типовых задачах синтеза поведения, выбора оптимального решения, назначения наилучшего плана и т. д. трудность, как правило, заключается в выборе в определенном смысле наилучшего алгоритма решения задачи из имеющегося набора алгоритмов. Изобретение нового алгоритма в такой ситуации нецелесообразно и, во всяком случае,, неэкономично.
Живые организмы умеют эффективно решать эту задачу и в типовых ситуациях строят поведение, комбинируя уже известные им алгоритмы.
Рассмотрим следующую весьма распространенную ситуацию. Пусть имеется некоторое множество <(конечное или бесконечное) однотипных задач {Xt},	2, ..., /. Эти задачи кодируются п па-
раметрами Xi, хг, ...» хп так, что каждая задача в пространстве представляется точкой Х»==(Х1, Хг, ...» хп), а все множество задач образует область S Х<еЕ, i= 1, 2 ...
Пусть также имеется конечный набор алгоритмов {/?} = (/?i, /?2, ...» Rl) решения задач XtsS. Каждый из этих алгоритмов Ri, Z=l, 2, ..., L, решает или не решает задачу Xi. Эффективность решения определяется некоторым заданным критерием Q, который паре Xi и Ri соотносит число
q=Q(Kt, Ri),	(3.1)
70
характеризующее работоспособность алгоритма Ri при решении задачи Х<.
Приведем примеры задач такого рода: 1) задача распознавания образов, о которой уже шла речь: X — конкретная задача распознавания, {/?} — множество алгоритмов распознавания, например методы Байеса, потенциальных функций, перцептрона и т. д., q — критерий эффективности распознавания; 2) задача определения корня, где X — конкретная функция, корень которой определяется, {У?} — множество алгоритмов определения корня, например методы касательных, хорд, дихотомии и т. д., q — число итераций, необходимых для попадания в 8 — окрестность корня; 3) задача поисковой оптимизации, где X — ситуация, сложившаяся в процессе оптимизации, {/?} — множество алгоритмов поиска, например методы градиента, случайного поиска и т. д., q — среднее приращение оптимизируемой функции или число неудачных шагов; 4) задача прогнозирования или экстраполяции, где X — ситуация, будущее состояние которой следует прогнозировать, {/?} — множество алгоритмов экстраполяции или прогнозирования, включающее формальные и неформальные методы (методы экспертных оценок), q — значение относительной ошибки прогноза. Список задач легко можно продолжить.
Выбор оптимального алгоритма решения задачи X сводится, таким образом, к решению экстремальной задачи:
Q (Xh Ri) -► extr => Rp,	(3.2)
Z=I, ...,L
где Rp — наилучший из имеющихся алгоритмов решения задачи Xt-«
Предложенные в книге алгоритмы в слегка модифицированном виде могут быть использованы для решения этих разнообразных задач. Модификация алгоритма зависит от типа решаемой задачи. Данный подход позволяет решать задачу (3.2), минуя полный перебор алгоритмов. Поскольку решение оптимизационной задачи (3.2} связано с однократным решением задачи Хг, в случае полного перебора выбор оптимального алгоритма становится бессмысленным, так как задача уже решена.
Как уже говорилось, живые организмы довольно хорошо решают задачу (3.2). Поэтому данный подход может быть использован как модель для понимания процессов выбора поведения организмов в типичных ситуациях. В этом случае путь исследования очевиден — нужно описать пространство задач Qn, решаемых организмом, выделить множество задач S и множество алгоритмов поведения {/?}, а затем по наблюдениям поведения в различных ситуациях, т. е. при решении задач из множества S, выделить области компетентности каждого алгоритма поведения Ri. Если эти области не пересекаются, то есть все основания предполагать, что живой организм при выборе поведения реализует описанный выше алгоритм.
Если пойти дальше, то идея коллектива алгоритмов в социальной области давно нашла свое применение в виде концепции разделения труда. Оптимальность подобной организации здесь не вызывает сомнений. Авторы надеются, что им удалось защитить идею коллектива и в несоциальной области, в частности, при решецц# задач распознавания образов.
СПИСОК ЛИТЕРАТУРЫ
1.	Аб А. Ф., Первушин Ю. П., Эренштейн Р. X. Прогнозирование уровня статической апериодической устойчивости в объединенных электроэнергетических системах методами распознавания образов. — Изв. АН СССР. Энергетика и транспорт, 1975, № 4, с. 39—50.
2.	Адлер Ю. П., Азагальдов Г. Г., Райхман Э. П. Классификация экспертных методов. — Материалы VI симпозиума по кибернетике, ч. III. — Тбилиси: 1972, с. 1—3.
3.	Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970. —384 с.
4.	Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Теоретические основы метода потенциальных функций в задаче об обучении автоматов разделению входных ситуаций на классы. — Изв. АН СССР. Автоматика и телемеханика, т. XXV, 1964, № 6, с. 947—936.
5.	Андерсон Т. Введение в многомерный статистический анализ. — М : Физматгиз, 1963. — 500 с.
6.	Барабаш Ю. Л., Барский Б. В., Зиновьев В. Т. Вопросы статистической теории распознавания. — М.: Советское радио, 1967. — 376 с.
7.	Бешелев С. Д., Гурвич Ф. Г. Экспертные оценки. — М.: Наука, 1973. — 159 с.
8.	Больдур Дж. О групповом принятии решений. — В кн.: Социология и математика. — Новосибирск: СО АН СССР, 1970, с. 16—28.
9.	Бонгард М. М. Проблема узнавания. — М.: Наука, 1967.— 320 с.
10.	Браверман Э. М. Опыты по обучению машин распознаванию зрительных образов. — Изв. АН СССР. Автоматика и телемеханика, т. XXIII, 1962, № 3, с. 426—439
1'1	. Браверман Э. М. О методе потенциальных функций. — Изв. АН СССР. Автоматика и телемеханика, 1965, № 12, с. 2205—22'13.
12.	Браверман Э. М., Аркадьев А. Г. Обучение машины классификации объектов. — М.: Наука, 1971. — 192 с.
13.	Быховский М. Л., Вишневский А. А. Кибернетические системы в медицине. — М.: Наука, 1971. — 407 с.
14.	Вайнцвайг М. Н. Алгоритм обучения распознаванию образов «Кора». — В кн.: Алгоритмы обучения распознаванию образов. — М.: Советское радио, 1973, с. 8—12.
15.	Вапник В. Н., Червоненкис А. Я. Теория распознавания образов — М: Наука, 1974. — 416 с,
72
16.	Васильев В. И. Распознающие системы. Справочник. — Киев: Наукова думка, 1969.— 292 с.
17.	Веников В. А. Переходные электромеханические процессы в электрических системах. — М.: Высшая школа, 1960. — 312 с.
18.	Применение статистических методов факторного планирования эксперимента и расчета к оценке статической устойчивости при учете неточности задания Параметров схем и режимов электрических систем/ В. А. Веников, Н. Д. Анисимова, Н. К. Круг, Е. М. Артемьева— В кн.: Кибернетика и моделирование в энергетике. — М.: Наука, 1972, с. 112—122.	-
19.	Перспективы развития методов и средств АСДУ для обеспечения устойчивости ЕЭС СССР/ В. А. Веников, Я. Н. Лугииский, Л. Г. Мамиконянц и др. — Доклады на III Всесоюзном научно-техническом совещании по устойчивости и надежности энергосистем СССР. — М.: Энергия, 1973, с. 16—19.
20.	Воробьев Н. Н. Вопросы математизации принятия решений на основе экспертных оценок. — Материалы VI симпозиума по кибернетике, ч. III, Тбилиси, 1972, с. 47—51.
21.	Гладун В. П., Ващенко Н. Д. Методы формирования понятий на ЦВМ. Обзор. Изв. АН УССР. — Кибернетика, 1975, № 2, с. 107—112.
22.	Глушков В. М. О прогнозировании на основе экспертных оценок. — Кибернетика, 1969, № 2, с. 2—4.
23.	Глушков В. М. Введение в кибернетику. — Киев: Наукова думка, 1964. — 324 с.
24.	Глюшинский В. Г., Флиорент Г. И. Теоретические основы инженерного прогнозирования. — М.: Наука, 1973.—228 с.
25.	Голендер В. Е., Розенблит А. Б. Вычислительные методы конструирования лекарств. — Рига: Зинатне, 1978. — 232 с.
26.	Горелик А. Л., Скрипкин В. А. Построение систем распознавания.— М.: Советское радио, '1974. — 224 с.
27.	Структура алгоритмов автоматизированной системы диспетчерского управления режимами ЕЭС СССР/ В. М. Горнштейн, М. Г. Портной, В. Н. Силаков и др. — В кн.: Разработка математического обеспечения ОАСУ «Энергия». — Кишинев: Штиинца, 1973, с. 36—42.
~28	. Гублер р. В. Вычислительные методы распознавания патологических процесов. — Л.: Наука, 1970. — 381 с.
29.	Гумбель Э. Статистика экстремальных значений. — М.: Мир, 1965. — 408 с.
30.	Добров Г. И. Прогнозирование науки и техники. — М.: Наука, 1968. —209 с.
31.	Дуда Р. О., Фоссум X. Классификация образов посредством последовательно определяемых линейных и кусочно-линейных разделительных функций..— В кн.: Техническая кибернетика за рубежом.— М.: Машиностроение, 1968, с. 34—58. >
32.	Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 19'76. — 512 с. ’
33.	Завалишин Н. В., Мучник И. Б, Лингвистический (структурный) подход к задаче распознавания образов. — Изв. АН СССР. Автоматика и телемеханика, 1969, № 8.
73
34.	Журавлев Ю. И., Камилов М. М., Туляганов Ш. Е. Алгоритмы вычисления оценок и их применение. — Ташкент: Фан, 19*74.— 120 с.
35.	Загоруйко Н. Г. Методы распознавания и их применение. — М.: Советское радио, 1972 —206 с.
36.	Загоруйко Н. Г. Современное состояние проблемы распознавания образов. — В кн.: Вычислительные системы СО АН СССР. — Новосибирск, вып. 10, 1964, с. 4—44.
37.	Ивахненко А. Г. Самообучающиеся системы распознавания и автоматического управления. — Киев: Техника, 1969. — 328 с.
38.	Карп В. П., Кунин П. Е. Метод направленного обучения в переборной схеме М.. М. Бонгарда и онкологическая диагностика.—В кн.: Моделирование обуения и поведения. — М.: Наука, 1975, с. 7—17.
39.	Касавин А. Д. Адаптивные алгоритмы кусочной аппроксимации в задачах идентификации — Изв. АН СССР. Автоматика и телемеханика, 1972, № 12, с. 3—5.
40.	Ковалевский В. А. Корреляционный метод распознавания изображений. — Журнал вычислительной математики и математической физики, 1962, № 4, с. 16—27.
41.	Ковалевский В. А. Методы оптимальных решениц в распознавании изображений. — М.: Наука, ’1976. — 328 с.
42.	Кокс Дж., Нолл Ф., Артур Р. Анализ электроэнцефалограмм, кривых кровяного давления и электрокардиограмм на цифровой вычислительной машине Обзор. — ТЦИЭР, № 10, т. 60, 1972, с. 181—205.
43.	Льюс Р. Д., Райфа X. Игры и решения.—М.: Изд-во иностранной литературы, 196'1.— 642 с.
44.	Математические методы в социальных науках/ Под ред. П. Лазарфельда, Н. Генри. — М.: Наука, 1973. — 352 с.
45.	Медицинская информационная система/ Под ред. Н. И. Амосова.— Киев: Наукова думка, 1975. — 508 с.
46.	Миленький А. В. Классификация сигналов в условиях неопределенности.— М.: Советское радио, 1975.— 135 с.
47.	Минский М., Пайперт С. Перцептроны. — М.: Мир, 1971.— 264 с.
48.	Миркин Б. Г. Проблема группового выбора. — М.: Наука, 1974.— 342 с.
49.	Моделирование обучения и поведения. Сборник статей. — М.: Наука, 1975. —237 с.
50.	Морозов Ю. И., Поповян С. С. Анализ влияния типа лидерства на поведение коллектива в ситуациях выработки решений. — Материалы VI симпозиума по кибернетике. Ч. III. — Тбилиси. 1972.
51.	Мучник И. Б. Алгоритм формирования локальных признаков для зрительных образов. — Изв. АН СССР. Автоматика и телемеханика, 1966, № 10, с. 88—99.
52.	Надь Г. Распознавание образов. Обзор. — ТИИЭР, т. 56, № 5, 1968, с. 57—86.
53.	Нильсон Н. Обучающиеся машины. — М\ Мир, 1967.— 180 с.
74
54.	11ашичев П. Л., Руденко Ю. Е., Ушаков Е. И. Оценка статической устойчивости электроэнергетических систем с применением вероятностно-статистических методов. — Изв. АН СССР. Энергетика и транспорт, 19'73, № 3.
55.	Перцептрон — система распознавания образов/ Под ред А. Г. Ивахненко. — Киев: Наукова думка, 1975. — 432 с.
56.	Раудис Ш. Алгоритмы построения правила классификации. Статистические проблемы управления, — Вильнюс, 1975, Вып. 11, с. 11—53.
57.	Раудис Ш. Ограниченность выборки в задачах классификации. Статистические проблемы управления, вып. 18. — Вильнюс: 1976, Вып. 18, 185 с.
58	Растригин Л. А. Статистические методы поиска. — М.: Наука, 1968. — 376 с х
59.	Растригин Л. А., Андреев Н. А., Эренштейн Р. X. Об одной модели консилиума. — В кн.: Адаптивные системы. — Рига: Зинатне, 1972, Вып. 2, с. 16—25.
60.	Растригин ,Л. А., Эренштейн Р. X. Коллектив решающих правил как метод классификации. — Тезисы Международного симпозиума «Теоретические проблемы распознавания образов и ситуаций».— Варна: 1972, с. 29—30.
61.	Растригин Л. А., Эренштейн Р. X. О принятии решения коллективом решающих правил. — Изв. вузов. ЛИТМО. Приборостроение, т. XVI, 1973, № 11, с. 31—35.
62.	Растригин Л. А., Эренштейн Р. X. Об оптимальном разнообразии коллектива линейных решающих правил. — В кн.:4 Адаптивные системы. Вып. 3. — Рига: Зинатне, 1973, с. 25—34.
63.	Растригин Л. А., Эренштейн Р. X. Некоторые методы принятия коллективного решения при классификации ситуаций. — Материалы III Всесоюзного совещания по статистическим методам в процессах управления. Вильнюс. Ч. 1. — М.: Наука, 1973, с. 46—48.
64.	Растригин Л. А., Эренштейн Р. X. Обучение коллектива решающих правил. — В кн.: Адаптивные системы. Вып. 4. — Рига: Зинатне, 1974, с. 64—78.
65.	Растригин Л. А., Эренштейн Р. X. Эвристический алгоритм се’лекции коллектива решающих правил. — В кн.: Распознавание образов. Вып. 1.— Рига: Зинатне, 1974, с. 8—20.
66.	Растригин Л. А., Эренштейн Р. X. Коллектив алгоритмов для обобщения алгоритмов решения задач. — Изв. АН СССР. Техническая кибернетика, 1978, № 2, с. 116—126.
67.	Растригин Л. А., Эренштейн Р. X. Принятие решений коллективом решающих правил в задачах распознавания образов. — Изв. АН СССР. Автоматика и телемеханика, 1975, № 9, с. 134—144.
68.	Растригин Л. А., Эренштейн Р. X. Коллектив алгоритмов. Материалы IV Международной объединенной конференции по искусственному интеллекту. — М.: 1975, т. 3, с. 138—144.
69.	Распознавание образов и медицинская диагностика/ Под ред. Ю. И. Неймарка. — М.: Наука, ^972. — 328 с.
70.	Репин В. Г., Философов Л. В. Об оптимальном совместном использовании алгоритмов распознавания. — Изв. АН СССР. Радиотехника и электроника, 1969, 14, № 6, с. 73—78.
75
71.	Розенблатт Ф. Принципы нейродинамики. — М.: Мир, 1965.— 450 с.	*
72.	Семенов В. А., Совалов С. А., Черня Г. А. Требования к АСДУ, связанные с обеспечением надежной работы ЕЭС СССР.— Доклады на III Всесоюзном научно-техническом совещании по устойчивости и надежности энергосистем СССР.—М.: Энергия, 1973, с. 115—118.
73.	Слейгл Дж. Искусственный интеллект. — М.: Мир, 1973.— 320 с.
74.	Себестиан Г. С. Процессы принятия решения при распознавании образов. — Киев: Техника, 1965.— 152 с.
75.	Совалов С. А., Семенов В. А. Сравнительный анализ программ расчета на ЦВМ статической устойчивости энергосистем. — В кн.: Доклады на III Всесоюзном научно-техническом совещании по устойчивости и надежности энергосистем СССР. — М.: Энергия, 1973, с. 110—114.
76.	Сочивко В. П. Электронные опознающие устройства. — М.: Энергия, 1964. — 56 с
77.	Ту Дж., Гонсалес Р. Принципы распознавания образов. — М.: Мир, 1978. —4112 с.
78.	Уилкс С. Математическая статистика. — М.: Наука, 1967. — 632 с.
79.	Файн В. С. Опознавание изображений. — М : Наука, 1970.— 296 с.
80.	Феллер В. Введение в теорию вероятностей и ее приложения.— М.: Мир, 1967. — 498 с.
81.	Француз А. Г. Об -одном алгоритме опознания образов.— Изв. АН СССР. Техническая кибернетика, 1965, № 5, с. 18—26.
82.	Фу К. Последовательные методы в распознавании образов и обучении машин.—М.: Наука, 19'71. — 256 с
83.	Фу К. Структурные методы в распознавании образов. — М.: Мир, 1977.-^320 с.
84.	Хант Э. Искусственный интеллект. — М.: Мир, 1978. — 558 с.
85.	Хант Э., Марин Дж., Стоун Ф. Моделирование процесса формирования понятий на вычислительной машине. — М.: Мир, 1970 —302 с.
86.	Цыпкин Я. 3. Адаптация и обучение в автоматических системах.— М.: Наука, 1968. — 400 с.
87.	Цыпкин Я. 3. Основы теории обучающихся систем. — М.: Наука, 1970. — 253 с.
88.	Чавчанидзе В. В. Аналитическое решение задач формирования понятий и распознавание образов. Сообщения ИК АН ГССР. Изд. ИК АН ГССР /репринт/, 1970, с. 10—14.
89.	Шестаков О. А. Количественная экспертная оценка в краткосрочном прогнозировании. — Изв. АН СССР. Автоматика и телемеханика, 1972, № 8, с. 15—20.
90.	Шляпенштох В. Э. Kai? сегодня изучать завтра? — М: Советское радио, 1975. — 253 с.
91.	Якубович В. А. Некоторые общие теоретические принципы построения обучаемых опознающих систем. — Вычислительная тех-76
ника и вопросы программирования. Вып. 4. — Изд-во ЛГУ, 1965, с. 72—96.
92.	Arrow К. J. Social Choise and Individuals Values. — N.—Y., 1952.*
93.	Pattern .Recognition and Micro-economics/ J. M. Blin, K. S. Fu. К. B. Moberg, A. B. Whinston — Proc, of the International Conference on Cybernetics and Society, October, 1972, № 443, p. 1—4.
94.	Blin J. M., Fu K. S., Whinston A. B. Application of Pattern Recognition to some Problems in Economics. — Techniques of Optimisation. Ed. A. V. Balakrishnan, 1972, № 416, p. 1—18.
95.	Kanal L. Interactive Pattern Analysis and Classification. Systems a Survey and Commentary.— Proc, of the IEEE, 1972, vol. 60, № 10, p. 1200—1215.
96.	Fix E., Hodges J. L. Nonparametric discrimination. — Technical Report 11, Rendolph Field. — Texas, 1952.
97.	Cournot A. A. Exposition de la theorie des chances. — Paris: 1843, 213—214.
98.	Распознавание образов/ Под ред. И. Т. Турбовича — М.: Наука, 1977 — 128 с.
9^	. Джуре П., Айзенауэр Т. Распознавание образов в химии.— М.: Мир, 1977. —232 с.
100.	Карелина А. В., Печерский Ю. Н. Теоретико-графические методы в распознавании образов. — Кишинев: Штиинца, 1978.— 92 с.
'101	. Гренадер У. Лекции по теории образов. Т. 1. — М.: Мир, 1979. —334 с.
10*2	. Фукунага К. Введение в статистическую теорию распознавания образов. — М.: Наука, 1979. — 367 с.
103.	Описание и распознавание объектов в системах искусственного интеллекта/ Под ред. В. С. Гурфинкеля и В, С. Файна — М.: Наука, 1980. — 137 с.
104.	Классификация и кластер/ Под ред. Дж. В. Райзина—М: Мир, 1980. — 390 с.
105.	Уинстон П. Искусственный интеллект. — М.: Мир, 1980.— 519 с.	к
106.	Фишберн П. Теория полезности для принятия решений.— М.: Наука. 1978. — 352 с.
107.	Айзерман М. А., Малишевский А. В. Некоторые аспекты общей теории выбора лучших вариантов. Препринт. — М.: ИПУ АН СССР, 1980. — 36 с.
108.	Айзерман М. А., Малишевский А. В. Проблемы логического обоснования в общей теории выбора. Общая модель выбора и его классически рациональные основания. Препринт. — М.: ИПУ АН СССР, 1980.—72 с.
109.	Некоторые вопросы теории распознавания образов в управлении/ Л. А. Растригин, Ю. И. Неймарк, А. Б. Глаз и др. — Рига: МИПК СНХ, 1979. — 109 с.
77.
110.	Решение некоторых практических задач распознавания образов/ М. Н. Либензон, Ш. Ю. Раудис, А. Б. Глаз, Р. X. Эренштейн. Учебное пособие. — Рига: МИПК СНХ, 1980. — 88 с.
111.	Эренштейн Р. X. Коллектив алгоритмов принятия решений и параллельные вычисления в микроэлектронике. — Изв. АН СССР. Микроэлектроника, 198*1’, № 1, с Ы9>—68.
112.	Растригин Л. А. Современные принципы управления сложными объектами.—М.: Советское радио, 1'980. — 260 с.
ИЗ. Растригин Л. А. Искусственный интеллект, адаптация и микроэлектроника. — Микроэлектроника: 1984, № 1, с. 4—25.
114. Синтез структуры решающего правила методами многомерной линейной экстраполяции/ Л. А. Растригин, А. Б. Глаз, Т С. Ямпольская. — Автоматика, 497Й, № 5, с 3—7.
145. Джандиери И. В., Растригин Л. А. Об одном способе синтеза алгоритма распознавания. — В кн.: Динамика систем. Оптимизация и адаптация. — Горький, ГГУ, 1979, с. ’168—179.
116. Адаптация случайного поиска/ Л. А Растригин, К. К. Рипа, Г. С. Татасенко. — Рига: Знатне, 1978. — 340 с
117. Один подход к оптимизации коллектива решающих правил/ И. В. Джандиери, Л. А. Растригин, Р. X. Эренштейн. — В кн.: Структурная адаптация сложных систем управления. — Воронеж: ВПИ, 1977. с. 54—63.
ОГЛАВЛЕНИЕ
Предисловие...............................................,	3
Введение ....................................................... 4
В.1. Идея распознавания образов	(краткий	обзор)	.	.	4
В.2. Иерархические системы распознавания	....	10
Глава первая. Коллектив решающих правил в задаче распознавания .............................................13
li. 1. Общая схема коллектива...........................13
1.2.	Алгоритмы выделения областей компетентности решающих правил .	..........................16
1.3.	Метод априорного задания областей компетентности 25
1.4.	Эксперименты с коллективом на модельных задачах 27
Глава вторая. Синтез оптимального коллектива решающих правил............................................  32
2.1.	Задача оптимизации коллективного	решения ...	32
2.2.	Эвристический	алгоритм селекции........................34
2.3.	Эксперименты	на модельных задачах.....................39
2.4.	Анализ аппроксимационных свойств работы коллектива ....................................................43
Глава третья. Распознавание областей статической устойчивости с помощью коллектива............................45
3.1. Постановка задачи прогноза нарушений статической апериодической устойчивости режима работы энергетической системы.................................45
3.2. Эксперименты . х................................50
Глава четвертая. Распознавание	коллективом	экспертов	58
4.1.	Проблема коллективного решения................. 58
4.2.	Анализ электрокардиосигналов	коллективом	экспертов	61
4.3.	Задача краткосрочного прогноза и решение ее коллективом экспертов........................ .............65
Заключение....................................67
Список литературы....................................,	72
ЛЕОНАРД АНДРЕЕВИЧ РАСТРИГИН, РОМАН ХОНОНОВИЧ ЭРЕНШТЕЙН
МЕТОД КОЛЛЕКТИВНОГО РАСПОЗНАВАНИЯ
Редактор П. В. Ермуратский
Редактор издательства Л. Д. Никулина
Технический редактор А. С. Давыдова Корректор Г. А. Полонская
ИБ № 964 («Энергия»)
Сдано в набор 25.03.81. Подписано в печать 04.06.81.	Т-05889
Формат 84Х10в/эа« Бумага типографская Ns 3. Гарнитура литературная.
Печать высокая.	Усл. печ. л. 4,2.	Уч.-изд. л. 5,63.
Тираж 8500 экз.' Заказ 1107 Цена 30 к.
Энергоиздат, 113114, Москва, М-114, Шлюзовая наб., 10
Московская типография № 10 Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 113114, Москва, М-114. Шлюзовая наб., 10
Цена 30 к.