Problema dinainte a fost un pretext pentru a va introduce notiunea de 'functie convexa':http://en.wikipedia.org/wiki/Convex_function .O astfel de functie are propretatea ca graficul ei se afla sub orice segment de dreapta ce uneste doua puncte ale graficului.
*Rezolvarea pe scurt:*
Functia <tex>2 dist(M, A) + dist(M, B) + dist(M, C)</tex> e o functie convexa. Functiile convexe isi ating maximul pe marginea domeniului de definitie. Astfel e de ajuns sa evaluam functia in punctele A, B si C si gasim ca maximul este 13 si e realizat in punctul C.
Daca f:X->R unde x e un domeniu convex (interval etc.) atunci pentru oricare doua puncte x1 si x2 din X si orice t din intervalul [0, 1] avem ca f(tx1 + (1-t)x2) <= tf(x1) + (1-t)f(x2).
*Functii convexe:*
Problema este pretext pentru a discuta notiunea de 'functie convexa':http://en.wikipedia.org/wiki/Convex_function. O astfel de functie are proprietatea ca pentru oricare doua puncte de pe graficul ei, graficul se afla sub segmentul determinat de cele puncte. Mai formal, daca <tex>f:X->R</tex> unde <tex>X</tex> e un domeniu convex (interval etc.) atunci pentru oricare doua puncte <tex>x1</tex> si <tex>x2</tex> din <tex>X</tex> si orice <tex>t</tex> din intervalul <tex>[0, 1]</tex> avem ca <tex>f(tx_{1} + (1-t)x_{2}) \le tf(x_{1}) + (1-t)f(x_{2})</tex>. <tex>X</tex> poate fi orice spatiu vectorial, R, interval in o dimensiune, poligon convex in doua si asa mai departe.
O proprietate importanta a functiilor convexe este ca au doar un minim local care este si global. Astfel problema *minimizarii valorii unei functii* este mai simplu de rezolvat pentru functii convexe.
In *machine learning* apare frecvent aceasta problema. Functiile generale nu sunt usor de minimizat. Nu au o forma care poate fi rezolvata matematic sau sunt neregulate si au multe optime locale. Pentru a putea obtine solutii bune, de multe ori functiile generale sunt aproximate sau marginite de functii convexe pentru care exista algoritmi eficienti de minimizare, cum ar fi cautare ternara pentru cazul uni dimensional sau gradient descent pentru cazul general.
O proprietate importanta a functiilor convexe este ca au doar un minim local care este si global. Astfel problema *minimizarii valorii unei functii multi dimensionale* este mai simplu de rezolvat pentru functii convexe. Ea apare frecvent in *machine learning*. Functiile generale nu sunt usor de minimizat. Nu au o forma care poate fi rezolvata matematic sau sunt neregulate si au multe optime locale. Pentru a putea obtine solutii bune, de multe ori functiile generale sunt aproximate de functii convexe pentru care exista algoritmi eficienti de minimizare, cum ar fi 'cautare ternara':http://en.wikipedia.org/wiki/Ternary_search pentru cazul unidimensional sau 'gradient descent':http://en.wikipedia.org/wiki/Gradient_descent pentru cazul general.
!{margin: 10px; margin-right: 5; border: 1px solid gray;}<blog/suma-in-triunghi-rezolvare?graph.gif!
Sa revenim la problema noastra:
*Rezolvarea mai detaliata:*
Functia distanta euclidiana fata de un punct fix e o functie convexa.
_demonstratie:_
Vedem usor daca facem un grafic care este un con sau putem incerca sa ne uitam la derivate.
Functia distanta euclidiana e o functie strict convexa. E simplu de demonstrat ca suma a doua functii convexe e tot o functie convexa. De aici rezulta ca 2dist(M, A) + dist(M, B) + dist(M, C) e si ea o functie convexa.
Maximul pentru o functie convexa e realizat pe marginea domeniului de definitie. Asta e usor de vazut mai ales pentru functii unidimensionale cum ar fi parabolele.
Astfel e deajuns sa ne uitam la valoarea functiei in punctele A, B si C. Obtinem ca C e punctul cautat.
Suma a doua functii convexe este tot o functie convexa.
_demonstratie:_
<tex>f_{1}(tx_{1} + (1-t)x_{2}) \le tf_{1}(x_{1}) + (1-t)f_{1}(x_{2})</tex>
<tex>f_{2}(tx_{1} + (1-t)x_{2}) \le tf_{2}(x_{1}) + (1-t)f_{2}(x_{2})</tex>
=>
<tex>f_{1}(tx_{1} + (1-t)x_{2}) + f_{2}(tx_{1} + (1-t)x_{2}) \le t(f_{1}(x_{1}) + f_{2}(x_{1})) +</tex>
<tex>(1-t)(f_{1}(x_{2}) + f_{2}(x_{2}))</tex>
Am facut un grafic folosind octave unde punctele A, B si C au coordonatele (0, 0), (3, 0) respectiv (0, 4), iar culoarea graficului reprezinta suma ceruta in problema.
Astfel <tex>2dist(M, A) + dist(M, B) + dist(M, C)</tex> e si ea o functie convexa.
!{margin: 1px; margin-right: 10px; border: 1px solid gray;}<blog/suma-in-triunghi-rezolvare?graph.gif!
Maximul pentru o functie convexa e realizat pe marginea domeniului de definitie.
_demonstratie:_
Din definitie, graficul intre <tex>x1</tex> si <tex>x2</tex> se afla sub segmentul determinat de <tex>(x1, f(x1))</tex> si <tex>(x_{2}, f(x_{2}))</tex> astfel pentru <tex>x_{1}</tex> si <tex>x_{2}</tex> pe contur unul dintre cele doua puncte va fi mai sus decat toate restul din grafic.
Acum am demonstrat toti pasii din prima propozitie a articolului.
Aveti aici codul octave cu care am generat graficul de mai sus.
In graficul alaturat puteti vedea cum se comporta functia. Punctele A, B si C au coordonatele (0, 0), (3, 0) respectiv (0, 4), iar culoarea graficului reprezinta suma ceruta in problema.
Aveti aici codul in 'Octave':http://www.gnu.org/software/octave/ cu care e generat.
== code(c) |
dist = @(x, y, x1, y1) sqrt((x - x1).^2 + (y - y1).^2)
sumt = @(x, y) 2 * dist(x, y, 0, 0) + dist(x, y, 3, 0) + dist(x, y, 0, 4)
x=linspace(0, 3, 50)
y=linspace(0, 4, 50)
[xx,yy]=meshgrid(x,y)
contourf(xx,yy,sumt(xx,yy))
x = linspace(0, 3, 50)
y = linspace(0, 4, 50)
[xx, yy] = meshgrid(x, y)
contourf(xx, yy, sumt(xx, yy))
==
Sper ca v-am deschis apetitul pentru functii convexe :).
'Adapost2':problema/adapost2 se poate rezolva folosind idei din acest post.
Cerinta de gasire a maximului e putin fortata pentru a face problema posibil de rezolvat in cap. Pentru ca in general la functii convexe cautam minimul. Putem avea maxime locale in orice colt al frontierei, deci pentru o frontiera cu multe colturi nu avem algoritmi eficienti.
'Adapost2':problema/adapost2 se poate rezolva folosind idei din acest post.
Sper ca v-am deschis apetitul pentru functii convexe :).
