RL 5: Học tự động hóa và môi trường ngẫu nhiên (1961–1974)

Tóm tắt nhanh, trong trường hợp bạn mới theo dõi từ Bài viết số 4. Chương trình chơi cờ đam của Arthur Samuel học bằng cách đoán độ tốt của một vị trí trên bàn cờ (ước lượng giá trị). Máy hộp diêm MENACE của Donald Michie học bằng cách thay đổi nước đi mà nó ưu tiên (chọn chính sách). Cả hai đều hoạt động. Cả hai đều mong manh: Samuel cần các đặc trưng được tạo thủ công, và Michie cần một hộp diêm cho mỗi vị trí bàn cờ có thể có. Điều đó để lại một câu hỏi bỏ ngỏ: một cỗ máy cần tối thiểu những gì để có thể cải thiện từ phản hồi? Câu trả lời rõ ràng đầu tiên đến từ Moscow. Trước khi bắt đầu: bảng chú giải thuật ngữ 60 giây Bạn sẽ thấy những từ này rất nhiều trong bài viết này. Không từ nào đáng sợ. Tác nhân (Agent): thực thể hành động và học hỏi (ở đây là một cỗ máy nhỏ). Môi trường (Environment): bất cứ điều gì tác nhân tương tác (ở đây là một tập hợp các máy đánh bạc). Hành động (Action): một lựa chọn mà tác nhân có thể thực hiện (kéo máy nào). Phần thưởng/Hình phạt (Reward / Penalty): phản hồi sau một hành động. Kết quả tốt = phần thưởng, kết quả xấu = hình phạt. Ngẫu nhiên (Stochastic): "gần như ngẫu nhiên." Cùng một hành động có thể cho kết quả khác nhau trong những lần thử khác nhau. Tự động tử (Automaton) (số nhiều: automata): một cỗ máy tồn tại trong một số trạng thái cố định và chuyển đổi giữa chúng theo các quy tắc đơn giản. Hãy nghĩ đến đèn giao thông, không phải siêu máy tính. Trạng thái (State): "chế độ" hiện tại của cỗ máy. Về cơ bản là bộ nhớ của nó. Phần 1: Những cỗ máy học hỏi nhỏ nhất Vấn đề: làm thế nào để học khi phản hồi không đáng tin cậy? Samuel và Michie đã dạy chúng ta rằng máy móc có thể học hỏi từ kinh nghiệm. Nhưng cả hai hệ thống của họ đều ngầm giả định rằng phản hồi có ý nghĩa. Thắng trò chơi, tốt. Thua trò chơi, xấu. Cuộc sống thực tế phức tạp hơn. Hãy hình dung các máy bán hàng tự động trên đường phố của bạn: Máy A cho bạn một món ăn nhẹ miễn phí 70% thời gian. Máy B cho bạn một món ăn nhẹ miễn phí 40% thời gian. Bạn không biết những con số này. Bạn chỉ có thể thử một máy, xem nó có trả tiền không, và điều chỉnh. Và đây là vấn đề: Máy A đôi khi sẽ làm bạn thất vọng, và Máy B đôi khi sẽ gặp may. Một kết quả gần như không nói lên điều gì. Vì vậy, câu hỏi thực sự trở thành: làm thế nào để một cỗ máy học được lựa chọn đúng khi bất kỳ kết quả đơn lẻ nào cũng có thể là sai lệch? Đó là thế giới của các môi trường ngẫu nhiên, và đó là nơi Mikhail Tsetlin bắt đầu. Gặp gỡ Mikhail Tsetlin: người đàn ông của "bộ não nhỏ nhất có thể" Mikhail Tsetlin (1924–1966) là một nhà toán học Liên Xô làm việc tại Moscow trong kỷ nguyên điều khiển học sơ khai. Năm 1961, ông xuất bản một bài báo có tựa đề "Về hành vi của các tự động tử hữu hạn trong môi trường ngẫu nhiên". Tựa đề khá dài dòng, nhưng ý tưởng lại khiêm tốn một cách đẹp đẽ. Hầu hết các nhà nghiên cứu thời đó hỏi, "làm thế nào để chúng ta xây dựng một cỗ máy thông minh hơn?" Tsetlin hỏi câu hỏi ngược lại: Cấu trúc nội bộ nhỏ nhất mà một cỗ máy cần để cải thiện hành vi của nó là gì? Không phải mạnh nhất. Mà là nhỏ nhất. Ông đang tìm kiếm giới hạn thấp nhất của trí tuệ máy móc. Câu trả lời của ông là một tự động tử trạng thái hữu hạn với một điểm khác biệt: không có mô hình thế giới, không có dự đoán, không có phép tính, không có điểm số. Chỉ có: một vài trạng thái nội bộ (bộ nhớ của nó), một quy tắc để chọn một hành động dựa trên trạng thái hiện tại, và một quy tắc để di chuyển giữa các trạng thái dựa trên phản hồi. Lưu ý cụm từ "môi trường ngẫu nhiên" trong tiêu đề. Đó là tên mà Tsetlin đặt cho một môi trường ngẫu nhiên: một thế giới phản hồi các hành động của bạn bằng phần thưởng hoặc hình phạt theo các xác suất ẩn. Các máy bán hàng tự động là một môi trường ngẫu nhiên. Các căn phòng: bộ nhớ của Tsetlin, được hiển thị rõ ràng Cách tốt nhất để hiểu một tự động tử Tsetlin là hình dung một hành lang các căn phòng. Nửa bên trái của hành lang là "Hành động A" (kéo máy A). Nửa bên phải là "Hành động B" (kéo máy B). Máy luôn ở chính xác một phòng, và vị trí của nó quyết định hành động tiếp theo. Dưới đây là một phiên bản nhỏ với 3 phòng mỗi bên (tổng cộng 6 trạng thái): Bên Hành động A | Bên Hành động B [ 1 ] [ 2 ] [ 3 ] | [ 4 ] [ 5 ] [ 6 ] sâu rìa | rìa sâu Các quy tắc chỉ dài hai dòng: Phần thưởng -> đi sâu hơn vào phía hiện tại của bạn (cam kết hơn). Hình phạt -> đi một phòng về phía giữa. Nếu bạn đã ở rìa, bạn sẽ vượt qua ranh giới và chuyển đổi hành động. Phản hồi chỉ là một bit duy nhất: 0 = phần thưởng, 1 = hình phạt. Không có điểm số, không có xác suất, không có gradient. Chỉ có sự di chuyển. Hãy cùng xem xét Giả sử chúng ta bắt đầu ở phòng 3 (rìa của Hành động A) và tiếp tục kéo máy A, máy này trả thưởng 70% thời gian: Bước Phòng Hành động Kết quả Nơi chúng ta sẽ đến tiếp theo 1 3 A Phần thưởng Phòng 2 (sâu hơn) 2 2 A Phần thưởng Phòng 1 (sâu nhất) 3 1 A Hình phạt (không may!) Phòng 2 (lùi một bước) 4 2 A Phần thưởng Phòng 1 một lần nữa Hãy nhìn vào bước 3. Máy gặp vận rủi, nhưng nó không hoảng loạn. Một kết quả xấu chỉ khiến nó di chuyển một phòng, và nó vẫn kiên định ở Đội A. Các phòng đã hấp thụ nhiễu. Tại sao bộ nhớ lại quan trọng (tại sao không chỉ tung đồng xu?) Bạn có thể hỏi: nếu phản hồi chỉ là phần thưởng/hình phạt, tại sao phải bận tâm với sáu phòng? Tại sao không phải là quy tắc đơn giản nhất từ trước đến nay: "nếu được trả thưởng, hãy làm lại; nếu không, hãy chuyển đổi"? Điều thú vị là: quy tắc đó là một Tsetlin automaton, loại nhỏ nhất, chỉ có 1 phòng mỗi bên. Đó là chiến lược "thắng thì giữ, thua thì đổi" kinh điển. Và nó rất dễ thay đổi. Một hình phạt không may mắn có thể khiến nó từ bỏ một cỗ máy hoàn toàn tốt. Hãy nghĩ về nhà hàng yêu thích của bạn. Bạn đã có một bữa ăn tồi tệ. Bạn có bao giờ không quay lại không? Tất nhiên là không. Bạn có ký ức về nhiều bữa ăn ngon, vì vậy một đêm tồi tệ không làm thay đổi ý kiến của bạn. Nhiều phòng hơn = kiên nhẫn hơn. Vì vậy, hãy kiểm tra nó. Tôi đã mô phỏng chính xác hành lang trên (Máy A trả thưởng 70%, Máy B trả thưởng 40%, 5.000 lần kéo mỗi lần chạy, trung bình trên 200 lần chạy), chỉ thay đổi số lượng phòng mỗi bên, N: Số phòng mỗi bên (N) Tỷ lệ kéo trên máy tốt hơn 1 (thắng thì giữ, thua thì đổi) ~67% 2 ~80% 3 ~89% 5 ~97,5% 10 ~99,9% Càng nhiều bộ nhớ, quyết định càng tốt hơn. Dưới đây là đoạn mã nhỏ nếu bạn muốn tự mình thử: import random def tsetlin(pay=(0.7, 0.4), N=3, steps=5000): # states 1..N -> action 0 (1 = deepest, N = edge) # states N+1..2N -> action 1 (N+1 = edge, 2N = deepest) state = N pulls = [0, 0] for _ in range(steps): action = 0 if state <= N else 1 pulls[action] += 1 rewarded = random.random() < pay[action] if action == 0: state = max(state - 1, 1) if r