Xem mẫu

  1. Ch­¬ng 20 NHẬN DẠNG MẪU: PHÂN LỚP VÀ ĐÁNH GIÁ 20.1. GIỚI THIỆU Trong chương 18, chúng ta đã giới thiệu về nhận dạng mẫu thống kê và đã đề cập đến việc tách và trích chọn các đối tượng từ một cảnh phức tạp. Chương 19 đã chỉ ra các phương pháp xác định những đặc điểm của các đối tượng đó. Trong chương này, chúng ta tiếp cận bài toán nhận biết các đối tượng bằng cách phân lớp chúng thành từng nhóm. Có lẽ phải viết nhiều về chủ đề này và chúng ta chỉ có thể giới thiệu các khái niệm cơ bản ở đây. Nếu muốn nghiên cứu đầy đủ hơn, độc giả nên tham khảo tài liệu về chủ đề này (Phụ lục 2) 20.2. PHÂN LỚP 20.2.1. Chọn lọc đặc trưng Nếu ta muốn một hệ thống phân biệt các loại đối tượng khác nhau, đầu tiên chúng ta phải quyết định nên xác định những đặc điểm nào để tạo ra các tham số miêu tả. Các đặc điểm riêng biệt cần xác định gọi là các đặc trưng của đối tượng và các giá trị tham số kết quả gồm có vec tơ đặc trưng đối với từng đối tượng. Việc chọn lựa các đặc trưng thích hợp là rất quan trọng, vì chỉ có chúng mới được sử dụng để nhận biết đối tượng. Có vài phương tiện phân tích để hướng dẫn chọn lựa các đặc trưng. Khả năng trực giác thường xuyên chỉ đạo danh sách các đặc trưng có ích tiềm tàng. Các kỹ thuật sắp xếp đặc trưng tính toán có liên quan đến số lượng các đặc trưng khác nhau. Điều này cho phép lược bớt danh sách chỉ còn một vài đặc trưng tốt nhất. Các đặc trưng tốt có bốn đặc điểm: 1. Sự phân biệt đối xử. Các đặc trưng phải nhận những giá trị khác nhau một cách đáng kể đối với các đối tượng thuộc các lớp khác nhau. Ví dụ, đường kính là dặc tính tốt trong ví dụ sắp xếp trái cây ở chương 18, vì nó nhận những giá trị khác nhau đối với những quả sơ ri và những quả nho. 2. Tính tin cậy. Các đặc trưng phải nhận các giá trị giống nhau đối với mọi đối tượng cùng lớp. Ví dụ, màu sắc có thể là đặc trưng kém đối với những quả táo nếu chúng xuất hiện theo các mức độ chín không ổn định. Tức là, một quả táo xanh và một quả táo chín (đỏ) có thể rất khác nhauvề màu sắc, mặc dù cả hai đều thuộc lớp đối tượng là các quả táo. 3. Tính độc lập. Nhiều đặc trưng được sử dụng khác nhau không được tương quan với nhau. Đường kính và trọng lượng của một trái cây sẽ tạo thành các đặc trưng tương quan chặt, vì trọng lượng tỷ lệ gần đúng với đường kính mũ ba. Bài toán mà cả đường kính lẫn trọng lượng về bản chất đều phản ánh cùng một tính chất, ấy là kích thước của trái cây. Trong khi các đặc trưng tương quan chặt có thể kết hợp (ví dụ, bằng cách lấy trung bình tất cả chúng cùng với nhau) 401
  2. để làm giảm tính nhậy cảm đối với nhiễu, thì nói chung chúng lại không được sử dụng như những đặc trưng độc lập. 4. Các số nhỏ. Tính phức tạp của một hệ thống nhận dạng mẫu tăng nhanh chóng theo kích cỡ (số các đặc trưng được dùng) của hệ thống. Quan trọng hơn là số các đối tượng cần có để huấn luyện bộ phân lớp và để đo lường hiệu suất của nó tăng theo cấp số mũ với số các đặc trưng. Trong vài trường hợp, để có thể đạt được lượng dữ liệu cần thiết cho việc huấn luyện bộ phân lớp tương xứng chỉ là điều hão huyền. Cuối cùng, việc thêm các đặc trưng nhiễu hay đặc trưng tương quan chặt với các đặc trưng hiện có có thể làm suy giảmhiệu suất của những bộ phân lớp, đặc biệt bởi vì kích thước giới hạn của tập huấn luyện. Trong thực tế, quá trình chọn lựa đặc trưng thường bao gồm cả việc kiểm tra tập các đặc trưng hợp lý quatrực giác và việc giảm tập xuống còn một số các đặc trưng tốt nhất có thể chấp nhận. Thường có ít hoặc không có sẵn các đặc trưng lý tưởng dưới dạng các tính chất đã nói ở trên. 20.2.2. Thiết kế bộ phân lớp Thiết kế bộ phân lớp bao gồm việc thiết lập cấu trúc logic của bộ phân lớp và cơ sở toán học của quy tắc phân lớp. Thông thường, đối với mỗi đối tượng thường gặp, sự phân lớp tính toán, với từng lớp, giá trị báo hiệu (bằng độ lớn của nó) mức độ mà đối tượng đó tương tự đối tượng điển hình của lớp đó. Giá trị này được tính như một hàm đặc trưng và nó được dùng để chọn lớp gần giống với công việc được giao nhất. Hầu hết các quy tắc quyết định bộ phân lớp đều giảm đến một vạch ngưỡng phân chia các không gian kích cỡ thành các vùng rời nhau, mỗi lớp một (hoặc nhiều) vùng. Mỗi vùng (phạm vi các giá trị đặc trưng) ứng với một lớp riêng lẻ. Nếu các giá trị đặc trưng nằm trong một vùng riêng biệt thì đối tượng được ấn định cho lớp tương ứng. Trong vài trường hợp, một hoặc nhiều vùng như vậy có thể ứng với một lớp “không xác định”. 20.2.3. Huấn luyện bộ phân lớp Một khi các quy tắc quyết định cơ bản của bộ phân lớp đã được thiết lập thì ta phải xác định các giá trị ngưỡng riêng biệt phân tách các lớp. Điều này thường được thực hiện bằng cách huấn luyện bộ phân lớp theo nhóm các đối tượng đã biết. Tập huấn luyện là một tập hợp các đối tượng từ mỗi lớp đã được nhận biết trước đó bằng một phương pháp chính xác nào đó. Các đối tượng trong tập huấn luyện được đo, và không gian kích cỡ được phân chia, bằng các bề mặt quyết định, thành các vùng mà độ chính xác của bộ phân lớp là tối đa khi nó hoạt động trên tập huấn luyện. Khi huấn luyện một bộ phân lớp, ta có thể sử dụng quy tắc đơn lẻ, ví dụ như tối thiểu hoá tổng các sai số phân lớp. Nếu một vài sự phân lớp sai lầm có thể gây rắc rối hơn những cái khác thì ta có thể thiết lập một hàm giá để giải thích điều này bằng cách cân nhắc các sai số khác nhau một cách gần đúng. Các đường quyết định sau đó được đặt vào để tối thiểu hoá toàn bộ “giá” của việc thao tác bộ phân lớp. Nếu tập huấn luyện là biểu diễn của các đối tượng nói chung thì bộ phân lớp loại cũng phải thực hiện xung quanh các đối tượng mới giống như nó đã từng thực hiện trên tập huấn luyện. Có được một tập huấn luyện đủ lớn thường là một công việc gian khổ. Để được thể hiện, tập huấn luyện phải bam gồm các ví dụ về tất cả những đối tượng có thể gặp, kể cả những đối tượng hiếm khi nhìn thấy. Nếu tập huấn luyện ngăn chận một đối tượng không phổ biến nào đó, thì nó không biểu hiện. Nếu nó chứa các sai số phân lớp thì nó bị thành kiến. 402
  3. 20.2.4. Xác định hiệu suất Sự chính xác của một bộ phân lớp có thể được đánh giá trực tiếp bằng cách liệt kê hiệu suất của nó dựa trên tập các đối tượng kiểm tra đã biết. Nếu tập kiểm tra đủ lớn để biểu diễn các đối tượng lớn và nếu nó không có sai số, thì hiệu suất được đánh giá có thể rất hữu ích. Một phương pháp lựa chọn cho việc đánh giá hiệu suất là sử dụng tập kiểm tra của các đối tượng đã biết để đánh giá PDF của những đặc trưng theo từng nhóm. Từ những PDF cơ bản đã cho, ta có thể sử dụng các tham số phân lớp để tính tỷ lệ sai số mong muốn. Nếu đã dạng tổng quát của các PDF đó thì kỹ thuật này có thể sử dụng tập kiểm tra kích thước ở mép tốt hơn. Ta muốn có được hiệu suất của bộ phân lớp trên tập huấn luyện như một phép đo toàn bộ hiệu suất của nó, nhưng đánh giá này thường bị nghi ngờ về tính lạc quan. Một phương pháp tiếp cận tốt hơn là sử dụng một tập kiểm tra riêng biệt đối với việc đánh giá hiệu suất của bộ phân lớp. Tuy nhiên, điều này làm tăng đáng kể sự cần thiết của những dữ liệu trước phân lớp. Nếu những đối tượng đã phân lớp trước đây được đánh giá cao, thì ta có thể sử dụng một thủ tục vòng luân chuyển mà trong đó bộ phân lớp được huấn luyện với hầu hết mọi đối tượng và tiếp theo sau là đối tượng đó được phân lớp. Khi điều này được thực hiện với tất cả các đối tượng thì ta sẽ có một đánh giá của toàn bộ hiệu suất thực hiện của bộ phân lớp. 20.3. CHỌN LỰA ĐẶC TRƯNG Trong một bài toán nhạn dạng mẫu, ta thường phải đối mặt với côngviệc chọn lựa trong nhiều đặc trưng sẵn có, đặc trưng nào xác định và thể hiện bộ phân lớp. Bài toán chọn lựa đặc trưng đã nhận được sự quan tâm đáng kể trong tài liệu, nhưng lại nổi lên tình trạng không rõ ràng. Phần này dành cho độc giả như một vấn đề lý thú. Như đã lưu ý trước đây, ta tìm kiếm một tập nhỏ các đặc trưng tin cậy, độc lập và sự phân biệt đối xử. Nói chung, ta mong muốn làm suy giảm hiệu suất của bộ phân lớp khi các đặc trưng được đánh giá, ít ra cũng là những đặc trưng hữu ích. Thực tế, đánh giá nhiễu hay các đặc trưng tương quan chặt có thể thực sự cải tiến hiệu suất thực hiện. Sau đó, chọn lựa đặc trưng có thể được coi như quá trình đánh giá một vài đặc trưng và kết hợp các đặc trưng có liên quan khác, cho đến khi tập đặc trưng trở nên dễ sử dụng và sự thực hiện vẫn còn chính xác. Nếu tập đặc trưng được giảm từ M đặc trưng xuống còn một lượng N nào đó nhỏ hơn, thì chúng ta sẽ tìm kiếm tập N đặc trưng riêng biệt để tối thiểu hoá toàn bộ việc thực hiện bộ phân lớp. Một phương pháp tiếp cận bằng cách lặp đi lặp lại một thủ tục đơn giản nhiều lần để chọn lựa đặc trưng được cho dưới đây. Đối với tất cả các tập con của N đặc trưng có thể có, huấn luyện bộ phân lớp, và xác định hiệu suất của nó bằng cách liệt kê các tỷ số phân lớp nhầm các nhóm khác nhau của bộ phân lớp. Sau đó tạo ra một chỉ số hiệu suất tổng thể là một hàm tỷ số lỗi. Cuối cùng, sử dụng tập N đặc trưng đó để tạo ra chỉ số hiệu suất tốt nhất. Dĩ nhiên bài toán với cách tiếp cận bằng cách lặp đi lặp lại một thủ tục đơn giản nhiều lần là một khối lượng khổng lồ đối với tất cả trừ các bài toán nhận dạng mẫu đơn giản nhất. Thực tế, thường thì tài nguyên chỉ đủ để huấn luyện và đánh giá bộ phân lớp. Trong đa số các bài toán thực tiễn, phương pháp tiếp cận bằng cách lặp đi 403
  4. lặp lại một thủ tục đơn giản nhiều lần là không thực tế và một kỹ thuật ít tốn tiền phải được sử dụng để đạt được cùng một mục đích. Trong phần thảo luận dưới đây, chúng ta sẽ xem xét trường hợp giảm một bài toán hai đặc trưng xuống còn một đặc trưng đơn giản. Giả sử tập huấn luyện là có sẵn và chứa các đối tượng của M lớp khác nhau. Đặt Nj là số đối tượng trong lớp j. Hai đặc trưng xij và yij thu được khi xác định đối tượng thứ i trong lớp j. Ta có thể khởi đầu bằng việc tính giá trị trung bình của từng đặc trưng trong mỗi lớp:  Nj 1  xj  Nj x i 1 ij (1) và  Nj 1  yj  Nj y i 1 ij (2) Dấu mũ trên đầu xj và yj nhắc ta rằng đây là những đánh giá của các giá trị trung bình trong lớp dựa trên tập huấn luyện, chứ không phải là các giá trị trung bình thật sự của lớp. 20.3.1. Độ lệch đặc trưng Lý tưởng mà nói, các đặc trưng phải nhận các giá trị giống nhau đối với mọi đối tượng trong cùng một lớp. Độ lệch đặc trưng x trong lớp j được đánh giá là  Nj  2 2 1    xj  Nj   i 1  x ij   xj   (3) và đối với đặc trưng y là  Nj  2 2 1    yj  Nj   i 1  y ij   yj   (4) 20.3.2. Tương quan đặc trưng Sự tương quan của các đặc trưng x và y trong lớp j có thể được đánh giá bởi Nj   1     Nj   i 1  x ij   xj   y ij   yj    xyj    (5)  xj  yj Đại lượng này nằm giữa -1 và +1. Giá trị 0 cho thấy rằng hai đặc trưng là không tương quan, trong khi giá trị gần +1 cho thấy một mức đọ cao của sự tương quan. Giá trị -1 chứng tỏ rằng mỗi biến tỷ lệ với giá trị âm của biến khác. Nếu độ lớn của một tương quan xấp xỉ 1, thì hai đặc trưng có thể được kết hợp thành một hay có thể bỏ đi một trong hai đặc trưng đó. 20.3.3. Khoảng cách phân tách lớp Một phép tính xác đáng về khả năng của một đặc trưng để phân biệt hai lớp là khoảng cách độ lệch đã chuẩn hoá giữa các giá trị trung bình của lớp. Với đặc trưng x, khoảng cách này được cho bởi 404
  5.     xj  xk D xjk  (6)  2  2  xj  xk trong đó j, k là hai lớp. Rõ ràng, đặc trưng cao hơn là đặc trưng tạo ra sự tách lớp phổ biến nhất. 20.3.4. Giảm chiều Có nhiều phương pháp kết hợp hai đặc trưng x và y thành một đặc trưng z đơn lẻ. Một phương pháp đơn giản là sử dụng một hàm tuyến tính (Xem phần 13.6.2.1) z  ax  by (7) Bởi vì hiệu suất phân lớp không bị ảnh hưởng bởi việc lấy tỷ lệ độ lớn của các đặc trưng, chúng ta có thể lợi dụng sự hạn chế về độ lớn, ví dụ như a2  b2  1 (8) Biểu thức này có thể hợp nhất với biểu thức (7) bằng cách viết z  x cos  y sin  (9) trong đó  là một biến mới chỉ rõ tỷ lệ của x và y trong biểu thức. Nếu mỗi đối tượng trong tập huấn luyện tương ứng với một điểm trong không gian đặc trưng hai chiều (ví dụ mặt phẳng x, y), thì biểu thức (9) miêu tả mọi điểm lên trục z, làm thành với trục x một góc . Điều này được cho trong bảng 20-1. Rõ ràng,  phải được chọn để tối thiểu hoá sự tách lớp hay một tiêu chuẩn chất lượng nào đó của một đặc trưng. Để hiểu thêm về sự giảm chiều, độc giả nên tham khảo một cuốn sách nói về nhận dạng mẫu. HÌNH 20-1 Hình 20-1 Giảm chiều bằng phép chiếu 20.4. SỰ PHÂN LỚP THỐNG KÊ Trong phần này, chúng ta sẽ xem xét một vài phương pháp thống kê phổ biến được dùng cho phân lớp. 405
  6. 20.4.1. Lý thuyết quyết định thống kê Giả sử chúng ta có một bài toán sắp xếp trái cây đơn giản như trong chương 18, nhưng chỉ với hai lớp và một đặc trưng đơn lẻ. Nghĩa là các đối tượng thể hiện chính bản thân chúng theo lớp 1 (anh đào) hoặc lớp 2 (táo). Đối với mỗi đối tượng, ta xác định một tính chất, đường kính, và ta gọi đặc trưng này là x. Có thể biết trước PDF của đường kính x đối với một hay cả hai lớp đối tượng. Ví dụ, Hiệp hội nông dân trồng anh đào có thể phát hành một bản tin mở đầu là đường kính trung bình của các quả anh đào là 20 mm và PDF là xẫpỉ hàm Gauss với độ lệch tiêu chuẩn là 4 mm. Nếu không biết PDF của đừng kính những quả táo, ta có thể ước lượng nó bằng cách đo một lượng lớn các quả táo, vẽ lược đồ các đường kính của chúng và tính trung bình và độ lệch. Sau đó chuẩn hoá thành đơn vị diện tích và có lẽ nên làm trơn, có thể coi lược đồ này như một ước lượng củaPDF tương ứng. 20.4.1.1. Xác suất tiên nghiệm Nói chung, đó là khả năng một lớp hầu như sẽ xuất hiện không theo thứ tự. Ví dụ, giả sử băng truyền trong ví dụ sắp xếp trái cây đã biết, vận chuyển số anh đào nhiều gấp hai lần số táo mỗi chu kỳ vận hành. Vì thế, ta có thể nói rằng một xác suất tiên nghiệm của hai lớp là 2 1 P C i   vµ P C 2   (10) 3 3 Các biểu thức này phát biểu đơn giản rằng lớp 1 có khả năng xuất hiện gấp hai lần lớp 2. Xác suất tiên nghiệm biểu diễn điều mà chúng ta biết về một đối tượng trước khi nó được xác định. Trong ví dụ này, chúng ta ta biết rằng một đối tượng chưa xác định là anh đào có khả năng xuất hiện gấp hai lần táo. Xác suất có điều kiện. Hình 20-2 trình bày hình dạng của hai PDF. Ta ký hiệu PDF có điều kiện đối với đường kính anh đào là P(x|C1), có thể đọc là “xác suất mà đường kính x sẽ xuất hiện, khi đã biết xác suất xuất hiện đối tượng thuộc lớp 1”. Tương tự, P(x|C2) là xác suất xuất hiện của đường kính x, khi đã biết xác suất xuất hiện lớp 2. HÌNH 20-2 Hình 20-2 Các PDF có điều kiện 20.4.1.2. Định lý Bayes Trước khi một đối tượng được xác định, ta chỉ biết nó chỉ gồm xác suất tiên nghiệm của biểu thức (10). Tuy nhiên, sau khi xác định, ta có thể sử dụng số đo và 406
  7. các PDF có điều kiện để chứng tỏ hiểu biết của ta về thành viên lớp của đối tượng. Sau khi xác định, cái gọi là xác suất hậu nghiệm để đối tượng thuộc lớp i được cho bởi định lý Bayes; tức là, p x | C i PC i  PC i | x   (11) p x  trong đó 2 p x    p  x | C i PC i  (12) i 1 là hệ số chuẩn hoá cần thiết để tạo thành tổng các xác suất hậu nghiệm có tổng bằng 1. Định lý Bayes cho phép ta kết hợp xác suất tiên nghiệm của thành viên lớp, PDF có điều kiện và phép đo cần thiết để tính toán, đối với từng lớp, xác suất để xác định đối tượng thuộc lớp nào. Với những thông tin dã cho này, ta có thể ấn định mỗi đối tượng với lớp có khả năng chứa nó nhiều nhất. Trong ví dụ sắp xếp trái cây, ta ấn định đối tượng cho lớp 1 (ví dụ, ta sẽ gọi nó là anh đào) nếu PC1 | x   PC 2 | x  (13) và ấn định nó cho lớp 2 (táo) nếu trái lại. Thay thế định lý Bayes [biểu thức (10)] vào biểu thức (13) nhân với mẫu số chung, ta được p x | C1 PC1   p x | C 2 PC 2  (14) giống như điều kiện giả định lớp 1 chứa trái cây đường kính x. Tại ngưỡng quyết định, biểu thức (14) xuất hiện dấu đẳng thức, ta có thể ấn định các đối tượng cho các lớp tuỳ ý. Bộ phân lớp định nghĩa bởi quy tắc quyết định này là bộ phân lớp có thể đúng tối đa (maximun-likelihood). Trường hợp tổng quát. Giả sử ta không tiến hành không phải chỉ một mà là n phép tính trên mỗi đối tượng. Thay vì là một giá trị đặc trưng đơn lẻ, ta có một vec tơ đặc trưng [x1, x2, …, xn]T, và mỗi đối tượng được xác định tương ứng với một điểm trong không gian đặc trưng n chiều. Cũng giả thiết rằng không phải chỉ có hai mà là m lớp đối tượng. Với những điều kiện đó, xác suất tiên nghiệm của thành viên lớp i theo định lý Bayes là p x1 , x 2 ,..., x n | C i PC i  pC i | x1 , x 2 ,..., x n   m (15)  p x , x i 1 1 2 ,..., x n | C i PCi  trong đó các PDF có điều kiện bây giờ là n chiều. 20.4.1.3. Rủi ro Bayes Mỗi khi ta ấn định một đối tượng cho một lớp, điều rủi ro là ta tạo ra một sự sai lạc. Trong bài toán đa lớp, một vài sự phân lớp nhầm có thể gây tai hại hơn điều khác. Một phương pháp được đưa ra để làm sáng tỏ, đó là hàm giá. Đặt lij là giá (hay “sự mất mát”) của việc ấn định một đối tượng vào lớp i khi nó thực sự thuộc vào lớp j. Thường thì lij sẽ nhận giá trị 0 với mọi quyết định chính xác (i = j), nhận các giá trị nhỏ đối với các lỗi vô hại và nhận các giá trị lớn hơn đối với các sai lầm nghiêm trọng hơn. Rủi ro Bayes là một cái giá lâu dài do hoạt động của bộ phân lớp. Rủi ro được đánh giá bằng tích phân hàm giá có trọng số xác suất. 407
  8. Giả sử ta xác định một đối tượng và ấn định nó cho lớp i. Mất mát xảy ra từ giả định này là sự rủi ro có điều kiện m RC i | x1 , x 2 ,..., x n    lij pC j | x1 , x 2 ,..., x n  (16) j 1 là giá được lấy trung bình trên toàn bộ m nhóm thực sự chứa đối tượng. Vì vậy, cho vec tơ đặc trưng, có một sự rủi ro nào đó hàm ý trong việc ấn định đối tượng cho nhóm bất kỳ. 20.4.1.4. Quy tắc Bayes Quy tắc quyết định Bayes phát biểu rằng mỗi đối tượng phải được ấn định cho một lớp mà lớp đó tạo ra sự rủi ro có điều kiện nhỏ nhất. Nếu thực hiện quy tắc này, ta có thể đặt Rm(x1, x2, …, xn) bằng sự rủi ro nhỏ nhất tương ứng với vec tơ đặc trưng [x1, x2, …, xn]T. Toàn bộ sự rủi ro dài hạn đối với hoạt động của bộ phân lớp với quy tắc quyết định Bayes gọi là rủi ro Bayes. Điều này có được bằng cách tích phân hàm rủi ro trên toàn bộ không gian đặc trưng  R   R m  x1 , x 2 ,..., x n  p x1 , x 2 ,..., x n dx1 dx 2 ...dx n (17)  Rõ ràng, không có một quy tắc nào khác có thể giảm Rm(x1, x2, …, xn) tại một điểm bất kỳ và sự rủi ro toàn bộ được tối thiểu hoá bằng quy tắc quyết định Bayes. 20.4.2. Các loại bộ phân lớp Đó là điều cần thiết để phân bệt các loại bộ phân lớp khác nhau trên cơ sở cái đã biết về nền tảng thống kê và cái phải được đánh giá. Các bộ phân lớp tham số và không tham số. Nếu đã biết dạng hàm của các PDF có điều kiện, nhưng một vài tham số của hàm mật độ (giá trị trung bình, độ biến thiên,…) là chưa biết, thì bộ phân lớp được gọi là tham số. Bởi vì các xác suất tiên nghiệm cũng là các tham số, nên chúng có thể là chưa biết. Với các bộ phân lớp tham số, dạng hàm của các PDF có điều kiện sẽ được giả thiết, trên cơ sở của một nền tảng tri thức nào đó về bản thân các đối tượng. Thường thì các dạng hàm được giả thiết cho mục đích toán học cũng như các lý do thiết yếu hơn. Nếu chưa biết dạng hàm của một vài hay tất cả các PDF có điều kiện, thì bộ phân lớp được gọi là không tham số. Nghĩa là tất cả các PDF có điều kiện phải được đánh giá từ một tập dữ liệu huấn luyện. Để làm được điều đó cần có nhiều dữ liệu hơn viêc đánh giá đơn thuần một vài tham số trong PDF đã biết dạng hàm. Vì thế, kỹ thuật không tham số được sử dụng khi các kiẻu tham số thích hợp không có sẵn và khối lượng dữ liệu huấn luyện nằm trong phạm vi có thể. 20.4.3. Đánh giá tham số và huấn luyện bộ phân lớp Quá trình đánh giá các PDF có điều kiện hay các tham số của chúng dùng kích thước đối tượng được biết với cái tên huấn luyện bộ phân lớp. 20.4.3.1. Huấn luyện có giám sát và không có giám sát Nếu một đối tượng đã được phân lớp trước bởi một quá trình không sai sót nào đó, thì quá trình đó được gọi là huấn luyện có giám sát. Với huấn luyện không giám sát, các PDF có điều kiện được đánh giá bằng các mẫu mà lớp của chúng là chưa biết. Các lớp, thậm chí số lớp, phải được xác định bằng cách định vị nhóm các điểm trong không gian kích thước. Đây gọi là phân tích nhóm. Huấn luyện không có giám 408
  9. sát thường chỉ được sử dụng khi nó không thuận tiện hay không có khả năng để có được một tập huấn luyện trước phân lớp hay khi số lớp và các đặc trưng của các lớp cũng chưa được xác định. Ở đây chúng ta sẽ nói về hai phương pháp tiếp cận thường dùng với huấn luyện có giám sát: kỹ thuật có thể đúng tối đa và kỹ thuật Bayes. Trong khi hai kỹ thuật khác nhau về tính triết học, thì chúng thường tạo ra các kết quả tương tự nhau. Các kết quả này giống nhau đến mức nào tuỳ thuộc vào tình huống đặc biệt. 20.4.3.2. Đánh giá có thể đúng tối đa Tiếp cận sự đánh giá có thể đúng tối đa giả thiết rằng các tham số được đánh giá là ổn định nhưng chưa biết. Một mẫu đã cho (tập huấn luyện) được vẽ và tham số đánh giá được coi như giá trị làm cho sự xuất hiện của tập huấn luyện là có khả năng xảy ra nhất. Ví dụ, giả thiết rằng 100 mẫu được vẽ từ sự phân bố chuẩn của các giá trị trung bình, với độ lệch tiêu chuẩn là 2. Giả thiết thêm rằng giá trị trung bình của 100 mẫu là 12. Dĩ nhiên, nó có vẻ phù hợp khi 100 mẫu có được từ nhóm mẫu có giá trị trung bình là 12 hơn là có được từ nhóm mẫu có giá trị trung bình là 0. mặc dù tình huống sau là có khả năng, nhưng nó yêu cầu một sự trùng khớp của các sự kiện không thể xảy ra. Nó có thể chứng tỏ rằng giá trị trung bình của nhóm mẫu cơ bản mà tạo ra giá trị mẫu quan sát trung bình có khả năng xảy ra nhất là 12. Đánh giá có thể đúng tối đa là một đề tài được phát triển toàn diện và nằm ngoài tầm kiểm soát của chúng ta. Ở đây chúng ta giới thiệu khái niệm và trích dẫn kết quả mà những đánh giá có thể đúng tối đa của giá trị trung bình và độ lệch tiêu chuẩn của một phân bố chuẩn là trung bình mẫu và độ lệch tiêu chuẩn mẫu được nhiều người biết đến. 20.4.3.3. Ước lượng Bayes Không giống như đánh giá có thể đúng tối đa, tiếp cận Bayes coi tham số chưa biết như một biến ngẫu nhiên. Hơn thế nữa, nó giả thiết là đã biết một chút gì đó về tham số chưa biết trước. Ước lượng Bayes giả thiết rằng tham số chưa biết có một PDF tiên nghiệm đã biết, hay giả thiết là đã biết, trước khi nhận được một mẫu bất kỳ. Sau khi xác định tập huấn luyện, định lý Bayes được sử dụng để cho phép các giá trị mẫu cập nhật, hay cải tiến, PDF tiên nghiệm. Điều này mang lại một PDF hậu nghiệm của giá trị tham số chưa biết. Chúng ta hy vọng rằng PDF này có một đỉnh hẹp đơn lẻ, tập trung vào giá trị thật sự của tham số. Một ví dụ về ước lượng Bayes, giả sử chúng ta muốn ước lượng trung bình của sự phân bố chuẩn với sự biến thiên đã biết. Trước khi xác định tập huấn luyện, chúng ta có thể sử dụng bất cứ nhận thức nào có sẵn để thiết lập một PDF tiên nghiệm trên giá trị trung bình đã biết. Ta gọi là hàm mật độ tiên nghiêm p(). Ta ký hiệu dạng hàm đã biết của PDF với giá trị trung bình chưa biết là p(x|). Điều này được phát biểu rằng, cho trước một giá trị đối với , thì ta sẽ biết p(x). Nếu X biểu diễn tập giá trị mẫu thu được bằng việc xác định tập huấn luyện, định lý Bayes sinh ra một PDF hậu nghiệm của  sau khi tập huấn luyện được xác định: p X |   p  p  | X   (18)  p X |   p d 409
  10. Cái mà chúng ta thực sự muốn là p(x|X), ước lượng tốt nhất của mật độ p(x), cho trước kích thước tập huấn luyện X. Một cách để đạt được ước lượng này là thiết lập PDF chung (hai chiều) giữa cả hai x và  với tích phân theo ; tức là,  p x | X    p x,  | X d (19)  Mật độ chung trong tích phân có thể được viết như một tích của hai PDF một chiều độc lập. Biểu thức (19) trở thành  p x | X    p x |   p  | X d (20)  Đây là kết quả mong muốn, vì p(x|) là dạng hàm được giả định và p(|X) là PDF hậu nghiệm của giá trị trung bình chưa biết từ biểu thức (18). Ví dụ. Để hiểu tác động của p(x|) lên p(x|X) như thế nào, giả sử rằng p(|X) có một đỉnh nhọn đơn lẻ tại  = 0. Nghĩa là nhận thức trước đây của chúng ta đã kết hợp với tập huấn luyện để xác định  trong phạm vi giới hạn hẹp xung quanh giá trị 0. Nếu đỉnh đủ nhọn thì chúng ta có thể xấp xỉ hoá p(|X) bằng một xung tại 0: p | X       0  (21) Thì biểu thức (20) trở thành  p x | X    p x |      0 d (22)  Theo tính chất chọn lọc của xung, biểu thức này là p x | X   p x |  0  (23) Biểu thức này phát biểu rằng 0 là ước lượng tốt nhất của giá trị trung bình chưa biết. Nói cách khác, giả sử rằng phân bố hậu nghiệm của một giá trị trung bình chưa biết, p(|X), có một đỉnh tương đối rộng xung quanh 0. Trong trường hợp này, p(x|X) trở thành trung bình trọng số của nhiều PDF, tất cả đều có các giá trị trung bình khác nhau trong lân cận của 0. Điều này có tác dụng làm mờ hay mở rộng p(x|X) để phản ánh tính không chắc chắn của chúng ta về giá trị trung bình. Như đã nói đến trước đây, ước lượng có thể đúng tối đa và ước lượng Bayes tạo ra kết quả tương tự, nhưng không giống nhau, trong nhiều trường hợp thường gặp. Ví dụ, cả hai phương pháp tiếp cận đều có xu hướng thiết lập giá trị trung bình chưa biết tại giá trị trung bình của tập huấn luyện. Ước lượng Bayes cho phép ta kết hợp một tri thức tiên nghiệm bất kỳ mà ta có với dữ liệu xác định của tập huấn luyện để ước lượng tham số chưa biết. Hơn nữa, độ rộng của p(|X) là một dấu hiệu cho biết mức độ ta đã ước lượng được tham số chưa biết. Sử dụng ước lượng Bayes. Để tổng kết, các bước trong ước lượng Bayes như sau. Thứ nhất, chúng ta giả định một PDF tiên nghiệm đối với tham số hay các tham số chưa biết. Thứ hai, chúng ta tổng hợp các giá trị mẫu từ tổ hợp các mẫu bằng cách tính tập huấn luyện. Thứ ba, chúng ta sử dụng định lý Bayes để cải tiến PDF tiên nghiệm thành PDF hậu nghiệm, dùng các giá trị mẫu. Cuối cùng, chúng ta tạo mật độ chung của x và tham số chưa biết với tích phân tham số để được ước lượng mong muốn của PDF. 410
  11. Nếu ta có những ý kiến vững chắc về những giá trị xác suất của tham số chưa biết, ta có thể giả định một PDF tiên nghiệm hẹp. Nói cách khác, nếu ta biết đôi chút về tham số, ta phải giả định một PDF tương đối rộng. Hiwuj quả của việc sử dụng các giá trị mẫu để cải tiến PDF tiên nghiệm được cho dưới dạng 1 1 n p  | X   p X |   p     p xi |   p   (24) c c i 1 Trong đó c là mẫu số của biểu thức (18) và  ký hiệu cho tích của n số hạng. Bởi vì n mẫu nhận được một cách độc lập nên xác suất rút ra từ toàn bộ tập huấn luyện đơn thuần là tích của các xác suất riêng lẻ rút ra từ từng mẫu. Nếu các mẫu được nhóm lại chặt chẽ xung quanh giá trị mẫu trung bình s, thì p(X|) có một đỉnh nhọn tại hay gần  = s. Nếu mật độ tiên nghiệm tương đối bằng phẳng trong vùng đó, thì  p x | X    p x |  p  X |   p d (25)  Hàm p(x|) là dạng được của PDF giả định với  như một tham số. Cho đến khi tích phân trong biểu thức (25) được xét đến, thì p(x|) là một hàm của x và . Hàm p(X|) là xác suất mà tập mẫu X xảy ra nếu PDF quả thực có giá trị trung bình . Nó được cho bởi biểu thức (24), là hàm của  và trở nên nhọn lên dần khi n tăng. Tri thức tiên nghiệm của chúng ta về tham số  chưa biết được cho bởi p(), nó là PDF tiên nghiệm được giả định của giá trị trung bình chưa biết. Tri thức tiên nghiệm. Bây giờ chúng ta xem xét hai trường hợp minh hạo vai trò của tri thức tiên nghiệm và tập huấn luyện trong ước lượng Bayes. Trong trường hợp 1, chúng ta có những cảm nghĩ vững chắc về giá trị của và ta có một lượng tương đối nhỏ các mẫu trong tập huấn luyện. Nghĩa là ta sẽ giả thiết rằng p() là hẹp xung quanh 0, ý kiến nhận thức trước của chúng ta về giá trị trung bình. Nếu n nhỏ, p(X|) sẽ rộng xung quanh giá trị mẫu trung bình s. Sau đó biểu thức (25) có thể được xấp xỉ hoá bằng p x | X    p  x |      0 d  p  x |  0  (26) Biểu thức này chỉ ra rằng ước lượng của PDF chưa biết là cơ sở của dạng tham số giả định, với giá trị nhận thức trước 0 thay thế cho giá trị trung bình. Trong trường hợp thứ hai, giả sử chúng ta không có những cảm nghĩ vững chắc về giá trị trung bình và chúng ta dùng một tập huấn luyện lớn. Vì thế, chúng ta giả định p() là rộng xung quanh s, giá trị mẫu trung bình. Khi đó ước lượng Bayes của PDF chưa biết là p x | X    p  x |      s d  p  x |  s  (27) Trong trường hợp này, tập huấn luyện lớn đã chế ngự ước lượng tiên nghiệm rụt rè của chúng ta và thay thế giá trị mẫu trung bình vào dạng giả định của PDF chưa biết. Vì thế, khi số lượng mẫu tăng thì ước lượng cuối cùng của giá trị trung bình di chuyển ước lượng khởi gán 0 của chúng ta về phía giá trị mẫu trung bình s. Độ tin cậy tiên nghiệm của chúng ta được biểu diễn bởi độ sắc nét của p(): hàm này sắc nét hơn, ước lượng di chuyển về phái s chậm hơn so với sự tăng n. 411
  12. Ước lượng có thể đúng tối đa cho phép chúng ta sử dụng tập huấn luyện để ước lượng giá trị trung bình chưa biết. Ước lượng Bayes cho phép chúng ta kết hợp tri thức tiên nghiệm của chúng ta với tập huấn luyện để ước lượng giá trị trung bình chưa biết. Nếu tri thức tiên nghiệm của chúng ta sơ sài so với tri thức biểu hiện trong tập huấn luyện, thì cả hai phương pháp đều có xu hướng hội tụ về phía giá trị mẫu trung bình. 20.4.3.4. Ví dụ về huấn luyện bộ phân lớp Chúng ta kết thúc thảo luận về sự phân lớp thống kê bằng một ví dụ minh hoạ sự huấn luyện một bộ phân lớp. Các đối tượng được phân lớp là những nhiễm sắc thể người. Dưới kính hiển vi quang học, 46 nhiễm sắc thể từ nhân của một tế bào bạch huyết người (tế bào bạch cầu) xuất hiện rải rác không thành hàng [hình 23-3a]. Bổ thể 46 nhiễm sắc thể đã biết bao gồm 22 cặp giống nhau về mặt hình thái học, các nhiễm sắc thể tương đồng và hai nhiễm sắc thể xác định giới tính (XX là nữ và là nữ và là nam). Hai tay dài và hai tay ngắn của mỗi nhiễm sắc thể nối nhau tại trung đoạn của nhiễm sắc thể đó. Đối với mục đích chẩn đoán, thông thường người ta sắp xếp các ảnh nhiễm sắc thể thành các nhóm có cùng hình thái học. Sự sắp xếp này tạo ra kiểu tế bào của hình 20-3b. Các nhóm được đặt tên từ A đến G. Khuôn dạng hiển thị này thuận tiện việc nghiên cứu hình ảnh các nhiễm sắc thể khác thường hay bị thiếu. Các kỹ thuật chuẩn bị mẫu vật hiện nay có khả năng nhuộm các nhiễm sắc thể sao cho có thể phân biệt tất cả 24 kiểu, nhưng ví dụ này tốt hơn là dùng để minh hoạ các ý chính của thảo luận. HÌNH 20-3 Hình 20-3 Nhiễm sắc thể người: (a) ảnh hiển vi đã số hoá; (b) kiểu tế bào Giống như công việc nhận dạng mẫu, công việc của chúng ta đơn thuần chỉ là ấn định mỗi nhiễm sắc thể vào một trong bảy nhóm, từ A đến G. Chúng ta sẽ xác định hai đặc trưng của từng nhiễm sắc thể: tổng chiều dài và tỷ số chiều dài cánh tay. Đặc trưng sau được gọi là chỉ số trung đoạn và là tỷ số của chiều dài cánh tay dài với tổng chiều dài. Hình 20-4a cho thấy lược đồ hai chiều kích thước cuat 2.300 nhiễm sắc thể tìm tháy trong một tập có 50 tế bào thường. Trong không gian đặc trưng hai chiều, toạ độ là chiều dài nhiễm sắc thể, trong khi tung độ là chỉ số trung đoạn. Mức xám được biểu thị bằng sự kết hợp đạo hàm hình dạng với các đường viền. Lược đồ đã được làm hơi trơn bằng tích chập với một bộ lọc thông thấp. Nhiều nhóm hiển nhiên cho biết khác nhau về hình thái giữa các cặp tương đồng. 412
  13. Hình 20-4b tđưa ra một lược đồ tương tự cho các nhiễm sắc thể thuộc nhóm C. Tập con các nhiễm sắc thể được nhận biết bằng một nhà di truyền học có kinh nghiệm. Lược đồ của tất cả các nhiễm sắc thể ngoài nhóm C cho trong hình 20-4c. Việc huấn luyện bộ phân lớp trong trường hợp này bao gồm phân chia không gian đặc trưng thành các vùng rời nhau, mỗi vùng cho một nhóm loại tế bào. lược đồ đã làm trơn trong hình 20-4b có thể được coi như ước lượng chưa chuẩn hoá của PDF đối với nhiễm sắc thể nhóm C. Nó có thể được viết như sau f c  x, y   Np C  p x, y | C  (28) Trong đó N (= 50) là số các tế bào trong tập huấn luyện, p(C)là xác suất tiên nghiệm mà một nhiễm sắc thể chưa được xác định thuộc nhóm C và p(x, y|C) là PDF đối với các nhiễm sắc thể nhóm C. Các loại tế bào giống đực thường có 15 và tế bào giống cái có 16 nhiễm sắc thể thuộc nhóm C, bao gồm các nhiễm sắc thể X. Vì thế, nếu các nhiễm sắc thể đực và cái bằng nhau thì xác suất tiên nghiệm là 15.5 pC   (29) 46 HÌNH 20-4 Hình 20-4 PDF nhiễm sắc thể: (a) toàn bộ các nhiễm sắc thể; (b) chỉ có nhóm C; (c) các nhiễm sắc thể không thuộc nhóm C; (d) vùng quyết định nhóm C Biểu thức (14) đưa ra quy tắc quyết định đối với bộ phân lớp có thể đúng tối đa. Nghĩa là chúng ta phải ấn định một nhiễm sắc thể với các giá trị đặc trưng (x, y) cho nhóm C nếu lược đồ của hình 20-4b tại (x, y) lớn hơn lược đồ của hình 20-4c. Chúng ta có thể nhận biết vùng có thể đuúng tối đa này bằng cách láy ảnh số của hình 20-4b trừ cho ảnh số của hình 20-4c. Vùng này được trình bày trong hình 20-4d đối với nhóm C. Một thủ tục tương tự cho các nhóm khác tạo ra sự phân lớp thể hiện trong hình 20-5. HÌNH 20-5 413
  14. Hình 20-5 Phân lớp nhiễm sắc thể 20.4.4. Hiệu suất của bộ phân lớp Có nhiều phương pháp để đánh giá hiệu suất của một bộ phân lớp sau khi nó đã được thiết kế và huấn luyện. Nếu số chiều của nó thấp và đã biết PDF hay có thể giả định thì ta có thể tính xác suất của sai số như diện tích đoạn cuối. Ta cũng có thể thao tác bộ phân lớp trên một tập thử nghiệm đã biết, tốt nhất là trên một tập khác tập huấn luyện. Giống như một quy tắc tổng quát, trong nhận dạng mẫu ứng dụng cho các ảnh số, chất lượng ảnh hạn chế độ tin cậy của các phép đo và điều này hạn chế độ chính xác của sự phân lớp bằng cách phủ chồng các PDF. Chất lượng ảnh bị suy giảm do các thiết bị quang học, nhiễu và sự biến dạng. Chúng kết hợp với tính chất có thể thay đổi của các đối tượng trong lớp để mở rộng các PDF. Sự phân lới phải gần đúng đối với bài toán, nhưng một bộ phân lớp phức tạp hơn sẽ không nhất thiết thực hiện tốt hơn một bộ phân lớp đơn giản. Phủ chồng các lớp trong không gian đặc trưng thiết lập giới hạn cơ bản dựa vào sự chính xác của bộ phân lớp: tuy phức tạp, nhưng không một bộ phân lớp nào có thể phân biệt hai đối tượng có kiểu khác nhau khi chúng có cùng một giá trị kích thước. 20.5. MẠNG NƠ RON Một tiếp cận khác để nhận dạng mẫu đã thu hút mối quan tâm đáng kể trong những năm gần đây mới ra đời là kỹ thuật mạng nơ ron nhân tạo. Ban đầu nó xuất phát từ ý tưởng của các hệ thống thần kinh sinh học, sự phát triển mạng nơ ron nhân tạo gầy đây đã được thúc đẩy hơn bởi khả năng ứng dụng của chúng với một loại bài toán nào đấy và tiềm năng của chúng đối với các phép xử lý song song. Trong số đó nổi bật lên một số kiểu mạng có khả năng huấn luyện có gián sát và không giám sát trong các bài toán nhận dạng mẫu. 20.5.1. Kiến trúc mạng nơ ron Một mạng nơ ron là một tập hợp các nút giống hệt nhau, hay các phần tử xử lý (PE), nối liền nhau, hoạt động của mỗi nút tương đối đơn giản. Mỗi PE nhận các đầu vào từ nhiều PE “ngược dòng” khác trong mạng, tạo ra một đầu ra vô hướng và gửi nó “xuôi dòng” đến một nhóm PE khác. Giản đồ nối liền nhau, hay kiến trúc mạng, là một trong những lựa chọn thiết kế chủ yếu. Các PE thường được tổ chức thành các tầng. Số lượng PE trong mỗi tầng tuỳ chọn khi thiết kế. Trong một vài mạng, mỗi PE trong một tầng nhận đầu vào từ mọi PE trong tầng trước đó và gửi đầu ra của nó đến mọi PE trong tầng tiếp theo. Tuy nhiên, một vài kiến trúc mạng cho phép liên lạc giữa các PE trong cùng một tầng và thậm chí kiến trúc phản hồi còn cho phép truyền ngược về các PE trong các tầng trước. Tầng cuối cùng được gọi là tầng ra và tất cả các tầng khác đều có tên là tầng ẩn. 20.5.2. Phần tử xử lý (PE) Phần tử xử lý cơ bản của một mạng nơ ron hoạt động khá đơn giản. Nó đơn thuần là tổng các tích của vec tơ đầu vào và một vec tơ trọng số, biến đổi kết quả theo một hàm biến đổi sigma, và đưa ra kết quả (vô hướng). Kết quả này sau đó đi tiếp để trở thành đầu vào của một hay nhiều PE khác thông qua các kết nối mạng. Hình 20-6 miêu tả một phần tử xử lý điển hình. 414
  15. Quá trình xử lý thực tế được thực hiện bởi một PE có thể được miêu tả như một hàm tích điểm; tức là, N    O  g X T  W  g  xi wi   g S  (30)  i 1  Trong đó O là đầu ra, X là vec tơ đầu vào và W là vec tơ trọng số kết hợp với PE đã cho. Các trọng số sử dụng trong tổng này là các tham số được điều chỉnh trong suốt quá trình huấn luyện, sau đó chúng vẫn được sử dụng như ban đầu. Tổng trọng số tuỳ thuộc vào một phép biến đổi phi tuyến theo hàm kích hoạt. Đây là một hàm có dạng sigma. Nó sẽ đơn điệu tăng, có thể vi phân, và tiệm cận tới 0 và 1 tại các đối số mang giá trị âm và dương lớn . mục đích chủ yếu của nó là hạn chế đầu vào của PE vào khoảng [0,1]. Dạng hàm g là một thiết kế tuỳ ý và nó có thể sử dụng ảnh đáng kể của mình lên hành vi của mạng. Theo quy ước, các đầu vào là dương, nhưng các trọng số kết nối có thẻ là dương (gia tăng) hay âm (hạn chế). HÌNH 20-6 Hình 20-6 Giản đồ của một phàn tử xử lý Trong một bài tập huấn luyện (có giám sát), các vec tơ đặc trưng của các đối tượng đã biết từ tập huấn luyện được biểu thị theo thứ tự ngẫu nhiên trong mạng. Các trọng số kết nối của các PE được điều chỉnh không đáng kể mối lần, sử dụng một quy tắc huấn luyện cố định, hướng đầu ra của mạng theo hướng có giá trị đúng. Khi tiến hành huấn luyện, cải tiến sự thực hiện, đến khi cuối cùng mạng hội tụ về tập các trọng số hoàn chỉnh đối với mối PE. 20.5.3. Hoạt động của mạng nơ ron Trong ứng dụng nhận dạng mẫu, đầu vào mạng là vec tơ đặc trưng của đối tượng chưa biết. Vec tơ đặc trưng được biểu thị bằng từng PE trong tầng thứ nhất của mạng. Thường thường vec tơ đặc trưng tăng thêm một phần tử luôn bằng 1. Điều này cung cấp thêm một trọng số và tổng như một đoạn bù trong hàm họat hoá. Thông tin đầu vào sau đó truyền qua ns tầng khác nhau cho đến khi một vec tơ đàu ra xuất hiện tại tầng ra. Đối tượng chưa biết được ấn định cho lớp được xác định bằng cách này hay cách khác theo vec tơ đầu ra. Sau đó mạng chấp nhận một vec tơ đặc trưng như đầu vào và tạo ra một vec tơ đầu ra đánh dấu một giá trị thành viên tương ứng với lớp chứa đối tượng chưa biết. 415
  16. Ví dụ, trong bài toán bốn lớp khi một đối tượng lớp hai biểu thị cho mạng, vec tơ đầu ra chính xác là [0100]. Nói chung, kết quả sẽ không bị cắt hoàn toàn, nhưng hy vọng rằng đầu ra của nút 2 ít ra sẽ vượt quá đối thủ của nó. Sau khi định nghĩa PE và kiến trúc kết nối được cố định, hoạt động của mạng đượ xác định bởi các trọng số theo nhangd kết nối các phần tử. Giá trị của các trọng số kết nối được điều chỉnh trong suốt quá trình huấn luyện mạng và được coi là hằng số khi mạng hoạt động trong chế độ sản xuất. Hầu hết các ứng dụng hiện tại của mạng nơ ron đều được thực hiện bằng trạng thái số. Chúng ds phần mềm hay các chíp xử lý tín hiệu số (DPS) để mô phỏng phần mềm đối với kiến trúc mạng đã chọn và sau đó huấn luyện mạng. Trong một tình trạng số bất kỳ của một nhóm PR kết nối, có một đòi hỏi về thứ tự xử lý, đó là chuỗi các phần tử được cập nhật. Vì thế, quy tắc cập nhật là một nhân tố thiết kế quan trọng của một mạng nơ ron. 20.5.4. Thực hiện mạng nơ ron Những lợi thế thường gặp nhất thuận lợi cho một mạng nơ ron tiếp cận với nhận dạng mẫu là (1) nó đòi hỏi ít hiểu biết về bài toán đầu vào hơn các phương pháp tiếp cận lhác, (2) nó có khả năng thực hiện công việc phân chia không gian đặc trưng phức tạp hơn và (3) nó tuân theo sự thực hiện xử lý song song hiệu suất cao. Chủ trương của tiếp cận này cũng chỉ ra các khả năng nhận dạng mẫu đáng kinh ngạc của bộ não người, gợi ý rằng các mạng nơ ron nhân tạo có thể có khả năng tiến tới mức hiệu suất đó. Tuy nhiên, sự thực hiện nhận dạng mẫu kiểm tra kỳ hạn thường có xu hướng chỉ tiến đến hiệu suất của các bộ phân lớp thống kê thiết kế tốt. Những bất lợi của giải pháp mạng nơ ron, so với các phương pháp tiếp cận thống kê, bao gồm (1) khối lượng huấn luyện yêu cầu rộng rãi, (2) hoạt động chậm hơn khi thực hiện như một giải pháp trên máy tính thường và (3) không có khả năng hiểu chi tiết quá trình quyết định đang được sử dụng (chẳng hạn, các mặt quyết định trong không gian đặc trưng). Những nguyên tắc cơ bản trong phạm vi hoạt động ở đây là (1) một bộ phân lớp bất kỳ, tuy được thực hiện, đơn thuần là phân chia không gian đặc trưng thành nhiều vungd tương ứng với từng lớp và ấn định các đối tượng theo đó, và (2) hiệu suất của một lớp bị giới hạn sau cùng bởi sự phủ chồng các lớp trong không gian đặc trưng. Chúng kết hợp với khó khăn thực tế thừ việc thu nhận một tập huấn luyện tiêu biểu và sử dụng nó để thiết lập các bề mặt phân chia tối ưu, để thiết lập các quy tắc nhóm cho việc phát triển bộ phân lớp. Một mạng nơ ron sẽ nổi bật khi nó đã được huấn luyện để cắt nhỏ không gian đặc trưng tốt hơn so với một bộ phân lớp thống kê có thể làm. Dù có như thế thì hiệu suất của nó cơ bản vẫn bị ràng buộc bới sự phủ chồng các lớp. Tiếp theo, chúng ta sẽ giới thiệu hai mạng tuân theo sự nhận dạng mẫu: mạng lan truyền ngược và mạng phản lan truyền. Các ứng dụng của mạng nơ ron đối với các bài toán trong các lĩnh vực khác không được đưa ra như lĩnh vực nhận dạng mẫu. 20.5.5. Mạng lan truyền ngược (Backpropagation Network) Cấu hình tiêu chuẩn cho một mạng lan truyền ngược hai tầng được cho trong hình 20-7. Số lượng PE trong mỗi tầng thay đổi theo ứng dụng. Có thể thêm nhiều tầng ần vào giữa tầng ẩn đầu và và tầng ra. Chúng ta giả thiết ở đây là các vec tơ có giá trị nằm giữa 0.1 và 0.9. 416
  17. Khi mạng hoạt động, mỗi PE trong lớp ẩn thạo thành một tích điểm giữa vec tơ trọng số và vec tơ đầu vào. Tổng trọng số thu được, S, sau đó được biến đổi bởi hàm kích hoạt 1 g S   (31) 1  es Đây là hàm sigma có khả vi tiệm cận đến 0 và 1 tại hai đầu mút đối số của nó. Vec tơ xuất phát từ tầng ẩn đến tầng ra, trong đó các PE xử lý nó theo cùng một cách và tạo ra vec tơ tổng hợp. 20.5.5.1. Huấn luyện bộ phân lớp Khi bắt đầu huấn luyện, tất cả các trọng số trong mạng được gán cho một giá trị ngẫu nhin trong khoảng [-0.5, +0.5]. Tất cả các vec tơ đầu vào được lấy tỷ lệ sao cho các giá trị nhỏ nhất và lớn nhất của một thành phần bất kỳ phải bằng 0.1 và 0.9. Một mẫu huấn luyện là một vec tơ đầu vào đặc biệt và vec tơ đích tương ứng của nó. Một trong số đó được chọn ngẫu nhiên từ tập huấn luyện và vec tơ đầu vào được truyền qua mạng. Sau đó kết quả đầu ra được so sánh với vec tơ đích, các trọng số liên kết giữa tầng ẩn và tầng ra được điều chỉnh theo cách đã đề cập ở trên để làm cho vec tơ đầu ra gần vec tơ đích hơn. Sau cùng, tầng ẩn trung gian nằm dưới tầng ra cũng được điều chỉnh tương tự. HÌNH 20-7 Hình 20-7 Mạng lan truyền ngược Trong khi hình 20-7 chỉ đưa ra một mạng hai tầng thì nói chung một mạng có thể sử dụng một lượng tầng bất kỳ. Chúng ta sẽ sử dụng thuật ngữ tổng quát hơn trong bảng 20-1 để thảo luận về huấn luyện lan truyền ngược dưới đây Quá trình huấn luyện tiến hành từ trên xuống dưới, bắt đầu với các PE trong tầng ra. Khối lượng điều chỉnh trọng số thứ i tại nút đầu vào thứ j của tầng ra (k = N) là   wijN   jN g ' S jN OiN 1 (32) Trong đó sai số  jN  t j  O jN (33) Là độ chênh lệch giữa phần tử thứ j của vec tơ đích (ví dụ đầu ra mong muốn) và giá trị ra thực sự của nút j trong tầng ra. 417
  18. Biểu thức (32) được biết đến như quy tắc delta tổng quát hoá. Nó dựa trên phương pháp giảm gradient. Khối lượng điều chỉnh [biểu thức (32)] là tỷ lệ phần trăm  nào đó của sai số jN, tại nút đầu ra, nhân với độ dốc của hàm kích hoạt g’(SjN), nhân với phần tử thứ j của vec tơ đầu ra từ tầng ẩn trước đó. BẢNG 20-1 THUẬT NGỮ TRONG MẠNG LAN TRUYỀN NGƯỢC BẢNG 20-1 Tiếp đến, các trọng số tại đầu vào mỗi nút trong tầng ẩn đèu được điều chỉnh bằng một lượng   wijk   jk g ' S jk Oik 1 (34) Biểu thức này tương tự biểu thức (32), ngoại trừ số hạng sai số jk biểu diễn sai số tập trung bởi tất cả các nút; tức là, N k 1  jk  w i 1  ik 1 ijk 1 (35) Nếu có nhiều hơn hai tầng, quá trình huấn luyện sẽ xử lý liên tục từ đầu ra đến đầu vào, từng tầng một, sử dụng biểu thức (34) và (35). Trong quá trình huấn luyện các sai số được lan truyền ngược qua mạng theo cách tương tự lan truyền xuôi của dữ liệu đầu vào xuất hiện trong hoạt động bình thường. Các sai số lan truyền ngược lại và kết quả của sự lan truyền này hướng dẫn việc điều chỉnh các trọng số kết nối. Quá trình được lặp lại cho tất cả các cặp vec tơ đầu vào và vec tơ đích còn lại. sau đó nó cũng được lặp lại cùng số lần đối với tập huấn luyện của nó, cho đến khi sai số trên toàn bộ các vec tơ đầu vào nằm dưới một ngưỡng cho sẵn. Tại giai đoạn huấn luyện bất kỳ, sai số tổng thể xác định được là NN P 2   j 1 p 1 jp E RMS  (36) PN N Trong đó P là số mẫu trong tập huấn luyện, NN là số nút đầu ra và jP = tjP - OjP là sai số, đối với mẫu đầu vào thứ p, giữa các phần tử thứ j của vec tơ đích và vec tơ đầu ra. Việc cập nhật các biểu thức (34) và (35) bằng cách vi phân số đo sai số này theo các trọng số kết nối. Khối lượng mà các trọng số được cập nhật đơn giản là tỷ lệ với 418
  19. gradient âm của ERMS. Như là một kết quả, mỗi lần cập nhật di chuyển mạng theomột bề mặt sai, luôn theo chiều giảm nhanh nhất. Bề mặt “thung lũng” sai mà trong đó những bố trí mạng cuối cùng có thể không phải là cách bố trí khó hiểu nhất. Tức là, mạng có thể hội tụ về một sai số tối thiểu cục bộ thay vì tối thiểu tổng thể, như mong muốn. Tuy nhiên, nếu sai số nàyđủ thấp thì sự thực hiện vẫn có thể chấp nhận được. Nếu cần thiết, ta có thể huấn luyện lại mạng bằng cách sử dụng tập các trọng số khởi gán ngẫu nhiên khác nhau để khởi động mạng tại một vị trí khác trên bề mặt sai, nhờ đó mà cỉa tiến khả năng tìm kiếm sự tối thiểu tổng thể hay ít ra cũng thấp hơn sự tối thiểu cục bộ của nó. Ta cũng có thể thử huấn luyện một mạng thiết kế lại sử dụng số lượng các nút ẩn khác nhau. Trong suốt quá trình huấn luyện, ta có thể giám sát sai số RMS tại tầng ra (ví dụ các sai số từ vec tơ đích) đối với từng mẫu đầu vào. Theo kinh nghiệm, việc huấn luyện có thể dừng sau khi sai số RMS nằm xấp xỉ bên dưới 0.01. Một khi điều này đúng, thì mạng là hội tụ và “học được phép ánh xạ”. Sau đó các trọng số kết nối trở nên cố định, hiệu suất tổng thể của mạng có thể được kiểm tra và mạng được đặt vào chế độ hoạt động và sử dụng dữ liệu thực sự. 20.5.5.2. Huấn luyện xếp chồng (Overtraining) Quá trình huấn luyện có thể được phép tiếp tục trong một thời gian rất dài. nhắc lại rằng một hệ thống nhận dạng mẫu bất kỳ, thực hiện theo thống kê, mạng hay các phương tiện khác, đơn thuần chỉ làm nhiệm vụ phân chia không gian kích thước thành các vùng tương ứmg với các lớp khác nhau. Với bộ phân lớp Bayes, được thiết kế trên giả thiết thống kê chuẩn, việc phân chia được thực hiện bởi các mặt cong bậc hai trong không gian đặc trưng n chiều. Tính phức tạp của việc phân vùng vì thế mà có phần bị hạn chế bởi những giới hạn vốn có theo cách mà mặt cong bậc hai có thể được quấn lại. Ta có thể hình dung một quá trình phân chia không gian đặc trưng trong đó mạng đã đặt một đường elip nhỏ xung quanh mỗi điểm ảnh trong một tập huấn luyện nhỏ. Dĩ nhiê, việc này sẽ tạo ra một sai số thấp trên tập huấn luyện, nói chung hiệu suất rất kém. Có thể tránh được việc huấn luyện xếp chồng bằng cách sử dụng một tập huấn luyện lớn và một tập kiểm tra khác với tập huấn luyện. Khi tỷ lệ sai số, xác định trên tập kiểm tra, dừng lại không giảm nữa và bắt đầu tăng thi việc huấn luyện xếp chồng đã bắt đầu. 20.5.5.3. Nghiên cứu thiết kế Kích thước mạng là một nghiên cứu quan trọng xuất phát từ quan điểm cả về hiệu suất lẫn tính toán. Nó đã được chứng minh rằng một tầng ẩn đủ để xấp xỉ hoá ánh xạ của một hàm liên tục bất kỳ và phần lớn hai tầng ẩn, nói chung đều cần thiết để xấp xỉ hoá một hàm bất kỳ. Số lượng PE trong tầng ẩn đầu tiên thường bị khống chế bởi ứng dụng. Khi một mạng lan truyền ngược được dùng để phân lớp các đối tượng, thì số lượng đó bằng chiều dài vec tơ đặc trưng. Cũng như vậy, số các nút trong tầng ra thường giống với số các lớp. Số các tầng ẩn tiếp theo và số các PE trong mỗi tầng như vậy đều là những chọn lựa khi thiết kế. Trong hầu các ứng dụng, số lượng PE là một phần nhỏ của số lượng đơn vị trong tầng đầu vào. Thường mong muốn giữ được lượng này nhỏ để giảm nguy hiểm cho huấn luyện xếp chồng. Nói cách khác, quá ít PE trong tầng ẩn có thể 419
  20. khiến cho mạng khó hội tụ về một quá trình phân chia không gian đặc trưng phức tạp một cách thích hợp. Khi một mạng đã hội tụ, nó có thể được rút ngắn về kích thước và được huấn luyện lại, thường đi kèm một sự cải tiến về hiệu suất toàn bộ. Giống như các bộ phân lớp thống kê, dữ liệu sử dụng cho huấn luyện phải là biểu diễn của mẫu trên toàn bộ không gian đặc trưng hợp lệ đối với mạng tương xứng để mô phỏng hàm mật độ xác suất của mỗi lớp. Nó cũng quan trọng để bảo đảm các mẫu huấn luyện được thể hiện ngẫu nhiên. Mạng phải có khả năng tổng quát hoá toàn bộ tập huấn luyện cùng một lúc, không phải mỗi lần một lớp riêng lẻ. Trình bày lớp các vec tơ một cách liên lục có thể dẫn đến sự hội tụ kém và sự tách lớp không đáng tin cậy. Huấn luyện trên các mẫu ngẫu nhiên sinh ra một kiểu nhiễu mà có thể đẩy mạng ra khỏi một mức tối thiểu cục bộ. Đôi khi nhiễu được thêm vào tập huấn luyện vì mục đích này và đã trợ giúp sự hội tụ của mạng. 20.5.6. Mạng lan truyền đếm (Counterpropagation Network) Kiến trúc lan truyền đếm được phát triển gần đây nhất khác với khái niệm kiến trúc mạng lan truyền ngược. Mặc dù thực hiện của mạng lan truyền đếm dễ hiểu hơn, nhưng nó thường đòi hỏi người thiết kế phải hiểu biết về vấn đề sâu sắc hơn so với mạng lan truyền ngược. Mạng lan truyền đếm có khả năng học không cần giám sát. Tức là, tập huấn luyện không cần phải được phân lớp trước. Giống như việc huấn luyện trước, mạng định vị sự xuất hiện tự nhiên của các nhóm điểm trong không gian đặc trưng và tạo ra các lớp trong số chúng. Trong các ứng dụng mà dữ liệu là mong đợi hay đã biết xuất hiện trong từng lớp riêng biệt, nhưng dữ liệu đầu vào được phân lớp trước một cách thích hợp không có sẵn, đây có thể là điều rất có ích. Kiến trúc nối kết đối với mạng lan truyền đếm ánh xạ tiến cũng giống như kiến trúc nối kết của mạng lan truyền ngược trong hình 20-7. Tuy nhiên, trong khi mạng lan truyền ngược có thể có nhiều tầng, thì mạng lan truyền đếm chỉ hạn chế ở hai tầng. Hơn nữa, hàm kích hoạt của mỗi PE là tuyến tính (không phải điều hoà) và đầu ra của nó đơn thuần là tích điểm của biểu thức (30). Một sự khác biệt quan trọng khác là kiểu quá trình thực hiện trong tầng ẩn. Tầng đó được gọi là tầng cạnh tranh bởi vì các nút của nó cạnh tranh để sinh ra một giá trị đầu ra. Nút ẩn nào tính toán cho ra kết quả lớn nhất sẽ chiến thắng cuộc đua và đưa ra giá trị là 1. Tất cả các nút ẩn khác đưa ra giá trị 0. Bởi vì duy nhất một nút ẩn tại một thời điểm được kích hoạt vad nó đưa ra một giá trị 1 tới tất cả các nút của tầng ra, đầu ra cuối cùng của mạng thực tế là một vec tơ trọng số kết nối từ tầng cao hơn. Các trọng số kết nối đó được nối kết với đầu ra của nút ẩn chiến thắng trở thành vec tơ đầu ra. Các trọng số của tầng ra có chức năng như một kiểu của bảng tra cứu, sinh ra đầu ra mong muốn mỗi khi một lớp được thừa nhận bởi một trong các nút ẩn. Khả năng nhận dạng mẫu của mạng lan truyền đếm được biểu hiện trong sự tính toán thực hiện bởi các PE của tầng ẩn. Do tính chất cạnh tranh của tầng ẩn mà sự tính toán đó phản ánh mức độ tương tự giữa vec tơ đầu vào và một vec tơ lý tưởng tương ứng với vec tơ trọng số liên kết của từng nút trong tầng ẩn. Nút có kết quả tính toán cao nhất sẽ là nút có vec tơ trọng số đầu vào giống với vec tơ đầu vào nhất. Các PE có thể sử dụng một trong hai phương pháp tính toán. Phương pháp phổ biến hơn, đã miêu tả trong phần lan truyền ngược trước đây, là tích điểm. Đây là độ lớn của phép chiếu một vec tơ lên một vec tơ khác. Do đó, tại một nút bất kỳtrong tầng ẩn, 420
nguon tai.lieu . vn