Metody optymalizacji w uczeniu maszynowym (kurs wykładowy) / 2012

1. Materiał z MachineLearning. Kurs poświęcony jest klasycznym i nowoczesnym metodom rozwiązywania problemów...
2. Zadania praktyczne
3. Egzamin
4. Oceny
5. System klasy kursu
6. Program kursu
7. Zobacz także

Materiał z MachineLearning.

Kurs poświęcony jest klasycznym i nowoczesnym metodom rozwiązywania problemów ciągłej optymalizacji, a także specyfikom ich zastosowania w problemach optymalizacji wynikających z uczenia maszynowego. Główny nacisk w prezentacji kładzie się na praktyczne aspekty wdrażania i stosowania metod. Celem kursu jest rozwijanie umiejętności uczniów nie tylko w wyborze odpowiedniej metody dla ich zadania, ale także w rozwijaniu ich metody optymalizacji, która w pełni uwzględnia specyficzne cechy konkretnego zadania.

Kurs przeznaczony jest dla starszych studentów i studentów. Znajomość podstaw uczenia maszynowego jest mile widziana, ale nie jest konieczna - wszystkie niezbędne koncepcje są wprowadzane podczas wykładów.

Autor kursu: D.A. Kropotow . Pytania i komentarze dotyczące kursu, proszę opuścić zakładkę „dyskusja” na tej stronie lub wysłać list do [email protected] . W tytule listu dodaj [MOMO12].

Harmonogram na rok akademicki 2012

W semestrze zimowym 2012 r. Kurs specjalny jest czytany VMK w poniedziałki w aud. 506, zaczynając od 18-10.

Data Nazwa wykładu Materiały 10 września 2012 r. Wprowadzenie do kursu 17 września 2012 r. Nie było wykładów 24 września 2012 r. Metody minimalizacji jednowymiarowej Tekst (PDF, 185 KB) 1 października 2012 r. Podstawowe metody optymalizacji wielowymiarowej Tekst (PDF, 1,13 MB) 8 października 2012 Zaawansowane techniki optymalizacji wielowymiarowej Tekst (PDF, 667 KB) 15 października 2012 Metody optymalizacji wykorzystujące globalne najlepsze szacunki Tekst (PDF, 248 KB) 22 października 2012 Problemy z optymalizacją z ograniczeniami 29 października 2012 Metody punktów wewnętrznych Tekst (PDF, 241 KB) 5 listopada 2012 r. Nie było wykładów (święto państwowe) 12 listopada 2012 r. Przykłady zastosowania metod punktów wewnętrznych 19 listopada 2012 r. Metody optymalizacji dla rzadkich modeli liniowych i regresji Tekst (PDF, 229 KB) 26 listopada 2012 Metody cięcia płaszczyzn 3 grudnia 2012 Optymalizacja stochastyczna 10 grudnia 2012 r. Nie było wykładu 17 grudnia 2012 r. Egzamin Pytania do egzaminu (PDF, 99 KB)

Zadania praktyczne

Zadanie 1. Metody minimalizacji jednowymiarowej .

Zadanie 2. Wielowymiarowe metody minimalizacji regresji logistycznej .

Zadanie 3. Metody punktowe dla regresji liniowej .

Egzamin

Egzamin odbędzie się 17 grudnia w aud. 506, zaczynając od 16-20. Tylko uczniowie, którzy ukończyli przynajmniej jedno zadanie praktyczne, mogą przystąpić do egzaminu. Na egzaminie podczas przygotowania wolno używać dowolnych materiałów.

Pytania do egzaminu + minimum teoretyczne (PDF, 99 KB)

Oceny

Grupa studentów Zadanie 1 Zadanie 2 Zadanie 3 Egzamin Razem Sokursky 317 - Chistyakova 422 4.0 5 5 Artyukhin 517 4.9 Elshin 517 - Zimovnov 517 5,0 4,3 4,3 5 Kirillov 517 4,0 Nekrasov 517 3,8 3 3 Novikov P. 517 3,8 4 4 Sokolov 517 5,0 4,8 4,4 5 Figurnov 517 - Saiko mech-mate 3.6

System klasy kursu

Kurs obejmuje trzy zadania praktyczne i egzamin. Każde zadanie i egzamin są oceniane w pięciopunktowej skali. Końcowa ocena z kursu jest uzyskiwana poprzez ważone sumowanie ocen za zadania i egzamin, z dalszym zaokrągleniem w kierunku najbliższej liczby całkowitej. Waga każdego zadania wynosi 1/3. Tak więc, jeśli student pomyślnie ukończył wszystkie trzy zadania praktyczne, otrzyma ocenę za kurs bez egzaminu. Co najmniej student musi wykonać jedno praktyczne zadanie. W tym przypadku zdaje egzamin, którego ocena przechodzi do ostatecznej kwoty z wagą 2/3. Jeśli uczeń ukończył dwa praktyczne zadania, zdaje egzamin, ale w lekkim programie (mniej pytań w bilecie, mniej dodatkowych pytań). W takim przypadku ocena egzaminu jest w ostatecznej kwocie z wagą 1/3. Za każdy dzień zwłoki w wykonaniu zadania naliczana jest kara w wysokości 0,1 punktu, ale nie więcej niż 2 punkty.

Program kursu

Podstawowe pojęcia i przykłady zadań

• Funkcje gradientowe i heskie kilku zmiennych, ich właściwości, warunki konieczne i wystarczające dla ekstremum bezwarunkowego;
• Obliczenia macierzowe, przykłady;
• Rozszerzenia macierzy, ich wykorzystanie do rozwiązywania SLAE;
• Struktura iteracyjnego procesu w optymalizacji, pojęcie wyroczni;
• Przykłady wyroczni i zadań uczenia maszynowego z „złożoną” optymalizacją.

Techniki optymalizacji jednozmiennej

Wielowymiarowe metody optymalizacji

• Metoda spadku współrzędnych;
• Metody gradientu zniżania: najszybsze zejście, zejście z niedokładną jednowymiarową optymalizacją, zależność od skali pomiarów znaków;
• Metoda Newtona, wybór długości kroku;
• Wyniki teoretyczne dotyczące tempa zbieżności gradientu zniżania i metody Newtona;
• Fazy ​​procesu iteracyjnego, dekompozycja LDL, metoda hybrydowa Newtona;
• Metoda Levenberga-Marquardta, jej zastosowanie do treningu regresji nieliniowej;
• Metoda gradientu sprzężonego do rozwiązywania układów równań liniowych;
• Metoda gradientu sprzężonego do optymalizacji funkcji nie kwadratowych, zależność od dokładnej optymalizacji jednowymiarowej;
• Metody optymalizacji quasi-Newtona: DFP, BFGS i L-BFGS;
• Relacje między różnymi metodami rozwiązywania SLAE.

Metody optymalizacji wykorzystujące globalne górne granice zależne od parametrów

• Probabilistyczny model regresji liniowej z różnymi regularyzacjami: kwadratowy, L1, Student;
• Idea metody optymalizacji opartej na wykorzystaniu szacunków globalnych, zbieżności;
• Przykład wykorzystania metody uczenia się LASSO;
• Konstrukcja globalnych oszacowań z wykorzystaniem nierówności Jensena, algorytmu EM, jego zastosowanie do probabilistycznych modeli regresji liniowej;
• Budowanie szacunków za pomocą stycznych i zmiennych zmiennych;
• Oszacowanie Jakkoli-Jordana dla funkcji logistycznej, oszacowania rozkładu Laplace'a i Studenta;
• Zastosowanie szacunków do trenowania probabilistycznych modeli regresji liniowej;
• Procedura wypukła-wklęsła, przykłady użycia.

Problemy optymalizacyjne z ograniczeniami, koncepcja dualności

• Normy wektorowe i macierzowe, przykłady, podwójna norma;
• Wypukłe zestawy i funkcje, sprzężenie funkcji Fenchela, pojęcie dualizmu;
• Podwójna funkcja Lagrange'a, jej stosunek do sprzężonej funkcji Fenchela, problem podwójnej optymalizacji;
• Geometryczna interpretacja dualności;
• Konieczne i wystarczające warunki optymalności w problemach optymalizacji warunkowej, twierdzenie Kuhna-Tuckera;
• Problem optymalizacji zaburzonej, znaczenie ekonomiczne współczynników Lagrange'a.

Metody punktowe

• Warunki Kuhna-Tuckera dla problemów optymalizacji wypukłej, ogólna struktura metod optymalizacji bezpośredniego podwójnego;
• Rozwiązywanie problemów optymalizacji warunkowej z liniowymi ograniczeniami typu równości, metoda Newtona;
• Metoda dualna Newtona;
• Metoda logarytmicznych funkcji barierowych, wyszukiwanie prawidłowego punktu początkowego;
• Metoda wewnętrznego punktu prostego;
• Używanie metod wewnętrznych do nauki SVM.

Rzadkie metody uczenia maszynowego

• Modele regresji liniowej / logistycznej z regulacją L1 i L1 / L2;
• Pojęcie subgradientu funkcji wypukłej, warunek konieczny i wystarczający dla ekstremum dla wypukłych, niezagładzonych problemów bezwarunkowej optymalizacji, przykłady;
• Metoda proksymalna;
• Metoda zstępowania współrzędnych i optymalizacji współrzędnych bloku;
• Metoda aktywnego zestawu na przykładzie regresji najmniejszych kątów.

Metody płaszczyzny cięcia

• Koncepcja separacji wyroczni, podstawowa metoda cięcia płaszczyzn (płaszczyzna cięcia);
• Supergraficzna forma metody cięcia płaszczyzn;
• Wersja pakietu metody cięcia płaszczyzn, zależność od regulowanych parametrów;
• Używanie metody pakietu dla zadania uczenia SVM;
• Dodanie skutecznej procedury wyszukiwania jednowymiarowego;
• Implementacja metody z wykorzystaniem obliczeń równoległych i warunków ograniczeń pamięci.

Optymalizacja stochastyczna

• Ogólne sformułowanie problemu optymalizacji stochastycznej, przykład użycia;
• Zadania minimalizacji średniego i empirycznego ryzyka;
• Metoda stochastycznego spadku gradientu, jego różnice w stosunku do metody gradientu zniżania;
• Stochastyczne zejście gradientowe jako metoda optymalizacji i jako metoda treningowa;
• Wykorzystanie gradientu stochastycznego dla SVM (algorytm PEGASOS);
• Modele auto-kodera i głębokiego auto-kodera, cechy procedury treningowej i zastosowanie stochastycznego zejścia gradientowego.

Literatura

1. Optymalizacja uczenia maszynowego . Pod redakcją Suvrit Sra, Sebastian Nowozin i Stephen J. Wright, MIT Press, 2011.
2. S. Boyd, L. Vandenberghe. Optymalizacja wypukła , Cambridge University Press, 2004.
3. A. Antoniou, W.-S. Lu. Optymalizacja praktyczna: algorytmy i aplikacje inżynierskie , Springer, 2007.
4. B. Polyak. Wprowadzenie do optymalizacji , Science, 1983.
5. Y. Nesterov. Metody optymalizacji wypukłej , ICMNO, 2010.
6. R. Fletcher. Praktyczne metody optymalizacji , Wiley, 2000.
7. Przepisy numeryczne. Sztuka obliczeń naukowych 1992

Zobacz także

Kurs „Modele graficzne”

Kurs „Bayesowskie metody uczenia maszynowego”

Specjalne warsztaty „Bayesowskie metody uczenia maszynowego”

Matematyczne metody prognozowania (Wydział Moskiewskiego Uniwersytetu Państwowego, Moskiewski Uniwersytet Państwowy)