I løpet av det første semesteret på Honours-programmet har vi blitt presentert for mange perspektiver på kunstig intelligens (KI), men vi har ikke fått vite mye om hvordan vi går frem for å lage selv. Jeg tenkte det ville være interessant å anvende det jeg har lært i løpet av mitt første år på Universitet i Oslo til å lage et enkelt eksempel på KI. Jeg valgte meg et nevralt nettverk, da jeg opplever at det er denne formen for KI som er mest aktuell.

I denne teksten vil jeg ta for meg teorien bak et nevralt nettverk som kan trenes opp med veiledet læring til klassifiseringsproblemer. Her vil jeg gjøre rede for både arkitektur og treningsprosessen. Deretter vil jeg presentere mitt eget nevrale nettverk som jeg har trent opp til å skille engelsk fra norsk.

Teori

Aller først ønsker jeg å definere veiledet læring. Veiledet læring er bruk av data som er klassifisert på forhånd til å lære systemet at det finnes en korrelasjon mellom inngangsverdiene og korrekt utgangsverdi (https://snl.no/maskinl%C3%A6ring). For at det skal skje, er vi nødt til å kunne justere nettverket vårt avhengig av tilbakemeldingen den får i treningen. Til dette kommer vi til å bruke en gradient som vi finner gjennom numerisk derivasjon.

Arkitektur

Før vi får trene nettverket vårt til noe som helst er vi nødt til å bygge det opp. Nettverket skal bygges opp av nevroner som minste komponenter. En samling av disse utgjør et lag, som igjen settes sammen til det nevrale nettverket. Vi bruker Python til å bygge opp arkitekturen, og i prosjektet forøvrig. Vi trenger også å importere noen bibloteker. I første omgang trenger vi pakkene numpy og random.

import numpy as np
import random

 

Over er en illustrasjon av hvordan nettet skal bygges opp. Om vi ser på hvert av lagene som vektorfelt, fungerer nettverket ved at funksjonsverdien fra et lag sendes inn i neste lag. Hvert av koordinatene i funksjonsverdien er funksjonsverdien til nevronene, som derfor er skalarfelt.

$$\vec{L_{j}}\left( \vec{L_{j-1}}\right) = (n_1\left(\vec{L_{j-1}}\right), n_2\left(\vec{L_{j-1}}\right), ..., n_k\left(\vec{L_{j-1}}\right))$$

Over er funskjonen $L_i$ for det $i$-te laget. Det tar inn vektoren som er det forrige laget, og har hver av sine $k$ nevroner som koordinater.

Så kan vi ta for oss nevronene. Nevronene holder det vi kaller vektene $\vec{m}$ og biasene $b$. Som man kan lese av notasjonen er vektene en vektor, mens bias er en skalar. Det vi ønsker er summen av produktene når hvert av tallene i forrige lag ganges med en egen vekt, pluss en bias. Det er dette vi får om vi tar skalarproduktet av $\vec{m}$ og $\vec{L_{j-1}}$ og legger til $b$. Antall vekter i $\vec{m}$ må derfor samstemme med antall nevroner i forrige lag. I tillegg ønsker vi at verdien skal være mellom 0 og 1, så vi bruker sigmoidfunksjonen $\sigma$ for å oppnå dette. Den står under.

def sigmoid(x):
    return 1/(1+np.exp(-x))

$$n_i \left(\vec{L_{j-1}}\right) = \sigma \left(\vec{m} \cdot \vec{L_{j-1}} + b \right) $$

Over er skalarfelter til den $i$-te nevronen i det $j$-te laget. Python-koden under konstruerer nevroner og lag akkurat slik vi har beskrevet dem til nå. Deretter følger en kostfunksjon før selve det nevrale nettverket konstrueres. Initialiseringen og kallet er blitt gjort rede for, mens metodene for trening og tildeling av vekter beskrives senere. Da vil også kostfunksjonen forklares.

class Neuron:
    def __init__(self, m, b):
        self.weights = m
        self.bias = b

    def __call__(self, x, delta_weights, delta_bias):
        return sigmoid(np.sum((self.weights + delta_weights) * x) + self.bias + delta_bias)

class Layer:
    def __init__(self, m, b, width, prev_width):
        self.axons_per_neuron = prev_width
        self.neurons = [Neuron(m[prev_width * i: prev_width * (i + 1)], b[i]) for i in range(width)]

    def __call__(self, x, delta_weights, delta_bias):
        delta_weights_split = np.split(delta_weights, len(delta_weights)/self.axons_per_neuron)
        return np.array([neuron(x, delta_weights_split[i], delta_bias[i]) for i, neuron in enumerate(self.neurons)])

def cost_func(y, yHat): # kilde: https://ml-cheatsheet.readthedocs.io/en/latest/loss_functions.html
    if y == 1:
        return -np.log(yHat)
    else:
        return -np.log(1 - yHat)

def basis_array(index, size):
    arr = np.zeros(size)
    arr[index] = 1
    return arr

class NeuralNetwork:
    def __init__(self, layers, m, b):
        self.m = m
        self.b = b
        self.neurons_per_layer = layers
        self.bias_indexing = layers[1:].cumsum()
        self.weight_indexing = (layers[1:] * layers[: -1]).cumsum()
        bias_split = np.split(b, self.bias_indexing)
        weights_split = np.split(m, self.weight_indexing)
        self.layers = [Layer(weights_split[i], bias_split[i], layers[i + 1], layers[i]) for i in range(len(layers) - 1)]

    def __call__(self, x, delta_weights, delta_bias):
        iterate = x
        delta_weights_split = np.split(delta_weights, self.weight_indexing)
        delta_bias_split = np.split(delta_bias, self.bias_indexing)
        for i, layer in enumerate(self.layers):
            iterate = layer(iterate, delta_weights_split[i], delta_bias_split[i])
        return iterate

    def assign(self, m, b):
        self.m = m
        self.b = b
        bias_split_layer = np.split(b, self.bias_indexing)
        weights_split_layer = np.split(m, self.weight_indexing)
        for layer, weights, biases in zip(self.layers, weights_split_layer, bias_split_layer):
            for i, neuron in enumerate(layer.neurons):
                neuron.bias = biases[i]
                neuron.weights = weights[len(neuron.weights) * i: len(neuron.weights) * (i + 1)]

    def train(self, data_set, f, lr, print_and_stop):
        h = 1e-6
        done = False
        record = []
        while not done:
            label = random.randint(0, len(data_set) - 1)
            sample = random.choice(tuple(data_set[label]))
            m_dim = len(self.m)
            b_dim = len(self.b)
            x = f(sample)
            prediction = self.__call__(x, np.zeros(m_dim), np.zeros(b_dim))
            cost = sum(cost_func(int(i == label), out) for i, out in enumerate(prediction))
            delta_weights = [basis_array(i, m_dim) * h for i in range(m_dim)]
            delta_bias = [basis_array(i, b_dim) * h for i in range(b_dim)]
            predictions_delta_m = np.array([self.__call__(x, delta_weights[i], np.zeros(b_dim)) for i in range(m_dim)])
            predictions_delta_b = np.array([self.__call__(x, np.zeros(m_dim), delta_bias[i]) for i in range(b_dim)])
            cost_delta_m = []
            for pred in predictions_delta_m:
                cost_delta_m += [sum(cost_func(int(i == label), out) for i, out in enumerate(pred))]
            cost_delta_b = []
            for pred in predictions_delta_b:
                cost_delta_b += [sum(cost_func(int(i == label), out) for i, out in enumerate(pred))]
            cost_delta_m = np.array(cost_delta_m)
            cost_delta_b = np.array(cost_delta_b)
            gradient_m = (cost_delta_m - cost)/h
            gradient_b = (cost_delta_b - cost)/h
            self.assign(self.m - gradient_m * lr, self.b - gradient_b * lr)
            record.append(label == np.argmax(prediction))
            done = print_and_stop(record)
            

Tren med gradient

Vi ønsker at nettet vårt skal klassifisere en input $\vec{x}$ basert på tallverdiene i det siste nevronlaget. Hver av nevronene her tilsvarer en klasse, og nevronverdien er i hvor stor grad nettet mener $\vec{x}$ passer i klassen. Vi kan kalle verdiene i det siste laget for nettets prediksjon $\vec{P}\left(\vec{x}\right)$. Merk at inputen $\vec{x}$ er på formen til funksjonsverdien av et nevralt lag, og tilsvarer inputlaget i illustrasjonen fra tidligere. Dette er verdien som brukes som argument for å regne ut $\vec{L_1}$. Dersom vi har et nevralt nettverk med $m$ lag i tillegg til inputtlaget får vi:

$$\vec{P}\left(\vec{x}\right) = \vec{L_m}\left(\vec{L_{m-1}}\left(...\vec{L_1}\left(\vec{x}\right)\right)\right) $$

Nå er utfordringen å få en prediksjon som stemmer. Altså vil vi at nettet skal kunne plassere $\vec{x}$ i klassen den faktisk tilhører. Hvilke tall vi får i det siste nevronlaget avhenger av vektene og biasene inne i nettet vårt. Vi kaller samlingen av alle biaser $\vec{B}$ og samlingen av alle vekter $\vec{M}$. For at nettet skal kunne gi gode prediksjoner vil vi ha vekter og biaser som fanger opp mønster og strukturer som er karakteristiske for klassene. Veiledet læring er hvordan vi går fra tilfeldig satte vekter og biaser, til noen som gir oss gode prediksjoner.

Ideen med veiledet læring er at vi har et datasett hvor innholdet er merket med klassen det tilhører, og dette settet skal brukes til å trene nettverket til å gi gode prediksjoner. Til det trenger vi først å kunne tallfeste hvor god en prediksjon er, og det er her kostfuksjonen kommer inn. Dersom $\vec{x}$ tilhører en klasse, ønsker vi at nevronverdien som svarer til den klassen skal være 1, mens alle andre nevroner i laget skal være 0. Kostfunksjonen $C$ gir en verdi for hvor godt dette stemmer, der lave tall er en presis prediksjon. Målet vårt må derfor være å finne bunnpunktet til $C$ som en funksjon av $\vec{B}$ og $\vec{M}$, hvor $\vec{x}$ er gitt.

Dette gjør vi ved å konstruere en gradient, som vi finner med numerisk derivasjon. Gradienten forteller oss i hvilken retning funksjonsverdien $C$ stiger raskest, og alt vi trenger å gjøre da er å flytte $\vec{M}$ og $\vec{B}$ i motsatt retning. Enklest er det om vi lager en gradient hver for $\vec{M}$ og $\vec{B}$, hvor vi holder den andre konstant. Vi bruker den enkleste formen for numerisk derivasjon, nemlig Newtons kvotient: $$f'(x) = \frac{f(x + h)-f(x)}{h}$$ Der $h$ er et lite tall. Siden vi jobber i flere dimensjoner blir det nyttig å introdusere enhetsvektoren $\vec{e_i}$ som har $1$ som det $i$-te koordinatet, og $0$ resten. På den måten blir det å legge til $\vec{e_i} \cdot h$ til $\vec{M}$ det samme som å forskyve den $i$-te koordinaten i $\vec{M}$ med $h$. Dermed har vi: $$\nabla_\vec{M} C(\vec{M}) = (\frac{\partial C}{\partial M_1}(\vec{M}), \frac{\partial C}{\partial M_2}(\vec{M}),..., \frac{\partial C}{\partial M_n}(\vec{M})) \approx (\frac{C(\vec{M} + \vec{e_1} \cdot h) - C(\vec{M})}{h}, \frac{C(\vec{M} + \vec{e_2} \cdot h)-C(\vec{M})}{h}, ... , \frac{C(\vec{M} + \vec{e_n} \cdot h) - C(\vec{M})}{h})$$

$$\nabla_\vec{B} C(\vec{B}) = (\frac{\partial C}{\partial B_1}(\vec{B}), \frac{\partial C}{\partial B_2}(\vec{B}),..., \frac{\partial C}{\partial B_m}(\vec{B})) \approx (\frac{C(\vec{B} + \vec{e_1} \cdot h - C(\vec{B}))}{h}, \frac{C(\vec{B} + \vec{e_2} \cdot h)- C(\vec{B})}{h}, ... , \frac{C(\vec{B} + \vec{e_m} \cdot h) - C(\vec{B})}{h})$$

Nå først får vi bruk for metoden til å tildele nye vekter. De nye vektene skal være $\vec{M} - \nabla_\vec{M} C(\vec{M}) \cdot l$ og $\vec{B} - \nabla_\vec{B} C(\vec{B}) \cdot l$. Her er $l$ læringsraten, som vil si hvor langt i den motsatte gradientretningen man vil gå per mutasjon. Den setter man gjerne et sted mellom $0.01$ og $1$, avhengig av hvor raskt og preist man vil at programmet skal lære.

Nå lærer det nevrale nettverket seg å klassifisere elementene i datasettet, og man har en kunstig intelligens.

Resultat

Nå som vi har arkitekturen og treningsprosessen på plass, kan vi gi nettverket et ekte klassifiseringsproblem. Ideen er at nettverket skal kunne ta imot en liste tall som forteller den relativ frekvens av hver enkelt bokstav i alfabetet for et ord. Dette er inngangsverdiene som nettverket skal bruke til å plassere ordet som enten engelsk eller norsk. Til dette trenger vi datasett, og vi benytter oss av ordlister som er ment til bruk for spillet Scrabble. Det engelske settet går under navnet TWL06, mens det norske settet er NSF-ordliste. Det er verdt å merke seg at selvom det norske settet er betydelig større (692 872 ord) enn det engelske (178 691 ord), har hvert sett like stor sjanse til å bli trukket fra hver gang. Vi gjør også en innsats for å kvitte oss med ord som inneholdes i begge sett, som reduserer settstørrelsene til henholdsvis 683 616 og 169 435 ord.

engtext = open("engelsk.txt", "r")
engset_gross = set(word.strip() for word in engtext)
engtext.close()
nortext = open("nsf2016.txt", "r", encoding="utf-8")
norset_gross = set(word.strip().upper() for word in nortext)
nortext.close()

engset = engset_gross.difference(norset_gross)
norset = norset_gross.difference(engset_gross)

print(f"Norsk sett: {len(norset)} ord, Engelsk sett: {len(engset)} ord")
dataset = [norset, engset]

Norsk sett: 683616 ord, Engelsk sett: 169435 ord

Før vi skal teste systemet vårt skriver vi en funksjon som skal sendes med i treningen. Den tar i mot liste over resultatet fra alle treningsforsøkene til systemet, og er den som printer ut informasjonen vi ser under treningen. Her forteller vi også programmet når det skal avslutte treningen, og plotter en graf som viser hele treningsforløpet. Til plottet bruker vi matplotlib.

Under denne funksjonen følger en funksjon som gjør om ordene i datasettet til inngangsverdier nettverket vårt forstår. Det vil si en array hvor hver koordinat forteller om den relative frekvensen til en bokstav i et ord. At den tar imot relativ frekvens i stedet for absolutt frekvens har med at nettverket ikke skal få vite lengden på ordet den evaluerte. Den avgjørelsen er tatt etter at tidligere versjoner ofte foretrakk engelsk alt for ofte dersom ordet var kort, og kan skyldes svakhet i datasettet.

import matplotlib.pyplot as plt


def to_train(record):
    cut_off = 5000
    if len(record) % 100 == 0:
        print("|", sum(record[-100:])/100, len(record), "|", end = " ")
    if len(record) == cut_off:
        intervals = list(range(0, cut_off + 1, 100))
        avg = [sum(record[left : right]) for left, right in zip(intervals[:-1], intervals[1:])]
        plt.plot(intervals[1:], avg, label = "Treffratio siste 100 forsøk")
        plt.legend()
        plt.show()
        return True
    return False

def inp(word):
    alf = "ABCDEFGHIJKLMNOPQRSTUVWXYZÆØÅ"
    arr = np.zeros(29)
    for i, letter in enumerate(word):
        index = alf.find(letter)
        arr[index] += 1
    return arr/len(word)

Nå er vi klare til å lage en instans av det nevrale nettverket vi har laget, for å så trene det på datasettet vårt. Vi starter med å initialisere vekter og biaser. Disse skal settes tilfeldig, og etter litt eksperimentering er en normalfordeling om 0 valgt til å gjøre dette.

Vi er låst til å konstruere inputlaget vårt med 29 nevroner, ettersom dette er antall bokstaver i det norske alfabetet. Deretter skal vi ha kun ett skjult lag med 10 nevroner. Grunnen til dette er at det er relativt ukomplisert klassifikasjon. Tanken er at ett skjult lag skal være nok til at nettverket fanger opp strukturene som potensielt kan dukke opp i informasjonen den er matet. Til slutt er det siste laget bundet til å være 2 nevroner, ettersom vi har to klasser nettverket kan velge mellom.

m = np.random.normal(0, 1, 29 * 10 + 10 * 2)
b = np.random.normal(0, 1, 10 + 2)
N = NeuralNetwork(np.array([29, 10, 2]), m, b)
N.train(dataset, inp, 0.1, to_train)

| 0.53 100 | | 0.46 200 | | 0.65 300 | | 0.51 400 | | 0.52 500 | | 0.53 600 | | 0.54 700 | | 0.55 800 | | 0.57 900 | | 0.56 1000 | | 0.61 1100 | | 0.61 1200 | | 0.63 1300 | | 0.53 1400 | | 0.66 1500 | | 0.65 1600 | | 0.68 1700 | | 0.59 1800 | | 0.7 1900 | | 0.67 2000 | | 0.68 2100 | | 0.69 2200 | | 0.7 2300 | | 0.69 2400 | | 0.73 2500 | | 0.64 2600 | | 0.75 2700 | | 0.7 2800 | | 0.77 2900 | | 0.73 3000 | | 0.72 3100 | | 0.72 3200 | | 0.75 3300 | | 0.76 3400 | | 0.81 3500 | | 0.8 3600 | | 0.67 3700 | | 0.79 3800 | | 0.77 3900 | | 0.75 4000 | | 0.77 4100 | | 0.82 4200 | | 0.77 4300 | | 0.68 4400 | | 0.66 4500 | | 0.72 4600 | | 0.8 4700 | | 0.81 4800 | | 0.77 4900 | | 0.75 5000 | 

Over er utskrift fra resultanene av treningen. Vi oppnår etter 5000 gjennomkjøringer en treffprosent på et sted mellom 75% og 80%, og kan enkelt lese progresjon av grafen.

Konklusjon

Vårt forsøk var på en ganske kort treningsperiode, og erfaring tilsier at man ofte kan nå enda bedre treffsikkerthet om man lar den trene utover de 5000 ordene vi ga den nå. Allikevel er dette betydelig gode resultater, og er mer enn nok til å kunne dokumentere at veiledet læring fungerer.

Det er en rekke ting som kunne gjort treffsikkerheten til dette systemet bedre, men i mange tilfeller er vi begrenset av datakraft. Dette eksperimentet er gjort på en svak personlig datamaskin, som nok setter en øvre grense for hvor gode resultater vi kan få. Spesielt kan man peke på at det i dette tilfelle nok ikke er en god ide å justere vekter og biaser etter hvert enkelt ord, ettersom enkelte ord slettes ikke er karakteristiske for språket det tilhører. Derfor får vi en stor negativ utvikling hver et slikt ord dukker opp. Dette kunne vi forbedret ved å regne ut en snittkostnad over flere ord, før vi justerer vekter og biaser. På den måten er vi sikrere på at vi går i riktig retning hver gang vi beveger noe.

I tillegg er det viktig å huske på at nettverket i vårt tilfelle ikke fikk noe informasjon om rekkefølgen på bokstavene. I praksis betyr det for eksempel at alle anagrammer er like for nettverket, og det er lett å tenke seg at dette senker teoretisk oppnålig treffprosent.

Alt i alt har dette vært et veldig morsomt prosjekt å få jobbe med, og jeg kommer til å bygge videre på dette nettverket. Jeg skulle veldig gjerne ha testet det på andre klassifikasjonsproblemer, men utfordringen ligger i tilgang til datasett. Etterhvert vil jeg gjerne prøve meg på andre former for maskinlæring også, og gjerne sette de opp mot dette prosjektet.