عنوان

Parallel Machine Learning Using Concurrency Control

شماره

TL8h44r0v5

زبان متن نوشتاري يا گفتاري و مانند آن

انگلیسی

عنوان اصلي

Parallel Machine Learning Using Concurrency Control

نام عام مواد

[Thesis]

نام نخستين پديدآور

Pan, Xinghao

نام ساير پديدآوران

Jordan, Michael I

نام ناشر، پخش کننده و غيره

UC Berkeley

تاریخ نشرو بخش و غیره

2017

کسي که مدرک را اعطا کرده

UC Berkeley

امتياز متن

2017

متن يادداشت

Many machine learning algorithms iteratively process datapoints and transform global model parameters. It has become increasingly impractical to serially execute such iterative algorithms as processor speeds fail to catch up to the growth in dataset sizes.To address these problems, the machine learning community has turned to two parallelization strategies: bulk synchronous parallel (BSP), and coordination-free. BSP algorithms partition computational work among workers, with occasional synchronization at global barriers, but has only been applied to 'embarrassingly parallel' problems where work is trivially factorizable. Coordination-free algorithms simply allow concurrent processors to execute in parallel, interleaving transformations and possibly introducing inconsistencies. Theoretical analysis is then required to prove that the coordination-free algorithm produces a reasonable approximation to the desired outcome, under assumptions on the problem and system.In this dissertation, we propose and explore a third approach by applying concurrency control to manage parallel transformations in machine learning algorithms. We identify points of possible interference between parallel iterations by examining the semantics of the serial algorithm. Coordination is then introduced to either avoid or resolve such conflicts, whereas non-conflicting transformations are allowed to execute concurrently. Our parallel algorithms are thus engineered to produce the same exact output as the serial machine learning algorithm, preserving the serial algorithm's theoretical guarantees of correctness while maximizing concurrency.We demonstrate the feasibility of our approach to parallelizing a variety of machine learning algorithms, including nonparametric unsupervised learning, graph clustering, discrete optimization, and sparse convex optimization. We theoretically prove and empirically verify that our parallel algorithms produce equivalent output to their serial counterparts. We also theoretically analyze the expected concurrency of our parallel algorithms, and empirically demonstrate their scalability.

مستند نام اشخاص تاييد نشده

Pan, Xinghao

مستند نام اشخاص تاييد نشده

Jordan, Michael I

مستند نام تنالگان تاييد نشده

UC Berkeley

نام الکترونيکي

فرمت انتشار

p

نوع ماده

[Thesis]

کد کاربرگه

276903

سطح دسترسي

a

تكميل شده

Y