PiMA

Posted on: 29/7/2018

---

“Lumos!” - Một tia sáng xanh lóe lên, hiện ra hình ảnh cô bé Uyên tinh nghịch đang thử hết thần chú này đến thần chú khác mà cô đã học trong cả mùa hè. Bùm, chéo! Những tia sáng xanh đỏ đang chớp nhoáng trong đêm tối của tòa lâu đài Hogwart bỗng chạm một thứ gì đó văng ngược lại. Sững sờ, trí tò mò thôi thúc Uyên… “Alohomora!”… một cánh cửa mở ra và trước mắt cô là một căn phòng lộng lẫy tràn ngập ánh sáng: “Ồ, đây chính là phòng hiệu trưởng, và trên bàn kia chính là “Chiếc Mũ phân loại” nổi tiếng!”

“Làm sao để chiếc mũ bay đến phía mình nhỉ” - Cô nghĩ…. “Leviosa Kedavra!” ….

Bùm! Chiếc mũ “huyền thoại” tan tành, những dòng ký ức vàng lóng lánh của các phù thủy mà chiếc mũ từng phân loại bay tứ tung trong không trung. Thì ra, Uyên đã gộp nhầm câu thần chú di chuyển “Wingardium Leviosa” với thần chú chết chóc “Avada Kedavra”. Ngày mai là ngày khai giảng rồi, và nếu bị phát hiện, chắc chắn cô bé sẽ bị đuổi học mất.

Thật may mắn, trước khi nhập học Hogwart, cô bé đã tham trại hè PiMA và được học một số thuật toán phân loại có thể giúp cô sử dụng dữ liệu kí ức này để “làm giả” một chiếc mũ mới để phân loại học sinh vào 4 nhà.

Trong bài toán này, cô bé cần chiếc mũ giả phân loại được học sinh mới vào 4 nhà: Gryffindor, Hufflepuff, Ravenclaw hoặc Slytherin (tạm ký hiệu là nhà 1,2,3,4).

Uyên vẫy đũa phép, những kí ức lóng lánh bay thành 3 phần ngay ngắn: train, validation và test set (trong thực tế, dữ liệu cũng thường được chia với tỉ lệ là 80/10/10 hoặc 98/1/1 với lượng dữ liệu đồ sộ để xử lí)

Với phần kí ức dùng để train (lần lượt gọi là \(x_1,x_2,\dots,x_n\)), có 2 thuật toán mà Uyên đang phân vân:

One vs All: Với mỗi nhà i, Uyên sẽ phải lần lượt tìm xác suất phù thủy x được xếp vào nhà i, \(y_i\) là biến boolean ứng với mỗi nhà i (1 nếu dự đoán là nhà i, 0 cho tất cả các nhà còn lại):

\[f_i(x)=P(y=y_i\vert \theta_i,x),i=1\rightarrow 4\]

với \(\theta_i\) chính là những tham số cho thấy đặc trưng của các phù thủy thuộc nhà đó (ví dụ những phù thủy được xếp vào Gryffindor thường có “điểm” dũng cảm cao hơn, Ravenclaw là trí thông minh, Hufflepuff là lòng trung thành, Slytherin là sự tham vọng, xảo quyệt).

Thuật toán này được gọi là One vs All vì cô bé sẽ phải đọc thần chú 4 lần, mỗi lần ứng với một nhà để tính fi(x). Ví dụ với nhà Gryffindor, 1 sẽ là kết quả nếu dự đoán là Gryffindor và 0 với tất cả các nhà còn lại KHÔNG PHẢI LÀ GRYFFINDOR. Kết quả cuối cùng sẽ là \(\mathrm{max} f_i(x)(i=1\rightarrow 4)\).

Softmax Classification: đầu tiên, với mỗi nhà i, giá trị \(z_i=(w_i)^Tx\) càng lớn thì xác suất rơi vào nhà i càng cao (Lưu ý: \((w_i)^T\) là ma trận chuyển vị của \(w_i\), \(w_i\) là những đặc trưng, tính cách của các phù thủy được nhận vào nhà i). Với thuật toán này, Uyên cũng sẽ phải đọc thần chú 4 lần để tính xác suất phù thủy được phân loại vào nhà i (dựa vào thông tin về phù thủy đó và thông tin về các ký ức đã có):

\(f_i=\frac{e^{z_i}}{\sum e^{z_i}}\) ​ Nếu bạn có thể giúp Uyên, bạn sẽ chọn phương pháp nào, và vì sao?