Geçen hafta, GPT-5.6 ve Claude Fable, 2000'lerden 2010'lara kadar yoğun biçimde üzerinde çalışılan ve benim de kaygılı bir birinci sınıf doktora öğrencisiyken kısaca uğraştığım, kablosuz iletişimdeki açık bir teorik soruyu çözmüş görünüyor. Cevap nihayet geldi, belki de çünkü soruyu soran son birkaç kişiden biriydim ve makineleri çözmeye yönlendiren ilk kişiydim 😊
Sonuç: N biti, N×N Gauss kablosuz kanalı üzerinden gönderiyorsunuz ve alıcının hepsini hatasız bir şekilde geri kazanması gerekiyor. 2000'lerden beri, sinyal-gürültü oranı en az 2 log N olduğunda bunun bilgi kuramsal olarak mümkün olduğu biliniyordu. Ancak buna ulaşan tek bilinen yöntem üstel bir arama algoritmasıydı. Artık basit, polinom zamanlı bir algoritmanın tam olarak aynı eşikte başarılı olduğuna dair kanıt mevcut.
Size biraz daha detaylı anlatayım.
2009'da, kısa süre sonra doktora danışmanım olan Alex Dimakis (@AlexGDimakis) ile ilk makalem üzerinde çalıştım (o makale sayesinde değil):
Bu makale, MIMO sezimine polinom zamanlı bir çözüm sunmaya yönelik birçok girişimden biriydi.
MIMO sezimi nedir diye soruyorsunuz?
Bir verici, N bitlik bir vektörü, N verici ve N alıcı antenli kablosuz kanal üzerinden gönderir. Kanal, bitleri birbirine karıştırır ve gürültü ekler. Kanal matrisini bilen alıcı, hangi bitlerin gönderildiğini bulmak zorundadır.
Blok hatası açısından optimal alıcı, diğer adıyla maksimum olabilirlik (ML) sezici, bu sorunu, alınan sinyal veriyken gönderilmiş olabilecek en olası vektörü bularak tam olarak çözer. Bu durumda, ML sezimi şu temel ayrık en küçük kareler problemini çözmeye indirgenir:
Ne yazık ki, hayattaki tüm güzel problemler gibi… ML sezimi NP-zordur.
Yine de biz TCS karamsarları değiliz ve kablosuz kanallar en kötü durumda değildir; onlar rastgeledir ve topluluk 2000'lerin başından beri şu soru üzerinde çalışıyordu:
Gönderilen bitleri istatistiksel olarak geri kazanmak mümkün olduğunda, bunu polinom zamanda yapabilir miyiz?
2010'daki o makalede bu soru üzerinde pek ilerleme kaydedemedik ve alandaki onca çalışmaya rağmen, sorun anladığım kadarıyla 2001'den beri açık kaldı… yani daha dramatik olması için söylersek, ÇEYREK YÜZYILDIR.
Ta ki geçen haftaya kadar. Ve nihai cevap şu:
EVET! Tam sezim istatistiksel olarak mümkün olduğunda, bunu polinom zamanda yapabilirsiniz.
MIMO çözüldü; Bitti.
Ama kimin umurunda? Buna birazdan geri döneceğiz.
Makaleyi ekliyorum ve ispatları ve anlatımı sadeleştirmek için modellerle 5+ gün boyunca ileri geri gittim (ki bu başlangıçta tam bir felaketti). Bu süreç, GPT'nin ürettiği ilk ispattan (yaklaşık 30 dakika sürmüştü) çok çok daha uzun sürdü. İspat uzun ama nispeten temel düzeyde. Her şeyi doğruladım ve elimden geldiğince kontrol ettim; doğru.
Şimdi problemden ve tarihçesinden biraz daha bahsedeyim ve alan bu MIMO sezim teorisinin bu spesifik köşesinden uzaklaşmış olsa da bunun hakkında yazmaya değer olduğunu neden düşündüğümü anlatayım.
Problemin kurulumu
Diyelim ki {±1}^N içinde ikili bir x vektörü gönderiyorsunuz ve
y=SNRNHx+w{\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w}
alıyorsunuz. Burada H, N×N boyutunda ve hem H hem de w'nin girdileri bağımsız ve özdeş dağılımlı (iid) N(0,1) şeklinde. Alıcı H'yi ve gürültü istatistiklerini biliyor ama w'yi bilmiyor ve y'den x'i geri istiyor. Geri kazanma probleminin blok hatası açısından optimal çözümü şuna eşittir:
Bu arada bu optimizasyon başka kılıklarda da karşımıza çıkar: MIMO sezimi, CDMA çok kullanıcılı sezim, tamsayı en küçük kareler, bir kafeste en yakın vektör, vb.
SNR = ∞ (yani etkin gürültü 0) olduğunda problem önemsizleşir: kanal matrisi H, olasılık 1 ile tersinirdir, bu yüzden onu ters çevirirsiniz ve inv(H)*y ile x'i hatasız geri kazanırsınız. Diğer uçta, SNR = 0 olduğunda, gürültüden tespit edebileceğiniz hiçbir şey yoktur ve ML sezimi başarısız olur.
Ancak 0 ile sonsuz arasında bir yerde, ML sezimi başarılı olur ve bunu tam olarak SNR = 2 log N'de yapar. Bu, yukarıdaki optimizasyon problemini çözmenin, gönderilen N bitlik dizinin tüm bitlerini olasılığı 1'e yaklaşan bir şekilde mükemmel biçimde geri kazanmanızı sağladığı anlamına gelir ve bunun altında (loglogN mertebesinde toplamsal terimlere kadar) blok geri kazanma olasılığı 0'a yaklaşır.
Yani 2logN'nin üzerinde, gönderilen sinyal ML optimizasyon probleminin bir optimumudur, ancak onu çözmek tüm olası N bitlik diziler üzerinde kapsamlı bir arama gerektiriyor gibi görünür. Dolayısıyla şimdi önemsediğimiz soru şu:
ML başarılı olduğunda, polinom zamanlı bir algoritma gönderilen x'i geri kazanabilir mi?
**
Kısa ve biraz dramatik bir tarihçe
Tamsayı en küçük kareler probleminin çözülebilirliği sorusu en az 1989 yılına kadar uzanır; Verdú, genel durumda NP-zor olduğunu kanıtladı. Ancak NP-zorluk en kötü durum için geçerli bir ifadedir ve bizim örneklerimiz en kötü durumda değildir.
Hassibi ve Vikalo 2001'de, bildiğim kadarıyla, ortalama durumda polinom zamanlı bir çözüm için umut olduğunu savunan ilk kişilerdi. Analiz ettikleri algoritma, o zamanlar popüler bir yöntemdi: Fincke ve Pohst 1985'teki çalışmasına dayanan Sphere Decoder (SD). Sphere Decoder özellikle ilgi çekiciydi çünkü 1) tam bir ML algoritmasıdır, yani her zaman minimize edeni verir ve 2) pratikte üstel zamandan çok daha hızlı görünüyordu.
Umuluyordu ki SD'nin polinom zamanda çalıştığı gerçekten kanıtlanabilirdi. H&V'nin makalelerinde dile getirdikleri de tam olarak buydu: kanal ve gürültü üzerinden ortalaması alınan Sphere Decoder'ın beklenen karmaşıklığı için bir formül türettiler ve bunun polinom göründüğünü gösterdiler. Eğer bu doğru olsaydı, soru çözülmüş olurdu. Bu inanılmaz bir sonuç gibi görünüyordu.
Sonra Jaldén ve Ottersten 2005'te asimptotik yorumun tam olarak doğru olmadığını gösterdi: herhangi bir sabit SNR'de, ne kadar büyük olursa olsun, küre kod çözmenin beklenen karmaşıklığı aslında problem boyutunda üsseldir.
Tam ve hızlı çalışmadığı için, alan ML optimizasyon problemine yaklaşıklıklar üzerinde hatırı sayılır çaba harcadı. Yaklaşıklık garantili yarı tanımlı gevşetmeler ve yüksek SNR'de sıkılık koşulları vardı, ancak keskin bir eşik yoktu. Bit çevirme yerel araması simülasyonlarda ML ile eşleşiyor gibi görünüyordu ancak ML geri kazanma eşiğini eşleştirmeye dair tam kanıtlar yoktu. AMP literatürü, blok geri kazanmanın mümkün olmadığı sabit SNR'de bit başına hatayı titizlikle karakterize etti. İstatistiksel fizik, replika düzeyi argümanlarla tam ML'yi izlediği öngörülen polinom zamanlı yöntemler üretti, ancak anladığım kadarıyla kanıtı yok. Ve yukarıdaki 2010 tarihli Babak ve Alex ile yazdığımız makale, bir MCMC yöntemini analiz ederek, karışma (mixing) sonrasında durağan dağılımın doğru çözüme sıfırdan farklı bir kütle koyduğunu kanıtladı, ancak zor kısım olan karışma süresi hakkında hiçbir şey kanıtlamadı.
Bana öyle geliyor ki, tüm bu yıllar boyunca, herhangi bir SNR ölçeğinde titiz blok geri kazanma garantileriyle gelen tam olarak bir polinom zamanlı yöntem vardı: kutu gevşetmesi, 2020'de, SNR 4 log N gibi ölçeklendiğinde bloğu geri kazandığı gösterildi ve kanıtlanabilir şekilde altında kazanamıyor. Bu arada, böyle bir tekniği analiz etmek için gereken olasılıksal araçların 2010'ların sonlarında olgunlaşması ilginç; ki bu, topluluğun çoğunlukla konuyu bırakıp dağılmasından sonraydı.
Ve o zamandan beri… pek fazla aktivite yok.
Uzun lafın kısası, ML'nin başardığı ile herhangi bir polinom zamanlı yöntemin kanıtlanabilir şekilde başarabildiği arasındaki boşluk hiçbir zaman kapanmadı.
**
GPT ve Claude ne yaptı ve benim (Dimitris) doğrulayabileceğim bir kanıta nasıl ulaştık?
En gelişmiş modellerin zor matematik görevlerindeki son akıl almaz başarılarından motive olarak, lisansüstü öğrenciliğimde beni rahatsız eden problemlere (eskiden bilgi ve kodlama teorisi üzerinde çalışırdım) geri dönmeye ve Ölüm Yıldızı'nı onlara doğrultmaya karar verdim. Zor matematik soruları sormak ve GPT'nin onları sıfır atışla çözmesini izlemek tam olarak böyle hissettiriyor:
GIF
Ama bir sorun olabileceğini biliyordum. Sorduğum her soruya tam bir cevap alsam bile, bunu daha geniş çapta paylaşmak istiyorsam doğrulama darboğazıyla karşılaşırdım. Birincisi, yanlış olduğu ortaya çıkarsa kendimi rezil etmek istemem; ikincisi, paylaşmak zaten soru sormamızın ve bilim yapmamızın ana nedeni.
Bu yüzden, doktoramın başlarında beni rahatsız eden en iddialı sorulardan biri gibi hissettiren, ifadesi temiz ve hâlâ açık olan bir soruyu seçmeye karar verdim. GPT-5.6 ve Claude Fable 5'e ML MIMO seziminin ne zaman polinom zamanda çözülebileceğini sordum.
İkisi de farklı algoritmalar için kanıtlar üretti ve hiç boşluk olmadığını kendinden emin şekilde iddia etti! SNR 2 log N'nin üzerinde başarılı olan, ML geri kazanma eşiğini tam olarak eşleştiren (loglog terimlerine kadar, ama kimin umurunda) bir polinom zamanlı algoritma var.
Ama küçük bir sorun vardı 😊 GPT'nin algoritması bir AMP varyantıydı. Ve ben AMP'den tutkuyla nefret ediyorum çünkü analizlerini ömrüm boyunca anlayamıyorum. Bu yüzden ona, mümkünse aynı sonucu daha basit bir algoritma için yeniden kanıtlamasını söyledim. Nitekim GPT, bana da sezgisel gelmeyen ve daha önce hiç kullanıldığını görmediğim başka bir algoritma üretti!
Öte yandan Fable, gerçekten hoşuma giden bir şey buldu:
işaretli LMMSE, ardından açgözlü bit çevirmeleri. Geçmişte tanıtılmış ve pratikte gerçekten kullanılmış bir algoritma.
Ama başka bir sorun daha vardı! GPT'ye göre, Fable'ın kanıtı çoğunlukla yanlıştı… ama kurtarılabilirdi. Bu yüzden Fable'ın önerdiği algoritmada kalmaya karar verdim ve GPT'den Fable'ın kanıtını alıp düzeltmesini istedim. Ve düzeltti!
Ama bir sorun daha vardı: bu yeni kanıt OKUNAMAZDI: bir gösterim duvarı, değişkenleri tanımlayan değişkenlerin oranlarına işaret eden değişkenler, egzotik matris analizi ve olasılık makineleri, tüylerimi diken diken eden Marchenko–Pastur civarı şeyler ve diğer güzel şeyler.
Bu yüzden yaklaşık 4-5 gün boyunca iki model arasında gidip geldim ve kanıtın çalışması için gereken her büyük bileşen için bana mümkün olan en aptalca adım setlerini vermelerini istedim. Onlara açıkça, 2 log N eşiği korunduğu sürece sınırların ve sabitlerin kötüleşmesinin sorun olmadığını, amacın basitlik olduğunu söyledim.
Tek istediğim, kısa dikkat süresine sahip yaşlı bir dinozorun ağlamadan hazmedebileceği bir kanıttı.
Aslında GPT ve Claude'dan en çok sızlandığım mesajları geri paylaşmalarını istedim, lol
En sevdiğim:
Neden süper basit adımlarda ısrar ettim? Çünkü bunu kendim, baştan sona doğrulamak istedim. Ve hayır, Lean kullanmak istemiyorum, sorunumu ÇÖZMÜYOR. Biçimsel doğrulama soyutlama seviyesini başka bir yere taşıyor!! Yine de bir lemmanın İngilizcesinin Lean'e sadık bir şekilde çevrilip çevrilmediğini doğrulamanız gerekiyor; ki Lean anlamadığım bir dil.
Evet, boş verin. Lean'dan hoşlanmıyorum, üzgünüm.
Ama temel lineer cebir ve olasılığı anlıyorum ve bu tür adımları doğrulamak için kendime güveniyorum. Talep ettiğim kanıtın seviyesi bu.
Sonra günlerce süren tekrarlayan yönlendirmeler oldu; modeller birbirlerinin argümanlarını sadeleştirdi, ben ise takip edemediğim hiçbir şeyi kabul etmeyip durmadan şikayet ettim.
Ve sonunda işe yaradı! Tamamen anladığım ve artık satır satır kontrol ettiğim bir kanıt elde ettik.
İspatı üretmek 30 dakika sürdü; onu benim doğrulayabileceğim hale getirmek ise 5 gün civarı. Bu oldukça çılgın bir oran, ama durum neyse o. Ve sonuç: maksimum olabilirlik çalıştığı her zaman, polinom zamanda çalışan basit bir algoritma var. Bu problemde hesaplama-istatistiksel boşluk yok.
BOOM!
**
Kanıtın üst düzey fikri nedir?
Algoritma neredeyse utanç verici derecede basit. Peki bu neden işe yarıyor? Ardından yuvarlama ile gelen LMMSE, Hamming uzaklığı açısından sizi gönderilen sinyalin ihmal edilebilir bir kesri içine, yani doğrudan o(N) uzağa getirir.
Ardından, açgözlü bit çevirme takılıp kalamaz çünkü her adımdaki iniş kazançları (yani maliyetin ne kadar iyileştiği) Gauss büyüklükleri tarafından yönetilir ve bunların düzgün yoğunlaşması, belirli bir top içindeki her gerçek-olmayan-temel-doğru vektörünün garantili boyutta kesin olarak iyileştiren bir bit çevrimi sunduğunu gösterir. Yani ne yaparsanız yapın, sıfırdan uzak sınırlanmış bir miktarda kesinlikle iyileştirirsiniz.
Ancak her açgözlü adımda maliyeti iyileştirmek, doğruya olan Hamming uzaklığının her adımda iyileştiği anlamına gelmez. Gerçekten de geçici olarak kötüleşebilir. Ama çok fazla değil, çünkü maliyet fonksiyonu doğrudan Hamming uzaklığını artırdıkça büyür. Yani yeterince uzaktaki herhangi bir nokta, algoritmanın başladığı yerden çok daha maliyetlidir ve maliyeti yalnızca azalan bir yol oraya asla gidemez. Açgözlü algoritma Hamming uzaklık topunda dolaşabilir, ancak onun yolunu bir topun içinde tutan bir "maliyet bariyeri" ile sınırlıdır.
Yani 1) her adım maliyeti sıfırdan uzak sınırlanmış bir miktarda iyileştirir ve 2) başlangıç maliyeti optimumun çok üzerinde değildir. Dolayısıyla, açgözlü çalıştırma eninde sonunda durmalıdır ve iki miktarı birbirine bölmek, gereken adım sayısını verir; ki bu NlogN'dir.
Ayrıca, açgözlü algoritma temel doğru dışında hiçbir yerde sona eremez: topun içindeki diğer her noktada, bazı bit çevrimleri hâlâ iyileştirme sunar ve algoritmanın orada durmasına izin verilmez. Duracağı tek yer gönderilen vektördür.
İşte ana argümanın güzel bir görsel tasviri:
Önemli mi?
Kablosuz iletişim topluluğu başka konulara yöneldi, ben de öyle. Ama bu gerçekten önemli bir soruydu. Bu sonucun 2010 civarında ne anlama geleceğini tahmin edebilirim: bir ISIT ya da CommSoc/BT Topluluğu en iyi makale ödülü ve belki MIT, Berkeley ve Stanford'da mülakatlar. Bir doktora öğrencisi olarak bunun kutsal kâse türünden bir sonuç ve kısa bilgi teorik kariyerimin en önemli noktası olacağını güvenle söyleyebilirim.
Yine de… alan büyük ölçüde başka konulara yöneldi 😊
Bunun gibi eskiden önemli olan ve koca toplulukların onlarca yıl üzerinde çalıştığı tonla problem var. Sonra araştırma alanları yoluna devam ettikçe yavaş yavaş önemlerini yitirdiler ve açık ve yalnız bırakıldılar; imkansız oldukları için değil, insanlar yavaş yavaş umursamadığı için.
İnsanlar "N yıllık problem yapay zeka tarafından çözüldü" dediğinde, bunun ne anlama geldiğini bu şekilde yorumlamaya çalışırım.
Yine de tüm bunlarda inanı
