Trouver l'expression régulière minimale est-il un problème NP-complet?

Je pense au problème suivant: je veux trouver une expression régulière qui correspond à un ensemble particulier de chaînes (par exemple, des adresses électroniques valides) et ne correspond à aucune autre (adresses électroniques non valides).

Supposons que par expression régulière, nous entendons une machine à états finis bien définie. Je ne connais pas la terminologie exacte, mais convenons d'une classe d'expressions autorisées.

Au lieu de créer manuellement l'expression, je veux lui donner un ensemble d'exemples positifs et négatifs.

Il devrait ensuite trouver une expression qui corresponde aux +, rejette les - et est minimale dans un sens bien défini (nombre d'états dans les automates?).

Mes questions sont:

• A-t-on envisagé ce problème, comment peut-il être défini de manière plus concrète et résolu efficacement? Peut-on le résoudre en temps polynomial? Est-ce que NP est complet, pouvons-nous l'approcher d'une manière ou d'une autre? Pour quelles classes d'expressions cela fonctionnerait-il? J'apprécierais tout pointeur sur des manuels, des articles ou autres qui traitent de ce sujet.
• Cela at-il un lien quelconque avec la complexité de Kolmogorov?
• Est-ce que cela a un rapport avec l'apprentissage? Si l'expression régulière est conforme à mes exemples, en raison de son caractère minimal, pouvons-nous dire quelque chose à propos de son pouvoir de généralisation sur des exemples encore invisibles? Quel critère de minimalité conviendrait mieux à cela? Lequel serait le plus efficace? Cela at-il des liens avec l’apprentissage automatique? Encore une fois, tous les indicateurs seraient utiles ...

Désolé pour la question confuse ... Pointez-moi dans la bonne direction pour comprendre cela. Merci !

Oui, c'est NP-dur. Pitt et Warmuth ont montré que la recherche de la plus petite compatible DFA avec un échantillon donné ne peut pas être approchée à l' intérieur de $OPT^k$ pour toute constante $k$ , à moins que $P = NP$ .

En ce qui concerne la question d’apprentissage: Kearns et Valiant ont prouvé qu’il était possible d’encoder RSA dans un DFA. Ainsi, même si les exemples étiquetés proviennent de la distribution uniforme, le fait de pouvoir généraliser à des exemples futurs (même issus de la distribution uniforme) romprait le RSA. Par conséquent, nous pensons que dans le pire des cas, le fait d’avoir des exemples étiquetés n’aide pas à l’apprentissage d’un DFA (dans le modèle PAC). C'est l'un des résultats classiques de la dureté cryptographique pour l'apprentissage.

Ces deux problèmes sont étroitement liés en raison de ce que nous appelons le théorème du rasoir d'Occam . Il indique essentiellement que si nous disposons d'une procédure permettant de trouver la plus petite hypothèse d'une classe donnée qui soit cohérente avec un échantillon étiqueté par une hypothèse de la même classe, nous pouvons alors apprendre cette classe. Donc, étant donné le résultat de la dureté RSA, nous nous attendrions à ce que trouver le plus petit DFA cohérent soit difficile en général!

Pour ajouter un résultat d'apprentissage positif, Angluin a montré que vous pouvez apprendre un DFA si vous devez créer vos propres exemples, mais cela nécessite le pouvoir supplémentaire de pouvoir demander: "mon hypothèse actuelle est-elle correcte?" C'était aussi un document fondateur dans l'apprentissage.

Pour répondre à votre autre question, tout cela est en effet lié à la complexité de Kolmogorov, car le problème d'apprentissage devient plus facile lorsque la représentation canonique du DFA cible a une faible complexité.

Je réponds aux aspects liés à l'apprentissage de la question.

Ce problème semble être appelé «apprentissage DFA» dans la littérature.

Gold [Gol78] a montré qu'il est NP-complet de décider, étant donné k ∈ℕ et deux ensembles finis P et N de chaînes, s'il existe un automate déterministe à états finis (DFA) avec au plus k états acceptant chaque chaîne P et aucune des chaînes de N . Le document [PH01] semble aborder les problèmes liés à cette motivation (il peut y en avoir beaucoup plus; cela a été soulevé lorsque j'ai essayé de trouver des documents pertinents avec Google).

Les références

[Gol78] E Mark Gold. Complexité de l'identification des automates à partir de données données. Information and Control , 37 (3): 302–320, juin 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh et Vasant Honavar. Apprentissage de DFA à partir d’exemples simples. Machine Learning , 44 (1–2): 9–35, juillet 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh- dfa.pdf

Tout au long de cette discussion, il a été supposé que trouver une expression régulière minimale revenait à trouver un FSM reconnaissant le langage, mais ce sont deux choses différentes. Si je me souviens bien, un DFA peut être minimisé en temps polynomial, alors que trouver une expression régulière minimale qui représente un langage régulier donné est difficile à obtenir. Ce dernier est l'un de ces résultats qui appartiennent au folklore de la théorie des automates, mais dont la preuve ne peut être trouvée nulle part. Je pense que c'est indiqué comme un exercice dans le livre de Papadimitrou.

Voir aussi ce poste de débordement de pile. Le livre que vous recherchez semble être Introduction à la théorie du calcul de Michael Sipser.

Vous posez deux questions différentes, alors prenez-les une à la fois:

Is finding a minimal Finite State Machine for a language L NP-complete?

Non ce n'est pas. La publication Stack Overflow décrit un algorithme naïf n ^ 2 permettant de réduire un FSM à sa taille minimale. (En partant des états d'arrêt, combinez des états "identiques" dans un sens précis.)

Apparemment (je n'ai pas suivi le lien), il existe un algorithme n log n pour le faire.

I have a training set of strings, how do I find the minimal FSM 
that separates the good examples from the bad?

Comme vous l'avez dit, votre ensemble de formation décrit un langage fini . Les langues finies correspondent trivialement à un FSM - créez un ensemble linéaire d'états se terminant par un état d'arrêt pour chaque chaîne de votre langue, aucune boucle n'est requise. Ensuite, exécutez l'algorithme de minimisation FSM sur la machine résultante.

Is this a good way to build a classifier?

Je ne dirais pas ça. Réduire au minimum le FSM ne change pas son pouvoir discriminant - c'est en quelque sorte le but. Le FSM minimal accepte exactement l'ensemble de chaînes comme n'importe quel FSM non minimal équivalent.

En général, les expressions régulières ne conviennent pas à la classification de nouvelles données. Pour tout ensemble d’entraînement fini, vous obtiendrez un RE / FSM qui correspond uniquement aux exemples positifs de cet ensemble, sans possibilité de généraliser à de nouvelles données. Je n'ai jamais vu une approche qui tente de trouver un langage régulier infini qui correspond à un corpus de formation.

Pour l’apprentissage automatique, vous recherchez un classificateur, un arbre de décision, un réseau de neurones ou un élément plus exotique de Bayes naïf. L'intelligence artificielle de Russell et Norvig : une approche moderne est un endroit aussi propice que n'importe lequel pour trouver un aperçu des techniques d'apprentissage automatique (et bien plus encore).