\documentclass[a4paper, 12pt, twoside]{report} \input{pakiety.tex} \input{ustawienia.tex} \graphicspath{{img/}} \newcommand\blankpage{% \null \thispagestyle{empty}% %\addtocounter{page}{-1}% \newpage} \begin{document} \pagenumbering{roman} \theoremstyle{definition} \newtheorem{example}{Przykład} \numberwithin{example}{chapter} % strona tytulowa \input{strona_tytulowa.tex} % oswiadczenie \blankpage \input{oswiadczenie.tex} \blankpage \input{empty.tex} % wstawienie spisu tresci: \newpage \tableofcontents % tresc pracy - numeracja stron liczbami arabskimi \newcounter{licznikStron} \setcounter{licznikStron}{\value{page}} \pagenumbering{arabic} \setcounter{page}{\value{licznikStron}} \newpage\null\thispagestyle{empty}\newpage \input{streszczenie.tex} \newpage\null\thispagestyle{empty}\newpage \input{empty.tex} \input{abstract.tex} \newpage\null\thispagestyle{empty}\newpage \input{wstep.tex} \newpage\null\thispagestyle{empty}\newpage \input{rozdzial_1.tex} \input{rozdzial_2.tex} \newpage\null\thispagestyle{empty}\newpage \input{rozdzial_3.tex} \input{rozdzial_4.tex} \input{rozdzial_5.tex} \newpage\null\thispagestyle{empty}\newpage % spis ilustracji: %\newpage %\listoffigures %\addcontentsline{toc}{chapter}{Spis ilustracji} % spis tabel: %\newpage %\listoftables %\addcontentsline{toc}{chapter}{Spis tabel} %bibliografia \nocite{*} \bibliographystyle{acm} \bibliography{bibliografia} \addcontentsline{toc}{chapter}{Bibliografia} %\newpage\null\thispagestyle{empty}\newpage %\input{zakres_projektu.tex} \end{document}\thispagestyle{empty} \begin{figure}[h!] \centering \includegraphics[width=0.25\hsize]{uam_logo.jpg} \end{figure} \begin{center} \Large{Uniwersytet im. A. Mickiewicza w Poznaniu} \\ \large{Wydział Matematyki i Informatyki}\\ %\vskip0.2in \large{Praca magisterska}\\ \large{\textbf{Ekstrakcja informacji o godzinach rozpoczęcia mszy świętych}}\\ \normalsize{\textbf{Extracting information about church services start times}}\\ %\normalsize{\textbf{}} \end{center} %\vskip0.1in \begin{center} \Large{Dawid Jurkiewicz}\\ \normalsize{Numer albumu: 396341 }\\ \normalsize{Kierunek: Informatyka}\\ \normalsize{Specjalność: Przetwarzanie języka naturalnego} %\Large{Imię Nazwisko}\\ %\normalsize{Numer albumu: xxxxxx}\\ %\normalsize{Kierunek: Informatyka, Specjalność: xxxxxxxxxxxxxxxxxx} \end{center} %\vskip1.5in \begin{flushright} Promotor: \\ prof. UAM, dr hab. Krzysztof Jassem \\ \end{flushright} \vfill \begin{center} \rm Poznań, 2018 \end{center} \newpage \thispagestyle{empty} \newgeometry{bottom=0pt} \begin{flushright} Poznań, dnia \today \end{flushright} \vskip0.7in \begin{center} \large \textbf{Oświadczenie} \end{center} \begin{small} Ja, niżej podpisany Dawid Jurkiewicz, student Wydziału Matematyki i Informatyki Uniwersytetu im. Adama Mickiewicza w Poznaniu oświadczam, że przedkładaną pracę dyplomową pt. \begin{center} \textit{„Ekstrakcja informacji o godzinach rozpoczęcia mszyświętych”,} \end{center} %rozdziały: %\begin{center} %\textit{od 1 do 5} %\end{center} napisałem samodzielnie. Oznacza to, że przy pisaniu pracy, poza niezbędnymi konsultacjami, nie korzystałem z pomocy innych osób, a w szczególności nie zlecałem opracowania rozprawy lub jej części innym osobom, ani nie odpisywałem tej rozprawy lub jej części od innych osób. Oświadczam również, że egzemplarz pracy dyplomowej w wersji drukowanej jest całkowicie zgodny z egzemplarzem pracy dyplomowej w wersji elektronicznej. Jednocześnie przyjmuję do wiadomości, że przypisanie sobie, w pracy dyplomowej, autorstwa istotnego fragmentu lub innych elementów cudzego utworu lub ustalenia naukowego stanowi podstawę stwierdzenia nieważności postępowania w sprawie nadania tytułu zawodowego. [\qquad]* - wyrażam zgodę na udostępnianie mojej pracy w czytelni Archiwum UAM [\qquad]* - wyrażam zgodę na udostępnianie mojej pracy w zakresie koniecznym do ochrony mojego prawa do autorstwa lub praw osób trzecich \end{small} \begin{scriptsize} *Należy wpisać TAK w przypadku wyrażenia zgody na udostępnianie pracy w czytelni Archiwum UAM, NIE w przypadku braku zgody. Niewypełnienie pola oznacza brak zgody na udostępnianie pracy. \end{scriptsize} \begin{flushright} ...................................................... \end{flushright} \restoregeometry\usepackage[OT4]{polski} % tryb pelnej polonizacji \usepackage[utf8]{inputenc} % kodowanie \usepackage{makeidx} % indeks \usepackage[pdftex]{graphicx} % zalaczanie grafiki \usepackage{tikz} % grafika wektorowa \usepackage{setspace} % interlinia \usepackage{hyperref} % wewnetrzne odnosniki w dokumencie \usepackage{listings} % kody zrodlowe \usepackage{fancyhdr} % zywe paginy smierci \usepackage{tocloft} % format spisu tresci %\usepackage{array} % ladniejsze tabelki \usepackage{multirow} % laczenie wierszy w tabelach \usepackage[tableposition=top,format=hang,labelsep=period,labelfont={bf,small},textfont=small]{caption} % formatuje podpisy pod rysunkami i tabelami, format=hang powoduje, % ze kolejne linie podpisu beda wciete az do odleglosci nazwy podpisu np. "Rysunek 1." \usepackage{floatflt} % ladne oplywanie obrazkow tekstem \usepackage{url} % url w bibliografii \usepackage{amsmath} \usepackage{amsthm} \usepackage{tabularx} %lepsze tabele nie uzywane \usepackage{makecell} % do formatowania cell w tabelach \usepackage{geometry} % \usepackage{minted} %kolorowanie kodu \usepackage{subfig} \usepackage{float} % to use H option in figures \usepackage[shortlabels]{enumitem} % bold numbers in enumerate \usepackage{titling} \usepackage{afterpage}% ------------------------------------------------------------------------ % Kropki po numerach sekcji, podsekcji, itd. % Np. 1.2. Tytul podrozdzialu % ------------------------------------------------------------------------ \makeatletter \def\numberline#1{\hb@xt@\@tempdima{#1.\hfil}} %kropki w spisie tresci \renewcommand*\@seccntformat[1]{\csname the#1\endcsname.\enspace} %kropki w tresci dokumentu \makeatother %numerowanie tabel: %\renewcommand{\thetable}{\thechapter.\arabic{figure}} % %twierdzenia, definicje i lematy % \newtheorem{defin}{Definicja} \newtheorem{twr}{Twierdzenie} \newtheorem{lem}[twr]{Lemat} % ------------------------------------------------------------------------ % Inne % ------------------------------------------------------------------------ \frenchspacing \setlength{\parskip}{3pt} % odstep pom. akapitamia \linespread{1.49} % odstep pomiedzy liniami (interlinia) %\onehalfspacing \setcounter{tocdepth}{2} % stopien zaglebienia w spisie tresci \setcounter{secnumdepth}{2} % do jakiego stopnia zaglebienia numeracja % polskie podpisy \renewcommand{\figurename}{Rys.} \renewcommand{\tablename}{Tab.} %paginy zywe smierci \pagestyle{fancy} % zmiana liter w~zywej paginie na ma�e \renewcommand{\chaptermark}[1]{\markboth{#1}{}} \renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}} \fancyhf{} % usun biezace ustawienia pagin \fancyhead[LE,RO]{\small\bfseries\thepage} \fancyhead[LO]{\small\bfseries\rightmark} \fancyhead[RE]{\small\bfseries\leftmark} \renewcommand{\headrulewidth}{0.5pt} \renewcommand{\footrulewidth}{0pt} \addtolength{\headheight}{0.5pt} % pionowy odstep na kreske \fancypagestyle{plain}{% \fancyhead{} % usun p. g�rne na stronach pozbawionych % numeracji (plain) \renewcommand{\headrulewidth}{0pt} % pozioma kreska } \chapter{Podstawowe pojęcia} \section{Algorytmy genetyczne} Algorytm genetyczny jest to metaheurystyka zainspirowana teorią ewolucji Charlsa Darwin'a. Algorytm odzierciedla zjawisko ewolucji biologicznej. W procesie naturalnej selekcji najlepsze osobniki biorą udział w reprodukcji, dając początek nowej, lepiej przystosowanej generacji. % przecinek Naturalna selekcja zaczyna się od doboru najdoskonalszych osobników z populacji. Biorą one udział w reprodukcji przekazując część swoich genów potomkom. Nowa generacja powinna być lepiej przystosowana niż rodzice, ponieważ jest połączeniem genów, które zapewniły przeżycie rodzicom. W przypadku gdy wśród nowego potomstwa znalazłyby się słabe organizmy, to nie ma obawy, że ich geny przejdą do następnego pokolenia, ponieważ najprawdobniej nie dożyją one okresu rozrodczego. W ten sposób każde kolejne pokolenie jest lepsze niż poprzednie. Powyższa wiedza, wynikająca z obserwacji praw natury, została przełożona na grut matemtyki i informatyki tworząc algorytm genetyczny. % przecinek \newpage \enlargethispage{12\baselineskip} Na algorytm genetyczny składają się: \vspace*{-1mm} \begin{itemize}[noitemsep] % \setlength\itemsep{0.005em} \item inicjalizacja populacji, \item funkcja przystosowania (stosowana przy ewaluacji i selekcji), \item selekcja, \item krzyżowanie, \item mutacja. \end{itemize} \vspace*{-8mm} \begin{figure}[h!] \centering \includegraphics[width=0.9\hsize]{overview_GA.png} \caption{Schemat działania algorytmu genetycznego.} \label{overview_ga_pic} \end{figure} \newpage \subsection{Inicjalizacja populacji} Algorytm zaczyna się od utworzenia zbioru osobników zwanych populacją. Każdy z osobników jest rozwiązaniem problemu obliczeniowego. Osobnik reprezentowany jest poprzez zbiór genów (parametrów) nazywanych chromosem. Chromosom \newline jest najczęściej kodowany za pomocą: \begin{itemize} \item wektora genów, z których każdy reprezentowany jest przez liczbę całkowitą, a czasem nawet liczbę rzeczywistą, \item drzewiastych struktur danych. \end{itemize} \begin{example} \end{example} \begin{figure}[tbh] \centering \includegraphics[width=0.7\hsize]{kodowanie.png} \caption{Przykład osobników zakodowanych binarnie.} \label{kodowanie_pic} \end{figure} \subsection{Funkcja przystosowania} Funkcja przystosowania określa jak bardzo przystosowany jest osobnik (miara jakości osobnika). Im bardziej będzie przystosowany dany osobnik tym bardziej będzie faworyzowany w procesie selekcji. Funkcja przystosowania dobierana jest w zależności od modelu rozwiązywanego problemu, zwykle algorytm genetyczny dąży \newline do jej minializacji lub maksymalizacji. \begin{example} Dla problemu komiwojażera algorytm genetyczny będzie premiował te rozwiązania (w tym wypadku cykle Hamiltona), których suma wag krawędzi jest najbliższa minimalnej sumie wag krawędzi w cyklu Hamiltona. \end{example} \subsection{Selekcja} \enlargethispage{6\baselineskip} Z każdej generacji wybierany jest podzbiór populacji, który będzie brał udział \newline w rozmnażaniu, czyli w tworzeniu nowej generacji. Pojedyńcze osobniki wybierane \newline są na podstawie funkcji przystosowania. Im lepiej przystosowany dany osobnik tym większe będzie miał szanse na wzięcie udziału w reprodukcji. \noindent Wśród metod selekcji chromosomów wyróżniamy między innymi: \vspace*{-3mm} \begin{itemize} \setlength\itemsep{0.005em} \item metodę ruletki, \item metodę rankingową, \item metodę turniejową. \end{itemize} \begin{example} \textbf{Metoda ruletki.} \newline Niech $f(o_i)$ będzie przystosowaniem osobnika $o_i$ z populacji $P$, wtedy prawdopodbieństwo wyboru $o_i$ wynosi: \begin{equation*} p_i = \frac{f(o_i)}{\sum_{j=1}^N f(o_i)}, \end{equation*} gdzie $N$ to rozmiar populacji $P$. \end{example} \vspace*{-3mm} \begin{figure}[h!] \centering \includegraphics[width=0.7\hsize]{selekcja.png} \caption{Przykład selekcji metodą ruletki. Losowana jest liczba $r$ z zakresu $(0,F)$. \newline W tym wypadku wybrany został osobnik $o_4$.} \label{selekcja_pic} \end{figure} \subsection{Krzyżowanie} Krzyżowanie jest to metoda używana do tworzenia nowych osobników. Każdy nowy osobnik tworzony jest z pary rodziców. Krzyżowanie polega na łączeniu dwóch genotypów w jeden. Potomek rodziców ma zespół cech, które są kombinacją genotypów rodziców. \enlargethispage{4\baselineskip} \begin{example} \end{example} \begin{figure}[h!] \centering \includegraphics[width=1\hsize]{krzyzowanie.png} \caption{Przykładowe krzyżowanie osobników zakodowanych binarnie.} \label{krzyzowanie_pic} \end{figure} \subsection{Mutacja} Mutacja jest to operator genetyczny gwarantujący różnorodność osobników. Mutacja wprowadza do genotypu losowe zmiany. Zazwyczaj mutacja zachodzi z bardzo niskim prawdopodbieństwem - najczęściej około 1\%. Wyższe prawdopodbieństwo mogłoby spowodobać, że rozwiązania psułyby się zamiast delikatnie zmieniały. W zależności od kodowania mutację można przeprowadzić przykładowo na następujące sposoby: \begin{itemize} \item w przypadku kodowania binarnego można zanegować losowy bit, \item w przypadku kodowania liczbami całkowitymi (rzeczywistymi) można losowy gen zamienić liczbą wylosowaną z ustalonego ręcznie zakresu liczb całkowitych (rzeczywistych). \end{itemize} \newpage \begin{example} \end{example} \begin{figure}[th] \centering \includegraphics[width=0.3\hsize]{mutacja.png} \caption{Mutacja poprzez zanegowanie losowego bitu.} \label{mutacja_pic} \end{figure} \subsection{Kryterium stopu} Proces generowania coraz to nowyszych pokoleń trwa aż do osiągnięcia kryterium stopu. Popularne kryteria to: \begin{itemize} \item z góry ustalona liczba iteracji, \item znalezienie osobnika (rozwiązania), dla którego funkcja przystosowania \newline da wystarczająco dobry wynik, \item wykorzystanie określonej liczby zasobów np. czasu pracy procesora lub pieniędzy, \item przerwanie procesu, gdy kolejne iteracje nie tworzą lepszych rozwiązań, \item osiągnięcie najlepszego rozwiązania. \end{itemize} \newpage \section{Sieci neuronowe} \chapter{Metody ekstrakcji informacji} % w kontekście mojego projektu W tym rozdziale zaprezentowane są wybrane metody, które brane były pod uwagę lub zostały zastosowane w opisywanym tutaj systemie ekstrakcji informacji o godzinach rozpoczęcia mszy świętych. \section {Algorytmy \textit{bootstraping}} Niech $J$ będzie dowolną reprezentacją języka (wyraz, fraza, wyrażenie regularne itp.). W dziedzinie przetwarzania języka naturalnego \textit{bootstraping} to technika wyszukiwania niezanotowanych (nieprzypisanych do badanej klasy) $J$ przy użyciu małego zbioru specjalnie wyselekcjonowanych zanotowanych $J$. Implementacji algorytmu \textit{bootstraping} jest wiele, wszystkie jednak oparte są na następującym schemacie \cite{Bootstrap}: \enlargethispage{4\baselineskip} \begin{enumerate} \item Stwórz pustą listę reprezentacji języka $J$. % pusta lista $J$, pusta lista wyrazów, pusta % lista fraz \item Zainicjalizuj listę starannie dobranymi $J$. \item Wykorzystaj elementy listy do znalezienia nowych $J$ z korpusu treningowego. \item Oceń nowe $J$; najlepsze $J$ dodaj do listy. \item Wróć do 3. i powtarzaj aż do osiągnięcia z góry określonej liczby iteracji \newline lub spełnienia innego warunku stopu. \end{enumerate} % \textit{Bootstraping} jest szczególnie przydatny w przypadku, gdy mamy mały % zbiór treningowy, ponieważ z jego pomocą jesteśmy w stanie powiększyć zbiór % treningowy. %todo poprawić \subsection{Wzorce Hearst} Jednymi z pierwszych implementacji algorytmu \textit{bootstraping} w dziedzinie ekstrakcji informacji są wzorce Hearst \textit{(ang. Hearst patterns)} \cite{Hearst}. \smallskip \noindent Znajdowanie nowych przykładów uczących za pomocą wzorców Hearst przedstawia się następująco: \begin{enumerate} \item Wybierz relację leksykalną $R$. \item Utwórz początkowy zbiór $S$ par $(x, y)\in R$, gdzie $x$ i $y$ to słowa lub frazy. \item Znajdź zdania, które zawierają pary ze zbioru $S$. \item Przyjrzyj się kontekstowi, w jakim występują te pary. Załóż, że często powtarzające się wzorce reprezentują relację R. \item Wykorzystaj nowo odkryte wzorce do znalezienia kolejnych par $(x, y)\in R$. \item Dodaj nowo znalezione pary do zbioru $S$, wróć do 3. i powtarzaj aż do osiągnięcia z góry określonej liczby iteracji. \end{enumerate} \enlargethispage{4\baselineskip} \subsubsection{Przykład} Rozważmy relację R taką, że $(x, y) \in R$ wtedy, gdy $x$ został pochowany w $y$. Załóżmy, że zaczynamy z parą \texttt{('Józef Piłsudski', 'Kraków')}$\in R$. W korpusie treningowym szukamy zdań zawierających w sobie parę \texttt{('Józef Piłsudski', 'Kraków')} i otrzymujemy zdania takie jak: \centerline{„Józef Piłsudski został pochowany w Krakowie.”} \centerline{„Miejsce pochówku Józefa Piłsudskiego to Kraków.”} \centerline{„Grób Józefa Piłsudskiego znajduje się w Krakowie.”} \noindent Ze znalezionych zdań tworzymy następujące wzorce: \centerline{$x$ został pochowany w $y$.} \centerline{Miejsce pochówku $x$ to $y$.} \centerline{Grób $x$ znajduje się w $y$.} \noindent Wykorzystujemy powyższe wzorce do znalezienia nowych par będących w relacji $R$, przykładowo: % i otrzymujemy: \centerline{\texttt{('Witold Doroszweski, 'Warszawa')}} \centerline{\texttt{('Jana Długosz', 'Zakopane')}} \noindent Następnie szukamy zdań w których występują powyższe pary, na przykład: \centerline{„Witold Doroszewski spoczywa w Warszawie.”} \centerline{„Na cmentarzu w Zakopanem mieści się grób Jana Długosza.”} \noindent Z nowo otrzymanych zdań tworzymy poniższe wzorce: \centerline{$x$ spoczywa w $y$.} \centerline{Na cmentarzu w $y$ mieści się grób $x$.} \noindent Powtarzamy powyższy algorytm aż do osiągnięcia określonej liczby iteracji. % \subsection{Miejsce na opis bardziej skomplikowanej metody implementującej % algorytm \textit{bootstraping}} \section{Automatyczne generowanie wyrażeń regularnych za pomocą algorytmów genetycznych} W 2015 roku Bartoli i in. zaprezentowali efektywny algorytm genetyczny do generowania wzorców zapisanch w postaci wyrażeń regularnych przy użyciu niewielkiego zbioru zanotowanych przykładów (fraz oznaczonych jako pasujące do wyrażeń regularnych) \cite{genetic}. Nowością było zastosowanie metody „dziel i zwyciężaj”. Zamiast uczyć się jednego wyrażenia regularnego, które znajdowałoby wszystkie przykłady, system uczy się wielu różnych wzorców, które dopiero po połączeniu alternatywą tworzą ostateczne wyrażenie regularne. % Problem automatycznego generowania wyrażeń regularnych jest złożony. Warto zauważyć, że % bardzo łatwo wytrenować na zbiorze treningowym system, który znajdzie wzorzec o bardzo wysokiej precyzji i niskiej % czułości (np. wystarczy alternatywa, której składnikami są wszystkie zanotowane przykłady), ale szczególnie trudno wytrenować system tak, aby generalizował się na przypadki poza % zbiorem treningowym (innymi słowy taki system łatwo przetrenować). %(otrzymali wyniki bardzo zadowalające wyniki ) tabela wyników \subsection{Opis problemu} Niech $x_s$ będzie spójnym podciągiem ciągu znaków $s$ reprezentowanym przez indeks początkowy i końcowy w $s$. Dla ułatwienia, w przykładach $x_s$ będziemy reprezentować przez zawartość i indeks początkowy. \enlargethispage{1\baselineskip} Na przykład $x_s=\texttt{ku}_0$, $x'_s=\texttt{ku}_2$, $x''_s=\texttt{kuku}_0$, $x'''_s=\texttt{łka}_4$ to spójne podciągi ciągu znaków $s=\texttt{kukułka}$. $x_s$ nazywa się nadłańcuchem $x'_s$ (a $x'_s$ jest podłańcuchem $x_s$), jeśli (i) $x'_s$ jest krótszy niż $x_s$, (ii) indeks początkowy $x'_s$ jest nie mniejszy niż indeks początkowy $x_s$ oraz (iii) indeks końcowy $x'_s$ jest nie większy niż indeks końcowy $x_s$. Na przykład $\texttt{ku}_0$ jest podłańcuchem $\texttt{kuku}_0$. Mówi się, że $x_s$ nachodzi na $x'_s$ (lub $x'_s$ nachodzi na $x_s$), jeśli (i) indeks początkowy $x_s$ jest nie większy niż indeks końcowy $x'_s$ oraz (ii) indeks końcowy $x_s$ jest nie mniejszy niż indeks początkowy $x'_s$. Niech $(s,X)$ będzie przykładem uczącym, w którym $X$ to zbiór nienachodzących na siebie $x_s$. Jako $e(s,P)$ oznacza się zbiór wszystkich ciągów $x_s$ wyekstrahowanych poprzez zbiór wyrażeń regularnych $P$, taki że (i) $x_s$ pasuje do jakiegokolwiek wyrażenia regularnego $p\in P$, (ii) każdy nadłańcuch $x'_s$ ciągu $x_s$ nie pasuje do żadnego wyrażenia regularnego $p\in P$ oraz (iii) dla każdego ciągu $x''_s\neq x_s$, który nachodzi na $x_s$, indeks początkowy $x''_s$ jest większy od indeksu początkowego $x_s$ albo $x''_s$ nie pasuje do żadnego $p\in P$. Między innymi dla $s=\texttt{abcde}\textvisiblespace \texttt{a}$ i $P=\{\texttt{a}, \texttt{bc}, \texttt{cde}, \texttt{de}\}$ $e(s,P)=\{a_0, a_6, bc_1\}$. Należy zwrócić uwagę, że $de_3 \notin e(s,P)$ i $cde_2 \notin e(s,P)$, ponieważ nie spełniają one kolejno warunków (ii) oraz (iii). Mając dwa zbiory anotowanych przykładów $(E, E')$, zbiór wyrażeń regularnych $P$ generowany jest używając tylko i wyłącznie $E$ w taki sposób, że (i) maksymalizowana jest średnia harmoniczna z precyzji i pokrycia (ang. \textit{recall}) na $E'$ oraz (ii) minimalizowana jest $\sum_{p\in P}{l(p)}$, gdzie $l(p)$ to długość wyrażenia regularnego $p$. Wtedy precyzja i pokrycie definiowane są w następujący sposób: $$Prec(P, E'):=\frac{\sum_{(s,X)\in E'}{|e(s,P) \cup X|}}{\sum_{(s,X)\in E'}{|e(s,P)|}}$$ $$Rec(P, E'):=\frac{\sum_{(s,X)\in E'}{|e(s,P) \cup X|}}{\sum_{(s,X)\in E'}{|X|}}$$ \subsection{Szczegóły algorytmu genetycznego} Na wejściu do algorytmu genetycznego podawany jest zbiór treningowy $T$, a na wyjściu otrzymuje się pojedyncze wyrażenie regularne $p$. Zbiór treningowy $E$ składa się z trójki uporządkowanej $(s,X_d,X_u)=(s,X)$, gdzie $X_d$ to zbiór pożądanych ciągów $x_s$ ekstrahowanych przez $p$, a $X_u$ to zbiór niepożądanych ciągów $x_s$ ekstrahowanych przez $p$. Nie istnieje żaden podłańcuch $x'_s$ ciągu $x_s \in X_d$, który nachodzi na jakikolwiek podłańcuch $x'''_s$ ciągu $x''_s \in X_u$. Wyrażenie regularne reprezentowane jest za pomocą drzewa. Liście składają się z: \begin{enumerate} \item zakresów znaków np. \texttt{a-ż}, \texttt{A-Ż} i \texttt{0-9}, \item klas znaków \texttt{\textbackslash w} i \texttt{\textbackslash d}, \item cyfr od 0 do 9, \item częściowych zakresów, czyli największego zakresu znaków występującego \newline w $\bigcup_{(s,X_d,X_u)\in T}X_d$, np. dla $\texttt{\{pokój}_3, \texttt{ubierać}_{13}\}$ otrzymuje się zakresy \newline \texttt{j-k} i \texttt{o-r} (przy założeniu, że korzysta się z polskiego alfabetu), \item znaków specjalnych takich jak np. \texttt{\textbackslash ., :, @}. \end{enumerate} Wierzchołki nie będące liściami składają się z: \begin{enumerate} \item konkatenacji $\bullet \bullet$, \item klasy znaków $[\bullet]$ i jej negacji $[ \hat{\ } \bullet ]$, \item kwantyfikatorów bez nawrotów (ang. possessive quantifiers) $\bullet \ast$\texttt{+}, $\bullet$\texttt{++}, $\bullet$\texttt{?+ } oraz $ \bullet \{ \bullet, \bullet \}$\texttt{+}, \item oznaczeń grup nieprzechwytujących \texttt{(?:$\bullet$)}. \end{enumerate} Wyrażenie regularne $p$ otrzymuje się przechodząc drzewo sposobem \textit{post-order},\newline w którym pod znak $\bullet$ w wierzchołkach niebędących liściami podstawia się łańcuchy znaków zawarte w dzieciach tego wierzchołka. \begin{figure}[tbh] \centering \includegraphics[width=0.7\hsize]{drzewo.png} \caption{Reprezentacja wyrażenia regularnego \texttt{abc\{1,2\}+} za pomocą drzewa.} \label{drzewo_pic} \end{figure} \subsubsection{Inicjalizacja populacji} Jako $n_{pop}$ oznacza się rozmiar populacji wyrażeń regularnych $P$. Dla każdego $x_s\in \bigcup_{(s,X_d,X_u)\in T}X_d$ budowane są dwa osobniki (osobnikiem jest wyrażenie regularne). Pierwszy osobnik tworzony jest z $x_s$, w którym każda cyfra zamieniana jest na \texttt{\textbackslash d} oraz każda litera zamienia jest na \texttt{\textbackslash w}. Drugi osobnik tworzony jest identycznie jak pierwszy z tą różnicą, że wielkrotne wystąpienia \texttt{\textbackslash d} (lub \texttt{\textbackslash w}) zastępuje się oznaczeniami \texttt{\textbackslash d++} (lub \texttt{\textbackslash w++}). W szczególności dla $x_s=\texttt{14\textvisiblespace lutego}$ otrzymujemy osobniki \texttt{\textbackslash d\textbackslash d\textvisiblespace \textbackslash w\textbackslash w\textbackslash w\textbackslash w\textbackslash w\textbackslash w} oraz \texttt{\textbackslash d++\textvisiblespace \textbackslash w++}. Jeśli liczba wygenerowanych osobników jest większa niż $n_{pop}$, to są one losowo usuwane, natomiast jeśli liczba osobników jest mniejsza niż $n_{pop}$, to brakujące osobniki są generowane metodą \textit{Ramped half-and-half} \cite{ramped}. Osobniki niereprezentujące poprawnego wyrażenia regularnego są odrzucane, a w ich miejsce generowane \newline są nowe. \subsubsection{Funkcja przystosowania} Dla każdego osobnika funkcję przystosowania defniuje się jako: $$f(p):=(Prec(p,T), Acc(p,T), l(p))$$ Wprowadza się również dwie nowe operacje $\sqcap$ i $\ominus$, na których oparte są funkcje $Prec$ i $Acc$. Zakłada się, że $X_1$ i $X_2$ to zbiory spójnych podciągów tego samego łańcucha znaków $s$. Wtedy: \begin{itemize} \item $X_1 \ominus X_2$ jest zbiorem takich $x_s$, że (i) są one spójnym podciągiem jakiegoś elementu $X_1$, (ii) nie nachodzą na żaden z elementów $X_2$ oraz (iii) nie mają nadłańcucha, który spełnia warunki (i), (ii); \item $X_1 \sqcap X_2$ jest zbiorem takich $x_s$, że (i) są one spójnym podciągiem jakiekolwiek elementu $X_1$ i jakiekolwiek elementu $X_2$ oraz (ii) nie mają nadłańcucha, który spełnia (i). \end{itemize} Między innymi dla $X_1=\{\texttt{Ja}_0, \texttt{ty}_4, \texttt{Adam\textvisiblespace Małysz}_9\}$, $X_2=\{\texttt{Ja}_0, \texttt{Małysz}_{14}\}$: \newline $X_1 \ominus X_2 = \{\texttt{ty}_4, \texttt{Adam\textvisiblespace}_{9}\}$, $X_1 \sqcap X_2 = \{\texttt{Ja}_0,\texttt{Małysz}_{14}\}$. \enlargethispage{4\baselineskip} \bigskip \noindent W końcu $$Prec(p,T):=\frac{\sum_{(s,X_d,X_u)\in T}|e(s,\{p\})\cap X_d|}{\sum_{(s,X_d,X_u)\in T}|e(s,\{p\})\sqcap (X_d \cup X_u)|}$$ Drugi element trójki uporządkowanej, czyli $Acc(p,T)$ jest średnią arytmetyczną pokrycia na znakach (ang. True Positive Character Rate skr. TPCR) i specyficzności na znakach (ang. True Negative Character Rate skr. TNCR): \begin{equation*} \begin{split} TPCR(p,T) & :=\frac{\sum_{(s,X_d,X_u)\in T}||e(s,\{p\})\sqcap X_d||}{\sum_{(s,X_d,X_u)\in T}||X_d||} \\[3pt] TNCR(p,T) & :=\frac{\sum_{(s,X_d,X_u)\in T}||s \ominus e(s,\{p\}) \sqcap X_u||}{\sum_{(s,X_d,X_u)\in T}||X_u||} \\[3pt] Acc(p,T) & :=\frac{TPCR(p,T) + TNCR(p,T)}{2} \end{split} \end{equation*} gdzie $||X|| = \sum_{x_s\in X}l(x_s)$, a $l(x_s)$ oznacza długość ciągu $x_s$. Osobniki porównywane są w pierwszej kolejności na podstawie $Prec$, \newline potem za pomocą $Acc$, a na końcu w przypadku identycznych $Prec$ i $Acc$ brane jest pod uwagę $l(p)$. \enlargethispage{4\baselineskip} % \end{split} % \end{equation*} % \begin{equation*} % \begin{split} \textbf{Przykład} \begin{equation*} \begin{split} s & = \texttt{70.\textvisiblespace Poprawny\textvisiblespace zapis\textvisiblespace dat\textvisiblespace to\textvisiblespace np.\textvisiblespace } \\ & \quad \; \texttt{10.04.2019,\textvisiblespace 1.03.2018\textvisiblespace (nie\textvisiblespace 01.03.2018).} \\ X_d & =\{\texttt{10.04.2019}_{30}, \texttt{1.03.2018}_{42}\} \\ X_u & = \{\texttt{70.\textvisiblespace Poprawny\textvisiblespace zapis\textvisiblespace dat\textvisiblespace to\textvisiblespace np.\textvisiblespace }_0, \texttt{\textvisiblespace (nie\textvisiblespace}_{52}, \;\texttt{).}_{67}\} \\ T & = \{(s, X_d, X_u)\} \\ p_1 & = \texttt{\textbackslash d\{2,2\}+.\textbackslash d\{2,2\}+.\textbackslash d\{4,4\}+.} \\ p_2 & = \texttt{\textbackslash d\{2,4\}+} \\ e(s, {p_1}) & = \{\texttt{10.04.2019}_{30}, \texttt{01.03.2018}_{57}\} \\ e(s, {p_2}) & = \{\texttt{70}_{0}, \texttt{10}_{30}, \texttt{04}_{33}, \texttt{2019}_{36}, \texttt{03}_{44}, \texttt{2018}_{47}, \texttt{01}_{57}, \texttt{03}_{60}, \texttt{2018}_{63}\} \\[3pt] Prec(p_1, T) & = \frac{|\{\texttt{10.04.2019}_{30}\}|}{|\{\texttt{10.04.2019}_{30}\}|} =\frac{1}{1} = 1 \\[3pt] Prec(p_2, T) & = \frac{|\emptyset|}{|\{\texttt{70}_{0}, \texttt{10}_{30}, \texttt{04}_{33}, \texttt{2019}_{36}, \texttt{03}_{44}, \texttt{2018}_{47}\}|} = \frac{0}{6} = 0 \\[4pt] TPCR(p_1, T) & = \frac{||\{\texttt{10.04.2019}_{30}\}||}{||\{\texttt{10.04.2019}_{30}, \texttt{1.03.2018}_{42}\}||} = \frac{10}{19} \\[4pt] TPCR(p_2, T) & = \frac{||\{\texttt{10}_{26}, \texttt{04}_{29}, \texttt{2019}_{32}, \texttt{03}_{40}, \texttt{2018}_{43}\}||}{||\{\texttt{10.04.2019}_{30}, \texttt{1.03.2018}_{42}\}||} = \frac{14}{19} \\[4pt] TNCR(p_1, T) & = \frac{||\{\texttt{70.\textvisiblespace Poprawny\textvisiblespace zapis\textvisiblespace dat\textvisiblespace to\textvisiblespace np.\textvisiblespace }_0, \texttt{\textvisiblespace (nie\textvisiblespace}_{51}, \;\texttt{).}_{67}\}||}{||\{\texttt{70.\textvisiblespace Poprawny\textvisiblespace zapis\textvisiblespace dat\textvisiblespace to\textvisiblespace np.\textvisiblespace }_0, \texttt{\textvisiblespace (nie\textvisiblespace}_{51}, \;\texttt{).}_{67}\}||} = \frac{38}{38} = 1\\[4pt] TNCR(p_2, T) & = \frac{||\{\texttt{.\textvisiblespace Poprawny\textvisiblespace zapis\textvisiblespace dat\textvisiblespace to\textvisiblespace np.\textvisiblespace }_2, \texttt{\textvisiblespace (nie\textvisiblespace}_{51}, \;\texttt{).}_{67}\}||}{||\{\texttt{70.\textvisiblespace Poprawny\textvisiblespace zapis\textvisiblespace dat\textvisiblespace to\textvisiblespace np.\textvisiblespace }_0, \texttt{\textvisiblespace (nie\textvisiblespace}_{51}, \;\texttt{).}_{67}\}||} = \frac{36}{38}\\[4pt] f(p_1) & = \bigg(1, 0.76=\frac{1}{2}\Big(\frac{10}{19} + 1\Big), 20 \bigg)\\ f(p_2) & = \bigg(0, 0.84=\frac{1}{2}\Big(\frac{14}{19} + \frac{36}{38}, \Big), 24\bigg) \end{split} \end{equation*} Zgodnie z wprowadzoną funkcją oceny osobnik $p_1$ jest lepiej przystosowany niż osobnik $p_2$. \subsubsection{Ewolucja populacji} Populacja $P$ o liczności $n_{pop}$ ewoluuje następująco. W każdej epoce $0.1n$ osobników generowanych jest losowo za pomocą metody \textit{Ramped half-and-half} \cite{ramped}, kolejne $0.1n$ osobników powstaje za pomocą mutacji, a pozostałe $0.8n$ otrzymuje \newline się metodą krzyżowania. Z populacji P i zbioru nowo wygenerowanych osobników wybierane jest $n$ najlepiej przystosowanych osobników, które tworzą nową populację. Osobniki wybierane są do mutacji i krzyżowania metodą turnieju (losowanie z $P$ siedmiu osobników i wyłonienie najlepszego). Pondato wymusza się także różnorodność między fenotypami osobników, tzn. jeśli oba osobniki mają identyczny łańcuch znaków to w populacji zostawia się tylko jednego z nich. Koniec iteracji następuje, gdy zostanie osiągnięty z góry ustalony limit iteracji lub najlepiej przystosowany osobnik nie zmieni się od określonej liczby epok. Finalne wyrażenie regularne $p$ to najlepiej przystosowany osobnik po zakończeniu wszystkich iteracji. \subsubsection{Zastosowanie metody „dziel i zwyciężaj”} Zbiór wyrażeń regularnych $P$ generowany jest za pomocą strategii „dziel i zwyciężaj”. W każdej iteracji spójne podciągi ciągu znaków $s$, które zostały poprawnie wykryte przez $P$ są usuwane ze zbioru treningowego. \enlargethispage{2\baselineskip} Oby uniknąć przetrenowania, czyli bardzo wysokiego \textit{F-measure} na $E$, a niskiego na $E'$, zbiór treningowy $E$ dzielony jest losowo na dwa zbiory $E_{train}$ i $E_{validation}$ takie, że $E=E_{train} \cup E_{validation}$, $E_{train} \cap E_{validation} = \emptyset$ \newline i $\sum_{(s,X)\in E_{train}}|X|\approx \sum_{(s,X)\in E_{validation}}|X|$. \noindent Procedura generowania zbioru wyrażeń regularnych $P$ prezentuje się następująco. Zacznij z $P=\emptyset$ i z $T$ utworzonym w taki sposób, że dla każdego $(s,X)\in E_{train}$, trójka uporządkowana $(s, X, \{s\} \ominus X)$ jest dodawana do $T$, \newline gdzie $X_d:=X$ i $X_u:=\{s\} \ominus X$. \noindent Następnie dopóki $\bigcup_{(x,X_d,X_u)\in T}X_d\ne \emptyset$ powtarzaj: \begin{enumerate} \item Wykonaj algorytm genetyczny na $T$ i otrzymaj wyrażenie regularne $p$. \item Jeśli $Prec(p,T)=1$, to $P:=P\cup\{p\}$, w przeciwnym wypadku przerwij pętlę. \item Dla każdego $(s, X_d, X_u)\in T$ ustaw $X_d:=X_d\setminus e(s, \{p\})$. \end{enumerate} Powyższa procedura powtarzana jest wiele razy z różnym zarodkiem generatora liczb losowych (startowy zbiór trenujący $T$ pozostaje bez zmian), by otrzymać dużo różnych zbiorów $P$, z których na końcu wybierany jest ten o najwyższej  średniej harmonicznej z precyzji i pokrycia na $E=E_{train} \cup E_{validation}$. \section{Sieci neuronowe} \chapter{Metodologia} \section{Ogólny zarys} \section{Zbieranie informacji o parafiach} \section{Wyszukiwanie stron internetowych parafii} \section{Wydobywanie tekstu ze stron parafialnych} \section{Organizacja danych} % może zbyt inżynierskieby \section{Ekstrakcja godzin rozpoczęcia mszy świętych} \subsection{Ogólny zarys} \subsection{Named entity recognition} \subsection{Słowa kluczowe} \subsection{Reguły} \subsection{Bootstraping} \subsection{Otoczenia słów (ang. word embeddings)} \chapter{Rezultaty} \section{Wyrażenia regularne} \section{Bootstraping} \section{Autorska metoda} \subsection{Ewaluacja wewnętrzna} %F1 score \subsection{Ewaluacja zewnętrzna} % w systemie webowym, użytkownicy \chapter{Wnioski} \chapter{Perspektywy na przyszłość} \chapter*{Streszczenie} TODO \textbf{Słowa kluczowe:} ekstrakcja informacji\chapter*{Abstract} todo \textbf{Key words:} information extraction\markboth{Wstęp}{Wstęp} \addcontentsline{toc}{chapter}{Wstęp} @ARTICLE{Bootstrap, author = {Daniel Waegel}, title = {A Survey of Bootstrapping Techniques in Natural Language Processing}, journal = {Department of Computer Science, University of Delaware, Literature Survey Reports}, year = {2013} } @ARTICLE{Hearst, author = {Marti Hearst }, title = {Automatic Acquisition of Hyponyms from Large Text Corpora.}, journal = {Proc. of the Fourteenth International Conference on Computational Linguistics, Nantes, France.}, year = {1992} } @inproceedings{genetic, title={Learning text patterns using separate-and-conquer genetic programming}, author={Bartoli, Alberto and De Lorenzo, Andrea and Medvet, Eric and Tarlao, Fabiano}, booktitle={European Conference on Genetic Programming}, pages={16--27}, year={2015}, organization={Springer} } @article{ramped, title={Genetic programming as a means for programming computers by natural selection}, author={Koza, John R}, journal={Statistics and computing}, volume={4}, number={2}, pages={87--112}, year={1994}, publisher={Springer} } buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor buffor