Fraser/dream-coder

1from dreamcoder.program import *2from dreamcoder.differentiation import *3 4import signal5 6 7class EvaluationTimeout(Exception):8    pass9 10 11EVALUATIONTABLE = {}12 13 14class Task(object):15    def __init__(self, name, request, examples, features=None, cache=False):16        '''request: the type of this task17        examples: list of tuples of (input, output). input should be a tuple, with one entry for each argument18        cache: should program evaluations be cached?19        features: list of floats.'''20        self.cache = cache21        self.features = features22        self.request = request23        self.name = name24        self.examples = examples25        if len(self.examples) > 0:26            assert all(len(xs) == len(examples[0][0])27                       for xs, _ in examples), \28                "(for task %s) FATAL: Number of arguments varies." % name29 30    def __str__(self):31        if self.supervision is None:32            return self.name33        else:34            return self.name + " (%s)"%self.supervision35 36    def __repr__(self):37        return "Task(name={self.name}, request={self.request}, examples={self.examples}"\38            .format(self=self)39 40    def __eq__(self, o): return self.name == o.name41 42    def __ne__(self, o): return not (self == o)43 44    def __hash__(self): return hash(self.name)45 46    def describe(self):47        description = ["%s : %s" % (self.name, self.request)]48        for xs, y in self.examples:49            if len(xs) == 1:50                description.append("f(%s) = %s" % (xs[0], y))51            else:52                description.append("f%s = %s" % (xs, y))53        return "\n".join(description)54 55    def predict(self, f, x):56        for a in x:57            f = f(a)58        return f59 60    @property61    def supervision(self):62        if not hasattr(self, 'supervisedSolution'): return None63        return self.supervisedSolution64 65    def check(self, e, timeout=None):66        if timeout is not None:67            def timeoutCallBack(_1, _2): raise EvaluationTimeout()68        try:69            signal.signal(signal.SIGVTALRM, timeoutCallBack)70            signal.setitimer(signal.ITIMER_VIRTUAL, timeout)71 72            try:73                f = e.evaluate([])74            except IndexError:75                # free variable76                return False77            except Exception as e:78                eprint("Exception during evaluation:", e)79                return False80 81            for x, y in self.examples:82                if self.cache and (x, e) in EVALUATIONTABLE:83                    p = EVALUATIONTABLE[(x, e)]84                else:85                    try:86                        p = self.predict(f, x)87                    except BaseException:88                        p = None89                    if self.cache:90                        EVALUATIONTABLE[(x, e)] = p91                if p != y:92                    if timeout is not None:93                        signal.signal(signal.SIGVTALRM, lambda *_: None)94                        signal.setitimer(signal.ITIMER_VIRTUAL, 0)95                    return False96 97            return True98        # except e:99            # eprint(e)100            # assert(False)101        except EvaluationTimeout:102            eprint("Timed out while evaluating", e)103            return False104        finally:105            if timeout is not None:106                signal.signal(signal.SIGVTALRM, lambda *_: None)107                signal.setitimer(signal.ITIMER_VIRTUAL, 0)108 109    def logLikelihood(self, e, timeout=None):110        if self.check(e, timeout):111            return 0.0112        else:113            return NEGATIVEINFINITY114 115    @staticmethod116    def featureMeanAndStandardDeviation(tasks):117        dimension = len(tasks[0].features)118        averages = [sum(t.features[j] for t in tasks) / float(len(tasks))119                    for j in range(dimension)]120        variances = [sum((t.features[j] -121                          averages[j])**2 for t in tasks) /122                     float(len(tasks)) for j in range(dimension)]123        standardDeviations = [v**0.5 for v in variances]124        for j, s in enumerate(standardDeviations):125            if s == 0.:126                eprint(127                    "WARNING: Feature %d is always %f" %128                    (j + 1, averages[j]))129        return averages, standardDeviations130 131    def as_json_dict(self):132        return {133            "name": self.name,134            "request": str(self.request),135            "examples": [{"inputs": x, "output": y} for x, y in self.examples]136        }137 138 139class DifferentiableTask(Task):140 141    def __init__(self, name, request, examples, _=None,142                 features=None, BIC=1., loss=None, likelihoodThreshold=None,143                 steps=50, restarts=300, lr=0.5, decay=0.5, grow=1.2, actualParameters=None,144                 temperature=1., maxParameters=None, clipLoss=None, clipOutput=None):145        assert loss is not None146        self.temperature = temperature147        self.actualParameters = actualParameters148        self.maxParameters = maxParameters149        self.loss = loss150        self.BIC = BIC151        self.likelihoodThreshold = likelihoodThreshold152 153        arguments = {"parameterPenalty": BIC * math.log(len(examples)),154                     "temperature": temperature,155                     "steps": steps, "restarts": restarts, "lr": lr, "decay": decay, "grow": grow,156                     "maxParameters": maxParameters,157                     "lossThreshold": -likelihoodThreshold}158        if clipLoss is not None: arguments['clipLoss'] = float(clipLoss)159        if clipOutput is not None: arguments['clipOutput'] = float(clipOutput)160        if actualParameters is not None: arguments['actualParameters'] = int(actualParameters)161        162        self.specialTask = ("differentiable",163                            arguments)164 165        super(166            DifferentiableTask,167            self).__init__(168            name,169            request,170            examples,171            features,172            cache=False)173 174    def logLikelihood(self, e, timeout=None):175        assert timeout is None, "timeout not implemented for differentiable tasks, but not for any good reason."176        e, parameters = PlaceholderVisitor.execute(e)177        if self.maxParameters is not None and len(178                parameters) > self.maxParameters:179            return NEGATIVEINFINITY180        if self.actualParameters is not None and len(181                parameters) > self.actualParameters:182            return NEGATIVEINFINITY183        f = e.evaluate([])184 185        loss = sum(self.loss(self.predict(f, xs), y)186                   for xs, y in self.examples) / float(len(self.examples))187        if isinstance(loss, DN):188            try:189                loss = loss.restartingOptimize(190                    parameters,191                    lr=self.specialTask[1]["lr"],192                    steps=self.specialTask[1]["steps"],193                    decay=self.specialTask[1]["decay"],194                    grow=self.specialTask[1]["grow"],195                    attempts=self.specialTask[1]["restarts"],196                    update=None)197            except InvalidLoss:198                loss = POSITIVEINFINITY199 200        # BIC penalty201        penalty = self.BIC * len(parameters) * math.log(len(self.examples))202 203        if self.likelihoodThreshold is not None:204            if loss > -self.likelihoodThreshold:205                return NEGATIVEINFINITY206            else:207                return -penalty208        else:209            return -loss / self.temperature - penalty210 211 212def squaredErrorLoss(prediction, target):213    d = prediction - target214    return d * d215 216 217def l1loss(prediction, target):218    return abs(prediction - target)219 220 221class PlaceholderVisitor(object):222    def __init__(self): self.parameters = []223 224    def primitive(self, e):225        if e.name == 'REAL':226            placeholder = Placeholder.named("REAL_", random.random())227            self.parameters.append(placeholder)228            return Primitive(e.name, e.tp, placeholder)229        return e230 231    def invented(self, e): return e.body.visit(self)232 233    def abstraction(self, e): return Abstraction(e.body.visit(self))234 235    def application(self, e):236        return Application(e.f.visit(self), e.x.visit(self))237 238    def index(self, e): return e239 240    @staticmethod241    def execute(e):242        v = PlaceholderVisitor()243        e = e.visit(v)244        return e, v.parameters245