Wydział Informatyki - Informatyka (N2)
specjalność: grafika komputerowa i systemy multimedialne
Sylabus przedmiotu Metody rozpoznawania wzorców:
Informacje podstawowe
| Kierunek studiów | Informatyka | ||
|---|---|---|---|
| Forma studiów | studia niestacjonarne | Poziom | drugiego stopnia |
| Tytuł zawodowy absolwenta | magister | ||
| Obszary studiów | nauki techniczne | ||
| Profil | ogólnoakademicki | ||
| Moduł | — | ||
| Przedmiot | Metody rozpoznawania wzorców | ||
| Specjalność | inteligentne aplikacje komputerowe | ||
| Jednostka prowadząca | Katedra Metod Sztucznej Inteligencji i Matematyki Stosowanej | ||
| Nauczyciel odpowiedzialny | Marcin Korzeń <Marcin.Korzen@zut.edu.pl> | ||
| Inni nauczyciele | Przemysław Klęsk <pklesk@wi.zut.edu.pl>, Marcin Korzeń <Marcin.Korzen@zut.edu.pl> | ||
| ECTS (planowane) | 2,0 | ECTS (formy) | 2,0 |
| Forma zaliczenia | egzamin | Język | polski |
| Blok obieralny | — | Grupa obieralna | — |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | matematyka |
| W-2 | rachunek prawdopodobieństwa i statystyka |
| W-3 | metody optymalizacji |
| W-4 | podstawy programowania |
| W-5 | wstęp do sztucznej inteligencji |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Ukształtowanie rozumienia matematycznych elementów teorii uczenia dla zadania rozpoznawania wzorców, ze szczególnym naciskiem na własność zdolności do uogólniania. |
| C-2 | Przedstawienie różnych odmian algorytmu SVM i wyjaśnienie jego związków ze zdolnością do uogólaniania. |
| C-3 | Przedstawienie problemu rozpoznawania wzorców zależnych od czasu oraz możliwych praktycznych zastosowań (rozpoznawanie dokumentów tekstowych, pisma, głosu, sekwencji video). Przedstawienie algorytmów z dziedziny HMM. |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| laboratoria | ||
| T-L-1 | Metoda SVM, własna implementacja wykorzystująca funkcję quadprog, przekształcenia jądrowe | 2 |
| T-L-2 | Metoda SVM biblioteki: LibSVM i LibLINEAR, wykorzystanie w programie Matalb | 2 |
| T-L-3 | Analiza danych mikromacierzowych oraz danych tekstowych, sprawozdanie | 2 |
| T-L-4 | Ukryte łańcuch markowa, algorytmy Bauma-Welcha oraz Viterbiego, własna implementacja | 2 |
| T-L-5 | Zastosowanie ukrytych łańcuchów Markowa do rozpoznawania autorstwa | 2 |
| 10 | ||
| wykłady | ||
| T-W-1 | Matematyczne postawienie zadania rozpoznawania wzorców (klasyfikacji) w terminach statystycznej teorii uczenia. Pojęcia: maszyna ucząca się, zbiór funkcji aproksymujących, zbiór funkcji błędu, błąd prawdziwy (zdolność do uogólniania), błąd na próbie, zbieżność jednostajna reguły ERM. Model PAC. | 2 |
| T-W-2 | Ograniczenia na błąd prawdziwy i zaawansowane pojęcia w ramach teorii uczenia: shattering, wymiar Vapnika-Chervonenkisa, nierówność Chernoffa (Hoeffdinga), złożoność próbkowa, pokrycia i liczby pokryciowe, złożoność Rademachera. | 2 |
| T-W-3 | Algorytm Support Vector Machines. Margines separacji. Różne warianty kryterium optymalizacyjnego SVM: z/bez mnożników Lagrange'a, 'soft-margin'. Przekształcenie jądrowe. | 3 |
| T-W-4 | Rozpoznawanie wzorców przebiegających w czasie (temporal pattern recognition). Ukryte Modele Markowa (Hidden Markov Models). Pojęcia: proces stochastyczny, łańcuch stochastyczny, łańcuch stacjonarny, łańcuch markowowski. Przypadkowe błądzenie (problem przejść przez zero). Algorytmy: Forward-Backward, Viterbi'ego, Bauma-Welcha. | 3 |
| 10 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| laboratoria | ||
| A-L-1 | Uczestnictwo w zajęciach | 10 |
| A-L-2 | Przygotowanie do zajęć | 8 |
| A-L-3 | Samodzielna praca nad zadaniami programistycznymi i sprawozdaniami | 10 |
| 28 | ||
| wykłady | ||
| A-W-1 | Samodzielne studiowanie matematycznych aspektów teorii uczenia. Łączenie nierówności probabilistycznych. Analiza wyprowadzeń ograniczeń na błąd prawdziwy. | 4 |
| A-W-2 | Analiza pojęcia shattering i przykładów wymiarów VC dla niektórych maszyn uczących się. | 2 |
| A-W-3 | SVM - formułowanie i rozwiązywanie przy pomocy komputera (MATLAB, Mathematica) różnych wersji kryterium optymalizacyjnego dla algorytmu SVM. Wyliczanie marginesu separacji. Dobieranie parametru 'soft-margin'. | 4 |
| A-W-4 | "Ręczne" (pisemne) śledzenie działania poszczególnych algorytmów w ramamach HMM na małych przykładach. | 4 |
| A-W-5 | Przygotowanie się do kolokwium egzaminacyjnego. | 8 |
| A-W-6 | Uczestnictwo w wykładach | 10 |
| 32 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | wykład informacyjny |
| M-2 | wykład problemowy |
| M-3 | metody programowane z użyciem komputera |
Sposoby oceny
| KOD | Sposób oceny |
|---|---|
| S-1 | Ocena podsumowująca: Pisemne kolokwium egzaminacyjne. |
| S-2 | Ocena formująca: oceny czastkowe z zadan programistycznych oraz sprawozdan |
| S-3 | Ocena podsumowująca: Ocena koncowa z laboratorium - srednia z ocen czastkowych (wazona stopniem trudnosci i zlozonosci zadania) |
Zamierzone efekty kształcenia - wiedza
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_2A_D19/6_W01 Rozumie zadania pattern recognition oraz temporal pattern recognition. | I_2A_W01, I_2A_W08 | — | C-1 | T-W-2, T-W-1 | M-1, M-2 | S-1 |
| I_2A_D19/6_W02 Ma znajomość matematycznych aspektów i rezultatów z zakresu statystycznej teorii uczenia. | I_2A_W01, I_2A_W08 | — | C-1 | T-W-2, T-W-1 | M-1, M-2 | S-1 |
| I_2A_D19/6_W03 Zna algorytm SVM wraz z różnymi jego wariantami. | I_2A_W01, I_2A_W05, I_2A_W08 | — | C-2 | T-W-3 | M-1, M-3, M-2 | S-1, S-2 |
| I_2A_D19/6_W04 Zna algorytmy z zakresu Ukrytych Modeli Markowa (HMM). | I_2A_W01, I_2A_W05, I_2A_W08 | — | C-3 | T-W-4 | M-1, M-3, M-2 | S-1, S-2 |
| I_2A_D19/6_W05 Rozumie sens zadania pattern recognition oraz temporal pattern recognition. Ma znajomość matematycznych aspektów i rezultatów z zakresu statystycznej teorii uczenia. | I_2A_W01, I_2A_W08 | — | C-1 | T-W-2, T-W-1 | M-1, M-2 | S-1, S-2 |
Zamierzone efekty kształcenia - umiejętności
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_2A_D19/6_U01 Potrafi stosować różne odmiany algorytmu SVM. | I_2A_U05, I_2A_U07, I_2A_U09, I_2A_U10 | — | C-2 | T-W-3 | M-1, M-3, M-2 | S-1, S-2 |
| I_2A_D19/6_U02 Potrafi budować modele markowowskie (i stosować algorytmy z zakresu HMM) do rozpoznawania danych ze zmiennością w czasie. | I_2A_U05, I_2A_U07, I_2A_U09, I_2A_U10 | — | C-3 | T-W-4 | M-1, M-3, M-2 | S-1, S-2 |
Zamierzone efekty kształcenia - inne kompetencje społeczne i personalne
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_2A_D19/6_K01 Ma wysoką świadomość ważnych elementów teoretycznych i praktycznych dotyczących analizy danych i rozpoznawania wzorców. | I_2A_K02, I_2A_K03 | — | C-3, C-1, C-2 | T-W-2, T-W-4, T-W-3, T-W-1 | M-1, M-3, M-2 | S-1, S-2, S-3 |
Kryterium oceny - wiedza
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D19/6_W01 Rozumie zadania pattern recognition oraz temporal pattern recognition. | 2,0 | |
| 3,0 | Umie sformułować zadanie rozpoznawania wzorców, zna podstawowe metody ekstrakcji cech | |
| 3,5 | ||
| 4,0 | ||
| 4,5 | ||
| 5,0 | ||
| I_2A_D19/6_W02 Ma znajomość matematycznych aspektów i rezultatów z zakresu statystycznej teorii uczenia. | 2,0 | |
| 3,0 | zna podstawowe definicje i rezultaty z zakresu statystycznej teorii uczenia, rozróżnia pojęcie ryzyka proawdziwego od błędu na próbie uczącej | |
| 3,5 | ||
| 4,0 | ||
| 4,5 | ||
| 5,0 | ||
| I_2A_D19/6_W03 Zna algorytm SVM wraz z różnymi jego wariantami. | 2,0 | Nie zna podstawowych własności algorytmu SVM. |
| 3,0 | Zna podstawowe własności algorytmu SVM. | |
| 3,5 | Rozumie pojęcie marginesu separacji. | |
| 4,0 | Potrafi zapisać podstawowe kryterium optymalizacji dla algorytmu SVM (hard-margin). | |
| 4,5 | Potrafi zapisać podstawowe kryterium optymalizacji dla algorytmu SVM (hard-margin) w wariancie z mnożnikami Lagrange'a. | |
| 5,0 | Potrafi zapisać kryterium optymalizacji dla algorytmu SVM z miękkim marginesem (soft-margin) w wariancie z i bez mnożników Lagrange'a. | |
| I_2A_D19/6_W04 Zna algorytmy z zakresu Ukrytych Modeli Markowa (HMM). | 2,0 | Nie zna podstawowych pojęć dotyczących procesów losowych. |
| 3,0 | Zna podstawowe pojęcia dotyczące procesów losowych: proces, łańcuch, proces stacjonarny, łańcuch Markowa, ukryty łańcuch Markowa (HMM). | |
| 3,5 | Zna trzy podstawe problemy obliczeniowe stawiane w ramach HMM. | |
| 4,0 | Zna algorytm Forward-Backward. | |
| 4,5 | Zna algorytm Viterbi'ego wraz ze wstecznym śledzeniem ścieżki. Zna algorytm Bauma-Welcha. | |
| 5,0 | Zna algorytm skalowania gwarantujący precyzję numeryczną we wszytkich istotnych algorytmach. | |
| I_2A_D19/6_W05 Rozumie sens zadania pattern recognition oraz temporal pattern recognition. Ma znajomość matematycznych aspektów i rezultatów z zakresu statystycznej teorii uczenia. | 2,0 | Nie potrafi wyjaśnić sensu zadań pattern recognition oraz temporal pattern recognition. |
| 3,0 | Potrafi wyjaśnić sens zadań pattern recognition oraz temporal pattern recognition. | |
| 3,5 | Zna i rozumie pojęcia: łączny rozkład prawdopodobieństwa problemu (i.i.d.), maszyna ucząca się, zbiór funkcji aproksymujących, algorytm uczący. | |
| 4,0 | Zna i rozumie pojęcia: funkcjonał ryzyka, bład prawdziwy, reguła SAE (lub ERM). | |
| 4,5 | Rozumie matematyczne aspekty Statystycznej Teorii Uczenia: nierówność Chernoffa, ograniczenia na błąd prawdziwy dla skończonych zbiorów funkcji. | |
| 5,0 | Rozumie matematyczne aspekty Statystycznej Teorii Uczenia: wymiar Vapnika-Chervonenkisa, ograniczenia na błąd prawdziwy dla nieskończonych zbiorów funkcji. |
Kryterium oceny - umiejętności
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D19/6_U01 Potrafi stosować różne odmiany algorytmu SVM. | 2,0 | Nie potrafi użyć podstawowej wersji algorytmu SVM (środowiska MATLAB lub Mathematica). |
| 3,0 | Potrafi użyć podstawową wersję algorytmu SVM (środowiska MATLAB lub Mathematica). | |
| 3,5 | Potrafi użyć wersję podstawow algorytmu SVM z mnożnikami Lagrange'a (środowiska MATLAB lub Mathematica). | |
| 4,0 | Potrafi użyć wersję algorytmu SVM z miękkim marginesem (środowiska MATLAB lub Mathematica) z zadaną z góry stałą C. | |
| 4,5 | Potrafi użyć wersję algorytmu SVM z miękkim marginesem (środowiska MATLAB lub Mathematica) a także dobrać stałą C, wyznaczyć: margines separacji, obliczyć błąd. | |
| 5,0 | Dla danego problemu potrafi samodzielnie i skutecznie dobrać właściwą postać algorytmu SVM, a także porównać wyniki z prostszymi klasyfikatorami. | |
| I_2A_D19/6_U02 Potrafi budować modele markowowskie (i stosować algorytmy z zakresu HMM) do rozpoznawania danych ze zmiennością w czasie. | 2,0 | Nie potrafi zbudować najprostszego (jawnego) modelu markowowskiego. |
| 3,0 | Potrafi zbudować najprostszy (jawny) modelu markowowski. | |
| 3,5 | Potrafi zaprogramować algorytm Forward-Backward i zastosować do pewnego praktycznego problemu. | |
| 4,0 | Potrafi zaprogramować algorytm Vierbi'ego i zastosować do pewnego praktycznego problemu. | |
| 4,5 | Potrafi zaprogramować algorytm Bauma-Welcha i zastosować do pewnego praktycznego problemu. | |
| 5,0 | Potrafi zaprogramować algorytm skalowania obliczeń dla utrzymania precyzji numerycznej. |
Kryterium oceny - inne kompetencje społeczne i personalne
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D19/6_K01 Ma wysoką świadomość ważnych elementów teoretycznych i praktycznych dotyczących analizy danych i rozpoznawania wzorców. | 2,0 | Nie rozumie - nie zna podstawowego sensu i zastosowań - dla rozpoznawania wzorców w danych. |
| 3,0 | Rozumie - zna podstawowy sensu i zastosowania - dla rozpoznawania wzorców w danych. | |
| 3,5 | Rozumie pojęcia: zdolność do uogólniania, ograniczenia na błąd prawdziwy, złożoność próbkowa. | |
| 4,0 | Potrafi w sposób podstawowy zastosować algorytmy SVM i HMM. | |
| 4,5 | Potrafi w sposób zaawansowany zastosować algorytm SVM - tj. dobrać dobrą postać kryterium optymalizacyjnego, dobrać przekształcenie jądrowe, dobrać stałą C. | |
| 5,0 | Potrafi w sposób zaawansowany zastosować algorytmy z rodziny HMM - dobrać liczbę stanówi obserwacji, zapewnić precyzję numeryczną. |
Literatura podstawowa
- J. Koronacki, J. Ćwik, Statystyczne systemy uczące się, WNT, Warszawa, 2005
- R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, IEEE, 1989
Literatura dodatkowa
- V. Cherkassky, F. Mulier, Learning from data, Wiley & Sons, 2007
- V. Vapnik, Statistical Learning Theory, Wiley & Sons, 1998