การแพร่กระจายป้ายกำกับ
- ผู้เสนอ
- Zhu, X. & Ghahramani, Z.
- ปี
- 2002
- ประเภท
- Graph-based semi-supervised classification
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Label Propagation เป็นอัลกอริทึมการเรียนรู้แบบกึ่งกำกับดูแลบนกราฟที่พัฒนาโดย Zhu และ Ghahramani ในปี 2002 ซึ่งกระจายป้ายกำกับคลาสจากชุดโหนดที่มีป้ายกำกับจำนวนน้อยไปยังโหนดที่ไม่มีป้ายกำกับจำนวนมาก โดยการแพร่กระจายข้อมูลป้ายกำกับแบบวนซ้ำตามขอบของกราฟความคล้ายคลึงกัน โดยใช้ประโยชน์จากโครงสร้างแมนิฟอล์ของข้อมูล
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพเครือข่ายสังคมที่ผู้คนบางส่วนได้รับการกำหนดหมวดหมู่แล้ว ข่าวลือแพร่กระจายตามธรรมชาติ: แต่ละคนมีแนวโน้มที่จะรับป้ายกำกับที่พบบ่อยที่สุดในหมู่เพื่อนบ้านที่ใกล้ชิดของตน Label Propagation ทำให้แนวคิดนี้เป็นรูปธรรม — โดยสร้างกราฟถ่วงน้ำหนักที่จุดข้อมูลที่คล้ายคลึงกันเชื่อมต่อด้วยขอบที่แข็งแกร่ง จากนั้นปล่อยให้ป้ายกำกับที่ทราบไหลออกไปทีละขั้นตอนจนกว่าจุดที่ไม่มีป้ายกำกับแต่ละจุดจะดูดซับสัญญาณเพียงพอที่จะจำแนกได้ เนื่องจากกระบวนการแพร่กระจายนี้เป็นไปตามเรขาคณิตของข้อมูล แทนที่จะเป็นขอบเขตการตัดสินใจตามอำเภอใจ จึงสามารถให้การทำนายที่แม่นยำสูงได้ แม้ว่าตัวอย่างที่มีป้ายกำกับจะหายากก็ตาม
ประวัติศาสตร์
Xiaojin (Jerry) Zhu และ Zoubin Ghahramani ได้นำเสนอ Label Propagation ในรายงานทางเทคนิคของ Carnegie Mellon University ปี 2002 (CMU-CALD-02-107) ในปีถัดมา Zhu, Ghahramani และ John Lafferty ได้ตีพิมพ์กรอบงาน Gaussian fields and harmonic functions ที่เกี่ยวข้องอย่างใกล้ชิดในงาน ICML 2003 ซึ่งให้การตีความเชิงความน่าจะเป็นผ่านการสุ่มเดินและ Gaussian Markov random fields งานเหล่านี้เป็นตัวเร่งให้เกิดวิธีการกึ่งกำกับดูแลบนกราฟจำนวนมากในช่วงกลางทศวรรษ 2000 Dengyong Zhou และเพื่อนร่วมงานได้เสนอ Label Spreading ในปี 2004 ซึ่งเป็นรูปแบบที่ได้รับการปรับให้เหมาะสมซึ่งอนุญาตให้ข้อมูลป้ายกำกับเข้ามาแทนที่ป้ายกำกับที่ถูกบังคับบางส่วน ทำให้มีความทนทานต่อสัญญาณรบกวนจากป้ายกำกับมากขึ้น ทั้งสองวิธีเป็นเกณฑ์มาตรฐานมาตรฐานในการประเมินผลการเรียนรู้แบบกึ่งกำกับดูแล และรวมอยู่ในไลบรารีการเรียนรู้ของเครื่องที่ใช้กันอย่างแพร่หลาย ด้วยการเพิ่มขึ้นของ Graph Neural Networks ในทศวรรษ 2010 Label Propagation ได้กลายเป็นต้นแบบเชิงแนวคิดและเกณฑ์มาตรฐานที่มีการแข่งขัน ยังคงถูกอ้างอิงถึงความเรียบง่ายและการรับประกันในรูปแบบปิด
ควรใช้เมื่อใด
Label Propagation เหมาะสมเมื่อตัวอย่างที่มีป้ายกำกับมีจำนวนน้อยเมื่อเทียบกับขนาดชุดข้อมูลทั้งหมด ข้อมูลมีโครงสร้างกลุ่มหรือโครงสร้างแมนิฟอล์พื้นฐานที่กราฟความคล้ายคลึงสามารถจับภาพได้ และมีเหตุผลที่จะเชื่อว่าสมมติฐานความเรียบเนียนเป็นจริง — ว่าจุดที่อยู่ใกล้กัน (ในปริภูมิคุณลักษณะ) มีแนวโน้มที่จะมีป้ายกำกับเดียวกัน สถานการณ์ทั่วไป ได้แก่ การจำแนกข้อความที่มีเอกสารที่ถูกกำกับน้อย การจำแนกรูปภาพที่มีป้ายกำกับจากมนุษย์แบบเบาบาง และการจำแนกโหนดเครือข่าย วิธีการนี้ต้องการให้กราฟเชื่อมต่อกัน (หรืออย่างน้อยที่สุด โหนดที่ไม่มีป้ายกำกับแต่ละโหนดสามารถเข้าถึงได้จากโหนดที่มีป้ายกำกับ) ไม่เหมาะเมื่อปริภูมิคุณลักษณะไม่สะท้อนความคล้ายคลึงเชิงความหมาย เมื่อขอบเขตการตัดสินใจตัดผ่านบริเวณที่หนาแน่น หรือเมื่อข้อมูลทั้งหมดถูกกำกับแล้ว
ข้อจำกัดและข้อควรพิจารณา
- ความสามารถในการปรับขนาด: การจัดเก็บและดำเนินการบนเมทริกซ์น้ำหนัก n x n เป็นไปไม่ได้สำหรับชุดข้อมูลขนาดใหญ่หากไม่มีการประมาณค่าแบบเบาบาง
- การสร้างกราฟมีความอ่อนไหวต่อการเลือกแบนด์วิดท์เคอร์เนล sigma และขนาดเพื่อนบ้าน k การเลือกที่ไม่ดีจะลดความแม่นยำลงอย่างมาก
- สมมติฐานความเรียบเนียน (กลุ่ม): การละเมิดสมมติฐานนี้ — เมื่อขอบเขตการตัดสินใจผ่านบริเวณที่หนาแน่น — นำไปสู่การจำแนกผิดอย่างเป็นระบบ
- เป็นแบบ Transductive โดยค่าเริ่มต้น: การทำนายสำหรับจุดทดสอบใหม่ที่ยังไม่เคยเห็นต้องการการรันอัลกอริทึมซ้ำหรือส่วนขยายแบบ Inductive
- สัญญาณรบกวนป้ายกำกับบนโหนดที่มีป้ายกำกับจำนวนน้อยจะแพร่กระจายและอาจทำให้ส่วนใหญ่ของกราฟเสียหาย
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ใช้ประโยชน์จากข้อมูลที่ไม่มีป้ายกำกับได้อย่างมีประสิทธิภาพ ให้ความแม่นยำสูงด้วยตัวอย่างที่มีป้ายกำกับน้อยมาก
- การรับประกันการลู่เข้าในรูปแบบปิด: การอัปเดตแบบวนซ้ำจะถึงจุดตรึงที่ไม่ซ้ำกันเสมอ
- จัดการปัญหาหลายคลาสได้อย่างเป็นธรรมชาติโดยไม่ต้องปรับเปลี่ยน
- การตีความเชิงเรขาคณิตที่เข้าใจง่ายซึ่งมีพื้นฐานมาจากการแพร่กระจายกราฟและการวิเคราะห์ฮาร์มอนิก
- ไม่มีพารามิเตอร์โมเดลให้ปรับให้เหมาะสมนอกเหนือจากการเลือกการสร้างกราฟ (แบนด์วิดท์เคอร์เนล ขนาดเพื่อนบ้าน)
การประยุกต์ใช้
- การจำแนกข้อความและเอกสารเมื่อมีเอกสารเพียงส่วนน้อยที่มีป้ายกำกับที่มนุษย์กำหนด
- การใส่คำอธิบายประกอบรูปภาพหรือวิดีโอซึ่งการติดป้ายกำกับด้วยตนเองมีค่าใช้จ่ายสูงและมีรูปภาพที่ไม่มีป้ายกำกับจำนวนมาก
- การจำแนกโหนดเครือข่ายสังคมและกราฟการอ้างอิง (เช่น การอนุมานความสนใจของผู้ใช้หรือหัวข้อของบทความ)
- ชีวสารสนเทศศาสตร์: การทำนายหน้าที่ของยีนหรือบทบาทการมีปฏิสัมพันธ์ของโปรตีนจากเครือข่ายชีวภาพที่มีคำอธิบายประกอบบางส่วน
- การตรวจจับความผิดปกติแบบกึ่งกำกับดูแลโดยการแพร่กระจายป้ายกำกับปกติ/ผิดปกติที่ทราบผ่านกราฟความคล้ายคลึงกัน
วิธีการทำงาน
วิธีการทำงาน
สร้างกราฟความคล้ายคลึงถ่วงน้ำหนักบนจุดข้อมูลทั้งหมด n จุด ทั้งที่มีป้ายกำกับและไม่มีป้ายกำกับ ตัวเลือกทั่วไปคือเคอร์เนลแบบเกาส์เซียน (RBF): น้ำหนักขอบ W_ij เป็นฟังก์ชันที่ลดลงของระยะทางแบบยุคลิดยกกำลังสองระหว่างจุด i และ j ซึ่งควบคุมโดยพารามิเตอร์แบนด์วิดท์ sigma จะเก็บเฉพาะเพื่อนบ้าน k อันดับต้นๆ หรือเพื่อนบ้านรัศมี epsilon เท่านั้น เพื่อให้กราฟยังคงเบาบาง
สูตร
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)เมทริกซ์น้ำหนัก W จะถูกทำให้เป็นมาตรฐานคอลัมน์เพื่อสร้างเมทริกซ์การเปลี่ยน T แบบแถว-สุ่ม โดยที่แต่ละรายการ T_ij แสดงถึงความน่าจะเป็นที่ข้อมูลป้ายกำกับจะไหลจากโหนด j ไปยังโหนด i สิ่งนี้ทำให้มั่นใจได้ว่าอิทธิพลรวมที่แต่ละโหนดได้รับจะรวมกันเป็นหนึ่ง
สูตร
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}เริ่มต้นด้วยเมทริกซ์ป้ายกำกับเริ่มต้น F (หนึ่งคอลัมน์ต่อคลาส) อัลกอริทึมจะวนซ้ำ: คูณ F ด้วย T จากนั้นบังคับแถวที่สอดคล้องกับโหนดที่มีป้ายกำกับกลับไปที่ป้ายกำกับแบบ one-hot ที่แท้จริง Y_L การบังคับนี้จะป้องกันไม่ให้ป้ายกำกับที่ทราบเลื่อนออกไปและทำหน้าที่เป็นเงื่อนไขขอบเขตที่ดูดซับ การวนซ้ำจะถูกทำซ้ำจนกว่ารายการที่ไม่มีป้ายกำกับของ F จะลู่เข้า
สูตร
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}ผลลัพธ์จุดตรึงสำหรับบล็อกที่ไม่มีป้ายกำกับ F_U* จะได้รับในรูปแบบปิดเป็น (I - T_UU)^{-1} T_UL Y_L โดยที่ T_UU คือเมทริกซ์ย่อยของการเปลี่ยนระหว่างโหนดที่ไม่มีป้ายกำกับ และ T_UL จับการเปลี่ยนจากโหนดที่มีป้ายกำกับไปยังโหนดที่ไม่มีป้ายกำกับ ในทางปฏิบัติ รูปแบบวนซ้ำจะถูกเลือกสำหรับกราฟขนาดใหญ่เนื่องจากหลีกเลี่ยงการผกผันเมทริกซ์ ทั้งสองวิธีให้ผลลัพธ์ที่ไม่ซ้ำกันเหมือนกัน
สูตร
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_Lข้อผิดพลาดที่พบบ่อย
- การใช้กราฟที่เชื่อมต่อกันอย่างสมบูรณ์โดยไม่มีการทำให้เบาบาง ซึ่งบดบังโครงสร้างท้องถิ่นและไม่สามารถคำนวณได้ในระดับใหญ่
- การเลือก sigma โดยค่าเริ่มต้นโดยไม่มีการตรวจสอบไขว้บนชุดที่มีป้ายกำกับ ซึ่งนำไปสู่การกระจายป้ายกำกับที่เรียบเกินไปหรือน้อยเกินไป
- การเพิกเฉยต่อความไม่สมดุลของคลาส: หากคลาสหนึ่งครอบงำชุดที่มีป้ายกำกับ ป้ายกำกับของคลาสนั้นจะท่วมกราฟ จำเป็นต้องมีการถ่วงน้ำหนักใหม่หรือการสุ่มตัวอย่าง
- การปฏิบัติต่อการทำนายแบบ Transductive ราวกับว่าเป็นโมเดลที่ฝึกฝนแล้ว และนำไปใช้กับจุดใหม่โดยไม่มีส่วนหุ้มแบบ Inductive
- การไม่ตรวจสอบการเชื่อมต่อของกราฟ: โหนดที่ไม่มีป้ายกำกับในส่วนประกอบที่แยกจากกันจะไม่ได้รับสัญญาณใดๆ และจะใช้ค่าเฉลี่ยความน่าจะเป็นของคลาสแบบสม่ำเสมอ
คำถามที่พบบ่อย
อะไรคือความแตกต่างระหว่าง Label Propagation และ Label Spreading?
Label Spreading ซึ่งเสนอโดย Zhou และคณะ (2004) ได้นำเสนอพารามิเตอร์การปรับให้เหมาะสม alpha ซึ่งควบคุมว่าแต่ละโหนดจะรักษาป้ายกำกับเริ่มต้นของตนเองมากน้อยเพียงใดเมื่อเทียบกับการรับป้ายกำกับของเพื่อนบ้าน ใน Label Propagation แบบคลาสสิก โหนดที่มีป้ายกำกับจะถูกบังคับอย่างเข้มงวด ทำให้เป็นแบบดูดซับอย่างสมบูรณ์ Label Spreading อนุญาตให้โหนดที่มีป้ายกำกับถูกแทนที่บางส่วน ซึ่งทำให้มีความทนทานต่อสัญญาณรบกวนจากป้ายกำกับมากขึ้น โดยแลกกับไฮเปอร์พารามิเตอร์เพิ่มเติมหนึ่งตัว
Label Propagation สามารถปรับขนาดให้เข้ากับชุดข้อมูลขนาดใหญ่ได้หรือไม่?
โซลูชันรูปแบบปิดแบบตรงไปตรงมาต้องการการผกผันเมทริกซ์ (n_U x n_U) ซึ่งเป็นไปไม่ได้สำหรับ n ขนาดใหญ่ ในทางปฏิบัติ กราฟ k-nearest-neighbor หรือ epsilon-radius แบบเบาบางจะลดหน่วยความจำลงเหลือ O(nk) และการอัปเดตแบบวนซ้ำจะปรับขนาดตามจำนวนขอบต่อการวนซ้ำโดยประมาณ สำหรับกราฟขนาดใหญ่มาก จะใช้วิธีการ approximate nearest-neighbor และรูปแบบ mini-batch
ต้องใช้ตัวอย่างที่มีป้ายกำกับจำนวนเท่าใด?
Label Propagation ได้รับการออกแบบมาโดยเฉพาะสำหรับสภาวะที่มีป้ายกำกับน้อยมาก แม้แต่โหนดที่มีป้ายกำกับเพียงโหนดเดียวต่อคลาสก็สามารถให้การทำนายที่มีความหมายได้หากโครงสร้างกราฟสอดคล้องกับขอบเขตคลาส แม้ว่าการมีตัวอย่างที่มีป้ายกำกับอย่างน้อยสองสามตัวอย่างต่อคลาสจะแนะนำอย่างยิ่งเพื่อความน่าเชื่อถือ ประสิทธิภาพจะลดลงเมื่อสัญญาณรบกวนจากป้ายกำกับเพิ่มขึ้น หรือเมื่อกราฟให้ข้อมูลเกี่ยวกับสมาชิกคลาสน้อยลง
Label Propagation สามารถทำนายข้อมูลใหม่ที่ยังไม่เคยเห็นได้หรือไม่?
ในรูปแบบ Transductive มาตรฐาน ไม่ได้ — อัลกอริทึมทำงานบนกราฟที่คงที่และไม่มีกลไกในการทำนายภายนอกกราฟนั้น สำหรับการใช้งานแบบ Inductive วิธีการทั่วไปคือการเชื่อมต่อจุดใหม่กับเพื่อนบ้าน k อันดับต้นๆ ในกราฟที่มีอยู่และทำการแพร่กระจายบางส่วน หรือใช้เมทริกซ์ป้ายกำกับที่ลู่เข้าเพื่อฝึกตัวจำแนกแบบ Supervised มาตรฐานเป็นขั้นตอนที่สอง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วZhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วChapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9คัดลอกแล้ว