Chương 1 giới thiệu tổng quan về bài toán chuỗi thời gian, nêu lên mục tiêu, nội dung nghiên cứu và bố cục luận văn. Chương 2 trình bày cơ sở lý thuyết gồm: mô hình RVM/SVM, chuỗi thời gian và chuỗi ARIMA. Chương 3 phương pháp đề xuất: nêu hạn chế của trung bình di động và đề xuất hướng khắc phục, ứng dụng của mô hình RVM/SVM vào phương pháp phân rã chuỗi thời gian và đề xuất thuật toán phân rã chuỗi thời gian. Chương 4 thực nghiệm: nêu quy trình thực nghiệm và phân tích đánh giá kết quả thực nghiệm.
Chương 5 là phần tổng kết và phát thảo một số hướng phát triển trong tương lai của luận văn. Luan van 5 Chương 2. CƠ SỞ LÝ THUYẾT Chương 2 sẽ trình bày cở sở lý thuyết gồm: mô hình SVM, mô hình RVM, chuỗi thời gian tổng quát và chuỗi ARIMA. Mô hình Support Vector Machine (SVM) SVM là một trong phương pháp tiêu biểu nhất của nhánh phương pháp kernel.
SVM được sử dụng rất phổ biến áp dụng được cho bài toán phân loại, bài toán hồi quy và bài toán dò bất thường. Ý tưởng của SVM Trong không gian dữ liệu 𝒟 ban đầu không tách được, sử dụng một ánh xạ Φ để biến không gian dữ liệu 𝒟 ∈ ℝ𝑑 ban đầu (input space) vào không gian đặc trưng ℋ (feature space). Không gian đặc trưng có số chiều lớn hơn nhiều so với không gian dữ liệu ban đầu khả năng dữ liệu tách được tuyến tính, khi ánh xạ ngược trở lại không gian dữ liệu ban đầu có thể tạo ra các biên quyết định phi tuyến (Hình 2. X2 Biến đổi dữ liệu Z2 vào không gian đặc trưng 𝑧 = 𝚽(𝑥) X1 Dữ liệu tách được tuyến tính Z1 Dữ liệu không tách được tuyến tính trong không gian đặc trưng Hình 2.
Mô tả dữ liệu tách được tuyến tính trong không gian đặc trưng Z Luan van 6 2. SVM đối với bài toán phân loại Phương pháp này áp dụng được cho bài toán phân loại hai lớp. Nếu muốn áp dụng cho bài toán nhiều lớp, chúng ta cần sử dụng phiên bản SVM mở rộng hoặc kết hợp nhiều bài toán phân loại hai lớp lại với nhau [1]. Cho trước tập dữ liệu huấn luyện 𝒟 = {(𝑥1 , 𝑡1 ), … , (𝑥𝑁 , 𝑡𝑁 )} với N là số điểm dữ liệu, 𝑥𝑖 ∈ ℝ𝑑 với d là số chiều của dữ liệu, 𝑦𝑖 là nhãn của điểm dữ liệu và 𝑡𝑖 ∈ {−1, +1}.
Khi đó, tập huấn luyện trong ℋ có dạng 𝒟Φ = {(Φ(𝑥1 ), 𝑡1 ), … , (Φ(𝑥𝑁 ), 𝑡𝑁 )}. Giả sử tập huấn luyện 𝒟Φ tách được tuyến tính (linearly separate) trong không gian đặc trưng. Cần tìm siêu phẳng tối ưu để tách tập huấn luyện 𝒟Φ trong không gian đặc trưng. Support vectors lề Hình 2.
Mô tả lề của siêu phẳng Có nhiều siêu phẳng tách được 𝒟Φ , vậy siêu phẳng nào là siêu phẳng tối ưu? Trong SVM đưa ra khái niệm lề của siêu phẳng (Hình 2.2), được hiểu là khoảng cách từ điểm gần nhất của tập dữ liệu 𝒟Φ đến siêu phẳng. Vapnik và cộng sự đã sử dụng lý thuyết học thống kê (statistical learning) để chứng minh rằng siêu phẳng tối ưu là siêu phẳng có lề cực đại (maximum margin) [1] và [21]. Từ kết quả này dẫn đến bài toán SVM chính là bài toán tìm siêu phẳng (H) tách được tập huấn luyện 𝒟Φ mà có lề cực đại.1) trong đó: Φ(𝑥) là không gian đặc trưng, 𝑤 và 𝑏 là tham số. Luan van 7 Như vậy, khoảng cách tập 𝒟Φ tới siêu phẳng (H) có thể được định nghĩa: |𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏| 𝑑 (𝒟Φ , 𝐻) = min 1≤𝑖≤𝑁 ‖𝑤 ‖ Khi đó, bài toán SVM là bài toán học siêu phẳng tối ưu: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) max min (2.
SVM với lề cứng (hard margin) Theo phân tích ở trên, để tìm siêu phẳng có lề cực đại chúng ta cần giải bài toán tối ưu: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) max min (2.3) 𝑤,𝑏 1≤𝑖≤𝑁 ‖𝑤 ‖ Ràng buộc: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) ≥ 0, ∀𝑖 = 1, … , 𝑁 Nếu thay đổi 𝑤 → 𝑘𝑤 và b→ 𝑘𝑏 với 𝑘 là hằng số dương, thì khoảng cách từ một điểm bất kỳ 𝑥𝑖 đến siêu phẳng sẽ không đổi. Chúng ta có thể giả sử rằng: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) = 1 (2. Luan van 8 Tính đạo hàm 𝐿(𝑤, 𝑏, 𝜆) theo 𝑤 và 𝑏 và cho bằng không [4], ta thu được: 𝑁 𝑤 = ∑ 𝜆𝑖 𝑡𝑖 Φ(𝑥𝑖 ) (2.4) ta thu được 𝑔(𝜆) : 𝑁 𝑁 𝑁 1 𝑔(𝜆) = ∑ 𝜆𝑖 − ∑ ∑ 𝜆𝑖 𝜆𝑗 𝑡𝑖 𝑡𝑗 𝑘(𝑥𝑖 , 𝑥𝑗 ) 2 𝑖=1 𝑖=1 𝑗=1 Với 𝑘(𝑥𝑖 , 𝑥𝑗 ) = Φ𝑇 (𝑥𝑖 )Φ(𝑥𝑗 ) gọi là hàm hạt nhân. Bài toán đối ngẫu: 𝑎𝑔𝑟 max 𝑔(𝜆) 𝜆 Ràng buộc: 𝜆𝑖 ≥ 0 ∑𝑁 𝑖=1 𝜆𝑖 𝑡𝑖 = 0 Để phân lớp cho các điểm dữ liệu mới, ta cần xác định dấu của 𝑦(𝑥) được định nghĩa bởi công thức (2.5) vào biểu thức này ta thu được: 𝑁 𝑦(𝑥 ) = ∑ 𝜆𝑖 𝑡𝑖 𝑘(𝑥, 𝑥𝑖 ) + 𝑏 (2.7) 𝑖=1 Ta thấy các ràng buộc tối ưu thỏa hệ điều kiện KKT: 1 − 𝑡𝑖 (𝑤 𝑇 ϕ(𝑥𝑖 ) + 𝑏) ≤ 0, ∀𝑖 = 1, … , 𝑁 𝜆𝑖 ≥ 0, ∀𝑖 = 1, … , 𝑁 𝜆𝑖 (1 − 𝑡𝑖 (𝑤 𝑇 ϕ(𝑥𝑖 ) + 𝑏)) = 0, ∀𝑖 = 1, … , 𝑁 Thế thì tất cả điểm dữ liệu hoặc 𝜆𝑖 = 0, 𝑡𝑖 𝑦(𝑥𝑖 ) = 1.
Những điểm dữ liệu mà 𝜆𝑖 = 0 thì không thể hiện trong tổng (2.7) nên nó không đóng vai trò trong việc dự đoán dữ liệu mới. Những điểm còn lại gọi là vector hỗ trợ (support vector) bởi vì thỏa mãn 𝑡𝑖 𝑦(𝑥𝑖 ) = 1, những điểm dữ liệu này nằm trên lề cực đại của siêu phẳng trong không gian đặc trưng, các điểm khoanh tròn nằm trên đường màu xanh của Hình 2. Tính chất này là trọng tâm trong ứng dụng thực tế của SVM. Một mô hình huấn luyện, Luan van 9 một tỷ lệ đáng kể các điểm dữ liệu có thể bị loại bỏ và chỉ giữ lại các vector hỗ trợ (số lượng ít) [4].
Các vector hỗ trợ 𝑥𝑖 thỏa 𝑡𝑖 𝑦(𝑥𝑖 ) = 1 và điều kiện KKT, khi 𝜆𝑖 ≠ 0 thu được b. Để dự đoán một điểm x thuộc lớp nào, ta xác định dấu của biểu thức: 𝑁 𝑤 𝑇 Φ(𝑥) + b = ∑ 𝜆𝑖 𝑡𝑖 Φ(𝑥𝑖 )𝑇 Φ(𝑥) + 𝑏 𝑖=1 Với giả thiết tập huấn luyện tách được tuyến tính trong không gian đặc trưng Φ(𝑥), mô hình SVM với lề cứng sẽ cho ra kết quả tách chính xác trên không gian ban đầu (input space), tương ứng biên quyết định là phi tuyến. Tuy nhiên trong thực tế, các lớp dữ liệu có phân bố chồng lên nhau, trường hợp này SVM (với lề cứng) có thể không giải được hoặc kết quả không tốt [4]. Do đó, người ta đã cải tiến SVM với lề mềm.
SVM với lề mềm (soft margin) Để cải tiến SVM với lề cứng, người ta đưa thêm biến nới lỏng (slack) 𝜉𝑖 ≥ 0 tương ứng với mỗi điểm dữ liệu. Những điểm dữ liệu phân lớp đúng nằm về hai phía của biên thì 𝜉𝑖 = 0, ngược lại thì 𝜉𝑖 = |𝑡𝑖 − 𝑦(𝑥𝑖 )|. Nghĩa là những điểm nằm trên lề và ở bên phía phân lớp đúng của siêu phẳng thì 0 < 𝜉𝑖 ≤ 1, như 𝑥2 ; những điểm phân lớp sai thì 𝜉𝑖 > 1, như 𝑥1 , 𝑥3 (Hình 2. Mô tả biến nới lỏng 𝜉 Luan van 10 Bài toán tối ưu SVM với lề mềm: 𝑁 1 𝑎𝑟𝑔 𝑚𝑖𝑛 ( ‖𝑤‖2 + 𝐶 ∑ 𝜉𝑖 ) (2.8) 𝑤,𝑏,𝜉 2 𝑖=1 Ràng buộc: 1 − 𝜉𝑖 − 𝑡𝑖 (𝑤 𝑇 ϕ(𝑥𝑖 ) + 𝑏) ≤ 0, ∀𝑖 = 1, … , 𝑁 −𝜉𝑖 ≤ 0, ∀𝑖 = 1, … , 𝑁 Với điều kiện 𝐶 ≥ 0 gọi là tham số bù trừ (trade – off parameter), cân bằng giữa sự chấp nhận hy sinh các điểm lỗi và lề.
Dùng điều kiện KKT để xác định các quan hệ giữa 𝒘, 𝒃, 𝝀: Hàm Lagrange tương ứng của bài toán: 𝑁 𝑁 𝑁 1 𝐿(𝑤, 𝑏, 𝜉, 𝜆, 𝜇) = ‖𝑤‖2 + 𝐶 ∑ 𝜉𝑖 + ∑ 𝜆𝑖 (1 − 𝜉𝑖 − 𝑡𝑖 𝑦(𝑥𝑖 )) − ∑ 𝜇𝑖 𝜉𝑖 (2.9) 2 𝑖=1 𝑖=1 𝑖=1 Trong đó 𝜆𝑖 và 𝜇𝑖 là các nhân tử Lagrange và: 𝜆𝑖 ≥ 0, 𝑡𝑖 𝑦(𝑥𝑖 ) ≥ 1 − 𝜉𝑖 , 𝜆𝑖 (𝑡𝑖 𝑦(𝑥𝑖 ) − 1 + 𝜉𝑖 ) = 0 (2.11) là các điều kiện KKT. Hàm đối ngẫu: 𝑔(𝜆, 𝜇) = min 𝐿(𝑤, 𝑏, 𝜉, 𝜆, 𝜇) 𝑤,𝑏 Thiết lập đạo hàm của hàm Lagrange theo các biến chính 𝑤, 𝑏, 𝜉 và cho bằng không [4], ta thu được: 𝑁 𝑁 0 = ∇𝑤 𝐿 = 𝑤 − ∑ 𝑡𝑖 𝜆𝑖 Φ(𝑥𝑖 ) ⇒ 𝑤 = ∑ 𝑡𝑖 𝜆𝑖 Φ(𝑥𝑖 ) (2.14) Luan van 11 Thế (2.9) ta thu được hàm đối ngẫu: 𝑁 𝑁 𝑁 1 𝑔(𝜆, 𝜇) = ∑ 𝜆𝑖 − ∑ ∑ 𝜆𝑖 𝜆𝑗 𝑡𝑖 𝑡𝑗 𝑘(𝑥𝑖 , 𝑥𝑗 ) (2.15) không phụ thuộc vào 𝜇𝑖 , nên bài toán đối ngẫu có dạng: 𝑎𝑔𝑟 max 𝑔(𝜆) 𝜆 Ràng buộc: 0 ≤ 𝜆𝑖 ≤ 𝐶, ∀𝑖 = 1, … , 𝑁 ∑𝑁 𝑖=1 𝜆𝑖 𝑡𝑖 = 0 Điều kiện KKT (2.11) giúp ta suy ra được tính chất: 𝜆𝑖 = 0: 𝜇𝑖 = 𝐶 ⟹ 𝜉𝑖 = 0 ⟹ 𝑡𝑖 𝑦(𝑥𝑖 ) ≥ 1, đây là trường hợp các vectơ 𝑥𝑖 nằm ngoài lề và được phân lớp đúng. 0 < 𝜆𝑖 < 𝐶: 𝜇𝑖 > 0 ⟹ 𝜉𝑖 = 0 ⟹ 𝑡𝑖 𝑦(𝑥𝑖 ) = 1, đây là trường hợp các vectơ 𝑥𝑖 nằm trên lề (gọi là vectơ hỗ trợ) và được phân lớp đúng. 𝜆𝑖 = 𝐶 ⟹ 𝑡𝑖 𝑦(𝑥𝑖 ) = 1 − 𝜉𝑖 , đây là trường hợp các vectơ 𝑥𝑖 có thể được phân lớp đúng nếu 𝜉𝑖 ≤ 1 hoặc sai nếu 𝜉𝑖 > 1.1) ta dựa vào các vectơ hỗ trợ, là trường hợp 0 < 𝜆𝑖 < 𝐶 có 𝜉𝑖 = 0.
Để dự đoán một điểm x thuộc lớp nào, ta xác định dấu của biểu thức: 𝑁 𝑤 𝑇 Φ(𝑥) + b = ∑ 𝜆𝑖 𝑡𝑖 Φ(𝑥𝑖 )𝑇 Φ(𝑥) + 𝑏 𝑖=1 2. Hàm hạt nhân (kernel function) Hàm hạt nhân được định nghĩa [4]: 𝑘(𝑥, 𝑥 ′ ) = Φ𝑇 (𝑥)Φ(𝑥), trong đó Φ là một ánh xạ không gian dữ liệu vào không gian đặc trưng. Trường hợp đơn giản nhất Φ(𝑥 ) = 𝑥 thì 𝑘(𝑥, 𝑥 ′ ) = 𝑥 𝑇 𝑥 ′ đây là trường hợp tuyến tính.