Một số bất đẳng thức về lỗi phân lớp đối với bài toán phân lớp nhị phân

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

12
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài toán phân lớp nhị phân là một bài toán cơ bản trong bài toán phân lớp thuộc nhóm các thuật toán học có giám sát. Người ta sử dụng một hàm phân loại để gán một điểm dữ liệu với một trong 2 lớp đã cho dựa trên một tập dữ liệu khảo sát được đã được gán nhãn. Ở bài viết này, tác giả nghiên cứu và xây dựng một số bất đẳng thức để đánh giá về lỗi phân lớp trong bài toán phân lớp nhị phân.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Một số bất đẳng thức về lỗi phân lớp đối với bài toán phân lớp nhị phân

ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ - ĐẠI HỌC ĐÀ NẴNG, VOL. 22, NO. 3, 2024 49 MỘT SỐ BẤT ĐẲNG THỨC VỀ LỖI PHÂN LỚP ĐỐI VỚI BÀI TOÁN PHÂN LỚP NHỊ PHÂN SOME INEQUALITIES ON CLASSIFICATION ERRORS FOR BINARY CLASSIFICATION Tôn Thất Tú* Trường Đại học Sư phạm - Đại học Đà Nẵng, Đà Nẵng, Việt Nam1 *Tác giả liên hệ / Corresponding author: tttu@ued.udn.vn (Nhận bài / Received: 10/12/2023; Sửa bài / Revised: 31/01/2024; Chấp nhận đăng / Accepted: 02/02/2024) Tóm tắt - Bài toán phân lớp nhị phân là một bài toán cơ bản trong Abstract - The binary classification problem is a basic problem in bài toán phân lớp thuộc nhóm các thuật toán học có giám sát. the classification problem of the group of supervised learning Người ta sử dụng một hàm phân loại để gán một điểm dữ liệu với algorithms. One uses a classification function to assign a data point một trong 2 lớp đã cho dựa trên một tập dữ liệu khảo sát được đã to one of two given classes based on a labeled collected data set. This được gán nhãn. Hành động này có thể mắc sai lầm nếu việc gán action can be erroneous if the labeling of data points is incorrect. nhãn cho các điểm dữ liệu không chính xác. Có nhiều thuật toán There are many different algorithms that have been studied related to khác nhau đã được nghiên cứu liên quan đến bài toán phân lớp the binary classification problem. To measure the quality of the nhị phân. Để đo lường chất lượng của hàm phân lớp, người ta đưa classification function, people introduce some concepts about the ra một số khái niệm về lỗi mắc phải khi tiến hành phân lớp. Ở bài errors made when performing classification. In this article, the author báo này, tác giả nghiên cứu và xây dựng một số bất đẳng thức để researches and builds a number of inequalities to evaluate the đánh giá về lỗi phân lớp trong bài toán phân lớp nhị phân. classification errors in the binary classification problem. Từ khóa - Phân lớp; nhị phân; lỗi phân lớp; bất đẳng thức; học Key words - Classification; binary; classification error; máy thống kê. inequality; statistical machine learning. 1. Giới thiệu 1,  ( x)  1/ 2 Kí hiệu g * ( x) =  Bài toán phân lớp nhị phân là bài toán cơ bản, được nhiều 0,  ( x)  1/ 2 tác giả nghiên cứu về cách thức tiếp cận cũng như đánh giá chất lượng của các thuật toán [1, 2, 3]. Giả sử ( X , Y ) là một và L* = L( g* ) = P( g* ( X )  Y ). cặp biến ngẫu nhiên nhận giá trị trong Rd {0,1}. Để mô tả Định lý 1. [2] Với mọi hàm phân lớp g : Rd → {0,1} phân phối của ( X , Y ) ta có thể sử dụng cặp giá trị (  , ) , ta luôn có: trong đó  là độ đo xác suất sinh bởi biến ngẫu nhiên X P( g* ( X )  Y )  P( g ( X )  Y ), và  là hàm hồi quy của Y theo X , tức là tức là g * là hàm phân lớp tối ưu.  ( A) = P( X  A) với A là tập Borel trên R , d Hàm g * được gọi là hàm phân lớp Bayes và giá trị L* ( x) = P(Y = 1| X = x) = E(Y | X = x), x R . d được gọi là xác suất lỗi Bayes. Một hàm g : Rd → {0,1} được gọi là một hàm phân Với x  R ta có d lớp (classifier, decision function) và giá trị P( g ( X )  Y | X = x) = 1- P( g ( X ) = Y | X = x) L( g ) = P ( g ( X )  Y ) = 1-[ P(Y = 1, g ( x) = 1| X = x) được gọi là xác suất lỗi (error probability, misclassification + P(Y = 0, g ( x) = 0 | X = x)] error) của hàm phân lớp g . = 1-[ I{ g ( x ) =1} P(Y = 1| X = x) Để tính được giá trị của L ( g ) ta cần phải biết phân phối + I{ g ( x ) = 0} P(Y = 0 | X = x)] chính xác của ( X , Y ). Tuy nhiên, trên thực tế ta thường không = 1-[ I{ g ( x ) =1} ( x) + I{ g ( x ) = 0} (1- ( x))]. biết được thông tin này. Thông tin mà ta biết được thường là dữ liệu được thu thập từ ( X , Y ). Nếu ( X 1 , Y1 ),..., (X n , Yn ) là Do đó, một mẫu ngẫu nhiên của ( X , Y ) thì giá trị L( g ) = 1 − E(I{g ( X )=1}( X ) + I{g ( X ) =0} (1 -( X ))) 1 n và Ln ( g ) =  I{g ( X i ) Yi } n i =1 L* = L( g * ) = 1 − E ( I{ ( X ) 1/ 2} ( X ) + I{ ( X ) 1/ 2} (1-  ( X ))) được gọi là xác suất lỗi thực nghiệm (empirical error 1 1 = E min{ ( X ),1 −  ( X )} = − E | 2 ( X ) − 1 | . probability) của hàm phân lớp g . 2 2 1 The University of Danang – University of Science and Education, Danang, Vietnam (Ton That Tu)
50 Tôn Thất Tú Ngoài việc sử dụng L ( g ) để đo xác suất mắc sai lầm Bất đẳng thức này đúng vì x  [0,1/2] và khi phân lớp, người ta còn sử dụng các hàm sau để đo 1 − x + x  2. “khoảng cách” giữa hai lớp [2]: Tương tự, bất đẳng thức ở phía phải được biến đổi như sau: i) Khoảng cách Kolmogorov: 1 1 1 h( x ) − f ( x )  2 x − h( x )  KO = E | P(Y = 1| X ) − P(Y = 0 | X ) | = E | 2 ( X ) − 1| . 2 2 2 ii) Lỗi phân lớp tiệm cận cho “phương pháp người láng  x 1 − x − x  (1 − 2 x ) x (1 − x ) giềng”: x (1 − 2 x )  1  LNN = E (2 ( X )(1 −  ( X ))).   − 1  0 1 − x  1 − x + x (1 − x )    iii) Lỗi Matsushita: =E ( )  ( X )(1 −  ( X )) .  x (1 − 2 x ) ( x − 1− x ) 0 iv) Entropy có điều kiện trung bình: ( 1 − x 1 − x + x (1 − x ) )  = − E ( ( X ) ln  ( X ) + (1 −  ( X )) ln(1 −  ( X ))). Bất đẳng thức này đúng vì x  [0, 1/ 2]. v) Độ khác biệt Jeffrey: b) Với x  [0, 1/2] đặt l ( x) = e( x) − 2 ln 2 g ( x). Lúc đó,    ( X )  1 − 2x J = E (2 ( X ) − 1) ln   . l( x) =  0,  x  [0, 1/2]   1 − ( X )  x 2 (1 − x)2 1 nên l ( x ) là hàm lồi trên [0, 1/2]. Mặt khác, ta lại có Dễ thấy rằng, L = * −  KO . Điều này có nghĩa nếu xác 2 lim l ( x ) = +, l(1/ 2) = 0, l(1/ 4) = ln(3 / 4)  0 suất lỗi Bayes giảm thì khoảng cách Kolomogov  KO sẽ x → 0+ tăng dần tiến đến 1/ 2 và ngược lại. nên tồn tại duy nhất x0 (0, 1/ 2) sao cho l( x0 ) = 0. Từ đó 2. Kết quả chính suy ra Xét các hàm f , g , h, e, j :[0,1] → R xác định như sau: l ( x)  min {l (0), l (1/ 2)} = 0, x [0, 1/ 2]. ◼ f ( x) = min {x,1- x}, g ( x) = 2 x(1- x), h( x) = x(1 − x), Bổ đề 2. Với mọi x  (0,1) và n  N ta luôn có * 22 k −1  2k  x  n 1 e( x) = − x ln x − (1 − x) ln(1 − x), j ( x) = (2 x − 1) ln  . e( x)  ln 2 −  x−  . 1− x  k =1 k (2k − 1)  2 Dễ thấy rằng, với mọi x  [0,1] ta luôn có: Chứng minh: Với n  1 đạo hàm cấp n của e( x ) bằng: f ( x)  min{h( x), g ( x)}.  − ln x + ln(1 − x), n =1  Bổ đề 1: Với x  [0,1] ta luôn có: e ( x) =  (−1) (n − 2)! ( n − 2)! (n) n −1  − , n 1  x n −1 (1 − x) n −1 1 1 a) 2 x− f ( x )  h( x ) − f ( x )  2 x − h( x). 2 2 Từ đó, suy ra n  1 ta có: b) e( x)  2 ln 2 g ( x). 0, n = 2k + 1 e( n ) (1 / 2) =  2 k với k N* .  −2 (2k − 2)!, n = 2k Chứng minh: Vì với mọi x  [0,1] ta luôn có e( x) = e(1 − x), f ( x) = f (1 − x), g ( x) = g (1 − x) Theo công thức khai triển Taylor [4] với mọi x  (0, 1) tồn tại  nằm giữa 1/ 2 và x sao cho: và h( x) = h(1 − x) nên ta chỉ cần chỉ ra các bất đẳng thức 2n+ 2 1  e(2 n + 2) ( )  2 n +1 k e( k ) (1/ 2)  1 trên đúng với x  [0,1/2]. e( x ) =  x−  + x−  k =0 k!  2 (2n + 2)!  2 a) Với x  [0,1/2] bất đẳng thức ở phía trái trở thành: 2n+ 2 e(2 n + 2) ( )  1 1 Vì  (0, 1) nên x−   0. h( x ) − f ( x )  2 x − f ( x) (2n + 2)!  2 2 1  Do đó, với mọi x  (0, 1)  x 1− x − x  2  − x  x  2  2 n +1 e( k ) (1/ 2)  1 k n 22 k −1  1 2k  1 2 e( x )   k!   x −  = ln 2 −  2 x−  . k =1 k (2k − 1)  2  x (1 − 2 x )   1 − x + x − 2   0.  k =0   Bổ đề được chứng minh. ◼
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ - ĐẠI HỌC ĐÀ NẴNG, VOL. 22, NO. 3, 2024 51 Bổ đề 3. Với mọi x  (0,1) và n  N ta luôn có * 1 1  Mặt khác, vì x − x  2 x  − x  , x [0, 1/ 2] nên 2 n  2 k +1 1 2k 2 2  j ( x)   x−  . k =1 2k − 1  2 1 2E  ( X ) − f ( ( X )) Chứng minh: Với n  1 đạo hàm cấp n của 2 ln( x / (1 − x)) bằng: 1 1 1 = 2 E (X ) − − ( X ) − (n − 1)! (−1) (n − 1)!n 2 2 2 ( ln( x / (1 − x)) ) = − , x (0, 1). (n) (1 − x)n xn 1 1 1  2 E (X ) −  − ( X ) −  Từ đó, với n  2 sử dụng công thức đạo hàm của tích 2  2 2 ta có: 1 2 =  KO − 2E  ( X ) − . j ( n ) ( x) = (2 x − 1) ( ln( x / (1 − x)) ) (n) 2 + 2n ( ln( x / (1 − x)) ) ( n −1) Định lý được chứng minh. ◼ (n − 2 x + 1)(n − 2)! Định lý 2. Giá trị entropy thỏa mãn bất đẳng thức: = (1 − x) n E  2 ln 2 LN . (−1) n (n − 2 x + 1)(n − 2)! Nói riêng, E  4 ln 2 L* (1 − L* ). + , x (0, 1). xn Chứng minh: Bất đẳng thức được suy ra trực tiếp từ Bổ Suy ra đề 1 và nhận xét: 0, n = 2k − 1 x(1 − x) = min {x,1- x}(1- min {x,1- x}), x  [0, 1]. ◼ j ( n ) (1 / 2) =  n +1 với k N* . 2 n(n − 2)!, n = 2k Định lý 3. Entropy và độ khác biệt Jeffrey thỏa mãn các Lúc đó, sử dụng khai triển Taylor [1] với mọi x  (0, 1) bất đẳng thức sau: 22 k −1  * 1  2k tồn tại  nằm giữa 1/ 2 và x sao cho: n E  ln 2 −  L −  2n+ 2 k =1 k (2k − 1)  2 j (2 n + 2) ( )  2 n +1 k j ( k ) (1/ 2)  1 1 j ( x) =  k!   x−  + 2 (2n + 2)!  x−  2 n 22 k +1  * 1  2k J  k =0 Và L −  , k =1 2k − 1  2 2n+ 2 j (2 n + 2) ( )  1 Vì  (0, 1) nên x−   0. (2n + 2)!  2 với mọi n  N* . Do đó, với mọi x  (0, 1) Chứng minh: Với x (0,1) ta luôn có: 2 2 2 n +1 j ( k ) (1/ 2)  1 n 22 k +1  k 1 2k  1  1 j ( x)    x−  =  x−  .  x −  =  min{x,1- x} −  . k =1 k!  2 k =1 2k − 1  2  2  2 Bổ đề được chứng minh. ◼ Do đó, từ Bổ đề 2 và bất đẳng thức Jensen [5] ta có: Định lý 1. Độ lệch  − L* thỏa mãn bất đẳng thức: 22 k −1 2k n  1 E = E e( ( X ))  ln 2 −  E  ( X ) −  2 k =1 k (2k − 1)  2 1  KO − 2 E  ( X ) −   − L*   KO 1 − 4 KO . 2 22 k −1 2k n  1 2 = ln 2 −  E  min { ( X ),1 −  ( X )} −  Chứng minh: Từ Bổ đề 1 ta có: k =1 k (2k − 1)  2 22 k −1  * 1  n 2k  ln 2 −  1 2E  ( X ) − f ( ( X )) L −  . 2 k =1 k (2k − 1)  2 1 Bất đẳng thức còn lại được suy ra từ Bổ đề 3 và được   − L*  2 E  ( X ) − h( ( X )). 2 chứng minh tương tự. ◼ Áp dụng bất đẳng thức Jensen [5], ta được: Trường hợp đặc biệt khi n = 1 ta được hệ quả sau: 2 Hệ quả 1 [2]: Entropy và độ khác biệt Jeffrey thỏa mãn 1 1 1 1 E  ( X ) − h( ( X )) = E  ( X ) − − ( X ) − các bất đẳng thức sau: 2 2 4 2 (1 − 2 L* ) 2 2 E  ln 2 − và J  2(1 − 2L* )2 . 1 1  1 2  E (X ) − −  E ( X ) −  2 4  2 Để đánh giá xác suất lỗi lý thuyết L ( g ) thông qua xác 1 suất lỗi thực nghiệm Ln ( g ) , ta có thể sử dụng các bất đẳng =  KO −  KO . 2 4 thức về mức độ tập trung (concentration inequalities) cho
52 Tôn Thất Tú tổng của các biến ngẫu nhiên độc lập. Bổ đề 4 (Bất đẳng thức Hoeffding) [5, 6]. Cho X 1 ,..., X n Zn = ( L ( g ) − L( g ) ) n n L( g ).(1 − L( g )) là các biến ngẫu nhiên độc lập với P(ai  X i  bi ) = 1 với có phân phối xấp xỉ phân phối chuẩn tắc N (0,1). Lúc đó, với mọi i = 1, n , trong đó ai , bi  R, ai  bi . Khi đó, với mọi n độ tin cậy 1 −  khoảng tin cậy cho xác suất lỗi L ( g ) là: t  0 và S = ( X i − EX i ) ta luôn có: i =1  2nLn ( g ) + z / 2 2 2nLn ( g ) + z / 2 2   −, − ,  n   2(n + z / 2 ) 2 2(n + z / 2 ) 2  P( S  t )  exp  −2t 2 / (bi − ai ) 2  ,     ( ). i =1 z / 2 z / 2 + 4nLn ( g ) 1 − Ln ( g ) 2  n  trong đó = P(| S | t )  2exp  −2t 2 / (bi − ai ) 2  . 2(n + z / 2 ) 2  i =1  Hệ quả 2: Khoảng tin cậy cho xác suất lỗi L ( g ) của hàm phân lớp g với độ tin cậy tối thiểu 1 −  là:  1 2 1  2   Ln ( g ) − ln   , Ln ( g ) + ln    .  2n     2n      Chứng minh: Áp dụng bất đẳng thức Hoeffding cho các biến ngẫu nhiên I{ g ( X i ) Yi } , với mọi   0 ta có:  n  ( ) P   I{ g ( X i ) Yi } − L( g )  n   i =1  Hình 1. Khoảng tin cậy 95% với Ln ( g ) = 1/ | n − 40 |  2(n ) 2  −2 n  2  2exp  −  = 2e . Từ Hình 1 có thể thấy, khoảng tin cậy được xây dựng  n  bởi phép xấp xỉ phân phối chuẩn tốt hơn theo nghĩa độ dài Điều này tương đương với khoảng tin cậy nhỏ hơn. Mặc dù vậy, chất lượng của ( ) khoảng tin cậy này phụ thuộc nhiều vào chất lượng của P Ln ( g ) − L( g )    2e−2 n  2 phép xấp xỉ phân phối chuẩn. ( ) Hay P Ln ( g ) − L( g )    1 − 2e−2 n  . 2 3. Kết luận Bài báo đã trình bày một số kết quả nghiên cứu về bất 1 2 đẳng thức đánh giá lỗi phân lớp cho bài toán phân lớp nhị Cho 2e−2 n  =  (0, 1). Lúc đó  = 2 ln   và phân. Sử dụng bất đẳng thức Hoeffding và định lý giới hạn 2n    trung tâm, khoảng tin cậy cho xác suất lỗi lý thuyết cũng  1  2  được xây dựng. Khi kích thước mẫu càng lớn, phép xấp xỉ P  Ln ( g ) − L( g )  ln     1 −  . phân phối chuẩn càng chính xác và lúc đó ta nên sử dụng  2n       khoảng tin cậy cho xác suất lỗi lý thuyết được xây dựng Từ đó, ta được điều phải chứng minh. ◼ dựa trên phép xấp xỉ này. Nhận xét 1: Nếu muốn độ dài khoảng tin cậy cho xác TÀI LIỆU THAM KHẢO suất lỗi L ( g ) được xây dựng ở trên không vượt quá [1] A. K. Menon and R. C. Williamson, “The Cost of Fairness in Binary  0  0 cho trước, ta cần chọn n sao cho: Classification”, Proceedings of Machine Learning Research, vol. 81, pp. 1-12, 2018. 1 2 [2] L. Devroye, L. Gyorfi, and G. Lugosi, A Probabilistic Theory of 2 ln     0 . 2n    Pattern Recognition, Springer-Verlag, 1996. [3] S. Singh and J. Khim, “Optimal Binary Classification Beyond Từ đó, ta được: Accuracy”, 36th Conference on Neural Information Processing Systems, 2022. 2 2 n ln   . [4] N. D. Tien, Lectures on Mathematical Analysis (Vol. 1), Hanoi 0    2 National University Publishing House, 2004. [5] M. Sugiyama, Introduction to Statistical Machine Learning, Nhận xét 2: Sử dụng định lý giới hạn trung tâm [5], ta Elsevier Inc., 2016. có khi n lớn biến ngẫu nhiên [6] B. Stephane, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013.