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

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

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

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

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

y^=arg⁡max⁡c∈{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+xTw2⋯gC(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,...w0C∈Rw_{01},w_{02},...w_{0C}\in \mathbb{R} и CC векторов из коэффициентов при каждом признаке w1,w2,...wC∈RD\mathbf{w}_1,\mathbf{w}_2,...\mathbf{w}_C\in\mathbb{R}^D. Таким образом, для спецификации достаточно C(D+1)C(D+1) параметров.

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

Поскольку дискриминантные функции определены с точностью до сдвига на произвольную функцию (докажите!), то можно всегда смещать на gC(x)g_C(x), получая, что рейтинг последнего класса будет равен тождественному нулю. И для эквивалентной спецификации линейного классификатора будет достаточно всего (C−1)(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)=arg⁡max⁡c∈{+1,−1}{w0c+wcTx}=sign(w0,+1+w+1Tx−w0,−1−w−1Tx)=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,+1−w0,−1w=w+1−w−1\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,u≥0−1,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+wTx∥w∥\rho(\mathbf{x},H)=\frac{w_0+\mathbf{w}^T \mathbf{x}}{\|\mathbf{w}\|}

Доказательство этого факта можно прочитать в [1].

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

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

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

  • По знаку дискриминантной функции можно судить о том, с какой именно стороны от разделяющей гиперплоскости оказался объект.

  • Если дискриминантная функция равна нулю, то объект попадает строго на границу между классами.

Литература​

  1. Math.stackexchange: distance from a point to a hyperplane.