Beklenmedik bir kaynaktan gelen yeni küre paketleme rekoru

• Boaz Klartag, mevcut yaklaşımlardan farklı olarak ultra yüksek boyutlu küre paketleme problemine konveks geometri araçlarını dahil etti
• Klartag’ın yeni rastgele yöntemi, daha büyük hacimli elipsoidler üreterek önceki rekorları büyük ölçüde yeniledi
• Bu yaklaşım, yüksek boyutlu uzayda çok daha fazla kürenin paketlenmesini mümkün kılıyor
• Bu sonuç, paketlemede düzen ve simetrinin önemi hakkındaki tartışmayı yeniden alevlendirdi
• Araştırma, kriptografi ve iletişim alanları dahil çeşitli uygulama olasılıkları nedeniyle dikkat çekiyor

---

Önceki küre paketleme araştırmaları ve sınırlamalar

• Geçmişte Rogers yönteminin avantajı, başlangıç kafesinin mutlaka verimli olmasının gerekmemesi; yalnızca uygun bir elipsoid seçmenin yeterli olmasıydı
• Ancak elipsoidin eksenleri, yüksek boyutlarda çok farklı biçimlerde değiştirilebildiği için hangi biçimde büyütüleceğine dair fazla sayıda seçenek vardı
• Daha sonra matematikçiler Minkowski yaklaşımına geri dönerek kafesin kendisine odaklandı, kafes teorisinde uzmanlaştı ve Rogers’ın geometri merkezli yaklaşımından uzaklaştı
• Bu strateji, yüksek boyutlu küre paketlemede kademeli iyileşmeler gösterdi ancak Rogers yöntemine kıyasla yalnızca küçük verim artışları sağladı
• On yıllar boyunca büyük bir sıçrama gelmedi ve durgunluk sürdü

Dışarıdan bir bakışla başlayan yenilik

• Weizmann Institute of Science’dan Boaz Klartag, aslında kafes teorisinden değil konveks geometri alanından gelen bir araştırmacı
• Uzun süredir küre paketleme problemine ilgi duyuyordu ancak bu konuda çalışma fırsatı bulamamıştı
• 2023’te yeni bir zaman aralığı elde edince, Tel Aviv University’den Barak Weiss ile bir seminer düzenleyip klasik literatürü (Minkowski, Rogers) yoğun biçimde inceledi
• Klartag, Rogers’ın elipsoid yönteminin konveks şekillerin manipülasyonu konusundaki pratik bilgi eksikliği nedeniyle verimsiz kaldığını değerlendirdi
• Daha verimli elipsoidler üretilebilirse küre paketleme rekorunun yeniden yazılabileceğine inandı

Rastgele büyüme algoritmasının kullanıma alınması

• Klartag, her eksen yönü için elipsoid sınırını rastgele genişletip daraltan kendine özgü bir yöntem uyguladı
• Sınır bir kafes noktasına değdiğinde o yöndeki büyümeyi durduruyor, diğer yönlerde ise büyüme sürüyor
• Bu süreçte elipsoid, uzayı düzensiz bir biçimde tarayarak kademeli olarak büyüyor
• Rastgele yapısı nedeniyle üretilen her elipsoidin hacmi farklı olduğundan, birden çok deneme yaparak daha büyük hacimli elipsoid olasılığını değerlendirdi
• Birkaç hafta içinde Rogers’ınkinden daha büyük elipsoidlerin elde edilebileceğini kanıtladı

Rekorun yenilenmesi ve etkisi

• Yeni elipsoid yöntemi, Rogers’tan (1947) bu yana küre paketleme verimliliğinde en büyük iyileşmeyi sağladı
• Boyut d olduğunda, önceki yönteme kıyasla d kat daha fazla küre paketlemek mümkün
  • 100 boyut → yaklaşık 100 kat, 1,000,000 boyut → yaklaşık 1 milyon kat daha fazla küre paketleme
• Klartag, konveks geometrideki içgörüleriyle kafesler ve küre paketleme alanındaki eski bir merkezi problemi birkaç ay içinde aştı
• Bu başarıyla birlikte, düzen ve simetriye dayalı paketlemelerin en yoğun yerleşimi sağlayabileceği görüşü yeniden öne çıktı
• Öte yandan son dönemde, düzenli kafesler olmadan düzensizlikten yararlanılması gerektiğini savunan araştırmalar da rekabet ediyor

Değerlendirme ve gelecek beklentileri

• Şu anda Klartag’ın paketleme yönteminin gerçekten optimuma yakın olup olmadığı ve daha fazla iyileştirme payı bulunup bulunmadığı konusunda akademi içinde tartışmalar var
• Bu sorunun yanıtı, kriptografi, iletişim mühendisliği ve benzeri gerçek dünya uygulamaları açısından da büyük önem taşıyor
• Henüz pratik uygulama aşamasında değil ancak mühendislik çevrelerinde yeni bir teknoloji olarak ilgi görüyor
• Klartag, bu vesileyle konveks geometri ile kafes teorisi arasındaki bağın güçlenmesini umuyor
• İki alan arasındaki kopukluğun aşılmasını ve bu birleşimin paketleme dışındaki kafes problemlerine de çözüm sunmasını diliyor

[GN⁺]

Hacker News yorumu

• Anne babama yaptığım işin gerçekten var olan bir meslek olduğunu anlatmanın her zaman zor olduğuna dair bir itiraf; “Ben şekilleri inceliyorum ama sadece içbükey girintileri olmayan şekilleri inceliyorum” diye açıklamak zorunda kalınca durumun daha da tuhaflaştığını hayal edin
  • Benim deneyimime göre işi zor teknik terimlerle anlatmak en iyisi; seçenekler üçe iniyor: Anne babanın anlayabileceği kadar basit anlatırsan iş fazla kolay görünür ve “Gerçekten bununla para mı kazanıyorsun?” tepkisini alırsın. Neden önemli olduğunu düzgün anlatmaya kalkarsan açıklama çok uzar, onlar da sıkılıp bu soruyu sorduklarına pişman olur. Ya da karmaşık uzmanlık terimleriyle kısa geçersin; ne dediğini anlamazlar ama nedense etkileyici görünürsün. En iyi seçenek bu.
  • Yüksek enerjili fizik ekipmanları için parça üreten bir mikro işletmem var; başkalarına işimi anlatırken konu, insanların hiç karşılaşmadığı ve günlük hayattan birkaç kademe uzak, son derece yabancı ve niş bir alan olduğu için hâlâ anlaşılır bir açıklama yolu bulabilmiş değilim
  • Ben sadece “Bilgisayarlarla çalışıyorum” diyorum; sonra “Aa, güzel işmiş” tepkisi geliyor ve konuşmanın orada bitmesi çok pratik oluyor
  • Benim için asıl zor olan genelde “Ne iş yapıyorsun?” sorusundan çok, ardından gelen “Peki bunun ne faydası var / nerede kullanılıyor?” sorusunu cevaplamak; temel araştırmadan gerçek uygulamaya giden uzun bağlantı zincirini kısa ve etkili biçimde anlatmanın bir yolunu arıyorum
  • En azından küre paketleme (sphere packing), bilgi kuramındaki temel problemlerle yakından bağlantılı ve bunun Bell Telephone System'ın güvenilirliğinin artmasına kadar uzanan tarihsel bir önemi var (gerçi dışbükey cisimler için aynısı söylenebilir mi bilmiyorum)
• Küreleri sıkı biçimde dizme yöntemlerini (sphere packing) kullanarak vektör veri sıkıştırma algoritmaları üzerine düşündüğüm bir deneyimim oldu; kuramsal yaklaşım ancak veri çok homojen olduğunda işe yarıyordu ve gerçek dünyadaki verilere uygulamak zordu
  • Düzensiz (homojen olmayan) veriyi daha homojen hâle getirmek için alan bilgisini kullanıp asimetrileri azaltmak klasik bir hiledir; örneğin veri yüksek boyutlu bir yapıya sahip olsa bile, yerel düzeyde gürültü nedeniyle oldukça homojenleşebilir. Merkez noktaları (centroid) hesaplayıp saklarsın; merkez noktaları daha homojen olur ve her vektörü merkez nokta indeksi ile vektör ofseti olarak ayırıp saklarsın. İndeks verimli entropi sıkıştırmasına gider, ofsetler ise artık neredeyse homojen olduğu için mevcut sphere packing stratejilerini uygulamaya daha elverişli olur
  • Muhtemelen zaten denenmiştir ama ön sıkıştırma (precompression) ile vektörün seyrekliğini azaltıp homojenliğin artıp artmadığı test edilebilir
  • Gerçek vektörlerle uğraşırken (grope, “el yordamıyla yoklamak”, group yazım hatası) dikkatli olmak gerektiğine dair şakalı bir uyarı
  • Kuramın kapsamını pratik sorunlara, yani homojen olmayan verilere de genişletme ihtiyacı; gerçek dünyadaki kullanım örnekleri fazla çeşitliyse genel bir yaklaşım zor olabilir ama yine de araştırmanın genişlemesi gerektiğine dikkat çekiliyor
  • Ticari olarak önemli eski alanlarda kolay elde edilebilecek kazanımların (low-hanging fruit) büyük ölçüde zaten toplanmış olduğuna dair bir tespit
• Klartag’ın “Dışbükey cisimler çok güçlü ve çok kullanışlıdır” iddiasına katıldığını söyleyen biri, matematikçi olmamasına rağmen Convex Hull algoritmasının beklenmedik yerlerde, özellikle görüntülerde otomatik palet ayrıştırma gibi çeşitli sorunlarda sık sık ortaya çıktığını gördüğünü paylaşıyor; ilgili makale bağlantısı veriyor Convex Hull and automatic palette decomposition
• Klartag’ın yeni küre paketleme yönteminin, boyut d ise önceye kıyasla d kat daha fazla küre yerleştirebildiği söyleniyor; 100 boyutta 100 kat, bir milyon boyutta bir milyon kat artış kulağa inanılmaz geliyor. Bunun çeşitli iletişim sistemlerinde gerçekten bant genişliğinin onlarca-yüzlerce kat artması ya da güç tüketiminin büyük ölçüde azalması anlamına gelip gelmediği merak ediliyor
  • Gerçekte boyut arttıkça yoğunluk (density) n^2/2^n biçiminde üstel olarak kötüleştiği için, kuramdaki doğrusal iyileşme fiilî performansa aynı ölçüde yansımıyor. Yani doğal olarak yüksek boyutlu yapıya sahip veriler için yararlı olabilir ama dijital veride (yalnızca uzunluğu seçilebilen durumda) küçük boyutlar tercih edilebilir; ayrıntılar için sphere packing bkz. wikipedia link
• Matematikçilerin, ilk doktoralarından birkaç yıl sonra aynı alan değil de komşu bir disiplinde ikinci bir doktora yapabilmeleri gerektiği düşüncesi
  • Doktoranın temel amacı bağımsız araştırma yapabilme yetisini kanıtlamak olduğundan, gerçekte birçok araştırmacı doktoradan sonra başka alanlara geçiyor ya da ilgi duyduğu araştırma konularını değiştiriyor; o noktadan sonra merkezde olan şey artık doğrudan “araştırma” oluyor
  • Bunun gerçekten mümkün olduğuna örnek olarak ünlü matematikçi Bela Bollobas’ın ayrık geometri ve fonksiyonel analiz alanlarında iki doktora derecesine sahip olduğu belirtiliyor; yine de bunu günümüz akademisinde yeniden denemek muhtemelen çok zor olurdu
  • Bilim genelinde böyle kurumsal bir esneklik olsa, farklı alanların teknikleri ve fikirleri daha hızlı dolaşıma girer ve bilimsel ilerleme hızlanabilirdi; özellikle matematik gibi alt dallar arası bağların önemli olduğu alanlarda bunun etkisinin daha da büyük olması beklenir
• Acemice bir soru olarak, en iyi küre paketlemesinin (sphere packing) her zaman düzenli kafeslerle ilişkili olup olmadığı soruluyor; 2D ve 3D’de öyle görünüyor ama bunun ND’ye de uzanıp uzanmadığı merak ediliyor
  • 2 ve 3 boyutların dışında 8 boyutta (E₈ kafesi) ve 24 boyutta (Leech kafesi) da en iyi paketlemenin düzenli kafes biçiminde olduğu kanıtlanmış örnekler var. Bunu Maryna Viazovska ve çalışma arkadaşları 2017’de gösterdi; ilgili bağlantılar: makale1, makale2, açıklama pdf. Ancak başka boyutlarda en iyi paketlemenin düzenli kafes olmayabileceğine dair karşı örnekler bulunabilir ve bazı boyutlarda düzensiz yapılar daha yoğun olabilir
  • Her zaman öyle değil; 3 boyutta bile lattice (düzenli kafes) yerleşimlerinin dışında, katmanların yatay kaymasını değiştirerek sayısız kafes-dışı dizilim elde edilebilir. Bunların yoğunluğu da FCC lattice ile aynıdır. Daha yüksek boyutlarda simetri eksikliği nedeniyle en iyi paketlemenin her zaman kafes-dışı olduğu yönünde tahminler de vardır
• Bu yeni küre paketleme yapısının, önceki en iyi yoğunluğun kanıtlandığı boyutlarla karşılaştırıldığında hangi en düşük boyuttan itibaren daha iyi olduğu merak ediliyor
• Bu araştırma sonucunun kriptografi ve iletişim alanlarında gerçekten daha güvenli, daha güvenilir ve daha enerji verimli iletişim sistemlerinin geliştirilmesinde kullanılıp kullanılamayacağına dair bir gelişim yönü öneriliyor; gerçekten çok ilgi çekici bir araştırma alanı
• Gerçek fizikte “Cow Packing”in (teorik olarak inekleri en uygun yoğunlukta doldurma çalışmaları vb.) pratik uygulamalarının olabileceğinden söz eden esprili bir benzetme
• Küre paketleme, uygulamalı alanlarda gerçekten çok çeşitli problemlerde ortaya çıktığı için ilgi çekici; makaleyi dikkatle okumayı bekliyorum