Inteligentne algorytmy i struktury danych

Wyjaśnialne algorytmy

Algorytmy, szczególnie te wykorzystywane w uczeniu maszynowym, dają szanse na podejmowanie lepszych decyzji niż te, które podejmuje człowiek. W wielu przypadkach, nawet koncepcyjnie, proste algorytmy mogą dostarczać odpowiedzi lepszej jakości niż człowiek, np. popełniając mniej błędów.

Obietnica ta jest jednak daleka od spełnienia w zadowalającym zakresie na obecnym poziomie rozwoju algorytmów. Główny problem polega na tym, że algorytmy nie wyjaśniają swoich decyzji, a dla użytkownika nie jest jasne, dlaczego proponowana przez algorytm odpowiedź jest prawidłowa. Nawet jeśli próbujemy odtworzyć powody, dla których dana decyzja została podjęta przez algorytm, to te powody mogą być niezrozumiałe dla ludzi. Problem ten można najprościej zilustrować przykładem Deep Blue, komputera grającego w szachy stworzonego przez IBM. Człowiek nie ma szans zrozumieć jego “rozumowania” dla konkretnego ruchu.

Możemy prowadzić w nieskończoność filozoficzny spór, czy Deep Blue faktycznie rozumie grę w szachy, czy też nie. Jednakże problem ten staje się kluczową kwestią podczas wdrażania rozwiązań algorytmicznych w świecie rzeczywistych zastosowań. Musimy zagwarantować, że algorytmy będą zrozumiałe dla osób, które ich używają. W przeciwnym razie użytkownicy odmówią wykonywania decyzji podjętych przez algorytmy. Co zaskakujące, obecnie nie ma dobrych narzędzi do dostarczania wyjaśnień nawet dla najbardziej podstawowych algorytmów. Na przykład niektórzy często wątpią, czy GPS znalazł najszybszą trasę i wolą sami dokonywać alternatywnych wyborów. Dzieje się tak pomimo faktu, że znalezienie najkrótszej drogi dotarcia jest dobrze zbadanym problemem i możemy udowodnić, że algorytm działa poprawnie. Problem polega raczej na wyjaśnieniu użytkownikowi, dlaczego proponowane przez algorytm rozwiązanie jest najlepsze, a nie jak działa sam algorytm. Co więcej, algorytm może być używany przez kogoś, kto nie ma odpowiedniej wiedzy algorytmicznej, dlatego wyjaśnienie toku rozumowania staje się jeszcze bardziej istotne.

Dobra informacja brzmi: nie trzeba latami studiować algorytmów, aby przekonać się, że działają one we właściwy sposób. Na przykład jednym z głównych powodów, dla których Google Maps pokazują alternatywne trasy, jest wyjaśnienie użytkownikowi, dlaczego zaproponowane rozwiązanie jest najlepsze. Algorytmy stają się coraz bardziej powszechne w naszym życiu z powodu postępującej cyfryzacji, której tempo zostało dodatkowo przyspieszone przez pandemię COVID-19. Potrzeba wyjaśnienia ich wyników staje się więc bardziej nagląca. Prace naszej grupy badawczej mają na celu dostarczenie koncepcji narzędzi, które umożliwiłyby wyjaśnienie najbardziej podstawowych problemów optymalizacyjnych, np. problemu skojarzeń. Są one kluczowym wyzwaniem w badaniach operacyjnych i są używane do opisu dostosowania ofert pracy do pracowników, miejsc pracy do serwerów, wyświetleń stron do reklam, mieszkańców do szpitali, studentów do uniwersytetów lub domów do najemców.

Wyuczone struktury danych

Sztuczna inteligencja i algorytmy to dwa obszary informatyki, które przez wiele lat rozwijały się oddzielnie. Dopiero od niedawna obserwujemy ich coraz częstsze przenikanie się, które sprzyja rozwojowi nowych narzędzi po obu stronach. Z jednej strony, jesteśmy świadkami pojawienia się narzędzi algorytmów ML, które zostały w pełni przeanalizowane z teoretycznego punktu widzenia, np. przybliżone wyszukiwanie najbliższego sąsiada (approximate nearest neighbor search – NNS). Z drugiej strony narzędzia ML wchodzą jako komponenty wewnętrzne do podstawowych struktur danych lub najnowocześniejszych algorytmów aproksymacyjnych, dzięki czemu powstają rozwiązania o lepszych właściwościach praktycznych, np. indeksy. Te nowe konstrukcje hybrydowe nazywane są wyuczonymi strukturami danych (Learned Data-Structures – LDS).

Ponieważ prace nad tymi pomysłami dopiero się rozpoczęły, brakuje nam odpowiednich narzędzi do wdrażania najnowocześniejszych rozwiązań; tym samym badania nad nowymi narzędziami i modelami są utrudnione. Problem ten można rozwiązać, tworząc nowe algorytmy i struktury danych wraz z biblioteką oprogramowania, która pozwoliłaby na łatwe komponowanie różnych bloków. W ten sposób można udowodnić, że istnieją narzędzia do wypełniania luki między teorią a praktyką w algorytmach i pokazać, że nowe osiągnięcia teoretyczne mogą mieć rzeczywiste zastosowanie.

Algorytmy data science i ML

Analiza danych staje się motorem napędowym rozwoju technologicznego. Aby jednak móc wyciągać sensowne wnioski z tych wciąż rosnących zbiorów informacji, musimy zaprojektować skuteczne algorytmy. Nasz projekt ma na celu rozwiązanie fundamentalnych problemów pojawiających się w kontekście przetwarzania ogromnych zbiorów danych. Długoterminowym celem jest opracowanie technik projektowania bardzo szybkich i możliwie skalowalnych algorytmów.

Grafy to najczęstszy sposób przechwytywania struktur i relacji w danych, dlatego są często wykorzystywane w data science. Najbardziej znane przykłady to analiza sieci społecznościowych, np. wykrywanie społeczności lub procesy kaskadowe. Grafy są również często używane do reprezentowania wiedzy, np. za pomocą grafów wiedzy. Takie podejście było widoczne w przejściu z perspektywy relacyjnej na grafową w bazach danych. Te i inne przykłady pokazują, że grafy i algorytmy grafowe są podstawowymi narzędziami do reprezentowania i analizowania danych. Jednak rozmiary bieżących zbiorów danych wymagają zastosowania obliczeń równoległych, ponieważ nawet przechowywanie ich na jednej maszynie jest często niemożliwe. Na przykład sieć WWW składa się z ponad 5 miliardów stron, graf wiedzy Google zawiera 800 miliardów faktów dotyczących 8 miliardów podmiotów, podczas gdy Facebook ma ponad 2 miliardy aktywnych użytkowników dziennie.

Jak widać, dane są zwykle rozproszone na wielu komputerach, a obliczenia muszą być wykonywane równolegle. Systemy ze świata rzeczywistego są modelowane w ramach modelu Massively Parallel Computation (MPC), w bibliotekach takich jak MapReduce, Hadoop, Spark lub Flume. Chociaż od lat badane są różne modele obliczeń równoległych, to MPC daje zupełnie nowe możliwości i wymagania. Obliczenia MPC są wykonywane w rundach synchronicznych, ale implementacja tych rund w rzeczywistych systemach zajmuje dużo czasu. Jedna runda trwa o rzędy wielkości dłużej niż w klasycznym systemie typu Cray. Dlatego chcielibyśmy rozwiązywać problemy, w szczególności te związane z grafami, w jak najmniejszej liczbie rund. Dążymy do zaprojektowania metod pokonania złożoności, których nie można było pokonać przy użyciu klasycznych technik i modeli. Skupimy się na nowych narzędziach algorytmicznych, które poprawią wydajność zarówno równoległych, jak i nierównoległych algorytmów wykorzystywanych w data science.

Linki

Google Scholar

ELLIS member

E-mail

Papers and publications