Subbab4.5Rantai Markov dan algoritma PageRank Google
Dalam bagian sebelumnya, kita menggunakan pemahaman tentang nilai eigen dan vektor eigen untuk mendeskripsikan perilaku jangka panjang beberapa sistem dinamis diskret. Keadaan sistem pada suatu waktu, yang misalnya dapat mencatat populasi beberapa spesies yang saling berinteraksi, dideskripsikan oleh vektor \(\xvec_k\text{.}\) Vektor keadaan kemudian berkembang menurut aturan linear \(\xvec_{k+1} =
A\xvec_k\text{.}\)
Bagian ini melanjutkan penelaahan tersebut dengan membahas rantai Markov, yang merupakan jenis khusus sistem dinamis diskret. Sebagai contoh, kita dapat menelaah sebuah perusahaan penyewaan mobil yang menyewakan mobil dari beberapa lokasi. Dari satu hari ke hari berikutnya, jumlah mobil di berbagai lokasi dapat berubah, tetapi jumlah total mobil tetap sama. Sekali lagi, pemahaman tentang nilai eigen dan vektor eigen akan membantu kita membuat prediksi tentang perilaku jangka panjang sistem tersebut.
Misalkan perusahaan penyewaan mobil kita menyewakan mobil dari dua lokasi \(P\) dan \(Q\text{.}\) Kita mendapati bahwa 80% mobil yang disewa dari lokasi \(P\) dikembalikan ke \(P\text{,}\) sedangkan 20% sisanya dikembalikan ke \(Q\text{.}\) Dari mobil yang disewa dari lokasi \(Q\text{,}\) 60% dikembalikan ke \(Q\) dan 40% ke \(P\text{.}\)
Kita akan menggunakan \(P_k\) dan \(Q_k\) untuk menyatakan jumlah mobil di kedua lokasi pada hari ke-\(k\text{.}\) Pada hari berikutnya, jumlah mobil di \(P\) sama dengan 80% dari \(P_k\) ditambah 40% dari \(Q_k\text{.}\) Hal ini menunjukkan bahwa
Jika kita menggunakan vektor \(\xvec_k =
\twovec{P_k}{Q_k}\) untuk menyatakan distribusi mobil pada hari ke-\(k\text{,}\) tentukan matriks \(A\) sedemikian sehingga \(\xvec_{k+1} = A\xvec_k\text{.}\)
Misalkan pada awalnya terdapat 1500 mobil dan semuanya berada di lokasi \(P\text{.}\) Nyatakan vektor \(\xvec_0\) sebagai kombinasi linear vektor-vektor eigen dari \(A\text{.}\)
Matriks ini memiliki beberapa sifat khusus. Pertama, setiap entri menyatakan probabilitas bahwa sebuah mobil yang disewa di satu lokasi dikembalikan ke suatu lokasi. Sebagai contoh, terdapat peluang 80% bahwa mobil yang disewa di \(P\) dikembalikan ke \(P\text{,}\) yang menjelaskan entri 0.8 di sudut kiri atas. Oleh karena itu, entri-entri matriks berada di antara 0 dan 1.
Kedua, sebuah mobil yang disewa di suatu lokasi harus dikembalikan ke salah satu lokasi. Sebagai contoh, karena 80% mobil yang disewa di \(P\) dikembalikan ke \(P\text{,}\) maka 20% mobil lainnya yang disewa di \(P\) dikembalikan ke \(Q\text{.}\) Hal ini menyiratkan bahwa jumlah entri dalam setiap kolom harus sama dengan 1. Situasi ini akan sering muncul dalam pembahasan kita, sehingga kita memperkenalkan definisi berikut.
Vektor yang entri-entrinya taknegatif dan berjumlah 1 disebut vektor probabilitas. Matriks persegi yang kolom-kolomnya merupakan vektor probabilitas disebut matriks stokastik.
Misalkan Anda tinggal di sebuah negara dengan tiga partai politik \(P\text{,}\)\(Q\text{,}\) dan \(R\text{.}\) Kita menggunakan \(P_k\text{,}\)\(Q_k\text{,}\) dan \(R_k\) untuk menyatakan persentase pemilih yang memilih partai tersebut dalam pemilu ke-\(k\text{.}\)
Pemilih akan berpindah partai dari satu pemilu ke pemilu berikutnya seperti ditunjukkan pada gambar. Kita melihat bahwa 60% pemilih tetap memilih partai yang sama. Namun, 40% pemilih partai \(P\) akan memilih partai \(Q\) pada pemilu berikutnya.
Dari kotak berlabel P, terdapat panah menuju Q berlabel \(0.4\text{,}\) panah menuju R berlabel \(0\text{,}\) dan gelung yang kembali ke P berlabel \(0.6\text{.}\)
Misalkan pada awalnya 40% warga memilih partai \(P\text{,}\) 30% memilih partai \(Q\text{,}\) dan 30% memilih partai \(R\text{.}\) Bentuklah vektor \(\xvec_0\) dan jelaskan mengapa \(\xvec_0\) merupakan vektor probabilitas.
Tentukan \(\xvec_1\text{,}\) yaitu persentase pemilih ketiga partai pada pemilu berikutnya. Verifikasikan bahwa \(\xvec_1\) juga merupakan vektor probabilitas dan jelaskan mengapa \(\xvec_k\) akan menjadi vektor probabilitas untuk setiap \(k\text{.}\)
Tentukan nilai-nilai eigen matriks \(A\) dan jelaskan mengapa ruang eigen \(E_1\) merupakan subruang berdimensi satu dari \(\real^3\text{.}\) Kemudian verifikasikan bahwa \(\vvec=\threevec{1}{2}{2}\) merupakan vektor basis untuk \(E_1\text{.}\)
Karena setiap vektor dalam \(E_1\) merupakan kelipatan skalar dari \(\vvec\text{,}\) tentukan sebuah vektor probabilitas dalam \(E_1\) dan jelaskan mengapa vektor tersebut merupakan satu-satunya vektor probabilitas dalam \(E_1\text{.}\)
Pertama, untuk menentukan \(P_{k+1}\text{,}\) kita mencatat bahwa dalam pemilu ke-\(k+1\text{,}\) partai \(P\) mempertahankan 60% pemilihnya dari pemilu sebelumnya dan memperoleh tambahan 20% pemilih yang sebelumnya memilih partai \(R\text{.}\) Dengan demikian, kita melihat bahwa
Jika kita memperhatikan kolom pertama \(A\text{,}\) kita melihat bahwa entri-entrinya menyatakan persentase pemilih partai \(P\) pada pemilu sebelumnya yang memilih masing-masing dari ketiga partai pada pemilu berikutnya. Karena setiap orang yang sebelumnya memilih partai \(P\) akan memilih salah satu dari ketiga partai pada pemilu berikutnya, jumlah persentase tersebut harus 1. Hal ini berlaku untuk setiap kolom \(A\text{,}\) yang menjelaskan mengapa \(A\) merupakan matriks stokastik.
Kita mulai dengan vektor \(\xvec_0 =
\threevec{0.4}{0.3}{0.3}\text{,}\) yang entri-entrinya menyatakan persentase pemilih untuk masing-masing dari ketiga partai. Karena setiap pemilih memilih salah satu dari ketiga partai, jumlah entri tersebut harus 1, yang berarti bahwa \(\xvec_0\) merupakan vektor probabilitas. Selanjutnya kita memperoleh
Perhatikan bahwa vektor-vektor \(\xvec_k\) juga merupakan vektor probabilitas dan barisan \(\xvec_k\) tampaknya konvergen ke \(\threevec{0.2}{0.4}{0.4}\text{.}\) Kita ingin memahami perilaku ini secara lebih menyeluruh dengan menyelidiki nilai eigen dan vektor eigen dari \(A\text{.}\)
Perhatikan bahwa jika \(\vvec\) merupakan vektor eigen \(A\) dengan nilai eigen terkait \(\lambda_1=1\text{,}\) maka \(A\vvec = 1\vvec
= \vvec\text{.}\) Artinya, \(\vvec\) tidak berubah ketika dikalikan dengan \(A\text{.}\)
Perhatikan bahwa \(|\lambda_2| = |\lambda_3| \lt 1\text{,}\) sehingga trajektori \(\xvec_k\) bergerak spiral menuju ruang eigen \(E_1\) seperti ditunjukkan pada gambar.
Diagram tiga dimensi dengan sumbu-sumbu koordinat baku berlabel \(x_1\text{,}\)\(x_2\text{,}\) dan \(x_3\text{.}\) Pada bidang \(x_2x_3\text{,}\) terdapat kisi koordinat yang menunjukkan bidang tersebut. Terdapat pula trajektori pada bidang itu yang bergerak spiral menuju titik asal seperti pada atraktor spiral dua dimensi.
Terdapat sejumlah trajektori serupa pada bidang-bidang yang sejajar dengan bidang \(x_2x_3\text{;}\) trajektori-trajektori tersebut bergerak spiral menuju sumbu \(x_1\text{.}\)
Hal ini menunjukkan bahwa barisan \(\xvec_k\) konvergen ke suatu vektor dalam \(E_1\text{.}\) Seperti biasa, kita melihat bahwa \(\vvec=\threevec{1}{2}{2}\) merupakan vektor basis untuk \(E_1\) karena \(A\vvec = \vvec\text{,}\) sehingga kita memperkirakan bahwa \(\xvec_k\) akan konvergen ke suatu kelipatan skalar dari \(\vvec\text{.}\) Memang, karena vektor-vektor \(\xvec_k\) merupakan vektor probabilitas, kita memperkirakan vektor-vektor tersebut akan konvergen ke suatu vektor probabilitas dalam \(E_1\text{.}\)
Kita dapat menentukan vektor probabilitas dalam \(E_1\) dengan mencari kelipatan skalar \(\vvec\) yang sesuai. Perhatikan bahwa \(c\vvec = \threevec{c}{2c}{2c}\) merupakan vektor probabilitas jika \(c+2c+2c=5c = 1\text{,}\) yang menyiratkan bahwa \(c = 1/5\text{.}\) Oleh karena itu, \(\qvec=\threevec{0.2}{0.4}{0.4}\) merupakan satu-satunya vektor probabilitas dalam \(E_1\text{.}\) Karena barisan \(\xvec_k\) konvergen ke suatu vektor probabilitas dalam \(E_1\text{,}\) kita melihat bahwa \(\xvec_k\) konvergen ke \(\qvec\text{,}\) sesuai dengan perhitungan yang ditunjukkan di atas.
Peran nilai eigen penting dalam contoh ini. Karena \(\lambda_1=1\text{,}\) kita dapat menemukan vektor probabilitas \(\qvec\) yang tidak berubah akibat perkalian dengan \(A\text{.}\) Selain itu, nilai-nilai eigen lainnya memenuhi \(|\lambda_j| \lt 1\text{,}\) yang berarti bahwa semua trajektori tertarik menuju ruang eigen \(E_1\text{.}\) Karena \(\xvec_k\) merupakan barisan vektor probabilitas, vektor-vektor tersebut konvergen ke vektor probabilitas \(\qvec\) ketika tertarik menuju \(E_1\text{.}\)
Jika kita mempunyai matriks stokastik \(A\) dan vektor probabilitas \(\xvec_0\text{,}\) kita dapat membentuk barisan \(\xvec_k\) dengan \(\xvec_{k+1} = A \xvec_k\text{.}\) Barisan vektor ini disebut rantai Markov. Latihan 4.5.6.6 menjelaskan mengapa kita dapat menjamin bahwa vektor-vektor \(\xvec_k\) merupakan vektor probabilitas.
Dalam contoh yang menelaah pola pemilihan, kita membentuk rantai Markov yang mendeskripsikan perubahan persentase pemilih berbagai partai dari satu pemilu ke pemilu berikutnya. Kita melihat bahwa rantai Markov tersebut konvergen ke \(\qvec=\threevec{0.2}{0.4}{0.4}\text{,}\) yaitu vektor probabilitas dalam ruang eigen \(E_1\text{.}\) Dengan kata lain, \(\qvec\) merupakan vektor probabilitas yang tidak berubah akibat perkalian dengan \(A\text{;}\) yaitu, \(A\qvec = \qvec\text{.}\) Hal ini menyiratkan bahwa setelah waktu yang lama, 20% pemilih memilih partai \(P\text{,}\) 40% memilih \(Q\text{,}\) dan 40% memilih \(R\text{.}\)
Kita akan membentuk rantai Markov yang diawali dengan vektor \(\xvec_0 = \twovec{1}{0}\) dan didefinisikan oleh \(\xvec_{k+1} = A\xvec_k\text{.}\) Sel Sage di bawah membentuk \(N\) suku pertama rantai Markov dengan perintah markov_chain(A, x0, N). Definisikan matriks A dan vektor x0, lalu evaluasi sel tersebut untuk menentukan 10 suku pertama rantai Markov.
Seperti sebelumnya, tentukan 10 suku pertama rantai Markov yang diawali dengan \(\xvec_0 = \twovec{1}{0}\) dan \(\xvec_{k+1} = B\xvec_k\text{.}\) Apa yang Anda amati tentang rantai Markov tersebut? Apakah rantai itu konvergen ke vektor keadaan tunak untuk \(B\text{?}\)
Seperti yang ditunjukkan aktivitas ini, nilai-nilai eigen suatu matriks stokastik memberi tahu kita apakah rantai Markov akan konvergen ke vektor keadaan tunak. Berikut beberapa fakta penting tentang nilai-nilai eigen matriks stokastik.
Seperti diperlihatkan dalam Latihan 4.5.6.8, \(\lambda=1\) merupakan nilai eigen setiap matriks stokastik. Biasanya kita mengurutkan nilai-nilai eigen sehingga nilai ini menjadi nilai eigen pertama, yang berarti bahwa \(\lambda_1=1\text{.}\)
Seperti digambarkan dalam aktivitas tersebut, rantai Markov dapat gagal konvergen ke vektor keadaan tunak jika \(|\lambda_2| = 1\text{.}\) Hal ini terjadi untuk matriks \(A = \left[\begin{array}{rr}
0 \amp 1 \\
1 \amp 0 \\
\end{array}\right]
\text{,}\) yang nilai-nilai eigennya adalah \(\lambda_1=1\) dan \(\lambda_2 =
-1\text{.}\)
Namun, jika semua nilai eigen selain yang pertama memenuhi \(|\lambda_j|\lt 1\text{,}\) maka terdapat tepat satu vektor keadaan tunak \(\qvec\) dan setiap rantai Markov akan konvergen ke \(\qvec\text{.}\) Hal ini berlaku untuk matriks \(B = \left[\begin{array}{rr}
0.4 \amp 0.3 \\
0.6 \amp 0.7 \\
\end{array}\right]
\text{,}\) yang nilai-nilai eigennya adalah \(\lambda_1=1\) dan \(\lambda_2 = 0.1\text{.}\) Dalam kasus ini, setiap rantai Markov akan konvergen ke satu-satunya vektor keadaan tunak \(\qvec =
\twovec{\frac13}{\frac23}\text{.}\)
Dengan demikian, kita melihat bahwa nilai-nilai eigen suatu matriks stokastik memberi tahu kita apakah rantai Markov akan konvergen ke vektor keadaan tunak. Namun, menghitung nilai eigen untuk menjawab pertanyaan ini agak merepotkan. Adakah cara untuk menyimpulkan bahwa setiap rantai Markov akan konvergen ke vektor keadaan tunak tanpa benar-benar menghitung nilai-nilai eigennya? Ternyata terdapat syarat sederhana pada matriks \(A\) yang menjamin hal tersebut.
Matriks \(A = \left[\begin{array}{rr}
0 \amp 1 \\
1 \amp 0 \\
\end{array}\right]\) tidak positif. Hal ini terlihat karena beberapa entri \(A\) bernilai nol sehingga tidak positif. Selain itu, kita melihat bahwa \(A^2 = I\text{,}\)\(A^3 = A\text{,}\) dan seterusnya. Oleh karena itu, setiap pangkat \(A\) juga memiliki beberapa entri nol, yang berarti bahwa \(A\) tidak positif.
Selain itu, matriks \(C = \left[\begin{array}{rr}
0 \amp 0.5 \\
1 \amp 0.5 \\
\end{array}\right]\) jelas memiliki sebuah entri nol. Namun, \(C^2 = \left[\begin{array}{rr}
0.5 \amp 0.25 \\
0.5 \amp 0.75 \\
\end{array}\right]
\text{,}\) yang semua entrinya positif. Oleh karena itu, kita melihat bahwa \(C\) merupakan matriks positif.
Jika \(A\) merupakan matriks stokastik positif, nilai-nilai eigennya memenuhi \(\lambda_1=1\) dan \(|\lambda_j| \lt
1\) untuk \(j\gt 1\text{.}\) Ini berarti bahwa \(A\) memiliki satu-satunya vektor keadaan tunak positif \(\qvec\) dan bahwa setiap rantai Markov yang didefinisikan oleh \(A\) akan konvergen ke \(\qvec\text{.}\)
Kita akan menelaah makna teorema Perron-Frobenius dalam aktivitas ini.
Perhatikan matriks \(C = \left[\begin{array}{rr}
0 \amp 0.5 \\
1 \amp 0.5 \\
\end{array}\right]
\text{.}\) Matriks ini positif, seperti yang kita lihat dalam contoh sebelumnya. Tentukan vektor-vektor eigen \(C\) dan verifikasikan bahwa terdapat satu-satunya vektor keadaan tunak.
Dengan menggunakan sel Sage di bawah, bentuklah rantai Markov dengan vektor awal \(\xvec_0= \twovec{1}{0}\) dan deskripsikan apa yang terjadi pada \(\xvec_k\) ketika \(k\) membesar.
Bentuklah rantai Markov lain dengan vektor awal \(\xvec_0=\twovec{0.2}{0.8}\) dan deskripsikan apa yang terjadi pada \(\xvec_k\) ketika \(k\) membesar.
Apa yang terjadi pada rantai Markov yang didefinisikan oleh \(D\) dengan vektor awal \(\xvec_0 =\threevec{1}{0}{0}\text{?}\) Apa yang terjadi pada rantai Markov dengan vektor awal \(\xvec_0=\threevec{0}{0}{1}\text{.}\)
Rantai Markov dan teorema Perron-Frobenius merupakan unsur utama dalam algoritma PageRank Google, yang dikembangkan Google untuk menilai kualitas halaman web.
Misalkan kita memasukkan “aljabar linear” ke mesin pencari Google. Google memberi tahu kita bahwa terdapat 138 juta halaman web yang memuat istilah tersebut. Namun, pada halaman pertama terdapat tautan ke sepuluh halaman web yang dinilai Google memiliki kualitas tertinggi dan paling mungkin menarik minat kita. Bagaimana Google menilai kualitas halaman web?
Ketika uraian ini ditulis, Google melacak 35 triliun halaman web. Jelas, jumlah ini terlalu banyak untuk dinilai manusia. Selain itu, penilai manusia dapat memasukkan bias mereka sendiri ke dalam penilaian, bahkan mungkin tanpa sengaja. Gagasan Google adalah menggunakan struktur Internet untuk menilai kualitas halaman web tanpa campur tangan manusia. Sebagai contoh, jika sebuah halaman web memiliki konten berkualitas, halaman web lain akan menaut kepadanya. Artinya, jumlah tautan menuju suatu halaman mencerminkan kualitas halaman tersebut. Selain itu, kita memperkirakan bahwa sebuah halaman memiliki konten berkualitas lebih tinggi lagi jika tautan-tautan itu berasal dari halaman yang juga dinilai berkualitas tinggi. Sederhananya, jika banyak halaman berkualitas menaut ke sebuah halaman, halaman itu sendiri pastilah berkualitas tinggi. Inilah inti algoritma PageRank, yang kita perkenalkan dalam aktivitas berikut.
Kita akan menelaah model sederhana Internet yang memiliki tiga halaman dengan tautan di antaranya seperti ditunjukkan di sini. Sebagai contoh, halaman 1 menaut ke halaman 2 dan 3, tetapi halaman 2 hanya menaut ke halaman 1.
Tiga lingkaran yang menyatakan tiga halaman web disusun pada titik-titik sudut segitiga dan diberi label “1”, “2”, dan “3”. Tautan dari satu halaman ke halaman lain dinyatakan oleh panah dari satu lingkaran ke lingkaran lain.
Dari halaman web berlabel 1, terdapat panah menuju halaman web 2 dan 3. Dari halaman berlabel 2, terdapat panah menuju 1. Dari halaman 3, terdapat panah menuju 1 dan 2.
Kita akan mengukur kualitas halaman ke-\(j^{th}\) dengan bilangan \(x_j\text{,}\) yang disebut PageRank halaman \(j\text{.}\) PageRank ditentukan oleh aturan berikut: setiap halaman membagi PageRank-nya menjadi bagian-bagian sama besar, satu untuk setiap tautan keluar, dan memberikan satu bagian kepada setiap halaman yang ditautnya. PageRank suatu halaman adalah jumlah seluruh PageRank yang diterimanya dari halaman-halaman yang menaut kepadanya.
Sebagai contoh, halaman 3 memiliki dua tautan keluar. Oleh karena itu, halaman tersebut membagi dua PageRank \(x_3\) dan memberikan separuhnya kepada halaman 1. Halaman 2 hanya memiliki satu tautan keluar sehingga memberikan seluruh PageRank \(x_2\)-nya kepada halaman 1. Dengan demikian, kita mempunyai
Sekarang kita membentuk vektor PageRank \(\xvec =
\threevec{x_1}{x_2}{x_3}\text{.}\) Tentukan matriks \(G\) sedemikian sehingga ekspresi untuk \(x_1\text{,}\)\(x_2\text{,}\) dan \(x_3\) dapat dituliskan dalam bentuk \(G\xvec = \xvec\text{.}\) Matriks \(G\) disebut “matriks Google”.
Karena \(\xvec\) didefinisikan oleh persamaan \(G\xvec = \xvec\text{,}\) setiap vektor dalam ruang eigen \(E_1\) memenuhi persamaan ini. Agar kita dapat bekerja dengan suatu vektor tertentu, kita mendefinisikan vektor PageRank sebagai vektor keadaan tunak dari matriks stokastik \(G\text{.}\) Tentukan vektor keadaan tunak ini.
Vektor PageRank \(\xvec\) tersusun atas PageRank setiap halaman dari ketiga halaman tersebut. Halaman manakah yang dinilai memiliki kualitas tertinggi? Dengan mengacu pada struktur model kecil Internet ini, jelaskan mengapa pilihan tersebut tepat.
Jika kita memulai dengan vektor awal \(\xvec_0 =
\threevec{1}{0}{0}\) dan membentuk rantai Markov \(\xvec_{k+1} = G\xvec_k\text{,}\) apa yang dinyatakan teorema Perron-Frobenius tentang perilaku jangka panjang rantai Markov tersebut?
Aktivitas ini menunjukkan dua cara untuk menentukan vektor PageRank. Pada cara pertama, kita menentukan vektor keadaan tunak secara langsung dengan mencari deskripsi ruang eigen \(E_1\text{,}\) kemudian mencari kelipatan skalar yang sesuai dari sebuah vektor basis yang menghasilkan vektor keadaan tunak. Namun, untuk mencari deskripsi ruang eigen \(E_1\text{,}\) kita perlu menentukan ruang nol \(\nul(G-I)\text{.}\) Ingatlah bahwa Internet sebenarnya memiliki 35 triliun halaman, sehingga menentukan \(\nul(G-I)\) mengharuskan kita mereduksi baris matriks dengan 35 triliun baris dan kolom. Seperti yang kita lihat dalam Subbagian 1.3.3, hal itu tidak layak secara komputasional.
Seperti yang disarankan aktivitas tersebut, cara kedua untuk menentukan vektor PageRank adalah menggunakan rantai Markov yang konvergen ke vektor PageRank. Karena mengalikan vektor dengan matriks memerlukan jauh lebih sedikit usaha daripada mereduksi baris matriks, pendekatan ini layak secara komputasional. Sebenarnya, beginilah cara Google menghitung vektor PageRank.
Model Internet yang lebih rumit dengan delapan halaman berlabel 1 hingga 8. Halaman 1 menaut ke halaman 2 dan 3. Halaman 2 menaut ke halaman 4. Halaman 3 menaut ke halaman 2 dan 5. Halaman 4 menaut ke halaman 2 dan 6. Halaman 5 menaut ke halaman 6, 7, dan 8. Halaman 6 menaut ke halaman 8. Halaman 7 menaut ke halaman 1, 5, dan 8. Halaman 8 menaut ke halaman 6 dan 7.
Apa yang dinyatakan vektor ini tentang kualitas relatif halaman-halaman dalam Internet ini? Halaman mana yang memiliki kualitas tertinggi dan mana yang terendah?
Terdapat lima halaman web berlabel 1 hingga 5. Halaman 1 menaut ke halaman 2. Halaman 2 menaut ke halaman 3. Halaman 3 menaut ke halaman 4. Halaman 4 menaut ke halaman 5. Halaman 5 menaut ke halaman 1.
Apa yang terjadi ketika Anda memulai rantai Markov dengan vektor \(\xvec_0=\fivevec{1}{0}{0}{0}{0}\text{?}\) Jelaskan mengapa perilaku ini konsisten dengan teorema Perron-Frobenius.
Model Internet dengan delapan halaman. Model ini persis sama dengan yang dinyatakan dalam Gambar 4.5.8, kecuali tautan dari halaman 7 ke halaman 1 telah dihapus.
Secara lebih terperinci, terdapat delapan halaman berlabel 1 hingga 8. Halaman 1 menaut ke halaman 2 dan 3. Halaman 2 menaut ke halaman 4. Halaman 3 menaut ke halaman 2 dan 5. Halaman 4 menaut ke halaman 2 dan 6. Halaman 5 menaut ke halaman 6, 7, dan 8. Halaman 6 menaut ke halaman 8. Halaman 7 menaut ke halaman 5 dan 8. Halaman 8 menaut ke halaman 6 dan 7.
Perhatikan bahwa versi Internet ini identik dengan versi pertama yang kita lihat dalam aktivitas ini, kecuali satu tautan dari halaman 7 ke halaman 1 telah dihapus. Oleh karena itu, kita dapat menentukan matriks Google \(G\)-nya dengan sedikit memodifikasi matriks sebelumnya.
Bagaimana perilaku jangka panjang rantai Markov yang didefinisikan oleh \(G\text{,}\) dan mengapa perilaku ini tidak diinginkan? Bagaimana perilaku ini konsisten dengan teorema Perron-Frobenius?
Teorema Perron-Frobenius Teorema 4.5.6 menyatakan bahwa rantai Markov \(\xvec_{k+1}=G\xvec_k\) konvergen ke satu-satunya vektor keadaan tunak jika matriks \(G\) positif. Artinya, \(G\) atau suatu pangkat \(G\) seharusnya hanya memiliki entri positif. Jelas bahwa hal ini tidak berlaku untuk matriks yang dibentuk dari Internet dalam Gambar 4.5.9.
Kita dapat memahami masalah pada Internet yang ditunjukkan dalam Gambar 4.5.10 dengan menambahkan kotak yang mengelilingi beberapa halaman seperti ditunjukkan dalam Gambar 4.5.11. Di sini kita melihat bahwa halaman di luar kotak menyerahkan seluruh PageRank-nya kepada halaman di dalam kotak. Hal ini tidak diinginkan karena PageRank halaman di luar kotak menjadi nol. Sekali lagi, matriks Google \(G\) bukan matriks positif.
Internet yang sama dengan yang dinyatakan dalam Gambar 4.5.10, dengan kotak yang digambar mengelilingi halaman 5, 6, 7, dan 8. Terdapat dua panah menuju bagian dalam kotak dan tidak ada panah yang keluar. Hal ini menunjukkan bahwa PageRank mengalir masuk ke kotak tetapi tidak pernah dapat keluar. Oleh karena itu, halaman di luar kotak menyerahkan seluruh PageRank-nya kepada halaman di dalam kotak.
Google mengatasi masalah ini dengan sedikit memodifikasi matriks Google \(G\) untuk memperoleh matriks positif \(G'\text{.}\) Untuk memahaminya, anggaplah entri-entri dalam matriks Google menyatakan probabilitas bahwa pengguna Internet mengikuti tautan dari satu halaman ke halaman lain. Untuk membentuk matriks positif, kita akan mengizinkan pengguna tersebut melompat secara acak ke halaman lain mana pun di Internet dengan probabilitas kecil.
merupakan matriks stokastik positif yang mendeskripsikan proses ketika kita dapat berpindah dari halaman mana pun ke halaman lain dengan probabilitas yang sama. Untuk membentuk matriks Google termodifikasi \(G'\text{,}\) kita memilih parameter \(\alpha\) yang digunakan untuk mencampurkan \(G\) dan \(H_n\text{;}\) yaitu, \(G'\) merupakan matriks stokastik positif
\begin{equation*}
G' = \alpha G +(1-\alpha)H_n\text{.}
\end{equation*}
Dalam praktiknya, Google diperkirakan menggunakan nilai \(\alpha=0.85\) (Google tidak memublikasikan angka ini karena merupakan rahasia dagang), sehingga kita mempunyai
\begin{equation*}
G' = 0.85 G + 0.15H_n\text{.}
\end{equation*}
Secara intuitif, ini berarti bahwa pengguna Internet akan mengikuti tautan secara acak dari satu halaman ke halaman lain sebanyak 85% dari waktu dan melompat secara acak ke halaman lain mana pun di Internet sebanyak 15% dari waktu. Karena matriks \(G'\) positif, teorema Perron-Frobenius menyatakan bahwa setiap rantai Markov akan konvergen ke satu-satunya vektor keadaan tunak yang kita sebut vektor PageRank.
Sel Sage berikut akan menghasilkan rantai Markov untuk matriks Google termodifikasi \(G'\) jika Anda cukup memasukkan matriks Google asli \(G\) pada baris yang sesuai.
Perhatikan Internet asli dengan tiga halaman yang ditunjukkan dalam Gambar 4.5.7, lalu tentukan vektor PageRank \(\xvec\) dengan menggunakan matriks Google termodifikasi pada sel Sage di atas. Bagaimana perbandingan vektor PageRank termodifikasi ini dengan vektor yang kita peroleh menggunakan matriks Google asli \(G\text{?}\)
Tentukan vektor PageRank termodifikasi untuk Internet yang ditunjukkan dalam Gambar 4.5.9. Jelaskan mengapa vektor ini tampaknya merupakan vektor yang tepat.
Tentukan vektor PageRank termodifikasi untuk Internet yang ditunjukkan dalam Gambar 4.5.10. Jelaskan mengapa vektor PageRank termodifikasi ini memperbaiki masalah yang muncul pada vektor PageRank asli.
Kemampuan mengakses hampir segala sesuatu yang ingin kita ketahui melalui Internet merupakan hal yang kita anggap biasa dalam masyarakat masa kini. Namun, tanpa algoritma PageRank Google, Internet tentu akan menjadi tempat yang kacau; bayangkan harus mencari halaman web yang berguna di antara 30 triliun halaman yang tersedia tanpa algoritma itu. (Tentu saja terdapat algoritma pencarian lain, tetapi algoritma Google paling luas digunakan.) Peran mendasar rantai Markov dan teorema Perron-Frobenius dalam algoritma Google menunjukkan kekuatan luar biasa matematika dalam membentuk masyarakat kita.
Bagian ini menelaah matriks stokastik dan rantai Markov.
Vektor probabilitas adalah vektor yang entri-entrinya taknegatif dan berjumlah 1. Matriks stokastik adalah matriks persegi yang kolom-kolomnya merupakan vektor probabilitas.
Rantai Markov dibentuk dari matriks stokastik \(A\) dan vektor probabilitas awal \(\xvec_0\) dengan menggunakan aturan \(\xvec_{k+1}=A\xvec_k\text{.}\) Kita dapat memandang barisan \(\xvec_k\) sebagai deskripsi perkembangan suatu kuantitas yang kekal, seperti jumlah mobil sewaan atau pemilih, di antara sejumlah keadaan yang mungkin seiring waktu.
Teorema Perron-Frobenius menyatakan bahwa jika \(A\) merupakan matriks stokastik positif, maka setiap rantai Markov yang didefinisikan oleh \(A\) konvergen ke satu-satunya vektor keadaan tunak positif.
Untuk masing-masing matriks, buatlah salinan diagram dan beri label setiap sisi untuk menunjukkan probabilitas transisi tersebut. Kemudian tentukan semua vektor keadaan tunaknya dan deskripsikan apa yang terjadi pada rantai Markov yang didefinisikan oleh matriks itu.
Terdapat dua kotak berlabel P dan Q. Terdapat panah dari P ke Q dan panah dari Q ke P. Terdapat pula gelung dari P kembali ke dirinya sendiri dan dari Q kembali ke dirinya sendiri. Tidak satu pun diberi label karena latihan ini akan menelaah beberapa kemungkinan.
Setiap tahun, orang berpindah di antara populasi perkotaan (U), pinggiran kota (S), dan pedesaan (R) dengan probabilitas yang diberikan dalam Gambar 4.5.12.
Dari kotak berlabel U, terdapat panah menuju S berlabel \(0.07\text{,}\) panah menuju R berlabel \(0.05\text{,}\) dan gelung yang kembali ke U berlabel \(0.88\text{.}\)
Dari S, terdapat panah menuju U berlabel \(0.08\text{,}\) panah menuju R berlabel \(0.06\text{,}\) dan gelung yang kembali ke S berlabel \(0.86\text{.}\)
Dari R, terdapat panah menuju U berlabel \(0.08\text{,}\) panah menuju S berlabel \(0.07\text{,}\) dan gelung yang kembali ke R berlabel \(0.85\text{.}\)
Dalam beberapa latihan berikut, kita akan menelaah matriks \(1\times n\)\(S = \left[\begin{array}{rrrr} 1 \amp 1 \amp
\ldots \amp 1 \end{array}\right]\text{.}\)
Misalkan \(A\) merupakan matriks stokastik dan \(\xvec\) merupakan vektor probabilitas. Kita ingin menjelaskan mengapa hasil kali \(A\xvec\) merupakan vektor probabilitas.
Jelaskan mengapa \(\xvec=\threevec{0.4}{0.5}{0.1}\) merupakan vektor probabilitas, kemudian tentukan hasil kali \(S\xvec\text{.}\)
Dengan menggunakan hasil latihan sebelumnya, kita ingin menjelaskan mengapa \(A^2\) merupakan matriks stokastik jika \(A\) stokastik.
Misalkan \(A\) dan \(B\) merupakan matriks stokastik. Jelaskan mengapa hasil kali \(AB\) merupakan matriks stokastik dengan memperhatikan hasil kali \(SAB\text{.}\)
Latihan ini menjelaskan mengapa \(\lambda=1\) merupakan nilai eigen matriks stokastik \(A\text{.}\) Untuk menyimpulkan bahwa \(\lambda=1\) merupakan nilai eigen, kita perlu mengetahui bahwa \(A-I\) tidak invertibel.
Perhatikan persamaan \((A-I)\xvec = \evec_1\text{.}\) Jelaskan mengapa persamaan ini tidak mungkin konsisten dengan mengalikannya dengan \(S\) untuk memperoleh \(S(A-I)\xvec = S\evec_1\text{.}\)
Kita telah melihat beberapa model Internet yang rantai Markovnya, yang didefinisikan oleh matriks Google \(G\text{,}\) tidak konvergen ke vektor PageRank yang sesuai. Karena alasan ini, Google mendefinisikan matriks
Kita telah menyatakan bahwa Google memilih \(\alpha = 0.85\text{,}\) sehingga kita mungkin bertanya-tanya mengapa pilihan ini baik. Kita akan menelaah peran \(\alpha\) dalam latihan ini. Perhatikan model Internet yang dideskripsikan dalam Gambar 4.5.9 dan bentuklah matriks Google \(G\text{.}\) Dalam sel Sage di bawah, Anda dapat memasukkan matriks \(G\) dan memilih nilai \(\alpha\text{.}\)
Mari kita mulai dengan \(\alpha=0\text{.}\) Dengan pilihan ini, menjadi apakah matriks \(G'=\alpha G + (1-\alpha)H_n\text{?}\) Bentuklah rantai Markov menggunakan sel Sage di atas. Berapa banyak langkah yang diperlukan agar rantai Markov konvergen hingga ketelitian yang digunakan untuk menampilkan vektor-vektor \(\xvec_k\text{?}\)
Sekarang pilih \(\alpha=0.25\text{.}\) Berapa banyak langkah yang diperlukan agar rantai Markov konvergen hingga ketelitian yang digunakan untuk menampilkan vektor-vektor \(\xvec_k\text{?}\)
Eksperimen ini memberi kita sedikit wawasan tentang pemilihan \(\alpha\text{.}\) Semakin kecil \(\alpha\text{,}\) semakin cepat rantai Markov konvergen. Hal ini penting; karena matriks \(G'\) yang digunakan Google sangat besar, kita ingin meminimalkan jumlah suku rantai Markov yang perlu dihitung. Di sisi lain, ketika kita memperkecil \(\alpha\text{,}\) matriks \(G' = \alpha G + (1-\alpha)H_n\) mulai semakin menyerupai \(H_n\) dan semakin kurang menyerupai \(G\text{.}\) Nilai \(\alpha=0.85\) dipilih agar matriks \(G'\) cukup menyerupai \(G\text{,}\) sementara rantai Markovnya konvergen dalam jumlah langkah yang wajar.
Papan permainan ini terdiri atas 100 petak yang disusun dalam kisi \(10\times10\) dan diberi nomor 1 hingga 100. Terdapat pasangan petak yang dihubungkan oleh tangga dan pasangan yang dihubungkan oleh perosotan. Semua pemain mulai di petak 1 dan bergiliran melempar dadu. Pada gilirannya, pemain bergerak maju sebanyak jumlah petak yang ditunjukkan oleh dadu. Jika pemain tiba di petak pada dasar tangga, ia berpindah ke petak di puncak tangga. Jika pemain tiba di petak pada puncak perosotan, ia turun ke petak di dasar perosotan. Pemenangnya adalah pemain pertama yang mencapai petak 100.
Kita mulai dengan memainkan versi lebih sederhana dari permainan ini, yang hanya memiliki delapan petak tersusun dalam satu baris seperti ditunjukkan dalam Gambar 4.5.13 dan tidak memiliki perosotan maupun tangga. Alih-alih menggunakan dadu bersisi enam, kita akan melempar koin dan bergerak maju satu atau dua petak, bergantung pada hasil lemparan koin. Jika berada di petak 7, kita bergerak maju ke petak 8 apa pun hasil lemparan koin, dan jika berada di petak 8, kita akan tetap di sana selamanya.
Bentuklah matriks \(8\times8\)\(A\) yang mencatat probabilitas bahwa seorang pemain berpindah dari satu petak ke petak lain dalam satu giliran. Sebagai contoh, jika seorang pemain berada di petak 2, terdapat peluang 50% untuk berpindah ke petak 3 dan peluang 50% untuk berpindah ke petak 4 pada giliran berikutnya.
Karena kita memulai permainan di petak 1, vektor awalnya adalah \(\xvec_0 = \evec_1\text{.}\) Bentuklah beberapa suku rantai Markov \(\xvec_{k+1} = A\xvec_k\text{.}\)
Versi sederhana Chutes and Ladders dengan delapan kotak yang disusun dari kiri ke kanan. Petak paling kiri diberi label \(1\text{,}\) sedangkan petak berikutnya kosong. Petak-petak berikutnya diberi label \(2\text{,}\)\(3\text{,}\)\(4\text{,}\) dan \(5\text{.}\) Berikutnya terdapat petak kosong, lalu petak berlabel \(6\text{.}\) Terdapat panah dari petak kosong paling kiri menuju petak berlabel \(4\) yang menyatakan tangga. Terdapat pula panah dari petak kosong paling kanan menuju petak berlabel \(1\) yang menyatakan perosotan.
Meskipun terdapat delapan petak, kita hanya perlu menelaah enam di antaranya. Sebagai contoh, jika tiba di petak kosong pertama, kita naik ke petak 4. Demikian pula, jika tiba di petak kosong kedua, kita turun ke petak 1.
Sekali lagi, bentuklah matriks stokastik \(6\times6\) yang mencatat probabilitas kita berpindah dari satu petak ke petak lain dalam suatu giliran, lalu bentuklah beberapa suku rantai Markov yang diawali dengan \(\xvec_0=\evec_1\text{.}\)
Versi lengkap Chutes and Ladders yang memiliki 100 petak dapat dianalisis dengan cara yang sama. Tanpa perosotan atau tangga, jumlah rata-rata giliran yang diperlukan untuk mencapai petak 100 adalah 29.0. Setelah perosotan dan tangga ditambahkan kembali, jumlah rata-rata giliran yang diperlukan untuk mencapai petak 100 adalah 27.1. Hal ini menunjukkan bahwa jumlah rata-rata giliran tidak banyak berubah ketika perosotan dan tangga ditambahkan. Namun, kemungkinan hasilnya jauh lebih bervariasi karena petak 100 dapat dicapai jauh lebih cepat maupun jauh lebih lambat.
