Videos
To answer your questions directly:
- A loss function is a scoring function used to evaluate how well a given boundary separates the training data. Each loss function represents a different set of priorities about what the scoring criteria are. In particular, the hinge loss function doesn't care about correctly classified points as long as they're correct, but imposes a penalty for incorrectly classified points which is directly proportional to how far away they are on the wrong side of the boundary in question.
A boundary's loss score is computed by seeing how well it classifies each training point, computing each training point's loss value (which is a function of its distance from the boundary), then adding up the results.
By plotting how a single training point's loss score would vary based on how well it is classified, you can get a feel for the loss function's priorities. That's what your graphs are showing— the size of the penalty that would hypothetically be assigned to a single point based on how confidently it is classified or misclassified. They're pictures of the scoring rubric, not calculations of an actual score. [See diagram below!]
At least conceptually, you minimize the loss for a dataset by considering all possible linear boundaries, computing their loss scores, and picking the boundary whose loss score is smallest. Remember that the plots just show how an individual point would be scored in each case based on how accurately it is classified.
Interpret loss plots as follows: The horizontal axis corresponds to
, which is how accurately a point is classified. Positive values correspond to increasingly confident correct classifications, while negative values correspond to increasingly confident incorrect classifications. (Or, geometrically, 
is the distance of the point from the boundary, and we prefer boundaries that separate points as widely as possible.) The vertical axis is the magnitude of the penalty. (They're simplified in the sense that they're showing the scoring rubric for a single point; they're not showing you the computed total loss for various boundaries as a function of which boundary you pick.)
Details follow.
The linear SVM problem is the problem of finding a line (or plane, etc.) in space that separates points of one class from points of the other class by the widest possible margin. You want to find, out of all possible planes, the one that separates the points best.
If it helps to think geometrically, a plane can be completely defined by two parameters: a vector
perpendicular to the plane (which tells you the plane's orientation) and an offset 
(which tells you how far it is from the origin). Each choice of 
is therefore a choice of plane. Another helpful geometric fact for intuition: if 
is some plane and 
is a point in space, then 
is the distance between the plane and the point (!). [Nitpick: If
is not a unit vector, then this formula actually gives a multiple of a distance, but the constants don't matter here.] That planar-distance formula
is useful because it defines a measurement scheme throughout all space: points lying on the plane have a value of 0; points far away on one side of the boundary have increasingly positive value, and points far away on the other side of the boundary have increasingly negative value.We have two classes of points. By convention, we'll call one of the classes positive and the other negative. An effective decision boundary will be one that assigns very positive planar-distance values to positive points and very negative planar-distance values to negative points. In formal terms, if
denotes the class of the 
th training point and 
denotes its position, then what we want is for 
and 
to have the same sign and for 
to be large in magnitude. A loss function is a way of scoring how well the boundary assigns planar-distance values that match each point's actual class. A loss function is always a function
of two arguments— for the first argument we plug in the true class 
of the point in question, and for the second 
we plug in the planar distance value our plane assigns to it. The total loss for the planar boundary is the sum of the losses for each of the training points.Based on our choice of loss function, we might express a preference that points be classified correctly but that we don't care about the magnitude of the planar-distance value if it's beyond, say, 1000; or we might choose a loss function which allows some points to be misclassified as long as the rest are very solidly classified, etc.
Your graphs show how different loss functions behave on a single point whose class
is fixed and whose planar distance 
varies (
runs along the horizontal axis). This can give you an idea of what the loss function is prioritizing. (Under this scheme, by the way, positive values of 
correspond to increasingly confident correct classification, and negative values of 
correspond to increasingly confident incorrect classification.) As a concrete example, the hinge loss function is a mathematical formulation of the following preference:
Hinge loss preference: When evaluating planar boundaries that separate positive points from negative points, it is irrelevant how far away from the boundary the correctly classified points are. However, misclassified points incur a penalty that is directly proportional to how far they are on the wrong side of the boundary.
Formally, this preference falls out of the fact that a correctly classified point incurs zero loss once its planar distance
is greater than 1. On the other hand, it incurs a linear penalty directly proportional to the planar distance 
as the classification becomes more badly incorrect.Computing the loss value means computing the value of the loss for a particular set of training points and a particular boundary. Minimizing the loss means finding, for a particular set of training data, the boundary for which the loss value is minimal.
For a dataset as in the 2D picture provided, first draw any linear boundary; call one side the positive (or red square) side, and the other the negative (or blue circle) side. You can compute the loss of the boundary by first measuring the planar distance values of each point; here, the signed distance between each training point and the boundary. Points on the positive side have positive
values and points on the negative side have negative values. Next, each point contributes to the total loss: 
. Compute the loss for each of the points now that you've computed 
for each point and you know 
whether the point is a red square or blue circle. Add them all up to compute the overall loss. The best boundary is the one that has the lowest loss on this dataset out of all possible linear boundaries you could draw. (Time permitting, I'll add illustrations for all of this.)
If the training data can be separated by a linear boundary, then any boundary which does so will have a hinge loss of zero— the lowest achievable value. Based on our preferences as expressed by hinge loss, all such boundaries tie for first place.
Only if the training data is not linearly separable will the best boundary have a nonzero (positive, worse) hinge loss. In that case, the hinge loss preference will prefer to choose the boundary so that whichever misclassified points are not too far on the wrong side.
Addendum: As you can see from the shape of the curves, the loss functions in your picture express the following scoring rubrics:
- Zero-one loss
: Being misclassified is uniformly bad— points on the wrong side of the boundary get the same size penalty regardless of how far on the wrong side they are. Similarly, all points on the correct side of the boundary get no penalty and no special bonus, even if they're very far on the correct side. - Exponential loss
: The more correct you are, the better. But once you're on the correct side of the boundary, it gets less and less important that you be far away from the boundary. On the other hand, the further you are on the wrong side of the boundary, the more exponentially urgent of a problem it is. 
: Same, qualitatively, as previous function.- Hinge loss
: If you're correctly classified beyond the margin (
) then it's irrelevant just how far on the correct side you are. On the other hand, if you're within the margin or on the incorrect side, you get a penalty directly proportional to how far you are on the wrong side.
The hinge function is convex and the problem of its minimization can be cast as a quadratic program:
$\quad t_i \geq 1 - y_i(wx_i + b) , \forall i=1,\ldots,m
\quad t_i \geq 0 , \forall i=1,\ldots,m$
or in conic form
$\quad t_i \geq y_i(wx_i + b) , \forall i=1,\ldots,m
\quad t_i \geq 0 , \forall i=1,\ldots,m
(2,z,w) \in Q_r^m$
where 
is the rotated cone.
You can solve this problem either using a QP /SOCP solver, as MOSEK, or by some specialize algorithms that you can find in literature. Note that the minimum is not necessarily in zero, because of the interplay between the norm of 
and the blue side of the objective function.
In the second picture, every feasible solution is a line. An optimal one will balance the separation of the two classes, given by the blue term and the norm.
As for references, searching on Scholar Google seems quite ok. But even following the references from Wikipedia it is already a first steps.
You can draw some inspiration from one of my recent blog post:
http://blog.mosek.com/2014/03/swissquant-math-challenge-on-lasso.html
it is a similar problem. Also, for more general concept on conic optimization and regression you can check the classical book of Boyd.