Wnioskowanie i obliczenia aproksymacyjne

informatyka
matematyka

monograficzne

w sali

Wykład został przygotowany zarówno dla studentów matematyki jak i dla studentów informatyki, interesujących się aspektami teoretycznymi oraz zastosowaniami praktycznymi wnioskowania aproksymacyjnego. Wykład poświęcony 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.

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.

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.

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.

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.