Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/PolysemousTraining.h
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 // Copyright 2004-present Facebook. All Rights Reserved.
10 // -*- c++ -*-
11
12 #ifndef FAISS_POLYSEMOUS_TRAINING_INCLUDED
13 #define FAISS_POLYSEMOUS_TRAINING_INCLUDED
14
15
16 #include "ProductQuantizer.h"
17
18
19 namespace faiss {
20
21
22
23
24 /// parameters used for the simulated annealing method
25 struct SimulatedAnnealingParameters {
26
27 // optimization parameters
28 double init_temperature; // init probaility of accepting a bad swap
29 double temperature_decay; // at each iteration the temp is multiplied by this
30 int n_iter; // nb of iterations
31 int n_redo; // nb of runs of the simulation
32 int seed; // random seed
33 int verbose;
34 bool only_bit_flips; // restrict permutation changes to bit flips
35 bool init_random; // intialize with a random permutation (not identity)
36
37 // set reasonable defaults
38 SimulatedAnnealingParameters ();
39
40 };
41
42
43 /// abstract class for the loss function
44 struct PermutationObjective {
45
46 int n;
47
48 virtual double compute_cost (const int *perm) const = 0;
49
50 // what would the cost update be if iw and jw were swapped?
51 // default implementation just computes both and computes the difference
52 virtual double cost_update (const int *perm, int iw, int jw) const;
53
54 virtual ~PermutationObjective () {}
55 };
56
57
58 struct ReproduceDistancesObjective : PermutationObjective {
59
60 double dis_weight_factor;
61
62 static double sqr (double x) { return x * x; }
63
64 // weihgting of distances: it is more important to reproduce small
65 // distances well
66 double dis_weight (double x) const;
67
68 std::vector<double> source_dis; ///< "real" corrected distances (size n^2)
69 const double * target_dis; ///< wanted distances (size n^2)
70 std::vector<double> weights; ///< weights for each distance (size n^2)
71
72 double get_source_dis (int i, int j) const;
73
74 // cost = quadratic difference between actual distance and Hamming distance
75 double compute_cost(const int* perm) const override;
76
77 // what would the cost update be if iw and jw were swapped?
78 // computed in O(n) instead of O(n^2) for the full re-computation
79 double cost_update(const int* perm, int iw, int jw) const override;
80
81 ReproduceDistancesObjective (
82 int n,
83 const double *source_dis_in,
84 const double *target_dis_in,
85 double dis_weight_factor);
86
87 static void compute_mean_stdev (const double *tab, size_t n2,
88 double *mean_out, double *stddev_out);
89
90 void set_affine_target_dis (const double *source_dis_in);
91
92 ~ReproduceDistancesObjective() override {}
93 };
94
95 struct RandomGenerator;
96
97 /// Simulated annealing optimization algorithm for permutations.
98 struct SimulatedAnnealingOptimizer: SimulatedAnnealingParameters {
99
100 PermutationObjective *obj;
101 int n; ///< size of the permutation
102 FILE *logfile; /// logs values of the cost function
103
104 SimulatedAnnealingOptimizer (PermutationObjective *obj,
105 const SimulatedAnnealingParameters &p);
106 RandomGenerator *rnd;
107
108 /// remember intial cost of optimization
109 double init_cost;
110
111 // main entry point. Perform the optimization loop, starting from
112 // and modifying permutation in-place
113 double optimize (int *perm);
114
115 // run the optimization and return the best result in best_perm
116 double run_optimization (int * best_perm);
117
118 virtual ~SimulatedAnnealingOptimizer ();
119 };
120
121
122
123
124 /// optimizes the order of indices in a ProductQuantizer
125 struct PolysemousTraining: SimulatedAnnealingParameters {
126
127 enum Optimization_type_t {
128 OT_None,
129 OT_ReproduceDistances_affine, ///< default
130 OT_Ranking_weighted_diff /// same as _2, but use rank of y+ - rank of y-
131 };
132 Optimization_type_t optimization_type;
133
134 // use 1/4 of the training points for the optimization, with
135 // max. ntrain_permutation. If ntrain_permutation == 0: train on
136 // centroids
137 int ntrain_permutation;
138 double dis_weight_factor; // decay of exp that weights distance loss
139
140 // filename pattern for the logging of iterations
141 std::string log_pattern;
142
143 // sets default values
144 PolysemousTraining ();
145
146 /// reorder the centroids so that the Hamming distace becomes a
147 /// good approximation of the SDC distance (called by train)
148 void optimize_pq_for_hamming (ProductQuantizer & pq,
149 size_t n, const float *x) const;
150
151 /// called by optimize_pq_for_hamming
152 void optimize_ranking (ProductQuantizer &pq, size_t n, const float *x) const;
153 /// called by optimize_pq_for_hamming
154 void optimize_reproduce_distances (ProductQuantizer &pq) const;
155
156 };
157
158
159
160 } // namespace faiss
161
162
163 #endif
faiss::RandomGenerator
random generator that can be used in multithreaded contexts
Definition: utils.h:48
faiss::PolysemousTraining::OT_Ranking_weighted_diff
same as _2, but use rank of y+ - rank of y-
Definition: PolysemousTraining.h:130
faiss::SimulatedAnnealingOptimizer::SimulatedAnnealingOptimizer
SimulatedAnnealingOptimizer(PermutationObjective *obj, const SimulatedAnnealingParameters &p)
logs values of the cost function
Definition: PolysemousTraining.cpp:67
faiss::ReproduceDistancesObjective
Definition: PolysemousTraining.h:58
faiss::SimulatedAnnealingOptimizer::n
int n
size of the permutation
Definition: PolysemousTraining.h:101
faiss::ReproduceDistancesObjective::target_dis
const double * target_dis
wanted distances (size n^2)
Definition: PolysemousTraining.h:69
faiss::SimulatedAnnealingOptimizer::init_cost
double init_cost
remember intial cost of optimization
Definition: PolysemousTraining.h:109
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::PolysemousTraining
optimizes the order of indices in a ProductQuantizer
Definition: PolysemousTraining.h:125
faiss::ReproduceDistancesObjective::weights
std::vector< double > weights
weights for each distance (size n^2)
Definition: PolysemousTraining.h:70
faiss::SimulatedAnnealingParameters
parameters used for the simulated annealing method
Definition: PolysemousTraining.h:25
faiss::PolysemousTraining::OT_ReproduceDistances_affine
default
Definition: PolysemousTraining.h:129
faiss::PermutationObjective
abstract class for the loss function
Definition: PolysemousTraining.h:44
faiss::PolysemousTraining::Optimization_type_t
Optimization_type_t
Definition: PolysemousTraining.h:127
faiss::ProductQuantizer
Definition: ProductQuantizer.h:25
faiss::ReproduceDistancesObjective::source_dis
std::vector< double > source_dis
&quot;real&quot; corrected distances (size n^2)
Definition: PolysemousTraining.h:68
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::SimulatedAnnealingOptimizer
Simulated annealing optimization algorithm for permutations.
Definition: PolysemousTraining.h:98