Marj Temelli Sınıflandırıcı

Önceki iki aile kararını bütün eğitim kümesine eşit ağırlıkta dayandırdı: komşu yordamında 31 komşunun her biri bir oy verdi, sayan ailede her satır bir hücreyi bir birim büyüttü.

Bu ders bunun tersini yapan bir aile alır. Marj temelli sınıflandırıcı sınırı iki sınıf arasındaki boşluğun ortasına oturtur ve yalnız o boşluğa giren örneklerle ilgilenir; boşluğun genişliğine marj denir. Aile ayrıca eğri sınırı sütun açmadan üretebilen bir yapı taşır: çekirdek dönüşümü. Ders üçünü de sayar — marj genişliği ile ayrılmış küme sayısı arasındaki ilişkiyi, kararı taşıyan örnek sayısını ve çekirdeğin açık sütunlara göre kazandırdığını.

• DO17. Küme, bölme ve taban çizgisi değişmez: 1.260 abonelik kurgu tablo, tohum 20260218, bölme 756/252/252, taban çizgisi sınamada 0,7579 ve doğrulamada 0,8135. Öznitelik kümesi K02’den gelen on iki sütundur; ölçek yalnız eğitim kümesinden öğrenilir.
• DO18. Etiketler $+1$ ve $-1$ yazılır. Model, marj kaybı ile ağırlıkların karesel cezasının toplamını küçültür; ceza katsayısı bu dersin ayar değişkenidir ve marj genişliği $2 / \lVert w \rVert$’dir.
• DO19. Destek vektörü, marjın içinde ya da yanlış tarafında kalan eğitim satırıdır; marjın dışındakiler kayba hiç katkı vermez.
• DO20. Çözücü, adımı $1/(\lambda t)$ ile küçülen bir alt eğim inişidir ve birincil biçimde 300, ikili biçimde 40 tur döner; basılan sayılar bu sabit bütçenin sayılarıdır.
• DO21. Çekirdek, genişletilmiş bir uzaydaki iç çarpımı o uzayı kurmadan veren işlevdir. Polinom çekirdeği $(x \cdot z + 1)^2/10$, radyal çekirdek $e^{-0{,}05 \lVert x - z \rVert^2}$ biçimindedir; ondalık katsayılar üç çekirdekte de aynı ceza aralığı kullanılabilsin diye sabittir. İkili biçim eğitim satırı sayısının karesi kadar çekirdek değeri tutar.
• DO22. Seçim doğrulama kümesinden okunur; beraberlikte daha geniş marj seçilir.

Marjın Genişliği

Kurulum kümeyi üretir, modeli yazar ve ceza katsayısını sekiz değerde süpürür.

# marj.py — MODELDIR. M27/K01 ve K02'nin KURGU abone tablosu ayni tohumla
# uretilir; oznitelik kumesi K02'den gelir ve kurs boyunca sabittir.
import math
import statistics


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


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, oyn, r = sum(v) / len(v), max(v) - min(v), uretec(TOHUM + 51000 + k["no"])
    z = (0.052 * (ort - 20) + 0.85 * (min(v) == 0.0) + 0.026 * oyn
         + 0.24 * (k["hane"] >= 5) - 0.20 * (k["memnuniyet"] >= 4) + k["bolge"][3]
         + 0.9 * (k["no"] - 10001) / 1399 + (r() + r() + r() - 1.5) * 1.30)
    x = {"hane": k["hane"], "memnuniyet": k["memnuniyet"], "donem": len(v),
         "ort_tuketim": round(ort, 2), "oynaklik": round(oyn, 2),
         "sifir_okuma": int(min(v) == 0.0), "supheli": int(z > 1.35)}
    for b in BOLGE:
        x["b_" + b[0]] = int(k["bolge"][0] == b[0])
    x["kisi_basi"] = round(x["ort_tuketim"] / x["hane"], 3)
    VERI.append(x)


SAYISAL = ["ort_tuketim", "oynaklik", "hane", "memnuniyet", "donem", "kisi_basi"]
ALAN = SAYISAL + ["sifir_okuma", "b_kuzey", "b_guney", "b_dogu", "b_bati", "b_merkez"]


def karistir(veri, tohum):
    r, s = uretec(tohum), 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]
    return [veri[i] for i in s]


K = karistir(VERI, TOHUM + 90000)
EGT, DOG, SIN = K[:756], K[756:1008], K[1008:]
TABAN_SIN = sum(x["supheli"] == 0 for x in SIN) / len(SIN)
OLCEK = {a: (statistics.fmean(x[a] for x in EGT),
             statistics.pstdev([x[a] for x in EGT])) for a in SAYISAL}


def vektor(s):                              # etiketler +1 / -1
    return [([(x[a] - OLCEK[a][0]) / OLCEK[a][1] if a in OLCEK else x[a]
              for a in ALAN], 1 if x["supheli"] else -1) for x in s]


VE, VD, VS = vektor(EGT), vektor(DOG), vektor(SIN)


def skor(w, b, v):
    return sum(w[i] * v[i] for i in range(len(w))) + b


def marj_egit(egt, lam, tur=300, n=None):   # MODELDIR: marj temelli siniflandirici
    d, n = len(egt[0][0]), n or len(egt)
    w, b = [0.0] * d, 0.0
    for t in range(1, tur + 1):
        adim, gw, gb = 1.0 / (lam * t), [0.0] * d, 0.0
        for v, y in egt:
            if y * skor(w, b, v) < 1:       # marjin icinde ya da yanlis tarafta
                for i in range(d):
                    gw[i] -= y * v[i]
                gb -= y
        for i in range(d):
            w[i] -= adim * (gw[i] / n + lam * w[i])
        b -= adim * gb / n
    return w, b


def dogruluk(m, hedef):
    return sum((skor(m[0], m[1], v) > 0) == (y > 0) for v, y in hedef) / len(hedef)


ADAY = {}
print(f"taban cizgisi sinamada {TABAN_SIN:.4f}; egitim {len(VE)} satir, {len(ALAN)} sutun")
print(f"{'ceza':>8} {'|w|':>7} {'marj':>8} {'destek':>7} {'dogrulama':>10} {'sinama':>8}")
for lam in (0.0003, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1.0):
    m = marj_egit(VE, lam)
    nw = math.sqrt(sum(x * x for x in m[0]))
    ADAY[lam] = (dogruluk(m, VD), dogruluk(m, VS))
    ic = sum(1 for v, y in VE if y * skor(m[0], m[1], v) < 1)
    print(f"{lam:>8} {nw:>7.3f} {2 / nw:>8.3f} {ic:>7} "
          f"{ADAY[lam][0]:>10.4f} {ADAY[lam][1]:>8.4f}")
en = max(ADAY, key=lambda a: (ADAY[a][0], a))
kucuk = max(ADAY, key=lambda a: (ADAY[a][0], -a))
print(f"denenen aday {len(ADAY)}; dogrulamadan secilen ceza {en} -> sinama "
      f"{ADAY[en][1]:.4f}, taban cizgisinin {ADAY[en][1] - TABAN_SIN:+.4f} ustunde")
print(f"beraberlik en kucuk ceza lehine cozulseydi ceza {kucuk} -> sinama "
      f"{ADAY[kucuk][1]:.4f}")

taban cizgisi sinamada 0.7579; egitim 756 satir, 12 sutun
    ceza     |w|     marj  destek  dogrulama   sinama
  0.0003  42.768    0.047     252     0.7421   0.7619
   0.001  12.742    0.157     338     0.8294   0.8016
   0.003   4.289    0.466     320     0.8294   0.7976
    0.01   1.587    1.260     324     0.8294   0.7857
    0.03   0.833    2.401     333     0.8175   0.7857
     0.1   0.266    7.523     334     0.8135   0.7579
     0.3   0.075   26.789     335     0.8135   0.7579
     1.0   0.021   93.488     335     0.8135   0.7579
denenen aday 8; dogrulamadan secilen ceza 0.01 -> sinama 0.7857, taban cizgisinin +0.0278 ustunde
beraberlik en kucuk ceza lehine cozulseydi ceza 0.001 -> sinama 0.8016

Marj 0,047’den 93,488’e genişliyor ve tablonun iki ucu da kötüdür. En dar marjda ağırlık vektörünün uzunluğu 42,768’e çıkıyor ve doğrulama sayısı kendi tabanının 0,0714 altına düşüyor; en geniş marjda sınır düzleşiyor ve model sınamada tam olarak taban çizgisini okuyor. Aradaki üç aday doğrulama kümesinde 0,8294’te beraberedir.

Beraberliğin çözümü bir karardır ve son iki satır bedelini veriyor. Geniş marj lehine çözüldüğünde ceza 0,01 seçiliyor ve ailenin sayısı 0,7857 oluyor, taban çizgisinin 0,0278 üstünde; dar marj lehine çözülseydi 0,8016 bildirilirdi. Aradaki 0,0159 dört abone eder ve hiçbir ölçümden değil yalnız beraberlik kuralından gelir.

Kararı Kaç Örnek Taşıyor

Destek vektörü sayısı tabloda duruyor ama tek başına bir iddia değildir; kararı taşıyıp taşımadıkları, o satırlar atılıp model yeniden eğitilerek ölçülür.

SECILEN = 0.01
M = marj_egit(VE, SECILEN)
T0 = [skor(M[0], M[1], v) > 0 for v, _ in VS]
IC = [i for i, (v, y) in enumerate(VE) if y * skor(M[0], M[1], v) < 1]
DIS = [i for i, (v, y) in enumerate(VE) if y * skor(M[0], M[1], v) >= 1]
r = uretec(TOHUM + 610000)


def rastgele_sec(havuz, k):
    h = list(havuz)
    for i in range(len(h) - 1, 0, -1):
        j = int(r() * (i + 1))
        h[i], h[j] = h[j], h[i]
    return set(h[:k])


print(f"ceza {SECILEN}: marj icinde {len(IC)} satir, marj disinda {len(DIS)} satir")
print(f"{'atilan':>7} {'havuz':>14} {'degisen tahmin':>15} {'sinama':>8}")
for k in (200, 300):
    for ad, havuz in (("marj disindan", DIS), ("marj icinden", IC)):
        at = rastgele_sec(havuz, k)
        m2 = marj_egit([p for i, p in enumerate(VE) if i not in at], SECILEN, n=len(VE))
        t2 = [skor(m2[0], m2[1], v) > 0 for v, _ in VS]
        print(f"{k:>7} {ad:>14} {sum(a != b for a, b in zip(T0, t2)):>15} "
              f"{dogruluk(m2, VS):>8.4f}")

ceza 0.01: marj icinde 324 satir, marj disinda 432 satir
 atilan          havuz  degisen tahmin   sinama
    200  marj disindan               0   0.7857
    200   marj icinden              15   0.7817
    300  marj disindan               4   0.7937
    300   marj icinden              21   0.7579

Seçilen adayda 756 eğitim satırının 324’ü marjın içindedir; bu, sınıfların ne kadar iç içe geçtiğinin ölçüsüdür. Marjın dışından 300 satır atıldığında 252 sınama satırının yalnız dördünde tahmin değişiyor, 200 satır atıldığında hiçbiri değişmiyor. Marjın içinden aynı sayıda satır atıldığında değişen tahmin 21’e çıkıyor. Değişen tahmin sayısı bir kayıp ölçüsü de değildir: marj dışından 300 satır atıldığında sınama sayısı 0,7937’ye çıkıyor. Ölçülen şey sınırın oynamasıdır.

Çekirdek Dönüşümü

Eğri sınır iki yolla elde edilir. Birincisi sütunları açmaktır: kareler ve çarpımlar hesaplanıp tabloya eklenir. İkincisi çekirdek dönüşümüdür — model iki satırın genişletilmiş uzaydaki iç çarpımından başka bir şey kullanmadığı için, o iç çarpımı doğrudan veren bir işlev yazılırsa uzayı kurmaya gerek kalmaz. Bunun için model ikili biçimde yazılır: ağırlık vektörü yerine eğitim satırlarının katsayıları tutulur.

def gram(A, B):                             # ic carpim matrisi; cekirdekler bundan turer
    return [[sum(p * q for p, q in zip(a, b)) for b, _ in B] for a, _ in A]


def cekirdek(ad, G, n1, n2):
    if ad == "dogrusal":
        return G
    if ad == "polinom":                     # (x . z + 1)^2 / 10
        return [[(g + 1.0) ** 2 / 10.0 for g in s] for s in G]
    return [[math.exp(-0.05 * (n1[i] + n2[j] - 2 * g)) for j, g in enumerate(s)]
            for i, s in enumerate(G)]       # radyal cekirdek


def ikili_egit(K, y, lam, tur=40):          # MODELDIR: ayni olcut, ikili bicimde
    n, a, b = len(y), [0.0] * len(y), 0.0
    for t in range(1, tur + 1):
        adim = 1.0 / (lam * t)
        f = [sum(a[j] * K[i][j] for j in range(n)) + b for i in range(n)]
        a, gb = [x * (1.0 - adim * lam) for x in a], 0.0
        for i in range(n):
            if y[i] * f[i] < 1:
                a[i] += adim * y[i] / n
                gb += y[i]
        b += adim * gb / n
    return a, b


def ikili_dogruluk(a, b, KH, hedef):
    return sum((sum(a[j] * KH[i][j] for j in range(len(a))) + b > 0) == (y > 0)
               for i, (v, y) in enumerate(hedef)) / len(hedef)


Y = [y for _, y in VE]
GE, GD, GS = gram(VE, VE), gram(VD, VE), gram(VS, VE)
NE = [sum(p * p for p in v) for v, _ in VE]
ND = [sum(p * p for p in v) for v, _ in VD]
NS = [sum(p * p for p in v) for v, _ in VS]
CEK = {}
print(f"{'cekirdek':<10}{'ceza':>8}{'dogrulama':>11}{'sinama':>8}")
for ad in ("dogrusal", "polinom", "radyal"):
    K = cekirdek(ad, GE, NE, NE)
    KD, KS_ = cekirdek(ad, GD, ND, NE), cekirdek(ad, GS, NS, NE)
    for lam in (0.003, 0.01, 0.03):
        a, b = ikili_egit(K, Y, lam)
        CEK[(ad, lam)] = (ikili_dogruluk(a, b, KD, VD), ikili_dogruluk(a, b, KS_, VS))
        print(f"{ad:<10}{lam:>8}{CEK[(ad, lam)][0]:>11.4f}{CEK[(ad, lam)][1]:>8.4f}")
sec = max(CEK, key=lambda a: (CEK[a][0], -a[1]))
print(f"denenen aday {len(ADAY) + len(CEK)} (dogrusal {len(ADAY)} + cekirdek {len(CEK)}); "
      f"dogrulamadan secilen {sec[0]}, ceza {sec[1]} -> sinama {CEK[sec][1]:.4f}")
print(f"cekirdek matrisi {len(VE)} x {len(VE)} = {len(VE) ** 2} giris")

cekirdek      ceza  dogrulama  sinama
dogrusal     0.003     0.8016  0.7817
dogrusal      0.01     0.8095  0.7897
dogrusal      0.03     0.8294  0.7857
polinom      0.003     0.7778  0.7857
polinom       0.01     0.7897  0.7778
polinom       0.03     0.8175  0.7937
radyal       0.003     0.7222  0.6627
radyal        0.01     0.8135  0.7579
radyal        0.03     0.8135  0.7579
denenen aday 17 (dogrusal 8 + cekirdek 9); dogrulamadan secilen dogrusal, ceza 0.03 -> sinama 0.7857
cekirdek matrisi 756 x 756 = 571536 giris

Dokuz adayın hiçbiri düz sınırı geçemiyor. Doğrulamadan okunan seçim doğrusal çekirdektir ve sınama sayısı 0,7857’dir, birincil biçimin verdiği sayının aynısı. Polinom çekirdeğinin en yüksek sınama sayısı 0,7937’dir ve doğrusal çekirdeğinkini geçer, ama doğrulama sayısı 0,8175’te kalıyor; o adayı seçmek sınama kümesine bakmak olurdu. Radyal çekirdek en küçük cezada taban çizgisinin 0,0952 altına düşüyor. Eğri sınırın bu kümede kattığı fark, seçim doğrulama kümesinden okunduğunda sıfırdır; bedeli ise görünürdedir, ikili biçim 756 katsayı tutar ve 571.536 çekirdek girişi hesaplar.

Geriye çekirdeğin asıl iddiası kalıyor: aynı model, sütunlar açıkça hesaplandığında da aynı kararı vermelidir.

def acik_polinom(v):        # (x . z + 1)^2 / 10 cekirdegine denk acik sutunlar
    d = len(v)
    o = [math.sqrt(2) * v[i] for i in range(d)] + [v[i] * v[i] for i in range(d)]
    o += [math.sqrt(2) * v[i] * v[j] for i in range(d) for j in range(i + 1, d)]
    return [x / math.sqrt(10.0) for x in o]


AE = [(acik_polinom(v), y) for v, y in VE]
AS = [(acik_polinom(v), y) for v, y in VS]
LAM = 0.03
ma = marj_egit(AE, LAM, tur=40)
KE_, KS_ = cekirdek("polinom", GE, NE, NE), cekirdek("polinom", GS, NS, NE)
a, b = ikili_egit(KE_, Y, LAM)
tk = [sum(a[j] * KS_[i][j] for j in range(len(a))) + b > 0 for i in range(len(VS))]
ta = [skor(ma[0], ma[1], v) > 0 for v, _ in AS]
print(f"acikca hesaplanan sutun {len(AE[0][0])}, cekirdekle acilan sutun 0")
print(f"acik sutunlarla sinama  {dogruluk(ma, AS):.4f}")
print(f"cekirdekle sinama       {CEK[('polinom', LAM)][1]:.4f}")
print(f"iki bicimin ayni tahmini verdigi sinama satiri "
      f"{sum(p == q for p, q in zip(tk, ta))}/{len(VS)}")

acikca hesaplanan sutun 90, cekirdekle acilan sutun 0
acik sutunlarla sinama  0.7937
cekirdekle sinama       0.7937
iki bicimin ayni tahmini verdigi sinama satiri 252/252

On iki sütunun ikinci dereceden bütün terimleri 90 sütun açar ve iki biçim 252 sınama satırının 252’sinde aynı tahmini verir. Kazanç sayıda değil açılmayan sütundadır: derece üçe çıksaydı açılacak sütun 454’e giderken çekirdek işlevi tek bir üs değişikliğiyle kalırdı. On yedi aday denendi, ailenin sayısı 0,7857’dir ve eğri sınır taban çizgisi üstündeki farka hiçbir şey eklemedi.

Özet

• Marj genişliği ceza katsayısıyla 0,047’den 93,488’e çıkar; en dar marjda doğrulama sayısı kendi tabanının 0,0714 altına düşer.
• Ailenin sayısı 0,7857’dir ve taban çizgisini 0,0278 geçer; doğrulamada üç aday berabere kaldığı için bu sayının 0,0159’u beraberlik kuralından gelir.
• Kararı marj içindeki 324 satır taşır: marj dışından 300 satır atılınca 4, marj içinden 21 tahmin değişir.
• Üç çekirdekle dokuz aday denendi; seçilen çekirdek doğrusaldır ve eğri sınır hiçbir şey eklemedi.
• Polinom çekirdeği, açıkça hesaplanmış 90 sütunla 252 sınama satırının 252’sinde aynı tahmini verir; ikili biçimin bedeli 571.536 çekirdek girişidir.

Sonraki Adım

Üç ailenin ortak bir kısıtı vardı: uzaklık toplamı, olasılık çarpımı ve iç çarpım bütün sütunları aynı anda kullanır ve hangi sütunun kararı taşıdığı ancak dolaylı okunur. Sonraki ders sütunları teker teker ele alan bir aileye döner: karar ağacı her adımda tek bir sütun ve tek bir eşik seçer, seçimi bir bölme ölçütüne göre yapar. Ağacın kendisi M27/K01 ve K02 boyunca kullanıldı ve derinliği ölçüldü; sorulmayan şey, bölmeyi hangi ölçütün seçtiği ve derinliği baştan sınırlamak yerine büyümüş ağacı budamanın neyi geri aldığıdır.