m8ta
You are not authenticated, login.
text: sort by
tags: modified
type: chronology
{1529}
hide / / print
ref: -2020 tags: dreamcoder ellis program induction ai date: 02-01-2021 18:39 gmt revision:0 [head]

DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning

  • Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, Joshua B. Tenenbaum

This paper describes a system for adaptively finding programs which succinctly and accurately produce desired output.  These desired outputs are provided by the user / test system, and come from a number of domains:

  • list (as in lisp) processing,
  • text editing,
  • regular expressions,
  • line graphics,
  • 2d lego block stacking,
  • symbolic regression (ish),
  • functional programming,
  • and physcial laws.  
Some of these domains are naturally toy-like, eg. the text processing, but others are deeply impressive: the system was able to "re-derive" basic physical laws of vector calculus in the process of looking for S-expression forms of cheat-sheet physics equations.  These advancements result from a long lineage of work, perhaps starting from the Helmholtz machine PMID-7584891 introduced by Peter Dayan, Geoff Hinton and others, where onemodel is trained to generate patterns given context (e.g.) while a second recognition module is trained to invert this model: derive context from the patterns.  The two work simultaneously to allow model-exploration in high dimensions.  

Also in the lineage is the EC2 algorithm, which most of the same authors above published in 2018.  EC2 centers around the idea of "explore - compress" : explore solutions to your program induction problem during the 'wake' phase, then compress the observed programs into a library by extracting/factoring out commonalities during the 'sleep' phase.  This of course is one of the core algorithms of human learning: explore options, keep track of both what worked and what didn't, search for commonalities among the options & their effects, and use these inferred laws or heuristics to further guide search and goal-setting, thereby building a buffer attack the curse of dimensionality.  Making the inferred laws themselves functions in a programming library allows hierarchically factoring the search task, making exploration of unbounded spaces possible.  This advantage is unique to the program synthesis approach. 

This much is said in the introduction, though perhaps with more clarity.  DreamCoder is an improved, more-accessible version of EC2, though the underlying ideas are the same.   It differs in that the method for constructing libraries has improved through the addition of a powerful version space for enumerating and evaluating refactors of the solutions generated during the wake phase.  (I will admit that I don't much understand the version space system.)  This version space allows DreamCoder to collapse the search space for re-factorings by many orders of magnitude, and seems to be a clear advancement.  Furthermore, DreamCoder incorporates a second phase of sleep: "dreaming", hence the moniker.  During dreaming the library is used to create 'dreams' consisting of combinations of the library primitives, which are then executed with training data as input.  These dreams are then used to train up a neural network to predict which library and atomic objects to use in given contexts.  Context in this case is where in the parse tree a given object has been inserted (it's parent and which argument number it sits in); how the data-context is incorporated to make this decision is not clear to me (???). 

This neural dream and replay-trained neural network is either a GRU recurrent net with 64 hidden states, or a convolutional network feeding into a RNN.  The final stage is a linear ReLu (???) which again is not clear how it feeds into the prediction of "which unit to use when".  The authors clearly demonstrate that the network, or the probabalistic context-free grammar that it controls (?) is capable of straightforward optimizations, like breaking symmetries due to commutativity, avoiding adding zero, avoiding multiplying by one, etc.  Beyond this, they do demonstrate via an ablation study that the presence of the neural network affords significant algorithmic leverage in all of the problem domains tested.  The network also seems to learn a reasonable representation of the sub-type of task encountered -- but a thorough investigation of how it works, or how it might be made to work better, remains desired. 

I've spent a little time looking around the code, which is a mix of python high-level experimental control code, and lower-level OCaml code responsible for running (emulating) the lisp-like DSL, inferring type in it's polymorphic system / reconciling types in evaluated program instances, maintaining the library, and recompressing it using aforementioned version spaces.  The code, like many things experimental, is clearly a work-in progress, with some old or unused code scattered about, glue to run the many experiments & record / analyze the data, and personal notes from the first author for making his job talks (! :).  The description in the supplemental materials, which is satisfyingly thorough (if again impenetrable wrt version spaces), is readily understandable, suggesting that one (presumably the first) author has a clear understanding of the system.  It doesn't appear that much is being hidden or glossed over, which is not the case for all scientific papers. 


With the caveat that I don't claim to understand the system to completion, there are some clear areas where the existing system could be augmented further.  The 'recognition' or perceptual module, which guides actual synthesis of candidate programs, realistically can use as much information as is available in DreamCoder as is available: full lexical and semantic scope, full input-output specifications, type information, possibly runtime binding of variables when filling holes.  This is motivated by the way that humans solve problems, at least as observed by introspection:
  • Examine problem, specification; extract patterns (via perceptual modules)
  • Compare patterns with existing library (memory) of compositionally-factored 'useful solutions' (this is identical to the library in DreamCoder)* Do something like beam-search or quasi stochastic search on selected useful solutions.  This is the same as DreamCoder, however human engineers make decisions progressively, at runtime so-to-speak: you fill not one hole per cycle, but many holes.  The addition of recursion to DreamCoder, provided a wider breadth of input information, could support this functionality. 
  • Run the program to observe input-output .. but also observe the inner workings of the program, eg. dataflow patterns.  These dataflow patterns are useful to human engineers when both debugging and when learning-by-inspection what library elements do.   DreamCoder does not really have this facility. 
  • Compare the current program results to the desired program output.  Make a stochastic decision whether to try to fix it, or to try another beam in the search.  Since this would be on a computer, this could be in parallel (as DreamCoder is); the ability to 'fix' or change a DUT is directly absent dreamcoder.   As an 'deeply philosophical' aside, this loop itself might be the effect of running a language-of-thought program, as was suggested by pioneers in AI (ref).  The loop itself is subject to modification and replacement based on goal-seeking success in the domain of interest, in a deeply-satisfying and deeply recursive manner ...
At each stage in the pipeline, the perceptual modules would have access to relevant variables in the current problem-solving context.  This is modeled on Jacques Pitrat's work.  Humans of course are even more flexible than that -- context includes roughly the whole brain, and if anything we're mushy on which level of the hierarchy we are working. 

Critical to making this work is to have, as I've written in my notes many years ago, a 'self compressing and factorizing memory'.  The version space magic + library could be considered a working example of this.  In the realm of ANNs, per recent OpenAI results with CLIP and Dall-E, really big transformers also seem to have strong compositional abilities, with the caveat that they need to be trained on segments of the whole web.  (This wouldn't be an issue here, as Dreamcoder generates a lot of its own training data via dreams).  Despite the data-inefficiency of DNN / transformers, they should be sufficient for making something in the spirit of above work, with a lot of compute, at least until more efficient models are available (which they should be shortly; see AlphaZero vs MuZero). 

{866}
hide / / print
ref: -0 tags: fragment of a dream san francisco frustration life date: 01-07-2011 05:33 gmt revision:1 [0] [head]

Remembered fragment of a dream, letter never sent.

Probably it was ill-fated to ---. Eh. That didn't distract me from having a batshit insane dream last night, feat three army goons, myself, and the vivacious ---. The goons and I were soldiers in charge of some truck-mounted machine gun in a logged and dried-mud hillcountry - probably Serbia - but whenever we tried to get it ready, the part in question would instantly transform into crochet. When the ammunition roll was finally in the yarn gun, all the bullets would fall on the ground; look away and it would resume metallic reality. On cue to amplify our disorganization a officer sped in to harass us in a Honda S2000. Annoyed, I threw gravel at him; it transformed into a lamborghini, then a porsche, a tesla, a toyota. (I've seen a lot of fancy cars this past week).

Given the frustrated Daliesque nature of the battlefield, we retreated, I as a restrained but irked soldier. Montage in, montage out, you enter to this scene as an bit-played angry estranged woman, pissed at my lack of caring / perceived neglect. Bitch complain threaten whine, I guilt but look outside and the vegetation is gorgeous, lush, the sky a mild hazy blue. I am a little thirsty.

{734}
hide / / print
ref: -0 tags: Vanity Fair American dream control theory in politics and society date: 05-03-2009 17:11 gmt revision:3 [2] [1] [0] [head]

Rethinking the American Dream by David Kamp

  • check out the lights in the frame at the bottom, and the kid taking a picture center-right (image courtesy of Kodak, hence.)

  • (quote:) "Still, we need to challenge some of the middle-class orthodoxies that have brought us to this point—not least the notion, widely promulgated throughout popular culture, that the middle class itself is a soul-suffocating dead end."
    • Perhaps they should teach expectations management in school? Sure, middle class should never die - I hope it will grow.
  • And yet, this is still rather depressive - we all want things to continuously, exponentially get better. I actually think this is almost possible, we just need to reason carefully about how this could happen: what changes in manufacturing, consumption, energy generation, transportation, and social organization would gradually effect widespread improvement.
    • Some time in individual lives (my own included!) is squandered in pursuit of the small pleasures which would be better used for purposeful endeavor. Seems we need to resurrect the idea of sacrifice towards the future (and it seems this meme itself is increasingly popular).
  • Realistically: nothing is for free; we are probably only enjoying this more recent economic boom because energy (and i mean oil, gas, coal, hydro, nuclear etc), which drives almost everything in society, is really cheap. If we can keep it this cheap, or make it cheaper through judicious investment in new technologies (and perhaps serendipity), then our standard of living can increase. That is not to say that it will - we need to put the caloric input to the economy to good use.
    • Currently our best system for enacting a general goal of efficiency is market-based capitalism. Now, the problem is that this is an inherently unstable system: there will be cheaters e.g. people who repackage crap mortgages as safe securities, companies who put lead paint on children's toys, companies who make unsafe products - and the capitalistic system, in and of itself, is imperfect at regulating these cheaters (*). Bureaucracy may not be the most efficient use of money or people's lives, but again it seems to be the best system for regulating/auditing cheaters. Examined from a control feedback point-of-view, bureaucracy 'tries' to control axes which pure capitalism does not directly address.
    • (*) Or is it? The largest problem with using consumer (or, more generally, individual) choice as the path to audit & evaluate production is that there is a large information gradient or knowledge difference between producers and consumers. It is the great (white?) hope of the internet generation that we can reduce this gradient, democratize information, and have everyone making better choices.
      • In this way, I'm very optimistic that things will get continuously better. (But recall that optimality-seeking requires time/money/energy - it ain't going to be free, and it certainly is not going to be 'natural'. Alternately, unstable-equilibrium-maintaining (servoing! auditing!) requires energy; democracy's big trick is that it takes advantage of a normal human behavior, bitching, as the feedstock. )
  • Finally (quote:) "I’m no champion of downward mobility, but the time has come to consider the idea of simple continuity: the perpetuation of a contented, sustainable middle-class way of life, where the standard of living remains happily constant from one generation to the next. "
    • Uh, you've had this coming: stick it. You can enjoy 'simple continuity'. My life is going to get better (or at least my life is going to change and be interesting/fun), and I expect the same for everybody else that I know. See logic above, and homoiconic's optimism

{700}
hide / / print
ref: Stickgold-2001.11 tags: review dream sleep REM NREM SWS learning memory replay date: 03-19-2009 17:09 gmt revision:7 [6] [5] [4] [3] [2] [1] [head]

PMID-11691983[0] Sleep, Learning, and Dreams: Off-line Memory Reprocessing

  • sleep can be broadly divided into REM (rapid eye movement) and NREM (no rapid eye movement) sleep, with the REM-NREM cycle lasting 90 minutes in humans.
  • REM seems involved in proper binocular wiring in the visual cortex, development of problem solving skills, and discrimination tasks.
    • REM sleep seems as important as visual experience for wiring binocular vision.
  • REM seems critical for learning procedural memories, but not declarative (by the authors claim that the tasks used in declarative tests are too simple).
    • Depriving rats of REM sleep can impair procedural learning at test points up to a week later.
    • SWS may be better for consolidation of declarative memory.
  • Strongest evidence comes from a visual texture discrimination task, where improvements are only seen after REM sleep.
    • REM has also been shown to have an effect in learning of complex logic games, foreign language acquisition, and after intensive studying.
    • Solving anagrames stronger after being woken up from REM sleep. (!)
  • REM (hypothetically) involves NC -> hippocampus; SWS involves hippocampus -> NC (hence declarative memory). (Buzaki 1996).
    • This may use theta waves, which enhance LTP in the hippocampus; the slow large depolarizations in SWS may facilitate LTP in the cortex.
  • Replay in the rat hippocampus:
    • replay occurs within layer CA1 during SWS for a half hour or so after learning, and in REM after 24 hours.
    • replay shifts from being in-phase with the theta wave activity (e.g. helping LTP) to being out of phase (coinicident with troughs, possibly used to 'erase' memories from the hippocampus?); this is in accord with memories becoming hippocampally independent.
  • ACh levels are at waking levels or higher, and levels of NE (noradrenergic) & 5-HT go near zero.
  • DLPFC (dorsolateral prefrontal cortex) is inhibited during REM sleep - presumably, this results in an inability to allocate attentional resources.
  • ACC (anterior cingulate cortex), MFC (medial frontal cortex), and the amygdala are highly active in REM sleep.
  • if you block correlates of learning - PKA pathwat, zif-268 genes during REM, learning is impaired.
  • In the context of a multilevel system of sleep-dependent memory reprocessing, dreams represent the conscious awareness of complex brain systems involved in the reprocessing of emotions and memories during sleep.
    • the whole section on dreaming is really interesting!

____References____

[0] Stickgold R, Hobson JA, Fosse R, Fosse M, Sleep, learning, and dreams: off-line memory reprocessing.Science 294:5544, 1052-7 (2001 Nov 2)