Bayes Error
ในการวิเคราะห์ทั้งหมดที่ผ่านมา เราสมมติว่า label ที่ถูกต้องของ input $x\in X$ ใด ๆ นั้นสามารถระบุได้ชัดเจนด้วย concept $c:X\to Y$ และในการเรียนรู้จากตัวอย่างข้อมูล เราสมมติให้ตัวอย่างข้อมูล $(x,y)$ แต่ละตัวนั้น เราได้ $x$ มาจากการสุ่มด้วยการกระจาย $D$ บน input space $X$ และ label $y$ นั้นได้รับมาจาก $y=c(x)$ เราเรียกสถานการณ์นี้ว่าเป็นแบบจำลองการจำแนกข้อมูลแบบ deterministic
ในทางปฏิบัตินั้น เรามักจะเจอสถานการณ์ที่ข้อมูลใน input $x$ นั้นไม่เพียงพอที่จะสามารถแยกแยะ label ที่ถูกต้องได้ ตัวอย่างเช่น หากเราต้องการทำนายเพศของคนจากความสูงและน้ำหนัก จะเห็นว่ามีคู่ลำดับของความสูงและน้ำหนักจำนวนมากที่สามารถเป็นเพศใดก็ได้ ลักษณะปัญหาแบบนี้ทำให้เราไม่สามารถหาฟังก์ชันที่ทำนาย label $y$ จาก input $x$ ได้ถูกต้องเสมอ โดยสำหรับ input $x$ แต่ละตัว จะต้องมีการกระจายของความน่าจะเป็นที่ label $y$ ที่ถูกต้องจะมีค่าต่าง ๆ
เราเรียกแบบจำลองการจำแนกข้อมูลในลักษณะนี้ว่าเป็นแบบ stochastic โดยเราจะมองว่า $D$ เป็นการกระจายที่นิยามบน $X\times Y$ และตัวอย่างข้อมูล $(x,y)$ แต่ละตัวจะถูกสุ่มมาจาก $D$ โดยตรง และสำหรับ hypothesis $h\in H$ ใด ๆ เราจะนิยามให้ error ของ $h$ เป็น
เนื่องจากเราไม่สามารถทำนาย label $y$ ที่ถูกต้องจาก input $x$ ได้เสมอ แสดงว่าจะต้องไม่มี concept $c$ ที่ $R(c)=0$ แน่นอน นั่นคือ สำหรับฟังก์ชัน $f:X\to Y$ ใด ๆ เราจะได้ว่า $R(f)>0$ เสมอ เราจะนิยามให้ Bayes error $R^*$ เป็นค่า error ที่น้อยที่สุดที่เป็นไปได้จากฟังก์ชัน $f:X\to Y$ ใด ๆ นั่นคือ
และหาก hypothesis $h$ มี $R(h)=R^*$ เราก็จะเรียก $h$ ว่าเป็น Bayes hypothesis หรือ Bayes classifier สังเกตว่าสำหรับ Bayes classifier $h_{Bayes}$ เราสามารถนิยามการตัดสินใจของ $h_{Bayes}$ ด้วยความน่าจะเป็นแบบมีเงื่อนไขได้ดังนี้
ซึ่ง error เฉลี่ยของ $h_{Bayes}$ ที่ input $x\in X$ จะมีค่าเป็น
ซึ่งเป็น error ที่น้อยที่สุดที่เป็นไปได้ ถ้าเรานิยามให้ $noise(x)=\min(\Pr[0|x],\Pr[1|x])$ เราจะได้ว่า
เมื่อเราไม่สามารถรับประกันว่าจะมีฟังก์ชันใดที่สามารถจำแนกข้อมูลของเราได้โดยไม่ผิดพลาดเลยเช่นนี้ เป้าหมายในการเรียนรู้ของเราก็จะเปลี่ยนมาเป็นการพยายามหา hypothesis $h$ ที่มี $R(h)$ ใกล้เคียง $R^*$ ให้ได้มากที่สุด