Für die meisten Probleme gibt es mehrere Lösungswege. Willst du zum Beispiel von einer Seite des Raums zur anderen, kannst du entweder außen herumgehen – oder direkt abkürzen.
Genau das verdeutlicht die Normalengleichung: Sie ist ein alternativer Lösungsweg. Welches Problem damit gelöst wird? Darauf kommen wir gleich. Wichtig ist zunächst: Unter bestimmten Bedingungen ist sie ein effizienter Ansatz, der dir bei der Umsetzung der linearen Regression viel Zeit spart.
Steigen wir ein…
Was ist die Normalengleichung?
Die Normalengleichung ist eine geschlossene Lösung, mit der die Werte von θ gefunden werden, die die Kostenfunktion bei der gewöhnlichen kleinsten Quadrate-Regression (Ordinary Least Squares) minimieren. Anders formuliert: ein analytischer Ansatz, um die Koeffizienten zu bestimmen, die die Loss-Funktion minimieren. Beides trifft zu – aber was bedeutet das konkret?
Die lineare Regression macht eine Vorhersage, y_hat, indem sie die gewichtete Summe der Eingabefeatures plus einen Bias-Term berechnet. Mathematisch lässt sich das so darstellen:
Dabei steht θ für die Parameter, und n ist die Anzahl der Features.
Im Kern wird oben das Skalarprodukt von θ und x gebildet und aufsummiert. Kürzer geht das in vektorisierter Form:
h(θ) ist die Hypothesenfunktion.
Mit dieser angenäherten Zielfunktion kann unser Modell Vorhersagen treffen. Um zu prüfen, wie gut das Modell gelernt hat, messen wir seine Leistung auf den Trainingsdaten – dafür berechnen wir eine Loss-Funktion. Ziel des Trainings ist, die Werte von θ zu finden, die diese Loss-Funktion minimieren.
So lässt sich die Loss-Funktion mathematisch darstellen:
In dieser Gleichung ist θ ein (n + 1)-dimensionaler Vektor, und unsere Loss-Funktion hängt vom Vektorwert ab. Entsprechend muss die partielle Ableitung der Kostenfunktion J nacheinander nach jedem Parameter θ_j gebildet werden. Alle müssen Null ergeben. Löst man so für alle Werte von θ von θ_0 bis θ_n, erhält man die Parameter, die die Loss-Funktion minimieren.
Die vollständige Herleitung von θ_0 bis θ_n ist allerdings sehr aufwendig. Es geht zum Glück schneller.
Hier ist die Formel der Normalengleichung:
Wobei gilt:
θ → Die Parameter, die die Loss-Funktion minimieren X → Die Eingabefeature-Werte je Instanz y → Der Vektor der Zielwerte je Instanz
Normalengleichung vs. Gradient Descent
Beide Verfahren suchen die Parameter θ, die die Loss-Funktion minimieren, unterscheiden sich aber deutlich im Vorgehen.
Da wir die Normalengleichung bereits erklärt haben, fassen wir Gradient Descent kurz zusammen und stellen dann die Unterschiede heraus.
Gradient Descent
Gradient Descent ist eines der meistgenutzten Verfahren im Machine Learning. Es findet die Parameter θ iterativ, um die Loss-Funktion zu minimieren.
Der Ablauf: Zuerst wird die Modellleistung bewertet. Dann berechnen wir die partielle Ableitung der Loss-Funktion, die die Steigung am aktuellen Punkt angibt. Anschließend gehen wir proportional zum negativen Gradienten Schritt für Schritt in Richtung Minimum, indem wir die aktuellen Parameter aktualisieren – siehe Formel unten.
Dieser Prozess wird wiederholt, bis wir am Minimum der Loss-Funktion konvergieren.
Worin unterscheiden sie sich?
Der offensichtlichste Unterschied: Die Normalengleichung ist analytisch. Gradient Descent ist iterativ, die Parameter nähern sich also schrittweise dem Optimum. Ein weiterer Punkt: Bei Gradient Descent musst du eine Lernrate festlegen, die die Schrittgröße zum Minimum steuert. Bei der Normalengleichung entfällt das, da keine iterativen Schritte nötig sind – die Lösung kommt direkt.
Außerdem ist beim Ansatz mit der Normalengleichung kein Feature-Scaling erforderlich. Feature-Scaling verwenden wir typischerweise, um ähnliche Wertebereiche sicherzustellen, weil Gradient Descent empfindlich auf unterschiedliche Skalen reagiert. Ohne Normalisierung können bei Gradient Descent Verzerrungen in den Konturlinien der Loss-Funktion entstehen – die Normalengleichung hat dieses Problem nicht.
Wann solltest du die Normalengleichung verwenden?
Am einfachsten entscheidest du über den Einsatz, wenn du die Nachteile kennst.
Die Berechnung der Normalengleichung wird schwierig, wenn die Zahl der Features groß ist. Grund: Um θ zu bestimmen, muss (X’ X)^-1 berechnet werden. X’ X ist eine n x n-Matrix, und bei den meisten Implementierungen wächst der Aufwand für das Invertieren ungefähr mit der dritten Potenz der Matrixdimension. Die Inversion hat also eine Laufzeitkomplexität von O(n^3) und macht die Normalengleichung für sehr große n extrem langsam – mehr zu Laufzeitkomplexität.
Deshalb ist Gradient Descent bei vielen Features oft die bessere Wahl. Andrew Ng, ein führender Experte für Machine Learning und KI, empfiehlt, ab mehr als 10.000 Features über Gradient Descent nachzudenken. Bei 10.000 oder weniger Features bist du mit einem analytischen Ansatz wie der Normalengleichung oft gut bedient, weil keine Lernrate gewählt werden muss – ein Hyperparameter weniger. Allerdings nutzen Sprachen wie R oder Python in der Praxis häufig die QR-Zerlegung, um die Koeffizienten der OLS-Regression zu bestimmen – sie ist numerisch stabiler und effizienter als die Normalengleichung.
Die Normalengleichung in Python – von Grund auf
Erzeugen wir zunächst ein Regressionsproblem, um die Gleichung zu testen:
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_regression
# Generate a regression problem
X, y = make_regression(
n_samples=100,
n_features=2,
n_informative=2,
noise = 10,
random_state=25
)
# Visualize feature at index 1 vs target
plt.subplots(figsize=(8, 5))
plt.scatter(X[:, 1], y, marker='o')
plt.xlabel("Feature at Index 1")
plt.ylabel("Target")
plt.show()
Jetzt implementieren wir die Normalengleichung:
# adds x0 = 1 to each instance
X_b = np.concatenate([np.ones((len(X), 1)), X], axis=1)
# calculate normal equation
theta_best = np.linalg.inv(X_b.T.dot(X_b)).dot(X_b.T).dot(y)
# best values for theta
intercept, *coef = theta_best
print(f"Intercept: {intercept}\n\
Coefficients: {coef}")
Intercept: 0.35921242677977794
Coefficients: [6.129199175400593, 96.44309685893134]
Testen wir das Modell mit einer Vorhersage:
# making a new sample
new_sample = np.array([[-2, 0.25]])
# adding a bias term to the instance
new_sample_b = np.concatenate([np.ones((len(new_sample), 1)), new_sample], axis=1)
# predicting the value of our new sample
new_sample_pred = new_sample_b.dot(theta_best)
print(f"Prediction: {new_sample_pred}")
Prediction: [12.21158829]
Wenn du ML-Algorithmen von Grund auf implementierst, ist eine Validierung hilfreich. Scikit-learn ist eine der beliebtesten ML-Bibliotheken in Python. Sie bietet viele Implementierungen, darunter lineare Regression, mit der wir unsere Normalengleichung validieren.
from sklearn.linear_model import LinearRegression
lr = LinearRegression()
lr.fit(X, y)
print(f"Intercept: {lr.intercept_}\n\
Coefficients: {lr.coef_}")
print(f"Prediction: {lr.predict(new_sample)}")
Intercept: 0.3592124267797807
Coefficients: [ 6.12919918 96.44309686]
Prediction: [12.21158829]
Die Lösungen stimmen näherungsweise überein – unsere Implementierung ist damit bestätigt.