Entropy

Claude Shannon (1948): Entropy as a measure of surprise / uncertainty.

Message about an event with a probability of occurrence p includes $- \mathit{log}_2 p$ bits of information

Example of a fair coin: $- \mathit{log}_2 0.5 = $1

Mutual information

Werte eines Features, F ⇒ ML-Algo ⇒ Vorhergesagte Werte eines Verhaltens B

H(F) ⇒ ML-Algo ⇒ H(B)

Mutual Information zwischen F und B definiert als

$$ I(F,B) \equiv \sum_{f,b} p(f,b) log \frac{p(f,b)}{p(f)p(b)} $$

Summieren über Feature und Verhalten

Erklärung Verhältnis-Teil: Wenn Feature und Verhalten unabhängig, dann $p(f,b) = p(f)p(b)$ und $I(F,B) = 0$

D.h. Vorhersage ist unmöglich.

H(F) + H(B) - H(F,B)

Features selection ⇒ Die, die höchste MI haben, allerdings zu rechenintensiv

Proxies: IDF; iterativ AdaBoost

Mehr features → NBC verbessert sich, fällt dann.

Redundante Features, Annahme von Bayes

Beispiel

p(+) = 10.000/15.000 = 2/3
p(-) = 5.000/15.000 = 1/3
p(hate) = 3.000/15.000 = 0,2
p(~hate) = 0,8
p(hate,+) =1/15.000 \text{(kommt in keinem positiven Kommentar vor, 1 anstelle von Null ⇒ Smoothing)}
p(~hate,+) = 10.000/15.000 = 2/3
p(hate,-) = 3.000/15.000 = 1/5
p(~hate,-) = 2.000/15.000 = 2/15

$$ I(H,S) = p(hate,+) * log \frac{p(hate,+)}{p(hate)p(+)} + \ldots = $$

Kapazität eines Kanals

Maximale mutual information, die zwischen Sender und Empfängeer pro Sekunde

Äquivalent im ML: Wie viele Trainingsdaten notwendig → Abhängig vom Konzept