Model Campuran Proses Dirichlet

• Juni 23, 2014
• Vasilis Vriniotis
• . 2 Komentar

Entri blog ini adalah bagian keempat dari rangkaian pada Clustering dengan Model Campuran Proses Dirichlet. Dalam artikel sebelumnya kita membahas Model Campuran Dirichlet Hingga dan kita mengambil batas model mereka untuk cluster k tak terbatas yang membawa kita pada pengenalan Proses Dirichlet. Seperti yang kita lihat, target kita adalah membangun model campuran yang tidak mengharuskan kita menentukan jumlah k cluster / komponen dari awal. Setelah menyajikan representasi yang berbeda dari Proses Dirichlet, sekarang saatnya untuk benar-benar menggunakan DP untuk membangun Model Campuran tak terbatas yang memungkinkan kita melakukan pengelompokan. Sasaran dari artikel ini adalah untuk mendefinisikan Model Campuran Proses Dirichlet dan membahas penggunaan Proses Restoran Cina dan Sampling Gibbs. Jika Anda belum membaca posting sebelumnya, sangat disarankan untuk melakukannya karena topiknya agak teoretis dan memerlukan pemahaman yang baik tentang konstruksi model.

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.

1. Definisi Model Campuran Proses Dirichlet

Menggunakan Proses Dirichlet memungkinkan kita memiliki model campuran dengan komponen tak hingga yang dapat dianggap mengambil batas model hingga k hingga tak terhingga. Mari kita asumsikan bahwa kita memiliki model berikut:

Persamaan 1: Model Campuran Proses Dirichlet

Dimana G didefinisikan sebagai dan digunakan sebagai notasi singkat untuk yang merupakan fungsi delta yang membutuhkan 1 if dan 0 di tempat lain. The θ_i adalah parameter cluster yang diambil sampelnya dari G. Distribusi generatif F dikonfigurasi oleh parameter cluster θ_i dan digunakan untuk menghasilkan x_i observasi. Akhirnya kita bisa mendefinisikan distribusi Densitas yang merupakan distribusi campuran kami (campuran tak terbatas yang dapat dihitung) dengan proporsi pencampuran dan komponen pencampur .

Gambar 1: Model Grafis Model Campuran Proses Dirichlet

Di atas kita dapat melihat Model Grafis yang setara dari DPMM. G₀ adalah distribusi dasar DP dan biasanya dipilih untuk dikonjugasikan sebelum distribusi generatif F kami untuk membuat perhitungan lebih mudah dan memanfaatkan properti matematika yang menarik. Α adalah hyperparameter skalar dari Proses Dirichlet dan mempengaruhi jumlah cluster yang akan kita dapatkan. Semakin besar nilai α, semakin banyak clusternya; semakin kecil α semakin sedikit clusternya. Kita harus mencatat bahwa nilai α diekspresikan kekuatan kepercayaan dalam G₀. Nilai yang besar menunjukkan bahwa sebagian besar sampel akan berbeda dan memiliki nilai terkonsentrasi pada G₀. G adalah distribusi acak atas Θ ruang parameter yang diambil sampelnya dari DP yang memberikan probabilitas ke parameter. The θ_i adalah vektor parameter yang diambil dari distribusi G dan berisi parameter cluster, distribusi F diparameterisasi oleh θ_i dan x_i adalah titik data yang dihasilkan oleh Distribusi Generatif F.

Penting untuk dicatat bahwa θ_i adalah elemen dari ruang parameter Θ dan mereka "mengkonfigurasi" cluster kita. Mereka juga dapat dilihat sebagai variabel laten pada x_i yang memberitahu kita dari komponen / cluster mana x_i berasal dan apa saja parameter dari komponen ini. Jadi untuk setiap x_i yang kami amati, kami menggambar θ_i dari distribusi G. Dengan setiap gambar, distribusi berubah tergantung pada pilihan sebelumnya. Seperti yang kita lihat dalam skema guci Blackwell-MacQueen, distribusi G dapat diintegrasikan dan pilihan θ kami di masa mendatang_i hanya bergantung pada G₀: . Memperkirakan parameter θi dari rumus sebelumnya tidak selalu dapat dilakukan karena banyak implementasi (seperti Proses Restoran Cina) melibatkan pencacahan melalui meningkatkan komponen k secara eksponensial. Jadi metode perhitungan perkiraan digunakan seperti Gibbs Sampling. Akhirnya kita harus mencatat bahwa meskipun cluster k tidak terbatas, jumlah cluster aktif adalah . Jadi θ_i akan mengulangi dan menunjukkan efek pengelompokan.

2. Menggunakan Proses Restoran Cina untuk mendefinisikan Model Campuran Tak Terbatas

Model yang ditentukan di segmen sebelumnya solid secara matematis, namun memiliki kelemahan utama: untuk setiap x baru_i yang kami amati, kami harus mencicipi θ baru_i dengan mempertimbangkan nilai sebelumnya dari θ. Masalahnya adalah bahwa dalam banyak kasus, pengambilan sampel parameter ini bisa menjadi tugas yang sulit dan mahal secara komputasi.

Pendekatan alternatif adalah dengan menggunakan Proses Restoran Cina untuk memodelkan variabel laten z_i tugas cluster. Dengan cara ini daripada menggunakan θ_i untuk menunjukkan parameter cluster dan tugas cluster, kami menggunakan variabel laten z_i untuk menunjukkan id cluster dan kemudian menggunakan nilai ini untuk menetapkan parameter cluster. Akibatnya, kita tidak perlu lagi mengambil sampel θ setiap kali kita mendapatkan pengamatan baru, tetapi kita mendapatkan tugas cluster dengan mengambil sampel z_i dari CRP. Dengan skema ini, θ baru diambil sampelnya hanya ketika kita perlu membuat cluster baru. Di bawah ini kami menyajikan model pendekatan ini:

Persamaan 2: Model Campuran dengan CRP

Di atas adalah model generatif yang menggambarkan bagaimana data x_i dan cluster dibuat. Untuk melakukan analisis cluster kita harus menggunakan observasi x_i dan memperkirakan tugas cluster z_i.

3. Inferensi Model Campuran dan Sampling Gibbs

Sayangnya karena Proses Dirichlet non-parametrik, kami tidak dapat menggunakan algoritma EM untuk memperkirakan variabel laten yang menyimpan tugas cluster. Untuk memperkirakan tugas, kami akan menggunakan Pengambilan Sampel Gibbs yang Diciutkan.

The Collapsed Gibbs Sampling adalah algoritma Markov Chain Monte Carlo (MCMC) sederhana. Ini cepat dan memungkinkan kami untuk mengintegrasikan beberapa variabel sambil mengambil sampel variabel lain. Namun algoritma ini mengharuskan kita untuk memilih G₀ yang merupakan konjugasi sebelum distribusi generatif F agar dapat menyelesaikan persamaan secara analitis dan dapat mengambil sampel langsung dari .

Langkah-langkah dari Collapsed Gibbs Sampling yang akan kita gunakan untuk memperkirakan tugas cluster adalah sebagai berikut:

• Inisialisasi z_i tugas cluster secara acak
• Ulangi sampai konvergensi
• Pilih kapak secara acak_i
  
• Pertahankan z lainnya_j tetap untuk setiap j ≠ i:
• Tetapkan nilai baru pada z_i dengan menghitung "probabilitas CRP" yang bergantung pada z_j dan x_j dari semua j ≠ i:

Pada artikel selanjutnya kita akan fokus pada bagaimana melakukan analisis cluster dengan menggunakan model Dirichlet Process Mixture. Kami akan mendefinisikan dua Model Campuran Proses Dirichlet berbeda yang menggunakan Proses Restoran Cina dan Sampling Gibbs yang Diciutkan untuk melakukan pengelompokan pada kumpulan data dan dokumen berkelanjutan.