ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG SAVADY Sathaphone Nghiên cứu phương pháp Máy véc tơ hỗ trợ với lề mềm ứng dụng phân lớp liệu tuyến tính có nhiễu LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2019 Số hóa Trung tâm Học liệu Cơng nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG SAVADY Sathaphone Nghiên cứu phương pháp Máy véc tơ hỗ trợ với lề mềm ứng dụng phân lớp liệu tuyến tính có nhiễu Chun ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS Đàm Thanh Phương THÁI NGUYÊN - 2019 Số hóa Trung tâm Học liệu Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan: Luận văn thạc sỹ chuyên ngành Khoa học máy tính, tên đề tài “Nghiên cứu phương pháp Máy véc tơ hỗ trợ với lề mềm ứng dụng phân lớp liệu tuyến tính có nhiễu” cơng trình nghiên cứu, tìm hiểu trình bày tơi thực hướng dẫn khoa học TS Đàm Thanh Phương, Trường Đại học Công nghệ Thông tin Truyền thông - Đại học Thái Nguyên Kết tìm hiểu, nghiên cứu luận văn hồn tồn trung thực, khơng vi phạm điều luật sở hữu trí tuệ pháp luật Việt Nam Nếu sai, tơi hồn tồn chịu trách nhiệm trước pháp luật Tất tài liệu, báo, khóa luận, cơng cụ phần mềm tác giả khác sử dụng lại luận văn dẫn tường minh tác giả có danh mục tài liệu tham khảo Thái Nguyên, ngày 18 tháng năm 2019 Tác giả luận văn SAVADY Sathaphone i LỜI CẢM ƠN Tác giả xin chân thành cảm ơn TS Đàm Thanh Phương, trường Đại học Công nghệ thông tin truyền thông - Đại học Thái Nguyên, giáo viên hướng dẫn khoa học hướng dẫn tác giả hoàn thành luận văn này, xin cảm ơn thầy, cô giáo trường Đại học công nghệ thông tin truyền thông nơi tác giả theo học hồn thành chương trình cao học nhiệt tình giảng dạy giúp đỡ Xin cảm ơn nơi tác giả công tác tạo điều kiện thuận lợi để tác giả hoàn thành chương trình học tập Và cuối xin cảm ơn gia đình, bạn bè, đồng nghiệp động viên, giúp đỡ tác giả suốt thời gian học tập, nghiên cứu hoàn thành luận văn Xin chân thành cảm ơn Thái Nguyên, ngày 18 tháng năm 2019 Tác giả luận văn SAVADY Sathaphone ii DANH SÁCH HÌNH VẼ 2.1 Các mặt phân cách hai lớp tuyến tính 26 2.2 Lề hai lớp không 26 2.3 Lề hai lớp nhau, chọn phương án có lề rộng 26 2.4 Phân tích tốn SVM 27 2.5 Các điểm gần mặt phân cách hai classes khoanh tròn.28 2.6 Soft margin SVM có nhiễu, SVM không hoạt động hiệu quả.33 2.7 Soft margin SVM liệu gần linearly separable, SVM không hoạt động hiệu 34 2.8 Mô tả chọn lề 36 2.9 Hàm hinge loss 3.1 Minh họa nghiệm tìm đc SVM 47 3.2 Dữ liệu tuyến tính có nhiễu 49 3.3 Đường phân chia tìm sklearn 52 3.4 Đường phân chia tìm hinge loss 52 3.5 Đường phân chia tìm đối ngẫu Các kết 52 3.6 Nghiệm tìm sklearn, C =0.1 53 3.7 Nghiệm tìm sklearn, C=1 53 3.8 Nghiệm C=10 53 3.9 Ảnh hưởng C lên nghiệm, C=100 54 42 iii DANH MỤC KÝ HIỆU, TỪ VIẾT TẮT iv R Tập hợp số thực Z Tập hợp số nguyên C Tập hợp số phức Rn Không gian Euclide n chiều ||.|| Chuẩn Euclide Suport vector machine - máy véc tơ hỗ SVM trợ Soft SVM Máy véc tơ hỗ trợ với lề mềm Argmin Bài tốn tối ưu tham số Duality Tính chất đối ngẫu, đối ngẫu Lagrangian Đối ngẫu Lagrange Strong duality Tính chất đối ngẫu mạnh Weak duality Tính chất đối ngẫu yếu KKT Karush Kuhn Tucker - Điều kiện KKT det(A) Định thức ma trận A AT Chuyển vị ma trận A AH Hermitian ma trận A A F Frobenius norm ma trận A diag(A) Đường chéo ma trận A trace(A) trace ma trận A sng(x) Hàm xác định dấu ∂f ∂x ∇x f Đạo hàm hàm số f theo biến số x∈R Gradient (đạo hàm ) hàm số f theo véc tơ x v MỤC LỤC Lời cam đoan i Lời cảm ơn ii Danh sách hình vẽ ii Danh mục ký hiệu, từ viết tắt v Mở đầu Chương MỘT SỐ KIẾN THỨC CHUẨN BỊ 1.1 Tổng quan ngôn ngữ Python 1.2 Giới thiệu học máy 1.3 Một số kiến thức toán học bổ trợ 11 Chương PHƯƠNG PHÁP MÁY VÉC TƠ HỖ TRỢ SVM 25 2.1 Bài toán phân lớp SVM 25 2.2 Bài toán SVM với lề mềm 33 Chương ỨNG DỤNG VÀ LẬP TRÌNH MƠ PHỎNG 46 3.1 Lập trình tìm nghiệm cho SVM 46 3.2 Lập trình tìm nghiệm cho Soft SVM 48 Kết luận chung 55 Tài liệu tham khảo 55 vi MỞ ĐẦU Những năm gần đây, AI - Artificial Intelligence (Trí Tuệ Nhân Tạo), cụ thể Machine Learning (Học Máy Máy Học) lên chứng cách mạng công nghiệp lần thứ tư (1 - động nước, lượng điện, - cơng nghệ thơng tin) Trí Tuệ Nhân Tạo len lỏi vào lĩnh vực đời sống mà không nhận Xe tự hành Google Tesla, hệ thống tự tag khuôn mặt ảnh Facebook, trợ lý ảo Siri Apple, hệ thống gợi ý sản phẩm Amazon, hệ thống gợi ý phim Netflix, máy chơi cờ vây AlphaGo Google DeepMind, , vài ứng dụng AI/Machine Learning [7] Machine Learning tập AI Theo định nghĩa Wikipedia, Machine learning is the subfield of computer science that “gives computers the ability to learn without being explicitly programmed” Nói đơn giản, Machine Learning lĩnh vực nhỏ Khoa Học Máy Tính, có khả tự học hỏi dựa liệu đưa vào mà khơng cần phải lập trình cụ thể [1] Phân lớp hồi quy hai số thuật tốn học máy có giám sát có nhiều ứng dụng thực tế Bài tốn phân lớp tuyến tính yêu cầu xây dựng classifier từ liệu training để có điểm liệu ta dự đốn nhãn Giả sử có hai class khác mơ tả điểm không gian nhiều chiều, hai classes linearly separable, tức tồn siêu phẳng phân chia xác hai classes Hãy tìm siêu mặt phẳng phân chia hai classes đó, tức tất điểm thuộc class nằm phía siêu mặt phẳng ngược phía với tồn điểm thuộc class lại Chúng ta biết rằng, thuật tốn PLA làm việc cho vơ số nghiệm Câu hỏi đặt là: vô số mặt phân chia đó, đâu mặt phân chia tốt theo tiêu chuẩn đó? Chúng ta cần đường phân chia cho khoảng cách từ điểm gần class tới đường phân chia nhau, cơng Khoảng cách gọi margin (lề) Ngoài ra, việc margin rộng mang lại hiệu ứng phân lớp tốt phân chia hai classes rạch ròi Việc điểm quan trọng giúp Support Vector Machine mang lại kết phân loại tốt so với Neural Network với layer, tức Perceptron Learning Algorithm.[1], [2] Bài toán tối ưu Support Vector Machine (SVM) tốn tìm đường phân chia cho margin lớn Đây lý SVM gọi Maximum Margin Classifier [7] Tuy nhiên SVM với lề cứng không giải số tốn phân lớp có nhiễu, việc nghiên cứu SVM với lề mềm giải tốt trường hợp Nội dung luận văn gồm chương: Chương Các kiến thức sở Chương trình bày kiến thức chuẩn bị cho việc nghiên cứu 1.1 Giới thiệu học máy 1.2 Giới thiệu ngơn ngữ lập trình Python 1.3 Các kiến thức sở Đại số tuyến tính Chương Phương pháp máy véc tơ hỗ trợ SVM Nội dung chương tập trung vào vấn đề nghiên cứu phương pháp máy véc tơ hỗ trợ, cụ thể sau: 2.1 Xây dựng toán tối ưu cho SVM 2.2 Bài toán đối ngẫu cho SVM 2.3 Bài toán đối ngẫu Lagrange 2.4 Bài tốn tối ưu khơng ràng buộc cho Soft SVM Chương Ứng dụng lập trình mô Sau nắm rõ nội dung chương 2, chương trình bày số ví phân loại sai Ta có nhận xét: • Với hàm zero-one loss, điểm có score ngược dấu với đầu mong muốn gây mát (bằng 1), chúng gần hay xa đường phân chia (trục tung) Đây hàm rời rạc, khó tối ưu ta khó đo đếm hy sinh định nghĩa phần đầu • Với hàm hinge loss, điểm nằm vùng an toàn, ứng với ys ≥ , khơng gây mát Những điểm nằm margin class tương ứng đường phân chia tương ứng với < y < 1, điểm gây mát nhỏ Những điểm bị misclassifed, tức y < gây mát lớn hơn, vậy, tối thiểu hàm mát, ta tránh điểm bị misclassifed lấn sang phần class lại nhiều Đây ưu điểm hàm hinge loss • Hàm hinge loss hàm liên tục, có đạo hàm gần nơi (almost everywhere differentiable) trừ điểm có hồnh độ Ngồi ra, đạo hàm hàm dễ xác định: -1 điểm nhỏ điểm lớn Tại 1, ta coi đạo hàm Xây dựng hàm mát Ta xem xét toán Soft Margin SVM góc nhìn hinge loss Với cặp (w, b), đặt Ln (w, b) = max(0, − yn (wT xn + b)) (2.2.36) Lấy tổng tất loss theo n ta được: N N L(w, b) = max(0, − yn (wT xn + b)) Li = n=1 (2.2.37) n=1 Chúng ta không trực tiếp tối ưu hinge loss mà bổ sung số hạng λR(w, b) vào L(w, b) Số hạng gọi thành phần regularization Khi hàm mát tổng là: J(w, b) = L(w, b) + λR(w, b) 43 (2.2.38) với λ tham số regularization dương, R() hàm giúp hạn chế việc hệ số (w, b) trở nên lớn Một cách chọn hàm () chuẩn l2 , hàm mát SVM lề mềm N J(w, b) = λ max(0, − yn (wT xn + b)) + ||w||22 n=1 (2.2.39) Nếu mở rộng thêm thành phần vào điểm liệu xn ∈ Rd để ¯ n ∈ Rd+1 kết hợp w, b thành véc tơ w ¯ = [wT , b]T ∈ Rd+1 ta x viết gọn hơn: N ¯Tx max(0, − yn w ¯n ) + J(w) ¯ = n=1 hinge loss λ ||w||22 (2.2.40) regularization Ta nhận thấy hàm lồi (theo w ¯ ) vì: ¯Tx • − yn w ¯n hàm tuyến tính nên hàm lồi Hàm số hàm lồi, max cuả hai hàm lồi hàm lồi Vậy biểu thức hinge loss hàm lồi • Chuẩn hàm lồi, số hạng regularization hàm lồi • Tổng hai hàm lồi hàm lồi Vì tốn tối ưu khơng ràng buộc, sử dụng phương pháp Gradient Descent để tối ưu Hơn nữa, tính chất lồi hàm mát, chọn learning rate khơng q lớn số vòng lặp đủ nhiều, thuật toán hội tụ tới điểm global optimal tốn Tối ưu hàm mát Ta tính thành  phần  w Đạo hàm phần regularization đơn giản λ   với thành phần 0 cuối đạo hàm theo bias thành phần regularization Với phần hinge loss, xét điểm liệu, ta có hai trường hợp: • Nếu − yn w ¯Tx ¯n ≤ 0, ta có đạo hàm theo w ¯ • Nếu − yn w ¯Tx ¯n > 0, đạo hàm theo w ¯ −yn xn 44 Để tính gradient cho toàn liệu, ta đặt Z = [y1 x ¯1 , y2 x ¯ , , yN x ¯N ] (2.2.41) u = [y1 w ¯Tx ¯1 , y2 w ¯Tx ¯ , , yN w ¯Tx ¯N ] = w ¯TZ (2.2.42) ý u véc tơ hàng Tiếp tục, ta cần xác định vị trí u có giá trị nhỏ 1, tức ứng với trường hợp Đặt H = {n : un < 1} ta suy cách tính đạo hàm theo w ¯ hàm mát   w ∇J(w) ¯ = −yn x ¯n + λ   n∈H (2.2.43) Vậy quy tắc cập nhật w ¯ là:    w −yn x ¯n + λ   w ¯ =w ¯ −η n∈H với η tốc độ học 45 (2.2.44) CHƯƠNG ỨNG DỤNG VÀ LẬP TRÌNH MƠ PHỎNG Chương trình bày số kết lập trình mơ ứng dụng SVM với lề mềm trường hợp liệu tuyến tính có nhiễu 3.1 Lập trình tìm nghiệm cho SVM 3.1.1 Tìm nghiệm theo cơng thức - Gọi module cần dùng tạo liệu giả, đảm bảo phân tách tuyến tính from future import print_function import numpy as np import matplotlib.pyplot as plt from scipy.spatial.distance import cdist np.random.seed(22) means = [[2, 2], [4, 2]] cov = [[.3, 2], [.2, 3]] N = 10 X0 = np.random.multivariate_normal(means[0], cov, N) # class X1 = np.random.multivariate_normal(means[1], cov, N) # class -1 X = np.concatenate((X0.T, X1.T), axis = 1) # all data y = np.concatenate((np.ones((1, N)), -1*np.ones((1, N))), axis = 1) # labels Tiếp theo, giải toán đối ngẫu 2.1.16 - 2.1.18 CVXOPT: from cvxopt import matrix, solvers # build K V = np.concatenate((X0.T, -X1.T), axis = 1) K = matrix(V.T.dot(V)) # see definition of V, K near eq (8) p = matrix(-np.ones((2*N, 1))) # all-one vector # build A, b, G, h G = matrix(-np.eye(2*N)) # for all lambda_n >= h = matrix(np.zeros((2*N, 1))) A = matrix(y) # the equality constrain is actually y^T lambda = b = matrix(np.zeros((1, 1))) solvers.options[’show_progress’] = False sol = solvers.qp(K, p, G, h, A, b) l = np.array(sol[’x’]) print(’lambda = ’) print(l.T) Kết lambda = [[ 8.54018321e-01 2.89132533e-10 1.37095535e+00 6.36030818e-10 4.04317408e-10 8.82390106e-10 6.35001881e-10 5.49567576e-10 8.33359230e-10 1.20982928e-10 6.86678649e-10 1.25039745e-10 2.22497367e+00 4.05417905e-09 1.26763684e-10 1.99008949e-10 2.13742578e-10 1.51537487e-10 3.75329509e-10 3.56161975e-10]] 46 Hình 3.1: Minh họa nghiệm tìm đc SVM Các giá trị lambda nhỏ Đúng phải kết phản ánh sai số tính tốn Ta tìm tập hợp véc tơ hỗ trợ tìm nghiệm toán epsilon = 1e-6 # just a small number, greater than 1e-9 S = np.where(l > epsilon)[0] VS = V[:, S] XS = X[:, S] yS = y[:, S] lS = l[S] # calculate w and b w = VS.dot(lS) b = np.mean(yS.T - w.T.dot(XS)) print(’w = ’, w.T) print(’b = ’, b) w = [[-2.00984381 0.64068336]] b = 4.66856063387 Các kết minh họa hình ảnh 3.1 Đường màu đen đậm mặt phân cách tìm SVM 3.1.2 Tìm nghiệm theo thư viện Nếu sử dụng sklearn, ta làm sau from sklearn.svm import SVC y1 = y.reshape((2*N,)) X1 = X.T # each sample is one row clf = SVC(kernel = ’linear’, C = 1e5) # just a big number clf.fit(X1, y1) 47 w = clf.coef_ b = clf.intercept_ print(’w = ’, w) print(’b = ’, b) Kết w = [[-2.00971102 0.64194082]] b = [ 4.66595309] Kết kết tìm nghiệm theo cơng thức tương đồng 3.2 Lập trình tìm nghiệm cho Soft SVM 3.2.1 Giải toán lề mềm ba cách Khai báo tạo liệu giả # generate data # list of points import numpy as np import matplotlib.pyplot as plt from scipy.spatial.distance import cdist np.random.seed(21) from matplotlib.backends.backend_pdf import PdfPages means = [[2, 2], [4, 1]] cov = [[.3, 2], [.2, 3]] N = 10 X0 = np.random.multivariate_normal(means[0], cov, N) X1 = np.random.multivariate_normal(means[1], cov, N) X1[-1, :] = [2.7, 2] X = np.concatenate((X0.T, X1.T), axis = 1) y = np.concatenate((np.ones((1, N)), -1*np.ones((1, N))), axis = 1) Hình 3.2 mô tả liệu vừa tạo Giải thư viện sklearn Chọn C = 100 from sklearn.svm import SVC C = 100 clf = SVC(kernel = ’linear’, C = C) clf.fit(X, y) w_sklearn = clf.coef_.reshape(-1, 1) b_sklearn = clf.intercept_[0] print(w_sklearn.T, b_sklearn) Nghiệm tìm đc [[-1.87461946 -1.80697358]] 8.49691190196 Tìm nghiệm giải tốn đối ngẫu from cvxopt import matrix, solvers # build K 48 Hình 3.2: Dữ liệu tuyến tính có nhiễu V = np.concatenate((X0.T, -X1.T), axis = 1) K = matrix(V.T.dot(V)) p = matrix(-np.ones((2*N, 1))) # build A, b, G, h G = matrix(np.vstack((-np.eye(2*N), np.eye(2*N)))) h = matrix(np.vstack((np.zeros((2*N, 1)), C*np.ones((2*N, 1))))) A = matrix(y.reshape((-1, 2*N))) b = matrix(np.zeros((1, 1))) solvers.options[’show_progress’] = False sol = solvers.qp(K, p, G, h, A, b) l = np.array(sol[’x’]) print(’lambda = \n’, l.T) lambda = [[ 1.11381472e-06 9.99999967e+01 1.10533112e-06 6.70163540e-06 3.40838760e+01 4.73972850e-06 9.99999978e+01 3.13320446e-06 9.99999985e+01 5.06729333e+01 9.99999929e+01 3.23564235e-06 9.99999984e+01 9.99999948e+01 1.37977626e-06 9.99997155e+01 3.45005660e-06 1.46190314e-06 5.50601997e-06 1.45062544e-06 1.85373848e-06 1.14181647e-06 8.47565685e+01 9.99999966e+01 9.99999971e+01 8.00764708e-07 2.65537193e-06 1.45230729e-06 4.15737085e-06 9.99999887e+01 9.99999761e+01 8.98414770e-07 9.99999979e+01 1.75651607e-06 8.27947897e-07 1.04289116e-06 9.99999969e+01 9.07920759e-07 8.83138295e-07 9.99999971e+01]] Trong thành phần lambda tìm được, có nhiều thành phần nhỏ, tới 10−7 Đây lambdai = Có nhiều phần tử xấp xỉ với C = 100, tương ứng với véc tơ hỗ trợ không nằm lề, với sai số tính tốn nhỏ Các giá trị lại nằm 100 giá trị tương ứng với điểm nằm xác hai lề Tiếp theo ta cần tính w b theo công thức 2.2.25 ?? Trước ta cần 49 tìm tập hợp điểm hỗ trợ điểm nằm lề S = np.where(l > 1e-5)[0] # support set S2 = np.where(l < 999*C)[0] M = [val for val in S if val in S2] # intersection of two lists XT VS lS yM XM = = = = = X.T # we need each column to be one data point in this alg V[:, S] l[S] y[M] XT[:, M] w_dual = VS.dot(lS).reshape(-1, 1) b_dual = np.mean(yM.T - w_dual.T.dot(XM)) print(w_dual.T, b_dual) Kết [[-1.87457279 -1.80695039]] 8.49672109815 Kết gần giống với kết tìm sklearn Tìm nghiệm giải tốn khơng ràng buộc Trong phương pháp này, ta cần tính gradient hàm mát Như thường lệ, cần kiểm chứng cách so sánh với đạo hàm số X0_bar = np.vstack((X0.T, np.ones((1, N)))) # extended data X1_bar = np.vstack((X1.T, np.ones((1, N)))) # extended data Z = np.hstack((X0_bar, - X1_bar)) # as in (22) lam = 1./C def cost(w): u = w.T.dot(Z) # as in (23) return (np.sum(np.maximum(0, - u)) + \ 5*lam*np.sum(w*w)) - 5*lam*w[-1]*w[-1] # no bias def grad(w): u = w.T.dot(Z) # as in (23) H = np.where(u < 1)[1] ZS = Z[:, H] g = (-np.sum(ZS, axis = 1, keepdims = True) + lam*w) g[-1] -= lam*w[-1] # no weight decay on bias return g eps = 1e-6 def num_grad(w): g = np.zeros_like(w) for i in xrange(len(w)): wp = w.copy() wm = w.copy() wp[i] += eps wm[i] -= eps g[i] = (cost(wp) - cost(wm))/(2*eps) return g w0 = g1 = g2 = diff np.random.randn(X0_ext.shape[0], 1) grad(w0) num_grad(w0) = np.linalg.norm(g1 - g2) 50 print(’Gradient different: %f’ %diff) Kết so sánh cho thấy với đạo hàm số Gradient difference: 0.000000 Vì khác hai cách tính gradient 0, ta n tâm gradient tính xác Sau chắn gradient tìm xác, ta bắt đầu làm Gradient Descent: def grad_descent(w0, eta): w = w0 it = while it < 100000: it = it + g = grad(w) w -= eta*g if (it % 10000) == 1: print(’iter %d’ %it + ’ cost: %f’ %cost(w)) if np.linalg.norm(g) < 1e-5: break return w w0 = np.random.randn(X0_ext.shape[0], 1) w = grad_descent(w0, 0.001) w_hinge = w[:-1].reshape(-1, 1) b_hinge = w[-1] print(w_hinge.T, b_hinge) Kết [[-1.8623959 -1.79532187]] [ 8.4493419] Ta thấy kết tìm ba cách Các hình 3.33.5 minh hoạ kết ba cách tính: Trong thực tế áp dụng, phương pháp chắn lựa chọn gọn gàng, nhanh chóng Ảnh hưởng C lên nghiệm Ta thấy C lớn biên nhỏ phần phân tích tốn học Kết thể biến đổi C hình Thảo luận • SVM (Hard Margin SVM) hoạt động khơng hiệu có nhiễu gần biên chí liệu hai lớp gần linearly separable Soft Margin SVM giúp khắc phục điểm 51 Hình 3.3: Đường phân chia tìm sklearn Hình 3.4: Đường phân chia tìm hinge loss Hình 3.5: Đường phân chia tìm đối ngẫu Các kết 52 Hình 3.6: Nghiệm tìm sklearn, C =0.1 Hình 3.7: Nghiệm tìm sklearn, C=1 Hình 3.8: Nghiệm C=10 53 Hình 3.9: Ảnh hưởng C lên nghiệm, C=100 • Trong Soft Margin SVM, chấp nhận lỗi xảy vài điểm liệu Lỗi xác định khoảng cách từ điểm tới đường biên tương ứng Bài tốn tối ưu tối thiểu lỗi cách sử dụng thêm biến gọi slack varaibles • Để giải tốn tối ưu, có hai cách khác Mỗi cách có ưu, nhược điểm riêng • Cách thứ giải toán đối ngẫu Bài toán đối ngẫu Soft Margin SVM giống với toán đối ngẫu Hard Margin SVM, khác ràng buộc chặn nhân tử Laggrange Ràng buộc gọi box costraint • Cách thứ hai đưa tốn dạng khơng ràng buộc dựa hàm gọi hinge loss Với cách này, hàm mát thu hàm lồi giải dễ dàng hiệu phương pháp Gradient Descent • Trong Soft Margin SVM, có số phải chọn, C Hướng tiếp cận gọi C-SVM Ngồi ra, có hướng tiếp cận khác hay sử dụng, gọi v-svm 54 KẾT LUẬN CHUNG Dưới bảo Giáo viên hướng dẫn, vào đề cương luận văn phê duyệt, luận văn đạt số nhiệm vụ sau: (1) Tìm hiểu phương pháp phân lớp tuyến tính máy véc tơ hỗ trợ SVM Bài toán tối ưu SVM toán tìm đường phân chia cho lề đảm bảo lớn Nghĩa đảm bảo khoảng cách từ điểm gần hai lớp tới mặt phân chia rộng (2) Xây dựng giải toán tối ưu cho SVM Hiểu kiến thức toán sở SVM bước giải tốn tối ưu (3) Tìm hiểu toán SVM với lề mềm Trong trường hợp lớp tuyến tính có nhiễu, cần phải xây dựng lại điều kiện tối ưu để giải toán thực tế Việc giải trực tiếp giải thơng qua toán đối ngẫu nghiên cứu (4) Cài đặt mô ứng dụng phương pháp phân lớp điều kiện đơn giản, có nhiễu để thấy ý nghĩa toán Trên sở kết đạt được, tiếp tục nghiên cứu luận văn tảng tốt để nghiên cứu thêm số vấn đề sau: • Mở rộng tốn SVM thỏa mãn yêu cầu thực tế liệu • Tối ưu phương pháp giải • Các ứng dụng phân lớp tuyến tính có nhiễu thực tế 55 TÀI LIỆU THAM KHẢO [1] Bishop, Christopher M.“Pattern recognition and Machine Learning.”, Springer (2006) [2] Duda, Richard O., Peter E Hart, and David G Stork Pattern classification John Wiley & Sons, 2012 [3] LIBSVM – A Library for Support Vector Machines https://www.csie.ntu.edu.tw/ cjlin/libsvm/ [4] sklearn.svm.SVC https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html [5] Bennett, K P (1992) “Robust linear programming discrimination of two linearly separable sets” Optimization Methods and Software 1, 23–34 [6] Rosasco, L.; De Vito, E D.; Caponnetto, A.; Piana, M.; Verri, A (2004) “Are Loss Functions All the Same?” Neural Computation 16 (5): 1063–1076 [7] Machine learning bản, Vũ Hữu Tiệp., https://machinelearningcoban.com/ [8] Eric Matthes, "Python Crash Course", 2016 [9] Võ Duy Tuấn, "Python bản", 2016 [10] Đàm Thanh Phương, Trương Hà Hải, Ngô Mạnh Tưởng, Bùi Thị Thanh Xn, "Giáo trình Tốn cao cấp 1", NXB Đại học Thái Nguyên, 2016 56 Số hóa Trung tâm Học liệu Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn ... Sathaphone Nghiên cứu phương pháp Máy véc tơ hỗ trợ với lề mềm ứng dụng phân lớp liệu tuyến tính có nhiễu Chun ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người... đề tài Nghiên cứu phương pháp Máy véc tơ hỗ trợ với lề mềm ứng dụng phân lớp liệu tuyến tính có nhiễu cơng trình nghiên cứu, tìm hiểu trình bày tơi thực hướng dẫn khoa học TS Đàm Thanh Phương, ... Tính chất Nếu x véc tơ riêng A ứng với giá trị riêng λ với k ∈ R, k = 0, kx véc tơ riêng A ứng với giá trị riêng Nếu x1 , x2 hai véc tơ riêng ứng với giá trị riêng λ tổng chúng véc tơ riêng ứng