Skip to content
กลับไปยังผลการค้นหา

ต้นไม้ตัดสินใจแบบกึ่งกำกับดูแล (Semi-supervised Decision Tree)

ผู้เสนอ
Various (Levin & Shapiro; Zhu & Goldberg lineage)
ปี
2000s
ประเภท
Semi-supervised classifier / regressor
กลุ่มวิธี
Machine learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

ต้นไม้ตัดสินใจแบบกึ่งกำกับดูแลเป็นการขยายผลการเหนี่ยวนำต้นไม้ตัดสินใจมาตรฐาน เช่น CART หรือ C4.5 เพื่อใช้ประโยชน์จากข้อมูลที่ไม่มีป้ายกำกับควบคู่ไปกับชุดข้อมูลฝึกสอนที่มีป้ายกำกับ โดยการกำหนดป้ายกำกับชั่วคราวให้กับข้อมูลที่ไม่มีป้ายกำกับและนำไปรวมในกระบวนการสร้างหรือแบ่งกิ่งของต้นไม้ อัลกอริทึมสามารถให้ความแม่นยำที่ดีกว่าต้นไม้แบบกำกับดูแลเต็มรูปแบบที่ฝึกสอนจากชุดข้อมูลย่อยที่มีป้ายกำกับเพียงอย่างเดียว ซึ่งมีคุณค่าอย่างยิ่งเมื่อการติดป้ายกำกับมีค่าใช้จ่ายสูงหรือใช้เวลานาน

แนวคิดเบื้องหลังวิธีการ

การติดป้ายกำกับทุกการสังเกตมีค่าใช้จ่ายสูง แต่ข้อมูลที่ไม่มีป้ายกำกับยังคงมีข้อมูลโครงสร้างที่มีประโยชน์เกี่ยวกับปริภูมิคุณลักษณะ ต้นไม้ตัดสินใจแบบกึ่งกำกับดูแลใช้ประโยชน์จากสิ่งนี้โดยการสร้างต้นไม้จากตัวอย่างที่มีป้ายกำกับจำนวนน้อยก่อน จากนั้นใช้ต้นไม้นั้นเพื่อติดป้ายกำกับข้อมูลที่ไม่มีป้ายกำกับชั่วคราว และทำการฝึกสอนใหม่บนชุดข้อมูลที่ขยายออก การทำซ้ำหลายครั้งจะปรับปรุงทั้งป้ายกำกับชั่วคราวและโครงสร้างต้นไม้ไปพร้อมกัน ดังนั้นแบบจำลองจึงเรียนรู้จากการกระจายตัวของข้อมูลทั้งหมด แม้ว่าป้ายกำกับจริงจะหายากก็ตาม

ประวัติศาสตร์

การเรียนรู้แบบกึ่งกำกับดูแล (Semi-supervised learning) เกิดขึ้นในช่วงปลายทศวรรษ 1990 เมื่อนักวิจัยพยายามใช้ประโยชน์จากข้อมูลที่ไม่มีป้ายกำกับที่มีอยู่มากมายในโดเมนต่างๆ เช่น การจำแนกประเภทเว็บและชีววิทยาเชิงคำนวณ รูปแบบการฝึกสอนตนเอง (self-training) ของต้นไม้ตัดสินใจ ซึ่งต้นไม้จะติดป้ายกำกับข้อมูลที่ไม่มีป้ายกำกับของตนเองซ้ำๆ เป็นหนึ่งในการใช้งานยุคแรกๆ การศึกษาอย่างเป็นทางการปรากฏในบทสำรวจโดย Zhu & Goldberg (2009) ซึ่งจัดประเภทการฝึกสอนตนเองแบบต้นไม้ให้อยู่ในกลุ่มการเรียนรู้แบบกึ่งกำกับดูแลที่กว้างขึ้น นับตั้งแต่นั้นมา แนวทางต่างๆ ได้ขยายไปสู่การตั้งค่าแบบกลุ่ม (ensemble) ทำให้เกิดต้นไม้สุ่มแบบกึ่งกำกับดูแล (semi-supervised random forests) และต้นไม้แบบไล่ระดับ (gradient-boosted trees)

ควรใช้เมื่อใด

ต้นไม้ตัดสินใจแบบกึ่งกำกับดูแลมีความเหมาะสมเมื่อข้อมูลที่มีป้ายกำกับมีน้อยและมีค่าใช้จ่ายสูงในการได้มา แต่มีข้อมูลที่ไม่มีป้ายกำกับจำนวนมาก ซึ่งเป็นเรื่องปกติในการอธิบายภาพทางการแพทย์ การจำแนกประเภทข้อความ และการตรวจสอบด้วยเซ็นเซอร์ วิธีนี้มีประโยชน์อย่างยิ่งเมื่อการกระจายตัวของคุณลักษณะโดยรวมถูกจับได้ดีโดยกลุ่มข้อมูลที่ไม่มีป้ายกำกับ และเมื่อต้องการแบบจำลองที่มนุษย์สามารถตีความได้ (ต้นไม้) ควรหลีกเลี่ยงวิธีนี้เมื่อตัวอย่างที่มีป้ายกำกับมีน้อยมากจนต้นไม้เริ่มต้นไม่น่าเชื่อถือ หรือเมื่อข้อมูลที่ไม่มีป้ายกำกับไม่ได้เป็นตัวแทนของการกระจายตัวของการทดสอบ หรือเมื่อกระบวนการติดป้ายกำกับเสมือนคาดว่าจะแพร่กระจายข้อผิดพลาดที่เป็นระบบ (confirmation bias) ในกรณีเหล่านั้น วิธีการแบบกำกับดูแลล้วนบนข้อมูลที่มีป้ายกำกับที่สะอาด หรือวิธีการกึ่งกำกับดูแลทางเลือก เช่น การแพร่กระจายป้ายกำกับ (label propagation) หรือ co-training อาจปลอดภัยกว่า

ข้อจำกัดและข้อควรพิจารณา

  • ข้อผิดพลาดของป้ายกำกับเสมือนจากต้นไม้เริ่มต้นที่ไม่น่าเชื่อถืออาจถูกขยายไปเรื่อยๆ ในแต่ละรอบการทำซ้ำ ทำให้ประสิทธิภาพลดลงเมื่อเทียบกับแบบจำลองกำกับดูแลเต็มรูปแบบ
  • วิธีนี้สมมติว่าข้อมูลที่ไม่มีป้ายกำกับมีการกระจายตัวพื้นฐานเหมือนกับข้อมูลที่มีป้ายกำกับ การเปลี่ยนแปลงการกระจายตัวจะทำให้สมมตินี้ไม่ถูกต้อง
  • ต้นทุนการคำนวณเพิ่มขึ้นในแต่ละรอบการทำซ้ำ เนื่องจากต้นไม้ถูกฝึกสอนใหม่บนชุดข้อมูลที่มีประสิทธิภาพที่ใหญ่ขึ้นเรื่อยๆ
  • การเลือกเกณฑ์ความเชื่อมั่นสำหรับการรวมป้ายกำกับเสมือนต้องมีการปรับแต่งและการตรวจสอบไขว้ (cross-validation) อย่างรอบคอบ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ใช้ประโยชน์จากข้อมูลที่ไม่มีป้ายกำกับเพื่อปรับปรุงความแม่นยำเมื่อตัวอย่างที่มีป้ายกำกับมีน้อย ช่วยลดต้นทุนการติดป้ายกำกับ
  • รักษาความสามารถในการตีความของต้นไม้ตัดสินใจ: แบบจำลองที่ได้จะเป็นชุดกฎ if-then ที่มนุษย์สามารถอ่านได้
  • จัดการประเภทคุณลักษณะผสมผสานได้อย่างเป็นธรรมชาติ เช่น ต่อเนื่อง หมวดหมู่ หรือทวิภาค โดยไม่ต้องมีการประมวลผลล่วงหน้าหรือการปรับมาตรฐาน
  • การฝึกสอนตนเองแบบทำซ้ำนั้นง่ายต่อการนำไปใช้กับตัวเรียนรู้ต้นไม้ที่มีอยู่
  • สามารถจับขอบเขตที่ไม่เป็นเชิงเส้นและการปฏิสัมพันธ์ของคุณลักษณะที่แบบจำลองกึ่งกำกับดูแลเชิงเส้นพลาดไป

การประยุกต์ใช้

  • การจำแนกประเภทภาพทางการแพทย์และบันทึกทางการแพทย์ ซึ่งการอธิบายโดยผู้เชี่ยวชาญมีค่าใช้จ่ายสูงและมีคลังข้อมูลที่ไม่มีป้ายกำกับจำนวนมาก
  • การจำแนกประเภทข้อความและเอกสาร โดยมีคลังข้อมูลที่มีป้ายกำกับขนาดเล็กและคอลเลกชันที่ไม่มีป้ายกำกับขนาดใหญ่
  • การวิเคราะห์ข้อมูลเซ็นเซอร์และ IoT ซึ่งมีเพียงส่วนเล็กน้อยของส่วนอนุกรมเวลาที่ถูกติดป้ายกำกับด้วยตนเอง
  • งานชีวสารสนเทศ เช่น การทำนายหน้าที่ของยีน โดยมีป้ายกำกับที่ได้รับการยืนยันจากการทดลองน้อย
  • การตรวจจับการฉ้อโกง เมื่อกรณีการฉ้อโกงที่มีป้ายกำกับหายากเมื่อเทียบกับปริมาณธุรกรรมที่ไม่มีป้ายกำกับ

วิธีการทำงาน

วิธีการทำงาน

1

ต้นไม้ตัดสินใจมาตรฐาน (เช่น CART หรือ C4.5) จะถูกปรับให้เหมาะสมโดยใช้เฉพาะส่วนที่มีป้ายกำกับของชุดข้อมูล แบบจำลองเริ่มต้นนี้จะให้การประมาณค่าขอบเขตการตัดสินใจเบื้องต้น และทำหน้าที่เป็นจุดเริ่มต้นสำหรับการทำซ้ำแบบกึ่งกำกับดูแลในภายหลัง

2

การสังเกตที่ไม่มีป้ายกำกับแต่ละรายการจะถูกส่งผ่านต้นไม้ปัจจุบัน และคลาสที่ทำนาย (สำหรับการจำแนกประเภท) หรือค่าที่ทำนาย (สำหรับการถดถอย) จะถูกกำหนดเป็นป้ายกำกับชั่วคราว สามารถใช้การประมาณค่าความเชื่อมั่นหรือความน่าจะเป็นจากโหนดใบเพื่อเลือกเฉพาะป้ายกำกับเสมือนที่มีความน่าเชื่อถือสูง โดยกรองการกำหนดค่าที่มีความเชื่อมั่นต่ำออก

3

ต้นไม้จะถูกฝึกสอนใหม่ตั้งแต่ต้น โดยใช้ทั้งตัวอย่างที่มีป้ายกำกับเดิมและข้อมูลที่ไม่มีป้ายกำกับที่เพิ่งติดป้ายกำกับเสมือน ป้ายกำกับเสมือนที่มีความเชื่อมั่นสูงจะส่งผลต่อการตัดสินใจแบ่งกิ่งควบคู่ไปกับป้ายกำกับจริง ซึ่งเป็นการขยายชุดข้อมูลฝึกสอนที่มีประสิทธิภาพ

4

เกณฑ์การแบ่งกิ่งที่ปรับปรุงแล้ว เช่น เอนโทรปีหรือ Gini ที่คำนวณจากทั้งข้อมูลที่มีป้ายกำกับและไม่มีป้ายกำกับ หรือวัตถุประสงค์แบบสองเกณฑ์ที่สร้างสมดุลระหว่างความบริสุทธิ์แบบกำกับดูแลกับความสอดคล้องของกลุ่มแบบไม่มีการกำกับดูแล จะนำทางการแบ่งกิ่งโหนดเพื่อเคารพการกระจายตัวของข้อมูลพื้นฐานที่เปิดเผยโดยจุดที่ไม่มีป้ายกำกับ

5

การทำซ้ำจะดำเนินต่อไปจนกว่าป้ายกำกับชั่วคราวจะคงที่ในรอบที่ต่อเนื่องกัน หรือถึงขีดจำกัดการทำซ้ำสูงสุด จากนั้นจะใช้กลยุทธ์การตัดแต่งกิ่งมาตรฐาน (การตัดแต่งกิ่งแบบต้นทุน-ความซับซ้อน, ขนาดโหนดใบขั้นต่ำ) กับต้นไม้สุดท้ายเพื่อควบคุมการเรียนรู้เกิน (overfitting) บนข้อมูลที่มีป้ายกำกับเสมือน

ข้อผิดพลาดที่พบบ่อย

  • การใช้ป้ายกำกับเสมือนทั้งหมดโดยไม่คำนึงถึงความเชื่อมั่น ซึ่งอนุญาตให้การกำหนดค่าคุณภาพต่ำครอบงำรอบการทำซ้ำในภายหลัง
  • การไม่ตรวจสอบว่าข้อมูลที่ไม่มีป้ายกำกับถูกดึงมาจากชุดการกระจายตัวเดียวกับชุดที่มีป้ายกำกับก่อนทำการฝึกสอน
  • การปฏิบัติต่อสถิติโหนดใบของต้นไม้สุดท้ายเสมือนว่าเป็นการกำกับดูแลล้วนๆ เมื่อรายงานเมตริกประสิทธิภาพ จำเป็นต้องมีการประเมินนอกชุด (out-of-bag) หรือชุดข้อมูลที่มีป้ายกำกับที่ถูกพักไว้
  • การข้ามขั้นตอนการตัดแต่งกิ่งหลังจากการเพิ่มป้ายกำกับเสมือน ทำให้เกิดการเรียนรู้เกิน (overfitting) อย่างรุนแรงต่อป้ายกำกับชั่วคราวที่มีสัญญาณรบกวน
  • การเปรียบเทียบโดยตรงกับต้นไม้แบบกำกับดูแลเต็มรูปแบบที่ฝึกสอนบนชุดข้อมูลย่อยที่มีป้ายกำกับเดียวกัน โดยไม่ได้คำนึงถึงข้อมูลที่ไม่มีป้ายกำกับเพิ่มเติมที่ใช้

คำถามที่พบบ่อย

ต้นไม้ตัดสินใจแบบกึ่งกำกับดูแลแตกต่างจากตัวจำแนกประเภทแบบฝึกสอนตนเองทั่วไปอย่างไร?

หลักการหลัก — การใช้การทำนายบนข้อมูลที่ไม่มีป้ายกำกับเพื่อเพิ่มการฝึกสอน — ยังคงเหมือนเดิม สิ่งที่ทำให้แนวทางเฉพาะสำหรับต้นไม้แตกต่างคือตัวเลือกในการปรับเปลี่ยนเกณฑ์การแบ่งกิ่งเองเพื่อรวมข้อมูลการกระจายตัวที่ไม่มีป้ายกำกับ แทนที่จะเพียงแค่ขยายชุดข้อมูลที่มีป้ายกำกับซ้ำๆ

ฉันต้องการตัวอย่างที่มีป้ายกำกับกี่ตัวอย่างในการเริ่มต้น?

ไม่มีจำนวนขั้นต่ำที่เป็นสากล แต่ต้นไม้แบบกำกับดูแลเริ่มต้นต้องน่าเชื่อถือเพียงพอที่จะสร้างป้ายกำกับเสมือนที่มีประโยชน์ ในทางปฏิบัติ มักแนะนำให้มีตัวอย่างที่มีป้ายกำกับอย่างน้อย 20-50 ตัวอย่างต่อคลาส หากมีน้อยกว่า ความเสี่ยงในการแพร่กระจายข้อผิดพลาดจะสูง และแนวทางทางเลือก เช่น การแพร่กระจายป้ายกำกับ อาจทำงานได้ดีกว่า

ฉันควรใช้ข้อมูลที่ไม่มีป้ายกำกับทั้งหมดหรือเลือกชุดย่อย?

การเลือกเฉพาะป้ายกำกับเสมือนที่มีความเชื่อมั่นสูง — เช่น ป้ายกำกับที่ความน่าจะเป็นของโหนดใบเกินเกณฑ์ที่กำหนด เช่น 0.85 — โดยทั่วไปจะให้ผลลัพธ์ที่ดีกว่าการใช้จุดที่ไม่มีป้ายกำกับทั้งหมด โดยเฉพาะอย่างยิ่งเมื่อต้นไม้เริ่มต้นไม่สมบูรณ์

สิ่งนี้มาแทนที่การตรวจสอบไขว้ (cross-validation) มาตรฐานหรือไม่?

ไม่ เนื่องจากป้ายกำกับเสมือนได้มาจากแบบจำลองเอง เมตริกภายในชุด (in-sample metrics) จะมองโลกในแง่ดีเกินไป การประเมินต้องใช้ชุดทดสอบที่มีป้ายกำกับที่ถูกพักไว้ หรือการตรวจสอบไขว้แบบ k-fold ที่ใช้กับส่วนที่มีป้ายกำกับอย่างเคร่งครัด

ฉันสามารถรวมวิธีนี้กับวิธีการแบบกลุ่ม (ensemble methods) ได้หรือไม่?

ได้ ต้นไม้สุ่มแบบกึ่งกำกับดูแล (Semi-supervised random forests) และแนวทาง co-forest ขยายแนวคิดนี้ไปยังแบบกลุ่ม ซึ่งสามารถลดความแปรปรวนของข้อผิดพลาดของป้ายกำกับเสมือน และโดยทั่วไปจะให้ผลลัพธ์ที่ดีกว่าต้นไม้กึ่งกำกับดูแลเดี่ยว

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Levin, E. & Shapiro, E. (2000). Learning Decision Trees from Semi-labeled Examples. Proceedings of the ICML Workshop on Attribute-Value and Relational Learning.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Zhu, X. & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers.

    ISBN: 978-1-598-29548-9
    คัดลอกแล้ว