DifferenceKernelMatrix.h
Go to the documentation of this file.
1//===========================================================================
2/*!
3 *
4 *
5 * \brief Kernel matrix for SVM ranking.
6 *
7 *
8 * \par
9 *
10 *
11 *
12 * \author T. Glasmachers
13 * \date 2016
14 *
15 *
16 * \par Copyright 1995-2017 Shark Development Team
17 *
18 * <BR><HR>
19 * This file is part of Shark.
20 * <https://shark-ml.github.io/Shark/>
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_DIFFERENCEKERNELMATRIX_H
40#define SHARK_LINALG_DIFFERENCEKERNELMATRIX_H
41
42#include <shark/Data/Dataset.h>
43#include <shark/Data/DataView.h>
44#include <shark/LinAlg/Base.h>
45
46#include <vector>
47#include <utility>
48#include <cmath>
49
50
51namespace shark {
52
53
54///
55/// \brief SVM ranking matrix
56///
57/// \par
58/// The DifferenceKernelMatrix class is kernel matrix with entries of
59/// the form \f$ K_{i,j} = k(g_i, g_j) - k(g_i, s_j) - k(s_i, g_j) + k(s_i, s_j) \f$
60/// where for data consisting of pairs of point \f$ (g_i, s_i) \f$.
61/// This matrix form is needed in SVM ranking problems.
62///
63template <class InputType, class CacheType>
64class DifferenceKernelMatrix
65{
66public:
67 typedef CacheType QpFloatType;
68
69 /// Constructor.
70 DifferenceKernelMatrix(
71 AbstractKernelFunction<InputType> const& kernel,
72 Data<InputType> const& dataset,
73 std::vector<std::pair<std::size_t, std::size_t>> const& pairs)
74 : m_kernel(kernel)
75 , m_dataset(dataset)
76 , m_indices(pairs.size())
77 {
78 DataView< Data<InputType> const > view(dataset);
79 for (std::size_t i=0; i<pairs.size(); i++)
80 {
81 std::pair<std::size_t, std::size_t> const& p = pairs[i];
82 m_indices[i] = std::make_tuple(
83 view.batch(p.first), view.positionInBatch(p.first),
84 view.batch(p.second), view.positionInBatch(p.second));
85 }
86 }
87
88
89 /// return a single matrix entry
90 QpFloatType operator () (std::size_t i, std::size_t j) const
91 { return entry(i, j); }
92
93 /// return a single matrix entry
94 QpFloatType entry(std::size_t i, std::size_t j) const
95 {
96 std::tuple<std::size_t, std::size_t, std::size_t, std::size_t> const& pi = m_indices[i];
97 std::tuple<std::size_t, std::size_t, std::size_t, std::size_t> const& pj = m_indices[j];
98 std::size_t batch_si = std::get<0>(pi);
99 std::size_t index_si = std::get<1>(pi);
100 std::size_t batch_gi = std::get<2>(pi);
101 std::size_t index_gi = std::get<3>(pi);
102 std::size_t batch_sj = std::get<0>(pj);
103 std::size_t index_sj = std::get<1>(pj);
104 std::size_t batch_gj = std::get<2>(pj);
105 std::size_t index_gj = std::get<3>(pj);
106 typedef typename Data<InputType>::const_element_reference reference;
107 reference si = getBatchElement(m_dataset.batch(batch_si), index_si);
108 reference gi = getBatchElement(m_dataset.batch(batch_gi), index_gi);
109 reference sj = getBatchElement(m_dataset.batch(batch_sj), index_sj);
110 reference gj = getBatchElement(m_dataset.batch(batch_gj), index_gj);
111 double k_gi_gj = m_kernel(gi, gj);
112 double k_gi_sj = m_kernel(gi, sj);
113 double k_si_gj = m_kernel(si, gj);
114 double k_si_sj = m_kernel(si, sj);
115 return (k_gi_gj - k_gi_sj - k_si_gj + k_si_sj);
116 }
117
118 /// \brief Computes the i-th row of the kernel matrix.
119 ///
120 /// The entries start,...,end of the i-th row are computed and stored in storage.
121 /// There must be enough room for this operation preallocated.
122 void row(std::size_t i, std::size_t start, std::size_t end, QpFloatType* storage) const {
123 for (std::size_t j = start; j < end; j++) storage[j-start] = entry(i, j);
124 }
125
126 /// \brief Computes the kernel-matrix
127 template<class M>
128 void matrix(blas::matrix_expression<M, blas::cpu_tag>& storage) const {
129 for (std::size_t i = 0; i != size(); ++i) {
130 for (std::size_t j = 0; j != size(); ++j) {
131 storage()(i, j) = entry(i, j);
132 }
133 }
134 }
135
136 /// swap two variables
137 void flipColumnsAndRows(std::size_t i, std::size_t j)
138 {
139 using namespace std;
140 swap(m_indices[i], m_indices[j]);
141 }
142
143 /// return the size of the quadratic matrix
144 std::size_t size() const
145 { return m_indices.size(); }
146
147protected:
148 /// underlying kernel function
149 AbstractKernelFunction<InputType> const& m_kernel;
150
151 /// underlying set of points
152 Data<InputType> const& m_dataset;
153
154 /// pairs of points defining the matrix components
155 std::vector<std::tuple<std::size_t, std::size_t, std::size_t, std::size_t>> m_indices;
156};
157
158}
159#endif