Fraser/dream-coder

1import math2import random3from dreamcoder.utilities import *4 5 6class InvalidLoss(Exception):7    pass8 9 10class DN(object):11    '''differentiable node: parent object of every differentiable operation'''12 13    def __init__(self, arguments):14        self.gradient = None15        if arguments != []:16            self.data = None17        self.arguments = arguments18 19        # descendents: every variable that takes this variable as input20        # descendents: [(DN,float)]21        # the additional float parameter is d Descendent / d This22        self.descendents = []23 24        self.recalculate()25 26    def __str__(self):27        if self.arguments == []:28            return self.name29        return "(%s %s)" % (self.name, " ".join(str(x)30                                                for x in self.arguments))31 32    def __repr__(self):33        return "DN(op = %s, data = %s, grad = %s, #descendents = %d, args = %s)" % (34            self.name, self.data, self.gradient, len(self.descendents), self.arguments)35 36    @property37    def derivative(self): return self.differentiate()38 39    def differentiate(self):40        if self.gradient is None:41            self.gradient = sum(partial * descendent.differentiate()42                                for descendent, partial in self.descendents)43        return self.gradient44 45    def zeroEverything(self):46        if self.gradient is None and self.descendents == [] and (47                self.data is None or self.arguments == []):48            return49 50        self.gradient = None51        self.descendents = []52        if self.arguments != []:53            self.data = None54 55        for x in self.arguments:56            x.zeroEverything()57 58    def lightweightRecalculate(self):59        return self.forward(*[a.lightweightRecalculate()60                              for a in self.arguments])61 62    def recalculate(self):63        if self.data is None:64            inputs = [a.recalculate() for a in self.arguments]65            self.data = self.forward(*inputs)66            # if invalid(self.data):67            #     eprint("I am invalid",repr(self))68            #     eprint("Here are my inputs",inputs)69            #     self.zeroEverything()70            #     eprint("Here I am after being zeroed",repr(self))71            #     raise Exception('invalid loss')72            #assert valid(self.data)73            partials = self.backward(*inputs)74            for d, a in zip(partials, self.arguments):75                # if invalid(d):76                #     eprint("I have an invalid derivative",self)77                #     eprint("Inputs",inputs)78                #     eprint("partials",partials)79                #     raise Exception('invalid derivative')80                a.descendents.append((self, d))81        return self.data82 83    def backPropagation(self):84        self.gradient = 1.85        self.recursivelyDifferentiate()86 87    def recursivelyDifferentiate(self):88        self.differentiate()89        for x in self.arguments:90            x.recursivelyDifferentiate()91 92    def updateNetwork(self):93        self.zeroEverything()94        l = self.recalculate()95        self.backPropagation()96        return l97 98    def log(self): return Logarithm(self)99 100    def square(self): return Square(self)101 102    def exp(self): return Exponentiation(self)103 104    def clamp(self, l, u): return Clamp(self, l, u)105 106    def __abs__(self): return AbsoluteValue(self)107 108    def __add__(self, o): return Addition(self, Placeholder.maybe(o))109 110    def __radd__(self, o): return Addition(self, Placeholder.maybe(o))111 112    def __sub__(self, o): return Subtraction(self, Placeholder.maybe(o))113 114    def __rsub__(self, o): return Subtraction(Placeholder.maybe(o), self)115 116    def __mul__(self, o): return Multiplication(self, Placeholder.maybe(o))117 118    def __rmul__(self, o): return Multiplication(self, Placeholder.maybe(o))119 120    def __neg__(self): return Negation(self)121 122    def __truediv__(self, o): return Division(self, Placeholder.maybe(o))123 124    def __rtruediv__(self, o): return Division(Placeholder.maybe(o), self)125 126    def numericallyVerifyGradients(self, parameters):127        calculatedGradients = [p.derivative for p in parameters]128        e = 0.00001129        for j, p in enumerate(parameters):130            p.data -= e131            y1 = self.lightweightRecalculate()132            p.data += 2 * e133            y2 = self.lightweightRecalculate()134            p.data -= e135            d = (y2 - y1) / (2 * e)136            if abs(calculatedGradients[j] - d) > 0.1:137                eprint(138                    "Bad gradient: expected %f, got %f" %139                    (d, calculatedGradients[j]))140 141    def gradientDescent(142            self,143            parameters,144            _=None,145            lr=0.001,146            steps=10**3,147            update=None):148        for j in range(steps):149            l = self.updateNetwork()150            if update is not None and j % update == 0:151                eprint("LOSS:", l)152                for p in parameters:153                    eprint(p.data, '\t', p.derivative)154            if invalid(l):155                raise InvalidLoss()156 157            for p in parameters:158                p.data -= lr * p.derivative159        return self.data160 161    def restartingOptimize(self, parameters, _=None, attempts=1,162                           s=1., decay=0.5, grow=0.1,163                           lr=0.1, steps=10**3, update=None):164        ls = []165        for _ in range(attempts):166            for p in parameters:167                p.data = random.random()*10 - 5168            ls.append(169                self.resilientBackPropagation(170                    parameters, lr=lr, steps=steps,171                    decay=decay, grow=grow))172        return min(ls)173 174    def resilientBackPropagation(175            self,176            parameters,177            _=None,178            decay=0.5,179            grow=1.2,180            lr=0.1,181            steps=10**3,182            update=None):183        previousSign = [None] * len(parameters)184        lr = [lr] * len(parameters)185        for j in range(steps):186            l = self.updateNetwork()187 188            if update is not None and j % update == 0:189                eprint("LOSS:", l)190                eprint("\t".join(str(p.derivative) for p in parameters))191            if invalid(l):192                raise InvalidLoss()193 194            newSigns = [p.derivative > 0 for p in parameters]195            for i, p in enumerate(parameters):196                if p.derivative > 0:197                    p.data -= lr[i]198                elif p.derivative < 0:199                    p.data += lr[i]200                if previousSign[i] is not None:201                    if previousSign[i] == newSigns[i]:202                        lr[i] *= grow203                    else:204                        lr[i] *= decay205            previousSign = newSigns206 207        return self.data208 209 210class Placeholder(DN):211    COUNTER = 0212 213    def __init__(self, initialValue=0., name=None):214        self.data = initialValue215        super(Placeholder, self).__init__([])216        if name is None:217            name = "p_" + str(Placeholder.COUNTER)218            Placeholder.COUNTER += 1219        self.name = name220 221    @staticmethod222    def named(namePrefix, initialValue=0.):223        p = Placeholder(initialValue, namePrefix + str(Placeholder.COUNTER))224        Placeholder.COUNTER += 1225        return p226 227    def __str__(self):228        return "Placeholder(%s = %s)" % (self.name, self.data)229 230    @staticmethod231    def maybe(x):232        if isinstance(x, DN):233            return x234        return Placeholder(float(x))235 236    def forward(self): return self.data237 238    def backward(self): return []239 240 241class Clamp(DN):242    def __init__(self, x, l, u):243        assert u > l244        self.l = l245        self.u = u246        super(Clamp, self).__init__([x])247        self.name = "clamp"248 249    def forward(self, x):250        if x > self.u:251            return self.u252        if x < self.l:253            return self.l254        return x255 256    def backward(self, x):257        if x > self.u or x < self.l:258            return [0.]259        else:260            return [1.]261 262 263class Addition(DN):264    def __init__(self, x, y):265        super(Addition, self).__init__([x, y])266        self.name = '+'267 268    def forward(self, x, y): return x + y269 270    def backward(self, x, y): return [1., 1.]271 272 273class Subtraction(DN):274    def __init__(self, x, y):275        super(Subtraction, self).__init__([x, y])276        self.name = '-'277 278    def forward(self, x, y): return x - y279 280    def backward(self, x, y): return [1., -1.]281 282 283class Negation(DN):284    def __init__(self, x):285        super(Negation, self).__init__([x])286        self.name = '-'287 288    def forward(self, x): return -x289 290    def backward(self, x): return [-1.]291 292 293class AbsoluteValue(DN):294    def __init__(self, x):295        super(AbsoluteValue, self).__init__([x])296        self.name = 'abs'297 298    def forward(self, x): return abs(x)299 300    def backward(self, x):301        if x > 0:302            return [1.]303        return [-1.]304 305 306class Multiplication(DN):307    def __init__(self, x, y):308        super(Multiplication, self).__init__([x, y])309        self.name = '*'310 311    def forward(self, x, y): return x * y312 313    def backward(self, x, y): return [y, x]314 315 316class Division(DN):317    def __init__(self, x, y):318        super(Division, self).__init__([x, y])319        self.name = '/'320 321    def forward(self, x, y): return x / y322 323    def backward(self, x, y): return [1.0 / y, -x / (y * y)]324 325 326class Square(DN):327    def __init__(self, x):328        super(Square, self).__init__([x])329        self.name = 'sq'330 331    def forward(self, x): return x * x332 333    def backward(self, x): return [2 * x]334 335 336class Exponentiation(DN):337    def __init__(self, x):338        super(Exponentiation, self).__init__([x])339        self.name = 'exp'340 341    def forward(self, x): return math.exp(x)342 343    def backward(self, x): return [math.exp(x)]344 345 346class Logarithm(DN):347    def __init__(self, x):348        super(Logarithm, self).__init__([x])349        self.name = 'log'350 351    def forward(self, x): return math.log(x)352 353    def backward(self, x): return [1. / x]354 355 356class LSE(DN):357    def __init__(self, xs):358        super(LSE, self).__init__(xs)359        self.name = 'LSE'360 361    def forward(self, *xs):362        m = max(xs)363        return m + math.log(sum(math.exp(y - m) for y in xs))364 365    def backward(self, *xs):366        m = max(xs)367        zm = sum(math.exp(x - m) for x in xs)368        return [math.exp(x - m) / zm for x in xs]369 370 371if __name__ == "__main__":372    x = Placeholder(10., "x")373    y = Placeholder(2., "y")374    z = x - LSE([x, y])375    z.updateNetwork()376    eprint("dL/dx = %f\tdL/dy = %f" % (x.derivative, y.derivative))377 378    x.data = 2.379    y.data = 10.380    z.updateNetwork()381    eprint("dL/dx = %f\tdL/dy = %f" % (x.differentiate(), y.differentiate()))382 383    x.data = 2.384    y.data = 2.385    z.updateNetwork()386    eprint("z = ", z.data, z)387    eprint("dL/dx = %f\tdL/dy = %f" % (x.differentiate(), y.differentiate()))388 389    loss = -z390    eprint(loss)391 392    lr = 0.001393    loss.gradientDescent([x, y], steps=10000, update=1000)394