Co je cílem optimalizačního problému SVM a jak je matematicky formulován?

/ / Vyšlo v Umělá inteligence, Strojové učení EITC/AI/MLP s Pythonem, Podpora vektor stroj, Podpora optimalizace vektorových strojů, Přehled vyšetření

Cílem problému optimalizace Support Vector Machine (SVM) je najít nadrovinu, která nejlépe rozděluje sadu datových bodů do odlišných tříd. Tohoto oddělení je dosaženo maximalizací okraje, definovaného jako vzdálenost mezi nadrovinou a nejbližšími datovými body z každé třídy, známé jako podpůrné vektory. Algoritmus SVM si klade za cíl vytvořit model, který dokáže dobře zobecnit na neviditelná data tím, že se zaměří na tyto kritické body.

Matematicky lze problém optimalizace SVM formulovat v kontextu problému binární klasifikace, kde je cílem rozdělit datové body do dvou tříd, obvykle označených jako +1 a -1. Datové body jsou reprezentovány jako vektory v n-rozměrném prostoru prvků. Označme trénovací datovou sadu jako \{(\mathbf{x}_i, y_i)\}_{i=1}^m, Kde \mathbf{x}_i \in \mathbb{R}^n představuje příznakový vektor i-tého datového bodu a y_i \in \{-1, +1\} představuje odpovídající označení třídy.

Problém lineární optimalizace SVM lze formulovat následovně:

1. Primární složení:

Cílem je najít nadrovinu definovanou váhovým vektorem \mathbf{w} \in \mathbb{R}^n a zaujatý termín b \in \mathbb{R} což maximalizuje rezervu při správné klasifikaci trénovacích dat. Nadrovinu lze znázornit rovnicí \mathbf{w} \cdot \mathbf{x} + b = 0.

Optimalizační problém lze vyjádřit takto:

    \[ \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \]

s výhradou omezení:

    \[ y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 \quad \forall i = 1, \ldots, m \]

Zde, \|\mathbf{w}\|^2 je kvadratická norma vektoru hmotnosti, kterou se snažíme minimalizovat, abychom maximalizovali rozpětí. Omezení zajišťují, že každý datový bod je správně klasifikován a leží na správné straně okraje.

2. Duální složení:

Prvotní problém lze převést do jeho duální podoby pomocí Lagrangeových multiplikátorů. Duální formulace je v praxi často preferována, protože umožňuje použití funkcí jádra ke zpracování nelineárních rozhodovacích hranic.

Problém duální optimalizace je formulován takto:

    \[ \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) \]

s výhradou omezení:

    \[ 0 \leq \alpha_i \leq C \quad \forall i = 1, \ldots, m \]

    \[ \sum_{i=1}^m \alpha_i y_i = 0 \]

Zde, \alpha_i jsou Lagrangeovy multiplikátory a C je regularizační parametr, který řídí kompromis mezi maximalizací marže a minimalizací chyby klasifikace. Funkce jádra K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i \cdot \mathbf{x}_j umožňuje algoritmu pracovat ve vysokorozměrném prostoru prvků bez explicitního výpočtu souřadnic dat v tomto prostoru.

3. Nelineární SVM:

Ke zpracování nelineárních separací se používá jádrový trik. Myšlenkou je mapování původního prostoru rysů do vícerozměrného prostoru pomocí nelineární mapovací funkce \phi(\mathbf{x}). Funkce jádra K(\mathbf{x}_i, \mathbf{x}_j) představuje vnitřní produkt v tomto vyšší dimenzionálním prostoru, tzn. K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j).

Mezi běžně používané funkce jádra patří:

- Lineární jádro: K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i \cdot \mathbf{x}_j
- Polynomiální jádro: K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j + 1)^d, Kde d je stupeň polynomu.
- Jádro funkce radiální báze (RBF): K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2), Kde \ gama je parametr, který definuje šířku Gaussovy funkce.
- Sigmoidní jádro: K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\kappa (\mathbf{x}_i \cdot \mathbf{x}_j) + \theta), Kde \kappa si \ theta jsou parametry sigmoidní funkce.

Problém duální optimalizace pro nelineární SVM zůstává stejný jako v lineárním případě, ale s funkcí jádra K(\mathbf{x}_i, \mathbf{x}_j) výměna vnitřního produktu \mathbf{x}_i \cdot \mathbf{x}_j.

4. Měkká marže SVM:

Ve scénářích reálného světa nemusí být data dokonale oddělitelná. Pro řešení takových případů je zaveden koncept měkkého rozpětí. SVM s měkkým okrajem umožňuje určitou chybnou klasifikaci zavedením proměnných nevyužitých hodnot \xi_i \geq 0 pro každý datový bod.

Primární optimalizační problém pro SVM s měkkým okrajem je formulován jako:

    \[ \min_{\mathbf{w}, b, \xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^m \xi_i \]

s výhradou omezení:

    \[ y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i \quad \forall i = 1, \ldots, m \]

    \[ \xi_i \geq 0 \quad \forall i = 1, \ldots, m \]

Tady termín C \sum_{i=1}^m \xi_i penalizuje nesprávně klasifikované body a C je regularizační parametr, který řídí kompromis mezi maximalizací marže a minimalizací chyby klasifikace.

Duální formulace pro SVM s měkkým rozpětím je podobná případu s pevným rozpětím, s omezeními na Lagrangeových multiplikátorech \alpha_i upraveno tak, aby zahrnovalo parametr regularizace C:

    \[ 0 \leq \alpha_i \leq C \quad \forall i = 1, \ldots, m \]

5. Příklad:

Zvažte jednoduchý příklad s dvourozměrnou datovou sadou sestávající ze dvou tříd. Datové body jsou:

Třída +1: (2, 3), (3, 3), (4, 4)
Třída -1: (1, 1), (2, 1), (3, 2)

Cílem je najít nadrovinu, která nejlépe odděluje tyto dvě třídy. Pro jednoduchost předpokládejme lineární SVM s pevným okrajem. Primární optimalizační problém lze formulovat takto:

    \[ \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \]

s výhradou omezení:

    \[ \mathbf{w} \cdot (2, 3) + b \geq 1 \]

    \[ \mathbf{w} \cdot (3, 3) + b \geq 1 \]

    \[ \mathbf{w} \cdot (4, 4) + b \geq 1 \]

    \[ \mathbf{w} \cdot (1, 1) + b \leq -1 \]

    \[ \mathbf{w} \cdot (2, 1) + b \leq -1 \]

    \[ \mathbf{w} \cdot (3, 2) + b \leq -1 \]

Řešením tohoto optimalizačního problému se získá vektor hmotnosti \mathbf{w} a zkreslení b které definují optimální nadrovinu. Podpěrné vektory, což jsou datové body nejblíže k nadrovině, určují okraj.

V praxi jsou SVM implementovány pomocí optimalizačních knihoven, které efektivně řeší duální formulaci. V Pythonu knihovna `scikit-learn` poskytuje implementaci SVM prostřednictvím třídy `SVC`, která dokáže pracovat s lineárními i nelineárními jádry.

Například pro trénování SVM s lineárním jádrem pomocí `scikit-learn` lze použít následující kód:

python
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score

# Load a sample dataset
iris = datasets.load_iris()
X = iris.data
y = iris.target

# Use only two classes for binary classification
X = X[y != 2]
y = y[y != 2]

# Split the dataset into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# Create an SVM classifier with a linear kernel
svm = SVC(kernel='linear', C=1.0)

# Train the SVM classifier
svm.fit(X_train, y_train)

# Make predictions on the test set
y_pred = svm.predict(X_test)

# Evaluate the accuracy of the classifier
accuracy = accuracy_score(y_test, y_pred)
print(f'Accuracy: {accuracy:.2f}')

V tomto příkladu je třída `SVC` použita k vytvoření klasifikátoru SVM s lineárním jádrem. Klasifikátor je natrénován na trénovací sadě a vyhodnocen na testovací sadě, přičemž přesnost předpovědí je vytištěna na konzole.

Problém optimalizace SVM je základním aspektem strojového učení a poskytuje robustní a všestrannou metodu pro klasifikační úlohy. Maximalizací marže se SVM zaměřují na dosažení dobrého výkonu zobecnění, což z nich činí cenný nástroj v různých aplikacích.

Další nedávné otázky a odpovědi týkající se Strojové učení EITC/AI/MLP s Pythonem:

Prohlédněte si další otázky a odpovědi v EITC/AI/MLP Machine Learning with Python

Další otázky a odpovědi:

V rubrice: , , , , ,