Pengenalan Kepada Rantai Markov Dengan Contoh - Rantai Markov Dengan Python

Pengenalan kepada Markov Chains:

Adakah anda pernah tertanya-tanya bagaimana Google meletakkan halaman web? Sekiranya anda telah membuat kajian anda, anda mesti tahu bahawa ia menggunakan Algoritma PageRank yang berdasarkan idea rantai Markov. Artikel ini mengenai Pengenalan Kepada Markov Chains akan membantu anda memahami idea asas di sebalik rantai Markov dan bagaimana ia dapat dijadikan model sebagai penyelesaian untuk masalah dunia nyata.

Berikut adalah senarai topik yang akan dibahas dalam blog ini:

1. Apakah Rantai Markov?
2. Apakah Harta Markov?
3. Memahami Rantai Markov Dengan Contohnya
4. Apakah Matriks Peralihan?
5. Rantai Markov Di Python
6. Aplikasi Rantai Markov

Untuk mendapatkan pengetahuan mendalam mengenai Sains Data dan Pembelajaran Mesin menggunakan Python, anda boleh mendaftar secara langsung oleh Edureka dengan sokongan 24/7 dan akses seumur hidup.

Apakah Rantai Markov?

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

Proses stokastik yang mengandungi pemboleh ubah rawak, beralih dari satu keadaan ke keadaan yang lain bergantung pada andaian tertentu dan peraturan probabilistik yang pasti.

Ini secara rawak pemboleh ubah beralih dari satu ke keadaan ke yang lain, berdasarkan sifat penting matematik yang disebut Harta Markov.

Ini membawa kita kepada persoalan:

Apakah Harta Markov?

Discrete Time Markov Property menyatakan bahawa kebarangkalian yang dikira dari proses rawak yang beralih ke keadaan seterusnya mungkin hanya bergantung pada keadaan dan masa semasa dan tidak bergantung kepada rangkaian keadaan yang mendahuluinya.

Kenyataan bahawa kemungkinan tindakan / keadaan proses rawak seterusnya tidak bergantung pada urutan keadaan sebelumnya, menjadikan rantai Markov sebagai proses tanpa memori yang bergantung sepenuhnya pada keadaan / tindakan semasa pemboleh ubah.

Mari kita hasilkan ini secara matematik:

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

Proses ini adalah rantaian Markov hanya jika,

Markov Chain - Pengenalan Kepada Markov Chains - Edureka

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

Untuk bilangan negeri yang terbatas, S = {0, 1, 2, ⋯, r}, ini disebut rantai Markov terhingga.

P (Xm + 1 = j | Xm = i) di sini mewakili kebarangkalian peralihan untuk beralih dari satu keadaan ke keadaan yang lain. Di sini, kami menganggap bahawa kebarangkalian peralihan tidak bergantung pada masa.

Yang bermaksud bahawa P (Xm + 1 = j | Xm = i) tidak bergantung pada nilai ‘m’. Oleh itu, kita dapat merumuskan,

Formula Rantai Markov - Pengenalan Kepada Rantai Markov - Edureka

Jadi persamaan ini mewakili rantaian Markov.

Sekarang mari kita fahami apa sebenarnya rantai Markov dengan contoh.

Contoh Rantai Markov

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

Apakah Model Markov?

Model Markov adalah model stokastik yang memodelkan pemboleh ubah rawak sedemikian rupa sehingga pemboleh ubah mengikuti harta Markov.

Sekarang mari kita fahami bagaimana Model Markov berfungsi dengan contoh mudah.

Seperti yang disebutkan sebelumnya, rantai Markov digunakan dalam aplikasi pembuatan teks dan penyelesaian otomatis. Untuk contoh ini, kita akan melihat contoh ayat (rawak) dan melihat bagaimana ia dapat dimodelkan dengan menggunakan rantai Markov.

Contoh Markov Chain - Pengenalan Kepada Markov Chains - Edureka

kepada kekuatan java

Kalimat di atas adalah contoh kami, saya tahu ia tidak masuk akal (tidak semestinya), itu adalah ayat yang mengandungi kata-kata rawak, di mana:

1. Kekunci menunjukkan perkataan unik dalam ayat, iaitu 5 kunci (satu, dua, hujan es, gembira, edureka)

2. Token menunjukkan jumlah kata, iaitu 8 token.

Melangkah ke hadapan, kita perlu memahami kekerapan berlakunya kata-kata ini, rajah di bawah menunjukkan setiap perkataan bersama dengan angka yang menunjukkan kekerapan kata tersebut.

Kekunci Dan Kekerapan - Pengenalan Kepada Rantai Markov - Edureka

Jadi lajur kiri di sini menunjukkan kekunci dan lajur kanan menunjukkan frekuensi.

Dari jadual di atas, kita dapat menyimpulkan bahawa kunci 'edureka' muncul 4x sama seperti kunci lain. Penting untuk menyimpulkan maklumat tersebut kerana dapat membantu kita meramalkan perkataan apa yang mungkin terjadi pada suatu masa tertentu. Sekiranya saya meneka tentang kata berikutnya dalam ayat contoh, saya akan menggunakan 'edureka' kerana ia mempunyai kemungkinan kejadian paling tinggi.

Bercakap mengenai kebarangkalian, langkah lain yang mesti anda perhatikan adalah pembahagian berwajaran.

Dalam kes kami, taburan berwajaran untuk 'edureka' adalah 50% (4/8) kerana kekerapannya adalah 4, daripada jumlah keseluruhan 8 token. Kekunci selebihnya (satu, dua, salam, gembira) semuanya mempunyai peluang 1/8 untuk berlaku (& asymp 13%).

Sekarang kita mempunyai pemahaman tentang sebaran tertimbang dan idea tentang bagaimana kata-kata tertentu lebih kerap berlaku daripada yang lain, kita dapat meneruskan bahagian selanjutnya.

Memahami Markov Chains - Pengenalan Kepada Markov Chains - Edureka

Dalam gambar di atas, saya telah menambahkan dua perkataan tambahan yang menunjukkan permulaan dan akhir ayat, anda akan memahami mengapa saya melakukan ini di bahagian bawah.

Sekarang mari kita tetapkan kekerapan untuk kunci ini juga:

Kekunci dan Kekerapan yang Dikemas kini - Pengenalan Kepada Rantai Markov - Edureka

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

Jadi pada dasarnya dalam model Markov, untuk meramalkan keadaan seterusnya, kita hanya perlu mempertimbangkan keadaan semasa.

Dalam rajah di bawah, anda dapat melihat bagaimana setiap token dalam ayat kami membawa kepada token yang lain. Ini menunjukkan bahawa keadaan masa depan (token seterusnya) berdasarkan keadaan semasa (token sekarang). Jadi ini adalah peraturan paling asas dalam Model Markov.

Gambar rajah di bawah menunjukkan bahawa terdapat pasangan token di mana setiap token dalam pasangan membawa kepada token yang lain dalam pasangan yang sama.

Pasangan Rantai Markov - Pengenalan Kepada Rantai Markov - Edureka

Dalam rajah di bawah, saya telah membuat perwakilan struktur yang menunjukkan setiap kunci dengan pelbagai token seterusnya yang dapat dipadankan.

Pelbagai Pasangan Rantai Markov - Pengenalan Kepada Rantai Markov - Edureka

Untuk meringkaskan contoh ini, pertimbangkan senario di mana anda perlu membentuk ayat dengan menggunakan susunan kunci dan tanda yang kita lihat dalam contoh di atas. Sebelum kita melalui contoh ini, satu lagi perkara penting ialah kita perlu menentukan dua langkah awal:

1. Taburan kebarangkalian awal (iaitu keadaan permulaan pada masa = 0, (kunci 'Mula'))

2. Kebarangkalian peralihan melompat dari satu keadaan ke keadaan lain (dalam kes ini, kebarangkalian peralihan dari satu token ke token yang lain)

Kami telah menentukan taburan berwajaran di awal itu sendiri, jadi kami mempunyai kebarangkalian dan keadaan awal, sekarang mari kita mulakan dengan contohnya.

• Jadi untuk memulakan dengan token awal adalah [Mula]

• Seterusnya, kami hanya mempunyai satu token yang mungkin iaitu [satu]

• Pada masa ini, ayat itu hanya mempunyai satu perkataan, iaitu 'satu'

• Dari token ini, token yang mungkin seterusnya adalah [edureka]

• Kalimat dikemas kini menjadi 'satu edureka'

• Dari [edureka] kita boleh beralih ke salah satu daripada token berikut [dua, salam, gembira, akhir]

• Terdapat 25% kemungkinan 'dua' terpilih, ini mungkin akan menghasilkan ayat yang asli (satu edureka dua edureka salam edureka happy edureka). Namun, jika 'akhir' dipilih maka prosesnya akan berhenti dan kita akhirnya akan menghasilkan ayat baru, iaitu 'satu edureka'.

Lekatkan diri anda di belakang kerana anda baru membina Model Markov dan menjalankan ujian kes melaluinya. Untuk meringkaskan contoh di atas, pada dasarnya kita menggunakan keadaan sekarang (kata sekarang) untuk menentukan keadaan seterusnya (kata seterusnya). Dan itulah sebenarnya proses Markov.

Ini adalah proses stokastik di mana pemboleh ubah rawak beralih dari satu keadaan ke keadaan lain sedemikian rupa sehingga keadaan pemboleh ubah masa depan hanya bergantung pada keadaan sekarang.

Mari kita teruskan ke langkah seterusnya dan gambarkan Model Markov untuk contoh ini.

Diagram Peralihan Negeri - Pengenalan Kepada Rantai Markov - Edureka

Rajah di atas dikenali sebagai Diagram Peralihan Negeri. Kami akan membincangkan lebih lanjut mengenai perkara ini di bahagian di bawah, kerana sekarang ingat bahawa rajah ini menunjukkan peralihan dan kebarangkalian dari satu keadaan ke keadaan yang lain.

Perhatikan bahawa setiap bujur dalam gambar mewakili kunci dan anak panah diarahkan ke arah kemungkinan kunci yang boleh mengikutinya. Berat pada anak panah menandakan kebarangkalian atau pembobotan wajaran peralihan dari / ke negeri masing-masing.

Jadi itu semua mengenai bagaimana Model Markov berfungsi. Sekarang mari kita cuba memahami beberapa istilah penting dalam Proses Markov.

Apakah Matriks Kebarangkalian Peralihan?

Pada bahagian di atas kita membincangkan cara kerja Model Markov dengan contoh mudah, sekarang mari kita memahami terminologi matematik dalam Proses Markov.

Dalam Proses Markov, kami menggunakan matriks untuk mewakili kebarangkalian peralihan dari satu keadaan ke keadaan yang lain. Matriks ini dipanggil matriks Transisi atau kebarangkalian. Ia biasanya dilambangkan oleh P.

Transisi Matriks - Pengenalan Kepada Markov Chains - Edureka

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

Formula Matriks Peralihan - Pengenalan Kepada Rantai Markov - Edureka

Izinkan saya menerangkan perkara ini. Dengan andaian bahawa keadaan kita sekarang adalah 'i', keadaan berikutnya atau yang akan datang harus menjadi salah satu keadaan yang berpotensi. Oleh itu, semasa mengambil penjumlahan semua nilai k, kita mesti mendapatkannya.

Apakah Rajah Peralihan Negeri?

Model Markov diwakili oleh Diagram Peralihan Negeri. Rajah menunjukkan peralihan antara keadaan yang berlainan dalam Rantai Markov. Mari kita fahami matriks peralihan dan matriks peralihan keadaan dengan contoh.

Contoh Matriks Peralihan

Pertimbangkan rantaian Markov dengan tiga keadaan 1, 2, dan 3 dan kemungkinan berikut:

Contoh Transisi Matriks - Pengenalan Kepada Markov Chains - Edureka

Diagram Peralihan Negeri Contoh - Pengenalan Kepada Rantai Markov - Edureka

Gambar rajah di atas mewakili rajah peralihan keadaan untuk rantaian Markov. Di sini, 1,2 dan 3 adalah tiga keadaan yang mungkin, dan anak panah yang menunjuk dari satu keadaan ke negeri lain mewakili kebarangkalian peralihan pij. Bila, pij = 0, ini bermaksud bahawa tidak ada peralihan antara keadaan ‘i’ dan keadaan ‘j’.

Sekarang kita ketahui matematik dan logik di sebalik rantaian Markov, mari kita jalankan demo ringkas dan fahami di mana rantai Markov dapat digunakan.

Rantai Markov Di Python

Untuk menjalankan demo ini, saya akan menggunakan Python, jadi jika anda tidak mengenali Python, anda boleh melalui blog berikut:

2. Cara Belajar Python 3 dari Scratch - Panduan Pemula

Sekarang mari kita mulakan dengan pengekodan!

Penjana Teks Markov Chain

Pernyataan masalah: Untuk menggunakan Markov Property dan membuat Model Markov yang dapat menghasilkan simulasi teks dengan mengkaji set data ucapan Donald Trump.

Penerangan Set Data: Fail teks mengandungi senarai ucapan yang diberikan oleh Donald Trump pada tahun 2016.

Logik: Gunakan Markov Property untuk menghasilkan ucapan Donald Trump dengan mempertimbangkan setiap perkataan yang digunakan dalam ucapan itu dan untuk setiap perkataan, buat kamus perkataan yang akan digunakan seterusnya.

Langkah 1: Import pakej yang diperlukan

import numpy sebagai np

Langkah 2: Baca set data

trump = terbuka ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). baca () #lihatkan cetakan data (trump) UCAPAN 1 ... Terima kasih awak sangat. Bagus sangat. Bukankah dia lelaki yang hebat. Dia tidak mendapat akhbar yang adil dan tidak mendapatnya. Ia tidak adil. Dan saya harus memberitahu anda bahawa saya di sini, dan sangat kuat di sini, kerana saya sangat menghormati Steve King dan juga sangat menghormati Citizens United, David dan semua orang, dan penghormatan yang luar biasa untuk Tea Party. Juga, orang-orang Iowa. Mereka mempunyai persamaan. Orang yang rajin….

Langkah 3: Pisahkan kumpulan data menjadi perkataan individu

corpus = trump.split () #Menampilkan cetakan corpus (corpus) 'kuat,', 'tetapi', 'tidak', 'kuat', 'seperti', 'kita.', 'Iran', 'telah', ' disemai ',' keganasan ', ...

Seterusnya, buat fungsi yang menghasilkan pelbagai pasangan kata dalam ucapan. Untuk menjimatkan ruang, kami akan menggunakan objek penjana.

Langkah 4: Membuat pasangan ke kunci dan kata-kata susulan

def make_pairs (corpus): for i in range (len (corpus) - 1): hasil (corpus [i], corpus [i + 1]) pasangan = make_pairs (corpus)

Seterusnya, mari kita mulakan kamus kosong untuk menyimpan pasangan perkataan.

Sekiranya kata pertama dalam pasangan sudah menjadi kunci dalam kamus, tambahkan kata berpotensi berikutnya ke senarai kata yang mengikuti kata tersebut. Tetapi jika kata itu bukan kunci, maka buat entri baru dalam kamus dan tetapkan kunci sama dengan kata pertama dalam pasangan.

Langkah 5: Menambah kamus

word_dict = {} untuk word_1, word_2 berpasangan: if word_1 in word_dict.keys (): word_dict [word_1]. append (word_2) other: word_dict [word_1] = [word_2]

Seterusnya, kami memilih perkataan dari korpus secara rawak, yang akan memulakan rantaian Markov.

Langkah 6: Bina model Markov

# pilih secara acak kata pertama first_word = np.random.choice (corpus) #Pilih kata pertama sebagai kata besar sehingga perkataan yang dipilih tidak diambil dari antara ayat sementara first_word.islower (): # Mulakan rantai dari rantai kata yang dipilih = [kata pertama] #Mulakan bilangan perkataan yang dirangsang n_words = 20

Mengikuti kata pertama, setiap kata dalam rantai tersebut diambil sampel secara rawak dari senarai kata yang mengikuti kata tertentu itu dalam pidato langsung Trump. Ini ditunjukkan dalam coretan kod di bawah:

untuk i in range (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Langkah 7: Ramalan

Akhirnya, mari kita paparkan teks yang dirangsang.

#Join mengembalikan rantai sebagai cetakan rentetan ('' .join (rantai)) Jumlah orang yang luar biasa. Dan Hillary Clinton, mempunyai orang-orang kita, dan pekerjaan yang hebat. Dan kita tidak akan mengalahkan Obama

Jadi ini adalah teks yang dihasilkan yang saya dapat dengan mempertimbangkan ucapan Trump. Ini mungkin tidak masuk akal tetapi cukup baik untuk membuat anda memahami bagaimana rantai Markov dapat digunakan untuk menghasilkan teks secara automatik.

Sekarang mari kita lihat beberapa aplikasi lagi rantai Markov dan bagaimana ia digunakan untuk menyelesaikan masalah di dunia nyata.

Aplikasi Rantai Markov

Berikut adalah senarai aplikasi dunia nyata dari rangkaian Markov:

1. Kedudukan Halaman Google: Seluruh web boleh dianggap sebagai model Markov, di mana setiap halaman web boleh menjadi keadaan dan pautan atau rujukan antara halaman ini dapat dianggap sebagai, peralihan dengan kemungkinan. Jadi pada dasarnya, tanpa mengira halaman web mana anda mula melayari, kemungkinan masuk ke laman web tertentu, katakanlah, X adalah kebarangkalian tetap.

2. Ramalan Kata Menaip: Rantai Markov diketahui digunakan untuk meramalkan kata-kata yang akan datang. Mereka juga dapat digunakan dalam penyelesaian dan cadangan automatik.

3. Simulasi Subreddit: Pasti anda telah menemui Reddit dan mempunyai interaksi pada salah satu utas atau subreddit mereka. Reddit menggunakan simulator subreddit yang menggunakan sejumlah besar data yang mengandungi semua komen dan perbincangan yang diadakan di seluruh kumpulan mereka. Dengan menggunakan rantai Markov, simulator menghasilkan kebarangkalian kata-ke-kata, untuk membuat komen dan topik.

4. Penjana teks: Rantai Markov paling sering digunakan untuk menghasilkan teks palsu atau menghasilkan karangan besar dan menyusun ucapan. Ia juga digunakan dalam penjana nama yang anda lihat di web.

Sekarang setelah anda mengetahui cara menyelesaikan masalah dunia nyata dengan menggunakan Markov Chains, saya pasti anda ingin tahu lebih banyak. Berikut adalah senarai blog yang akan membantu anda memulakan konsep statistik lain:

Dengan ini, kita sampai pada akhir blog Introduction To Markov Chains ini. Sekiranya anda mempunyai pertanyaan mengenai topik ini, sila tinggalkan komen di bawah dan kami akan menghubungi anda.

Nantikan lebih banyak blog mengenai teknologi yang sedang tren.

Sekiranya anda mencari latihan berstruktur dalam talian dalam Sains Data, edureka! mempunyai kurasi khas program yang membantu anda memperoleh kepakaran dalam Statistik, Penyusunan Data, Analisis Data Eksploratori, Algoritma Pembelajaran Mesin seperti Pengelompokan K-Means, Pohon Keputusan, Hutan Acak, Teluk Naive. Anda akan mempelajari konsep Siri Masa, Perlombongan Teks dan juga pengenalan kepada Pembelajaran Dalam. Kumpulan baru untuk kursus ini akan dimulakan tidak lama lagi !!