Yeniden Sıralama

Önceki ders sorguyu dizine göndermeden önce düzeltti ve ilk beş parçanın birlikte ne kadar iyi olduğunu saydı. Geriye o beşin içindeki dağılım kaldı: getirilen kümenin başı neden dolu değil ve başını düzeltmek neye mal olur.

Cevabın yarısı puanın kendisindedir. Birinci aşama sorguyu parçayı görmeden bir vektöre sıkıştırır; bu vektör “şu kavramı ara” diyebilir, ama “şu kavramı ve şu kayıt türünü birlikte ara” diyemez, çünkü tek bir benzerlik sayısı iki koşulun kesişimini taşımaz. İkinci aşama sorgu ile parçayı birlikte okur ve iki koşulu ayrı ayrı arayabilir. Bedeli açıktır: her aday için bir çağrı.

• EH47. Kod bir benzeticidir; gerçek bir gömme, sıralayıcı ya da model uç noktası çağrılmaz. Dağarcık, kavramlar ve sorgular kurgudur, tohum 20260218.
• EH48. Hedefin tanımı erisim-hatti/05’ten sürer: sorgunun hedefi hem bir kavram hem bir kayıt türüdür, parça ancak ikisini birden taşıyorsa ilgilidir. Hat da aynıdır.
• EH49. Bu ders dönüştürme adımını kapatır ve sorgu kümesini tanımlandığı biçimiyle alır; ölçülen tek düzenek yeniden sıralamadır. Dönüştürmenin bedeli 05’te ölçüldü.
• EH50. Yeniden sıralayıcı aday başına bir model çağrısıdır ve sorgu ile parçayı tek istemde görür. Puanı iki koşulun toplamıdır: kavram ortaklığı ve kayıt türü ortaklığı.
• EH51. Sıralayıcı da bir modeldir, puanı gürültülüdür. Gürültünün genliği bir koşulun ağırlığını aşar, yani tek koşulluk bir farkı her zaman göremez.
• EH52. Bağlama giren parça sayısı üçte sabittir; k’nın kendisi ve bağlam sınırı erisim-hatti/07’nin konusudur.
• EH53. Gecikme sınıf olarak yazılır. Adaylar birbirinden bağımsız puanlandığı için paralel çağrılabilir, ama aşamaların sırası zorunludur: birinci bitmeden ikincisi başlayamaz.

Tek Aşamanın Sınırı

Aşağıdaki blok hattı kurar ve tek aşamalı getirmede k büyüdükçe anma ile kesinliğin ne yaptığını basar. İki sütun zıt yönlere gider; aradaki gerilim bu dersin sebebidir.

# BENZETICI -- KURGUDUR. Gercek bir gomme ya da model uc noktasi cagrilmaz; dagarcik,
# kavramlar ve sorgular kurgudur, tohum 20260218.
import math
TOHUM, M32 = 20260218, 0xFFFFFFFF
BOYUT = 32


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


def belirtecle(m):
    b = []
    for s in m.lower().replace(",", " , ").split():
        while len(s) > 5:
            b.append(s[:5])
            s = s[5:]
        b.append(s)
    return b


# ---- KURGU anlam ekseni: her kavramin belge dilinde ve sorgu dilinde ayri yuzeyi var
SINIF = ["tarife", "ariza", "sayac", "kesinti", "bakim"]
KOD = {"tarife": "TR", "ariza": "AR", "sayac": "SY", "kesinti": "KS", "bakim": "BK"}
KAVRAM = {                       # kavram: (sinif, belge yuzeyi, sorgu yuzeyi)
    "basamak":   ("tarife", "kademe esigi", "hangi dilimdeyim"),
    "birim":     ("tarife", "birim ucret", "metrekup fiyati"),
    "abonetip":  ("tarife", "abone tipi", "mesken mi isyeri mi"),
    "gecis":     ("tarife", "tarife gecisi", "plan degistirme"),
    "arizakod":  ("ariza", "ariza kodu", "hata numarasi"),
    "sizinti":   ("ariza", "hat sizintisi", "su kacagi"),
    "basinc":    ("ariza", "basinc dususu", "zayif akis"),
    "ekip":      ("ariza", "saha ekibi", "gorevli ne zaman gelir"),
    "endeks":    ("sayac", "endeks degeri", "sayac ustundeki rakam"),
    "okuma":     ("sayac", "okuma yordami", "nasil kaydediliyor"),
    "degisim":   ("sayac", "sayac degisimi", "cihaz yenileme"),
    "dogrula":   ("sayac", "okuma dogrulamasi", "yanlis girilmis mi"),
    "planli":    ("kesinti", "planli kesinti", "onceden duyurulan durma"),
    "duyuru":    ("kesinti", "duyuru kanali", "nereden ogrenirim"),
    "sure":      ("kesinti", "kesinti suresi", "ne kadar surer"),
    "geridonus": ("kesinti", "yeniden verme", "ne zaman gelir"),
    "periyot":   ("bakim", "periyodik bakim", "duzenli kontrol"),
    "vana":      ("bakim", "vana kontrolu", "musluk kapatma duzeni"),
    "filtre":    ("bakim", "filtre degisimi", "temizleme parcasi"),
    "kalib":     ("bakim", "kalibrasyon kaydi", "olcum ayari"),
}
ANAHTAR = list(KAVRAM)
ORTAK = ["kayit", "bolge", "donem", "islem", "form", "onay", "not"]

# ---- KURGU dagarcik
BELGE = []
for i in range(200):
    r = uretec(TOHUM + 7919 * i)
    s = SINIF[ayrik(r(), [0.22, 0.24, 0.20, 0.18, 0.16])]
    kav = [k for k in ANAHTAR if KAVRAM[k][0] == s]
    ana = kav[int(r() * len(kav))]
    n = 2 + int(r() * 4)
    par, kavlar = [], [ana]
    for _ in range(n):
        y = kav[int(r() * len(kav))]
        kavlar.append(y)
        o = ORTAK[int(r() * len(ORTAK))]
        par.append(f"{KAVRAM[y][1]} icin {o} tutulur ve {KAVRAM[ana][1]} ile birlikte yazilir")
    BELGE.append({"kod": f"{KOD[s]}{i + 1:03d}", "sinif": s, "ana": ana, "kavram": kavlar,
                  "baslik": f"{KAVRAM[ana][1]} yordami", "par": par})


def metin(d):
    return d["baslik"] + " " + " ".join(d["par"])


# ---- KURGU gomme: yuzey once kavrama, kavram sonra boyuta dusuruluyor
def _kavramla(m, alan=True):
    v = [0.0] * len(ANAHTAR)
    dm = " " + m.lower() + " "
    for i, k in enumerate(ANAHTAR):
        bel, sor = KAVRAM[k][1], KAVRAM[k][2]
        if bel in dm:
            v[i] += 1.0
        if sor in dm:
            v[i] += 1.0 if alan else 0.0      # alan disi gomme sorgu dilini tanimaz
    if not alan:
        for o in ORTAK:
            if " " + o + " " in dm:
                for i in range(len(ANAHTAR)):
                    v[i] += 0.05
    return v


IZDUS = []
for i in range(len(ANAHTAR)):
    r = uretec(TOHUM ^ (i + 1) * 2654435761)
    IZDUS.append([r() * 2 - 1 for _ in range(64)])


def gom(m, boyut=BOYUT, alan=True):
    k = _kavramla(m, alan)
    v = [0.0] * boyut
    for i, a in enumerate(k):
        if a:
            for j in range(boyut):
                v[j] += a * IZDUS[i][j % 64]
    n = sum(x * x for x in v) ** 0.5
    return [x / n for x in v] if n else v


def aci(a, b):
    return sum(x * y for x, y in zip(a, b))


# ---- KURGU sorgu kumesi: sorgu dili belge dilinden ayri
SORGU = []
for i in range(40):
    r = uretec(TOHUM + 104729 * i)
    d = BELGE[int(r() * len(BELGE))]
    SORGU.append({"metin": f"{KAVRAM[d['ana']][2]} {ORTAK[int(r() * len(ORTAK))]}",
                  "sinif": d["sinif"], "kavram": d["ana"]})

# ---- hat: parcalar, karma getirme, hedef tanimi ve uretim
PARCA = [{"kod": d["kod"], "ana": d["ana"], "metin": p} for d in BELGE for p in d["par"]]
for p in PARCA:
    p["vek"], p["bel"] = gom(p["metin"]), set(belirtecle(p["metin"]))
for s in SORGU:
    s["kayit"] = s["metin"].split()[-1]


def getir(q, k=5, w=0.5):
    qv, qb = gom(q), set(belirtecle(q))
    s = sorted(((aci(qv, p["vek"]) + w * len(qb & p["bel"]) / len(qb | p["bel"]), i)
                for i, p in enumerate(PARCA)), key=lambda t: (-t[0], t[1]))
    return [PARCA[i] for _, i in s[:k]]


def ilgili(s, p):
    return KAVRAM[s["kavram"]][1] in p["metin"] and s["kayit"] in p["bel"]


def izno(m):
    h = 2166136261
    for c in m:
        h = ((h ^ ord(c)) * 16777619) & M32
    return h


PENCERE = 240
SAYAC = [0]
YON_Y = "Asagidaki parcalara bakarak yanitla ve kullandigin parcanin kodunu yaz . "


def yanitla(sorgu, parcalar, tohum=TOHUM, sicaklik=0.12):
    """KURGU uretim: baglamdan bir parca secilir, parcanin YERI agirligi degistirir."""
    SAYAC[0] += 1
    istem = YON_Y + " ".join(f"[{p['kod']}] {p['metin']} ." for p in parcalar) + " Soru: " + sorgu
    bel = belirtecle(istem)
    if len(bel) > PENCERE:
        return {"durum": "baglam_asimi", "giris": len(bel), "cikis": 0, "parca": None}
    r, qb, n = uretec(tohum ^ izno(istem)), set(belirtecle(sorgu)), len(parcalar)
    p = [(1.0 if i == 0 else 0.8 if i == n - 1 else 0.45) * (0.3 + len(qb & x["bel"]) / len(qb))
         for i, x in enumerate(parcalar)]
    w = [math.exp(a / sicaklik) for a in p]
    se = parcalar[ayrik(r(), [a / sum(w) for a in w])]
    return {"durum": "tamam", "giris": len(bel), "parca": se,
            "cikis": len(belirtecle(f"{se['kod']} : {se['metin']}"))}


print("dagarcik %d belge %d parca ; hedef parca kumesi ortalama %.1f parca"
      % (len(BELGE), len(PARCA),
         sum(len([p for p in PARCA if ilgili(s, p)]) for s in SORGU) / 40))
print("tek asamali getirme:  k  anma@k  kesinlik@k")
for k in (1, 3, 5, 10, 20, 40):
    a = sum(any(ilgili(s, p) for p in getir(s["metin"], k)) for s in SORGU) / 40
    e = sum(sum(ilgili(s, p) for p in getir(s["metin"], k)) / k for s in SORGU) / 40
    print("                     %2d  %.4f  %.4f" % (k, a, e))

dagarcik 200 belge 693 parca ; hedef parca kumesi ortalama 8.9 parca
tek asamali getirme:  k  anma@k  kesinlik@k
                      1  0.7750  0.7750
                      3  0.7750  0.4167
                      5  0.8000  0.2700
                     10  0.9750  0.2400
                     20  1.0000  0.2250
                     40  1.0000  0.1775

Anma kırk sorgunun tamamını yakalamak için yirmi parça istiyor. Kesinlik ise tam tersini söylüyor: k yirmi olduğunda ilk yirminin yalnızca 0,2250’si ilgilidir, yani her doğru parçanın yanında üç buçuk yanlış parça bağlama girer. k üçte kesinlik 0,4167, ama anma 0,7750’de kalır ve sorguların dörtte biri hiç doğru parça görmez.

Bu iki sütunu aynı anda iyileştirmenin tek aşamalı bir hatta yolu yoktur, çünkü sıra tek bir puandan çıkar. Yeniden sıralama şunu önerir: anmayı geniş bir aday kümesinden al, kesinliği ikinci bir puanlayıcıdan.

İkinci Aşama

Aşağıdaki blok sıralayıcıyı tanımlar ve aday sayısını üçten kırk sekize çıkararak aynı kırk sorguyu beş kez koşturur. Bağlama giren parça sayısı hep üçtür; değişen tek şey, o üçün kaç aday arasından seçildiğidir.

YON_S = "Sorgu ile parca ayni kaydi anlatiyor mu . Parca: "
IZ = {}                              # iki dilin belirtecleri de ayni kavrama baglanir
for k in ANAHTAR:
    for m in (KAVRAM[k][1], KAVRAM[k][2]):
        for t in belirtecle(m):
            if len(t) > 3:
                IZ.setdefault(t, k)


def sirala(q, p, tohum=TOHUM, gurultu=1.4):
    """KURGU ikinci asama: sorgu ile parcayi BIRLIKTE gorur, iki kosulu ayri ayri arar."""
    SAYAC[0] += 1
    bel = belirtecle(YON_S + p["metin"] + " Sorgu: " + q)
    r, qb = uretec(tohum ^ izno(q + p["metin"])), set(belirtecle(q))
    kavram = bool({IZ[t] for t in qb if t in IZ} & {IZ[t] for t in p["bel"] if t in IZ})
    kayit = bool(qb & p["bel"] & set(ORTAK))
    return 1.0 * kavram + 1.0 * kayit + gurultu * (r() - 0.5), len(bel) + 1


def olc(N, tohum=TOHUM, k=3):
    SAYAC[0] = 0
    an = ke = ur = ca = bt = 0
    for s in SORGU:
        aday = getir(s["metin"], max(N, k))
        if N > k:
            pu = []
            for p in aday:
                v, b = sirala(s["metin"], p, tohum)
                pu.append(v)
                ca, bt = ca + 1, bt + b
            aday = [p for _, p in sorted(zip(pu, aday), key=lambda t: -t[0])]
        ilk = aday[:k]
        an += any(ilgili(s, p) for p in ilk)
        ke += sum(ilgili(s, p) for p in ilk) / k
        y = yanitla(s["metin"], ilk, tohum)
        ca, bt = ca + 1, bt + y["giris"] + y["cikis"]
        ur += ilgili(s, y["parca"])
    return an / 40, ke / 40, ur / 40, ca, bt


print("aday  anma@3  kesinlik@3  uretim  cagri  belirtec  gecikme sinifi")
onceki, fark = None, [0.0, 0.0, 0.0]
for N in (3, 6, 12, 24, 48):
    a, e, u, c, b = olc(N)
    i = olc(N, TOHUM + 1)
    fark = [max(f, abs(x - y)) for f, x, y in zip(fark, (a, e, u), i[:3])]
    print("%4d  %.4f  %.4f      %.4f  %5d  %8d  %s"
          % (N, a, e, u, c, b, "tek asama" if N == 3 else "iki asama, %d ek cagri" % N))
print("iki kosum farki (tohum 20260219): anma %.4f  kesinlik %.4f  uretim %.4f" % tuple(fark))

aday  anma@3  kesinlik@3  uretim  cagri  belirtec  gecikme sinifi
   3  0.7750  0.4167      0.7500     40      4003  tek asama
   6  0.8000  0.4917      0.7250    280     12424  iki asama, 6 ek cagri
  12  0.9750  0.8000      0.9500    520     20851  iki asama, 12 ek cagri
  24  1.0000  0.9000      1.0000   1000     37689  iki asama, 24 ek cagri
  48  0.9500  0.9083      0.9500   1960     71374  iki asama, 48 ek cagri
iki kosum farki (tohum 20260219): anma 0.0250  kesinlik 0.0333  uretim 0.0500

Aday Sayısı Büyüdükçe

İlk satır tabandır: yeniden sıralama yok, ilk üç doğrudan bağlama giriyor, kesinlik 0,4167, üretim 0,7500, kırk çağrı.

Altı adayda kesinlik 0,4917‘ye çıkıyor. Kazanç 0,0750 ve iki koşum farkının (0,0333) üstünde, yani gerçek; ama karşılığında çağrı kırktan iki yüz seksene, belirteç 4003’ten 12424’e gidiyor. Üretim bu satırda 0,7250’ye düşüyor, düşüş 0,0250 ve üretimin iki koşum farkı 0,0500 olduğu için bu satır “üretimi düşürdü” diye okunamaz; bu ölçümle bilinemez diye okunur.

On iki adayda tablo değişiyor: kesinlik 0,8000, anma 0,9750, üretim 0,9500. Tabana göre kesinlikte 0,3833, üretimde 0,2000 kazanç var ve ikisi de eşiğin çok üstünde. Yirmi dört adayda anma 1,0000, kesinlik 0,9000, üretim 1,0000 oluyor; bu kurulum kırk sorgunun hepsinde doğru parçayı bağlamın içine ve yanıtın kaynağına koyuyor.

Bedel tarafında aynı satır bin çağrı ve 37689 belirteç yazıyor. Taban kırk çağrıydı; yirmi beş kat. Gecikme sınıfı da değişti: hat tek aşamadan iki aşamaya geçti ve ikinci aşama aday sayısıyla ölçekleniyor. Adaylar paralel puanlanabilir, ama birinci aşama bitmeden hiçbiri başlayamaz, yani zincirin uzunluğu iki adımda sabit kalırken genişliği yirmi dörde çıkıyor.

Ölçülemeyen Kazanç ve Ölçülen Kayıp

Son satır bu dersin asıl bulgusudur. Aday sayısı yirmi dörtten kırk sekize çıkarıldığında kesinlik 0,9000’den 0,9083‘e gidiyor. Kazanç 0,0083, iki koşum farkının dörtte biri. Bu satır “kesinliği artırdı” diye yazılamaz; artırıp artırmadığı bu ölçümle bilinemez. Karşılığında ödenen ise ölçülmüştür: çağrı 1000’den 1960‘a, belirteç 37689’dan 71374’e çıkıyor.

Aynı satırda ölçülebilen bir şey daha var ve yönü terstir. İlk üçün anması 1,0000’den 0,9500‘e düşüyor; düşüş 0,0500 ve anmanın iki koşum farkı 0,0250, yani gerçek. Üretim de 1,0000’den 0,9500’e iniyor. Aday kümesi büyüdükçe gürültülü sıralayıcının önüne daha çok yanlış parça geliyor ve bunlardan birini ilk üçe taşıma olasılığı artıyor. Sıralayıcının gürültüsü bir koşulluk farkı örtebildiği için, kalabalıkta bir yanlış adayın doğru adayı geçmesi kaçınılmaz hâle geliyor.

Kursun ikinci iddiasının bu derse düşen örneği budur: erişim düzeneğini büyütmek işi kötüleştirdi. Doğru okuma, en yüksek kesinlik satırını seçmek değil, kazancın eşiğin altına düştüğü yeri bulup orada durmaktır. Bu iş yükünde o yer yirmi dört adaydır.

Özet

• Tek bir benzerlik puanı sorguyu parçayı görmeden sıkıştırdığı için kavram ile kayıt türünü birlikte arayamaz; anma yirmi parça isterken kesinlik ilk üçte 0,4167’de kalır.
• Adayları sorguyla birlikte okuyan ikinci aşama on iki adayda kesinliği 0,8000’e, yirmi dört adayda 0,9000’e, üretimi 0,7500’den 1,0000’e çıkarır.
• Bedel aday başına bir çağrıdır: kırk çağrı ve 4003 belirteç, yirmi dört adayda 1000 çağrı ve 37689 belirtece çıkar; gecikme sınıfı tek aşamadan iki aşamaya geçer.
• Kırk sekiz adayda kesinlik yalnızca 0,0083 artar ve 0,0333’lük iki koşum farkının altında kalır; bu satır kazandırdı diye okunamaz.
• Aynı satırda ilk üçün anması 1,0000’den 0,9500’e düşer ve bu düşüş 0,0250’lik eşiğin üstündedir: aday kümesini büyütmek gürültülü sıralayıcıya daha çok yanlış aday sunar.

Sonraki Adım

Bu dersin bütün kurulumlarında bağlama üç parça girdi ve hep aynı sırada, yani sıralayıcının verdiği sırada girdi. İki sayı bu seçimin sorgulanmadığını gösteriyor: üç parça bağlamın sınırının neresinde duruyor ve o üç parçanın sırası yanıtı değiştiriyor mu. Sonraki ders bağlam sınırına kaç parçanın sığdığını sayar, sınır aşıldığında hattın ne yaptığını gösterir ve aynı parçaları farklı sıralarda vererek yanıtın değişme payını ölçer.