Darmowy fragment publikacji:
Tytuł oryginału: Machine Learning for Hackers
Tłumaczenie: Przemysław Szeremiota
ISBN: 978-83-246-9816-5
© 2015 Helion S.A.
Authorized Polish translation of the English edition of Machine Learning
for Hackers 9781449303716 © 2012 Drew Conway and John Myles White.
This translation is published and sold by permission of O’Reilly Media,
Inc., which owns or controls all rights to publish and sell the same.
All rights reserved. No part of this book may be reproduced or transmitted
in any form or by any means, electronic or mechanical, including photocopying,
recording or by any information storage retrieval system, without permission
from the Publisher.
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości
lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą
kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub
innym powoduje naruszenie praw autorskich niniejszej publikacji.
Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi
bądź towarowymi ich właścicieli.
Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były
kompletne i rzetelne. Nie bierze jednak żadnej odpowiedzialności aniza ich wykorzystanie, ani za związane
z tym ewentualne naruszenie praw patentowych lub autorskich. Wydawnictwo HELION nie ponosi również
żadnej odpowiedzialności za ewentualne szkody wynikłez wykorzystania informacji zawartych w książce.
Wydawnictwo HELION
ul. Kościuszki 1c, 44-100 GLIWICE
tel. 32 231 22 19, 32 230 98 63
e-mail: helion@helion.pl
WWW: http://helion.pl (księgarnia internetowa, katalog książek)
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
http://helion.pl/user/opinie/umapro
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
Printed in Poland.
• Kup książkę
• Poleć książkę
• Oceń książkę
• Księgarnia internetowa
• Lubię to! » Nasza społeczność
Spis tre(cid:316)ci
Wst(cid:253)p .............................................................................................................................7
1.
J(cid:253)zyk R .......................................................................................................................... 13
14
J(cid:246)zyk R w uczeniu maszynowym
16
19
20
23
36
Pobieranie i instalowanie R
Edytory plików tekstowych i (cid:264)rodowiska programistyczne
(cid:227)adowanie i instalowanie pakietów R
Podstawy R w uczeniu maszynowym
Dodatkowe materia(cid:228)y o R
2. Eksplorowanie danych ................................................................................................39
39
40
43
45
46
46
48
49
52
67
Analiza eksploracyjna i analiza potwierdzaj(cid:241)ca
Czym s(cid:241) dane?
Wnioskowanie o typach danych w kolumnach
Wnioskowanie o znaczeniu warto(cid:264)ci
Podsumowania liczbowe
(cid:263)rednie, mediany i dominanty
Kwantyle
Odchylenia standardowe i wariancje
Eksploracyjne wizualizacje danych
Wizualizowanie powi(cid:241)za(cid:254) pomi(cid:246)dzy kolumnami
3. Klasyfikacja — odsiewanie spamu .............................................................................73
73
77
78
To czy nie to? Klasyfikacja binarna
P(cid:228)ynne przej(cid:264)cie do prawdopodobie(cid:254)stwa warunkowego
Nasz pierwszy bayesowski klasyfikator spamu
Definiowanie i testowanie klasyfikatora
na w(cid:241)tpliwych wiadomo(cid:264)ciach tre(cid:264)ciwych
Testowanie klasyfikatora na wiadomo(cid:264)ciach wszystkich typów
Polepszanie wyników klasyfikacji
84
88
91
3
Poleć książkęKup książkęJak uporz(cid:241)dkowa(cid:232), nie znaj(cid:241)c kryterium?
Uk(cid:228)adanie wiadomo(cid:264)ci e-mail wed(cid:228)ug wa(cid:276)no(cid:264)ci
4. Uk(cid:293)adanie rankingu — priorytetowa skrzynka pocztowa ........................................93
93
94
95
99
99
106
110
115
Cechy istotno(cid:264)ci wiadomo(cid:264)ci e-mail
Implementacja skrzynki priorytetowej
Funkcje wy(cid:228)uskuj(cid:241)ce warto(cid:264)ci cech
Tworzenie mechanizmu nadawania wag
Nadawanie wag na podstawie aktywno(cid:264)ci w w(cid:241)tku
Uczenie i testowanie algorytmu uk(cid:228)adaj(cid:241)cego ranking
Wprowadzenie do regresji
5. Regresja — przewidywanie ods(cid:293)on stron ................................................................ 123
123
123
126
128
135
145
Model wyj(cid:264)ciowy
Regresja z u(cid:276)yciem zmiennych sztucznych
Podstawy regresji liniowej
Przewidywanie odwiedzin stron WWW
Definiowanie korelacji
Wst(cid:246)p do regresji wielomianowej
Nieliniowe zale(cid:276)no(cid:264)ci pomi(cid:246)dzy kolumnami — (cid:264)wiat krzywych
6. Regularyzacja — regresja tekstu .............................................................................. 149
149
152
158
162
166
170
Zapobieganie nadmiernemu dopasowaniu przez regularyzacj(cid:246)
Metody zapobiegania nadmiernemu dopasowaniu
Regresja tekstu
Pociecha w regresji logistycznej
7. Optymalizacja — (cid:293)amanie szyfrów ...........................................................................175
175
181
185
Wprowadzenie do optymalizacji
Regresja grzbietowa
(cid:227)amanie szyfrów jako problem optymalizacji
8. Analiza g(cid:293)ównych sk(cid:293)adowych — budowanie indeksu rynku ................................ 195
195
Uczenie nienadzorowane
Grupowanie na podstawie podobie(cid:254)stwa
9. Skalowanie wielowymiarowe — uwidocznianie podobie(cid:295)stwa polityków .........203
203
204
209
210
Wprowadzenie do miar odleg(cid:228)o(cid:264)ci i skalowania wielowymiarowego
Analiza rejestrów g(cid:228)osowa(cid:254) w Senacie (kongresy 101. – 111.)
Jak si(cid:246) grupuj(cid:241) ameryka(cid:254)scy senatorzy?
4
(cid:95)
Spis tre(cid:316)ci
Poleć książkęKup książkę10. kNN — systemy rekomendacyjne.............................................................................. 219
219
224
Algorytm kNN
Dane o instalacjach pakietów j(cid:246)zyka R
Analiza sieci spo(cid:228)ecznych
My(cid:264)lenie grafowe
Pozyskiwanie danych do grafu spo(cid:228)ecznego Twittera
11. Analiza grafów spo(cid:293)ecznych .....................................................................................229
229
231
233
236
241
242
246
251
Lokalna struktura spo(cid:228)eczna
Wizualizacja pogrupowanej sieci spo(cid:228)ecznej Twittera w programie Gephi
W(cid:228)asny mechanizm rekomendacji warto(cid:264)ciowych twitterowiczów
Praca z API us(cid:228)ugi SocialGraph
Analiza sieci Twittera
12. Porównanie modeli ...................................................................................................259
259
269
SVM — maszyna wektorów no(cid:264)nych
Porównanie algorytmów
Bibliografia ................................................................................................................ 274
Skorowidz .................................................................................................................. 276
Spis tre(cid:316)ci
(cid:95)
5
Poleć książkęKup książkę6
(cid:95)
Spis tre(cid:316)ci
Poleć książkęKup książkęROZDZIA(cid:292) 7.
Optymalizacja — (cid:293)amanie szyfrów
Wprowadzenie do optymalizacji
Jak dot(cid:241)d, wi(cid:246)kszo(cid:264)(cid:232) algorytmów opisywanych w ksi(cid:241)(cid:276)ce traktowali(cid:264)my jak swego rodzaju
„czarne skrzynki” — skupiali(cid:264)my si(cid:246) na zrozumieniu danych wej(cid:264)ciowych i interpretacji danych
wyj(cid:264)ciowych. Zasadniczo wi(cid:246)c traktowali(cid:264)my algorytmy uczenia maszynowego jako funkcje
biblioteczne, specjalizowane do wykonywania zada(cid:254) predykcyjnych.
W tym rozdziale przyjrzymy si(cid:246) jednak technikom wykorzystywanym do implementowania
najprostszych algorytmów uczenia maszynowego. Jako punkt wyj(cid:264)cia we(cid:274)miemy funkcj(cid:246) do
dopasowywania prostych modeli regresji liniowej z jednym predyktorem. Przyk(cid:228)ad ten po-
zwoli na spojrzenie na problem dopasowania modelu do danych jako problem optymalizacji.
Problem optymalizacji to taki problem, w którym dysponuj(cid:241)c pewnym urz(cid:241)dzeniem albo
mechanizmem, chcemy dostraja(cid:232) jego dzia(cid:228)anie i mierzy(cid:232) wp(cid:228)yw dostrajania na sprawno(cid:264)(cid:232)
urz(cid:241)dzenia b(cid:241)d(cid:274) mechanizmu. Zadanie polega na znalezieniu najlepszych mo(cid:276)liwych usta-
wie(cid:254), to znaczy takich, które maksymalizuj(cid:241) pewn(cid:241) prost(cid:241) miar(cid:246) sprawno(cid:264)ci urz(cid:241)dzenia.
Zbiór tych ustawie(cid:254) nazwiemy punktem optimum, a docieranie do tego punktu nazwiemy
optymalizacj(cid:241).
Po przybli(cid:276)eniu podstaw dzia(cid:228)ania optymalizacji przejdziemy do zadania zasadniczego, a mia-
nowicie zbudowania prostego systemu (cid:228)amania szyfrów (kodów), w ramach którego rozszy-
frowywanie tekstu b(cid:246)dziemy traktowa(cid:232) jako problem optymalizacji.
Skoro zamierzamy zbudowa(cid:232) w(cid:228)asn(cid:241) funkcj(cid:246) regresji liniowej, wró(cid:232)my do naszego standardowe-
go przyk(cid:228)adowego zbioru danych — wagi i wzrostu. Za(cid:228)o(cid:276)ymy (sprawdzili(cid:264)my to w poprzed-
nich (cid:232)wiczeniach), (cid:276)e b(cid:246)dziemy w stanie przewidzie(cid:232) wag(cid:246) poprzez obliczenie funkcji wagi
od wzrostu. A konkretnie — za(cid:228)o(cid:276)ymy, (cid:276)e taka funkcja b(cid:246)dzie liniowa. W j(cid:246)zyku R wygl(cid:241)-
da(cid:228)aby ona nast(cid:246)puj(cid:241)co:
height.to.weight - function(height, a, b)
{
return(a + b * height)
}
W rozdziale 5. zapoznali(cid:264)my si(cid:246) ze szczegó(cid:228)ami obliczania nachylenia i przesuni(cid:246)cia linii
predykcji za pomoc(cid:241) funkcji lm. W tym przyk(cid:228)adzie nachylenie reprezentuje parametr b, a prze-
suni(cid:246)cie reprezentuje parametr a (mówi on, ile wa(cid:276)y(cid:228)aby osoba o zerowym wzro(cid:264)cie).
175
Poleć książkęKup książkęJak przy tak zadanej funkcji zdecydowa(cid:232) o tym, jakie warto(cid:264)ci a i b b(cid:246)d(cid:241) najodpowiedniejsze?
Tu w(cid:228)a(cid:264)nie zaczyna si(cid:246) problem optymalizacji — zdefiniujemy miar(cid:246) jako(cid:264)ci naszej funkcji
w zadaniu predykcji wagi na podstawie wzrostu, a potem b(cid:246)dziemy zmienia(cid:232) warto(cid:264)ci a i b
dopóty, dopóki nie osi(cid:241)gniemy mo(cid:276)liwie najwy(cid:276)szej skuteczno(cid:264)ci predykcji.
Jak to zrobi(cid:232)? Có(cid:276), robi to ju(cid:276) za nas funkcja lm — optymalizuje ona prost(cid:241) funkcj(cid:246) b(cid:228)(cid:246)du, wyzna-
czaj(cid:241)c w ten sposób najlepsze warto(cid:264)ci a i b za pomoc(cid:241) bardzo specyficznego algorytmu,
dzia(cid:228)aj(cid:241)cego wy(cid:228)(cid:241)cznie dla zwyczajnej regresji liniowej.
Spróbujmy wi(cid:246)c wywo(cid:228)a(cid:232) funkcj(cid:246) lm i podejrze(cid:232) wyznaczone warto(cid:264)ci a i b:
heights.weights - read.csv(file.path( data , 01_heights_weights_genders.csv ))
coef(lm(Weight ~ Height, data = heights.weights))
#(Intercept) Height
#-350.737192 7.717288
Dlaczego w(cid:228)a(cid:264)nie takie warto(cid:264)ci zosta(cid:228)y ustalone dla parametrów a i b? Aby odpowiedzie(cid:232) na
to pytanie, musimy zna(cid:232) funkcj(cid:246) b(cid:228)(cid:246)du u(cid:276)ywan(cid:241) w lm. W rozdziale 5. by(cid:228)a mowa o tym, (cid:276)e lm
wykorzystuje miar(cid:246) b(cid:228)(cid:246)du o nazwie „kwadrat b(cid:228)(cid:246)du”, obliczan(cid:241) nast(cid:246)puj(cid:241)co:
1. Ustal warto(cid:264)ci dla a i b.
2. Dla danej warto(cid:264)ci wzrostu oblicz przewidywan(cid:241) wag(cid:246).
3. Odejmij wag(cid:246) przewidzian(cid:241) od faktycznej — wyst(cid:241)pi b(cid:228)(cid:241)d.
4. Podnie(cid:264) b(cid:228)(cid:241)d do kwadratu.
5. Zsumuj kwadraty b(cid:228)(cid:246)du predykcji ze wszystkich danych wej(cid:264)ciowych.
Do interpretacji w podsumowaniach zazwyczaj bierzemy (cid:264)redni(cid:241), a nie sum(cid:246), i pier-
wiastki, a nie kwadraty. Ale w przypadku optymalizacji nie jest to potrzebne, mo(cid:276)emy
wi(cid:246)c oszcz(cid:246)dzi(cid:232) odrobin(cid:246) mocy obliczeniowej, ograniczaj(cid:241)c si(cid:246) do zliczania sumy
kwadratów b(cid:228)(cid:246)dów.
Ostatnie dwa kroki s(cid:241) ze sob(cid:241) (cid:264)ci(cid:264)le powi(cid:241)zane. Gdyby(cid:264)my nie sumowali b(cid:228)(cid:246)dów, nie trzeba
by ich by(cid:228)o podnosi(cid:232) do kwadratu. Pot(cid:246)gowanie jest tu niezb(cid:246)dne w(cid:228)a(cid:264)nie z powodu sumo-
wania — bez podnoszenia b(cid:228)(cid:246)dów do kwadratu ich suma da(cid:228)aby zero.
Udowodnienie zerowania sumy b(cid:228)(cid:246)dów nie jest trudne, ale wymaga odwo(cid:228)ania si(cid:246)
do algebry, której w tej ksi(cid:241)(cid:276)ce staramy si(cid:246) unika(cid:232).
Zobaczmy, jak mo(cid:276)na zaimplementowa(cid:232) ten algorytm:
squared.error - function(heights.weights, a, b)
{
predictions - with(heights.weights, height.to.weight(Height, a, b))
errors - with(heights.weights, Weight - predictions)
return(sum(errors ^ 2))
}
Obliczmy teraz warto(cid:264)ci funkcji squared.error dla pewnych konkretnych warto(cid:264)ci a i b — zo-
baczymy, jak to dzia(cid:228)a w praktyce (wyniki eksperymentu podsumowuje tabela 7.1):
for (a in seq(-1, 1, by = 1))
{
176
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkę for (b in seq(-1, 1, by = 1))
{
print(squared.error(heights.weights, a, b))
}
}
Tabela 7.1. Kwadraty b(cid:228)(cid:246)du dla parametrów a i b w zakresie –1,1
a
–1
–1
–1
0
0
0
1
1
1
b
–1
0
1
–1
0
1
–1
0
1
Kwadrat b(cid:293)(cid:253)du
536271759
274177183
100471706
531705601
270938376
98560250
527159442
267719569
96668794
Jak wida(cid:232), dla niektórych kombinacji warto(cid:264)ci a i b przyj(cid:246)ta miara b(cid:228)(cid:246)du ma znacznie mniej-
sze warto(cid:264)ci ni(cid:276) dla innych kombinacji. Oznacza to, (cid:276)e nasza funkcja b(cid:228)(cid:246)du faktycznie niesie
jak(cid:241)(cid:264) informacj(cid:246) o jako(cid:264)ci predykcji, i chcemy teraz znale(cid:274)(cid:232) najlepsze warto(cid:264)ci parametrów a i b.
To pierwsza cz(cid:246)(cid:264)(cid:232) zadania optymalizacyjnego — ustalenie miary, któr(cid:241) b(cid:246)dziemy minimali-
zowa(cid:232) albo maksymalizowa(cid:232). Miara ta jest zazwyczaj nazywana funkcj(cid:241) celu (ang. objective
function). Problem optymalizacji staje si(cid:246) wi(cid:246)c problemem znalezienia takich warto(cid:264)ci a i b,
które daj(cid:241) najwi(cid:246)ksz(cid:241) albo najmniejsz(cid:241) warto(cid:264)(cid:232) funkcji celu.
Oczywistym sposobem poszukiwania optymalnych warto(cid:264)ci jest metoda przeszukiwania tzw.
„kraty” (ang. grid search). Nale(cid:276)y wygenerowa(cid:232) krat(cid:246) warto(cid:264)ci a i b podobn(cid:241) do tej z tabeli 7.1 dla
odpowiednio du(cid:276)ego zakresu warto(cid:264)ci a i b, a potem wybra(cid:232) z niej wiersz o najmniejszej
warto(cid:264)ci kwadratu b(cid:228)(cid:246)du. Metoda ta pozwala ka(cid:276)dorazowo znale(cid:274)(cid:232) najlepsze mo(cid:276)liwe warto(cid:264)ci
parametrów, wydaje si(cid:246) wi(cid:246)c odpowiednia. Niestety, ma istotne wady:
(cid:120) Jak dobra(cid:232) zakresy i odleg(cid:228)o(cid:264)ci pomi(cid:246)dzy warto(cid:264)ciami poszczególnych parametrów kra-
ty? Czy a powinno mie(cid:232) warto(cid:264)ci 0, 1, 2 i 3? A mo(cid:276)e odpowiedniejsze b(cid:246)d(cid:241) warto(cid:264)ci 0,
0,001, 0,002 i 0,003? Innymi s(cid:228)owy, jaki zakres i z jak(cid:241) rozdzielczo(cid:264)ci(cid:241) chcemy przeszu-
ka(cid:232)? Odpowied(cid:274) na to pytanie wymaga przeliczenia obu wariantów kraty i sprawdzenia,
która z nich daje wi(cid:246)cej informacji. Ale takie podej(cid:264)cie jest kosztowne obliczeniowo, wi(cid:246)c
zasadniczo wprowadza kolejny problem optymalizacji, sprowadzaj(cid:241)cy si(cid:246) do optymali-
zowania rozmiaru kraty. A tu zaczyna si(cid:246) szale(cid:254)stwo niesko(cid:254)czonej rekurencji.
(cid:120) Je(cid:264)li chcemy przeliczy(cid:232) krat(cid:246) dla 10 warto(cid:264)ci dla ka(cid:276)dego z dwóch parametrów, musimy
zbudowa(cid:232) tabel(cid:246) o 100 elementach. Ale dla 100 parametrów b(cid:246)dzie to ju(cid:276) tabela o roz-
miarze 10100 elementów. Problem wyk(cid:228)adniczego wzrostu z(cid:228)o(cid:276)ono(cid:264)ci obliczeniowej jest
tak powszechny w uczeniu maszynowym, (cid:276)e zyska(cid:228) tu nies(cid:228)awne miano przekle(cid:254)stwa
wielowymiarowo(cid:264)ci.
Poniewa(cid:276) chcemy mie(cid:232) mo(cid:276)liwo(cid:264)(cid:232) u(cid:276)ywania regresji liniowej z setkami, a mo(cid:276)e i tysi(cid:241)cami
wej(cid:264)(cid:232), przeszukiwanie kraty rozumiane jako algorytm optymalizacji uznamy za skre(cid:264)lone.
Jak wi(cid:246)c post(cid:241)pi(cid:232)? Na szcz(cid:246)(cid:264)cie informatycy i matematycy badali problem optymalizacji od
Wprowadzenie do optymalizacji
(cid:95)
177
Poleć książkęKup książkędawna i dopracowali si(cid:246) sporego zbioru algorytmów gotowych do (cid:228)atwego u(cid:276)ycia. W j(cid:246)zyku R
pierwsze podej(cid:264)cie do problemu optymalizacji sprowadza si(cid:246) do u(cid:276)ycia funkcji optim, b(cid:246)d(cid:241)cej
czarn(cid:241) skrzynk(cid:241) implementuj(cid:241)c(cid:241) wiele popularnych algorytmów optymalizacji.
Aby zademonstrowa(cid:232) dzia(cid:228)anie funkcji optim, spróbujemy wykorzysta(cid:232) j(cid:241) do dopasowania
naszego modelu regresji liniowej — z nie(cid:264)mia(cid:228)(cid:241) nadziej(cid:241), (cid:276)e otrzymane wyniki b(cid:246)d(cid:241) podobne
do wyników uzyskanych z funkcji lm:
optim(c(0, 0),
function (x)
{
squared.error(heights.weights, x[1], x[2])
})
#$par
#[1] -350.786736 7.718158
#
#$value
#[1] 1492936
#
#$counts
#function gradient
# 111 NA
#
#$convergence
#[1] 0
#
#$message
#NULL
Zgodnie z przytoczonym przyk(cid:228)adem funkcja optim przyjmuje kilka ró(cid:276)nych parametrów. Jako
pierwszy nale(cid:276)y przekaza(cid:232) wektor liczbowy punktów startowych dla optymalizowanych pa-
rametrów. W tym przypadku mówimy, (cid:276)e pocz(cid:241)tkowe warto(cid:264)ci parametrów a i b odpowiadaj(cid:241)
wektorowi c(0,0). Kolejnym parametrem funkcji optim powinna by(cid:232) funkcja przyjmuj(cid:241)ca wektor
(u nas nazywany x) zawieraj(cid:241)cy komplet parametrów do zoptymalizowania. Poniewa(cid:276) nasza
funkcja celu przyjmuje dwa parametry, ujmujemy jej wywo(cid:228)anie w funkcji anonimowej
przyjmuj(cid:241)cej wektor x i wy(cid:228)uskuj(cid:241)cej z niego parametry dla wywo(cid:228)ania w(cid:228)a(cid:264)ciwej funkcji celu
— squared.error.
Wykonanie powy(cid:276)szego wywo(cid:228)ania funkcji optim zwraca warto(cid:264)ci dla parametrów a b jako
warto(cid:264)ci kolumny par. Jak wida(cid:232), warto(cid:264)ci te s(cid:241) bardzo bliskie warto(cid:264)ciom obliczanym przez
lm, co sugeruje, (cid:276)e funkcja optim faktycznie dzia(cid:228)a1. W praktyce lm u(cid:276)ywa algorytmu optyma-
lizacji mocno specjalizowanego dla regresji liniowej, dzi(cid:246)ki czemu otrzymuje wyniki precyzyjniej-
sze ni(cid:276) wyniki z optymalizacji funkcj(cid:241) optim. Za to funkcja optim dobrze sprawdza si(cid:246) we w(cid:228)a-
snych implementacjach, bo nadaje si(cid:246) do stosowania równie(cid:276) w modelach innych ni(cid:276) regresja
liniowa.
Pozosta(cid:228)e warto(cid:264)ci wyliczane przez optim s(cid:241) najcz(cid:246)(cid:264)ciej mniej interesuj(cid:241)ce. Pierwsza z nich to
value, reprezentuj(cid:241)ca warto(cid:264)(cid:232) funkcji celu (kwadratu b(cid:228)(cid:246)du) dla zoptymalizowanych warto(cid:264)ci
parametrów. Dalej mamy counts, czyli licznik wykona(cid:254) g(cid:228)ównej funkcji (function), oraz gra-
dient (gradient), b(cid:246)d(cid:241)cy opcjonalnym argumentem optymalizacji do stosowania, kiedy zna si(cid:246)
matematyk(cid:246) wystarczaj(cid:241)co dobrze, aby obliczy(cid:232) gradient funkcji g(cid:228)ównej.
1 A przynajmniej, (cid:276)e dzia(cid:228)a tak samo dobrze (albo tak samo (cid:274)le) jak lm.
178
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkęNie przejmujmy si(cid:246), je(cid:264)li poj(cid:246)cie gradientu jest nam zupe(cid:228)nie obce. R(cid:246)czne obliczanie
gradientów jest (cid:276)mudne, wi(cid:246)c zazwyczaj zdajemy si(cid:246) na funkcj(cid:246) optim bez dookre-
(cid:264)lania opcjonalnej warto(cid:264)ci gradientu. Jak dot(cid:241)d, ta strusia strategia sprawdza(cid:228)a si(cid:246)
nie najgorzej.
Nast(cid:246)pna warto(cid:264)(cid:232) to konwergencja (convergence), mówi(cid:241)ca o tym, czy funkcja optim ma pew-
no(cid:264)(cid:232), (cid:276)e znalaz(cid:228)a faktycznie najlepszy mo(cid:276)liwy zestaw parametrów. Je(cid:264)li wszystko posz(cid:228)o
dobrze, warto(cid:264)(cid:232) ta b(cid:246)dzie równa 0. Je(cid:264)li konwergencja jest ró(cid:276)na od zera, nale(cid:276)y sprawdzi(cid:232)
przyczyn(cid:246) niepe(cid:228)nej optymalizacji w dokumentacji funkcji optim — convergence b(cid:246)dzie wtedy
kodem b(cid:228)(cid:246)du. Wreszcie warto(cid:264)(cid:232) message zawiera komunikat z ewentualnymi dodatkowymi
istotnymi informacjami o przebiegu optymalizacji.
Zasadniczo funkcja optim implementuje wiele sprytnych pomys(cid:228)ów obliczeniowych, pozwa-
laj(cid:241)cych na przeprowadzenie optymalizacji. Poniewa(cid:276) matematycznie jest ona do(cid:264)(cid:232) zaawan-
sowana, nie b(cid:246)dziemy zag(cid:228)(cid:246)bia(cid:232) si(cid:246) w tajniki jej wewn(cid:246)trznego dzia(cid:228)ania. Natomiast ogólna
zasada dzia(cid:228)ania funkcji optim daje si(cid:246) bardzo (cid:228)atwo zilustrowa(cid:232) graficznie. Wyobra(cid:274)my so-
bie, (cid:276)e chcemy znale(cid:274)(cid:232) najlepsz(cid:241) warto(cid:264)(cid:232) a przy b ustalonym na 0. Kwadrat b(cid:228)(cid:246)du dla wy-
izolowanej zmiennej a mo(cid:276)na wtedy obliczy(cid:232) nast(cid:246)puj(cid:241)co:
a.error - function(a)
{
return(squared.error(heights.weights, a, 0))
}
Wykres kwadratu b(cid:228)(cid:246)du w zale(cid:276)no(cid:264)ci od warto(cid:264)ci a pozwala (cid:228)atwo znale(cid:274)(cid:232) miejsce najlepszej
warto(cid:264)ci a; wystarczy u(cid:276)y(cid:232) funkcji curve j(cid:246)zyka R, która obliczy funkcj(cid:246) albo wyra(cid:276)enie dla
wielu warto(cid:264)ci zmiennej, a potem wyrysuje wyniki. W poni(cid:276)szym przyk(cid:228)adzie szacujemy
a.error dla wielu warto(cid:264)ci x. Z powodu zawi(cid:228)o(cid:264)ci obliczania warto(cid:264)ci wyra(cid:276)e(cid:254) w j(cid:246)zyku R
musimy wykorzysta(cid:232) do tego funkcj(cid:246) sapply:
curve(sapply(x, function (a) {a.error(a)}), from = -1000, to = 1000)
Na rysunku 7.1 mo(cid:276)na wskaza(cid:232) miejsce, w którym warto(cid:264)(cid:232) a jest optymalna z punktu widze-
nia funkcji celu. W miar(cid:246) oddalania si(cid:246) od tego miejsca b(cid:228)(cid:241)d ro(cid:264)nie. W takim przypadku
mówimy o istnieniu globalnego optimum. Funkcja optim na podstawie kszta(cid:228)tu funkcji celu
mo(cid:276)e wówczas ustali(cid:232), w którym kierunku przesuwa(cid:232) sprawdzian po obliczeniu funkcji celu
dla jednej warto(cid:264)ci a. U(cid:276)ycie lokalnej informacji do pozyskania wiedzy o globalnej strukturze
problemu pozwala funkcji optim bardzo szybko znale(cid:274)(cid:232) punkt optimum.
Aby odnie(cid:264)(cid:232) to do pe(cid:228)nego problemu regresji, powinni(cid:264)my równie(cid:276) zbada(cid:232) zmienno(cid:264)(cid:232) funkcji
kwadratu b(cid:228)(cid:246)du w zale(cid:276)no(cid:264)ci od zmian parametru b (patrz rysunek 7.2):
b.error - function(b)
{
return(squared.error(heights.weights, 0, b))
}
curve(sapply(x, function (b) {b.error(b)}), from = -1000, to = 1000)
Wprowadzenie do optymalizacji
(cid:95)
179
Poleć książkęKup książkęRysunek 7.1. kwadrat b(cid:228)(cid:246)du dla ró(cid:276)nych warto(cid:264)ci a
Rysunek 7.2. Kwadrat b(cid:228)(cid:246)du dla ró(cid:276)nych warto(cid:264)ci b
180
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkęZ rysunku 7.2 wiemy, (cid:276)e dla parametru b funkcja b(cid:228)(cid:246)du równie(cid:276) posiada globalne optimum.
Skoro istnieje lokalne optimum dla parametrów a i b rozpatrywanych osobno, wydaje si(cid:246), (cid:276)e
funkcja optim powinna poradzi(cid:232) sobie ze znalezieniem jednego zestawu warto(cid:264)ci a i b, dla
których funkcja b(cid:228)(cid:246)du ma najmniejsz(cid:241) warto(cid:264)(cid:232).
Ogólniej mo(cid:276)na powiedzie(cid:232), (cid:276)e funkcja optim dzia(cid:228)a, poniewa(cid:276) mo(cid:276)e przeszukiwa(cid:232) przestrze(cid:254)
funkcji b(cid:228)(cid:246)du dla wszystkich parametrów naraz. Dzia(cid:228)a szybciej ni(cid:276) przeszukiwanie kraty, bo
wykorzystuje informacje o obecnie rozwa(cid:276)anym punkcie do wnioskowania o punktach s(cid:241)-
siednich, co pozwala na podj(cid:246)cie decyzji o kierunku dalszych poszukiwa(cid:254). Ta jej zdolno(cid:264)(cid:232) do
adaptacji sprawia, (cid:276)e jest znacznie wydajniejsza od (cid:228)opatologicznego przeszukiwania kraty
kombinacji parametrów.
Regresja grzbietowa
Skoro wiemy ju(cid:276), jak u(cid:276)ywa(cid:232) funkcji optim, mo(cid:276)emy przyst(cid:241)pi(cid:232) do stosowania algorytmów
optymalizacji do implementowania w(cid:228)asnej wersji regresji grzbietowej. Regresja grzbietowa (ang.
ridge regression) to specyficzna forma regresji ujmuj(cid:241)ca regularyzacj(cid:246) omawian(cid:241) w rozdziale 6.
Ró(cid:276)nica pomi(cid:246)dzy klasyczn(cid:241) regresj(cid:241) najmniejszych kwadratów a regresj(cid:241) grzbietow(cid:241) sprowa-
dza si(cid:246) do u(cid:276)ytej funkcji b(cid:228)(cid:246)du — regresja grzbietowa d(cid:241)(cid:276)y do zmniejszania wspó(cid:228)czynników,
uwzgl(cid:246)dniaj(cid:241)c ich warto(cid:264)ci przy okre(cid:264)laniu b(cid:228)(cid:246)du. W tym przyk(cid:228)adzie spowoduje to spychanie
warto(cid:264)ci przesuni(cid:246)cia i nachylenia w kierunku zera.
Poza zmian(cid:241) funkcji b(cid:228)(cid:246)du regresja grzbietowa wprowadza te(cid:276) narzut z(cid:228)o(cid:276)ono(cid:264)ci obliczeniowej,
wprowadzaj(cid:241)c dodatkowy parametr — lambda — balansuj(cid:241)cy wag(cid:246) przyk(cid:228)adan(cid:241) do minima-
lizowania kwadratu b(cid:228)(cid:246)du i wag(cid:246) przyk(cid:228)adan(cid:241) do minimalizowania warto(cid:264)ci a i b (co pozwala na
unikni(cid:246)cie nadmiernego dopasowania). Dodatkowy parametr tego regularyzowanego algo-
rytmu nosi nazw(cid:246) hiperparametru, omawianego ju(cid:276) w pewnym zakresie w rozdziale 6. Dla
ustalonej warto(cid:264)ci lambda funkcj(cid:246) b(cid:228)(cid:246)du regresji grzbietowej mo(cid:276)emy zapisa(cid:232) nast(cid:246)puj(cid:241)co:
ridge.error - function(heights.weights, a, b, lambda)
{
predictions - with(heights.weights, height.to.weight(Height, a, b))
errors - with(heights.weights, Weight - predictions)
return(sum(errors ^ 2) + lambda * (a ^ 2 + b ^ 2))
}
Zgodnie z omówieniem z rozdzia(cid:228)u 6., warto(cid:264)(cid:232) lambdy dobiera si(cid:246) za pomoc(cid:241) sprawdzianu
krzy(cid:276)owego. Na potrzeby tego rozdzia(cid:228)u za(cid:228)o(cid:276)ymy po prostu, (cid:276)e sprawdzian ten zosta(cid:228) ju(cid:276)
przeprowadzony i odpowiedni(cid:241) warto(cid:264)ci(cid:241) parametru lambda b(cid:246)dzie 1.
Po zdefiniowaniu funkcji b(cid:228)(cid:246)du regresji grzbietowej jako funkcji j(cid:246)zyka R rozwi(cid:241)zanie zadania
regresji grzbietowej sprowadza si(cid:246) znów do wywo(cid:228)ania optim — równie (cid:228)atwo, jak w przypadku
regresji z kwadratem b(cid:228)(cid:246)du:
lambda - 1
optim(c(0, 0),
function (x)
{
ridge.error(heights.weights, x[1], x[2], lambda)
})
#$par
#[1] -340.434108 7.562524
#
Regresja grzbietowa
(cid:95)
181
Poleć książkęKup książkę#$value
#[1] 1612443
#
#$counts
#function gradient
# 115 NA
#
#$convergence
#[1] 0
#
#$message
#NULL
Wynik funkcji optim pokazuje, (cid:276)e mo(cid:276)emy w ten sposób wygenerowa(cid:232) nieco mniejsze przesuni(cid:246)-
cie i nachylenie ni(cid:276) w przypadku regresji liniowej funkcj(cid:241) lm, gdzie przesuni(cid:246)cie wynosi(cid:228)o –350,
a nachylenie 7,7. W tym uproszczonym przyk(cid:228)adzie nie jest to szczególnie przydatne, ale w regre-
sjach o wi(cid:246)kszej skali, takich jak regresje z rozdzia(cid:228)u 6., penalizowanie du(cid:276)ych warto(cid:264)ci wspó(cid:228)-
czynników okaza(cid:228)o si(cid:246) zbawienne dla jako(cid:264)ci algorytmu.
Oprócz ogl(cid:241)dania dopasowanych wspó(cid:228)czynników regresji mo(cid:276)emy te(cid:276) powtórzy(cid:232) wywo(cid:228)ania
funkcji curve w celu sprawdzenia, dlaczego funkcja optim radzi sobie z regresj(cid:241) grzbietow(cid:241)
równie dobrze, jak ze zwyczajn(cid:241) regresj(cid:241) liniow(cid:241). Odpowiednie wykresy prezentowane s(cid:241) na
rysunkach 7.3 i 7.4.
Rysunek 7.3. B(cid:228)(cid:241)d regresji grzbietowej przy zmianach parametru a
182
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkęRysunek 7.4. B(cid:228)(cid:241)d regresji grzbietowej przy zmianach parametru b
a.ridge.error - function(a, lambda)
{
return(ridge.error(heights.weights, a, 0, lambda))
}
curve(sapply(x, function (a) {a.ridge.error(a, lambda)}), from = -1000, to = 1000)
b.ridge.error - function(b, lambda)
{
return(ridge.error(heights.weights, 0, b, lambda))
}
curve(sapply(x, function (b) {b.ridge.error(b, lambda)}), from = -1000, to = 1000)
Przyk(cid:228)ad ten pokazuje, (cid:276)e w uczeniu maszynowym mo(cid:276)emy wiele zdzia(cid:228)a(cid:232) sam(cid:241) tylko umiej(cid:246)t-
no(cid:264)ci(cid:241) stosowania funkcji takich jak optim w celu minimalizowania pewnej miary b(cid:228)(cid:246)du predykcji.
Zalecamy samodzielne przepracowanie kilku przyk(cid:228)adów i eksperymentowanie z ró(cid:276)nymi w(cid:228)a-
snymi funkcjami b(cid:228)(cid:246)du. Umiej(cid:246)tno(cid:264)(cid:232) pos(cid:228)ugiwania si(cid:246) funkcj(cid:241) optim i interpretowania jej wyników
jest przydatna zw(cid:228)aszcza przy testowaniu funkcji warto(cid:264)ci bezwzgl(cid:246)dnej b(cid:228)(cid:246)du, jak tutaj:
absolute.error - function (heights.weights, a, b)
{
predictions - with(heights.weights, height.to.weight(Height, a, b))
errors - with(heights.weights, Weight - predictions)
return(sum(abs(errors)))
}
Regresja grzbietowa
(cid:95)
183
Poleć książkęKup książkęZ uwagi na techniczne aspekty rachunku ró(cid:276)niczkowego taka miara b(cid:228)(cid:246)du nie da dobrych wyni-
ków z funkcj(cid:241) optim. Wyja(cid:264)nienie tego bez wykonywania zaawansowanych oblicze(cid:254) jest nieco
utrudnione, ale da si(cid:246) to wyt(cid:228)umaczy(cid:232) na podstawie wizualizacji. Powtórzmy wi(cid:246)c wywo(cid:228)anie
funkcji rysuj(cid:241)cej wykres:
a.absolute.error - function(a)
{
return(absolute.error(heights.weights, a, 0))
}
curve(sapply(x, function (a) {a.absolute.error(a)}), from = -1000, to = 1000)
Na rysunku 7.5 widzimy znacznie ostrzejszy przebieg krzywej b(cid:228)(cid:246)du bezwzgl(cid:246)dnego w porów-
naniu z kwadratem b(cid:228)(cid:246)du i b(cid:228)(cid:246)dem regresji grzbietowej. Poniewa(cid:276) kszta(cid:228)t krzywej jest tak ostry,
funkcja optim nie uzyskuje wystarczaj(cid:241)cej ilo(cid:264)ci informacji o po(cid:276)(cid:241)danym kierunku dalszych
poszukiwa(cid:254) i niekoniecznie dotrze do globalnego optimum, mimo (cid:276)e na wykresie punkt opti-
mum wida(cid:232) jak na d(cid:228)oni.
Rysunek 7.5. B(cid:228)(cid:241)d bezwzgl(cid:246)dny przy zmianach parametru a
Skoro niektóre typy miar b(cid:228)(cid:246)du za(cid:228)amuj(cid:241) skuteczno(cid:264)(cid:232) nawet zaawansowanych algorytmów,
elementem sztuki uczenia maszynowego jest poznanie warunków skutecznego dzia(cid:228)ania narz(cid:246)-
dzi takich jak funkcja optim i rozpoznawanie sytuacji, w których te prostsze narz(cid:246)dzia przestaj(cid:241)
wystarcza(cid:232). Istniej(cid:241) przecie(cid:276) algorytmy dzia(cid:228)aj(cid:241)ce równie(cid:276) w przypadku optymalizacji z b(cid:228)(cid:246)dem
bezwzgl(cid:246)dnym, cho(cid:232) ich omawianie wykracza poza zakres tej ksi(cid:241)(cid:276)ki — zainteresowanych
Czytelników pozostaje odes(cid:228)a(cid:232) do lokalnego guru matematyki, aby pogaw(cid:246)dzili o optymali-
zacji wypuk(cid:228)ej (ang. convex optimization).
184
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkę(cid:292)amanie szyfrów jako problem optymalizacji
Wychodz(cid:241)c poza modele regresji, praktycznie ka(cid:276)dy algorytm w uczeniu maszynowym mo(cid:276)na
postrzega(cid:232) jako problem optymalizacji, w ramach którego chcemy zminimalizowa(cid:232) pewn(cid:241)
miar(cid:246) b(cid:228)(cid:246)du predykcji. Ale niekiedy nasze parametry nie s(cid:241) prostymi liczbami, przez co oblicze-
nie funkcji b(cid:228)(cid:246)du w jednym punkcie danych nie daje wystarczaj(cid:241)cej informacji o punktach s(cid:241)-
siednich, aby skutecznie u(cid:276)y(cid:232) funkcji optim. W przypadku takich problemów mo(cid:276)emy uciec
si(cid:246) do przeszukiwania kraty, ale s(cid:241) te(cid:276) inne, efektywniejsze techniki. Skupimy si(cid:246) tu na jednej
z nich, szczególnie intuicyjnej i do(cid:264)(cid:232) efektywnej. Koncepcja stoj(cid:241)ca za tym nowym podej(cid:264)ciem,
które b(cid:246)dziemy nazywa(cid:232) optymalizacj(cid:241) stochastyczn(cid:241), polega na przej(cid:264)ciu przez zakres mo(cid:276)li-
wych parametrów w pewien sposób losowo, ale z zapewnieniem utrzymywania kierunku, w któ-
rym funkcja b(cid:228)(cid:246)du raczej maleje, ni(cid:276) wzrasta. Podej(cid:264)cie to jest zwi(cid:241)zane z wieloma popularnymi
algorytmami optymalizacji, z symulowanym wy(cid:276)arzaniem (ang. simulated annealing), algorytma-
mi genetycznymi i markowowskim Monte Carlo (MCMC, od ang. Markov Chain Monte Carlo) na
czele. Konkretny algorytm, którego u(cid:276)yjemy, nosi miano metody Metropolis. Rozmaite wersje tej
metody stanowi(cid:241) podstawy wielu wspó(cid:228)czesnych algorytmów uczenia maszynowego.
Aby zilustrowa(cid:232) metod(cid:246) Metropolis, jako studium przypadku dla tego rozdzia(cid:228)u wybrali(cid:264)my
problem (cid:228)amania tajnych szyfrów. Algorytm, który b(cid:246)dziemy tu definiowa(cid:232), nie jest bynajm-
niej szczególnie efektywnym systemem deszyfruj(cid:241)cym i nie móg(cid:228)by by(cid:232) brany na powa(cid:276)nie
w rozwi(cid:241)zaniach produkcyjnych, ale stanowi dobitny przyk(cid:228)ad zastosowania metody Metropolis.
Co wa(cid:276)ne, jest to te(cid:276) przyk(cid:228)ad problemu, z którym gotowe algorytmy optymalizacji w rodzaju
funkcji optim w ogóle sobie nie radz(cid:241).
Okre(cid:264)lmy wi(cid:246)c zadanie — dla danego ci(cid:241)gu liter, o którym wiemy, (cid:276)e jest szyfrogramem wytwo-
rzonym przez szyfr podstawieniowy, nale(cid:276)y zdecydowa(cid:232) o przyj(cid:246)ciu regu(cid:228)y deszyfruj(cid:241)cej,
pozwalaj(cid:241)cej na odtworzenie jawnego tekstu. Dla osób nieznaj(cid:241)cych szyfrów podstawienio-
wych wypada przypomnie(cid:232), (cid:276)e s(cid:241) to najprostsze mo(cid:276)liwe systemy szyfrowania, w których
ka(cid:276)da litera jawnego tekstu jest zamieniana na odpowiadaj(cid:241)c(cid:241) jej liter(cid:246) szyfrogramu (zawsze
tak(cid:241) sam(cid:241)). Chyba najbardziej znanym przyk(cid:228)adem takiego szyfru jest ROT132; innym s(cid:228)yn-
nym szyfrem z tej rodziny jest szyfr Cezara. W szyfrze Cezara ka(cid:276)da litera jest zamieniana na
nast(cid:246)pn(cid:241) liter(cid:246) alfabetu: „a” zamienia si(cid:246) na „b”, „b” na „c”, a „c” na „d” (w przypadku brzego-
wym: „z” zamienia si(cid:246) na „a”).
Aby prze(cid:232)wiczy(cid:232) stosowanie prostych szyfrów w R, napiszemy w tym j(cid:246)zyku implementacj(cid:246) szy-
fru Cezara:
english.letters - c( a , b , c , d , e , f , g , h , i , j , k ,
l , m , n , o , p , q , r , s , t , u , v ,
w , x , y , z )
caesar.cipher - list()
inverse.caesar.cipher - list()
for (index in 1:length(english.letters))
{
caesar.cipher[[english.letters[index]]] - english.letters[index 26 + 1]
inverse.caesar.cipher[[english.letters[index 26 + 1]]] - english.letters[index]
}
print(caesar.cipher)
2 Szyfr ROT13 zamienia ka(cid:276)d(cid:241) liter(cid:246) na liter(cid:246) odleg(cid:228)(cid:241) o 13 pozycji w alfabecie: „a” zamienia si(cid:246) na „n”, „b”
na „o” itd.
(cid:292)amanie szyfrów jako problem optymalizacji
(cid:95)
185
Poleć książkęKup książkęPo zaimplementowaniu szyfru mo(cid:276)emy przyst(cid:241)pi(cid:232) do programowania funkcji pomocniczych,
które pozwol(cid:241) na zaszyfrowanie ci(cid:241)gu znaków za pomoc(cid:241) przekazanego szyfru:
apply.cipher.to.string - function(string, cipher)
{
output -
for (i in 1:nchar(string))
{
output - paste(output, cipher[[substr(string, i, i)]], sep = )
}
return(output)
}
apply.cipher.to.text - function(text, cipher)
{
output - c()
for (string in text)
{
output - c(output, apply.cipher.to.string(string, cipher))
}
return(output)
}
apply.cipher.to.text(c( sample , text ), caesar.cipher)
Wypracowali(cid:264)my sobie podstawowe narz(cid:246)dzia do pracy z szyframi, mo(cid:276)emy wi(cid:246)c zacz(cid:241)(cid:232) za-
stanawia(cid:232) si(cid:246) nad problemem (cid:228)amania szyfrów. Podobnie jak w regresji liniowej, problem
z(cid:228)amania podstawienia szyfruj(cid:241)cego b(cid:246)dziemy rozwi(cid:241)zywa(cid:232) etapami:
1. Zdefiniuj miar(cid:246) jako(cid:264)ci proponowanej regu(cid:228)y deszyfruj(cid:241)cej.
2. Zdefiniuj algorytm proponowania nowych potencjalnych regu(cid:228) deszyfruj(cid:241)cych, który lo-
sowo modyfikuje warianty obecnie najlepszej regu(cid:228)y.
3. Zdefiniuj algorytm przesuwania si(cid:246) w kierunku coraz lepszych regu(cid:228) deszyfruj(cid:241)cych.
W ramach przymiarki do mierzenia jako(cid:264)ci regu(cid:228)y deszyfruj(cid:241)cej za(cid:228)ó(cid:276)my, (cid:276)e mamy dany frag-
ment tekstu, o którym wiemy, (cid:276)e zosta(cid:228) zaszyfrowany za pomoc(cid:241) szyfru podstawieniowego.
Na przyk(cid:228)ad sam Juliusz Cezar przys(cid:228)a(cid:228) nam wiadomo(cid:264)(cid:232) o tre(cid:264)ci „wfoj wjej wjdj”. Po odwró-
ceniu szyfru Cezara tekst ten zamieni si(cid:246) w s(cid:228)ynne zdanie „veni vidi vici”.
Wyobra(cid:274)my sobie, (cid:276)e mamy do dyspozycji troch(cid:246) zaszyfrowanego tekstu i zapewnienie, (cid:276)e
tekst jawny szyfrogramu by(cid:228) tekstem w j(cid:246)zyku angielskim. Jak podeszliby(cid:264)my do z(cid:228)amania
szyfrogramu? Otó(cid:276) powiedzieliby(cid:264)my, (cid:276)e regu(cid:228)a deszyfruj(cid:241)ca jest dobra, je(cid:264)li zamienia szy-
frogram na tekst w j(cid:246)zyku angielskim. Dla proponowanej regu(cid:228)y deszyfruj(cid:241)cej nale(cid:276)a(cid:228)oby za-
stosowa(cid:232) j(cid:241) do szyfrogramu i sprawdzi(cid:232), czy otrzymany tekst jest faktycznie tekstem w j(cid:246)zy-
ku angielskim. Na przyk(cid:228)ad dane s(cid:241) dwie proponowane regu(cid:228)y deszyfruj(cid:241)ce A i B, które daj(cid:241)
nast(cid:246)puj(cid:241)ce wyniki:
(cid:120) decrypt(T, A) = xgpk xkfk xkek
(cid:120) decrypt(T, B) = veni vidi vici
Po obejrzeniu wyników zastosowania obu proponowanych regu(cid:228) wydaje si(cid:246) oczywiste, (cid:276)e
regu(cid:228)a B jest lepsza ni(cid:276) regu(cid:228)a A. Jak doszli(cid:264)my do tego intuicyjnego wniosku? Widzimy, (cid:276)e
regu(cid:228)a B jest lepsza od A, bo tekst wynikowy z zastosowania regu(cid:228)y B przypomina prawdzi-
wy j(cid:246)zyk, podczas gdy wynik zastosowania regu(cid:228)y A wygl(cid:241)da jak kompletny be(cid:228)kot. Aby
prze(cid:228)o(cid:276)y(cid:232) ludzk(cid:241) intuicj(cid:246) na co(cid:264) automatycznego, co da si(cid:246) zaprogramowa(cid:232) na komputerze,
186
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkęb(cid:246)dziemy musieli skorzysta(cid:232) z leksykalnej bazy danych, okre(cid:264)laj(cid:241)cej prawdopodobie(cid:254)stwo
wyst(cid:246)powania poszczególnych s(cid:228)ów. Jako prawdziwy j(cid:246)zyk wytypujemy wtedy taki tekst, który
b(cid:246)dzie si(cid:246) sk(cid:228)ada(cid:228) z wyrazów maj(cid:241)cych wysokie prawdopodobie(cid:254)stwo wyst(cid:246)powania. Be(cid:228)kot
by(cid:228)by tu odpowiednikiem tekstu, który sk(cid:228)ada si(cid:246) ze s(cid:228)ów o niskim prawdopodobie(cid:254)stwie
wyst(cid:246)powania. Jedyna trudno(cid:264)(cid:232) w tym modelu polega na radzeniu sobie ze s(cid:228)owami, które
w ogóle nie istniej(cid:241). Poniewa(cid:276) prawdopodobie(cid:254)stwo ich wyst(cid:241)pienia wynosi zero, a praw-
dopodobie(cid:254)stwo przynale(cid:276)no(cid:264)ci ca(cid:228)ego tekstu do prawdziwego j(cid:246)zyka b(cid:246)dziemy ocenia(cid:232) jako
iloczyn prawdopodobie(cid:254)stwa wyst(cid:241)pienia poszczególnych s(cid:228)ów, powinni(cid:264)my zast(cid:241)pi(cid:232) zero
jak(cid:241)(cid:264) bardzo ma(cid:228)(cid:241) warto(cid:264)ci(cid:241) — na przyk(cid:228)ad minimaln(cid:241) warto(cid:264)ci(cid:241) zmiennoprzecinkow(cid:241), któ-
r(cid:241) nazwiemy epsilon. Gdy za(cid:228)atwimy w ten sposób przypadki brzegowe, mo(cid:276)emy u(cid:276)y(cid:232) leksykal-
nej bazy danych do u(cid:228)o(cid:276)enia rankingu jako(cid:264)ci dwóch rozszyfrowanych tekstów poprzez wyzna-
czenie prawdopodobie(cid:254)stwa wyst(cid:241)pienia ka(cid:276)dego ze s(cid:228)ów i przez wyznaczenie iloczynu tych
prawdopodobie(cid:254)stw jako (cid:228)(cid:241)cznego prawdopodobie(cid:254)stwa przynale(cid:276)no(cid:264)ci tekstu do j(cid:246)zyka.
Zastosowanie leksykalnej bazy danych do obliczania prawdopodobie(cid:254)stwa wyst(cid:241)pienia od-
szyfrowanego tekstu b(cid:246)dzie nasz(cid:241) miar(cid:241) b(cid:228)(cid:246)du przy ocenianiu proponowanej regu(cid:228)y deszy-
fruj(cid:241)cej. A skoro mamy ju(cid:276) pomys(cid:228) na funkcj(cid:246) b(cid:228)(cid:246)du, nasz problem faktycznie przekszta(cid:228)ca
si(cid:246) ca(cid:228)kowicie w problem optymalizacji. Teraz wystarczy wi(cid:246)c znale(cid:274)(cid:232) regu(cid:228)y deszyfruj(cid:241)ce,
generuj(cid:241)ce teksty o wysokim prawdopodobie(cid:254)stwie wyst(cid:241)pienia w za(cid:228)o(cid:276)onym j(cid:246)zyku.
Niestety, zadanie wyszukiwania regu(cid:228) o najwy(cid:276)szym prawdopodobie(cid:254)stwie wyst(cid:241)pienia
tekstu nie jest nawet w przybli(cid:276)eniu zadaniem, z którym poradzi sobie funkcja optim. Z regu(cid:228)
deszyfruj(cid:241)cych nie da si(cid:246) zrobi(cid:232) wykresu; nie maj(cid:241) te(cid:276) g(cid:228)adko(cid:264)ci potrzebnej funkcji optim do
okre(cid:264)lania kierunku poszukiwa(cid:254) coraz lepszych regu(cid:228). Potrzebujemy wi(cid:246)c zupe(cid:228)nie innego algo-
rytmu optymalizacji. B(cid:246)dzie nim zapowiadana ju(cid:276) metoda Metropolis. Algorytm ten powinien si(cid:246)
do(cid:264)(cid:232) dobrze sprawia(cid:232) w naszym problemie, chocia(cid:276) jest algorytmem powolnym (przynajmniej
dla jakichkolwiek d(cid:228)u(cid:276)szych tekstów)3.
Podstawowa koncepcja metody Metropolis polega na tym, (cid:276)e zaczynamy od arbitralnie przyj(cid:246)tej
regu(cid:228)y deszyfruj(cid:241)cej i potem iteracyjnie próbujemy j(cid:241) polepsza(cid:232) — do momentu, w którym uzna-
my, (cid:276)e to mo(cid:276)e by(cid:232) w(cid:228)a(cid:264)ciwa regu(cid:228)a. Wydaje si(cid:246), (cid:276)e brzmi to nieco magicznie, ale w praktyce
cz(cid:246)sto dzia(cid:228)a zupe(cid:228)nie dobrze, o czym przekonamy si(cid:246) do(cid:264)wiadczalnie. A po uzyskaniu stosun-
kowo dobrej regu(cid:228)y deszyfruj(cid:241)cej mo(cid:276)emy odwo(cid:228)a(cid:232) si(cid:246) do w(cid:228)asnej intuicji w oparciu o ocen(cid:246)
spójno(cid:264)ci znaczeniowej i gramatycznej i w ten sposób ostatecznie zdecydowa(cid:232), czy tekst zosta(cid:228)
poprawnie odszyfrowany.
Aby wygenerowa(cid:232) dobr(cid:241) regu(cid:228)(cid:246) deszyfruj(cid:241)c(cid:241), zaczniemy od zupe(cid:228)nie dowolnej regu(cid:228)y, a potem
b(cid:246)dziemy wielokrotnie — powiedzmy, 50 000 razy — powtarza(cid:232) pojedyncz(cid:241) operacj(cid:246) polep-
szaj(cid:241)c(cid:241) t(cid:246) regu(cid:228)(cid:246). Poniewa(cid:276) ka(cid:276)dy krok iteracji b(cid:246)dzie wykonywany w kierunku coraz lep-
szych regu(cid:228), uparte powtarzanie tej operacji powinno wreszcie doprowadzi(cid:232) do sensownych
wyników. Nie ma tylko gwarancji, (cid:276)e ca(cid:228)o(cid:264)(cid:232) zamknie si(cid:246) w 50 000 iteracji, a nie na przyk(cid:228)ad
w 50 000 000. Dlatego w(cid:228)a(cid:264)nie nie zastosowaliby(cid:264)my tego algorytmu do (cid:228)amania szyfrów na
powa(cid:276)nie — nie mamy gwarancji, (cid:276)e algorytm dostarczy rozwi(cid:241)zanie w sko(cid:254)czonym i rozs(cid:241)d-
nym czasie, a oczekuj(cid:241)c na zako(cid:254)czenie, trudno cz(cid:246)sto stwierdzi(cid:232), czy ca(cid:228)o(cid:264)(cid:232) posuwa si(cid:246) aby
ku lepszemu. To studium przypadku mo(cid:276)na wi(cid:246)c uzna(cid:232) za (cid:232)wiczenie czysto dydaktyczne.
Jedynym jego za(cid:228)o(cid:276)eniem jest pokazanie zastosowania algorytmów optymalizacji do skom-
plikowanych zada(cid:254), które z pozoru s(cid:241) problemami zupe(cid:228)nie innej klasy.
3 Jego powolno(cid:264)(cid:232) jest silnie uwypuklona przez nieefektywno(cid:264)(cid:232) dost(cid:246)pnych w R narz(cid:246)dzi do przetwarzania
tekstu, nieporównanie wolniejszych od podobnych narz(cid:246)dzi na przyk(cid:228)ad w j(cid:246)zyku Perl.
(cid:292)amanie szyfrów jako problem optymalizacji
(cid:95)
187
Poleć książkęKup książkęSkonkretyzujmy sposób proponowania nowej regu(cid:228)y deszyfruj(cid:241)cej. Otó(cid:276) b(cid:246)dziemy losowo
zmienia(cid:232) bie(cid:276)(cid:241)c(cid:241) regu(cid:228)(cid:246) w jednym punkcie. W ka(cid:276)dym kroku b(cid:246)dziemy wi(cid:246)c modyfikowa(cid:232)
wp(cid:228)yw regu(cid:228)y deszyfruj(cid:241)cej na pojedyncz(cid:241) liter(cid:246) alfabetu: je(cid:264)li „a” w obecnej regule zamienia
si(cid:246) na „b”, zaproponujemy regu(cid:228)(cid:246) zmodyfikowan(cid:241), w której „a” zamienia si(cid:246) na „q”. Z powodu
zasady dzia(cid:228)ania szyfru podstawieniowego zmiana ta b(cid:246)dzie wymaga(cid:228)a równoczesnej mody-
fikacji tej cz(cid:246)(cid:264)ci regu(cid:228)y, która dotychczas zamienia(cid:228)a na „q” inn(cid:241) liter(cid:246) alfabetu, dajmy na to
„c”. Aby szyfr wci(cid:241)(cid:276) dzia(cid:228)a(cid:228), „c” b(cid:246)dzie w nowej regule zamieniane na „b”.
Tak wi(cid:246)c nasz algorytm proponowania nowych regu(cid:228) deszyfruj(cid:241)cych sprowadza si(cid:246) do wy-
konania dwóch zamian w istniej(cid:241)cej regule — jednej dobranej losowo i drugiej koryguj(cid:241)cej,
wymuszonej przez zasad(cid:246) dzia(cid:228)ania szyfru podstawieniowego.
W naiwnym podej(cid:264)ciu proponowan(cid:241) now(cid:241) regu(cid:228)(cid:246) zaakceptowaliby(cid:264)my tylko wtedy, kiedy
zwi(cid:246)ksza(cid:228)aby prawdopodobie(cid:254)stwo odszyfrowania wiadomo(cid:264)ci. Taka optymalizacja nazywa
si(cid:246) optymalizacj(cid:241) zach(cid:228)ann(cid:241) albo agresywn(cid:241) (ang. greedy optimization). Niestety, zach(cid:228)anna
optymalizacja wprowadza ryzyko utkni(cid:246)cia na z(cid:228)ych regu(cid:228)ach, wi(cid:246)c przy akceptowaniu no-
wej propozycji regu(cid:228)y deszyfruj(cid:241)cej b(cid:246)dziemy u(cid:276)ywali oceny niezach(cid:228)annej:
1. Je(cid:264)li prawdopodobie(cid:254)stwo wyst(cid:241)pienia tekstu odszyfrowanego regu(cid:228)(cid:241) B jest wi(cid:246)ksze ni(cid:276)
prawdopodobie(cid:254)stwo wyst(cid:241)pienia tekstu odszyfrowanego regu(cid:228)(cid:241) A, regu(cid:228)a B zast(cid:246)puje
regu(cid:228)(cid:246) A.
2. Je(cid:264)li prawdopodobie(cid:254)stwo wyst(cid:241)pienia tekstu odszyfrowanego regu(cid:228)(cid:241) B jest mniejsze ni(cid:276)
prawdopodobie(cid:254)stwo wyst(cid:241)pienia tekstu odszyfrowanego regu(cid:228)(cid:241) A, to regu(cid:228)a B zast(cid:241)pi
regu(cid:228)(cid:246) A, ale nie za ka(cid:276)dym razem. Konkretnie mówi(cid:241)c, je(cid:264)li prawdopodobie(cid:254)stwo skutecz-
no(cid:264)ci regu(cid:228)y B to probability(T,B), a analogiczne prawdopodobie(cid:254)stwo dla regu(cid:228)y A to
probability(T,A), wybierzemy regu(cid:228)(cid:246) B w probability(T,B)/probability(T,A) procencie
przypadków.
Je(cid:264)li powy(cid:276)szy wspó(cid:228)czynnik dopuszczenia zast(cid:241)pienia lepszej regu(cid:228)y przez s(cid:228)absz(cid:241)
regu(cid:228)(cid:246) wydaje si(cid:246) arbitralny, nie szkodzi. Tak naprawd(cid:246) nie liczy si(cid:246) konkretny
wspó(cid:228)czynnik, ale sam fakt, (cid:276)e s(cid:228)absza regu(cid:228)a ma jak(cid:241)kolwiek szans(cid:246) zast(cid:241)pi(cid:232) regu(cid:228)(cid:246)
silniejsz(cid:241). W ten sposób unikamy pu(cid:228)apki zatrzymania zach(cid:228)annej optymalizacji na
lokalnym optimum funkcji b(cid:228)(cid:246)du.
Zanim b(cid:246)dziemy mogli u(cid:276)y(cid:232) metody Metropolis do (cid:228)amania najró(cid:276)niejszych szyfrów, potrze-
bujemy jeszcze kilku narz(cid:246)dzi do generowania i modyfikowania szyfrów. Oto one:
generate.random.cipher - function()
{
cipher - list()
inputs - english.letters
outputs - english.letters[sample(1:length(english.letters),
length(english.letters))]
for (index in 1:length(english.letters))
{
cipher[[inputs[index]]] - outputs[index]
}
return(cipher)
}
modify.cipher - function(cipher, input, output)
188
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkę{
new.cipher - cipher
new.cipher[[input]] - output
old.output - cipher[[input]]
collateral.input - names(which(sapply(names(cipher),
function (key) {cipher[[key]]}) == output))
new.cipher[[collateral.input]] - old.output
return(new.cipher)
}
propose.modified.cipher - function(cipher)
{
input - sample(names(cipher), 1)
output - sample(english.letters, 1)
return(modify.cipher(cipher, input, output))
}
Po(cid:228)(cid:241)czenie narz(cid:246)dzia do proponowania nowych regu(cid:228) i opisanej procedury zamiany (cid:228)agodzi
zach(cid:228)anno(cid:264)(cid:232) metody optymalizacji bez nara(cid:276)ania nas na marnowanie zbyt du(cid:276)ej ilo(cid:264)ci czasu
na regu(cid:228)y wyra(cid:274)nie s(cid:228)abe, które daj(cid:241) znacznie mniejsze (ni(cid:276) regu(cid:228)a bie(cid:276)(cid:241)ca) prawdopodobie(cid:254)stwo
odszyfrowania. Aby to z(cid:228)agodzenie zapisa(cid:232) algorytmicznie, obliczamy iloraz probability(T,B)/
probability(T,A) i porównujemy wynik z liczb(cid:241) losow(cid:241) z zakresu od 0 do 1. Je(cid:264)li otrzymana
liczba losowa jest wi(cid:246)ksza ni(cid:276) iloraz probability(T,B)/probability(T,A), regu(cid:228)a proponowana
zast(cid:246)puje regu(cid:228)(cid:246) bie(cid:276)(cid:241)c(cid:241). Je(cid:264)li nie, pozostajemy przy regule bie(cid:276)(cid:241)cej.
Na potrzeby wyznaczania prawdopodobie(cid:254)stw, na które si(cid:246) stale powo(cid:228)ujemy, tworzymy
leksykaln(cid:241) baz(cid:246) danych mówi(cid:241)c(cid:241) o cz(cid:246)sto(cid:264)ci wyst(cid:246)powania s(cid:228)ów zgromadzonych w pliku
/usr/share/dic/words w tek(cid:264)cie z Wikipedii. Aby za(cid:228)adowa(cid:232) tak(cid:241) baz(cid:246) do programu w j(cid:246)zyku R,
korzystamy z nast(cid:246)puj(cid:241)cej instrukcji:
load( data/lexical_database.Rdata )
Baz(cid:246) danych mo(cid:276)na przejrze(cid:232), podgl(cid:241)daj(cid:241)c pojedyncze s(cid:228)owa i ich cz(cid:246)sto(cid:264)ci wyst(cid:241)pie(cid:254) w przy-
k(cid:228)adowym tek(cid:264)cie (patrz tabela 7.2):
lexical.database[[ a ]]
lexical.database[[ the ]]
lexical.database[[ he ]]
lexical.database[[ she ]]
lexical.database[[ data ]]
Tabela 7.2. Leksykalna baza danych
S(cid:293)owo
a
the
he
she
data
Prawdopodobie(cid:295)stwo wyst(cid:233)pienia
0,01617576
0,05278924
0,003205034
0,0007412179
0,0002168354
Po za(cid:228)adowaniu bazy danych potrzebujemy jeszcze metod obliczania prawdopodobie(cid:254)stwa
wyst(cid:241)pienia tekstu. Najpierw wi(cid:246)c piszemy funkcj(cid:246) ujmuj(cid:241)c(cid:241) zadanie wyci(cid:241)gni(cid:246)cia prawdopodo-
bie(cid:254)stwa z bazy danych. Rol(cid:241) tej funkcji b(cid:246)dzie te(cid:276) u(cid:228)atwienie obs(cid:228)ugi fikcyjnych s(cid:228)ów, którym
funkcja b(cid:246)dzie przypisywa(cid:232) najmniejsze mo(cid:276)liwe prawdopodobie(cid:254)stwo — równe najmniejszemu
epsilonowi reprezentacji zmiennoprzecinkowej dla danego typu komputera. Warto(cid:264)(cid:232) ta w j(cid:246)-
zyku R jest dost(cid:246)pna jako zmienna .Machine$double.eps:
(cid:292)amanie szyfrów jako problem optymalizacji
(cid:95)
189
Poleć książkęKup książkęone.gram.probability - function(one.gram, lexical.database = list())
{
lexical.probability - lexical.database[[one.gram]]
if (is.null(lexical.probability) || is.na(lexical.probability))
{
return(.Machine$double.eps)
}
else
{
return(lexical.probability)
}
}
Zaimplementowali(cid:264)my metod(cid:246) wyszukiwania prawdopodobie(cid:254)stwa pojedynczych s(cid:228)ów —
potrzebujemy jeszcze metody obliczania (cid:228)(cid:241)cznego prawdopodobie(cid:254)stwa wyst(cid:246)powania tekstu
w j(cid:246)zyku angielskim. Metoda ta dzieli tekst na s(cid:228)owa, pozyskuje prawdopodobie(cid:254)stwo poje-
dynczych s(cid:228)ów, a potem oblicza prawdopodobie(cid:254)stwo wynikowe jako iloczyn prawdopodo-
bie(cid:254)stw jednostkowych. Niestety, okazuje si(cid:246), (cid:276)e stosowanie surowych warto(cid:264)ci prawdopodo-
bie(cid:254)stwa jest niestabilne obliczeniowo (z powodu ograniczonej precyzji oblicze(cid:254) na operandach
zmiennoprzecinkowych przy mno(cid:276)eniu). Z tego powodu postanowili(cid:264)my oblicza(cid:232) zlogarytmo-
wane prawdopodobie(cid:254)stwo wyst(cid:246)powania tekstu w j(cid:246)zyku angielskim, b(cid:246)d(cid:241)ce sum(cid:241) zloga-
rytmowanych prawdopodobie(cid:254)stw wyst(cid:246)powania poszczególnych s(cid:228)ów. Tak obliczona miara
okaza(cid:228)a si(cid:246) stabilna obliczeniowo.
log.probability.of.text - function(text, cipher, lexical.database = list())
{
log.probability - 0.0
for (string in text)
{
decrypted.string - apply.cipher.to.string(string, cipher)
log.probability - log.probability +
log(one.gram.probability(decrypted.string, lexical.database))
}
return(log.probability)
}
Skoro mamy ju(cid:276) wszystkie komponenty wykonawcze, mo(cid:276)emy zdefiniowa(cid:232) krok metody
Metropolis:
metropolis.step - function(text, cipher, lexical.database = list())
{
proposed.cipher - propose.modified.cipher(cipher)
lp1 - log.probability.of.text(text, cipher, lexical.database)
lp2 - log.probability.of.text(text, proposed.cipher, lexical.database)
if (lp2 lp1)
{
return(proposed.cipher)
}
else
{
a - exp(lp2 - lp1)
x - runif(1)
if (x a)
{
return(proposed.cipher)
190
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkę }
else
{
return(cipher)
}
}
}
Mo(cid:276)emy ju(cid:276) przyst(cid:241)pi(cid:232) do po(cid:228)(cid:241)czenia poszczególnych etapów algorytmu optymalizacji —
napiszemy prosty program i sprawdzimy jego dzia(cid:228)anie. Na pocz(cid:241)tek potrzebujemy jakiego(cid:264)
tekstu wzorcowego, który zapiszemy w R jako wektor znakowy:
decrypted.text - c( here , is , some , sample , text )
Tekst ten zaszyfrujemy szyfrem Cezara:
encrypted.text - apply.cipher.to.text(decrypted.text, caesar.cipher)
Teraz wygenerujemy losowy szyfr dekoduj(cid:241)cy, rozpoczniemy od niego 50 000 iteracji metody
Metropolis i zapiszemy wyniki poszczególnych iteracji w ramce danych results. W ka(cid:276)dym prze-
biegu b(cid:246)dziemy rejestrowa(cid:232) logarytm prawdopodobie(cid:254)stwa dla odszyfrowanego tekstu, odszy-
frowany w danej iteracji tekst oraz sztuczn(cid:241) zmienn(cid:241), sygnalizuj(cid:241)c(cid:241), czy tekst zosta(cid:228) odszy-
frowany poprawnie.
Gdyby(cid:264)my naprawd(cid:246) chcieli z(cid:228)ama(cid:232) tajny szyfr, nie byliby(cid:264)my w stanie oznaczy(cid:232) od-
szyfrowanych wiadomo(cid:264)ci jako prawdziwe. Tu robimy to jedynie w ramach przyk(cid:228)adu.
set.seed(1)
cipher - generate.random.cipher()
results - data.frame()
number.of.iterations - 50000
for (iteration in 1:number.of.iterations)
{
log.probability - log.probability.of.text(encrypted.text, cipher, lexical.database)
current.decrypted.text - paste(apply.cipher.to.text(encrypted.text, cipher),
collapse = )
correct.text - as.numeric(current.decrypted.text == paste(decrypted.text,
collapse = ))
results - rbind(results,
data.frame(Iteration = iteration,
LogProbability = log.probability,
CurrentDecryptedText = current.decrypted.text,
CorrectText = correct.text))
cipher - metropolis.step(encrypted.text, cipher, lexical.database)
}
write.table(results, file = file.path( data/results.tsv ),
row.names = FALSE, sep = \t )
Wykonanie programu zajmie dobr(cid:241) chwil(cid:246), wi(cid:246)c podczas oczekiwania na wyniki zapraszamy
do spojrzenia na próbk(cid:246) gotowych wyników, zebranych w tabeli 7.3.
(cid:292)amanie szyfrów jako problem optymalizacji
(cid:95)
191
Poleć książkęKup książkęTabela 7.3. Post(cid:246)py metody Metropolis
Iteracja
1
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
Logarytm prawdopodobie(cid:295)stwa
Odszyfrowany tekst
-180.218266945586
-67.6077693543898
-67.6077693543898
-67.6077693543898
-70.8114316132189
-39.8590155606438
-39.8590155606438
-39.8590155606438
-35.784429416419
-37.0128944882928
-35.784429416419
lsps bk kfvs kjvhys zsrz
gene is same sfmpwe text
gene is same spmzoe text
gene is some scmhbe text
dene as some scmire text
gene as some simple text
gene as some simple text
gene as some simple text
were as some simple text
were is some sample text
were as some simple text
Jak wida(cid:232), po 45 000 krokach metody Metropolis byli(cid:264)my ju(cid:276) bardzo blisko poprawnego od-
szyfrowania tekstu. Szczegó(cid:228)owa analiza wszystkich wyników pokazuje, (cid:276)e poprawny tekst zo-
sta(cid:228) uzyskany w iteracji numer 45 609, ale algorytm poszed(cid:228) dalej, zamieniaj(cid:241)c regu(cid:228)(cid:246) w pe(cid:228)ni
poprawn(cid:241) na inn(cid:241) zaproponowan(cid:241). Jest to skutek ograniczenia naszej funkcji celu, która nie
ocenia, czy odszyfrowany tekst jest poprawnym tekstem j(cid:246)zyka angielskiego, lecz jedynie spraw-
dza, czy poszczególne wyrazy s(cid:241) poprawnymi wyrazami. Je(cid:264)li zmiana regu(cid:228)y pozwala na od-
szyfrowanie bardziej prawdopodobnego s(cid:228)owa, algorytm pójdzie w tym kierunku, nawet je(cid:264)li
wynikowy tekst b(cid:246)dzie koszmarnie niegramatyczny albo nielogiczny. Mogliby(cid:264)my u(cid:276)y(cid:232) do
oceny dodatkowych miar, na przyk(cid:228)ad prawdopodobie(cid:254)stwa wyst(cid:246)powania par s(cid:228)ów. Na razie
jednak zostawimy algorytm bez zmian, podkre(cid:264)laj(cid:241)c na tym przyk(cid:228)adzie skomplikowanie metod
optymalizacyjnych opartych na zmontowanych napr(cid:246)dce funkcjach oceny — niekiedy oczeki-
wane rozwi(cid:241)zanie wcale nie jest rozwi(cid:241)zaniem najlepszym z punktu widzenia oceny celu. Jak
wida(cid:232), przyda(cid:228)aby si(cid:246) tu interwencja operatora, znaj(cid:241)cego oczekiwania lepiej ni(cid:276) funkcja celu.
Problematyczno(cid:264)(cid:232) optymalizacji nie ogranicza si(cid:246) zreszt(cid:241) do k(cid:228)opotów z nadmiernym prymitywi-
zmem funkcji celu. Metoda Metropolis jest przede wszystkim zawsze metod(cid:241) optymalizacji
losowej. Na szcz(cid:246)(cid:264)cie zacz(cid:246)li(cid:264)my od dobrego zarodka generatora losowego, ale w przypadku
niektórych innych stanów pocz(cid:241)tkowych generatora losowego mo(cid:276)e si(cid:246) okaza(cid:232), (cid:276)e na popraw-
n(cid:241) regu(cid:228)(cid:246) deszyfruj(cid:241)c(cid:241) poczekamy nawet tryliony iteracji. Mo(cid:276)na to (cid:228)atwo samemu spraw-
dzi(cid:232), zmieniaj(cid:241)c warto(cid:264)(cid:232) parametru funkcji set.seed i próbkuj(cid:241)c metod(cid:246) Metropolis porcjami
po 1000 iteracji dla ka(cid:276)dego badanego stanu generatora losowego.
Ponadto metoda Metropolis zawsze b(cid:246)dzie sk(cid:228)onna do porzucania dobrych odszyfrowa(cid:254). Dzi(cid:246)ki
temu algorytm jest niezach(cid:228)anny. Gdy b(cid:246)dziemy analizowa(cid:232) szczegó(cid:228)owy przebieg wykonania
optymalizacji, cz(cid:246)sto zdarzy si(cid:246) nam zobaczy(cid:232), jak metoda Metropolis porzuca w(cid:228)a(cid:264)ciwe, oczeki-
wane rozwi(cid:241)zanie i idzie dalej, w kierunku rozwi(cid:241)zania nieco s(cid:228)abszego. Na rysunku 7.6 po-
kazujemy wykres logarytmu prawdopodobie(cid:254)stwa dla odszyfrowanego tekstu z poszczegól-
nych kroków metody Metropolis. Wida(cid:232), (cid:276)e ruchy algorytmu w przestrzeni rozwi(cid:241)za(cid:254) s(cid:241)
do(cid:264)(cid:232) nerwowe.
192
(cid:95)
Rozdzia(cid:293) 7. Optymalizacja — (cid:293)amanie szyfrów
Poleć książkęKup książkęRysunek 7.6. Post(cid:246)p metody Metropolis — szukanie optymalnej regu(cid:228)y deszyfruj(cid:241)cej
Te losowe zwroty metody mo(cid:276)na st(cid:228)umi(cid:232) na kilka cz(cid:246)sto stosowanych sposobów. Jednym z nich
jest powi(cid:246)kszanie zach(cid:228)anno(cid:264)ci metody z up(cid:228)ywem czasu poprzez coraz rzadsze akceptowanie
niepost(cid:246)powych propozycji. Technika ta, znana jako symulowane wy(cid:276)arzanie (ang. simulated
annealing), jest bardzo efektywnym mechanizmem optymalizacji. Mo(cid:276)emy j(cid:241) wypróbowa(cid:232) w swoim
w(cid:228)asnym programie, zmieniaj(cid:241)c sposób akceptowania nowej regu(cid:228)y deszyfruj(cid:241)cej4.
Mo(cid:276)na te(cid:276) przyj(cid:241)(cid:232) losowy charakter metody z dobrodziejstwem inwentarza i zamiast zaw(cid:246)(cid:276)a(cid:232)
wynik do jednej optymalnej regu(cid:228)y, dawa(cid:232) w odpowiedzi rozk(cid:228)ad mo(cid:276)liwych odpowiedzi w uj(cid:246)-
ciu prawdopodobie(cid:254)stwa. W zadaniu deszyfrowania nie by(cid:228)oby to szczególnie u(cid:276)yteczne, ale
tam, gdzie szukamy odpowiedzi liczbowej, mo(cid:276)liwo(cid:264)(cid:232) wygenerowania zestawu odpowiedzi
bliskich odpowiedzi optymalnej do wyboru bywa bardzo pomocne.
Mamy nadziej(cid:246), (cid:276)e uda(cid:228)o si(cid:246) nam przedstawi(cid:232) zasad(cid:246) i sedno dzia(cid:228)ania metod optymalizacji
w ogóle, a w szczególno(cid:264)ci techniki anga(cid:276)owania optymalizacji do rozwi(cid:241)zywania skomplikowa-
nych problemów uczenia maszynowego. Do niektórych przywo(cid:228)anych tu pomys(cid:228)ów b(cid:246)dziemy
wraca(cid:232) w dalszych rozdzia(cid:228)ach, zw(cid:228)aszcza przy omawianiu systemów rekomendacyjnych.
4 Funkcja optim przyjmuje nawet opcjonalny parametr zmuszaj(cid:241)cy j(cid:241) do stosowania symulowanego wy(cid:276)a-
rzania zamiast standardowego algorytmu optymalizacji. Ale w naszym przyk(cid:228)adzie i tak nie mo(cid:276)emy
skorzysta(cid:232) z „gotowca” w postaci funkcji optim, bo optymalizacja realizowana przez t(cid:246) funkcj(cid:246) dzia(cid:228)a na
warto(cid:264)ciach liczbowych i nie obs(cid:228)uguje struk
Pobierz darmowy fragment (pdf)