Est-il possible pour un ordinateur «d'apprendre» une expression régulière à l'aide d'exemples fournis par l'utilisateur?

Est-il possible pour un ordinateur "d'apprendre" une expression régulière à l'aide d'exemples fournis par l'utilisateur?

Clarifier:

• Je ne pas veux apprendre des expressions régulières.
• Je souhaite créer un programme qui "apprend" une expression régulière à partir d'exemples fournis de manière interactive par un utilisateur, peut-être en sélectionnant des parties d'un texte ou en sélectionnant des marqueurs de début ou de fin.

C'est possible? Existe-t-il des algorithmes, des mots-clés, etc. pour lesquels je peux utiliser Google?

EDIT : Merci pour les réponses, mais je ne suis pas intéressé par les outils qui fournissent cette fonctionnalité. Je recherche des informations théoriques, comme des articles, des tutoriels, du code source, des noms d'algorithmes, afin de pouvoir créer quelque chose pour moi-même.

Le livre An Introduction to Computational Learning Theory contient un algorithme pour apprendre un automate fini. Comme tout langage régulier équivaut à un automate fini, il est possible d'apprendre certaines expressions régulières par un programme. Kearns et Valiant montrent quelques cas où il n'est pas possible d'apprendre un automate fini. Un problème connexe est l' apprentissage des modèles de Markov cachés , qui sont des automates probabilistes capables de décrire une séquence de caractères. Notez que la plupart des «expressions régulières» modernes utilisées dans les langages de programmation sont en fait plus fortes que les langages normaux, et donc parfois plus difficiles à apprendre.

Oui, c'est possible, nous pouvons générer des expressions rationnelles à partir d'exemples (texte -> extractions souhaitées). Ceci est un outil en ligne fonctionnel qui fait le travail: http://regex.inginf.units.it/

L'outil en ligne Regex Generator ++ génère une expression régulière à partir d'exemples fournis à l'aide d'un algorithme de recherche GP. L'algorithme GP est piloté par une forme multi-objectifs qui conduit à des performances plus élevées et à une structure de solution plus simple (Rasoir d'Occam). Cet outil est une application de démonstration du Machine Lerning Lab, Université de Trieste (Università degli studi di Trieste). Veuillez regarder le didacticiel vidéo ici .

Ceci est un projet de recherche afin que vous puissiez en savoir plus sur les algorithmes utilisés ici .

Voir! :-)

Trouver une expression régulière / une solution significative à partir d'exemples est possible si et seulement si les exemples fournis décrivent bien le problème. Considérez ces exemples qui décrivent une tâche d'extraction, nous recherchons des codes d'article particuliers; les exemples sont des paires texte / extraction:

"The product code is 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Un gars (humain), en regardant les exemples, peut dire: "les codes d'article sont des choses comme \ d ++ - 345 [AB]"

Lorsque le code article est plus permissif mais que nous n'avons pas fourni d'autres exemples, nous n'avons pas de preuves pour bien comprendre le problème. Lors de l'application de la solution générée par l'homme \ d ++ - 345 [AB] au texte suivant, elle échoue:

"On the back of the item there is a code: 966-347Z"

Vous devez fournir d'autres exemples, afin de mieux décrire ce qu'est une correspondance et ce qui n'est pas une correspondance souhaitée: --ie:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

Le numéro de téléphone n'est pas un identifiant de produit, cela peut être une preuve importante.

Aucun programme informatique ne pourra jamais générer une expression régulière significative basée uniquement sur une liste de correspondances valides. Laissez-moi vous montrer pourquoi.

Supposons que vous fournissiez les exemples 111111 et 999999, si l'ordinateur génère:

1. Une regex correspondant exactement à ces deux exemples: (111111|999999)
2. Une expression régulière correspondant à 6 chiffres identiques (\d)\1{5}
3. Une regex correspondant à 6 uns et neuf [19]{6}
4. Une expression régulière correspondant à 6 chiffres \d{6}
5. L'un des trois ci-dessus, avec des limites de mots, par exemple \b\d{6}\b
6. L'une des trois premières, non précédée ou suivie d'un chiffre, par ex. (?<!\d)\d{6}(?!\d)

Comme vous pouvez le voir, il existe de nombreuses manières de généraliser les exemples en une expression régulière. La seule façon pour l'ordinateur de créer une expression régulière prévisible est de vous demander de répertorier toutes les correspondances possibles. Ensuite, il pourrait générer un modèle de recherche qui correspond exactement à ces correspondances.

Si vous ne souhaitez pas répertorier toutes les correspondances possibles, vous avez besoin d'une description de niveau supérieur. C'est exactement ce que les expressions régulières sont conçues pour fournir. Au lieu de fournir une longue liste de nombres à 6 chiffres, vous dites simplement au programme de faire correspondre "six chiffres quelconques". Dans la syntaxe des expressions régulières, cela devient \ d {6}.

Toute méthode permettant de fournir une description de niveau supérieur aussi flexible que les expressions régulières sera également aussi complexe que les expressions régulières. Tous les outils comme RegexBuddy peuvent faire est de faciliter la création et le test de la description de haut niveau. Au lieu d'utiliser directement la syntaxe d'expression régulière concise, RegexBuddy vous permet d'utiliser des blocs de construction en anglais simple. Mais il ne peut pas créer la description de haut niveau pour vous, car il ne peut pas savoir par magie quand il devrait généraliser vos exemples et quand il ne le devrait pas.

Il est certainement possible de créer un outil qui utilise un exemple de texte avec des instructions fournies par l'utilisateur pour générer une expression régulière. La partie la plus difficile dans la conception d'un tel outil est de savoir comment demander à l'utilisateur les informations d'orientation dont il a besoin, sans rendre l'outil plus difficile à apprendre que les expressions régulières elles-mêmes, et sans restreindre l'outil aux travaux regex courants ou aux expressions régulières simples.

Oui, c'est certainement «possible»; Voici le pseudo-code:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")$";

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

Le problème est qu'il existe un nombre infini d'expressions rationnelles qui correspondent à une liste d'exemples. Ce code fournit la regex la plus simple / la plus stupide de l'ensemble, correspondant essentiellement à tout ce qui se trouve dans la liste des exemples positifs (et rien d'autre, y compris les exemples négatifs).

Je suppose que le vrai défi serait de trouver la regex la plus courte qui correspond à tous les exemples, mais même dans ce cas, l'utilisateur devrait fournir de très bonnes entrées pour s'assurer que l'expression résultante était "la bonne".

Je crois que le terme est «induction». Vous souhaitez induire une grammaire régulière.

Je ne pense pas que ce soit possible avec un ensemble fini d'exemples (positifs ou négatifs). Mais, si je me souviens bien, cela peut être fait s'il y a un Oracle qui peut être consulté. (Fondamentalement, vous devez laisser le programme poser des questions oui / non à l'utilisateur jusqu'à ce qu'il soit satisfait.)

Vous voudrez peut-être jouer un peu avec ce site, c'est assez cool et on dirait qu'il fait quelque chose de similaire à ce dont vous parlez: http://txt2re.com

Il existe un langage dédié aux problèmes comme celui-ci, basé sur le prologue. Ça s'appelle progol .

Comme d'autres l'ont mentionné, l'idée de base est l'apprentissage inductif, souvent appelé ILP ( programmation logique inductive ) dans les cercles d'IA.

Le deuxième lien est l'article wiki sur ILP, qui contient de nombreuses sources utiles si vous souhaitez en savoir plus sur le sujet.

@Yuval a raison. Vous regardez la théorie de l'apprentissage informatique, ou «inférence inductive».

La question est plus compliquée que vous ne le pensez, car la définition de «apprendre» n'est pas triviale. Une définition courante est que l'apprenant peut cracher des réponses quand il le souhaite, mais finalement, il doit soit arrêter de cracher des réponses, soit toujours cracher la même réponse. Cela suppose un nombre infini d'entrées et ne donne absolument aucune garantie quant au moment où le programme prendra sa décision. De plus, vous ne pouvez pas dire quand il a pris sa décision car il pourrait encore afficher quelque chose de différent plus tard.

Par cette définition, je suis presque sûr que les langues ordinaires sont apprenables. Par d'autres définitions, pas tellement ...

J'ai fait des recherches sur Google et CiteSeer et j'ai trouvé ces techniques / articles:

• Identification de la langue dans la limite
• Apprentissage probablement approximativement correct

Aussi «Apprendre des ensembles réguliers à partir de requêtes et de contre-exemples» de Dana Angluin semble prometteur, mais je n'ai pas pu trouver une version PS ou PDF, seulement des citations et des articles de séminaire.

Il semble que ce soit un problème délicat même sur le plan théorique.

S'il est possible pour une personne d'apprendre une expression régulière, alors c'est fondamentalement possible pour un programme. Cependant, ce programme devra être correctement programmé pour pouvoir apprendre. Heureusement, il s'agit d'un espace logique assez fini, donc ce ne serait pas aussi complexe que d'enseigner à un programme pour pouvoir voir des objets ou quelque chose comme ça.