Inductive Inference: Theory And Methods

Front 1

what is the idea of inductive inference?

Back 1

inferring a general rule from a set of examples

Front 2

what is the idea identification in the limit?

Back 2

guessing the correct rule after a certain number of examples

Front 3

what is the idea of identification by enumeration?

Back 3

exhaustively searching the space of rules by listing all possible rules then trying them one after another

Front 4

what is the practical problem of identification by enumeration?

Back 4

it usually has a search space exponential in the length of the description for the correct rule

Front 5

what is the first thing that must be specified in order to define an inductive inference problem?

Back 5

the class of rules being considered (usually a class of functions or languages (where a language is a set of words))

another way to think about this is a class of sets from which our set of examples might belong to

Front 6

why do the class of rules need to be specified?

Back 6

to prevent rules that cannot be learned e.g. in a sequence prediction problem where one must guess the nth term of a sequence given 1,...,n-1 terms

if the rule is the nth term is the nth guess +1 then this rule is unlearnable

Front 7

what is an example of a rule classes where the sequence of data consists of integers?

Back 7

the class of rules (or rule space) may be functions f:Z->Z where f(n) is a fixed polynomial with integer coefficients

Front 8

what is an example of a rule class where the sequence of data consists of bit strings

Back 8

the rule space might be the regular sets over the alphabet {0,1}

Front 9

what is the second thing that must be specified in order to define an inductive inference problem?

Back 9

the hypothesis space, i.e., a set of descriptions where each rule in the class has at least one description in the hypothesis space

in terms of the rule space being a class of sets, they hypothesis space can be thought of as machines/programs that compute a set in the rule class

Front 10

what are examples of a hypothesis space when the rule class is regular sets over the alphabet {1,1}

Back 10

regular expressions or context free grammars

Front 11

what is an example of a hypothesis space when the rule class is functions f:z->z that are integer polynomials in a single variable

Back 11

the hypothesis space is essentially the same as the rule class, but we could also presumably use some other representation of polynomial functions e.g. a neural network

Front 12

what is the third thing that must be specified in order to define an inductive inference problem?

Back 12

for each rule its set of examples and the sequences of examples that constitute admissible presentations of the rule

Front 13

what is an admissible presentation of a rule?

Back 13

a examples that hold true for the rule

Front 14

what is the fourth thing that must be specified in order to define an inductive inference problem?

Back 14

the class of inference methods

Front 15

what is the fifth thing that must be specified in order to define an inductive inference problem?

Back 15

criteria for successful inference

Front 16

why can't learning from a program trace be reduced to learning input output pairs of some function?

Back 16

because if one wants to formulate the steps of the trace as input/output pairs of the transition function there is a missing argument of control state

Front 17

what is an acceptor?

Back 17

a finite state machine

Front 18

what is a canonical acceptor for a language L?

Back 18

it is the acceptor with minimal number of states

Front 19

what is the prefix tree acceptor of a set of positive examples from a language i.e. a subset?

Back 19

an acceptor that accepts S

Front 20

what is an example of using the organization or structure of a hypothesis space to do practical inductive inference where the domain is finite state acceptors?

Back 20

if one is learning minimal finite state acceptors then starting from the canonical tree acceptor of a set of examples one can search through state machines that have merged states rather than enumerate through all finite state machines

Front 21

how is organization of search space useful for practical inductive inference?

Back 21

properties of the hypothesis space can be used to avoid search through enumeration

one hypothesis may give information on another hypothesis (e.g. due to similarity) and this means if one is wrong it may be possible to not have to look at the other

Front 22

what is basic idea of subsumption and version spaces as applied to organizing a search space?

Back 22

if the set that corresponds to a hypothesis does not contain a positive example of the true set then any refinement or more specific hypothesis will also not capture the example and thus does not need to be examined conversely if a negative example is captured by a hypothesis then generalizations of the hypothesis do not need to be examined

Front 23

what is the version space algorithm?

Back 23

maintain a set of the most general hypotheses that do not capture any negative examples

also maintain the most specific hypotheses that contain all the positive examples

as more examples are received the hypotheses compatible in both the general set and the specific set will shrink and these hypotheses are the desired ones

Front 24

what is the idea of pruning by forbidden features when it comes to practical inductive inference

Back 24

one can identify part of a hypothesis as the root cause of its failure on many examples and thus avoid examining any hypothesis that has this part

Front 25

how was forbidden feature idea applied to searching the space of context-free grammars (CFGs)?

Back 25

CFGs are enumerated in increasing order of complexity

starting from the first a grammar is tested against a sample, if the grammar fails a routine determines the first production in the grammar that can be changed to avoid failure

the search through the enumerated list of grammars skips over any following grammar that contains the production (grammars close together in the enumeration should be similar and so some will probably have this production and be skipped)

Front 26

what is the idea of jumping to conclusions or constructive methods?

Back 26

usually heuristic search
the opposite of pruning systematic search. basically using the data and information about the hypothesis space to jump to a hypothesis even if it means skipping over other possibly consistent hypotheses

Front 27

what are the downsides of constructive algorithms?

Back 27

they usually don't have good theoretical descriptions of the optimality of their solutions

Front 28

what is the constructive algorithm of k-tails, used for inferring non-deterministic finite-state transducers?

Back 28

a parameter k is used to heuristically determine if states in a machine should be the same, by seeing if their behavior on strings of length less than k is the same.

if states behave the same they are identified(collapsed/merged?) creating a new transducer

Front 29

what are some inductive problems that have constructive algorithm solutions with guarantees?

Back 29

learning context-free grammars from bracketed examples

inferring pattern languages

inferring k-reversible languages

Front 30

what is the learning context free grammars from bracketed examples problem?

Back 30

learning a grammar given examples of the language along with unlabeled parse trees i.e. trying to identify internal labels for the nodes in the example parse trees

Front 31

what are pattern languages?

Back 31

a pattern language is a set of strings that can be generated by a string containing constants and variables (a pattern)

Front 32

what are k-reversible languages?

Back 32

a proper subclass of regular languages where if two strings have a same middle part of length k then any other strings with a different suffix after the middle part are also in the language

Front 33

how do the systems of Hardy and Shaw approach inference of LISP programs?

Back 33

they start with a schema program and use data to fill in the details of the schema

Front 34

what is the summers approach to program induction?

Back 34

the approach uses a recursive schemata and fills it in by rewriting the output in terms of cars, cdrs, and cons applied to the input and then a recursive relation is searched for within these basic list expressions

he also has a method for introducing auxiliary variables to build more complicated functions