Квадратичный дискриминант
Материал из 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> |
- | + | После логарифмирования | |
+ | |||
+ | ::<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
Квадратичный дискриминант - это вариант Байесовского классификатора, который основывается на двух дополнительных допущениях, касающихся вероятностных свойств выборки, а именно - независимость выборки и ее нормальность. Нормальное (гауссово) распределение широко используется по причине вычислительного удобства и адекватности во многих случаях.
Содержание |
Основные допущения
- Выборка независима, то есть
- Выборка имеет многомерное нормальное распределение. То есть функция правдоподобия имеет следующий вид:
где размерность пространства
Оценка параметров
Оценки, основанные на принципе максимума правдоподобия, принимают следующий вид для каждого класса :
Где
количество элементов в классе
Алгоритм классификации
В общем виде, алгоритм Байесовского классификатора имеет вид
Иногда вместо самих вероятностей удобнее брать некоторые функции от них:
где монотонно возрастает.
Функция называется дискриминантной функцией, откуда и пошло название самого метода.
В условиях выдвинутых гипотез удобнее всего взять в качестве функции натуральный логарифм, и тогда алгоритм приобретает следующий вид:
Теорема: Квадратичный дискриминант имеет квадратичную разделяющую поверхность, которая вырождается в линейную, если ковариационные матрицы классов совпадают.
Доказательство: Поверхность, разделяющая классы и , описывается уравнением
После логарифмирования
где константа, не зависящая от . Разделяющая поверхность в общем случае квадратична, так как является квадратичной формой по .
Если , то квадратичные члены сокращаются и уравнение разделяющей поверхности вырождается в линейную форму:
где точка посередине между центрами классов.
Имеет ли смысл описывать геометрию разделяющих поверхностей здесь, или лучше оформить это отдельной статьей? |
Недостатки
- Если длина выборки меньше размерности пространства, , то матрица становится вырожденной, так как ее ранг не может превышать . В этом случае обратная матрица не существует, и метод неприменим.
- Даже если длина выборки достаточно велика, матрица все равно может оказаться вырожденной. Это происходит, когда некоторые признаки линейно зависимы. Это так называемая проблема мультиколлинеарности. Более того, признаки могут быть почти линейно зависимы. В этом случае матрица будет близка к вырожденной, иначе говоря, плохо обусловлена. Такие матрицы обладают рядом неприятных свойств, например при их обращении получаются неустойчивые решения. Положение разделяющей поверхности может сильно непредсказуемо меняться при незначительной вариации обучающих данных.
- Выборочные оценки чувствительны к нарушениям нормальности распределений, в частности, к редким большим выбросам. Мат.ожидание в таком случае значительно смещается. При увеличении размерности влияние загрязнений только усиливается.
- Если функции правдоподобия классов существенно отличаются от гауссовских, то метод квадратичного дискриминанта будет приводить к алгоритмам низкого качества. Например, когда имеются признаки, принимающие дискретные значения, или когда классы распадаются на изолированные сгустки.
Литература
- К.В.Воронцов „Лекции по статистическим (байесовским) алгоритмам классификации“
- Л.М.Местецкий Курс лекций "Математические методы распознавания образов"
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |