Representation และประสิทธิภาพในการเรียนรู้

ในหัวข้อนี้ เราจะแสดงให้เห็นว่า ถ้าเราเปลี่ยนรูปแบบของ representation ของ 3-term DNF เสียใหม่ จะทำให้คลาสของ 3-term DNF สามารถทำการเรียนรู้อย่างมีประสิทธิภาพได้

เราจะใช้ความจริงที่ว่า สำหรับ 3-term DNF ใด ๆ เราสามารถเขียนให้อยู่ในรูป conjunctive normal form (CNF)

ได้ โดยที่ $d_i$ ใด ๆ เป็น disjunction ของ literal ไม่เกินสามตัว เราเรียก representation ลักษณะนี้ว่า 3-Conjunctive Normal Form หรือ 3-CNF สำหรับ 3-term DNF $T_1\lor T_2\lor T_3$ ใด ๆ เราจะสามารถจัดให้อยู่ในรูปของ 3-CNF ได้ดังนี้

ตัวอย่างเช่น 3-term DNF

จะสามารถเขียนในรูป 3-CNF ได้เป็น

ซึ่งลดรูปได้เป็น

หากเราพิจารณาปัญหาการเรียนรู้ 3-CNF จะเห็นว่าเราสามารถลดรูปให้เป็นปัญหาการเรียนรู้ Boolean Conjunction ซึ่งเราสามารถเรียนรู้อย่างมีประสิทธิภาพได้ โดยในการแปลงจากปัญหาการเรียนรู้ 3-CNF ไปเป็นปัญหาการเรียนรู้ Boolean Conjunction นั้น สำหรับ literal สามตัว $u,v,w$ ใด ๆ บนตัวแปรตั้งต้น $x_1,\dots,x_n$ ในปัญหา 3-CNF เราจะสร้างตัวแปร $y_{u,v,w}$ ให้เป็นตัวแปร boolean ในปัญหา Boolean Conjunction โดยให้มีค่าเท่ากับ $u\lor v\lor w$ สังเกตว่าถ้าในปัญหาตั้งต้นมีตัวแปรอยู่ $n$ ตัว ตัวแปรในปัญหา Boolean Conjunction จะมีจำนวนเป็น $(2n)^3$

จากนั้น สำหรับตัวอย่างข้อมูล $a\in\{0,1\}^n$ ที่เป็นการกำหนดค่าบนตัวแปรตั้งต้น $x_1,\dots,x_n$ เราจะสามารถสร้างเป็นการกำหนดค่า $a’$ บนตัวแปรชุดใหม่ $\{y_{u,v,w}\}$ ได้ในเวลา $O(n^3)$ นอกจากนี้ สังเกตว่าสำหรับ 3-CNF $c$ ใด ๆ บนตัวแปรตั้งต้น $x_1,\dots,x_n$ เราจะต้องมี conjunction $c’$ บนตัวแปรชุดใหม่ที่มีค่าเท่ากับ $c$ เสมอ ดังนั้นจะเห็นว่าเราสามารถแปลงปัญหาให้เป็นการเรียนรู้ conjunction $c’$ บนตัวแปร $\{y_{u,v,w}\}$ ได้โดยแปลงตัวอย่างข้อมูลบนปัญหา 3-CNF ให้กลายเป็นตัวอย่างข้อมูลบนปัญหา Boolean Conjunction ด้วยการแปลงการกำหนดค่าบน $x_1,\dots, x_n$ เป็นการกำหนดค่าบน $y_{u,v,w}$ และให้ตัวอย่างข้อมูลหลังการแปลงแต่ละตัวมี label เหมือนในปัญหาตั้งต้น เมื่อเราได้ hypothesis $h’$ ในปัญหา Boolean Conjunction บน $y_{u,v,w}$ มาแล้ว เราก็สามารถแปลงกลับเป็น hypothesis $h$ ในปัญหา 3-CNF ได้อย่างตรงไปตรงมา ดังนั้น เราจึงสรุปได้ว่าปัญหา 3-CNF สามารถเรียนรู้ได้อย่างมีประสิทธิภาพ

เนื่องจากเราได้แสดงให้เห็นมาแล้วว่า 3-term DNF ใด ๆ สามารถจัดรูปเป็น 3-CNF ได้เสมอ ดังนั้น เราจะสามารถเรียนรู้ปัญหา 3-term DNF ได้หากเรายอมให้ hypothesis ของเรานั้นอยู่ในรูปของ 3-CNF (ซึ่งก็สามารถนำไปใช้ในการทำนาย label ของข้อมูลอื่น ๆ ได้เช่นกัน) แต่หากเราต้องการจะได้ hypothesis ที่อยู่ในรูปของ 3-term DNF เช่นเดิม ปัญหาการเรียนรู้ของเราจะอยู่ในกลุ่มปัญหายากทันที หากเราพิจารณาปัญหาการเรียนรู้ $k$-term DNF และ $k$-CNF ก็จะได้ความสัมพันธ์ในลักษณะนี้เช่นเดียวกัน ตัวอย่างนี้แสดงให้เห็นหลักการหนึ่งซึ่งมีความสำคัญมากในทฤษฎีการเรียนรู้ นั่นคือ representation ของ hypothesis มีบทบาทสำคัญที่จะทำให้ปัญหาที่เราสนใจสามารถเรียนรู้ได้อย่างมีประสิทธิภาพ

Prev: ปัญหาที่เรียนรู้ยาก

Next: Consistent Hypothesis