2024-08-19
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Koneen sydänraportti
Toimittaja: Jiaqi
Matriisia on vaikea ymmärtää, mutta se voi olla erilainen, jos katsot sitä toisesta näkökulmasta.
Matematiikkaa oppiessamme olemme usein turhautuneita opitun tiedon vaikeudesta ja abstraktisuudesta, mutta joskus voimme löytää yksinkertaisen ja intuitiivisen ratkaisun ongelmaan. Esimerkiksi, kun opimme lapsina neliöiden summan kaavaa (a+b)², emme ehkä ymmärrä, miksi se on yhtä suuri kuin a²+2ab+b². Tiedämme vain, että se on kirjoitettu näin kirja ja opettaja pyysi meitä muistamaan sen näin, kunnes eräänä päivänä näemme Saimme tämän animoidun kuvan:
Yhtäkkiä tajusimme, että voimme ymmärtää sen geometrisesta näkökulmasta!
Nyt tämä valaistumisen tunne ilmenee jälleen: ei-negatiivinen matriisi voidaan vastaavasti muuntaa vastaavaksi suunnatuksi graafiksi!
Kuten alla olevasta kuvasta näkyy, vasemmanpuoleinen 3×3 matriisi voidaan itse asiassa esittää vastaavasti suunnattuna graafina, joka sisältää kolme solmua oikealla, ja tämä esitys on erittäin hyödyllinen sekä matriisi- että graafiteoriassa.
Tämä esimerkki on peräisin matemaatikko Tivadar Dankalta, joka on sitoutunut tekemään matematiikasta kaikkien saatavilla. Itse julistautunut "kaoottiseksi hyväksi" matemaatikko esitteli elävästi tämän matriisien ja kaavioiden vastaavuuden ja niiden käytön tviiteissä ja blogikirjoituksissa. Tähän mennessä nämä tweetit on luettu yli 2 miljoonaa kertaa, ne ovat saaneet yli 3 200 uudelleentwiittaa ja 9 100 suosikkia.
Matriisien ja suunnattujen graafien valenssi
Kuten yllä olevassa esimerkissä näkyy, jos käsittelemme jokaista riviä solmuna, jokainen elementti voidaan esittää suunnattuna ja painotettuna reunana. Tietenkin 0 elementtiä voidaan jättää huomiotta. Jos elementti sijaitsee rivillä i ja sarakkeessa j, se vastaa reunaa solmusta i solmuun j.
Ensi silmäyksellä tämä saattaa tuntua monimutkaiselta, mutta voimme aloittaa tarkastelemalla yhtä solmuista.
Kuten kuvasta näkyy, tässä 3×3 matriisissa rivi 1 vastaa ylintä solmua (kutsumme sitä tässä solmuksi 1), joka sisältää 3 elementtiä, mutta yksi niistä on 0, joten solmu ulottuu ulos kaksi sivua. Keltainen reuna edustaa elementtiä 0,5 kohdassa (1,1), joten se on itseensä osoittava suunnattu reuna painolla 0,5. Samalla tavalla sininen reuna on reuna, joka osoittaa solmuun 2 ja jonka paino on 1.
Tällä tavalla voidaan analysoida, että matriisin i. sarake vastaa kaikkia i-solmuun osoittavia reunoja.
Mitä hyötyä tästä vastaavasta esityksestä on?
Tämä ei-negatiivisten matriisien ja suunnattujen graafien välinen vastaavuus voi auttaa meitä ymmärtämään paremmin matriiseja ja niiden toimintoja, vaan myös yksinkertaistaa joitain laskentaprosesseja. Tämä voi myös auttaa meitä ymmärtämään kuvaajia uudesta näkökulmasta.
Esimerkiksi matriisin potenssit vastaavat käyriä kaaviossa.
Kuten yllä olevasta kuvasta näkyy, n × n neliömatriisin A k:nnelle potenssille kunkin elementin summausprosessi sisältää kaikki mahdolliset k-askelmat.
Oletetaan esimerkiksi, että haluamme neliöttää yllä olevan 3×3-matriisin.
Jos käytät matriisikertoa, meidän on laskettava se seuraavasti:
Operaatiotuloksen ensimmäiselle elementille saadaan tulos = 0,5×0,5+1×0,2+0×1,8 = 0,45. Lopuksi voimme saada täydellisen tuloksen seuraavasti:
Jos kuitenkin käytät yllä olevaa kuvaajakävelymenetelmää, voit saada tulokset kävelemällä polkua. Vastaavasti tulosmatriisin ensimmäiselle elementille on tarpeen laskea yhteen kaikki 2-vaiheiset kävelyreitit, jotka vastaavat muotoa a_{1,l}→a_{l,1}.
Jos tämä suunnattu graafi kuitenkin edustaa Markovin ketjun tilaa, sen siirtymän todennäköisyysmatriisin neliö edustaa oleellisesti todennäköisyyttä, että ketju saavuttaa tietyn tilan 2 askeleen jälkeen.
Sen lisäksi, että matriisien esittäminen graafina voi myös antaa meille käsityksen ei-negatiivisten matriisien rakenteesta. Tätä varten Danka sanoi, että meidän on ensin ymmärrettävä "vahvasti kytkettyjen komponenttien" käsite.
Vahvasti kytketty komponentti
Mikä on vahvasti kytketty komponentti? Suunnatun graafin kohdalla, jos graafin joka toinen solmu on saavutettavissa jokaisesta solmusta, sanotaan, että graafi on vahvasti yhteydessä. Kuten alla näkyy.
Vahvasti yhdistetty komponentti viittaa suunnatun graafin osaan/aligraafiin, joka voi saavuttaa vahvan liitettävyyden. Kuten alla olevasta kuvasta näkyy, vasemmalla ja oikealla on vahvasti kytketty komponentti, kun taas valkoinen reuna keskellä ei kuulu mihinkään vahvasti toisiinsa liittyvään komponenttiin.
Alla olevassa kuvassa on toinen esimerkki, jossa keltainen osa on vahvasti kytketty komponentti:
Vahvasti yhdistettyä graafia vastaava matriisi on pelkistymätön matriisi, kun taas kaikki muut ei-negatiivisen matriisin matriisit ovat pelkistyviä matriiseja.
Danka selittää esimerkillä. (Selityksen yksinkertaisuuden vuoksi kaikki esimerkin painot ovat yksikköpainoja, mutta käytännössä nämä painoarvot voivat olla mitä tahansa ei-negatiivisia arvoja.)
Seuraavaksi tämä graafi, joka sisältää vahvasti toisiinsa liittyvät komponentit, mutta ei itse ole vahvasti kytketty, muunnetaan vastaavaan matriisimuotoon:
Ja tämä matriisi on pelkistävä matriisi.
Voidaan nähdä, että päädiagonaalin kaksi alimatriisia edustavat vastaavasti kahta vahvasti toisiinsa liittyvää komponenttia, kun taas oikeassa yläkulmassa oleva alimatriisi edustaa reunaa ensimmäisestä vahvasti kytketystä komponentista toiseen vahvasti yhdistettyyn komponenttiin, ja alimatriisi vasemmalla edustaa. Edustaa reunaa toisesta vahvasti kytketystä komponentista 1. vahvasti yhdistettyyn komponenttiin (koska sellaista reunaa ei ole, se on kaikki 0).
Tätä lohkomatriisin kirjoitusmuotoa kutsutaan Frobeniuksen normaalimuodoksi.
Joten kysymme luonnollisesti: Voimmeko muuntaa minkä tahansa ei-negatiivisen matriisin Frobeniuksen kanoniseksi matriisiksi?
Käyttämällä suunnattua graafia edustamaan ei-negatiivista matriisia, voimme helposti nähdä, että vastaus on kyllä, koska mikä tahansa ei-negatiivista matriisia edustava suunnattu graafi voidaan esittää vahvasti toisiinsa liittyvinä komponentteina, jotka ovat yhteydessä toisiinsa. Prosessi on hyvin yksinkertainen:
Ja olet valmis!
Käytä kaavioita saadaksesi Frobenius-standardilomakkeen
Joten mikä tämä on parempi tapa?
Katsotaanpa prosessia yllä olevan esimerkin perusteella.
Ensin yksittäiset vahvasti kytketyt komponentit sulatetaan yhdeksi esineeksi alla olevan kuvan mukaisesti. Tällä hetkellä voimme käsitellä jokaista vahvasti kytkettyä komponenttia mustana laatikkona - emme välitä sen sisäisestä rakenteesta, vain sen ulkoisista liitännöistä.
Sitten tässä uudessa kaaviossa meidän on löydettävä komponentit, joilla on vain lähteviä reunoja, mutta ei saapuvia reunoja. Tässä esimerkissä on vain yksi, jonka merkitsemme numerolla 0:
Seuraava vaihe on hankalampi: numeroi jokainen komponentti niin, että kunkin komponentin numero on kauimpana numerosta 0. Seuraava esimerkki havainnollistaa tätä asiaa selkeämmin:
Voidaan nähdä, että numerosta 0 keskikomponenttiin on kaksi polkua, joten valitse numerosta 0 kauimpana oleva polku. Lopulta saatiin:
Käytännössä tämä määrittää komponenttien järjestyksen. Merkitse seuraavaksi kunkin komponentin sisäiset solmut:
Jos itse graafi tulee matriisista, tällainen uudelleenmerkintäprosessi johtaa Frobenius-kanoniseen matriisiin!
Itse asiassa tässä uudelleenmerkintäprosessissa käytetään permutaatiomatriisia P muuttamaan alkuperäinen matriisi, ja permutaatiomatriisi koostuu useiden transponoitujen matriisien tulosta.
Seuraava on lauseen täydellinen muoto:
Tietenkin graafien käyttö matriisien esittämiseen menee paljon pidemmälle. Esimerkiksi matriisin ominaisarvoja voidaan käyttää graafin ominaisarvojen määrittämiseen. Itse asiassa tämä ajattelutapa sai aikaan spektrigraafiteorian tutkimuskentän.
Johtopäätös
Ilmeisesti tämä matriisien ja graafien välinen ekvivalenssisuhde ei ole vain hyödyllinen graafiteoriatutkimukselle, vaan se tarjoaa myös uuden näkökulman lineaarisen algebran laskemiseen ja analysointiin. Sillä on myös tärkeitä käytännön käyttötarkoituksia. Esimerkiksi DNA-tiedot esitetään usein matriisin tai graafin muodossa.
Lisäksi me kaikki tiedämme matriisioperaatioiden tärkeyden nykyiselle suuren mallin tekoälylle, ja tietokaavioiden edustamista kaavioista on tulossa tärkeä nykyisen tekoälyn ajuri tekniikoiden, kuten hakutehostetun haun, ansiosta. Näiden kahden yhdistäminen voi tuoda uusia läpimurtoja tekoälyn tulkittavuuteen ja kuvaajien tekoälyyn. Ainakin tämä auttaa meitä oppimaan lineaarista algebraa paremmin.
Itse asiassa yllä oleva sisältö on poimittu Tivadar Dankan kirjoittamasta kirjasta "Mathematics of Machine Learning". Tämä kirja esittelee koneoppimiseen liittyvän matemaattisen tiedon yksinkertaisesta syvälle tasolle, jolloin lukijat voivat todella ymmärtää, mitä se on ja miksi se tehdään, Danka vakuuttaa, että tämä on "paras resurssi koneoppimisen oppimiseen". Tällä hetkellä hän on julkaissut verkossa kaksi luvun esikatselua: https://tivadardanka.com/mathematics-of-machine-learning-preview/.
Kerää ja järjestele viimeisimmät uutiset ja tee ne kaikkien tarkastettavaksi ilmaiseksi.
