Softmaks Regresyonu

Önceki bölümlerde lineer regresyon tanıtıldı, daha sonra nasıl hesaplanacağını hatta büyük veri olması durumunda özel kütüphaneler ile nasıl iş yapılacağını gördük.

Regresyon, bir şeyin ne kadar, kaç tane olduğu gibi sorulara cevap aradığımızda kullandığımız bir araçtır. Bir evin kaç araya satılabileceğini, bir takımın kaç maç kazanabileceğini veya bir hastanın hastanede kaç gün yatacağını tahimin etmek istiyorsanız, muhtemelen regresyon sizin için en iyisidir.

Pratik uygulamalarda sınıflandırma daha çok gereklidir. Sınıflandırmada nesnelerin ne kadar olduğu yerine hangisi olduğu ile ilgileniriz:

  • Bu e-posta istenmeyen bildirim midir?
  • Bu müşterinin hizmet alması muhtemel midir?
  • Bu resim maymun, köpek, kedi veya horoz arasından hangisinin resmidir?
  • Hangi film sayfayı ziyaret eden kişinin en çok izlemek isteyeceği türdendir?

Makine öğrenmesi uygulayıcıları günlük kullanımda sınıflandırma ifadesini birbirinden ince bir çizgiyle ayrılan iki durum için kullanılır: (i) Örneğin hangi sınıfa ait olduğunu kesin olarak belirlemek (hard assignment) istediğimiz durum. (ii) Esnek olarak belirlemek (soft assignment), yani her bir sınıfa ait olma olasığının belirlenmesi. Aradaki fark detaya indiğinizde kapanır çünkü kesin olarak sınıfları belirlerken de aslında olasılık kullanırız.

Sınıflandırma (Classification)

Konuya çabuk ısınmak adına, $2\times2$ boyutunda siyah-beyaz resimlerin sınıflandırılması örneği ile başlayalım. Her bir pikseli bir sayı ile gösterirsek, bir resim için $x_1, x_2, x_3, x_4$ ile gösterdiğimiz dört özellik belirlenmiş olur. Dahası, resimlerin "kedi", "tavuk" ve "köpek" sınıflarından birine ait olduğunu kabul edelim.

Şimdi etiketlere yani resmin ait olduğu sınıfı nasıl ifade edeceğimize karar vermeliyiz. En doğal yol {kedi, tavuk, köpek} sınıflarını, birden üçe kadar olan tamsayılarla gösterip $y \in \{1, 2, 3\}$ biçiminde ifade etmektedir. Bu şekilde bilgisayarın hafızasına yük olmayız. Sınıflar arasıda doğal bir sıralama söz konusu olsaydı problemimiz regresyon problemi olurdu ve bu tür etiketleri kullannabilirdik. Mesela {bebek, çokuk, genç, yetişkin, yaşlı} örneğinde olduğu gibi.

Ancak genellikle sınıflandırma problemlerinde sınıflar arasında doğal bir hiyerarşi yoktur. Neyse ki İstatistikçiler uzun yıllar önce buna bir çözüm buldular: tek aktif kod (one-hot encoding). Tek aktif kod, sınıf sayısı kadar bileşene sahip bir vektördür. Veri kümseindeki bir örnek için tek aktif kod vektörü oluşturulurken, örneğin ait olduğu bileşen $1$, diğer bilşenler $0$ alı alınır. Bu durumda yukarıdaki üçlü sınıflandırmada etiketler

$$\mathbf{y} \in \{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}$$

şeklinde vektörler olur. Eğer $\mathbf{y}$ vektörü $(1, 0, 0)$ ise "kedi", $(0, 1, 0)$ ise "tavuk" ve $(0, 0, 1)$ ise "köpek" belirtir.

Ağ Yapısı (Network Architecture)

Her sınıfın koşullu olasılığını tahmin etmek için çoklu çıktı veren bir modele ihtiyacımız var. Lineer modellerle sınıflandırma yapabilmek amacıyla çıktı sayısı kadar lineer fonksiyon gerekir. Her çıktı kendi lineer fonksiyonuna karşılık gelir. Bizim durumumuzda $3$ çıktı sınıfı ve $4$ özellik olduğundan, $w$ ile göstereceğimiz $12$ tane ağırlık (weight), $b$ ile göstereceğimiz $3$ tane yanlılık (bias) terimleri olacaktır. Şimdi $o$ ile gösterilen her çıktı (output) için

$$ \begin{aligned} o_1 &= x_1 w_{11} + x_2 w_{12} + x_3 w_{13} + x_4 w_{14} + b_1,\\ o_2 &= x_1 w_{21} + x_2 w_{22} + x_3 w_{23} + x_4 w_{24} + b_2,\\ o_3 &= x_1 w_{31} + x_2 w_{32} + x_3 w_{33} + x_4 w_{34} + b_3 \end{aligned} $$

elde edilir. Bu hesabı aşağıdaki sinir ağı (neural network) diyagramı ile gösterebiliriz. Lineer regresyonda olduğu gibi, lojistik regresyon modeli de bir tek katman içerir. Her bir $o_1, o_2$, and $o_3$ çıktısı tüm $x_1$, $x_2$, $x_3$, and $x_4$ girdileri ile bağımlı olduğundan, çıktı katmanı tam bağlantılı katmanıdır (fully-connected layer).

Softmax regression is a single-layer neural network.

Modelimizi daha derlitoplu ifade etmek için, Lineer Cebir gösterimi kullanacağız. Vektör formatında $\mathbf{o} = \mathbf{W} \mathbf{x} + \mathbf{b}$ yazarak hem matematiksel açıdan hem de kod yazmada daha uygun bir form elde edilir. Burada tüm ağırlıklar $3\times4$ ebatında $\mathbf{W}$ matrisini oluşturur. Verilen bir $\mathbf{x}$veri örneği için çıktı vektörümüz, ağırlık matris ile örnek vektörünün çarpımına $\mathbf{b}$ yanlılık vektörünün eklenmesiyle elde edilir.

Softmaks İşlemi (Softmax Operation)

Modelimizin çıktılarını olasılıklar olarak yorumlamak istiyoruz. Parametrelerimizi, verinin olabılırılığini maksimum yapacak şekilde belirleyeceğiz. Daha sonra da tahminler üretebilmek için, bir eşik belirleyeceğiz. Örneğin elde edilen olasılıklar üzerinden en büyüğüne karşılık gelen sınıfı seçeceğiz.

Daha açık ifade edelim: $\hat{y}_k$ çıktısını verilen bir girdinin $k$ sınıfında olma olasılığı anlamını taşımasını istiyoruz. Bu durumda $\operatorname*{argmax}_k y_k$ işlemi sonucunda en büyük değere sahip sınıfı seçeriz. Mesela $\hat{y}_1$, $\hat{y}_2$, and $\hat{y}_3$ çıktıları $0.1$, $0.8$, and $0.1$ değerlerini alıyorsa, seçeceğimiz sınıf $2$ numaralı sınıftır, yani örneğimizdeki "tavuk" resmidir.

Yukarıda ${o}$ ile gösterilen ve "logit" denilen sayılar modelin çıktıları gibi görünebilir. Ancak lineer katmanın çıktılarını olasılıklar gibi ele almak sorun çıkarabilir. Bunların toplamının $1$ olması gerekiyor. Hatta girdilere bağlı olarak negatif değerler bile alıyorlar. Bunlar olasılığın temel aksiyomlarını (kabullerini) ihlal ediyor.

Bunları olasılıklarolarak alabilmemiz için her girdi için toplamlarının $1$ olması gerekiyor. Dahası kayıp fonksiyonunu da olasılıkların anlamlı olmasını sağlayacak şekilde seçmeliyiz. Modelimizin $0.5$ sonucunu verdiği tüm durumlarda bu örneklerin yarısının belirtilen sınıfa ait olduğunu düşünürüz. Buna ayarlama (calibration) denir.

Softmaks fonksiyonu 1959 yılında sosyal bilimci R. Duncan Luce tarafından bahsettiğimiz sınıflandırmaya benzer olan seçim modeli için bulundu. Elde edilen $o$ değerlerini negatif olmayan ve toplamları $1$ olan sayılara çevirmek, bunun yanında modelimizin türevlenebilir olmasını şu şekilde sağlayacağız: Bir $o$ sayısının üstel fonksiyon altındaki değerini diğer tüm sayıların üstellerinin toplamına oranlayacağız. Sayının üstelini almak sonucun negatif olmamasını, toplama oranlamak da sonuçların toplamının $1$ olmasını garanti eder. Matemaiksel olarak

$$ \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)} \quad \text{olmak üzere}\quad \hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) $$

şeklinde yazabiliriz.

Üçlü örneğimizde her $i$ için $0 \leq \hat{y}_i \leq 1$ ve $\hat{y}_1 + \hat{y}_2 + \hat{y}_3 = 1$ olacağını görebilirsiniz. Dolayısıyla $\hat{y}$ bir olasılık dağılımı belirtir ve $\hat{\mathbf{y}}$ vektörünün değerleri de bu şekilde yorumlanır. Softmaks işlemi büyüklük küçüklük sıralamsını değiştirmez ve yani en olası sınıfı iki yoldan da seçebiliriz:

$$ \hat{\imath}(\mathbf{o}) = \operatorname*{argmax}_i o_i = \operatorname*{argmax}_i \hat y_i. $$

Sonuç olarak $\mathbf{o}$ vektörünü oluşturan sayılar, softmaks öncesi her sınıfın olasılıklarını belirleyen sayılardır. Vektör gösterimi ile ${\mathbf{o}}^{(i)} = \mathbf{W} {\mathbf{x}}^{(i)} + {\mathbf{b}}$, where ${\hat{\mathbf{y}}}^{(i)} = \mathrm{softmax}({\mathbf{o}}^{(i)})$ şeklinde yazabiliriz.

Küçük Yığınları Vektörleştirme (Vectorization for Minibatches)

Etkin bir hesaplama ve GPU kullanabilmek için verinin küçük veri yığınları ile vektör hesabı yapılır. Verinin bir kısmından oluşan $\mathbf{X}$ yığınını ele alalım. Yığın $n$ elemandan örnek veriden ve her bir örnek $d$ boyutlu olsun. Sınıfların (çıktılar) saysının da $q$ olduğunu kabul edelim. Bu durumda küçük yığının $\mathbf{X}$ özellik matrisi $\mathbb{R}^{n \times d}$ uzayındadır. Benzer şekilde ağırlıklar $\mathbf{W} \in \mathbb{R}^{d \times q}$ ve yanlılık terimi $\mathbf{b} \in \mathbb{R}^q$ olur. Dolayısıyla denklemlerimiz
$$ \begin{aligned} \mathbf{O} &= \mathbf{X} \mathbf{W} + \mathbf{b}, \\ \hat{\mathbf{Y}} & = \mathrm{softmax}(\mathbf{O}). \end{aligned} $$ formunda yazılabilir.

Veri kümesindeki örnekler için tek tek hesaplama yapmak istediğimizde matris-vektör çarpımı yapacaktık, burada ise matris-matris çarpımı ile işlemleri hızlandırıyoruz. Softmaks için de önce $\mathbf{O}$ matrsinin eksponansiyeli alınır, daha sonra da tolama bölünerek normalleştirme yapılır.

Kayıp Fonksiyonu (Loss Function)

Şimdi tahminlerimizi oluşturan olasılıkların niteliğini ölçmek için bir kayıp fonksiyonu gerekiyor. Lineer regresyonda oluğu gibi maksimum olabilirlik (maximum likelyhood) yadımıyla seçtiğimiz kayıp fonksiyonunun sağlamasını yapacağız.

Olabilirliğin Logaritması (Log-Likelihood)

Softmaks fonksiyonu $\hat{\mathbf{y}}$ vektörünü verir ve bunu verilen $x$ girdisine karşılık her sınıfın koşullu olasılığı olarak yorumlarız. Örneğin, $\hat{y}_1$ = $\hat{P}(y=\mathrm{kedi} \mid \mathbf{x})$ gibi. Modelimizin tahminleri ile gerçek durumu karşılaştırmak için özelikler bilindiğinde sınıfların ne kadar olası durduğunu kontrol ederiz. Yani $$ P(Y \mid X) = \prod_{i=1}^n P(y^{(i)} \mid x^{(i)}) $$

olasılığına veya

$$ -\log P(Y \mid X) = \sum_{i=1}^n -\log P(y^{(i)} \mid x^{(i)}) $$

olabilirliğin logaritmasının ters işaretlisine bakılır. $P(Y \mid X)$ ifadesini maksimize etmek (yani $-\log P(Y \mid X)$ ifadesini minimum yapmak) etiketi iyi tahmin etmek anlamına gelir. Buradan

$$ l = -\log P(y \mid x) = - \sum_j y_j \log \hat{y}_j. $$

kayıp fonksiyonu elde edilir. (Gösterimin sade olması için $(i)$ üst indisi atılmıştır.) Daha sonra açıklanacak sebeplerden bu bu kayıp fonksiyonuna çapraz entropi (cross-entropy) denir. Burada $\hat{y}$ bir ayrık olasılık dağılımı ve $\mathbf{y}$ bir tek aktif vektördür. Doayısıyla tüm $j$'ler üzerinden alınan toplamda biri hariç tüm toplananlar sıfır olur. Ayrıca $\hat{y}_j$ ifadeleri olasılıklar olduklarından logarıtmaları asla sıfırdan büyük değildir. Dolayısıyla, eğer $y$ değerini doğru tahmin etmişsek kayıp fonksiyonu daha fazla azaltılamaz yani sıfır olur. Yani doğru $y$ için $P(y \mid x) = 1$ olacağından kayıp fonksiyonu en küçük değerini alır. Ancak bu çoğunlukla mümkün değildir. Örneğin veri kümemizde hatalı etiketler olabilir (yanlış etiketleme gibi). Ayrıca girdilerin özellikleri çok fazla bilgi verici değilse, her örneği sınıflanırmamız mümkün olamayabilir.

Softmaks ve Türevler

Softmaks ve karşılık gelen kayıp fonksiyonu çok kullanıldığından bunların hesaplanmasını anlamakta yarar var. Eğer $o$ değerini $l$ ifadesinde yerine yazarsak ve softmaks tanımını kullarırsak

$$ l = -\sum_j y_j \log \hat{y}_j = \sum_j y_j \log \sum_k \exp(o_k) - \sum_j y_j o_j = \log \sum_k \exp(o_k) - \sum_j y_j o_j $$

elde edilir. Olup bitene daha iyi anlam verebilmek için $o$'ya göre kısmi türev alalım: $$ \partial_{o_j} l = \frac{\exp(o_j)}{\sum_k \exp(o_k)} - y_j = \mathrm{softmax}(\mathbf{o})_j - y_j = P(y = j \mid x) - y_j. $$

Yani gradiyent, modelimizin gerçek sınıfa atadığı olasılık olan $P(y \mid x)$ ile gerçek sınıf etiketi olan $y$ arasındaki farktır. Bu anlamda regresyona benzemktedir, çünkü orada da gradiyent, $y$ gözlemi ile $\hat{y}$ tahmini arasındaki farktı. Bu rastlantı değil. Üstel (exponential) olasılık dağılım ailelerinde, olabilirliğin logaritması tam olarak bu terimdir. Bu özellik sayesinde hesaplamalar pratikte çok kolaylaşır.

Cross-Entropy Loss

Now consider the case where we observe not just a single outcome but an entire distribution over outcomes. We can use the same representation as before for $y$. The only difference is that rather than a vector containing only binary entries, say $(0, 0, 1)$, we now have a generic probability vector, say $(0.1, 0.2, 0.7)$. The math that we used previously to define the loss $l$ still works out fine, just that the interpretation is slightly more general. It is the expected value of the loss for a distribution over labels.

$$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_j y_j \log \hat{y}_j. $$

This loss is called the cross-entropy loss and it is one of the most commonly used losses for multiclass classification. We can demystify the name by introducing the basics of information theory.

Information Theory Basics

Information theory deals with the problem of encoding, decoding, transmitting and manipulating information (also known as data) in as concise form as possible.

Entropy

The central idea in information theory is to quantify the information content in data. This quantity places a hard limit on our ability to compress the data. In information theory, this quantity is called the entropy of a distribution $p$, and it is captured by the following equation:

$$ H[p] = \sum_j - p(j) \log p(j). $$

One of the fundamental theorems of information theory states that in order to encode data drawn randomly from the distribution $p$, we need at least $H[p]$ "nats" to encode it. If you wonder what a "nat" is, it is the equivalent of bit but when using a code with base $e$ rather than one with base 2. One nat is $\frac{1}{\log(2)} \approx 1.44$ bit. $H[p] / 2$ is often also called the binary entropy.

Surprisal

You might be wondering what compression has to do with prediction. Imagine that we have a stream of data that we want to compress. If it is always easy for us to predict the next token, then this data is easy to compress! Take the extreme example where every token in the stream always takes the same value. That is a very boring data stream! And not only it is boring, but it is easy to predict. Because they are always the same, we do not have to transmit any information to communicate the contents of the stream. Easy to predict, easy to compress.

However if we cannot perfectly predict every event, then we might some times be surprised. Our surprise is greater when we assigned an event lower probability. For reasons that we will elaborate in the appendix, Claude Shannon settled on $\log(1/p(j)) = -\log p(j)$ to quantify one's surprisal at observing an event $j$ having assigned it a (subjective) probability $p(j)$. The entropy is then the expected surprisal when one assigned the correct probabilities (that truly match the data-generating process). The entropy of the data is then the least surprised that one can ever be (in expectation).

Cross-Entropy Revisited

So if entropy is level of surprise experienced by someone who knows the true probability, then you might be wondering, what is cross-entropy? The cross-entropy from $p$ to $q$, denoted $H(p, q)$, is the expected surprisal of an observer with subjective probabilities $q$ upon seeing data that was actually generated according to probabilities $p$. The lowest possible cross-entropy is achieved when $p=q$. In this case, the cross-entropy from $p$ to $q$ is $H(p, p)= H(p)$. Relating this back to our classification objective, even if we get the best possible predictions, we will never be perfect. Our loss is lower-bounded by the entropy given by the actual conditional distributions $P(\mathbf{y} \mid \mathbf{x})$.

Kullback-Leibler Divergence

Perhaps the most common way to measure the distance between two distributions is to calculate the Kullback-Leibler divergence $D(p\|q)$. This is simply the difference between the cross-entropy and the entropy, i.e., the additional cross-entropy incurred over the irreducible minimum value it could take:

$$ D(p\|q) = H(p, q) - H[p] = \sum_j p(j) \log \frac{p(j)}{q(j)}. $$

Note that in classification, we do not know the true $p$, so we cannot compute the entropy directly. However, because the entropy is out of our control, minimizing $D(p\|q)$ with respect to $q$ is equivalent to minimizing the cross-entropy loss.

In short, we can think of the cross-entropy classification objective in two ways: (i) as maximizing the likelihood of the observed data; and (ii) as minimizing our surprise (and thus the number of bits) required to communicate the labels.

Model Prediction and Evaluation

After training the softmax regression model, given any example features, we can predict the probability of each output category. Normally, we use the category with the highest predicted probability as the output category. The prediction is correct if it is consistent with the actual category (label). In the next part of the experiment, we will use accuracy to evaluate the model’s performance. This is equal to the ratio between the number of correct predictions and the total number of predictions.

Summary

  • We introduced the softmax operation which takes a vector and maps it into probabilities.
  • Softmax regression applies to classification problems. It uses the probability distribution of the output category in the softmax operation.
  • Cross-entropy is a good measure of the difference between two probability distributions. It measures the number of bits needed to encode the data given our model.

Exercises

  1. Show that the Kullback-Leibler divergence $D(p\|q)$ is nonnegative for all distributions $p$ and $q$. Hint: use Jensen's inequality, i.e., use the fact that $-\log x$ is a convex function.
  2. Show that $\log \sum_j \exp(o_j)$ is a convex function in $o$.
  3. We can explore the connection between exponential families and the softmax in some more depth
    • Compute the second derivative of the cross-entropy loss $l(y,\hat{y})$ for the softmax.
    • Compute the variance of the distribution given by $\mathrm{softmax}(o)$ and show that it matches the second derivative computed above.
  4. Assume that we have three classes which occur with equal probability, i.e., the probability vector is $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$.
    • What is the problem if we try to design a binary code for it? Can we match the entropy lower bound on the number of bits?
    • Can you design a better code. Hint: what happens if we try to encode two independent observations? What if we encode $n$ observations jointly?
  5. Softmax is a misnomer for the mapping introduced above (but everyone in deep learning uses it). The real softmax is defined as $\mathrm{RealSoftMax}(a, b) = \log (\exp(a) + \exp(b))$.
    • Prove that $\mathrm{RealSoftMax}(a, b) > \mathrm{max}(a, b)$.
    • Prove that this holds for $\lambda^{-1} \mathrm{RealSoftMax}(\lambda a, \lambda b)$, provided that $\lambda > 0$.
    • Show that for $\lambda \to \infty$ we have $\lambda^{-1} \mathrm{RealSoftMax}(\lambda a, \lambda b) \to \mathrm{max}(a, b)$.
    • What does the soft-min look like?
    • Extend this to more than two numbers.

Discussions