I would like to test an experimental algorithm for string classification. More precisely, the dataset should be split into a set GOOD of good strigs and a set BAD of bad strings. The algorithm should learn a model that is consistent with the dataset, in the sense that the output model always answers Yes for strings in GOOD, No for strings in BAD. The algorithm can behave arbitrarily on strings that are neither in GOOD nor in BAD.

Note that I'm not interested in prediction for strings not in the dataset. The only important thing is to obtain a model that is consistency with the given dataset. What makes the problem interesting is the fact that the model can be much smaller than the dataset. For instance, if the model is an automaton, then in some cases one can find automata that are exponentially smaller than the number of bits necessary to represent the dataset.

I would like to test our heuristics against known algorithms/datasets.

  1. What are standard datasets used for testing new experimental heuristics in this area?
  2. What are the standard tools used for such classification tasks on strings.

Note: The goal is to classify strings, not large texts. In particular, a typical size for the strings being considered is 1000 characters (at most). Additionally, one can assume these strings have the same length.

  • $\begingroup$ Welcome to DataScienceSE. There is something strange about your desscription: as far as I understand, this algorithm can only classify the strings it has seen in the training set, right? If so I don't see the point, since if there is finite list of strings in each class then the class can simply be stored in a map. Also are you assuming that these strings correspond to real natural language sentences or are they arbitrary? Is it supposed to work with any vocabulary, e.g. Chinese alphabet? $\endgroup$
    – Erwan
    Commented Mar 22, 2021 at 0:30
  • $\begingroup$ Good point. The point here is that the model should be much smaller than the input dataset. For instance, in automata learning, you want to find a finite automaton consistent with the dataset. The automaton can be exponentially smaller than the dataset. I have edited the question to make it clearer. $\endgroup$
    – verifying
    Commented Mar 22, 2021 at 8:31

1 Answer 1


Your description corresponds to the general problem of grammatical inference (or grammar induction): as opposed to statistical models, the goal is to learn the exact language represented as a formal grammar. Importantly this is symbolic learning, i.e. there is no concept of minimizing error because errors are not acceptable at all.

As far as I know the field is rather theoretical, as opposed to statistical ML: one formally proves that some classes of languages can or cannot be learnt under specific constraints. A type of learning framework which used to be studied in this context (not sure if it's still active) is language identification in the limit. A quite different framework is Probably approximately correct learning (PAC), but in this is more general and not strictly about grammatical inference (to the best of my knowledge).

So I'm not aware of any real dataset: in general arbitrary datasets don't have the kind of formal constraints which are relevant for this kind of problem. But it's possible that some parts of the literature contain at least artificial datasets.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.