Generator streszczeń artykułów prasowych

Spis treści

1. Opis problemu
2. Znane rozwiązania problemu
3. Źródło danych
4. Opis działania programu
5. Informacje o implementacji
6. Algorytmy użyte podczas tworzenia streszczenia
   • Przygotowanie danych treningowych
   • Algorytm wybierający kategorię artykułu
   • Algorytm wybierania najważniejszych słów
   • Algorytm wybierający najważniejsze zdania
   • Tworzenie ostatecznego streszczenia
7. Wykonane testy
   • Sprawdzenie poprawności algorytmu decydującego o klasie artykułu
   • Tworzenie streszczeń
8. Wnioski
9. Literatura

Opis problemu

Bardzo często korzystam z wiadomości RSS. W ten sposób zdobywam informacje o tym co dzieje się w kraju i na świecie. Ma on jednak kilka wad. Po pierwsze dziennie dostaję minimum 100 wiadomości i niekiedy ciężko jest mi znaleźć te, które interesują mnie najbardziej. Po drugie bardzo często jakość krótkich streszczeń, które dołączane są do wiadomości nie jest wystarczająca. Tworzone są one z myślą o jak największym zachęcenia użytkownika do przeczytania całego artykułu. W związku z tym zawierają niekiedy przekoloryzowane fakty oraz niedomówienia.

Postanowiłam poradzić sobie z tym problemem pisząc własny program tworzący streszczenia takich artykułów. Miał on zarówno w konkretny i jak najbardziej zwięzły sposób opisywać artykuł, jak również umożliwiać wyszukiwanie w takich streszczeniach konkretnych informacji.

Znane rozwiązania problemu

Problem generowania streszczeń jest zagadnieniem znanym od wielu lat. Definiuje się go jako "proces tworzenia z tekstu jego skróconej wersji, zawierającej najważniejsze informacje dla konkretnego zadania i użytkownika". Do jego rozwiązania podchodzono na dwa sposoby.

• extract - wybór fraz oraz zdań z dokumentu i złożenie ich w jeden, zwięzły tekst
• abstract - ogólne opisanie sensu całego dokumentu

Aktualnie większość generatorów streszczeń zaczyna od podejścia pierwszego i różnymi metodami związanymi z przetwarzaniem języka naturalnego stara się na podstawie wybranych informacji stworzyć jak najbardziej spójną wypowiedź. W takich pracach jak [1] można znaleźć próby stworzenia abstraktu z tekstu. Opierają się one w dużej mierze na metodach rozumienia języka naturalnego.

Mój wybór sposobu rozwiązania tego problemu był mocno uzależniony od posiadanych przeze mnie danych. Wszelkie metody związane z rozumieniem języka naturalnego wymagają posiadania złożonej bazy danych posiadającej jakąś wiedzę o świecie. Przykładem takiej bazy może być wordNet. Niestety dla języka polskiego czegoś takiego nie stworzono. W związku z tym zastosowałam metodę ekstrakcji informacji.

Źródło danych

Dane, na których pracowałam, pochodziły z dwóch różnych kanałów RSS. Program uczył się na wiadomościach z portalu www.gazeta.pl, natomiast testowany był na wiadomościach z www.rp.pl. Wybrałam dwa różne źródła danych aby sprawdzić, czy rodzaj i sposób pisania takich wiadomości ma wpływ na jakość działania mojego programu.

Opis działania programu

Działanie programu można podzielić na trzy etapy:

• proces uczenia się

• pobranie wiadomości RSS i wygenerowanie dla nich streszczeń

• przeglądanie wiadomości, wybieranie najbardziej interesujących za pomocą kategorii i słów kluczowych, oglądanie streszczeń i decydowanie się na przeczytanie całego artykułu.

Informacje o implementacji

Wszystkie moduły dotyczące tworzenia streszczenia zostały napisane w języku Python. Interfejs graficzny stworzyłam natomiast w języku C#, z użyciem biblioteki System.Windows.Forms.

Algorytmy użyte podczas tworzenia streszczenia

Przygotowanie danych treningowych

Jako danych treningowych użyłam wiadomości RSS z gazety wyborczej z czterech kanałów:

• sport
• świat
• kraj
• gospodarka

Wiadomości te musiałam początkowo przetworzyć w celu wyciągnięcia z nich najbardziej potrzebnych informacji. Odbywało się to w kilku krokach:

• wyrzucenie wszystkich niepotrzebnych html'owych tagów oraz skryptów w javaScripcie.
• dla każdego artykułu stworzenie zbioru jego słów oraz ich częstości. W tym kroku napotkałam na trudności związane z odmianą słów języka polskiego. Chciałam, aby w zbiorze słów były ich formy bazowe, a nie odmienione wersje (np zamiast słów "czarnemu", "czarnego", "czarna" chciałam mieć informację, że baza "czarny" wystąpiła trzy razy). W związku z tym na podstawie korpusu języka polskiego z stworzyłam słownik słów i ich form bazowych
• ostatecznie wyrzuciłam słowa, które występują we wszystkich artykułach nic nie mówiąc o ich treści. Zbiór takich słów znalazłam na wikipedii (nazywane są one "stop words").

Algorytm wybierający kategorię artykułu

Pierwszym etapem generowania streszczenia jest stwierdzenie do jakiej kategorii wiadomości należy dany artykuł. W tym celu stworzyłam klasyfikator Bayesa. Na podstawie danych treningowych uczył się on jakie własności mają artykuły w danej klasie. Korzystał on ze wzorów:

Dla słów, które nie należały do danych testowych pojawiał się problem, gdyż ich prawdopodobieństwo przyjmowało wartość 0. W związku z tym zastosowałam metodę wygładzania i użyłam wzoru:

Ostatecznie dla danego artykułu wybierana jest kategoria, dla której prawdopodobieństwo jest największe.

Algorytm wybierania najważniejszych słów

Drugim etapem generowania streszczenia jest wybór najważniejszych słów dla artykułu. Odbywał się on w trzech krokach:

• ostatecznie wybierane są słowa o wadze większej niż 0.1

Przyjęta waga powoduje, że odrzucane są słowa, które bardzo często wystąpiły w ważnych słowach, gdyż nie niosą one żadnej informacji o konkretnym artykule. Dodatkowo ważniejsze są słowa, które występują najczęściej w artykule, ze względu na to, że posiadają informację o jego ogólnym sensie.

Algorytm wybierający najważniejsze zdania

Etap ten sprawił mi najwięcej problemów. Początkowym pomysłem było wybieranie zdań używając klasyfikatora. Za pomocą wiadomości RSS uczyłby się jakie cechy mają zdania należące do streszczenia, a później jedynie wybierał najodpowiedniejsze z danego artykułu. Okazało się jednak, że

• wiadomości RSS są za krótkie, aby móc na ich podstawie coś wnioskować
• do takiego podejścia potrzebny jest specjalny zbiór danych treningowych. W większości prac jakie czytałam na ten temat jako dane treningowe przyjmowano specjalnie w tym celu stworzone streszczenia składające się z wybranych zdań z tekstu.

W związku z powyższym podeszłam do tego zadania w inny sposób, wykonując na danym artykule następujące kroki:

1. podział na zdania.
   Odbywał się on za pomocą znaków interpunkcyjnych. Problem skrótów i innych słów w których jest taki znak rozwiązałam sprawdzając czy następne słowo po znaku zaczyna się dużą literą. Dodatkowo przyjęłam, że zdanie nie może zaczynać się od czegoś innego niż litera i cyfra.
2. problem zaimków
   Długo pracowałam nad algorytmem, który poradziłby sobie z tym problemem. Pojawia się on w sytuacji, gdy w artykule mamy dwa zdania, np "Widziałem kota. Miał on ładne futerko.", z których drugie odwołuje się do pierwszego. Podczas wyboru najważniejszych zdań może się zdarzyć, że wybrane zostanie drugie z nich, które poza kontekstem traci sens. Aktualny algorytm, dla znalezionego zaimka:
   • szuka w poprzednim zdaniu słowa o odpowiednich własnościach (tzn dla "on" będzie szukał rzeczownika rodzaju męskiego w mianowniku).
   • jeżeli znajdzie więcej takich słów wybierze to o podobnej pozycji w zdaniu (np dla zaimka na początku zdania wybierze pierwsze z tych słów)
   • wstawi to słowo w miejsce zaimka
   Okazało się jednak, że algorytm ten nie działa bardzo efektywnie. Napotyka on na dwa problemy
   • zbyt mały zbiór danych. W artykułach bardzo często pojawiają się słowa o których nie ma żadnych informacji np nazwy własne.
   • bardzo duża możliwość umiejscowienia słowa, do którego odnosi się zaimek. Niekoniecznie musi być ono w poprzedzającym go zdaniu.
3. ocena zdań
   Dla każdego zdania liczona jest jego waga:
   • dla wszystkich słów z artykułu liczone są prawdopodobieństwa wystąpienia w oryginalnym streszczeniu
   • na ich podstawie liczone jest prawdopodobieństwo całego zdania – suma logarytmów prawdopodobieństw słów
   • powyższa waga dzielona jest przez długość zdania w celu niefaworyzowania zdań krótkich
   • dla każdego zdania zliczana jest ilość ważnych słów całego artykułu
   • do wszystkich powyższych doliczana jest jeszcze kara za kolejność zdania w artykule
   • ostatecznie wybierane są te zdania, które mają powyższą wagę większą niż 0.8

Tworzenie ostatecznego streszczenia

Postanowiłam zrezygnować z pomysłu tworzenia na podstawie wybranych informacji jednego tekstu. W związku z tym postanowiłam, że streszczenie będzie miało formę xml'owego pliku, takiej postaci:

Wykonane testy

Sprawdzenie poprawności algorytmu decydującego o klasie artykułu

1. Skuteczność klasyfikatora to 92%. Sądzę, że jest ona bardzo zadowalająca.
2. Algorytm ma większy problem z bliskimi sobie klasami. Myli więcej dokumentów z klas gospodarka oraz świat. Wynika to po pierwsze z faktu, że w obu kategoriach występują podobne słowa i tematy. Po drugie nawet człowiekowi ciężko jest niekiedy zdecydować do której kategorii powinien należeć dany artykuł np opisujący wizytę premiera Polski w Rosji. Dotyczy on zarówno tematów krajowych jak i światowych.
3. Dla klas bardziej specyficznych, takich jak sport i gospodarka algorytm działa lepiej. Wynika to z faktu, że w obu z tych kategorii występują bardzo rzadkie w innych słowa. Dla sportu są to np "gol", "mecz", "boisko". Oprócz tego występuje w nim bardzo dużo nazw własnych (nazwiska, nazwy drużyn) niewystępujących w innych kategoriach

Tworzenie streszczeń

Bezbłędne streszczenia

• Kategoria artykułu została wybrana poprawnie
• Słowa kluczowe są najważniejszymi słowami z artykułu. Pomogą, jeżeli będziemy chcieli znaleźć np wszystkie artykuły u zespole Detroit Red Wings
• Wybrane zdania są poprawne, w krótki sposób informują o czym jest cały artykuł

• W tym przypadku wiadomość RSS była bardzo krótka. W związku z tym wybrane zdania rozwijają ją. Bez czytania całego artykułu można zdobyć większość informacji ze streszczenia
• Wybrane słowa opisują treść artykułu. Na ich podstawie możnaby stworzyć dodatkową hierarchię - podkategoriami mogłaby być oświata, kurator itp.

Streszczenia z błędami

• Na podstawie tego przykładu można zauważyć, że program byłby bardziej funkcjonalny, gdyby dodać mu mechanizm znajdowania kolokacji. Są to związki słów, które występują razem tworząc nowe znaczenie. W tym przypadku, wolelibyśmy w miejscu słów kluczowych otrzymać park oliwski, niż dwa osobne słowa.
• Dodatkowo można zauważyć nieudolność algorytmu służącego do usuwania zaimków. W pierwszym zdaniu nie wiadomo do czego odnosi się słowo jego.

• W niektórych przypadkach tworzenie baz ze słów generuje błędy. Algorytm słowo Wałęsa traktuje jako czasownik w czasie teraźniejszym. W związku z tym do słów kluczowych dodaje jego bazę - bezokolicznik wałęsać. Podobny błąd zauważyłam w streszczeniu do artykułu o słonych paluszkach. W ważnych słowach pojawił się palec.
• Dodatkowo można tutaj zauważyć, że nie zawsze artykuły z Rzeczpospolitej posiadają jednakowe tagi html. W tym przypadku były one zaburzone w miejscu krótkiego streszczenia. W związku z tym algorytm nie poradził sobie ze znalezieniem go, przez co jest ono niezrozumiałe.

Całkiem błędne streszczenia

• Poszczególne części artykułu, oprócz ogólnego tematu muzyki, nie miały ze sobą nic wspólnego. Niektóre dotyczyły konkretnego koncertu, inne przedstawienia itp. W każdym z nich pojawiały się inne nazwy własne.
• Wiadomość RSS była pusta. W związku z tym program nie posiadał żadnych informacji o ważnych słowach i zdaniach.
• Wśród kluczowych słów pojawiło się słowo muzyka. Rzeczywiście jest ono ważne dla tego artykułu. Pozostałe występują tam dlatego, że pojawiały się w każdym opisie wydarzeń muzycznych, przez co były o wiele częstsze od innych.
• Wybrane ważne zdania to po prostu frazy, które pojawiały się najczęściej. Przy każdym wydarzeniu pojawiała się informacja o numerze telefonu i godzinie wydarzenia.

• Artykuł ten był bardzo długim wywiadem. W związku z tym wybór ważnych zdań był trudny. Aktualnie nie mówią one za dużo o treści całego artykułu, są wyrwane z kontekstu.
• Wybór ważnych słów również miał problemy. Wskoczyły tam słowa, które nie mówią nic o treści artykułu: ala, tenże, wszystek. Wynika to z faktu, że dla tak długiego artykułu dobrane wagi okazały się być za małe. Należałoby je uzależnić od długości tekstu.
• Ponownym problemem okazują się nazwy własne i ich bazy. W związku z tym, że program nie miał informacji o słowie Cenckiewicz pojawiło się ono w ważnych słowach w dwóch formach.

Wnioski

• Klasyfikator Bayesa dobrze poradził sobie z problemem wyboru kategorii artykułu. Wydaje się, że możnaby go spokojnie rozwinąć o następne klasy, nie tracąc w znaczącym stopniu na poprawności działania. Okazało się również, że nie jest ona uzależniona od źródła artykułów.
• Algorytmy tworzenia streszczenia radzą sobie w akceptowalny sposób z artykułami, które nie są specyficzne. Na szczęście pojawiają się one o wiele częściej, niż te oryginalne np bardzo długie, wywiady bądź krótkie notki z informacjami.
• Jakość działania programu poprawiłaby się w dużym stopniu, gdyby działał on w oparciu o bardziej specyficzną bazę danych, stworzoną specjalnie na potrzeby artykułów. Posiadałaby ona np informację jakie słowo jest nazwą własną, jak się odmienia i jakiej kategorii dotyczy. Poprawiłoby to działanie modułu rozwiązującego problem zaimków, jak również wybierającego zdania (słowa Cenckiewicz i Cenckiewicza traktowane byłyby jako jedno) oraz wyboru słów (nie pojawiałby się problem form bazowych).

Literatura

1. Abstract generation based on rhetorical structure extraction - Kenji Ono, Kazuo Sumita, Seiji Miike
2. A trainable document summarizer - Julian Kupiec, Jan Pedersen, Francine Chen
3. Extract-based summarization with simplification - Patha Lal, Stefan Ruger