Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 490, № 1, стр. 67-70

В работе рассматриваются алгоритмы классификации на $l$ классов [1], которые по контрольной выборке (некоторому множеству q объектов) получают бинарную матрицу классификации размера $q \times l$, ij-й элемент которой – ответ алгоритма на вопрос, принадлежит ли i-й объект j-му классу (1 – да, 0 – нет). Алгоритм классификации выбирается из модели алгоритмов (некоторого параметрического множества), используя обучающую выборку (множество объектов с известной классификацией). Например, параметры алгоритма настраиваются так, чтобы ответ на обучающей выборке был как можно точнее, такая настройка называется обучением.

Следуя алгебраическому подходу к решению задач классификации [2–4], мы сосредоточимся на вопросах реализации произвольных матриц классификации в рамках одной модели, оставляя в стороне классические вопросы машинного обучения (machine learning): проблему выбора параметров, функционалы качества классификации [5] и т.п. В алгебраическом подходе каждый алгоритм $A$ представляется в виде суперпозиции $A = B \cdot C$: сначала оператор $B$ формирует матрицу оценок $H = {\text{||}}{{h}_{{ij}}}{\text{|}}{{{\text{|}}}_{{q \times l}}}$, ij-й элемент которой интерпретируется как оценка принадлежности i-го объекта j-му классу, затем решающее правило $C$ получает по ней матрицу классификации ${{\left\| {{{\alpha }_{{ij}}}} \right\|}_{{q \times l}}}$.

Определение 1. Модель алгоритмов классификации называется полной (для данных обучающей и контрольной выборок), если для любой матрицы $H \in {{\mathbb{R}}^{{q \times l}}}$ существует оператор модели B, порождающий матрицу оценок H.

Дальше все определения будут вводиться при фиксированных обучающей и контрольной выборках, поэтому не будем это отдельно обговаривать. Иногда полнота называется корректностью, оба понятия были введены в [1] (при необременительных условиях они эквивалентны). Понятие полноты затем исследовалось в работах [6, 7]. В [8, 9] сделано предположение, что требование полноты слишком жесткое. По сути, полнота нужна для реализации произвольных матриц классификации с помощью достаточно простых решающих правил. Логично потребовать возможность такой реализации и рассматривать нетривиальные решающие правила и/или правила из некоторых семейств.

Определение 2. Модель алгоритмов классификации называется полной относительно решающего правила C или C-полной, если для любой матрицы $G \in {{\{ 0,1\} }^{{q \times l}}}$ существует такой оператор модели B, что алгоритм $A = B \cdot C$ реализует матрицу классификации G.

Определение 3. Модель алгоритмов классификации называется полной относительно семейства решающих правил $C{\text{*}}$ или $C{\text{*}}$-полной, если для любой матрицы $G \in {{\{ 0,1\} }^{{q \times l}}}$ существуют такие оператор модели В и решающее правило C из семейства $C{\text{*}}$, что алгоритм $A = B \cdot C$ реализует матрицу классификации G.

Одно из самых популярных на практике решающих правил [10] – пороговое решающее правило с порогом $c \in \mathbb{R}$:

для всех $\left( {i,j} \right) \in QL$, здесь и далее QL = {1, 2, ... ..., $q\} \times \{ 1,2, \ldots ,l\} $. Семейство пороговых решающих правил получается варьированием порога:

Определение 4. Модель алгоритмов классификации называется линейной, если существуют такие матрицы ${{H}_{1}},{{H}_{2}},\; \ldots ,\;{{H}_{l}}$, матрица ${{H}_{j}}$ имеет размер $q \times {{k}_{j}}$, $j \in \{ 1,2, \ldots ,l\} $, что матрица оценок H получается оператором алгоритма модели тогда и только тогда, когда j-й столбец матрицы имеет вид ${{H}_{j}}{{{\mathbf{x}}}_{j}}$, ${{{\mathbf{x}}}_{j}} \in {{\mathbb{R}}^{{{{k}_{j}}}}}$ для всех $j \in \{ 1,2, \ldots ,l\} $.

Линейная модель задается набором матриц ${{H}_{1}},{{H}_{2}}, \ldots ,{{H}_{l}}$, мы не будем подробно описывать, как они вычисляются, приведем лишь один пример. Если для каждого класса независимо мы настраиваем линейный регрессор (или логистическую регрессию [5]) на признаковых $n$-мерных описаниях объектов обучающей выборки (целевой признак здесь равен 1, если объект принадлежит $j$-му классу, 0 – в противном случае), то получаем линейную (в нашей терминологии) модель, в которой ${{H}_{1}} = {{H}_{2}} = \; \ldots \; = {{H}_{l}} = X$, в матрице X размера $q \times n$ по строкам записаны признаковые описания контрольных объектов. Формально при использовании логистической регрессии модель нелинейная, а именно эта модель наиболее популярная и часто используемая на практике, но из-за использования порогового решающего правила можно привести эквивалентную ей (порождает такие же матрицы классификации) линейную.

В алгебраическом подходе [1, 3] вводятся операции над операторами, они индуцируются операциями над их матрицами оценок. Например, $H\left( {{{B}_{1}} + {{B}_{2}}} \right) = H\left( {{{B}_{1}}} \right) + H\left( {{{B}_{2}}} \right)$, где H(B) – матрица оценок оператора B. Аналогично вводится умножение на константу. Линейное замыкание модели (говорят сразу про модель алгоритмов, так как решающее правило фиксируют) – множество алгоритмов, операторы которой являются линейными комбинациями операторов модели. Для линейных моделей линейное замыкание модели совпадает с самой моделью, что освобождает от необходимости отдельно исследовать модель и ее линейное замыкание.

Для матриц ${{X}_{1}} \in {{\mathbb{R}}^{{q \times {{l}_{1}}}}}$, ${{X}_{2}} \in {{\mathbb{R}}^{{q \times {{l}_{2}}}}}$ с помощью квадратных скобок будем обозначать их горизонтальную конкатенацию размера $q \times \left( {{{l}_{1}} + {{l}_{2}}} \right)$:

Для большего числа матриц – аналогично, т.е. для линейной модели матрица оценок имеет вид

перебором различных ${{{\mathbf{x}}}_{1}},{{{\mathbf{x}}}_{2}},\; \ldots ,\;{{{\mathbf{x}}}_{l}}$ получаем все матрицы оценок операторов модели. Через $\tilde {1}\, = \,{{(1,1, \ldots ,1)}^{{\text{т}}}}$ будем обозначать вектор, состоящий из одних единиц (размерность будет понятна из контекста), q-мерный вектор по умолчанию рассматривается как матрица размера $q \times 1$, поэтому запись $[{{H}_{j}},\tilde {1}]$ означает приписывание к матрице H_j единичного столбца.

При доказательстве описанных ниже теорем существенно используется следующий критерий: система неравенств

где ${\mathbf{m}}_{i}^{{\text{т}}}$ – $i$-я строка матрицы $M \in {{\mathbb{R}}^{{q \times l}}}$, совместна (относительно неизвестного вектора x) для всех подмножеств $I \subseteq \{ 1,2,\; \ldots ,\;q\} $ тогда и только тогда, когда ${\text{rank(}}M{\text{)}} = q$.

Теорема 1. Линейная модель алгоритмов классификации полна относительно решающего правила ${{C}_{c}}$ (порогового с фиксированным порогом c) тогда и только тогда, когда

Теорема 2. Линейная модель алгоритмов классификации полна относительно семейства пороговых решающих правил тогда и только тогда, когда для всех $j \in \{ 1,2,\; \ldots ,\;l\} $ выполняется равенство $\operatorname{rank} ({{H}_{j}}) = q$, кроме, быть может, одного, для которого $\operatorname{rank} ([{{H}_{j}},\tilde {1}]) = q$.

В [8] доказано, что для алгоритмов вычисления оценок (АВО) [1, 3] возможность реализации любой матрицы классификации с помощью порогового решающего правила эквивалентна возможности реализации любой матрицы оценок операторами модели. Для линейной модели и фиксированного порогового решающего правила это также справедливо, но в случае возможности использовать произвольное пороговое решающее правило линейная модель может порождать любую матрицу классификации и при этом не любую матрицу оценок. Отметим, что на практике часто регрессоры в линейной модели могут получать константные ответы, поэтому

rank(H_j) = ${\text{rank}}([{{H}_{j}},\tilde {1}])$.

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

Обычно используют такое решающее правило:

для всех $(i,j) \in QL$ (если в i-й строке несколько максимальных элементов, то можно считать, что ${{\alpha }_{{ij}}} = 1$ для какого-то одного $j \in \{ s~~|~~{{h}_{{is}}} = \mathop {{\text{max}}}\limits_t {{h}_{{it}}}\} $).

Определение 5. Модель алгоритмов классификации называется полной относительно решающего правила C  в задаче с непересекающимися классами, если для любой матрицы $G \in {{G}_{{~нп~}}}$ существует такой оператор модели В, что алгоритм $A = B \cdot C$ реализует матрицу классификации G.

Полнота относительно решающего правила C_max в задаче с непересекающимися классами будем называть C_max-полнотой.

Теорема 3. Линейная модель алгоритмов классификации C_max-полна в задаче с двумя непересекающимися классами тогда и только тогда, когда

Теорема 4. Если линейная модель алгоритмов классификации C_max-полна в задаче с непересекающимися классами из множества $\left\{ {1,2,\; \ldots ,\;l} \right\}$, тогда она C_max-полна в задаче с любым подмножеством классов $J:~~\phi \ne J \subseteq \left\{ {1,2, \ldots ,l} \right\}$.

В случае произвольного числа классов получаем необходимое условие C_max-полноты:

которое не является достаточным.

Если для всех $s \in \left\{ {1,2,\; \ldots ,\;l} \right\}$ выполнено ${\text{rank}}({{H}_{s}})$ = q, кроме, быть может, двух i, $j \in \{ 1,$ 2, ..., l}, для которых ${\text{rank}}([{{H}_{i}},{{H}_{j}}]) = q$, тогда линейная модель C_max-полна. Полученное достаточное условие C_max-полноты не является необходимым.

Таким образом, в задачах классификации с непересекающимися классами уже для числа классов l = 2 критерии C_max-полноты (1) и полноты

различаются, хотя решающее правило C_max является довольно простым и непараметрическим.