Hahah jag hoppas jag hinner före.

[ailab3.git] / rapport.tex

\documentclass[a4paper, 12pt]{article}
\usepackage[swedish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{verbatim}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{parskip}
% Include pdf with multiple pages ex \includepdf[pages=-, nup=2x2]{filename.pdf}
\usepackage[final]{pdfpages}
% Place figures where they should be
\usepackage{float}

% vars
\def\title{Projekt}
\def\preTitle{Laboration 3: Information Retrieval \& Extraction}
\def\kurs{Artificiell Intelligens med inriktning mot kognition och
  design B, ht 2008}

\def\namn{Anton Johansson}
\def\mail{dit06ajn@cs.umu.se}
\def\namnett{Victor Zamanian}
\def\mailett{dit06vzy@cs.umu.se}

\def\handledareEtt{Dennis Olsson, denniso@cs.umu.se}
\def\inst{datavetenskap}
\def\dokumentTyp{Laborationsrapport}

\begin{document}
\begin{titlepage}
  \thispagestyle{empty}
  \begin{small}
    \begin{tabular}{@{}p{\textwidth}@{}}
      UMEÅ UNIVERSITET \hfill \today \\
      Institutionen för \inst \\
      \dokumentTyp \\
    \end{tabular}
  \end{small}
  \vspace{10mm}
  \begin{center}
    \LARGE{\preTitle} \\
    \huge{\textbf{\kurs}} \\
    \vspace{10mm}
    \LARGE{\title} \\
    \vspace{15mm}
    \begin{large}
      \namn, \mail \\
      \namnett, \mailett
    \end{large}
    \vfill
    \large{\textbf{Handledare}}\\
    \mbox{\large{\handledareEtt}}
  \end{center}
\end{titlepage}

\newpage
\thispagestyle{empty}
\mbox{}
\newpage

\pagestyle{fancy}
\rhead{\footnotesize{\today}}
\lhead{\footnotesize{\namn, \mail \\ \namnett, \mailett}}
\chead{}
\lfoot{}
\cfoot{}
\rfoot{}

\section*{Sammanfattning}
Reguljära uttryck (Regular Expressions, regexp eller regex) är uttryck
som innehåller olika syntax för att identifiera specifika textsträngar
ur en större mängd text. Detta kan användas inom ämnet Artificiell
intelligens för att till exempel validera och tolka indata och
specificera olika typer av språk.

\newpage
\tableofcontents
\newpage

\rfoot{\thepage}
\pagenumbering{arabic}

% TODO @anton - Problem-solving as search, basic to AI, Norvig.

\section{Introduktion}
% till ämnet.
Denna rapport går igenom användandet av Reguljära uttrycker (Regular
Expressions) med hänseende på informations hämtning inom ämnen
Artificiell intelligens.

Rapporten är formulerad och utförd enligt specifikation på sidan:\\
\verb!http://www.cs.umu.se/kurser/5DV063/HT08/assignments/!\\
\verb!lab3-spes-ht08.html!

\section{Syfte}
% med uppgiften, beskrivet med egna ord.
Syftet med rapporten är att fördjupa sig inom ett smalt ämne inom
området Artificiell Intelligens och presentera teori för det valda
ämnet på ett vetenskapligt sätt.

\section{Metodbeskrivning}
%: beskrivning av metod, material, design och procedur
Denna rapport är sammanställd genom främst en litteraturstudie
gällande AI i förhållande till Reguljära uttryck. Informations och
tankar är samlade från böcker och internetsidor, för att försöka få
ihop en överblick över de Reguljära uttryckens betydelse och
användande inom ämnet Artificiell intelligens.

\section{Litteraturstudie}
%, teoretisk fördjupning
Enligt \cite{speech} härstammar Reguljära uttryck från Alan Turings
(1936) modell för aritmetisk beräkning, även kallad
Turingmaskin. Denna maskin var abstrakt, ett tanke experiment, för att
utföra beräkningar.
% TODO Church-Turings hypotes säger att varje tänkbar process kan
% utföras av en Turingmaskin, och alltså finns det rent principiellt
% inte någon mer kraftfull beräkningsmekanism. Enligt wikipedia
% http://sv.wikipedia.org/wiki/Turingmaskin

Inspirerad av Turings arbete skapade sedan Warren McCulloch och Walter
Pitts (1943) en förenklad modell för neuronen, se \cite{norvig}
kapitel 18.

Stephen Cole Kleene definierade sedan (1951 och 1956) Ändlig
automation (Finite automation), Reguljära uttryck och påvisade dess
likhet.

Både Reguljära uttryck och Finite automation är en del av det en
språktyp som brukar kallas Reguljära språk, (''Regular Language'').

I boken \cite{speech} ger man ett exempel på hur Finite automation och
Reguljära uttryck förhåller sig till varandra. Säg att man ska
definiera ett naturligt språk, för enkelhets skull försöker vi
definiera vad som är ''ko-språk''. Vi kan säga att korrekt
''ko-språk'' definieras av kombinationerna:

\begin{verbatim}
Muu!
Muuu!
Muuuu!
...
\end{verbatim}

Detta skulle kunna beskrivas med en modell för \textbf{Finite-state
  automation} enligt figur nedan.

\begin{figure}[H]
  \begin{center}
    \includegraphics[width=110mm]{images/state.pdf}
    \caption{Ändlig automation för ''ko-språk''}
    \label{state.pdf}
  \end{center}
\end{figure}

Tillstånden \verb!q0-q4! är de giltiga tillstånd som finns, \verb!q1!
är starttillståndet och \verb!q4! representerar sluttillstånd. Pilarna
i figuren markerar möjliga förflyttningar mellan tillstånden.

Denna information går även att representera som en
\textbf{State-transition tabell}, se nedan:

\begin{center}
  \begin{tabular}{|c|l|l|l|}
    \hline
    & \multicolumn{3}{|c|}{Indata} \\
    \hline
    Tillstånd & M & u & ! \\
    \hline
    0  & 1 & 0 & 0 \\
    1  & 0 & 2 & 0 \\
    2  & 0 & 3 & 0 \\
    3  & 0 & 3 & 4 \\
    4  & 0 & 0 & 0 \\
    \hline
  \end{tabular}
\end{center}

Ovan tabell läses av uppifrån och ner. Starttillståndet \verb!0! har
en giltig förflyttning till tillstånd \verb!1!, detta gäller enbart
för indata \verb!M!, för alla andra indata finns inga giltiga
förflyttningar, detta markeras med \verb!0!.

Det korresponderande \textbf{Reguljära uttrycket} för att beskriva
''ko-språk'' skulle vara:

\begin{verbatim}
Muu+!
\end{verbatim}

Man läser det som man läser det ungefär som man läser vanlig
text. \verb!M! är tillåtet starttillstånd, följt av ett \verb!u!,
sedan markerar operatorn \verb!u+! att en eller flera \verb!u! är
tillåtna. Meningen avslutas med \verb?!?, vilket markerar
sluttillståndet. % Se sektion TODO för mer info om regexp syntax.

% REGEXP-MANUAL:
% Står på sidan 848 i Norvig.
% TODO @anton/victor - beskrivning regexp manual med fina tabeller.

Ett reguljärt uttryck består enkelt nog av text som ska matchas. Om
man vill matcha texten ''hej'' i en textsträng ''hoppsanhejsan'' så
blir det reguljära uttrycket helt enkelt bara ''hej'' och ''hej'':et i
''hoppsanhejsan'' matchas. Däremot är det mer sällan man använder
reguljära uttryck för sådana enkla matchningar. Man vill i stället
använda dem till att matcha \textbf{generella mönster}. Ett exempel på
ett mönster skulle kunna vara en e-postadress på formen
\verb!<användarnamn>@<subdomän>.<domän>!, där \verb!<användarnamn>!
kan innehålla (i detta exempel) alla siffror, alla små och stora
bokstäver, understreck, punkt, bindestreck och plus.

I stället för att behöva skriva ett textmönster för varje e-postadress
som är möjlig att konstruera (i praktiken oräkneligt antal
variationer) kan man använda sig av speciella ''texthändelser'' för
att beskriva till exempel början\slash slutet av ett ord och
början\slash slutet av en hel sträng. Man kan också definiera
teckenklasser som man vill inkludera i sitt uttryck, till exempel alla
stora bokstäver, alla små bokstäver, siffror, eller till och med
vilken godtycklig kombination av tecken som helst. Här nedanför visas
en kort tabell med några texthändelser och deras motsvarande reguljära
uttryck.

\begin{center}
  \begin{footnotesize}
    \begin{tabular}{|c|p{4cm}|l|l|l|}
      \hline
      regex-uttryck & Texthändelse & Exempel & Matchar
      \\ \hline
      \verb!\b! & Början eller slutet på ett ord & \verb!\b!text\verb!\b! & ''ord1 \textbf{text} ord3'' \\ \hline
      
      \
      
      \verb!^! & Början av en textsträng & \verb!^!text & ''\textbf{text} i början'' \\ \hline
      
      \verb!$! & Slutet av en textsträng & \verb!lutet$! & ''text i s\textbf{lutet}'' \\ \hline
      
      \verb![A-Za-z0-9]! & Definierar klass med tecknen A till Z, a
      till z och 0 till 9. & \verb![abc0-9]! & ''\textbf{b}r\textbf{a} text med \textbf{23} te\textbf{c}ken'' \\
      
      \hline
      
      \verb!.! & Står för vilket tecken som helst. & \verb!^.! & ''\textbf{t}ext'' \\ \hline
    \end{tabular}
  \end{footnotesize}
\end{center}

Om man vill matcha en e-postadress i löpande text skulle man alltså
vilja använda sig av \verb!\b! runt uttrycket för att markera att det
som finns runt omkring adressen måste vara ordavgränsare av något
slag, så som ny rad eller någon typ av blanktecken. Vill man däremot
kontrollera indata från till exempel ett formulärfält där det är
meningen att en användare ska ange enbart en e-postadress är det
däremot önskvärt att omsluta uttrycket med \verb!^! i början och
\verb!$! i slutet för att markera att hela strängen måste
\textbf{börja och sluta med} adressen.

% Olika sätt att matcha e-mail adresser.
% \b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}\b
% ^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}$

\section{Resultat}
% innehållande sammanställning/analys av eventuell testdata,
% implementering av algoritmer osv.

% TODO - resultat, användningsområden kopplade till AI.
% TODO @anton - Kolla upp och skriv om ELIZA, regexp memory.
\subsection{Applikationer av Reguljära uttryck}
\subsubsection{ELIZA}
Mer avancerade former av Reguljära uttryck kan använda sig av
minnesfunktioner för att spara tidigare matchningar. I
programmeringssråket Perl kan man göra ersättningar på formen:
\begin{verbatim}
s/hej/hejsan/
\end{verbatim}

Här ersätts alla \verb!hej! med \verb!hejsan!. För att spara träffar i
sökningen och ersätta med samma ord i ersättningssträngen använder man
grupper inom parenteser \verb!()!. Den sträng som en grupp matchar kan
sedan refereras till, \verb!\1!, representerar innehållet i första
gruppen.

\begin{verbatim}
s/heter (\w+)/Hej på dig \1, trevligt att höras/
\end{verbatim}

Ovan Reguljära uttryck skulle ersätta ''Hej jag heter Anton'' med
''Hej på dig Anton, trevligt att höras''. Denna typ av Reguljära
ersättningar utgör grunden för implementationen av Chatroboten ELIZA,
som utvecklades Joseph Weizenbaum, se \cite{speech}. Nedan följer en
kort konversation med Emacs implementering av ELIZA:

\begin{itemize}
\item[-] Hello my name is Anton
\item[-] \textbf{ELIZA:} How do you do?  What brings you to see me?
\item[-] I need help with some Artificial Intelligence questions
\item[-] \textbf{ELIZA:}Why do you say you need help with some artificial intelligence questions?
\item[-] I'm writing a rapport on Regular Expressions
\item[-] \textbf{ELIZA:}Is it because of your plans that you say you are writing a rapport on
  regular expressions?
\end{itemize}

Ovan exempel vittar om att denna typ av chatrobot har en relativt fast
ram med frågor–svar att följa, det tar inte lång tid för en mänsklig
användare att fatta att det inte är en mänsklig motpart man
kommunicerar med. ELIZA är implementerad för att svara på frågor som
rök Psykoterapi, så fort man lämnar det bekanta ämnet blir
följdfrågorna ologiska ur ett mänskligt perspektiv.

Implementationerna av ELIZA har en mängd svar hårdkodade i sig. Nedan
kodsnutt visar svaren som kan fås av indata som innehåller vissa
nyckelord gälladen död:

\begin{footnotesize}
\begin{verbatim}
(setq deathlst
        '((this is not a healthy way of thinking \.)
          ((doc$ bother) you\, too\, may die someday \?)
          (i am worried by your obsession with this topic!)
          (did you watch a lot of crime and violence on television as a child \?))
        )
\end{verbatim}
\end{footnotesize}

Även en mängd språkord sparas för att på ett bättre sätt kunna tolka
indata, exempelvis synonymer och förkortningar:

\begin{footnotesize}
\begin{verbatim}
(setq replist
  (wanna . (want to))
  (gimme . (give me))
  (gotta . (have to))
  (gonna . (going to))
  (never . (not ever))
  ...)
\end{verbatim}
\end{footnotesize}

\subsubsection{Tolkning av indata}
När ett datorsystem får indata från användare, finns en mängd
användbara Reguljära uttryck för att tolka och behandla denna indata
på ett vettigt sätt. Det kan gälla alla typer av indata. Exempelvis
som verifiering e-postadresser, datum, telefonnummer och så
vidare. Detta är användbart vid allt typ av indata från användare, och
i hög grad aktuellt när det gäller forumlär på Internet.

Till exempel kan man istället för att kräva att användare ska skriva
för och efternamn i separata rutor använda Reguljära uttryck för att
försöka tolka vad som är vad. Samma sak gäller adresser och
telefonnummer. Det kan vara intressant att ha information och ett
telefonnummers riktnummer och landskod, utan att för den sakens skull
kräva att en användare ska behöva specificera upp allt sådant
manuellt. Följer man bara vanliga konventioner för hur telefonnummer
skrivs kan man skapa ett Reguljärt uttryck för att fånga upp all denna
information ur en enda textsträng. All sådan här tolkning av indata är
väldigt bra ur användarsynpunkt, ''Don't make me click'', som Aza
Raskin \cite{raskin:website} säger i en presentation om
användarvänlighet på webbsidor.

Ett annat bra exempel på hur Reguljära uttryck kan underlätta
inmatning av data finns implementerat i den webbaserade kalendern,
http://google.com/calendar/. För att skapa en ny händelse i kalendern
kan användaren klicka på aktuell dag och skriva till exempel ''Äta mat
hos mamma kl 10-12'', detta genererar en händelse med rubrik ''Äta mat
hos mamma'' och placeras med start kl 10 och slut kl 12. Ett Reguljärt
uttryck för detta skulle kunna vara att matcha de första siffrorna
efter \verb!(kl|klockan)!, dessa borde vara starttimme för händelse.
Följs dessa siffror av \verb!.! eller \verb!:! utan mellanslag efter
skulle nästa siffror kunna representera minuter, nästa siffror kan
representera sluttid och så vidare. På detta sätt kan man med hjälp av
Reguljära uttryck representera naturligt språk för datorn. Vidare
skulle extra nyckelord kunna läggas in, till exempel \verb!hos! för
att markera att det som följer är en position, eller \verb!med! för
att markera att följande text innehåller information om deltagare i
händelsen.

\subsubsection{Datahämtning}
Reguljära uttryck kan användas för att hämta och tolka information ur
en större mängd data. Ett trivialt exempel är till exempel att försöka
svara på frågan, ''Vad är det för väder i Umeå idag'' baserat på
innehållet från sidan:

\begin{verbatim}
http://www.tfe.umu.se/weather/1440/900/10/sv-SE/now.htm
\end{verbatim}

Html-taggen som visar den aktuella temperaturen i Umeå har följande
utseende:
\begin{verbatim}
<td class="tempfont" ... >0,7 &deg;C</td>
\end{verbatim}

Det som skiljer denna tagg från de andra på sidan är attributet
\verb!class="tempfont"!. Den aktuella temperaturen visas mellan
\verb!<td ...>! och \verb!</td>!, det innebär att det skulle vara
$0,7\,^{\circ}\mathrm{C}$ dagen sidan hämtades. Följande Reguljära
uttryck matchar enbart strängen som innehåller temperatur:

\begin{verbatim}
<td class="tempfont.+?>([0-9]+,[0-9]+)
\end{verbatim}

Med denna information kan man sedan förenkla och säga att bra väder
gäller för alla $temperaturer \geq 15$ och dåligt väder gäller för
$temperaturer < 15$. Detta Reguljära uttryck är mycket specifikt och
enbart användbart på denna specifika sida så länge temperaturen
inkapslas av exakt ovan tagg och attribut.

\section{Diskussion}
% av resultatet, koppling till tidigare studier.

\section{Slutsats}
%.

%. Använd minst två referenser utöver kursboken.
\bibliographystyle{alpha}
\bibliography{books}

\end{document}