Квадратичный дискриминант

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 28: Строка 28:
== Алгоритм классификации ==
== Алгоритм классификации ==
-
В общем виде, алгоритм Байесовского классификатора имеет вид
+
В общем виде, алгоритм [[Байесовский классификатор|Байесовского классификатора]] имеет вид
<tex>a(x)=argmax_{y \in Y} \lambda_y p_y(x) P_y</tex>
<tex>a(x)=argmax_{y \in Y} \lambda_y p_y(x) P_y</tex>
-
В условиях выдвинутых гипотез алгоритм очевидным образом приобретает следующий вид:
+
Иногда вместо самих вероятностей удобнее брать некоторые функции от них:
 +
 
 +
::<tex>g_y(x)=f(p_y(x)) </tex>
 +
 
 +
где <tex>f -</tex> монотонно возрастает.
 +
 
 +
Функция <tex>g_y(x)</tex> называется дискриминантной функцией, откуда и пошло название самого метода.
 +
 
 +
В условиях выдвинутых гипотез удобнее всего взять в качестве функции <tex>f</tex> натуральный логарифм, и тогда алгоритм приобретает следующий вид:
<tex> a(x)= argmax_{y \in Y} (ln \lambda_y P_y - \frac {1}{2}(x- \hat \mu_y)^T \Sigma^{-1} (x- \hat \mu_y) - \frac {1}{2} ln det {\hat \Sigma_y} ) </tex>
<tex> a(x)= argmax_{y \in Y} (ln \lambda_y P_y - \frac {1}{2}(x- \hat \mu_y)^T \Sigma^{-1} (x- \hat \mu_y) - \frac {1}{2} ln det {\hat \Sigma_y} ) </tex>
Строка 38: Строка 46:
<u>'''Теорема:'''</u> Квадратичный дискриминант имеет квадратичную разделяющую поверхность, которая вырождается в линейную, если ковариационные матрицы классов совпадают.
<u>'''Теорема:'''</u> Квадратичный дискриминант имеет квадратичную разделяющую поверхность, которая вырождается в линейную, если ковариационные матрицы классов совпадают.
-
== Недостатки квадратичного дискриминанта ==
+
<u>'''Доказательство:'''</u> Поверхность, разделяющая классы <tex>s</tex> и <tex>t</tex>, описывается уравнением
-
== Литература ==
+
::<tex>\lambda_s P_s p_s(x)=\lambda_t P_t p_t(x)</tex>
-
# К.В.Воронцов [http://www.machinelearning.ru/wiki/images/e/ed/Voron-ML-Bayes.pdf „Лекции по статистическим (байесовским) алгоритмам классификации“]
+
После логарифмирования
 +
 
 +
::<tex>ln p_s(x)-ln p_t(x)=C_{st}</tex>
 +
 
 +
где <tex>C_{st}=ln(\lambda_s P_s /\lambda_t P_t) -</tex> константа, не зависящая от <tex>x</tex>. Разделяющая поверхность в общем случае квадратична, так как <tex>ln p_y(x)</tex> является квадратичной формой по <tex>x</tex>.
 +
 
 +
::<tex>ln p_y(x)=-\frac {n}{2} ln 2\pi -\frac{1}{2} ln det {\Sigma_y} -\frac{1}{2}(x-\mu_y)^T \Sigma_y^{-1} (x-\mu_y)</tex>
 +
 
 +
Если <tex>\Sigma_s=\Sigma_t</tex>, то квадратичные члены сокращаются и уравнение разделяющей поверхности вырождается в линейную форму:
 +
 
 +
::<tex>(x-\mu_{st})^T \Sigma_y^{-1} (\mu_s-\mu_t)=C_{st}</tex>
 +
 
 +
где <tex>\mu_{st}=\frac{1}{2}(\mu_s+\mu_t) -</tex> точка посередине между центрами классов.
 +
 
 +
{{tip|
 +
Имеет ли смысл описывать геометрию разделяющих поверхностей здесь, или лучше оформить это отдельной статьей?
 +
}}
 +
== Недостатки ==
 +
 
 +
* Если длина выборки меньше размерности пространства, <tex>l_y < n</tex>, то матрица <tex>\hat\Sigma_y^</tex> становится <b>вырожденной</b>, так как ее ранг не может превышать <tex>l_y</tex>. В этом случае обратная матрица не существует, и метод неприменим.
 +
 
 +
* Даже если длина выборки достаточно велика, матрица <tex>\hat\Sigma_y^</tex> все равно может оказаться вырожденной. Это происходит, когда некоторые признаки линейно зависимы. Это так называемая <b>проблема мультиколлинеарности</b>. Более того, признаки могут быть <i>почти</i> линейно зависимы. В этом случае матрица <tex>\hat\Sigma_y^</tex> будет близка к вырожденной, иначе говоря, плохо обусловлена. Такие матрицы обладают рядом неприятных свойств, например при их обращении получаются неустойчивые решения. Положение разделяющей поверхности может сильно непредсказуемо меняться при незначительной вариации обучающих данных.
 +
 
 +
* Выборочные оценки чувствительны к нарушениям нормальности распределений, в частности, к редким большим <b>выбросам</b>. Мат.ожидание в таком случае значительно смещается. При увеличении размерности влияние загрязнений только усиливается.
 +
 
 +
* Если функции правдоподобия классов существенно <b>отличаются от гауссовских</b>, то метод квадратичного дискриминанта будет приводить к алгоритмам низкого качества. Например, когда имеются признаки, принимающие дискретные значения, или когда классы распадаются на изолированные сгустки.
 +
 
 +
== Литература ==
-
# Л.М.Местецкий [http://www.ccas.ru/frc/papers/mestetskii04course.pdf Курс лекций "Математические методы распознавания образов"]
+
#К.В.Воронцов [http://www.machinelearning.ru/wiki/images/e/ed/Voron-ML-Bayes.pdf „Лекции по статистическим (байесовским) алгоритмам классификации“]
 +
#Л.М.Местецкий [http://www.ccas.ru/frc/papers/mestetskii04course.pdf Курс лекций "Математические методы распознавания образов"]
{{Задание|Вера Батурина|Константин Воронцов|6 января 2010}}
{{Задание|Вера Батурина|Константин Воронцов|6 января 2010}}
[[Категория:Непроверенные учебные задания]]
[[Категория:Непроверенные учебные задания]]

Версия 20:25, 5 января 2010

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

Содержание

Основные допущения

  • Выборка независима, то есть
p(x_1 ... x_m)=\prod_{i=1}^m p(x_i)
  • Выборка имеет многомерное нормальное распределение. То есть функция правдоподобия имеет следующий вид:
p(X)=N(X, \mu, \Sigma)=\frac {exp(-\frac {1}{2}(X- \mu)^T \Sigma^{-1} (X- \mu))}{\sqrt{(2 \pi)^n det \Sigma }}

где n - размерность пространства

Оценка параметров

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

\hat \mu = \frac {1}{m} \sum _{i=1}^m x_i
\hat \Sigma = \frac {1}{m} \sum _{i=1}^m (x_i-\hat \mu)(x_i-\hat \mu)^T

Где x_i \in y,

 m - количество элементов в классе y

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

В общем виде, алгоритм Байесовского классификатора имеет вид

a(x)=argmax_{y \in Y} \lambda_y p_y(x) P_y

Иногда вместо самих вероятностей удобнее брать некоторые функции от них:

g_y(x)=f(p_y(x))

где f - монотонно возрастает.

Функция g_y(x) называется дискриминантной функцией, откуда и пошло название самого метода.

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

 a(x)= argmax_{y \in Y} (ln \lambda_y P_y - \frac {1}{2}(x- \hat \mu_y)^T \Sigma^{-1} (x- \hat \mu_y) - \frac {1}{2} ln det {\hat \Sigma_y} )

Теорема: Квадратичный дискриминант имеет квадратичную разделяющую поверхность, которая вырождается в линейную, если ковариационные матрицы классов совпадают.

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

\lambda_s P_s p_s(x)=\lambda_t P_t p_t(x)

После логарифмирования

ln p_s(x)-ln p_t(x)=C_{st}

где C_{st}=ln(\lambda_s P_s /\lambda_t P_t) - константа, не зависящая от x. Разделяющая поверхность в общем случае квадратична, так как ln p_y(x) является квадратичной формой по x.

ln p_y(x)=-\frac {n}{2} ln 2\pi -\frac{1}{2} ln det {\Sigma_y} -\frac{1}{2}(x-\mu_y)^T \Sigma_y^{-1} (x-\mu_y)

Если \Sigma_s=\Sigma_t, то квадратичные члены сокращаются и уравнение разделяющей поверхности вырождается в линейную форму:

(x-\mu_{st})^T \Sigma_y^{-1} (\mu_s-\mu_t)=C_{st}

где \mu_{st}=\frac{1}{2}(\mu_s+\mu_t) - точка посередине между центрами классов.


Имеет ли смысл описывать геометрию разделяющих поверхностей здесь, или лучше оформить это отдельной статьей?


Недостатки

  • Если длина выборки меньше размерности пространства, l_y < n, то матрица \hat\Sigma_y^ становится вырожденной, так как ее ранг не может превышать l_y. В этом случае обратная матрица не существует, и метод неприменим.
  • Даже если длина выборки достаточно велика, матрица \hat\Sigma_y^ все равно может оказаться вырожденной. Это происходит, когда некоторые признаки линейно зависимы. Это так называемая проблема мультиколлинеарности. Более того, признаки могут быть почти линейно зависимы. В этом случае матрица \hat\Sigma_y^ будет близка к вырожденной, иначе говоря, плохо обусловлена. Такие матрицы обладают рядом неприятных свойств, например при их обращении получаются неустойчивые решения. Положение разделяющей поверхности может сильно непредсказуемо меняться при незначительной вариации обучающих данных.
  • Выборочные оценки чувствительны к нарушениям нормальности распределений, в частности, к редким большим выбросам. Мат.ожидание в таком случае значительно смещается. При увеличении размерности влияние загрязнений только усиливается.
  • Если функции правдоподобия классов существенно отличаются от гауссовских, то метод квадратичного дискриминанта будет приводить к алгоритмам низкого качества. Например, когда имеются признаки, принимающие дискретные значения, или когда классы распадаются на изолированные сгустки.

Литература

  1. К.В.Воронцов „Лекции по статистическим (байесовским) алгоритмам классификации“
  2. Л.М.Местецкий Курс лекций "Математические методы распознавания образов"


Данная статья является непроверенным учебным заданием.
Студент: Участник:Вера Батурина
Преподаватель: Участник:Константин Воронцов
Срок: 6 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Личные инструменты