Softmax Regression

In these notes, we describe the '''Softmax regression''' model.  This model generalizes logistic regression to

This will be useful for such problems as MNIST digit classification, where the goal is to distinguish between 10 different

numerical digits.  Softmax regression is a supervised learning algorithm, but we will later be

of <math>m</math> labeled examples, where the input features are <math>x^{(i)} \in \Re^{n+1}</math>.   

With logistic regression, we were in the binary classification setting, so the labels  

were <math>y^{(i)} \in \{0,1\}</math>.  Our hypothesis took the form:

we now have that <math>y^{(i)} \in \{1, 2, \ldots, k\}</math>. (Note that

our convention will be to index the classes starting from 1, rather than from 0.) For example,

the probability that <math>p(y=j | x)</math> for each value of <math>j = 1, \ldots, k</math>.

I.e., we want to estimate the probability of the class label taking

us our <math>k</math> estimated probabilities. Concretely, our hypothesis

h_\theta(x^{(i)}) =

p(y^{(i)} = 1 | x^{(i)}; \theta) \\

p(y^{(i)} = 2 | x^{(i)}; \theta) \\

p(y^{(i)} = k | x^{(i)}; \theta)

\frac{1}{ \sum_{j=1}^{k}{e^{ \theta_j^T x^{(i)} }} }

Here <math>\theta_1, \theta_2, \ldots, \theta_k \in \Re^{n+1}</math> are the

parameters of our model.   

Notice that

the term <math>\frac{1}{ \sum_{j=1}^{k}{e^{ \theta_j^T x^{(i)} }} } </math>

normalizes the distribution, so that it sums to one.  

We now describe the cost function that we'll use for softmax regression.  In the equation below, <math>1\{\cdot\}</math> is

the '''indicator function,''' so that <math>1\{\hbox{a true statement}\}=1</math>, and <math>1\{\hbox{a false statement}\}=0</math>.

For example, <math>1\{2+2=4\}</math> evaluates to 1; whereas <math>1\{1+1=5\}</math> evaluates to 0. Our cost function will be:

J(\theta) = - \frac{1}{m} \left[ \sum_{i=1}^{m} \sum_{j=1}^{k} 1\left\{y^{(i)} = j\right\} \log \frac{e^{\theta_j^T x^{(i)}}}{\sum_{l=1}^k e^{ \theta_l^T x^{(i)} }}\right]

J(\theta) &= -\frac{1}{m} \left[ \sum_{i=1}^m  (1-y^{(i)}) \log (1-h_\theta(x^{(i)})) + y^{(i)} \log h_\theta(x^{(i)}) \right] \\

&= - \frac{1}{m} \left[ \sum_{i=1}^{m} \sum_{j=0}^{1} 1\left\{y^{(i)} = j\right\} \log p(y^{(i)} = j | x^{(i)} ; \theta) \right]

p(y^{(i)} = j | x^{(i)} ; \theta) = \frac{e^{\theta_j^T x^{(i)}}}{\sum_{l=1}^k e^{ \theta_l^T x^{(i)}} }

There is no known closed-form way to solve for the minimum of <math>J(\theta)</math>, and thus as usual we'll resort to an iterative

\nabla_{\theta_j} J(\theta) = - \frac{1}{m} \sum_{i=1}^{m}{ \left[ x^{(i)} \left( 1\{ y^{(i)} = j\}  - p(y^{(i)} = j | x^{(i)}; \theta) \right) \right]  }

<math>p(y^{(i)} = j | x^{(i)} ; \theta) = e^{\theta_j^T x^{(i)}}/(\sum_{l=1}^k e^{ \theta_l^T x^{(i)}} )</math>.  !-->

 

the partial derivative of <math>J(\theta)</math> with respect to the <math>l</math>-th element of <math>\theta_j</math>.

 

Armed with this formula for the derivative, one can then plug it into an algorithm such as gradient descent, and have it

minimize <math>J(\theta)</math>.  For example, with the standard implementation of gradient descent, on each iteration

we would perform the update <math>\theta_j := \theta_j - \alpha \nabla_{\theta_j} J(\theta)</math> (for each <math>j=1,\ldots,k</math>).

Softmax regression has an unusual property that it has a "redundant" set of parameters.  To explain what this means,  

from it, so that every <math>\theta_j</math> is now replaced with <math>\theta_j - \psi</math>  

(for every <math>j=1, \ldots, k</math>).  Our hypothesis

&= \frac{e^{(\theta_j-\psi)^T x^{(i)}}}{\sum_{l=1}^k e^{ (\theta_l-\psi)^T x^{(i)}}}  \\

&= \frac{e^{\theta_j^T x^{(i)}} e^{-\psi^Tx^{(i)}}}{\sum_{l=1}^k e^{\theta_l^T x^{(i)}} e^{-\psi^Tx^{(i)}}} \\

&= \frac{e^{\theta_j^T x^{(i)}}}{\sum_{l=1}^k e^{ \theta_l^T x^{(i)}}}.

fit to the data, there are multiple parameter settings that give rise to exactly

the same hypothesis function <math>h_\theta</math> mapping from inputs <math>x</math>

to the predictions.  

setting of the parameters <math>(\theta_1, \theta_2,\ldots, \theta_k)</math>,

\theta_k - \psi)</math> for any value of <math>\psi</math>.  Thus, the

minimizer of <math>J(\theta)</math> is not unique.  (Interestingly,  

<math>J(\theta)</math> is still convex, and thus gradient descent will

not run into a local optima problems.  But the Hessian is singular/non-invertible,

which causes a straightforward implementation of Newton's method to run into

numerical problems.)  

replace <math>\theta_1</math> with <math>\theta_1 - \psi = \vec{0}</math> (the vector of all

of our hypothesis.  Indeed, rather than optimizing over the <math>k(n+1)</math>

parameters <math>(\theta_1, \theta_2,\ldots, \theta_k)</math> (where

<math>\theta_j \in \Re^{n+1}</math>), one could instead set <math>\theta_1 =

\vec{0}</math> and optimize only with respect to the <math>(k-1)(n+1)</math>

remaining parameters, and this would work fine.  

all the parameters <math>(\theta_1, \theta_2,\ldots, \theta_n)</math>, without

arbitrarily setting one of them to zero.  But we will

== Weight Decay ==

<math>\textstyle \frac{\lambda}{2} \sum_{i=1}^k \sum_{j=0}^{n} \theta_{ij}^2</math>

J(\theta) = - \frac{1}{m} \left[ \sum_{i=1}^{m} \sum_{j=1}^{k} 1\left\{y^{(i)} = j\right\} \log \frac{e^{\theta_j^T x^{(i)}}}{\sum_{l=1}^k e^{ \theta_l^T x^{(i)} }} \right]

               + \frac{\lambda}{2} \sum_{i=1}^k \sum_{j=0}^n \theta_{ij}^2

unique solution.  The Hessian is now invertible, and because <math>J(\theta)</math> is  

convex, algorithms such as gradient descent, L-BFGS, etc. are guaranteed

To apply an optimization algorithm, we also need the derivative of this

new definition of <math>J(\theta)</math>.  One can show that the derivative is:

\nabla_{\theta_j} J(\theta) = - \frac{1}{m} \sum_{i=1}^{m}{ \left[ x^{(i)} ( 1\{ y^{(i)} = j\}  - p(y^{(i)} = j | x^{(i)}; \theta) ) \right]  } + \lambda \theta_j

By minimizing <math>J(\theta)</math> with respect to <math>\theta</math>, we will have a working implementation of softmax regression.

In the special case where <math>k = 2</math>, one can show that softmax regression reduces to logistic regression.

This shows that softmax regression is a generalization of logistic regression.  Concretely, when <math>k=2</math>,

the softmax regression hypothesis outputs

h_\theta(x) &=

is overparameterized and setting <math>\psi = \theta_1</math>,

we can subtract <math>\theta_1</math> from each of the two parameters, giving us

Thus, replacing <math>\theta_2-\theta_1</math> with a single parameter vector <math>\theta'</math>, we find

== Softmax Regression vs. k Binary Classifiers ==

<math>k</math> types of music that you are trying to recognize.  Should you use a

(If there're also some examples that are none of the above four classes,

then you can set <math>k=5</math> in softmax regression, and also have a fifth, "none of the above," class.)

If however your categories are has_vocals, dance, soundtrack, pop, then the

music that comes from a soundtrack and in addition has vocals.  In this case, it

would be more appropriate to build 4 binary logistic regression classifiers.

This way, for each new musical piece, your algorithm can separately decide whether