SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ANOVAKernel.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2011 Andrew Tereskin
8  * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
9  */
10 
14 
15 using namespace shogun;
16 
17 CANOVAKernel::CANOVAKernel(): CDotKernel(0), cardinality(1.0)
18 {
20 }
21 
22 CANOVAKernel::CANOVAKernel(int32_t cache, int32_t d)
23 : CDotKernel(cache), cardinality(d)
24 {
26 }
27 
29  CDenseFeatures<float64_t>* l, CDenseFeatures<float64_t>* r, int32_t d, int32_t cache)
30  : CDotKernel(cache), cardinality(d)
31 {
33  init(l, r);
34 }
35 
37 {
38  cleanup();
39 }
40 
41 bool CANOVAKernel::init(CFeatures* l, CFeatures* r)
42 {
43  cleanup();
44 
45  bool result = CDotKernel::init(l,r);
46 
48  return result;
49 }
50 
51 float64_t CANOVAKernel::compute(int32_t idx_a, int32_t idx_b)
52 {
53  return compute_rec1(idx_a, idx_b);
54 }
55 
56 float64_t CANOVAKernel::compute_rec1(int32_t idx_a, int32_t idx_b)
57 {
58  int32_t alen, blen;
59  bool afree, bfree;
60 
61  float64_t* avec=
62  ((CDenseFeatures<float64_t>*) lhs)->get_feature_vector(idx_a, alen, afree);
63  float64_t* bvec=
64  ((CDenseFeatures<float64_t>*) rhs)->get_feature_vector(idx_b, blen, bfree);
65  ASSERT(alen==blen)
66 
67  float64_t result = compute_recursive1(avec, bvec, alen);
68 
69  ((CDenseFeatures<float64_t>*) lhs)->free_feature_vector(avec, idx_a, afree);
70  ((CDenseFeatures<float64_t>*) rhs)->free_feature_vector(bvec, idx_b, bfree);
71 
72  return result;
73 }
74 
75 float64_t CANOVAKernel::compute_rec2(int32_t idx_a, int32_t idx_b)
76 {
77  int32_t alen, blen;
78  bool afree, bfree;
79 
80  float64_t* avec=
81  ((CDenseFeatures<float64_t>*) lhs)->get_feature_vector(idx_a, alen, afree);
82  float64_t* bvec=
83  ((CDenseFeatures<float64_t>*) rhs)->get_feature_vector(idx_b, blen, bfree);
84  ASSERT(alen==blen)
85 
86  float64_t result = compute_recursive2(avec, bvec, alen);
87 
88  ((CDenseFeatures<float64_t>*) lhs)->free_feature_vector(avec, idx_a, afree);
89  ((CDenseFeatures<float64_t>*) rhs)->free_feature_vector(bvec, idx_b, bfree);
90 
91  return result;
92 }
93 
95 {
96  SG_ADD(&cardinality, "cardinality", "Kernel cardinality.", MS_AVAILABLE);
97 }
98 
99 
100 float64_t CANOVAKernel::compute_recursive1(float64_t* avec, float64_t* bvec, int32_t len)
101 {
102  int32_t DP_len=(cardinality+1)*(len+1);
103  float64_t* DP = SG_MALLOC(float64_t, DP_len);
104 
105  ASSERT(DP)
106  int32_t d=cardinality;
107  int32_t offs=cardinality+1;
108 
109  ASSERT(DP_len==(len+1)*offs)
110 
111  for (int32_t j=0; j < len+1; j++)
112  DP[j] = 1.0;
113 
114  for (int32_t k=1; k < d+1; k++)
115  {
116  // TRAP d>len case
117  if (k-1>=len)
118  return 0.0;
119 
120  DP[k*offs+k-1] = 0;
121  for (int32_t j=k; j < len+1; j++)
122  DP[k*offs+j]=DP[k*offs+j-1]+avec[j-1]*bvec[j-1]*DP[(k-1)*offs+j-1];
123  }
124 
125  float64_t result=DP[d*offs+len];
126 
127  SG_FREE(DP);
128 
129  return result;
130 }
131 
132 float64_t CANOVAKernel::compute_recursive2(float64_t* avec, float64_t* bvec, int32_t len)
133 {
134  float64_t* KD = SG_MALLOC(float64_t, cardinality+1);
135  float64_t* KS = SG_MALLOC(float64_t, cardinality+1);
136  float64_t* vec_pow = SG_MALLOC(float64_t, len);
137 
138  ASSERT(vec_pow)
139  ASSERT(KS)
140  ASSERT(KD)
141 
142  int32_t d=cardinality;
143  for (int32_t i=0; i < len; i++)
144  vec_pow[i] = 1;
145 
146  for (int32_t k=1; k < d+1; k++)
147  {
148  KS[k] = 0;
149  for (int32_t i=0; i < len; i++)
150  {
151  vec_pow[i] *= avec[i]*bvec[i];
152  KS[k] += vec_pow[i];
153  }
154  }
155 
156  KD[0] = 1;
157  for (int32_t k=1; k < d+1; k++)
158  {
159  float64_t sum = 0;
160  for (int32_t s=1; s < k+1; s++)
161  {
162  float64_t sign = 1.0;
163  if (s % 2 == 0)
164  sign = -1.0;
165 
166  sum += sign*KD[k-s]*KS[s];
167  }
168 
169  KD[k] = sum / k;
170  }
171  float64_t result=KD[d];
172  SG_FREE(vec_pow);
173  SG_FREE(KS);
174  SG_FREE(KD);
175 
176  return result;
177 }
178 
180 {
181  if (!kernel)
182  return NULL;
183 
184  REQUIRE(kernel->get_kernel_type()==K_ANOVA, "Provided kernel is "
185  "not of type CANOVAKernel, but type %d!\n",
186  kernel->get_kernel_type())
187 
188  /* since an additional reference is returned */
189  SG_REF(kernel);
190  return (CANOVAKernel*)kernel;
191 }

SHOGUN Machine Learning Toolbox - Documentation