annotate toolboxes/distance_learning/mlr/separationOracle/separationOracleMRR.m @ 0:cc4b1211e677 tip

initial commit to HG from Changeset: 646 (e263d8a21543) added further path and more save "camirversion.m"
author Daniel Wolff
date Fri, 19 Aug 2016 13:07:06 +0200
parents
children
rev   line source
Daniel@0 1 function [Y, Loss] = separationOracleMRR(q, D, pos, neg, k)
Daniel@0 2 %
Daniel@0 3 % [Y,Loss] = separationOracleMRR(q, D, pos, neg, k)
Daniel@0 4 %
Daniel@0 5 % q = index of the query point
Daniel@0 6 % D = the current distance matrix
Daniel@0 7 % pos = indices of relevant results for q
Daniel@0 8 % neg = indices of irrelevant results for q
Daniel@0 9 % k = length of the list to consider (unused in MRR)
Daniel@0 10 %
Daniel@0 11 % Y is a permutation 1:n corresponding to the maximally
Daniel@0 12 % violated constraint
Daniel@0 13 %
Daniel@0 14 % Loss is the loss for Y, in this case, 1-MRR(Y)
Daniel@0 15
Daniel@0 16
Daniel@0 17 % First, sort the documents in descending order of W'Phi(q,x)
Daniel@0 18 % Phi = - (X(q) - X(x)) * (X(q) - X(x))'
Daniel@0 19
Daniel@0 20 % Sort the positive documents
Daniel@0 21 ScorePos = - D(pos,q);
Daniel@0 22 [Vpos, Ipos] = sort(full(ScorePos'), 'descend');
Daniel@0 23 Ipos = pos(Ipos);
Daniel@0 24
Daniel@0 25 % Sort the negative documents
Daniel@0 26 ScoreNeg = -D(neg,q);
Daniel@0 27 [Vneg, Ineg] = sort(full(ScoreNeg'), 'descend');
Daniel@0 28 Ineg = neg(Ineg);
Daniel@0 29
Daniel@0 30 % Now, solve the DP for the interleaving
Daniel@0 31
Daniel@0 32 numPos = length(pos);
Daniel@0 33 numNeg = length(neg);
Daniel@0 34 n = numPos + numNeg;
Daniel@0 35
Daniel@0 36 cVpos = cumsum(Vpos);
Daniel@0 37 cVneg = cumsum(Vneg);
Daniel@0 38
Daniel@0 39
Daniel@0 40 % Algorithm:
Daniel@0 41 % For each RR score in 1/1, 1/2, ..., 1/(numNeg+1)
Daniel@0 42 % Calculate maximum discriminant score for that precision level
Daniel@0 43 MRR = ((1:(numNeg+1)).^-1)';
Daniel@0 44
Daniel@0 45
Daniel@0 46 Discriminant = zeros(numNeg+1, 1);
Daniel@0 47 Discriminant(end) = numPos * cVneg(end) - numNeg * cVpos(end);
Daniel@0 48
Daniel@0 49 % For the rest of the positions, we're interleaving one more negative
Daniel@0 50 % example into the 2nd-through-last positives
Daniel@0 51 offsets = 1 + binarysearch(Vneg, Vpos(2:end));
Daniel@0 52
Daniel@0 53 % How many of the remaining positives go before Vneg(a)?
Daniel@0 54 NegsBefore = -bsxfun(@ge, offsets, (1:length(Vpos))');
Daniel@0 55
Daniel@0 56 % For the last position, all negatives come before all positives
Daniel@0 57 NegsBefore(:,numNeg+1) = numNeg;
Daniel@0 58
Daniel@0 59 Discriminant(1:numNeg) = -2 * (offsets .* Vneg - cVpos(offsets));
Daniel@0 60 Discriminant = sum(Discriminant) - cumsum(Discriminant) + Discriminant;
Daniel@0 61
Daniel@0 62
Daniel@0 63 % Normalize discriminant scores
Daniel@0 64 Discriminant = Discriminant / (numPos * numNeg);
Daniel@0 65 [s, x] = max(Discriminant - MRR);
Daniel@0 66
Daniel@0 67 % Now we know that there are x-1 relevant docs in the max ranking
Daniel@0 68 % Construct Y from NegsBefore(x,:)
Daniel@0 69
Daniel@0 70 Y = nan * ones(n,1);
Daniel@0 71 Y((1:numPos)' + sum(NegsBefore(:,x:end),2)) = Ipos;
Daniel@0 72 Y(isnan(Y)) = Ineg;
Daniel@0 73
Daniel@0 74 % Compute loss for this list
Daniel@0 75 Loss = 1 - MRR(x);
Daniel@0 76 end
Daniel@0 77