Characteristic samples

Characteristic samples is a concept in the field of grammatical inference, related to passive learning. In passive learning, an inference algorithm I is given a set of pairs of strings and labels S , and returns a representation R that is consistent with S . Characteristic samples consider the scenario when the goal is not only finding a representation consistent with S , but finding a representation that recognizes a specific target language. A characteristic sample of language L is a set of pairs of the form (s, l(s)) where: # l(s) = 1 if and only if s\in L # l(s) = -1 if and only if s\notin L Given the characteristic sample S , I 's output on it is a representation R , e.g. an automaton, that recognizes L .

Characteristic samples is a concept in the field of grammatical inference, related to passive learning. In passive learning, an inference algorithm I is given a set of pairs of strings and labels S , and returns a representation R that is consistent with S . Characteristic samples consider the scenario when the goal is not only finding a representation consistent with S , but finding a representation that recognizes a specific target language. A characteristic sample of language L is a set of pairs of the form (s, l(s)) where: l(s) = 1 if and only if s\in L l(s) = -1 if and only if s\notin L Given the characteristic sample S , I 's output on it is a representation R , e.g. an automaton, that recognizes L . l(s) = 1\text{ if and only if } s\in L l(s) = -1 \text{ if and only if } s\notin L If equivalence is undecidable for a class \mathbb{C} over \Sigma of cardinality bigger than 1, then \mathbb{C} doesn't have characteristic samples. Given a class of representations \mathbb{C} such that equivalence is undecidable, for every polynomial p(x) and every n \in \mathbb{N} , there exist two representations r_1 and r_2 of sizes bounded by n , that recognize different languages but are inseparable by any string of size bounded by p(n) . Assuming this is not the case, we can decide if r_1 and r_2 are equivalent by simulating their run on all strings of size smaller than p(n) , contradicting the assumption that equivalence is undecidable. Given a class \mathbb{C} that has characteristic samples, let R_1 and R_2 be representations that recognize L_1 and L_2 respectively. Under the assumption that there is a characteristic sample for L_1 , S_1 that is also consistent with L_2 , we'll assume falsely that there exist a characteristic sample for L_2 , S_2 that is consistent with L_1 . By the definition of characteristic sample, the inference algorithm I must return a representation which recognizes the language if given a sample that subsumes the characteristic sample itself. But for the sample S_1\cup S_2 , the answer of the inferring algorithm needs to recognize both L_1 and L_2 , in contradiction. Given the sample from the adversary W , the construction of the automaton by the inference algorithm I starts with defining P = \text{prefix}(W) and S = \text{suffix}(W) , which are the set of prefixes and suffixes of W respectively. Now the algorithm constructs a matrix M where the elements of P function as the rows, ordered by the shortlex order, and the elements of S function as the columns, ordered by the shortlex order. Next, the cells in the matrix are filled in the following manner for prefix p_i and suffix s_j : If p_is_j \in W \rightarrow M_{ij} = l(p_is_j) else, M_{ij} = 0 Now, we say row i and t are distinguishable if there exists an index j such that M_{ij} = -1\times M_{tj} . The next stage of the inference algorithm is to construct the set Q of distinguishable rows in M , by initializing Q with \epsilon and iterating from the first row of M downwards and doing the following for row r_i : If r_i is distinguishable from all elements in Q , add it to Q 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 s \in Q and every \sigma \in \Sigma , the row s\sigma exists in M , and from the construction of Q , there exists a row s' \in Q such that s' and s\sigma are indistinguishable. The output automaton will be defined as follows: The set of states is Q . The initial state is the state corresponding to row \epsilon \in Q . The accepting states is the set \{s\in Q|\text{ } l(s)=1\} . The transitions function will be defined \delta(s,\sigma) = s' , where s' is the element in Q that is indistinguishable from s\sigma .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370551737 under CC BY-SA 4.0; modifications have been made.