Krystalizacja problemu do rozwiązania w pracy doktorskiej

1.    Wstęp

Przewód doktorski p.t. „Metody analizy spójności i zgodności kolekcji dokumentów WWW” został otwarty 2003.06.03 na Wydziale Informatyki i Zarządzania Politechniki Wrocławskiej przez mgr inż. Marka Kopla. Jego promotorem był dr hab. inż. Czesław Daniłowicz, prof. PWr. Od kwietnia 2007 promotorem jest dr hab. inż. Aleksander Zgrzywa, prof. PWr.

W ramach pracy powstało 5 publikacji. Trzy z nich to referaty na konferencjach międzynarodowych, a jeden na  konferencji krajowej.  Opracowano również rozdział do książki „Intelligent technologies for inconsistent knowledge processing (International Series on Advanced Intelligence; vol. 10)”.

2.    Kontekst pracy

 

Tematyka pracy oscyluje wokół generalnych zagadnień wyszukiwania informacji i data mining. Dzięki m metodom analizy spójności i zgodności można do zbioru wyszukanych dokumentów wprowadzić ranking. Natomiast metody pochodne data mining mogą być wykorzystane we wstępnej fazie analizy do wydobycia informacji semantycznych z dokumentów.

Badanie spójności i zgodności można używać do wyznaczania bardziej spójnych i zgodnych podzbiorów dokumentów w kolekcji. Progowa wartość spójności podzbioru kolekcji pozwala nam kontrolować liczbę grup, klastrów dokumentów w kolekcji. Patrząc na to z tej strony metody analizy spójności i zgodności można traktować jako alternatywne podejście do problematyki klasyfikacji i klasteringu.

Z drugiej strony dzięki informacji semantycznej o relacji między autorami dokumentów oraz ich ocenie możemy badać kolekcje spójne ze względu na wysoki rating dokumentów i ich autorów. W tym kontekście zastosowanie miar spójności i zgodności odpowiada na problemy związane z filtrowanie kolaboratywnym i personalizacją. Dodatkowo budując graf autorów dokumentów wkraczamy na teren problematyki analizy sieci społecznych, który nie jest jedynie problemem z dziedziny informatyki.

 

Spójność i zgodność to w literaturze naukowej pojęcia odnoszące się do bardzo różnych problemów. Spójność jako cosistency, cohesion lub coherence (czy coherency)  oraz zgodność (również często tłumaczona jako cosistency) występują w różnych  dziedzinach nauki takich jak chemia, fizyka w problemach zupełnie niezwiązanych z informatyką. W samej informatyce pojęcie spójność stosowane jest w odniesieniu do różnych problemów.

W technologiach informatycznych spójność najczęściej kojarzy się jako jedna z czterech integralnych własności reguły ACID (Atomicity, Consistency, Isolation and Durability). Reguła ta stanowi filar transakcyjnych baz danych. Drugim równie trafnym skojarzeniem jest spójność pamięci podręcznej cache w systemach buforujących WWW (proxy). Tu problem utrzymania spójności jest analogiczny do problemu, który występuje podczas replikacji baz danych. Oba te problemy wywodzą się z teorii dostępu do pamięci dzielonej DSM (Distributed Shared Memories).

W pracy doktorskiej spójność i zgodność rozumiane są jako pewnego rodzaju podobieństwo czy jednakowość dokumentów w kolekcji, na pewnym poziomie abstrakcji. Ponieważ tak rozumiana spójność nie jest funkcją binarną, a jej wartość nie jest może być powodem modyfikacji dokumentów, więc problem utrzymania spójności w ogóle tu nie istnieje. Podobna niejednoznaczność interpretacji może dotyczyć pojęcia dokument WWW, dlatego przeprowadzona została dekompozycja tematu pracy uściślająca jego interpretację.

2.1.                   Dekompozycja tematu pracy

Temat otwartego przewodu doktorskiego brzmi: „Metody analizy spójności i zgodności kolekcji dokumentów WWW”. Analizując semantykę tematu zaczynamy od końca.

WWW to globalna sieć dokumentów dostępnych w Internecie poprzez protokół HTTP(S) za pomocą odpowiedniego oprogramowania klienckiego – najczęściej przeglądarki internetowej. Ponieważ obecna WWW jest na coraz dalszym etapie przekształcania się w Semantic Web, bazę opracowywanej metody stanowi taka właśnie współczesna sieć dokumentów często wzbogaconych o informacje semantyczne.

Dokumenty WWW to hipertekstowe i multimedialne zbiory danych jak np.: dokumenty HTML, zdjęcia, dźwięki, filmy czy animacje. Najpopularniejsze (w przeważającej liczbie) to dokumenty tekstowe[1] sformatowane językiem znaczników.

W pracy mówiąc o dokumentach WWW mamy na myśli dokumenty języka znaczników. Mogą to być zarówno dokumenty zawierające:

·         wyłącznie dane, np. dokumenty HTML tylko ze znacznikami formatującymi wygląd

·         wyłącznie metadane, np. dokumenty RDF opisujące inne dokumenty

·         dane wzbogacone o metadane, np. dokumenty XHTML zawierające dodatkowo informację semantyczną.

Co ciekawe rozpatrując publikację jako dokument na poziomie semantycznym możemy w ogóle nie sięgać do jego źródła (które może być w dowolnej postaci, np.: PDF, JPG, AVI). Jeśli mamy do dyspozycji dokument opisujący tą publikację (plik RDF z metadanymi – jak ma to miejsce np. w bibliotekach cyfrowych), to możemy przyjąć, że ten dokument jest używany w metodzie i w ten sposób metoda analizy spójności działająca na dokumentach XML’owych pozwala analizować dowolne multimedialne dokumenty.

Bardzo często dokument WWW rozumiany jest jako strona WWW. W niedalekiej przeszłości było to, w większości przypadków, prawdą. Jednak obecnie, w kontekście dynamicznie rozwijającej się blogosfery, poprzez dokument WWW możemy rozumieć pojedynczy wpis (post) lub komentarz do tego wpisu w blogu. Z kolei cały blog, bądź jeden z jego widoków jest stroną WWW. To, coraz bardziej oczywiste, rozróżnienie spowodowane jest coraz powszechniejszym zastosowaniem w budowie systemów Web’owych architektury trójwarstwowej oraz dynamicznie generowanych stron za pomocą języków skryptowych jak np. PHP i ASP. Implikacją takiego podejścia jest fakt, że strony HTML przestają być nośnikiem treści, a stają się jedynie jedną z możliwych wersji prezentacji tych treści.

Kolekcja to zbiór dokumentów o podobnym charakterze wynikającym ze zgodności pewnego podzbioru atrybutów opisujących te dokumenty. Atrybutami są konkretne rodzaje danych i metadanych, np.:

·         data opublikowania dokumentu,

·         abstrakt dokumentu,

·         wielkość (długość) dokumentu,

·         pozycja bibliograficzna,

·         format dokumentu,

·         hiperłącze odsyłające z treści dokumentu do innego zasobu,

·         słowo kluczowe (podane jawnie),

·         waga terminu w treści (wyznaczona metodami statystycznymi, np. tf-idf),

·         dziedzina nauki, której dotyczy dokument.

Wobec powyższego kolekcjami mogą być np.:

·         posty z jednego bloga (wspólni autorzy),

·         dokumenty opublikowane w bibliotece cyfrowej w jednym tygodniu (zgodność co do tygodnia daty publikacji),

·         wiadomości syndykowane z różnych źródeł RSS, ale z identycznymi tag’ami (jednakowe przyporządkowanie słów kluczowych przez autorów),

·         posty z blogów autorów, do których mamy najwyższe zaufanie (wyznaczone metodami Social Network Analysis).

Kolekcją dokumentów będziemy również nazywać zbiór dokumentów, otrzymanych z pewnego źródła, gdy nie konieczne znany jest zbiór ich wspólnych atrybutów, np. pierwsze 100 dokumentów z odpowiedzi wyszukiwarki Google. Wyrażenia, z zadanego do wyszukiwarki, pytania nie muszą być słowami kluczowymi tych dokumentów (nawet nie muszą w nich występować), a algorytm sortowania (PageRank), który wpłynął na to, które 100 dokumentów z odpowiedzi znalazło się w kolekcji, cały czas jest modyfikowaną i strzeżoną tajemnicą firmy Google.

Zgodność kolekcji wiąże się z analizą treści dokumentów, tzn. na zgodność mają wpływ atrybuty dotyczące danych, czyli treści i faktów podanych wprost. Z kolei spójność wiąże się z metadanymi dotyczącymi dokumentów opisującymi pewną semantykę, dzięki której można przeprowadzać automatyczne (maszynowe) wnioskowanie. Zgodność i spójność są miarami podobieństwa dokumentów wewnątrz kolekcji, jednak operują na różnych poziomach analizy tych kolekcji.

Żeby lepiej zobrazować różnicę między zgodnością i spójnością można powiedzieć, że zgodność jest miarą bardziej bezwzględną, ponieważ opiera się tylko na jawnych danych. Natomiast spójność zależy od interpretacji semantyki metadanych w dokumentach i sposobów wnioskowania na ich podstawie. Co za tym idzie: miarę zgodności można wyznaczyć operując na kolekcji dokumentów tradycyjnej WWW, a miara spójności wymaga metadanych, które zawierają dokumenty z Semantic Web.

Przykład. 1. Rozpatrzmy kolekcję 2 dokumentów oraz zgodność i spójność tej kolekcji na poziomie autorstwa dokumentów. Zakładając, że dokumenty mają różnych autorów, ich miara zgodności zawsze będzie minimalna, natomiast spójność może zależeć od relacji między tymi autorami. Jeżeli w kolekcji istnieje informacja semantyczna, według której możemy stwierdzić np. pokrewieństwo, znajomość czy współpracę tych autorów, to miara spójności tej kolekcji na poziomie autorów będzie większa od minimalnej, czyli takiej, w której brak relacji między autorami lub relacja ta wskazuje na antagonizm[2]. Należy również zwrócić uwagę, że miara zgodności nie musi być w tym przypadku binarna, ponieważ dokumenty mogą mieć kilku autorów. Jeżeli choćby jeden z kilku autorów byłby wspólny dla obu dokumentów, to zgodność byłaby większa od minimalnej.

W dużym uproszczeniu można powiedzieć, że zgodność dotyczy danych w dokumentach, a spójność – metadanych. W rzeczywistości prawdziwość tego twierdzenia zależy do sposobu klasyfikacji atrybutów dokumentów względem bycia daną czy metadaną. Przykładowo HTML’owe metatagi można traktować jako metadane dla dokumentu, ale też jako dane w kontekście całej kolekcji. Należy również zaznaczyć, że nie wszystkie metadane niosą informację semantyczną, na postawie której można przeprowadzać maszynowe  wnioskowanie. Często metadane są opcjonalnym uzupełnieniem danych, np. jeżeli hiperlink  w treści dokumentu potraktujemy jako daną, to metadaną jest np. atrybut REL, mówiący o relacji między dokumentem odsyłającym i docelowym. Ta metadana niesie jednocześnie informację semantyczną. Z drugiej strony metadane semantyczne często charakteryzuje redundancja, ponieważ jest to powielenie informacji nieczytelnej dla maszyn tak, aby była dla nich przyswajalna. Jednak bez względu na sposób podziału informacji w dokumentach na dane i metadane zawsze prawdziwym będzie stwierdzenie, że zgodność dotyczy atrybutów dokumentów jako informacji wprost, a spójność wymaga informacji semantycznej wynikającej (również przez wnioskowanie) z tych atrybutów.

Tytułowe metody analizy wiążą się ze zdefiniowaniem własności miar zgodności i spójności oraz z opracowaniem algorytmu ich wyznaczania. Metody te mają na celu znalezienie w kolekcji dokumentów podzbiorów o większej zgodności i spójności, które można następnie wykorzystać do np. poprawiania wyników wyszukiwania czy badania dynamiki popularności tematyki w czasie. Analiza dotyczyć będzie grafów i podgrafów odpowiadających kolekcji dokumentów na pewnym poziomie abstrakcji. Zakłada się adaptację znanych metod analizy grafów dla potrzeb badania zgodności i spójności kolekcji.

2.2.                   Semantic Web w praktyce

Współczesna WWW nie jest jeszcze Semantic Web, ale część serwisów udostępnia metadane niosące informacje semantyczne. Są one najczęściej udostępniane w postaci pliku RDF. Przykładem takiego serwisu może być biblioteka cyfrowa oparta na platformie dLibra. W takiej bibliotece każda publikacja opisana jest atrybutami, które można pobrać w formie RDF. Innym przykładem opisywania metadanymi dokumentów WWW jest serwis CMSReview, w którym każdy recenzowany system ma odpowiadający mu plik RDF zawierający atrybuty charakteryzujące danego CMS’a.

Na podobnej zasadzie działa technologia FOAF (Friend Of A Friend). Tutaj podobnie mamy do czynienia z plikiem RDF zawierającym atrybuty, z tą różnicą, że atrybuty te opisują nie dokument, a jego autora. Najważniejszym jednak elementem tego pliku RDF jest informacja o innych osobach, z którymi deklaruje autor znajomość. Dzięki takim plikom foaf możemy zbudować graf, którego węzłami będą autorzy dokumentów WWW. Aby nadać wagi krawędziom grafu można skorzystać z technologii XFN (XHTML Friends Network), która działa podobnie do FOAF, z tym, że poza deklaracją samego faktu znajomości możemy określić rodzaj relacji, np.: krewny, przyjaciel, współpracownik, itd. Mając taki graf możemy potraktować go jako reprezentację sieć społecznej i do jego analizy użyć metod znanych z analiz sieci społecznych (SNA). Dodatkowo, jak przy wszystkich rozproszonych źródłach informacji, dochodzi tutaj problem zaufania do autora i pośrednio od informacji, którą tworzy. Rozwiązaniem tego problemu jest budowa sieci zaufania (Web of Trust).

Dzięki udostępnieniu metadanych dla dokumentów WWW w metodach analizy semantyki znika problem ekstrakcji informacji semantycznej, gdy nie jest ona podana wprost. Czyli mogąc operować na Semantic Web, zamiast na tradycyjnej WWW, odpada problem często najtrudniejszy i najbardziej niedeterministyczny procesu wstępnego wybywania semantyki z dokumentów metodami Text Mining.

3.    Problem

Głównym problemem, który ma rozwiązać praca doktorska jest dostarczenie algorytmu wyznaczania miar spójności i zgodności dla kolekcji dokumentów. Złożoność tego problemu wynika głównie z faktu, że spójność może być mierzona na różnych poziomach, np. tematyka dokumentów, zaufanie do autorów dokumentów, czas publikacji dokumentów. Dodatkowo spójność może dotyczyć dowolnego podzbioru tych poziomów. To sprawia, że rozwiązaniem problemu nie może być jeden wzór czy algorytm.

3.1.                   Opis problemu

Załóżmy, że mamy kolekcję dokumentów, otrzymaną jako wynik z wyszukiwarki czy z feedów RSS. Problemem jest zbyt ogólny ranking i słaba skalowalność liczności wyniku. Zastosowanie analizy zgodności  i spójność pozwoli poprawić ranking biorąc pod uwagę konkretne aspekty wpływające na spójność kolekcji wejściowej i przesuwając dokumenty wzajemnie bardziej spójne w górę rankingu.

Możemy też wyznaczyć bardziej zgodne/spójne podzbiory dokumentów, co wpłynie  na bardziej płynną skalowalność (przesuwając próg spójności) oraz na możliwość clasteringu wyników ze względy na podane kryteria.

3.2.                   Metody rozwiązania

Kolekcję dokumentów można przedstawić w postaci grafu, którego węzłami są dokumenty, a krawędziami – związki między nimi. Podobnie można skonstruować graf, którym węzłami będą autorzy dokumentów, a krawędziami relacje między nimi, które również świadczą o jakiś związkach między dokumentami. Dlatego do rozwiązania problemu zastosowane zostaną metody grafowe. Przewiduje się adaptację znanych algorytmów grafowych dla stworzonych w pracy grafów.

 

4.    Spodziewane wyniki i zastosowania

 

Wynikiem pracy będzie metoda wyznaczania miary spójności i zgodności konkretnej kolekcji. Dodatkowo rozwiązane zostaną pośrednie problemy takie jak: sposób definiowania grafów w celu zbadania spójności w zadanym aspekcie czy algorytm wyznaczania bardziej spójnych podzbiorów w zadanej kolekcji dokumentów.

Konkretne zastosowania przewiduje się dla systemów oferujących dokumentny wraz z informacją semantyczną. Przykładem takich systemów są blogi czy biblioteki cyfrowe. Te drugie wydają się nawet bardziej podatne na możliwości analizy zgodności/spójności ze względu na homogeniczne źródło informacji semantycznych (opisy bibliograficzne tworzone w jednakowy sposób). Należy jednak zauważyć, że biblioteki cyfrowe mają poważne ograniczenia związane z rosnącą dynamiką zawartości WWW. Można przez analogię uznać je za odpowiedniki katalogów WWW w Semantic Web, tzn. mają już dane semantyczne, ale ponieważ są tworzone ręcznie przez użytkowników – mogą być niepełnie i nieaktualne.

Innym aspektem funkcjonalność możliwym do poprawienia dzięki badaniu spójności jest ranking wyszukiwania, gdy wszystkie dokumenty odpowiedzi pasują do pytania w 100%.  Na przykład pytamy o dokumenty wskazanego autora i z określonym słowem kluczowym w tytule. Wszystkie dokumentu w odpowiedzi spełniają to kryterium, ale jest ich za dużo, aby użytkownik mógł je przejrzeć. Nie możemy ich posortować ze względu na relewancję, ponieważ jest to zbiór (wszystkie spełniają kryterium jednakowo). Można wtedy miarami spójności wyznaczyć np. pozbiory dokumentów, które powstawały w jednym czasie i przy współpracy z tymi samymi współautorami. Następnie posortować podzbiory wg wielkości i z takim rankingiem (lub po odfiltrowaniu najmniejszych zbiorów) podać użytkownikowi. Można powiedzieć, że w tym rozumieniu zastosowanie miar spójności pozwoli na otrzymanie funkcjonalności, jaką dał model wektorowy modelowi Boolowskiemu.

Kolejnym  zastosowaniem dla opracowywanych metod może być dynamiczne katalogowanie, czyli rozwiązanie problemu z nieaktualnym ręcznym katalogowaniem. Może to być pół- lub całkowicie automatyczne przypisywanie atrybutów dokumentom na podstawie analizy spójności tych dokumentów z wzorcowymi z tej kolekcji, podobnie jak ma to miejsce w klasyfikatorach.

Jeszcze innym polem zastosowań miar spójności/zgodności może być analiza dynamiki wiedzy w WWW. Zakładając, że przy określonym progu spójności/zgodności wyznaczymy zbiór dokumentów „pasujących” do określonego dokumentu wzorcowego dla danej dziedziny wiedzy. Jeśli powtórzymy tę operację w określonych interwałach, możemy np. stwierdzić, na podstawie tempa wzrostu liczności takiej kolekcji, zainteresowanie tą tematyką.

Miary spójności i zgodności, choć przeznaczone dla kolekcji dokumentów można spróbować również zaadaptować dla grup użytkowników (autorów) i w ten sposób otrzymać narzędzie analizy sieci społecznych.

5.    Metody weryfikacji

 

Ponieważ badanie spójności na poziomie semantycznym wykorzystując informacje Semantic Web jest stosunkowo nowym problemem nie ma obiektywnego sposobu weryfikacji poprawności i efektywności opracowywanych metod.

Weryfikacja najczęściej polega na porównaniu wyników działania metody z wynikami innej uznanej metody. Metodami, z którymi można porównać metody analizy spójności mogą być metody rankingowe, jak Google PageRank lub klasteringowe, jak k-means.

Ponieważ porównania wyników nie można sprowadzić do porównania dwóch wartości, do obiektywnej oceny potrzeba opinii eksportów. Tu z kolei pojawiają się problemy, które mogą podważyć wiarygodność weryfikacji:

·         kryteria wyboru ekspertów dla danej dziedziny,

·         gwarancja rzetelności i bezstronności opinii eksperckich.

Drugą metodą weryfikacji, nie wymagającą opinii eksperckich jest weryfikacja empiryczna, czyli testy metody w rzeczywistym systemie przez użytkowników. Problemami  wiarygodności takich testów są jednak występujące zwykle w takich przypadkach:

·         sposób doboru i wielkość próbki reprezentacyjnej użytkowników,

·         bezinteresowność i rzetelność testerów.

Pierwsza metoda wymaga jedynie opracowania metody, jednak problemem może być znalezienie ekspertów. W drugiej metodzie znalezienie testerów nie są aż takim problemem, jednak niezbędna jest implementacja metody w działającym systemie, co zwiększa koszt tej metody weryfikacji. Do momentu szczegółowego opracowania metod analizy decyzja o sposobie ich weryfikacji nie zapadnie. Możliwe również, że zostaną zastosowane obie metody weryfikacji.



[1] Liczba dokumentów tekstowych w odpowiedzi zwracanej przez wyszukiwarkę Google na przykładowe pytania: „computer science”, „medicine” czy „psychology” jest średnio o 3 rzędy wielkości większa od liczby obrazów i 6 rzędów wielkości od liczby filmów

[2] Dziedzina miar zgodności i spójności może być kojarzona z dziedziną współczynnika korelacji i może przyjmować wartości ujemne, gdy np. dwa dokumenty są nie tylko niezgodne, ale wręcz prezentują przeciwstawne stanowiska (np. negują wzajemnie zawarte w nich informacje)

Skomentuj

Please log in using one of these methods to post your comment:

Logo WordPress.com

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

Zdjęcie z Twittera

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

Facebook photo

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

Google+ photo

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

Connecting to %s


%d bloggers like this: