04

Nasze Badania

Inteligentne algorytmy i struktury danych

Piotr Sankowski

Lider Grupy Badawczej

Polski informatyk, doktor habilitowany nauk matematycznych. Specjalizuje się w algorytmach, w szczególności w zastosowaniach metod algebraicznych w algorytmach grafowych. Profesor nadzwyczajny Instytutu Informatyki Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

Explainable Algorithmic Tools

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ż może zrobić to sam człowiek, np. poprzez popełnianie mniejszej ilości błędów. Obietnica ta  jest jednak daleka od realizacji w zadowalającym zakresie na obecnym rozwoju algorytmów. Główny problem polega na tym, że algorytmy nie wyjasniają 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, jak Deep Blue gra w szachy. 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ń. Robiąc to musimy zagwarantować, że algorytmy będą zrozumiałe przez osoby, które ich używają, bo 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 algorytmu. Co więcej, algorytm może być używany przez kogoś, kto nie ma odpowiedniej wiedzy algorytmicznej, dlatego wyjaśnienie samej decyzji 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. Dzieje się tak, ponieważ inne możliwe opcje są gorszym wyborem!

Algorytmy stają się coraz bardziej powszechne w naszym życiu z powodu postępującej cyfryzacji, której tempo zostało dodatkowo przyspieszone poprzez obecną sytuację pandemiczną. Stąd potrzeba wyjaśnienia ich wyników staje się bardziej immanentna. Niniejsze badanie ma na celu dostarczenie koncepcji narzędzi, które umożliwiłyby wyjaśnienie najbardziej podstawowych problemów optymalizacyjnych, np. problemu skojarzeń. Skojarzenia są 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.

Learned Data-Structures

Sztuczna inteligencja i algorytmy to dwa obszary informatyki, które przez wiele lat rozwijały się oddzielnie. Dopiero od niedawna obserwujemy coraz więcej interakcji między tymi dwoma dziedzinami. Interakcje te prowadzą do wzajemnego oddziaływania i rozwoju 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ń, a 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ć praktyczne efekty.

ZWIĘKSZAMY POTENCJAŁ BRI W DZIEDZINIE SZTUCZNEJ INTELIGENCJI

dr hab. PIOTR SANKOWSKI

CEO IDEAS NCBR

Algorithmic Tools for Data Science and ML

Dane z pewnością 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ć do tego 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. Podobnie grafy są 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śći, których nie można było pokonać przy użyciu klasycznych technik i modeli. W szczególności będziemy pracować nad nowymi narzędziami algorytmicznymi, które poprawią wydajność zarówno równoległych, jak i nierównoległych algorytmów wykorzystywanych w data science.

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

dr hab. PIOTR SANKOWSKI

CEO IDEAS NCBR

Piotr Sankowski

Lider Grupy Badawczej

Doświadczenie zawodowe

  • 2021- do dzisiaj Prezes IDEAS NCBR – instytut naukowo-badawczy w obszarze sztucznej inteligencji i cyfrowej ekonomii
  • 2021 – do dzisiaj Dyrektor Naukowy MIM Solutions – spin-off utworzonego wraz z Uniwersytetem Warszawskim
  • 2015-2021 Dyrektor Generalny MIM Solutions – spin-off utworzonego wraz z Uniwersytetem Warszawskim
  • 2010 – do dzisiaj Profesor Nadzwyczajny w Instytucie Informatyki na Uniwersytecie Warszawskim
  • 2006-2010 Adiunkt w Instytucie Informatyki na Uniwersytecie Warszawskim
  • 2009-2010 Post-doc na Uniwersytecie “Sapienza” w Rzymie
  • 2008 Post-doc w Szwajcarskim Federalnym Instytucie Technologii w Zurychu
  • 2006-2008 Post-doc na Uniwersytecie “Sapienza” w Rzymie
  • 2005-2006 Asystent w Instytucie Informatyki na Uniwersytecie Warszawskim

Nagrody i osiągnięcia

  • 2018 Laureat indywidualnej nagrody Crystal Brussels Sprout Award
  • 2018 Laureat Nagrody Narodowego Centrum Nauki
  • 2017 Profesor wizytujący w Simons Institute for the Theory of Computing w semestrze “Bridging Continuous and Discrete Optimization”
  • 2016 Profesor wizytujący w Simons Institute for the Theory of Computing w semestrze „Algorithms and Uncertainty”
  • 2011 Nagroda Best Poster Award – 4. Międzynarodowa Konferencja – Web Search and Data Mining (WSDM ’11)
  • 2010-2015 Stypendium „Pomysły dla Polski” przyznane przez Fundację na rzecz Nauki Polskiej (FNP)
  • 2010 Nagroda naukowa II stopnia Ministra Szkolnictwa Wyższego
  • 2005 Lureat nagrody im. Witolda Lipskiego dla Młodych Naukowców Informatyki
  • 2005 Stypendium „Zostań z Nami” przyznane przez tygodnik Polityka
  • 2005 Nagroda Best Student Paper Award — 13. Europejskie Sympozjum na temat Algorytmów(ESA’ 05)
  • 2004 Nagroda Best Student Paper Award – 45. Sympozjum na temat Foundations of Computer Science (FOCS’ 04)
  • 2004 Nagroda Best Student Paper Award — 12. Europejskie Sympozjum na temat Algorytmów(ESA’ 04)

Granty

  • 2018-2023 Lider grupy badawczej – grant Europejskiej Rady ds. Badań Naukowych – ERC CoG Grant 772346 – Towards Unification of Algorithmic Tools
  • 2015-2018 Lider projektu – grant Narodowego Centrum Badań i Rozwoju w Polsce – System Przewidywania Przestępczości i Zarządzania Policją
  • 2015-2018 Lider grupy badawczej – grant Narodowego Centrum Nauki –
    nr 2014/13/B/ST6/01811 – Efficient Planar Graph Algorithms
  • 2015-2017 Lider grupy badawczej – grant Europejskiej Rady ds. Badań Naukowych – ERC PoC Grant 680912 – Practical Approximation Algorithms – Proof of Concept
  • 2012-2016 Lider projektu – EU-FET 317532 – Foundational Research on MULTIlevel comPLEX networks and systems
  • 2010-2015 Lider grupy badawczej – grant Europejskiej Rady ds. Badań Naukowych – ERC StG Grant 259515 – Practical Approximation Algorithms
  • 2009-2012 Lider grupy badawczej – grant Narodowego Centrum Nauki – nr N N206 355636 – Approximation Algorithms with Bounded Resources
  • 2006-2007 Lider grupy badawczej – grant Komitetu Badań Naukowych – nr 1 PO3A 018 30 – Algebraic Graph Algorithms

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.

Skip to content