Uczenie maszynowe i sztuczne sieci neuronowe/Wykład 9

Maszyny Wektorów Wspierających 2

SVM w formaliźmie Lagranga

W ostatnim wykładzie doszliśmy do tego, że problem znalezienia klasyfikatora optymalnego pod względem marginesów można wyrazić w następujący sposób:

[math]\begin{matrix} \min _{w,b} \frac{1}{2}||w||^{2}&\\ \text{pod warunkiem: } &y^{(j)}(w^{T}x^{(j)}+b) \ge 1, \quad j= 1, \dots ,m \end{matrix}[/math]

Można go przepisać w takiej postaci aby pasowała do formalizmu uogólnionej metody Lagrangea, którą omówiliśmy na poprzednim wykładzie:

[math]\begin{matrix} \min _{ w,b} \frac{1}{2}||w||^{2}&\\ \text{pod warunkiem: } &g_{j}(w,b) = 1 - y^{(j)}(w^{T}x^{(j)}+b) \le 0, \quad j= 1, \dots ,m \end{matrix}[/math]

[math]\begin{matrix} \end{matrix}[/math]

Każdy przykład z ciągu uczącego dodaje nam jeden wiąz [math]g_{j}[/math]. Do uogólnianego Lagrangianu warunki te wchodzą z wagami [math]\alpha _{j}[/math]. Można zauważyć na podstawie warunków KKT, że tylko te [math]\alpha _{j}[/math] są niezerowe (tak konkretnie to [math]\gt 0[/math]), dla których warunek jest spełniony z równością, tzn. [math]g_{j}(w) = 0[/math]. Są to punkty położone najbliżej hiperpowierzchni decyzyjnej. To właśnie te punkty nazywane są wektorami wspierającymi. Później okaże się, że fakt iż wektorów wspierających jest tak na prawdę mało jest bardzo użyteczny.

Lagrangian dla problemu SVM w postaci pierwotnej wygląda tak:

[math] \mathcal {L}(w,b,\alpha ) = \frac{1}{2}||w||^{2} - \sum _{j=1}^{m} \alpha _{j}\left[ y^{(j)}(w^{T}x^{(j)}+b) -1\right] [/math]

W Lagrangianie występują tylko mnożniki [math]\alpha [/math], ponieważ mamy więzy tylko w postaci nierówności.

Przejście do pstaci dualnej

Teraz zajmiemy się formułowaniem problemu optymalizacyjnego (%i 1) w postaci dualnej. Pozwoli nam to na rozwiązywanie problemów, które nie są separowalne liniowo. Najpierw uzyskajmy [math]\theta _{d}[/math]. Aby to uczynić musimy zminimalizować [math]\mathcal {L}[/math] po [math]w[/math] i [math]b[/math], trzymając [math]\alpha [/math] stałe. W tym celu policzymy pochodną [math]\mathcal {L}[/math] po [math]w[/math] i po [math]b[/math] i położymy je równe zero:

[math] \nabla _{w} \mathcal {L}(w,b,\alpha ) = w - \sum _{j=1}^{m}\alpha _{j}y^{(j)}x^{(j)} =0 [/math]

Stąd:

[math] w = \sum _{j=1}^{m}\alpha _{j}y^{(j)}x^{(j)} [/math]

Dla [math]b[/math] mamy:

[math] \frac{\partial }{\partial b} \mathcal {L}(w,b,\alpha ) = \sum _{j=1}^{m} \alpha _{j}y^{(j)} =0 [/math]

Jeśli teraz weźmiemy [math]w[/math] z (%i 4) i wstawimy do Lagrangianu (%i 3) to otrzymamy:

[math] \theta _{d}= \min _{w,b}\mathcal {L}(w,b,\alpha ) = \sum _{j=1}^{m}\alpha _{j} - \frac{1}{2}\sum _{i,j =1}^{m} y^{(i)}y^{(j)} \alpha _{i}\alpha _{j} (x^{(i)})^{T}x^{(j)} - b \sum _{j=1}^{m}\alpha _{j}y^{(j)} [/math]

Ale z równania (%i 5) wynika, że ostatni człon tego wyrażenia jest równy zero, więc mamy:

[math] \theta _{d}= \min _{w,b}\mathcal {L}(w,b,\alpha ) = \sum _{j=1}^{m}\alpha _{j} - \frac{1}{2}\sum _{i,j =1}^{m} y^{(i)}y^{(j)} \alpha _{i}\alpha _{j} (x^{(i)})^{T}x^{(j)} [/math]

Pojawiające się tu wyrażenie [math](x^{(i)})^{T}x^{(j)}[/math] to iloczyn skalarny wektorów [math]x^{(i)}[/math] oraz [math]x^{(j)}[/math], bedziemy je dalej zapisywać jako [math]\langle x^{(i)},x^{(j)}\rangle [/math]. Zatem nasz dualny problem optymalizacyjny można zapisać tak:

[math]\begin{matrix} \max _{\alpha } \theta _{d} &= &\sum _{j=1}^{m}\alpha _{j} - \frac{1}{2}\sum _{i,j =1}^{m} y^{(i)}y^{(j)} \alpha _{i}\alpha _{j} \langle x^{(i)}, x^{(j)}\rangle \\ \text{pod warunkiem: }&& \alpha _{j}\ge 0, \quad j=1,\dots ,m\\ && \sum _{j=1}^{m}\alpha _{j}y^{(j)} = 0 \end{matrix}[/math]

Spełnione są warunki KKT, zatem rozwiązanie tego problemu dualnego jest też rozwiązaniem naszego problemu pierwotnego.

Wyznaczenie parametrów modelu:

Zakładając, że mamy algorytm znajdujący [math]\alpha ^{*}[/math], które maksymalizują [math]\theta _{d}[/math] (będzie o nim w dalszej części tego wykładu) możemy podstawić to [math]\alpha ^{*}[/math] do równania (%i 4) i wyznaczyć [math]w^{*}[/math]:

[math] w^{*} = \sum _{j=1}^{m}\alpha _{j}^{*}y^{(j)}x^{(j)} [/math]

a następnie obliczyć optymalne [math]b[/math] ze wzoru:

[math] b^{*} = - \frac{\max _{j:y^{(j)} = -1}{w^{*}}^{T}x^{(j)} + \min _{j:y^{(j)} = 1}{w^{*}}^{T}x^{(j)} }{2} [/math]

Klasyfikacja:

Teraz chcąc przewidzieć jaką klasę przydzielić nowemu przypadkowi [math]x[/math] musielibyśmy policzyć [math]{w^{*}}^{T}x + b^{*}[/math] i jeśli otrzymamy wartość ujemną to klasyfikujemy [math]x[/math] jako typ [math]-1[/math] a w przeciwnym wypadku jako 1. Skorzystajmy w tych obliczeniach z równania (%i 4):

[math]\begin{matrix} {w^{*}}^{T}x + b^{*} &=& \left( \sum _{j=1}^{m} \alpha _{j}^{*}y^{(j)}x^{(j)}\right)^{T} x + b^{*} \\ &=&\sum _{j=1}^{m} \alpha _{j}^{*}y^{(j)} \langle x^{(j)}, x \rangle + b^{*} \end{matrix}[/math]

Zatem aby wykonać klasyfikację nowego przypadku [math]x[/math] musimy obliczyć jego iloczyn skalarny z wektorami wspierającymi ze zbioru uczącego (tymi, dla których [math]\alpha _{j}^{*} \gt 0[/math], dla pozostałych wektorów w zbiorze uczącym [math]\alpha _{j}^{*}=0[/math]), a tych jak już wcześniej wspominaliśmy jest zazwyczaj niewiele.

Samo obliczanie iloczynów skalarnych można przeprowadzić bardzo wydajnie stosując odpowiednie funkcje jądrowe.

Funkcje jądrowe

Mapowanie do przestrzeni wielowymiarowych

Nasze dotychczasowe algorytmy klasyfikacyjne, z wyjątkiem nieliniowych sieci wielowarstwowych, były ograniczone do rozwiązywania problemów separowalnych liniowo. Okazuje się jednak, że często można uczynić problem separowalnym liniowo poprzez przemapowanie oryginalnych danych wejściowych do jakiejś więcej wymiarowej przestrzeni. Dla przykładu rozważmy dwa zbiory punktów jednowymiarowych. Jeden zbiór skupiony jest wokół zera a drugi rozłożony równomiernie po lewej i prawej jego stronie. Przechodząc ze zmiennych [math]x[/math] do [math](x,x^{2})[/math] punkty stają się liniowo separowalne.

W ogólności wprowadzimy funkcję mapującą [math]\phi (x)[/math], która przenosi punkty z oryginalnej przestrzeni wejściowej do rozszerzonej przestrzeni cech. W powyższym przykładzie byłoby to:

[math] \phi (x) = \left[\begin{array}{c} x\\ x^{2} \end{array}\right] [/math]

Aby skorzystać z takiego mapowania wystarczy w naszych algorytmach uczących zamienić wszędzie [math]x[/math] na [math]\phi (x)[/math]. Podobnie możemy postąpić z algorytmem SVM. W postaci dualnej algorytm SVM jest wyrażony całkowicie przez iloczyny skalarne. Możemy zatem zastąpić wszystkie wyrażenia [math]\langle x, z \rangle [/math] przez [math]\langle \phi (x), \phi (z) \rangle [/math].

Sprytne liczenie iloczynów skalarnych

Dla danego mapowania [math]\phi [/math] zdefiniujemy jądro (kernel):

[math] K(x,z) = \phi (x)^{T}\phi (z) [/math]

wtedy wszędzie gdzie w algorytmie występuje [math]\langle x,z \rangle [/math] wstawiamy [math]K(x,z)[/math] i otrzymujemy algorytm działający w przestrzeni, do której mapuje [math]\phi [/math]. Co ciekawe okazuje się, że w wielu praktycznie interesujących przypadkach, aby obliczyć [math]K(x,z)[/math] nie musimy wcale przechodzić całej drogi: [math]x \rightarrow \phi (x) \rightarrow \langle \phi (x),\phi (z) \rangle [/math] (taka droga zresztą mogła by być niewykonalna, np. w przypadku mapowania do przestrzeni nieskończenie wymiarowej). Rozważmy przykład:

[math] K(x,z) = ( x^{T}z)^{2} [/math]

Rozpisując to wyrażenie na współrzędne otrzymujemy:

[math]\begin{matrix} K(x,z) &=& \left(\sum _{i=1}^{m}x_{i}z_{i} \right) \left(\sum _{j=1}^{m}x_{j}z_{j}\right)\\ &=& \sum _{i=1}^{m}\sum _{j=1}^{m} x_{i}x_{j}z_{i}z_{j}\\ &=& \sum _{i,j=1}^{m}(x_{i}x_{j})(z_{i}z_{j}) \end{matrix}[/math]

Widzimy tu, że jeśli popatrzeć na [math]K[/math] tak: [math]K(x,z) = \phi (x)^{T}\phi (z)[/math] to owo [math]K[/math] związane jest z mapowaniem [math]\phi [/math], które w jawnej postaci dla [math]m=3[/math] wyglądałoby tak:

[math] \phi (x) = \left[\begin{array}{c} x_{1}x_{1}\\ x_{1}x_{2}\\ x_{1}x_{3}\\ x_{2}x_{1}\\ x_{2}x_{2}\\ x_{2}x_{3}\\ x_{3}x_{1}\\ x_{3}x_{2}\\ x_{3}x_{3} \end{array}\right] [/math]

Zauważmy, że samo obliczenie mapowania w tym przypadku jest operacją o złożoności obliczeniowej [math]O(m^{2})[/math] natomiast obliczenie jądra za pomocą równia (%i 9) jest operacją o złożoności obliczeniowej [math]O(m)[/math].

Podobne własności ma jądro:

[math] K(x,z) = (x^{T}z + c)^{2} = \sum _{i,j=1}^{m} (x_{i}x_{j})(z_{i}z_{j}) + \sum _{i=1}^{m}(\sqrt{2c}x_{i} )(\sqrt{2c}z_{i}) +c^{2} [/math]

Jawna postać mapowania odpowiadającego temu jądru wygląda następująco (dla [math]m=3[/math]):

[math] \phi (x) = \left[\begin{array}{c} x_{1}x_{1}\\ x_{1}x_{2}\\ x_{1}x_{3}\\ x_{2}x_{1}\\ x_{2}x_{2}\\ x_{2}x_{3}\\ x_{3}x_{1}\\ x_{3}x_{2}\\ x_{3}x_{3} \\ \sqrt{2c}x_{1}\\ \sqrt{2c}x_{2}\\ \sqrt{2c}x_{3}\\ c \end{array}\right] [/math]

czyli zawiera zarówno wyrazy pierwszego rzędu ([math]x_{i}[/math]) oraz drugiego rzędu ([math]x_{i}x_{j}[/math]). Parametr [math]c[/math] kontroluje względny udział części liniowej.

W ogólności jądro postaci [math]K(x,z) = (x^{T}z + c)^{d}[/math] odpowiada mapowaniu do [math]\binom{n+d}{d}[/math] wymiarowej przestrzeni parametrów, której wymiary są rozpięte przez wszystkie iloczyny typu [math]x_{i_{1}},x_{i_{2}},\dots ,x_{i_{k}}[/math] aż do rzędu [math]d[/math]. Dzięki sztuczce z jądrem nigdy nie musimy jawnie obliczać tych wielowymiarowych wektorów i obliczenia nadal mają złożoność [math]O(m)[/math].

Twierdzenie Mercera

Na jądro możemy patrzeć jak na funkcję, która jest jakąś miarą podobieństwa pomiędzy wektorami cech. W szczególności gdyby nasze wektory cech były znormalizowane do jedynki to duża wartość jądra [math]K(x,z) = \phi (x)^{T}\phi (z)[/math] odpowiadałaby wektorom bardzo podobnym, zaś wartość jądra bliska zeru odpowiadałaby wektorom cech, które są do siebie prawie ortogonalne, tzn. mało podobne. Idąc tym tropem możemy zapostulować także inne funkcje jądra, które w jakimś sensie mogłyby stanowić miarę podobieństwa między wektorami. Popularną funkcją jest np. funkcja Gaussa, prowadząca do jądra Gaussowskiego następującej postaci:

[math] K(x,z) = \exp \left( - \frac{||x-z||^{2}}{2 \sigma ^{2}}\right) [/math]

Jak w ogólności sprawdzić czy wymyślona przez nas funkcja jest dobrym kandydatem na jądro? Rozważymy to najpierw na przykładzie a potem podamy ogólne twierdzenie. Załóżmy, że mamy pewną funkcję [math]K[/math], która jest jądrem pewnego mapowania [math]\phi [/math]. Załóżmy dalej, że mamy pewien zbiór [math]m[/math] punktów [math]\lbrace x^{(1)},\dots ,x^{(m)}\rbrace [/math]. Zdefiniujmy macierz [math]\mathbf {K}[/math] zwaną macierzą jądra w taki sposób, że jej [math]i,j[/math] element dany jest wzorem:

[math] \mathbf {K}_{i,j} = K(x^{(i)},x^{(j)}) [/math]

Zauważmy, że macierz ta musi być symetryczna, bo:

[math] \mathbf {K}_{i,j} = K(x^{(i)},x^{(j)}) =\phi (x^{(i)})^{T}\phi (x^{(j)}) = \phi (x^{(j)})^{T}\phi (x^{(i)}) = K(x^{(j)},x^{(i)}) = \mathbf {K}_{j,i} [/math]

Druga obserwacja jest następująca. Niech [math]\phi _{k}(x)[/math] oznacza [math]k[/math]-tą współrzędną wektora [math]\phi (x)[/math]. Wtedy dla dowolnego wektora [math]z[/math] mamy:

[math]\begin{matrix} z^{T}\mathbf {K}z &=& \sum _{i}\sum _{j} z_{i}\mathbf {K}_{i,j}z_{j} \\ &=& \sum _{i}\sum _{j} z_{i}\phi (x^{(i)})^{T}\phi (x^{(j)})z_{j} \\ &=& \sum _{i}\sum _{j} z_{i} \sum _{k} \phi _{k}(x^{(i)})\phi _{k}(x^{(j)})z_{j} \\ &=& \sum _{k}\sum _{i}\sum _{j} z_{i}\phi _{k}(x^{(i)})\phi _{k}(x^{(j)})z_{j} \\ &=& \sum _{k} \left( \sum _{i} z_{i} \phi _{k}(x^{(i)})\right)^{2} \\ &\ge & 0 \end{matrix}[/math]

Ponieważ powyższe obliczenie pokazuje, że dla dowolnego [math]z[/math] wyrażenie [math]z^{T}\mathbf {K}z[/math] jest nieujemne to oznacza, że macierz [math]\mathbf {K}[/math] jest dodatnio określona.

Pokazaliśmy w tym przykładzie, że jeśli mamy jakieś mapowanie [math]\phi [/math] i związane z nim jądro [math]K[/math] to macierz jądra jest symetryczna i dodatnio określona. Okazuje się, że jest to warunek konieczny i wystarczający, aby funkcja [math]K[/math] była jądrem, jest to twierdzenie Mercera.

Warto sobie uświadomić, że podejście "jądrowe" ma znacznie szersze zastosowanie niż tylko algorytm SVM. Jeśli tylko jesteśmy w stanie wyrazić algorytm w postaci bazującej na iloczynach skalarnych [math]\langle x,z \rangle [/math] (da się to w szczególności zrobić np. dla regresji logistycznej) to zamiana tych iloczynów na funkcje jądra daje nam algorytm działający efektywnie w przestrzeni, do której przenosi nas odwzorowanie [math]\phi [/math]. Dzięki temu można spowodować, że wiele problemów, które nie są separowalne liniowo w pierwotnej przestrzeni wejść staje się separowalna liniowo w tej nowej, więcej wymiarowej przestrzeni.

Regularyzcja i przypadki nieseparowalne liniowo

Zaprezentowana dotychczas wersja SVM zakładała, że dane są liniowo separowalne. Sztuczka z jądrem mapującym zwiększa co prawda szansę na otrzymanie problemu liniowo separowalnego, ale nie daje na to gwarancji. Co więcej w dotychczasowej wersji nasz algorytm SVM jest bardzo podatny na outliery, czyli przypadki odstające. (Pokażemy to na ćwiczeniach)

Aby poprawić oba te problemy można zastosować regularyzację:

[math]\begin{matrix} \min _{ w, b}&& \frac{1}{2}||w||^{2} + C\sum _{j=1}^{m}\xi _{j}\\ \text{pod warunkiem: }&& y^{(j)}(w^{T}x^{(j)} +b ) \ge 1- \xi _{j}, \quad j=1,\dots ,m\\ && \xi _{j} \ge 0, \quad j=1,\dots ,m \end{matrix}[/math]

Oznacza ona tyle, że zgadzamy się na to, że nie wszystkie marginesy funkcyjne są większe niż 1 (przypomnijmy, że ujemny margines funkcyjny odpowiadał złej klasyfikacji), ale karzemy algorytm za naruszanie tego warunku przez zwiększanie funkcji celu. Parametr [math]C[/math] kontroluje jak bardzo nie podoba nam się błędne klasyfikowanie przypadków.

Aby rozwiązać ten problem optymalizacyjny też posłużymy się mnożnikami Lagrangea. Formułujemy Lagrangian następującej postaci:

[math] \mathcal {L}(w,b,\xi ,\alpha ,r) = \frac{1}{2}w^{T}w + C\sum _{j=1}^{m}\xi _{j} - \sum _{j=1}^{m}\alpha _{j}[y^{(j)}(x^{T}w +b)-1 +\xi _{j}] - \sum _{j=1}^{m}r_{j}\xi _{j} [/math]

gdzie [math]\alpha _{j}\ge 0[/math] i [math]r_{j}\ge 0[/math] są mnożnikami Lagrangea. Przejście do postaci dualnej polega na policzeniu pochodnej Lagrangianu względem [math]w[/math] i [math]b[/math], przyrównaniu od zera i podstawieniu otrzymanych wyrażeń ponownie do Lagragianu (tak jak tu –tu link–) otrzymujemy problem dualny następującej postaci:

[math]\begin{matrix} \max _{\alpha } && \theta _{d}(\alpha ) = \sum _{j=1}^{m}\alpha _{j} - \frac{1}{2} \sum _{i,j =1}^{m} y^{(i)}y^{(j)}\alpha _{i}\alpha _{j} \langle x^{(i)},x^{(j)} \rangle \\ \text{pod warunkiem: } && 0 \le \alpha _{j} \le C, \quad j=1,\dots ,m\\ &&\sum _{j=1}^{m}\alpha _{j}y^{(j)} = 0 \end{matrix}[/math]

Do rozwiązania powyższego problemu dobrze stosuje się algorytm SMO (Sequential Minimal Optimization) [opis algorytmu zaproponowanego przez J. Platta (1998)]. Po wyznaczeniu za jego pomocą parametrów [math]\alpha [/math] i [math]b[/math] można wykonywać predykcję nowych przykładów zgodnie z równaniem (%i 8).

Algorytm SMO - sekwencyjnej minimalnej optymalizacji

Zanim przejdziemy do omówienia właściwego algorytmu SMO zrobimy dygresję na temat optymalizacji osiowej.

Optymalizacja osiowa

Załóżmy, że chcemy rozwiązać następujący problem optymalizacyjny bez więzów:

[math] \max _{\alpha } W (\alpha _{1},\dots ,\alpha _{m}) [/math]

Jeśli funkcja [math]W[/math] jest wypukła to algorytm, który w pętli kolejno optymalizuje jedno [math]\alpha _{i}[/math], trzymając w danym kroku optymalizacyjnym pozostałe alfy stałe, jest zbieżny. (na tablicy rysunek konturowy paraboloidy ze zbiegającym osiowo rozwiązaniem)

Algorytm SMO

Chcemy rozwiązać problem optymalizacyjny (%i 10). Nie da się do niego zastosować algorytmu optymalizacji osiowej bo drugi warunek narzuca więzy na [math]\alpha [/math]. Jeśli ustalimy [math]m-1[/math] wartości [math]\alpha _{j}[/math] to ostatnia [math]m[/math]-ta wartość też już jest ustalona:

[math] \alpha _{i}y^{(i)} = -\sum _{j \ne i} \alpha _{j}y^{(j)} [/math]

Lub korzystając z faktu, że [math]y^{(i)} = \lbrace -1,1\rbrace [/math] i mnożąc stronami przez [math]y^{(i)}[/math] mamy: [math]\alpha _{i}= -y^{(i)} \sum _{j \ne i} \alpha _{j}y^{(j)}[/math].

Zatem najmniejszy możliwy problem optymalizacyjny wymaga jednoczesnej optymalizacji dwóch parametrów [math]\alpha [/math]. Najogólniej algorytm SMO wygląda więc następująco:

Powtarzaj, aż zbiegniesz:

1. Wybierz parę [math]\alpha _{i}[/math] i [math]\alpha _{j}[/math] do optymalizacji (na podstawie heurystyki szacującej która para da największe zbliżenie do maksimum).
2. Popraw [math]\theta _{d}(\alpha )[/math] biorąc pod uwagę [math]\alpha _{i}[/math] i [math]\alpha _{j}[/math] trzymając pozostałe alfy stałe.

Testem na zbieżność są tu warunki KKT, które powinny zostać spełnione z zadaną tolerancją.

Rozważmy krok 2. powyższego algorytmu. Załóżmy, że chcemy wykonać maksymalizację ze względu na parametry [math]\alpha _{1}[/math] i [math]\alpha _{2}[/math] trzymając pozostałe parametry [math]\alpha _{3}, \dots ,\alpha _{m}[/math] stałe. Z drugiego warunku mamy:

[math] \alpha _{1}y^{(1)}+ \alpha _{2}y^{(2)} = - \sum _{i=3}^{m} \alpha _{i} y^{(i)} = \zeta [/math]

gdzie [math]\zeta [/math] jest stałą. Oznacza to, że punkt [math](\alpha _{1},\alpha _{2})[/math] będący rozwiązaniem musi leżeć na prostej [math]\alpha _{1}y^{(1)}+ \alpha _{2}y^{(2)} =\zeta [/math].

(rysunek na tablicy: prosta przecinająca kwadrat [0,C]x[0,C])

Przekształcając równanie (%i 11) mamy:

[math] \alpha _{1} = \frac{ \zeta -\alpha _{2}y^{(2)} }{ y^{(1)}} [/math]

Zatem funkcja celu może być zapisana jako:

[math] \theta _{d}(\alpha _{1},\alpha _{2},\alpha _{3},\dots ,\alpha _{m}) = \theta _{d}(\frac{\zeta - \alpha _{2}y^{(2)}}{y^{(1)}}, \alpha _{2},\alpha _{3},\dots ,\alpha _{m}) [/math]

Ponieważ trzymamy w tym kroku parametry [math]\alpha _{3}, \dots ,\alpha _{m}[/math] jato stałe to funkcja celu jest funkcją kwadratową parametru [math]\alpha _{2}[/math]. Można by ją zapisać w postaci

[math]\theta _{d}(\alpha _{2})=a\alpha _{2}^{2}+b\alpha _{2}+c[/math]

dla odpowiednio dobranych [math]a,b[/math] i [math]c[/math]. Łatwo można zmaksymalizować analitycznie funkcję [math]\theta _{d}(\alpha _{2})[/math] w przypadku swobodnym, a następnie przyciąć rozwiązanie do "pudełka" wynikającego z więzów.