Содержание к диссертации
Введение
Глава І. Модель алгоритмов распознавания с предста вит ельныгли наборами для к -значных таблиц 7
1. Представительные наборы 7
2. Тупиковые представительные наборы II
3. Геометрическая интерпретация 14
4. Описание модели Ш-Cf* Р>у) распознающих .
алгоритмов с представительными наборами 16
Глава II. Метод синтеза тупиковых,представительных.наборов. для к -значных таблиц 19
1. О синтезе тупиковых представительных наборов для к -значных таблиц 19
2. Формула для умножения двух уравнений . Нельсоновского типа (Н.типа) 26
3. Формула для умножения трех уравнений Н.типа . 31
4. Формула для умножения четырех уравнений Н.типа . 35
5. Оптимальное разбиение системы уравнений Н.типа на пары 47
6. Применение алгоритма Эдмондсона и Джонсона для .
разбиения системыуравнений Н.типа на.четверки 48
7. О решении системы уравнений Н.типа 50
Глава III. Комплекс прикладных программ ЮШ и его применение 52
1. Принцип организации комплекса..Блок-схема 52
2. Описание программ комплекса 54
3. Применение комплекса для решениязадачи
идентификации авторства 60
Приложение
- Геометрическая интерпретация
- Формула для умножения двух уравнений . Нельсоновского типа (Н.типа)
- Оптимальное разбиение системы уравнений Н.типа на пары
- Применение комплекса для решениязадачи
Введение к работе
Задача синтеза классификаций или задача распознавания образов является одной из важнейших задач современной математической кибернетики. Методы ее решения образуют самостоятельное направление в рамках этой науки. Большой интерес к задачам распознавания определяется тем, что, во-первых, они являются весьма общигли в плане математической постановки и, во-вторых, находят широкое применение при решении важных практических задач, таких как прогнозирование в естествознании и технике, автоматическое чтение текстов и т.д. При этом задача прогнозирования решается на основе ограниченного накопленного опыта. Данное обстоятельство определяет актуальность работ по математической теории распознавания, созданию численных методов и программ для решения прикладных задач распознавания. Особенно следует отметить, что в настоящее время не существует других математических подходов к решению задач классификации и прогнозирования, отличных от методов распознавания образов, если исходная информация о процессе или явлении ограничена.
В научной литературе дано описание нескольких семейств-моделей распознающих алгоритмов. Некоторые из них, в том числе алгоритмы типа "Кора", приспособлены лишь для работы со специальной обучающей информацией. Поэтому актуальным является построение расширений таких алгоритмов, позволяющее применять их для решения более широких классов прикладных задач. Именно такое расширение, позволяющее включать в обработку алгоритмами типа "Кора" градуированные признаки с большим, чем 2 числом значений, выполнено в настоящей работе.
Цель работы состоит в создании нового класса алгоритмов распознавания, предназначенного для обработки информации с многозначны-
.-.4-., .. . . . ..,..,,
ми признаками, разработке для них эффективных численных методов, позволяющих решать прикладные задачи на ЭВМ в приемлемое время, создании соответствующего программного обеспечения и решении прикладной задачи идентификации авторства.
Алгоритм "Кора" ([4,6,7,9]) появился в середине 60-х годов и предназначался для обработки объектов с бинарными признаками. На бинарной таблице обучения выделялись так называемые представительные наборы. Для каждой двойки, а впоследствии тройки признаков в каждом классе искались объекты, значения которых по этим признакам были бы отличны от соответствующих значений объектов других классов. Найденные поднаборы в паре соответственно с двойкой или тройкой признаков назывались представительными наборами данного класса. В случае когда рассматривались двойки признаков, задача выделения представительных наборов решалась перебором всех пар признаков. В случае когда рассматривались тройки признаков, задача выделения представительных наборов решалась перебором трехбуквенных конъюнкций. При таком подходе рассмотрение опорных множеств большей мощности вызывает необходимость просмотра всех элементарных конъюнкций соответствующего ранга. При решении практических задач этот просмотр требует значительного времени даже при использовании современных ЭВМ. С другой стороны такое ограничение опорных множеств приводит к тому, что при достаточно больших объемах обучающей информации вероятность распознавания любого нового объекта равна почти О (Г28]). Если рассматривать представительные наборы произвольной длины, то задача выделения их для каждого класса сводится к задаче построения сокращенной дизъюнктивной нормальной формы (д.н.ф.) для не всюду определенной функции алгебры логики (Г377). Если же перейти от бинарных признаков к градуированным, то задача выделения представительных наборов для каждого класса становится эквива-
лентной задаче построения сокращенной д.н.ф. для не всюду опреде-ленной функции к -значной логики (ГІ2І).
Использование аналога метода Нельсона (Г45І) для построения сокращенной д.н.ф. не всвду определенной функции к-значной логики позволяет свести эту задачу к решению системы логических уравнений - уравнений Нельсоновкого типа. Отметим, что традиционный метод решения системы - переход от конъюнктивной нормальной формы к дизъюнктивной нормальной форме с последующим применением к последней операций поглощения и склеивания - требует построения и перебора большого числа элементарных конъюнкций. Встает вопрос о сокращении числа рассматриваемых элементарных конъюнкций. При решении этого вопроса было получено обобщение на /с-значный случай формулы свертки двух специальных дизъюнкций, выведенной С.В.Яблонским ([14]), которое позволило сократить число уравнений вдвое, увеличив при этом сложность каждого минимальным образом. С использованием этого результата получены формулы экономного умножения левых частей двух, трех, четырех уравнений системы, которые позволили уменьшить первоначальное число уравнений в четыре раза.
Умея считать сложности произведения двух, трех, четырех уравнений системы, можно поставить вопрос о таком разбиении системы логических уравнений на четверки, чтобы суммарная сложность их произведений была бы минимальной. Эта задача решается сведением к задаче синтеза паросочетания с максимальным весом в соответствующем взвешенном графе (С23І).
В результате достигаемого сокращения числа рассматриваемых элементаных конъюнкций получаем не сокращенную д.н.ф. для не всюду определенной функции к-значной логики, а д.н.ф., реализующую ту же функцию, но состоящую в общем случае из меньшего
..-6-. - .
числа простых элементарных конъюнкций. Следовательно, в общем случае получаем собственное подмножество множества тупиковых представительных наборов. Т.к. из построенной д.н.ф. можно методом, аналогичным методу Блейка ([14,36]), всегда построить сокращенную д.н.ф., то указанное подмножество несет в себе ту же информацию о разбиении множества допустимых объектов на классы, что и множество тупиковых представительных наборов.
На основе предложенного метода синтеза совокупности представительных наборов построена многопараметрическая модель распознающих алгоритмов с представительными наборами - алгоритмов типа "Кора". С помощью этих алгоритмов решена практическая задача идентификации авторства стихов поэтов-антифашистов группы Мусы Джалиля (список I). Тексты этих стихов дошли до нас в блокнотах военнопленных, и их точное авторство было неизвестно. Вместе с там сохранились произведения тех лет некоторых членов группы : Моабнтские тетради М.Джалиля (спивок 2), тетрадь А.Алиша. (список 3), одно стихотворение Г.Баттала, пять стихотворений А.Симая, три стихотворения Р.Нигмати, не вжодившего в группу, но находившегося в одних условиях с джалиловцами(список 4).
Наиболее интересной литературоведческой задачей было : установить какие из спорных произведений (список I) принадлежат М.Ддалилю и какие А.Алишу. Эта задача решается в диссертации.
Опишем содержание диссертации по главам.
В первой главе приводятся основные определения, доказывается, что множество тупиковых представительных наборов несет в себе ту же информацию о разбиении допустимых объектов на классы, что и множество представительных наборов, описывается параметрическая модель распознающих алгоритмов с представительными наборами.
Во второй главе предлагается метод синтеза тупиковых пред-
ставительных наборов ($0, описывается численный метод построения совокупности тупиковых представительных наборов (2-7).
Результаты второй главы являются основными.
В третьей главе описывается комплекс прикладных программ КПП, предназначенный для решения практических задач распознавания. Описываются результаты решения задачи идентификации авторства стихов поэтов-антифашистов группы М.Джалиля с помощью данного комплекса.
В приложении приводятся тексты программ комплекса КПП.
Автор выражает глубокую благодарность своему научному руководителю Юрию Ивановичу Журавлеву за постановку задачи и постоянное внимание к работе, Рафаэлю Ахметовичу Мустафину, Канафи Габдельбаровичу Баликову, Илиде Басыровне Башировой , принявшим деятельное участие в выработке признаков и обработке текстового материала.
Геометрическая интерпретация
В данной главе описывается программная реализация предложенных выше алгоритмов и методов.
Теоретической основой комплекса являются результаты, полученные в первых двух главах диссертации, а также в работах ([12, I3J).
Комплекс написан на языках ФОРТРАН-ІУ и АЛГОЛ-ГДР в мониторы ой системе ".Вубна" (С34]), причем основная часть комплекса написана на языке ФОРГРАН-ІУ и лишь небольшая часть, связанная с эксплуатацией диалоговой системы оптимизации да0 ([5,15]), написана на языке АЛГОЛ-ГДР. Комплекс реализован на ЭВМ БЭСМ-6 и состоит из пяти программ : 1. Программы построения системы уравнений Нельсоновкого типа и.разбиения ее на четверки, 2. Программы построения д.н.ф., 3. Программы построения тупиковых представительных наборов, 4. Программы оптимизации весов признаков и весов объектов, 5. Программы классификации объектов, предложенных на распознавание. Все управляющие программы находятся на магнитном диске, основная часть подпрограмгл хранится в оттранслированном виде на магнитной ленте в двух индивидуальных библиотеках. Обмен информации между программами осуществляется через магнитную ленту. Запись и считывание файлов с ленты производится по прямому доступу с использованием соответствущих подпрограмгл из библиотеки стандартных подпрограмгл.
Первые две программы требуют значительного машинного времени, поэтому в них предусмотрено ветвление по времени с необходимым запоминанием на ленте.
Четвертая програміа комплекса предполагает работу с диалоговой системой оптимизации ДИСО, которая может вестись как в диалоге, так и в пакетном режиме (С8]). В приложении приведен текст программы со сценарием для работы в пакетном режиме. Блок-схема комплекса имеет вид :
Управляющая програш ПЛРОс производит построение двух полных неориентированных взвешенных графов Q и Q без петель и кратных ребер и осуществляет обращения к подпрограмме Е МО А/Я) , выполняющей поиск паросочетания с максимальным весом в графе при помощи алгоритма Эдмондсона и Джонсона. Подпрограмма М PERI А/ и подпрограммы-функции ІН и icOA/ST служат для вычисления весов графа & . Подпрограмма NP sr используется подпрограммой Е молґь ддд построения пути между двумя вершинами дерева.
Результатом работы программы являются.паросочетания MM-f(M) графа G- и MMt(M) графа Q- . Теоретической основой данной программы являются результаты, полученные в 3, 4, 7 второй главы. . Исходной информацией для программы служит : I. таблица обучения ТО(М}А/) , г. массив KLCU . 3. паросочетания MMiCM) и MMZ(M) , 4. вектор К A-K/V) t где к A--І(І) равно числу градащш I -того признака, , 5. переменная КМ , равная максимальному числу градаций признаков, 6. текущий номер класса NKL , 7. переменная S Т , ограничивающая время счета. Смысл переменных М , л/ , L и массива KL(L) ТОт же, что и в первой программе.
Формула для умножения двух уравнений . Нельсоновского типа (Н.типа)
Полученные в 2 результаты позволяют свернуть левые части произвольных двух.уравнений Нельсоновского типа и определить сложность свертки. Поэтому возникает задача разбиения левых частей уравнений системы (3) на пары таким образом, чтобы суммарная сложность соответствующих шл сверток была бы минимальной. Сведем эту задачу к задаче выбора паросочетания с максимальным весом. (Г235.
Поставим в соответствие системе (3) полный неориентированный граф G без петель и кратных ребер с pj = т- (т - /. J вершинами. Сопоставим У($І) вершину 3-І графа G- , L =/,2.,...,pj. Тогда разбиению системы (3) на пары Судет соответствовать паросо-четание в графе G- . Припишем ребру (3CS , --6) вес cs ± равный числу совпадающих координат в 1($ s ) и ICS . ) Требуется в графе G- найти паросочетание Р с максимальным весом. Эта задача решается алгоритмом Эдмондсона и Джонсона (Г447) за полиномиальное время 0(pj ) , где pj число вершин графа ([32]).
Применение алгоритма Эдмондсона и Джонсона для разбиения системы уравнений Нельсоновского типа на четверки
Полученные в 3 и 4 результаты позволяют рационально умножать левые части произвольных трех и четырех уравнении Нельсоновского типа, вычислятьс сложность получаемых произведений. Поэтому возникает задача разбиения системы уравнений Нельсоновского типа на четверки с целью уменьшения суммарной сложности соответствующих им произведений. При решении этой задачи используется оптимальное разбиение системы (3) на пары. соответственно и выпишем У (&i.s , S , tsx. Si \ или построим У " и Vі для / ГSi , Sc±g_-) и yt$csi S ±- 1 и выпишем ytSis S a , Scsz , ) . Если паросочетание P содержит элемент (ЭС-J , r tj + i), то в зависимости от того cst&.j+4 равно /?-/, Л_/ или Л./ » построим с/? , как описано в 3, для УС S с . , SV ) i/ , J+/; или CSLsz Sc j l и выпишем по формуле (7) соответственно yCS с.s , Sc-SJi , /- 7+-/ , y(ScS4, figs/j+s S"sJ или , Л/ у » 15 .
Если Л- нечетно, то в (г есть вершина ос , не инцидент ная ни одному ребру из Р . Если -к. є ( d,z, ..,, -3} , то добавим к новой системе У CSc±, 7 S± ) » построенное по правилу (6), где if - произвольная циклическая перестановка соответствующих элементов 1С Si ) и J (St ) . Если / 7+-/ , то добавим к новой системе (S rPjn ). Полученная новая система решается стандартным сведением к ВИДУ rnqcc -{ 0? f , . ..9 D7 м = к-1 t Где t , 6" = М t - элементарные конъюнкции, в резуль тате которого будем иметь слева не сокращенную д.н.ф. ЯЬ (fod С-эсУ) , а д.н.ф. Ч СP0d С .)) , реализующую ту же функцию и состоящую из меньшего числа простых элементарных конъюнкций. Из д.н.ф. дСР Сое)) выделим д.н.ф.. . ЯЬ С FJ С&)) так, как описано в I второй главы. Т.к. из д.н.ф. CF ґсс )) аналогом метода Блейка (С14,363) можно построить сокращенную д.н.ф., то совокупность тупиковых представительных наборов, соответствующая д.н.ф. { СР с -Л} / - ,2., . .., г несет в себе ту же информацию о разбиении множества М допустимых объектов на классы К. , . . .9 Ке что и все множество тупиковых представительных наборов.
Оптимальное разбиение системы уравнений Н.типа на пары
В данной главе описывается программная реализация предложенных выше алгоритмов и методов. Теоретической основой комплекса являются результаты, полученные в первых двух главах диссертации, а также в работах ([12, I3J).
Комплекс написан на языках ФОРТРАН-ІУ и АЛГОЛ-ГДР в мониторы ой системе ".Вубна" (С34]), причем основная часть комплекса написана на языке ФОРГРАН-ІУ и лишь небольшая часть, связанная с эксплуатацией диалоговой системы оптимизации да0 ([5,15]), написана на языке АЛГОЛ-ГДР. Комплекс реализован на ЭВМ БЭСМ-6 и состоит из пяти программ : 1. Программы построения системы уравнений Нельсоновкого типа и.разбиения ее на четверки, 2. Программы построения д.н.ф., 3. Программы построения тупиковых представительных наборов, 4. Программы оптимизации весов признаков и весов объектов, 5. Программы классификации объектов, предложенных на распознавание. Все управляющие программы находятся на магнитном диске, основная часть подпрограмгл хранится в оттранслированном виде на магнитной ленте в двух индивидуальных библиотеках. Обмен информации между программами осуществляется через магнитную ленту. Запись и считывание файлов с ленты производится по прямому доступу с использованием соответствущих подпрограмгл из библиотеки стандартных подпрограмгл.
Первые две программы требуют значительного машинного времени, поэтому в них предусмотрено ветвление по времени с необходимым запоминанием на ленте.
Четвертая програміа комплекса предполагает работу с диалоговой системой оптимизации ДИСО, которая может вестись как в диалоге, так и в пакетном режиме (С8]). В приложении приведен текст программы со сценарием для работы в пакетном режиме. Блок-схема комплекса имеет вид : A/KL = 4 программа построения системы уравнений Нельсон, типа и разбиения ее на четверки запись паро-сочетаний \ на МЛ программа построенияД.Н.ф. запись д.н.ф.на МЛ программа построения тупико- запись наборов на МЛ вых і іредстави тельных наооров MKL = A/KL +± да программа оптимизации весов признаков и весов объектов запись весов на МЛ программа классификации объектов, предложенных на распознавание
-Здесь A/kL - текущий номер класса, L - число классов. Все программы комплекса предполагают, что множество к « /?, У, . ..,к-} предварительно отображено в шожество {d, 9.,..., к} следущим образом : L L = о, 1,..., -1. 2. Описание программ кюмплекса I. Программа построс-ения системы уравнений Нельсоновского типа и разбиения ее на четверки Работа этой программы основана на результатах 5 и 6 второй главы. Исходными данными для программы являются : 1. Таблица обучения Т0(М,М) , где М - число объектов, А/ - число признаков, 2. массив KU(L) , указывающий мощности классов, L - число классов, 3. NKL -текущий номер класса, 4. переменная $Т , указывающая время счета.
Управляющая программой Работа программы основана на результатах, полученных в 4 первой главы. . Входными данными для программы являются : 1. таблица Tg (MR, /[/) распознаваемых объектов, где MR -число объектов, предложенных на распознавание, 2. массивы LTPRt/V, м) и TPR(M, А/-І) , 3. массив Х(мм) весов признаков и весов объектов, где - 60 -4. вектор kLK(L ) ,
Результатом работы програмш являются списки номеров распознаваемых объектов, отнесенных в первый, второй, третий классы, выводимые на листинге под заголовками "Первый класс", "Второй класс", "Третий класс" соответственно, и список нераспознанных объектов, выводимый под заголовком "Не распознаны объекты".
Применение комплекса для решения задачи идентификации авторства Комплекс КПП был опробирован на задаче идентификации авторства стихов (список I) поэтов-антифашистов группы М.Дналиля.
Множество авторов было разбито на три класса : класс Кч -М.Джалиль, класс &L - А.Алиш, класс Къ - Г.Баттал.А.Симай, Р.Нигмати. Обучавдий массив составили первые 47 произведений Моабитских тетрадей (список 2), первые 6 произведений тетради А.Алиша (список 3), одно произведение Г.Баттала, первые три произведения А.Симая, первые два произведения Р.Нигмати (список 4). Остальные произведения, указанные в списках 2, 3, 4, отнесены в контрольную выборку.
Признаки и их градации указаны в таблице 2. Описания обучающих объектов приведены в таблице 3. Описания объектов контрольной выборки приведены в таблице 4. Поскольку описания объектов 52-67 (список I) совпадают, то в таблице 5 описаний распознаваемых объектов они представлены одной - 52-ой - строкой.
Было выделено 211 тупиковых представительных наборов первого класса, 58 тупиковых представительных набора второго класса, - 61 43 тупиковых представительных набора третьего класса (таблица 6).
В результате работы комплекса КПП был построен распознающий алгоритм, который правильно классифицировал 88$ объектов контрольной выборки. Параметр сГ был при этом равен d. , а веса признаков и веса объектов приведены соответственно в таблице 7 и в таблице 8.
Алгоритм "Кора" ([4,6,7,9]) появился в середине 60-х годов и предназначался для обработки объектов с бинарными признаками. На бинарной таблице обучения выделялись так называемые представительные наборы. Для каждой двойки, а впоследствии тройки признаков в каждом классе искались объекты, значения которых по этим признакам были бы отличны от соответствующих значений объектов других классов. Найденные поднаборы в паре соответственно с двойкой или тройкой признаков назывались представительными наборами данного класса. В случае когда рассматривались двойки признаков, задача выделения представительных наборов решалась перебором всех пар признаков. В случае когда рассматривались тройки признаков, задача выделения представительных наборов решалась перебором трехбуквенных конъюнкций. При таком подходе рассмотрение опорных множеств большей мощности вызывает необходимость просмотра всех элементарных конъюнкций соответствующего ранга. При решении практических задач этот просмотр требует значительного времени даже при использовании современных ЭВМ. С другой стороны такое ограничение опорных множеств приводит к тому, что при достаточно больших объемах обучающей информации вероятность распознавания любого нового объекта равна почти О (Г28]). Если рассматривать представительные наборы произвольной длины, то задача выделения их для каждого класса сводится к задаче построения сокращенной дизъюнктивной нормальной формы (д.н.ф.) для не всюду определенной функции алгебры логики (Г377). Если же перейти от бинарных признаков к градуированным, то задача выделения представительных наборов для каждого класса становится эквива лентной задаче построения сокращенной д.н.ф. для не всюду опреде-ленной функции к -значной логики (ГІ2І).
Использование аналога метода Нельсона (Г45І) для построения сокращенной д.н.ф. не всвду определенной функции к-значной логики позволяет свести эту задачу к решению системы логических уравнений - уравнений Нельсоновкого типа. Отметим, что традиционный метод решения системы - переход от конъюнктивной нормальной формы к дизъюнктивной нормальной форме с последующим применением к последней операций поглощения и склеивания - требует построения и перебора большого числа элементарных конъюнкций. Встает вопрос о сокращении числа рассматриваемых элементарных конъюнкций. При решении этого вопроса было получено обобщение на /с-значный случай формулы свертки двух специальных дизъюнкций, выведенной С.В.Яблонским ([14]), которое позволило сократить число уравнений вдвое, увеличив при этом сложность каждого минимальным образом. С использованием этого результата получены формулы экономного умножения левых частей двух, трех, четырех уравнений системы, которые позволили уменьшить первоначальное число уравнений в четыре раза.
ПЛРОс производит построение двух полных неориентированных взвешенных графов Q и Q без петель и кратных ребер и осуществляет обращения к подпрограмме Е МО А/Я) , выполняющей поиск паросочетания с максимальным весом в графе при помощи алгоритма Эдмондсона и Джонсона. Подпрограмма М PERI А/ и подпрограммы-функции ІН и icOA/ST служат для вычисления весов графа & . Подпрограмма NP sr используется подпрограммой Е молґь ддд построения пути между двумя вершинами дерева.
