• Np. Pokazać, że dla każdego n∈N zachodzi

  Ψ⁢n:⁢12+22+…+n2=n⁢n+1⁢2⁢n+16

• <+-> Indukcja pełna:

  Ψ⁢1⁢⁢ oraz ⁢⁢∀n≥1Ψ⁢n⟹Ψ⁢n+1

• <+-> Indukcja niepełna: czy wystarczy sprawdzić, np.

  Ψ⁢1,Ψ⁢2,Ψ⁢3,Ψ⁢4⁢?

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

<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

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

  • C – klasa pojęć w X, tj. C=f:X→0,1

  • c∈C – pojęcie docelowe lub funkcja celu;

• <+-> Dane są

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

    D=x1,c⁢x1,…,xm,c⁢xm∈S⁢m,c

    gdzie x1,…,xm∈X.

  • przestrzeń hipotez H=h:X→0,1;

• <+-> Szukana

  • hipoteza h∈H będąca dobrą aproksymacją pojęcia c.

• <+-> Wymagane

  • dobra jakość aproksymacji

  • szybki czas wyuczania.

0.65

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

• <+-> Dane – czyli osoby – są reprezentowane przez ich wagęk⁢g i wzrostc⁢m i są etykietowane przez + i -.

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

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

• <+-> X=ℜ2;

• <+-> C=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):

  X=ℜ;⁢C=H=λ,∞:α∈ℜ

• Uczenie hiperpłaszczyzny:

  X=ℜn;H={fw0,w1,…,wn:ℜn→{0,1}|}

  gdzie fw0,…,wn⁢x1,…,xn=s⁢g⁢n⁢w0+w1⁢x1+…+wn⁢xn.

• Uczenie jednomianów Boolowskich:

  X=0,1n;⁢c:0,1n→0,1;

  H=Mn = zbiór jednomianów Boolowskich o n zmiennych.

Błąd rzeczywisty

• Ω=X,μ – przestrzeń probabilistyczna na X;

• <+-> Błąd hipotezy h∈H względem funkcji celu c:

  e⁢rΩ⁢h,c=e⁢rΩc⁢h=μ⁢Xh≠c

  gdzie Xh≠c=x∈X:h⁢x≠c⁢x.

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

• <+-> e⁢rΩc⁢h≈e⁢rDc⁢h=D∩Xh≠cD,

• <+-> z prawdopodobieństwem 1-ε

  e⁢rΩc-e⁢rDc⩽sε2⋅e⁢rDc⁢1-e⁢rDcD

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.

<2> PAC-owy uczeń Niech \blockL będzie algorytmem uczenia się, jeśli

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

• H=C={fλ:ℜ→{0,1}:fλ(x)=1⇔x⩾λ}

• c=fλ0

• znaleźć λ0 na podstawie losowo wygenerowanych przykładów D=x1,fλ0⁢x1,…,xm,fλ0⁢xm

<2->Algorytm: \block

1. Set λ*:=mini∈1,…,m⁡xi:fλ0⁢xi=1;

2. L⁢D:=fλ*;

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

• <+-> e⁢rΩc⁢fλ*=μ⁢λ0,λ*.

• <+->Niech β0=sup⁡β:μ⁢λ0,β<ε.

• <+-> Wówczas erΩc(fλ*)⩾ε⇔∀xi∈D:xi∉[λ0,β0];

• <+->Stąd

  	μm⁢x1,…,xm:∀xi∈D:xi∉λ0,β0⩽1-εm
  	μm⁢D∈S⁢m,fλ0:e⁢rΩ⁢fλ*⩽ε⩾1-1-εm

• <+-> Aby to prawdopodobieństwo było >1-δ, wystarczy przyjąć m⩾m0=1ε⁢ln⁡1δ

• Niech Ω będzie rozkładem dyskretnym zdefiniowanym przez μ1=μ⁢x1, …, μn=μ⁢xn – dla pewnych x1,…,xn∈X – takich, że μ1+…+μn=1. Niech εmin=mini⁡μi.

• Jeśli L jest PAC, i jeśli ε⩽εmin to warunek e⁢rΩc⁢L⁢D<ε jest równoważny z e⁢rΩc⁢L⁢D=0. Stąd dla każdego δ, istnieje m0=m0⁢εmin,δ taka, że dla dowolnego c∈C i Ω

  m>m0⇒μm⁢D∈S⁢m,t|e⁢rΩ⁢L⁢D=0>1-δ

• Wówczas mówimy, że prawdopodobnie L jest dokładnym algorytmem ( jest PEC – probably exactly correct)

• <+-> Niech D=x1,c⁢x1,…,xm,c⁢xm i niech

  Hc(D)={h∈H:h|D=c|D}

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

• <+-> Bεc=h∈H:e⁢rΩ⁢h⩾ε – zbiór ε-złych hipotez

<4-> Definicja: Potencjalna wyuczalność Mówimy, że \blockC jest potencjalnie wyuczalna za pomocą H, jeśli dla każdego rozkładu Ω na X i dowolnego pojęcia c∈C oraz dla dowolnych 0<ε,δ<1 istnieje m0=m0⁢ε,δ takie, że

<1-> Algorytm L nazywamy niesprzecznym jeśli L⁢D∈Hc⁢D dla każdego zbioru D.

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

<2->

Twierdzenie (Haussler, 1988) Jeśli C=H i C<∞, to C jest potencjalnie wyuczalna.

Dowód: Niech h∈Bε (tzn. e⁢rΩ⁢h⩾ε). Wówczas

Aby H⁢1-εm<δ wystarczy wybrać m⩾m0=1ε⁢ln⁡Hδ

• <+-> Niech x→=x1,…,xm∈Xm. Niech

  ΠH⁢x→=h⁢x1,…,h⁢xm∈0,1m:h∈H

• <+-> ΠH⁢x→ jest liczbą podziałów zbioru elementów x→ wyznaczonych przez H. Mamy ΠH⁢x→⩽2m.

• <+-> Gdy ΠH⁢x→=2m, mówimy, że H rozbija x.

• <+-> Niech ΠH⁢m=maxx→∈Xm⁡ΠH⁢x→

• <+-> Na przykład: W przypadku klasy pojęć ”półosi” postaci α,∞ mamy ΠH⁢m=m+1.

Uwagi:

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

• <+-> Maksymalna wartość m, dla której ΠH⁢m=2m można uważać za siłę wyrażalności przestrzeni H

<3-> Definicja: wymiar \blockV⁢C⁢d⁢i⁢m Wymiarem Vapnika-Chervonenkisa przestrzeni hipotez H nazywamy liczbę

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

0.7

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

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

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

  V⁢C⁢H=1 jeśli “+” są zawsze po prawej stronie;

  V⁢C⁢H=2 jeśli “+” mogą być po obu stronach

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

  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 ℜ2 … } ⟹VC(H)=3

• <+-> czy istnieje H dla której V⁢C⁢H=∞?

0.3

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

Dowód:

• V⁢C⁢d⁢i⁢m⁢Pn≤n+1: Wynika z Twierdzenia Radona: Dla dowolnego zbioru E zawierającego n+2 punktów w przestrzeni Rn istnieje niepusty podzbiór S⊂E taki, że

  c⁢o⁢n⁢v⁢S∩c⁢o⁢n⁢v⁢E∖S≠∅

• VCdim(Pn)≥n+1: Wystarczy wybrać x=0,e1,…,en i pokazać, że każdy jego podzbiór jest definiowany przez jakiś perceptron.

Twierdzenie

1. Jeśli H<∞ to V⁢C⁢d⁢i⁢m⁢H⩽log⁡H.

2. <+-> (Lemat Sauer'a) Jeśli V⁢C⁢d⁢i⁢m⁢H=d≥0 i m≥1, to

   ΠH⁢m⩽1+m1+…+md=Φ⁢d,m

3. <+-> Wniosek: Φ⁢d,m⩽e⁢mdd⇒ΠH⁢m⩽e⁢mdd

4. <+-> Jeśli X<∞, H⊂2X oraz H>1

   X<∞⟹V⁢C⁢d⁢i⁢m⁢H>l⁢n⁢H1+l⁢n⁢X

Twierdzenie: (Warunek konieczny) Jeśli przestrzeń hipotez ma nieskończony wymiar V⁢C⁢d⁢i⁢m to nie jest potencjalnie wyuczalna.

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

1. <+-> Definiujemy

   Qmε=D∈S⁢m,c:Hc⁢D∩Bε≠∅

2. <+-> Szukamy górnego ograniczenia f⁢m,ε dla μm⁢Qmε, które powinno

   - być niezależne od c∈C i μ (rozkład).

   - dążyć do 0 przy m→∞

3. <+-> Twierdzenie Niech H będzie przestrzenią hipotez określonych na X. Dla dowolnych c, μ, ε (ale ustalonych) mamy

   μm⁢Qmε<2⁢ΠH⁢2⁢m⁢2-ε⁢m/2

   o ile m⩾8/ε.

4. <+-> Korzystamy z lematu Sauer'a, aby pokazać, że μm⁢Qmε<δ dla dostatecznie dużych m.

• Dla skończonych przestrzeni hipotez H mamy

  mL⁢H,δ,ε≤1ε⁢ln⁡Hδ=1ε⁢ln⁡H+ln⁡1/δ

• Twierdzenie Niech V⁢C⁢d⁢i⁢m⁢H=d≥1. Wówczas każdy algorytm niesprzeczny L jest PAC oraz wymagana liczba przykładów dla L wynosi

  mL⁢H,δ,ε≤4ε⁢d⁢log⁡12ε+log⁡2δ

• Dolne ograniczenia:

  • mL⁢H,δ,ε⩾d⁢1-ε

  • Jeśli δ≤1/100 i ε≤1/8, to mL⁢H,δ,ε>d-132⁢ε

  • mL⁢H,δ,ε>1-εε⁢ln⁡1δ

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

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

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

1. <2-> V⁢C⁢d⁢i⁢m⁢C=d<∞⇔C jest wyuczalna;

2. <3-> Wówczas L⁢1ε,1δ,d<m⁢ε,δ<U⁢1ε,1δ,d

3. Ocena ucznia

na podstawie N losowych przykładów

Kiedy i jak szybko R⁢αN→R⁢α?

Skończoność wymiaru VCdim()

1. <2->[3] Dla algorytmów typu ERM, R⁢αN→R⁢α szybko.

• Znaleźć optimum nieznanej funkcji f:S→W (f∈F), gdzie S,W są skończonymi zbiorami.

• Działanie algorytmu przeszukiwania A dla funkcji f jest identyfikowany z wektorem:

  VA⁢f,t=s1,f⁢s1,s2,f⁢s2,…,st,f⁢st

• Ocena algorytmu: M:VA⁢f,t|A,f,t→R;

  Np. M⁢VA⁢f,t=min⁡i|f⁢si=fmax

• Warunek NFL: Dla dowolnej funkcji M, i dla dowolnych algorytmów A,A′

  ∑f∈FM⁢VA⁢f,S=∑f∈FM⁢VA′⁢f,S

• F jest zamknięta wzg. permutacji: dla dowolnej funkcji f⁢∈F i dowolnej permutacji σ∈P⁢e⁢r⁢m⁢S mamy σ⁢f∈F

Twierdzenie o NFL

• zachodzi równoważność

  N⁢F⁢L⇔F jest zamknięta wzg. permutacji

• Prawdopodobieństwo wylosowania niepustej klasy funkcji zamkniętej wzg. permutacji wynosi:

  2S+W-1S-12SW-1

• Algorytm L dobrze się uczy pojęcia c jeśli e⁢rΩc jest mały.

• Niech P⁢X=c:X→0,1.

  Czy można stwierdzić wiedzieć, że L1 uczy się wszystkich pojęć z P⁢X lepiej od L2?

• ”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ęć C⊂P⁢X

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