[ Pobierz całość w formacie PDF ]
UNIWERSYTET MARII CURIESKŁODOWSKIEJ
W LUBLINIE
WYDZIAŁ MATEMATYKI FIZYKI I INFORMATYKI
Michał Pańczyk
Wykorzystanie złożoności Kołmogorowa
do wyznaczania związków kontekstowych
poprzez analizę efektów pracy
wyszukiwarek internetowych
Using Kolmogorov complexity to discover context associations
by analysis of web search engines’ search effects
Praca magisterska wykonana
pod kierunkiem dra Jerzego Mycki
Lublin 2008
Składam serdeczne podziękowania
Panu dr. Jerzemu Mycce
za poświęcony czas, cenne wskazówki
i wszelką pomoc okazaną
podczas pisania niniejszej pracy.
Spis treści
Wprowadzenie
iv
1. Podstawy teorii złożoności Kołmogorowa 1
1.1. Notacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1. Słowa i kody . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2. Funkcje rekurencyjne . . . . . . . . . . . . . . . . . . . . 5
1.1.3. Maszyna Turinga . . . . . . . . . . . . . . . . . . . . . . 6
1.2. Klasyczna złożoność Kołmogorowa . . . . . . . . . . . . . . . . 8
1.2.1. Definicja . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2. Własności . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3. Prefiksowa złożoność Kołmogorowa . . . . . . . . . . . . . . . . 14
1.3.1. Definicja . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.2. Własności . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2. Odległość informacyjna 17
2.1. Intuicja zagadnienia . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2. Znormalizowana odległość informacyjna . . . . . . . . . . . . . . 18
2.3. Znormalizowana odległość kontekstowa . . . . . . . . . . . . . . 19
2.3.1. Definicja . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.2. Własności . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.3. Przykłady . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3. Program komputerowy 28
3.1. Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2. AlgorytmFindInadequate . . . . . . . . . . . . . . . . . . . 29
3.3. Język programowania Python . . . . . . . . . . . . . . . . . . . 31
3.4. Implementacja algorytmu. . . . . . . . . . . . . . . . . . . . . . 35
3.5. Przykłady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.6. Kod programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
iii
Wprowadzenie
W niniejszej pracy zajmiemy się zagadnieniem bliskości kontekstowej
między słowami z języka naturalnego. Idea przedstawiona przez nas została
zaproponowana w [5]. Wykorzystuje ona teorię złożoności Kołmogorowa [6]
oraz częstość występowania słów na stronach internetowych zindeksowanych
przez popularne wyszukiwarki.
Otrzymanąmiaręodległościkontekstowejzastosujemywzaprojektowanym
przez nas algorytmie, który mając podaną na wejściu listę bliskich sobie
słów oraz jedno słowo spoza ich wspólnego kontekstu, wskazuje właśnie
to niepasujące słowo. Program implementujący nasz algorytm napisaliśmy
w języku Python.
Rozdział pierwszy przedstawia używaną notację oraz podstawy teorii
złożoności Kołmogorowa. Prezentujemy w nim twierdzenia pozwalające
na wyrobienie pewnej intuicji oraz mające wpływ na zastosowanie teorii,
w szczególności prezentujemy własny dowód nieobliczalności
C
(tw. 1.2.11).
Rozdział ten został opracowany na podstawie książki [6], a także [8]
oraz pracy [7].
Rozdział drugi przedstawia zagadnienie bliskości informacyjnej i na jej
podstawiewyprowadza odległośćkontekstową główniewoparciuo[1]oraz[5].
Omówiona została również przydatność różnych wyszukiwarek internetowych
dla naszego zagadnienia.
Rozdział trzeci prezentuje zaproponowany przez nas algorytm odrzucania
słowa niepasującego do kontekstu określonego przez listę słów. Przedstawiono
implementację w języku Python, krótkie wprowadzenie do niego oraz przy
kłady działania programu.
iv
Rozdział 1
Podstawy teorii złożoności
Kołmogorowa
1.1. Notacja
W celu sprawnego posługiwania się terminami używanymi w dalszej części
pracy, musimy zdefiniować kilka pojęć wstępnych.
1.1.1. Słowa i kody
Definicja 1.1.1.
Alfabet
jest niepustym, skończonym zbiorem niepodziel
nych symboli.
Takskonstruowana definicjagwarantujenam,żesłowabędąjednoznacznie
rozkładalne na symbole. Przykładem wadliwie zbudowanego alfabetu jest
{
a
,
b
,
ab
}
, gdyż słowo
ab
może być zbudowane z pojedynczego symbolu
ab
lub z dwóch symboli
a
i
b
. Najczęściej będziemy oznaczać alfabet przez Σ.
Definicja1.1.2.
Słowem(napisem)x
odługości
n
—cozapisujemy
l
(
x
)=
n
— nazywamy funkcję
x
: Z
n
−→
Σ, gdzie Z
n
=
{
1
,
2
,...,n
}
.
Zbiór wszystkich słów długości
n
oznaczamy przez Σ
n
, przy czym Σ
0
zawiera jeden element, oznaczany przez
ǫ
, zwany słowem pustym.
Słowa zapisujemy wymieniając po kolei składowe symbole: Σ
n
∋
x
=
x
(1)
x
(2)
...x
(
n
) lub — stosując krótszy zapis —
x
=
x
1
x
2
...x
n
, zatem
x
(
i
)=
x
i
∈
Σ oznacza
i
ty symbol słowa
x
.
1
[ Pobierz całość w formacie PDF ]
© 2009 Po zniszczeniu przeszłości przyszedł czas na budowanie przyszłości. - Ceske - Sjezdovky .cz. Design downloaded from free website templates