การเรียนรู้แบบ PAC เมื่อมีการรบกวน

ในหัวข้อนี้เราจะมาวิเคราะห์เกี่ยวกับกรณีทั่วไปของการเรียนรู้ตามกรอบของ PAC สำหรับ hypothesis space $H$ ที่มีขนาดจำกัด เมื่อตัวอย่างข้อมูลที่ได้รับมามีการรบกวน โดยแบบจำลองการรบกวนที่เราสนใจนั้น จะเป็นการรบกวนที่ทำให้ label ที่เราได้รับสำหรับตัวอย่างข้อมูลตัวใด ๆ สามารถเปลี่ยนไปจากเดิมได้ด้วยความน่าจะเป็น $\eta$ ที่ $0<\eta<\frac{1}{2}$ โดยค่าที่แท้จริงของ $\eta$ นั้นไม่สามารถเข้าถึงได้ แต่เรารู้ขอบเขตบน $\eta’$ ที่ $\eta\leq\eta’<\frac{1}{2}$

ในขั้นตอนแรก ถ้าเรากำหนดให้ $d(h)$ แทนความน่าจะเป็นที่ตัวอย่างข้อมูลตัวหนึ่งที่เราได้รับมา (ซึ่งอาจจะถูกรบกวนจนทำให้ label สลับค่าไปแล้ว) ขัดแย้งกับการติดสินใจของ $h$ จะเห็นว่าเหตุการณ์ดังกล่าวเกิดขึ้นได้สองกรณี ได้แก่

เมื่อตัวอย่างข้อมูลที่สุ่มมาได้นั้นเป็นตัวอย่างข้อมูลที่ $h$ ตัดสินใจผิดอยู่แล้ว และตัวอย่างข้อมูลดังกล่าวรอดพ้นจากการถูกสลับ label ซึ่งจะเกิดขึ้นด้วยความน่าจะเป็นเท่ากับ $R(h)(1-\eta)$
เมื่อตัวอย่างข้อมูลที่สุ่มมาได้นั้นเป็นตัวอย่างข้อมูลที่ในความเป็นจริงแล้ว $h$ ตอบถูกต้อง แต่ตัวอย่างข้อมูลดังกล่างถูกรบกวนจนทำให้ label สลับค่าไป ทำให้เมื่อเราได้รับตัวอย่างข้อมูลดังกล่าวจึงพบว่า label ที่ได้นั้นขัดแย้งกับ $h$ ซึ่งเหตุการณ์ในกรณีนี้สามารถเกิดขึ้นได้ด้วยความน่าจะเป็นเท่ากับ $(1-R(h))\eta$

ดังนั้นเราจึงได้ว่า

$\begin{split} d(h) &=R(h)(1-\eta)+(1-R(h))\eta\\ &=R(h)-2R(h)\eta +\eta\\ &=\eta + R(h)(1-2\eta) \end{split}$

และสำหรับ hypothesis เป้าหมาย $c$ ที่ $R(c)=0$ เราจะได้ว่า $d(c)=\eta$

ถัดมา หากเรากำหนดค่า $\epsilon>0$ เป็นขอบเขตของ error ที่ต้องการจำกัด เมื่อพิจารณา hypothesis $h\in H$ ที่ $R(h)>\epsilon$ เราจะได้ว่า

$\begin{split} d(h) &=\eta + R(h)(1-2\eta)\\ &\geq\eta+\epsilon(1-2\eta)\\ &\geq\eta+\epsilon(1-2\eta') \end{split}$

เนื่องจาก $d(c)=\eta$ ดังนั้นเราจึงได้ว่า สำหรับ hypothesis $h\in H$ ใด ๆ ที่ $R(h)>\epsilon$ แสดงว่า $d(h)-d(c)\geq\epsilon(1-2\eta’)$

Hoeffding’s inequality

คราวนี้ ถ้าเราให้ $S=\{(x_1,y_1),\dots,(x_m,y_m)\}$ เป็นตัวอย่างข้อมูลที่แต่ละตัวถูกสุ่มมาอย่างเป็นอิสระจากกัน และผ่านการรบกวนที่อาจเปลี่ยน label ด้วยความน่าจะเป็น $\eta$ มาแล้ว ถ้าให้ $\hat{d}(h)$ แทนอัตราส่วนของตัวอย่างข้อมูลใน $S$ ที่มี label ขัดแย้งกับการตัดสินใจของ $h$ เราจะแสดงให้เห็นว่าเราสามารถวิเคราะห์ความสัมพันธ์ระหว่าง $\hat{d}(h)$ และ $d(h)$ ได้โดยถ้าจำนวนตัวอย่างข้อมูล $m$ ยิ่งมาก ความแตกต่างระหว่าง $\hat{d}(h)$ และ $d(h)$ ก็จะยิ่งน้อย

เครื่องมือที่เราจะใช้ในการวิเคราะห์ขอบเขตดังกล่าวคือ Hoeffding’s inequality ซึ่งกล่าวไว้ดังนี้

Hoeffding’s inequality ให้ $X_1,\dots,X_m$ เป็นตัวแปรสุ่มที่เป็นอิสระกัน $m$ ตัวโดยที่ $X_i$ มีค่าอยู่ในช่วง $[a_i,b_i]$ ถ้าให้ $S_m=\sum_{i=1}^mX_i$ เราจะได้ว่า

$\Pr[S_m-\mathbb{E}[S_m]\geq\epsilon]\leq e^{-2\epsilon^2/\sum_{i=1}^m(b_i-a_i)^2}$

และ

$\Pr[S_m-\mathbb{E}[S_m]\leq -\epsilon]\leq e^{-2\epsilon^2/\sum_{i=1}^m(b_i-a_i)^2}$

จาก Hoeffding’s inequality เราจะได้ว่าเมื่อเราพิจารณาตัวอย่างข้อมูล $S$ และ hypothesis $h\in H$ ที่มีอัตราการตัดสินใจขัดแย้งกับตัวอย่างข้อมูลใน $S$ เท่ากับ $\hat{d}(h)$ เราจะได้ว่า

$\Pr[\hat{d}(h)-d(h)\geq\epsilon]\leq e^{-2m\epsilon^2}$

และ

$\Pr[\hat{d}(h)-d(h)\leq -\epsilon]\leq e^{-2m\epsilon^2}$

จากตรงนี้ หากเราต้องการให้ hypothesis $h$ ทุกตัวใน $H$ มีค่า $d(h)-\hat{d}(h)$ ไม่เกิน $\epsilon’$ ด้วยความน่าจะเป็นไม่น้อยกว่า $1-\delta/2$ เราทำได้โดยจำกัดขอบเขตของความน่าจะเป็นที่จะมี $h\in H$ บางตัวที่ไม่เป็นไปตามต้องการ นั่นคือ

$\begin{split} \Pr[\exists h\in H: d(h)- \hat{d}(h)>\epsilon']&\leq\sum_{h\in H}\Pr[d(h)-\hat{d}(h)>\epsilon']\\ &\leq |H|e^{-2m\epsilon'^2} \end{split}$

เมื่อเรากำหนดให้ $|H|e^{-2m\epsilon'^2}\leq\frac{\delta}{2}$ ก็จะได้ว่า

$m\geq\frac{1}{2\epsilon'^2}(\ln|H|+\ln\frac{2}{\delta})$

ในทำนองเดียวกัน หากเราต้องการให้ $\hat{d}(c)- d(c)\leq\epsilon’$ ด้วยความน่าจะเป็นไม่น้อยกว่า $1-\delta/2$ เราก็ทำได้โดยพิจารณา

$\Pr[\hat{d}(c)- d(c)>\epsilon']\leq e^{-2m\epsilon'^2}$

ดังนั้นถ้ากำหนดให้ $e^{-2m\epsilon’^2}\leq\frac{\delta}{2}$ ก็จะได้

$m\geq\frac{1}{2\epsilon'^2}\ln\frac{2}{\delta}$

จากตรงนี้เราสรุปได้ว่า หากเรามีจำนวนตัวอย่างข้อมูลอย่างน้อย $\frac{1}{2\epsilon’^2}(\ln|H|+\ln\frac{2}{\delta})$ เราจะได้ว่า $\hat{d}(c)-d(c)\leq\epsilon’$ และ $d(h)-\hat{d}(h)\leq\epsilon’$ สำหรับ hypothesis $h\in H$ ทุกตัว ด้วยความน่าจะเป็นไม่ต่ำกว่า $1-\delta$

การเลือก hypothesis ที่ขัดแย้งกับตัวอย่างข้อมูลน้อยที่สุด

เราจะแสดงให้เห็นว่าการเลือกตอบ hypothesis $h$ ที่มีค่า $\hat{d}(h)$ น้อยที่สุดใน $H$ นั้นสามารถทำการเรียนรู้ตามกรอบของ PAC ได้ หากเราพิจารณา hypothesis $h\in H$ ใด ๆ ที่ $R(h)>\epsilon$ จะได้ว่า

$\begin{split} \hat{d}(h)-\hat{d}(c)& = [\hat{d}(h)-d(h)] + [d(h)-d(c)] + [d(c)-\hat{d}(c)]\\ &\geq \epsilon(1-2\eta') - [d(h)-\hat{d}(h)] - [\hat{d}(c)-d(c)] \end{split}$

ดังนั้น เนื่องจากอัลกอริทึมของเราจะเลือกตอบ hypothesis $h\in H$ ที่มี $\hat{d}(h)$ น้อยที่สุด หากเราต้องการให้อัลกอริทึมของเราไม่เลือก $h$ ที่ $R(h)>\epsilon$ เราสามารถกำหนดให้

$\epsilon' = \frac{\epsilon(1-2\eta')}{2}$

ซึ่งจะทำให้

$\epsilon(1-2\eta') - [d(h)-\hat{d}(h)] - [\hat{d}(c)-d(c)]\geq 0$

และได้ว่า $\hat{d}(h)\geq\hat{d}(c)$ ด้วยความน่าจะเป็นอย่างน้อย $1-\delta$ นั่นคือ ด้วยความน่าจะเป็นดังกล่าว hypothesis $h\in H$ ใด ๆ ที่ $R(h)>\epsilon$ จะไม่ใช่ hypothesis ที่มี $\hat{d}(h)$ น้อยที่สุด ดังนั้นคำตอบที่จะได้จากอัลกอริทึมของเราก็จะเป็น hypothesis ที่ $R(h)\leq\epsilon$ ตามต้องการ

จากตรงนี้จะเห็นว่า การกำหนดให้ $\epsilon’=\frac{\epsilon(1-2\eta’)}{2}$ แสดงว่าการเรียนรู้ด้วยวิธีนี้จะมี sample complexity เป็น

$m\geq \frac{2}{\epsilon^2(1-2\eta')^2}(\ln|H|+\ln\frac{2}{\delta})$

Prev: การเรียนรู้รูปสี่เหลี่ยมขนานแกนเมื่อมีการรบกวน

Next: Bayes Error

Computational-Learning-Theory

ทฤษฎีการเรียนรู้เชิงคำนวณ

การเรียนรู้แบบ PAC เมื่อมีการรบกวน

Hoeffding’s inequality

การเลือก hypothesis ที่ขัดแย้งกับตัวอย่างข้อมูลน้อยที่สุด