Algorytm wyrabia sobie opinię

Prof. Andrzej Tarlecki, informatyk: Wszystko, co wyszukiwarki internetowe "wiedzą", opiera się o proste skojarzenia i analizę zachowań użytkownika. System nie wie. Podejrzewa. Rozmawiał Michał Kuźmiński

06.12.2011

Czyta się kilka minut

/ rys. Joanna Grochocka /
/ rys. Joanna Grochocka /

Michał Kuźmiński: Większość użytkowników wyszukiwarek internetowych pewnie nie wie, że istnieje teoria wyszukiwania...

Prof. Andrzej Tarlecki: Funkcjonuje w niej pojęcie, które dziś jest bardzo na czasie: bazy danych z niepełną informacją. Wprowadził je do nauki wybitny, przedwcześnie zmarły informatyk, Witold Lipski. Otóż bazę danych zwykle wyobrażamy sobie zakładając, że dysponujemy wszystkimi danymi: np. rekord o pracowniku będzie zawierał i datę urodzenia, i wysokość zarobków, i stanowisko w firmie itp. Nawet wtedy nie takie proste jest wyszukanie w bazie pracowników, których średnia zarobków za ostatnie pół roku była wyższa niż 1538 zł. Natomiast w rzeczywistości dane w bazie zwykle są niepełne: mamy imię i nazwisko, brak daty urodzenia, a zarobki znamy za ostatnie trzy miesiące. Wówczas próba znalezienia wszystkich pracowników według takiego kryterium okazuje się dużo trudniejsza, choćby przez to, że nie jest jasne, jakie niepełne rekordy danych to kryterium spełniają. Wokół takich baz ze znakami zapytania powstają ciekawe problemy, których formalną analizę rozpoczął właśnie Lipski. Dziś problematyka wyszukiwania w dużych bazach o niepełnych danych jest nadal jednym z fascynujących problemów informatyki - i to w zupełnie innej skali, gdyż wielkość przechowywanych zasobów informacji jest dziś nieporównywalnie większa.

Wyszukiwarki to tak naprawdę gigantyczne bazy danych na temat zawartości internetu - i to bazy niepełne?

W wielkim uproszczeniu ich działanie można opisać jako użycie "prostej siły": nieustanne gromadzenie dostatecznie dużej liczby informacji, porządkowanie ich, indeksowanie i zapewnienie odpowiednio szybkiego dostępu do nich. To ostatnie jest szczególnie niebanalnym zadaniem - służą do tego bardzo złożone algorytmy indeksacji, zapamiętywania skrótów, znajdywania najbardziej prawdopodobnych szybkich połączeń itd. A w tle tkwi jeszcze olbrzymia moc obliczeniowa komputerów i ich gigantyczna pamięć. Rosną one dosłownie z miesiąca na miesiąc. Farmy serwerów, które obsługują wyszukiwarki, przypominają dziś hale produkcyjne.

Paweł Parys, tegoroczny laureat nagrody informatycznej imienia wspomnianego Witolda Lipskiego, zajmuje się wyszukiwaniem w dokumentach XML, rekurencją... Cóż to znaczy?

Zwykły - a nawet niezwykły - użytkownik widzi okienko, w które wpisuje hasło, a za chwilę otrzymuje odpowiedź. Warto sobie uświadomić, że pojawia się ona po przeszukaniu olbrzymiej liczby stron. Przy czym wcale nie odbywa się to na zasadzie ich żmudnego przeszukiwania jedna po drugiej. Szukając czegoś w domowej biblioteczce, sięgamy niekiedy po pierwszą książkę, przeglądamy, jeśli nam pasuje, odkładamy na stosik, jeśli nie, to książka wraca na półkę, a my sięgamy po kolejną... Takie liniowe przeszukiwanie internetu trwałoby wieczność. Dosłownie - chodzi tu o czasy porównywalne z astronomicznymi.

Sztuka polega na tym, by naiwny, liniowy algorytm wyszukiwania zastąpić znacznie bardziej wyrafinowanym i dotrzeć do pożądanych wyników jeszcze przed końcem świata.

Jeśli odpowiednio uporządkujemy zbiór danych, przeszukiwanie liniowe można zastąpić logarytmicznym, znacznie szybszym: gdy wiem, że książki na półce uporządkowane są według dat wydania, i znam rok wydania książki, której szukam, sprawdzam w połowie półki i orientuję się, czy moją książkę znajdę po prawej, czy po lewej stronie. Następnie patrzę w połowie wybranej połówki... i właśnie nauczyłem pana, czym jest rekurencja: do wybranej połówki zastosowałem ten sam algorytm, co pierwotnie do całości.

Pojęcie rekurencji było znane i badane przez matematyków długo przed obecną "erą informatyki". Ale zastosowania informatyczne podkreślają znaczenie dobrych algorytmów rekurencyjnych. Opracowanie takich niebanalnych algorytmów dla trudnych i ważnych problemów to często prawdziwa sztuka, o wielkim potencjale zastosowań. Paweł Parys zajmował się problemem szybkiego budowania odpowiedzi na zapytania dotyczące danych przechowywanych w formacie XML, powszechnym dziś standardzie tworzenia dokumentów. Zaproponował nietrywialny, efektywny algorytm, który potencjalnie może znaleźć zastosowanie w systemach wykorzystywanych na co dzień przez miliony użytkowników.

Niekiedy sam nie wiem dokładnie, czego szukam, a tu Google podsuwa właściwą odpowiedź, Facebook sugeruje znajomość z przez lata niewidzianym kolegą... Skąd to wiedzą?

Ostrzegałbym przed używaniem słowa "wiedza". Cała ta "wiedza" opiera się o bardzo proste w gruncie rzeczy skojarzenia i o analizę zachowań użytkownika w przeszłości. System sprawdza, jakiego typu hasła najczęściej pan wpisywał, i zestawia z owymi skojarzeniami: jeżeli "Tarlecki", to pewnie informatyka, a jeśli do tego często pyta pan o listy publikacji naukowców, na pierwszym miejscu system podsunie listę publikacji Tarleckiego. Więc system nie tyle "wie", co "podejrzewa".

A niepewna wiedza to jedna z większych bolączek internetu. Ktoś powiedział, że w sieci można znaleźć wszystko... czyli też każdą bzdurę. Nie lada problemem jest wyłapanie owych bzdur i pominięcie ich na rzecz informacji obiektywnie wartych zauważenia.

Czy algorytmy mogą być pomocne w ocenianiu wartości odnalezionej informacji?

Pytanie - co to znaczy "wartość"? Czy chodzi o coś przydatnego mnie, czy raczej o coś obiektywnie prawdziwego? Dla matematyka czy informatyka o obiektywnej prawdziwości świadczy formalny dowód. Od lat są już budowane bazy danych gromadzące twierdzenia wraz z ich pełnymi, sprawdzonymi formalnymi dowodami. Warto tu wymienić intensywnie rozwijany polski system Mizar. Powstają też systemy wspomagania formalnego dowodzenia twierdzeń i własności programów, coraz lepiej radzące sobie w praktycznych zastosowaniach.

Formalny dowód twierdzenia matematycznego to oczywiście ideał, ale chciałoby się mieć pewność, że wpisując w wyszukiwarkę zapytanie o to, w którym roku urodził się Sean Connery, dostanę odpowiedź, że było to... nie pamiętam...

To moment, w którym trzeba sięgnąć do wyszukiwarki.

...i chciałbym mieć pewność, że informacja, iż było to w - sprawdźmy... - w 1930 r., jest prawdziwa. Bo zwykle między źródłami podsuwanymi przez wyszukiwarkę są poważne różnice. Otrzymujemy listę odwołań, z których sami musimy wybrać to właściwe. Chciałoby się, by algorytmy wyszukiwarek umiały dokonywać analizy powiązań i sprzeczności między informacjami. Wracamy tu do tematu baz danych z niepełną czy niepewną informacją. W takich przypadkach można by stosować - i niekiedy się stosuje - statystyczną analizę wiarygodności.

Jednym z większych problemów sieci nie jest to, jak znaleźć informację, o którą nam chodzi, lecz jak sprawdzić, czy to, co znaleźliśmy, jest wiarygodne. Dziś każda z tysięcy stron - wyników wyszukiwania hasła "Sean Connery", jest równouprawniona. Stosowane algorytmy rankingowania stron, czyli określania kolejności, w której mają się pojawić, są tu pomocne tylko w niewielkim stopniu.

To ranking według liczby odniesień do danej strony z innych stron, czyli niejako jej popularności. Skuteczny?

Nie zawsze. Na pewnej uczelni zrezygnowano z podręczników - "bo przecież jest internet". Mizerny efekt ujawnił się szybko w poziomie prac studentów. Bo skąd mieli oni wiedzieć, że rację ma mówiący do 50 osób wykładowca, a nie internetowy autor, do którego strony odsyła kilka tysięcy innych?

Ostatnie lata przyniosły niezwykły rozwój usług wyszukiwania. Upowszechnia się wyszukiwanie dźwięków czy obrazów: można np. wyszukiwarce SoundHound odtworzyć fragment piosenki, a ona powie, co to za utwór, albo pokazać Google’owi obrazek, a on znajdzie podobne. Co jeszcze zostało do wymyślenia w tej dziedzinie?

Gdybym wiedział, dorabiałbym się właśnie wielkich pieniędzy. Ale rozwój tego typu technologii to nic niezwykłego. Nie tak odległe są czasy, gdy internet był maszyną do wysyłania poczty, i to tylko dla wtajemniczonych. W którymś momencie nastąpił boom technologii sieciowych, którego konsekwencją było umieszczenie w sieci informacji każdego możliwego rodzaju. Przy czym wszystkie te informacje mają postać cyfrową - stanowią ciągi dających się analizować zer i jedynek, bez względu na to, czy kodują tekst, obraz czy dźwięki. Im więcej informacji było w sieci, tym ważniejsze było jej wyszukiwanie, które umożliwiał z kolei wzrost mocy obliczeniowych serwerów i przepustowości łączy. Bo nie jest ważne tylko to, co można policzyć, ale też to, jak wiele danych możemy przesyłać.

Z naukowego punktu widzenia nie są to rzeczy bardzo nowe, np. analizę obrazu rozwija się już od dawna. Nowa jest skala, upowszechnienie, dostępność dla każdego. Technologie te będą dalej rozwijane, bo wszystko, co jest dostępne w sieci, podlega wyszukiwaniu, analizie, porównaniom. Szukać będziemy we wszystkim, co będziemy przechowywać, a tego będzie już tylko więcej.

Nie bez kozery zapytałem wcześniej: "skąd wyszukiwarka coś wie" - bo mamy tendencję do przypisywania maszynom zachowań, intencji, inteligencji itd. Ale czy do wyszukiwania zaprzęga się metody sztucznej inteligencji?

Ależ tak - tylko że rozumianej znacznie bardziej porządnie niż w popularnym pojęciu. Nie lubię tego terminu, kryje on dla mnie po prostu dział informatyki zajmujący się algorytmami, które z natury rzeczy nie są dokładne i nie dają absolutnych wyników. Istnieją bowiem takie problemy - matematyk czy informatyk powie: "problemy nierozstrzygalne" - dla których nie może istnieć algorytm w pełni je rozwiązujący. Co nie znaczy, że nie można podejmować prób stworzenia jak najlepszego algorytmu, który możliwie często będzie potrafił udzielić dostatecznie dobrej odpowiedzi.

Zaakceptowaliśmy już, niestety, że nasze programy są niedoskonałe. Nasz ulubiony system operacyjny od czasu do czasu się zawiesza i nauczyliśmy się z tym żyć, błagając jedynie, żeby nie stało się to w połowie pisania ważnego artykułu. I dla nierozstrzygalnych problemów da się stworzyć "niedoskonałe" algorytmy, które poprawną odpowiedź podadzą zadowalająco często. Albo wręcz dostatecznie rzadko dadzą odpowiedź błędną. Łatwo można zgodzić się, by algorytm przewidział "tylko" 495 na 500 razy, czy jutro giełda pójdzie w górę, czy w dół. Analiza takich algorytmów nie polega na ocenie "źle - dobrze", lecz na sprawdzeniu, czy dostatecznie często jesteśmy dostatecznie blisko dostatecznie dobrej odpowiedzi.

Portale społecznościowe, a od niedawna również wyszukiwarki zaprzęgają tymczasem do wyszukiwania inteligencję ludzką. Zabawę użytkownika w oznaczanie na zdjęciach swoich znajomych wykorzystuje się do uczenia algorytmów rozpoznających twarze. Lub choćby zadaje się użytkownikowi pytanie: "czy ta odpowiedź była trafna?".

Po pierwsze - to też klasyka. Interakcja z kimś, kto wie lepiej niż dopiero budowany system, to normalna technika zdobywania wiedzy.

Po drugie, działają tu bardzo ciekawe klasy algorytmów uczących się, które zmieniają swoją strukturę - mowa na przykład o tzw. algorytmach genetycznych, sieciach neuronowych lub algorytmach "mrówkowych", ­opartych o zachowania tłumne. Otóż ostateczną strukturę udzielania odpowiedzi budują one w sposób w pewnym sensie losowy. Choćby w przypadku algorytmów genetycznych, po to, żeby znaleźć najlepsze rozwiązanie, wybiera się losowo zbiór obiektów, który może je tworzyć, i sprawdza, czy tak faktycznie jest. Jeśli nie, to nieco się te obiekty zmienia, również losowo, i sprawdza ponownie, czy po zmianie jesteśmy bliżej rozwiązania.

Jak w ewolucji?

To w rzeczy samej algorytmy ewolucyjne, tyle że czuwa nad nimi dozorca - funkcja oceniająca, czy wybrać ten, czy inny podzbiór zmodyfikowanych obiektów. Projektowanie tego typu algorytmów w dużym stopniu polega na trafnym doborze owej funkcji oceny.

Ale trzeba też dysponować dostatecznie dużą liczbą próbek, na których algorytm zakodowany np. jako sieć neuronowa będzie się uczył. Za pierwszym razem nie będzie on wiedział, czy np. kolor zgniłozielony to jeszcze zielony, czy już brązowy. Ale jeśli dostarczy się mu miliona odpowiedzi dla różnych odcieni, algorytm wyrobi sobie dość dobrą opinię na temat tego, gdzie przebiega granica między zielenią a brązem.

A próbek dostarczają właśnie użytkownicy?

W zależności od dziedziny i zastosowań. Rozpoznawanie twarzy na Facebooku to rzecz dość błaha w porównaniu np. z systemami wspomagającymi diagnozy lekarskie. Tu funkcje oceny sprawdza się na rzeczywistych bazach przypadków lekarskich. A to już rzecz na innej skali powagi niż to, czy Facebook bądź Picasa nauczą się poprawnie rozpoznawać kolegę Kazia. Wiele z technologii, które zaczynają dziś służyć codziennym użytkownikom, ma źródła w poważnych pracach naukowych, które rozwijane były, słowo honoru, bez myślenia o Facebooku.

Nasza praca, relacje i codzienne czynności opierają się o pracę maszyn, których zasady funkcjonowania nie potrafimy sobie wyobrazić. Wytłumaczenie, jak działa lokomotywa parowa, było chyba łatwiejsze od wyjaśnienia, jak działa procesor. Czy niepokoi Pana deficyt zrozumienia użytkownika dla technologii?

O ile dla nas dzisiaj zrozumienie zasady działania maszyny parowej nie jest niczym szczególnym, to pamiętajmy, że kiedyś takich maszyn nie było i trzeba je było dopiero wynaleźć. A lokomotywa to nie tylko podstawowa idea działania na tłok pary pod ciśnieniem, ale też tysiące precyzyjnych części zrobionych tak, a nie inaczej - i tu nie wiemy już, dlaczego. Rower też niby jest prostą maszyną, ale proporcje i rozmiary jego elementów są dziełem specjalistów od fizjologii, medycyny, mechaniki. Z grubsza wiemy, jak działa przekładnia, ale nie mamy pojęcia, czy w łożysku ma być 13, czy 17 kulek. Nie czuję się jednak tym zaniepokojony - wierzę, że i nad każdym procesorem, i nad każdą śrubką, której używam, czuwali ludzie, którzy się na tym znają. A to, że wiedza potrzebna do tworzenia towarzyszących nam dziś maszyn jest coraz bardziej wyrafinowana, wynika po prostu z ogromnego jej rozwoju.

Żyjemy też w czasach, w których ścisła matematyka - rdzeń naszych technologii - zrodziła fenomeny humanistyczne czy socjologiczne: wpłynęła nie tylko na jakość uprawiania nauki, ale też na komunikację społeczną, więzi międzyludzkie...

Ależ nie ma w tym nic dziwnego! Nowe narzędzia otwierają nowe możliwości. W 1983 r. toczyłem długą dyskusję z małżeństwem malarzy - o tym, czy na ekranie komputera da się tworzyć prawdziwe obrazy. Broniłem wtedy poglądu, że tak, dziś już oczywistego i dla moich ówczesnych adwersarzy. I pędzlem na płótnie, i myszką na komputerze da się tworzyć zarówno wielką sztukę, jak i chłam.

Ale też narzędzia nas kształtują. Niedawno "Science" opublikował artykuł o tzw. efekcie Google: otóż mniej - a na pewno inaczej - dziś zapamiętujemy, delegując na wyszukiwarkę zadania, którymi zwykle zajmowała się nasza pamięć. Nie musimy pamiętać, bo mamy pod ręką Google.

"Iliada" najpierw mogła być powtarzana ustnie, potem dopiero spisana, jeszcze później powielana w druku. Technologia jej przekazu się zmieniała. To, co uważamy za wiedzę niezbędną do przechowywania w głowie, też się zmieniało na przestrzeni wieków.

Chciałbym teraz móc powiedzieć, że ponieważ łatwo dostępna jest nam dziś wiedza rutynowa, prosta informacja, to więcej miejsca zostawiamy sobie na kreatywną inteligencję. Ale to nie zawsze prawda. Zdarzyło mi się - na szczęście nie w Polsce - że gdy miałem zapłacić 10,25 funta, podałem banknot 20-funtowy i 25 pensów, a kasjerka nie mogła wyjść ze zdumienia, że maszyna kazała wydać tak równą resztę.

Sama zmiana nie jest niczym niezwykłym - skala i dostępność informacji, owszem. Zjawisko to ma też bardzo negatywne konsekwencje. Jestem przerażony, gdy dziecko, zamiast odpowiedzieć, ile jest 6 razy 7, wstukuje to w kalkulator w komórce.

Bo jeśli wszyscy będziemy chcieli korzystać z Wikipedii, nie będzie jej miał kto pisać?

Z Wikipedii korzystamy w dziedzinach, w których nie potrafimy jej współtworzyć, zaś piszemy w tych dziedzinach, w których z naszej wiedzy mogą korzystać inni. Jesteśmy coraz bardziej wyspecjalizowani nie dlatego, że robimy się coraz głupsi i mamy coraz węższe horyzonty, tylko dlatego, że tak bardzo przyrasta ilość wiedzy.

Na przełomie lat 70. i 80., gdy zaczynałem swoją informatyczną przygodę, miałem wrażenie, że właściwie każdy wykład rozumiem i w każdy temat mogę wejść. Dziś już nie sposób być tak zarozumiałym. Informatyka rozrosła się niepomiernie, a dystans od początków studiów do problemów, które rozwiązuje np. Paweł Parys, jest ogromny - co nie znaczy, że nie da się go szybko pokonać. Przykład laureatów Nagrody im. Lipskiego najlepiej o tym świadczy.

Mamy w Polsce świetnych młodych informatyków. Czego nam brakuje, żeby nad Wisłą wyrosła druga Krzemowa Dolina?

Niczego poza pieniędzmi, pieniędzmi i jeszcze raz pieniędzmi. Mechanizmy, które sprzyjają przekładaniu potencjału naukowego na praktyczne efekty, są u nas w powijakach. Jest raczej wyjątkiem niż regułą, że dobre pomysły prowadzą do rzeczywistych prób ich wdrożenia na istotną skalę.

Skądinąd w świecie również nie zawsze zwyciężają najlepsze pomysły i to nie zawsze one tworzą standardy, z których potem wszyscy musimy korzystać...

Niewątpliwie, mamy świetnych studentów, choć ów dystans, o którym przed chwilą mówiłem, powiększa się w obie strony. Średni poziom wiedzy matematycznej i informatycznej, którą młodzi ludzie wynoszą ze szkoły, jest, delikatnie mówiąc, kiepski. Przy czym nie mówię tu o tzw. "informatyce" rozumianej jako umiejętność posługiwania się komputerem, z czym dzisiejsza młodzież niemal się rodzi, tylko o rzetelnej wiedzy matematycznej, umiejętności abstrakcyjnego myślenia i rozwiązywania problemów. Ale choć średnia się zmienia, to na szczęście czołówka zostaje: co roku na naszym Wydziale Matematyki, Informatyki i Mechaniki UW zaczyna studia grupa kilkudziesięciu młodych ludzi, którzy będą mogli podbić świat. To nie przypadek - zawdzięczamy to całemu systemowi, który funkcjonuje za sprawą grupy zapaleńców: to olimpiady przedmiotowe, z informatyczną i matematyczną na czele, inicjatywy takie jak "Potyczki Algorytmiczne", zawody dla młodych studentów czy stypendia Krajowego Funduszu na rzecz Dzieci. Pozwala to zarazić młodych ludzi informatyką, a następnie skutecznie się nimi opiekować.

Świetnie, że wielu z nich poświęca potem swój talent, zapał i pracę badaniom w zakresie informatyki. Najlepsi z nich, jak laureaci dotychczasowych edycji Nagrody im. Lipskiego, legitymują się widocznym w świecie dorobkiem naukowym, prowadzą badania i osiągają wyniki na najwyższym światowym poziomie - biorą udział w wielkim rozwoju informatyki we wszystkich, także bardzo praktycznych jej aspektach.

PROF. ANDRZEJ TARLECKI jest informatykiemw, pracuje na Uniwersytecie Warszawskim i w Instytucie Podstaw Informatyki PAN. Zajmuje się matematycznymi podstawami informatyki i ich zastosowaniem do tworzenia oprogramowania najwyższej jakości. Autor ponad 70 publikacji naukowych, członek Academia Europea. Przewodniczący Rady Nagrody im. Witolda Lipskiego dla młodych naukowców w zakresie informatyki.

Dziękujemy, że nas czytasz!

Wykupienie dostępu pozwoli Ci czytać artykuły wysokiej jakości i wspierać niezależne dziennikarstwo w wymagających dla wydawców czasach. Rośnij z nami! Pełna oferta →

Dostęp 10/10

  • 10 dni dostępu - poznaj nas
  • Natychmiastowy dostęp
  • Ogromne archiwum
  • Zapamiętaj i czytaj później
  • Autorskie newslettery premium
  • Także w formatach PDF, EPUB i MOBI
10,00 zł

Dostęp kwartalny

Kwartalny dostęp do TygodnikPowszechny.pl
  • Natychmiastowy dostęp
  • 92 dni dostępu = aż 13 numerów Tygodnika
  • Ogromne archiwum
  • Zapamiętaj i czytaj później
  • Autorskie newslettery premium
  • Także w formatach PDF, EPUB i MOBI
89,90 zł
© Wszelkie prawa w tym prawa autorów i wydawcy zastrzeżone. Jakiekolwiek dalsze rozpowszechnianie artykułów i innych części czasopisma bez zgody wydawcy zabronione [nota wydawnicza]. Jeśli na końcu artykułu znajduje się znak ℗, wówczas istnieje możliwość przedruku po zakupieniu licencji od Wydawcy [kontakt z Wydawcą]

Artykuł pochodzi z numeru TP 50/2011