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

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

– 11 –

• Методы нормального дискриминантного анализа перестают работать, если

классы имеют плотности, существенно отличающиеся от гауссовских. В частно-

сти, когда имеются номинальные признаки (принимающие небольшое конечное

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

Далее рассматриваются некоторые способы устранения перечисленных недостатков.

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

В 1936 г. Фишер предложил следующую эвристику, позволяющую увели-

чить число объектов, по которым оценивается ковариационная матрица, повысить

её устойчивость и заодно упростить алгоритм обучения.

Будем считать ковариационные матрицы классов равными, даже если они на са-

мом деле не равны. В таком случае достаточно оценить только одну ковариацион-

ную матрицу

Σ, задействовав для этого все ` обучающих объектов. При этом классы

всегда разделяются линейными поверхностями. Коэффициенты поверхностей полу-

чаются непосредственно из (1.3):

a(x) = arg max

y∈Y

(x)

= arg max

y∈Y

ln(λ

) −

ˆµ

−1

ˆµ

{z }

−1

ˆµ

{z}

= arg max

y∈Y

+ β

. (1.5)

Обучение сводится к вычислению оценок матожидания ˆµ

для всех классов y ∈

∈ Y и оценки общей ковариационной матрицы

Σ. Затем вычисляются коэффициенты

∈ R

и β

∈ R для всех y ∈ Y . После обучения классификация новых объектов

производится по формуле (1.5). Этот алгоритм называется линейным дискриминан-

том Фишера (алгоритм 1.1).

Алгоритм 1.1 Обучение линейного дискриминанта Фишера

Вход:

выборка X

, предполагается ` > |Y |;

величины потерь λ

, y ∈ Y ;

Выход:

коэффициенты линейных разделяющих поверхностей α

∈ R

, β

∈ R, y ∈ Y ;

1: для всех y ∈ Y

2: X

:= {x

∈ X

| y

= y}; `

:= |X

:= `

/`;

3: ˆµ

x∈X

Σ :=

` − |Y |

y∈Y

x∈X

(x − ˆµ

)(x − ˆµ

)

;

5: для всех y ∈ Y

6: α

−1

ˆµ

; β

:= ln(λ

) −

ˆµ

;

– 12 –

Эвристика Фишера неплохо работает, когда формы классов близки к нормаль-

ным и не слишком сильно различаются. В этом случае линейное решающее правило

достаточно близко к оптимальному байесовскому, но существенно более устойчиво

и часто обладает лучшей обобщающей способностью.

Регуляризация ковариационной матрицы Общая ковариационная матрица

классов

Σ может оказаться плохо обусловленной (близкой к вырожденной), если

длина выборки невелика по сравнению с числом признаков или если среди призна-

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

матрицы

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

неустойчивым.

TODO:

что значит «плохо обусловлена», «почти линейно зависима»

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

ных эллипсов. Собственные векторы матрицы

Σ задают направления осей эллипса.

Собственные значения определяют «толщину» эллипса вдоль соответствующих на-

правлений. Существует простой способ увеличить все собственные значения матри-

цы

Σ на одну и ту же величину τ, оставив неизменными собственные векторы. При

этом «форма» распределения немного искажается, зато матрица становится хорошо

обусловленной.

Для этого достаточно вместо

Σ взять матрицу

Σ+τI

, где I

— единичная мат-

рица размера n. Действительно, пусть v — собственный вектор, λ — его собственное

значение,

Σv = λv. Тогда

(

Σ + τ I

)v = λv + τ v = (λ + τ)v.

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

недиагональные элементы — вместо

Σ брать матрицу (1 − τ )

Σ + τ diag

Σ. Можно

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

корреляции которых незначимо отличаются от нуля. Можно разбивать множество

признаков на группы и полагать, что признаки из разных групп не коррелированы.

Тогда матрица

Σ приобретает блочно-диагональный вид, и для её обращения может

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

Синтез информативных признаков Сокращение размерности методом главных

компонент

Отбор информативных признаков

Метод редукции Другой подход к уменьшению размерности пространства заклю-

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

Робастные методы оценивания Оценки, устойчивые относительно редких боль-

ших выбросов, связанных с малыми загрязнениями плотности, называются робаст-

ными (robust — здравый).

– 13 –

Метод одномерных нелинейных преобразований признаков

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

В тех случаях, когда «форму» класса не удаётся описать каким-либо одним

распределением, можно попробовать описать её смесью распределений.

Гипотеза 1.5 Плотность распределения на X имеет вид смеси k распределений:

p(x) =

j=1

(x),

где p

(x) — функция правдоподобия j-й компоненты смеси, w

— её априорная веро-

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

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

(x) = p(x; θ

Заметим, что по формуле полной вероятности

j=1

= 1.

Задача разделения смеси заключается в том, чтобы, зная выборку X

, число k

и семейство p(x; θ), оценить вектор параметров Θ = (w

, . . . , w

, θ

, . . . , θ

1.3.1 EM-алгоритм

К сожалению, попытка разделить смесь, используя принцип ма ксимума правдо-

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

эту трудность позволяет алгоритм EM (expectation-maximization). Идея алгоритма

заключается в следующем. Вводится вектор скрытых (hidden) переменных G, обла-

дающий двумя замечательными свойствами. С одной стороны, он может быть вы-

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

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

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

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

Алгоритм 1.2 Общая идея EM-алгоритма

1: Вычислить начальное приближение вектора параметров Θ

2: повторять

3: E-шаг (expectation): имея текущее приближение Θ

, вычислить ожидаемое зна-

чение вектора скрытых переменных G.

4: M-шаг (maximization): имея текущее значение G, вычислить следующее при-

ближение вектора Θ, исходя из принципа максимума правдоподобия.

5: Θ

:= Θ;

6: пока Θ и G не стабилизируются.

Этот общий алгоритм находит применение в задачах дискриминантного ана-

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

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

– 14 –

E-шаг (expectation) Обозначим через p(x

) совместную плотность вероятно-

сти того, что получен объект x и этот объект сгенерирован j-й компонентой смеси.

По формуле условной вероятности

p(x

) = p (x) P(θ

|x) = w

p(x|θ

Введём обозначение g

≡ P(θ

). Это апостериорная вероятность того, что обу-

чающий объект x

был сгенерирован j-й компонентой смеси. Именно эти величины

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

j=1

= 1 для всех i.

Зная параметры компонент w

, θ

, легко вычислить g

по формуле Байеса:

)

s=1

)

для всех i, j.

В этом и заключается E-шаг алгоритма EM.

M-шаг (maximization) Покажем, что знание значений скрытых переменных g

и принцип максимума правдоподобия приводят к оптимизационной задаче, допуска-

ющей эффективное численное (или даже аналитическое) решение. Будем минимизи-

ровать функционал

Q(Θ) = −ln

i=1

p(x

) = −

i=1

ln p(x

Для сходимости EM-процесса желательно, чтобы значение функционала Q(Θ) не уве-

личивалось от итерации к итерации:

∆Q ≡ Q(Θ) − Q(Θ

) 6 0,

где Θ

= (w

, . . . , w

, θ

, . . . , θ

) — вектор параметров с предыдущей итерации.

По определению условной вероятности p

= w

), следовательно,

∆Q = −

i=1

p(x

)

= −

i=1

j=1

)

6 −

i=1

j=1

)

где неравенство следует из выпуклости функции f(z) = −ln z. Введём обозначение

Q(Θ) = −

i=1

j=1

)

– 15 –

Тогда ∆Q 6

Q(Θ) −

Q(Θ

), следовательно,

Q(Θ) 6

Q(Θ) + Q(Θ

) −

Q(Θ

)

{z }

const(Θ)

≡ Φ(Θ).

Функционал Φ(Θ) мажорирует Q(Θ) и совпадает с ним в точке Θ

. Возьмём

в качестве следующего приближения вектора Θ точку минимума функционала

Q(Θ).

Тогда гарантированно выполняется неравенство Q(Θ) 6 Φ(Θ

) = Q(Θ

). Сходимость

алгоритма вытекает, главным образом, из этого факта. Более подробно условия схо-

димости рассматриваются в работах Джеффа Ву (1983) и Джордана (1993).

Итак, на M-шаге решается задача минимизации функционала Φ(Θ) или, что

то же самое, функционала

Q(Θ), при ограничении типа равенства:











Q(Θ) = −

i=1

j=1

)

→ min

;

j=1

= 1;

(1.6)

Критерий останова Принцип максимума апостериорной информации (теоре-

ма 1.2) позволяет отнести каждый объект x

к той или иной компоненте смеси:

J(x

) = arg max

j=1,...,k

Тогда критерием останова EM-алгоритма может быть стабилизация состава компо-

нент, когда объекты перестают «перепрыгивать» из одной компоненты в другую:

J(x

) = J

) для всех i,

где J

) — номер компоненты, к которой x

был отнесён на предыдущей итерации.

Обобщённый алгоритм EM (GEM) Не обязательно добиваться высокой точ-

ности решения максимизационной задачи на каждом шаге алгоритма. Достаточно

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

ций. Можно даже выполнять E-шаг после каждой итерации M-шага.

Смесь многомерных нормальных распределений общего вида Минимиза-

ция функционала

Q(Θ) является существенно более простой задачей, чем миними-

зация Q(Θ). В некоторых случаях удаётся получить аналитическое решение и даже

доказать, что минимум функционала

Q(Θ) является глобальным. В частности, это

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

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

раметрами θ

= (µ

, Σ

), где µ

— n-мерный вектор, Σ

— ковариационная матрица,

в общем случае не диагональная:

(x) =

(2π)

|Σ

exp

−

(x − µ

)

−1

(x − µ

)

, j = 1, . . . , k.

– 16 –

Теорема 1.4 Если справедлива гипотеза 1.6, то стационарная точка оптимизацион-

ной задачи (1.6) имеет вид

ˆw

i=1

;

ˆµ

` ˆw

i=1

;

` ˆw

i=1

− ˆµ

)(x

− ˆµ

)

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

Запишем лагранжиан оптимизационной задачи (1.6):

L(Θ, λ) = −

i=1

j=1

ln w

−

i=1

j=1

ln p

) + λ

j=1

− 1

. (1.7)

Необходимые условия стационарной точки:

∂L

∂w

= −

i=1

+ λ = 0;

∂L

∂θ

= −

i=1

∂

∂θ

ln p

) = 0;

Из первого равенства находим λ = ` и lw

i=1

, откуда следует первое из трёх

соотношений, которые требовалось доказать.

Запишем логарифм плотности нормального распределения:

ln p

(x) = const(µ

, Σ

) +

ln |Σ

−1

(x − µ

)

−1

(x − µ

Производные по вектору матожидания:

∂

∂µ

ln p

) = −Σ

−1

− µ

);

∂L

∂µ

i=1

−1

− µ

) = 0.

Умножая последнее равенство слева на Σ

, получаем

i=1

откуда следует второе соотношение.

– 17 –

Теперь запишем производные по ковариационной матрице. Заметим, что, по-

скольку матрица Σ

−1

взаимно однозначно связана с матрицей Σ

, то неважно, по ка-

кой из этих двух матриц дифференцировать лагранжиан. Удобнее взять производ-

ную по Σ

−1

∂

∂Σ

−1

ln p

) = −

2Σ

− diag Σ

−

2(x

− µ

)(x

− µ

)

− diag(x

− µ

)(x

− µ

)

Введём обозначения

) = Σ

− (x

− µ

)(x

− µ

)

;

i=1

В этих обозначениях

∂L

∂Σ

−1

= −

i=1

) − diag S

)

= S

−

diag S

= 0,

откуда немедленно вытекает S

= 0, следовательно,

i=1

− µ

)(x

− µ

)

Таким образом, доказано последнее из трёх соотношений. ¥

Смесь многомерных нормальных распределений позволяет описывать широкий

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

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

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

Недостатком подхода является необходимость обращать ковариационные мат-

рицы. Это трудоёмкая операция. Кроме того, ковариационная матрица может ока-

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

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

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

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

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

простым классом распределений.

Смесь сферических нормальных распределений Обращения матриц можно

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

версальными аппроксиматорами плотности, хотя требуется их, как правило, больше.

Гипотеза 1.7 Компоненты смеси имеют n-мерные сферические нормальные распре-

деления с параметрами θ

= (µ

, σ

), где µ

— n-мерный вектор, σ

— скаляр:

(x) = (σ

√

2π)

−n

exp

−

−2

kx − µ

, j = 1, . . . , k.

– 18 –

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

ционные матрицы диагональны, Σ

= σ

Теорема 1.5 Если справедлива гипотеза 1.7, то стационарная точка оптимизацион-

ной задачи (1.6) имеет вид

ˆw

i=1

;

ˆµ

` ˆw

i=1

;

ˆσ

` ˆw

i=1

− ˆµ

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

Возьмём производные функции плотности p

(x) по параметрам µ

, σ

∂

∂µ

ln p

(x) = −σ

−1

(x − µ

);

∂

∂σ

ln p

(x) = −nσ

−1

+ σ

−3

kx − µ

;

и приравняем нулю производные лагранжиана (1.7) по параметрам w

, µ

, σ

∂L

∂w

= −

i=1

+ λ = 0;

∂L

∂µ

= σ

−1

i=1

− µ

) = 0;

∂L

∂σ

= σ

−3

i=1

nσ

− kx

− µ

= 0,

откуда немедленно вытекают требуемые соотношения. ¥

Выбор начального приближения Хотя алгоритм EM сходится при достаточно

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

ности» начального приближения. Сходимость ухудшается в тех случаях, когда дела-

ется попытка разместить центр компоненты посередине между фактическими сгуст-

ками распределения. Отсюда вытекает простая эвристика: в качестве начального

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

TODO:

Алгоритм выделения точек, наиболее удалённых друг от друга.

– 19 –

Выбор числа компонент k Разведочный анализ. Визуальное оценивание числа

сгустков с помощью целенаправленного проектирования или многомерного шкали-

рования.

Критерий «крутого обрыва» для функции правдоподобия.

Иерархический алгоритм EM ( HEM) .

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

До сих пор мы рассматривали задачу разделения смеси распределений, забыв

на время о том, что выборка состоит из объектов разных классов. Теперь вернёмся

к задаче классификации. Пусть каждый класс y имеет свою плотность распределе-

ния p

(x), и, соответственно, свою часть выборки X

= {x

∈ X

| y

= y}.

Гипотеза 1.8 Функции правдоподобия классов p

(x), y ∈ Y , представимы в виде

смеси k

компонент — n-мерных сферических гауссианов с параметрами µ

, σ

(x) =

j=1

(x),

j=1

= 1, w

> 0;

(x) = (σ

√

2π)

−n

exp

−

−2

kx − µ

, j = 1, . . . , k, y ∈ Y.

Гипотеза 1.8 — это эвристика, которая часто срабатывает благодаря способ-

ности смеси гауссианов аппроксимировать произвольные непрерывные плотности.

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

не работают, например, задачи с дискретными признаками.

Гипотеза 1.8 неявно предполагает, что евклидова метрика адекватно оценивает

близость векторов в признаковом пространстве, и близкие объекты чаще принадле-

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

Алгоритм классификации Запишем байесовское решающее правило (1.3):

a(x) = arg max

y∈Y

j=1

(x).

Оно имеет вид суперпозиции, состоящей из трёх уровней (слоёв). Первый слой обра-

зован

y∈Y

гауссианами с параметрами µ

, σ

. На входе они принимают описание

объекта x, на выходе выдают значения плотностей компонент в точке x. Второй слой

состоит из |Y | сумматоров, вычисляющих взвешенные средние с весами w

. На вы-

ходе второго слоя появляются значения плотностей классов в точке x. Третий слой

состоит из единственного блока arg max, принимающего решение о принадлежности

объекта x одному из классов.

Описанная многослойная схема вычислений называется сетью радиальных ба-

зисных функций или RBF-сетью (radial basis functions). Это одна из разновидностей

нейронных сетей.

Обучение RBF-сети Один из самых эффективных способов настройки RBF-сетей

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

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

стройки нейронных сетей.

– 20 –

Алгоритм 1.3 Настройка RBF-сети EM-алгоритмом

Вход:

выборка X

;

количество компонент k

, для каждого y ∈ Y ;

Выход:

, µ

, σ

, w

, для всех j = 1, . . . , k

, y ∈ Y ;

1: для всех y ∈ Y , j = 1, . . . , k

инициализация:

2: w

:= случайные значения, удовлетворяющие

j=1

= 1, w

> 0;

:= наиболее далёкие друг от друга k

объектов класса y;

:= среднее kµ

− µ

k по классу y;

3: для всех y ∈ Y

4: X

:= {x

∈ X

| y

= y}; `

:= |X

|; P

:= `

/`;

5: повторять

6: E-шаг: для всех x

∈ X

, j = 1, . . . , k

вычислить скрытые переменные:

)

s=1

)

;

7: M-шаг: для всех j = 1, . . . , k

вычислить параметры компонент:

∈ X

] g

;

∈ X

] g

;

∈ X

] g

− µ

;

8: Запомнить текущие принадлежности объектов компонентам:

:= J

, для всех x

∈ X

;

9: Вычислить новые принадлежности объектов компонентам:

:= arg max

j=1,...,k

, для всех x

∈ X

;

10: пока ∃i: J

6= J

(повторять, пока состав компонент не стабилизируется).

Преимущества RBF-EM

• При использовании сферических плотностей компонент не нужно обращать ко-

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

• При разумном выборе начального приближения метод быстро сходится (гораз-

до быстрее градиентных методов).

Недостатки RBF-EM

• Алгоритм не оценивает число компонент. Приходится заключать шаги 5–10

в дополнительный цикл перебора, определяющий оптимальное значение k

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

• Качество классификации сильно зависит от того, насколько удачно выбрана

метрика. Это общий недостаток метрических алгоритмов.