Problema de mate-info

Updated

De cateva zile ma chinui cu urmatoarea problema. Poate reusiti sa-mi dati ceva pointeri buni.

Se da un un set de puncte (> 10k evenimente) de forma (x1,x2,x3,...,xn, w), unde xi,i=1,n sunt coordonatele axelor ortogonale Oi iar w greutatea punctului. Se cer vectorii x0i care definesc marginile binilor pe axele Oi astfel incat in fiecare bin n-dimensional se indeplineste conditia sqrt(sum(w^2))/sum(w) < w0 (unde primul factor e insumat peste toate evenimentele din bin) si unde w0 este cunoscut. Sunt interesat in rezolvarea problemei in 3-4 dimensiuni dar daca exista un algoritm mai general sunt bucuros sa-l aflu. Daca nu e clara problema semnalati si o sa incerc sa dau o explicatie mai buna. HELP! Incerc sa fiu mai clar si sa dau un exemplu 1D. [caption id="attachment_1640" align="aligncenter" width="400"]Variable Variable [/caption]

In imaginea de mai sus avem 3k evenimente caracterizate de vectorul (var,w). Valoarea var este reprezentata pe axa Ox iar w corespunde segmentelor verticale. Prima histograma este "rebinned" de la dreapta la stanga astfel incat in fiecare bin functia descrisa mai sus este <0.2 (se insumeaza peste toate evenimentele care cad in intervalul unui bin. Conditia de pornire este o histograma cu 100k bini egal echidistanti in intervalul [0.1,0.3] si se ajunge la urmatorul vector al binilor 1D [0.1, 0.192334, 0.199014, 0.205538, 0.22110200000000002, 0.222138, 0.223216, 0.224592, 0.22581, 0.226992, 0.228162, 0.3].

   Send article as PDF   

6 Comments

  1. lektor

    Problema este puternic dependenta de constanta w_0 precum si de numarul de evenimente. Daca w_0 e prea mic, nicio alegere de bini nu poate functiona, iar daca w_0 e destul de mare, atunci orice alegere de bini e la fel de buna. E in legatura cu faptul ca intr-un spatiu finit dimensional normele l^2 si l^1 sint echivalente.

    Daca nu introduci mai multe restrictii, problema nu are intotdeauna o solutie. Daca are, atunci niciodata nu e unica.

  2. Daca w_0 este prea mic atunci rezultatul e binul maxim .... Nu este o problema daca nu exista o solutie, w_0 poate fi ajustat. Cat despre un w_0 mare : e suficienta o singura solutie .... nu trebuie gasite toate.

    Poti sa explici un pic mai mult ce intelegi prin normele l^2 si l^1?

  3. lektor

    Mai jos formule sint in latex. Daca $A=\{a_j\}_{j=1}^N$ e un vector cu coeficienti reali de dimensiune $N$, atunci
    $||A||_2=\sqrt{\sum_{j=1}^N a_j^2}$ este norma $l^2$, iar $||A||_1=\sum_{j=1}^N|a_j|}$ este norma $l^1$. Intr-un spatiu finit dimensional, toate normele sint echivalente. Asta inseamna ca exista doua constante pozitive $c_1$ si $c_2$ depinzind de dimensiunea $N$, astfel incit

    Cu alte cuvinte, pentru un $N$ dat (marginit superior de numarul de evenimente), daca $w_0$ e mai mic decit $c_1$, nicio alegere de bini nu poate fi o solutie.

    Problema nu e bine formulata. Lipsesc conditii suplimentare care sa asigure existenta unei solutii.

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top