РАЗДЕЛ 2
МЕТОДИКА И МЕТОДЫ ИССЛЕДОВАНИЯ
В основе дедуктивных вычислений лежит последовательный принцип организации вычислений. При доказательстве конкретной теоремы образуется цепочка истинных утверждений, которая начинается аксиомой и заканчивается выводимой теоремой. Промежуточные утверждения получаются на основе дедуктивных правил по типу "modus ponens" или метода резолюций [33]. При доказательстве конкретной теоремы нельзя заранее оценить длину этой цепочки. Скажем, знаменитая теорема Ферма будоражила умы математиков на протяжении трех столетий и, наконец, была решена Э.Уайлсом в 1995 г. Дедуктивные правила вывода имеют высокую сложность и низкую эффективность. Так, алгоритм Британского музея, который последовательно порождает все возможные выводы, может быть эффективнее известного метода резолюций [33].
В дедуктивной математике объекты и явления природы изучаются с помощью математических моделей. Эти модели формируются на основе известных уравнений о причинно-следственных связях между переменными или признаками объекта. Процесс наблюдений или экспериментов определяет конкретные значения переменных. Если не удается получить аналитическое решение задачи, то поиск точного решения строится в виде последовательной цепочки приближений.
Индуктивный подход кардинально отличается от дедуктивного: он не требует знания уравнений причинно-следственных связей. В индуктивном подходе невозможно получить точные значения интересующих нас характеристик объекта или предсказать исход следующего эксперимента, поскольку известна информация только о конечном числе наблюдений и исходов предыдущих экспериментов. В этом смысле не выполняется основная догма дедуктивной математики - получение точного решения. Индуктивные процедуры дают приближенное решение задачи, зато решение получается за один шаг вычислений. Как и в квантовой механике нужно привлекать вероятностный аппарат. Индуктивные процедуры, как и квантовые вычисления по своей природе являются вероятностными. В квантовой механике невозможно заранее прогнозировать исход отдельного эксперимента (он объективно является случайным), остается только прогнозировать среднее число результатов большого количества экспериментов.
Общая методика исследований в диссертации основана на теории сложности процедур индуктивного вывода, разработанной в [4,7]. Развиваемый подход проводится с позиций решения задач распознавания или обучения.
2.1. Постановка задачи
Изучение природных объектов проводится на основе измерений с помощью различных измерительных устройств или приборов. Для наблюдаемого объекта строится его описание в виде вектора
...
Здесь - измерения объекта, а - исход эксперимента или значение интересующей нас характеристики. Например, в медицине - результаты анализов, а - состояние пациента (болен или здоров). В задачах распознавания эти величины называют признаками. В начале рассмотрим булев случай, когда каждый признак и исход эксперимента принимают два значения 0 или 1. Пусть мы провели наблюдений над объектами и в каждом случае зафиксировали исход эксперимента. Таким образом, у нас есть таких описаний объектов, все они составляют обучающую выборку следующего вида:
......
1
Рис.2.1 Обучающая выборка
Здесь - размер класса 0; - размер класса 1;
- число описаний объектов.Структура и способ получения обучающей выборки описаны ниже.
Индуктивный шаг. Требуется построить такую процедуру индуктивного вывода, которая по измерениям любого следующего - го объекта и обучающих выборок и определяет исход эксперимента . В индуктивном подходе невозможно получить точное значение , т.к. известна информация только о конечном числе наблюдений над объектами.
Основная проблема в естественных науках - уметь предсказывать исходы наблюдений, для любых измерений объекта , эксперименты в них недешевы и часто проводятся в реальном масштабе времени. Для решения этой проблемы нужны эффективные процедуры индуктивного вывода, обладающие полиномиальными оценками погрешности.
Отметим следующий основной момент: нужно отличать объекты от их описаний, на самом деле это разные понятия. Легко заметить, что для точного описания объектов может понадобиться большое число измерений, не исключено, что и бесконечное. При изучении объектов на основе конечного числа измерений, вектору может соответствовать несколько значений , например, один и тот же вектор может соответствовать как больному, так и здоровому пациенту.
Чтобы различать такие описания объектов, нужно на множестве всех описаний объектов ввести некоторое распределение вероятностей , которое нам заранее неизвестно.
2.2. Необходимые понятия: класс задач, процедура обучения, погрешность процедуры, обучающая выборка
Для того чтобы изучить вопрос об эффективности индуктивного подхода к решению описанной задачи, а также сложность подобных задач, необходимо формализовать такие понятия, как класс задач, наилучшая функция распознавания, процедура распознавания, погрешность процедуры, обучающие выборки и их вероятностные распределения.
Число булевых векторов , где , равно . Они образуют множество описаний объектов . Назовем функцией распознавания функцию , определенную на множестве булевых векторов и принимающую значения во множестве . Известно, что число (мощность) таких функций равно числу подмножеств множества , которое составляет [34].
Считаем, что процесс распознавания целевого признака объекта по известным значениям вектора входа проводится с помощью функции , т.е. полагаем . Функцию целесообразно выбрать так, чтобы как можно большим было значение , т.е.
.
Известно, что среди функций существует в определенном смысле наилучшая функция , такая, что среди всех и выполняется неравенство . Ее можно получить лексикографическим упорядочиванием функций по знач