Дискриминантный анализ Кернела Фишера

В статистике используется ядерный дискриминантный анализ Фишера (KFD) , также известный как обобщенный дискриминантный анализ и ядерный дискриминантный анализ , представляет собой ядерную версию линейного дискриминантного анализа (LDA). Он назван в честь Рональда Фишера .

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

Интуитивно понятно, что идея LDA состоит в том, чтобы найти проекцию, в которой разделение классов будет максимальным. Учитывая два набора помеченных данных, $\mathbf {C} _{1}$ и $\mathbf {C} _{2}$, мы можем вычислить среднее значение каждого класса, $\mathbf {m} _{1}$ и $\mathbf {m} _{2}$, как

$\mathbf {m} _{i}={\frac {1}{l_{i}}}\sum _{n=1}^{l_{i}}\mathbf {x} _{n}^{i},$

где $l_{i}$ количество примеров класса $\mathbf {C} _{i}$. Цель линейного дискриминантного анализа — обеспечить большое разделение средних классов, сохраняя при этом небольшую дисперсию внутри класса. Это формулируется как максимизация по отношению к $\mathbf {w}$, следующее соотношение:

$J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }},$

где $\mathbf {S} _{B}$ - ковариационная матрица между классами и $\mathbf {S} _{W}$ — общая ковариационная матрица внутри класса:

${\begin{aligned}\mathbf {S} _{B}&=(\mathbf {m} _{2}-\mathbf {m} _{1})(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\\\mathbf {S} _{W}&=\sum _{i=1,2}\sum _{n=1}^{l_{i}}(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})^{\text{T}}.\end{aligned}}$

Максимум указанного соотношения достигается при

$\mathbf {w} \propto \mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).$

как можно показать с помощью метода множителей Лагранжа (эскиз доказательства):

Максимизация $J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }}$ эквивалентно максимизации

$\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w}$

при условии

$\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} =1.$

Это, в свою очередь, эквивалентно максимизации $I(\mathbf {w} ,\lambda )=\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} -\lambda (\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} -1)$, где $\lambda$ – множитель Лагранжа.

В максимуме производные $I(\mathbf {w} ,\lambda )$ относительно $\mathbf {w}$ и $\lambda$ должно быть равно нулю. принимая ${\frac {dI}{d\mathbf {w} }}=\mathbf {0}$ урожайность

$\mathbf {S} _{B}\mathbf {w} -\lambda \mathbf {S} _{W}\mathbf {w} =\mathbf {0} ,$

что тривиально удовлетворяется $\mathbf {w} =c\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1})$ и $\lambda =(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).$

Расширение LDA

Чтобы расширить LDA до нелинейных отображений, данные в виде $\ell$ очки $\mathbf {x} _{i},$ могут быть сопоставлены с новым пространством объектов, $F,$ через какую-то функцию $\phi .$ В этом новом пространстве функций функция, которую необходимо максимизировать, равна

$J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} }},$

где

${\begin{aligned}\mathbf {S} _{B}^{\phi }&=\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)^{\text{T}}\\\mathbf {S} _{W}^{\phi }&=\sum _{i=1,2}\sum _{n=1}^{l_{i}}\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)^{\text{T}},\end{aligned}}$

и

$\mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\sum _{j=1}^{l_{i}}\phi (\mathbf {x} _{j}^{i}).$

Далее, обратите внимание, что $\mathbf {w} \in F$. Явное вычисление отображений $\phi (\mathbf {x} _{i})$ и тогда выполнение LDA может оказаться дорогостоящим в вычислительном отношении и во многих случаях неразрешимым. Например, $F$ может быть бесконечномерным. Таким образом, вместо того, чтобы явно сопоставлять данные с $F$данные могут быть неявно внедрены путем переписывания алгоритма с использованием скалярных произведений и использования функций ядра, в которых скалярное произведение в новом пространстве признаков заменяется функцией ядра, $k(\mathbf {x} ,\mathbf {y} )=\phi (\mathbf {x} )\cdot \phi (\mathbf {y} )$.

LDA можно переформулировать в терминах скалярного произведения, заметив сначала, что $\mathbf {w}$ будет иметь расширениеформа

$\mathbf {w} =\sum _{i=1}^{l}\alpha _{i}\phi (\mathbf {x} _{i}).$

Тогда обратите внимание, что

$\mathbf {w} ^{\text{T}}\mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\sum _{j=1}^{l}\sum _{k=1}^{l_{i}}\alpha _{j}k\left(\mathbf {x} _{j},\mathbf {x} _{k}^{i}\right)=\mathbf {\alpha } ^{\text{T}}\mathbf {M} _{i},$

где

$(\mathbf {M} _{i})_{j}={\frac {1}{l_{i}}}\sum _{k=1}^{l_{i}}k(\mathbf {x} _{j},\mathbf {x} _{k}^{i}).$

Числитель $J(\mathbf {w} )$ тогда можно записать как:

$\mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} =\mathbf {w} ^{\text{T}}\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)^{\text{T}}\mathbf {w} =\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } ,\qquad {\text{where}}\qquad \mathbf {M} =(\mathbf {M} _{2}-\mathbf {M} _{1})(\mathbf {M} _{2}-\mathbf {M} _{1})^{\text{T}}.$

Аналогично знаменатель можно записать как

$\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} =\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } ,\qquad {\text{where}}\qquad \mathbf {N} =\sum _{j=1,2}\mathbf {K} _{j}(\mathbf {I} -\mathbf {1} _{l_{j}})\mathbf {K} _{j}^{\text{T}},$

с $n^{\text{th}},m^{\text{th}}$ компонент $\mathbf {K} _{j}$ определяется как $k(\mathbf {x} _{n},\mathbf {x} _{m}^{j}),\mathbf {I}$ - единичная матрица, и $\mathbf {1} _{l_{j}}$ матрица со всеми элементами, равными $1/l_{j}$. Это тождество можно получить, начав с выражения для $\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w}$ и используя расширение $\mathbf {w}$ и определения $\mathbf {S} _{W}^{\phi }$ и $\mathbf {m} _{i}^{\phi }$

${\begin{aligned}\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} &=\left(\sum _{i=1}^{l}\alpha _{i}\phi ^{\text{T}}(\mathbf {x} _{i})\right)\left(\sum _{j=1,2}\sum _{n=1}^{l_{j}}\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)^{\text{T}}\right)\left(\sum _{k=1}^{l}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\phi ^{\text{T}}(\mathbf {x} _{i})\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)^{\text{T}}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{p=1}^{l_{j}}\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})\right)\left(\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{q=1}^{l_{j}}\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\alpha _{k}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {2\alpha _{i}\alpha _{k}}{l_{j}}}\sum _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})+{\frac {\alpha _{i}\alpha _{k}}{l_{j}^{2}}}\sum _{p=1}^{l_{j}}\sum _{q=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\alpha _{k}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {\alpha _{i}\alpha _{k}}{l_{j}}}\sum _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})\right)\right)\\[6pt]&=\sum _{j=1,2}\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {K} _{j}^{\text{T}}\mathbf {\alpha } -\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {1} _{l_{j}}\mathbf {K} _{j}^{\text{T}}\mathbf {\alpha } \\[4pt]&=\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } .\end{aligned}}$

Используя эти уравнения для числителя и знаменателя $J(\mathbf {w} )$, уравнение для $J$ можно переписать как

$J(\mathbf {\alpha } )={\frac {\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } }{\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } }}.$

Тогда дифференцирование и приравнивание к нулю дает

$(\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } )\mathbf {N} \mathbf {\alpha } =(\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } )\mathbf {M} \mathbf {\alpha } .$

Поскольку только направление $\mathbf {w}$, а, следовательно, и направление $\mathbf {\alpha } ,$ вопросы, вышеизложенное может быть решено для $\mathbf {\alpha }$ как

$\mathbf {\alpha } =\mathbf {N} ^{-1}(\mathbf {M} _{2}-\mathbf {M} _{1}).$

Обратите внимание, что на практике $\mathbf {N}$ обычно имеет единственное число, поэтому к нему добавляется кратное тождеству

$\mathbf {N} _{\epsilon }=\mathbf {N} +\epsilon \mathbf {I} .$

Учитывая решение для $\mathbf {\alpha }$, проекция новой точки данных определяется выражением

$y(\mathbf {x} )=(\mathbf {w} \cdot \phi (\mathbf {x} ))=\sum _{i=1}^{l}\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} ).$

Мультиклассовый КФД

Распространение на случаи, когда существует более двух классов, относительно просто. Позволять $c$ быть числом классов. Затем многоклассовый KFD предполагает проецирование данных в $(c-1)$-мерное пространство с использованием $(c-1)$ дискриминантные функции

$y_{i}=\mathbf {w} _{i}^{\text{T}}\phi (\mathbf {x} )\qquad i=1,\ldots ,c-1.$

Это можно записать в матричной записи

$\mathbf {y} =\mathbf {W} ^{\text{T}}\phi (\mathbf {x} ),$

где $\mathbf {w} _{i}$ это столбцы $\mathbf {W}$. Кроме того, ковариационная матрица между классами теперь имеет вид

$\mathbf {S} _{B}^{\phi }=\sum _{i=1}^{c}l_{i}(\mathbf {m} _{i}^{\phi }-\mathbf {m} ^{\phi })(\mathbf {m} _{i}^{\phi }-\mathbf {m} ^{\phi })^{\text{T}},$

где $\mathbf {m} ^{\phi }$ является средним значением всех данных в новом пространстве признаков. Ковариационная матрица внутри класса:

$\mathbf {S} _{W}^{\phi }=\sum _{i=1}^{c}\sum _{n=1}^{l_{i}}(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi })(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi })^{\text{T}},$

Решение теперь получается путем максимизации

$J(\mathbf {W} )={\frac {\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {W} \right|}{\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {W} \right|}}.$

Снова можно использовать трюк с ядром, и цель многоклассового KFD становится

$\mathbf {A} ^{*}={\underset {\mathbf {A} }{\operatorname {argmax} }}={\frac {\left|\mathbf {A} ^{\text{T}}\mathbf {M} \mathbf {A} \right|}{\left|\mathbf {A} ^{\text{T}}\mathbf {N} \mathbf {A} \right|}},$

где $A=[\mathbf {\alpha } _{1},\ldots ,\mathbf {\alpha } _{c-1}]$ и

${\begin{aligned}M&=\sum _{j=1}^{c}l_{j}(\mathbf {M} _{j}-\mathbf {M} _{*})(\mathbf {M} _{j}-\mathbf {M} _{*})^{\text{T}}\\N&=\sum _{j=1}^{c}\mathbf {K} _{j}(\mathbf {I} -\mathbf {1} _{l_{j}})\mathbf {K} _{j}^{\text{T}}.\end{aligned}}$

The $\mathbf {M} _{i}$ определяются, как в предыдущем разделе, и $\mathbf {M} _{*}$ определяется как

$(\mathbf {M} _{*})_{j}={\frac {1}{l}}\sum _{k=1}^{l}k(\mathbf {x} _{j},\mathbf {x} _{k}).$

$\mathbf {A} ^{*}$ затем можно вычислить, найдя $(c-1)$ ведущие собственные векторы $\mathbf {N} ^{-1}\mathbf {M}$. Кроме того, проекция нового входа, $\mathbf {x} _{t}$, определяется

$\mathbf {y} (\mathbf {x} _{t})=\left(\mathbf {A} ^{*}\right)^{\text{T}}\mathbf {K} _{t},$

где $i^{th}$ компонент $\mathbf {K} _{t}$ дается $k(\mathbf {x} _{i},\mathbf {x} _{t})$.

Классификация с использованием KFD

Как в двухклассовом, так и в многоклассовом KFD метка класса нового входа может быть назначена как

$f(\mathbf {x} )=arg\min _{j}D(\mathbf {y} (\mathbf {x} ),{\bar {\mathbf {y} }}_{j}),$

где ${\bar {\mathbf {y} }}_{j}$ это прогнозируемое среднее значение для класса $j$ и $D(\cdot ,\cdot )$ является функцией расстояния.

Приложения

Дискриминантный анализ ядра использовался во многих приложениях. К ним относятся:

• Распознавание лиц и обнаружение
• Распознавание рукописных цифр
• Распознавание отпечатков пальцев
• Классификация злокачественных и доброкачественных кластерных микрокальцинатов
• Классификация семян
• Поиск бозона Хиггса в ЦЕРНе

См. также

• Факторный анализ
• Анализ главных компонентов ядра
• Трюк с ядром
• Линейный дискриминантный анализ

Внешние ссылки

• Дискриминантный анализ ядра на C# — код C# для выполнения KFD.
• Matlab Toolbox для уменьшения размерности — включает метод выполнения KFD.
• Распознавание рукописного текста с использованием дискриминантного анализа ядра — код C#, демонстрирующий распознавание рукописных цифр с использованием KFD.