Bölüm 3: Temel Algoritmalar (Fundamental Algorithms)

Kaynak: Andriy Burkov -- "The Hundred-Page Machine Learning Book" (theMLbook.com)

Bölüm 3: Temel Algoritmalar

Bu bölüm, makine öğrenmesinde en cok bilinen ve en etkili bes temel algorithmayi kapsar. Bu algoritmalar ya kendi baslarina cok etkilidir ya da daha gelismis algoritmalarin yapi taslari olarak kullanılır.

3.1 Doğrusal Regresyon (Linear Regression)

Doğrusal regresyon, girdi örneğinin özelliklerinin doğrusal bir kombinasyonunu öğrenen bir regresyon algoritmasidir.

3.1.1 Problem Tanimi

Veriler: Etiketli örnekler koleksiyonu {(x_i, y_i)} (i = 1, ..., N) - N: Koleksiyonun boyutu - x_i: D boyutlu özellik vektoru - y_i: Gerçek degerli hedef - Her x_i(j) (j = 1, ..., D) de gerçek sayidir

Model formu:

f_{w,b}(x) = w . x + b

• w: D boyutlu parametre vektoru
• b: Gerçek sayisal parametre (bias / sapma)
• Amac: En dogru tahminleri yapan optimal w* ve b* değerlerini bulmak

SVM ile Karşılaştırma

Doğrusal regresyon modeli, SVM modeliyle benzer bir forma sahiptir (farki sign operatorunun olmamasi). Ancak rolleri farklidir: - SVM'de hiperduzlem bir karar siniri gorevi gorur; iki gruptan mumkun oldugunca uzak olmalidır - Doğrusal regresyonda hiperduzlem tum eğitim örneklerine mumkun oldugunca yakin olmalidir

Bu yakinlik gereksinimi kritiktir: regresyon cizgisi veri noktalarindan uzak olsaydi, yeni örnekler için tahminler hatali olurdu.

3.1.2 Cozum

Optimal w* ve b* değerleri, asagidaki ifadeyi minimize eden optimizasyon yoluyla bulunur:

Maliyet fonksiyonu (Cost Function) -- Ampirik Risk:

(1/N) * Toplam(i=1..N) (f_{w,b}(x_i) - y_i)^2

Temel kavramlar: - Amac fonksiyonu (Objective function): Minimize veya maksimize edilen ifade - Kayip Fonksiyonu (Loss function): Tek bir örnek için yanlis sınıflandırma cezasi. Burada karesel hata kaybi (squared error loss) kullanılır: (f(x_i) - y_i)^2 - Maliyet fonksiyonu: Ortalama kayip, yani ampirik risk (empirical risk)

Neden Karesel Hata?

• Mutlak deger de kullanilabilir, ancak turevi surekli degildir (fonksiyon puruzsuz degil)
• Puruzsuz olmayan fonksiyonlar, doğrusal cebir ile kapali form çözümler bulmada zorluk yaratir
• Karesel ceza, gerçek hedef ile tahmin arasındaki farki bu farkin büyüklugune gore abartir -- büyük hatalar daha cok cezalandirilir
• Kup veya dort gibi daha yüksek usler de kullanilabilir, ancak turevleri daha karmaşıktir

Neden Turev Önemli?

Maliyet fonksiyonunun Gradyani hesaplanip sifira esitlenerek, optimal w* ve b* değerleri doğrudan hesaplanabilir (kapali form çözüm).

Aşırı Uyum (Overfitting)

Aşırı uyum: Modelin eğitim verilerini cok iyi tahmin etmesi ancak yeni verilerde sik hata yapmasi durumu.

• Doğrusal modeller nadiren aşırı uyum gösterir
• Polinom regresyonu (örneğin derece 10) ile eğitim verisi neredeyse mukemmel tahmin edilebilir, ancak yeni veriler için büyük hatalar olusur
• Aşırı uyumu onleme teknikleri Bölüm 5'te incelenir

3.2 Lojistik Regresyon (Logistic Regression)

Lojistik Regresyon aslinda bir regresyon degil, bir sınıflandırma algoritmasidir. Isim, matematiksel formulasyonunun doğrusal regresyona benzerliginden gelir.

3.2.1 Problem Tanimi

Ikili sınıflandırma problemi: y_i in {0, 1}

Zorluk: w . x + b doğrusal kombinasyonu eksi sonsuzdan arti sonsuzluga yayilirken, y_i yalnizca iki değer alabilir.

Cozum: Ciktisi (0, 1) araliginda olan surekli bir fonksiyon kullanmak. Bu fonksiyon standart lojistik fonksiyon (sigmoid fonksiyonu):

f(x) = 1 / (1 + e^(-x))

• e: Dogal logaritmanin tabani (Euler sayisi)
• Cikti 0.5'e yakin veya üstündeyse: pozitif sinif
• Cikti 0.5'in altindaysa: negatif sinif
• Cikti, y_i'nin pozitif olma olasıligi olarak yorumlanabilir

Lojistik regresyon modeli:

f_{w,b}(x) = 1 / (1 + e^(-(w.x + b)))

3.2.2 Cozum -- Maksimum Olabilirlik

Doğrusal regresyondan farkli olarak, lojistik regresyonda ampirik riski minimize etmek yerine olabilirlik fonksiyonu (likelihood function) maksimize edilir.

Olabilirlik fonksiyonu: Bir gözlemin (örneğin), modele gore ne kadar olası oldugunu tanimlar.

• Eger y_i = 1 ise, olabilirlik p (modelin çıktısi)
• Eger y_i = 0 ise, olabilirlik 1 - p

Maksimum olabilirlik kriteri:

L_{w,b} = Carpim(i=1..N) f_{w,b}(x_i)^{y_i} * (1 - f_{w,b}(x_i))^{(1-y_i)}

Bu ifade su anlama gelir: y_i = 1 iken f_{w,b}(x_i), y_i = 0 iken (1 - f_{w,b}(x_i)).

Neden carpim? N adet etiketin N örnek için gözlemlenme olabilirligi, her bir gözlemin olabilirliginin carpimidir (gözlemler birbirinden bagimsiz oldugunda).

Log-olabilirlik (Log-Likelihood):

Pratikte, logaritmasi alinmis olabilirlik fonksiyonu kullanılır:

LogL_{w,b} = Toplam(i=1..N) [y_i * ln(f_{w,b}(x_i)) + (1-y_i) * ln(1 - f_{w,b}(x_i))]

ln kesinlikle artan bir fonksiyon oldugundan, log-olabilirligi maksimize etmek olabilirligi maksimize etmekle ayni sonuçu verir.

Cozum yöntemi: Kapali form çözüm yoktur. Gradyan Inisi (gradient descent) gibi sayisal optimizasyon yöntemleri kullanılır (Bölüm 4'te anlatilir).

3.3 Karar Ağaçi Öğrenmesi (Decision Tree Learning)

Karar ağaçi, karar vermek için kullanilabilen asiklik bir graftir (acyclic graph).

Nasil Calisir?

• Her dallanma dugumunde, özellik vektorunun belirli bir ozelligi j incelenir
• Özellik değeri bir esik değerinden düşükse: sol dal izlenir
• Degeri esikten büyük veya esitse: sag dal izlenir
• Yaprak dugume ulasildiginda, örneğin sınıfı hakkinda karar verilir

3.3.1 Problem Tanimi

Etiketli örnekler koleksiyonu; etiketler {0, 1} kumesine aittir. Amac, bir örneği özellik vektoru verildeginde siniflandirabilecek bir karar ağaçi oluşturmaktir.

3.3.2 Cozum -- ID3 Algoritmasi

ID3 algoritmasi, ortalama log-olabilirligi yaklasik olarak optimize ederek parametrik olmayan bir model f_ID3 oluşturur.

Algoritma adim adim:

1. Baslangic: Tum örnekleri içeren tek bir dugumle basla. Bu dugum sabit bir tahmin üretir:

f_ID3^S = (1/|S|) * Toplam_{(x,y) in S} y

Bu model, herhangi bir x girdisi için ayni tahmini verir.

2. En Iyi Bolunmeyi Bul: Tum özellikler j = 1, ..., D ve tum esik değerleri t icin, S kumesini iki alt kumeye bol: - S- = {(x,y) | (x,y) in S, x(j) < t} (esikten küçükler) - S+ = {(x,y) | (x,y) in S, x(j) >= t} (esikten büyük veya esitler)

3. Iyiligin Degerlendirilmesi -- Entropi:

Entropi: Bir rasgele değişken hakkindaki belirsizligin olcusu. - Tum değerler esit olasılikli ise: entropi maksimum - Yalnizca tek değer mumkunse: entropi minimum (= 0)

Bir örnek kumesi S için entropi:

H(S) = -f_ID3^S * ln(f_ID3^S) - (1 - f_ID3^S) * ln(1 - f_ID3^S)

Bir bölünmenin entropisi, iki entropinin ağırlıkli toplamidir:

H(S-, S+) = (|S-|/|S|) * H(S-) + (|S+|/|S|) * H(S+)

Her adimda, bu ağırlıkli entropiyi minimize eden bölünme secilir.

4. Durma Kosullari: - Yaprak dugumundeki tum örnekler dogru siniflandirilmissa - Bolunecek özellik bulunamiyorsa - Bolunme entropiyi epsilon'dan az azaltiyorsa (deneysel olarak belirlenir) - Ağaç maksimum d derinligine ulasmissa (deneysel olarak belirlenir)

Önemli not: ID3, her yinelemede yerel bir karar verdigi için (gelecekteki bölünmelere bakmaz), optimal çözümu garanti etmez. Geri izleme (backtracking) teknikleriyle iyilestirilebilir.

Entropinin sezgisel anlami: Entropi, S'deki tum örnekler ayni etikete sahip olduğunda 0'a (minimum) ulasir. Örneklerin tam yarisi 1 etiketli oldugunda 1'e (maksimum) ulasir -- bu yaprak sınıflandırma için ise yaramaz.

3.4 Destek Vektor Makinesi (Support Vector Machine -- SVM)

Bölüm 1'deki SVM girisinin üstüne, iki kritik soru ele alinir:

3.4.1 Gurultu ile Basa Cikma (Noise)

Verilerde gurultu varsa (aykiri değerler veya yanlis etiketler), hicbir hiperduzlem örnekleri mukemmel ayiramayabilir.

Cozum -- Mentes Kayip Fonksiyonu (Hinge Loss):

max(0, 1 - y_i * (w . x_i - b))

• Kisitlar saglaniyorsa (örnek dogru tarafta): kayip = 0
• Örnek yanlis taraftaysa: kayip, karar sinirindan uzaklikla orantili

Yumusak Marjinli SVM (Soft-Margin SVM) Maliyet Fonksiyonu:

C * ||w||^2 + (1/N) * Toplam(i=1..N) max(0, 1 - y_i * (w . x_i - b))

• C hiperparametresi: Marj büyüklugu ile yanlis sınıflandırma arasındaki dengeyi kontrol eder
• C cok büyükse: ikinci terim ihmal edilir, algoritma yalnizca en genis marjini arar (yanlis sınıflandırmalari goz ardi eder)
• C kuculdukce: yanlis sınıflandırma daha maliyetli olur, algoritma marjdan feragat ederek daha az hata yapmaya çalışır
• Sert marjinli SVM (Hard-Margin): Orijinal formulasyon (gurultuye izin vermez)
• Yumusak marjinli SVM (Soft-Margin): Mentes kaybi optimize eden versiyon

C, ampirik risk (eğitim verisini iyi sınıflandırma) ile genellestirme (gelecekteki örnekleri iyi sınıflandırma) arasındaki dengeyi duzenler.

3.4.2 Dogasal Doğrusal Olmayanligi Ele Alma (Kernel Trick)

Veriler orijinal uzayda bir hiperduzlemle ayrilamiyorsa ne yapilir? Veriyi daha yüksek boyutlu bir uzaya donusturerek doğrusal olarak ayrilabilir hale getirilebilir.

Cekirdek Hilesi (Kernel Trick): Orijinal uzayi daha yüksek boyutlu bir uzaya acikca donusturmeden, maliyet fonksiyonu optimizasyonu sirasinda bu dönüşümu dolayli olarak gerçeklestiren bir yöntem.

Örnek: 2B veriyi 3B uzaya donusturme: - Donusum: phi([q, p]) = (q^2, karekok(2)*q*p, p^2) - 2B'de doğrusal olmayan karar siniri, 3B'de doğrusal hale gelir

Lagrange Carpanlari Yöntemi

SVM optimizasyon problemi, Lagrange carpanlari ile yeniden formule edilir:

max_{alpha_1..alpha_N} Toplam(i=1..N) alpha_i - (1/2) * Toplam_i Toplam_k y_i*alpha_i*(x_i . x_k)*y_k*alpha_k

Kisitlar: Toplam(i=1..N) alpha_i * y_i = 0 ve alpha_i >= 0

Bu formulasyonda özellik vektorleri yalnizca ic carpim x_i . x_k olarak gorulur. Cekirdek hilesi, bu ic carpimi yüksek boyutlu uzayda doğrudan hesaplamadan, orijinal uzaydaki basit bir işlemle elde etmeyi saglar.

Örnek -- Kuadratik Cekirdek: - (q_1, p_1) ve (q_2, p_2) icin: k(x_i, x_k) = (x_i . x_k)^2 - Bu, donusturulmus vektorlerin ic carpimiyla ayni sonuçu verir

Yaygin Cekirdek Fonksiyonlari

Rbf Cekirdegi (Radial Basis Function):

k(x, x') = exp(-||x - x'||^2 / (2 * sigma^2))

• ||x - x'||^2: Iki özellik vektoru arasındaki karesel Oklid mesafesi
• RBF cekirdeginin özellik uzayi sonsuz boyutludur
• sigma hiperparametresi ile puruzsuz veya kirmali karar siniri secimi yapilabilir

Oklid Mesafesi:

d(x_i, x_k) = karekof(Toplam(j=1..D) (x_i(j) - x_k(j))^2)

3.5 k-En Yakin Komsular (k-Nearest Neighbors -- kNN)

kNN, parametrik olmayan bir öğrenme algoritmasidir. Diger algoritmalarin aksine, model olustuktan sonra eğitim verisini atamaaz; tum veri seti bellekte tutulur.

Nasil Calisir?

1. Yeni, daha once gorulmemis bir örnek x gelir
2. Algoritma, özellik uzayinda x'e en yakin k eğitim örneğini bulur
3. Sınıflandırma: Cogunluk etiketini dondurur
4. Regresyon: Ortalama etiketi dondurur

Mesafe Fonksiyonlari

Iki noktanin yakinligi bir mesafe fonksiyonu ile belirlenir:

Oklid Mesafesi: Yukarda tanimlandi.

Kosinus Benzerligi (Cosine Similarity):

s(x_i, x_k) = cos(aci(x_i, x_k)) = (Toplam(j) x_i(j)*x_k(j)) / (karekof(Toplam(j) x_i(j)^2) * karekof(Toplam(j) x_k(j)^2))

• Iki vektor ayni yonde: kosinus benzerligi = 1
• Dik (ortogonal): = 0
• Zit yonlerde: = -1
• Mesafe metrigi olarak kullanmak için -1 ile carpilir

Diger mesafe metrikleri: Chebyshev, Mahalanobis, Hamming mesafeleri.

Mesafe metrigi ve k değeri, algoritmaya baslamadan once secilen hiperparametrelerdir. Mesafe metrigi veriden de ogrenilebiIir (Bölüm 10'da anlatilir).

kNN'in Maliyet Fonksiyonu

Sasirtici bir şekilde, kNN'in maliyet fonksiyonu literaturde fazla incelenmemistir. Li ve Yang (2003) tarafından yapilan bir analize gore:

Ikili sınıflandırma, kosinus benzerligi ve normalize özellik vektorleri varsayimiyla, kNN yerel doğrusal bir sınıflandırma yapar:

w_x = Toplam_{(x', y') in R_k(x)} y' * x'

Burada R_k(x), x girdisine en yakin k komsunun kumesidir. Yani 0 etiketli komsular atlanarak, pozitif etiketli komsu özellik vektorleri toplanir.

Maliyet fonksiyonu:

L = -Toplam_{(x', y') in R_k(x)} y' * x' . w_x + (1/2) * ||w||^2

Ozet Karşılaştırma Tablosu

Lisans ve Atıf

Bu sayfa, Andriy Burkov tarafından yazılan "The Hundred-Page Machine Learning Book" kitabına dayalı notlar içermektedir.

• Kitap: theMLbook.com
• GitHub: github.com/aburkov/theMLbook
• Lisans: MIT License — Copyright (c) 2019 Andriy Burkov
• İlke: "Read first, buy later" — Kitabı önce okuyun, beğenirseniz satın alın.

MIT Lisansı gereği bu copyright bildirimi ve izin bildirimi, Yazılımın tüm kopyalarına veya önemli bölümlerine dahil edilmelidir.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND. Bu içerik eğitim amaçlıdır ve orijinal eserin yerine geçmez. Tam kitap için themlbook.com adresini ziyaret edin.