Гистограммная функция автомата и ее приложения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова»

На правах рукописи

Пархоменко Денис Владимирова

ГИСТОГРАММНАЯ ФУНКЦИЯ АВТОМАТА И ЕЕ ПРИЛОЖЕНИЯ

01.01.09. - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Научный руководитель: Доктор физико-математических наук, профессор Д.Н. Бабин

Москва- 2015

2 9 АПР 2015

005568104

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова».

Научный руководитель: Бабин Дмитрий Николаевич, доктор

физико-математических наук, профессор.

Официальные оппоненты: Фролов Александр Борисович, доктор

технических наук, профессор ФГБОУ ВПО Национальный исследовательский

университет «Московский энергетический институт», Институт автоматики и вычислительной техники, профессор кафедры математического моделирования.

Зайцев Денис Владимирович,

кандидат физико-математических наук, ООО «Техкомпания Хуавэй»

Ведущая организация: Федеральное государственное

образовательное бюджетное учреждение высшего образования "Финансовый университет при Правительстве Российской Федерации".

Защита состоится 15 мая 2015 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.001.84 на базе ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова», по адресу: 119991, Москва, ГСП -1, Ленинские горы, д.1, ФГБОУ ВО МГУ имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова» (Москва,Ломоносовский проспект, д.27, сектор А, 8 этаж), http://www.math.msu.su/. Автореферат разослан 15 апреля 2015г.

Ученый секретарь

диссертационного совета Д.501.001.84 на базе ФГБОУ ВО МГУ, д.ф.-м.н.

Иванов Александр Олегович

Общая характеристика работы Актуальность темы

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

Если сопоставить слову частоту его появления на выходе автомата, то возникает новая функция, названная автором гистограммной функцией автомата. Целью работы автора является изучение свойств и приложений этой новой функции. Зафиксировав порог р, можно получить множество Ьр тех слов, которые встретились на выходе не менее р раз. Это множество автор назвал /^-языком, порождённым автоматом.

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

1 Kleene S.C., Representation of events in nerve nets andfinite automata,// Automata studies, princaton university press, 1956, P.3-41.

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

Предпосылкой к формированию теории автоматов явилась фундаментальная статья Мак-Каллока и Питтса2 о логическом анализе нервной деятельности. Первой работой, давшей толчок к развитию теории автоматов, можно считать работу Э. Поста31941 года. В ней была описана структура решетки замкнутых классов булевых функций. Булевы функции являются частным случаем автоматов - автоматами без памяти. Возникшие для булевых функций, а также для функции /с-значной логики4, задачи о выразимости, полноте, базисах актуальны и для автоматных функций. Применим к ним и аппарат, используемый для решения этих задач. Под выразимостью здесь понимается возможность получения одной автоматной функций через другие путём соединения их выходных и входных каналов. Частным случаем задачи выразимости является задача полноты, в которой проверяется возможность выразимости всех автоматных функций. Этот подход носит название структурной теории автоматов. Значительный вклад в развитие структурной теории автоматов внесли В.Б.Кудрявцев5, А.А.Летичевский6, М.И.Кратко7, C.B. Алёшин8, Д.Н.Бабин9.

2 Маккалок У.С., Питгс У., Логическое исчисление идей, относящихся к нервной деятельности // Автоматы / Сборник статей под редакцией Шеннона К.Э., Маккарти Дж.,-М., Изд-во иностранной литературы, 1956, С.362-385.

Post Е„ Two-Valued iterative Systems of Mathematical Logic II Princeton Univ. Press, Princeton, 1941

4 Яблонский C.B., Функциональные построения в k-значной логике // Труды математического институтами. В.А. Стек-лова, АН СССР, 1958, Т.51. С. 5-142

5 Кудрявцев В.Б., Алешин C.B., Подколзин A.C., Введение в теорию автоматов // Изд-во Наука, M., 1985, 320 с.

Летичевский A.A., Условия полноты для конечных автоматов И Вычислительная математика и математическая физика, №4, 1961, с. 702-710.

7 Кратко М.И., Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов // ДАН СССР, ¡964, т. 155, N I, с.35-37.

8 Алешин C.B., Об одном следствии теоремы Крона-Роудза Н Дискретная математика, том 11, вып.4, 1999 год, С. 101- 109.

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

Под конечным детерминированным инициальным автоматом V, согласно10, будем понимать шестерку

У=(А,()Л<Р.¥,Ч<}. где А - входной алфавит, - множество состояний, В - выходной алфавит, все три множества конечны, начальное состояние.

Функционирование автомата происходит по тактам времени согласно каноническим уравнениям:

[<7(0) = ?«,

где <р,щ- суть функции переходов и выходов, соответственно.

Через А* будем обозначать множество слов в алфавите А. Следуя С.К.Клини, будем говорить, что автомат представляет язык Ь с помощью множества выходных символов В 'сВ, если

Ь={аеА'\ ц/(яп,а) еВ'}.

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

Естественным расширением концепции конечного детерминированного автомата, является понятие вероятностного

9 Бабин Д.Н., О полноте двухместных о.д.-функций относительно суперпозции // Дискретная математика, том 1, 1989, Вып. 4, стр. 86-91

10 Кудрявцев В.Б., Алешин C.B., Подколзин A.C., Введение в теорию автоматов // Изд-во Наука, М., 1985, 320 с.

автомата. Согласно Бухараеву Р.Г.", конечным вероятностным автоматом назовем пятерку

ц=(Б, Е„, Ет, у^'.а |5, Ь), у0), где 5=^;,52. — .5,у/ - совокупность состояний автомата, п,т - натуральные числа, Е„, Е„, - входной и выходной алфавиты, а числа

у(5',а | Ь)

удовлетворяют условиям:

у(з',а\8,Ь')>0,

где ' еБ, а, а' еЕ„, Ъ еЕт. Стохастический вектор г0 задает начальное распределение вероятностей на множестве состояний 5.

При содержательном толковании вероятностного автомата, как преобразователья информации, число у(з',а | 5, Ъ) означает условную вероятность перехода из состояния 5' при подаче входного символа а, в состояние 5 при выходном сигнале Ъ. Числа

у(5\а ¡5, Ь)

иногда представляеют в виде множества матриц

(А(а), В(а) | аеЕт}, где стохастическая матрица А(а) - соответствует переходам между состояниями, а стохастическая матрица В(а) - выходам, при заданной букве а входного алфавита.

Важным подклассом вероятностных автоматов являются вероятностные источники, или скрытые марковские модели (СММ). Концепция СММ была сформулирована Баумом в конце 1960-х. СММ играют важную роль в приложениях: предсказании погоды,

" Бухараев Р.Г., Основы теории вероятностных автоматов // Изд-во Наука М. 1985,268 с.

распознавании образов, машинном обучении. Вероятностный источник12 это пятерка

Х=(Б, А, Г, в, к)

где

- совокупность состояний источника,

А = {а,,а2,...,ам}

- алфавит выходной последовательности,

- стохастическая матрица вероятностей переходов между состояниями,

где §к=§(к)=Р[ак\ д(=5}/,

- стохастическая матрица вероятностей появления символов п=(п1, тг2,..., /Ту) - вектор вероятностей начального состояния

пгР(Чп=81), 1 </,у, к<К Вероятностный источник — это вероятностный автомат без входа, который приписывает вероятности выходным словам. Выбирая параметры 5, А, Р,0, л-подходящим образом, вероятностные источники используют для описания и распознавания слов, имеющих разную вероятность наблюдения. Для заданной модели и порога вероятности, модель будет распознавать все те слова, которые могут появиться на ее выходе с вероятностью более некоторого порога.

В реальных задачах вероятностные источники используют для «распознавания через синтез», когда для каждой из гипотез строится свой вероятностный источник, её описывающий. Для исследуемого слова принимается та гипотеза, источник которой выдаёт на этом слове максимальную вероятность.

12 Baum L.E., Egon J.A., An inequality with applications to statistical estimation for probabilistic functions of a Markov process and to a model for ecology // Bull. Amer. Meteorol. Soc. Vol. 73. 1967. P.360-363.

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

Цель работы

Исследовать гистограммную функцию автомата. Создать эффективный метод построения гистограммной функции по её известной части.

Разработать новый метод распознавания слов, основанный на синтезе гистограммной функции. Оценить качество этого метода.

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

Научная новизна

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

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

2. Установлен критерий принадлежности языка к классу ф. Доказана связь правильной р-раскраски автомата с принадлежностью представляемого им языка к классу 42.

3. Разработан алгоритм, который для любого регулярного языка Ь определяет все натуральные р, что ¿е

4. Найден и доказан критерий автоматности мультимножества, а также критерий квази-автоматности мультимножества. Найден алгоритм синтеза гистограммной функции автомата по её части, получены сложностные оценки алгоритма.

5. Автором предложен новый метод распознавания слов, основанный на синтезе гистограммной функции автомата.

Основные методы исследования

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

Теоретическая и практическая значимость

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

Аппробация результатов

Результаты диссертации неоднократно докладывались на научно-исследовательских семинарах:

1. Кафедральный семинар «Теория автоматов» кафедры Математической Теории Интеллектуальных Систем МГУ под руководством академика В.Б. Кудрявцева (2007-2014 гг. неоднократно)

2. «Теория дискретных функций и приложений» под руководством профессора Д.Н. Бабина (2007-2013 гг. неоднократно).

Также результаты диссертации докладывались на следующих международных конференциях:

1. XVII международная конференция "Проблемы теоретической кибернетики" (Казань, 16-24 июня 20014).

2. XI международный семинар "Дискретная математика и ее приложения" (Москва, 18-23 июня 2012 г.).

3. X международный семинар "Дискретная математика и ее приложения" (Москва, 1-6 февраля 2010 г.).

4. XVI международная конференция аспирантов и молодых ученых "Ломоносов-2009" (Москва, 13-18 апреля 2009 г.).

Структура диссертации

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

Публикации

Результаты диссертации опубликованы в 6 работах автора, список которых приведен в конце автореферата.

Краткое содержание работы.

Центральным понятием Главы 1 является понятие гистограммной автоматной функции, замечательной тем, что с помощью нее можно ещё одним способом порождать регулярные языки конечным детерминированным автоматом. Глава 1 посвящена изучению таких языков, а также свойств гистограммной автоматной функции. Определение 1.1:

Пусть задан конечный детерминированный инициальный автомат

У=(А, <2, В, <р, у/, Чп). Гистограммной автоматной функцией автомата V назовем функицю

ку:В*— К и {0},

определенную по правшу

куф) = \{аеА' | Щя„а)=Р }|. Здесь К означает множество натуральных чисел, а |' |, означает мощность множества.

В параграфе 1.1 для произвольного натурального р и автомата V рассматриваются языки, состоящие из слов, встречающихся на выходе автомата V не менее р раз. Определение 1.2:

Для любого натурального р и конечного детерминированного автомат V, р-языком, порожденным автоматом V назовем: ЬР(У) = { №'\куф)>р}. Каждый конечный детерминированный инициальный автомат V, задает цепочку языков, вложенных друг в друга языков:

Структуру этих языков описывают следующие теоремы: Теорема 1.1:

Для любого конечного инициального автомата А и для всякого г>0, Ь,(А) —регулярный язык. Теорема 1.2:

Пусть дан автомат V, у которого мощность выходного алфавита не превосходит мощности входного. Если для некоторого г'= К, слово /? е Ь;(У), то найдется буква Ъ выходного алфавита автомата В такая, чторЪеЬ-,(У).

Параграф 1.2 посвящен изучению свойств классов языков: Определение 1.3:

Назовём класом р-языков множество

где К(А,В) - класс всех автоматов вида (А^,В, <р, у/, до). Исследована замкнутость введенных классов языков относительно основных операций и их связь с регулярными, факториальными и другими классами языков. Имеет место Теорема 1.3:

1) Класс языков замкнут относительно операций: объединения, взятия автоматного образа, конкатенации и итерации, но не замкнут относительно пересечения.

2) Класс языков при 1>1 замкнут относительно операции взятия автоматного образа, но не замкнут относительно теоретико-множественных операций объединения и пересечения. Каждый /5-язык является регулярным, но не каждый регулярный является /?-языком. Вопрос, проверяемо ли свойство произвольного языка быть языком р-типа, исследуется в Параграфе 1.3. Более точно в этом разделе будет сформулирован критерий принадлежности языка к классу для произвольного р. Для того чтобы явно представить алгоритм, будет введено понятие р-раскраски автомата без выхода. Определение 1.4: Пусть задан автомат

& = (В, й (р, д„, Ш без выхода, с выделенным множеством финальных состояний Q^. Введем функцию

к: К и {0},

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

1) к(д)<р, для любого д^Яг, к(д)>р, для любого д £(2/? и

Ж

2) к(д)Щ = ^К(р{д,Ь,))1 если VjXe.fi,)йб, и

м

к(ч)ЩЪ X К<Р(Ч,Ь,)) + 4д)-р, где =

¡.МяАнОг 1 1

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

Теорема 1.5:

Пусть р > 1, автомат V = (В, Q, (р, до, QF) представляет язык Ь. Тогда в том и только том случае, когда найдется правильно р-

раскрашенный автомат

У=(В, <2\<р\Чв\ О/), также, представляющий Ь. Причем число состояний нового автомата сравнимо с числом состояний исходного, а именно:

Теорема 1.6:

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

Параграф 1.4 содержит доказательства основных результатов сформулированных в Параграфе 1.3.

Вопрос синтеза гистограммной функции исследован в Главе 2. Под мультимножеством над множеством В — будем понимать пару

(Л,Х)>

где х-' Л —► X — это функция, сопоставляющая каждому элементу А натуральное число, называемое кратностью этого элемента. Задача восстановления гистограммной функции сводится к построению детерминированного автомата, гистограммная функция которого на множестве слов А совпадает с отображением Заметим, что из-за детерминированного характера восстановить гистограммную функцию не всегда возможно. Однако, можно восстановить гистограммное накрытие. Мультимножество (В,-/) назовем автоматным, если куф)=хФ). для любого РеВ, и назовём квази-автоматным, если существует автомат

У=(Ек,0,Ек,(р,1//,дп),

что для любого слова /1еВ к,-ф)>хф). Функцию кг, в этом случае, назовем гнстограммным накрытием. В параграфе 2.1 сформулированы критерии автоматности и квази-автоматности конечного мультимножества слов и алгоритм построения автомата с заданной гистограммной функцией. Теорема 2.3:

1) Существует алгоритм <£, который по мультимножеству (В,у), ^ ;>-(/?)< находит автомат V, что Ку -

гистограммное накрытие (В,у), или определяет, что такого автомата не существует.

2) Число операций сложения и умножения натуральных чисел, необходимых для проверки и поиска не превосходит

С-5ХЛ-

3) При этом число \Q\-\ состояний автомата V удовлетворяет неравенству

1-4т

ДгЯ _ 1

где М—максимальная длина слова из В. Для приложений важна простота подсчета значения гистограммной функции детерминированного автомата. Оказывается, гистограммную функцию можно вычислять эффективно. Теорема 2.4:

Пусть У=(Л,(),В,(р,1{/,д0), ку - его гистограштая функция. Тогда для любого слова р выходного алфавита В, число С арифметических операций для нахождения Куф) удовлетворяет С = \В\ *|/?|

Параграф 2.2 посвящен необычному, на первый взгляд, свойству классов языков ££. Если для некоторых / < г, Ье<% будет выполнено

Ь , то отсюда не следует, что для классов языков выполнено -ё* с Оказывается, верна

Теорема 2.5:

Для любых натуральных Щ выполнено:

В Главе 3 описан опыт применения алгоритма синтеза гистограммного накрытия к задаче распознавания образов. Параграф 3.1 посвящен методам распознавания слов автоматами и источниками, дано описания метода распознавания с помощью гистограммной автоматной функции. Для проверки нового метода распознавания был написан программный комплекс на ЭВМ и собрана коллекция данных ЭКГ. ЭКГ были выбраны для анализа, т.к. с одной стороны изменение потенциалов сердечной мышцы, регистрируемое электро-кардиографом обладает регулярной структурой и будет релевантно методу распознавания. С другой стороны, ЭКГ обладают достаточной вариабельностью, чтобы можно было говорить о чистоте эксперимента. Данные для распознавания и обучения были получены от Института Клинической Кардиологии им. А.Л.Мясникова. Полный корпус данных состоял из 100 ЭКГ здоровых испытуемых и 100 ЭКГ испытуемых с нарушением проводимости сердца. Задача распознавания состояла в выявлении ЭКГ здорового человека. В параграфе 3.2 приведены результаты симуляции метода. Доля правильно классифицированных ЭКГ превысила 0.82.

Заключение

Основными результатами работы являются:

1. Метод синтеза гистограммной функции автомата по её части.

2. Установленная регулярность и другие свойства Ьр -языков,

порождаемых гистограммной функцией автомата.

3. Критерий принадлежности языка к классу

4. Критерии автоматности и квази-автоматности мультимножетсва.

5. Алгоритм поиска всех классов р>0, которые содержат данный регулярный язык.

6. Метод распознавания слов, основанный на синтезе гистограммной функции автомата.

Благодарность

Автор выражает глубокую благодарность своему учителю -доктору физико-математических наук, профессору Бабину Д.Н. за постановку задачи и внимание к работе. Автор благодарит заведующего кафедрой Математической Теории Интеллектуальных Систем академика В.Б. Кудрявцева, а также весь коллектив кафедры за доброжелательную атмосферу и ценные советы. Отдельную благодарность автор выражает сотрудникам кафедры к.ф.м.н. И.Л.Мазуренко и к.ф.м.н. П.А.Пантелееву.

Список работ автора по теме диссертации

1. Пархоменко Д.В., Порожденные автомататамир-языки II Дискретная математика, 2014, Т.26, вып. 1, с. 96-102.

2. Пархомнеко Д.В., Вторая автоматная функция и с нею связанные классы регялрных языков // Интеллектуальные системы, Т. 17, вып. 1-4, 2013.

3. Пархомнеко Д.В., Метод распознавания множетсва слов через синтех детерминированного автомата // Интеллектуальные системы, Т. 15, вып. 1-4, 2011, с. 189-204.

4. Пархомнеко Д.В., Моделирование вероятностными источниками // Интеллектуальные системы, Т. 14, вып. 1-4, 2010, с. 213-224.

5. Пархоменко Д.В., Спектральная автоматная функция и связанные с нею регулярные языки И Интеллектуальные системы в производстве, 2012, вып. 1,с. 165-175.

6. Пархоменко Д. В., Применение метода Марковских моделей к задаче описания морганий человека, // Интеллектуальные системы в производстве, 2007, вып. 2, с. 54-61.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡СР экз. Заказ № | Э