Lý thuyết học thống kê

LÝ THUYẾT HỌC THỐNG KÊ (statistical learning theory) MÔ HÌNH TỔNG QUÁT CỦA HỌC TỪ VÍ DỤGiả sử có một quan hệ hàm giữa hai tập X và Y f : X  Y Mục đích : tìm ra quan hệ hàm này khi được cho tập ví dụ Hàm f : hàm học hay hàm mục tiêu. Mỗi đối tượng x biểu diễn bởi vectơ đặc trưng Hàm học giá trị thực : vấn đề hồi quy (regression). Hàm học giá trị rời rạc : vấn đề phân lớp (classification). Học với tập ví dụ gắn nhãn : học có giám sát (supervised learning). Giả thiết của lý thuyết học thống kêTồn tại một phân phối xác suất p(x,y) cố định và chưa biết trên X x Y.Các ví dụ (x,y) được lấy mẫu độc lập theo cùng một phân phối p(x,y) Giả thiết i.i.d (independent and identically distributed). Mục tiêu : sử dụng tập ví dụ huấn luyện để đưa ra một hàm là xấp xỉ của hàm mục tiêu. Học là vấn đề xấp xỉ hàm. SAI SỐ VÀ SAI SỐ THỰC NGHIỆM. Đối với phân lớp : lỗi phân lớp (classification error) L(y,h(x)) = 0 nếu y = h(x) và =1 nếu khác Hàm sai lệch (loss function). Giả sử (x,y) là một ví dụ, h : X  Y. Ký hiệu L(y,h(x)) là độ đo sự sai khác giữa y và h(x) L : hàm sai lệch (loss function). Trường hợp hồi quy: Lôĩ bình phương (squared loss)Sai số kỳ vọng hay lỗi kỳ vọng (expected risk / expected loss) của hàm h:Sai số thực nghiệm. Sai số thực nghiệm (empirical risk) của hàm h: Hàm xấp xỉ tốt nhất của hàm mục tiêu là hàm có sai số kỳ vọng nhỏ nhất.Ví dụ. Hàm lỗi tổng bình phương (sum-of-squares error function):Lỗi phân lớp: NGUYÊN LÝ QUY NẠP CỰC TIỂU SAI SỐ THỰC NGHIỆM Hàm mục tiêu cần học f được xấp xỉ bằng hàm g : Hai đường xấp xỉ từ 5 ví dụ. Giả sử H là một lớp hàm nào đó. H : không gian các giả thuyết ( space of hypotheses). Nguyên lý quy nạp : xấp xỉ hàm mục tiêu bởi hàm g Nguyên lý quy nạp cực tiểu lỗi thực nghiệm (empirical risk minimization inductive principle) Câu hỏi : Hàm g là xấp xỉ tốt của hàm cần học không? Cụ thể hơn : sai số R(g) nhỏ không? Hàm g phụ thuộc vào lớp các hàm H, nó đóng vai trò như là hướng quy nạp.Hàm mục tiêu không thuộc lớp hàm H, khó có thể g là xấp xỉ tốt. Lớp hàm H chứa hàm mục tiêu, không có gì đảm bảo hàm g có sai số nhỏ. Chúng ta hoàn toàn không biết gì về hàm mục tiêu, chỉ có các thông tin trong tập huấn luyện D. Đưa ra lớp hàm H thích hợp cho một nhiệm vụ học ?Câu hỏi khác : ta không thể tính được sai số R(g) , làm thế nào đánh giá được khả năng tiên đoán chính xác của nó ở ngoài tập ví dụ huấn luyện? Thiết kế các thuật toán học dựa trên nguyên lý quy nạp Đưa vào lớp các hàm H. Chẳng hạn: Tìm vectơ tham biến sao cho sai số thực nghiệm nhỏ nhất. Học từ các ví dụ là vấn đề tìm kiếm tối ưu . PHÂN LỚP BAYES VÀ HÀM HỒI QUY Lý thuyết xác suất và thống kê + Lý thuyết quyết định (decision theory)  khung làm việc để thiết kế và phân tích các thuật toán học Phân lớp Bayes Hàm mục tiêu cần học : P(c ) : xác suất tiên nghiệm (prior probability) P(c / x): xác suất hậu nghiệm (posterior probability) p(x) : Hàm mật độ xác suất của các đối tượng x p(x / c) : Hàm mật độ xác suất của các đối tượng trong lớp c :mật độ xác suất điều kiện trên lớp (class- conditional probability density function). Luật quyết định Bayes Phân lớp Bayes (Bayes classifier) : đối tượng x được phân vào lớp c có xác suất hậu nghiệm lớn nhất : Phân lớp Bayes là phân lớp tối ưu Phân lớp Bayes cho sai số kỳ vọng nhỏ nhất. Phân lớp Bayes cho xác suất lỗi nhỏ nhất. Phân lớp Bayes : Cách khác : đối tượng x được phân vào lớp c sao cho tích P(x / c)P(c) là lớn nhất:Ví dụ . Phân các bệnh nhân thành hai lớp ung thư và không ung thư theo kết quả xét nghiệm (dương/âm) Giả sử: P(cancer)=0,008), P(noncancer)=0,992 .Các cách tiếp cận phân lớp Bayes 1. Các mô hình sinh (generative models):Đưa ra mô hình mô tả các mật độ xác suất p(x /c) và các xác suất P(c ) . Đánh giá các đại lượng đó từ các dữ liệu huấn luyện. Tương đương, đưa ra mô hình mô tả phân phối kết hợp p(x,c) và đánh giá nó từ dữ liệu. 2. Các mô hình phân biệt (discriminative models): Mô hình hoá trực tiếp các xác suất hậu nghiệm P(c / x) và đánh giá chúng từ dữ liệu. Hàm hồi quy Cần đánh giá một hàm mục tiêu thực: f : X  Y = RGiả sử h là một hàm xấp xỉ của hàm mục tiêu, lỗi kỳ vọng của hàm h là: Mục đích : tìm hàm h sao cho lỗi kỳ vọng trên là nhỏ nhất. Từ các kết quả cơ bản của phép tính biến phân (the calculus of variations), Trong đóHàm h(x) : hàm hồi quy (regression function). Hai hướng tiếp cận để giải quyết vấn đề hồi quy Đưa ra mô hình biểu diễn hàm mật độ xác suất kết hợp p(x,y) và đánh giá hàm mật độ từ tập dữ liệu huấn luyện. Cách thứ hai : đưa ra mô hình xác suất biểu diễn trực tiếp hàm mật độ xác suất p(y/x), rồi đánh giá mật độ này từ dữ liệu. HỌC KHÔNG CÓ GIÁM SÁT Học từ tập dữ liệu không gắn nhãn :1. Đánh giá mật độ. Giả thiết : tập dữ liệu được sinh ra từ hàm mật độ xác suất p(x) Nhiệm vụ : đánh giá hàm mật độ đó từ tập dữ liệu. 2. Phân cụm dữ liệu (clustering). 3. Rút gọn chiều dữ liệu. The curse of dimensionality. 4. Phát hiện các điểm dữ liệu ngoại lai (outlier). Các phương pháp đánh giá mật độ Giả thiết : hàm mật độ xác suất sinh ra tập dữ liệu có dạng hàm phụ thuộc vectơ tham biến Hai phương pháp đánh giá: Phương pháp maximum-likelihood Phương pháp Bayes PHƯƠNG PHÁP MAXIMUM-LIKELIHOOD Đánh giá maximum-likelihood của vectơ tham biến là vectơ :Hàm likelihood Hàm log-likelihood Tìm vectơ tham biến ML là vấn đề tìm kiếm tối ưu :Có thể sử dụng các phương pháp kinh điển của phép tính vi phân . Sử dụng kỹ thuật tìm kiếm gradientVectơ ML thoả mãn một số ràng buộc : có thể sử dụng phương pháp nhân tử Lagrange (Lagrange Multipliers).Mô hình chứa biến ẩn: Thuật toán EMCác kỹ thuật tìm kiếm tối ưu khác. PHƯƠNG PHÁP BAYES Đưa vào mật độ xác suất trên không gian tham biến : mật độ tiên nghiệm (prior density) Sau khi quan sát được tập dữ liệu D, đánh giá lại mức độ tin tưởng về các tham biến mật độ hậu nghiệm (posterior density) Tính mật độ hậu nghiệm: Hậu nghiệm = Tiên nghiệm X LikelihoodSử dụng mật độ hậu nghiệm, tính phân phối tiên đoán Cũng có thể tính vectơ tham biến MAP (maximum a posteriori) Hai hướng tiếp cận Phương pháp tham biến: xây dựng các mô hình biểu diễn hàm mục tiêu hoặc các mô hình biểu diễn các phân phối xác suất sinh ra tập dữ liệu quan sát, rồi đánh giá các tham biến của mô hình từ dữ liệu. Ví dụ: Linear Models, Feed-Forward Neural Networks, Bayesian Netwoks, Markov Random Fields, Gaussian Mixtures, Hidden Markov Models, Conditional Random Fields, Bolzman Machines, Deep Belief Networks Phương pháp không tham biến: Đánh giá mật độ (Parzen windows), phương pháp k-láng giềng gần nhất. Các phương pháp cây : cây quyết định, ĐÁNH GIÁ MỘT GIẢ THUYẾT Giả sử h là một giả thuyết, lỗi của h : R(h) (không thể tính được ) Đánh giá R(h) qua lỗi thực nghiệm Câu hỏi : Lỗi thực nghiệm có là đánh giá tốt của lỗi đúng R(h) không ? Luật số lớn Bất đẳng thức Hoeffding Giả sử X là biến ngẫu nhiên nhận giá trị trong khoảng [a,b] : Trường hợp phân lớp, với hàm sai lệch là lỗi phân lớp: Đánh giá biên sai lệch giữa sai số thực nghiệm và sai số kỳ vọng. Chẳng hạn, đối với phân lớp, với mức độ tin tưởng (xác suất) là TÍNH CHẤT CONSISTENT CỦA THUẬT TOÁN HỌC Mục tiêu: Khi được cho tập ví dụ D, tìm hàm h sao cho sai số R(h) nhỏ nhất. Hàm tối ưu : Xấp xỉ hàm tối ưu bởi hàm tốt nhất trong lớp hàm H nào đó : Giả sử một thuật toán học khi chạy trên N ví dụ huấn luyện cho ra hàm (hàm này được chọn ra từ lớp hàm H), chẳng hạn: Thuật toán học có cho ra hàm gần với hàm tối ưu, khi số dữ liệu huấn luyện tăng vô hạn, tức là :Thuật toán học có cho ra hàm gần với hàm tốt nhất trong lớp hàm H, khi số dữ liệu huấn luyện tăng vô hạn, tức là : Đánh giá biên của sai số của hàm ?Lỗi đánh giá và lỗi xấp xỉLớp hàm H lớn : lỗi xấp xỉ sẽ nhỏ, đặc biệt nếu H đủ lớn để chứa hàm tối ưu thì lỗi xấp xỉ sẽ bằng 0 lỗi đánh giá (estimation error) lỗi xấp xỉ (approximation error) Khi lớp hàm H lớn, có thể chứa hàm cho sai số thực nghiệm nhỏ (có thể = 0), nhưng sai số của hàm đó lại lớn. Hiện tượng quá khớp (ouverfit).Vấn đề : H như thế nào để lỗi đánh giá nhỏ khi số dữ liệu N lớn? Lựa chọn lớp hàm H (lựa chọn mô hình) thích hợp với một nhiệm vụ học?Tính chất phù hợp (consistency) Một thuật toán học được gọi là phù hợp (consistent ), nếuMột thuật toán học được gọi là phù hợp (consistent ) đối với lớp hàm H, nếu Định lý (Vapnik – Chernovenkis, 1989). Điều kiện cần và đủ để phương pháp cực tiểu sai số thực nghiệm phù hợp đối với lớp hàm H là Tức là, sai số thực nghiệm hội tụ đồng đều (uniform convergence) trên lớp hàm H tới sai số kỳ vọng.SAI SỐ THỰC NGHIỆM ĐIỀU CHỈNH Một hướng tiếp cận : đưa vào lớp hàm H đủ lớn song đưa vào một “sự trừng phạt” cho các hàm phức tạp. Sai số thực nghiệm điều chỉnh :lượng điều chỉnh (regularier), độ đo “sự phức tạp” của h hệ số điều chỉnh và là tham số ĐỊNH LÝ BỮA ĂN KHÔNG MIỄN PHÍ Có nhiều thuật toán học. Câu hỏi : có thể nói thuật toán học A là tốt hơn thuật toán học B không? Có thuật toán nào là tốt nhất không? Câu trả lời : không.Đinh lý bữa ăn không miễn phí (No Free Lunch Theorem) . Định lý khẳng định rằng, lấy trung bình đồng đều trên tất cả các phân phối xác suất p(x,y), thì sai số ở ngoài tập huấn luyện của các thuật toán là bằng nhau. TÀI LIỆU THAM KHẢO V. vapnik (1995). The Nature Of Statistical Learning Theory.V. Vapnik (1998). Statistical Learning Theory.O. Bousquet, S. Boucheron, and G. Lugosi (2003). Introduction to Statistical Learning Theory. (In advanced Lectures on Machine Learning)U. V. Luxburg and B. Scholkopf (2008). Statistical Learning Theory : Models, Concepts, and Results.B. Scholkopf, and A. J. Smola (2002). Learning With Kernels (I. Concepts and Tools)