Anhang A

U ngleichungen aus Statistik und Kombinatorik

Sei X eine Menge, A, B S;;; X und D eine Wahrscheinlichkeitsverteilung auf X. Die Mengen A und B nennt man auch Ereignisse, weil sie manch­mal durch eine syntaktische Bedingung Bed(x) an die x beschrieben sind das heiBt A := {x E X I Bed(x)}. Die Wahrscheinlichkeit eines Ereignisses unter D bezeichnen wir wie folgt:

Pr [A] = PrD [A] = Pr'~D [Bed(x)] = Prx~D {x E X I Bed(x)} (A.I)

Je nachdem, wie klar die Rolle von D ist, wird der entsprechende Index gewahlt.

Sei 1 2: p 2: 0, q = 1 - p und mEN. Seien Xi, i = 1,2, ... , m, unabhangige Bernoulli Variablen mit Erfolgswahrscheinlichkeit Pr [Xi = 1] = P fUr aile i E {I, ... , m}. Sei Ym = ~ ~::l Xi, dann E[Ym] = p und a(Ym) = VfXj/m, wobei E [.] den Erwartungswert und a(-) die Standardabweichung bezeichnet.

Chernoff U ngleichung

Die Chernoff Ungleichung liefert eine obere Schranke fUr die Wahrschein­lichkeit einer groBen multiplikativen Abweichung der Zufallsvariablen Ym von ihrem Erwartungswert p. Sei 0 :S A :S 1.

(A.2)

und (A.3)

Wir werden diese Ungleichungen oft in einer anderen Formulierung anwen­den: Es bezeichne GE (p, m, k) bzw. LE (p, m, k) die Wahrscheinlichkeit, bei m Versuchen jeweils mit Erfolgswahrscheinlichkeit p mehr als bzw. weniger als k Erfolge zu sehen. Dann gilt fUr aile 0 :S f3 :S 1:

GE (p, m, (1 + (3)mp) < e-(J2mp/ 3

LE (p, m, (1 - (3)mp) < e-(J2 mp/ 2

(A.4)

(A.5)

184 ANHANG A UNGLEICHUNGEN AUS DER STATISTIK

Hoeffding U ngleichung [Hoe63]

Die Hoeffding Ungleichung liefert eine obere Schranke fur die Wahrschein­lichkeit einer groBen additiven Abweichung der Zufallsvariablen Ym von ihrem Erwartungswert p. Sei 0 ::; A ::; 1. Sei A > O.

und

zusammen

Verschatzung urn den Faktor hochstens 2 [AV79]

Pr [Ym 2: 2p 1 ::; e-mp/ 3

Pr [y. < ~p] < e-mp/ 8 m - 2 -

Abweichung von der Erwartung [VaI84]

(A.6)

(A.7)

(A.8)

(A.9)

(A. 10)

Bei m Versuchen mit Erfolgswahrscheinlichkeit p ist die Wahrscheinlichkeit, weniger als k Erfolge zu sehen (k < mp), hOchstens

(mm-_~p)m-k (m:)k < e-mp+k (m:f (A.ll)

Wenn gilt

(A.12)

so ist die Wahrscheinlichkeit in (A.ll) kleiner als &.

Bienayrne-Chebyschev

Seien Xi, i = 1, ... , m, paarweise unabhangige ZufaIlsvariablen mit ge­meinsamem Erwartungswert p, und gemeinsamer Varianz a 2 • Dann gilt fur aIle A 2: 0

(A.13)

ANHANG A UNGLEICHUNGEN AUS DER STATISTIK 185

Die Markov-Ungleichung

Sei X eine Zufallsvariable mit nichtnegativen Werten. Sei c > 0. Dann gilt

Pr [X> c] :S lE[X] . c

Abschatzungen fur Binomialkoeffizienten

Abschatzungen der Exponential-Funktion

Fur x > 0, n ~ 1 und It I :S n gilt:

1 e

In(I + x) :S x

Die Herleitung von (A.17) findet man in [Mit70].

(A.14)

(A.15)

(A.16)

(A.I7)

(A.I8)

Literaturverzeichnis

[AB92] M. Anthony und N. Biggs. Computational Learning Theory. Cam­bridge University Press, 1992.

[ACGS88] W. Alexi, B. Chor, O. Goldrich, und C.P. Schnorr. RSA and Rabin Functions: Certain Parts are as hard as the whole. SIAM J. on Computing, 17:194-209, 1988.

[AL88] D. Angluin und P. Laird. Learning from Noisy Examples. Machine Learning, 2(4):343-370, 1988.

[AV79] D. Angluin und L. Valiant. Fast Probabilistic Algorithms for Ha­miltonian Circuits and Matching. Journal of Computer and Sy­stem Sciences, 18: 155-193, 1979.

[BCH86] P.W. Beame, S.A. Cook, und H.J Hoover. Log Depth Circuits vor Division and Related Problems. SIAM J. on Computing, 19:994-1003, 1986.

[BEHW89] A. Blumer, A. Ehrenfeucht, D. Haussler, und M. Warmuth. Lear­nability and the Vapnik-Chervonenkis Dimension. J. Assoc. Compo Machinery, 36:929-965, 1989.

[Ben86] J. Bentley. Programming Pearls. Addison Wesley, 1986.

[CBDFS96] N. Cesa-Bianchi, E. Dichterman, P. Fischer, und H.U. Simon. Noise-Tolerant Learning near the Information-Theoretic Bound. In Proc. 28th Annual ACM Symposium on Theory of Computing, (STOC'96), Seiten 141-150. ACM Press, 1996.

[CM92] Z. Chen und W. Maass. On-line Learning of Rectangles. In Proc. 5th Annu. Workshop on Comput. Learning Theory, Seiten 16-28. ACM Press, New York, NY, 1992.

[CSV84] A.K. Chandra, L.J. Stockmeyer, und U. Vishkin. Constant Depth Reducibility. SIAM J. on Computing, 13:423-432, 1984.

[DH73] R. O. Duda und P. E. Hart. Pattern Classification and Scene Analysis. Wiley, 1973.

188 LITERATURVERZEICHNIS

[Dud84] R M. Dudley. A Course on Empirical Processes. Springer-Verlag, New York, Heidelberg, Berlin, 1984. Summer School St.Flour, 1982, LNCS 1097.

[EHKV88] A. Ehrenfeucht, D. Haussler, M. Kearns, und L. Valiant. A Ge­neral Lower Bound on the Number of Examples Needed for Lear­ning. In Proc. 1st Annu. Workshop on Comput. Learning Theory, Seiten 139-154. Morgan Kaufmann, San Mateo, CA, 1988.

[FHLL93] P. Fischer, K.-U. Hoffgen, H. Lefmann, und T. Luczak. Approxi­mations with Axis-Aligned Rectangles. In Proc. Fund. Compo Theo. (FCT'93), LNCS 710, Seiten 244-255. Springer Verlag, 1993.

[Fis93] P. Fischer. Finding Maximum Convex Polygons. In Z. Esik, Hrsg., Proc. Fund. Compo Theo. (FCT'93), LNCS 710, Seiten 234-243. Springer Verlag, 1993.

[FS90a] P. Fischer und H. Simon. On Learning Ring-sum Expansions. In Proc. 3rd Annu. Workshop on Comput. Learning Theory, Seiten 130-143. Morgan-Kaufmann, 1990.

[FS90b] P. Fischer und H.-U. Simon. Separation Problems and Circular Arc Systems. In RH. Mohring, Hrsg., Proc. 16th Int. Workshop on Graph- Theoretic Concepts in Computer Science, WG90, Seiten 251-259. Springer Verlag, LNCS 484, 1990.

[FS92] P. Fischer und H. Simon. On Learning Ring-sum Expansions. SIAM J. Comput., 21:181-192, 1992.

[GJ79] M. R Garey und D. S. Johnson. Computers and Intractabiliy. W.H. Freeman, 1979.

[Hoe63] W. Hoeffding. Probability Inequalities for Sums of Bounded Ran­dom Variables. Journal of the American Statistical Association, 58(301):13-30, Marz 1963.

[HR89] T. Hagerup und Ch. Rub. A Guided Tour to Chernoff Bounds. Information Processing Letters, 33:305-308, 1989.

[HSW92] D. Helmbold, R Sloan, und M. K. Warmuth. Learning Integer Lattices. SIAM J. Comput., 21(2):240-266, 1992.

LITERATURVERZEICHNIS 189

[Joh74] D.S. Johnson. Approximation Algorithms for Combinatorial Pro­blems. 1.Comput .Sys .Sci., 9:256-278,1974.

[JS68] K. Jogdeo und S. M. Samuels. Monotone Convergence of Binomial Probabilities and a Generalization of Ramanujan's Equation. The Annals of Mathematical Staistics, 39:1191-1195, 1968.

[KL93] M. Kearns und M. Li. Learning in the Presence of Malicious Errors. SIAM J. Comput., 22:807-837, 1993.

[KLPV87] M. Kearns, M. Li, L. Pitt, und L. Valiant. Recent Results on Boolean Concept Learning. In Proc. 4th Workshop on Machine Learning, Seiten 337-352, 1987.

[KSS94] Michael J. Kearns, Robert E. Schapire, und Linda M. Sellie. To­ward Efficient Agnostic Learning. Machine Learning, 17:115-142, 1994.

[KV89] M. Kearns und L. G. Valiant. Cryptographic Limitations on Lear­ning Boolean Formulae and Finite Automata. In Proc. of the 21st Symposium on Theory of Computing, Seiten 433-444. ACM Press, New York, NY, 1989.

[KV94] M. Kearns und U. Vazirani. An Introduction to Computational Learning Theory. The MIT Press, Cambridge, Massachusetts and London, England, 1994.

[Lai88] Ph. Laird. Learning from Good and Bad Data. Kluwer Academic Publishers, 1988.

[Lit88] N. Littlestone. Learning Quickly when Irrelevant Attributes Abound: a New Linear-Threshold Algorithm. Machine Learning, 2:285-318, 1988.

[Mas] W.J. Masek. Some NP-complete Set Cover Problems. MIT La­boratory for Computer Science.

[Mit70] D. Mitrinovie:. Analytic Inequalities. Springer-Verlag, New York, Heidelberg, Berlin, 1970.

[MM82] C. Meyer und S. Matyas. Cryptography: A New Dimension in Computer Data Security. John Wiley and Sons, 1982.

[PV88] L. Pitt und L. Valiant. Computational Limitations on Learning from Examples. 1. Assoc. Compo Machinery, 35:965-984, 1988.

190

[PW93]

[Rab79]

[Rei87]

[RSA78]

[Sau72]

[Sch90]

[She72]

[SS77]

[VaI84]

[Weg87]

LITERATURVERZEICHNIS

L. Pitt und M. Warmuth. The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial. J. Assoc. Compo Machinery, 40(1) :95-142, 1993.

M.O. Rabin. Digital Signatures and Public Key Functions are as Intractable as Factorization. Interner Bericht TM-212, MIT CS-Lab, 1979.

J. Reif. On Threshold Circuits and Polynomial Computations. In Proc. 2nd. Conf. Structure in Complexity Theory, Seiten 118-125, 1987.

R. Rivest, A. Shamir, und L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Comm. ACM, 21:120-126, 1978.

N. Sauer. On the Density of Families of Sets. J. Combin. Th. A, 13:145-147, 1972.

R. E. Schapire. The Strength of Weak Learnability. Machine Learning, 5(2):197-227, 1990.

S. Shelah. A Combinatorial Problem; Stability and Order for Models and Theories in Infinitary Languages. Pacific J. of Math., 41:247-261, 1972.

R. Solovay und V. Strassen. A Fast Monte-Carlo Test for Prima­lity. SIAM J. on Computing, 6:84-85, 1977.

L. G. Valiant. A Theory of the Learnable. Commun. ACM, 27(11):1134-1142, 1984.

1. Wegener. The Complexity of Boolean Functions. Wiley­Teubner, 1987.

Index

Symbole

1]-M unze 106 6 139 c-schlecht 20 c-gut 20

em pirisch 51 k-Farbbarkeits-Problem fur Hyper­

graphen 94 k-Term-DNF n 94

A abgreifen 30 aktuelle Hypothese 165 Algorithmische Lerntheorie 1 Alphabet 15 Assoziativspeicher 5

B Batch-Lernen 5 Bayes Strategie 134 Beispiel 3, 16

klassifiziertes 16 markiertes 16 negatives 16 nicht klassifiziertes 16 positives 16 unmarkiertes 16 verfalschtes 107

Beispiele klassifizierte 11

Belegung 26 Beobachtung 6 B6fiwilliges Rauschen 121 b6swilliges Rauschen 105 Boolesche Formeln 25 Boolesche Funktionen 25

Boolesche Schwellwertfunktionen 96 Boosting 65

c Charakteristische Funktion 45 classification noise 106

D Darstellungslange 15 decoding exponent 99 Disjunktion 26 disjunktive Normalform 26 DNF 26 Durchschnittsklasse 35

E effektiver Stichprobenraum 59 effizient PAC-Iernbar durch 22 effizient schwach PAC-lernbar durch

65 effizienter Occam-Algorithmus 59,

61 einfaches Polygon 36 einseitiger Fehler 52 Einsmonom 52 empirisch c-gut 51 empirischer Fehler 76 encoding exponent 99 Entschlusselungsexponent 99 Equivalence-Query 6 Ereignisse 183 Erfullenden Belegung 26

F

Fallturfunktion 98 Fehler 5, 12, 165

192

einseitiger 52 empirischer 76

Fehler einer Hypothese 20 Fehlerbereich 12

gemeinsamer 148 Fehlermenge 12, 148 Fehlerminimierungs-Problem 105 Fehlerminimierungs-Strategie 108 Fehlerschranke 165

optimale 166 Worst-Case- 165

Fehlerwahrscheinlichkeit 13, 149 gemeinsame 148, 149

four-Germans-paper 37

G

gefilterte Stichprobe 69 Gegenbeispiel 7 Gegenspieler 121

Off-Line- 122 On-Line- 122

gemaB einer Verteilung ziehen 18 gemeinsame Fehlerwahrscheinlichkeit

149 Genauigkeit einer Hypothese 20 Genauigkeitsparameter 20 Gewicht 17 Gewichtsvektor 96 GroBe einer Konzeptklasse 15 GroBe eines Konzeptes 15 gutartig 38

H Halbierungs-Algorithmus 166 Halving Algorithmus 7 Hypothese 3

aktuelle 165 konsistente 17 probabilistische 121 randomisierte 121

INDEX

Hypothesenklasse 19

I

informationstheoretische Schranke 107 Instanz 16

K Kapazitatsfunktion 30 Klassifikationsrauschen 106

zufalliges 107 klassifizierte Stich probe 16 klassifiziertes Beispiel 16 Klausel 26 KNF 26 Konjunktion 25 konjunktive Normalform 26 konservatives Lernverfahren 6 konsistent 17 konsistenter Hypothesenfinder 19 Konsistenzproblem 93 Konzept 2 Konzept 14 Konzeptklasse 14

L

gutartige 38 strukturierte 21

label 16 Lernalgorithmus 19

optimaler 166 lernbar

streng 21 Lernbarkeit

strenge 21 Lernen 2

aktives 6 aus Beobachtungen 6 durch Fragen 6 Maschinelles 2 nicht iiberwachtes 4

INDEX

PAC 11 passives 6 tutorielles 7 iiberwachtes 3

Lerner 19 Lernuniversum 14 Lernverfahren

konservatives 6 Literal 25

M

markiertes Beispiel 16 Maschinelles Lernen 2 maximal konsistent 111 Median 128 Membership-Query 6 Methode des nachsten N achbarn 2 Minimum disagreement problem 105 Monom 25 M iinzwurf-Regel 148

N negatives Beispiel 16 nicht iiberwachtes Lernen 4 nicht klassifiziertes Beispiel 16 nicht-trivial 40 noise rate 107 Normalform

o

disjunktive 26 konjunktive 26 Ring-Summen- 52

Occam's Razor 57, 58 Occam-Algorithmus 58, 59, 61 6ffentlicher Schlussel 98 Off-Line-Gegenspieler 122 Off-Line-Lernen 5 Off-Line-Lerner 165 Oh-Tilde-Notation 139

On-Line Modell 5 On-Line-Gegenspieler 122 On-Line-Lerner 165 On-Line-Modell 165 optimale Fehlerschranke 166 optimaler

193

On-Line-Lernalgorithmus 166 Orakel 6, 18

p

PAC-Kriterium 21 PAC-Lernalgorithmus 21

schwacher 66 PAC-lernbar 21

durch 21 schwach 65

PAC-Lernen 8, 11 passives Lernen 6 Polygon

einfaches 36 polynomiell PAC-Iernbar durch 22 positives Beispiel 16 probabilistische Hypothese 121 Probably Approximately Correct Lear-

ning 11 public-key cryptosystem 98

Q

Query Equivalence 6 Membership 6

Query-Lernen 6

R

random classification noise 107 randomisierte Hypothese 121 randomisierte Regel 148 Rauschen

b6Bwilliges 121 b6swilliges 105

194

Rauschen auf den Klassifikationen 106

Rauschrate 107 Reduktionen 93 Regel 122

randomisierte 148 relativ prim 98 Reprasentation 15 Reprasentationssprache 15 Reprasentation 15 Ring-Summen-Expansion 52 Robustheit eines Lemmodells 8 RSE 52

S

schwacher PAC-Lemalgorithmus 66 Schwellwert 96 Separation 66 separierende Hyperebene 97 SIze 15 Statistische Separation 66 Stichprobe 3, 16

gefilterte 69 klassifizierte 16 verrauschte 107

Stichprobe fUr eine Konzeptklasse 16

Stichprobeneffizienz 8 Stichprobenkomplexitat 21 Stichprobenraum 18

effektiver 59 streng PAC-Iembar durch 21 symmetrische Differenz 12, 14

T Teaching 7 Threshold-Funktionen 96 trapdoor function 98 tutorielles Lemen 7

u ii berwachtes Lemen 3 unabhangig 148, 150

INDEX

ungerade Linearkombination 92 Universum 3, 14

strukturiertes 21 unmarkiertes Beispiel 16 Unzuverlassigkeit 20

v Vapnik-Chervonenkis-Dimension 30,

31 verallgemeinem 13 Verallgemeinerung 2 Vereinigungsklasse 35 verfalschtes Beispiel 107 verrauschte Stichprobe 107 Verschliisselungsexponent 99 Verschl iissel ungssystem

mit offentlichen Schliisseln 98 Verteilung 13 Vorhersagefehler 165 Vorhersageregel 122

w Worst-Case-Fehlerschranke 165 Wort 15

z Zahlargument 44 zerschmettem 30 Zielklasse 19 Zielkonzept 3, 11, 19 Zielkonzeptklasse 19 zufalliges Klassifikationsrauschen 107 zulassiges Konzept 62 Zuverlassigkeitsparameter 20

Dagstuhl-Seminar 1997 Effiziente Methoden der geometrischen Modellierung und der wissenschaftlichen Visualisierung

Herausgegeben von Prof. Dr. Hans Hagen und Prof. Dr. Guido Brunnet Universiut Kaiserslautern Prof. Dr. Heinrich Muller Universiut Dortmund und Prof. Dr. Dieter Roller Universitat Stuttgart

1999. 286 Seiten. 16.2 x 22.9 cm. Kart. DM 60.-OS 438.- / SFr 54.­ISBN 3-519-02746-1

Die Gesellschaft fUr Informatik (GI) veranstaltet eine Reihe von Semi­naren. die wichtigen aktuellen Ent­wicklungen in der Informatikfor­schung gewidmet sind. Unter der Anleitung von Wissenschaftlern. die auf dem Gebiet ausgewiesen sind. erarbeiten junge Wissenschaftler solche Forschungsgebiete. die noch keine Darstellungen in Lehrbuchern gefunden haben. mit dem Ziel. die­se in einheitl icher Terminologie und verstandlich darzustellen.

""""...---- -_ .. ~

Dagstuhl-Seminar 1997

iE B. G. Teubner Stuttgart · leipzig

Aus dem Inhalt:

Jorg Wendt: Nichtlineare Spline­Interpolation - Monika Bihler: Fea­ture Modelling - Design by Feature - Ingrid Hotz: Qualitatsanalyse­Algorithmen - Dirk Schroder: Aktuelle Ansatze im Bereich Feature Recognition - Alexa Nawotki: Flachenmodifikation mit der Methode der finiten Elemente - Jurgen Toelke: Scattered-Data­Verfahren - Gudrun Albrecht: Invariante Gutekriterien im Kurvendesign - Axel Becker: Design mit energieoptimierten Twists - Gerik Scheuermann: Visualisierung von Vektor- und Tensorfeldern - Frank Albersmann: Aufbereitung von 3D-Digitalisier­daten - Oliver Deussen: A Pixel­Oriented Approach for Rendering Line Drawings - Robert Mend: Reconstruction of Surfaces from Three-Dimensional Point Clouds

Preisanderungen vorbehalten.

B. G. Teubner Stuttgart· Leipzig Postfach 80 1069 . 70510 Stuttgart

Wegener Kompendium Theoretische Informatik - eine Ideensammlung

Das Kompendium Theoretisehe Infor­matik - eine Ideensammlung erganzt das Lehrbuch Theoretische Informatik - eine algorithmenorientierte EinfOh­rung yom gleiehen Autor. Es enthiilt die gangigen Inhalte von EinfOhrungs­vorlesungen in die Theoretische Infor­matik: Entscheidbarkeit, NP-Volistan­digkeit, Endliche Automaten, Kontext­freie Grammatiken, Kellerautomaten.

Anstelle von formalen Beweisen wer­den die wesentliehen Ideen herausge­arbeitet und vorgestellt. Die Vertiefung und Auffrisehung von Kenntnissen in Theoretischer Informatik wird unter­stOtzt. Die Ideensammlung wird erganzt durch Ubungsaufgaben mit L6sungen und L6sungsmethoden sowie Testfragen mit knappen Antwor­ten. Dadurch wird eine Hilfestellung bei der Vorbereitung auf PrOfungen gegeben.

Ingo \tegeou

m B (,. H:ubncr \ Iuttgan

Von Prof. Dr. Ingo Wegener Universitat Dortmund

1996. VIII, 189 Seiten. 16,2 x 22,9 em. Kart. OM 34,-6s 248,- / SFr 31 ,­ISBN 3-519-02145-5

(Leitfaden der Informatik)

Preisanderungen vorbehalten.

B. G. Teubner Stuttgart· Leipzig