Software & Systems

Индуктивное формирование знаний (ИФЗ) на основе эмпирических данных является основным способом получения новых эмпирических знаний в науке и практике. Он заключается в получении общего знания или базы знаний (БЗ) о некотором классе объектов на основании анализа единообразного описания отдельных представителей этого класса – выборки данных. БЗ представляет собой предикат, который для одних объектов области определения истинен, для других ложен. Объекты, для которых значение БЗ истинно, называются примерами, а их конечная совокупность – выборкой примеров. Объекты, для которых это значение ложно, называются контрпримерами, а их конечная совокупность – выборкой контрпримеров. Выборка, на основе которой осуществляется индуктивное формирование БЗ, называется обучающей. Выборка, на основе которой проводится оценка БЗ, называется контрольной. Таким образом, в задаче ИФЗ по конечному числу объектов, описанных обучающей выборкой, состоящей из примеров и контрпримеров, необходимо найти предикат, который истинен на возможно большем числе примеров и ложен на возможно большем числе контрпримеров контрольной выборки.

Методы ИФЗ и их свойства

ИФЗ как способ познания лежит в основе многих направлений исследований, получивших в англоязычной литературе названия Machine Learning (машинное обучение), Data Mining (анализ данных), Knowledge Discovery in Databases (обнаружение знаний в базах данных), Pattern Recognition (распознавание образов) и т.д., каждое из которых характеризуется собственным подходом к проблеме ИФЗ, собственными постановками задач и методами их решения (см. работы Вагина В.Н., Загоруйко Н.Г., Финна В.К.).

Методы ИФЗ можно разделить на проблемно-независимые (методы, в основе которых лежат абстрактные математические модели ИФЗ) и проблемно-ориентированные (методы, в основе которых лежат модели ИФЗ, существенно использующие зависимости и законы предметной области (ПО) или узкого класса ПО). При решении прикладных задач возникает необходимость выбора наиболее подходящего метода ИФЗ и формирование выборки достаточного объема. Такой выбор должен осуществляться исходя из условий и ограничений задачи, а также из известных значений свойств методов ИФЗ.

Наиболее важным свойством метода ИФЗ является функция, представляющая зависимость процента дефектов БЗ от объема выборки. Если процент дефектов БЗ с увеличением объема выборки уменьшается, то тогда имеет место сходимость метода. При исследовании качества интерес представляет вид функции, ее асимптотика и то, как она ведет себя на всей области определения. Причина в том, что в разных приложениях и объем выборки может быть разным. Другим важным свойством метода ИФЗ является функция, представляющая зависимость времени ИФЗ от объема выборки. Знание вида этой функции и ее асимптотики важно тогда, когда метод имеет высокую вычислительную сложность. В этом случае необходимо установить предельный объем выборки, на котором время формирования знаний не выйдет за пределы имеющихся у исследователя вычислительных ресурсов.

Устойчивость значений свойств метода на выборках различного объема является определяющей характеристикой свойств метода ИФЗ. Свойство метода устойчиво относительно разных выборок одной и той же ПО, если значения этого свойства близки на разных выборках (этой ПО) одного и того же объема, причем чем больше объем выборок, тем эти значения ближе. Свойство метода устойчиво относительно свойств разных ПО, если значения этого свойства близки на разных выборках (взятых из различных ПО) одного и того же объема, причем чем больше объем выборок, тем эти значения ближе.

Теоретическое исследование свойств методов ИФЗ обычно неэффективно, поэтому предпочтительным становится их экспериментальное изучение. Экспериментальные исследования свойств методов ИФЗ проводятся либо на реальных данных, либо на данных из репозитариев, либо на модельных данных.

Оценки свойств методов ИФЗ строятся из оценок индуктивно сформированных БЗ (ИФБЗ), полученных с помощью этих методов, – оценок их качества и времени, затраченного на их получение на конкретных выборках. Таким образом, оценка метода ИФЗ – это функция, а оценка ИФБЗ – значение этой функции в точке. Если известно достаточно много значений функции в точках, то можно понять, какой вид имеет эта функция. Среди оценок значений таких функций в точке выделяют: оценку качества ИФБЗ, оценку времени, затраченного на ее получение на конкретных выборках, а также сравнительную оценку.

Оценки качества ИФБЗ могут быть двух видов – внешние и внутренние. Внешняя оценка представляет собой оценку ошибок 1-го и 2-го рода, то есть оценку числа дефектов ИФБЗ на контрольной выборке. Ошибкой 1-го рода считается несоответствие примера из выборки примеров ИФБЗ. Ошибкой 2-го рода считается соответствие контрпримера из выборки контрпримеров ИФБЗ. Внутренняя оценка является оценкой близости ИФБЗ к “идеальной” БЗ (к знаниям о том, как в действительности устроен мир).

Внутренняя оценка может быть экспертной или автоматической. Если ИФБЗ понятна эксперту ПО, тогда такая оценка применима. Более того, она значительно предпочтительнее формального критерия близости, так как эксперт в первую очередь обращает внимание на важные вещи. При этом его “идеальная” БЗ не обязательно должна быть явно представлена. Оценка близости в этом случае – содержательный комментарий: что в ИФБЗ упущено из-за недостаточно репрезентативной выборки, какие новые знания обнаружил метод ИФЗ и т.д. Если ИФБЗ не понятна эксперту, необходимо сформулировать формальный критерий близости, то есть некий набор правил, проверка которых осуществлялась бы автоматически.

Сравнительная оценка – это кортеж внешних оценок нескольких ИФБЗ, полученных с помощью различных методов ИФЗ на одних и тех же выборках. Если для методов от 1 до n известна оценка некоторого свойства метода ИФЗ и разработан некий новый метод ИФЗ i, то сравнительная оценка позволяет найти место его оценки в кортеже.

Постановка задачи экспериментальногоисследования свойств методов ИФЗ

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

Однако на практике свойства метода ИФЗ чаще всего изучаются на одной сравнительно небольшой выборке реальных данных. Часто это изучение ограничивается лишь оценкой процента ошибок 1-го рода ИФБЗ или сравнительной оценкой свойств методов ИФЗ и их устойчивости на небольшом количестве выборок небольшого объема из какого-либо репозитария. Таким образом, изучение свойств метода (то есть функций, зависящих от объема выборки) заменяется изучением одного значения лишь одной функции в одной точке, обычно далекой от асимптотики. Кроме единственной попытки (Michalski R.S.), внутреннее качество ИФБЗ вообще не исследуется. Важность же таких исследований состоит в том, что, какие бы внешние оценки метода ИФЗ не были бы получены, у пользователя ИФБЗ без исследования ее внутреннего качества нет полной уверенности в том, что этот метод действительно восстанавливает знания ПО.

Из вышесказанного следует, что существует потребность в общем подходе к экспериментальному исследованию свойств методов ИФЗ. В подобных исследованиях для каждого метода необходимо определить:

· зависимость качества ИФБЗ от объема и сложности выборки (сложности примеров и контрпримеров), а также от сложности модели ПО (количества классов, признаков и их значений);

· зависимость времени ИФЗ от объема и сложности выборки, а также от сложности модели ПО для таких методов ИФЗ, для которых на выборках практически важного объема время вычислений может быть велико;

· характеристики устойчивости значений свойств метода ИФЗ (качества ИФБЗ и времени ИФЗ) относительно выборок одной ПО и относительно свойств разных ПО – для проблемно-независимых методов.

Исходными данными таких исследований должны быть множество выборок различного объема для одной и той же ПО (для проблемно-ориентированных и проблемно-независимых методов ИФЗ) и множество выборок различного объема для разных ПО (для проблемно-независимых методов ИФЗ).

Общий подход к исследованию свойствметодов ИФЗ

По указанным выше причинам использование реальных данных в полноценном исследовании свойств методов ИФЗ ограничено. Поэтому такие исследования целесообразно проводить на модельных данных, а затем, используя полученную в подобных исследованиях информацию, применять метод ИФЗ к выборкам реальных данных (такого объема, который имеется в распоряжении исследователя) и с учетом его свойств интерпретировать оценки полученных ИФБЗ. На основе информации об устойчивости свойств метода можно сделать вывод о том, какова возможная погрешность оценок ИФБЗ на имеющейся выборке и насколько ИФБЗ может быть близка к “идеальной” БЗ. Если эти оценки ИФБЗ окажутся неприемлемыми, можно прогнозировать, каково будет время работы метода при увеличении объема выборки и насколько этот объем необходимо увеличить для достижения приемлемой оценки. Если результаты, полученные на модельных данных, не соответствуют результатам, полученным на реальных данных, то можно косвенно судить о том, что предположения о ПО, лежащие в основе метода ИФЗ, в данном случае не выполняются.

Перейдем к описанию общего подхода. Введем следующие обозначения. Пусть M – множество БЗ; mÎM – некоторая БЗ; O – множество объектов. Тогда обозначим O(m)ÌO – множество примеров; O\O(m) – множество контрпримеров для БЗ mÎM. Пусть V – множество выборок; vÎV – конкретная выборка (конечное множество объектов – элементов O), vÌO.

В основе любого метода ИФЗ лежит некоторый класс БЗ (моделей) M. Метод ИФЗ решает обратную задачу вычисления значения некоторого отображения V→M, то есть на основе имеющейся выборки v метод выбирает одну из БЗ m*(v). Идея предлагаемого общего подхода состоит в том, чтобы для получения модельных данных, необходимых для экспериментальных исследований свойств метода ИФЗ, явно представить классБЗ M. Далее на основе этого явного представления разработать алгоритмы решения следующих прямых задач: случайного выбора (или генерации) БЗ m из M; случайной генерации выборок модельных данных v(m) различного объема на основе БЗ m; каждая из таких выборок v(m) представляет собой объединение выборки примеров vп(m)ÌO(m) и выборки контрпримеров vкп(m) ÌO\O(m).

После этого в процессе экспериментального исследования, применяя метод ИФЗ к сгенерированным выборкам модельных данных v(m) разного объема, можно получать различные ИФБЗ

m*(v) и, используя их оценки, получать оценки свойств метода ИФЗ: внешнего и внутреннего качества, времени работы, а также устойчивости в зависимости от объема выборок. При этом оценка внешнего качества ИФБЗ – это оценка процента ошибок 1-го рода m*(v) на контрольной vп(m) и оценка процента ошибок 2-го рода m*(v) на контрольной vкп(m). Первая представляет собой долю элементов vп(m), соответствующих ИФБЗ m*(v), от объема vп(m), вторая – долю элементов vкп(m), не соответствующих ИФБЗ m*(v), от объема vкп(m). Оценка внутреннего качества – это оценка сходства m и m*(v). Оценка устойчивости может быть получена с помощью генерации выборок различного объема и анализа разброса значений свойства метода ИФЗ для этих выборок.

Таким образом, предлагаемый подход свободен от трудностей, связанных с экспериментальными исследованиями свойств методов ИФЗ на реальных данных, и позволяет проводить подобные исследования на большом числе выборок различного объема. Результаты экспериментальных исследований методов ИФЗ (значения свойств этих методов на различных объемах выборок) могут быть использованы в качестве наполнения каталога свойств методов ИФЗ, в котором явно приведены их свойства и значения этих свойств для каждого метода.