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

Question

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

Pour clarifier:

• Je ne souhaite pas apprendre les 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, par exemple en sélectionnant des parties dans un texte ou en sélectionnant des marqueurs de début ou de fin.

Est-ce possible? Existe-t-il des algorithmes, des mots-clés, etc. que je peux utiliser pour Google?

MODIFIER : merci pour les réponses, mais les outils qui fournissent cette fonctionnalité ne m'intéressent pas. Je recherche des informations théoriques, telles que des documents, des tutoriels, du code source, des noms d'algorithmes, afin de pouvoir créer quelque chose pour moi-même.

Answer 1

Le livre Une introduction à la théorie de l'apprentissage informatique contient un algorithme d'apprentissage automate fini. Comme tout langage régulier est équivalent à un automate fini, il est possible d'apprendre certaines expressions régulières par un programme. Kearns et Valiant montrent certains cas où il n'est pas possible d'apprendre un automate fini. Un problème lié est l'apprentissage des modèles de Markov cachés , qui sont des automates probabilistes pouvant décrire séquence de caractères. Notez que la plupart des "expressions régulières" les plus modernes utilisés dans les langages de programmation sont en réalité plus forts que les langages normaux, et sont donc parfois plus difficiles à apprendre.

Answer 2

Oui c'est possible, nous pouvons générer des expressions rationnelles à partir d’exemples (texte - extractions souhaitées). C’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 des exemples fournis à l'aide d'un algorithme de recherche de stratégie de groupe. L'algorithme GP est basé sur une aptitude multiobjectif qui conduit à des performances plus élevées et à une structure de solution plus simple (Razor d'Occam). Cet outil est une application démonstrative du laboratoire Machine Lerning Lab de l’Université de Trieste (Universit # 224; degli studi di Trieste). Consultez le didacticiel vidéo ici .

Il s'agit d'un projet de recherche pour que vous puissiez en savoir plus sur les algorithmes utilisés ici .

Voici! : -)

Il est possible de trouver une solution rationnelle rationnelle à partir d’exemples 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 il 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

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

Lorsque le code de l'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. Lorsque vous appliquez 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 qui est une correspondance et ce qui n'est pas une correspondance souhaitée: --i.e:

"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. Il peut s'agir d'une preuve importante.

Answer 3

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

Supposons que vous fournissiez les exemples 111111 et 999999 si l'ordinateur devait générer:

1. Une expression rationnelle correspondant exactement à ces deux exemples: (111111 | 999999)
2. Une expression régulière correspondant à 6 chiffres identiques (\ d) \ 1 {5}
3. Une expression rationnelle correspondant à 6 et à neuf [19] {6}
4. Une expression rationnelle correspondant à 6 chiffres \ d {6}
5. N'importe lequel des trois précédents, avec des limites de mots, par ex. \ b \ d {6} \ b
6. L'un des trois premiers, non précédé ni suivi d'un chiffre, par ex. (? <! \ d) \ d {6} (?! \ d)

Comme vous pouvez le constater, les exemples peuvent être généralisés de différentes manières en une expression régulière. Pour créer une expression régulière prévisible, l'ordinateur doit obligatoirement répertorier toutes les correspondances possibles. Il pourrait ensuite générer un modèle de recherche correspondant 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 numéros à 6 chiffres, vous indiquez simplement au programme de faire correspondre "tous les six chiffres". 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 souple que les expressions régulières sera aussi complexe que les expressions régulières. Tous les outils que RegexBuddy peut faire sont destinés à faciliter la création et le test de la description de haut niveau. Au lieu d'utiliser directement la syntaxe succincte des expressions rationnelles, 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 comme 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 ainsi que des instructions fournies par l’utilisateur pour générer une expression régulière. La difficulté avec la conception d’un tel outil est de savoir comment demander à l’utilisateur les informations de guidage 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 tâches de regex courantes ou aux simples expressions régulières.

Answer 4

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 + ")<*>quot;;

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

   return regex;
}

Le problème est qu’il existe un nombre infini de regex qui correspondront à une liste d’exemples. Ce code fournit l'expression rationnelle la plus simple / stupide de l'ensemble, correspondant à tout élément de 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 corresponde à 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". / p>

Answer 5

Je crois que le terme est "induction". Vous voulez 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 existe un Oracle pouvant être consulté. (En gros, vous devez laisser le programme poser des questions oui / non à l’utilisateur jusqu’à ce qu’il soit contenu.)

Answer 6

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

Answer 7

Il existe un langage dédié aux problèmes comme celui-ci, basé sur prolog. C'est ce qu'on appelle progol .

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

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

Answer 8

@Yuval est correct. Vous examinez la théorie de l'apprentissage informatique, ou "l'inférence inductive". "

La question est plus compliquée que vous ne le pensez, car la définition de "apprendre" est non-trivial. Une définition courante est que l'apprenant peut cracher des réponses quand il le souhaite, mais il doit finalement arrêter de cracher des réponses ou 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. En outre, vous ne pouvez pas savoir quand il a pris sa décision car il est possible que quelque chose de différent soit produit ultérieurement.

Par cette définition, je suis à peu près sûr que les langues ordinaires sont apprenables. Par d’autres définitions, pas tellement…

Answer 9

J'ai effectué des recherches sur Google et CiteSeer et découvert ces techniques / documents:

• Identification de la langue dans la limite
• Un apprentissage probablement à peu près correct

Egalement, "Apprendre les ensembles normaux à partir de requêtes et de contre-exemples" de Dana Angluin " Cela semble prometteur, mais je n’ai pas réussi à trouver une version PS ou PDF, mais seulement des citations et des notes de séminaires.

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

Answer 10

S'il est possible pour une personne d'apprendre une expression régulière, il 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 limité, aussi ne serait-il pas aussi complexe que d’enseigner à un programme de voir des objets ou quelque chose comme ça.