Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wnioskowanie aproksymacyjne

Informacje ogólne

Kod przedmiotu: 1000-1M00WA Kod Erasmus / ISCED: 11.414 / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Wnioskowanie aproksymacyjne
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty monograficzne dla IV - V roku matematyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

Wykład został przygotowany zarówno dla studentów matematyki jak i dla studentów informatyki interesujących się aspektami teoretycznymi lub praktycznymi zastosowaniami wnioskowań aprolsymacyjnych. Wykład poświecony jest zagadnieniom i problemom, które w opinii wybitnych matematyków i informatyków należą do centralnych problemów matematyki obecnego stulecia, tak ważnych jak w XX wieku centralnym dla nauki był problem rozszyfrowania genomu ludzkiego. W wykładzie analizowane będą problemy o zasadniczym znaczeniu dla dokonania postępu w licznych zastosowaniach informatyki, w szczególności w wielu interdyscyplinarnych projektach łączących zespoły matematyków, informatyków oraz specjalistów z wielu innych dziedzin (np. neuroscience, bioinformatyka, psychologia, socjologia, ekonomia, modelowanie systemów złożonych). W wykładzie przedstawione zostaną różne teoretyczne i praktyczne aspekty metod aproksymacji pojęć z danych eksperymentalnych i wiedzy dziedzinowej.

Pełny opis:

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.

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, 2010.

6. V. Vapnik: Statistical learning theory. Wiley 1998.

Efekty uczenia się:

W zakresie podstaw teoretycznych wnioskowań aproksymacyjnych student:

1. zna podstawowe pojęcia i twierdzenia z teorii uczenia sie pojęć (PAC-algorytm, wymiar Vapnika-Chervonenkisa (VC), twierdzenia zwane kamieniami milowymi) ;

2. zna podstawowe pojęcia i twierdzenia o aproksymacji problemów NP-trudnych (algorytym 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, informorfizm, 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 sie złożonych pojęć nieostrych;

5. potrafi konstruować strategie dla wyznaczania koalicji w wybranych problemach hierarchicznych obliczeń interakcyjnych.

Metody i kryteria oceniania:

Ocena końcowa: 70% - egzamin ustny (50% - materiał wykładu, 20% - literatura stanowiąca rozszerzenie wybranej części wykładu), 30% - rozwiązywanie zadań i referat na ćwiczeniach na podstawie wybranych prac

Zajęcia w cyklu "Semestr zimowy 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-01-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Dominik Ślęzak
Prowadzący grup: Dominik Ślęzak
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (w trakcie)

Okres: 2019-10-01 - 2020-01-27
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Dominik Ślęzak
Prowadzący grup: Dominik Ślęzak
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.