Dirichlet Process และ Hierarchical Dirichlet Process (Chinese Restaurant Process/Franchise)
level: บัณฑิตศึกษา ตัวเนื้อหาก็เลขระดับปอโทขึ้นไปอยู่แล้วนะอันนี้ Stochastic Processes
Dirichlet Process เป็น stochastic process ประเภท discrete เป็นโมเดลทางคณิตศาสตร์อันนึง (จริงๆเป็นโมเดลเลขแบบ HMMs, Gaussian Process, Random Walk, Wiener Process, etc. อ่ะแหละ) โดยอาจารย์ Yee Whye Teh, University College London (และคณะ) และทุกวันนี้อยู่ Oxford เป็น advisee ของอาจารย์ Geoff Hinton อีกที บางคนอาจเคยเห็นชื่อคุ้นๆตามเปเปอร์ Deep Learning โดย อาจารย์ Yee Whye Teh ชาวมาเลเซียนี่แหละ จบปริญญาและบัณฑิตแคนาดา เคย postdoc Berkeley และ NUS ทุนลีกวนยู เปเปอร์ Deep Belief Networks ก็คนนี้ ทุกวันนี้อยู่ในเครือข่ายราชบัณฑิต Royal society ของ UK มีคนไทยเป็นลูกศิษย์คืออาจารย์ไกรกมล หมื่นเดชที่อยู่เยอรมัน สมัยเรียนโท ที่จบตรี SIIT โปรเจคกับอาจารย์ชลวิช นัทธีมั้งครับ (อาจารย์ชลวิชเป็นกรรมการสอบปอโทผมด้วย สมัยปอโทที่จุฬา นานมากละ)
Dirichlet process เป็น discrete-time stochastic processes ที่ realization หรือ observable values เป็น probabilistic distributions และแจกแจงแบบ Dirichlet ใน non-parametric Bayesian statistics หลายครั้งใช้ Dirichlet process โมเดล prior ของการแจกแจงอื่นๆที่ให้ผลเป็น samples โดยสามารถสร้างโมเดลที่เป็น “infinite” models ได้ด้วย Dirichlet distribution ถ้าเคยอ่านเปเปอร์ชื่อแบบนี้ส่วนมากใช้อันนี้ทำอะไรซักอย่างเช่นจำนวน latent variables หรือ hidden layer -> inf (infinite HMM เป็นต้น) ลักษณะ Dirichlet Process ก็เหมือน graphical model ที่มีโมเดลกับ inference แต่พวกนี้จะมี Schema หรือ metaphor ด้วย (HMMs ก็น่าจะมีนะ แต่ไม่เห็นรู้เลย)
ในบทความ Dirichlet process [3] มีเขียน intuition ง่ายๆที่ว่า Dirichlet process เป็น infinite generalization ของ Dirichlet distribution ไว้ดังภาพต่อไปนี้ว่า สมมติ Bayesian mixture model มี K components: pi เป็น mixing proportions, alpha เป็น pseudo count hyper parameter ของ Dirichlet prior, H เป็น prior distribution over theta_k^star, F เป็น component distribution parametrized by theta, z_i เป็น latent variables, x_i เป็น observations/data เค้ากล่าวว่า สำหรับค่า K มากๆ เนื่องจากวิธีที่ใช้ Dirichlet prior กับ pi จำนวน component ที่ต้องใช้จะไม่ขึ้นกับ K และจะเป็น O(alpha log n) แทน เมื่อ n คือจำนวนข้อมูล ก็จะได้ว่า mixture model แบบนี้ well-defined แม้ K-inf ก็ติ๊งต่างว่าจริงไปก่อนเพราะ it can be shown that ตามอ้างอิง [5, 6] ที่เป็นเปเปอร์ infinite Gaussian mixture model เค้าว่าเป็นเปเอร์แรกๆที่นำเสนอวิธีที่จัดการกับจำนวน mixture component ที่เหมาะสมที่สุดในปัญหาพวกนี้ โดยจำนวน mixture เพิ่มขึ้นได้ตาม n โดย DP เมื่อ K->inf นั้น จะได้ของความน่าจะเป็นสุ่มแบบดิสครีตจะได้มาเป็นสูตรผลรวมของผลคูณสองตัวแปรสูตรนึงชิวๆ โดยตัวแปรนึง เดลต้า จะเป็น point mass ที่จุด theta ก็มีย่อหน้าโดยย่อตรงนี้ จริงๆควรเขียนแบบ [1] หรือ [4] ว่าให้ draw ตัวแปรสุ่ม G จาก Dirichlet process จะได้ G ~ DP(alpha0, G0) หรือ G ~ DP(alpha, H)แล้ว G = sum ก้อนเดียวกันกับในภาพต่อไปนี้ด้วยความน่าจะเป็น 1 เมื่อจำนวน components -> inf พจน์ข้างซ้ายของผลคูณเป็น stick breaking weight โดย [1] [4] [3] ใช้ notations คนละสัญลักษณ์กัน ในที่นี้เป็น pi อันอื่นเป็น beta แต่เรียงพจน์แบบเดียวกัน ยังดี กล่าว(บ่น)คือใน [1] หรือ [4] ตามคหสตรู้สึกว่าเขียน intuitions รึเปล่าไม่รู้ เห็นแต่ motivations ใน intro section เป็นหน้าหรือ column ตามแต่เวอร์ชั่นที่อ่าน เขียนอะไรไม่รู้ “sharing statistical strength” “multi-task learning” แล้วก็บรรยาย clustering โดยส่วนตัวคิดว่า [3] เขียนดีกว่า
ต่อมา [3] จะเขียนเยอะกว่าหน่อย เช่น จะมีว่าจาก Dirichlet กับ multinomial เป็น conjugate กัน posterior จะได้รูปสวยๆบวกตัว likelihood เข้าไปใส่ prior ได้เลย ตามนี้ แล้ว posterior ก็จะเป็น weighted averaged ใช้ alpha บวกๆเข้าไป พวกนี้เขียนให้ด้วยใน [3] ที่เป็นบทความสารานุกรมการเรียนรู้ของเครื่อง อ่านง่ายสบายดีครับ ใน [1] กับ [4] ที่เป็นเปเปอร์ NeurIPS กับวารสาร ไม่มีอ่ะนะ จะขึ้น HDP กับ CRP/CRF เลย ท่าทาง page limit ไปรวมๆ posterior กับ polya urn schema ไม่เขียน proof ของ schema ด้วย ตรง posterior นี้มีประโยชน์มาก เพราะจะกลายเป็นบวกๆหรือ weighted averaged เต็มไปหมด
ต่อมาก็ Blackwell-MacQueen urn scheme หรือ Polya urn scheme เป็น metaphor ของ DP ที่ว่า theta_i ~ G เป็นสีลูกบอลที่หยิบจากโถ โดยมีโถหยิบจาก H แบบคล้าย HMM แต่จะเริ่มจาก 0 คือโถไม่มีบอล แล้วด้วยความน่าจะเป็น H ก็ทาสีบอลแล้วใส่ในโถ ต่อมาก็จะทำแบบนี้อีก แต่จะมีทางเลือกที่สเต็ป n+1 คือ 1) เลือกสีใหม่แล้วทาสีบอลแล้วใส่โถ 2) จะหยิบบอลออกจากโถได้แล้วทาสีที่เลือกทับไป เค้าใช้ de Finetti’s theorem เปลี่ยนสมการที่ว่ามา จัดรูปในฟอร์มสมการ (9) เหมือน pmf ทั่วๆไป พิสูจน์ existence equivalent ของ schema นี้กับ DP เกี่ยวกับตรงนี้ ใน [4] อยู่ section 3.2
อ่ะทีนี้ก็ได้ DP ละ stick-breaking ของ DP จะเป็นดังต่อไปนี้ โดยใช้ pi หรือ beta [1, 4] เริ่มว่าเรามีไม้ไผ่ขนาด 1 หักไม่ไผ่ที่ beta_1 ขนาดไม้ไผ่เป็น pi_1 เก็บอันนี้ไว้ หักไม่ไผ่ที่เหลือไปเรื่อยๆ การแจกแจงบนความยาวกระบวนการหักไม้ไผ่ pi ~ GEM(alpha) ทำไมใช้ GEM โดยเป็นชื่อคนสามคน Griffiths Engen และ McClosky ตรงนี้จะเขียนงงงงนิดนึงว่า อ้าวหักไม่ไผ่เกี่ยวไรกับ DP สมการ G=sum อะไรนี่ มีคนพิสูจน์ในปี 1994 คือคุณ Sethuraman พิสูจน์อยู่ในนั้น เอวัง บอกว่า G นี้ คือ DP(alpha, H) แล้วมันเป็น mixture model DPMM ด้วยหรือ? สมควรที่งง เพราะไม่ได้เขียน ติ๊งต่างว่าจริงอืมๆต่อไป
Chinese Restaurant Process เป็นอีก metaphor ของ Dirichlet process โดยคล้ายๆ stick breaking หรือ Blackwell-MacQueen urn scheme แต่เป็นโต๊ะจีนแทน แต่ละโต๊ะมีเก้าอี้ไม่จำกัด เริ่มมามีโต๊ะเดียว ลูกค้าก็ไปนั่ง แต่สเต็ป n+1 ลูกค้าจะเลือกว่านั่งตรงโต๊ะที่มีคนอยู่แล้ว กับนั่งโต๊ะใหม่ โดยการเลือกเป็นไปตามความน่าจะเป็นที่ parametrized ตามภาพ
HDP คือเอา Dirichlet Process ตัวนึงมาเป็น prior ของ H หรือ G0 ใน DP จะกลายเป็นมี G0 อันใหม่เป็น top layer แล้วตัวที่เป็น DP เดิม จะเป็น G_j แทน คือ G1,G2|G0 ~ DP(alpha, G0) เป็นต้น ก็จะได้เป็น nested model ที่ทรงพลังอันใหม่ออกมา แนวคิดคือง่ายเลย สมการดังภาพ เพิ่มความลึกของ hierarchy ได้ด้วยการซ้อนๆๆๆทับๆๆๆไปเรื่อยๆเหมือน Deep Belief Network/Restricted Boltzmann Machine แต่ไม่ค่อยมีคนทำกัน
Stick breaking ก็มีไม้ใหญ่ไม้รองลงมาตามนั้น
ตัว metaphor ของ HDP เช่นแบบ CRP ก็จะกลายเป็น CRF (ที่ไม่ใช่ Conditional Random Field) คือจากร้านเดียวโต๊ะจีนหลายโต๊ะ จะกลายเป็นแฟรนไชส์ เลือกร้านก่อนเป็นสเต็ปก่อนโดยมี schema แบบเดียวกับโต๊ะ ดังภาพ
คราวนี้ก็ที่สำคัญละคือ inference ยังไง
จริงๆพวกนี้สำคัญที่เอามาเป็นโค้ดยังไง ตัวอย่างโค้ดเช่น https://github.com/morrisgreenberg/hdp-py เค้าน่าจะ implement ง่ายๆแบบใช้ scipy ได้นะ เราๆควรลองทำดู แบบใช้ง่ายมีใน gensim https://radimrehurek.com/gensim/models/hdpmodel.html สามารถแกะหรือ reimplement ได้ด้วย เค้า open source https://github.com/piskvorky/gensim/blob/develop/gensim/models/hdpmodel.py อันอื่นๆเช่นแบบใช้ C++ หรือจาวาก็ตาม awesome list มี https://github.com/jonaschn/awesome-topic-models?tab=readme-ov-file#hierarchical-dirichlet-process-hdp-page_facing_up
ตัวอย่างง่ายๆรัน topic model ด้วย hdp ใช้ gensim พล๊อต t-sne น่าเอาไปสอนในห้องแล้วพล๊อต umap เพิ่มไรงี้ https://github.com/ruanchaves/hdp jupyter notebook: https://github.com/ruanchaves/hdp/blob/master/hdpclusters.ipynb
การทดลอง ดูทำ topic model ดังภาพ ส่วน character-based model section Alice in Wonderland ไปอ่านเอาเอง ใครทำอะไรขายก็ปล่อยเค้าไป อย่าไปบถุลลี่เค้าลบหลู่เมพจริมๆปายกินยารักชีวิตนินึง เด็กเกรียนบางคนหลายปีก่อนเปนด๊อกกันไปแล้วส่วนทุกวันนี้เดกกุเรียนทีละตัวหนึ่งๆยังไม่ด๊อกก็กำลังจะเป็นไปในสามโลก เปเปอร์ช่องโหว่เยอะแยะเลยก็จบ ให้ อนุญาต พิสูดดดดมาแย้ว ยังไงมะรุ
ถามว่าที่เพ้อๆมาเนี่ยเอามาจากไหน อ่านเองรึเปล่า? คือเรียนมาตอนเป็น visitor ที่ UMD มกราถึงกรกฎา 2013 จ้ะ (จริงๆก็ควรอ่านเองได้นะ ถ้าแน่น Stochastic processes) ครูไล่เปเปอร์ [4] ให้ดูในคลาส https://web.archive.org/web/20201013015811/https://sites.google.com/site/umdnpbayes/reading-list แล้วก็ไปอ่านทวน เดี๋ยวมี indian buffet process (IBP) อีก เลยมาโน้ตทวนไว้แถวนี้ จริงๆตอนนั้นที่ไปต่อเป็น grad student เทอมถัดไป สิงหา-ธันวา 2013 ในคลาส computational linguistics 1 มี bonus assignment Pitman-Yor language model ด้วย เราทำได้คนเดียวในห้องเลย 55 จบคลาสได้ A+ เกือบเต็ม สงสัยถามอาจารย์ Jordan Boyd-Graber หรือ TA ตอนนั้นที่ตอนนี้เป็นอาจารย์แล้วคือ อาจารย์ Mohit Iyyer กับ อาจารย์ Alvin Grissom ได้ จริงๆก็เป็นวิชาที่เรียนมาหลายรอบกับหลายสถาบันอ่ะนะ ทั้ง Coursera หรือสมัยอยู่ TokyoTech ไปหามเหสี 55 (ประโยคตัวอย่างตัดคำไทย ที่ใครๆก็สอน รู้สึกมาจาก nectec ใช้ HMMs หรือ CRF สมัยนั้น เค้าชอบสอน tagging หรือ tasks พื้นๆ NLP กัน รันง่าวๆก็ 9x% ประมาณ เกิน 95 ด้วยบางอัน เห็นว่ามีคนบอกว่า ส่วนมากจุดข้อมูลบางอันไม่ได้เทรน สำหรับโมเดลพวกนี้ กล่าวคือตัว valid หรือ test set ไม่ได้สร้างมาดีแบบทดสอบกฏการผสมคำและความหมายครบ อย่างน้อยควรครอบคลุมในพจนานุกรมภาษานั้นๆ ปกติแบ่งชุดฝึกกับทดสอนมักทำ random split เอา ตลกดี ไม่ stratified ไม่มีการเก็บข้อมูลแบ่งตามกฏเกณฑ์ทางภาษาศาสตร์ บางทีบางอันบางภาษาเป็นแบบนี้จริงๆนะ เป็นมายี่สิบสามสิบปีแล้ว ทำต่อๆกันมา ถ้ามีสติฉุกคิดจะทราบ เหมือนเค้าไม่คิดมากกันจนกระทั่งเป็นเชิงพาณิชย์แพร่หลายเมื่อไม่นานมานี้ แล้วก็แบบตั้งแต่ตอนเรียนในห้องที่มักไม่สอนตามมหาลัยบางแห่ง ต้องทำลับๆโปรเจคกับครู สนใจต้องทำกับผมนะไรงี้อีก ตลกดีอีกอัน ขณะที่หลายที่สอนในห้องบางทีมีการบ้านทำแปปเดียวเสร็จ และก็บางทีถ้าดูตอนโมเดลเทรนเลือกจุดข้อมูลในชุดฝึกที่โมเดลพยากรณ์ถูกและผ่านไปมาบางอัน โมเดลไม่ได้พยากรณ์จากการเรียนรู้ภาษา แต่เป็นพวก surface regularities ดูจากทวีต Andrej Karpathy วันสองวันก่อนได้ เป็นต้น คือเท่าที่ผมดูหลังสุดสามสี่ปีก่อน ก็ไม่ใช่ character-based models หรือ LLMs ใดๆอ่ะนะ ไม่ได้วัดเป็น perplexity เป็น accuracy มั้ง แต่อวยและใช้กันทางพาณิชย์อุตสาหกรรมกันแล้ว ประสิทธิภาพต่างจากการันตีในระบบภาษาอื่นที่เค้าใช้กัน คหสต)
References
[1] Teh, Yee, et al. “Sharing clusters among related groups: Hierarchical Dirichlet processes.” Advances in neural information processing systems 17 (2004). [PDF]
[2] Blunsom, Phil, et al. “A note on the implementation of hierarchical Dirichlet processes.” Proceedings of the ACL-IJCNLP 2009 Conference Short Papers. 2009. [PDF]
[3] Teh, Yee Whye. “Dirichlet Process.” Encyclopedia of machine learning 1063 (2010): 280–287. [PDF]
[4] Teh, Yee Whye, et al. “Hierarchical Dirichlet Processes.” Journal of the American Statistical Association 101 (2006): 1566–1581. [PDF] [PDF] หรืออันนี้ด้วย Teh, Blei, Beal, and Jordan (2006). Hierarchical Dirichlet processes. Journal of Machine Learning Research.
