Модели и алгоритмы контроля знаний обучаемых на основе сетей Петри

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

ФОРМУЛИРОВКА И АКТУАЛЬНОСТЬ РЕШАЕМОЙ ПРОБЛЕМЫ

В связи с развитием вычислительной техники и информационных технологий появляется возможность применять искусственный интеллект (ИИ) в автоматизированных обучающих системах (АОС). Одной из проблем, которую можно решить в АОС с помощью ИИ на основе сетей Петри (СП), является контроль знаний в случае, когда в качестве тестовых заданий (ТестЗ) применяются ТестЗ открытого типа с максимально свободной формой изложения ответа обучаемого. До сих пор решение этой проблемы сдерживалось из-за непонимания ЭВМ естественного языка (ЕЯ) и невозможности оценки машиной полученных ответов.

ИЗВЕСТНЫЕ ПОДХОДЫ К РЕШЕНИЮ

В системах ИИ (системах машинного перевода, экспертных системах (ЭС)) эту задачу обычно решает лингвистический процессор (ЛП) [1]. Формальный аппарат ЛП — это метаязык лингвистического описания, позволяющий представить информацию о языке в наглядной и математически строгой форме и облегчающий объективную проверку адекватности этого описания.

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

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

Концептуальная модель ЛП приведена на рис. 1 и может быть представлена кортежем [1]

LP = , где F — формальный аппарат; М — формальная модель; S — структура данных; А — алгоритм анализа и синтеза; I — интерфейс, преобразующий входные данные во внутреннее представление и наоборот.

Известные способы математического описания содержания ЕЯ в ЛП рассмотрены в [2] и используются: при разработке формальных языков-посредников, в грамматике Монтегю, в теории обобщенных кванторов, в теории структурированных значений предложений, в динамической предикатной логике, в теории представления дискурсов. Однако они требуют различных подходов для описания ЛП, что не позволяет использовать для этого единый формальный аппарат алгоритмов его работы и затрудняет анализ.

I 1

I 2

Выходные данные

Рис. 1. Концептуальная схема ЛП

ПРЕДЛАГАЕМЫЙ ПОДХОД, ЕГО НОВИЗНА И ОСОБЕННОСТИ

В качестве единого аппарата (метааппарата) для построения лингвистических моделей, для моделирования взаимодействия компонентов системы, таких как формальные модели, данные и алгоритмы, предлагается использовать СП.

Сеть Петри есть двудольный ориентированный граф и определяется [3, 4] как

С = <Р, Т, А, Мо>, (1)

где соответственно Р — конечное множество позиций; Т — конечное множество переходов; А — алгоритмические представления, а Мо — начальная маркировка сети.

Предлагаемый в качестве ИИ аппарат СП обладает следующими достоинствами:

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

• 2)    легкость описания алгоритмов;

• 3)    понятность (доступна пониманию математикам, лингвистам и инженерам);

• 4)    модель, построенную на основе СП, легко оценить на устойчивость, обратимость, работоспособность, являющиеся важными свойствами любого программного комплекса.

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

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

С =

0, Ω>, (2)

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

ОСОБЕННОСТИ РЕАЛИЗАЦИИ ПРЕДЛАГАЕМОГО ПОДХОДА

Исходя из выбранного аппарата, в разрабатываемых ЛП было решено применить ряд формализмов.

• 1.    На уровне морфологии была применена атрибутивно-типовая модель, представленная на основе СП и реализованная в виде отношений с помощью реляционных СУБД. На их основе были

• 2.    На этапах анализа, синтеза и корректировки словоформ были применены лингвистические СП и создан программный комплекс, позволяющий на входе задать с их помощью сетевой шаблон (порядок следования морфем), а на выходе получить готовое разложение сети в виде набора путей.

• 3.    На уровне синтаксиса разработана формальная модель синтаксических отношений с помощью СП, их типовая классификация и алгоритмы анализа. Таким образом, СП впервые столь широко использованы в ЛП.

• 4.    База знаний (БЗ) (содержащаяся в реляционной СУБД) использовалась в рамках предметной области "Воздушная навигация" [5].

• 5.    Реализация алгоритмов произведена с использованием технологии РНР + МуSQL + Flash для применения наработок в системе дистанционного образования [6, 7].

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

В ЛП имеются два анализатора — морфологический (МА) и синтаксический (СА) (рис. 2) [8]. Каждый из них состоит из набора алгоритмов, реализующих обработку поступающей информации, и структур данных, служащих для извлечения необходимых для этого данных из формальной модели и хранения анализируемой информации. ЛП может работать и как СА, и как МА. В первом случае на вход поступает предложение, а на выходе выдается ею синтаксическая структура (СинтС); во втором — на вход подается словоформа (С), а на выходе выдается ее морфологическая структура (МорфС). При этом МА ЛП осуществляет не только анализ словоформы, но и проверку на корректность, а СА осуществляет еще и классификацию предложения по типам.

Рис. 2. Архитектура ЛП

Рис. 3. Сетевая модель извлечения данных с помощью шаблонов. p₁₉ е P, t_1-3е T

Рис. 4. Модель СинтО. p_1-4е P, t_1-2е T

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

Основной задачей синтаксического анализатора ЛП является преобразование МорфС предложений, поступающих с выхода морфологического блока в СинтС. Так как МорфС предложения состоят из МорфС отдельных словоформ, то переход от МорфС предложения к его СинтС осуществляется путем установления синтаксических связей между МорфС слов и между ними самими. При этом МорфС отдельных словоформ служит для их установления. Такие связи принято называть син- таксическими отношениями (СинтО), и, как показано в [9], все они могут быть смоделированы с помощью СП.

Для анализа простых предложений ЕЯ достаточно около 16 СинтО, что было выявлено путем анализа типов [1]. Все СинтО бинарные и ориентированные. Ориентированность подразумевает то, что все отношения представлены в формате: Y (левая часть)—Х (правая часть), где Х — главное слово, а Y — зависимое.

Введем следующие позиции и переходы: p1 — содержит маркер с атрибутом X, который, возможно, является сказуемым; p₂ — содержит маркер с атрибутом Y, который, возможно, является подлежащим; p3 — содержит маркер, если СинтО может быть установлено; p₄ — вспомогательная позиция; t1 — проверка условия, что Х — сказуемое; t₂ — проверка условия, что Y — подлежащее (существительное, местоимение или числительное).

На рис. 4 показано, как СП моделирует СинтО. При наличии в позиции p₁ сказуемого X срабатывает переход t1. Если это происходит, то при наличии в позиции p₂ подлежащего Y срабатывает переход t2. При этом устанавливается, что первое подлежащно-сказуемостное отношение имеет место. Аналогично моделируются остальные 15 синтаксических отношений.

ПРИМЕРЫ ПРИМЕНЕНИЯ ПРЕДЛАГАЕМОГО ПОДХОДА

Рассмотрим применение СП для реализации морфологического и синтаксического анализаторов на примере четырех открытых ТестЗ, взятых из [5].

В табл. 1 в столбце "Текст ТестЗ" цифрами обозначены правильные варианты ответов. На основании перечня возможных ответов опишем глоссарий (табл. 2). Для каждой из словоформ представим ее лексическую структуру (табл. 3). Морфологическая структура рассмотрена в табл. 4.

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

Описание лексической структуры может быть представлено в виде (3):

Причастие =

= < Префикс > & < Основа > & < Суффикс > & & < Окончание > & < Частица >. (3)

Оно позволяет создать экземпляры шаблонов.

Табл. 1. Тестовые задания (ТестЗ) в открытой форме

№	Название теста	Текст теста	Ответы
1	Метеорологическое направление ветра	Метеорологическим направлением ветра называется _1_, заключенный между _3_ _2_ _4_ и _2_, откуда дует ветер	1.    угол; 2.    направление; 3.    северный; 4.    меридиан
2	Навигационное направление ветра	Навигационным направлением ветра (НВ) называется _1_, заключенный между _2_, принятым для ориентации _2__3_, и_2_ , куда дует ветер	1.    угол; 2.    направление; 3.    полет
3	Магнитное склонение	Магнитным склонением (∆М) называется _2_ между _1_ и _3_ меридианами в данной точке	1.    истинный; 2.    угол; 3.    магнитный
4	Азимутальная поправка	Азимутальной поправкой (∆А) называется _1_ между _3_ и _2_ меридианами	1.    угол; 2.    истинный; 3.    условный

Табл. 2. Глоссарий для ТестЗ из табл. 1

№	Словоформа	Часть речи
1	угол	Существительное
2	направление	–″–
3	северный	Прилагательное
4	меридиан	Существительное
5	полет	–″–
6	истинный	Прилагательное
7	магнитный	–″–
8	условный	–″–

Табл. 3. Лексическая структура словоформ из глоссария табл. 2

№	Словоформа	Префикс	Основа	Тема	Суффикс	Окончание	Частица
1	угол	—	угол	—	—	—	—
2	направление	—	направл	—	ен	ие	—
3	северный	—	север	—	н	ый	—
4	меридиан	—	меридиан	—	—	—	—
5	полет	—	полет	—	—	—	—
6	истинный	—	истин	—	н	ый	—
7	магнитный	—	магнит	—	н	ый	—
8	условный	—	услов	—	н	ый	—

Табл. 4. Морфологическая структура

Лексема без словоизменения	Атрибуты
	Вид	Залог	Время	Число	Род	Падеж
угол	—	—	—	Ед.	Муж.	Им.
направление	—	—	—	–″–	Ср.	–″–
северный	—	—	—	–″–	Муж.	–″–
меридиан	—	—	—	–″–	–″–	–″–
полет	—	—	—	–″–	–″–	–″–
истинный	—	—	—	–″–	–″–	–″–
магнитный	—	—	—	–″–	–″–	–″–
условный	—	—	—	–″–	–″–	–″–

Табл. 5. Пример морфологической омонимии для слова магнитный

Лексемы	Часть речи	Атрибуты
		Одушевленность	Род	Число	Падеж
магнитный	Прил.	Неодуш.	Муж.	Ед.	Им.
–″–	–″–	–″–	Ср.	–″–	–″–
–″–	–″–	–″–	Жен.	–″–	–″–
–″–	–″–	–″–	Муж., жен., ср.	Мн.	–″–

Табл. 6. Экземпляры шаблонов

Префикс	Основа	Суффикс	Окончание	Частица
#	1	#	+|#	#
#	2	#	ие	#
#	3	н	ые	#
#	4	н	ый	#

Примечание. Здесь используются следующие обозначения: + — наличие лексемы; # — отсутствие лексемы; | — логическое исключительное ИЛИ.

Рис. 5. Исходная форма ТестЗ

Рис. 6. Форма ТестЗ после ввода исходных данных и проверки результата

Помимо морфологического анализа система должна анализировать синтаксическую составляющую текста. Синтаксический анализ заключается в проверке правильной последовательности словоформ в определении.

Синтаксическое расположение словоформ представляется в виде матрицы-шаблона разрядностью n × m, где n — количество строк, m — количество столбцов:

	"1	0	0	0"
	0	1	1-1	0
X = mn	0	1-1	1	0	.                      (4)
	0	0	0	1

Коэффициент 1 элемента матрицы (4) говорит

о том, что n-я словоформа может располагаться в m-й ячейке определения; 1^–1 — информирует, что словоформы могут меняться ячейками без потери смысла определения; 0 — словоформа не может располагаться в данной ячейке ни в коем случае.

Описанная выше методика была реализована в программе на объектно-ориентированном языке программирования Borland Delphi 7.0 и апробирована в СПбГУАП. В программе были реализованы механизмы морфологического и синтаксического анализаторов при ответе на открытое ТестЗ (рис. 5). На первом этапе производится орфографический анализ введенной информации обучаемым, за который выставляется коэффициент М. На втором этапе производится синтаксическая оценка С введенного текста в открытое ТестЗ. По сумме двух коэффициентов система выставляет оценку обучаемому.

Рис. 7. Форма ТестЗ с правильным ответом

Система подробно описывает все ошибки обучаемого (рис. 6) и показывает правильный ответ (рис. 7).

ВЫВОДЫ

По результатам исследований с учетом практического применения реализованного подхода:

• •    уменьшилось потребное учебное время инструктора по сравнению с обучением без АОС;

• •    увеличилась объективность контроля знаний;

• •    дифференцировалась скорость обучения;

• •    расширилась интеллектуальность АОС (функцию анализа ТестЗ выполняет ЭВМ, в том числе анализ открытых ТестЗ).

Предлагаемый к использованию аппарат позволяет подойти к анализу ЕЯ с точки зрения системы ИИ. Аппарат позволяет описывать сложные процессы распознавания ЕЯ с помощью СП и реализовать тестовый контроль знаний на основе ТестЗ открытой формы. Применение СП дало возможность использовать единый подход и формат для всех структурных единиц ЛП.