Tài liệu Phương pháp support vector machines và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI -------------------------------------- VŨ VIỆT VŨ PHƯƠNG PHÁP SUPPORT VECTOR MACHINES VÀ ỨNG DỤNG CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS NGUYỄN THANH THUỶ HÀ NỘI - 2004 1 MỤC LỤC MỞ ĐẦU .......................................................................................................... 3 CHƯƠNG 1. CÁC KHÁI NIỆM CƠ BẢN ................................................... 5 1.1. Các phương pháp học .................................................................................. 5 1.1.1. Giới thiệu .............................................................................................. 5 1.1.2. Học có thầy ............................................................................................ 5 1.1.3. Học không có thầy .................................................................................. 6 1.1.4. Học tăng cường ...................................................................................... 6 1.1.5. Các biến thể trong mô hình học ............................................................... 6 1.1.6. Quá trình học......................................................................................... 7 1.1.7. Lý thuyết học ......................................................................................... 7 1.2. Support Vector Machines và phân lớp với khoảng cách lớn nhất ................... 7 1.3. Phân lớp tuyến tính ..................................................................................... 8 1.4. Ma trận GRAM .......................................................................................... 8 1.5. Khoảng cách giữa các siêu phẳng ................................................................. 8 1.6. Tổng kết chương 1 ..................................................................................... 10 CHƯƠNG 2. KHÔNG GIAN ĐẶC TRƯNG ............................................. 11 2.1. Đặt vấn đề ................................................................................................ 11 2.2. Không gian đặc trưng ................................................................................ 11 2.3. Hàm hạt nhân ........................................................................................... 11 2.3.1. Khái niệm hàm hạt nhân ...................................................................... 11 2.3.2. Máy học tuyến tính thông qua biểu diễn hàm hạt nhân ........................... 12 2.3.3. Các đặc trưng của xâu kí tự và văn bản ................................................. 13 2.3.4. Hàm hạt nhân dựa trên đặc trưng của xâu kí tự ..................................... 16 2.3.5. Khoảng cách Levenstein ....................................................................... 18 2.3.6. Hàm hạt nhân dựa trên khoảng cách ..................................................... 19 2.3.7. Một số hàm hạt nhân ............................................................................ 19 2.3.8. Tính chất của hàm hạt nhân.................................................................. 21 2.3.9. Xây dựng vectơ đặc trưng dựa trên hàm hạt nhân .................................. 22 2.3.10. Xây dựng hàm hạt nhân từ các hàm hạt nhân cơ sở .............................. 23 2.4. Không gian các hàm hạt nhân Hilbert ......................................................... 24 2.5. Tổng kết chương 2 ..................................................................................... 25 CHƯƠNG 3. PHƯƠNG PHÁP SUPPORT VECTOR MACHINES ..... 26 3.1. Giới thiệu.................................................................................................. 26 3.2. Nội dung phương pháp .............................................................................. 26 3.2.1. Mở đầu ................................................................................................ 26 LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 2 3.2.2. Phương pháp SVM trong trường hợp dữ liệu phân tách tuyến tính.......... 29 3.2.3. Phương pháp SVM trong trường hợp dữ liệu không phân tách tuyến tính trong không gian đặc trưng ........................................................................... 37 3.2.4. SVM nhiều lớp ..................................................................................... 43 3.2.5. Lựa chọn hàm hạt nhân cho các ứng dụng ............................................. 43 3.2.6. Lựa chọn các tham số cho hạt nhân RBF ............................................... 44 3.3. Giải quyết bài toán tối ưu dạng C- SVC và v - SVC ..................................... 45 3.3.1. Thuật toán phân rã cho bài toán C – SVC ............................................. 45 3.3.2. Lựa chọn tập làm việc và tiêu chuẩn dừng cho C –SVC........................... 47 3.3.3. Thuật toán phân rã cho bài toán v- SVC ................................................ 49 3.3.4. Phân tích lời giải .................................................................................. 50 3.3.5. Tính b và  .......................................................................................... 52 3.4. So sánh phương pháp SVM và phương pháp mạng Nơ ron .......................... 52 3.5. Tổng kết chương 3 ..................................................................................... 53 CHƯƠNG 4. MỘT SỐ ỨNG DỤNG CỦA SVM ....................................... 53 4.1. Giới thiệu.................................................................................................. 53 4.2. Cài đặt chương trình ................................................................................. 53 4.3. Kiểm thử chương trình .............................................................................. 54 4.3. Phân lớp nấm sử dụng SVM....................................................................... 63 4.3.1. Giới thiệu ............................................................................................ 63 4.3.2. Tiền xử lý dữ liệu ................................................................................. 63 4.3.3. Lựa chọn hàm hạt nhân ........................................................................ 65 4.3.4. Kết quả thi hành chương trình .............................................................. 65 4.5. Một số ứng dụng đã triển khai sử dụng phương pháp SVM .......................... 67 4.6. Kết luận .................................................................................................... 68 CHƯƠNG 5. KẾT LUẬN ............................................................................. 69 5.1. Những kết quả đã đạt được ........................................................................ 69 5.2. Hướng phát triển của đề tài........................................................................ 69 TÀI LIỆU THAM KHẢO ............................................................................ 70 LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 3 MỞ ĐẦU Ngày nay sự phát triển rất nhanh và mạnh mẽ của ngành Công nghệ Thông tin đã góp phần rất lớn vào sự phát triển của xã hội. Các ứng dụng của Công nghệ Thông tin đã liên tục được triển khai và mang lại hiệu quả cao trong thực tế. Công nghệ Thông tin đã có những liên hệ chặt chẽ với các ngành khác như điều khiển học, khoa học vũ trụ, sinh học, hoá học,... Trong luận văn tốt nghiệp Cao học tại Trường Đại học Bách Khoa Hà Nội, tôi chọn đề tài “PHƯƠNG PHÁP SUPPORT VECTOR MACHINES VÀ ỨNG DỤNG”. ▪ Lý do chọn đề tài Vấn đề phân lớp (Classification) và dự đoán (Pridiction) là khâu rất quan trọng trong học máy và trong khai phá dữ liệu, phát hiện tri thức. Phương pháp Support Vector Machines (SVM) được coi là công cụ mạnh và tinh vi nhất hiện nay cho những bài toán phân lớp phi tuyến, phương pháp này ra đời năm 1995 bởi tác giả Vapnik và Chervonenkis. Hiện nay đã có rất nhiều những ứng dụng hiệu quả được xây dựng dựa vào phương pháp SVM và nhiều người đã đánh giá rằng SVM là phương pháp mạnh và hiệu quả hơn phương pháp mạng Neural. ▪ Mục đích, đối tượng và phạm vi nghiên cứu Trong khuôn khổ luận văn sẽ nghiên cứu phần cơ sở lý thuyết của phương pháp SVM, các vấn đề liên quan đến phương pháp và xây dựng một số ứng dụng cụ thể của phương pháp. ▪ Ý nghĩa khoa học và thực tiễn Đây là một phương pháp phân lớp hiện đại và hiệu quả, nắm chắc phương pháp này sẽ là nền tảng cho việc xây dựng những ứng dụng quan trọng trong thực tế. Nội dụng của luận văn bao gồm: LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 4 Chương 1. Các khái niệm cơ bản Chương 2. Không gian đặc trưng Chương 3. Phương pháp Support Vector Machines Chương 4. Một số ứng dụng của phương pháp SVM Chương 5. Kết luận LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 5 CHƯƠNG 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. Các phương pháp học 1.1.1. Giới thiệu Có một số bài toán khó có thể giải quyết bằng kỹ thuật cổ điển, ví dụ như nhận dạng chữ viết tay với giả thiết có rất nhiều mẫu chữ viết tay có sẵn. Vấn đề đặt ra ở đây là huấn luyện máy tính nhận dạng các ký tự thông qua các mẫu có sẵn. Các kỹ thuật này tương tự cũng sẽ sử dụng cho việc tìm kiếm gene trong dãy DNA, lọc thư điện tử, phát hiện virus máy tính, dự đoán cấu trúc của Protein,... Việc sử dụng các mẫu học cho việc xây dựng các chương trình có khả năng khái quát và tổng hợp được biết đến như là phương pháp học 1.1.2. Học có thầy Vấn đề cơ bản của học có thầy là xác định một hàm, hay xác định một ánh xạ giữa đầu vào và đầu ra một cách tốt nhất, tức là việc tỷ lệ lỗi đối với các mẫu kiểm chứng là nhỏ nhất. Các ký hiệu: x  X: đầu vào và không gian đầu vào, y  Y: đầu ra và không gian đầu ra, S : tập mẫu học, S = {(x1, y1), (x2, y2), (x3, y3),… (xℓ yℓ)}  (X  Y)ℓ ℓ: là kích thước tập mẫu huấn luyện. Tuỳ thuộc vào kiểu của đầu ra, ta chia các bài toán phân lớp với học có thầy thành: học phân lớp, học ưu tiên, hồi quy (học hàm). Nếu đầu ra là các giá trị nhị phân như : (yes/ no), (+/-), (0/1), bài toán học được gọi là bài toán phân lớp nhị phân. Nếu đầu ra có một số hữu hạn giá trị khác nhau thì ta nói đây là bài toán nhiều lớp. Nếu không gian đầu ra là các số thực, bài toán học LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 6 có thầy được gọi là bài toán hồi quy (Regression). Nếu không gian đầu ra có thứ tự, trong đó các giá trị sánh được với nhau, khác nhau từng đôi một, bài toán học có thầy được gọi là học ưu tiên. 1.1.3. Học không có thầy Trong học không có thầy, mục đích đặt ra là xây dựng một miêu tả chung cho một phần tử x bất kỳ, có thể sử dụng cho việc lập luận, tạo ra các quyết định, dự đoán, xác định mối liên hệ giữa các thực thể… Học không có thầy do không có giá trị đầu ra nên được xem như việc trích rút các quá trình phát sinh ra từ dữ liệu đầu vào. Ứng dụng của học không có thầy: thường trong bài toán phân cụm, bài toán giảm số chiều, tìm ra ngữ nghĩa ẩn hoặc nguồn gốc của dữ liệu, các mô hình mật độ dữ liệu giúp cho quá trình nén dữ liệu, phát hiện các dị thường và quá trình phân lớp. 1.1.4. Học tăng cường Trong học tăng cường, máy có thể đưa ra các hoạt động ảnh hưởng tới trạng thái thực tại và nhận được những kích thích dưới dạng lợi ích hoặc rủi ro, nhằm cực đại lợi ích thu được. 1.1.5. Các biến thể trong mô hình học • Học theo lô: Tất cả dữ liệu được đưa cho người học tại thời điểm ban đầu. • Học trực tuyến: Trong quá trình học người học nhận được một mẫu tại một thời điểm, đưa ra một đánh giá cho đầu ra và sau đó nhận được kết quả đúng và ghi nhận một mẫu. Chúng ta sẽ tập trung vào kỹ thuật áp dụng cho việc học có thầy và sử dụng việc học theo lô. LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 7 1.1.6. Quá trình học Mô hình điển hình về quá trình học là xác định một hàm mục tiêu, một khái niệm, phản ánh mối quan hệ giữa đầu vào và đầu ra. Khi đó, mẫu học sẽ đưa tới một đánh giá của hàm mục tiêu. Thuật toán học là thuật toán nhận tập mẫu học như là đầu vào và lựa chọn các giả thuyết h từ không gian giả thuyết H. Một thuật toán chọn được một giả thuyết h tạo ra phân lớp đúng so với tập mẫu sẽ được gọi là thuật toán học nhất quán. Khi giả thuyết phân lớp áp dụng được cho cả đầu vào không có trong tập mẫu, ta nói quá trình học đã đạt được sự khái quát hoá. Mục đích của chúng ta là tối ưu hoá sự khái quát này. 1.1.7. Lý thuyết học Mục đích của lý thuyết học là trả lời các câu hỏi như sau: ▪ Cần bao nhiêu mẫu học ℓ đủ cho việc thi hành của máy suy diễn? ▪ Với một tập mẫu xác định S, hiệu suất là bao nhiêu? ▪ Với hai thuật toán học đã cho, thuật toán nào sẽ phân lớp tối ưu hơn? 1.2. Support Vector Machines và phân lớp với khoảng cách lớn nhất Support Vector Machines (SVM) là phương pháp học sử dụng không gian giả thuyết các hàm tuyến tính trên không gian đặc trưng nhiều chiều, dựa trên lý thuyết tối ưu và lý thuyết thống kê. Trong học có thầy, ta có tập các mẫu học: S = {(x1, y1), (x2, y2), (x3, y3),... (xℓ,yℓ)}  (X  Y)ℓ, ℓ là số lượng của tập mẫu học, xi là đầu vào và yi là nhãn phân lớp tương ứng. Một tập mẫu học được gọi là tầm thường nếu tất cả các nhãn là bằng nhau. Thông thường không gian đầu vào thường là tập con của không gian giá trị thực, X  Rn (trong đó n là số chiều của không gian đầu vào). LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 8 1.3. Phân lớp tuyến tính Hàm tuyến tính f(x) tương ứng với phân lớp nhị phân ( đầu ra y {-1, 1}), có thể phát biểu như sau: Đầu vào x = {x1, x2, ..., xn} sẽ được gán vào lớp có nhãn 1 nếu f(x) 0, còn ngược lại gán vào lớp có nhãn -1 n ở đây f ( x)   wi xi  b  w.x  b i 1 trong đó . biểu thị tích vô hướng. + + + - w + + - b/||w|| + + +xi - Hình 1.1. Phân tách theo siêu phẳng (w, b) trong không gian 2 chiều của tập mẫu Vectơ w gọi là vectơ pháp tuyến của siêu phẳng, giá trị của b thay đổi có thể tạo ra các siêu phẳng song song với nhau. b được gọi là ngưỡng. 1.4. Ma trận GRAM Cho tập {x1, x2, ..., xℓ} các vector trong không gian tích vô hướng X, ma trận G kích thước ℓ  ℓ với Gij =  xi.xj được gọi là ma trận GRAM. Đặc điểm quan trọng của ma trận Gram là: các dữ liệu đầu vào cho các chương trình tổng hợp hoặc khái quát hoàn toàn có thể biểu diễn thông qua ma trận GRAM. 1.5. Khoảng cách giữa các siêu phẳng • Khoảng cách của một mẫu (xi, yi) tới siêu phẳng (w, b) là: LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 9 i = yi(w.xi + b) với y{-1, +1}, khi i > 0 ta nói có một sự phân lớp đúng (xi, yi) . • Khoảng cách hình học là khoảng cách vuông góc của điểm đến siêu phẳng. • Khoảng cách của tập mẫu S là khoảng cách hình học lớn nhất trên tất cả các siêu phẳng. Một siêu phẳng nhận khoảng cách lớn nhất gọi là siêu phẳng khoảng cách lớn nhất. • Khoảng cách của S đạt giá trị nhỏ nhất bằng / w cho tất cả các mẫu trong S. • Ta sẽ tìm một siêu phẳng (wopt, bopt) với khoảng cách hình học lớn nhất và gọi đó là siêu phẳng có khoảng cách lớn nhất. Trong trường hợp mẫu học không phân tách tuyến tính ta sẽ đưa ra các biến “mềm” i. Cụ thể với mẫu (xi, yi) siêu phẳng (w, b) và khoảng cách đích , ta có: i = max(0,  - yi(w. xi + b). Nếu i >  thì xi bị phân lớp sai bởi siêu phẳng (w, b). + + + + + + + j - Xj+ - xi - + i +  - Hình 1.2. Các biến “mềm” LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 10 1.6. Tổng kết chương 1 Ba kiểu học chính dựa trên sự phân biệt kiểu đầu ra: • Học có thầy, • Học không có thầy, • Học tăng cường, Các kiểu khác nhau trong học không có thầy cũng được phân biệt bằng đầu ra của nó: • Phân lớp: đầu ra rời rạc • Nội suy: đầu ra giá trị thực • Ưu tiên: đầu ra có thứ tự LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 11 CHƯƠNG 2. KHÔNG GIAN ĐẶC TRƯNG 2.1. Đặt vấn đề Các ứng dụng phức tạp trong thế giới thực đòi hỏi phải biểu diễn không gian không chỉ bởi các hàm tuyến tính, do không thể diễn tả dưới dạng một tổ hợp tuyến tính của các thuộc tính đầu vào. Nhận xét này được đánh giá bởi Minsky và Papert năm 1960 khi xem xét mạng nơ ron perceptron và dẫn đến đề nghị xây dựng mạng nơ ron nhiều tầng. Cách biểu diễn qua hạt nhân sẽ được đề cập ở đây cho phép ánh xạ các thuộc tính đầu vào lên không gian đặc trưng nhiều chiều. Điều này sẽ làm tăng tốc độ tính toán, cho phép phối hợp các thuật toán học trên không gian đặc trưng và thiết kế hàm hạt nhân cho phù hợp với ứng dụng của người dùng. 2.2. Không gian đặc trưng Sự phức tạp của hàm mục tiêu dẫn đến quá trình học phụ thuộc vào cách nó được diễn tả. Khi diễn tả dữ liệu một cách phù hợp, vấn đề học sẽ trở nên dễ dàng. Vì vậy, một việc làm rất phổ biến trong học máy là chuyển đổi dữ liệu từ không gian đầu vào X sang không gian đặc trưng: x = (x1, x2 , ..., xn)  (x) = (1(x), ..., N(x)) trong đó n là số chiều của đầu vào (số thuộc tính) và N là số chiều của không gian đặc trưng. Dữ liệu sẽ được chuyển vào không gian đặc trưng với N > n. Không gian đặc trưng kí hiệu là F: F = {(x)| x X}. 2.3. Hàm hạt nhân 2.3.1. Khái niệm hàm hạt nhân Một hạt nhân là một hàm K sao cho mọi x, z  X ta có: LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 12 K(x, z) =  (x). (z), ở đây < . > là tích vô hướng trong không gian đặc trưng Ví dụ: Xét phép biến đối dữ liệu từ không gian đầu vào X = R 2 vào không gian đặc trưng F = R3 được cho bởi: : R2  R3  x = (x1, x2)  (x) = (1(x), 2(x), 3(x)) = x12 , 2x1 x2 , x22  Ánh xạ trên cũng có thể được lý giải như sau. Cho x = (x 1, x2) và z = (z1, z2) ta có: 2 x.z 2  2  2    xi zi   x1 z1  x2 z 2   i 1   x12 z12  2 x1 z1 x2 z 2  x22 z 22    x12 , 2 x1 x2 , x22 . z12 , 2 z1 z 2 , z 22    x . z  Khi đó ta lấy (x, z) =  (x). (z) = x. z2. Vì vậy ta không cần phải tính ánh xạ . 2.3.2. Máy học tuyến tính thông qua biểu diễn hàm hạt nhân Máy học không tuyến tính trên không gian đầu vào được xây dựng qua hai bước: trước tiên sử dụng một ánh xạ không tuyến tính để chuyển đổi dữ liệu vào không gian đặc trưng và sau đó sử dụng máy học phân lớp tuyến tính trong không gian đặc trưng. Máy học tuyến tính trong không gian đặc trưng tương ứng với hàm: N f ( x)   wii x   b i 1 Chúng ta không cần xác định tường minh trọng số w, khi triển khai tiếp bằng cách đưa vào vector w = i 1 i xi ta có:  LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 13  f ( x)   i yi  xi . x   b . i 1 Hơn nữa, cũng không cần xây dựng tường minh ánh xạ , nhờ sử dụng hàm hạt nhân nên:  f ( x)   i yi K ( xi , x)  b i 1 Đặt SV là tập các chỉ số i thoả mãn i  0 ta được: f ( x )    i yi  ( x i , x )  b iSV Các xi ứng với i  0 được gọi là các vectơ trợ giúp (Support vector), hàm phân lớp sẽ xác định duy nhất qua các vector này. 2.3.3. Các đặc trưng của xâu kí tự và văn bản Ký hiệu * biểu thị tập hợp của các xâu kí tự có độ dài hữu hạn sinh ra từ tập . Nếu  = {a, b, c} thì * = {, a, b, c, aa, ab, ba, bb, aaa, aab,...} trong đó  biểu thị xâu rỗng. Với s *, s biểu thị chiều dài xâu s (bằng số lượng kí tự trong xâu s). Ta quy định độ dài của xâu rỗng là 0. Giả sử u* và s *, ta nói u là xâu con của s nếu tồn tại các chỉ số i = (i1, i2,...,i|u|) với 1  i1 >r = stringkernel(‘abcaaab’, ‘bcaac’, [1 1 1]) r= 46 >> [r, K] = stringkernel(‘abcaaab’, ‘bcaac’, 0.9.^(2 * [1: 3])) r= 30.5315 K(:, :, 1) = empty b bc bca bcaa bcaac empty 1 1 1 1 1 1 a 1 1 1 1 1 1 ab 1 1 1 1 1 1 abc 1 1 1 1 1 1 abca 1 1 1 1 1 1 abcaa 1 1 1 1 1 1 abcaa 1 1 1 1 1 1 abcaaab 1 1 1 1 1 1 LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 17 K(:, :, 2)= 0 0 0 0 0 0 0 0 0 1 2 2 0 1 1 2 3 3 0 1 2 3 4 4 0 1 2 4 6 5 0 1 2 5 8 6 0 1 2 6 10 11 0 2 3 7 11 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 4 0 0 1 3 6 9 0 0 1 5 12 15 0 0 1 7 19 22 0 0 1 7 19 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 0 0 0 2 6 6 0 0 0 3 12 12 0 0 0 3 12 12 K(:, :, 3)= K(:, :, 4)= LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 18 2.3.5. Khoảng cách Levenstein Khoảng cách Levenstein (mang tên nhà khoa học người Nga Vladimir Levenstein) đánh giá độ tương tự giữa xâu nguồn s và xâu đích t được định nghĩa bằng số lượng các phép xoá, chèn và thay thế cần thiết để biến đổi s thành t. Ví dụ: • s là “test” và t là “test” thì d(s, t)=0 • s là “test” và t là “best” thì d(s, t)=1 Thuật toán tính khoảng cách Levenstein được sử dụng trong: • Kiểm tra đánh vần, • Nhận dạng tiếng nói, • Phân tích DNA, • Phát hiện gian lận. Thuật toán Levenstein: Sử dụng phương pháp quy hoạch động: 1. Đặt ns và nt tương ứng là độ dài của xâu s và t. Khởi tạo giá trị đầu của ma trận C có kích thước (ns +1)  (nt +1) bằng 0, đánh số chỉ số hàng của C từ 0 đến ns và chỉ số cột của C từ 0 đến nt, 2. Khởi tạo giá trị các phần tử cột đầu tiên với Ci, 0 = i, i = 0, 1, 2, …, ns, 3. Khởi tạo giá trị các phần tử dòng đầu tiên với C0,j = j, j = 0,1,2,…,nt, 4. Việc tính C[i, j] dựa vào công thức đệ quy sau: C[i,j] = min(C[i, j-1]+1, C[i-1, j], C[i-1, j-1] + T[i,j]), 0 nÕu si  t  j  1 nÕu si  t  j  trong đó: T i, j    5. Khoảng cách giữa s và t là d(s, t) = Cns 1,nt 1 . LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin 19 2.3.6. Hàm hạt nhân dựa trên khoảng cách Hàm hạt nhân dựa trên khoảng cách giữa hai xâu thường được cho dưới dạng tổng quát như sau: K(xc, x) = ((x - xc)’D-1(x - xc)) trong đó  là hàm, xc là tâm và D ma trận sao cho (x - xc)’D-1(x - xc) là độ đo khoảng cách giữa đầu vào x và tâm xc. Khi xét khoảng cách Euclidean, ta có D = r2I, trong đó I là ma trận đơn vị. Khi đó công thức hàm hạt nhân trở thành:  x  xc ' x  xc    K(xc, x) =   2  r   Một số hàm  phổ biến thường được dùng: • Gaussian: (z) = exp(-z) • Căn thức: (z) = (1+z)-1/2 • Cauchy: (z) = (1 +z)-1 • Levenstein: (z) = exp(-z/) trong đó  >0. 2.3.7. Một số hàm hạt nhân • K(x, z) = x . z. • K(x, z) = (1 + x . z)d, với d là tham số do người dùng định nghĩa. 1  x.z • K(x, z) = , với d là tham số do người dùng định nghĩa, 1  x.z d -1< x.z <1. • K(x, z) = 1 , trong đó -1 < x . z <1. 1  x.z • K(x, z) = exp(- x  z ), với  do người dùng định nghĩa. 2 • K(x, z) = 1 . 1  expv x.z   c LuËn v¨n Th¹c sÜ C«ng nghÖ Th«ng tin