Giriş
Matematikçiler iyi bir bulmacayı sever. Çarpan matrisler (iki boyutlu sayı tabloları) kadar soyut bir şey bile, onu yapmanın en etkili yolunu bulmaya çalıştığınızda bir oyun gibi gelebilir. Bu biraz Rubik Küpünü mümkün olan en az hamlede çözmeye çalışmak gibidir - zorlu ama çekici. Bunun dışında Rubik Küpü için her adımda olası hamle sayısı 18'dir; matris çarpımı için, nispeten basit durumlarda bile, her adım 10'dan fazla sunabilir12 seçenekleri.
Son 50 yılda, araştırmacılar bu soruna, tümü insan sezgisi tarafından desteklenen bilgisayar araştırmalarına dayanan birçok şekilde yaklaştılar. Geçen ay, yapay zeka şirketi DeepMind'daki bir ekip, sorunun yeni bir yönden nasıl çözüleceğini gösterdi. kâğıt in Tabiat matris çarpımı için yeni hızlı algoritmalar keşfetmek üzere bir sinir ağını başarıyla eğittiklerini. Sanki yapay zeka, korkunç derecede karmaşık bir Rubik Küpünü çözmek için bilinmeyen bir strateji bulmuş gibiydi.
"Çok temiz bir sonuç" dedi Josh Alman, Columbia Üniversitesi'nde bir bilgisayar bilimcisi. Ancak o ve diğer matris çarpım uzmanları, bu tür bir yapay zeka yardımının mevcut yöntemlerin yerini almak yerine en azından yakın vadede tamamlayıcı olacağını vurguladı. Alman, "Çığır açabilecek bir şey için bir kavram kanıtı gibi," dedi. Sonuç, araştırmacılara arayışlarında yardımcı olacaktır.
Sanki bunu kanıtlamak istercesine, olaydan üç gün sonra Tabiat kağıt çıktı, bir çift Avusturyalı araştırmacı yeni ve eski yöntemlerin birbirini nasıl tamamlayabileceğini gösterdi. için geleneksel bir bilgisayar destekli arama kullandılar. daha fazla geliştirmek sinir ağının keşfettiği algoritmalardan biri.
Sonuçlar, bir Rubik Küpü çözme süreci gibi, daha iyi algoritmalara giden yolun kıvrımlı ve dönüşlerle dolu olacağını gösteriyor.
Çarpan Matrisler
Matris çarpımı, tüm matematiğin en temel ve her yerde bulunan işlemlerinden biridir. bir çifti çoğaltmak için n-By-n matrisler, her biri n2 öğeleri, çarparsınız ve ürünü oluşturmak için bu öğeleri belirli kombinasyonlarda bir araya getirirsiniz, üçüncüsü n-By-n matris. İkiyi çarpmak için standart tarif n-By-n matrisler gerektirir n3 çarpma işlemleri, örneğin 2'ye 2'lik bir matris sekiz çarpma gerektirir.
Binlerce satır ve sütun içeren daha büyük matrisler için bu işlem hızla hantal hale gelir. Ancak 1969'da matematikçi Volker Strassen bir prosedür keşfetti sekiz yerine yedi çarpma adımı kullanarak bir çift 2'ye 2 matrisi çarpmak için, daha fazla toplama adımı sunma pahasına.
Sadece bir çift 2'ye 2 matrisi çarpmak istiyorsanız, Strassen'in algoritması gereksiz yere karmaşıktır. Ancak bunun daha büyük matrisler için de işe yarayacağını fark etti. Bunun nedeni, bir matrisin elemanlarının kendilerinin de matris olabilmesidir. Örneğin, 20,000 satır ve 20,000 sütun içeren bir matris, dört öğesinin her biri 2'e 2 matris olan 10,000'ye 10,000'lik bir matris olarak yeniden tasarlanabilir. Bu matrislerin her biri daha sonra 5,000'e 5,000'lik dört bloğa bölünebilir ve bu böyle devam eder. Strassen, yöntemini bu iç içe geçmiş hiyerarşinin her seviyesinde 2'ye 2 matrisleri çarpmak için uygulayabilirdi. Matris boyutu arttıkça, daha az sayıda çarpmadan elde edilen tasarruf da artar.
Strassen'in keşfi, o zamandan beri iki farklı alt alana ilham veren matris çarpımı için verimli algoritmalar arayışına yol açtı. Biri bir ilke sorununa odaklanıyor: İkiyi çarpmayı hayal ederseniz n-By-n matrisler ve let n sonsuza doğru koşarken, mümkün olan en hızlı algoritmadaki çarpma adımlarının sayısı ile nasıl ölçeklenir? n? şuan ki kayıt en iyi ölçeklendirme için, n2.3728596, Alman'a ait ve Virginia Vasilevska Williams, Massachusetts Institute of Technology'de bir bilgisayar bilimcisi. (Yakın zamanda yayınlanmamış ön baskı yeni bir teknik kullanarak küçük bir gelişme bildirdi.) Ancak bu algoritmalar, yalnızca saçma sapan büyük matrisler için Strassen'inki gibi yöntemlere üstün gelen, tamamen teorik açıdan ilgi çekicidir.
İkinci alt alan daha küçük ölçekte düşünür. Strassen'in çalışmasından kısa bir süre sonra, İsrailli Amerikalı bilgisayar bilimcisi Shmuel Winograd gösterdi Strassen teorik bir sınıra ulaştı: 2'ye 2 matrisleri yediden az çarpma adımıyla çarpmak mümkün değil. Ancak diğer tüm matris boyutları için, gereken minimum çarpma sayısı açık bir soru olarak kalır. Ve küçük matrisler için hızlı algoritmalar, çok büyük bir etkiye sahip olabilir, çünkü böyle bir algoritmanın tekrarlanan yinelemeleri, makul boyuttaki matrisler çarpılırken Strassen'in algoritmasını yenebilir.
Ne yazık ki, olasılıkların sayısı çok fazla. 3'e 3 matrisler için bile, "olası algoritmaların sayısı evrendeki atom sayısını aşıyor" dedi. El Hüseyin Fevzi, bir DeepMind araştırmacısı ve yeni çalışmanın liderlerinden biri.
Bu baş döndürücü seçenekler menüsüyle karşı karşıya kalan araştırmacılar, matris çarpımını tamamen farklı bir matematik problemine dönüştürerek ilerleme kaydettiler - bilgisayarların halletmesi daha kolay bir problem. İki matrisi çarpmanın soyut görevini belirli bir tür matematiksel nesne olarak temsil etmek mümkündür: tensör adı verilen üç boyutlu bir sayı dizisi. Araştırmacılar daha sonra bu tensörü "sıra-1" tensörler adı verilen bir dizi temel bileşene ayırabilir; bunların her biri karşılık gelen matris çarpma algoritmasında farklı bir adımı temsil edecektir. Bu, verimli bir çarpma algoritması bulmanın, bir tensör ayrışımındaki terim sayısını en aza indirme anlamına geldiği anlamına gelir - terimler ne kadar azsa, ilgili adımlar o kadar az olur.
Bu sayede araştırmacılar yeni algoritmalar çoğalan n-By-n standarttan daha azını kullanan matrisler n3 birçok küçük matris boyutu için çarpma adımları. Ancak, yalnızca standardı değil, aynı zamanda Strassen'in küçük matrisler için algoritmasını da geride bırakan algoritmalar, şimdiye kadar erişilemez durumdaydı.
Oyun hakkında
DeepMind ekibi, tensör ayrıştırmasını tek oyunculu bir oyuna çevirerek soruna yaklaştı. 2016'da başka bir DeepMind yapay zekası olan AlphaGo'dan türetilen bir derin öğrenme algoritmasıyla başladılar. masa oyunu Go oynamayı öğrendim en iyi insan oyuncuları yenecek kadar iyi.
Tüm derin öğrenme algoritmaları, sinir ağları etrafında inşa edilmiştir: yapay nöron ağları, her bir nöronun bir sonraki katmandakileri ne kadar etkilediğini temsil eden güçte değişebilen bağlantılarla katmanlara ayrılmıştır. Bu bağlantıların gücü, sinir ağının aldığı her girdiyi, algoritmanın genel amacını gerçekleştirmesine yardımcı olan bir çıktıya dönüştürmeyi öğrendiği bir eğitim prosedürünün birçok yinelemesinde ince ayar yapılır.
DeepMind'in AlphaTensor adlı yeni algoritmasında, girdiler geçerli bir matris çarpım şemasına giden yoldaki adımları temsil ediyor. Sinir ağına ilk girdi, orijinal matris çarpım tensörüdür ve çıkışı, AlphaTensor'un ilk hareketi için seçtiği sıra-1 tensörüdür. Algoritma, bu sıra-1 tensörünü ilk girdiden çıkararak, ağa yeni bir girdi olarak geri beslenen güncellenmiş bir tensör verir. Süreç, başlangıç tensöründeki her öğe sıfıra indirilene kadar tekrar eder, yani çıkarılacak daha fazla 1. sıra tensör kalmaz.
Bu noktada sinir ağı geçerli bir tensör ayrışımı keşfetmiştir, çünkü 1. sıradaki tüm tensörlerin toplamının başlangıç tensörüne tam olarak eşit olduğu matematiksel olarak garanti edilmiştir. Ve oraya ulaşmak için attığı adımlar, karşılık gelen matris çarpma algoritmasının adımlarına geri çevrilebilir.
İşte oyun: AlphaTensor, bir tensörü art arda bir sıra 1 bileşen kümesine ayrıştırır. AlphaTensor her seferinde adım sayısını azaltmanın bir yolunu bulursa ödüllendirilir. Ancak zafere giden kısayollar hiç de sezgisel değildir, tıpkı bazen her şeyi çözebilmeniz için bir Rubik Küpünde mükemmel şekilde sıralanmış bir yüzü karıştırmanız gerektiği gibi.
Ekibin artık teorik olarak problemlerini çözebilecek bir algoritması vardı. Önce onu eğitmeleri gerekiyordu.
Yeni Yollar
Tüm nöral ağlar gibi, AlphaTensor üzerinde çalışmak için çok fazla veriye ihtiyaç duyar, ancak tensör ayrışımı, herkesin bildiği gibi zor bir problemdir. Araştırmacıların ağı besleyebileceği birkaç verimli ayrıştırma örneği vardı. Bunun yerine, algoritmayı çok daha kolay ters problem üzerinde eğiterek başlamasına yardımcı oldular: bir grup rastgele oluşturulmuş sıra-1 tensörü toplamak.
"Zor sorun için daha fazla veri üretmek için kolay sorunu kullanıyorlar" dedi Michael Litman, Brown Üniversitesi'nde bir bilgisayar bilimcisi. Bu geriye dönük eğitim prosedürünü takviyeli öğrenmeyle birleştirmek, burada AlphaTensor verimli ayrıştırmalar ararken hata yaparken kendi eğitim verilerini oluşturdu, her iki eğitim yönteminden de kendi başına çok daha iyi çalıştı.
DeepMind ekibi, 12'ye 12'ye kadar matrislerin çarpımını temsil eden tensörleri ayrıştırması için AlphaTensor'u eğitti. Sıradan gerçek sayıların matrislerini çarpmak için hızlı algoritmalar ve ayrıca modulo 2 aritmetiği olarak bilinen daha kısıtlı bir ayara özgü algoritmalar aradı. (Bu, yalnızca iki sayıya dayalı bir matematiktir, bu nedenle matris öğeleri yalnızca 0 veya 1 ve 1 + 1 = 0 olabilir.) Araştırmacılar, burada keşfedilen algoritmaların uyarlanabileceğini umarak genellikle bu daha sınırlı ancak yine de geniş alanla başlar. gerçek sayıların matrisleri üzerinde çalışmak.
Eğitimden sonra AlphaTensor, Strassen'in algoritmasını dakikalar içinde yeniden keşfetti. Ardından, her bir matris boyutu için binlerce yeni hızlı algoritma keşfetti. Bunlar, en iyi bilinen algoritmalardan farklıydı ancak aynı sayıda çarpma adımına sahipti.
Birkaç durumda, AlphaTensor mevcut rekorları bile geçti. En şaşırtıcı keşifleri, 2'e 4 matrisleri 4 çarpma adımında çarpmak için yeni bir algoritma bulduğu modulo 47 aritmetiğinde oldu, Strassen'in algoritmasının iki tekrarı için gereken 49 adım üzerinde bir gelişme. Ayrıca, 5'e 5 modulo 2 matrisleri için en iyi bilinen algoritmayı yendi ve gerekli çarpma sayısını önceki 98'den 96'ya düşürdü. Strassen'in 91'e 5 matris kullanan algoritması.)
Yeni yüksek profilli sonuç, büyük bir heyecan yarattı. bazı araştırmacılar statükodaki yapay zeka tabanlı iyileştirmeye övgüler yağdırıyor. Ancak matris çarpımı topluluğundaki herkes o kadar etkilenmedi. Vassilevska Williams, "Biraz abartılmış gibi hissettim" dedi. “Bu başka bir araç. 'Oh, bilgisayarlar insanları yener' gibi değil, anlıyor musunuz?
Araştırmacılar ayrıca, rekor kıran 4'e 4 algoritmasının anlık uygulamalarının sınırlı olacağını vurguladı: Yalnızca modulo 2 aritmetiğinde geçerli değil, gerçek hayatta hızın yanı sıra önemli hususlar da var.
Fawzi, bunun gerçekten başlangıç olduğunu kabul etti. "Geliştirme ve araştırma için çok yer var ve bu iyi bir şey" dedi.
Son Bir Dönüş
AlphaTensor'un köklü bilgisayar arama yöntemlerine göre en büyük gücü, aynı zamanda en büyük zayıflığıdır: İyi algoritmaların neye benzediği konusunda insan sezgileri tarafından kısıtlanmaz, bu nedenle seçimlerini açıklayamaz. Bu, araştırmacıların başarılarından ders almasını zorlaştırıyor.
Ancak bu göründüğü kadar büyük bir dezavantaj olmayabilir. AlphaTensor sonucundan birkaç gün sonra, matematikçi Manuel Kauers ve onun yüksek lisans öğrencisi Jakob Moosbauer, her ikisi de Avusturya'daki Johannes Kepler Üniversitesi Linz'den bir adım daha ileri gittiğini bildirdi.
Giriş
DeepMind makalesi çıktığında, Kauers ve Moosbauer, geleneksel bir bilgisayar destekli arama kullanarak yeni çarpma algoritmaları arama sürecindeydiler. Ancak, yeni bir yol gösterici ilkeyle yeniden başlayan bu tür aramaların çoğundan farklı olarak, yöntemleri, daha fazla çarpma tasarrufu elde etme umuduyla var olan bir algoritmayı tekrar tekrar değiştirerek çalışır. AlphaTensor'un 5'e 5 modulo 2 matrisleri için algoritmasını başlangıç noktası olarak alarak, yöntemlerinin yalnızca birkaç saniyelik hesaplamadan sonra çarpma adımlarının sayısını 96'dan 95'e düşürdüğünü görünce şaşırdılar.
AlphaTensor ayrıca dolaylı olarak başka bir iyileştirme yapmalarına yardımcı oldu. Daha önce Kauers ve Moosbauer, Strassen'in algoritmasının iki yinelemesini geçmenin mümkün olmayacağına inandıkları için 4'e 4 matris uzayını keşfetme zahmetine girmemişlerdi. AlphaTensor sonucu onları yeniden düşünmeye sevk etti ve sıfırdan başlayan bir haftalık hesaplama süresinden sonra, yöntemleri AlphaTensor'un keşfettiği ile ilgisi olmayan başka bir 47 adımlı algoritma ortaya çıkardı. Kauers, "Birisi bize 4'e 4 için keşfedilecek bir şey olduğunu söyleseydi, bunu daha önce yapabilirdik" dedi. "Ama tamam, işte böyle işliyor."
Littman, durumu ilk kez bir koşucunun bir mili dört dakikadan kısa sürede bitirmesine benzeterek, bu tür sürprizlerin daha fazlasını bekliyor, bu büyük ölçüde imkansız kabul edilen bir başarı. "İnsanlar 'Oh, bekle, bunu yapabiliriz' gibiydi ve şimdi birçok insan bunu yapabiliyor" dedi.
İleriye dönük olarak Fawzi, AlphaTensor'u daha geniş bir matematiksel ve hesaplamalı görev yelpazesiyle başa çıkmak için genelleştirmeyi umuyor, tıpkı atası AlphaGo'nun sonunda diğer oyunlara dalması gibi.
Kauers bunu, makine öğreniminin yeni algoritmalar keşfetmeye uygulanması için gerçek bir turnusol testi olarak görüyor. Hızlı matris çarpma algoritmaları arayışının, insan yardımı olsun ya da olmasın bilgisayar aramalarının çok uygun olduğu bir kombinatoryal problem olduğuna dikkat çekiyor. Ancak tüm matematik problemlerini tespit etmek o kadar kolay değildir. Makine öğrenimi niteliksel olarak yeni bir algoritmik fikir keşfedebilirse, "o zaman bu bir oyun değiştirici olur" dedi.
