Методи формалізації і моделі морфологічних структур та їх застосування в системах штучного інтелекту

Размещено на http://www.allbest.ru

Харківський національний університет радіоелектроніки

УДК 519.7

Методи формалізації і моделі морфологічних структур та їх застосування в системах штучного інтелекту

05. 13. 23 - Системи та засоби штучного інтелекту

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Козяєв Леонід Леонідович

Харків 2006

Дисертацією є рукопис.

Робота виконана у Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник: доктор технічних наук, професор Шабанов-Кушнаренко Сергій Юрійович, Харківський національний університет радіоелектроніки.

Офіційні опоненти: доктор технічних наук, професор Шаронова Наталія Валеріївна, Національний технічний університет „Харківський політехнічний інститут”, професор кафедри АСУ;

кандидат технічних наук, доцент Шостак Ігор Володимирович, Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, доцент кафедри програмного забезпечення комп'ютерних систем.

Провідна установа:

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

Захист відбудеться 12.04.2006 р. о __15__ годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел. (0572) 702-14-51.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки, м. Харків, пр. Леніна, 14.

Автореферат розісланий 10.03. 2006 р.

Вчений секретар спеціалізованої вченої ради Чалий С.Ф.

АНОТАЦІЯ

Козяєв Л.Л. Методи формалізації і моделі морфологічних структур та їх застосування в системах штучного інтелекту. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 - системи та засоби штучного інтелекту - Харківський національний університет радіоелектроніки, Харків, 2006.

Дисертація присвячена побудові методів формалізіції відношень за допомогою апарата логічних мереж, зокрема, природно-мовного відношення відмінювання прикметників, з їх подальшою реалізацією у вигляді електронних схем паралельної дії. Отримані результати орієнтовані на реальні можливості сучасної комп'ютерної та обчислювальної бази і нові вимоги до інформаційних технологій. Розроблений комплекс математичних і алгоритмічних моделей застосовано в системах автоматичної обробки текстів природної мови для програмного й апаратного забезпечення логічних мереж.

Отримані методи побудови логічних мереж застосовані при побудові комп'ютерного комплексу для автоматизованого керування фірмою. Використання удосконаленої парадигматичної таблиці та відповідної їй логічної мережі відмінювання прикметників дозволили мінімізувати схемну реалізацію системи синтаксичного аналізу.

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

прикметник мова морфологічний

АННОТАЦИЯ

Козяев Л.Л. Методы формализации и модели морфологических структур и их применение в системах искусственного интеллекта. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - системы и средства искусственного интеллекта - Харьковский национальный университет радиоэлектроники, Харьков, 2006.

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

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

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

Усовершенствована парадигматическая таблица словообразования полных непритяжательных имен прилагательных. Разработан метод представления парадигматической модели морфологического отношения склонения полных непритяжательных имен прилагательных русского языка в виде двудольных графов. Соответственно парадигме морфологического отношения словоизменения имен прилагательных построены графы всех связей логической сети этого отношения. Разработана программная модель логической сети склонения любых словоформ имен прилагательных по заданным признакам. Разработан метод построения логической сети для операции дизъюнкции, которая позволяет моделировать также любые другие логические операции. Разработан метод сокращения внутренних состояний в логической сети. Полученные методы построения логических сетей применены при построении компьютерного комплекса для автоматизации работы по разработке, комплектации и размещению торгового оборудования в служебных и офисных помещениях, а также для автоматизированного управления фирмой и согласования работы ее отделов (торгово-производственное предприятие "Европейское торговое оборудование", акт внедрения от 31.05.2005). Использование усовершенствованной парадигматической таблицы и соответствующей ей логической сети словообразования имен прилагательных позволили минимизировать схемную реализацию в системах синтаксического анализа прилагательных русского языка, реализованную в виде ІP-core (ХНУРЕ, кафедра АПОТ, акт внедрения от 10.06.2005). Результаты диссертации внедрены в учебный процесс для студентов 4-5 курсов специальности "Программное обеспечение автоматизированных систем" факультета Компьютерных наук ХНУРЕ в курсах лекций “Теория интеллекта” и “Алгебраическая логика” (ХНУРЕ, акт внедрения от 25.05.2005).

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

ABSTRACT

Kozyaev L.L. Morphological structures models and methods of it formalization and their application in an artificial intellect systems. - Manuscript.

A thesis on competition of a scientific degree of the candidate of technical science on a speciality 05.13.23 - system and means of an artificial intellect - Kharkov's National University of Radio Electronics, Kharkov, 2006.

The dissertation is devoted to construction of the relations formal representation methods with the help of logic networks apparatus, in particular, the natural language relation of adjectives declination, with their further realization in parallel processors. The received results are focused on the real account of modern computer opportunities, computing base and new requirements to information technologies. The received methods of logic networks construction are applied at a computer complex construction for automated firm management. Use of the advanced paradigmatic model and a logic network of adjectives names word-formation, have allowed to minimize syntactic analysis systems circuit realization, realized as ІP-core.

Key words: a natural language, the text sense formalization, apparatus of logic algebra, a morphological predicate, the morphological space, the predicate operation, binarization, a logic network.

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Програмна обробка текстової інформації (насамперед в інформаційно-пошукових, експертних системах різних областей застосування, у бібліографічних системах, у системах машинного перекладу, при обробці баз даних і т.п.) в умовах безперервного росту потоку науково-технічної інформації продовжує здобувати усе більше значення. Ефективне використання комп'ютерної техніки в цьому напрямку неможливо без створення діючих моделей природних мов. Впровадження результатів дисертаційної роботи буде сприяти підвищенню рівня інформаційних технологій на Україні.

У різних комп'ютеризованих областях виникає необхідність обробки інформації, представленої природною мовою. В системах, що включають людину як свою органічну ланку, основною формою передачі інформації є документи, що містять значну кількість текстової інформації. Комп'ютерне моделювання процесів обробки текстів дозволить автоматизувати багато видів інтелектуальної діяльності людини, розширити його можливості. Ефективність АІС, призначення яких - автоматизація процесів накопичення, пошуку й узагальнення інформації, визначається їх здатністю обробляти інформацію неформалізовану або слабко формалізовану.

Моделювання природної мови дозволило б не тільки просунутися в рішенні проблеми автоматизації інформаційних робіт, але і найкращим для людини способом вирішити проблему спілкування з комп'ютером. Останнє особливо важливо при використанні комп'ютера в АСУ та інших сферах, де необхідно обробляти текстову інформацію. Людині зручніше виражати свої думки в мовній формі, тому безпосереднє спілкування природною мовою було б найбільш доцільним.

Мова тісно зв'язана з мисленням, тому побудова його моделей корисна також для автоматизації процесу творчості, створення штучного інтелекту. Для створення моделі мови необхідно формалізувати різноманітні й численні функції, реалізовані людиною при обробці мовної і текстової інформації. При цьому моделювання мови повинне здійснюватися на різних рівнях (морфологічному, синтаксичному, семантичному й інших).

Однією з проблем, що стоять перед дослідниками в області штучного інтелекту, є проблема застосування наукових знань про мову до рішення різних практичних задач, серед яких машинний переклад, служба науково-технічної інформації, довідково-бібліографічні роботи, редагування, каталогізація банків даних в інформаційно-довідкових системах і т.п. Дисертаційна робота вносить вклад у рішення цих проблем, тому що моделювання граматичних процесів на морфологічному рівні є складовою частиною моделі природної мови. Актуальність роботи визначається перспективністю застосування отриманих методів для розробки систем спілкування з комп'ютером природною мовою.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася згідно з планом науково-технічних робіт Харківського державного університету радіоелектроніки в рамках держбюджетної теми №159 "Розробка теорії штучного інтелекту на базі дослідження механізмів інтелекту людини та її застосування для проектування систем штучного інтелекту", розділ 1 "Розробка математичного і програмного забезпечення системи логічної підтримки проектування систем штучного інтелекту" (№ ДР 0103U001545).

Мета і задачі дослідження. Метою дисертаційної роботи є підвищення ефективності систем обробки природно-мовної інформації за рахунок формалізації структур морфології природної мови у вигляді логічних мереж, та реалізація отриманих моделей у вигляді програмних продуктів.

Для досягнення поставленої мети потрібно вирішити наступні задачі:

проаналізувати та систематизувати теоретичні та практичні наукові досягнення в області формалізації структур природної мови;

розробити методи формалізації морфологічних структур природної мови за допомогою апарату морфологічних просторів;

розробити метод бінаризації алгебраїчного формульного запису морфологічних предикатів;

побудувати логічну мережу, що моделює відмінювання повних неприсвійних прикметників російської мови; розробити метод скорочення внутрішніх станів логічної мережі.

розробити алгоритми побудовані математичні моделі та програмно їх реалізувати.

Об'єкт дослідження - алгебро-логічний апарат моделювання природної мови.

Предмет дослідження- алгебро-логічна модель відмінювання повних прикметників російської мови та модель довільних булевих рівнянь.

Методи дослідження. Основним математичним апаратом обрані логічний аналіз та алгебра скінченних предикатів. Вони є зручним засобом для логіко-математичних побудов в обраній області, та для створення повноцінного апарата моделювання механізмів природної мови у вигляді логічних мереж. Також використовувалися основні поняття булевої алгебри та теорії графів.

Наукова новизна отриманих результатів.

1. Уперше розроблено метод побудови проекційного предиката і супровідних квазітолерантностей для заданого морфологічного простору. Метод більш точно, ніж існуючі аналоги, відповідає структурі морфології, тому дозволив значно розширити клас природно-мовних структур, які можна формалізувати.

2. Уперше розроблено методи декомпозиції морфологічних предикатів і просторів та декартової декомпозиції багатомісних предикатів за допомогою унарних предикатів, що є необхідним етапом побудови формальної моделі у вигляді бінарної логічної мережі. Це дає можливість паралельної обробки природно-мовної, зокрема, морфологічної, інформації.

3. Уперше розроблено метод бінаризації алгебраїчного формульного запису морфологічних структур. Цей метод перетворює будь-яку модель, представлену системою логічних рівнянь в алгебрі скінченних предикатів, в систему бінарних предикатів, що дозволяє побудувати логічну мережу, яка забезпечує більшу швидкість обробки символьної інформації.

4. Набув подальшого розвитку метод побудови логічної мережі, який, на відміну від існуючих, моделює булеві предикатні операції, що забезпечує паралельні обчислення рівнянь алгебри предикатів.

Практичне значення отриманих результатів. Розроблені в дисертаційній роботі математичні методи формалізації морфологічних структур природної мови, алгоритми та програмна система призначені для створення логічних мереж, які, у свою чергу, є основою для побудови мозкоподібного комп'ютера паралельної дії. Математичні і програмні результати роботи можуть бути використані в системах автоматичної обробки текстової інформації (підтримка і реалізація БД, баз знань, компьютерный переклад тощо), системах автоматизованого проектування нових інформаційних технологій.

Результати, отримані в ході даної дисертаційної роботи, знайшли своє практичне застосування при побудові систем обробки природно-мовної інформації. Ці системи програмно й апаратно реалізовані на кафедрі АПОТ ХНУРЕ при проектуванні ІP-core, що реалізує функції синтаксичного аналізу мовного поводження людини (акт упровадження від 01.06.2005 р.) та в торгово-виробничому підприємстві "Європейске торгівельне обладнання" для розробки комп'ютерного комплексу для автоматизації роботи з проектування торгівельного обладнання та автоматизованого керування фірмою (акт упровадження від 31.05.2005 р.)

Теоретичні результати дисертації були використані в навчальному процесі на кафедрах Програмного забезпечення ЕОМ та Прикладної математики ХНУРЕ при підготовці курсів лекцій "Теорія інтелекту" та "Алгебраїчна логіка" для спеціальності "Програмне забезпечення автоматизованих систем" (акт упровадження від 25.05.2005 р.).

Програмне забезпечення, розроблене в дисертації, використовується в курсовому й дипломному проектуванні, у науково-дослідній роботі студентів на кафедрі ПЗ ЕОМ.

Особистий внесок здобувача. Всі результати, представлені в роботі, отримані автором самостійно. Їх основний зміст викладений у роботах [1-8]. У статті [1] автором розроблено метод представлення парадигматичної таблиці морфологічного відношення відмінювання повних неприсвійних прикметників російської мови у вигляді двочасткових графів. Розроблено програмну модель цього відношення. У роботі [2] автором проведено бінаризацію морфологічного предиката, що необхідно для побудови логічної мережі. У статті [3] автором побудовано структурну модель логічної мережі відмінювання повних неприсвійних прикметників російської мови. У статті [4] розроблено методи декомпозиції і композиції морфологічних просторів. У статті [5] автором розроблено метод побудови проекційних предикатів морфологічного простору та метод перетворення предиката до економної скобкової форми. У тезах доповіді [6] автором розроблено метод побудови морфологічного простору. У тезах доповіді [7] автором розроблено метод вирішення булевих рівнянь за допомогою логічних мереж. У тезах доповіді [8] автором розвинуто методи декомпозиції морфологічних предикатів і просторів.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на наступних конференціях: 1) [6, 8] 9-й Міжнародний молодіжний форум “Радиоэлектроника и молодежь в XXI веке”, (Харків, 19-21 квітня 2005); 2) [7] VІІІ міжнародна науково-практична конференція "Інформаційні технології: наука, техніка, технологія, освіта, здоров'я", MіcroCAD-2005, (Харьков19-20 травня 2005).

Публікації. Основні результати роботи опубліковані в 8 наукових працях, з них 5 статей, опублікованих у наукових спеціалізованих виданнях, затверджених ВАК України, 3 - тези конференцій.

Структура й обсяг дисертаційної роботи. Дисертаційна робота складається з уведення, чотирьох розділів, висновків, списку використаних джерел, додатків. Повний обсяг роботи - 153 сторінки, з них основного тексту - 150 сторінок. Дисертація містить 41 малюнок на 8 сторінках, 20 таблиць на 7 сторінках, 3 додатка на 3 сторінках, список використаних джерел з 167 найменувань на 15 сторінках.

2. ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми, сформульовано основну мету і задачі дослідження, наведено відомості про зв'язки обраного напрямку досліджень із планами організації, де виконана робота. Дана загальна характеристика роботи, сформульовано основні положення, що винесено автором на захист, визначено їх практичну цінність. Наведено дані про використання результатів дисертації в народному господарстві.

Перший розділ присвячено аналізу основних наукових досягнень у галузях формального алгебро-логічного апарату для аналізу та моделювання природної мови, практичних розробок по формалізації структур природної мови, зокрема - морфології російської мови. Проаналізовано основні наукові досягнення в області формалізації структур природної мови, створення систем із природно-мовним інтерфейсом. Обґрунтовано необхідність подальшого розвитку універсального алгебро-логічного апарату для опису природної мови. Сформульовані та обґрунтовані мета й задачі наукових досліджень, що були виконані в дисертаційній роботі.

Як формальні мови, на яких вівся опис природної мови, були випробувані мови програмування, апарат теорії графів, мова теорії алгоритмів, логічні вирахування. Виявилося, що спроби їх застосування для опису природної мови приводять до великих перешкод при моделюванні. До засобів опису лінгвістичних знань є цілий ряд вимог: незалежність лінгвістичного опису від процедур рішення конкретних задач обробки тексту; єдність виразних засобів мови опису; універсальність, що розуміється як придатність для опису цілого класу близьких за структурою мов; наочність формальних конструкцій; прийнятність для автоматичної обробки.

На основі проведеного аналізу літературних джерел показано, що існуючі формальні системи природної мови не задовольняють усім цим вимогам, не володіють достатньою гнучкістю та повнотою. Ряд моделей жорстко орієнтований на один конкретний вид граматичної обробки (частіше аналіз або синтез). При цьому об'єктом моделювання є не вся мова, а окремі її підмножини, що не дозволяє промоделювати відношення, що існують на множині всієї мови. У той же час представлення математичної моделі природної мови у вигляді системи логічних рівнянь дозволить без зміни лінгвістичного забезпечення вирішувати будь-які задачі обробки різних рівнів мови як з повним, так і з частковим завданням початкових значень.

Огляд літературних даних показав, що найбільш природним і зручним апаратом для моделювання природно-мовних структур є алгебра скінченних предикатів, що оперує буквеними змінними. Цей апарат задовольняє усім вимогам до язикових формалізмів. При цьому усі види морфологічної обробки зводяться до рішення алгебро-логічних рівнянь з різними вихідними даними (цілком або частково заданими), що при наявності алгоритму рішення цих рівнянь, значно спрощує формалізацію різних процесів обробки. При такому підході є можливість еквівалентних перетворень та мінімізації морфологічної моделі, а спільність виразних засобів робить зручним аналіз різних фрагментів моделі.

Другий розділ присвячений розробці апарата алгебри скінченних предикатів для опису структури узагальнених морфологічних просторів. Вивчені питання формалізації різних відповідностей, запропоновані варіанти абсолютних і неабсолютних, однозначних і неоднозначних предикатних визначень деяких необхідних понять. Дано визначення проекційного предиката й проектора. На морфологічних прикладах показані координатні представлення векторів у морфологічних просторах. Запропоновано методи побудови проекційного предиката і супровідних квазітолерантностей для заданого простору. Розроблено метод перетворення предикатів до економної скобкової форми.

Введемо основні поняття морфологічного простору. Предикат S(x1, x2,…, xn, y) задає над множиною B простір S у координатній системі A=A1A2…An. Предикат S називається характеристикою простору S, множина B - носієм простору S, елементи множини B - векторами або точками простору S. Елементи x1A1, x2A2,…, xnAn, що задовольняють умові

S(x1, x2,…, xn, y)=1, (1)

називаються координатами точки yB в системі A. Набір (x1, x2,…,xn,), що задовольняє умові (1), називається координатним представленням точки y. Відображення S(x1, x2,…,xn)=y A в B, що відповідає предикату S, називається відображенням координатної системи A простору S у його носій B. Предикат S(x1, x2,…,xn, y) зв'язує кожну точку yB з набором (x1, x2,…, xn) її координат x1A1, x2A2,…, xnAn (одним, багатьма або жодним). Відображення S(x1, x2,…,xn)=y кожному набору координат (x1, x2,…, xn)A ставить у відповідність точку yB (одну, багато або ні однієї).

i-м проекційним предикатом простору S називається предикат Gi(y, xi) на BAi (i=), значення якого при будь-яких yB и xiAi визначаються рівністю

Gi(y, xi)=x1A1x2A2…xi-1Ai-1 xi+1Ai+1…xnAn

S(x1, x2,…, xi,…xn, y).

Предикату Gi(y, xi) відповідає відображення gi(y)=xi з B в Ai, яке називається i-м проектором простору S над B. Проекційний предикат Gi(y, xi) зв'язує кожну точку yB простору S з її координатою xiAi (однієї, багатьма або ні однієї). Проектор gi(y)=xi кожній точці yB ставить у відповідність її координату xiAi (одну, багато або ні однієї). Іноді, в залежності від застосувань, вектор yB простору A називають його предметом, а змінні x1, x2,…,xn - ознаками предметів, значення змінної xi (i=) називають відтінками i-ї ознаки, множину Ai - i-м полем відтінків.

Розглянемо метод побудови проекційного предиката. Задані поля відтінків A1={a, b, c}; A2={, }; носій простору B={1, 2, 3}. Простір S задано його характеристикою:

S(x1, x2, y)=x1ax2(y2y3)x1bx2y2x1ax2y3.

Знаходимо проекційний предикат G1(y, x1):

G1(y, x1)=x2A2S(x1, x2, y)=S(x1, , y)S(x1, , y)=(x1a(y2y3)x1by2x1ay3)(x1a(y2y3)x1by2x1ay3)=(x1a(y2y3)x1by2)(x1ay3)=x1a (y2y3)x1by2.

Знаходимо проекційний предикат G2(y, x2):

G2(y, x2)=x1A1S(x1, x2, y)=S(a, x2, y)S(b, x2, y)S(c, x2, y)=(aax2(y2y3)abx2y2aax2y3)(bax2(y2y3)bbx2y2bax2y3)(cax2(y2y3)cbx2y2cax2y3)=(x2(y2y3)x2y3)(x2y2)=x2(y2y3)x2y3.

Проекційні предикати представлені множиною пар:

G1={(a, 2), (a, 3), (b, 2)}; G2={(, 2), (, 3), (, 3)}

Проектори простору можна одержати по проекційних предикатах або побудувати за графіком:

g1(y)=x1: y10; y2x1ax1b; y3x1a; g2(y)=x2: y10; y2x2; y3x2x2.

Для кожного предмета простору знаходимо всі відтінки кожної ознаки. По попередніх формулах знаходимо:

y=1x1; 2{a, b}; 3{a}; y=1x2; 2{}; 3{, }

Запишемо відображення, зворотні проекторам простору.

Задано: G1(y, x1)=x1a(y2y3)x1by2.

Знаходимо: g1-1(x1)=y: x1ay2y3; x1by2; x1c0.

Беремо: G2(y, x2)=x2(y2y3)x2y3.

Задано: g2-1(x2)=y: x2y2y3; x2y3.

Для кожного відтінку кожної ознаки знайдемо всі предмети даного простору. По попередніх формулах знаходимо:

x1=ay{2,3}; b{2}; c; x2=y{2,3}; {3}.

Для кожного координатного представлення знайдемо всі предмети даного простору.

S(x1, x2, y)=x1ax2(y2y3)x1bx2y2x1ax2y3.

Записуємо відображення координатної системи простору в його носій:

x1ax2y2y3; x1bx2y2; x1ax2y3; x1cx20; x1bx20; x1cx20.

Для кожного координатного представлення знаходимо всі предмети простору S: (x1, x2)=(a, )y{2, 3}. (b, ){2}; (a, b){3}; (b, ), (c, ), (c, ).

Для кожного предмета даного простору знайдемо всі набори відтінків для всіх наборів ознак.

S(x1, x2, y)=x1ax2(y2y3)x1bx2y2x1ax2y3.

Записуємо формули переходу від предметів до наборів відтінків ознак:

y10; y2x1ax2x1bx2; y3x1ax2x1ax2.

Переходимо від предметів до наборів відтінків їх ознак: y=1(x1, x2); 2{(a, ), (b, )}; 3{(a, ), (a, )}.

Твердження 1. Про узгодження двох вкладених еквівалентностей. Нехай на декартовому квадраті множини задані два бінарних предикати еквівалентності і , зв'язані наступною умовою

. (2)

Тоді знайдуться множина , функція , предикат рівності та предикат еквівалентності , задані на , такі що

, (3)

. (4)

Якщо мають місце представлення (3) й (4), то предикати й є предикатами еквівалентності, причому виконується умова (2).

У третьому розділі розвивається алгебра предикатних операцій, задана на різних просторах та їх областях, що має практичну значимість для застосування цього апарата при алгебраїчній формалізації різних структур природної мови. Уведено ряд алгебраїчних конструкцій і визначень, що дозволяють більш повно і заглиблено описувати морфологію природної мови - повні, неповні, повноохватні й поповнені морфологічні простори. Розроблені методи декомпозиції та композиції предикатів у морфологічних просторах.

Нехай S(x1, x2,…, xn, y) - предикат на A1A2…AnB, що задає простір S. Простір S називається повноохватним (або сюр'єктивним), якщо предикат S(x1, x2,…, xn, y) цілком визначений за аргументом y. Тобто для кожного вектора yB існує набір координат (x1, x2,…, xn)A (A=A1A2…An) (може бути, навіть не один), такий що S(x1, x2,…, xn, y)=1:

yB(x1, x2,…, xn)A1A2…AnS(x1, x2,…, xn, y).

Координатна система охоплює весь носій простору BA.

Тільки в повноохватному просторі всі супроводжуючі його предикати є толерантностями. Завжди, звужуючи множину B, тобто викидаючи ті вектори, що не потрапили в координатну сітку, можна зробити простір повноохватним.

Для будь-якого повноохватного простору S, заданого предикатом S(x1, x2,…, xn, y) на A1A2…AnB, існує єдиний набір (E1, E2,…, En) супроводжуючих його толерантностей.

Для будь-якого набору толерантностей E1, E2,…, En на BB знайдуться координатна система A=A1A2…An та простір S, що задається деяким предикатом S(x1, x2,…, xn, y) на A1A2…AnB, такі що ці толерантності будуть для S супровідними.

Вибір множин A1A2…An та предиката S для толерантностей E1, E2,…, En, узагалі говорячи, в абстрактному сенсі (тобто з точністю до ізоморфізму) не єдиний, тому можуть існувати такі варіанти просторів, що відрізняються не тільки позначеннями елементів A1A2…An.

Простір називається всюди визначеним, якщо його відображення S(x1, x2,…, xn)=y з A1A2…An у B задовольняє умові всюди визначеності. У противному випадку воно називається частковим.

Простір називається ін'єктивним, якщо всі його проектори однозначні. Будь-який предикат S ін'єктивного (але не тільки такого) простору виражається через його проекційні предикати G1G2…Gn у вигляді:

S(x1, x2,…, xn)=G1(y, x1)G2(y, x2)…Gn(y, xn).

На цій властивості можна заснувати метод декомпозиції предиката P(x1, x2,…, xn). Нехай S(x1, x2,…, xn)=y - предикат простору (A=A1A2…An - координатна система просторів) над B. B - носій простору. Тоді відповідно до теореми про диз'юнктивне розкладання предиката

S(x1, x2,…, xn, y)=S(a, x2,…, xn, y).

Ми виконали розкладання предиката S за змінною x1. Позначаємо: S(a, x2,…, xn, y)=Sa(x2,…, xn, y). Отримали систему n-місних предикатів Sa(aA1). Тоді

S(x1, x2,…, xn, y)=Sa(x2,…, xn, y). (5)

Будь-який ін'єктивний предикат S розкладається в кон'юнкцію його проекційних предикатів G1, G2,…, Gn:

S(x1, x2,…, xn, y) = G1(y, x1)G2(y, x2)…Gn(y, xn) (6)

Тому виходить, що предикат квазідекартового простору S теж розкладається. Предикати G1, G2,…, Gn визначені на BA1, BA2,…, BAn. У результаті декартової декомпозиції n+1-арний предикат S замінюється рівносильною йому системою бінарних предикатів Gi(i=).

Відновлення предиката P за предикатами G1, G2,…, Gn називається його декартовою композицією. Воно виконується за формулою

P(x1, x2,…, xn)=yBS(x1, x2,…, xn, y) (7)

Проекційні предикати можуть бути знайдені за формулою:

Gi(y, xi)=x1A1x2A2…xi-1Ai-1 xi+1Ai+1…xnAn

S(x1, x2,…, xn, y) (i=). (8)

Заміна багатомісного предиката (відношення) рівносильною йому системою бінарних предикатів (відношень) називається його бінаризацією.

Бінарна декомпозиція предикатів має важливе практичне значення в області формалізації логічних структур природної мови за допомогою логічних мереж.

Нехай є скінченні множини , множина та предикат , заданий на множині .

Твердження 2. Предикат можна представити у вигляді добутку бінарних предикатів

(9)

якщо і тільки якщо для будь-якого знайдуться унарні предикати , ,…, , такі що

(10)

Припустимо, деякий предикат , заданий на множині , має властивість

(11)

Твердження 3. Якщо предикати і зв'язані тотожністю (11), і предикат можна представити у вигляді

, (12)

то предикат можна представити у вигляді (9).

Наслідок. Якщо предикати і зв'язані тотожністю (11) і не можна представити у вигляді (9), то предикат не можна представити у вигляді (12).

Четвертий розділ присвячений розробці математичних моделей і методів для формалізації різних семантичних структур природної мови на базі принципів логічних мереж. На прикладі алгебро-логічної формалізації процесу відмінювання повних неприсвійних прикметників розглядається метод побудови алгебро-логічних структур, що приводять до побудови логічних мереж. Удосконалена парадигматична таблиця словотвору прикметників та розроблено метод бінаризації алгебраїчного формульного запису семантичних структур на прикладі словоформ прикметників.

Розглянемо функцію закінчення словоформи заданого слова від граматичних ознак . Аргументами цієї функції служать: - рід словоформи зі значеннями М - чоловічий, Ж - жіночий, С - середній; - число словоформи зі значеннями Е - єдине, М - множинне; - падіж словоформи зі значеннями И - називний, Р - родовий, Д - давальний, В - знахідний, Т - орудний, П - прийменниковий; - ознака одушевленості словоформи зі значеннями Н - неодушевлений, О - одушевлений; - ознака употребляемості словоформи зі значеннями Ш - широка, О - обмежена; - номер типу відмінювання слова зі значеннями від 1 - першого до 7 - сьомого.

Функція закінчення розглядалася для часткового випадку - повних неприсвійних прикметників. Тип відмінювання слова, у свою чергу, визначається однозначною залежністю змінної від ознак . Залежність називається функцією типу відмінювання слова. Аргументами цієї функції служать: - остання буква основи слова зі значеннями Б, В, Г, Д, Е, Ж, З, К, Л, М, Н, П, Р, С, Т, Х, Ц, Ч, Ш, Щ; - ознака зм'якшення останньої букви основи слова зі значеннями Т - тверда, М - м'яка; - ознака наголошення основи слова зі значеннями У - наголошена, Б - ненаголошена.

Утворюючи суперпозицію обох отриманих функцій, отримуємо однозначну залежність

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

Морфологічна функція формує закінчення у повних неприсвійних прикметників за заданим значенням ознак . Закінчення розвертається в набір букв: - перша буква закінчення; - друга, - третя. Значеннями змінної служать букви А, Я, У, Ю, О, Е, Ы, И; - букви Я, Ю, Е, Й, Г, М, Х; - букви О, У, И та знак пробілу #, який ставиться замість відсутньої третьої букви закінчення. Для знаходження формули предиката треба виявити достатню кількість бінарних зв'язків , ,..., ,..., між його аргументами й утворити з відповідних їм предикатів кон'юнкцію:

(13)

що виражає предикат . Цей процес називається бінаризацією морфологічного відношення . Наведемо приклад побудови двох таких бінарних предикатів.

Таблиця 1 Нумерація пар твердих і м'яких закінчень

Номер пари родинних закінчень

1

2

3

4

5

6

7

8

9

10

11

12

13

Тверде

ая

ую

ое

ой

ом

ого

ому

ою

ый

ым

ые

ых

ыми

М'яке

яя

юю

ее

ей

ем

его

ему

ею

ий

им

ие

их

ими

Таблиця 1 задає перший декартовий добуток, що зв'язує закінчення з ознакою зм'якшення і з номером пари родинних закінчень.

Описуємо відношення, що зв'язує закінчення з номером пари родинних закінчень:

(14)

Описуємо відношення, що зв'язує закінчення з ознакою зм'якшення закінчення (або, що те ж саме, - основи слова):

Описуємо зв'язки першої букви закінчення з ознакою зм'якшення закінчення: , а також з парами родинних букв:

Цей зв'язок виявляє другий декартовий добуток, що характеризується таблицею:

Таблиця 2 Зв'язок першої букви закінчення з ознакою зм'якшення

T	Пари родинних букв
	1	2	3	4
Т	А	У	О	Ы
М	Я	Ю	Е	И

У п'ятому розділі розробляються методи, алгоритми та програмні моделі для формалізації різних семантичних структур природної мови на базі принципів логічних мереж. Розглядається побудова алгебро-логічних структур, що приводять до характерних інженерних мереж, названих логічними. При зіставленні логічних мереж з основними типами нейроструктур виявляється глибока подібність побудови технічних і біологічних конструкцій, що дозволяє описувати в точних математичних і технічних термінах принципи функціонування мозку.

Структура логічної мережі цілком визначається її парадигмою. Для прикладу представимо один з 15 зв'язків мережі словозміни прикметників у вигляді двочасткових графів. Разом із графічним наведемо й алгебро-логічне представлення цього бінарного зв'язку.

1. Зв'язок типу контексту з родом .



Рис. 1 Зв'язок “”:Тип контексту - Рід

Отримана модель логічної мережі була протестована програмно на комп'ютері Іntel Pentіum ІV 2.4 GHz, 256MB DDR RAM, та апаратно на перепрограмувальних кристалах Xіlіnx. Цикл моделювання одного слова в FPGA складає від трьох до семи тактів (включаючи завантаження початкових значень і генерацію сигналу ready). Порівняльний аналіз ефективності апаратної і програмної реалізації дав наступні результати: програмне моделювання складає в середньому 4000 слів у секунду, апаратне (у різних сімействах Xіlіnx) - 6*106 слів у секунду (при f=43 MHz), що в 1500 разів швидше, ніж програмна реалізація.

Розглянемо на прикладі операції диз'юнкції метод побудови й роботи ще однієї логічної мережі - булевих предикатних операцій. Нехай задана операція . При побудові логічної мережі будемо вважати, що значення змінних х, у, z, t не логічні, а літерні. Додаткова змінна t означає порядковий номер набору значень (х, у, z). Вона необхідна для зворотності операції в логічній мережі. Логічна мережа має вигляд:

Розглянемо приклад роботи мережі. Функція обчислюється однозначно за набором значень (х, у). Однак у зворотну сторону - від значень змінної z до значень х, у однозначності немає. Щоб за значенням z знайти x і y, треба уточнити значення додаткової змінної t. Промоделюємо роботу мережі для одного набору значень х, у: х=0; у=0. Аналітично зв'язок усіх змінних мережі запишеться так: .

Розглянемо обидва напівтакти роботи мережі. На першому напівтакті задані значення кожної змінної х, у породжують множини відповідних їм значень змінної t - відповідно {0, 1} і {0, 2}. На другому напівтакті обчислюється перетинання цих множин. Отримуємо однозначне значення змінної z=0.

Рис. 3 Результат роботи логічної мережі на наборі х=0; у=0

Вихідне відношення , що містить всю інформацію та дозволяє проводити зворотні обчислення, має вигляд:

Використовуючи змінну , отримаємо повну (розгорнуту) бінаризацію:

У додатку наведено акти впровадження теоретичних і практичних результатів дисертаційної роботи.

ВИСНОВКИ

У дисертаційній роботі наведено результати, котрі, у відповідності з метою дослідження, в сукупності є вирішенням актуальної наукової задачі - розробки алгебро-логічних засобів формалізації морфологічних структур природної мови у вигляді комплексу математичних і алгоритмічних моделей. Розроблені моделі були застосовані в системах автоматичної обробки текстів природної мови для розробки програмного й апаратного забезпечення логічних мереж, що має велике значення для створення ефективного інтерфейсу спілкування між користувачами та автоматичними системами. У результаті вирішення сформульованої задачі:

Проаналізовано сучасний стан проблеми моделювання структур природної мови. Визначено ряд недоліків відомих систем, пов'язаних зі складністю, неповнотою та емпіричністю аналізу природно-мовної інформації в цих системах. Шляхом вирішення цієї проблеми є розробка універсального алгебро-логічного апарату та комплексу методів побудови логічних мереж, які є базою процесорів паралельної дії для природно-мовних систем. Це обумовило вибір напрямку досліджень, формулювання мети та задач дисертаційної роботи.

Уперше розроблено метод побудови проекційного предиката і супровідних квазітолерантностей для заданого морфологічного простору, відновлення морфологічного простору, коли він існує, за його проекційним предикатами. Методи дозволили значно розширити клас природно-мовних структур, які формалізуються, тому що відповідають структурі морфології більш точно, ніж існуючі аналоги.

Розроблено метод перетворення морфологічного предиката до економної скобкової форми на прикладі закінчень повних неприсвійних прикметників.

Уперше розроблено методи декомпозиції морфологічних предикатів і просторів та декартової декомпозиції багатомісних предикатів за допомогою унарних предикатів, що є необхідним етапом побудови бінарних логічних мереж. Розроблено структуру предиката, що задає повноохватний морфологічний простір. Розроблено метод практичного застосування цілком визначених n-арних предикатів. Виконана декартова декомпозиція предиката закінчень повних неприсвійних прикметників.

Уперше розроблено метод бінаризації алгебраїчного формульного запису морфологічних структур. Бінаризовано морфологічне відношення відмінювань повних неприсвійних прикметників російської мови. Отримано таблиці бінарних зв'язків, що дозволяють реалізувати модель цього об'єкта у вигляді логічної мережі програмно та апаратно.

Удосконалено парадигматичну таблицю відмінювання повних неприсвійних прикметників. Розроблено метод представлення парадигматичної таблиці морфологічного відношення відмінювання повних неприсвійних прикметників російської мови у вигляді двочасткових графів. Розроблено програмну модель відповідної логічної мережі. Набув подальшого розвитку метод побудови логічної мережі: бінаризовано булеві предикатні операції та розроблено метод скорочення її внутрішніх станів, що забезпечує паралельні обчислення рівнянь алгебри предикатів. Отримані методи побудови логічних мереж впроваджені в комп'ютерному автоматизованому комплексі для розробки, комплектації та розміщення торгівельного обладнання в службових та офісних приміщеннях, а також для автоматизованого керування фірмою та узгодження роботи її підрозділів (торгівельно-виробниче підприємство “Європейське торгівельне обладнання”, акт упровадження від 31.05.05 р.); в системах синтаксичного аналізу прикметників російської мови, що реалізовані у вигляді IP-core (ХНУРЕ, кафедра АПОТ, акт упровадження від 10.06.05 р.). Теоретичні результати дисертації були використані в навчальному процесі на кафедрах Програмного забезпечення ЕОМ і Прикладної математики (акт упровадження від 25.05.05 р.)

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Дударь З.В., Калиниченко О.В., Козяев Л.Л., Мельникова Р.В. О программной реализации логической сети // АСУ и приборы автоматики. 2005. № 130. С. 103-112.

2. Козяев Л.Л., Шабанов-Кушнаренко С.Ю. Бинаризация морфологического отношения склонения полных имен прилагательных // Радиоэлектроника и информатика. 2005. № 1. С. 106-111.

3. Калиниченко О.В., Козяев Л.Л., Мельникова Р.В. О формальной структуре логических сетей // Радиоэлектроника и информатика. 2005. № 2. С. 79-83.

4. Козяев Л.Л., Шабанов-Кушнаренко С.Ю. О методах декомпозиции предикатов в морфологических пространствах // Східно-Європейський журнал передових технологій. 2005. №2/2 (14), С. 80-83.

5. Козяев Л.Л. Об алгебрологическом аппарате морфологического пространства // Вестник Национального технического университета “ХПИ”. - Межд. научн.-техн. сборник. - Харьков: НТУ “ХПИ”, 2005. - Вып. 46. - с. 112-118.

6. Козяев Л.Л. О построении морфологического пространства // 9-й Международный молодежный форум “Радиоэлектроника и молодежь в XXI веке”, Харків, 19-21 апреля 2005. С. 382.

7. Козяєв Л.Л. Рішення булевих рівнянь за допомогою логічних мереж // MicroCad-2005. Харків. С 112.

8. Козяев Л.Л., Шабанов-Кушнаренко С.Ю. О декомпозиции морфологических предикатов и пространств // 9-й Международный молодежный форум “Радиоэлектроника и молодежь в XXI веке”, Харків, 19-21 апреля 2005. С. 381.

Размещено на Allbest.ru

...