berita

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Laporan Jantung Mesin

Editor: Jiaqi

Matriksnya sulit untuk dipahami, tetapi mungkin berbeda jika dilihat dari sudut pandang lain.

Saat mempelajari matematika, kita sering merasa frustrasi dengan kesulitan dan keabstrakan pengetahuan yang kita pelajari, namun terkadang, hanya dengan mengubah perspektif, kita dapat menemukan solusi sederhana dan intuitif terhadap masalah tersebut; Misalnya, saat kita masih kecil mempelajari rumus jumlah kuadrat (a+b)², kita mungkin tidak mengerti kenapa sama dengan a²+2ab+b² buku dan guru meminta kami untuk mengingatnya seperti ini sampai suatu hari kami melihat gambar animasi ini:

Tiba-tiba kami sadar bahwa kami dapat memahaminya dari sudut pandang geometris!

Sekarang, pencerahan ini muncul lagi: matriks non-negatif dapat diubah secara ekuivalen menjadi grafik berarah yang sesuai!

Seperti yang ditunjukkan pada gambar di bawah, matriks 3×3 di sebelah kiri sebenarnya dapat direpresentasikan secara ekuivalen sebagai graf berarah yang memuat tiga titik simpul di sebelah kanan, dan representasi ini sangat membantu baik untuk teori matriks maupun graf.

Contoh ini datang dari ahli matematika Tivadar Danka, yang berkomitmen membuat matematika dapat diakses oleh semua orang. Ahli matematika yang memproklamirkan dirinya sebagai "orang yang baik dan kacau" dengan jelas memperkenalkan kesetaraan matriks dan grafik serta penggunaannya dalam serangkaian tweet dan postingan blog. Sejauh ini, tweet tersebut telah dibaca lebih dari 2 juta kali, mendapat lebih dari 3.200 retweet dan 9.100 favorit.

Valensi matriks dan grafik berarah

Seperti yang ditunjukkan pada contoh di atas, jika kita memperlakukan setiap baris sebagai simpul, setiap elemen dapat direpresentasikan sebagai tepi yang terarah dan berbobot. Tentu saja, 0 elemen bisa diabaikan. Jika elemen terletak pada baris i dan kolom j, maka elemen tersebut berkorespondensi dengan tepi dari node i ke node j.

Pada pandangan pertama, ini mungkin tampak rumit, tapi kita bisa mulai dengan melihat salah satu node.

Seperti yang ditunjukkan pada gambar, untuk matriks 3x3 ini, baris 1 berhubungan dengan simpul paling atas (di sini kita menyebutnya simpul 1), yang berisi 3 elemen tetapi salah satunya adalah 0, sehingga simpul tersebut memanjang ke dua sisi. Tepi kuning melambangkan elemen 0,5 pada (1,1), sehingga merupakan tepi berarah yang menunjuk ke dirinya sendiri dengan bobot 0,5. Dengan cara yang sama, tepi biru adalah tepi yang menunjuk ke node 2 dan memiliki bobot 1.

Dengan cara ini, kita dapat menganalisis bahwa kolom ke-i dari matriks tersebut bersesuaian dengan semua sisi yang menunjuk ke simpul-i.

Apa gunanya representasi yang setara ini?

Kesetaraan antara matriks non-negatif dan grafik berarah tidak hanya dapat membantu kita lebih memahami matriks dan operasinya, namun juga membantu menyederhanakan beberapa proses penghitungan, hal ini juga dapat membantu kita memahami grafik dari perspektif baru;

Misalnya, pangkat suatu matriks berhubungan dengan jalan pada grafik.

Seperti yang ditunjukkan pada gambar di atas, untuk pangkat ke-k dari matriks persegi n×n A, proses penjumlahan setiap elemen akan mencakup semua kemungkinan langkah k-langkah.

Misalnya kita ingin mengkuadratkan matriks 3×3 di atas.

Jika menggunakan perkalian matriks, kita perlu menghitungnya seperti ini:

Untuk hasil operasi elemen pertama diperoleh hasil = 0,5×0,5+1×0,2+0×1,8 = 0,45. Akhirnya kita bisa mendapatkan hasil lengkapnya sebagai:

Namun, jika Anda menggunakan metode berjalan grafik di atas, Anda bisa mendapatkan hasilnya dengan menelusuri jalur tersebut. Demikian pula, untuk elemen pertama dari matriks hasil, perlu untuk menjumlahkan semua jalur berjalan 2 langkah yang sesuai dengan a_{1,l}→a_{l,1}.

Namun, jika grafik berarah ini mewakili keadaan rantai Markov, kuadrat matriks probabilitas transisinya pada dasarnya mewakili probabilitas rantai mencapai keadaan tertentu setelah 2 langkah.

Tidak hanya itu, merepresentasikan matriks dalam bentuk grafik juga dapat memberikan kita gambaran tentang struktur matriks non-negatif. Untuk melakukan hal ini, Danka mengatakan kita perlu terlebih dahulu memahami konsep “komponen yang terhubung kuat”.

Komponen yang terhubung kuat

Apa yang dimaksud dengan komponen yang terhubung kuat? Untuk graf berarah, jika setiap simpul lain dalam graf tersebut dapat dijangkau dari setiap simpul, maka graf tersebut dikatakan terhubung kuat. Seperti yang ditunjukkan di bawah ini.

Komponen terhubung kuat mengacu pada bagian/subgraf dalam graf berarah yang dapat mencapai konektivitas kuat. Seperti terlihat pada gambar di bawah, terdapat komponen terhubung kuat di kiri dan kanan, sedangkan tepi putih di tengah tidak termasuk komponen terhubung kuat.

Gambar di bawah menunjukkan contoh lain, dimana bagian kuning merupakan komponen yang terhubung kuat:

Matriks yang bersesuaian dengan graf terhubung kuat adalah matriks yang tidak dapat direduksi, sedangkan semua matriks lain dalam matriks tak-negatif adalah matriks yang dapat direduksi.

Danka menjelaskan dengan sebuah contoh. (Untuk mempermudah penjelasan, semua bobot dalam contoh adalah satuan bobot, namun dalam praktiknya, nilai bobot ini dapat berupa nilai non-negatif apa pun.)

Selanjutnya, grafik ini, yang berisi komponen-komponen yang terhubung kuat tetapi tidak terhubung kuat, diubah menjadi bentuk matriks yang sesuai:

Dan matriks ini merupakan matriks yang dapat direduksi.

Terlihat bahwa dua submatriks pada diagonal utama masing-masing mewakili dua komponen yang terhubung kuat, sedangkan submatriks di kanan atas mewakili tepi dari komponen terhubung kuat pertama ke komponen terhubung kuat kedua, dan submatriks di kiri bawah mewakili Mewakili sisi dari komponen terkoneksi kuat ke-2 hingga komponen terkoneksi kuat ke-1 (karena tidak ada sisi seperti itu, semuanya bernilai 0).

Bentuk penulisan matriks blok ini disebut bentuk normal Frobenius.

Jadi, kita tentu bertanya: Bisakah kita mengubah matriks non-negatif menjadi matriks kanonik Frobenius?

Dengan menggunakan grafik berarah untuk merepresentasikan matriks non-negatif, kita dapat dengan mudah melihat bahwa jawabannya adalah ya, karena setiap graf berarah yang mewakili matriks non-negatif dapat direpresentasikan sebagai komponen-komponen yang terhubung kuat dan terhubung satu sama lain. Prosesnya sangat sederhana:

1. Buatlah grafik berarah yang sesuai untuk matriks non-negatif;
2. Temukan komponen yang terhubung kuat;
3. Temukan cara yang lebih baik untuk memberi label pada setiap node.

Dan Anda sudah selesai!

Gunakan grafik untuk mendapatkan bentuk standar Frobenius

Jadi, cara apa yang lebih baik?

Berdasarkan contoh di atas, mari kita lihat prosesnya.

Pertama, masing-masing komponen yang terhubung kuat digabungkan menjadi satu objek, seperti yang ditunjukkan pada gambar di bawah. Saat ini, kita dapat memperlakukan setiap komponen yang terhubung kuat sebagai kotak hitam - kita tidak peduli dengan struktur internalnya, hanya koneksi eksternalnya.

Kemudian, pada grafik baru ini, kita perlu mencari komponen yang hanya memiliki sisi keluar tetapi tidak memiliki sisi masuk. Hanya ada satu dalam contoh spesifik ini, yang kami beri label nomor 0:

Langkah selanjutnya yang lebih merepotkan: beri nomor pada setiap komponen sehingga jumlah setiap komponen berada pada jarak terjauh dari angka 0. Contoh berikut menggambarkan hal ini dengan lebih jelas:

Terlihat terdapat dua jalur dari angka 0 ke komponen tengah, maka pilihlah jalur yang paling jauh dari angka 0 ke komponen tengahnya. Akhirnya mendapat:

Akibatnya, ini menentukan urutan komponen. Selanjutnya tandai node internal setiap komponen:

Jika grafik itu sendiri berasal dari sebuah matriks, proses pelabelan ulang tersebut menghasilkan matriks kanonik Frobenius!

Faktanya, proses pelabelan ulang ini menggunakan matriks permutasi P untuk mengubah matriks asli, dan matriks permutasi tersebut terdiri dari produk beberapa matriks yang ditransposisikan.

Berikut bentuk lengkap teorema tersebut:

Tentu saja, penggunaan grafik untuk merepresentasikan matriks lebih dari itu. Misalnya, kita juga dapat menggunakan nilai eigen matriks untuk menentukan nilai eigen grafik. Faktanya, pemikiran ini memunculkan bidang penelitian teori grafik spektral.

Kesimpulan

Tentunya hubungan ekivalensi antara matriks dan graf ini tidak hanya berguna untuk penelitian teori graf, tetapi juga memberikan perspektif baru dalam penghitungan dan analisis aljabar linier. Ini juga memiliki beberapa kegunaan praktis yang penting. Misalnya, data DNA sering direpresentasikan dalam bentuk matriks atau grafik.

Selain itu, kita semua mengetahui pentingnya operasi matriks untuk AI model besar saat ini, dan grafik yang diwakili oleh grafik pengetahuan menjadi pendorong penting AI saat ini melalui teknologi seperti pencarian yang ditingkatkan pengambilannya. Menghubungkan keduanya dapat membawa beberapa terobosan baru dalam interpretasi AI dan kecerdasan buatan grafik. Setidaknya, ini membantu kita mempelajari aljabar linier dengan lebih baik.

Sebenarnya konten di atas diambil dari buku "Mathematics of Machine Learning" yang ditulis Tivadar Danka. Buku ini akan memperkenalkan pengetahuan matematika terkait pembelajaran mesin dari tingkat sederhana hingga mendalam, sehingga pembaca dapat benar-benar memahami apa itu pembelajaran mesin dan mengapa hal itu dilakukan. Danka dengan yakin menyatakan bahwa ini akan menjadi "sumber daya terbaik untuk mempelajari pembelajaran mesin". Saat ini, ia telah merilis dua bab pratinjau secara online. Pembaca yang tertarik dapat mengunjungi: https://tivadardanka.com/mathematics-of-machine-learning-preview/