How does Linear Regression classification work? I am currently trying to understand the following:

Logistic regression is a probabilistic, linear classifier. It is parametrized by a weight matrix $W$ and a bias vector $b$. Classification is done by projecting data points onto a set of hyperplanes, the distance to which reflects a class membership probability.
Mathematically, this can be written as:
\begin{align}
P(Y=i|x, W,b) &= softmax_i(W x + b) \\
              &= \frac {e^{W_i x + b_i}} {\sum_j e^{W_j x + b_j}}
\end{align}

Source: http://www.deeplearning.net/tutorial/logreg.html#logreg
What I think I've understood
We have the following scenario:


*

*When you have $p$ points in $\mathbb{R}^n$ from which you know the class $c(p_i) \in [1 ... m]$  (for $i \in 1..p$) of. This is our training set.

*We have other points that we want to classify.

*We always do one check at a time. For a given point $p$ we check "What is the probability of $p$ being a point of class $i$?" and our classification will be the maximum of that. So we can reduce the problem of classifying a point in $\mathbb{R}^n$ on $m$ classes to one class.

*For the one-class-classification of a point in $\mathbb{R}^2$ we use a sigmoid function $S_a(t) = \frac{1}{1+e^{-at}}$ where $a$ is a parameter that has to be learned. This means we choose $a$ such that an error gets minimized for the training set. The error is probably the sum of all distances between the points in the training set to the function $S_a$.

*Softmax is similar to the sigmoid functions


My Questions


*

*Is what I have written above correct?

*In the cited formula:


*

*Is $i$ the class we want to get the probability of that $x$ (the point we want to classify) might belong to?

*How do we calculate $W$ and $b$?

*The sigmoid functions map $\mathbb{R} \rightarrow \mathbb{R}$. From which space to which space does softmax map to?

*In this video by Andrew Ng he uses $g(\theta^T x) = g(z) = \frac{1}{1+e^{-z}}$ where $\theta$ has to be learned. Is that equivalent to the softmax function approach? What is the advantage of Softmax? (The approach from Andrew Ng seems to be much simpler.)


 A: 
We always do one check at a time.

We can classify one example $x$ at a time, but we wouldn't consider one candidate class $i$ at a time. For each $i$, I suppose you could isolate the $i$th row of $W$ and the $i$th element of the column vector $b$, called $W_i$ and $b_i$, and compute $W_ix+b_i$. Then you want to maximize this quantity over all $i$. But in practice, you might as well compute all of $Wx+b$ at once.
(And depending on the software framework, it may also make sense to classify multiple examples in parallel.)

For a given point $p$ we check "What is the probability of $p$ being a point of class $i$?" and our classification will be the maximum of that.

You could do that, but if you only want to compute the most probable label, you don't actually have to compute any $P$. The denominator is a constant across classes, so it doesn't matter, and the exponential function is strictly increasing, so it doesn't change the order of the scores. So it's equivalent to find the maximum coordinate of $Wx+b$.

So we can reduce the problem of classifying a point in $\mathbb{R}^n$ on $m$ classes to one class.

Well, in this formulation, you still have to compute the row values for all classes. If for some test example, you just want to know whether the classifier predicts that the class is $42$, it's not enough to compute $W_{42}x+b_{42}$. No matter how large that value might be, you still need to know the rest of $Wx+b$, because $W_{79}x+b_{79}$ might be even larger.

For the one-class-classification ... The error is probably the sum of all distances of the points in the training set to the function $S_a$

That would be an $\ell_1$ loss over the probability vector, which doesn't make too much sense. See below about training.

Is $i$ the class we want to get the probability of that $x$ (the point we want to classify) might belong to?

Yep

How do we calculate $W$ and $b$?

That's training! First, you have to specify the loss function you care about, and an optimization algorithm that will minimize the empirical loss over your training data. In order to interpret the softmax outputs as probabilities, as you do above, the loss function should be something like a logistic loss, and the algorithm can be some variant of gradient descent. See the recommendations in the following sections of the tutorial, http://www.deeplearning.net/tutorial/logreg.html#defining-a-loss-function

The sigmoid functions map $\mathbb{R} \rightarrow \mathbb{R}$. From which space to which space does softmax map to?

The softmax function maps from $\mathbb R^m$ to the space of probability distributions on the set of classes $\{1,\ldots,m\}$. This is a subspace of the $m$-dimensional unit cube, $[0,1]^m$, where the coordinates (probabilities) add up to $1$. In fact, softmax never outputs a probability of $0$ or $1$, so you could also use the open cube $(0,1)^m$ as the range. In practice, the important thing is that it's a subset of $\mathbb R^m$.

In this video by Andrew Ng he uses $g(\theta^T x) = g(z) = \frac{1}{1+e^{-z}}$ where $\theta$ has to be learned. Is that equivalent to the softmax function approach? What is the advantage of softmax? (The approach from Andrew Ng seems to be much simpler.)

That video is no longer available, but it sounds like he's doing binary classification. The problem is simpler, so it makes sense that the solution is simpler.
