Pengantar Rantai Markov Dengan Contoh - Rantai Markov Dengan Python

Pengantar Rantai Markov:

Pernahkah Anda bertanya-tanya bagaimana Google memberi peringkat halaman web? Jika Anda telah melakukan penelitian Anda, maka Anda harus tahu bahwa itu menggunakan Algoritma PageRank yang didasarkan pada gagasan rantai Markov. Artikel tentang Pengantar Rantai Markov ini akan membantu Anda memahami ide dasar di balik rantai Markov dan bagaimana rantai tersebut dapat dimodelkan sebagai solusi untuk masalah dunia nyata.

Berikut daftar topik yang akan dibahas di blog ini:

1. Apa Itu Rantai Markov?
2. Apa Itu Properti Markov?
3. Memahami Rantai Markov Dengan Contoh
4. Apa Itu Matriks Transisi?
5. Rantai Markov Dengan Python
6. Aplikasi Markov Chain

Untuk mendapatkan pengetahuan mendalam tentang Ilmu Data dan Pembelajaran Mesin menggunakan Python, Anda dapat mendaftar secara langsung oleh Edureka dengan dukungan 24/7 dan akses seumur hidup.

Apa Itu Rantai Markov?

Andrey Markov pertama kali memperkenalkan rantai Markov pada tahun 1906. Dia menjelaskan rantai Markov sebagai:

Proses stokastik yang mengandung variabel acak, bertransisi dari satu keadaan ke keadaan lain tergantung pada asumsi tertentu dan aturan probabilistik yang pasti.

Acak ini variabel transisi dari satu keadaan ke keadaan lain, berdasarkan properti matematika penting yang disebut Properti Markov.

Ini membawa kita pada pertanyaan:

Apa Itu Properti Markov?

Properti Markov Waktu Diskrit menyatakan bahwa probabilitas terhitung dari proses acak yang bertransisi ke keadaan berikutnya yang mungkin hanya bergantung pada keadaan dan waktu saat ini dan tidak tergantung pada rangkaian keadaan yang mendahuluinya.

Fakta bahwa kemungkinan tindakan / status proses acak berikutnya tidak bergantung pada urutan status sebelumnya, menjadikan rantai Markov sebagai proses tanpa memori yang hanya bergantung pada status / tindakan saat ini dari suatu variabel.

Mari kita turunkan ini secara matematis:

Biarkan proses acaknya menjadi, {Xm, m = 0,1,2, ⋯}.

Proses ini adalah rantai Markov hanya jika,

Markov Chain - Pengantar Markov Chains - Edureka

untuk semua m, j, i, i0, i1, ⋯ im & minus1

Untuk sejumlah keadaan terbatas, S = {0, 1, 2, ⋯, r}, ini disebut rantai Markov hingga.

P (Xm + 1 = j | Xm = i) di sini mewakili probabilitas transisi untuk transisi dari satu kondisi ke kondisi lain. Di sini, kami mengasumsikan bahwa probabilitas transisi tidak bergantung pada waktu.

Artinya P (Xm + 1 = j | Xm = i) tidak bergantung pada nilai 'm'. Oleh karena itu, kami dapat meringkas,

Formula Rantai Markov - Pengantar Rantai Markov - Edureka

Jadi persamaan ini mewakili rantai Markov.

Sekarang mari kita pahami apa sebenarnya rantai Markov dengan sebuah contoh.

Contoh Rantai Markov

Sebelum saya memberi Anda contoh, mari kita tentukan apa itu Model Markov:

Apa Itu Model Markov?

Model Markov adalah model stokastik yang memodelkan variabel acak sedemikian rupa sehingga variabel tersebut mengikuti properti Markov.

Sekarang mari kita pahami cara kerja Model Markov dengan contoh sederhana.

cara menginstal php di windows

Seperti disebutkan sebelumnya, rantai Markov digunakan dalam pembuatan teks dan aplikasi pelengkapan otomatis. Untuk contoh ini, kita akan melihat contoh kalimat (acak) dan melihat bagaimana hal itu dapat dimodelkan dengan menggunakan rantai Markov.

Contoh Rantai Markov - Pengantar Rantai Markov - Edureka

Kalimat di atas adalah contoh kita, saya tahu itu tidak masuk akal (tidak harus), itu adalah kalimat yang mengandung kata-kata acak, dimana:

1. Kunci menunjukkan kata-kata unik dalam kalimat tersebut, yaitu 5 kunci (satu, dua, salam, bahagia, edureka)

2. Token menunjukkan jumlah kata, yaitu 8 token.

Ke depan, kita perlu memahami frekuensi kemunculan kata-kata tersebut, diagram di bawah ini menunjukkan setiap kata beserta angka yang menunjukkan frekuensi kata tersebut.

Kunci Dan Frekuensi - Pengantar Rantai Markov - Edureka

Jadi kolom kiri di sini menunjukkan kunci dan kolom kanan menunjukkan frekuensi.

Dari tabel di atas, kita dapat menyimpulkan bahwa kunci 'edureka' muncul 4x lebih banyak dari kunci lainnya. Informasi semacam itu penting untuk disimpulkan karena dapat membantu kami memprediksi kata apa yang mungkin muncul pada titik waktu tertentu. Jika saya menebak tentang kata berikutnya dalam contoh kalimat, saya akan memilih 'edureka' karena memiliki kemungkinan kemunculan tertinggi.

Berbicara tentang probabilitas, ukuran lain yang harus Anda waspadai adalah distribusi tertimbang.

Dalam kasus kami, distribusi berbobot untuk 'edureka' adalah 50% (4/8) karena frekuensinya adalah 4, dari total 8 token. Kunci lainnya (satu, dua, salam, bahagia) semuanya memiliki peluang 1/8 untuk muncul (& asymp 13%).

Sekarang setelah kita memiliki pemahaman tentang distribusi berbobot dan gagasan tentang bagaimana kata-kata tertentu muncul lebih sering daripada yang lain, kita dapat melanjutkan ke bagian selanjutnya.

Memahami Rantai Markov - Pengantar Rantai Markov - Edureka

Pada gambar di atas, saya telah menambahkan dua kata tambahan yang menunjukkan awal dan akhir kalimat, Anda akan mengerti mengapa saya melakukan ini di bagian bawah.

Sekarang mari kita tetapkan juga frekuensi untuk tombol-tombol ini:

Kunci dan Frekuensi yang Diperbarui - Pengantar Rantai Markov - Edureka

Sekarang mari kita buat model Markov. Seperti disebutkan sebelumnya, model Markov digunakan untuk memodelkan variabel acak pada keadaan tertentu sedemikian rupa sehingga keadaan masa depan variabel ini hanya bergantung pada keadaan mereka saat ini dan bukan keadaan masa lalu mereka.

Jadi pada dasarnya dalam model Markov, untuk memprediksi keadaan selanjutnya, kita hanya harus mempertimbangkan keadaan saat ini.

Pada diagram di bawah ini, Anda dapat melihat bagaimana setiap token dalam kalimat kita mengarah ke token lainnya. Ini menunjukkan bahwa keadaan masa depan (token berikutnya) didasarkan pada keadaan saat ini (token sekarang). Jadi inilah aturan paling dasar dalam Model Markov.

Diagram di bawah ini menunjukkan bahwa ada pasangan token di mana setiap token dalam pasangan mengarah ke yang lain dalam pasangan yang sama.

Pasangan Rantai Markov - Pengantar Rantai Markov - Edureka

Dalam diagram di bawah ini, saya telah membuat representasi struktural yang menunjukkan setiap kunci dengan array kemungkinan token berikutnya yang dapat dipasangkan.

Array Pasangan Rantai Markov - Pengantar Rantai Markov - Edureka

Untuk meringkas contoh ini pertimbangkan skenario di mana Anda harus membentuk kalimat dengan menggunakan larik kunci dan token yang kita lihat pada contoh di atas. Sebelum kita menjalankan contoh ini, poin penting lainnya adalah kita perlu menentukan dua ukuran awal:

1. Distribusi probabilitas awal (yaitu status awal pada waktu = 0, (kunci ‘Mulai’))

2. Probabilitas transisi untuk melompat dari satu status ke status lainnya (dalam hal ini, probabilitas transisi dari satu token ke token lainnya)

Kami telah mendefinisikan distribusi berbobot di awal itu sendiri, jadi kami memiliki probabilitas dan keadaan awal, sekarang mari kita lanjutkan dengan contohnya.

• Jadi untuk memulai dengan token awal adalah [Start]

• Selanjutnya, kami hanya memiliki satu kemungkinan token yaitu [satu]

• Saat ini kalimat tersebut hanya memiliki satu kata, yaitu 'satu'

• Dari token ini, kemungkinan token berikutnya adalah [edureka]

• Kalimat tersebut diperbarui menjadi 'one edureka'

• Dari [edureka] kita dapat pindah ke salah satu dari token berikut [dua, salam, bahagia, berakhir]

• Ada 25% kemungkinan 'dua' dicomot, hal ini kemungkinan akan mengakibatkan terbentuknya kalimat asli (satu edureka dua edureka hail edureka happy edureka). Namun, jika 'akhir' dipilih maka prosesnya berhenti dan kami akan menghasilkan kalimat baru, yaitu 'satu edureka'.

Beri diri Anda tepukan di punggung karena Anda baru saja membangun Model Markov dan menjalankan uji kasus melalui itu. Untuk meringkas contoh di atas, pada dasarnya kita menggunakan keadaan sekarang (kata sekarang) untuk menentukan keadaan selanjutnya (kata berikutnya). Dan itulah tepatnya proses Markov.

Ini adalah proses stokastik di mana variabel acak bertransisi dari satu keadaan ke keadaan lain sedemikian rupa sehingga keadaan variabel di masa depan hanya bergantung pada keadaan saat ini.

Mari kita lanjutkan ke langkah berikutnya dan menggambar Model Markov untuk contoh ini.

Diagram Transisi Status - Pengantar Rantai Markov - Edureka

Gambar di atas dikenal dengan State Transition Diagram. Kita akan membahas lebih lanjut tentang ini di bagian bawah, karena sekarang ingatlah bahwa diagram ini menunjukkan transisi dan probabilitas dari satu keadaan ke keadaan lainnya.

Perhatikan bahwa setiap oval pada gambar mewakili sebuah kunci dan panah diarahkan ke kemungkinan kunci yang dapat mengikutinya. Juga, bobot pada panah menunjukkan probabilitas atau distribusi berbobot dari transisi dari / ke status masing-masing.

Jadi itu semua tentang cara kerja Model Markov. Sekarang mari kita coba memahami beberapa terminologi penting dalam Proses Markov.

Apa Itu Matriks Probabilitas Transisi?

Pada bagian di atas kita membahas cara kerja Model Markov dengan contoh sederhana, sekarang mari kita memahami terminologi matematika dalam Proses Markov.

Dalam Proses Markov, kami menggunakan matriks untuk mewakili probabilitas transisi dari satu keadaan ke keadaan lain. Matriks ini disebut Matriks Transisi atau probabilitas. Biasanya dilambangkan dengan P.

Matriks Transisi - Pengantar Rantai Markov - Edureka

Catatan, pij & ge0, dan 'i' untuk semua nilai adalah,

Formula Matriks Transisi - Pengantar Rantai Markov - Edureka

Biar saya jelaskan ini. Dengan asumsi bahwa keadaan kita saat ini adalah 'i', keadaan berikutnya atau yang akan datang harus menjadi salah satu keadaan potensial. Oleh karena itu, saat menjumlahkan semua nilai k, kita harus mendapatkannya.

Apa Itu Diagram Transisi Keadaan?

Model Markov diwakili oleh Diagram Transisi Status. Diagram menunjukkan transisi di antara berbagai status dalam Rantai Markov. Mari kita pahami matriks transisi dan matriks transisi keadaan dengan sebuah contoh.

Contoh Matriks Transisi

Pertimbangkan rantai Markov dengan tiga keadaan 1, 2, dan 3 dan probabilitas berikut:

Contoh Matriks Transisi - Pengantar Rantai Markov - Edureka

Contoh Diagram Transisi Status - Pengantar Rantai Markov - Edureka

Diagram di atas mewakili diagram transisi keadaan untuk rantai Markov. Di sini, 1,2 dan 3 adalah tiga kemungkinan keadaan, dan panah yang menunjuk dari satu keadaan ke keadaan lain mewakili probabilitas transisi pij. Bila, pij = 0, berarti tidak ada transisi antara keadaan 'i' dan keadaan 'j'.

Sekarang kita mengetahui matematika dan logika di balik rantai Markov, mari kita jalankan demo sederhana dan pahami di mana rantai Markov dapat digunakan.

Rantai Markov Dengan Python

Untuk menjalankan demo ini, saya akan menggunakan Python, jadi jika Anda tidak tahu Python, Anda dapat membuka blog berikut ini:

2. Cara Belajar Python 3 dari Awal - Panduan Pemula

Sekarang, mari kita mulai dengan coding!

Pembuat Teks Rantai Markov

Pernyataan masalah: Untuk menerapkan Properti Markov dan membuat Model Markov yang dapat menghasilkan simulasi teks dengan mempelajari kumpulan data ucapan Donald Trump.

Deskripsi Kumpulan Data: File teks berisi daftar pidato yang diberikan oleh Donald Trump pada tahun 2016.

Logika: Terapkan Properti Markov untuk menghasilkan pidato Donald Trump dengan mempertimbangkan setiap kata yang digunakan dalam pidato tersebut dan untuk setiap kata, buat kamus kata-kata yang digunakan selanjutnya.

Langkah 1: Impor paket yang diperlukan

impor numpy sebagai np

Langkah 2: Baca kumpulan data

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display data print (trump) SPEECH 1 ... Terima kasih kamu banyak. Bagus sekali. Bukankah dia pria yang hebat. Dia tidak mendapatkan pers yang adil, dia tidak mendapatkannya. Ini tidak adil. Dan saya harus memberi tahu Anda bahwa saya di sini, dan sangat kuat di sini, karena saya sangat menghormati Steve King dan juga sangat menghormati Citizens United, David dan semua orang, dan sangat menghormati Tea Party. Juga, juga orang-orang Iowa. Mereka memiliki kesamaan. Orang pekerja keras ....

Langkah 3: Pisahkan kumpulan data menjadi kata-kata individual

corpus = trump.split () #Display corpus print (corpus) 'powerful,', 'but', 'not', 'powerful', 'like', 'us.', 'Iran', 'has', ' unggulan ',' teror ', ...

Selanjutnya, buat fungsi yang menghasilkan pasangan kata yang berbeda dalam pidato. Untuk menghemat ruang, kita akan menggunakan objek generator.

Langkah 4: Membuat pasangan kunci dan kata tindak lanjut

def make_pairs (corpus): untuk i dalam jangkauan (len (corpus) - 1): hasil (corpus [i], corpus [i + 1]) pasang = make_pairs (corpus)

Selanjutnya, mari kita inisialisasi kamus kosong untuk menyimpan pasangan kata.

Jika kata pertama dalam pasangan sudah menjadi kunci dalam kamus, cukup tambahkan kata potensial berikutnya ke daftar kata setelah kata tersebut. Namun jika kata tersebut bukan kunci, buat entri baru dalam kamus dan tetapkan kunci yang sama dengan kata pertama dalam pasangan.

Langkah 5: Menambahkan kamus

word_dict = {} untuk kata_1, kata_2 berpasangan: if word_1 di word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Selanjutnya, kami secara acak memilih kata dari korpus, yang akan memulai rantai Markov.

Langkah 6: Buat model Markov

# secara acak pilih kata pertama first_word = np.random.choice (corpus) #Pilih kata pertama sebagai kata dalam huruf besar sehingga kata yang dipilih tidak diambil dari antara kalimat sementara first_word.islower (): #Mulai rantai dari rantai kata yang dipilih = [kata_pertama] #Inisialisasi jumlah kata yang distimulasi n_words = 20

Setelah kata pertama, setiap kata dalam rangkaian diambil sampelnya secara acak dari daftar kata yang mengikuti kata spesifik tersebut dalam pidato langsung Trump. Ini ditunjukkan pada potongan kode di bawah ini:

untuk saya dalam jangkauan (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Langkah 7: Prediksi

Akhirnya, mari kita tampilkan teks yang dirangsang.

#Join mengembalikan rantai sebagai cetakan string ('.join (chain)) Jumlah orang yang luar biasa. Dan Hillary Clinton, memiliki orang-orang kami, dan pekerjaan yang luar biasa. Dan kami tidak akan mengalahkan Obama

Jadi inilah teks yang saya hasilkan dengan mempertimbangkan pidato Trump. Ini mungkin tidak masuk akal, tetapi cukup baik untuk membuat Anda memahami bagaimana rantai Markov dapat digunakan untuk menghasilkan teks secara otomatis.

Sekarang mari kita lihat beberapa aplikasi lainnya rantai Markov dan cara mereka digunakan untuk memecahkan masalah dunia nyata.

Aplikasi Markov Chain

Berikut daftar aplikasi rantai Markov di dunia nyata:

1. Google PageRank: Seluruh web dapat dianggap sebagai model Markov, di mana setiap halaman web dapat menjadi keadaan dan tautan atau referensi di antara halaman-halaman ini dapat dianggap sebagai, transisi dengan probabilitas. Jadi pada dasarnya, terlepas dari halaman web mana Anda mulai berselancar, peluang untuk membuka halaman web tertentu, katakanlah, X adalah probabilitas tetap.

2. Prediksi Mengetik Kata: Rantai Markov dikenal digunakan untuk memprediksi kata-kata yang akan datang. Mereka juga dapat digunakan dalam pelengkapan otomatis dan saran.

3. Simulasi Subreddit: Pasti Anda pernah menemukan Reddit dan berinteraksi di salah satu utas atau subreddit mereka. Reddit menggunakan simulator subreddit yang mengkonsumsi sejumlah besar data yang berisi semua komentar dan diskusi yang diadakan di seluruh grup mereka. Dengan menggunakan rantai Markov, simulator menghasilkan probabilitas kata-ke-kata, untuk membuat komentar dan topik.

4. Generator teks: Rantai Markov paling sering digunakan untuk menghasilkan teks tiruan atau menghasilkan esai besar dan menyusun pidato. Ini juga digunakan dalam generator nama yang Anda lihat di web.

Sekarang setelah Anda mengetahui cara memecahkan masalah dunia nyata dengan menggunakan Rantai Markov, saya yakin Anda penasaran untuk mempelajari lebih lanjut. Berikut daftar blog yang akan membantu Anda memulai konsep statistik lainnya:

Dengan ini, kita sampai pada bagian akhir blog Pengantar Rantai Markov. Jika Anda memiliki pertanyaan tentang topik ini, silakan tinggalkan komentar di bawah dan kami akan menghubungi Anda kembali.

Pantau terus untuk lebih banyak blog tentang teknologi yang sedang tren.

Jika Anda mencari pelatihan terstruktur online dalam Ilmu Data, edureka! memiliki kurasi khusus program yang membantu Anda mendapatkan keahlian dalam Statistik, Data Wrangling, Analisis Data Eksplorasi, Algoritma Pembelajaran Mesin seperti K-Means Clustering, Decision Trees, Random Forest, Naive Bayes. Anda akan mempelajari konsep Rangkaian Waktu, Penambangan Teks, dan pengantar Deep Learning juga. Gelombang baru untuk kursus ini akan segera dimulai !!