Luận văn Nghiên cứu mô hình Relevance Vector Machine (RVM) áp dụng giải một số bài toán thực tế
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
Lê Quốc Vương
NGHIÊN CỨU MÔ HÌNH
RELEVANCE VECTOR MACHINE (RVM)
ÁP DỤNG GIẢI MỘT SỐ BÀI TOÁN THỰC TẾ
LUẬN VĂN THẠC SĨ MÁY TÍNH
Thành phố Hồ Chí Minh - 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
Lê Quốc Vương
NGHIÊN CỨU MÔ HÌNH
RELEVANCE VECTOR MACHINE (RVM)
ÁP DỤNG GIẢI MỘT SỐ BÀI TOÁN THỰC TẾ
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. HUỲNH VĂN ĐỨC
Thành phố Hồ Chí Minh - 2018
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của bản thân tôi dưới sự hướng dẫn
khoa học của TS. Huỳnh Văn Đức. Các thông tin và số liệu của luận văn có nguồn gốc
rõ ràng, cụ thể, có trích dẫn theo đúng quy định.
Kết quả nghiên cứu của luận văn hoàn toàn trung thực, khách quan và chưa từng
được sử dụng hay công bố trong bất kỳ công trình nghiên cứu nào khác.
TP. Hồ Chí Minh, tháng 03 năm 2018.
Học viên
Lê Quốc Vương
LỜI CẢM ƠN
Lời đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc
nhất đến thầy Huỳnh Văn Đức - giảng viên hướng dẫn luận văn. Trong
quá trình tìm hiểu và nghiên cứu đề tài, tôi đã gặp rất nhiều khó khăn,
nhưng nhờ Thầy luôn động viên, hết lòng hướng dẫn và giúp đỡ nên
tôi đã hoàn thành luận văn này.
Tôi cũng xin gửi lời cảm ơn chân thành đến quý Thầy/Cô Trường
Đại học Sư phạm Thành phố Hồ Chí Minh đã tận tâm dạy dỗ và truyền
đạt những kiến thức quý báu trong quá trình học tập. Đồng thời, tôi
cũng xin cảm ơn Ban chủ nhiệm khoa Công nghệ thông tin và phòng
Sau đại học đã hỗ trợ và tạo điều kiện cho tôi trong thời gian qua.
Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đến gia đình đã luôn
động viên và giúp đỡ tôi trong suốt quá trình học tập cũng như thực
hiện luận văn.
TP. Hồ Chí Minh, tháng 03 năm 2018.
Học viên thực hiện
Lê Quốc Vương
MỤC LỤC
Trang
Trang phụ bìa
Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục thuật ngữ và viết tắt
Danh mục các bảng
Danh mục các hình vẽ
Chương 1. MỞ ĐẦU......................................................................................................1
1.1. Đặt vấn đề ............................................................................................................1
1.2. Mục tiêu luận văn.................................................................................................3
1.3. Nội dung thực hiện...............................................................................................3
1.4. Bố cục luận văn....................................................................................................4
Chương 2. CƠ SỞ LÝ THUYẾT .................................................................................5
2.1. Mô hình Support Vector Machine (SVM) ...........................................................5
2.1.1. Ý tưởng của SVM.........................................................................................5
2.1.2. SVM đối với bài toán phân loại....................................................................6
2.1.2.2. SVM với lề mềm (soft margin) .............................................................9
2.1.3. Hàm hạt nhân (kernel function)..................................................................11
2.1.4. SVM đối với bài toán hồi quy ....................................................................12
2.2.1. RVM đối với bài toán hồi quy....................................................................16
2.2.2. RVM đối với bài toán phân loại .................................................................18
2.2.3. Một số hàm cơ sở (basis functions)............................................................20
2.3.4. Trung bình di động (Moving average)........................................................24
2.3.7. Phương pháp phân rã STL..........................................................................29
2.4. Chuỗi ARIMA....................................................................................................30
2.4.1. Nhiễu trắng (white noise) ...........................................................................30
2.4.3. Tính dừng (stationarity) của chuỗi thời gian ..............................................31
2.4.4. Mô hình ARIMA ........................................................................................31
2.4.6. Phương pháp luận Box - Jenkins ................................................................34
3.1.1. Hạn chế của trung bình di động..................................................................36
3.2. Đề xuất thuật toán phân rã chuỗi thời gian ........................................................38
3.2.1. Ý tưởng .......................................................................................................38
3.2.2. Thuật toán ...................................................................................................39
Chương 4. THỰC NGHIỆM ......................................................................................48
4.1. Quy trình thực nghiệm .......................................................................................48
4.1.1. Dữ liệu ........................................................................................................48
4.2. Kết quả thực nghiệm và đánh giá.......................................................................50
4.2.1. Thuật toán phân rã chuỗi thời gian.............................................................51
4.2.2. Dự báo của thuật toán phân rã ....................................................................54
Chương 5. TỔNG KẾT...............................................................................................61
5.1. Kết luận ..............................................................................................................61
DANH MỤC THUẬT NGỮ VÀ VIẾT TẮT
ACF
Auto Correlation Function
Auto Regressive
AR
ARMA
ARIMA
KKT
Auto Regressive Moving Average
Auto Regressive Integrated Moving Average
Karush Kuhn Tucker
RVM
MA
Relevance Vector Machine
Moving Average
PACF
Partial Auto Correlation Function
SARIMA
SVM
Seasonal Auto Regressive Integrated Moving Average
Support Vector Machine
DANH MỤC CÁC BẢNG
Bảng 3.1. Hệ bất đối xứng của 3x3 MA........................................................................37
Bảng 3.3. Sai số của thuật toán 1...................................................................................40
Bảng 3.4. Sai số của thuật toán 2...................................................................................43
Bảng 3.5. Sai số của thuật toán 3...................................................................................44
Bảng 3.6. Sai số của thuật toán 4...................................................................................47
Bảng 4.1. Số lượng mẫu của dữ liệu .............................................................................49
Bảng 4.2. Kết quả sai số của thuật toán phân rã 03 dữ liệu đầu....................................51
DANH MỤC CÁC HÌNH VẼ
Hình 2.2. Mô tả lề của siêu phẳng...................................................................................6
Hình 2.3. Mô tả biến nới lỏng ξ.......................................................................................9
Hình 2.4. Mô tả ε - tube.................................................................................................13
Hình 2.5. GDP (USD) của Kenya từ năm 1960 ............................................................21
Hình 2.6. Tỷ lệ thất nghiệp của lao động Mỹ................................................................21
Hình 2.8. Biểu đồ phương pháp luận Box – Jenkins.....................................................35
Hình 3.1. Biểu đồ mô hình RVM/SVM thuật toán 1 ....................................................40
Hình 3.3. Biểu đồ của học thuật toán 2 .........................................................................42
Hình 3.4. Biểu đồ thành phần sai số của mô hình SVM ...............................................43
Hình 3.5. Biểu đồ của thuật toán 3................................................................................44
Hình 3.6. Biểu đồ thành phần sai số của mô hình SVM ...............................................45
Hình 3.7. Biểu đồ của thuật toán 4................................................................................47
1
Chương 1. MỞ ĐẦU
Chương 1 sẽ trình bày một số vấn đề đã thúc đẩy việc tìm hiểu và
tiến hành nghiên cứu bài toán chuỗi thời gian. Tiếp theo đó, chương
mở đầu này cũng sẽ giới thiệu những mục tiêu, nội dung nghiên cứu và
bố cục trình bày của luận văn.
1.1. Đặt vấn đề
Thông thường, có một độ lệch thời gian giữa nhận thức của con người về thời điểm
một sự kiện sắp xảy ra hoặc nhu cầu của con người và sự kiện đó thực sự xuất hiện,
khoảng thời gian này gọi thời gian trễ (time lag) và nó là lý do để chúng ta lên kế hoạch
và dự báo. Nếu thời gian trễ rất nhỏ hoặc bằng không thì không cần lên kế hoạch, nếu
thời gian trễ lớn và kết quả của sự kiện đó là điều kiện để xác định các nhân tố khác thì
việc lên kế hoạch đóng vai trò quan trọng. Trong trường hợp này, dự báo là cần thiết để
xác định thời điểm một sự kiện xảy ra hoặc nhu cầu phát sinh để chúng ta có những hành
động thích hợp [19].
Luận văn giới thiệu hai mô hình chính để dự báo: mô hình chuỗi thời gian (time
định rằng biến dự báo có quan hệ với một hay nhiều biến độc lập (biến giải thích), ví
dụ:
GNP = f(chính sách tiền tệ và tài khóa, lạm phát,
chi tiêu vốn, nhập khẩu, xuất khẩu và sai số).
Trong đó: GNP (Gross National Product) là tổng sản phẩm quốc gia.
Khác với mô hình giải thích, mô hình chuỗi thời gian dự báo tương lai dựa trên các
giá trị và sai số trong quá khứ. Mục tiêu của mô hình chuỗi thời gian là xây dựng mô
hình dữ liệu trong lịch sử và từ đó dự báo giá trị trong tương lai.
GNPt+1 = f(GNPt, GNPt-1, GNPt-2, GNPt-3, …, nhiễu).
2
Trong đó: t là tháng hiện tại,
t+1 tháng kế tiếp, t-1 tháng trước, t-2 hai tháng trước, …
Cả hai mô hình giải thích và chuỗi thời gian đều có những thuận lợi riêng trong
những tình huống nhất định. Mô hình chuỗi thời gian thường được sử dụng dễ dàng hơn
Luận văn giới thiệu các hướng tiếp cận mô hình chuỗi thời gian dưới đây:
- Sử dụng phương pháp phân rã chuỗi thời gian thành các thành phần T (xu thế), S
(mùa), E (sai số). Đây là hướng tiếp cận mà luận văn quan tâm;
- Hướng tiếp cận phổ biến sử dụng mô hình tự hồi quy (Auto Regressive Model –
AR);
- Hướng tiếp cận phổ biến khác sử dụng mô hình trung bình di động (Moving
Average Model – MA);
- Hướng tiếp cận Box – Jenkins là kết hợp hai mô hình AR và MA.
Thời gian gần đây, phương pháp phân rã chuỗi thời gian cũng được các nhà nghiên
Ngoài ra, sử dụng SVM và RVM trong dự báo chuỗi thời gian là một hướng tiếp
cận khác cũng đang được các nhà nghiên cứu quan tâm. Mô hình SVM dựa trên lý thuyết
Cả hai mô hình này sau khi đề xuất được phổ biến rộng rãi. Khác với SVM, mô hình
RVM huấn luyện dựa trên lý thuyết Bayes và dự báo dựa trên phân phối xác suất còn
Hướng tiếp cận SVM đối với chuỗi thời gian đã có các công trình nghiên cứu
nhưng kết quả rất khả quan có nhiều tiềm năng, cần có nhiều nghiên cứu về hướng tiếp
khác.
3
RVM được kế thừa từ SVM, nên thuận của cả RVM/SVM là khả năng học phi
dừng của chuỗi thời gian giống như các hướng tiếp cận cổ điển.
Những điều nêu trên đã thúc đẩy luận văn nghiên cứu ứng dụng mô hình
RVM/SVM vào bài toán dự báo chuỗi thời gian bằng hướng tiếp cận phân rã chuỗi thời
gian về kinh tế.
Để đánh giá phương pháp phân rã chuỗi thời gian, luận văn đánh giá mô hình phân
rã và đánh giá kết quả của dự báo. Đánh giá mô hình phân rã, luận văn đánh giá thành
phần sai số là chuỗi gần với nhiễu trắng và dựa vào tiêu chí trung bình (mean), độ lệch
chuẩn (standard deviation). Đánh giá kết quả dự báo của mô hình phân rã dựa trên tiêu
chí Root Mean Square Error (RMSE) độ lệch của chuỗi dữ liệu quan sát và kết quả dự
1.2. Mục tiêu luận văn
- Nghiên cứu mô hình RVM, sau đó áp dụng mô hình RVM để phân rã chuỗi thời
gian lĩnh vực kinh tế.
- Dự báo chuỗi thời gian kinh tế dựa trên mô hình đã phân rã.
1.3. Nội dung thực hiện
Nhằm đạt được những mục tiêu nêu trên, về mặt lý thuyết luận văn tiến hành
nghiên cứu những công trình liên quan chuỗi thời gian, mô hình RVM/SVM. Những
công việc cụ thể bao gồm:
. Tìm hiểu mô hình RVM/SVM và các ứng dụng.
. Tìm hiểu chuỗi thời gian và chuỗi ARIMA.
. Các hướng tiếp cận giải bài toán chuỗi thời gian.
. Tìm cách đưa mô hình RVM/SVM để giải bài toán chuỗi thời gian, đề xuất
thuật toán giải bài toán chuỗi thời gian.
Về mặt thực nghiệm, các thuật toán do luận văn đề xuất sẽ được thực nghiệm trên
minh họa và dữ liệu chuỗi thời gian của thư viện ngôn ngữ R.
4
Quá trình thử nghiệm của luận văn sẽ được tiến hành các bước chính sau:
. Chuẩn bị dữ liệu
. Xây dựng quy trình thử nghiệm
. Tiến hành thử nghiệm
. Phân tích và đánh giá kết quả.
1.4. Bố cục luận văn
Bố cục luận văn được tổ chức thành năm chương như sau:
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.
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.
2.1. 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.
2.1.1. Ý 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
Biến đổi dữ liệu
vào không gian
đặc trưng
X2
Z2
푧 = 횽(푥)
X1
Z1
Dữ liệu tách được tuyến tính
trong không gian đặc trưng
Dữ liệu không tách
được tuyến tính
Hình 2.1. Mô tả dữ liệu tách được tuyến tính trong không gian đặc trưng Z
6
2.1.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
{(
)
(
)}
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.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
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
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.
푇
( )
Siêu phẳng (H) có dạng: 푦 푥 = 푤 Φ(푥) + 푏
(2.1.1)
trong đó: Φ(푥) là không gian đặc trưng, 푤 và 푏 là tham số.
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:
푡푖(푤푇Φ(푥푖) + 푏)
(2.1.2)
max min
푤,푏 1≤푖≤푁
‖ ‖
푤
푇
(
( )
)
Điều kiện: 푡푖 푤 Φ 푥푖 + 푏 ≥ 0, ∀푖 = 1, … , 푁
2.1.2.1. 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:
푇
(
( ) )
푡푖 푤 Φ 푥푖 + 푏
(2.1.3)
max min
푤,푏 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.1.3) trở thành:
1
‖ ‖2
푎푟푔 푚푖푛 ( 푤 )
푤,푏
2
푇
(
( )
)
Ràng buộc: 1 − 푡푖 푤 Φ 푥 + 푏 ≤ 0, ∀푖 = 1, … , 푁
Dùng điều kiện KKT1 để xác định các quan hệ giữa 풘, 풃, 흀:
Hàm Lagrange:
푁
1
푇
(
)
‖ ‖2
[
(
( )
)]
(2.1.4)
퐿 푤, 푏, 휆 =
푤
+ ∑ 휆푖 1 − 푡푖 푤 ϕ 푥푖 + 푏
2
푖=1
푇
(
)
휆푖 ≥ 0, 휆 = 휆1, … , 휆푁
Hàm đối ngẫu:
( )
(
)
푔 휆 = min 퐿 푤, 푏, 휆 với 휆푖 ≥ 0
푤,푏
1 KKT là điều kiện tối ưu của bài toán tối ưu có ràng buộc được đặt tên theo tên của 03 tác giả: Karush, 1939;
Kuhn và Tucker, 1951 (Chi tiết xem [4]).
8
(
)
푁
(2.1.5)
(2.1.6)
푤 = ∑ 휆푖 푡푖Φ(푥푖)
푖=1
푁
0 = ∑ 휆푖 푡푖
푖=1
( )
Thế (2.1.5) và (2.1.6) vào (2.1.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.1.1). Thế (2.1.5) vào biểu thức này ta thu được:
푁
( )
(
)
(2.1.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.1.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
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,
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ố
( )
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
2.1.2.2. 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ì
휉3
푥
휉2
휉1
푥
푥2
Hình 2.3. Mô tả biến nới lỏng 휉
10
Bài toán tối ưu SVM với lề mềm:
푁
1
‖ ‖2
(2.1.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.1.9)
퐿 푤, 푏, 휉, 휆, 휇 =
푤
2
푖=1
푖=1
푖=1
Trong đó 휆푖và 휇푖 là các nhân tử Lagrange và:
( )
(
( )
)
(2.1.10)
(2.1.11)
휆푖 ≥ 0, 푡푖푦 푥푖 ≥ 1 − 휉푖, 휆푖 푡푖푦 푥푖 − 1 + 휉푖 = 0
휇푖 ≥ 0, 휉푖 ≥ 0, 휇푖휉푖 = 0
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
푁
푁
( )
( )
(2.1.12)
0 = ∇푤퐿 = 푤 − ∑ 푡푖 휆푖Φ 푥푖 ⇒ 푤 = ∑ 푡푖 휆푖Φ 푥푖
푖=1
푖=1
푁
(2.1.13)
(2.1.14)
0 = ∇푤퐿 = ∑ 푡푖 휆푖
푖=1
0 = ∇휉 퐿 = 퐶 − 휆푖 − 휇푖 ⟹ 휆푖 = 퐶 − 휇푖, ∀푖 = 1, … , 푁
푖
Tải về để xem bản đầy đủ
76 trang
12900
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Nghiên cứu mô hình Relevance Vector Machine (RVM) áp dụng giải một số bài toán thực tế", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_nghien_cuu_mo_hinh_relevance_vector_machine_rvm_ap.pdf
