فرآیند دیریکله فرآیند رستوران چینی و سایر نمایندگی ها

• ممکن است 20، 2014
• واسیلیس ورینیوتس
• . بدون نظر

این مقاله سومین قسمت از مجموعه خوشه‌بندی با مدل‌های مخلوط فرآیند دیریکله است. دفعه قبل مدل مخلوط محدود را بر اساس توزیع دیریکله تعریف کردیم و سؤالاتی در مورد اینکه چگونه می توانیم این مدل خاص را نامحدود کنیم مطرح کردیم. ما به طور خلاصه ایده گرفتن حد مدل را در زمانی که k تعداد خوشه ها به بی نهایت میل می کند مورد بحث قرار دادیم، اما همانطور که تاکید کردیم وجود چنین جسمی بی اهمیت نیست (به عبارت دیگر، چگونه می توانیم حد یک مدل را در نظر بگیریم. ”؟). به عنوان یادآوری، دلیل اینکه می‌خواهیم k را بی‌نهایت در نظر بگیریم این است که به این ترتیب یک مدل ناپارامتریک خواهیم داشت که نیازی به تعریف تعداد کل خوشه‌ها در داده‌ها ندارد.

به روز رسانی: چارچوب یادگیری ماشین Datumbox اکنون منبع باز و رایگان است دانلود. برای مشاهده اجرای مدل‌های مخلوط فرآیند دیریکله در جاوا، بسته com.datumbox.framework.machinelearning.clustering را بررسی کنید.

اگرچه هدف ما ساخت مدلی است که قادر به انجام خوشه بندی بر روی مجموعه داده ها باشد، قبل از آن باید در مورد فرآیندهای دیریکله بحث کنیم. ما هم تعاریف دقیق ریاضی و هم توضیحات شهودی تر DP را ارائه خواهیم داد و راه های ساخت این فرآیند را مورد بحث قرار خواهیم داد. این ساختارها/بازنمایی‌ها را می‌توان راهی برای یافتن رخدادهای فرآیند دیریکله در «زندگی واقعی» دانست.

علیرغم این واقعیت که من سعی کردم گزارش تحقیق خود را به گونه‌ای تنظیم کنم که این پست‌های وبلاگ راحت‌تر دنبال شوند، هنوز مهم است که ابزارها و توزیع‌های ریاضی لازم را قبل از استفاده از مدل‌ها تعریف کنیم. مدل‌های فرآیند دیریکله موضوع تحقیقات فعال هستند، اما قبل از استفاده از آنها نیاز به درک خوبی از آمار و فرآیندهای تصادفی دارند. مشکل دیگر این است که همانطور که در این مقاله خواهیم دید، فرآیندهای دیریکله را می توان با روش های متعددی نشان داد/ ساخت. در نتیجه چندین مقاله آکادمیک از نمادها / قراردادهای کاملاً متفاوت استفاده می کنند و مسئله را از دیدگاه های مختلف بررسی می کنند. در این پست سعی می کنم تا حد امکان ساده آنها را توضیح دهم و از همان علامت گذاری استفاده کنم. امیدواریم با دو مقاله آتی که بر تعریف مدل‌های مخلوط فرآیند دیریکله و نحوه استفاده واقعی از آنها برای انجام تجزیه و تحلیل خوشه‌ای تمرکز دارند، همه چیز واضح‌تر شود.

1. تعریف فرآیند دیریکله

فرآیند دیریکله در فضای Θ یک فرآیند تصادفی است. این یک توزیع احتمال بر روی "توزیعات احتمال در فضای Θ" و الف است استخراج از آن یک توزیع گسسته است. به طور رسمی تر، توزیع دیریکله، توزیعی بر معیارهای احتمال است. آ اندازه گیری احتمال تابعی از زیر مجموعه های فضای Θ تا [0,1] است. G یک اندازه گیری احتمال تصادفی توزیع شده DP است که با نشان داده می شود ، اگر برای هر پارتیشن (A₁،…آ_n) فضای Θ داریم که .

شکل 1: حاشیه های روی پارتیشن های محدود دریکله توزیع شده اند.

DP دو پارامتر دارد: اولی توزیع پایه G است₀ که مانند یک وسیله عمل می کند . دومی پارامتر قدرت α است که کاملاً مثبت است و مانند واریانس معکوس عمل می کند . میزان تکرار مقادیر توزیع خروجی را تعیین می کند. هر چه مقدار a بیشتر باشد، تکرار کوچکتر است. هر چه مقدار کوچکتر باشد، تکرار مقادیر توزیع خروجی بیشتر است. در نهایت فضای Θ، فضای پارامتری است که DP را بر روی آن تعریف می کنیم. علاوه بر این، فضای Θ نیز فضای تعریف G است₀ که همان G.

ساده تر و بیشتر راه شهودی برای توضیح یک فرآیند دیریکله به شرح زیر است. فرض کنید فضای Θ داریم که می‌توان آن را به هر طریقی محدود تقسیم کرد (A₁،…،آ_n) و یک توزیع احتمال G که احتمالات را به آنها اختصاص می دهد. G یک توزیع احتمال خاص بر روی Θ است اما بسیاری دیگر وجود دارد. فرآیند دیریکله در Θ دقیقاً این را مدل می کند. این توزیع بر روی تمام توزیع های احتمال ممکن در فضای Θ است. فرآیند دیریکله با G پارامتر بندی می شود₀ تابع پایه و پارامتر غلظت α. می توان گفت که G بر اساس DP با پارامترهای α و G توزیع می شود₀ اگر توزیع مشترک احتمالاتی که G به تقسیمات Θ نسبت می دهد از توزیع دیریکله پیروی کند. از طرف دیگر می توان گفت که احتمالاتی که G به هر بخش متناهی Θ نسبت می دهد از توزیع دیریکله تبعیت می کند.

شکل 2: مدل گرافیکی فرآیند دیریکله

در نهایت در بالا ما می توانیم ببینیم مدل گرافیکی یک DP. باید توجه داشته باشیم که α یک فراپارامتر اسکالر است، G₀ توزیع پایه DP است، G توزیع تصادفی در فضای پارامتر Θ نمونه برداری شده از DP است که احتمالات را به پارامترها و θ اختصاص می دهد._i بردار پارامتری است که از توزیع G گرفته شده و عنصری از فضای Θ است.

2. فرآیندهای دیریکله خلفی

فرآیندهای دیریکله پسین توسط مورد بحث قرار گرفت فرگوسن. ما با ترسیم یک اندازه گیری احتمال تصادفی G از یک فرآیند دیریکله شروع می کنیم. . از آنجایی که G یک توزیع احتمال بر روی Θ است، می‌توانیم از این توزیع نمونه‌برداری کنیم و نمونه‌های مستقل توزیع‌شده یکسان θ را ترسیم کنیم.₁,…, θ_n ~ G. از آنجایی که برداشت‌های حاصل از فرآیند دیریکله توزیع‌های گسسته هستند، می‌توانیم نشان دهیم جایی که یک نماد کوتاه برای است که یک تابع دلتا است که 1 اگر را می گیرد و 0 در جای دیگر. یک اثر جالب این است که از آنجایی که G به این شکل تعریف می شود، احتمال مثبت وجود دارد که نمونه های مختلف مقدار مشابهی داشته باشند. . همانطور که در ادامه خواهیم دید، این یک اثر خوشه‌بندی ایجاد می‌کند که می‌تواند برای انجام تحلیل خوشه‌ای روی مجموعه‌های داده استفاده شود.

با استفاده از تعاریف و مشاهدات فوق، می‌خواهیم با توجه به نمونه‌های θ، قسمت خلفی فرآیند دیریکله را تخمین بزنیم. با این حال از آنجایی که ما می دانیم و با استفاده از قواعد بیز و مزدوج بین دیریکله و چندجمله‌ای، آن را داریم و .

معادله 1: فرآیند دیریکله خلفی

این ویژگی بسیار مهم است و توسط نمایندگی های مختلف DP استفاده می شود.

3. نمایندگی های فرآیند دیریکله

در بخش‌های قبل، فرآیند دیریکله را تعریف و مدل نظری آن را ارائه کردیم. یک سوال مهم که باید به آن پاسخ دهیم این است که چگونه می دانیم که چنین شیئی وجود دارد و چگونه می توانیم ساختن و نشان دادن فرآیند دیریکله

اولین نشانه های وجود توسط فرگوسن که از قضیه قوام کولموگروف استفاده کرد، فرآیند دیریکله را تعریف کرد و فرآیند دیریکله خلفی را توصیف کرد. در ادامه تحقیقات خود، بلک ول و مک کوئین از قضیه دی فینتی برای اثبات وجود چنین اندازه‌گیری احتمال تصادفی استفاده کرد و طرح urn بلک‌ول-مک کوئین را معرفی کرد که ویژگی‌های فرآیند دیریکله را برآورده می‌کند. در سال 1994 ستورامان با معرفی ساختار Stick-breaking یک راه ساده و مستقیم اضافی برای ساخت یک DP ارائه کرد. در نهایت یک نمایندگی دیگر توسط آلدوس که فرآیند رستوران چینی را به عنوان روشی مؤثر برای ساختن فرآیند دیریکله معرفی کرد.

بازنمایی های مختلف فرآیند دیریکله از نظر ریاضی معادل هستند، اما فرمول بندی آنها متفاوت است زیرا آنها مسئله را از دیدگاه های مختلف بررسی می کنند. در زیر رایج‌ترین نمایش‌های موجود در ادبیات را ارائه می‌کنیم و بر فرآیند رستوران چینی تمرکز می‌کنیم که یک روش ساده و محاسباتی کارآمد برای ساخت الگوریتم‌های استنتاج برای فرآیند دیریکله ارائه می‌دهد.

3.1 طرح urn Blackwell-MacQueen

طرح urn Blackwell-MacQueen را می توان برای نشان دادن فرآیند دیریکله استفاده کرد و توسط آن معرفی شد. بلک ول و مک کوئین. این بر اساس طرح urn Pólya است که می تواند به عنوان مدل مخالف نمونه برداری بدون جایگزینی دیده شود. در طرح urn Pólya ما فرض می کنیم که یک urn غیر شفاف داریم که حاوی توپ های رنگی است و به طور تصادفی توپ ها را می کشیم. وقتی توپی را می کشیم، رنگ آن را رعایت می کنیم، آن را دوباره در ظرف می گذاریم و یک توپ اضافه به همان رنگ اضافه می کنیم. طرح مشابهی توسط بلک ول و مک کوئین برای ساختن فرآیند دیریکله استفاده می شود.

این طرح دنباله ای از θ را تولید می کند₁,θ₂،… با احتمالات مشروط . در این طرح فرض می کنیم که G₀ توزیع روی رنگ ها و هر θ است_n نشان دهنده رنگ توپی است که در کوزه قرار می گیرد. در الگوریتم به شرح زیر است:

· با یک کوزه خالی شروع می کنیم.

· با احتمال متناسب با α می کشیم و یک گلوله به این رنگ را در قوطی اضافه می کنیم.

· با احتمال متناسب با n-1، یک توپ تصادفی از داخل سطل می کشیم، رنگ آن را مشاهده می کنیم، آن را به داخل سطل برمی گردانیم و یک توپ اضافی به همان رنگ در سطل اضافه می کنیم.

قبلاً ما با یک فرآیند دیریکله شروع کردیم و طرح Blackwell-MacQueen را استخراج کردیم. حالا بیایید برعکس از طرح Blackwell-MacQueen شروع کنیم و DP را استخراج کنیم. از آنجایی که θ_i به صورت iid از G ترسیم شده اند، توزیع مشترک آنها نسبت به هر جایگشت متناهی ثابت خواهد بود و بنابراین آنها قابل مبادله هستند. در نتیجه با استفاده از قضیه دی فینتی، دریافتیم که باید توزیعی بر روی معیارها وجود داشته باشد تا آنها را iid کند و این توزیع فرآیند دیریکله است. در نتیجه ما ثابت می کنیم که طرح urn Blackwell-MacQueen نمایشی از DP است و راهی مشخص برای ساخت آن به ما می دهد. همانطور که بعدا خواهیم دید، این طرح از نظر ریاضی معادل فرآیند رستوران چینی است.

3.2 ساخت و ساز چوب شکن

ساخت و ساز چوب شکن یک راه جایگزین برای نشان دادن فرآیند دیریکله است که توسط آن معرفی شد ستورامان. این یک راه سازنده برای تشکیل است توزیع و استفاده می کند به دنبال قیاس: فرض می کنیم چوبی به طول 1 داریم، آن را در موقعیت β می شکنیم₁ و π را اختصاص می دهیم₁ به اندازه طول قسمتی از چوب که شکستیم. برای بدست آوردن π همین روند را تکرار می کنیم₂، π₃،… و غیره؛ با توجه به نحوه تعریف این طرح می توانیم بی نهایت به انجام آن ادامه دهیم.

بر اساس موارد فوق، π_k را می توان به عنوان مدل سازی کرد ، که در آن در حالی که مانند طرح های قبلی، θ به طور مستقیم توسط توزیع پایه نمونه برداری می شود . در نتیجه توزیع G را می توان به صورت مجموع توابع دلتا که با π وزن دارند نوشت_k احتمالات که برابر است با . بنابراین ساختار چوب شکن راهی ساده و شهودی برای ساختن فرآیند دیریکله به ما می دهد.

3.3 فرآیند رستوران چینی

فرآیند رستوران چینی که توسط آلدوس، یکی دیگر از راه های موثر برای نشان دادن فرآیند دیریکله است و می توان آن را مستقیماً به طرح urn Blackwell-MacQueen مرتبط کرد. این طرح از به دنبال قیاس: فرض می کنیم یک رستوران چینی با بی نهایت میز وجود دارد. هنگامی که مشتریان وارد رستوران می شوند، به طور تصادفی روی هر یک از میزهای اشغال شده می نشینند یا اینکه روی اولین میز خالی موجود می نشینند.

CRP توزیعی را در فضای پارتیشن های اعداد صحیح مثبت تعریف می کند. با ترسیم θ شروع می کنیم₁،…θ_n از طرح urn Blackwell-MacQueen. همانطور که در بخش‌های قبلی بحث کردیم، انتظار داریم یک اثر خوشه‌بندی را ببینیم و بنابراین تعداد کل مقادیر θ منحصر به فرد k به طور قابل‌توجهی کمتر از n خواهد بود. بنابراین این پارتیشنی از مجموعه {1,2,…,n} را در k خوشه تعریف می کند. در نتیجه ترسیم از طرح urn Blackwell-MacQueen یک پارتیشن تصادفی از مجموعه {1,2,…,n} را القا می کند. فرآیند رستوران چینی به همین دلیل است توزیع بر روی پارتیشن ها. الگوریتم به شرح زیر است:

· با یک رستوران خالی شروع می کنیم.

· 1^st مشتری همیشه روی 1 می نشیند^st جدول

· n+1^th مشتری 2 گزینه دارد:

o به احتمال زیاد روی اولین میز خالی بنشینید

o به احتمال زیاد روی هر یک از میزهای اشغال شده کیلویی بنشینید
جایی که تعداد افرادی است که روی آن میز نشسته اند

جایی که α مقدار پراکندگی DP و n تعداد کل مشتریان در رستوران در یک زمان معین است. متغیر پنهان z_i شماره جدول i را ذخیره می کند^th مشتری و مقادیر از 1 تا k را می گیرد_n جایی که k_n تعداد کل میزهای اشغال شده زمانی است که n مشتری در رستوران هستند. باید توجه داشته باشیم که k_n همیشه کوچکتر یا مساوی n خواهد بود و به طور متوسط ​​حدود است . در نهایت باید توجه داشت که احتمال چیدمان میز نسبت به جایگشت ها ثابت است. بنابراین z_i قابل مبادله است که به این معنی است که جداول با اندازه مشتریان مشابه احتمال یکسانی دارند.

فرآیند رستوران چینی به شدت به طرح urn Pólya و فرآیند دیریکله متصل است. CRP راهی برای تعیین a توزیع بر روی پارتیشن ها (تخصیص جدول) از n نقطه و می تواند به عنوان پیشین در فضای متغیر پنهان z استفاده شود._i که تکالیف خوشه را تعیین می کند. CRP معادل طرح urn Pólya است تنها با این تفاوت که پارامترهایی را به هر جدول/خوشه اختصاص نمی دهد. رفتن از CRP تا طرح urn Pólya می کشیم برای همه جداول k=1,2… و سپس برای هر x_i که در جدول z گروه بندی می شود_i اختصاص دادن الف . به عبارت دیگر به x جدید اختصاص دهید_i پارامتر θ جدول سرانجام از آن زمان نمی توانیم تعیین کنیم θ را از ابتدا به جداول بی‌نهایت، می‌توانیم هر بار که شخصی روی میز جدیدی می‌نشیند، یک θ جدید اختصاص دهیم. با توجه به تمام موارد فوق، CRP می تواند به ما در ساخت الگوریتم های محاسباتی کارآمد برای انجام تجزیه و تحلیل خوشه ای در مجموعه داده ها کمک کند.

در این پست، فرآیند دیریکله و چندین راه برای ساخت آن را مورد بحث قرار دادیم. در مقاله بعدی از ایده های فوق استفاده خواهیم کرد. ما مدل مخلوط فرآیند دیریکله را معرفی می‌کنیم و از نمایندگی رستوران چینی برای ساختن فرآیند دیریکله و پیش‌فرض آنالیز خوشه‌ای استفاده می‌کنیم. اگر چند نکته را از دست دادید نگران نباشید زیرا با دو مقاله بعدی همه چیز روشن تر می شود.

امیدوارم این پست برای شما جالب بوده باشد. اگر این کار را کردید، چند لحظه وقت بگذارید و آن را در فیس بوک و توییتر به اشتراک بگذارید. 🙂