การเรียนรู้กฎ (RIPPER)
- ผู้เสนอ
- William W. Cohen
- ปี
- 1995
- ประเภท
- Supervised rule learning algorithm
- กลุ่มวิธี
- Rule learning
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การเรียนรู้กฎ โดยเฉพาะอย่างยิ่งอัลกอริทึม RIPPER (Repeated Incremental Pruning to Produce Error Reduction) เป็นวิธีการเรียนรู้ของเครื่องแบบมีผู้สอน (supervised machine learning) ที่เรียนรู้ชุดกฎการจำแนกประเภทแบบ IF-THEN ที่กระชับจากข้อมูลฝึกอบรมที่มีป้ายกำกับ RIPPER ซึ่งแนะนำโดย William W. Cohen ในปี 1995 ใช้กลยุทธ์การแยกและพิชิต (separate-and-conquer) ร่วมกับการตัดแต่งตามหลักการความยาวคำอธิบายขั้นต่ำ (Minimum Description Length - MDL) เพื่อสร้างกฎที่มีทั้งความแม่นยำและสามารถตีความได้ ทำให้เป็นอัลกอริทึมที่เป็นหลักสำคัญในสาขาการเรียนรู้กฎแบบอุปนัย (inductive rule learning)
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพการเขียนรายการตรวจสอบการวินิจฉัยสำหรับแพทย์: กฎแต่ละข้อจะจับคู่ชุดอาการเฉพาะที่สามารถทำนายการวินิจฉัยได้อย่างน่าเชื่อถือ RIPPER จะสร้างรายการตรวจสอบนี้โดยอัตโนมัติจากข้อมูลผู้ป่วย โดยจะร่างกฎทีละข้อ ครอบคลุมกรณีที่เป็นบวกให้ได้มากที่สุด จากนั้นจึงตรวจสอบกฎแต่ละข้อกับชุดข้อมูลที่แยกไว้เพื่อลื่อนไขที่เฉพาะเจาะจงเกินไป ผลลัพธ์ที่ได้คือคู่มือกฎที่สั้นและอ่านได้โดยมนุษย์ ซึ่งสามารถนำไปใช้กับผู้ป่วยรายใหม่ได้โดยไม่จำเป็นต้องตรวจสอบประวัติการฝึกอบรมทั้งหมด
ประวัติศาสตร์
การเรียนรู้กฎมีรากฐานมาจากระบบการเรียนรู้ของเครื่องยุคแรก เช่น AQ (Michalski, 1969) และ CN2 (Clark and Niblett, 1989) เปเปอร์ RIPPER ของ Cohen ในปี 1995 ได้แก้ไขปัญหาประสิทธิภาพการคำนวณและแนวโน้มการเรียนรู้เกินของอัลกอริทึมก่อนหน้าเหล่านั้น โดยการแนะนำการตัดแต่งแบบเพิ่มหน่วย (incremental pruning) และการปรับปรุงตามหลัก MDL RIPPER ซึ่งนำเสนอในงาน ICML 1995 ได้กลายเป็นอัลกอริทึมที่เป็นมาตรฐานอย่างรวดเร็ว เนื่องจากมีความแม่นยำและความโปร่งใสที่แข่งขันได้ และยังคงเป็นข้อมูลอ้างอิงมาตรฐานในวรรณกรรมและตำราเรียนเกี่ยวกับการเรียนรู้กฎ
ควรใช้เมื่อใด
การเรียนรู้กฎด้วย RIPPER เหมาะสมเมื่อความสามารถในการตีความแบบจำลองเป็นข้อกำหนดหลัก เช่น การสนับสนุนการตัดสินใจทางคลินิก การตรวจจับการฉ้อโกง หรือการตั้งค่าการปฏิบัติตามกฎระเบียบ สามารถทำงานกับคุณลักษณะแบบผสมทั้งแบบนามบัญญัติ (nominal) และแบบตัวเลข (numeric) และปรับขนาดได้ดีกับข้อมูลหลายหมื่นอินสแตนซ์ RIPPER สันนิษฐานว่าป้ายกำกับฝึกอบรมมีความน่าเชื่อถือเพียงพอ และขอบเขตการตัดสินใจพื้นฐานสามารถประมาณได้ด้วยการเชื่อมโยงที่ขนานกับแกน (axis-aligned conjunctions) เหมาะน้อยกว่าสำหรับปริภูมิคุณลักษณะต่อเนื่องที่มีมิติสูง หรืองานที่ต้องการผลลัพธ์การสอบเทียบความน่าจะเป็น ในกรณีเหล่านั้น อาจเลือกใช้ต้นไม้ที่เพิ่มประสิทธิภาพด้วยการไล่ระดับสี (gradient boosted trees) หรือการถดถอยโลจิสติก (logistic regression) แทน
ข้อจำกัดและข้อควรพิจารณา
- คุณภาพของกฎจะเสื่อมลงอย่างมากในปริภูมิคุณลักษณะที่มีมิติสูงมากหรือเบาบาง
- รายการกฎที่มีลำดับอาจไวต่อลำดับคลาส คลาสส่วนน้อยที่เรียนรู้สุดท้ายอาจได้รับกฎที่อ่อนแอกว่า
- ไม่สร้างการประมาณค่าความน่าจะเป็นที่สอบเทียบได้ ทำให้จำกัดการใช้งานในงานที่คำนึงถึงต้นทุนหรืองานจัดอันดับ
- กฎแบบเชื่อมโยงไม่สามารถจับปฏิสัมพันธ์ที่ซับซ้อนซึ่งต้องการขอบเขตที่ไม่ขนานกับแกนได้หากไม่มีการสร้างคุณลักษณะ (feature engineering)
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- สร้างกฎ IF-THEN ที่มนุษย์อ่านได้ ซึ่งผู้เชี่ยวชาญในสาขาสามารถตรวจสอบและยืนยันได้
- การเรียนรู้แบบแยกและพิชิตที่มีประสิทธิภาพพร้อมการตัดแต่งที่แนะนำโดย MDL ช่วยลดการเรียนรู้เกิน
- จัดการกับแอตทริบิวต์ทั้งแบบนามบัญญัติและตัวเลขโดยไม่ต้องมีการประมวลผลล่วงหน้ามากนัก
- โดยทั่วไปมีเวลาฝึกอบรมที่รวดเร็วกว่าเมื่อเทียบกับวิธีการแบบกลุ่ม (ensemble methods) สำหรับชุดข้อมูลขนาดปานกลาง
การประยุกต์ใช้
- การสนับสนุนการตัดสินใจทางคลินิกและการสกัดกฎการวินิจฉัยทางการแพทย์
- การตรวจจับการฉ้อโกงและความผิดปกติในการตรวจสอบธุรกรรมทางการเงิน
- การจำแนกประเภทข้อความโดยใช้คุณลักษณะทางศัพท์และโครงสร้าง
- การตรวจจับการบุกรุกเครือข่ายด้วยกฎการแจ้งเตือนที่สามารถตีความได้
- การทำนายการเลิกใช้บริการของลูกค้าด้วยกฎธุรกิจที่นำไปปฏิบัติได้
วิธีการทำงาน
วิธีการทำงาน
RIPPER ประมวลผลทีละคลาส โดยถือว่าอินสแตนซ์ที่เหลือทั้งหมดเป็นเซตเชิงลบ มันจะสร้างกฎแบบเชื่อมโยง (conjunctive rule) อย่างละโมบโดยการเพิ่มเงื่อนไขที่เพิ่มอัตราส่วนของกรณีบวกต่ออินสแตนซ์ทั้งหมดที่ครอบคลุมซ้ำๆ เมื่อกฎถูกสร้างขึ้นแล้ว กฎนั้นจะถูกยึดถือ และอินสแตนซ์ทั้งหมดที่กฎนั้นครอบคลุมจะถูกลบออกก่อนที่จะเรียนรู้กฎถัดไป ตามกระบวนทัศน์การแยกและพิชิตแบบคลาสสิกที่อธิบายโดย Cohen (1995)
สูตร
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}กฎที่คาดการณ์แต่ละข้อจะถูกตัดแต่งบนพาร์ติชันการตรวจสอบ (validation partition) ที่แยกไว้ โดยใช้เมตริก (p - n) / (p + n) โดยที่ p และ n คือจำนวนอินสแตนซ์ที่ครอบคลุมอย่างถูกต้องและไม่ถูกต้องตามลำดับ เงื่อนไขจะถูกลบออกจากส่วนท้ายของกฎทีละน้อย ตราบเท่าที่การตัดแต่งช่วยเพิ่มค่านี้ ซึ่งเป็นการป้องกันการเรียนรู้เกิน (overfitting) ที่เกิดจากการเชื่อมโยงที่เฉพาะเจาะจงเกินไปซึ่งบังเอิญเข้ากับชุดฝึกอบรม
สูตร
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}หลังจากกฎต่อคลาสทั้งหมดถูกเรียนรู้แล้ว RIPPER จะดำเนินการปรับปรุงเพิ่มเติม (optimization pass) ที่เป็นทางเลือก โดยใช้หลักการ Minimum Description Length สำหรับกฎแต่ละข้อในชุดสุดท้าย อัลกอริทึมจะพิจารณาแทนที่หรือแก้ไขกฎนั้น และยอมรับการเปลี่ยนแปลงก็ต่อเมื่อช่วยลดความยาวคำอธิบายรวมของชุดกฎและข้อมูลที่จำแนกผิดพลาดที่เหลืออยู่ ซึ่งเป็นการสร้างสมดุลระหว่างความแม่นยำกับความซับซ้อนของแบบจำลอง
สูตร
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})ในเวลาทำนาย กฎจะถูกนำไปใช้ตามลำดับที่เรียนรู้ อินสแตนซ์ที่ไม่เคยเห็นมาก่อนจะได้รับป้ายกำกับคลาสของกฎแรกที่เงื่อนไขทั้งหมดของกฎนั้นถูกตอบสนองโดยค่าคุณลักษณะของอินสแตนซ์นั้น หากไม่มีกฎใดทำงาน อินสแตนซ์นั้นจะตกอยู่ภายใต้คลาสเริ่มต้น (default class) ซึ่งโดยทั่วไปคือคลาสส่วนใหญ่จากข้อมูลฝึกอบรม เพื่อให้มั่นใจว่าครอบคลุมปริภูมิอินพุตทั้งหมด
สูตร
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}ข้อผิดพลาดที่พบบ่อย
- การใช้ RIPPER กับชุดข้อมูลขนาดเล็กที่ไม่มีข้อมูลการตัดแต่งที่เพียงพอ อาจส่งผลให้กฎถูกตัดแต่งมากเกินไปและมีอัตราการครอบคลุมต่ำ
- การละเลยความไม่สมดุลของคลาสทำให้คลาสเริ่มต้นดูดซับคลาสส่วนน้อย ทำให้การเรียกคืน (recall) ของคลาสส่วนน้อยแย่ลง
- การปฏิบัติต่อลำดับกฎที่เรียนรู้ว่าเป็นสาเหตุมากกว่าการทำนาย อาจนำไปสู่การตีความผิดในการวิเคราะห์เชิงสำรวจ
- การข้ามขั้นตอนการปรับปรุง MDL (มีให้ในบางการใช้งาน) อาจทำให้มีกฎที่ซ้ำซ้อนหรือขัดแย้งกันในชุดสุดท้าย
คำถามที่พบบ่อย
RIPPER แตกต่างจากต้นไม้ตัดสินใจ (decision tree) อย่างไร?
ทั้งสองเรียนรู้ขอบเขตที่ขนานกับแกน แต่ต้นไม้ตัดสินใจจะแบ่งปริภูมิคุณลักษณะทั้งหมดแบบเวียนซ้ำ (recursively) สร้างโครงสร้างแบบลำดับชั้น ในทางกลับกัน RIPPER เรียนรู้รายการกฎที่มีลำดับโดยใช้การแยกและพิชิต ซึ่งสามารถให้การแสดงผลที่กระชับกว่าเมื่อมีเพียงรูปแบบเฉพาะคลาสเพียงไม่กี่รูปแบบที่สำคัญ กฎยังอ่านได้ง่ายกว่าสำหรับผู้เชี่ยวชาญในสาขาเมื่อพิจารณาแยกกันมากกว่าเส้นทางในต้นไม้
RIPPER สามารถจัดการกับปัญหาหลายคลาส (multi-class) ได้หรือไม่?
ได้ RIPPER ขยายไปยังการตั้งค่าหลายคลาสโดยการเรียนรู้กฎสำหรับแต่ละคลาสตามลำดับ จากคลาสที่หายากที่สุดไปยังคลาสที่พบบ่อยที่สุด อินสแตนซ์ที่ครอบคลุมโดยกฎสำหรับคลาสก่อนหน้าจะถูกลบออกก่อนที่จะเรียนรู้กฎสำหรับคลาสถัดไป กฎเริ่มต้นจะกำหนดคลาสส่วนใหญ่ให้กับอินสแตนซ์ใดๆ ที่ไม่ครอบคลุมโดยกฎที่ชัดเจน
บทบาทของหลักการ Minimum Description Length (MDL) ใน RIPPER คืออะไร?
MDL ให้เกณฑ์ที่เป็นทางการเพื่อสร้างสมดุลระหว่างความซับซ้อนของกฎกับความเหมาะสมของข้อมูล ในขั้นตอนการปรับปรุง RIPPER จะให้ความสำคัญกับชุดกฎที่มีความยาวคำอธิบายรวม ซึ่งเข้ารหัสทั้งกฎและอินสแตนซ์ที่จำแนกผิดพลาด ว่าสั้นกว่า สิ่งนี้จะป้องกันไม่ให้อัลกอริทึมเก็บกฎที่เฉพาะเจาะจงเกินไปซึ่งจดจำสัญญาณรบกวน (noise) แทนที่จะจับรูปแบบที่แท้จริงในข้อมูล
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว