Итеративный подход к анализу естественно-языковых текстов: логический аспект
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/47 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-47 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/c5/d9afed1c7d66ff3d6a34722057b160c5.pdf |
| spelling |
pp_isofts_kiev_ua-article-472018-07-25T14:29:23Z Итеративный подход к анализу естественно-языковых текстов: логический аспект Kryvyi, S.L. Bibikov, D.S. Анализ естественно языкового текста; Извлечение знаний Описывается логический подход к анализу естественно языкового текста с целью извлечения знаний. В частности рассматривается использование линейной темпоральной логики для анализа и представления модальностей в таком тексте.A logical approach to analysis of natural language text for extraction knowledges from this text is described. In special case consider using of linear temporal logic for representations of modalities in such text. Інститут програмних систем НАН України 2015-09-10 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/47 PROBLEMS IN PROGRAMMING; No 2-3 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2012) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/47/48 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-07-25T14:29:23Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
|
| spellingShingle |
Kryvyi, S.L. Bibikov, D.S. Итеративный подход к анализу естественно-языковых текстов: логический аспект |
| topic_facet |
Анализ естественно языкового текста Извлечение знаний |
| format |
Article |
| author |
Kryvyi, S.L. Bibikov, D.S. |
| author_facet |
Kryvyi, S.L. Bibikov, D.S. |
| author_sort |
Kryvyi, S.L. |
| title |
Итеративный подход к анализу естественно-языковых текстов: логический аспект |
| title_short |
Итеративный подход к анализу естественно-языковых текстов: логический аспект |
| title_full |
Итеративный подход к анализу естественно-языковых текстов: логический аспект |
| title_fullStr |
Итеративный подход к анализу естественно-языковых текстов: логический аспект |
| title_full_unstemmed |
Итеративный подход к анализу естественно-языковых текстов: логический аспект |
| title_sort |
итеративный подход к анализу естественно-языковых текстов: логический аспект |
| description |
|
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2015 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/47 |
| work_keys_str_mv |
AT kryvyisl iterativnyjpodhodkanalizuestestvennoâzykovyhtekstovlogičeskijaspekt AT bibikovds iterativnyjpodhodkanalizuestestvennoâzykovyhtekstovlogičeskijaspekt |
| first_indexed |
2025-07-17T09:46:11Z |
| last_indexed |
2025-07-17T09:46:11Z |
| _version_ |
1838409376281395200 |
| fulltext |
Теоретичні та методологічні основи програмування
УДК 004.318
ИТЕРАТИВНЫЙ ПОДХОД К АНАЛИЗУ ЕСТЕСТВЕННО-ЯЗЫКОВЫХ
ТЕКСТОВ: ЛОГИЧЕСКИЙ АСПЕКТ
С.Л. Крывый, Д.С. Бибиков
Киевский национальный университет имени Тараса Шевченко, тел.: (044) 522 3433, email:krivoi@i.com.ua
Институт кибернетики им. В.М. Глушкова НАН Украины, email: bb_coff@mail.ru
Описывается логический подход к анализу естественно языкового текста с целью извлечения знаний. В частности рассматривается
использование линейной темпоральной логики для анализа и представления модальностей в таком тексте.
A logical approach to analysis of natural language text for extraction knowledges from this text is described. In special case consider using of
linear temporal logic for representations of modalities in such text.
Введение
Проблемы, связанные с анализом естественно-языковых объектов (ЕЯО) традиционно относят к области
искусственного интеллекта. Однако, объективные трудности, возникающие на пути анализа ЕЯО, не позволяют
удовлетворительно решать проблему автоматизации такого анализа. Эти трудности связаны с тем, что
проблема анализа ЕЯО относится к областям, которые плохо поддаются формализации.
Отметим некоторые из трудностей, связанных с таким анализом. Как формализовать и смоделировать
- эмоциональную окраску естественно-языкового текста (ЕЯТ);
- знания, имеющиеся в предложениях иронического характера;
- знания, имеющиеся в предложениях иносказательного характера;
- правдоподобные знания и достоверные знания;
- понятие здравого смысла и здравого рассуждения и т. д. и т. п.
Одни исследователи этих проблем считают, что моделирование знаний, извлеченных из ЕЯТ, не может
ограничиваться формализацией только лишь непогрешимого интеллекта. Естественным основанием для такого
мнения является то, что важной чертой естественного интеллекта есть способность вырабатывать здравые
суждения, которые могут оказаться и недостоверными. В случае неполной, неточной и изменчивой
информации наши суждения часто становятся только предположительными, а в следствии этого лишь
правдоподобными и поэтому могут подлежать пересмотру и уточнению (модификации). Примером такого типа
рассуждений является диагностика. Здесь, необходима формальная теория модифицируемых рассуждений.
Другие исследователи считают, что проблема анализа ЕЯТ решена, если извлеченные знания
представлены в базе знаний и все проблемы по их анализу решаются средствами баз знаний. Это мнение, с
нашей точки зрения, не совсем соответствует реальному состоянию дел. Главная проблема при обработке
знаний в базах знаний – это та же модифицируемость знаний. Модификация знаний необходима по многим
причинам. Различают два фундаментальных типа модифицируемых знаний: предположительные и
индексируемые.
Предположительные знания являются всего лишь правдоподобными. Это связано с тем, что они
неточные, поскольку базируются на неполной, неточной и изменчивой информации, а также по причине их
естественной неточности и модифицируемости. Примерами такого типа знаний являются рассуждения по
умолчанию, рассуждения с прототипами и знания статистического характера.
Индексируемые знания – это рассуждения, которые основаны на знаниях, предполагаемых полными, но
которые таковыми не являются или перестают быть таковыми. В действительности часто встречается ситуация,
когда выдвигаются модифицируемые (а иногда и неявные) соглашения, для наращивания наших знаний в
условиях неполной или неизвестной информации. Основываясь на таких знаниях наши выводы могут быть
логически корректными по отношению к этим добавленным знаниям. Однако, эти рассуждения оказываются
модифицируемыми, так как они основываются на изменчивом состоянии знаний. Следует отметить, что
некоторые корректные формы вывода, которые формализует классическая математическая логика, могут
оказаться модифицируемыми. Это объясняется тем, что они применяются к базе знаний, которая зачастую
пополняется всего лишь правдоподобными знаниями. Например, знания, занесенные одним исследователем в
базу знаний, могут быть неправильно или неточно поняты и поэтому будут подвергаться модификации другим
исследователем.
По проблеме анализа ЕЯО существует огромная литература, в которой описываются различные методы и
подходы к решению частных случаев упомянутых проблем [1 – 6]. В частности, в работах [5 – 7] описывались
способы извлечения первичных знаний из ЕЯТ, ограничиваясь окрестностью одного предложения (именно в
этом смысле и употреблялось слово «первичных»).
10
В данной работе рассматривается задача семантического анализа предложений естественного языка с
целью извлечения знаний, не ограничиваясь рамками одного предложения и с учетом модальностей. Первичной
информацией при таком подходе выступает информация, которую дает система частотного анализа слов в ЕЯТ
© С.Л. Кривий, Д.С. Бибиков, 2012
ISSN 1727-4907. Проблеми програмування. 2012. № 2-3. Спеціальний випуск
mailto:krivoi@i.com.ua
Теоретичні та методологічні основи програмування
[6]. На первом шаге итерации все глаголы и предикатные слова объявляются отношениями, на втором шаге
итерации уточняется арность этих отношений и выполняется их семантический анализ в пределах одного
предложения, на третьем шаге выполняется уточнение семантического смысла полученной информации исходя
из некоторой локальной части текста или из всего текста в целом. Данный подход можно выполнять как в
автоматизированном режиме, так и в диалоговом. Извлеченные из текста отношения трактуются как знания, в
виде формул логики предикатов первого порядка, а модальности – в виде формул линейной темпоральной
логики. Потом полученные формулы линейной темпоральной логики транслируются в формулы логики
первого порядка. Отношения, соответствующие извлеченным предикатам, или сами предикаты заносятся в базу
знаний, с помощью которой выполняется дальнейший логический и информационный анализ (схема такого
анализа показана на рис. 1).
ЕЯТ
анализ
предложений БД+БЗ
Логический
анализ
модификация
итерационный
процесс
выделяем следствия,
которые нас интересуют
Рис. 1. Схема анализа ЕЯТ
Анализ такого типа существенно облегчается, если ЕЯТ является структурированным. Ведущей
парадигмой структурирования информации на сегодняшний день являются онтологии или иерархические
концептуальные структуры, представляющие собой модель предметной области, состоящей из иерархии
понятий (концептов) предметной области, связей между ними и законов, действующих в рамках этой модели.
Поэтому данный анализ ЕЯТ может служить одной из ступенек построения онтологий.
Формальная постановка задачи
Процесс автоматизации какой-либо деятельности, как правило, требует формализованной постановки
задачи, которая дает возможность выполнения анализа данной задачи с целью выработки метода ее решения.
Когда речь идет об автоматизации процесса извлечения знаний из ЕЯТ и построения соответствующей
онтологии, то необходимо определить понятия «знание» и «извлечение знания». С целью формализации
вышеуказанных понятий, введем следующие определения, пользуясь нотацией констрейнтного
программирования [3].
Пусть дано некоторое множество D, на котором определена конечная совокупность
отношений конечной арности. Языком ограничений на называется
непустое множество . Проблема выполнимости ограничений из формулируется следующим образом.
{ 1 , , kR R R= K } ,
}
}
, 1,2, ,n
iR D i k⊆ = K L D
L R⊆ L
Для произвольного множества и языка ограничений на проблемой выполнимости ограничений
является решение такой комбинаторной задачи:
D L D
( )CSP L
дана тройка , где ( , , )P V D C=
- – конечное множество переменных; { 1, , mV v v= K
- – конечное множество ограничений, где ограничение из С – пара { 1, , qC c c= K ic ( , )i is R , где
1( ,..., )i i ijs v v= – кортеж, состоящий из переменных, iR L nj∈ − -арное отношение на ; D
найти функцию :V Dϕ → такую, что ( , )i is R C∀ ∈ кортеж 1( ( ), , ( ))i ijv v iRϕ ϕ ∈K либо убедится в том,
что её не существует, Множество в этом случае называется областью проблемы, а функция 1, 2, , .i = K k D ϕ
называется интерпретацией . ( )CSP L
В случае анализа ЕЯТ с целью извлечения знаний множество интерпретируется как множество
объектов, извлечённых из входного текста Т, которое факторизовано по некоторому отношению
эквивалентности R (это отношение будем называть отношением синонимии) и в котором «закодированы»
отношения Переменные из множества
D
, 1, 2, ,iR i k= K
11
. 1 2{ , , , }mV v v v= K принимают свои значения в этом
факторизованном множестве объектов, фигурирующих в тексте Т (это могут быть лексико-грамматические
разряды, конкретные объекты (люди, даты, предметы и т. п.)).
Теоретичні та методологічні основи програмування
Проблемой извлечения знаний из ЕЯТ называется проблема поиска интерпретации :V Dϕ → с явным
построением отношений совокупности . При этом, отношения iR L R⊆ , 1, 2,..., ,iR L i k∈ = извлеченные из
текста T, будем называть знаниями.
Приведенное определение достаточно общее и его необходимо уточнять для настройки на конкретную
область применения. Конкретизация интерпретации отношений в таком случае определяется целями, которые
преследуются при анализе данного текста Т. Хорошо известными примерами такого уточнения являются
следующие примеры.
1. Лексико-грамматический анализ приводит к конкретизации интерпретации :V Tϕ → и отношений
. Интерпретация iR L∈ ϕ в данном случае представляется в виде суперпозиции двух функций 1ϕ и 2ϕ , т. е.
2 1 1 2( ) ( ( )) ( )V V Vϕ ϕ ϕ ϕ ϕ= = ∗ , где означает суперпозицию функций. Функции ∗ 1ϕ и 2ϕ реализуют процесс
синтаксического и семантического анализа предложений текста Т, а отношения 1R и 2R – это синтаксические
ограничения (синтаксические правила языка, в котором представлен текст Т) и семантические ограничения.
Функцию 1ϕ тоже можно рассматривать как суперпозицию отображений 11ϕ и 12ϕ , которые реализуют
соответственно морфологический и синтаксический анализ предложений ЕЯТ Т и которые вместе с
отображением 2ϕ составляют классическую систему лексико-грамматического анализа [4].
2. Силлогистика Аристотеля – другой пример уточнения интерпретации ϕ и отношений . В этом
случае интерпретация
iR L∈
ϕ носит теоретико-множественный характер, а отношения – это отношение
включения для множеств и его свойства. Более полное описание этого уточнения можно найти в [5, 7, 8].
iR L∈
3. Текст библиографического характера – пример хорошо структурированного текста. Это значит, что
проблему извлечения знаний из такого текста можно решить в автоматизированном режиме.
Пример автоматизированной обработки ЕЯТ
Рассмотрим пример автоматизированной обработки некоторого фрагмента ЕЯТ T. Подсистема
частотного анализа использует толковый словарь естественного языка (это может быть словарь
русского, украинского, английского или какого-либо другого естественного языка).
S ( )L X
Текст состоит из предложений языка , не содержащий никаких символов, кроме символов
алфавита X (т. е. T не содержит формул, графиков, рисунков и т. п.). Эта подсистема реализует отношение
T ( )L X
γ ,
которое является суперпозицией двух отношений 1 2γ γ∗ , выполняемых последовательно. Содержательно
отношение 1γ означает распознавание принадлежности слова к данному языку и проверку правильности
написания слова it , где , в соответствии с написанием его в толковом словаре, т. е.
ji t∈ it T∈
1
1, если ;
( )
0, если .
j
j
j
i
i
i
t S
t
t S
∈⎧⎪γ = ⎨ ∉⎪⎩
Если слово i распознано в словаре S, то оно заносится в словарь T
jit t∈ ′правильных слов, а если это не
так, то предусматривается сигнализация о том, что данное слово отсутствует в словаре S и принимается
решение о добавлении данного слова в словарь или его исправлении (слово может быть искажено, например, в
следствии сканирования текста Т).
Словари S и – входные данные для отношения T ′ 2γ . Содержательный смысл отношения 2γ сводится к
тому, что если 1( ) 1
jitγ = , то 2 ( )
jitγ определяет его грамматическую единицу языка (имя собственное,
сказуемое, существительное, числительное и т. п.), а также возможные флексии слова . Областью
интерпретации текста T является модель
jit t∈
12
i
( , )A D П= , где – это исходный текст, возможно расширенный
некоторой дополнительной информацией, а сигнатура предикатов (отношений) П определяется из текста T в
результате использования информации о различных вхождениях слова в предложения . При этом
вычисление отношения ограничивается отдельно взятым предложением
T
jit it T∈
ϕ it T∈ , определяемым каждым
вхождением слова в текст T. В случае трудности определения предиката
jit iπ ∈Π , предусматривается
диалоговый режим вычисления и ( )iϕ π ( ( ))iγ ϕ π . Предлагаемая система анализа на рис. 2 выглядит следующим
образом:
Теоретичні та методологічні основи програмування
Тол
ков
ый
сл
ова
рь,
S
Текст, T
Текст,
правильный
T
21 γγγ ∗=
Словарь , T
Результаты анализа T
Гр
ам
ма
ти
че
ск
ие
ед
ин
иц
ы
Д
ли
на
, Т
Ко
ли
че
ст
во
пр
ав
ил
ьн
ы
х
сл
ов
Ча
ст
от
а
вх
ож
де
ни
я
Программа
обработки P1
База знаний
где записываются
результаты
анализа
Таблица VT
первое вхождение
второе вхождение
Слово t i j
t i j
Семантический
анализ
вхождения
в t i
Программа P2
Рис. 2. Схема системы анализа предложений естественного языка
В этой схеме отношение 1 2γ = γ ∗ γ вычисляет программа . Результатом ее работы является два файла 1P
1F и 2F , заполненные соответственно числовыми характеристиками слов входного текста и словами
предложений этого текста. Структура файла
T
jit
2F показана на рис. 3.
Рис. 3. Структура файла 2F
13
Файлы 1F и 2F , сформированные программой , служат входными данными для работы программы
, которая вычисляет отношение . При этом, работа программы сводится к построению таблицы для
слов , . Затем, по этой таблице и предложениям текста определяется семантический смысл
рассматриваемого предложения. Предложение
1P
2P ϕ 2P TV
ji it t∈ it T∈ T
it T∈ определяется на основе номера вхождения слова в
текст T с помощью таблицы , вид которой показан на рис. 4.
jit
TV
Теоретичні та методологічні основи програмування
Рис. 4. Структура таблицы TV
Итеративный подход к анализу ЕЯТ: логический аспект
В общем случае неструктурированного текста семантический анализ затруднителен и возникает вопрос:
каким ограничениям должен удовлетворять исходный текст, чтобы можно было каким либо образом
анализировать ЕЯТ. Ответ на этот вопрос усложняется ещё и тем, что в ЕЯТ возможны временные зависимости
и модальности. Примером такого типа предложений могут служить предложения «Пока брат не извинится, я с
ним не буду разговаривать» и «Я всегда любил играть в крокет и до вчерашнего дня я любил пить после игры
кофе, а с сегодняшнего дня я пью только чай». Учитывая эту ситуацию предлагается вести анализ ЕЯТ
итеративным методом, используя толковый словарь, словарь, извлечённый из текста, места вхождения слов в
ЕЯТ и частотный анализ слов. Поясним итеративный подход к анализу ЕЯТ с помощью примера. С этой целью
рассмотрим фрагмент некоторого текста из книги Эрленд Лу «НАИВНО. СУПЕР».
«Я всегда любил играть в крокет со своим братом. Но после ссоры с братом, я заявил, что пока брат не
извинится, я с ним не буду разговаривать… Вчера брат пришёл с извинениями и я его простил. На следующий
день мы с братом стали играть в крокет. Это бывает нечасто. Принадлежности для крокета, брошенные
под сараем, совсем сгнили. Мы объездили несколько заправок в поисках нового комплекта. Брат расплатился
по одной из своих кредитных карточек. Потом мы шагами отмерили в родительском саду расстояния, вбили в
землю воротца и колышки. Я выбрал красный цвет, мой брат – желтый.
Мы начали играть, и некоторое время все шло прекрасно. Я быстро прошел первые и вторые воротца.
Заработал дополнительный ход и продолжил игру …»
На первом шаге итерации, как было сказано ранее, все глаголы и предикатные слова объявляются
отношениями. Например, в предложении «Вечером мы с братом стали играть в крокет», как глагол, первым
выделяется словосочетание «стали играть», которое в диалоговом режиме уточняется со специалистом. В
результате чего мы получаем в черновом варианте предикат СТАЛИ_ИГРАТЬ (я, брат, крокет). Далее, из
предложения «Мы объездили несколько заправок в поисках нового комплекта» получаем ИСКАТЬ (я, брат,
комплект, заправок), а так же ОТМЕРИЛИ (я, брат, сад, расстояния), ВБИЛИ (я, брат, воротца) и ВБИЛИ (я,
брат, колышки) и т.д.
При анализе сложных (сложно подчинённых) предложений они автоматически разбиваются на простые,
причем существительное которое присутствует в одной из составляющих частей, дублируется и на вторую
часть предложения. Таким образом, вместо одного предложения «Потом мы шагами отмерили в родительском
саду расстояния, вбили в землю воротца и колышки.», мы получаем два простых: «Шагами отмерили в
родительском саду расстояния», «мы вбили в землю воротца» и «мы вбили в землю колышки» которыми
оперирует программа.
Разбиение сложного предложения на простые никак не влияет на логическую связанность текста, потому
как первый этап препроцессинга подразумевает построения статистической таблицы VT аналогично той, что
показана на рис. 4, в которой четко фиксируется какому предложению принадлежат слова.
На втором шаге выполняется определение арности и окончательное формирование предикатов. Как
результат получаем следующие предикаты: ИСКАТЬ (я, брат, комплект) арность 3, а так же МЕРЯТЬ (я, брат,
расстояния) арность 3, ВБИВАТЬ (я, брат, воротца), ВБИВАТЬ (я, брат, колышки) – арности обоих отношений
3. Если арность больше 2, тогда имеет место замена предиката на конъюнкцию двух новых: ВБИВАТЬ (я,
воротца) ВБИВАТЬ (я, колышки) ВБИВАТЬ (брат, воротца) ∧ ∧ ∧ ВБИВАТЬ (брат, колышки). В
14
Теоретичні та методологічні основи програмування
приведенном случае семантическая обработка дает нам эквивалентную замену «мы» на смысловую
конъюнкцию «я» «брат», и тогда вместо полученных ранее трех предикатов, получаем две конъюнкции:
ИСКАТЬ (я, комплект) ИСКАТЬ (брат, комплект), МЕРЯТЬ (я, расстояния)
∧
∧ ∧МЕРЯТЬ (брат, расстояния) и
т. д.
Таким образом, получаются такие предикаты:
- ЛЮБИТЬ_ИГРАТЬ_КРОКЕТ (я, брат);
- ССОРА (я, брат);
- РАЗГОВАРИВАТЬ (я, брат);
- ИЗВИНЯТЬСЯ (брат, я);
- ПРОСТИТЬ (я, брат);
- СТАЛИ_ИГРАТЬ_КРОКЕТ (я, брат);
- и т. д.
Что касается модальностей и временных зависимостей, имеющихся в тексте, то на помощь приходит
модальная временная логика. Начало вышеприведенного текста принимает такую форму в этой логике:
F − (ЛЮБИТЬ_ИГРАТЬ_КРОКЕТ (я, брат)) – «Я всегда любил играть в крокет со своим братом».
O− (ССОРА(я, брат)) – «после ссоры с братом»,
(ИЗВИНЯТЬСЯ (брат, я)) ( РАЗГОВАРИВАТЬ (я, брат)) – «пока брат не извинится, я с ним не буду
разговаривать…»
∪ ¬
O− (ИЗВИНЯТЬСЯ (брат, я)) (ПРОСТИТЬ (я, брат)) – «вчера брат пришёл с извинениями и я его
простил».
∧ O−
O (СТАЛИ_ИГРАТЬ_КРОКЕТ (я, брат)) – «На следующий день мы с братом стали играть в крокет».
Тогда зависимости между предложениями выглядят таким образом:
( F − (ЛЮБИТЬ_ИГРАТЬ_КРОКЕТ (я, брат)) ∧ O− (ССОРА (я, брат)) →
((ИЗВИНЯТЬСЯ (брат, я)) (¬ РАЗГОВАРИВАТЬ (я, брат))); ∪
( O (ИЗВИНЯТЬСЯ (брат, я)) ( ПРОСТИТЬ (я, брат))
− ∧ O− →
O (СТАЛИ_ИГРАТЬ_КРОКЕТ (я, брат)).
Если в процессе такого анализа возникают трудности с определением смысла того или иного
предложения, то уточнение семантического смысла выполняется в диалоговом режиме при появлении
семантической неоднозначности. Подобного рода ситуация может появиться, например, в таком предложении:
«Проезжая по набережной Черного моря, он сравнил облака с танцующими сатирами. Но когда он
присмотрелся, то понял, что на самом деле эти небесные сатиры не плясали а плыли». Из первого предложения
получаем, что существительное «облака» логично эквивалентно понятию «сатиры», а из второго предложения
находим, что сатиры на небе не танцуют, а плывут. Что же на самом деле имеет место в этом предложении –
«облака пляшут или плывут»? В таком случае специалисту на выбор предлагаются варианты семантических
значений слова. Полученные таким образом формулы и отношения транслируются в формулы логики
предикатов и по результатам этой трансляции строится база знаний.
Трансляция формул линейной темпоральной логики в формулы языка предикатов
первого порядка
Для описания процесса трансляции формул линейной темпоральной логики (LTL) в формулы логики
предикатов первого порядка, приведем определение синтаксиса и семантики формул LTL.
Синтаксис LTL (linear temporal logic). Пусть { , , ,...}P p q r= – множество пропозициональных
атомарных высказываний. Тогда синтаксис LTL строится по таким правилам:
: | 0 | | |LTL P LTL LTL LTL LTL LTL LTL+ −= → ∪ ∪ ,
где 0 – логическая константа false; → – импликация; +∪ и −∪ – модальные until-операторы
настоящего и будущего, а также для прошедшего соответственно. Остальные связки вводятся с помощью таких
эквивалентностей:
0¬ = →ϕ ϕ , 1 0 0 0¬ = → ∨ = ¬ →, ψ ϕ ψ , = ϕ
( ) ( )∧ = ¬ ¬ ∨¬ = ¬ →¬ϕ ψ ϕ ψ ϕ ψ ,
( ) ( )⇔ = → ∧ →ϕ ψ ϕ ψ ψ ϕ .
Модальные операторы G, F, ,F G− − а также O (next) вводятся с помощью until-операторов +∪ и −∪
следующим образом:
( )0O += ∪ϕ ϕ , ( )1F += ∪ϕ ϕ , ( )1G F += ¬ ¬ = ¬ ∪ ¬ϕ ϕ ϕ ,
(1 ), .F G− − − −F⇔ ∪ ⇔ ¬ ¬φ φ φ φ
Семантика LTL-формул. Семантика формул LTL описывается с помощью модели Крипке, которая для
LTL имеет вид ( 0, , , )M T R I t= , где Т – множество моментов времени, 0t T∈ – начальный момент времени, а I –
интерпретация, сопоставляющая отношению бинарное отношение достижимости – отношение линейного R
15
Теоретичні та методологічні основи програмування
порядка ( )I R T= ≤ ⊆ ×T
,
, а каждому – подмножество тех моментов времени, в которые -истинно.
Семантика LTL – формул определяется на модели М таким способом:
p P∈ p
0| ( ),M p t I p p P= ⇔ ∈ ∈
| 0,M ≠
| ( ) из | |M M= → ⇔ = = ,Mϕ ψ ϕ ψ
1 0 1 1( )( & | )t T t t t &∃ ∈ < =ψ
| ( )M += ∪ ⇔ϕ ψ
2 0 2 1 2( )( |t T t t t t )∀ ∈ < < → =ϕ
1 1 0 1( )( & | )t T t t t &∃ ∈ < =ψ
| ( )M −= ∪ ⇔ϕ ψ
2 1 2 0 2( )( |t T t t t t )∀ ∈ < < → =ϕ
Известно, что формулы линейной темпоральной логики транслируются в язык FOL с одной свободной
переменной [9]. Правила трансляции получаются из определения семантики LTL-формул, которая приведена
выше. В результате получается некоторый фрагмент FOL, называемый языком монадической логики первого
порядка и обозначаемый mFOL.
Исходя из определения семантики LTL – формул, определяются правила трансляции в язык FOL, а
точнее в язык монадической логики первого порядка (mFOL):
0 0( ) ( ), , ,FOL p p t где p P t T= ∈ ∈
0 0 0 0(0) ( ) ( ),FOL t t t t= ≠ = ¬ =
( ) ( ) (FOL FOL FOL→ = → )ϕ ψ ϕ ψ
1 0 1 0 1( ) ( )( & ( ){ : })FOL t T t t FOL t t+∪ = ∃ ∈ < =ϕ ψ ψ &
})
2 0 2 1 0 2( )( ( ){ :t T t t t FOL t t∀ ∈ < < → =ϕ ,
1 1 0 0 1( ) ( )( & ( ){ : })FOL t T t t FOL t t−∪ = ∃ ∈ < =ϕ ψ ψ &
})
2 1 2 0 0 2( )( ( ){ :t T t t t FOL t t∀ ∈ < < → =ϕ ,
где переменные и – произвольные переменные, которые не входят в формулы 1t 2t ( )FOL ϕ и ( )FOL ψ , а
FOL означает (программу) алгоритм трансляции.
Такую трансляцию иногда называют стандартной трансляцией. В процессе трансляции формул +∪ϕ ψ ,
−∪ϕ ψ и oϕ символами t′ и обозначают произвольные переменные, которые не входят в t′′ ( )FOL ϕ или
( ).FOL ψ Формула 0( ){ : }FOL t t′=ϕ означает формулу ( ),FOL ϕ где каждое свободное вхождение переменной
замещается переменой t . 0t ′
Например, предложение «До тех пор, пока нет запроса на доступ к общей памяти от некоторого процесса
вычислений, до тех пор не будет разрешения на доступ к общей памяти». Это предложение переводится в LTL-
формулу:
( ( ) ( )) ( )ent c m req c m ent c m− +¬ − − ∪ − − ∪ − − ,
где en и обозначают формулы «есть доступ к общей памяти» и «есть запрос к общей
памяти», соответственно. Тогда трансляция этой формулы имеет вид:
t c m− − req c m− −
(( ( ) ( )) ( ))FOL ent c m req c m ent c m− +¬ − − ∪ − − ∪ − − =
1 0 1 1 2 0 2 1 0 2( ( ) ( (( )))){ : }t t t ent c m t t t t t FOL ent c m req c m t t−= ∃ < ∧ − − ∧∀ < < → ¬ − − − − = =U
1 0 1 2 0 2 1 3 3 2 3
4 3 4 2 4
( ( 1) ( ) ( ( )
( ( )))).
t t t req c m t t t t t t t t req c m t
t t t t ent c m t
= ∃ < ∧ − − ∧ ∀ < < → ∃ < − − ∧
∧∀ < < →¬ − −
Как видно из работы алгоритма FOL, язык mFOL должен содержать два предиката: и <Π =< ≠Π = ≠ .
Свойства этих предикатов следующие:
а) свойства предиката <Π :
а1) (транзитивность) ( , ) & ( , ) ( , )t t t t t t< < <′ ′ ′′Π Π →Π ′′
а2) (иррефлексивность) ( , ) 0t t<Π →
б) свойства предиката ≠Π :
б1) (симметричность) ( , ) ( , )t t t t≠ ≠′Π ⇔ Π ′
б2) (иррефлексивность) ( , ) 0t t≠Π →
Учитывая предикаты <Π и , транслятор FOL принимает вид: ≠Π
0( ) ( )FOL P P t=
0 0(0) ( , ),FOL t t≠= Π
( ) ( ) (FOL FOL FOL→ = → )ϕ ψ ϕ ψ
1 0 1 0 1( ) ( )( ( , ) & ( ){ : })FOL t t t FOL t t+
<∪ = ∃ Π =ϕ ψ ψ &
16
Теоретичні та методологічні основи програмування
2 0 2 2 1 0 2&( )( ( , ) & ( , ) ( ){ : })t t t t t FOL t t< <∀ Π Π → =ϕ ,
1 1 0 0 1( ) ( )( ( , ) & ( ){ : })FOL t t t FOL t t−
<∪ = ∃ Π =ϕ ψ ψ &
2 1 2 2 0 0 2&( )( ( , ) & ( , ) ( ){ : })t t t t t FOL t t< <∀ Π Π → =ϕ ,
где и не являются переменными формул 1t 2t ( )FOL ϕ и ( ).FOL ψ
Применим теоретические выводы к конкретным примерам:
а) «Я всегда любил играть в крокет со своим братом». Это выражение имеет следующее представление:
( _ _ ( ,F ЛЮБИТЬ ИГРАТЬ КРОКЕТ я брат− ⇒))
( )( )( )1 _ _ ,ЛЮБИТЬ ИГРАТЬ КРОКЕТ я брат−⇒ ¬ ∪ ¬ ⇒
1 0 1 2 0 2 2 1( ( , ) _ _ ( , )) ( ( , ) ( , ) 1)t t t ЛЮБИТЬ ИГРАТЬ КРОКЕТ я брат t t t t t< < <⇒ ∃ Π ∧ ∧∀ Π ∧Π → ⇒
1 0 1 2 0 2 2 1(( ) _ _ ( , )) (( ) ( ) 1);t t t ЛЮБИТЬ ИГРАТЬ КРОКЕТ я брат t t t t t⇒∃ < ∧ ∧∀ < ∧ < →
б) «после ссоры с братом»:
( ( , ))O ССОРА я брат− ⇒
1 1 0 2 1 2 2 0( ( , ) ( ( , )) ( ( , ) ( , ) ( , ))t t t ССОРА я брат t t t t t ССОРА я брат< < <⇒ ∃ Π ∧ ∧ ∀ Π ∧Π → ⇒
1 1 0 2 1 2 2 0( ( ) ( ( , )) ( ( ) ( ) ( , )t t t ССОРА я брат t t t t t ССОРА я брат⇒ ∃ < ∧ ∧ ∀ < ∧ < → ;
))
))
в) «пока брат не извинится, я с ним не буду разговаривать…»:
( ( , )) ( ( ,ИЗВИНЯТСЯ брат я РАЗГОВАРИВАТЬ я брат∪ ¬ ⇒
1 0 1 1 2 0 2 2 1
2
( ( , )) ( ( , )( )) ( ( , ) ( , )
( ( , )( ))
t t t РАЗГОВАРИВАТЬ я брат t t t t t t
ИЗВИНЯТЬСЯ брат я t
< < <⇒ ∃ Π ∧ ¬ ∧ ∀ Π ∧Π →
⇒
1 0 1 2 0 2 2 1( ( )) ( ( , )) ( ( ) ( )
( ( , ));
t t t РАЗГОВАРИВАТЬ я брат t t t t t
ИЗВИНЯТЬСЯ брат я
⇒ ∃ < ∧ ¬ ∧ ∀ < ∧ < →
г) «вчера брат пришел с извинениями и я его простил»:
( ( , )) ( ( ,O ИЗВИНЯТЬСЯ брат я O ПРОСТИТЬ я брат− −∧ ⇒
0 ( ( , )) 0 ( ( , ))ИЗВИНЯТЬСЯ брат я ПРОСТИТЬ я брат− −⇒ ∪ ∧ ∪ ⇒
1 1 0 2 1 2 2 0( ( , ) ( ( , ))) ( ( , ) ( , ) ( , ))t t t ИЗВИНЯТЬСЯ брат я t t t t t ИЗВИНЯТЬСЯ брат я< < <⇒ ∃ Π ∧ ∧ ∀ Π ∧Π → ∧
1 1 0 2 1 2 2 0( ( , ) ( ( , ))) ( ( , ) ( , ) ( , )t t t ПРОСТИТЬ я брат t t t t t ПРОСТИТЬ я брат< < <∧ ∃ Π ∧ ∧ ∀ Π ∧Π → ⇒
1 1 0 2 1 2 2 0( ( ) ( ( , ))) ( ( ) ( ) ( , ))t t t ИЗВИНЯТЬСЯ брат я t t t t t ИЗВИНЯТЬСЯ брат я⇒ ∃ < ∧ ∧ ∀ < ∧ < → ∧
1 1 0 2 1 2 2 0( ( ) ( ( , ))) ( ( ) ( ) ( , ))t t t ПРОСТИТЬ я брат t t t t t ПРОСТИТЬ я брат∧ ∃ < ∧ ∧ ∀ < ∧ < →
д) «на следующий день мы с братом стали играть в крокет»
( _ _ ( , ))O СТАЛИ ИГРАТЬ КРОКЕТ я брат ⇒
0 _ _ ( ,СТАЛИ ИГРАТЬ КРОКЕТ я брат+⇒ ∪ ⇒)
)
1 0 1 2 0 2 2 1( ( , ) ( _ _ ( , )) ( ( , ) ( , ) 0)t t t СТАЛИ ИГРАТЬ КРОКЕТ я брат t t t t t< < <⇒ ∃ Π ∧ ∧ ∀ Π ∧Π → ⇒
1 0 1 2 0 2 2 1( ( ) ( _ _ ( , )) ( ( ) ( ) 0t t t СТАЛИ ИГРАТЬ КРОКЕТ я брат t t t t t⇒ ∃ < ∧ ∧ ∀ < ∧ < → .
Заключение
Описанные в данной работе способы автоматизации обработки ЕЯТ составляют основу как
теоретического, так практического анализа извлечения знаний из ЕЯТ. Используя эту основу и прежде всего ее
реализацию, предполагается наращивание ее мощности за счет построения новых мета отношений над
построенными отношениями, являющимися отдельными частями знаний в исследуемом тексте.
1. Палагин А.В., Крывый С.Л., Петренко Н.Г., Знание ориентированные информационные системы с обработкой естественно-языкових
объектов: основы методологии и архитектурно-структурная организация. – УСиМ. – 2009. – № 3. – С. 42 – 55.
2. Палагин А.В., Петренко Н.Г. Системно-онтологический анализ предметной области. – УСиМ. – 2009. – № 4. – С. 3 – 14.
3. Cohen D. Jeavons P. The Complexity of Constraint Languages. In “Handbook of Constraint Programming. – Edited by F. Rossi, P. van Beek
and T. Walsh. – 2006. – P. 245 – 280.
4. Апресян Ю.Д. Лингвистический процессор для сложных информационных систем. – М.: Наука, 1992. – 324 с.
5. Палагін О.В., Кривий С.Л., Петренко М.Г., Бібіков Д.С. Алгебро-логічний підхід до аналізу та обробки текстової інформації. //
Проблеми программування. – 2010. – № 2–3. – С. 318 – 329.
6. Палагин О.В., Крывый С.Л., Бибиков Д.С. Обработка предложений естественного языка с использованием словарей и частоты
появления слов. – Natural and Artificial Intelligence Intern Book Series. – Inteligent Processing. – ITHEA. – Sofia. – 2010. – N 9. – P. 44 –
52.
7. Палагін О.В., Кривий С.Л., Петренко М.Г., Бібіков Д.С. Формально-логічний підхід до побудови системи аналізу знань в різних
предметних областях // Проблеми програмування. – 2010. – № 2 – 3. – С. 382 – 389.
8. Кулик Б.А. Логика естественных рассуждений. – С.-Петербург: Невский диалект, 2001. – 127 с.
9. Clarke E.M., Schlingloff B.-H. Model checking. In Handbook of Automated Reasoning. Eds. A. Robinson and A/ Voronkov. – Elsevier Science
Publishers B.V. – 2001. – P. 1360 – 1522.
17
|