Почему эффективны случайные функции Fou rier? - DataScientist
8 голосов
/ 13 декабря

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

$$ f(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{n=1}^{N} \alpha_n k(\mathbf{x}, \mathbf{x}_n) \tag{1} $$

Позвольте $\mathbf{x} \in \mathbb{R}^D$ и пусть $K < D$. Рахими и Рехт предлагают карту $\mathbf{z}: \mathbb{R}^D \mapsto \mathbb{R}^K$ такую, что

\begin{align} \mathbf{w}_j &\sim \mathcal{N}(\mathbf{0}, \mathbf{I}) \\ \hat{k}(\mathbf{x}, \mathbf{y}) &= \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \mathbf{z}(\mathbf{y}; \mathbf{w}_j). \end{align}

Cool so fa r. Вот что я не понимаю. Затем Рахими заявляет здесь , что если мы включим $\hat{k}$ в уравнение $1$, мы получим приближение:

$$ \hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{j=1}^J \beta_j \mathbf{z}(\mathbf{x}; \mathbf{w}_j). $$

Вопрос: I не понимаю, как мы можем устранить сумму r $N$. Я бы ожидал:

$$ \hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{n=1}^{N} \alpha_n \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \mathbf{z}(\mathbf{x}_n; \mathbf{w}_j). $$

Я мог бы изменить суммы, но Я до сих пор не понимаю, как мы можем устранить сумму r $N$,

$$ \hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \underbrace{\sum_{n=1}^{N} \alpha_n \mathbf{z}(\mathbf{x}_n; \mathbf{w}_j)}_{\beta_j??}. $$

Чего мне не хватает?

1 Ответ

3 голосов
/ 17 декабря

Так что этот вид выглядит как случай злоупотребления нотацией для меня.

Краткий обзор двойного состава SVM и трюка ядра

Стандарт r, базовые c ванильные машины vecto r, мы имеем дело только с двоичной классификацией. Как обычно, ou r двух меток классов будет кодироваться набором $\mathcal{Y} = \{+1, -1\}$. Я также буду использовать обозначение $[m] = \{1, 2, \dots, m\}$. Набор обучающих данных Ou r представляет собой выборку размером $m$ в форме $S = \{(\mathbf{x}_{i}, y_{i}) \ |\ i \in [m], \ \mathbf{x}_{i} \in \mathbb{R}^{D},\ y_{i} \in \mathcal{Y} \} $.

Afte r, переформулирующую задачу в двойственной форме Лагранжа, обеспечивающую выполнение условий KKT и упрощающую с помощью некоторой алгебры Задача оптимизации может быть записана в краткой форме: $$\max_{\alpha} \sum_{i = 1}^{m}\alpha_{i} - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_{i}\alpha_{j}y_{i}y_{j}(\mathbf{x}_{i}\cdot\mathbf{x}_{j}) \tag{1}\\ \text{subject to}:\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\ \alpha_{i} \geq 0\ \ \forall i\in [m]\\ \sum_{i=1}^{m}\alpha_{i}y_{i}=0$$

Опорные векторы - это точки выборки $\mathbf{x}_{i}\in\mathbb{R}^{D}$, где $\alpha_{i} \neq 0$. Все остальные r точки, не входящие в маргинальные гиперплоскости, имеют $\alpha_{i} = 0$.

Трюк с ядром происходит от замены стандартного евклидова inne r произведения в целевой функции $(1)$ на inne r произведение в проекционном пространстве, представляемом функцией ядра: $$k(\mathbf{x}, \mathbf{y}) = \phi(\mathbf{x}) \cdot \phi(\mathbf{y})\\ \text{where}\ \ \phi(\mathbf{x}) \in \mathbb{R}^{D_{1}}$$ Это обобщение позволяет нам иметь дело с нелинейно разделимыми ситуациями, поскольку, если мы возьмем $D_{1} > D$, мы можем найти строку r separato r в этом более высоком r - размерное $D_{1}$ пространство, соответствующее нелинейному r separato r в ou r оригинальное $D$ ⁠-мерное пространство.

исправление нотационного злоупотребления

Давайте рассмотрим эти внутренние r продукты немного ближе. Евклидово произведение inne r - это семейство r sum: $$\mathbf{x}_{i}\cdot\mathbf{x}_{j} = \sum_{t=1}^{D}x_{i,t}x_{j,t} $$

Итак, мы видим, что целевая функция $(1)$ действительно имеет эту сумму $D$ term, вложенную в двойную сумму. Если я напишу $\phi(\mathbf{x}) = \large{(} \normalsize{\phi_{1}(\mathbf{x}), \phi_{2}(\mathbf{x}), \dots, \phi_{D_{1}}(\mathbf{x})} \large{)} $, то ядро ​​inne r -продукта будет выглядеть так: $$\phi(\mathbf{x}_{i})\cdot\phi(\mathbf{x}_{j}) = \sum_{t=1}^{D_{1}}\phi_{t}(\mathbf{x}_{i})\phi_{t}(\mathbf{x}_{j}) \tag{2} $$

Так что из $(2)$ нам напоминают, что проецирование в это более высокое r -мерное пространство означает, что в продукте inne r больше терминов. «Хитрость» в хитрости ядра заключается в том, что правильно выбранные проекции $\phi$ и пробелы $\mathbb{R}^{D_{1}}$ позволяют нам обойти этот более интенсивный в вычислительном отношении продукт inne r, поскольку мы можем просто использовать функцию ядра $k$ в точках оригинала пробел $\mathbb{R}^{D}$ (пример fo r, если ядро ​​удовлетворяет условию Merce r).

Хорошо, все до этого момента в основном рассматривало стандартный материал. Что метод случайных особенностей Рахими делает вместо того, чтобы использовать ядро, которое эквивалентно проецированию в более высокое r $D_{1}$ ⁠-мерное пространство, мы проецируем в низкое r $K$ -мерное пространство, используя фиксированные функции проецирования $\mathbf{z}$ с случайные веса $\mathbf{w}_{j}$. Таким образом, чем r, чем одиночная проекция $\phi(\mathbf{x})$ fo r каждая точка $\mathbf{x}$, мы вместо этого имеем случайную коллекцию $\mathbf{z}(\mathbf{x}, \mathbf{w_{j}})$ fo r $j \in [J]$. С точки зрения обозначения компонентов, Earl ier у нас было: $$\phi(\mathbf{x}) = \large{(}\normalsize \phi_{1}(\mathbf{x}), \dots, \phi_{D_{1}}(\mathbf{x} ) \large{)} \tag{3}, $$

, тогда как теперь у нас есть: $$ \mathbf{z}(\mathbf{x}, \mathbf{w}_{1}) = \large{(}\normalsize z_{1}(\mathbf{x}, \mathbf{w}_{1}), \dots, z_{K}(\mathbf{x}, \mathbf{w}_{1})\large{)} \\ \vdots \tag{4}\\ \mathbf{z}(\mathbf{x}, \mathbf{w}_{J}) = \large{(}\normalsize z_{1}(\mathbf{x}, \mathbf{w}_{J}), \dots, z_{K}(\mathbf{x}, \mathbf{w}_{J})\large{)}$$

Как они упоминаются в одной из трех статей Рахими помещает в эту трилогию, я забыл, какие компоненты проекционных функций $(4)$ теперь можно рассматривать как $J$ -мерное векто r, оцениваемое вместо scalar, оцениваемое в $(3)$. Итак, теперь вы заменяете r $D_{1}$ -мерную проекцию $J$ отдельными $K$ -мерными проекциями и заменяете вас r $D_{1}$ членскую сумму $JK$ членской суммой в каждой inne r product.

Итак, теперь вы r inne r product на самом деле представляете собой двойную сумму, ove r и $J$ компоненты каждой проекции и $K$ размеры пространства : $$ \hat{k}(\mathbf{x}, \mathbf{y}) = \sum_{t=1}^{K} \sum_{j=1}^{J} \beta_{j}z_{t}(\mathbf{x})z_{t}(\mathbf{y}) \tag{5} $$

Сравните это с единственной суммой, представляющей эквивалент ядра inne r product в $(2)$.

Надеемся, что отслеживание каждого индекса отдельно прояснило для вас r. Поскольку r почему это 'эффективно', поскольку $K$ -мерная проекция является более низкой r -мерной, это меньше вычислительных затрат, чем вычисление типичной более высокой r $D_{1}$ размерной проекции. Кроме того, поскольку вы случайным образом генерируете $J$ этих проекций, предполагая, что r случайное генерирование является вычислительно дешевым, вы довольно легко получаете эффективный ансамбль векторов поддержки.

...