The Dirichlet Process the Chinese Restaurant Process dan representasi lainnya

• 20 Mei 2014
• Vasilis Vriniotis
• . Tidak ada komentar

Artikel ini adalah bagian ketiga dari seri Clustering dengan Model Campuran Proses Dirichlet. Sebelumnya kami mendefinisikan Model Campuran Hingga berdasarkan Distribusi Dirichlet dan kami mengajukan pertanyaan tentang bagaimana kami dapat membuat model khusus ini tak terbatas. Kami secara singkat membahas gagasan mengambil batas model ketika jumlah k cluster cenderung tak terhingga tetapi seperti yang kami tekankan, keberadaan objek semacam itu tidak sepele (dengan kata lain, bagaimana kita sebenarnya "mengambil batas model "?). Sebagai pengingat, alasan mengapa kita ingin mengambil make k infinite adalah karena dengan cara ini kita akan memiliki model non-parametrik yang tidak mengharuskan kita untuk menentukan jumlah cluster dalam data.

Pembaruan: Kerangka Pembelajaran Mesin Datumbox sekarang open-source dan bebas untuk Download. Lihatlah paket com.datumbox.framework.machinelearning.clustering untuk melihat implementasi Model Campuranch Prosesch Dirichlet di Jawa.

Padahal target kita adalah membangun model yang mampu melakukan clustering pada dataset, sebelumnya kita harus membahas tentang Dirichlet Processes. Kami akan memberikan definisi matematika yang ketat dan penjelasan DP yang lebih intuitif dan kami akan membahas cara untuk membangun prosesnya. Konstruksi / representasi tersebut dapat dilihat sebagai cara untuk menemukan kemunculan Proses Dirichlet dalam “kehidupan nyata”.

Terlepas dari kenyataan bahwa saya mencoba menyesuaikan laporan penelitian saya sedemikian rupa sehingga posting blog ini lebih mudah diikuti, tetap penting untuk menentukan alat dan distribusi matematika yang diperlukan sebelum kita mulai menggunakan model. Model Proses Dirichlet adalah topik penelitian aktif, tetapi mereka membutuhkan pemahaman yang baik tentang Statistik dan Proses Stochastic sebelum menggunakannya. Masalah lain adalah seperti yang akan kita lihat di artikel ini, Proses Dirichlet dapat direpresentasikan / dibangun dengan berbagai cara. Akibatnya beberapa makalah akademis menggunakan notasi / konvensi yang sama sekali berbeda dan memeriksa masalah dari sudut pandang yang berbeda. Pada postingan kali ini saya mencoba menjelaskannya sesederhana mungkin dan menggunakan notasi yang sama. Mudah-mudahan semuanya akan menjadi lebih jelas dengan dua artikel mendatang yang fokus pada definisi Model Campuran Proses Dirichlet dan tentang bagaimana sebenarnya menggunakannya untuk melakukan analisis cluster.

1. Definisi Proses Dirichlet

Proses Dirichlet melalui ruang Θ adalah proses stokastik. Ini adalah distribusi probabilitas atas “distribusi probabilitas di atas Θ ruang” dan a menarik darinya adalah distribusi diskrit. Lebih formal Distribusi Dirichlet adalah distribusi atas ukuran probabilitas. SEBUAH ukuran probabilitas adalah fungsi dari himpunan bagian ruang Θ hingga [0,1]. G adalah ukuran probabilitas acak terdistribusi DP, dilambangkan sebagai , jika untuk partisi apa pun (A₁,…SEBUAH_n) ruang Θ kita punya itu .

Gambar 1: Marginal pada partisi finit didistribusikan Dirichlet.

DP memiliki dua parameter: Yang pertama adalah distribusi basis G₀ yang berfungsi seperti sarana . Yang kedua adalah parameter kekuatan α yang sangat positif dan berfungsi seperti varian terbalik . Ini menentukan sejauh mana pengulangan nilai-nilai distribusi output. Semakin tinggi nilai a, semakin kecil pengulangannya; semakin kecil nilainya, semakin tinggi pengulangan nilai distribusi keluaran. Terakhir, ruang is adalah ruang parameter tempat kita mendefinisikan DP. Selain itu, ruang Θ juga merupakan ruang definisi G₀ yang sama dengan salah satu G.

Lebih sederhana dan lebih cara intuitif untuk menjelaskan Proses Dirichlet adalah sebagai berikut. Misalkan kita memiliki ruang Θ yang dapat dipartisi dengan cara apa pun (A₁,…,SEBUAH_n) dan distribusi probabilitas G yang memberikan probabilitas kepada mereka. G adalah distribusi probabilitas spesifik atas Θ tetapi ada banyak lainnya. Proses Dirichlet pada Θ memodelkan persis seperti ini; ini adalah distribusi atas semua kemungkinan distribusi probabilitas pada ruang Θ. Proses Dirichlet diparameterisasi dengan G₀ fungsi dasar dan parameter konsentrasi α. Kita dapat mengatakan bahwa G didistribusikan menurut DP dengan parameter α dan G.₀ jika distribusi bersama dari probabilitas yang diberikan G ke partisi Θ mengikuti Distribusi Dirichlet. Alternatifnya, kita dapat mengatakan bahwa probabilitas yang diberikan G ke partisi terbatas Θ mengikuti Distribusi Dirichlet.

Gambar 2: Model Grafis Proses Dirichlet

Akhirnya di atas kita bisa melihat file model grafis DP. Perlu dicatat bahwa α adalah hyperparameter skalar, G₀ adalah distribusi dasar DP, G distribusi acak atas Θ ruang parameter sampel dari DP yang memberikan probabilitas ke parameter dan θ_i adalah vektor parameter yang diambil dari distribusi G dan merupakan elemen ruang Θ.

2. Proses Posterior Dirichlet

Proses Posterior Dirichlet dibahas oleh Ferguson. Kita mulai dengan menggambar ukuran probabilitas acak G dari Proses Dirichlet, . Karena G adalah distribusi probabilitas atas Θ kita juga dapat mengambil sampel dari distribusi ini dan mengambil sampel terdistribusi identik independen θ₁,…, Θ_n ~ G. Karena penarikan dari Proses Dirichlet adalah distribusi diskrit, kami dapat mewakili dimana adalah notasi singkat untuk yang merupakan fungsi delta yang membutuhkan 1 if dan 0 di tempat lain. Efek yang menarik dari hal ini adalah karena G didefinisikan dengan cara ini, ada kemungkinan positif dari sampel yang berbeda memiliki nilai yang sama . Seperti yang akan kita lihat nanti, ini menciptakan efek pengelompokan yang dapat digunakan untuk melakukan Analisis Klaster pada kumpulan data.

Dengan menggunakan definisi dan observasi di atas kami ingin memperkirakan posterior Proses Dirichlet yang diberikan sampel θ. Namun demikian sejak kita tahu itu dan dengan menggunakan Aturan Bayes dan Konjugasi antara Dirichlet dan Multinomial kami memilikinya dan .

Persamaan 1: Proses Posterior Dirichlet

Properti ini sangat penting dan digunakan oleh berbagai representasi DP.

3. Representasi Proses Dirichlet

Pada segmen sebelumnya kami mendefinisikan Proses Dirichlet dan mempresentasikan model teoretisnya. Satu pertanyaan penting yang harus kita jawab adalah bagaimana kita tahu bahwa benda seperti itu ada dan bagaimana kita bisa membangun dan merepresentasikan Proses Dirichlet.

Indikasi pertama keberadaan disediakan oleh Ferguson yang menggunakan Teorema Konsistensi Kolmogorov, memberikan definisi Proses Dirichlet dan menjelaskan Proses Dirichlet Posterior. Melanjutkan penelitiannya, Blackwell dan MacQueen menggunakan Teorema de Finetti untuk membuktikan keberadaan ukuran probabilitas acak seperti itu dan memperkenalkan skema guci Blackwell-MacQueen yang memenuhi sifat Proses Dirichlet. Pada tahun 1994 Sethuraman memberikan cara tambahan yang sederhana dan langsung untuk membangun DP dengan memperkenalkan konstruksi pemecah Tongkat. Akhirnya representasi lain diberikan oleh Aldous yang memperkenalkan Proses Restoran Cina sebagai cara yang efektif untuk membangun Proses Dirichlet.

Berbagai Representasi dari Proses Dirichlet secara matematis setara tetapi formulasinya berbeda karena mereka memeriksa masalah dari sudut pandang yang berbeda. Di bawah ini kami menyajikan representasi paling umum yang ditemukan dalam literatur dan kami fokus pada Proses Restoran Cina yang menyediakan cara sederhana dan efisien secara komputasi untuk membangun algoritma inferensi untuk Proses Dirichlet.

3.1 Skema guci Blackwell-MacQueen

Skema guci Blackwell-MacQueen dapat digunakan untuk mewakili Proses Dirichlet dan diperkenalkan oleh Blackwell dan MacQueen. Ini didasarkan pada skema Pólya guci yang dapat dilihat sebagai model berlawanan dari pengambilan sampel tanpa penggantian. Dalam skema Pólya guci, kami berasumsi bahwa kami memiliki guci tidak transparan yang berisi bola berwarna dan kami menggambar bola secara acak. Saat kami menggambar bola, kami mengamati warnanya, kami memasukkannya kembali ke dalam guci dan kami menambahkan bola tambahan dengan warna yang sama. Skema serupa digunakan oleh Blackwell dan MacQueen untuk membangun Proses Dirichlet.

Skema ini menghasilkan urutan θ₁, θ₂,… Dengan probabilitas bersyarat . Dalam skema ini kami berasumsi bahwa G₀ adalah distribusi warna dan masing-masing θ_n mewakili warna bola yang ditempatkan di guci. Itu algoritma adalah sebagai berikut:

· Kami mulai dengan guci kosong.

· Dengan probabilitas sebanding α kami menggambar dan kami menambahkan bola warna ini ke dalam guci.

· Dengan probabilitas sebanding dengan n-1 kami menarik bola acak dari guci, kami mengamati warnanya, kami menempatkannya kembali ke guci dan kami menambahkan bola tambahan dengan warna yang sama di dalam guci.

Sebelumnya kami mulai dengan Proses Dirichlet dan menurunkan skema Blackwell-MacQueen. Sekarang mari kita mulai secara terbalik dari skema Blackwell-MacQueen dan mendapatkan DP. Sejak θ_i diambil dengan cara iid dari G, distribusi gabungannya tidak akan berubah ke permutasi terbatas dan dengan demikian dapat dipertukarkan. Akibatnya dengan menggunakan teorema de Finetti, kita memiliki bahwa harus ada distribusi ukuran untuk membuatnya iid dan distribusi ini adalah Proses Dirichlet. Hasilnya kami membuktikan bahwa skema guci Blackwell-MacQueen adalah representasi dari DP dan memberi kami cara konkret untuk membangunnya. Seperti yang akan kita lihat nanti, skema ini secara matematis setara dengan Proses Restoran Cina.

3.2 Konstruksi pemecah tongkat

Konstruksi pemecah tongkat adalah cara alternatif untuk merepresentasikan Proses Dirichlet yang diperkenalkan oleh Sethuraman. Ini adalah cara konstruktif untuk membentuk distribusi dan menggunakan analogi berikut: Kami berasumsi bahwa kami memiliki tongkat dengan panjang 1, kami mematahkannya pada posisi β₁ dan kami menetapkan π₁ sama dengan panjang bagian tongkat yang kita patahkan. Kami mengulangi proses yang sama untuk mendapatkan π₂,₃,… Dll; karena cara skema ini didefinisikan, kami dapat terus melakukannya berkali-kali.

Berdasarkan π di atas_k dapat dimodelkan sebagai , Di mana sedangkan seperti pada skema sebelumnya, θ diambil sampelnya langsung oleh distribusi Basis . Akibatnya distribusi G dapat ditulis sebagai penjumlahan dari fungsi delta yang berbobot π_k probabilitas yang sama dengan . Jadi konstruksi pemecah tongkat memberi kita cara sederhana dan intuitif untuk membangun Proses Dirichlet.

3.3 Proses Restoran Cina

Proses Restoran Cina, yang diperkenalkan oleh Aldous, adalah cara efektif lain untuk merepresentasikan Proses Dirichlet dan dapat langsung dihubungkan ke skema guci Blackwell-MacQueen. Skema ini menggunakan analogi berikut: Kami berasumsi bahwa ada restoran Cina dengan banyak meja yang tak terbatas. Saat pelanggan memasuki restoran, mereka duduk secara acak ke salah satu meja yang ditempati atau mereka memilih untuk duduk di meja kosong pertama yang tersedia.

CRP mendefinisikan distribusi pada ruang partisi dari bilangan bulat positif. Kami mulai dengan menggambar θ₁,… Θ_n dari skema guci Blackwell-MacQueen. Seperti yang kita bahas di segmen sebelumnya, kita berharap untuk melihat efek pengelompokan dan dengan demikian jumlah total nilai θ unik k akan jauh lebih kecil dari n. Jadi ini mendefinisikan partisi dari himpunan {1,2,…, n} dalam k cluster. Akibatnya, menggambar dari skema guci Blackwell-MacQueen menginduksi partisi acak dari himpunan {1,2,…, n}. Proses Restoran Cina adalah seperti ini distribusi atas partisi. Algoritmanya adalah sebagai berikut:

· Kami mulai dengan restoran kosong.

· The 1^st pelanggan selalu duduk di 1^st tabel

· N + 1^th pelanggan memiliki 2 pilihan:

o Duduklah di meja kosong pertama dengan probabilitas

o Duduklah di salah satu tabel yang ditempati dengan probabilitas
dimana adalah jumlah orang yang duduk di meja itu

Dimana α adalah nilai dispersi DP dan n adalah jumlah total pelanggan di restoran pada waktu tertentu. Variabel laten z_i menyimpan nomor tabel i^th pelanggan dan mengambil nilai dari 1 hingga k_n dimana k_n adalah jumlah total meja yang ditempati saat n pelanggan berada di restoran. Kita harus mencatat bahwa k_n akan selalu kurang atau sama dengan n dan rata-rata sekitar . Akhirnya kita harus mencatat bahwa kemungkinan pengaturan tabel tidak berbeda dengan permutasi. Jadi z_i dapat ditukar yang menyiratkan bahwa tabel dengan ukuran pelanggan yang sama memiliki probabilitas yang sama.

Proses Restoran Cina sangat terkait dengan skema Pólya guci dan Proses Dirichlet. CRP adalah cara untuk menentukan a distribusi atas partisi (tugas tabel) dari n poin dan dapat digunakan sebagai prior pada spasi variabel laten z_i yang menentukan tugas cluster. CRP setara dengan skema guci Pólya dengan hanya perbedaannya tidak menetapkan parameter ke setiap tabel / cluster. Untuk pergi dari CRP ke skema guci Pólya kami menggambar untuk semua tabel k = 1,2… dan kemudian untuk setiap x_i yang dikelompokkan ke tabel z_i menetapkan a . Dengan kata lain tetapkan ke x baru_i parameter θ dari tabel. Akhirnya sejak kami tidak dapat menetapkan θ ke tabel tak terbatas dari awal, kita bisa menetapkan θ baru setiap kali seseorang duduk di meja baru. Karena semua hal di atas, CRP dapat membantu kami membangun algoritme yang efisien secara komputasi untuk melakukan Analisis Klaster pada kumpulan data.

Dalam posting ini, kami membahas Proses Dirichlet dan beberapa cara untuk membangunnya. Kami akan menggunakan ide-ide di atas di artikel berikutnya. Kami akan memperkenalkan Model Campuran Proses Dirichlet dan kami akan menggunakan Representasi Restoran Cina untuk membangun Proses Dirichlet dan membentuk Analisis Klaster sebelumnya. Jika Anda melewatkan beberapa poin, jangan khawatir karena semuanya akan mulai menjadi lebih jelas dengan dua artikel berikutnya.

Saya harap Anda menemukan posting ini menarik. Jika ya, luangkan waktu sejenak untuk membagikannya di Facebook dan Twitter. 🙂