Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Systemy decyzyjne – 1. Wprowadzenie do systemów decyzyjnych – MIM UW

Zagadnienia

1. Wprowadzenie do systemów decyzyjnych

1.1. Wprowadzenie do systemów decyzyjnych

1.1.1. Elementy systemów decyzyjnych

1.1.1.1. Wprowadzenie do teorii uczenia się

\block

Kto się uczy? Ograniczymy się do programów komputerowych zwanych ”algorytmami uczącymi się”.

\block

Czego się uczy?

  • pojęć: – np. odróżnienie “krzeseł” od innych mebli.

  • nieznanych urządzeń – np. używanie VCR

  • nieznanych środowisk – np. nowe miasto

  • procesów – np. pieczenie ciasta

  • rodzin podobnych wzorców – np. rozp. mowy, twarzy lub pisma.

  • funkcji: (np. funkcje boolowskie)

\block

Wymagania skuteczność, efektywność, …

Każdy “uczeń” powinien mieć zdolność uogólnienia, t.j. zdolność rozpoznawania różnych obiektów tego samego pojęcia.

Np. jeśli uczymy się funkcji, to ważne jest aby “algorytm uczenia się” nie ograniczał się do jednej konkretnej funkcji. Żądamy aby “modele uczenia” działały skutecznie na klasach funkcji.

Uczeń może pozyskać informacje o dziedzinie poprzez:

  1. Przykłady: Uczeń dostaje pozytywne i/lub negatywne przykłady. Przykłady mogą być zdobywane w sposób:

    1. losowy: według pewnego znanego lub nieznanego rozkładu;

    2. arbitralny;

    3. złośliwy: (np. przez kontrolera, który chciałby wykryć sytuację, kiedy algorytm zachowuje się najgorzej);

    4. specjalny przez życzliwego nauczyciela: (np., starającego ułatwiać proces uczenia się)

  2. Zapytania: uczeń zdobywa informacje o dziedzinie przez zadawanie nauczycielowi zapytań.

  3. Eksperymentowanie: aktywne uczenie się.

  • <+->Podejście indukcyjne: wnioskowanie na podstawie skończonego zbioru obserwacji;

  • <+-> Np. Pokazać, że dla każdego n\in\mathbb{N}

    1^{2}+2^{2}+...+n^{2}=\frac{n(n+1)(2n+1)}{6}
  • <+-> Jakie prawa rządzą w podejściu uczenia indukcyjnego?

    Szukamy teorii pozwalającej na oszacowanie

    • Prawdopodobieństwa wyuczenia się pojęć;

    • Liczby niezbędnych przykładów treningowych;

    • Złożoności przestrzeni hipotez;

    • Skuteczności aproksymacji;

    • Jakość reprezentacji danych treningowych;

Skąd wiemy, czy uczeń się nauczył lub jak dobrze się nauczył?

  • Miara jakości wsadowa (ang. off-line, batch) i miara interaktywna (ang. on-line, interactive).

  • Jakość opisu vs. jakość predykcji

  • Skuteczność: obliczona na podstawie błędu klasyfikacji, dokładności opisu …

  • Efektywność uczenia: wymagana jest wielomianowa złożoność obliczeniowa.

  • Załóżmy, że chcemy nauczyć się pojęcia ”człowieka o średniej budowie ciała”. Dane – czyli osoby – są reprezentowane przez punkty ({wzrost(cm),waga(Kg)}) i są etykietowane przez + dla pozytywnych przykładów i - dla negatywnych.

  • Dodatkowa wiedza: szukane pojęcie można wyrazić za pomocą PROSTOKĄTA

  • Na przykład dany jest etykietowany zbiór:

    ((84,184),+), ((70,170),+), ((75,163),-), ((80,180),+), ((81,195),-), ((63,191),-), ((77,187),-), ((68,168),+)

  • Znajdź etykietę ((79,183,?)

Roważany problem możemy zdefiniować problem następująco:

  • <+-> Cel: Znaleźć w \Re^{2} prostokąt R o bokach równoległych do osi.

  • <+-> Wejście: Zbiór zawierający przykłady w postaci punktów ((x,y),+/-). Punkty z tego zbioru zostały wygenerowane losowo.

  • <+-> Wyjście: Hipotetyczny prostokąt R^{{\prime}} będący “'dobrą aproksymacją” R.

  • <+-> Dodatkowe wymagania: Algorytm powinien być efektywny (ze wzgledu na złożoność obliczeniową) i powinien używać do uczenia jak najmniejszej liczby przykładów .

Przy ustalonych zbiorach pojęć \mathbb{C} (dotyczących obiektów ze zbioru X - skończonego lub nie) oraz hipotez \mathbb{H} rozważamy następujacy problem

  • <+-> Dane:

    • skończona próbka D obiektów x_{1},...,x_{m}\in X wraz z wartościami pewnej funkcji c ze zbioru \mathbb{C} na tych obiektach;

  • <+-> Szukane:

    • hipoteza h\in\mathbb{H} będąca dobrą aproksymacją pojęcia c.

  • <+-> Żądania:

    • dobra jakość aproksymacji

    • szybki czas działania.

  • Uczenie półosi (lub dyskretyzacji):

    X=\Re;\qquad\mathbb{C}=\mathbb{H}=\{[\lambda,\infty):\alpha\in\Re\}
  • Uczenie hiperpłaszczyzny:

    X=\Re^{n};\qquad\mathbb{H}=\{ f_{{w_{0},w_{1},...,w_{n}}}:\Re^{n}\rightarrow\{ 0,1\}|\}

    gdzie f_{{w_{0},...,w_{n}}}(x_{1},...,x_{n})=sgn(w_{0}+w_{1}x_{1}+...+w_{n}x_{n}).

  • Uczenie jednomianów Boolowskich:

    X=\{ 0,1\}^{n};\qquad c:\{ 0,1\}^{n}\rightarrow\{ 0,1\};

    \mathbb{H}=M_{n} = zbiór jednomianów Boolowskich o n zmiennych.

Niech

  • X – zbiór wszystkich obiektów.

  • \Omega=(X,\mu) – przestrzeń probabilistyczna określona na X.

Błąd hipotezy h\in\mathbb{H} względem pojęcia c (funkcji docelowej):

er_{{\Omega}}(h,c)=er_{{\Omega}}^{c}(h)=\mu\{ x\in X|h(x)\neq c(x)\}
Pytanie:

Dane jest pojęcie c, hipoteza h i zbiór przykladów D. Jak oszacować rzeczywisty błąd hipotezy h na podstawie jej błędu er^{c}_{D} na zbiorze D?

Odp.:

Jeśli przykłady z D są wybrane zgodnie z miarą prawdopodobieństwa \mu niezależnie od tej hipotezy i niezależnie od siebie nawzajem oraz |D|\geqslant 30, to

  • najbardziej prawdopodobną wartością er_{{\Omega}}(c,h) jest er^{c}_{D},

  • z prawdopodobieństwem (1-\varepsilon)

    |er^{c}_{{\Omega}}-er^{c}_{D}|\leqslant s_{{\frac{\varepsilon}{2}}}\sqrt{\frac{er^{c}_{D}(1-er^{c}_{D})}{|D|}}

1.1.1.2. Systemy informacyjne i tablice decyzyjne

  • Teoria zbiorów przybliżonych została wprowadzona w latach 80-tych przez prof. Zdzisława Pawlaka.

  • Głównym celem jest dostarczanie narzędzi dla problemu aproksymacji pojęć (zbiorów).

  • Zastosowania w systemach decyzyjnych:

    • Redukcja danych, selekcja ważnych atrybutów

    • Generowanie reguł decyzyjnych

    • Odkrywanie wzorców z danych: szablony, reguły asocjacyjne

    • Odkrywanie zależności w danych

\block

Przykład
Pacjent Wiek Płeć Chol. ECG Rytm serca Chory?
p_{1} 53 M 203 hyp 155 Tak
p_{2} 60 M 185 hyp 155 Tak
p_{3} 40 M 199 norm 178 Nie
p_{4} 46 K 243 norm 144 Nie
p_{5} 62 F 294 norm 162 Nie
p_{6} 43 M 177 hyp 120 Tak
p_{7} 76 K 197 abnorm 116 Nie
p_{8} 62 M 267 norm 99 Tak
p_{9} 57 M 274 norm 88 Tak
p_{{10}} 72 M 200 abnorm 100 Nie

\block

Tablica decyzyjna Jest to struktura \mathbb{S}=(U,A\cup\{ dec\}), gdzie

  • U jest zbiorem obiektów:

    U=\{ u_{1},...,u_{n}\};
  • A jest zbiorem atrybutów postaci

    a_{j}:U\rightarrow V_{j};
  • dec jest specjalnym atrybutem zwanym decyzją

    dec:U\rightarrow\{ 1,...,d\}.

Tablica decyzyjna powstaje ze zwykłych tablic danych poprzez sprecyzowanie:

  • Atrybutów (nazwanych warunkowymi): cechy, których wartości na obiektach są dostępne, np. pomiary, parametry, dane osobowe, …

  • Decyzji (atrybut decyzyjny):, t.j. cecha “ukryta” związana z pewną znaną częściowo wiedzą o pewnym pojęciu:

    • Decyzja jest znana tylko dla obiektów z (treningowej) tablicy decyzyjnej;

    • Jest podana przez eksperta (np. lekarza) lub na podstawie późniejszych obserwacji (np. ocena giełdy);

    • Chcemy podać metodę jej wyznaczania dla dowolnych obiektów na podstawie wartości atrybutów warunkowych na tych obiektach.

\columns\column

4.5cm Przedstawiona tablica decyzyjna zawiera:

  • 8 obiektów będących opisami pacjentów

  • 3 atrybuty: Headache Muscle pain, Temp.

  • Decyzję stwierdzącą czy pacjent jest przeziębiony czy też nie. lub nie

\column

8cm\example
U Ból głowy Ból mięśni Temp. Grypa
p1 Tak Tak N Nie
p2 Tak Tak H Tak
p3 Tak Tak VH Tak
p4 Nie Tak N Nie
p5 Nie Nie H Nie
p6 Nie Tak VH Tak
p7 Nie Tak H Tak
p8 Nie Nie VH Nie

Dane są obiekty x,y\in U i zbiór atrybutów B\subset A, mówimy, że

  • x,yrozróżnialne przez B wtw, gdy istnieje a\in B taki, że a(x)\neq a(y);

  • x,ynierozróżnialne przez B, jeśli one są identyczne na B, tzn. a(x)=a(y) dla każdego a\in B;

  • [x]_{B} = zbiór obiektów nierozróżnialnych z x przez B.

  • Dla każdych obiektów x,y:

    • albo [x]_{B}=[y]_{B};

    • albo [x]_{B}\cap[y]_{B}=\emptyset.

  • Relacja

    x\  IND_{B}\  y:=x,y\text{ są nierozróżnialne przez }B

    jest relacją równoważności.

  • Każdy zbiór atrybutów B\subset A wyznacza podział zbioru obiektów na klasy nierozróżnialności.

Dla B=\{ Bólgłowy,Bólmięśni\}

\columns\column

4.5cm

  • obiekty p1,p2,p3 są nierozróżnialne;

  • są 3 klasy nierozróżnialności relacji IND_{B}:

    • [p1]_{B}=\{ p1,p2,p3\}

    • [p4]_{B}=\{ p4,p6,p7\}

    • [p5]_{B}=\{ p5,p8\}

\column

8cm\example
U Ból głowy Ból mięśni Temp. Grypa
p1 Tak Tak N Nie
p2 Tak Tak H Tak
p3 Tak Tak VH Tak
p4 Nie Tak N Nie
p5 Nie Nie H Nie
p6 Nie Tak VH Tak
p7 Nie Tak H Tak
p8 Nie Nie VH Nie

1.1.1.3. Aproksymacja pojęć

\only

<2> Aproksymacja funkcji \block

  • Sztuczna sieć neuronowa;

  • Twierdzenie Kolmogorowa;

  • Modele sieci.

\block

Aproksymacja pojęć

  • Uczenie indukcyjne;

  • COLT;

  • Metody uczenia się.

\block

Wnioskowanie aproksymacyjne

  • Wnioskowanie rozmyte;

  • Wnioskowanie Boolowskie, teoria zbiorów przybliżonych;

  • Inne: wnioskowanie Bayesowskie, sieci przekonań, …

  • Klasyfikatory (algorytmy klasyfikujące) i metody oceny klasyfikatorów

  • Metody rozumowania Boolowskiego

  • Teoria zbiorów przybliżonych

  • Reguły decyzyjne, drzewo decyzyjne i lasy decyzyjne

  • Klasyfikatory Bayesowskie

  • Sieci neuronowe

  • COLT: Obliczeniowa Teoria Uczenia się

  • Metody przygotowywania danych

  • SVM: Maszyna wektorów podpierających

  • Metody wzmacniania klasyfikatorów (ang. Boosting)

1.1.1.4. Nie ma nic za darmo czyli “Non Free Lunch Theorem”

  • Znaleźć optimum nieznanej funkcji f:S\rightarrow W (f\in\mathcal{F}), gdzie S,W są skończonymi zbiorami.

  • Działanie algorytmu przeszukiwania \mathcal{A} dla funkcji f jest identyfikowane z wektorem:

    V_{{\mathcal{A}}}(f,t)=\langle(s_{1},f(s_{1})),(s_{2},f(s_{2})),...,(s_{t},f(s_{t}))\rangle
  • Ocena algorytmu: M:\{ V_{{\mathcal{A}}}(f,t)|\mathcal{A},f,t\}\rightarrow\mathbb{R}. Np.

    M(V_{{\mathcal{A}}}(f,t))=\min _{{i\in\{ 1,..,t\}}}\{ i|f(s_{i})=f_{{\max}}\}
  • Warunek NFL: Dla dowolnej funkcji M, i dla dowolnych algorytmów \mathcal{A},\mathcal{A}^{{\prime}}

    \sum _{{f\in\mathcal{F}}}M(V_{{\mathcal{A}}}(f,|S|))=\sum _{{f\in\mathcal{F}}}M(V_{{\mathcal{A}^{{\prime}}}}(f,|S|))
  • \mathcal{F} jest zamknięta względem permutacji: dla dowolnej funkcji f\ \in\mathcal{F} i dowolnej permutacji \sigma\in Perm(S) mamy \sigma f\in\mathcal{F}

\block

Twierdzenie o NFL

  • Zachodzi równoważność

    NFL\Leftrightarrow\text{$\mathcal{F}$ jest zamknięta względem permutacji}.
  • Prawdopodobieństwo wylosowania niepustej klasy funkcji zamkniętej wzg. permutacji wynosi:

    \frac{2^{{\binom{|S|+|W|-1}{|S|}}}-1}{2^{{|S|^{{|W|}}}}-1}
  • Algorytm \mathfrak{L} dobrze się uczy pojęcia c jeśli er^{c}_{{\Omega}} jest mały.

  • Niech \mathbb{P}(X)=\{ c:X\rightarrow\{ 0,1\}\}.

    Czy można stwierdzić wiedzieć, że algorytm \mathfrak{L}_{1} wyuczy się wszystkich pojęć z \mathbb{P}(X) lepiej niż algorytm \mathfrak{L}_{2}?

  • ”No Free Lunch theorem” (Wolpert, Schaffer) w wersji problemów uczenia się głosi, że:

    • Żaden algorytm nie może być najlepszy w wyuczeniu wszystkich pojęć.

    • Każdy algorytm jest najlepszy dla takiej samej liczby pojęć

    • Ale interesuje nas tylko pewna klasa problemów czyli klasa pojęć \mathbb{C}\subset\mathbb{P}(X)

    • Wniosek: Należy znaleźć odpowiedni algorytm do każdego problemu.

1.1.2. Sprawy organizacyjne

  • Obecność: 20%

  • Projekt: 40%

  • Egzamin: 40%

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.