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