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

Уменьшение размерности и LDA

Предположим, мы работаем с набором данных, содержащим изображения. Наша цель — обучить модель, которая классифицирует изображения по двум или более категориям. Итак, что же представляют собой эти изображения в наборе данных? Это векторы более высоких измерений, над которыми нужно работать, что приводит к большим вычислительным затратам и задержкам. Хорошим примером может служить модель, работающая с генами человека, которая обычно включает в себя огромное количество многомерных данных. Уменьшение размеров может не только сэкономить время и ресурсы, но и помочь избавиться от ненужной сложности.
Линейный дискриминантный анализ (LDA) — это метод, используемый в статистике, распознавании образов и машинном обучении для нахождения линейной комбинации признаки, характеризующие или разделяющие два или более классов объектов или событий. Полученную комбинацию можно использовать в качестве линейного классификатора или, чаще, для уменьшения размерности перед последующей классификацией. Цель состоит в том, чтобы найти ось/оси таким образом, чтобы при проецировании данных обеспечивалось максимальное расстояние между классами и был минимальный разброс или дисперсия данных в каждом классе, что интуитивно является требованием для хороших моделей классификации.
работа LDA почти такая же, как и у PCA, с небольшими отличиями-

  1. PCA — это неконтролируемый метод, в то время как LDA контролируется, т. е. использует метки для обучения.
  2. PCA находит ось, которая максимизирует дисперсию данных, тогда как LDA находит ось, которая максимизирует расстояние между кластерами, минимизируя дисперсию в каждом классе.

Короче говоря, наша цель состоит в том, чтобы найти такие оси, которые помогут нам уменьшить размерность сложного набора данных и в то же время помогут нам эффективно классифицировать данные в желаемые кластеры. Стоит отметить, что для задачи классификации k-класса мы можем найти только первые k-1 таких осей — для набора данных из трех классов мы можем найти только первые две оси, подробности которых будут рассмотрены позже.

Теория и метод

Давайте возьмем набор данных бинарной классификации, который имеет матрицу X = [x₁ x₂ x₃ x₄…] до n точек, где каждая точка в X является вектором размерности d, что делает X матрицей d⨉n. Также у нас есть матрица 1 ⨉ n Y = [y₁ y₂ y₃ y₄ … ], которая содержит кодировки классов, т.е. y ∈ {0,1}, где 0 и 1 представляют кодировки двух классов.
Наша цель — спроецировать точки на ось так, чтобы расстояние между классами было максимальным, а внутренняя дисперсия класса была минимальной. Предположим, что w₁ — это вектор размерности d⨉1, который должен быть одной из наших осей. Таким образом, спроецированные значения x₁ вдоль w₁ будут равны w₁ᵀx₁, где w₁ᵀ транспонировано w₁ с размерностями 1⨉d, что делает произведение масштабируемой величиной. Таким образом, мы пытаемся спроецировать все значения X на w₁.

По определению среднее значение класса 0, представленное как μ₀, равно ⅟ₙ∑xᵢ, так что yᵢ равно 0. Точно так же μ₁ = ⅟ₙ∑xᵢ, так что yᵢ равно 1. Если мы умножим каждый член на w₁ᵀ, новое среднее значение тоже будет умножено на один и тот же фактор, то есть w₁ᵀ.
Итак, теперь, когда у нас есть средства обоих кластеров, наша цель состоит в том, чтобы максимизировать расстояние между ними. Чтобы учесть перспективы отрицательного результата, мы пытаемся максимизировать значение (w₁ᵀμ₀-w₁ᵀμ₁)². По определению,

(w₁ᵀμ₀-w₁ᵀμ₁)² = (w₁ᵀμ₀-w₁ᵀμ₁)ᵀ(w₁ᵀμ₀-w₁ᵀμ₁)
= (μ₀-μ₁)ᵀ(w₁)(w₁ᵀ)(μ₀-μ₁)
)ᵀ(μ₀-μ₁)w₁
= w₁ᵀ Sₑ w₁, где Sₑ — (μ₀-μ₁)ᵀ(μ₀-μ₁) или межклассовая дисперсия

ПРИМЕЧАНИЕ. Описанное выше преобразование возможно, потому что результатом умножения является масштабирование, дающее трассировку масштабирования, а трассировка масштабирования подразумевает, что элементы матрицы можно поворачивать.

Мы также знаем, что формой нахождения ковариации матрицы X является нахождение XXᵀ. Итак,
Дисперсия (w₁ᵀX) = (w₁ᵀX)(w₁ᵀX)ᵀ
⇒ U₁ᵀ(wwᵀ)U₁
⇒ w₁ᵀ∑w₁, где ∑ — ковариационная матрица X размерности d⨉ d
Итак, дисперсия класса для классов 0 и 1 равна w₁ᵀ ∑₀ w₁ и w₁ᵀ ∑₁ w₁ соответственно. Чтобы минимизировать их обоих, мы можем считать их сумму минимальной. Таким образом,
минимальным считается w₁ᵀ(∑₀+∑₁)w₁ или w₁ᵀ(Sᵢ)w₁,
где Sᵢ = ∑₀+∑₁

Теперь у нас есть дисперсия между классом w₁ᵀ Sₑ w₁ и внутриклассовая дисперсия w₁ᵀ Sᵢ w₁, где дисперсия между классом должна быть максимизирована, а внутриклассовая дисперсия должна быть минимизирована. Таким образом, в совокупности их соотношение может быть максимизировано. Это можно сделать, зафиксировав w₁ᵀ Sᵢ w₁ = 1 и максимизировав w₁ᵀ Sₑ w₁.

Теперь мы будем использовать лагранжевую форму для решения уравнения-
L (w₁, λ₁) = (w₁ᵀ Sₑ w₁)-λ₁(w₁ᵀ Sᵢ w₁-1)
Чтобы получить максимальную / седловую точку, мы частично дифференцируем это относительно w₁ и приравняем к 0, и, отбросив сложные вычисления, получим следующее уравнение -
2 Sₑ w₁- 2λ₁Sᵢ w₁ = 0
⇒ Sₑ w₁ = λ₁Sᵢ w₁
⇒ (Sᵢ´ Sₑ) w₁ = λ₁w₁, где Sᵢ´ обратно Sᵢ

которое является представлением пар собственного значения и собственного вектора. Загвоздка здесь в том, что Sₑ является произведением двух векторов 1d и, следовательно, имеет ранг 1. Таким образом, общий ранг произведения будет равен 1.
Следовательно, будет существовать только одна пара собственного вектора и собственного значения.

Расширение до k классов

Теперь мы расширим его до набора данных класса k. Мы заменим w₁ на W = [w₁ w₂ w₃ … wₖ-₁], что, как и ожидалось (для k классов доступно k-1 осей). Итак, размеры W равны d⨉(k-1).

Нам нужно найти способ использовать эту матрицу W для максимизации отношения, поэтому один из способов - возможно использовать след (w₁ᵀ Sₑ w₁) и (w₁ᵀ Sᵢ w₁), что было бы эквивалентно суммированию отдельных отклонений.
Таким образом, Trace(w₁ᵀ Sₑ w₁)/trace(w₁ᵀ Sᵢ w₁) должен быть максимизирован.
Используя аналогичную концепцию лагранжиана, мы получаем уравнение-
trace(w₁ᵀ Sₑ w₁)-λ₁( trace(w₁ᵀ Sᵢ w₁)-1), и это в конечном итоге даст нам k-1 собственных векторов, поскольку (Sᵢ´Sₑ) имеет ранг k-1.

Теперь легко рассчитать Sᵢ, поскольку это просто сумма индивидуальных отклонений в классе. Но найти новый Sₑ с более чем двумя классами было бы проблемой, но у нас есть решение! Мы знаем, что общая дисперсия Sₜ представляет собой сумму дисперсии внутри класса и дисперсии между классами, и вычислить Sₜ легко. Таким образом, обратным вычислением мы получаем Sₑ.

Sₜ = ⅟ₙ∑(xᵢ-μ)(xᵢ-μ)ᵀ, где μ — среднее значение всех xᵢ.

Теперь у нас есть все необходимые значения, и мы можем легко найти первые оси k-1!