Воронцов К.В. Лекции по статистическим алгоритмам классификации

Подождите немного. Документ загружается.

Лекции по статистическим (байесовским)

алгоритмам классификации

(черновик)

К. В. Воронцов

19 июня 2005 г.

Содержание

1 Статистические (байесовские) алгоритмы классификации 2

1.1 Вероятностная постановка задачи классификации . . . . . . . . . . . . 3

1.1.1 Функционал среднего риска . . . . . . . . . . . . . . . . . . . . . 3

1.1.2 Оптимальное байесовское решающее правило . . . . . . . . . . . 4

1.2 Нормальный дискриминантный анализ . . . . . . . . . . . . . . . . . . . 7

1.2.1 Линейные и квадратичные разделяющие поверхности . . . . . . 7

1.2.2 Метод максимума правдоподобия . . . . . . . . . . . . . . . . . . 9

1.2.3 Подстановочный алгоритм . . . . . . . . . . . . . . . . . . . . . . 10

1.2.4 Линейный дискриминант Фишера . . . . . . . . . . . . . . . . . . 11

1.3 Разделение смеси распределений . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.1 EM-алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.2 Метод радиальных базисных функций . . . . . . . . . . . . . . . 19

1.4 Непараметрические методы классификации . . . . . . . . . . . . . . . . 21

1.4.1 Непараметрические оценки плотности распределения . . . . . . 21

1.4.2 Метод парзеновского окна . . . . . . . . . . . . . . . . . . . . . . 22

1.4.3 Связь параметрических и непараметрических методов . . . . . . 22

– 2 –

1 Статистические (байесовские) алгоритмы клас-

сификации

Байесовский подход основан на предположении, что плотности распределения

классов либо известны, либо могут быть оценены по обучающей выборке. Это очень

сильное предположение. Оно позволяет выписать искомый алгоритм в явном анали-

тическом виде. Более того, можно доказать, что этот алгоритм является оптималь-

ным, обладая минимальной вероятностью ошибки классификации.

К сожалению, на практике плотности распределения классов, как правило,

неизвестны. Оценивание плотности по конечной выборке — задача, вообще говоря,

более трудная, чем построение алгоритма классификации. В первом случае требу-

ется восстановить вещественную функцию, во втором — всего лишь бинарную. Ка-

залось бы, нет особого смысла сводить простую задачу к сложной. Тем не менее,

байесовский подход, основанный на восстановлении плотностей, позволяет строить

вполне работоспособные алгоритмические конструкции. Эти алгоритмы, как и мно-

гие другие алгоритмы классификации, являются, по сути дела, эвристическими.

По идее, они должны работать в тех случаях, когда реальные данные удовлетворя-

ют, хотя бы приближённо, исходным вероятностным предположениям. На практике

границы их применимости оказываются значительно шире.

Перечислим наиболее распространённые подходы к восстановлению плотностей

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

• Если функция плотности известна с точностью до параметров, то значения

этих параметров можно оценить по выборке, исходя из принципа максимума

правдо подоб ия. В этом случае говорят о параметрических методах оценивания.

Часто используют многомерные нормальные распределения или смеси несколь-

ких нормальных распределений. Эти методы работают, когда реальные данные

достаточно точно описываются выбранным семейством распределений.

• Если подогнать параметрическую модель распределения под имеющиеся дан-

ные не удаётся, то применяют непараметрические методы, основанные на ло-

кальной аппроксимации плотности в каждой точке пространства X. Эти ме-

тоды дают сбой при большом числе признаков, так как по мере увеличения

размерности пространства X все точки выборки становятся практически оди-

наково далеки друг от друга. Этот эффект называют проклятием размерности

(curse of dimensionality). Для сокращения размерности применяются различные

методы отбора информативных признаков (features selection).

• При отсутствии информации о виде распределения вместо параметрического

семейства плотностей можно непосредственно задавать вид разделяющей по-

верхности. Эта эвристика хорошо работает в тех случаях, когда семейство раз-

деляющих поверхностей удачно подобрано для данной конкретной задачи.

Задача построения алгоритма классификации в условиях, когда фиксирован

вид функций правдоподобия классов, либо вид разделяющей поверхности, называ-

ется в математической статистике задачей дискриминантного анализа.

– 3 –

1.1 Вероятностная постановка задачи классификации

Элемент x множества X — это не сам объект, а лишь его описание, доступная

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

вые или очень похожие описания будут относиться к разным классам. В этом случае

определять классы как непересекающиеся подмножества K

x ∈ X

∗

(x) = y

не вполне корректно. Более того, соответствие x → y

∗

(x) в общем случае даже

не является функцией. Тем не менее, алгоритм a(x) обязан быть функцией. Дале-

ко не все подходы к решению задач классификации «замечают» это противоречие.

Чаще всё же полагают, что объект и его описание — это одно и то же.

Байесовский вероятностный подход «замечает» противоречие, но обходит его.

Предполагается, что в произвольной точке x ∈ X каждый класс имеет свою плот-

ность вероятности p(x|K

), y ∈ Y , и задача заключается в том, чтобы построить

алгоритм a(x), минимизирующий вероятность ошибочной классификации.

Реализация этой идеи опирается на следующие исходные гипотезы.

Гипотеза 1.1 Множество прецедентов X × Y является вероятностным простран-

ством с вероятностной мерой P. Прецеденты (x

, y

), . . . , (x

, y

) появляются случайно

и независимо в соответствии с распределением P.

Гипотеза 1.2 Известны плотности распределения классов p

(x) = p(x|K

), y ∈ Y ,

называемые функциями правдоподобия.

Гипотеза 1.3 Известны вероятности появления объектов каждого из классов P

= P(K

), y ∈ Y , называемые априорными вероятностями классов.

Предполагается также, что существуют, но не известны, условные вероятности

P(K

|x) принадлежности объекта x классам K

, y ∈ Y . Их называют апостериор-

ными вероятностями классов, подчёркивая, что они возникают a posteriori, то есть

после того, как стал известен объект x.

1.1.1 Функционал среднего риска

Функции правдоподобия позволяют находить вероятности событий вида «x ∈ Ω

при условии, что x принадлежит классу K

»:

P(Ω|K

) =

Ω

(x) dx.

Рассмотрим произвольный алгоритм a : X → Y . Он разбивает множество X

на непересекающиеся области:

= {x ∈ X | a(x) = y}, y ∈ Y.

Вероятность того, что алгоритм a относит объект y-го класса к s-му классу,

равна P(A

∩ K

) = P

P(A

). Если y = s, то это вероятность правильной класси-

фикации. Если y 6= s, то это вероятность ошибочной классификации. В зависимости

от конкретной задачи потери от ошибок разного рода могут быть различны. Каждой

паре (y, s) поставим в соответствие величину потери λ

, возникающей при отнесении

объекта класса y к классу s. Обычно полагают λ

= 0, и λ

> 0 при y 6= s.

– 4 –

Пример 1.1 В задаче радиолокационной разведки класс K

— самолёты противни-

ка, класс K

— ложные цели. Наиболее опасна ситуация, когда объект класса K

принимается за объект класса K

. Это называется ошибкой I рода или «пропуском

цели». Когда объект класса K

принимается за объект класса K

, говорят об ошибке

II рода или «ложной тревоге». Очевидно, в данном случае λ

> λ

Пример 1.2 В задаче обнаружения спама класс K

— нежелательные сообщения,

подлежащие удалению. Класс K

— сообщения, которые следует сохранить. Здесь,

наоборот, удаление нужного сообщения является более существенной потерей, чем

пропуск спама, поэтому λ

< λ

Опр. 1.1 Функционал среднего риска есть ожидаемая величина потери при класси-

фикации объектов алгоритмом a:

R(a) =

y∈Y

s∈Y

P(A

Если величина потерь одинакова для ошибок любого рода (положим для опре-

делённости λ

= 0 и λ

= 1 при y 6= s), то средний риск R(a) есть просто вероятность

ошибки алгоритма a.

1.1.2 Оптимальное байесовское решающее правило

Знание функций правдоподобия позволяет выписать в явном виде алгоритм a,

минимизирующий средний риск R(a).

Теорема 1.1 Если известны априорные вероятности P

и функции правдоподобия

(x), то минимум среднего риска достигается алгоритмом

a(x) = arg min

s∈Y

(x), где

(x) =

y∈Y

(x), s ∈ Y.

Доказательство.

По формуле полной вероятности для любых y и t из Y

P(A

) = 1 −

s∈Y \{t}

P(A

Выделив произвольный t ∈ Y , распишем функционал полного риска:

R(a) =

y∈Y

s∈Y

P(A

) =

y∈Y

P(A

) +

y∈Y

s∈Y \{t}

P(A

) =

y∈Y

{z }

const(a)

y∈Y

s∈Y \{t}

(λ

− λ

P(A

) =

(1.1)

– 5 –

= const(a) +

s∈Y \{t}

y∈Y

(λ

− λ

(x) dx = (1.2)

= const(a) +

s∈Y \{t}

(ϕ

(x) − ϕ

(x)) dx.

В последнем выражении от алгоритма a зависят только области A

. Интеграл при-

нимает наименьшее значение, когда область A

состоит их тех и только тех точек,

на которых подынтегральное выражение отрицательно. В силу произвольности t

x ∈ X

(x) < ϕ

(x), ∀t 6= s

для всех s ∈ Y .

Но это и означает, что алгоритм a принимает значение s на тех и только тех объек-

тах x, для которых значение ϕ

(x) минимально по s ∈ Y . ¥

Часто м ожно полагать, что величина потери зависит только от истинной клас-

сификации объекта, т. е. λ

≡ λ

. В этом случае алгоритм, доставляющий наимень-

шее значение функционалу среднего риска, приобретает более простой вид.

Теорема 1.2 Если известны априорные вероятности P

и функции правдоподобия

(x), и, кроме того, λ

= 0 и λ

≡ λ

для всех y, s ∈ Y , то минимум среднего риска

доставляется алгоритмом

a(x) = arg max

y∈Y

(x), y ∈ Y. (1.3)

Доказательство.

Рассмотрим выражение (1.2) из доказательства предыдущей теоремы. Посколь-

ку λ

не зависит от второго индекса, разность (λ

−λ

) принимает значение либо λ

при y = t, либо λ

при y = s. Поэтому для любых s, t ∈ Y

(x) − ϕ

(x) =

y∈Y

(λ

− λ

(x) = ψ

(x) − ψ

(x),

где ψ

(x) ≡ λ

(x) для всех y ∈ Y . Аналогично доказательству предыдущей

теоремы отсюда вытекает, что алгоритм a принимает значение s на тех и только тех

объектах x, для которых значение ψ

(x) максимально по s ∈ Y . ¥

Замечание 1.1 Если максимум в (1.3) достигается одновременно при y = s и y =

= t, то объект x находится на разделяющей поверхности между классами K

и K

которая определяется уравнением ψ

(x) = ψ

(x). Алгоритм может относить такие

объекты к любому из классов, это не влияет на средний риск R(a). В некоторых

задачах имеет смысл выдавать «особый ответ» ∆ /∈ Y , означающий отказ алгоритма

от классификации объекта.

Принцип максимума апостериорной вероятности По определению условной

вероятности p

(x)P

= P(K

|x)p(x), поэтому оптимальный алгоритм классифика-

ции (1.3) можно также записать в виде

a(x) = arg max

y∈Y

P(K

|x).

– 6 –

Если классы равнозначны (λ

≡ 1), то данное правило классификации называется

методом максимума апостериорной вероятности. Если классы ещё и равноверо-

ятны (P

≡ 1/M), то объект x просто относится к классу с наибольшим значением

плотности распределения в точке x:

a(x) = arg max

y∈Y

(x).

Выражение (1.3) называют байесовским решающим правилом. Оно непосред-

ственно вытекает из формулы Байеса (точнее, из определения условной вероятно-

сти), если в качестве исходного постулата принять принцип максимума апостериор-

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

волило обобщить решение на случай произвольной матрицы потерь kλ

Тестирование алгоритмов классификации на модельных данных Байесов-

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

качества алгоритмов классификации на этапе их разработки.

Методика тестирования такова.

Сначала с помощью заранее известных функций правдоподобия классов гене-

рируются модельные выборки: обучающая и контрольная. По обучающей выборке

настраивается тестируемый алгоритм a. Вычисляется частота ошибок алгоритм a

на контрольной выборке. Она является несмещённой оценкой функционала средне-

го риска (проведя настройку и контроль многократно, можно оценить средний риск

с любой требуемой точностью). Эта оценка сравнивается с байесовским значением

среднего риска, который для модельных данных может быть рассчитан точно. При

этом сам байесовский классификатор строить не обязательно. Тестируемый алгоритм

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

Преимущества байесовского подхода

• Байесовское решающее правило оптимально, выписывается в явном аналити-

ческом виде, легко реализуется программно.

• Его удобно использовать в качестве эталона при тестировании алгоритмов клас-

сификации на модельных данных.

Недостатки байесовского подхода

• На практике бывает трудно сделать адекватные предположения о виде функ-

ций правдоподобия. При отсутствии содержательных обоснований семейство

плотностей выбирают из соображений удобства получения аналитического ре-

шения, например, предполагают, что плотности нормальны.

• Оценки функций правдоподобия по конечной выборке чувствительны к шуму

в данных и часто имеют значительную погрешность.

– 7 –

1.2 Нормальный дискриминантный анализ

Рассматривается задача классификации, в которой объекты описываются n-

мерными векторами, X = R

. Число классов |Y | произвольно, но конечно.

Опр. 1.2 Вероятностное распределение с плотностью

p(x; µ, Σ) =

(2π)

|Σ|

exp

−

(x − µ)

−1

(x − µ)

называется n-мерным нормальным (гауссовским) распределением с центром µ = Ex

и ковариационной матрицей Σ = E(x − µ)(x − µ)

. Ковариационная матрица имеет

размер n×n, является симметричной, невырожденной и положительно определённой.

Гипотеза 1.4 Классы имеют n-мерные нормальные плотности распределения с па-

раметрами (µ

, Σ

), y ∈ Y .

Геометрическая интерпретация нормальной плотности Если признаки

некоррелированы, Σ = diag(σ

, . . . , σ

), то линии уровня плотности распределения

имеют форму эллипсов с центром µ и осями, параллельными линиям координат. Ес-

ли признаки имеют одинаковые дисперсии, Σ = σ

, то эллипсы являются сферами.

Если признаки коррелированы, то матрица Σ не диагональна и линии уровня

имеют форму эллипсов, оси которых повёрнуты относительно исходной системы ко-

ординат. Действительно, как всякая симметричная матрица, Σ имеет спектральное

разложение Σ = V SV

, где V = (v

, . . . , v

) — ортогональные собственные векторы

матрицы Σ, соответствующие собственным значениям λ

, . . . , λ

, матрица S диаго-

нальна, S = diag(λ

, . . . , λ

). Тогда

(x − µ)

−1

(x − µ) = (x − µ)

V SV

(x − µ) = (x

− µ

)

S(x

− µ

В результате ортогонального преобразования координат x

= V

x оси эллипсов ста-

новятся параллельны линиям координат. В исходных координатах оси эллипсов на-

правлены вдоль собственных векторов. Фактически, собственные векторы ковариа-

ционной матрицы определяют геометрическую «форму» класса. В новых координа-

тах ковариационная матрица S является диагональной. Описанное линейное преоб-

разование признакового описания называется декоррелирующим.

1.2.1 Линейные и квадратичные разделяющие поверхности

Теорема 1.3 Если классы имеют нормальные функции правдоподобия, то байесов-

ское решающее правило строит квадратичную разделяющую поверхность. Квадра-

тичная поверхность вырождается в линейную тогда и только тогда, когда ковариа-

ционные матрицы классов равны.

Доказательство.

Запишем уравнение поверхности, разделяющей классы s и t:

(x) = λ

(x);

ln p

(x) − ln p

(x) − ln(λ

/λ

)

{z }

=const(x)

= 0.

– 8 –

Разделяющая поверхность в общем случае квадратична, поскольку ln p

(x) является

квадратичной формой по x:

ln p

(x) = −

ln 2π −

ln |Σ

| −

(x − µ

)

−1

(x − µ

Если Σ

= Σ

≡ Σ, то квадратичные члены сокращаются и уравнение поверхности

вырождается в линейную форму:

−1

(µ

− µ

) −

−1

− C

= 0;

(x − x

)

−1

(µ

− µ

) − C

= 0;

где x

(µ

+ µ

) — точка посередине между центрами классов. ¥

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

роятны и равнозначны, ковариационные матрицы равны, признаки некоррелирова-

ны и имеют одинаковые дисперсии. Тогда разделяющая гиперплоскость проходит

посередине между классами, ортогонально линии, соединяющей центры классов.

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

на нормаль классы разделяются наилучшим образом.

Усложнение 1: признаки коррелированы. Тогда ортогональность исчезает, при-

чём разделяющая гиперплоскость проходит посередине между классами, касательно

к линиям уровня обоих распределений.

Усложнение 2: классы не равновероятны или не равнозначны. Тогда разделяю-

щая гиперплоскость старается держаться подальше от более опасного класса.

Усложнение 3: ковариационные матрицы общего вида и не равны. Тогда разде-

ляющая поверхность становится квадратичной и прогибается так, что менее плотный

класс охватывает более плотный.

Усложнение 4: Если число классов превышает 2, то разделяющая поверхность

является кусочно-квадратичной, а при равных ковариационных матрицах — кусочно-

линейной.

Замечание 1.2 Пусть классы равновероятны и равнозначны, ковариационные мат-

рицы равны. Тогда уравнение разделяющей поверхности принимает вид

(x − µ

)

−1

(x − µ

) = (x − µ

)

−1

(x − µ

);

kx − µ

= kx − µ

;

где ku − vk

≡

(u − v)

−1

(u − v) — метрика, называемая расстоянием Махалан-

обиса . Разделяющая поверхность является геометрическим местом точек, равноуда-

лённых от центров классов в смысле расстояния Махаланобиса.

Замечание 1.3 Если признаки независимы и имеют одинаковые дисперсии, то рас-

стояние Махаланобиса совпадает с обычной евклидовой метрикой. В этом случае оп-

тимальным (байесовским) решающим правилом является «относить объект к классу

с ближайшим центром». Это алгоритм называют классификатором по минимуму

расстояния.

Замечание 1.4 Ошибка классификации. r ∼ 1.5 ÷ 4. Асимптотика Колмогорова-

Деева.

– 9 –

1.2.2 Метод максимума правдоподобия

Метод максимума правдоподобия позволяет оценить неизвестные параметры

плотности распределения p(x; θ) по случайной, независимой, одинаково распределён-

ной выборке X

= {x

, . . . , x

}. Метод состоит в том, чтобы найти значение вектора

параметров θ, при котором наблюдаемая выборка наиболее вероятна. Запишем плот-

ность распределения (функцию правдоподобия) выборки:

L(X

; θ) =

i=1

p(x

; θ).

Если функция p(x; θ) достаточно гладкая, то необходимое условие максимума есть

∂

∂θ

ln L(X

; θ) =

i=1

∂

∂θ

ln p(x

; θ) = 0. (1.4)

Введение логарифма позволяет заменить произведение суммой и существенно упро-

стить дальнейшие выкладки.

Принцип максимума правдоподобия играет значительную роль в математиче-

ской статистике. Он позволяет сводить задачи оценивания неизвестных параметров

распределений к задачам оптимизации, для решения которых существуют стандарт-

ные методы. Оценки параметров, найденные по конечной выборке данных, принято

называть выборочными.

Оценка параметров нормального распределения В случае гауссовской плот-

ности с параметрами θ ≡ (µ, Σ) задача имеет аналитическое решение.

Напомним, что производная скалярной функции f(A) по матрице A определя-

ется покомпонентно:

∂

∂A

f(A) =

∂

∂a

f(A)

. Если A — квадратная n ×n-матрица, u —

вектор размерности n, то справедливы соотношения:

если A произвольного вида:

∂

∂u

Au = A

u + Au;

∂

∂A

ln |A| = A

−1T

;

∂

∂A

Au = uu

;

если A симметричная:

∂

∂u

Au = 2Au;

∂

∂A

ln |A| = 2A

−1T

− diag A

−1

;

∂

∂A

Au = 2uu

− diag uu

;

В случае гауссовской плотности с параметром θ ≡ (µ, Σ) дифференцирование

функционала ln L(X

; µ, Σ) по вектору µ и матрице Σ приводит к оценкам

ˆµ =

i=1

;

Σ =

x=1

− ˆµ)(x

− ˆµ)

– 10 –

Поправка на смещение

Σ =

` − 1

x=1

− ˆµ)(x

− ˆµ)

1.2.3 Подстановочный алгоритм

В задаче классификации с гауссовскими классами (гипотеза 1.4) параметры

функций правдоподобия ˆµ

оцениваются по обучающей выборке X

для каж-

дого класса y ∈ Y отдельно. Априорные вероятности классов P

также оцениваются

по выборке — это доля объектов выборки, лежащих в классе y:

= `

/`, где `

= |X

|, X

= {x

∈ X

| y

= y}.

На стадии классификации полученные выборочные оценки просто подставляются

в формулу (1.3). Данный алгоритм называется подстановочным.

В асимптотике `

→ ∞ оценки ˆµ

обладают рядом оптимальных свойств:

они не смещены, состоятельны и эффективны. Однако в условиях конечных, зача-

стую слишком коротких, выборок асимптотические свойства не гарантируют вы-

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

«подпорки», чтобы довести алгоритм до состояния практической пригодности.

Недостатки подстановочного алгоритма

• Если длина выборки меньше размерности пространства, `

< n, то матрица

становится вырожденной, поскольку её ранг не может превышать `

. В этом

случае обратная матрица не существует и метод вообще неприменим.

• Когда длина выборки больше размерности пространства, `

> n, но приближа-

ется к ней, матрица

может оказаться плохо обусловленной. В результате её

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

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

кать, когда признаки почти линейно зависимы (мультиколлинеарны).

TODO:

про склонность к переобучению

• Выборочные оценки чувствительны к нарушениям нормальности распределе-

ний, в частности, к редким большим выбросам. Тьюки (1960) показал, что

классическая оценка матожидания нормального распределения неустойчива от-

носительно сколь угодно малого ε -загрязнения плотности даже в одномерном

случае. Загрязнения с «тяжёлым хвостом» приводят к появлению выбросов

и значительному смещению оценки. При увеличении размерности влияние за-

грязнений только усиливается.

TODO:

определение ε-загрязнения плотности