04

Nasze Badania

Inteligentne algorytmy i struktury danych

Piotr Sankowski

Lider Grupy Badawczej

Polski informatyk, doktor habilitowany nauk matematycznych. Profesor nadzwyczajny Instytutu Informatyki Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego. Członek ELLIS Society.

Wyjaśnialne algorytmy

Algorytmy, szczególnie te wykorzystywane w uczeniu maszynowym, dają szanse na podejmowanie lepszych decyzji niż ludzkie. 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 ta 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.

W przypadku gier 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ń. Adresując realne problemy musimy zagwarantować, że algorytmy będą zrozumiałe przez osoby, które ich używają. W przeciwnym razie użytkownicy odmówią przestrzegania ich decyzji. Co zaskakujące, obecnie nie ma dobrych narzędzi do dostarczania wyjaśnień nawet dla najbardziej podstawowych algorytmów. Na przykład niektórzy z nas często wątpią, czy GPS znalazł najszybszą trasę i wolą sami dokonać 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. Dobrą informacją jest fakt, że 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. Niniejsze badanie ma na celu dostarczenie koncepcji narzędzi, które umożliwiłyby wyjaśnienie najbardziej podstawowych problemów optymalizacyjnych, np. problemu skojarzeń. Są one kluczowym problemem 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.

Kształcenie naukowców, którzy umieją wypełniać lukę między badaniami podstawowymi i stosowanymi było jedną z głównych przesłanek do powołania centrum badawczego – dedykowanego sztucznej inteligencji i ekonomii cyfrowej

Prof. Piotr Sankowski

CEO IDEAS NCBR

ALGORYTMY DLA DATA SCIENCE i ML

Dane stają się motorem napędowym przyszłości. Aby jednak móc wyciągać sensowne wnioski z tych wciąż rosnących zbiorów informacji, musimy zaprojektować w tym celu skuteczne algorytmy. Projekt ten 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 500 miliardów faktów dotyczących 5 miliardów podmiotów, podczas gdy Facebook ma 1,88 miliarda aktywnych użytkowników dziennie.

Wobec powyższego 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), 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. Mając to wyzwanie na uwadze, projekt ten ma na celu zaprojektowanie 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.

Publikacje członków zespołów w ramach prac badawczych prowadzonych w IDEAS NCBR

2022

Nazwa konferencji Data Link Tytuł dokumentu Autorzy
UAI (Uncertainty in Artificial Intelligence), Eindhoven, the Netherlands
1-4 August 2022
Improved Feature Importance Computation for Tree ModelsBased on the Banzhaf Value
Tomasz Michalak
STOC (Symposium on Theory of Computing), Rome, Italy
20-24 June 2022
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
Adam Karczmarz, Michał Pawłowski, Anish Mukherjee, Mathieu Mari, Piotr Sankowski
SODA (Symposium on Discrete Algorithms)
A 3-Approximation Algorithm for Maximum Independent Set of Rectangles
Mathieu Mari
NeurIPS, New Orlean, the USA
27 November - 2 December 2022
Subgoal Search For Complex Reasoning Tasks
Tomasz Odrzygóźdź
AlgPiE 2022, Będlewo
20-26 August 2022
Subquadratic Dynamic Path Reporting against an Adaptive Adversary
Anish Mukherjee, Adam Karczmarz, Piotr Sankowski
Online matching with delays & Online busy-time scheduling
Runtian Ren
MLinPL
04.11.2022 - 06.11.2022
Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Tomasz Odrzygóźdź
Fine-Grained Conditional Computation in Transformers
Sebastian Jaszczur
Improved Feature Importance Computation for Tree Models Based on the Banzhaf Value
Piotr Sankowski, Adam Karczmarz, Tomasz Michalak

Piotr Sankowski

Lider Grupy Badawczej

Doświadczenie zawodowe

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 roku otrzymał doktorat z informatyki, a w 2009 roku habilitację oraz doktorat z fizyki na Polskiej Akademii Nauk. Odbył on staże post-doktorskie w Szwajcarskim Federalnym Instytucie Technologii w Zurychu i na Uniwersytecie „La Sapienza” w Rzymie.

Nagrody i osiągnięcia

Piotr Sankowski współtworzył konferencję Highlights of Algorithms zorganizowaną w 2016 roku 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 roku 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. W latach 2010-2015 otrzymał stypendium „IDEE dla Polski” przyznane przez Fundację na rzecz Nauki Polskiej (FNP), a w 2011 roku nagrodę Best Poster Award na 4. Międzynarodowej Konferencji Web Search and Data Mining (WSDM’11).

Granty

Jest pierwszym Polakiem, który otrzymał trzy granty Europejskiej Rady ds. Badań Naukowych (ERC – European Research Council): ERC Starting Independent Researcher Grant (2010), ERC Proof of Concept Grant (2015), 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 roku pełni funkcję dyrektora naukowego. Od marca 2021 roku jest również prezesem zarządu IDEAS NCBR.

NASZE BADANIA

Algorytmy, szczególnie te wykorzystywane w uczeniu maszynowym, dają szanse na podejmowanie lepszych decyzji niż ludzkie.

Technologia Blockchain została wprowadzona w 2008 roku. Pod tą nazwą rozumie się zwykle protokoły kryptograficzne służące do osiągania konsensusu na dużą skalę w sieciach rozproszonych.

Zarówno nauka, jak i przemysł chętnie sięgają po rozwiązania wykorzystujące modele uczenia maszynowego, głównie głębokie sieci neuronowe.

Skip to content