1 // This is rpl/rrel/rrel_kernel_density_obj.cxx
2 #include <iostream>
3 #include <algorithm>
4 #include "rrel_kernel_density_obj.h"
5 #include <rrel/rrel_muset_obj.h>
6 #include "vnl/vnl_vector.h"
7 #include "vnl/vnl_math.h"
8 #ifdef _MSC_VER
9 # include "vcl_msvc_warnings.h"
10 #endif
11 #include <cassert>
12
13 namespace {
shft2(double & a,double & b,const double c)14 inline void shft2(double &a, double &b, const double c)
15 {
16 a = b;
17 b = c;
18 }
19
shft3(double & a,double & b,double & c,const double d)20 inline void shft3(double &a, double &b, double &c, const double d)
21 {
22 a = b;
23 b = c;
24 c = d;
25 }
26 }
27
rrel_kernel_density_obj(rrel_kernel_scale_type scale_type)28 rrel_kernel_density_obj::rrel_kernel_density_obj(
29 rrel_kernel_scale_type scale_type)
30 : scale_type_(scale_type)
31
32 {}
33
34 double
fcn(vect_const_iter,vect_const_iter,vect_const_iter,vnl_vector<double> *) const35 rrel_kernel_density_obj::fcn(vect_const_iter /*res_begin*/, vect_const_iter /*res_end*/,
36 vect_const_iter /*scale_begin*/,
37 vnl_vector<double>* /*param_vector*/ ) const
38 {
39 std::cerr << "rrel_kernel_density_obj::fcn() not implemented\n";
40 return 0;
41 }
42
43 double
fcn(vect_const_iter res_begin,vect_const_iter res_end,double prior_scale,vnl_vector<double> *) const44 rrel_kernel_density_obj::fcn(vect_const_iter res_begin,
45 vect_const_iter res_end,
46 double prior_scale,
47 vnl_vector<double>* ) const
48 {
49 double h = bandwidth ( res_begin, res_end, prior_scale );
50 assert ( h != 0 );
51 double x = best_x ( res_begin, res_end, prior_scale );
52
53 return -1 * kernel_density( res_begin, res_end, x, h );
54 }
55
56 double
best_x(vect_const_iter res_begin,vect_const_iter res_end,double prior_scale) const57 rrel_kernel_density_obj::best_x(vect_const_iter res_begin,
58 vect_const_iter res_end,
59 double prior_scale) const
60 {
61 if (fix_x_)
62 return 0;
63
64 //Golden Section Search is adapted from "Numerical Recipes in C++"
65 //to find x that maximizes kernel_density.
66 const double R = 0.61803399, C = 1.0 - R; //The golden ratios.
67 double f1, f2, x0, x1, x2, x3;
68 double tol = 1.0e-9;
69 double f0 = 0;
70
71 double h = bandwidth(res_begin, res_end, prior_scale);
72 assert(h!=0);
73
74 std::vector<double> sort_res( res_begin, res_end );
75 std::sort( sort_res.begin(), sort_res.end() );
76
77 unsigned int loc = 0;
78 unsigned int i = 0;
79 for ( ; i<sort_res.size(); ++i ) {
80 double x = sort_res[i];
81 double f = kernel_density( res_begin, res_end, x, h );
82 if (f > f0) {
83 f0 = f;
84 loc = i;
85 }
86 }
87
88 x0 = sort_res[loc-1];
89 x3 = sort_res[loc+1];
90
91 if ( vnl_math::abs( x3 - sort_res[loc] ) > vnl_math::abs( sort_res[loc] - x0 ) ) {
92 x1 = sort_res[loc];
93 x2 = sort_res[loc] + C * ( x3 - sort_res[loc] );
94 }
95 else {
96 x2 = sort_res[loc];
97 x1 = sort_res[loc] - C * ( sort_res[loc] - x0 );
98 }
99
100 f1 = kernel_density( res_begin, res_end, x1, h );
101 f2 = kernel_density( res_begin, res_end, x2, h );
102 while ( vnl_math::abs( x3 - x0 ) >
103 tol * vnl_math::abs( x1 ) + vnl_math::abs( x2 ) ) {
104 if ( f2 > f1 ) {
105 shft3( x0, x1, x2, R * x2 + C * x3 );
106 shft2( f1, f2, kernel_density( res_begin, res_end, x2, h ) );
107 }
108 else {
109 shft3( x3, x2, x1, R * x1 + C * x0 );
110 shft2( f2, f1, kernel_density( res_begin, res_end, x1, h ) );
111 }
112 }
113 if (f1 < f2)
114 return x2;
115 else
116 return x1;
117 }
118
119 double
bandwidth(vect_const_iter res_begin,vect_const_iter res_end,double prior_scale) const120 rrel_kernel_density_obj::bandwidth(vect_const_iter res_begin, vect_const_iter res_end,
121 double prior_scale) const
122 {
123 std::vector<double>::difference_type n = res_end - res_begin;
124 double scale = 1.0;
125
126 switch ( scale_type_ )
127 {
128 case RREL_KERNEL_MAD: {
129 //A median absolute deviations (MAD) scale estimate.
130
131 //Here I avoid using rrel_util_median_abs_dev_scale
132 //because it assumes residuals are zero-based and have a Gaussian distribution.
133
134 std::vector<double> residuals(res_begin, res_end);
135 auto loc = residuals.begin() + n / 2;
136 std::nth_element( residuals.begin(), loc, residuals.end() );
137
138 double res_median = *loc;
139 std::vector<double> abs_res_median;
140 abs_res_median.reserve( n );
141 for (std::vector<double>::difference_type i=0; i<n; ++i ) {
142 abs_res_median.push_back( vnl_math::abs( residuals[i] - res_median ) );
143 }
144 loc = abs_res_median.begin() + n / 2;
145 std::nth_element( abs_res_median.begin(), loc, abs_res_median.end() );
146 // c=0.5 is chosen to avoid over-smoothing of the estimated density.
147 scale = 0.5 * (*loc);
148 break;
149 }
150
151 case RREL_KERNEL_PRIOR:
152 scale = prior_scale;
153 break;
154
155 case RREL_KERNEL_MUSE: {
156 rrel_muset_obj muse( (int)n );
157 scale = muse.fcn( res_begin, res_end );
158 break; }
159
160 default:
161 assert(!"invalid scale_type");
162 }
163
164 // h = [243 * R(K) / 35 / Mu(K)^2 / n]^0.2 * scale
165 // R(K) = Integral ( K(u)^2 ) du
166 // Mu(K) = Integral ( u^2 * K(u) ) du
167 const double c = 65610.0 / 143;
168 return std::pow( c / n , 0.2 ) * scale;
169 }
170
171 double
kernel_density(vect_const_iter res_begin,vect_const_iter res_end,double x,double h) const172 rrel_kernel_density_obj::kernel_density(vect_const_iter res_begin,
173 vect_const_iter res_end,
174 double x,
175 double h) const
176 {
177 double f=0;
178 std::vector<double>::difference_type n = res_end - res_begin;
179 for ( ; res_begin!= res_end; ++res_begin ) {
180 f += kernel_function( ( *res_begin - x ) / h );
181 }
182 f /= n*h;
183 return f;
184 }
185
186 double
kernel_function(double u) const187 rrel_kernel_density_obj::kernel_function(double u) const
188 {
189 if (vnl_math::abs(u) > 1)
190 return 0;
191
192 double t = 1 - u * u;
193 return 1.09375 * t * t * t;
194 }
195