WUT

TWG

2005

WEDT

Teoria informacji

Wykład 3

Piotr Gawrysiak

[e-mail]

2005

WUT

TWG

2005

Projekt

•

Dwie grupy studentów

•

1)

Piotr Gawrysiak – [e-mail]

•

2) Piotr Andruszkiewicz - [e-mail]

•

1) Jabłonka – Marcinkowska

•

2) Mierzejewski - Zyśk

•

Etapy:

•

I wybór tematu – 1 tydzień / propozycja tematu

•

II projekt wstępny – 4 tygodnie / wstępna analiza teoretyczna

•

III implementacja – ost. termin / pełna dokumentacja

•

Ostateczny termin oddania projektu – ostatnie zajęcia (jeśli

jednak ktoś chce być zwolniony z egzaminu, musi oczywiście

oddać projekt wcześniej, czas sprawdzania

•

Zgłoszenie pełnej dokumentacji na konferencję jest dodatkowo

premiowane ;-)

WUT

TWG

2005

Teoria informacji

•

Opracowana przez Shannona w latach 40-tych XX
w.

•

Określenie ilości informacji możliwej do
przesłania przez nieidealny /„zaszumiony” –
„noisy channel”/ kanał komunikacyjny

•

Określenie maksymalnych wartości:

•

Szybkości transmisji (pojemność kanału)

•

Stopnia kompresji danych (entropia)

•

Możliwe jest zapewnienie dowolnie małego
prawdopodobieństwa wystąpienia błędu
transmisji pod warunkiem zastosowania
odpowiednio niewielkiej szybkości transmisji i
stopnia kompresji

WUT

TWG

2005

Entropia

•

Entropia – miara chaosu, stopnia
nieuporządkowania

•

Fizyka – entropia układu rośnie, lub pozostaje
stała, jeśli nie zostanie dostarczona energia

•

Miara niepewności:

•

Niska entropia – wysoka pewność, przewidywalność

•

Wysoka entropia – niska pewność, ale także ilość
informacji jaką możemy uzyskać przeprowadzając
eksperyment

•

Miara ilości informacji

WUT

TWG

2005

Entropia

•

X: dyskretna zmienna losowa

•

pmf p(X) – rozkład zmiennej X

0 log 0 = 0

•

Jednostka – bity (stąd log

2

)

•

Entropia określa ilość informacji w zmiennej

losowej: średnia długość słowa potrzebnego do

przekazania wartości tej zmiennej przy użyciu

optymalnego kodowania

•

Notacja – H(X) = H

p

(X) = H(p) = H

X

(p) = H(p

X

)

p(x)

p(x)log

H(X)

H(p)

X

x

2











WUT

TWG

2005

Entropia

Przykład: rzucamy 8-ścienną kostką i przekazujemy

wynik

Entropia:

(bity)

3

log(8)

8

1

log

8

1

log

8

1

p(i)

p(i)log

H(X)

2

2

2

























8

1

8

1

i

i





























p(x)

1

log

E

p(x)

1

p(x)log

p(x)

p(x)log

H(X)

2

X

x

2

X

x

2

Wartość oczekiwana

Średnia ważona
prawdopodobieństwem
wystąpień wartości x

1=001, 2=010, ...

WUT

TWG

2005

Entropia

Przykład: jakiś język polinezyjski

•

Entropia (przesłanie jednej litery):

•

Kodowanie liter (dla częściej występujących liter
używamy mniejszej liczby bitów)

(bitu)

2

1

2

4

1

log

8

1

log

p(i)

p(i)log

H(X)

2

2

2





























4

1

2

8

1

4

}

,

,

,

,

,

{

u

i

a

k

t

p

i

p

t

k

a

i

u

1/8 1/4 1/8 1/4 1/8 1/8

p

t

k

a

i

u

100 00

101 01

110 111

WUT

TWG

2005

Entropia

Inne interpretacje:

•

Liczba pytań niezbędnych do odgadnięcia
przekazu – wielkość przestrzeni poszukiwań
/search space/

1

p(X)

0

H(X)

0

H(X)









Czyli gdy nie ma niepewności

WUT

TWG

2005

Entropia łączna

•

Podobnie jak dla prawdopodobieństw (łączne,
warunkowe)

•

Entropia łączna /joint entropy/ - dla dwóch
dyskretnych zmiennych losowych X, Y, średnia
długość słowa potrzebnego dla przekazanie ich
wartości











X

x

Y

y

Y)

y)logp(X,

p(x,

Y)

H(X,

WUT

TWG

2005

Entropia warunkowa

Zakładając, że odbiorca informacji zna X, entropia

warunkowa określa długość słowa potrzebną,
aby przekazać wartość Y





X)

|

p(Y

log

E

x)

|

p(y

y)log

p(x,

x)

|

p(y

x)log

|

p(y

p(x)

x)

X

|

p(x)H(Y

X)

|

H(Y

2

X

x

Y

y

2

X

x

Y

y

2

X

x



































WUT

TWG

2005

Reguła łańcuchowa dla entropii

•

Logarytmy, więc w odróżnieniu od
prawdopodobieństw reguła łańcuchowa będzie
sumą składników

)

,...X

X

|

H(X

....

)

X

|

H(X

)

H(X

)

X

...,

H(X

1

n

1

n

1

2

1

n

1,











X)

|

H(Y

H(X)

x))

|

p(y

(log

E

p(x))

(log

E

x))

|

p(y

log

p(x)

(log

E

x)))

|

(p(x)p(y

(log

E

y))

p(x,

(log

E

Y)

H(X,

2

y)

p(x,

2

p(x)

2

2

y)

p(x,

2

y)

p(x,

2

y)

p(x,

























WUT

TWG

2005

Przykład

•

Nasz język polinezyjski modelowaliśmy za
pomocą zmiennej losowej

•

Załóżmy, że dodatkowe badania pozwoliły
odkryć strukturę użycia sylab w tym języku:
wszystkie słowa składają się z ciągów sylab
złożonych ze spółgłoski (C) i samogłoski (V):

p

t

k

a

1/16 3/8

1/16 1/2

i

1/16 3/16 0

1/4

u

0

3/16 1/16 1/4

1/8

3/4

1/8

WUT

TWG

2005

Przykład cd.

•

Używając reguły łańcuchowej dla obliczenia
H(C,V):

(bitów)

1.061

3

log

4

3

4

9

3)

log

(2

4

3

3

8

1

2

H(C)

2

2













(bitów)

1.375

8

11

2

3

4

3

4

1

2

4

1

2

2

1

4

3

8

1

2

)

2

1

,0,

2

1

H(

8

1

)

4

1

,

4

1

,

2

1

H(

4

3

,0)

2

1

,

2

1

H(

8

1

)

c

|C

c)H(V

p(C

|C)

H(V

k}

t,

{p,

c



















































WUT

TWG

2005

Przykład cd.

•

Entropia ciągu (znaków, wyrazów itd.) zależy od jego
długości. W praktyce zatem wygodnie definiować
entropię dla pojedynczych znaków – entropy rate

(bitów)

2.44

8

11

3

log

4

3

4

9

|C)

H(V

H(C)

V)

H(C,

2













Dla całej sylaby

)

X

,...,

(X

X

gdzie

)

p(x

)log

p(x

n

1

)

H(X

n

1

H

n

1

1n

X

1n

2

1n

1n

rate

1n











WUT

TWG

2005

Entropia języka

•

Załóżmy, że język L jest reprezentowany przez
proces stochastyczny, generujący sekwencję
tokenów: L=(X

i

)

)

X

,...,

X

,

H(X

n

1

lim

(L)

H

n

2

1

n

rate







WUT

TWG

2005

Informacja wzajemna /mutual
information/

•

Informacja o zmiennej losowej Y, którą zawiera
zmienna losowa X

•

Miara niezależności

Y)

I(X;

X)

|

H(Y

H(Y)

Y)

|

X(X

H(X)

Y)

|

H(X

H(Y)

X)

|

H(Y

H(X)

Y)

H(X,

















Reguła łańcuchowa

?

p(x)p(y)

y)

p(x,

y)log

p(x,

y)

p(x,

y)log

p(x,

p(y)

1

p(y)log

p(x)

1

p(x)log

Y)

H(X,

H(Y)

H(X)

Y)

|

H(X

H(X)

Y)

I(X;

y

x,

2

y

x,

2

x

x

2

2



























WUT

TWG

2005

Informacja wzajemna cd.

•

H(X|X)=0 stąd

•

H(X)=H(X)-H(X|X)=I(X;X)

•

Gdy X i Y są niezależne to:

•

H(X|Y) = H(X)

•

I(X;Y) = H(X)-H(X) = 0

•

Interpretacja MI – I(X;Y) mierzy to jak bardzo

nasza wiedza o Y ułatwia (średnio)

przewidywanie wartości X

•

Mierzona w bitach

Entropia – miara
informacji własnej

WUT

TWG

2005

Model zaszumionego kanału

•

Dualizm pomiędzy kompresją, a jakością transmisji

•

Pojemność kanału – określa maksymalną szybkość
transmisji informacji

•

Wykorzystamy pojemność kanału, gdy użyjemy
kodowania X, którego rozkład maksymalizuje wartość
informacji wzajemnej pomiędzy wejściem i wyjściem dla
wszystkich możliwych rozkładów wejściowych p(X)

W

X

W*

Y

koder

dekoder

Kanał

p(y|x)

wiadomość

wejście

wyjście

Y)

I(X;

max

C

p(X)



WUT

TWG

2005

Przykład:

•

Symetryczny kanał binarny:

•

Wejście X ~ {0,1}

•

Wyjście Y -> 0->1 oraz 1->0 z prawdopodobieństwem p

•

I(X;Y) = H(Y)-H(Y|X)=H(Y)-H(p)

•

Gdy p=0 lub p=1 (kanał zawsze zamienia bity) C=1

•

Gdy p=1/2, C=0; taki kanał nie nadaje się w ogóle do
transmisji danych

H(p)

-

1

Y)

I(X;

max

p(X)



Gdy kody dla X i Y takie
same, wymagany 1 bit

WUT

TWG

2005

Zastosowanie w NLP

•

Pragniemy określić najbardziej prawdopodobną
wiadomość na wejściu kanału, znając zakodowane
wyjście

•

p(i) – model języka, rozkład występowania słów (lub
innych sekwencji)

•

p(o|i) – „operacja” wykonywana przez kanał

i)

|

p(i)p(o

argmax

p(o)

i)

|

p(i)p(o

argmax

o)

p(i|

argmax

I

i

i

i







ˆ

dekoder

Kanał

p(o|i)

I

O

WUT

TWG

2005

Zastosowanie w NLP cd.

Zastosowan
ie

Wejście

Wyjście

P(i)

P(o|i)

Tłumaczenie
automatyczn
e

Sekwencje
słów L

Sekwenc
je słów

Prawdopodobieńst
wo wystąpienia L
wg modelu języka

Model
tłumaczeni
a

OCR

Skanowany
tekst

Tekst z
błędami

Prawdopodobieńst
wo wystąpienia
tekstu w języku

Model
błędów
OCR

POS tagging

Sekwencje
znaczników
POS (t)

Sekwenc
je słów
(w)

Prawdopodobieńst
wo sekwencji
znaczników

P(w|t)

Rozpoznawa
nie mowy

Sekwencje
słów

Sygnał
mowy

Prawdopodobieńst
wo sekwencji słów

Model
akustyczny

WUT

TWG

2005

Porównywanie rozkładów

•

Dywergencja Kullbacka-Leiblera

•

Miara różnic pomiędzy pmf p(x), q(x)

•

I(X;Y) = D(p(x,y)||p(x)p(y))

•

D(p||q)>0 oraz D(p||q)=0 wtw. p=q

•

To nie jest miara odległości, nie spełnia warunku
nierówności trójkąta, ponadto nie jest symetryczna





















q(X)

p(X)

log

E

q(x)

p(x)

p(x)log

q)

||

D(p

p

X

x

Jeszcze jedna definicja MI
– „odległość” rozkładu
łącznego dwóch
zmiennych od rozkładu
dla zmiennych
niezależnych

WUT

TWG

2005

Wyrażenia regularne

/regular

expressions/

•

Są wszędzie

•

emacs, vi, perl, python, grep, sed, awk,...

•

Elementy wyrażeń regularnych

•

Ciągi znaków

•

Kleene star

•

Zbiór znaków, dopełnienie zbioru

•

Kotwice

•

Zakres

•

Alternatywa

•

Grupowanie

WUT

TWG

2005

Reguły

•

case sensitive
/woodchuck/

•

Ciągi

•

Zakres

/[wW]oodchuck/

Woodchuck lub

woodchuck

Woodchuck

/[abc]/

a, b lub c

In uomini, in

soldati

/[1234567890]/

Dowolna cyfra

Plenty of 7 to 5

/[A-Z]/

Wielka litera

we call it „A great

/[a-z]/

Mała litera

my dear

/[0-9]/

Dowolna cyfra

Chapter 1: in

WUT

TWG

2005

Reguły

•

Dopełnienie

•

Znaki opcjonalne

•

Kleene *

•

Zero lub więcej powtórzeń poprzedzającej sekwencji

•

/[ab]*/ - aaaa, bbbb, abababbba, bbabaaab

/[^A-Z] /

Nie wielka litera

Woodchuck

/[e^]/

e lub ^

Look up ^ now

/a^b/

Ciąg a^b

Look up a^b now

/woodchucks?

woodchuck lub

woodchucks

woodchuck

/colou?r/

color lub colour

colour

WUT

TWG

2005

Reguły

•

Alternatywa i grupowanie

•

Kotwice

•

^ - początek ciągu

•

$ - koniec ciągu

•

\b – granica słowa

•

\B – środek słowa

•

Kleene +

•

Przynajmniej jedno wystąpienia sekwencji

•

/[0-9]+/ - liczba całkowita

/cat|dog/

cat lub dog

cat

/gupp(y|ies)/

guppy lub guppies

guppy

/(Column_[0-

9]+_*)*/

Column 1 Column 2 itd.

WUT

TWG

2005

Hierarchia operatorów

1. Grupowanie ()
2. Liczniki * + ? {}
3. Kotwice the ^my end$
4. Alternatywa

|

{n} – n wystąpień sekwencji
{n,m} – od n do m wystąpień
{n, } - przynajmniej n wystąpień

Character escaping – np. \*, \. itd.

WUT

TWG

2005

Przykład

•

Znaleźć wystąpienia określnika “the”:

The

recent attempt by

the

police to

retain their current rates of pay has not

gathered much favor with

the

southern

factions.

Przykład - Kathy McCoy

WUT

TWG

2005

•

Znaleźć wystąpienia określnika “the”:

/the/

The recent attempt by

the

police to

retain

the

ir current rates of pay has not

ga

the

red much favor with

the

sou

the

rn

factions.

Przykład

WUT

TWG

2005

•

Znaleźć wystąpienia określnika “the”:

/[Tt]he/

The

recent attempt by

the

police to

retain

the

ir current rates of pay has not

ga

the

red much favor with

the

sou

the

rn

factions.

Przykład

WUT

TWG

2005

•

Znaleźć wystąpienia określnika “the”:

/\b[Tt]he\b/

The

recent attempt by

the

police to

retain their current rates of pay has not

gathered much favor with

the

southern

factions.

Dwa rodzaje błędów:

• False negatives

• False positives

Przykład

WUT

TWG

2005

Zastosowania w NLP

•

Wszędzie 

•

ELIZA:

•

U: Men are all alike.

•

E: IN WHAT WAY?

•

They’re always bugging us abouy something or other.

•

CAN YOU THINK OF A SPECIFIC EXAMPLE?

•

Well, my boyfriend made me come here.

•

YOUR BOYFRIEND MADE YOU COME HERE

•

He says I’m depressed much of the time.

•

I AM SORRY TO HEAR YOU ARE DEPRESSED

WUT

TWG

2005

ELIZA

•

Seria następujących po sobie substytucji ciągów

znaków

•

1 – zamiana wszystkich wystąpień my na YOUR

oraz I’m na YOU ARE itd.

•

2 – słownik substytucji:

•

s/.* YOU ARE (depressed|sad) .*/I AM SORRY TO HEAR

YOU ARE \1/

•

s/.* YOU ARE (depressed|sad) .*/WHY DO YOU THINK

YOU ARE\1/

•

s/.* all .*/IN WHAT WAY/

•

s/.* always .*/CAN YOU THINK OF A SPECIFIC

EXAMPLE/

•

Do jednego ciągu może pasować więcej niż jeden

wzorzec