Wnioskowanie i obliczenia aproksymacyjne 1000-1M00WA
1. Problematyka wnioskowań aproksymacyjnych i jej związek z różnymi dziedzinami zastosowań takimi jak:
-maszynowe uczenie (ang. machine learning),
-wykrywanie wzorców (ang. pattern recognition),
-eksploracja danych i wykrywanie z nich wiedzy (ang. data mining and knowledge discovery),
-wnioskowanie o wiedzy (ang. reasoning about knowledge),
-przetwarzanie obrazów (ang. image processing).
2. Metody wnioskowania w oparciu o pojęcia nieostre (ang. soft computing).
3. Teoretyczne podstawy maszynowego uczenia: wymiar Vapnika-Czerwonenkisa, związki wnioskowań aproksymacyjnych z wnioskowaniami statystycznymi, rola entropii w indukcyjnym uczeniu się pojęć.
4. Problemy logiczne wnioskowań aproksymacyjnych:
-wnioskowania boolowskie,
-problem SAT i strategie poszukiwania wartościowań spełniających formuły,
-zastosowania,
-wnioskowania niemonotoniczne,
-systemy adaptacyjne,
-rewizja przekonań,
-wnioskowania o wiedzy w systemach rozproszonych,
-problemy negocjacji.
5. Metody algorytmiczne wykrywania praw i schematów wnioskowań aproksymacyjnych z danych:
-metody wykrywania nowych własności,
-metody algorytmiczne wykrywania reguł domniemań (ang. defaultowych) z danych,
-sieci bayesowskie, wykrywanie i reprezentacja zależności aproksymacyjnych, problemy dekompozycji dużych zbiorów danych.
6. Problemy złożoności obliczeniowej wnioskowań aproksymacyjnych:
-oszacowania złożoności wybranych problemów,
-heurystyki ich rozwiązań.
-zasada minimalnego opisu (ang. minimum description length) i związki z teorią złożoności Kołmogorowa,
-złożoność problemów kompresji informacji.
7. Metody oparte o niekonwencjonalne modele obliczeń (w szczególności algorytmy genetyczne i programowanie ewolucyjne, sieci neuronowe, rozwiązania hybrydowe) dla rozwiązywania problemów wnioskowania aproksymacyjnego.
Kierunek podstawowy MISMaP
matematyka
Rodzaj przedmiotu
Tryb prowadzenia
Koordynatorzy przedmiotu
Efekty kształcenia
W zakresie podstaw teoretycznych wnioskowań aproksymacyjnych student:
1. zna podstawowe pojęcia i twierdzenia z teorii uczenia się pojęć (PAC-algorytm, wymiar Vapnika-Chervonenkisa (VC), twierdzenia zwane kamieniami milowymi);
2. zna podstawowe pojęcia i twierdzenia o aproksymacji problemów NP-trudnych (algorytm aproksymacyjny w danym stopniu, schemat aproksymacyjny, przykłady problemów "dobrze" i "źle" aproksymujących się, charakteryzacja klasy NP za pomocą klasy języków rozpoznawalnych przez weryfikatory probabilistyczne , twierdzenia o nieistnieniu schematu aproksymacyjnego dla wybranych problemów); (c) podstawy logiki systemów rozproszonych w teorii przepływu informacji (klasyfikacja, infomorfizm, teoria, logika lokalna, twierdzenia o reprezentacji sieci przez kanał informacyjny oraz sieci logik lokalnych) .
3. umie wyznaczać wymiar VC dla prostych przestrzeni pojęć;
4, umie dowodzić NP-trudności wybranych problemów;
5. umie dowodzić aproksymowalność w stopniu dla wybranych problemów;
6. umie dowodzić NP-trudność istnienia schematów aproksymacyjnych dla wybranych problemów; 7. interpretować pojęcia z systemów decyzyjnych w teorii przepływu informacji;
8. potrafi formułować i dowodzić twierdzenia o reprezentacji w teorii przepływu informacji.
W zakresie wnioskowań aproksymacyjnych dotyczących wybranych zagadnień praktycznych student:
1. zna wybrane metody selekcji i wykrywania nowych cech, metody modelowania obliczeń interakcyjnych, wybrane problemy systemów samoorganizujących się i metody ich rozwiązywania oraz wybrane problemy ewolucji języka komunikacji;
2. umie konstruować heurystyki selekcji cech i zbiorów cech;
3. umie konstruować heurystyki dla poszukiwania nowych cech;
4. umie modelować interakcyjne obliczenia dla rozwiązywania problemów hierarchicznego uczenia się złożonych pojęć nieostrych;
5. potrafi konstruować strategie dla wyznaczania koalicji w wybranych problemach hierarchicznych obliczeń interakcyjnych.
Kryteria oceniania
Ocena końcowa: 50% - egzamin ustny (25% - materiał wykładu i ćwiczeń, 25% - literatura stanowiąca rozszerzenie wybranej części wykładu), 50% - przygotowanie i wygłoszenie referatu na ćwiczeniach na podstawie wybranych prac.
Literatura
1. T. Baeck: Evolutionary Algorithms in Theory and Practice, Oxford University Press 1996.
2. J. Barwise, J. Seligman: Information flow: The logic of distributed systems, Cambridge University Press 1997.
3. T. Hastie, R. Tibshirani, J. Friedman: The elements of statistical learning. Data mining, inference, and prediction. (2nd edition), Springer 2009.
4. D.S. Hochbaum: Approximation algorithms for NP-hard problems. PWS 1997.
5. A. Skowron: Wnioskowanie aproksymacyjne, notatki do wykładu, 2013.
6. V. Vapnik: Statistical learning theory. Wiley 1998.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: