Bayes Filter selber bauen

14 April 2021

farhaven

Intro

1.1. Warum?

1.2. Ziel(e)

2

Grundlagen

3

Grundlagen: Wahrscheinlichkeitsrechnung

4

Grundlagen: Satz von Bayes

Einzelnes Wort:

$$ P(S|W) = \frac{P(W|S)}{P(W|S) + P(W|H)} $$

Davon haben wir:

"Wie oft" ist dabei relativ: Bei 100 "Sichtungen insgesamt" von denen 95 in Spamnachrichten waren, ist $P(W|S) = 0.95$.

Dann: $P(S|W) = \frac{0.95}{0.95 + 0.05} = 0.95 = P(W|S)$

5

Grundlagen: Satz von Bayes

Kombinieren der einzelnen Worte für eine ganze Message $M = W_1 W_2 \ldots W_n$:

$$ \begin{align} p_n &= P(S|W_n) \\
P(S|M) &= \frac{p_1 \cdot p_2 \cdot \ldots \cdot p_n}{p_1 \cdot p_2 \cdot \ldots \cdot p_n + (1-p_1) \cdot (1-p_2) \cdot \ldots \cdot (1-p_n)} \end{align} $$

Also im Grunde "rekursiv" das gleiche Schema wie bei Spamwahrscheinlichkeit von einem Wort

6

Grundlagen: Mathetricks: Logarithmen

Basis: $\log \frac{x}{y} = \log x - \log y$ und $\log xy = \log x + \log y$

Verhindert Under-/Overflow während des Aufmultiplizierens:

Dazu hilft:

$0 < P(x) < 1$ : $\log(P(x))$ bleibt "managebar":

7

Grundlagen: Mathetricks: Logarithmen

\begin{align} p &= \frac{p_0 \cdot p_1 \cdot \ldots \cdot p_n}{p_0 \cdot p_1 \cdot \ldots \cdot p_n + (1-p_0) \cdot (1-p_1) \cdot \ldots \cdot (1-p_n)} \\
\Rightarrow \frac{1}{p} &= \frac{(1-p_0) \cdot (1-p_1) \cdot \ldots \cdot (1-p_n)}{p_0 \cdot p_1 \cdot \ldots \cdot p_n} + \frac{p_0 \cdot p_1 \cdot \ldots \cdot p_n}{p_0 \cdot p_1 \cdot \ldots \cdot p_n} \\
\Rightarrow \frac{1}{p} - 1 &= \frac{(1-p_0) \cdot (1-p_1) \cdot \ldots \cdot (1-p_n)}{p_0 \cdot p_1 \cdot \ldots \cdot p_n} \\
&= \frac{1-p_0}{p_0} \cdot \frac{1-p_1}{p_1} \cdot \ldots \cdot \frac{1-p_n}{p_n} \\
\Rightarrow \log \left( \frac{1}{p}-1 \right) &= \sum_{x=0} \log (1-p_x) - \log p_x = \eta \\
\Rightarrow \frac{1}{p} - 1 &= e^\eta \qquad \Rightarrow p = \frac{1}{1 + e^\eta} & \Box \end{align}

8

Grundlagen: Mathetricks: Sigmoid

Division durch 0 für $P(x) \in \lbrace 0, 1 \rbrace$ macht alles etwas fummelig, weil das beim Aufmultiplizeren extra beachtet werden muss.

Meine Lösung: wir rechnen nicht mit $P(x)$ sondern mit $\sigma (P(x))$:

$$ \sigma (x) = \frac{1}{1 + e^{-k (x-m)}} $$

für $k = 5$ und $m = 0.5$. Dadurch ist sichergestellt, dass $0 < \sigma (P(x)) < 1$.

9

Grundlagen: Mathetricks: Sigmoid

10

Plan

11

Meine Umsetzung

12

Bloom Filter

$$ w \in F \Leftrightarrow \forall x\in \left[0, \ldots , k \right]: F_x[h_x(w)] = 1 $$

13

Counting Bloom Filter

14

Counting Bloom Filter mit $k=4$, $n=10$

$$h(w_1) = \left[ 5, 7, 3, 9 \right] , h(w_2) = \left[ 4, 9, 3, 1 \right]$$

15

Counting Bloom Filter: Usecase

Mein Spamfilter verwendet zwei Counting Bloom Filter, die uint64 speichern:

16

Counting Bloom Filter: Vor- und Nachteile

17

Sachen, die erst beim Bauen auffallen

18

Sachen, die mal waren aber nicht mehr sind

19

Lessons learned

20

Lessons learned: Macht Benchmarks

21

Lessons learned: Benchmarks

Versucht halbwegs realistische Datasets zu finden oder zu generieren:

22

Lessons learned: Benchmarks

Sammelt die Ergebnisse:

$ benchstat old.txt new.txt
name        old time/op  new time/op  delta
GobEncode   13.6ms ± 1%  11.8ms ± 1%  -13.31% (p=0.016 n=4+5)
JSONEncode  32.1ms ± 1%  31.8ms ± 1%     ~    (p=0.286 n=4+5)
23

Lessons learned: Habt ein Ziel

24

Lessons learned: Seid flexibel

25

Zeug das evtl. noch kommt

26

Alternativen

27

Thank you

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)