Consistent Hypothesis
ก่อนหน้านี้เราได้ดูตัวอย่างการวิเคราะห์ sample complexity และ generalization bound ของปัญหาการเรียนรู้มาบ้างแล้ว ในหัวข้อนี้เราจะมาวิเคราะห์ในกรณีของปัญหาการเรียนรู้ใด ๆ ที่อัลกอริทึมการเรียนรู้ของเราสามารถสร้าง hypothesis ที่เป็นคำตอบได้ เป็นจำนวนจำกัด นั่นคือ เมื่อ hypothesis class $H$ มีขนาดจำกัด
ถ้าให้ $H$ เป็นเซตของ hypothesis ทั้งหมดที่สร้างได้จากอัลกอริทึมการเรียนรู้ โดยที่ขนาดของ $H$ เป็นจำนวนจำกัด สมมติว่าเราทราบว่า $C\subseteq H$ หรือ concept เป้าหมาย $c$ ของเรานั้นเป็นสมาชิกใน $H$ ด้วย แนวทางการเรียนรู้หนึ่งที่ทำได้คือ เมื่อได้รับตัวอย่างข้อมูล มาแล้ว เราเลือก hypothesis ที่ตัดสินใจตามตัวอย่างข้อมูลทั้งหมดได้อย่างถูกต้อง นั่นคือเราเลือกตอบ hypothesis $h_S\in H$ ที่ สอดคล้อง (consistent) กับตัวอย่างข้อมูลทั้งหมด หรือกล่าวได้อีกอย่างว่า เราเลือก hypothesis $h_S$ ที่ $h_S(x)=y$ สำหรับตัวอย่างข้อมูล $(x,y)\in S$ ทุกตัวเป็นคำตอบ
เราจะมาวิเคราะห์กันว่าการเลือกตอบ hypothesis ตามแนวทางนี้จะสามารถใช้ในการเรียนรู้ตามกรอบการเรียนรู้แบบ PAC ได้หรือไม่
สังเกตว่าถ้าเรากำหนดค่าพารามิเตอร์ความผิดพลาด $\epsilon>0$ และพารามิเตอร์ความมั่นใจ $\delta>0$ สำหรับ hypothesis $h\in H$ ใด ๆ ที่มี $R(h)>\epsilon$ หรือ $\Pr_{x\sim D}[h(x)\neq c(x)] >\epsilon$ การที่ $h$ จะสอดคล้องกับตัวอย่างข้อมูล $(x,y)$ ใด ๆ ได้นั้น แสดงว่า $(x,y)$ จะต้องเป็นตัวอย่างข้อมูลที่ $h(x)=c(x)$ ซึ่งจะถูกสุ่มหยิบมาได้ด้วยความน่าจะเป็นไม่เกิน $1-\epsilon$ ดังนั้น ความน่าจะเป็นที่ $h$ จะสอดคล้องกับข้อมูลใน $S$ ทั้ง $m$ ตัวจะต้องมีค่าไม่เกิน $(1-\epsilon)^m$
การที่เรารับตัวอย่างข้อมูล $S$ มาและหา hypothesis ที่สอดคล้องกับ $S$ ทั้งหมดเป็นคำตอบนั้น สิ่งที่เราไม่ต้องการคือการได้ hypothesis $h\in H$ ที่ $R(h)>\epsilon$ เป็นคำตอบ ดังนั้นเราจึงต้องหาวิธีจำกัดความน่าจะเป็นที่จะเกิดเหตุการณ์ดังกล่าวนี้ สังเกตว่าเราจะเลือกตอบ hypothesis $h$ ที่มีความผิดพลาดสูง ($R(h)>\epsilon$) ได้ถ้ามี hypothesis ดังกล่าวบางตัวมีความสอดคล้องกับตัวอย่างข้อมูลใน $S$ ทั้งหมด ซึ่งจะเกิดขึ้นได้ด้วยความน่าจะเป็นดังนี้
ดังนั้นถ้าเราต้องการให้ hypothesis $h_S$ ที่เราเลือกเป็น hypothesis ที่มี error $R(h_S)\leq\epsilon$ ด้วยความน่าจะเป็นไม่ต่ำกว่า $1-\delta$ เราสามารถกำหนดให้ความน่าจะเป็นที่จะมี hypothesis ที่ error มากกว่า $\epsilon$ หลุดรอดมาเป็นตัวเลือกในคำตอบได้มีค่าไม่เกิน $\delta$ ซึ่งทำได้โดยกำหนดให้
ซึ่งจะได้ sample conplexity เป็น
หรือเราสามารถวิเคราะห์ generalization bound ได้ว่า ด้วยความน่าจะเป็นอย่างน้อย $1-\delta$ เราจะได้ผลลัพธ์เป็น hypothesis $h_S$ ที่มีความผิดพลาด
การเรียนรู้ Boolean Conjunction
ย้อนกลับมาพิจารณา ปัญหาการเรียนรู้ Boolean Conjunction บนตัวแปร $x_1\dots, x_n$ ซึ่งเราเคยวิเคราะห์ว่าสามารถเรียนรู้ได้โดยมี sample complexity เป็น $\frac{2n}{\epsilon}\ln\frac{2n}{\delta}$
สังเกตว่าอัลกอริทึมการเรียนรู้ของเรานั้นจะให้ hypothesis เป็น conjunction ที่สอดคล้องกับตัวอย่างข้อมูลที่ได้รับมาทั้งหมด เนื่องจากเรารับประกันได้ว่า literal ทั้งหมดที่มีอยู่ใน conjunction เป้าหมาย $c$ จะปรากฏใน hypothesis $h$ ที่เป็นคำตอบจากอัลกอริทึมแน่นอน นั่นแสดงว่า negative example ซึ่งขัดแย้งกับ $c$ จะต้องขัดแย้งกับ $h$ ด้วยเช่นกัน ในขณะที่อัลกอริทึมของเราจะมีการปรับปรุง hypothesis เพื่อให้สอดคล้องกับตัวอย่างข้อมูลที่เป็น positive example ทั้งหมด เราจึงสรุปได้ว่า hypothesis $h$ จากอัลกอริทึมนี้จะสอดคล้องกับตัวอย่างข้อมูล $S$ แน่นอน
เนื่องจากสำหรับ conjunction $c$ ใด ๆ สำหรับตัวแปร $x_i$ แต่ละตัว เรามีทางเลือกในการปรากฏอยู่ใน $c$ ทั้งสิ้น 3 ทางเลือก คือจะปรากฏเป็น $x_i$ หรือ $\bar{x}_i$ หรือไม่ปรากฏเลยก็ได้ ดังนั้นจะเห็นว่าจำนวน conjunction ทั้งหมดที่เป็นไปได้จะมีจำนวนเท่ากับ $3^n$ นั่นคือขนาดของ $H$ เท่ากับ $3^n$ นั่นเอง
จากการวิเคราะห์ของเราเมื่อ hypothesis space มีจำนวนจำกัด เราจึงได้ว่าอัลกอริทึมการเรียนรู้ conjunction เดียวกันนี้สามารถเรียนรู้ได้โดยมี sample complexity เป็น
ซึ่งดีกว่า sample complexity ที่วิเคราะห์ได้ก่อนหน้านี้
ในมุมของ generalization error เราก็สรุปได้ว่า hypothesis $h$ ที่เป็นผลลัพธ์จากการเรียนรู้จะมีความผิดพลาด