Test Failed
Pull Request — master (#63)
by
unknown
02:47
created

mp::adds()   A

Complexity

Conditions 2
Paths 2

Size

Total Lines 9
Code Lines 5

Duplication

Lines 9
Ratio 100 %

Importance

Changes 0
Metric Value
dl 9
loc 9
rs 9.6666
c 0
b 0
f 0
cc 2
eloc 5
nc 2
nop 3
1
<?php declare(strict_types=1);
2
3
namespace Phpml\Helper\Optimizer;
4
5
/**
6
 * Conjugate Gradient method to solve a non-linear f(x) with respect to unknown x
7
 * See https://en.wikipedia.org/wiki/Nonlinear_conjugate_gradient_method)
8
 *
9
 * The method applied below is explained in the below document in a practical manner
10
 *  - http://web.cs.iastate.edu/~cs577/handouts/conjugate-gradient.pdf
11
 *
12
 * However it is compliant with the general Conjugate Gradient method with
13
 * Fletcher-Reeves update method. Note that, the f(x) is assumed to be one-dimensional
14
 * and one gradient is utilized for all dimensions in the given data.
15
 */
16
class ConjugateGradient extends GD
17
{
18
    /**
19
     * @param array $samples
20
     * @param array $targets
21
     * @param \Closure $gradientCb
22
     *
23
     * @return array
24
     */
25
    public function runOptimization(array $samples, array $targets, \Closure $gradientCb)
26
    {
27
        $this->samples = $samples;
28
        $this->targets = $targets;
29
        $this->gradientCb = $gradientCb;
30
        $this->sampleCount = count($samples);
31
        $this->costValues = [];
32
33
        $d = mp::muls($this->gradient($this->theta), -1);
34
35
        for ($i=0; $i < $this->maxIterations; $i++) {
36
            // Obtain α that minimizes f(θ + α.d)
37
            $alpha = $this->getAlpha(array_sum($d));
38
39
            // θ(k+1) = θ(k) + α.d
40
            $thetaNew = $this->getNewTheta($alpha, $d);
41
42
            // β = ||∇f(x(k+1))||²  ∕  ||∇f(x(k))||²
0 ignored issues
show
Unused Code Comprehensibility introduced by
44% of this comment could be valid code. Did you maybe forget this after debugging?

Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it.

The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production.

This check looks for comments that seem to be mostly valid code and reports them.

Loading history...
43
            $beta = $this->getBeta($thetaNew);
44
45
            // d(k+1) =–∇f(x(k+1)) + β(k).d(k)
0 ignored issues
show
Unused Code Comprehensibility introduced by
40% of this comment could be valid code. Did you maybe forget this after debugging?

Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it.

The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production.

This check looks for comments that seem to be mostly valid code and reports them.

Loading history...
46
            $d = $this->getNewDirection($thetaNew, $beta, $d);
47
48
            // Save values for the next iteration
49
            $oldTheta = $this->theta;
50
            $this->costValues[] = $this->cost($thetaNew);
51
52
            $this->theta = $thetaNew;
53
            if ($this->earlyStop($oldTheta)) {
54
                break;
55
            }
56
        }
57
58
        return $this->theta;
59
    }
60
61
    /**
62
     * Executes the callback function for the problem and returns
63
     * sum of the gradient for all samples & targets.
64
     *
65
     * @param array $theta
66
     *
67
     * @return float
68
     */
69
    protected function gradient(array $theta)
70
    {
71
        list($_, $gradient, $_) = parent::gradient($theta);
0 ignored issues
show
Unused Code introduced by
The assignment to $_ is unused. Consider omitting it like so list($first,,$third).

This checks looks for assignemnts to variables using the list(...) function, where not all assigned variables are subsequently used.

Consider the following code example.

<?php

function returnThreeValues() {
    return array('a', 'b', 'c');
}

list($a, $b, $c) = returnThreeValues();

print $a . " - " . $c;

Only the variables $a and $c are used. There was no need to assign $b.

Instead, the list call could have been.

list($a,, $c) = returnThreeValues();
Loading history...
72
73
        return $gradient;
74
    }
75
76
    /**
77
     * Returns the value of f(x) for given solution
78
     *
79
     * @param array $theta
80
     *
81
     * @return float
82
     */
83
    protected function cost(array $theta)
84
    {
85
        list($cost, $_, $_) = parent::gradient($theta);
0 ignored issues
show
Comprehensibility Bug introduced by
It seems like you call parent on a different method (gradient() instead of cost()). Are you sure this is correct? If so, you might want to change this to $this->gradient().

This check looks for a call to a parent method whose name is different than the method from which it is called.

Consider the following code:

class Daddy
{
    protected function getFirstName()
    {
        return "Eidur";
    }

    protected function getSurName()
    {
        return "Gudjohnsen";
    }
}

class Son
{
    public function getFirstName()
    {
        return parent::getSurname();
    }
}

The getFirstName() method in the Son calls the wrong method in the parent class.

Loading history...
Bug introduced by
Why assign $_ to itself?

This checks looks for cases where a variable has been assigned to itself.

This assignement can be removed without consequences.

Loading history...
Unused Code introduced by
The assignment to $_ is unused. Consider omitting it like so list($first,,$third).

This checks looks for assignemnts to variables using the list(...) function, where not all assigned variables are subsequently used.

Consider the following code example.

<?php

function returnThreeValues() {
    return array('a', 'b', 'c');
}

list($a, $b, $c) = returnThreeValues();

print $a . " - " . $c;

Only the variables $a and $c are used. There was no need to assign $b.

Instead, the list call could have been.

list($a,, $c) = returnThreeValues();
Loading history...
86
87
        return array_sum($cost) / $this->sampleCount;
88
    }
89
90
    /**
91
     * Calculates alpha that minimizes the function f(θ + α.d)
92
     * by performing a line search that does not rely upon the derivation.
93
     *
94
     * There are several alternatives for this function. For now, we
95
     * prefer a method inspired from the bisection method for its simplicity.
96
     * This algorithm attempts to find an optimum alpha value between 0.0001 and 0.01
97
     *
98
     * Algorithm as follows:
99
     *  a) Probe a small alpha  (0.0001) and calculate cost function
100
     *  b) Probe a larger alpha (0.01) and calculate cost function
101
     *		b-1) If cost function decreases, continue enlarging alpha
102
     *		b-2) If cost function increases, take the midpoint and try again
103
     *
104
     * @param float $d
105
     *
106
     * @return array
107
     */
108
    protected function getAlpha(float $d)
109
    {
110
        $small = 0.0001 * $d;
111
        $large = 0.01 * $d;
112
113
        // Obtain θ + α.d for two initial values, x0 and x1
114
        $x0 = mp::adds($this->theta, $small);
115
        $x1 = mp::adds($this->theta, $large);
116
117
        $epsilon = 0.0001;
118
        $iteration = 0;
119
        do {
120
            $fx1 = $this->cost($x1);
121
            $fx0 = $this->cost($x0);
122
123
            // If the difference between two values is small enough
124
            // then break the loop
125
            if (abs($fx1 - $fx0) <= $epsilon) {
126
                break;
127
            }
128
129
            if ($fx1 < $fx0) {
130
                $x0 = $x1;
131
                $x1 = mp::adds($x1, 0.01); // Enlarge second
132
            } else {
133
                $x1 = mp::divs(mp::add($x1, $x0), 2.0);
134
            } // Get to the midpoint
135
136
            $error = $fx1 / $this->dimensions;
137
        } while ($error <= $epsilon || $iteration++ < 10);
138
139
        //  Return α = θ / d
140
        if ($d == 0) {
141
            return $x1[0] - $this->theta[0];
142
        }
143
144
        return ($x1[0] - $this->theta[0]) / $d;
145
    }
146
147
    /**
148
     * Calculates new set of solutions with given alpha (for each θ(k)) and
149
     * gradient direction.
150
     *
151
     * θ(k+1) = θ(k) + α.d
152
     *
153
     * @param float $alpha
154
     * @param array $d
155
     *
156
     * return array
157
     */
158
    protected function getNewTheta(float $alpha, array $d)
159
    {
160
        $theta = $this->theta;
161
162
        for ($i=0; $i < $this->dimensions + 1; $i++) {
163
            if ($i == 0) {
164
                $theta[$i] += $alpha * array_sum($d);
165
            } else {
166
                $sum = 0.0;
167
                foreach ($this->samples as $si => $sample) {
168
                    $sum += $sample[$i - 1] * $d[$si] * $alpha;
169
                }
170
171
                $theta[$i] += $sum;
172
            }
173
        }
174
175
        return $theta;
176
    }
177
178
    /**
179
     * Calculates new beta (β) for given set of solutions by using
180
     * Fletcher–Reeves method.
181
     *
182
     * β = ||f(x(k+1))||²  ∕  ||f(x(k))||²
183
     *
184
     * See:
185
     *  R. Fletcher and C. M. Reeves, "Function minimization by conjugate gradients", Comput. J. 7 (1964), 149–154.
186
     *
187
     * @param array $newTheta
188
     *
189
     * @return float
190
     */
191
    protected function getBeta(array $newTheta)
192
    {
193
        $dNew = array_sum($this->gradient($newTheta));
194
        $dOld = array_sum($this->gradient($this->theta)) + 1e-100;
195
196
        return  $dNew ** 2 / $dOld ** 2;
197
    }
198
199
    /**
200
     * Calculates the new conjugate direction
201
     *
202
     * d(k+1) =–∇f(x(k+1)) + β(k).d(k)
203
     *
204
     * @param array $theta
205
     * @param float $beta
206
     * @param array $d
207
     *
208
     * @return array
209
     */
210
    protected function getNewDirection(array $theta, float $beta, array $d)
211
    {
212
        $grad = $this->gradient($theta);
213
214
        return mp::add(mp::muls($grad, -1), mp::muls($d, $beta));
215
    }
216
}
217
218
/**
219
 * Handles element-wise vector operations between vector-vector
220
 * and vector-scalar variables
221
 */
222
class mp
0 ignored issues
show
Coding Style Compatibility introduced by
PSR1 recommends that each class should be in its own file to aid autoloaders.

Having each class in a dedicated file usually plays nice with PSR autoloaders and is therefore a well established practice. If you use other autoloaders, you might not want to follow this rule.

Loading history...
223
{
224
    /**
225
     * Element-wise <b>multiplication</b> of two vectors of the same size
226
     *
227
     * @param array $m1
228
     * @param array $m2
229
     *
230
     * @return array
231
     */
232 View Code Duplication
    public static function mul(array $m1, array $m2)
0 ignored issues
show
Duplication introduced by
This method seems to be duplicated in your project.

Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.

You can also find more detailed suggestions in the “Code” section of your repository.

Loading history...
233
    {
234
        $res = [];
235
        foreach ($m1 as $i => $val) {
236
            $res[] = $val * $m2[$i];
237
        }
238
239
        return $res;
240
    }
241
242
    /**
243
     * Element-wise <b>division</b> of two vectors of the same size
244
     *
245
     * @param array $m1
246
     * @param array $m2
247
     *
248
     * @return array
249
     */
250 View Code Duplication
    public static function div(array $m1, array $m2)
0 ignored issues
show
Duplication introduced by
This method seems to be duplicated in your project.

Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.

You can also find more detailed suggestions in the “Code” section of your repository.

Loading history...
251
    {
252
        $res = [];
253
        foreach ($m1 as $i => $val) {
254
            $res[] = $val / $m2[$i];
255
        }
256
257
        return $res;
258
    }
259
260
    /**
261
     * Element-wise <b>addition</b> of two vectors of the same size
262
     *
263
     * @param array $m1
264
     * @param array $m2
265
     *
266
     * @return array
267
     */
268 View Code Duplication
    public static function add(array $m1, array $m2, $mag = 1)
0 ignored issues
show
Duplication introduced by
This method seems to be duplicated in your project.

Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.

You can also find more detailed suggestions in the “Code” section of your repository.

Loading history...
269
    {
270
        $res = [];
271
        foreach ($m1 as $i => $val) {
272
            $res[] = $val + $mag * $m2[$i];
273
        }
274
275
        return $res;
276
    }
277
278
    /**
279
     * Element-wise <b>subtraction</b> of two vectors of the same size
280
     *
281
     * @param array $m1
282
     * @param array $m2
283
     *
284
     * @return array
285
     */
286
    public static function sub(array $m1, array $m2)
287
    {
288
        return self::add($m1, $m2, -1);
289
    }
290
291
    /**
292
     * Element-wise <b>multiplication</b> of a vector with a scalar
293
     *
294
     * @param array $m1
295
     * @param float $m2
296
     *
297
     * @return array
298
     */
299
    public static function muls(array $m1, float $m2)
300
    {
301
        $res = [];
302
        foreach ($m1 as $val) {
303
            $res[] = $val * $m2;
304
        }
305
306
        return $res;
307
    }
308
309
    /**
310
     * Element-wise <b>division</b> of a vector with a scalar
311
     *
312
     * @param array $m1
313
     * @param float $m2
314
     *
315
     * @return array
316
     */
317 View Code Duplication
    public static function divs(array $m1, float $m2)
0 ignored issues
show
Duplication introduced by
This method seems to be duplicated in your project.

Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.

You can also find more detailed suggestions in the “Code” section of your repository.

Loading history...
318
    {
319
        $res = [];
320
        foreach ($m1 as $val) {
321
            $res[] = $val / ($m2 + 1e-32);
322
        }
323
324
        return $res;
325
    }
326
327
    /**
328
     * Element-wise <b>addition</b> of a vector with a scalar
329
     *
330
     * @param array $m1
331
     * @param float $m2
332
     *
333
     * @return array
334
     */
335 View Code Duplication
    public static function adds(array $m1, float $m2, $mag = 1)
0 ignored issues
show
Duplication introduced by
This method seems to be duplicated in your project.

Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.

You can also find more detailed suggestions in the “Code” section of your repository.

Loading history...
336
    {
337
        $res = [];
338
        foreach ($m1 as $val) {
339
            $res[] = $val + $mag * $m2;
340
        }
341
342
        return $res;
343
    }
344
345
    /**
346
     * Element-wise <b>subtraction</b> of a vector with a scalar
347
     *
348
     * @param array $m1
349
     * @param float $m2
350
     *
351
     * @return array
352
     */
353
    public static function subs(array $m1, array $m2)
354
    {
355
        return self::adds($m1, $m2, -1);
0 ignored issues
show
Documentation introduced by
$m2 is of type array, but the function expects a double.

It seems like the type of the argument is not accepted by the function/method which you are calling.

In some cases, in particular if PHP’s automatic type-juggling kicks in this might be fine. In other cases, however this might be a bug.

We suggest to add an explicit type cast like in the following example:

function acceptsInteger($int) { }

$x = '123'; // string "123"

// Instead of
acceptsInteger($x);

// we recommend to use
acceptsInteger((integer) $x);
Loading history...
356
    }
357
}
358