Category: Drafts
-
Fitting Finite Automata
Finite state machines (finite automata) provide a simple model of computation: the machine starts from some initial state, observes a series of inputs, which cause it to transition to different states depending on the input and the current state, and then outputs a value, dependent on its final state. As a well-studied model of simple computations, it is not surprising that finite state machines are one of the earliest and best-studied computational inverse problems. They also provide one of the cleanest sample complexity results. Learning large (many state) state machines is not feasible for passive learners, which attempt to fit bulk-collected data: such learners require a number of data samples that is exponential in the size of the machine. Active learners, on the other hand, which can request information about specific points, are able to learn large state machines, with the number of samples growing quadratically with the number of states in the machine.