source: liacs/ai/poker/report.tex@ 382

%
% $Id: report.tex 557 2008-04-08 22:57:09Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage{graphicx}
\usepackage{url}
\usepackage{multicol}
\usepackage{fancybox}
\usepackage{amssymb,amsmath}

\author{Rick van der Zwet, Universiteit Leiden}
\title{Kunstmatige Intelligentie  2008 --- opdracht 3 \\
\large{Neurale netwerken}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}\\
  \\
  LIACS\\
  Leiden University\\
  Niels Bohrweg 1\\
  2333 CA Leiden\\
  The Netherlands}
\date{\today}

\begin{document}

\maketitle

\section{Inleiding}

Dit verslag gaat over de derde programmeer-opgave van het vak
kunstmatige intelligentie~\cite{opdracht}. Welke als opdracht heeft om
een neuraal netwerk te bouwen, wat met \'e\'en verborgen laag Poker
handen kan classificeren. Dit alle met met als doel de bouw en
werking van neurale netwerken (\emph{NN}) uit het college
boek~\cite{collegeboek} beter te kunnen begrijpen.

\section{Uitleg probleem}

Om het probleem een visueel gestalte te geven is gekozen om een
pokerhand te bepalen. Als invoer wordt er 5 kaarten uitgegeven, waarvan
de waarde en kleur apart gecodeerd zijn in respectievelijk 13 en 4
mogelijke waardes..  Met deze kaarten kan er een van de 10 combinaties
van een pokerhand gevormd worden. Als er 5 willekeurige kaarten
aangeboden worden is het de taak van het NN daar de juiste combinatie
bij te zoeken.  Er wordt geen informatie gegeven wat de regels zijn om
de combinaties te maken, maar er worden wel voorbeelden gegeven van
valide combinaties.  Nadat alle voorbeelden gezien zijn worden er
willekeurige combinaties kaarten aangeboden, de taak is om deze set zo
goed mogelijk te clasifiseren.


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.25]{neuraal-netwerk}
\end{center}
\caption{
Voorbeeld van een 1-laags neuraal netwerk met 2 invoer nodes, 3
verbonden perceptronen, 2 uitvoer nodes.
}
\label{fig:feedforward}
\end{figure}


\section{Theorie}

Voor de menselijke beleving is het relatief makkelijk om in \'e\'en opzicht
te zien welke pokerhand er in hand is of om dit aan te leren, door
voorbeelden aan te bieden, waarbij dan logische regels worden afgeleid.
Om in een algoritme hetzelfde \emph{lerende} gedrag te simuleren/cre\"eren
zijn NN uitgevonden in verschillende smaken en stijlen. Dit verslag
focust zich in feed-forward netwerken welke als voordeel hebben dat ze
een van de simpelste neurale netwerken zijn, waarbij de informatie maar
een richting op gaat.

Bij een NN kan uit 3 of meerdere lagen onderscheiden worden. Als eerste
is er de \emph{invoer} laag met zijn invoer nodes, waar de gecodeerde
invoer op komt te staa. Bij gecodeerd wordt een waarde tussen 0 en 1
bedoeld de reden hiervan komt later aan de orde. De \emph{verborgen}
laag kan uit meerdere lagen bestaan, maar tijdens dit verslag zal focust
worden op \'e\'en laag. In deze verborgen laag zitten de
\emph{perceptronen}, welke de intelligentie zijn van het NN. In de
\emph{uitvoer} laag zitten de uitvoer nodes, welke hun waarde weer
tussen 0 en 1 bevinden.
Tussen alle nodes in de invoer laag en de
uitvoer laag zitten takken, zo ook tussen de verborgen laag en de
uitvoer laag. Zie ook figuur~\ref{fig:feedforward}.

Een perceptronen heeft de eigenschap dat het een \emph{activatie}
functie bezit en een drempel waarde. Stel dit voor als een persoon die
je slaat, als iemand dit zachtjes doet zal je niets zeggen, als dit een
stuk harder is zal je 'auwch' roepen. De kracht die het nodig om je auwch te
laten roepen is de drempelwaarde. Van binnen voelde dat dit pijn deed
naar mate je harder werd geslagen ging je meer pijn voelen. Dit kan je
het beste vatten in een lineaire functie. Vanwege het feit dat een NN
een continue functie is ligt het voor de hand om een logaritmische
functie te krijgen, waarbij de activatie functie de vorm krijgt van
formule~\ref{eq:perceptron}. Dit verklaart tevens waarom de invoer en
uitvoer tussen 0 en 1 moeten liggen, gezien dit ook het uitvoer bereik
is.

\begin{equation}
uit = \frac{1}{1 + e^{in}}
\label{eq:perceptron}
\end{equation}

De $in$ in formule~\ref{eq:perceptron} is een gewogen invoer van alle
$inkomende takken * het gewicht van een tak$. De drempel waarde is
echter een vervelend feit, welke makkelijker op te lossen is met een
zogenoemde \emph{bias} knoop, de waarde op deze knoop is altijd $-1$,
waardoor deze samen met het gewicht was tussen deze bias knoop en de
knoop hangt zorgt voor de drempelwaarde die origineel gebruikt was nu
de drempelwaarde $0$ gebruikt kan worden.


De gewichten zijn het `magische' van het NN, deze gewichten kunnen
namelijk getraind worden waardoor de uitvoer van het neurale netwerk kan
veranderen. Deze training word \emph{backpropagation} genoemd en heeft
een correlatie met de fout in de uitvoer, het huidige gewicht en de
leer-snelheid en de invoer. Om deze fout in een koop te bepalen moet er
gekeken worden naar de fout in de uitvoer en het gewicht naar tak van
die knoop, zie formule~\ref{eq:gewicht}. Waarbij $\triangle_{uit}$
gelijk is aan $\triangle_{j} = g'(in_j)\sum_i W_{j,i}\triangle{i}$
Waarbij $i$ all opvolgende knopen van $j$ zijn.

\begin{equation}
W_{in,uit} = \alpha * a_{in} * \triangle_{uit}
\label{eq:gewicht}
\end{equation}

De fouten worden dus omgekeerd berekend, eerst de fouten van de uitvoer
laag, dan de verborgen lagen ervoor en als die zijn die van de invoer
laag.

\section{Aanpak}
Er is gekozen gebruik te maken voorbeeld implementatie raamwerk gegeven
in de sheet \cite{web-sheet} tijdens het college kunstmatige
intelligentie welke een pseudo beschrijving geeft voor het programmeren
van een neuraal netwerk.

\begin{verbatim}
herhaal
    voor elke E in trainings set doe
        voorzie de invoer knopen
        bereken de waardes in de perceptronen en uitvoer-knopen
        bereken de delta fouten van de knopen en perceptronen
        pas de takken aan
totdat netwerk "geconvergeerd"
\end{verbatim}

Als eerste stap is simpele Perl code gebruikt om van de training en
validatie sets een in- en uitvoer data voor het NN te schrijven waarbij
alle waarden tussen 0 en 1 liggen. Perl code is een stuk flexibeler als
het gaat om tekst verwerking dan C code.

Om ook eens met een kritische noot naar de invoer te kijken en de
daadwerkelijke intelligentie van een NN, zal er extra knopen toegevoegd
worden om te kijken hoe deze presteren. Voor de poker set zijn dit een
paar specifieke combinaties namelijk de setjes -doubles, triples, four-
en de aantallen kaarten van elke soort kleur.

Nadat het netwerk geschreven is kan deze getest worden met een het leren
van de zogenoemde XOR functie. Deze functie is niet lineair te scheiden,
maar is met een NN van 2 invoer, 3 verborgen, 1 uitvoer perfect te
berekenen/leren.

\section{Implementatie}

Het NN is geschreven in C, hevig hangend op globale array waar de data
in zit en losse functies om de programma flow duidelijker te maken. De
pre-parse is geschreven in Perl en Bourne shell code.

\section{Experimenten}
Alle testen zijn uitgevoerd met een computer, waarbij gcc 4.01 als
compiler aanwezig was en Perl 5.8.8 als parser . Bij wijziging van de
input knopen of uitvoer knopen, is de pre-parse aangeroepen en de code
opnieuw gecompileerd met de nieuwe waardes.

Tijdens alle simulaties het de trainingsset een grootte van 25000. De
eind validatie set -welke de eind kwaliteit van het NN bepaald- 1
miljoen. En de tussentijdse kwaliteit set heeft een grootte van 1000,
welke na elke 100 training invoeren draaien.


Tijdens de leersnelheid experiment is gebruik gemaakt van het de
standaard poker set, met 10 invoeren, 10 uitvoeren en 10 verborgen
perceptronen. De resultaten zijn te zien in figuur~\ref{fig:leersnelheid}.
De verborgen perceptronen test is gedaan om dezelfde data set, hierbij is de
leer-snelheid 0.5 gekozen, deze resultaten staan in figuur~\ref{fig:verborgen}.

\begin{center}
\begin{figure}
\includegraphics[width=0.75\textwidth]{test-learn}
\caption{NN training verloop bij variabele leersnelheden}
\label{fig:leersnelheid}
\end{figure}
\end{center}

\begin{center}
\begin{figure}
\includegraphics[width=0.75\textwidth]{test-perceptrons}
\caption{NN training verloop bij variabele verborgen invoer laag grootte}
\label{fig:verborgen}
\end{figure}
\end{center}

Tijdens de invoer variatie is gekozen voor vijf verschillende
combinaties, de randvoorwaarden zijn 10 uitvoer knopen, aantal verborgen
knopen 20, leersnelheid 0.5 De standaard set hierna afgekort met
\emph{STD} (1). STD met kleur tellingen (2), STD met paar tellingen (3),
STD met kleur en paar tellingen (4), de paar tellingen + kleur tellingen
(5) . Resultaten staan in tabel~\ref{tab:invoer-variatie}.

\begin{center}
\begin{table}
\caption{Prestaties NN bij verschillende invoer data types}
\begin{tabular}{l|r|r}
Invoer variatie & Maximale kwaliteit in \% & Voorbeelden nodig \\
\hline 
1 & 49.92 & 400 \\
2 & 49.82 & 600 \\
3 & 92.26 & 1800 \\
4 & 92.26 & 6800 \\
5 & 92.26 & 600 \\
\end{tabular}
\label{tab:invoer-variatie}
\end{table}
\end{center}


%%Resultaten

\section{Conclusie}
Er is gekeken naar verschillende aspecten van het neurale netwerk.
Heeft toevoegen van nieuwe knopen met extra informatie invloed
op de uitvoer?  Heeft de leer-snelheid een positief effect op het NN?
Heeft het aantal verborgen perceptronen invloed op het netwerk?  Dit
alle gecombineerd tot het originele probleem: Is het mogelijk goed
poker-handen te voorspellen aan te hand van een 1-laags NN.

Het vari\"eren van leer-snelheid levert geen beter kwaliteit NN
op, als de leer-snelheid echter tussen 0 en 1 ligt zal het verloop minder
grillig zijn en zal het NN niet `te ver' doorschieten in een bepaalde
richting.

Het vari\"eren van het aantal verborgen knopen levert een maximum op als het
aantal verborgen knopen groter of gelijk is aan het aantal invoer
knopen. In het kader van de efficient is het aan te raden, deze rond de
waarde van de invoer knopen te houden om zo het aantal berekeningen dat
uitgevoerd moet worden zo minimaal mogelijk te houden.

Het grillige verloop van de grafiek in figuur~\ref{fig:leersnelheid} als
ook in figuur~\ref{fig:verborgen} is een gedag wat niet verklaard kan
worden. Verder onderzoek met bijvoorbeeld een andere data-set of de data
in een andere volgorde aan te bieden zou hier misschien uitsluitsel voor
kunnen bieden.

Het vari\"eren van de invoer heeft groot effect op te effectiviteit van
het netwerk. Bij het kiezen van de juiste data verdubbeld het netwerk
zijn effectiviteit. Dit kan verklaard worden doordat op het moment de
paren van te voren bepaald worden deze intelligentie niet meer door het
systeem ontdekt hoeft te worden. Het probleem wordt dus eigenlijk
versimpeld. Wel is het noodzakelijk relevante versimpelingen te maken.
Het tellen van het aantal kaarten van een bepaalde kleur heeft duidelijk
geen enkel effect in het netwerk, wat logisch is als we dichter naar de
poker kaarten gaan kijken. Hiervoor is het enkel interessant om te weten
of er 5 dezelfde kleuren in zitten of niet. Elke andere tussenvorm
levert geen extra informatie op.

Voor een vervolg verslag zou gekeken kunnen worden of een meer laags
NN een beter resultaat boekt bij het ontdekken van de poker kaarten.
Verder zouden er ook 'debug' sets ontwikkeld kunnen worden waarbij een
willekeurig NN netwerk getest kan worden op juiste werking, gegeven alle
randvoorwaarden. Deze optie wordt momenteel enkel voor een XOR voorbeeld
gegeven welke enkel maar een validatie set is van een zeer beperkt
probleem. Het is namelijk niet aan te tonen of het netwerk fout
geimplementeerd is.

\begin{thebibliography}{10}

\bibitem{opdracht}
W.A.~Kosters, Kunstmatige intelligentie Programmeer-opgave 3 van 2008
-- Neurale netwerken, \url{http://www.liacs.nl/~kosters/AI/nn08.html}

\bibitem{web-sheet}
W.A.~Kosters, Kunstmatige intelligentie College neurale netwerken 2008,
\url{http://www.liacs.nl/~kosters/AI/neuraal.pdf}

\bibitem{collegeboek}
S.J. Russell en P. Norvig, Artificial Intelligence, A Modern Approach,
Second ediion, Prentice Hall, 2003.

\bibitem{website}
Asuncion, A. \& Newman, D.J. (2007). UCI Machine Learning Repository
\url{http://www.ics.uci.edu/~mlearn/MLRepository.html}. Irvine, CA:
University of California, School of Information and Computer Science.

\bibitem{website-poker}
Robert Cattral (cattral@gmail.com) and Franz Oppacher (oppacher@scs.carleton.ca)
Carleton University, Department of Computer Science, Intelligent Systems Research Unit
\url{http://archive.ics.uci.edu/ml/datasets/Poker+Hand}

\end{thebibliography}
\newpage
\advance\textwidth by 8cm
\advance\oddsidemargin by -3cm
\advance\evensidemargin by -3cm
\advance\topmargin by -2cm
\advance\textheight by 4cm
\advance\footskip by -4cm
\marginparwidth 0cm
\twocolumn
\section*{Appendix}
De NN code en pre-parse.pl code  zagen er als volgt uit:
\newline
\tiny
%preformatted with `source-highlight -n -f latex bridge.cc`
\input{nn.c}
\input{data/pre-parse.pl}
\onecolumn

\end{document}