Dirichlet ดำเนินการกระบวนการร้านอาหารจีนและการแสดงอื่น ๆ

• May 20, 2014
• Vasilis Vryniotiso
• . ไม่มีความคิดเห็น

บทความนี้เป็นส่วนที่สามของซีรีส์เรื่อง Clustering with Dirichlet Process Mixture Models คราวที่แล้วเรากำหนด Finite Mixture Model ตาม Dirichlet Distribution และเราตั้งคำถามว่าเราจะทำให้โมเดลนี้ไม่มีที่สิ้นสุดได้อย่างไร เราพูดคุยกันสั้น ๆ เกี่ยวกับแนวคิดในการจำกัดขอบเขตของแบบจำลองเมื่อจำนวน k ของกลุ่มมีแนวโน้มเป็นอนันต์ แต่เมื่อเราเน้นย้ำว่าการมีอยู่ของวัตถุดังกล่าวไม่ใช่เรื่องเล็กน้อย ”?) เพื่อเป็นการเตือนความจำ เหตุผลที่เราต้องการทำให้ k เป็นอนันต์ เพราะด้วยวิธีนี้ เราจะมีโมเดลที่ไม่มีพารามิเตอร์ ซึ่งไม่ต้องการให้เรากำหนดจำนวนคลัสเตอร์ภายในข้อมูลล่วงหน้า

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

แม้ว่าเป้าหมายของเราคือการสร้างแบบจำลองที่สามารถทำคลัสเตอร์บนชุดข้อมูลได้ ก่อนนั้นเราต้องหารือเกี่ยวกับกระบวนการของ Dirichlet เราจะให้ทั้งคำจำกัดความทางคณิตศาสตร์ที่เข้มงวดและคำอธิบายที่เข้าใจง่ายยิ่งขึ้นของ DP และเราจะหารือถึงวิธีการสร้างกระบวนการ โครงสร้าง/การเป็นตัวแทนเหล่านั้นสามารถมองได้ว่าเป็นวิธีการหาเหตุการณ์ที่เกิดขึ้นของกระบวนการ Dirichlet ใน "ชีวิตจริง"

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

1. คำจำกัดความของกระบวนการ Dirichlet

กระบวนการ Dirichlet บนสเปซ Θ เป็นกระบวนการสุ่ม เป็นการแจกแจงความน่าจะเป็นเหนือ “การแจกแจงความน่าจะเป็นบน Θ สเปซ” และ a วาดจากมันคือการกระจายแบบไม่ต่อเนื่อง. การแจกแจงแบบ Dirichlet อย่างเป็นทางการคือการแจกแจงเหนือการวัดความน่าจะเป็น NS การวัดความน่าจะเป็น เป็นฟังก์ชันของเซตย่อยของสเปซ Θ ถึง [0,1] G เป็นการวัดความน่าจะเป็นแบบสุ่มแบบกระจาย DP แสดงเป็น , ถ้าสำหรับพาร์ติชันใด ๆ (A₁,…NS_n) ของพื้นที่ Θ เรามีสิ่งนั้น .

รูปที่ 1: ระยะขอบบนไฟไนต์พาร์ติชั่นเป็น Dirichlet กระจาย

DP มีสองพารามิเตอร์: อันแรกคือการแจกแจงฐาน G₀ ซึ่งทำหน้าที่เหมือนคนใจร้าย . อันที่สองคือค่าพารามิเตอร์กำลัง α ซึ่งเป็นค่าบวกอย่างเคร่งครัดและทำหน้าที่เหมือนค่าความแปรปรวนผกผัน . กำหนดขอบเขตของการทำซ้ำของค่าของการกระจายเอาต์พุต ยิ่งค่าของ a สูง การซ้ำซ้อนก็จะยิ่งน้อยลง ยิ่งค่าน้อย การซ้ำซ้อนของค่าของการกระจายเอาต์พุตก็จะยิ่งสูงขึ้น สุดท้าย ช่องว่าง Θ คือพื้นที่พารามิเตอร์ที่เรากำหนด DP นอกจากนี้ช่องว่าง Θ ยังเป็นพื้นที่คำจำกัดความของ G₀ ซึ่งเป็นตัวเดียวกับตัว G

ที่เรียบง่ายและมากขึ้น ทางสัญชาตญาณ เพื่ออธิบายกระบวนการ Dirichlet มีดังต่อไปนี้ สมมุติว่าเรามีพื้นที่ Θ ที่สามารถแบ่งพาร์ติชั่นได้แบบไม่จำกัด (A₁,…,NS_n) และการแจกแจงความน่าจะเป็น G ซึ่งกำหนดความน่าจะเป็นให้กับพวกเขา G เป็นการแจกแจงความน่าจะเป็นเฉพาะส่วน Θ แต่มีอย่างอื่นอีกมากมาย กระบวนการ Dirichlet บน Θ จำลองแบบนี้ เป็นการแจกแจงการแจกแจงความน่าจะเป็นที่เป็นไปได้ทั้งหมดบนอวกาศ Θ กระบวนการ Dirichlet ถูกกำหนดพารามิเตอร์ด้วย G₀ ฟังก์ชันฐานและพารามิเตอร์ความเข้มข้น α เราสามารถพูดได้ว่า G ถูกแจกจ่ายตาม DP ด้วยพารามิเตอร์ α และ G₀ ถ้าการแจกแจงร่วมของความน่าจะเป็นที่ G กำหนดให้กับพาร์ติชั่นของ Θ เป็นไปตามการแจกแจงของ Dirichlet อีกวิธีหนึ่ง เราสามารถพูดได้ว่าความน่าจะเป็นที่ G กำหนดให้กับพาร์ติชั่นจำกัดใดๆ ของ Θ เป็นไปตามการกระจายของไดริชเล็ต

รูปที่ 2: แบบจำลองกราฟิกของกระบวนการ Dirichlet

สุดท้ายด้านบนเราจะเห็น แบบจำลองกราฟิกของ DP. เราควรสังเกตว่า α เป็นไฮเปอร์พารามิเตอร์สเกลาร์ G₀ คือการแจกแจงฐานของ DP, G เป็นการแจกแจงแบบสุ่มบนพื้นที่พารามิเตอร์ sample สุ่มตัวอย่างจาก DP ซึ่งกำหนดความน่าจะเป็นให้กับพารามิเตอร์และ θ_i เป็นเวกเตอร์พารามิเตอร์ซึ่งดึงมาจากการแจกแจง G และเป็นองค์ประกอบของช่องว่าง Θ

2. กระบวนการ Dirichlet หลัง

กระบวนการ Posterior Dirichlet ถูกกล่าวถึงโดย เฟอร์กูสัน. เราเริ่มต้นด้วยการสุ่มวัดความน่าจะเป็น G จากกระบวนการ Dirichlet . เนื่องจาก G เป็นการแจกแจงความน่าจะเป็นส่วน Θ เราจึงสามารถสุ่มตัวอย่างจากการแจกแจงนี้และวาดตัวอย่างที่แจกแจงเหมือนกันอย่างอิสระ θ₁,…, θ_n ~ G. เนื่องจากการดึงจากกระบวนการ Dirichlet เป็นการแจกแจงแบบไม่ต่อเนื่อง เราจึงสามารถแสดง ที่ไหน เป็นสัญกรณ์สั้นสำหรับ ซึ่งเป็นฟังก์ชันเดลต้าที่รับ 1 if และ 0 ที่อื่น ผลที่น่าสนใจของสิ่งนี้คือ เนื่องจาก G ถูกกำหนดด้วยวิธีนี้ จึงมีความเป็นไปได้เชิงบวกที่กลุ่มตัวอย่างต่างๆ มีค่าเท่ากัน . ดังที่เราจะได้เห็นในภายหลัง สิ่งนี้สร้างเอฟเฟกต์การจัดกลุ่มที่สามารถใช้เพื่อทำการวิเคราะห์คลัสเตอร์บนชุดข้อมูล

โดยใช้คำจำกัดความและการสังเกตข้างต้น เราต้องการประเมินส่วนหลังของกระบวนการ Dirichlet จากตัวอย่าง θ ทั้งที่รู้อยู่แก่ใจว่า และ โดยใช้ Bayes Rules และ Conjugacy ระหว่าง Dirichlet และ Multinomial เรามีสิ่งนั้น และ .

สมการที่ 1: กระบวนการ Dirichlet หลัง

คุณสมบัตินี้มีความสำคัญมากและถูกใช้โดยการแสดงแทน DP ต่างๆ

3. การแสดงแทนกระบวนการ Dirichlet

ในส่วนก่อนหน้านี้ เราได้กำหนดกระบวนการ Dirichlet และนำเสนอแบบจำลองทางทฤษฎี คำถามสำคัญข้อหนึ่งที่เราต้องตอบคือ เราจะรู้ได้อย่างไรว่าวัตถุนั้นมีอยู่จริง และเราจะทำได้อย่างไร สร้างและเป็นตัวแทน กระบวนการ Dirichlet

ตัวบ่งชี้แรกของการดำรงอยู่จัดทำโดย เฟอร์กูสัน ผู้ที่ใช้ทฤษฎีบทความสม่ำเสมอของ Kolmogorov ให้คำจำกัดความของกระบวนการ Dirichlet และอธิบายกระบวนการหลัง Dirichlet ต่อการวิจัยของเขา, Blackwell และ MacQueen ใช้ทฤษฎีบทของ De Finetti เพื่อพิสูจน์การมีอยู่ของการวัดความน่าจะเป็นแบบสุ่มและแนะนำโครงร่างโกศของ Blackwell-MacQueen ซึ่งเป็นไปตามคุณสมบัติของกระบวนการ Dirichlet ในปี 1994 เศรษฐรามัน ให้วิธีการเพิ่มเติมที่ง่ายและตรงไปตรงมาในการสร้าง DP โดยแนะนำโครงสร้าง Stick-break ในที่สุดก็มีตัวแทนอื่นให้ provided ชาติพันธุ์ ผู้แนะนำกระบวนการร้านอาหารจีนเป็นวิธีที่มีประสิทธิภาพในการสร้างกระบวนการ Dirichlet

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

3.1 โครงการโกศ Blackwell-MacQueen

โกศ Blackwell-MacQueen สามารถใช้เป็นตัวแทนของกระบวนการ Dirichlet และได้รับการแนะนำโดย Blackwell และ MacQueen. มันขึ้นอยู่กับรูปแบบโกศของPólyaซึ่งสามารถมองเห็นได้ว่าเป็นแบบจำลองที่ตรงกันข้ามกับการสุ่มตัวอย่างโดยไม่ต้องเปลี่ยน ในรูปแบบโกศ Pólya เราคิดว่าเรามีโกศที่ไม่โปร่งใสที่มีลูกบอลสีและเราสุ่มจับลูกบอล เมื่อเราวาดลูกบอล เราสังเกตสีของลูกบอล เราใส่กลับเข้าไปในโกศ และเราเพิ่มลูกบอลสีเดียวกันอีกลูก Blackwell และ MacQueen ใช้โครงร่างที่คล้ายกันเพื่อสร้างกระบวนการ Dirichlet

โครงการนี้สร้างลำดับของ θ₁,θ₂,… กับ ความน่าจะเป็นตามเงื่อนไข . ในโครงการนี้ เราคิดว่า G₀ คือการกระจายตามสีและแต่ละสี each_n หมายถึงสีของลูกบอลที่วางอยู่ในโกศ NS ขั้นตอนวิธี จะเป็นดังนี้:

· เราเริ่มต้นด้วยโกศว่างเปล่า

· โดยมีความน่าจะเป็นเป็นสัดส่วนกับ α เราวาด และเราเพิ่มลูกบอลสีนี้ในโกศ

· ด้วยความน่าจะเป็นที่เป็นสัดส่วนกับ n-1 เราวาดลูกบอลแบบสุ่มจากโกศ เราสังเกตสีของมัน เราวางมันกลับไปที่โกศ และเราเพิ่มลูกบอลที่มีสีเดียวกันเพิ่มเติมในโกศ

ก่อนหน้านี้เราเริ่มต้นด้วยกระบวนการ Dirichlet และได้รับโครงการ Blackwell-MacQueen ตอนนี้ มาเริ่มย้อนกลับจากแผน Blackwell-MacQueen และรับ DP ตั้งแต่ θ_i ถูกดึงออกมาในลักษณะที่งี่เง่าจาก G การแจกแจงร่วมกันของพวกมันจะคงที่กับการเรียงสับเปลี่ยนแบบจำกัดใดๆ และด้วยเหตุนี้ พวกมันจึงสามารถแลกเปลี่ยนกันได้ ด้วยการใช้ทฤษฎีบทของเดอ ฟิเนตติ เราจึงเห็นว่าต้องมีการแจกแจงเหนือการวัดเพื่อทำให้เป็น iid และการแจกแจงนี้คือกระบวนการดิริชเลต์ ด้วยเหตุนี้ เราจึงพิสูจน์ได้ว่าโครงร่างโกศของ Blackwell-MacQueen เป็นตัวแทนของ DP และทำให้เรามีวิธีสร้างที่เป็นรูปธรรม ดังที่เราจะได้เห็นในภายหลัง โครงร่างนี้เทียบเท่ากับกระบวนการทางคณิตศาสตร์ของร้านอาหารจีน

3.2 โครงสร้างที่แตกหัก

โครงสร้างแบบหักติดเป็นอีกทางเลือกหนึ่งในการแสดงกระบวนการ Dirichlet ซึ่งแนะนำโดย เศรษฐรามัน. เป็นวิธีที่สร้างสรรค์ในการสร้าง การกระจายและการใช้งาน ตามการเปรียบเทียบ: สมมติว่าเรามีแท่งยาว 1 เราทำลายมันที่ตำแหน่ง β₁ และเรามอบหมายให้ π₁ เท่ากับความยาวของท่อนไม้ที่เราหัก เราทำซ้ำขั้นตอนเดียวกันเพื่อรับ π₂,₃,… ฯลฯ ; เนื่องจากวิธีการกำหนดรูปแบบนี้ เราจึงสามารถดำเนินการต่อไปได้ไม่จำกัดครั้ง

ขึ้นอยู่กับ π . ข้างต้น_k สามารถจำลองเป็น ที่นี่มี ในขณะที่ในรูปแบบก่อนหน้า θ จะถูกสุ่มตัวอย่างโดยตรงโดยการกระจายฐาน . ดังนั้น การแจกแจง G สามารถเขียนเป็นผลรวมของฟังก์ชันเดลต้าที่ถ่วงน้ำหนักด้วย π_k ความน่าจะเป็นที่เท่ากับ . ดังนั้น โครงสร้างแบบหักแท่งทำให้เรามีวิธีที่ง่ายและเป็นธรรมชาติในการสร้างกระบวนการ Dirichlet

3.3 กระบวนการร้านอาหารจีน

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

CRP กำหนดการกระจายบนพื้นที่ของพาร์ติชันของจำนวนเต็มบวก เราเริ่มต้นด้วยการวาด θ₁,…θ_n จากโครงการโกศ Blackwell-MacQueen ดังที่เราได้พูดคุยกันในส่วนก่อนหน้านี้ เราคาดว่าจะเห็นผลการจัดกลุ่ม ดังนั้นจำนวนรวมของค่า θ ที่ไม่ซ้ำกัน k จะน้อยกว่า n อย่างมีนัยสำคัญ ดังนั้น นี่จึงกำหนดพาร์ติชั่นของชุด {1,2,…,n} ใน k คลัสเตอร์ ดังนั้น การดึงจากโครงร่างโกศของ Blackwell-MacQueen ทำให้เกิดการแบ่งพาร์ติชันแบบสุ่มของชุด {1,2,…,n} ชุด กระบวนการร้านอาหารจีนเป็นเช่นนี้ การกระจายผ่านพาร์ติชั่น. อัลกอริทึมมีดังนี้:

· เราเริ่มต้นด้วยร้านอาหารที่ว่างเปล่า

· 1^st ลูกค้านั่งบน 1 . เสมอ^st ตาราง

· n+1^th ลูกค้ามี 2 ตัวเลือก:

o นั่งบนโต๊ะว่างที่ 1 ด้วยความน่าจะเป็น

o นั่งบนโต๊ะใด ๆ ของ kth ที่ถูกครอบครองด้วยความน่าจะเป็น
ที่ไหน คือจำนวนคนนั่งโต๊ะนั้น

โดยที่ α คือค่าการกระจายของ DP และ n คือจำนวนลูกค้าทั้งหมดในร้านอาหาร ณ เวลาที่กำหนด ตัวแปรแฝง z_i เก็บหมายเลขตารางของi^th ลูกค้าและรับค่าตั้งแต่ 1 ถึง k_n โดยที่ k_n คือจำนวนโต๊ะที่ถูกครอบครองทั้งหมดเมื่อมีลูกค้า n คนอยู่ในร้านอาหาร เราควรสังเกตว่า k_n จะน้อยกว่าหรือเท่ากับ n เสมอ และโดยเฉลี่ยจะอยู่ที่ประมาณ . สุดท้ายเราควรสังเกตว่าความน่าจะเป็นของการจัดโต๊ะ ไม่แปรผันต่อการเรียงสับเปลี่ยน ดังนั้น z_i สามารถแลกเปลี่ยนได้ซึ่งหมายถึงโต๊ะที่มีขนาดเท่ากันของลูกค้ามีความน่าจะเป็นเท่ากัน

กระบวนการร้านอาหารจีนมีความเชื่อมโยงอย่างมากกับโครงการ Pólya urn และ Dirichlet Process CRP เป็นวิธีการระบุ a การกระจายผ่านพาร์ติชั่น (การกำหนดตาราง) ของ n คะแนนและสามารถใช้เป็นก่อนหน้าในช่องว่างของตัวแปรแฝง z_i ที่ กำหนดงานคลัสเตอร์. CRP เทียบเท่ากับโครงร่างโกศของ Pólya โดยมีความแตกต่างเพียงอย่างเดียวคือไม่ได้กำหนดพารามิเตอร์ให้กับแต่ละตาราง/คลัสเตอร์ ไป จาก CRP สู่โครงการโกศของ Polya เราวาด สำหรับทุกตาราง k=1,2… จากนั้นสำหรับทุก x_i ซึ่งจัดกลุ่มเป็นตาราง z_i มอบหมายก . กล่าวอีกนัยหนึ่งกำหนดให้กับ x . ใหม่_i พารามิเตอร์ θ ของตาราง ในที่สุดตั้งแต่ เราไม่สามารถมอบหมาย จากจุดเริ่มต้น θ ถึงตารางอนันต์ เราสามารถกำหนด θ ใหม่ทุกครั้งที่มีคนนั่งบนโต๊ะใหม่ จากทั้งหมดที่กล่าวมา CRP สามารถช่วยให้เราสร้างอัลกอริธึมที่มีประสิทธิภาพในการคำนวณเพื่อดำเนินการวิเคราะห์คลัสเตอร์บนชุดข้อมูล

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

ฉันหวังว่าคุณจะพบว่าโพสต์นี้น่าสนใจ หากใช่ โปรดสละเวลาสักครู่เพื่อแชร์บน Facebook และ Twitter 🙂