Алгебраический подход к задаче распознавания

Выше рассмотрены алгоритмы распознавания: детерминированные алгоритмы, основанные на проведении в признаковом пространстве решающей границы (границы, разделяющей классы и представляющей собой некоторую гиперповерхность или гиперплоскость), вероятностные алгоритмы, основанные на теории статистических решений, алгоритмы вычисления оценок (АВО), логические алгоритмы, базирующиеся на алгебре логики, и, наконец, структурные (лингвистические) алгоритмы.

Наличие различных алгоритмов распознавания поставило вопрос о выборе в каждой конкретной ситуации наилучшего алгоритма. Эта задача была сформулирована академиком РАН Ю. И. Журавлевым, предложившим и подход к ее решению, который получил название алгебраического подхода к решению задач распознавания и классификации [32, 33 и др.]. Рассмотрим его суть. Прежде всего обратим внимание на следующее. Когда на вход системы распознавания поступает неизвестный объект, подлежащий распознаванию, то процедура его отнесения к соответствующему классу безотносительно к используемому алгоритму распознавания может быть подразделена на два этапа.

Этап 1. Вычисляется мера близости неизвестного объекта с каждым классом (в логических алгоритмах значения поизнаков неизвестного объекта подставляются в логические уравнения, описывающие классы).

Этап 2. В соответствии с тем или другим правилом (выбранным порогом) на основании информации, полученной на этапе 1, принимается окончательное решение о принадлежности неизвестного объекта соответствующему классу.

Так, применительно к вероятностным алгоритмам на этапе 1 вычисляются апостериорные вероятности где a_N — событие, состоящее в том, что у неизвестного объекта со значения признаков равны, т. е. x₁=x⁰₁,..., x_N=x_N⁰, i = l,..., m. На этапе 2 в зависимости от избранного критерия на основании сравнения величин принимается окончательное решение вида, например,

Соответственно этим этапам распознавания любой алгоритм распознавания может быть представлен в виде двух последовательно выполняемых алгоритмов В и С. Алгоритм В переводит исходную информацию об объектах общим числом q в числовую матрицу размерности qxm, где m — число классов. Применительно к вероятностным алгоритмам элементами матрицы являются апостериорные вероятности отнесения каждого объекта к соответствующему классу. Алгоритм С — «решающее правило» — переводит полученную матрицу в матрицу ответов, составленных из символов 1, 0, ´ (1 — объект относится к данному классу, 0 — объект не относится к данному классу, ´ — не установлено, относится объект к данному классу или не относится), имеющую ту же размерность.

Алгоритм В при алгебраическом подходе называют распознающим оператором. С распознающими операторами можно производить некоторые алгебраические операции (сложения, умножения и умножения на число), позволяющие расширять их совокупность. Даже если в исходном семействе распознающих алгоритмов отсутствует алгоритм, правильно решающий задачу распознавания, то искомый, правильно решающий задачу распознавания алгоритм в алгебраическом расширении существует и может быть записан в явном виде [33]. Таково содержательное описание алгебраического подхода решению задач распознавания.

Рассмотрим формальную постановку этого подхода. Пусть дана исходная (обучающая) совокупность объектов известны классы к которым относятся эти объекты, а также группа неизвестных объектов, подлежащих распознаванию, — {w _l,..., w_q}. Любой из выбранных распознающих операторов, будучи применен к исходной совокупности объектов, позволяет получить матрицу ответов (информационную матрицу) вида

(9.37)

Элементы матрицы a_ji=1,..., q; i=1,..., m, применительно к вероятностным алгоритмам соответственно равны a_ji=Р (Ω_i|a^j_N)', где a^j_N — событие, состоящее в том, что у объекта w_j признаки приняли значение {x₁=x₁⁰,..., x_N=x_N⁰}_j.

Введем в рассмотрение произвольные фиксированные положительные числа d₁ и d₂ (пороги), при этом 0<d₁<d₂. Тогда с помощью алгоритма С матрица (9.37) может быть представлена в виде

(9.38)

Над распознающим оператором можно проводить операции:

сложения

умножения

(при перемножении распознающих операторов используется не стандартное, а поэлементное (адамарово) перемножение соответствующих матриц); умножения на число

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

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

где d₁ и d₂ — пороги; l_ji — константы; B_ji — распознающие операторы; k_ji — степень операторного многочлена (порядок алгебраического замыкания),

Для определения величин d_1, d₂ и l _ji и k_ij алгебраический подход к задачам распознавания предлагает использовать специально разработанные алгоритмы обработки исходной априорной информации.

Алгебраический подход в настоящее время находится в стадии интенсивного развития, однако полученные результаты свидетельствуют о том, что распознающие операторы, которые могут быть определены в рамках этого подхода на основе специально разработанных процедур (алгоритмов), обеспечивают эффективное решение традиционной задачи теории распознавания — определения решающего правила (решающих границ), обеспечивающего (в условиях заданного алфавита классов и словаря признаков) правильное решение задачи распознавания неизвестных объектов и явлений.