Świetne algorytmy, uczenie maszynowe i brak algebry liniowej

30

Prowadzę kurs zaawansowanych algorytmów i chciałbym uwzględnić niektóre tematy związane z uczeniem maszynowym, które zainteresują moich studentów. W związku z tym chciałbym usłyszeć opinie ludzi na temat najbardziej interesujących / największych wyników algorytmicznych w uczeniu maszynowym. Potencjalnie trudnym ograniczeniem jest to, że uczniowie nie będą mieli żadnej konkretnej wcześniejszej wiedzy na temat algebry liniowej ani innych głównych tematów uczenia maszynowego.

To naprawdę ekscytuje ich tematem i informuje, że ML jest potencjalnie ekscytującym obszarem badań dla ekspertów w dziedzinie algorytmów.

EDYCJA: To jest ostatni rok studiów licencjackich (ponieważ nie mamy kursów magisterskich w Wielkiej Brytanii). Zrobili wcześniej co najmniej jeden podstawowy kurs algorytmów i prawdopodobnie dobrze w nim wybrali, aby wybrać zaawansowany kurs kontrolny. Aktualny program zaawansowanego kursu obejmuje takie tematy, jak haszowanie idealne, filtry Blooma, drzewa van Emde Boasa, program liniowy, ok. algorytmy dla problemów NP-trudnych itp. Nie zamierzam spędzać więcej niż jednego wykładu wyłącznie na ML, ale jeśli coś jest naprawdę istotne zarówno dla kursu algorytmów, jak i ML, to oczywiście można je również uwzględnić.

Raphael
źródło
1
Proszę wyjaśnić dwie rzeczy: 1) Czy jest to kurs licencjacki lub magisterski? Jakie kursy powiązane (jeśli w ogóle) zdali? 2) Ile czasu chcesz poświęcić ML?
MS Dousti,
3
hmmm Myślę, że algebra liniowa jest koniecznością i ważnym kursem podstawowym, przynajmniej w zakresie uczenia maszynowego. i myślę, że model liniowy jest bardzo dobrym wprowadzeniem do algorytmów uczenia maszynowego. możesz pomyśleć o innych podstawowych algorytmach poziomu, takich jak najbliższy sąsiad K lub algorytmy regresji logistycznej. może to ci pomóc en.wikipedia.org/wiki/List_of_machine_learning_algorithms
Deyaa
1
Być może kilka pomysłów z tego, jak Hal Daume uczy uczenia maszynowego - nlpers.blogspot.com/2010/04/how-i-teach-machine-learning.html
Jarosław
3
Drogi Rafale, Avrim Blum zazwyczaj kończy swoją klasę algorytmów na poziomie wyższym uczeniem maszynowym i kilkoma pokrewnymi tematami; ostatnia iteracja znajduje się pod następującym linkiem cs.cmu.edu/~avrim/451f09/index.html , a więcej informacji można uzyskać z jego strony internetowej. Biorąc zarówno TA, jak i tę klasę, mogę powiedzieć, że (i materiał końcowy) są bardzo ciepło przyjmowane przez studentów.
matus
1
patrz np algorytmy genetyczne lub też głęboką naukę
vzn

Odpowiedzi:

29

Możesz pokryć wzmocnienie . Jest bardzo sprytny, łatwy do wdrożenia, jest szeroko stosowany w praktyce i nie wymaga dużej wiedzy wstępnej do zrozumienia.

Lew Reyzin
źródło
5
Przedstawiłem niektóre części ankiety przeprowadzonej przez Arora i in. ( cs.princeton.edu/~arora/pubs/MWsurvey.pdf ) w klasie teorii gradów kilka lat temu. Wydawało się, że ludziom się to podoba i myślę, że nie potrzebujesz prawie żadnego tła, aby zrozumieć ten materiał.
Danu,
9

Jeśli chcesz tylko zwiększyć ich apetyt w jednym wykładzie, najbardziej ekscytujące może być zaprezentowanie potężnej aplikacji. Na przykład maszyny wektorów pomocniczych i inne algorytmy uczenia maszynowego są wykorzystywane w chemoinformatyce do odkrywania leków.

Problem uczenia się zasadniczo polega na tym: biorąc pod uwagę zachowanie, które chcemy, aby substancja chemiczna wykazywała, opracuj strukturę, która wykazuje to zachowanie, dedukując ją z bazy danych znanych struktur, które wykazują podobne (lub niepodobne) zachowania. Problem uczenia się ma dodatkowe zmarszczki: nowy lek musi być „odległy” w globalnej strukturze od znanych wcześniej leków, aby założyć patent.

Jednym ze źródeł są metody grupowania i ich zastosowania w chemii obliczeniowej .

Aaron Sterling
źródło
1
Dzięki za referencje. Myślałem o nauczeniu SVM jako aplikacji optymalizacji wypukłej. To ładnie powiązałoby część algorytmów z częścią ML.
Raphael,
2
jak objąć SVM bez algebry liniowej?
Lew Reyzin
Miałem nadzieję, że nauczę ich minimalnych wymagań w tym zakresie. Może to było zbyt optymistyczne :-)
Raphael
Czy wciąż istnieją ważne przykłady, w których najlepszym wyborem są maszyny wektorów wspierających? Zauważam, że na przykład w zawodach kaggle nigdy nie są one główną częścią zwycięskiego zgłoszenia. Przynajmniej nie które ostatnio widziałem. (Oczywiście zamierzam zostać poprawiony.)
Lembik
7

Środki K i KNN są bardzo potężne i nie wymagają żadnej algebry liniowej, z wyjątkiem obliczania odległości punktów.


źródło
Szczególnie K-Means jest bardzo silnym algorytmem. Jest niewiarygodnie skuteczny, mimo że nie udowodniono ograniczeń w zakresie jego funkcji celu, w tak strasznym stopniu, że jest prawie jak efektywna złożoność wielomianowa algorytmu Simplex (pomimo rzeczywistej złożoności wykładniczej). Jego wersja online jest również przydatna w aplikacjach danych na dużą skalę.
Elliot JJ
5

Druga część „Sieci neuronowych i uczenia maszynowego” Christophera Bishopa (w MSR) dotyczy algorytmów w ML. Podręczniki biskupa są powszechnie używane do podręczników dla absolwentów (a później studentów) i są wyjątkowo dobrze napisane.

Christina Boucher
źródło
4

Ten algorytm wykorzystuje minimalne cięcia na wykresie, aby sklasyfikować dużą liczbę próbek nieznakowanych przy użyciu tylko niewielkiej ilości próbek oznakowanych.

Jest przyjazny dla studentów. Wyjaśniłem to kilku losowo wybranym studentom i oni to zrozumieli.

Patrz: Blum, A. i Chawla, S. (2001). Uczenie się na podstawie danych oznaczonych i nieznakowanych przy użyciu skrótów grafowych.

Autopromocja Wizualizacja algorytmu na youtube .

Pratik Deoghare
źródło
1

Algorytmy uczenia się przez zbrojenie (szczególnie Q-Learning i SARSA) są dość proste do zrozumienia i bardzo skuteczne w rozwiązywaniu niektórych problemów uczenia się. Nie wymagają żadnej zaawansowanej wiedzy z zakresu algebry liniowej, z wyjątkiem dowodu zbieżności i współczynnika zbieżności.

Możesz skorzystać ze znanej ankiety Littmana i in .: http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/rl-survey.html

Lamine
źródło
1

Możesz omówić niektóre algorytmy, które są klasyczne lub mają dobrą intuicję.

Na przykład C4.5 i CART, które są klasycznymi algorytmami drzewa decyzyjnego.

Możesz także omówić niektóre metody zespołowe (np. AdaBoost (Boosting), Bagging), które mają bardzo dobrą wydajność w rzeczywistych zastosowaniach.

Ponadto głębokie uczenie się jest również dobrym tematem, ponieważ jest bardzo gorące.

strumień
źródło
0

Natywne bayes i sieć bayesowska, algorytmy drzewa decyzyjnego są dość łatwe do wizualizacji niż rozpoczynanie od neutralnej sieci lub svm

Prabu
źródło
0

Programowanie genetyczne jest naprawdę fajne. Wykorzystuje inspirację z biologii i można go zastosować do wielu problemów (na przykład problemu n-królowych i TSP).

Nie wymaga głębokich umiejętności matematycznych.

EDYCJA: Wymaga tylko sposobu oszacowania, jak dobre jest potencjalne rozwiązanie. Można go na przykład użyć do odgadnięcia reguły za szeregiem liczb, znajdowania minimów / maksimów w przypadku problemów z wieloma odmianami i wyszukiwania ogromnych przestrzeni parametrów. Jest odpowiedni, gdy nie interesuje Cię optymalne rozwiązanie, ale gdy wystarczy dobre rozwiązanie. Uważam, że wykorzystano to do znalezienia dobrych strategii do gier (budowanie zamówień w Starcraft 2 i optymalna gra w Mario).

Per Alexandersson
źródło
Czy jest jakiś ważny problem, dla którego jest to najlepsza metoda? Mam na myśli, że na pewno nie dotyczy to na przykład TSP.
Lembik