PartlyPrecomputedMatrix.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Partly Precomputed version of a matrix for quadratic programming
6  *
7  *
8  * \par
9  *
10  *
11  *
12  * \author T. Glasmachers, A. Demircioglu
13  * \date 2007-2014
14  *
15  *
16  * \par Copyright 1995-2017 Shark Development Team
17  *
18  * <BR><HR>
19  * This file is part of Shark.
20  * <http://shark-ml.org/>
21  *
22  * Shark is free software: you can redistribute it and/or modify
23  * it under the terms of the GNU Lesser General Public License as published
24  * by the Free Software Foundation, either version 3 of the License, or
25  * (at your option) any later version.
26  *
27  * Shark is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  *
32  * You should have received a copy of the GNU Lesser General Public License
33  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
34  *
35  */
36 //===========================================================================
37 
38 
39 #ifndef SHARK_LINALG_PARTLYPRECOMPUTEDMATRIX_H
40 #define SHARK_LINALG_PARTLYPRECOMPUTEDMATRIX_H
41 
42 #include <shark/Data/Dataset.h>
43 #include <shark/LinAlg/Base.h>
44 
45 #include <vector>
46 #include <cmath>
47 
48 
49 namespace shark
50 {
51 
52 ///
53 /// \brief Partly Precomputed version of a matrix for quadratic programming
54 ///
55 /// \par
56 /// The PartlyPrecomputedMatrix class computes all pairs of kernel
57 /// evaluations that fits the given cachesize in its constructor and
58 /// stores them im memory.
59 ///
60 /// \par
61 /// Use of this class may be beneficial for certain model
62 /// selection strategies, where the whole matrix does not fit into
63 /// memory, and the LRU cache will produce too much hit rates,
64 /// so that at least partially caching the kernel matrix will help.
65 /// In particular this will help the KernelSGD/Pegasos algorithm.
66 ///
67 template <class Matrix>
68 class PartlyPrecomputedMatrix
69 {
70 public:
71  typedef typename Matrix::QpFloatType QpFloatType;
72 
73  /// Constructor
74  /// \param[in] base matrix to be cached. it is assumed that this matrix is not precomputed,
75  /// but the (costy) computation takes place every time an entry is queried.
76  /// \param[in] cachesize size of the cache to use in bytes. the size of the cached matrix will
77  // depend on this value.
78  PartlyPrecomputedMatrix(Matrix* base, std::size_t cachesize = 0x4000000)
79  : m_cacheSize(cachesize)
80  , m_baseMatrix(base)
81  {
82  SHARK_RUNTIME_CHECK(m_baseMatrix || m_baseMatrix ->size() == 0, "Cannot cache a NULL matrix!");
83 
84  // remember the original size of the matrix
85  m_originalNumberOfRows = m_baseMatrix -> size();
86 
87  // determine how many bytes we need for a single row
88  size_t rowSizeBytes = m_originalNumberOfRows * sizeof(QpFloatType);
89 
90  // how many rows fit into our cache?
91  size_t m_nRows = (size_t) m_cacheSize / rowSizeBytes;
92  SHARK_RUNTIME_CHECK(m_nRows, "Cache size is smaller than the size of a row!");
93 
94  // if we have more space than needed, well, we do not need it.
95  if(m_nRows > m_originalNumberOfRows)
96  m_nRows = m_originalNumberOfRows ;
97 
98  // resize matrix
99  m_cachedMatrix.resize(m_nRows, m_baseMatrix ->size());
100 
101  // copy the rows
102  for(std::size_t r = 0; r < m_cachedMatrix.size1(); r++)
103  {
104  for(std::size_t j = 0; j < m_baseMatrix->size(); j++)
105  {
106  m_cachedMatrix(r, j) = (*m_baseMatrix)(r, j);
107  }
108  }
109  }
110 
111 
112 
113  /// return, if a given row is cached
114  /// \param[in] k row to check
115  /// \return is given row in cached matrix or not?
116  bool isCached(std::size_t k) const
117  {
118  if(k < m_cachedMatrix.size1())
119  return true;
120  return false;
121  }
122 
123 
124 
125  /// return a complete row of the matrix.
126  /// if the row is cached, it will be returned from there, if not, it will
127  /// be recomputed on-the-fly and not stored.
128  /// param[in] k row to compute
129  /// param[in] storage vector to store the row. must be the same size as a row!
130  void row(std::size_t k, blas::vector<QpFloatType> &storage) const
131  {
132  RANGE_CHECK(k < m_originalNumberOfRows);
133  RANGE_CHECK(0 <= k);
134  SIZE_CHECK(storage.size() == m_cachedMatrix.size2());
135  if(isCached(k) == true)
136  {
137  for(std::size_t j = 0; j < m_cachedMatrix.size2(); j++)
138  {
139  storage[j] = m_cachedMatrix(k, j);
140  }
141  }
142  else
143  {
144  for(std::size_t j = 0; j < m_cachedMatrix.size2(); j++)
145  {
146  storage[j] = (*m_baseMatrix)(k, j);
147  }
148  }
149  }
150 
151 
152 
153  /// return a single matrix entry
154  /// param[in] i row of entry
155  /// param[in] j column entry
156  /// @return value of matrix at given position
157  QpFloatType operator()(std::size_t i, std::size_t j) const
158  {
159  return entry(i, j);
160  }
161 
162 
163 
164  /// return a single matrix entry
165  /// param[in] i row of entry
166  /// param[in] j column entry
167  /// @return value of matrix at given position
168  QpFloatType entry(std::size_t i, std::size_t j) const
169  {
170  // check if we have to compute that or not
171  if(isCached(i))
172  return m_cachedMatrix(i, j);
173 
174  // ok, need to compute that element
175  return (*m_baseMatrix)(i, j);
176  }
177 
178 
179 
180  /// return the number of cached rows
181  /// @return number of rows that are cached
182  std::size_t size() const
183  {
184  return m_cachedMatrix.size();
185  }
186 
187 
188 
189  /// return size of cached matrix in QpFloatType units
190  /// @return the capacity of the cached matrix in QpFloatType units
191  std::size_t getMaxCacheSize()
192  {
193  return m_cachedMatrix.size() * m_cachedMatrix.size2();
194  }
195 
196 
197 
198  /// return the dimension of a row in the cache (as we do not shorten our
199  /// rows, this must be the same as the dimension of a row in the original kernel matrix).
200  /// @return dimension of any cached row
201  std::size_t getCacheRowSize() const
202  {
203  return m_cachedMatrix.size2();
204  }
205 
206 
207 
208 protected:
209  /// container for precomputed values
210  blas::matrix<QpFloatType> m_cachedMatrix;
211 
212  // maximal size of cache
213  size_t m_cacheSize;
214 
215  // original kernel matrix, will be accessed if entries outsied the cache are requested
216  Matrix* m_baseMatrix;
217 
218  // remember how big the original matrix was to prevent access errors
219  size_t m_originalNumberOfRows;
220 };
221 
222 }
223 #endif