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!