Machine Learning 13: Μέθοδος Newton για Μη Γραμμικά Προβλήματα

Στα προβλήματα μη γραμμικής βελτιστοποίησης και εκτίμησης παραμέτρων, η μέθοδος Newton (Newton-Raphson) είναι μια ισχυρή αριθμητική τεχνική που χρησιμοποιείται για την εύρεση ριζών ή ακραίων σημείων συναρτήσεων.

1. Θεωρία της Μεθόδου Newton

Η βασική ιδέα της μεθόδου είναι να προσεγγίσουμε τη συνάρτηση f(x) με την εφαπτομένη της στο τρέχον σημείο x_n και να βρούμε το σημείο όπου η εφαπτομένη τέμνει τον άξονα x:

Επαναλαμβάνοντας αυτή τη διαδικασία, η μέθοδος συγκλίνει σε μια ρίζα της f(x).

1.1 Διαφορά με Gradient Descent

Το Gradient Descent χρησιμοποιείται συνήθως για την εύρεση του ελάχιστου μιας συνάρτησης κόστους L(x) ακολουθώντας την κατεύθυνση του αρνητικού gradient:

Όπου η είναι το learning rate. Η μέθοδος Newton προχωρά ένα βήμα πιο πέρα: χρησιμοποιεί και τη δεύτερη παράγωγο (Hessian) της συνάρτησης:

Αυτό σημαίνει ότι η Newton "προβλέπει" καλύτερα τη καμπυλότητα της συνάρτησης και όχι μόνο την κλίση.

1.2 Πλεονεκτήματα της Μεθόδου Newton

• Γρηγορότερη σύγκλιση
• Ακριβέστερες προβλέψεις
• Ιδανική για μικρά προβλήματα

Παράδειγμα: Μέθοδος Newton για f(x) = x³ - 2x - 5

Θέλουμε να βρούμε μια ρίζα της συνάρτησης:

Βήμα 1: Επιλογή Αρχικής Τιμής

Επιλέγουμε αρχική τιμή για x, π.χ.:

Η τιμή αυτή είναι κοντά στη ρίζα που ψάχνουμε.

Βήμα 2: Υπολογισμός της Παραγώγου

Η παράγωγος της f(x) είναι:

Στο x₀ έχουμε:

Βήμα 3: Υπολογισμός Νέας Τιμής x₁

Η μέθοδος Newton δίνει:

Υπολογίζουμε την τιμή της f στο x₀:

Άρα:

Βήμα 4: Γραφική Ερμηνεία

Η εφαπτομένη στο x₀ δίνεται από τον τύπο:

Στο γράφημα:

• Η κόκκινη κουκίδα είναι η αρχική τιμή x₀.
• Η πορτοκαλί διάστικτη γραμμή είναι η εφαπτομένη στο x₀.
• Η πράσινη κουκίδα είναι η νέα τιμή x₁ όπου η εφαπτομένη τέμνει τον άξονα x.

Μαθηματική Εξήγηση: Iteration 2 και 3

Συνέχεια από Iteration 1, όπου βρήκαμε:

Iteration 2

Υπολογίζουμε νέα τιμή με τον τύπο Newton:

Υπολογίζουμε f(x₁) και f'(x₁):

Άρα:

Iteration 3

Συνεχίζουμε με:

Υπολογισμοί:

Νέα τιμή:

Στο γράφημα:

• Η κόκκινη κουκίδα: προηγούμενη τιμή x₂
• Η πορτοκαλί διάστικτη γραμμή: εφαπτομένη στο x₂
• Η πράσινη κουκίδα: νέα τιμή x₃

Συμπέρασμα

Μετά από 3 iterations η μέθοδος Newton έχει συγκλίνει σε:

Υλοποίηση της Μεθόδου Newton σε Python

Παρακάτω υλοποιούμε τη μέθοδο Newton για τη συνάρτηση:

import numpy as np

def f(x):
    return x**3 - 2*x - 5

def fp(x):
    return 3*x**2 - 2

def newton_method(x0, tol=1e-6, max_iter=10):
    x = x0
    history = []

    for i in range(max_iter):
        fx = f(x)
        fpx = fp(x)

        x_new = x - fx / fpx

        history.append((i, x, fx, fpx, x_new))

        if abs(x_new - x) < tol:
            break

        x = x_new

    return history

results = newton_method(2)

for r in results:
    print(r)

1. Ορισμός Συνάρτησης και Παραγώγου

Ορίζουμε τη συνάρτηση f(x) και την παράγωγό της f'(x), που είναι απαραίτητη για τη μέθοδο Newton.

2. Υλοποίηση της Newton Method

Η συνάρτηση δέχεται:

• x₀: αρχική τιμή
• tol: ανοχή (πότε σταματάμε)
• max_iter: μέγιστος αριθμός επαναλήψεων

3. Επανάληψη (Core του Αλγορίθμου)

Σε κάθε iteration:

• Υπολογίζουμε την τιμή της συνάρτησης f(x)
• Υπολογίζουμε την παράγωγο f'(x)
• Εφαρμόζουμε τον τύπο Newton:

4. Κριτήριο Σύγκλισης

Αν η διαφορά μεταξύ δύο διαδοχικών τιμών είναι πολύ μικρή, τότε θεωρούμε ότι έχουμε συγκλίνει στη ρίζα.

5. Αποθήκευση Ιστορικού

Αποθηκεύουμε κάθε iteration για να μπορούμε να δούμε πώς εξελίσσεται η λύση.

Αποτελέσματα

Κάθε γραμμή του πίνακα αντιστοιχεί σε ένα iteration της μεθόδου Newton.

Εξήγηση Στηλών

• Iteration: Ο αριθμός επανάληψης του αλγορίθμου.
• xₙ: Η τρέχουσα εκτίμηση της ρίζας.
• f(xₙ): Η τιμή της συνάρτησης στο xₙ. Όσο πλησιάζει το 0, τόσο είμαστε κοντά στη ρίζα.
• f'(xₙ): Η παράγωγος στο xₙ, δηλαδή η κλίση της εφαπτομένης.
• xₙ₊₁: Η νέα εκτίμηση που προκύπτει από τη μέθοδο Newton.

Βιβλιογραφία

Stanford Online. Stanford CS229: Machine Learning - Locally Weighted & Logistic Regression | Lecture 3 (Autumn 2018) [Video]. YouTube. https://youtu.be/het9HFqo1TQ?list=PLoROMvodv4rMiGQp3WXShtMGgzqpfVfbU