FastMinKernel.h 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555
  1. /**
  2. * @file FastMinKernel.h
  3. * @brief Efficient GPs with HIK for classification by regression (Interface)
  4. * @author Alexander Freytag
  5. * @date 06-12-2011 (dd-mm-yyyy)
  6. */
  7. #ifndef FASTMINKERNELINCLUDE
  8. #define FASTMINKERNELINCLUDE
  9. // STL includes
  10. #include <iostream>
  11. // NICE-core includes
  12. #include <core/basics/Config.h>
  13. #include <core/basics/Exception.h>
  14. #include <core/basics/Persistent.h>
  15. //
  16. //
  17. #include <core/vector/MatrixT.h>
  18. #include <core/vector/SparseVectorT.h>
  19. #include <core/vector/VectorT.h>
  20. #include <core/vector/VVector.h>
  21. // gp-hik-core includes
  22. #include "gp-hik-core/FeatureMatrixT.h"
  23. #include "gp-hik-core/OnlineLearnable.h"
  24. #include "gp-hik-core/Quantization.h"
  25. #include "gp-hik-core/parameterizedFunctions/ParameterizedFunction.h"
  26. namespace NICE {
  27. /**
  28. * @class FastMinKernel
  29. * @brief Efficient GPs with HIK for classification by regression
  30. * @author Alexander Freytag
  31. */
  32. /** interface to FastMinKernel implementation*/
  33. class FastMinKernel : public NICE::Persistent, public OnlineLearnable
  34. {
  35. protected:
  36. /** number of examples */
  37. uint ui_n;
  38. /** dimension of feature vectors */
  39. uint ui_d;
  40. /** noise added to the diagonal of the kernel matrix */
  41. double d_noise;
  42. /** sorted matrix of features (sorted along each dimension) */
  43. NICE::FeatureMatrixT<double> X_sorted;
  44. //! verbose flag for output after calling the restore-function
  45. bool b_verbose;
  46. //! debug flag for output during debugging
  47. bool b_debug;
  48. /**
  49. * @brief Set number of examples
  50. * @author Alexander Freytag
  51. * @date 07-12-2011 (dd-mm-yyyy)
  52. */
  53. void set_n(const uint & _n){this->ui_n = _n;};
  54. /**
  55. * @brief Set number of dimensions
  56. * @author Alexander Freytag
  57. * @date 07-12-2011 (dd-mm-yyyy)
  58. */
  59. void set_d(const uint & _d){this->ui_d = _d;};
  60. void randomPermutation(NICE::Vector & _permutation,
  61. const std::vector<uint> & _oldIndices,
  62. const uint & _newSize
  63. ) const;
  64. enum ApproximationScheme{ MEDIAN = 0, EXPECTATION=1};
  65. ApproximationScheme approxScheme;
  66. public:
  67. //------------------------------------------------------
  68. // several constructors and destructors
  69. //------------------------------------------------------
  70. /**
  71. * @brief default constructor
  72. * @author Alexander Freytag
  73. * @date 20-04-2012 (dd-mm-yyyy)
  74. */
  75. FastMinKernel();
  76. /**
  77. * @brief recommended constructor, initialize with some data
  78. * @author Alexander Freytag
  79. * @date 06-12-2011 (dd-mm-yyyy)
  80. */
  81. FastMinKernel( const std::vector<std::vector<double> > & _X,
  82. const double _noise ,
  83. const bool _debug = false,
  84. const uint & _dim = 0
  85. );
  86. /**
  87. * @brief recommended constructor, just another sparse data structure
  88. *
  89. * @param X vector of sparse vector pointers
  90. * @param noise GP noise
  91. */
  92. FastMinKernel( const std::vector< const NICE::SparseVector * > & _X,
  93. const double _noise,
  94. const bool _debug = false,
  95. const bool & dimensionsOverExamples=false,
  96. const uint & _dim = 0
  97. );
  98. #ifdef NICE_USELIB_MATIO
  99. /**
  100. * @brief recommended constructor, intialize with some data given in a matlab-sparse struct and restricted with an example index
  101. *
  102. * @param X matlab-struct containing the feature vectors
  103. * @param noise additional noise variance of the labels
  104. * @param examples set of indices to include
  105. */
  106. FastMinKernel ( const sparse_t & _X,
  107. const double _noise,
  108. const std::map<uint, uint> & _examples,
  109. const bool _debug = false ,
  110. const uint & _dim = 0);
  111. #endif
  112. /**
  113. * @brief Default destructor
  114. * @author Alexander Freytag
  115. * @date 06-12-2011 (dd-mm-yyyy)
  116. */
  117. ~FastMinKernel();
  118. ///////////////////// ///////////////////// /////////////////////
  119. // GET / SET
  120. // INCLUDING ACCESS OPERATORS
  121. ///////////////////// ///////////////////// /////////////////////
  122. void setApproximationScheme(const ApproximationScheme & _approxScheme = MEDIAN) {approxScheme = _approxScheme;};
  123. virtual void setApproximationScheme(const int & _approxScheme = 0);
  124. /**
  125. * @brief Get number of examples
  126. * @author Alexander Freytag
  127. * @date 07-12-2011 (dd-mm-yyyy)
  128. */
  129. uint get_n() const;
  130. /**
  131. * @brief Get number of dimensions
  132. * @author Alexander Freytag
  133. * @date 07-12-2011 (dd-mm-yyyy)
  134. */
  135. uint get_d() const;
  136. /**
  137. * @brief Computes the ratio of sparsity across the matrix
  138. * @author Alexander Freytag
  139. * @date 11-01-2012 (dd-mm-yyyy)
  140. */
  141. double getSparsityRatio() const;
  142. /** set verbose flag used for restore-functionality*/
  143. void setVerbose( const bool & _verbose);
  144. bool getVerbose( ) const;
  145. /** set debug flag used for debug output*/
  146. void setDebug( const bool & _debug);
  147. bool getDebug( ) const;
  148. //------------------------------------------------------
  149. // high level methods
  150. //------------------------------------------------------
  151. /**
  152. * @brief apply a parameterized function to the feature matrix
  153. * @author Alexander Freytag
  154. * @date 04-05-2012 (dd-mm-yyyy)
  155. *
  156. * @param pf the parameterized function (optional), if not given, nothing will be done
  157. */
  158. void applyFunctionToFeatureMatrix ( const NICE::ParameterizedFunction *_pf = NULL );
  159. /**
  160. * @brief Prepare the efficient HIK-computations part 2: calculate the partial sum for each dimension. Explicitely exploiting sparsity!!! Pay attention: X_sorted is of dimensionality d x n!
  161. * @author Alexander Freytag
  162. * @date 17-01-2012 (dd-mm-yyyy)
  163. */
  164. void hik_prepare_alpha_multiplications(const NICE::Vector & _alpha,
  165. NICE::VVector & _A,
  166. NICE::VVector & _B
  167. ) const;
  168. /**
  169. * @brief Prepare the efficient HIK-computations part 2 but for only a subset of examples
  170. * @author Erik Rodner
  171. * @date 15-09-2015 (dd-mm-yyyy)
  172. */
  173. void hik_prepare_alpha_multiplications_subset(const NICE::Vector & _alpha,
  174. NICE::VVector & _A,
  175. NICE::VVector & _B,
  176. const std::vector<int> & _subset
  177. ) const;
  178. /**
  179. * @brief Computing K*alpha with the minimum kernel trick, explicitely exploiting sparsity!!!
  180. * @author Alexander Freytag
  181. * @date 17-01-2012 (dd-mm-yyyy)
  182. */
  183. void hik_kernel_multiply(const NICE::VVector & _A,
  184. const NICE::VVector & _B,
  185. const NICE::Vector & _alpha,
  186. NICE::Vector & _beta
  187. ) const;
  188. void hik_kernel_multiply_fast(const double *_Tlookup,
  189. const Quantization & _q,
  190. const NICE::Vector & _alpha,
  191. NICE::Vector & _beta
  192. ) const;
  193. /**
  194. * @brief Computing k_{*}*alpha using the minimum kernel trick and exploiting sparsity of the feature vector given
  195. *
  196. * @author Alexander Freytag
  197. * @date 20-01-2012 (dd-mm-yyyy)
  198. * @param A pre-computation matrix (VVector) (use the prepare method)
  199. * @param B pre-computation matrix (VVector)
  200. * @param xstar new feature vector (SparseVector)
  201. * @param beta result of the scalar product
  202. * @param pf optional feature transformation
  203. */
  204. void hik_kernel_sum(const NICE::VVector & _A,
  205. const NICE::VVector & _B,
  206. const NICE::SparseVector & _xstar,
  207. double & _beta,
  208. const ParameterizedFunction *_pf = NULL
  209. ) const;
  210. /**
  211. * @brief Computing k_{*}*alpha using the minimum kernel trick and exploiting sparsity of the feature vector given
  212. * NOTE: Whenever possible, you should use sparse features to obtain significantly smaller computation times!
  213. *
  214. * @author Alexander Freytag
  215. * @date 18-06-2013 (dd-mm-yyyy)
  216. * @param A pre-computation matrix (VVector) (use the prepare method)
  217. * @param B pre-computation matrix (VVector)
  218. * @param xstar new feature vector (non-sparse Vector)
  219. * @param beta result of the scalar product
  220. * @param pf optional feature transformation
  221. */
  222. void hik_kernel_sum(const NICE::VVector & _A,
  223. const NICE::VVector & _B,
  224. const NICE::Vector & _xstar,
  225. double & _beta,
  226. const ParameterizedFunction *_pf = NULL
  227. ) const;
  228. /**
  229. * @brief compute beta = k_*^T * alpha by using a large lookup table created by hik_prepare_alpha_multiplications_fast
  230. * NOTE: Whenever possible, you should use sparse features to obtain significantly smaller computation times!
  231. * @author Alexander Freytag
  232. * @date 18-06-2013 (dd-mm-yyyy)
  233. *
  234. * @param Tlookup large lookup table calculated by hik_prepare_alpha_multiplications_fast
  235. * @param q Quantization object
  236. * @param xstar feature vector (indirect k_*)
  237. * @param beta result of the calculation
  238. */
  239. void hik_kernel_sum_fast(const double* _Tlookup,
  240. const Quantization & _q,
  241. const NICE::Vector & _xstar,
  242. double & _beta
  243. ) const;
  244. /**
  245. * @brief compute beta = k_*^T * alpha by using a large lookup table created by hik_prepare_alpha_multiplications_fast
  246. * NOTE: Whenever possible, you should use sparse features to obtain significantly smaller computation times!
  247. * @author Alexander Frytag
  248. *
  249. * @param Tlookup large lookup table calculated by hik_prepare_alpha_multiplications_fast
  250. * @param q Quantization object
  251. * @param xstar feature vector (indirect k_*)
  252. * @param beta result of the calculation
  253. */
  254. void hik_kernel_sum_fast(const double *_Tlookup,
  255. const Quantization & _q,
  256. const NICE::SparseVector & _xstar,
  257. double & _beta
  258. ) const;
  259. /**
  260. * @brief compute lookup table for HIK calculation using quantized signals and prepare for K*alpha or k_*^T * alpha computations,
  261. * whenever possible use hikPrepareLookupTable directly.
  262. * @author Erik Rodner, Alexander Freytag
  263. *
  264. * @param alpha coefficient vector
  265. * @param A pre-calculation array computed by hik_prepare_alpha_multiplications
  266. * @param B pre-calculation array computed by hik_prepare_alpha_multiplications
  267. * @param q Quantization
  268. *
  269. * @return C standard vector representing a q.size()*n double matrix and the lookup table T. Elements can be accessed with
  270. * T[dim*q.size() + j], where j is a bin entry corresponding to quantization q.
  271. */
  272. double *hik_prepare_alpha_multiplications_fast(const NICE::VVector & _A,
  273. const NICE::VVector & _B,
  274. const Quantization & _q,
  275. const ParameterizedFunction *_pf = NULL
  276. ) const;
  277. /**
  278. * @brief compute lookup table for HIK calculation using quantized signals and prepare for K*alpha or k_*^T * alpha computations
  279. * @author Alexander Freytag
  280. *
  281. * @param alpha coefficient vector
  282. * @param q Quantization
  283. * @param pf ParameterizedFunction to change the original feature values
  284. *
  285. * @return C standard vector representing a q.size()*n double matrix and the lookup table T. Elements can be accessed with
  286. * T[dim*q.size() + j], where j is a bin entry corresponding to quantization q.
  287. */
  288. double* hikPrepareLookupTable(const NICE::Vector & _alpha,
  289. const Quantization & _q,
  290. const ParameterizedFunction *_pf = NULL
  291. ) const;
  292. /**
  293. * @brief update the lookup table for HIK calculation using quantized signals and prepare for K*alpha or k_*^T * alpha computations
  294. * @author Alexander Freytag
  295. *
  296. * @param T previously computed LUT, that will be changed
  297. * @param alphaNew new value of alpha at index idx
  298. * @param alphaOld old value of alpha at index idx
  299. * @param idx index in which alpha changed
  300. * @param q Quantization
  301. * @param pf ParameterizedFunction to change the original feature values
  302. */
  303. void hikUpdateLookupTable(double * _T,
  304. const double & _alphaNew,
  305. const double & _alphaOld,
  306. const uint & _idx,
  307. const Quantization & _q,
  308. const ParameterizedFunction *pf
  309. ) const;
  310. /**
  311. * @brief return a reference to the sorted feature matrix
  312. */
  313. FeatureMatrix & featureMatrix(void) { return X_sorted; };
  314. const FeatureMatrix & featureMatrix(void) const { return X_sorted; };
  315. /**
  316. * @brief solve the linear system K*alpha = y with the minimum kernel trick based on the algorithm of Wu (Wu10_AFD)
  317. * @note method converges slowly for large scale problems and even for normal scale :(
  318. * @author Paul Bodesheim
  319. *
  320. * @param y right hand side of linear system
  321. * @param alpha final solution of the linear system
  322. * @param q Quantization
  323. * @param pf ParameterizedFunction to change the original feature values
  324. * @param useRandomSubsets true, if the order of examples in each iteration should be randomly sampled
  325. * @param maxIterations maximum number of iterations
  326. * @param sizeOfRandomSubset nr of Elements that should be randomly considered in each iteration (max: y.size())
  327. * @param minDelta minimum difference between two solutions alpha_t and alpha_{t+1} (convergence criterion)
  328. *
  329. * @return C standard vector representing a q.size()*n double matrix and the lookup table T. Elements can be accessed with
  330. * T[dim*q.size() + j], where j is a bin entry corresponding to quantization q.
  331. **/
  332. double *solveLin(const NICE::Vector & _y,
  333. NICE::Vector & _alpha,
  334. const Quantization & _q,
  335. const ParameterizedFunction *_pf = NULL,
  336. const bool & _useRandomSubsets = true,
  337. uint _maxIterations = 10000,
  338. const uint & _sizeOfRandomSubset = 0,
  339. double _minDelta = 1e-7,
  340. bool _timeAnalysis = false
  341. ) const;
  342. //! set the noise parameter
  343. void setNoise ( double _noise ) { this->d_noise = _noise; }
  344. //! get the current noise parameter
  345. double getNoise (void) const { return this->d_noise; }
  346. double getFrobNormApprox();
  347. /**
  348. * @brief Prepare the efficient HIK-computations for the squared kernel vector |k_*|^2 : calculate the partial squared sums for each dimension.
  349. * @author Alexander Freytag
  350. * @date 10-04-2012 (dd-mm-yyyy)
  351. */
  352. void hikPrepareKVNApproximation(NICE::VVector & _A) const;
  353. /**
  354. * @brief Compute lookup table for HIK calculation of |k_*|^2 assuming quantized test samples. You have to run hikPrepareSquaredKernelVector before
  355. * @author Alexander Freytag
  356. * @date 10-04-2012 (dd-mm-yyyy)
  357. *
  358. * @param A pre-calculation array computed by hikPrepareSquaredKernelVector
  359. * @param q Quantization
  360. * @param pf Parameterized Function to efficiently apply a function to the underlying data
  361. *
  362. * @return C standard vector representing a q.size()*d double matrix and the lookup table T. Elements can be accessed with
  363. * T[dim*q.size() + j], where j is a bin entry corresponding to quantization q.
  364. */
  365. double * hikPrepareKVNApproximationFast(NICE::VVector & _A, const Quantization & _q, const ParameterizedFunction *_pf = NULL ) const;
  366. /**
  367. * @brief Compute lookup table for HIK calculation of |k_*|^2 assuming quantized test samples ( equals hikPrepareSquaredKernelVector + hikPrepareSquaredKernelVectorFast, but is faster). Approximation does not considere mixed terms between dimensions.
  368. * @author Alexander Freytag
  369. * @date 10-04-2012 (dd-mm-yyyy)
  370. *
  371. * @param q Quantization
  372. * @param pf ParameterizedFunction to change the original feature values
  373. *
  374. * @return C standard vector representing a q.size()*d double matrix and the lookup table T. Elements can be accessed with
  375. * T[dim*q.size() + j], where j is a bin entry corresponding to quantization q.
  376. */
  377. double* hikPrepareLookupTableForKVNApproximation(const Quantization & _q, const ParameterizedFunction *_pf = NULL) const;
  378. //////////////////////////////////////////
  379. // variance computation: sparse inputs
  380. //////////////////////////////////////////
  381. /**
  382. * @brief Approximate norm = |k_*|^2 using the minimum kernel trick and exploiting sparsity of the given feature vector. Approximation does not considere mixed terms between dimensions.
  383. * @author Alexander Freytag
  384. * @date 10-04-2012 (dd-mm-yyyy)
  385. *
  386. * @param A pre-computation matrix (VVector) (use the prepare method)
  387. * @param xstar new feature vector (SparseVector)
  388. * @param norm result of the squared norm approximation
  389. * @param pf optional feature transformation
  390. */
  391. void hikComputeKVNApproximation(const NICE::VVector & _A, const NICE::SparseVector & _xstar, double & _norm, const ParameterizedFunction *_pf = NULL ) ;
  392. /**
  393. * @brief Approximate norm = |k_*|^2 using a large lookup table created by hikPrepareSquaredKernelVector and hikPrepareSquaredKernelVectorFast or directly using hikPrepareLookupTableForSquaredKernelVector. Approximation does not considere mixed terms between dimensions.
  394. * @author Alexander Freytag
  395. * @date 10-04-2012 (dd-mm-yyyy)
  396. *
  397. * @param Tlookup large lookup table
  398. * @param q Quantization object
  399. * @param xstar feature vector (indirect k_*)
  400. * @param norm result of the calculation
  401. */
  402. void hikComputeKVNApproximationFast(const double *_Tlookup, const Quantization & _q, const NICE::SparseVector & _xstar, double & _norm ) const;
  403. /**
  404. * @brief Compute the kernel vector k_* between training examples and test example. Runtime. O(n \times D). Exploiting sparsity
  405. * @author Alexander Freytag
  406. * @date 13-04-2012 (dd-mm-yyyy)
  407. *
  408. * @param xstar feature vector
  409. * @param kstar kernel vector
  410. */
  411. void hikComputeKernelVector( const NICE::SparseVector & _xstar, NICE::Vector & _kstar) const;
  412. //////////////////////////////////////////
  413. // variance computation: non-sparse inputs
  414. //////////////////////////////////////////
  415. /**
  416. * @brief Approximate norm = |k_*|^2 using the minimum kernel trick and exploiting sparsity of the given feature vector. Approximation does not considere mixed terms between dimensions.
  417. * @author Alexander Freytag
  418. * @date 19-12-2013 (dd-mm-yyyy)
  419. *
  420. * @param A pre-computation matrix (VVector) (use the prepare method)
  421. * @param xstar new feature vector (Vector)
  422. * @param norm result of the squared norm approximation
  423. * @param pf optional feature transformation
  424. */
  425. void hikComputeKVNApproximation(const NICE::VVector & _A, const NICE::Vector & _xstar, double & _norm, const ParameterizedFunction *_pf = NULL ) ;
  426. /**
  427. * @brief Approximate norm = |k_*|^2 using a large lookup table created by hikPrepareSquaredKernelVector and hikPrepareSquaredKernelVectorFast or directly using hikPrepareLookupTableForSquaredKernelVector. Approximation does not considere mixed terms between dimensions.
  428. * @author Alexander Freytag
  429. * @date 19-12-2013 (dd-mm-yyyy)
  430. *
  431. * @param Tlookup large lookup table
  432. * @param q Quantization object
  433. * @param xstar feature vector (indirect k_*)
  434. * @param norm result of the calculation
  435. */
  436. void hikComputeKVNApproximationFast(const double *_Tlookup, const Quantization & _q, const NICE::Vector & _xstar, double & _norm ) const;
  437. /**
  438. * @brief Compute the kernel vector k_* between training examples and test example. Runtime. O(n \times D). Does not exploit sparsity - deprecated!
  439. * @author Alexander Freytag
  440. * @date 19-12-2013 (dd-mm-yyyy)
  441. *
  442. * @param xstar feature vector
  443. * @param kstar kernel vector
  444. */
  445. void hikComputeKernelVector( const NICE::Vector & _xstar, NICE::Vector & _kstar) const;
  446. /** Persistent interface */
  447. virtual void restore ( std::istream & _is, int _format = 0 );
  448. virtual void store ( std::ostream & _os, int _format = 0 ) const;
  449. virtual void clear ();
  450. ///////////////////// INTERFACE ONLINE LEARNABLE /////////////////////
  451. // interface specific methods for incremental extensions
  452. ///////////////////// INTERFACE ONLINE LEARNABLE /////////////////////
  453. virtual void addExample( const NICE::SparseVector * _example,
  454. const double & _label,
  455. const bool & _performOptimizationAfterIncrement = true
  456. );
  457. virtual void addMultipleExamples( const std::vector< const NICE::SparseVector * > & _newExamples,
  458. const NICE::Vector & _newLabels,
  459. const bool & _performOptimizationAfterIncrement = true
  460. );
  461. /**
  462. * @brief Add a new example to the feature-storage. You have to update the corresponding variables explicitely after that.
  463. * @author Alexander Freytag
  464. * @date 02-01-2014 (dd-mm-yyyy)
  465. *
  466. * @param example new feature vector
  467. */
  468. void addExample(const NICE::SparseVector * _example, const NICE::ParameterizedFunction *_pf = NULL);
  469. /**
  470. * @brief Add multiple new example to the feature-storage. You have to update the corresponding variables explicitely after that.
  471. * @author Alexander Freytag
  472. * @date 02-01-2014 (dd-mm-yyyy)
  473. *
  474. * @param newExamples new feature vectors
  475. */
  476. void addMultipleExamples(const std::vector<const NICE::SparseVector * > & _newExamples, const NICE::ParameterizedFunction *_pf = NULL);
  477. };
  478. } // namespace
  479. #endif