Trait programinduction::EC
[−]
[src]
pub trait EC: Send + Sync + Sized { type Expression: Clone + Send + Sync; type Params; fn enumerate<F>(&self, tp: TypeSchema, termination_condition: F)
where
F: FnMut(Self::Expression, f64) -> bool; fn compress<O: Sync>(
&self,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>],
frontiers: Vec<ECFrontier<Self>>
) -> (Self, Vec<ECFrontier<Self>>); fn ec<O: Sync>(
&self,
ecparams: &ECParams,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>]
) -> (Self, Vec<ECFrontier<Self>>) { ... } fn ec_with_recognition<O: Sync, R>(
&self,
ecparams: &ECParams,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>],
recognizer: R
) -> (Self, Vec<ECFrontier<Self>>)
where
R: FnOnce(&Self, &[Task<Self, Self::Expression, O>]) -> Vec<Self>, { ... } fn explore<O: Sync>(
&self,
ec_params: &ECParams,
tasks: &[Task<Self, Self::Expression, O>]
) -> Vec<ECFrontier<Self>> { ... } fn explore_with_recognition<O: Sync>(
&self,
ec_params: &ECParams,
tasks: &[Task<Self, Self::Expression, O>],
representations: &[Self]
) -> Vec<ECFrontier<Self>> { ... } }
A kind of representation suitable for exploration-compression.
For details on the EC algorithm, see the module-level documentation here.
Implementors of EC
need only provide an enumerate
and compress
methods. By doing so,
we provide the ec
, ec_with_recognition
, and explore
methods.
Typically, you will interact with this trait via existing implementations, such as with
lambda::Language
or pcfg::Grammar
.
Associated Types
type Expression: Clone + Send + Sync
An Expression is a sentence in the representation. Tasks are solved by Expressions.
type Params
Many representations have some parameters for compression. They belong here.
Required Methods
fn enumerate<F>(&self, tp: TypeSchema, termination_condition: F) where
F: FnMut(Self::Expression, f64) -> bool,
F: FnMut(Self::Expression, f64) -> bool,
Iterate over Expression
s for a given type, with their corresponding log-priors, until a
condition is met. This enumeration should be best-first: the log-prior of enumerated
expressions should generally increase, so simple expressions are enumerated first.
The termination_condition
acts as a callback for each enumerated (Expression, f64)
.
If it responds with true, enumeration must stop (i.e. this method call should terminate).
fn compress<O: Sync>(
&self,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>],
frontiers: Vec<ECFrontier<Self>>
) -> (Self, Vec<ECFrontier<Self>>)
&self,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>],
frontiers: Vec<ECFrontier<Self>>
) -> (Self, Vec<ECFrontier<Self>>)
Update the representation based on findings of expressions that solve Task
s.
The frontiers
argument, and similar return value, must always be of the same size as
tasks
. Each frontier is a possibly-empty list of expressions that solve the corresponding
task, and the log-prior and log-likelihood for that expression.
Provided Methods
fn ec<O: Sync>(
&self,
ecparams: &ECParams,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>]
) -> (Self, Vec<ECFrontier<Self>>)
&self,
ecparams: &ECParams,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>]
) -> (Self, Vec<ECFrontier<Self>>)
The entry point for one iteration of the EC algorithm.
Returned solutions include the log-prior and log-likelihood of successful expressions.
Examples
use programinduction::{lambda, ECParams, EC}; use programinduction::domains::circuits; let mut dsl = circuits::dsl(); let tasks = circuits::make_tasks(250); let ec_params = ECParams { frontier_limit: 10, search_limit_timeout: None, search_limit_description_length: Some(8.0), }; let params = lambda::CompressionParams::default(); let mut frontiers = Vec::new(); for i in 1..6 { println!("running EC iteration {}", i); let (new_dsl, new_frontiers) = dsl.ec(&ec_params, ¶ms, &tasks); dsl = new_dsl; frontiers = new_frontiers; let n_hit = frontiers.iter().filter(|f| !f.is_empty()).count(); println!("hit {} of {}", n_hit, tasks.len()); } assert!(!dsl.invented.is_empty()); for &(ref expr, _, _) in &dsl.invented { println!("invented {}", dsl.display(expr)) }
fn ec_with_recognition<O: Sync, R>(
&self,
ecparams: &ECParams,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>],
recognizer: R
) -> (Self, Vec<ECFrontier<Self>>) where
R: FnOnce(&Self, &[Task<Self, Self::Expression, O>]) -> Vec<Self>,
&self,
ecparams: &ECParams,
params: &Self::Params,
tasks: &[Task<Self, Self::Expression, O>],
recognizer: R
) -> (Self, Vec<ECFrontier<Self>>) where
R: FnOnce(&Self, &[Task<Self, Self::Expression, O>]) -> Vec<Self>,
The entry point for one iteration of the EC algorithm with a recognizer, very similar to
ec
.
The recognizer supplies a representation for every task which is then used for exploration-compression.
Returned solutions include the log-prior and log-likelihood of successful expressions.
fn explore<O: Sync>(
&self,
ec_params: &ECParams,
tasks: &[Task<Self, Self::Expression, O>]
) -> Vec<ECFrontier<Self>>
&self,
ec_params: &ECParams,
tasks: &[Task<Self, Self::Expression, O>]
) -> Vec<ECFrontier<Self>>
Enumerate solutions for the given tasks.
Considers a "solution" to be any expression with finite log-probability according to a task's oracle.
Each task will be associated with at most params.frontier_limit
many such expressions,
and enumeration is stopped when params.search_limit
valid expressions have been checked.
Examples
use programinduction::{EC, ECParams}; use programinduction::pcfg::{Grammar, Rule, task_by_evaluation}; fn evaluator(name: &str, inps: &[i32]) -> i32 { match name { "0" => 0, "1" => 1, "plus" => inps[0] + inps[1], _ => unreachable!(), } } let g = Grammar::new( tp!(EXPR), vec![ Rule::new("0", tp!(EXPR), 1.0), Rule::new("1", tp!(EXPR), 1.0), Rule::new("plus", tp!(@arrow[tp!(EXPR), tp!(EXPR), tp!(EXPR)]), 1.0), ], ); let ec_params = ECParams { frontier_limit: 1, search_limit_timeout: Some(std::time::Duration::new(1, 0)), search_limit_description_length: None, }; // task: the number 4 let task = task_by_evaluation(&evaluator, &4, tp!(EXPR)); let frontiers = g.explore(&ec_params, &[task]); assert!(frontiers[0].best_solution().is_some());
fn explore_with_recognition<O: Sync>(
&self,
ec_params: &ECParams,
tasks: &[Task<Self, Self::Expression, O>],
representations: &[Self]
) -> Vec<ECFrontier<Self>>
&self,
ec_params: &ECParams,
tasks: &[Task<Self, Self::Expression, O>],
representations: &[Self]
) -> Vec<ECFrontier<Self>>
Like explore
, but with specific "recognized" representations for each task.
Implementors
impl EC for Language type Expression = Expression; type Params = CompressionParams;
impl EC for Grammar type Expression = AppliedRule; type Params = EstimationParams;