Understanding Machine Learning: From Theory to Algorithms

242 Multiclass, Ranking, and Complex Prediction Problems

equivalent to solving the problem

argmin

v∈V

∑r

i=1

(αivi+βiD(vi)),

whereαi=−〈w,xi〉andβi=yi/G(y,y). We can think of this problem a little

bit differently by defining a matrixA∈Rr,rwhere

Ai,j=jαi+D(j)βi.

Now, let us think about eachjas a “worker,” eachias a “task,” andAi,jas

the cost of assigning taskito workerj. With this view, the problem of finding

vbecomes the problem of finding an assignment of the tasks to workers of

minimal cost. This problem is called “the assignment problem” and can be solved

efficiently. One particular algorithm is the “Hungarian method” (Kuhn 1955).

Another way to solve the assignment problem is using linear programming. To

do so, let us first write the assignment problem as

argmin

B∈Rr,r+

∑r

i,j=1

Ai,jBi,j (17.9)

s.t. ∀i∈[r],

∑r

j=1

Bi,j= 1

∀j∈[r],

∑r

i=1

Bi,j= 1

∀i,j, Bi,j∈{ 0 , 1 }

A matrixBthat satisfies the constraints in the preceding optimization problem

is called a permutation matrix. This is because the constraints guarantee that

there is at most a single entry of each row that equals 1 and a single entry of each

column that equals 1. Therefore, the matrixBcorresponds to the permutation

v∈Vdefined byvi=jfor the single indexjthat satisfiesBi,j= 1.

The preceding optimization is still not a linear program because of the com-

binatorial constraintBi,j∈ { 0 , 1 }. However, as it turns out, this constraint is

redundant – if we solve the optimization problem while simply omitting the

combinatorial constraint, then we are still guaranteed that there is an optimal

solution that will satisfy this constraint. This is formalized later.

Denote〈A,B〉=

∑

i,jAi,jBi,j. Then, Equation (17.9) is the problem of mini-

mizing〈A,B〉such thatBis a permutation matrix.

A matrixB∈Rr,ris calleddoubly stochasticif all elements ofBare non-

negative, the sum of each row ofBis 1, and the sum of each column ofBis 1.

Therefore, solving Equation (17.9) without the constraintsBi,j∈ { 0 , 1 }is the

problem

argmin

B∈Rr,r

〈A,B〉 s.t. B is a doubly stochastic matrix. (17.10)