Macar Algoritması: 1955’ten Kalma Bir Atama Çözücüsü Neden Hâlâ Modern Yapay Zeka Yığınının Tam Ortasında Duruyor?

Macar Algoritması: 1955’ten Kalma Bir Atama Çözücüsü Neden Hâlâ Modern Yapay Zeka Yığınının Tam Ortasında Duruyor?

Bugünlerde bir sistem tasarım toplantısında “eşleştirme” kelimesi geçtiğinde refleksimiz belli: embedding çıkar, kosinüs benzerliği hesapla, top-k al, gerekiyorsa bir cross-encoder’la yeniden sırala. Bu refleks çoğu zaman işe de yarıyor. Ama bu yaklaşımın sessizce yaptığı bir varsayım var — her sorgunun kendi en iyi sonucunu bağımsız olarak seçebileceği varsayımı. Ve bu varsayım, sistemin çıktısında bir *bütünlük* kısıtı olduğu anda çöküyor.

Slava Efimov’un Towards Data Science’ta yayımladığı yazı, tam da bu kör noktaya 1955’ten bir cevap hatırlatıyor: Macar algoritması. Yazı algoritmayı çok obje takibi (multi-object tracking, MOT) bağlamında anlatıyor — ardışık video karelerindeki bounding box’ları birbirine bağlama problemi. Ama algoritmanın çözdüğü şey video değil. Çözdüğü şey, **atama problemi**: iki küme arasında, her elemanın yalnızca bir kez kullanıldığı, toplam maliyeti minimize eden bir eşleme kurmak. Ve o problem, RAG hatlarınızın, öneri motorlarınızın ve LLM değerlendirme (eval) yığınlarınızın içinde, çoğu zaman farkında olmadan çözmeye çalıştığınız problemin ta kendisi.

Kâğıt Üstündeki Problem: n İşçi, n Görev

Efimov’un tercih ettiği klasik kurulum şu: elinizde n işçi ve n görev var. Her işçinin her görev için bir maliyeti var; bu bir maliyet matrisi oluşturuyor. Amaç, her işçiye tam olarak bir görev atamak, tüm görevleri tamamlatmak ve toplam maliyeti minimize etmek. Geometrik olarak: matristen n eleman seçin, hiçbiri aynı satır veya sütunda olmasın, toplamları minimum olsun.

Naif çözüm tüm permütasyonları denemek — yani n! adım. 20 elemanlık bir matriste bu, evrenin yaşından uzun sürer. Macar algoritmasının zarafeti, problemi *değiştirmeden* matrisi dönüştürmesinde. Her satırdan o satırın minimumunu çıkarırsınız; sonra her sütundan o sütunun minimumunu. Toplam maliyet değişir ama **çözümlerin sıralaması değişmez** — çünkü aynı işçinin farklı görevler arasındaki göreli maliyeti sabit kalır. Bu dönüşüm matriste sıfırlar üretir ve her sıfır, potansiyel bir atamadır.

Sonrası bir örtme oyunu: tüm sıfırları kapatmak için gereken minimum sayıda yatay/dikey çizgiyi çizersiniz. Çizgi sayısı k, matris boyutu n’e eşitse çözüm elinizdedir. Değilse ayarlama adımına geçersiniz — örtülmemiş elemanların minimumunu bulur, onu tüm örtülmemiş elemanlardan çıkarır ve iki kez örtülmüş “köşe” elemanlara eklersiniz. Bu, problemi yine bozmaz: örtülmemişlerden yapılan çıkarma, örtülmüşlere iki kez yapılan ekleme ile dengelenir. k = n olana kadar tekrarlanır.

Sonuç: O(n³). Faktöriyelden kübiğe inen bir problem, kırk yıl boyunca yüzlerce sistemin altına girecek kadar ucuz demektir.

Pratikte kimse bu adımları elle yazmıyor. `scipy.optimize.linear_sum_assignment`, Crouse’un 2016’da tarif ettiği, başlatma gerektirmeyen modifiye Jonker-Volgenant varyantını kullanıyor — teorik karmaşıklık yine O(n³) ama sabitler çok daha iyi. Daha büyük matrisler için `lap` veya `lapjv` gibi C++ sarmalayıcıları var; bazıları AVX2 ile vektörleştirilmiş. Dikkat edilecek bir detay: bu çözücüler dikdörtgen matrisleri de kabul ediyor, yani iki kümenin eleman sayısı eşit olmak zorunda değil. Bu, gerçek dünyada kritik — bir karede 5, sonrakinde 7 obje tespit ettiğinizde kimse size kare matris vermiyor.

Kayıp Fonksiyonuna Terfi Eden Bir Algoritma

Macar algoritmasının bilgisayarlı görüdeki ilk yerleşim yeri takip hattıydı. SORT ve türevleri gibi klasik MOT sistemleri, Kalman filtresiyle tahmin ettikleri konumlarla yeni tespitler arasında bir maliyet matrisi kurup Macar algoritmasıyla eşleştirir. Efimov’un yazısı bunu sadece merkez noktaları arası mesafeyle örnekliyor; gerçek sistemler maliyet fonksiyonuna hareket vektörü, IoU, görsel benzerlik (appearance embedding) ve tıkanma (occlusion) sinyallerini de katıyor. Yani maliyet matrisi bir mühendislik ürünü; algoritma sadece o matrisi optimal çözüyor.

Asıl ilginç kısım şu: DETR ile birlikte Macar algoritması *çıkarım sonrası bir eşleştirme adımı* olmaktan çıkıp **eğitim kaybının içine** girdi. Carion ve ekibinin 2020’de önerdiği DETR, obje tespitini bir küme tahmini (set prediction) problemi olarak formüle ediyor: model sabit sayıda — varsayılan olarak 100 — obje sorgusu üretiyor, gerçek etiketler boş (∅) sınıfıyla aynı uzunluğa dolduruluyor ve tahminlerle etiketler arasında Macar algoritmasıyla iki parçalı (bipartite) optimal eşleme kuruluyor. Kayıp yalnızca eşleşen çiftler üzerinden hesaplanıyor.

Bunun neden önemli olduğunu görmek için ne kazanıldığına bakın: her gerçek objeye tam olarak bir tahmin atandığı için model kopya üretmeye teşvik edilmiyor, dolayısıyla **non-maximum suppression’a gerek kalmıyor**. Yıllardır elle ayarlanan bir post-processing adımı, bir atama kısıtı sayesinde mimariden düşüyor.

Bedava değil elbette. DETR’in yavaş yakınsamasının nedenlerinden biri, tam da bu eşleştirmenin kararsızlığı: başlangıçta rastgele olan eşleme, eğitim boyunca aynı gerçek obje için farklı sorgulara atlayabiliyor ve model tutarsız bir denetim sinyali alıyor. Literatürde bunu adresleyen bir dizi çalışma var — eşleştirme damıtması (matching distillation), sorgu gürültüleme (DN-DETR), tutarlılık kayıpları. Yani “optimal atama” garantisi, öğrenme dinamiği açısından bedelsiz bir garanti değil.

Peki Bu Aramayı ve Öneriyi Neden İlgilendiriyor?

Şimdi başladığımız yere dönelim. Retrieval yığınlarımız neredeyse tamamen **bağımsız top-k** üzerine kurulu: her sorgu kendi en iyi belgelerini seçer, sorgular birbirinden habersizdir. Bu, atama problemini *açgözlü* (greedy) çözmek demek — ve açgözlü çözüm, kısıt olmadığı sürece gerçekten de optimaldir.

Sorun, kısıtın olduğu ve bizim onu görmezden geldiğimiz durumlar:

Bir kaynağın birden fazla talep tarafından paylaşılamadığı yerler. Bir slot dolduruluyorsa (ana sayfadaki 6 kart, e-postadaki 3 ürün, bir reklam envanteri) ve aynı öğe iki yere birden konamıyorsa, karta göre bağımsız top-1 almak toplamda kötü bir dağılım üretir. En güçlü aday tüm slotların birinci tercihi olur, sonra keyfi bir tie-breaking devreye girer. Macar algoritması burada tam olarak doğru araçtır ve slot sayıları küçük olduğu için O(n³) hiç sorun değildir.

Küme-küme değerlendirme. LLM çıktısını gerçek etiketle karşılaştırdığınız her yerde — çıkarılan varlıklar (entity), üretilen özet cümleleri, tespit edilen iddialar — elinizde sırasız iki küme var ve onları hizalamanız gerekiyor. Çoğu ekip bunu ya tam eşleşmeyle ya da açgözlü en yakın komşuyla yapıyor. İkisi de skoru sistematik biçimde yanlış hesaplar. DETR’in kayıp fonksiyonunda yaptığı şey, aslında bir eval probleminin doğru çözümüdür ve doğrudan ödünç alınabilir.

Görselleştirme ve düzenleme. Daha küçük ama somut bir örnek: t-SNE veya UMAP çıktısını düzenli bir ızgaraya oturtmak, birebir bir atama problemidir — `lapjv` deposunun kendi örneklerinden biri budur. Embedding uzayınızı bir müşteriye göstereceğiniz her an bu problemle karşılaşırsınız.

Şu noktada dürüst olmak gerek: bu, “RAG’inizde Macar algoritması kullanın” demek değil. Milyonlarca belgelik bir korpusta n³ hesaplanamaz; retrieval’ın kendisi zaten yaklaşık (ANN) olduğu için optimal atama garantisi anlamını yitirir. Macar algoritması, **darboğazın küçük ve kısıtın sıkı olduğu son aşamalarda** parlıyor: reranking sonrası, slot atamasında, değerlendirmede. Doğru zihinsel model şu — geniş aday havuzunu ANN ile daralt, sonra o küçük matriste global optimali çöz.

Sektörel Çıkarımlar

**Geliştiriciler için:** `linear_sum_assignment` üç satırlık bir çağrı. Eğer kodunuzda “her X için en iyi Y’yi bul, sonra çakışmaları temizle” şeklinde bir döngü varsa, muhtemelen bir atama problemini elle ve yanlış çözüyorsunuz. Yeniden yazmanın maliyeti bir öğleden sonra.

**Ürün yöneticileri için:** “Çeşitlilik”, “tekrar etmeme”, “her kullanıcıya farklı içerik” gibi gereksinimler ürün diliyle ifade edildiğinde masum görünür ama teknik olarak bunlar kısıtlı optimizasyon talepleridir. Bunu ekibe bir sıralama (ranking) problemi olarak vermek yerine bir atama problemi olarak vermek, çözümün kalitesini doğrudan değiştirir.

**Mimari açısından:** DETR’in hikâyesi buradaki asıl ders. Bir optimizasyon adımını çıkarım hattından alıp eğitim hedefinin içine taşımak, elle ayarlanan bir bileşeni (NMS) tamamen ortadan kaldırdı. Benzer bir hamle retrieval tarafında da mümkün mü — çeşitlilik kısıtını post-processing’de MMR ile uygulamak yerine eğitim hedefine gömmek? Bu soru bana en az DETR’in kendisi kadar ilginç geliyor.

## Sonuç ve Gelecek Görünümü

Yapay zeka ekosisteminde her şeyin altı ay içinde eskidiği hissine kapılmak kolay. Macar algoritması bunun tersini hatırlatıyor: 1955’te formüle edilmiş, iki Macar matematikçinin daha da eski çalışmalarına dayanan bir yöntem, 2020’de bir transformer mimarisinin kayıp fonksiyonunun merkezine yerleşti ve orada duruyor. Çünkü çözdüğü problem modaya değil, yapıya ait.

Asıl soru şu: yığınınızda, kısıtlı bir atama problemini açgözlü bir top-k ile çözdüğünüz kaç yer var — ve bunların kaçının farkındasınız?

—

*Kaynak: Slava Efimov, “The Hungarian Algorithm and Its Applications in Computer Vision”, Towards Data Science, 9 Eylül 2025.*