| 93 | |
| 94 | |
| 95 | class ThreeClassClassifierProblem: |
| 96 | # Now we arrive at the meat of this example program. To use the |
| 97 | # dlib.solve_structural_svm_problem() routine you need to define an object |
| 98 | # which tells the structural SVM solver what to do for your problem. In |
| 99 | # this example, this is done by defining the ThreeClassClassifierProblem |
| 100 | # object. Before we get into the details, we first discuss some background |
| 101 | # information on structural SVMs. |
| 102 | # |
| 103 | # A structural SVM is a supervised machine learning method for learning to |
| 104 | # predict complex outputs. This is contrasted with a binary classifier |
| 105 | # which makes only simple yes/no predictions. A structural SVM, on the |
| 106 | # other hand, can learn to predict complex outputs such as entire parse |
| 107 | # trees or DNA sequence alignments. To do this, it learns a function F(x,y) |
| 108 | # which measures how well a particular data sample x matches a label y, |
| 109 | # where a label is potentially a complex thing like a parse tree. However, |
| 110 | # to keep this example program simple we use only a 3 category label output. |
| 111 | # |
| 112 | # At test time, the best label for a new x is given by the y which |
| 113 | # maximizes F(x,y). To put this into the context of the current example, |
| 114 | # F(x,y) computes the score for a given sample and class label. The |
| 115 | # predicted class label is therefore whatever value of y which makes F(x,y) |
| 116 | # the biggest. This is exactly what predict_label() does. That is, it |
| 117 | # computes F(x,0), F(x,1), and F(x,2) and then reports which label has the |
| 118 | # biggest value. |
| 119 | # |
| 120 | # At a high level, a structural SVM can be thought of as searching the |
| 121 | # parameter space of F(x,y) for the set of parameters that make the |
| 122 | # following inequality true as often as possible: |
| 123 | # F(x_i,y_i) > max{over all incorrect labels of x_i} F(x_i, y_incorrect) |
| 124 | # That is, it seeks to find the parameter vector such that F(x,y) always |
| 125 | # gives the highest score to the correct output. To define the structural |
| 126 | # SVM optimization problem precisely, we first introduce some notation: |
| 127 | # - let PSI(x,y) == the joint feature vector for input x and a label y |
| 128 | # - let F(x,y|w) == dot(w,PSI(x,y)). |
| 129 | # (we use the | notation to emphasize that F() has the parameter vector |
| 130 | # of weights called w) |
| 131 | # - let LOSS(idx,y) == the loss incurred for predicting that the |
| 132 | # idx-th training sample has a label of y. Note that LOSS() |
| 133 | # should always be >= 0 and should become exactly 0 when y is the |
| 134 | # correct label for the idx-th sample. Moreover, it should notionally |
| 135 | # indicate how bad it is to predict y for the idx'th sample. |
| 136 | # - let x_i == the i-th training sample. |
| 137 | # - let y_i == the correct label for the i-th training sample. |
| 138 | # - The number of data samples is N. |
| 139 | # |
| 140 | # Then the optimization problem solved by a structural SVM using |
| 141 | # dlib.solve_structural_svm_problem() is the following: |
| 142 | # Minimize: h(w) == 0.5*dot(w,w) + C*R(w) |
| 143 | # |
| 144 | # Where R(w) == sum from i=1 to N: 1/N * sample_risk(i,w) and |
| 145 | # sample_risk(i,w) == max over all |
| 146 | # Y: LOSS(i,Y) + F(x_i,Y|w) - F(x_i,y_i|w) and C > 0 |
| 147 | # |
| 148 | # You can think of the sample_risk(i,w) as measuring the degree of error |
| 149 | # you would make when predicting the label of the i-th sample using |
| 150 | # parameters w. That is, it is zero only when the correct label would be |
| 151 | # predicted and grows larger the more "wrong" the predicted output becomes. |
| 152 | # Therefore, the objective function is minimizing a balance between making |