POLSKI SPOJ

Dany jest zbiór n punktów płaszczyzny

d=((x₁,y₁),..., (x_n,y_n ))

Poszczególne punkty są od siebie wzajemnie niezależne i mają rozkład, będący mieszaniną K rozkładów normalnych, tj. mają rozkład zadany przez gęstość

p(x,y)= w₁ p₁(x,y)+ ... + w_K p_K(x,y),

gdzie w₁+...+w_K=1 oraz

p_j (x,y)= 1/(2 s_xjs_yj) exp{ -[(x-m_xj )/s_xj ]²/2 -[(y-m_yj )/s_yj ]²/2 }.

Parametry w_j, m_xj, m_yj oraz s_xj, s_yj są nieznane. Zadanie polega na dobraniu tych parametrów metodą EM (Expectation-Maximization), tak aby wartość funkcji

L(d)= -ln(p(x₁,y₁)) - ... -ln(p(x_n,y_n))

była możliwie jak najmniejsza.

Wejście

W pierwszym wierszu podana jest wartość K oraz n oddzielone spacją.

W kolejnych n wierszach podane są kolejne wartości x_i, y_i oddzielone spacją.

Uwaga: W pierwszych dwóch zestawach K=1, czyli problem sprowadza się do metody ML.

Wyjście

W pierwszym wierszu należy podać otrzymaną wartość L(d). W następnych K wierszach należy wypisać kolejne wartości w_j, m_xj, s_xj, m_yj, s_yj oddzielone spacjami.

Liczby w_j muszą się sumować do jedności oraz żadna z liczb s_xj, s_yj nie może być mniejsza od 10^-15

Każdy z 10 testów ma indywidualny próg na wartość L(d), powyżej którego test nie jest zaliczany. Osoba, która rozwiąże wszystkie testy i otrzyma najmniejszą sumę L(d) otrzyma dodatkowe 5% (razem 10%).

Przykład 1

Wejście
2 10
5 5.5
5.5 4.5
5 4.5
4.5 5
4.9 5.1
4.7 4.9
-2 -2
-2 -2.1
-2.1 -1.9
-1.9 -2


Wyjście
0.545208
0.4 -2 0.0707107 -2 0.0707107
0.6 4.93333 0.309121 4.91667 0.348409

Przykład 2

Na poniższym wykresie punkty są zaznaczone przez '+', zaś rozwiązanie jest zaznaczone w ten sposób, że średnie poszczególnych składowych leżą w środkach elips, zaś elipsy mają promienie s_xj, s_yj oraz 2s_xj, 2s_yj.

A po co to komu?

Opisany problem może być wykorzystywane w grupowaniu danych (clustering). Mamy punkty na płaszczyźnie i chcemy podzielić je automatycznie na K grup. Mając wyznaczone współczynniki mieszaniny rozkładów normalnych, możemy dla każdego punktu (x_i,y_i ) wyznaczyć prawdopodobieństwa przynależności tego punktu do j-tej składowej, czyli

w_jp_j (x_i, y_i) / p (x_i, y_i)

W ten sposób otrzymujemy rozmyte grupowanie danych.

Odnośniki

1. Wykład o metodzie ML
2. Wykład z modelowania internetu, str. 24-28.
3. Applet dla problemu Mixture of Gaussians w nieco bardziej skomplikowanej formie.
4. Wikipedia.
5. Google.