Comment Apple trouve-t-il les dates, heures et adresses dans les e-mails?

128

Dans le client de messagerie iOS, lorsqu'un e-mail contient une date, une heure ou un lieu, le texte devient un hyperlien et il est possible de créer un rendez-vous ou de consulter une carte en appuyant simplement sur le lien. Cela fonctionne non seulement pour les e-mails en anglais, mais également dans d'autres langues. J'adore cette fonctionnalité et j'aimerais comprendre comment ils le font.

La manière naïve de le faire serait d'avoir de nombreuses expressions régulières et de les exécuter toutes. Cependant, cela ne va pas très bien évoluer et ne fonctionnera que pour une langue ou un format de date spécifique, etc. Je pense qu'Apple doit utiliser un concept d'apprentissage automatique pour extraire des entités (20h00, 20h00, 20h00, 0800, 20h00, 20h, 20h00, 2000 etc.).

Une idée de la façon dont Apple est capable d'extraire des entités si rapidement dans son client de messagerie? Quel algorithme d'apprentissage automatique utiliseriez-vous pour accomplir une telle tâche?

machine-learning nlp information-extraction named-entity-recognition Martin
la source
5
J'y ai aussi pensé, en particulier le truc regex. Je sais qu'ils ont un brevet dessus, alors vous pouvez peut-être essayer de le rechercher. Cependant, cela m'intéresserait beaucoup aussi. +1
Thomas Jungblut
15
En fait, l'astuce de l'expression rationnelle capturera probablement 99% des cas avec un taux d'erreur très faible. Et c'est super rapide, lorsque vous optimisez bien les expressions régulières. Je ne serais donc pas surpris s'il s'agissait en fait d'un ensemble d'expressions régulières.
A QUITTER - Anony-Mousse

Réponses:

153

Ils utilisent probablement des techniques d' extraction d'informations pour cela.

Voici une démo de l'outil SUTime de Stanford:

http://nlp.stanford.edu:8080/sutime/process

Vous extrairiez des attributs sur les n-grammes (mots consécutifs) dans un document:

  • numberOfLetters
  • numberOfSymbols
  • longueur
  • précédentWord
  • nextWord
  • suivantWordNumberOfSymbols
    ...

Et puis utilisez un algorithme de classification, et donnez-lui des exemples positifs et négatifs:

Observation  nLetters  nSymbols  length  prevWord  nextWord isPartOfDate  
"Feb."       3         1         4       "Wed"     "29th"   TRUE  
"DEC"        3         0         3       "company" "went"   FALSE  
...

Vous pourriez vous en tirer avec 50 exemples de chacun, mais plus on est de fous. Ensuite, l'algorithme apprend sur la base de ces exemples et peut s'appliquer à de futurs exemples qu'il n'a jamais vus auparavant.

Il pourrait apprendre des règles telles que

  • si le mot précédent n'est que des caractères et peut-être des points ...
  • et le mot actuel est en "février", "mars", "le" ...
  • et le mot suivant est en "douzième", n'importe quel numéro ...
  • alors est la date

Voici une vidéo décente d'un ingénieur Google sur le sujet

Neil McGuigan
la source
4
Intéressant! Je n'y ai jamais pensé de cette façon. Merci el chef.
Martin
2
el chef, à votre avis, quel type de modèle conviendrait le mieux? Bayésien?
Martin
5
Je suis presque sûr qu'une telle approche ne fonctionnera pas mieux que, disons, une mesure f d'env. 0.9. (Remarque, ce n'est qu'un sentiment, je me trompe peut-être). D'un autre côté, j'excepterais l'approche naïve d'encodage de tous les formats courants pour être bien plus performants (peut-être 0,99+ étant donné que les formats les plus fréquents ne seront jamais manqués) et pour être plus rapide à implémenter + à l'exécution.
b.buchhold
@ b.buchhold, peut-être, mais alors vous devrez faire le même travail pour la langue suivante et la langue suivante, alors que ma solution est générale.
Neil McGuigan
@Neil McGuigan, c'est vrai. Mais vous devrez fournir beaucoup de données d'entraînement pour tous ces formats / langues, ce qui demande beaucoup plus de travail.
b.buchhold
110

C'est une technologie qu'Apple a développée il y a très longtemps Apple Data Detectors. Vous pouvez en savoir plus ici:

http://www.miramontes.com/writing/add-cacm/

Essentiellement, il analyse le texte et détecte les modèles qui représentent des éléments de données spécifiques, puis lui applique des actions contextuelles du système d'exploitation. C'est chouette.

jeffehobbs
la source
24
C'est la bonne réponse. D'autres réponses peuvent vous dire comment vous pourriez le faire, mais celle-ci vous explique comment Apple le fait .
LaC
2
pourrions-nous avoir un peu plus de détails dans la rédaction du tho? les entrées de lien unique n'ajoutent pas autant
shigeta
14
Ah, donc c'est de là que viennent tous les hits sur mon site Web :) FWIW, j'étais le chef de projet sur les détecteurs de données Apple à l'époque d'ATG; ce que je peux ajouter ici, c'est qu'il s'agissait uniquement d'une technologie OS 8 et 9 - elle n'a jamais fait le saut vers OS X. Il y a évidemment des choses similaires qui se produisent dans OS X et IOS, et, bien que je ne sois plus chez Apple et donc je ne peux pas vraiment dire, je ne serais pas surpris si l'architecture est un peu différente. Néanmoins, je m'attends à ce qu'une sorte de système de grammaire / analyseur soit toujours au cœur de celui-ci. Les ordinateurs sont rapides de nos jours et les grammaires simples sont assez bon marché.
Jim Miller
5

Une partie du puzzle pourrait être la NSDataDetectorclasse. Il est utilisé pour reconnaître certains types standard comme les numéros de téléphone.

hburde
la source
2
Il semble que la NSDataDetectorclasse soit le résultat des efforts déployés par Apple pour l'implémenter. La question est de savoir comment fonctionne la classe en interne?
Ole Begemann
3
c'est dans NSRegularExpression.h, il semble donc tout à fait possible que ce soit, comme indiqué, juste un ensemble d'expressions régulières.
riffraff
2

Une fois, j'ai écrit un analyseur pour ce faire, en utilisant pyparsing. C'est vraiment très simple, il vous suffit de bien comprendre toutes les méthodes, mais il n'y en a pas beaucoup. Cela n'a pris que quelques heures et a été assez rapide.

Stavros Korokithakis
la source
Extrait de Miramontes "Il n'est pas difficile de coder en dur un outil de reconnaissance pour une structure atomique telle qu'une URL, mais un travail considérable est nécessaire pour créer une architecture qui ouvre le processus de création de structures complexes."
Remy