Szymon
Grabowski
Propozycje tematów prac dyplomowych
magisterskich
na rok akademicki 2023 / 2024
1.
(NOWOŚĆ!) Aspekty
implementacyjne lasów losowych
(Implementation aspects of random forests)
Las losowy (ang. random
forest) jest kolekcją drzew decyzyjnych,
działających z różnymi (losowymi) podzbiorami zbioru uczącego i/lub różnymi
podzbiorami jego cech. (Istnieje
wiele wariantów RF, p. np. (Lior Rokach,
Decision forest: Twenty years of research,
2016, https://www.sciencedirect.com/science/article/pii/S1566253515000561)).
W ramach pracy należy zaimplementować
(niskopoziomowo) las losowy, z naciskiem na wydajność (i ewent. oszczędność
pamięci), zwłaszcza na etapie budowy. Eksperymenty na zbiorach różnej wielkości
używanych w literaturze (https://www.kaggle.com/datasets?tags=13302-Classification).
Możliwe idee:
·
wybrane ID obiektów dla każdego węzła każdego drzewa pamiętamy na górnych
poziomach drzewa (gdzie obiektów jest zwykle dużo) jako ustawione bity w
wektorze bitowym, a nie liczby typu int; na dolnych
poziomach drzewa, gdy w węzłach jest już niewiele obiektów, stosujemy (bardziej
tradycyjnie) listy intów,
·
(dla danych numerycznych) sortujemy obiekty po każdej cesze, a
następnie jako punkty podziału rozpatrujemy tylko średnie par kolejnych
punktów, których klasy się różnią (idea wspomniana np. w rozdz. 18.3.6 monografii (Stuart Russell i Peter Norvig, Artificial Intelligence. A Modern Approach. Third Edition, 2010)),
·
powtórne wykorzystanie roboczych rejonów pamięci,
·
...lub wczesne zwalnianie niewykorzystywanych później tablic, dla
oszczędności pamięci,
·
oszczędna reprezentacja klasy danego obiektu (np. jeśli klas jest £ 4, to można ID każdej klasy
zapisywać na 2 bitach) i szybkie (bitowo-równoległe) zliczanie rozkładu
przynależności obiektów do klas,
·
praca wielowątkowa.
2.
(NOWOŚĆ!) Wydajny
algorytm dla planszowej gry logicznej „Blokus”
wykorzystujący logikę bitową
(An efficient algorithm for playing the logic board
game “Blokus” based on bit logic)
Blokus (https://en.wikipedia.org/wiki/Blokus)
to gra inspirowana łamigłówką pentomino, dla 2, 3 lub
4 graczy, polegająca na dostawianiu na planszy klocków swojego koloru w celu
blokowania ruchów przeciwnikom. Celem pracy jest zaprojektowanie i
zaimplementowanie algorytmu, w którym przeszukiwanie planszy będzie
wykorzystywało operacje bitowe (typu OR, AND) dla słów maszynowych, co umożliwi
szybkie znajdowanie dozwolonych w danej pozycji ruchów.
Pożądana (ale niekonieczna) funkcjonalność to
również implementacja i testy platformy dla programów (botów) grających w Blokus.
3.
Ocena jakości
danych dla uczenia maszynowego
(Data quality assessment for machine learning)
Rzeczywiste
zbiory danych (np. z platformy Kaggle) stosunkowo
często zawierają błędy lub niekonsekwencje, wynikające np. z niechlujnego
gromadzenia danych. Przykładowo, liczby (w wybranych lub wszystkich kolumnach
danych tabularycznych) mogą być zapisywane jako stringi,
wyniki pomiarów tej samej wartości fizycznej mogą używać różnych jednostek, zaś
brakujące wartości mogą być kodowane przy użyciu arbitralnej (i ryzykownej) konwencji,
np. -99999. Niektóre „zjawiska” w danych niekoniecznie oznaczają błąd, lecz
należy je wykryć do dalszej analizy, np. powtarzające się (jak często?)
wartości całych wierszy/rekordów. Jednym z (niedoskonałych) sposobów wykrywania
problematycznych danych (i ich oczyszczania) jest użycie schematu (ang. schema), ale nie
zawsze jest on dostępny, a ręczna jego budowa może być pracochłonna.
Celem
pracy jest
·
zaproponowanie i
przetestowanie reguł ad-hoc służących do analizy danych (np. detekcji outlierów, niekonsekwentnego użycia formatu daty i czasu,
proporcji liczby wystąpień elementu najczęstszego, tj. mody, do liczby
wszystkich obiektów),
·
próba
automatycznej budowy reguł,
·
implementacja wybranych technik oszczędnego
pamięciowo wyznaczania kwantyli (np. mediany) próbek,
m.in. dla modelu strumieniowego.
Istnieje
już dość bogata literatura przedmiotu, m.in.
https://sites.cs.ucsb.edu/suri/psdir/ency.pdf
https://www.vldb.org/vol11/p1781-schelter.pdf
http://learningsys.org/nips17/assets/papers/paper_19.pdf
https://arxiv.org/abs/2203.10384
Oraz
narzędzia typu „data linter”:
https://github.com/brain-research/data-linter
https://github.com/moj-analytical-services/data_linter
Słowa kluczowe: data cleaning, data cleansing, data smells, data
linter
4.
Znajdowanie
największych klik w grafach
(Finding maximum cliques in graphs)
Klika
w grafie to podgraf pełny, tj. taki że w jego obrębie
istnieją krawędzie od każdego do każdego wierzchołka. Celem pracy jest
zaimplementowanie i porównanie eksperymentalne kilku algorytmów znajdowania
największych klik w grafach. Grafy wejściowe mogą pochodzić z benchmarku DIMACS:
http://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark
Przykładowa
literatura:
http://users.uj.edu.pl/~ufkapano/download/Dariusz_Zdybski_2016.pdf (praca mgr z UJ)
https://www.sciencedirect.com/science/article/abs/pii/016763779090057C
https://www.sciencedirect.com/science/article/pii/S0167637797000540
5.
Projekt i
implementacja algorytmu kompresji wykorzystującego ideę narzędzia copMEM
(Design and implementation
of a compression algorithm based on the copMEM
tool idea)
Literatura:
https://arxiv.org/abs/1805.08816
lub (prawie to samo):
Kody źródłowe:
https://github.com/wbieniec/copmem
Chodzi o projekt i implementację b. szybkiego
kompresora z rodziny LZ77, który jednak znajduje tylko długie „matche” (przykładowe zastosowanie: deduplikacja).
Uwaga: taki sam temat podałem jako pracę inż. W ramach pracy magisterskiej należałoby
zrobić więcej (różne tryby kompresji: kompromisy między szybkością a stopniem
kompresji; obszerniejszy stan wiedzy; może więcej eksperymentów, np. na różnych
maszynach).
Przetwarzanie obrazu / wideo
6.
Stratna kompresja grafik komiksowych
(Lossy compression of comic strips)
Obrazki
komiksów są typowo kompresowane algorytmem JPEG, znanym ze swych artefaktów
pierścieniowych (i zdecydowanie bardziej przydatnym do fotografii niż grafik).
Algorytm PNG (bezstratny) oferuje stosunkowo słabą kompresję. Zapewne lepszy
jest stosunkowo nowy algorytm FLIF (https://flif.info/index.html),
ale też jest bezstratny.
Celem
pracy jest zbadanie możliwości dedykowanego algorytmu kompresji stratnej dla
obrazów „komiksowych”. Etap wstępny mógłby redukować liczbę kolorów i wykrywać
jednokolorowe obszary (które na wejściu mogą być tylko w przybliżeniu
jednokolorowe). Obraz segmentujemy, wykrywając krawędzie (kontury) i zapisując
je oszczędnie za pomocą np. kodu łańcuchowego. Jednolite wypełnienie nie
sprawia problemu, ale może być też przejście tonalne. W przypadku „trudnego”
wypełnienia, np. tektury, można odwołać się do bardziej konwencjonalnej
techniki kompresji. Specyfiką komiksów są też dialogi, zwykle w dymkach (może
się przydać OCR).
Przykładowe
komiksy można obejrzeć pod:
https://swiatkomiksu.pl/katalog/wyszukiwanie/galeria,1,326.html
7.
Wykrywanie i dekodowanie kodów paskowych na obrazach
(Barcode detection and decoding in
images)
8.
Śledzenie i adnotowanie sylwetek ludzkich w sekwencjach wideo
(Tracking and annotating humans in video sequences)
Inżynieria oprogramowania
9.
Zastosowanie algorytmu sortowania pozycyjnego dla generycznego
sortowania obiektów w języku Java
(Using the radix sort algorithm for a generic
object sort in Java)
Celem
pracy jest zbadanie możliwości zastosowania sortowania pozycyjnego (ang. radix sort), zamiast bardziej tradycyjnego
sortowania opartego na porównaniach (tj. zazwyczaj: sortowania przez scalanie,
sortowania szybkiego, lub nieraz hybrydy powyższych), w generycznym
sortowaniu obiektów, czego przykładem w bibliotece standardowej Javy są Arrays.sort(Object[] a) i Collections.sort(List<T>
list).
Jeśli
np. typ elementów tablicy przekazanej do Arrays.sort
to Student, który implementuje Comparable i funkcja compareTo wygląda następująco:
int compareTo(Student other)
{
return Long.compareTo(other.id());
// lub nawet: ...(other.getId());
}
to
można wydedukować, że sortujemy Studentów po 8-bajtowym polu id (ze znakiem) i
można do tego wykorzystać alg. radix sort (przyjmijmy
dokładniej: LSD radix sort), który będzie
prawdopodobnie szybszy niż merge sort (używany do
sortowania obiektów w Arrays.sort) – zakładając, że
sortujemy przynajmniej tysiące Studentów...
Niemniej,
problem komplikuje się, jeśli kryterium sortowania jest bardziej złożone (np.:
po jednym polu, a jeśli równość, to wtedy decyduje drugie pole itd.).
Algorytm
LSD radix sort nie nadaje się, w ogólnym przypadku,
do sortowania napisów (chyba że są równej i niedużej długości), dlatego
skupiamy się na typach liczbowych (głównie int/Integer, long/Long, double/Double, float/Float). Radix sort najlepiej
nadaje się do sortowania liczb całkowitych bez
znaku, zatem trzeba zmodyfikować oryginalną procedurę pod kątem obsługi
(osobno) typów całkowitych ze znakiem oraz typów zmiennoprzecinkowych.
Jak
podejść do problemu? Konieczna analiza
kodu funkcji compareTo (jeśli dana klasa implementuje
Comparable) lub funkcji compare
(jeśli do funkcji Arrays.sort lub Collections.sort
jest przekazany komparator). Reflekcja w Javie nie
wystarczy – trzeba wygenerować drzewo składniowe (AST, abstract syntax tree).
Zalecane narzędzie: https://javaparser.org
Minimalne
rozwiązanie problemu to obsługa przypadków jak powyżej (np. Long.compareTo(...)).
Im bardziej złożony kod w compare(To) będzie
zrozumiały i obsłużony via radix sort, tym lepiej.
Ale gdy algorytm analizy sobie nie poradzi, wtedy ma wywoływać standardowy Arrays.sort/Collections.sort.
Pożądana
część pracy: eksperymenty wydajnościowe (różne typy danych, tablice/listy
różnej wielkości; przy małych kolekcjach zapewne nie opłaca się przechodzić na radix sort, stąd należy znaleźć odpowiedni próg, etc.).
Powstałym
produktem byłyby (uproszczone) klasy o nazwie np. MyArrays,
MyCollections, zawierające opisaną metodę sort (lub: rsort).
Algorytmy tekstowe i bioinformatyka:
10.
Oznaczanie typów
wypowiedzi w systemie dialogowym
(Tagging dialog acts in a dialog system)
Systemy dialogowe (=wirtualni asystenci, chatboty) działają zwykle wg pewnego schematu. Przypisują
wypowiedzi użytkownika do jednej z predefiniowanych klas (typu: powitanie,
pytanie, oświadczenie, zaprzeczenie, etc.) i również posługują się podobną
klasyfikacją/oznaczaniem przy swoich wypowiedziach (np. potwierdzenie
zrozumienia poprzedniej wypowiedzi, prośba o ujednoznacznienie).
Przykład dialogu z oznaczaniem typów wypowiedzi:
Źródło: https://web.stanford.edu/~jurafsky/slp3/ed3book.pdf
Celem pracy jest opracowanie i zaimpl.
algorytmu oznaczania typów wypowiedzi. Oczywiście problem jest trudny, dlatego
wydaje się konieczne odpowiednie zawężenie dziedziny tematycznej rozmowy. Język
rozmowy angielski lub (ambitniejsze) polski.
Lektura podstawowa: podany wyżej URL (draft
trzeciego wydania monografii „Speech and Language Processing”, 2017), rozdział 29.
11.
Implementacja
efektywnego i bezpiecznego wątkowo dynamicznego łańcucha tekstowego
(Efficient and thread-safe dynamic string implementation)
Projekt
jest rozszerzeniem podobnego tematu zaproponowanego na pracę inżynierską (http://szgrabowski.kis.p.lodz.pl/dyplomy/dyplomy2016inz.htm,
nr 1).
W
skrócie:
Celem
projektu jest zaimplementowanie struktury danych „rope”
(https://en.wikipedia.org/wiki/Rope_(data_structure)),
rozważeniu różnych jej szczegółów implementacyjnych i testy wydajnościowe przy
podstawowych scenariuszach użycia (typowych sekwencjach operacji).
Ponadto,
zaprojektowana struktura danych ma się nadawać do pracy grupowej (np.
współbieżna edycja artykułu przez kilku autorów), tj. należy zadbać o
bezpieczeństwo wątkowe (ang. thread safety) oraz efektywność przy takim reżimie pracy.
12.
Wydajne i
oszczędne pamięciowo struktury listowe w Javie
(Effective and compact list data structures
in Java)
13.
Budowa otagowanego korpusu języka angielskiego
(Construction of a tagged
corpus for the English language)
14.
System
zarządzania streszczeniami publikacji naukowych
(A management system for scientific abstracts)
15.
Kompresja danych bioinformatycznych w języku Julia
(Bioinformatics data compression in Julia programming language)
Julia
(http://julialang.org) jest względnie nowym
interesującym językiem programowania do obliczeń naukowych i inżynierskich.
Siłą tego języka jest połączenie prostej składni (przypominającej trochę Pythona) z wydajnością bliską językom C i C++. Celem pracy
jest zaimplementowanie i przetestowanie przynajmniej dwóch algorytmów kompresji
danych bioinformatycznych (kolekcji genomów w
formacie FASTA i/lub kolekcji odczytów w formacie FASTQ i/lub kolekcji genomów
w uproszczonym formacie VCF z szybkim dostępem i/lub wyników mapowania odczytów
na genom referencyjny w formacie SAM).
16.
Zastosowanie
paradygmatu obliczeniowego MapReduce dla wybranych
problemów bioinformatycznych
(Application of the MapReduce computing paradigm for selected bioinformatics problems)
– opiekun pomocniczy: dr inż. T. Kowalski
17. Aplikacja pomocna w korekcie
dokumentów tekstowych
(A textual document correction
assisting application)
Moduł
kontroli pisowni (spellchecker)
we współczesnych edytorach tekstu jest wprawdzie przydatnym, ale często
niedoskonałym narzędziem: korekta błędów jest dość powolna (z uwagi na ich
przeglądanie sekwencyjne); brak wygodnych mechanizmów do pomijania niektórych
słów (np. pisanych wielką literą w środku zdania – nazwy własne); brak
wykorzystania np. Google API do sprawdzenia poprawności słów.
18. Kompresja wyników uliniawiania sekwencji DNA zapisanych w formacie SAM
(Compression
of DNA sequence alignment data in SAM format)
TEMAT ZAREZERWOWANY
19. Oszczędne struktury
słownikowe dla napisów
(Succinct string dictionaries)
Literatura:
http://www.dcc.uchile.cl/~gnavarro/ps/sea11.1.pdf
http://journals.bg.agh.edu.pl/AUTOMATYKA/2011-03/Auto_2011_3_23.pdf
http://arxiv.org/abs/1305.0674
20. Biblioteka kolekcji
słownikowych z wyszukiwaniem probabilistycznym i przybliżonym
(Dictionary structures library with probabilistic
and approximate search)
– opiekun pomocniczy: dr inż. T.
Kowalski
21. Rozmyte wyrażenia regularne
(Fuzzy regular expressions)
TEMAT
ZAREZERWOWANY
Literatura:
http://en.wikipedia.org/wiki/TRE_%28computing%29
http://frej.sourceforge.net/rules.html
http://frej.sourceforge.net/javadocs/overview-summary.html
ewent.:
http://www.dcc.uchile.cl/~gnavarro/ps/spe01.pdf
(NR-grep)
Temat
obejmuje opracowanie składni, implementacji i przeprowadzenie testów rozmytych
wyrażeń regularnych, będących rozszerzeniem konwencjonalnych wyrażeń
regularnych. Nowość polega na dodaniu
pasowania przybliżonego (np. w sensie Levenshteina)
na poziomie całego wzorca lub jego części (grup), dodanie wag związanych z
pozycją (np. prefiks wzorca jest „ważniejszy” niż jego sufiks) oraz
(alternatywnie) dopuszczenie innej kolejności elementów (grup) wyrażenia w
pasowanym tekście. Każde pasowanie
zwraca stopień podobieństwa (od 0 do 1), użytkownik wywołuje narzędzie z
odpowiednim progiem, np. „zwróć trafienia z podobieństwem >=
22. Kompresja tekstowego XML z
możliwością obsługi zapytań
23. Usuwanie redundancji z
dużych kolekcji plików
24. Szukanie wzorców w tekście
skompresowanym
25. Rozszerzanie funkcjonalności
tablicy sufiksowej
26. Dynamiczne indeksowanie
tekstu przy użyciu odmian tablicy sufiksowej
27. Efektywność słownikowych
struktur danych w przetwarzaniu tekstu
Information
retrieval i data mining:
28. Tworzenie materiałów
wspomagających naukę języka obcego z wykorzystaniem dwóch wersji językowych Wikipedii
(Preparing language learning materials from
bilingual Wikipedia articles)
29. Efektywna kompresja dużych
grafów z użyciem drzew k2
(Efficient compression of large graphs with
k2-trees)
Literatura:
http://www.dcc.uchile.cl/~gnavarro/ps/spire09.1.pdf
30.
Implementacja i zastosowania R-drzewa
(Implementation and applications of the
R-tree)
– opiekun pomocniczy: dr inż. T.
Kowalski
Literatura (na początek):
http://www.cse.cuhk.edu.hk/~taoyf/course/wst501/notes/lec13.pdf
Rozpoznawanie
obrazów:
30. Klasyfikacja minimalnoodległościowa w
zadaniach opisanych cechami symbolicznymi
31. Klasyfikacja minimalnoodległościowa przy
niekompletnych danych uczących (missing data)
Gry
logiczne:
32. Wykorzystanie programowania z ograniczeniami do realizacji platformy
planszowych gier logicznych
(Using constraint programming for developing a logic
board games platform)
33. Generacja bazy końcówek dla wybranych gier logicznych
(Endgame tablebase generation for selected logic games)
(Chodzi o np. szachy, warcaby, go-moku na zmniejszonej planszy, reversi?
Idea generacji takiej bazy jest opisana np. w http://www.mimuw.edu.pl/~pan/gry.pdf
, sekcja 2.)
Kryptografia i okolice
34. Steganografia w algorytmach kompresji
danych
(Steganography exploiting properties of data compression
algorithms)
Inne
35. Porównanie wydajności równoległych algorytmów sortowania
(Performance comparison
of parallel sorting algorithms)
TEMAT ZAREZERWOWANY
36. Zależności pamięciowo-czasowe w skompresowanych filtrach Blooma
(Space-time tradeoffs in compressed Bloom
filters)
Literatura:
http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/cbf2.pdf
(Mitzenmacher, 2002)
http://www.cs.amherst.edu/~ccm/cs34/papers/cacheefficientbloomfilters-jea.pdf
(Putze et al., 2009)
http://szgrabowski.kis.p.lodz.pl/Gliwice/Bloom%20Filters%20-%20SzGrabowski.ppt
Filtr Blooma
(BF) to oszczędna probabilistyczna struktura słownikowa – pozwala na sprawdzenie,
czy dany element został wstawiony do słownika, ale możliwe są „fałszywe
pozytywy” (odpowiedź twierdząca, podczas gdy element nie został wstawiony).
Idea BF znana jest od roku 1970, ale dopiero w ostatnich
latach stają się one popularne na szerszą skalę, z zastosowaniami m.in. w
sieciach komputerowych i bazach danych. Przykładem popularności jest też
implementacja BF w bibliotece javowej Google Guava.
Mitzenmacher (2002) zaproponował
skompresowany filtr Blooma (do transmisji przez
sieć), a wersja obsługująca także zapytania bezpośrednio w postaci
skompresowanej została przedstawiona w (Putze et al.,
2009).
Celem pracy jest zbadanie innych rozwiązań kompresji i
otrzymania pewnych zależności między zużyciem pamięci a czasem dostępu.
37. Indeksowanie audiobooków na podstawie
sygnału mowy
(Speech indexing for audiobook data)
– opiekun pomocniczy: prof. dr hab. inż.
K. Ślot
W audiobookach
przydałaby się inteligentna nawigacja: cofnięcie się do początku poprzedniego
zdania (akapitu?), analogicznie do przodu. Zastosowanie takie, że gdy słuchacz
się zdekoncentruje, to chciałby sobie cofnąć, ale nie naiwnie np. o 10s, tylko
do początku jakiejś jednostki tekstu. (Również manipulacje suwakiem nie są
wygodne, a całkiem odpadają, jeśli książki słucha kierowca.) Nasuwa się idea
segmentacji z wykorzystaniem długości pauzy.
Druga możliwość nawigacji: do
początku np. poprzedniego rozdziału. Czyli: dłuższa pauza przed + coś
brzmiącego podobnie jak słowo „rozdział”. Oczywiście do początków rozdziałów
powinny być zakładki, ale audiobooki mogą być też
dostarczane jako zwykły mp3 (ewent. kilka takich plików, ale i tak granulacja
większa niż 1 rozdział).
Drugi pokrewny pomysł, który
mogłaby obejmować praca magisterska, to znajdowanie korespondencji między
odtwarzanym audiobookiem a tekstem tej samej książki
(szczegóły dla zainteresowanych...).
38. Moduł
deklaratywnej grafiki wektorowej dla Pythona
(A declarative vector graphics
Python module)
– opiekun pomocniczy: dr inż. W.
Bieniecki
Proszę zapoznać się z bibliotekami
(dla innych języków):
Diagrams (Haskell):
http://projects.haskell.org/diagrams/doc/quickstart.html#getting-started
Compose (Julia):
https://github.com/dcjones/Compose.jl
http://giovineitalia.github.io/Compose.jl/latest/