Review waiting, please be patient. This may take 4 months or more, since drafts are reviewed in no specific order. There are 3,105 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. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review 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. Add tags to your draft Editor resources Find sources:  Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL Easy tools: Citation bot ( help) | Advanced: Fix bare URLs Reviewer tools Instructions · What links here · Characteristic samples ( talk:  + · bio) · ( log) · Copyvios report · reFill · Citation Bot · (Search:  Google,  Bing,  Wikipedia) · Submitted 21 days ago by Gal Meirom ( talk:  D · +) · Last edited 7 hours ago by TakuyaMurata

Characteristic Samples is a concept in the field of grammatical inference, related to passive learning. In passive learning, an inference algorithm ${\displaystyle I}$ is given a set of pairs of strings and labels ${\displaystyle S}$, and returns a representation ${\displaystyle R}$ that is consistent with ${\displaystyle S}$. Characteristic samples consider the scenario when the goal is not only finding a representation consistent with ${\displaystyle S}$, but finding a representation that recognizes a specific target language.

A characteristic sample of language ${\displaystyle L}$ is a set of pairs of the form ${\displaystyle (s,l(s))}$ where:

1. ${\displaystyle l(s)=1}$ if and only if ${\displaystyle s\in L}$
2. ${\displaystyle l(s)=-1}$ if and only if ${\displaystyle s\notin L}$

Given the characteristic sample ${\displaystyle S}$, ${\displaystyle I}$'s output on it is a representation ${\displaystyle R}$, e.g an automaton, that recognizes ${\displaystyle L}$.

Formal Definition

The Learning Paradigm associated with Characteristic Samples

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 ${\displaystyle \mathbb {C} }$ and a class of representations for the languages ${\displaystyle \mathbb {R} }$, the paradigm goes as follows:

• The adversary ${\displaystyle A}$ selects a language ${\displaystyle L\in \mathbb {C} }$ and reports it to the teacher
• The teacher ${\displaystyle T}$ then computes a set of strings and label them correctly according to ${\displaystyle L}$, trying to make sure that the inference algorithm will compute ${\displaystyle L}$
• The adversary can add correctly labeled words to the set in order to confuse the inference algorithm
• The inference algorithm ${\displaystyle I}$ gets the sample and computes a representation ${\displaystyle R\in \mathbb {R} }$ consistent with the sample.

The goal is that when the inference algorithm receives a characteristic sample for a language ${\displaystyle L}$, or a sample that subsumes a characteristic sample for ${\displaystyle L}$, it will return a representation that recognizes exactly the language ${\displaystyle L}$.

Sample

Sample ${\displaystyle S}$ is a set of pairs of the form ${\displaystyle (s,l(s))}$ such that ${\displaystyle l(s)\in \{-1,1\}}$

Sample consistent with a language

We say that a sample ${\displaystyle S}$ is consistent with language ${\displaystyle L}$ if for every pair ${\displaystyle (s,l(s))}$ in ${\displaystyle S}$:

1. ${\displaystyle l(s)=1{\text{ if and only if }}s\in L}$
2. ${\displaystyle l(s)=-1{\text{ if and only if }}s\notin L}$

Characteristic sample

Given an inference algorithm ${\displaystyle I}$ and a language ${\displaystyle L}$, a sample ${\displaystyle S}$ that is consistent with ${\displaystyle L}$ is called a characteristic sample of ${\displaystyle L}$ for ${\displaystyle I}$ if:

• ${\displaystyle I}$'s output on ${\displaystyle S}$ is a representation ${\displaystyle R}$ that recognizes ${\displaystyle L}$.
• For every sample ${\displaystyle D}$ that is consistent with ${\displaystyle L}$ and also fulfils ${\displaystyle S\subseteq D}$, ${\displaystyle I}$'s output on ${\displaystyle D}$ is a representation ${\displaystyle R}$ that recognizes ${\displaystyle L}$.

A Class of languages ${\displaystyle \mathbb {C} }$ is said to have charistaristic samples if every ${\displaystyle L\in \mathbb {C} }$ has a characteristic sample.

Related Theorems

Theorem

If equivalence is undecidable for a class ${\textstyle \mathbb {C} }$ over ${\textstyle \Sigma }$ of cardinality bigger than 1, then ${\textstyle \mathbb {C} }$ doesn't have characteristic samples. ^[1]

Proof

Given a class of representations ${\textstyle \mathbb {C} }$ such that equivalence is undecidable, for every polynomial ${\displaystyle p(x)}$ and every ${\displaystyle n\in \mathbb {N} }$, there exist two representations ${\displaystyle r_{1}}$ and ${\displaystyle r_{2}}$ of sizes bounded by ${\displaystyle n}$, that recognize different languages but are inseparable by any string of size bounded by ${\displaystyle p(n)}$. Assuming this is not the case, we can decide if ${\displaystyle r_{1}}$ and ${\displaystyle r_{2}}$ are equivalent by simulating their run on all strings of size smaller than ${\displaystyle p(n)}$, contradicting the assumption that equivalence is undecidable.

Theorem

If ${\displaystyle S_{1}}$is a charateristic sample for ${\displaystyle L_{1}}$and is also consistent with ${\displaystyle L_{2}}$, then every characteristic sample of ${\displaystyle L_{2}}$, is inconsistent with ${\displaystyle L_{1}}$. ^[1]

Proof

Given a class ${\textstyle \mathbb {C} }$ that has characteristic samples, let ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$ be representations that recognize ${\displaystyle L_{1}}$ and ${\displaystyle L_{2}}$ respectively. Under the assumption that there is a characteristic sample for ${\displaystyle L_{1}}$, ${\displaystyle S_{1}}$ that is also consistent with ${\displaystyle L_{2}}$, we'll assume falsely that there exist a characteristic sample for ${\displaystyle L_{2}}$, ${\displaystyle S_{2}}$ that is consistent with ${\displaystyle L_{1}}$. By the definition of characteristic sample, the inference algorithm ${\displaystyle I}$ must return a representation which recognizes the language if given a sample that subsumes the characteristic sample itself. But for the sample ${\displaystyle S_{1}\cup S_{2}}$, the answer of the inferring algorithm needs to recognize both ${\displaystyle L_{1}}$ and ${\displaystyle L_{2}}$, in contradiction.

Theorem

If a class is polynomialy learnable by example based queries, it is learnable with characteristic samples. ^[2]

Polynomialy characterizable classes

Regular languages ^[3]

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, ${\displaystyle \sim _{L}}$ (where ${\displaystyle x\sim _{L}y}$ for ${\displaystyle x,y\in \Sigma ^{*}}$ if and only if ${\displaystyle \forall z\in \Sigma ^{*}:xz\in L\leftrightarrow yz\in L}$). Note that if ${\displaystyle x}$, ${\displaystyle y}$ are not congruent with respect to ${\displaystyle \sim _{L}}$, there exists a string ${\displaystyle z}$ such that ${\displaystyle xz\in L}$ but ${\displaystyle yz\notin L}$ or vice versa, this string is called a separating suffix.

Constructing a characteristic sample

The construction of a characteristic sample for a language ${\displaystyle L}$ by the teacher goes as follows. Firstly, by running a depth first search on a deterministic automaton ${\displaystyle A}$ recognizing ${\displaystyle L}$, starting from it's initial state, we get a suffix closed set of words, ${\displaystyle W}$, 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 ${\displaystyle A}$ on them ends in the respective states. We refer to the set of separating suffixes as ${\displaystyle S}$. The labeled set (sample) of words the teacher gives the adversary is ${\displaystyle \{(w,l(w))|w\in W\cdot S\cup W\cdot \Sigma \cdot S\}}$ where ${\displaystyle l(w)}$ is the correct lable of ${\displaystyle w}$ (whether it is in ${\displaystyle L}$ or not). We may assume that ${\displaystyle \epsilon \in S}$.

Constructing a deterministic automata

Given the sample from the adversary ${\displaystyle W}$, the construction of the automaton by the inference algorithm ${\displaystyle I}$ starts with defining ${\displaystyle P={\text{prefix}}(W)}$ and ${\displaystyle S={\text{suffix}}(W)}$, which are the set of prefixes and suffixes of ${\displaystyle W}$ respectively. Now the algorithm constructs a matrix ${\displaystyle M}$ where the elements of ${\displaystyle P}$ function as the rows, ordered by the shortlex order, and the elements of ${\displaystyle S}$ function as the columns, ordered by the shortlex order. Next, the cells in the matrix are filled in the following manner for prefix ${\displaystyle p_{i}}$ and suffix ${\displaystyle s_{j}}$:

1. If ${\displaystyle p_{i}s_{j}\in W\rightarrow M_{ij}=l(p_{i}s_{j})}$
2. else, ${\displaystyle M_{ij}=0}$

Now, we say row ${\displaystyle i}$ and ${\displaystyle t}$ are distinguishable if there exists an index ${\displaystyle j}$ such that ${\displaystyle M_{ij}=-1\times M_{tj}}$. The next stage of the inference algorithm is to construct the set ${\displaystyle Q}$ of distinguishable rows in ${\displaystyle M}$, by initializing ${\displaystyle Q}$ with ${\displaystyle \epsilon }$ and iterating from the first row of ${\displaystyle M}$ downwards and doing the following for row ${\displaystyle r_{i}}$:

1. If ${\displaystyle r_{i}}$ is distinguishable from all elements in ${\displaystyle Q}$, add it to ${\displaystyle Q}$
2. 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 ${\displaystyle s\in Q}$ and every ${\displaystyle \sigma \in \Sigma }$, the row ${\displaystyle s\sigma }$ exists in ${\displaystyle M}$, and from the construction of ${\displaystyle Q}$, there exists a row ${\displaystyle s'\in Q}$ such that ${\displaystyle s'}$ and ${\displaystyle s\sigma }$ are indistinguishable. The output automaton will be defined as follows:

• The set of states is ${\displaystyle Q}$.
• The initial state is the state corresponding to row ${\displaystyle \epsilon \in Q}$.
• The accepting states is the set ${\displaystyle \{s\in Q|{\text{ }}l(s)=1\}}$.
• The transitions function will be defined ${\displaystyle \delta (s,\sigma )=s'}$, where ${\displaystyle s'}$ is the element in ${\displaystyle Q}$ that is indistinguishable from ${\displaystyle s\sigma }$.

Other polynomially characterizable classes

• Class of languages recognizable by multiplicity automatons ^[4]
• Class of languages recognizable by tree automata ^[5]
• Class of languages recognizable by multiplicity tree automata ^[6]
• Class of languages recognizable by Fully-Ordered Lattice Automata ^[7]
• Class of languages recognizable by Visibly One-Counter Automata ^[8]
• Class of fully informative omega regular languages ^{[9] [10]}

Non polynomially characterizable classes

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:

• ${\displaystyle \mathbb {CFG} }$ - The class of context-free grammars Languages over ${\displaystyle \Sigma }$ of cardinality larger then ${\displaystyle 1}$ ^[1]
• ${\displaystyle \mathbb {LING} }$ - The class of linear grammar languages over ${\displaystyle \Sigma }$ of cardinality larger then ${\displaystyle 1}$ ^[1]
• ${\displaystyle \mathbb {SDG} }$ - The class of simple deterministic grammars Languages ^[1]
• ${\displaystyle \mathbb {NFA} }$ - The class of nondeterministic finite automata Languages ^[1]

Relations to other learning paradigms

Classes of representations that has characteristic samples relates to the following learning paradigms:

Class of semi-poly ${\displaystyle T/L}$ teachable languages ^[2]

A representation class ${\displaystyle \mathbb {C} }$ is semi-poly ${\displaystyle T/L}$ teachable if there exist 3 polynomials ${\displaystyle p,q,r}$, a teacher ${\displaystyle T}$ , and an inference algorithm ${\displaystyle I}$, such that for any adversary ${\displaystyle A}$ the following holds:

• ${\displaystyle A}$ Selects a represntation ${\displaystyle R}$ of size ${\displaystyle n}$ from ${\displaystyle \mathbb {C} }$
• ${\displaystyle T}$ computes a sample that is consistent with the language that ${\displaystyle R}$ recognize, of size bounded by ${\displaystyle p(n)}$ and the strings in the sample bounded by length ${\displaystyle q(n)}$
• ${\displaystyle A}$ adds correctly labeled strings to the sample computed by ${\displaystyle T}$, making the new sample of size ${\displaystyle m}$
• ${\displaystyle I}$ then computes a representation equivalent to ${\displaystyle R}$ in time bounded by ${\displaystyle r(m)}$

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.

Polynomially characterizable languages

Given a representation class ${\displaystyle \mathbb {R} }$, and ${\displaystyle {\mathcal {I}}}$ a set of identification algorithms for ${\displaystyle \mathbb {R} }$, ${\displaystyle \mathbb {R} }$ is polynomially characterizable for ${\displaystyle {\mathcal {I}}}$ if any ${\displaystyle R\in \mathbb {R} }$ has a characteristic sample of size polynomial of ${\displaystyle R}$'s size, ${\displaystyle S}$, that for every ${\displaystyle I\in {\mathcal {I}}}$, ${\displaystyle I}$'s output on ${\displaystyle S}$ is ${\displaystyle R}$.

Releations between the paradigms

Theorem

A consistency-easy class ${\displaystyle \mathbb {C} }$ has characteristic samples if and only if it is semi-poly ${\displaystyle T/L}$ teachable. ^[1]

Proof

Assuming ${\displaystyle \mathbb {C} }$ has characteristic samples, then for every representation ${\displaystyle R\in \mathbb {C} }$, its characteristic sample ${\displaystyle S}$ holds the conditions for the sample computaed by the teacher, and the output of ${\displaystyle I}$ on every sample ${\displaystyle S'}$ such that ${\displaystyle S\subseteq S'}$ is equivalent to ${\displaystyle R}$ from the definition of characteristic sample.

Assuming that ${\displaystyle \mathbb {C} }$ is semi-poly ${\displaystyle T/L}$ teachable, then for every representation ${\displaystyle R\in \mathbb {C} }$, the computed sample by the teacher ${\displaystyle S}$ is a characteristic sample for ${\displaystyle R}$.

Theorem

If ${\displaystyle \mathbb {C} }$ has characteristic sample, then ${\displaystyle \mathbb {C} }$ is polynomially characterizable. ^[1]

Proof

Assuming falsely that ${\displaystyle \mathbb {C} }$ is not polynomially characterizable, there are two non equivalent representations ${\displaystyle R_{1},R_{2}\in \mathbb {C} }$, with characteristic samples ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$ respectively. From the definition of characteristic samples, any inference algorithm ${\displaystyle I}$ need to infer from the sample ${\displaystyle S_{1}\cup S_{2}}$ a representation compatible with ${\displaystyle R_{1}}$ and ${\displaystyle R_{2}}$, in contradiction.

See Also

• Grammar induction
• Passive learning
• Induction of regular languages
• Deterministic finite automaton

References