การเรียนรู้เชิงรุกแบบเพื่อนบ้านใกล้ที่สุด K ตัว
- ผู้เสนอ
- Settles, B. (active learning framework); Fix & Hodges (KNN base)
- ปี
- 1951–2010
- ประเภท
- Active learning with KNN base learner
- กลุ่มวิธี
- Machine learning
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การเรียนรู้เชิงรุกด้วยเพื่อนบ้านใกล้ที่สุด K ตัว (K-nearest neighbors) เป็นการรวมการทำนายแบบอิงตามตัวอย่างของ KNN เข้ากับกลยุทธ์การสอบถามแบบวนซ้ำที่เลือกตัวอย่างที่ไม่มีป้ายกำกับที่ให้ข้อมูลมากที่สุดสำหรับการทำคำอธิบายประกอบ แบบจำลองจะร้องขอป้ายกำกับเฉพาะสำหรับตัวอย่างที่คะแนนโหวตของเพื่อนบ้านมีความใกล้เคียงกันมากที่สุด ซึ่งทำให้ได้ความแม่นยำที่แข่งขันได้โดยใช้ตัวอย่างที่มีป้ายกำกับน้อยกว่า KNN แบบมีการกำกับดูแลเต็มรูปแบบบนข้อมูลตาราง
แนวคิดเบื้องหลังวิธีการ
KNN จัดประเภทจุดโดยพิจารณาจากเพื่อนบ้านที่มีป้ายกำกับที่ใกล้ที่สุด k ตัว และใช้การโหวตแบบเสียงข้างมาก เมื่อเพื่อนบ้านเหล่านั้นมีการแบ่งแยกเกือบเท่ากันระหว่างคลาส แบบจำลองจะมีความไม่แน่นอนอย่างแท้จริง — และความไม่แน่นอนนั้นชี้ให้เห็นว่าตัวอย่างที่ไม่มีป้ายกำกับใดที่คุ้มค่าที่สุดที่จะติดป้ายกำกับ การเรียนรู้เชิงรุกใช้ประโยชน์จากสัญญาณนี้: ในแต่ละรอบ อัลกอริทึมจะค้นหาจุดที่ไม่มีป้ายกำกับซึ่งมีเพื่อนบ้านที่แบ่งแยกเท่ากันมากที่สุด ขอให้ผู้เชี่ยวชาญติดป้ายกำกับ เพิ่มลงในกลุ่มที่มีป้ายกำกับ และทำซ้ำ ผลลัพธ์คือความพยายามในการติดป้ายกำกับจะกระจุกตัวอยู่ใกล้ขอบเขตการตัดสินใจ ซึ่งป้ายกำกับใหม่จะให้ข้อมูลมากที่สุด
ประวัติศาสตร์
ตัวจำแนกประเภทเพื่อนบ้านใกล้ที่สุด K ตัว มีต้นกำเนิดมาจาก Fix and Hodges (1951) และได้รับการจัดรูปแบบโดย Cover and Hart (1967) การเรียนรู้เชิงรุกในฐานะกรอบการทำงานที่เป็นหลักการได้รับการสำรวจอย่างเป็นระบบโดย Burr Settles (2010) ซึ่งได้บันทึกการสุ่มตัวอย่างความไม่แน่นอนแบบอิงกลุ่ม (pool-based uncertainty sampling), การสอบถามโดยคณะกรรมการ (query-by-committee) และกลยุทธ์ถ่วงน้ำหนักความหนาแน่น (density-weighted strategies) KNN ได้รับการนำเสนอในฐานะผู้เรียนรู้พื้นฐานในการวัดประสิทธิภาพการเรียนรู้เชิงรุกแบบอิงกลุ่มมาตั้งแต่ผลงานพื้นฐานของ Cohn, Atlas, and Ladner (1994) เป็นอย่างน้อย โดยได้รับการยกย่องในด้านสัญญาณความไม่แน่นอนที่โปร่งใสและไม่มีค่าใช้จ่ายในการฝึกอบรมซ้ำต่อรอบ
ควรใช้เมื่อใด
ใช้การเรียนรู้เชิงรุกกับ KNN เมื่อข้อมูลที่มีป้ายกำกับหายากหรือมีค่าใช้จ่ายสูงในการได้มา ตัวอย่างที่ไม่มีป้ายกำกับมีจำนวนมาก พื้นที่ฟีเจอร์มีมิติปานกลาง และคาดว่าขอบเขตการตัดสินใจจะราบเรียบในระดับท้องถิ่น มีประโยชน์อย่างยิ่งในโครงการการจัดประเภทในระยะเริ่มต้นที่ต้องมีการจัดสรรการติดป้ายกำกับ หลีกเลี่ยงเมื่อชุดข้อมูลมีมิติสูงมาก (เมตริกระยะทางของ KNN ลดลงในมิติสูง ซึ่งเป็นคำสาปของมิติ), เมื่อกลุ่มที่มีป้ายกำกับมีขนาดใหญ่แล้ว (KNN แบบพาสซีฟก็เพียงพอ), เมื่อต้องการการทำนายที่มีความหน่วงต่ำในขนาดใหญ่ (การทำนายของ KNN เป็น O(n) ในชุดที่มีป้ายกำกับ), หรือเมื่องบประมาณป้ายกำกับมีขนาดเล็กมากจนการประมาณค่าเพื่อนบ้านไม่น่าเชื่อถือ
ข้อจำกัดและข้อควรพิจารณา
- ต้นทุนการทำนายเพิ่มขึ้นเป็นสัดส่วนเชิงเส้นกับขนาดชุดที่มีป้ายกำกับ ทำให้การอนุมานช้าลงเมื่อกลุ่มข้อมูลเติบโตขึ้นเรื่อย ๆ ในแต่ละรอบ
- ความไม่แน่นอนที่อิงตามระยะทางลดลงอย่างรวดเร็วในพื้นที่ที่มีมิติสูงเนื่องจากคำสาปของมิติ
- ขีดจำกัดความแม่นยำของ KNN ต่ำกว่าวิธีการแบบ Ensemble; กลยุทธ์เชิงรุกไม่สามารถชดเชยความสามารถที่จำกัดของผู้เรียนรู้พื้นฐานได้
- อ่อนไหวต่อการเลือก k และเมตริกระยะทาง; ค่าเริ่มต้นที่ไม่ดีนำไปสู่การประมาณค่าความไม่แน่นอนที่ไม่น่าเชื่อถือ
- จุดที่มีป้ายกำกับทั้งหมดถูกเก็บไว้ในหน่วยความจำ; งบประมาณขนาดใหญ่ส่งผลให้มีการใช้หน่วยความจำสูง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไม่ใช้พารามิเตอร์และไม่มีข้อสมมติฐาน: ไม่จำเป็นต้องมีข้อสมมติฐานการแจกแจงเกี่ยวกับข้อมูล
- การประมาณค่าความไม่แน่นอนเป็นธรรมชาติและตีความได้ — มันสะท้อนโดยตรงถึงการแบ่งคะแนนโหวตในหมู่เพื่อนบ้านที่ใกล้ที่สุด
- การเรียนรู้แบบขี้เกียจหมายถึงไม่มีค่าใช้จ่ายในการฝึกอบรมซ้ำต่อรอบ; ชุดที่มีป้ายกำกับที่ขยายออกไปคือแบบจำลองที่อัปเดตแล้ว
- มีประสิทธิภาพในการรวมป้ายกำกับใกล้ขอบเขตการตัดสินใจ ทำให้ได้ความละเอียดขอบเขตที่ดีด้วยคำอธิบายประกอบเพียงเล็กน้อย
- ทำงานได้ดีกับข้อมูลตารางที่มีมิติปานกลางที่มีทั้งฟีเจอร์ต่อเนื่องและไบนารี
การประยุกต์ใช้
- บันทึกทางการแพทย์หรือการทำคำอธิบายประกอบภาพที่เวลาของผู้เชี่ยวชาญในการติดป้ายกำกับมีจำกัด และขอบเขตการตัดสินใจราบเรียบในระดับท้องถิ่น
- การจัดประเภทข้อความหรือเอกสารด้วยคลังข้อมูลที่มีป้ายกำกับขนาดเล็กและเอกสารที่ไม่มีป้ายกำกับจำนวนมากโดยใช้ระยะทางแบบอิงการฝังตัว
- งานตรวจจับข้อผิดพลาดของเซ็นเซอร์และอุตสาหกรรมที่สามารถตรวจสอบเหตุการณ์ด้วยตนเองได้เพียงบางส่วน
- การสำรวจทางนิเวศวิทยาที่การยืนยันป้ายกำกับชนิดพันธุ์ในภาคสนามมีค่าใช้จ่ายสูงและมีการรวมกลุ่มในระดับท้องถิ่น
- ตัวจำแนกประเภทต้นแบบในระยะเริ่มต้นก่อนที่จะเปลี่ยนไปใช้แบบจำลองที่มีความสามารถสูงขึ้นเมื่อรวบรวมป้ายกำกับได้เพียงพอ
วิธีการทำงาน
วิธีการทำงาน
มีการรวบรวมชุดเริ่มต้นขนาดเล็กของตัวอย่างที่มีป้ายกำกับเพื่อเริ่มต้นกระบวนการ พร้อมกับกลุ่มตัวอย่างที่ไม่มีป้ายกำกับขนาดใหญ่ขึ้น ขอแนะนำให้ใช้การเลือกแบบสุ่มแบบแบ่งชั้นเพื่อให้แน่ใจว่ามีตัวอย่างอย่างน้อยหนึ่งตัวอย่างต่อคลาส เพื่อให้ KNN มีเพื่อนบ้านเริ่มต้นที่มีความหมายก่อนที่วงจรเชิงรุกจะเริ่มต้นขึ้น
ตัวจำแนกประเภท KNN จะถูกปรับให้เข้ากับชุดที่มีป้ายกำกับปัจจุบันโดยใช้ k และเมตริกระยะทางที่เลือก (โดยทั่วไปคือ Euclidean หรือ cosine) เนื่องจาก KNN เป็นแบบขี้เกียจและเก็บจุดการฝึกอบรมทั้งหมด การปรับจึงเกิดขึ้นทันที แต่ต้นทุนการทำนายจะเพิ่มขึ้นเป็นสัดส่วนเชิงเส้นกับขนาดชุดที่มีป้ายกำกับ — ซึ่งเป็นข้อพิจารณาที่เกี่ยวข้องเมื่อกลุ่มข้อมูลเติบโตขึ้นเรื่อย ๆ ในแต่ละรอบ
แต่ละตัวอย่างที่ไม่มีป้ายกำกับจะถูกให้คะแนนโดยเกณฑ์ข้อมูล การสุ่มตัวอย่างตามระยะขอบจะคำนวณช่องว่างระหว่างส่วนแบ่งคะแนนโหวตของสองคลาสสูงสุดในบรรดาเพื่อนบ้าน k ตัว; การสุ่มตัวอย่างตามเอนโทรปีจะคำนวณ H(y-hat | x) เหนือสัดส่วนคลาสทั้งหมด ตัวอย่างที่มีระยะขอบน้อยที่สุดหรือเอนโทรปีสูงสุดจะถูกสอบถาม: x* = argmax H(y-hat | x)
สูตร
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)ตัวอย่างที่ถูกสอบถามจะถูกส่งไปยังผู้เชี่ยวชาญ — ผู้ทำคำอธิบายประกอบที่เป็นมนุษย์หรือกลไกการติดป้ายกำกับอัตโนมัติ — เพื่อขอป้ายกำกับที่แท้จริง ป้ายกำกับจะถูกเพิ่มลงในชุดการฝึกอบรมและตัวอย่างจะถูกลบออกจากกลุ่มที่ไม่มีป้ายกำกับ ควรมีการตรวจสอบความน่าเชื่อถือของผู้ทำคำอธิบายประกอบ เนื่องจากป้ายกำกับที่มีสัญญาณรบกวนจะทำให้ประสิทธิภาพของ KNN ลดลงอย่างรวดเร็วใกล้ขอบเขต
เนื่องจาก KNN เป็นผู้เรียนรู้แบบขี้เกียจ จึงไม่จำเป็นต้องมีการฝึกอบรมซ้ำอย่างชัดเจน ชุดที่มีป้ายกำกับที่ขยายออกไปจะประกอบเป็นแบบจำลองใหม่ทันที วงจรการสอบถาม-ให้คะแนน-ติดป้ายกำกับจะทำซ้ำจนกว่างบประมาณการติดป้ายกำกับจะหมดลง เกณฑ์ความแม่นยำในการตรวจสอบจะถึง หรือจำนวนรอบสูงสุดจะถึง ประสิทธิภาพสุดท้ายจะถูกรายงานบนชุดทดสอบที่แยกต่างหาก
ข้อผิดพลาดที่พบบ่อย
- การไม่ทำให้ฟีเจอร์เป็นมาตรฐานก่อนการคำนวณระยะทาง ทำให้ฟีเจอร์ที่มีขนาดใหญ่ครอบงำเพื่อนบ้าน
- การใช้ชุดทดสอบเพื่อนำทางหรือประเมินการเลือกคำถาม ซึ่งถือเป็นการรั่วไหลของข้อมูล
- การตั้งค่า k เล็กเกินไป (k=1) ใกล้ขอบเขตการตัดสินใจ ทำให้เกิดคะแนนความไม่แน่นอนที่ผันผวนสูงซึ่งไม่สะท้อนความกำกวมที่แท้จริง
- การละเลยความไม่สมดุลของคลาสในชุดเริ่มต้น ซึ่งทำให้คำถามในช่วงแรกเอนเอียงไปทางขอบเขตของคลาสส่วนใหญ่
- การถือว่าความแม่นยำของการเรียนรู้เชิงรุกเทียบเท่ากับพื้นฐานที่มีการกำกับดูแลเต็มรูปแบบโดยไม่รายงานจำนวนป้ายกำกับที่ใช้
คำถามที่พบบ่อย
ทำไมต้องใช้ KNN แทนที่จะเป็นแบบจำลองที่มีประสิทธิภาพมากกว่าเป็นพื้นฐานการเรียนรู้เชิงรุก?
ความไม่แน่นอนของการแบ่งคะแนนโหวตของ KNN คำนวณได้ง่ายและไม่จำเป็นต้องมีการฝึกอบรมซ้ำ — การเพิ่มจุดที่มีป้ายกำกับใหม่จะอัปเดตแบบจำลองทันที ทำให้เป็นที่น่าสนใจเมื่อต้นทุนการคำนวณต่อรอบมีความสำคัญ สำหรับความแม่นยำสูงสุดภายใต้งบประมาณป้ายกำกับที่กำหนด ผู้เรียนรู้พื้นฐานแบบ Ensemble เช่น random forest หรือ gradient boosting มักจะให้ประสิทธิภาพดีกว่า KNN
ฉันจะเลือก k สำหรับการเรียนรู้เชิงรุกได้อย่างไร?
ช่วงเริ่มต้นทั่วไปคือ k = 5 ถึง 15 ค่า k ที่เล็กกว่าจะสร้างการประมาณค่าความไม่แน่นอนที่มีสัญญาณรบกวนมากกว่า; ค่า k ที่ใหญ่กว่าจะทำให้ขอบเขตราบเรียบขึ้น แต่อาจพลาดความกำกวมที่มีรายละเอียดปลีกย่อย ทำการตรวจสอบข้าม (cross-validate) k บนชุดเริ่มต้นที่มีป้ายกำกับ และปรับเปลี่ยนเมื่อกลุ่มที่มีป้ายกำกับเติบโตขึ้น
การปรับขนาดฟีเจอร์มีความสำคัญหรือไม่?
ใช่ สำคัญมาก ระยะทางของ KNN จะถูกครอบงำโดยฟีเจอร์ที่มีขนาดใหญ่หากฟีเจอร์ไม่ได้รับการทำให้เป็นมาตรฐาน ควรใช้การปรับขนาดแบบ min-max หรือการทำให้เป็นมาตรฐานแบบ z-score เสมอก่อนการคำนวณระยะทางและคะแนนความไม่แน่นอน
ต้องใช้ตัวอย่างที่มีป้ายกำกับเริ่มต้นกี่ตัวอย่าง?
อย่างน้อยที่สุด ต้องมีตัวอย่างที่มีป้ายกำกับหนึ่งหรือสองตัวอย่างต่อคลาส เพื่อให้ KNN สามารถสร้างเพื่อนบ้านสำหรับทุกคลาส ในทางปฏิบัติ ตัวอย่างที่มีป้ายกำกับ 5–20 ตัวอย่างจะให้การประมาณค่าความไม่แน่นอนเริ่มต้นที่เสถียรมากขึ้น; น้อยกว่านั้นมีความเสี่ยงที่จะเกิดเพื่อนบ้านที่เสื่อมสภาพซึ่งสร้างคำถามในช่วงแรกที่ไม่ให้ข้อมูล
ฉันควรหยุดวงจรเชิงรุกเมื่อใด?
กำหนดงบประมาณการติดป้ายกำกับล่วงหน้า หรือตรวจสอบความแม่นยำในการตรวจสอบและหยุดเมื่อการปรับปรุงต่อป้ายกำกับใหม่ลดลงต่ำกว่าเกณฑ์ที่มีความหมาย ห้ามใช้ชุดทดสอบเป็นสัญญาณการหยุดเด็ดขาด เนื่องจากจะทำให้ข้อมูลรั่วไหลเข้าสู่กระบวนการสอบถาม
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วZhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว