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

В статистике , ядро Фишер дискриминантный анализ (УПКИ) , ^[1] , также известный как обобщенный дискриминантный анализ ^[2] и ядро дискриминантного анализа , ^[3] является kernelized вариантом линейного дискриминантного анализа (LDA). Он назван в честь Рональда Фишера . Используя трюк с ядром , LDA неявно выполняется в новом пространстве функций, что позволяет изучать нелинейные отображения.

Линейный дискриминантный анализ [ править ]

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

при условии

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

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

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

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

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

Уловка ядра с LDA [ править ]

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

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

куда

${\displaystyle {\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}}}$

и

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

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

LDA можно переформулировать в терминах скалярных произведений, сначала отметив, что это будет расширение формы ^[5]${\displaystyle \mathbf {w} }$

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

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

${\displaystyle \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},}$

куда

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

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

${\displaystyle \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}}.}$

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

${\displaystyle \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}},}$

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

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

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

Мультиклассовый KFD [ править ]

Распространение на случаи, когда существует более двух классов, относительно просто. ^{[2] [6] [7]} Позвольте быть количество классов. Затем мультиклассовый KFD включает в себя проектирование данных в -мерное пространство с использованием дискриминантных функций.${\displaystyle c}$${\displaystyle (c-1)}$${\displaystyle (c-1)}$

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

Это можно записать в матричных обозначениях

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

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

${\displaystyle \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}},}$

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

${\displaystyle \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}},}$

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

${\displaystyle 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 становится ^[7]

${\displaystyle \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|}},}$

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

${\displaystyle {\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}}}$

Они определены как в предыдущем разделе и определены как ${\displaystyle \mathbf {M} _{i}}$${\displaystyle \mathbf {M} _{*}}$

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

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

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

где составляющая дается выражением .${\displaystyle i^{th}}$${\displaystyle \mathbf {K} _{t}}$${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{t})}$

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

Как в двухклассовом, так и в многоклассовом KFD, метка класса нового входа может быть присвоена как ^[7]

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

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

Приложения [ править ]

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

• Распознавание лиц ^{[3] [8] [9]} и обнаружение ^{[10] [11]}
• Распознавание рукописных цифр ^{[1] [12]}
• Распознавание отпечатков пальцев ^[13]
• Классификация злокачественных и доброкачественных кластерных микрокальцификатов ^[14]
• Классификация семян ^[2]
• Поиски бозона Хиггса в ЦЕРНе ^[15]

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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