Vorlesung 7 Statistische Lerntheorie I - Uni Ulm · 2004. 2. 24. · M. Giese: Lernmethoden in Computer Grafik und Multimedia 22 November 2003 zBeim Arbeiten in hochdimensionalen

M. Giese: Lernmethoden in Computer Grafik und Multimedia22 November 2003

Vorlesung 7

Statistische Lerntheorie I

Martin Giese

[email protected]


Übersicht

MotivationKapazitätsmasseVapnik-Chervonenkis-Dimension


I. Motivation


Curse of Dimensionality

Beim Übergehen auf grössere Zahl von Dimensionen nimmt erforderliche Datenmenge erheblich zu.

d=1

d=2 d=3

Beispiel: gleiche Zahl von Datenpunkten


Curse of DimensionalityBeispiele (Friedman, 1994):

Abtasten mit n Datenpunkten pro Dimension:

Stichprobengrösse ~ nd

Hyperwürfel der Anteil p der Daten enthält für

Gleichverteilung auf [0,1]d :

⇒ Seitenlänge , z.B. für d=50, p=0.1 ⇒ l=0.96 dpl /1=

l1d=2 d=1

Um nur 10 % der Daten zu erfassen, muss der gesamte Hyperwürfel fast den ganzen

Datenraum abdecken!


Beim Arbeiten in hochdimensionalen Merkmalsräumen

steigt im allgemeinen die Menge der erforderlichen

Daten stark an.Zahl der erforderlichen Daten kann durch a prioriInformation (z.B. Glattheit / Komplexität von Funktionen) erheblich reduziert werden.Bei zunehmender Dimensionalität des Merkmalsraumes nimmt daher die Leistung von Lernverfahren oft drastisch ab.




Folgerungen:Durch Kontrolle der Komplexität (Kapazität) der approximierenden Funktionen (Hypothesenraum) kann Curse of Dimensionality bei geeigneten Datensätzen verhindert werden.Alternativ kann vor Anwendung des Lernverfahrens die Dimensionalität der Merkmalsvektoren verringert werden (z.B. PCA, Vorlesung 10).


Bias-Varianz-Austausch (bias variance tade off)

Regressionsproblem:Datensatz D: {(xi, yi) mit l ≥ i ≥1}

Approximation: mit H (Hypothesenraum)

L2-Fehler (siehe Vorlesung 3):

Optimallösung: Regression von x auf y

)( ii fy x≈ ∈f

∫∫∫

−+−=

−=

dxxpxfxyEyxdyxpxyEy

yxdyxpxfyfR

)())(}|{(),(),(})|{(

),(),())((][22

2

Unabhängig von f, untere Schranke für R[f]

x

Kann nach f minimiert werden.

y)(ˆ xf

∫== dyxyypxyEf )|(}|{)(* x



Real geschätzte Funktion: HZufallsabhängig durch (endlichen) Datensatz D

Generalisierungsfehler:

{ }∫∫

−=

−=

xxxx

xxxx

dpffE

ydypfffG

DD )())(*)(ˆ(

),(),())(*)((][2

2

∈)(ˆ xDf

Erwartungswert über alle Datensätze



Zerlegung des Generalisierungsfehlers in 2 Terme:

{ }{ }{ }

{ }{ } ∫∫

∫∫∫

∫∫

−+−=

−−−

−+−=

−+−=

−=

xxxxxxxx

xxxxxx

xxxxxxxx

xxxxxx

xxxx

dpffEdpfEfE

dpffEfEfE

dpffEdpfEfE

dpffEfEfE

dpffEfG

DDDDDD

DDDDDD

DDDDDD

DDDDDD

DD

)())(*)}(ˆ{()()})(ˆ{)(ˆ(

))())(*)}(ˆ{()})(ˆ{)(ˆ(2

)())(*)}(ˆ{()()})(ˆ{)(ˆ(

)())(*)}(ˆ{)}(ˆ{)(ˆ(

)())(*)(ˆ(][

22

22

2

2

Varianz (Streuung um Prädiktorerwartungswert)

Bias (Abweichung des Erwar-tungswertes vom besten Prädiktor)



Feste datenunabhängige Funktion: Varianz = 0; aber typ. hoher Bias (schlechter Fit) !

Sehr grosser Hypothesenraum, der zu perfektem Fit der Trainingsdaten führt.

Geringer Bias; aber hohe Varianz, da unwesentliche Details der Trainingsdaten modelliert werden !

In beiden Fällen grosser Generalisierungsfehler

Glattheit

BiasVarianzG[f]

ygf D vonunabh. )()(ˆ xx =


Overfitting

Jakkolaa (2002)

Zu wenig Daten: ggf. sehr kleiner Trainings-fehler, aber schlechter Generalisierungsfehler

Folgerung:Generalisierungfähigkeit wird nicht durch kleinen Trainingsfehler garantiert;entscheidend ist der Generalisierungsfehler


Heuristische Methoden zur Kontrolle des Generalisierungsfehlers Bishop (1995)

Kreuzvalidierung (Vorlesung 4)Regularisierung (Vorlesung 3)Frühes Stoppen bei iterativen Lernregeln bei neuronalen Netzen (NN)Daten verrauschenWeight sharing (Erzwingen, dass Gruppen von Gewichten ähnliche Werte annehmen)Wachsende und schrumpfende NNKombination von (kleinen) Expertennetzwerken(mixture of experts)


Vorgehen der Statistischen Lerntheorie

Messen der Komplexität (Kapazität) der approximierenden FunktionenklasseHerleitung von Bedingungen, die Konvergenz des empirischen Risikos gegen wahres Risiko garantieren Herleitung von Schranken für den Generalisie-rungsfehler, die schnelle Konvergenz garantierenMinimierung des empirischen Risikos zusammenmit Komplexitätsmassen (oder Schranken dafür)


II. Kapazitätsmasse


Komplexitätsmasse

Masse die Funktionenklasse H charakterisieren Verschiedene Masse motiviert durch verschiedeneAnsätze (Informationstheorie, paramatrische, nichtparametrische Statistik)Anwendungsbereiche:– Auswahl von Klassifikatoren– Schranken für den Generalisierungsfehler


Einfache Komplexitätsmasse

Einfache Komplexitätsmasse: abhängig von effektiver Zahl der freien Parameter (Freiheitsgrade) der Funktion f(x) ∈ HFür lineare statistische Modelle (kleinste Quadrate !) kann die Zahl der effektiven Freiheitsgrade statistisch exakt geschätzt werden

Verteilung bekannt !Erweiterungen für nichtlineare Modelle vogeschlagen.


Verteilungsabhängige Komplexitätsmasse

Geschätztes Risiko als Funktion des empirischen Risikos (l: Zahle der Datenpunkte, k: geschätzte Zahl von Freiheitsgraden):

Minimierung von statt des empirischen Risikos garantiert, dass klein.

][),(][ˆ][ emp fRlklkAfRfR =≈

][ˆ fR][ fR


Verteilungsabhängige Komplexitätsmasse

Beispiele:Final prediction error (FPE) (Akaike, 1970):

Schwartz-Kriterium (1978):

Generalisierte Kreuzvalidierung (Craven & Wahba, 1979):

klkllkA

−+

=),(

klkllkA−

+=2

ln1),(

2

),(

−=

klllkA


Verteilungsunabhängige Komplexitätsmasse

∫= ),(),()),((][ yxdyxpyxfVfR

∑=

=l

iii yxfV

lfR

1emp )),((1][

Ziel der SLT is die Kontrolle des Generalisierungfehlers unabhängig von der zugrundeliegenden VerteilungAngabe von Bedingungen, die die Konvergenz

garantieren

Angabe von Schranken für die Abweichung für endliche grosse Datensätze

Diese Bediningungen müssen unabhängig von der Verteilung (nichtparametrisch) gelten !

|][][| emp fRfR −

][][emp fRfR →


Konsistenz des empirischen Risikos

Konsistenz der Methode der Minimierung des empirischen Risikos falls das Minimum des empirischen Risikos und des wahren RisikosR[f] für l→∞ gegen denselben Wert konvergierenFormal mit :][minarg* fRf

f ∈=

H

*][]ˆ[emp fRfR l → ∞→

*][]ˆ[ fRfR l → ∞→

]ˆ[emp fR

l]ˆ[emp fR

]ˆ[ fR

*][ fR



(Punktweise) Konvergenz der Werte von Remp gegen Rfür festes f garantiert noch notwendigerweise die Konvergenz von gegen f*Durch Minimierung des empirisches Risikos wird immerFunktion f bestimmt, die zu optimalem Fit der Trainingsdaten führt; Optimum des wahren Risikos gilt unabhängig von bestimmten Datensatz.Daher muss die Konvergenz gleichmässig über alle Funktionen f ∈ H garantiert werden.

f̂



Satz (Vapnik & Chervonenkis, 1989):Für beschränkte Kostenfunktionen ist folgende Bedingung notwendig und hinreichend für die Konsistenz der Minimierung des empirischen Risikos(im oben genannten Sinne):

0|][][|suplim emp =

>−

∈∞→εfRfRP

fl H0>∀ε



Implikation: ”Worst-case”-Abschätzung ist notwendig um Konsistenz zu garantieren.Für die Praxis nicht nur Konsistenz für l → ∞ wichtig, sondern auch wie schnell die Konvergenz erfolgt für endliche l (z.B. mit exponentieller Geschwindigeit)

Schranken (Vorlesung 8)Solche Schranken hängen ab von Kapazitätsmassen der Funktionenklasse H , die spezifisch für die jeweilige Anwendung (Regression, Klassifikation, …) sind.


Zahl der Parameter nicht immer hinreichendBeispiel:

Binäre Klassifikation: y = sign(f(x))Funktionenklasse H : f(x) = sin (wx), w ∈ IR Ein freier Parameter !Fast alle Separationen von l Punkten in 2 Klassenkönnen modelliert werden für beliebiges l.

f(x) xKlasse 1

Klasse 2


III. Vapnik-Chervonenkis (VC-) Dimension


Komplexitätsmasse für Klassifikation

Komplexität eines (binären) Klassifikators gegeben durch die maximale Zahl der Zuordnungen von Datenpunkten zu den zwei KlassenKostenfunktion:Datenpunkte zusammengefasst: zi = (xi, yi) Datenvektor: Zl = [z1 … zl]

>

=Θ sonst 0

0 wenn1)(

yy


Entropiemasse

Maximale Zahl von binären Labelings von lDatenpunkten: 2l

N(Zl ): Zahl der mit einer Funktionenklasse realisierbaren verschiedenen Labelings des Datenvektors der Länge lZufalls-VC-Entropie (random VC entropy):

H(Zl ) = ln N(Zl ) (Zufallsgrösse, da abh. von zi)VC-Entropie (Vapnik Cherovenkis entropy):

H(l) = E{ln N(Zl )} (Erwartungswert über alle Stichproben der Grösse l)


EntropiemasseWachstumsfunktion (growth function):

Maximum über alle möglichen Stichproben (Existenz eines Datensatzes der auf so viele Weisen gelabelt werden kann, ist hinreichend)

verteilungsfrei !Abgekühlte VC-Entropie (annealed VC entropy):

Hann(l) = ln E{N(Zl )}Es gilt die Ungleichungskette (Vapnik, 1998):

)(maxln)( lNlGl

ZZ

=

2ln)()()( ann llGlHlH ≤≤≤


Konsistenzbedingungen (Vapnik, 1998;Cherakassky & Mulier, 1998)

Notwendige und hinreichende Bedingung für Konsistenz der Minimierung des empirischen Risikos bei gegebenerVerteilung:

Hinreichende Bedingung für exponentielle Konvergenz:

Verteilungsfreie notwendige und hinreichende Bedingung für exponentielle Konvergenz:

0)(lim =∞→ l

lHl

0)(lim ann =∞→ l

lHl

)(lG

D.h. H(l) steigt langsamer alslinear in der Zahl l der

Datenpunkte.

0lim =∞→ ll


Wachstumsfunktion (growth function)

Es gilt immer: l ln 2 ≥ G(l)Ab einem bestimmten Wert l > h kann G(l) von einer linearen Funktion in l abweichen; dann gilt:

Der Wert h heisst Vapnik-Chervonenkis-Dimension(VC-Dimension)Falls G(l) linear überall, wird VC-Dimension als ∞ definiert.

+≤

hlhlG ln1)( G(l)

lh

l ln 2

h (ln (l/h) +1)


VC (Vapnik-Chervonenkis) Dimension

Definition: Die VC-Dimension h ist gegeben durch die maximale Zahl von Datenpunkten, die durch die Funktionenklasse auf alle 2l möglichen Weisen in 2 Klassen aufgeteilt werden können. Folgerungen:

Es gibt mindestens einen Datensatz mit h Elementen, der auf alle möglichen Weisen gelabelt werden kann.Es gibt keinen Datensatz mit h+1 Punkten, der aufalle möglichen Weisen gelabelt werden kann.



Mukherjee & Poggio (2002)

Beispiel: f(x) linear2D, 2 Datenpunkte

22 = 4 mögliche Labelings





23 = 8 mögliche Labelings





Für 4 Datenpunktekönnen nicht allemöglichen Labeleings erzeugt werden, wenn f(x) linear ist.

VC Dimension h = 3



Satz (Vapnik): Die Endlichkeit VC-Dimension (h < ∞) ist notwendig und hinreichend für die Konsistenz der Minimierung desempirischen Risikos für Hypothesenräume mit beschränkten Funktionen, und für die schnelle (exponentielle) Konvergenz des Fehlers.


VC (Vapnik-Chervonenkis) DimensionBeispiele:

Lineare Funktionen (Hyperebenen) für x ∈ IRd: h = d +1

f(x) = sin (wx), w ∈ IR: h = ∞

Linearkombination von m linear unabhängigen Funktionen: h = m+1

Multilayer Perzeptron (harte Schwelle) mit n adjustierbaren Gewichten: h ~ n ln n (Maass, 1994)

0)( wf T += xwx

01

)()( wgwf n

m

nn += ∑

=

xx



Verallgemeinerung für kontinuierliche beschränkteFunktionen (für Regression):

Sei: A ≤ V(f(x), y) ≤ B, d.h. beschränkte Kostenfunktion

Herleitung einer binären Indikatorfunktion:Θ(V(f(x), y) – β) mit A ≤ β ≤ B

Als VC-Dimension der kontinuierlichen Funktionenklasse mit den Elementen f(x) wird dann die VC-Dimension dieser binären Indikatorfunktionen mit Parameter β definiert.


Wichtige Punkte

Curse of DimensionalityBias-Varianz-ProblemOverfittingParametrische KapazitätsmasseKonsistenz des empirischen RisikosVC-DimensionBedingung für exponentielle Konvergenz


Literatur

Bishop, C.M. (1995). Neural Networks for Pattern Recognition. Oxford University Press, UK.

Cherkassky, V., Mulier, F. (1998). Learning From Data. John-Wiley & Sons Inc, New York.

Christianini, N., Shawe-Taylor, J. (2000). Support vector Machines. Cambridge University Press, UK.

Evgeniou, T., Pontil, M., Poggio, T. (2000). Regularization networks and Support Vector Machines. Advances in Computational Mathematics, 13, 1-50.

Hastie, T., Tibshirani, R., Friedman, J. (2001). The Elements of Statistical learning Theory. Springer, Berlin.

Vapnik, V.N. (1998). Statistical learning Theory. John Wiley & Sons, New York.


Web-Seiten

http://fpn.mit.edu/9.520Spring2002/ MIT Course 9.520: Statistical Learning Theory and Applications. (T. Poggio, S. Mukherjee, R.Rifkin)

http://www.ai.mit.edu/courses/6.867/ MIT Course 6.867: Machine learning. (T. Jaakkola)

Documents

Vorlesung 7 Statistische Lerntheorie I - Uni Ulm · 2004. 2. 24. · M. Giese: Lernmethoden in Computer Grafik und Multimedia 22 November 2003 zBeim Arbeiten in hochdimensionalen