Information Extraction - metody, narzędzia, zastosowania.

Spis treści:

  1. Wprowadzenie
  2. Metody
  3. Narzędzia
  4. Przykłady
  5. Materiały

1. Wprowadzenie

1.1 Wstęp

W dzisiejszych czasach 1TB dysku to wydatek rzędu 1600$. Za kilka lat kwota ta zmniejszy się kilkukrotnie a taka pojemność nie będzie niczym nadzwyczajnym. Taka ilość miejsca pozwala na zachowanie na dysku wszystkich rozmów przeprowadzonych przez człowieka przez całe życie. Gdyby ktoś umieścił w głowie kamerę możliwe byłoby przechowywanie nagrań o długości 6 miesięcy. Przy wciąż zwiększającej się liczbie informacji coraz trudniej znaleźć tę właściwą i coraz więcej czasu zajmuje ich wyszykiwanie. W tym celu powstają metody takie jak IE. Współczesne wyszukiwarki internetowe można podzielić na 2 kategorie: - wyszukujące dane z katalogu, do którego użytkownicy sami dodają swoje strony - przeszukujące internet za pomocą tzw crawlery. Jedne i drugie metody mają zalety i wady. Aby pozbyć się wad potrzebna jest całkowicie inna technologia. Program musi znaleźć potrzebną informację, wybrać z niej to co nas może zainteresować i przedstawić w odpowiedniej formie. Technologię taką nazywamy Information Extraction.

1.2 Information Extraction

Systemy Information extraction analizują nieustrukturyzowany tekst w celu wydobycia z nich informacji. Information Extraction jest bardzo abstrakcyjną technologią z punktu widzenia użytkownika w dzisiejszym świecie. Zamiast wskazywania dokumentów, które użytkownik powinien przeczytać aby uzyskać potrzebną mu informację wydobywana są fragmenty informacji z dostępnych dokumentów, które zaspokają potrzeby użytkownika. Połączenie między wydobytą informacją, a oryginalnym dokumentem jest utrzymywane, aby umożliwić użytkownikowi możliwość zbadania jej kontekstu w razie potrzeby. Rodzaje informacji jakie są wydobywane z dokumentu są zróżnicowane ze względu na ich szczegółowość i wiarygodność. Na przykład nazwane byty takie jak osoby, czy organizacje mogą być wydobyte z 90% skutecznośći, ale nie zapewnia to znalezienia atrybutów, wydarzeń do których się one odnoszą. Poniższa tabela przedstawia szacunkową skuteczność systemów IE:

Rodzaj informacjiWiarygodność
Entities90%
Attributes80%
Facts70%
Events60%

Information Extraction nie jest tym samym co Information Retrieval: Information Extraction różni się od tradycyjnych metod, tym że nie wybiera z zbioru dokumentów tych które być może odpowiadają zapytaniu bazują na szukaniu słów kluczowych. Zamiast tego zadaniem jest wydobycie z dokumentów informacji zdefiniowanych typów: ENTITIES, ATTRIBUTES, FACTS, EVENTS, RELATIONSHIPS. Te dane są zwykle automatycznie wprowadzane do bazy danych, która może być następnie wykorzystyna do podsumowanie informacji zawartej w tekście czy też po prostu do pobierania z niej konkretnych danych.

  • Information Retrieval znajduje zbiór dokumentów - użytkownik je analizuje

  • Information Extraction wydobywa z dokumentów fakty - użytkownik je analizuje
  • Dlaczego IE jest trudne?

    Istnieją różne możliwości zapisania tej samej informacji w języku naturalnym.


    Szukana informacja może być zapisana w skomplikowany sposób:

    2. Metody

    Tworzenie wzorców - użyteczne w przypadku gdy znamy rodzaj tekstu, język oraz informację jaka powinna być w streszczeniu dokumentu. Użytkownik tworzy wzorzec w oparciu o który dokonywana jest ekstrakcja informacji. We wzorcu jest miejsce na fragmenty z przeszukiwanego tekstu (slots).

    Streszczenia dokumentów można podzielić na trzy główne grupy:

    2.1 Stałe elementy systemów IE

    Generalnie wyróżniane są dwa podejścia tworzenia systemów:

    W pierwszym przypadku reguły wyciągania informacji z dokumentu ustalane są przez twórców systemu. W drugim podejściu system sam próbuje nauczyć się reguł z zapytań użytkowników.

    W każdym systemie można wyróżnić następujące składowe.

    Procesor tekstów oraz generator wzorców - ich zadaniem jest analiza leksykalna tekstu (DTP - deep text processing oraz STP - shallow text processing). STP jest częściej stosowaną metodą ponieważ jest mniej czasochłonne - nie analizuje wszystkich możliwych interpretacji i relacji gramatycznych w dokumencie. STP jest kompromisem pomiędzy wyszukiwaniem wzorców a pełną analizą leksykalną. Procesor tekstów dokonuje również segmentacji tekstu na zdania, wykonuje interpretację skrótów, analizę podstaw słowotwórczych oraz parsing dokumentów (czyli stworzenie struktury zdania - parse tree).
    Generator wzorców - łączy elementy wyszukane przez procesor tekstów z wiedzą dziedzinową.

    2.2 Text mining

    Technologia ta powstała na podstawie data mining. Ekstrakcja informacji dokonywana jest w oparciu o wzorce. W zbiorze dokumentów wykonywana jest próba znalezienia powiązań pomiędzy nimi i łączenie tekstów w celu uzyskania informacji.
    Typowe zadania to znajdowanie podobnych dokumentów (patrz CIRES - wyszukiwarka obrazów), tworzenie rankingów dokumentów oraz ich grupowanie, tworzenie streszczeń dokumentów.

    2.3 Tworzenie streszczeń z wielu źródeł.

    Dość trudnym zadaniem stojącym przed systemami IE jest tworzenie abstraktów z wielu dokumentów. Należy określić podobieństwa i różnice pomiędzy dokumentami. System powinien wybierać tylko najważniejsze fakty z każdego z dokumentów, uszeregować je według ważności a następnie wyświetlić użytkownikowi. Często stosowaną techniką jest działanie dwustopniowe. W pierwszej fazie tworzone jest streszczenie dla każdego z dokumentów za pomocą jednej z wymienionych wcześniej metod. Druga faza polega na stworzeniu podsumowania tych streszczeń. Trudnością może być również subiektywny opis problemu prezentujący różne podejścia, może to być porównane za pomocą dodatkowych reguł wiedzy takich jak wyszukiwanie zdań przeciwstawnych, luk w informacjach itp. Innym problemem jest tworzenie podsumowań dokumentów napisanych w różnych językach.

    2.4 Pytania w języku naturalnym

    Problem udzielenia odpowiedzi na zapytania w języku naturalnym. Mają tu zastosowanie zarówno techniki IE jak i IR. Wyszukiwane są słowa kluczowe (kto, komu, co) i porównywane ze strukturą i relacjami w dokumentach.

    2.5 Podsumowanie

    Dokumenty przetwarzane przez systemy IE są różnorodne pod względem języka oraz zawartości. Dosyć przydatne i popularne są systemy używające wiedzy symbolicznej o wzorcach - tym efektywniejsze in bardziej zautomatyzowane. Programy takie wymagają jednak dużego nakładu pracy w początkowej fazie rozwoju i przerobienia dużej ilości przykładowych dokumentów.
    Głównym zadaniem dla systemów IE jest określenie ważnych treści i odrzucenie informacji nieistotnych. Najefektywniejsze podejście do tego problemu polega na określeniu właściwości tekstu takich jak użycie struktur retorycznych i spójności leksykalnej. Innymi kluczowymi elementami są długość zdania czy pozycja zdania w akapicie. Jednak dla dokumentów pochodzących z różnych źródeł może to generować błędy.
    Niektóre aspekty podsumowywania tekstów do tej pory nie zostały jeszcze dostatecznie rozwinięte. Można do nich zaliczyć np. tworzenie podsumowań, które zawierają więcej abstrakcyjnych zdań niż znaleźć można w oryginalnym tekście źródłowym.

    2.6 Działanie algorytmu IE na podstawie systemu LOLITA

    Language for the On-Line Investigation and Transformation of Abstractions

    System przetwarzania języka naturalnego LOLITA został stworzony na uniwersytecie Durham. Głównym celem jaki przyświecał twórcom była redukcja czasu odpowiedzi przy jednoczesnym zwiększeniu funkcjonalności całego systemu. Program przypomina swoją strukturą kompilator. Przetwarzanie składa się z następujących części:

    Lolita to wielofunkcyjny system który może służyć zarówno do tłumaczenia tekstów jak i do systemów IE. W zależności od tego do czego system ma służyć niektóre elementy przetwarzania mogą zostać pominięte.




    Algorytm przystosowany jest do przetwarzania równoległego. Docelową architekturą były procesory SPARC. Równoległe przetwarzanie polega na równoczesnym wykonywaniu wszystkich etapów na kilku zdaniach ze strumienia wejściowego.

    Szczegóły działania algorytmu LOLITA Parser próbuje parsować zdanie według wszystkich możliwości (parse forest). Analiza semantyczna i pragmatyczna jest stosowana do predefiniowanej liczby tych możliwości (parList). Analiza jest przeprowadzana w celu ustalenia punktacji dla każdej możliwosci. Parsing z najlepszą punktacją (pickBestAnalysis) wybierany jest jako rezultat parsingu całego tekstu. Bardzo istotną kwestią jest to aby te strategie nie były zbytnio restrykcyjne ponieważ zbyt wiele powtarzających się porównań jest przeprowadanych co powoduje brak przyspieszenia wykonywania programu.



    3. Narzędzia

    3.1 ANNIE

    GATE korzysta z systemu IE - ANNIE, A Nearly-New IE system (stworzony przez Hamish Cunningham, Valentin Tablan, Diana Maynard, Kalina Bontcheva, Marin Dimitrov i innych).

    Schemat działania systemu:


    3.1.1 Tokeniser

    Zadaniem tokenisera jest podzał tekstu na tokeny takie jak liczby, znaki przestankowe, słowa. Na przykład rozróżnia miedzy słowami pisanym wielkimi, a małymi literami. Celem jest zmaksymalizowanie wydajnośći tokenizera i przerzucenie cieżaru na reguły gramatyki, która jest bardziej elastyczna.
    Rodzaje tokenów:

    3.1.2 Gazetteer

    Listy które wykorzystuje Gazeteer sa zapisane w postaci plików tekstowych. Każda lista reprezentuje zbiór nazw, takich jak miasta, organizacje, dni tygodnia.
    Przykład (waluty):

    3.1.3 Sentence Splitter

    Moduł ten dzieli tekst na zdania. Wykorzystuje listy gazetteer'a w celu rozróżnienia kropek kończących zdanie od występującyh w innym kontekscie. Każde zdanie jest anotowane - typ 'Sentence', każda przerwa ('.', '?', '?!' itd) także dostaje odpowiednia anotację.

    3.1.4 Semantic Tagger

    Part of Speech Tagger - używa domyślnego zbioru reguł (rezultat treningu na korpusie zaczerpniętym z 'Wall Street Journal').

    Semantic Tagger jest oparty na języku JAPE (Java Annotation Patterns Engine). Korzysta z anotacji sporządzonych na wcześniejszym etapie (poza ANNIE) w celu utworzenia zbioru zaanotowanych wyrażeń.

    3.1.5 NameMatcher

    Moduł dodaje relacje pomiędzy rozpoznanymi wcześniej bytami. Nie znajduje nowych, ale może przyporządkować typ (Osoba, Organizacja, Miejsce itd). Reguły są wywoływane jeżeli porównywane byty należą do tej samej kategorii, powiedzmy są taggowane jako organizacja, czy adres. Zapobiega to zmienieniu kategorii danego bytu.

    3.2 CIRES

    CIRES (Content Based Image REtrieval System) stworzony został przez "Qasim Iqbal" w "Computer and Vision Research Center (CVRC)" na Uniwersytecie w Austin, w Teksasie. Jest bazowany na postawie wysoko oraz niskopoziomowych składowych wyszukiwanego obrazu. Wysokopoziomowa analiza polega na poszukiwaniu informacji związanych z opisem obrazu w bazie danych. Podczas niskopoziomowej analizy sprawdzane są dane związane z samym obrazem - takie jak histogram kolorów. System potrafi wyszukiwać obrazki zwizane zarówno z naturą (drzewa, niebo, zwierzęta) oraz związane z architekturą i działalnością człowieka (budynki, mosty).

    4. Przykłady

    4.1 Demo ANNIE

    4.1.1 Prezentacja online

    Demo działania systemu ANNIE wchodzącego w skład narzędzia GATE:
    Demo ANNIE

    4.1.2 Przykładowe wyniki

    Dla tekstu technicznego (krotki fragment z RFC). Ilustracja działania programu:


    4.2 Demo CIRES

    Demo działania systemu IR - CIRES:
    Demo CIRES



    5.Materiały

    Informacje: