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

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

УДК 004.838:004.853:004.855.5

Генератор тестовых примеров для различных вариантов ДСМ-метода

Ю.В. Козлова

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

В статье рассматривается программа «TestJSM!» для порождения тестовых примеров, демонстрирующих возможности разных вариантов ДСМ-метода. В частности, эта программа может быть использована для проверки стратегий ДСМ-метода [Финн, 1991], а также для сравнения выразительной силы ДСМ-стратегий Будем говорить, что выразительная сила стратегии S не больше, чем выразительная сила стратегии S', если все гипотезы, которые можно породить с помощью стратегии S, можно породить и с помощью стратегии S'. Можно сравнивать выразительную силу стратегий и для каких-либо конкретных разновидностей гипотез, например, только для гипотез первого (второго) рода, только для положительных (отрицательных) гипотез и т.п.. Программа написана на языке Visual Prolog.

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

Объектная модель системы требований

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

· может порождать данные для проверки и сравнения эффективности разных ДСМ-стратегий;

· может использоваться для тестирования разрабатываемых ДСМ-систем;

· может использоваться как генератор задач для студентов, изучающих ДСМ-метод.

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

· выбор ДСМ-стратегии,

· ввод желаемых причин, свойств, тормозов,

· определение ограничений на объекты, порождающие причины и тормоза.

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

Рис.1 Объектная модель системы требований

Описание работы генератора тестовых примеров «TestJSM!»

Основными функциями генератора примеров для ДСМ-метода являются: тестовый автоматический генерация

· ввод новой системы требований к примерам в соответствии с объектной моделью,

· загрузка ранее сохраненной системы требований из файла формата XML,

· порождение примеров в виде таблицы «Объект-Свойство»,

· сохранение примеров в файлах форматов CSV и XLS,

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

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

· start_jsm (ListEl, First, Last, [Elnum | Rest], Fin) - 5-арная предикатная переменная, описывающая отношение между параметрами, задаваемыми пользователем (ListEl, First, Last, [Elnum | Rest]), и конечным результатом работы системы правил (Fin):

o ListEl - список элементов рассматриваемой причины,

o First и Last - начало и конец диапазона атомов, образующих объекты, пересечением которых является рассматриваемая причина,

o Fin - список объектов, пересечением которых является упомянутая выше причина,

o [Elnum | Rest] - список, который для каждого объекта содержит количество элементов, не входящих в рассматриваемую причину, указывается первый элемент списка (Elnum) и оставшиеся элементы (Rest);

· final_list (ListEl, First, Last, Elnum, List) - 5-арная предикатная переменная, имеющая смысл, аналогичный предыдущей предикатной переменной:

o ListEl, First, Last, Elnum понимаются так же, как и в предыдущем предикате,

o List - список элементов одного из объектов, содержащих причину;

· list (ListEl, First, Last, Elnum, List1) - 5-арная предикатная переменная, которая описывает отношение между данными, задаваемыми пользователем (ListEl, First, Last, Elnum), и порождаемым с помощью генератора псевдослучайных чисел списком элементов, не входящих в причину (List1):

o ListEl, First, Last, Elnum понимаются так же, как и в первом предикате,

o List1 - список элементов, не входящих в причину;

· append (ListEl, List1, Res) - тернарная предикатная переменная:

o ListEl - список элементов рассматриваемой причины,

o List1 - список элементов, не входящих в причину,

o Res - список, являющийся объединением списков ListEl и List1;

· casual (First, Last, El) - тернарная предикатная переменная:

o First и Last - начало и конец диапазона атомов, образующих объекты, пересечением которых является рассматриваемая причина,

o El - случайный элемент из диапазона [First, Last];

· member (El, ListEl) - бинарная предикатная переменная, означающая, что элемент El входит в список ListEl:

o параметры El и ListEl описаны выше;

· rest_els (Els) - унарная предикатная переменная, используемая для сохранения списков элементов, не входящих в причину:

o Els - список списков элементов, не входящих в причину (для каждого объекта формируется свой список элементов, не входящих в причину);

· member2 (El, Els) - бинарная предикатная переменная, означающая, что элемент El входит в один из элементов списка Els:

o параметры El и Els описаны выше.

Генерация тестовых примеров для простого ДСМ-метода может быть записана как следующая система правил:

% пополнение списка объектов, содержащих причину

start_jsm (ListEl, First, Last, [Elnum | Rest], Fin)

final_list (ListEl, First, Last, Elnum, List),

start_jsm (ListEl, First, Last, Rest, [List | Fin]).

% формирование списка элементов одного объекта

final_list (ListEl, First, Last, Elnum, Res)

list (ListEl, First, Last, Elnum, List1),

append (ListEl, List1, Res).

% формирование списка элементов, не входящих в причину (для каждого объекта формируется свой список)

list (ListEl, First, Last, Elnum, RestList)

Elnum > 0,

casual (First, Last, El),

?member (El, ListEl),

?member (El, RestList),

rest_els (Els),

?member2 (El, Els),

Elnum1 = Elnum -1,

list (ListEl, First, Last, Elnum1, [El | RestList]).

Работа экспериментальной ДСМ-системы с тестовыми данными, порожденными генератором «TestJSM!»

Рассматриваемая ниже ДСМ-система была разработана О.А.Сафроновой [Efimova et al, 2006] на языке Visual Prolog на основе системы правил, предложенных Д.В.Виноградовым в [Виноградов, 1999] и [Виноградов, 2001]. В этой экспериментальной ДСМ-системе в отличие от профессиональных ДСМ-систем реализованы все основные разновидности ДСМ-стратегий.

Простой ДСМ-метод без итераций и простой ДСМ-метод с итерациями

Итак, сравним работу простого ДСМ-метода без использования итераций и работу простого ДСМ-метода, использующего итерации. Оба метода прямые с запретом на контрпример.

С помощью генератора «TestJSM!» было порождено 10 тестовых примеров с одним целевым свойством для простого ДСМ-метода с итерациями. После этого полученные примеры были последовательно поданы на вход ДСМ-системы для простого ДСМ-метод без итераций и для простого ДСМ-метода с итерациями.

Результаты работы простого ДСМ-метода без итераций и с итерациями сравнивались по следующим параметрам:

· количество гипотез, порожденных на этапе индукции,

· количество гипотез, порожденных на этапе аналогии (что соответствует и количеству доопределенных примеров),

· количество «+»-примеров среди доопределенных,

· количество «-»-примеров среди доопределенных,

· количество «0»-примеров среди доопределенных.

На следующих диаграммах представлено сравнение методов по первым двум параметрам.

Рис.2 Сравнение простого ДСМ-метода с итерациями и без итераций.
Количество гипотез на этапе индукции.

Рис.3 Сравнение простого ДСМ-метода с итерациями и без итераций.
Количество гипотез на этапе аналогии.

На диаграммах хорошо видно, что при использовании итераций в простом ДСМ-методе количество порождаемых гипотез, как на этапе индукции, так и на этапе аналогии значительно больше, чем количество гипотез, полученных в процессе работы простого ДСМ-метода без итераций.

Следует заметить, что количество итераций не везде было одинаковым. Так, для примеров №1-5 было сделано 3 шага работы ДСМ-метода, для примеров №6-8 - 4 шага и для примеров №9-10 - 5 шагов. По диаграммам видно, что чем больше ДСМ-метод делает шагов, тем больше порождается гипотез.

Простой ДСМ-метод без итераций и обобщенный ДСМ-метод

Сравним результаты работы простого ДСМ-метода с запретом на контрпример, не использующего итерации, и результаты работы обобщенного ДСМ-метода без итераций. Оба метода прямые.

С помощью генератора «TestJSM!» было порождено 10 тестовых примеров с одним целевым свойством для обобщенного ДСМ-метода. После этого примеры были поданы на вход ДСМ-системы для простого ДСМ-метода без использования итераций и для обобщенного ДСМ-метода без итераций.

Результаты работы методов сравнивались по следующим параметрам:

· количество «+»-примеров среди доопределенных,

· количество «-»-примеров среди доопределенных,

· количество «0»-примеров среди доопределенных.

Cравнение по этим параметрам представлено на следующих диаграммах.



Рис.4 Сравнение простого ДСМ-метода и обобщенного ДСМ-метода.
Количество доопределенных «+»-примеров.

Рис.5 Сравнение простого ДСМ-метода и обобщенного ДСМ-метода.
Количество доопределенных «-»-примеров.

Рис.6 Сравнение простого ДСМ-метода и обобщенного ДСМ-метода.
Количество доопределенных «0»-примеров.

Из сравнения результатов работы простого ДСМ-метода и обобщенного видны особенности каждой из стратегий, а именно, что обобщенный ДСМ-метод порождает больше положительных и отрицательных гипотез и вообще не порождает «0»-гипотез, а простой порождает достаточно большое количество противоречивых гипотез.

Итак, был продемонстрирован пример применения тестовых примеров, получаемых генератором «TestJSM!», в качестве входных данных для ДСМ-системы. Было показано, что тестовые примеры могут использоваться для тестирования работы ДСМ-системы, а также для сравнения разных вариантов ДСМ-метода. На основании сравнения можно выдвинуть определенные гипотезы о работе того или иного метода, но для этого нужна, без сомнения, более объемная статистика.

Список литературы

1. [Виноградов, 1999] Виноградов Д. В. Логические программы для квазиаксиоматических теорий // НТИ. Сер 2. 1999. № 1_2.

2. [Виноградов, 2001] Виноградов Д. В. Корректные логические программы для правдоподобных рассуждений // НТИ. Сер. 2. 2001. №5.

3. [Финн, 1991] Финн В.К., Правдоподобные рассуждения в интеллектуальных системах типа ДСМ. // Итоги науки и техники. Сер. Информатика. 1991. Т. 15 (Интеллектуальные информационные системы).

4. [Efimova et al, 2006] Efimova E., Safronova O., Vinogradov D. A Prototype of JSM-system in Visual Prolog // Proceedings of the First Visual Prolog Applications and Language Conference. Prolog Development Center. 2006.

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

...