Appunti esame Matematica per l'intelligenza artificiale

MIA 2022

Titolare:

• Francesco Vaccarino
• Lamberto Rondoni
• Andrea Tosin
• Francesco Della Santa (Post Doc)

Ricevimento su appuntamento

3 ore lunedì in presenza

3 ore martedì, online sino alle vacanze pasquali, dopo misto (fino al 17 maggio)

• 24 - 31 maggio Rondoni in aula 10 D
• 7 giugno Vaccarino online

Il lunedì: Della Santa e poi Tosin fino al 04/04

• Della Santa - Della Santa il 11/04
• Della Santa - Rondoni dal 2/05

Vaccarino Tosin Rondoni

• AI/ML
• CBO
• Rapporto tra learning e sistemi dinamici

35 h 10 h 75 h

Della Santa

Esercizi + lab con uso di Python 20 h

ESAME

Tesina (ita/ing)

TI VOGLIO BENE

Il termine λ(m^i_n - x^i_n)

esprime un rilassamento di x^i_n verso m^i_n

• η^i_n è una variabile aleatoria di media nulla: ⟨η^i_n⟩ = 0
• e varianza strettamente positiva: ⟨(η^i_n)²⟩ > 0 che

rappresenta una fluttuazione stocastica

Nota: ogni particella ad ogni iterazione ha una variabile aleatoria ad essa associata che é indipendente rispetto alle variabili aleatorie associate alle altre particelle e alle variabili aleatorie dei passi precedenti (tutto é indipendente)

Supponiamo η^i_n i.i.d e varianza unitaria: ⟨(η^i_n)²⟩ = 1

L'algoritmo

si chiama CBO = Consensus-Based Optimisation

Analisi di base dell'algoritmo CBO

Hp: Supponiamo che ω: ℝⁿ → ℝ goda delle seguenti proprietà:

1. ∃ c, C > 0 con c < C tali che c ≤ ω(x) ≤ C ∀ x ∈ ℝⁿ

ω é sempre strettamente positiva

2. x → ω(x), x → xω(x) sono lipschitziane su ℝⁿ cioè:

|ω(y) - ω(x)| ≤ L_ω|y - x| ∀ x, y ∈ ℝⁿ

|y ω(y) - x ω(x)| ≤ L_xω|y - x| ∀ x, y ∈ ℝⁿ

dove L_ω, L_xω > 0 sono due costanti.

≔ M < + ∞

∬ |ω(y) - ω(x₁)| dy(x, y) +

≤ _G/^c² [ ∬ |y - x₁| dy(x, y) + L_ω ∬ |x - y| dy(x, y)]

Per l'arbitrarietà di y ε Γ (f_N ^R, f^R) questa disuguaglianza vale anche passando al min su y

⇒ |m [f^R] - m ^L ≤ _G/^c² [M_Lω + L_xω] ∀_N (u_e ^N - f^e) → N → 0

Se supponiamo N molto grande possiamo riscrivere l'algoritmo CBO come:

x_i ^k+1 = x_i ^k + λ (m [f^e] - x_i ^k) + θ (m [f^e] - x_i ^R)η_i ^R

Chiamiamo:

• f^e la distribuzione teorica delle particule nel limite N → ∞ ;
• m [f^e] la posizione media pesata teorica delle particule

= λ∫_Rⁿ (m[f^*] - x) φ(x,t) dx

= λ (m[f^*]∫_Rⁿ φ(x,t) dx - ∫_Rⁿ x φ(x,t) dx)

=>

dM(t)/dt = λ (m[f^*] - M(t))

(*) Hp. Supponiamo che per tempi lunghi la distribuzione f(x,t) converga ad una distribuzione f_p∞(x). Più precisamente:

f_p∞ ∈ B₁(R)_, lim W₁(f_(·,t), f_p∞) = 0

_{t → ∞}

Prop. Si ha:

m[f](t) = ∫_R xω(x)φ(x,t) dx / ∫_R ω(x)φ(x,t) dx → t →

∫_R xω(x)f_p∞(x) dx / ∫_R ω(x)f_p∞(x) dx

Dimostrazione: Il risultato dipende dall'ipotesi (*) usando la stessa tecnica già vista nella dimostrazione del fatto che m^∞ = m[f^*]

Hp. Supponiamo che f( ·,t) →_{t →} f_p∞ in B₁(R) in maniera esponenzialmente veloce cioè:

∃ a,b > 0: W₁(f( ·,t), f_p∞) ≤ ae^-bt

2λ - λ² - θ² > 0

perché é presente al denominatore (≠0) e non voglio che abbia influenza nei segni ( >0)

Sotto questa condizione verifichiamo che:

(i) G tende ad un limite G_∞ per t → ∞:

lim_t G(t) =

λ² + θ² m² [f_p∞] + 2λ - 2λ² - 2θ² m² [f_p∞]

2λ - θ² - λ²

= m² [f_p∞]

(ii) G tende al valore m² [f_p∞] in modo esponenzialmente veloce:

|G(t) - m² [f_p∞]| =

(λ² + θ²) m² [f] + (2λ - 2λ² - 2θ²) m² [f_p∞] M - m² [f_p∞]

(2λ - λ² - θ²)

=

(λ² + θ²) m² [f] - m² [f_p∞]

2λ - λ² - θ²

< λ² + θ² |m² [f] - m² [f_p∞]|

2λ - λ² - θ² + 2λ - 2λ² - 2θ² [m² [G]M - m² [f_p∞]]

Osserviamo che:

(ii: a) | m² [f] - m² [f_p∞] | = |m [f]| m [f_p∞] | - |m [f_p∞]|

<= |m [f]| + |m [f_p∞]| limitata

Scegliamo: \( \omega(x) = e^{-aF(x)} \), \( a > 0 \)

Verifichiamo che questa \( \omega \) soddisfa le ipotesi previste dalla teoria:

• \( 0 < F \leq \overline{F}(x) \leq \overline{\overline{F}} < +\infty \quad \forall x \in \mathbb{R} \)

\( \Rightarrow \omega(x) = e^{-a\overline{F}(x)} \geq e^{-a\overline{\overline{F}}} =: c > 0 \)

\( \omega(x) = e^{-aF(x)} \leq e^{-aF} =: C \gt 0 \)

Quindi \( c \leq \omega(x) \leq C \quad \forall x \in \mathbb{R} \)

(ii) Lipschitzianità di \( \omega(x) \):

\( |\omega(y) - \omega(x)| = |e^{-aF(y)} - e^{-aF(x)}| \leq |-a[F(y) - (-aF(x))]| \)

\( = a |F(y) - F(x)| \)

\( \leq aL_F |y-x| \)

Quindi \( \omega \) è lipschitziana su \(\mathbb{R}\) con \( L = aL_F \)

(iii) Lipschitzianità di \( x \omega(x) \):

Condizione sufficiente: limitatezza di \( \frac{d}{dx} (x\omega(x)) = \omega(x) + x \omega'(x) \)

\( = e^{-aF(x)} + x(-aF'(x) e^{-aF(x)}) \)

\( = e^{-aF(x)} (1 - a x F'(x)) \)

Come condizione sufficiente possiamo chiedere che \( F'(x) \longrightarrow 0 \) per \(|x| \longrightarrow +\infty\) abbastanza velocemente (almeno come \( \frac{1}{x} \))

Bontà dell'approssimazione fornita dal CBO

Supponiamo che F abbia un unico punto di minimo globale ̄ ∈ ℝ

Vediamo come accertare se il punto ̃ (punto di consenso delle particelle prodotto dal CBO) è una buona approssimazione di ̄

Teorema

Supponiamo che esista > 0 tale che

\(\int_{\mathbb{R}} \omega(x) f_0(x) \, dx < \int_{\mathbb{R}} \omega(x) f(x,t) \, dx \quad \forall t \geq 0\)

Allora ̃ si può rendere vicino a piacere a ̄

Dimostrazione

Per la monotonia del logaritmo, abbiamo:

• \(\frac{1}{2} \log \left( \int_{\mathbb{R}} \omega(x) f_0(x) \, dx \right) \leq \frac{1}{2} \log \left( \int_{\mathbb{R}} \omega(x) f(x,t) \, dx \right)\)

\(-\frac{1}{2} \log \left( \int_{\mathbb{R}} \omega(x) f_0(x) \, dx \right) \geq -\frac{1}{2} \log \left( \int_{\mathbb{R}} \omega(x) f(x,t) \, dx \right)\)

\(\delta(x - \bar{x}) \in \mathcal{G}_1(\mathbb{R}), \Theta_1(\mathbb{R})\)