Joseph Kruskal: MST Algoritmasının Mucidi ve Çok Boyutlu Ölçeklemenin Öncüsü

Üç Kruskal kardeş

ABD'de 20. yüzyılın ortasında, Kruskal ailesi matematikte alışılmadık bir başarı sergiledi: üç kardeş, üç matematikçi:

• William Kruskal (1919-2005): istatistikçi, Chicago Üniversitesi; Kruskal-Wallis istatistik testi.
• Martin Kruskal (1925-2006): fizikçi-matematikçi; soliton dalgalarının kâşifi, dipsiz kuyu plazma fiziği.
• Joseph Kruskal (1928-2010): bizim konumuz; istatistikçi-bilgisayar bilimcisi.

Üçü de en üst akademik kademede. Aile dinamiği matematiği yapıyordu.

Erken yıllar

• Doğum: 29 Ocak 1928, New York City.
• Aile: Yahudi orta sınıf. Babası kürk satıcısı; annesi okul yöneticisi.
• Eğitim: Chicago Üniversitesi (BS 1948, MS 1949). Princeton Üniversitesi (PhD 1954, danışman: Roger Lyndon).
• Doktora tezi: Yapraklı kategoriler ve iyi-quasi-sıralama. Soyut cebir-mantık kesişimi.

İlginç gözlem: Joseph'in tezi soyut mantık ve sıralama teorisiydi; ama hayatının asıl mirası uygulamalı algoritmalar ve istatistiksel veri analizinde geldi. Bu, akademik kariyerin tahmin edilemezliğine zarif bir örnek.

Bell Labs (1959-93)

1959'da Joseph Kruskal Bell Labs'a katıldı. Bu, 20. yüzyıl bilim tarihinin altın atölyesiydi: Claude Shannon (bilgi teorisi), John Tukey (FFT, EDA), Walter Brattain (transistör, Nobel), Dennis Ritchie (C dili, Unix), Ken Thompson (Unix).

Kruskal Bell Labs'in istatistik ve hesaplama grubunda 34 yıl çalıştı. Bu süreç boyunca:

• Akademik özgürlük: araştırma yapacağı konuyu seçti.
• Yayın patlaması: 100'den fazla makale.
• Mentor: Pek çok yeni istatistikçinin yetiştiricisi.

1956: MST algoritması

Princeton'da doktora bittikten sonra, henüz 28 yaşında, Joseph Kruskal minimum kapsayan ağaç problemine çözüm yayımladı.

Algoritma şıktı:

1. Kenarları ağırlığa göre sırala.
2. Küçükten büyüğe ekle; döngü oluşturanları atla.

Bu bir sayfalık makaleydi (Proceedings of the American Mathematical Society, 1956). Hızlı, sade, paralel hesaplamaya uygun. Bugün her bilgisayar bilimi giriş dersinde öğretilir.

İlginç tarihsel not: Joseph Otakar Borůvka'nın 1926'daki çalışmasını bilmiyordu — Slovakça yazılmıştı, İngilizce dünyada bilinmiyordu. Algoritmasını bağımsız buldu.

1964: Çok boyutlu ölçekleme (MDS)

8 yıl sonra Kruskal başka bir alanda devrim yaptı: çok boyutlu ölçekleme (Multidimensional Scaling, MDS).

Sorun: Elinizde $n$ nesne arasındaki mesafe matrisi var ($d_{ij}$). Bu nesneleri $k$-boyutlu uzayda (mesela 2B) öyle yerleştirin ki mesafe yapısı korunsun. Bu mümkün mü?

Klasik MDS (önceki çalışmalar) metrik mesafeleri varsayıyordu. Kruskal non-metric MDS geliştirdi: sadece mesafelerin sırası korunsun yeter.

Uygulamalar:

• Psikoloji: özneye nesneleri karşılaştırtın; sıraladığı benzerlikten 2B harita.
• Pazarlama: müşterilerin ürün karşılaştırmalarından "ürün haritası".
• Genetik: gen ifade verilerini 2B'de görselleştir.
• Sosyoloji: toplumsal yakınlık haritaları.

MDS bugün makine öğrenmesinde kategori azaltma (dimensionality reduction) tekniklerinin atasıdır. PCA, t-SNE, UMAP gibi modern teknikler MDS'in soyundan gelir.

Diğer katkıları

Kruskal ağaç teoremi (1960)

Sıralama teorisindeki şaheserlerinden biri: ağaçların iyi-quasi-sıralı olduğunu kanıtladı. Bu sonuç mantığın derinliklerine kadar uzanır — Friedman sonradan bu teoremin Peano aritmetiğinde kanıtlanamaz olduğunu gösterdi (Gödel benzeri sınır).

İstatistiksel paketler

Kruskal Bell Labs'da istatistik yazılımının gelişiminde kilit rol oynadı. S dili (sonradan R olacak) için temel fonksiyonların tasarımında yardım etti.

Kruskal-Wallis testi (kardeşi William ile)

1952'de William Kruskal ile birlikte: parametrik olmayan ANOVA. Üç veya daha fazla grup arasında istatistiksel fark testi için klasik araç. Sosyal bilimlerden tıbba kadar her yerde kullanılır.

Dil ve müzik tutkunu

Joseph'in matematik dışı dünyası da rengarenkti:

• Dilbilim: Çok sayıda dile (Latin Amerika dilleri, Bask dili) ilgi duydu. Matematiksel dilbilim çalışmaları yaptı: dillerin akrabalık ilişkilerinin istatistiksel olarak nasıl bulunabileceği.
• Müzik: profesyonel düzeyde flüt çaldı. New York'ta klasik müzik camiasında biliniyordu.
• Çocuk eğitimi: Bell Labs'in açık günlerinde çocuklara matematik öğretme etkinlikleri organize etti.

Ödüller ve tanınma

• John von Neumann Theory Prize (2002) — operasyon araştırması ödülü.
• IEEE Computer Pioneer Award (1984).
• American Statistical Association seçkin üye.
• American Mathematical Society seçkin üye.

Akademik takdir geç ama belirli geldi. Bell Labs'in özel doğası nedeniyle Joseph bir üniversite profesörlüğüne asla geçmedi; ama Princeton ve Stanford gibi yerlerde misafir profesör olarak ders verdi.

Hayat

Joseph Rachel Lieber ile evlendi. Üç çocuk dünyaya getirdiler — birisi (Anna) sonradan matematik tarihi profesörü oldu.

Bell Labs'in 1980'lerdeki çöküşü (AT&T parçalanması) Joseph'i etkiledi. 1993'te emekli oldu. Sonra New Jersey'de özel araştırmaya devam etti. Sayı teorisi, dilbilim, ve istatistiksel hesaplama üzerine yayınlamayı sürdürdü.

19 Eylül 2010, New York'ta öldü. 82 yaşında.

Mirası

Joseph Kruskal'ın matematik tarihindeki yeri özel:

• Kruskal MST algoritması (1956): her bilgisayar bilimi dersinin klasiği.
• Kruskal ağaç teoremi (1960): mantık ve sıralama teorisinin temel sonucu.
• Non-metric MDS (1964): modern boyut azaltma tekniklerinin atası.
• Kruskal-Wallis testi (1952, William ile): istatistik standardı.
• Bell Labs'in geleneği: araştırma özgürlüğü, multidisipliner yaklaşım.

Joseph hayatında Üç kardeşten ortancası olmadan da pek anılmıştı — ama matematik tarihinde üç farklı alanda klasikleşmiş katkılarıyla kendi yerini kazandı. Bell Labs'in altın çağında karakterli bir bilgin: alçakgönüllü, dil-müzik tutkunu, ve algoritmalarının matematik zarafetini hayatına da taşıyan biri.

Bir cümle ile: algoritmaların güzelliği, basit fikirlerden gelir — Kruskal'ın inancı. Ve her gün, her fiber optik şirketinin yazılımında, bu inanç yaşamaya devam ediyor.