แบบจำลองส่วนผสมของกระบวนการ Dirichlet

• มิถุนายน 23, 2014
• Vasilis Vryniotiso
• . 2 ความคิดเห็น

โพสต์บล็อกนี้เป็นส่วนที่สี่ของซีรีส์เรื่อง การทำคลัสเตอร์ด้วยแบบจำลองส่วนผสมของกระบวนการ Dirichlet. ในบทความที่แล้ว เราได้พูดถึง Finite Dirichlet Mixture Models และเรานำแบบจำลองของมันมาจำกัดสำหรับคลัสเตอร์ k ที่ไม่มีที่สิ้นสุด ซึ่งนำเราไปสู่การแนะนำกระบวนการ Dirichlet ดังที่เราเห็น เป้าหมายของเราคือการสร้างแบบจำลองผสมซึ่งไม่ต้องการให้เราระบุจำนวน k กลุ่ม/ส่วนประกอบตั้งแต่เริ่มต้น หลังจาก นำเสนอกระบวนการ Dirichlet Processes ที่แตกต่างกันถึงเวลาแล้วที่จะใช้ DP จริง ๆ เพื่อสร้างแบบจำลองส่วนผสมที่ไม่มีที่สิ้นสุดซึ่งทำให้เราสามารถทำคลัสเตอร์ได้ เป้าหมายของบทความนี้คือการกำหนดแบบจำลองส่วนผสมของกระบวนการ Dirichlet และหารือเกี่ยวกับการใช้กระบวนการร้านอาหารจีนและการสุ่มตัวอย่างกิ๊บส์ หากคุณยังไม่ได้อ่านโพสต์ก่อนหน้านี้ ขอแนะนำเป็นอย่างยิ่งให้ทำเช่นนั้นเนื่องจากหัวข้อนี้ค่อนข้างเป็นทฤษฎีและต้องมีความเข้าใจที่ดีเกี่ยวกับการสร้างแบบจำลอง

อัปเดต: ขณะนี้ Datumbox Machine Learning Framework เป็นโอเพ่นซอร์สและฟรีสำหรับ ดาวน์โหลด. ตรวจสอบแพ็คเกจ com.datumbox.framework.machinelearning.clustering เพื่อดูการใช้งาน Dirichlet Process Mixture Models ใน Java

1. คำจำกัดความของแบบจำลองส่วนผสมของกระบวนการไดริชเล็ต

การใช้กระบวนการ Dirichlet ช่วยให้เรามีตัวแบบผสมที่มีองค์ประกอบแบบอนันต์ ซึ่งถือได้ว่าเป็นการจำกัดขอบเขตของแบบจำลองจำกัดสำหรับ k ถึงอนันต์ สมมติว่าเรามีรูปแบบต่อไปนี้:

สมการที่ 1: แบบจำลองส่วนผสมของกระบวนการไดริชเล็ต

โดยที่ G ถูกกำหนดเป็น และ ใช้เป็นสัญกรณ์ย่อสำหรับ ซึ่งเป็นฟังก์ชันเดลต้าที่รับ 1 if และ 0 ที่อื่น เดอะ θ_i คือพารามิเตอร์คลัสเตอร์ที่สุ่มตัวอย่างจาก G การแจกแจงกำเนิด F ถูกกำหนดค่าโดยพารามิเตอร์คลัสเตอร์ θ_i และใช้สร้าง x_i การสังเกต สุดท้ายเราสามารถกำหนดการกระจายความหนาแน่น ซึ่งก็คือการกระจายส่วนผสมของเรา (ส่วนผสมที่นับได้ไม่สิ้นสุด) กับสัดส่วนการผสม และส่วนผสมต่างๆ .

รูปที่ 1: แบบจำลองกราฟิกของแบบจำลองส่วนผสมของกระบวนการไดริชเลต

ด้านบนเราจะเห็นรูปแบบกราฟิกที่เทียบเท่าของ DPMM เดอะ จี₀ คือการแจกแจงพื้นฐานของ DP และมักจะถูกเลือกให้เป็นคอนจูเกตก่อนการแจกแจงกำเนิด F ของเรา เพื่อทำให้การคำนวณง่ายขึ้นและใช้คุณสมบัติทางคณิตศาสตร์ที่น่าสนใจ α เป็นไฮเปอร์พารามิเตอร์สเกลาร์ของกระบวนการ Dirichlet และส่งผลต่อจำนวนคลัสเตอร์ที่เราจะได้รับ ยิ่งค่าของ α มากเท่าไร คลัสเตอร์ก็จะยิ่งมากขึ้นเท่านั้น ยิ่ง α เล็กลง คลัสเตอร์ก็จะน้อยลง เราควรสังเกตว่าค่าของ α แสดง พลังแห่งศรัทธา ในG₀. ค่าที่มากแสดงว่าตัวอย่างส่วนใหญ่จะมีความแตกต่างและมีค่าที่เน้นที่ G₀. G คือการแจกแจงแบบสุ่มบนพื้นที่พารามิเตอร์ Θ สุ่มตัวอย่างจาก DP ซึ่งกำหนดความน่าจะเป็นให้กับพารามิเตอร์ เดอะ θ_i เป็นเวกเตอร์พารามิเตอร์ซึ่งดึงมาจากการแจกแจงแบบ G และมีพารามิเตอร์ของคลัสเตอร์ การแจกแจงแบบ F ถูกทำให้เป็นพารามิเตอร์โดย θ_i และ x_i คือจุดข้อมูลที่สร้างโดย Geneative Distribution F

สิ่งสำคัญคือต้องสังเกตว่า θ_i เป็นองค์ประกอบของพื้นที่พารามิเตอร์ Θ และพวกเขา "กำหนดค่า" คลัสเตอร์ของเรา พวกมันยังสามารถถูกมองว่าเป็นตัวแปรแฝงบน x_i ซึ่งบอกเราว่าองค์ประกอบ/คลัสเตอร์ใดที่ x which_i มาจากอะไรและพารามิเตอร์ขององค์ประกอบนี้คืออะไร ดังนั้นสำหรับทุก x_i ที่เราสังเกต เราวาด θ_i จากการกระจาย G ทุกครั้งที่วาดการกระจายจะเปลี่ยนไปขึ้นอยู่กับการเลือกก่อนหน้า ดังที่เราเห็นในโครงร่างโกศของ Blackwell-MacQueen การกระจาย G สามารถรวมเข้ากับการเลือก future ในอนาคตของเรา_i ขึ้นอยู่กับ G . เท่านั้น₀: . การประมาณค่าพารามิเตอร์ θi จากสูตรก่อนหน้านั้นไม่สามารถทำได้เสมอไป เนื่องจากการใช้งานหลายอย่าง (เช่น กระบวนการร้านอาหารจีน) เกี่ยวข้องกับการแจงนับผ่าน ส่วนประกอบ k เพิ่มขึ้นแบบทวีคูณ. ดังนั้นวิธีการคำนวณโดยประมาณจึงถูกนำมาใช้ เช่น Gibbs Sampling สุดท้ายนี้ เราควรสังเกตว่าแม้ว่า k คลัสเตอร์จะไม่มีที่สิ้นสุด แต่จำนวนของคลัสเตอร์ที่ใช้งานอยู่คือ . ดังนั้น θ_i จะทำซ้ำและแสดงผลการจัดกลุ่ม

2. การใช้กระบวนการร้านอาหารจีนเพื่อกำหนดรูปแบบส่วนผสมที่ไม่มีที่สิ้นสุด

โมเดลที่กำหนดไว้ในส่วนก่อนหน้านั้นมีความสมบูรณ์ทางคณิตศาสตร์ แต่ก็มีข้อเสียที่สำคัญ: สำหรับ x ใหม่ทุกตัว_i ที่เราสังเกตเราต้องสุ่มตัวอย่างใหม่ ._i โดยคำนึงถึงค่าก่อนหน้าของ θ ปัญหาคือในหลายกรณี การสุ่มตัวอย่างพารามิเตอร์เหล่านี้อาจเป็นงานที่ยากและมีราคาแพงในการคำนวณ

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

สมการที่ 2: แบบจำลองส่วนผสมด้วย CRP

ข้างต้นเป็นแบบจำลองกำเนิดที่อธิบายว่าข้อมูล x . เป็นอย่างไร_i และคลัสเตอร์จะถูกสร้างขึ้น เพื่อทำการวิเคราะห์คลัสเตอร์ เราต้องใช้การสังเกต x_i และประมาณการมอบหมายคลัสเตอร์ z_i.

3. การอนุมานแบบจำลองผสมและการสุ่มตัวอย่างกิ๊บส์

น่าเสียดาย เนื่องจากกระบวนการ Dirichlet ไม่ใช่พารามิเตอร์ เรา ไม่สามารถใช้อัลกอริธึม EM ได้ เพื่อประมาณค่าตัวแปรแฝงที่เก็บการกำหนดคลัสเตอร์ ในการประมาณการงานที่มอบหมาย เราจะใช้ การสุ่มตัวอย่างกิ๊บส์ที่ยุบ.

Collapsed Gibbs Sampling เป็นอัลกอริธึม Markov Chain Monte Carlo (MCMC) อย่างง่าย รวดเร็วและทำให้เราสามารถรวมเอาตัวแปรบางตัวออกมาในขณะที่สุ่มตัวอย่างตัวแปรอื่น อย่างไรก็ตาม อัลกอริทึมนี้ต้องการให้เราเลือก G requires₀ ซึ่งเป็นคอนจูเกตก่อนการแจกแจงกำเนิดแบบ F เพื่อให้สามารถแก้สมการวิเคราะห์และสามารถสุ่มตัวอย่างได้โดยตรงจาก .

ขั้นตอนของ Collapsed Gibbs Sampling ที่เราจะใช้ในการประมาณการมอบหมายคลัสเตอร์มีดังต่อไปนี้:

• เริ่มต้น z_i การมอบหมายคลัสเตอร์แบบสุ่ม
• ทำซ้ำจนกระทั่งบรรจบกัน
• เลือกสุ่มขวาน_i
  
• เก็บ z . อื่นไว้_j แก้ไขสำหรับทุก j≠i:
• กำหนดค่าใหม่บนz_i โดยการคำนวณ “ความน่าจะเป็นของ CRP” ที่ขึ้นอยู่กับ z_j และ x_j ของทั้งหมด ji≠i:

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