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

• Автор: Дюсембаев, Ануар Ермуканович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Алма-Ата
• Количество страниц: 87 c. : ил

* Глава I. КОРРЕКТНОСТЬ АЛГЕБРАИЧЕСКИХ ЗАМЫКАНИЙ РАСПОЗНАЕШЬ АЛГОРИТМОВ ТИПА ’’ТЕСТОВЫХ"

I. Основные понятия

§ I. Связь нормальных задач с системами опорных множеств. Корректность {А} над множеством Л, - нормальных задач

§ 2. Построение корректных алгоритмов для

невырожденных задач

Глава 2. КОРРЕКТНОСТЬ АЛГЕБРАИЧЕСКИХ ЗАМЫКАНИЙ

РАСПОЗНАЕШЬ АЛГОРИТМОВ ТИПА "КОРА"

§ I. Основные понятия

§ 2. Корректность алгебраического замыкания

над множеством Л - регулярных задач

§ 3. Корректность алгебраического замыкания Ш} над множеством л - слаборегулярных задач
Глава 3. ПОЛНОТА МНОЖЕСТВА ЗАДАЧ ОТНОСИТЕЛЬНО ЗАМЫКАНИЙ РАСПОЗНАЕШЬ ОПЕРАТОРОВ, ПОРОЖДАЕМЫХ
КУСОЧНО-ЛИНЕЙНЫМИ ПОВЕРХНОСТЯМИ И ПАРАМЕТРАМИ
§ I. Полнота детерминированных задач относительно линейного замыкания ив '(в, /т)}
§ 2. Корректность алгебраического замыкания Ш над множеством невырожденных задач
§ 3. Полнота множества невырожденных задач
относительно иЗ"(В/Т/)}
ЛИТЕРАТУРА
Теория распознавания образов в процессе своего развития

прошла несколько естественных этапов. На первом этапе в конце 50 г. создавались и исследовались отдельные алгоритмы. На втором этапе развития теории для решения практических задач создавались и исследовались уже семейства эвристических алгоритмов, из которых для каждой задачи выбирался экстремальный по некоторому функционалу алгоритм.
Опишем характерный при таком подходе метод решения задачи распознавания.
Пусть множество объектов X покрывается двумя непересекающи-мися классами X и 1(г и задано т объектов обучения ЗС13Хг. , ОСт • Будем считать, что каждый объект ОС, представляет собой вектор размерности П, т.е. <£/? ) г
координаты которого принимают вещественные значения. Для каждого из обучающих' объектов 6С, , Х2 ,,,, ? известно, в какой из
классов он входит. Распознающий алгоритм задается набором чисел
коэффициентов, определяющих гиперплоскость

}/пн) ~ 2^
в евклидовом пространстве признаков. Классификация новых объектов происходит по следующему правилу: объект ОС заносится в класс , если X лежит в '’положительном” (т.е.^/^Л"^(¥^ О) полупространстве и заносится в класс , если ОС лежит в
"отрицательном" (т. е.^а1 ++ X* *** * &) полупространстве^ определенных гиперплоскостью К . Функционалом качества

здесь является отношение числа правильно классифицированных объектов обучения к числу всех объектов в обучении. Необходимо найти алгоритм (т.е. определить коэффициенты^ гиперплоскости К ), максимизирующий функционал качества. Для этого условия правильной классификации каждого из объектов обу-чения ■) т запишем в виде системы линейных неравенств
У 4 * ' " + Уп а*п * У*+4
• • • # • # •
У &*4* *"'+ У” Я'СНЛ + У»+4 < С?
.ф ' * * • * *
С/4 &П)4 + "'+Уи Ямп *+ < О
Решение^ >>> эт°й системы в случае ее совместности определяло бы алгоритм, точно классифицирующий объекты обучения. Но данная система в общем случае является несовместной. Выделив из этой системы максимальную совместную подсистему и решив ее, мы получим значения параметров экстремального алгоритма.
В свою очередь, решение задачи о выделении максимальной совместной подсистемы в системе линейных неравенств потребовало разработки специальных методов [32~}, [зз].
Следует отметить, что данным методом в различных областях естествознания, таких как: геология, химия, медицина, физика и т.д., было решено с приемлемой точностью значительное количество прикладных задач.
Как известно, исходные семейства (множества) распознающих алгоритмов строятся на различных принципах, таких как: принцип разде-летя[б], [хз], частичной прецедентности £1б], потенциалов И; на структурных [*3б], [39], на статистических [б,2] принципах и т.д. И выбор

СU€L » такое, что -v ,.<»-// л /
Зх'фсих"
Еоли задача Z—<Хо(,Х^> такова, что <^= i. , то задачу Z будем называть IL - регулярной, если она удовлетворяет условию I определения.
Задачу } , удовлетворяющую условию 2 (т.е.
выполнимость условия I не требуется) определения, будем называть SL - слаборегулярной
Приведем пример J2- регулярной задачи Zr<10)Г> :
{ ЭС, а [о, 0,0^0), Х^(С,CMC); PQi-: ГМ ,
tx>={4A,*iJ > Ъл(&=Ф ■
(Я>= ***>** Ь ^,аг w)-/.
§ 2. Корректность алгебраического заннкания/“,!?}£*./$ над множеством J2. - регулярных задач
Теорема 2.2.1. Линейное замыкание Lib} множества операторов / В (J2, />/?*/ т)} является квази-полным для множества JZ, - регулярных задач.
Доказательство. Докажем, что в и { UJ существуют операторы &а,р ) t » такие,что для элементов
матрицы оператора справедливы следующие соотношения:
ГуИф>1; ШффИ