Перейти к основному содержимому

Линейная классификация

Напомним из более ранней главы, что задача классификации состоит в предсказании дискретного отклика:

y{1,2,....C}y \in \{1,2,....C\}

и осуществляется по правилу

y^=argmaxc{1,2,...C}gc(x),\hat{y}=\arg\max_{c\in \{1,2,...C\}} g_c(\mathbf{x}),

где g1(x),...gC(x)g_1(\mathbf{x}),...g_C(\mathbf{x}) - дискриминантные функции, измеряющие рейтинг класса для объекта x\mathbf{x}.

Линейный многоклассовый классификатор

Линейный многоклассовый классификатор (linear multiclass classifier) - классификатор, у которого все дискриминантные функции могут быть представлены в виде линейных функций:

g1(x)=w01+xTw1g2(x)=w02+xTw2gC(x)=w0C+xTwС\begin{matrix} g_1(\mathbf{x})=w_{01}+\mathbf{x}^T \mathbf{w}_1 \\ g_2(\mathbf{x})=w_{02}+\mathbf{x}^T \mathbf{w}_2 \\ \cdots \\ g_C(\mathbf{x})=w_{0C}+\mathbf{x}^T \mathbf{w}_С \\ \end{matrix}

Для спецификации линейного классификатора нужно задать CC смещений w01,w02,...w0CRw_{01},w_{02},...w_{0C}\in \mathbb{R} и CC векторов из коэффициентов при каждом признаке w1,w2,...wCRD\mathbf{w}_1,\mathbf{w}_2,...\mathbf{w}_C\in\mathbb{R}^D. Таким образом, для спецификации достаточно C(D+1)C(D+1) параметров.

На самом деле меньше...

Поскольку дискриминантные функции определены с точностью до сдвига на произвольную функцию (докажите!), то можно всегда смещать на gC(x)g_C(x), получая, что рейтинг последнего класса будет равен тождественному нулю. И для спецификации линейного классификатора достаточно всего (C1)(D+1)(C-1)(D+1) параметров.

Граница между ii-м и jj-м классом определяется из условия:

{x:gi(x)=gj(x)}={x:w0i+xTwi=w0j+xTwj}\{\mathbf{x}: g_i(\mathbf{x})=g_j(\mathbf{x})\} = \{\mathbf{x}: w_{0i}+\mathbf{x}^T \mathbf{w}_i = w_{0j}+\mathbf{x}^T \mathbf{w}_j\}

Поскольку это линейное уравнение, то граница для линейного классификатора всегда будет линейной гиперплоскостью.

Линейный бинарный классификатор

Линейный бинарный классификатор (linear binary classifier) решает задачу классификации на два класса, называемые положительным и отрицательным:

y{+1,1}y\in\{+1,-1\}

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

Прогноз для линейного бинарного классификатора строится по правилу:

y^(x)=argmaxc{+1,1}{w0c+wcTx}=sign(w0,+1+w+1Txw0,1w1Tx)=sign(w0+wTx),\widehat{y}(\mathbf{x})=\arg\max_{c\in\{+1,-1\}}\{w_{0c}+\mathbf{w}_{c}^{T}\mathbf{x}\}=\text{sign}\left(w_{0,+1}+\mathbf{w}_{+1}^{T}\mathbf{x}-w_{0,-1}-\mathbf{w}_{-1}^{T}\mathbf{x}\right)=\text{sign}\left(w_0+\mathbf{w}^{T}\mathbf{x}\right),

где мы ввели обозначения:

w0=w0,+1w0,1w=w+1w1\begin{align} w_0&=w_{0,+1}-w_{0,-1}\\ \mathbf{w}&=\mathbf{w}_{+1}-\mathbf{w}_{-1} \end{align}

а функция sign(u)\text{sign}(u) извлекает знак аргумента:

sign(u)={+1,u01,u<0\text{sign}(u)= \begin{cases} +1, \quad u\ge 0 \\ -1, \quad u<0 \\ \end{cases}\\

Величина w0+wTxw_0+\mathbf{w}^{T}\mathbf{x} является относительной дискриминантной функцией или относительным рейтингом, и характеризует насколько положительный класс лучше подходит для объекта x\mathbf{x}, чем отрицательный.

Геометрическая интерпретация

Расстояние от x\mathbf{x} до гиперплоскости HH, задаваемым уравнением

{x:w0+wTx=0}\{\mathbf{x}: w_0+\mathbf{w}^T \mathbf{x}=0\}

можно посчитать (докажите!) как

ρ(x,H)=w0+wTxw.\rho(\mathbf{x},H)=\frac{w_0+\mathbf{w}^T \mathbf{x}}{\|\mathbf{w}\|}.

Обратим внимание, что это расстояние со знаком, т.е. оно может быть как положительным, так и отрицательным, в зависимости от того, точка x\mathbf{x} лежит с одной или с другой стороны от гиперплоскости.

Из последней формулы видно, что относительная дискриминантная функция - это расстояние (со знаком) от x\mathbf{x} до разделяющей гиперплоскости.

  • Если она принимает большие значения, то x\mathbf{x} лежит в глубине того или иного класса, а если малые - то на границе между классами.

  • По одну сторону от разделяющей гиперплоскости модель прогнозирует один класс, а по другую - другой.