22.3 Távolság, kernel és méretkorlát

A szintetikus tanulópéldánk ma kétdimenziós: minden sor egy megfigyelés, két numerikus jellemzője van, és a cél egy 0/1 osztálycímke. Azért választottam hold alakú, nemlineáris határú adatot, mert ezen jól látszik, mit tud a távolságalapú kNN és a kernel-SVM a lineáris baseline-hoz képest. A bemenet X alakja $(300, 2)$, a cél y alakja $(300,)$; a megfigyelési egység egy szintetikus pont, pénznem vagy fizikai mértékegység nincs. A feladat annak ellenőrzése, hogy a kNN és az RBF-kernelű SVM jobb-e a logisztikus baseline-nál, és mennyibe kerülne mindezt nagyobb adatra vinni. Előzetes becslés: a dummy AUC 0.5; a lineáris modell a hold alakú határon nagyjából 0.75–0.85 AUC-t érhet el; a kNN és az SVM 0.85–0.95 tartományba kerülhet. Ez nem mért eredmény, hanem a modellcsaládok geometriájából következő várakozás.

22.3.1 Távolság, norma és a kNN döntése

A kNN (k-nearest neighbours, k legközelebbi szomszéd) „lustatanuló”: a .fit() lépésben csak tárolja a tanítóadatot, a döntést pedig a kérdezés pillanatában hozza meg. Egy új $\mathbf x$ pont osztályát úgy becsüli, hogy megkeresi a tanítóhalmaz $k$ legközelebbi pontját, és a szomszédok címkéit többségi szavazással összegzi.

A szomszédság fogalma távolságon (distance) múlik. A tanult euklideszi norma visszahívható Vetítés és legkisebb négyzetek alfejezetből: a pontok közötti eltérésvektor normája

$$\|\mathbf u - \mathbf v\|_2 = \sqrt{\sum_{j=1}^{p}(u_j - v_j)^2},$$

ahol $\mathbf u, \mathbf v \in \mathbb{R}^p$ két sorvektor, $p$ a jellemzők száma, az eredmény pedig nemnegatív, dimenziómentes szám, ha a jellemzők már standardizáltak. A kifejezés belseje a $\langle\mathbf u-\mathbf v, \mathbf u-\mathbf v\rangle$ skalárszorzat. Kézi kontroll: $\mathbf u=(0,0)$, $\mathbf v=(3,4)$ esetén a távolság $\sqrt{9+16}=5$. Ha a második jellemző milliméterben, az első méterben lenne, ugyanaz a geometriai helyzet egészen más számot adna; ezt orvosolja a skálázás (scaling).

A tanítóadaton illesztett standardizálás

$$z_j = \frac{x_j - \mu_j}{\sigma_j}$$

minden $j$ oszlopra kivonja az oszlopátlagot $\mu_j$, és elosztja az oszlop szórásával $\sigma_j>0$. Így minden jellemző átlaga 0, szórása 1 lesz, és egyik sem uralja a távolságot pusztán azért, mert nagyobb a számértéke. A skálázót a Baseline és egyetlen teljes kísérlet pipeline-szabálya szerint csak a tanítórészen illesztjük, majd ugyanazt az eltolást és osztót alkalmazzuk a tesztrészre.

22.3.2 Az SVM és a kernel ötlete

Az SVM (support vector machine, tartóvektor-gép) lineárisan szeparálható esetben egy olyan $\langle\mathbf w,\mathbf x\rangle + b = 0$ határegyenest keres, amely a két osztályt maximális margóval választja el. A $\mathbf w \in \mathbb{R}^p$ súlyvektor, $b \in \mathbb{R}$ az eltolás, a döntés pedig a $\langle\mathbf w,\mathbf x\rangle + b$ előjele. A margó nagysága $1/\|\mathbf w\|$; maximalizálása ezért a $\|\mathbf w\|$ minimalizálását jelenti, miközben a pontok helyes oldalon maradnak. A lágy margójú változat $C$ büntetőparaméterrel enged meg hibás pontokat: kis $C$ széles, de tévedő margót ad, nagy $C$ a tanítópontokat jobban követi.

A lineáris határ azonban a hold alakú adaton kevés. A kernel (magfüggvény) ötlete, hogy az eredeti $\mathbf x$ pontot egy másik, gyakran nagyon gazdag jellemzőtérbe képzi: $\mathbf x \mapsto \phi(\mathbf x)$. A döntési függvény ott lineáris, az eredetiben viszont hajlított határ lehet. A kernel trükk lényege, hogy a modellnek csak a $\langle\phi(\mathbf x_i), \phi(\mathbf x_j)\rangle$ skalárszorzatra van szüksége, ezért ezt közvetlenül kiszámolhatjuk $\phi$ tényleges tárolása nélkül:

$$K(\mathbf x_i, \mathbf x_j) = \exp\left(-\gamma \|\mathbf x_i - \mathbf x_j\|^2\right).$$

Ez az RBF-kernel (radial basis function). A $\gamma>0$ paraméter azt szabályozza, milyen gyorsan cseng le a hasonlóság a távolság növekedésével: nagy $\gamma$ nagyon lokális határokat ad, kis $\gamma$ simábbat. A scikit-learn gamma='scale' beállítása a $\gamma = 1/(p \cdot \mathrm{Var}(X))$ értéket használja, tehát az adat szórásához igazítja. A tanítás utáni döntési függvény

$$s(\mathbf x) = b + \sum_{i=1}^{n} \alpha_i y_i K(\mathbf x_i, \mathbf x),$$

ahol $n$ a tanítósorok száma, $y_i \in \{-1,1\}$ a tanítócímke, $\alpha_i \geq 0$ pedig Lagrange-szorzó. A legtöbb $\alpha_i$ nulla; csak a tartóvektorok (support vectors) maradnak a modellben.

22.3.3 Teljes minimális munkapélda

A következő kód futtatásra kész, de a könyvíró környezet itt nem futtatta; minden numerikus kimenet ezért szemléltető, és a saját futásod a mérvadó. A szkriptet a fejezet munkakönyvtárában s087_example.py néven helyezd el.

import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.dummy import DummyClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score, roc_auc_score

X, y = make_moons(n_samples=300, noise=0.2, random_state=17)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=101, stratify=y
)

models = {
    "dummy": DummyClassifier(strategy="most_frequent"),
    "linear": make_pipeline(StandardScaler(), LogisticRegression(max_iter=1000)),
    "knn5": make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)),
    "svm_rbf": make_pipeline(
        StandardScaler(), SVC(kernel="rbf", gamma="scale", C=1.0)
    ),
}

for name, model in models.items():
    model.fit(X_train, y_train)
    acc = accuracy_score(y_test, model.predict(X_test))
    if name == "dummy":
        print(f"{name}: test_accuracy={acc:.3f}")
    else:
        auc = roc_auc_score(y_test, model.decision_function(X_test))
        print(f"{name}: test_accuracy={acc:.3f}, test_auc={auc:.3f}")

Futtatás Linux/macOS terminálból, a munkakönyvtárból:

python s087_example.py

Vagy Windows PowerShellből:

python s087_example.py

A szemléltető kimenet formája:

dummy: test_accuracy=0.500
linear: test_accuracy=0.720, test_auc=0.810
knn5: test_accuracy=0.840, test_auc=0.910
svm_rbf: test_accuracy=0.880, test_auc=0.920

A számok nem a generálás pillanatában mért értékek, csak a várt nagyságrendet mutatják.

22.3.4 Eredményértelmezés

A dummy baseline a többségi osztályt adja, így a holdouton körülbelül 0.5 pontosságú, és AUC-ja definíció szerint 0.5. A logisztikus modell csak egy egyenest tud húzni, ezért a két hold alakú osztályt nem választja el jól; az RBF-SVM és a kNN hajlított határral jobban illeszkedik. A pontos különbség a 75 tesztponton nagy szórással bír, ezért önmagában egyetlen holdout szám nem elég „a legjobb modell” kijelentéshez; a Modellcsalád választása tudományos jegyzőkönyvvel majd ezt jegyzőkönyvvel rendezi.

22.3.5 A páronkénti távolságmátrix RAM-igénye

A kNN döntése első ránézésre olcsó, mert tanításkor „nem csinál semmit”. A költség a predikcióban jelentkezik: minden új sorhoz a tanítóadatok minden sorával távolságot kell számolni. Ha $n_{\text{train}}$ tanítósorunk, $m$ kérdezősorunk és $p$ jellemzőnk van, akkor a távolságszámítások száma $m \cdot n_{\text{train}}$, mindegyik $p$ koordinátapárral. Az időigény $O(m n_{\text{train}} p)$.

Ennél súlyosabb a memóriaigény, ha valaki explicit páronkénti távolságmátrixot épít. Egy $n \times n$ float64 mátrix bájtmérete

$$\text{bytes}(n) = 8 n^2.$$

Például $n=50\,000$ tanítósornál a teljes mátrix $8 \cdot 50\,000^2 = 20\cdot 10^9$ bájt, ami $18.6\ \mathrm{GiB}$. A tömörített, átló nélküli felső háromszög feleannyi: $\frac{n(n-1)}{2}\cdot 8$ bájt, itt $9.3\ \mathrm{GiB}$. A KNeighborsClassifier éppen ezért nem tartja a teljes mátrixot; csak a $k$ legközelebbi szomszédot keresi. Ez a négyzetes növekedés a mai alfejezet matematikai hídja: a mátrix celláinak száma $n^2$-tel nő, ezért a kis mintán látott sikerből nem következik a nagy adatra való alkalmazhatóság.

Az SVM kernelmódban hasonló korlátot mutat. Az RBF-kernel kiértékelése minden pontpárra $O(n^2 p)$ művelet, a tanítóoptimalizálás pedig a megoldó függvényében $O(n^2)$ és $O(n^3)$ között lehet. A lineáris kernel esetén a modell csak a $\mathbf w$ súlyvektort tárolja, a predikció $O(p)$; ezért nagy, de nagyjából lineárisan szeparálható adatra a lineáris baseline vagy a LinearSVC gyakran a futtatható választás. A Fák, random forest és gradiensboosting alfejezetben tanult fa- és boostingmodellek ezzel szemben a tabuláris adat jellemzőit tengelyenként vágják, és nem építenek teljes pontpár-mátrixot.

22.3.6 Feladatok

1. Értelmezés. A Fák, random forest és gradiensboosting alfejezetben tanult döntési fa döntései nem változnak, ha egy numerikus jellemzőt pozitív konstanssal szorzunk vagy eltolunk. A kNN döntése viszont változhat skálázás nélkül. Magyarázd el, miért, és adj egy kétdimenziós példát, ahol a Manhattan- és az euklideszi távolság különböző legközelebbi szomszédot ad.

2. Implementálás. A fenti példakódban futtasd a kNN-t $k=1, 5, 15, 31$ értékekkel, és írd ki a tanító- és tesztpontosságot, valamint a teszt-AUC-t. Mit tapasztalsz $k=1$ esetén, és mi a magyarázat?

3. Hibadiagnózis. Egy notebook MemoryError hibát ad ennél a sornál: pairwise_distances(X_train, X_train), ahol X_train.shape == (50000, 64). Számold ki a kért teljes mátrix bájtméretét, és adj két különböző javítást, amely a kNN feladatához valóban szükséges.

4. Megváltoztatott adatra transzfer. A termelési adat $n=120\,000$ tanítósorból, $p=40$ numerikus jellemzőből áll, és $m=30\,000$ sorra kell offline predikciót adni. Becsüld meg a tanító-tanító teljes távolságmátrix GiB-méretét, a páronkénti távolságszámítások számát a predikciós lépésben, és indokold, miért nem ugyanaz a memóriaigény a KNeighborsClassifier predikciójában.

22.3.7 Megoldások és indoklás

1. A fa minden csomópontban egyetlen koordinátára vonatkozó küszöböt vizsgál: $x_j \leq t$. A pozitív szorzó és az eltolás monoton transzformáció, tehát az $x_j \leq t$ igazságértéke nem változik. A kNN ezzel szemben több koordinátát összegző távolságot használ; az összeg tagjainak mértékegysége és szórása megváltoztatja, melyik pont kerül közelebb. Kétdimenziós példa: a kérdezett pont $\mathbf q=(0,0)$, a tanítópontok $\mathbf a=(1,0)$ és $\mathbf b=(0.6,0.6)$. Euklideszi távolság: $\|\mathbf q-\mathbf a\|_2=1$ és $\|\mathbf q-\mathbf b\|_2=\sqrt{0.36+0.36}\approx 0.85$, tehát $\mathbf b$ van közelebb. Manhattan-távolság: $d_1(\mathbf q,\mathbf a)=1$ és $d_1(\mathbf q,\mathbf b)=0.6+0.6=1.2$, tehát $\mathbf a$ van közelebb. A metrika választása tehát akár $k=1$ mellett is más címkét adhat.

2. Futtatható váz:

for k in (1, 5, 15, 31):
    pipe = make_pipeline(
        StandardScaler(), KNeighborsClassifier(n_neighbors=k)
    )
    pipe.fit(X_train, y_train)
    train_acc = accuracy_score(y_train, pipe.predict(X_train))
    test_acc = accuracy_score(y_test, pipe.predict(X_test))
    test_auc = roc_auc_score(y_test, pipe.predict_proba(X_test)[:, 1])
    print(k, train_acc, test_acc, test_auc)

$k=1$ esetén a tanítópontosság 1.000, mert minden pont saját maga a legközelebbi szomszédja. A tesztpontosság ilyenkor várhatóan alacsonyabb, mint a nagyobb $k$-k esetén, mert a modell a zajos és átfedő pontokat is megtanulja; ez a túlillesztés klasszikus jele. A nagyobb $k$ simítja a határt, de túl nagy $k$ már alulillesztést okozhat. Az ellenőrző invariáns, hogy a tanítópontosság $k=1$-nél pontosan 1 legyen.

3. A teljes mátrix mérete $8 \cdot 50\,000^2 = 2\cdot 10^{10}$ bájt, azaz $18.6\ \mathrm{GiB}$; egy közönséges notebook ezt gyakran nem tudja lefoglalni. Első javítás: ne építsünk explicit mátrixot, hanem használjuk a KNeighborsClassifier-t, amely a szomszédkeresést a $k$ szomszéd megtartásával végzi. Második javítás: ha valamilyen más okból mégis kell a páronkénti távolság, használjunk scipy.spatial.distance.pdist tömörített vektort, amely $9.3\ \mathrm{GiB}$-ot foglal, vagy chunkonként számoljunk. Nagyobb adatnál a közelítő szomszédkereső könyvtárak is szóba jönnek, de ott már más pontossági szerződést kell mérni.

4. A tanító-tanító mátrix: $8 \cdot 120\,000^2 = 115.2\cdot 10^9$ bájt, azaz $107.3\ \mathrm{GiB}$. A predikciós lépésben a páronkénti távolságok száma $m n_{\text{train}} = 30\,000 \cdot 120\,000 = 3.6\cdot 10^9$; mindegyikhez $p=40$ koordináta-pár tartozik. A KNeighborsClassifier nem tartja mind a $3.6$ milliárd távolságot, hanem soronként frissíti a $k$ legkisebbet, így a memóriaigény nagyságrendje $m \cdot k$ szomszédtárolás, nem pedig a teljes mátrix. Az ellenőrző invariant a $\text{bytes}/1024^3$ átváltás: a három szám 107.3 GiB, 3.6 milliárd páronkénti távolság és 144 milliárd elemi koordináta-különbségszámítás.

22.3.8 Gyakori tévedés ellenpéldával

Gyakori hiba, hogy egy 300 soros bemutatón az RBF-SVM nyer, ezért a csapat a több milliós termelési táblára is ezt választja. A 300 soros demó semmit nem mond a nagy adatos költségről. Konkrét ellenpélda: $n=2\,000\,000$ tanítósornál a teljes Gram-mátrix $8\cdot(2\cdot 10^6)^2 = 3.2\cdot 10^{13}$ bájt, körülbelül $29\ \mathrm{TiB}$. Ez nem fér el egyetlen észszerű gépen sem, hiába volt pontos a modell a kis mintán. A kernel olyan eszköz, amelynek matematikai előnyét a memória- és időkorlát ellenében kell mérlegelni. Hasonlóan téves az a mondat, hogy „a kNN-nek nincs tanítási ideje, tehát gyors”: a predikció költsége lineárisan nő a tanítómérettel, és nagy forgalmú szolgáltatásban ez a drága oldal. A Megfigyeléses becslés és érzékenység alfejezetből azt is tudjuk, hogy a távolsági hasonlóság nem oksági kapcsolat; a szomszédok egyezése nem azonos a beavatkozás hatásával.

Önellenőrzés: számold ki, mennyi a teljes távolságmátrix bájtmérete $n=80\,000$ sorra; miért kell a skálázót a tanítórészen illeszteni; mit változtat a $\gamma$ növelése; és miért nem elegendő egyetlen tesztpontosság a modellválasztáshoz?

A két holdon közölt AUC-tartományok hipotézisek: csak a generátor, a seed, a zaj és a felosztás rögzítése után reprodukálhatók. kNN és RBF-SVM előtt a skálázást a tanítófoldon belül illesszük.

22.3.9 Rövid összefoglaló

A kNN lustatanuló: tanításkor tárol, predikciókor minden kérdezősorhoz az összes tanítóponttal számol. A döntés távolságmetrikán múlik, ezért a jellemzőket tanítórészen illesztett skálázóval kell összemérhetővé tenni. Az SVM lineáris margót keres, a kernel pedig magasabb jellemzőtérbeli skalárszorzatot számít ki közvetlenül; az RBF-kernel hajlított határt ad, de $\gamma$ és $C$ hangolást igényel. A négyzetes növekedés miatt a páronkénti mátrix mérete $8n^2$ bájt, ezért kis mintán mért siker nem igazol nagy adatos megvalósíthatóságot. A következő alkalmazás a Modellcsalád választása tudományos jegyzőkönyvvel modellcsalád-választási jegyzőkönyv, ahol a mérést és a költségkorlátot együtt rögzítjük.