Объяснение линейного дискриминантного анализа

• Правило максимального правдоподобия: если мы предполагаем, что каждый класс может возникнуть с равной вероятностью, тогда отнесите x к классу j, если

• Байесовское правило: если мы знаем априорные вероятности класса, π, то относим x к классу j, если

Линейный и квадратичный дискриминантный анализ

Если мы предположим, что данные получены из многомерного распределения Гаусса, то есть распределение X может быть охарактеризовано его средним значением (μ) и ковариацией ( Σ) можно получить явные формы приведенных выше правил распределения. Следуя байесовскому правилу, мы относим данные x к классу j, если они имеют наибольшую вероятность среди всех классов K для i = 1,…, K:

Вышеупомянутая функция называется дискриминантной функцией. Обратите внимание на использование логарифмической вероятности здесь. Другими словами, дискриминантная функция сообщает нам, насколько вероятны данные x каждого класса. Граница решения, разделяющая любые два класса, k и l, следовательно, представляет собой набор x, где две дискриминантные функции имеют одинаковое значение. Следовательно, любые данные, попадающие на границу принятия решения, равновероятны из двух классов (мы не могли решить).

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

Обратите внимание, что это линейная функция от x. Таким образом, граница принятия решения между любой парой классов также является линейной функцией от x, причина ее названия: линейный дискриминантный анализ. Без предположения о равной ковариантности квадратичный член в вероятности не сокращается, поэтому результирующая дискриминантная функция является квадратичной функцией по x:

В этом случае граница решения квадратична по x. Это известно как квадратичный дискриминантный анализ (QDA).

Что лучше? LDA или QDA?

В реальных задачах параметры генеральной совокупности обычно неизвестны и оцениваются на основе обучающих данных как выборочные средние и выборочные ковариационные матрицы. Хотя QDA предусматривает более гибкие границы принятия решений по сравнению с LDA, количество параметров, которые необходимо оценить, также увеличивается быстрее, чем у LDA. Для LDA необходимы параметры (p + 1) для построения дискриминантной функции в (2). Для проблемы с классами K нам потребуется только (K-1) таких дискриминантных функций, произвольно выбирая один класс в качестве базового (вычитая вероятность базового класса из все остальные классы). Следовательно, общее количество оценочных параметров для LDA составляет (K-1) (p + 1).

С другой стороны, для каждой дискриминантной функции QDA в (3) необходимо оценить вектор среднего, ковариационную матрицу и класс:
- Среднее: p
- Ковариация : p (p + 1) / 2
- Предыдущий класс: 1
Аналогично, для QDA нам нужно оценить (K-1) {p (p + 3) / 2 + 1} параметров.

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

Лучшее из двух миров? Компромисс между LDA и QDA

Мы можем найти компромисс между LDA и QDA, упорядочив ковариационные матрицы отдельных классов. Регуляризация означает, что мы накладываем определенные ограничения на предполагаемые параметры. В этом случае мы требуем, чтобы индивидуальная ковариационная матрица сжималась до общей объединенной ковариационной матрицы через параметр штрафа, например α:

Общая ковариационная матрица также может быть преобразована в единичную матрицу с помощью параметра штрафа, например β:

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

Расчет для LDA

Из (2) и (3) видно, что вычисления дискриминантных функций можно упростить, если сначала диагонализовать ковариационные матрицы. То есть данные преобразуются, чтобы иметь единичную ковариационную матрицу (без корреляции, дисперсия 1). В случае LDA вот как мы продолжим вычисления:

Шаг 2 сферирует данные для создания единичной ковариационной матрицы в преобразованном пространстве. Шаг 4 получается, следуя (2).

Давайте рассмотрим пример из двух классов, чтобы увидеть, что на самом деле делает LDA. Предположим, есть два класса: k и l. Мы относим x к классу k, если

Вышеупомянутое условие означает, что класс k с большей вероятностью будет генерировать данные x, чем класс l. Следуя четырем шагам, описанным выше, мы пишем

То есть мы классифицируем данные x в класс k, если

Производное правило распределения показывает работу LDA. Левая часть (l.h.s.) уравнения - это длина ортогональной проекции x * на отрезок прямой, соединяющий два средних класса. Правая часть - это местоположение центра сегмента, скорректированного с учетом априорных вероятностей класса. По сути, LDA классифицирует сферические данные по ближайшему среднему классу. Здесь можно сделать два наблюдения:

1. Точка принятия решения отклоняется от средней точки, когда априорные вероятности класса не совпадают, то есть граница сдвигается к классу с меньшей априорной вероятностью.
2. Данные проецируются на пространство, охватываемое средствами класса (умножение x * и среднее вычитание на левой стороне правила). Затем в этом пространстве производятся сравнения расстояний.

LDA пониженного ранга

То, что я только что описал, является LDA для классификации. LDA также славится своей способностью находить небольшое количество значимых измерений, что позволяет нам визуализировать и решать многомерные проблемы. Что мы подразумеваем под значимым и как LDA находит эти измерения? Мы ответим на эти вопросы в ближайшее время.

Во-первых, взгляните на график ниже. Для задачи классификации вин с тремя различными типами вин и 13 входными переменными график визуализирует данные в двух дискриминантных координатах, найденных LDA. В этом двумерном пространстве классы могут быть хорошо разделены. Для сравнения, классы не так четко разделены с использованием первых двух основных компонентов, обнаруженных PCA.

Уменьшение размеров, присущее LDA

В приведенном выше примере с вином 13-мерная проблема визуализирована в 2-м пространстве. Почему это возможно? Это возможно, потому что LDA имеет естественное уменьшение размеров. Из предыдущего раздела мы заметили, что LDA выполняет сравнение расстояний в пространстве, охватываемом различными классовыми средствами. Две различные точки лежат на 1-й линии; три различные точки лежат на 2-й плоскости. Точно так же класс K означает, что он лежит на гиперплоскости с числом измерений не более (K-1). В частности, подпространство, натянутое таким образом, есть

При сравнении расстояний в этом пространстве расстояния, ортогональные этому подпространству, не добавят никакой информации, поскольку они вносят одинаковый вклад для каждого класса. Следовательно, ограничение сравнений расстояний только этим подпространством не потеряло бы никакой информации, полезной для классификации LDA. Это означает, что мы можем безопасно преобразовать нашу задачу из p -мерной проблемы в (K-1) -мерную проблему с помощью ортогональной проекции данных на это подпространство. Когда p намного больше, чем K, это означает значительное уменьшение количества измерений.

Что, если мы хотим еще больше уменьшить размер с p до L, например двухмерный с L = 2? Мы можем попытаться построить L -мерное подпространство из (K-1) -мерного пространства, и это подпространство в некотором смысле оптимально для LDA-классификации.

Какое подпространство было бы оптимальным?

Фишер предполагает, что гораздо меньшее L -мерное подпространство является оптимальным, когда средние класса сферических данных в этом пространстве имеют максимальное разделение с точки зрения дисперсии. Следуя этому определению, оптимальные координаты подпространства просто находятся путем выполнения PCA со средними значениями сферического класса, поскольку PCA находит направление максимальной дисперсии. Шаги вычислений кратко описаны ниже:

С помощью этой процедуры мы заменяем наши данные с X на Z и уменьшаем размер проблемы с p до L. Дискриминантные координаты 1 и 2 на предыдущем графике вина находятся с помощью этой процедуры, задав L = 2. Повторение предыдущих процедур LDA для классификации с использованием новых данных называется LDA пониженного ранга.

LDA Фишера

Если вывод предыдущего LDA пониженного ранга сильно отличается от того, что вы знали раньше, вы не одиноки! А вот и откровение. Фишер произвел этапы вычислений в соответствии со своим определением оптимальности другим способом ». Его шаги по выполнению LDA пониженного ранга позже будут известны как дискриминантный анализ Фишера.

Fisher не делает никаких предположений относительно распределения данных. Вместо этого он пытается найти «разумное» правило, чтобы упростить задачу классификации. В частности, Фишер находит линейную комбинацию исходных данных, где межклассовая дисперсия B = cov (M) максимизируется относительно дисперсии внутри класса, W, как определено в (6).

График ниже, взятый из ESL², показывает, почему это правило имеет интуитивный смысл. Правило устанавливает направление, a, где после проецирования данных на это направление средние классы имеют максимальное разделение между ними, а каждый класс имеет минимальную дисперсию в пределах их. Направление проекции, найденное в соответствии с этим правилом, показанное на правом графике, значительно упрощает классификацию.

В поисках направления: путь Фишера

Используя разумное правило Фишера, нахождение оптимального направления (направлений) проекции сводится к решению задачи оптимизации:

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

После решения задачи оптимальные координаты подпространства, также известные как дискриминантные координаты, получаются как собственные векторы inv (W) ∙ B. It можно показать, что эти координаты совпадают с координатами преобразования X в Z в приведенной выше формулировке LDA с пониженным рангом.

Удивительно, но Фишер пришел к этим дискриминантным координатам без какого-либо гауссовского предположения о популяции, в отличие от формулировки LDA с пониженным рангом. Есть надежда, что с этим разумным правилом LDA будет работать хорошо, даже когда данные не следует точно распределению Гаусса.

Проблема с рукописными цифрами

Вот пример, демонстрирующий возможности визуализации и классификации LDA Фишера или просто LDA. Нам нужно распознать десять разных цифр, то есть от 0 до 9, используя 64 переменных (значения пикселей из изображений). Набор данных взят отсюда. Во-первых, мы можем визуализировать обучающие изображения, и они выглядят следующим образом:

Затем мы обучаем классификатор LDA на первой половине данных. Решение обобщенной проблемы собственных значений, упомянутой ранее, дает нам список оптимальных направлений проекции. В этой задаче мы сохраняем четыре верхних координаты, а преобразованные данные показаны ниже.

Приведенный выше график позволяет нам интерпретировать обученный классификатор LDA. Например, координата 1 помогает сопоставить 4 и 2/3, тогда как координата 2 противопоставляет 0 и 1. Впоследствии координаты 3 и 4 помогают различать цифры, плохо разделенные в координатах 1 и 2. Мы тестируем обученный классификатор, используя другую половину набора данных. Отчет ниже резюмирует результат.

Наивысшая точность составляет 99%, а самая низкая - 77%, что является достойным результатом, учитывая, что метод был предложен около 70 лет назад. Кроме того, мы не сделали ничего, чтобы улучшить процедуру для этой конкретной проблемы. Например, есть коллинеарность входных переменных, и параметр усадки может быть неоптимальным.

Резюме LDA

Достоинства LDA:

1. Простой прототип классификатора: используется расстояние до среднего класса, его легко интерпретировать.
2. Граница принятия решения линейна: ее легко реализовать, а классификация надежна.
3. Уменьшение размеров: это обеспечивает информативное низкоразмерное
   представление данных, которое полезно как для визуализации, так и для проектирования функций.

Недостатки LDA:

1. Границы линейных решений могут не разделять классы должным образом. Желательна поддержка более общих границ.
2. В параметрах большой размерности LDA использует слишком много параметров. Желательна упорядоченная версия LDA.
3. Желательна поддержка более сложной классификации прототипов.

Спасибо, что дочитали до конца! В следующем разделе будет представлен гибкий, штрафной и смешанный дискриминантный анализ для устранения каждого из трех недостатков LDA. С этими обобщениями LDA может взять на себя гораздо более сложные и сложные проблемы, такие как та, которая показана на изображении функции.

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

использованная литература

1. Р. А., Фишер, Использование множественных измерений в таксономических проблемах (1936), Annals of Eugenics, 7 (2), 179–188.
2. Дж. Фридман, Т. Хасти и Р. Тибширани, Элементы статистического обучения (2001), Серия Спрингера в статистике.
3. К. В. Мардиа, Дж. Т. Кент и Дж. М. Бибби, Многомерный анализ (1979), Вероятность и математическая статистика, Academic Press Inc.