CHƯƠNG 1: BÀI TOÁN PHÂN LỚP VÀ MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN Chương này trình bày về khái niệm bài toán phân lớp trong học máy và hai phương pháp kinh điển để giải bài toán này hiện nay: mạng neural và k-láng giềng gần nhất. PHÁT BIỂU BÀI TOÁN PHÂN LỚP 1. Mẫu (pattern/sample): Có thể phân làm hai hoại: mẫu trừu tượng và mẫu cụ thể. Các ý tưởng, lập luận và khái niệm.
là những ví dụ về mẫu trừu tượng, nhận dạng các mẫu như vậy thuộc về lĩnh vực nhận dạng khái niệm. Các mẫu cụ thể bao gồm các đối tượng có tính không gian, thời gian và hình ảnh, hoặc các đối tượng vật lý, chữ ký, chữ viết, ký hiệu, ảnh, đoạn sóng âm thanh, điện não đồ hoặc điện tâm đồ, hàm số.là những ví dụ về mẫu cụ thể. Nhận dạng mẫu là gì? Không có một định nghĩa thống nhất nào về nhận dạng mẫu (Pattern recognition viết tắt là PR) nhưng điều này cũng không gây ra tranh cãi gì trong giới nghiên cứu. Sau đây là một số định nghĩa theo ngữ cảnh nghiên cứu: - Duda et al: Nhận dạng mẫu là việc quy những đối tượng vật lí hay sự kiện vào một loại (nhóm) nào đó đã xác định từ trước.
- Jürgen Schürmann: Nhận dạng mẫu là việc gán nhãn w cho một quan sát x. - Selim Aksoy: Nhận dạng mẫu là việc nghiên cứu cách làm cho một máy có thể thực hiện: + Quan sát môi trường. + Học cách phân biệt được các mẫu cần quan tâm. + Đưa ra các quyết định đúng đắn về loại (nhóm) của các mẫu.
Như vậy thay cho việc tìm định nghĩa chính xác cho khái niệm nhận dạng mẫu ta sẽ liệt kê các bài toán chính trong lĩnh vực này. Các bài toán nhận dạng mẫu thường gặp Các bài toán nhận dạng mẫu thường gặp có thể quy về các dạng sau. Phân lớp có giám sát hay phân loại (categorize): Dựa trên một tập con (tập đào tạo) đã biết nhãn, đưa ra một cách gán nhãn cho các đối tượng mới để phân tập các đối tượng thành các lớp. Ví dụ: nhận dạng chữ viết tay nhờ các chữ đã biết, nhận dạng loài hoa nhờ các thông tin về độ dài, độ rộng, màu sắc.
Phân lớp không giám sát hay phân cụm (cluster): Chia tập đối tượng thành nhóm sao cho các đối tượng trong mỗi nhóm tương đối giống nhau còn các đối tượng khác nhóm thì khác nhau. Phân tích hồi quy (regression) hay nhận dạng hàm: Xác định một biến (hàm) qua tập các biến khác. Nhận thực (Identify): Xác định đối tượng trong tập đã cho có là đối tượng đang quan tâm hay không. Chẳng hạn như nhận thực vân tay, nhận thực mặt người.
Mô tả: Mô tả các đối tượng dưới hình thức dễ phân tích. Chẳng hạn mô tả điện tâm đồ dưới dạng biểu đồ đặc trưng hoặc xâu mã. Khóa luận này sẽ đề cập đến bài toán đầu tiên: Phân lớp có giám sát hay phân loại (categorize). Để hiểu rõ hơn yêu cầu của bài, xem ví dụ ở phần 1.3 phương pháp k láng giềng gần nhất.
MẠNG NEURAL NHÂN TẠO Bộ não con người chứa đựng những bí mật mà đến bây giờ khoa học vẫn chưa giải đáp được, chính nhờ có bộ não hoàn chỉnh mà con người đã trở thành động vật bậc cao thống trị muôn loài. Đã từ lâu con người đã nghiên cứu cấu trúc đặc biệt của bộ não từ đó ứng dụng để giải quyết những bài toán khoa học kỹ thuật. Người ta đã phát hiện ra rằng bộ não con người là mạng lưới chằng chịt các Neural liên kết với nhau, đây là cơ sở hình thành nên cấu trúc của mạng Neural nhân tạo. Về bản chất toán học thì mạng Neural nhân tạo như là một mặt trong không gian đa chiều để xấp xỉ một hàm chưa biết nào đấy.
Nhưng mạng Neural nhân tạo lại giống mạng Neural sinh học ở chỗ đó là khá năng có thể huấn luyện(học), đây là đặc điểm quan trọng nhất của mạng Neural nhân tạo. Chính vì đặc điểm này mà mạng Neural nhân tạo có khả năng thực hiện tốt các công việc sau khi đã được huấn luyện, và đến khi môi trường thay đổi ta lại có thể huấn luyện lại mạng Neural nhân tạo để nó thích nghi với điều kiện mới. Mạng Neural sinh học Mạng Neural sinh học là một mạng lưới (plexus) các Neuron có kết nối hoặc có liên quan về mặt chức năng trực thuộc hệ thần kinh ngoại biên (peripheral nervous system) hay hệ thần kinh trung ương (central nervous system). Hình 1: Minh họa một Neuron thần kinh sinh học Trên đây là hình ảnh của một tế bào thần kinh(Neural thần kinh), ta chú ý thấy rằng một tế bào thần kinh có ba phần quan trọng: -Phần đầu cũng có nhiều xúc tu (Dendrite) là nơi tiếp xúc với các với các điểm kết nối(Axon Terminal) của các tế bào thần kinh khác -Nhân của tế bào thần kinh (Nucleus) là nơi tiếp nhận các tín hiệu điện truyền từ xúc tu.
Sau khi tổng hợp và xử lý các tín hiệu nhận được nó truyền tín hiệu kết quả qua trục cảm ứng (Axon) đến các điểm kết nối (Axon Terminal) ở đuôi. -Phần đuôi có nhiều điểm kết nối (Axon Terminal) để kết nối với các tế bào thần kinh khác. Khi tín hiệu vào ở xúc tu kích hoạt nhân nhân Neuron có tín hiệu ra ở trục cảm ứng thì Neuron được gọi là cháy.Pitts (1940) đề xuất mô hình mạng neural nhân tạo khá sớm nhưng định đề Heb (1949) mới là nền tảng lý luận cho mạng neural nhân tạo. Định đề Heb: Khi một neuron(thần kinh) A ở gần neuron B, kích hoạt thường xuyên hoặc lặp lại việc làm cháy nó thì phát triển một quá trình sinh hoá ở các neuron làm tăng tác động này.
Mạng Neural nhân tạo Mạng Neural nhân tạo được thiết kế để mô hình một số tính chất của mạng Neural sinh học, tuy nhiên, khác với các mô hình nhận thức, phần lớn các ứng dụng lại có bản chất kỹ thuật. Mạng Neural nhân tạo (ANN) là máy mô phỏng cách bộ não hoạt động thực hiên các nhiệm vụ của nó. Một mạng Neural là bộ xử lý song song phân tán lớn nó giống bộ não người về 2 mặt: -Tri thức được nắm bắt bởi Neural thông qua quá trình học. -Độ lớn của trọng số kết nối Neural đóng vai trò khớp nối cất giữ thông tin.
a) Cấu tạo một Neuron trong mạng Neural nhân tạo x1 w1 w0 x2 w2 Y ∑ xn F w3 Cấu tạo một Neural nhân tạo Một neuron bao gồm các liên kết nhận tín hiệu vào bằng số có các trọng số kết nối wi tương ứng với tín hiệu xi, hàm F gọi là hàm kích hoạt để tạo tín hiệu ra dựa trên giá trị 6. hàm tổng có trọng số của các giá trị đầu vào, Y là giá trị đầu ra của Neural. Ta có thể biểu n diễn một Neural nhân tạo theo công thức toán học như sau: Y F w 0 xi wi i 1 Tùy vào thực tế bài toán hàm F là một hàm cụ thể nào đấy, trong quá trình huấn luyện(học) thì các tham số wi được xác định. Trên thực thế F thường được chọn trong những hàm sau: 1.5 1; x 0 F ( x) ( x) 0 1) Hàm ngưỡng 1; x 0 -6 -4 -2 0 2 4 6 -0.5 Hình 2: Đồ thị hàm ngưỡng 4 3 2 1 2) Hàm tuyến tính 0 F ( x) ax -1 -6 -4 -2 0 2 4 6 -2 -3 -4 Hình 3: Đồ thị hàm tuyến tính 1 3) Hàm sigmoid 1 0.5 F ( x) 1 e x 0 -6 -4 -2 0 2 4 6 Hình 4: Đồ thị hàm sigmoid 7 .5 -1 Hình 5: Đồ thị hàm tanh 1 0.5 5) Hàm bán kính x2 F ( x) e (Gauss) 0 -6 -4 -2 0 2 4 6 Hình 6: Đồ thị hàm Gauss Trên thực tế thì các họ hàm sigmoid thường dùng cho mạng Neural truyền thẳng nhiều tầng MLP vì các hàm này dễ tính đạo hàm: f '( x) f ( x)(1 f ( x )) , trong khi đó mạng Neural RBF lại dùng hàm kích hoạt là hàm bán kính.
b) Kiến trúc của mạng Neural nhân tạo 8. Kiến trúc của mạng Neural nhân tạo lấy tư tưởng chính của mạng Neural sinh học đó là sự kết nối của các Neural. Tuy nhiên, mạng Neural nhân tạo có kiến trúc HIDDEN đơn giản hơn nhiều, về cả số lượng INPUT Neuron và cả kiến trúc mạng, trong khi ở OUTPUT mạng Neural tự nhiên một Neuron có thể kết nối với một Neuron khác bất kỳ ở trong mạng thì ở mạng Neural nhân tạo các Neuron được kết nối sao cho nó có thể dễ dàng được biểu diễn bởi một mô hình toán học nào đấy. Ví dụ trong mạng Neural truyền tới các Neuron được phân Hình 7: Kiến trúc mạng neural truyền tới thành nhiều lớp, các Neuron ở lớp trước chỉ được kết nối với các Neuron ở lớp sau.
c) Quá trình học Như đã nói ở trên mạng Neural nhân tạo có khả năng huấn luyện được(học), quá trình huấn luyện là quá trình mà mạng Neural nhân tạo tự thay đổi mình dưới sự kích thích của môi trường(bộ dữ liệu huấn luyện) để phù hợp với điều kiện của môi trường. Quá trình huấn luyện chỉ có thể được thực hiện khi mạng Neural nhân tạo đã xây dựng được kiến trúc cụ thể, và hàm kích hoạt F đã được xác định. Về bản chất quá trình học là quá trình xác định các tham số wi của các Neuron trong mạng Neural. Có ba kiểu học chính, mỗi kiểu mẫu tương ứng với một nhiệm vụ học trừu tượng.
Đó là học có giám sát, học không có giám sát và học tăng cường. Dưới đây xin nêu ra phương pháp học có giám sát, các phương pháp khác xem thêm phần phụ lục. Học có giám sát Trong học có giám sát, ta được cho trước một tập ví dụ gồm các cặp ( xi , y i , i 1.n), x X , y Y và mục tiêu là tìm một hàm f : X Y (trong lớp các hàm 9. được phép) khớp với các ví dụ.
Trên thực tế người ta thường tìm hàm f sao cho tổng bình n 2 phương sai số đạt giá trị nhỏ nhất trên tập ví dụ: E f ( xi ) y i i 1 Chương 2 xin được trình bày về bản đồ tự tổ chức (còn gọi là bản đồ Kohonen) – một loại mạng neural dùng để phân cụm. PHƯƠNG PHÁP K LÁNG GIỀNG GẦN NHẤT 1.1 Thuật toán k láng giềng gần nhất là gì?