Perceptron từ đầu: một neuron thật sự tính gì

Một perceptron lấy các phép đo, nhân mỗi phép đo với một con số mà nó kiểm soát, cộng chúng lại, cộng thêm một con số nữa, rồi nhìn vào dấu.

Viết các phép đo của một linh kiện dưới dạng vector $\mathbf{x} = (x_1, x_2)$ — chiều rộng và khối lượng. Perceptron giữ một vector trọng số $\mathbf{w} = (w_1, w_2)$ và một bias $b$. Điểm số của nó là

và câu trả lời của nó là dấu của điểm số đó: chấp nhận nếu $s(\mathbf{x}) \geq 0$, nếu không thì loại.

Đó là toàn bộ mô hình. Mọi thứ perceptron từng biết về nhà máy nằm trong ba con số.

Phần hình học đáng để dừng lại một chút, vì đó là bức tranh sẽ tiếp tục hữu ích trong hai mươi chín chương tiếp theo, kể cả khi các phương trình không còn nằm gọn trên một dòng. Tập hợp các điểm nơi $s(\mathbf{x}) = 0$ — nơi perceptron đúng bằng trạng thái lưỡng lự — là một đường thẳng trong mặt phẳng. Ở một phía, điểm số dương và mọi thứ được chấp nhận; ở phía kia, điểm số âm và mọi thứ bị loại. Với perceptron, học nghĩa là di chuyển đường thẳng đó.

Hai sự thật về đường thẳng đó đi thẳng từ đại số ra, và cả hai đều quan trọng về sau:

• $\mathbf{w}$ vuông góc với nó. Vector trọng số không nằm dọc theo ranh giới, nó chỉ xuyên qua ranh giới, hướng về phía được chấp nhận.
• $b$ trượt nó đi mà không xoay nó. Không có bias, đường thẳng sẽ bị buộc phải đi qua gốc tọa độ; với một nhà máy đo milimét và gam, đó sẽ là một ràng buộc vô lý — nó có nghĩa là một linh kiện rộng bằng 0 và nặng bằng 0 nằm đúng trên hàng rào.

Perceptron bắt đầu mà không biết gì: $\mathbf{w} = (0, 0)$ và $b = 0$. Mọi điểm số đều bằng 0, nên nó chấp nhận mọi thứ.

Giờ hãy cho nó xem từng ví dụ một. Gán nhãn các linh kiện được chấp nhận là $y = +1$ và các linh kiện bị loại là $y = -1$. Với mỗi ví dụ, hỏi một câu: dấu có đúng không? Cách viết gọn câu hỏi đó là kiểm tra xem $y \cdot s(\mathbf{x})$ có dương hay không — nếu nhãn và điểm số cùng dấu, tích của chúng dương; nếu trái dấu, tích của chúng âm.

Nếu câu trả lời là có, không thay đổi gì. Nếu câu trả lời là không, đẩy nhẹ:

Đó là toàn bộ thuật toán, và đáng để hiểu vì sao đó là cú đẩy đúng thay vì học thuộc nó. Giả sử một linh kiện lẽ ra phải được chấp nhận ($y = +1$) nhưng điểm số lại âm. Cộng $\mathbf{x}$ vào $\mathbf{w}$ làm điểm số trên chính linh kiện đó thay đổi một lượng

là một số dương. Điểm số trên linh kiện mà nó vừa làm sai đi lên, đúng hướng nó cần đi. Quy tắc này không phải một mẹo heuristic ai đó đoán ra; nó là thay đổi nhỏ nhất có thể chứng minh là cải thiện trường hợp ngay trước mặt. Dĩ nhiên nó có thể làm hỏng một trường hợp khác, đó là lý do bạn đi vòng lại.

Hãy chú ý thứ vắng mặt. Không có đạo hàm ở đâu cả. Đây không phải sơ suất, và đó là ý tưởng thật sự quan trọng đầu tiên của khóa học.

Thứ bạn muốn lấy đạo hàm là lỗi — số lượng linh kiện bị phân loại sai. Nhưng con số đó là một bậc thang: nó nằm phẳng ở 4 trong khi bạn đẩy nhẹ đường thẳng, rồi rơi xuống 3 ngay khoảnh khắc đường thẳng cắt qua một điểm. Đạo hàm của nó bằng 0 gần như ở mọi nơi và không xác định tại các bậc. Giải tích không có gì để bám. Quy tắc perceptron đi vòng qua chuyện đó bằng cách không hỏi độ dốc gì cả: nó chỉ hỏi "đúng hay sai?", rồi di chuyển theo một hướng mà nó có thể biện minh bằng hình học.

Đó là một lời giải thật sự, và cũng là một ngõ cụt. Ở Chương 2, chúng ta sẽ muốn một loss đến từ đâu đó chứ không phải được chọn tùy ý; ở Chương 4, một mô hình báo cáo nó chắc chắn đến mức nào; và ở Chương 5, một thứ có nhiều hơn một layer — mà không thứ nào đạt được từ một quy tắc chỉ biết "sai". Lấy lại một độ dốc dùng được là điều buộc hai chương tiếp theo phải xuất hiện. Nhưng perceptron được làm một việc mà không hậu duệ nào của nó làm được: học mà hoàn toàn không cần giải tích.

Python thuần, không NumPy. Danh sách và một vòng lặp. NumPy sẽ đến ở chương sau, nơi số học không còn nằm gọn trong một vòng lặp mà bạn muốn đọc; đưa nó vào lúc này sẽ giấu số học sau một thư viện đúng vào khoảnh khắc bạn muốn nhìn thấy số học.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Bốn dòng được tô sáng là thuật toán. Mọi thứ khác là sổ sách.

Và đây là băng chuyền, với tám linh kiện được đo từ đó — bốn linh kiện được xuất xưởng và bốn linh kiện quay lại:

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

Tám linh kiện này có thể được tách bằng một đường thẳng — mọi linh kiện được chấp nhận đều dưới 22 mm và mọi linh kiện bị loại đều từ 23 mm trở lên. Một hàng rào thẳng đứng tại 22 milimét là đủ. Vậy perceptron nên tìm được nó.

Chạy nó:

None [-142.1, -13.0] 54.0

Hai trăm epoch, 454 lần sửa, và nó vẫn chưa hội tụ. Trọng số lớn và sai dấu. Có gì đó không ổn — ngoại trừ việc không có gì không ổn, và lý do chính là điều hữu ích nhất trong chương này.

Perceptron có một bảo đảm, được Novikoff chứng minh năm 1962.¹ Nếu dữ liệu có thể được tách bằng một đường thẳng, thuật toán sẽ thực hiện nhiều nhất

lần sửa trước khi không còn sửa gì nữa — trong đó $R$ là bán kính của dữ liệu, tức độ dài của vector ví dụ dài nhất, và $\gamma$ là margin: khoảng cách từ siêu phẳng tách đến điểm gần nhất trong không gian mở rộng nơi bias là tọa độ thứ ba. Đó là lý do việc căn giữa dữ liệu làm nó thay đổi, trong khi khoảng cách tính bằng milimét thì không.

Bảo đảm này là vô điều kiện và không nhắc đến epoch, learning rate hay may rủi. Nó cũng không nhắc đến thời gian, và sự thiếu vắng đó chính là điểm mấu chốt.

Thế các con số của chúng ta vào. Đo trực tiếp từ tám linh kiện, với bias được gập vào như một đặc trưng hằng:

Định lý chưa bao giờ bị vi phạm. Chạy phiên bản thô đủ lâu thì nó thật sự hội tụ — ở epoch 11,976, sau 29,870 lần sửa — vẫn nằm thoải mái trong cận 2,633,550, và chính khoảng cách đó mới là điểm đáng nói: định lý chặn trường hợp xấu nhất, không phải trường hợp điển hình. Nó chỉ cần nhiều epoch hơn sáu mươi lần so với mức bất kỳ ai chịu ngồi chờ.

Hàng thứ hai là cùng tám linh kiện, cùng hai mươi dòng code, chỉ thêm ba dòng để trừ chiều rộng trung bình và khối lượng trung bình khỏi mọi phép đo. Chỉ vậy thôi. Toàn bộ thay đổi là vậy. Nó dời đám mây điểm để đám mây vắt qua gốc tọa độ thay vì lơ lửng ở (22, 57), và hiệu ứng lên cận là một hệ số mười lăm nghìn, vì cả hai hạng đều cải thiện cùng lúc: $R$ giảm từ 74 xuống 13 vì các điểm không còn được đo từ một gốc tọa độ xa xôi, và $\gamma$ tăng từ 0.045 lên 0.989 vì margin được đo theo một vector trọng số không còn phải mang một bias khổng lồ để vươn tới dữ liệu.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Hội tụ trong hai epoch, sau khi tự sửa đúng một lần.

Có một bài học thật sự ở đây, và đó không phải là "hãy nhớ chuẩn hóa input", dù bạn nên làm thế. Bài học là một bảo đảm rằng thuật toán có kết thúc không nói cho bạn biết gì về việc bạn có còn ở đó khi nó kết thúc hay không, và khoảng cách giữa hai điều này thường là hình học. Đây là lần đầu tiên xuất hiện một mẫu hình bạn sẽ gặp lại ở Chương 6 với khởi tạo, ở Chương 10 với lịch learning rate, và ở Chương 13 với lượng tử hóa: toán học nói rằng điều đó là khả thi, còn kỹ thuật quyết định nó có thực tế hay không. Một khóa học chỉ dạy bạn định lý sẽ đưa cho bạn một mô hình train ba ngày rồi đổ lỗi cho bạn.

Giờ là thất bại đã kết thúc kỷ nguyên đầu tiên của neural network, và nó nằm gọn trong bốn hàng.

Quên nhà máy đi. Lấy hai input, mỗi input là 0 hoặc 1, và yêu cầu câu trả lời là $+1$ khi đúng một trong hai input bằng 1:

Đây là XOR — hoặc loại trừ. Trước khi đọc tiếp, hãy vẽ bốn điểm lên giấy: ba góc của một hình vuông đơn vị và góc thứ tư. Đánh dấu hai góc chéo nhau $(0,1)$ và $(1,0)$ là chấp nhận, còn $(0,0)$ và $(1,1)$ là loại. Giờ hãy vẽ một đường thẳng sao cho hai điểm được chấp nhận nằm một phía và hai điểm bị loại nằm phía kia.

Bạn không thể. Không phải vì việc đó khó, hay vì bạn cần một thuật toán khôn hơn; mà vì đường thẳng đó không tồn tại. Ba dòng đại số cho thấy vì sao. Nếu một perceptron làm đúng cả bốn, thì đọc bốn hàng theo thứ tự sẽ cho

Cộng hai bất đẳng thức ở giữa: $w_1 + w_2 + 2b \geq 0$, nên $w_1 + w_2 \geq -2b$. Bất đẳng thức cuối nói $w_1 + w_2 < -b$. Kết hợp lại: $-2b \leq w_1 + w_2 < -b$, điều này đòi hỏi $-2b < -b$, kéo theo $b > 0$. Và bất đẳng thức đầu tiên nói $b < 0$. Không có $b$ như vậy, nên không có bộ trọng số nào như vậy. Không perceptron nào, với bất kỳ con số nào, phân loại được XOR.

Dù vậy cứ chạy nó, vì xem một thuật toán thất bại có giá trị hơn nhiều so với việc được bảo rằng nó sẽ thất bại:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

Nó không phân kỳ, và cũng không quẫy quanh một câu trả lời tạm ổn. Nó lặp vòng: nó đi một vòng ngắn trong không gian trọng số rồi quay lại đúng nơi bắt đầu, mãi mãi, làm đúng hai trên bốn — đúng mức bạn có được nếu đoán mò. Một trăm nghìn epoch và một trăm epoch không khác gì nhau, vì thuật toán không tạo ra tiến triển mà một lần chạy dài hơn có thể hoàn tất. So với băng chuyền, trường hợp kia trông như bị kẹt ở 200 epoch nhưng thật ra đang ì ạch tiến về một câu trả lời thật. Nhìn từ bên ngoài, trong vài giây đầu hai trường hợp khá giống nhau. Phân biệt chúng mà không có định lý là bất khả thi — thêm một lý do để biết định lý.

Năm 1969, Marvin Minsky và Seymour Papert xuất bản Perceptrons, một nghiên cứu toán học dài cả cuốn sách về chính xác những gì mô hình này có thể và không thể biểu diễn.² XOR là kết quả được trích dẫn nhiều nhất, và câu trích dẫn thường được dùng như một lời buộc tội: rằng cuốn sách đã giết chết nghiên cứu neural network trong mười lăm năm vì ganh đua hoặc ác ý.

Toán học trong cuốn sách là đúng, và nó thú vị hơn ví dụ XOR. Minsky và Papert chủ yếu không quan tâm liệu một perceptron đơn lẻ có làm được XOR hay không; họ quan tâm chuyện gì xảy ra khi perceptron có trường tiếp nhận giới hạn — mỗi đơn vị chỉ nhìn thấy một phần của input — và họ chứng minh rằng một số thuộc tính toàn cục của ảnh, chẳng hạn một hình có liên thông hay không, không thể được tính theo cách đó bất kể bạn dùng bao nhiêu đơn vị. Đó là một kết quả thật sự sâu về tính cục bộ, và nó không liên quan gì đến câu chuyện phổ biến.

Câu chuyện phổ biến cũng sai về lịch sử. Minsky và Papert bàn rõ về perceptron nhiều layer và nói rằng câu hỏi về sức mạnh của chúng còn bỏ ngỏ — họ nghi ngờ việc mở rộng lý thuyết sẽ "vô hiệu", đó là một dự đoán chứ không phải một chứng minh, và dự đoán đó sai. Thứ còn thiếu năm 1969 không phải ý tưởng xếp chồng các layer; mà là cách train một chồng như vậy. Quy tắc perceptron không làm được: nó cần biết mỗi đơn vị sai đến mức nào, và với một đơn vị bị chôn ở giữa thì không có nhãn để so sánh. Khoảng trống đó vẫn mở cho đến khi backpropagation được phổ biến năm 1986,³ và khép lại khoảng trống đó là việc Chương 5 làm.

Vậy tóm tắt trung thực là thế này. Cuốn sách chứng minh một giới hạn thật của một mô hình thật. Sự sụp đổ tài trợ của lĩnh vực trong thập niên 70 có nhiều nguyên nhân, một trong số đó là những lời hứa dành cho perceptron đầu thập niên 60 đã quá phóng đại. Và trở ngại kỹ thuật là có thể giải được, chỉ là khi đó chưa ai có công cụ.

Perceptron đã sáu mươi tám tuổi và bạn vừa viết một cái. Đáng để nói chính xác phần nào của nó vẫn còn trong cỗ máy mà bạn sẽ hoàn thiện vào cuối khóa học này, vì câu trả lời là: nhiều hơn bạn tưởng.

Perceptron bị kẹt ở hai thứ cùng lúc, và hóa ra chúng là cùng một thứ.

Nó không thể biểu diễn XOR, vì một đường thẳng là không đủ. Sửa điều đó nghĩa là xếp chồng các layer — một layer đầu tiên bẻ cong không gian, một layer thứ hai vẽ đường thẳng trong không gian đã bị bẻ cong. Đó là Chương 5.

Nhưng bạn không thể train một chồng bằng quy tắc perceptron, vì nó chỉ biết "sai", và một đơn vị ở giữa mạng không có nhãn riêng để biết mình sai về điều gì. Để train một chồng, bạn cần biết sai như thế nào, và theo hướng nào, với mọi trọng số — bạn cần một độ dốc. Và hàm lỗi của perceptron, cái bậc thang đó, không có độ dốc.

Vì vậy trước khi có chồng layer, phải có một loss function với đạo hàm dùng được. Cũng không phải một hàm được chọn vì nó tiện lấy đạo hàm: mà là một hàm đến từ đâu đó, nói điều gì đó đúng về dữ liệu, và có gradient rơi ra từ chính ý nghĩa đó thay vì được đảo ngược thiết kế cho trông gọn gàng.

Đó là Chương 2, và nó bắt đầu bằng cách hỏi một câu mà perceptron chưa bao giờ phải trả lời: không phải "linh kiện này có tốt không?", mà là "các phép đo này có khả năng xảy ra đến mức nào, nếu đây là sự thật?"

Cũng đáng đọc song song với chương này: bài báo gốc của Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), dễ đọc hơn danh tiếng của nó gợi ý; McCulloch và Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), bài báo đầu tiên mô hình hóa một neuron như một ngưỡng trên tổng có trọng số; phần perceptron trong A Course in Machine Learning của Hal Daumé III, suy ra cùng cập nhật với một trọng tâm khác; và chương 2 và 3 của Mathematics for Machine Learning của Deisenroth, Faisal và Ong cho phần đại số tuyến tính, nếu hộp ở trên khiến bạn muốn nhiều hơn những gì nó đã cho.