TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN TOÁN ỨNG DỤNG VÀ TIN HỌC
-------------------------
BÀI GIẢNG
LÝ THUYẾT NHẬN DẠNG
( TÀI LIỆU LƯU HÀNH NỘI BỘ )
Đếu có nhà xuất bản :v
Bài Giảng
Lý thuyết nhận dạng
Mục lục
1 Cơ sở lý luận của lý thuyết nhận dạng 6
1.1 Khái niệm cơ bản về nhận dạng . . . . . . . . . . . . . . 6
1.1.1 Sự ra đời của khoa học nhận dạng và hai định
hướng trong khoa học nhận dạng(KHND) . . . . 6
1.1.2 Một số ví dụ về nhận dạng dẫn đến định nghĩa
tổng quát về dạng . . . . . . . . . . . . . . . . . . 7
1.1.3 Định nghĩa tổng quát về dạng . . . . . . . . . . . 8
1.2 Một số bài toán cơ bản làm cơ sở cho việc xây dựng hệ
nhận dạng . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Bài toán mã hóa dạng . . . . . . . . . . . . . . . 9
1.2.2 Bài toán về việc xử lý sơ bộ và lựa chọn các dấu
hiệu ......................... 11
1.2.3 Bài toán xây dựng hệ nhận dạng . . . . . . . . . 12
1.2.4 Bài toán đánh giá tham số . . . . . . . . . . . . . 12
1.2.5 Bài toán mô phỏng dạng . . . . . . . . . . . . . . 12
1.3 Một số nguyên tắc và phương pháp luận làm cơ sở để xây
dựng hệ nhận dạng . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 Mội số nguyên tắc cơ bản . . . . . . . . . . . . . 13
1.3.2 Một số phương pháp luận làm cơ sở cho việc xây
dựng hệ nhận dạng tự động . . . . . . . . . . . . 13
1.4 Về một số phương pháp toán học xây dựng tiêu chuẩn
nhận dạng cho hệ nhận dạng tự động . . . . . . . . . . . 14
1.4.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . 14
1.4.2 Xây dựng tiêu chuẩn nhận dạng cho hệ nhận dạng
tự động . . . . . . . . . . . . . . . . . . . . . . . 15
2 Các hàm quyết định phân lớp dạng 18
2.1 Hàm quyết định và các yếu tố xác định hàm quyết định . 18
2.2 Nhận dạng bằng các hàm quyết định tuyến tính . . . . . 21
2.3 Một số trường hợp phân lớp dạng bằng hàm quyết định
tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2
Giáp Văn Hiệp - Toán Tin 2 - K54
2.4 Nhận dạng bằng hàm quyết định suy rộng . . . . . . . . 28
2.4.1 Dạng tổng quát của các hàm suy rộng . . . . . . 28
2.4.2 Một số biến dạng quan trọng của các hàm suy rộng 29
2.5 Các phép lưỡng phân tập dạng . . . . . . . . . . . . . . 31
2.5.1 Khái niệm về phép lưỡng phân và có ý nghĩa của
phép lưỡng phân . . . . . . . . . . . . . . . . . . 31
2.5.2 Xác định bậc lưỡng phân bằng hàm suy rộng . . . 34
2.6 Phương pháp xâu dựng hàm tuyến tính trên cơ sở xấp xỉ
bởi 1 hệ các đa thức trực giao, trực chuẩn . . . . . . . . 35
2.6.1 Xây dựng hệ trực giao, trực chuẩn các hàm 1 biến 35
2.7 Xây dựng hệ trực giao, trực chuẩn đầy đủ, các hàm nhiều
biến trên cở sở hệ trực giao, trực chuẩn đầy đủ các hàm
1biến ............................ 39
2.7.1 Xây dựng một số hệ đa thức trực giao, trực chuẩn
đầy đỷ 1 biến đặc biệt và áp dụng xây dựng hệ đa
thức trực giao, trực chuẩn nhiều chiều. . . . . . . 40
2.8 Phương pháp xây dựng các hàm quyết định dựa trên cở
sở xấp xỉ bởi hệ các đa thức trực giao, trực chuẩn. . . . . 43
3 Phân lớp dạng bằng các hàm khoảng cách 45
3.1 Đặc trưng của việc phân lớp dạng bằng các hàm khoảng
cách ............................. 45
3.1.1 Khái niệm khoảng cách, hàm khoảng cách . . . . 45
3.1.2 Đăc trưng của việc phân lớp dạng bằng các hàm
khoảng cách . . . . . . . . . . . . . . . . . . . . . 46
3.2 Một số phương pháp phân lớp dạng theo tiêu chuẩn cực
tiểu khoảng cách . . . . . . . . . . . . . . . . . . . . . . 46
3.2.1 Phương pháp 1 . . . . . . . . . . . . . . . . . . . 46
3.2.2 Phương pháp 2 . . . . . . . . . . . . . . . . . . . 49
3.3 Một số thuật toán phân hoạch tập dạng theo tiêu chuẩn
cực tiểu khoảng cách . . . . . . . . . . . . . . . . . . . . 52
3.3.1 Khái niệm độ đo đồng dạng và một số độ đo đồng
dạng tiêu biểu . . . . . . . . . . . . . . . . . . . . 52
3.3.2 Một số thuật toán phân hoạch dạng theo tiêu chuẩn
cực tiểu khoảng cách. . . . . . . . . . . . . . . . . 55
4 Phân lớp dạng bằng các hàm xác suất 66
4.1 Phân lớp dạng như là một bài toán về lý thuyết các phép
giải thống kê . . . . . . . . . . . . . . . . . . . . . . . . 66
3
Giáp Văn Hiệp - Toán Tin 2 - K54
4.1.1 Xác định bài toán phân lớp dạng như là 1 trò chơi
mang đặc trưng thống kê. . . . . . . . . . . . . . 66
4.1.2 Xây dựng tiêu chuẩn nhận dạng cho việc phân lớp
dạng theo nghĩ xác suất. . . . . . . . . . . . . . . 68
4.1.3 Large Xây dựng các hàm quyết định phân lớp dạng
theo quy tắc phân lớp Bayets . . . . . . . . . . . 70
4.2 Phân lớp dạng theo quy tắc phân lớp Bayets trong trường
hợp các dạng tuân theo luật phân phối chuẩn . . . . . . 71
4.2.1 Nhắc lại đặc trưng của các biến ngẫu nhiên có
phân phối chuẩn . . . . . . . . . . . . . . . . . . 71
4.2.2 Xây dựng tiêu chuẩn nhận dạng, hàm quyết định
theo quy tắc phân lớp Bayets có các dạng có phân
phối chuẩn . . . . . . . . . . . . . . . . . . . . . . 72
4.3 Một số đánh giá xác suất sai số của phân lớp Bayets trong
một số trường hợp đặc biệt . . . . . . . . . . . . . . . . . 77
4.3.1 Đánh giá sai số của phân lớp Bayets trong trường
hợp phân phối chuẩn . . . . . . . . . . . . . . . . 77
4.3.2 Mở rộng đánh giá cho trường hợp phân lớp dạng
được thưc hiện bởi các hàm tuyến tính . . . . . . 80
4.4 Giới thiệu một số hàm mật đọ phân phối quan trọng trong
nhận dạng . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.4.1 Hàm mật độ dạng tổng quát . . . . . . . . . . . . 81
4.4.2 Một số hàm mật độ dạng Peason . . . . . . . . . 81
4.5 Phương pháp xây dựng các hàm quyết định phân lớp dạng
theo quy tắc phân lớp Bayets trên cơ sở xấp xỉ các hàm
mật độ phân phốix ác suất . . . . . . . . . . . . . . . . . 83
4.5.1 Xây dựng các công thức truy toán tính kỳ vọng,
ma trận hiệp biến của các dạng thuộc cùng 1 lớp 83
4.5.2 Xây dựng xấp xỉ mật độ phân phối bởi hệ hàm . 85
4.5.3 Xây dựng các hàm quyết định phân lớp dạng theo
quy tắc phân lớp Bayets trên cơ sở xâp xỉ các hàm
mật độ phân phối . . . . . . . . . . . . . . . . . . 88
Tài liệu tham khảo 92
4