Przejdź do treści Wyszukiwarka

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.

Kluczem do efektywnego transferu innowacji związanych z przełomowymi technologiami takimi jak sztuczna inteligencja są innowatorzy, tzn. osoby, które z jednej strony rozumieją i współtworzą badania naukowe na światowym poziomie, a z drugiej strony umieją i chcą współpracować z przemysłem.



Prof. Piotr Sankowski
Prezes IDEAS NCBR

Lider grupy badawczej


Piotr Sankowski

W swojej pracy badawczej koncentruje się na problemach praktycznego wykorzystania algorytmów, poczynając od zastosowań ekonomicznych, poprzez uczące się struktury danych, a na równoległych algorytmach dla data science kończąc. W 2005 r. otrzymał doktorat z informatyki, a w 2009 r. habilitację oraz doktorat z fizyki. Odbył staże post-doktorskie w Szwajcarskim Federalnym Instytucie Technologii w Zurychu i na Uniwersytecie Sapienza w Rzymie.

Członek ELLIS Society.

 

Piotr Sankowski współtworzył konferencję Highlights of Algorithms zorganizowaną w 2016 r. w Paryżu, a w 2017 r. w Berlinie. Był przewodniczącym PC Track A 24th Annual European Sympozium on Algorithms (ESA 2016), która jest największą europejską konferencją na temat algorytmów. W 2018 r. został laureatem indywidualnej nagrody Kryształowej Brukselki oraz Nagrody Narodowego Centrum Nauki. Dwukrotnie był profesorem wizytującym w Simons Institute for the Theory of Computing  na Uniwersytecie w Berkeley.. W latach 2010-2015 otrzymał stypendium „IDEE dla Polski” przyznane przez Fundację na rzecz Nauki Polskiej (FNP), a w 2011 r. nagrodę Best Poster Award na 4. Międzynarodowej Konferencji Web Search and Data Mining (WSDM’11).

 

Jest pierwszym Polakiem, który otrzymał cztery granty Europejskiej Rady ds. Badań Naukowych (ERC – European Research Council): ERC Starting Independent Researcher Grant (2010), ERC Proof of Concept Grant (2015, 2023), ERC Consolidator Grant (2017). W latach 2015-2018 jako lider grupy badawczej prowadził badania w ramach grantu Narodowego Centrum Nauki „Efficient Planar Graph Algorithms” oraz był liderem projektu badawczego w ramach grantu Narodowego Centrum Badań i Rozwoju. Jest współzałożycielem spin-offu MIM Solutions, w którym od 2021 r. pełni funkcję dyrektora naukowego. Od marca 2021 r. jest również prezesem zarządu IDEAS NCBR.

Inne grupy i zespoły badawcze

  • Diagnostyka patologii medycznych Naszym celem jest kształtowanie przyszłości diagnostyki medycznej poprzez opracowanie rozwiązań opartych na sztucznej inteligencji. W pracach badawczych koncentrujemy się na analizie obrazowych danych medycznych, takich jak dane radiologiczne oraz histopatologiczne (digital pathology).
    Żaneta Świderska-Chadaj
  • Uczenie maszynowe zero-waste w wizji komputerowej Zarówno nauka, jak i przemysł chętnie sięgają po rozwiązania wykorzystujące modele uczenia maszynowego, głównie głębokie sieci neuronowe.
    Tomasz Trzciński
  • Leśnictwo precyzyjne Zastosowanie danych teledetekcyjnych w pozyskiwaniu informacji o lasach ma swoją długą, już około 100-letnią, historię.
    Krzysztof Stereńczak