Aplicatii ale fluxului maxim in inteligenta artificiala

Patru exemple explicate prin retele: segmentarea imaginilor, alocarea sarcinilor, distribuirea cererilor pe GPU si separarea comunitatilor sociale. Fiecare exemplu precizeaza ce reprezinta nodurile, arcele, capacitatile si rezultatul.

Principiul comun

O retea de flux contine o sursa S, o destinatie T si arce cu capacitati nenegative. Fluxul pe fiecare arc nu poate depasi capacitatea, iar in nodurile intermediare fluxul intrat este egal cu cel iesit.

Fluxul maxim este cantitatea maxima trimisa de la S la T. Teorema flux maxim = capacitatea taieturii minime leaga problema transportului de problema separarii unei retele.

Atentie: capacitatea unui arc nu este automat o distanta. In exemplele 1 si 4, capacitatile sunt penalizari sau intensitati ale legaturilor; in exemplele 2 si 3, sunt limite de alocare.

1. Aplicatii ale fluxului maxim in AI

Nr.AplicatieCe reprezinta fluxul?Ce se optimizeaza?
1Segmentarea imaginilorFlux intr-o retea construita din pixeliSepararea obiectelor de fundal
2Alocarea sarcinilor catre robotiSarcini atribuite robotilorNumarul maxim de sarcini executabile
3Alocarea resurselor pentru modele AICapacitate de procesare GPUNumarul maxim de cereri AI procesate
4Procesarea limbajului naturalCorespondente intre cuvinte sau concepteNumarul maxim de asocieri compatibile
5Sisteme multi-agentSarcini distribuite intre agentiNumarul maxim de sarcini acoperite
6Analiza retelelor socialeFlux informational posibil intre comunitatiCapacitatea maxima de transmitere
7Planificarea transportului cu vehicule autonomeVehicule care traverseaza o retea rutieraNumarul maxim de vehicule transportate
8Sisteme de recomandareRecomandari alocate utilizatorilorNumarul maxim de recomandari compatibile

Unele aplicatii folosesc direct fluxul maxim, iar altele se modeleaza prin cuplaj maxim sau prin taietura minima.

1. Segmentarea imaginilor: obiect sau fundal?

Problema. Pentru fiecare pixel trebuie sa decidem daca apartine obiectului sau fundalului. Conectam pixelii intre ei si la doua noduri speciale: S (obiect) si T (fundal).

SP1P2P3P4Tcost etichetavecinatatecost etichetaObiectFundal

De unde vin capacitatile? Arcele pixel-sursa si pixel-destinatie codifica penalizarea clasificarii acelui pixel intr-o clasa sau alta. Arcele dintre vecini penalizeaza separarea unor pixeli asemanatori (de exemplu, in functie de diferenta de culoare).

Ce calculam? Taietura minima S-T determina clasificarea binara cu cost minim pentru energia reprezentata de retea. Calculul fluxului maxim ofera valoarea acelei taieturi.

Interpretare: o legatura puternica intre pixeli face costisitoare separarea lor; de aceea pot trece impreuna din obiect in fundal atunci cand modificam o singura penalizare.

2. Alocarea sarcinilor catre roboti

Problema. Avem trei roboti si patru sarcini. Fiecare robot poate executa cel mult o sarcina; fiecare sarcina poate fi atribuita unui singur robot. Nu toti robotii sunt compatibili cu toate sarcinile.

RobotSarcini posibileCapacitate
R1A, B1
R2B, C1
R3A, C, D1
SR1R2R3ABCDTToate arcele au capacitatea 1; portocaliu = o alocare optima.

Modelare. S→robot are capacitatea 1, robot→sarcina exista doar daca robotul poate executa sarcina si are capacitatea 1, iar sarcina→T are capacitatea 1.

Rezultat. Fluxul maxim este 3, de exemplu R1→A, R2→B, R3→D. Sarcina C ramane neatribuita. Nu putem avea flux 4 deoarece doar trei arce de capacitate 1 pleaca din S.

3. Alocarea cererilor AI catre servere GPU

Problema. Un serviciu AI trebuie sa proceseze cereri pentru trei tipuri de modele. Unele servere au suficienta memorie pentru toate modelele, altele doar pentru unele. Dorim sa procesam cat mai multe cereri intr-un minut.

Cereri pe minut

Model M1: 7
Model M2: 6
Model M3: 5
Total: 18

Capacitati servere

GPU1: 5 cereri/min
GPU2: 8 cereri/min
GPU3: 4 cereri/min
Total: 17

Compatibilitati

M1 → GPU1, GPU2
M2 → GPU2, GPU3
M3 → GPU1, GPU3

Reteaua de flux

SM1M2M3GPU1GPU2GPU3T765584compatibilitateArcele model → GPU au capacitate 18 (suficient de mare).

De unde vin valorile?

Capacitatile 7, 6, 5 de la sursa sunt numarul de cereri sosite pentru fiecare model intr-un minut. Capacitatile 5, 8, 4 catre destinatie sunt numarul maxim de cereri pe care fiecare server le poate procesa intr-un minut. Un arc model→GPU exista numai daca serverul este compatibil cu acel model; capacitatea 18 pe aceste arce nu restrictioneaza suplimentar repartizarea.

Calculul unei alocari optime

ServerModel M1Model M2Model M3Total
GPU13025
GPU24408
GPU30224
Total procesat76417

Rezultat: flux maxim = 17 cereri/minut. Aceasta alocare este realizabila si foloseste toate cele 17 unitati de capacitate GPU. Cum suma capacitatilor serverelor este 17, niciun flux nu poate fi mai mare. O cerere M3 ramane in asteptare.

Limita modelului: presupunem cereri de consum unitar si capacitati constante pe minut. Daca modelele consuma durate sau cantitati diferite de memorie, fluxul maxim simplu nu mai descrie integral problema; poate fi necesara programare intreaga sau planificare cu constrangeri.

4. Separarea a doua comunitati intr-o retea sociala

Problema. Intr-o retea sociala vrem sa identificam legaturile care separa doi utilizatori reprezentativi, A si F, cu un cost total minim. Nodurile reprezinta utilizatori; capacitatea unui arc exprima forta unei legaturi (de exemplu, o masura a interactiunilor).

Vom considera un graf neorientat: fiecare muchie are o capacitate de separare, iar o taietura plateste acea capacitate o singura data. Pentru calculul fluxului se poate reprezenta fiecare muchie prin doua arce orientate opuse, cu aceeasi capacitate.

43221344ABCDEFMuchiile rosii punctate formeaza taietura de capacitate 2 + 1 = 3.

Ce inseamna numerele de pe muchii?

Valorile sunt intensitati ipotetice ale legaturilor, nu distante geometrice. De exemplu, legatura A-B are capacitatea 4, B-D are 2, iar C-E are 1. O legatura cu valoare mare este mai costisitor de taiat.

Cum obtinem raspunsul?

Alegem partitionarea {A, B, C} si {D, E, F}. Singurele muchii care trec intre cele doua grupuri sunt B-D (capacitate 2) si C-E (capacitate 1). Capacitatea taieturii este 2 + 1 = 3.

Este si o limita inferioara: exista doua trasee A→B→D→F si A→C→E→F care pot transporta fluxuri 2 si, respectiv, 1. Deci fluxul maxim este cel putin 3. Taietura arata ca nu poate depasi 3. Prin urmare flux maxim = taietura minima = 3.

Interpretare: legaturile B-D si C-E sunt punctele de conexiune cele mai ieftin de intrerupt intre A si F. Aceasta este o separare intre doua noduri fixate, nu un algoritm general care descopera automat toate comunitatile unei retele sociale.

Experiment: ce se intampla daca intarim legatura B-D?

Modifica valoarea legaturii B-D si observa cum se schimba taietura minima.

Calculul examineaza toate partitionarile posibile cu A in grupul sursei si F in grupul destinatiei.

Comparatie finala

AplicatieCe inseamna capacitatea?Ce cautam?
Segmentare imaginePenalizare de clasificare sau separareTaietura minima
Alocare robotiNumar de sarcini alocabileFlux maxim / cuplaj maxim
Procesare GPUCereri pe minutFlux maxim
Retea socialaIntensitatea legaturiiTaietura minima intre A si F

Ideea esentiala: acelasi algoritm matematic poate rezolva probleme foarte diferite, dar interpretarea capacitatilor trebuie construita separat pentru fiecare problema.