กรอบการเรียนรู้แบบ Probably Approximately Correct

ทฤษฎีการเรียนรู้เชิงคำนวณ (computational learning theory) สนใจการวิเคราะห์แง่มุมต่าง ๆ ของปัญหาการเรียนรู้และอัลกอริทึมการเรียนรู้ เพื่อตอบคำถามเช่น ปัญหาใดสามารถเรียนรู้ได้อย่างมีประสิทธิภาพ หรือ ในปัญหาการเรียนรู้หนึ่ง เราต้องการตัวอย่างข้อมูลมากแค่ไหนจึงเพียงพอที่เรียนรู้ได้สำเร็จ ในส่วนนี้เราจะทำความรู้จักกับกรอบการเรียนรู้ที่เรียกว่า probably approximately correct หรือ PAC ซึ่งจะช่วยให้เราสามารถนิยามและวิเคราะห์ปัญหาและอัลกอริทึมที่เกี่ยวกับการเรียนรู้ได้เป็นอย่างดี

PAC framework

กำหนดให้ $X$ เป็น input space หรือเซตของข้อมูลทั้งหมด และ $Y$ เป็นเซตของ label เพื่อความง่ายเราจะพิจารณากรณีที่ label ที่เป็นไปได้มีจำนวนเพียง 2 แบบเท่านั้น นั่นคือ $Y=\{0,1\}$ เราต้องการเรียนรู้ที่จะทำนาย label ใน $Y$ ที่ถูกต้องสำหรับ input $x\in X$ ใด ๆ เราเรียกประเภทของปัญหาการเรียนรู้เพื่อทำนาย label ที่ถูกต้องเช่นนี้ว่าปัญหา classification

เราจะเรียกฟังก์ชัน $c:X\to Y$ ใด ๆ ว่าเป็น concept ซึ่งในกรณีที่ $Y=\{0,1\}$ นั้น เราอาจมอง concept $c$ ใด ๆ ในรูปของเซต $\{x\in X: c(x)=1\}$ ก็ได้

สมมติให้การสุ่มหยิบข้อมูลใน $X$ แต่ละครั้งนั้นมีความเป็นอิสระภายใต้การกระจายตัวแบบเดียวกัน (independently and identically distributed หรือ i.i.d.) โดยเราให้ $D$ แทนการกระจายตัวของข้อมูล เราสามารถนิยามปัญหาการเรียนรู้อย่างเป็นทางการได้ดังนี้

นิยาม ปัญหาการเรียนรู้

พิจารณาเซตของ concept จำนวนหนึ่งซึ่งเราจะเรียกว่า hypothesis set $H$ หากเราได้รับเซตของตัวอย่างข้อมูลและ label ที่ถูกต้อง $S=\{(x_1,y_1),\dots,(x_m,y_m)\}$ ซึ่งถูกสุ่มหยิบมาแบบ i.i.d. บนการกระจายตัว $D$ โดยที่ label ทั้งหมดสอดคล้องกับ concept $c$ concept หนึ่ง (นั่นคือ $y_i=c(x_i)$ สำหรับ $i=1,\dots,m$) เราต้องการหา hypothesis $h\in H$ ที่มี generalization error $R(h)$ เมื่อเทียบกับ $c$ น้อยที่สุด

โดยเรานิยาม generalization error $R(h)$ ดังนี้

นิยาม generalization error

สำหรับ hypothesis $h$, concept เป้าหมาย $c$ และการกระจายตัวของข้อมูล $D$ generalization error ของ $h$ คือความน่าจะเป็นที่สุ่มหยิบข้อมูล $x$ จาก $D$ แล้วได้ว่า $h$ ทำนาย label ของ $x$ ไม่ตรงกับ $c$ หรือเราเขียนได้เป็น

ถึงตรงนี้เราสามารถพูดถึงประสิทธิภาพในการเรียนรู้ของปัญหาการเรียนรู้ได้ดังนี้

นิยาม PAC learning

ให้ $C$ เป็นคลาสของ concept เราจะกล่าวว่าคลาส $C$ สามารถ เรียนรู้ได้ ถ้ามีอัลกอริทึม $A$ ที่ สำหรับค่าคงที่ $\epsilon>0$ และ $\delta>0$ ใด ๆ, concept $c\in C$ ใด ๆ, และการกระจายตัวของข้อมูล $D$ ใด ๆ อัลกอริทึม $A$ สามารถให้ผลลัพธ์เป็น hypothesis $h$ ที่

เราเรียกค่าคงที่ $\epsilon$ ว่า พารามิเตอร์ความผิดพลาด (error parameter) และเรียกค่าคงที่ $\delta$ ว่า พารามิเตอร์ความมั่นใจ (confident parameter)

ถ้าอัลกอริทึม $A$ ใช้เวลาทำงานเป็น polynomial บน $1/\epsilon, 1/\delta, n,$ และ $size(c)$ เมื่อ $n$ เป็นขนาดของ representation ของ $x\in X$ ใด ๆ (เราอาจมองว่า $n$ เป็นมิติของ $X$ ก็ได้) และ $size(c)$ แทนขนาดของ representation ที่น้อยที่สุดของ $c$ เราจะกล่าวว่าปัญหาดังกล่าวสามารถ เรียนรู้ได้อย่างมีประสิทธิภาพ โดยทั่วไปแล้วอัลกอริทึมการเรียนรู้ที่เราสนใจมักมีการดำเนินการง่าย ๆ ต่อตัวอย่างข้อมูลแต่ละตัว ซึ่งทำให้เราสามารถวัดประสิทธิภาพของอัลกอริทึมจากจำนวนตัวอย่างข้อมูลที่ต้องการใช้แทนได้ เราเรียกจำนวนตัวอย่างข้อมูลที่ทำให้อัลกอริทึมเรียนรู้ได้สำเร็จว่า sample complexity ของอัลกอริทึมนั้น

Next: ปัญหาการเรียนรู้รูปสี่เหลี่ยมขนานแกน