Multitrådad maskinlärande med Java

På kursen T2732 Avancerad Java programmering går vi bland annat igenom Executor ramverket som introducerades med Java 1.5. Ramverket tar hand om trådhanteringen och låter oss fokusera på de uppgifter som skall utföras i bakgrunden.

En användning för multipla trådar som blir allt vanligare är att utnyttja flera processoror och kärnor för beräkningsintensiva applikationer. Ett område som jag brinner för är AI och maskinlärande, där algoritmerna oftast är CPU-intensiva. Genom att köra på flera processorer parallellt så blir beräkningen klar snabbare.

I denna artikel får Ni känna lite på maskinlärande, med 2 implementationer av en kNN klassificerare, en enkeltrådad och en multitrådad. Under resan får vi även bekanta oss med Strategy och Template Method, två kraftfulla designmönster samt definiera och använda generiska typer, ämnen som också behandlas på kursen. Artikeln visar en hel del javakod men bara de väsentligaste delarna. Om du vill se hela koden kan du ladda ner projektet här.

Maskinlärande

En vanlig uppgift inom maskinlärande är klassifikation. Utifrån ett antal instanser, eller exempel, skapar man en klassificerare som kan användas för att kategorisera nya instanser. Kreditbedömning, medicinsk diagnos och textanalys är bara några exempel. Neurala nätverk, Naive Bayes, SVM, kNN är några olika typer av klassificerare.

Exempeldata

Vi tar kreditbedömning vid sms lån som exempel. I tabellen visas två tidigare ansökningar och dess utfall. Bedömningen kanske har skett manuellt tidigare men med ett stort antal exempel så kan vi bygga en beslutsmodell som avgör nya ansökningar.

Kön Årsinkomst Lånebelopp Operatör Veckodag Timme Beviljat
man 190.000 800 telenor lördag 3 nej
kvinna 240.000 400 telia tisdag 17 ja

Många ramverk för maskinlärande representerar alla attribut som en array av double. Vi håller oss till  objektorienterad representation och definierar därför en klass för en låneansökan:

kNN – Nearest Neighbor

kNN är en algoritm som är lätt att förstå och lätt att implementera. Idén bygger på att man jämför instansen som skall klassificeras med ett stort antal tidigare instanser och tilldelar samma klass som den (k = 1) eller de (k > 1) som är mest lika. Till detta behöver vi en funktion som kan beräkna hur lika två instanser är. Denna funktion är specifik för varje typ av instans och definieras genom att implementera följande interface:

Här är en implementation som jämför två låneansökningar och returnerar ett mått på hur olika de är. I normala fall får man arbeta mycket med denna för att trimma in kvaliteten på klassificeringen.

Här är själva klassificeringsmetoden för kNN, observera att loopen som beräknar alla avstånd går på en enda tråd.

Nästa steg är att göra beräkningen av alla avstånd på flera processorer. Ett sätt att implementera det är att bryta ut beräkningen till en egen metod (calculateDistances) som sedan överrids i en subklass. Om vi samtidigt lyfter upp den utbrutna metoden samt classify-implementation i en abstrakt basklass, så har vi ett exempel på designmönstret Template Method. Nedan följer de intressanta metoderna i ParallelNearestNeighborClassifier:
Notera att vi skapar ett antal instanser av Callable som vi lämnar över till en ExecutorService som fördelar uppgifterna på trådarna i trådpoolen.

Och slutligen ett test-program som jämför båda algoritmerna med olika mängder data.

Resultat

Av tabellen framgår att den multitrådade versionen går lite mer än dubbelt så fort utom för väldigt små datamängder. Min maskin har 8 kärnor och jag körde applikationen i en VMware instans med 4 kärnor tilldelade. I teorin skall det gå 4 gånger fortare men jag kom aldrig riktigt upp i fullt tryck (100% CPU) på alla 4 kärnor, vilket kan bero på den virtuella miljön. Som med alla typer av optimering är det bra att mäta och göra val utifrån faktisk prestanda och inte teoretiskt resonemang.

Antal instanser En tråd (ms) Flera trådar (ms)
5000 102 73
10000 91 85
50000 376 251
100000 781 385
1000000 7681 3353
5000000 39376 16893
10000000 83029 34699

PS. AI och maskinlärande är inget som tas upp på kursen, men om det finns intresse så kan vi ordna en workshop. Kontakta din lokala säljare!