Линейный дискриминантный анализ - это всего лишь три линии псевдокода ...

LDA в форме пониженного ранга

Навигация

Это конспекты лекции FAU на YouTube Распознавание образов. Это полная стенограмма видео лекции и соответствующие слайды. Исходники слайдов доступны здесь. Надеемся, вам понравится это не меньше, чем видео. Эта стенограмма была почти полностью сгенерирована машиной с использованием AutoBlog, и в нее были внесены лишь незначительные изменения вручную. Если вы заметили ошибки, сообщите нам об этом!

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

Предыдущая глава / Посмотреть это видео / Следующая глава / Верхний уровень

Добро пожаловать в раздел «Распознавание образов»! Сегодня мы хотим изучить реальный линейный дискриминантный анализ и то, как его вычислить в форме с пониженным рангом.

Сегодня мы переходим к дискриминантному анализу. И то, о чем мы сегодня говорим, - это так называемый линейный дискриминантный анализ с пониженным рангом. Мы уже видели, что наша проблема заключалась в том, как выбрать L-мерное подпространство с L = K-1, где K - количество классов. Предполагается, что это подпространство, подходящее для этого линейного дискриминантного анализа. Теперь идея, которой мы хотим следовать, состоит в том, чтобы максимизировать распространение L-мерной проекции центроидов. Мы уже знаем метод, который может это сделать, и это так называемый анализ главных компонент. Итак, мы вычисляем главные компоненты ковариации средних векторов. Вы помните, что мы, конечно, можем преобразовать наши средние векторы с помощью Φ. И тогда мы можем сделать это для всех наших классов.

Анализ главных компонентов, как вы, возможно, знаете из «Введение в распознавание образов», представляет собой отображение, которое вычисляет линейное преобразование Φ. Это приводит к наибольшему разбросу проектируемых функций. Итак, у этого есть целевая функция, и здесь мы ищем преобразование Φ *, которое является максимальным по этому члену. Этот термин может показаться немного сложным, но вы можете видеть, что это уже версия для наших классов. Итак, мы берем средние наших классов y, затем вычитаем расстояние до других средних и, по сути, берем L₂ норму этих преобразованных матриц. Теперь мы вводим норму L₂ как скалярное произведение двух векторов. И затем, конечно, мы вычисляем среднее значение по всем классам K. И в то же время мы применяем регуляризацию. Итак, вы видите здесь, с правой стороны, у нас есть дополнительная регуляризация. По сути, это сумма различных условий регуляризации. И здесь вы видите, что это λᵢ, умноженное на норму L₂ для Φᵢ, где Φᵢ - это, по сути, восьмой вектор-строка матрицы Φ. По сути, это означает, что мы ищем матрицу, в которой отдельные векторы-строки имеют норму, равную единице. Метод, который мы используем для введения этих ограничений, заключающийся в том, что векторы-строки имеют длину, равную единице, задается так называемыми множителями Лагранжа. Обратите внимание, что мы должны ввести такой вид регуляризации, эти ограничения. Поскольку мы делаем максимизацию по пространству преобразований, они могут очень легко максимизировать левый член нашей задачи максимизации, просто максимизируя все элементы Φ. Итак, если я позволю им уйти в бесконечность, то я также получу максимизацию всего члена. Однако это не то, что мы ищем, поэтому нам необходимо ввести эти ограничения.

А теперь вернемся к нашей исходной проблеме. И одна вещь, которую я хочу использовать в дальнейшем, - это два ярлыка из кулинарной книги матрицы. Опять же, вот ссылка на кулинарную книгу матрицы «www.matrixcookbook.com». Вам, ребята, это должно быть легко запомнить. И здесь мы будем использовать следующие два тождества. Итак, первое: если у нас есть какое-то ожидаемое значение, которое следует за средним вектором μ и ковариацией Σ, то мы можем заменить это ожидаемое значение и преобразование отдельных характеристик x преобразованием A. Это может быть переписывается в след A Σ Aᵀ + (A μ) ᵀ (A μ). Также обратите внимание, что в этом тождестве, если бы у меня была нормализация к μ, равной 0, поэтому я заставляю по существу все быть центрированным, тогда член справа будет сокращен. Таким образом, у нас будет только след матрицы A, умноженный на матрицу ковариации, умноженную на Aᵀ. Этот след довольно интересен. Это подводит нас ко второму ярлыку, матричной производной трассы по отношению к A. Или в следующий раз это будет X. Итак, если вы действительно заинтересованы в вычислении этой частной производной по X, вы видите это все еще такая же настройка, что и график в строке выше. Затем это можно переписать в X Bᵀ + X B. Теперь очень интересно то, что если бы B была ковариационной матрицей, то транспонирование по существу не изменило бы матрицу, потому что это метрика. Таким образом, вы даже можете записать это как 2X + B.

Давайте посмотрим на наш линейный дискриминантный анализ с пониженным рангом. Здесь мы видим, что можем немного изменить это. Итак, вы видите, что преобразование нашей функции применяется к нашим средствам класса, а также ко всем другим средствам. Это означает, что мы действительно можем вытащить этого парня. Таким образом, мы получаем разницу между средними классами и всеми остальными средствами или, по сути, полное преобразование средних. Это означает, что наше распределение является средним свободным, поэтому у нас есть вектор среднего значения 0 в преобразованном пространстве. Затем это позволяет нам использовать предыдущий трюк с трассировкой. Здесь вы видите, что у нас есть просто матрица межклассовой ковариации. И затем у нас есть след, умноженный на матрицу ковариации между классами, по сути, матрицу ковариации средних векторов, и она снова умножается на Φᵀ. Итак, вы видите, что два других члена, которые были введены в матричную кулинарную книгу, отменяются, потому что наше распределение в этом случае является практически бесплатным, что затем исключает это из нашего уравнения.

Теперь вы видите, что у нас есть эта трасса, и мы знаем из нашей поваренной книги матриц, что можем упростить эту трассу, записав это как Φ, умноженное на взаимную ковариацию, плюс Φ, умноженную на ковариацию между транспонированием. И это, конечно, мы можем переписать как 2 раза Φ Σinter, и в правой части у нас есть производная от L₂ нормы. Эту производную по норме L₂ мы можем просто записать как удвоенное количество лагранжевых множителей в векторе. И тогда мы получаем наше исходное преобразование признаков Φ. Итак, вы видите, что мы можем немного упростить это, и это обязательно должно быть равно нулю. Вы можете видеть, что если мы разделим теперь на два, это, по сути, дает нам проблему собственных значений и собственных векторов Σinter Φᵀ = λ′Φᵀ. Заметим, что мы, по сути, избавились от минуса, введя это λ ′. Взгляните сюда, это из оригинального PCA. Там матрица преобразования создается путем максимизации разброса по всем функциям с использованием ковариационной матрицы всех функций. Здесь вы, по сути, сталкиваетесь с проблемой, что у вас есть Σ, а затем Φᵀ равно λ ′ и Φᵀ снова. Итак, снова у нас есть проблема с собственным вектором и собственным значением, которую затем, конечно, можно вычислить, просто вычислив собственные значения и собственные векторы наших соответствующих ковариационных матриц. Итак, для линейного дискриминантного анализа с пониженным рангом вам необходимо применить его к ковариационной матрице между классами. А в обычном PCA вы применили бы его к обычной ковариационной матрице.

Давайте посмотрим на шаги, необходимые для вычисления линейного дискриминантного анализа с пониженным рангом. Итак, мы продолжаем и вычисляем ковариационную матрицу преобразованных векторов средних значений. В первом шаге из предыдущего видео вы помните, что мы сначала применяем нормализацию по отношению к общей ковариационной матрице и преобразуем ее в это нормализованное пространство. И затем мы вычисляем в этом нормализованном пространстве ковариацию по средним нашим классам. И тогда среднее значение - это, конечно, среднее значение всех средних векторов. Теперь вы вычисляете L собственных векторов ковариационной матрицы, принадлежащих наибольшим собственным значениям. Очевидно, это можно сделать с помощью стандартного анализа собственных значений. И затем вы по существу выбираете собственные векторы, которые затем становятся строками отображения Φ из измерения K - 1 в L пространства признаков. Это дает нам выходную матрицу Φ.

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

Если вам понравился этот пост, вы можете найти «больше эссе здесь», больше образовательных материалов по машинному обучению «здесь» или взглянуть на нашу «Лекцию» «Глубокое обучение». Я также был бы признателен за подписку на «YouTube», «Twitter», «Facebook» или «LinkedIn», если вы хотите получать информацию о новых эссе, видео и исследованиях в будущем. Эта статья выпущена под лицензией «Creative Commons 4.0 Attribution License» и может быть перепечатана и изменена при наличии ссылки. Если вас интересует создание стенограмм видеолекций, попробуйте «Автоблог».

Линейный дискриминантный анализ - это всего лишь три линии псевдокода ...

Ллойд Н. Трефетен, Дэвид Бау III: Численная линейная алгебра, SIAM, Филадельфия, 1997.

  • Matrix Cookbook, «https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf»
  • Т. Хасти, Р. Тибширани и Дж. Фридман: элементы статистического обучения - интеллектуальный анализ данных, вывод и прогнозирование. 2-е издание, Спрингер, Нью-Йорк, 2009.
  • Б. Эскофьер, Ф. Хениг, П. Кюнер: Классификация воспринимаемой усталости при беге в цифровом спорте, Труды 19-й Международной конференции по распознаванию образов (ICPR 2008), Тампа, Флорида, США, 2008 г.
  • М. Шпигель, Д. Хан, В. Даум, Дж. Ваза, Дж. Хорнеггер: Сегментация почек с использованием новой техники создания модели активной формы, основанной на нежесткой регистрации изображений, Компьютерная медицинская визуализация и графика 2009 33 (1): 29–39
  • Если вы забыли о множителях Лагранжа, давайте напомним. Как правило, это метод включения ограничений в оптимизацию. Мы будем использовать эту технику довольно часто для остальной части этого класса. Так что, если у вас возникли проблемы с этим, вы можете обратиться к учебнику по математике, чтобы познакомиться с этой концепцией. Давайте рассмотрим простой пример. Здесь у нас есть просто функция x + y. Вы уже видите, как и в предыдущем примере, это не ограниченная функция. Итак, если мы хотим максимизировать x + y, мы просто перейдем к x или y в сторону бесконечности, и это, по сути, даст нам максимум этой функции. В общем, это не очень приятно. Что ж, на самом деле это довольно легко оптимизировать, потому что я могу посмотреть на функцию и сказать, что максимум находится на бесконечности. Так что это может быть быстрое решение, но оно не очень полезно. Поэтому в подобных случаях вы можете захотеть работать с ограничениями. Теперь ограничение, которое мы выбираем здесь в качестве примера, - x² + y² = 1, что означает, что я хочу иметь решения на круге, который я показываю здесь на графике. Что мне теперь нужно сделать, так это объединить ограничение и нашу максимизацию. По сути, это требует решения, в котором мы отображаем наш круг на пространство решений. И затем наш допустимый набор здесь обозначен деформированным кругом, поэтому наши решения должны лежать на этом конкретном круге. В противном случае мы бы не выполнили ограничение. Как я могу внести это в оптимизацию? Что ж, один из подходов - это множители Лагранжа. И это подводит нас к функции Лагранжа. Здесь я беру исходную задачу максимизации, а затем добавляю ограничение с множителем λ. Этот λ затем используется для обеспечения соблюдения этого ограничения. Теперь вы видите, что наша исходная функция зависела от x и y, а функция Лагранжа теперь зависит от x, y и λ. Таким образом, λ - это, по сути, увеличение размерности. И в этом многомерном пространстве мы можем видеть, что все решения, которые являются решениями нашей регуляризованной задачи, должны удовлетворять ограничению, что частная производная или градиент для всех переменных должны быть равны нулю. Итак, вы видите, что мы вычисляем частную производную лагранжиана по x, y и λ и устанавливаем ее равной нулю. Теперь вы могли бы сказать, что я мог бы максимизировать то же самое в исходной функции, вычислив частичные значения с x и y. Но мы, по сути, вводим эту дополнительную координату. Вы увидите, что только критические точки в этом многомерном пространстве, где производная по λ равна 0, по существу являются решениями на допустимом множестве. И если мы посмотрим на функцию Лагранжа, если я вычислю частную производную для λ, по существу исходная цель, x и y, будет сокращаться, потому что они не зависят от λ. Все, что осталось, это x ² + y ² - 1. Это должно быть 0, поэтому я могу решить его для x ² + y ² = 1. Вы видите, что, по сути, принудительное выполнение частной производной по отношению к λ, равному 0, создает необходимое условие. Итак, наши критические места могут существовать в этом месте только при выполнении условия. Таким образом, все критические позиции в этом пространстве будут иметь хотя бы необходимое условие выполнения ограничения. Это очень хорошая идея того, как мы можем отобразить нашу исходную проблему в более высокомерном пространстве и решить по существу обе задачи оптимизации, сохранив ограничение. В этом конкретном случае, поскольку x ² + y ² = 1 является ограничением нормы, это очень близко к регуляризации. Что вы довольно часто видите в классах, которые больше изучают реализованные и инженерные решения, так это то, что их интерпретация λ является своего рода инженерной константой. Таким образом, они просто устанавливают значение для λ, конечно, значение, которое затем выбирается пользователем. И вы можете видеть, что любое нарушение ограничения в этом случае, поэтому, если мы не на круге, приведет к затратам. И если вы выберете тогда λ соответствующим образом, вы, по сути, заставите решения тянуться к кругу, потому что не нахождение на круге приведет к затратам. Тогда вы также, скорее всего, найдете решения. Тем не менее, на самом деле лямбда - это увеличение размерности, а лямбда - это фактически одна из наших переменных поиска, так что мы можем решить эту проблему оптимизации. Очень краткий учебник по лагранжевой оптимизации.