Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
6 Cards in this Set
- Front
- Back
|
what are the main challenges of using programs as models to be learned?
|
Unbounded capacity - programs exist in an infinite-dimensional space
syntax-semantics divide -syntactically similar programs have very different behavior, same behavior can be described by many syntactically different programs resource consumption - programs can take a lot of resources to simulate |
|
|
what are the main objects when describing properties a tractable program representation should have?
|
a set of expressions for programs that represents syntax
a set of points with a metric B, with each point representing a behavior of a program, so points in S have a corresponding point in B (or a distribution over B for probabilistic programs) a distribution over behaviors, which corresponds to problems that arise in the natural world |
|
|
is behavior a well-defined concept? what are some concrete examples of B
|
TBD
|
|
|
what is the d-cover concept?
|
it's how probable you are to have a program within a size-bounded set that has a similar behavior to one that is drawn from the natural distribution
|
|
|
what are desired properties of a representation that can be used to define tractability?
|
1. as the size of possible programs increases the probability of having a program that has a behavior close to a randomly picked behavior according to the distribution P will go to 1.
2. as n increases the distance required for having a particular probability of having a good program (one similar to a randomly chosen behavior) goes to 0 3. the size bound required for finding a good program should be as small as possible 4. syntactic and semantic distance should be correlated |
|
|
how are program transformations classified?
|
reductions - semantics preserving transformations that reduce the size of a program
neutral transformations - semantics preserving transformations that don't preserve semantics non-neutral transformations - transformations that don't necessarily preserve semantics, these are further subdivided by type of expression |
