Условия корректности алгебраических замыканий эвристических алгоритмов распознавания

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

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

Пусть множество объектов X покрывается двумя непересекающимися классами К^ и и задано т объектов обучения >" '?^т • Будем считать, что каждый объект ОС, представляет собой вектор размерности П, т. е. ,",)) 9 координаты которого принимают вещественные значения. Для каждого из обучающих' объектов ЗС,, Х2, ? 0Ст известно, в какой из классов он входит. Распознающий алгоритм задается набором чисел коэффициентов, определяющих гиперплоскость п Zji = О в евклидовом пространстве признаков. Классификация новых объектов происходит по следующему правилу: объект ОС заносится в класс, если X лежит в «положительном» (т.е.^^^^" '^?//^ О) полупространстве и заносится в класс Ki, если ЭС, лежит в «отрицательном» (т. е. ^ + /" + fa < 0) полупространстве определенных гиперплоскостью^. Функционалом качества здесь является отношение числа правильно классифицированных объектов обучения к числу всех объектов в обучении. Необходимо найти алгоритм (т.е. определить коэффициенты^ гиперплоскости R), максимизирующий функционал качества. Для этого условия правильной классификации каждого из объектов обучения, ><�" y&jn), j~1>2-?>n?m запишем в виде системы линейных неравенств г + «' +/» + fa+4 Л О • • ¦ • • # ф fa + -• + у" fyn i-ун+л > О +" <+ fa O-Lh* + fa+4 < CP.

Ф «» • «• t y4 < &.

Решение^, эт°й системы в случае ее совместности определяло бы алгоритм, точно классифицирующий объекты обучения. Но данная система в общем случае является несовместной. Выделив из этой системы максимальную совместную подсистему и решив ее, мы получим значения параметров экстремального алгоритма. В свою очередь, решение задачи о выделении максимальной совместной подсистемы в системе линейных неравенств потребовало разработки специальных методов [*32],[33].

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

Как известно, исходные семейства (множества) распознающих алгоритмов строятся на различных принципах, таких как: принцип разде-ления[" б}, [*13], частичной прецедентности £[б], потенциалов [i]- на структурных [3б],[39], на статистических [б, 2] принципах и т. д. И выбор того или иного алгоритма исходной совокупности эвристик для решения конкретной задачи осуществляется некоторой процедурой, требующей либо, в общем случае, значительных вычислительных усилий и не гарантирующей при этом высокую точность распознавания, либо существование сильных ограничений на обучающую информацию при удовлетворительной точности распознавания [ 26J • Однако, в ряде случаев известны условия, гарантирующие математическое обоснование применимости эвристических алгоритмов при решении конкретных задач C&J • На практике проверка этих условий затруднительна ввиду недостаточности априорной информации в задачах распознавания. Поэтому часто обоснованием применимости эвристических алгоритмов при решении новых прикладных задач является большое число решенных с их помощью и с приемлемой точностью задач распознавания в различных областях естествознания. Таким образом, важной задачей теории распознавания на втором этапе является задача создания численных методов для решения прикладных задач и их теоретическое или экспериментальное обоснование. Целью теоретического подхода является определение корректных множеств алгоритмов для задач распознавания, т. е. множеств алгоритмов, содержащих для каждой конкретной задачи точно её решающий алгоритм.

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

Основы такой общей алгебраической теории были заложены в ряде работ Журавлева Ю. И. f10, II, 12,13,14,15]. Другим общим подходом к проблеме распознавания является подход, развитый в работах Гренандера У. L^lj .

Подход, предложенный Ю. И .Журавлевым, является принципиально новым, поскольку позволяет строить корректные (абсолютно точные) алгоритмы, не изменяя начальной задачи, т. е. задачи синтеза корректных алгоритмов. Тогда как ранее, в основном, сужали постановку задачи (выбор конкретного функционала качества), и задача синтеза корректного алгоритма сводилась к экстремальной задаче поиска? — оптимальных алгоритмов. При этом сходимость по? к оптимальному алгоритму гарантировалась не всегда. В качестве функционалов в экстремальных задачах брались различные разумные фун-кципналы, например, функционал i l^(tor F (x (>d)f суммарного риска3 fy — число объектов в контроле [ 6 J. Таким образом понятие корректного алгоритма подменялось понятием оптимального алгоритма. Благодаря тому, что в алгебраической теории для. ¦ синтеза корректных алгоритмов требуются чрезвычайно простые операции над матрицами, такие алгоритмы легко реализуются на ЭВМ, и, более того, аналитический вид корректных алгоритмов удобен для их естественного распараллеливания на современных многопроцессорных ЭВМ С38] .

Приведем необходимые определения и утверждения из [ 10,11,12].

Пусть{Д| - множество допустимых объектов, а X — множество описаний, соответствующее множеству /. Элементами множества X являются И — мерные векторы, при этом множество J (также есть декартово произведение множеств «где fc» — множество чисел, являющееся областью значений С — го признака. g.

ПустьX^P^Kj j /^-классы.

Рассмотрим множество одноместных предикатов. Каждый предикат Р> определен на множестве X •.

PjW="xeKj" t j*i"u, e} хеХ,.

Информационной строкой ol (объекта ЭС{ t ЭС{ € У по системе предикатов i^,) Р (является строка =*(fLfacUg^jdig), *L{j =: lj'(X{), Пусть далее / «f'jXiti}- множество допустимых объектов, для которых информационные строки по предикатам fys fy/» '/ fy известны, тогда за начальную информацию некоторой задачи Z возьмем множествоМножество таких начальных информаций обозначим через Ца}ф Задача Z есть пара 4 1)(/>, где / г множество допустимых объектов, для которых информационные строки по предикатам ft. А. ,. // необходимо вычислить. Множества от ъЪ, * - ч.

J, X называются обучающей и контрольной выборками соответственно. Обозначим через.

К/ = УтП к-, ?. Условие yCL, J ^ * > «.

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

Определение I. Матрица II Hqyt называется информа.

Г7 Г Т/Я* ционной матрицей набора ОС^, (задачи %) по системе предикатов fy ^" jfy '.

Рассмотрим совокупность алгоритмов распознавания.

АУ.

Определение 2. Алгоритм, А из называется корректным для задачи Z, если, А по задаче Z вычисляет информационную матрицу задачи? , т. е.) ~ H^-tj *.

Алгоритм, А, не являющийся корректным для задачи Z, называется некорректным.

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

В рамках алгебраической теории распознавания может быть поставлена и в ряде случаев решена следующая задача: для заданного множества задач j" распознавания выделить в алгебраическом замыкании tfliA} «априори заданного подкласса алгоритмов i^J, множество {Д^} алгоритмов, среди которых находится алгоритм, точно решающий заданную задачу Z* из {Zi< Более того, часто удается выделить конечное множество алгоритмов, среди которых находится корректный для задачи Z* алгоритм, и указать его аналитический вид.

Очевидно, что доказательство корректности требует существования некоторых ограничений на обучающую информацию и на связи этой информации с описанием задачи и описанием алгоритмовранее в работах С2, 3, 4, 10, II, 12, 13, 14, 17, 18, 36, 28, 30 J была доказана корректность над задачами со стандартной обучающей информацией алгебраических замыканий следующих семейств эвристик: потенциалов, алгоритмов вычисления оценок, структурных, статистических и алгоритмов, порождаемых кусочно-линейными поверхностями и параметрами.

Представляет интерес также проблема построения корректных замыканий над задачами с бинарной обучающей информацией для алгоритмов типа «тестовых» и типа «Кора», широко используемых при решении прикладных задач, а также уточнения результатов для алгоритмов, основанных на принципе разделения. В Гю, 1Ъ] предложен вял алгоритма распознавания, в который укладываются все существующие типы алгоритмов, и была доказана теорема о каноническом представлении алгоритмов из множества iA}.

Теорема I. Каждый алгоритм представим как последовательное выполнение алгоритмов $ и С, где & алгоритмический оператор, С — решающее правило, причем b (Z) =11 а^цеЩ flfjвещественное число, I -4,"/"/, р J = :/,"/,.

Из теоремы I, следует, что множество J Л} порождает множества { 3 I и f С} <

Определение 3. Решающее правило С называется корректным на X «если Для всякого конечного набора Xj, Тг fltlJ объектов из X существует хотя бы одна числовая матрица Ч dtj Н<1/(, такая, что С (II Q-ij llp, fj^, где.

1Ц*Г инФ°РмаЧионная матрица элементов ХЛ) по системе предикатов Pj > Р^ }", j Pf. Корректное решающее правило будем обозначать через С* •.

В множестве операторовj Qj легко вводятся операции сложения, умножения и умножения на скаляр:

Пусть i’t b- 8', 8″ e W, Ь’ЩЦя^ьиМф^ШЬ У тогда.

S^lltk'ijll^, (I).

B’tB f (2).

8'- B" = ila-j-ajj — (8,.

Замыкание множества относительно операций (I), (2) является линейным замыканием и обозначается через ЫВ}.

Замыкание множества операторов {В} относительно операций (I) — (3) является алгебраическим замыканием множества операторов { Й/ и обозначается через llilb}.

Нетрудно видеть, что алгебраическое замыкание И i 8} остоит из операторных многочленов, т. е. если & € с то.

Максимальное число сомножителей-операторов в слагаемом является степенью многочлена^. Пусть.

U4B}.

— совокупность операторных многочленов степени не выше. Ясно, что.

Множество.

21кЩ (WW) называется алгебраическим замыканием степени k множества операторов *tВ} (алгоритмов У, А }).

Пусть — задача, обозначим через ШЛ — множество матриц таких, что & € (Й, ГАЕ.

Определение 4. Если множество содержит базис в пространстве матриц размерности fyfi, то задача Z называется полной относительно ?) С.

Теорема 2. f" 10J Если множество *f 2 } состоит только из задач, полных относительно, то линейное замыканиеL /<4) множества алгоритмов является корректным над •/ Z.

Следствие 1.1ЖПусть { A J — совокупность некорректных алгоритмов, f В} «соответствующее множество операторов, С^ - К°Р» рентное решающее правило. Тогда Ь iAj-'i h{&} является корректным относительно «/2} «если f Z} состоит из задач полных относительно { $ j.

Следствие 2. Й01.Пуоть выполнены все условия следствия I, тогда является корректным над jZj «если «iZj состоит из задач, полных относительно ^//Й],.

Определение 5. Алгебраическое замыкание tyt^iВ}} k>i называется квази-полным для множества задач J Zf «если для любой задачи Z из jZt} в В} существуют операторы.

Bet ф 1r ^mijty') J — l/tuj t такие, что для матрицы оператора й f hj) {Z) «Л следУюп*ие соотношения.

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

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

Пусть jZ } - множество регулярных задач, JAJff В}) -подкласс алгоритмов (операторов) вычисления оценок [ XXJ .

Алгебраическое замыкание 411 DJ является квази-полным для W В) iZU i B (hJ)}f-l — квази-базио Ш/SJ.

Ю"И.Журавлевым в Г12] найден аналитический вид корректных алгоритмов для этого случая и доказана.

Теорема 3. Корректный алгоритм /} для задачи % из /2/ можно представить в виде л f '.

Ui J где II «ttj ll.

Z,, Скорректное решающее правило с параметрами Сц^С^^ Сц^Сцу И 'V Q’JlIp}матрща опе^т°Ра В (bj)P = > Ъ — maх c<4>l, для вычисления J< имеет место формула ' lty- + l"f. + ih (C4+ci)iinci.

I thai.

В каждом конкретном случае формула для вычисления k зависит от способа построения операторов B (l>tJ)j.

Как было показано в последующих публикациях [l7, 18, 19, 27? корректный алгоритм, представленный в виде (I) обладает рядом полезных свойств, тем самым стало ясно, что приведенное выше Ь L представление корректного алгоритма удобно для теоретических исследований. Ввиду многократного использования программ, реализующих корректные алгоритмы, естественной является также задача синтеза простых корректных алгоритмов 18, 28″ ], В данной работе упрощение корректных алгоритмов производится за счет дальнейшей параметризации исходной совокупности эвристических алгоритмов. Однако, при этом остается открытым вопрос о емкости алгебраических замыканий параметризованной совокупности эвристических алгоритмов Г 27 ],.

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

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

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

Диссертация состоит из трех глав, введения и списка литературы. Объем работы страниц.

Доказательства приведенных в работе утверждений в ряде случаев опираются на результаты из С 10, II, IZ3 .

По теме диссертации опубликованы две работы. Основные результаты работы докладывались на I Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации (Алма-Ата, 1981), на семинаре лаборатории проблем распознавания ВЦ АН СССР, на семинаре по теории автоматов механико-математического факультета МГУ (1У конференция молодых ученых механико-математического факультета, М., 1982).

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

Ранее дщ доказательства корректности алгебраических замыканий алгоритмов вычисления оценок над задачами со стандартной обучающей информацией использовались системы опорных множеств JfZ^-'i'Ub ,&bdquo->Щ} жтЛ0 совместно с SL^ ~ У ft}, Возникал естественный вопрос: можно ли строить корректные алгоритмы в алгебраическом замыкании алгоритмов вычисления оценок с использованием произвольной системы опорных множеств. В частности, когда система опорных множеств состоит из тупиковых тестов матрицы обучения, подмножеств множества признаков одинаковой мощности к, представительных наборов / 5J и т. д.

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

В диссертации рассматриваются системы опорных множеств удов.

— V летворяющие следующему специальному условию: если — элемент системы опорных множеств XL, то М Ф U (л) io'&SL. п 7.

Систему опорных множеств Jt., удовлетворяющую этому условию, будем называть базой множества признаков {ij 2jtttJ П Доказана корректность алгебраических замыканий подклассов i, А <&, е, ШТ^ Лсг>и Н р! r^trfim над множествами «SL — нормальных, невырожденных задач соответственно. Следствием изложенных результатов являются аналогичные результаты для тестовых алгоритмов.

Указан аналитический вид алгоритма, корректного для рассматриваемой задачи Z ,.

Во второй главе диссертации рассматриваются подклассы.

1А ШrfafftM алгоритмов типа «Кора» и множества задач с бинарной обучающей информацией. Алгоритмы подобного типа используются при решении прикладных задач С 7 ].

Каждому алгоритму из рассматриваемых подклассов также соответствует база множества бинарных признаков 4 4? 2 t м, Я }, являющаяся совокупностью опорных множеств для данного алгоритма. В частности, в качестве бызы могут быть использованы: некоторое множество тупиковых тестов матрицы обучения^Ttimf (2″ 3 «некоторые подмножестаадлинн 3 множества 4 i } 2,, tjh j t.

Доказано, что алгебраическое замыкание подкласса алгоритмов j) ft* jf^Cf Л)/яВЛяется корректным над множеством Л регулярных задач. Алгебраическое замыкание подкласса алгоритмов корректно над множеством задач, объемлющем множество — регулярных задач. Указан также явный вид корректного алгоритма для решения рассматриваемых задач.

В третьей главе диссертации рассматриваются подклассы распознающих алгоритмов.

1ве диссертации рассматриваются подклассы рас iA'(Bj, l>i> iftikjrju. tM порождаемых кусочно-линейными поверхностями и параметрами, причем.

А'}с1А" },.

Для операторов (алгоритмов) из множества ^/г^/оценка объекта ОС следующим образом >j. nd за класс К d вычисляется.

Г11 «t Го о rj + г№ nd nd HP t I 04 если.

R (x)>0.

2) если J? (ОС) < О.

Г4 + Г4 «Н '.

Ча т 1 *t> 1.

Для операторов (алгоритмов) из множества.

К/*)} ($" (№/*?,&)}) оценка объекта СС (за класс И/ вычисляется так:

I V. f/w- <

AowQi +Ма<�хоГн t/ijxo ГД +1 з).

R — кусочно-линейная поверхность, раделяющая два непересекающихся конечных множества объектов в X > >"•"j jj’m «веса» объектов из обучения, у^СЛ^ 6.

Эти алгоритмы (операторы) подробно описаны в Г 10,14,15]. В §§ 1−3 главы 3 приводятся доказательства теорем о корректности линейных и алгебраических замыканий данных подклассов над множествами задач со стандартной обучающей информацией. Таким образом результаты главы 3-ей дополняют результаты, изложенные в Гю, 14,151 .

Рассмотрим множество задач { Z} f10] таких, что каждая задача Z из iZ} удовлетворяет следующим условиям:

I. HtfHf, t=4″", lР-A,., t-^tfl^J.

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

Пусть La — > JС.

— невырожденная задача. Класс Kj flO, 14] называется изолированным в Z, если существуют классы t lit) Kv j 1 < Fjti Р такие, что.

1. Ъ С .

2. 14 с ^.

3. fy.

Рассмотрим множество задач {Z^j flO, 14] дая задача Z из «{ Z4} является невырожденной и кроме того классы }, 1- l^j не являются изолированными в Z •.

Пусть — ftзадача. Пара классов, назы— z.

1. Ки Uky^ X •.

2. КиПКу т таких, что кажвается изолированной в Zu, если лг ^.

T K/fy.

Невырожденная задача Z =J? называется детерминированной, если начальная информация задачи 2 не содержит изолированных пар клаосов.

Множество детермированных задач обозначим через JZcj. Очевидно, что.

В работе if 10, I4-] доказаны следующие теоремы: Теорема 4. [ 10J Линейное замыкание >4 ') класса алгоритмов m-m с произвольным корректным решающим правилом С^ и операторами (В} определенными соотношением (3), является корректным над множеством задач { Zj J,.

Теорема 5.? 103 Совокупность алгоритмов корректна над множеством невырожденных задач i^}* В § I главы 3 доказана.

Теорема I.I. Множество задач jZ} является полным относительно линейного замыкания LJ В ® Q t тогда и только тогда, когда множество jZj состоит лишь из детерминированных задач.

Следствием из теоремы 1*1 является f ^ Теорема Линейное замыкание.

МАП, П} является корректным над множеством детерминированных задач iZv},.

В § а доказана ^ f ^.

Теорема 1.2. Алгебраическое замыкание юте корректно над множеством невырожденных задач /2* }t.

В § 3 доказана.

Теорема 1.3* Линейное замыкание L{/l (R, f^l/tl, Q, Сг)} корректно над множеством невыровденных задач {%},.

Автор искренне признателен Ю. ИДуравлеву за постановку задач и внимание к работе. Здесь алгоритмы из {А ') обобщают алгоритмы из множества [А'} использованные в flO, 14 J .

1. АЙЗЕРМАН М.А., БРОВЕРМАН Э.М., Р03ЕН0ЭР Л. И. Метод потенциальных функций в теории обучения машин.- М.: Наука, 1970, 384 о.

2. БАК ХЫНГ КХАНГ. О полноте модели статистических алгоритмов распознавания.- Ж. вычисл. матем. и матем. физ. 1978, т.18, I, с. 183−196.

3. БАК ХЫНГ КХАНГ. О модели распознающих алгоритмов типа потенциальных функций. Ж. вычисл.матем. и матем. физ. 1978, т.18, Ш 2, с.467−479.

4. БАК ХЫНГ КХАНГ. Достаточные условия полноты линейных замыканий алгоритмов распознавания. Кибернетика. 1978, № 4,с.I31−137.

5. БАСКАКОВА Л.В., ЖУРАВЛЕВ Ю. И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств.-Ж. вычисл.матем. и матем.физ., 1981, т.21, № 5, с.1264−1275.

6. ВАПНИК В.Н., ЧЕРВОНЕНКИС А. Я. Теория распознавания образов.- М.: Наука, 1974, 415 с.

7. ГУБЕРМАН Ш. А., МАРИПОВ Т. М. Оценка перспективности месторождений гидротермальных руд с применением ЭВМ.- Труды МИНК и ГП им. Губкина. М.: вып.62.

8. ДЮКОВА Е. В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания. Диссертация на соискание уч. степени канд. физ.-мат. наук, — М.: ВЦ АН СССР, 1979.

9. ДМИТРИЕВ А.И., ЖУРАВЛЕВ Ю.И., КРЕНДЕЛЕВ ф.П. Об одном при-ципе классификации и прогноза геологических объектов и явлений.Изв. Сиб. отд. АН СССР, сер. Геология и геофизика, 1968,№ 5, с.50−64.

10. ЖУРАВЛЕВ Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов.- Кибернетика, 1977, № 4,с.14−21.

11. ЖУРАВЛЕВ Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов.- Кибернетика, 1977, № 6,с. 21−27.

12. ЖУРАВЛЕВ Ю. И. Корректнные алгебры над множеством некорректных (эвристических) алгоритмов. Кибернетика, 1978, № 2,с. 35−43.

13. ЖУРАВЛЕВ Ю. И. Алгебраический подход к решению задач распознавания или классификации.- В кн.: Проблемы кибернетики, вып. 33, М.: 1978, Наука, с.5−68.

14. ЖУРАВЛЕВ Ю. И. Принципы построения обоснования алгоритмов для решения плохо формализованных задач.- Ж. Матем. заметки, 1978, т.23, вып.6, с.899−914.

15. ЖУРАВЛЕВ Ю. И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации. ДАН СССР, 1976, т.231, Ш 3,0.532−535.

16. ЖУРАВЛЕВ Ю.И., КАМИЛОВ М.М., ШЯГАНОВ Ш. Е. Алгоритмы вычисления оценок и их применение. Ташкент: ФАН, 1974,.

17. ЖУРАВЛЕВ Ю.И., ЗЕНКИН А.А., ЗЕНКИН А.И., ИСАЕВ Н.В., КОЛЬЦОВ П.П., КОЧЕТКОВ Д.В., РЯЗАНОВ В. В. Задачи распознавания и классификация со стандартной обучающей информацией.- Ж. вычисл. матем. и матем. физ. 1981, т.20, № 5, с.1294−1310.

18. ЖУРАВЛЕВ Ю.И., ИСАЕВ И. В. Построение алгоритмов распознавания корректных для заданной контрольной выборки.- Ж. вычисл.матем. и матем. физ. 1979, т.19, fe 3, с.726−738.

19. ИСАЕВ И. В. Программирующий комплекс с алгебраическими корректорами абсолютно точный на заданной контрольной выборке.-М.: ВЦ АН СССР, 1979, о.1−21.

20. КАТЕРИНОЧКИНА Н. Н. Поиск максимального верхнего нуля монотонной функции алгебры логики ДАН СССР, 1975, т.224, Ш 3, с.557−560.

21. КОНСТАНТИНОВ P.M., КОРОЛЕВА З. Е. Применение тестовых алгоритмов к задачам геологического прогнозирования.- Труды Международного симпозиума по практическим применениям методов распознавания образов. М., ВЦ АН СССР, 1973, с.194−204.

22. КОНСТАНТИНОВ P.M., КОРОЛЕВА З.Е., КУДРЯВЦЕВ В.Б. Комбинаторно-логический подход к задачам прогноза рудоностности.- М. Сб. Проблемы кибернетики. Вып. 31, 1976, с.5−33.

23. КОРОЛЕВА З.Е. О сравнении тестовых алгоритмов распознавания.- Ж. вычисл. матем. и матем.физ. 1975, т.15, № 3, с.749−756.

24. КУДРЯВЦЕВ В.Б., КУДРЯВЦЕВ Вит.Б. О тестовом подходе к задаче о перспективности населенных пунктов.- Сб. Исследование операций., М., ВЦ АН СССР, 1972.

25. КУЗНЕЦОВ В. Е. Об одном стохастическом алгоритме вычисления информационных характеристик таблиц по методу тестов. Сб. Дискретный анализ. Вып.: 23, Н: ИМСО АН СССР, 1973, с.8−23.

26. МАДАТЯН I.A. Построение оптимального алгоритма в одном классе задач распознавания.- Сб. работ по матем. кибернетике. Вып.1, М., ВЦ АН СССР, 1976, с.223−232.

27. МАТРОСОВ В. Л. Корректные алгебры ограниченной емкости над множеством алгоритмов вычисления оценок.- Ж. вычисл. матем. и матем.физ. 1981, т.21, Ш 5, с.1276−1291.

28. ПАВЛЙАШВИЛИ Н.Р. О методах построения корректных распознающих алгоритмов, — Дисе. канд. физ.-мат. наук.-М. 1979.

29. Пакет прикладных программ для решения задач распознавания и классификации. (ПАРК). М: ВЦ АН СССР.

30. РУДАКОВ К.В. О корректности алгоритмов распознавания типа потенциальных функций. ?. вычисл.матем. и матем. физ., 1980, № 3, с.737−744.

31. РУДАКОВ К.В. О числе гиперплоскостей разделяющих конечные множества в эвклидовом пространстве. ДАН СССР, 1976, т.231, № 6, с.1296−1299.

32. РЯЗАНОВ В. В. Оптимизация алгоритмов вычисления оценокпо параметрам характеризующим представительность эталонных строк. Ж. вычисл. матем. и матем. физ. 1976, т.16, № 6, с.1559−1570.

33. РЯЗАНОВ В.В. О выборе релаксационных алгоритмов решения систем линейных неравенств.- В сб. работ по матем. кибернет., вып. 2, М., ВЦ АН СССР, 1977, о.171−192.

34. СОЛОВЬЕВ М. А. Тесты: (Теория, построение, применение)-Н: Наука, 1978, с. 189.

35. СЛУЦКАЯ Т. Л. Алгоритм вычисления информационных весов признаков. Сб. Дискретный анализ. Вып.12. Н: ИМ СО АН СССР, 1968, с.75−80.

36. СМОЛЬЯНИНОВА З. А. Корректные алгоритмы в алгебраическом замыкании семейства алгоритмов распознавания со специальным видом обучающей информации. Ж. вычисл. матем. и матем. физ., т.19,4, 1979, с.1023−1032.

37. ЧЕГИС И.А., ЯБЛОНСКИЙ С. В. Логические способы контроля электрических схем.- Труды Матем. инст.им. В. А. Стеклова, т.51, 1958, с.270−360.

38. ФАДЕЕВ Д.К., ФАДЕЕВА В. Н. Параллельные вычисления в линейной алгебре.- Кибернетика, 1977, № б, с.28−40.

39. ФУ К. Структурные методы в распознавании образов.- М.: Мир, 1977.

40. ДЮСЕМБАЕВ А.Е. О корректности алгебраических замыканий распознающих алгоритмов типа «тестовых» .- I. вычисл.матем. и матем. физ., т.22, N2 6, 1982, с.1491−1499.

41. ДЮСШБАЕВ А. Е. Корректность алгебраических замыканий распознающих алгоритмов типа «Кора» 1У Конференция молодых ученых механико-математического ф-та МГУ, М., 1982,.

42. ДЮСЕМБАЕВ А. Е. Достаточные условия корректности алгебраических замыканий распознающих алгоритмов типа «Кора» .- I. вычисл. матем. и матем. физ. (сдано в печать).