Perceptron - thuật toán Machine Learning đầu tiên

1. Giới thiệu về Perceptron

Cảm hứng

Perceptron chính là thuật toán machine learning đầu tiên. Nó được lấy cảm hứng từ chức năng của những neuron trong não.

Minh họa cho Perceptron

Nôm na, một neuron có thể nhận được tín hiệu từ các neuron khác, và dựa vào đó để ra quyết định là nó sẽ truyền tín hiệu đi hay không. Ở bản perceptron đầu tiên, thuật toán này nhận các số có giá trị là 0 hoặc 1 (nhận được hay không) và cho ra kết quả là 0 hoặc 1 (truyền đi dữ liệu hay không).

Ta có thể xét ví dụ sau: Ví dụ về perceptron

Ta có các input , và các hệ số . Ta đi tính giá trị

Nếu ( là một ngưỡng nào đó) thì ta sẽ truyền đi dữ liệu (output là 1), còn ngược lại thì không (output là 0).

Ta lấy ví dụ với ngưỡng , và . Khi đó . Như vậy, output là .

Sau này, perceptron đã được tổng quát hơn khi ta có thể cho vào các giá trị thực chứ không chỉ là 0 hoặc 1 (đầu ra vẫn là 1 trong 2 kết quả). Như vậy, Perceptron là một thuật toán supervised learning, cụ thể hơn chính là một binary classifier.

Linearly Separable

Trước khi đến phần tiếp theo, mình xin nhắc lại: mọi thuật toán Machine Learning khi được áp dụng cần có một giả định nào đó cho dữ liệu. Với Perceptron, ta dùng nó khi ta giả định dữ liệu có các tính chất:

• Có 2 class (Binary classification)
• Linearly separable.

Linearly separable nôm na có nghĩa là tồn tại một hyperplane có thể chia dữ liệu của chúng ta thành 2 nhóm, mỗi nhóm nằm hoàn toàn ở một phía của hyperplane.

Hyperplane của không gian chiều là một không gian con của nó có chiều. Ví dụ, đường thẳng (1d) là hyperplane của mặt phẳng, mặt phẳng là hyperplane trong không gian 3d.

Ví dụ về linearly separable

Rõ ràng, với giả định như thế, để phân loại dataset thì ta chỉ cần tìm cho ra một hyperplane thỏa mãn là xong. Và đó cũng chính là output của Perceptron, một hyperplane chia tách 2 class.

Sau đây ta sẽ lần lượt xây dựng vào giải quyết bài toán Perceptron.

2. Bài toán Perceptron

Phát biểu bài toán

Cho một dataset trong đó

Dựa trên dataset trên, ta muốn tìm các hệ số sao cho:

Hay

¹

Như vậy, ta cần tìm một model có dạng . Lưu ý rằng là phương trình của một hyperplane có vector pháp tuyến là , nên có thể nói rằng ta đang tìm một hyperplane.

Một tính chất toán học đã được giới thiệu qua (với trường hợp 2d và 3d) ở chương trình(2008) toán cấp 2, cấp 3 chính là: tất cả những điểm nằm ở cùng một phía của một hyperplane khi thay vào đều cho ra các giá trị có cùng dấu.

Đơn giản hóa

Có một trick để ta làm cho bài toán đơn giản hơn. Ta sẽ thay . Khi đó, phát biểu lại bài toán, ta chỉ cần tìm vector sao cho Tức là ta tăng số chiều dữ liệu lên 1 để giúp biểu thức đơn giản hơn. Một cách trực quan, điều này tức là chúng ta chỉ cần đi tìm các hyperplane đi qua gốc tọa độ.

Minh họa hình học cho trick trên

Tóm lại, ta chỉ cần tìm vector pháp tuyến .

Thuật toán

Đầu tiên ta cứ chọn là một vector bất kỳ. Ý tưởng của thuật toán Perceptron là lặp lại 2 việc sau đến khi tìm được :

1. Tìm một điểm M chưa được phân loại đúng
2. Điều chỉnh vector pháp tuyến sao cho về gần (hoặc là về luôn) đúng phía mà nó thuộc về.

Ta sẽ xử lý ý 2 như sau:

Đầu tiên, chú ý rằng:

• Một điểm chưa được phân loại đúng, tức là và không cùng dấu, hay , kéo theo , đồng nghĩa với việc góc giữa 2 vector và là góc có số đo không bé hơn .
• Ngược lại, nếu được phân loại đúng thì , hay góc giữa 2 vector và là góc có số đo bé hơn .

Như vậy, ta cần điều chỉnh sao cho góc giữa 2 vector và bé dần.

w* là vector đích, w là vector chúng ta cần điều chỉnh

Để làm được điều đó, ta thấy rằng chỉ cần di chuyển thành một nằm giữa và là xong. Khi đó, với nào đó (thật ra không phải bộ số nào cũng thỏa mãn, chứng minh ở dưới). Với thuật toán Perceptron, người ta đã chọn , điều này đảm bảo sau một số bước, sẽ về đúng phía mà nó thuộc về.

Tóm lại, ta có pseudocode như sau:

# Perceptron
w = 0
while True:
    isClassified = True
	
    for (x_i, y_i) in D:
        if y_i(x_i.w) <= 0:
            w = w + y_i * x_i # updating step
            isClassified = False
	
    if is Classified == True: break

Phần chứng minh cho việc thuật toán này dừng sẽ được trình bày ở phần sau.

Hãy tham khảo thêm về demo của perceptron ở đây.

3. Các chứng minh cho phát biểu ở trên (đọc thêm)

Chứng minh 1:

Nói lại, ta cần cập nhật vector thành vector với nào đó sao cho sau một số bước thì góc giữa 2 vector và có số đo nhỏ hơn . Đấy chính là mấu chốt. Tuy nhiên không phải nào cũng có thể được chọn. Sau đây ta sẽ tìm những bộ thỏa mãn.

Xét điểm cố định, và hiện đang bị phân loại chưa đúng. Ta có

Đặt , , như vậy ta có thể xét dãy số thỏa mãn: , đồng thời

Rõ ràng dãy số này biểu thị giá trị của đại lượng sau mỗi bước cập nhật cho điểm . Từ mệnh đề trên, ta có:

Kéo theo:

Xét riêng với thì:

Từ đây, ta có các nhận xét:

• Nếu hoặc thì , tức là sẽ có lúc nào đó .
• Nếu thì , tức là cũng sẽ đến lúc .
• Nếu :
  • Nếu thì , tức là cũng sẽ đến lúc .
  • Nếu thì dễ dàng chỉ ra , mặt khác ta cũng dễ chỉ ra là dãy đơn điệu (do ) nên là dãy giảm. Do đó không thể có để

Như vậy, trong thuật toán Perceptron, ta chỉ cần chọn là thuật toán sẽ hoạt động, còn nếu lấy thì phải chọn cho phù hợp.

Chứng minh 2 (Novikoff):

Ta sẽ chứng minh thuật toán được phát biểu bằng pseudocode ở trên dừng bằng phản chứng.

Giả sử, thuật toán trên không dừng, tức là với mọi số nguyên dương thì ở lần lặp thứ luôn tồn tại một điểm bị phân loại sai. Ta gọi chính là lúc khởi tạo, gọi là vector pháp tuyến ở ngay lúc bắt đầu vòng lặp thứ (). Khi đó . (1)

Vì dữ liệu của chúng ta là linearly separable, nên tồn tại hyperplane có vector pháp tuyến mà phân loại đúng, tức là . (2). Không mất tính tổng quát giả sử .

Ta có (3). Chú ý (2), ta được:

với . Kéo theo . (4)

Mặt khác, ta cũng có (Cauchy-Schwarz). Vì thế ta sẽ tìm cách đánh giá một cận trên cho .

Từ (3) ta cũng có:

với . Biến đổi dòng thứ 3 là nhờ (1). Từ đây ta suy ra , kéo theo . Như vậy (5).

Từ (4) và (5), suy ra: , tương đương với (vô lý). Như vậy điều giả sử là sai. Vậy thuật toán sẽ dừng.

Các bài báo có thể đọc thêm

• Bài báo đầu tiên cung cấp các lý thuyết toán học nền tảng cho perceptron (1943)
• Lần đầu trình bày thuật toán perceptron(1957)
• Chi tiết và mở rộng hơn paper năm 1957 ở trên(1958)
• Sách Perceptrons(1969)

Footnotes

1. Ta ký hiệu tích vô hướng của 2 vector và là . ↩