# From Least Squares to KNN, Statistical Models, Supervised Learning and Function Approximation

Infinity returns!

As you know, I follow the book The Elements of Statistical Learning and my main motivation is to help people like me who are suffering from not understanding anything on their first attemp to read the book since the book is not quite appropriate for beginners. This is a little bit tough subject but I will try to simplfy it as much as I can or at least to give some intuition that lays the foundation of the theories we will encounter.

### Starting with Two Simple Methods: Least Squares and Nearest Neighbors

These are the good starting points in this journey because they are the easiest, most basic, and most intuitive approaches that have their origins in the pre-computer era, and the large portions of today’s much fancier methods are the intelligent derivations of these two approaches.

The linear regression with least squares makes a huge assumptions: the model is linear. On the other hand, k-nearest neighbors makes very mild assumption about the structure of the model. The assumption made in linear regression makes it relatively stable but its predictions tend to be inaccurate because the real world is almost never linear. The KNN, on the other hand, tends to give accurate predictions but it can be easily unstable due to its mild assumptions. Let’s dive into them.

### Linear Models and Least Squares

From this point on, the book starts to express every calculation and computation in matrix and vector forms so the understanding of linear algebra would be a huge time and life saver in the remaining of the book. The residual sum of squares is given by:

Here we are trying to find such betas(coefficients) to minimize the RSS. In this example, there is only one input variable X and one output variable Y.  So the alternate representation of this is in vector form:

Consider Y is a vector of outputs and X is a matrix of inputs (1 for every row of the first column, and the value of the random variable X for the second column).  Taking the derivative of it and equating it to zero, we obtain betas as:

This is a basic linear algebra and differentiation job. But why did we include ones for the first columns? Let’s leave it for further subjects.

The result is a two-element vector, the first element is intercept and the other is the slope. Why? Because we include the intercept in X and made it two columns matrix.

This formula requires X transpose * X to be nonsingular so that it has an inverse. What does it mean? In linear algebra, a matrix has an inverse if it is nonsingular or in other words has full-rank. This means that the columns of the matrix have to be linearly independent of each other so that its determinant will be non-zero quantity. Since we use determinant in the denominator to find the inverse of a matrix,  a number / 0 is undefined. That is why it has to be full rank. Fortunately, there are more intelligent ways to calculate betas utilizing matrix decomposition methods such as QR decomposition that does not suffer from ill-conditioned zero determinant case.

### Nearest-Neighbor Methods

This is a more intuitive one than least squares linear regression is. In order to form a prediction for an observation, we find the nearest neighbors of it in terms of some distance measures such as euclidean distance.Then we average the outcomes of the neighbors to predict the outcome of the observation.

This simple method has only one parameter which is k: the number of neighbors. As k goes to infinity the prediction will be less accurate since we average over more observations but this decreases the variance of the predictions. On the other hand, as k goes to 1, the prediction tends to be more accurate because an observation is likely to be very similar to its nearest neighbor but the variance of prediction will be higher. In this case, we cannot use least squares methods to find optimal k because it would always pick 1 for k.

One big disadvantage of this method is that in order to find an observation’s nearest neighbors it needs n*n distance matrix to store each observation’s distance to all other observations. Here, n is the number of observations in the data and as n increases, n*n increases even faster which makes the computation and storage very costly.

### From Least Squares to Neares Neighbors

Least squares linear regression in which linear decision boundary is assumed is the most rigid one and stable to fit. Nearest neighbors, on the other hand, does not assume any stringent assumptions about the decision boundary and can adapt any situation. However, this makes it unstable relative to least squares (hight variance, low bias).

As it is always said, there is no free lunch in this science, so each method has its own advantages and disadvantages depending on data at hand. In some ways, these two methods can be enhanced to develop more advanced methods:

1- In KNN, all k-nearest neighbors of an observation has equal weights in averaging but it doesn’t have to be in this way. We might use some weights that decrease smoothly to zero with distance from the target point. We do this by a function called Kernel.

2- If the space is high dimensional then distance kernels can be modified to emphasize some variables more than others.

3- Rather than fitting a linear regression to entire data globally, we can fit linear models locally by locally weighted least squares.

4- We can expand the original inputs to a basis in which we can develop any complex models. Truncated power basis is an important methods for this.

5- We can non-linearly transform linear models by projection pursuit or neural network.

### Statistical Decision Theory

This section of the book is little bit difficult if you do not know basic probability. The book says than the statistical decision theory requires a loss function L(Y, f(X)) for penalizing errors in prediction. This is intuitive because we can quantify or measure how well our model is only when we have some penalty or loss function and all what we do is to minimize this loss. Squared error loss by far is the most convenient one:

E means expected value of its argument which is also known as mean. The first line might be obvious to you, but in the second line the things become messy. Well, it is the basic properties of probability theory actually. The quantity that we are trying to find its expected value is a continuous jointly distributed random variable. It consists of Y as a one random variable and f(X) as the other random variable and our quantity is the function of the two random variables: Y-f(X). In order to find the expected value of it, we need to integrate it with its joint probability density function. For more information, you can visit my notes of probability course from MIT.

If you revisited the probability then you may remember that a joint pdf of two random variable can be splitted into two parts as:

So when you replace Pr(dx, dy) in the original EPE formula above with this split and rearrange the terms, you can obtain:

here g(x,y) denotes the functions of two random variables which is [y-f(x)]^2. Then it is simply conditioned on X, and EPE can be written as:

This is again from probability theory. This is specifically called total expectation theorem (or more specifically law of iterated expectation, which is an abstract version of total expectation theorem). I cannot go over details of these theorems but you can learn by your self and use my notes of probability. My aim is just to give you some guidance to make you understand what is going on here. Going back to our discussion, EPE can be minimized poinwise. The solution is the conditional expectation which is known as regression function. Then when least squares is used in fitting, the best prediction of Y at any point X=x is the conditional mean of Y.

The nearest-neighbor methods attempt to directly implement this recipe using the training data. The difference is that expectation is approximated by averaging over sample data, and conditioning at a point is relaxed to conditioning on some region close to the target point.

The two methods end up approximating conditional expectations by averages. But where do they differ? The least squares assumes that f(x) is well approximated by a globally linear function whereas knn assumes f(x) is well approximated by a locally constant function. KNN fails in high dimensional space because the neares neighbors need not be close to the target point and can result in large errors. That is why KNN is avoided when the input space is high dimensional.

### Function Approximation

All we try to do is to approximate to the true function (relationship) between inputs and output. What ever you call it machine learning, statistical learning, mathematical modelling, and so on, they all have this aim. The aim is to find a useful approximation to f(x). We can treat supervised learning as a function estimation problem in this sense.

The majority of approximations have associated a set of parameters θ so that we can modify them to suit the data at hand. In linear regression those parameters are betas, β, (the coefficients). Linear basis expansions could be another class of useful approximation and sigmoid transformation common to neural networks could be an example of nonlinear transformation. Least squares methods can be used to estimates such parameters by minimizing the residual sum of squares. Linear models has a closed form solution to the minimization problems but in some models the solution requires either iterative methods or numerical optimization.

In some situations least squares does not make much sense. A more general principle for estimation is maximum likelihood estimation. If we have observations from a density Prθ(y) indexed by some parameters θ, the log probability of the observed sample is

Maximum likelihood estimation says that the probability of observed sample is maximum. The intuition behind it is that we are likely to observe high probability observations more often than we observe low probability observations. So we assume that what we observe must be the most likely one.

Why is maximum likelihood estimation is more general methods than least squares is? How do they related to each other? Well actually under the assumption of normally distributed error terms, least squares methods are derived from maximum likelihood estimation method and hence they are identical:

As you can see the picture above, the least squares and maximum likelihood are closely related.

# İstatistiksel Öğrenme II – Modelin Netliğini Değerlendirme

statistik ne yazık ki kesin kuralları olan bir disiplin değil. Herhangi bir metot bir veri setinde çok iyi sonuçlar üretebilirken başka bir veri seti üzerinde çok kötü sonuçlar üretebilir. Bu yüzden belirli bir veri seti üzerinde en iyi performansı veren metodu bulabilmek çok önemli bir konu. Pratikte istatistiksel öğrenmenin en çetrefilli olayı da tam olarak budur: doğru yaklaşımı ve metodu belirlemek. Bu yazıda, belirli bir veri seti için en iyi sonucu üreten istatistiksel öğrenme prosedürünü seçmemizde bize yol gösterecek birkaç önemli konsepti inceleyeceğiz.

#### Uyum Kalitesinin Ölçümü

Bir istatistiksel öğrenme metodunun belirli bir veri seti üzerindeki performansını değerlendirmek için metodun ürettiği tahminlerin gerçek sonuçlarla ne kadar örtüştüğünü ölçümlememize yarayacak yöntemlere ihtiyacımız var. Yani, belirli bir gözlem için tahmin edilen cevap(reponse) değerin o gözlemin gerçek cevap(reponse) değerine ne kadar yakın olduğunu sayısallaştırmamız gerekiyor. Regresyon için, en yaygın olarak kullanılan ölçüm Ortalama Karesel Hata (Mean Squared Error-MSE)‘dır ve şu şekilde ifade edilir:

Burada (xi) ‘in i numaralı gözlem için ürettiği tahmini gösteriyor. Tahmin edilen değerler gerçek değerlere ne kadar yakınsa MSE o kadar küçük olur; gerçek değerlerden ne kadar uzaklaşırsa MSE o kadar büyük olur. Yukarıda MSE, modeli uydurmak(model fitting) için kullanılan training veri seti kullanılarak hesaplanır ve training MSE olarak ifade edilmelidir. Fakat genellikle, metodumuzun training veri seti üzerinde ne kadar iyi sonuçlar ürettiğiyle ilgilenmeyiz. Bilakis training veri seti dışındaki verilerde(test) modelin ne kadar kesin sonuçlar ürettiğiyle ilgileniriz. Peki neden durum böyle?

###### Örnek 1

Yukarıdaki grafiği inceleyerek bu durumu açıklayalım. Sol taraftaki grafikte siyah ile çizilmiş eğri bizim gerçek  fonksiyonumuzu gösteriyor. Turuncu çizgi ile mavi ve yeşil eğriler ise bizim gerçek  fonksiyonu için tahminlerimizi göstersin ve bunların esnekliği(flexibility) sırasıyla artıyor olsun; yani mavi turuncudan, yeşil de maviden daha esnek olsun. Turuncu çizgi “linear regression” metodu ile elde edilen tahmindir; yani esnekliği görece azdır. Mavi ve yeşil eğriler ise ilerideki konularda ayrıntılı ele alacağımız “smoothing splines” metodu kullanılarak elde edilen tahminlerdir ve bu eğriler farklı düzleme seviyeleri (level of smoothing) kullanılarak üretilmişlerdir. Grafiğe dikkatli baktığımızda göreceğimiz üzere esneklik seviyesi arttıkça eğri gözlemlenen veriye daha çok uyum sağlar (fit). Yeşil eğri en esnek olan eğridir ve gözlemlenen veriye en çok uyumu sağlamıştır. Fakat, bu eğrinin gerçek  eğrisine çok da benzemediğini görüyoruz; çünkü gereğinden fazla kıvrımlı. Smoothing spline fit metodunun esneklik seviyesini değiştirerek aynı veriye bir çok farklı eğri uydurabiliriz.

Sağ taraftaki grafikte gri eğri ortalama training MSE değerini esnekliğin  bir fonksiyonu olarak göstermekte. Burada esneklik kavramı istatistiki jargonda serbestlik derecesi(degree of freedom) olarak adlandırılır. Turuncu, mavi ve yeşil kareler sol taraftaki ilgili eğrinin MSE değerlerini belirtmekte. Daha kısıtlayıcı ve dolayısıyla daha düz(smooth) eğriler daha kıvrımlı olanlara nazaran daha az serbestlik derecesine (degree of freedom) sahiptir. Training MSE değeri esneklik arttıkça monoton olarak azalır. Bu örnekte gerçek  doğrusal değil, ve bu yüzden turuncu çizgi gerçek ‘i yeterince iyi tahminleyecek esnekliğe sahip değil. Yeşil eğri en düşük training MSE değerine sahip çünkü içlerinden en esnek olanı o. Bu örnekte gerçek  fonksiyonunu biliyoruz ve böylece test MSE değerlerini çeşitli esneklik seviyeleri için hesaplayabiliyoruz. (Elbette pratikte gerçek  fonksiyonu genellikle bilinmez; dolayısıyla bu örnekte yapacağımız hesaplamayı yapmak mümkün olmaz). Test MSE değeri sağ tarafta kırmızı eğri ile gösterilmekte. Esneklik seviyesi arttıkça training MSE değerine paralel olarak test MSE değeri en başta azalmakta, belli bir noktada test MSE değeri minimum olmakta ve o noktadan sonra test MSE değeri tekrar artmakta. Bu nedenle, turuncu ve yeşil eğriler yüksek test MSE değerine sahip. Mavi eğri test MSE değerini minimize etmekte ve sol taraftaki görselde de görülebileceği üzere zaten görsel olarak gerçek ‘i en iyi tahmin eden de bu. Yatay kesikli çizgi azaltılamayan hatayı (irreducible error) Var(e) gösteriyor ve bu da bütün metotların ulaşabileceği minimum test MSE değeri anlamına geliyor. Dolayısıyla, mavi eğri ile gösterilen smoothing spline tahmini optimuma yakın bir tahmin.

Yukarıdaki görselin sağ tarafındaki grafikte görebileceğiniz üzere istatistiksel öğrenme metodunun esnekliği arttıkça training MSE değerinde monoton bir azalma gözlemlerken test MSE değerinde U şekli gözlemliyoruz. Bu durum, eldeki veriden ve kullanılan istatistiksel metottan bağımsız olarak istatistiksel öğrenmenin temel bir özelliğidir. Model esnekliği arttıkça, training MSE hep azalır ancak test MSE hep azalmayabilir. Bir metot düşük training MSE değeri üretirken yüksek test MSE değeri üretiyorsa, bu durum elimizdeki veriye “aşırı uydurma” veya tam adıyla “overfitting” yapıyoruz demektir. Bunun sebebi elimizdeki istatistiksel öğrenme prosedürünün training veri setindeki örüntüyü (pattern) çok yakından takip etmesidir ve bu örüntülerden bazıları gerçek  fonksiyonunun özelliğinden kaynaklanmayıp tamamıyla şans eseri oluşan örüntülerdir. Training verisine “aşırı uydurma” yaptığımızda, test MSE değeri çok büyük olacaktır çünkü training verisinde bulduğumuzu sandığımız örüntüler(rastgele hatalardan kaynaklanan) test verisinde bulunmayacaktır. Şunu da not etmek gerekiyor ki aşırı uydurma yapalım ya da yapmayalım, neredeyse her zaman training MSE değerinin test MSE değerinden düşük olmasını bekleriz çünkü çoğu istatistiksel öğrenme metodu direkt ya da dolaylı olarak training MSE değerini minimize etmek için tasarlanmıştır.

###### Örnek 2

Yukarıdaki grafik gerçek ‘in yaklaşık olarak doğrusal olduğu başka bir örneği gösteriyor. Gene esneklik arttıkça, training MSE değerinin monoton olarak azaldığını, test MSE değerinin ise U şekli çizdiğini görüyoruz. Fakat, gerçek  fonksiyonu doğrusala yakın bir fonksiyon olduğundan, test MSE artmadan önce çok az bir miktarda azalıyor; dolayısıyla turuncu least square fit yüksek miktarda esnek olan yeşil eğriden daha iyi tahminleme yapıyor.

Aşağıdaki figür ise gerçek  fonksiyonunun doğrusal olmadığı bir örneği gösteriyor. Training ve test MSE eğrileri aynı davranışı(yani training azalırken test MSE değeri U şekli çiziyor) gösteriyor fakat bu sefer test MSE değeri artmaya başlamadan önce her iki eğride de hızlı bir düşüş gözlemleniyor.

###### Örnek 3

Pratikte genellikle sadece training MSE değerini hesaplayabiliriz; test MSE değerini hesaplamak çok daha zordur çünkü genellikle test verisi elimizde yoktur. Yukarıdaki üç örnekten görebileceğiniz üzere, minimum test MSE değerini üreten modelin esneklik seviyesi veri setinden veri setine ciddi derecede farklılık gösterebiliyor. Bu minimum test MSE noktasını hesaplamak için bir çok yöntem var. Bunlardan en yaygını cross-validation. İleriki yazılarda ayrıntılı olarak inceleyeceğimiz için şimdilik burada duralım.

Test MSE değerinde gözlemlediğimiz U şekli istatistiksel öğrenme metotlarının birbirleriyle rekabet içinde olan iki özelliğinden kaynaklanıyor. Matematiksel kanıtlamayı burada yapmaya kalkarsak yazının amacını çok aşmış oluruz, fakat beklenen(expected) test MSE değerinin her zaman üç temel miktarın toplamına eşit olduğunu söyleyelim:

Burada   beklenen(expected) test MSE değerini gösteriyor ve bu da bir sürü farklı training veri seti kullanılarak hesaplanan ‘erin test setleri üzerindeki MSE değerlerinin ortalamasına tekabül ediyor.

Bu denklem bize şunu diyor aslında: beklenen test hatasını minimize etmek için, aynı anda hem düşük varyansa hem de düşük taraflılığa(bias) erişebilen bir istatistiksel öğrenme metodu seçmemiz gerekiyor. Dikkat edilmesi gereken konu şu ki varyans yapısı gereği her zaman sıfıra eşit ya da pozitiftir ve karesi alınmış taraflılık(bias) da hiçbir zaman negatif olamaz. Bu yüzden, beklenen test MSE değeri asla ‘nin yani azaltılamaz hatanın (irreducible error) altına inemez.

Bir istatistiksel öğrenme metodunun taraflılığı ve varyansı derken tam olarak neden bahsediyoruz? Varyans ‘in farklı training veri setleri kullanılarak hesaplandığında ne kadar değiştiği ile ilgilidir. Training veri seti istatistiksel öğrenme metodunu uydurmak(fit) için kullanıldığından, farklı training veri setleri farklı ‘ler üretecektir. Fakat ideal olarak gerçek  için olan tahminimizin farklı training veri seti kullandığımızda çok fazla değişmemesi gerekir. Eğer bir metot yüksek varyansa sahipse o zaman training veri setindeki küçük değişiklikler bile tahminimiz olan ‘te büyük değişikliklere sebep olur. Genel olarak, daha esnek istatistiksel metotlar daha yüksek varyanslara sahiptir. Örnek 1‘deki yeşil ve turuncu eğrileri gözlemleyin. Esnek yeşil eğri gözlemleri çok yakından takip ediyor. Bu eğri yüksek bir varyansa sahip çünkü gözlemlerden herhangi birini değiştirdiğimizde hesapladığımız  fonksiyonu ciddi derecede değişir. Diğer yandan, turuncu “least squares” çizgisi ise göreceli olarak daha az esnektir ve dolayısıyla daha düşük varyansa sahiptir çünkü herhangi bir gözlemi değiştirdiğimizde bu değişiklik fonksiyonumuzda çok çok ufak bir değişikliğe neden olacaktır.

Taraflılık(bias) ise gerçek hayattaki bir problemi yaklaşık olarak olarak modellediğimizde modelimizin sebep olduğu hatadır. Bu hata seçtiğimiz model basitleştikçe artış gösterir. Örneğin, linear regression Y ve X1,X2, . . . , Xp arasında doğrusal bir ilişki olduğunu var sayar. Gerçek hayatta karşılaştığımız herhangi bir problemin böylesine basit bir doğrusal ilişkiye sahip olması çok az rastlanılan bir durumdur. Dolayısıyla linear regression ‘i tahminlemede şüphesiz bir biçimde bir miktar taraflılığa sebep olacaktır. Örnek 3‘te gerçek  doğrusal değildir, bu yüzden ne kadar training verisine sahip olursak olalım linear regression kullanarak net bir tahmin yapmamız mümkün değil. Diğer bir deyişle linear regression bu örnekte yüksek taraflılığa sebep oluyor. Fakat Örnek 2‘de gerçek  doğrusala çok yakın ve dolayısıyla elimizde yeterince veri olduğunda linear regression kullanarak net bir tahmin elde etmemiz mümkün. Genel olarak, daha esnek metotlar daha az taraflılığa sebep olur.

Genel bir kural olarak, daha esnek metotlar kullandığımızda varyans artarken taraflılık azalacaktır. Test MSE değerinin artmasını ya da azalmasını belirleyen etmen bu iki miktarın göreceli değişimidir. Esnekliği artırdığımızda taraflılık en başlarda varyansın artış hızından daha hızlı bir şekilde düşecektir. Sonuç olarak beklenen test MSE değeri de düşecektir. Ancak, belirli bir noktadan sonra esnekliği artırmak taraflılık üzerinde çok düşük miktarda etki gösterecektir ve varyansı ciddi derecede artırmaya başlayacaktır. Bu olduğunda test MSE değeri artış gösterir. Bu olay yukarıdaki 3 örneğin sağ tarafındaki grafiklerde gösteriliyor.

Yukarıdaki görseldeki üç grafik 1.,2. ve 3. örneklerimiz için beklenen test MSE değeri denklemimiz için sonuçlarını gösteriyor. Mavi eğri çeşitli esneklik seviyeleri için karesel taraflılığı (squared-bias), turuncu eğri de varyansı gösteriyor. Kesikli yatay çizgi ise azaltılamaz hatayı, gösteriyor. Kırmızı eğri ise bu üç miktarın toplamını yani beklenen test MSE değerini gösteriyor. Her üç örnekte de metodun esnekliği arttıkça varyans artıyor ve taraflılık azalıyor. Fakat, minimum test MSE değerine karşılık gelen esneklik seviyesi her örnek için ciddi derecede farklılık gösteriyor çünkü karesel taraflılık ve varyans hepsinde farklı hızlarlarla değişiklik gösteriyor. Soldaki grafikte en başlarda taraflılık varyansın değişim hızına kıyasla çok hızlı bir şekilde azalıyor ve dolayısıyla test MSE değerinde düşüşe sebep oluyor. Fakat ortadaki grafikte gerçek  doğrusala yakın olduğundan esneklik arttıkça taraflılıkta çok az bir azalmaya neden oluyor ve test MSE değeri çok az miktarda azalıyor ve sonrasında varyans arttığı için hızla artmaya başlıyor. Ve sağ taraftaki grafikte ise esneklik arttıkça taraflılıkta çok ciddi bir azalma oluyor çüknü gerçek  bu örnekte doğrusal olmaktan çok uzak. Ayrıca esneklik arttıkça varyansta da çok az bir artış gözlemleniyor. Sonuç olarak, test MSE değeri çok ciddi miktarda azalıyor ve belirli bir noktadan sonra çok az artış gösteriyor.

Bu durum taraflılık-varyans dengesi (bias-variance trade-off) olarak adlandırılıyor. Bir istatistiksel öğrenme metodunun düşük test MSE değeri üretebilmesi için hem düşük varyansa hem de düşük karesel taraflılığa sahip olması gerekiyor. Bu denge olarak ifade ediliyor çünkü son derece düşük taraflılığı olup son derece yüksek varyansa sahip bir metot veya tam tersini elde etmek kolay. Buradaki zorlayıcı nokta hem varyansı hem de karesel taraflılığı düşük olan bir metot bulmak.

Gerçek hayatta gerçek ‘i genellikle bilmeyiz. Bu yüzden bir istatistiksel öğrenme metodunun test MSE değerini, taraflılığını ve varyansını hesaplamak çoğu zaman mümkün değildir. Yine de taraflılık-varyansa dengesini göz önünde bulundurmamız gerekiyor. Bunları nasıl hesaplayacağımıza dair metotları sonraki yazılarda ele alacağız.

#### Sınıflandırma (Classification) Olayı

Şimdiye kadar model netliğini tartışırken hep regresyona odaklandık. Fakat karşılaştığımız konseptlerin çoğu, mesela taraflılık-varyans dengesi, sınıflandırma metotları için de geçerli. Buradaki tek değişiklik tahmin etmeye çalıştığımız değişkenin artık sayısal bir değişken olmaması. Diyelim ki elimizdeki veri şöyle olsun: {(x1, y1), . . . , (xn, yn)} ve gerçek ‘i hesaplamaya çalışalım. Burada y değişkeni kalitatiftir. Tahminimizin, , netliğini ölçmedeki en yaygın yaklaşım training hata oranıdır (training error rate) ve bu da tahmin ettiğimiz ‘i training veri setine uyguladığımızda elde ettiğimiz hatalı tahminlerin tüm tahminlere oranıdır.

Üzerinde şapka olan y i.’ci gözlem için tahminimizi temsil ediyor. I fonksiyonu ise içindeki ifade doğru ise 1 değil ise 0 üretiyor. Dolayısıyla yukarıdaki fonksiyon bize yanlış sınıflandırılan gözlemlerin yüzdesini veriyor.

Burada da gene tahminimizin training veri seti üzerinde ne kadar iyi sonuçlar ürettiğinden ziyade test veri seti üzerinde ne kadar iyi sonuçlar ürettiğiyle ilgileniriz. İyi bir sınıflandırıcı(classifier) test MSE değeri minimum yapandır.

##### Bayes Sınıflandırıcısı (Bayes Classifier)

Test MSE değeri her bir gözlemi tahmin değişkenlerine bakarak en yüksek olasılıktaki sınıfa atayarak minimize edilir. Diğer bir deyişle x0 tahminleyici değişken vektörüne (yani X1,X2,…,Xp) sahip bir test gözlemini öyle bir j sınıfına atamalıyız ki

Pr(Y = j|X = x0)

değeri maksimum olsun. Bu ifade bir koşullu olasılık (conditional probability)‘dır ve şu şekilde ifade edilir: x0 verildiğinde Y’nin j’ye eşit olma olasılığı. Bu son derece basit sınıflandırıcı Bayes Sınıflandırıcısı(Bayes Classifier) olarak adlandırılır. Yalnızca iki sınıftan(sınıf1, sınıf2) oluşan problemlerde Bayes Sınıflandırıcısı bir gözlemi Pr(Y = 1|X = x0) > 0.5 ise birinci sınıfa değilse ikinci sınıfa atar.

Yukarıdaki grafik X1 ve X2 tahminleyici değişkenlerinden oluşan iki boyutlu bir uzaydaki bir örneği gösteriyor. Turuncu ve mavi halkalar iki farklı sınıfa ait olan training veri seti gözlemlerini gösteriyor. X1 ve X2‘nin her bir değeri için, cevap (response) değişkeninin turuncu veya mavi olma olasılığı farklılık gösteriyor. Bu örnek yapay olarak yaratıldığından verinin nasıl oluşturulduğunu biliyoruz ve X1 ve X2’nin her bir değeri için koşullu olasılık değerlerini hesaplayabiliyoruz. Turuncu alan Pr(Y = orange| X) > 0.5 olduğu alanı, mavi alan ise bu değerin 0.5’ten küçük olduğu alanı gösteriyor. Kesikli mor çizgi ise olasılığın tam olarak 0.5 olduğu yerleri gösteriyor. Bu çizgi Bayes Karar Sınırı (Bayes decision boundary) olarak adlandırılıyor. Bayes Sınıflandırıcısının tahminleri bu sınır tarafından belirleniyor: eğer bir gözlem bu çizginin turuncu tarafına düşerse turuncu sınıfa, mavi tarafında düşerse mavi sınıfa atanıyor.

Bayes Sınıflandırıcısı mümkün olabilecek en düşük test hata oranını üretiyor ve bu da Bayes hata oranı (Bayes error rate) olarak adlandırılıyor. Bu örnekte Bayes hata oranı 0.1304. Sıfırdan büyük çünkü sınıflar birbirleriyle bazı noktalarda çakışıyor. Bayes hata oranı regresyon ortamındaki azaltılamaz hataya denk geliyor.

##### K-Nearest Neighbors

Teoride her zaman Bayes sınıflandırıcısını kullanmak isteriz. Ancak gerçek veriler için Y’nin X değerlerine bağlı koşullu olasılık dağılımını bilmeyiz; bu nedenle Bayes sınıflandırıcısını kullanmak imkansızdır. Bu yüzden, Bayes sınıflandırıcısı ulaşılamaz bir altın standarttır ve diğer metotlar bununla kıyaslanarak değerlendirilir. Y‘nin X‘e bağlı koşullu olasılık dağılımını hesaplamaya yönelik birçok yaklaşım var. Bunlardan biri de En Yakın K Komşu Sınıflandırıcısı(K-Nearest Neighbors or KNN)‘dır. Elimizde training ve test veri setleri olsun. Test verisetindeki bir gözlemin hangi sınıfa ait olacağını hesaplamak için KNN algoritması ilk olarak bu test gözlemine training veri setindeki  en yakın K gözlemi  (N0) bulur. Sonrasında bu en yakın K gözlemin sınıf dağılımını hesaplar.

Hesapladıktan sonra KNN sınıflandırıcısı Bayes kuralını uygular ve test gözlemini (x0) en yüksek olasılık değerine sahip sınıfa atar.

Yukarıdaki görselle birlikte KNN metodunu açıklamaya çalışalım. Sol tarafta 6 mavi ve 6 turuncu gözlemden oluşan küçük bir training veri seti gösteriliyor. Amacımız x ile gösterilen gözlem için sınıf tahminlemek. Diyelim ki K değerini 3 olarak seçtik. KNN ilk olarak bu gözleme en yakın 3 gözlemi bulacaktır. En yakın üç gözlemden ikisi mavi biri ise turuncu sınıfa ait gözüküyor ve bu gözlem için tahminimiz 2/3 olasılıkla mavi sınıf 1/3 olasılıkla turuncu sınıf olarak hesaplanıyor. Dolayısıyla KNN bu gözlem için mavi sınıf tahminliyor. Sağ tarafta ise KNN metodunu K=3 ile mümkün olan bütün X1 ve X2 değerleri için uyguladık ve KNN karar sınırını (KNN decision boundary) belirledik.

Çok basit bir yöntem olmasına rağmen KNN şaşırtıcı bir şekilde çoğu zaman optimal Bayes Sınıflandırıcısına yakın sınıflandırıcı üretiyor.

Aşağıdaki figür KNN‘in K=10 ile 100 adet gözleme uygulandığında elde edilen karar sınırını gösteriyor. Gerçek dağılım KNN sınıflandırıcısı tarafından bilinmemesine rağmen, KNN karar sınırı Bayes karar sınırına çok yakın. Test  hata oranı KNN ile 0.1363. Bu oran Bayes hata oranı olan 0.1304’e son derece yakın!

K’nin seçimi KNN sınıflandırıcısı üzerinde son derece önemli etkilere sahip. Aşağıdaki görselde K = 1 ve K = 100 iken elde edilen KNN karar sınırını görebilirsiniz. K=1 iken karar sınırı son derece esnek ve Bayes karar sınırında olmayan bazı örüntüler bulmuş. Bu düşük taraflılığa fakat son derece yüksek varyansa sahip bir sınıflandırıcıya denk geliyor. K arttıkça, metot daha az esnek olmaya başlıyor ve doğrusala yakın karar sınırları üretmeye başlıyor. Bu düşük  varyanslı fakat yüksek taraflılıklı sınıflandırıcıya denk geliyor.

Tıpkı regresyonda olduğu gibi, sınıflandırmada da training ve test hata oranları arasında güçlü bir ilişki yok.  K=1 olduğunda KNN training hata oranı 0 oluyor fakat test hata oranı oldukça fazla olabilir. Genel olarak, daha esnek sınıflandırma metotları kullandığımızda training hata oranı azalacaktır ancak test hata oranı azalmayabilir. Aşağıdaki figürde KNN test ve training hataları 1/K‘nin bir fonksiyonu olarak gösteriliyor.  1/K arttıkça yani K azaldıkça, metot daha çok esnekleşiyor. Regresyonda olduğu gibi, tranining hata oranı esneklik arttıkça hep azalıyor. Fakat test hata oranı gene U şeklini gösteriyor: en başta azalıyor(K=10 iken minimum oluyor) fakat belirli bir esneklik noktasından sonra tekrar artmaya başlıyor ve veriye aşırı uydurma (overfitting) gerçekleşiyor.

Hem regresyonda hem de sınıflandırmada, esneklik seviyesini doğru seçmek herhangi bir istatistiksel öğrenme metodunun başarısı için kritik derecede önemli. Taraflılık-varyans dengesi, ve bunun sonucunda oluşan U şeklinde test hata oranı bu seçimi zor bir işe dönüştürüyor. Test hata oranını hesaplamak ve optimum esneklik seviyesini seçmek için oluşturulan metotları ileriki yazılarda ayrıntılı olarak ele alacağız.