Obliczanie wartości Shapleya faktów w odpowiadaniu na zapytania

Speaker(s)

Agata Bielenica

Affiliation

MIMUW

Language of the talk

Polish

Date

Dec. 10, 2024, 10:15 a.m.

Room

room 4060

Title in English

Computing the Shapley Value of Facts in Query Answering

Seminar

Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

---

W referacie podejmę problem wyjaśniania, dlaczego dane zapytanie bazy danych daje określony wynik. Posłuży do tego teorio-growe pojęcie wartości Shapleya. Intuicyjnie, wartość Shapleya dla pewnego faktu z bazy danych, zapytania i krotki reprezentuje, jak bardzo dany fakt przyczynił się do obecności danej krotki w wyniku zapytania. Najpierw określę precyzyjnie, czym jest wartość Shapleya dla faktów w bazach danych, a następnie zaprezentuję wyniki pracy: https://arxiv.org/abs/2112.08874. Przedstawię wynik teoretyczny na temat złożoności obliczeniowej wyliczania wartości Shapleya dla zapytań klasy UCQ. Omówię również algorytm wyliczania wartości Shapleya dla zapytań tej klasy oraz szybką heurystykę służącą do przybliżania tej wartości. Na zakończenie zaprezentuję wyniki eksperymentów wykonanych przez autorów pracy.

---