comparison toolboxes/distance_learning/mlr/separationOracle/separationOracleKNN.m @ 0:e9a9cd732c1e tip

first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:e9a9cd732c1e
1 function [Y, Loss] = separationOracleKNN(q, D, pos, neg, k)
2 %
3 % [Y,Loss] = separationOracleKNN(q, D, pos, neg, k)
4 %
5 % q = index of the query point
6 % D = the current distance matrix
7 % pos = indices of relevant results for q
8 % neg = indices of irrelevant results for q
9 % k = length of the list to consider
10 %
11 % Y is a permutation 1:n corresponding to the maximally
12 % violated constraint
13 %
14 % Loss is the loss for Y, in this case, 1-Prec@k(Y)
15
16
17 % First, sort the documents in descending order of W'Phi(q,x)
18 % Phi = - (X(q) - X(x)) * (X(q) - X(x))'
19
20 % Sort the positive documents
21 ScorePos = - D(pos,q);
22 [Vpos, Ipos] = sort(full(ScorePos'), 'descend');
23 Ipos = pos(Ipos);
24
25 % Sort the negative documents
26 ScoreNeg = - D(neg,q);
27 [Vneg, Ineg] = sort(full(ScoreNeg'), 'descend');
28 Ineg = neg(Ineg);
29
30 % Now, solve the DP for the interleaving
31
32 numPos = length(pos);
33 numNeg = length(neg);
34 n = numPos + numNeg;
35
36 cVpos = cumsum(Vpos);
37 cVneg = cumsum(Vneg);
38
39
40 % If we don't have enough positive (or negative) examples, scale k down
41 k = min([k, numPos, numNeg]);
42
43 % Algorithm:
44 % For each precision score in 0, 1/k, 2/k, ... 1
45 % Calculate maximum discriminant score for that precision level
46 KNN = (0:(1/k):1)' > 0.5;
47 Discriminant = zeros(k+1, 1);
48 NegsBefore = zeros(numPos,k+1);
49
50 % For 0 precision, all positives go after the first k negatives
51
52 NegsBefore(:,1) = k + binarysearch(Vpos, Vneg(k+1:end));
53 Discriminant(1) = Vpos * (numNeg - 2 * NegsBefore(:,1)) + numPos * cVneg(end) ...
54 - 2 * sum(cVneg(NegsBefore((NegsBefore(:,1) > 0),1)));
55
56
57
58 % For precision (a-1)/k, swap the (a-1)'th positive doc
59 % into the top (k-a) negative docs
60
61 for a = 2:(k+1)
62 NegsBefore(:,a) = NegsBefore(:,a-1);
63
64 % We have a-1 positives, and k - (a-1) negatives
65 NegsBefore(a-1, a) = binarysearch(Vpos(a-1), Vneg(1:(k-a+1)));
66
67 % There were NegsBefore(a-1,a-1) negatives before (a-1)
68 % Now there are NegsBefore(a,a-1)
69
70 Discriminant(a) = Discriminant(a-1) ...
71 + 2 * (NegsBefore(a-1,a-1) - NegsBefore(a-1,a)) * Vpos(a-1);
72
73 if NegsBefore(a-1,a-1) > 0
74 Discriminant(a) = Discriminant(a) + 2 * cVneg(NegsBefore(a-1,a-1));
75 end
76 if NegsBefore(a-1,a) > 0
77 Discriminant(a) = Discriminant(a) - 2 * cVneg(NegsBefore(a-1,a));
78 end
79 end
80
81 % Normalize discriminant scores
82 Discriminant = Discriminant / (numPos * numNeg);
83 [s, x] = max(Discriminant - KNN);
84
85 % Now we know that there are x-1 relevant docs in the max ranking
86 % Construct Y from NegsBefore(x,:)
87
88 Y = nan * ones(n,1);
89 Y((1:numPos)' + NegsBefore(:,x)) = Ipos;
90 if sum(isnan(Y)) ~= length(Ineg)
91 keyboard;
92 end
93 Y(isnan(Y)) = Ineg;
94
95 % Compute loss for this list
96 Loss = 1 - KNN(x);
97 end
98