[ad_1]
Học tăng cường: Bài toán quyết định Markov để lựa chọn tính năng
Người ta đã chứng minh rằng kỹ thuật học tăng cường (RL) có thể rất hiệu quả đối với các vấn đề như giải trò chơi. Khái niệm RL dựa trên Quy trình Quyết định Markovian (MDP). Vấn đề ở đây không phải là xác định sâu sắc MDP mà là có được ý tưởng chung về cách thức hoạt động của nó và nó có thể hữu ích như thế nào đối với vấn đề của chúng ta.
Ý tưởng ngây thơ đằng sau RL là một tác nhân bắt đầu trong một môi trường không xác định. Tác nhân này phải thực hiện các hành động để hoàn thành một nhiệm vụ. Tùy theo trạng thái hiện tại của tác nhân và hành động mà anh ta đã chọn trước đó, tác nhân sẽ có xu hướng chọn một số hành động hơn. Ở mỗi trạng thái mới đạt được và hành động được thực hiện, tác nhân sẽ nhận được phần thưởng. Sau đây là các tham số chính mà chúng ta cần xác định cho mục đích lựa chọn tính năng:
- Nhà nước là gì?
- Một hành động là gì?
- Phần thưởng là gì?
- Làm thế nào để chúng ta chọn một hành động?
Thứ nhất, trạng thái chỉ là một tập hợp con các tính năng tồn tại trong tập dữ liệu. Ví dụ: nếu tập dữ liệu có ba đặc điểm (Tuổi, Giới tính, Chiều cao) cộng với một nhãn thì đây sẽ là các trạng thái có thể có:
() --> Empty set
(Age), (Gender), (Top) --> 1-feature set
(Age, Gender), (Gender, Top), (Age, Top) --> 2-feature set
(Age, Gender, Top) --> All-feature set
Trong một trạng thái, thứ tự của các tính năng không quan trọng và điều này sẽ được giải thích tại sao ở phần sau của bài viết. Chúng ta phải coi nó như một bộ chứ không phải một danh sách các tính năng.
Liên quan đến các hành động, từ một tập hợp con, chúng ta có thể đi đến bất kỳ tập hợp con nào khác với một tính năng chưa được khám phá nhiều hơn trạng thái hiện tại. Trong bài toán lựa chọn tính năng, một hành động sau đó là chọn một tính năng chưa được khám phá ở trạng thái hiện tại và thêm nó vào trạng thái tiếp theo. Dưới đây là mẫu về các hành động có thể thực hiện:
(Age) -> (Age, Gender)
(Gender, Top) -> (Age, Gender, Top)
Đây là một ví dụ về những hành động không thể thực hiện được:
(Age) -> (Age, Gender, Top)
(Age, Gender) -> (Age)
(Gender) -> (Gender, Gender)
Chúng tôi đã xác định các trạng thái và hành động nhưng chưa xác định được phần thưởng. Phần thưởng là một con số thực được sử dụng để đánh giá chất lượng của một trạng thái. Ví dụ: nếu một robotic đang cố gắng đi đến lối ra của mê cung và quyết định đi đến lối ra đó làm hành động tiếp theo thì phần thưởng liên quan đến hành động này sẽ là “tốt”. Nếu anh ta chọn hành động tiếp theo để đi vào bẫy thì phần thưởng sẽ “không tốt”. Phần thưởng là giá trị mang lại thông tin về hành động được thực hiện trước đó.
Trong vấn đề lựa chọn tính năng, phần thưởng thú vị có thể là giá trị chính xác được thêm vào mô hình bằng cách thêm tính năng mới. Dưới đây là ví dụ về cách tính phần thưởng:
(Age) --> Accuracy = 0.65
(Age, Gender) --> Accuracy = 0.76
Reward(Gender) = 0.76 - 0.65 = 0.11
Đối với mỗi trạng thái mà chúng ta truy cập lần đầu tiên, bộ phân loại sẽ được huấn luyện với tập hợp các tính năng. Giá trị này được lưu trữ ở trạng thái và việc đào tạo bộ phân loại, rất tốn kém, sẽ chỉ xảy ra một lần ngay cả khi đạt lại trạng thái đó sau đó. Trình phân loại không xem xét thứ tự của tính năng. Đây là lý do tại sao chúng ta có thể xem vấn đề này như một biểu đồ chứ không phải một cái cây. Trong ví dụ này, phần thưởng của hành động chọn Giới tính làm tính năng mới cho mô hình là sự khác biệt giữa độ chính xác của trạng thái hiện tại và trạng thái tiếp theo.
Trên biểu đồ trên, mỗi đặc điểm được ánh xạ thành một số (tức là “Tuổi” là 1, “Giới tính” là 2 và “Chiều cao” là 3). Hoàn toàn có thể lấy các số liệu khác tối đa hóa để tìm ra bộ tối ưu. Trong nhiều ứng dụng kinh doanh, việc thu hồi được quan tâm nhiều hơn là độ chính xác.
Câu hỏi quan trọng tiếp theo là làm cách nào để chúng ta chọn trạng thái tiếp theo từ trạng thái hiện tại hoặc làm cách nào để chúng ta khám phá môi trường của mình. Chúng ta phải tìm ra cách tối ưu nhất để thực hiện vì nó có thể nhanh chóng trở thành một vấn đề rất phức tạp. Thật vậy, nếu chúng ta khám phá một cách ngây thơ tất cả tập đặc trưng có thể có trong một bài toán có 10 đặc điểm thì số trạng thái sẽ là
10! + 2 = 3 628 802 potential states
+2 là do chúng tôi xem xét trạng thái trống và trạng thái chứa tất cả các tính năng có thể có. Trong bài toán này, chúng ta sẽ phải huấn luyện cùng một mô hình trên tất cả các trạng thái để có được tập hợp các tính năng giúp tối đa hóa độ chính xác. Theo cách tiếp cận RL, chúng tôi sẽ không phải đi đến tất cả các trạng thái và đào tạo một mô hình mỗi khi chúng tôi đến một trạng thái đã ghé thăm.
Chúng tôi phải xác định một số điều kiện dừng cho vấn đề này và chúng sẽ được trình bày chi tiết sau. Hiện tại, lựa chọn trạng thái tham lam epsilon đã được chọn. Ý tưởng là từ trạng thái hiện tại, chúng tôi chọn hành động tiếp theo một cách ngẫu nhiên với xác suất epsilon (trong khoảng từ 0 đến 1 và thường là khoảng 0,2) và nếu không thì chọn hành động tối đa hóa hàm. Đối với việc lựa chọn tính năng, hàm là phần thưởng trung bình mà mỗi tính năng đã mang lại cho độ chính xác của mô hình.
Thuật toán tham lam epsilon bao gồm hai bước:
- Pha ngẫu nhiên: với epsilon xác suất, chúng ta chọn ngẫu nhiên trạng thái tiếp theo trong số các trạng thái lân cận có thể có của trạng thái hiện tại (chúng ta có thể tưởng tượng lựa chọn thống nhất hoặc lựa chọn softmax)
- Giai đoạn tham lam: chúng tôi chọn trạng thái tiếp theo sao cho tính năng được thêm vào trạng thái hiện tại có đóng góp tối đa về độ chính xác cho mô hình. Để giảm bớt độ phức tạp về thời gian, chúng tôi đã khởi tạo một danh sách chứa các giá trị này cho từng tính năng. Danh sách này được cập nhật mỗi khi một tính năng được chọn. Việc cập nhật rất tối ưu nhờ công thức sau:
- AORf : Trung bình phần thưởng do tính năng “f” mang lại
- ok : số lần chữ “f” được chọn
- V(F) : giá trị trạng thái của tập hợp tính năng F (không được nêu chi tiết trong bài viết này vì lý do rõ ràng)
Ý tưởng chung là tìm ra tính năng nào mang lại độ chính xác cao nhất cho mô hình. Đó là lý do tại sao chúng ta cần duyệt qua các trạng thái khác nhau để đánh giá giá trị chính xác nhất toàn cầu của một tính năng cho mô hình trong nhiều môi trường khác nhau.
Cuối cùng tôi sẽ trình bày chi tiết hai điều kiện dừng. Vì mục tiêu là giảm thiểu số lượng trạng thái mà thuật toán truy cập nên chúng ta cần phải cẩn thận với chúng. Chúng ta càng truy cập ít trạng thái chưa bao giờ ghé thăm thì số lượng mô hình chúng ta phải đào tạo với các bộ tính năng khác nhau càng ít. Huấn luyện mô hình để có được độ chính xác là giai đoạn tốn kém nhất về thời gian và khả năng tính toán.
- Thuật toán dừng trong mọi trường hợp ở trạng thái cuối cùng là tập hợp chứa tất cả các đặc điểm. Chúng tôi muốn tránh đạt đến trạng thái này vì việc đào tạo một mô hình là tốn kém nhất.
- Ngoài ra, nó sẽ dừng duyệt biểu đồ nếu một chuỗi các trạng thái được truy cập thấy giá trị của chúng giảm liên tiếp. Một ngưỡng đã được đặt sao cho sau căn bậc hai của tổng số đối tượng địa lý trong tập dữ liệu, nó sẽ ngừng khám phá.
Bây giờ mô hình hóa vấn đề đã được giải thích, chúng tôi sẽ trình bày chi tiết cách triển khai trong python.
[ad_2]
Source link