Introduktion
Detta är det första inlägget i en serie som utforskar implementationer av artificiella neurala nätverk (ANN). Syftet med artikeln är att hjälpa läsaren att få en uppfattning om de grundläggande begreppen innan han eller hon går vidare till de algoritmiska implementationer som kommer att följa.

Ingen förkunskaper förutsätts, även om inte all terminologi förklaras i artikeln för att vara kortfattad. I stället ges hyperlänkar till Wikipedia och andra källor där ytterligare läsning kan behövas.

Detta är ett stort ämne. ANNs har en mängd olika tillämpningar och kan användas för övervakad, oövervakad, halvövervakad och förstärkningsinlärning. Detta är innan man kommer in på problemspecifika arkitekturer inom dessa kategorier. Men vi måste börja någonstans, så för att begränsa räckvidden börjar vi med tillämpningen av ANNs på ett enkelt problem.

The XOr Problem
The XOr, eller ”exclusive or”, problem är ett klassiskt problem inom ANN-forskningen. Det är problemet med att använda ett neuralt nätverk för att förutsäga utgångarna för XOr-logiska grindar givet två binära ingångar. En XOr-funktion ska ge ett sant värde om de två ingångarna inte är lika och ett falskt värde om de är lika. Alla möjliga ingångar och förutsagda utgångar visas i figur 1.

XOr är ett klassificeringsproblem och ett problem för vilket de förväntade utgångarna är kända i förväg. Det är därför lämpligt att använda en övervakad inlärningsmetod.

På ytan verkar XOr vara ett mycket enkelt problem, men Minksy och Papert (1969) visade att detta var ett stort problem för neurala nätverksarkitekturer från 1960-talet, så kallade perceptroner.

Perceptroner
Som alla ANN:er består perceptronen av ett nätverk av enheter, som är analoga med biologiska neuroner. En enhet kan ta emot inmatning från andra enheter. När den gör det tar den summan av alla mottagna värden och bestämmer om den ska vidarebefordra en signal till andra enheter som den är ansluten till. Detta kallas aktivering. Aktiveringsfunktionen använder ett eller annat sätt att reducera summan av de ingående värdena till 1 eller 0 (eller ett värde som ligger mycket nära 1 eller 0) för att representera aktivering eller avsaknad av aktivering. En annan form av enhet, en så kallad bias-enhet, aktiveras alltid och skickar vanligtvis en hårt kodad 1 till alla enheter som den är ansluten till.

Perceptroner består av ett enda lager av ingångsenheter – inklusive en bias-enhet – och en enda utgångsenhet (se figur 2). Här visas en bias-enhet med en streckad cirkel, medan andra enheter visas som blå cirklar. Det finns två icke-biasade ingångsenheter som representerar de två binära ingångsvärdena för XOr. Det går att inkludera vilket antal ingångsenheter som helst.

Perceptronen är en typ av feed-forward-nätverk, vilket innebär att processen för att generera ett utdata – så kallad forward propagation – flödar i en riktning från ingångsskiktet till utgångsskiktet. Det finns inga förbindelser mellan enheterna i ingångslagret. Istället är alla enheter i inmatningsskiktet anslutna direkt till utdataenheten.

En förenklad förklaring av processen för framåtriktad propagation är att inmatningsvärdena X1 och X2, tillsammans med förskjutningsvärdet 1, multipliceras med sina respektive vikter W0..W2 och analyseras till utdataenheten. Utgångsenheten tar summan av dessa värden och använder en aktiveringsfunktion – vanligtvis Heavside-stegsfunktionen – för att omvandla det resulterande värdet till 0 eller 1 och därmed klassificera ingångsvärdena som 0 eller 1.

Det är inställningen av viktvariablerna som ger nätverksförfattaren kontroll över processen för att omvandla ingångsvärden till ett utgångsvärde. Det är vikterna som avgör var klassificeringslinjen, den linje som skiljer datapunkterna åt i klassificeringsgrupper, dras. Om alla datapunkter på ena sidan av en klassificeringslinje tilldelas klassen 0, klassificeras alla andra som 1.

En begränsning av denna arkitektur är att den endast kan separera datapunkter med en enda linje. Detta är olyckligt eftersom XOr-ingångarna inte är linjärt separerbara. Detta är särskilt synligt om man plottar XOr-ingångsvärdena i ett diagram. Som visas i figur 3 finns det inget sätt att separera förutsägelserna 1 och 0 med en enda klassificeringslinje.

Multilayer Perceptrons
Lösningen på det här problemet är att expandera bortom arkitekturen med ett enda lager genom att lägga till ytterligare ett lager med enheter som inte har någon direkt tillgång till omvärlden, det så kallade dolda lagret. Denna typ av arkitektur – som visas i figur 4 – är ett annat feed-forward-nätverk som kallas multilayer perceptron (MLP).

Det är värt att notera att en MLP kan ha ett obegränsat antal enheter i sina inmatnings-, dolda och utmatningslager. Det kan också finnas ett valfritt antal dolda lager. Den arkitektur som används här är utformad specifikt för XOr-problemet.

Som i den klassiska perceptronen börjar framåtpropagering med att ingångsvärdena och bias-enheten från ingångslagret multipliceras med sina respektive vikter, men i det här fallet finns det dock en vikt för varje kombination av ingång (inklusive ingångslagrets bias-enhet) och dold enhet (exklusive det dolda lagrets bias-enhet). Produkterna av värdena i inmatningsskiktet och deras respektive vikter analyseras som indata till de icke-biaserade enheterna i det dolda lagret. Varje dold enhet utan bias använder en aktiveringsfunktion – vanligtvis den klassiska sigmoidfunktionen när det gäller XOr-problemet – för att pressa ner summan av deras ingångsvärden till ett värde som ligger mellan 0 och 1 (vanligtvis ett värde som ligger mycket nära antingen 0 eller 1). Utgångarna från varje enhet i det dolda lagret, inklusive förskjutningsenheten, multipliceras sedan med ytterligare en uppsättning vikter och skickas till en utgångsenhet. Utgångsenheten analyserar också summan av sina ingångsvärden genom en aktiveringsfunktion – även här är sigmoidfunktionen lämplig – för att återge ett utgångsvärde som ligger mellan 0 och 1. Detta är det förutspådda utfallet.

Denna arkitektur är visserligen mer komplex än det klassiska perceptronnätverkets, men den kan åstadkomma en icke-linjär separation. Med rätt uppsättning viktvärden kan den alltså ge den nödvändiga separationen för att korrekt klassificera XOr-ingångarna.

Backpropagation
Elefanten i rummet är förstås hur man skulle kunna komma fram till en uppsättning viktvärden som säkerställer att nätverket producerar den förväntade utgången. Att manuellt försöka hitta en acceptabel uppsättning vikter för ett MLP-nätverk skulle i praktiken vara en otroligt mödosam uppgift. Det är faktiskt NP-komplett (Blum och Rivest, 1992). Det är dock lyckligtvis möjligt att lära sig en bra uppsättning viktvärden automatiskt genom en process som kallas backpropagation. Detta visades först fungera bra för XOr-problemet av Rumelhart et al. (1985).

Backpropagationsalgoritmen börjar med att jämföra det faktiska värdet som produceras av den framåtriktade propagationsprocessen med det förväntade värdet och rör sig sedan bakåt genom nätverket, genom att justera var och en av vikterna något i en riktning som minskar storleken på felet med en liten grad. Både framåt- och bakåtpropagering körs om tusentals gånger för varje kombination av indata tills nätverket kan förutsäga det förväntade utfallet av de möjliga inmatningarna med hjälp av framåtpropagering.

För xOr-problemet är 100 % av de möjliga dataexemplen tillgängliga att använda i träningsprocessen. Vi kan därför förvänta oss att det tränade nätverket är 100 % korrekt i sina förutsägelser och det finns ingen anledning att vara orolig för frågor som bias och varians i den resulterande modellen.

Slutsats
I det här inlägget undersöktes det klassiska ANN XOr-problemet. Själva problemet beskrevs i detalj, tillsammans med det faktum att indata för XOr inte är linjärt separerbara i sina korrekta klassificeringskategorier. En icke-linjär lösning – som involverar en MLP-arkitektur – undersöktes på en hög nivå, tillsammans med algoritmen för forward propagation som används för att generera ett utgångsvärde från nätverket och backpropagation-algoritmen, som används för att träna nätverket.

Nästa inlägg i denna serie kommer att innehålla en Java-implementering av MLP-arkitekturen som beskrivs här, inklusive alla komponenter som är nödvändiga för att träna nätverket så att det kan fungera som en XOr-logisk grind.

Blum, A. Rivest, R. L. (1992). Träning av ett neuralt nätverk med tre noder är NP-komplett. Neural Networks, 5(1), 117-127.