www-ai.cs.tu-dortmund.de/de/LEHRE/VORLESUNGEN/KDD/SS13/FOLIEN/9MLVsubgroup.pdf
Vorlesung Wissensentdeckung - Knowledge based sampling – KBS
Hoeffding-Schranke ist unabhängig von Acc definiert.
Pr[Ȳ − p ≥ ε] ≤ exp(−2ε2m)
Pr[Ȳ − p ≤ −ε] ≤ exp(−2ε2m)
Pr[| Ȳ −−p |≥ ε] ≤ 2exp(−2ε2m) (4)
Die wahre Acc soll um nicht mehr als 10% über- oder unterschätzt [...] Wegen Gleichung (4) ergibt sich:
Pr[| Âcc−Acc |≥ 0, 1] ≤ 2exp(−2 ·(0, 1)2m) ≤ 2exp(0, 02m)
Risiko ≤ δ = 5% dafür bei m ∼ 184 Beispielen:
2exp(−0, 02m) ≤ 0, 05⇔ −0, 02m ≤ ln 1
40 ⇔ 0, 02m ≥ ln 40⇔ m ≥ [...] distributed) bezeichnet.
Beispiel dreimaliges Würfeln: X1 1. Wurf, X2 2. Wurf, X3 3. Wurf sind i.i.d. verteilt. X4 = X1 +X2 und X5 = X2 +X3 sind zwar identisch verteilt, aber nicht unabhängig. X4 und X3 …