Формальное определение последовательной процедуры

Пусть рассматриваются образы, описание каждого из которых может быть представлено вектором x = (x ₁, x ₂,..., x_m), где x ₁, x ₂,..., x_m — целые числа, причём i -я компонента — значений i -го измерения в диапазоне от 1 до v_i. Множество всех возможных описаний составляет пространство описаний D. Существует конечное множество классов { C_j }, j = 1,..., c, таких, что каждый объект принадлежит точно одному из них. Класс задаёт распределение вероятностей
P(x | C_j) на множестве D. При этом предполагается, что все классы различны, т.е. для каждой пары классов C_i и C_j найдётся хотя бы один образ x ∈ D, для которого будет выполнено

P(x | C_i) ≠ P(x | C_j).

До начала процедуры последовательного распознавания система не знает ничего о входном образе. По мере прохождения дерева решений на каждом шаге появляется знание о значении очередной компоненты описания образа. На каждом шагу можно фиксировать получаемые факты о рассматриваемом образе в виде упорядоченной последовательности.

Такую последовательность описаний длины v (v < m) определим как упорядоченное множество S_v (y) пар целых чисел. i -я пара (a, b) в последовательности свидетельствует о том, что на i -м шаге анализа значение
a -й компоненты описания образа было определено как b. При этом любая последовательность описаний не содержит пар с одинаковыми a -компонентами, т.е. каждое измерение образа выполняется только один раз. Можно утверждать, что каждый узел дерева решений будет иметь единственную соответствующую ему последовательность описаний образа как единственный путь к этому узлу из корня дерева.

Правилом последовательного распознавания R назовём множество пар
{(S_v (y), C_j)}, каждая из которых ставит в соответствие некоторой последовательности описания образа один из возможных классов. Каждая последовательность из R описывает один путь из корня дерева решений к одному из листовых узлов. Заметим, что все последовательности в R должны начинаться с пар, имеющих одинаковые первые элементы.

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