La descente de gradient est-elle possible pour les SVM noyés (si oui, pourquoi les gens utilisent-ils la programmation quadratique)?

Pourquoi les gens utilisent-ils des techniques de programmation quadratique (comme SMO) lorsqu'ils traitent avec des SVM noyés? Quel est le problème avec Gradient Descent? Est-il impossible de l'utiliser avec des noyaux ou est-ce simplement trop lent (et pourquoi?).

Voici un peu plus de contexte: en essayant de mieux comprendre les SVM, j'ai utilisé Gradient Descent pour former un classificateur SVM linéaire en utilisant la fonction de coût suivante:

$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \mathbf{x}^{(i)} + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$

J'utilise les notations suivantes:

• $\mathbf{w}$ est le poids caractéristique du modèle et$b$ est son paramètre de biais.
• $\mathbf{x}^{(i)}$ est levecteur d' entités de la$i^\text{th}$ formation.
• $y^{(i)}$ est la classe cible (-1 ou 1) pour la$i^\text{th}$ instance.
• $m$ est le nombre d'instances de formation.
• $C$ est l'hyperparamètre de régularisation.

J'ai dérivé un vecteur (sub) gradient (en ce qui concerne $\mathbf{w}$ et $b$ ) de cette équation, et Gradient Descent a très bien fonctionné.

J'aimerais maintenant aborder des problèmes non linéaires. Puis-je simplement remplacer tous les produits scalaires par K ( u , $\mathbf{u}^t \cdot \mathbf{v}$ dans la fonction de coût, où K est la fonction du noyau (par exemple le RBF gaussien, K ( u , v ) = e - γ ‖ u - v ‖ 2 ), puis utilisez le calcul pour dériver un vecteur de (sous-) gradient et continuer avec Gradient Descent?$K(\mathbf{u}, \mathbf{v})$$K$$K(\mathbf{u}, \mathbf{v}) = e^{-\gamma \|\mathbf{u} - \mathbf{v}\|^2}$

Si c'est trop lent, pourquoi? La fonction de coût n'est-elle pas convexe? Ou est-ce parce que le gradient change trop vite (ce n'est pas Lipschitz continu) donc l'algorithme continue de sauter à travers les vallées pendant la descente, donc il converge très lentement? Mais même alors, comment peut-elle être pire que la complexité temporelle de la programmation quadratique, qui est ? S'il s'agit de minima locaux, le GD stochastique avec recuit simulé ne peut-il pas les surmonter? $O({n_\text{samples}}^2 \times n_\text{features})$

Fixons telle sorte que w t ϕ ( x ) = u t ⋅ K et w t w = u t K u , avec K = ϕ ( x ) t ϕ ( x ) , où ϕ ( x ) est un mappage de la matrice d'entrée d'origine, $\mathbf w = \phi(\mathbf x)\cdot \mathbf u$$\mathbf w^t \phi(\mathbf x)=\mathbf u^t \cdot \mathbf K$$\mathbf w^t\mathbf w = \mathbf u^t\mathbf K\mathbf u$$\mathbf K = \phi(\mathbf x)^t\phi(\mathbf x)$$\phi(x)$$\mathbf x$. Cela permet de résoudre le SVM à travers la formulation primale. En utilisant votre notation pour la perte:

est unematrice m × m , et u est unematrice m × 1 . Ni l'un ni l'autre n'est infini.$\mathbf{K}$$m \times m$$\mathbf{u}$$m \times 1$

En effet, le dual est généralement plus rapide à résoudre, mais le primal a aussi ses avantages, tels que les solutions approximatives (qui ne sont pas garanties dans la formulation dual).

Maintenant, pourquoi le double est-il tellement plus important n'est pas évident du tout: [1]

Les raisons historiques pour lesquelles la plupart des recherches de la dernière décennie ont porté sur la double optimisation ne sont pas claires . Nous pensons que c'est parce que les SVM ont été introduits pour la première fois dans leur formulation à marge dure [Boser et al., 1992], pour lesquels une double optimisation (en raison des contraintes) semble plus naturelle. En général, cependant, les SVM à marge souple devraient être préférés, même si les données de formation sont séparables: la frontière de décision est plus robuste car plus de points de formation sont pris en compte [Chapelle et al., 2000]

Chapelle (2007) soutient que la complexité temporelle de l'optimisation primaire et double est , le pire étant O ( n 3 ) , mais ils ont analysé les pertes quadratiques et approximatives des charnières, donc pas une bonne perte de charnière, car il n'est pas différenciable d'être utilisé avec la méthode de Newton.$\mathcal{O}\left(nn_{sv} + n_{sv}^3\right)$$\mathcal{O}\left(n^3\right)$

_{[1] Chapelle, O. (2007). Formation d'une machine à vecteurs de support dans le primal. Calcul neuronal, 19 (5), 1155-1178.}

Si nous appliquons une transformation à tous les vecteurs de poids d'entrée ( x ( i ) ), nous obtenons la fonction de coût suivante:$\phi$$\mathbf{x}^{(i)}$

$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$

$\phi(\mathbf{u})^t \cdot \phi(\mathbf{v})$$K(\mathbf{u}, \mathbf{v})$$\mathbf{w}$ n'est pas transformé, l'astuce du noyau ne peut pas être appliquée à la fonction de coût ci-dessus .

La fonction de coût ci-dessus correspond à la forme primitive de l'objectif SVM:

$\underset{\mathbf{w}, b, \mathbf{\zeta}}\min{C \sum\limits_{i=1}^m{\zeta^{(i)}} + \dfrac{1}{2}\mathbf{w}^t \cdot \mathbf{w}}$

subject to $y^{(i)}(\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b) \ge 1 - \zeta^{(i)})$ and $\zeta^{(i)} \ge 0$ for $i=1, \cdots, m$

The dual form is:

$\underset{\mathbf{\alpha}}\min{\dfrac{1}{2}\mathbf{\alpha}^t \cdot \mathbf{Q} \cdot \mathbf{\alpha} - \mathbf{1}^t \cdot \mathbf{\alpha}}$

subject to $\mathbf{y}^t \cdot \mathbf{\alpha} = 0$ and $0 \le \alpha_i \le C$ for $i = 1, 2, \cdots, m$

where $\mathbf{1}$ is a vector full of 1s and $\mathbf{Q}$ is an $m \times m$ matrix with elements $Q_{ij} = y^{(i)} y^{(j)} \phi(\mathbf{x}^{(i)})^t \cdot \phi(\mathbf{x}^{(j)})$.

Now we can use the kernel trick by computing $Q_{ij}$ like so:

$Q_{ij} = y^{(i)} y^{(j)} K(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})$

So the kernel trick can only be used on the dual form of the SVM problem (plus some other algorithms such as logistic regression).

Now you can use off-the-shelf Quadratic Programming libraries to solve this problem, or use Lagrangian multipliers to get an unconstrained function (the dual cost function), then search for a minimum using Gradient Descent or any other optimization technique. One of the most efficient approach seems to be the SMO algorithm implemented by the libsvm library (for kernelized SVM).

I might be wrong, but I don't see how we can replace the dot products with kernels without turning it into the dual problem.

The kernels map the input implicitly to some feature space where $x$ becomes $\phi(x)$, the loss function then becomes
$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$
If Gaussian kernel is applied, $\phi(\mathbf{x}^{(i)})$ will have ifinite dimensions, so will $\mathbf{w}$.

It seems difficult to optimize a vector of infinite dimensions using gradient descent directly.

Update
Firebug's answer gives a way of replacing the dot products with kernels in the primal formulation.