Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00185 003931 15209784 na godz. na dobę w sumie
Uczenie maszynowe dla programistów - ebook/pdf
Uczenie maszynowe dla programistów - ebook/pdf
Autor: , Liczba stron: 280
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-9819-6 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> inne - programowanie
Porównaj ceny (książka, ebook, audiobook).

Wyciągnij najlepsze wnioski z dostępnych danych!

Maszyna myśląca jak człowiek to marzenie ludzkości. Dzięki dzisiejszej wiedzy i dostępnym narzędziom wciąż przybliżamy się do jego spełnienia. Zastanawiasz się, jak nauczyć maszynę myślenia? Jak sprawić, żeby podejmowała trafne decyzje oraz przewidywała najbliższą przyszłość na podstawie przygotowanych modeli? Na to i wiele innych pytań odpowiada ta wspaniała książka.

Dzięki niej poznasz język R, nauczysz się eksplorować dostępne dane, określać wartość mediany i odchylenia standardowego oraz wizualizować powiązania między kolumnami. Gdy opanujesz już solidne podstawy teoretyczne, możesz śmiało przejść do kolejnych rozdziałów i zapoznać się z klasyfikacją binarną, tworzeniem rankingów oraz modelowaniem przyszłości przy użyciu regresji. Ponadto zrozumiesz, jak tworzyć systemy rekomendacyjne, analizować sieci społeczne oraz łamać szyfry. Książka ta jest doskonałą lekturą dla pasjonatów analizy danych i wyciągania z nich wniosków.

Każdy rozdział książki jest poświęcony konkretnemu zagadnieniu uczenia maszynowego: klasyfikacji, predykcji, regresji, optymalizacji i wreszcie rekomendacji. Czytelnik nauczy się konstruować proste algorytmy uczenia maszynowego (i przepuszczać przez nie próbki danych) za pomocą języka programowania R. Uczenie maszynowe dla programistów jest więc znakomitą lekturą dla programistów parających się czy to projektami komercyjnymi, czy to rządowymi, czy wreszcie akademickimi.

Naucz się czytać i analizować dane!

Książka ta stanowi świetny przegląd przypadków i tuzina różnych technik uczenia maszynowego. Jest ukierunkowana na proces dochodzenia do rozwiązania, a nie gotowe recepty ani abstrakcyjne teorie; dzięki temu jej materiał jest dostępny dla wszystkich programistów, ale też przysłowiowych „umysłów ścisłych”

— Max Shron, OkCupid

 

Znajdź podobne książki Ostatnio czytane w tej kategorii

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)

Gdzie kupić całą publikację:

Uczenie maszynowe dla programistów
Autor:
,

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: