Phương pháp tối ưu hàm kernel của thuật toán MPM

hình
khác nhau ñược ñưa ra trong phương pháp trích chọn. ðiển hình là hai mô hình: Filter và
Wrapper.
Hình 2.2. Mô hình Filter
1 2
Filter
3 A
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
Hình 2.3. Mô hình Wrapper
Giải thích hình vẽ:
A: Tập ñặc trưng ñầu vào.
1: Bộ sinh tập con (Feature Subset Generator).
2: Bộ ñánh giá (Feature Subset Evaluator).
3: Các thuật toán học máy (Followed Machine learning Algorithm)
4: Thuật toán học máy ñiều khiển (Central Machine learning Algorithm).
Mô hình Filter ñánh giá mỗi cá thể bằng một vài tiêu chuẩn, rồi chọn ra tập con các
thuộc tính có ñộ ñánh giá cao nhất. Nhìn chung, Filter coi tiến trình của trích chọn thuộc
tính như tiến trình thực thi trước, sau ñó mới sử dụng thuật toán ñể phân lớp.
Wrapper sử dụng một thuật toán tìm kiếm ñể ñánh giá tập con các thuộc tính coi như
là một nhóm hơn là một cá thể riêng lẻ. Mô hình Wrapper ñược ñặt vào trung tâm của
một thuật toán máy học cụ thể. Nó ñánh giá ñộ tốt của những tập con ñặc trưng tùy theo
ñộ chính xác học của tập con, ñiều này xác ñịnh thông qua tỷ lệ. Những thuật toán tìm
kiếm cũng sử dụng hàm ñánh giá kinh nghiệm (heuristics) ñể hướng dẫn việc tìm kiếm
tập trung vào các ñối tượng có triển vọng.
1
2
4
Wrapper Model
3
A
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
2.2.2. ðánh giá hai mô hình Filter và Wrapper
2.2.2.1. Filter
• Ưu ñiểm:
- Không có xử lý học máy trong quá trình lựa chọn các ñặc trưng.
- Dễ dàng nhận diện và thời gian tiêu thụ ít hơn mô hình Wrapper.
• Nhược ñiểm:
- Hiệu suất sản sinh các tập con ñặc trưng là không ñảm bảo vì nó thường ñánh
giá một tập con ñặc trưng chỉ dựa trên ñặc trưng nhỏ thiên về nguyên lý mà
không tính tới ñộ chính xác của kết quả học máy.
- Kết quả thu ñược bị giảm sút về ñộ chính xác học ở những giai ñoạn sau vì các
hàm ñánh giá hiện thời ñược sử dụng thường thiên về giá trị ở một vài phạm vi,
do ñó sẽ không ñánh giá một cách khách quan tầm quan trọng của các ñặc
trưng.
2.2.2.2. Mô hình Wrapper
• Ưu ñiểm:
- ðảm bảo hiệu suất của kết quả học hơn mô hình Filter.
• Nhược ñiểm:
- Ít ñược sử dụng hơn môt hình Filter trên thực tế vì:

Tiến trình học tốn kém về thời gian ñến mức thời gian thực hiện ñưa ra bởi
một thuật toán sử dụng mô hình Wrapper là không chấp nhận ñược.

Với một hệ thống kích thước cực lớn, mô hình này không thực tế do phạm
vi của nó buộc phải thu nhỏ lại trước khi thuật toán học máy ñược áp dụng.
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n

Kết quả ñánh giá của mô hình phụ thuộc nhiều vào thuật toán học máy ñiều
khiển.
2.3. Một số kỹ thuật xử lý
2.3.1. Bộ sinh tập con (Feature Subset Generator)
Tùy từng chiến lược cụ thể, bộ sinh tập con sẽ tạo ra những tập con ñặc trưng từ một
tập ñầu vào tương ứng. ðầu ra của bộ sinh sẽ xác ñịnh thuật toán trích chọn ñặc trưng của
việc tìm ñường và tìm kiếm phạm vi trong một không gian ñặc trưng tương ứng. Nói
chung, bộ sinh có hai chiến lược ñể sản sinh ra những tập con ñặc trưng:
• ðầy ñủ (Completely): Một bộ khởi tạo ñầy ñủ có thể sản sinh ra tất cả các tập con
từ một tập ñặc trưng ñầu vào, do vậy phạm vi tìm kiếm của chiến lược này là NP
ñầy ñủ, tuy nhiên ñiều này không phải lúc nào cũng chứng tỏ tìm kiếm vét cạn là
cần thiết trong thực tế, bởi vì một số công nghệ như: ñường biên và rẽ nhánh có
thể ñược áp dụng ñể lược bớt phạm vi tìm kiếm tốt nhất. Bởi vậy nếu là thuật toán
trích chọn với bộ khởi tạo ñầy ñủ, thực nghiệm chỉ ra rằng không gian tìm kiếm
lớn nhất là O(2k). Mà ñối với hầu hết những hệ thống học máy thực, ñiều này là
không cần thiết phải ñánh giá tất cả những tập con từ một tập ñặc trưng tương ứng.
Thường thì, thuật toán trích chọn với bộ khởi tạo ñầy ñủ có thể tìm ra một tập con
ñặc trưng tối ưu của hệ thống học máy nhưng ñòi hỏi thời gian thực thi phức tạp.
Liu H. [12] ñã ñưa ra bộ khởi tạo ñầy ñủ ñặc biệt mà sản sinh một cách ngẫu nhiên
ra những tập con ñặc trưng dựa vào thuật toán Las Vegas (LV). Thuật toán LV có
thể tìm kiếm trên toàn bộ không gian ñáp án rồi sau ñó ñưa ra kết quả tối ưu ñảm
bảo. Tuy nhiên khác với những bộ khởi tạo ñầy ñủ khác, ñối với một ứng dụng
thực tế, khả năng thực thi của bộ khởi tạo Liu là hoàn toàn thay ñổi, nó phụ thuộc
nhiều vào quá trình phân chia dữ liệu ngẫu nhiên trong toàn bộ hệ thống học máy.
• Kinh nghiệm (Heuristically): ðể lược bớt không gian tìm kiếm, bộ khởi tạo kinh
nghiệm sản sinh ra các tập con ñặc trưng dựa vào những kinh nghiệm chiến lược
nào ñó. Có ba kỹ thuật tìm kiếm tập con ñiển hình là:
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
- Lựa chọn tiến (Forward Selection): các tập con ñặc trưng ñược khởi tạo
trước hết là rỗng (null), sau ñó liên tục gán những chức năng tốt nhất hiện
thời cho tập con ñó cho ñến khi không còn chức năng nào nữa hay các ñiều
kiện thực thi ñưa ra ñã ñược tiếp nhận hết.
- Lược bỏ lùi (Backward Elimination): Các tập con ñặc trưng ñược khởi tạo
trước hết là ñầy ñủ các ñặc trưng, sau ñó loại bỏ lần lượt những ñặc trưng
kém nhất hiện thời từ các tập con ñó, cho ñến khi không còn ñặc trưng nào
hay các ñiều kiện thực thi ñưa ra ñã ñược triệt tiêu hết.
- Lựa chọn hai hướng (Bi – direction Selection): các tập con ñặc trưng ñược
khởi tạo trước hết là rỗng, ñầy, hay sản sinh ngẫu nhiên một tập con ñặc
trưng, sau ñó liên tục hay là gán chức năng tốt nhất hiện thời cho tập con ñó
hay là triệt tiêu chức năng kém nhất từ các tập con ñó. ðể từ ñó ñưa ra
những giá trị ñịnh hướng tốt nhất ở mỗi lần lặp lại ñó. Quá trình tiếp tục
cho tới khi tất cả ñiều kiện ñược ñưa ra từ trước ñã ñược tiếp nhận hết.
Bộ phận khởi tạo kinh nghiệm giảm thiểu phạm vi tìm kiếm ña thức số mũ, do ñó
giảm thời gian thực hiện thuật toán phức tạp trong phương pháp trích chọn. Tuy nhiên,
thuật toán chỉ ñưa ra một lượng nhỏ kết quả tối ưu, khi thực hiện tìm ñường và tìm kiếm
phạm vi của bộ phận khởi tạo, kết quả này ñược ñảm bảo thông qua những thuật toán này.
2.3.2. Bộ ñánh giá tập con ñặc trưng (Feature Subset Evaluator)
Hiệu suất của một tập con ñặc trưng ñược ñánh giá dựa trên cơ sở nào ñó mà bộ ñánh
giá ñạt ñược. Bộ ñánh giá của những mô hình thuật toán khác nhau là khác nhau. Bộ ñánh
giá của mô hình Filter thường là các hàm ñánh giá, trong khi của mô hình Wrapper là ñộ
học chính xác ñạt ñược bởi quá trình thực thi thuật toán học máy ñiều khiển trên hệ thống
học.
• Hàm ñánh giá
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
Những hàm ñánh giá ñiển hình dùng ñể ño ñạc và phân biệt khả năng phân lớp của
những ñặc ñiểm khác nhau trên các mẫu. Thực tế, các hàm ñánh giá khác nhau
thường ñược dùng hiện nay như: xấp xỉ chất lượng (Approximation Quality), ñộ
quan trọng của thuộc tính (Feature Importance), trọng số của thuộc tính (Feature
Weight) …
• Học chính xác
Trong mô hình Wrapper, ñể ước lượng ñộ học máy ...