استفاده از تقريب رتبه پايين به منظور بهبود كارايي ماشين بردار پشتيبان مبتني بر هسته ها و كاربردهاي آن

Using Low-Rank Approximation In Order To Improve the Efficiency of the Support Vector Machine and Applications

ماشين بردار پشتيبان يكي از ابزارهاي توانمند در زمينه يادگيري ماشين با ناظر در طبقه‌بندي داده‌ها مي‌باشد. در مواجهه با داده-هايي كه ساختار ماشين بردار پشتيبان خطي در طبقه‌بندي آنها از كارايي لازم برخوردار نيست، استفاده از ساختار ماشين بردار پشتيبان مبتني بر هسته‌ها مدنظر مي‌باشد. در رويكرد مبتني بر هسته‌ها به دليل استفاده از فضاي ويژگي داده‌ها به جاي خود داده‌هاي اصلي امكان طبقه‌بندي غيرخطي فراهم مي‌آيد. يكي از چالش‌هاي موجود در اين رويكرد افزايش پيچيدگي‌هاي محاسباتي و در نهايت افزايش زمان لازم براي طبقه‌بندي است. عمدتاً اين افزايش زمان محاسباتي به دليل ظاهر شدن هسته در حل مسئله بهينه-سازي درجه دوم است كه با استفاده از تقريب رتبه پايين ارائه شده در اين مقاله قادر خواهيم بود بر اين مشكل غلبه كنيم. در اين تكنيك با به كارگيري سري تقريبي قطع شده از هسته موجود، مسئله بهينه‌سازي درجه دوم در ساختار ماشين بردار پشتيبان مبتني بر هسته‌ها با يك مسئله بهينه سازي با ساختار ساده‌تر جايگزين مي‌گردد. در اين رويكرد ، حاصلضرب‌هاي بردار-ماتريس و تجزيه‌هاي ماتريسي مورد نياز بسيار سريع‌تر انجام خواهد شد. اين تغييرات منجر به حل سريعتر مسئله بهينه‌سازي درجه دوم موجود و افزايش كارايي در طبقه‌بندي مي‌گردد. نهايتاً نتايج عددي ارائه شده در طبقه‌بندي برخي داده‌هاي كاربردي با استفاده از تقريب رتبه پايين ماشين بردار پشتيبان مبتني بر هسته‌ها نشان مي‌دهد كه ضمن حفظ عملكرد طبقه‌بندي در حد قابل قبول، زمان محاسباتي به‌طور قابل توجهي كاهش يافته است.

Support vector machine is one of the most powerful tools in the field of supervised machine learning to classify the existed data. In the data that the linear support vector machine does not have the required efficiency in their classification, using the kernel-based support vector machine which is based on the use of feature space instead of the original data is considered. As a result of this structure, nonlinear classification can be provided. One of the challenges in this approach is to increase the computational complexity and ultimately increase in the required time for classification. As such, it is not particularly useful for large data sets. This increasing in computational time is mainly due to the appearance of the kernel in solving the quadratic optimization problem, which we will be able to overcome this problem using the presented low rank approximation in this paper. In this technique, using a truncated Mercer series of the kernel, the quadratic optimization problem in the kernel-based support vector machine is replaced with a much simpler optimization problem. In the new presented approach, the required vector computations and matrix decompositions will be much faster such that these changes lead to faster resolution of the quadratic optimization problem and increase efficiency. Finally, the results of experiments show that using a low rank kernel-based approximation of support vector machine, while keeping the classification performance in an acceptable range, the computational time has been significantly reduced.