Zagadnienia

9.1 Teoria systemów uczących się
9.2 Wymiar Vapnika-Chervonenkisa

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

Set $\lambda^{*}:=\min\limits _{{i\in\{ 1,...,m\}}}\{ x_{i}:f_{{\lambda _{0}}}(x_{i})=1\}$ ;
$\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 \block $VCdim$ 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

Jeśli $|\mathbb{H}|<\infty$ to $\boxed{VCdim(\mathbb{H})\leqslant\log|\mathbb{H}|}$ .
<+-> (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)}$
<+-> Wniosek: $\Phi(d,m)\leqslant\left(\dfrac{em}{d}\right)^{d}\Rightarrow\Pi _{{\mathbb{H}}}(m)\leqslant\left(\dfrac{em}{d}\right)^{d}$
<+-> 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

<+-> Definiujemy

$Q^{{\varepsilon}}_{m}=\{ D\in\mathcal{S}(m,c):H^{c}[D]\cap B_{{\varepsilon}}\neq\emptyset\}$
<+-> 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$
<+-> 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$ .
<+-> 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 \block $VCdim()$

<2-> $VCdim(\mathbb{C})=d<\infty\Leftrightarrow\mathbb{C}$ jest wyuczalna;
<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()$

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

	$\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}$

Systemy decyzyjne

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ęć

9.1.2. Model PAC (probably approximately correct)

9.1.3. Wyuczalność klasy pojęć

9.2. Wymiar Vapnika-Chervonenkisa

9.2.1. Wymiar Vapnika Chervonenkisa (ang. VC dimension)

9.2.2. Podstawowe twierdzenia teorii uczenia się

9.2.3. Appendix: ,,Nie ma nic za darmo” czyli “Non Free Lunch Theorem”