vl_bfgs.py 13.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# NIFTy
# Copyright (C) 2017  Theo Steininger
#
# Author: Theo Steininger
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
Theo Steininger's avatar
Theo Steininger committed
18

19
20
import numpy as np

21
from .descent_minimizer import DescentMinimizer
22
from .line_searching import LineSearchStrongWolfe
Theo Steininger's avatar
Theo Steininger committed
23
24


25
class VL_BFGS(DescentMinimizer):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
    """Implementation of the Vector-free L-BFGS minimization scheme.
    
    Find the descent direction by using the inverse Hessian.
    Instead of storing the whole matrix, it stores only the last few updates, 
    which are used to do operations requiring the inverse Hessian product. The
    updates are represented in a new basis to optimize the algorithm.
    LITERATURE:
        W. Chen, Z. Wang, J. Zhou, Large-scale L-BFGS using MapReduce, 2014,
        Microsoft
        
    Parameters
    ----------
    line_searcher : callable
        Function which finds the step size in descent direction. (default:
        LineSearchStrongWolfe())
    callback : function *optional*
        Function f(energy, iteration_number) specified by the user to print 
        iteration number and energy value at every iteration step. It accepts 
        an Energy object(energy) and integer(iteration_number). (default: None)
    convergence_tolerance : scalar
        Tolerance specifying convergence. (default: 1E-4)
    convergence_level : integer
        Number of times the tolerance should be undershot before exiting. 
        (default: 3)
    iteration_limit : integer *optional*
        Maximum number of iterations performed. (default: None)
    max_history_length : integer
        Maximum number of stored past updates. (default: 10)
    
    Attributes
    ----------
    max_history_length : integer
        Maximum number of stored past updates.
    
    """
61
62
63
64
65
66
67
68
69
70
71
72
73
    def __init__(self, line_searcher=LineSearchStrongWolfe(), callback=None,
                 convergence_tolerance=1E-4, convergence_level=3,
                 iteration_limit=None, max_history_length=10):

        super(VL_BFGS, self).__init__(
                                line_searcher=line_searcher,
                                callback=callback,
                                convergence_tolerance=convergence_tolerance,
                                convergence_level=convergence_level,
                                iteration_limit=iteration_limit)

        self.max_history_length = max_history_length

74
    def __call__(self, energy):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
        """Runs the inherited __call__ method from QuasiNewtonMinimizer.
        
        Parameters
        ----------
        energy : Energy object
            Energy object which describes our system.
            
        Returns
        -------
        energy : Energy object
            Latest `energy` of the minimization.
        convergence : integer
            Latest convergence level indicating whether the minimization
            has converged or not.
        
        """
91
        self._information_store = None
92
        return super(VL_BFGS, self).__call__(energy)
93

94
    def _get_descend_direction(self, energy):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
        """Initializes the storage of updates and gets descent direction.
        
        Gets the new basis vectors b and sums them to get the descend 
        direction.
        
        Parameters
        ----------
        energy : Energy object
            Energy object which describes our system.
            
        Returns
        -------
        descend_direction : Field
            Descend direction.
        
        """
111
112
        x = energy.position
        gradient = energy.gradient
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
        # initialize the information store if it doesn't already exist
        try:
            self._information_store.add_new_point(x, gradient)
        except AttributeError:
            self._information_store = InformationStore(self.max_history_length,
                                                       x0=x,
                                                       gradient=gradient)

        b = self._information_store.b
        delta = self._information_store.delta

        descend_direction = delta[0] * b[0]
        for i in xrange(1, len(delta)):
            descend_direction += delta[i] * b[i]

128
        norm = descend_direction.norm()
129
130
        if norm != 1:
            descend_direction /= norm
131
        return descend_direction
Theo Steininger's avatar
Theo Steininger committed
132
133
134


class InformationStore(object):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
    """Class for storing a list of past updates.
    
    Parameters
    ----------
    max_history_length : integer
        Maximum number of stored past updates.
    x0 : Field
        Initial position in variable space.
    gradient : Field
        Gradient at position x0.
    
    Attributes
    ----------
    max_history_length : integer
        Maximum number of stored past updates.
    s : List
        List of past position differences, which are Fields.
    y : List
        List of past gradient differences, which are Fields.
    last_x : Field
        Initial position in variable space.
    last_gradient : Field
        Gradient at initial position.
    k : integer
        Number of currently stored past updates.
    _ss_store : dictionary
        Dictionary of scalar products between different elements of s.
    _sy_store : dictionary
        Dictionary of scalar products between elements of s and y.
    _yy_store : dictionary
        Dictionary of scalar products between different elements of y.
    
    """
168
169
170
171
    def __init__(self, max_history_length, x0, gradient):
        self.max_history_length = max_history_length
        self.s = LimitedList(max_history_length)
        self.y = LimitedList(max_history_length)
172
173
        self.last_x = x0.copy()
        self.last_gradient = gradient.copy()
Theo Steininger's avatar
Theo Steininger committed
174
        self.k = 0
175
176
177
178
179
180
181

        self._ss_store = {}
        self._sy_store = {}
        self._yy_store = {}

    @property
    def history_length(self):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
182
183
184
        """Returns the number of currently stored updates.
        
        """
185
186
187
188
        return min(self.k, self.max_history_length)

    @property
    def b(self):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
189
190
191
192
193
194
195
196
        """Combines s, y and gradient to form the new base vectors b. 
        
        Returns
        -------
        result : List
            List of new basis vectors.
            
        """
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
        result = []
        m = self.history_length
        k = self.k

        s = self.s
        for i in xrange(m):
            result.append(s[k-m+i])

        y = self.y
        for i in xrange(m):
            result.append(y[k-m+i])

        result.append(self.last_gradient)

        return result

    @property
    def b_dot_b(self):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
215
216
217
218
219
220
221
222
223
224
225
        """Generates the (2m+1) * (2m+1) scalar matrix.
        
        The i,j-th element of the matrix is a scalar product between the i-th
        and j-th base vector. 
        
        Returns
        -------
        result : numpy.ndarray      
            Scalar matrix.
        
        """
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
        m = self.history_length
        k = self.k
        result = np.empty((2*m+1, 2*m+1), dtype=np.float)

        for i in xrange(m):
            for j in xrange(m):
                result[i, j] = self.ss_store(k-m+i, k-m+j)

                sy_ij = self.sy_store(k-m+i, k-m+j)
                result[i, m+j] = sy_ij
                result[m+j, i] = sy_ij

                result[m+i, m+j] = self.yy_store(k-m+i, k-m+j)

            sgrad_i = self.sgrad_store(k-m+i)
            result[2*m, i] = sgrad_i
            result[i, 2*m] = sgrad_i

            ygrad_i = self.ygrad_store(k-m+i)
            result[2*m, m+i] = ygrad_i
            result[m+i, 2*m] = ygrad_i

        result[2*m, 2*m] = self.gradgrad_store()

        return result
Theo Steininger's avatar
Theo Steininger committed
251
252

    @property
253
    def delta(self):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
254
255
256
257
258
259
260
261
        """Calculates the new scalar coefficients (deltas).
        
        Returns
        -------
        delta : List
            List of the new scalar coefficients (deltas).
        
        """
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
        m = self.history_length
        b_dot_b = self.b_dot_b

        delta = np.zeros(2*m+1, dtype=np.float)
        delta[2*m] = -1

        alpha = np.empty(m, dtype=np.float)

        for j in xrange(m-1, -1, -1):
            delta_b_b = sum([delta[l] * b_dot_b[l, j] for l in xrange(2*m+1)])
            alpha[j] = delta_b_b/b_dot_b[j, m+j]
            delta[m+j] -= alpha[j]

        for i in xrange(2*m+1):
            delta[i] *= b_dot_b[m-1, 2*m-1]/b_dot_b[2*m-1, 2*m-1]

        for j in xrange(m-1, -1, -1):
            delta_b_b = sum([delta[l]*b_dot_b[m+j, l] for l in xrange(2*m+1)])
            beta = delta_b_b/b_dot_b[j, m+j]
            delta[j] += (alpha[j] - beta)

        return delta

    def ss_store(self, i, j):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
        """Updates the dictionary _ss_store with a new scalar product.
        
        Returns the scalar product of s_i and s_j.        
        
        Parameters
        ----------
        i : integer
            s index.
        j : integer
            s index.
            
        Returns
        -------
        _ss_store[key] : float
            Scalar product of s_i and s_j.
            
        """
303
304
305
306
307
308
        key = tuple(sorted((i, j)))
        if key not in self._ss_store:
            self._ss_store[key] = self.s[i].dot(self.s[j])
        return self._ss_store[key]

    def sy_store(self, i, j):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
        """Updates the dictionary _sy_store with a new scalar product.
        
        Returns the scalar product of s_i and y_j.        
        
        Parameters
        ----------
        i : integer
            s index.
        j : integer
            y index.
            
        Returns
        -------
        _sy_store[key] : float
            Scalar product of s_i and y_j.
            
        """
326
327
328
329
330
331
        key = (i, j)
        if key not in self._sy_store:
            self._sy_store[key] = self.s[i].dot(self.y[j])
        return self._sy_store[key]

    def yy_store(self, i, j):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
        """Updates the dictionary _yy_store with a new scalar product.
        
        Returns the scalar product of y_i and y_j.        
        
        Parameters
        ----------
        i : integer
            y index.
        j : integer
            y index.
            
        Returns
        ------
        _yy_store[key] : float
            Scalar product of y_i and y_j.
            
        """
349
350
351
352
353
354
        key = tuple(sorted((i, j)))
        if key not in self._yy_store:
            self._yy_store[key] = self.y[i].dot(self.y[j])
        return self._yy_store[key]

    def sgrad_store(self, i):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
355
356
357
358
359
360
361
362
        """Returns scalar product between s_i and gradient on initial position.
        
        Returns
        -------
        scalar product : float
            Scalar product.
            
        """
363
364
365
        return self.s[i].dot(self.last_gradient)

    def ygrad_store(self, i):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
366
367
368
369
370
371
372
373
        """Returns scalar product between y_i and gradient on initial position.
        
        Returns
        -------
        scalar product : float
            Scalar product.
            
        """
374
375
376
        return self.y[i].dot(self.last_gradient)

    def gradgrad_store(self):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
377
378
379
380
381
382
383
384
        """Returns scalar product of gradient on initial position with itself.
        
        Returns
        -------
        scalar product : float
            Scalar product.
            
        """
385
        return self.last_gradient.dot(self.last_gradient)
Theo Steininger's avatar
Theo Steininger committed
386
387

    def add_new_point(self, x, gradient):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
388
389
390
391
392
393
        """Updates the s list and y list.

        Calculates the new position and gradient differences and adds them to 
        the respective list.        
        
        """
Theo Steininger's avatar
Theo Steininger committed
394
395
396
397
398
399
400
401
        self.k += 1

        new_s = x - self.last_x
        self.s.add(new_s)

        new_y = gradient - self.last_gradient
        self.y.add(new_y)

402
403
        self.last_x = x.copy()
        self.last_gradient = gradient.copy()
Theo Steininger's avatar
Theo Steininger committed
404
405
406


class LimitedList(object):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
    """Class for creating a list of limited length.
    
    Parameters
    ----------
    history_length : integer
        Maximum number of stored past updates.
    
    Attributes
    ----------
    history_length : integer
        Maximum number of stored past updates.
    _offset : integer
        Offset to correct the indices which are bigger than maximum history.
        length.
    _storage : list
        List where input values are stored.
        
    """
Theo Steininger's avatar
Theo Steininger committed
425
426
427
428
429
430
    def __init__(self, history_length):
        self.history_length = int(history_length)
        self._offset = 0
        self._storage = []

    def __getitem__(self, index):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
431
432
433
434
435
436
437
438
439
440
441
        """Returns the element with index [index-offset].
        
        Parameters
        ----------
        index : integer
            Index of the selected element.
            
        Returns
        -------
            selected element
        """
Theo Steininger's avatar
Theo Steininger committed
442
443
444
        return self._storage[index-self._offset]

    def add(self, value):
Matevz, Sraml (sraml)'s avatar
Matevz, Sraml (sraml) committed
445
446
447
448
449
450
451
452
453
454
455
        """Adds a new element to the list.
        
        If the list is of length maximum history then it removes the first
        element first.
        
        Parameters
        ----------
        value : anything
            New element in the list.
        
        """
Theo Steininger's avatar
Theo Steininger committed
456
457
458
459
        if len(self._storage) == self.history_length:
            self._storage.pop(0)
            self._offset += 1
        self._storage.append(value)