Tekil Değer Ayrışımı Uygulaması

Önceki ders bileşen yönlerini eşdeğişim dizeyi üzerinden buldu ve her noktayı k yöne izdüşürüp geri kurdu. Ölçü nokta başına ortalama uzaklıktı ve sütun ortalamalarıyla geri kurma 3,3411 veriyordu. Yordamın sormadığı soru şuydu: bu gösterimi saklamak için kaç sayı gerekiyor. On iki sütunlu 252 satırlık bir tablo 3.024 sayıdır; iki bileşenli gösterim aynı tabloyu kaçla tutar.

Soru sorulduğu anda izdüşüm bir dizey işlemine dönüşür. Tablo, satırları abone ve sütunları ölçüm olan bir dizeydir; izdüşüm bu dizeyi iki küçük dizeyin çarpımı olarak yeniden yazmaktır. Tekil değer ayrışımı bunu yapan ayrışımdır: dizeyi, satır yönleri, sütun yönleri ve her yön çiftine bir ağırlık veren tekil değerler olarak üçe ayırır. İlk r tekil değeri tutup kalanı atmak düşük ranklı yaklaşım üretir. Bu dersin ölçtüğü şey o yaklaşımın iki tarafıdır: hata ne kadar artıyor ve saklanan sayı adedi ne kadar azalıyor.

• BA9. Ölçülen dizey sınama kümesidir: 252 satır, 12 sütun, 3.024 sayı. Sütunlar önceki dersteki ölçekle, yani yalnız eğitim kümesinden okunan ortalama ve standart sapmayla ölçeklenir.
• BA10. Ayrışım ders içinde yazılır ve modeldir: dizeyin sütun çarpım dizeyi kurulur, en büyük yön 300 yinelemede aranır, her yeni yön öncekilere diklenir, tekil değer bulunan büyüklüğün kökü olarak alınır. Kitaplık çağrılmaz ve ölçek küçük tutulur.
• BA11. Tekil değerler negatif değildir ve büyükten küçüğe sıralanır. Rank, sıfırdan farklı tekil değerlerin sayısıdır; eşik $10^{-10}$ alınmıştır, çünkü yinelemeli arama sıfırı tam olarak değil yaklaşık üretir.
• BA12. Saklanan sayı adedi açıkça sayılır: rank r için satır katsayıları $252r$, sütun yönleri $12r$, tekil değerler $r$, ve tabloyu özgün birimine döndürmek için 12 ortalama ile 12 standart sapma. Toplam $265r + 24$.
• BA13. Geri kurma hatası tanımı önceki dersten sürer: nokta başına ortalama uzaklık, ölçeklenmiş uzayda, birimi standart sapma.
• BA14. Taban çizgisi yine sütun ortalamalarıyla geri kurmadır ve rank 0 satırıdır.
• BA15. Küçük dizey elle kurulmuştur, abone tablosundan gelmez ve yalnız ayrışımın ne yaptığını görünür kılmak içindir.
• BA16. İkinci karşılaştırma aynı bütçeyle r ham sütun saklamaktır: rastgele r sütun tutulur, kalan sütunlar ortalamayla kurulur, üç çekiliş ortalanır.

Ayrışım Küçük Bir Dizeyde

Altı satırlı, beş sütunlu bir dizey elle kurulur. Satırların çoğu iki temel örüntünün ağırlıklı toplamıdır: biri uçlarda yüksek ortada düşük, öbürü tam tersi. Üçüncü satırın ilk hücresi bilerek bir birim kaydırılmıştır, böylece dizey iki örüntüye tam oturmaz.

def carp(m, v):
    return [sum(m[i][j] * v[j] for j in range(len(v))) for i in range(len(m))]


def diklestir(v, B):
    for u in B:
        c = sum(v[i] * u[i] for i in range(len(v)))
        v = [v[i] - c * u[i] for i in range(len(v))]
    return v


def ayristir(A):
    # MODELDIR: tekil deger ayrisimi ders icinde, yalniz standart kitaplikla yazilir.
    m = len(A[0])
    G = [[sum(s[i] * s[j] for s in A) for j in range(m)] for i in range(m)]
    sag, tekil = [], []
    for _ in range(m):
        v, lam = [1.0 / (i + 1) for i in range(m)], 0.0
        for _ in range(300):
            w = diklestir(carp(G, v), sag)
            u = sum(q * q for q in w) ** 0.5
            if u < 1e-12:
                break
            v, lam = [q / u for q in w], u
        if lam < 1e-10:
            break
        sag.append(v)
        tekil.append(lam ** 0.5)
    sol = [[sum(s[j] * v[j] for j in range(m)) / tekil[i] for s in A]
           for i, v in enumerate(sag)]
    return sol, tekil, sag


def yaklas(sol, tekil, sag, r, a, b):
    return sum(sol[i][a] * tekil[i] * sag[i][b] for i in range(r))


KUCUK = [[6, 3, 0, 3, 6], [4, 3, 2, 3, 4], [3, 3, 4, 3, 2],
         [0, 3, 6, 3, 0], [4, 4, 4, 4, 4], [2, 2, 2, 2, 2]]
SOL, TEKIL, SAG = ayristir([[float(q) for q in s] for s in KUCUK])
print("tekil degerler: " + ", ".join(f"{s:.4f}" for s in TEKIL))
print(f"{'rank':>4} {'toplam hata':>12} {'atilanlarin koku':>17} {'saklanan':>9}")
for r in range(len(TEKIL) + 1):
    h = sum((KUCUK[a][b] - yaklas(SOL, TEKIL, SAG, r, a, b)) ** 2
            for a in range(6) for b in range(5)) ** 0.5
    print(f"{r:>4} {h:>12.4f} {sum(s * s for s in TEKIL[r:]) ** 0.5:>17.4f} "
          f"{r * (6 + 5 + 1):>9}")
print("ozgun dizey 30 sayi. rank 2 yaklasim:")
for a in range(6):
    print("  " + " ".join(f"{yaklas(SOL, TEKIL, SAG, 2, a, b):6.2f}" for b in range(5)))

tekil degerler: 17.0637, 7.3058, 0.6746
rank  toplam hata  atilanlarin koku  saklanan
   0      18.5742           18.5742         0
   1       7.3369            7.3369        12
   2       0.6746            0.6746        24
   3       0.0000            0.0000        36
ozgun dizey 30 sayi. rank 2 yaklasim:
    6.03   2.99   0.01   2.99   5.98
    4.07   2.98   2.02   2.98   3.95
    2.54   3.12   3.90   3.12   2.34
    0.16   2.96   6.04   2.96  -0.12
    4.13   3.97   4.03   3.97   3.90
    2.06   1.98   2.01   1.98   1.95

İki sütun birbirine birebir eşit. Rank r yaklaşımın toplam hatası, atılan tekil değerlerin karelerinin toplamının köküdür — rank 2’de hata 0,6746 ve atılan tek tekil değer de 0,6746. Bu, ayrışımın verdiği en kullanışlı şeydir: hata, yaklaşım kurulmadan önce, yalnız tekil değerler listesine bakılarak bilinir. Yordamı çalıştırıp ölçmeye gerek yoktur.

İkinci sütun okumayı tersine çevirir. Rank 2 yaklaşım 24 sayı saklar, özgün dizey 30 sayı; kazanç 6 sayıdır ve hata 0,6746’dır. Rank 3 yaklaşım hatasızdır ama 36 sayı saklar — özgün dizeyden 6 fazla. Tam ayrışım sıkıştırma değildir. Kazanç yalnız atılan ranktan gelir ve dizeyin kendisi küçükse hiç gelmeyebilir.

Yaklaşımın çıktısı da okunabilir. İlk, ikinci, dördüncü, beşinci ve altıncı satırlar neredeyse birebir geri geliyor, çünkü onlar gerçekten iki örüntünün toplamıydı. Kaydırılmış üçüncü satır 3, 3, 4, 3, 2 yerine 2.54, 3.12, 3.90, 3.12, 2.34 dönüyor. Hatanın tamamı bu tek satırda toplanmış durumda. Düşük ranklı yaklaşım hatayı eşit dağıtmaz; örüntüye uymayan satırı düzeltir ve o satır hakkındaki bilgiyi atar.

Abone Tablosunda Rank ve Saklanan Sayı

Aynı ayrışım 252 satırlık, 12 sütunlu abone tablosuna uygulanır. Sütunlar önceki dersteki ölçekle ölçeklenir, ki taban çizgisi değişmesin.

import math

TOHUM, HAM, M32 = 20260218, 1400, 0xFFFFFFFF
BOLGE = [("kuzey", 0.28, 21), ("guney", 0.22, 17), ("dogu", 0.18, 26),
         ("bati", 0.14, 14), ("merkez", 0.18, 23)]


def uretec(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def sonraki():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return sonraki


def ayrik(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


ABONE, VERI = [], []
for i in range(HAM):
    r = uretec(TOHUM + i)
    b = BOLGE[ayrik(r(), [x[1] for x in BOLGE])]
    hane = 1 + ayrik(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    memnun = 1 + ayrik(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() >= 0.046:
        ABONE.append({"no": 10001 + i, "bolge": b, "hane": hane, "memnuniyet": memnun})
for k in ABONE:
    r, v = uretec(TOHUM + 7000 + k["no"]), []
    for d in range(ayrik(r(), [0.05, 0.12, 0.21, 0.62])):
        v.append(0.0 if r() < 0.038 else math.floor(
            k["bolge"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        continue
    ort = sum(v) / len(v)
    x = {"hane": k["hane"], "memnuniyet": k["memnuniyet"], "donem": len(v),
         "ort_tuketim": round(ort, 2), "oynaklik": round(max(v) - min(v), 2),
         "sifir_okuma": int(min(v) == 0.0), "kisi_basi": round(ort / k["hane"], 3)}
    for b in BOLGE:
        x["b_" + b[0]] = int(k["bolge"][0] == b[0])
    VERI.append(x)

ALAN = ["ort_tuketim", "oynaklik", "kisi_basi", "hane", "memnuniyet", "donem",
        "sifir_okuma", "b_kuzey", "b_guney", "b_dogu", "b_bati", "b_merkez"]
r, s = uretec(TOHUM + 90000), list(range(len(VERI)))
for i in range(len(s) - 1, 0, -1):
    j = int(r() * (i + 1))
    s[i], s[j] = s[j], s[i]
K = [VERI[i] for i in s]
EGT, SIN = K[:756], K[1008:]

n = len(ALAN)
ORT = {a: sum(x[a] for x in EGT) / len(EGT) for a in ALAN}
SAC = {a: max(1e-9, (sum((x[a] - ORT[a]) ** 2 for x in EGT) / len(EGT)) ** 0.5)
       for a in ALAN}
Z = [[(x[a] - ORT[a]) / SAC[a] for a in ALAN] for x in SIN]
N = len(Z)
SOL, TEKIL, SAG = ayristir(Z)


def hata(r):
    return sum(sum((Z[a][b] - yaklas(SOL, TEKIL, SAG, r, a, b)) ** 2
                   for b in range(n)) ** 0.5 for a in range(N)) / N


print(f"ozgun tablo {N} x {n} = {N * n} sayi, bulunan rank {len(TEKIL)}")
print("tekil degerler: " + ", ".join(f"{s:.2f}" for s in TEKIL))
print(f"{'rank':>4} {'hata':>8} {'fark':>8} {'saklanan':>9} {'oran':>6}")
for r in (0, 1, 2, 3, 4, 6, 8, 10, 11):
    print(f"{r:>4} {hata(r):>8.4f} {hata(r) - hata(0):>+8.4f} "
          f"{24 + r * (N + n + 1):>9} {(24 + r * (N + n + 1)) / (N * n):>6.3f}")

ozgun tablo 252 x 12 = 3024 sayi, bulunan rank 11
tekil degerler: 24.19, 21.44, 19.46, 18.48, 18.14, 16.64, 15.66, 14.15, 10.50, 7.14, 5.69
rank     hata     fark  saklanan   oran
   0   3.3411  +0.0000        24  0.008
   1   3.0129  -0.3282       289  0.096
   2   2.7464  -0.5947       554  0.183
   3   2.4284  -0.9127       819  0.271
   4   2.1363  -1.2048      1084  0.358
   6   1.5054  -1.8357      1614  0.534
   8   0.7925  -2.5486      2144  0.709
  10   0.2568  -3.0843      2674  0.884
  11   0.0000  -3.3411      2939  0.972

Tekil değerler bu tabloda hiç dik inmiyor: en büyüğü 24,19, en küçüğü 5,69 ve arada bir uçurum yok. Küçük dizeyde iki tekil değer 17,06 ve 7,31 iken üçüncüsü 0,67’ye düşüyordu; orada rank 2 doğal bir kesme noktasıydı. Burada öyle bir nokta yok. Bu, kesmenin veriden değil karardan geldiği anlamına gelir ve kararın bedeli tabloda okunur.

Rank 2 yaklaşım 3.024 sayı yerine 554 sayı saklıyor — özgünün 0,183’ü — ve hatayı tabandan 0,5947 aşağı çekiyor. Rank 8’e çıkıldığında hata 0,7925’e iniyor ama saklanan sayı 2.144’e, yani özgünün 0,709’una çıkıyor. Rank 11’de hata sıfır ve saklama 2.939 sayı; özgün 3.024’ten yalnız 85 sayı az. Hatasız sıkıştırma bu tabloda pratikte yok, çünkü rank on birdir ve on iki sütunla arasındaki tek fark bölge göstergelerinin toplamıdır — önceki dersin on birinci yönde sıfıra inen hatası burada rank olarak adını buluyor.

Aynı Bütçeyle Ham Sütun Saklamak

Sayı adedi bir bütçedir ve bütçeyi harcamanın başka bir yolu vardır: ham sütunların bir kısmını olduğu gibi tutup kalanını ortalamayla kurmak. Bu, önceki kursun öznitelik seçimi konusunda ölçtüğü karara benzer ama burada ölçüt farklıdır — soru hangi sütunun ayırt ettiği değil, hangi sütunun tabloyu geri kurduğudur. Karşılaştırma anlamlı olsun diye tutulacak sütunlar rastgele seçilir ve üç çekiliş ortalanır.

def sutun_taban(r, tohum):
    rr, idx = uretec(tohum), list(range(n))
    for i in range(n - 1, 0, -1):
        j = int(rr() * (i + 1))
        idx[i], idx[j] = idx[j], idx[i]
    tut = set(idx[:r])
    return sum(sum(z[j] * z[j] for j in range(n) if j not in tut) ** 0.5
               for z in Z) / N


print(f"{'r':>3} {'dusuk rank':>11} {'saklanan':>9} {'r ham sutun':>12} "
      f"{'saklanan':>9} {'fark':>8}")
for r in (1, 2, 4, 6, 8, 11):
    st = sum(sutun_taban(r, TOHUM + 500 * (t + 1)) for t in range(3)) / 3
    print(f"{r:>3} {hata(r):>11.4f} {24 + r * (N + n + 1):>9} {st:>12.4f} "
          f"{r * N + r:>9} {st - hata(r):>+8.4f}")

  r  dusuk rank  saklanan  r ham sutun  saklanan     fark
  1      3.0129       289       3.2008       253  +0.1879
  2      2.7464       554       3.0617       506  +0.3153
  4      2.1363      1084       2.6787      1012  +0.5423
  6      1.5054      1614       2.2730      1518  +0.7676
  8      0.7925      2144       1.7588      2024  +0.9663
 11      0.0000      2939       0.7857      2783  +0.7857

İki yol neredeyse aynı bütçeyi harcıyor: rank 2 için 554 sayı, iki ham sütun için 506. Fark 48 sayıdır, bütçenin yüzde onundan azı. Karşılığında alınan hata farkı rank 2’de 0,3153. Düşük ranklı yaklaşım kazanıyor, ama kazanç küçük — ve bu tablo için önemli bir bulgudur, çünkü boyut azaltmanın ham sütun saklamaya üstünlüğünün kendiliğinden olduğu varsayılır.

Üstünlük rank büyüdükçe açılıyor: 4’te 0,5423, 6’da 0,7676, 8’de 0,9663. Nedeni tekil değer listesinde duruyor. Düşük ranklı yaklaşım her rankta dizeyin o rankta taşınabilecek en iyi parçasını alır; ham sütun saklamak ise sütunları olduğu gibi alır ve sütunlar arasındaki ortak yapıyı hiç kullanmaz. Rank arttıkça bu ortak yapı birikir. Rank 11’de fark tersine dönmeye başlar (0,7857), çünkü rank 11 zaten hatasızdır ve karşı taraf tek bir sütunu atmanın hatasını taşır.

Karar bu iki tablodan okunur. Sıkıştırma amacıyla düşük ranklı yaklaşım kullanmak, hatayı tekil değerlerden önceden bilebilmek ve her sayıya karşılık en çok geri kurmayı almak demektir. Ama tablo dar ve rank yüksekse, kazanç ne saklamada ne hatada büyüktür — 3.024 sayının 554’e inmesi hatanın tabandan yalnız 0,5947 uzaklaşmasıyla ödenir.

Özet

• Tekil değer ayrışımı dizeyi satır yönleri, sütun yönleri ve tekil değerler olarak yazar; ilk r terimi tutmak düşük ranklı yaklaşımdır.
• Geri kurma hatası atılan tekil değerlerden okunur: küçük dizeyde rank 2’nin toplam hatası 0,6746 ve atılan tek tekil değer de 0,6746’dır.
• Tam ayrışım sıkıştırma değildir: küçük dizeyde rank 3 yaklaşım hatasızdır ama 36 sayı saklar, özgün dizey 30 sayıdır.
• Abone tablosunda taban çizgisi 3,3411; rank 2 yaklaşım 2,7464 verir ve 3.024 sayı yerine 554 sayı saklar. Rank 11 hatasızdır ve yalnız 85 sayı kazandırır.
• Aynı bütçeyle rastgele ham sütun saklamak rank 2’de 3,0617 verir; düşük ranklı yaklaşımın üstünlüğü orada 0,3153’tür ve ancak rank 8’de 0,9663’e çıkar.

Sonraki Adım

İki derste izdüşüm hep aynı biçimdeydi: her yeni sayı, eski sütunların ağırlıklı toplamıydı. Bu kısıt hatayı hesaplanabilir kıldı ve tekil değerlerden okunmasını sağladı, ama bir bedeli var — doğrular yalnız doğrulara gider. Noktalar bir düzlemde değil de kıvrılmış bir yüzeyde duruyorsa, ağırlıklı toplamla kurulan hiçbir izdüşüm o kıvrımı takip edemez ve komşu noktalar izdüşümde birbirinden uzağa düşer. Sonraki ders bu kısıtı kaldıran yaklaşımları ele alır: uzaklıkları değil komşulukları korumayı hedefleyen gömmeler. Ölçü de değişir, çünkü geri kurma hatası orada tanımsızdır — sorulacak soru, özgün uzayda en yakın komşuların kaçının gömmede de komşu kaldığıdır.