Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/VectorTransform.h
1
2 /**
3 * Copyright (c) 2015-present, Facebook, Inc.
4 * All rights reserved.
5 *
6 * This source code is licensed under the CC-by-NC license found in the
7 * LICENSE file in the root directory of this source tree.
8 */
9
10 // Copyright 2004-present Facebook. All Rights Reserved.
11 // -*- c++ -*-
12
13 #ifndef FAISS_VECTOR_TRANSFORM_H
14 #define FAISS_VECTOR_TRANSFORM_H
15
16 /** Defines a few objects that apply transformations to a set of
17 * vectors Often these are pre-processing steps.
18 */
19
20 #include <vector>
21
22 #include "Index.h"
23
24
25 namespace faiss {
26
27
28 /** Any transformation applied on a set of vectors */
29 struct VectorTransform {
30
31 typedef Index::idx_t idx_t;
32
33 int d_in; ///! input dimension
34 int d_out; ///! output dimension
35
36 explicit VectorTransform (int d_in = 0, int d_out = 0):
37 d_in(d_in), d_out(d_out), is_trained(true)
38 {}
39
40
41 /// set if the LinearTransform does not require training, or if
42 /// training is done already
43 bool is_trained;
44
45
46 /** Perform training on a representative set of vectors. Does
47 * nothing by default.
48 *
49 * @param n nb of training vectors
50 * @param x training vecors, size n * d
51 */
52 virtual void train (idx_t n, const float *x);
53
54 /** apply the random roation, return new allocated matrix
55 * @param x size n * d_in
56 * @return size n * d_out
57 */
58 float *apply (idx_t n, const float * x) const;
59
60 /// same as apply, but result is pre-allocated
61 virtual void apply_noalloc (idx_t n, const float * x,
62 float *xt) const = 0;
63
64 /// reverse transformation. May not be implemented or may return
65 /// approximate result
66 virtual void reverse_transform (idx_t n, const float * xt,
67 float *x) const;
68
69 virtual ~VectorTransform () {}
70
71 };
72
73
74
75 /** Generic linear transformation, with bias term applied on output
76 * y = A * x + b
77 */
78 struct LinearTransform: VectorTransform {
79
80
81 bool have_bias; ///! whether to use the bias term
82
83 /// Transformation matrix, size d_out * d_in
84 std::vector<float> A;
85
86 /// bias vector, size d_out
87 std::vector<float> b;
88
89
90 /// both d_in > d_out and d_out < d_in are supported
91 explicit LinearTransform (int d_in = 0, int d_out = 0,
92 bool have_bias = false);
93
94 /// same as apply, but result is pre-allocated
95 virtual void apply_noalloc (idx_t n, const float * x,
96 float *xt) const;
97
98 /// compute x = A^T * (x - b)
99 /// is reverse transform if A has orthonormal lines
100 void transform_transpose (idx_t n, const float * y,
101 float *x) const;
102
103 bool verbose;
104
105 virtual ~LinearTransform () {}
106
107
108 };
109
110
111
112 /// Randomly rotate a set of vectors
113 struct RandomRotationMatrix: LinearTransform {
114
115 /// both d_in > d_out and d_out < d_in are supported
116 RandomRotationMatrix (int d_in, int d_out):
117 LinearTransform(d_in, d_out, false) {}
118
119 /// must be called before the transform is used
120 void init(int seed);
121
122 virtual void reverse_transform (idx_t n, const float * xt,
123 float *x) const override;
124
125 RandomRotationMatrix () {}
126 };
127
128
129 /** Applies a principal component analysis on a set of vectors,
130 * with optionally whitening and random rotation. */
131 struct PCAMatrix: LinearTransform {
132
133 /** after transformation the components are multiplied by
134 * eigenvalues^eigen_power
135 *
136 * =0: no whitening
137 * =-2: full whitening
138 */
139 float eigen_power;
140
141 /// random rotation after PCA
142 bool random_rotation;
143
144 /// ratio between # training vectors and dimension
145 size_t max_points_per_d;
146
147 /// try to distribute output eigenvectors in this many bins
148 int balanced_bins;
149
150 /// Mean, size d_in
151 std::vector<float> mean;
152
153 /// eigenvalues of covariance matrix (= squared singular values)
154 std::vector<float> eigenvalues;
155
156 /// PCA matrix, size d_in * d_in
157 std::vector<float> PCAMat;
158
159 // the final matrix is computed after random rotation and/or whitening
160 explicit PCAMatrix (int d_in = 0, int d_out = 0,
161 float eigen_power = 0, bool random_rotation = false);
162
163 virtual void train (Index::idx_t n, const float *x) override;
164
165 virtual void reverse_transform (idx_t n, const float * xt,
166 float *x) const override;
167
168 /// copy pre-trained PCA matrix
169 void copy_from (const PCAMatrix & other);
170
171 /// called after mean, PCAMat and eigenvalues are computed
172 void prepare_Ab();
173
174 };
175
176
177
178 /** Applies a rotation to align the dimensions with a PQ to minimize
179 * the reconstruction error. Can be used before an IndexPQ or an
180 * IndexIVFPQ. The method is the non-parametric version described in:
181 *
182 * "Optimized Product Quantization for Approximate Nearest Neighbor Search"
183 * Tiezheng Ge, Kaiming He, Qifa Ke, Jian Sun, CVPR'13
184 *
185 */
186 struct OPQMatrix: LinearTransform {
187
188 int M; ///< nb of subquantizers
189 int niter; ///< Number of outer training iterations
190 int niter_pq; ///< Number of training iterations for the PQ
191 int niter_pq_0; ///< same, for the first outer iteration
192
193 /// if there are too many training points, resample
194 size_t max_train_points;
195 bool verbose;
196
197 /// if d2 != -1, output vectors of this dimension
198 explicit OPQMatrix (int d = 0, int M = 1, int d2 = -1);
199
200 virtual void train (Index::idx_t n, const float *x) override;
201
202 virtual void reverse_transform (idx_t n, const float * xt,
203 float *x) const override;
204 };
205
206
207 /** remap dimensions for intput vectors, possibly inserting 0s
208 * strictly speaking this is also a linear transform but we don't want
209 * to compute it with matrix multiplies */
210 struct RemapDimensionsTransform: VectorTransform {
211
212
213 /// map from output dimension to input, size d_out
214 /// -1 -> set output to 0
215 std::vector<int> map;
216
217 RemapDimensionsTransform (int d_in, int d_out, const int *map);
218
219 /// remap input to output, skipping or inserting dimensions as needed
220 /// if uniform: distribute dimensions uniformly
221 /// otherwise just take the d_out first ones.
222 RemapDimensionsTransform (int d_in, int d_out, bool uniform = true);
223
224 virtual void apply_noalloc (idx_t n, const float * x,
225 float *xt) const override;
226
227 /// reverse transform correct only when the mapping is a permuation
228 virtual void reverse_transform (idx_t n, const float * xt,
229 float *x) const override;
230
231 RemapDimensionsTransform () {}
232 };
233
234
235 /** Index that applies a LinearTransform transform on vectors before
236 * handing them over to a sub-index */
237 struct IndexPreTransform: Index {
238
239 std::vector<VectorTransform *> chain; ///! chain of tranforms
240 Index * index; ///! the sub-index
241
242 bool own_fields; ///! whether pointers are deleted in destructor
243
244 explicit IndexPreTransform (Index *index);
245
246 IndexPreTransform ();
247
248 /// ltrans is the last transform before the index
249 IndexPreTransform (VectorTransform * ltrans, Index * index);
250
251 void prepend_transform (VectorTransform * ltrans);
252
253 virtual void set_typename () override;
254
255 virtual void train (idx_t n, const float *x) override;
256
257 virtual void add (idx_t n, const float *x) override;
258
259 virtual void add_with_ids (idx_t n, const float * x, const long *xids)
260 override;
261
262
263 virtual void reset () override;
264
265 /** removes IDs from the index. Not supported by all indexes.
266 */
267 virtual long remove_ids (const IDSelector & sel) override;
268
269 virtual void search (
270 idx_t n, const float *x, idx_t k,
271 float *distances, idx_t *labels) const override;
272
273 void reconstruct_n (idx_t i0, idx_t ni, float *recons)
274 const override;
275
276 /// apply the transforms in the chain. The returned float * may be
277 /// equal to x, otherwise it should be deallocated.
278 const float * apply_chain (idx_t n, const float *x) const;
279
280 virtual ~IndexPreTransform ();
281
282 };
283
284
285
286 } // namespace faiss
287
288
289
290 #endif
faiss::LinearTransform::transform_transpose
void transform_transpose(idx_t n, const float *y, float *x) const
Definition: VectorTransform.cpp:130
faiss::IndexPreTransform::index
Index * index
! chain of tranforms
Definition: VectorTransform.h:240
faiss::RandomRotationMatrix
Randomly rotate a set of vectors.
Definition: VectorTransform.h:113
faiss::OPQMatrix::niter
int niter
Number of outer training iterations.
Definition: VectorTransform.h:189
faiss::RandomRotationMatrix::RandomRotationMatrix
RandomRotationMatrix(int d_in, int d_out)
both d_in &gt; d_out and d_out &lt; d_in are supported
Definition: VectorTransform.h:116
faiss::RandomRotationMatrix::init
void init(int seed)
must be called before the transform is used
Definition: VectorTransform.cpp:160
faiss::IndexPreTransform::reset
virtual void reset() override
removes all elements from the database.
Definition: VectorTransform.cpp:751
faiss::OPQMatrix::niter_pq
int niter_pq
Number of training iterations for the PQ.
Definition: VectorTransform.h:190
faiss::LinearTransform::A
std::vector< float > A
! whether to use the bias term
Definition: VectorTransform.h:84
faiss::PCAMatrix::eigen_power
float eigen_power
Definition: VectorTransform.h:139
faiss::IDSelector
Definition: AuxIndexStructures.h:58
faiss::LinearTransform::LinearTransform
LinearTransform(int d_in=0, int d_out=0, bool have_bias=false)
both d_in &gt; d_out and d_out &lt; d_in are supported
Definition: VectorTransform.cpp:95
faiss::PCAMatrix
Definition: VectorTransform.h:131
faiss::VectorTransform::VectorTransform
VectorTransform(int d_in=0, int d_out=0)
! output dimension
Definition: VectorTransform.h:36
faiss::OPQMatrix
Definition: VectorTransform.h:186
faiss::PCAMatrix::train
virtual void train(Index::idx_t n, const float *x) override
Definition: VectorTransform.cpp:206
faiss::IndexPreTransform
Definition: VectorTransform.h:237
faiss::PCAMatrix::mean
std::vector< float > mean
Mean, size d_in.
Definition: VectorTransform.h:151
faiss::RemapDimensionsTransform::map
std::vector< int > map
Definition: VectorTransform.h:215
faiss::IndexPreTransform::apply_chain
const float * apply_chain(idx_t n, const float *x) const
Definition: VectorTransform.cpp:708
faiss::PCAMatrix::PCAMat
std::vector< float > PCAMat
PCA matrix, size d_in * d_in.
Definition: VectorTransform.h:157
faiss::IndexPreTransform::train
virtual void train(idx_t n, const float *x) override
Definition: VectorTransform.cpp:680
faiss::LinearTransform::b
std::vector< float > b
bias vector, size d_out
Definition: VectorTransform.h:87
faiss::LinearTransform
Definition: VectorTransform.h:78
faiss::OPQMatrix::train
virtual void train(Index::idx_t n, const float *x) override
Definition: VectorTransform.cpp:450
faiss::PCAMatrix::balanced_bins
int balanced_bins
try to distribute output eigenvectors in this many bins
Definition: VectorTransform.h:148
faiss::VectorTransform::is_trained
bool is_trained
Definition: VectorTransform.h:43
faiss::Index::idx_t
long idx_t
all indices are this type
Definition: Index.h:64
faiss::IndexPreTransform::reconstruct_n
void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override
Definition: VectorTransform.cpp:763
faiss::LinearTransform::apply_noalloc
virtual void apply_noalloc(idx_t n, const float *x, float *xt) const
same as apply, but result is pre-allocated
Definition: VectorTransform.cpp:101
faiss::VectorTransform
Definition: VectorTransform.h:29
faiss::IndexPreTransform::own_fields
bool own_fields
! the sub-index
Definition: VectorTransform.h:242
faiss::OPQMatrix::niter_pq_0
int niter_pq_0
same, for the first outer iteration
Definition: VectorTransform.h:191
faiss::OPQMatrix::reverse_transform
virtual void reverse_transform(idx_t n, const float *xt, float *x) const override
Definition: VectorTransform.cpp:612
faiss::VectorTransform::train
virtual void train(idx_t n, const float *x)
Definition: VectorTransform.cpp:76
faiss::RandomRotationMatrix::reverse_transform
virtual void reverse_transform(idx_t n, const float *xt, float *x) const override
Definition: VectorTransform.cpp:185
faiss::VectorTransform::reverse_transform
virtual void reverse_transform(idx_t n, const float *xt, float *x) const
Definition: VectorTransform.cpp:81
faiss::RemapDimensionsTransform::reverse_transform
virtual void reverse_transform(idx_t n, const float *xt, float *x) const override
reverse transform correct only when the mapping is a permuation
Definition: VectorTransform.cpp:830
faiss::RemapDimensionsTransform
Definition: VectorTransform.h:210
faiss::PCAMatrix::reverse_transform
virtual void reverse_transform(idx_t n, const float *xt, float *x) const override
Definition: VectorTransform.cpp:424
faiss::OPQMatrix::max_train_points
size_t max_train_points
if there are too many training points, resample
Definition: VectorTransform.h:194
faiss::PCAMatrix::copy_from
void copy_from(const PCAMatrix &other)
copy pre-trained PCA matrix
Definition: VectorTransform.cpp:319
faiss::VectorTransform::d_out
int d_out
! input dimension
Definition: VectorTransform.h:34
faiss::OPQMatrix::OPQMatrix
OPQMatrix(int d=0, int M=1, int d2=-1)
if d2 != -1, output vectors of this dimension
Definition: VectorTransform.cpp:437
faiss::Index
Definition: Index.h:61
faiss::PCAMatrix::prepare_Ab
void prepare_Ab()
called after mean, PCAMat and eigenvalues are computed
Definition: VectorTransform.cpp:329
faiss::IndexPreTransform::add
virtual void add(idx_t n, const float *x) override
Definition: VectorTransform.cpp:719
faiss::RemapDimensionsTransform::apply_noalloc
virtual void apply_noalloc(idx_t n, const float *x, float *xt) const override
same as apply, but result is pre-allocated
Definition: VectorTransform.cpp:818
faiss::PCAMatrix::eigenvalues
std::vector< float > eigenvalues
eigenvalues of covariance matrix (= squared singular values)
Definition: VectorTransform.h:154
faiss::IndexPreTransform::search
virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override
Definition: VectorTransform.cpp:741
faiss::IndexPreTransform::add_with_ids
virtual void add_with_ids(idx_t n, const float *x, const long *xids) override
Definition: VectorTransform.cpp:728
faiss::PCAMatrix::random_rotation
bool random_rotation
random rotation after PCA
Definition: VectorTransform.h:142
faiss::PCAMatrix::max_points_per_d
size_t max_points_per_d
ratio between # training vectors and dimension
Definition: VectorTransform.h:145
faiss::VectorTransform::apply
float * apply(idx_t n, const float *x) const
Definition: VectorTransform.cpp:68
faiss::IndexPreTransform::remove_ids
virtual long remove_ids(const IDSelector &sel) override
Definition: VectorTransform.cpp:756
faiss::VectorTransform::apply_noalloc
virtual void apply_noalloc(idx_t n, const float *x, float *xt) const =0
same as apply, but result is pre-allocated
faiss::OPQMatrix::M
int M
nb of subquantizers
Definition: VectorTransform.h:188