Giới thiệu

Bài toán nhận diện mẫu (pattern recognition ngày nay đã trở nên khá phổ biến. Ví dụ với bài toán nhận số chữ số viết tay. Giả sử mẫu các con số được lưu thành từng ảnh có kích thước 28x28. Như vậy, có khả năng có 28x28 = 748 biến thể có thể có trên bức ảnh. Nhiệm vụ của nhận dạng mẫu là ánh xạ 748 mẫu về tập số từ 0 đến 9, đồng thời bỏ qua các mẫu không phải là số.

Về mặt toán, bài nhận diện mẫu có dạng tổng quát là y = f(x). Với tập dữ liệu mẫu ban đầu input x₁, x₂, x₃, ..., x_n, output t₁, t₂, ..., tn cho trước đã biết, gọi là tập mẫu học (training set), mục tiêu của việc nhận dạng là tìm ra hàm xấp xỉ f tốt nhất có thể được (t_i gần đúng với y_i). Giả sử với xét y = f(x) trong không gian 2D như hình bên dưới:

Những chấm xanh tròn giả những cặp (x, y) trong training set. Đường màu xanh lá là hàm xấp xỉ f cần tìm.

Trong thực tế, x_i có thể có giá trị là vector/matrix chứ ít khi là một số.

Để xấp xỉ hàm f, công thức thường được dùng là đa thức:

Với M là bậc (order) của đa thức (polynomial). Từ những giá trị cho trước trong training set, mục tiêu đặt ra là phải tìm được các w_i sao cho hàm f có thể xấp xỉ được hàm cần tìm. Xét theo x, thì đa thức trên là không tuyến tính (linear). Tuy nhiên, nếu xét theo w thì lại là một hàm tuyến tính. Đặc điểm này là rất quan trọng, đường dùng để qui bài toán về bài toán đại số tuyến tính (linear algebra).

hệ số w (coefficients w) là viết tắt của weight, được biết đến với tên "trọng số".

Giả w đã được xác định, khi tính f(x_i, w) với x_i là một giá trị trong tập mẫu, sẽ cho kết quả xấp xỉ y_i (y_i không bằng t_i). Sai số giữa y_i và t_i được gọi là giái trị lỗi (error). Xét trên toàn tập training set, tổng lỗi được tính bằng công thức:

Công thức này được biết đến với tên gọi là sai số bình phương. Lúc này, việc bài toán xấp xỉ hàm f trở thành bài toán tìm w sao cho E(w) là cực tiểu (sai số ít nhất) - bài toán bình phương tối thiểu (least square). Giá trị 1/2 được thêm vào để tiện lợi cho việc tính toán sau này.

Có thể thấy E(w) là một hàm bậc 2 theo w (quadratic function), có đạo hàm (derivative) của nó theo w là một hàm tuyến tính theo w. Do đó, giá trị cực tiểu w* là duy nhất. Lúc này hàm f được chọn là y(x, w*)

Vấn đề còn lại là phải xác định được giá trị của M, bậc của đa thức y. Bậc của y không thể quá nhỏ hoặc quá lớn. Xét vị dụ với hàm cần xấp xỉ là hàm g(x) = sin(2*pi*x)

Trong hình minh họa trên, M được chọn lần lượt là 0, 1, 3, và 9. Trong trường hợp M = 0 hoặc M = 1, hàm xấp xỉ không cho được kết quả tốt (xấp xỉ 1 hình sin bởi một đường thẳng). Trong M = 3, kết quả tương đối khả quan, nhưng với M = 9, sai số tại những giá trị mẫu trong training set là rất thấp, song đây không phải là giá trị M ta cần tìm để xấp xỉ một hàm sin. Tình trạng này được gọi là over-fitting.

Việc chọn M phải đảm bảo được đặc tính phổ quát (generalization), tức khi có phát sinh một trường hợp mới (x', t'), giá trị xấp xỉ f(x') vẫn có giá trị tương đương t'. Nếu chọn M quá lớn, sẽ dẫn đến việc rơi vào tình trạng cá biệt chỉ đúng cho tập mẫu.

Trong trường hợp training set là một tập lớn, ta có thể tách thành 2 tập con, một tập vẫn được gọi là training set, tập kia gọi là test set. Ứng với mỗi M, tính E(w*) training set và test set. Trong trường hợp này, hàm sai số được dùng là root-mean-square, sai số sẽ có tính đến sự ảnh hưởng của số lượng phần tử trong tập.

Trong ví dụ bên dưới, hàm lỗi từ training set ngày càng giảm dần khi tăng M. Khi M = 9, lỗi đạt mức gần 0, tuy nhiên lỗi của tập test set tăng vọt. Đây là dấu hiệu của over-fitting.

Về mặt trực quan, khi xãy ra hiện tượng over-fitting, hàm y(x,w*) sẽ dao động (oscillation) với các điểm chốt là các giá trị của tập training set (xem hình trên)

Để đảm bảo tính chính xác của hàm xấp xĩ, tập dữ liệu mẫu phải đủ lớn. Với tập mẫu lớn, khả năng overfitting khi tăng M sẽ được giảm thiểu.