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

การแพร่กระจายป้ายกำกับ

ผู้เสนอ
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
  • สัญญาณรบกวนป้ายกำกับบนโหนดที่มีป้ายกำกับจำนวนน้อยจะแพร่กระจายและอาจทำให้ส่วนใหญ่ของกราฟเสียหาย

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

จุดแข็ง

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

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

  • การจำแนกข้อความและเอกสารเมื่อมีเอกสารเพียงส่วนน้อยที่มีป้ายกำกับที่มนุษย์กำหนด
  • การใส่คำอธิบายประกอบรูปภาพหรือวิดีโอซึ่งการติดป้ายกำกับด้วยตนเองมีค่าใช้จ่ายสูงและมีรูปภาพที่ไม่มีป้ายกำกับจำนวนมาก
  • การจำแนกโหนดเครือข่ายสังคมและกราฟการอ้างอิง (เช่น การอนุมานความสนใจของผู้ใช้หรือหัวข้อของบทความ)
  • ชีวสารสนเทศศาสตร์: การทำนายหน้าที่ของยีนหรือบทบาทการมีปฏิสัมพันธ์ของโปรตีนจากเครือข่ายชีวภาพที่มีคำอธิบายประกอบบางส่วน
  • การตรวจจับความผิดปกติแบบกึ่งกำกับดูแลโดยการแพร่กระจายป้ายกำกับปกติ/ผิดปกติที่ทราบผ่านกราฟความคล้ายคลึงกัน

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

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

1

สร้างกราฟความคล้ายคลึงถ่วงน้ำหนักบนจุดข้อมูลทั้งหมด n จุด ทั้งที่มีป้ายกำกับและไม่มีป้ายกำกับ ตัวเลือกทั่วไปคือเคอร์เนลแบบเกาส์เซียน (RBF): น้ำหนักขอบ W_ij เป็นฟังก์ชันที่ลดลงของระยะทางแบบยุคลิดยกกำลังสองระหว่างจุด i และ j ซึ่งควบคุมโดยพารามิเตอร์แบนด์วิดท์ sigma จะเก็บเฉพาะเพื่อนบ้าน k อันดับต้นๆ หรือเพื่อนบ้านรัศมี epsilon เท่านั้น เพื่อให้กราฟยังคงเบาบาง

สูตร
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

เมทริกซ์น้ำหนัก W จะถูกทำให้เป็นมาตรฐานคอลัมน์เพื่อสร้างเมทริกซ์การเปลี่ยน T แบบแถว-สุ่ม โดยที่แต่ละรายการ T_ij แสดงถึงความน่าจะเป็นที่ข้อมูลป้ายกำกับจะไหลจากโหนด j ไปยังโหนด i สิ่งนี้ทำให้มั่นใจได้ว่าอิทธิพลรวมที่แต่ละโหนดได้รับจะรวมกันเป็นหนึ่ง

สูตร
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

เริ่มต้นด้วยเมทริกซ์ป้ายกำกับเริ่มต้น 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)}
4

ผลลัพธ์จุดตรึงสำหรับบล็อกที่ไม่มีป้ายกำกับ 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 มาตรฐานเป็นขั้นตอนที่สอง

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

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

  1. Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. 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.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    คัดลอกแล้ว