This may take 3 months or more, since drafts are reviewed in no specific order. There are 2,433 pending submissions waiting for review.
If the submission is accepted, then this page will be moved into the article space.
If the submission is declined, then the reason will be posted here.
In the meantime, you can continue to improve this submission by editing normally.
Where to get help
If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews.
If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed.
To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags.
Characteristic Samples is a concept in the field of grammatical inference, related to passive learning. In passive learning, an inference algorithm is given a set of pairs of strings and labels , and returns a representation that is consistent with . Characteristic samples consider the scenario when the goal is not only finding a representation consistent with , but finding a representation that recognizes a specific target language.
A characteristic sample of language is a set of pairs of the form where:
if and only if
if and only if
Given the characteristic sample , 's output on it is a representation , e.g an automaton, that recognizes .
There are three entities in the learning paradigm connected to characteristic samples, the adversary, the teacher and the inference algorithm.
Given a class of languages and a class of representations for the languages , the paradigm goes as follows:
The adversary selects a language and reports it to the teacher
The teacher then computes a set of strings and label them correctly according to , trying to make sure that the inference algorithm will compute
The adversary can add correctly labeled words to the set in order to confuse the inference algorithm
The inference algorithm gets the sample and computes a representation consistent with the sample.
The goal is that when the inference algorithm receives a characteristic sample for a language , or a sample that subsumes a characteristic sample for , it will return a representation that recognizes exactly the language .
Given a class of representations such that equivalence is undecidable, for every polynomial and every , there exist two representations and of sizes bounded by , that recognize different languages but are inseparable by any string of size bounded by . Assuming this is not the case, we can decide if and are equivalent by simulating their run on all strings of size smaller than , contradicting the assumption that equivalence is undecidable.
Given a class that has characteristic samples, let and be representations that recognize and respectively. Under the assumption that there is a characteristic sample for , that is also consistent with , we'll assume falsely that there exist a characteristic sample for , that is consistent with . By the definition of characteristic sample, the inference algorithm must return a representation which recognizes the language if given a sample that subsumes the characteristic sample itself. But for the sample , the answer of the inferring algorithm needs to recognize both and , in contradiction.
The proof that DFA's are learnable using characteristic samples, relies on the fact that every regular language has a finite number of equivalence classes with respect to the right congruence relation, (where for if and only if ). Note that if , are not congruent with respect to , there exists a string such that but or vice versa, this string is called a separating suffix.
The construction of a characteristic sample for a language by the teacher goes as follows. Firstly, by running a depth first search on a deterministic automaton recognizing , starting from it's initial state, we get a suffix closed set of words, , ordered in shortlex order. From the fact above, we know that for every two states in the automaton, there exists a seperating suffix that separates between every two strings that the run of on them ends in the respective states. We refer to the set of separating suffixes as . The labeled set (sample) of words the teacher gives the adversary is where is the correct lable of (whether it is in or not). We may assume that .
Given the sample from the adversary , the construction of the automaton by the inference algorithm starts with defining and , which are the set of prefixes and suffixes of respectively. Now the algorithm constructs a matrix where the elements of function as the rows, ordered by the shortlex order, and the elements of function as the columns, ordered by the shortlex order. Next, the cells in the matrix are filled in the following manner for prefix and suffix :
If
else,
Now, we say row and are distinguishable if there exists an index such that . The next stage of the inference algorithm is to construct the set of distinguishable rows in , by initializing with and iterating from the first row of downwards and doing the following for row :
If is distinguishable from all elements in , add it to
else, pass on it to the next row
From the way the teacher constructed the sample it passed to the adversary, we know that for every and every , the row exists in , and from the construction of , there exists a row such that and are indistinguishable. The output automaton will be defined as follows:
The set of states is .
The initial state is the state corresponding to row .
The accepting states is the set .
The transitions function will be defined , where is the element in that is indistinguishable from .
There are some classes that do not have polynomially sized characteristic samples. For example, from the first theorem in the Related theorems segment, it has been shown that the following classes of languages do not have polynomial sized characteristic samples:
- The class of context-free grammars Languages over of cardinality larger then [1]
- The class of linear grammar languages over of cardinality larger then [1]
- The class of simple deterministic grammars Languages[1]
- The class of nondeterministic finite automata Languages[1]
A representation class is semi-poly teachable if there exist 3 polynomials , a teacher , and an inference algorithm , such that for any adversary the following holds:
Selects a represntation of size from
computes a sample that is consistent with the language that recognize, of size bounded by and the strings in the sample bounded by length
adds correctly labeled strings to the sample computed by , making the new sample of size
then computes a representation equivalent to in time bounded by
The class of languages that there exists a polynomial algorithm that given a sample, returns a representation consistent with the sample is called consistency easy.
Given a representation class , and a set of identification algorithms for , is polynomially characterizable for if any has a characteristic sample of size polynomial of 's size, , that for every , 's output on is .
Assuming has characteristic samples, then for every representation , its characteristic sample holds the conditions for the sample computaed by the teacher, and the output of on every sample such that is equivalent to from the definition of characteristic sample.
Assuming that is semi-poly teachable, then for every representation , the computed sample by the teacher is a characteristic sample for .
Assuming falsely that is not polynomially characterizable, there are two non equivalent representations , with characteristic samples and respectively. From the definition of characteristic samples, any inference algorithm need to infer from the sample a representation compatible with and , in contradiction.