Ardışık Artırma

Önceki ders kırk bir ağacı birbirinden bağımsız kurdu; hiçbiri ötekinin nerede yanıldığını bilmiyordu. Bağımsızlık saçılmayı 0,0193’ten 0,0075’e düşürdü ama sınama ortalamasını yalnız dört abone yukarı taşıdı. Bu ders ters yönü dener: her yeni model, öncekilerin kalan hatasına bakarak kurulur.

Ardışık artırma (boosting) bir toplam kurar. Başlangıç, eğitim kümesindeki şüpheli oranının logitidir; her tur, toplamın her abonede bıraktığı farka bir zayıf öğrenici uydurur ve katkısını bir öğrenme adımı ile çarparak toplama ekler. Zayıf öğrenici burada bir ya da iki bölmeli küçük bir ağaçtır. Ölçülen üç şey var: tur sayısı arttıkça iki sayının ayrışması, adım ile tur sayısının birbirinin yerine geçmesi, ve bunların ayar bütçesine yazdığı hesap.

• DO37. Küme, bölme ve taban çizgisi önceki derstekiyle aynıdır: 1.260 abone, 756/252/252, tohum 20260218, taban çizgisi sınamada 0,7579 ve doğrulamada 0,8135. Öznitelikler değişmez.
• DO38. Ağaç bu derste bir bağlanım ağacıdır: her örnek bir eğim ve bir eğrilik taşır, yaprağın değeri bu ikisinin oranıdır. Etiketi eğim, biri de eğrilik vermek aynı işlevi önceki dersin sınıflandırma ağacına çevirir.
• DO39. Turun eğimi etiket - olasilik, eğriliği olasilik * (1 - olasilik) olarak alınır ve eğrilik 1e-6 altına inmez; bu bir taşma korumasıdır, ayar değil.
• DO40. Karar eşiği toplamın sıfırı, yani olasılığın 0,5’idir; M27/K02’den sabittir.
• DO41. Zayıf öğrenicinin derinliği 1, 2 ya da 3’tür; öğrenme adımı 0,02 / 0,05 / 0,15 / 0,45; tur sayısı en çok 300’dür.
• DO42. Takas ölçümünün hedefi doğrulama kümesinde 208/252, yani 0,8254’tür ve ölçümden önce sabitlendi.
• DO43. Maliyet ölçüsü bölme sayısıdır: iç düğümlerin toplamı. Süre yazılmaz.
• DO44. Ayar bütçesi doğrulama kümesinde ölçülen her (adım, derinlik, tur) üçlüsünü sayar; seçim yalnız yetmiş iki hücrelik ızgaradan yapılır.

Kalan Hatanın Üstüne Kurmak

Kurulum tabloyu üretir, ağacı ve artırma döngüsünü yazar, sabit bir ayarla tur sayısını süpürür.

# artirma.py — MODELDIR. M27/K01'in KURGU abone tablosu ayni tohumla yeniden
# uretilir; oznitelik kumesi K02'den gelir ve kurs boyunca sabit tutulur.
import bisect
import math

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])
    VERI.append(x)


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:]
ALAN = ["ort_tuketim", "oynaklik", "hane", "memnuniyet", "donem", "sifir_okuma",
        "b_kuzey", "b_guney", "b_dogu", "b_bati", "b_merkez"]
ESIK = {}
for a in ALAN:
    d = sorted({x[a] for x in EGT})
    ESIK[a] = d[1:] if len(d) <= 24 else [d[int(i * len(d) / 25)] for i in range(1, 25)]
KOVA = [len(ESIK[a]) + 1 for a in ALAN]


def kutula(s):                              # her satir: kova numaralari ve etiket
    return [(tuple(bisect.bisect_right(ESIK[a], x[a]) for a in ALAN), x["supheli"])
            for x in s]


KE, KD, KS = kutula(EGT), kutula(DOG), kutula(SIN)
KUME, TUM = (KE, KD, KS), list(range(len(ALAN)))


def agac(orn, derinlik, alanlar, enaz=2):   # MODELDIR: her ornek (kova, egim, egrilik)
    n, en = len(orn), None
    G, H = sum(o[1] for o in orn), sum(o[2] for o in orn)
    if derinlik and n >= 2 * enaz:
        for k in alanlar:
            sg, sh, ss = [0.0] * KOVA[k], [0.0] * KOVA[k], [0] * KOVA[k]
            for b, g, h in orn:
                sg[b[k]] += g
                sh[b[k]] += h
                ss[b[k]] += 1
            cg = ch = cs = 0
            for j in range(KOVA[k] - 1):
                cg, ch, cs = cg + sg[j], ch + sh[j], cs + ss[j]
                if cs < enaz or n - cs < enaz:
                    continue
                kazanc = cg * cg / ch + (G - cg) ** 2 / (H - ch) - G * G / H
                if en is None or kazanc > en[0]:
                    en = (kazanc, k, j)
    if en is None or en[0] <= 1e-9:
        return G / H
    _, k, j = en
    return (k, j, agac([o for o in orn if o[0][k] <= j], derinlik - 1, alanlar, enaz),
            agac([o for o in orn if o[0][k] > j], derinlik - 1, alanlar, enaz))


def deger(d, b):
    while type(d) is tuple:
        d = d[2] if b[d[0]] <= d[1] else d[3]
    return d


def sikistir(z):
    return 1.0 / (1.0 + math.exp(-z)) if z > -30 else 0.0


def artir(adim, tur, derinlik, duraklar):   # MODELDIR: ardisik artirma
    p = sum(y for _, y in KE) / len(KE)
    F = [[math.log(p / (1 - p))] * len(k) for k in KUME]
    iz = {}
    for t in range(1, tur + 1):
        orn = []
        for i, (b, y) in enumerate(KE):
            q = sikistir(F[0][i])
            orn.append((b, y - q, max(q * (1 - q), 1e-6)))
        d = agac(orn, derinlik, TUM)
        for u, kume in enumerate(KUME):
            for i, (b, _) in enumerate(kume):
                F[u][i] += adim * deger(d, b)
        if t in duraklar:
            iz[t] = tuple(sum((F[u][i] > 0) == y for i, (_, y) in enumerate(kume)) / len(kume)
                          for u, kume in enumerate(KUME))
    return iz


def taban(kume):
    return sum(y == 0 for _, y in kume) / len(kume)


DURAK = (1, 5, 10, 25, 50, 100, 200)
IZ = artir(0.15, 200, 2, set(DURAK))
print(f"taban cizgisi           {'':>8} dogrulama {taban(KD):.4f}  sinama {taban(KS):.4f}")
print(f"{'tur':>5} {'egitim':>9} {'dogrulama':>10} {'sinama':>9}")
for t in DURAK:
    print(f"{t:>5} {IZ[t][0]:>9.4f} {IZ[t][1]:>10.4f} {IZ[t][2]:>9.4f}")

taban cizgisi                    dogrulama 0.8135  sinama 0.7579
  tur    egitim  dogrulama    sinama
    1    0.7778     0.8135    0.7579
    5    0.7804     0.8095    0.7579
   10    0.8082     0.8373    0.7738
   25    0.8280     0.8214    0.7937
   50    0.8439     0.8135    0.7897
  100    0.8532     0.8016    0.7778
  200    0.8638     0.8056    0.7817

Tablo bir ayrışmadır. Birinci turda eğitim sayısı 0,7778, doğrulama 0,8135; ayrılmış küme önde. Onuncu turda doğrulama 0,8373 ile tepe yapıyor. Yirmi beşinci turdan sonra yönler ayrılıyor: eğitim sayısı hiç durmadan 0,8638’e tırmanırken doğrulama 0,8056’ya iniyor. Aradaki fark birinci turda 0,0357 iken ikiyüzüncü turda işaret değiştirip 0,0582 oluyor.

Kaynağı görünür: her tur, yanlış tarafta kalmış abonelere daha büyük bir eğim yazar ve yeni zayıf öğrenici onlara göre kurulur; yüz tur sonra toplam tek tek abonelerini kovalar. Tur sayısı bir kapasite düğmesidir ve sınırı ayrılmış kümeden okunur: onuncu turdan sonrası eğitim için kâr, doğrulama için zarardır.

Öğrenme Adımı ile Tur Sayısının Takası

İkinci ayar öğrenme adımıdır. Aynı hedefe kaç turda varıldığı dört adım için ayrı ayrı sayılır; zayıf öğrenici bu bölümde tek bölmeli ağaçtır.

HEDEF, TUR = 208 / 252, 300
print(f"{'adim':>6} {'hedefe tur':>11} {'en iyi tur':>11} {'en iyi dog':>11} "
      f"{'o turda sin':>12} {'300. tur egt':>13}")
TAKAS = {}
for adim in (0.02, 0.05, 0.15, 0.45):
    iz = artir(adim, TUR, 1, set(range(1, TUR + 1)))
    ilk = next((t for t in range(1, TUR + 1) if iz[t][1] >= HEDEF), 0)
    en = max(range(1, TUR + 1), key=lambda t: iz[t][1])
    TAKAS[adim] = (ilk, en, iz[en][1], iz[en][2])
    print(f"{adim:>6.2f} {ilk:>11} {en:>11} {iz[en][1]:>11.4f} "
          f"{iz[en][2]:>12.4f} {iz[TUR][0]:>13.4f}")
print(f"hedef {HEDEF:.4f} (252 abonenin 208'i), zayif ogrenici tek bolmeli agac")

  adim  hedefe tur  en iyi tur  en iyi dog  o turda sin  300. tur egt
  0.02          79         204      0.8294       0.7897        0.8135
  0.05          30          84      0.8333       0.8016        0.8148
  0.15          10          36      0.8333       0.7976        0.8280
  0.45           4           8      0.8294       0.7976        0.8307
hedef 0.8254 (252 abonenin 208'i), zayif ogrenici tek bolmeli agac

İkinci sütun dersin ölçüsüdür. Doğrulama kümesinde 208 aboneye 0,02 adımla 79, 0,05 adımla 30, 0,15 adımla 10, 0,45 adımla 4 turda varılıyor. Adım ile tur sayısının çarpımı sırasıyla 1,58, 1,50, 1,50 ve 1,80: dördünde de yaklaşık aynı. İki ayar değişkeni tek düğmenin iki yüzüdür ve birlikte okunmalıdır; tek başına “iki yüz tur” bir ayar tarifi değildir.

Çarpım sabit olsa da sonuç değil. En iyi doğrulama sayısı ortadaki iki adımda 0,8333, uçlarda 0,8294; aynı adayların sınama sayıları 0,7897 ile 0,8016 arasında geziniyor. Üç yüzüncü turdaki eğitim sayısı 0,02 adımda 0,8135, 0,45 adımda 0,8307: büyük adım aynı yere daha hızlı gider ve daha çok ezberler.

Bütçe, Maliyet ve Torbalamayla Fark

Son bölüm iki ayarı ve tur sayısını tek ızgarada birleştirir, seçimi doğrulamadan okur, sonra artırmanın maliyetini önceki dersin torbalanmış topluluğuyla karşılaştırır.

def bolme_sayisi(d):
    return 0 if type(d) is not tuple else 1 + bolme_sayisi(d[2]) + bolme_sayisi(d[3])


def orman(tohum, sayi, m, derinlik):        # onceki dersin torbalanmis toplulugu
    r, agaclar = uretec(tohum), []
    for _ in range(sayi):
        secim = [int(r() * len(KE)) for _ in range(len(KE))]
        havuz, alanlar = list(TUM), []
        for _ in range(min(m, len(TUM))):
            alanlar.append(havuz.pop(int(r() * len(havuz))))
        agaclar.append(agac([(KE[i][0], KE[i][1], 1.0) for i in secim],
                            derinlik, sorted(alanlar)))
    return agaclar


ORMAN = orman(TOHUM, 41, 6, 4)
IZGARA, DURAK3 = {}, (5, 10, 25, 50, 100, 200)
print(f"{'adim':>6} {'derinlik':>9}" + "".join(f"{'tur ' + str(t):>14}" for t in DURAK3))
for adim in (0.02, 0.05, 0.15, 0.45):
    for derinlik in (1, 2, 3):
        iz = artir(adim, 200, derinlik, set(DURAK3))
        for t in DURAK3:
            IZGARA[(adim, derinlik, t)] = iz[t][1:]
        print(f"{adim:>6.2f} {derinlik:>9}"
              + "".join(f"{iz[t][1]:>7.4f}/{iz[t][2]:.4f}" for t in DURAK3))
SIRA = [(a, d, t) for a in (0.02, 0.05, 0.15, 0.45) for d in (1, 2, 3) for t in DURAK3]
for ad, sutun in (("dogrulamadan", 0), ("sinamadan", 1)):
    e = max(IZGARA[k][sutun] for k in SIRA)
    a, d, t = next(k for k in SIRA if IZGARA[k][sutun] == e)
    print(f"secim {ad:<13} adim={a:<5} derinlik={d}  tur={t:<4} "
          f"dogrulama {IZGARA[(a, d, t)][0]:.4f}  sinama {IZGARA[(a, d, t)][1]:.4f}")
e = max(IZGARA[k][0] for k in SIRA)
a, d, t = next(k for k in SIRA if IZGARA[k][0] == e)
print(f"artirma  {t} tur x derinlik {d} = {t * (2 ** d - 1)} bolme, "
      f"sinama {IZGARA[(a, d, t)][1]:.4f}")
print(f"torbalama 41 agac x derinlik 4 = {sum(map(bolme_sayisi, ORMAN))} bolme, "
      f"sinama {sum((sum(deger(x, b) > 0.5 for x in ORMAN) * 2 > 41) == y for b, y in KS) / len(KS):.4f}")
print(f"denenen aday {7 + 4 * TUR + len(SIRA)}, ailenin sayisi {IZGARA[(a, d, t)][1]:.4f}, "
      f"taban cizgisi ustu {IZGARA[(a, d, t)][1] - taban(KS):+.4f}")

  adim  derinlik         tur 5        tur 10        tur 25        tur 50       tur 100       tur 200
  0.02         1 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8254/0.7817 0.8254/0.7857
  0.02         2 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8135/0.7659 0.8294/0.7817 0.8214/0.7937
  0.02         3 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8214/0.7857 0.8135/0.7778 0.8254/0.7817
  0.05         1 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8175/0.7857 0.8294/0.7976 0.8294/0.7937
  0.05         2 0.8135/0.7579 0.8135/0.7579 0.8294/0.7738 0.8175/0.7897 0.8294/0.7937 0.8175/0.7857
  0.05         3 0.8135/0.7579 0.8135/0.7579 0.8175/0.7817 0.8254/0.7778 0.8254/0.7817 0.8095/0.7857
  0.15         1 0.8135/0.7579 0.8254/0.7817 0.8254/0.7897 0.8333/0.7937 0.8175/0.8016 0.8135/0.8056
  0.15         2 0.8095/0.7579 0.8373/0.7738 0.8214/0.7937 0.8135/0.7897 0.8016/0.7778 0.8056/0.7817
  0.15         3 0.8254/0.7817 0.8056/0.7817 0.8095/0.7817 0.8056/0.7778 0.8016/0.7778 0.8016/0.7817
  0.45         1 0.8254/0.7857 0.8294/0.7897 0.8135/0.7897 0.8175/0.7937 0.8175/0.8016 0.8214/0.7897
  0.45         2 0.8135/0.7857 0.8214/0.7778 0.8254/0.7778 0.7976/0.7698 0.7857/0.7659 0.7976/0.7659
  0.45         3 0.8175/0.7778 0.7937/0.7738 0.7817/0.7540 0.7897/0.7659 0.7698/0.7619 0.7778/0.7738
secim dogrulamadan  adim=0.15  derinlik=2  tur=10   dogrulama 0.8373  sinama 0.7738
secim sinamadan     adim=0.15  derinlik=1  tur=200  dogrulama 0.8135  sinama 0.8056
artirma  10 tur x derinlik 2 = 30 bolme, sinama 0.7738
torbalama 41 agac x derinlik 4 = 568 bolme, sinama 0.7897
denenen aday 1279, ailenin sayisi 0.7738, taban cizgisi ustu +0.0159

Izgaranın verdiği en yüksek doğrulama sayısı 0,8373 ve tek bir hücrede: adım 0,15, derinlik 2, tur 10. O adayın sınama sayısı 0,7738. Sınama kümesinden okunsaydı adım 0,15, derinlik 1, tur 200 seçilirdi ve sayı 0,8056 olurdu. Fark 0,0318, yani sekiz abone. Önceki derste aynı fark 0,0040, tek aboneydi.

Nedeni ızgaranın kendisidir. Bu derste doğrulama kümesinde ölçülen üçlü sayısı 1.279, önceki derste 31’di. 252 satırlık bir kümede bu kadar aday denendiğinde en yüksek hücre, en iyi ayarın değil en şanslı ayarın hücresidir. Kursun kuralı burada tam karşılığını buluyor: bir modelin sayısı, o sayıyı bulmak için kaç aday denendiği yazılmadan okunamaz.

Son iki satır aileler arasındaki farkı sayıyla veriyor. Doğrulamadan seçilen artırma 30 bölme kurup 0,7738 veriyor; önceki dersin torbalanmış topluluğu 568 bölme kurup 0,7897 veriyor. Artırma on dokuz kat ucuz ve dört abone geride. Aile değiştirmenin kattığı fark −0,0159; aynı ızgara içinde bütçenin şişirdiği fark +0,0318. Bütçenin farkı, ailenin farkının iki katı.

Ailenin sayısı 0,7738’dir, taban çizgisinin 0,0159 üstünde. Tek ağacın 0,7778’inin de altındadır ve düzeltilmez: ızgaranın en iyi doğrulama hücresi budur.

Özet

• İki yüz turda eğitim sayısı 0,7778’den 0,8638’e çıkarken doğrulama 0,8373’te tepe yapıp 0,8056’ya iniyor; iki sayı arasındaki fark işaret değiştirip 0,0582 oluyor.
• Aynı doğrulama hedefine 0,02 adımla 79, 0,05 adımla 30, 0,15 adımla 10, 0,45 adımla 4 turda varılıyor; adım ile tur sayısının çarpımı 1,50 ile 1,80 arasında kalıyor.
• Çarpım sabit olsa da sonuç değildir: uç adımların en iyi doğrulama sayısı 0,8294, ortadakilerin 0,8333; büyük adım üç yüz turda eğitimi 0,8307’ye kadar ezberliyor.
• Doğrulamadan okunan seçim sınama kümesinde 0,7738, sınamadan okunan 0,8056 veriyor; fark 0,0318 ve 1.279 aday denenmiştir. Önceki derste 31 adayla aynı fark 0,0040’tı.
• Artırma 30 bölmeyle 0,7738, torbalama 568 bölmeyle 0,7897 veriyor: aile farkı −0,0159, bütçe farkı +0,0318.

Sonraki Adım

İki birleştirme denendi ve ikisi de aynı aileden, karar ağacından besleniyordu: torbalama bağımsız ağaçları oylattı, artırma onları üst üste yığdı. Üçüncü bir biçim daha var: farklı ailelerden gelen modellerin çıktılarını girdi kabul eden ikinci bir katman. Bu hemen bir soru doğurur, ikinci katman hangi kümeden öğrenilecek. Birinci katmanın eğitim kümesindeki çıktılarından öğrenilirse katman ezberlenmiş çıktıları görür ve sayı şişer. Sonraki ders üç birleştirmeyi yan yana koyar, şişmeyi sayar ve toplulukların birlikte yanıldığı abone sayısını basar.