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 – 9. Teoria systemów uczących się – MIM UW

Zagadnienia

9. Teoria systemów uczących się

9.1. Teoria systemów uczących się

9.1.1. Wstęp do komputerowego uczenia się pojęć

  • Np. Pokazać, że dla każdego n\in\mathbb{N} zachodzi

    \Psi(n):\boxed{\quad 1^{2}+2^{2}+...+n^{2}=\frac{n(n+1)(2n+1)}{6}}
  • <+-> Indukcja pełna:

    \Psi(1)\quad\text{ oraz }\quad\forall _{{n\geq 1}}[\Psi(n)\implies\Psi(n+1)]
  • <+-> Indukcja niepełna: czy wystarczy sprawdzić, np.

    \Psi(1),\Psi(2),\Psi(3),\Psi(4)?
\block

Podejście indukcyjne: Wnioskowanie na podstawie skończonego zbioru obserwacji

\onslide

<2-> Jakie prawa rządzą procesem indukcyjnego uczenia się pojęć? <3-> Szukamy teorii obejmującej zagadnienia: \onslide\block

  • Szansy na skuteczne wyuczanie się pojęć;

  • Niezbędnej liczby przykładów treningowych;

  • Złożoności przestrzeni hipotez;

  • Jakości aproksymacji;

  • Metod reprezentacji danych treningowych;

  • <+-> Niech

    • \mathcal{X} – (skończony lub nieskończony) zbiór obiektów;

    • \mathbb{C} – klasa pojęć w \mathcal{X}, tj. \mathbb{C}=\{ f:\mathcal{X}\rightarrow\{ 0,1\}\}

    • c\in\mathbb{C} – pojęcie docelowe lub funkcja celu;

  • <+-> Dane są

    • skończona próbka etykietowanych obiektów:

      D=\{\langle x_{1},c(x_{1})\rangle,...,\langle x_{m},c(x_{m})\rangle\}\in\mathcal{S}(m,c)

      gdzie x_{1},...,x_{m}\in\mathcal{X}.

    • przestrzeń hipotez \mathbb{H}=\{ h:\mathcal{X}\rightarrow\{ 0,1\}\};

  • <+-> Szukana

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

  • <+-> Wymagane

    • dobra jakość aproksymacji

    • szybki czas wyuczania.

\columns\column

0.65

  • <+-> Pojęcie: ”człowieka o średniej budowie ciała”.

  • <+-> Dane – czyli osoby – są reprezentowane przez ich wagę(kg) i wzrost(cm) i są etykietowane przez + i -.

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

\onslide

<7-> 0.35\column\onslide<4->Uczenie prostokąta \block

  • <+-> \mathcal{X}=\Re^{2};

  • <+-> \mathbb{C}=\mathbb{H}= zbiór prostokątów;

  • <+-> Przykład zbioru treningowego

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

  • <+-> ((79,183,?)

  • Uczenie półosi (lub dyskretyzacji):

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

    \mathcal{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:

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

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

\block

Błąd rzeczywisty

  • \Omega=(\mathcal{X},\mu) – przestrzeń probabilistyczna na \mathcal{X};

  • <+-> Błąd hipotezy h\in\mathbb{H} względem funkcji celu c:

    \boxed{er_{{\Omega}}(h,c)=er_{{\Omega}}^{c}(h)=\mu(\mathcal{X}_{{h\neq c}})}

    gdzie \mathcal{X}_{{h\neq c}}=\{ x\in\mathcal{X}:h(x)\neq c(x)\}.

<+->[Statystyka:] Jeśli przykłady z D są wybrane zgodnie z miarą prawdopodobieństwa \mu w sposób niezależny oraz |D|\geqslant 30, to

  • <+-> er^{c}_{{\Omega}}(h)\thickapprox er^{c}_{D}(h)=\frac{|D\cap\mathcal{X}_{{h\neq c}}|}{|D|},

  • <+-> z prawdopodobieństwem (1-\varepsilon)

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

9.1.2. Model PAC (probably approximately correct)

\block

Idea modelu PAC (Probably Approximately Correct): Określenie warunków, przy których uczeń (algorytm uczenia się) z ,,dużym prawdopodobieństwem” znajdzie ,,dobrą hipotezę” na podstawie danych D.

\onslide

<2> PAC-owy uczeń Niech \block\mathfrak{L} będzie algorytmem uczenia się, jeśli

dla każdych 0<\varepsilon,\delta<1, istnieje liczba m_{0}=m_{0}(\varepsilon,\delta) taka, że dla dowolnego pojęcia c\in\mathbb{C}, dla dowolnego rozkładu \Omega na X i dla m>m_{0} mamy

\mu^{m}\{ D\in\mathcal{S}(m,c):er_{{\Omega}}(\mathfrak{L}(D))<\varepsilon\}>1-\delta

Wówczas mówimy w skrócie, że \mathfrak{L} jest PAC dla klasy \mathbb{C} (“prawdopodobnie aproksymacyjnie poprawny”). \varepsilon = dopuszczalny poziom błędu; (1-\delta) = poziom zaufania.

  • \mathbb{H}=\mathbb{C}=\{ f_{{\lambda}}:\Re\rightarrow\{ 0,1\}:f_{{\lambda}}(x)=1\Leftrightarrow x\geqslant\lambda\}

  • c=f_{{\lambda _{0}}}

  • znaleźć \lambda _{0} na podstawie losowo wygenerowanych przykładów D=\{\langle x_{1},f_{{\lambda _{0}}}(x_{1})\rangle,...,\langle x_{m},f_{{\lambda _{0}}}(x_{m})\rangle\}

\onslide

<2->Algorytm: \block

  1. Set \lambda^{*}:=\min\limits _{{i\in\{ 1,...,m\}}}\{ x_{i}:f_{{\lambda _{0}}}(x_{i})=1\};

  2. \mathcal{L}(D):=f_{{\lambda^{*}}};

\onslide

<3-> Twierdzenie: Powyższy algorytm jest PAC \block

  • <+-> er_{{\Omega}}^{c}(f_{{\lambda^{*}}})=\mu([\lambda _{0},\lambda^{*})).

  • <+->Niech \beta _{0}=\sup\{\beta:\mu([\lambda _{0},\beta))<\varepsilon\}.

  • <+-> Wówczas er_{{\Omega}}^{c}(f_{{\lambda^{*}}})\geqslant\varepsilon\Leftrightarrow\forall _{{x_{i}\in D}}:x_{i}\notin[\lambda _{0},\beta _{0}];

  • <+->Stąd

    \displaystyle\mu^{m}\{(x_{1},...,x_{m}):\forall _{{x_{i}\in D}}:x_{i}\notin[\lambda _{0},\beta _{0}]\}\leqslant(1-\varepsilon)^{m}
    \displaystyle\mu^{m}\{ D\in\mathcal{S}(m,f_{{\lambda _{0}}}):er_{{\Omega}}(f_{{\lambda^{*}}})\leqslant\varepsilon\}\geqslant 1-(1-\varepsilon)^{m}
  • <+-> Aby to prawdopodobieństwo było >1-\delta, wystarczy przyjąć m\geqslant m_{0}=\left\lceil\frac{1}{\varepsilon}\ln\frac{1}{\delta}\right\rceil

  • Niech \Omega będzie rozkładem dyskretnym zdefiniowanym przez \mu _{1}=\mu(x_{1}), …, \mu _{n}=\mu(x_{n}) – dla pewnych x_{1},...,x_{n}\in X – takich, że \mu _{1}+...+\mu _{n}=1. Niech \varepsilon _{{\min}}=\min\limits _{{i}}\mu _{i}.

  • Jeśli \mathfrak{L} jest PAC, i jeśli \varepsilon\leqslant\varepsilon _{{\min}} to warunek er^{c}_{{\Omega}}(L(D))<\varepsilon jest równoważny z er^{c}_{{\Omega}}(L(D))=0. Stąd dla każdego \delta, istnieje m_{0}=m_{0}(\varepsilon _{{\min}},\delta) taka, że dla dowolnego c\in\mathbb{C} i \Omega

    m>m_{0}\Rightarrow\mu^{m}\{ D\in\mathcal{S}(m,t)|er_{{\Omega}}(L(D))=0\}>1-\delta
  • Wówczas mówimy, że prawdopodobnie \mathfrak{L} jest dokładnym algorytmem ( jest PEC – probably exactly correct)

9.1.3. Wyuczalność klasy pojęć

  • <+-> Niech D=\{\langle x_{1},c(x_{1})\rangle,...,\langle x_{m},c(x_{m})\rangle\} i niech

    \boxed{\mathbb{H}^{c}(D)=\{ h\in\mathbb{H}:h|D=c|D\}}

    zbiór hipotez zgodnych z c na próbce D.

  • <+-> \boxed{\mathbb{B}^{c}_{{\varepsilon}}=\{ h\in\mathbb{H}:er_{{\Omega}}(h)\geqslant\varepsilon\}} – zbiór \varepsilon-złych hipotez

\onslide

<4-> Definicja: Potencjalna wyuczalność Mówimy, że \block\mathbb{C} jest potencjalnie wyuczalna za pomocą \mathbb{H}, jeśli dla każdego rozkładu \Omega na \mathcal{X} i dowolnego pojęcia c\in\mathbb{C} oraz dla dowolnych 0<\varepsilon,\delta<1 istnieje m_{0}=m_{0}(\varepsilon,\delta) takie, że

m\geqslant m_{0}\Rightarrow\mu^{m}\{ D\in\mathcal{S}(m,c):\mathbb{H}^{c}(D)\cap\mathbb{B}^{c}_{{\varepsilon}}=\emptyset\}>1-\delta
\onslide

<1-> Algorytm \mathfrak{L} nazywamy niesprzecznym jeśli \mathfrak{L}(D)\in\mathbb{H}^{c}(D) dla każdego zbioru D.

\block

Twierdzenie W przestrzeni potencjalnie wyuczalnej, każdy wzorowy uczeń (niesprzeczny algorytm) jest PAC-owy.

\onslide

<2->

\block

Twierdzenie (Haussler, 1988) Jeśli \mathbb{C}=\mathbb{H} i |\mathbb{C}|<\infty, to \mathbb{C} jest potencjalnie wyuczalna.

Dowód: Niech h\in\mathbb{B}_{{\varepsilon}} (tzn. er_{{\Omega}}(h)\geqslant\varepsilon). Wówczas

\mu^{m}\{ D\in\mathcal{S}(m,c):er_{{D}}(h)=0\}\leqslant(1-\varepsilon)^{m}
\Rightarrow\mu^{m}\{ D:\mathbb{H}^{c}(D)\cap\mathbb{B}_{{\varepsilon}}\neq\emptyset\}\leqslant|\mathbb{B}_{{\varepsilon}}|(1-\varepsilon)^{m}\leqslant|\mathbb{H}|(1-\varepsilon)^{m}

Aby |\mathbb{H}|(1-\varepsilon)^{m}<\delta wystarczy wybrać m\geqslant m_{0}=\left\lceil\frac{1}{\varepsilon}\ln\frac{|\mathbb{H}|}{\delta}\right\rceil

9.2. Wymiar Vapnika-Chervonenkisa

9.2.1. Wymiar Vapnika Chervonenkisa (ang. VC dimension)

  • <+-> Niech \overrightarrow{\bf x}=\langle x_{1},...,x_{m}\rangle\in\mathcal{X}^{m}. Niech

    \Pi _{{\mathbb{H}}}(\overrightarrow{\bf x})=|\{\langle h(x_{1}),...,h(x_{m})\rangle\in\{ 0,1\}^{m}:h\in\mathbb{H}\}|
  • <+-> \Pi _{{\mathbb{H}}}(\overrightarrow{\bf x}) jest liczbą podziałów zbioru elementów \overrightarrow{\bf x} wyznaczonych przez \mathbb{H}. Mamy \Pi _{{\mathbb{H}}}(\overrightarrow{\bf x})\leqslant 2^{m}.

  • <+-> Gdy \Pi _{{\mathbb{H}}}(\overrightarrow{\bf x})=2^{m}, mówimy, że \mathbb{H} rozbija {\bf x}.

  • <+-> Niech \Pi _{{\mathbb{H}}}(m)=\max\limits _{{\overrightarrow{\bf x}\in\mathcal{X}^{m}}}\Pi _{{\mathbb{H}}}(\overrightarrow{\bf x})

  • <+-> Na przykład: W przypadku klasy pojęć ”półosi” postaci [\alpha,\infty) mamy \Pi _{{\mathbb{H}}}(m)=m+1.

Uwagi:

  • <+-> Jeśli \Pi _{{\mathbb{H}}}(m)=2^{m}, to istnieje pewien zbiór o mocy m taki, że \mathbb{H} może definiować każdy jego podzbiór (\mathbb{H} rozbija ten zbiór).

  • <+-> Maksymalna wartość m, dla której \Pi _{{\mathbb{H}}}(m)=2^{m} można uważać za siłę wyrażalności przestrzeni \mathbb{H}

\onslide

<3-> Definicja: wymiar \blockVCdim Wymiarem Vapnika-Chervonenkisa przestrzeni hipotez \mathbb{H} nazywamy liczbę

VCdim(\mathbb{H})=\max\{ m:\Pi _{{\mathbb{H}}}(m)=2^{m}\}

gdzie maksimum wynosi \infty jeśli ten zbiór jest nieograniczony.

\columns\column

0.7

  • <+-> H=\{okręgi … \}\implies VC(H)=3

  • <+-> H=\{prostokąty … \}\implies VC(H)=4

  • <+-> H=\{funkcje progowe … \}\implies

    VC(H)=1 jeśli “+” są zawsze po prawej stronie;

    VC(H)=2 jeśli “+” mogą być po obu stronach

  • <+-> H=\{przedziały … \}\implies

    VC(H) = 2 jeśli “+” są zawsze w środku

    VC(H) = 3 jeśli w środku mogą być zarówno “+” i “-”

  • <+-> H=\{ półpłaszczyzny w \Re^{2}\} \implies VC(H)=3

  • <+-> czy istnieje H dla której VC(H)=\infty?

\column

0.3

\block

Twierdzenie Dla każdej liczby naturalnej n, niech P_{n} będzie perceptronem o n wejściach rzeczywistych. Wówczas

VCdim(P_{n})=n+1

Dowód:

  • VCdim(P_{n})\leq n+1: Wynika z Twierdzenia Radona: Dla dowolnego zbioru E zawierającego n+2 punktów w przestrzeni \mathbb{R}^{n} istnieje niepusty podzbiór S\subset E taki, że

    conv(S)\cap conv(E\setminus S)\neq\emptyset
  • VCdim(P_{n})\geq n+1: Wystarczy wybrać \mathbf{x}=\{ 0,e_{1},...,e_{n}\} i pokazać, że każdy jego podzbiór jest definiowany przez jakiś perceptron.

\block

Twierdzenie

  1. Jeśli |\mathbb{H}|<\infty to \boxed{VCdim(\mathbb{H})\leqslant\log|\mathbb{H}|}.

  2. <+-> (Lemat Sauer'a) Jeśli VCdim(\mathbb{H})=d\geq 0 i m\geq 1, to

    {\Pi _{{\mathbb{H}}}(m)\leqslant}1+{m\choose 1}+...+{m\choose d}={\Phi(d,m)}
  3. <+-> Wniosek: \Phi(d,m)\leqslant\left(\dfrac{em}{d}\right)^{d}\Rightarrow\Pi _{{\mathbb{H}}}(m)\leqslant\left(\dfrac{em}{d}\right)^{d}

  4. <+-> Jeśli |\mathcal{X}|<\infty, \mathbb{H}\subset 2^{{\mathcal{X}}} oraz \mathbb{H}>1

    |\mathcal{X}|<\infty\implies\boxed{VCdim(\mathbb{H})>\frac{ln|\mathbb{H}|}{1+ln|\mathcal{X}|}}

9.2.2. Podstawowe twierdzenia teorii uczenia się

\block

Twierdzenie: (Warunek konieczny) Jeśli przestrzeń hipotez ma nieskończony wymiar VCdim to nie jest potencjalnie wyuczalna.

\onslide

<2-> Twierdzenie: (fundamentalne) Jeśli przestrzeń hipotez ma skończony wymiar VC, to jest ona potencjalnie wyuczalna. \block

  1. <+-> Definiujemy

    Q^{{\varepsilon}}_{m}=\{ D\in\mathcal{S}(m,c):H^{c}[D]\cap B_{{\varepsilon}}\neq\emptyset\}
  2. <+-> Szukamy górnego ograniczenia f(m,\varepsilon) dla \mu^{m}(Q^{{\varepsilon}}_{m}), które powinno

    - być niezależne od c\in\mathbb{C} i \mu (rozkład).

    - dążyć do 0 przy m\rightarrow\infty

  3. <+-> Twierdzenie Niech \mathbb{H} będzie przestrzenią hipotez określonych na X. Dla dowolnych c, \mu, \varepsilon (ale ustalonych) mamy

    \mu^{m}(Q^{{\varepsilon}}_{m})<2\Pi _{{\mathbb{H}}}(2m)2^{{-\varepsilon m/2}}

    o ile m\geqslant 8/\varepsilon.

  4. <+-> Korzystamy z lematu Sauer'a, aby pokazać, że \mu^{m}(Q^{{\varepsilon}}_{m})<\delta dla dostatecznie dużych m.

  • Dla skończonych przestrzeni hipotez \mathbb{H} mamy

    m_{L}(\mathbb{H},\delta,\varepsilon)\leq\left\lceil\frac{1}{\varepsilon}\ln\frac{|\mathbb{H}|}{\delta}\right\rceil=\left\lceil\frac{1}{\varepsilon}(\ln|\mathbb{H}|+\ln(1/{\delta}))\right\rceil
  • Twierdzenie Niech VCdim(\mathbb{H})=d\geq 1. Wówczas każdy algorytm niesprzeczny \mathfrak{L} jest PAC oraz wymagana liczba przykładów dla \mathfrak{L} wynosi

    m_{L}(\mathbb{H},\delta,\varepsilon)\leq\left\lceil\frac{4}{\varepsilon}\left(d\log\frac{12}{\varepsilon}+\log\frac{2}{\delta}\right)\right\rceil
  • Dolne ograniczenia:

    • m_{L}(\mathbb{H},\delta,\varepsilon)\geqslant d(1-\varepsilon)

    • Jeśli \delta\leq 1/100 i \varepsilon\leq 1/8, to m_{L}(\mathbb{H},\delta,\varepsilon)>\frac{d-1}{32\varepsilon}

    • m_{L}(\mathbb{H},\delta,\varepsilon)>\frac{1-\varepsilon}{\varepsilon}\ln\frac{1}{\delta}

\block

1. Wyuczalność Kiedy każdy ,,wzorowy uczeń” będzie PAC-owy?

\block

2. Liczba przykładów Ile przykładów musi mieć uczeń, by się nauczyć?

\onslide

<2-> Skończoność wymiaru \blockVCdim()

  1. <2-> VCdim(\mathbb{C})=d<\infty\Leftrightarrow\mathbb{C} jest wyuczalna;

  2. <3-> Wówczas L(\frac{1}{\varepsilon},\frac{1}{\delta},d)<m(\varepsilon,\delta)<U(\frac{1}{\varepsilon},\frac{1}{\delta},d)

\block

3. Ocena ucznia

R(\alpha)=\min _{{\alpha\in A}}\int Q^{c}_{{\Omega}}(h_{\alpha})d\mu

na podstawie N losowych przykładów

R(\alpha _{N})=\min _{{\alpha _{i}\in D}}\frac{1}{N}\sum^{N}_{{i=1}}Q^{c}(h_{{\alpha _{i}}})

Kiedy i jak szybko R(\alpha _{N})\rightarrow R(\alpha)?

\block

Skończoność wymiaru VCdim()

  1. <2->[3] Dla algorytmów typu ERM, R(\alpha _{N})\rightarrow R(\alpha) szybko.

9.2.3. Appendix: ,,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 identyfikowany 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|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 wzg. 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 wzg. 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 \mathfrak{L}_{1} uczy się wszystkich pojęć z \mathbb{P}(X) lepiej od \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 uczeniu 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źć odp. algorytm do każdego problemu.

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.