🕴🏻 👨🏼‍💻 🛕 Pengantar singkat tentang rantai Markov 🤭 🛌🏼 👆🏿

Pada tahun 1998, Lawrence Page, Sergey Brin, Rajiv Motwani dan Terry Vinograd menerbitkan artikel "Peringkat Kutipan PageRank: Membawa Pesanan ke Web", yang menggambarkan algoritma PageRank yang sekarang terkenal, yang menjadi fondasi Google. Setelah kurang dari dua dekade, Google menjadi raksasa, dan meskipun algoritmanya telah banyak berkembang, PageRank masih menjadi "simbol" dari algoritma peringkat Google (meskipun hanya beberapa orang yang dapat benar-benar mengetahui berapa banyak bobot yang dibutuhkan dalam algoritma saat ini) .

Dari sudut pandang teoretis, menarik untuk dicatat bahwa salah satu interpretasi standar dari algoritma PageRank didasarkan pada konsep rantai Markov yang sederhana namun mendasar. Dari artikel ini kita akan melihat bahwa rantai Markov adalah alat yang kuat untuk pemodelan stokastik yang dapat berguna bagi ilmuwan data mana pun. Secara khusus, kami akan menjawab pertanyaan mendasar seperti itu: apa rantai Markov, properti bagus apa yang mereka miliki, dan apa yang dapat dilakukan dengan bantuan mereka?

Ulasan singkat

Pada bagian pertama, kami memberikan definisi dasar yang diperlukan untuk memahami rantai Markov. Pada bagian kedua, kami mempertimbangkan kasus khusus rantai Markov di ruang keadaan terbatas. Pada bagian ketiga, kami mempertimbangkan beberapa sifat dasar rantai Markov dan menggambarkan properti ini dengan banyak contoh kecil. Akhirnya, pada bagian keempat, kami mengaitkan rantai Markov dengan algoritma PageRank dan melihat dengan contoh buatan bagaimana rantai Markov dapat digunakan untuk menentukan peringkat node grafik.

Catatan Memahami posting ini membutuhkan pengetahuan tentang dasar-dasar probabilitas dan aljabar linier. Secara khusus, konsep-konsep berikut akan digunakan: probabilitas bersyarat , vektor eigen, dan rumus probabilitas penuh .

Apa itu rantai Markov?

Variabel acak dan proses acak

Sebelum memperkenalkan konsep rantai Markov, mari kita mengingat secara singkat konsep dasar, tetapi penting dari teori probabilitas.

Pertama, di luar bahasa matematika, variabel acak X adalah kuantitas yang ditentukan oleh hasil dari fenomena acak. Hasilnya mungkin berupa angka (atau "kesamaan angka", misalnya vektor) atau yang lainnya. Sebagai contoh, kita dapat mendefinisikan variabel acak sebagai hasil dari die roll (angka) atau sebagai hasil lemparan koin (bukan angka, kecuali kita menunjuk, misalnya, "elang" sebagai 0, tetapi "ekor" sebagai 1). Kami juga menyebutkan bahwa ruang hasil yang mungkin dari variabel acak dapat diskrit atau kontinu: misalnya, variabel acak normal kontinu, dan variabel acak Poisson adalah diskrit.

Lebih lanjut, kita dapat mendefinisikan proses acak (juga disebut stokastik) sebagai satu set variabel acak yang diindeks oleh himpunan T, yang sering menunjukkan titik yang berbeda dalam waktu (dalam hal berikut kita akan menganggap ini). Dua kasus yang paling umum: T dapat berupa satu set bilangan alami (proses acak dengan waktu diskrit), atau satu set bilangan real (proses acak dengan waktu kontinu). Misalnya, jika kita melempar koin setiap hari, kita akan menetapkan proses acak dengan waktu diskrit, dan nilai opsi yang selalu berubah di bursa akan menetapkan proses acak dengan waktu kontinu. Variabel acak pada titik yang berbeda dalam waktu dapat independen satu sama lain (contoh dengan lemparan koin), atau memiliki semacam ketergantungan (contoh dengan nilai opsi); selain itu, mereka dapat memiliki ruang keadaan kontinu atau diskrit (ruang hasil yang mungkin pada setiap saat dalam waktu).

Berbagai jenis proses acak (diskrit / kontinyu dalam ruang / waktu).

Properti Markov dan rantai Markov

Ada keluarga terkenal dari proses acak: proses Gaussian, proses Poisson, model autoregresif, model rata-rata bergerak, rantai Markov, dan lain-lain. Masing-masing kasus ini memiliki sifat tertentu yang memungkinkan kami untuk mengeksplorasi dan memahaminya dengan lebih baik.

Salah satu properti yang sangat menyederhanakan studi proses acak adalah properti Markov. Jika kami menjelaskannya dalam bahasa yang sangat informal, maka properti Markov memberi tahu kami bahwa jika kami mengetahui nilai yang diperoleh dari beberapa proses acak pada saat tertentu, maka kami tidak akan menerima informasi tambahan tentang perilaku proses di masa depan, mengumpulkan informasi lain tentang masa lalu. Dalam bahasa yang lebih matematis: kapan saja dalam waktu, distribusi kondisional dari kondisi masa depan dari suatu proses dengan kondisi saat ini dan masa lalu hanya bergantung pada kondisi saat ini, dan bukan pada kondisi masa lalu ( properti kurangnya memori ). Proses acak dengan properti Markov disebut proses Markov .

Properti Markov berarti bahwa jika kita mengetahui keadaan saat ini pada saat tertentu, maka kita tidak memerlukan informasi tambahan tentang masa depan, yang dikumpulkan dari masa lalu.

Berdasarkan definisi ini, kita dapat merumuskan definisi "rantai Markov homogen dengan waktu diskrit" (selanjutnya untuk kesederhanaan kita akan menyebutnya "rantai Markov"). Rantai Markov adalah proses Markov dengan waktu diskrit dan ruang keadaan diskrit. Jadi, rantai Markov adalah urutan keadaan diskrit, yang masing-masing diambil dari ruang keadaan diskrit (terbatas atau tak terbatas), memuaskan properti Markov.

Secara matematis, kita dapat menunjukkan rantai Markov sebagai berikut:

di mana pada setiap momen waktu proses mengambil nilainya dari himpunan E diskrit, sedemikian rupa sehingga

Kemudian properti Markov menyiratkan bahwa kita miliki

Perhatikan lagi bahwa rumus terakhir ini mencerminkan fakta bahwa untuk kronologi (di mana saya sekarang dan di mana saya berada sebelumnya) distribusi probabilitas keadaan berikutnya (di mana saya akan menjadi berikutnya) tergantung pada keadaan saat ini, tetapi tidak pada keadaan sebelumnya.

Catatan Dalam posting pengantar ini, kami memutuskan untuk berbicara hanya tentang rantai Markov homogen sederhana dengan waktu diskrit. Namun, ada juga rantai Markov yang tidak homogen (tergantung waktu) dan / atau rantai waktu kontinu. Pada artikel ini kami tidak akan mempertimbangkan variasi model tersebut. Perlu juga dicatat bahwa definisi properti Markov di atas sangat disederhanakan: definisi matematika yang sebenarnya menggunakan konsep penyaringan, yang jauh melampaui perkenalan awal kami dengan model.

Kami mencirikan dinamika keacakan rantai Markov

Pada subbab sebelumnya, kami berkenalan dengan struktur umum yang terkait dengan rantai Markov. Mari kita lihat apa yang perlu kita atur "contoh" spesifik dari proses acak tersebut.

Pertama, kami mencatat bahwa penentuan lengkap dari karakteristik proses acak dengan waktu diskrit yang tidak memenuhi properti Markov bisa sulit: distribusi probabilitas pada titik waktu tertentu mungkin tergantung pada satu atau lebih momen di masa lalu dan / atau masa depan. Semua kemungkinan dependensi waktu ini berpotensi mempersulit pembuatan definisi proses.

Namun, karena properti Markov, dinamika rantai Markov cukup sederhana untuk ditentukan. Dan memang. kita hanya perlu menentukan dua aspek: distribusi probabilitas awal (mis., distribusi probabilitas pada waktu n = 0), dilambangkan dengan

dan matriks probabilitas transisi (yang memberi kita probabilitas bahwa negara pada waktu n +1 adalah yang berikutnya untuk keadaan lain pada waktu n untuk setiap pasangan negara), dilambangkan dengan

Jika kedua aspek ini diketahui, maka dinamika penuh (probabilistik) dari proses tersebut didefinisikan dengan jelas. Dan faktanya, probabilitas dari setiap hasil proses kemudian dapat dihitung secara siklis.

Contoh: misalkan kita ingin mengetahui probabilitas bahwa 3 status pertama dari proses akan memiliki nilai (s0, s1, s2). Artinya, kami ingin menghitung probabilitas

Di sini kita menerapkan rumus untuk probabilitas total, yang menyatakan bahwa probabilitas untuk memperoleh (s0, s1, s2) sama dengan probabilitas untuk mendapatkan s0 pertama dikalikan dengan probabilitas untuk memperoleh s1, mengingat bahwa kita sebelumnya menerima s0 dikalikan dengan probabilitas memperoleh s2 dengan mempertimbangkan fakta bahwa kami mendapat sebelumnya dalam urutan s0 dan s1. Secara matematis, ini dapat ditulis sebagai

Dan kemudian penyederhanaan diungkapkan, ditentukan oleh asumsi Markov. Dan faktanya, dalam kasus rantai panjang, kami memperoleh probabilitas sangat kondisional untuk kondisi terakhir. Namun, dalam kasus rantai Markov, kita dapat menyederhanakan ungkapan ini dengan mengambil keuntungan dari kenyataan itu

mendapatkan cara ini

Karena mereka sepenuhnya mencirikan dinamika probabilistik dari proses, banyak peristiwa kompleks dapat dihitung hanya berdasarkan distribusi probabilitas awal q0 dan matriks probabilitas transisi p. Perlu juga disebutkan satu koneksi dasar lagi: ekspresi distribusi probabilitas pada waktu n + 1, dinyatakan sehubungan dengan distribusi probabilitas pada waktu n

Markov berantai dalam ruang keadaan terbatas

Representasi matriks dan grafik

Di sini kita mengasumsikan bahwa himpunan E memiliki jumlah terbatas dari keadaan yang mungkin N:

Kemudian distribusi probabilitas awal dapat digambarkan sebagai vektor baris q0 ukuran N, dan probabilitas transisi dapat digambarkan sebagai matriks p ukuran N oleh N, sedemikian rupa sehingga

Keuntungan dari notasi ini adalah bahwa jika kita menyatakan distribusi probabilitas pada langkah n oleh vektor baris qn sehingga komponennya ditentukan

maka hubungan matriks sederhana dipertahankan

(di sini kami tidak akan mempertimbangkan buktinya, tetapi sangat mudah untuk mereproduksinya).

Jika kita mengalikan vektor baris di sebelah kanan, yang menggambarkan distribusi probabilitas pada tahap waktu tertentu, dengan matriks probabilitas transisi, maka kita mendapatkan distribusi probabilitas pada tahap waktu berikutnya.

Jadi, seperti yang kita lihat, transisi distribusi probabilitas dari tahap tertentu ke tahap berikutnya hanya didefinisikan sebagai perkalian yang tepat dari vektor baris probabilitas dari langkah awal dengan matriks p. Selain itu, ini menyiratkan yang kita miliki

Dinamika acak dari rantai Markov dalam ruang keadaan terbatas dapat dengan mudah direpresentasikan sebagai grafik berorientasi dinormalisasi sehingga setiap node dari grafik adalah negara, dan untuk setiap pasangan negara (ei, ej) terdapat tepi yang bergerak dari ei ke ej jika p (ei, ej )> 0. Maka nilai edge akan menjadi probabilitas p yang sama (ei, ej).

Contoh: pembaca situs kami

Mari kita ilustrasikan semua ini dengan contoh sederhana. Pertimbangkan perilaku sehari-hari pengunjung fiktif ke sebuah situs. Setiap hari ia memiliki 3 kemungkinan kondisi: pembaca tidak mengunjungi situs hari itu (N), pembaca mengunjungi situs, tetapi tidak membaca seluruh posting (V), dan pembaca mengunjungi situs dan membaca satu posting penuh (R). Jadi, kami memiliki ruang keadaan berikut:

Misalkan, pada hari pertama, pembaca ini memiliki peluang 50% untuk hanya mengakses situs dan 50% kemungkinan mengunjungi situs dan membaca setidaknya satu artikel. Vektor yang menggambarkan distribusi probabilitas awal (n = 0) kemudian terlihat seperti ini:

Juga bayangkan bahwa probabilitas berikut diamati:

ketika pembaca tidak mengunjungi satu hari, maka ada kemungkinan 25% tidak mengunjunginya pada hari berikutnya, probabilitas 50% hanya untuk mengunjunginya dan 25% untuk mengunjungi dan membaca artikel
ketika pembaca mengunjungi situs suatu hari, tetapi tidak membaca, maka dia memiliki kesempatan 50% untuk mengunjunginya lagi pada hari berikutnya dan tidak membaca artikel, dan 50% kesempatan untuk mengunjungi dan membaca
ketika seorang pembaca mengunjungi dan membaca sebuah artikel pada hari yang sama, ia memiliki peluang 33% untuk tidak masuk di hari berikutnya (saya harap posting ini tidak akan memiliki efek seperti itu!) , peluang 33% untuk hanya masuk ke situs dan 34% mengunjungi dan membaca artikel lagi

Kemudian kita memiliki matriks transisi berikut:

Dari subbagian sebelumnya, kita tahu bagaimana menghitung untuk pembaca ini probabilitas dari masing-masing negara pada hari berikutnya (n = 1)

Dinamika probabilistik rantai Markov ini dapat direpresentasikan secara grafis sebagai berikut:

Presentasi dalam bentuk grafik rantai Markov, memodelkan perilaku pengunjung yang kami temukan ke situs.

Properti rantai Markov

Pada bagian ini, kita hanya akan berbicara tentang beberapa sifat atau karakteristik paling mendasar dari rantai Markov. Kami tidak akan masuk ke detail matematika, tetapi akan memberikan gambaran singkat tentang poin menarik yang harus dipelajari untuk menggunakan rantai Markov. Seperti yang telah kita lihat, dalam kasus ruang keadaan terbatas, rantai Markov dapat direpresentasikan sebagai grafik. Di masa depan, kami akan menggunakan representasi grafis untuk menjelaskan beberapa properti. Namun, jangan lupa bahwa sifat-sifat ini tidak selalu terbatas pada kasus ruang keadaan terbatas.

Dekomposisi, periodisitas, irrevocabilitas, dan pemulihan

Dalam subbagian ini, mari kita mulai dengan beberapa cara klasik untuk mengkarakterisasi suatu negara atau keseluruhan rantai Markov.

Pertama, kami menyebutkan bahwa rantai Markov tidak dapat didaur ulang jika memungkinkan untuk mencapai negara mana pun dari negara lain (tidak perlu dalam satu langkah waktu). Jika ruang keadaan terbatas dan rantai dapat direpresentasikan sebagai grafik, maka kita dapat mengatakan bahwa grafik rantai Markov yang tidak dapat didekomposisikan sangat terhubung (teori graf).

Ilustrasi dari properti indecomposability (irreducibility). Rantai di sebelah kiri tidak dapat dipersingkat: dari 3 atau 4 kita tidak bisa masuk ke 1 atau 2. Rantai di sebelah kanan (satu sisi ditambahkan) dapat dipersingkat: setiap negara dapat dijangkau dari yang lain.

Suatu negara memiliki periode k jika, setelah meninggalkannya, untuk setiap pengembalian ke keadaan ini, jumlah langkah waktu adalah kelipatan k (k adalah pembagi umum terbesar dari semua panjang kemungkinan jalur pengembalian). Jika k = 1, maka mereka mengatakan bahwa negara adalah aperiodik, dan seluruh rantai Markov adalah aperiodik jika semua negara adalah aperiodik. Dalam kasus rantai Markov yang tidak dapat direduksi, kita juga dapat menyebutkan bahwa jika satu negara adalah aperiodik, maka semua yang lain juga aperiodik.

Ilustrasi properti periodisitas. Rantai di sebelah kiri adalah periodik dengan k = 2: ketika meninggalkan keadaan apa pun, kembali ke keadaan itu selalu membutuhkan jumlah langkah kelipatan 2. Rantai di sebelah kanan memiliki periode 3.

Suatu negara tidak dapat dibatalkan jika, ketika meninggalkan negara tersebut, ada kemungkinan tidak nol bahwa kita tidak akan pernah kembali ke sana. Sebaliknya, suatu negara dianggap dapat dikembalikan jika kita tahu bahwa setelah meninggalkan negara kita dapat kembali ke sana di masa depan dengan probabilitas 1 (jika tidak dapat dibatalkan).

Ilustrasi properti pengembalian / irrevocability. Rantai di sebelah kiri memiliki sifat-sifat berikut: 1, 2 dan 3 tidak dapat dibatalkan (ketika meninggalkan titik-titik ini kita tidak dapat benar-benar yakin bahwa kita akan kembali kepada mereka) dan memiliki periode 3, dan 4 dan 5 dapat dikembalikan (ketika meninggalkan titik-titik ini kita benar-benar yakin bahwa suatu hari nanti kita akan kembali kepada mereka) dan memiliki periode 2. Rantai di sebelah kanan memiliki tulang rusuk lain, membuat seluruh rantai dapat dikembalikan dan aperiodik.

Untuk kondisi pengembalian, kita dapat menghitung waktu pengembalian rata-rata, yang merupakan waktu pengembalian yang diharapkan saat meninggalkan negara. Perhatikan bahwa bahkan probabilitas pengembalian adalah 1, ini tidak berarti bahwa waktu pengembalian yang diharapkan terbatas. Oleh karena itu, di antara semua status pengembalian, kita dapat membedakan antara kondisi pengembalian positif (dengan waktu pengembalian yang diharapkan terbatas) dan kondisi pengembalian nol (dengan waktu pengembalian yang diharapkan tidak terbatas).

Distribusi stasioner, perilaku marjinal, dan ergodisitas

Dalam subbagian ini, kami mempertimbangkan properti yang mencirikan beberapa aspek dari dinamika (acak) yang dijelaskan oleh rantai Markov.

Distribusi probabilitas π di atas ruang keadaan E disebut distribusi stasioner jika memenuhi ekspresi

Karena sudah

Kemudian distribusi stasioner memenuhi ekspresi

Menurut definisi, distribusi probabilitas stasioner tidak berubah seiring waktu. Artinya, jika q distribusi awal adalah stasioner, maka itu akan sama pada semua tahap waktu berikutnya. Jika ruang keadaan terbatas, maka p dapat direpresentasikan sebagai matriks, dan π sebagai vektor baris, dan kemudian kita dapatkan

Ini lagi mengungkapkan fakta bahwa distribusi probabilitas stasioner tidak berubah dengan waktu (seperti yang kita lihat, mengalikan distribusi probabilitas di sebelah kanan dengan p memungkinkan kita untuk menghitung distribusi probabilitas pada tahap waktu berikutnya). Perlu diingat bahwa rantai Markov yang tidak dapat didekomposisi memiliki distribusi probabilitas stasioner jika dan hanya jika salah satu statusnya adalah pengembalian positif.

Properti menarik lainnya yang terkait dengan distribusi probabilitas stasioner adalah sebagai berikut. Jika rantai adalah pengembalian positif (yaitu, ada distribusi stasioner di dalamnya) dan aperiodik, maka, apa pun probabilitas awal, distribusi probabilitas rantai konvergen ketika interval waktu cenderung tak terbatas: mereka mengatakan bahwa rantai memiliki distribusi terbatas , yang tidak lain, sebagai distribusi stasioner. Secara umum, dapat ditulis seperti ini:

Kami menekankan sekali lagi fakta bahwa kami tidak membuat asumsi tentang distribusi probabilitas awal: distribusi probabilitas rantai berkurang ke distribusi stasioner (distribusi kesetimbangan rantai) terlepas dari parameter awal.

Akhirnya, ergodisitas adalah sifat menarik lainnya yang terkait dengan perilaku rantai Markov. Jika rantai Markov tidak dapat didekomposisi, maka dikatakan juga “ergodik” karena memenuhi teorema ergodik berikut. Misalkan kita memiliki fungsi f (.) Yang bergerak dari ruang keadaan E ke sumbu (ini bisa, misalnya, harga berada di setiap negara). Kita dapat menentukan nilai rata-rata yang menggerakkan fungsi ini sepanjang lintasan yang diberikan (rata-rata temporal). Untuk istilah pertama n, ini dilambangkan sebagai

Kita juga dapat menghitung nilai rata-rata fungsi f pada himpunan E, tertimbang oleh distribusi stasioner (spasial rata-rata), yang dilambangkan

Kemudian teorema ergodik memberi tahu kita bahwa ketika lintasan menjadi panjang tak terhingga, rata-rata waktu sama dengan rata-rata spasial (ditimbang oleh distribusi stasioner). Properti ergodisitas dapat ditulis sebagai berikut:

Dengan kata lain, itu berarti bahwa dalam batas sebelumnya perilaku lintasan menjadi tidak signifikan dan hanya perilaku stasioner jangka panjang yang penting ketika menghitung rata-rata temporal.

Mari kita kembali ke contoh dengan pembaca situs

Sekali lagi, perhatikan contoh pembaca situs. Dalam contoh sederhana ini, jelas bahwa rantai itu tidak dapat diurai, aperiodik, dan semua statusnya dapat dikembalikan secara positif.

Untuk menunjukkan hasil menarik apa yang dapat dihitung menggunakan rantai Markov, kami mempertimbangkan waktu rata-rata pengembalian ke negara R (negara “mengunjungi situs dan membaca artikel”). Dengan kata lain, kami ingin menjawab pertanyaan berikut: jika pembaca kami mengunjungi situs suatu hari dan membaca artikel, maka berapa hari kita harus menunggu rata-rata baginya untuk kembali dan membaca artikel? Mari kita coba untuk mendapatkan konsep intuitif tentang bagaimana nilai ini dihitung.

Pertama kita menunjukkan

Jadi kami ingin menghitung m (R, R). Berbicara tentang interval pertama yang dicapai setelah meninggalkan R, kita dapatkan

Namun, ungkapan ini mensyaratkan bahwa untuk perhitungan m (R, R) kita tahu m (N, R) dan m (V, R). Dua kuantitas ini dapat diekspresikan dengan cara yang serupa:

Jadi, kami mendapat 3 persamaan dengan 3 tidak diketahui dan setelah menyelesaikannya kami mendapatkan m (N, R) = 2.67, m (V, R) = 2.00 dan m (R, R) = 2.54. Waktu rata-rata untuk kembali ke keadaan R adalah 2.54. Yaitu, dengan menggunakan aljabar linier, kami dapat menghitung waktu rata-rata untuk kembali ke keadaan R (serta waktu transisi rata-rata dari N ke R dan waktu transisi rata-rata dari V ke R).

Untuk menyelesaikan dengan contoh ini, mari kita lihat apa distribusi stasioner rantai Markov nantinya. Untuk menentukan distribusi stasioner, kita perlu menyelesaikan persamaan aljabar linier berikut:

Yaitu, kita perlu menemukan vektor eigen kiri yang terkait dengan vektor eigen 1. Memecahkan masalah ini, kita memperoleh distribusi stasioner berikut:

Distribusi stasioner dalam contoh dengan pembaca situs.

Anda juga dapat memperhatikan bahwa π (R) = 1 / m (R, R), dan jika sedikit merenung, maka identitas ini cukup logis (tetapi kami tidak akan membicarakan hal ini secara rinci).

Karena rantai tidak dapat didekomposisi dan aperiodik, ini berarti bahwa dalam jangka panjang distribusi probabilitas akan menyatu dengan distribusi stasioner (untuk setiap parameter awal). Dengan kata lain, apa pun keadaan awal pembaca situs, jika kita menunggu cukup lama dan memilih satu hari secara acak, kita akan mendapatkan probabilitas π (N) bahwa pembaca tidak akan mengunjungi situs hari itu, probabilitas π (V) yang pembaca akan mampir tetapi tidak akan membaca artikel, dan probabilitasnya adalah π® bahwa pembaca akan mampir dan membaca artikel. Untuk lebih memahami properti konvergensi, mari kita lihat pada grafik berikut ini yang menunjukkan evolusi distribusi probabilitas mulai dari titik awal yang berbeda dan (cepat) konvergen ke distribusi stasioner:

Visualisasi konvergensi 3 distribusi probabilitas dengan parameter awal yang berbeda (biru, oranye dan hijau) ke distribusi stasioner (merah).

Contoh Klasik: Algoritma PageRank

Sudah waktunya untuk kembali ke PageRank! Tetapi sebelum melanjutkan, perlu disebutkan bahwa interpretasi PageRank yang diberikan dalam artikel ini bukan satu-satunya yang mungkin, dan penulis artikel asli tidak selalu bergantung pada penggunaan rantai Markov ketika mengembangkan metodologi. Namun, interpretasi kami baik karena sangat jelas.

Pengguna web sewenang-wenang

PageRank sedang mencoba untuk menyelesaikan masalah berikut: bagaimana kita dapat memberi peringkat pada set yang ada (kita dapat berasumsi bahwa set ini telah difilter, misalnya, dengan beberapa permintaan) menggunakan tautan yang sudah ada di antara halaman?

Untuk mengatasi masalah ini dan dapat membuat peringkat halaman, PageRank kira-kira melakukan proses berikut. Kami percaya bahwa pengguna Internet yang sewenang-wenang pada awalnya ada di salah satu halaman. Kemudian pengguna ini mulai secara acak mulai bergerak, mengklik pada setiap halaman pada salah satu tautan yang mengarah ke halaman lain dari set yang dipermasalahkan (diasumsikan bahwa semua tautan yang mengarah ke luar halaman ini dilarang). Pada halaman mana pun, semua tautan yang valid memiliki kemungkinan yang sama untuk mengklik.

Ini adalah bagaimana kami mendefinisikan rantai Markov: halaman adalah status yang memungkinkan, probabilitas transisi ditetapkan oleh tautan dari halaman ke halaman (ditimbang sedemikian rupa sehingga pada setiap halaman semua halaman yang terhubung memiliki probabilitas pemilihan yang sama), dan sifat-sifat kekurangan memori jelas ditentukan oleh perilaku pengguna. Jika kita juga mengasumsikan bahwa rantai yang diberikan dapat dikembalikan secara positif dan aperiodik (trik kecil digunakan untuk memenuhi persyaratan ini), maka dalam jangka panjang distribusi probabilitas "halaman saat ini" menyatu menjadi distribusi stasioner. Artinya, apa pun halaman awal, setelah waktu yang lama, setiap halaman memiliki probabilitas (hampir tetap) untuk menjadi terkini jika kita memilih momen acak dalam waktu.

PageRank didasarkan pada hipotesis berikut: halaman yang paling mungkin dalam distribusi stasioner juga harus menjadi yang paling penting (kami sering mengunjungi halaman ini karena mereka mendapatkan tautan dari halaman yang juga sering dikunjungi selama transisi). Kemudian distribusi probabilitas stasioner menentukan nilai PageRank untuk setiap negara.

Contoh Buatan

Untuk membuatnya lebih jelas, mari kita lihat contoh buatan. Misalkan kita memiliki situs web kecil dengan 7 halaman, berlabel 1 hingga 7, dan tautan di antara halaman-halaman ini sesuai dengan kolom berikut.

Demi kejelasan, probabilitas setiap transisi dalam animasi yang ditunjukkan di atas tidak ditampilkan. Namun, karena diasumsikan bahwa "navigasi" harus secara acak acak (ini disebut "jalan acak"), nilai-nilai dapat dengan mudah direproduksi dari aturan sederhana berikut: untuk situs dengan tautan keluar K (halaman dengan tautan K ke halaman lain), probabilitas setiap tautan keluar sama dengan 1 / K. Artinya, matriks probabilitas transisi memiliki bentuk:

di mana nilai 0,0 diganti untuk kenyamanan dengan "." Sebelum melakukan perhitungan lebih lanjut, kita dapat melihat bahwa rantai Markov ini tidak dapat dikompos dan aperiodik, yaitu, dalam jangka panjang sistem konvergen ke distribusi stasioner. Seperti yang telah kita lihat, distribusi stasioner ini dapat dihitung dengan memecahkan masalah vektor eigen kiri berikut

Dengan melakukannya, kita mendapatkan nilai PageRank berikut (nilai distribusi stasioner) untuk setiap halaman

Nilai-nilai PageRank dihitung untuk contoh buatan kami 7 halaman.

Maka peringkat PageRank situs web kecil ini adalah 1> 7> 4> 2> 5 = 6> 3.

Kesimpulan

Temuan kunci dari artikel ini:

proses acak adalah set variabel acak yang sering diindeks berdasarkan waktu (indeks sering menunjukkan waktu diskrit atau kontinu)
untuk proses acak, properti Markov berarti bahwa untuk arus yang diberikan, probabilitas masa depan tidak tergantung pada masa lalu (properti ini juga disebut "kurangnya memori")
rantai Markov diskrit-waktu adalah proses acak dengan indeks waktu diskrit yang memuaskan properti Markov
( , …)
PageRank ( ) -, ; ( , , , )

Sebagai kesimpulan, kami menekankan sekali lagi betapa kuatnya sebuah alat adalah rantai Markov dalam masalah pemodelan yang terkait dengan dinamika acak. Karena sifatnya yang baik, mereka digunakan dalam berbagai bidang, misalnya, dalam teori antrian (mengoptimalkan kinerja jaringan telekomunikasi di mana pesan sering harus bersaing untuk sumber daya yang terbatas dan antri ketika semua sumber daya sudah diambil), dalam statistik (Monte terkenal) Carlo menurut skema rantai Markov untuk menghasilkan variabel acak didasarkan pada rantai Markov), dalam biologi (pemodelan evolusi populasi biologis), dalam ilmu komputer (model Markov tersembunyi adalah alat penting umentami dalam teori informasi, dan pengenalan suara), serta di daerah lain.

Tentu saja, peluang besar yang diberikan oleh rantai Markov dari sudut pandang pemodelan dan komputasi jauh lebih luas daripada yang dipertimbangkan dalam ulasan sederhana ini. Oleh karena itu, kami berharap kami dapat membangkitkan minat pembaca untuk mempelajari lebih lanjut alat-alat ini, yang menempati tempat penting dalam gudang senjata seorang ilmuwan dan pakar data.

Pengantar singkat tentang rantai Markov