Destek karar makineleri (Support Vector Machines – SVM) yüksek boyutlu verilerde sıkça kullanılan bir ayrım metodudur. Veri üzerinde eğitilerek uygulanır. Eğitim için konveks optimizasyonunda kullanılan herhangi bir metot seçilebilir. Temelde düşük boyutta lineer olarak ayrılamayacak bir veri kümesini, daha yüksek boyuta taşıyarak bir düzlem yardımıyla ayırmayı sağlar. Destek karar makinelerinin mantığını anlamak için, lineer ayrımın nasıl işlediğine bakmamız gerekir.[more]
Yukarıdaki şekilde Fisher Lineer Diskriminantı (Fisher Lineer Discriminant) görülmektedir. Burada iki farklı tipteki veri birbirinden lineer olarak ayrılmaktadır. Bu lineer doğru veya ayrım fonksiyonu aşağıdaki şekilde ifade edilir:
Burada x ayrım yapacağımız girdi verisi, b ise eşik değer veya orijine uzaklık olarak tanımlanmaktadır. w ise ağırlık matrisi yada veriye bağlı olarak bir vektördür. Bu vektör veri eğitim aşamasında şekillenir.
Destek karar makineleri, yapı itibariyle Perceptron algoritmasına benzemesine rağmen aralarında çok önemli bir fark vardır. Bu fark çekirdek (kernel) fonksiyonu ile sağlanmaktadır. Çekirdek fonksiyonun Destek karar makinelerine sağladığı avantaj aşağıda gösterilmektedir.
Bu çekirdek fonksiyonun görevi aslında lineer olarak ayrılamayan veriyi, daha yüksek bir boyuta taşıyarak bir düzlem ile ayrım yapılmasını sağlar. Çeşitli çekirdek fonksiyonları bulunmaktadır, örneğin
Destek karar makineleri çekirdek kullandıkları için yukarıda bahsettiğimiz Fisher Lineer Diskriminantından ayrılıyorlar. Aşağıda, Destek karar makinelerinin ayrım fonksiyonu gösterilmektedir.
Bu ayrım fonksiyonunu lineer ayrım fonksiyonlarından ayıran tek şey, w ağırlık matrisinin eğitim şeklidir. Bu ayrımın lineer bir düzlem şeklinde yapılabilmesi için, w’nin karmaşıklığının en düşük olması gerekir. Bu da ancak ikinci dereceden (Quadratic) optimizasyon teknikleri ile mümkün olabilir. Aşağıdaki optimizasyonun neye göre yapılması gerektiği çıkarımlar göz önüne alınmadan basitçe verilmiştir.
Yukarıdaki ikili (dual) optimizasyonu çözmek için Lagranj çarpanlarının kullanılması gerekir, Lagranj açılımı yapıldıktan sonra ikili optimizasyon problemi aşağıdaki şekli alacaktır.
Burada bütün işlemler aslında çekirdek fonksiyonunun üzerinde gerçekleşmektedir. Dolayısıyla burada yapılacak bir optimizasyonun tüm veri üzerinde üstsel bir etki yapacağı ve veriyi non-lineer olarak ayıracağı düşünülebilir. Yukarıdaki optimizasyon işlemi için konveks optimizasyonunda kullanılabilen tüm yöntemler geçerli olacaktır. Bu da demek oluyor ki optimizasyon sonucunda bulunan tüm lokal minimum yada lokal maksimum noktaları tektir ve globaldir. Destek karar makinelerinde en çok kullanılan optimizasyon tekniği Sequential Minimum Optimizasyon (SMO) dur [Platt, 1998]. SMO hızlı ve kararlı bir tekniktir.
Çeşitli destek karar makineleri bulunmaktadır. Verinin gürültü içerip içermemesine bağlı olarak en çok kullanılan iki yöntem bulunmaktadır. Bunlar maksimal marjin (maximal margin) ayrımcısı ve esnek marjin (soft margin) ayrımcısıdır.
Maksimal marjin ayrımcısında amaç marjini oldukça geniş tutmaktır. Bunu yapabilmek içinde marjine yakın olan tüm vektörler seçilerek bu vektörleri ayırabilecek en geniş alanı bulmak gerekir. Esnek marjin ayrımcısında ise kullanılan yardımcı vektörler marjini optimum tutacak şekilde seçilir. Dolayısıyla esnek marjin ayrımcısı ayrımı yapmak için daha genel bir düzlem belirler. Bu da esnek marjin ayrımcısının veriyi aşırı uyum (overfitting) olasılığını düşürür. Maksimal marjin ise veriyi aşırı uyacağından gürültüye daha duyarlı olacak, gürültülü veri için kötü sonuçlar üretecektir.
Görüldüğü gibi destek karar makinelerindeki temel mantık, veri lineer olarak ayrılabilecek uzaya (Hilbert Uzayı) taşımak ve üstsel optimizasyon ile yardımcı vektörleri belirleyerek, bunlar üzerinden ayrım marjinini belirlemektir.