Разработка метода генерации тестов для отладки экспертных систем, основанных на нейросетевом представлении знаний

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

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

Современная нейроинформатика располагает большим количеством нейросетевых моделей, однако наибольшее распространение получила модель многослойного персептрона, являющаяся развитием модели персептрона Розенблатта. Это связано с тем фактом, что большая часть прикладных задач может быть формализована как задачи классификации входных векторов Хх. Х2, . . . Х_п по т выходным классам 01,02,..., о_т, а для решения именно таких задач применяются многослойные персептроны. Модель многослойного персептрона подразумевает наличие входного слоя нейронов, одного или нескольких промежуточных слоёв и выходного слоя.

Следует заметить, что Колмогоровым было теоретически доказано, что математическая функция

где x^lnj_n — значение г„-го входа j_n-го нейрона слоя гг; в',‘_п — значение смещения j„-го нейрона слоя гг, соответствующая персептрону с одним скрытым слоем, приближает произвольную данную функцию с погрешностью не более заранее заданной малой величины г на всей области определения.

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

Жизненный цикл нейросетевых ЭС соответствует жизненному циклу классических ЭС и включает в себя такие этапы, как идентификация, концептуализация, формализация, выполнение, отладка, опытная эксплуатация. Особенностью жизненного цикла нейросетевых ЭС является то, что на этапе формализации производится выбор множества входных фактов F = { /,. /₂,..., /_п} и выходных О — {oi,02,... ,о_то} классов системы, а также формируется обучающее множество вида

где X, — {x,x₂,...,x_q} — г-й входной вектор нейронной сети; У) — — {уи У2-. ???? !J,j } — г-й известный выходной вектор нейронной сети.

На этапе выполнения наполнение БЗ экспертом заменяется автоматическим процессом обучения нейронной сети.

К большинству существующих нейросетевых ЭС предъявляются повышенные требования к корректности функционирования, поэтому очень большое значение приобретает этап отладки, в ходе которого проверяется компетентность ЭС на предмет соответствия поставленных целей и выдаваемых решений, а также исправление найденных ошибок. С точки зрения обнаружения ошибок наиболее эффективным методом отладки является тестирование, т. е. выполнение ЭС на тестовом множестве, состоящем из входных и известных выходных данных. Тестовое множество должно включать в себя такие примеры, которые обнаруживают как можно большее количество ошибок, и успех проведения тестирования зависит от того, насколько развиты методы создания тестового множества. В настоящее время широко используется подход, основанный на использовании в качестве тестового множества некоторого подмножества имеющихся примеров предметной области, которое не используется для обучения нейронной сети (работы Цисильского, Жу, Балашубрама- ниана, Паланивела, Рамалингама, Ребровой, Ишанова). В случае недостатка имеющихся примеров чаще всего применяется экспертная генерация тестовых данных, при которой эксперт, основываясь на своём опыте, пытается сгенерировать такие примеры, которые, по его мнению, могут вызвать ошибку ЭС. Таким образом, создавались тестовые наборы для нейросетевой ЭС Carbonate detector, нейросетевых экспертных систем проекта NASA Applied Information Systems Research Program, экспертные системы обнаружения ошибок операторов производственного оборудования, разработанные в Nova Southeastern University. Во всех вышеперечисленных случаях отсутствовала гарантия того, что сгенерированное тестовое множество обладает высокой обнаруживающей способностью. Основная проблема заключается в том, что эксперту трудно вспомнить и учесть все нюансы предметной области из-за её высокой сложности.

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

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

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

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

где Xi, Х2, ? ? ?, Х_т — множество описаний объектов; X; = [жi,ж 2, х_ч] — описание i-ro объекта; Xj — значение j-го признака объекта; О — {01,02,..,о/.} — множество выходных классов. Класс о_; определяется выходным вектором нейронной сети Yj — [yi,y2,j/t], где Уз > Уг при г ф ].

Приведем используемый алгоритм обучения нейронной сети. Введем понятие ошибки нейросетевой ЭС, решающей задачу классификации, как факт неверного отнесения к классу су- наблюдения Xi = [.Г1.Ж2. ...,х_р], принадлежащего к классу о_р:

где Р — функция, реализуемая нейросетью; Х, Х2,Х_п — множество наблюдений; О — {01,02, ..,o_t} — множество выходных классов.

Ошибки нейросетевых ЭС классифицированы по причинам возникновения на следующие классы:

• • ошибки, вызванные некорректной программной реализацией нейросетевой ЭС;
• • ошибки, вызванные вычислительными сбоями времени выполнения ЭС;
• • ошибки, вызванные некорректно проведённым процессом обучения нейронной сети;
• • ошибки, вызванные особенностями предметной области ЭС. Наиболее сложными для обнаружения являются ошибки, связанные с особенностями предметной области, неучтёнными при разработке ЭС. Введем формализовано понятие исключения предметной области как ситуации, когда для некоторых входных данных нейросеть на основании установленного набора фактов //,/2,..., /{, некоторого наблюдения X/ делает заключение о принадлежности X/ к классу оXi е Х°к, которое на самом деле оказывается неверным из-за того, что X/ характеризуется некоторой комбинацией фактов

установка которой однозначно свидетельствует о непринадлежности X/ к классу Ok-

Наличие исключительной комбинации F_x является особенностью предметной области, и в случае, если такая комбинация останется неучтённой при разработке, нейронная сеть будет выдать при её возникновении неверный результат

на основании статистической близости X; к классу Х°^к. Ошибка нейронной сети такого типа формализуется математически в следующем виде:

Наблюдение Х₍, характеризующееся наличием комбинации (7.26), называется исключением, а ошибка (7.29) нейронной сети на таком наблюдении носит характер «забывания об исключении». Введем понятие степени ошибки типа «забывание об исключении» как количество фактов /ъ /г, • ••, fd в комбинации.

Отладка нейронной сети может быть статической и динамической. Однако ошибки вида (7.30) могут быть обнаружены только методом динамической отладки (тестированием), для которого необходимо тестовое множество вида

где (Xi.Yi) — Ti — i-й тест множества; X; — {xi,X2, ???, x_q} — г-й входной вектор нейронной сети; У) = {щ, уг, ???, Ut} — г-й выходной вектор нейронной сети.

Множество Т должно учитывать комбинации фактов, приводящих к ситуации (7.28). Главная проблема состоит в том, что существующие методы генерации тестовых наборов, основанных на имеющейся базе данных ретроспективных примеров, на модели предметной области или на экспертной генерации не гарантируют учёта всех комбинаций фактов, приводящих к ошибкам типа «забывание об исключении».

Проведённый анализ литературы показал, что на данный момент отсутствуют автоматизированные методы генерации тестовых

Рис. 7.7. Пример логической схемы нейронной сети

данных, способных выявить ошибки нейросетевых ЭС, связанные с исключительными ситуациями предметной области.

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

ЕСЛИ f_a ИЛИ /_ь... ИЛИ f_c

И fd ИЛИ fa ... ИЛИ f{

ТО класс, .

Пусть при помощи алгоритма GLARE получено правило ЕСЛИ Л ИЛИ /₂ И /₃ ИЛИ /₄ И /₅ ТО классу Тогда это правило может быть представлено в виде логической схемы, показанной на рис. 7.7.

В терминах нейросети исключительная ситуация в схемотехническом представлении формализуется как наличие набора линий Ь_х = {Д. /г,.... }, при одновременной установке на которых значения 1 на выходной линии не должно устанавливаться значение 1 независимо от сигналов на других входных линиях. Ошибка типа «забывание об исключении» в данном случае формализуется как установка на выходной линии схемы значения 1, несмотря на одновременную установку значения 1 на линиях I1J2, •••, Ik-

Часть схемы, учитывающую исключительную комбинацию фактов /х, /₂,..., fd и состоящую из конъюнктора, инвертора и соединяющих линий, будем называть комбинационным блоком. На рис. 7.8 комбинационный блок включает в себя элементы 64, Д>, а также линии /9,/ю,/п,/12-

Схемотехническое представление ошибки нейронной сети типа «забывание об исключении» представляет собой неисправность типа

Рис. 7.8. Пример логической схемы, учитывающей исключительную ситуацию

предметной области

«константная 1» на выходной линии комбинационного блока (неисправность /12/I для схемы на рис. 7.8). Для построения множества тестов, обнаруживающих вышеописанные константные ошибки, может быть применён метод PODEM Гоуэла.

Метод PODEM не учитывает возможности установки во входных векторах A'i. Х-у-.-Х,, тестов значений, соответствующих запрещённым комбинациям фактов предметной области. Для решения данной проблемы предлагается модификация метода PODEM, заключающаяся в следующем.

Пусть множество запрещённых комбинаций входных фактов предметной области формализовано в виде наборов D-кубов С_х. Тогда на этапе D-установки, D-прохода или операции продвижения назад по мере построения входного вектора очередного i-го теста схемы на его основе будем строить входной D-куб R,. При этом в случае С_х П Л! = 0:

• 1) на этапе D-установки извлечём из стека SStack очередную линию /, и произведём операцию D-установки, рассматривая путь, начинающийся с линии Z*;
• 2) на этапе D-прохода извлечём из стека DStack очередной элемент bi и повторим для него операцию D-прохода;
• 3) на этапе продвижения назад прервём операцию продвижения назад для линии 1_т, извлечём из стека SStack очередную линию

и повторим для неё операцию продвижения назад. В случае, если ни по одной из линий в стеке SStack операцию возврата выполнить не удалось, то извлечём из стека DStack очередной элемент Ь( и повторим для него операцию D-прохода.

Тестовое множество вида (7.31) предложено называть полным, если оно обнаруживает все устанавливаемые комбинации входных фактов, приводящих к ошибкам типа «забывание об исключении» всех степеней гп, гп = 1 где п — количество входных фактов ЭС.

Предложим следующий метод генерации полного тестового множества нейронной сети:

• 1. Установить искомое множество тестов пустым Т — 0.
• 2. При помощи алгоритма GLARE извлечь продукционные правила R,R2,...,Rt вида (11) из персептрона Р для каждого выходного класса о, 02,..., o_f.
• 3. Экспертным методом сформировать множество кубов запрещённых комбинаций С_х.
• 4. Рассмотреть продукционное правило Л; для нерассмотренного выходного класса о, .
• 5. Преобразовать рассматриваемое продукционное правило к виду логической схемы S.
• 6. Применить модифицированный алгоритм PODEM для схемы S с учётом множества кубов запрещённых комбинаций С_х; получить полное тестовое множество Т для логической схемы S.
• 7. Рассмотреть очередной тест T_i 6 Т, 7] — (Л,,о;), где R, — входной D-куб; о, — ожидаемое выходное значение схемы, обнаруживающий возможную ошибку типа «забывание об исключении», связанную с одновременной установкой фактов /ь/г,/к-
• 8. Преобразовать куб Л/ к входному вектору нейросети Х_г = = [xi,X₂,-,X_q.
• 9. Экспертным путём определить выходной класс о, для X,;.
• 10. Создать г-й тест нейросети (X,, о*) и включить его в искомое тестовое множество Т = Т U (Х;,а,).
• 11. Перейти к шагу 4, рассмотрев продукционное правило для ещё нерассмотренного выходного класса о у
• 12. Завершить генерацию тестов.

Алгоритм PODEM, лежащий в основе вышеприведённого метода, позволяет строить тест всегда, когда он существует, а также гарантирует обнаружение всех константных неисправностей схемы, что позволяет сделать вывод о том, что вышеприведённый метод гарантирует обнаружение всех ошибок типа «забывание об исключении» нейросетевых ЭС. Так как ошибки нейросетевых ЭС типа «забывание об исключении» являются наиболее общими и покрывают другие типы ошибок, то тестовое множество, полученное по предлагаемому методу, является полным.

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

Рис. 7.9. Зависимость времени генерации тестов от размера входного слоя

Программно алгоритм генерации тестов реализован в виде приложения NNetwork Tester. Язык разработки — С#, среда разработки — Microsoft Visual Studio 2008.

Проведны многочисленные экспериментальные определения характера зависимости времени генерации тестовых наборов от количества нейронов на входном слое. Эксперимент проводился на IBM- совместимом PC с процессором Intel Core 2 Duo с тактовой частотой 3 ГГц и объёмом ОЗУ 1024 Мб. Выявленная в ходе эксперимента зависимость носит нелинейный характер и может быть приближённо описана экспоненциальной функцией вида у — 64е^0,2х. При размере входного слоя до 600 нейронов время генерации тестов не превышает 10 секунд. Большинство существующих нейросетей, как видно из рис. 7.9, содержат до 600 нейронов на первом слое, что позволяет сделать вывод о широкой практической применимости разработанного метода.

Проверка работоспособности разработанного метода генерации тестов производилась на реальной нейросетевой ЭС.

В качестве механизма принятия решения выступает трёхслойный персептрон с 136 нейронами на входном слое, 16 нейронами на промежуточном и 2 нейронами на выходном слое. Персептрон обучался методом обратного распространения ошибки, длительность обучения составила 300 эпох. После успешного обучения нейросети экспертным путём было сформировано множество запрещённых комбинаций фактов С_х и применён алгоритм генерации тестов. Сгенерированное тестовое множество позволило выявить ошибки нейросетевой ЭС типа «забывание об исключении», связанные с установкой комбинаций фактов.