Естественно-языковые системы

09.04.02 Б1.О.07- Интеллектуальные информационные системы Тема 6. Лекция 6. Естественно-языковые системы Цель лекции: Познакомить студентов с основными подходами, методами и моделями построения интеллектуальных естественно-языковых систем, закрепить знания об их особенностях и областях применения. План: 1. Общие сведения об естественно-языковых системах 2. Основные классы ЕЯ-систем. 3. Методы модели, алгоритмы и программно-технические платформы организации работы библиотек. 4. Логические исчисления: логика предикатов и дескриптивная логика, логика высказываний. Литература: [1] Евдокимова, И.С. Естественно-языковые системы: курс лекций / И.С. Евдокимова. – Улан-Удэ: ВСГТУ, 2006. – 92 с. [2] Новиков, Ф.А. Искусственный интеллект: представление знаний и методы поиска решений: учеб. пособие / Ф.А. Новиков. – СПб.: Изд-во Поли-техн. ун-та, 2010. – 240 с. [3] http://dic.academic.ru/dic.nsf/ruwiki/653956 [4] Гущин, А.Н. Основы представления знаний: учеб. пособие / А.Н. Гущин. – СПб.: Балт. гос. техн. ун-т., 2007. – 70 с. [5] http://www.mari-el.ru/mmlab/home/AI/4/#part_4 [6] Интеллектуальные информационные системы и технологии : учебное пособие / Ю.Ю. Громов, О.Г. Иванова, В.В. Алексеев и др. – Тамбов : Изд-во ФГБОУ ВПО «ТГТУ», 2013. – 244 с. – 100 экз. – ISBN 978-5-8265-1178-7. [7] Интеллектуальные системы и технологии: учебник для студ. учреждений высш. проф. образования / Б. Я. Советов, В. В. Це- хановский, В. Д. Чертовской. – М. : Издательский центр «Ака- демия», 2013. – 320 с. – (Сер. Бакалавриат). 1. Общие сведения об естественно-языковых системах. Естественно-языковая система (ЕЯ-система) – это автоматизированная информационная система, использующая в качестве языка общения с пользователем естественный язык. Это значит, что пользователь обращается к системе на естественном языке и так же на естественном языке получает ответ на свой вопрос. Естественно-языковые системы используются для поиска в текстах, распознавания речи, голосового управления и обработки данных. В данном направлении выделяются следующие категории информационных продуктов: • средства, обеспечивающие естественно-языковый интерфейс к базам данных; • средства естественно-языкового поиска в текстах и содержательного • сканирования текстов (Natural Language text retrieval and Contents Scanning Systems); • масштабируемые средства для распознавания речи (Large-Vocabulary Talkwriter); • средства голосового ввода, управления и сбора данных (Voice Input and Control Products and Data Collection Systems); • компоненты речевой обработки (Voice-Recognition Programming Tools). Программные продукты первой категории преобразуют естественно-языковые запросы пользователя в SQL-запросы к базам данных. Средства естественно-языкового поиска в текстах осуществляют по запросам пользователей поиск, фильтрацию и сканирование текстовой информации. В отличие от продуктов предыдущей группы, где поиск осуществляется в базах данных, имеющих четкую и заранее известную структуру, средства данной категории осуществляют поиск в неструктурированных текстах, оформленных в соответствии с правилами грамматики того или иного естественного языка. Средства для распознавания речи распознают голосовую информацию и преобразуют ее в последовательность символов. Они ориентированы на работу со словарями объемом от 30000 до 70000 слов. В отличие от этого, средства голосового ввода ориентированы на работу со словарем около 1000 слов и существенно ограничены в возможностях распознавания. Программные средства этого типа предназначены для ввода голосовых команд, управляющих работой некоторого продукта, например, программы сбора данных в тех приложениях, в которых у исполнителей заняты руки. В практическом плане модели и методы, развиваемые в системах обработки связных текстов, могут быть полезны при создании интеллектуальных систем автоматического индексирования и реферирования. Задача понимания связных текстов превосходит по сложности задачи, решаемые ЕЯ-системами. Наиболее сложными для понимания являются тексты, описывающие взаимоотношения и поступки активных действующих лиц. Для их понимания система должна обладать громадным объемом знаний о мире, иметь совершенные механизмы вывода. Поэтому в настоящее время системы обработки связных текстов находятся на стадии разработки экспериментальных образцов, которые используются для исследования и оценки методов решения этой крайне сложной и многогранной задачи. Машинный перевод (МП), или автоматический перевод (АП) – интенсивно развивающаяся область научных исследований, экспериментальных разработок и уже функционирующих систем (СМП), в которых к процессу перевода с одного естественного языка на другой привлекается вычислительная система. СМП открывают быстрый и систематический доступ к информации на иностранном языке, обеспечивают оперативность и единообразие в переводе больших потоков текстов, в основном научно-технических. Основные сферы использования МП: 1. В отраслевых службах информации при наличии большого массива или постоянного потока иноязычных источников. Если СМП используются для выдачи сигнальной информации, постредактирование не требуется. 2. В крупных международных организациях, имеющих дело с многоязычным политематическим массивом документов. Поскольку требования к переводу здесь высоки, МП нуждается в постредактировании. 3. В службах, осуществляющих перевод технической документации, сопровождающей экспортируемую продукцию. Структура и язык технической документации достаточно стандартны, что облегчает МП и даже делает его предпочтительным перед ручным переводом, так как гарантирует единый стиль всего массива. Поскольку перевод спецификаций должен быть полным и точным, продукция МП нуждается в постредактировании. Помимо практической потребности делового мира в СМП, существуют и чисто научные стимулы к развитию МП: стабильно работающие экспериментальные системы МП являются опытным полем для проверки различных аспектов общей теории понимания, речевого общения, преобразования информации, а также для создания новых, более эффективных моделей самого МП. 2. Основные классы ЕЯ-систем В общем виде основные функциональные компоненты ЕЯ-систем включают: ведение диалога, понимание высказываний и генерация высказываний. В зависимости от назначения прикладных систем, в состав которых входят конкретные реализации ЕЯ-систем, задачи, решаемые отдельными функциональными компонентами (как по постановке, так и по методам решения), могут в значительной степени варьироваться. Исходя из этого, а также с учетом истории развития ЕЯ-систем, различают следующие их основные классы: ◦ интеллектуальные вопрос-ответные системы; ◦ системы общения с базами данных; ◦ диалоговые системы решения задач; ◦ системы обработки связных текстов; ◦ системы машинного перевода. Каждый из классов ЕЯ-систем обладает специфическими особенностями, которые хорошо заметны при рассмотрении характера задач, решаемых основными функциональными компонентами этих систем (табл. 1). Приведенная выше классификация ЕЯ-систем охватывает лишь функционально полные системы, т. е. такие, в которых представлены все основные функциональные компоненты. Таблица 1 – Сравнительная характеристика основных классов ЕЯ-систем Классы ЕЯ- систем Компоненты ЕЯ-систем Ведение диалога Понимание высказываний Генерация высказываний Системы общения с БД Жесткий или альтернатив- ный диалог. Инициатива в основном принадлежит пользователю. Перехваты инициативы системой для предупреждения или устра- нения некоторых видов ло- кальных неудач ЕЯ-предложения, которые могут со- держать неправильности и ссылки на предложения из предыдущих запро- сов. Интерпретация на проблемную область или область языка общения Прямые ответы, получаемые с помощью средств генерации от- четов СУБД. Стандартные сооб- щения для предупреждения или устранения неудач. Перефразиро- вание запросов на ЕЯ Вопрос- ответные системы Жесткий диалог с инициа- тивой у пользователя Отдельные правильные ЕЯ- предложения с лексическими, син- таксическими и семантическими ог- раничениями. Интерпретация осуще- ствляется на ПО Прямые ответы в виде ЕЯ- предложений с лексическими, синтаксическими и семантиче- скими ограничениями. Стандарт- ные сообщения о неудачах Системы обработки связных текстов Жесткий диалог с инициа- тивой у пользователя Связный текст в виде последователь- ности ЕЯ-предложений, описываю- щих события, сложные объекты, яв- ления и т.п. Связный текст в виде последова- тельности ЕЯ-предложений Диалоговые сис- темы решения задач Гибкий диалог. Инициати- ва, в основном, принадле- жит системе. Разнообраз- ные способы перехвата инициативы ЕЯ-предложения, которые могут со- держать неправильности и ссылки на предыдущие высказывания. Интер- претация на проблемную область, область языка общения, область сис- темы, область пользователя и область дискурса Прямые и косвенные ответы, в виде, ЕЯ-предложений, генери- руемых с учетом целей и намере- ний участников общения Однако помимо функционально полных систем ведется интенсивная разработка систем, которые можно назвать фрагментарными. Цель их создания – исследование или реализация новых методов решения достаточно узких задач (например, таких, как анализ, интерпретация, определение целей пользователя и т. п.). Благодаря модульности структуры ЕЯ-систем и, как правило, универсальному (т. е. не зависящему от специфики прикладных областей) характеру языка внутреннего представления, фрагментарные системы могут успешно использоваться в качестве отдельных функциональных блоков, встраиваемых (хотя бы на логическом уровне) в различные функционально полные ЕЯ-системы. Рассмотрим основные отличительные характеристики каждого класса ЕЯ-систем. Интеллектуальные вопрос-ответные (ИВО) системы. При разработке ИВО систем основные внимание уделяется языковому аспекту, т.е. максимальному приближению языка общения к литературному естественному языку. С помощью первых вопрос-ответных систем была показана принципиальная возможность получения ответов на ЕЯ-вопросы, относящиеся к ограниченным проблемным областям. Первые эксперименты с ИВО системами показали, что, несмотря на возможность понимания запросов на ЕЯ, данные системы налагают достаточно жесткие (и в общем случае трудновыполнимые) ограничения на процесс общения. Эти ограничения стимулировали дальнейшие исследования, направленные, в первую очередь, на повышение гибкости процесса общения. Системы общения с базами данных (ОБД) В последнее время возрос интерес к ЕЯ-системам данного класса, что связано с усиливающейся тенденцией хранения информации в структурированных источниках данных. Концепция базы данных (БД) лежит в основе подавляющего большинства современных систем обработки данных. Для обеспечения взаимодействия с конечными пользователями системы управления базами данных (СУБД) предоставляют специальные формализованные языки. Однако, как правило, эти языки ориентированы на пользователей, обладающих специальными знаниями. В частности, они должны знать основные приемы программирования, синтаксис языка запросов, логическую структуру БД, термины, используемые в БД для обозначения сущностей предметной области, и т.п. ЕЯ-системы рассматриваемого класса предназначены для использования в качестве посредника (естественно-языкового интерфейса) между неподготовленными конечными пользователями (т.е. специалистами в прикладных проблемных областях, не обладающими указанными выше знаниями) и БД. Другими словами, они должны позволять получать информацию, хранящуюся в БД, по запросам, сформулированным на ЕЯ. На рисунке 1 показана упрощенная схема систем общения с БД. В системах общения с БД общение ведется в форме связного диалога, т.е. ответы на вопросы пользователя выдаются с учетом его предыдущих вопросов и/или предыдущих ответов системы. Инициатива в диалоге в основном принадлежит пользователю. Перехват инициативы допускается лишь для уточнения незнакомых системе слов и исправления орфографических ошибок. Язык общения является подмножеством естественного языка, семантически ограниченным предметной областью, отображаемой в БД. В высказываниях пользователя допускаются многие общепринятые синтаксические конструкции. Кроме того, допускаются определенные неправильности: орфографические ошибки, пропуск слов, ошибки в пунктуации, неправильное употребление строчных и прописных букв и ряд типичных диалоговых конструкций: эллипсис и анафорические ссылки. Ответы ЕЯ-системы строятся таким образом, чтобы обеспечить, насколько это возможно, «дружественность» общения. Рисунок 1 – Структурная схема систем общения с БД С точки зрения возможностей практического использования, системы общения с БД значительно опережают остальные классы ЕЯ-систем. Сравнительный анализ типов пользовательских интерфейсов (основанных на формах, с формальным языком запросов, графические) показывает, что в целях построения ЕЯ- интерфейсов превалирует желание максимально приблизить интерфейс к потребностям неподготовленного пользователя. Это несколько поднимает планку требований к дружественности и надежности ЕЯ-интерфейсов, поскольку пользователь, впервые столкнувшись с системой, понимающей естественный язык, слабо представляет, насколько интеллектуальна система. При этом ожидания к степени понимания ЕЯ может отличаться от реальных способностей системы в обе стороны - т.е. пользователь может спрашивать систему о том, чего она «не знает», а может «по привычке» использовать простейшие шаблонные формулировки запросов. Диалоговые системы решения задач Основное отличие ЕЯ-систем данного класса от ЕЯ-систем общения с БД состоит в той роли, которую играет система в процессе решения задач пользователя. Системы общения с БД лишь облегчают получение из БД информации. Они, как правило, не имеют знаний о задаче, для решения которой пользователю нужна эта информация. При общении с диалоговыми системами решения задач пользователь и система меняются ролями. Цель системы состоит в получении решения задачи на основе использования как собственных знаний и механизмов вывода, так и данных, получаемых из ответов пользователя и из прикладных программ, которые могут вызываться диалоговой системой для непосредственного решения каких-то подзадач. Основной областью практического использования диалоговых систем решения задач яв- ляется обеспечение ЕЯ-доступа к различным прикладным системам, предназначенным для ре- шения задач реальных объемов и сложности. При этом диалоговая система выступает в качест- ве интерфейса между прикладной системой и конечным пользователем, не знающим входного языка прикладной системы и имеющим лишь самое общее представление об алгоритме реше- ния задачи. В этом случае процесс решения задачи распадается на следующие этапы: • информирование пользователя о возможностях прикладной системы; • получение от пользователя исходных данных (описаний задач, подзадач и их параметров), их уточнение и формирование заданий на входном языке прикладной системы; • собственно, решение подзадач прикладной системой; • предоставление пользователю результатов решения задачи. Большинство из существующих в настоящее время ЕЯ-систем данного типа предназначены для общения пользователя (клиента) с экспертными системами (ЭС) в процессе кооперативного решения задачи. Вместе с тем разрабатываются и ЕЯ-системы, не прибегающие в процессе решения задач к помощи пользователей (эти системы могут найти применение в простых проблемных областях). В настоящее время разработано достаточно много систем данного класса, но все они ориентированы на решение определенного круга вопросов в конкретной предметной области. Например: • система Advisor выполняет функции консультанта, способного отвечать на вопросы студентов о различных дисциплинах и давать советы относительно возможности или необходимости изучения той или иной дисциплины и др. На рисунке 2 показана примерная схема диалоговых систем решения задач (система Advisor), в которой отражены компоненты данного класса ЕЯ-систем и их взаимосвязь. Рисунок 2 – Структурная схема системы Advisor Системы обработки связных текстов Системы данного класса моделируют процесс понимания законченных описаний определенных фрагментов действительности (историй, рассказов, эпизодов и т. п.), выраженных в виде текста на естественном языке, т. е. последовательности связанных друг с другом предложений. Понимание текста трактуется как извлечение из него всей существенной с точки зрения системы информации и присоединение ее к собственной базе знаний. После этого система может отвечать на вопросы относительно фактов, событий, явлений и прочих сущностей, которые явно или косвенно описаны во введенных текстах. Очевидно, что в практическом плане модели и методы, развиваемые в системах обработки связных текстов, могут быть полезны при создании интеллектуальных систем автоматического индексирования и реферирования. Для примера рассмотрим системы Researcher и Tailor, которые образуют единый комплекс (рис. 3), позволяющий пользователю получать сведения из рефератов-патентов, описывающих сложные физические объекты. Система Researcher получает рефераты патентов, стрит на их основе базу знаний и делает обобщения их различных патентов, которые могут служить для изучения содержащихся в рефератах сведений, относящихся к различным объектам. Вопрос-ответные функции выполняет система Tailor. Рисунок 3 – Схема взаимодействия систем Researcher и Tailor Системы машинного перевода Машинный перевод (МП), или автоматический перевод (АП) – интенсивно развивающаяся область научных исследований, экспериментальных разработок и уже функционирующих систем (СМП), в которых к процессу перевода с одного естественного языка на другой привлекается вычислительная система. СМП открывают быстрый и систематический доступ к информации на иностранном языке, обеспечивают оперативность и единообразие в переводе больших потоков текстов, в основном научно-технических. Работающие в промышленном масштабе СМП опираются на большие терминологические банки данных и, как правило, требуют привлечения человека в качестве пред-, интер- или постредактора. Современные СМП, и в особенности те, которые опираются при переводе на базы знаний в определенной предметной области, относят к классу систем искусственного интеллекта. Основные сферы использования МП: 1) В отраслевых службах информации при наличии большого массива или постоянного потока иноязычных источников. Если СМП используются для выдачи сигнальной информации, постредактирование не требуется. 2) В крупных международных организациях, имеющих дело с многоязычным политематическим массивом документов. Поскольку требования к переводу здесь высоки, МП нуждается в постредактировании. 3) В службах, осуществляющих перевод технической документации, сопровождающей экспортируемую продукцию. Структура и язык технической документации достаточно стандартны, что облегчает МП и даже делает его предпочтительным перед ручным переводом, так как гарантирует единый стиль всего массива. Поскольку перевод спецификаций должен быть полным и точным, продукция МП нуждается в постредактировании. Помимо практической потребности делового мира в СМП, существуют и чисто научные стимулы к развитию МП: стабильно работающие экспериментальные системы МП являются опытным полем для проверки различных аспектов общей теории понимания, речевого общения, преобразования информации, а также для создания новых, более эффективных моделей самого МП. В классических СМП, осуществляющих непрямой перевод по отдельным предложениям (пофразный перевод), каждое предложение проходит последовательность преобразований, состоящую из трех этапов: АНАЛИЗ → ТРАНСФЕР (межъязыковые операции) → СИНТЕЗ. В свою очередь, каждый из этих этапов представляет собой достаточно сложную систему промежуточных преобразований. Цель этапа анализа – построить структурное описание (промежуточное представление, внутреннее представление) входного предложения. Задача этапа трансфера (перевода) - преобразовать структуру входного предложения во внутреннюю структуру выходного предложения. К этому этапу относятся и замены лексем входного языка их переводными эквивалентами (лексические межъязыковые преобразования). Цель этапа синтеза – на основе полученной в результате анализа структуры построить правильное предложение выходного языка. Одно из необходимых требований к современным СМП – высокая модульность. С лингвистически содержательной точки зрения это означает, что анализ и следующие за ним процессы строятся с учетом теории лингвистических уровней. В практике создания СМП различают четыре уровня анализа: 1) Морфологический анализ, анализ оборотов, неопознанных элементов текста и др.; Построение синтаксического представления предложения. В его пределах может выделяться ряд подуровне, обеспечивающих анализ разных синтаксических единиц; 2) Построение аргументно-предикатной структуры высказываний или другого вида семантического предложения и текста; 3) Анализ в терминах концептуальных структур, отражающих семантику предметной области. Этот уровень анализа используется в СМП, ориентированных на очень ограниченные ПО. 3. Методы модели, алгоритмы и программно-технические платформы организации работы библиотек. Стадия морфологического анализа (МА) является наиболее проработанным лингвистическим этапом процесса обработки естественного текста. Существуют три основных метода реализации МА: декларативный, процедурный и комбинированный. При декларативном методе в словаре хранятся все возможные словоформы каждого слова с приписанной им морфологической информацией (МИ). В этом случае задача МА состоит просто в поиске словоформы в словаре и переписывании из словаря МИ, поэтому можно считать, что в этом методе отсутствует как таковой морфологический анализ, а хранится только его результат. Так как количество различных словоформ у каждого слова довольно велико, декларативный метод требует больших затрат памяти ВС, что порождает ряд технических проблем. Достоинствами метода является высокая скорость анализа, а также универсальность по отношению к множеству всех возможных словоформ русского языка. Процедурный МА выполняет следующие функции: выделяет в текущей словоформе основу, идентифицирует ее и приписывает данной словоформе соответствующий комплекс МИ. Процедурный метод предполагает предварительную систематизацию морфологических знаний о ЕЯ и разработку алгоритмов присвоения МИ отдельной словоформе. Недостатком такого подхода является высокая трудоемкость составления словарей совместимости. При этом наличие в русском языке большого числа слов-исключений не позволяет сколько-нибудь автоматизировать этот процесс. Для проведения анализа словоформы необходимо наличие словарей «приставка-корень», «корень – суффикс – флективный класс», «флективный класс – окончание – морфологическая информация». Работающая система, в которой реализован процедурный морфологический анализ, занимает значительно меньший объем памяти, но при этом увеличивается время поиска МИ за счет разбиения словоформы на составляющие и применения процедур совместимости. В системах реальной степени сложности чаще используется комбинированный вариант морфологического анализа. При этом используется как словарь словоформ, так и словарь основ. На первом этапе проводится поиск по словарю словоформ, как при декларативном методе, и в случае успешного поиска анализ на этом завершается. В противном случае задействуется словарь основ и процедурный метод анализа. В комбинированном методе словоформа разделяется на основу и аффикс (окончание и, возможно, суффикс), и словарь содержит только основы слов вместе со ссылками на соответствующие строки в таблице возможных аффиксов, причем основа должна оставаться неизменной во всех возможных словоформах данного слова. За счет использования словаря готовых словоформ обеспечивается достаточно высокая скорость определения МИ, а за счет справочников «основа+аффикс» – качество морфологического анализа. В отличие от морфологического анализа текста синтаксический анализ (СА) – развивающаяся область прикладной лингвистики. Цель синтаксического анализа – автоматическое построение функционального дерева фразы, т.е. нахождение взаимозависимостей между разноуровневыми элементами предложения. Существует достаточно много различных способов синтаксического анализа естественно-языковых текстов, которые можно проанализировать с различных точек зрения. Общая структура классификации способов синтаксического анализа приведена в таблице 2. Таблица 2 – Классификация способов синтаксического анализа № п/п Основание классификации Группа методов 1 Тип цели Одноцелевые Многоцелевые 2 Синтаксическая структура Построение графа зависимостей Построение дерева непосредственных составляющих 3 Формальные теории описания естественного языка Формально-грамматические методы Вероятностно-статистические методы С точки зрения цели синтаксического анализа можно выделить два основных подхода: одноцелевой и многоцелевой. При первом подходе для фразы требуется построить одно синтаксическое представление, этот подход характерен для первых алгоритмов синтаксического анализа, когда считалось, что синтаксических средств достаточно для того, чтобы обеспечить правильный анализ фразы, хотя бы для большинства фраз. При втором подходе для фразы требуется получить все те синтаксические представления, которые удовлетворяют определенным соглашениям (все «правильно построенные» представления). Существует два способа применения синтаксических правил: снизу-вверх и сверху-вниз. В первом случае применяются правила, заменяющие структуру, описанную в правой части, символом, представленным в левой части. Во втором случае доказывается выводимость данного предложения из начального символа S. Часто оказывается возможным применить правила несколькими способами при анализе снизу-вверх. В синтаксическом анализе существуют две стандартные стратегии применения правил при возможности альтернативного выбора: поиск "в ширину" и поиск "в глубину". В первом случае запоминаются все возможные варианты, и каждый из них разворачивается параллельно (или по очереди в случае последовательного анализа), при неудаче какого-либо варианта разбора соответствующий вариант удаляется из набора возможностей. Во втором случае, при анализе "в глубину", выбирается одна из альтернатив, а при неудаче построения разбора происходит возврат на точку последней альтернативы и выбор другого варианта. Использование анализа с проходом сверху-вниз не позволяет создавать не грамматичные варианты. С другой стороны, анализ снизу-вверх не позволяет генерировать гипотезы разбора, невозможные для данного предложения. Комбинацию достоинств этих вариантов представляет анализ с помощью таблиц, содержимое которых является результатом частичного разбора. В случае, если разбор по какому-то пути зашел в тупик, происходит возврат на точку выбора последнего правила и делается попытка использовать другое правило. Однако заполнение таблицы, порожденное предыдущим способом разбора, сохраняется в таблице и может быть использовано в разборе по текущей ветке. Эта информация не запрещает проход анализа по тем веткам, которые уже были опробованы, но неудачно. Для этой цели применяется запоминание также и гипотез, выдвигаемых при разборе, и результатов их проверки. Такой подход называется анализом с помощью схем (chart-parsing). Впервые его предложил Мартин Кэй в системе Powerful Parser. Грамматики конечных автоматов достаточно эффективны в реализации, но обладают слишком ограниченными возможностями для анализа, по этой причине одним из широко используемых механизмов анализа является формализм расширенных сетей переходов (augmented transition networks, ATN). Формализм ATN расширяет грамматику конечных автоматов, вводя аппарат рекурсивного вызова новой подсети переходов (операция PUSH) и набор регистров, в которых хранятся текущие результаты разбора фразы, а также средства работы с этими регистрами. Значения регистров могут выступать условиями для переходов по веткам, что обеспечивает частичную зависимость от контекста и выход за пределы КС- грамматик. Благодаря регистрам и операциям над значениями, которые там хранятся, ATN-формализм эквивалентен процедурному языку программирования, в котором можно описать анализ языка произвольной сложности. Логико-алгоритмические подходы синтаксического анализа. В настоящее время можно говорить о существовании трех основных логико-алгоритмических подходов СА: недетерминированный «сначала в ширину», недетерминированный «сначала в глубину» и детерминированный. Недетерминированный «сначала в ширину». Недетерминированный подход «сначала в ширину» характеризуется тем, что процедура синтаксического анализа на первом этапе порождает заведомо избыточный набор синтаксических связей, из числа которых на втором этапе с помощью серии фильтров отбираются такие, которые в совокупности давали бы правильную синтаксическую структуру входного предложения (или несколько правильных синтаксических структур). Этот подход был впервые теоретически обоснован и экспериментально проверен О.С.Кулагиной. В настоящее время эта стратегия имеет варианты, которые различаются: • степенью ослабления контекстуальных условий на этапе порождения связей; • статусом синтаксических структур, подвергающихся фильтрации (синтаксическая структура входного предложения, синтаксическая структура фрагмента входного предложения) и другими чертами. Примерами систем, использующих этот подход, могут служить АРТ, ЭТАП-2, алгоритм Л.Г. Митюшина,1 и 2 версии ЛГУ, алгоритм Е.И. Анно и т.д. Недетерминированный «сначала в глубину». Во многих системах, ориентированных на промышленную эксплуатацию, используется другая стратегия СА. Она встречается под разными названиями: стратегия, опирающаяся на механизм возвратов backtracking, стратегия depth-first («сначала в глубину»); в некоторых работах эта стратегия объединяется с предыдущей под одним названием «недетерминированный анализ». Этот подход принят, например, в системе АДАМАНТ. Отличие его от концепции псевдопараллелизма состоит в том, что алгоритм на каждом шаге выбирает одну из возможных интерпретаций, но при этом сохраняется принципиальная возможность порождения альтернативных интерпретаций в случае той или иной неудачи с первой (например, если полученная синтаксическая структура входного предложения или его фрагмент не удовлетворяет требованиям проективности, связности, не проходит семантический фильтр и т.п.). Если первый вариант разбора признается неудовлетворительным, нет необходимости начинать анализ сначала. Процедуре анализа достаточно вернуться в ближайшее из состояний, при котором возможен был альтернативный путь, и попытаться довести до конца этот вариант. Если же и он окажется неприемлемым, процедура снова использует механизм возвратов и перейдет к следующему варианту и так далее, пока не будет порожден первый приемлемый вариант разбора входного предложения. Поиск других вариантов после этого прекращается. Детерминированный подход. Третья стратегия – стратегия детерминированного анализа – базируется на следующем принципе: ни одна синтаксическая связь, установленная в процессе анализа предложения, не может быть отвергнута, иными словами, если связь порождена, она должна присутствовать в синтаксической структуре, являющейся результатом работы синтаксического анализатора. Эта стратегия используется в системах ЯИП, САГА и другие. Синтаксический анализатор, разработанный в группе Г.Г. Белоногова, в целом также может быть отнесен к этому типу, хотя локально он допускает пересмотр уже установленных связей. В результате синтаксического анализа должны быть однозначно определены все синтаксические единицы естественно-языкового предложения. Синтаксическими единицами будем называть конструкции, в которых их элементы (компоненты) объединены синтаксическими связями и отношениями. Синтаксическая связь является выражением взаимосвязи элементов в синтаксической единице, то есть служит для выражения синтаксических отношений между словами, создает синтаксическую структуру предложения и словосочетания, а также условия для реализации лексического значения слова. Исходными данными для проведения синтаксического анализа являются результаты морфологического анализа, представленные в виде множества пар , где xi – ЕЯ-лексема, Vi – вектор морфологической информации xi лексемы. Синтаксический анализ проходит три этапа. На первом этапе осуществляется нормализация лексем естественно-языкового предложения для выделения синтаксических групп, к которым относятся группы ФИО, ДАТА, ПС (существительное с предлогом) и другие, описание и правила выделения которых более подробно рассмотрены в следующем разделе данной главы. На этом же этапе осуществляется удаление несущественных лексем из исходного множества, таких как служебные части речи (предлоги, союзы, частицы и т.п.). В результате будут сформированы два множества: новое исходное множество лексем Х и L – множество синтаксических групп в виде векторов связанных лексем. Синтаксическая связь, относящаяся к типу подчинение, передает сочетание двух слов, в котором одно выступает как главное, а другое – как зависимое. Поэтому задачей второго этапа является выявление синтаксической связи между двумя лексемами множества Х и множества векторов L, разбиение лексем на множество главных слов и множество зависимых слов, причем , и формирование множества сочетаемых пар лексем . Для нахождения корневой вершины необходимо: 1) объединить множества и : = ; 2) найти разности множеств и :, где – одноэлементное множество корневых вершин. Таким образом, формируется один или несколько графов зависимостей , где Х – множество вершин графа G, которое составляет множество лексем, а D – множество дуг. Web-технологии. К настоящему времени существующие естественно-языковые системы используют в основном два последних подхода. Второй подход реализован в достаточно распространенной системе ЗАПСИБ, разработанной в середине 80-х годов. Система позволяет вести общение на ограниченном подмножестве естественного языка. Развитием проекта является система InterBase, вышедшая в 1990 году. Система основана на семантически-ориентированном анализе и продолжает ряд естественно-языковых технологий лаборатории искусственного интеллекта ВЦ АН Новосибирска, затем фирмы «Интеллектуальные технологии», а теперь РосНИИ искусственного интеллекта. В 2001 году эта система была переработана и получила название InBASE в виде коммерческого продукта. В настоящее время система представляет собой библиотеку COM-компонентов и среду настройки естественно-языковых интерфейсов. Существенным отличием от старой версии является появление промежуточного уровня запросов – Q-языка, являющегося подмножеством языка объектных запросов OQL и уровня описания предметной области в виде диаграммы классов UML. В полном соответствии с особенностями семантически-ориентированной парадигмы InBASE позволяет строить естественно-языковые интерфейсы ко многим языкам – для русского и для английского используется один и тот же Л-процессор. Интересной особенностью InBASE является возможность моделирования предметной области на естественном языке: с помощью класса словарных статей «Толкование» смысл слова можно описать простой фразой. Это позволяет настраивать естественно-языковые интерфейсы людям, не обладающим навыками инженеров знаний. Основным недостатком данной системы является то, что кортежи базы данных продублированы в словарях – отдельных файлах. В базах данных больших объемов этот недостаток может стать проблемой. Ярким представителем третьего подхода является система English Query. Система English Query от Microsoft основана на синтаксически-ориентированных шаблонах, связываемых с моделью предметной области, и через нее - со схемой базы данных. При настройке необходимо задать модель базы данных и предметной области, а затем для каждого отношения в базе данных (а отношением считается и связь между классом и его атрибутом, например, между товаром и его ценой) задать синтаксический шаблон английской грамматики, выбираемый из списка. Этот продукт позволяет строить естественно-языковые интерфейсы только для английского языка и работает только с Microsoft SQL Server, в этом смысле это лишь утилита, поставляемая с SQL-сервером, именно так она и позиционируется. В целом же этот продукт очень интересен. Например, в нем есть встроенная обучаемая база знаний, с которой можно пообщаться на английском языке, – она запоминает факты, правила и отвечает на вопросы по этой базе. К сожалению, эта замечательная способность не совмещена с пониманием запросов к базе данных. База знаний, необходимая для выполнения анализа запроса, содержит метаописание базы данных и знания проблемной среды. Модуль метаописания БД состоит из описания концептуальной схемы базы данных на естественном языке: сущностей, атрибутов и связей между сущностями. Модуль словарей содержит знания для проведения морфологического, синтаксического анализов и трансляции естественно-языковых запросов к базе данных. 4. Логические исчисления: логика предикатов и дескриптивная логика, логика высказываний Механизмы для представления фактографических и алгоритмических знаний в компьютерах хорошо изучены и устоялись. Для фактографических знаний – это системы управления базами данных (СУБД), в современных условиях чаще всего реляционные. Для алгоритмических знаний – это библиотеки процедур, в современных условиях чаще всего объектно- ориентированные, то есть библиотеки типов и классов. Таким образом, классификация по форме представления знаний рассматривает, прежде всего, представление концептуальных знаний. Предлагается множество различных механизмов представления концептуальных знаний (рис. 4). Чаще всего сейчас применяются следующие три: Правила, или продукции. Системы искусственного интеллекта, основанные на правилах, в настоящее время встречаются чаще всего. С математической точки зрения такие системы используют модели вычислимости, близкие к нормальным алгорифмам Маркова. Системы продукций детально рассматриваются во второй и третьей главах данной книги. Формулы логических исчислений. Системы искусственного интеллекта, основанные на логических формулах, в настоящее время занимают второе место по распространенности. С математической точки зрения такие системы используют исчисления, близкие к исчислению предикатов первого порядка, а в некоторых случаях близкие к исчислению Чёрча. Представление знаний с помощью формул логических исчислений рассматривается в четвертой главе. Фреймы и семантические сети. Сейчас этот механизм используется сравнительно редко, хотя в недавнем прошлом это было не так. С математической точки зрения такие системы используют аппарат теории графов. Все три распространенных механизма сопоставимы с точки зрения выразительной силы и других общематематических свойств. Предпочтение тому или иному механизму представления знаний часто отдается исходя из соображений привычности, удобства программирования, знакомства с теорией разработчиков прикладной системы. Особенно важным является то, насколько компактным оказывается представление знаний о конкретной задаче. Рисунок 4 – Механизмы представления различных видов знаний Можно выделить ряд общих для всех систем представления знаний (СПЗ) черт. А именно: все СПЗ имеют дело с двумя мирами – представляемым и представляющим. Вместе они образуют систему для представления. Существует также ряд общих для всех СПЗ проблем. К ним можно отнести, в частности, проблемы: приобретения новых знаний и их взаимодействие с уже существующими, организации ассоциативных связей, неоднозначности и выбора семантических примитивов, явности знаний и доступности, выбора соотношения декларативной и процедуральной составляющих представления, что влияет на экономичность системы, полноту, легкость кодировки и понимания. Логические модели представлений знаний, их краткая характеристика Описания предметных областей, выполненные в логических языках, называются (формальными) логическими моделями. Достоинства логических моделей представления знаний: 1) В качестве «фундамента» здесь используется классический аппарат математической логики, методы которой достаточно хорошо изучены и формально обоснованы. 2) Существуют достаточно эффективные процедуры вывода, в том числе реализованные в языке логического программирования Пролог, использующие механизмы автоматического доказательства теорем для поиска и логически осмысленного вывода информации. 3) В базах знаний можно хранить лишь множество аксиом, а все остальные знания полу- чать из них по правилам вывода, а также Данные, факты и другие сведения о людях, предметах, событиях и процессах. Для представления математического знания в математической логике пользуются логическими формализмами – исчислением высказываний и исчислением предикатов. Эти формализмы имеют ясную формальную семантику и для них разработаны механизмы вывода. Поэтому исчисление предикатов было первым логическим языком, который применяли для формального описания предметных областей, связанных с решением прикладных задач. Логические модели представления знаний реализуются средствами логики предикатов. Предикатом называется функция, принимающая два значения (истина или ложь) и предназначенная для выражения свойств объектов или связей между ними. Выражение, в котором утверждается или отрицается наличие каких-либо свойств у объекта, называется высказыванием. Константы служат для именования объектов предметной области. Логические предложения или высказывания образуют атомарные формулы. Интерпретация предиката– это множество всех допустимых связываний переменных с константами. Связывание представляет собой подстановку констант вместо переменных. Предикат считается общезначимым, если он истинен во всех возможных интерпретациях. Говорят, что высказывание логически следует из заданных посылок, если оно истинно всегда, когда истинны посылки. Логический вывод осуществляется с помощью силлогизма (если из A следует B, а из B следует C, то из A следует C). В основе логических моделей представления знаний лежит понятие формальной системы, задаваемой четверкой: где В – множество базовых символов (алфавит) формальной системы S; F – синтаксические правила построения формул теории из символов алфавита; А – выделенное множество формул, называемых аксиомами теории S, которые полагаются априори истинными; R – конечное множество отношений между формулами, называемых правилами вывода. Формальная система называется разрешимой, если существует эффективная процедура (алгоритм), позволяющая для любой заданной формулы определить, выводима ли она в данной формальной системе. Наиболее распространенной формальной системой, используемой для представления знаний, является исчисление предикатов первого порядка. Алфавит языка логики предикатов включает следующие группы символов: ◦ предметные константы: a, Ь, с, ...; ◦ предметные переменные: х, у, z,…; ◦ функциональные символы: f, g. h, ...; ◦ предикатные символы: Р, Q, R, …; ◦ логические связки: “|, &, , , ; ◦ кванторы: , . Множество D объектов, о которых ведется рассуждение, называется областью интерпретации языка логики предикатов или фактуальными знаниями. Предметные константы соответствуют конкретным элементам множества D. а предметные переменные могут принимать значения в множестве D. Функциональные символы соответствуют функциям, заданным операционными знаниями на области интерпретации. Функциональный символ вместе со списком аргументов образует функциональную форму. Термом является всякая предметная константа, предметная переменная либо функциональная форма. Аргументами функциональной формы могут быть любые термы, например . Логическая модель, построенная на основе логики предикатов первого порядка, предполагает в общем случае пропозициональный взгляд на знание, когда в качестве элемента знания рассматривается некоторое утверждение и, соответственно, элементарное знание представляется атомарной формулой языка логики предикатов. Понятие формулы в логике предикатов определяется следующим образом: ◦ всякий атом есть формула; ◦ если А и В – формулы, то , А&В., и также формулы; ◦ других формул нет. Для записи некоторого утверждения на языке логики предикатов необходимо: ◦ зафиксировать множество объектов, о которых идет речь, как область интерпретации; ◦ выделить функциональные связи и отношения (свойства), упоминаемые в данном утверждении, и сопоставить им функциональные и предикатные символы соответствующей местности; ◦ определить логическую структуру утверждения, включая области действия кванторов, и записать утверждение в виде формулы. Процесс вывода строится как последовательность шагов получения целевой формулы с помощью правил вывода, к которым относятся следующие классические правила: Modus Ponens, цепное, подстановки. резолюций: 1. Правило Modus Ponens: Если А – выводима и А влечет В, то В – выводимая формула. 2. Цепное правило: Если формулы и выводимы, то выводима и формула. 3. Правило подстановки: если формула A(x) выводима, то выводима и формула A(B), в которой все вхождения литерала x заменены на формулу B. 4. Правило резолюций: если выводимы формулы двух дизьюнктов, имеющих контрарную пару и , то выводима формула дизьюнкта , полученного из данных двух удалением контрарной пары. 5. Можно построить процесс вывода с использованием только правил подстановки и резолюции, так как правило Modus Ponens и цепное правило можно рассматривать как частные случаи правила резолюций, интерпретируя формулу как дизъюнкт Эффективной языковой реализацией логического подхода к представлению и обработке знаний является язык Пролог. Программы на языке Пролог носят декларативный характер – в них отсутствуют такие управляющие конструкции, как условные операторы, операторы цикла и операторы передачи управления. Программа на этом языке является, по существу, спецификацией решаемой задачи в терминах объектов предметной области, фактов и правил, описывающих отношения на множестве данных объектов. Встроенный механизм логического вывода, базирующийся на методе резолюций логики предикатов, на основе данной спецификации и инициирующего запроса-цели строит алгоритм процесса дедукции для доказательства данного целевого утверждения. Преимущество логических моделей состоит в единственности теоретического обоснования и возможности реализации системы формально точных определений и выводов. Недостатком таких моделей является то, что классическая логика не позволяет решать ряд задач, что может требовать включения временных, модальных и т.п. категорий, для которых отсутствуют автоматические системы вывода, а также сложность создания подсистемы объяснений. Формальные модели представления знаний Система ИИ в определенном смысле моделирует интеллектуальную деятельность человека и, в частности, - логику его рассуждений. В грубо упрощенной форме наши логические построения при этом сводятся к следующей схеме: из одной или нескольких посылок (которые считаются истинными) следует сделать "логически верное" заключение (вывод, следствие). Очевидно, для этого необходимо, чтобы и посылки, и заключение были представлены на понятном языке, адекватно отражающем предметную область, в которой проводится вывод. В обычной жизни это наш естественный язык общения, в математике, например, это язык определенных формул и т.п. Наличие же языка предполагает, во - первых, наличие алфавита (словаря), отображающего в символьной форме весь набор базовых понятий (элементов), с которыми придется иметь дело и, во - вторых, набор синтаксических правил, на основе которых, пользуясь алфавитом, можно построить определенные выражения. Логические выражения, построенные в данном языке, могут быть истинными или ложными. Некоторые из этих выражений, являющиеся всегда истинными. Объявляются аксиомами (или постулатами). Они составляют ту базовую систему посылок, исходя из которой и пользуясь определенными правилами вывода, можно получить заключения в виде новых выражений, также являющихся истинными. Если перечисленные условия выполняются, то говорят, что система удовлетворяет требованиям формальной теории. Ее так и называют формальной системой (ФС). Система, построенная на основе формальной теории, называется также аксиоматической системой. Формальная теория должна, таким образом, удовлетворять следующему определению: всякая формальная теория F = (A, V, W, R), определяющая некоторую аксиоматическую систему, характеризуется: а) наличием алфавита (словаря), A, б) множеством синтаксических правил, V, в) множеством аксиом, лежащих в основе теории, W, г) множеством правил вывода, R. Алфавит. Множество A есть множество базовых элементов различной природы, например слов из некоторого ограниченного словаря, деталей детского конструктора, входящих в состав некоторого набора и т.п. Важно, что для множества A существует некоторый способ определения принадлежности или непринадлежности произвольного элемента к этому множеству. Процедура такой проверки может быть любой, но за конечное число шагов она должна давать положительный или отрицательный ответ на вопрос, является ли x элементом множества T. Обозначим эту процедуру П(T). Синтаксические правила. Множество V есть множество синтаксических правил. С их помощью из элементов A образуют синтаксически правильные совокупности. Например, из слов ограниченного словаря строятся синтаксически правильные фразы, из деталей детского конструктора с помощью гаек и болтов собираются новые конструкции. Декларируется существование процедуры П(V), с помощью которой за конечное число шагов можно получить ответ на вопрос, является ли совокупность X синтаксически правильной. Аксиомы. В множестве синтаксически правильных совокупностей выделяется некоторое подмножество W. Элементы W называются аксиомами. Как и для других составляющих формальной системы, должна существовать процедура П(W), с помощью которой для любой синтаксически правильной совокупности можно получить ответ на вопрос о принадлежности ее к множеству W. Правила вывода. Множество R есть множество правил вывода. Применяя их к элементам W, можно получать новые синтаксически правильные совокупности, к которым снова можно применять правила из R. Так формируется множество выводимых в данной формальной системе совокупностей. Если имеется процедура П(R), с помощью которой можно определить для любой синтаксически правильной совокупности, является ли она выводимой, то соответствующая формальная система называется разрешимой. Это показывает, что именно правило вывода является наиболее сложной составляющей формальной системы. Исчисление высказываний (ИВ) и исчисление предикатов (ИП) являются классическими примерами аксиоматических систем. Эти ФС хорошо исследованы и имеют прекрасно разработанные модели логического вывода - главной метапроцедуры в интеллектуальных системах. Поэтому все, что может и гарантирует каждая из этих систем, гарантируется и для прикладных ФС как моделей конкретных предметных областей. В частности, это гарантии непротиворечивости вывода, алгоритмической разрешимости (для исчисления высказываний) и полуразрешимости (для исчислений предикатов первого порядка). Для знаний, входящих в базу знаний, можно считать, что множество W образуют все ин- формационные единицы, которые введены в базу знаний извне, а с помощью правил вывода из них выводятся новые производные знания. Другими словами формальная система представляет собой генератор порождения новых знаний, образующих множество выводимых в данной системе знаний. Это свойство логических моделей делает их притягательными для использования в базах знаний. Оно позволяет хранить в базе лишь те знания, которые образуют множество A, а все остальные знания получать из них по правилам вывода. ФС имеют и недостатки, которые заставляют искать иные формы представления. Главный недостаток – это «закрытость» ФС, их негибкость. Модификация и расширение здесь всегда связаны с перестройкой всей ФС, что для практических систем сложно и трудоемко. В них очень сложно учитывать происходящие изменения. Поэтому ФС как модели представления знаний используются в тех предметных областях, которые хорошо локализуются и мало зависят от внешних факторов. Неформальные (семантические) модели представления знаний, их краткая характеристика Существуют два типа методов представления знаний (ПЗ): 1. Формальные модели ПЗ. 2. Неформальные (семантические, реляционные) модели ПЗ. В отличие от формальных моделей, в основе которых лежит строгая математическая теория, неформальные модели такой теории не придерживаются. Каждая неформальная модель годится только для конкретной предметной области и поэтому не обладает универсальностью, которая присуща моделям формальным. Логический вывод – основная операция в ИИС – в формальных системах строг и корректен, поскольку подчинен жестким аксиоматическим правилам. Вывод в неформальных системах во многом определяется самим исследователем, который и отвечает за его корректность. Семантическая сеть Семантическая сеть (СС) – диаграмма, описывающая связи (отношения) между понятиями (концептами) и конкретными объектами некоторой области знаний. Формально СС задается помеченным ориентированным графом, вершинами которого ставятся в соответствие сущности рассматриваемой предметной области (объекты, свойства, события, процессы, явления), а дугам – отношения между сущностями, которые они связывают. СС, в которых вершины не имеют внутренней структуры, называются простыми. Если вершины обладают внутренней структурой, СС называется иерархической. В основе процедур вывода на СС лежит использование транзитивности (наследования) свойств, а также обслуживание запросов путем сопоставления фрагментов сети (подграфов). При этом строится соответствующая запросу подсеть, которая сопоставляется с хранящейся в БЗ сетью. Обработка сложных запросов требует реализации более сложных переборных процедур. При этом в общем случае может существовать несколько вариантов обработки запроса, отличающихся вычислительной сложностью. Очевидно, что эффективность поиска будет определяться особенностями конкретной СС. Проиллюстрируем СС на примере выражения: Студент пришел в аудиторию и слушал лекцию, которую читал преподаватель. Лекция была посвящена ЭС. Введем обозначения: xi – элементы (существительные); rj – связки (глаголы). Студент – x1; аудитория – x2; лекция – x3; преподаватель – x4; ЭС – x5; пришел – r1; слушал – r2; читал – r3; была посвящена – r4. На основе принятых обозначений можно дать графическую трактовку предложения (рис. 5). Данный способ удобен при оперировании с естественным языком (ЕЯ), однако плохо сочетается с теоретическим аппаратом описания машины логического вывода (МЛВ). Рисунок 5 – Семантическая сеть Фреймовые модель представления знаний Концепция фреймов как модели представления знаний была предложена М. Минским в 1975 г. Он определил фрейм как «структуру данных для представления стереотипных ситуаций». Эта структура может быть представлена самой разнообразной информацией об объектах и событиях, которые можно ожидать в этой ситуации, а также о том, как использовать содержащуюся во фрейме информацию. Фрейм содержит множество характеристик ситуации, называемых слотами, и их значений. В самом общем виде фрейм состоит из имени фрейма и последовательности слотов. Концепция фрейма определяет общий подход к представлению знаний, в рамках которого предложении множество различных конкретных конструкций фреймов. В качестве примера рассмотрим фреймовую модель представления знаний в системе FRL (Frame Representation Language). В этой системе фрейм определен как конструкция следующего вида: <ИФ, <ИС, УН, УТД, ЗС, Д, <Х>*, где ИФ – имя фрейма; ИС – имя слота; УН – указатель наследования; УТД – указатель типа данных; ЗС – значение слота; Д – демон; <Х>* – последовательность произвольной длины из элементов <Х>. Имя фрейма является его уникальным идентификатором в рамках рассматриваемой фреймовой системы и используется для обращений к нему. Имя слота выполняет роль уникального идентификатора слота в рамках фрейма. Некоторые слоты могут определяться для внутрисистемных целей или отражать информацию, общую для любых иерархий знаний. Например, в системе FRL слот DEFINEDON хранит дату определения фрейма, а слот IS-A указывает, какому классу принадлежит данный фрейм. Указатель наследования используется во фреймовых системах иерархического типа для указания способа наследования информации, содержащейся в слотах фреймов верхнего уровня, соответствующими слотами фреймов нижних уровней. В системе используются следующие типы наследования: • U (unique) – значение слота фрейма нижнего уровня не связано со значением соответствующего слота родительского фрейма; • S (same) – значение слота дочернего фрейма должно совпадать со значением соответствующего слота родительского фрейма; • R (range) – значение слота дочернего фрейма должно лежать в диапазоне, заданном в соответствующем слоте родительского фрейма; • O (override) – значение слота дочернего фрейма по умолчанию определяется значением соответствующего слота родительского фрейма (как в случае S), но при явном задании определяется этим значением (как в случае U). Наследование позволяет извлекать информацию из родительских фреймов и, таким образом, может рассматриваться как один из механизмов вывода во фреймовой системе. Указатель типа данных явно указывает тип информации, содержащейся в слоте. Значение слота хранит конкретное значение в соответствии с указателем типа данных. Особенностью фреймовых систем является возможность помещать в слоты не только данные, но и процедуры, которые в этом случае называется присоединенными процедурами. Таким образом, фреймы представляют собой комбинацию декларативных и процедурных знаний. Демоны являются специфическим видом присоединенных процедур, которые автоматически запускаются некоторым типовым событием, связанным с данным слотом. Основными видами демонов являются: • IF-NEEDED – запускается, если в момент обращения к слоту его значение не определено; • IF-ADDED – запускается при записи в слот нового значения; • IF-REMOVED – запускается при стирании значения слота. Таким образом, управление выводом во фреймовых системах выполняется с использованием механизма наследования, присоединенных процедур и демонов. Концепция фреймов явилась важнейшей теоретической предпосылкой создания и развития объектно-ориентированного программирования. Существуют различные градации фреймов. Воспользуемся одной из них. Выделим фреймы-описания (элементы) и ролевые фреймы (связки). Фрейм F может иметь иерархическую структуру F = [, …, < Nn, Vn>] где N1, …, Nn – название слота; V1, …, Vn – значение слота. Каждая такая пара называется слот. Возможны ссылки на другие фреймы. Приведем примеры: • фрейм-описание [<машины>, <станки токарные, 70>, <станки фрезерные, 20>]; • ролевой фрейм [<отгрузка>, <станки токарные, 70>, <куда, Москва>, <откуда, СПб>, <вид транспорта, железная дорога>]. Существуют также понятия фрейм-образец (прототип, без введенных данных), называемый интенсиональное описание, фрейм-экземпляр с соответствующими конкретными данными или экстенсионально описание. В другой градации выделяют следующие фреймы: фреймы-структуры (объекты, понятия), фреймы-роли (вариант поведения объекта), фреймы-сценарии (взаимодействие связанных процессов) и фреймы-ситуации (влияние внешней среды). Все процедуры фреймов делятся на две группы: демоны и присоединенные процедуры. Демоны действуют автоматически при удалении, запросе, изменении данных, а присоединенные процедуры лишь после выполнения условий. В силу необычности описания и сложности языка программирования фреймы получили ограниченное применение. К тому же они не сочетаются с методами МЛВ. Продукционные модели представления знаний, их краткая характеристика Продукционная модель знания – модель, основанная на правилах, позволяет предста- вить знание в виде предложений типа «Если (условие), то (действие)». В продукционных системах база знаний состоит из базы данных и базы правил. База данных содержит факты, описывающие вводимые данные и состояние системы, они могут иметь различную форму, но у всех продукционных систем могут быть представлены как группа данных, содержащая имя данных, имена атрибутов, значения атрибутов. В наиболее простом случае, база знаний содержит набор продукционных правил вида: ЕСЛИ <условие>, ТО <действие>. Механизмом выводов в продукционных системах является интерпретатор правил. В наиболее полном случае, обладающим большей выразительной способностью, правила имеют вид: . Здесь – ядро, являющееся основным элементом продукции. Обычно оно интерпритируется фразой «Если А, то В». Под А обычно понимается условие существования заключения В; (i) – продукции, с помощью которого данная продукция выделяется из множества продукций. Именем может быть как номер, так и имя понятия, которому она соответствует; Q – сфера применения продукции, описывающая ПО или ситуацию. Это позволяет систематизировать продукции, что облегчает работу с системой продукций; Р – условие применимости ядра продукции (предикат). Если Р истинно, ядро продукции активизируется; N – постусловие продукции. Оно представляет собой процедуру, которую следует выполнить после успешной реализации ядра (необязательно сразу). Например, после покупки вещи у продавца их количество следует уменьшить на 1. Все части продукции, кроме ее ядра, являются факультативными. В зависимости от оценок реализации ядро делится на обязательное и необязательное. В качестве оценок реализации могут применяться вероятность, возможность, коэффициент уверенности. Например: ЕСЛИ А, ТО с большой долей уверенности реализовать В. Взаимосвязанный набор продукций образует систему. Основной проблемой вывода знания в системе продукций является выбор для анализа очередной продукции. Проиллюстрируем проблему следующим примером: а) А→В; б) B&D→A; в) A∨B→D; г) D→C. Если истинно условие А, то кандидатами на выполнение являются продукции а) и в), если же истинны условия В и D, то – б), в) и г). Этот пример показывает, с одной стороны, неоднозначность выбора очередной продукции, а с другой – возможность распараллеливания вычислений (одновременной реализации группы продукций). Конкурирующие продукции образуют фронт. Существуют два варианта организации цепочки выводов: суждение по цепочке вперёд и суждение по цепочке назад (прямой и обратный выводы). При суждении по цепочке вперёд выполняются все правила, которые могут быть выполнены в настоящий момент, при их исполнении происходит модификация базы данных, которая может привести к возможности выполнения других правил из базы знаний. Основной недостаток состоит в том, что необходимо пройти всю цепочку, чтобы получить требуемый результат (излишние затраты времени и финансовых средств, то есть неоптимальная работа системы). Эффективнее вывод при суждении по цепочке назад: в базе правил отыскивается правило, содержащее искомый факт в правой части (после TO), а затем в базе данных ищутся факты, указанные в левой части правила (после ЕСЛИ). Если таких фактов нет, система пытается найти правила, позволяющие прийти к ним, и так происходит до тех пор, пока не будут найдены все требуемые факты («удача рассуждения»), или же не будет исчерпана возможность их нахождения («неудача рассуждения»). В общем виде функционирование продукционной системы представлено на рисунке 6. Рисунок 6 – Функционирование продукционной системы Заключение Системы на естественном языке специфичны и предназначены преимущественно для таких целей, как машинный перевод, генерация документов, автоматическое аннотирование и реферирование. Контрольные вопросы 1) Назовите основные сферы использования МП. 2) Дайте характеристику основных классов ЕЯ-систем, поясните их особенности, области применения, подберите пример применения. 3) Чем морфологический анализа текста отличается от синтаксического анализа? 4) Перечислите несколько достоинств логических моделей представления знаний. 5) Дайте определение продукционной модели знания.