ปัญหาการเรียนรู้ Boolean Conjunction
ในการศึกษาด้าน machine learning ทั่วไป เรามักจะพิจารณาตัวอย่างข้อมูลหนึ่งในรูปเซตของคู่ attribute-value ซึ่งในหลายสถานการณ์ attribute ที่เราสนใจนั้นสามารถจัดให้อยู่ในรูปแบบของตัวแปร boolean ที่มีค่าเป็นจริงหรือเท็จ สมมติว่าเราสนใจพิจารณา attribute ลักษณะดังกล่าวจำนวน $n$ ตัว เรากำหนดให้ $x_1,\dots,x_n$ เป็นตัวแปรที่แทนแต่ละ attribute ซึ่งก็จะมีความหมายแตกต่างกันไปตามปัญหาการเรียนรู้ ตัวอย่างเช่น ถ้า $n=3$ $x_1$ อาจทำหน้าที่บันทึกว่าตัวอย่างข้อมูลหนึ่งเป็นสิ่งมีชีวิตที่บินได้หรือไม่ $x_2$ อาจทำหน้าที่บันทึกว่าเป็นสัตว์เลี้ยงลูกด้วยนมหรือไม่ และ $x_3$ อาจบันทึกว่าสูญพันธ์แล้วหรือไม่
ในการอธิบาย concept บนตัวแปร boolean เรามักจะใช้ boolean formula ซึ่งแสดงการดำเนินการทาง logic บนตัวแปร boolean ที่เราสนใจ และจำแนกประเภทของตัวอย่างข้อมูลเป็นสองกลุ่มได้ ได้แก่กลุ่มของตัวอย่างข้อมูลที่ทำให้ boolean formula นั้นมีค่าเป็นจริง (positive example) และกลุ่มของตัวอย่างข้อมูลที่ทำให้ boolean formula เป็นเท็จ (negative example)
สังเกตว่า boolean formula $f$ ใด ๆ บนตัวแปร $x_1,\dots, x_n$ นั้นสามารถเรียนรู้ได้แน่นอนถ้าเรามีตัวอย่างข้อมูลที่มากพอ เนื่องจาก $f$ เป็นฟังก์ชันที่นิยามบนโดเมน $X$ ที่มีขนาดจำกัด กล่าวคือ ซึ่งขนาดของ $X$ จะเป็น $2^n$ ดังนั้นหากเราสามารถหาวิธีเข้าถึงตัวอย่างข้อมูลได้ครบทุกตัวใน $X$ เราก็จะได้ตารางค่าความจริงของ $f$ อย่างสมบูรณ์ อย่างไรก็ดี ในสถานการณ์จริงนั้นเรามักจะสนใจ attribute ของข้อมูลเป็นจำนวนมาก ซึ่งทำให้ขนาดของ $X$ ใหญ่มากตามไปด้วย นอกจากนี้ตัวอย่างข้อมูลที่เราเข้าถึงได้มักจะเป็นเซตของตัวอย่างข้อมูลที่ได้จากการสุ่มแบบ i.i.d. ซึ่งเราไม่สามารถคาดหวังว่าจะได้เห็นตัวอย่างข้อมูลที่ถูกต้องครบทั้งหมดใน $X$ ได้เลย
จากที่กล่าวมา เราจึงสนใจ class ของ boolean formula ที่สามารถ เรียนรู้ได้อย่างมีประสิทธิภาพ มากกว่าแค่ เรียนรู้ได้ เท่านั้น ในหัวข้อนี้เราจะสนใจปัญหาการเรียนรู้ class ของ boolean formula ที่มีความซับซ้อนไม่มากและสามารถเรียนรู้ได้อย่างมีประสิทธิภาพตามกรอบการเรียนรู้แบบ PAC โดย boolean formula ที่เราสนใจนี้ เรียกว่า boolean conjunction ซึ่งหมายถึงการนำ literal ของตัวแปร $x_i$ บางตัวมาเชื่อมกันด้วยตัวดำเนินการ logical and ($\land$) เมื่อ literal ของ $x_i$ อาจเป็น $x_i$ หรือ $\bar{x}_i$
ในปัญหาการเรียนรู้ boolean conjunction นี้ เรากำหนดให้ concept class $C$ เป็นเซตของ conjunction ทั้งหมดที่สร้างได้จาก literal ของตัวแปร boolean $x_1,\dots,x_n$ และให้ input space เป็นเซตของการกำหนดค่าให้กับตัวแปร $x_i$ ในทุกรูปแบบ
ให้ $c$ เป็น conjunction หนึ่งใน $C$ เราจะกำหนดให้ $c(a)=1$ สำหรับ $a\in X$ ถ้าการกำหนดค่าให้ตัวแปร $x_1,\dots,x_n$ ตามแบบ $a$ นั้นทำให้ conjunction $c$ เป็นจริง และให้ $c(a)=0$ ถ้าการกำหนดค่าดังกล่าวทำให้ conjunction $c$ เป็นเท็จ ตัวอย่างเช่น ถ้า $n=4$ และ concept เป้าหมายเป็น conjunction
หรือเราอาจเขียนอีกแบบได้เป็น
เราจะได้ว่า $(1,0,0,1)$ เป็นตัวอย่างข้อมูลที่มี label เป็น 1 และ $(1,1,1,0)$ มี label เป็น 0
เราอาจนิยามให้ขนาดของ conjunction $c$ ใด ๆ เป็นจำนวน literal ใน $c$ ซึ่งจะทำให้เราได้ว่า $size(c)\leq 2n$ และเนื่องจากขนาดของตัวอย่างข้อมูล $a\in X$ แต่ละตัวเป็น $n$ ดังนั้น เราจะสามารถเรียนรู้ boolean conjunction จากตัวอย่างข้อมูลได้อย่างมีประสิทธิภาพหากมีอัลกอริทึมการเรียนรู้ตามกรอบ PAC ที่ใช้จำนวนตัวอย่างข้อมูลเป็น polynomial บน $n$, $1/\epsilon$ และ $1/\delta$
อัลกอริทึมการเรียนรู้ conjunction
จากตัวอย่าง conjunction ด้านบน สังเกตว่าตัวอย่างข้อมูลที่มี label เป็น 0 เช่น $(1,1,1,0)$ นั้นบอกเราได้เพียงว่า จะต้องมี literal ที่ขัดแย้งกับการกำหนดค่าอย่างน้อยหนึ่งตัวใน conjunction เป้าหมาย นั่นคือ ใน $c$ จะต้องมี $\bar{x}_1$ หรือ $\bar{x}_2$ หรือ $\bar{x}_3$ หรือ $x_4$ อย่างน้อยหนึ่งตัว แต่เรายังไม่สามารถระบุได้ว่าต้องมีตัวใดบ้าง ในขณะที่ตัวอย่างข้อมูลที่มี label เป็น 1 เช่น $(1,0,0,1)$ นั้นสามารถบอกเราได้ว่าใน $c$ จะไม่สามารถมี literal $\bar{x}_1,x_2,x_3,\bar{x}_4$ อยู่ได้แม้สักตัวเดียว จากตรงนี้นำเรามาสู่อัลกอริทึมหนึ่งในการเรียนรู้ conjunction ที่มีการทำงานดังนี้
อัลกอริทึมเริ่มต้นจากการกำหนด hypothesis conjunction ให้ประกอบด้วย literal ทั้งหมด ได้เป็น
ซึ่งจะเห็นว่า hypothesis เริ่มต้นนี้จะไม่สอดคล้องกับการกำหนดค่าให้กับตัวแปรใด ๆ เลย ถัดมา สำหรับเซตของตัวอย่างข้อมูล $S$ ที่มีสมาชิก $m$ ตัว เมื่ออัลกอริทึมรับตัวอย่างข้อมูล $(a,c(a))\in S$ มาตัวหนึ่ง หากตัวอย่างข้อมูลดังกล่าวเป็น positive example หรือ $c(a)=1$ อัลกอริทึมจะทำการปรับปรุง hypothesis $h$ โดยการลบ literal ที่ขัดแย้งกับ $a$ ออกไป กล่าวคือ สำหรับ $i=1,\dots,n$ ถ้า $a_i=0$ เราจะลบ $x_i$ ออกจาก $h$ แต่ถ้า $a_i=1$ เราจะลบ $\bar{x}_i$ ออกจาก $h$ ในขณะที่ หากตัวอย่างข้อมูลที่พิจารณาเป็น negative example ($c(a)=0$) อัลกอริทึมจะไม่มีการปรับปรุง hypothesis
สมมติว่า $n=4$ และ $c$ เป็น conjunction $x_1\land\bar{x}_4$ โดยเซตของตัวอย่างข้อมูล $S$ มีสมาชิกดังตาราง
| $a$ | $c(a)$ |
|---|---|
| $(0,1,1,1)$ | 0 |
| $(1,1,0,0)$ | 0 |
| $(1,0,1,0)$ | 1 |
| $(0,0,1,0)$ | 0 |
| $(1,1,1,0)$ | 1 |
ในขั้นตอนเริ่มต้น อัลกอริทึมจะกำหนด hypothesis
หรือ
จากนั้น สมมติให้อัลกอริทึมทำการพิจารณาตัวอย่างข้อมูลใน $S$ ทีละตัวตามลำดับในตารางด้านบน เราสามารถแสดงลำดับการปรับปรุง hypothesis ของอัลกอริทึมได้ดังตารางต่อไปนี้
| $a$ | $c(a)$ | literal ที่ขัดแย้ง | $h$ หลังการปรับปรุง |
|---|---|---|---|
| $(0,1,1,1)$ | 0 | - | $x_1\bar{x}_1 x_2\bar{x}_2 x_3\bar{x}_3 x_4\bar{x}_4$ |
| $(1,1,0,0)$ | 0 | - | $x_1\bar{x}_1 x_2\bar{x}_2 x_3\bar{x}_3 x_4\bar{x}_4$ |
| $(1,0,1,0)$ | 1 | $\bar{x}_1,x_2,\bar{x}_3,x_4$ | $x_1 \bar{x}_2 x_3\bar{x}_4$ |
| $(0,0,1,0)$ | 0 | - | $x_1 \bar{x}_2 x_3\bar{x}_4$ |
| $(1,1,1,0)$ | 1 | $\bar{x}_2$ | $x_1 x_3 \bar{x}_4$ |
ดังนั้น อัลกอริทึมจะตอบ hypothesis $h=x_1 x_3 \bar{x}_4$ เป็นคำตอบ
การวิเคราะห์อัลกอริทึม
สังเกตว่าตลอดเวลาการทำงานของอัลกอริทึมนั้น เซตของ literal ที่ปรากฏใน $h$ จะต้องครอบคลุม literal ทั้งหมดใน $c$ เนื่องจากอัลกอริทึมเราเริ่มต้นให้ $h$ ประกอบด้วย literal ทั้งหมดที่มี และเราจะลบ literal ตัวใดตัวหนึ่งออกเมื่อมันขัดแย้งกับ positive example เท่านั้น แสดงว่า literal เหล่านั้นย่อมไม่สามารถมีอยู่ใน $c$ ได้แน่นอน เราจึงมั่นใจได้ว่า hypothesis ที่เป็นผลลัพธ์จากอัลกอริทึมนี้เป็น conjunction ที่มี literal ใน $c$ อยู่ครบถ้วน (แต่อาจมี literal อื่น ๆ อยู่ด้วย) คุณสมบัตินี้ทำให้เราได้ว่า $h$ จะไม่มีทางทำนาย negative example ผิดแน่นอน (เนื่องจาก $h$ มีความเฉพาะเจาะจงมากกว่า $c$ หรือไม่ก็เท่ากัน)
คราวนี้สมมติให้ $h\neq c$ พิจารณา literal $z$ ที่ปรากฏใน $h$ แต่ไม่อยู่ใน $c$ สังเกตว่า $z$ จะทำให้ $h$ มีการทำนายที่ผิดพลาดเมื่อเจอตัวอย่างข้อมูล $a\in X$ ที่เป็น positive example ที่ขัดแย้งกับ $z$ ซึ่งตัวอย่างข้อมูลดังกล่าวจะนำไปสู่การลบ $z$ ออกจาก $h$ หากมีอยู่ใน $S$ สมมติให้ $p(z)$ เป็นความน่าจะเป็นที่เราสุ่มตัวอย่างข้อมูลดังกล่าวได้จากการกระจายตัว $D$ กล่าวคือ
เนื่องจาก error ของ $h$ คือ
สังเกตว่า หาก literal $z \in h$ ทุกตัวมี $p(z)\leq \epsilon/2n$ เราจะได้
นั่นคือเราจะได้ hypothesis $h$ ที่มี error ไม่เกิน $\epsilon$ ตามต้องการ
คราวนี้สมมติว่ามี literal $z$ ที่ $p(z)>\epsilon/2n$ เราจะมาวิเคราะห์ว่ามีความน่าจะเป็นมากน้อยแค่ไหนที่ $z$ จะยังเหลืออยู่ใน $h$
เนื่องจากเรามีความน่าจะเป็นที่จะสุ่มได้ positive example ที่ขัดแย้งกับ $z$ มากกว่า $\epsilon/2n$ หาก $z$ ยังเหลืออยู่ใน $h$ ได้ แสดงว่าตัวอย่างข้อมูลใน $S$ ทั้ง $m$ ตัวไม่มีตัวอย่างข้อมูลดังกล่าวอยู่เลยแม้แต่ตัวเดียว สังเกตว่าความน่าจะเป็นที่เราจะสุ่มข้อมูลใน $S$ แล้วไม่โดนตัวอย่างข้อมูลดังกล่าวนั้นเลยจะมีค่าไม่เกิน
เนื่องจากจำนวน literal ดังกล่าวนี้ไม่มีทางเกิน $2n$ ดังนั้นความน่าจะเป็นที่จะมี literal $z$ อย่างน้อยตัวหนึ่งที่ $p(z)>\epsilon/2n$ และ $z$ ยังปรากฏอยู่ใน $h$ หลังการทำงานของอัลกอริทึมจะมีค่าไม่เกิน
หากเราต้องการให้ความน่าจะเป็นดังกล่าวมีค่าไม่เกิน $\delta$ เราทำได้โดยกำหนดให้
ซึ่งจะได้ว่า
นั่นคือ เราจะสามารถหา conjunction ที่มี error ไม่เกิน $\epsilon$ โดยความน่าจะเป็นไม่น้อยกว่า $1-\delta$ ได้เมื่อมีตัวอย่างข้อมูลเป็นจำนวนอย่างน้อย $\frac{2n}{\epsilon}\ln\frac{2n}{\delta}$ ซึ่งจะเห็นว่า sample complexity นี้เป็น polynomial บน $1/\epsilon, 1/\delta, n $ และ $size(c)$ ดังนั้นเราจึงสรุปได้ว่าปัญหาการเรียนรู้ boolean conjunction นี้สามารถเรียนรู้ได้อย่างมีประสิทธิภาพ
ในมุมของ generalization error เราก็สามารถสรุปได้ว่า สำหรับจำนวนตัวอย่างข้อมูล $m$ เราจะมีความน่าจะเป็นไม่น้อยกว่า $1-\delta$ ที่จะได้ hypothesis $h$ ที่
Prev: ปัญหาการเรียนรู้รูปสี่เหลี่ยมขนานแกน
Next: ปัญหาที่เรียนรู้ยาก