Programmazione Scientifica++: Lezione 12

Ereditarietà, polimorfismo e classi astratte

Cristiano De Michele

Una citazione da verificare

Knowledge is having the right answers. Intelligence is asking the right questions. Wisdom is knowing when to ask the right questions.

— Richard P. Feynman autore sconosciuto

Ho chiesto a un assistente di intelligenza artificiale se fosse davvero di Feynman.

  • Non compare in nessuno dei suoi libri, delle sue lezioni o delle interviste registrate.
  • La prima attribuzione trovata è del 2021, in un post di un account di ammiratori.
  • Prima la frase circolava senza autore, e più corta: «Knowledge is knowing the right answer. Intelligence is asking the right question.»

Lo strumento ha fatto la ricerca, ma la domanda l’ha posta chi lo usava: senza quella domanda, la frase sarebbe finita qui con il nome sbagliato.

Due citazioni con una fonte

The formulation of a problem is often more essential than its solution, which may be merely a matter of mathematical or experimental skill. To raise new questions, new possibilities, to regard old problems from a new angle requires creative imagination and marks real advances in science.

A. Einstein e L. Infeld, The Evolution of Physics (1938), p. 92.

But they are useless. They can only give you answers.

Pablo Picasso, a proposito dei calcolatori, in W. Fifield, «Pablo Picasso: A Composite Interview», The Paris Review 32 (1964), p. 62.

Oggi una parte crescente della skill di cui parlano Einstein e Infeld la svolgono gli strumenti: un assistente di intelligenza artificiale scrive codice in pochi secondi. Formulare il problema e verificare la risposta resta compito di chi li usa.

Una frase di Feynman con una fonte

What I cannot create, I do not understand.

Scritta sulla lavagna di Feynman al Caltech, com’era alla sua morte, nel febbraio 1988 (Caltech Archives).

  • Per verificare una risposta, data da una persona o da uno strumento, bisogna capire ciò di cui parla; e per capirlo bisogna saperlo costruire.
  • È il motivo per cui in questo corso il framework che riconosce le cifre di MNIST si scrive da zero, in C++, invece di usare una libreria già pronta.

Argomenti di oggi

  • L’ereditarietà: una classe derivata riceve attributi e metodi da una classe base; i membri protected
  • La classe std::vector: un array che gestisce da sé la sua memoria
  • Il polimorfismo: metodi virtual e override, un vettore di puntatori alla classe base
  • Il distruttore virtuale: oggetti creati con new e distrutti attraverso la classe base
  • Le classi astratte: i metodi virtuali puri, dichiarati senza corpo, che ogni classe derivata deve scrivere
  • Esercizi: le funzioni di loss; la discesa del gradiente per una funzione qualsiasi

Gli argomenti di oggi nel framework

  • Ereditarietà. Tutti i layer derivano dalla classe base Layer: DenseLayer attraverso ParametricLayer (i layer con pesi), SigmoidLayer attraverso ActivationLayer (le funzioni di attivazione).
  • Classe astratta. Layer dichiara forward, backward e get_type come metodi virtuali puri: un Layer generico non si può creare, e ogni layer concreto li deve scrivere, con override.
  • Polimorfismo. Sequential tiene i layer in un std::vector di puntatori alla classe base, e il suo forward chiama forward su ciascun layer: viene eseguito il metodo del layer vero, DenseLayer o SigmoidLayer.

Gli argomenti di oggi nel framework (segue)

  • Distruttore virtuale. Layer ha virtual ~Layer() = default;, perché i layer vengono distrutti attraverso il puntatore alla classe base. = default chiede al compilatore il distruttore che scriverebbe da solo.
  • Loss. Le funzioni di loss seguono lo stesso schema: la classe base Loss, con il metodo virtuale puro forward, e la classe derivata MSELoss.

La cartella della lezione

Oggi ogni esempio si scrive e si compila durante la lezione, in un progetto CMake come quello dei laboratori, ma in una cartella a parte.

CMakeLists.txt
cmake_minimum_required(VERSION 3.15)
project(Lezione12)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall")
# AddressSanitizer (Lezione 08)
add_compile_options(-fsanitize=address -g)
add_link_options(-fsanitize=address)
# qui una riga add_executable per esempio
  1. Create la cartella LEZIONE_12, fuori da basic_neural_plusplus, e apritela in VS Code.
  2. Createvi il file CMakeLists.txt qui a sinistra.
  3. Dalla cartella LEZIONE_12:
    cmake -B build.

L’AddressSanitizer mostra gli errori di memoria degli esperimenti di oggi sul distruttore virtuale.

Un eseguibile per esempio

Sopra ogni esempio c’è il nome del suo file. Quando lo incontrate, create il file, copiatevi il codice e aggiungete al CMakeLists.txt la sua riga:

add_executable(ereditarieta ereditarieta.cpp)
add_executable(vettore vettore.cpp)
add_executable(polimorfismo polimorfismo.cpp)
add_executable(layer_new layer_new.cpp)
add_executable(loss loss.cpp)                          # esercizio
add_executable(lampo lampo.cpp)                        # approfondimento
add_executable(discesa discesa.cpp Vettore2D.cpp)      # esercizio

Poi, dalla cartella LEZIONE_12, compilate ed eseguite solo quell’esempio:

cmake -B build && cmake --build build --target ereditarieta && ./build/ereditarieta

cmake -B build rilegge il CMakeLists.txt: senza, --target non trova un esempio appena aggiunto. Con --target si compila solo l’esempio indicato: un esercizio non ancora finito non blocca gli altri. I messaggi citati sono quelli di g++ su Linux; con clang (macOS) il testo cambia, il significato no.

Classi con una parte in comune

Una rete è una sequenza di layer di tipi diversi:

  • DenseLayer: moltiplica l’ingresso per la matrice dei pesi, \(z = W x + b\) (Laboratorio 05);
  • SigmoidLayer: applica a ogni componente la funzione di attivazione \(\sigma\).

I calcoli sono diversi, ma i due tipi hanno una parte in comune: entrambi hanno un nome che ne indica il tipo, come "DenseLayer", ricevono un ingresso e producono un’uscita con un metodo forward, e la rete deve chiamarli uno dopo l’altro.

Il C++ permette di scrivere la parte comune una volta sola, in una classe da cui le altre derivano: un errore nella parte comune si corregge in un solo punto.

L’ereditarietà

Una classe derivata riceve (eredita) gli attributi e i metodi di una classe base, e ne aggiunge di propri:

class DenseLayer : public Layer {
    // attributi e metodi in piu' rispetto a Layer
};
  • DenseLayer è la classe derivata, Layer la classe base.
  • public Layer: i membri pubblici di Layer restano pubblici anche in DenseLayer. Nel corso si usa sempre questa forma. Senza public, in una class la derivazione è private, come i membri (Lezione 06): un DenseLayer non si può più usare come Layer.

L’ereditarietà descrive la relazione “è un”: un DenseLayer è un Layer. Quando la relazione è “ha un”, si usa un attributo: una rete ha dei layer, come un oggetto può avere un altro oggetto come attributo (Lezione 07).

Una classe derivata

ereditarieta.cpp
#include <iostream>
#include <string>
class Layer {
protected:
1    std::string tipo_;
public:
    Layer(const std::string& tipo) : tipo_(tipo) {}
    void stampa_tipo() const { std::cout << "layer di tipo " << tipo_ << "\n"; }
};

class DenseLayer : public Layer {
private:
    int Nn_, Ni_;
public:
2    DenseLayer(int Nn, int Ni) : Layer("DenseLayer"), Nn_(Nn), Ni_(Ni) {}
    void stampa_dimensioni() const {
3        std::cout << tipo_ << ": " << Nn_ << " neuroni, " << Ni_ << " ingressi\n";
    }
};
1
protected: come private per il resto del programma, ma accessibile dai metodi delle classi derivate.
2
Il costruttore di DenseLayer chiama prima quello di Layer, nella lista di inizializzazione (Lezione 07).
3
tipo_ è un attributo di Layer: stampa_dimensioni lo legge perché è protected, non private.

Una classe derivata: il main

ereditarieta.cpp
int main() {
    DenseLayer d(128, 784);
    d.stampa_tipo();         // metodo ereditato da Layer
    d.stampa_dimensioni();   // metodo di DenseLayer
    return 0;
}

Output:

layer di tipo DenseLayer
DenseLayer: 128 neuroni, 784 ingressi

DenseLayer non ha un metodo stampa_tipo: lo eredita da Layer. Nella classe derivata tipo_ e stampa_tipo non si riscrivono.

Provate: la classe base

In ereditarieta.cpp, un esperimento alla volta:

  1. Alla riga 4 scrivete private: al posto di protected:. Compila?
    No: ‘std::string Layer::tipo_’ is private within this context, alla riga 17: stampa_dimensioni non può più leggere tipo_.
  2. Rimettete protected: e alla riga 15 togliete Layer("DenseLayer"), dalla lista di inizializzazione. Compila?
    No: no matching function for call to ‘Layer::Layer()’. Senza la chiamata esplicita il compilatore usa il costruttore di Layer senza argomenti, che Layer non ha.

La classe std::vector

Per tenere i layer di una rete in un elenco si usa std::vector (da <vector>): un array nell’heap, di dimensione variabile, che gestisce da sé la sua memoria (RAII, Lezione 09).

vettore.cpp
#include <iostream>
#include <vector>
int main() {
1    std::vector<double> v;
2    v.push_back(1.5);
    v.push_back(2.5);
    std::cout << v.size() << " " << v[0] << "\n";
3    for (double x : v) {
        std::cout << x << "\n";
    }
    return 0;
}
1
Un vettore vuoto; il tipo degli elementi va fra parentesi angolari.
2
push_back aggiunge un elemento in fondo.
3
Il for sugli elementi: x prende, uno dopo l’altro, i valori di v.

Output:

2 1.5
1.5
2.5

size() dà il numero di elementi e, come negli array, v[i] è l’elemento i.

std::vector si approfondisce nella Lezione 18; oggi servono solo queste operazioni.

Provate: un indice che non c’è

In vettore.cpp, alla riga 7, scrivete v[2] al posto di v[0]. Cosa succede?

L’AddressSanitizer si ferma con heap-buffer-overflow: v ha due elementi, e come negli array [] non controlla l’indice. L’errore lo trova l’AddressSanitizer, non std::vector.

Il polimorfismo: un vettore di layer

polimorfismo.cpp
#include <iostream>
#include <vector>

class Layer {
public:
1    virtual void forward() const { std::cout << "Layer::forward\n"; }
};

class DenseLayer : public Layer {
private:
    int Nn_, Ni_;
public:
    DenseLayer(int Nn, int Ni) : Nn_(Nn), Ni_(Ni) {}
2    void forward() const override {
        std::cout << "DenseLayer: W x + b, W di " << Nn_ << " x " << Ni_ << "\n";
    }
};

class SigmoidLayer : public Layer {
public:
    void forward() const override { std::cout << "SigmoidLayer: sigma(z)\n"; }
};
1
virtual: quale forward eseguire si decide in esecuzione, in base al tipo vero dell’oggetto.
2
override: sostituisce un metodo virtuale della classe base; qui virtual non si ripete.

Il polimorfismo: il main

polimorfismo.cpp
int main() {
    DenseLayer d(128, 784);
    SigmoidLayer s;
1    std::vector<Layer*> rete;
    rete.push_back(&d);
    rete.push_back(&s);
    for (Layer* l : rete) {
2        l->forward();
    }
    return 0;
}
1
Un DenseLayer è un Layer: il suo indirizzo si mette in un Layer* senza conversioni esplicite.
2
l è un Layer*, ma viene eseguito il forward della classe vera dell’oggetto.

Output:

DenseLayer: W x + b, W di 128 x 784
SigmoidLayer: sigma(z)

La stessa riga, l->forward(), esegue codice diverso a seconda dell’oggetto: è il polimorfismo.

virtual e override

  • Senza virtual il compilatore sceglie il metodo in compilazione, in base al tipo del puntatore, non a quello dell’oggetto a cui si riferisce.
  • Con virtual la scelta avviene in esecuzione, in base al tipo vero dell’oggetto a cui il puntatore si riferisce.
  • override protegge dai refusi: il compilatore controlla che il metodo sostituisca davvero un metodo virtuale della classe base.

Provate: virtual e override

In polimorfismo.cpp, un esperimento alla volta:

  1. Togliete virtual alla riga 6, e override alle righe 14 e 21. Cosa stampa?
    Due volte Layer::forward: senza virtual il metodo si sceglie in base al tipo del puntatore, Layer*.
  2. Rimettete virtual e override, e alla riga 14 scrivete fowrard al posto di forward. Compila?
    No: marked ‘override’, but does not override. Senza override il refuso compilerebbe come un metodo nuovo, che nessuno chiama, e la rete userebbe in silenzio il forward della classe base.

Layer creati con new

layer_new.cpp
#include <iostream>
#include <vector>

class Layer {
public:
1    virtual ~Layer() { std::cout << "~Layer\n"; }
2    virtual void forward() const = 0;
};

class DenseLayer : public Layer {
private:
    int Nn_, Ni_;
public:
    DenseLayer(int Nn, int Ni) : Nn_(Nn), Ni_(Ni) {}
    ~DenseLayer() { std::cout << "~DenseLayer\n"; }
    void forward() const override { std::cout << "DenseLayer: " << Nn_ << " x " << Ni_ << "\n"; }
};

class SigmoidLayer : public Layer {
public:
    ~SigmoidLayer() { std::cout << "~SigmoidLayer\n"; }
    void forward() const override { std::cout << "SigmoidLayer\n"; }
};
1
Il distruttore di Layer è virtual.
2
forward è un metodo virtuale puro: = 0 al posto del corpo.

Layer creati con new (segue)

Nel framework i layer si creano con new e li possiede la rete, che li distrugge quando viene distrutta (Lezione 09: ogni new ha un proprietario). Qui il proprietario è il main.

layer_new.cpp
int main() {
    std::vector<Layer*> rete;
    rete.push_back(new DenseLayer(128, 784));
    rete.push_back(new SigmoidLayer());
    for (Layer* l : rete) {
        l->forward();
    }
    for (Layer* l : rete) {
1        delete l;
    }
    return 0;
}
1
rete contiene solo indirizzi: alla sua distruzione non distrugge gli oggetti puntati. Li distrugge delete, attraverso un Layer*.

Output:

DenseLayer: 128 x 784
SigmoidLayer
~DenseLayer
~Layer
~SigmoidLayer
~Layer

delete esegue prima il distruttore della classe derivata, poi quello della classe base: l’ordine inverso della costruzione.

Il distruttore virtuale

delete l riceve un Layer*. Se il distruttore di Layer non è virtual, il compilatore sceglie quello del tipo del puntatore, ~Layer: i distruttori di DenseLayer e SigmoidLayer non vengono eseguiti.

Avviso

Regola pratica. Una classe con almeno un metodo virtual ha anche il distruttore virtual. Più in generale, il distruttore della base deve essere virtual ogni volta che un oggetto derivato viene distrutto con delete attraverso un puntatore alla base.

Quando il distruttore non ha nulla da fare, come nel framework, si scrive:

virtual ~Layer() = default;

= default chiede al compilatore il distruttore che scriverebbe da solo, qui reso virtual. I distruttori delle classi derivate sono allora virtuali anche senza scriverli: nel framework DenseLayer e SigmoidLayer non ne hanno uno proprio.

Provate: il distruttore non virtuale

In layer_new.cpp togliete virtual alla riga 6. Cosa dice il compilatore, e cosa stampa il programma?

  • -Wall avvisa: deleting object of abstract class type 'Layer' which has non-virtual destructor will cause undefined behavior;
  • dopo i due forward compare solo ~Layer, poi l’AddressSanitizer si ferma con new-delete-type-mismatch: delete ha liberato un DenseLayer come se fosse un Layer;
  • senza l’AddressSanitizer il programma stamperebbe ~Layer due volte e uscirebbe con codice 0: i distruttori di DenseLayer e SigmoidLayer non vengono eseguiti. Se DenseLayer liberasse i suoi pesi nel distruttore, quella memoria resterebbe occupata.
  • con clang su macOS: subito trace trap, senza ~Layer (Layer è astratta, e clang compila il suo distruttore come un’istruzione di arresto).

Le classi astratte

virtual void forward() const = 0; (riga 7) dichiara un metodo virtuale puro: Layer non ne dà un’implementazione. Una classe con almeno un metodo virtuale puro è astratta:

  • non si possono creare oggetti di quella classe. Ha senso: un layer generico non sa calcolare nulla;
  • una classe derivata che non scrive forward resta astratta.

Una classe astratta stabilisce quali metodi devono avere tutte le classi derivate, senza scriverli: è lo schema della classe base Layer del framework, con forward, backward e get_type virtuali puri. I puntatori a una classe astratta si possono usare: rete è un vettore di Layer*.

Provate: le classi astratte

In layer_new.cpp, un esperimento alla volta:

  1. All’inizio del main aggiungete Layer l;. Compila?
    No: cannot declare variable ‘l’ to be of abstract type ‘Layer’.
  2. Togliete la riga 22, il forward di SigmoidLayer. Compila?
    No: invalid new-expression of abstract class type ‘SigmoidLayer’, nella riga di new SigmoidLayer(): SigmoidLayer è rimasta astratta.

Esercizio: le funzioni di loss

Scopo: scrivere una classe derivata da una classe astratta e usarla attraverso un puntatore alla classe base, come le loss del framework.

Una funzione di loss confronta la previsione \(p\) della rete con il valore atteso \(t\) (target). Qui lavora su un solo valore; nel framework, su matrici.

  1. La classe astratta Loss e la derivata MSELoss, con \(L = (p - t)^2\), sono date.
  2. Scrivete la derivata AbsLoss, con \(L = |p - t|\) (std::abs, da <cmath>).
  3. Il main è dato: mette un MSELoss e un AbsLoss in un std::vector<Loss*>, stampa le due loss per \(p = 0{,}5\) e \(t = 1\) e distrugge gli oggetti.

Output atteso: MSELoss: 0.25 e AbsLoss: 0.5, su due righe. Il codice è nelle due slide seguenti; si compila ed esegue con:

cmake -B build && cmake --build build --target loss && ./build/loss

Esercizio sulle loss: le classi date

loss.cpp
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

class Loss {
public:
    virtual ~Loss() {}
    virtual double forward(double p, double t) const = 0;
    virtual std::string get_type() const = 0;
};

class MSELoss : public Loss {
public:
    double forward(double p, double t) const override {
        return (p - t) * (p - t);
    }
    std::string get_type() const override {
        return "MSELoss";
    }
};

Sono le prime righe di loss.cpp.

Loss è astratta: ha due metodi virtuali puri e il distruttore virtuale, perché gli oggetti si distruggono attraverso un Loss*.

Le loss: il file da completare

loss.cpp
// da completare: la classe AbsLoss, derivata
// pubblicamente da Loss, con due metodi:
// - double forward(double p, double t) const override,
//   che restituisce il valore assoluto di p - t;
// - std::string get_type() const override,
//   che restituisce "AbsLoss".

int main() {
    std::vector<Loss*> losses;
    losses.push_back(new MSELoss());
    // scommentate quando AbsLoss è scritta:
    // losses.push_back(new AbsLoss());
    for (Loss* l : losses) {
        std::cout << l->get_type() << ": "
                  << l->forward(0.5, 1.0) << "\n";
    }
    for (Loss* l : losses) {
        delete l;
    }
    return 0;
}

AbsLoss va scritta dopo MSELoss, che fa da modello: stessa struttura, un’altra formula e un altro nome.

Il main crea gli oggetti con new e li distrugge con delete attraverso il Loss*, come i layer della slide “Layer creati con new”.

Soluzione dell’esercizio

loss.cpp
class AbsLoss : public Loss {
public:
    double forward(double p, double t) const override {
        return std::abs(p - t);
    }
    std::string get_type() const override {
        return "AbsLoss";
    }
};

int main() {
    std::vector<Loss*> losses;
    losses.push_back(new MSELoss());
    losses.push_back(new AbsLoss());
    for (Loss* l : losses) {
        std::cout << l->get_type() << ": "
                  << l->forward(0.5, 1.0) << "\n";
    }
    for (Loss* l : losses) {
        delete l;
    }
    return 0;
}

Output:

MSELoss: 0.25
AbsLoss: 0.5

Il ciclo chiama forward e get_type attraverso il Loss*: viene eseguito il metodo della classe vera.

Senza virtual nel distruttore di Loss, g++ -Wall avvisa che il delete ha comportamento indefinito.

Approfondimento: esercizio lampo

Cosa stampa? info() è virtuale e la classe derivata la sostituisce, con un argomento di default diverso.

lampo.cpp
#include <iostream>
class Layer {
public:
    virtual ~Layer() {}
    virtual void info(int livello = 1) const {
        std::cout << "Layer, livello " << livello << "\n";
    }
};

class DenseLayer : public Layer {
public:
    void info(int livello = 2) const override {
        std::cout << "DenseLayer, livello " << livello << "\n";
    }
};

int main() {
    Layer* p = new DenseLayer();
    p->info();
    delete p;
    return 0;
}

Approfondimento: la risposta dell’esercizio lampo

Stampa DenseLayer, livello 1: il metodo della classe derivata, con l’argomento di default della classe base.

  • Quale metodo eseguire si decide in esecuzione, in base al tipo vero dell’oggetto: info è virtuale, quindi parte DenseLayer::info.
  • Quale argomento di default usare si decide in compilazione, in base al tipo del puntatore: il compilatore vede un Layer* e passa il default di Layer::info, cioè 1.

Avviso

Se un metodo virtuale ha argomenti di default, si scrivono gli stessi valori in tutte le classi. Il framework fa così con il metodo virtuale init_weights, che sceglie come inizializzare i pesi: stessi default nella classe base Layer, in DenseLayer e in Sequential.

Discesa su una funzione qualsiasi

Nella Lezione 10 la discesa conosceva una sola funzione, perché chiamava gradF. Per minimizzare una funzione qualsiasi, \(F\) diventa una classe astratta, come la loss dell’esercizio precedente: la discesa usa solo i metodi virtuali valore e gradiente.

La seconda funzione di prova è quella di Rosenbrock, introdotta nel 1960 proprio per mettere alla prova la convergenza dei metodi di minimizzazione:

\[ F(x, y) = (1 - x)^2 + 100\,(y - x^2)^2 \]

Il minimo è in \((1, 1)\), dove \(F = 0\), in fondo a una valle stretta e curva lungo la parabola \(y = x^2\). Il punto di partenza abituale è \((-1{,}2;\ 1)\). Il gradiente è

\[ \nabla F = \big(-2\,(1 - x) - 400\,x\,(y - x^2),\ \ 200\,(y - x^2)\big) \]

Esercizio: la discesa per una funzione qualsiasi

Scopo: usare una classe astratta come schema comune: la stessa funzione discesa minimizza due funzioni diverse.

  1. Copiate Vettore2D.hpp e Vettore2D.cpp da LEZIONE_10, oppure dalle slide di soluzione in fondo.
  2. In Funzione2D.hpp sono date la classe astratta Funzione2D e la classe Paraboloide, la \(F = x^2 + 4y^2\) della Lezione 10. Scrivete in fondo la classe Rosenbrock, sul modello di Paraboloide.
  3. In discesa.cpp scrivete per prima la funzione discesa: è quella della Lezione 10 con un argomento in più, const Funzione2D& f, e con f.gradiente(x) al posto di gradF(x). Le funzioni prova e main, che la seguono, sono date. Le parti date e quelle da scrivere sono nelle slide seguenti.

Esercizio: la discesa per una funzione qualsiasi (segue)

Si compila ed esegue con:

cmake -B build && cmake --build build --target discesa && ./build/discesa

Output atteso:

Paraboloide, eta = 0.2: 32 passi, x = (1.59173e-07, 7.95866e-08), F = 5.06722e-14
Rosenbrock, eta = 0.001: 32076 passi, x = (0.999999, 0.999998), F = 1.25172e-12
Rosenbrock, eta = 0.0019: 16851 passi, x = (0.999999, 0.999998), F = 1.25181e-12
Rosenbrock, eta = 0.002: non converge, x = (1.00041, 0.997295), F = 0.00124955

Esercizio sulla discesa: i file dati

Funzione2D.hpp
#pragma once
#include "Vettore2D.hpp"

class Funzione2D {
public:
    virtual ~Funzione2D() {}
    virtual double valore(const Vettore2D& p) const = 0;
    virtual Vettore2D gradiente(const Vettore2D& p) const = 0;
};

class Paraboloide : public Funzione2D {
public:
    double valore(const Vettore2D& p) const override {
        double x = p.getX(), y = p.getY();
        return x * x + 4.0 * y * y;
    }
    Vettore2D gradiente(const Vettore2D& p) const override {
        return Vettore2D(2.0 * p.getX(), 8.0 * p.getY());
    }
};

Da Vettore2D servono getX, getY, operator-, operator* (vettore per scalare) e norma.

Funzione2D è astratta: stabilisce che ogni funzione abbia valore e gradiente, senza scriverli.

Paraboloide li scrive per \(F = x^2 + 4y^2\), con \(\nabla F = (2x,\ 8y)\): è la \(F\) e la gradF della Lezione 10.

Vettore2D.hpp e Vettore2D.cpp sono quelli della Lezione 10, nelle slide seguenti.

Funzione2D: il codice da scrivere

Funzione2D.hpp
class Rosenbrock : public Funzione2D {
public:
    double valore(const Vettore2D& p) const override {
        // da completare: (1 - x)^2 + 100 (y - x^2)^2
        return 0.0;
    }
    Vettore2D gradiente(const Vettore2D& p) const override {
        // da completare: (-2 (1-x) - 400 x (y-x^2), 200 (y-x^2))
        return Vettore2D(0.0, 0.0);
    }
};
discesa.cpp
#include <iostream>
#include <string>
#include "Funzione2D.hpp"
int discesa(const Funzione2D& f, Vettore2D& x,
            double eta, int max_passi) {
    for (int n = 1; n <= max_passi; ++n) {
        // da completare: il passo (x meno gradiente per eta) e g,
        // la norma del gradiente nel nuovo punto
        double g = 0.0;
        if (g < 1e-6) return n;
        if (g > 1e10) return -1;
    }
    return max_passi;
}

Rosenbrock va in fondo a Funzione2D.hpp, dopo Paraboloide: completate i due metodi al posto dei return provvisori, con x = p.getX() e y = p.getY().

discesa va all’inizio di discesa.cpp, prima di prova e del main.

x è passato per riferimento: alla fine della chiamata contiene l’ultimo punto raggiunto, che prova stampa.

Funzione2D: prova e main

discesa.cpp
void prova(const Funzione2D& f, const std::string& nome, Vettore2D x, double eta) {
    const int max_passi = 1000000;
    int passi = discesa(f, x, eta, max_passi);
    std::cout << nome << ", eta = " << eta << ": ";
    if (passi < 0) {
        std::cout << "diverge\n";
        return;
    }
    if (passi == max_passi) std::cout << "non converge";
    else                    std::cout << passi << " passi";
    std::cout << ", x = (" << x.getX() << ", " << x.getY() << "), F = " << f.valore(x) << "\n";
}

int main() {
    Paraboloide p;
    Rosenbrock r;
    prova(p, "Paraboloide", Vettore2D(2.0, 1.0), 0.2);
    prova(r, "Rosenbrock", Vettore2D(-1.2, 1.0), 0.001);
    prova(r, "Rosenbrock", Vettore2D(-1.2, 1.0), 0.0019);
    prova(r, "Rosenbrock", Vettore2D(-1.2, 1.0), 0.002);
    return 0;
}

Sono date: vanno copiate in discesa.cpp dopo discesa.

Soluzione dell’esercizio: Vettore2D.hpp

Vettore2D.hpp
#pragma once

class Vettore2D {
private:
    double x_, y_;

public:
    Vettore2D(double x, double y) : x_(x), y_(y) {}

    Vettore2D operator+(const Vettore2D& altro) const;
    Vettore2D operator-(const Vettore2D& altro) const;
    Vettore2D operator*(double scalare) const;
    double norma() const;

    double getX() const { return x_; }
    double getY() const { return y_; }
};

Identico alla soluzione della Lezione 10.

Soluzione dell’esercizio: Vettore2D.cpp

Vettore2D.cpp
#include "Vettore2D.hpp"
#include <cmath>

Vettore2D Vettore2D::operator+(const Vettore2D& altro) const {
    return Vettore2D(x_ + altro.x_, y_ + altro.y_);
}

Vettore2D Vettore2D::operator-(const Vettore2D& altro) const {
    return Vettore2D(x_ - altro.x_, y_ - altro.y_);
}

Vettore2D Vettore2D::operator*(double scalare) const {
    return Vettore2D(x_ * scalare, y_ * scalare);
}

double Vettore2D::norma() const {
    return std::sqrt(x_ * x_ + y_ * y_);
}

Identico alla soluzione della Lezione 10.

Soluzione dell’esercizio: Rosenbrock

Funzione2D.hpp
class Rosenbrock : public Funzione2D {
public:
    double valore(const Vettore2D& p) const override {
        double x = p.getX(), y = p.getY();
        return (1.0 - x) * (1.0 - x) + 100.0 * (y - x * x) * (y - x * x);
    }
    Vettore2D gradiente(const Vettore2D& p) const override {
        double x = p.getX(), y = p.getY();
        return Vettore2D(-2.0 * (1.0 - x) - 400.0 * x * (y - x * x),
                         200.0 * (y - x * x));
    }
};

Paraboloide e Rosenbrock hanno gli stessi metodi e calcoli diversi: discesa non ha bisogno di sapere quale delle due riceve.

Soluzione dell’esercizio: discesa

discesa.cpp
#include <iostream>
#include <string>
#include "Funzione2D.hpp"

int discesa(const Funzione2D& f, Vettore2D& x,
            double eta, int max_passi) {
    for (int n = 1; n <= max_passi; ++n) {
1        x = x - f.gradiente(x) * eta;
        double g = f.gradiente(x).norma();
        if (g < 1e-6) return n;
        if (g > 1e10) return -1;
    }
    return max_passi;
}
1
gradiente è virtuale: si esegue il metodo della classe vera dell’oggetto, Paraboloide o Rosenbrock.

Un riferimento alla classe base funziona come un puntatore: f è un const Funzione2D&, e f.gradiente(x) esegue il metodo della classe vera.

prova e il main sono quelli dati, nella slide seguente.

Soluzione dell’esercizio: prova e main

discesa.cpp
void prova(const Funzione2D& f, const std::string& nome, Vettore2D x, double eta) {
    const int max_passi = 1000000;
    int passi = discesa(f, x, eta, max_passi);
    std::cout << nome << ", eta = " << eta << ": ";
    if (passi < 0) {
        std::cout << "diverge\n";
        return;
    }
    if (passi == max_passi) std::cout << "non converge";
    else                    std::cout << passi << " passi";
    std::cout << ", x = (" << x.getX() << ", " << x.getY() << "), F = " << f.valore(x) << "\n";
}

int main() {
    Paraboloide p;
    Rosenbrock r;
    prova(p, "Paraboloide", Vettore2D(2.0, 1.0), 0.2);
    prova(r, "Rosenbrock", Vettore2D(-1.2, 1.0), 0.001);
    prova(r, "Rosenbrock", Vettore2D(-1.2, 1.0), 0.0019);
    prova(r, "Rosenbrock", Vettore2D(-1.2, 1.0), 0.002);
    return 0;
}

Soluzione dell’esercizio: l’output

Paraboloide, eta = 0.2: 32 passi, x = (1.59173e-07, 7.95866e-08), F = 5.06722e-14
Rosenbrock, eta = 0.001: 32076 passi, x = (0.999999, 0.999998), F = 1.25172e-12
Rosenbrock, eta = 0.0019: 16851 passi, x = (0.999999, 0.999998), F = 1.25181e-12
Rosenbrock, eta = 0.002: non converge, x = (1.00041, 0.997295), F = 0.00124955

Lo stesso codice di discesa minimizza le due funzioni: è il polimorfismo. Il paraboloide converge in 32 passi, come nella Lezione 10. La funzione di Rosenbrock richiede decine di migliaia di passi, e con eta = 0,002 la discesa oscilla vicino al minimo, senza convergere né divergere.

È la difficoltà per cui Rosenbrock si usa come prova: da \((-1{,}2;\ 1)\) la discesa arriva in 5 passi sul fondo della valle (\(F\) scende da 24,2 a 4,1), ma lungo il fondo la pendenza è piccola e ogni passo avanza di poco verso il minimo. Con eta = 0,002 i passi sono troppo lunghi, e la discesa rimbalza da una parete all’altra della valle.

L’esercizio verrà ripreso più avanti.