BeamSearch.h File Reference

This is an implementation of beam search that maintains a priority queue of partial states and attempts to find a program with the lowest posterior score. To do this, we choose a node to expand based on its prior plus N_REPS samples of its likelihood, computed by filling in its children at random. This stochastic heuristic is actually inadmissable (in A* terms) since it usually overestimates the cost. As a result, it usually makes sense to run at a pretty high temperature, corresponding to a downweighting of the likelihood, and making the heuristic more likely to be admissable. More...

#include "IO.h"
#include "Control.h"
#include <queue>
#include <thread>
#include <signal.h>
#include "FleetStatistics.h"
#include "ThreadedInferenceInterface.h"

Include dependency graph for BeamSearch.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	BeamSearch< HYP >

Variables
std::atomic< bool >	CTRL_C

Detailed Description

This is an implementation of beam search that maintains a priority queue of partial states and attempts to find a program with the lowest posterior score. To do this, we choose a node to expand based on its prior plus N_REPS samples of its likelihood, computed by filling in its children at random. This stochastic heuristic is actually inadmissable (in A* terms) since it usually overestimates the cost. As a result, it usually makes sense to run at a pretty high temperature, corresponding to a downweighting of the likelihood, and making the heuristic more likely to be admissable.

One general challenge is how to handle -inf likelihoods, and here we've done that by, if you end up with -inf, taking your parent's temperature and multiplying by PARENT_PENALTY.

TODO: Is it worth making this stochastic, so we sample the the expansion with the probabilities and some temperature?

Variable Documentation

CTRL_C

std::atomic<bool> CTRL_C