WebPIE: rozproszone wnioskowanie w oparciu o MapReduce

- autor: tsissput

W przeciągu ostatnich lat powstały ogromne wolumeny danych semantycznych. Stanowią one wartościowe źródło dla naukowców i badaczy wielu dziedzin, np. medycyny. Rządy Wielkiej Brytanii oraz Stanów Zjednoczonych dokładają wszelkich starań, aby publikowane dane miały odpowiedni format sieci semantycznych. Również widza ogólna uzyskana z Wikipedii a także wiedza geograficzna dostępne są w postaci danych semantycznych.
Liczba trójek (podmiot, predykat, przedmiot) składowanych w ramach danych semantycznych bardzo szybko przekroczyła wartość, którą można bezproblemowo analizować za pomocą dostępnych obecnie maszyn (używając ich pojedynczo). W marcu 2009 ok. 4 miliardy trójek było dostępne w sieci. W przeciągu 9 miesięcy liczba ta została potrojona.

Czym jest wnioskowanie?

Wnioskowanie (w przód) w maszynach polega na zaaplikowaniu pewnych reguł na dostępnym zbiorze trójek, aby uzyskać nową wiedzę, nie zawartą bezpośrednio w początkowym zbiorze. Najczęściej używane zbiory reguł to te występujące w RDFS oraz OWL-horst (podzbiór OWL). Reguły są zazwyczaj aplikowane rekurencyjnie, dopóki z reguł na wejściu możliwe jest wywnioskowanie nowej wiedzy. Stan w którym nie jest możliwe uzyskanie żadnych nowych trójek aplikując konkretny zestaw reguł nazywany jest inferred closure.

Zrównoleglenie wnioskowania

Przyjrzyjmy się przykładowej regule przechodniości predykatu:

if (<?p isA transitiveProperty>, <?a ?p ?b>, <?b ?p ?c>) then <?a ?p ?c>

Aby zaaplikować powyższą regułę musimy wykonać operację połączenia trójek, które zawierają predykat p oraz mają wspólną parę przedmiot-podmiot. Zarówno RDFS jak i OWL-horst posiadają wiele tego typu reguł. W pesymistycznym przypadku złożoność wnioskowania na danych semantycznych jest wykładnicza.
Dotychczasowo wnioskowania takiego dokonywano zazwyczaj wykorzystując pojedynczą maszynę. Wraz z dramatycznym wzrostem liczby danych semantycznych pojawiła się konieczność zrównoleglenia procesu wnioskowania. Nie jest on jednak trywialny, ponieważ:

  • dokonywanie połączeń pomiędzy trójkami w sposób równoległy stanowi problem
  • ciężko jest podzielić dane na niezależne od siebie partycje
  • popularność poszczególnych termów występujących w trójkach zazwyczaj nie ma rozkładu jednostajnego, przez co ciężko zapewnić load balancing
  • zbiór reguł musi być aplikowany rekurencyjnie

Pomimo trudności związanych ze zrównolegleniem wnioskowania twórcom WebPIE udało się tego dokonać. Wykorzystali w swojej pracy framework MapReduce

Czym jest MapReduce?

MapReduce to model programowania rozproszonego zaprojektowany i zaimplementowany przez Google. Umożliwia on proste przetwarzanie i generowanie ogromnych zbiorów danych.  W modelu tym możemy wyróżnić dwie fazy: “map” oraz “reduce”. Wszelkie informacje kodowane są w postaci krotek <klucz, wartość>. W fazie map dla każdej pary <klucz1, wartość1>, emitowana jest para <klucz2, wartość2> (może być emitowana więcej niż jedna para wyjściowa). Dane przetwarzane są niezależnie od siebie, bardzo łatwo zadbać o to, aby były rozłożone pomiędzy poszczególnymi węzłami w sposób równomierny. Pomiędzy fazami map i reduce otrzymane krotki <klucz2, wartość2> są sortowane i grupowane według klucza. W fazie reduce generowany jest wynik. Podczas jego generacji zapewniony zostaje fakt, że krotki posiadające ten sam klucz trafią do tych samych węzłów (powoduje to pewien problem związany z load balancingiem dla fazy reduce). Jako wynik otrzymujemy krotki <klucz3, wartość3>. Ich liczba może się diametralnie różnić w zależności od tego jaki algorytm zaimplementowano.

W jaki sposób wykorzystano MapReduce do rozproszenia wnioskowania?

Na początku dane wejściowe zostają poddane procesowi wstępnego przetwarzania. Aby zminimalizować wymagania pamięciowe algorytmu zasoby występujące w trójkach (które często występują w postaci długich, w tym wypadku niepotrzebnie „pamięciożernych” URI) są zamieniane na unikalne id. Przetwarzanie wstępne jest wykonywane, podobnie jak główny algorytm, z wykorzystaniem MapReduce. Każdej trójce w fazie map przypisywane jest unikalny numer identyfikacyjny (zakresy przydzielanych id są zależne od węzła, zapewnia to unikalność bez potrzeby komunikacji pomiędzy węzłami). Emitowane są pary <K1, V1>, gdzie K1 oznacza identyfikator zasobu, a V1 jest parą (unikalny identyfikator trójki, pozycja zasobu w trójce). Zgodnie z podejściem MapReduce następuje grupowanie po kluczu, co pozwala nadać w fazie reduce unikalne id dla zasobów. Emitowane trójki w stosunku do pochodzących z fazy map różnią się tym, że w kluczu występuje id zasobu zamiast jego nazwy. Tak otrzymane dane stanowią wejście do kolejnego przebiegu MapReduce. W fazie map zadanie jest dość prozaiczne – zamieniane są miejscami id trójki oraz zasobu (id trójki staje się kluczem). Następnie w fazie reduce trójki są agregowane i emitowane w postaci unikalnych identyfikatorów, które zastąpiły URI. Podczas działania algorytmu możliwe jest oczywiście zapisanie mapowania odpowiednich URI na identyfikatory. W dalszej części algorytm działa na identyfikatorach, aby wszelkie operacje wykonywały się szybciej dzięki mniejszej zajętości pamięciowej.

Dla odpowiednio przygotowanych danych następuje wnioskowanie w przód. Pozwolę sobie omówić sposób działania jedynie algorytmu dla reguł RDFS, zainteresowanych realizacją wnioskowania dla reguł OWL-Horst odsyłam do źródeł.

Każda reguła wnioskująca odpowiada jednemu z zadań. Zadania są wykonywane tak długo, dopóki nie zostanie osiągnięte inferred closure. W celu optymalizacji zadania dotyczące każdej z reguł wykonywane są w odpowiedniej kolejności (reguły wnioskowania w RDF cechują się pewnymi zależnościami). Aby zmniejszyć rozmiar danych pomiędzy poszczególnymi przebiegami stosuje się usuwanie duplikatów w powstałych danych.

Jak wygląda wnioskowanie dla jednej reguły?

Dla każdej reguły wnioskowanie wygląda podobnie. Jako przykład przeanalizujmy regułę:

if a rdf:type B and B rfds:subClassOf C then a rdf:type C

Jest to prosta reguła mówiąca o tym, że jeżeli zasób a jest typu B, a typ B jest podtypem typu C, to zasób a jest także typu C. Chcąc zaaplikować powyższą regułę do danych musimy poszukać trójek typu x rdf:type X oraz X rfds:subClassOf Y (X będący obiektem jednej trójki oraz podmiotem drugiej jest w tym wypadku elementem, na podstawie którego dokonujemy łączenia trójek). Czy już domyślacie się w jaki sposób wykorzystane zostanie MapReduce do wnioskowania? Dokładnie tak – dla każdej trójki, która ma predykat rdf:type lub rdf:subClassOf zostanie w fazie map wyemitowana para, której kluczem będzie X, a wartością trójka. Dzięki temu w fazie reduce wnioskowanie jest już trywialne i polega na wyemitowaniu trójek postaci x rdf:type Y dla wszystkich możliwych połączeń x i Y (wiemy, że mają one wspólny przedmiot / podmiot, ponieważ jest on kluczem).

Jak wydajne jest użycie MapReduce do wnioskowania?

Eksperyment przeprowadzone na klastrze DAS3 złożonym z 64 stacji roboczych wyposażonych w dwurdzeniowe procesory Opteron, 4 GB pamięci RAM oraz dyski twarde o pojemności 250 GB. Eksperymenty zostały przeprowadzone m.in. na podstawie ontologii Lehigh University Benchmark (LUBM) oraz Universal Protein Resource (UniProt). Dla ontologii LUBM w czasie wnioskowania przetworzono 10 miliardów trójek w 4 godziny (wynik BigOWLIM, który jest najwydajniejszym obecnie narzędzie do wnioskowania na pojedynczych maszynach, dla 12 miliardów trójek to 290 godzin). W przypadku UniProt przetworzono 1,5 miliarda trójek w czasie 6. godzin, BigOwlim potrzebował 21 godzin aby dokonać wnioskowania na 1,15 miliarda trójek. Rezultaty jak widać różnią się w zależności od ontologii. Dla LUBM zysk jest bardzo satysfakcjonujący. W przypadku UniProt, zważywszy na to, że użyto 64 komputerów dla WebPIE, kontra 1 dla BigOwlim, już nie jest to rewelacyjny wynik. Warto jednak zauważyć, żę wykorzystując WebPIE przeprowadzono wnioskowanie dla 100 miliardów trójek (dla ontologii LUBM), jest to o rząd wielkości więcej niż w jakiejkolwiek publikacji naukowej dotyczącej wnioskowania na pojedynczych maszynach. Wyniki są więc naprawdę obiecujące, a prototyp systemu powstał zaledwie 3 lata temu, jako praca magisterska Jacopo Urbani, studenta Vrije Universiteit Amsterdam.

Żródła: http://www.few.vu.nl/~jui200/webpie.html

Autor: 84889

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: