Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 271 lines (231 sloc) 6.022 kB
bb0d65c @ianbarber adding multivariate gradient descent example
authored
1 <?php
2
3 class MVGradient {
4
5 protected $data;
6 protected $learning_rate = 0.1;
7
8 /**
9 * Set the data for the function.
10 * @param array - 0 => (x1, x2, x3, x4), 1 => y
11 */
12 public function set_data($data) {
13 $this->data = $this->scale_data($data);
14 }
15
16 /**
17 * Set the rate at which the algorithm updates.
18 * Normal values are 0.1 - 0.001
19 *
20 * @param float $rate
21 * @return void
22 */
23 public function set_learning_rate($rate) {
24 $this->learning_rate = $rate;
25 }
26
27 /**
28 * Normalise variance and scale data to:
29 * xi - avg(xi) / range(max-min)
30 * so we get in a -0.5 - 0.5 range with an
31 * avg of 0
32 * - this is a bit of clunky method!
33 */
34 protected function scale_data($data) {
35 $minmax = array();
36 $rows = count($data);
37
38 foreach($data as $key => $row) {
39 foreach($row[0] as $id => $val) {
40 /* Initialise Arrays */
41 if(!isset($minmax[$id])) {
42 $minmax[$id] = array();
43 $minmax[$id]['min'] = false;
44 $minmax[$id]['max'] = false;
45 $minmax[$id]['total'] = 0;
46 }
47
48 /* Get stats */
49 if( $minmax[$id]['min'] == false ||
50 $minmax[$id]['min'] > $val) {
51 $minmax[$id]['min'] = $val;
52 }
53 if( $minmax[$id]['max'] == false ||
54 $minmax[$id]['max'] < $val) {
55 $minmax[$id]['max'] = $val;
56 }
57
58 $minmax[$id]['total'] += $val;
59 }
60 }
61
62 /* Compute average and variance */
63 foreach($minmax as $id => $row) {
64 $minmax[$id]['var'] = $row['max'] - $row['min'];
65 $minmax[$id]['avg'] = $row['total'] / $rows;
66
67 }
68
69 foreach($data as $key => $row) {
70 foreach($row[0] as $id => $val) {
71 $data[$key][0][$id] = ( $val - $minmax[$id]['avg'] )
72 / $minmax[$id]['var'];
73 }
74 }
75
76 return $data;
77 }
78
79 /**
80 * Update the parameters, including using a dummy row value
81 * of 1 for the first parameter.
82 *
83 * @param array $params
84 * @return array
85 */
86 protected function learn($params) {
87 $data_rate = 1/count($this->data);
88
89 foreach($params as $id => $p) {
90 foreach($this->data as $row) {
91 $score = $this->mv_hypothesis($row[0], $params) - $row[1];
92
93 // Update parameters
94 $params[$id] -= $this->learning_rate *
95 ($data_rate *
96 ( $score * ($id == 0 ? 1 : $row[0][$id-1]) )
97 );
98 }
99 }
100
101 return $params;
102 }
103
104 /**
105 * Generate a score based on the data and passed parameters
106 *
107 * @param array $params
108 * @return int
109 */
110 protected function mv_hypothesis($rowdata, $params) {
111 $score = $params[0];
112 foreach($rowdata as $id => $value) {
113 $score += $value * $params[$id+1];
114 }
115 return $score;
116 }
117
118 /**
119 * Return the sum of squared error score
120 *
121 * @param array $params
122 * @return int
123 */
124 public function score($params) {
125 $score = 0;
126 foreach($this->data as $row) {
127 $score += pow($this->mv_hypothesis($row[0], $params) - $row[1], 2);
128 }
129 return $score;
130 }
131
132 /**
133 * Update parameters
134 *
135 * @param string $data
136 * @param string $parameters
137 * @return array parameters
138 */
139 function mv_gradient($parameters) {
140 $score = $this->score($parameters);
141
142 // Create a new hypothesis to test our score
143 $parameters = $this->learn($parameters);
144
145 if($score < $this->score($parameters)) {
146 return false;
147 }
148
149 return $parameters;
150 }
151
152 /**
153 * Find the parameters that best fit the data
154 *
155 * @param int $iterations - max iterations to run
156 * @param array $defaults - optional starting params
157 * @return array - best fit parameters
158 */
159 public function find_params($iterations = 5000, $defaults = null) {
160 if(!$defaults) {
161 $defaults = array_fill(0, count($this->data[0][0]) + 1, 0);
162 }
163
164 $parameters = $defaults;
165 $iters = 0;
166 do {
167 $last_parameters = $parameters;
168 $parameters = $this->mv_gradient($parameters);
169 } while($parameters != false && $iters++ < $iterations);
170
171 return $parameters ? $parameters : $last_parameters;
172 }
173
174 }
175
8c09c2a @ianbarber Adding following rank code
authored
176 /* Nice regular data for testing */
bb0d65c @ianbarber adding multivariate gradient descent example
authored
177 $data = array(
8c09c2a @ianbarber Adding following rank code
authored
178 array(array(2, 4000, 0.5), 2+2+(2*4)+(3*5)),
179 array(array(2, 4000, 0.4), 2+2+(2*4)+(3*4)),
180 array(array(2, 4000, 0.6), 2+2+(2*4)+(3*6)),
181 array(array(1, 5000, 0.5), 2+1+(2*5)+(3*5)),
182 array(array(2, 5000, 0.1), 2+2+(2*5)+(3*1)),
bb0d65c @ianbarber adding multivariate gradient descent example
authored
183 );
184
185 class PolyMV extends MVGradient {
186
187 /**
188 * Skip scaling just for the example
189 */
190 protected function scale_data($data) {
191 return $data;
192 }
193
194 /**
195 * Generate a score based on the data and passed parameters
196 *
197 * @param array $params
198 * @return int
199 */
200 protected function mv_hypothesis($rowdata, $params) {
201 $score = $params[0];
202 foreach($rowdata as $id => $value) {
203 $score += pow($value, $id+2) * $params[$id+1];
204 }
205 return $score;
206 }
207
208 /**
209 * Update the parameters, including using a dummy row value
210 * of 1 for the first parameter.
211 *
212 * @param array $params
213 * @return array
214 */
215 protected function learn($params) {
216 $data_rate = 1/count($this->data);
217
218 foreach($params as $id => $p) {
219 foreach($this->data as $row) {
220 $score = $this->mv_hypothesis($row[0], $params) - $row[1];
221
222 // Update parameters
223 // We have to multiply by an appropriate power as part of the
224 // partial derivative
225 $params[$id] -= $this->learning_rate *
226 ($data_rate *
227 ( $score * ($id == 0 ? 1 : pow($row[0][$id-1], $id+1)) )
228 );
229 }
230 }
231
232 return $params;
233 }
234 }
8c09c2a @ianbarber Adding following rank code
authored
235 /*
236
237
238 $iterations = array(10, 100, 500, 1000, 2000, 5000, 10000);
239 $mvg = new MVGradient();
240 $mvg->set_data($data);
241 foreach(array(0.1, 0.01, 0.001, 0.001) as $rate) {
242 $mvg->set_learning_rate($rate);
243 foreach($iterations as $i) {
244 $params = $mvg->find_params($i);
245 echo $mvg->score($params), "\n";
246 }
247 echo "\n";
248 }
249 die();
250
251
252 // We have a polynomial example here
253
254 $data = array(
255 array(array(2, 2), 1+(3*pow(2, 2))+(2*pow(2, 3))),
256 array(array(3, 3), 1+(3*pow(3, 2))+(2*pow(3, 3))),
257 array(array(4, 4), 1+(3*pow(4, 2))+(2*pow(4, 3))),
258 array(array(5, 5), 1+(3*pow(5, 2))+(2*pow(5, 3))),
259 );
bb0d65c @ianbarber adding multivariate gradient descent example
authored
260
261 $iterations = array(10000);
262 $mvg = new PolyMV();
263 $mvg->set_data($data);
264 $mvg->set_learning_rate(0.001);
265 foreach($iterations as $i) {
266 $params = $mvg->find_params($i);
267 echo $mvg->score($params), "\n";
268 var_dump($params);
269 }
270 echo "\n";
8c09c2a @ianbarber Adding following rank code
authored
271 */
Something went wrong with that request. Please try again.