Archiwa tagu: algorytm

Google w gąszczu danych: fotograficzny skandal i uczenie maszynowe dla laików

Dwa tygodnie temu media obiegła wieść o skandalicznej wpadce Google Photos. System automatycznego rozpoznawania twarzy i obiektów na zdjęciach zaklasyfikował dwie czarnoskóre osoby jako „goryle” i utworzył dla nich specjalny album o tym właśnie tytule.

Wśród tłumaczeń Google – a trzeba firmie przyznać, że zareagowała bardzo szybko – najbardziej spodobało mi się wyznanie, że twarze białych osób niejednokrotnie są rozpoznawane i podpisywane jako foki albo psy.

Moją uwagę przykuły komentarze czytelników, którzy domagali się „natychmiastowej zmiany algorytmu”. Pomyślałam, że to dobra okazja, żeby napisać kilka słów o uczeniu maszynowym i wyjaśnić, że za tę wpadkę nie odpowiada algorytm w klasycznym znaczeniu tego słowa.

Algorytm to skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Ludzie stosują algorytmy w swoim codziennym życiu, mniej lub bardziej świadomie (każdy z nas wie mniej więcej, jakie kroki należy wykonać w celu wymiany  zepsutej żarówki). Jeżeli jednak chcemy skłonić do działania komputer, musimy powiedzieć mu wyraźnie i jednoznacznie, jak ma postąpić w określonej sytuacji.

Jedną z metod zapisu algorytmów są schematy blokowe. Poniższy diagram przedstawia schemat blokowy algorytmu sprzątania po swoim psie w miejscu publicznym.

algorytm-pies
Algorytm sprzątania po swoim psie w miejscu publicznym

Przykład pięknego „poważnego” algorytmu znajdziesz w moim poprzednim wpisie.

Algorytmy można badać i porównywać, dzięki czemu powstają ich coraz szybsze i sprawniejsze wersje. Istnieje jednak grupa problemów, które algorytmom nie poddają się najlepiej. Chodzi albo o zadania bardzo skomplikowane, w których rozpisywanie kroków zajęłoby całe lata, albo o takie, które ludzkie mózgi wykonują bardzo szybko, ale ich nosiciele sami nie są w stanie odpowiedzieć na pytanie, jak to się dzieje. Doskonałymi przykładami są tutaj rozpoznawanie twarzy i rozpoznawanie mowy. Sprawa nie jest trywialna. Wiadomo, że istnieją choroby, które odbierają ludziom wymienione przed chwilą umiejętności, nie zaburzając przy tym zdolności logicznego myślenia.

Problemy z opisanej kategorii można rozwiązywać przy użyciu uczenia maszynowego. Jest to dziedzina, która od lat dziewięćdziesiątych nabiera coraz większego znaczenia, w miarę jak wzrasta moc obliczeniowa komputerów i wraz z dostępnością coraz większej ilości danych w Internecie. Dominują dwa nurty: pierwszy oparty na sieciach neuronowych (mających naśladować budowę ludzkiego mózgu), drugi na statystyce i rachunku prawdopodobieństwa.  Poniżej przedstawię prosty (żeby nie użyć mocniejszego słowa) przykład statystycznego uczenia maszynowego.

Jak to działa? Rozważmy popularne zadanie wykrywania spamu. Jeżeli przeanalizujemy tysiąc maili, z których połowa została przez użytkownika oznaczona jako spam, a połowa to normalne, pożądane treści, będziemy w stanie wyciągnąć jakieś wnioski. Możemy, na przykład, utworzyć listę słów, które pojawiły się w wiadomościach i podliczyć, ile razy dane słowo pojawiło się w wiadomości oznaczonej jako spam, a ile razy w wartościowej wiadomości. W ten sposób dla każdego ze słów wyznaczymy prawdopodobieństwo „bycia spamem”. Kiedy pojawi się nowa wiadomość, możemy, w oparciu o listę słów, wyliczyć całkowite prawdopodobieństwo (ryzyko), że dana wiadomość to spam.

Poniżej przykładowy prosty model i związane z nim wyliczenia. Proszę pod żadnym pozorem nie uczyć się z tego statystyki!!!

Wiadomości otrzymane przez użytkownika, zaklasyfikowane przez niego jako wartościowe treści albo spam:

Treść wiadomości Klasyfikacja
Ciociu, jak będzie okazja, kup mi nad morzem wisiorek z bursztynem. Ok.
Okazja! Tylko dzisiaj kup viagrę za 30 zł! Okazja! Spam.

Analiza słów zawartych w wiadomościach:

Słowo Wystąpień „spam” Wystąpień „ok” Prawdopodobieństwo, że to spam
ciociu 0 1 0
kup 1 1 1/2
okazja 2 1 2/3
viagrę 1 0 1
wisiorek 0 1 0

Próba automatycznego oszacowania, czy nowe wiadomości należy wrzucić do folderu „spam”:

Treść nowej wiadomości Prawdopodobieństwo, że spam?
Ciociu, kup wisiorek. (0+1/2+0)/3 = 1/6 = 16.6%
Ciociu, kup viagrę. (0+1/2+1)/3 = 1/2 = 50%
Kup viagrę. (1/2+1)/2 = 3/4 = 75%

Można spotkać się z terminem „algorytm uczenia maszynowego”, ale należy pamiętać, że najczęściej mamy w tej kategorii do czynienia z matematycznymi metodami, które dadzą kompletnie odmienne wyniki w zależności od tego, na jakim zbiorze danych zostaną wytrenowane.

Jakie są efekty? Raczej dobre. Nie da się jednak dogodzić wszystkim, a już na pewno nie na podstawie jednego, wspólnego zbioru danych. Większość z nas chce, aby reklamy środków na powiększenie penisa automatycznie trafiały do katalogu „spam” lub do kosza, ale ktoś przecież takie środki kupuje i wówczas z pewnością chce się dowiedzieć, kiedy dotrze do niego upragniona przesyłka. Poza tym, zbiór danych użyty do trenowania może okazać się za mały, za duży, błędnie opisany lub niewystarczająco reprezentatywny.

Co dokładnie stało się w przypadku Google? Najprawdopodobniej dane wykorzystane do uczenia nie były wystarczająco reprezentatywne – występowali na nich głównie biali ludzie, więc system uwzględnił jasny kolor skóry jako istotny wyznacznik bycia człowiekiem. Warto dodać, że autor (i obiekt) fotografii, które rozpętały całe to zamieszanie, sam jest programistą i od razu zaznaczał, że wie co się stało. Pytał tylko retorycznie „skąd wzięliście te dane?”. Najbardziej wstydliwa możliwość, choć raczej mało prawdopodobna, jest taka, że podczas trenowania użyte zostały zdjęcia opatrzone rasistowskimi komentarzami, które system potraktował jako pewnik.

Problem nie jest łatwy do naprawienia. Być może firma do końca nie wie, skąd pochodziły dane. Być może trenowanie trwa wiele dni. Zgodnie z aktualnymi doniesieniami, etykieta „gorillas” została na wszelki wypadek kompletnie usunięta z systemu.

Elegancki algorytm miesiąca: Kadane

Mój pracodawca niespodziewanie wpadł na pomysł poddania wszystkich programistów testom algorytmicznym. Plan niepokojący, zwłaszcza dla „seniorów”, wobec których oczekiwania są wysokie, a którzy na co dzień raczej nie implementują własnoręcznie ekstrawaganckich algorytmów sortowania.

Na szczęście (niekoniecznie dla efektów pracy projektowej) w ramach zachęty otrzymaliśmy możliwość uczestnictwa w pięciodniowym kursie algorytmicznym. Mam za sobą dwa takie dni i muszę powiedzieć, że wrócił mi zapał do programowania, jakiego nie czułam od lat!

Urzekł mnie pewien króciutki i bardzo elegancki algorytm rozwiązujący problem znalezienia podciągu o największej sumie.

Problem

Niech dana będzie tablica (ciąg) liczb o długości co najmniej 1.

4 -10 3 29 -3 12 -5 4

Zadanie polega na znalezieniu w tablicy spójnej podtablicy o największej sumie elementów i zwróceniu tej sumy. W naszym przypadku całkowita suma elementów tablicy to 34, natomiast maksymalna suma podciągu elementów to 41. Elementy składające się na tę maksymalną sumę oznaczyłam kolorem czerwonym.

Programujesz?

Poświęć chwilę na rozwiązanie tego problemu. Jaką złożoność obliczeniową ma Twój program?  Brute force to pewnie O(n2). O(nlogn)? Nieźle. Ile masz linii?

Niniejszym przedstawiam przepiękny, pięciolinijkowy algorytm o złożoności liniowej, czyli O(n).

Programowanie dynamiczne

Eleganckie rozwiązanie tego problemu jest oparte na pomyśle określanym mianem „programowania dynamicznego”. Co to znaczy?

Można zauważyć, że niektóre problemy algorytmiczne da się podzielić na mniejsze podzadania.

  • Jeżeli podzadania te są od siebie niezależne, w ramach uproszczenia warto zastosować metodę „dziel i zwyciężaj” – w ten sposób działa wiele dobrych algorytmów sortowania (np. quicksort).
  • Jeśli podzadania w jakiś sposób na siebie nachodzą i jedne wyniki są inkrementacyjnie zależne od drugich, można spróbować użyć programowania dynamicznego.

Programowanie dynamiczne przypomina stosowanie rekurencji, z tą różnicą, że potrzebne nam wyniki cząstkowe wyznaczamy tylko raz. Wynik możemy konstruować wstępująco (najpierw wynik dla najmniejszego podproblemu, potem narastająco dla coraz większych zadań) lub zstępująco (definiujemy „rekurencyjną” zależność pomiędzy wynikiem większego problemu a problemami mniejszymi, tyle że potrzebne nam wyniki zapamiętujemy w jakimś buforze i nie wyznaczamy ich ponownie).

Algorytm Kedane’a

Implementacja w Pythonie dla tablicy A wygląda tak:

I już!!!

Jak to działa?

Najpierw wyznaczamy wynik dla najmniejszej tablicy, o długości jeden. Suma elementów tablicy o tej długości (największa, najmniejsza i każda inna suma) to oczywiście wartość jedynego elementu (A[0]).

Przez cały czas działania algorytmu będziemy utrzymywać dwie zmienne: max_total to nasz najlepszy napotkany do tej pory wynik, natomiast max_local to najlepszy wynik zawierający aktualnie obsługiwany element.

Przechodząc przez kolejne elementy,  za max_local każdorazowo podstawiamy większą z dwóch liczb: aktualny element x lub dotychczasową wartość max_local zwiększoną o x.

Jeśli nowy wynik lokalny jest większy od max_total, zamieniamy wartość max_total.

Ostatnia wartość max_total jest naszą odpowiedzią dla problemu wielkości całej tablicy.

Studium przypadku

Zakresy w tabeli oznaczyłam odpowiednim formatowaniem. Zielone elementy składają się na max_local, a podkreślone na max_total.

Zatem, dla naszej początkowej tablicy, algorytm będzie przebiegał następująco:

Element 0
4
  • max_local = 4
  • max_total = 4
Element 1
4 -10
  • max_local = max(-10,-10+4) = -6
  • max_total = max(4,-6) = 4
Element 2
4 -10 3
  • max_local = max(3,-6+3) = 3
  • max_total = max(4,3) = 4
Element 3
4 -10 3 29
  • max_local = max(29,3+29) = 32
  • max_total = max(4,32) = 32
Element 4
4 -10 3 29 -3
  • max_local = max(-3,32-3) = 29
  • max_total = max(32,29) = 32
Element 5
4 -10 3 29 -3 12
  • max_local = max(12,29+12) = 41
  • max_total = max(32,41) = 41
Element 6
4 -10 3 29 -3 12 -5
  • max_local = max(-5,41-5) = 36
  • max_total = max(41,36) = 41
Element 7
4 -10 3 29 -3 12 -5 4
  • max_local = max(4,36+4) = 40
  • max_total = max(41,40) = 41

Ładny, prawda? 🙂

Posłowia

  1. „Algorytm Kadane’a” piszemy z apostrofem, inaczej niż na przykład „Algorytm Kruskala”. Swego czasu, doprowadzona do ostateczności nadużywaniem apostrofu w polskim Internecie popełniłam wpis na ten temat. W najbliższej przyszłości zamierzam odświeżyć go i opublikować także tutaj, gdyż plaga ta zatacza coraz szersze kręgi.
  2. Pamiętam, że w poprzednim wpisie (Ciągła Integracja: anioł stróż dobrego programisty) obiecałam pokazać, jak stworzyć plan na serwerze Bamboo. Jeszcze chwilka.