Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/PolysemousTraining.cpp
1 /**
2 * Copyright (c) 2015-present, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD+Patents license found in the
6 * LICENSE file in the root directory of this source tree.
7 */
8
9 #include "PolysemousTraining.h"
10
11 #include <cstdlib>
12 #include <cmath>
13 #include <cstring>
14
15 #include <algorithm>
16
17 #include "utils.h"
18 #include "hamming.h"
19
20 #include "FaissAssert.h"
21
22 /*****************************************
23 * Mixed PQ / Hamming
24 ******************************************/
25
26 namespace faiss {
27
28 /****************************************************
29 * Optimization code
30 ****************************************************/
31
32
33 SimulatedAnnealingParameters::SimulatedAnnealingParameters ()
34 {
35 // set some reasonable defaults for the optimization
36 init_temperature = 0.7;
37 temperature_decay = pow (0.9, 1/500.);
38 // reduce by a factor 0.9 every 500 it
39 n_iter = 500000;
40 n_redo = 2;
41 seed = 123;
42 verbose = 0;
43 only_bit_flips = false;
44 init_random = false;
45 }
46
47 // what would the cost update be if iw and jw were swapped?
48 // default implementation just computes both and computes the difference
49 double PermutationObjective::cost_update (
50 const int *perm, int iw, int jw) const
51 {
52 double orig_cost = compute_cost (perm);
53
54 std::vector<int> perm2 (n);
55 for (int i = 0; i < n; i++)
56 perm2[i] = perm[i];
57 perm2[iw] = perm[jw];
58 perm2[jw] = perm[iw];
59
60 double new_cost = compute_cost (perm2.data());
61 return new_cost - orig_cost;
62 }
63
64
65
66
67 SimulatedAnnealingOptimizer::SimulatedAnnealingOptimizer (
68 PermutationObjective *obj,
69 const SimulatedAnnealingParameters &p):
70 SimulatedAnnealingParameters (p),
71 obj (obj),
72 n(obj->n),
73 logfile (nullptr)
74 {
75 rnd = new RandomGenerator (p.seed);
76 FAISS_THROW_IF_NOT (n < 100000 && n >=0 );
77 }
78
79 SimulatedAnnealingOptimizer::~SimulatedAnnealingOptimizer ()
80 {
81 delete rnd;
82 }
83
84 // run the optimization and return the best result in best_perm
85 double SimulatedAnnealingOptimizer::run_optimization (int * best_perm)
86 {
87 double min_cost = 1e30;
88
89 // just do a few runs of the annealing and keep the lowest output cost
90 for (int it = 0; it < n_redo; it++) {
91 std::vector<int> perm(n);
92 for (int i = 0; i < n; i++)
93 perm[i] = i;
94 if (init_random) {
95 for (int i = 0; i < n; i++) {
96 int j = i + rnd->rand_int (n - i);
97 std::swap (perm[i], perm[j]);
98 }
99 }
100 float cost = optimize (perm.data());
101 if (logfile) fprintf (logfile, "\n");
102 if(verbose > 1) {
103 printf (" optimization run %d: cost=%g %s\n",
104 it, cost, cost < min_cost ? "keep" : "");
105 }
106 if (cost < min_cost) {
107 memcpy (best_perm, perm.data(), sizeof(perm[0]) * n);
108 min_cost = cost;
109 }
110 }
111 return min_cost;
112 }
113
114 // perform the optimization loop, starting from and modifying
115 // permutation in-place
116 double SimulatedAnnealingOptimizer::optimize (int *perm)
117 {
118 double cost = init_cost = obj->compute_cost (perm);
119 int log2n = 0;
120 while (!(n <= (1 << log2n))) log2n++;
121 double temperature = init_temperature;
122 int n_swap = 0, n_hot = 0;
123 for (int it = 0; it < n_iter; it++) {
124 temperature = temperature * temperature_decay;
125 int iw, jw;
126 if (only_bit_flips) {
127 iw = rnd->rand_int (n);
128 jw = iw ^ (1 << rnd->rand_int (log2n));
129 } else {
130 iw = rnd->rand_int (n);
131 jw = rnd->rand_int (n - 1);
132 if (jw == iw) jw++;
133 }
134 double delta_cost = obj->cost_update (perm, iw, jw);
135 if (delta_cost < 0 || rnd->rand_float () < temperature) {
136 std::swap (perm[iw], perm[jw]);
137 cost += delta_cost;
138 n_swap++;
139 if (delta_cost >= 0) n_hot++;
140 }
141 if (verbose > 2 || (verbose > 1 && it % 10000 == 0)) {
142 printf (" iteration %d cost %g temp %g n_swap %d "
143 "(%d hot) \r",
144 it, cost, temperature, n_swap, n_hot);
145 fflush(stdout);
146 }
147 if (logfile) {
148 fprintf (logfile, "%d %g %g %d %d\n",
149 it, cost, temperature, n_swap, n_hot);
150 }
151 }
152 if (verbose > 1) printf("\n");
153 return cost;
154 }
155
156
157
158
159
160 /****************************************************
161 * Cost functions: ReproduceDistanceTable
162 ****************************************************/
163
164
165
166
167
168
169 static inline int hamming_dis (uint64_t a, uint64_t b)
170 {
171 return __builtin_popcountl (a ^ b);
172 }
173
174 namespace {
175
176 /// optimize permutation to reproduce a distance table with Hamming distances
177 struct ReproduceWithHammingObjective : PermutationObjective {
178 int nbits;
179 double dis_weight_factor;
180
181 static double sqr (double x) { return x * x; }
182
183
184 // weihgting of distances: it is more important to reproduce small
185 // distances well
186 double dis_weight (double x) const
187 {
188 return exp (-dis_weight_factor * x);
189 }
190
191 std::vector<double> target_dis; // wanted distances (size n^2)
192 std::vector<double> weights; // weights for each distance (size n^2)
193
194 // cost = quadratic difference between actual distance and Hamming distance
195 double compute_cost(const int* perm) const override {
196 double cost = 0;
197 for (int i = 0; i < n; i++) {
198 for (int j = 0; j < n; j++) {
199 double wanted = target_dis[i * n + j];
200 double w = weights[i * n + j];
201 double actual = hamming_dis(perm[i], perm[j]);
202 cost += w * sqr(wanted - actual);
203 }
204 }
205 return cost;
206 }
207
208
209 // what would the cost update be if iw and jw were swapped?
210 // computed in O(n) instead of O(n^2) for the full re-computation
211 double cost_update(const int* perm, int iw, int jw) const override {
212 double delta_cost = 0;
213
214 for (int i = 0; i < n; i++) {
215 if (i == iw) {
216 for (int j = 0; j < n; j++) {
217 double wanted = target_dis[i * n + j], w = weights[i * n + j];
218 double actual = hamming_dis(perm[i], perm[j]);
219 delta_cost -= w * sqr(wanted - actual);
220 double new_actual =
221 hamming_dis(perm[jw], perm[j == iw ? jw : j == jw ? iw : j]);
222 delta_cost += w * sqr(wanted - new_actual);
223 }
224 } else if (i == jw) {
225 for (int j = 0; j < n; j++) {
226 double wanted = target_dis[i * n + j], w = weights[i * n + j];
227 double actual = hamming_dis(perm[i], perm[j]);
228 delta_cost -= w * sqr(wanted - actual);
229 double new_actual =
230 hamming_dis(perm[iw], perm[j == iw ? jw : j == jw ? iw : j]);
231 delta_cost += w * sqr(wanted - new_actual);
232 }
233 } else {
234 int j = iw;
235 {
236 double wanted = target_dis[i * n + j], w = weights[i * n + j];
237 double actual = hamming_dis(perm[i], perm[j]);
238 delta_cost -= w * sqr(wanted - actual);
239 double new_actual = hamming_dis(perm[i], perm[jw]);
240 delta_cost += w * sqr(wanted - new_actual);
241 }
242 j = jw;
243 {
244 double wanted = target_dis[i * n + j], w = weights[i * n + j];
245 double actual = hamming_dis(perm[i], perm[j]);
246 delta_cost -= w * sqr(wanted - actual);
247 double new_actual = hamming_dis(perm[i], perm[iw]);
248 delta_cost += w * sqr(wanted - new_actual);
249 }
250 }
251 }
252
253 return delta_cost;
254 }
255
256
257
258 ReproduceWithHammingObjective (
259 int nbits,
260 const std::vector<double> & dis_table,
261 double dis_weight_factor):
262 nbits (nbits), dis_weight_factor (dis_weight_factor)
263 {
264 n = 1 << nbits;
265 FAISS_THROW_IF_NOT (dis_table.size() == n * n);
266 set_affine_target_dis (dis_table);
267 }
268
269 void set_affine_target_dis (const std::vector<double> & dis_table)
270 {
271 double sum = 0, sum2 = 0;
272 int n2 = n * n;
273 for (int i = 0; i < n2; i++) {
274 sum += dis_table [i];
275 sum2 += dis_table [i] * dis_table [i];
276 }
277 double mean = sum / n2;
278 double stddev = sqrt(sum2 / n2 - (sum / n2) * (sum / n2));
279
280 target_dis.resize (n2);
281
282 for (int i = 0; i < n2; i++) {
283 // the mapping function
284 double td = (dis_table [i] - mean) / stddev * sqrt(nbits / 4) +
285 nbits / 2;
286 target_dis[i] = td;
287 // compute a weight
288 weights.push_back (dis_weight (td));
289 }
290
291 }
292
293 ~ReproduceWithHammingObjective() override {}
294 };
295
296 } // anonymous namespace
297
298 // weihgting of distances: it is more important to reproduce small
299 // distances well
300 double ReproduceDistancesObjective::dis_weight (double x) const
301 {
302 return exp (-dis_weight_factor * x);
303 }
304
305
306 double ReproduceDistancesObjective::get_source_dis (int i, int j) const
307 {
308 return source_dis [i * n + j];
309 }
310
311 // cost = quadratic difference between actual distance and Hamming distance
312 double ReproduceDistancesObjective::compute_cost (const int *perm) const
313 {
314 double cost = 0;
315 for (int i = 0; i < n; i++) {
316 for (int j = 0; j < n; j++) {
317 double wanted = target_dis [i * n + j];
318 double w = weights [i * n + j];
319 double actual = get_source_dis (perm[i], perm[j]);
320 cost += w * sqr (wanted - actual);
321 }
322 }
323 return cost;
324 }
325
326 // what would the cost update be if iw and jw were swapped?
327 // computed in O(n) instead of O(n^2) for the full re-computation
328 double ReproduceDistancesObjective::cost_update(
329 const int *perm, int iw, int jw) const
330 {
331 double delta_cost = 0;
332 for (int i = 0; i < n; i++) {
333 if (i == iw) {
334 for (int j = 0; j < n; j++) {
335 double wanted = target_dis [i * n + j],
336 w = weights [i * n + j];
337 double actual = get_source_dis (perm[i], perm[j]);
338 delta_cost -= w * sqr (wanted - actual);
339 double new_actual = get_source_dis (
340 perm[jw],
341 perm[j == iw ? jw : j == jw ? iw : j]);
342 delta_cost += w * sqr (wanted - new_actual);
343 }
344 } else if (i == jw) {
345 for (int j = 0; j < n; j++) {
346 double wanted = target_dis [i * n + j],
347 w = weights [i * n + j];
348 double actual = get_source_dis (perm[i], perm[j]);
349 delta_cost -= w * sqr (wanted - actual);
350 double new_actual = get_source_dis (
351 perm[iw],
352 perm[j == iw ? jw : j == jw ? iw : j]);
353 delta_cost += w * sqr (wanted - new_actual);
354 }
355 } else {
356 int j = iw;
357 {
358 double wanted = target_dis [i * n + j],
359 w = weights [i * n + j];
360 double actual = get_source_dis (perm[i], perm[j]);
361 delta_cost -= w * sqr (wanted - actual);
362 double new_actual = get_source_dis (perm[i], perm[jw]);
363 delta_cost += w * sqr (wanted - new_actual);
364 }
365 j = jw;
366 {
367 double wanted = target_dis [i * n + j],
368 w = weights [i * n + j];
369 double actual = get_source_dis (perm[i], perm[j]);
370 delta_cost -= w * sqr (wanted - actual);
371 double new_actual = get_source_dis (perm[i], perm[iw]);
372 delta_cost += w * sqr (wanted - new_actual);
373 }
374 }
375 }
376 return delta_cost;
377 }
378
379
380
381 ReproduceDistancesObjective::ReproduceDistancesObjective (
382 int n,
383 const double *source_dis_in,
384 const double *target_dis_in,
385 double dis_weight_factor):
386 dis_weight_factor (dis_weight_factor),
387 target_dis (target_dis_in)
388 {
389 this->n = n;
390 set_affine_target_dis (source_dis_in);
391 }
392
393 void ReproduceDistancesObjective::compute_mean_stdev (
394 const double *tab, size_t n2,
395 double *mean_out, double *stddev_out)
396 {
397 double sum = 0, sum2 = 0;
398 for (int i = 0; i < n2; i++) {
399 sum += tab [i];
400 sum2 += tab [i] * tab [i];
401 }
402 double mean = sum / n2;
403 double stddev = sqrt(sum2 / n2 - (sum / n2) * (sum / n2));
404 *mean_out = mean;
405 *stddev_out = stddev;
406 }
407
408 void ReproduceDistancesObjective::set_affine_target_dis (
409 const double *source_dis_in)
410 {
411 int n2 = n * n;
412
413 double mean_src, stddev_src;
414 compute_mean_stdev (source_dis_in, n2, &mean_src, &stddev_src);
415
416 double mean_target, stddev_target;
417 compute_mean_stdev (target_dis, n2, &mean_target, &stddev_target);
418
419 printf ("map mean %g std %g -> mean %g std %g\n",
420 mean_src, stddev_src, mean_target, stddev_target);
421
422 source_dis.resize (n2);
423 weights.resize (n2);
424
425 for (int i = 0; i < n2; i++) {
426 // the mapping function
427 source_dis[i] = (source_dis_in[i] - mean_src) / stddev_src
428 * stddev_target + mean_target;
429
430 // compute a weight
431 weights [i] = dis_weight (target_dis[i]);
432 }
433
434 }
435
436 /****************************************************
437 * Cost functions: RankingScore
438 ****************************************************/
439
440 /// Maintains a 3D table of elementary costs.
441 /// Accumulates elements based on Hamming distance comparisons
442 template <typename Ttab, typename Taccu>
443 struct Score3Computer: PermutationObjective {
444
445 int nc;
446
447 // cost matrix of size nc * nc *nc
448 // n_gt (i,j,k) = count of d_gt(x, y-) < d_gt(x, y+)
449 // where x has PQ code i, y- PQ code j and y+ PQ code k
450 std::vector<Ttab> n_gt;
451
452
453 /// the cost is a triple loop on the nc * nc * nc matrix of entries.
454 ///
455 Taccu compute (const int * perm) const
456 {
457 Taccu accu = 0;
458 const Ttab *p = n_gt.data();
459 for (int i = 0; i < nc; i++) {
460 int ip = perm [i];
461 for (int j = 0; j < nc; j++) {
462 int jp = perm [j];
463 for (int k = 0; k < nc; k++) {
464 int kp = perm [k];
465 if (hamming_dis (ip, jp) <
466 hamming_dis (ip, kp)) {
467 accu += *p; // n_gt [ ( i * nc + j) * nc + k];
468 }
469 p++;
470 }
471 }
472 }
473 return accu;
474 }
475
476
477 /** cost update if entries iw and jw of the permutation would be
478 * swapped.
479 *
480 * The computation is optimized by avoiding elements in the
481 * nc*nc*nc cube that are known not to change. For nc=256, this
482 * reduces the nb of cells to visit to about 6/256 th of the
483 * cells. Practical speedup is about 8x, and the code is quite
484 * complex :-/
485 */
486 Taccu compute_update (const int *perm, int iw, int jw) const
487 {
488 assert (iw != jw);
489 if (iw > jw) std::swap (iw, jw);
490
491 Taccu accu = 0;
492 const Ttab * n_gt_i = n_gt.data();
493 for (int i = 0; i < nc; i++) {
494 int ip0 = perm [i];
495 int ip = perm [i == iw ? jw : i == jw ? iw : i];
496
497 //accu += update_i (perm, iw, jw, ip0, ip, n_gt_i);
498
499 accu += update_i_cross (perm, iw, jw,
500 ip0, ip, n_gt_i);
501
502 if (ip != ip0)
503 accu += update_i_plane (perm, iw, jw,
504 ip0, ip, n_gt_i);
505
506 n_gt_i += nc * nc;
507 }
508
509 return accu;
510 }
511
512
513 Taccu update_i (const int *perm, int iw, int jw,
514 int ip0, int ip, const Ttab * n_gt_i) const
515 {
516 Taccu accu = 0;
517 const Ttab *n_gt_ij = n_gt_i;
518 for (int j = 0; j < nc; j++) {
519 int jp0 = perm[j];
520 int jp = perm [j == iw ? jw : j == jw ? iw : j];
521 for (int k = 0; k < nc; k++) {
522 int kp0 = perm [k];
523 int kp = perm [k == iw ? jw : k == jw ? iw : k];
524 int ng = n_gt_ij [k];
525 if (hamming_dis (ip, jp) < hamming_dis (ip, kp)) {
526 accu += ng;
527 }
528 if (hamming_dis (ip0, jp0) < hamming_dis (ip0, kp0)) {
529 accu -= ng;
530 }
531 }
532 n_gt_ij += nc;
533 }
534 return accu;
535 }
536
537 // 2 inner loops for the case ip0 != ip
538 Taccu update_i_plane (const int *perm, int iw, int jw,
539 int ip0, int ip, const Ttab * n_gt_i) const
540 {
541 Taccu accu = 0;
542 const Ttab *n_gt_ij = n_gt_i;
543
544 for (int j = 0; j < nc; j++) {
545 if (j != iw && j != jw) {
546 int jp = perm[j];
547 for (int k = 0; k < nc; k++) {
548 if (k != iw && k != jw) {
549 int kp = perm [k];
550 Ttab ng = n_gt_ij [k];
551 if (hamming_dis (ip, jp) < hamming_dis (ip, kp)) {
552 accu += ng;
553 }
554 if (hamming_dis (ip0, jp) < hamming_dis (ip0, kp)) {
555 accu -= ng;
556 }
557 }
558 }
559 }
560 n_gt_ij += nc;
561 }
562 return accu;
563 }
564
565 /// used for the 8 cells were the 3 indices are swapped
566 inline Taccu update_k (const int *perm, int iw, int jw,
567 int ip0, int ip, int jp0, int jp,
568 int k,
569 const Ttab * n_gt_ij) const
570 {
571 Taccu accu = 0;
572 int kp0 = perm [k];
573 int kp = perm [k == iw ? jw : k == jw ? iw : k];
574 Ttab ng = n_gt_ij [k];
575 if (hamming_dis (ip, jp) < hamming_dis (ip, kp)) {
576 accu += ng;
577 }
578 if (hamming_dis (ip0, jp0) < hamming_dis (ip0, kp0)) {
579 accu -= ng;
580 }
581 return accu;
582 }
583
584 /// compute update on a line of k's, where i and j are swapped
585 Taccu update_j_line (const int *perm, int iw, int jw,
586 int ip0, int ip, int jp0, int jp,
587 const Ttab * n_gt_ij) const
588 {
589 Taccu accu = 0;
590 for (int k = 0; k < nc; k++) {
591 if (k == iw || k == jw) continue;
592 int kp = perm [k];
593 Ttab ng = n_gt_ij [k];
594 if (hamming_dis (ip, jp) < hamming_dis (ip, kp)) {
595 accu += ng;
596 }
597 if (hamming_dis (ip0, jp0) < hamming_dis (ip0, kp)) {
598 accu -= ng;
599 }
600 }
601 return accu;
602 }
603
604
605 /// considers the 2 pairs of crossing lines j=iw or jw and k = iw or kw
606 Taccu update_i_cross (const int *perm, int iw, int jw,
607 int ip0, int ip, const Ttab * n_gt_i) const
608 {
609 Taccu accu = 0;
610 const Ttab *n_gt_ij = n_gt_i;
611
612 for (int j = 0; j < nc; j++) {
613 int jp0 = perm[j];
614 int jp = perm [j == iw ? jw : j == jw ? iw : j];
615
616 accu += update_k (perm, iw, jw, ip0, ip, jp0, jp, iw, n_gt_ij);
617 accu += update_k (perm, iw, jw, ip0, ip, jp0, jp, jw, n_gt_ij);
618
619 if (jp != jp0)
620 accu += update_j_line (perm, iw, jw, ip0, ip, jp0, jp, n_gt_ij);
621
622 n_gt_ij += nc;
623 }
624 return accu;
625 }
626
627
628 /// PermutationObjective implementeation (just negates the scores
629 /// for minimization)
630
631 double compute_cost(const int* perm) const override {
632 return -compute(perm);
633 }
634
635 double cost_update(const int* perm, int iw, int jw) const override {
636 double ret = -compute_update(perm, iw, jw);
637 return ret;
638 }
639
640 ~Score3Computer() override {}
641 };
642
643
644
645
646
647 struct IndirectSort {
648 const float *tab;
649 bool operator () (int a, int b) {return tab[a] < tab[b]; }
650 };
651
652
653
654 struct RankingScore2: Score3Computer<float, double> {
655 int nbits;
656 int nq, nb;
657 const uint32_t *qcodes, *bcodes;
658 const float *gt_distances;
659
660 RankingScore2 (int nbits, int nq, int nb,
661 const uint32_t *qcodes, const uint32_t *bcodes,
662 const float *gt_distances):
663 nbits(nbits), nq(nq), nb(nb), qcodes(qcodes),
664 bcodes(bcodes), gt_distances(gt_distances)
665 {
666 n = nc = 1 << nbits;
667 n_gt.resize (nc * nc * nc);
668 init_n_gt ();
669 }
670
671
672 double rank_weight (int r)
673 {
674 return 1.0 / (r + 1);
675 }
676
677 /// count nb of i, j in a x b st. i < j
678 /// a and b should be sorted on input
679 /// they are the ranks of j and k respectively.
680 /// specific version for diff-of-rank weighting, cannot optimized
681 /// with a cumulative table
682 double accum_gt_weight_diff (const std::vector<int> & a,
683 const std::vector<int> & b)
684 {
685 int nb = b.size(), na = a.size();
686
687 double accu = 0;
688 int j = 0;
689 for (int i = 0; i < na; i++) {
690 int ai = a[i];
691 while (j < nb && ai >= b[j]) j++;
692
693 double accu_i = 0;
694 for (int k = j; k < b.size(); k++)
695 accu_i += rank_weight (b[k] - ai);
696
697 accu += rank_weight (ai) * accu_i;
698
699 }
700 return accu;
701 }
702
703 void init_n_gt ()
704 {
705 for (int q = 0; q < nq; q++) {
706 const float *gtd = gt_distances + q * nb;
707 const uint32_t *cb = bcodes;// all same codes
708 float * n_gt_q = & n_gt [qcodes[q] * nc * nc];
709
710 printf("init gt for q=%d/%d \r", q, nq); fflush(stdout);
711
712 std::vector<int> rankv (nb);
713 int * ranks = rankv.data();
714
715 // elements in each code bin, ordered by rank within each bin
716 std::vector<std::vector<int> > tab (nc);
717
718 { // build rank table
719 IndirectSort s = {gtd};
720 for (int j = 0; j < nb; j++) ranks[j] = j;
721 std::sort (ranks, ranks + nb, s);
722 }
723
724 for (int rank = 0; rank < nb; rank++) {
725 int i = ranks [rank];
726 tab [cb[i]].push_back (rank);
727 }
728
729
730 // this is very expensive. Any suggestion for improvement
731 // welcome.
732 for (int i = 0; i < nc; i++) {
733 std::vector<int> & di = tab[i];
734 for (int j = 0; j < nc; j++) {
735 std::vector<int> & dj = tab[j];
736 n_gt_q [i * nc + j] += accum_gt_weight_diff (di, dj);
737
738 }
739 }
740
741 }
742
743 }
744
745 };
746
747
748 /*****************************************
749 * PolysemousTraining
750 ******************************************/
751
752
753
754 PolysemousTraining::PolysemousTraining ()
755 {
756 optimization_type = OT_ReproduceDistances_affine;
757 ntrain_permutation = 0;
758 dis_weight_factor = log(2);
759 }
760
761
762
763 void PolysemousTraining::optimize_reproduce_distances (
764 ProductQuantizer &pq) const
765 {
766
767 int dsub = pq.dsub;
768
769 int n = pq.ksub;
770 int nbits = pq.nbits;
771
772 #pragma omp parallel for
773 for (int m = 0; m < pq.M; m++) {
774 std::vector<double> dis_table;
775
776 // printf ("Optimizing quantizer %d\n", m);
777
778 float * centroids = pq.get_centroids (m, 0);
779
780 for (int i = 0; i < n; i++) {
781 for (int j = 0; j < n; j++) {
782 dis_table.push_back (fvec_L2sqr (centroids + i * dsub,
783 centroids + j * dsub,
784 dsub));
785 }
786 }
787
788 std::vector<int> perm (n);
789 ReproduceWithHammingObjective obj (
790 nbits, dis_table,
791 dis_weight_factor);
792
793
794 SimulatedAnnealingOptimizer optim (&obj, *this);
795
796 if (log_pattern.size()) {
797 char fname[256];
798 snprintf (fname, 256, log_pattern.c_str(), m);
799 printf ("opening log file %s\n", fname);
800 optim.logfile = fopen (fname, "w");
801 FAISS_THROW_IF_NOT_MSG (optim.logfile, "could not open logfile");
802 }
803 double final_cost = optim.run_optimization (perm.data());
804
805 if (verbose > 0) {
806 printf ("SimulatedAnnealingOptimizer for m=%d: %g -> %g\n",
807 m, optim.init_cost, final_cost);
808 }
809
810 if (log_pattern.size()) fclose (optim.logfile);
811
812 std::vector<float> centroids_copy;
813 for (int i = 0; i < dsub * n; i++)
814 centroids_copy.push_back (centroids[i]);
815
816 for (int i = 0; i < n; i++)
817 memcpy (centroids + perm[i] * dsub,
818 centroids_copy.data() + i * dsub,
819 dsub * sizeof(centroids[0]));
820
821 }
822
823 }
824
825
826 void PolysemousTraining::optimize_ranking (
827 ProductQuantizer &pq, size_t n, const float *x) const
828 {
829
830 int dsub = pq.dsub;
831
832 int nbits = pq.nbits;
833
834 std::vector<uint8_t> all_codes (pq.code_size * n);
835
836 pq.compute_codes (x, all_codes.data(), n);
837
838 FAISS_THROW_IF_NOT (pq.byte_per_idx == 1);
839
840 if (n == 0)
841 pq.compute_sdc_table ();
842
843 #pragma omp parallel for
844 for (int m = 0; m < pq.M; m++) {
845 size_t nq, nb;
846 std::vector <uint32_t> codes; // query codes, then db codes
847 std::vector <float> gt_distances; // nq * nb matrix of distances
848
849 if (n > 0) {
850 std::vector<float> xtrain (n * dsub);
851 for (int i = 0; i < n; i++)
852 memcpy (xtrain.data() + i * dsub,
853 x + i * pq.d + m * dsub,
854 sizeof(float) * dsub);
855
856 codes.resize (n);
857 for (int i = 0; i < n; i++)
858 codes [i] = all_codes [i * pq.code_size + m];
859
860 nq = n / 4; nb = n - nq;
861 const float *xq = xtrain.data();
862 const float *xb = xq + nq * dsub;
863
864 gt_distances.resize (nq * nb);
865
866 pairwise_L2sqr (dsub,
867 nq, xq,
868 nb, xb,
869 gt_distances.data());
870 } else {
871 nq = nb = pq.ksub;
872 codes.resize (2 * nq);
873 for (int i = 0; i < nq; i++)
874 codes[i] = codes [i + nq] = i;
875
876 gt_distances.resize (nq * nb);
877
878 memcpy (gt_distances.data (),
879 pq.sdc_table.data () + m * nq * nb,
880 sizeof (float) * nq * nb);
881 }
882
883 double t0 = getmillisecs ();
884
885 PermutationObjective *obj = new RankingScore2 (
886 nbits, nq, nb,
887 codes.data(), codes.data() + nq,
888 gt_distances.data ());
889 ScopeDeleter1<PermutationObjective> del (obj);
890
891 if (verbose > 0) {
892 printf(" m=%d, nq=%ld, nb=%ld, intialize RankingScore "
893 "in %.3f ms\n",
894 m, nq, nb, getmillisecs () - t0);
895 }
896
897 SimulatedAnnealingOptimizer optim (obj, *this);
898
899 if (log_pattern.size()) {
900 char fname[256];
901 snprintf (fname, 256, log_pattern.c_str(), m);
902 printf ("opening log file %s\n", fname);
903 optim.logfile = fopen (fname, "w");
904 FAISS_THROW_IF_NOT_FMT (optim.logfile,
905 "could not open logfile %s", fname);
906 }
907
908 std::vector<int> perm (pq.ksub);
909
910 double final_cost = optim.run_optimization (perm.data());
911 printf ("SimulatedAnnealingOptimizer for m=%d: %g -> %g\n",
912 m, optim.init_cost, final_cost);
913
914 if (log_pattern.size()) fclose (optim.logfile);
915
916 float * centroids = pq.get_centroids (m, 0);
917
918 std::vector<float> centroids_copy;
919 for (int i = 0; i < dsub * pq.ksub; i++)
920 centroids_copy.push_back (centroids[i]);
921
922 for (int i = 0; i < pq.ksub; i++)
923 memcpy (centroids + perm[i] * dsub,
924 centroids_copy.data() + i * dsub,
925 dsub * sizeof(centroids[0]));
926
927 }
928
929 }
930
931
932
933 void PolysemousTraining::optimize_pq_for_hamming (ProductQuantizer &pq,
934 size_t n, const float *x) const
935 {
936 if (optimization_type == OT_None) {
937
938 } else if (optimization_type == OT_ReproduceDistances_affine) {
939 optimize_reproduce_distances (pq);
940 } else {
941 optimize_ranking (pq, n, x);
942 }
943
944 pq.compute_sdc_table ();
945
946 }
947
948
949
950 } // namespace faiss
faiss::RandomGenerator
random generator that can be used in multithreaded contexts
Definition: utils.h:48
faiss::ProductQuantizer::nbits
size_t nbits
number of bits per quantization index
Definition: ProductQuantizer.h:29
faiss::fvec_L2sqr
float fvec_L2sqr(const float *x, const float *y, size_t d)
Squared L2 distance between two vectors.
Definition: utils.cpp:574
faiss::ProductQuantizer::byte_per_idx
size_t byte_per_idx
nb bytes per code component (1 or 2)
Definition: ProductQuantizer.h:33
faiss::Score3Computer::compute_update
Taccu compute_update(const int *perm, int iw, int jw) const
Definition: PolysemousTraining.cpp:486
faiss::ProductQuantizer::sdc_table
std::vector< float > sdc_table
Symmetric Distance Table.
Definition: ProductQuantizer.h:159
faiss::SimulatedAnnealingOptimizer::SimulatedAnnealingOptimizer
SimulatedAnnealingOptimizer(PermutationObjective *obj, const SimulatedAnnealingParameters &p)
logs values of the cost function
Definition: PolysemousTraining.cpp:67
faiss::ScopeDeleter1
Definition: FaissException.h:52
faiss::SimulatedAnnealingOptimizer::n
int n
size of the permutation
Definition: PolysemousTraining.h:101
faiss::Score3Computer::compute
Taccu compute(const int *perm) const
Definition: PolysemousTraining.cpp:455
faiss::ProductQuantizer::dsub
size_t dsub
dimensionality of each subvector
Definition: ProductQuantizer.h:32
faiss::ProductQuantizer::compute_codes
void compute_codes(const float *x, uint8_t *codes, size_t n) const
same as compute_code for several vectors
Definition: ProductQuantizer.cpp:386
faiss::Score3Computer::update_j_line
Taccu update_j_line(const int *perm, int iw, int jw, int ip0, int ip, int jp0, int jp, const Ttab *n_gt_ij) const
compute update on a line of k&#39;s, where i and j are swapped
Definition: PolysemousTraining.cpp:585
faiss::ReproduceDistancesObjective::target_dis
const double * target_dis
wanted distances (size n^2)
Definition: PolysemousTraining.h:69
faiss::ProductQuantizer::code_size
size_t code_size
byte per indexed vector
Definition: ProductQuantizer.h:34
faiss::SimulatedAnnealingOptimizer::init_cost
double init_cost
remember intial cost of optimization
Definition: PolysemousTraining.h:109
faiss::RandomGenerator::rand_int
int rand_int()
random 31-bit positive integer
faiss::ProductQuantizer::ksub
size_t ksub
number of centroids for each subquantizer
Definition: ProductQuantizer.h:35
faiss::PolysemousTraining::optimize_ranking
void optimize_ranking(ProductQuantizer &pq, size_t n, const float *x) const
called by optimize_pq_for_hamming
Definition: PolysemousTraining.cpp:826
faiss::pairwise_L2sqr
void pairwise_L2sqr(long d, long nq, const float *xq, long nb, const float *xb, float *dis, long ldq, long ldb, long ldd)
Definition: utils.cpp:1344
faiss::Score3Computer::compute_cost
double compute_cost(const int *perm) const override
Definition: PolysemousTraining.cpp:631
faiss::Score3Computer
Definition: PolysemousTraining.cpp:443
faiss::getmillisecs
double getmillisecs()
ms elapsed since some arbitrary epoch
Definition: utils.cpp:74
faiss::ReproduceDistancesObjective::weights
std::vector< double > weights
weights for each distance (size n^2)
Definition: PolysemousTraining.h:70
faiss::RankingScore2::accum_gt_weight_diff
double accum_gt_weight_diff(const std::vector< int > &a, const std::vector< int > &b)
Definition: PolysemousTraining.cpp:682
faiss::SimulatedAnnealingParameters
parameters used for the simulated annealing method
Definition: PolysemousTraining.h:25
faiss::IndirectSort
Definition: PolysemousTraining.cpp:647
faiss::Score3Computer::update_i_cross
Taccu update_i_cross(const int *perm, int iw, int jw, int ip0, int ip, const Ttab *n_gt_i) const
considers the 2 pairs of crossing lines j=iw or jw and k = iw or kw
Definition: PolysemousTraining.cpp:606
faiss::ProductQuantizer::M
size_t M
number of subquantizers
Definition: ProductQuantizer.h:28
faiss::PolysemousTraining::OT_ReproduceDistances_affine
default
Definition: PolysemousTraining.h:129
faiss::PermutationObjective
abstract class for the loss function
Definition: PolysemousTraining.h:44
faiss::ProductQuantizer
Definition: ProductQuantizer.h:25
faiss::Score3Computer::update_k
Taccu update_k(const int *perm, int iw, int jw, int ip0, int ip, int jp0, int jp, int k, const Ttab *n_gt_ij) const
used for the 8 cells were the 3 indices are swapped
Definition: PolysemousTraining.cpp:566
faiss::ReproduceDistancesObjective::source_dis
std::vector< double > source_dis
&quot;real&quot; corrected distances (size n^2)
Definition: PolysemousTraining.h:68
faiss::ProductQuantizer::get_centroids
float * get_centroids(size_t m, size_t i)
return the centroids associated with subvector m
Definition: ProductQuantizer.h:59
faiss::PolysemousTraining::optimize_reproduce_distances
void optimize_reproduce_distances(ProductQuantizer &pq) const
called by optimize_pq_for_hamming
Definition: PolysemousTraining.cpp:763
faiss::PolysemousTraining::optimize_pq_for_hamming
void optimize_pq_for_hamming(ProductQuantizer &pq, size_t n, const float *x) const
Definition: PolysemousTraining.cpp:933
faiss::ProductQuantizer::d
size_t d
size of the input vectors
Definition: ProductQuantizer.h:27
faiss::RankingScore2
Definition: PolysemousTraining.cpp:654
faiss::SimulatedAnnealingOptimizer
Simulated annealing optimization algorithm for permutations.
Definition: PolysemousTraining.h:98