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.

Veiledet l?ring

Teori

Arkitektur?

Tren med gradient?

Resultat?

Konklusjon?

Siste innlegg