Журнал вычислительной математики и математической физики, 2019, T. 59, № 9, стр. 1605-1616

1.1. Модели логических классификаторов, основанные на голосовании по корректным эл.кл.

Считается, что каждый распознающий алгоритм A на этапе обучения строит для каждого класса K некоторое множество корректных эл.кл. C^A(K). Распознавание объекта S осуществляется на основе вычисления величины B(σ, S, H) для каждого построенного эл.кл. (σ, H), т.е. каждый элемент множества C^A(K), K ∈ {K₁, …, K_l}, участвует в процедуре голосования. В результате для класса K вычисляется оценка Γ(S, K) принадлежности объекта S классу K. Таким образом, алгоритм A из рассматриваемого семейства распознающих алгоритмов определяется множествами C^A(K₁), …, C^A(K_l). Алгоритмы отличаются и способом вычисления оценки Γ(S, K). Рассмотрим основные модели.

В общем случае элементарный классификатор (σ, H), по отношению к классу K может обладать одним из следующих трех свойств: 1) каждый обучающий объект из класса K содержит (σ, H); 2) не все, а лишь некоторые обучающие объекты из класса K содержат (σ, H); 3) ни один обучающий объект из класса K не содержит (σ, H).

Первый случай встречается крайне редко, поэтому работать с эл.кл. первого типа не представляется возможным. Во втором и третьем случаях аргументом за отнесение распознаваемого объекта S в класс K считается ситуация, когда распознаваемый объект S соответственно содержит (σ, H) и не содержит (σ, H).

Корректный эл.кл. второго типа называется представительным эл.кл. класса K. Представительный для класса K эл.кл. (σ, H) называется тупиковым представительным эл.кл. класса K, если не является представительным для K любой эл.кл. вида (σ', H  '), где σ' = (${{\sigma }_{1}}, \ldots ,{{\sigma }_{{t - 1}}},{{\sigma }_{{t + 1}}}, \ldots ,{{\sigma }_{r}}$), H  ' = $H{\backslash \{ }{{x}_{{{{j}_{t}}}}}{\text{\} }}$, t ∈ {1, 2, …, r}.

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

В рассматриваемом случае эл.кл. (σ, H), H = {${{x}_{{{{j}_{1}}}}}, \ldots ,{{x}_{{{{j}_{r}}}}}$}, σ = (${{\sigma }_{1}}, \ldots ,{{\sigma }_{r}}$), – это элементарная конъюнкция (ЭК) B над переменными x₁, …, x_n вида $x_{{{{j}_{1}}}}^{{{{\sigma }_{1}}}} \wedge \ldots \wedge x_{{{{j}_{r}}}}^{{{{\sigma }_{r}}}}$, которая обращается в 1 на описании объекта S, если объект S cодержит эл.кл. (σ, H), т.е. описание объекта S принадлежит интервалу истинности N_B конъюнкции B.

Пусть f_K(x₁, …, x_n) – частичная булева функция, определенная на описаниях объектов обучающей выборки и принимающая значение 1 только на описаниях обучающих объектов из K. Пусть ${{N}_{{{{{\bar {f}}}_{K}}}}}$ – множество булевых наборов, на которых f_K принимает значение 0. ЭК B называется допустимой для f_K, если ${{N}_{B}} \cap {{N}_{{{{{\bar {f}}}_{K}}}}} = \not {0}$. ЭК B называется максимальной для функции f_K, если не существует допустимой для f_K ЭК B ' такой, что ${{N}_{{B'}}} \subset {{N}_{B}}$.

Нетрудно видеть, что представительный эл.кл. класса K – это допустимая конъюнкция для функции  f_K. Тупиковый представительный эл.кл. для класса K – это максимальная конъюнкция для  f_K.

Набор признаков H называется тестом, если в каждом классе K, K ∈ {K₁, …, K_l}, каждый прецедент содержит представительный для K эл.кл. вида (σ, H). Тест называется тупиковым, если любое его собственное подмножество тестом не является.

Эл.кл. третьего типа называется покрытием класса K. Покрытие (σ, H) класса K называется тупиковым покрытием класса K, если не является покрытием для K любой эл.кл. вида (σ', H  '), где σ' = ${{\sigma }_{1}}, \ldots ,{{\sigma }_{{t - 1}}},{{\sigma }_{{t + 1}}}, \ldots ,{{\sigma }_{r}}$), H  ' = $H{\backslash }\{ {{x}_{{{{j}_{t}}}}}\} $, t ∈ {1, 2, …, r}.

Переформулируем понятие представительного эл.кл. класса K, используя понятие покрытия класса. Пусть $\bar {K}$ = M\K. Будем рассматривать $\bar {K}$ как отдельный класс, т.е. будем считать, что у нас всего два класса K и $\bar {K}$. Тогда, как нетрудно видеть, (тупиковый) представительный эл.кл. является (тупиковым) покрытием для класса $\bar {K}$ и не является покрытием для класса K.

Модели тестовых алгоритмов и алгоритмов голосования по представительным эл.кл. основаны на построении для каждого класса K множества представительных эл.кл. этого класса C^A(K). В простейших модификациях этих моделей число голосов, поданных эл.кл. из C^A(K) за принадлежность объекта S к классу K, вычисляется по формуле

В моделях голосования по (тупиковым) покрытиям класса множество C^A(K) состоит из (тупиковых) покрытий класса K. Эл.кл. из C^A(K) голосует за принадлежность распознаваемого объекта классу K, если этот эл.кл. не встречается в описании распознаваемого объекта S. Принадлежность объекта S классу K в простейшей модификации оценивается величиной

Сравнение описанных выше моделей по качеству распознавания приведено в [5]. Наиболее информативными являются эл.кл. небольшого ранга. Поэтому при решении прикладных задач, как правило, либо ограничивают ранг эл.кл., либо рассматривают только тупиковые корректные эл.кл. (при этом не обязательно все). Например, алгоритм КОРА, предложенный в [2], использует эл.кл. с рангом меньшим или равным трем. Модель голосования по покрытиям класса выигрывает по скорости счета, если число прецедентов из K существенно меньше числа прецедентов из $\bar {K}$.

1.2. Логические корректоры

В задачах с большой значностью признаков, как правило, почти все корректные эл.кл. имеют большой ранг и, как следствие, каждый такой эл.кл. содержится в небольшом числе прецедентов. При этом под значностью признака понимается число его различных значений и вещественнозначные данные часто трактуются как целочисленные высокой значности. Задачи, в которых значность признаков слишком большая, сложны для классических логических алгоритмов распознавания. Существуют различные способы решения этой проблемы. Один из этих способов основан на идеях алгебраического подхода [16] и базируется на использовании произвольных эл.кл. (не обязательно корректных эл.кл.). Алгебраический подход применяется тогда, когда требуется скорректировать работу нескольких алгоритмов, каждый из которых безошибочно классифицирует лишь часть обучающих объектов. Цель коррекции – сделать так, чтобы ошибки одних алгоритмов были скомпенсированы другими алгоритмами. И качество результирующего алгоритма оказалось лучше, чем качество каждого из базовых алгоритмов в отдельности. Об алгебро-логическом подходе говорят, когда каждый базовый алгоритм однозначно определяется некоторым эл.кл. и корректирующие функции являются булевыми [7]–[9]. Оценки принадлежности распознаваемого объекта к классам вычисляются с использованием процедуры голосования по корректным наборам эл.кл.

Рассмотрим набор эл.кл. U = {(${{\sigma }_{1}},{{H}_{1}}$), …, (${{\sigma }_{t}},{{H}_{t}}$}. Бинарный вектор U(S) = (${{q}_{1}}(S), \ldots ,{{q}_{t}}(S)$), в котором q_i(S) = B(σ_i, S, H_i) при i ∈ {1, 2, …, t}, называется откликом набора U на объекте S. Очевидно, что набор эл.кл. U является корректным для класса K тогда и только тогда, когда не существует двух прецедентов с одинаковыми откликами, один из которых принадлежит K, а другой K не принадлежит. Очевидно также, что для корректного для класса K набора эл.кл. U всегда существует частичная булева функция ${{F}_{{U,K}}}$, выполняющая роль корректирующей. Функция ${{F}_{{U,K}}}$ определена на откликах прецедентов и принимает значение 1 только на откликах прецедентов из K.

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

Утверждение 1. Набор эл.кл. U является монотонным корректным набором для класса K тогда и только тогда, когда для любых двух обучающих объектов S  ' и S  '', S  ' ∈ K, S  '' $ \notin $ K, в наборе U можно указать эл.кл. (σ, H) такой, что B(σ, S  ', H) = 1, B(σ, S  '', H) = 0.

Заметим, что если набор эл.кл. U является монотонным корректным набором для класса K и состоит из одного эл.кл. (σ, H), то (σ, H) – представительный эл.кл. для класса K. Набор признаков H, являющийся тестом, порождает для каждого класса K корректный набор эл.кл., в котором каждый эл.кл. – представительный эл.кл. для K, имеющий вид (σ, H).

Логический корректор на этапе обучения для каждого класса K строит семейство W_K, состоящее из корректных для K наборов эл.кл. Далее осуществляется голосование по наборам из семейства W_K. Корректность классификации обеспечивается за счет корректности каждого голосующего набора эл.кл.

Распознавание объекта S по корректному набору эл.кл. U класса K осуществляется следующим образом. Для каждого объекта S  ' из обучающей выборки, принадлежащего классу K, выписывается вектор U(S  '), который сравнивается с вектором U(S) (сравниваются отклики набора U на объектах S и S  '). Далее запись U(S  ') $ \preccurlyeq $ U(S) означает, что каждая координата вектора U(S  ') не превосходит соответствующую координату вектора U(S) . Объект S не получает голос за принадлежность классу K, если не выполнено U(S  ') $ \preccurlyeq $ U(S). Если U – монотонный корректный набор эл.кл. класса K и U(S  ') $ \preccurlyeq $ U(S), то объект S получает голос за принадлежность классу K. Если же U не является монотонным корректным набором эл.кл. класса K, то S получает голос за принадлежность к классу K только в случае U(S  ') = U(S).

На практике проверено, что целесообразно использовать корректные наборы эл.кл. небольшой длины, в частности, тупиковые. Корректный набор эл.кл. для класса K называется тупиковым, если любое его собственное подмножество не является корректным для K набором эл.кл. Решение прикладных задач показывает, что монотонный логический корректор (логический корректор, использующий только монотонные корректные наборы эл.кл.) работает лучше немонотонного логического корректора.

На этапе построения семейств корректных наборов эл.кл. также, как и при построении логических процедур классификации, основанных на голосовании по корректным эл.кл., приходится решать сложные дискретные задачи, среди которых центральное место принадлежит задаче монотонной дуализации. Как правило, используется матричная формулировка монотонной дуализации и поиск искомых корректных эл.кл. или корректных наборов эл.кл. сводится к поиску неприводимых покрытий булевой матрицы, которая специальным образом строится по обучающей выборке. В [17] показано, что при поиске корректных эл.кл. можно обойтись без построения вспомогательной булевой матрицы, если ввести понятие (тупикового) покрытия целочисленной матрицы.

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

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

В [9] предложена общая схема синтеза корректных логических процедур классификации, в рамках которой описаны алгоритмы голосования по корректным эл.кл. и существующие логические корректоры. В этой же работе построен и исследован логический корректор с поляризуемой булевой функцией в качестве корректирующей. Монотонная булева функция является частным случаем поляризуемой булевой функции.

2. ЛОГИЧЕСКИЙ АНАЛИЗ ДАННЫХ С ЧАСТИЧНЫМИ ПОРЯДКАМИ. ЗАДАЧИ ПОИСКА МАКСИМАЛЬНЫХ И МИНИМАЛЬНЫХ НЕЗАВИСИМЫХ ЭЛЕМЕНТОВ ПРОИЗВЕДЕНИЯ ЧАСТИЧНЫХ ПОРЯДКОВ

В данном разделе введены основные понятия логического анализа данных с частичными порядками, и сформулированы две центральные задачи такого анализа, а именно, задача поиска максимальных независимых элементов произведения частичных порядков и задача поиска минимальных независимых элементов произведения частичных порядков, простейшим частным случаем которой является задача монотонной дуализации.

Пусть P = P₁ × … × P_n, где P₁, …, P_n – конечные частично упорядоченные множества. Считается, что элемент y = (y₁, …, y_n) ∈ P следует за элементом x = (x₁, …, x_n) ∈ P (x предшествует y), если y_i следует за x_i (x_i предшествует y_i) при i = 1, 2, …, n. Для обозначения того, что y ∈ P следует за x∈ P (x предшествует y) далее используется запись x $ \preccurlyeq $ y или y $ \succcurlyeq $ x. Запись x $ \prec $ y (y $ \succ $ x) означает, что x $ \preccurlyeq $ y и y ≠ x. Элементы x,y ∈ P называются сравнимыми, если либо x $ \preccurlyeq $ y, либо y $ \preccurlyeq $ x. В противном случае x и y называются несравнимыми.

Пусть R $ \subseteq $ P. Введем обозначения: ${{R}^{ + }} = R \cup \{ x \in \left. P \right|\exists a \in R,\;a \prec x\} $ – множество элементов, следующих за элементами из R; ${{R}^{ - }} = R \cup \{ x \in \left. P \right|\exists a \in R,\;x \prec a\} $ – множество элементов, предшествующих элементам из R.

Элемент x множества $P{\backslash }{{R}^{ + }}\;(P{\backslash }{{R}^{ - }})$ называется максимальным (минимальным) независимым от R элементом множества P, если для любого другого элемента y множества $P{\backslash }{{R}^{ + }}\;(P{\backslash }{{R}^{ - }})$ отношение x $ \prec $ y (y $ \prec $ x) не выполняется.

Обозначим через $I({{R}^{ + }})$ множество, состоящее из максимальных независимых от R элементов множества P, через $I({{R}^{ - }})$ – множество, состоящее из минимальных независимых от R элементов множества P.

Ставятся задачи построения для заданного R множеств $I({{R}^{ + }})$ и $I({{R}^{ - }})$. Каждую из этих двух задач можно свести к другой путем изменения порядка на обратный.

Одним из наиболее востребованных и изученных является случай, когда множества P₁, …, P_n – цепи, т.е. в каждом из этих множеств любые два элемента сравнимы. Антицепью называется множество, в котором любые два различных элемента несравнимы. Множества $I({{R}^{ + }})$ и $I({{R}^{ - }})$ являются антицепями.

Простейшим случаем дуализации над произведением цепей является монотонная дуализация. Задача формулируется следующим образом.

Дана конъюнктивная нормальная форма (КНФ), реализующая монотонную булеву функцию F(x₁, …, x_n). Требуется построить сокращенную дизъюнктивную нормальную форму (ДНФ) функции F, т.е. ДНФ, состоящую из всех максимальных конъюнкций функции F.

Покажем, что монотонная дуализация – это задача построения минимальных независимых от R элементов множества P при условии, что P – n -мерный булев куб, P_i ={0, 1} при i = 1, 2, …, n, в каждом P_i задан порядок 0 $ \prec $ 1 и R – множество нулей функции F, содержащее множество так называемых “верхних нулей” функции F.

Действительно, пусть E₀ и E₁ – множества вершин n-мерного булева куба P, на которых функция F принимает соответственно значение 0 и 1. Множества I(E₁) и I(E₀) называются соответственно верхними нулями и нижними единицами функции F. Каждое из этих множеств является антицепью. Очевидно, что ${{E}_{0}} = {{(I({{E}_{1}}))}^{ - }}$, ${{E}_{1}} = {{(I({{E}_{0}}))}^{ + }}$. Представление монотонной булевой функции в виде КНФ равносильно заданию множества нулей этой функции, содержащего множество ее верхних нулей. Задание множества нижних единиц монотонной булевой функции равносильно заданию ее в виде сокращенной ДНФ. Таким образом, монотонная дуализация – это задача построения $I({{R}^{ - }})$ при $I({{E}_{1}}) \subseteq R \subseteq {{E}_{0}}$ (в частности, это задача построения нижних единиц монотонной булевой функции, заданной верхними нулями).

Заметим, что если в искомой сокращенной ДНФ функции F заменить знаки & и $ \vee $ соответственно на знаки $ \vee $ и &, то получим КНФ функции dualF. По определению dualF = $\bar {F}$(${{\bar {\alpha }}_{1}}, \ldots {{\bar {\alpha }}_{n}}$) для любого набора (${{\alpha }_{1}}, \ldots ,{{\alpha }_{n}}$). Отсюда название задачи.

Задача монотонной дуализации может быть решена, во-первых, на основе перечисления неприводимых покрытий булевой матрицы, строками которой являются наборы из R, и, во-вторых, на основе перечисления минимальных вершинных покрытий гиперграфа с n вершинами и |R| ребрами [6], [12], [14], [17].

Теоретические оценки эффективности алгоритмов дуализации базируются на оценке сложности одного шага, т.е. сложности поиска одного нового решения. Наиболее эффективным считается алгоритм, имеющий полиномиальный от размера входа шаг. Такой алгоритм называется алгоритмом с полиномиальной задержкой [14]. Однако полиномиальные алгоритмы удалось построить лишь для некоторых частных случаев монотонной дуализации, например, для случая 2-КНФ. В настоящее время сформировались два основных направления исследований.

Первое направление нацелено на построение так называемых инкрементальных алгоритмов, когда алгоритму разрешено просматривать решения, найденные на предыдущих шагах. При этом оценка сложности шага алгоритма дается для худшего случая (для самого сложного варианта задачи). В [18] построен инкрементальный алгоритм дуализации гиперграфа с квазиполиномиальным шагом, определяемым фактически не только размером входа задачи, но и размером ее выхода. В [19] для случая, когда каждое P_i, i = 1, 2, …, n, является цепью и |P_i | ≥ 2, на базе алгоритма, предложенного в [18], построен квазиполиномиальный инкрементальный алгоритм. Подход интересен в основном для теории, поскольку в худшем случае число решений дуализации (размер выхода задачи) растет экспоненциально с ростом размера ее входа.

Второе направление основано на построении асимптотически оптимальных алгоритмов дуализации. В этом случае алгоритму разрешено делать лишние полиномиальные шаги при условии, что их число почти всегда должно быть достаточно мало по сравнению с числом всех решений задачи. В рамках данного направления удалось построить алгоритмы монотонной дуализации, эффективные в типичном случае (эффективные для почти всех вариантов задачи). Эти алгоритмы имеют теоретическое обоснование и являются лидерами по скорости счета [11]–[13]. В [20]–[22] предложен асимптотически оптимальный алгоритм построения $I({{R}^{ + }})$ для случая, когда каждое множество P_i = {0, 1, …, k – 1}, i = 1, 2, …, n, – цепь и элементы в P_i упорядочены по возрастанию. При обосновании асимптотической оптимальности данного алгоритма используется матричная формулировка дуализации над произведением цепей.

3.1. Постановка задачи и основные утверждения

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

На фиг. 1 и 2 представлены модельные примеры, наглядно демонстрирующие преимущество более общей постановки логической классификации. Рассматриваются две задачи классификации, каждая из которых с двумя классами и системой признаков {x₁, x₂}. Обучающие объекты классов K₁ и K₂ изображены соответственно в виде крестиков и в виде кружочков. Множество допустимых значений каждого признака – множество целых чисел.

Фиг. 1.

Фиг. 2.

Рассмотрим первый пример (фиг. 1). Нетрудно видеть, что для любого значения признака x₁ число объектов каждого класса, у которых признак x₁ принимает данное значение, равно четырем. То же верно и для признака x₂. Также нетрудно видеть, что каждый эл.кл. ранга 2 является корректным либо для класса K₁, либо для класса K₂ и что только один объект из обучающей выборки его порождает. Следовательно, любой корректный эл.кл. любого из двух классов обладает низкой информативностью. Такой эл.кл. не порождается ни одним объектом, не входящим в обучающую выборку. Схожая ситуация и со вторым примером (фиг. 2). Существует всего два корректных эл.кл. ранга 1, а именно, эл.кл. ((0), {x₁}) и ((0), {x₂}), и каждый из них порождается лишь несколькими объектами класса K₂.

С другой стороны, если на множестве допустимых значений признаков x₁ и x₂ ввести естественный порядок $ \cdots \preccurlyeq 0 \preccurlyeq 1 \preccurlyeq \cdots $), то решающие правила для обоих примеров становятся простыми. Пусть S = (a₁, a₂) – распознаваемый объект. Тогда решающее правило для первого примера: если (a₁, a₂) $ \preccurlyeq $ (3, 3) или (a₁, a₂) $ \succcurlyeq $ (4, 4), то S ∈ K₁, иначе S ∈ K₂. Решающее правило для второго примера: если (a₁, a₂) $ \preccurlyeq $ (x, 7 – x) для хотя бы одного x ∈ {0, 1, …, 7}, то S ∈ K₂, иначе S ∈ K₁.

Рассмотрим задачу классификации по прецедентам при условии, что на множестве допустимых значений каждого признака задан частичный порядок.

Пусть M = N₁ × … × N_n, где N_i, i ∈ {1, 2, …, n}, – конечное множество значений признака x_i, на котором задан частичный порядок. Будем считать, что каждое множество N_i, i ∈ {1, 2, …, n}, имеет наименьший и наибольший элементы, т.е. такие элементы q_i и k_i, для которых выполнено a $ \succcurlyeq $ q_i и a $ \preccurlyeq $ k_i для любого a ∈ N_i. Если наименьший (наибольший) элемент в N_i отсутствует, то N_i дополним таким элементом.

Близость объекта S = (a₁, …, a_n) из M и эл.кл. (σ, H), H = {${{x}_{{{{j}_{1}}}}}, \ldots ,{{x}_{{{{j}_{r}}}}}$}, σ_i = (${{\sigma }_{1}}, \ldots ,{{\sigma }_{r}}$), ${{\sigma }_{i}} \in {{N}_{{{{j}_{i}}}}}$, при i = 1, 2, …, r, будем оценивать величиной $\hat {B}$(σ, S, H), равной 1, если ${{a}_{{{{j}_{i}}}}} \preccurlyeq {{\sigma }_{i}}$ при i = 1, 2, …, r, и равной 0 в противном случае. Будем говорить, что объект S порождает эл.кл. (σ, H), если $\hat {B}$(σ, S, H) = 1.

Данные в разд. 1 понятия корректного эл.кл. класса K, представительного эл.кл. класса K, покрытия класса K и теста полностью переносятся на рассматриваемый случай, если B(σ, S, H) заменить на $\hat {B}$(σ, S, H).

Пусть (σ, H) – эл.кл., в котором H = {${{x}_{{{{j}_{1}}}}}, \ldots ,{{x}_{{{{j}_{r}}}}}$}, σ = (${{\sigma }_{1}}, \ldots ,{{\sigma }_{r}}$), ${{\sigma }_{i}} \in {{N}_{{{{j}_{i}}}}}$, i = 1, 2, …, r. Эл.кл. (σ, H) сопоставим набор ${{S}_{{(\sigma ,H)}}}$ = (${{\gamma }_{1}}, \ldots ,{{\gamma }_{n}}$) из M = N₁ × … × N_n, в котором ${{\gamma }_{t}} = {{\sigma }_{i}}$ при t = j_i, i = 1, 2, …, r, и ${{\gamma }_{t}} = {{k}_{t}}$ при t $ \notin $ {${{j}_{1}}, \ldots ,{{j}_{r}}$}.

Покрытие (σ, H) класса K назовем тупиковым, если любой эл.кл. (σ', H ') такой, что ${{S}_{{(\sigma ,H)}}} \prec {{S}_{{(\sigma ',H')}}}$, не является покрытием класса K.

Через R(K) обозначим множество прецедентов из класса K. Нетрудно убедиться в справедливости приводимых ниже утверждений 2 и 3.

Утверждение 2. Эл.кл. (σ, H) является покрытием класса K относительно заданного частичного порядка тогда и только тогда, когда ${{S}_{{(\sigma ,H)}}} \in M{\text{/}}R{{(K)}^{ + }}$.

Утверждение 3. Покрытие (σ, H) класса K является тупиковым покрытием класса K относительно заданного частичного порядка тогда и только тогда, когда ${{S}_{{(\sigma ,H)}}} \in I(R{{(K)}^{ + }})$.

Представительный для класса K эл.кл. (σ, H) назовем тупиковым, если любой эл.кл. (σ', H') такой, что ${{S}_{{(\sigma ,H)}}} \prec {{S}_{{(\sigma ',H')}}}$, не является представительным для класса K.

Пусть $\bar {K}$ = M\K. Будем рассматривать $\bar {K}$ как отдельный класс, т.е. будем считать, что есть всего два класса K и $\bar {K}$. Тогда очевидным является

Утверждение 4. Эл.кл. (σ, H) является тупиковым представительным для класса K относительно заданного частичного порядка тогда и только тогда, когда ${{S}_{{(\sigma ,H)}}} \in I(R{{(\bar {K})}^{ + }})$ и ${{S}_{{(\sigma ,H)}}} \in R{{(K)}^{ + }}$.

Из утверждений 3 и 4 следует, что в случае частично упорядоченных данных при построении логических классификаторов, основанных на голосовании по тупиковым покрытиям класса и тупиковым представительным эл.кл. класса, возникает задача построения максимальных независимых элементов произведения частичных порядков.

Заметим, что если описание обучающего объекта S класса K следует за описанием некоторого объекта из $\bar {K}$, то, очевидно, S не порождает ни одного представительного эл.кл. класса K. Поэтому в общем случае существование представительных для класса K эл.кл. не гарантировано и для корректности алгоритма голосования по представительным эл.кл. или тестам необходимо, чтобы описания объектов из разных классов были несравнимы.

Покажем, что в случае непересекающихся классов существует такое преобразование признакового описания множества M, в результате которого для каждого класса K всегда образуется непустое множество тупиковых представительных эл.кл. и любой прецедент из K порождает хотя бы один эл.кл. из данного множества.

Обозначим через $\tilde {P}$ множество, совпадающее с множеством P, но с обратным отношением порядка, т.е. x $ \preccurlyeq $ y в P тогда и только тогда, когда y $ \preccurlyeq $ x в $\tilde {P}$.

Пусть $\tilde {M}$ = ${{\tilde {N}}_{1}} \times \ldots \times {{\tilde {N}}_{n}}$. Зададим отображение φ : M $ \to $ M × $\tilde {M}$ следующим образом. Отображение φ переводит объект S = (a₁, …, a_n) из M в объект φ(S) = (a₁, …, ${{a}_{n}},\;{{a}_{{n + 1}}}, \ldots ,{{a}_{{2n}}}$) из M × $\tilde {M}$, в котором ${{a}_{{i + n}}} = {{a}_{i}}$ при i ∈ {1, 2, …, n}. Иными словами, признаковое описание объекта S дублируется с обратным отношением порядка.

Пусть φ(A), $A \subset M$, – образ A при отображении φ. Имеет место следующая

Теорема 1. Если классы множества M не пересекаются, то любой прецедент из класса φ(K) порождает тупиковый представительный эл.кл. класса φ(K).

Доказательство. Пусть S ∈ R(K). Покажем, что элемент φ(S) не принадлежит $\varphi {{(R(\bar {K}))}^{ + }}$ (независим от φ(R($\bar {K}$)) в φ(M)). Действительно, пусть φ($\bar {S}$) $ \preccurlyeq $ φ(S), $\bar {S}$ ∈ R($\bar {K}$). Тогда имеем: $\bar {S}$ $ \preccurlyeq $ S и S $ \preccurlyeq $ $\bar {S}$. Откуда в силу антисимметричности заданного отношения частичного порядка получаем $\bar {S}$ = S, что противоречит условию $R(K) \cap R(\bar {K}) = \not {0}$. В силу конечности M × $\tilde {M}$ существует максимальный независимый от φ(R($\bar {K}$)) элемент φ(S  ') ∈ M × $\tilde {M}$ такой, что $\varphi (S) \preccurlyeq \varphi (S')$. Отсюда следует утверждение теоремы.

Замечание 1. Отметим, что если каждое множество N_i, i ∈ {1, 2, …, n}, – антицепь с добавленным наибольшим элементом, то $R{{(K)}^{ + }} = R(K)$ и $\hat {B}$(σ, S, H) = B(σ, S, H) и, следовательно, в этом случае мы имеем классическую постановку, рассмотренную в разд. 1.

3.2. О построении $I({{R}^{ + }})$

В [20]–[22] дана матричная постановка задачи дуализации над произведением конечных цепей и построен асимптотически оптимальный алгоритм, решающий данную задачу путем перечисления так называемых упорядоченных тупиковых покрытий целочисленной матрицы.

Ниже приведена матричная формулировка задачи построения максимальных независимых элементов для произведения конечных частичных порядков P, опирающаяся на понятие упорядоченного тупикового покрытия матрицы, строками которой являются наборы из $R \subseteq P$.

Введем обозначения: Q₁(x, P), x ∈ P, – множество всех элементов в P, непосредственно следующих за x (Q₁(x, P) = {y ∈ P: x $ \prec $ y, $\forall a \in P$: }); Q₂(x, y, P), x ∈ P, y ∈ Q₁(x, P), – множество всех элементов a ∈ P, не предшествующих x и предшествующих y (Q₂(x, y, P) = {a ∈ P: }).

Элемент x частично упорядоченного множества P называется максимальным элементом в P, если Q₁(x, P) = $\not {0}$, т.е. для любого y ∈ P либо y $ \preccurlyeq $ x, либо x и y несравнимы.

Пусть P = P₁ × … × P_n и каждое P_i, i ∈ {1, 2, …, n}, – конечное частично упорядоченное множество с наибольшим элементом. В заданных обозначениях введем понятие упорядоченного тупикового покрытия матрицы L_R, строками которой являются наборы из $R \subseteq P$.

Пусть H – набор столбцов матрицы L_R с номерами j₁, …, j_r, σ = (${{\sigma }_{1}}, \ldots ,{{\sigma }_{r}}$) , ${{\sigma }_{i}} \in {{P}_{{{{j}_{i}}}}}$ при i = 1, 2, …, r. Тогда набор столбцов H называется упорядоченным тупиковым σ-покрытием, если выполнены следующие два условия: 1) для любого i ∈ {1, 2, …, r} и любого y ∈ Q₁(${{\sigma }_{i}},{{P}_{{{{j}_{i}}}}}$) подматрица $L_{R}^{H}$ матрицы L_R, образованная столбцами из H, содержит каждую из строк вида (${{\beta }_{1}}, \ldots ,{{\beta }_{{i - 1}}},{{\beta }_{i}},{{\beta }_{{i + 1}}}, \ldots ,{{\beta }_{r}}$), где β_r ∈ Q₂(${{\sigma }_{i}},y,{{P}_{{{{j}_{i}}}}}$) и ${{\beta }_{t}} \preccurlyeq {{\sigma }_{t}}$ при t ≠ i, t ∈ {1, 2, …, r}; 2) подматрица $L_{R}^{H}$ не содержит строк, предшествующих σ.

Заметим, что если P_i, i ∈ {1, 2, …, n}, – конечная цепь и x ∈ P_i не является наибольшим элементом в P_i, то множество Q₁(x, P_i) состоит из одного элемента, обозначаемого далее через x + 1, и следовательно, Q₂(x, x + 1, P_i) = {x + 1}. Поэтому в случае произведения конечных цепей условие 1) из определения упорядоченного тупикового σ-покрытия превращается в следующее условие: для любого i ∈ {1, 2, …, r} подматрица $L_{R}^{H}$ матрицы L_R, образованная столбцами из H, содержит строку (${{\beta }_{1}}, \ldots ,{{\beta }_{{i - 1}}},{{\sigma }_{i}} + 1,{{\beta }_{{i + 1}}}, \ldots ,{{\beta }_{r}}$), где ${{\beta }_{t}} \preccurlyeq {{\sigma }_{t}}$ при t ≠ i, t ∈ {1, 2, …, r}.

Покажем, что между множеством упорядоченных тупиковых покрытий матрицы L_R и множеством $I({{R}^{ + }})$ существует взаимно однозначное соответствие.

Возьмем элемент x = (x₁, …, x_n) ∈ P, в котором компонента ${{x}_{{{{j}_{i}}}}} = {{\sigma }_{i}}$, i ∈ {1, 2, …, r}, не является наибольшим элементом в ${{P}_{{{{j}_{i}}}}}$, а каждая из остальных компонент x_j, j ∈ {1, 2, …, n}\{j₁, …, j_r} – наибольший элемент в P_j. Положим σ = (${{\sigma }_{1}}, \ldots ,{{\sigma }_{r}}$). Имеет место следующая

Теорема 2. Элемент x является максимальным независимым от R тогда и только тогда, когда набор столбцов матрицы L_R с номерами j₁, …, j_r является упорядоченным тупиковым σ-покрытием матрицы L_R.

Доказательство. Достаточность очевидна. Докажем необходимость.

Пусть элемент x является максимальным независимым от R. Тогда из условия независимости элемента x следует условие 2) из определения упорядоченного тупикового σ-покрытия матрицы L_R. Покажем справедливость условия 1) из того же определения.

Так как при i ∈ {1, 2, …, r} компонента ${{x}_{{{{j}_{i}}}}}$ элемента x, не является наибольшим элементом в ${{P}_{{{{j}_{i}}}}}$, то Q₁(${{\sigma }_{i}},{{P}_{{{{j}_{i}}}}}$) ≠ $\not {0}$ для всех i ∈ {1, 2, …, r}. Пусть i ∈ {1, 2, …, r}, $\sigma _{i}^{'} \in {{Q}_{1}}({{\sigma }_{i}},{{P}_{{{{j}_{i}}}}})$. Рассмотрим элемент x' = ($x_{1}^{'}, \ldots ,x_{n}^{'}$) множества P, полученный из элемента x путем замены компоненты ${{x}_{{{{j}_{i}}}}}$, равной σ_i, на компоненту $x_{{{{j}_{i}}}}^{'}$, равную $\sigma _{i}^{'}$. Из того, что x – максимальный независимый от R элемент, следует, что $x{\kern 1pt} ' \in {{R}^{ + }}$. Это означает, что в R существует элемент $x{\kern 1pt} '' = (x_{1}^{{''}}, \ldots ,x_{n}^{{''}})$, такой что $x{\kern 1pt} '' \preccurlyeq x{\kern 1pt} '$. Положим $x_{{{{j}_{t}}}}^{{''}}$ = β_t, t ∈ {1, 2, …, r}. Тогда из сказанного следует, что ${{\beta }_{t}} \preccurlyeq \sigma _{t}^{'}$, $\sigma _{t}^{'}$ = σ_t при t ≠ i, t ∈ {1, 2, …, r}, и ${{\beta }_{i}} \preccurlyeq \sigma _{i}^{'}$, $\sigma _{t}^{'}$ ∈ Q₁(${{\sigma }_{i}},{{P}_{{{{j}_{i}}}}}$). Если ${{\beta }_{i}} \preccurlyeq {{\sigma }_{i}}$, то $x{\kern 1pt} '' \preccurlyeq x$, что противоречит независимости x. Значит, , т.е. β_i ∈ Q₂(${{\sigma }_{i}},\sigma _{i}^{'},{{P}_{{{{j}_{i}}}}}$). Таким образом, в силу произвольности выбора компоненты σ_i элемента x, а также произвольности выбора элемента $\sigma _{i}^{'}$ ∈ Q₁(${{\sigma }_{i}},{{P}_{{{{j}_{i}}}}}$), условие 1 оказывается выполненным и действительно набор столбцов матрицы L_R с номерами  j₁, …, j_r является упорядоченным тупиковым σ-покрытием матрицы L_R.

Теорема доказана.

Замечание 2. Согласно теореме 2 логическая классификация данных, являющихся произведением конечных частичных порядков, фактически сводится к поиску упорядоченных тупиковых покрытий целочисленной матрицы.

Замечание 3. В разд. 2 было отмечено, что задача монотонной дуализации может быть решена на основе перечисления неприводимых покрытий булевой матрицы. Введенное в данном разделе понятие упорядоченного тупикового покрытия матрицы L_R обобщает понятие неприводимого покрытия булевой матрицы. Действительно, если $R \subseteq P$, P = P₁ × … × P_n, P_i = {0, 1}, i ∈ {1, 2, …, n}, и в каждом P_i задан порядок 0 $ \prec $ 1, то упорядоченное тупиковое (0, …, 0)-покрытие матрицы L_R является неприводимым покрытием.