Högskolan i Skövde

Machine learning algorithms are very successful in solving classification and regression problems, however the immense amount of data created by digitalization slows down the training and predicting processes, if solvable at all. High-Performance Computing(HPC) and particularly parallel computing are promising tools for improving the performance of machine learning algorithms in terms of time. Support Vector Machines(SVM) is one of the most popular supervised machine learning techniques that enjoy the advancement of HPC to overcome the problems regarding big data, however, efficient parallel implementations of SVM is a complex endeavour. While there are many parallel techniques to facilitate the performance of SVM, there is no clear roadmap for every application scenario. This thesis is based on a collection of publications. It addresses the problems regarding parallel implementations of SVM through four research questions, all of which are answered through three research articles. In the first research question, the thesis investigates important factors such as parallel algorithms, HPC tools, and heuristics on the efficiency of parallel SVM implementation. This leads to identifying the state of the art parallel implementations of SVMs, their pros and cons, and suggests possible avenues for future research. It is up to the user to create a balance between the computation time and the classification accuracy. In the second research question, the thesis explores the impact of changes in problem size, and the value of corresponding SVM parameters that lead to significant performance. This leads to addressing the impact of the problem size on the optimal choice of important parameters. Besides, the thesis shows the existence of a threshold between the number of cores and the training time. In the third research question, the thesis investigates the impact of the network topology on the performance of a network-based SVM. This leads to three key contributions. The first contribution is to show how much the expansion property of the network impact the convergence. The next is to show which network topology is preferable to efficiently use the computing powers. Third is to supply an implementation making the theoretical advances practically available. The results show that graphs with large spectral gaps and higher degrees exhibit accelerated convergence. In the last research question, the thesis combines all contributions in the articles and offers recommendations towards implementing an efficient framework for SVMs regarding large-scale problems.

Machine Learning (ML) has achieved remarkable success in solving classification, regression, and related problems over the past decade. In particular the exponential growth of digital data, makes using ML inevitable and necessary to exploit the wealth of information hidden inside the data. However, this posits new challenges for traditional serial learning methods concerning scalability as the learning process becomes slow, if it is feasible at all. Distributed and parallel learning are natural approaches for improving the performance of ML algorithms in terms of running time. Support Vector Machines (SVM) are successful and popular supervised machine learning models that enjoy the availability of parallel and distributed computational approaches to tackle the challenges arising from big data. However, efficient parallel and distributed implementation of SVMs is a complex endeavour. To make matters worse, distributed learning of SVMs may impose privacy concerns, particularly with models built from data distributed across multiple nodes where due to confidentiality of data, intellectual property interest, or other reasons, the information cannot be easily shared. Despite the large amounts of prior work, the problems regarding learning SVMs with respect to big data are not fully solved. Therefore in this dissertation, we try to shed light on efficient parallel SVM implementations and on how they can be further improved. This dissertation is based on a collection of publications. The research presented here addresses some problems in parallel and distributed computing of SVMs through four research questions. The key contribution is to provide answers to these research questions through five research articles. For the first research question, we explore available parallel approaches for learning SVMs for large-scale problems. We investigate important factors such as algorithmic approaches, HPC tools, strategies and heuristics used for effective parallel SVM implementations. All of these helped identifying the state-of-the-art parallel SVMs, their pros and cons, and provide suggestions for potential avenues for future studies. We conclude that it is the responsibility of the user to make judicious choices to balance the trade-offs. To address the second research question, we explore the impact of changes in the problem size and the important SVM parameters that lead to significant performance improvements. It turns out that the problem size has impact on the optimal choice of the important SVM parameters. In addition, we show the existence of a threshold on the number of cores after which the training time does not improve. The third research question investigates the effect of network topology on the performance of network-based distributed SVMs in terms of convergence. The three key contributions are to 1) show the effect of the expansion property and the connectivity of the underlying communication network on the convergence of the algorithm, 2) present a preferable network topology, and 3) supply an implementation that makes the theoretical advances practically available. The results I suggest that the graphs with higher node degrees and larger spectral gaps, thus higher connectivity, exhibit accelerated convergence. The fourth research question investigates federated learning of SVMs in which the data privacy is protected under limited and private communication between agents. The key contribution is incorporating differential privacy during the learning procedure. The results show that the learning process 1) respects data privacy, 2) achieves accuracy comparable to the algorithm without considering privacy-preserving, and 3) yields tight empirical guarantees for privacy after convergence. Finally, we combine all the contributions in the dissertation and offer recommendations for implementing an efficient privacy-preserving framework for parallel computing of SVMs for large-scale problems.

Machine Learning (ML) har haft en anmärkningsvärd framgång bland annat när det gäller att lösa klassificerings- och regressionsproblem under det senaste decenniet. Särskilt när det gäller den exponentiella tillväxten av digital data, är det oundvikligt och nödvändigt att använda ML för att utnyttja den mängd information som är gömd i datan. Detta innebär dock nya utmaningar för traditionella seriella inlärningsmetoder när det gäller skalbarhet eftersom inlärningsprocessen blir långsam, om alls möjligt. Distribuerat och parallellt lärande är lovande metoder för att för[1]bättra prestandan hos ML-algoritmer när det gäller körtid. Support Vector Machines (SVM) är framgångsrika och populära modeller för övervakad maskininlärning som åtnjuter tillgången till parallell och distribuerad datoranvändning för att hantera de utmaningar som uppstår från big data. Hur som helst är effektiv parallell och distribuerad implementering av SVM ett komplext problem. För att göra saken värre kan distribuerad inlärning av SVM skapa integritetsproblem, särskilt med modeller byggda från data som distribueras över flera noder där informationen inte enkelt kan delas på grund av datakonfidentialitet, immateriella intressen eller andra skäl. Trots de stora mängderna tidigare arbete är problemen med att lära SVM:er med avseende på big data inte helt lösta, därför försöker vi i denna avhandling belysa effektiva parallella SVM-implementeringar och hur de kan förbättras ytterligare. Denna avhandling bygger på en samling publikationer. Forskningen som presenteras i denna avhandling tar upp några problem parallellt med och distribuerad beräkning av SVM:er genom fem forskningsfrågor. Det viktigaste bidraget för denna avhandling är att ge svar på avhandlingarnas forskningsfrågor genom fem forskningsartiklar. För den första forskningsfrågan utforskar vi tillgängliga parallella tillvägagångssätt för att lära SVM:er för storskaliga problem. Vi undersöker viktiga faktorer som algoritmiska tillvägagångssätt, HPC-verktyg, strategier och heuristik som används för effektiva parallella SVM-implementeringar. Alla dessa hjälpte till att identifiera de senaste parallella SVM:erna, deras för- och nackdelar, och ge förslag på potentiella vägar för framtida studier. Vi drar sen slutsatsen att det är användarens ansvar att göra kloka val för att balansera avvägningarna. För att ta itu med den andra forskningsfrågan utforskar vi effekterna av förändringar i problemstorleken och de viktiga SVM-parametrar som leder till betydande prestanda. Det visar sig att problemets storlek har inverkan på det optimala valet av viktiga SVM-parametrar. Dessutom visar vi att det finns en tröskel mellan träningstiden och antalet kärnor. Den tredje forskningsfrågan undersöker effekten av nätverkstopologi på prestandan hos nätverksbaserade distribuerade SVM när det gäller konvergens. De tre nyckelbidragen är att 1) visa effekten av expansionsegenskapen och det underliggande nätverkets uppkoppling på algoritmens konvergens, 2) presentera en föredragen nätverkstopologi och 3) tillhandahålla en implementering som gör de teoretiska framstegen praktiskt tillgängliga. Resultaten tyder på att graferna med högre grader och större spektralgap, alltså högre anslutningsmöjligheter, uppvisar accelererad konvergens. Den fjärde forskningsfrågan undersöker federerad inlärning av SVM:er där dataintegriteten skyddas under begränsad och privat kommunikation mellan agenter. Det viktigaste bidraget är att införliva differentierad integritet under inlärningsproceduren. Resultaten visar att inlärningsprocessen 1) respekterar dataintegritet, 2) uppnår en noggrannhet jämförbar med den icke-privata algoritmen och 3) ger snäva empiriska garantier för integritet efter konvergens. Slutligen löser man den sista forskningsfrågan genom att kombinera alla bidrag i avhandlingen och ger rekommendationer för att implementera ett effektivt ramverk för parallell beräkning av SVM för storskaliga problem.