ขอบเขตของ Growth Function

หากเราย้อนกลับมาดู generalization bound ของ error ของ hypothesis ที่ได้จากการเรียนรู้แบบ PAC ในกรณีที่ hypothesis space $H$ มีขนาดจำกัด เราสรุปได้ว่าหากมี hypothesis $c\in H$ ที่ $R(c)=0$ อยู่จริง เราสามารถทำการเรียนรู้โดยการหา hypothesis $h$ ที่ consistent กับตัวอย่างข้อมูลทั้งหมด ซึ่งจะทำให้ได้ผลลัพธ์เป็น $h\in H$ ที่รับประกันได้ว่า ด้วยความน่าจะเป็นไม่น้อยกว่า $1-\delta$

ในขณะที่กรณีของ Agnostic-PAC สำหรับ hypothesis $h\in H$ ใด ๆ ที่มี empirical error เป็น $\hat{R}(h)$ เราสามารถสรุปขอบเขตของ error จริงของ $h$ ได้ว่า ด้วยความน่าจะเป็นไม่น้อยกว่า $1-\delta$

เมื่อ $H$ ของเรามีขนาดเป็นอนันต์ เราจำเป็นจะต้องหาเครื่องมือสำหรับวัดความซับซ้อนของ $H$ มาใช้แทน $|H|$ ซึ่งทางเลือกหนึ่งที่น่าสนใจคือการใช้ growth function $\Pi_H(m)$ เนื่องจาก $\Pi_H(m)$ นั้นสื่อถึงของเขตของขนาดของ $H$ เมื่อพิจารณาบนตัวอย่างข้อมูลจำนวนจำกัด หากลองคิดเล่น ๆ ว่าเราจะนำค่า $\Pi_H(m)$ มาแทนที่ $|H|$ ตรง ๆ ใน error bar $\frac{1}{m}(\ln|H| + \ln\frac{1}{\delta})$ และ $\sqrt{\frac{1}{2m}(\ln |H| + \frac{2}{\delta})}$ จะเห็นว่า ถ้า $H$ มีความซับซ้อนมากเช่นเมื่อ VC-dimension ของ $H$ เป็น $\infty$ หรือ $\Pi_H(m)=2^m$ เสมอ เราจะได้ว่า error bar ของการเรียนรู้ทั้งสองแบบจะไม่ลู่เข้าสู่ศูนย์เมื่อจำนวนตัวอย่างข้อมูล $m$ มีค่ามากขึ้น แต่ถ้า hypothesis space $H$ ของเรามี $\Pi_H(m)$ เป็น polynomial บน $m$ เราก็จะยังสามารถลด error bar ด้วยการเพิ่มจำนวนข้อมูล $m$ ได้

ในหัวข้อนี้เราจะแสดงให้เห็นว่า ถ้า hypothesis space $H$ มี VC-dimension เป็นจำนวนจำกัด (ไม่ใช่ $\infty$) ค่าของ $\Pi_H(m)$ จะมีอัตราการโตเป็น polynomial บน $m$

ตัวอย่างการนับ $\Pi_H(m)$ สำหรับ $H$ ที่มี VC-dimension เป็นจำนวนจำกัด

ก่อนที่จะพิสูจน์ให้เห็นว่าสำหรับ $H$ ใด ๆ ที่มี VC-dimension เป็นจำนวนจำกัดนั้น $\Pi_H(m)$ เป็น polynomial บน $m$ เราจะมาลองดูตัวอย่างในกรณีง่าย ๆ กันก่อนเพื่อที่จะได้เห็นว่า เงื่อนไขจาก VC-dimension ที่เป็นจำนวนจำกัดนั้น ทำให้จำนวน dichotomy ที่สามารถสร้างได้จาก $H$ นั้นน้อยกว่า $2^m$ อยู่มาก

สมมติให้ $H$ เป็น hypothesis space ที่มี VC-dimension เท่ากับ 1 นั่นคือ สำหรับตัวอย่างข้อมูล 2 ตัวใด ๆ $H$ จะต้องไม่สามารถสร้าง dichotomy ของตัวอย่างข้อมูลทั้งสองตัวได้ครบทุกรูปแบบ คราวนี้เราลองมานับจำนวน dichotomy ของตัวอย่างข้อมูลจำนวนสามตัวที่สร้างได้จาก $H$ เราจะลองนับโดยการพิจารณาการให้ label ของตัวอย่างข้อมูล $x_1,x_2,x_3$ ตามลำดับ $(0,0,0), (0,0,1),\dots,(1,1,1)$ โดยที่ หากการให้ label แบบใดทำให้มีตัวอย่างข้อมูลคู่หนึ่งที่มี dichotomy ครบทุกแบบเกิดขึ้น ซึ่งแสดงว่า $H$ shatter ข้อมูลคู่นั้นได้ เราจะตัดการให้ label นั้นออกไป

เราจะแสดงผลการนับตามที่กล่าวมาด้วยตารางต่อไปนี้

จากตัวอย่างจะเห็นว่าจำนวน dichotomy ที่สร้างได้จริงนั้นมีเพียง 4 แบบเท่านั้น ในความเป็นจริงแล้วการเลือกนับ dichotomy ที่เป็นไปได้ตามลำดับนี้อาจไม่ใช่ทางเลือกที่ทำให้ได้จำนวน dichotomy มากที่สุด แต่อย่างไรก็ตาม ตัวอย่างนี้แสดงให้เห็นว่าข้อจำกัดของ VC-dimension นั้นมีผลอย่างมากต่อจำนวน dichotomy ที่เกิดขึ้นได้ หรือก็คือขอบเขตของ growth function $\Pi_H(m)$ นั่นเอง

Recurrent relation ของขอบเขตของ $\Pi_H(m)$

เราจะเริ่มวิเคราะห์ขอบเขตของ $\Pi_H(m)$ ในกรณีทั่วไป เมื่อ $H$ มี VC-dimension เท่ากับ $d$ สมมติให้ $B(m,d)$ แทนจำนวน dichotomy ที่มากที่สุดที่เป็นไปได้บนตัวอย่างข้อมูล $m$ ตัว เมื่อ $d$ เป็นจำนวนตัวอย่างข้อมูลที่มากที่สุดที่ถูก shatter ได้ด้วย dichotomy เหล่านี้ หรือกล่าวอีกอย่างว่า $B(m,d)$ คือจำนวน dichotomy ที่มากที่สุดที่เป็นไปได้ที่ไม่ shatter ตัวอย่างข้อมูล $d+1$ ตัวใด ๆ หากเราคำนวณค่าของ $B(m,d)$ ได้ เราจะได้ว่า

เราเริ่มพิจารณากรณีพื้นฐานของ $B(m,d)$ กันก่อน สังเกตว่าไม่ว่าจำนวนข้อมูล $m$ จะเป็นเท่าไหร่ก็ตาม ถ้า $d=0$ เราจะได้ว่า $B(m,0)=1$ เนื่องจากหากมีจำนวน dichotomy ที่แตกต่างกันมากกว่า 1 แบบ จะต้องมีตัวอย่างข้อมูลอย่างน้อยหนึ่งตัวที่ถูก label ได้ทั้งสองวิธีซึ่งเป็นไปไม่ได้เนื่องจาก $d=0$

นอกจากนี้ สำหรับ $d\geq 1$ ใด ๆ หาก $m=1$ เราก็จะมีจำนวน dichotomy ได้สูงสุดเท่ากับ 2 แบบเสมอ

คราวนี้พิจารณาเมื่อ $m>1$ และ $d\geq 1$ สมมติว่าเราแจกแจง dichotomy ที่เป็นไปได้ทั้ง $B(m,d)$ แบบออกมาเป็นตารางด้านล่างนี้ โดยแบ่ง dichotomy ทั้งหมดออกเป็นสามกลุ่ม ได้แก่ $S_1$ ประกอบด้วย dichotomy ที่เมื่อพิจารณา dichotomy ย่อยของตัวอย่างข้อมูล $x_1,\dots,x_{m-1}$ จะพบว่าปรากฏเพียงครั้งเดียว dichotomy ที่อยู่นอก $S_1$ จะสามารถจับเป็นคู่ที่มี dichotomy ย่อยของ $x_1,\dots,x_{m-1}$ เหมือนกันและมีเพียง label ของ $x_m$ ที่ต่างกันได้ เราให้ $S_2^0$ ประกอบด้วย dichotomy ที่ไม่อยู่ใน $S_1$ ที่มี label ของ $x_m$ เป็น 0 และให้ $S_2^1$ ประกอบด้วย dichotomy ที่ไม่อยู่ใน $S_1$ ที่มี label ของ $x_m$ เป็น 1

สมมติให้จำนวน dichotomy ใน $S_1$ มีทั้งสิ้น $\alpha$ แบบ และให้จำนวน dichotomy ใน $S_2^0$ มีทั้งสิ้น $\beta$ แบบ เนื่องจาก dichotomy แต่ละแบบใน $S_2^0$ จะมีคู่ที่เหมือนกันทั้งหมดยกเว้น label ของ $x_m$ อยู่ใน $S_2^1$ ดังนั้นจำนวน dichotomy ใน $S_2^1$ ก็จะเท่ากับ $\beta$ ด้วยเช่นกัน จากตรงนี้เราจะได้ว่าจำนวน dichotomy ทั้งหมดในตารางนี้จะมีค่าเป็น

หากเราลองพิจารณาเฉพาะ dichotomy บนตัวอย่างข้อมูล $x_1,\dots,x_{m-1}$ ในตาราง สังเกตว่า dichotomy ของ $x_1,\dots,x_{m-1}$ ที่อยู่ในเซต $S_1$ แต่ละแบบนั้นจะไม่มีทางซ้ำกับ dichotomy ตัวอื่น ในขณะที่ dichotomy แต่ละแบบใน $S_2^0$ จะปรากฏอยู่ใน $S_2^1$ เช่นกัน ดังนั้นจะเห็นว่าจำนวน dichotomy บน $x_1,\dots,x_{m-1}$ ที่แตกต่างกันทั้งสิ้นในตารางนี้จะเท่ากับจำนวน dichotomy ใน $S_1\cup S_2^0$ ซึ่งเท่ากับ $\alpha + \beta$ และเนื่องจาก dichotomy เหล่านี้จะต้องไม่ shatter ตัวอย่างข้อมูล $d+1$ ตัวใด ๆ (เพราะ dichotomy เดิมที่รวม $x_m$ ด้วยก็ไม่ shatter ตัวอย่างข้อมูล $d+1$ ตัวใด ๆ เช่นกัน) เราจึงได้ว่าจำนวน dichotomy ของ $x_1,\dots,x_{m-1}$ ที่ปรากฏในตารางนี้จะต้องมีค่าไม่เกิน $B(m-1,d)$ เนื่องจาก $B(m-1,d)$ เป็นจำนวน dichotomy ที่มากที่สุดบนตัวอย่างข้อมูล $m-1$ ตัวที่ไม่ shatter ตัวอย่างข้อมูล $d+1$ ตัวใด ๆ นั่นคือเราได้ว่า

คราวนี้ลองพิจารณาเฉพาะ dichotomy ใน $S_2^0$ และ $S_2^1$ สังเกตว่าเมื่อเราพิจารณา dichotomy กลุ่มนี้บน $x_1,\dots,x_{m-1}$ เท่านั้น เราจะได้ว่า dichotomy กลุ่มนี้จะต้องไม่ shatter ตัวอย่างข้อมูล $d$ ตัวใด ๆ เนื่องจากหากมีตัวอย่างข้อมูล $d$ ตัวที่ถูก shatter ด้วย dichotomy กลุ่มนี้ได้แล้ว เราจะได้ว่า dichotomy เดิมของเราที่มี label สำหรับ $x_m$ ทั้งสองแบบ จะสามารถ shatter ตัวอย่างข้อมูล $d+1$ ตัวได้อย่างน้อยชุดหนึ่ง ซึ่งผิดจากเงื่อนไขที่ VC-dimension เท่ากับ $d$ ดังนั้นเราจึงได้ว่าจำนวน dichotomy บนข้อมูล $m-1$ ตัวใน $S_2^0$ หรือใน $S_2^1$ นี้จะต้องมีค่าไม่เกินจำนวน dichotomy ที่มากที่สุดบนตัวอย่างข้อมูล $m-1$ ตัวเมื่อ shatter ข้อมูลได้มากที่สุด $d-1$ ตัว นั่นคือเราได้ว่า

ถึงตรงนี้เราสามารถสร้าง recurrent relation ของ $B(m,d)$ ได้ดังนี้

Sauer’s Lemma

จาก recurrence ด้านบน เราสามารถหารูปแบบปิดของขอบเขตดังกล่าวได้ตาม Sauer’s Lemma

ซึ่งสามารถพิสูจน์ได้ด้วย induction เมื่อ $m=1$ หรือ $d=0$ จะเห็นได้ไม่ยากว่าขอบเขตดังกล่าวเป็นจริง หากเราสมมติให้ขอบเขตดังกล่าวเป็นจริงสำหรับจำนวนตัวอย่างข้อมูลตั้งแต่ $1$ จนถึง $m-1$ สำหรับ VC-dimension $d$ ใด ๆ เราจะแสดงให้เห็นว่า $B(m,d)$ ก็สามารถจำกัดขอบเขตได้ดัง lemma นี้เช่นเดียวกัน โดยพิจารณา

จาก Sauer’s lemma เราสามารถจำกัดขอบเขตของ $B(m,d)$ ต่อได้โดยพิจารณาเมื่อ $m\leq d$ เราจะได้ว่า

และเมื่อ $m> d$ ซึ่งทำให้ $\frac{m}{d}>1$ จะได้ว่า

เนื่องจาก $B(m,d)$ นั้นเป็นขอบเขตบนของ growth function $\Pi_H(m)$ เราจึงสรุปได้ว่า สำหรับ hypothesis space $H$ ที่มี VC-dimension เท่ากับ $d$ เราจะได้ว่า

จะเห็นว่าอัตราการโตของ $\Pi_H(m)$ นั้นเป็น polynomial บน $m$ ซึ่งน่าจะช่วยให้ error bar ของเราลู่เข้าสู่ศูนย์ตามต้องการได้ อย่างไรก็ดี การนำ $\Pi_H(m)$ มาใช้วิเคราะห์การเรียนรู้ตามกรอบของ PAC นี้ไม่สามารถทำได้ในรูปแบบเดียวกับกรณีที่ $H$ มีขนาดจำกัด เราจำเป็นต้องทำการวิเคราะห์ที่ซับซ้อนมากขึ้น

Prev: VC-Dimension

Next: VC Generalization