Khái niệm “chuyển giản” (reduction) là khái niệm trung tâm của lý thuyết tính toán và thuật toán. Alina Beygelzimer, John Langford, và Bianca Zadrozny có một tutorial hay ở ICML 2009 về “chuyển giản” trong học máy. Ví dụ, ta có thể “chuyển giản” bài toán phân loại (classification) tổng quát về bài toán phân loại nhị phân.
5 Comments
Hi bác Hưng, bên lý thuyết thuật toán thì reduction là khái niệm trung tâm, nhưng trong học máy hay trong thống kê thì tôi nghĩ khong như vậỵ (Thích chữ “học giả” của bác bữa trước
There is an intrinsic difference between logical deduction and inductive reasoning. In logical deduction, reduction is sufficient for the study of complexitỵ. This is not the case for inductive reasoning.
Khi gò các vấn đề inference thống kê về binary classification, thực ra mất đi rất nhiều information (in a precise sense), từ đó mất đi performance (có thể rất tệ). Trong một số trường hợp ứng dụng thì không sao lắm, có thể thuận tiện tuy không tự nhiên, nhưng trong phần lớn các vấn đề khác thì nhẽ ra người ta cần phải kết hợp càng nhiều thông tin khác thay vì vứt đi nhưng cấu trúc có thể rất hữu ích.
Về lý tưởng thì JL có một ý tốt, đó là muốn phát triển off-the-self one-fit-all learning algorithms cho non-experts. Nhưng đó là lãng mạn kiểu AI không tưởng.
Kỹ thuật reduction của JL khá là simplistic, không hề sâu sắc gì, chủ yếu dựa trên manipulation của một vấn đề inference đối với probability distributions mà không đếm xỉa gì structures của distributions cũng như khía cạnh học (estimation/learning) từ datạ. Cho nên tuy làm vấn đề dễ đi, performance có thể rất tệ không kiểm soát được. Binary classification về mặt học thì giản lược quá, không thể nhét structures vào formulation được dễ dàng. Đây là lý do lý thuyết này không đi xa được. Anh này quảng cáo trò này từ khi tôi bắt đầu vào grad school cơ, nhưng xem ra không có ai follow-up mấỵ
Thanks bác Long, I like the (obvious yet subtle) distinction between induction and deduction.
While JL’s attempt might have been futile, in my opinion the general idea of defining and studying “reductions” in learning is a worthwhile direction to look at. For example, it was surprising that weak (PAC) learning is actually equivalent to strong (PAC) learning. Schapire (and Freund) showed this fact via a reduction from strong learning to weak learning. The result lead to AdaBoost and later various other Boosting algorithms which have been quite useful in practice.
Cái này hữu dụng với tôi. Tôi đang muốn sử dụng điều kiện ổn định của hệ thống cho hội tụ của hệ thống gần giống. Sau khi biến đổi, cố gắng đưa nó về gần nhau nhất rồi dùng tiêu chuẩn ổn định của cái này áp cho cái kia, tôi thấy kết quả trùng trong khá nhiều trường hợp riêng. Tôi chưa dám sử dụng chỉ vì vướng mắc là chưa chặt chẽ khi coi 2 hệ thống có hàm truyền (transfer function) gần giống nhau là như nhau. Thầy hướng dẫn có gợi ý về hàm làm già, nhưng tôi chưa tìm hiểu được.
Cám ơn anh đã giới thiệu tutorial.
nen chang dich na` “qui gia?n”
Cảm ơn bác, đúng là “qui giản” hay hơn.